# Capability Spec Delta: emblem-solver (emblem-solver) **Package**: `@suaveplan/emblem-solver` **Status**: PROPOSED > Every requirement below carries a `**Verified by:**` line at authoring time. No exceptions. ## ADDED Requirements ### Requirement: Stable error code registry The package SHALL expose `EMBLEM_SOLVER_CODES` created via `defineCodes("EMBLEM_SOLVER", [...] as const)` containing exactly the codes `INVALID_GRID`, `INVALID_OPTIONS`, `INVALID_PIXEL`. The registry MUST be frozen and each value MUST be the namespaced string (`EMBLEM_SOLVER.INVALID_GRID`, …). #### Scenario: registry shape is frozen - **WHEN** a consumer reads `EMBLEM_SOLVER_CODES` - **THEN** the returned object MUST contain all three expected keys with namespaced string values and MUST be `Object.isFrozen`. **Verified by:** `src/errors/errors.test.ts::"EMBLEM_SOLVER_CODES exposes all three codes"` --- ### Requirement: EmblemSolverError extends SuaveplanError The package SHALL export `EmblemSolverError extends SuaveplanError`. Constructing `new EmblemSolverError(EMBLEM_SOLVER_CODES.INVALID_GRID, "msg")` MUST yield an instance whose `.code === "EMBLEM_SOLVER.INVALID_GRID"`, whose `.message === "msg"`, and which satisfies `instanceof EmblemSolverError` AND `instanceof Error`. A `cause` passed in options MUST be preserved. #### Scenario: round-trips through cause chain - **WHEN** an `EmblemSolverError` is constructed with `cause: new Error("inner")` - **THEN** `error.cause` MUST return the original error and `error.code` MUST preserve the namespaced code. **Verified by:** `src/errors/errors.test.ts::"EmblemSolverError preserves code and cause"` --- ### Requirement: ConvertOptions Zod validation The package SHALL expose `ConvertOptionsSchema` (Zod) accepting `layerOrder` (enum: `auto | area-desc | area-asc | island-aware | perimeter-desc`, default `auto`), `maxPermutations` (integer ≥ 1, default `40320`), and optional `rng` (`() => number`). The schema MUST reject unknown keys (strict). `convert()` MUST call `safeParse` and on failure throw `EmblemSolverError(INVALID_OPTIONS)` whose message embeds the Zod issue list. #### Scenario: rejects unknown option - **WHEN** `convert(pixels, w, h, { wibble: 1 } as never)` is invoked - **THEN** the call MUST throw `EmblemSolverError` whose `.code` equals `EMBLEM_SOLVER.INVALID_OPTIONS`. #### Scenario: rejects non-positive maxPermutations - **WHEN** `convert(pixels, w, h, { maxPermutations: 0 })` is invoked - **THEN** the call MUST throw `EmblemSolverError(INVALID_OPTIONS)`. **Verified by:** `src/schemas/schemas.test.ts::"ConvertOptionsSchema rejects unknown keys"` AND `src/converter/converter.test.ts::"throws INVALID_OPTIONS on bad option"` --- ### Requirement: Grid input validation The `convert()` entry point SHALL throw `EmblemSolverError(EMBLEM_SOLVER_CODES.INVALID_GRID)` when `width ≤ 0`, `height ≤ 0`, or `pixels.length !== width * height`. The `parseRGBABuffer()` entry point SHALL throw the same error when the supplied `Uint8Array` length is not exactly `width * height * 4`. #### Scenario: width/height mismatch - **WHEN** `convert([], 2, 2)` is invoked with empty pixels - **THEN** the call MUST throw `EmblemSolverError` whose `.code` equals `EMBLEM_SOLVER.INVALID_GRID`. #### Scenario: buffer length mismatch - **WHEN** `parseRGBABuffer(new Uint8Array(3), 2, 2)` is invoked - **THEN** the call MUST throw `EmblemSolverError(INVALID_GRID)`. **Verified by:** `src/converter/converter.test.ts::"throws INVALID_GRID on dimension mismatch"` AND `src/io/parse/parse.test.ts::"throws INVALID_GRID on buffer length mismatch"` --- ### Requirement: Public type surface The package SHALL export the following types verbatim from the package root: `RGBA`, `Rect`, `Island`, `ColourAnalysis`, `ColourLayer`, `ConvertOptions`, `ConvertResult`, `GridAnalysis`, `Rng`, `EmblemSolverCode`. The shapes MUST match the upstream contract (`RGBA.a: 0 | 1`, `Rect: {x,y,w,h}`, `Island.pixels: Set`, `ColourAnalysis` includes `density`/`fragmentation`/`bounds`/`islands`). #### Scenario: type re-exports are present - **WHEN** a TypeScript consumer imports the type set above - **THEN** type-checking MUST succeed against the documented shapes. **Verified by:** `src/types/types.md` AND `src/converter/converter.test.ts::"ConvertResult exposes all documented fields"` --- ### Requirement: Pixel-grid analysis with 4-connected islands The package SHALL expose `analyseGrid(pixels, width, height)` which produces a `GridAnalysis` containing `width`, `height`, `opaquePixels` (a `Set` of packed indices), `colourGroups` (a `Map>` keyed by `"r,g,b"`), and `colourAnalysis` (a `Map`) where each entry reports `totalPixels`, `bounds`, `density = pixels / bbox area`, `fragmentation = islands / pixels`, and the full `islands` list discovered via 4-connected BFS flood-fill. #### Scenario: detects two disjoint islands - **WHEN** `analyseGrid` runs on a grid where one colour appears in two blocks separated by transparency - **THEN** that colour's `islands.length` MUST equal `2`. #### Scenario: diagonals are not connected - **WHEN** `analyseGrid` runs on a `[[1,0],[0,1]]` grid - **THEN** the only colour's `islands.length` MUST equal `2`. **Verified by:** `src/grid/analyse/analyse.test.ts::"detects two islands separated by transparency"` AND `src/grid/analyse/analyse.test.ts::"treats diagonal pixels as separate islands (4-connected)"` --- ### Requirement: RGBA buffer + indexed grid IO The package SHALL expose `parseRGBABuffer(buf, w, h)` returning `RGBA[]` of length `w*h` where `a` is quantised to `0 | 1` at the threshold `byte ≥ 128`. It SHALL also expose `fromIndexedGrid(grid, palette)` returning `{ pixels, width, height }` from a `number[][]` palette map. Index `0` MUST map to a fully-transparent pixel (`a === 0`). Indices not present in the palette MUST also produce a transparent pixel. #### Scenario: alpha quantisation rounds half-up - **WHEN** `parseRGBABuffer` reads a byte with `a = 128` - **THEN** the resulting `RGBA.a` MUST equal `1`; for `a = 127` it MUST be `0`. #### Scenario: indexed grid maps palette correctly - **WHEN** `fromIndexedGrid([[1,0],[0,2]], {1:r, 2:g})` is called - **THEN** result `pixels[0]` MUST be the `r`-colour with `a===1`, `pixels[1]` MUST be transparent, and `pixels[3]` MUST be the `g`-colour. **Verified by:** `src/io/parse/parse.test.ts::"parseRGBABuffer quantises alpha"` AND `src/io/parse/parse.test.ts::"fromIndexedGrid maps palette indices to RGBA pixels"` --- ### Requirement: Dual-axis histogram maximal-rectangles The package SHALL expose a `dualAxisMaximalRects(available, rows, cols)` solver that enumerates every distinct maximal-rectangle candidate in the opaque-pixel grid by combining a normal histogram sweep and a transposed sweep. Duplicates MUST be deduplicated by their `(x,y,w,h)` key. #### Scenario: solid 3x3 produces the full rect - **WHEN** the input is a 3×3 all-`true` grid - **THEN** the returned set MUST include `{x:0,y:0,w:3,h:3}`. **Verified by:** `src/solver/histogram/histogram.test.ts::"includes the full grid rect for a solid grid"` --- ### Requirement: Strip decomposition picks the smaller axis The package SHALL expose `stripDecomposition(required, rows, cols)` that computes maximal horizontal strips (and the transposed vertical variant) where same-extent + adjacent runs merge, and returns whichever orientation yields fewer rects. #### Scenario: tall vertical strip beats horizontal runs - **WHEN** the required mask is a single column of height `5` - **THEN** the returned strips MUST contain exactly one rect of width `1` and height `5`. **Verified by:** `src/solver/strip/strip.test.ts::"single column produces one vertical strip"` --- ### Requirement: Enhanced greedy set-cover with three-key tiebreak The package SHALL expose `enhancedGreedyCover(candidates, required, w, h)` that selects rects to cover the required mask using a deterministic score of `covered*1000 + efficiency*100 + proximity*10`. When no rect overlaps the remaining uncovered pixels, the function MUST fall back to emitting 1×1 rects for the residual. #### Scenario: empty required returns no rects - **WHEN** all entries of `required` are `false` - **THEN** `enhancedGreedyCover` MUST return an empty array. **Verified by:** `src/solver/greedy/greedy.test.ts::"returns empty array when nothing is required"` --- ### Requirement: Per-island independent cover The package SHALL expose `perIslandCover(islands, candidates, w, h)` that runs `enhancedGreedyCover` independently on each island's local required mask, restricting candidates to those that touch the island. #### Scenario: independent covers don't span islands - **WHEN** two 2×2 islands are separated by transparency - **THEN** `perIslandCover` MUST produce at least two rects, one per island, and no rect MUST span the transparent gap. **Verified by:** `src/solver/greedy/greedy.test.ts::"covers two islands without spanning the gap"` --- ### Requirement: Layer-ordering search The package SHALL expose `getStaticOrdering(analysis, strategy)` for the strategies `area-desc`, `area-asc`, `island-aware`, `perimeter-desc`, and `permutations(arr)` implementing Heap's algorithm yielding `n!` permutations including the identity, and `factorial(n)` returning the mathematical factorial with `factorial(0) === factorial(1) === 1`. #### Scenario: permutations yields n! arrays in total - **WHEN** `permutations(["a","b","c"])` is fully iterated - **THEN** the iteration MUST emit exactly `6` arrays. #### Scenario: factorial agrees with the definition - **WHEN** `factorial(5)` is called - **THEN** the return value MUST equal `120`. **Verified by:** `src/solver/ordering/ordering.test.ts::"permutations yields n! arrays"` AND `src/solver/ordering/ordering.test.ts::"factorial matches the standard definition"` --- ### Requirement: Multi-strategy layer processor The package SHALL expose `processLayerMultiStrategy(key, ownPixels, analysis, earlierPixels)` that runs the four covering strategies (dual-axis-histogram + greedy, per-island, strip decomposition where it fully covers, and a merge pass on the best so far) and returns the rect list with the smallest cardinality. #### Scenario: returns a valid cover - **WHEN** the layer processor runs on the upstream `cross3x3` fixture's red pixels - **THEN** the returned rect list MUST cover every required red pixel and MUST contain at most `2` rects. **Verified by:** `src/solver/layer/layer.test.ts::"cross3x3 produces at most 2 rects"` --- ### Requirement: Adjacent-rect merge optimisation The package SHALL expose `mergeAdjacentRects(rects, available)` which combines edge-sharing same-extent rect pairs into a single larger rect provided the merged span is fully `available`. The function MUST iterate until no further merge is possible. #### Scenario: two adjacent unit squares merge - **WHEN** `mergeAdjacentRects([{0,0,1,1},{1,0,1,1}], all-available)` runs - **THEN** the output MUST be exactly `[{0,0,2,1}]`. **Verified by:** `src/optimizer/merge/merge.test.ts::"merges two horizontally adjacent unit squares"` --- ### Requirement: Overlap optimiser The package SHALL expose `optimiseOverlap(rects, required, available, rows, cols)` that (1) merges pairs whose bbox is fully available and whose union covers no more than the original required pixels, (2) extends a rect to subsume another while remaining inside `available`, and (3) replaces a triple of rects with a 2-rect cross/T/L pattern when one exists. #### Scenario: cross 3x3 reduces to two rects - **WHEN** `convert` runs on the upstream `cross3x3` fixture - **THEN** `ConvertResult.totalRects` MUST be at most `2`. **Verified by:** `src/optimizer/overlap/overlap.test.ts::"reduces a 3-rect L to 2 rects"` AND `src/converter/converter.test.ts::"cross 3x3 reduces to <=2 rects"` --- ### Requirement: Cross-layer redundancy elimination The package SHALL expose `eliminateRedundant(layers, width, height)` which, given a list of `ColourLayer` objects, removes any rect whose pixels are either fully occluded by higher-z layers (of any colour) or already covered by sibling rects in the same layer. #### Scenario: fully-occluded rect is removed - **WHEN** layer 0 contains a 4×4 red rect at (0,0) and layer 1 contains a 4×4 blue rect at (0,0) - **THEN** after `eliminateRedundant` layer 0 MUST have zero rects. **Verified by:** `src/optimizer/redundancy/redundancy.test.ts::"removes a fully-occluded rect"` --- ### Requirement: SVG emission The package SHALL expose `buildSVG(layers, width, height)` returning a string that begins with ``, contains one `` per layer-rect with `fill="rgb(r,g,b)"`, and renders layers in `zIndex` ascending order. #### Scenario: empty layer list produces an empty viewBox svg - **WHEN** `buildSVG([], 4, 4)` is invoked - **THEN** the result MUST contain `viewBox="0 0 4 4"` and zero `` tags. **Verified by:** `src/svg/build/build.test.ts::"empty layers yields a rect-free svg"` --- ### Requirement: Public `convert()` orchestrator The package SHALL expose `convert(pixels, width, height, options?)`. The function MUST (1) parse `options` via `ConvertOptionsSchema`, (2) call `analyseGrid`, (3) early-return an empty result for fully-transparent input, (4) explore orderings (exhaustive for `colourCount! ≤ maxPermutations`; heuristics + ≤ 1000 RNG-driven samples otherwise), (5) pick the ordering with the smallest `totalRects`, (6) emit the SVG via `buildSVG`, and (7) return `{ svg, layers, totalRects, naiveRects, ratio, orderingUsed, orderingsEvaluated, colourAnalysis }`. #### Scenario: chessboard 8x8 ≤ 33 rects - **WHEN** `convert` runs on the upstream `chessboard8x8` fixture - **THEN** `result.totalRects ≤ 33`. #### Scenario: solid grid produces exactly one rect - **WHEN** `convert` runs on a 4×4 solid-red grid - **THEN** `result.totalRects === 1`. #### Scenario: fully transparent grid produces zero rects - **WHEN** `convert` runs on a 4×4 fully-transparent grid - **THEN** `result.totalRects === 0` and `result.layers` MUST be empty. #### Scenario: shield emblem 32x32 compresses > 50x - **WHEN** `convert` runs on the upstream `shieldEmblem32` fixture - **THEN** `result.ratio > 50`. **Verified by:** `src/converter/converter.test.ts::"chessboard 8x8: ≤33 rects"` AND `src/converter/converter.test.ts::"solid colour 4x4 = 1 rect"` AND `src/converter/converter.test.ts::"fully transparent = 0 rects"` AND `src/converter/converter.test.ts::"shield emblem 32x32 ratio > 50"` --- ### Requirement: Injectable Rng for deterministic auto-ordering `convert()` SHALL accept an optional `rng: () => number` in its options. The heuristics-plus-sampling branch (entered when `colourCount! > maxPermutations`) MUST consume the injected `rng` for every Fisher–Yates shuffle step, falling back to `Math.random` only when no `rng` is supplied. The same seeded `rng` MUST yield byte-identical `ConvertResult.svg` across runs. #### Scenario: seeded rng yields deterministic output - **WHEN** `convert` runs twice on the same > 8-colour fixture with the same seeded mulberry32 `rng` - **THEN** the two `ConvertResult.svg` strings MUST be identical. **Verified by:** `src/converter/converter.test.ts::"seeded rng yields deterministic auto output"` --- ### Requirement: OpenTelemetry instrumentation `convert()` SHALL emit an OTel counter `emblem_solver.convert.total` (incremented once per call) and a histogram `emblem_solver.convert.duration_ms` (one observation per call, unit `ms`). Instruments MUST be created lazily on first call (no module-load side effects) using `metrics.getMeter("@suaveplan/emblem-solver")`. #### Scenario: no instrument is registered before the first call - **WHEN** the module is imported but `convert` has not been called - **THEN** internal `counter`/`histogram` references MUST remain `undefined`. #### Scenario: first call registers both instruments - **WHEN** `convert` is invoked once - **THEN** the internal `counter` and `histogram` MUST be defined and the counter MUST have been incremented by `1`. **Verified by:** `src/telemetry/telemetry.test.ts::"instruments are lazily registered"` AND `src/telemetry/telemetry.test.ts::"convert increments counter and records duration"` --- ### Requirement: Tree-shakeable subpath exports The package's `package.json` SHALL expose `./types`, `./errors`, `./schemas`, `./grid`, `./io`, `./svg`, `./solver`, and `./optimizer` subpath exports in addition to the root entry, each pointing at a feature barrel. `sideEffects` MUST be `false`. #### Scenario: each subpath is importable - **WHEN** a consumer imports `@suaveplan/emblem-solver/errors` - **THEN** the import MUST resolve and expose `EmblemSolverError` and `EMBLEM_SOLVER_CODES`. **Verified by:** `src/errors/errors.test.ts::"errors subpath barrel re-exports the public surface"` --- ### Requirement: Property-based coverage correctness A property test SHALL assert that for arbitrary single-colour pixel grids generated via `fast-check`, the `convert()` output satisfies: (a) every opaque pixel in the input is covered by at least one rect in the corresponding layer, and (b) no rect's footprint extends beyond the grid bounds. #### Scenario: random solid-colour grid round-trip - **WHEN** `fast-check` generates 50 random grids of width/height in `[1, 12]` - **THEN** every required pixel MUST be covered by at least one rect. **Verified by:** `src/converter/converter.test.ts::"property: every opaque pixel is covered"`