Establish a repository-wide standard for solution extraction

[isPANN]

Why this is needed

A witness reduction constructs a target problem and later maps a target witness back into the source problem's configuration space through ReductionResult::extract_solution.

#1117 and PR #1083 make that operation explicitly fallible and remove the known all-zero failure markers. However, the repository still has no written rule for what counts as valid extraction input, which malformed states must be rejected, or when zero and sentinel values are legitimate mathematical results.

That missing standard affects both existing and future reductions. A scan after the targeted fixes found 270 extractor implementations. Among them, 50 functions still contain a default-producing operation such as unwrap_or(...) without an explicit extraction error, 3 silently truncate to the available target length, and 5 use expect/unwrap without converting decode failure into ExtractionError. These are audit candidates rather than 58 already-proven bugs: a default can be correct only when the source model explicitly gives it mathematical meaning.

The contributor documentation also still shows the superseded signature:

fn extract_solution(&self, target_sol: &[usize]) -> Vec<usize>

in docs/src/design.md. A new reduction author therefore cannot discover the current error contract from the design guide.

Existing behavior showing the gap

A missing one-hot selection becomes a real label

Several ILP and QUBO reductions decode an assignment block like this:

(0..num_choices)
    .find(|&choice| target_solution[index(choice)] == 1)
    .unwrap_or(0)

For a one-vertex, three-color encoding:

[1, 0, 0] -> color 0
[0, 0, 0] -> color 0

The first input selects color 0. The second selects no color and is not a valid encoded witness, but the extractor returns the same source configuration. Current examples include:

• partitionintopathsoflength2_ilp.rs: missing group becomes group 0;
• minimumdiscreteplanarinversekinematics_qubo.rs: missing orientation becomes orientation 0;
• subgraphisomorphism_ilp.rs: unmapped pattern vertex becomes host vertex 0;
• coloring_ilp.rs and coloring_qubo.rs: missing color becomes color 0.

Two selected entries are also ambiguous. An extractor that uses find silently chooses the first:

[1, 1, 0] -> color 0

The required behavior for an exactly-one block is:

[0, 1, 0] -> Ok(color 1)
[0, 0, 0] -> Err(no color selected)
[1, 1, 0] -> Err(multiple colors selected)

A short target configuration is silently accepted

preemptivescheduling_ilp.rs and kcoloring_clustering.rs currently use the available prefix:

target_solution[..expected_len.min(target_solution.len())].to_vec()

If the source requires three values and the target input contains only [1, 0], extraction returns a two-element source configuration. The missing value is neither represented nor reported.

Other rules use get(index).unwrap_or(0), so the same short input is padded with invented zeros instead. Direct indexing produces a third behavior: panic.

The standard must require one result for all three implementations:

wrong target length -> Err

A decoder failure becomes a panic

optimallineararrangement_sequencingtominimizeweightedcompletiontime.rs calls expect after decoding a Lehmer code. A malformed permutation representation therefore panics even though the public extraction API returns ExtractionResult.

The required behavior is to preserve the decoder's failure as ExtractionError, with enough context to identify the invalid representation.

Zero or a sentinel can be mathematically correct

Not every apparent default is a fallback. MaximumCommonEdgeSubgraph represents an unmapped source vertex with n2, where n2 is one past the last target-graph vertex. Its source dimensions explicitly include that value:

vec![graph_2.num_vertices() + 1; graph_1.num_vertices()]

For one source vertex and two target vertices, an ILP witness with no selected mapping variables may therefore correctly extract to [2]. Replacing that value with an error would change the problem definition.

This is the distinction the audit must enforce:

value defined by the source model -> keep and test it
value invented only because decoding failed -> return Err

Objective

Create and adopt one repository-wide standard for solution extraction.

The standard must cover existing reductions and future contributions. It must make concrete decisions for:

1. exact target configuration length;
2. each target value's Problem::dims() domain;
3. structured encodings such as one-hot blocks, permutations, paths, flows, and schedules;
4. exact source configuration length and domains;
5. partial mappings, empty instances, and model-defined sentinel values;
6. error messages and rule context;
7. panic-free behavior for caller-provided target configurations;
8. propagation through direct, dynamic-chain, bundle, solver, and CLI execution.

For each category, the documentation must state:

• what is valid input;
• what extract_solution returns for valid input;
• which malformed inputs return ExtractionError;
• one short example from an existing reduction;
• which semantic test a new reduction must provide.

A contributor should be able to implement and review an extractor without knowing the history of #1117 or PR #1083.

Repository-wide extraction standard

The adopted standard must express at least these rules:

• target_solution.len() must equal target_problem().dims().len(). Missing and extra entries are errors; they are never padded or ignored.
• Every target value must be smaller than its corresponding dimension before rule-specific decoding indexes or interprets it.
• If extraction relies on exactly one selected entry, it must reject both zero selected entries and multiple selected entries. Selecting the first is not decoding.
• If extraction relies on a permutation, path, schedule, flow, or another structured representation, it must reject a representation that does not satisfy the structure needed by the inverse mapping.
• Decode failures return ExtractionError; malformed caller input must not reach unwrap, expect, or an indexing panic.
• A successful result must have the exact length and per-variable domains required by the source problem.
• Numeric zero is ordinary data. It may be returned when the reduction maps to zero, but it must never mean "extraction failed."
• A sentinel or partial mapping is allowed only when it is part of the source model's declared configuration space and reduction semantics.
• Empty and singleton instances follow the same mathematical mapping as other instances. They must not have a separate fabricated fallback merely to avoid an error.
• Errors must identify the violated condition, such as expected versus actual length, an out-of-domain value and index, or a zero-hot/two-hot block. Dynamic execution must add the source and target problem names.

Validation branches that reject invalid input are part of the contract. Compatibility branches that manufacture an old result are not.

