Repository: tweag/FawltyDeps

Issue:
Maximum recursion exceeded in `dirs_between`
**Describe the bug**
A clear and concise description of what the bug is.

<pre>
Traceback (most recent call last):
  File "/home/vscode/.cache/bazel/_bazel_vscode/d9fd8dd9485b3d1d1994c3846baefa35/sandbox/linux-sandbox/914/execroot/_main/bazel-out/k8-opt-exec-ST-ff2b6a5febf8/bin/tools/build/python/fawltydeps_wrapper.runfiles/_main/tools/build/python/fawltydeps_wrapper.py", line 96, in <module>
    ret = main(args, None, output_file)
  File "/home/vscode/.cache/bazel/_bazel_vscode/d9fd8dd9485b3d1d1994c3846baefa35/sandbox/linux-sandbox/914/execroot/_main/bazel-out/k8-opt-exec-ST-ff2b6a5febf8/bin/tools/build/python/fawltydeps_wrapper.runfiles/rules_python~~pip~pypi_310_fawltydeps/site-packages/fawltydeps/main.py", line 365, in main
    analysis = Analysis.create(settings, stdin)
  File "/home/vscode/.cache/bazel/_bazel_vscode/d9fd8dd9485b3d1d1994c3846baefa35/sandbox/linux-sandbox/914/execroot/_main/bazel-out/k8-opt-exec-ST-ff2b6a5febf8/bin/tools/build/python/fawltydeps_wrapper.runfiles/rules_python~~pip~pypi_310_fawltydeps/site-packages/fawltydeps/main.py", line 185, in create
    ret.undeclared_deps  # noqa: B018
  File "/home/vscode/.cache/bazel/_bazel_vscode/d9fd8dd9485b3d1d1994c3846baefa35/execroot/_main/external/rules_python~~python~python_3_10_x86_64-unknown-linux-gnu/lib/python3.10/functools.py", line 981, in __get__
    val = self.func(instance)
  File "/home/vscode/.cache/bazel/_bazel_vscode/d9fd8dd9485b3d1d1994c3846baefa35/sandbox/linux-sandbox/914/execroot/_main/bazel-out/k8-opt-exec-ST-ff2b6a5febf8/bin/tools/build/python/fawltydeps_wrapper.runfiles/rules_python~~pip~pypi_310_fawltydeps/site-packages/fawltydeps/main.py", line 153, in undeclared_deps
    self.imports, self.resolved_deps, self.resolvers, self.settings
  File "/home/vscode/.cache/bazel/_bazel_vscode/d9fd8dd9485b3d1d1994c3846baefa35/execroot/_main/external/rules_python~~python~python_3_10_x86_64-unknown-linux-gnu/lib/python3.10/functools.py", line 981, in __get__
    val = self.func(instance)
  File "/home/vscode/.cache/bazel/_bazel_vscode/d9fd8dd9485b3d1d1994c3846baefa35/sandbox/linux-sandbox/914/execroot/_main/bazel-out/k8-opt-exec-ST-ff2b6a5febf8/bin/tools/build/python/fawltydeps_wrapper.runfiles/rules_python~~pip~pypi_310_fawltydeps/site-packages/fawltydeps/main.py", line 112, in imports
    return list(
  File "/home/vscode/.cache/bazel/_bazel_vscode/d9fd8dd9485b3d1d1994c3846baefa35/sandbox/linux-sandbox/914/execroot/_main/bazel-out/k8-opt-exec-ST-ff2b6a5febf8/bin/tools/build/python/fawltydeps_wrapper.runfiles/rules_python~~pip~pypi_310_fawltydeps/site-packages/fawltydeps/extract_imports.py", line 214, in parse_sources
    yield from parse_source(source, stdin)
  File "/home/vscode/.cache/bazel/_bazel_vscode/d9fd8dd9485b3d1d1994c3846baefa35/sandbox/linux-sandbox/914/execroot/_main/bazel-out/k8-opt-exec-ST-ff2b6a5febf8/bin/tools/build/python/fawltydeps_wrapper.runfiles/rules_python~~pip~pypi_310_fawltydeps/site-packages/fawltydeps/extract_imports.py", line 196, in parse_source
    src_paths=tuple(dirs_between(src.base_dir, src.path.parent)),
  File "/home/vscode/.cache/bazel/_bazel_vscode/d9fd8dd9485b3d1d1994c3846baefa35/sandbox/linux-sandbox/914/execroot/_main/bazel-out/k8-opt-exec-ST-ff2b6a5febf8/bin/tools/build/python/fawltydeps_wrapper.runfiles/rules_python~~pip~pypi_310_fawltydeps/site-packages/fawltydeps/utils.py", line 27, in dirs_between
    yield from dirs_between(parent, child.parent)
  File "/home/vscode/.cache/bazel/_bazel_vscode/d9fd8dd9485b3d1d1994c3846baefa35/sandbox/linux-sandbox/914/execroot/_main/bazel-out/k8-opt-exec-ST-ff2b6a5febf8/bin/tools/build/python/fawltydeps_wrapper.runfiles/rules_python~~pip~pypi_310_fawltydeps/site-packages/fawltydeps/utils.py", line 27, in dirs_between
    yield from dirs_between(parent, child.parent)
  File "/home/vscode/.cache/bazel/_bazel_vscode/d9fd8dd9485b3d1d1994c3846baefa35/sandbox/linux-sandbox/914/execroot/_main/bazel-out/k8-opt-exec-ST-ff2b6a5febf8/bin/tools/build/python/fawltydeps_wrapper.runfiles/rules_python~~pip~pypi_310_fawltydeps/site-packages/fawltydeps/utils.py", line 27, in dirs_between
    <b>yield from dirs_between(parent, child.parent)
  [Previous line repeated 983 more times]</b>
  File "/home/vscode/.cache/bazel/_bazel_vscode/d9fd8dd9485b3d1d1994c3846baefa35/sandbox/linux-sandbox/914/execroot/_main/bazel-out/k8-opt-exec-ST-ff2b6a5febf8/bin/tools/build/python/fawltydeps_wrapper.runfiles/rules_python~~pip~pypi_310_fawltydeps/site-packages/fawltydeps/utils.py", line 26, in dirs_between
    if child != parent:
  File "/home/vscode/.cache/bazel/_bazel_vscode/d9fd8dd9485b3d1d1994c3846baefa35/execroot/_main/external/rules_python~~python~python_3_10_x86_64-unknown-linux-gnu/lib/python3.10/pathlib.py", line 666, in __eq__
    return self._cparts == other._cparts and self._flavour is other._flavour
  File "/home/vscode/.cache/bazel/_bazel_vscode/d9fd8dd9485b3d1d1994c3846baefa35/execroot/_main/external/rules_python~~python~python_3_10_x86_64-unknown-linux-gnu/lib/python3.10/pathlib.py", line 660, in _cparts
    self._cached_cparts = self._flavour.casefold_parts(self._parts)
<b>RecursionError: maximum recursion depth exceeded</b>
</pre>

**To Reproduce**
I guess it happens when parent is *not* a parent of child.parent. Then the loop keeps going forever.

**Expected behavior**
I am really puzzled by dirs_between. It returns a list of which only the first entry is used. It also assumes that there is a parent relationship, which is apparently not the case in my test case. (Maybe because of --base-dir ?)

So the expected behavior is to not crash. I have patched it successfully with 


```patch
diff --git a/fawltydeps/utils.py b/fawltydeps/utils.py
index 4639247..82ec15f 100644
--- a/fawltydeps/utils.py
+++ b/fawltydeps/utils.py
@@ -27,9 +27,10 @@ def version() -> str:
 
 def dirs_between(parent: Path, child: Path) -> Iterator[Path]:
     """Yield directories between 'parent' and 'child', inclusive."""
-    yield child
-    if child != parent:
-        yield from dirs_between(parent, child.parent)
+    return [ p for p in child.parents if str(p).startswith(str(parent))] or [parent]
+    #yield child
+    #if child != parent:
+    #    yield from dirs_between(parent, child.parent)
 
 
 def hide_dataclass_fields(instance: object, *field_names: str) -> None:
```

**Environment**
 - OS name + version:
 - Version of the code:

**Additional context**
Add any other context about the problem here.

Hints from issue comments:
@layus: Another way to view this is to error out with a proper error message. That situation makes little sense, but should probably not yield to a stack trace.
@layus: One case where this makes sense for me is with a pytest shim. The shim is located elsewhere in the tree, not under base-dir. @jherland: Yeah, this looks like a clear bug, probably exposed by the recent `--base-dir` work.

There is obviously an assumption being made on the `parent` and `child` arguments, but that assumption is never checked! 😱

Looking at the users of `dirs_between()`, they _do_ actually use all entries in the returned list:
- `for dir_path in reversed(list(dirs_between(parent_dir, child_dir))):`
- `src_paths=tuple(dirs_between(src.base_dir, src.path.parent)),`

Need to keep digging a but, but should have a fix ready, soon.

Solution patch:
diff --git a/fawltydeps/extract_imports.py b/fawltydeps/extract_imports.py
index f174fa1..28dfaee 100644
--- a/fawltydeps/extract_imports.py
+++ b/fawltydeps/extract_imports.py
@@ -188,14 +188,10 @@ def parse_source(
 
     assert isinstance(src.path, Path)  # noqa: S101, sanity check / silence mypy
 
-    local_context = (
-        None
-        if src.base_dir is None
-        else make_isort_config(
-            path=src.base_dir,
-            src_paths=tuple(dirs_between(src.base_dir, src.path.parent)),
-        )
-    )
+    local_context = None
+    if src.base_dir is not None:
+        src_paths = tuple(dirs_between(src.base_dir, src.path.parent))
+        local_context = make_isort_config(path=src.base_dir, src_paths=src_paths)
 
     if src.path.suffix == ".py":
         logger.info("Parsing Python file %s", src.path)
diff --git a/fawltydeps/utils.py b/fawltydeps/utils.py
index d199e74..a1b3c74 100644
--- a/fawltydeps/utils.py
+++ b/fawltydeps/utils.py
@@ -4,6 +4,7 @@ import logging
 import sys
 from collections.abc import Iterator
 from dataclasses import is_dataclass
+from itertools import takewhile
 from pathlib import Path
 from typing import TypeVar
 
@@ -21,10 +22,11 @@ def version() -> str:
 
 
 def dirs_between(parent: Path, child: Path) -> Iterator[Path]:
-    """Yield directories between 'parent' and 'child', inclusive."""
-    yield child
-    if child != parent:
-        yield from dirs_between(parent, child.parent)
+    """Return directories between 'parent' and 'child', inclusive.
+
+    Return nothing if 'parent' is not a parent of `child'.
+    """
+    return takewhile(lambda p: p.is_relative_to(parent), [child, *child.parents])
 
 
 def hide_dataclass_fields(instance: object, *field_names: str) -> None:


Test patch:
diff --git a/tests/test_extract_imports_simple.py b/tests/test_extract_imports_simple.py
index 0825bca..6558db0 100644
--- a/tests/test_extract_imports_simple.py
+++ b/tests/test_extract_imports_simple.py
@@ -2,6 +2,7 @@
 
 import json
 import logging
+from dataclasses import dataclass, field
 from io import BytesIO
 from pathlib import Path
 from textwrap import dedent
@@ -80,12 +81,14 @@ def generate_notebook(
 def write_code_sources(write_tmp_files):
     """A wrapper around write_tmp_files() that return CodeSource objects."""
 
-    def _inner(file_contents: dict[str, str]) -> tuple[Path, list[CodeSource]]:
+    def _inner(
+        file_contents: dict[str, str], base_dir: Path = Path()
+    ) -> tuple[Path, list[CodeSource]]:
         tmp_path = write_tmp_files(file_contents)
         sources = []
         for filepath in file_contents:
             assert filepath.endswith((".py", ".ipynb"))
-            sources.append(CodeSource(tmp_path / filepath, tmp_path))
+            sources.append(CodeSource(tmp_path / filepath, tmp_path / base_dir))
         return tmp_path, sources
 
     return _inner
@@ -492,73 +495,89 @@ def test_parse_sources__imports__are_extracted_in_order_of_encounter(
     assert list(parse_sources(code_sources)) == expect
 
 
+@dataclass
+class FirstPartyImportTestVector:
+    """Test vectors for verifying that 1st-party imports are ignored by parse_sources()."""
+
+    id: str
+    sources: dict[str, str]
+    expect_imports: list[tuple[str, str, int]] = field(default_factory=list)
+    base_dir: Path = Path()
+
+
+first_party_import_vectors = [
+    FirstPartyImportTestVector(
+        id="ignore_imports_from_the_same_dir",
+        sources={
+            "my_application.py": "import my_utils",
+            "my_utils.py": "import sys",
+        },
+    ),
+    FirstPartyImportTestVector(
+        id="ignore_self_imports",
+        sources={
+            "my_app/__init__.py": "",
+            "my_app/main.py": "from my_app import utils",
+            "my_app/utils.py": "import numpy",
+        },
+        expect_imports=[("numpy", "my_app/utils.py", 1)],
+    ),
+    FirstPartyImportTestVector(
+        id="ignore_imports_from_the_same_child_dir",
+        sources={
+            "classifier/effnet.py": "from resnet import make_weights_for_balanced_classes",
+            "classifier/resnet.py": "make_weights_for_balanced_classes = lambda x:x",
+        },
+    ),
+    FirstPartyImportTestVector(
+        id="ignore_imports_from_the_same_nested_dir",
+        sources={
+            "dir/classifier/effnet.py": "from resnet import make_weights_for_balanced_classes",
+            "dir/classifier/resnet.py": "make_weights_for_balanced_classes = lambda x:x",
+        },
+    ),
+    FirstPartyImportTestVector(
+        id="ignore_imports_from_submodule",
+        sources={
+            "detr/main.py": "import util.misc as utils",
+            "detr/util/__init__.py": "",
+            "detr/util/misc.py": "a = 1",
+        },
+    ),
+    FirstPartyImportTestVector(
+        id="ignore_imports_from_uncle",
+        sources={
+            "efficientdet/effdet/data/loader.py": "from effdet.anchors import AnchorLabeler",
+            "efficientdet/effdet/data/__init__.py": "",
+            "efficientdet/effdet/__init__.py": "",
+            "efficientdet/effdet/anchors.py": "class AnchorLabel",
+        },
+    ),
+    FirstPartyImportTestVector(
+        id="base_dir_not_a_parent_of_source_file",
+        sources={
+            "some_project/main.py": "from lib import support",
+            "lib/support.py": "import numpy",
+        },
+        expect_imports=[("numpy", "lib/support.py", 1)],
+        base_dir=Path("lib/"),
+    ),
+]
+
+
 @pytest.mark.parametrize(
-    ("code", "expect_data"),
-    [
-        pytest.param(
-            {
-                "my_application.py": "import my_utils",
-                "my_utils.py": "import sys",
-            },
-            [],
-            id="__ignore_imports_from_the_same_dir",
-        ),
-        pytest.param(
-            {
-                "my_app/__init__.py": "",
-                "my_app/main.py": "from my_app import utils",
-                "my_app/utils.py": "import numpy",
-            },
-            [("numpy", "my_app/utils.py", 1)],
-            id="__ignore_self_imports",
-        ),
-        pytest.param(
-            {
-                "classifier/effnet.py": "from resnet import make_weights_for_balanced_classes",
-                "classifier/resnet.py": "make_weights_for_balanced_classes = lambda x:x",
-            },
-            [],
-            id="__ignore_imports_from_the_same_child_dir",
-        ),
-        pytest.param(
-            {
-                "dir/classifier/effnet.py": "from resnet import make_weights_for_balanced_classes",
-                "dir/classifier/resnet.py": "make_weights_for_balanced_classes = lambda x:x",
-            },
-            [],
-            id="__ignore_imports_from_the_same_nested_dir",
-        ),
-        pytest.param(
-            {
-                "detr/main.py": "import util.misc as utils",
-                "detr/util/__init__.py": "",
-                "detr/util/misc.py": "a = 1",
-            },
-            [],
-            id="__ignore_imports_from_submodule",
-        ),
-        pytest.param(
-            {
-                "efficientdet/effdet/data/loader.py": "from effdet.anchors import AnchorLabeler",
-                "efficientdet/effdet/data/__init__.py": "",
-                "efficientdet/effdet/__init__.py": "",
-                "efficientdet/effdet/anchors.py": "class AnchorLabel",
-            },
-            [],
-            id="__ignore_imports_from_uncle",
-        ),
-    ],
+    "vector", [pytest.param(v, id=v.id) for v in first_party_import_vectors]
 )
-def test_parse_sources__ignore_first_party_imports(
-    code, expect_data, write_code_sources
-):
-    tmp_path, code_sources = write_code_sources(code)
+def test_parse_sources__ignore_first_party_imports(vector, write_code_sources):
+    tmp_path, code_sources = write_code_sources(
+        vector.sources, base_dir=vector.base_dir
+    )
     expect = [
         ParsedImport(
             name=e[0],
             source=Location(path=tmp_path / e[1], lineno=e[2]),
         )
-        for e in expect_data
+        for e in vector.expect_imports
     ]
 
     assert list(parse_sources(code_sources)) == expect