4 commits

Author	SHA1	Message	Date
Gergő Magyar	d540b00184	fix(check): stop reporting erased and deferred imports as initialization cycles (#2934)	2026-08-12 17:09:32 +00:00
Carter LaSalle	81100e2c74	fix(python): resolve calls through __init__.py re-exports (#2864) ... * fix(python): resolve calls through `__init__.py` re-exports A call to a name imported from a package never resolved when the package's `__init__.py` re-exported it rather than defining it: pkg/impl.py def target_fn(x): ... pkg/__init__.py from pkg.impl import target_fn caller.py from pkg import target_fn def calls_it(): return target_fn(21) # no CALLS edge `caller.py` gets no CALLS edge. Both IMPORTS hops are recorded, and all four functions are extracted as nodes — only the call binding is missing. Because `__init__.py` re-exports are how Python packages declare a public surface, this misses a large fraction of real call edges, and the failure is silent: the defining file looks like dead code with zero callers. The re-export closure that should carry this already exists and is fully general (`buildReexportClosures` — SCC over the re-export subgraph, bounded fixpoint for cycles, transitive `via` chains). Python just never fed it: the subgraph admits only `kind: 'reexport'` and `kind: 'wildcard'`, and Python emits neither for `from m import x`. Python has no dedicated re-export form. A module-level `from pkg.impl import X` binds X locally AND publishes it as `pkg.X`, so it is both a named import and a re-export. Emitting `kind: 'reexport'` would be wrong — that form drops the local binding, which Python's does create. Instead add an optional `reexportsName` flag to the `named`/`alias` variants, alongside the existing provider-specific `importedSymbolKind` / `targetIncludesImportedName` flags, and admit flagged imports into the closure subgraph. Languages with an explicit form keep emitting `kind: 'reexport'` and leave the flag unset, so nothing changes for them — a negative-control test asserts a plain named import still does not resolve. Verified on a fixture covering the three shapes (direct, top-level-via-re-export, function-local-via-re-export): 1 of 3 CALLS edges resolved before, 3 of 3 after. On a 12.4k-file Python/Go/TypeScript repository: edges 294,416 -> 301,443 (+7,027) and execution flows 300 -> 813. A previously "100% orphaned" module (`shared/db/event_writer.py`) now correctly reports its caller. 5 new finalize tests (single hop, 3-hop chain, alias keying, cycle termination, and the negative control) plus 6 updated Python fixture shapes. `npx tsc --noEmit` clean in both packages; full unit suite shows no regression against baseline (remaining failures are pre-existing load-sensitive flakes in analyzer-identity / evidence-provenance-helper / skip-git-cli / hooks, each verified passing in isolation). * fix(python): set reexportsName only for module-level imports `interpretPythonImport` flagged every `from m import x` as republishing the name, but only a module-level statement does. A `from m import X` inside a `def` or `class` body binds locally and puts nothing in the module namespace, so flagging it fabricates a re-export of a name no importer can reach: # pkg/__init__.py def loader(): from pkg.impl import InternalHelper # caller.py from pkg import InternalHelper # CPython: ImportError resolved to `def:pkg.impl.InternalHelper`. Worse, with declaration-order first-wins in the closure, a scope-blind entry could claim a name ahead of the real module-level import and give a WRONG def for legal, running code. `interpretImport` receives a `CaptureMatch`, which is `{name, range, text}` with no syntax node, so the scope is not recoverable there — and it is not recoverable downstream either: `pass3CollectImports` applies no scope filter and `ImportEdgeDraft.fromScope` is hardcoded to the module scope. The decision therefore moves up to `import-decomposer.ts`, which still holds the live `import_from_statement` node, and rides down as an `@import.publishes` marker. Computed once per statement, not once per imported name, with the existing `findAncestorBeforeBoundary` helper. Only `function_definition` and `class_definition` suppress publication. `if` / `try` / `for` / `with` do NOT — Python has no block scope — so the predicate is an ancestor walk for those two node types and nothing else. Verified against CPython 3.11 in both directions; both are now pinned by tests, including the counterpart control that a branch-nested import still republishes. Also corrects the docblock in `scope-extractor.ts` that sent this change the wrong way. It claims pass 3 attaches imports "not to any `Scope` — finalize reconstructs the owning scope via `provider.importOwningScope` during Phase 2". Finalize does no such thing: `importOwningScope` is declared on `LanguageProvider` and implemented by a dozen providers, and `grep -rnE "\.importOwningScope\b" gitnexus/src/` returns exactly one hit — that doc comment. Nothing invokes it. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01Rzsb6mdGtbu66BG1EaF6Zz * fix(shared): stop guessing ambiguous and namespace re-exports; bound the via chain Four changes to the re-export closure, all reachable only now that Python feeds it. 1. AMBIGUOUS NAMES ARE DROPPED, NOT GUESSED. `populateFileClosure` documented "declaration order first-wins for duplicates of the same exported name", which is sound only where a duplicate export is illegal — two `export { X } from …` is a TypeScript compile error, so the rule never fires. Python has no such guarantee: from .v1 import Client # legacy, left behind from .v2 import Client # the actual public Client CPython binds v2 (verified on 3.11); first-wins attributed every `from pkg import Client` in the repo to the DEAD implementation, and `impact("Client")` pointed at the wrong file. Last-wins is not the fix either: for the equally common `try:`/`except ImportError:` and `if sys.version_info` pairs exactly one branch runs, and which one is not decidable here. Both directions are wrong on real code, so the entry is dropped — the importer stays unresolved, which is exactly the pre-#2864 answer, and the file-level IMPORTS edge is untouched. `collectAmbiguousReexports` runs as a PRE-PASS over data phase 0 froze, so the poisoned set is constant across the fixpoint. That matters: a set that grew mid-fixpoint would need retraction to propagate to files that already inherited the name, would make `myClosure.size > before` an unsound progress signal, and would invalidate the `|SCC| + 1` cap. As a pre-pass the closure map stays monotone and every existing termination argument survives unchanged. Only two flagged drafts resolving to two DIFFERENT in-workspace files count; duplicates of one target are harmless, and unresolvable targets never entered the closure. Checked in both loops. Named re-exports take precedence over wildcards, so suppressing only the named loop would hand the name to a later `import *` and reinstate an arbitrary winner through the back door. 2. NAMESPACE-RECLASSIFIED DRAFTS ARE EXCLUDED. The admission guards tested `draft.source.kind` while `tryFinalize` tests the post-reclassification `draft.base.kind`. Python's `from . import logger` is emitted as `named`, reclassified to `namespace` by `isNamespaceImport`, and was still admitted — republishing whatever def shared the module's simple name. For a `logger.py` holding a module-level `logger = logging.getLogger(...)`, importers of `from pkg import logger` bound to that Variable instead of the module. Reproduced end to end. Both predicates now take the draft and test `base.kind`; this is a no-op for TS/Rust, whose only `isNamespaceImport` implementation is Python's. 3. `transitiveVia` IS CAPPED AT 32. Each hop copies the inherited path, so an unbounded chain is Theta(depth^2) in time AND retained memory, and Theta(|SCC|^2) for a cycle whose chain tracks it. `MAX_REEXPORT_DEPTH = 100` covered this until fc919ad6 removed it — correct for the shallow TypeScript barrels that were then the only input, and invisible until the input class changed. Measured at depth 400: 67 ms / 145 MB uncapped vs 25 ms / 40 MB capped. 32 against a real-world worst case of ~6 for `__init__.py` chains. Safe because `ImportEdge.transitiveVia` has no production reader — it is diagnostic provenance, emitted and typed but dropped by graph emission. 4. `localDefs` ARE INDEXED BY SIMPLE NAME. `findExportByName` linearly scanned a target's defs on every call, and the phase-3 fixpoint rescans the same target once per iteration. Memoized on the array identity, which `FinalizeFile` documents as static input. Worth 12-14% where lookups repeat and neutral elsewhere. The 46-line algorithm docblock was also ORPHANED by the helpers inserted between it and `buildReexportClosures` — AST-verified, that function had zero jsdoc blocks, so the cross-reference elsewhere in the file landed on an undocumented function. Helpers move below it (declarations hoist), and its step 1, precedence and complexity sections are rewritten: they still claimed regular imports do not contribute to the export surface, and justified the via-copy cost by TypeScript barrels being shallow. The `reexportsName` contract consolidates onto `ParsedImport`, where its "`kind: 'reexport'` would drop the local binding" rationale is corrected — `materializeBindings` creates a module-scope binding for every linked edge, re-export included. The real reasons are that `origin` flips, changing evidence weight and priority, and that it misreports Python's syntax. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01Rzsb6mdGtbu66BG1EaF6Zz * test(shared): add a re-export closure scaling guard to CI No bench covered `buildReexportClosures` at all. Until #2864 its input was TypeScript barrel files — a handful of shallow edges — and it admitted only `reexport` and `wildcard` drafts. It now admits every module-level Python `from m import x`, measured ~20x more edges on the CPython stdlib and cyclic SCCs where there were none. The pass went from "rarely runs" to "runs over the whole named import graph" with nothing watching it. The regression this guards has already happened once: fc919ad6 removed `MAX_REEXPORT_DEPTH`, which was correct for shallow barrels and stayed invisible for as long as the input stayed shallow. The depth arm is an EXACT structural assertion — build a chain far past the cap, assert the longest emitted `transitiveVia` is exactly `MAX_VIA_LENGTH`. It started as a `depth_ratio` timing arm and that was a bad gate: sampled five times capped it scored 2.71-3.52 and three times uncapped 5.87-7.65, so the ranges nearly touch and one uncapped run came in UNDER budget. A gate that passes a third of the time on a broken build is worse than none, because it gets read as evidence. The structural form fails 3/3 with 401 vs 32. `width_ms` stays a timing arm with a deliberately loose budget, because a structural check cannot see a constant factor: restoring a per-lookup linear scan of `localDefs` leaves every array length untouched while making every real analyze slower. Both arms drive `finalize` through INDEXED hooks. Reusing the unit tests' `defaultHooks` is the trap — its `resolveImportTarget` does `files.some(...)` per import, which is O(imports x files) in the FIXTURE and swamps the pass so completely that removing the cap measures as no change at all. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01Rzsb6mdGtbu66BG1EaF6Zz * fix(cache): bump SCHEMA_BUMP 53 -> 60 for ParsedImport.reexportsName `reexportsName` is a new field on `ParsedImport`, and `parsedfile-store.ts` serializes the whole `ParsedFile` generically — so it is part of the cached shape even though it is not a capture, which is the easy-to-miss variant of the rule `parse-cache.ts` states as a MUST. (The `@import.publishes` marker added alongside it moves the capture output too, so this qualifies twice; the python captures golden confirms the drift.) Without the bump, a warm `parsedfile-cache` replays pre-fix `ParsedImport`s carrying no flag, `isNamedReexport`'s strict `=== true` takes the old path, and the entire fix is a SILENT NO-OP on incremental analyze while every cold-run test passes. It lands hardest on `__init__.py` — the rarest-changing, highest-cache-hit files in a Python repo, i.e. exactly the target. A published npm release invalidates via `GITNEXUS_PKG_VERSION`; dev trees, main-HEAD installs and CI with a restored cache dir do not. 60, not 54, because the value has to clear every in-flight claim rather than just origin/main: main is at 53 while open PR #2899 claims 54 and #2891 claims 59. Five exact clashes are recorded in the ledger, and the pin test cannot detect a tie — both sides assert the same number and both pass. RE-CHECK against origin/main immediately before merging. Also documents the divergence between `pythonFileExportsName` and the re-export closure. That predicate answers "does this package expose X?" from `localDefs` alone, so with `pkg/__init__.py: from .impl import log`, `pkg/impl.py: def log` and a same-named `pkg/log.py`, `from pkg import log` still targets the submodule and the closure is never consulted — for exactly the case it was built for. Deliberately NOT fixed by reusing the flag, which is the obvious three-line change and is WRONG: `reexportsName` is also set for `from . import log`, where CPython binds `pkg.log` to the MODULE, not a name (verified on 3.11 against the `from .impl import log` form, which binds the function). Returning true there would kill the correct namespace edge. Separating the two needs the re-export's own resolved target — i.e. re-entering `resolvePythonImportTarget` from a different `fromFile` — and that classification is the subject of open issue #2882, so it belongs with that fix. Not a regression: both halves behave exactly as they did before #2864. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01Rzsb6mdGtbu66BG1EaF6Zz * test(python): re-baseline the scope-capture fingerprint for @import.publishes CI's `bench/python-scope/measure.mjs --check` failed on capture fingerprint drift. Intentional: the module-level marker added for `reexportsName` is a new synthetic capture, and that guard hashes `tag|text|range` over every `emitPythonScopeCaptures` output. Attributed before re-baselining rather than after. Reverting ONLY the `@import.publishes` emission — nothing else — restores the previous hash a0da3e7c exactly, so the whole drift is that one marker. `capture_groups_fp` is 3246 either way and `scaling_ratio` stays ~1.0, so no capture group appeared or vanished and the pass is still linear. The other nine bench guards were run rather than assumed: scope-capture, callable-value-flow, finalize-reexport, cpp-qualified-ns, kotlin-import-target, receiver-resolution, scope-emission, import-target and cfg all pass. The benchmarks job runs under `-e`, so this failure masked whatever followed it — worth checking the rest before pushing a one-line baseline change. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01Rzsb6mdGtbu66BG1EaF6Zz --------- Co-authored-by: Carter LaSalle <carterlasalle@gmail.com> Co-authored-by: Gergő Magyar <gergomagyar@icloud.com> Co-authored-by: Gergo Magyar <gergomagyar0@gmail.com> Co-authored-by: Claude Opus 5 (1M context) <noreply@anthropic.com>	2026-08-09 12:21:06 +01:00
Gergő Magyar	ab077b4c29	feat(ingestion): TypeScript registry-primary scope resolution (Ring 3) (#1050) ... * feat(ingestion): TypeScript registry-primary scope resolution (Ring 3) - Add TypeScript ScopeResolver stack (query/captures/interpret, import decomposition, hooks, arity, merge, receiver binding) and register in SCOPE_RESOLVERS. - Harden shared compound receiver and receiver-bound CALLS pass for map for-of tuple bindings, dotted typeRef shapes, and callable-alias fallbacks. - Flip TypeScript into MIGRATED_LANGUAGES; refresh AGENTS.md and type-resolution-system.md. - Shared finalize-algorithm updates for cross-file scope parity. - Tests: TS scope-resolution unit suite; legacy call-processor suite forces REGISTRY_PRIMARY_TYPESCRIPT=0; registry-primary flag test opts out TS in override scenario. Made-with: Cursor * fix(ingestion): SCC-ordered cross-file return-type propagation + multi-hop re-export resolution Fix CI failures on PR #1050 (TypeScript registry-primary migration) by making `propagateImportedReturnTypes` deterministic via reverse- topological SCC ordering and updating the multi-hop re-export contract to match `followReexportChain` behavior. Why: the legacy pass mirrored an intermediate ref instead of the terminal type when an importer was processed before its source module had its own typeBindings chain-followed (4-file alias chain regression in `ts-simple` fixture: `models.User -> service.user -> app.user` collapsed to `getUser` instead of `User`). Reverse-topological walk of `indexes.sccs` (leaves first) lets every importer see the source's already-followed terminal type in a single pass. Changes: - `imported-return-types.ts`: rewrite to walk SCCs leaves-first, chain- follow the source module's typeBindings BEFORE mirroring, and chain- follow the importer's typeBindings AFTER mirroring. Cyclic SCCs reach a partial fixpoint (no convergence guarantee, ts-circular only asserts no-throw). - `finalize-algorithm.ts`: docstring update on `FinalizeFile.localDefs` to reflect that `followReexportChain` resolves multi-hop re-exports through barrels even when intermediates do not surface the name - surfacing is now a static optimization, not a correctness requirement. - `contract/scope-resolver.ts` Invariant I3: explicitly document the SCC ordering requirement. - `pipeline/run.ts`: split PROF timer into `finalize` and `propagate` so the pass's cost is observable independently. - `ARCHITECTURE.md` Performance notes: describe SCC-ordered propagation. - `imported-return-types.ts`: expand chain-depth comment (2x effective depth from pre/post follow), add multi-ref break rationale, add `ts-simple` motivating-fixture pointer. Tests: - `finalize-algorithm.test.ts`: add 4 cases (3-hop chain, cyclic re-export visited-set guard, wildcard re-export fall-through, multi-source first-match-wins); fix misleading shared nodeId in the thick variant; rename and update the multi-hop test for the new contract (transitiveVia assertion on the thin variant). - `imported-return-types.test.ts` (NEW): unit tests for the SCC pass pinning topological collapse, local-annotation guard, missing-source skip, and cyclic-SCC no-throw. - `cross-file-binding.test.ts` + `ts-deep-alias-chain` fixture (NEW): 5-file integration regression guard for SCC-ordered propagation through 4 module boundaries. Validation: 865 scope-resolution + cross-file tests pass on Windows; typecheck clean across both packages; only pre-existing Swift overload failures remain (verified on PR base commit, environmental). Made-with: Cursor * fix(ingestion): address PR #1050 review findings — side-effect imports, resolve-cache perf, adapter signature Three independent fixes surfaced by the production-readiness review of the TypeScript registry-primary scope-resolution migration (RFC #909 Ring 3). All three pass under both REGISTRY_PRIMARY_TYPESCRIPT=0 and =1. 1. Side-effect imports were silently dropped (correctness regression). The legacy DAG emitted IMPORTS edges for `import './polyfill'` because its tree-sitter query matches `(import_statement source: (string))` regardless of clause. The new registry-primary path returned `[]` from `splitImportStatement()` for clause-less imports, so no ParsedImport / ImportEdge was ever produced — silent file-level edge loss. Add a generic 'side-effect' variant to `ParsedImport` and `ImportEdge['kind']` in `gitnexus-shared`; finalize resolves the target file and pre-finalizes the edge (no `targetDefId`, no `BindingRef`) so the SCC fixpoint loop skips it. The TypeScript provider now emits + interprets the new kind end-to-end. The variant is intentionally generic so other languages (Rust `use foo as _`, Python module-init) can adopt it. 2. Per-import re-derivation in `resolveImportTarget` (perf regression). The TS adapter built `new Set(allFilePaths)` on every call and let `resolveTsImportTarget` re-derive `allFileList` / `normalizedFileList` and discard the `resolveCache`. For a workspace with N files and M imports that's O(N × M) work per pass. Wrap the adapter in a closure that memoizes all five derived values keyed on the orchestrator's `ReadonlySet` identity; reset only when the set reference changes (start of new pass). New cost: O(N + M). 3. Misleading fake `ParsedImport` in the adapter (architecture). The adapter constructed `{ kind: 'named', localName: '_', importedName: '_', targetRaw }` to call `resolveTsImportTarget`, even though only `targetRaw` and the structural-typed context are read. Extract `resolveTsTarget(targetRaw, ctx)` so the adapter has an honest signature; `resolveTsImportTarget` still works for other callers. Also extract `narrowTsContext` for the type narrowing. Tests: - New 4-file fixture `typescript-side-effect-imports` with two side-effect imports + one named import. - New "TypeScript side-effect imports" describe in `test/integration/resolvers/typescript.test.ts` (parity-gated by `ci-scope-parity.yml` — runs under both flag states). - Updated 2 unit tests to expect 1 side-effect ParsedImport and 4 `@import.statement` matches (was 0 / 3). - 785 / 785 TS scope-resolution tests pass under both REGISTRY_PRIMARY_TYPESCRIPT=0 and =1. Made-with: Cursor * fix(scope): address Codex adversarial review findings on PR #1050 Four findings from the Codex adversarial review broke registry-primary TypeScript resolution for common patterns. All four now have unit and integration regression coverage that pass under both `REGISTRY_PRIMARY_TYPESCRIPT=0` (legacy DAG) and the default registry-primary path. [high] tsconfig path aliases dropped: Threaded `tsconfigPaths` through ScopeResolver via a new opaque `resolutionConfig` parameter and a `loadResolutionConfig(repoPath)` hook. The orchestrator (`scopeResolutionPhase` + `runScopeResolution`) loads it once per workspace pass and forwards into every `resolveImportTarget` call. TypeScript resolver now resolves `@/services/user` style imports through the standard resolver's alias branch. [high] TSX parsed with the wrong grammar: `emitTsScopeCaptures` now picks the parser/query by `filePath` (`.tsx` -> TSX grammar) and validates cached trees against the expected grammar via the new exported `tsCachedTreeMatchesGrammar` helper. Stale TS-grammar trees for `.tsx` files no longer leak through the scope query. [medium] Literal dynamic imports never linked: Added `kind: 'dynamic-resolved'` to `ParsedImport` and `ImportEdge`. The decomposer emits a synthetic `@import.literal` capture for string-literal dynamic imports; the interpreter maps that to `dynamic-resolved`; finalize pre-finalizes it as a file-level terminal (same shape as `side-effect`). `import('./feature')` now produces a real IMPORTS edge under the registry-primary path. Legacy DAG keeps its existing behavior — the new integration assertion is gated behind the flag. [medium] Namespace re-exports invisible from barrels: The decomposer now emits TWO captures for `export * as ns from './m'` — the existing `reexport-namespace` import draft AND a synthetic `@declaration.namespace` capture (via `buildNamespaceDeclarationMatch`). The latter creates a Namespace `SymbolDefinition` in the barrel's `localDefs`, so downstream `import { ns } from './barrel'` resolves through `findExportByName`. Regression fixtures under `gitnexus/test/fixtures/lang-resolution/`: - typescript-tsconfig-aliases (`@/` alias) - typescript-tsx-jsx (Button.tsx + App.tsx with JSX) - typescript-dynamic-import (`await import('./feature')`) - typescript-reexport-namespace (`export * as Models from './base'`) Validation: - gitnexus-shared builds clean - gitnexus typecheck clean - 385/385 TS scope-resolution tests pass under both `REGISTRY_PRIMARY_TYPESCRIPT=0` and default Made-with: Cursor * perf(scope): O(1) defById lookup + bounded re-export depth (PR #1050 round 3) Addresses the round-3 PR #1050 reviews (Claude adversarial + xkonjin): both flagged the existing O(N²) `findDefById` linear scan in `materializeBindings` and the unbounded recursion in `followReexportChain` as production-readiness blockers for TypeScript monorepos. Both fixes land alongside their regression tests under both `REGISTRY_PRIMARY_TYPESCRIPT=0` and the default registry-primary path. [high] materializeBindings O(N_files × N_defs × N_edges) → O(N_defs + N_edges): Build a `nodeId → SymbolDefinition` index map once at the top of `materializeBindings` (one O(N_defs) pass), then replace the per-edge `findDefById(files, edge.targetDefId)` linear scan with an O(1) `defById.get(edge.targetDefId)` lookup. Also drop the now-unused `findDefById` helper. At realistic TypeScript monorepo scale (~5k files × ~50 defs/file × ~100k linked import edges) this is the difference between ~25 s and a few ms inside finalize. Regression test in `finalize-algorithm.test.ts` builds 200 leaf files + 1 consumer importing one symbol from each, asserts every binding materializes correctly. [medium] followReexportChain unbounded recursion: The existing `visited` set caps depth at `O(N_files)` but allows recursion proportional to barrel-chain depth, mismatching the explicit "Iterative DFS to avoid stack overflow" policy in `tarjanSccs`. Added a `MAX_REEXPORT_DEPTH = 100` constant and a `depth` parameter to `followReexportChain` (defaults to 0); each recursive call passes `depth + 1` and the function returns `null` when the cap is exceeded. 100 is comfortably above any realistic hand-authored barrel chain (typical depth 1-5; auto-generated barrels rarely exceed 20) while staying well below JS engine call stack limits. Regression test wires a 200-link reexport chain and verifies the crawl terminates cleanly with `linkStatus: 'unresolved'` (no terminal def reachable within the budget). [low] synthesizeInstanceofNarrowings bare-identifier-only limitation: xkonjin's review #4 noted that the LHS narrowing only handles bare identifiers (`if (x instanceof Foo)`), not member expressions (`if (user.address instanceof Address)`). Added a JSDoc note explaining the constraint and pointing readers at field-type resolution as the workaround for member-chain receivers. Validation: - gitnexus-shared builds clean - gitnexus typecheck clean - 413/413 tests pass under both flag states for finalize-algorithm + TS unit + TS integration suites - 972/972 tests pass across full scope-resolution + Python + C# integration smoke (no cross-language regression) Made-with: Cursor * refactor(finalize): replace recursive followReexportChain with SCC-condensed iterative closure The legacy `followReexportChain` walked re-export drafts via mutual recursion guarded by a per-call visited set + a `MAX_REEXPORT_DEPTH` ceiling. Recursion is fragile (call-stack ceiling, no bound on depth that's actually meaningful), so this replaces it with a structurally better algorithm: a precomputed per-file re-export closure built by running Tarjan SCC over the re-export sub-graph and propagating names in reverse-topological order with a bounded intra-SCC fixpoint. Algorithm (`buildReexportClosures` in finalize-algorithm.ts): 1. Sub-graph: build the directed graph of `reexport` + `wildcard` drafts only (regular/namespace/dynamic imports do not contribute). 2. SCC condensation: run the same iterative `tarjanSccs` already used for the file-level import graph; output is in reverse-topo order so out-of-SCC neighbors are always already-finalized. 3. Per-SCC propagation: - Acyclic singleton: one pass populates from neighbors' closures. - Cyclic SCC: bounded fixpoint capped at |SCC|+1 iterations. With first-wins precedence the closure map is monotone, so each name needs at most |SCC| hops to traverse the cycle. Precedence (preserved from the recursive crawl): - Named re-exports take precedence over wildcards. - Within each kind, declaration order wins. Lookup at finalize time becomes O(1) (`lookupReexportedName`), down from O(chain_depth × drafts) per consult and recursive at that. Properties vs the legacy implementation: - Stack-safe by construction; no `MAX_REEXPORT_DEPTH` guard needed. - 1000-hop barrel chains now resolve in full (legacy capped at 100 and surfaced anything deeper as `unresolved`). - Cycles handled structurally via SCC, not via per-call visited set. - Same observable semantics: every existing test passes unchanged. Tests: - Replace the obsolete `MAX_REEXPORT_DEPTH (200-hop chain stops cleanly without stack overflow)` test (which asserted the OLD bug — that deep chains failed to resolve) with a positive 1000-hop test that asserts full resolution + accurate `transitiveVia`. Proves both the recursion is gone AND the closure correctly inherits the leaf def across all hops. - Update commentary on adjacent re-export tests to reference the closure mechanism. - Update `FinalizeFile.localDefs` JSDoc + import-decomposer.ts inline doc to point at `buildReexportClosures` instead of the removed function name. Validation: - gitnexus-shared builds cleanly. - gitnexus typechecks cleanly. - 28/28 finalize-algorithm.test.ts tests pass (incl. new 1000-hop). - 801/801 TypeScript scope-resolution tests pass under default (registry-primary) AND `REGISTRY_PRIMARY_TYPESCRIPT=0` (legacy DAG). - 404/404 Python + C# integration tests pass — no regression in cross-language consumers of the shared `finalize`. Made-with: Cursor * fix(scope): remove non-null assertions from scope resolution Made-with: Cursor * fix(scope): address TypeScript review follow-ups Made-with: Cursor * fix(scope): address TypeScript import review follow-ups Add regression coverage for non-binding import edges and circular TypeScript bindings so PR #1050 review concerns stay visible without changing runtime semantics. Made-with: Cursor	2026-04-26 08:23:08 +01:00
Gergő Magyar	a9a5e1c388	feat(shared): SCC-aware finalize algorithm with bounded fixpoint (#915, RFC #909 Ring 2 SHARED) (#962) ... * feat(shared): SCC-aware finalize algorithm with bounded fixpoint (#915, RFC #909 Ring 2 SHARED) Implements RFC §3.2 Phase 2 as pure logic in `gitnexus-shared`. Takes per-file parse output and returns linked `ImportEdge[]` + materialized module-scope bindings, fully language-agnostic (target resolution, wildcard expansion, and binding precedence all go through caller hooks). Three-phase algorithm: 1. Tarjan SCC over the file-level import graph (iterative, deterministic node order, O(V+E)). Returns SCCs in reverse-topological order so leaves finalize before dependents — and so disjoint SCCs are explicitly surfaced for parallel-processing callers. 2. Per-SCC bounded fixpoint. For each SCC in topo order, iterate up to `N = |intra-SCC edges|`; each pass tries to resolve every still- unlinked edge by looking up the imported name in the target file's local defs. Stops early when no progress. Edges still unlinked after the cap get `linkStatus: 'unresolved'` — keeps malformed inputs bounded and preserves the RFC §4v2 capped-signal contract for unresolved markers. 3. Wildcard expansion + module-scope binding materialization. For each `wildcard` ParsedImport that linked to a module, expand via `expandsWildcardTo` into one `wildcard-expanded` ImportEdge per exported name. Bindings per module scope are the merge of local defs (`origin: 'local'`), named / alias / reexport imports (`origin: 'import' | 'reexport'`), namespace imports (`origin: 'namespace'`), and wildcard expansions (`origin: 'wildcard'`), with precedence delegated to `provider.mergeBindings`. Dynamic imports rule: `kind: 'dynamic-unresolved'` passes through as an ImportEdge with `targetFile: null` and no BindingRef. Re-export flattening: reexport edges land with `transitiveVia: [targetFile]`. Multi-hop chains settle iteratively across the fixpoint. Types: - Adds `'wildcard'` variant to ParsedImport (parse-time signal for `import * from M`). The finalize-only `'wildcard-expanded'` ImportEdge kind is unchanged and remains finalize output only, as documented. - Exports `finalize` + `FinalizeFile` / `FinalizeInput` / `FinalizeHooks` / `FinalizeOutput` / `FinalizedScc` / `FinalizeStats`. Simple-name derivation: `deriveSimpleName` uses `def.qualifiedName` as the authoritative source (tail after the last `.`). Defs without a qualifiedName are not name-resolvable by this algorithm — an explicit design choice that trades strictness for predictability (no heuristic nodeId parsing). Tests (20, all passing): - Trivial: empty workspace · acyclic resolution · unresolvable target (file + name) · dynamic-unresolved passthrough. - Cycles: A↔B two-file cycle linked · cycles packed into SCC with isCycle=true · disjoint cycles produce disjoint SCCs · mixed linked/unresolved edges reported correctly in stats. - Wildcards: one ImportEdge per exported name · unresolved wildcards survive as single edges · expanded bindings carry origin='wildcard'. - Reexports: transitiveVia carries the intermediate file path. - Aliased + namespace: alias preserves targetExportedName under its local name · namespace links to module scope even without a module-def. - Bindings: locals land as origin='local' · imports layer on via mergeBindings · mergeBindings can drop existing (last-write-wins precedence honored). - SCC-DAG: reverse-topological ordering verified (leaf first). Combined scope-resolution / model / shadow suite: 229/229 pass. `tsc --noEmit` clean in both `gitnexus-shared` and `gitnexus`. Closes part of #909. Unblocks #917 (Registry.lookup's import-chain fast path consumes finalized ImportEdges); unblocks Ring 3 language migrations (per-language providers supply FinalizeHooks implementations). * chore(shared): address #915 review findings — dead code, docs, tests Review thread on PR #962. Code changes: - Remove dead `resolvedTargets` map + `keyFor` + `ParsedImportKey` type alias. The map was populated but never read; originally intended to cache / dedup resolutions for later phases but that path was never wired (finding 1.1). - Drop unused params (`_edgeIndex`, `_hooks`, `_workspace`) from `tryFinalize`. No planned fixpoint-state consultation; no reason to keep them reserved (finding 2.1). Documentation: - `FinalizeFile.localDefs` now documents the multi-hop re-export contract explicitly: `finalize` looks names up in the target's static `localDefs`; if B only re-exports from C and doesn't surface the name in its own localDefs, A's import of that name from B will hit the cap and be marked unresolved. Parsers that want multi-hop chains to settle end-to-end must include re-exported names in the intermediate file's localDefs (finding 1.2). - `FinalizeStats` now documents its counting granularity: all edge counters are per-`ParsedImport`, not per-materialized-`ImportEdge`. A wildcard expanding to N exports counts as one linked edge; dynamic-unresolved pass-throughs count as linked. The bindings map is the authoritative "has a BindingRef" source (finding 3.2). Tests (2 added, 22 total in finalize-algorithm.test.ts, 231/231 combined): - Explicit cap-hit → `linkStatus: 'unresolved'` assertion for a cycle where the name-level lookup never succeeds (distinct from `targetFile: null`; cap exhaustion path) (finding 3.1). - Multi-hop re-export contract test: demonstrates both variants — intermediate B WITHOUT X in localDefs → unresolved; B WITH X in localDefs → resolved to the original source DefId (finding 1.2). Not addressed (filed as follow-up issues): - LanguageProvider.resolveImportTarget vs FinalizeHooks signature divergence (finding 1.3) — pre-Ring-3 concern. - findDefById O(F×D) scan in Phase 5 (finding 4.1) — acceptable for Ring 2; optimize before large-workspace Ring 3 migrations.	2026-04-18 17:26:07 +01:00