Merge pull request #7931 from bluetech/xunit-quadratic-2

fixtures: fix quadratic behavior in the number of autouse fixtures

2 files changed, 44 insertions, 56 deletions

diff --git a/src/_pytest/fixtures.py b/src/_pytest/fixtures.py
index 94171b5f6..18094f21c 100644
--- a/src/_pytest/fixtures.py
+++ b/src/_pytest/fixtures.py
@@ -1412,9 +1412,10 @@ class FixtureManager:
         self.config: Config = session.config
         self._arg2fixturedefs: Dict[str, List[FixtureDef[Any]]] = {}
         self._holderobjseen: Set[object] = set()
-        self._nodeid_and_autousenames: List[Tuple[str, List[str]]] = [
-            ("", self.config.getini("usefixtures"))
-        ]
+        # A mapping from a nodeid to a list of autouse fixtures it defines.
+        self._nodeid_autousenames: Dict[str, List[str]] = {
+            "": self.config.getini("usefixtures"),
+        }
         session.config.pluginmanager.register(self, "funcmanage")
 
     def _get_direct_parametrize_args(self, node: nodes.Node) -> List[str]:
@@ -1476,18 +1477,12 @@ class FixtureManager:
 
         self.parsefactories(plugin, nodeid)
 
-    def _getautousenames(self, nodeid: str) -> List[str]:
-        """Return a list of fixture names to be used."""
-        autousenames: List[str] = []
-        for baseid, basenames in self._nodeid_and_autousenames:
-            if nodeid.startswith(baseid):
-                if baseid:
-                    i = len(baseid)
-                    nextchar = nodeid[i : i + 1]
-                    if nextchar and nextchar not in ":/":
-                        continue
-                autousenames.extend(basenames)
-        return autousenames
+    def _getautousenames(self, nodeid: str) -> Iterator[str]:
+        """Return the names of autouse fixtures applicable to nodeid."""
+        for parentnodeid in nodes.iterparentnodeids(nodeid):
+            basenames = self._nodeid_autousenames.get(parentnodeid)
+            if basenames:
+                yield from basenames
 
     def getfixtureclosure(
         self,
@@ -1503,7 +1498,7 @@ class FixtureManager:
         # (discovering matching fixtures for a given name/node is expensive).
 
         parentid = parentnode.nodeid
-        fixturenames_closure = self._getautousenames(parentid)
+        fixturenames_closure = list(self._getautousenames(parentid))
 
         def merge(otherlist: Iterable[str]) -> None:
             for arg in otherlist:
@@ -1648,7 +1643,7 @@ class FixtureManager:
                 autousenames.append(name)
 
         if autousenames:
-            self._nodeid_and_autousenames.append((nodeid or "", autousenames))
+            self._nodeid_autousenames.setdefault(nodeid or "", []).extend(autousenames)
 
     def getfixturedefs(
         self, argname: str, nodeid: str
@@ -1668,6 +1663,7 @@ class FixtureManager:
     def _matchfactories(
         self, fixturedefs: Iterable[FixtureDef[Any]], nodeid: str
     ) -> Iterator[FixtureDef[Any]]:
+        parentnodeids = set(nodes.iterparentnodeids(nodeid))
         for fixturedef in fixturedefs:
-            if nodes.ischildnode(fixturedef.baseid, nodeid):
+            if fixturedef.baseid in parentnodeids:
                 yield fixturedef
diff --git a/src/_pytest/nodes.py b/src/_pytest/nodes.py
index 6ab08953a..dd58d5df9 100644
--- a/src/_pytest/nodes.py
+++ b/src/_pytest/nodes.py
@@ -1,6 +1,5 @@
 import os
 import warnings
-from functools import lru_cache
 from pathlib import Path
 from typing import Callable
 from typing import Iterable
@@ -44,46 +43,39 @@ SEP = "/"
 tracebackcutdir = py.path.local(_pytest.__file__).dirpath()
 
 
-@lru_cache(maxsize=None)
-def _splitnode(nodeid: str) -> Tuple[str, ...]:
-    """Split a nodeid into constituent 'parts'.
+def iterparentnodeids(nodeid: str) -> Iterator[str]:
+    """Return the parent node IDs of a given node ID, inclusive.
 
-    Node IDs are strings, and can be things like:
-        ''
-        'testing/code'
-        'testing/code/test_excinfo.py'
-        'testing/code/test_excinfo.py::TestFormattedExcinfo'
+    For the node ID
 
-    Return values are lists e.g.
-        []
-        ['testing', 'code']
-        ['testing', 'code', 'test_excinfo.py']
-        ['testing', 'code', 'test_excinfo.py', 'TestFormattedExcinfo']
-    """
-    if nodeid == "":
-        # If there is no root node at all, return an empty list so the caller's
-        # logic can remain sane.
-        return ()
-    parts = nodeid.split(SEP)
-    # Replace single last element 'test_foo.py::Bar' with multiple elements
-    # 'test_foo.py', 'Bar'.
-    parts[-1:] = parts[-1].split("::")
-    # Convert parts into a tuple to avoid possible errors with caching of a
-    # mutable type.
-    return tuple(parts)
-
-
-def ischildnode(baseid: str, nodeid: str) -> bool:
-    """Return True if the nodeid is a child node of the baseid.
-
-    E.g. 'foo/bar::Baz' is a child of 'foo', 'foo/bar' and 'foo/bar::Baz',
-    but not of 'foo/blorp'.
+        "testing/code/test_excinfo.py::TestFormattedExcinfo::test_repr_source"
+
+    the result would be
+
+        ""
+        "testing"
+        "testing/code"
+        "testing/code/test_excinfo.py"
+        "testing/code/test_excinfo.py::TestFormattedExcinfo"
+        "testing/code/test_excinfo.py::TestFormattedExcinfo::test_repr_source"
+
+    Note that :: parts are only considered at the last / component.
     """
-    base_parts = _splitnode(baseid)
-    node_parts = _splitnode(nodeid)
-    if len(node_parts) < len(base_parts):
-        return False
-    return node_parts[: len(base_parts)] == base_parts
+    pos = 0
+    sep = SEP
+    yield ""
+    while True:
+        at = nodeid.find(sep, pos)
+        if at == -1 and sep == SEP:
+            sep = "::"
+        elif at == -1:
+            if nodeid:
+                yield nodeid
+            break
+        else:
+            if at:
+                yield nodeid[:at]
+            pos = at + len(sep)
 
 
 _NodeType = TypeVar("_NodeType", bound="Node")