mirror of
https://github.com/abhigyanpatwari/GitNexus.git
synced 2026-09-07 08:26:11 +00:00
9ad1984b17
* fix: resolve C/C++ cross-file calls through transitive #include chains In C/C++, #include is transitive: if a.c includes b.h and b.h includes c.h, then a.c can call any function declared in c.h. The wildcard import synthesis only walked direct imports (1 hop), missing symbols reachable through transitive header chains. This is the dominant pattern in large C codebases — Redis's db.c includes server.h which includes dict.h, so db.c should resolve calls to dictFind() declared in dict.h and defined in dict.c. Before this fix, those cross-file call edges were missing entirely. The fix expands the import closure transitively for C/C++ files before synthesizing wildcard bindings. A BFS walks ctx.importMap and graphImports to collect all transitively reachable headers, then passes the full closure to synthesizeForFile. Tested on Redis (github.com/redis/redis): - Before: dictFetchValue had 0 cross-file callers, processCommand had 0 - After: dictFetchValue has 9 callers, processCommand has 1, +1946 edges total Fixes #813 * refactor(ingestion): dispatch wildcard synthesis by import-semantics strategy Generalize PR #816's C/C++ transitive #include fix into a language-agnostic strategy pattern. The `wildcard-synthesis.ts` pipeline phase no longer references `SupportedLanguages.C` / `SupportedLanguages.CPlusPlus` — it dispatches on `provider.importSemantics` via an exhaustive `switch`. Also fixes a correctness bug the original BFS introduced: `queue.pop()` (LIFO/DFS) reversed the iteration order of `#include` directives, which — combined with first-seen-wins dedup in `synthesizeForFile` — silently bound overloaded symbols to the wrong header. For the `cpp-calls` fixture, `write_audit("hello")` was being resolved to `zero.h`'s arity-0 overload instead of `one.h`'s arity-1 overload, breaking arity narrowing. Switched to FIFO (`queue.shift()`) with direct imports seeded in declaration order. Taxonomy (researched across 20+ languages + stack-graphs / SCIP prior art): | Tag | Traversal | Languages | |---------------------|-----------------|------------------------------------| | named | none | TS, JS, Java, C#, Rust, PHP, Kotlin| | wildcard-transitive | BFS closure | C, C++ | | wildcard-leaf | single hop | Go, Ruby, Swift, Dart | | namespace | none at import | Python | | explicit-reexport | topological DAG | (scaffold; TS `export *` future) | Changes: - Widen `ImportSemantics` union from 3 to 5 tags with full taxonomy JSDoc - Retag 5 providers: c-cpp (x2) → wildcard-transitive; dart, go, ruby, swift → wildcard-leaf - Move BFS closure into `wildcard-synthesis.ts` as `expandTransitiveIncludeClosure` (pipeline-owned; providers stay pure declarations) - Replace `if (lang === C || CPP)` with `dispatchSynthesis` helper called by both Loop 1 (ctx.importMap) and Loop 2 (graphImports) so a future transitive language whose edges arrive via graphImports gets closure expansion consistently - `never`-assertion default arm forces compile-time exhaustiveness - `explicit-reexport` arm falls through to leaf behavior (scaffold; TODO: implement re-export DAG walk for TS `export *` / Rust `pub use`) - New unit tests covering circular includes, deep chains, diamond dedup, graphImports-only paths, and order-preservation (the regression fix) Verification: - All existing C/C++ transitive tests pass unchanged - Previously failing `cpp.test.ts > resolves run → write_audit to one.h via arity narrowing` now passes - `tsc --noEmit` clean - 225/225 tests pass across wildcard-synthesis, cross-file-binding, cpp resolver, and new closure unit tests * fix(ingestion): bound closure size, O(1) dequeue, track Strategy 4 (#816 review) Address @xkonjin's review feedback on the import-resolution strategy refactor: 1. **DoS guard**: cap transitive closures at 5,000 files via `MAX_TRANSITIVE_CLOSURE_SIZE`. Pathological codebases (boost-style headers, monoheader kernels) could previously produce closures with tens of thousands of entries per translation unit. BFS now stops early and returns a partial closure rather than risking OOM. The closest-headers-first BFS ordering means the partial closure still contains the files overload resolution cares about. 2. **Perf**: replace `Array.prototype.shift()` (O(n)) with a head-index queue (O(1) dequeue). Deep chains previously had quadratic BFS behavior; now linear in closure size. 3. **Strategy 4 tracking**: change TODO in `dispatchSynthesis` to `TODO(#821)` referencing the filed issue for TS `export *` / Rust `pub use` DAG-walk implementation, and clarify that today's leaf fallthrough preserves correctness for direct imports — only the extra re-export traversal is missing. 4. **Test**: new unit test exercising the 5,000-file cap on a 10k-file synthetic chain, verifying partial-closure invariants (starts from importer side, bounded, deep nodes excluded). Not addressed in this commit (followups): - Review point 3 (graphImports-only deep-chain *integration* fixture): unit tests already exercise the `graphImports` traversal path directly in isolation and combined with `importMap`. A fixture that stresses graphImports-only transitive resolution is valuable but requires understanding when the pipeline populates graphImports distinctly from ctx.importMap — tracking as a followup rather than blocking this PR. --------- Co-authored-by: Gergo Magyar <gergomagyar@icloud.com>
101 lines
4.4 KiB
TypeScript
101 lines
4.4 KiB
TypeScript
/**
|
|
* Unit tests for `expandTransitiveIncludeClosure` — the C/C++ Strategy 1
|
|
* (`wildcard-transitive`) implementation extracted from `wildcard-synthesis.ts`.
|
|
*
|
|
* These tests exercise the BFS/DFS closure algorithm in isolation, without
|
|
* running the full pipeline. They cover edge cases flagged in PR #816 review:
|
|
* circular header includes, deep chains, and graphImports-only transitive paths.
|
|
*/
|
|
|
|
import { describe, it, expect } from 'vitest';
|
|
import { expandTransitiveIncludeClosure } from '../../src/core/ingestion/pipeline-phases/wildcard-synthesis.js';
|
|
|
|
const EMPTY = new Map<string, ReadonlySet<string>>();
|
|
|
|
describe('expandTransitiveIncludeClosure', () => {
|
|
it('returns the direct imports when none are chained', () => {
|
|
const direct = new Set(['a.h', 'b.h']);
|
|
const closure = expandTransitiveIncludeClosure(direct, EMPTY, EMPTY);
|
|
expect([...closure].sort()).toEqual(['a.h', 'b.h']);
|
|
});
|
|
|
|
it('expands a two-hop chain via importMap (a.c → b.h → c.h)', () => {
|
|
const importMap = new Map<string, ReadonlySet<string>>([['b.h', new Set(['c.h'])]]);
|
|
const closure = expandTransitiveIncludeClosure(new Set(['b.h']), importMap, EMPTY);
|
|
expect([...closure].sort()).toEqual(['b.h', 'c.h']);
|
|
});
|
|
|
|
it('expands a deep 5-level chain (A → B → C → D → E)', () => {
|
|
const importMap = new Map<string, ReadonlySet<string>>([
|
|
['B.h', new Set(['C.h'])],
|
|
['C.h', new Set(['D.h'])],
|
|
['D.h', new Set(['E.h'])],
|
|
]);
|
|
const closure = expandTransitiveIncludeClosure(new Set(['B.h']), importMap, EMPTY);
|
|
expect([...closure].sort()).toEqual(['B.h', 'C.h', 'D.h', 'E.h']);
|
|
});
|
|
|
|
it('terminates on circular header includes (A.h ↔ B.h)', () => {
|
|
const importMap = new Map<string, ReadonlySet<string>>([
|
|
['A.h', new Set(['B.h'])],
|
|
['B.h', new Set(['A.h'])],
|
|
]);
|
|
const closure = expandTransitiveIncludeClosure(new Set(['A.h']), importMap, EMPTY);
|
|
expect([...closure].sort()).toEqual(['A.h', 'B.h']);
|
|
});
|
|
|
|
it('terminates on self-referential include (A.h includes A.h)', () => {
|
|
const importMap = new Map<string, ReadonlySet<string>>([['A.h', new Set(['A.h'])]]);
|
|
const closure = expandTransitiveIncludeClosure(new Set(['A.h']), importMap, EMPTY);
|
|
expect([...closure]).toEqual(['A.h']);
|
|
});
|
|
|
|
it('expands through graphImports edges when importMap is empty', () => {
|
|
const graphImports = new Map<string, ReadonlySet<string>>([['b.h', new Set(['c.h'])]]);
|
|
const closure = expandTransitiveIncludeClosure(new Set(['b.h']), EMPTY, graphImports);
|
|
expect([...closure].sort()).toEqual(['b.h', 'c.h']);
|
|
});
|
|
|
|
it('combines importMap and graphImports in one traversal', () => {
|
|
const importMap = new Map<string, ReadonlySet<string>>([['b.h', new Set(['c.h'])]]);
|
|
const graphImports = new Map<string, ReadonlySet<string>>([['c.h', new Set(['d.h'])]]);
|
|
const closure = expandTransitiveIncludeClosure(new Set(['b.h']), importMap, graphImports);
|
|
expect([...closure].sort()).toEqual(['b.h', 'c.h', 'd.h']);
|
|
});
|
|
|
|
it('returns an empty set when given no direct imports', () => {
|
|
const closure = expandTransitiveIncludeClosure(new Set<string>(), EMPTY, EMPTY);
|
|
expect(closure.size).toBe(0);
|
|
});
|
|
|
|
it('caps closure size to prevent OOM on pathological codebases', () => {
|
|
// Build a synthetic include graph of 10,000 files, each including the next.
|
|
// The cap (5000) should halt BFS early with a partial but bounded closure.
|
|
const importMap = new Map<string, ReadonlySet<string>>();
|
|
for (let i = 0; i < 10_000; i++) {
|
|
importMap.set(`h${i}.h`, new Set([`h${i + 1}.h`]));
|
|
}
|
|
const closure = expandTransitiveIncludeClosure(new Set(['h0.h']), importMap, EMPTY);
|
|
expect(closure.size).toBe(5000);
|
|
// Partial closure still starts from the importer's side (BFS ordering).
|
|
expect(closure.has('h0.h')).toBe(true);
|
|
expect(closure.has('h1.h')).toBe(true);
|
|
expect(closure.has('h9999.h')).toBe(false);
|
|
});
|
|
|
|
it('deduplicates when a file is reachable through multiple paths (diamond)', () => {
|
|
// A
|
|
// / \
|
|
// B C
|
|
// \ /
|
|
// D
|
|
const importMap = new Map<string, ReadonlySet<string>>([
|
|
['A.h', new Set(['B.h', 'C.h'])],
|
|
['B.h', new Set(['D.h'])],
|
|
['C.h', new Set(['D.h'])],
|
|
]);
|
|
const closure = expandTransitiveIncludeClosure(new Set(['A.h']), importMap, EMPTY);
|
|
expect([...closure].sort()).toEqual(['A.h', 'B.h', 'C.h', 'D.h']);
|
|
expect(closure.size).toBe(4); // D.h appears once
|
|
});
|
|
});
|