Breakwater

Sandboxes / #1030

perf: translate for canonicalize_name

pypa/packaging#1030 · merged 2026-01-05 · base 52e57f2003 → head 3803ce341b · ran on Sandboxes

BLOCK

At least one behaviour change looks like an unintended regression. The “faster” code does up to 7× the work on valid inputs, growing with input size (complexity regression).

Known regressions in this PR

Counterexamples · 2 groups of 7 classes: 7 likely bug

P1

Output changed

known regression: unicode-lowercase
inputcanonicalize_name("İ")
basevalue: "i̇"
headvalue: "İ"
Likely bugvotes: 2 likely-bug, 1 intended

The PR is described as a performance refactor with no intention to change Unicode handling. The new code replaces Unicode‑aware `.lower()` with an ASCII‑only translation table, causing non‑ASCII letters like “İ” to remain uppercase. This is an unintended regression.

# About 2x faster, safe since packages only support alphanumeric characters
# Emulates ``re.sub(r

Found by: Nemotron strategy search, Ultra's planned example, hostile mutation, search sample · also caught by: Plain Hypothesis, Mutations of the PR's own test strings, Nemotron plan only

ran onToken Factory Sandboxes · image a2d83f6b-ca9d-4fca-95ce-558082aac714

Regression test verified passes on base, fails on head
def test_1030_p1_value_0():
    """Breakwater P1: base behaviour pinned (found by differential testing; label: likely-bug)."""
    from packaging.utils import canonicalize_name
    assert canonicalize_name('İ') == 'i̇'
Reproduce
uv run breakwater probe --repo https://github.com/pypa/packaging --base 52e57f20037f --head 3803ce341b59 --target packaging.utils:canonicalize_name --backend contree --input "İ"
2 near-duplicate classes same behaviour, inputs with extra traits
  • canonicalize_name("İ ") base value: "i̇ " · head value: "İ "unicode-lowercase test verified
  • canonicalize_name("İ\u0000") base value: "i̇\u0000" · head value: "İ\u0000"unicode-lowercase test verified
P3

Equality / ordering changed

acanonicalize_name("Ω")
bcanonicalize_name("ẞ")
basea > b → True
heada > b → False
Likely bugvotes: 2 likely-bug, 1 intended

Same as C4 – the new ASCII‑only mapping flips the relative order of “Ω” and “ẞ”. This is an unintended side‑effect of the performance rewrite.

# About 2x faster, safe since packages only support alphanumeric characters
# Emulates ``re.sub(r

Found by: Ultra's planned example, relations pass · also caught by: Nemotron plan only

ran onToken Factory Sandboxes · image a2d83f6b-ca9d-4fca-95ce-558082aac714

Regression test verified passes on base, fails on head
def test_1030_p3_gt_4():
    """Breakwater P3: base behaviour pinned (found by differential testing; label: likely-bug)."""
    from packaging.utils import canonicalize_name
    a = canonicalize_name('Ω')
    b = canonicalize_name('ẞ')
    assert (a > b) is True
3 near-duplicate relation flipes same behaviour, inputs with extra traits
  • canonicalize_name("Ω") vs canonicalize_name("ẞ") base a < b → False · head a < b → True test verified
  • canonicalize_name("İ") vs canonicalize_name("ÖÄ") base a > b → False · head a > b → True test verified
  • canonicalize_name("İ") vs canonicalize_name("ÖÄ") base a < b → True · head a < b → False test verified

Regression tests

7 of 7 classes have a generated pytest that pins the old behaviour. Each passed on the base commit and failed on the head commit in the sandbox before it was offered.

Download test_1030.py

Performance · canonicalize_name

Worst family with mostly valid inputs: 6.50× the instructions of base (leading_and_alternating_pattern).

head slowerhead faster0.031×0.062×0.12×0.25×0.5×1×2×4×101001,000input size (characters)R1R1: 1.39× at ~12 charsR1: 1.39× at ~12 charsR1: 2.46× at ~24 charsR1: 2.38× at ~72 charsR1: 0.90× at ~264 charsR1: 0.37× at ~1,032 charsR1: 0.21× at ~4,104 charsR2.2R2.2: 1.60× at ~14 charsR2.2: 1.68× at ~18 charsR2.2: 2.45× at ~42 charsR2.2: 3.81× at ~138 charsR2.2: 5.38× at ~522 charsR2.2: 6.14× at ~2,058 charsR2.2: 6.50× at ~8,202 charsR2R2: 1.10× at ~8 charsR2: 1.38× at ~12 charsR2: 2.19× at ~36 charsR2: 3.64× at ~132 charsR2: 5.32× at ~516 charsR2: 6.12× at ~2,052 charsR2: 6.50× at ~8,196 charsF4F4: 1.30× at ~9 charsF4: 1.48× at ~11 charsF4: 1.96× at ~23 charsF4: 2.76× at ~71 charsF4: 3.97× at ~263 charsF4: 4.86× at ~1,031 charsF4: 5.24× at ~4,103 charsF2F2: 0.80× at ~7 charsF2: 0.55× at ~11 charsF2: 0.20× at ~35 charsF2: 0.08× at ~131 charsF2: 0.04× at ~515 charsF2: 0.03× at ~2,051 charsF2: 0.03× at ~8,195 chars
  • R1
  • R2.2
  • R2
  • F4
  • F2
Head/base cachegrind instructions per call, by input size (log-log). Each line is one input family Nemotron proposed; points above 1× are where the "faster" code does more work.
FamilyInputsRatio range Slope base → headVerdict
R1Names starting/ending with multiple dots or underscoresclaimed speedup · archive0.21× – 2.46×0.85 → 0.49slower
R2.2leading_and_alternating_patternsuspected slowdown · expand:R21.60× – 6.50×0.56 → 0.79complexity-regression
R2many_underscores_and_dotssuspected slowdown · archive1.10× – 6.50×0.52 → 0.78complexity-regression
F4A long run of '_' (or '.') characters becomes a long run of '-' after translation. The while‑loop collapses '--' by repeatedly replacing non‑overlapping pairs, suspected slowdown · plan1.30× – 5.24×0.46 → 0.70complexity-regression
F2Typical distribution names consist of alphanumerics and single hyphens. The new translate+single-pass replace avoids the regex engine and is ~2× faster on theseclaimed speedup · plan0.03× – 0.80×0.96 → 0.46faster

Receipt

TargetBackendImageRun AuditAdjudication
packaging.utils:canonicalize_nameToken Factory Sandboxesa2d83f6b-ca9d-4fca-95ce-558082aac714bt-1030-f3ff10$0.048$0.018

Nemotron cost on Nebius Token Factory. Backend: where the untrusted code ran. Token Factory Sandboxes (a microVM branched from a kept image, cited by its UUID). Every image is content-addressed (repo at each commit + harness), so every card re-runs from the image and seed 0. Raw data: audit, adjudication.