FA-79861 / Typography line breaking / Open access

Glue-set badness rating: badness ceiling · case 01

Extremely loose lines report badness far above the infinite-badness ceiling.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The computed badness is not clamped to 10000.

VERIFIED REPAIR

Clamp badness at 10000.

Unsuccessful approach: Clamping at 1000 truncates legitimately bad but finite ratings.

Case contract

Input [natural, stretch, shrink, width, tolerance] (ints). shortfall=width-natural. Positive shortfall with zero stretch is underfull 10000 very_loose; shrinking past total shrink is overfull 1000000 tight. r=shortfall/stretch (or /shrink when negative); badness=min(10000, floor(100*|r|^3+1/2)); fitness tight r<-1/2, decent r<=1/2, loose r<=1, else very_loose; status ok iff badness<=tolerance. Return [status, badness, fitness].

Why this case matters

Line breaking decides where paragraphs wrap on screen and in print; a wrong decision point shifts every following line.

1 / The failure

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    natural, stretch, shrink, width, tolerance = x
    shortfall = width - natural
    if shortfall > 0:
        if stretch == 0:
            return ['underfull', 10000, 'very_loose']
        r = Fraction(shortfall, stretch)
    elif shortfall < 0:
        if -shortfall > shrink:
            return ['overfull', 1000000, 'tight']
        r = Fraction(shortfall, shrink)
    else:
        r = Fraction(0)
    badness = min(10 ** 9, math.floor(100 * abs(r) ** 3 + Fraction(1, 2)))
    if r < Fraction(-1, 2):
        fitness = 'tight'
    elif r <= Fraction(1, 2):
        fitness = 'decent'
    elif r <= 1:
        fitness = 'loose'
    else:
        fitness = 'very_loose'
    status = 'ok' if badness <= tolerance else 'underfull'
    return [status, badness, fitness]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('badness cap at 10000', [100, 2, 0, 150, 200], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [71, 4, 1, 93, 200], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [109, 1, 11, 127, 1000], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [101, 3, 6, 123, 200], ['underfull', 10000, 'very_loose']), ('negative half ratio is decent', [100, 10, 6, 97, 200], ['ok', 13, 'decent']), ('very loose over tolerance', [100, 4, 0, 110, 200], ['underfull', 1563, 'very_loose']), ('control layout', [102, 20, 7, 125, 500], ['ok', 152, 'very_loose']), ('control layout', [107, 8, 3, 121, 500], ['underfull', 536, 'very_loose'])], [('regression: badness ceiling', [94, 3, 10, 118, 500], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [105, 1, 1, 120, 500], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [101, 3, 6, 123, 200], ['underfull', 10000, 'very_loose']), ('partial-repair probe', [69, 6, 6, 85, 150], ['underfull', 1896, 'very_loose']), ('one unit past total shrink', [100, 10, 5, 94, 200], ['overfull', 1000000, 'tight']), ('half stretch ratio rounds 12.5 up', [100, 10, 5, 105, 200], ['ok', 13, 'decent']), ('control layout', [75, 12, 4, 93, 100], ['underfull', 338, 'very_loose']), ('control layout', [80, 12, 4, 75, 1000], ['overfull', 1000000, 'tight'])], [('regression: badness ceiling', [96, 1, 0, 119, 150], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [109, 1, 11, 127, 1000], ['underfull', 10000, 'very_loose']), ('very loose over tolerance', [100, 4, 0, 110, 200], ['underfull', 1563, 'very_loose']), ('regression: badness ceiling', [101, 3, 6, 123, 200], ['underfull', 10000, 'very_loose']), ('negative half ratio is decent', [100, 10, 6, 97, 200], ['ok', 13, 'decent']), ('one unit past total shrink', [100, 10, 5, 94, 200], ['overfull', 1000000, 'tight']), ('control layout', [91, 16, 1, 85, 150], ['overfull', 1000000, 'tight']), ('control layout', [62, 4, 4, 58, 200], ['ok', 100, 'tight'])], [('regression: badness ceiling', [106, 3, 3, 126, 100], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [111, 1, 3, 129, 500], ['underfull', 10000, 'very_loose']), ('partial-repair probe', [109, 10, 12, 132, 200], ['underfull', 1217, 'very_loose']), ('regression: badness ceiling', [85, 1, 12, 100, 500], ['underfull', 10000, 'very_loose']), ('rigid line with slack', [100, 0, 5, 110, 200], ['underfull', 10000, 'very_loose']), ('exact natural width', [100, 10, 5, 100, 200], ['ok', 0, 'decent']), ('control layout', [101, 2, 2, 93, 1000], ['overfull', 1000000, 'tight']), ('control layout', [62, 2, 9, 66, 200], ['underfull', 800, 'very_loose'])], [('regression: badness ceiling', [91, 4, 7, 115, 500], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [119, 2, 6, 138, 500], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [60, 2, 12, 73, 500], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [79, 2, 6, 95, 200], ['underfull', 10000, 'very_loose']), ('exact natural width', [100, 10, 5, 100, 200], ['ok', 0, 'decent']), ('very loose over tolerance', [100, 4, 0, 110, 200], ['underfull', 1563, 'very_loose']), ('control layout', [99, 16, 2, 111, 1000], ['ok', 42, 'loose']), ('control layout', [85, 1, 11, 80, 200], ['ok', 9, 'decent'])]]
