feat(library-selection): Rust-native LDF-style transitive header scanner, zccache-backed

[zackees]

Summary

Replace the current eager "compile every library under <framework>/libraries/" behavior with a fast LDF-style transitive reachability scan, written in Rust and cached through zccache so the cost is paid at most once per (project, toolchain, library-set) tuple.

This is the proper fix for #204 (teensyLC/30 RAM overflow from unreferenced framework libraries) and gives the right answer for STM32 (#202) and any future platform port.

Motivation

Two competing goals:

1. Correctness — only link libraries transitively reachable from the sketch, matching PlatformIO's LDF chain mode. teensy30/LC: Teensy orchestrator compiles unreferenced framework libraries (FNET, Snooze, RadioHead, mbedtls) — causes .bss / .dmabuffers RAM overflow #204 shows that building the whole libraries/* tree pins unreferenced statics (FNET / Snooze / RadioHead / mbedtls ~300 TUs for a Blink sketch) in .bss, which blows the 8 KB / 16 KB RAM budget on teensyLC / teensy30.
2. Speed — PlatformIO's LDF is notoriously slow (spawns the C preprocessor, single-threaded, runs every build). fbuild's selling point is that it's fast; copying PlatformIO's design wholesale would regress build time.

A Rust-native scanner backed by zccache hits both.

Proposal

1. Native Rust header scanner

A parser that reads C/C++ source and extracts #include "…" / #include <…> directives without invoking the preprocessor.

Design notes:

