pw_coverage/coverage.md

# Test Configuration Coverage & Optimization

## Problem Statement

Pigweed supports a vast matrix of configuration options in the embedded space, making exhaustive testing impossible. We need a systematic approach to selecting test configurations that maximizes coverage under fixed compute budgets or minimizes cost.

### Context
*   **Dimensions:**
    *   Build Systems: 5+ (Bazel, GN, CMake, etc.)
    *   Host OS: Mac, Windows, Linux
    *   Host Arch: x86, ARM64
    *   Target Arch: RISC-V, ARM Cortex-M, Xtensa, etc.
    *   Compiler: Clang/LLVM, GCC
    *   Language Standards: C++17, C++20, C++23, Python versions
    *   Build Options: Sanitizers (ASAN, TSAN, MSAN), Fuzzers, Optimization levels, Memory configs

### Requirements
1.  **Input Model:**
    *   Mutually exclusive parameters (e.g., OS: [Mac, Win, Lin])
    *   Hard Constraints (e.g., "Windows does not support BuildSystem=Soong")
    *   Costing Model (e.g., Mac is 50x more expensive than Linux)
    *   **Explicit Coverage Goals** (e.g., "We must cover every OS", "We must cover every Compiler x CppStd pair").
2.  **Execution/Optimization:**
    *   Minimize total cost of selected configurations.
    *   Guarantee that all explicit coverage goals are met.
    *   Identify "Coverage Gaps" (valid options that were skipped).
3.  **Scale:**
    *   Must handle domains with > $10^8$ possible combinations.

---

## Implemented Solution: Two-Phase Optimization

We implemented a **Declarative Modeling** approach using **Google OR-Tools (CP-SAT)**.

### 1. Declarative Model
We define the problem using high-level dataclasses in Python, ensuring type safety and validation.

*   **`Parameter`**: A dimension of variation (e.g., "Compiler") with a list of `Option`s.
*   **`Option`**: A choice (e.g., "GCC") with an integer `cost`.
*   **`Exclusion`**: A hard constraint prohibiting specific combinations (e.g., `IF OS=Win THEN Compiler!=GCC`).
*   **`PointConstraint`**: A mandatory requirement to include a specific partial configuration (e.g., `MUST HAVE {OS: Win, Target: Qemu32}`).
*   **`CoverageGoal`**: An explicit request to cover all valid combinations of a subset of parameters (e.g., `["Compiler", "CppStd"]`).

