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            paper: None,
274            related_work: vec![],
275            concepts: vec![],
276            problem: None,
277            recipes: vec![],
278            exhibits: vec![],
279            built_on: vec![],
280            node_exhibits: vec![],
281        }
282    }
283
284    #[test]
285    fn all_positions_finite() {
286        let m = simple_manifest();
287        let result = layout(&m, &LayoutOptions::default());
288        for np in &result.positions {
289            assert!(np.pos.x.is_finite(), "NaN/inf x for {}", np.id);
290            assert!(np.pos.y.is_finite(), "NaN/inf y for {}", np.id);
291        }
292    }
293
294    #[test]
295    fn ranks_monotonic_along_child_edges() {
296        let m = simple_manifest();
297        let result = layout(&m, &LayoutOptions::default());
298        let pos_map: std::collections::HashMap<&str, &Point> = result
299            .positions
300            .iter()
301            .map(|np| (np.id.as_str(), &np.pos))
302            .collect();
303        for link in &m.links {
304            if link.kind == LinkKind::Child {
305                let from_y = pos_map[link.from.as_str()].y;
306                let to_y = pos_map[link.to.as_str()].y;
307                assert!(
308                    from_y < to_y,
309                    "rank not monotonic: {} (y={}) -> {} (y={})",
310                    link.from,
311                    from_y,
312                    link.to,
313                    to_y
314                );
315            }
316        }
317    }
318
319    #[test]
320    fn tie_break_stable_across_input_order() {
321        let m1 = simple_manifest();
322        let mut m2 = simple_manifest();
323        m2.nodes.reverse(); // shuffle input order
324        let r1 = layout(&m1, &LayoutOptions::default());
325        let r2 = layout(&m2, &LayoutOptions::default());
326        // Positions are returned in manifest.nodes order, so sort by id.
327        let mut p1: Vec<_> = r1.positions.clone();
328        let mut p2: Vec<_> = r2.positions.clone();
329        p1.sort_by(|a, b| a.id.cmp(&b.id));
330        p2.sort_by(|a, b| a.id.cmp(&b.id));
331        assert_eq!(p1, p2);
332        assert_eq!(r1.bounds, r2.bounds);
333    }
334
335    #[test]
336    fn empty_manifest_produces_zero_bounds() {
337        let m = Manifest {
338            nodes: vec![],
339            links: vec![],
340            bindings: vec![],
341            claims: vec![],
342            bounds: None,
343            paper: None,
344            related_work: vec![],
345            concepts: vec![],
346            problem: None,
347            recipes: vec![],
348            exhibits: vec![],
349            built_on: vec![],
350            node_exhibits: vec![],
351        };
352        let result = layout(&m, &LayoutOptions::default());
353        assert!(result.positions.is_empty());
354        assert_eq!(result.bounds.width, 0.0);
355        assert_eq!(result.bounds.height, 0.0);
356    }
357
358    #[test]
359    fn single_node_has_finite_pos_and_enclosing_bounds() {
360        let m = Manifest {
361            nodes: vec![Node {
362                id: NodeId::new("N01"),
363                kind: NodeKind::Question,
364                label: None,
365                support_level: None,
366                source_refs: vec![],
367                description: None,
368                fields: NodeFields::Question,
369                evidence_notes: vec![],
370                isolated: false,
371                pos: None,
372            }],
373            links: vec![],
374            bindings: vec![],
375            claims: vec![],
376            bounds: None,
377            paper: None,
378            related_work: vec![],
379            concepts: vec![],
380            problem: None,
381            recipes: vec![],
382            exhibits: vec![],
383            built_on: vec![],
384            node_exhibits: vec![],
385        };
386        let opts = LayoutOptions::default();
387        let result = layout(&m, &opts);
388        assert_eq!(result.positions.len(), 1);
389        assert!(result.positions[0].pos.x.is_finite());
390        assert!(result.positions[0].pos.y.is_finite());
391        assert!(result.bounds.width >= opts.node_width);
392        assert!(result.bounds.height >= opts.node_height);
393    }
394
395    #[test]
396    fn bounds_enclose_all_node_rects() {
397        let m = simple_manifest();
398        let opts = LayoutOptions::default();
399        let result = layout(&m, &opts);
400        let half_w = opts.node_width / 2.0;
401        let half_h = opts.node_height / 2.0;
402        for np in &result.positions {
403            assert!(np.pos.x - half_w >= result.bounds.x - 1e-9);
404            assert!(np.pos.y - half_h >= result.bounds.y - 1e-9);
405            assert!(np.pos.x + half_w <= result.bounds.x + result.bounds.width + 1e-9);
406            assert!(np.pos.y + half_h <= result.bounds.y + result.bounds.height + 1e-9);
407        }
408    }
409
410    #[test]
411    fn canonicalize_normalizes_negative_zero() {
412        assert_eq!(canonicalize(-0.0), 0.0);
413        assert_eq!(canonicalize(-0.0).to_bits(), 0.0_f64.to_bits());
414    }
415
416    #[test]
417    fn canonicalize_rounds_to_six_decimals() {
418        let v = 1.23456789;
419        assert_eq!(canonicalize(v), 1.234568);
420    }
421
422    #[test]
423    fn layout_twice_identical() {
424        let m = simple_manifest();
425        let opts = LayoutOptions::default();
426        let r1 = layout(&m, &opts);
427        let r2 = layout(&m, &opts);
428        let j1 = serde_json::to_string(&r1).unwrap();
429        let j2 = serde_json::to_string(&r2).unwrap();
430        assert_eq!(j1, j2);
431    }
432}
ara_core/layout.rs

ara_core/
layout.rs
