T-UY5H-intersect-segment-core-engine

Status: closed/done · Impact: high · Complexity: large

Goal

Implement the pure segment-core engine — intersects, matches, and witness over SegmentPattern — via per-segment glob automata, a synchronized product across segment sequences (handling globstar), and reachability. This is the mathematical heart every other layer builds on.

Today

The segment-core surface and its fixtures exist as stubs from T-FGMJ.

Location	Role today
plugin/lib/intersect/segments/index.ts	L0 public surface — throwing stubs.
plugin/lib/intersect/fixtures/segments.cases.json	Segment-core spec, all pending.
docs/planning/decisions/D-4FRD-intersect-api/layered-api.md	The L0 signatures and semantics.

Proposed

The segment core is fully implemented and its fixtures are active and green. It has zero runtime dependencies, does no string parsing (it consumes SegmentPattern = pre-split segments), and witness returns a concrete common path when one exists.

Approach

1. Per-segment matcher: compile a single glob segment (* = run of non-separator chars, ? = one char, […] classes, {a,b} alternation) into a character-level NFA. Two segment matchers “agree” iff their NFAs share a common string (a character-level product-emptiness check).
2. Segment-sequence NFA per SegmentPattern: a literal segment consumes one input segment (subject to its matcher); ** consumes zero-or-more segments (an epsilon self-loop). Honor globstarMatchesZero.
3. intersects(a, b): run the synchronized product of the two sequence NFAs — advance both on the same input segment only where their matchers agree, ** handled as the zero-or-more skip on either side — and test reachability of a joint accepting state via BFS. Expand product states lazily; do not materialize the full product.
4. witness(a, b): record predecessors during the BFS; on reaching an accepting product state, reconstruct one concrete segment sequence (a concrete string per segment matcher). Return null when unreachable.
5. matches(path, pattern): the degenerate case where path is a literal SegmentPattern — reuse intersects.
6. Apply Options (caseInsensitive, dot) at the character-matcher level; a leading-dot segment is excluded from */** unless dot is set.
7. Flip segments.cases.json (and the segment-level cases in options.cases.json) to pending: false.

Files to touch

Location	Kind	Change
plugin/lib/intersect/segments/automaton.ts	new	Per-segment and sequence NFA construction.
plugin/lib/intersect/segments/product.ts	new	Synchronized product, reachability, witness reconstruction.
plugin/lib/intersect/segments/index.ts	modify	Replace stubs with real intersects/matches/witness.
plugin/lib/intersect/fixtures/segments.cases.json	modify	Flip cases to active.
plugin/lib/intersect/fixtures/options.cases.json	modify	Activate the segment-level option cases (case / dot / globstar-zero).

Acceptance criteria

• AC-1: All segments.cases.json cases pass; bun test plugin/lib/intersect is green.
• AC-2: intersects(["src","**","*.vue"], ["src","siteA","c","x.vue"]) is true; intersects(["a","b"], ["a","c"]) is false.
• AC-3: For every fixture whose expect is true, witness(a,b) returns a segment path that matches both a and b; for disjoint inputs it returns null.
• AC-4: segments/ imports nothing outside the standard library and bunx tsc --noEmit passes.

Out of scope

• Path-string parsing and string | string[] set-awareness — T-IRYT.
• The registry and the fs layer — T-C4Q0, T-ZAZO.
• Pattern-level negation (!pat) and intersection(a,b) — deferred per D-4FRD-intersect-api.

Dependencies

• Requires the skeleton, stubs, and fixtures from T-FGMJ.

Discovery context

• The D-4FRD-intersect-api layered-api.md L0 section; the automata-product approach is grounded in intersect-research.

Depends on

T-FGMJ

---

← Back to Tasks