[GH-ISSUE #1748] [Bug] Repeated endpoint observations cause quadratic JavaScript graph accumulation #586

New issue

Closed

opened 2026-10-15 18:26:26 +00:00 by bsakaguchi · 0 comments

bsakaguchi commented

2026-10-15 18:26:26 +00:00

Owner

Originally created by @N0zoM1z0 on GitHub (Oct 11, 2026).
Original GitHub issue: https://github.com/morluto/rea/issues/1748

Before submitting

I searched the open and closed issues for a related report.
I removed credentials, tokens, private paths, and sensitive target data.

Area

Evidence, artifacts, or reconstruction

Observed behavior

Repeated observations of the same JavaScript endpoint cause increasingly expensive graph accumulation. Each append rebuilds a map of all previously retained observations and sorts the complete growing set again.

Public CLI analysis of 1,000 identical fetch('/same') calls produced one endpoint node with all 1,000 distinct source-range observations and complete coverage. An isolated harness then exercised the same production accumulator and Evidence factories. Its ordered observation-ID checksum exactly matched the CLI's endpoint observations, establishing that it measures the same merge semantics.

In two unprofiled runs, doubling from 4,000 to 8,000 observations increased CPU spent in addNode by approximately four times:

Distinct observations	Run 1 CPU	Run 2 CPU
1,000	376 ms	366 ms
2,000	578 ms	469 ms
4,000	1,858 ms	1,590 ms
8,000	7,179 ms	7,834 ms

These numbers time only accumulation: input construction, final graph validation, and CLI serialization are excluded. Run 2 used a different size order after the 1,000-observation warm-up. Timings are host observations, not portable thresholds or an end-to-end latency claim.

Reproduction

Build the pinned source using npm ci and npm run build:cached.
In a temporary application directory, create main.js containing 1,000 copies of fetch('/same'); separated by newlines.

Run the public workflow:

node scripts/rea.mjs analyze-javascript-application "$APP" \
  --artifact-format directory --max-heap-mb 512 \
  --analysis-timeout-ms 60000 --format json --full-output > result.json

In data.normalized_result.graph, verify one endpoint node with 1,000 observations, distinct source-range lines, exact /same values, and complete coverage.
Run the production-function harness below from the repository root after building. It preserves the same observation semantics while removing worker/parser/serialization costs. The harness validates the completed graph and checks observation uniqueness outside the timed region.

Expected behavior

Maintain an incrementally deduplicated observation collection for each node and perform canonical sorting once when materializing the graph. Retain every distinct observation, preserve node and observation identities, and keep deterministic canonical graph output.

Impact and scope

CPU grows superlinearly for a common repeated-literal workload. Source also shows growing maps and arrays being reconstructed on every append; allocation volume was not measured. This is a graph-accumulation performance bug; the tested observations were retained correctly, with unchanged deterministic checksums across runs. CLI and MCP share this producer, but this investigation executed the public CLI and the production accumulator, not a live model workflow.

Larger public CLI cases with a 512 MiB worker limit reached existing projection budgets and returned partial coverage. In particular, the 4,000-call case retained static facts on the file node and did not expand endpoint nodes. Their total runtimes are not used as equivalent complete-graph scaling measurements.

REA version

Source revision 21650455a9c90a26e725c3505a3c17054cc4516c.

Runtime and platform

Linux x86_64 VPS; Node.js v24.18.0; isolated runs on one CPU, nice 10. Unprofiled accumulator runs used a 512 MiB V8 old-space limit.

Target and artifact context

Local inert JavaScript source with repeated short endpoint literals. No provider, GUI, target execution, browser, or credentials are required.

Interface

CLI

Earliest failure stage

Artifact or evidence registration

Relevant output or evidence

Flameox 0.2.9 analysis of the actual process executing the production accumulator reported 2,773 CPU samples. addNode had 1,631 self samples. The profile covers the isolated producer harness, including untimed setup/validation; sample counts are not milliseconds and overlapping inclusive counts are not summed. Anonymous generated-code rows are not attributed to specific TypeScript operations without a resolved source map.

All harness graphs had complete coverage, one endpoint node, and exactly N unique observations. For N=1,000, the CLI and harness's ordered observation IDs both hashed to:

a43614710ddc8b72f49e8a968c196582f88595ff912dc9cf64746f8083bab5f8

Typed outcome or recovery expected

Return the same complete graph and exact Evidence while avoiding repeated full-collection copying and sorting. Preserve existing resource-limit outcomes for workloads that genuinely exceed capacity.

Analysis or suspected cause

The source-derived cause is in JavaScriptArtifactGraphAccumulator.addNode: each duplicate ID copies all prior observations into a new map and sorts the entire accumulated set. Across N distinct observations for one node, map construction alone visits a triangular number of entries. The endpoint producer uses the same node identity for the same artifact and literal while source ranges give observations distinct identities; repeated endpoints are therefore normal inputs, not malformed schema data.

Additional context

Suggested acceptance: preserve the existing two-occurrence CLI/MCP journey, exercise a larger repeated endpoint source, and assert exact observation IDs/ranges/coverage and canonical graph identity. Measure producer scaling separately from full CLI latency; avoid a brittle absolute-time unit assertion. Imported graph authentication and malformed-input validation must remain intact.

The closed #1495 concerns a separate returned-reference semantic analysis pass; this report isolates observation merging in the artifact graph accumulator.

Reproducible producer harness (save outside the repository as accumulator-probe.mjs and invoke it with Node from the repository root):

import { createHash } from 'node:crypto';
import { pathToFileURL } from 'node:url';

const repo = process.cwd();
const moduleAt = (path) => import(pathToFileURL(`${repo}/${path}`).href);
const [
  { JavaScriptArtifactGraphAccumulator },
  { artifactLocalIdentity },
  { astObservationEvidence },
  { compactStringIdentityKey },
  { completeApplicationCoverage },
  { createJavaScriptApplicationGraph },
] = await Promise.all([
  moduleAt('dist/application/javascript/JavaScriptArtifactGraphAccumulator.js'),
  moduleAt('dist/application/javascript/JavaScriptArtifactGraphContext.js'),
  moduleAt('dist/application/javascript/JavaScriptArtifactGraphEvidence.js'),
  moduleAt('dist/domain/compactStringIdentity.js'),
  moduleAt('dist/domain/javascript/javascriptApplicationEvidenceSchemas.js'),
  moduleAt('dist/domain/javascript/javascriptApplicationGraph.js'),
]);

const sourceLine = "fetch('/same');";
const coverage = completeApplicationCoverage();
const counts=process.argv.length>2?process.argv.slice(2).map(Number):[1_000,2_000,4_000,8_000];
for (const count of counts) {
  const source = `${sourceLine}\n`.repeat(count);
  const sha256 = createHash('sha256').update(source).digest('hex');
  const key = compactStringIdentityKey('/same');
  const inputs = Array.from({ length: count }, (_, index) => ({
    kind: 'endpoint',
    identity: artifactLocalIdentity(sha256, 'network', key),
    observations: [{
      label: '/same',
      properties: { endpoint_kind: 'network', value: '/same', mechanism: 'call:fetch' },
      evidence: astObservationEvidence({
        sha256,
        path: 'main.js',
        range: {
          start: { line: index + 1, column: 0 },
          end: { line: index + 1, column: 14 },
        },
        operation: 'discover-static-endpoint',
        coverage,
      }),
    }],
  }));

  const accumulator = new JavaScriptArtifactGraphAccumulator();
  const started = performance.now();
  const cpuStarted=process.cpuUsage();
  for (const input of inputs) accumulator.addNode(input);
  const elapsedMs = performance.now() - started;
  const cpu=process.cpuUsage(cpuStarted);

  const nodes = accumulator.nodes();
  const node = nodes[0];
  if (nodes.length !== 1 || node === undefined || node.observations.length !== count)
    throw new Error(`Unexpected merge result for ${count} inputs`);
  const ids = node.observations.map(({ observation_id }) => observation_id);
  if (new Set(ids).size !== count) throw new Error(`Duplicate observation IDs at ${count}`);
  const checksum = createHash('sha256').update(ids.join('\n')).digest('hex');
  const graph = createJavaScriptApplicationGraph({
    schema: 'JavaScriptApplicationGraph',
    root_node_ids: [node.node_id],
    nodes,
    edges: [],
    coverage,
    limitations: [],
  });
  console.log(JSON.stringify({
    count,
    elapsed_ms: Number(elapsedMs.toFixed(2)),
    cpu_ms: (cpu.user+cpu.system)/1000,
    node_count: nodes.length,
    observation_count: ids.length,
    observation_id_checksum: checksum,
    graph_id: graph.graph_id,
    graph_coverage: graph.coverage.status,
  }));
}

Originally created by @N0zoM1z0 on GitHub (Oct 11, 2026). Original GitHub issue: https://github.com/morluto/rea/issues/1748 ### Before submitting - [x] I searched the open and closed issues for a related report. - [x] I removed credentials, tokens, private paths, and sensitive target data. ### Area Evidence, artifacts, or reconstruction ### Observed behavior Repeated observations of the same JavaScript endpoint cause increasingly expensive graph accumulation. Each append rebuilds a map of all previously retained observations and sorts the complete growing set again. Public CLI analysis of 1,000 identical `fetch('/same')` calls produced one endpoint node with all 1,000 distinct source-range observations and complete coverage. An isolated harness then exercised the same production accumulator and Evidence factories. Its ordered observation-ID checksum exactly matched the CLI's endpoint observations, establishing that it measures the same merge semantics. In two unprofiled runs, doubling from 4,000 to 8,000 observations increased CPU spent in `addNode` by approximately four times: | Distinct observations | Run 1 CPU | Run 2 CPU | | --- | ---: | ---: | | 1,000 | 376 ms | 366 ms | | 2,000 | 578 ms | 469 ms | | 4,000 | 1,858 ms | 1,590 ms | | 8,000 | 7,179 ms | 7,834 ms | These numbers time only accumulation: input construction, final graph validation, and CLI serialization are excluded. Run 2 used a different size order after the 1,000-observation warm-up. Timings are host observations, not portable thresholds or an end-to-end latency claim. ### Reproduction 1. Build the pinned source using `npm ci` and `npm run build:cached`. 2. In a temporary application directory, create `main.js` containing 1,000 copies of `fetch('/same');` separated by newlines. 3. Run the public workflow: ```sh node scripts/rea.mjs analyze-javascript-application "$APP" \ --artifact-format directory --max-heap-mb 512 \ --analysis-timeout-ms 60000 --format json --full-output > result.json ``` 4. In `data.normalized_result.graph`, verify one `endpoint` node with 1,000 observations, distinct source-range lines, exact `/same` values, and complete coverage. 5. Run the production-function harness below from the repository root after building. It preserves the same observation semantics while removing worker/parser/serialization costs. The harness validates the completed graph and checks observation uniqueness outside the timed region. ### Expected behavior Maintain an incrementally deduplicated observation collection for each node and perform canonical sorting once when materializing the graph. Retain every distinct observation, preserve node and observation identities, and keep deterministic canonical graph output. ### Impact and scope CPU grows superlinearly for a common repeated-literal workload. Source also shows growing maps and arrays being reconstructed on every append; allocation volume was not measured. This is a graph-accumulation performance bug; the tested observations were retained correctly, with unchanged deterministic checksums across runs. CLI and MCP share this producer, but this investigation executed the public CLI and the production accumulator, not a live model workflow. Larger public CLI cases with a 512 MiB worker limit reached existing projection budgets and returned partial coverage. In particular, the 4,000-call case retained static facts on the file node and did not expand endpoint nodes. Their total runtimes are **not** used as equivalent complete-graph scaling measurements. ### REA version Source revision `21650455a9c90a26e725c3505a3c17054cc4516c`. ### Runtime and platform Linux x86_64 VPS; Node.js v24.18.0; isolated runs on one CPU, nice 10. Unprofiled accumulator runs used a 512 MiB V8 old-space limit. ### Target and artifact context Local inert JavaScript source with repeated short endpoint literals. No provider, GUI, target execution, browser, or credentials are required. ### Interface CLI ### Earliest failure stage Artifact or evidence registration ### Relevant output or evidence Flameox 0.2.9 analysis of the actual process executing the production accumulator reported 2,773 CPU samples. `addNode` had 1,631 self samples. The profile covers the isolated producer harness, including untimed setup/validation; sample counts are not milliseconds and overlapping inclusive counts are not summed. Anonymous generated-code rows are not attributed to specific TypeScript operations without a resolved source map. All harness graphs had complete coverage, one endpoint node, and exactly N unique observations. For N=1,000, the CLI and harness's ordered observation IDs both hashed to: ```text a43614710ddc8b72f49e8a968c196582f88595ff912dc9cf64746f8083bab5f8 ``` ### Typed outcome or recovery expected Return the same complete graph and exact Evidence while avoiding repeated full-collection copying and sorting. Preserve existing resource-limit outcomes for workloads that genuinely exceed capacity. ### Analysis or suspected cause The source-derived cause is in [JavaScriptArtifactGraphAccumulator.addNode](https://github.com/morluto/rea/blob/21650455a9c90a26e725c3505a3c17054cc4516c/src/application/javascript/JavaScriptArtifactGraphAccumulator.ts#L15-L39): each duplicate ID copies all prior observations into a new map and sorts the entire accumulated set. Across N distinct observations for one node, map construction alone visits a triangular number of entries. The endpoint producer uses the same node identity for the same artifact and literal while source ranges give observations distinct identities; repeated endpoints are therefore normal inputs, not malformed schema data. ### Additional context Suggested acceptance: preserve the existing two-occurrence CLI/MCP journey, exercise a larger repeated endpoint source, and assert exact observation IDs/ranges/coverage and canonical graph identity. Measure producer scaling separately from full CLI latency; avoid a brittle absolute-time unit assertion. Imported graph authentication and malformed-input validation must remain intact. The closed [#1495](https://github.com/morluto/rea/issues/1495) concerns a separate returned-reference semantic analysis pass; this report isolates observation merging in the artifact graph accumulator. Reproducible producer harness (save outside the repository as `accumulator-probe.mjs` and invoke it with Node from the repository root): ```js import { createHash } from 'node:crypto'; import { pathToFileURL } from 'node:url'; const repo = process.cwd(); const moduleAt = (path) => import(pathToFileURL(`${repo}/${path}`).href); const [ { JavaScriptArtifactGraphAccumulator }, { artifactLocalIdentity }, { astObservationEvidence }, { compactStringIdentityKey }, { completeApplicationCoverage }, { createJavaScriptApplicationGraph }, ] = await Promise.all([ moduleAt('dist/application/javascript/JavaScriptArtifactGraphAccumulator.js'), moduleAt('dist/application/javascript/JavaScriptArtifactGraphContext.js'), moduleAt('dist/application/javascript/JavaScriptArtifactGraphEvidence.js'), moduleAt('dist/domain/compactStringIdentity.js'), moduleAt('dist/domain/javascript/javascriptApplicationEvidenceSchemas.js'), moduleAt('dist/domain/javascript/javascriptApplicationGraph.js'), ]); const sourceLine = "fetch('/same');"; const coverage = completeApplicationCoverage(); const counts=process.argv.length>2?process.argv.slice(2).map(Number):[1_000,2_000,4_000,8_000]; for (const count of counts) { const source = `${sourceLine}\n`.repeat(count); const sha256 = createHash('sha256').update(source).digest('hex'); const key = compactStringIdentityKey('/same'); const inputs = Array.from({ length: count }, (_, index) => ({ kind: 'endpoint', identity: artifactLocalIdentity(sha256, 'network', key), observations: [{ label: '/same', properties: { endpoint_kind: 'network', value: '/same', mechanism: 'call:fetch' }, evidence: astObservationEvidence({ sha256, path: 'main.js', range: { start: { line: index + 1, column: 0 }, end: { line: index + 1, column: 14 }, }, operation: 'discover-static-endpoint', coverage, }), }], })); const accumulator = new JavaScriptArtifactGraphAccumulator(); const started = performance.now(); const cpuStarted=process.cpuUsage(); for (const input of inputs) accumulator.addNode(input); const elapsedMs = performance.now() - started; const cpu=process.cpuUsage(cpuStarted); const nodes = accumulator.nodes(); const node = nodes[0]; if (nodes.length !== 1 || node === undefined || node.observations.length !== count) throw new Error(`Unexpected merge result for ${count} inputs`); const ids = node.observations.map(({ observation_id }) => observation_id); if (new Set(ids).size !== count) throw new Error(`Duplicate observation IDs at ${count}`); const checksum = createHash('sha256').update(ids.join('\n')).digest('hex'); const graph = createJavaScriptApplicationGraph({ schema: 'JavaScriptApplicationGraph', root_node_ids: [node.node_id], nodes, edges: [], coverage, limitations: [], }); console.log(JSON.stringify({ count, elapsed_ms: Number(elapsedMs.toFixed(2)), cpu_ms: (cpu.user+cpu.system)/1000, node_count: nodes.length, observation_count: ids.length, observation_id_checksum: checksum, graph_id: graph.graph_id, graph_coverage: graph.coverage.status, })); } ```

bsakaguchi

2026-10-15 18:26:26 +00:00