You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
safe-bash: ${x#*pat}/${x%pat*}/${x//*pat/} are O(n²) with a 64 M-unit ledger — 3 KB value = 10 s, 5 KB value burns the full 30 s CPU budget #666
Where:packages/safe-bash/src/shell/runtime.ts ~:4583-4620 — parameterPattern tries every prefix/suffix length and calls matchTokens (src/shell/pattern.ts:80+) per candidate; for a *-containing pattern each attempt is itself linear, so the removal is O(n²) at 2 µs/step. The work ledger is sized limit*4+1024 = 64 M units (:4586), far more than 30 s can process, so maxCpuMs/maxWallClockMs is the binding limit. Interruptible (abort honored at the deadline).
Measured: 1 KB → 691 ms; 3 KB → 9 958 ms (${x##*1} 7 026 ms, ${x/%*1/} 10 808 ms; re-verified independently: 9 887 ms); 5 KB → maxWallClockMs at 30 003 ms; 10 KB … 1 MB → maxCpuMs/maxWallClockMs at ~30 s, result never produced. Control: case $x in *1) on the same 3 KB value → 3–18 ms.
Impact: (d) — a 60-byte script pins the thread for the full wall clock per exec, loopable across execs. Same class as closed #623/#634 (under-priced work ledger), different mechanism.
Fix: for *-anchored removals compute the match once (single backtracking scan with an end-position search for longest/shortest) instead of trying every split; or charge length per candidate against a ledger sized to real CPU (≈1–2 M units), not 4 × maxExpansionBytes.
Validated and fixed on main at 8a1f223. Parameter-pattern operations now compute reusable match boundaries instead of rescanning candidate substrings; global replacement reuses the same table. Bounded witnesses changed global no-match reads from 291/1799/12559 to 23/47/95 at input sizes 8/16/32. Work and table memory are admitted through existing budgets; shortest/longest, anchoring, Unicode and cancellation controls pass. Delivery: maintained build, 282 runner checks, complete package suite with 22,153 passes and 63 skips, guarded root lint, and 166 playground tests. Built-public 8 KiB case matches Bash; browser 2 KiB case succeeds, while its tighter 64 KiB profile refuses 8 KiB without raising limits. Evidence: docs/plans/bugfix-666-pattern-boundaries.md. Remote main verified; release monitored separately.
Scoped release verified: run 34200967739 succeeded for exact delivered main commit 8a1f223. This verifies scoped package publication; the separate root poe-code release remains independently monitored.
Activity
kamilio commentedon Sep 8, 2026
Validated and fixed on main at 8a1f223. Parameter-pattern operations now compute reusable match boundaries instead of rescanning candidate substrings; global replacement reuses the same table. Bounded witnesses changed global no-match reads from 291/1799/12559 to 23/47/95 at input sizes 8/16/32. Work and table memory are admitted through existing budgets; shortest/longest, anchoring, Unicode and cancellation controls pass. Delivery: maintained build, 282 runner checks, complete package suite with 22,153 passes and 63 skips, guarded root lint, and 166 playground tests. Built-public 8 KiB case matches Bash; browser 2 KiB case succeeds, while its tighter 64 KiB profile refuses 8 KiB without raising limits. Evidence: docs/plans/bugfix-666-pattern-boundaries.md. Remote main verified; release monitored separately.
kamilio commentedon Sep 8, 2026
Scoped release verified: run 34200967739 succeeded for exact delivered main commit 8a1f223. This verifies scoped package publication; the separate root poe-code release remains independently monitored.