Doc system test

Dependency flattening

How one template version's dependency tree becomes one run order - post-order, siblings by version id, shared nodes once with merged presets, root last.

Meta block front matter of this doc
namespaces
  • durian.cloud/cyanprint/composition
  • durian.cloud/cyanprint/registry
type
algorithm
code
  • sulfone.iridium/cyancoordinator/src/operations/composition/resolver.rs
  • sulfone.iridium/cyanregistry/src/http/models/template_res.rs

The problem. A dependency tree must run one node at a time, children before parents, each shared node once. The order also decides which file wins a file clash, so it must be the same on every machine and every run.

The idea. Walk the tree depth-first and add each node after its children (post-order), visiting siblings in version id order, then add the root last. A node already in the list is not added again; its new preset answers are merged in instead.

The picture shows the walk for one edge.

flowchart TD
  S["sort the node's edges by child version id"] --> E{next edge}
  E --> D{"child already in the run order?"}
  D -->|yes| M["add the edge's missing preset ids<br/>(first value wins)"] --> E
  D -->|no| V{"child already visited?"}
  V -->|"yes (a back edge)"| K["skip the edge and its presets"] --> E
  V -->|no| F["fetch child by version id<br/>mark visited"] --> R["walk the child's edges"] --> P["append the child with this edge's presets"] --> E
  E -->|none left| Z["the caller appends the root, no presets"]
One edge of the walk

How it works

The code's name for this is DependencyResolver; it has nothing to do with a conflict resolver.

  1. Mark the root visited before the walk, so a back edge to the root cannot add it twice.
  2. Sort the edges of the current node by child version id (plain string order). The cyan.yaml order is ignored.
  3. For each edge, convert its presets to answers (string, bool, string list; others dropped).
  4. Already in the order? The child is shared: add each preset id it does not have yet, and go to the next edge. The first value for an id always wins.
  5. Already visited, not yet in the order? The child is an ancestor still being walked (a cycle). Skip the edge, presets included. No error.
  6. New child: fetch it from the registry by version id, mark it visited, walk its own edges (steps 2 to 6), then append it with this edge's presets.
  7. Append the root last, with no presets.

The result is the run order. Every node in it is run or served from cache in that order, and its output is laid in that order (dependency layering), so a later node wins a clash with no agreed conflict resolver.

Here is the real code.

