Metadata-Version: 2.4
Name: trellis-kconfig
Version: 1.0.0
Summary: Configure a system from Kconfig option trees, checked with a SAT solver
Author: PacketFive
License-Expression: GPL-2.0-only
Project-URL: Homepage, https://github.com/PacketFive/trellis
Project-URL: Source, https://github.com/PacketFive/trellis
Project-URL: Issues, https://github.com/PacketFive/trellis/issues
Keywords: kconfig,menuconfig,configuration,sat,solver,reproducible-builds
Classifier: Development Status :: 5 - Production/Stable
Classifier: Intended Audience :: Developers
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Topic :: System :: Systems Administration
Classifier: Topic :: Software Development :: Build Tools
Classifier: Typing :: Typed
Requires-Python: >=3.12
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: pydantic<3,>=2.6
Dynamic: license-file

# Trellis

Trellis configures a build from a tree of options written in a subset of
the Linux Kconfig language. The user's choices are kept in a defconfig,
and a SAT solver resolves them into one value for every option. When
choices cannot all hold, Trellis names the smallest set of choices and
rules in conflict and lists the changes that would remove it, instead of
quietly turning an option off. It is a Python library first, with a
command, a line prompter and a full-screen menu on top.

Trellis is the configuration system of
[PyrixOS](https://github.com/PacketFive/PyrixOS), where `lattice config`
runs it. It is published on its own so any project with a Kconfig-style
option tree can use it.

Resolving is repeatable. The same tree and the same choices always give
the same configuration, whichever solver backend is used and whichever
model the solver finds on the way. The resolved configuration is written
as `config.pyb`, a file that
[PyBonsai](https://github.com/PacketFive/pybonsai) or plain Python can
read.

## Status

Stable since 1.0.0. Two solver backends give the same results:

| Backend | Solver | Needs |
| --- | --- | --- |
| `builtin` (default) | A CDCL solver in pure Python | Nothing |
| `picosat` | PicoSAT, the solver the Linux kernel's ConfigFix uses, through ctypes | `libpicosat` |

PicoSAT is found through `ctypes.util.find_library("picosat")`, or at the
path in the `TRELLIS_PICOSAT` environment variable. The tests compare
both backends with a brute-force check on random option trees. The
coverage floor is 80%.

## Install

Trellis is published on PyPI as `trellis-kconfig`, since the name
`trellis` is taken. The import name and the command are `trellis`. To use
it in another project:

```sh
pip install trellis-kconfig
```

or add `trellis-kconfig>=1.0,<2` to the project's dependencies.

To work on Trellis itself:

```sh
python -m pip install --upgrade "pip>=25.1"
pip install --group dev
pip install --config-settings editable_mode=strict -e .
pybootstrap check
```

Python 3.12 or later is required. The only runtime dependency is
Pydantic 2. The `dev` dependency group installs
[pybootstrap](https://github.com/packetfive/pybootstrap) and the tools its
gates drive: ruff, pyright, and pytest with coverage. The PicoSAT tests
are skipped when the library cannot be loaded.

Releases are made by pushing a tag `vX.Y.Z` that matches `__version__`
and has a section in `CHANGELOG.md`. The release workflow runs the gates,
builds the package, publishes it to PyPI through trusted publishing with
attestations, and creates the GitHub release.

## An example

```
config MODULES
	bool "Loadable module support"
	modules
	default y

menu "Networking"

config NET
	bool "Networking support"
	default y

config WIFI
	tristate "Wireless LAN"
	depends on NET
	select CRYPTO
	help
	  Drivers for wireless network cards.

endmenu

config CRYPTO
	tristate "Cryptographic API"
```

With this tree in `Kconfig`:

```console
$ trellis set WIFI=m
trellis: resolved 4 options in 0.3 ms
$ cat defconfig
CONFIG_WIFI=m
$ cat config.pyb
# Generated by trellis from the option tree "Configuration". Do not edit:
# change the defconfig and run trellis olddefconfig.

options = {
    "MODULES": True,
    "NET": True,
    "WIFI": "m",
    "CRYPTO": "m",
}
$ trellis explain CRYPTO
CRYPTO = m
  WIFI=m selects it (Kconfig:12)
  it cannot be n: you set WIFI=m; WIFI selects CRYPTO
$ trellis set NET=n
trellis: these choices and rules cannot all hold:
  you set NET=n
  you set WIFI=m
  WIFI depends on NET (Kconfig:12)
trellis: run trellis explain NAME VALUE to see the ways to allow a choice
$ trellis explain CRYPTO n
these choices and rules cannot all hold:
  you set WIFI=m
  WIFI selects CRYPTO (Kconfig:12)
1. drop WIFI=m
     WIFI: m -> n
     CRYPTO: m -> n
```

The defconfig holds only what the user chose. A failed `set` changes
nothing on disk.

## Use

```python
from trellis import Configurator, ConflictError

configurator = Configurator.load("Kconfig", "defconfig")
configurator.set("WIFI", "m")
print(configurator.resolve().values)  # {'MODULES': 'y', 'NET': 'y', 'WIFI': 'm', 'CRYPTO': 'm'}

conflict = configurator.conflict("NET", "n")
if conflict is not None:
    print(conflict.describe())
    for fix in configurator.fixes("NET", "n"):
        print("drop", fix.dropped, "changes", fix.changes)

configurator.save("defconfig", "config.pyb")
```

`Configurator.load` reads the tree and the defconfig, if it exists;
`Configurator(tree)` takes a tree already parsed with `parse_file` or
`parse_text`. Both take `backend="picosat"` to choose the solver.
Choices for options the tree does not have, or cannot be set because
they have no prompt, are listed in `ignored` rather than refused, so an
old defconfig still loads after the tree changes.

| Method | Does |
| --- | --- |
| `set(name, value)`, `unset(name)` | Add or remove a choice; the value is checked against the option's type at once |
| `restore(choices)` | Replace the choices |
| `resolve()` | Return the `Configuration`, or raise `ConflictError` with the conflict |
| `explain(name)` | Return why the option has its value, as reasons |
| `conflict(name, value)` | Return what stops the option taking the value, or `None` |
| `fixes(name, value, limit)` | Return the smallest sets of other choices to drop that allow it, with the values each set changes |
| `minimal()` | Return the choices without those that change nothing |
| `set_all(value)` | Set every option the rules allow to `y` or `n` |
| `save(defconfig, config)` | Resolve, then write both files; nothing is written on a conflict |
| `dimacs()` | Return the clauses of the tree in DIMACS form |

Files are written atomically and keep their existing mode.
`read_defconfig`, `write_defconfig`, `read_config` and `write_config`
handle the two file formats on their own.

Errors derive from `ConfigError`:

| Error | Raised when |
| --- | --- |
| `ParseError` | A Kconfig file cannot be read or breaks the grammar |
| `RejectedConstruct` | A Kconfig file uses a construct outside the subset |
| `TreeError` | The tree parses but breaks a rule, such as an undefined symbol or a dependency cycle |
| `InvalidValue` | A value has the wrong type, is out of range or names no option |
| `ConflictError` | The choices cannot all hold; `error.conflict` holds the details |
| `SolverUnavailable` | The `picosat` backend was asked for and cannot be loaded |

## The command

```sh
trellis menu                       # full-screen menu
trellis old                        # ask only about options config.pyb lacks
trellis olddefconfig               # write config.pyb from the defconfig
trellis defconfig configs/small    # take the choices of another defconfig
trellis savedefconfig --output -   # print the smallest defconfig
trellis set NET=y BUF=16           # add choices
trellis allyes                     # or allno
trellis check                      # exit 1 if config.pyb is out of date
trellis explain NAME [VALUE]       # why NAME has its value, or cannot be VALUE
trellis export-dimacs              # the clauses, for other SAT tools
```

`--kconfig`, `--defconfig` and `--config` name the three files, by
default `Kconfig`, `defconfig` and `config.pyb` in the current
directory. `--solver` chooses `builtin` or `picosat`. `menu`, `old`,
`set`, `defconfig`, `allyes` and `allno` save both files when they
succeed; `olddefconfig` writes only `config.pyb`. The time the solver
took goes to standard error. The exit status is 0 on success, 1 when the
choices conflict or a check fails, and 2 for an error in a file or an
argument.

In the menu, Enter opens a submenu or edits a value, Space cycles a
bool or tristate option, `y`, `m` and `n` set it, `?` shows its help and
why it has its value, and `a` also shows the options whose dependencies
do not hold. A change that conflicts is undone and the menu lists
the conflict with up to three fixes; `1` to `3` applies one. `s` saves
and `q` quits.

## The Kconfig subset

Trellis reads `config`, `menuconfig`, `choice`, `menu`, `if`, `comment`,
`mainmenu` and `source`, with the attributes `bool`, `tristate`, `int`,
`hex`, `string`, `def_bool`, `def_tristate`, `prompt`, `default`,
`depends on`, `select`, `imply`, `range`, `visible if`, `optional`,
`modules` and `help`. Anything else is refused with its file and line,
never skipped. The differences from Linux:

* `source` takes a path relative to the directory of the top file and
  cannot leave it. `rsource`, `osource`, `option env`,
  `option defconfig_list` and macros are refused.
* Choices are bool only; tristate choices are refused.
* Comparisons with `=` and `!=` take bool and tristate options or the
  constants `y`, `m` and `n`. `<`, `>`, `<=` and `>=` are refused.
* Defaults and ranges of `int`, `hex` and `string` options are literals.
* Using an undefined symbol, defining a symbol twice, or a cycle through
  `depends on` and `select` is an error.
* At most one option carries `modules`, and it must be bool.
* Selecting an option whose dependencies fail is a conflict, not a
  warning.
* Files, blocks, `menuconfig` levels and expressions nest at most 100
  deep, and the conditions of one option at most 200 deep.

The meaning otherwise follows Linux. `m` counts as `y` for a bool option,
and for a tristate option when modules are off. A `default`, an `imply`
and the default member of a choice are preferences: the user's choices
come first, and a preference gives way when it cannot hold with them.
An `optional` choice starts with no member chosen.

## How resolving works

The tree becomes clauses over two variables per tristate option and one
per bool option. The user's choices are assumptions. The preferences are
then tried in the order of the tree, each kept if everything kept so far
can still hold, except that an option the user set keeps the user's
value rather than its default. Last, every bool and tristate option is
made as small as it can be. Each step fixes something no later step can undo, which is
why the result does not depend on the solver. `int`, `hex` and `string`
options are filled in once the others are fixed.

When the assumptions cannot hold, the solver's core is shrunk until
removing any part of it would make the rest hold, so a conflict lists
only what matters. Fixes are minimal correction sets, as ConfigFix
proposes for Linux: smallest groups of the user's choices whose removal
lets the wanted value hold.

## Layout

| Module | Role |
| --- | --- |
| `language/lexer.py` | Splits Kconfig text into lines and tokens |
| `language/parser.py` | `parse_file` and `parse_text`: the subset, into an `OptionTree` |
| `language/checker.py` | `check`: undefined symbols, duplicates, cycles and types |
| `logic/expr.py` | Kconfig expressions and their values |
| `logic/cnf.py` | Clauses and DIMACS output |
| `logic/encode.py` | The tree as clauses, rules and preferences |
| `solver/cdcl.py` | The built-in CDCL solver |
| `solver/picosat.py` | The PicoSAT binding |
| `resolve.py` | Choices into a `Configuration` |
| `explain.py` | Conflicts, reasons and fixes |
| `files.py` | defconfig and `config.pyb` |
| `api.py` | `Configurator` |
| `ui/line.py` | The line prompter of `trellis old` |
| `ui/menu.py` | The full-screen menu |
| `ui/text.py` | Text shared by the consoles |
| `errors.py` | `ConfigError` and its subclasses |
| `cli.py` | The `trellis` command |

## License

GPL-2.0-only. See [LICENSE](LICENSE).
