Files
headroom/tests/test_tool_output_scan_bounds.py
bae62bc87b fix(compression): bound the JSON-block and truncation-banner scans (#4845)
## Description

Two scans over tool output ran in quadratic time:

1. **Mixed-content JSON detection** (`_has_valid_json_block_with_text`,
default-on through `ContentRouter` → `is_mixed_content`) and the section
splitter try every line that starts with `{` or `[` as a JSON block. A
candidate that never balances walks to the end of the content, so N such
lines cost N²/2 line steps (20,000 lines of `{` took about a minute).
The existing per-line memo removes the character work but not the line
walk.
2. **ast-grep truncation-banner detection** (`_detect_truncation`): the
banner regex has unbounded runs on both sides of the `showing lines A-B
of T total` phrase, so an unclosed banner was rescanned once per phrase.

Fixes:

1. `_JsonBlockScanner` answers every candidate of one pass with exactly
the result of walking it. Candidates are walked directly until they have
walked as many lines as the content has. After that, all candidates are
answered together:
- Every walk is a chain of (line, string-state) nodes with one successor
each, so all walks form one forest, and each node is scanned once.
- With `D(v)` the bracket and brace sums from node `v` to the end of its
chain, a walk from `u` balances at `w` exactly when `D(next(w)) >= D(u)`
in both sums. So each candidate ends just before its nearest ancestor
that satisfies this.
- One depth-first pass with an undoable tree of (brace sum, depth)
stacks, keyed by bracket sum, finds that ancestor in O(log² n). There is
no budget.
2. The banner is found in two linear steps: locate `[truncated: partial
view`, take the span to the next bracket (it must be `]`), then match
the phrase inside that span. Same matches as the old regex (checked
against it on 3,000 random layouts).

Fix adapted from a proposal by HetCreep.

## Type of Change

- [x] Bug fix (non-breaking change that fixes an issue)
- [ ] New feature (non-breaking change that adds functionality)
- [ ] Breaking change (fix or feature that would cause existing
functionality to change)
- [ ] Documentation update
- [x] Performance improvement
- [ ] Code refactoring (no functional changes)

## Changes Made

- `headroom/transforms/mixed_content.py`: `_JsonBlockScanner` (direct
walks, then a forest solve over all candidates), used by
`_has_valid_json_block_with_text` and `split_into_sections`.
`_extract_json_block` is unchanged from main.
- `headroom/proxy/interceptors/astgrep.py`: `_TRUNCATION_SIGNATURES` now
holds only the phrase pattern; `_iter_banners` finds the `[truncated:
partial view … ]` span and searches the phrase inside it.
- `tests/test_tool_output_scan_bounds.py`: timing tests for both shapes,
an oracle test against the previous banner regex, and checks that a real
banner and a 5,000-line JSON block inside text are still found. A JSON
object that follows 150 or 20,000 unclosed `{` lines, or a prefix whose
bracket and brace counts each reach zero but never on the same line
(once, and repeated 130 times), still gets its own JSON section, as does
one after 100 or 10,000 pairs of lines ending inside an escaped string.
The solve is checked against `_extract_json_block` on 3,000 random
inputs.

## Testing

- [x] Unit tests pass (`pytest`)
- [x] Linting passes (`ruff check .`)
- [x] Type checking passes (`mypy headroom`)
- [x] New tests added for new functionality
- [x] Manual testing performed

### Test Output

New tests on `origin/main` code:

```text
FAILED tests/test_tool_output_scan_bounds.py::test_truncation_scan_is_linear_on_unclosed_banner
FAILED tests/test_tool_output_scan_bounds.py::test_json_block_scans_are_bounded_on_unclosed_braces
    assert time.perf_counter() - start < 10.0
E   assert (63611.161382791 - 63549.279589625) < 10.0
==================== 2 failed, 3 passed in 75.96s (0:01:15) ====================
```

With the fix:

```text
$ pytest -q tests/test_tool_output_scan_bounds.py --durations=3   # (first version; now 10 tests, 10 passed in 0.88s)
0.34s call     tests/test_tool_output_scan_bounds.py::test_json_block_scans_are_bounded_on_unclosed_braces
0.02s call     tests/test_tool_output_scan_bounds.py::test_truncation_banner_matches_previous_regex
============================== 5 passed in 1.09s ===============================

$ pytest -q tests/test_tool_output_scan_bounds.py tests/test_mixed_content_scan_cache.py tests/test_mixed_content_sections.py tests/test_content_router_mixed_fence_placeholder.py
============================= 300 passed in 5.90s ==============================

$ pytest -q tests/test_tool_result_interceptors.py tests/test_proxy_compression_executor.py tests/test_subprocess_encoding.py tests/test_runtime_env.py tests/test_content_router*.py
============================= 247 passed in 32.58s =============================

$ ruff check / ruff format --check (0.17.3) on changed files: All checks passed
$ mypy headroom/proxy/interceptors/astgrep.py headroom/transforms/mixed_content.py --ignore-missing-imports
Success: no issues found in 2 source files
```

## Real Behavior Proof

- Environment: macOS (Apple silicon), Python 3.12 venv, this branch vs
`origin/main`.
- Exact command / steps: called `_has_valid_json_block_with_text` +
`split_into_sections` on 20,000 lines of `{`, and `_detect_truncation`
on `"[truncated: partial view " + "showing lines 1-10 of 50 total " *
12000`.
- Observed result: JSON scans about 62 s on main, 0.34 s here; banner
scan about 13 s on main, milliseconds here. The existing scan-cache
oracle tests (which compare against the original extractor) still pass.
- Not tested: end-to-end through the proxy; both functions are pure and
covered directly.

## Runtime Rollout Safety

- Rollout-managed feature(s): none
- Minimum rollout channel: n/a
- Stable/default behavior changed: no change in results (exact); only
time and memory bounds change
- Kill switch / disable path: none needed
- Unsafe override required: no
- Qualification impact: none
- Rollback path: revert this PR

## Review Readiness

- [x] I have performed a self-review
- [x] This PR is ready for human review

## Checklist

- [x] My code follows the project's style guidelines
- [x] I have performed a self-review of my code
- [x] I have commented my code, particularly in hard-to-understand areas
- [ ] I have made corresponding changes to the documentation — n/a
- [x] My changes generate no new warnings
- [x] I have added tests that prove my fix is effective or that my
feature works
- [x] New and existing unit tests pass locally with my changes
- [x] I did **not** edit `CHANGELOG.md` — it is generated by
release-please from my Conventional Commit PR title (a CI guard enforces
this)

## Additional Notes

Timings with the fix: 20,000 unclosed `{` lines take 0.13 s, the
crossed-count prefix repeated 130 times takes 0.23 s, 20,000 alternating
`{` / `}[` lines take 0.29 s, and 10,000 escaped-string line pairs take
0.14 s. With direct walking, the first takes about 62 s. Separately, on
main a balanced block nested about 10,000 deep makes `json.loads` raise
`RecursionError` in the gate; that is unchanged here.

Note: `tests/test_transforms_content_router.py` has 3 failures
(`test_json_in_html_preserves_records_and_markup`,
`test_embedded_json_mixed_tool_output_preserves_every_record[minify-*]`)
that also fail on unmodified `origin/main` in my environment, so they
are not caused by this change.

🤖 Generated with [Claude Code](https://claude.com/claude-code)

Reported by @JoaoMarcos44. Thank you for your contribution! 🩵

---------

Co-authored-by: Claude Opus 5.5 <noreply@anthropic.com>
Co-authored-by: JerrettDavis <mxjerrett@gmail.com>
2026-11-17 09:48:08 +05:30

149 lines
5.7 KiB
Python
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
"""Scans over tool output must stay linear on long unclosed shapes.
The timing bounds are loose (the old code took minutes at these sizes); the
oracle comparison checks the banner scan still finds exactly what it did.
"""
from __future__ import annotations
import random
import re
import time
import pytest
from headroom.proxy.interceptors.astgrep import (
_detect_truncation,
_is_plausible_truncation_range,
)
from headroom.transforms.mixed_content import (
ContentType,
_extract_json_block,
_has_valid_json_block_with_text,
_JsonBlockScanner,
split_into_sections,
)
_PREVIOUS_BANNER = re.compile(
r"\[\s*truncated\s*:\s*partial\s+view\b"
r"[^\[\]]*?"
r"showing\s+lines?\s+(?P<start_line>\d+)\s*[-–]\s*(?P<end_line>\d+)"
r"\s+of\s+(?P<total_lines>\d+)\s+total"
r"[^\[\]]*\]",
re.IGNORECASE,
)
def _previous_detect(source: str) -> tuple[int, int] | None:
count = len(source.splitlines())
for m in _PREVIOUS_BANNER.finditer(source):
s, e, t = (int(m.group(g)) for g in ("start_line", "end_line", "total_lines"))
if _is_plausible_truncation_range(s, e, t, count):
return e, t
return None
def test_truncation_banner_still_recognised() -> None:
src = (
"x\n" * 50 + "[Truncated: PARTIAL view -- a.py: showing lines 1-40 of 90 total (x). Read.]"
)
assert _detect_truncation(src) == (40, 90)
def test_truncation_banner_matches_previous_regex() -> None:
rng = random.Random(1234)
parts = [
"[truncated: partial view", "[ Truncated : PARTIAL view", "]", "[", "\n",
" showing lines 1-10 of 50 total ", "showing line 3–4 of 9 total", "showing lines 5-5 of 5 total",
"x", " ", "path.py:", "showing lines", "total", "12", "(more)",
] # fmt: skip
for _ in range(3000):
src = "".join(rng.choice(parts) for _ in range(rng.randint(1, 25)))
assert _detect_truncation(src) == _previous_detect(src), repr(src)
def test_truncation_scan_is_linear_on_unclosed_banner() -> None:
src = "[truncated: partial view " + "showing lines 1-10 of 50 total " * 12000
start = time.perf_counter()
assert _detect_truncation(src) is None
assert time.perf_counter() - start < 5.0
def test_json_block_scans_are_bounded_on_unclosed_braces() -> None:
content = "\n".join(["{"] * 20000)
start = time.perf_counter()
assert _has_valid_json_block_with_text(content) is False
sections = split_into_sections(content)
assert time.perf_counter() - start < 10.0
assert "\n".join(s.content for s in sections).count("{") == 20000
def test_long_json_block_inside_text_still_found() -> None:
body = ",\n".join(f' {{"k": {i}}}' for i in range(5000))
content = "log line\n[\n" + body + "\n]\ntrailing"
assert _has_valid_json_block_with_text(content) is True
types = [s.content_type for s in split_into_sections(content)]
assert ContentType.JSON_ARRAY in types
@pytest.mark.parametrize("unclosed", [150, 20000])
def test_json_object_after_many_unclosed_braces_keeps_its_own_section(unclosed: int) -> None:
obj = '{"critical": "disk full"}'
content = "\n".join(["{"] * unclosed + ["some prose"] * 6 + [obj, "more prose"])
assert _has_valid_json_block_with_text(content) is True
json_sections = [
s for s in split_into_sections(content) if s.content_type is ContentType.JSON_ARRAY
]
assert [s.content for s in json_sections] == [obj]
@pytest.mark.parametrize("repeats", [1, 130])
def test_json_object_after_crossed_count_prefix_keeps_its_own_section(repeats: int) -> None:
# Each count reaches zero on its own but never on the same line, so no
# early rejection applies; the object after it must still be found.
prefix = (["{"] * 150 + ["[" + "}" * 150]) * repeats
obj = '{"critical": "disk full"}'
content = "\n".join(prefix + ["some prose"] * 6 + [obj, "more prose"])
start = time.perf_counter()
assert _has_valid_json_block_with_text(content) is True
json_sections = [
s for s in split_into_sections(content) if s.content_type is ContentType.JSON_ARRAY
]
assert time.perf_counter() - start < 10.0
assert [s.content for s in json_sections] == [obj]
def test_block_scanner_matches_walking_each_candidate() -> None:
rng = random.Random(7)
parts = ["{", "}", "[", "]", '"', "\\\\", "a", " ", ",", "{}", "[]", '"x"', "}}", "]]", "{["]
parts += ['{"' + chr(92), '"' + chr(92)] # lines ending inside a string, escaped
for _ in range(3000):
lines = [
"".join(rng.choice(parts) for _ in range(rng.randint(0, 5)))
for _ in range(rng.randint(1, 25))
]
scanner = _JsonBlockScanner(lines)
scanner._direct_steps_left = 0 # answer every candidate from the sweep
for i, line in enumerate(lines):
if line.strip().startswith(("[", "{")):
assert scanner.extract(i) == _extract_json_block(lines, i), (lines, i)
@pytest.mark.parametrize("pairs", [100, 10000])
def test_json_object_after_escaped_string_lines_keeps_its_own_section(pairs: int) -> None:
# Lines ending inside a string with a trailing backslash put each walk in
# a different string state, so candidates start walks that only merge
# later; every one must still be answered.
obj = '{"critical": "disk full"}'
prefix_line = '{"' + chr(92)
content = "\n".join(
["{"] + [prefix_line, '"'] * pairs + ["some prose"] * 6 + [obj, "more prose"]
)
start = time.perf_counter()
assert _has_valid_json_block_with_text(content) is True
json_sections = [
s.content for s in split_into_sections(content) if s.content_type is ContentType.JSON_ARRAY
]
assert time.perf_counter() - start < 10.0
assert json_sections == [obj]