pw_coverage/config_solver.rst

.. _module-pw_coverage-config_solver:

====================================
Test Configuration Optimization Tool
====================================

--------
Overview
--------
The ``pw_coverage`` Config Solver is a tool for generating optimized test suites for projects with large configuration spaces.

Embedded projects often face a combinatorial explosion of build options (OS, Compiler, Architecture, Sanitizers, etc.). Testing every possible combination is impossible, but random sampling often misses critical edge cases.

This tool uses mathematical optimization to select a **minimal set of test configurations** that guarantees coverage of specific goals (e.g., "Test every Supported OS") while minimizing build costs.

-----------
Quick Start
-----------
Here is a complete example of defining a configuration space and solving for an optimal test suite.


.. literalinclude:: examples/quick_start.py
   :language: python
   :start-after: [pw_coverage-examples-quick_start]
   :end-before: [pw_coverage-examples-quick_start]

**Sample Output:**

.. code-block:: text

   Test 1: {'OS': 'Linux', 'Compiler': 'Clang'}
   Test 2: {'OS': 'Windows', 'Compiler': 'Clang'}
   Test 3: {'OS': 'Mac', 'Compiler': 'Clang'}

-----------
Usage Guide
-----------

Defining Parameters
===================
Parameters represent the dimensions of your test matrix.

- **Options**: Each parameter has a list of possible values.
- **Costs**: options can have an integer ``cost``. The solver will prefer using low-cost options (e.g., ``SimulatedTarget``) over high-cost ones (e.g., ``HardwareTarget``) whenever possible.

.. code-block:: python

   Parameter("Target", [
       Option("Qemu", cost=1),
       Option("DevelopmentBoard", cost=100)
   ])

Constraints (Exclusions)
========================
Use ``Exclusion`` to define invalid combinations. These often arise from toolchain limitations or platform incompatibilities.

- Exclusions are defined as Python callables that return ``True`` if a configuration is INVALID.
- **Tip**: Keep exclusion logic simple to ensure the solver can effectively sample valid candidates.

Coverage Goals
==============
Unlike pairwise testing tools that blindly cover every pair of parameters, ``pw_coverage`` requires **Explicit Coverage Goals**. This allows you to focus testing resources on what matters.

- ``CoverageGoal(["OS"])``: Ensures every OS is tested at least once.
- ``CoverageGoal(["Compiler", "Standard"])``: Ensures every valid combination of Compiler (GCC, Clang) and Standard (C++17, C++20) is tested.

Point Constraints
=================
Sometimes you need to force a specific scenario to be tested, regardless of efficiency. Use ``PointConstraint``.

.. code-block:: python

   # Force a specific sanitizer check
   PointConstraint({"OS": "Linux", "Compiler": "Clang", "Sanitizer": "ASAN"})

Existing Coverage
=================
If you already run certain tests (e.g., a mandatory "Golden" config in CI), you can tell the solver about them. It will count them towards your coverage goals but won't "charge" you for them.

.. code-block:: python

   ExistingCoverage({"OS": "Linux", "Compiler": "GCC"})

-------------------
Production Workflow
-------------------
The solver is precise, but integrating its output into a build system requires a strategy. We recommend the following patterns for robust production usage.

The "Generator" Pattern
=======================
Avoid running the solver dynamically during every build. Instead, treat it as a code generator:

1.  **Run Solver**: A project maintainer runs the generation script.
2.  **Commit Artifact**: The output (e.g., ``generated_tests.bzl`` or ``matrix.json``) is checked into version control.
3.  **CI Execution**: The build system reads the artifact to spawn tests.

This ensures **Determinism**: a specific commit always runs the exact same set of tests.

Stability Over Time
===================
When the configuration space changes (e.g., adding a new usage flag), re-running the solver entirely might produce a completely different set of tests, which "churns" the test history.

To mitigate this:

1.  Feed the **previous** generation's output into the solver as ``ExistingCoverage``.
2.  The solver will then only add enough *new* tests to cover the new interactions, keeping the baseline stable.

Build System Integration
========================
The ``CoverageSolver`` returns standard Python dictionaries. You can easily write a script to serialize these into your build system's preferred format.

**Example: generating a Bazel / Starlark list**

.. code-block:: python

   results = solver.solve()

   # Generate a .bzl file
   with open("generated_tests.bzl", "w") as f:
       f.write("COVERAGE_MATRIX = [\n")
       for config in results.selected_configurations:
           # config is just a dict: {'OS': 'Linux', ...}
           f.write(f"    {config},\n")
       f.write("]\n")

------------
How it Works
------------
The solver treats test selection as a **Weighted Set Cover** problem.

1.  **Generation**: It samples or constructively generates a pool of valid candidate configurations.
2.  **Optimization**: It uses **Google OR-Tools (CP-SAT)** to select the subset of candidates that satisfies all ``CoverageGoal`` objects with the minimum total cost.

See :ref:`module-pw_coverage-formulation` for the full mathematical details.

----------------------
Prior Art & Comparison
----------------------
This tool is inspired by **Microsoft PICT** (Pairwise Independent Combinatorial Testing).

**Key Differences:**

- **Cost Awareness**: PICT treats all tests as equal cost. ``pw_coverage`` optimizes for build time/resource usage.
- **Explicit Goals**: PICT defaults to all-pairs coverage. ``pw_coverage`` defaults to nothing, requiring users to explicitly state their testing intent. This prevents efficiently testing irrelevant interactions (e.g., ``LogFormat`` vs ``LinkerScript``).