• No full C parse. Just line-oriented tokenization that respects:
  • block / line comments,
  • string literals (don't match #include inside "…"),
  • the few preprocessing cases that matter (#if 0 / #ifdef __has_include can be skipped — false positives in include set are fine; false negatives are not).
• Output: Vec<IncludeRef> per TU, with { path: String, kind: Quoted | Angled, span: (line, col) }.
• Performance target: ≥ 50 MB/s single-thread on a modern host. With rayon fan-out across TUs, a 500-source Teensy core scan should be ≤ 50 ms cold.
• Unit-testable against a table of C/C++ fixtures; no external fixtures needed.

Prior art in the Rust ecosystem: cpp_includes / include_graph on crates.io, plus Bazel's and Meson's internal scanners. None are quite drop-in; a 200–400 LoC purpose-built scanner is simpler than adopting a dependency and lets us cache the output shape we actually want.

2. Transitive reachability walk

Given a seed set of TUs (the sketch + FastLED library sources + core required objects), walk the include graph over the union of project + framework + toolchain header search paths, and produce:

• included_files: Set<PathBuf> — all headers transitively reached.
• required_libraries: Set<LibraryId> — any Teensyduino (or STM32duino, or ESP) libraries/<Name>/src/<Name>.h whose header appears in included_files marks the library as "selected".
• For a selected library, compile libraries/<Name>/src/**/*.{c,cpp,S} (not examples/, extras/, tests/), add libraries/<Name>/src/ as an include root, and link the resulting archive. Then re-seed and walk again until the selection set stabilizes (fixed-point over include closure — typically 2–3 iterations).

This is exactly what PlatformIO LDF chain does semantically, but done in-process in Rust instead of spawning gcc or fork-wrapping a script.

3. zccache-backed memoization

The output of the scanner is a pure function of:

• Source file content hashes (the zccache input-fingerprint already tracks this per TU).
• The ordered search-path list (framework + toolchain + project include dirs).
• The toolchain triple (different toolchains may have different builtin headers that end the walk).

Cache key: blake3(source_content_hashes || search_paths || toolchain_triple || scanner_version).

Cache value: the serialized { included_files, required_libraries } pair. Bincode is fine; size is small (a few KB per project).

Store: put it in the existing zccache store under a new namespace (library-selection/…) so it rides existing actions/cache logic (#149, #151) and survives cross-runner restore.

Expected hit rate: on warm CI runs the scanner should be a pure cache hit. On cold runs it should be ≤ 100 ms for a typical FastLED sketch.

Non-goals

• Not a full preprocessor. We don't evaluate #if, don't expand macros. LDF doesn't either.
• Not a replacement for compile_commands.json. The scanner complements it.
• Not a replacement for the existing per-TU compile cache. It's a new cache for a new, separate question ("which libraries do I need?").

Acceptance criteria

1. fbuild build teensylc Blink compiles ≤ 250 TUs (currently 451). Specifically, FNET, Snooze, RadioHead, mbedtls are not compiled. Link succeeds with .bss ≤ 3 KB.
2. fbuild build teensy30 AnalogOutput — link succeeds, .dmabuffers ≤ 1 KB.
3. fbuild build teensy41 Blink — still succeeds; the existing Teensy 4 test coverage continues to pass.
4. fbuild build stm32f103c8 Blink — the SPI dependency is discovered automatically; no manual allowlist needed (closes stm32: Arduino_Core_STM32 framework libraries (SPI, Wire, ...) not discovered — fatal error: SPI.h: No such file or directory #202 too).
5. Warm build of the FastLED examples matrix adds ≤ 50 ms over current fbuild on the library-selection step (measured in bench/fastled-examples).
6. Cold run of library selection on teensy41 project ≤ 200 ms on a typical CI runner.

Suggested crate layout

• crates/fbuild-header-scan/ — the scanner + include-graph walker. Standalone, no fbuild dependencies; testable on its own.
• crates/fbuild-library-select/ — the per-orchestrator library resolver. Uses the scanner, adds the Teensyduino / STM32duino / Arduino library conventions. Wired into each */orchestrator.rs.
• zccache wiring in crates/fbuild-cache/ — new namespace for library-selection results.

Related

• teensy30/LC: Teensy orchestrator compiles unreferenced framework libraries (FNET, Snooze, RadioHead, mbedtls) — causes .bss / .dmabuffers RAM overflow #204 — teensyLC/teensy30 .bss overflow (bug this fixes)
• stm32: Arduino_Core_STM32 framework libraries (SPI, Wire, ...) not discovered — fatal error: SPI.h: No such file or directory #202 — STM32 SPI discovery (bug this also fixes)
• Teensy 4.x builds miss framework libraries like SPI and OctoWS2811 #163 / Fix Teensy framework library resolution #164 — prior Teensy framework-library resolution (current implementation that needs replacing)
• build: per-TU cache misses across CI runs — fast-path fingerprint bakes mtime, defeats content-based reuse #146 / build: absolute filesystem paths baked into cache keys — breaks cross-runner / cross-workspace reuse #148 / daemon/setup: expose zccache store location so consumer workflows can actions/cache it #149 / bench: add zccache store to bench/fastled-examples actions/cache path list #151 — zccache cross-runner cache strategy (the cache substrate reused here)
• Teensy 3.0 / LC link-time RAM overflow (.dmabuffers / .bss) across all examples FastLED#2406 — consumer-side tracking

[zackees]

TDD Test Plan, Implementation Plan, and Parallel Subagent Directive

Note on the issue text

One small correction before locking in the design: the issue says PlatformIO's LDF is slow because it "spawns the C preprocessor." That's not quite right — PlatformIO LDF is Python (platformio/builder/tools/piolib.py), and in chain/chain+ modes it does its own regex-based #include scan in Python (no cpp subprocess per TU). The slowness is Python + single-threaded walking + SCons node graph overhead, not preprocessor spawning. The Rust-native + rayon + zccache answer is still correct — just for the right reason.

---

Part 1 — TDD Test Plan

Organized Red → Green → Refactor. Every criterion maps to a concrete #[test], integration harness, or artifact probe. No mocks — use tempfile::TempDir trees per the project's TDD rule.

1. fbuild-header-scan — Scanner unit tests

Goal: pure function scan(&str) -> Vec<IncludeRef>. No I/O. Fixture strings inline.

1.1 Directive recognition

#	Fixture	Expected
S-01	#include <stdio.h>	1 ref, kind=Angled, path=stdio.h
S-02	#include "foo.h"	1 ref, kind=Quoted, path=foo.h
S-03	#include <a.h> (leading ws)	1 ref
S-04	# include <a.h> (ws after #)	1 ref
S-05	#include <a/b/c.h>	path=a/b/c.h
S-06	#include <a.h> // trail	1 ref, trailing comment ignored
S-07	#include "a.h" "b.h"	1 ref (second is garbage, don't crash)

1.2 Must-NOT-match cases (false-positive guards)

#	Fixture	Expected
S-10	// #include <evil.h>	0 refs
S-11	/* #include <evil.h> */	0 refs
S-12	/*\n#include <evil.h>\n*/	0 refs (multi-line block comment)
S-13	const char* s = "#include <evil.h>";	0 refs
S-14	const char* s = "\"#include <evil.h>\"";	0 refs (escaped quotes inside string)
S-15	R"(#include <evil.h>)"	0 refs (raw string literal)
S-16	char c = '#'; #include <a.h>	1 ref (char literal shouldn't swallow)
S-17	//#include <a.h>\n#include <b.h>	1 ref: b.h

1.3 Line/column spans

#	Fixture	Expected
S-20	\n\n#include <a.h>	span.line == 3, col == 1
S-21	#include <a.h>	span.line == 1, col == 3

1.4 Permissively over-include (per issue: false positives OK, false negatives not)

#	Fixture	Expected
S-30	#if 0\n#include <a.h>\n#endif	1 ref (we scan inside, per design)
S-31	#ifdef __has_include\n#include <a.h>\n#endif	1 ref
S-32	#if defined(X)\n#include <a.h>\n#else\n#include <b.h>\n#endif	2 refs (both branches)

1.5 Fuzz property tests (proptest)

• P-01: For any random UTF-8 input, scan() never panics.
• P-02: For any generated source with N embedded valid #include lines (interspersed with comments/strings), scanner returns exactly N refs in order.
• P-03: Commenting out any directive (prepend // ) monotonically decreases the ref count by 1.

1.6 Performance micro-bench (criterion)

• B-01: ≥ 50 MB/s single-thread on the Teensy 4 core (cores/teensy4/*.cpp, ~2 MB). Fail CI if < 30 MB/s.
• B-02: 500 TU rayon fan-out scan of Teensy core ≤ 50 ms cold on the CI runner spec. Report as benchmark, fail only at > 150 ms.

---

2. fbuild-header-scan — Graph walker unit tests

Goal: walk(seeds, search_paths) -> { reached: Set<PathBuf>, unresolved: Set<String> }. Use tempfile::TempDir trees — no mocks.

2.1 Resolution order

#	Setup	Expected
W-01	Quoted include resolves to same-dir first, then search paths	Matches same-dir
W-02	Angled include skips same-dir	Resolved only via search paths
W-03	Search path precedence: project → framework → toolchain	First hit wins; test with shadowing headers
W-04	Missing header	Added to unresolved, walk continues

2.2 Graph semantics

#	Scenario	Expected
W-10	Cycle: a.h → b.h → a.h	Terminates, both in reached
W-11	Diamond: main.cpp → a.h, b.h; both → common.h	common.h scanned exactly once
W-12	Transitive: depth-5 chain	All 5 reached
W-13	System header end-of-walk: <stdio.h> from toolchain include path marks as reached but does not recurse into libc internals	No bits/*.h in reached set

2.3 Determinism

• W-20: reached returned as sorted Vec<PathBuf> — run twice on same tree, byte-equal output (required for stable cache keys).

---

3. fbuild-library-select — Resolver unit tests

Goal: resolve(seeds, framework_root, project_root) -> Selection { included_files, required_libraries }.

3.1 Fixed-point iteration

#	Setup	Expected
R-01	Sketch includes <SPI.h>; libraries/SPI/src/SPI.h exists	SPI in required_libraries
R-02	SPI/src/SPI.cpp includes <Wire.h>; libraries/Wire/src/Wire.h exists	Both SPI and Wire selected (2nd iteration)
R-03	Sketch includes none of the framework libs	required_libraries empty
R-04	Convergence: artificial graph requiring 3 iterations	Exactly 3 rounds recorded; 4th is no-op
R-05	Divergence guard: circular "A needs B needs A" selection	Terminates; both selected once

3.2 Selection filters (per-framework conventions)

#	Setup	Expected
R-10	libraries/Foo/src/Foo.h reached	Foo/src/**/*.{c,cpp,S} returned as compile set
R-11	libraries/Foo/examples/** present	Not in compile set
R-12	libraries/Foo/extras/**, tests/** present	Not in compile set
R-13	Teensyduino libraries/FNET/ but not reached from seeds	Not selected (the #204 regression guard)
R-14	STM32duino libraries/SrcWrapper/src/stm32/ layout	Resolver recurses into src/, honors library.properties include root

3.3 Framework-specific conventions

• R-20: Arduino library.json declares alternate srcDir → resolver honors it.
• R-21: Recursive vs. flat library layouts both work.
• R-22: Case-insensitive match on Windows filesystems (pin this — Teensy ships SPI.h, user writes <Spi.h>).

---

4. fbuild-cache — zccache integration tests

Use a real TempDir-rooted zccache store.

4.1 Key stability

#	Test	Expected
C-01	Same inputs twice	Same blake3 key
C-02	Change one source content byte	Different key
C-03	Reorder search paths	Different key (order is part of key)
C-04	Add unreferenced file under project root	Same key (only content-hashed seeds matter)
C-05	Bump scanner_version constant	Different key
C-06	Change toolchain triple	Different key

4.2 Hit/miss semantics

• C-10: Cold miss → resolver runs → result stored.
• C-11: Warm hit → resolver NOT invoked (assert via counter/spy on resolve).
• C-12: Corrupt cache entry (manually truncated) → treated as miss, resolver re-runs, entry replaced.
• C-13: Concurrent builds writing same key → last writer wins, both builds succeed.
• C-14: Cross-runner restore: serialize cache dir, load on fresh tempdir → hit.

---

5. Per-orchestrator integration tests

Each is a cargo test -p fbuild-library-select --test <name> using real tiny framework trees in crates/fbuild-test-support/fixtures/.

• I-01 teensy: orchestrator.rs wired to library-select; Blink sketch → compile set excludes FNET, Snooze, RadioHead, mbedtls.
• I-02 stm32: Blink with <SPI.h> → SPI lib auto-selected; no manual allowlist.
• I-03 avr: Classic Arduino core still works; no regression.
• I-04 esp32: IDF component layout is a no-op — resolver returns empty required_libraries.
• I-05: Removing a #include from the sketch and rebuilding drops the library from compile set.

---

6. End-to-end board tests (TDD acceptance criteria from issue)

#	Board	Sketch	Assertion
E-01	teensyLC	Blink	TU count ≤ 250 (was 451); FNET|Snooze|RadioHead|mbedtls absent from compile DB
E-02	teensy30	AnalogOutput	Link succeeds
E-03	teensy41	Blink	Still succeeds (no regression)
E-04	stm32f103c8	Blink with SPI	SPI lib compiled, no allowlist needed (closes #202)
E-05	FastLED matrix	all examples	Diff compile set vs. pre-change; document expected deltas

---

7. Post-build artifact inspection

This is the teeth of the acceptance criteria. Don't trust "it compiles" — measure the ELF. Prefer the object crate to parse ELF in-process.

7.1 Section-size probes

#	Artifact	Probe	Threshold
A-01	teensyLC/Blink firmware.elf	.bss size	≤ 3 KB (issue AC#1)
A-02	teensy30/AnalogOutput firmware.elf	.dmabuffers section	≤ 1 KB (issue AC#2)
A-03	teensy41/Blink	.text + .data + .bss	≤ baseline + 1%
A-04	stm32f103c8/Blink with SPI	.text SPI symbols	SPIClass::* present

7.2 Symbol presence / absence

#	Board	Assertion
A-10	teensyLC/Blink	No fnet_*, snooze_*, RadioHead::*, mbedtls_* symbols
A-11	teensyLC/Blink	setup, loop, digitalWrite present
A-12	stm32/SPI sketch	SPIClass::transfer present

7.3 Compile-DB / TU-count probe

#	Probe	Assertion
A-20	.fbuild/compile_commands.json TU count, teensyLC/Blink	≤ 250
A-21	.o files under libraries/FNET/**	None
A-22	Link-line archive set == required_libraries ∪ {core}	true

7.4 Link-line probe

• A-30: -lFNET, -lSnooze, -lRadioHead, -lmbedtls absent from teensyLC link.
• A-31: All --start-group ... --end-group archives reachable from sketch.

---

8. Performance benchmarks (gate, not just report)

#	Benchmark	Threshold
P-01	Warm library-selection on FastLED examples matrix	≤ current fbuild + 50 ms (issue AC#5)
P-02	Cold library-selection on teensy41 typical project	≤ 200 ms (issue AC#6)
P-03	Scanner throughput	≥ 50 MB/s single-thread
P-04	Cache-hit round-trip	≤ 2 ms

Wire these through bench/fastled-examples so regressions fail CI, not just appear in a report.

---

Part 2 — Step-by-Step Red → Green Implementation Plan

Phase 0 — Test-support scaffolding (parallel, independent)

Step	Deliverable	Blocks
0.1	fbuild-test-support::MiniFramework — TempDir builder for fake Teensyduino/STM32duino/Arduino trees (libs, sketches, cores)	§2, §3, §5
0.2	fbuild-test-support::ElfProbe — wraps object crate: sections(), symbols(), section_size(name)	§7
0.3	fbuild-test-support::CompileDb — parses compile_commands.json into HashSet<PathBuf>	§5, §6, §7.3
0.4	Create empty crates/fbuild-header-scan/ (Cargo.toml, lib.rs stub, README)	Phase 1
0.5	Create empty crates/fbuild-library-select/	Phase 3
0.6	Add library-selection/ namespace to zccache store schema	Phase 4

Phase 1 — Scanner (TDD cycle)

1. Red: write S-01..S-07, S-10..S-17, S-20..S-21, S-30..S-32 as failing #[test].
2. Green: implement line-oriented tokenizer respecting block/line comments, string literals, raw strings, char literals. ~300 LoC budget.
3. Red: add proptest for P-01..P-03.
4. Green: harden until fuzz-clean for 100k iterations.
5. Red: add criterion bench B-01..B-02.
6. Green: optimize hot loop (bytes, not chars; avoid allocations per line).
7. Refactor: extract state machine if branching gets ugly.

Phase 2 — Graph walker

1. Red: W-01..W-04 resolution order tests using MiniFramework.
2. Green: implement walk() — BFS with visited set, quoted-first resolution for #include "…", search-path order for <…>.
3. Red: W-10..W-13 graph semantics.
4. Green: cycle detection, toolchain terminal-root configuration.
5. Red: W-20 determinism test.
6. Green: sort outputs.

Phase 3 — Resolver

1. Red: R-01..R-05 fixed-point tests.
2. Green: implement convergence loop — walk, detect new libs, add new include roots, re-walk. Cap at N iterations with error on non-convergence.
3. Red: R-10..R-14 selection-filter tests.
4. Green: exclude examples/, extras/, tests/; include src/**/*.{c,cpp,S}.
5. Red: R-20..R-22 framework conventions + Windows case-insensitive.
6. Green: library.json / library.properties parser, case-folding on Windows.

Phase 4 — zccache memoization (parallel with Phase 3 after Phase 2)

1. Red: C-01..C-06 key-stability tests.
2. Green: compose key as blake3(sorted_source_hashes ++ search_paths ++ toolchain_triple ++ SCANNER_VERSION).
3. Red: C-10..C-14 hit/miss semantics.
4. Green: wire through fbuild-cache::library-selection namespace, bincode-serialized Selection.
5. Verify: instrument with a resolve-counter for C-11.

Phase 5 — Per-orchestrator integration (parallel by framework)

All 4 can run in parallel after Phase 3 lands:

Step	Framework	Owner test	Integration point
5.a	teensy	I-01	crates/fbuild-build/src/teensy/orchestrator.rs
5.b	stm32	I-02	crates/fbuild-build/src/stm32/orchestrator.rs
5.c	avr (regression)	I-03	crates/fbuild-build/src/avr/orchestrator.rs
5.d	esp32 (no-op verify)	I-04	crates/fbuild-build/src/esp32/orchestrator.rs
5.e	cross-framework	I-05	cache invalidation on #include removal

Each step replaces the eager "compile every library" call with library_select::resolve(...) and feeds the result into the existing compile pipeline.

Phase 6 — End-to-end + artifact gates

1. Red: E-01..E-05 using real framework installs in CI.
2. Red: A-01..A-04 ELF section probes via ElfProbe.
3. Red: A-10..A-12 symbol-presence probes.
4. Red: A-20..A-22 compile-DB probes.
5. Red: A-30..A-31 link-line probes.
6. Green: fix any gap exposed (likely in resolver corner cases).

Phase 7 — Performance gates

1. Red: P-01..P-04 as bench thresholds wired to CI fail-on-regression.
2. Green: only optimize where a threshold fails. No premature optimization.

Phase 8 — Cleanup

1. Delete dead code paths from eager library compilation.
2. Update docs/architecture/ with the new library-selection subsystem.
3. Capture lessons in tasks/lessons.md.
4. Close stm32: Arduino_Core_STM32 framework libraries (SPI, Wire, ...) not discovered — fatal error: SPI.h: No such file or directory #202, teensy30/LC: Teensy orchestrator compiles unreferenced framework libraries (FNET, Snooze, RadioHead, mbedtls) — causes .bss / .dmabuffers RAM overflow #204 with links to the landing commits.

---

Part 3 — Acceptance Criteria (flat checklist)

Functional

• Scanner handles all S-01..S-32 cases.
• Scanner survives 100k proptest iterations without panic.
• Walker correctly handles cycles, diamonds, depth-5 chains, toolchain terminals.
• Walker output is deterministic and sorted.
• Resolver converges on fixed-point for all R-01..R-22 cases.
• Resolver excludes examples/, extras/, tests/.
• Resolver handles Windows case-insensitive file matching.

Caching

• Cache key is stable across identical-input runs.
• Cache key changes on content, search-path order, toolchain, or scanner version change.
• Warm hit skips resolver invocation.
• Corrupt entries fall back to miss cleanly.
• Cache round-trips through cross-runner restore.

Integration

• teensy orchestrator uses resolver (I-01 green).
• stm32 orchestrator uses resolver (I-02 green).
• avr regression passes (I-03).
• esp32 IDF path unaffected (I-04).
• Removing #include drops the library from next build (I-05).

End-to-end (issue acceptance criteria)

• AC#1: teensyLC/Blink compiles ≤ 250 TUs; FNET/Snooze/RadioHead/mbedtls absent; .bss ≤ 3 KB.
• AC#2: teensy30/AnalogOutput links; .dmabuffers ≤ 1 KB.
• AC#3: teensy41/Blink still green (no regression).
• AC#4: stm32f103c8/Blink with SPI auto-discovers (closes stm32: Arduino_Core_STM32 framework libraries (SPI, Wire, ...) not discovered — fatal error: SPI.h: No such file or directory #202).
• AC#5: Warm FastLED matrix selection ≤ current + 50 ms.
• AC#6: Cold teensy41 selection ≤ 200 ms.

Artifact probes

• A-01..A-04 ELF section sizes within thresholds.
• A-10..A-12 symbol presence/absence correct.
• A-20..A-22 compile-DB matches expected set.
• A-30..A-31 link line contains only required archives.

Performance

• P-01..P-04 thresholds enforced as CI gates, not just reported.

Hygiene

• All warnings still denied (RUSTFLAGS="-D warnings").
• uv run soldr cargo clippy --workspace --all-targets -- -D warnings clean.
• uv run soldr cargo fmt --all clean.
• RUSTDOCFLAGS="-D warnings" uv run soldr cargo doc --workspace --no-deps clean.
• Every new directory has a README.md (hook enforces).
• docs/architecture/ updated.
• tasks/lessons.md updated.
• stm32: Arduino_Core_STM32 framework libraries (SPI, Wire, ...) not discovered — fatal error: SPI.h: No such file or directory #202, teensy30/LC: Teensy orchestrator compiles unreferenced framework libraries (FNET, Snooze, RadioHead, mbedtls) — causes .bss / .dmabuffers RAM overflow #204 closed with references.

---

Part 4 — Parallel Subagent Directive

To any agent/contributor picking up this work: parallelize aggressively. The dependency graph below has several independent branches. Dispatch subagents for each concurrently. Do not serialize work that can be done in parallel.

Dependency DAG

Phase 0 (scaffolding)
├── 0.1 MiniFramework      ─┐
├── 0.2 ElfProbe           ─┼─► all independent, parallel
├── 0.3 CompileDb          ─┤
├── 0.4 fbuild-header-scan ─┤
├── 0.5 fbuild-library-select ─┤
└── 0.6 zccache namespace  ─┘

Phase 1 (scanner)         ─► depends on 0.4
Phase 2 (walker)          ─► depends on Phase 1 + 0.1
Phase 3 (resolver)        ─► depends on Phase 2 + 0.5
Phase 4 (cache)           ─► depends on Phase 2 + 0.6 (parallel with Phase 3)
Phase 5 (orchestrators)   ─► depends on Phase 3 + 4
  ├── 5.a teensy   ┐
  ├── 5.b stm32    │
  ├── 5.c avr      ├─► all four parallel
  ├── 5.d esp32    │
  └── 5.e cache-inv┘
Phase 6 (E2E + artifacts) ─► depends on Phase 5 (board tests parallel)
Phase 7 (perf gates)      ─► depends on Phase 6
Phase 8 (cleanup)         ─► depends on Phase 7

Subagent dispatch rules

1. One subagent per leaf node in the DAG. Every box that has no unstarted dependency is fair game.
2. Run independent subagents simultaneously, not sequentially. A single message with multiple Agent tool calls — not a chain of single-agent messages.
3. Each subagent owns its tests end-to-end. Red → Green → Refactor inside one subagent's scope; don't split test authorship from implementation across subagents.
4. Report back with concrete artifacts: passing test count, cargo paths, ELF probe outputs. No narrative-only summaries.
5. If a subagent blocks on another, it should post its current state and hand off — don't idle.

Parallel execution target

With 6 subagents running Phase 0 simultaneously, Phase 0 should complete in roughly the time of the slowest single item (~MiniFramework). With 4 subagents in Phase 5, per-orchestrator wiring lands together rather than over 4 serial rounds. Target total wall-clock: measured in days, not weeks.

---

Part 5 — zccache Coordination Directive

If any part of this work requires a change to zccache itself (new namespace support, serialization helpers, bug fixes in the cache layer that block library-selection memoization, cross-runner restore semantics, etc.), the workflow is:

1. Open the zccache repo locally at ~/dev/zccache.
2. Implement the required feature/fix there, with its own tests, Red → Green.
3. Cut a new zccache version — bump Cargo.toml, CHANGELOG, tag.
4. Push the release, letting GitHub Actions publish to crates.io (Rust crate) and PyPI (if the Python wrapper changed).
5. Wait for the release to propagate — verify the version is actually live on crates.io and PyPI (cargo search zccache, pip index versions zccache), don't just rely on CI success.
6. Bump the zccache dependency in this repo (Cargo.toml / pyproject.toml), re-resolve Cargo.lock.
7. Merge into fbuild and continue development from that green baseline.
8. Post a status update to this issue (feat(library-selection): Rust-native LDF-style transitive header scanner, zccache-backed #205) at every step: the zccache change landing, the version number published, the bump PR in fbuild. Include commit hashes and crates.io/PyPI links so progress is auditable from one place.

Do not vendor-patch zccache locally in fbuild's Cargo.toml (no path = "../zccache", no [patch.crates-io] hacks committed to main). Path overrides are fine for local iteration, but the landed code must pull a published version — otherwise CI and downstream consumers will break.

All updates — zccache changes, fbuild integration PRs, blockers, decisions — must be posted as comments on issue #205. This issue is the single source of truth for the feature's progress. Don't fragment status across a zccache issue, a Slack thread, or a separate fbuild issue. One thread, one timeline.

---

Part 6 — Build-Breakage Fix Directive

All build breakages encountered along the way must be fixed, regardless of whether they are caused by this work or not.

This includes but is not limited to:

• Pre-existing clippy warnings exposed by -D warnings on touched files.
• Unrelated test failures in the CI matrix.
• Toolchain or dependency issues in rust-toolchain.toml, Cargo.lock, or hook scripts.
• Broken external framework downloads (Teensyduino, STM32duino, Arduino cores).
• Flaky tests in neighboring crates.
• Documentation doc-tests failing.
• Any CI job that goes red on main during this feature's development.

Rationale: a partially green tree masks real regressions in the work at hand. If an unrelated breakage is left unfixed, every future test run is contaminated with a "known red" that hides new breakages introduced by this change. Fix it, commit the fix as a separate PR or preceding commit, then continue.

If a breakage is outside the scope of what's reasonable to fix, the subagent must:

1. Pin the root cause (file, line, error).
2. Open a separate issue referencing feat(library-selection): Rust-native LDF-style transitive header scanner, zccache-backed #205.
3. Decide whether to (a) work around it locally with a clearly-marked // TODO(#NEW_ISSUE) comment, or (b) block the phase until the separate issue is resolved.
4. Never silently skip, #[ignore], #[cfg(not(ci))], or --no-verify past the breakage.

Zero tolerance for red CI on landing. The final commit in this feature must have a fully green workspace — clippy, fmt, doc, tests, board matrix, perf gates.

[zackees]

For PR submission the agent should push and then confirm green and then merge or fix until it's merged.

[zackees]

Open-Question Resolution (post-research)

Before kicking off subagents, I dug into the current fbuild3 code, the zccache repo, and PlatformIO's LDF source to resolve the open questions. The research turned up four findings that materially change the original plan, then concrete answers to Q1–Q15.

---

Findings that change the plan

Finding 1 — fbuild3 already has a transitive walker

crates/fbuild-build/src/framework_libs.rs:22-95 (resolve_framework_library_sources) is already a BFS worklist over #include edges. It is NOT the "eager compile everything" approach the issue framing implies — it's a naive version of what #205 proposes.

Consequence: #205 is not a green-field implementation. It's:

• (a) fix the bugs in the current walker that still let FNET/Snooze/RadioHead/mbedtls through on teensyLC (teensy30/LC: Teensy orchestrator compiles unreferenced framework libraries (FNET, Snooze, RadioHead, mbedtls) — causes .bss / .dmabuffers RAM overflow #204),
• (b) add zccache memoization (currently re-runs every build),
• (c) fix ESP32 which is the only platform still doing eager "compile every library, let linker --gc-sections strip" (esp32/orchestrator.rs:569-760),
• (d) switch library-matching from basename → path-prefix attribution (see Finding 3).

Two suspect bugs in the current walker worth pinning early in Phase 1:

• framework_libs.rs:127 matches headers by basename only — collisions are possible (any Arduino.h wins regardless of which lib contains it).
• framework_libs.rs:126 compiles .c, .cpp, .cc, .cxx, .s for libraries but omits uppercase .S — assembly sources in libs are silently dropped.

Finding 2 — zccache has no Rust K/V API today

~/dev/zccache exposes only a compile-action-shaped store: ArtifactStore::insert(key, &ArtifactIndex) where ArtifactIndex is specifically { output_names, output_sizes, stdout, stderr, exit_code } (crates/zccache-artifact/src/store.rs:20-39). There is no get_bytes(key) -> Vec<u8> / put_bytes(key, bytes) surface, no namespace concept, and fbuild3 currently consumes zccache only as a CLI subprocess — zero Rust dep in any Cargo.toml.

Consequence: Phase 4 (cache wiring) activates the zccache-coordination directive from the previous comment. Concretely:

1. Open ~/dev/zccache locally.
2. Add a new zccache-kv crate (or extend zccache-artifact) with namespaced blake3-keyed Vec<u8> get/put backed by redb + content-addressed files.
3. Add a published Rust library API fbuild3 can depend on.
4. Cut zccache v1.4.0, publish to crates.io + PyPI.
5. Bump fbuild3's Cargo.toml, write Phase 4 integration tests against the real crate.

No vendor-patch shortcut. This must ship through a real zccache release.

Finding 3 — PlatformIO LDF does path-prefix attribution, not basename

Per platformio/builder/tools/piolib.py::search_deps_recursive (L428) and __contains__ (L158-178): PIO resolves each #include to an absolute path via a real scanner, then attributes the resolved path to whichever library's include_dirs contains it as a prefix. It does not match by folder name, does not read library.properties includes= (Arduino-IDE-only), and does not pre-glob .h.

Consequence: The new resolver should match PIO's path-prefix attribution, not the basename match the current fbuild3 code uses. This is also cleaner — it falls out naturally from the walker's search-path resolution.

Finding 4 — PlatformIO LDF chain mode is 2-pass, not fixed-point

Chain mode is: (1) BFS from project sources, marking libs dependent when reached; (2) one reconciliation pass (_correct_found_libs L1156) that re-walks each dependent lib's full source set (not just headers) to capture anything missed by the header-only first pass. Unconverged deps are silently dropped (L1164-1167). No iteration cap, no N-pass fixed point.

Consequence: The issue's "fixed-point over include closure — typically 2–3 iterations" framing is wrong for matching PIO semantics. Replace with PIO's 2-pass (BFS + reconciliation) design. Simpler and proven.

---

Answers to Q1–Q15

A. Seed set & scan boundary

Q1 — Seed set: Match PIO exactly. Seeds = user's src/ + include/ trees (plus test dir when testing). The sketch .ino is part of src/. Core/variant TUs are NOT seeds — they're separately compiled framework code. Project's own LDF mode is always upgraded chain→deep (PIO does the same at piolib.py:951), so the full project tree is walked regardless of any --ldf-mode chain flag.

Q2 — Terminal roots: No explicit terminal-root allowlist. Simply do not add toolchain system include paths to the walker's search paths. <stdio.h> naturally goes unresolved and is silently skipped. The walker's search paths are: project include dirs + selected framework libs' include dirs. That's it.

Q3 — Unresolved headers: Silently skip. Match PIO. Optionally emit a --verbose log line per unresolved include for debugging, but never warn or error by default. Covered by test W-04.

B. Library matching conventions

Q4 — Library discovery: Path-prefix attribution, not basename. For each library, collect its include_dirs (i.e., src/ if present, else lib root; plus utility/, include/ if they exist, plus any library.json build.includeDir override). Resolve each #include to an absolute path via the walker; attribute the resolved path to the lib whose include_dirs contains it as a prefix. Parse library.json build.includeDir/srcDir/srcFilter overrides (PIO L794-879). Do NOT consult library.properties includes= (PIO ignores it; Arduino-IDE-only).

Q5 — Source extensions: Match PIO's Arduino-library set — c, cpp, cc, cxx, c++, s, S (PIO L31-36, with asm/ASM dropped for Arduino libs per L568-576). Fix the current .S omission at framework_libs.rs:126. Exclude .h/.hpp from compilation (they're inputs to the scanner only). .ino is project-only, never a library source.

Q6 — Layout: Auto-detect. If <lib>/src/ exists → src-nested layout (src_dir=lib/src). Else → flat (src_dir=lib). Also expose <lib>/utility/ and <lib>/include/ as include dirs when present. library.json build.srcDir/includeDir fully override. Current fbuild3 already does this correctly at fbuild-packages/src/library/framework_library.rs:60-78 — keep.

C. Convergence & re-seeding

Q7 — Re-seed semantics: Two-pass, PIO style:

• Pass 1 (BFS chain): From project seeds, walk #include edges. When a resolved include lands inside any lib's include dirs, mark that lib dependent=true and add the reached header to the walk frontier (not all its sources).
• Pass 2 (reconciliation): For each dependent=true lib, do a full walk seeded with all its source files, not just reached headers. Any lib newly reached in pass 2 is also marked dependent (one extra pass, not recursive). Unconverged deps dropped silently.

Q8 — Convergence cap: No cap on the LDF walk itself (PIO has none). Cycle-safe via the visited-path set — already handled in the BFS. The only cap is preprocessor-directive depth inside a single file, and we don't evaluate #if at all, so it's moot.

D. Cache & invalidation

Q9 — Cache key composition: Do NOT hash every framework source (too expensive — Teensyduino is ~500 files). Key = blake3(

• sorted blake3s of each project source file content,
• sorted blake3s of each framework library's src/<lib-name>.h (canonical header), plus library.properties/library.json mtime-or-hash,
• ordered search-path list,
• toolchain triple,
• framework install path + framework version identifier (Teensyduino release string, STM32duino version, etc., read from whatever version file the package carries),
• SCANNER_VERSION const,
• LDF_MODE_VERSION const (bump when 2-pass algorithm changes)
  )

This catches content changes without hashing everything. Also catches framework upgrades via the version identifier.

Q10 — framework_libs.rs (417 lines) fate: Port and delete. Reusable bits → new fbuild-library-select crate: the local-header shadowing (L49-52), the exclusion filter (should_scan_framework_entry L190-199), and the #include regex (L222-240, will be superseded by the new scanner but it's a reference). Rest gets replaced by the new resolver. Delete the file entirely at end of Phase 8. Its only current caller is via resolve_framework_library_sources in orchestrators — update them in Phase 5.

E. Scope & interactions

Q11 — FastLED as seed: FastLED is a user library/project, not a framework library. Every src/**/*.{cpp,c,S} in the FastLED tree is a seed. No special-casing — falls out of Q1. When building a FastLED sketch, the sketch source is the entry point; FastLED's src/ is on the project-source seed set exactly like <project>/src/.

Q12 — ESP32: Arduino-flavored ESP32 builds do run the new resolver. Currently ESP32 compiles every built-in lib and lets linker --gc-sections strip — this is the eagerly-compiled case the issue actually refers to, not teensy (see Finding 1). Pure ESP-IDF/CMake component model is out of scope for #205. In Phase 5, esp32/orchestrator.rs:569-760 is the integration point — replace the greedy loop with resolver output.

Q13 — Introspection CLI: Add fbuild lib-select --explain <project> -e <env> in Phase 8. Prints the selected library set, each lib's trigger include, pass-1 vs pass-2 origin, and unresolved headers. Low priority but cheap once the resolver exists, and will pay for itself the first time someone debugs an AC#4-style STM32 SPI discovery regression.

F. Process

Q14 — PR strategy: Stacked PRs per phase. Each phase is independently reviewable and mergeable:

• PR Esp32-s3 PSRAM use #1: Phase 0 scaffolding (test-support, empty crates).
• PR cdc on boot warning #2: Phase 1 scanner.
• PR Fix ESP32-S3 PSRAM board configuration in board JSON database #3: Phase 2 walker.
• PR Add CDC on boot warning to ESP32 builds #4: Phase 3 resolver.
• PR Add VSCode extension scaffold (vscode-fbuild/) #5–7: Phase 4 = zccache v1.4.0 release + fbuild3 bump + Phase 4 integration tests (three separate steps).
• PR Fix ESP32-C2 build: support multiple archive formats in framework extraction #8–11: Phase 5 per-platform wiring (teensy / stm32 / avr / esp32).
• PR Add velxio integration TODO to README #12: Phase 6 E2E + artifact probes.
• PR feat(rp2040): wire up RP2040/RP2350 build orchestrator #13: Phase 7 perf gates.
• PR feat(apollo3): add build orchestrator, toolchain, and board definitions #14: Phase 8 cleanup + --explain CLI + framework_libs.rs deletion.

Squash-merge when the branch has messy intermediate commits; regular merge when commits are clean (per .claude/rules git-workflow). This stack allows Phases 1/2/3 to land on main even if the zccache coordination slips.

Q15 — Baseline measurements: No baseline infrastructure exists today. Add a Phase 0.7 "measure baseline" subagent that runs (on a stable main SHA, pinned):

• uv run soldr cargo run -p fbuild-cli -- deploy tests/platform/teensyLC -e teensyLC --dry-run → capture TU count, compile_commands.json.
• Build firmware.elf for teensyLC/Blink, teensy30/AnalogOutput, teensy41/Blink, stm32f103c8/Blink; parse with the object crate for .text/.data/.bss/.dmabuffers.
• Write all numbers to tasks/baseline-205.md with SHA + date.

This anchors AC#1/#2/#3 thresholds to real data (issue quotes 451 TUs but doesn't cite .bss in bytes). Without this, thresholds are guesses and agents will argue about them mid-Phase-6.

---

Revised DAG (post-research)

Phase 0 (scaffolding + baseline)
├── 0.1 MiniFramework         ─┐
├── 0.2 ElfProbe              ─┤
├── 0.3 CompileDb             ─┼─► all independent, parallel
├── 0.4 fbuild-header-scan    ─┤
├── 0.5 fbuild-library-select ─┤
├── 0.6 zccache Rust-KV design note (no code yet) ─┤
└── 0.7 baseline measurement (new)                 ─┘

Phase 1 (scanner)         ─► depends on 0.4
Phase 2 (walker)          ─► depends on Phase 1 + 0.1
Phase 3 (resolver, 2-pass)─► depends on Phase 2 + 0.5
   ^ switched from fixed-point to PIO-style 2-pass (Finding 4)
   ^ uses path-prefix attribution (Finding 3)

Phase 4 (cache) — now a zccache release + integration
├── 4.a open ~/dev/zccache, add zccache-kv crate (Red → Green)
├── 4.b cut zccache v1.4.0, publish crates.io + PyPI
├── 4.c wait for propagation, verify published
├── 4.d bump fbuild3 Cargo.toml, write Phase 4 integration tests
└── Posts status updates to #205 at each step.

Phase 5 (orchestrators) ─► depends on Phase 3 + 4
  ├── 5.a teensy   — replace framework_libs.rs BFS with resolver
  ├── 5.b stm32    — same
  ├── 5.c avr      — same (regression only)
  └── 5.d esp32    — replace the eager loop at orchestrator.rs:569-760
       ^ the ACTUAL eager case, not teensy

Phase 6 (E2E + artifacts) ─► depends on Phase 5, anchored to baseline from 0.7
Phase 7 (perf gates)      ─► depends on Phase 6
Phase 8 (cleanup + --explain CLI) ─► depends on Phase 7

---

Ready-to-dispatch Phase 0 subagents

Six parallel subagent jobs are now unblocked. No further open questions should stall them:

#	Job	Estimated scope
0.1	fbuild-test-support::MiniFramework — TempDir builder	~200 LoC + tests
0.2	fbuild-test-support::ElfProbe — object-crate wrapper	~100 LoC + tests
0.3	fbuild-test-support::CompileDb — parse compile_commands.json	~50 LoC + tests
0.4	crates/fbuild-header-scan/ skeleton (Cargo.toml, README, lib.rs stub, bench harness, proptest dev-dep)	~30 LoC
0.5	crates/fbuild-library-select/ skeleton (Cargo.toml, README, lib.rs stub)	~20 LoC
0.6	Design note: zccache-kv public API sketch posted as #205 comment for review before Phase 4.a begins	writeup only
0.7	Baseline measurement → tasks/baseline-205.md	script + data capture

Dispatch all seven in one round.

[zackees]

CodeRabbit follow-ups from PR #208

Captured here so they remain visible across PR merges. All 5 are minor; addressed in a follow-up PR.

1. crates/fbuild-build/tests/teensylc_acceptance.rs:80 — overly-permissive setup/loop fallback

has_symbol_containing("setup") / "loop" matches mangled C++ symbols whose names contain those substrings (e.g. _ZN6Stream8setupXxx). Since setup/loop are extern "C" from the sketch, drop the substring fallback and use has_symbol(...) only.

2. crates/fbuild-cli/src/lib_select.rs:25 — possibly unused Framework import

CodeRabbit flags use fbuild_packages::Framework; as unused. Local clippy -D warnings was green so this may be a false positive on the bot's side, but it's worth verifying and removing if truly unused.

3. crates/fbuild-cli/src/lib_select.rs (related) — document the in-process exception in crates/CLAUDE.md

The CLI's "thin HTTP client" guideline in crates/CLAUDE.md doesn't currently call out that diagnostic subcommands (lib-select, clang-tidy, iwyu, clang-query, mcp, lnk) intentionally run in-process. Add a sentence so future readers don't think the new lib-select violates the contract.

4. docs/architecture/library-selection.md:5 — stale status block

The status note still lists Phase 6 + Phase 8.a as follow-ups, but #208 ships them. Update to:

Foundation (Phases 0-3 + Phase 5 delegation) in PR #207. Phase 6 + Phase 8.a in PR #208. Phase 4 tracked at zackees/zccache#130. Phase 7 perf gates + Phase 8.b cleanup remain follow-ups in #205.

5. docs/architecture/library-selection.md:143 — Phase 8 in "Future work" is wrong

Phase 8.a (fbuild lib-select --explain CLI) ships in #208 — it should not be under "Future work". Either narrow the entry to Phase 8.b (framework_libs.rs final deletion) or move Phase 8.a to a "Now" / "What's shipped" section.

These are all addressed in PR (link to follow-up PR once opened).