Add explanatory comments and minor cleanups.

I went in to tabopen feeling a bit suspicious that the positioning code
was in some way duplicating `_get_new_tab_idx` in the parent class, or
if this code could be moved out to a common helper method or called by a
signal.

When a new tab is opened we need to position it in the tree structure.
For related and sibling tabs we need to know the tab that the new one is
opened "from". The tab related code deals with three new "new_position"
settings that the parent method doesn't know about.

For pulling it out behind a signal, we have the exiting `new_tab`
signal, but that doesn't say what the previous tab was. We could maybe
use the `TabbedBrowser._now_focused` or `TabbedBrowser.tab_dequeue` for
that, but that seems like it might be unfairly adding some new
responsibility onto those attributes? Even then we still would have no
way to know whether the user had requested a `related` or `sibling` tab.

So it seems all the code around tab positioning left here is specific to
tree tabs, assuming all the new "new_position" settings are needed, and
it's integrating with the existing code in a fine way, assuming we are
aiming for keeping the new code in subclasses. But that all begs the
question of how would an extension proper do it? I think it would do it
much the same way, but instead of subclassing TabbedBrowser it would
define a new :open command and ask uses to switch to that (or replace it
if we allow that). Then that new command would call TabbedBrowser to get
a tab and then do it's own extra stuff. And hook into the `new_tab`
signal to handle a new one being created via some other means. Although
that would not let if know whether a tab was opened as related or not
(eg created from clicking a link vs loading a session). So maybe
something to work on there for the extension API.

tabopen:
* add comment explaining necessity of the method
* add some early exits - I think this is fairly important to limit the
  number of possible logic paths maintainers have to keep in their heads
  when working with the more logic heavy code down below
* didn't add an early exit for `idx is not None` because I'm not 100%
  sure when that is set and I'm not confident enough in our test
  coverage to change it right now

position_tab:
* change to work with just Nodes instead of tabs - makes testing easier
* change the initial duplicate avoidance code to be more clear to me,
  probably it would be even more clear is `parent` was called
  `new_parent`

test_treetabbedbrowser
* add some tests for position_tab - not too happy with the mocking,
  should probably see how it looks with a proper tab, they just feel a
  bit heavy weight with the amount of mocking they bring with them

3 files changed, 297 insertions, 16 deletions

