Skip to content
sdlc

Intersect — research

State: open/active · Genre: research

Theory, prior art, and existing libraries behind PR-0002-intersect. The question the product answers: given path patterns (globs) and/or concrete paths, decide overlap — does pattern A share a common matching path with pattern B? Does path P match any pattern in set S? Which patterns in S overlap query Q?

Motivating use cases: DR-0011 assembling file-context sets for headless scripts; DR-0012 predicting edit conflicts between concurrent work items.

1. Theoretical underpinnings

Section titled “1. Theoretical underpinnings”

1.1 It is a known, solved problem

Section titled “1.1 It is a known, solved problem”

“Do two glob patterns share a common match?” is an instance of the intersection non-emptiness problem for regular languages. A glob converts to a regular expression, a regex compiles to a finite automaton, and “do two automata accept a common string?” is the classic DFA/NFA intersection non-emptiness decision. Glob→regex conversion is standard and shipped widely (globrex, glob-to-regexp; Rust globset implements globs by converting them to regexes and running them on the regex crate).

1.2 Mechanism: product (tensor) construction + reachability

Section titled “1.2 Mechanism: product (tensor) construction + reachability”

The Rabin–Scott product construction builds an automaton whose states are tuples (q₁,…,qₖ) — one state per input automaton — that accepts a string iff every input does. Intersection is non-empty iff an accepting state of the product is reachable from the start state. The product need not be materialized: transitions are computed on demand and you run a BFS/DFS over it lazily. Emptiness test: drop states unreachable from the start; if any accepting state survives, the language is non-empty.

1.3 The “graph intersection” hunch, made precise

Section titled “1.3 The “graph intersection” hunch, made precise”

Half-right, worth stating exactly:

ClaimVerdict
The computation is a graph searchTrue — it reduces to reachability (path existence) on the product graph.
The operation is set-intersection of two graphsFalse — it is the tensor / synchronized product: advance both automata in lockstep on the same symbol; a product edge exists only where both components have an edge on the matching label.

The accurate mental model is regular-language intersection non-emptiness = product-automaton construction + reachability. “Graph intersection” is a useful intuition pump but imprecise.

1.4 Complexity — cheap pairwise, expensive in general

