Switch pane not following visual layout of panes

[dholms]

Discord username (optional)

No response

Describe the bug

I'm seeing this when splitting my terminal into 4 panes (in a 2x2 square). 
"Switch pane left" goes to the terminal immediately to the left. 
"Switch pane right" goes to the terminal up and to the right.

To Reproduce

1. Open Warp
2. Split pane right
3. split each of those panes down
4. go to the bottom left pane & try to switch pane right
5. it switches to the top right pane

If you do the splitting in reverse (so split pane down, then split each of those right), the problem is that "switch pane down" from the top right pane goes to the bottom left pane.

Expected behaviour

I would expect the switch panes to be based on the visual layout of the panes, not the order in which they were created.

If I switch pane right, I expect it to go directly to the right. If I switch pane down, I expect it to go directly down.

Screenshots

No response

Operating System

MacOS

OS Version

12.2.1

Additional context

No response

[aditya211935]

https://www.warp.dev/blog/using-tree-data-structures-to-implement-terminal-split-panes-more-fun-than-it-sounds

It's due to this heuristic.

There's a bug with the current heuristic which causes this issue to happen. I came up with the following modification. @zachlloyd @alokedesai @kevinyang372 @elviskahoro Let me know any counter examples where this modification might fail.

Example: This node is split vertically, then horizontally. Suppose we initiate command "Switch panes up" from pane 2. It should go to pane 0, but instead it'll go to pane 1.

         V
    |------|
   H        H
|---|     |---|
0   1    2    3

So this issue happens because the algorithm always selects the last/first child regardless of direction. One modification we can make is (giving an example for navigating up, but this can be generalized to all the directions):

1. Store the index of the node we're navigating from, along with total number of siblings of the current node (don't care about the length of each subtree, for example if pane 3 was further split into 2 then we don't care about that. we only need number of sibliings of pane 2, which will be 2). Let's call this numerator = 1 and denominator = 2.
2. Now do the usual steps of the algorithm, find the first node whose split direction matches navigation direction (which will always be the great grandfather or lesser of the current node) and choose leftmost sibling (because direction is up). If there's no leftmost sibling, travel up again. (as mentioned in the blog)
3. Now, after finding the node from above step, we'll start traversing downwards. For reference, we're currently situated at the root of the tree in the above example with numerator=1, denominator=2. Again, to maintain proximity when travelling downwards we'll always choose the closest node, which in this case is the first left node.
4. Now, we'll encounter either a split or a pane. If a pane, then algorithm is completed. If a split, then we know that this split is in a different direction compared to the navigation direction (which is "up" currently). Now, to choose the correct node in this opposite split, we can use the following formula index = round(no_of_nodes * numerator / denominator) where no_of_nodes is the number of nodes that the current split contains (which is 2). Substituting the values, we get index=1 which says to pick the first child.
5. So we pick the child and traverse downwards and repeat step 4 until we hit a pane. The point to note here is that when traveling downwards, if we encounter a split direction that's different to navigation direction, we use the formula. Otherwise when the directions are same, we always pick the closest node (which will be the first left node).

The intuition behind the formula is that we're looking for the most optimal index in the opposite direction where we want to traverse downwards. Suppose a pane is split in the following way.

1. Vertically first.
2. Top most portion is split horizontally 3 times.
3. Bottom most portion is split horizontally 2 time. Now if we want to move up from bottom left pane, then by plugging the formula all we're trying to do is to find a mapping for 2x horizontally split pane into 3x horizontally split pane.

The good part about this is, if you want to get fancy, you could very easily plug the widths (flex-ratio as they're called in the blog) into the formula to get the most optimal pane to navigate to, albeit with some caveats. Thinking about this, I found 3 different ways in which we can plug flex-ratios to the formula. Note that only step 4 will be changed, all the other steps will remain the same. Before starting, we'll first convert flex-ratio array into a prefix sum array. Let's call it ps_arr. The good part about this is it kind of denotes a line segment of length 1. For example, let's suppose flex-ratio array was [0.3, 0.5, 0.2]. Then ps_arr = [0.3, 0.8, 1.0]. Thus, extending the logic, we can say first segment goes from (0, 0.3), second from (0.3, 0.8), third from (0.8, 1.0). Thus the problem simply becomes "Find most optimal matching for a pair of line segments". Let's suppose we have ps_arr_a and ps_arr_b. Since pane's height or width can be simply represented as line segments, we'll try to find most optimal matching for a segment from ps_arr_b (let's call it x) within ps_arr_a.