for label, args, expected in fixtures[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
badness cap at 10000	`['underfull', 1562500, 'very_loose']`	`['underfull', 10000, 'very_loose']`	Failed
regression: badness ceiling	`['underfull', 16638, 'very_loose']`	`['underfull', 10000, 'very_loose']`	Failed
regression: badness ceiling	`['underfull', 583200, 'very_loose']`	`['underfull', 10000, 'very_loose']`	Failed
regression: badness ceiling	`['underfull', 39437, 'very_loose']`	`['underfull', 10000, 'very_loose']`	Failed
negative half ratio is decent	`['ok', 13, 'decent']`	`['ok', 13, 'decent']`	Passed
very loose over tolerance	`['underfull', 1563, 'very_loose']`	`['underfull', 1563, 'very_loose']`	Passed
control layout	`['ok', 152, 'very_loose']`	`['ok', 152, 'very_loose']`	Passed
control layout	`['underfull', 536, 'very_loose']`	`['underfull', 536, 'very_loose']`	Passed

SHA-256 / 8e78b8810fe95eb63b8615a6ecfe5b3475b1e2b1aee33a4517fd3c8f345dc817

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    natural, stretch, shrink, width, tolerance = x
    shortfall = width - natural
    if shortfall > 0:
        if stretch == 0:
            return ['underfull', 10000, 'very_loose']
        r = Fraction(shortfall, stretch)
    elif shortfall < 0:
        if -shortfall > shrink:
            return ['overfull', 1000000, 'tight']
        r = Fraction(shortfall, shrink)
    else:
        r = Fraction(0)
    badness = min(1000, math.floor(100 * abs(r) ** 3 + Fraction(1, 2)))
    if r < Fraction(-1, 2):
        fitness = 'tight'
    elif r <= Fraction(1, 2):
        fitness = 'decent'
    elif r <= 1:
        fitness = 'loose'
    else:
        fitness = 'very_loose'
    status = 'ok' if badness <= tolerance else 'underfull'
    return [status, badness, fitness]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('badness cap at 10000', [100, 2, 0, 150, 200], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [71, 4, 1, 93, 200], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [109, 1, 11, 127, 1000], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [101, 3, 6, 123, 200], ['underfull', 10000, 'very_loose']), ('negative half ratio is decent', [100, 10, 6, 97, 200], ['ok', 13, 'decent']), ('very loose over tolerance', [100, 4, 0, 110, 200], ['underfull', 1563, 'very_loose']), ('control layout', [102, 20, 7, 125, 500], ['ok', 152, 'very_loose']), ('control layout', [107, 8, 3, 121, 500], ['underfull', 536, 'very_loose'])], [('regression: badness ceiling', [94, 3, 10, 118, 500], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [105, 1, 1, 120, 500], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [101, 3, 6, 123, 200], ['underfull', 10000, 'very_loose']), ('partial-repair probe', [69, 6, 6, 85, 150], ['underfull', 1896, 'very_loose']), ('one unit past total shrink', [100, 10, 5, 94, 200], ['overfull', 1000000, 'tight']), ('half stretch ratio rounds 12.5 up', [100, 10, 5, 105, 200], ['ok', 13, 'decent']), ('control layout', [75, 12, 4, 93, 100], ['underfull', 338, 'very_loose']), ('control layout', [80, 12, 4, 75, 1000], ['overfull', 1000000, 'tight'])], [('regression: badness ceiling', [96, 1, 0, 119, 150], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [109, 1, 11, 127, 1000], ['underfull', 10000, 'very_loose']), ('very loose over tolerance', [100, 4, 0, 110, 200], ['underfull', 1563, 'very_loose']), ('regression: badness ceiling', [101, 3, 6, 123, 200], ['underfull', 10000, 'very_loose']), ('negative half ratio is decent', [100, 10, 6, 97, 200], ['ok', 13, 'decent']), ('one unit past total shrink', [100, 10, 5, 94, 200], ['overfull', 1000000, 'tight']), ('control layout', [91, 16, 1, 85, 150], ['overfull', 1000000, 'tight']), ('control layout', [62, 4, 4, 58, 200], ['ok', 100, 'tight'])], [('regression: badness ceiling', [106, 3, 3, 126, 100], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [111, 1, 3, 129, 500], ['underfull', 10000, 'very_loose']), ('partial-repair probe', [109, 10, 12, 132, 200], ['underfull', 1217, 'very_loose']), ('regression: badness ceiling', [85, 1, 12, 100, 500], ['underfull', 10000, 'very_loose']), ('rigid line with slack', [100, 0, 5, 110, 200], ['underfull', 10000, 'very_loose']), ('exact natural width', [100, 10, 5, 100, 200], ['ok', 0, 'decent']), ('control layout', [101, 2, 2, 93, 1000], ['overfull', 1000000, 'tight']), ('control layout', [62, 2, 9, 66, 200], ['underfull', 800, 'very_loose'])], [('regression: badness ceiling', [91, 4, 7, 115, 500], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [119, 2, 6, 138, 500], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [60, 2, 12, 73, 500], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [79, 2, 6, 95, 200], ['underfull', 10000, 'very_loose']), ('exact natural width', [100, 10, 5, 100, 200], ['ok', 0, 'decent']), ('very loose over tolerance', [100, 4, 0, 110, 200], ['underfull', 1563, 'very_loose']), ('control layout', [99, 16, 2, 111, 1000], ['ok', 42, 'loose']), ('control layout', [85, 1, 11, 80, 200], ['ok', 9, 'decent'])]]
