Intersect

Status: open/active

Summary

A small library that answers one question about file paths: given path patterns (globs) and/or concrete paths, do two of them overlap — share any common matching path?
Extracted from the SDLC plugin into the workspace package packages/ts/intersect/ (@sksizer/intersect); intended to be published standalone once it stabilizes.
The formal core is regular-language intersection non-emptiness (product-automaton reachability); the value is correct path semantics and a clean pairwise API, not the automata math (intersect-research).

What it is

Intersect is a path-pattern overlap engine. It takes globs and concrete paths and decides overlap: does pattern A share a common match with pattern B (intersects), does a path match any pattern in a set (matches), and which patterns in a set overlap a query (overlapping). It does not touch the filesystem — it reasons over patterns as languages, not over directory contents.

It exists because two SDLC operations need overlap reasoning and the ecosystem has no off-the-shelf answer: mainstream matchers (minimatch, micromatch, picomatch, globset) only match a concrete path against a pattern, never a pattern against a pattern (intersect-research).

Boundary

Intersect is one of the sibling OSS libraries PR-0001-sdlc’s Boundary anticipates — a general-purpose piece extracted from the plugin and shipped standalone. It earns its own Product entity now because real SDLC work motivates it.

Inside this product:

The segment-based pattern core (glob dialect → automaton, product + reachability) and the friendly path-string API that wraps it.
The overlap primitives (intersects / matches / whichMatch / overlapping, and optional witness / intersection).
A pure registry (index) over labeled pattern-sets — “which guideline/standard artifacts apply to this scope” (DR-0014).

Outside it:

Filesystem walking / actual globbing (finding files on disk). Intersect answers pattern algebra; a caller pairs it with a globber when it needs real files.
The SDLC-specific callers — task claims conflict detection and headless-context assembly — consume Intersect; they are not part of it.
Precedence/ordering resolution — picking a winner (last-match-wins, gitignore ! re-inclusion). Intersect computes overlap and returns registry matches in caller-provided order so precedence can be applied, but it does not pick the winner.

It now lives at packages/ts/intersect/ as the @sksizer/intersect workspace package, extracted from the solutions/ontological/lib/_example/ shape it was incubated in.

The core question

Everything reduces to one primitive:

intersects(A, B) — is there any path that both pattern A and pattern B match?

matches (path vs. set) and overlapping (pattern vs. set) are the two call shapes SDLC needs, and both decompose into pairwise intersects.

Formal model

A glob is a regular language over path strings (with / a distinguished symbol: * = [^/]*, ** crosses /, ? = one non-/, {a,b} = alternation). Overlap is decided by the synchronized (tensor) product of the two patterns’ automata plus reachability: A intersects B iff some accepting state of the product is reachable from the start state. The product is walked lazily — never fully materialized.

The user’s “it’s basically a graph intersection” instinct is half-right and worth stating precisely: the computation is a graph reachability search, but over the synchronized product of the two automata (Cartesian product of states, lockstep transitions), not a set-intersection of two graphs. See intersect-research §1.

Complexity is friendly where it matters: the pairwise question (A vs. B) is polynomial, O(|A|·|B|). The simultaneous many-pattern intersection (⋂ Sᵢ ≠ ∅) is PSPACE-complete — so the API stays pairwise / one-vs-set and never asks the intractable question.

Design tenets & non-goals

Correct path semantics over clever math. The automata core is off-the-shelf; the load-bearing work is getting **, braces, anchoring, and dotfiles right for a chosen dialect.
No backtracking regex. Naïve glob→regex expansions of ** cause catastrophic backtracking; build a proper automaton (Thompson / RE2-style simulation) instead (intersect-research §1.5).
Pairwise only. Expose intersects / matches / overlapping; keep simultaneous many-pattern intersection out of the surface.
Non-goals (v1): no filesystem access; no pattern-level negation / gitignore ! re-inclusion (needs language complement — deferred); no precedence resolution.

Drivers & goals

Four Drivers motivate this product:

Driver	Kind	What it wants
DR-0011	use-case	The intersecting file set for a working scope, to feed headless scripts as context.
DR-0012	use-case	Predict edit conflicts by testing whether two work items’ path-claims overlap.
DR-0014	use-case	Resolve which guideline/standard artifacts (labeled pattern-sets) apply to a scope.
DR-0013	opportunity	Fill a real ecosystem gap — no TS library answers “do these two globs intersect?”

Goals attach here once the Product-layer Goal schema ships.

Status

open/active — v0.1 shipped. M-0010 delivered the full library test-first across PRs #551–#556: the segment core, path API, registry, and intersect/fs layer, with a green fixture corpus (zero pending cases) and dependency isolation (. / ./segments pull nothing; only ./fs pulls tinyglobby). The library was then extracted from solutions/ontological/lib/ into the workspace package packages/ts/intersect/ (@sksizer/intersect). Deferred past v1: pattern-level negation (!pat), intersection(a, b), and npm publish.

References

Design: D-4FRD-intersect-api — the API surface and layered architecture (pure core + intersect/fs wrapper), with TypeScript examples.
Research: intersect-research — theory, prior art, existing libraries, and the recommended API.
In-repo prior art: solutions/ontological/lib/model/entities/task/claims/paths.ts (glob-char detection + path relocation for task claims — the first internal consumer of overlap reasoning).
Parent boundary: PR-0001-sdlc Boundary (OSS libraries extracted from the plugin).

← Back to Products