Simplicity and control-flow requirement

This standard is also a control-flow standard. Fixing the audit must not turn each extractor into a collection of special cases.

A normal extractor has one readable path:

validate the complete target configuration once
-> decode the reduction representation once
-> return the source configuration

Apply these constraints during the audit:

• Check whole-input length and domains before indexing. Do not repeat idx < len, get(...).unwrap_or(...), or equivalent local bounds branches throughout a decoder.
• Every conditional must correspond to a named mathematical invariant and either continue the single mapping or return ExtractionError.
• Do not clamp, truncate, pad, repair, retry, complement, search for an alternative candidate, or choose a conventional value after decoding fails.
• Do not branch on empty, singleton, short, or legacy inputs merely to manufacture an output. Ranges and the mathematical mapping should handle degenerate valid instances naturally.
• Do not preserve old behavior behind compatibility conditions or add a list of rule-specific exceptions.
• When a reduction permits optional structure, such as an unmapped vertex, represent that option in the model and decode it directly. Do not infer optionality from missing target data.
• After replacing a fallback, delete the superseded branch and any helper used only by that branch.

The desired result is not "more validation code." It is less ambiguous code: one validation phase, one inverse mapping, and explicit failure when their preconditions do not hold.

Rust examples

Do not write a fallback disguised as decoding:

let color = (0..num_colors)
    .find(|&color| target_solution[color_index(vertex, color)] == 1)
    .unwrap_or(0);

Report an absent or ambiguous selection directly:

let mut selected = (0..num_colors)
    .filter(|&color| target_solution[color_index(vertex, color)] == 1);
let color = selected
    .next()
    .ok_or_else(|| ExtractionError::invalid("vertex has no selected color"))?;
if selected.next().is_some() {
    return Err(ExtractionError::invalid(
        "vertex has multiple selected colors",
    ));
}

Do not accept whatever prefix happened to arrive:

Ok(target_solution[..expected_len.min(target_solution.len())].to_vec())

Require the represented configuration exactly:

if target_solution.len() != expected_len {
    return Err(ExtractionError::invalid(format!(
        "expected {expected_len} target values, got {}",
        target_solution.len(),
    )));
}

Every direct extractor must call validate_target_solution() once before rule-specific decoding. The helper validates only exact target length and value domains; composed extractors delegate to the first direct decoder. Keep rule-specific structural validation and decoding direct and local.

Required repository changes

• Add a contributor-facing solution-extraction section to docs/src/design.md and update its obsolete ReductionResult example to return ExtractionResult<Vec<usize>>.
• Add a concise extraction checklist to .claude/CLAUDE.md so new reduction work follows the same rules.
• Update the repository's reduction contribution instructions to require authors to identify:
  • the target configuration layout;
  • the source configuration layout;
  • every structural invariant used by extraction;
  • legitimate sentinel or partial-mapping values;
  • malformed-input tests.
• Audit every ReductionResult::extract_solution implementation under src/rules/, including generic and macro-generated implementations.
• Classify every apparent default as a model-defined value or a failure fallback. Remove fallbacks; retain legitimate values with semantic tests.
• Replace extraction-path truncation and panics with ExtractionError.
• Simplify every changed extractor to one validation phase followed by one decoding phase; delete recovery, compatibility, and degenerate-input fallback branches.
• Add contract coverage for every registered witness reduction without deleting or weakening existing valid-witness assertions.

Do not add an exception registry, compatibility wrapper, second extraction interface, or generic decoding framework. Use the existing ExtractionResult boundary and direct Rust code close to each representation.

Verification

The standard is visible to contributors

Run:

make doc

The generated Design documentation must contain the eight categories under Objective, the repository-wide rules above, and current ExtractionResult<Vec<usize>> examples. The reduction contribution checklist must link to or summarize the same contract.

Known inputs distinguish values from failures

Add focused tests runnable with:

cargo test extraction_contracts -- --nocapture

The tests must include these hand-checkable cases:

1. For a one-vertex, three-color one-hot decoder, [0, 1, 0] extracts color 1; [0, 0, 0] and [1, 1, 0] both return Err.
2. The same decoder rejects [0, 1] and [0, 1, 0, 0] for wrong length and rejects [0, 2, 0] because a binary target variable contains 2.
3. MaximumCommonEdgeSubgraph with one source vertex and two target vertices accepts a valid no-mapping target witness and extracts the model-defined sentinel [2].
4. An invalid Lehmer-code witness returns Err; the test fails naturally if extraction panics.

The first two cases prove that malformed data cannot masquerade as color 0. The third is the negative control against an over-broad implementation that rejects every zero-hot block or sentinel. The fourth proves decoder failures remain inside the fallible API.

Every registered witness extractor follows the contract

The contract suite must exercise every registered witness reduction using its canonical valid example and verify:

• valid target witness -> expected valid source witness;
• remove one target entry -> Err for every non-empty target configuration;
• append one target entry -> Err;
• replace one target value with its dimension bound -> Err;
• representation-specific invalid state -> Err where extraction relies on that structure.

The test must fail if a registered witness reduction has no contract case. This prevents future rules from entering the repository without the standard's coverage. Review must also reject an extractor that passes these cases by accumulating input-specific recovery branches instead of implementing the single validation-and-decode path above.

Finally run:

make check

It must pass, proving that normal valid witnesses and the rest of the repository retain their behavior. Search commands may help locate candidates, but grep output alone is not acceptance evidence.

Out of scope

• Redesigning reduction graph search, solver selection, aggregate extraction, or capability registration.
• Reintroducing the old infallible extraction API.
• Rejecting a partial mapping or sentinel that is explicitly part of a source model's configuration space.
• Adding infrastructure or compatibility behavior for hypothetical future encodings.