GitNexus/gitnexus/test/integration/ruby-import-index-reuse.test.ts
Gergő Magyar 78ecce1b92
perf(import-target): index the workspace once per run for go/csharp/dart/ruby (#2898)
* perf(import-target): index the workspace once per run for go/csharp/dart/ruby

Four import-target resolvers answered their lookups with a full
`allFilePaths` scan per import, making resolution O(imports x files):

- go (#2877): `findRootPackageFiles` / `findAllFilesInPkgDir`, the latter
  once per path segment on the GOPATH fallback. Most Go imports are
  external, so the whole cascade ran to completion before returning null.
- csharp (#2878): the no-csproj leg took the raw Set past the memoized
  index the csproj leg was already using - up to eight passes for a
  four-segment `using`.
- dart (#2879): one scan per candidate path, and for an external package
  both candidates miss, so both always ran to completion.
- ruby (#2880): a complete `buildSuffixIndex` rebuilt and discarded per
  `require` - every require paid to index every file in the repo.

Each now reads an index memoized on the `allFilePaths` Set identity, the
shape `getPythonFileIndex` (#1918) and csharp's own `getWorkspaceFileIndex`
(#1881) already used. Two shared modules back them:

- `workspace-file-index.ts`: normalized list + `SuffixIndex` + a
  normalized->raw map, for csharp and ruby.
- `package-dir-index.ts`: "which files live directly inside a directory
  ending with <path>", for go and csharp. Candidates are bucketed by the
  directory's last segment rather than by indexing every directory suffix,
  which would cost O(files x depth) entries at kernel scale (#2649).

Behaviour is unchanged, including the tie-breaks that are expressed only
through Set-iteration order and `indexOf` positions: the go root leg stays
sorted and its package leg stays unsorted, the first-occurrence rule that
excludes a directory nested inside a same-named directory is preserved,
csharp's whole-path match still beats an earlier suffix match, and dart
still tries `lib/<rel>` fully before bare `<rel>` and matches raw paths.

Verified two ways. `import-target-index-parity.test.ts` keeps verbatim
copies of the pre-change implementations and diffs against them over a
deterministic corpus plus hand-built layouts for each tie-break; six
mutations of the new code were confirmed to fail it. Separately, the bench
corpus produces byte-identical fingerprints against the pre-change
resolvers at both 400 and 1600 files.

`bench/import-target/measure.mjs` gates both arms in CI: per-language
output fingerprints, a scaling budget (measured 0.98-1.12 here, 3.32-4.10
against the pre-change scans), and the corpus shape, so the corpus cannot
be shrunk below the size the scaling arm needs and still print PASS.

Closes #2877
Closes #2878
Closes #2879
Closes #2880

Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01BCptYZWRgnnJ821rzebQyj

* perf(import-target): cover kotlin, and add depth + absolute-cost arms

#2872 landed the same index hoist for Kotlin while this branch was open.
Fold it into the shared measures so all five resolvers are gated on one
corpus, and adopt the two arms that PR's review proved a scaling ratio
alone cannot carry.

- `bench/import-target/measure.mjs` gains a kotlin arm: a Gradle-shaped
  corpus with per-module source roots over one package namespace, `.kt`
  and `.kts` stems, a nested same-name package directory, and a share of
  wildcard `.*` imports so the package fan-out tier — the only tier whose
  output is order-bearing — is inside the fingerprint.

- `depth_ratio`: deep arm at a FIXED file count with ~6x the path
  components. `scaling_ratio` divides the file count out, so it is
  scale-invariant and structurally cannot see a cost that grows with path
  depth instead, and `buildSuffixIndex` (C#, Ruby) and Kotlin's
  `suffixByStem` each emit one entry per component. Measured: go 0.98,
  dart 0.88 (depth-free indexes), ruby 1.48, kotlin 2.20, csharp 3.45 —
  which is why the budget is per language. One global budget would have
  to sit at 5.0 and would let Dart go 0.88 -> 4.9 unnoticed.

- `small_ms_ceiling`: an absolute bound at 4x the measured arm, because a
  constant-factor regression that grows both scale arms equally passes
  every ratio.

- The deep arm must resolve exactly what the small arm resolves. Padding
  was supposed to change depth and nothing else; a deep arm that stopped
  resolving would be timing the null path.

The five fingerprints are unchanged by this commit - verified against the
previous baseline before rewriting it, so adding the kotlin arm and the
deep scale did not perturb the four languages' output.

Kotlin joins the Set-iteration counter in
`import-target-index-parity.test.ts` too. Its own guard
(`kotlin-import-index-reuse.test.ts`) counts index BUILDS, which a scan
added beside a reused index does not move.

That counter is also the only DETERMINISTIC guard against a reintroduced
scan, and this commit documents why rather than pretending otherwise: a
full workspace scan on 1-in-32 imports was measured to pass every timing
arm here (dart, 1.458 scaling against a 1.8 budget, 1.736 ms against a
4 ms ceiling) while the counter reads 14 instead of 1. Tightening the
ceilings toward the noise floor to chase that case would only buy flaky
CI.

`bench/kotlin-import-target/` stays: it fingerprints both file-set
iteration orders and probes the four-tier cascade shape by shape, neither
of which this corpus does.

Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01BCptYZWRgnnJ821rzebQyj

* perf(import-target): merge matching package dirs in one pass

`filesDirectlyInPkgDir` re-spread its accumulator once per matching
directory, costing O(files x dirs^2) copies per import. On a Go monorepo
where many services carry the same package directory (`svcN/internal/pkg`,
which Go's GOPATH cascade queries by two-segment tail) that made the index
SLOWER than the scan it replaced: 13.4x at 1600 matching directories.

Append into one array and sort once. Measured against a verbatim copy of
the pre-change scan, output byte-identical at every k:

  k=200   1400 files   old 0.126 ms   was 0.169 ms   now 0.042 ms
  k=800   5600 files   old 0.457 ms   was 3.002 ms   now 0.185 ms
  k=1600 11200 files   old 0.960 ms   was 12.890 ms  now 0.232 ms

The index now beats the scan by 2.5-4.1x on this shape instead of losing
to it by up to 13x.

Also drop the min-`ord` comparison in `firstFileDirectlyInPkgDir`: the
build loop appends a directory to its last-segment bucket the moment it
accepts that directory's first file, so bucket order already IS ascending
first-file-`ord` order and the first hit is the minimum. Differentially
verified at 0 divergences. The invariant, and the build-loop edits that
would silently break it, are now recorded at the early return.

Type the index containers as deeply readonly so Go's deliberate
`[...rootFiles].sort()` copy is compile-enforced rather than
comment-enforced, and correct the header's claim that a polyglot repo
"never pays" -- only the stored index is per-language.

Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_013rLy781K8E3rRHFGEe1khJ

* test(import-target): guard index reuse at the adapter boundary

`workspace-file-index.ts` documented the hazard as "a defensive
`new Set(allFilePaths)` in an ADAPTER" -- the bug #1918 shipped -- and
named the unit parity test as the guard. It is not: that test imports the
resolvers directly, while production reaches them through
`<lang>ScopeResolver.resolveImportTarget`. Inserting the copy at
`go/scope-resolver.ts:31`, `csharp:35`, `dart:189` and `ruby:268` left the
parity test 28/28 green and `measure.mjs --check` PASS in all four cases.
Kotlin and Python already had adapter-level guards; go/csharp/dart/ruby
had none.

Add `test/integration/<lang>-import-index-reuse.test.ts` for the four,
mirroring the Kotlin/Python precedent: resolve through the scope resolver,
assert the file set is traversed once (twice for C#, which builds two
indexes), and pair every count with a result assertion so a count of 1
cannot be the count of an adapter that resolves nothing. Each was proven
to fail under the copy it exists to catch:

  go     expected 600 to be 1     dart   expected 600 to be 1
  ruby   expected 400 to be 1     csharp expected 600 to be 2

`CountingSet` moves to `test/helpers/counting-file-set.ts` and now counts
`forEach`, `values`, `keys` and `entries` as well as `[Symbol.iterator]`.
It missed a rescan spelled `allFilePaths.forEach(...)` entirely; with the
overrides that mutation reads 14 instead of 1.

Four fixtures that pinned the guard next door, each now shown to kill its
mutation:
- the Dart "matched RAW" case used a forward-slash target, so the basename
  bucket missed before the raw comparison was reached and it asserted
  `null === null`. A positive twin carrying the backslash in the TARGET
  catches both half-mutations.
- no C# or Ruby target addressed the corpus's `win\dir\thing` file, so
  deleting the backslash normalization in `workspace-file-index.ts` passed
  both gates. Now 4 failures.
- `normToRaw`'s first-wins rule had no normalization twin in any corpus.
- the Go nested-package fixture was decided by the `endsWith` half and
  never reached the first-occurrence branch its title names; addressing
  the directory as a single segment makes it reach it.

The parity test's own docstring no longer claims the scan count is a
complete census -- it names the three materialized arrays it cannot see.

Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_013rLy781K8E3rRHFGEe1khJ

* test(import-target): assert every scale, add collide and retained-heap arms

Three holes in the gate this PR ships as its own proof.

1. `--check` computed three fingerprints per language, stored all three,
   and compared one. `DEEP_PAD = 16 -> 0` deleted the entire depth arm and
   still printed PASS, because depth padding is count-neutral by design so
   no asserted number moved. Assert `fingerprint` per scale, and assert
   `deep.fingerprint !== small.fingerprint` so the padding's EFFECT is
   pinned, not just its output.

2. The corpus minted per-index directory names (`src/pkg${d}`,
   `src/Ns${d}`, `lib/feature${d}`), so max last-segment bucket and max
   matching dirs were both 1 -- and bucket cardinality is the only
   non-constant term the index has. The `dirCount > 1` merge branch had
   never executed in any arm. Add a `collide` arm on shared-leaf layouts
   with identical files/imports/resolved counts; it reaches 9,269
   multi-directory merges per run, up to 34 directories at once. Go and
   C#/Dart legitimately score above the linear budget there and get their
   own; Ruby and Kotlin stay at 1.8 because their keyed maps are
   collision-immune and that immunity is the assertion.

3. No arm measured memory, while the C# no-csproj leg newly retains an
   O(files x depth) suffix index. Add a retained-heap arm on the
   `bench/cfg` pattern, including its loud failure when `--expose-gc` is
   missing rather than a silent skip. Measured at 32k files:
   csharp 73.62 MiB, ruby 55.26 MiB. Ceiling is 1.5x, NOT the 4x the
   timing arms use -- the measurement is byte-stable to 0.00085% across
   processes, so 4x would be throwing away the gate. `_arms_note` records
   why, so nobody harmonises it back.

`depth_ratio`, added by this PR, flaked ~1-in-20: go peaked at 1.748 and
dart at 2.043 against a 1.6 budget, both ratios of two sub-3 ms minima.
Fixed at the estimator, not the threshold -- REPS 5 -> 15, matching
`bench/cfg`, `schema-pairs` and `callable-value-flow` (5 was the lowest in
the repo; the sibling `kotlin-import-target` uses 7, which was not enough
here). 22/22 PASS, every arm now at 70-78% of its budget with a <=1.26x
swing. No budget was widened; the distributions are recorded in
`_arms_note` so the headroom is visibly earned.

Three copies of the same overclaim corrected: the parity test NARROWS the
1-in-32 blind spot, it does not close it -- it watches the Set while the
resolvers hold materialized arrays. `_floor` no longer claims its ratios
"match" the issues' (different corpora, both quadratic).

The step moves to the END of the benchmarks job and runs with
`--expose-gc`. A failing step aborts every step after it (#2895), so the
newest, least-proven gate must not sit ahead of eight established ones.

All five output fingerprints are byte-identical to before this session --
the proof that every change here was behaviour-preserving.

Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_013rLy781K8E3rRHFGEe1khJ

* docs(import-target): point the reuse contract at the guard that guards it

`workspace-file-index.ts` told callers the unit parity test guards the
adapter-copy hazard. It does not -- it never crosses the adapter. Name
both layers and say which catches what: the per-language
`test/integration/<lang>-import-index-reuse.test.ts` files at the adapter
boundary, the parity test for a rescan reintroduced inside a resolver.

The C# namespace-dir index comment named `findDirectChild`, which this PR
deleted; it feeds `firstFileDirectlyInPkgDir` now.

Drop `GoResolveContext`, dead since the legacy call-resolution DAG was
removed in #942 -- zero importers, and `gitnexus`'s package.json declares
no `main`, `exports` or `types`, so it is not a published surface.

Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_013rLy781K8E3rRHFGEe1khJ

* refactor(import-target): quality pass over the review-round changes

Four cleanup lanes (reuse / simplification / efficiency / altitude) over the
previous four commits. No behaviour change anywhere: all 25 bench cells
(5 languages x 5 arms) are byte-identical on files, imports, resolved,
distinct_outcomes and fingerprint, re-verified after each individual edit.

**Restores a fast path the last commit lost.** Fixing the O(k^2) accumulator
made the SINGLE-directory case — the overwhelmingly common one — copy the
bucket where the original aliased it: measured 1.11x slower at 4 files/dir
rising to 1.72x at 128. Holding the first bucket by reference and promoting to
an accumulator only when a second directory appears is 0.65-0.97x of the
previous code at dirCount=1 and parity at dirCount=64. 176-case differential,
0 divergences.

**`sortedRootFiles` accessor.** `rootFiles` was the only index container read
directly from outside the module. `readonly` is erased at runtime and
`Array.isArray` widens it back, so the copy rule now lives with the code that
owns the invariant instead of at the call site. No `Object.freeze`: V8's
PACKED_FROZEN_ELEMENTS read cost lands on the hot `matchingDirs` path.

**One shared arm for the four reuse guards.** The distinct-file-set test was
copy-pasted four ways, 33-38 identical lines each, and this repo's own helpers
(`mini-repo.ts`, `scope-model.ts`) document extracting at the SECOND verbatim
consumer. `expectDistinctFileSetsGetOwnIndex` takes what actually varies; its
`expected` type excludes `null` so the pairing rule cannot be reinstated as a
hole. The per-language first and third arms stay duplicated on purpose —
corpora and payload shapes genuinely differ. Re-proven: all four still fail
under an adapter-inserted `new Set(allFilePaths)`.

**Bench.** `dirsFor` shared by the two functions that must agree on directory
fan-out (they mint and address the same files). `SCALES` derived from the arm
table, so a future arm cannot be measured, printed and silently never asserted.
Five timing checks with one shape collapsed to a table — the trailing sentence
had already drifted into four wordings. `uniqueTarget`/`collideTarget` as flat
functions, mirroring the `uniqueDir`/`collideDir` split rather than nesting a
second axis four ternaries deep. One `identityPass` replaces two untimed full
resolution passes per cell: -371 ms median.

**CI step moved back where it belongs.** It was parked last "until #2895
lands", but that reasoning was backwards twice over: the flake that motivated
it was fixed at the estimator in the previous commit, and #2895's own audit
measured the last slot as executing zero times in 13 runs. It sits with the
other resolver-index guards; #2899 carries the `if: !cancelled()` that fixes
step masking for every step at once.

Filed rather than fixed here: #2908 (java and cobol still scan the workspace
per import, same shape as #2877-#2880, neither memoized), #2909 (make index
reuse a contract test over SCOPE_RESOLVERS on one instrument).

Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01Co58j4au9JLf8dmJpwdF9B

---------

Co-authored-by: Gergo Magyar <gergomagyar0@gmail.com>
Co-authored-by: Claude Opus 5 (1M context) <noreply@anthropic.com>
2026-08-09 09:59:37 +01:00

101 lines
4.5 KiB
TypeScript
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

/**
* Production-path regression guard for the Ruby import-resolution index (#2880).
*
* Ruby's bare `require` leg reads the shared `getWorkspaceFileIndex`
* (`import-resolvers/workspace-file-index.ts`), memoized on the `allFilePaths`
* Set identity via a WeakMap. Before #2880 every single `require` materialized
* two arrays AND built a whole `buildSuffixIndex` over the repo, then threw it
* away — the most expensive of the four resolvers hoisted.
*
* Resolution reaches that index through `rubyScopeResolver.resolveImportTarget`
* — the orchestrator adapter — not by calling `resolveRubyImportTarget`
* directly the way the unit parity test does. The adapter must therefore pass
* the Set THROUGH; a defensive copy (`new Set(allFilePaths)`) would hand a
* fresh WeakMap key per call and restore the per-require rebuild. Python hit
* exactly that (PR #1918 review P1), and the parity test cannot see it: it
* never crosses the adapter.
*
* The traversal-count assertions are the perf guard. They are paired with
* result assertions on purpose: a count of 1 is equally true of an adapter that
* has stopped resolving anything at all, so counting alone would stay green
* while every Ruby IMPORTS edge disappeared.
*/
import { describe, it, expect } from 'vitest';
import { rubyScopeResolver } from '../../src/core/ingestion/languages/ruby/scope-resolver.js';
import { CountingSet, expectDistinctFileSetsGetOwnIndex } from '../helpers/counting-file-set.js';
const { resolveImportTarget } = rubyScopeResolver;
const FROM_FILE = 'lib/main.rb';
/**
* A synthetic Ruby app: many service files plus the two requires below —
* `app/models/user` (a multi-segment suffix hit) and `util` (a single-segment
* one). `index.rb` covers the `require_relative` directory form.
*/
function buildWorkspace(fileCount: number): CountingSet {
const files: string[] = [];
for (let i = 0; i < fileCount; i++) {
files.push(`lib/app/services/service${String(i).padStart(5, '0')}.rb`);
}
files.push('lib/app/models/user.rb');
files.push('lib/util.rb');
files.push('lib/support/index.rb');
files.push('lib/main.rb');
return new CountingSet(files);
}
describe('Ruby import resolution — index reuse across requires (#2880)', () => {
it('builds the workspace index once for many requires over a stable file set', () => {
const files = buildWorkspace(300);
const resolved: (string | readonly string[] | null)[] = [];
for (let i = 0; i < 200; i++) {
// A resolvable bare require, and a gem-shaped one that misses. The miss
// is the expensive case: it walks every suffix × every extension before
// returning null, and used to rebuild the suffix index first.
resolved.push(resolveImportTarget('app/models/user', FROM_FILE, files));
resolved.push(resolveImportTarget(`gem${i}/missing`, FROM_FILE, files));
}
expect(files.scans).toBe(1);
// Paired result assertion — a count of 1 must not be the count of an
// adapter that resolves nothing.
expect(resolved[0]).toBe('lib/app/models/user.rb');
expect(resolved[1]).toBeNull();
});
it('a distinct file set gets its own index (no stale cross-run reuse)', () => {
expectDistinctFileSetsGetOwnIndex({
resolveImportTarget,
buildWorkspace: () => buildWorkspace(20),
targetRaw: 'app/models/user',
fromFile: FROM_FILE,
resolutionConfig: undefined,
expected: 'lib/app/models/user.rb',
expectedScans: 1,
});
});
it('still resolves real requires correctly (the perf test is not vacuous)', () => {
const files = buildWorkspace(5);
// Bare `require`: multi-segment and single-segment suffix matches.
expect(resolveImportTarget('app/models/user', FROM_FILE, files)).toBe('lib/app/models/user.rb');
expect(resolveImportTarget('util', FROM_FILE, files)).toBe('lib/util.rb');
// `require_relative`: resolved against the importer's directory, `.rb`
// first and then `<dir>/index.rb`. This leg answers from `Set.has` and
// never touches the index, which is why the counting arm drives bare
// requires instead.
expect(resolveImportTarget('./util', FROM_FILE, files)).toBe('lib/util.rb');
expect(resolveImportTarget('./support', FROM_FILE, files)).toBe('lib/support/index.rb');
expect(resolveImportTarget('../models/user', 'lib/app/services/service00000.rb', files)).toBe(
'lib/app/models/user.rb',
);
// Gems with no matching file in the repo resolve to nothing.
expect(resolveImportTarget('net/http', FROM_FILE, files)).toBeNull();
});
});