1. Choose first approach In this approach we'll find the first line segment in ps_arr_a that's completely with x or x is completely with the said line segement. Since ps_arr_a is sorted, we can easily find if such a line segment exists or not. If such segment doesn't exist, we'll have two segments that overlap x. We'll just take the segment with the largest overlap. Running time: Log(M) where M is length of ps_arr_a.
2. Choose last approach This is same as the above approach. Only difference is that instead of choosing first segment in ps_arr_a that's compeltely within x, we choose the last segment that's completely within x. Running time is also Log(M)
3. Greatest overlap approach. In this, instead of choosing a segment that's completely within x, or the other way around, we choose a segment that has the greatest overlap with x. Again, we can use binary search to find starting point of one such segment, and the optimal answer will always exist either to the left or to the right of our choosen segment. Algorithm is pretty similar to the above two approaches.

Also, note that when computing ps_arr from flex-ratio, we have to take care of the offsets arising from the previous split. This is because each flex-ratio is local to its own region. For example, if flex ratio for vertically and then horizontally split pane is is [0.5, [0.33, 0.33, 0.33] ], then ps_arr for [0.33, 0.33, 0.33] will be computed as [0.5+0.5*0.33, ...], with the added assumption that the segment starts from 0.5. Same kind of offset calculation will also need to be done to x to make it aligned to ps_arr with which we're trying to match it. Basically, all the offsets doing is its calculating how far from horizontal or vertical segment is our ps_arr or x.

I've skipped implementation details about the above 3 algorithms as there will be edge cases which will be very long if explained fully. But I hope that the idea was successfully conveyed. Let me know if it's not clear, and I'll try to create a reference implementation when I get time.

[elviskahoro]

Thanks @aditya211935 I think the product owner here is kevin. I'll forward this to him!

[kevinyang372]

@aditya211935 Very interesting idea! One small thing I noticed is we not only need to store the (nominator, denominator) pair of the original node that matches the axis we are navigating from, but also that of every matching axis node as we traverse up the tree.

Take the example below:

User hits up on the red focused pane. We should navigate them to the last pane on the top axis given the visual layout and not the round((1/2) 3) = 0 index on the top axis. To get the correct result, we need to keep track of the (nominator, denominator) pair as we move up the tree and update it every time we encounter an axis node matching the navigation axis. In the example above, the final nominator denominator par should be (((1/2) + 1) / 2 + 1) / 2 = (7, 8) and the resulting index will thus be round((7/8) 3) = 2.

I considered taking this approach to give a more natural navigation experience but ends up going with the simple solution because of two reasons: 1) Most users tend to have a two / three pane layout and the simple heuristic suffice for that. 2) The code will be much more readable and maintainable.

But definitely agree as Warp grows, we should get this behavior right in the future. Just filed a ticket internally to keep track of this. Thank you for your great idea @aditya211935 !

[aditya211935]

@kevinyang372 Sure, happy to help. Love using warp. But the simple heuristic breaks down for navigating a 2x2 split pane right? So, should we be prioritizing a more complex heuristic because, speaking as an iTerm user, I usually have a 2x2 pane and miss navigating simply through arrow key shortcuts.

Speaking of heuristic, yep I missed calculating the contribution of a pane with respect to the area it lives in. However, don't you think that a heuristic that uses flex-ratio to make judgement on which pane to navigate to makes more sense than the numerator and denominator one? Beacuse if you look at the above example, round(7*3/8) = round(2.625) = 3. But since the shaded pane can be resized arbitarily, it could be resized in such a way that it sits right above the top left pane. I agree it's probably an overkill at this point, but for a more complete heuristic that considers the contributions of every pane in the area, the contribution of panes can't be considered as constants.

Also, btw, I read that you've plans on open sourcing the client part. Does the client include the whole warp mac app that contains this split pane logic? Would love to tinker around with it.

[UPDATE]: I took a stab at implementing it in C++. Here's the code if that's helpful (although it's messy, so read at your own peril!).

https://gist.github.com/aditya211935/2d6f706d6c0e59bc6403847d68279839

[hossein-haeri]

I'm on Ubuntu 22.04 (warp v0.2024.09.17.08.02.stable_01) and it seems switch pane key shortcuts don't work. It also has conflict with the cnt+alt+left/right with the Ubuntu's screen switch but I even after I defined another shortcut it didn't work.