[PR #1505] [MERGED] fix(artifacts): record each case collision once at its diverging segment #2925

New issue

Closed

opened 2026-10-17 21:11:54 +00:00 by bsakaguchi · 0 comments

bsakaguchi commented

2026-10-17 21:11:54 +00:00

Owner

📋 Pull Request Information

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

Base: main ← Head: fix/case-collision-linear

📝 Commits (1)

3006d02 fix(artifacts): record each case collision once at its diverging segment

📊 Changes

2 files changed (+168 additions, -60 deletions)

View changed files

➕ src/artifacts/ArtifactPaths.test.ts (+83 -0)
📝 src/artifacts/ArtifactPaths.ts (+85 -60)

📄 Description

Summary

This addresses the two ArtifactPaths.ts review findings left open on #1480. (The third finding, about the Windows extraction test, was fixed in b12d0c63.)

Quadratic growth. noteFoldedSpellings collected every terminal under each case spelling and gave each one a set of all terminals under the other spellings. Each occurrence then received one limitation joining those paths. With Foo/ and foo/ holding N files each, that is 2N occurrences each listing N paths.

Repro, a ZIP with Foo/a{i}.txt and foo/b{i}.txt, using rea inspect-artifact x.zip --format json:

N per spelling	main: bytes / max RSS	this branch: bytes / max RSS
500	7,903,661 / 392 MB	1,038,661 / 379 MB
1,000	29,802,665 / 554 MB	—
2,000	119,604,665 / 943 MB	4,144,665 / 494 MB

A somewhat larger untrusted ZIP would exhaust the process before inventory returns.

Recursion. recordCaseCollisions and terminalsUnder recursed once per path component. A ZIP name with about 30,000 one-letter components still fits the 65,535-byte name field, and it threw RangeError: Maximum call stack size exceeded.

Change

A collision is recorded once, at the segment where the spellings diverge. A linked chain shares it with every path in that subtree. The trie is walked with an explicit stack.
Each affected occurrence names the colliding prefix and the first other spelling in code-point order, plus a count when there are more spellings:
- same file, two spellings (unchanged text): Logical path Main.js collides under English (en-US) Unicode case folding with main.js; …
- a path under a colliding directory: Logical path res/foo/b.txt is under res/foo, which collides under English (en-US) Unicode case folding with res/Foo; …
- three or more spellings: … with A.txt and 1 other spelling; …
Every spelling is still its own occurrence with its own limitation, so the full set stays in the result. The inventory-level limitation and extraction behavior are unchanged.

Verification

New src/artifacts/ArtifactPaths.test.ts covers the file message, a directory collision on descendants, the count form, a 2×5,000 subtree with one bounded limitation per occurrence, and a 30,000-component name. On main four of the five fail: the stack test with RangeError, and the subtree test runs 4.2 s with N-entry lists.
npm run test:focused -- tests/boundary/providers/native/artifactProvider.archiveSafety.test.ts tests/boundary/providers/native/artifactProvider.failureDetail.test.ts tests/composition/android/application.test.ts passes (14 tests).
npm run check:fast and npm run docs:check pass.
No real Hopper or Ghidra verification was needed.

🤖 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/1505 **Author:** [@kaoru0822-kitauji](https://github.com/kaoru0822-kitauji) **Created:** 10/10/2026 **Status:** ✅ Merged **Merged:** 10/10/2026 **Merged by:** [@kaoru0822-kitauji](https://github.com/kaoru0822-kitauji) **Base:** `main` ← **Head:** `fix/case-collision-linear` --- ### 📝 Commits (1) - [`3006d02`](https://github.com/morluto/rea/commit/3006d0252e95ff9a458895a08c699f3599a0d45f) fix(artifacts): record each case collision once at its diverging segment ### 📊 Changes **2 files changed** (+168 additions, -60 deletions) <details> <summary>View changed files</summary> ➕ `src/artifacts/ArtifactPaths.test.ts` (+83 -0) 📝 `src/artifacts/ArtifactPaths.ts` (+85 -60) </details> ### 📄 Description ## Summary This addresses the two `ArtifactPaths.ts` review findings left open on #1480. (The third finding, about the Windows extraction test, was fixed in b12d0c63.) **Quadratic growth.** `noteFoldedSpellings` collected every terminal under each case spelling and gave each one a set of all terminals under the other spellings. Each occurrence then received one limitation joining those paths. With `Foo/` and `foo/` holding N files each, that is 2N occurrences each listing N paths. Repro, a ZIP with `Foo/a{i}.txt` and `foo/b{i}.txt`, using `rea inspect-artifact x.zip --format json`: | N per spelling | main: bytes / max RSS | this branch: bytes / max RSS | |---|---|---| | 500 | 7,903,661 / 392 MB | 1,038,661 / 379 MB | | 1,000 | 29,802,665 / 554 MB | — | | 2,000 | 119,604,665 / 943 MB | 4,144,665 / 494 MB | A somewhat larger untrusted ZIP would exhaust the process before inventory returns. **Recursion.** `recordCaseCollisions` and `terminalsUnder` recursed once per path component. A ZIP name with about 30,000 one-letter components still fits the 65,535-byte name field, and it threw `RangeError: Maximum call stack size exceeded`. ## Change - A collision is recorded once, at the segment where the spellings diverge. A linked chain shares it with every path in that subtree. The trie is walked with an explicit stack. - Each affected occurrence names the colliding prefix and the first other spelling in code-point order, plus a count when there are more spellings: - same file, two spellings (unchanged text): `Logical path Main.js collides under English (en-US) Unicode case folding with main.js; …` - a path under a colliding directory: `Logical path res/foo/b.txt is under res/foo, which collides under English (en-US) Unicode case folding with res/Foo; …` - three or more spellings: `… with A.txt and 1 other spelling; …` Every spelling is still its own occurrence with its own limitation, so the full set stays in the result. The inventory-level limitation and extraction behavior are unchanged. ## Verification - New `src/artifacts/ArtifactPaths.test.ts` covers the file message, a directory collision on descendants, the count form, a 2×5,000 subtree with one bounded limitation per occurrence, and a 30,000-component name. On `main` four of the five fail: the stack test with `RangeError`, and the subtree test runs 4.2 s with N-entry lists. - `npm run test:focused -- tests/boundary/providers/native/artifactProvider.archiveSafety.test.ts tests/boundary/providers/native/artifactProvider.failureDetail.test.ts tests/composition/android/application.test.ts` passes (14 tests). - `npm run check:fast` and `npm run docs:check` pass. - No real Hopper or Ghidra verification was needed. 🤖 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-10-17 21:11:54 +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#2925

No description provided.

Rows
Columns