### 2. Large Domain Handling (Sampling)
For small domains (< 200k combinations), we fully enumerate the valid search space.
For large domains (e.g., Pigweed's ~80M combinations), full enumeration is intractable. We use **Random Constraint-Satisfying Sampling**:
1.  Repeatedly sample random values for each parameter.
2.  Filter by `is_valid()` (checking `Exclusion` rules).
3.  Collect `max_candidates` (e.g., 10,000 or 100,000) valid configurations.
This pool becomes the domain for the set cover optimizer.

### 2.5 Constructive Generation (Point Constraints)
Random sampling works well for broad coverage but struggles to find specific "needle in a haystack" configurations.
For **Point Constraints**, we use **Constructive Generation**:
1.  Explicitly fix the required parameter values.
2.  Randomly sample the remaining parameters until a valid configuration is found.
3.  Inject this configuration into the candidate pool to guarantee feasibility.

### 3. Optimization (CP-SAT)
We model the selection as a **Weighted Set Cover Problem**:
*   **Variables**: Binary `select_i` for each candidate configuration.
*   **Objective**: Minimize $\sum (cost_i \times select_i)$.
*   **Constraints**: For every required interaction (derived from `CoverageGoal`s), ensures $\sum_{c \in CoveringConfig} select_c \ge 1$.

### 4. Existing Coverage
We support **Existing Coverage** via the `ExistingCoverage` dataclass to respect pre-existing test investments (e.g., "This exact config runs in CQ").
*   **Opt-in Partiality**: By default, existing configs are **Strict** (must define all parameters). This catches outdated configs immediately.
*   **Partial Configs**: Users can explicit opt-in to `ExistingCoverage(..., partial=True)` for configs that only specify a subset of parameters.
*   **Strict Validation**: The model validates that all existing configs (full or partial) obey `Exclusion` constraints and parameter definitions.

### Example Output
The solver produces optimal, cost-aware test suites. For example, if "Mac" costs 500 and "Linux" costs 10:
*   It will concentrate mostly on Linux for generic coverage goals.
*   It will pick Mac *only* when absolutely necessary to satisfy a "Cover every OS" goal or a Mac-specific constraint.

---

## Learnings & Best Practices

### Explicit vs. Implicit Coverage
**Decision**: We moved away from implicit "pairwise coverage of everything" to **Explicit Coverage Goals**.
*   **Why?** Implicit pairwise explodes the logic (~$O(N^2)$ constraints) and often forces testing of irrelevant pairs (e.g., `Crypto` vs `RustEdition` might not matter).
*   **Benefit**: Users explicitly state what matters (e.g., `CoverageGoal(["Target"])`, `CoverageGoal(["Compiler", "CppStd"])`). This makes the solver faster and the output more meaningful.

### Robust Validation
We implemented strict validation in the `TestModel`:
*   **Duplicate Detection**: Immediate errors for duplicate parameters or options.
*   **Safety**: immediate `ValueError` if a `CoverageGoal` refers to a typo'd parameter.
*   **Feedback**: "Unknown parameter 'FuzzTset'" is better than a silent no-op.
*   **Strict Existing Coverage**: Configs violating constraints or missing parameters (without `partial=True`) raise immediate errors.

### Integer Costs
**Optimizers prefer Integers.**
*   We use integer costs (e.g., 10, 500) instead of floats (1.0, 50.0). using floats in Mixed Integer Programming can lead to precision artifacts.
*   We stripped arbitrary scaling factors (`* 100`) to keep the logic transparent.

### Reporting
**Don't just solve; Explain.**
*   The tool prints a **Coverage Gap Report**, identifying any parameter options that appear in *zero* selected configs. This highlights constraints that might be too aggressive (e.g., "Wait, why are we never testing 'MSAN'? Oh, we excluded it on all platforms!").

---

## Future Work / Open Questions

1.  **Deterministic Sampling**:
    *   `random.choice` is non-deterministic across runs.
    *   *Improvement*: Allow a fixed random seed for reproducible builds.
2.  **Advanced Exclusion Logic**:
    *   Current `Exclusion` is simple ("IF A=x THEN B!=y").
    *   *Improvement*: Support arbitrary boolean logic expressions (e.g., `(A=x OR B=y) IMPLIES (C!=z)`).

## Design Proposal: TestModel Display

To improve debuggability, we propose a human-readable `__str__` format for `TestModel` that mimics PICT's clarity but captures our specific features (costs, coverage goals, existing_coverage).

### Goals
1.  **Cleanliness**: No quotes, excessive brackets, or `repr()` artifacts.
2.  **Information Density**: Show costs only when relevant (non-default).
3.  **Readability**: Natural language syntax for constraints (`IF ... THEN ...`).

### Proposed Output Format

```text
Parameters:
  OS:            Mac ($50), Win ($50), Linux
  Compiler:      GCC, Clang
  Arch:          x64, arm64
  BuildSystem:   Bazel, GN ($10)

Constraints:
  1. IF OS=Win THEN Compiler!=GCC
  2. IF Arch=arm64 THEN OS!={Win, Linux}

Point Constraints:
  1. {OS=Win, Arch=x64}

Coverage Goals:
  1. (OS, Compiler)
  2. (Arch)

Existing Coverage:
  1. {OS: Linux, Compiler: GCC, Arch: x64, BuildSystem: GN}
  2. {OS: Win} (Partial)
```

### Formatting Rules

1.  **Parameters**:
    *   Align values for quick scanning.
    *   Show `($Cost)` next to a value only if `Cost > 1`.
    *   Comma-separated values.
2.  **Constraints**:
    *   Format `Exclusion` rules as `IF <Criteria> THEN <Forbidden>`.
    *   Use `Key=Val` for single values and `Key!={V1, V2}` for sets.
3.  **Point Constraints**:
    *   Format as `{Key=Val, ...}`.
4.  **Coverage Goals**:
    *   Simple tuple format `(Param1, Param2, ...)` listing the interaction dimensions.
4.  **Existing Coverage**:
    *   Format as simplified dictionaries `Key: Val`.
    *   Append `(Partial)` tag if `partial=True`.