`detect()`'s ignore-pattern list grows for the whole walk instead of being scoped to the current subtree — every file/directory check in a large monorepo scans every `.gitignore` ever seen, not just its own ancestors

[sub4biz]

Found alongside a second, unrelated instance of the same underlying mistake — recomputing something inside
a loop instead of once outside it — in a completely different part of the pipeline (extract_corpus_parallel
in llm.py, the semantic-extraction merge step, not the file-detection step below). Fixed separately in
#2827. Flagging the connection in case it's useful context, since both were found in the same session while
chasing why a full extraction run kept stalling for hours.

cc @safishamsi — two independent performance issues found back-to-back, wanted to flag both together.

Summary

detect() (graphify/detect.py) accumulates every nested .gitignore/.graphifyignore it discovers during
the os.walk traversal into two flat lists, ignore_patterns and explicit_ignore_patterns:

if dp != root:
    ignore_patterns.extend(_load_dir_own_ignore(dp, gitignore=gitignore))
    explicit_ignore_patterns.extend(_load_dir_own_ignore(dp, gitignore=False))

These lists are appended to on every directory the walk visits and never truncated when the walk
backtracks out of a subtree. Correctness is preserved by an anchor mechanism (_is_ignored/_eval check
target.relative_to(anchor) and skip a pattern that doesn't apply to the current path), but performance is
not: by the time the walk reaches the Nth of many independent subprojects in a monorepo, every single
candidate file/directory check scans the entire pattern set accumulated from every subtree visited so far
— not just the O(depth) patterns that are actually its own ancestors.

This is separate from #1873 ("scope nested ignore patterns to their own subtree"), which is already applied
and fixes a correctness bug (a nested .gitignore incorrectly matching a sibling directory). This issue
is purely about performance: the same anchor-based correctness holds regardless of how large the pattern
list gets, but the list is allowed to grow unboundedly for the lifetime of one detect() call.

Scale where this bites

A monorepo containing many independent projects (each with its own language-appropriate .gitignore) is
exactly the pathological shape. The real corpus this was found on has 274 such .gitignore files; the
reproduction below uses a synthetic 300-directory fixture for a clean, self-contained benchmark. Either
way, the pattern list can reach several thousand entries by the later portion of the walk, and every one of
those entries pays a Path.relative_to() call per candidate file — not filtered out until after the
(non-trivial) relative_to call already ran.

Reproduction (installed graphifyy 0.9.45)

import time
from pathlib import Path
from graphify.detect import detect

# 300 sibling directories, each with its own small .gitignore (10 patterns)
# excluding its own build/ dir -- structurally identical to a monorepo of
# independent per-language projects, just without any other file content.
root = Path("/tmp/many-siblings")
for i in range(300):
    proj = root / f"project_{i}"
    (proj / "build").mkdir(parents=True)
    (proj / "build" / "output.bin").write_text("x")
    (proj / "src.py").write_text("x = 1")
    (proj / ".gitignore").write_text(
        "build/\n*.log\n*.tmp\ndist/\ncoverage/\n.cache/\nnode_modules/\n__pycache__/\n*.pyc\n.env\n"
    )

t0 = time.perf_counter()
detect(root)
print(time.perf_counter() - t0)

On the reporter's machine: 201.4 seconds for 300 directories × 10 patterns each on unpatched 0.9.45,
versus 0.515 seconds for the identical fixture with the pattern list correctly scoped to the live
ancestor chain (see fix below) — a ~391x speedup, measured on a locally-patched fork, not upstream.

On a real 22k-file / 274-.gitignore corpus, detect() alone (before any AST or semantic extraction even
starts) ran for 67+ minutes without completing (interrupted at that point, not left to find a natural
end), confirmed via live stack sampling (py-spy dump, taken several times over that hour) to be
continuously CPU-bound the entire time inside this exact call chain (detect → _ignored_for_scan → _is_scan_ignored → _is_ignored → _eval → Path.relative_to), not blocked/stuck — genuinely doing (unnecessary)
work.

Root cause

ignore_patterns/explicit_ignore_patterns are plain lists mutated by .extend() on every directory the
walk descends into, with no corresponding removal when the walk backtracks out of that directory's subtree.
Every _is_ignored call (both the per-child-directory pruning check during the walk, and the final per-file
pass after the walk completes) scans the entire current list, correctness-filtering each pattern via its
stored anchor. Cost per check is O(total patterns discovered anywhere in the tree so far), when it should be
O(patterns actually anchored along the candidate's own ancestor chain) — bounded by path depth, not by
monorepo breadth.

Suggested fix

Scope pattern storage to mirror the walk's actual recursion (standard DFS push/pop discipline), so a
directory's own patterns are only "active" while the walk is inside that directory's subtree:

• Track, per currently-open ancestor directory, how many pattern rows it contributed (a small stack indexed
  by depth).
• When os.walk moves to a new directory, compute its depth relative to root and pop stack entries (and the
  corresponding trailing rows off the pattern lists) down to that depth minus one, before pushing the new
  directory's own rows. This is sound because a pre-order (topdown=True) walk can only decrease in depth by
  backtracking through the directories it's leaving — it never jumps sideways into an unrelated directory
  without passing back through their common ancestor first.
• The directory-pruning check during the walk (deciding whether to descend into a child) can use this live,
  correctly-bounded stack directly.
• The separate per-file pass that runs after the walk completes (checking individual files against their
  own directory's rules, since a file-level pattern like *.log doesn't get caught by directory-level
  pruning) needs each file's own ancestor-chain patterns reconstructed after the fact, since the live stack
  has moved on by then — cache each directory's own (unaccumulated) patterns once as they're discovered
  during the walk, then reconstruct any single directory's full root-to-leaf chain in O(depth) by walking up
  through parents, memoized per directory so files sharing a parent (the common case) only pay the ancestor
  walk once.

None of this requires changing _is_ignored/_eval's matching logic — they already treat whatever pattern
list they're handed as an opaque, correctness-filtered set. The fix is entirely in how detect() maintains
and feeds them that list.

Verification

A locally-patched fork applying the above:

• Passes the full existing nested-.gitignore test suite unchanged (tests/test_detect.py, including
  test_nested_gitignore_does_not_govern_sibling_project and the other nested/nested-negation tests) — the
  fix does not touch matching semantics, only what's kept in memory and for how long.
• New test (test_detect_nested_gitignore_many_sibling_projects_stays_scoped): 40 sibling projects each with
  their own .gitignore, confirms cross-sibling isolation still holds with the scoped stack.
• New unit tests directly on the extracted pop-logic function, covering: descending a level (no pop),
  backtracking to a sibling (pops exactly the previous directory, keeps nothing extra), backtracking past a
  shared ancestor (keeps the ancestor's rows, drops only the deeper ones), and a 500-iteration simulation of
  the pathological "many siblings" shape asserting the active list never exceeds one directory's own
  contribution.
• Reproduction fixture above: 300 sibling directories × 10 patterns, patched code completes in ~0.5s.

[stephanGarland]

See my comment in #1958 for more about why this is so slow.

[sub4biz]

Thanks for the pointer -- read through your #1958 writeup in full.

Good news: the first bottleneck you describe (ignore_patterns as an
unbounded flat list, _is_ignored() scanning all of it per path) is exactly
what #2834 fixes, and independently -- we arrived at the same "only resolve
anchors against the target's own ancestor chain" approach before seeing your
comment. Nice convergence.

The second one you found -- _matches() inside _match_anchored_ignore_pattern()
being redefined (and its lru_cache recreated and discarded) on every single
call, plus the reference-cycle GC pressure from a recursive closure wrapped
in lru_cache -- we hadn't caught that one. It's a real, separate bug (same
file, same "recompute what should persist" class of mistake, just a
different function) and your fix shape (module-level cache instead of a
per-call closure, dict instead of lru_cache, skip recursion entirely when
the pattern has no **) looks like the right approach on a read-through.

Question before we duplicate effort: do you have a PR up for that fix
anywhere, or is the comment the extent of it so far? If there's no PR yet,
we're planning to implement and verify it (own test corpus + before/after
timing, same rigor as #2834) and would credit your analysis explicitly in
the PR description either way.

[stephanGarland]

I don't have a PR, but can create one tonight.

EDIT: PR link.