morluto/rea

Fork 0

mirror of https://github.com/morluto/rea.git synced 2026-11-05 06:45:22 +00:00

[GH-ISSUE #7774] [Design] Bound per-binding member-write records in JavaScript semantic analysis #4639

New issue

Open

opened 2026-10-31 00:51:42 +00:00 by bsakaguchi · 3 comments

bsakaguchi commented

2026-10-31 00:51:42 +00:00

Owner

Originally created by @vickyekong on GitHub (Oct 28, 2026).
Original GitHub issue: https://github.com/morluto/rea/issues/7774

Originally assigned to: @kaoru0822-kitauji on GitHub.

Before submitting

I searched the open and closed issues and pull requests for a related discussion.
I understand the contribution scope must be reviewed before integration; open questions are welcome here.
This discussion does not include credentials, private samples, or sensitive target data. The reproducer is self-authored; no third-party bundle code is included.

Decision needed

How should REA bound the number of member-write and escape records that one JavaScript binding can accumulate during semantic member-mutation indexing, and what widening or unknown should replace records past that bound?

Context and evidence

Observed (MCP, rea 6.8.0): analyze_web_bundle on a large Closure Compiler ADVANCED web application (two first-party scripts, 919 KB and 1.3 MB) reported both scripts as unknowns after the 30-second per-script analysis deadline. Bisecting one script isolated a single DOM-event-dispatch function. The self-authored reproducer below has the same shape: register-style variable reuse (b, c, d, e reassigned across a loop), member writes through aliases, and a parent-chain walk.

function dispatch(a) {
  var b, c, d, e, f, g;
  for (b = a.target; b && b !== a.root; ) {
    c = b; d = a;
    e = c.cache;
    if (!e) { e = {}; c.cache = e; }
    f = e[d.kind];
    f !== void 0 && (d.hit = [f, c]);
    if (a.hit) break;
    if ((c = b.owner)) { b = c; continue; }
    b = b.parentNode;
    b = b && b.isFragment ? b.host : b;
  }
  if ((b = a.hit)) {
    c = a.event; d = a.kind; e = b[1]; f = c.related;
    if (!f || f === e) a.hit = void 0;
    else {
      c = a.event; d = b[1]; e = {};
      for (var k in c) { f = k; g = c[f]; e[f] = g; }
      e.type = c.type; e.target = e.source = d; e.original = c;
      a.event = e; a.target = b[1];
    }
  }
}

Observed (record counts, one run, base b675073): after member-mutation indexing of this function, binding a holds 8,788 member-write records from 10 syntactic write sites, with 5,054 distinct property paths up to depth 11, and 775 escape records. Other bindings hold c 3,302, b 2,472, d 1,040, e 618, g 430 and f 167 records.

Observed (elapsed time; single runs on macOS, Node 24.22.1; source-level phase harness for parse → index → ambient writes → member mutations → route scan, not the public CLI):

Input	`b675073`	With path index (`perf/member-write-key-index`)
Reproducer without the `owner` branch	0.70 s	0.53 s
Reproducer without the `isFragment ? host` line	18.8 s	13.9 s
Full reproducer	160.5 s	61.9 s
Original real-bundle statement	> 60 s	> 60 s (stopped)

Removing one alias assignment drops the time by an order of magnitude, which is consistent with combinatorial growth rather than a linear per-record cost. CPU time and peak process-family memory were not measured. Runs were not repeated.

Source-derived reasoning:

Every member-write push calls semanticProjectedSourceFactsAtRead, which scanned all of binding.memberWrites and binding.escapedPaths, plus semanticEffectTiming parent-chain walks per candidate. Total work is therefore quadratic in records per binding.
SEMANTIC_ALIAS_SELECTION_LIMIT (512, reported as the alias-selections resource limit) bounds work within a single selection or markValue call. Nothing bounds the records one binding accumulates across many calls.
SemanticPropertyPathCoverage keys include mutation, origin, owner, and read site, and only equal-depth writes cover each other. Alias chains through reused registers therefore yield distinct, non-deduplicated records at increasing depths.
memberWrites and escapedPaths are append-only. The only push sites are in javascriptSemanticMemberMutations.ts.
The route scan triggers member-mutation indexing whenever a script contains navigation calls or href properties, so most real web bundles reach this path.

Prototype (local branch, not yet a PR): perf/member-write-key-index adds an append-only path trie, so each projected read examines only effects whose recorded path is compatible with the selection. A seeded randomized equivalence test against the previous inline predicate checks identical results and order; a mutation check confirmed that the test detects a broken index. Focused semantic and web-bundle suites pass (16 files, 625 tests). The trie removes the full rescan but leaves record growth unbounded: after it, about 54% of profile self-time is in the mutation-initializer timing helpers. It is a partial fix only.

Relation to #2498: #2498 reports the same unbounded per-binding effect growth on a wasm2js file, driven by typed-array stores. Its thread names collapsing effects as an open lattice decision. #5139 (typed-array escape pruning) and #2941 (lookup memoization) are both included in b675073, yet this reproducer has no typed arrays and still grows. A general bound therefore seems necessary rather than another shape-specific prune.

Unknown: how much precision real bundles lose under each option below, and whether the growth comes from a missing coverage or deduplication rule rather than requiring a cap.

Expected interaction with targets

Read existing files or captured data

Boundary details

Static analysis of caller-selected JavaScript only. A bound must surface as an explicit resource limit or unknown in coverage, never as silently missing routes or values.

Options and tradeoffs

Per-binding record budget with path widening. Charge records per binding across queries. Past the budget, join new writes into a widened path using the existing joinSemanticPropertyPaths and record alias-selections. This keeps source facts at reduced precision, but whether the widened write remains sound for stored-source propagation still needs checking.
Overflow writes become escapes. This is simple and conservative for "may have changed" checks. Source-derived concern: escapes are ignored when includeUnknown is false, so stored-source propagation would lose facts rather than widen them, which may hide routes.
Per-pass effect budget with fallback to the unindexed state. Cap total effects per indexing pass. On overflow, discard the index and use the unindexed answer (referenceMayHaveChangedAt returns true) with the alias-selections reason. This is the coarsest option and the easiest to keep correct, but it loses all member-mutation facts for the script.
Fix the producer instead of capping. Deduplicate records whose coverage keys differ only by alias depth or read site when they carry the same source facts. This preserves the most precision, but it needs a precise equivalence argument and may not bound the worst case on its own.

The path index on the branch is compatible with all four options and could land separately.

Verification available so far

I have a prototype or observed results

Success criteria and open questions

The full reproducer completes well under the default per-script deadline, and so does the real-bundle statement, checked locally without publishing its code.
Results for existing route, ambient-write, mutation-initializer, and returned-reference fixtures are unchanged. Any precision loss on large inputs is reported through the alias-selections limit in coverage.
Open: which option the maintainers prefer, the budget value, and whether stored-source propagation must survive overflow (this rules out option 2).

References

src/domain/javascript/javascriptSemanticMemberMutations.ts (push sites and collectSemanticMemberMutationsSteps)
src/domain/javascript/javascriptSemanticProjectedSources.ts (semanticProjectedSourceFactsAtRead)
src/domain/javascript/javascriptSemanticResourceLimits.ts (SEMANTIC_ALIAS_SELECTION_LIMIT)
#2498 (same bottleneck, wasm2js input), #2941 and #5139 (merged partial fixes), #4321 and #4331 (closed)
Local prototype branch perf/member-write-key-index, commit 74dcdfe (not pushed)

AI agent note

An AI agent (Cursor) collected these measurements and drafted this issue at the user's request. Temporary instrumentation was removed; the prototype branch is local and has not been pushed.

Originally created by @vickyekong on GitHub (Oct 28, 2026). Original GitHub issue: https://github.com/morluto/rea/issues/7774 Originally assigned to: @kaoru0822-kitauji on GitHub. ### Before submitting - [x] I searched the open and closed issues and pull requests for a related discussion. - [x] I understand the contribution scope must be reviewed before integration; open questions are welcome here. - [x] This discussion does not include credentials, private samples, or sensitive target data. The reproducer is self-authored; no third-party bundle code is included. ### Decision needed How should REA bound the number of member-write and escape records that one JavaScript binding can accumulate during semantic member-mutation indexing, and what widening or unknown should replace records past that bound? ### Context and evidence **Observed (MCP, rea 6.8.0):** `analyze_web_bundle` on a large Closure Compiler ADVANCED web application (two first-party scripts, 919 KB and 1.3 MB) reported both scripts as unknowns after the 30-second per-script analysis deadline. Bisecting one script isolated a single DOM-event-dispatch function. The self-authored reproducer below has the same shape: register-style variable reuse (`b`, `c`, `d`, `e` reassigned across a loop), member writes through aliases, and a parent-chain walk. ```js function dispatch(a) { var b, c, d, e, f, g; for (b = a.target; b && b !== a.root; ) { c = b; d = a; e = c.cache; if (!e) { e = {}; c.cache = e; } f = e[d.kind]; f !== void 0 && (d.hit = [f, c]); if (a.hit) break; if ((c = b.owner)) { b = c; continue; } b = b.parentNode; b = b && b.isFragment ? b.host : b; } if ((b = a.hit)) { c = a.event; d = a.kind; e = b[1]; f = c.related; if (!f || f === e) a.hit = void 0; else { c = a.event; d = b[1]; e = {}; for (var k in c) { f = k; g = c[f]; e[f] = g; } e.type = c.type; e.target = e.source = d; e.original = c; a.event = e; a.target = b[1]; } } } ``` **Observed (record counts, one run, base `b675073`):** after member-mutation indexing of this function, binding `a` holds 8,788 member-write records from 10 syntactic write sites, with 5,054 distinct property paths up to depth 11, and 775 escape records. Other bindings hold `c` 3,302, `b` 2,472, `d` 1,040, `e` 618, `g` 430 and `f` 167 records. **Observed (elapsed time; single runs on macOS, Node 24.22.1; source-level phase harness for parse → index → ambient writes → member mutations → route scan, not the public CLI):** | Input | `b675073` | With path index (`perf/member-write-key-index`) | | --- | --- | --- | | Reproducer without the `owner` branch | 0.70 s | 0.53 s | | Reproducer without the `isFragment ? host` line | 18.8 s | 13.9 s | | Full reproducer | 160.5 s | 61.9 s | | Original real-bundle statement | > 60 s | > 60 s (stopped) | Removing one alias assignment drops the time by an order of magnitude, which is consistent with combinatorial growth rather than a linear per-record cost. CPU time and peak process-family memory were not measured. Runs were not repeated. **Source-derived reasoning:** - Every member-write push calls `semanticProjectedSourceFactsAtRead`, which scanned all of `binding.memberWrites` and `binding.escapedPaths`, plus `semanticEffectTiming` parent-chain walks per candidate. Total work is therefore quadratic in records per binding. - `SEMANTIC_ALIAS_SELECTION_LIMIT` (512, reported as the `alias-selections` resource limit) bounds work within a single selection or `markValue` call. Nothing bounds the records one binding accumulates across many calls. - `SemanticPropertyPathCoverage` keys include mutation, origin, owner, and read site, and only equal-depth writes cover each other. Alias chains through reused registers therefore yield distinct, non-deduplicated records at increasing depths. - `memberWrites` and `escapedPaths` are append-only. The only push sites are in `javascriptSemanticMemberMutations.ts`. - The route scan triggers member-mutation indexing whenever a script contains navigation calls or `href` properties, so most real web bundles reach this path. **Prototype (local branch, not yet a PR):** `perf/member-write-key-index` adds an append-only path trie, so each projected read examines only effects whose recorded path is compatible with the selection. A seeded randomized equivalence test against the previous inline predicate checks identical results and order; a mutation check confirmed that the test detects a broken index. Focused semantic and web-bundle suites pass (16 files, 625 tests). The trie removes the full rescan but leaves record growth unbounded: after it, about 54% of profile self-time is in the mutation-initializer timing helpers. It is a partial fix only. **Relation to #2498:** #2498 reports the same unbounded per-binding effect growth on a wasm2js file, driven by typed-array stores. Its thread names collapsing effects as an open lattice decision. #5139 (typed-array escape pruning) and #2941 (lookup memoization) are both included in `b675073`, yet this reproducer has no typed arrays and still grows. A general bound therefore seems necessary rather than another shape-specific prune. **Unknown:** how much precision real bundles lose under each option below, and whether the growth comes from a missing coverage or deduplication rule rather than requiring a cap. ### Expected interaction with targets Read existing files or captured data ### Boundary details Static analysis of caller-selected JavaScript only. A bound must surface as an explicit resource limit or unknown in coverage, never as silently missing routes or values. ### Options and tradeoffs 1. **Per-binding record budget with path widening.** Charge records per binding across queries. Past the budget, join new writes into a widened path using the existing `joinSemanticPropertyPaths` and record `alias-selections`. This keeps source facts at reduced precision, but whether the widened write remains sound for stored-source propagation still needs checking. 2. **Overflow writes become escapes.** This is simple and conservative for "may have changed" checks. Source-derived concern: escapes are ignored when `includeUnknown` is false, so stored-source propagation would lose facts rather than widen them, which may hide routes. 3. **Per-pass effect budget with fallback to the unindexed state.** Cap total effects per indexing pass. On overflow, discard the index and use the unindexed answer (`referenceMayHaveChangedAt` returns true) with the `alias-selections` reason. This is the coarsest option and the easiest to keep correct, but it loses all member-mutation facts for the script. 4. **Fix the producer instead of capping.** Deduplicate records whose coverage keys differ only by alias depth or read site when they carry the same source facts. This preserves the most precision, but it needs a precise equivalence argument and may not bound the worst case on its own. The path index on the branch is compatible with all four options and could land separately. ### Verification available so far I have a prototype or observed results ### Success criteria and open questions - The full reproducer completes well under the default per-script deadline, and so does the real-bundle statement, checked locally without publishing its code. - Results for existing route, ambient-write, mutation-initializer, and returned-reference fixtures are unchanged. Any precision loss on large inputs is reported through the `alias-selections` limit in coverage. - Open: which option the maintainers prefer, the budget value, and whether stored-source propagation must survive overflow (this rules out option 2). ### References - `src/domain/javascript/javascriptSemanticMemberMutations.ts` (push sites and `collectSemanticMemberMutationsSteps`) - `src/domain/javascript/javascriptSemanticProjectedSources.ts` (`semanticProjectedSourceFactsAtRead`) - `src/domain/javascript/javascriptSemanticResourceLimits.ts` (`SEMANTIC_ALIAS_SELECTION_LIMIT`) - #2498 (same bottleneck, wasm2js input), #2941 and #5139 (merged partial fixes), #4321 and #4331 (closed) - Local prototype branch `perf/member-write-key-index`, commit `74dcdfe` (not pushed) ### AI agent note An AI agent (Cursor) collected these measurements and drafted this issue at the user's request. Temporary instrumentation was removed; the prototype branch is local and has not been pushed.

bsakaguchi commented

2026-10-31 00:51:43 +00:00

Author

Owner

@kaoru0822-kitauji commented on GitHub (Oct 30, 2026):

Measurements on current main 317bf3fe2 (macOS arm64, Node 24.22.1, single runs). They suggest a semantics-preserving first step that does not need the bound decision.

Observed:

rea analyze-javascript-application <dir> --artifact-format directory --analysis-timeout-ms 240000 on the issue's full reproducer, plus one location.href = u export, takes 146 s wall / 147 s user, 580 MB max RSS. With the default 30 s deadline it would be reported as an unknown.
After member-mutation indexing, binding a holds 8,788 write records from 10 syntactic sites on the reduced reproducer (the version without the isFragment line). Only 5,056 of them are distinct across every stored field: receiverIdentity, path, node, receiverInitializers, receiverAt and assignedSources. So 42% are exact duplicates. They come from traversal states that differ only in coverage-key fields the record never stores, such as originAt, ownerInitializer and the getter flag. Escapes show the same pattern (775 records, 567 distinct).
A CPU profile puts 85% of the time in semanticProjectedSourceFactsAtRead, called from the write-push site. Within that, about 30% is the uncached position() walk inside semanticTopLevelEffectFollowsCapture. That walk is a pure function of the node and the parent map, like the positions already kept in InitializerPositionCache.

Prototype (patched build, not yet a PR):

Keep one member-write or escape record per distinct stored fact. Propagation is unchanged: the receiver query and the enqueues still run for every traversal state. The recorded-effect count is identical (18,672 on the reduced reproducer).
Cache the top-level statement position next to the existing initializer position caches.

Source-level analyzeJavaScriptSemantics time: reduced reproducer 8.7 s → 2.5 s, full reproducer → 15.1 s.

Plan: I'll open a PR with only these semantics-preserving changes. It will include an equivalence check that the semantic IR is byte-identical before and after on the reproducers and the existing semantic and route suites. Per-binding growth is still unbounded, so the question of which bound or widening to use (options 1–4) stays open here, and the PR will reference this issue rather than close it.

@kaoru0822-kitauji commented on GitHub (Oct 30, 2026): Measurements on current main `317bf3fe2` (macOS arm64, Node 24.22.1, single runs). They suggest a semantics-preserving first step that does not need the bound decision. **Observed:** - `rea analyze-javascript-application <dir> --artifact-format directory --analysis-timeout-ms 240000` on the issue's full reproducer, plus one `location.href = u` export, takes 146 s wall / 147 s user, 580 MB max RSS. With the default 30 s deadline it would be reported as an unknown. - After member-mutation indexing, binding `a` holds 8,788 write records from 10 syntactic sites on the reduced reproducer (the version without the `isFragment` line). Only **5,056** of them are distinct across every stored field: `receiverIdentity`, `path`, `node`, `receiverInitializers`, `receiverAt` and `assignedSources`. So 42% are exact duplicates. They come from traversal states that differ only in coverage-key fields the record never stores, such as `originAt`, `ownerInitializer` and the getter flag. Escapes show the same pattern (775 records, 567 distinct). - A CPU profile puts 85% of the time in `semanticProjectedSourceFactsAtRead`, called from the write-push site. Within that, about 30% is the uncached `position()` walk inside `semanticTopLevelEffectFollowsCapture`. That walk is a pure function of the node and the parent map, like the positions already kept in `InitializerPositionCache`. **Prototype (patched build, not yet a PR):** 1. Keep one member-write or escape record per distinct stored fact. Propagation is unchanged: the receiver query and the enqueues still run for every traversal state. The recorded-effect count is identical (18,672 on the reduced reproducer). 2. Cache the top-level statement position next to the existing initializer position caches. Source-level `analyzeJavaScriptSemantics` time: reduced reproducer 8.7 s → 2.5 s, full reproducer → 15.1 s. **Plan:** I'll open a PR with only these semantics-preserving changes. It will include an equivalence check that the semantic IR is byte-identical before and after on the reproducers and the existing semantic and route suites. Per-binding growth is still unbounded, so the question of which bound or widening to use (options 1–4) stays open here, and the PR will reference this issue rather than close it.

bsakaguchi commented

2026-10-31 00:51:43 +00:00

Author

Owner

@kaoru0822-kitauji commented on GitHub (Oct 30, 2026):

Two independent, semantics-preserving PRs are now open. Each byte-identically reproduces the semantic IR and the CLI Evidence:

#8103 keeps one member-effect record per stored fact, caches top-level statement positions, and tests the path first. It takes the full reproducer's CLI run from 146 s to 40 s.
#8108 indexes record paths for projected reads, following your path-trie idea. Alone it takes each worker phase from about 80 s to 29 s. Together with #8103 the CLI run takes 20 s.

Per-binding growth is still unbounded, so the bound or widening question (options 1–4) remains open for a maintainer decision.

@kaoru0822-kitauji commented on GitHub (Oct 30, 2026): Two independent, semantics-preserving PRs are now open. Each byte-identically reproduces the semantic IR and the CLI Evidence: - #8103 keeps one member-effect record per stored fact, caches top-level statement positions, and tests the path first. It takes the full reproducer's CLI run from 146 s to 40 s. - #8108 indexes record paths for projected reads, following your path-trie idea. Alone it takes each worker phase from about 80 s to 29 s. Together with #8103 the CLI run takes 20 s. Per-binding growth is still unbounded, so the bound or widening question (options 1–4) remains open for a maintainer decision.

bsakaguchi commented

2026-10-31 00:51:43 +00:00

Author

Owner

@kaoru0822-kitauji commented on GitHub (Oct 30, 2026):

A public input for the bound decision. It was measured on #8103's build (deduplicated records), macOS arm64, Node 24.22.1, single runs.

Input: #4601's isolated webpack factory, @qodo/command@0.36.0 factory 0x175ed (input/module.js SHA-256 b08aae1f5ca81a4e3307e16b982453c43fac8547f23506ed5123496352cb570c). It is obfuscator-style code: one function scope with _0x… bindings and computed member access.

Observed while indexing member mutations:

Only ~20,000 distinct records exist after 85 s, but the live heap is already ~2 GB. An uncapped run reached 6.6 GB RSS after 488 s without finishing. So the cost is not the records themselves.
Paths grow by wildcard depth at single sites, for example [*,*], [*,*,*], …, [*,*,*,*,*,*] at one write node. Each step goes through a different binding, so the existing revisit/repeatsUnpruned cut never fires. With equal-depth-only coverage, every depth is a new fact.
A sampling heap profile taken at 10,000 records (457 MB live) attributes about 175 MB to SemanticPropertyPathCoverage.retain. That is one coverage trie per traversal-state key, with two eager Maps per node and long pathState strings. Another ~65 MB goes to per-enqueue copies of the visited-binding Set and queue entries. Making coverage nodes lazy cut the 10k-record heap from 457 MB to 373 MB, but the run still never converges.

Implication for options 1–4: dedup and indexing remove redundant work (#8103, #8108), but this input keeps producing new wildcard-depth facts. Something must bound or widen them. One candidate that touches only this shape: once a path is entirely wildcards beyond the binding's observable prefix, a deeper all-wildcard path adds no selectable key. Treating it as covered by the shorter one, or recording an escape at the shallower depth, would bound growth by depth. Whether that is sound for stored-source propagation is the same question you raised for option 2, so I'm leaving it to your decision rather than implementing it.

@kaoru0822-kitauji commented on GitHub (Oct 30, 2026): A public input for the bound decision. It was measured on #8103's build (deduplicated records), macOS arm64, Node 24.22.1, single runs. **Input:** #4601's isolated webpack factory, `@qodo/command@0.36.0` factory `0x175ed` (`input/module.js` SHA-256 `b08aae1f5ca81a4e3307e16b982453c43fac8547f23506ed5123496352cb570c`). It is obfuscator-style code: one function scope with `_0x…` bindings and computed member access. **Observed while indexing member mutations:** - Only ~20,000 distinct records exist after 85 s, but the live heap is already ~2 GB. An uncapped run reached 6.6 GB RSS after 488 s without finishing. So the cost is not the records themselves. - Paths grow by wildcard depth at single sites, for example `[*,*]`, `[*,*,*]`, …, `[*,*,*,*,*,*]` at one write node. Each step goes through a different binding, so the existing revisit/`repeatsUnpruned` cut never fires. With equal-depth-only coverage, every depth is a new fact. - A sampling heap profile taken at 10,000 records (457 MB live) attributes about 175 MB to `SemanticPropertyPathCoverage.retain`. That is one coverage trie per traversal-state key, with two eager `Map`s per node and long `pathState` strings. Another ~65 MB goes to per-enqueue copies of the visited-binding `Set` and queue entries. Making coverage nodes lazy cut the 10k-record heap from 457 MB to 373 MB, but the run still never converges. **Implication for options 1–4:** dedup and indexing remove redundant work (#8103, #8108), but this input keeps producing new wildcard-depth facts. Something must bound or widen them. One candidate that touches only this shape: once a path is entirely wildcards beyond the binding's observable prefix, a deeper all-wildcard path adds no selectable key. Treating it as covered by the shorter one, or recording an escape at the shallower depth, would bound growth by depth. Whether that is sound for stored-source propagation is the same question you raised for option 2, so I'm leaving it to your decision rather than implementing it.

bsakaguchi referenced this issue

2026-10-31 01:14:08 +00:00

[PR #4761] [MERGED] fix(mcp): accept authentic native Evidence for managed boundary verification #6395

No milestone

No project

No assignees

1 participant

Notifications

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference

morluto/rea#4639

No description provided.

Rows
Columns