diff --git a/qutebrowser/mainwindow/treetabbedbrowser.py b/qutebrowser/mainwindow/treetabbedbrowser.py
index 860ee669f..3f2b6c7b1 100644
--- a/qutebrowser/mainwindow/treetabbedbrowser.py
+++ b/qutebrowser/mainwindow/treetabbedbrowser.py
@@ -214,18 +214,42 @@ class TreeTabbedBrowser(TabbedBrowser):
                      focused tab.  Follows `tabs.new_position.tree.sibling`.
 
         """
-        # we save this now because super.tabopen also resets the focus
+        # Save the current tab now before letting super create the new tab
+        # (and possibly give it focus). To insert the new tab correctly in the
+        # tree structure later we may need to know which tab it was opened
+        # from (for the `related` and `sibling` cases).
         cur_tab = self.widget.currentWidget()
         tab = super().tabopen(url, background, related, idx)
 
-        if config.val.tabs.tabs_are_windows or tab is cur_tab:
+        # Some trivial cases where we don't need to do positioning:
+
+        # 1. this is the first tab in the window.
+        if cur_tab is None:
+            assert self.widget.count() == 1
+            assert tab.node.parent == self.widget.tree_root
+            return tab
+
+        if (
+            config.val.tabs.tabs_are_windows or  # 2. one tab per window
+            tab is cur_tab                       # 3. opening URL in existing tab
+        ):
             return tab
 
+        # Some sanity checking to make sure the tab super created was set up
+        # as a tree style tab correctly. We don't have a TreeTab so this is
+        # heuristic to highlight any problems elsewhere in the application
+        # logic.
         assert tab.node.parent, (
             f"Node for new tab doesn't have a parent: {tab.node}"
         )
 
-        # get pos
+        # We may also be able to skip the positioning code below if the `idx`
+        # arg is passed in. Semgrep says that arg is used from undo() and
+        # SessionManager, both cases are updating the tree structure
+        # themselves after opening the new tab. On the other hand the only
+        # downside is we move the tab and update the tree twice. Although that
+        # may actually make loading large sessions a bit slower.
+
         if related:
             pos = config.val.tabs.new_position.tree.new_child
             parent = cur_tab.node
@@ -238,14 +262,14 @@ class TreeTabbedBrowser(TabbedBrowser):
             pos = config.val.tabs.new_position.tree.new_toplevel
             parent = self.widget.tree_root
 
-        self._position_tab(cur_tab, tab, pos, parent, sibling, related, background)
+        self._position_tab(cur_tab.node, tab.node, pos, parent, sibling, related, background)
 
         return tab
 
     def _position_tab(
         self,
-        cur_tab: browsertab.AbstractTab,
-        tab: browsertab.AbstractTab,
+        cur_node: notree.Node,
+        new_node: notree.Node,
         pos: str,
         parent: notree.Node,
         sibling: bool = False,
@@ -254,20 +278,21 @@ class TreeTabbedBrowser(TabbedBrowser):
     ) -> None:
         toplevel = not sibling and not related
         siblings = list(parent.children)
-        if tab.node in siblings:  # true if parent is tree_root
-            # remove it and add it later in the right position
-            siblings.remove(tab.node)
+        if new_node.parent == parent:
+            # Remove the current node from its parent's children list to avoid
+            # potentially adding it as a duplicate later.
+            siblings.remove(new_node)
 
         if pos == 'first':
             rel_idx = 0
             if config.val.tabs.new_position.stacking and related:
                 rel_idx += self._tree_tab_child_rel_idx
                 self._tree_tab_child_rel_idx += 1
-            siblings.insert(rel_idx, tab.node)
+            siblings.insert(rel_idx, new_node)
         elif pos in ['prev', 'next'] and (sibling or toplevel):
-            # pivot is the tab relative to which 'prev' or 'next' apply
-            # it is always a member of 'siblings'
-            pivot = cur_tab.node if sibling else cur_tab.node.path[1]
+            # Pivot is the tab relative to which 'prev' or 'next' apply to.
+            # Either the current node or top of the current tree.
+            pivot = cur_node if sibling else cur_node.path[1]
             direction = -1 if pos == 'prev' else 1
             rel_idx = 0 if pos == 'prev' else 1
             tgt_idx = siblings.index(pivot) + rel_idx
@@ -278,9 +303,10 @@ class TreeTabbedBrowser(TabbedBrowser):
                 elif toplevel:
                     tgt_idx += self._tree_tab_toplevel_rel_idx
                     self._tree_tab_toplevel_rel_idx += direction
-            siblings.insert(tgt_idx, tab.node)
+            siblings.insert(tgt_idx, new_node)
         else:  # position == 'last'
-            siblings.append(tab.node)
+            siblings.append(new_node)
+
         parent.children = siblings
         self.widget.tree_tab_update()
         if not background:
diff --git a/qutebrowser/misc/notree.py b/qutebrowser/misc/notree.py
index e12a8bf3f..6388a3e77 100644
--- a/qutebrowser/misc/notree.py
+++ b/qutebrowser/misc/notree.py
@@ -146,7 +146,7 @@ class Node(Generic[T]):
         """
         seen = set(value)
         if len(seen) != len(value):
-            raise TreeError("A duplicate item is present in in %r" % value)
+            raise TreeError("A duplicate item is present in %r" % value)
         new_children = list(value)
         for child in new_children:
             if child.parent is not self:
