ara_core/
layout.rs

1//! Deterministic layered DAG layout (Sugiyama method) for `Manifest`.
2//!
3//! Produces node positions + bounding rect via `dagre-dgl-rs`. All computation
4//! is pure and wasm-safe (no threads, filesystem, randomness, or `SystemTime`).
5//! The same input yields byte-identical JSON on native and wasm32 targets.
6
7use dagre_dgl_rs::{EdgeLabel, Graph, GraphLabel, NodeLabel as DagreNodeLabel};
8
9use std::collections::BTreeMap;
10
11use crate::manifest::{Link, Manifest, Node, NodeId};
12
13/// A 2D point (center of a node).
14#[derive(Debug, Clone, Copy, PartialEq, serde::Serialize, serde::Deserialize)]
15pub struct Point {
16    pub x: f64,
17    pub y: f64,
18}
19
20/// An axis-aligned rectangle (bounding box).
21#[derive(Debug, Clone, Copy, PartialEq, serde::Serialize, serde::Deserialize)]
22pub struct Rect {
23    pub x: f64,
24    pub y: f64,
25    pub width: f64,
26    pub height: f64,
27}
28
29/// Configuration knobs for layout. All values are pinned for determinism.
30#[derive(Debug, Clone)]
31pub struct LayoutOptions {
32    /// Width of every node box (px). Default: 180.
33    pub node_width: f64,
34    /// Height of every node box (px). Default: 60.
35    pub node_height: f64,
36    /// Minimum separation between adjacent nodes in the same rank. Default: 50.
37    pub node_sep: f64,
38    /// Minimum separation between adjacent ranks. Default: 50.
39    pub rank_sep: f64,
40}
41
42impl Default for LayoutOptions {
43    fn default() -> Self {
44        Self {
45            node_width: 180.0,
46            node_height: 60.0,
47            node_sep: 50.0,
48            rank_sep: 50.0,
49        }
50    }
51}
52
53/// Result of running layout on a manifest.
54#[derive(Debug, Clone, PartialEq, serde::Serialize, serde::Deserialize)]
55pub struct LayoutResult {
56    pub positions: Vec<NodePosition>,
57    pub bounds: Rect,
58}
59
60/// The computed position for a single node.
61#[derive(Debug, Clone, PartialEq, serde::Serialize, serde::Deserialize)]
62pub struct NodePosition {
63    pub id: NodeId,
64    pub pos: Point,
65}
66
67/// Computes a layered DAG layout for `manifest` with the given options.
68///
69/// Nodes are inserted in sorted `NodeId` order (the fixed tie-break) so
70/// equal-rank ordering is stable regardless of input shuffling.
71///
72/// # Panics
73///
74/// Debug-asserts that the graph has no cycles (the parse layer already
75/// rejects cycles, so this is a defensive invariant check).
76pub fn layout(manifest: &Manifest, opts: &LayoutOptions) -> LayoutResult {
77    if manifest.nodes.is_empty() {
78        return LayoutResult {
79            positions: Vec::new(),
80            bounds: Rect {
81                x: 0.0,
82                y: 0.0,
83                width: 0.0,
84                height: 0.0,
85            },
86        };
87    }
88
89    let mut g = Graph::default();
90    g.set_graph(GraphLabel {
91        rankdir: Some("TB".to_string()),
92        nodesep: Some(opts.node_sep),
93        ranksep: Some(opts.rank_sep),
94        ..Default::default()
95    });
96
97    // Insert nodes in sorted NodeId order for a stable tie-break.
98    let mut sorted_ids: Vec<&NodeId> = manifest.nodes.iter().map(|n| &n.id).collect();
99    sorted_ids.sort();
100    for id in &sorted_ids {
101        g.set_node(
102            id.as_str(),
103            DagreNodeLabel {
104                width: opts.node_width,
105                height: opts.node_height,
106                ..Default::default()
107            },
108        );
109    }
110
111    // Add edges. Only Child + DependsOn links exist; both are used for ranking.
112    debug_assert!(
113        !has_cycle(&manifest.nodes, &manifest.links),
114        "cycle reached layout — parse should have rejected this"
115    );
116    for link in &manifest.links {
117        g.set_edge(
118            link.from.as_str(),
119            link.to.as_str(),
120            EdgeLabel::default(),
121            None,
122        );
123    }
124
125    dagre_dgl_rs::layout(&mut g);
126
127    // Extract positions and compute bounds.
128    let mut positions = Vec::with_capacity(manifest.nodes.len());
129    let mut min_x = f64::INFINITY;
130    let mut min_y = f64::INFINITY;
131    let mut max_x = f64::NEG_INFINITY;
132    let mut max_y = f64::NEG_INFINITY;
133
134    for node in &manifest.nodes {
135        let nl = g.node(node.id.as_str());
136        let x = canonicalize(nl.x.unwrap_or(0.0));
137        let y = canonicalize(nl.y.unwrap_or(0.0));
138        positions.push(NodePosition {
139            id: node.id.clone(),
140            pos: Point { x, y },
141        });
142
143        let half_w = opts.node_width / 2.0;
144        let half_h = opts.node_height / 2.0;
145        min_x = min_x.min(x - half_w);
146        min_y = min_y.min(y - half_h);
147        max_x = max_x.max(x + half_w);
148        max_y = max_y.max(y + half_h);
149    }
150
151    let bounds = Rect {
152        x: canonicalize(min_x),
153        y: canonicalize(min_y),
154        width: canonicalize(max_x - min_x),
155        height: canonicalize(max_y - min_y),
156    };
157
158    LayoutResult { positions, bounds }
159}
160
161/// Canonicalize an f64: round to 6 decimal places and normalize -0.0 to 0.0.
162fn canonicalize(v: f64) -> f64 {
163    let rounded = (v * 1_000_000.0).round() / 1_000_000.0;
164    if rounded == 0.0 { 0.0 } else { rounded }
165}
166
167/// Cheap cycle check (DFS three-color). Only used in debug_assert.
168fn has_cycle(nodes: &[Node], links: &[Link]) -> bool {
169    let mut adj: BTreeMap<&str, Vec<&str>> = BTreeMap::new();
170    for link in links {
171        adj.entry(link.from.as_str())
172            .or_default()
173            .push(link.to.as_str());
174    }
175    let mut color: BTreeMap<&str, u8> = BTreeMap::new();
176    for node in nodes {
177        if color.get(node.id.as_str()).copied().unwrap_or(0) == 0
178            && visit_cycle(node.id.as_str(), &adj, &mut color)
179        {
180            return true;
181        }
182    }
183    false
184}
185
186fn visit_cycle<'a>(
187    u: &'a str,
188    adj: &BTreeMap<&'a str, Vec<&'a str>>,
189    color: &mut BTreeMap<&'a str, u8>,
190) -> bool {
191    color.insert(u, 1);
192    if let Some(neighbors) = adj.get(u) {
193        for &v in neighbors {
194            match color.get(v).copied().unwrap_or(0) {
195                0 => {
196                    if visit_cycle(v, adj, color) {
197                        return true;
198                    }
199                }
200                1 => return true,
201                _ => {}
202            }
203        }
204    }
205    color.insert(u, 2);
206    false
207}
208
209#[cfg(test)]
210mod tests {
211    use super::*;
212    use crate::manifest::{Link, LinkKind, Manifest, Node, NodeFields, NodeId, NodeKind};
213
214    fn simple_manifest() -> Manifest {
215        Manifest {
216            nodes: vec![
217                Node {
218                    id: NodeId::new("N01"),
219                    kind: NodeKind::Question,
220                    label: Some("Q?".into()),
221                    support_level: None,
222                    source_refs: vec![],
223                    description: None,
224                    fields: NodeFields::Question,
225                    evidence_notes: vec![],
226                    isolated: false,
227                    pos: None,
228                },
229                Node {
230                    id: NodeId::new("N02"),
231                    kind: NodeKind::Experiment,
232                    label: Some("Exp".into()),
233                    support_level: None,
234                    source_refs: vec![],
235                    description: None,
236                    fields: NodeFields::Experiment { result: None },
237                    evidence_notes: vec![],
238                    isolated: false,
239                    pos: None,
240                },
241                Node {
242                    id: NodeId::new("N03"),
243                    kind: NodeKind::Decision,
244                    label: Some("Dec".into()),
245                    support_level: None,
246                    source_refs: vec![],
247                    description: None,
248                    fields: NodeFields::Decision {
249                        choice: None,
250                        alternatives: vec![],
251                        rationale: None,
252                    },
253                    evidence_notes: vec![],
254                    isolated: false,
255                    pos: None,
256                },
257            ],
258            links: vec![
259                Link {
260                    from: NodeId::new("N01"),
261                    to: NodeId::new("N02"),
262                    kind: LinkKind::Child,
263                },
264                Link {
265                    from: NodeId::new("N01"),
266                    to: NodeId::new("N03"),
267                    kind: LinkKind::Child,
268                },
269            ],
270            bindings: vec![],
271            claims: vec![],
272            bounds: None,
273        }
274    }
275
276    #[test]
277    fn all_positions_finite() {
278        let m = simple_manifest();
279        let result = layout(&m, &LayoutOptions::default());
280        for np in &result.positions {
281            assert!(np.pos.x.is_finite(), "NaN/inf x for {}", np.id);
282            assert!(np.pos.y.is_finite(), "NaN/inf y for {}", np.id);
283        }
284    }
285
286    #[test]
287    fn ranks_monotonic_along_child_edges() {
288        let m = simple_manifest();
289        let result = layout(&m, &LayoutOptions::default());
290        let pos_map: std::collections::HashMap<&str, &Point> = result
291            .positions
292            .iter()
293            .map(|np| (np.id.as_str(), &np.pos))
294            .collect();
295        for link in &m.links {
296            if link.kind == LinkKind::Child {
297                let from_y = pos_map[link.from.as_str()].y;
298                let to_y = pos_map[link.to.as_str()].y;
299                assert!(
300                    from_y < to_y,
301                    "rank not monotonic: {} (y={}) -> {} (y={})",
302                    link.from,
303                    from_y,
304                    link.to,
305                    to_y
306                );
307            }
308        }
309    }
310
311    #[test]
312    fn tie_break_stable_across_input_order() {
313        let m1 = simple_manifest();
314        let mut m2 = simple_manifest();
315        m2.nodes.reverse(); // shuffle input order
316        let r1 = layout(&m1, &LayoutOptions::default());
317        let r2 = layout(&m2, &LayoutOptions::default());
318        // Positions are returned in manifest.nodes order, so sort by id.
319        let mut p1: Vec<_> = r1.positions.clone();
320        let mut p2: Vec<_> = r2.positions.clone();
321        p1.sort_by(|a, b| a.id.cmp(&b.id));
322        p2.sort_by(|a, b| a.id.cmp(&b.id));
323        assert_eq!(p1, p2);
324        assert_eq!(r1.bounds, r2.bounds);
325    }
326
327    #[test]
328    fn empty_manifest_produces_zero_bounds() {
329        let m = Manifest {
330            nodes: vec![],
331            links: vec![],
332            bindings: vec![],
333            claims: vec![],
334            bounds: None,
335        };
336        let result = layout(&m, &LayoutOptions::default());
337        assert!(result.positions.is_empty());
338        assert_eq!(result.bounds.width, 0.0);
339        assert_eq!(result.bounds.height, 0.0);
340    }
341
342    #[test]
343    fn single_node_has_finite_pos_and_enclosing_bounds() {
344        let m = Manifest {
345            nodes: vec![Node {
346                id: NodeId::new("N01"),
347                kind: NodeKind::Question,
348                label: None,
349                support_level: None,
350                source_refs: vec![],
351                description: None,
352                fields: NodeFields::Question,
353                evidence_notes: vec![],
354                isolated: false,
355                pos: None,
356            }],
357            links: vec![],
358            bindings: vec![],
359            claims: vec![],
360            bounds: None,
361        };
362        let opts = LayoutOptions::default();
363        let result = layout(&m, &opts);
364        assert_eq!(result.positions.len(), 1);
365        assert!(result.positions[0].pos.x.is_finite());
366        assert!(result.positions[0].pos.y.is_finite());
367        assert!(result.bounds.width >= opts.node_width);
368        assert!(result.bounds.height >= opts.node_height);
369    }
370
371    #[test]
372    fn bounds_enclose_all_node_rects() {
373        let m = simple_manifest();
374        let opts = LayoutOptions::default();
375        let result = layout(&m, &opts);
376        let half_w = opts.node_width / 2.0;
377        let half_h = opts.node_height / 2.0;
378        for np in &result.positions {
379            assert!(np.pos.x - half_w >= result.bounds.x - 1e-9);
380            assert!(np.pos.y - half_h >= result.bounds.y - 1e-9);
381            assert!(np.pos.x + half_w <= result.bounds.x + result.bounds.width + 1e-9);
382            assert!(np.pos.y + half_h <= result.bounds.y + result.bounds.height + 1e-9);
383        }
384    }
385
386    #[test]
387    fn canonicalize_normalizes_negative_zero() {
388        assert_eq!(canonicalize(-0.0), 0.0);
389        assert_eq!(canonicalize(-0.0).to_bits(), 0.0_f64.to_bits());
390    }
391
392    #[test]
393    fn canonicalize_rounds_to_six_decimals() {
394        let v = 1.23456789;
395        assert_eq!(canonicalize(v), 1.234568);
396    }
397
398    #[test]
399    fn layout_twice_identical() {
400        let m = simple_manifest();
401        let opts = LayoutOptions::default();
402        let r1 = layout(&m, &opts);
403        let r2 = layout(&m, &opts);
404        let j1 = serde_json::to_string(&r1).unwrap();
405        let j2 = serde_json::to_string(&r2).unwrap();
406        assert_eq!(j1, j2);
407    }
408}
ara_core/layout.rs

ara_core/
layout.rs
