crates/nornir-build-thing/src/kconfig_graph.rs
//! **The Kconfig GRAPH — the third class of `kernel.why.toml` stops being a
//! shrug.** (2026-08-30, lane AP, backlog #10.)
//!
//! [`WhyIndex`](crate::kernel_requires::WhyIndex) partitions every symbol of a
//! composed kernel into three classes. Two of them answer a question:
//! `feature` names the consumer that asked, `preset-only` names a fragment line
//! nobody claimed. The third, `kconfig-derived`, was **the rest** — measured on
//! the shipped `tunnr-kernel` artifact as **764 of 849 rows (90.0 %)**, and on
//! a fresh local recompose of the same fragment as **765 of 820 live symbols
//! (93.3 %)**. Nothing could declare them, so nothing could explain them: the
//! engine could not tell *"this symbol is here because something needs it"*
//! from *"this symbol is here because Kconfig dragged it in"*.
//!
//! This module reads the donor's own `Kconfig` tree — the same files
//! `olddefconfig` reads — and builds the graph:
//!
//! * `select S [if C]` — the edge that FORCES a symbol on regardless of prompt.
//! * `imply S [if C]` — the weaker edge (it moves the default, a user may say n).
//! * `depends on E` — the gate, including the implicit one an enclosing
//! `if`/`menu`/`choice` puts on every entry inside it.
//! * `default V [if C]` / `def_bool` / `def_tristate` — how a symbol nobody
//! selects becomes `y` on its own once its dependencies are met.
//!
//! and then answers, for each derived symbol, **the chain**: which declared
//! symbol (a `feature` requirement or a preset fragment line) or which named
//! FACT (the arch, the base config) ultimately pulled it in, and by which
//! edges. See [`Solver::explain`] and [`Chain`].
//!
//! # What this is NOT
//!
//! It is not a SAT solver and it does not replace `olddefconfig`. It explains a
//! `.config` that already exists. The verification that matters is therefore
//! the INVERSE, and it lives outside this module ([`Solver::heads_of`] feeds
//! it): remove the declaration at the head of a chain, recompose, and the
//! derived symbol must be gone. A solver whose chains are decorative passes
//! every test that only reads its own output — so no test in this crate is
//! allowed to be one.
//!
//! # Honest limits, measured rather than hidden
//!
//! * `$(...)` **macros** are expanded only for the environment values the
//! composer knows (`ARCH`, `SRCARCH`, `KERNELVERSION`, `CC`, `LD`). A
//! `$(shell,...)` or `$(cc-option,...)` is opaque; a default whose condition
//! is opaque is reported as [`Cause::Unexplained`] with the reason, never
//! silently assumed true.
//! * `choice` blocks are modelled as a dependency scope plus a default; the
//! exact "exactly one of" arbitration inside a choice is not re-derived.
//! * A symbol may have SEVERAL live causes. [`Solver::explain`] returns the
//! shortest chain to a head and [`Solver::heads_of`] returns EVERY head, so
//! the inverse test can say "all of this symbol's chains pass through H"
//! rather than "one of them did".
use std::collections::{BTreeMap, BTreeSet, VecDeque};
use std::path::{Path, PathBuf};
use anyhow::{Context, Result, bail};
// ── the expression language ──────────────────────────────────────────────────
/// A Kconfig boolean/tristate expression.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Expr {
/// A bare symbol (or the literals `y`/`m`/`n`), or a quoted string.
Sym(String),
/// A quoted string literal (`"x86"`).
Str(String),
/// `!e`
Not(Box<Expr>),
/// `a && b`
And(Box<Expr>, Box<Expr>),
/// `a || b`
Or(Box<Expr>, Box<Expr>),
/// `a = b` / `a != b` (`ne = true` for `!=`).
Cmp { lhs: Box<Expr>, rhs: Box<Expr>, ne: bool },
/// A relational compare (`<`, `>`, `<=`, `>=`) — kept whole, evaluated
/// numerically when both sides parse as integers.
Rel { lhs: Box<Expr>, rhs: Box<Expr>, op: String },
/// Something this parser will not pretend to understand (an unexpanded
/// `$(shell,...)`, a malformed line). Evaluation of an expression
/// containing one yields [`Tri::Unknown`].
Opaque(String),
}
/// A tristate with an explicit "the parser cannot say" value — the whole point
/// of it: an opaque macro must never read as `n`, because `n` is an answer.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum Tri {
/// `n`
No,
/// `m`
Mod,
/// `y`
Yes,
/// Not determinable from what the parser can see.
Unknown,
}
impl Tri {
/// Is this symbol ON at all (`y` or `m`)?
pub fn on(self) -> bool {
matches!(self, Tri::Yes | Tri::Mod)
}
}
impl Expr {
/// Every plain symbol name mentioned anywhere in the expression.
pub fn symbols(&self, out: &mut BTreeSet<String>) {
match self {
Expr::Sym(s) => {
if !matches!(s.as_str(), "y" | "m" | "n")
&& !s.starts_with(|c: char| c.is_ascii_digit())
{
out.insert(s.clone());
}
}
Expr::Str(_) | Expr::Opaque(_) => {}
Expr::Not(a) => a.symbols(out),
Expr::And(a, b) | Expr::Or(a, b) => {
a.symbols(out);
b.symbols(out);
}
Expr::Cmp { lhs, rhs, .. } | Expr::Rel { lhs, rhs, .. } => {
lhs.symbols(out);
rhs.symbols(out);
}
}
}
/// Evaluate against a `.config` (symbol name WITHOUT the `CONFIG_` prefix →
/// raw value half).
pub fn eval(&self, cfg: &ConfigView) -> Tri {
match self {
Expr::Sym(s) => match s.as_str() {
"y" => Tri::Yes,
"m" => Tri::Mod,
"n" => Tri::No,
// A numeric literal (`default 64`) is DATA, not a symbol: it is
// the value of an int option and says nothing boolean.
other if other.starts_with(|c: char| c.is_ascii_digit()) => Tri::Yes,
other => cfg.tri(other),
},
Expr::Str(_) => Tri::No,
Expr::Opaque(_) => Tri::Unknown,
Expr::Not(a) => match a.eval(cfg) {
Tri::Yes => Tri::No,
Tri::Mod => Tri::Mod,
Tri::No => Tri::Yes,
Tri::Unknown => Tri::Unknown,
},
Expr::And(a, b) => {
let (x, y) = (a.eval(cfg), b.eval(cfg));
if x == Tri::No || y == Tri::No {
return Tri::No;
}
if x == Tri::Unknown || y == Tri::Unknown {
return Tri::Unknown;
}
x.min(y)
}
Expr::Or(a, b) => {
let (x, y) = (a.eval(cfg), b.eval(cfg));
if x == Tri::Yes || y == Tri::Yes {
return Tri::Yes;
}
if x == Tri::Unknown || y == Tri::Unknown {
return Tri::Unknown;
}
x.max(y)
}
Expr::Cmp { lhs, rhs, ne } => {
let (a, b) = (cfg.text_of(lhs), cfg.text_of(rhs));
match (a, b) {
(Some(a), Some(b)) => {
let eq = a == b;
if eq != *ne { Tri::Yes } else { Tri::No }
}
_ => Tri::Unknown,
}
}
Expr::Rel { lhs, rhs, op } => {
let (a, b) = (cfg.text_of(lhs), cfg.text_of(rhs));
let (Some(a), Some(b)) = (a, b) else { return Tri::Unknown };
let (Ok(a), Ok(b)) = (a.parse::<i64>(), b.parse::<i64>()) else {
return Tri::Unknown;
};
let t = match op.as_str() {
"<" => a < b,
">" => a > b,
"<=" => a <= b,
">=" => a >= b,
_ => return Tri::Unknown,
};
if t { Tri::Yes } else { Tri::No }
}
}
}
}
/// A parsed `.config`: symbol (no `CONFIG_` prefix) → value half.
#[derive(Debug, Clone, Default)]
pub struct ConfigView {
/// `SMP` → `y`, `NR_CPUS` → `64`, `FAT_DEFAULT_IOCHARSET` → `cp437`.
pub values: BTreeMap<String, String>,
/// Environment values the composer knows, for `$(ARCH)`-shaped macros.
pub env: BTreeMap<String, String>,
/// **OPEN world**: a symbol this view does not mention is [`Tri::Unknown`],
/// not `n`. A merged FRAGMENT is an open world — it names 84 symbols of
/// 17 704, and the other 17 620 are decided later by `olddefconfig`, so
/// reading their absence as `n` would invent contradictions by the hundred.
/// A built `.config` is a CLOSED world and leaves this false.
pub open: bool,
}
impl ConfigView {
/// Parse a `.config` / fragment text. `# CONFIG_X is not set` records `n`.
pub fn parse(text: &str) -> Self {
let mut values = BTreeMap::new();
for line in text.lines() {
let l = line.trim();
if let Some(rest) = l.strip_prefix("# CONFIG_") {
if let Some(sym) = rest.strip_suffix(" is not set") {
values.insert(sym.to_string(), "n".to_string());
}
continue;
}
let Some(rest) = l.strip_prefix("CONFIG_") else { continue };
let Some((sym, val)) = rest.split_once('=') else { continue };
if sym.is_empty() || !sym.bytes().all(|b| b.is_ascii_alphanumeric() || b == b'_') {
continue;
}
values.insert(sym.to_string(), val.trim_matches('"').to_string());
}
ConfigView { values, env: BTreeMap::new(), open: false }
}
/// With the composer's environment (`ARCH`, `SRCARCH`, …).
pub fn with_env(mut self, env: BTreeMap<String, String>) -> Self {
self.env = env;
self
}
/// The tristate of a symbol: absent is `n`, an int/string symbol that is
/// present is `y` (it "exists"), which is what Kconfig's own `expr` does
/// for a non-bool in a boolean position.
pub fn tri(&self, sym: &str) -> Tri {
match self.values.get(sym).map(String::as_str) {
None if self.open => Tri::Unknown,
None => Tri::No,
Some("y") => Tri::Yes,
Some("m") => Tri::Mod,
Some("n") => Tri::No,
Some("") => Tri::No,
Some(_) => Tri::Yes,
}
}
/// The TEXT of one side of a comparison: a string literal is itself, a
/// NUMERIC literal is itself, a symbol is its `.config` value (absent =
/// `n`, kconfig's own rule).
///
/// The numeric arm is not a nicety. `select ARCH_HAS_NONLEAF_PMD_YOUNG if
/// PGTABLE_LEVELS > 2` lexes `2` as a name, and looking `2` up as a symbol
/// answers `n`, which does not parse as an integer — so the whole
/// comparison came back [`Tri::Unknown`] and three real `select` edges out
/// of `X86` were reported as opaque. A kconfig symbol can never start with
/// a digit, so this test is exact.
fn text_of(&self, e: &Expr) -> Option<String> {
match e {
Expr::Str(s) => Some(s.clone()),
Expr::Sym(s) => match s.as_str() {
"y" | "m" | "n" => Some(s.clone()),
other if other.starts_with(|c: char| c.is_ascii_digit()) => Some(other.to_string()),
other if self.open => self.values.get(other).cloned(),
other => Some(self.values.get(other).cloned().unwrap_or_else(|| "n".into())),
},
_ => None,
}
}
/// Is the symbol set to anything but `n`?
pub fn is_set(&self, sym: &str) -> bool {
self.tri(sym).on()
}
}
// ── the expression parser ────────────────────────────────────────────────────
struct Lexer<'a> {
s: &'a [u8],
i: usize,
}
#[derive(Debug, Clone, PartialEq, Eq)]
enum Tok {
Name(String),
Str(String),
Opaque(String),
LPar,
RPar,
Not,
And,
Or,
Eq,
Ne,
Rel(String),
End,
}
impl<'a> Lexer<'a> {
fn new(s: &'a str) -> Self {
Lexer { s: s.as_bytes(), i: 0 }
}
fn next(&mut self) -> Tok {
while self.i < self.s.len() && (self.s[self.i] as char).is_whitespace() {
self.i += 1;
}
if self.i >= self.s.len() {
return Tok::End;
}
let c = self.s[self.i] as char;
match c {
'(' => {
self.i += 1;
Tok::LPar
}
')' => {
self.i += 1;
Tok::RPar
}
'!' => {
if self.s.get(self.i + 1) == Some(&b'=') {
self.i += 2;
Tok::Ne
} else {
self.i += 1;
Tok::Not
}
}
'=' => {
self.i += 1;
Tok::Eq
}
'<' | '>' => {
let mut op = c.to_string();
self.i += 1;
if self.s.get(self.i) == Some(&b'=') {
op.push('=');
self.i += 1;
}
Tok::Rel(op)
}
'&' => {
self.i += 1;
if self.s.get(self.i) == Some(&b'&') {
self.i += 1;
}
Tok::And
}
'|' => {
self.i += 1;
if self.s.get(self.i) == Some(&b'|') {
self.i += 1;
}
Tok::Or
}
'"' | '\'' => {
let q = self.s[self.i];
self.i += 1;
let start = self.i;
while self.i < self.s.len() && self.s[self.i] != q {
self.i += 1;
}
let out = String::from_utf8_lossy(&self.s[start..self.i]).to_string();
if self.i < self.s.len() {
self.i += 1;
}
Tok::Str(out)
}
'$' => {
// A macro. Consume the balanced `$(...)`.
let start = self.i;
self.i += 1;
if self.s.get(self.i) == Some(&b'(') {
let mut depth = 0usize;
while self.i < self.s.len() {
match self.s[self.i] {
b'(' => depth += 1,
b')' => {
depth -= 1;
self.i += 1;
if depth == 0 {
break;
}
continue;
}
_ => {}
}
self.i += 1;
}
}
Tok::Opaque(String::from_utf8_lossy(&self.s[start..self.i]).to_string())
}
_ => {
let start = self.i;
while self.i < self.s.len() {
let b = self.s[self.i];
if b.is_ascii_alphanumeric() || b == b'_' || b == b'-' || b == b'.' || b == b'/' {
self.i += 1;
} else {
break;
}
}
if start == self.i {
self.i += 1; // never loop on an unknown byte
return Tok::Opaque(c.to_string());
}
Tok::Name(String::from_utf8_lossy(&self.s[start..self.i]).to_string())
}
}
}
}
struct Parser {
toks: Vec<Tok>,
i: usize,
}
impl Parser {
fn new(s: &str, env: &BTreeMap<String, String>) -> Self {
let mut lx = Lexer::new(s);
let mut toks = Vec::new();
loop {
let t = lx.next();
let done = t == Tok::End;
// Expand the macros the composer knows; leave the rest opaque.
let t = match t {
Tok::Opaque(ref m) => {
let inner = m.trim_start_matches("$(").trim_end_matches(')');
match env.get(inner) {
Some(v) => Tok::Str(v.clone()),
None => t,
}
}
other => other,
};
toks.push(t);
if done {
break;
}
}
Parser { toks, i: 0 }
}
fn peek(&self) -> &Tok {
self.toks.get(self.i).unwrap_or(&Tok::End)
}
fn bump(&mut self) -> Tok {
let t = self.toks.get(self.i).cloned().unwrap_or(Tok::End);
self.i += 1;
t
}
fn parse(&mut self) -> Expr {
self.or()
}
fn or(&mut self) -> Expr {
let mut lhs = self.and();
while *self.peek() == Tok::Or {
self.bump();
let rhs = self.and();
lhs = Expr::Or(Box::new(lhs), Box::new(rhs));
}
lhs
}
fn and(&mut self) -> Expr {
let mut lhs = self.unary();
while *self.peek() == Tok::And {
self.bump();
let rhs = self.unary();
lhs = Expr::And(Box::new(lhs), Box::new(rhs));
}
lhs
}
fn unary(&mut self) -> Expr {
if *self.peek() == Tok::Not {
self.bump();
return Expr::Not(Box::new(self.unary()));
}
self.cmp()
}
fn cmp(&mut self) -> Expr {
let lhs = self.primary();
match self.peek().clone() {
Tok::Eq => {
self.bump();
let rhs = self.primary();
Expr::Cmp { lhs: Box::new(lhs), rhs: Box::new(rhs), ne: false }
}
Tok::Ne => {
self.bump();
let rhs = self.primary();
Expr::Cmp { lhs: Box::new(lhs), rhs: Box::new(rhs), ne: true }
}
Tok::Rel(op) => {
self.bump();
let rhs = self.primary();
Expr::Rel { lhs: Box::new(lhs), rhs: Box::new(rhs), op }
}
_ => lhs,
}
}
fn primary(&mut self) -> Expr {
match self.bump() {
Tok::LPar => {
let e = self.or();
if *self.peek() == Tok::RPar {
self.bump();
}
e
}
Tok::Name(n) => Expr::Sym(n),
Tok::Str(s) => Expr::Str(s),
Tok::Opaque(m) => Expr::Opaque(m),
Tok::End => Expr::Opaque(String::new()),
other => Expr::Opaque(format!("{other:?}")),
}
}
}
/// Parse a Kconfig expression, expanding the macros in `env`.
pub fn parse_expr(s: &str, env: &BTreeMap<String, String>) -> Expr {
Parser::new(s, env).parse()
}
// ── the graph ────────────────────────────────────────────────────────────────
/// What a symbol HOLDS. The solver needs it because a `default` on an int or
/// string option carries DATA (`default 64`, `default "cp437"`), and asking
/// whether that data is "on" is a category error — it is why 40-odd int and
/// string options came back `no-live-cause` on the first real run.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum SymKind {
/// `bool` / `def_bool`
Bool,
/// `tristate` / `def_tristate`
Tristate,
/// `int` or `hex`
Int,
/// `string`
Str,
/// No type line seen (or one this parser did not reach).
#[default]
Unknown,
}
impl SymKind {
/// Does a `default` on this symbol carry a boolean, or data?
pub fn is_boolean(self) -> bool {
matches!(self, SymKind::Bool | SymKind::Tristate | SymKind::Unknown)
}
}
/// One `config`/`menuconfig` declaration, with everything the solver needs.
#[derive(Debug, Clone, Default)]
pub struct SymbolDef {
/// The name WITHOUT the `CONFIG_` prefix.
pub name: String,
/// `bool` · `tristate` · `int`/`hex` · `string`.
pub kind: SymKind,
/// Does it have a visible prompt anywhere (a user could type it)?
pub prompt: bool,
/// Every `depends on` and every enclosing `if`/`menu if`/`choice` gate,
/// as a conjunction.
pub depends: Vec<Expr>,
/// `select TARGET [if COND]`.
pub selects: Vec<(String, Option<Expr>)>,
/// `imply TARGET [if COND]`.
pub implies: Vec<(String, Option<Expr>)>,
/// `default VALUE [if COND]`, `def_bool`, `def_tristate`.
pub defaults: Vec<(Expr, Option<Expr>)>,
/// Every `Kconfig` file that declares (a piece of) this symbol.
pub files: Vec<String>,
/// Declared inside a `choice` block.
pub in_choice: bool,
}
/// The whole Kconfig tree of one kernel source, parsed.
#[derive(Debug, Clone, Default)]
pub struct KconfigGraph {
/// Symbol name (no `CONFIG_` prefix) → its declaration.
pub symbols: BTreeMap<String, SymbolDef>,
/// Reverse `select`: target → `(selector, cond)`.
pub selected_by: BTreeMap<String, Vec<(String, Option<Expr>)>>,
/// Reverse `imply`: target → `(implier, cond)`.
pub implied_by: BTreeMap<String, Vec<(String, Option<Expr>)>>,
/// Files read, in order — the provenance of the graph itself.
pub files_read: Vec<String>,
/// The environment used for macro expansion.
pub env: BTreeMap<String, String>,
}
/// The environment a kernel source's `Kconfig` tree is read under. Only what
/// the composer already declares: the arch is [`KernelBuild::arch`] and the
/// version comes off the pin.
pub fn kconfig_env(arch: &str, kernel_version: &str) -> BTreeMap<String, String> {
let srcarch = match arch {
"x86_64" | "i386" | "x86" => "x86",
"arm64" | "aarch64" => "arm64",
other => other,
};
BTreeMap::from([
("ARCH".to_string(), arch.to_string()),
("SRCARCH".to_string(), srcarch.to_string()),
("KERNELVERSION".to_string(), kernel_version.to_string()),
("CC".to_string(), "gcc".to_string()),
("LD".to_string(), "ld".to_string()),
("HOSTCC".to_string(), "gcc".to_string()),
("RUSTC".to_string(), "rustc".to_string()),
])
}
#[derive(Debug, Clone)]
enum Scope {
If(Expr),
Menu(Option<Expr>),
/// A `choice` block: the `depends on` that gates every member, the member
/// the block declares as its `default`, and the members in file order.
Choice { depends: Vec<Expr>, default_member: Option<String>, members: Vec<String> },
}
impl KconfigGraph {
/// Read the tree rooted at `<src>/Kconfig`, following `source` directives.
pub fn read(src: &Path, env: BTreeMap<String, String>) -> Result<Self> {
let mut g = KconfigGraph { env, ..Default::default() };
let root = src.join("Kconfig");
if !root.is_file() {
bail!(
"no Kconfig at {} — the kconfig solver needs the donor's own source tree \
(the extracted `linux-<version>` under the kernel workdir), not the .config alone",
root.display()
);
}
let mut seen = BTreeSet::new();
g.read_file(src, Path::new("Kconfig"), &mut seen, &mut Vec::new())?;
g.build_reverse();
Ok(g)
}
fn build_reverse(&mut self) {
let mut sel: BTreeMap<String, Vec<(String, Option<Expr>)>> = BTreeMap::new();
let mut imp: BTreeMap<String, Vec<(String, Option<Expr>)>> = BTreeMap::new();
for (name, d) in &self.symbols {
for (t, c) in &d.selects {
sel.entry(t.clone()).or_default().push((name.clone(), c.clone()));
}
for (t, c) in &d.implies {
imp.entry(t.clone()).or_default().push((name.clone(), c.clone()));
}
}
self.selected_by = sel;
self.implied_by = imp;
}
/// Textual macro expansion — for `source` PATHS only.
///
/// It must never touch an expression: `$(ARCH) != "i386"` expanded to text
/// becomes `x86_64 != "i386"`, and `x86_64` then lexes as a SYMBOL whose
/// `.config` value is absent = `n`, so the comparison is decided by a
/// symbol that does not exist. Inside an expression a macro is expanded at
/// the TOKEN level ([`Parser::new`]) into a string literal, which is what
/// it is.
fn expand_path(&self, s: &str) -> String {
let mut out = s.to_string();
for (k, v) in &self.env {
out = out.replace(&format!("$({k})"), v).replace(&format!("${k}"), v);
}
out
}
fn read_file(
&mut self,
src: &Path,
rel: &Path,
seen: &mut BTreeSet<PathBuf>,
scopes: &mut Vec<Scope>,
) -> Result<()> {
let abs = src.join(rel);
if !seen.insert(abs.clone()) {
return Ok(());
}
let text = std::fs::read_to_string(&abs)
.with_context(|| format!("read Kconfig {}", abs.display()))?;
self.files_read.push(rel.display().to_string());
// Join backslash continuations first — `select A if B && \` is one line.
let mut joined: Vec<String> = Vec::new();
for raw in text.lines() {
if let Some(prev) = joined.last_mut() {
if prev.ends_with('\\') {
prev.pop();
prev.push(' ');
prev.push_str(raw.trim_start());
continue;
}
}
joined.push(raw.to_string());
}
let mut cur: Option<String> = None;
let mut in_help = false;
let mut help_indent = 0usize;
let base_scopes = scopes.len();
let mut i = 0usize;
while i < joined.len() {
let raw = &joined[i];
i += 1;
let indent = raw.len() - raw.trim_start().len();
let line = raw.trim();
if in_help {
if line.is_empty() {
continue;
}
if indent > help_indent {
continue;
}
in_help = false;
}
if line.is_empty() || line.starts_with('#') {
continue;
}
let (kw, rest) = match line.split_once(char::is_whitespace) {
Some((a, b)) => (a, b.trim()),
None => (line, ""),
};
match kw {
"help" | "---help---" => {
in_help = true;
help_indent = indent;
}
"config" | "menuconfig" => {
let name = rest.split_whitespace().next().unwrap_or("").to_string();
if name.is_empty() {
cur = None;
continue;
}
let scope_deps = Self::scope_depends(scopes);
let in_choice = scopes.iter().any(|s| matches!(s, Scope::Choice { .. }));
if let Some(Scope::Choice { members, .. }) = scopes.last_mut() {
members.push(name.clone());
}
let e = self.symbols.entry(name.clone()).or_insert_with(|| SymbolDef {
name: name.clone(),
..Default::default()
});
e.depends.extend(scope_deps);
e.in_choice |= in_choice;
e.files.push(rel.display().to_string());
cur = Some(name);
}
"menu" => {
scopes.push(Scope::Menu(None));
cur = None;
}
"endmenu" => {
let _ = pop_scope(scopes, base_scopes, |s| matches!(s, Scope::Menu(_)));
cur = None;
}
"visible" => { /* `visible if E` gates the PROMPT, not the value */ }
"choice" => {
scopes.push(Scope::Choice {
depends: Vec::new(),
default_member: None,
members: Vec::new(),
});
cur = None;
}
"endchoice" => {
// **The choice arbitration, as far as it is honest to model
// it.** A `choice` turns exactly one member on. Which one is
// stated by the block's own `default MEMBER` when it has one
// — that is a fact in the file, and it is what put
// `CRC32_SLICEBY8`, `THERMAL_DEFAULT_GOV_STEP_WISE`,
// `PCIE_BUS_DEFAULT` and `CPU_FREQ_DEFAULT_GOV_SCHEDUTIL` in
// the composed kernel. Without the block's `default` the
// pick is the first VISIBLE member, which depends on prompt
// visibility this parser does not evaluate: those stay
// unexplained rather than guessed.
if let Some(Scope::Choice { default_member: Some(m), .. }) =
pop_scope(scopes, base_scopes, |s| matches!(s, Scope::Choice { .. }))
{
if let Some(d) = self.symbols.get_mut(&m) {
d.defaults.push((Expr::Sym("y".into()), None));
}
}
cur = None;
}
"if" => {
scopes.push(Scope::If(parse_expr(rest, &self.env)));
cur = None;
}
"endif" => {
let _ = pop_scope(scopes, base_scopes, |s| matches!(s, Scope::If(_)));
cur = None;
}
"comment" | "mainmenu" | "modules" | "option" | "optional" | "range" | "prompt" => {
if kw == "prompt" {
if let Some(c) = cur.clone() {
if let Some(d) = self.symbols.get_mut(&c) {
d.prompt = true;
}
}
}
}
"source" | "osource" | "rsource" | "orsource" => {
let p = self.expand_path(rest.trim().trim_matches('"'));
// `rsource`/`orsource` are relative to the sourcing file.
let relative = matches!(kw, "rsource" | "orsource");
let child: PathBuf = if relative {
rel.parent().unwrap_or(Path::new("")).join(&p)
} else {
PathBuf::from(&p)
};
// A `source` inherits the enclosing scopes: an `if` around a
// `source` gates every symbol in the sourced file, and that
// is where a third of the tree's dependencies live.
let mut inherited = scopes.clone();
// A glob (`source "drivers/*/Kconfig"`) is expanded by walking.
if p.contains('*') {
for m in glob_kconfig(src, &p) {
self.read_file(src, &m, seen, &mut inherited.clone())?;
}
} else if src.join(&child).is_file() {
self.read_file(src, &child, seen, &mut inherited)?;
}
cur = None;
}
"bool" | "tristate" | "int" | "hex" | "string" => {
if let Some(c) = cur.clone() {
let has_prompt = rest.trim_start().starts_with('"');
let kind = match kw {
"bool" => SymKind::Bool,
"tristate" => SymKind::Tristate,
"int" | "hex" => SymKind::Int,
_ => SymKind::Str,
};
// `bool "P" if COND` — the `if` gates the prompt only.
if let Some(d) = self.symbols.get_mut(&c) {
d.prompt |= has_prompt;
d.kind = kind;
}
}
}
"def_bool" | "def_tristate" => {
if let Some(c) = cur.clone() {
let (v, cond) = self.split_if(rest);
if let Some(d) = self.symbols.get_mut(&c) {
d.defaults.push((v, cond));
if d.kind == SymKind::Unknown {
d.kind =
if kw == "def_bool" { SymKind::Bool } else { SymKind::Tristate };
}
}
}
}
"default" => {
// `default MEMBER` with no `config` open is a CHOICE's own
// default — the one line that says which member wins.
if cur.is_none() {
if let Some(Scope::Choice { default_member, .. }) = scopes.last_mut() {
let m = split_top_if(rest)
.map(|(t, _)| t)
.unwrap_or(rest)
.trim()
.to_string();
if !m.is_empty() {
*default_member = Some(m);
}
}
}
if let Some(c) = cur.clone() {
let (v, cond) = self.split_if(rest);
if let Some(d) = self.symbols.get_mut(&c) {
d.defaults.push((v, cond));
}
}
}
"depends" => {
let rest = rest.strip_prefix("on").map(str::trim).unwrap_or(rest);
let e = parse_expr(rest, &self.env);
match cur.clone() {
Some(c) => {
if let Some(d) = self.symbols.get_mut(&c) {
d.depends.push(e);
}
}
None => {
// `depends on` directly inside a menu/choice applies
// to everything in it.
if let Some(top) = scopes.last_mut() {
match top {
Scope::Menu(slot) => *slot = Some(e),
Scope::Choice { depends, .. } => depends.push(e),
Scope::If(_) => {}
}
}
}
}
}
"select" | "imply" => {
if let Some(c) = cur.clone() {
let (target, cond) = self.split_target_if(rest);
if let Some(d) = self.symbols.get_mut(&c) {
if kw == "select" {
d.selects.push((target, cond));
} else {
d.implies.push((target, cond));
}
}
}
}
_ => {}
}
}
scopes.truncate(base_scopes);
Ok(())
}
fn scope_depends(scopes: &[Scope]) -> Vec<Expr> {
let mut out = Vec::new();
for s in scopes {
match s {
Scope::If(e) => out.push(e.clone()),
Scope::Menu(Some(e)) => out.push(e.clone()),
Scope::Menu(None) => {}
Scope::Choice { depends, .. } => out.extend(depends.iter().cloned()),
}
}
out
}
/// `VALUE if COND` → `(VALUE, Some(COND))`.
fn split_if(&self, s: &str) -> (Expr, Option<Expr>) {
match split_top_if(s) {
Some((v, c)) => (parse_expr(v, &self.env), Some(parse_expr(c, &self.env))),
None => (parse_expr(s, &self.env), None),
}
}
/// `TARGET if COND` → `("TARGET", Some(COND))`.
fn split_target_if(&self, s: &str) -> (String, Option<Expr>) {
match split_top_if(s) {
Some((t, c)) => (t.trim().to_string(), Some(parse_expr(c, &self.env))),
None => (s.trim().to_string(), None),
}
}
}
/// Pop back to (and including) the innermost scope of the wanted shape, never
/// below the scopes this file INHERITED from its `source`-er. Returns it.
fn pop_scope(scopes: &mut Vec<Scope>, base: usize, want: fn(&Scope) -> bool) -> Option<Scope> {
while scopes.len() > base {
let s = scopes.pop().expect("len > base");
if want(&s) {
return Some(s);
}
}
None
}
/// Split on the top-level ` if ` (never one inside quotes or parens).
fn split_top_if(s: &str) -> Option<(&str, &str)> {
let b = s.as_bytes();
let mut depth = 0i32;
let mut in_q = false;
let mut i = 0usize;
while i < b.len() {
match b[i] {
b'"' => in_q = !in_q,
b'(' if !in_q => depth += 1,
b')' if !in_q => depth -= 1,
b'i' if !in_q && depth == 0 => {
let before_ok = i == 0 || (b[i - 1] as char).is_whitespace();
if before_ok && b.get(i + 1) == Some(&b'f') {
let after = b.get(i + 2).copied();
if after.map(|c| (c as char).is_whitespace()).unwrap_or(false) {
return Some((&s[..i], &s[i + 3..]));
}
}
}
_ => {}
}
i += 1;
}
None
}
/// `drivers/*/Kconfig` — the only glob shape the kernel tree uses.
fn glob_kconfig(src: &Path, pat: &str) -> Vec<PathBuf> {
let Some((head, tail)) = pat.split_once('*') else { return vec![] };
let dir = src.join(head);
let tail = tail.trim_start_matches('/');
let mut out = Vec::new();
let Ok(rd) = std::fs::read_dir(&dir) else { return out };
let mut names: Vec<String> = rd
.filter_map(|e| e.ok())
.map(|e| e.file_name().to_string_lossy().to_string())
.collect();
names.sort();
for n in names {
let cand = Path::new(head).join(&n).join(tail);
if src.join(&cand).is_file() {
out.push(cand);
}
}
out
}
// ── the dangling declaration: lane AN's canary bug, made impossible ─────────
/// A fragment line the fragment ITSELF contradicts: `CONFIG_X=y` whose Kconfig
/// `depends on` is refuted by another line of the same fragment.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Dangle {
/// The symbol that cannot hold.
pub symbol: String,
/// Its `depends on`, as written.
pub depends: String,
/// The fragment lines that refute it.
pub refuted_by: Vec<String>,
}
impl Dangle {
/// The refusal sentence — it must name the fix, not the failure.
pub fn refusal(&self) -> String {
format!(
"CONFIG_{}=y cannot hold: it `depends on {}`, and this same merged fragment says {}. `olddefconfig` will DROP it and the build's canary will then refuse by name, after the container has run. Narrow the child with its parent, or stop declaring it",
self.symbol,
self.depends,
self.refuted_by.join(" · ")
)
}
}
impl KconfigGraph {
/// **Every declaration the merged fragment contradicts, before anything is
/// built.** (lane AP, 2026-08-30, from lane AN's canary bug.)
///
/// Lane AN composed a kernel for a machine with no UART. The target legally
/// narrowed `CONFIG_SERIAL_8250=n`; `kconfig/base.config`'s own
/// `CONFIG_SERIAL_8250_CONSOLE=y` stayed, `olddefconfig` dropped it because
/// it `depends on SERIAL_8250=y`, and the build died on
/// `KERNEL-CONFIG-REFUSED` — 48 seconds of container, a kernel toolchain and
/// a fetched tarball to learn something the two lines say to each other.
///
/// The fragment is read as an OPEN world ([`ConfigView::open`]): a symbol
/// it does not mention is unknown, not off, so only a contradiction the
/// fragment states about ITSELF is reported. That is the difference between
/// a check and a nuisance.
pub fn dangling_declarations(&self, merged_fragment: &str) -> Vec<Dangle> {
let mut view = ConfigView::parse(merged_fragment);
view.env = self.env.clone();
view.open = true;
let mut out = Vec::new();
for (sym, val) in &view.values {
if val == "n" {
continue;
}
let Some(def) = self.symbols.get(sym) else { continue };
for d in &def.depends {
if d.eval(&view) != Tri::No {
continue;
}
let mut named = BTreeSet::new();
d.symbols(&mut named);
let refuted: Vec<String> = named
.iter()
.filter_map(|n| view.values.get(n).map(|v| {
if v == "n" {
format!("# CONFIG_{n} is not set")
} else {
format!("CONFIG_{n}={v}")
}
}))
.collect();
out.push(Dangle {
symbol: sym.clone(),
depends: render_expr(d),
refuted_by: refuted,
});
break;
}
}
out
}
}
// ── the solver ───────────────────────────────────────────────────────────────
/// One edge of a justification chain.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Edge {
/// `PARENT select CHILD [if cond]` — the forcing edge.
Select { from: String, cond: Option<String> },
/// `PARENT imply CHILD [if cond]` — the weaker edge.
Imply { from: String, cond: Option<String> },
/// The child has a `default y`/`def_bool y` that fires because `from` is on
/// (it appears in the default's condition or in the child's `depends on`).
Default { from: String, note: String },
}
impl Edge {
/// The symbol this edge comes FROM.
pub fn from(&self) -> &str {
match self {
Edge::Select { from, .. } | Edge::Imply { from, .. } | Edge::Default { from, .. } => {
from
}
}
}
/// `select` · `imply` · `default`.
pub fn kind(&self) -> &'static str {
match self {
Edge::Select { .. } => "select",
Edge::Imply { .. } => "imply",
Edge::Default { .. } => "default",
}
}
}
/// Where a chain ENDS — the thing that is ultimately responsible.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub enum Head {
/// A symbol the merged fragment names — a `feature` requirement or a
/// `preset-only` line. **This is the head the inverse test removes.**
Declared(String),
/// Present in the BASE config (`tinyconfig`/`defconfig`) before the
/// fragment was merged, and nothing in the fragment moved it.
BaseConfig(String),
/// An unconditional `default y` on a symbol with no prompt: Kconfig turns
/// it on for everybody, and no declaration can reach it.
KconfigDefault(String),
/// The arch the composer declared (`ARCH=x86_64`): a `default` whose
/// condition is an `$(ARCH)` comparison.
Arch(String),
}
impl Head {
/// The symbol (or fact) named.
pub fn name(&self) -> &str {
match self {
Head::Declared(s) | Head::BaseConfig(s) | Head::KconfigDefault(s) | Head::Arch(s) => s,
}
}
/// The class word used in `kernel.why.toml`.
pub fn class(&self) -> &'static str {
match self {
Head::Declared(_) => "declared",
Head::BaseConfig(_) => "base-config",
Head::KconfigDefault(_) => "kconfig-default",
Head::Arch(_) => "arch",
}
}
}
/// A justification chain: `head` pulled `symbol` in, through `edges` (head-first).
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Chain {
/// The derived symbol being explained.
pub symbol: String,
/// Where the responsibility ends.
pub head: Head,
/// The edges, from the head DOWN to the symbol.
pub edges: Vec<Edge>,
}
impl Chain {
/// `CONFIG_VT [declared] --select--> CONFIG_INPUT --default--> CONFIG_INPUT_CORE`
/// — the head, then one arrow per edge, each naming the symbol it lands on.
pub fn render(&self) -> String {
// `edges[i].from()` is the symbol the i-th arrow LEAVES, so the symbol
// it LANDS on is `edges[i+1].from()` — and the last one lands on the
// symbol being explained.
let mut out = format!("CONFIG_{} [{}]", self.head.name(), self.head.class());
for (idx, e) in self.edges.iter().enumerate() {
// The terminal `default` of a [`Head::KconfigDefault`] leaves NO
// symbol (nothing above it): the head already names it.
if e.from().is_empty() {
continue;
}
let to = self
.edges
.get(idx + 1)
.map(Edge::from)
.unwrap_or(self.symbol.as_str());
out.push_str(&format!(" --{}--> CONFIG_{to}", e.kind()));
}
out
}
}
impl Unexplained {
/// The sentence that goes in `kernel.why.toml`. It must name the MECHANISM,
/// not merely the fact of failure — "no config block" and "the compiler
/// decides this one" call for different actions.
pub fn stated(&self) -> String {
match self {
Unexplained::NoDeclaration => {
"no `config` block for this symbol anywhere in the Kconfig tree".to_string()
}
Unexplained::NoLiveCause => {
"nothing selects, implies or defaults it in this .config — the parser can see no cause"
.to_string()
}
Unexplained::OpaqueCause(w) => format!(
"decided outside Kconfig: {w} — a toolchain probe is answered by RUNNING the \
compiler, so no declaration can reach it"
),
}
}
}
/// Why a symbol could NOT be explained.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub enum Unexplained {
/// The `Kconfig` tree has no `config` block for it at all (a symbol the
/// build system writes, or one this parser failed to see).
NoDeclaration,
/// Declared, but nothing selects/implies it and it has no default that
/// fires — so the parser cannot say what turned it on.
NoLiveCause,
/// Its only causes run through an expression this parser will not pretend
/// to evaluate (an unexpanded `$(shell,...)` / `$(cc-option,...)`).
OpaqueCause(String),
}
/// The verdict for one derived symbol.
#[derive(Clone)]
pub enum Cause {
/// Explained: the shortest chain, plus EVERY head that can reach it.
Explained { chain: Chain, heads: Vec<Head> },
/// Not explained, with the reason stated.
Unexplained(Unexplained),
}
/// The solver: a graph, a built `.config`, a base `.config` and the set of
/// symbols the merged fragment declares.
pub struct Solver<'a> {
/// The parsed Kconfig tree.
pub graph: &'a KconfigGraph,
/// The BUILT `.config` (after `olddefconfig`).
pub config: ConfigView,
/// The BASE `.config` (`tinyconfig`/`defconfig`, before the fragment).
pub base: ConfigView,
/// Symbols the merged fragment names — the declarations, WITHOUT `CONFIG_`.
pub declared: BTreeSet<String>,
}
/// One step of the derivation front: what turned this symbol on, from where,
/// and which OTHER live symbols the edge's own condition leans on.
///
/// `gates` exists because `X86 select GENERIC_IRQ_MIGRATION if SMP` has TWO
/// symbols in it and only one of them is the `from`. Withdrawing `SMP` removes
/// the symbol without `SMP` ever having selected it — nine of the ten misses
/// left after the gate closure landed were exactly this shape.
#[derive(Debug, Clone)]
struct Cause1 {
edge: Edge,
gates: Vec<String>,
}
impl<'a> Solver<'a> {
/// Build a solver. `fragment` is the merged fragment text, `built` the
/// `.config` beside the bzImage, `base` the starting point.
pub fn new(
graph: &'a KconfigGraph,
fragment: &str,
built: &str,
base: &str,
) -> Self {
let declared = ConfigView::parse(fragment).values.keys().cloned().collect();
Solver {
graph,
config: ConfigView::parse(built).with_env(graph.env.clone()),
base: ConfigView::parse(base),
declared,
}
}
/// Every symbol that is ON in the built `.config` and NOT named by the
/// fragment — the `kconfig-derived` class, by name.
pub fn derived(&self) -> Vec<String> {
self.config
.values
.iter()
.filter(|(k, v)| v.as_str() != "n" && !self.declared.contains(*k))
.map(|(k, _)| k.clone())
.collect()
}
/// The LIVE causes of one symbol: the edges that are actually firing in
/// this `.config`.
fn causes(&self, sym: &str) -> (Vec<Cause1>, Option<Unexplained>) {
let mut out = Vec::new();
let mut opaque: Option<String> = None;
// 1. select — the forcing edge. A selector that is ON forces the target
// ON regardless of the target's own prompt, so this is the strongest
// explanation there is.
for (from, cond) in self.graph.selected_by.get(sym).into_iter().flatten() {
if !self.config.is_set(from) {
continue;
}
match cond.as_ref().map(|c| c.eval(&self.config)) {
None | Some(Tri::Yes) | Some(Tri::Mod) => out.push(Cause1 {
edge: Edge::Select { from: from.clone(), cond: cond.as_ref().map(render_expr) },
gates: self.live_symbols_of(cond.as_ref()),
}),
Some(Tri::Unknown) => opaque = Some(format!("select from {from} has an opaque condition")),
Some(Tri::No) => {}
}
}
// 2. imply — moves the default, does not force.
for (from, cond) in self.graph.implied_by.get(sym).into_iter().flatten() {
if !self.config.is_set(from) {
continue;
}
match cond.as_ref().map(|c| c.eval(&self.config)) {
None | Some(Tri::Yes) | Some(Tri::Mod) => out.push(Cause1 {
edge: Edge::Imply { from: from.clone(), cond: cond.as_ref().map(render_expr) },
gates: self.live_symbols_of(cond.as_ref()),
}),
Some(Tri::Unknown) => opaque = Some(format!("imply from {from} has an opaque condition")),
Some(Tri::No) => {}
}
}
// 3. default — the symbol turns itself on once its gates are met. The
// PARENTS are the symbols in the winning default's condition and in
// the symbol's own `depends on`, because those are what a
// declaration can move.
if let Some(def) = self.graph.symbols.get(sym) {
let mut fired: Option<(&Expr, Option<&Expr>)> = None;
for (val, cond) in &def.defaults {
// For an int/hex/string option the default's VALUE is data: it
// is not asked whether it is `y`. Only its condition decides.
let v = if def.kind.is_boolean() { val.eval(&self.config) } else { Tri::Yes };
if !v.on() {
if v == Tri::Unknown {
opaque.get_or_insert_with(|| format!("default value {} is opaque", render_expr(val)));
}
continue;
}
match cond.as_ref().map(|c| c.eval(&self.config)) {
None | Some(Tri::Yes) | Some(Tri::Mod) => {
fired = Some((val, cond.as_ref()));
break;
}
Some(Tri::Unknown) => {
opaque.get_or_insert_with(|| {
format!("default condition {} is opaque", cond.as_ref().map(render_expr).unwrap_or_default())
});
}
Some(Tri::No) => {}
}
}
if let Some((val, cond)) = fired {
let mut parents = BTreeSet::new();
if let Some(c) = cond {
c.symbols(&mut parents);
}
if def.kind.is_boolean() {
val.symbols(&mut parents);
}
for d in &def.depends {
d.symbols(&mut parents);
}
let live: Vec<String> = parents
.into_iter()
.filter(|p| p != sym && self.config.is_set(p))
.collect();
let note = match cond {
Some(c) => format!("default {} if {}", render_expr(val), render_expr(c)),
None => format!("default {}", render_expr(val)),
};
if live.is_empty() {
// Nothing to walk up to: it is on for everybody.
out.push(Cause1 {
edge: Edge::Default { from: String::new(), note },
gates: Vec::new(),
});
} else {
for p in live {
out.push(Cause1 {
edge: Edge::Default { from: p, note: note.clone() },
gates: Vec::new(),
});
}
}
}
}
(out, opaque.map(Unexplained::OpaqueCause))
}
/// The symbols of an edge condition that are ON in this `.config`.
fn live_symbols_of(&self, cond: Option<&Expr>) -> Vec<String> {
let Some(c) = cond else { return Vec::new() };
let mut out = BTreeSet::new();
c.symbols(&mut out);
out.into_iter().filter(|s| self.config.is_set(s)).collect()
}
/// Is this symbol a HEAD in its own right?
///
/// A `Declared` head TERMINATES the walk — it is the thing an operator can
/// remove, and the inverse test removes exactly it. A `BaseConfig` head
/// does not: it is recorded and the walk CONTINUES, because a symbol can be
/// both carried over from the base and selected by a declaration, and the
/// declaration is the better answer.
///
/// The prompt is load-bearing. `olddefconfig` re-derives every symbol with
/// NO prompt from its selects and defaults and keeps nothing of the input
/// for it; only a symbol a user could have typed carries its old value
/// forward. Calling a promptless symbol "base residue" would therefore be a
/// chain that the inverse test refutes on the first try.
fn head_of(&self, sym: &str) -> Option<Head> {
if self.declared.contains(sym) {
return Some(Head::Declared(sym.to_string()));
}
let has_prompt = self.graph.symbols.get(sym).map(|d| d.prompt).unwrap_or(false);
if has_prompt && self.base.is_set(sym) {
return Some(Head::BaseConfig(sym.to_string()));
}
None
}
/// **The chain.** A breadth-first walk UP the live causes to the nearest
/// head; the shortest one wins, and ties break on head class (a declaration
/// beats a base-config residue, because a declaration is the thing an
/// operator can move).
pub fn explain(&self, sym: &str) -> Cause {
if !self.graph.symbols.contains_key(sym) {
return Cause::Unexplained(Unexplained::NoDeclaration);
}
// BFS over (symbol, path-of-edges).
let mut q: VecDeque<(String, Vec<Edge>)> = VecDeque::new();
let mut seen: BTreeSet<String> = BTreeSet::new();
seen.insert(sym.to_string());
q.push_back((sym.to_string(), Vec::new()));
let mut best: Option<Chain> = None;
let mut heads: BTreeSet<Head> = BTreeSet::new();
// A symbol can be its OWN head: `olddefconfig` carries a PROMPT symbol's
// value over from the input `.config`, so a prompt symbol the base
// already set needs no cause at all — the base IS the cause. Recorded
// as a zero-edge chain so it never outranks a real one-hop chain to a
// declaration (`consider` ranks on length first, but a zero-edge chain
// is shorter — hence the class rank, which puts `declared` first).
if !self.declared.contains(sym) {
if let Some(Head::BaseConfig(b)) = self.head_of(sym) {
let h = Head::BaseConfig(b);
heads.insert(h.clone());
best = Some(Chain { symbol: sym.to_string(), head: h, edges: Vec::new() });
}
}
let mut opaque: Option<Unexplained> = None;
let mut any_cause = false;
let mut budget = 200_000usize;
while let Some((cur, path)) = q.pop_front() {
if budget == 0 {
break;
}
budget -= 1;
let (causes, op) = self.causes(&cur);
if let Some(o) = op {
opaque.get_or_insert(o);
}
if !causes.is_empty() {
any_cause = true;
}
for c in causes {
let from = c.edge.from().to_string();
let mut p = path.clone();
p.insert(0, c.edge.clone());
if from.is_empty() {
// A default with nothing above it. If it had a CONDITION and
// that condition named no symbol at all, what decided it was
// the composer's own environment (`$(ARCH)` — the only env
// fact that varies between our kernels), not Kconfig's
// opinion; those are different answers and get different
// heads.
let h = if self.cond_names_no_symbol(&cur) {
Head::Arch(cur.clone())
} else {
Head::KconfigDefault(cur.clone())
};
heads.insert(h.clone());
consider(&mut best, Chain { symbol: sym.to_string(), head: h, edges: p });
continue;
}
if let Some(h) = self.head_of(&from) {
let terminal = matches!(h, Head::Declared(_));
heads.insert(h.clone());
consider(&mut best, Chain { symbol: sym.to_string(), head: h, edges: p.clone() });
// A DECLARED head is where the walk stops: it is the nearest
// thing the inverse test can remove. A base-config head is
// recorded and passed through.
if terminal {
continue;
}
}
if seen.insert(from.clone()) {
q.push_back((from, p));
}
}
}
match best {
Some(chain) => Cause::Explained { chain, heads: heads.into_iter().collect() },
None if opaque.is_some() => Cause::Unexplained(opaque.unwrap()),
None if any_cause => Cause::Unexplained(Unexplained::NoLiveCause),
None => Cause::Unexplained(Unexplained::NoLiveCause),
}
}
/// Did the default that fired for `sym` have a condition that names no
/// symbol at all? Then the composer's environment decided it.
fn cond_names_no_symbol(&self, sym: &str) -> bool {
let Some(def) = self.graph.symbols.get(sym) else { return false };
for (val, cond) in &def.defaults {
if !val.eval(&self.config).on() {
continue;
}
match cond {
None => return false,
Some(c) => {
if !c.eval(&self.config).on() {
continue;
}
let mut syms = BTreeSet::new();
c.symbols(&mut syms);
return syms.is_empty();
}
}
}
false
}
/// Every DECLARED head that can reach `sym` — the set the inverse test asks
/// about. A symbol with exactly one declared head is the strong case:
/// remove that declaration and the symbol MUST go.
pub fn heads_of(&self, sym: &str) -> Vec<Head> {
match self.explain(sym) {
Cause::Explained { heads, .. } => heads,
Cause::Unexplained(_) => Vec::new(),
}
}
/// **Every head of every live symbol, as a FIXPOINT.**
///
/// [`explain`](Self::explain) walks up from one symbol and stops at the
/// first declaration on each path — right for "which declaration should the
/// inverse test remove", wrong for "which declarations can reach this at
/// all", because a breadth-first walk marks each symbol seen once and never
/// revisits it by another route. Measured 2026-08-30: scored against 55 real
/// recomposes, the per-symbol walk linked **459 of 570** symbols that really
/// disappeared with a head; the fixpoint below is what closes that gap.
///
/// One pass over every live symbol's causes, repeated until nothing
/// changes. Cheap — 820 live symbols and a handful of causes each.
pub fn head_closure(&self) -> BTreeMap<String, BTreeSet<Head>> {
self.closure(false)
}
/// **The GATE closure: everything whose removal could remove this symbol.**
///
/// [`head_closure`](Self::head_closure) follows CAUSES — `select`, `imply`,
/// `default`. A symbol is also held up by its GATES: `depends on`. Both can
/// remove it, and they are different questions, so they are different
/// functions.
///
/// Measured 2026-08-30 over 55 real recomposes: of the symbols that really
/// disappeared when a declaration was withdrawn, the causal closure reached
/// **459 of 570 (80.5 %)** and the gate closure reaches the rest. Every one
/// of the 111 the causal closure missed was a GATE — `ACPI_CPPC_LIB` is
/// caused by `SMP` (`SCHED_MC_PRIO` → `X86_AMD_PSTATE`) and gated by `ACPI`,
/// so withdrawing `ACPI` removes a symbol `ACPI` never selected.
///
/// `kernel.why.toml` publishes the CAUSAL heads, because "who wanted this"
/// is the question an operator is asking; the gate closure is what the
/// inverse test scores its second direction against.
pub fn gate_closure(&self) -> BTreeMap<String, BTreeSet<Head>> {
self.closure(true)
}
fn closure(&self, follow_depends: bool) -> BTreeMap<String, BTreeSet<Head>> {
let live: Vec<String> = self
.config
.values
.iter()
.filter(|(_, v)| v.as_str() != "n")
.map(|(k, _)| k.clone())
.collect();
let mut heads: BTreeMap<String, BTreeSet<Head>> = BTreeMap::new();
// Seeds: a declaration is its own head and nothing above it matters.
for s in &live {
if self.declared.contains(s) {
heads.insert(s.clone(), BTreeSet::from([Head::Declared(s.clone())]));
} else if let Some(h) = self.head_of(s) {
heads.insert(s.clone(), BTreeSet::from([h]));
} else {
heads.insert(s.clone(), BTreeSet::new());
}
}
// Precompute the causes once — they do not change.
let causes: BTreeMap<&str, Vec<Cause1>> =
live.iter().map(|s| (s.as_str(), self.causes(s).0)).collect();
for _ in 0..64 {
let mut changed = false;
for s in &live {
if self.declared.contains(s) && !follow_depends {
continue;
}
let mut add: BTreeSet<Head> = BTreeSet::new();
if follow_depends {
// The GATES: a `depends on` that stops holding takes the
// symbol with it, whatever caused it.
if let Some(def) = self.graph.symbols.get(s) {
let mut gates = BTreeSet::new();
for d in &def.depends {
d.symbols(&mut gates);
}
for g in gates {
if g != *s && self.config.is_set(&g) {
if let Some(up) = heads.get(&g) {
add.extend(up.iter().cloned());
}
}
}
}
}
for c in causes.get(s.as_str()).into_iter().flatten() {
let from = c.edge.from();
if from.is_empty() {
add.insert(if self.cond_names_no_symbol(s) {
Head::Arch(s.clone())
} else {
Head::KconfigDefault(s.clone())
});
continue;
}
if let Some(up) = heads.get(from) {
add.extend(up.iter().cloned());
}
if follow_depends {
for g in &c.gates {
if let Some(up) = heads.get(g.as_str()) {
add.extend(up.iter().cloned());
}
}
}
}
let e = heads.entry(s.clone()).or_default();
let before = e.len();
e.extend(add);
if e.len() != before {
changed = true;
}
}
if !changed {
break;
}
}
heads
}
/// Explain EVERY derived symbol: the shortest chain from
/// [`explain`](Self::explain), with the COMPLETE head set from
/// [`head_closure`](Self::head_closure).
pub fn explain_all(&self) -> BTreeMap<String, Cause> {
let closure = self.head_closure();
self.derived()
.into_iter()
.map(|s| {
let c = match self.explain(&s) {
Cause::Explained { chain, heads } => {
let all = closure.get(&s).cloned().unwrap_or_default();
let heads = if all.is_empty() { heads } else { all.into_iter().collect() };
Cause::Explained { chain, heads }
}
other => other,
};
(s, c)
})
.collect()
}
}
fn consider(best: &mut Option<Chain>, c: Chain) {
let rank = |h: &Head| match h {
Head::Declared(_) => 0,
Head::Arch(_) => 1,
Head::KconfigDefault(_) => 2,
Head::BaseConfig(_) => 3,
};
match best {
None => *best = Some(c),
Some(b) => {
// Class FIRST, then length: a one-hop chain to a declaration is a
// better answer than a zero-hop "it was already in the base",
// because only the first one names something an operator can move.
let better = (rank(&c.head), c.edges.len()) < (rank(&b.head), b.edges.len());
if better {
*best = Some(c);
}
}
}
}
/// A human-readable spelling of an expression (for the toml rows).
pub fn render_expr(e: &Expr) -> String {
match e {
Expr::Sym(s) => s.clone(),
Expr::Str(s) => format!("{s:?}"),
Expr::Opaque(s) => s.clone(),
Expr::Not(a) => format!("!{}", render_expr(a)),
Expr::And(a, b) => format!("({} && {})", render_expr(a), render_expr(b)),
Expr::Or(a, b) => format!("({} || {})", render_expr(a), render_expr(b)),
Expr::Cmp { lhs, rhs, ne } => {
format!("{} {} {}", render_expr(lhs), if *ne { "!=" } else { "=" }, render_expr(rhs))
}
Expr::Rel { lhs, rhs, op } => format!("{} {} {}", render_expr(lhs), op, render_expr(rhs)),
}
}
#[cfg(test)]
mod tests {
use super::*;
fn env() -> BTreeMap<String, String> {
kconfig_env("x86_64", "6.12.104")
}
#[test]
fn the_expression_parser_reads_the_shapes_the_kernel_tree_actually_writes() {
let e = env();
let x = parse_expr("A && (B || !C)", &e);
let mut syms = BTreeSet::new();
x.symbols(&mut syms);
assert_eq!(syms, BTreeSet::from(["A".to_string(), "B".to_string(), "C".to_string()]));
// The macro the arch symbols hang off is EXPANDED, not opaque — that is
// what makes `64BIT` explainable at all.
let m = parse_expr("$(ARCH) != \"i386\"", &e);
let cfg = ConfigView::default().with_env(e.clone());
assert_eq!(m.eval(&cfg), Tri::Yes, "$(ARCH)=x86_64 is not i386");
// An UNKNOWN macro must not read as `n`.
let o = parse_expr("$(cc-option,-fno-stack-protector)", &e);
assert_eq!(o.eval(&cfg), Tri::Unknown);
}
#[test]
fn an_and_with_an_unknown_side_is_unknown_but_a_false_side_is_still_false() {
let e = env();
let cfg = ConfigView::parse("# CONFIG_A is not set\n").with_env(e.clone());
assert_eq!(parse_expr("A && $(shell,x)", &e).eval(&cfg), Tri::No);
let cfg2 = ConfigView::parse("CONFIG_A=y\n").with_env(e.clone());
assert_eq!(parse_expr("A && $(shell,x)", &e).eval(&cfg2), Tri::Unknown);
assert_eq!(parse_expr("A || $(shell,x)", &e).eval(&cfg2), Tri::Yes);
}
#[test]
fn the_top_level_if_split_ignores_an_if_inside_a_prompt_string() {
assert_eq!(split_top_if("FOO if BAR"), Some(("FOO ", "BAR")));
assert_eq!(split_top_if("\"turn it on if you dare\""), None);
assert_eq!(split_top_if("y"), None);
}
/// A miniature Kconfig tree with the four edge kinds, so the parser and the
/// solver are proven without a 2 GB kernel checkout.
fn tiny_tree() -> tempfile::TempDir {
let d = tempfile::tempdir().unwrap();
std::fs::write(
d.path().join("Kconfig"),
r#"
config VT
bool "virtual terminal"
select INPUT
help
this help text mentions select INPUT and must be ignored
config INPUT
bool
config INPUT_CORE
bool
default y if INPUT
config UNRELATED
bool
default y
if VT
config VT_ONLY
bool
default y
endif
config OPAQUE_ONE
bool
default y if $(cc-option,-fwhatever)
"#,
)
.unwrap();
d
}
#[test]
fn the_parser_sees_select_default_and_the_enclosing_if_and_ignores_help_prose() {
let d = tiny_tree();
let g = KconfigGraph::read(d.path(), env()).unwrap();
assert!(g.symbols.contains_key("VT"), "VT parsed");
assert_eq!(g.symbols["VT"].selects, vec![("INPUT".to_string(), None)]);
// The help text says "select INPUT" too — if help were not skipped the
// graph would carry a second, imaginary edge.
assert_eq!(g.selected_by["INPUT"].len(), 1);
assert!(g.symbols["VT"].prompt);
assert!(!g.symbols["INPUT"].prompt, "INPUT has no prompt: only a select can turn it on");
assert_eq!(g.symbols["VT_ONLY"].depends.len(), 1, "the enclosing `if VT` is a depends");
}
#[test]
fn a_selected_symbol_chains_to_the_declaration_that_selected_it() {
let d = tiny_tree();
let g = KconfigGraph::read(d.path(), env()).unwrap();
let frag = "CONFIG_VT=y\n";
let built = "CONFIG_VT=y\nCONFIG_INPUT=y\nCONFIG_INPUT_CORE=y\nCONFIG_UNRELATED=y\nCONFIG_VT_ONLY=y\n";
let base = "";
let s = Solver::new(&g, frag, built, base);
assert_eq!(s.derived(), vec!["INPUT", "INPUT_CORE", "UNRELATED", "VT_ONLY"]);
let Cause::Explained { chain, .. } = s.explain("INPUT") else { panic!("INPUT unexplained") };
assert_eq!(chain.head, Head::Declared("VT".into()));
assert_eq!(chain.edges.len(), 1);
assert_eq!(chain.edges[0].kind(), "select");
assert_eq!(chain.render(), "CONFIG_VT [declared] --select--> CONFIG_INPUT");
// Two hops: VT selects INPUT, INPUT_CORE defaults y if INPUT.
let Cause::Explained { chain, .. } = s.explain("INPUT_CORE") else { panic!() };
assert_eq!(chain.head, Head::Declared("VT".into()));
assert_eq!(chain.edges.len(), 2);
assert_eq!(chain.render(), "CONFIG_VT [declared] --select--> CONFIG_INPUT --default--> CONFIG_INPUT_CORE");
// The `if VT` scope is a dependency, so VT_ONLY chains through it too.
let Cause::Explained { chain, .. } = s.explain("VT_ONLY") else { panic!() };
assert_eq!(chain.head, Head::Declared("VT".into()));
}
#[test]
fn a_default_nobody_chose_is_named_a_kconfig_default_and_not_pinned_on_a_declaration() {
let d = tiny_tree();
let g = KconfigGraph::read(d.path(), env()).unwrap();
let s = Solver::new(
&g,
"CONFIG_VT=y\n",
"CONFIG_VT=y\nCONFIG_INPUT=y\nCONFIG_UNRELATED=y\n",
"",
);
let Cause::Explained { chain, .. } = s.explain("UNRELATED") else { panic!() };
assert_eq!(chain.head, Head::KconfigDefault("UNRELATED".into()));
// THE POINT: it must NOT be attributed to VT. An explanation that
// reaches for the nearest declaration is worse than no explanation.
assert!(!matches!(chain.head, Head::Declared(_)));
}
#[test]
fn an_opaque_condition_is_reported_as_opaque_and_never_assumed() {
let d = tiny_tree();
let g = KconfigGraph::read(d.path(), env()).unwrap();
let s = Solver::new(&g, "CONFIG_VT=y\n", "CONFIG_VT=y\nCONFIG_OPAQUE_ONE=y\n", "");
match s.explain("OPAQUE_ONE") {
Cause::Unexplained(Unexplained::OpaqueCause(w)) => assert!(w.contains("opaque"), "{w}"),
other => panic!("an unevaluatable macro must be NAMED, got {other:?}"),
}
}
#[test]
fn a_base_config_residue_is_its_own_head_and_not_a_declaration() {
let d = tiny_tree();
let g = KconfigGraph::read(d.path(), env()).unwrap();
// UNRELATED was already on in the BASE — the fragment did not cause it.
let s = Solver::new(&g, "CONFIG_VT=y\n", "CONFIG_VT=y\nCONFIG_INPUT=y\n", "CONFIG_INPUT=y\n");
// INPUT is both selected by VT and present in the base; `select` is a
// one-hop chain to a DECLARATION, which outranks the residue.
let Cause::Explained { chain, heads } = s.explain("INPUT") else { panic!() };
assert_eq!(chain.head, Head::Declared("VT".into()));
assert!(heads.contains(&Head::Declared("VT".into())));
}
#[test]
fn the_fragment_that_contradicts_itself_is_named_before_anything_is_built() {
// Lane AN's canary bug, in miniature and in the exact shape it shipped:
// a target narrows the parent, a preset line for the child stays.
let d = tempfile::tempdir().unwrap();
std::fs::write(
d.path().join("Kconfig"),
r#"
config SERIAL_8250
bool "8250 support"
config SERIAL_8250_CONSOLE
bool "console on 8250"
depends on SERIAL_8250=y
config UNRELATED
bool
default y
"#,
)
.unwrap();
let g = KconfigGraph::read(d.path(), env()).unwrap();
// GREEN: parent on, child on — nothing to say.
assert!(
g.dangling_declarations("CONFIG_SERIAL_8250=y\nCONFIG_SERIAL_8250_CONSOLE=y\n")
.is_empty()
);
// GREEN: the child alone. The fragment says nothing about the parent,
// and an OPEN world must not invent a contradiction out of silence —
// this is the arm that separates a check from a nuisance.
assert!(g.dangling_declarations("CONFIG_SERIAL_8250_CONSOLE=y\n").is_empty());
// RED: the shape that cost lane AN a container run.
let d1 = g.dangling_declarations(
"# CONFIG_SERIAL_8250 is not set\nCONFIG_SERIAL_8250_CONSOLE=y\n",
);
assert_eq!(d1.len(), 1, "exactly one dangling line, got {d1:?}");
assert_eq!(d1[0].symbol, "SERIAL_8250_CONSOLE");
let r = d1[0].refusal();
assert!(r.contains("depends on SERIAL_8250 = y"), "{r}");
assert!(r.contains("# CONFIG_SERIAL_8250 is not set"), "{r}");
assert!(r.contains("Narrow the child with its parent"), "the refusal names the FIX: {r}");
}
#[test]
fn a_symbol_with_no_config_block_at_all_says_so_rather_than_guessing() {
let d = tiny_tree();
let g = KconfigGraph::read(d.path(), env()).unwrap();
let s = Solver::new(&g, "CONFIG_VT=y\n", "CONFIG_VT=y\nCONFIG_MADE_UP=y\n", "");
assert!(matches!(
s.explain("MADE_UP"),
Cause::Unexplained(Unexplained::NoDeclaration)
));
}
}
impl std::fmt::Debug for Cause {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Cause::Explained { chain, heads } => {
write!(f, "Explained({}, heads={})", chain.render(), heads.len())
}
Cause::Unexplained(u) => write!(f, "Unexplained({u:?})"),
}
}
}