diff --git a/tests/unit/mainwindow/test_treetabbedbrowser.py b/tests/unit/mainwindow/test_treetabbedbrowser.py
new file mode 100644
index 000000000..3ae2b3b00
--- /dev/null
+++ b/tests/unit/mainwindow/test_treetabbedbrowser.py
@@ -0,0 +1,255 @@
+# SPDX-FileCopyrightText: Florian Bruhin (The Compiler) <mail@qutebrowser.org>
+#
+# SPDX-License-Identifier: GPL-3.0-or-later
+
+import pytest
+
+from qutebrowser.config.configtypes import NewTabPosition, NewChildPosition
+from qutebrowser.misc.notree import Node
+from qutebrowser.mainwindow import treetabbedbrowser, treetabwidget
+
+
+@pytest.fixture
+def mock_browser(mocker):
+    # Mock browser used as `self` below because we are actually testing mostly
+    # standalone functionality apart from the tab stack related counters.
+    # Which are also only defined in __init__, not on the class, so mock
+    # doesn't see them. Hence specifying them manually here.
+    browser = mocker.Mock(
+        spec=treetabbedbrowser.TreeTabbedBrowser,
+        widget=mocker.Mock(spec=treetabwidget.TreeTabWidget),
+        _tree_tab_child_rel_idx=0,
+        _tree_tab_sibling_rel_idx=0,
+        _tree_tab_toplevel_rel_idx=0,
+    )
+
+    # Sad little workaround to create a bound method on a mock, because
+    # _position_tab calls a method on self but we are using a mock as self to
+    # avoid initializing the whole tabbed browser class.
+    def reset_passthrough():
+        return treetabbedbrowser.TreeTabbedBrowser._reset_stack_counters(
+            browser
+        )
+    browser._reset_stack_counters = reset_passthrough
+
+    return browser
+
+
+class TestPositionTab:
+    """Test TreeTabbedBrowser._position_tab()."""
+
+    @pytest.mark.parametrize(
+        "     relation, cur_node, pos, expected", [
+            ("sibling", "three", "first", "one",),
+            ("sibling", "three", "prev", "two",),
+            ("sibling", "three", "next", "three",),
+            ("sibling", "three", "last", "six",),
+            ("sibling", "one", "first", "root",),
+            ("sibling", "one", "prev", "root",),
+            ("sibling", "one", "next", "one",),
+            ("sibling", "one", "last", "seven",),
+
+            ("related", "one", "first", "one",),
+            ("related", "one", "last", "six",),
+            ("related", "two", "first", "two",),
+            ("related", "two", "last", "two",),
+
+            (None, "five", "first", "root",),
+            (None, "five", "prev", "root",),
+            (None, "five", "next", "one",),
+            (None, "five", "last", "seven",),
+            (None, "seven", "prev", "one",),
+            (None, "seven", "next", "seven",),
+        ]
+    )
+    def test_position_tab(
+        self,
+        config_stub,
+        mock_browser,
+        # parameterized
+        relation,
+        cur_node,
+        pos,
+        expected,
+    ):
+        """Test tree tab positioning.
+
+        How to use the parameters above:
+        * refer to the tree structure being passed to create_tree() below, that's
+          our starting state
+        * specify how the new node should be related to the current one
+        * specify cur_node by value, which is the tab currently focused when the
+          new tab is opened and the one the "sibling" and "related" arguments
+          refer to
+        * set "pos" which is the position of the new node in the list of
+          siblings it's going to end up in. It should be one of first, list, prev,
+          next (except the "related" relation doesn't support prev and next)
+        * specify the expected preceding node (the preceding sibling if there is
+          one, otherwise the parent) after the new node is positioned, "root" is
+          a valid value for this
+
+        Having the expectation being the preceding tab (sibling or parent) is
+        a bit limited, in particular if the new tab somehow ends up as a child
+        instead of the next sibling you wouldn't be able to tell those
+        situations apart. But I went this route to avoid having to specify
+        multiple trees in the parameters.
+        """
+        root = self.create_tree(
+            """
+            - one
+              - two
+              - three
+              - four
+                - five
+              - six
+            - seven
+            """,
+        )
+        new_node = Node("new", parent=root)
+
+        config_stub.val.tabs.new_position.stacking = False
+        self.call_position_tab(
+            mock_browser,
+            root,
+            cur_node,
+            new_node,
+            pos,
+            relation,
+        )
+
+        preceding_node = None
+        if new_node.parent.children[0] == new_node:
+            preceding_node = new_node.parent
+        else:
+            for n in new_node.parent.children:
+                if n.value == "new":
+                    break
+                preceding_node = n
+            else:
+                pytest.fail("new tab not found")
+
+        assert preceding_node.value == expected
+
+    def call_position_tab(
+        self,
+        mock_browser,
+        root,
+        cur_node,
+        new_node,
+        pos,
+        relation,
+        background=False,
+    ):
+        sibling = related = False
+        if relation == "sibling":
+            sibling = True
+        elif relation == "related":
+            related = True
+        elif relation == "background":
+            background = True
+        elif relation is not None:
+            pytest.fail(
+                "Valid values for relation are: "
+                "sibling, related, background, None"
+            )
+
+        # This relation -> parent mapping is copied from
+        # TreeTabbedBrowser.tabopen().
+        cur_node = next(n for n in root.traverse() if n.value == cur_node)
+        assert not (related and sibling)
+        if related:
+            parent = cur_node
+            NewChildPosition().from_str(pos)
+        elif sibling:
+            parent = cur_node.parent
+            NewTabPosition().from_str(pos)
+        else:
+            parent = root
+            NewTabPosition().from_str(pos)
+
+        treetabbedbrowser.TreeTabbedBrowser._position_tab(
+            mock_browser,
+            cur_node=cur_node,
+            new_node=new_node,
+            pos=pos,
+            parent=parent,
+            sibling=sibling,
+            related=related,
+            background=background,
+        )
+
+    def create_tree(self, tree_str):
+        # Construct a notree.Node tree from the test string.
+        root = Node("root")
+        previous_indent = ''
+        previous_node = root
+        for line in tree_str.splitlines():
+            if not line.strip():
+                continue
+            indent, value = line.split("-")
+            node = Node(value.strip())
+            if len(indent) > len(previous_indent):
+                node.parent = previous_node
+            elif len(indent) == len(previous_indent):
+                node.parent = previous_node.parent
+            else:
+                # TODO: handle going up in jumps of more than one rank
+                node.parent = previous_node.parent.parent
+            previous_indent = indent
+            previous_node = node
+        return root
+
+    @pytest.mark.parametrize(
+        "     test_tree, relation, pos, expected", [
+            ("tree_one", "sibling", "next", "one,two,new1,new2,new3",),
+            ("tree_one", "sibling", "prev", "one,new3,new2,new1,two",),
+            ("tree_one", None, "next", "one,two,new1,new2,new3",),
+            ("tree_one", None, "prev", "new3,new2,new1,one,two",),
+            ("tree_one", "related", "first", "one,two,new1,new2,new3",),
+            ("tree_one", "related", "last", "one,two,new1,new2,new3",),
+        ]
+    )
+    def test_position_tab_stacking(
+        self,
+        config_stub,
+        mock_browser,
+        # parameterized
+        test_tree,
+        relation,
+        pos,
+        expected,
+    ):
+        """Test tree tab positioning with tab stacking enabled.
+
+        With tab stacking enabled the first background tab should be opened
+        beside the current one, successive background tabs should be opened on
+        the other side of prior opened tabs, not beside the current tab.
+        This test covers what is currently implemented, I'm not sure all the
+        desired behavior is implemented currently though.
+        """
+        # Simpler tree here to make the assert string a bit simpler.
+        # Tab "two" is hardcoded as cur_tab.
+        root = self.create_tree(
+            """
+            - one
+              - two
+            """,
+        )
+        config_stub.val.tabs.new_position.stacking = True
+
+        for val in ["new1", "new2", "new3"]:
+            new_node = Node(val, parent=root)
+
+            self.call_position_tab(
+                mock_browser,
+                root,
+                "two",
+                new_node,
+                pos,
+                relation,
+                background=True,
+            )
+
+        actual = ",".join([n.value for n in root.traverse()])
+        actual = actual[len("root,"):]
+        assert actual == expected