for label, args, expected in fixtures[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
badness cap at 10000	`['underfull', 1000, 'very_loose']`	`['underfull', 10000, 'very_loose']`	Failed
regression: badness ceiling	`['underfull', 1000, 'very_loose']`	`['underfull', 10000, 'very_loose']`	Failed
regression: badness ceiling	`['ok', 1000, 'very_loose']`	`['underfull', 10000, 'very_loose']`	Failed
regression: badness ceiling	`['underfull', 1000, 'very_loose']`	`['underfull', 10000, 'very_loose']`	Failed
negative half ratio is decent	`['ok', 13, 'decent']`	`['ok', 13, 'decent']`	Passed
very loose over tolerance	`['underfull', 1000, 'very_loose']`	`['underfull', 1563, 'very_loose']`	Failed
control layout	`['ok', 152, 'very_loose']`	`['ok', 152, 'very_loose']`	Passed
control layout	`['underfull', 536, 'very_loose']`	`['underfull', 536, 'very_loose']`	Passed

SHA-256 / 461bb5c45b58c189d6109616bc2e40304c1b57092b6d7f9991cec7807bf1c3df

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    natural, stretch, shrink, width, tolerance = x
    shortfall = width - natural
    if shortfall > 0:
        if stretch == 0:
            return ['underfull', 10000, 'very_loose']
        r = Fraction(shortfall, stretch)
    elif shortfall < 0:
        if -shortfall > shrink:
            return ['overfull', 1000000, 'tight']
        r = Fraction(shortfall, shrink)
    else:
        r = Fraction(0)
    badness = min(10000, math.floor(100 * abs(r) ** 3 + Fraction(1, 2)))
    if r < Fraction(-1, 2):
        fitness = 'tight'
    elif r <= Fraction(1, 2):
        fitness = 'decent'
    elif r <= 1:
        fitness = 'loose'
    else:
        fitness = 'very_loose'
    status = 'ok' if badness <= tolerance else 'underfull'
    return [status, badness, fitness]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('badness cap at 10000', [100, 2, 0, 150, 200], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [71, 4, 1, 93, 200], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [109, 1, 11, 127, 1000], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [101, 3, 6, 123, 200], ['underfull', 10000, 'very_loose']), ('negative half ratio is decent', [100, 10, 6, 97, 200], ['ok', 13, 'decent']), ('very loose over tolerance', [100, 4, 0, 110, 200], ['underfull', 1563, 'very_loose']), ('control layout', [102, 20, 7, 125, 500], ['ok', 152, 'very_loose']), ('control layout', [107, 8, 3, 121, 500], ['underfull', 536, 'very_loose'])], [('regression: badness ceiling', [94, 3, 10, 118, 500], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [105, 1, 1, 120, 500], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [101, 3, 6, 123, 200], ['underfull', 10000, 'very_loose']), ('partial-repair probe', [69, 6, 6, 85, 150], ['underfull', 1896, 'very_loose']), ('one unit past total shrink', [100, 10, 5, 94, 200], ['overfull', 1000000, 'tight']), ('half stretch ratio rounds 12.5 up', [100, 10, 5, 105, 200], ['ok', 13, 'decent']), ('control layout', [75, 12, 4, 93, 100], ['underfull', 338, 'very_loose']), ('control layout', [80, 12, 4, 75, 1000], ['overfull', 1000000, 'tight'])], [('regression: badness ceiling', [96, 1, 0, 119, 150], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [109, 1, 11, 127, 1000], ['underfull', 10000, 'very_loose']), ('very loose over tolerance', [100, 4, 0, 110, 200], ['underfull', 1563, 'very_loose']), ('regression: badness ceiling', [101, 3, 6, 123, 200], ['underfull', 10000, 'very_loose']), ('negative half ratio is decent', [100, 10, 6, 97, 200], ['ok', 13, 'decent']), ('one unit past total shrink', [100, 10, 5, 94, 200], ['overfull', 1000000, 'tight']), ('control layout', [91, 16, 1, 85, 150], ['overfull', 1000000, 'tight']), ('control layout', [62, 4, 4, 58, 200], ['ok', 100, 'tight'])], [('regression: badness ceiling', [106, 3, 3, 126, 100], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [111, 1, 3, 129, 500], ['underfull', 10000, 'very_loose']), ('partial-repair probe', [109, 10, 12, 132, 200], ['underfull', 1217, 'very_loose']), ('regression: badness ceiling', [85, 1, 12, 100, 500], ['underfull', 10000, 'very_loose']), ('rigid line with slack', [100, 0, 5, 110, 200], ['underfull', 10000, 'very_loose']), ('exact natural width', [100, 10, 5, 100, 200], ['ok', 0, 'decent']), ('control layout', [101, 2, 2, 93, 1000], ['overfull', 1000000, 'tight']), ('control layout', [62, 2, 9, 66, 200], ['underfull', 800, 'very_loose'])], [('regression: badness ceiling', [91, 4, 7, 115, 500], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [119, 2, 6, 138, 500], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [60, 2, 12, 73, 500], ['underfull', 10000, 'very_loose']), ('regression: badness ceiling', [79, 2, 6, 95, 200], ['underfull', 10000, 'very_loose']), ('exact natural width', [100, 10, 5, 100, 200], ['ok', 0, 'decent']), ('very loose over tolerance', [100, 4, 0, 110, 200], ['underfull', 1563, 'very_loose']), ('control layout', [99, 16, 2, 111, 1000], ['ok', 42, 'loose']), ('control layout', [85, 1, 11, 80, 200], ['ok', 9, 'decent'])]]