sulfone.iridiumcyancoordinator/src/operations/composition/resolver.rs
  1. lines 170-189Entry: mark the root visited, walk, then append the root with an empty preset map.
    cyancoordinator/src/operations/composition/resolver.rs:170-189rust
    impl DependencyResolver for DefaultDependencyResolver {
    fn resolve_dependencies(
    &self,
    template: &TemplateVersionRes,
    ) -> Result<Vec<ResolvedDependency>, Box<dyn Error + Send>> {
    let mut visited: HashSet<String> = HashSet::new();
    // Mark root as visited BEFORE traversal to prevent cycles back to root
    // from causing the root to be added twice (once from within recursion,
    // once as the final root append).
    visited.insert(template.principal.id.clone());
    let mut flattened = self.flatten_dependencies(template, &mut visited)?;
    // Add root template at the end (post-order) with no preset answers
    flattened.push(ResolvedDependency {
    template: template.clone(),
    preset_answers: HashMap::new(),
    });
    Ok(flattened)
    }
  2. lines 63-71One shared output list for the whole walk. Edges are cloned and sorted by version id.
    cyancoordinator/src/operations/composition/resolver.rs:63-71rust
    fn flatten_impl(
    template: &TemplateVersionRes,
    visited: &mut HashSet<String>,
    flattened: &mut Vec<ResolvedDependency>,
    fetch_template: &dyn Fn(String) -> Result<TemplateVersionRes, Box<dyn Error + Send>>,
    ) -> Result<(), Box<dyn Error + Send>> {
    // Sort dependencies by ID to ensure deterministic execution order
    let mut sorted_deps = template.templates.clone();
    sorted_deps.sort_by(|a, b| a.id.cmp(&b.id));
  3. lines 74-94Convert presets; if the child is already in the list, fill only missing ids and continue.
    cyancoordinator/src/operations/composition/resolver.rs:74-94rust
    for dep_ref in &sorted_deps {
    // Extract preset_answers from the dependency ref
    let preset_answers: HashMap<String, Answer> = dep_ref
    .preset_answers
    .iter()
    .filter_map(|(key, value)| {
    serde_json_value_to_answer(value).map(|answer| (key.clone(), answer))
    })
    .collect();
    // R2 Fix: Check if this template_id was already added to flattened (cross-branch).
    // If so, MERGE preset_answers instead of skipping or adding duplicate.
    if let Some(existing) = flattened
    .iter_mut()
    .find(|d| d.template.principal.id == dep_ref.id)
    {
    for (key, answer) in preset_answers {
    existing.preset_answers.entry(key).or_insert(answer);
    }
    continue;
    }
  4. lines 96-113A visited child is skipped. Otherwise fetch by id, mark visited, recurse, then append (post-order).
    cyancoordinator/src/operations/composition/resolver.rs:96-113rust
    // Check if we've already processed this template_id to prevent infinite recursion
    if visited.contains(&dep_ref.id) {
    continue;
    }
    // Fetch dependency template
    let dep_template = fetch_template(dep_ref.id.clone())?;
    visited.insert(dep_ref.id.clone());
    // Recursive call for nested dependencies (shares the same flattened vector)
    flatten_impl(&dep_template, visited, flattened, fetch_template)?;
    // Add this dependency after its nested dependencies (post-order)
    flattened.push(ResolvedDependency {
    template: dep_template,
    preset_answers,
    });

Worked example: web:5 and web:6

Step through the walk for web:5 (step 1 of the shop example). Version ids are shortened to four characters.

Flattening web:5
  1. Start

    Root web:5 is marked visited. Its edges sorted: 7a90 (docker:7), b2e4 (node-base:3). cyan.yaml listed node-base first; the sort puts docker first.

    visitede5d0
    pathweb:5
    order(empty)
  2. Edge 7a90

    Not in the order, not visited. Fetch docker:7, mark it, walk it: no edges. Append it.

    visitede5d0, 7a90
    pathweb:5 > docker:7
    orderdocker:7
  3. Edge b2e4

    Preset module_type esm. New: fetch node-base:3, mark it, walk its edges.

    visitede5d0, 7a90, b2e4
    pathweb:5 > node-base:3
    orderdocker:7
  4. Edge 3c1f

    lint:2 is new and has no edges. Append it.

    visitede5d0, 7a90, b2e4, 3c1f
    pathweb:5 > node-base:3 > lint:2
    orderdocker:7, lint:2
  5. Back in web:5

    node-base:3's edges are done. Append it with its preset.

    orderdocker:7, lint:2, node-base:3 (module_type esm)
  6. Root

    Append web:5 with no presets.

    orderdocker:7, lint:2, node-base:3, web:5

web:6 walks the same way. Its edges sort as 8b11 (docker:8), then b2e4 (node-base:3), so the order is docker:8, lint:2, node-base:3, web:6.

Step through a variation: suppose docker:7 also pinned node-base:3 with preset module_type: cjs.

A shared node with two presets
  1. Edge 7a90

    docker:7 is walked first, so its edge to node-base:3 is reached first.

    pathweb:5 > docker:7 > node-base:3
    orderlint:2, node-base:3 (cjs)
  2. docker:7 appended

    After its child.

    orderlint:2, node-base:3 (cjs), docker:7
  3. Edge b2e4 from web:5

    node-base:3 is already in the order. module_type is already set, so esm is ignored.

    orderlint:2, node-base:3 (cjs), docker:7
  4. Root

    web:5 last. node-base:3 now runs before docker:7, and web:5 asked for esm but gets cjs.

    orderlint:2, node-base:3, docker:7, web:5

Why it works this way

Hard cases

  • The author's order does not count. web:5 lists node-base first, yet docker runs first and its package.json sits under node-base's. Re-pushing with new version ids can change the order and so the clash winners.
  • A shared node runs where it is first finished, which is before every parent that pins it. Its files are laid once, at that place.
  • First value wins, silently. In a diamond, the parent walked first sets each preset id; the other parent's different value is dropped with no warning.
  • A back edge loses its presets. A skipped edge never merges, even for ids the node lacks.
  • Two ids for one fact. "Visited" uses the edge's id, "already in the order" uses the fetched node's id. Nothing checks they are equal, or that the edge's version number matches the node.
  • A failed fetch stops the walk. One registry error aborts the whole composition; there is no retry. Fetches are one at a time.
  • Groups are walked like any node and keep their place in the order, though they never run.

Questions for the designer

  1. Why version id order rather than the order in cyan.yaml? (The successor sulfone.lite chooses declaration order for dependency layers: lite docs/requirements/simplification-spec.md, line 119.)
  2. Should a cycle be refused with an error instead of skipped?
  3. In a diamond with two different preset values, which parent should win, and should it warn?
  4. Should a shared node run at its first place or its last place in the walk?