Section titled “1.4 Complexity — cheap pairwise, expensive in general”
CaseCost
Pairwise (A vs. B, k=2)`O(
Fixed k automataO(nᵏ) via Rabin–Scott.
Unbounded k (⋂ of many patterns)PSPACE-complete (Kozen, 1977) — intractable in the worst case.

Design consequence: favor pairwise overlap (A×B) and one-vs-set; never formulate the simultaneous many-pattern intersection.

1.5 Gotchas that inflate the automaton (or break the reduction)

Section titled “1.5 Gotchas that inflate the automaton (or break the reduction)”
FeatureIssue
Globstar **Naïve glob→regex ** causes catastrophic backtracking in backtracking engines. Convert to a proper automaton (Thompson / derivatives / RE2-style DFA simulation), never hand ** to a backtracking regex.
Separator /Special: * = [^/]*, ** crosses /, ? = one non-/. The alphabet must treat / distinctly or results are wrong.
Braces {a,b}, ranges {1..9}Alternation / Cartesian product; stay regular but blow up if eagerly expanded. Keep as automaton alternation.
NegationClass-negation [!abc] is easy (regular). Pattern-level negation (gitignore !, extglob !(…)) needs language complement ⇒ DFA determinization ⇒ exponential blowup. Biggest scoping decision.
Character classes :alpha:Regular but widen the alphabet; use symbolic (range-predicate) transitions.

2. Existing libraries — “does this already exist?“

Section titled “2. Existing libraries — “does this already exist?“”

2.1 Dedicated glob-vs-glob intersection

Section titled “2.1 Dedicated glob-vs-glob intersection”

glob-intersection (JS/CoffeeScript) is the directly-on-point library: intersect(a, b) returns a new glob describing the intersection or false. But it is low-maturity, single-author, and deliberately over-permissive (e.g. **cd intersects /abcd even though a real glob would not) — so it reports false-positive overlaps. Good as a reference / test oracle, risky as a dependency.

No mainstream matcher exposes a pattern-vs-pattern primitive. npm (minimatch, micromatch, picomatch, globrex, glob, fast-glob), crates.io (glob, globset, ignore, glob-match), and Go all do path-vs-pattern matching only. This is a genuine gap (DR-0013).

2.2 Automata engines (repurposable substrate)

Section titled “2.2 Automata engines (repurposable substrate)”
LibraryLangFit
greeneryPython (MIT)Purpose-built: regex→FSM, p1 & p2, .empty(). The cleanest existing “common match exists?” engine. Feed it glob→regex output.
Mata, RE#C++/PyHeavier automata toolkits; needed only for performance or complement (negation).
automata-libPython (MIT)General DFA/NFA with product/intersection primitives.
globrex, glob-to-regexpJSGlob→regex converters — a usable front-end for any of the above.

2.3 Summary table

Section titled “2.3 Summary table”
LibraryLangPattern×pattern intersection?MaturityLicense
glob-intersectionJS/CoffeeYes (returns a glob) — over-permissive, false positivesLowunspecified
greeneryPythonYes (&, .empty())Medium-highMIT
automata-libPythonYes (DFA product)MediumMIT
minimatch / micromatch / picomatchJSNo (path×pattern)Very highMIT
glob / fast-globJSNoVery highISC/MIT
globset / ignoreRustNo (glob→regex internally)Very highMIT/Unlicense
globrex / glob-to-regexpJSNo (converter front-end)MediumMIT

3. Prior art in real tools

Section titled “3. Prior art in real tools”

Most production systems solve the easier direction — “which patterns apply to this concrete path?” — and sidestep pattern×pattern overlap with a precedence/ordering rule so overlaps resolve deterministically rather than being computed.

SystemApproach
git .gitignore / pathspec, ripgrep ignorePath vs. ordered pattern list; last match wins, ! re-inclusion. Overlap never computed — resolved by order. Builds a globset (globs → one RegexSet).
CODEOWNERS (GitHub/GitLab)gitignore-style patterns; last matching line wins. Path-vs-set + ordering.
EditorConfig / VS CodePath-vs-glob; later sections override on conflict.
ESLint overrides / flat configA file may match many config objects; merge in order, last wins.
tsconfig include/exclude, Bazel/Buck glob(include, exclude)include ∧ ¬exclude evaluated per concrete file, not as pattern algebra.

Overlap is genuinely computed in only a few places, and usually over materialized paths, not patterns:

  • BuildStream “overlapping files” — detects two elements staging to the same output path; overlap of materialized paths, not globs.
  • MCP Agent Mail (closest analog to DR-0012) — agents reserve glob patterns for a TTL; a pre-commit hook checks whether committed files overlap another agent’s reserved pattern and blocks. Note the dodge: it checks concrete files against patterns (path-vs-pattern), not pattern-vs-pattern, and is advisory/bypassable to avoid deadlock.

Takeaway: the industry norm is (i) reduce to path-vs-pattern against a RegexSet-style combined automaton, and (ii) resolve overlaps by ordering, not computation. True pattern-vs-pattern overlap is rare and, where it appears, is often approximated by enumerating paths.

4. Design takeaways

Section titled “4. Design takeaways”

(a) Formal model to build on

Section titled “(a) Formal model to build on”

Treat each glob as a regular language over path strings (alphabet includes a distinguished /). Answer overlap by product-automaton reachability, not string enumeration: A intersects B iff, in the synchronized product of automata(A) and automata(B), some accepting state is reachable from the start. Build automata with a non-backtracking construction (Thompson NFA, Brzozowski/Antimirov derivatives, or RE2-style DFA simulation) using symbolic transitions (/ special, * = [^/]*, ** = .* across /, braces = alternation). Reachability runs lazily.

(b) Build vs. wrap

Section titled “(b) Build vs. wrap”
  • Do not hand globs to a backtracking regex engine (globstar → catastrophic backtracking).
  • Wrap, don’t reinvent the automata core. The genuinely novel, worth-building piece is the thin, path-semantics-correct layer: a glob dialect + glob→automaton translator + a small intersects / matches / overlapping API. The hard math is off-the-shelf.
  • Avoid depending on glob-intersection (over-permissive); keep it as a test oracle only.
  • TypeScript reality: no drop-in engine exists (greenery is Python). Either port a minimal automata-intersection core to TS or wrap a glob→regex converter + a small TS automaton. This is DR-0013’s niche.

(c) Hard cases any implementation MUST decide explicitly

Section titled “(c) Hard cases any implementation MUST decide explicitly”
  1. ** — cross /? match zero segments (a/**/b ⊇ a/b)? leading/trailing **? (git vs. minimatch differ.) Encode in the automaton.
  2. Braces / ranges — keep as alternation; do not expand to the Cartesian product of strings.
  3. Negation — support only class-negation [!…] (stays regular), or pattern-level negation (needs complement ⇒ DFA). Recommend excluding pattern-level negation from v1.
  4. Case-sensitivity — a parameter (macOS/Windows vs. Linux); affects the alphabet.
  5. Trailing slash / dir-vs-file / anchoring — is src/api == src/api/ == src/api/**? anchored or floating? relative to a base? Most real-world wrong answers come from here, not the automata math.
  6. Dotfiles — does */** match leading-dot segments? Make it a flag.
Section titled “(d) Recommended minimal API”

All primitives reduce to pairwise product + reachability, so all are polynomial:

// Core — does a common matching path exist?
intersects(a, b, opts?) -> bool
  // opts: { globstarCrossesSlash, dotMatch, caseInsensitive, negation: 'class' | 'none' }


// Path membership (a concrete path is a single-string pattern)
matches(path, patterns) -> bool          // does P match any of S?
whichMatch(path, patterns) -> Pattern[]  // which ones


// Set-vs-pattern overlap — the conflict-detection primitive
overlapping(q, patterns) -> Pattern[]    // which patterns in S overlap q


// Optional (strictly harder / larger output)
witness(a, b) -> string | null           // an example common path (the reachability path)
intersection(a, b) -> Pattern | null     // like glob-intersection's return
  • intersects is load-bearing; ship it first. Returning a witness path is cheap and makes conflict reports (DR-0012) explainable.
  • If the caller already has the concrete changed-file list, matches(file, patterns) sidesteps the pattern×pattern question entirely — what a git hook guard should use (the MCP Agent Mail pattern).
  • Keep the simultaneous many-pattern intersection (the PSPACE case) out of the surface.

Sources

Section titled “Sources”

← Back to Notes