for label, args, expected in fixtures[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
badness cap at 10000	`['underfull', 10000, 'very_loose']`	`['underfull', 10000, 'very_loose']`	Passed
regression: badness ceiling	`['underfull', 10000, 'very_loose']`	`['underfull', 10000, 'very_loose']`	Passed
regression: badness ceiling	`['underfull', 10000, 'very_loose']`	`['underfull', 10000, 'very_loose']`	Passed
regression: badness ceiling	`['underfull', 10000, 'very_loose']`	`['underfull', 10000, 'very_loose']`	Passed
negative half ratio is decent	`['ok', 13, 'decent']`	`['ok', 13, 'decent']`	Passed
very loose over tolerance	`['underfull', 1563, 'very_loose']`	`['underfull', 1563, 'very_loose']`	Passed
control layout	`['ok', 152, 'very_loose']`	`['ok', 152, 'very_loose']`	Passed
control layout	`['underfull', 536, 'very_loose']`	`['underfull', 536, 'very_loose']`	Passed

SHA-256 / c5289c67479c5828c3051825906b25419cb3dd91edd2d9720bf4e95bfbc09de0

Verification & scope

A deterministic toy typesetting model with integer widths and a stipulated rule set; it does not claim conformance to any engine. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:49:48.293746+00:00.

Case digest / 9a31f59deddde6450258105075e134032b33740a5c4fbd515d5f7a4ffe1f4eec