morluto/rea

Fork 0

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

[PR #7126] [MERGED] fix(javascript): evaluate each short-circuit left operand once #7658

New issue

Closed

opened 2026-11-03 13:39:26 +00:00 by bsakaguchi · 0 comments

bsakaguchi commented

2026-11-03 13:39:26 +00:00

Owner

📋 Pull Request Information

Original PR: https://github.com/morluto/rea/pull/7126
Author: @kaoru0822-kitauji
Created: 10/25/2026
Status: ✅ Merged
Merged: 10/25/2026
Merged by: @kaoru0822-kitauji

Base: main ← Head: fix/7115-logical-chain-exponential

📝 Commits (1)

c4e90ef fix(javascript): evaluate each short-circuit left operand once

📊 Changes

3 files changed (+178 additions, -12 deletions)

View changed files

📝 src/domain/javascript/javascriptSemanticAnalysis.scope_depth.test.ts (+101 -1)
📝 src/domain/javascript/javascriptSemanticValues.ts (+25 -11)
➕ tests/boundary/cli/javascriptLogicalChainScaling.test.ts (+52 -0)

📄 Description

What broke: Since 6.8.0, JavaScript semantic analysis takes twice as long for each extra operand of a ||/&&/?? chain. A 24-operand chain takes about 60 s, and CodeMirror 5's pug mode (38 operands) hits provider_timeout.
Fix: Logical branch selection already evaluates the left operand. Value evaluation now reuses that value instead of evaluating the left operand again at every level of the chain.
Risk: Low. The change touches one function in javascriptSemanticValues.ts. A differential over 4,160 sources found no output differences, and the CLI output for two multi-file apps is byte-identical.

Summary

Fixes #7115

Regressing commit: 2206822109 fix(javascript): preserve copied values and export publication lifetimes (first released in 6.8.0). That commit added semanticSelectedBranches, which evaluates a logical expression's left operand to decide which branches can be reached. evaluateExpressionValue then mapped evaluateExpression over the returned branch nodes, so the left operand was evaluated a second time. In a left-nested chain ((a || b) || c) || d, each level evaluates its left subtree twice, which gives O(2^n) work.

Problem and expected behavior

Trigger: var tok = f0(s) || f1(s) || ... || f23(s);. The same happens with && and ??, measured below.
Violated invariant: the cost of analyzing a chain should grow roughly linearly with its number of operands, as it did in 6.7.0. Establishing a branch fact should not multiply the work.
New behavior: analysis time stays nearly flat as operands are added. Values, provenance and every other output are unchanged.

Change and scope

semanticSelectedBranches now returns { node, value? }. For a logical expression, the left branch carries the value that selection already computed. Value evaluation uses branch.value ?? evaluateExpression(branch.node, …), and provenance still walks branch.node.
Both evaluations used the same nestedContext(context), so reusing the value gives the same result. The evaluator's side effects (resource-limit records, dependence.lowest, dependency proofs) are idempotent.
Not included: provenance for a logical node still evaluates its left operand's value in order to select branches. Over a long left-nested chain that costs O(k²), capped by the 256-level SEMANTIC_EXPRESSION_DEPTH_LIMIT. It does not appear in profiles: after the fix, the remaining superlinear time at n=4000 is in AST-ancestor walks in member-mutation/initializer indexing, which this PR does not touch.
Contribution scope: an ordinary fix within existing boundaries. A maintainer scope decision is not applicable.

Contract and boundary impact

Semantic owner and earliest changed stage: javascriptSemanticValues.ts (semantic value evaluation). Its value and provenance consumers keep the same results.
Contribution scope fit and linked maintainer decision: not applicable (performance regression fix).
CLI and MCP/tool-catalog contract: none. Output is unchanged.
Provider, bridge, target-format, or platform compatibility: none.
Evidence, artifact, provenance, or reconstruction contract: unchanged (see the differential).
Target selection, authority, upstream behavior, and cleanup details: not applicable.
Generated metadata, package, or installation impact: none.

Expected effects:

Read existing files or captured data.
Launch or attach to a process.
Inject instrumentation or run scripts/code.
Change process memory, registers, files, or configuration.
Contact network services.
Recover protected code or work around protections.
Documentation or usability only; no target interaction.
Not sure yet; investigation or maintainer guidance needed.

Evidence and regression coverage

Tests added or updated:
- src/domain/javascript/javascriptSemanticAnalysis.scope_depth.test.ts: counts reads of each LogicalExpression.left on the parsed AST during analyzeParsedJavaScriptSemantics, at 8 and 16 operands, for ||, &&, ??, and a mixed ||/&&/?? chain with conditional operands. It asserts that reads(16) < 4 × reads(8). It does not depend on wall time. On origin/main all 4 cases fail quickly (for example "expected 393624 to be less than 6880"; doubling per operand would multiply reads by 256). With the fix they pass. A further case checks that a 41-operand chain of known-falsy operands still yields require("electron").app provenance.
- tests/boundary/cli/javascriptLogicalChainScaling.test.ts: the public CLI analyzes a 38-operand || chain (the pug nextToken shape) with --analysis-timeout-ms 15000. The test asserts exit 0, one parsed file and 38 call-site nodes. With the fix it takes about 1.8 s. On origin/main it does not finish (the run with a 30 s deadline hit the vitest timeout).
Base reproduction (built CLI from the issue's generator, origin/main bc143125e): n=16 1.8 s, n=18 2.2 s, n=20 4.3 s, n=22 12.4 s.
Bisect: 2206822109^ (c8f8ec656) has flat domain-level semantic time (n=14/16/18/20: 6/2/6/2 ms). 2206822109 doubles per operand (n=14/16/18: 56/163/642 ms).
CPU profile (main, n=18, domain analyzeJavaScriptSemantics): 813 of 824 ms inclusive is under semanticSelectedBranches → evaluateExpressionValue.
Differential (main dist vs fix dist, same process setup):
- analyzeJavaScriptSemantics and analyzeJavaScriptStaticSource were run on 4,160 sources: every string/template literal that parses as JS from the 395 JavaScript/Electron test files, plus 657 generated sources (219 expressions, each in 3 wrappers). The generated expressions cover ||/&&/?? chains, mixed chains, ternary-of-logical and nested chains with 2–12 operands, and known-constant operands such as false || require("electron"), null ?? require("path"), false && … and 1 ? require("a") : …. The SHA-256 of the full serialized output differed for 0 of 4,160 sources. Main was run twice to confirm it is deterministic.
- CLI analyze-javascript-application --format json on two multi-file apps. One holds the 219 generated chain sources and the other 400 test-corpus sources. The JSON output is byte-identical between main and the fix (32.8 MB and 13.4 MB).

Measurements (built CLI, one cold run each, /usr/bin/time -l; CPU = user+sys; RSS = max resident size reported for the process family, i.e. the largest single process):

Input	main wall / CPU / RSS	fix wall / CPU / RSS
n=18	2.7 s / 2.8 s / 343 MiB	1.6 s / 1.6 s / 337 MiB
n=20	4.7 s / 5.1 s / 347 MiB	1.5 s / 1.8 s / 347 MiB
n=24	60.9 s / 56.8 s / 333 MiB (completed just under the 60 s deadline)	1.7 s / 1.8 s / 339 MiB
n=40	`provider_timeout` at 60 s / 61.5 s / 334 MiB	2.3 s / 2.4 s / 336 MiB
n=100	`provider_timeout` at 60 s / 62.4 s / 324 MiB	2.4 s / 2.4 s / 372 MiB
`codemirror@5.65.18` `mode/pug/pug.js`, unmodified	`provider_timeout` at 120 s / 121 s / 324 MiB	2.0 s / 2.4 s / 364 MiB, ok
all 121 `codemirror@5.65.18` `mode//.js` files	`provider_timeout` at 120 s (pug)	42 s / 51 s / 1116 MiB, ok (see the remaining gap below)

Domain-level analyzeJavaScriptSemantics for the issue's chain with the fix: n=24 2 ms, n=100 10 ms, n=400 54 ms, n=1000 144 ms. && and ?? at n=100 take 13 ms each. On main, && and ?? at n=18 take about 1,045 ms each (the same doubling).

User-visible CLI/MCP output: unchanged (byte-identical in the differential).
Remaining proof gaps:
- MCP was not run separately. It shares the analyzer.
- Obsidian's modes.min.js was not available and was not tested.
- One timing run per data point. Other agents' jobs were running on the same host.
- Separate pre-existing issue, not caused by this PR: codemirror@5.65.18 mode/stylus/stylus.js exhausts the owned worker's 1024 MiB heap during static analysis. It does so on both main and this branch (main 23.1 s, fix 20.9 s, same limitation reported). It accounts for most of the 42 s in the all-modes run. I did not check whether 6.7.0 handled it.

For boundary fixes: no lifecycle stage is changed. The boundary coverage is a public CLI workflow plus production-boundary domain analysis.

For evidence-bearing changes:

Observed, derived, and inferred claims remain distinguishable.
Artifact identity, source provenance, and failed attempts remain preserved.
Unsupported, incomplete, unavailable, or uncertain outcomes remain visible.

Validation performed

node node_modules/vitest/vitest.mjs run src/domain/javascript tests/boundary/cli/javascriptLogicalChainScaling.test.ts tests/boundary/javascriptSemanticTraceEvidence.test.ts --maxWorkers=2: 157 files, 4,134 tests passed.
npm run test:local -- src/domain/javascript/javascriptSemanticAnalysis.scope_depth.test.ts src/domain/javascript/javascriptSemanticAnalysis.unions.test.ts: 42 passed. On the main source the 4 new scaling cases fail.
npm run test:focused -- tests/boundary/cli/javascriptLogicalChainScaling.test.ts: passed (1.8 s). Against a main build it fails on timeout.
npm run check:fast: passed.
npm run format:check: passed.
Differential and benchmark runs as listed above.

Compatibility, safety, and release

Breaking changes or migration steps: none.
Real Hopper/Ghidra, browser, or OS coverage: not applicable. Measured on macOS arm64 with Node.js 26.5.0 (below the engines range; run with npm_config_engine_strict=false).
Package or release metadata impact: none.
Security, privacy, process, or containment review: no new process, file, or network behavior. The CodeMirror package was fetched with npm pack --ignore-scripts and only analyzed.

Author readiness

Human owner: @kaoru0822-kitauji

I reviewed the final diff and relevant existing code, understand the change and its edge cases, and take responsibility for the complete PR, including AI-assisted work.
I checked the evidence above, confirmed it supports the current change, and recorded meaningful validation gaps.
I declare this PR ready for initial maintainer review.

Before merge

This PR addresses a concrete problem or an agreed enhancement.
Material scope and authority questions are resolved, and any required maintainer scope decision covers the final diff.
The PR has one focused outcome and the title follows type(scope): outcome.
Related issue is linked, or the reason for not linking one is stated above.
Tests cover changed observable behavior and meaningful failure paths.
Owning docs, contracts, and generated metadata are updated where needed.
User-visible CLI/MCP changes include representative output.
I checked the final diff for secrets, unrelated cleanup, and unsupported claims.

🤖 Generated with Claude Code

_{🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.}

## 📋 Pull Request Information **Original PR:** https://github.com/morluto/rea/pull/7126 **Author:** [@kaoru0822-kitauji](https://github.com/kaoru0822-kitauji) **Created:** 10/25/2026 **Status:** ✅ Merged **Merged:** 10/25/2026 **Merged by:** [@kaoru0822-kitauji](https://github.com/kaoru0822-kitauji) **Base:** `main` ← **Head:** `fix/7115-logical-chain-exponential` --- ### 📝 Commits (1) - [`c4e90ef`](https://github.com/morluto/rea/commit/c4e90eff58cc22153b41278ace41e1eba8860c85) fix(javascript): evaluate each short-circuit left operand once ### 📊 Changes **3 files changed** (+178 additions, -12 deletions) <details> <summary>View changed files</summary> 📝 `src/domain/javascript/javascriptSemanticAnalysis.scope_depth.test.ts` (+101 -1) 📝 `src/domain/javascript/javascriptSemanticValues.ts` (+25 -11) ➕ `tests/boundary/cli/javascriptLogicalChainScaling.test.ts` (+52 -0) </details> ### 📄 Description **What broke:** Since 6.8.0, JavaScript semantic analysis takes twice as long for each extra operand of a `||`/`&&`/`??` chain. A 24-operand chain takes about 60 s, and CodeMirror 5's pug mode (38 operands) hits `provider_timeout`. **Fix:** Logical branch selection already evaluates the left operand. Value evaluation now reuses that value instead of evaluating the left operand again at every level of the chain. **Risk:** Low. The change touches one function in `javascriptSemanticValues.ts`. A differential over 4,160 sources found no output differences, and the CLI output for two multi-file apps is byte-identical. ## Summary Fixes #7115 Regressing commit: 22068221093e56ed7474ede7b7820dbe102f9069 `fix(javascript): preserve copied values and export publication lifetimes` (first released in 6.8.0). That commit added `semanticSelectedBranches`, which evaluates a logical expression's left operand to decide which branches can be reached. `evaluateExpressionValue` then mapped `evaluateExpression` over the returned branch nodes, so the left operand was evaluated a second time. In a left-nested chain `((a || b) || c) || d`, each level evaluates its left subtree twice, which gives O(2^n) work. ## Problem and expected behavior - Trigger: `var tok = f0(s) || f1(s) || ... || f23(s);`. The same happens with `&&` and `??`, measured below. - Violated invariant: the cost of analyzing a chain should grow roughly linearly with its number of operands, as it did in 6.7.0. Establishing a branch fact should not multiply the work. - New behavior: analysis time stays nearly flat as operands are added. Values, provenance and every other output are unchanged. ## Change and scope - `semanticSelectedBranches` now returns `{ node, value? }`. For a logical expression, the left branch carries the value that selection already computed. Value evaluation uses `branch.value ?? evaluateExpression(branch.node, …)`, and provenance still walks `branch.node`. - Both evaluations used the same `nestedContext(context)`, so reusing the value gives the same result. The evaluator's side effects (resource-limit records, `dependence.lowest`, dependency proofs) are idempotent. - Not included: provenance for a logical node still evaluates its left operand's value in order to select branches. Over a long left-nested chain that costs O(k²), capped by the 256-level `SEMANTIC_EXPRESSION_DEPTH_LIMIT`. It does not appear in profiles: after the fix, the remaining superlinear time at n=4000 is in AST-ancestor walks in member-mutation/initializer indexing, which this PR does not touch. - Contribution scope: an ordinary fix within existing boundaries. A maintainer scope decision is not applicable. ## Contract and boundary impact - Semantic owner and earliest changed stage: `javascriptSemanticValues.ts` (semantic value evaluation). Its value and provenance consumers keep the same results. - Contribution scope fit and linked maintainer decision: not applicable (performance regression fix). - CLI and MCP/tool-catalog contract: none. Output is unchanged. - Provider, bridge, target-format, or platform compatibility: none. - Evidence, artifact, provenance, or reconstruction contract: unchanged (see the differential). - Target selection, authority, upstream behavior, and cleanup details: not applicable. - Generated metadata, package, or installation impact: none. Expected effects: - [x] Read existing files or captured data. - [ ] Launch or attach to a process. - [ ] Inject instrumentation or run scripts/code. - [ ] Change process memory, registers, files, or configuration. - [ ] Contact network services. - [ ] Recover protected code or work around protections. - [ ] Documentation or usability only; no target interaction. - [ ] Not sure yet; investigation or maintainer guidance needed. ## Evidence and regression coverage - Tests added or updated: - `src/domain/javascript/javascriptSemanticAnalysis.scope_depth.test.ts`: counts reads of each `LogicalExpression.left` on the parsed AST during `analyzeParsedJavaScriptSemantics`, at 8 and 16 operands, for `||`, `&&`, `??`, and a mixed `||`/`&&`/`??` chain with conditional operands. It asserts that reads(16) < 4 × reads(8). It does not depend on wall time. On `origin/main` all 4 cases fail quickly (for example "expected 393624 to be less than 6880"; doubling per operand would multiply reads by 256). With the fix they pass. A further case checks that a 41-operand chain of known-falsy operands still yields `require("electron").app` provenance. - `tests/boundary/cli/javascriptLogicalChainScaling.test.ts`: the public CLI analyzes a 38-operand `||` chain (the pug `nextToken` shape) with `--analysis-timeout-ms 15000`. The test asserts exit 0, one parsed file and 38 call-site nodes. With the fix it takes about 1.8 s. On `origin/main` it does not finish (the run with a 30 s deadline hit the vitest timeout). - Base reproduction (built CLI from the issue's generator, `origin/main` bc143125e): n=16 1.8 s, n=18 2.2 s, n=20 4.3 s, n=22 12.4 s. - Bisect: `2206822109^` (c8f8ec656) has flat domain-level semantic time (n=14/16/18/20: 6/2/6/2 ms). `2206822109` doubles per operand (n=14/16/18: 56/163/642 ms). - CPU profile (main, n=18, domain `analyzeJavaScriptSemantics`): 813 of 824 ms inclusive is under `semanticSelectedBranches` → `evaluateExpressionValue`. - Differential (main dist vs fix dist, same process setup): - `analyzeJavaScriptSemantics` and `analyzeJavaScriptStaticSource` were run on 4,160 sources: every string/template literal that parses as JS from the 395 JavaScript/Electron test files, plus 657 generated sources (219 expressions, each in 3 wrappers). The generated expressions cover `||`/`&&`/`??` chains, mixed chains, ternary-of-logical and nested chains with 2–12 operands, and known-constant operands such as `false || require("electron")`, `null ?? require("path")`, `false && …` and `1 ? require("a") : …`. The SHA-256 of the full serialized output differed for **0 of 4,160** sources. Main was run twice to confirm it is deterministic. - CLI `analyze-javascript-application --format json` on two multi-file apps. One holds the 219 generated chain sources and the other 400 test-corpus sources. The JSON output is **byte-identical** between main and the fix (32.8 MB and 13.4 MB). - Measurements (built CLI, one cold run each, `/usr/bin/time -l`; CPU = user+sys; RSS = max resident size reported for the process family, i.e. the largest single process): | Input | main wall / CPU / RSS | fix wall / CPU / RSS | |---|---|---| | n=18 | 2.7 s / 2.8 s / 343 MiB | 1.6 s / 1.6 s / 337 MiB | | n=20 | 4.7 s / 5.1 s / 347 MiB | 1.5 s / 1.8 s / 347 MiB | | n=24 | 60.9 s / 56.8 s / 333 MiB (completed just under the 60 s deadline) | 1.7 s / 1.8 s / 339 MiB | | n=40 | `provider_timeout` at 60 s / 61.5 s / 334 MiB | 2.3 s / 2.4 s / 336 MiB | | n=100 | `provider_timeout` at 60 s / 62.4 s / 324 MiB | 2.4 s / 2.4 s / 372 MiB | | `codemirror@5.65.18` `mode/pug/pug.js`, unmodified | `provider_timeout` at 120 s / 121 s / 324 MiB | 2.0 s / 2.4 s / 364 MiB, ok | | all 121 `codemirror@5.65.18` `mode/*/*.js` files | `provider_timeout` at 120 s (pug) | 42 s / 51 s / 1116 MiB, ok (see the remaining gap below) | Domain-level `analyzeJavaScriptSemantics` for the issue's chain with the fix: n=24 2 ms, n=100 10 ms, n=400 54 ms, n=1000 144 ms. `&&` and `??` at n=100 take 13 ms each. On main, `&&` and `??` at n=18 take about 1,045 ms each (the same doubling). - User-visible CLI/MCP output: unchanged (byte-identical in the differential). - Remaining proof gaps: - MCP was not run separately. It shares the analyzer. - Obsidian's `modes.min.js` was not available and was not tested. - One timing run per data point. Other agents' jobs were running on the same host. - Separate pre-existing issue, not caused by this PR: `codemirror@5.65.18` `mode/stylus/stylus.js` exhausts the owned worker's 1024 MiB heap during static analysis. It does so on both main and this branch (main 23.1 s, fix 20.9 s, same limitation reported). It accounts for most of the 42 s in the all-modes run. I did not check whether 6.7.0 handled it. For boundary fixes: no lifecycle stage is changed. The boundary coverage is a public CLI workflow plus production-boundary domain analysis. For evidence-bearing changes: - [x] Observed, derived, and inferred claims remain distinguishable. - [x] Artifact identity, source provenance, and failed attempts remain preserved. - [x] Unsupported, incomplete, unavailable, or uncertain outcomes remain visible. ## Validation performed - `node node_modules/vitest/vitest.mjs run src/domain/javascript tests/boundary/cli/javascriptLogicalChainScaling.test.ts tests/boundary/javascriptSemanticTraceEvidence.test.ts --maxWorkers=2`: 157 files, 4,134 tests passed. - `npm run test:local -- src/domain/javascript/javascriptSemanticAnalysis.scope_depth.test.ts src/domain/javascript/javascriptSemanticAnalysis.unions.test.ts`: 42 passed. On the main source the 4 new scaling cases fail. - `npm run test:focused -- tests/boundary/cli/javascriptLogicalChainScaling.test.ts`: passed (1.8 s). Against a main build it fails on timeout. - `npm run check:fast`: passed. - `npm run format:check`: passed. - Differential and benchmark runs as listed above. ## Compatibility, safety, and release - Breaking changes or migration steps: none. - Real Hopper/Ghidra, browser, or OS coverage: not applicable. Measured on macOS arm64 with Node.js 26.5.0 (below the engines range; run with `npm_config_engine_strict=false`). - Package or release metadata impact: none. - Security, privacy, process, or containment review: no new process, file, or network behavior. The CodeMirror package was fetched with `npm pack --ignore-scripts` and only analyzed. ## Author readiness Human owner: @kaoru0822-kitauji - [x] I reviewed the final diff and relevant existing code, understand the change and its edge cases, and take responsibility for the complete PR, including AI-assisted work. - [x] I checked the evidence above, confirmed it supports the current change, and recorded meaningful validation gaps. - [x] I declare this PR ready for initial maintainer review. ## Before merge - [ ] This PR addresses a concrete problem or an agreed enhancement. - [ ] Material scope and authority questions are resolved, and any required maintainer scope decision covers the final diff. - [ ] The PR has one focused outcome and the title follows `type(scope): outcome`. - [ ] Related issue is linked, or the reason for not linking one is stated above. - [ ] Tests cover changed observable behavior and meaningful failure paths. - [ ] Owning docs, contracts, and generated metadata are updated where needed. - [ ] User-visible CLI/MCP changes include representative output. - [ ] I checked the final diff for secrets, unrelated cleanup, and unsupported claims. 🤖 Generated with [Claude Code](https://claude.com/claude-code) --- <sub>🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.</sub>

bsakaguchi

2026-11-03 13:39:26 +00:00

closed this issue
added the
pull-request
label

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#7658

No description provided.

Rows
Columns