varve_core/
compose.rs

1//! Layer composition (REQ-COMPOSE-001).
2//!
3//! A pin names one realm and one layer. That was fine while a layer held one
4//! organisation's tools, and it broke the first time a consumer needed two: the
5//! PulseEngine tools that CHECK their work and the upstream tools that BUILD it
6//! (varve#52). Putting both in one layer would place releases we do not control
7//! under a qualification claim covering tools we do — so instead a layer may
8//! COMPOSE another.
9//!
10//! An include is a manifest entry of payload kind `layer`, whose digest is the
11//! included layer's manifest digest and whose annotations name its realm. It
12//! lives in the signed payload, so the composition is signed; and because the
13//! digest is the identity, an include cannot silently drift.
14//!
15//! Everything here fails closed. A cycle is refused rather than followed, depth
16//! is bounded, and a tool exposed by two layers is an ERROR naming both — varve
17//! does not pick a winner, for the same reason a pin that does not resolve
18//! uniquely is an error and not a fallback.
19
20use std::collections::{BTreeMap, BTreeSet};
21
22/// A lenient view of a layer manifest — just what composition needs.
23///
24/// Deliberately NOT `LayerManifest`: that parse enforces the full install
25/// contract (counter, issued-at), and requiring it merely to discover whether a
26/// layer composes another would make `which` fail on layers that resolve fine
27/// today. Reading less is what lets this be additive.
28#[derive(Debug, Clone, PartialEq, Eq, Default)]
29pub struct LayerView {
30    pub includes: Vec<Include>,
31    /// Dispatchable tool names this layer exposes.
32    pub tools: Vec<String>,
33}
34
35/// Read the composition-relevant parts of a manifest. An unparseable manifest
36/// is an error, never an empty view — silently reporting "no includes" for a
37/// layer we could not read is the failure mode that hides a composition.
38pub fn view(bytes: &[u8]) -> Result<LayerView, ComposeError> {
39    let json: serde_json::Value =
40        serde_json::from_slice(bytes).map_err(|e| ComposeError::Unreadable(e.to_string()))?;
41    let mut v = LayerView::default();
42    let Some(entries) = json["manifests"].as_array() else {
43        return Ok(v);
44    };
45    for e in entries {
46        let ann = &e["annotations"];
47        let digest = e["digest"].as_str().unwrap_or_default().to_string();
48        match ann[crate::kind::ANN_KIND].as_str() {
49            Some("layer") => v.includes.push(Include {
50                digest,
51                realm: ann[ANN_INCLUDE_REALM].as_str().map(|s| s.to_string()),
52                layer: ann[ANN_INCLUDE_LAYER].as_str().map(|s| s.to_string()),
53            }),
54            // Absent kind = tool (back-compat, as everywhere else).
55            None => {
56                if let Some(t) = ann["eu.pulseengine.tool"].as_str() {
57                    v.tools.push(t.to_string());
58                }
59            }
60            // Any other kind is not dispatchable and not an include.
61            Some(_) => {}
62        }
63    }
64    Ok(v)
65}
66
67/// Annotation naming the realm an included layer belongs to. Absent means the
68/// including layer's own realm.
69pub const ANN_INCLUDE_REALM: &str = "eu.pulseengine.varve.include.realm";
70/// Annotation carrying the included layer's identity, for error messages that
71/// can name it before it has been fetched.
72pub const ANN_INCLUDE_LAYER: &str = "eu.pulseengine.varve.include.layer";
73
74/// How deep a composition graph may go. Generous for real use (a layer
75/// including a layer including a base), small enough that a malicious or
76/// mistaken graph cannot spend the client's time.
77pub const MAX_DEPTH: usize = 8;
78
79/// One layer this manifest composes.
80#[derive(Debug, Clone, PartialEq, Eq)]
81pub struct Include {
82    /// `sha256:<hex>` of the included layer's signed manifest — its identity.
83    pub digest: String,
84    /// The realm whose trust root verifies it. `None` = the including realm.
85    pub realm: Option<String>,
86    /// The included layer's identifier, for messages before it is resolved.
87    pub layer: Option<String>,
88}
89
90#[derive(Debug, thiserror::Error)]
91pub enum ComposeError {
92    #[error(
93        "composition cycle: layer {digest} includes itself, directly or through \
94         {via} — refusing to follow it"
95    )]
96    Cycle { digest: String, via: String },
97    #[error(
98        "composition is more than {MAX_DEPTH} layers deep — refusing to walk further \
99         (a layer graph this deep is a mistake, not a design)"
100    )]
101    TooDeep,
102    #[error("layer manifest could not be read for composition: {0}")]
103    Unreadable(String),
104    #[error(
105        "tool '{tool}' is exposed by more than one layer in this composition \
106         ({first} and {second}) — refusing to choose. Restrict the pin's `tools`, \
107         or remove the duplicate from one layer."
108    )]
109    AmbiguousTool {
110        tool: String,
111        first: String,
112        second: String,
113    },
114}
115
116/// The layers a view directly composes, in manifest order.
117pub fn includes(v: &LayerView) -> Vec<Include> {
118    v.includes.clone()
119}
120
121/// Walk a composition graph breadth-first from a root manifest, refusing cycles
122/// and excessive depth. `fetch` supplies a manifest for a digest, or `None` if
123/// that layer is not installed — a missing layer is the caller's error to
124/// report (with its corrective `varve install`), not this walker's to invent.
125///
126/// Returns the visit order, root first, so callers can union tools predictably.
127pub fn walk<F>(
128    root_digest: &str,
129    root: &LayerView,
130    mut fetch: F,
131) -> Result<Vec<(String, LayerView)>, ComposeError>
132where
133    F: FnMut(&str) -> Option<LayerView>,
134{
135    let mut out = vec![(root_digest.to_string(), root.clone())];
136    let mut emitted: BTreeSet<String> = BTreeSet::new();
137    emitted.insert(root_digest.to_string());
138    // (digest, view, ancestors-on-this-path). A CYCLE is a digest reappearing
139    // on its OWN path — not merely one seen before. An earlier version used a
140    // global `seen`, which reported a DIAMOND (two layers sharing a base) as a
141    // cycle, with a message falsely claiming the layer included itself. A
142    // shared base is the most ordinary composition there is.
143    let mut stack: Vec<(String, LayerView, BTreeSet<String>)> = vec![(
144        root_digest.to_string(),
145        root.clone(),
146        BTreeSet::from([root_digest.to_string()]),
147    )];
148    while let Some((from, view, path)) = stack.pop() {
149        if path.len() > MAX_DEPTH {
150            return Err(ComposeError::TooDeep);
151        }
152        for inc in includes(&view) {
153            if path.contains(&inc.digest) {
154                return Err(ComposeError::Cycle {
155                    digest: inc.digest.clone(),
156                    via: from.clone(),
157                });
158            }
159            let Some(child) = fetch(&inc.digest) else {
160                // Not installed. The caller names it and how to fix it.
161                continue;
162            };
163            // A layer reachable by two paths is walked once, not refused.
164            if emitted.insert(inc.digest.clone()) {
165                out.push((inc.digest.clone(), child.clone()));
166            }
167            let mut child_path = path.clone();
168            child_path.insert(inc.digest.clone());
169            stack.push((inc.digest.clone(), child, child_path));
170        }
171    }
172    Ok(out)
173}
174
175/// Union the tool names a composition exposes, refusing any name that appears
176/// in more than one layer. Returns tool → the digest of the layer providing it.
177pub fn union_tools(
178    layers: &[(String, LayerView)],
179) -> Result<BTreeMap<String, String>, ComposeError> {
180    let mut owner: BTreeMap<String, String> = BTreeMap::new();
181    for (digest, v) in layers {
182        for tool in &v.tools {
183            if let Some(first) = owner.get(tool)
184                && first != digest
185            {
186                return Err(ComposeError::AmbiguousTool {
187                    tool: tool.clone(),
188                    first: first.clone(),
189                    second: digest.clone(),
190                });
191            }
192            owner.insert(tool.clone(), digest.clone());
193        }
194    }
195    Ok(owner)
196}
197
198#[cfg(test)]
199mod tests {
200    use super::*;
201
202    /// A manifest with the given tools and includes.
203    fn manifest(layer: &str, tools: &[&str], includes: &[(&str, &str)]) -> LayerView {
204        let mut entries: Vec<String> = tools
205            .iter()
206            .map(|t| {
207                format!(
208                    r#"{{"digest":"sha256:{t}","annotations":{{"eu.pulseengine.tool":"{t}"}}}}"#
209                )
210            })
211            .collect();
212        for (digest, realm) in includes {
213            entries.push(format!(
214                r#"{{"digest":"{digest}","annotations":{{"eu.pulseengine.varve.kind":"layer","{ANN_INCLUDE_REALM}":"{realm}"}}}}"#
215            ));
216        }
217        let json = format!(
218            r#"{{"schemaVersion":2,"mediaType":"application/vnd.oci.image.index.v1+json",
219"artifactType":"application/vnd.pulseengine.varve.layer.v1+json",
220"annotations":{{"eu.pulseengine.varve.layer":"{layer}","eu.pulseengine.varve.channel":"qualified",
221"eu.pulseengine.varve.counter":"1","org.opencontainers.image.created":"2026-08-01T00:00:00Z"}},
222"manifests":[{}]}}"#,
223            entries.join(",")
224        );
225        let _ = layer;
226        view(json.as_bytes()).unwrap()
227    }
228
229    // rivet: verifies REQ-COMPOSE-001
230    #[test]
231    fn a_composition_exposes_both_layers_tools() {
232        let upstream = manifest("2026.08.0", &["wasm-tools", "cargo-component"], &[]);
233        let root = manifest(
234            "2026.08.0",
235            &["rivet", "meld"],
236            &[("sha256:up", "bytecodealliance")],
237        );
238        let inc = includes(&root);
239        assert_eq!(inc.len(), 1);
240        assert_eq!(inc[0].digest, "sha256:up");
241        assert_eq!(inc[0].realm.as_deref(), Some("bytecodealliance"));
242
243        let layers = walk("sha256:root", &root, |d| {
244            (d == "sha256:up").then(|| upstream.clone())
245        })
246        .unwrap();
247        assert_eq!(layers.len(), 2, "root plus the included layer");
248        let tools = union_tools(&layers).unwrap();
249        // The producing half is now answerable alongside the checking half.
250        for t in ["rivet", "meld", "wasm-tools", "cargo-component"] {
251            assert!(tools.contains_key(t), "{t} missing from the composition");
252        }
253        assert_eq!(tools["wasm-tools"], "sha256:up");
254        assert_eq!(tools["rivet"], "sha256:root");
255    }
256
257    // rivet: verifies REQ-COMPOSE-001
258    #[test]
259    fn a_tool_in_two_layers_is_an_error_not_a_silent_choice() {
260        // Both layers ship `wasm-tools`. varve must not pick one.
261        let upstream = manifest("2026.08.0", &["wasm-tools"], &[]);
262        let root = manifest(
263            "2026.08.0",
264            &["wasm-tools"],
265            &[("sha256:up", "bytecodealliance")],
266        );
267        let layers = walk("sha256:root", &root, |d| {
268            (d == "sha256:up").then(|| upstream.clone())
269        })
270        .unwrap();
271        match union_tools(&layers) {
272            Err(ComposeError::AmbiguousTool { tool, .. }) => assert_eq!(tool, "wasm-tools"),
273            other => panic!("expected AmbiguousTool, got {other:?}"),
274        }
275    }
276
277    // rivet: verifies REQ-COMPOSE-001
278    #[test]
279    fn depth_is_bounded_so_a_long_chain_cannot_exhaust_the_walker() {
280        // The bound is what keeps "refused" from meaning "followed until the
281        // process aborts". Re-verification found `verify` recursing without it
282        // and stack-overflowing on a self-referencing store entry; both walkers
283        // are now bounded.
284        let leaf = manifest("2026.08.0", &["leaf"], &[]);
285        // A chain longer than MAX_DEPTH, each link including the next.
286        let chain: Vec<LayerView> = (0..=MAX_DEPTH + 2)
287            .map(|i| manifest("2026.08.0", &["t"], &[(&format!("sha256:{}", i + 1), "r")]))
288            .collect();
289        let err = walk("sha256:0", &chain[0], |d| {
290            let n: usize = d.trim_start_matches("sha256:").parse().ok()?;
291            chain.get(n).cloned().or_else(|| Some(leaf.clone()))
292        })
293        .unwrap_err();
294        assert!(matches!(err, ComposeError::TooDeep), "got {err:?}");
295    }
296
297    // rivet: verifies REQ-COMPOSE-001
298    #[test]
299    fn a_diamond_is_walked_once_not_refused_as_a_cycle() {
300        // A includes B and C; both include D. This terminates and is the most
301        // ordinary composition shape there is — two layers sharing a base.
302        // The first version reported it as a cycle, with a message claiming D
303        // "includes itself". Found by clean-room review.
304        let d = manifest("2026.08.0", &["base"], &[]);
305        let b = manifest("2026.08.0", &["b"], &[("sha256:d", "r")]);
306        let c = manifest("2026.08.0", &["c"], &[("sha256:d", "r")]);
307        let a = manifest("2026.08.0", &["a"], &[("sha256:b", "r"), ("sha256:c", "r")]);
308        let walked = walk("sha256:a", &a, |q| match q {
309            "sha256:b" => Some(b.clone()),
310            "sha256:c" => Some(c.clone()),
311            "sha256:d" => Some(d.clone()),
312            _ => None,
313        })
314        .unwrap();
315        assert_eq!(walked.len(), 4, "A, B, C and D each once: {walked:?}");
316        // …and the shared base's tool resolves exactly once, not ambiguously.
317        let tools = union_tools(&walked).unwrap();
318        assert_eq!(tools["base"], "sha256:d");
319    }
320
321    // rivet: verifies REQ-COMPOSE-001
322    #[test]
323    fn a_cycle_is_refused_not_followed() {
324        // A includes B; B includes A. Following it would not terminate.
325        let a = manifest("2026.08.0", &["x"], &[("sha256:b", "r")]);
326        let b = manifest("2026.08.0", &["y"], &[("sha256:a", "r")]);
327        let (ac, bc) = (a.clone(), b.clone());
328        let err = walk("sha256:a", &a, move |d| match d {
329            "sha256:b" => Some(bc.clone()),
330            "sha256:a" => Some(ac.clone()),
331            _ => None,
332        })
333        .unwrap_err();
334        assert!(matches!(err, ComposeError::Cycle { .. }), "got {err:?}");
335    }
336
337    // rivet: verifies REQ-COMPOSE-001
338    #[test]
339    fn an_uninstalled_include_is_skipped_for_the_caller_to_report() {
340        // walk() does not invent a fetch. A missing layer is the caller's
341        // error to report, with its corrective `varve install`.
342        let root = manifest("2026.08.0", &["rivet"], &[("sha256:missing", "other")]);
343        let layers = walk("sha256:root", &root, |_| None).unwrap();
344        assert_eq!(layers.len(), 1, "only the root resolved");
345        assert_eq!(
346            includes(&root).len(),
347            1,
348            "but the include is still declared"
349        );
350    }
351
352    // rivet: verifies REQ-COMPOSE-001
353    #[test]
354    fn a_layer_without_includes_composes_to_itself() {
355        // Back-compat: every existing layer has no `layer` entries and must
356        // behave exactly as before.
357        let plain = manifest("2026.08.0", &["rivet", "meld"], &[]);
358        assert!(includes(&plain).is_empty());
359        let layers = walk("sha256:root", &plain, |_| None).unwrap();
360        assert_eq!(layers.len(), 1);
361        assert_eq!(union_tools(&layers).unwrap().len(), 2);
362    }
363}
varve_core/compose.rs

varve_core/
compose.rs
