Skip to main content

merman_layout_elk/
lib.rs

1#![forbid(unsafe_code)]
2
3//! Optional ELK layout engine integration for `merman`.
4//!
5//! Source-port policy:
6//! - The historical Mermaid adapter derivation is
7//!   https://github.com/mermaid-js/mermaid/blob/21f72f07ea22c0af48a3149c550654e80d8e40cb/packages/mermaid/src/rendering-util/layout-algorithms/elk/render.ts.
8//! - The historical `elkjs@0.9.3` derivation is
9//!   https://github.com/kieler/elkjs/tree/a8304cf79fde75bc2ab1a89d28320f53f8637436.
10//! - The historical Eclipse ELK Java derivation is
11//!   https://github.com/eclipse-elk/elk/tree/62d5909f96fad541bc101ad52dabaece6b7eab7e,
12//! - Mermaid 12.3.0's exact engine oracle is elkjs 0.12.0 at
13//!   https://github.com/kieler/elkjs/tree/ff5771d7165445c42c408bb8a090c8035272218c,
14//!   compared with Eclipse ELK 0.12.0 at
15//!   https://github.com/eclipse-elk/elk/tree/323312916048544e4e594eab3303cdb0d01e2929.
16//!   elkjs CI clones ELK master, so this tag is not a proven unique npm build input.
17//!   The engine crate's `MERMAID_12_3_DELTA.md` records ported deltas and unsupported options.
18//!
19//! The crate exposes one Mermaid adapter over the source-backed ELK providers. Additional providers
20//! handle flat graphs and recursive containers, including Mermaid's explicit metadata presets
21//! and cross-boundary downgrade. Remaining cross-provider boundary routes are rejected explicitly.
22//! New layout behavior must carry a pinned Mermaid or Eclipse ELK source reference.
23
24use std::collections::{HashMap, HashSet, VecDeque};
25use std::fmt::Write as _;
26use std::num::NonZeroU64;
27
28#[cfg(test)]
29mod adapter_tests;
30mod container;
31mod flat;
32mod model;
33#[cfg(test)]
34mod terminal_labels_tests;
35use container::ContainerMode;
36use merman_elk_layered as source_port;
37pub use model::*;
38pub use source_port::{
39    GraphExecution, HierarchySweepDebugTrace, HierarchySweepNodeDebug, LayeredPhase,
40    NoopWorkControl, ProcessorKind, WorkControl, WorkError,
41};
42
43/// The nonzero random seed captured by the owner of one render/layout operation.
44///
45/// This token is intentionally separate from ELK's signed `randomSeed` option. The latter keeps
46/// Eclipse ELK's Java semantics for every nonzero value and treats zero as an unseeded sentinel.
47/// Passing this token to [`layout_with_operation_seed`] supplies the deterministic replacement
48/// for that sentinel without mutating the source option.
49#[derive(Debug, Clone, Copy, PartialEq, Eq)]
50pub struct ElkOperationSeed(source_port::OperationSeed);
51
52impl ElkOperationSeed {
53    /// Creates an ELK token from the seed captured by an operation owner.
54    pub const fn from_operation_seed(seed: NonZeroU64) -> Self {
55        Self(source_port::OperationSeed::from_operation_seed(seed))
56    }
57
58    const fn source_port_seed(self) -> source_port::OperationSeed {
59        self.0
60    }
61}
62
63use source_port::{
64    ElkDirection, ElkInputEdge, ElkInputGraph, ElkInputLabel, ElkInputNode, LGraph, LNodeKind,
65    LPoint, LayeredOptions as SourceLayeredOptions, NodeLabelPlacement, PortRef,
66};
67
68const MEASURED_LABEL_PLACEHOLDER: &str = "\u{fffc}";
69
70/// A guarded diagnostic session for inspecting the source-backed layered pipeline.
71///
72/// The underlying ELK graph remains private. Every method that executes processors enters a
73/// fallible source-port pipeline boundary, so `randomSeed = 0` is either rejected or resolved
74/// from the [`ElkOperationSeed`] supplied at construction.
75///
76/// The former raw re-export is intentionally unavailable:
77///
78/// ```compile_fail
79/// use merman_layout_elk::source_port;
80/// ```
81pub struct SourcePhaseDiagnostics {
82    graph: LGraph,
83}
84
85impl Drop for SourcePhaseDiagnostics {
86    fn drop(&mut self) {
87        detach_source_graph_hierarchy_for_drop(&mut self.graph);
88    }
89}
90
91impl SourcePhaseDiagnostics {
92    /// Builds a raw diagnostic session. Executing a graph that retains ELK's zero seed sentinel
93    /// returns the same typed error as [`layout`].
94    pub fn from_graph(graph: &Graph) -> Result<Self> {
95        Self::from_graph_with_optional_operation_seed(graph, None)
96    }
97
98    /// Builds a diagnostic session using an operation-owned seed for ELK's zero sentinel.
99    pub fn from_graph_with_operation_seed(
100        graph: &Graph,
101        operation_seed: ElkOperationSeed,
102    ) -> Result<Self> {
103        Self::from_graph_with_optional_operation_seed(graph, Some(operation_seed))
104    }
105
106    fn from_graph_with_optional_operation_seed(
107        graph: &Graph,
108        operation_seed: Option<ElkOperationSeed>,
109    ) -> Result<Self> {
110        if graph.options.algorithm != Algorithm::Layered {
111            return Err(Error::LayeredDiagnosticsRequired);
112        }
113        let input = graph_to_source_input(graph)?;
114        let lgraph = match operation_seed {
115            Some(operation_seed) => source_port::import_graph_with_operation_seed(
116                &input,
117                operation_seed.source_port_seed(),
118            ),
119            None => source_port::import_graph(&input),
120        }
121        .map_err(Error::SourceImport)?;
122        Ok(Self { graph: lgraph })
123    }
124
125    /// Runs the source-backed pipeline until a phase completes.
126    pub fn execute_until(&mut self, target: LayeredPhase) -> Result<Vec<ProcessorKind>> {
127        source_port::execute_processors_until(&mut self.graph, target)
128            .map_err(Error::SourcePipeline)
129    }
130
131    /// Runs the source-backed pipeline until a processor completes.
132    pub fn execute_until_processor(&mut self, target: ProcessorKind) -> Result<Vec<ProcessorKind>> {
133        source_port::execute_processors_until_processor(&mut self.graph, target)
134            .map_err(Error::SourcePipeline)
135    }
136
137    /// Runs every currently ported processor for a flat graph.
138    pub fn execute_all(&mut self) -> Result<Vec<ProcessorKind>> {
139        source_port::execute_ported_processors(&mut self.graph).map_err(Error::SourcePipeline)
140    }
141
142    /// Runs the compound pipeline until a phase completes.
143    pub fn execute_compound_until(&mut self, target: LayeredPhase) -> Result<Vec<GraphExecution>> {
144        source_port::execute_ported_compound_processors_until(&mut self.graph, target)
145            .map_err(Error::SourcePipeline)
146    }
147
148    /// Runs the compound pipeline until a processor completes.
149    pub fn execute_compound_until_processor(
150        &mut self,
151        target: ProcessorKind,
152    ) -> Result<Vec<GraphExecution>> {
153        source_port::execute_ported_compound_processors_until_processor(&mut self.graph, target)
154            .map_err(Error::SourcePipeline)
155    }
156
157    /// Runs every currently ported compound processor.
158    pub fn execute_compound_all(&mut self) -> Result<Vec<GraphExecution>> {
159        source_port::execute_ported_compound_processors(&mut self.graph)
160            .map_err(Error::SourcePipeline)
161    }
162
163    /// Runs the guarded compound prefix used by the hierarchical crossing-sweep diagnostic.
164    pub fn inspect_compound_crossings_after_processor(
165        &mut self,
166        target: ProcessorKind,
167    ) -> Result<(Vec<GraphExecution>, Option<HierarchySweepDebugTrace>)> {
168        source_port::inspect_compound_crossings_after_processor(&mut self.graph, target)
169            .map_err(Error::SourcePipeline)
170    }
171
172    /// Formats the private source graph for human diagnostics without exposing executable phase
173    /// APIs or the mutable `LGraph` itself.
174    pub fn graph_dump(&self) -> String {
175        let mut output = String::new();
176        write_source_graph_dump(&mut output, &self.graph, 0)
177            .expect("writing to String cannot fail");
178        output
179    }
180}
181
182#[derive(Debug, thiserror::Error)]
183pub enum Error {
184    #[error(transparent)]
185    NodeSize(#[from] source_port::NodeSizeError),
186    #[error("phase diagnostics require the Layered algorithm")]
187    LayeredDiagnosticsRequired,
188    #[error("phase diagnostics require one scope; use layout for separately scheduled containers")]
189    SeparateScopesDiagnosticsUnsupported,
190    #[error("unsupported ELK hierarchy/provider combination for edge `{edge_id}`")]
191    UnsupportedCrossProviderEdge { edge_id: String },
192    #[error(transparent)]
193    Box(#[from] source_port::algorithms::box_layout::Error),
194    #[error(transparent)]
195    Rectpacking(#[from] source_port::algorithms::rectpacking::Error),
196    #[error(transparent)]
197    Force(#[from] source_port::algorithms::force::Error),
198    #[error(transparent)]
199    Stress(#[from] source_port::algorithms::stress::Error),
200    #[error(transparent)]
201    MrTree(#[from] source_port::algorithms::mrtree::Error),
202    #[error(transparent)]
203    Radial(#[from] source_port::algorithms::radial::Error),
204    #[error(transparent)]
205    SporeOverlap(#[from] source_port::algorithms::spore_overlap::Error),
206    #[error(transparent)]
207    RandomSeed(#[from] source_port::RandomSeedError),
208    #[error(transparent)]
209    SourceImport(#[from] merman_elk_layered::ImportError),
210    #[error(transparent)]
211    SourcePipeline(#[from] merman_elk_layered::PipelineError),
212    #[error(transparent)]
213    Work(#[from] WorkError),
214}
215
216impl Error {
217    pub const fn work_error(&self) -> Option<WorkError> {
218        match self {
219            Self::Box(source_port::algorithms::box_layout::Error::Work(error))
220            | Self::Rectpacking(source_port::algorithms::rectpacking::Error::Work(error))
221            | Self::Rectpacking(source_port::algorithms::rectpacking::Error::Box(
222                source_port::algorithms::box_layout::Error::Work(error),
223            ))
224            | Self::Force(source_port::algorithms::force::Error::Work(error))
225            | Self::Stress(source_port::algorithms::stress::Error::Work(error))
226            | Self::Stress(source_port::algorithms::stress::Error::Force(
227                source_port::algorithms::force::Error::Work(error),
228            ))
229            | Self::MrTree(source_port::algorithms::mrtree::Error::Work(error))
230            | Self::Radial(source_port::algorithms::radial::Error::Work(error))
231            | Self::SporeOverlap(source_port::algorithms::spore_overlap::Error::Work(error)) => {
232                Some(*error)
233            }
234            Self::Work(error) => Some(*error),
235            Self::SourceImport(source_port::ImportError::Work(error))
236            | Self::SourcePipeline(source_port::PipelineError::Work(error)) => Some(*error),
237            _ => None,
238        }
239    }
240}
241
242pub type Result<T> = std::result::Result<T, Error>;
243
244/// Executes the selected source-backed ELK provider. Unsupported cross-provider boundary edges
245/// return a typed error instead of flattening the graph or substituting the Layered provider.
246pub fn layout(graph: &Graph) -> Result<LayoutResult> {
247    let mut work_control = NoopWorkControl;
248    layout_with_work_control(graph, &mut work_control)
249}
250
251/// Executes Mermaid's ELK adapter with caller-owned checked work control.
252pub fn layout_with_work_control(
253    graph: &Graph,
254    work_control: &mut dyn WorkControl,
255) -> Result<LayoutResult> {
256    layout_scopes(graph, None, work_control)
257}
258
259/// Executes Mermaid's ELK adapter using the seed captured by its owning operation.
260///
261/// Normal Mermaid adapter graphs keep their source default seed of `1`, so this policy affects
262/// only an explicitly configured unseeded graph. [`layout`] is the raw/diagnostic API and rejects
263/// the sentinel; this API is for render or layout operation owners that intentionally provide a
264/// single immutable operation seed.
265pub fn layout_with_operation_seed(
266    graph: &Graph,
267    operation_seed: ElkOperationSeed,
268) -> Result<LayoutResult> {
269    let mut work_control = NoopWorkControl;
270    layout_with_operation_seed_and_work_control(graph, operation_seed, &mut work_control)
271}
272
273/// Executes Mermaid's ELK adapter with one operation-owned seed and checked work control.
274pub fn layout_with_operation_seed_and_work_control(
275    graph: &Graph,
276    operation_seed: ElkOperationSeed,
277    work_control: &mut dyn WorkControl,
278) -> Result<LayoutResult> {
279    layout_scopes(graph, Some(operation_seed.source_port_seed()), work_control)
280}
281
282fn graph_to_source_input(graph: &Graph) -> Result<ElkInputGraph> {
283    let index = HierarchyIndex::build(graph, &mut NoopWorkControl)?;
284    if index
285        .scopes
286        .iter()
287        .any(|scope| scope.algorithm != Algorithm::Layered)
288    {
289        return Err(Error::LayeredDiagnosticsRequired);
290    }
291    if index.scopes.len() > 1 {
292        return Err(Error::SeparateScopesDiagnosticsUnsupported);
293    }
294    let options = layered_options_to_source(graph);
295    let node_ids_with_direct_children = graph
296        .nodes
297        .iter()
298        .filter_map(|node| node.parent.as_deref())
299        .collect::<HashSet<_>>();
300
301    Ok(ElkInputGraph {
302        id: graph.id.clone(),
303        options,
304        nodes: graph
305            .nodes
306            .iter()
307            .enumerate()
308            .map(|(node_index, node)| ElkInputNode {
309                id: node.id.clone(),
310                width: if index.children[node_index].is_empty() {
311                    node.width
312                } else {
313                    0.0
314                },
315                height: if index.children[node_index].is_empty() {
316                    node.height
317                } else {
318                    0.0
319                },
320                parent: node.parent.clone(),
321                direction: index.container_modes[node_index]
322                    .direction(node)
323                    .map(direction_to_source),
324                hierarchy_handling: (node.kind == NodeKind::Group)
325                    .then(|| hierarchy_handling_to_source(index.resolved_handling[node_index])),
326                layer_constraint: node.layer_constraint.map(layer_constraint_to_source),
327                port_alignment: node.port_alignment.map(port_alignment_to_source),
328                port_constraints: None,
329                node_label_placement: match node.kind {
330                    NodeKind::Group => NodeLabelPlacement::InsideTopCenter,
331                    NodeKind::Leaf => NodeLabelPlacement::Fixed,
332                },
333                node_flexibility: if node.kind == NodeKind::Group {
334                    source_port::NodeFlexibility::PortPosition
335                } else {
336                    source_port::NodeFlexibility::None
337                },
338                ports_surrounding: (node.kind == NodeKind::Group).then_some(
339                    source_port::SpacingMargin {
340                        top: 12.0,
341                        right: 12.0,
342                        bottom: 12.0,
343                        left: 12.0,
344                    },
345                ),
346                nested_options: (node.kind == NodeKind::Group).then(|| {
347                    Box::new(resolved_container_options(
348                        graph,
349                        node,
350                        index.container_modes[node_index],
351                        graph.direction,
352                        graph.options.layered.hierarchy_handling,
353                    ))
354                }),
355                // Mermaid's leaf labels are already included in the painted node dimensions.
356                // Only non-empty groups expose an ELK label; retain all other measurements in
357                // the adapter model for SVG rendering without creating provider label margins.
358                label: if node.kind == NodeKind::Group
359                    && node_ids_with_direct_children.contains(node.id.as_str())
360                {
361                    node.label.map(|label| {
362                        ElkInputLabel::center(
363                            node.label_text
364                                .as_deref()
365                                .unwrap_or(MEASURED_LABEL_PLACEHOLDER),
366                            label.width,
367                            label.height,
368                        )
369                    })
370                } else {
371                    None
372                },
373            })
374            .collect(),
375        edges: graph
376            .edges
377            .iter()
378            .map(|edge| ElkInputEdge {
379                id: edge.id.clone(),
380                source: edge.source.clone(),
381                target: edge.target.clone(),
382                labels: source_edge_labels(edge, true, true, true),
383                minlen: edge.minlen,
384                inside_self_loops_yo: edge.inside_self_loops_yo,
385                model_order: None,
386                priority_direction: 0,
387                priority_shortness: 0,
388                priority_straightness: 0,
389            })
390            .collect(),
391    })
392}
393
394fn source_edge_labels(edge: &Edge, center: bool, start: bool, end: bool) -> Vec<ElkInputLabel> {
395    let mut labels: Vec<_> = edge
396        .label
397        .filter(|_| center)
398        .into_iter()
399        .map(|label| ElkInputLabel::center(MEASURED_LABEL_PLACEHOLDER, label.width, label.height))
400        .collect();
401    labels.extend(
402        edge.terminal_labels
403            .iter()
404            .filter(|terminal| if terminal.key.at_start() { start } else { end })
405            .map(|terminal| ElkInputLabel {
406                source_index: Some(terminal.key.source_index()),
407                text: MEASURED_LABEL_PLACEHOLDER.to_owned(),
408                width: terminal.label.width,
409                height: terminal.label.height,
410                placement: if terminal.key.at_start() {
411                    source_port::EdgeLabelPlacement::Tail
412                } else {
413                    source_port::EdgeLabelPlacement::Head
414                },
415                inline: false,
416            }),
417    );
418    labels
419}
420
421fn apply_root_inside_top_center_label_padding(
422    options: &mut SourceLayeredOptions,
423    label: Label,
424) -> Result<()> {
425    options.include_inside_top_center_label_minimum(source_port::LSize {
426        width: label.width,
427        height: label.height,
428    })?;
429    if label.height > 0.0 {
430        options.padding.top += label.height + options.node_labels_padding.top;
431    }
432    Ok(())
433}
434
435#[derive(Debug)]
436struct HierarchyIndex<'a> {
437    graph: &'a Graph,
438    parent: Vec<Option<usize>>,
439    children: Vec<Vec<usize>>,
440    container_modes: Vec<ContainerMode>,
441    resolved_handling: Vec<HierarchyHandling>,
442    node_scope: Vec<usize>,
443    edge_model_order: Vec<usize>,
444    child_scope_by_anchor: Vec<Option<usize>>,
445    scopes: Vec<ScopePlan>,
446    postorder: Vec<usize>,
447}
448
449#[derive(Debug)]
450struct ScopePlan {
451    algorithm: Algorithm,
452    parent: Option<usize>,
453    anchor: Option<usize>,
454    depth: usize,
455    seed_scope: source_port::GraphSeedScope,
456    direction: Direction,
457    handling: HierarchyHandling,
458    nodes: Vec<usize>,
459    children: Vec<usize>,
460    edges: Vec<ScopedEdge>,
461    owned_edges: Vec<usize>,
462}
463
464#[derive(Debug, Clone, Copy)]
465enum ScopedEndpoint {
466    Node(usize),
467    ParentBoundary { scope: usize, connects_node: bool },
468}
469
470type ScopeEdgePiece = (
471    usize,
472    ScopedEndpoint,
473    ScopedEndpoint,
474    source_port::CompoundEdgeSegment,
475);
476
477#[derive(Debug)]
478struct ScopedEdge {
479    original: usize,
480    source: ScopedEndpoint,
481    target: ScopedEndpoint,
482    segment: Option<source_port::CompoundEdgeSegment>,
483    segment_order: Option<usize>,
484    segment_count: usize,
485    carries_label: bool,
486}
487
488#[derive(Debug)]
489struct ScopeLayout {
490    layout: LayoutResult,
491    size: source_port::LSize,
492    edge_metadata: HashMap<String, ScopeEdgeMetadata>,
493    content_shifts: HashMap<String, Point>,
494    size_constraints_active: bool,
495    label_margin: source_port::LMargin,
496}
497
498#[derive(Debug, Clone, Copy)]
499struct ScopeEdgeMetadata {
500    original: usize,
501    segment: Option<SegmentedEdgeMetadata>,
502}
503
504#[derive(Debug, Clone, Copy)]
505struct SegmentedEdgeMetadata {
506    segment: source_port::CompoundEdgeSegment,
507    model_order: Option<usize>,
508    order: usize,
509    count: usize,
510}
511
512fn layout_scopes(
513    graph: &Graph,
514    operation_seed: Option<source_port::OperationSeed>,
515    work_control: &mut dyn WorkControl,
516) -> Result<LayoutResult> {
517    let index = HierarchyIndex::build(graph, work_control)?;
518    work_control.check(index.scopes.len())?;
519    work_control.charge(index.scopes.len())?;
520    let mut arena = std::iter::repeat_with(|| None)
521        .take(index.scopes.len())
522        .collect::<Vec<Option<ScopeLayout>>>();
523
524    for &scope in &index.postorder {
525        if index.scopes[scope].algorithm != Algorithm::Layered {
526            let (input, edge_metadata) =
527                index.materialize_flat_scope(scope, &arena, work_control)?;
528            let mut output = flat::layout(
529                &input,
530                &index.scopes[scope].seed_scope,
531                index.scopes[scope]
532                    .anchor
533                    .map_or(flat::ScopeContext::Root, |anchor| {
534                        flat::ScopeContext::Container {
535                            node: &graph.nodes[anchor],
536                            mode: index.container_modes[anchor],
537                        }
538                    }),
539                &index.scopes[scope]
540                    .nodes
541                    .iter()
542                    .map(|&node| flat::NodeContext {
543                        mode: index.container_modes[node],
544                        size_constraints_active: index.child_scope_by_anchor[node]
545                            .and_then(|child| arena[child].as_ref())
546                            .is_some_and(|child| child.size_constraints_active),
547                        label_margin: index.child_scope_by_anchor[node]
548                            .and_then(|child| arena[child].as_ref())
549                            .map_or_else(source_port::LMargin::default, |child| child.label_margin),
550                    })
551                    .collect::<Vec<_>>(),
552                operation_seed,
553                work_control,
554            )?;
555            index.complete_flat_hierarchy_edges(scope, &arena, &mut output, work_control)?;
556            arena[scope] = Some(ScopeLayout {
557                layout: output.layout,
558                size: output.size,
559                edge_metadata,
560                content_shifts: output.content_shifts,
561                size_constraints_active: output.size_constraints_active,
562                label_margin: container::scope_title_margin(
563                    index.scopes[scope]
564                        .anchor
565                        .and_then(|node| graph.nodes[node].label),
566                    output.size,
567                ),
568            });
569            continue;
570        }
571        let (input, segments, edge_metadata) =
572            index.materialize_scope(scope, &arena, work_control)?;
573        let mut lgraph = match operation_seed {
574            Some(operation_seed) => {
575                source_port::import_graph_with_operation_seed_at_seed_scope_and_segments_with_work_control(
576                    &input,
577                    operation_seed,
578                    &index.scopes[scope].seed_scope,
579                    &segments,
580                    work_control,
581                )
582            }
583            None => source_port::import_graph_at_seed_scope_and_segments_with_work_control(
584                &input,
585                &index.scopes[scope].seed_scope,
586                &segments,
587                work_control,
588            ),
589        }
590        .map_err(Error::SourceImport)?;
591        if source_graph_requires_compound_pipeline(&lgraph) {
592            source_port::execute_ported_compound_processors_with_work_control(
593                &mut lgraph,
594                work_control,
595            )
596            .map_err(Error::SourcePipeline)?;
597        } else {
598            source_port::execute_ported_processors_with_work_control(&mut lgraph, work_control)
599                .map_err(Error::SourcePipeline)?;
600        }
601        let export_work = source_graph_output_work_units(&lgraph)?;
602        work_control.check(export_work)?;
603        work_control.charge(export_work)?;
604        let size = actual_source_graph_size(&lgraph);
605        arena[scope] = Some(ScopeLayout {
606            layout: source_graph_to_layout_result(&lgraph),
607            size,
608            edge_metadata,
609            content_shifts: HashMap::new(),
610            size_constraints_active: false,
611            label_margin: container::scope_title_margin(
612                index.scopes[scope]
613                    .anchor
614                    .and_then(|node| graph.nodes[node].label),
615                size,
616            ),
617        });
618    }
619
620    flatten_scope_layouts(&index, arena, work_control)
621}
622
623impl<'a> HierarchyIndex<'a> {
624    fn materialize_flat_scope(
625        &self,
626        scope_index: usize,
627        arena: &[Option<ScopeLayout>],
628        work: &mut dyn WorkControl,
629    ) -> Result<(Graph, HashMap<String, ScopeEdgeMetadata>)> {
630        let scope = &self.scopes[scope_index];
631        // Only Layered-owned boundary segments reach this branch. Upstream Layered rejects
632        // endpoints inside a scope handled by another provider; do not invent external ports.
633        if let Some(edge) = scope.edges.iter().find(|edge| edge.segment.is_some()) {
634            return Err(Error::UnsupportedCrossProviderEdge {
635                edge_id: self.graph.edges[edge.original].id.clone(),
636            });
637        }
638        let units = scope
639            .nodes
640            .len()
641            .checked_add(scope.edges.len())
642            .ok_or(WorkError::ArithmeticOverflow)?;
643        work.check(units)?;
644        work.charge(units)?;
645        let nodes = scope
646            .nodes
647            .iter()
648            .map(|&index| {
649                let mut node = self.graph.nodes[index].clone();
650                node.parent = None;
651                if let Some(child) = self.child_scope_by_anchor[index] {
652                    let size = arena[child]
653                        .as_ref()
654                        .expect("children are laid out in postorder")
655                        .size;
656                    node.width = size.width;
657                    node.height = size.height;
658                } else if node.kind == NodeKind::Group {
659                    // Empty groups have no ELK container options or node labels.
660                    node.kind = NodeKind::Leaf;
661                    node.label_text = None;
662                }
663                node
664            })
665            .collect();
666        let edges = scope
667            .edges
668            .iter()
669            .filter(|edge| !self.is_flat_hierarchy_edge(scope_index, edge))
670            .map(|edge| {
671                let source = &self.graph.edges[edge.original];
672                // Non-layered providers never place terminal labels. Avoid cloning the
673                // caller-owned terminal-label payload into a graph that cannot consume it.
674                Edge {
675                    id: source.id.clone(),
676                    source: source.source.clone(),
677                    target: source.target.clone(),
678                    label: source.label,
679                    terminal_labels: Vec::new(),
680                    minlen: source.minlen,
681                    inside_self_loops_yo: source.inside_self_loops_yo,
682                }
683            })
684            .collect();
685        let metadata = scope
686            .edges
687            .iter()
688            .map(|edge| {
689                (
690                    self.graph.edges[edge.original].id.clone(),
691                    ScopeEdgeMetadata {
692                        original: edge.original,
693                        segment: None,
694                    },
695                )
696            })
697            .collect();
698        let mut options = self.graph.options.clone();
699        options.algorithm = scope.algorithm;
700        Ok((
701            Graph {
702                id: scope
703                    .anchor
704                    .map(|node| self.graph.nodes[node].id.clone())
705                    .unwrap_or_else(|| self.graph.id.clone()),
706                direction: scope.direction,
707                nodes,
708                edges,
709                options,
710                spacing: self.graph.spacing,
711            },
712            metadata,
713        ))
714    }
715
716    fn is_flat_hierarchy_edge(&self, scope: usize, edge: &ScopedEdge) -> bool {
717        matches!((edge.source, edge.target), (ScopedEndpoint::Node(source), ScopedEndpoint::Node(target))
718            if self.node_scope[source] != scope || self.node_scope[target] != scope)
719    }
720
721    fn complete_flat_hierarchy_edges(
722        &self,
723        scope: usize,
724        arena: &[Option<ScopeLayout>],
725        output: &mut flat::FlatLayout,
726        work: &mut dyn WorkControl,
727    ) -> Result<()> {
728        let hierarchical = self.scopes[scope]
729            .edges
730            .iter()
731            .filter(|edge| self.is_flat_hierarchy_edge(scope, edge))
732            .collect::<Vec<_>>();
733        if hierarchical.is_empty() {
734            return Ok(());
735        }
736        work.check(hierarchical.len())?;
737        work.charge(hierarchical.len())?;
738        let spore = self.scopes[scope].algorithm == Algorithm::SporeOverlap;
739        let mut geometry = HashMap::new();
740        if spore {
741            let mut required_scopes = HashSet::new();
742            for edge in &hierarchical {
743                let (ScopedEndpoint::Node(source), ScopedEndpoint::Node(target)) =
744                    (edge.source, edge.target)
745                else {
746                    unreachable!("flat hierarchy endpoints are original nodes")
747                };
748                for node in [source, target] {
749                    if Some(node) == self.scopes[scope].anchor {
750                        continue;
751                    }
752                    required_scopes.insert(self.node_scope[node]);
753                    if let Some(parent) = self.parent[node]
754                        && Some(parent) != self.scopes[scope].anchor
755                    {
756                        required_scopes.insert(self.node_scope[parent]);
757                    }
758                }
759            }
760            for required in required_scopes {
761                let nodes = if required == scope {
762                    &output.layout.nodes
763                } else {
764                    &arena[required]
765                        .as_ref()
766                        .expect("descendant scopes are complete")
767                        .layout
768                        .nodes
769                };
770                work.check(nodes.len())?;
771                work.charge(nodes.len())?;
772                geometry.extend(nodes.iter().map(|node| (node.id.as_str(), node)));
773            }
774        }
775        let mut completed = Vec::with_capacity(hierarchical.len());
776        for edge in hierarchical {
777            let original = &self.graph.edges[edge.original];
778            let mut points = Vec::new();
779            if spore {
780                let endpoint = |endpoint| {
781                    let ScopedEndpoint::Node(index) = endpoint else {
782                        unreachable!("flat endpoint")
783                    };
784                    if Some(index) == self.scopes[scope].anchor {
785                        // An edge to the layout parent is contained in that parent's inner
786                        // graph. At this export point the parent has not been positioned yet.
787                        return (
788                            Point {
789                                x: output.size.width / 2.0,
790                                y: output.size.height / 2.0,
791                            },
792                            output.size.width,
793                            output.size.height,
794                        );
795                    }
796                    let node = geometry[self.graph.nodes[index].id.as_str()];
797                    let mut center = Point {
798                        x: node.x,
799                        y: node.y,
800                    };
801                    if let Some(parent) = self.parent[index]
802                        && Some(parent) != self.scopes[scope].anchor
803                    {
804                        if self.node_scope[parent] == self.node_scope[index] {
805                            let parent = geometry[self.graph.nodes[parent].id.as_str()];
806                            center.x -= parent.x - parent.width / 2.0;
807                            center.y -= parent.y - parent.height / 2.0;
808                        } else {
809                            let parent_scope = self.node_scope[parent];
810                            let shifts = if parent_scope == scope {
811                                &output.content_shifts
812                            } else {
813                                &arena[parent_scope]
814                                    .as_ref()
815                                    .expect("parent scope is complete")
816                                    .content_shifts
817                            };
818                            if let Some(shift) = shifts.get(&self.graph.nodes[parent].id) {
819                                center.x += shift.x;
820                                center.y += shift.y;
821                            }
822                        }
823                    }
824                    (center, node.width, node.height)
825                };
826                let (source, sw, sh) = endpoint(edge.source);
827                let (target, tw, th) = endpoint(edge.target);
828                // SPOrE ElkGraphImporter.applyPositions reads each endpoint's own local
829                // coordinates, including for hierarchical edges. Do not add ancestor offsets.
830                let start = flat::clip_spore_endpoint(source, target, sw, sh);
831                let end = flat::clip_spore_endpoint(target, start, tw, th);
832                points.extend([start, end]);
833            }
834            completed.push(EdgeLayout {
835                id: original.id.clone(),
836                points,
837                labels: original
838                    .label
839                    .into_iter()
840                    .map(|label| EdgeLabelLayout {
841                        terminal: None,
842                        x: output.edge_translation.x,
843                        y: output.edge_translation.y,
844                        width: label.width,
845                        height: label.height,
846                    })
847                    .collect(),
848            });
849        }
850        output.layout.edges.extend(completed);
851        Ok(())
852    }
853
854    fn build(graph: &'a Graph, work_control: &mut dyn WorkControl) -> Result<Self> {
855        let unique_items = graph
856            .nodes
857            .len()
858            .checked_add(graph.edges.len())
859            .ok_or(WorkError::ArithmeticOverflow)?;
860        work_control.check(unique_items)?;
861        work_control.charge(unique_items)?;
862
863        let mut node_by_id = HashMap::with_capacity(graph.nodes.len());
864        for (index, node) in graph.nodes.iter().enumerate() {
865            if node_by_id.insert(node.id.as_str(), index).is_some() {
866                return Err(source_port::ImportError::DuplicateNode {
867                    id: node.id.clone(),
868                }
869                .into());
870            }
871        }
872
873        // FlowDB normalizes every edge ID before invoking Mermaid's ELK adapter: duplicate
874        // user-provided IDs receive unique generated identities. Scope metadata may key by that
875        // identity, but non-canonical duplicate input must not silently alias original edges.
876        work_control.check(graph.edges.len())?;
877        work_control.charge(graph.edges.len())?;
878        let mut edge_ids = HashSet::with_capacity(graph.edges.len());
879        for edge in &graph.edges {
880            if !edge_ids.insert(edge.id.as_str()) {
881                return Err(source_port::ImportError::DuplicateEdge {
882                    id: edge.id.clone(),
883                }
884                .into());
885            }
886        }
887
888        let mut parent = vec![None; graph.nodes.len()];
889        let mut children = vec![Vec::new(); graph.nodes.len()];
890        let mut roots = Vec::new();
891        for (index, node) in graph.nodes.iter().enumerate() {
892            if let Some(parent_id) = node.parent.as_deref() {
893                let Some(&parent_index) = node_by_id.get(parent_id) else {
894                    return Err(source_port::ImportError::MissingParent {
895                        node_id: node.id.clone(),
896                        parent_id: parent_id.to_string(),
897                    }
898                    .into());
899                };
900                parent[index] = Some(parent_index);
901                children[parent_index].push(index);
902            } else {
903                roots.push(index);
904            }
905        }
906        detect_parent_cycles(graph, &parent)?;
907
908        let (container_modes, include_children) =
909            container::resolve(graph, &parent, &children, &node_by_id, work_control)?;
910
911        work_control.check(1)?;
912        work_control.charge(1)?;
913        let mut scopes = vec![ScopePlan {
914            algorithm: graph.options.algorithm,
915            parent: None,
916            anchor: None,
917            depth: 0,
918            seed_scope: source_port::GraphSeedScope::root(graph.id.as_str()),
919            direction: graph.direction,
920            handling: graph.options.layered.hierarchy_handling,
921            nodes: Vec::new(),
922            children: Vec::new(),
923            edges: Vec::new(),
924            owned_edges: Vec::new(),
925        }];
926        let mut node_scope = vec![0usize; graph.nodes.len()];
927        let mut resolved_handling =
928            vec![graph.options.layered.hierarchy_handling; graph.nodes.len()];
929        let mut child_scope_by_anchor = vec![None; graph.nodes.len()];
930        let mut hierarchy_preorder = Vec::with_capacity(graph.nodes.len());
931        let mut preorder_position = vec![0usize; graph.nodes.len()];
932        let mut search = roots
933            .into_iter()
934            .rev()
935            .map(|node| {
936                (
937                    node,
938                    0usize,
939                    graph.options.layered.hierarchy_handling,
940                    graph.direction,
941                )
942            })
943            .collect::<Vec<_>>();
944        while let Some((node_index, scope, parent_handling, parent_direction)) = search.pop() {
945            let node = &graph.nodes[node_index];
946            let mode = container_modes[node_index];
947            let handling = if node.kind == NodeKind::Group {
948                if include_children[node_index] {
949                    HierarchyHandling::IncludeChildren
950                } else if matches!(mode, ContainerMode::Explicit(_)) {
951                    HierarchyHandling::SeparateChildren
952                } else {
953                    node.hierarchy_handling.unwrap_or(parent_handling)
954                }
955            } else {
956                parent_handling
957            };
958            let direction = mode.direction(node).unwrap_or(parent_direction);
959            // Unconfigured containers resolve to ELK's default provider, not their parent's
960            // non-layered provider. A direction option explicitly selects the diagram provider.
961            let algorithm = if let ContainerMode::Explicit(algorithm) = mode {
962                algorithm
963            } else if mode.direction(node).is_some() {
964                graph.options.algorithm
965            } else {
966                Algorithm::Layered
967            };
968            resolved_handling[node_index] = handling;
969            node_scope[node_index] = scope;
970            preorder_position[node_index] = hierarchy_preorder.len();
971            hierarchy_preorder.push(node_index);
972
973            let separates = node.kind == NodeKind::Group
974                && !children[node_index].is_empty()
975                && (parent_handling == HierarchyHandling::SeparateChildren
976                    || handling == HierarchyHandling::SeparateChildren
977                    || scopes[scope].algorithm != Algorithm::Layered
978                    || algorithm != scopes[scope].algorithm);
979            let child_scope = if separates {
980                work_control.check(1)?;
981                work_control.charge(1)?;
982                let child_scope = scopes.len();
983                let seed_scope = scopes[scope].seed_scope.child(node.id.as_str());
984                scopes.push(ScopePlan {
985                    algorithm,
986                    parent: Some(scope),
987                    anchor: Some(node_index),
988                    depth: scopes[scope].depth + 1,
989                    seed_scope,
990                    direction: mode
991                        .direction(node)
992                        .unwrap_or(if algorithm == Algorithm::MrTree {
993                            Direction::Down
994                        } else {
995                            Direction::Right
996                        }),
997                    handling,
998                    nodes: Vec::new(),
999                    children: Vec::new(),
1000                    edges: Vec::new(),
1001                    owned_edges: Vec::new(),
1002                });
1003                scopes[scope].children.push(child_scope);
1004                child_scope_by_anchor[node_index] = Some(child_scope);
1005                child_scope
1006            } else {
1007                scope
1008            };
1009            search.extend(children[node_index].iter().rev().map(|child| {
1010                (
1011                    *child,
1012                    child_scope,
1013                    handling,
1014                    if separates {
1015                        scopes[child_scope].direction
1016                    } else {
1017                        direction
1018                    },
1019                )
1020            }));
1021        }
1022        for node in 0..graph.nodes.len() {
1023            scopes[node_scope[node]].nodes.push(node);
1024        }
1025
1026        let mut edge_owner_scope = vec![0usize; graph.edges.len()];
1027        let mut edge_model_order = vec![0usize; graph.edges.len()];
1028        for (edge_index, edge) in graph.edges.iter().enumerate() {
1029            let Some(&source) = node_by_id.get(edge.source.as_str()) else {
1030                return Err(source_port::ImportError::MissingEndpoint {
1031                    edge_id: edge.id.clone(),
1032                    node_id: edge.source.clone(),
1033                }
1034                .into());
1035            };
1036            let Some(&target) = node_by_id.get(edge.target.as_str()) else {
1037                return Err(source_port::ImportError::MissingEndpoint {
1038                    edge_id: edge.id.clone(),
1039                    node_id: edge.target.clone(),
1040                }
1041                .into());
1042            };
1043            let source_scope = node_scope[source];
1044            let target_scope = node_scope[target];
1045            if source_scope == target_scope {
1046                let owner = source_scope;
1047                edge_owner_scope[edge_index] = owner;
1048                edge_model_order[edge_index] = scopes[owner].owned_edges.len();
1049                scopes[owner].owned_edges.push(edge_index);
1050                scopes[owner].edges.push(ScopedEdge {
1051                    original: edge_index,
1052                    source: ScopedEndpoint::Node(source),
1053                    target: ScopedEndpoint::Node(target),
1054                    segment: None,
1055                    segment_order: None,
1056                    segment_count: 0,
1057                    carries_label: true,
1058                });
1059                continue;
1060            }
1061
1062            // Mermaid owns a cross-scope edge at the endpoint-inclusive common ancestor. Build
1063            // that owner and ELK's required boundary sections in one parent-chain pass.
1064            let (owner, mut pieces) = scope_edge_segments(
1065                &scopes,
1066                source,
1067                target,
1068                source_scope,
1069                target_scope,
1070                work_control,
1071            )?;
1072            edge_owner_scope[edge_index] = owner;
1073            edge_model_order[edge_index] = scopes[owner].owned_edges.len();
1074            scopes[owner].owned_edges.push(edge_index);
1075            if scopes[owner].algorithm == Algorithm::Radial {
1076                // Radial uses hierarchical incoming edges to select its root and may traverse
1077                // successors in other scopes. The flat kernel cannot represent that node domain;
1078                // keep this raw-adapter combination unsupported instead of silently changing roots.
1079                return Err(Error::UnsupportedCrossProviderEdge {
1080                    edge_id: edge.id.clone(),
1081                });
1082            }
1083            if scopes[owner].algorithm != Algorithm::Layered {
1084                // Force/MrTree importers exclude hierarchical edges; packing providers never
1085                // route them. SPOrE exports the original contained edge after node placement.
1086                // None of these providers imports Layered's synthetic boundary segments.
1087                let containing_scope = pieces
1088                    .iter()
1089                    .find_map(|(scope, source, target, _)| {
1090                        [source, target]
1091                            .into_iter()
1092                            .any(|endpoint| {
1093                                matches!(
1094                                    endpoint,
1095                                    ScopedEndpoint::ParentBoundary {
1096                                        connects_node: true,
1097                                        ..
1098                                    }
1099                                )
1100                            })
1101                            .then_some(*scope)
1102                    })
1103                    .unwrap_or(owner);
1104                if scopes[containing_scope].algorithm == Algorithm::Layered {
1105                    // ELK Layered cannot import a parent endpoint belonging to another
1106                    // provider's scope (as opposed to an ordinary descendant-to-peer edge).
1107                    return Err(Error::UnsupportedCrossProviderEdge {
1108                        edge_id: edge.id.clone(),
1109                    });
1110                }
1111                scopes[containing_scope].edges.push(ScopedEdge {
1112                    original: edge_index,
1113                    source: ScopedEndpoint::Node(source),
1114                    target: ScopedEndpoint::Node(target),
1115                    segment: None,
1116                    segment_order: None,
1117                    segment_count: 0,
1118                    carries_label: true,
1119                });
1120                continue;
1121            }
1122            let label_piece = edge.label.map(|_| compound_center_segment(&pieces));
1123            let segment_count = pieces.len();
1124            for (piece_index, (scope, source, target, segment)) in pieces.drain(..).enumerate() {
1125                scopes[scope].edges.push(ScopedEdge {
1126                    original: edge_index,
1127                    source,
1128                    target,
1129                    segment: Some(segment),
1130                    segment_order: Some(piece_index),
1131                    segment_count,
1132                    carries_label: label_piece == Some(piece_index),
1133                });
1134            }
1135        }
1136
1137        let include_order_work = scopes
1138            .iter()
1139            .filter(|scope| {
1140                scope.handling == HierarchyHandling::IncludeChildren && scope.edges.len() >= 2
1141            })
1142            .try_fold(graph.nodes.len(), |work, scope| {
1143                let edge_work = scope
1144                    .edges
1145                    .len()
1146                    .checked_mul(3)
1147                    .ok_or(WorkError::ArithmeticOverflow)?;
1148                work.checked_add(scope.nodes.len())
1149                    .and_then(|work| work.checked_add(scope.owned_edges.len()))
1150                    .and_then(|work| work.checked_add(edge_work))
1151                    .ok_or(WorkError::ArithmeticOverflow)
1152            })?;
1153        if scopes.iter().any(|scope| {
1154            scope.handling == HierarchyHandling::IncludeChildren && scope.edges.len() >= 2
1155        }) {
1156            work_control.check(include_order_work)?;
1157            work_control.charge(include_order_work)?;
1158
1159            let mut subtree_size = vec![1usize; graph.nodes.len()];
1160            for node in hierarchy_preorder.iter().rev().copied() {
1161                if let Some(parent) = parent[node] {
1162                    subtree_size[parent] = subtree_size[parent]
1163                        .checked_add(subtree_size[node])
1164                        .ok_or(WorkError::ArithmeticOverflow)?;
1165                }
1166            }
1167            for (scope_index, scope) in scopes.iter_mut().enumerate() {
1168                if scope.handling != HierarchyHandling::IncludeChildren || scope.edges.len() < 2 {
1169                    continue;
1170                }
1171                order_scope_edges_like_elk_importer(
1172                    scope,
1173                    scope_index,
1174                    &parent,
1175                    &children,
1176                    &node_scope,
1177                    &resolved_handling,
1178                    &preorder_position,
1179                    &subtree_size,
1180                );
1181                let previous_owned = std::mem::take(&mut scope.owned_edges);
1182                for &original in &previous_owned {
1183                    edge_model_order[original] = usize::MAX;
1184                }
1185                for scoped in &scope.edges {
1186                    if edge_owner_scope[scoped.original] == scope_index
1187                        && edge_model_order[scoped.original] == usize::MAX
1188                    {
1189                        edge_model_order[scoped.original] = scope.owned_edges.len();
1190                        scope.owned_edges.push(scoped.original);
1191                    }
1192                }
1193                for original in previous_owned {
1194                    if edge_model_order[original] == usize::MAX {
1195                        edge_model_order[original] = scope.owned_edges.len();
1196                        scope.owned_edges.push(original);
1197                    }
1198                }
1199            }
1200        }
1201
1202        let mut postorder = Vec::with_capacity(scopes.len());
1203        let mut frames = vec![(0usize, false)];
1204        while let Some((scope, expanded)) = frames.pop() {
1205            if expanded {
1206                postorder.push(scope);
1207                continue;
1208            }
1209            frames.push((scope, true));
1210            frames.extend(
1211                scopes[scope]
1212                    .children
1213                    .iter()
1214                    .rev()
1215                    .map(|child| (*child, false)),
1216            );
1217        }
1218
1219        Ok(Self {
1220            graph,
1221            parent,
1222            children,
1223            container_modes,
1224            resolved_handling,
1225            node_scope,
1226            edge_model_order,
1227            child_scope_by_anchor,
1228            scopes,
1229            postorder,
1230        })
1231    }
1232
1233    fn materialize_scope(
1234        &self,
1235        scope_index: usize,
1236        arena: &[Option<ScopeLayout>],
1237        work_control: &mut dyn WorkControl,
1238    ) -> Result<(
1239        ElkInputGraph,
1240        Vec<source_port::ElkInputEdgeSegment>,
1241        HashMap<String, ScopeEdgeMetadata>,
1242    )> {
1243        let scope = &self.scopes[scope_index];
1244        let labels = scope.edges.iter().try_fold(0usize, |count, scoped| {
1245            count
1246                .checked_add(self.graph.edges[scoped.original].terminal_labels.len())
1247                .ok_or(WorkError::ArithmeticOverflow)
1248        })?;
1249        let materialized = scope
1250            .nodes
1251            .len()
1252            .checked_add(scope.edges.len())
1253            .and_then(|count| count.checked_add(labels))
1254            .ok_or(WorkError::ArithmeticOverflow)?;
1255        work_control.check(materialized)?;
1256        work_control.charge(materialized)?;
1257
1258        let mut options = if let Some(anchor) = scope.anchor {
1259            resolved_container_options(
1260                self.graph,
1261                &self.graph.nodes[anchor],
1262                self.container_modes[anchor],
1263                scope.direction,
1264                scope.handling,
1265            )
1266        } else {
1267            layered_options_to_source_for(self.graph, scope.direction, scope.handling)
1268        };
1269        if let Some(label) = scope.anchor.and_then(|node| self.graph.nodes[node].label) {
1270            apply_root_inside_top_center_label_padding(&mut options, label)?;
1271        }
1272
1273        let nodes = scope
1274            .nodes
1275            .iter()
1276            .map(|node_index| {
1277                let source = &self.graph.nodes[*node_index];
1278                let child_layout =
1279                    self.child_scope_by_anchor[*node_index].and_then(|child| arena[child].as_ref());
1280                let child_size = child_layout.map(|layout| layout.size);
1281                // Mermaid removes a non-empty group's explicit size before ELK layout. A parent
1282                // scope must therefore consume the completed child extent, not the input size.
1283                let width = child_size.map(|size| size.width).unwrap_or_else(|| {
1284                    if self.children[*node_index].is_empty() {
1285                        source.width
1286                    } else {
1287                        0.0
1288                    }
1289                });
1290                let height = child_size.map(|size| size.height).unwrap_or_else(|| {
1291                    if self.children[*node_index].is_empty() {
1292                        source.height
1293                    } else {
1294                        0.0
1295                    }
1296                });
1297                let size = if child_layout.is_some_and(|layout| layout.size_constraints_active) {
1298                    source_port::inside_top_center_micro_layout(
1299                        source_port::LSize { width, height },
1300                        self.container_modes[*node_index].minimum(source),
1301                        source.label.map(|label| source_port::LSize {
1302                            width: label.width,
1303                            height: label.height,
1304                        }),
1305                    )?
1306                    .0
1307                } else {
1308                    source_port::LSize { width, height }
1309                };
1310                Ok::<_, Error>(ElkInputNode {
1311                    id: source.id.clone(),
1312                    width: size.width,
1313                    height: size.height,
1314                    parent: self.parent[*node_index]
1315                        .filter(|parent| self.node_scope[*parent] == scope_index)
1316                        .map(|parent| self.graph.nodes[parent].id.clone()),
1317                    direction: self.container_modes[*node_index]
1318                        .direction(source)
1319                        .map(direction_to_source),
1320                    hierarchy_handling: (source.kind == NodeKind::Group)
1321                        .then(|| hierarchy_handling_to_source(self.resolved_handling[*node_index])),
1322                    layer_constraint: source.layer_constraint.map(layer_constraint_to_source),
1323                    port_alignment: source.port_alignment.map(port_alignment_to_source),
1324                    port_constraints: None,
1325                    node_label_placement: match source.kind {
1326                        NodeKind::Group => NodeLabelPlacement::InsideTopCenter,
1327                        NodeKind::Leaf => NodeLabelPlacement::Fixed,
1328                    },
1329                    node_flexibility: if source.kind == NodeKind::Group {
1330                        source_port::NodeFlexibility::PortPosition
1331                    } else {
1332                        source_port::NodeFlexibility::None
1333                    },
1334                    ports_surrounding: (source.kind == NodeKind::Group).then_some(
1335                        source_port::SpacingMargin {
1336                            top: 12.0,
1337                            right: 12.0,
1338                            bottom: 12.0,
1339                            left: 12.0,
1340                        },
1341                    ),
1342                    nested_options: (source.kind == NodeKind::Group).then(|| {
1343                        Box::new(resolved_container_options(
1344                            self.graph,
1345                            source,
1346                            self.container_modes[*node_index],
1347                            scope.direction,
1348                            scope.handling,
1349                        ))
1350                    }),
1351                    // Mermaid attaches an ELK label only when childrenById contains the group.
1352                    // Leaf measurements and empty-group titles are paint metadata, not margins.
1353                    label: if source.kind == NodeKind::Group
1354                        && !self.children[*node_index].is_empty()
1355                    {
1356                        source.label.map(|label| {
1357                            ElkInputLabel::center(
1358                                source
1359                                    .label_text
1360                                    .as_deref()
1361                                    .unwrap_or(MEASURED_LABEL_PLACEHOLDER),
1362                                label.width,
1363                                label.height,
1364                            )
1365                        })
1366                    } else {
1367                        None
1368                    },
1369                })
1370            })
1371            .collect::<Result<Vec<_>>>()?;
1372
1373        let mut edges = Vec::new();
1374        let mut segments = Vec::new();
1375        let mut edge_metadata = HashMap::new();
1376        let uses_edge_model_order = layout_uses_edge_model_order(self.graph);
1377        for (scope_edge_order, scoped) in scope.edges.iter().enumerate() {
1378            let source = &self.graph.edges[scoped.original];
1379            let model_order = uses_edge_model_order.then_some(if scoped.segment.is_some() {
1380                // A boundary segment inherits its original edge owner's ordinal even when this
1381                // particular piece is materialized in a descendant scope.
1382                self.edge_model_order[scoped.original]
1383            } else {
1384                // Ordinary edges follow the importer-visible order of this materialized scope.
1385                scope_edge_order
1386            });
1387            let input_edge = ElkInputEdge {
1388                id: source.id.clone(),
1389                source: source.source.clone(),
1390                target: source.target.clone(),
1391                labels: source_edge_labels(
1392                    source,
1393                    scoped.carries_label,
1394                    scoped.segment_order.is_none_or(|order| order == 0),
1395                    scoped
1396                        .segment_order
1397                        .is_none_or(|order| order + 1 == scoped.segment_count),
1398                ),
1399                minlen: source.minlen,
1400                inside_self_loops_yo: source.inside_self_loops_yo,
1401                model_order,
1402                priority_direction: 0,
1403                priority_shortness: 0,
1404                priority_straightness: 0,
1405            };
1406            let segment_metadata = scoped.segment.map(|segment| SegmentedEdgeMetadata {
1407                segment,
1408                model_order,
1409                order: scoped
1410                    .segment_order
1411                    .expect("segmented edge must carry its original path order"),
1412                count: scoped.segment_count,
1413            });
1414            edge_metadata.insert(
1415                source.id.clone(),
1416                ScopeEdgeMetadata {
1417                    original: scoped.original,
1418                    segment: segment_metadata,
1419                },
1420            );
1421            if let Some(segment) = scoped.segment {
1422                segments.push(source_port::ElkInputEdgeSegment {
1423                    edge: input_edge,
1424                    source: self.segment_endpoint(scoped.source),
1425                    target: self.segment_endpoint(scoped.target),
1426                    segment,
1427                    // Model order is local to the owning scope, while external-port identity must
1428                    // be unique among every segment materialized in this scope. Conflating the two
1429                    // lets edges with different owners accidentally reuse the same hierarchy port.
1430                    edge_order: scope_edge_order,
1431                });
1432            } else {
1433                edges.push(input_edge);
1434            }
1435        }
1436
1437        Ok((
1438            ElkInputGraph {
1439                id: scope
1440                    .anchor
1441                    .map(|node| self.graph.nodes[node].id.clone())
1442                    .unwrap_or_else(|| self.graph.id.clone()),
1443                options,
1444                nodes,
1445                edges,
1446            },
1447            segments,
1448            edge_metadata,
1449        ))
1450    }
1451
1452    fn segment_endpoint(
1453        &self,
1454        endpoint: ScopedEndpoint,
1455    ) -> source_port::ElkInputEdgeSegmentEndpoint {
1456        match endpoint {
1457            ScopedEndpoint::Node(node) => source_port::ElkInputEdgeSegmentEndpoint::Node {
1458                id: self.graph.nodes[node].id.clone(),
1459            },
1460            ScopedEndpoint::ParentBoundary {
1461                scope,
1462                connects_node,
1463            } => {
1464                let anchor = self.scopes[scope]
1465                    .anchor
1466                    .expect("non-root scope boundary must have an anchor");
1467                source_port::ElkInputEdgeSegmentEndpoint::ParentBoundary {
1468                    id: self.graph.nodes[anchor].id.clone(),
1469                    connects_node,
1470                }
1471            }
1472        }
1473    }
1474}
1475
1476#[allow(clippy::too_many_arguments)]
1477fn order_scope_edges_like_elk_importer(
1478    scope: &mut ScopePlan,
1479    scope_index: usize,
1480    parent: &[Option<usize>],
1481    children: &[Vec<usize>],
1482    node_scope: &[usize],
1483    resolved_handling: &[HierarchyHandling],
1484    preorder_position: &[usize],
1485    subtree_size: &[usize],
1486) {
1487    if scope.edges.len() < 2 {
1488        return;
1489    }
1490
1491    let local_parent =
1492        |node: usize| parent[node].filter(|parent| node_scope[*parent] == scope_index);
1493    let is_ancestor = |ancestor: usize, node: usize| {
1494        let start = preorder_position[ancestor];
1495        let end = start + subtree_size[ancestor];
1496        start <= preorder_position[node] && preorder_position[node] < end
1497    };
1498    let containing_parent = |edge: &ScopedEdge| {
1499        let (ScopedEndpoint::Node(source), ScopedEndpoint::Node(target)) =
1500            (edge.source, edge.target)
1501        else {
1502            return None;
1503        };
1504        let source_parent = local_parent(source);
1505        let target_parent = local_parent(target);
1506        if source_parent == target_parent {
1507            source_parent
1508        } else if is_ancestor(source, target) {
1509            Some(source)
1510        } else if is_ancestor(target, source) {
1511            Some(target)
1512        } else {
1513            None
1514        }
1515    };
1516
1517    let mut edges_by_parent: HashMap<Option<usize>, Vec<usize>> = HashMap::new();
1518    for (edge, scoped) in scope.edges.iter().enumerate() {
1519        edges_by_parent
1520            .entry(containing_parent(scoped))
1521            .or_default()
1522            .push(edge);
1523    }
1524
1525    // ElkGraphImporter visits the root graph first, then IncludeChildren graphs in stable BFS
1526    // child order. Preserve that model-order stream before scope-local kernel import.
1527    let mut order = Vec::with_capacity(scope.edges.len());
1528    let mut graph_queue = VecDeque::from([None]);
1529    while let Some(graph_parent) = graph_queue.pop_front() {
1530        if let Some(edges) = edges_by_parent.remove(&graph_parent) {
1531            order.extend(edges);
1532        }
1533        let graph_children: &[usize] = match graph_parent {
1534            Some(parent) => &children[parent],
1535            None => &scope.nodes,
1536        };
1537        graph_queue.extend(
1538            graph_children
1539                .iter()
1540                .copied()
1541                .filter(|child| {
1542                    node_scope[*child] == scope_index
1543                        && local_parent(*child) == graph_parent
1544                        && resolved_handling[*child] == HierarchyHandling::IncludeChildren
1545                })
1546                .map(Some),
1547        );
1548    }
1549
1550    let mut slots = std::mem::take(&mut scope.edges)
1551        .into_iter()
1552        .map(Some)
1553        .collect::<Vec<_>>();
1554    scope.edges.reserve(slots.len());
1555    for edge in order {
1556        scope.edges.push(
1557            slots[edge]
1558                .take()
1559                .expect("ELK scope edge order must visit each edge at most once"),
1560        );
1561    }
1562    scope.edges.extend(slots.into_iter().flatten());
1563}
1564
1565fn detect_parent_cycles(graph: &Graph, parent: &[Option<usize>]) -> Result<()> {
1566    let mut state = vec![0u8; graph.nodes.len()];
1567    for start in 0..graph.nodes.len() {
1568        if state[start] == 2 {
1569            continue;
1570        }
1571        let mut path = Vec::new();
1572        let mut current = Some(start);
1573        while let Some(node) = current {
1574            match state[node] {
1575                2 => break,
1576                1 => {
1577                    return Err(source_port::ImportError::ParentCycle {
1578                        node_id: graph.nodes[node].id.clone(),
1579                    }
1580                    .into());
1581                }
1582                _ => {
1583                    state[node] = 1;
1584                    path.push(node);
1585                    current = parent[node];
1586                }
1587            }
1588        }
1589        for node in path {
1590            state[node] = 2;
1591        }
1592    }
1593    Ok(())
1594}
1595
1596fn scope_edge_segments(
1597    scopes: &[ScopePlan],
1598    source: usize,
1599    target: usize,
1600    source_scope: usize,
1601    target_scope: usize,
1602    work_control: &mut dyn WorkControl,
1603) -> Result<(usize, Vec<ScopeEdgePiece>)> {
1604    let mut pieces = Vec::new();
1605    let mut target_pieces = Vec::new();
1606    let mut current_source_scope = source_scope;
1607    let mut current_target_scope = target_scope;
1608    let mut current_source = ScopedEndpoint::Node(source);
1609    let mut current_target = ScopedEndpoint::Node(target);
1610
1611    while scopes[current_source_scope].depth > scopes[current_target_scope].depth {
1612        ascend_source_scope(
1613            scopes,
1614            target,
1615            &mut current_source_scope,
1616            &mut current_source,
1617            &mut pieces,
1618            work_control,
1619        )?;
1620    }
1621    while scopes[current_target_scope].depth > scopes[current_source_scope].depth {
1622        ascend_target_scope(
1623            scopes,
1624            source,
1625            &mut current_target_scope,
1626            &mut current_target,
1627            &mut target_pieces,
1628            work_control,
1629        )?;
1630    }
1631    while current_source_scope != current_target_scope {
1632        ascend_source_scope(
1633            scopes,
1634            target,
1635            &mut current_source_scope,
1636            &mut current_source,
1637            &mut pieces,
1638            work_control,
1639        )?;
1640        ascend_target_scope(
1641            scopes,
1642            source,
1643            &mut current_target_scope,
1644            &mut current_target,
1645            &mut target_pieces,
1646            work_control,
1647        )?;
1648    }
1649    let owner = current_source_scope;
1650
1651    if !matches!(
1652        (current_source, current_target),
1653        (ScopedEndpoint::Node(left), ScopedEndpoint::Node(right)) if left == right
1654    ) {
1655        work_control.check(1)?;
1656        work_control.charge(1)?;
1657        pieces.push((
1658            owner,
1659            current_source,
1660            current_target,
1661            if source_scope != owner {
1662                source_port::CompoundEdgeSegment::Output {
1663                    depth: scopes[owner].depth,
1664                }
1665            } else {
1666                source_port::CompoundEdgeSegment::Input {
1667                    depth: scopes[owner].depth,
1668                }
1669            },
1670        ));
1671    }
1672    pieces.extend(target_pieces.into_iter().rev());
1673    Ok((owner, pieces))
1674}
1675
1676fn ascend_source_scope(
1677    scopes: &[ScopePlan],
1678    target: usize,
1679    current_scope: &mut usize,
1680    current_source: &mut ScopedEndpoint,
1681    pieces: &mut Vec<ScopeEdgePiece>,
1682    work_control: &mut dyn WorkControl,
1683) -> Result<()> {
1684    let anchor = scopes[*current_scope]
1685        .anchor
1686        .expect("non-root scope must have an anchor");
1687    work_control.check(1)?;
1688    work_control.charge(1)?;
1689    pieces.push((
1690        *current_scope,
1691        *current_source,
1692        ScopedEndpoint::ParentBoundary {
1693            scope: *current_scope,
1694            connects_node: target == anchor,
1695        },
1696        source_port::CompoundEdgeSegment::Output {
1697            depth: scopes[*current_scope].depth,
1698        },
1699    ));
1700    *current_source = ScopedEndpoint::Node(anchor);
1701    *current_scope = scopes[*current_scope]
1702        .parent
1703        .expect("source scope path must reach owner");
1704    Ok(())
1705}
1706
1707fn ascend_target_scope(
1708    scopes: &[ScopePlan],
1709    source: usize,
1710    current_scope: &mut usize,
1711    current_target: &mut ScopedEndpoint,
1712    pieces: &mut Vec<ScopeEdgePiece>,
1713    work_control: &mut dyn WorkControl,
1714) -> Result<()> {
1715    let anchor = scopes[*current_scope]
1716        .anchor
1717        .expect("non-root scope must have an anchor");
1718    work_control.check(1)?;
1719    work_control.charge(1)?;
1720    pieces.push((
1721        *current_scope,
1722        ScopedEndpoint::ParentBoundary {
1723            scope: *current_scope,
1724            connects_node: source == anchor,
1725        },
1726        *current_target,
1727        source_port::CompoundEdgeSegment::Input {
1728            depth: scopes[*current_scope].depth,
1729        },
1730    ));
1731    *current_target = ScopedEndpoint::Node(anchor);
1732    *current_scope = scopes[*current_scope]
1733        .parent
1734        .expect("target scope path must reach owner");
1735    Ok(())
1736}
1737
1738fn compound_center_segment(pieces: &[ScopeEdgePiece]) -> usize {
1739    pieces
1740        .iter()
1741        .position(|(_, _, _, segment)| {
1742            matches!(segment, source_port::CompoundEdgeSegment::Input { .. })
1743        })
1744        .map(|index| index.saturating_sub(1))
1745        .or_else(|| pieces.len().checked_sub(1))
1746        .unwrap_or(0)
1747}
1748
1749fn flatten_scope_layouts(
1750    index: &HierarchyIndex<'_>,
1751    mut arena: Vec<Option<ScopeLayout>>,
1752    work_control: &mut dyn WorkControl,
1753) -> Result<LayoutResult> {
1754    // Charge the planning scan before reading per-scope output geometry. The detailed tranche is
1755    // then charged before translation and compound-segment merging touch those points and labels.
1756    work_control.check(index.scopes.len())?;
1757    work_control.charge(index.scopes.len())?;
1758    let scoped_edge_count = index.scopes.iter().try_fold(0usize, |total, scope| {
1759        total
1760            .checked_add(scope.edges.len())
1761            .ok_or(WorkError::ArithmeticOverflow)
1762    })?;
1763    let flatten_work = index
1764        .scopes
1765        .len()
1766        .checked_mul(3)
1767        .and_then(|scope_work| scope_work.checked_add(index.graph.nodes.len()))
1768        .and_then(|work| work.checked_add(scoped_edge_count))
1769        .and_then(|work| work.checked_add(index.graph.edges.len().checked_mul(3)?))
1770        .ok_or(WorkError::ArithmeticOverflow)?;
1771
1772    work_control.check(scoped_edge_count)?;
1773    work_control.charge(scoped_edge_count)?;
1774    let geometry_items = arena.iter().try_fold(0usize, |total, layout| {
1775        let layout = layout.as_ref().expect("postorder fills every scope result");
1776        layout.layout.edges.iter().try_fold(total, |total, edge| {
1777            total
1778                .checked_add(edge.points.len())
1779                .and_then(|total| total.checked_add(edge.labels.len()))
1780                .and_then(|total| total.checked_add(1))
1781                .ok_or(WorkError::ArithmeticOverflow)
1782        })
1783    })?;
1784    let geometry_work = geometry_items
1785        .checked_mul(2)
1786        .ok_or(WorkError::ArithmeticOverflow)?;
1787    let execution_work = flatten_work
1788        .checked_add(geometry_work)
1789        .ok_or(WorkError::ArithmeticOverflow)?;
1790    work_control.check(execution_work)?;
1791    work_control.charge(execution_work)?;
1792
1793    let mut offsets = vec![Point { x: 0.0, y: 0.0 }; index.scopes.len()];
1794    let mut order = Vec::with_capacity(index.scopes.len());
1795    let mut stack = vec![0usize];
1796    while let Some(scope) = stack.pop() {
1797        order.push(scope);
1798        let scope_result = arena[scope]
1799            .as_ref()
1800            .expect("scope layout exists before flatten");
1801        let layout = &scope_result.layout;
1802        let child_by_id = index.scopes[scope]
1803            .children
1804            .iter()
1805            .map(|child| {
1806                let anchor = index.scopes[*child]
1807                    .anchor
1808                    .expect("child scope must have an anchor");
1809                (index.graph.nodes[anchor].id.as_str(), *child)
1810            })
1811            .collect::<HashMap<_, _>>();
1812        let mut children = Vec::new();
1813        for node in &layout.nodes {
1814            let Some(&child) = child_by_id.get(node.id.as_str()) else {
1815                continue;
1816            };
1817            offsets[child] = Point {
1818                // Mermaid accumulates nested coordinates from group top-left positions, while the
1819                // public Merman node layout is center-based.
1820                x: offsets[scope].x + node.x - node.width / 2.0
1821                    + scope_result
1822                        .content_shifts
1823                        .get(&node.id)
1824                        .map_or(0.0, |shift| shift.x),
1825                y: offsets[scope].y + node.y - node.height / 2.0
1826                    + scope_result
1827                        .content_shifts
1828                        .get(&node.id)
1829                        .map_or(0.0, |shift| shift.y),
1830            };
1831            children.push(child);
1832        }
1833        stack.extend(children.into_iter().rev());
1834    }
1835    let node_capacity = arena.iter().try_fold(0usize, |total, layout| {
1836        total
1837            .checked_add(
1838                layout
1839                    .as_ref()
1840                    .expect("postorder fills every scope result")
1841                    .layout
1842                    .nodes
1843                    .len(),
1844            )
1845            .ok_or(WorkError::ArithmeticOverflow)
1846    })?;
1847    let mut nodes = Vec::with_capacity(node_capacity);
1848    let mut edge_slots = std::iter::repeat_with(|| None)
1849        .take(index.graph.edges.len())
1850        .collect::<Vec<Option<EdgeLayout>>>();
1851    let mut compound_edges = std::iter::repeat_with(|| None)
1852        .take(index.graph.edges.len())
1853        .collect::<Vec<Option<Vec<Option<CompoundEdgeLayoutSegment>>>>>();
1854    for &scope in &order {
1855        let offset = offsets[scope];
1856        let mut scope_layout = arena[scope].take().expect("each scope is flattened once");
1857        for node in &mut scope_layout.layout.nodes {
1858            node.x += offset.x;
1859            node.y += offset.y;
1860        }
1861        nodes.append(&mut scope_layout.layout.nodes);
1862        for mut edge in scope_layout.layout.edges {
1863            translate_edge_layout(&mut edge, offset);
1864            let metadata = scope_layout
1865                .edge_metadata
1866                .get(edge.id.as_str())
1867                .copied()
1868                .expect("scope output edge must retain its source edge metadata");
1869            if let Some(segment) = metadata.segment {
1870                let entry = compound_edges[metadata.original]
1871                    .get_or_insert_with(|| vec![None; segment.count]);
1872                debug_assert_eq!(entry.len(), segment.count);
1873                entry[segment.order] = Some(CompoundEdgeLayoutSegment {
1874                    original_edge_id: edge.id.clone(),
1875                    segment: segment.segment,
1876                    model_order: segment.model_order,
1877                    edge,
1878                });
1879            } else {
1880                debug_assert!(edge_slots[metadata.original].is_none());
1881                edge_slots[metadata.original] = Some(edge);
1882            }
1883        }
1884    }
1885
1886    for (original, segments) in compound_edges.into_iter().enumerate() {
1887        let Some(segments) = segments else {
1888            continue;
1889        };
1890        let segments = segments.into_iter().flatten().collect::<Vec<_>>();
1891        if let Some(edge) = merge_compound_edge_segments(
1892            &segments,
1893            index.graph.options.layered.unnecessary_bendpoints,
1894        ) {
1895            debug_assert!(edge_slots[original].is_none());
1896            edge_slots[original] = Some(edge);
1897        }
1898    }
1899
1900    // ELK derives importer/model order from an edge's containing graph before moving an
1901    // ancestor-descendant edge into that endpoint's inner graph. A direct parent-child edge can
1902    // therefore be owned by the parent scope without materializing a segment there. Emit from
1903    // `owned_edges`, not first-seen segment order; the nested iteration also avoids an O(E) copy.
1904    let mut edges = Vec::with_capacity(index.graph.edges.len());
1905    for &scope in &order {
1906        for &original in &index.scopes[scope].owned_edges {
1907            if let Some(edge) = edge_slots[original].take() {
1908                edges.push(edge);
1909            }
1910        }
1911    }
1912    // Valid adapter inputs should have announced every rendered edge from its owner scope. Keep a
1913    // deterministic tail in release builds if a future source processor suppresses that marker.
1914    edges.extend(edge_slots.into_iter().flatten());
1915    Ok(LayoutResult { nodes, edges })
1916}
1917
1918fn translate_edge_layout(edge: &mut EdgeLayout, offset: Point) {
1919    for point in &mut edge.points {
1920        point.x += offset.x;
1921        point.y += offset.y;
1922    }
1923    for label in &mut edge.labels {
1924        label.x += offset.x;
1925        label.y += offset.y;
1926    }
1927}
1928
1929fn source_graph_requires_compound_pipeline(graph: &LGraph) -> bool {
1930    graph.options.hierarchy_handling == source_port::HierarchyHandling::IncludeChildren
1931        || graph.graph_properties.external_ports
1932        || !graph.hierarchy_edges.is_empty()
1933        || !graph.cross_hierarchy_edges.is_empty()
1934        || graph
1935            .layerless_nodes
1936            .iter()
1937            .any(|node| node.nested_graph.is_some())
1938}
1939
1940fn actual_source_graph_size(graph: &LGraph) -> source_port::LSize {
1941    graph.exported_root_size()
1942}
1943
1944fn source_graph_output_work_units(graph: &LGraph) -> std::result::Result<usize, WorkError> {
1945    let mut total = 0usize;
1946    let mut output_edge_upper_bound = 0usize;
1947    let mut stack = vec![graph];
1948    while let Some(current) = stack.pop() {
1949        // A merged hierarchy edge may expand back into several original rendered edges. Source
1950        // edges plus explicit cross-hierarchy records conservatively bound the final stable sort.
1951        output_edge_upper_bound = output_edge_upper_bound
1952            .checked_add(current.edges.len())
1953            .and_then(|total| total.checked_add(current.cross_hierarchy_edges.len()))
1954            .ok_or(WorkError::ArithmeticOverflow)?;
1955        total = total
1956            .checked_add(current.layerless_nodes.len())
1957            .and_then(|total| total.checked_add(current.edges.len()))
1958            .and_then(|total| total.checked_add(current.cross_hierarchy_edges.len()))
1959            .ok_or(WorkError::ArithmeticOverflow)?;
1960        for edge in &current.edges {
1961            let geometry = edge
1962                .bend_points
1963                .len()
1964                .checked_add(edge.labels.len())
1965                .and_then(|geometry| geometry.checked_add(3))
1966                .ok_or(WorkError::ArithmeticOverflow)?;
1967            total = total
1968                .checked_add(geometry)
1969                .ok_or(WorkError::ArithmeticOverflow)?;
1970            if edge.compound_segment.is_some() {
1971                total = total
1972                    .checked_add(
1973                        geometry
1974                            .checked_mul(2)
1975                            .ok_or(WorkError::ArithmeticOverflow)?,
1976                    )
1977                    .ok_or(WorkError::ArithmeticOverflow)?;
1978            }
1979        }
1980        for segment in &current.cross_hierarchy_edges {
1981            let edge = current
1982                .edges
1983                .get(segment.edge)
1984                .expect("compound segment must reference a graph edge");
1985            let geometry = edge
1986                .bend_points
1987                .len()
1988                .checked_add(edge.labels.len())
1989                .and_then(|geometry| geometry.checked_add(3))
1990                .and_then(|geometry| geometry.checked_mul(2))
1991                .ok_or(WorkError::ArithmeticOverflow)?;
1992            total = total
1993                .checked_add(geometry)
1994                .ok_or(WorkError::ArithmeticOverflow)?;
1995        }
1996        stack.extend(
1997            current
1998                .layerless_nodes
1999                .iter()
2000                .filter_map(|node| node.nested_graph.as_deref()),
2001        );
2002    }
2003    total = total
2004        .checked_add(comparison_sort_work_units(output_edge_upper_bound)?)
2005        .ok_or(WorkError::ArithmeticOverflow)?;
2006    Ok(total.max(1))
2007}
2008
2009fn comparison_sort_work_units(items: usize) -> std::result::Result<usize, WorkError> {
2010    if items < 2 {
2011        return Ok(0);
2012    }
2013    let levels = usize::BITS as usize - (items - 1).leading_zeros() as usize;
2014    items
2015        .checked_mul(levels)
2016        .ok_or(WorkError::ArithmeticOverflow)
2017}
2018
2019fn write_source_graph_dump(output: &mut String, graph: &LGraph, depth: usize) -> std::fmt::Result {
2020    let mut stack = vec![(graph, depth)];
2021    while let Some((current, current_depth)) = stack.pop() {
2022        write_source_graph_dump_frame(output, current, current_depth)?;
2023        stack.extend(
2024            current
2025                .layerless_nodes
2026                .iter()
2027                .rev()
2028                .filter_map(|node| node.nested_graph.as_deref())
2029                .map(|nested| (nested, current_depth + 1)),
2030        );
2031    }
2032    Ok(())
2033}
2034
2035/// Detaches nested graphs before their owners are dropped so deeply nested diagnostics do not
2036/// recurse through `Box<LGraph>` destruction on small worker stacks.
2037fn detach_source_graph_hierarchy_for_drop(graph: &mut LGraph) {
2038    let mut pending = graph
2039        .layerless_nodes
2040        .iter_mut()
2041        .filter_map(|node| node.nested_graph.take())
2042        .collect::<Vec<_>>();
2043    while let Some(mut nested) = pending.pop() {
2044        pending.extend(
2045            nested
2046                .layerless_nodes
2047                .iter_mut()
2048                .filter_map(|node| node.nested_graph.take()),
2049        );
2050    }
2051}
2052
2053fn write_source_graph_dump_frame(
2054    output: &mut String,
2055    graph: &LGraph,
2056    depth: usize,
2057) -> std::fmt::Result {
2058    let indent = "  ".repeat(depth);
2059    writeln!(
2060        output,
2061        "{indent}graph {} parent={:?} size=({}, {}) offset=({}, {}) padding=({}, {}, {}, {})",
2062        graph.id,
2063        graph.parent_node_id,
2064        graph.size.width,
2065        graph.size.height,
2066        graph.offset.x,
2067        graph.offset.y,
2068        graph.padding.left,
2069        graph.padding.right,
2070        graph.padding.top,
2071        graph.padding.bottom
2072    )?;
2073    writeln!(
2074        output,
2075        "{indent}options direction={:?} port_constraints={:?} thoroughness={} hierarchical_sweepiness={} consider_model_order={:?} force_node_model_order={} port_model_order={}",
2076        graph.options.direction,
2077        graph.options.port_constraints,
2078        graph.options.thoroughness,
2079        graph.options.hierarchical_sweepiness,
2080        graph.options.consider_model_order_strategy,
2081        graph.options.force_node_model_order,
2082        graph.options.consider_model_order_port_model_order
2083    )?;
2084    writeln!(output, "{indent}layerless:")?;
2085    for (index, node) in graph.layerless_nodes.iter().enumerate() {
2086        writeln!(
2087            output,
2088            "{indent}- #{index} {} kind={:?} layer={:?} order={:?} pos=({}, {}) size=({}, {}) margin=({}, {}, {}, {}) port_constraints={:?} parent_graph={}",
2089            node.id,
2090            node.kind,
2091            node.layer_index,
2092            node.model_order,
2093            node.position.x,
2094            node.position.y,
2095            node.size.width,
2096            node.size.height,
2097            node.margin.left,
2098            node.margin.right,
2099            node.margin.top,
2100            node.margin.bottom,
2101            node.port_constraints,
2102            node.nested_graph.is_some()
2103        )?;
2104        if node.kind == LNodeKind::ExternalPort {
2105            writeln!(
2106                output,
2107                "{indent}  external side={:?} size=({}, {}) ratio_or_position={} replaced={:?}",
2108                node.external_port_side,
2109                node.external_port_size.width,
2110                node.external_port_size.height,
2111                node.port_ratio_or_position,
2112                node.replaced_external_port_dummy
2113            )?;
2114        }
2115        for (port_index, port) in node.ports.iter().enumerate() {
2116            let incoming = port
2117                .incoming_edges
2118                .iter()
2119                .map(|edge| graph.edges[*edge].id.as_str())
2120                .collect::<Vec<_>>();
2121            let outgoing = port
2122                .outgoing_edges
2123                .iter()
2124                .map(|edge| graph.edges[*edge].id.as_str())
2125                .collect::<Vec<_>>();
2126            writeln!(
2127                output,
2128                "{indent}  port #{port_index} {} type={:?} side={:?} order={:?} index={:?} pos=({}, {}) anchor=({}, {}) size=({}, {}) border={:?} inside={} dummy={:?} origin={:?} in=[{}] out=[{}]",
2129                port.id,
2130                port.port_type,
2131                port.side,
2132                port.model_order,
2133                port.port_index,
2134                port.position.x,
2135                port.position.y,
2136                port.anchor.x,
2137                port.anchor.y,
2138                port.size.width,
2139                port.size.height,
2140                port.border_offset,
2141                port.inside_connections,
2142                port.port_dummy,
2143                node.origin_port,
2144                incoming.join(","),
2145                outgoing.join(",")
2146            )?;
2147        }
2148    }
2149    if !graph.edges.is_empty() {
2150        writeln!(output, "{indent}edges:")?;
2151        for (edge_index, edge) in graph.edges.iter().enumerate() {
2152            let source_attached = graph.edge_source_attached(edge_index);
2153            let target_attached = graph.edge_target_attached(edge_index);
2154            writeln!(
2155                output,
2156                "{indent}- #{edge_index} {} {}:{} -> {}:{} segment={:?} reversed={} attached=({source_attached},{target_attached}) bends={:?}",
2157                edge.id,
2158                edge.source.node,
2159                edge.source.port,
2160                edge.target.node,
2161                edge.target.port,
2162                edge.compound_segment,
2163                edge.reversed,
2164                edge.bend_points
2165            )?;
2166        }
2167    }
2168    writeln!(output, "{indent}layers:")?;
2169    for (index, layer) in graph.layers.iter().enumerate() {
2170        let nodes = layer
2171            .nodes
2172            .iter()
2173            .map(|node| {
2174                let lnode = &graph.layerless_nodes[*node];
2175                format!(
2176                    "{}#{node}[{:?},order={:?},pos=({},{}),size=({},{})]",
2177                    lnode.id,
2178                    lnode.kind,
2179                    lnode.model_order,
2180                    lnode.position.x,
2181                    lnode.position.y,
2182                    lnode.size.width,
2183                    lnode.size.height
2184                )
2185            })
2186            .collect::<Vec<_>>();
2187        writeln!(
2188            output,
2189            "{indent}- layer {index} size=({}, {}) nodes={}",
2190            layer.size.width,
2191            layer.size.height,
2192            nodes.join(" -> ")
2193        )?;
2194    }
2195    writeln!(output)?;
2196
2197    Ok(())
2198}
2199
2200fn layered_options_to_source(graph: &Graph) -> SourceLayeredOptions {
2201    layered_options_to_source_for(
2202        graph,
2203        graph.direction,
2204        graph.options.layered.hierarchy_handling,
2205    )
2206}
2207
2208fn layered_options_to_source_for(
2209    graph: &Graph,
2210    direction: Direction,
2211    hierarchy_handling: HierarchyHandling,
2212) -> SourceLayeredOptions {
2213    let mut options =
2214        SourceLayeredOptions::mermaid_flowchart_defaults(direction_to_source(direction));
2215    options.random_seed = graph.options.layered.random_seed;
2216    options.hierarchy_handling = hierarchy_handling_to_source(hierarchy_handling);
2217    options.edge_routing = edge_routing_to_source(graph.options.layered.edge_routing);
2218    options.cycle_breaking_strategy =
2219        cycle_breaking_to_source(graph.options.layered.cycle_breaking);
2220    options.layering_strategy = match graph.options.layered.layering {
2221        LayeringStrategy::NetworkSimplex => source_port::LayeringStrategy::NetworkSimplex,
2222        LayeringStrategy::LongestPath => source_port::LayeringStrategy::LongestPath,
2223        LayeringStrategy::LongestPathSource => source_port::LayeringStrategy::LongestPathSource,
2224        LayeringStrategy::CoffmanGraham => source_port::LayeringStrategy::CoffmanGraham,
2225        LayeringStrategy::MinWidth => source_port::LayeringStrategy::MinWidth,
2226        LayeringStrategy::StretchWidth => source_port::LayeringStrategy::StretchWidth,
2227        LayeringStrategy::Interactive => source_port::LayeringStrategy::Interactive,
2228    };
2229    options.layering_coffman_graham_layer_bound = graph.options.layered.layering_layer_bound;
2230    options.node_placement_strategy =
2231        node_placement_to_source(graph.options.layered.node_placement);
2232    options.node_placement_bk_fixed_alignment =
2233        node_placement_alignment_to_source(graph.options.layered.node_placement_alignment);
2234    options.consider_model_order_strategy = if graph.options.layered.consider_model_order {
2235        model_order_to_source(graph.options.layered.model_order)
2236    } else {
2237        source_port::OrderingStrategy::None
2238    };
2239    options.force_node_model_order = graph.options.layered.force_node_model_order;
2240    options.merge_edges = graph.options.layered.merge_edges;
2241    options.merge_hierarchy_edges = graph.options.layered.merge_hierarchy_edges;
2242    options.unnecessary_bendpoints = graph.options.layered.unnecessary_bendpoints;
2243    options.inside_self_loops_activate = graph.options.layered.inside_self_loops_activate;
2244    options.self_loop_distribution =
2245        self_loop_distribution_to_source(graph.options.layered.self_loop_distribution);
2246    options.self_loop_ordering =
2247        self_loop_ordering_to_source(graph.options.layered.self_loop_ordering);
2248    set_mermaid_port_clearance(&mut options);
2249    options
2250}
2251
2252fn set_mermaid_port_clearance(options: &mut SourceLayeredOptions) {
2253    options.spacing.ports_surrounding.top = 12.0;
2254    options.spacing.ports_surrounding.right = 12.0;
2255    options.spacing.ports_surrounding.bottom = 12.0;
2256    options.spacing.ports_surrounding.left = 12.0;
2257}
2258
2259fn container_options_to_source(
2260    graph: &Graph,
2261    direction: Direction,
2262    handling: HierarchyHandling,
2263) -> SourceLayeredOptions {
2264    // Mermaid 12 buildSubgraphLayoutOptions. Containers get their own strategy resolution;
2265    // root layering, layer bounds, model-order and edge-routing settings are not inherited.
2266    let mut options = SourceLayeredOptions {
2267        direction: direction_to_source(direction),
2268        hierarchy_handling: hierarchy_handling_to_source(handling),
2269        random_seed: graph.options.layered.random_seed,
2270        merge_edges: graph.options.layered.merge_edges,
2271        cycle_breaking_strategy: cycle_breaking_to_source(graph.options.container.cycle_breaking),
2272        node_placement_strategy: node_placement_to_source(graph.options.container.node_placement),
2273        node_placement_bk_fixed_alignment: node_placement_alignment_to_source(
2274            graph.options.container.node_placement_alignment,
2275        ),
2276        padding: source_port::ElkPadding::uniform(24.0),
2277        spacing: source_port::SpacingOptions::layered_base_value(24.0),
2278        ..Default::default()
2279    };
2280    options.spacing.node_node = 50.0;
2281    options.spacing.edge_node_between_layers = 30.0;
2282    options.spacing.edge_edge = 20.0;
2283    set_mermaid_port_clearance(&mut options);
2284    options
2285}
2286
2287fn resolved_container_options(
2288    graph: &Graph,
2289    node: &Node,
2290    mode: ContainerMode,
2291    direction: Direction,
2292    handling: HierarchyHandling,
2293) -> SourceLayeredOptions {
2294    let mut options = container_options_to_source(graph, direction, handling);
2295    options.padding = mode.padding(node);
2296    options.node_size_minimum = mode.minimum(node);
2297    options.node_size_include_labels = node.label.is_some();
2298    if matches!(mode, ContainerMode::Explicit(_)) {
2299        options.aspect_ratio = 2.0;
2300        options.horizontal_content_alignment = source_port::ContentAlignment::Center;
2301    }
2302    options
2303}
2304
2305fn layout_uses_edge_model_order(graph: &Graph) -> bool {
2306    graph.options.layered.consider_model_order
2307        || graph.options.layered.force_node_model_order
2308        || matches!(
2309            graph.options.layered.cycle_breaking,
2310            CycleBreakingStrategy::ModelOrder | CycleBreakingStrategy::GreedyModelOrder
2311        )
2312}
2313
2314fn direction_to_source(direction: Direction) -> ElkDirection {
2315    match direction {
2316        Direction::Left => ElkDirection::Left,
2317        Direction::Right => ElkDirection::Right,
2318        Direction::Up => ElkDirection::Up,
2319        Direction::Down => ElkDirection::Down,
2320    }
2321}
2322
2323fn hierarchy_handling_to_source(
2324    hierarchy_handling: HierarchyHandling,
2325) -> source_port::HierarchyHandling {
2326    match hierarchy_handling {
2327        HierarchyHandling::IncludeChildren => source_port::HierarchyHandling::IncludeChildren,
2328        HierarchyHandling::SeparateChildren => source_port::HierarchyHandling::SeparateChildren,
2329    }
2330}
2331
2332fn edge_routing_to_source(edge_routing: EdgeRouting) -> source_port::EdgeRouting {
2333    match edge_routing {
2334        EdgeRouting::Orthogonal => source_port::EdgeRouting::Orthogonal,
2335        EdgeRouting::Polyline => source_port::EdgeRouting::Polyline,
2336    }
2337}
2338
2339fn cycle_breaking_to_source(
2340    cycle_breaking: CycleBreakingStrategy,
2341) -> source_port::CycleBreakingStrategy {
2342    match cycle_breaking {
2343        CycleBreakingStrategy::Greedy => source_port::CycleBreakingStrategy::Greedy,
2344        CycleBreakingStrategy::DepthFirst => source_port::CycleBreakingStrategy::DepthFirst,
2345        CycleBreakingStrategy::Interactive => source_port::CycleBreakingStrategy::Interactive,
2346        CycleBreakingStrategy::ModelOrder => source_port::CycleBreakingStrategy::ModelOrder,
2347        CycleBreakingStrategy::GreedyModelOrder => {
2348            source_port::CycleBreakingStrategy::GreedyModelOrder
2349        }
2350    }
2351}
2352
2353fn node_placement_to_source(
2354    node_placement: NodePlacementStrategy,
2355) -> source_port::NodePlacementStrategy {
2356    match node_placement {
2357        NodePlacementStrategy::Simple => source_port::NodePlacementStrategy::Simple,
2358        NodePlacementStrategy::Interactive => source_port::NodePlacementStrategy::Interactive,
2359        NodePlacementStrategy::NetworkSimplex => source_port::NodePlacementStrategy::NetworkSimplex,
2360        NodePlacementStrategy::LinearSegments => source_port::NodePlacementStrategy::LinearSegments,
2361        NodePlacementStrategy::BrandesKoepf => source_port::NodePlacementStrategy::BrandesKoepf,
2362    }
2363}
2364
2365fn node_placement_alignment_to_source(
2366    alignment: NodePlacementAlignment,
2367) -> source_port::FixedAlignment {
2368    match alignment {
2369        NodePlacementAlignment::None => source_port::FixedAlignment::None,
2370        NodePlacementAlignment::LeftUp => source_port::FixedAlignment::LeftUp,
2371        NodePlacementAlignment::RightUp => source_port::FixedAlignment::RightUp,
2372        NodePlacementAlignment::LeftDown => source_port::FixedAlignment::LeftDown,
2373        NodePlacementAlignment::RightDown => source_port::FixedAlignment::RightDown,
2374        NodePlacementAlignment::Balanced => source_port::FixedAlignment::Balanced,
2375    }
2376}
2377
2378fn port_alignment_to_source(alignment: PortAlignment) -> source_port::PortAlignment {
2379    match alignment {
2380        PortAlignment::Distributed => source_port::PortAlignment::Distributed,
2381        PortAlignment::Justified => source_port::PortAlignment::Justified,
2382        PortAlignment::Begin => source_port::PortAlignment::Begin,
2383        PortAlignment::Center => source_port::PortAlignment::Center,
2384        PortAlignment::End => source_port::PortAlignment::End,
2385    }
2386}
2387
2388fn layer_constraint_to_source(layer_constraint: LayerConstraint) -> source_port::LayerConstraint {
2389    match layer_constraint {
2390        LayerConstraint::First => source_port::LayerConstraint::First,
2391        LayerConstraint::FirstSeparate => source_port::LayerConstraint::FirstSeparate,
2392        LayerConstraint::Last => source_port::LayerConstraint::Last,
2393        LayerConstraint::LastSeparate => source_port::LayerConstraint::LastSeparate,
2394    }
2395}
2396
2397fn model_order_to_source(model_order: ModelOrderStrategy) -> source_port::OrderingStrategy {
2398    match model_order {
2399        ModelOrderStrategy::None => source_port::OrderingStrategy::None,
2400        ModelOrderStrategy::NodesAndEdges => source_port::OrderingStrategy::NodesAndEdges,
2401        ModelOrderStrategy::PreferEdges => source_port::OrderingStrategy::PreferEdges,
2402        ModelOrderStrategy::PreferNodes => source_port::OrderingStrategy::PreferNodes,
2403    }
2404}
2405
2406fn self_loop_distribution_to_source(
2407    self_loop_distribution: SelfLoopDistributionStrategy,
2408) -> source_port::SelfLoopDistributionStrategy {
2409    match self_loop_distribution {
2410        SelfLoopDistributionStrategy::North => source_port::SelfLoopDistributionStrategy::North,
2411        SelfLoopDistributionStrategy::Equally => source_port::SelfLoopDistributionStrategy::Equally,
2412        SelfLoopDistributionStrategy::NorthSouth => {
2413            source_port::SelfLoopDistributionStrategy::NorthSouth
2414        }
2415    }
2416}
2417
2418fn self_loop_ordering_to_source(
2419    self_loop_ordering: SelfLoopOrderingStrategy,
2420) -> source_port::SelfLoopOrderingStrategy {
2421    match self_loop_ordering {
2422        SelfLoopOrderingStrategy::Stacked => source_port::SelfLoopOrderingStrategy::Stacked,
2423        SelfLoopOrderingStrategy::ReverseStacked => {
2424            source_port::SelfLoopOrderingStrategy::ReverseStacked
2425        }
2426        SelfLoopOrderingStrategy::Sequenced => source_port::SelfLoopOrderingStrategy::Sequenced,
2427    }
2428}
2429
2430fn source_graph_to_layout_result(graph: &LGraph) -> LayoutResult {
2431    source_graph_to_layout_result_with_ordering(graph, true)
2432}
2433
2434fn source_graph_to_layout_result_with_ordering(graph: &LGraph, order_edges: bool) -> LayoutResult {
2435    let mut result = SourceLayoutAccumulator {
2436        add_unnecessary_bendpoints: graph.options.unnecessary_bendpoints,
2437        ..Default::default()
2438    };
2439    append_source_graph_layout(graph, LPoint::default(), &mut result);
2440    result.into_layout_result(order_edges)
2441}
2442
2443#[derive(Debug, Default)]
2444struct SourceLayoutAccumulator {
2445    nodes: Vec<NodeLayout>,
2446    node_ids: HashSet<String>,
2447    edges: Vec<OrderedEdgeLayout>,
2448    compound_edges: HashMap<String, Vec<CompoundEdgeLayoutSegment>>,
2449    add_unnecessary_bendpoints: bool,
2450}
2451
2452impl SourceLayoutAccumulator {
2453    fn into_layout_result(mut self, order_edges: bool) -> LayoutResult {
2454        for segments in self.compound_edges.values_mut() {
2455            order_compound_layout_segments(segments);
2456            if let Some(edge) =
2457                merge_compound_edge_segments(segments, self.add_unnecessary_bendpoints)
2458            {
2459                self.edges.push(OrderedEdgeLayout {
2460                    model_order: segments
2461                        .iter()
2462                        .filter_map(|segment| segment.model_order)
2463                        .min(),
2464                    edge,
2465                });
2466            }
2467        }
2468        if order_edges {
2469            self.edges.sort_by(|left, right| {
2470                left.model_order
2471                    .unwrap_or(usize::MAX)
2472                    .cmp(&right.model_order.unwrap_or(usize::MAX))
2473                    .then_with(|| left.edge.id.cmp(&right.edge.id))
2474            });
2475        }
2476
2477        LayoutResult {
2478            nodes: self.nodes,
2479            edges: self.edges.into_iter().map(|ordered| ordered.edge).collect(),
2480        }
2481    }
2482}
2483
2484fn order_compound_layout_segments(segments: &mut Vec<CompoundEdgeLayoutSegment>) {
2485    if segments.len() < 2 {
2486        return;
2487    }
2488
2489    // ELK's compound postprocessor orders Output segments by descending hierarchy depth, then
2490    // Input segments by ascending depth before concatenation. Imported paths make each side's
2491    // depths unique and contiguous, so direct placement preserves that order without O(n log n)
2492    // comparison sorting.
2493    let mut output_min = usize::MAX;
2494    let mut output_max = 0usize;
2495    let mut output_count = 0usize;
2496    let mut input_min = usize::MAX;
2497    let mut input_max = 0usize;
2498    let mut input_count = 0usize;
2499    for segment in segments.iter() {
2500        match segment.segment {
2501            source_port::CompoundEdgeSegment::Output { depth } => {
2502                output_min = output_min.min(depth);
2503                output_max = output_max.max(depth);
2504                output_count += 1;
2505            }
2506            source_port::CompoundEdgeSegment::Input { depth } => {
2507                input_min = input_min.min(depth);
2508                input_max = input_max.max(depth);
2509                input_count += 1;
2510            }
2511        }
2512    }
2513
2514    let output_span = if output_count == 0 {
2515        0
2516    } else {
2517        output_max - output_min + 1
2518    };
2519    let input_span = if input_count == 0 {
2520        0
2521    } else {
2522        input_max - input_min + 1
2523    };
2524    assert_eq!(
2525        output_span, output_count,
2526        "compound output segments must have unique contiguous depths"
2527    );
2528    assert_eq!(
2529        input_span, input_count,
2530        "compound input segments must have unique contiguous depths"
2531    );
2532
2533    let mut ordered = std::iter::repeat_with(|| None)
2534        .take(segments.len())
2535        .collect::<Vec<Option<CompoundEdgeLayoutSegment>>>();
2536    for segment in std::mem::take(segments) {
2537        let position = match segment.segment {
2538            source_port::CompoundEdgeSegment::Output { depth } => output_max - depth,
2539            source_port::CompoundEdgeSegment::Input { depth } => output_count + depth - input_min,
2540        };
2541        assert!(
2542            ordered[position].replace(segment).is_none(),
2543            "compound segment path position must be unique"
2544        );
2545    }
2546    segments.extend(
2547        ordered
2548            .into_iter()
2549            .map(|segment| segment.expect("compound segment path must be contiguous")),
2550    );
2551}
2552
2553#[derive(Debug, Clone)]
2554struct OrderedEdgeLayout {
2555    model_order: Option<usize>,
2556    edge: EdgeLayout,
2557}
2558
2559fn append_source_graph_layout(
2560    graph: &LGraph,
2561    parent_origin: LPoint,
2562    result: &mut SourceLayoutAccumulator,
2563) {
2564    enum Frame<'a> {
2565        Enter {
2566            graph: &'a LGraph,
2567            parent_origin: LPoint,
2568        },
2569        Exit {
2570            graph: &'a LGraph,
2571            graph_origin: LPoint,
2572        },
2573    }
2574
2575    let mut frames = vec![Frame::Enter {
2576        graph,
2577        parent_origin,
2578    }];
2579    while let Some(frame) = frames.pop() {
2580        let (graph, parent_origin) = match frame {
2581            Frame::Enter {
2582                graph,
2583                parent_origin,
2584            } => (graph, parent_origin),
2585            Frame::Exit {
2586                graph,
2587                graph_origin,
2588            } => {
2589                append_source_graph_edges(graph, graph_origin, result);
2590                continue;
2591            }
2592        };
2593        let graph_origin = LPoint {
2594            x: parent_origin.x + graph.offset.x + graph.padding.left,
2595            y: parent_origin.y + graph.offset.y + graph.padding.top,
2596        };
2597        for node in graph
2598            .layerless_nodes
2599            .iter()
2600            .filter(|node| node.kind == LNodeKind::Normal)
2601        {
2602            result.node_ids.insert(node.id.clone());
2603            result.nodes.push(NodeLayout {
2604                id: node.id.clone(),
2605                x: graph_origin.x + node.position.x + node.size.width / 2.0,
2606                y: graph_origin.y + node.position.y + node.size.height / 2.0,
2607                width: node.size.width,
2608                height: node.size.height,
2609            });
2610        }
2611        frames.push(Frame::Exit {
2612            graph,
2613            graph_origin,
2614        });
2615        frames.extend(graph.layerless_nodes.iter().rev().filter_map(|node| {
2616            node.nested_graph
2617                .as_deref()
2618                .map(|nested_graph| Frame::Enter {
2619                    graph: nested_graph,
2620                    parent_origin: LPoint {
2621                        x: graph_origin.x + node.position.x,
2622                        y: graph_origin.y + node.position.y,
2623                    },
2624                })
2625        }));
2626    }
2627}
2628
2629fn append_source_graph_edges(
2630    graph: &LGraph,
2631    graph_origin: LPoint,
2632    result: &mut SourceLayoutAccumulator,
2633) {
2634    let mut compound_segments_by_edge: HashMap<usize, Vec<CompoundLayoutSegment>> = HashMap::new();
2635    for segment in &graph.cross_hierarchy_edges {
2636        compound_segments_by_edge
2637            .entry(segment.edge)
2638            .or_default()
2639            .push(CompoundLayoutSegment {
2640                original_edge_id: segment.original_edge_id.clone(),
2641                model_order: segment.original_model_order,
2642                segment: segment.segment,
2643            });
2644    }
2645
2646    for (edge_index, edge) in graph.edges.iter().enumerate() {
2647        let compound_segments = compound_segments_by_edge
2648            .remove(&edge_index)
2649            .or_else(|| {
2650                edge.compound_segment.map(|segment| {
2651                    vec![CompoundLayoutSegment {
2652                        original_edge_id: edge.id.clone(),
2653                        model_order: edge.model_order,
2654                        segment,
2655                    }]
2656                })
2657            })
2658            .unwrap_or_default();
2659        if compound_segments.is_empty() {
2660            if !edge_has_layout_endpoints(graph, result, edge_index, edge) {
2661                continue;
2662            }
2663        } else if !graph.edge_source_attached(edge_index) || !graph.edge_target_attached(edge_index)
2664        {
2665            continue;
2666        }
2667
2668        let edge_layout = EdgeLayout {
2669            id: edge.id.clone(),
2670            points: edge_points(graph, edge)
2671                .into_iter()
2672                .map(|point| Point {
2673                    x: graph_origin.x + point.x,
2674                    y: graph_origin.y + point.y,
2675                })
2676                .collect(),
2677            labels: edge_labels(graph_origin, edge),
2678        };
2679
2680        if !compound_segments.is_empty() {
2681            for segment in compound_segments {
2682                let original_edge_id = segment.original_edge_id.clone();
2683                let edge_layout = edge_layout_for_original_edge(
2684                    &edge_layout,
2685                    graph_origin,
2686                    edge,
2687                    original_edge_id.as_str(),
2688                );
2689                result
2690                    .compound_edges
2691                    .entry(original_edge_id)
2692                    .or_default()
2693                    .push(CompoundEdgeLayoutSegment {
2694                        original_edge_id: segment.original_edge_id,
2695                        segment: segment.segment,
2696                        model_order: segment.model_order.or(edge.model_order),
2697                        edge: edge_layout,
2698                    });
2699            }
2700        } else {
2701            result.edges.push(OrderedEdgeLayout {
2702                model_order: edge.model_order,
2703                edge: edge_layout,
2704            });
2705        }
2706    }
2707}
2708
2709fn edge_layout_for_original_edge(
2710    edge: &EdgeLayout,
2711    graph_origin: LPoint,
2712    source_edge: &source_port::LayeredEdge,
2713    original_edge_id: &str,
2714) -> EdgeLayout {
2715    let mut edge = edge.clone();
2716    edge.id = original_edge_id.to_string();
2717    edge.labels = edge_labels_for_original_edge(graph_origin, source_edge, original_edge_id);
2718    edge
2719}
2720
2721fn edge_labels_for_original_edge(
2722    graph_origin: LPoint,
2723    edge: &source_port::LayeredEdge,
2724    original_edge_id: &str,
2725) -> Vec<EdgeLabelLayout> {
2726    edge.labels
2727        .iter()
2728        .filter(|label| {
2729            label
2730                .original_label_edge
2731                .as_deref()
2732                .unwrap_or(original_edge_id)
2733                == original_edge_id
2734        })
2735        .map(|label| EdgeLabelLayout {
2736            terminal: label
2737                .source_index
2738                .and_then(TerminalLabelKey::from_source_index),
2739            x: graph_origin.x + label.position.x,
2740            y: graph_origin.y + label.position.y,
2741            width: label.size.width,
2742            height: label.size.height,
2743        })
2744        .collect()
2745}
2746
2747#[derive(Debug, Clone)]
2748struct CompoundLayoutSegment {
2749    original_edge_id: String,
2750    model_order: Option<usize>,
2751    segment: source_port::CompoundEdgeSegment,
2752}
2753
2754#[derive(Debug, Clone)]
2755struct CompoundEdgeLayoutSegment {
2756    original_edge_id: String,
2757    segment: source_port::CompoundEdgeSegment,
2758    model_order: Option<usize>,
2759    edge: EdgeLayout,
2760}
2761
2762/// Merge hierarchy-local edge segments following ELK's compound postprocessor.
2763///
2764/// Source:
2765/// https://github.com/eclipse-elk/elk/blob/62d5909f96fad541bc101ad52dabaece6b7eab7e/plugins/org.eclipse.elk.alg.layered/src/org/eclipse/elk/alg/layered/compound/CompoundGraphPostprocessor.java
2766fn merge_compound_edge_segments(
2767    segments: &[CompoundEdgeLayoutSegment],
2768    add_unnecessary_bendpoints: bool,
2769) -> Option<EdgeLayout> {
2770    let first = segments.first()?;
2771    let mut points = Vec::new();
2772    let mut labels = Vec::new();
2773    let mut last_point = None;
2774
2775    if let Some(source) = first.edge.points.first().copied() {
2776        push_distinct_point(&mut points, source);
2777    }
2778
2779    for segment in segments {
2780        let segment_points = &segment.edge.points;
2781        if segment_points.is_empty() {
2782            continue;
2783        }
2784
2785        let bend_points = if segment_points.len() > 2 {
2786            &segment_points[1..segment_points.len() - 1]
2787        } else {
2788            &[][..]
2789        };
2790
2791        if let (Some(previous), Some(next)) = (
2792            last_point,
2793            bend_points.first().or_else(|| segment_points.last()),
2794        ) && compound_boundary_needs_bendpoint(previous, *next, add_unnecessary_bendpoints)
2795            && let Some(source) = segment_points.first()
2796        {
2797            push_distinct_point(&mut points, *source);
2798        }
2799
2800        for point in bend_points {
2801            push_distinct_point(&mut points, *point);
2802        }
2803        labels.extend(segment.edge.labels.iter().cloned());
2804        last_point = bend_points
2805            .last()
2806            .copied()
2807            .or_else(|| segment_points.first().copied());
2808    }
2809
2810    if let Some(target) = segments
2811        .last()
2812        .and_then(|segment| segment.edge.points.last())
2813        .copied()
2814    {
2815        push_distinct_point(&mut points, target);
2816    }
2817
2818    Some(EdgeLayout {
2819        id: first.original_edge_id.clone(),
2820        points,
2821        labels,
2822    })
2823}
2824
2825fn compound_boundary_needs_bendpoint(
2826    previous: Point,
2827    next: Point,
2828    add_unnecessary_bendpoints: bool,
2829) -> bool {
2830    const ORTHOGONAL_TOLERANCE: f64 = 0.001;
2831    let x_diff_enough = (previous.x - next.x).abs() > ORTHOGONAL_TOLERANCE;
2832    let y_diff_enough = (previous.y - next.y).abs() > ORTHOGONAL_TOLERANCE;
2833    if add_unnecessary_bendpoints {
2834        x_diff_enough || y_diff_enough
2835    } else {
2836        x_diff_enough && y_diff_enough
2837    }
2838}
2839
2840fn push_distinct_point(points: &mut Vec<Point>, point: Point) {
2841    if points.last().is_some_and(|last| *last == point) {
2842        return;
2843    }
2844    points.push(point);
2845}
2846
2847fn edge_has_layout_endpoints(
2848    graph: &LGraph,
2849    result: &SourceLayoutAccumulator,
2850    edge_index: usize,
2851    edge: &source_port::LayeredEdge,
2852) -> bool {
2853    if !graph.edge_source_attached(edge_index) || !graph.edge_target_attached(edge_index) {
2854        return false;
2855    }
2856
2857    endpoint_has_layout(graph, result, edge.source, edge.source_node_id.as_str())
2858        && endpoint_has_layout(graph, result, edge.target, edge.target_node_id.as_str())
2859}
2860
2861fn endpoint_has_layout(
2862    graph: &LGraph,
2863    result: &SourceLayoutAccumulator,
2864    endpoint: PortRef,
2865    original_node_id: &str,
2866) -> bool {
2867    graph
2868        .layerless_nodes
2869        .get(endpoint.node)
2870        .is_some_and(|node| node.kind == LNodeKind::Normal)
2871        || result.node_ids.contains(original_node_id)
2872}
2873
2874fn edge_points(graph: &LGraph, edge: &source_port::LayeredEdge) -> Vec<source_port::LPoint> {
2875    let mut points = Vec::with_capacity(edge.bend_points.len() + 2);
2876    points.push(port_anchor(graph, edge.source));
2877    points.extend(edge.bend_points.iter().copied());
2878    points.push(port_anchor(graph, edge.target));
2879    points
2880}
2881
2882fn edge_labels(graph_origin: LPoint, edge: &source_port::LayeredEdge) -> Vec<EdgeLabelLayout> {
2883    edge.labels
2884        .iter()
2885        .map(|label| EdgeLabelLayout {
2886            terminal: label
2887                .source_index
2888                .and_then(TerminalLabelKey::from_source_index),
2889            x: graph_origin.x + label.position.x,
2890            y: graph_origin.y + label.position.y,
2891            width: label.size.width,
2892            height: label.size.height,
2893        })
2894        .collect()
2895}
2896
2897fn port_anchor(graph: &LGraph, port_ref: PortRef) -> source_port::LPoint {
2898    let node = &graph.layerless_nodes[port_ref.node];
2899    let port = &node.ports[port_ref.port];
2900    source_port::LPoint {
2901        x: node.position.x + port.position.x + port.anchor.x,
2902        y: node.position.y + port.position.y + port.anchor.y,
2903    }
2904}
2905
2906#[cfg(test)]
2907mod tests {
2908    use super::*;
2909
2910    fn leaf(id: &str) -> Node {
2911        Node {
2912            id: id.to_string(),
2913            kind: NodeKind::Leaf,
2914            container: Default::default(),
2915            label_text: None,
2916            width: 80.0,
2917            height: 40.0,
2918            parent: None,
2919            direction: None,
2920            hierarchy_handling: None,
2921            layer_constraint: None,
2922            port_alignment: None,
2923            label: None,
2924        }
2925    }
2926
2927    fn edge(id: &str, source: &str, target: &str) -> Edge {
2928        Edge {
2929            id: id.to_string(),
2930            source: source.to_string(),
2931            target: target.to_string(),
2932            label: None,
2933            terminal_labels: Vec::new(),
2934            minlen: 1,
2935            inside_self_loops_yo: false,
2936        }
2937    }
2938
2939    fn flat_graph(nodes: Vec<Node>, edges: Vec<Edge>) -> Graph {
2940        Graph {
2941            id: "root".to_string(),
2942            direction: Direction::Down,
2943            nodes,
2944            edges,
2945            ..Default::default()
2946        }
2947    }
2948
2949    #[test]
2950    fn node_port_alignment_matches_elkjs_in_flat_and_separate_scopes() {
2951        // elkjs 0.9.3, three implicit ports on a 40px side with Mermaid's 12px
2952        // surrounding margins and spacing.baseValue=40. CENTER expands 5px gaps to 10px.
2953        for nested in [false, true] {
2954            let expected = if nested {
2955                // buildSubgraphLayoutOptions uses spacing.baseValue=24.
2956                [[15.4, 20.0, 24.6], [10.8, 20.0, 29.2]]
2957            } else {
2958                [[15.0, 20.0, 25.0], [10.0, 20.0, 30.0]]
2959            };
2960            for (alignment, expected) in [None, Some(PortAlignment::Center)]
2961                .into_iter()
2962                .zip(expected)
2963            {
2964                let mut nodes = vec![leaf("A"), leaf("B"), leaf("C"), leaf("T")];
2965                nodes[3].port_alignment = alignment;
2966                if nested {
2967                    for node in &mut nodes {
2968                        node.parent = Some("frame".into());
2969                    }
2970                    nodes.push(group("frame", None, HierarchyHandling::SeparateChildren));
2971                }
2972                let mut graph = flat_graph(
2973                    nodes,
2974                    vec![
2975                        edge("AT", "A", "T"),
2976                        edge("BT", "B", "T"),
2977                        edge("CT", "C", "T"),
2978                    ],
2979                );
2980                graph.direction = Direction::Right;
2981                let result = layout(&graph).unwrap();
2982                let target = result.nodes.iter().find(|node| node.id == "T").unwrap();
2983                let mut offsets: Vec<_> = result
2984                    .edges
2985                    .iter()
2986                    .map(|edge| edge.points.last().unwrap().y - (target.y - target.height / 2.0))
2987                    .collect();
2988                offsets.sort_by(f64::total_cmp);
2989                assert_eq!(offsets.len(), expected.len());
2990                for (actual, expected) in offsets.iter().zip(expected) {
2991                    assert!(
2992                        (actual - expected).abs() < 1e-9,
2993                        "nested={nested}, alignment={alignment:?}, offsets={offsets:?}"
2994                    );
2995                }
2996            }
2997        }
2998    }
2999
3000    #[test]
3001    fn container_flexibility_belongs_to_the_container_node() {
3002        let mut container = leaf("frame");
3003        container.kind = NodeKind::Group;
3004        let mut child = leaf("child");
3005        child.parent = Some("frame".into());
3006        let mut graph = flat_graph(vec![container, child], vec![]);
3007        graph.options.layered.node_placement = NodePlacementStrategy::NetworkSimplex;
3008        let source = graph_to_source_input(&graph).unwrap();
3009        let imported = source_port::import_graph(&source).unwrap();
3010        let container = &imported.layerless_nodes[0];
3011        assert_eq!(
3012            container.node_flexibility,
3013            source_port::NodeFlexibility::PortPosition
3014        );
3015        let nested = container.nested_graph.as_ref().unwrap();
3016        assert_eq!(
3017            nested.options.node_placement_strategy,
3018            source_port::NodePlacementStrategy::BrandesKoepf
3019        );
3020        assert_eq!(
3021            nested.layerless_nodes[0].node_flexibility,
3022            source_port::NodeFlexibility::None
3023        );
3024    }
3025
3026    #[test]
3027    fn coffman_graham_bound_changes_the_published_layout() {
3028        let mut graph = flat_graph(
3029            vec![leaf("A"), leaf("B"), leaf("C"), leaf("D")],
3030            vec![
3031                edge("ab", "A", "B"),
3032                edge("ac", "A", "C"),
3033                edge("bd", "B", "D"),
3034                edge("cd", "C", "D"),
3035            ],
3036        );
3037        graph.options.layered.layering = LayeringStrategy::CoffmanGraham;
3038        graph.options.layered.layering_layer_bound = 1;
3039        let narrow = layout(&graph).unwrap();
3040        graph.options.layered.layering_layer_bound = 2;
3041        let wide = layout(&graph).unwrap();
3042        let y = |result: &LayoutResult, id: &str| {
3043            result.nodes.iter().find(|node| node.id == id).unwrap().y
3044        };
3045        assert_ne!(y(&narrow, "B"), y(&narrow, "C"));
3046        assert_eq!(y(&wide, "B"), y(&wide, "C"));
3047        assert!(y(&narrow, "D") - y(&narrow, "A") > y(&wide, "D") - y(&wide, "A"));
3048    }
3049
3050    #[test]
3051    fn parent_cycle_reports_the_revisited_cycle_member_after_a_stem() {
3052        let graph = flat_graph(vec![leaf("stem"), leaf("A"), leaf("B")], vec![]);
3053        let parent = [Some(1), Some(2), Some(1)];
3054
3055        assert!(matches!(
3056            detect_parent_cycles(&graph, &parent),
3057            Err(Error::SourceImport(source_port::ImportError::ParentCycle { node_id }))
3058                if node_id == "A"
3059        ));
3060    }
3061
3062    fn group(id: &str, parent: Option<&str>, handling: HierarchyHandling) -> Node {
3063        Node {
3064            id: id.to_string(),
3065            kind: NodeKind::Group,
3066            container: Default::default(),
3067            label_text: None,
3068            width: 0.0,
3069            height: 0.0,
3070            parent: parent.map(str::to_string),
3071            direction: None,
3072            hierarchy_handling: Some(handling),
3073            layer_constraint: None,
3074            port_alignment: None,
3075            label: Some(Label {
3076                width: 24.0,
3077                height: 18.0,
3078            }),
3079        }
3080    }
3081
3082    fn deep_separate_graph(depth: usize) -> Graph {
3083        let mut nodes = Vec::with_capacity(depth + 1);
3084        for index in 0..depth {
3085            nodes.push(group(
3086                format!("group-{index}").as_str(),
3087                index
3088                    .checked_sub(1)
3089                    .map(|parent| format!("group-{parent}"))
3090                    .as_deref(),
3091                HierarchyHandling::SeparateChildren,
3092            ));
3093        }
3094        let mut terminal = leaf("terminal");
3095        terminal.parent = depth.checked_sub(1).map(|parent| format!("group-{parent}"));
3096        nodes.push(terminal);
3097
3098        flat_graph(nodes, Vec::new())
3099    }
3100
3101    fn deep_include_graph(depth: usize) -> Graph {
3102        let mut graph = deep_separate_graph(depth);
3103        graph.options.layered.hierarchy_handling = HierarchyHandling::IncludeChildren;
3104        for node in &mut graph.nodes {
3105            if node.kind == NodeKind::Group {
3106                node.hierarchy_handling = Some(HierarchyHandling::IncludeChildren);
3107            }
3108        }
3109        graph
3110    }
3111
3112    fn repeated_cross_scope_graph(edge_count: usize) -> Graph {
3113        let mut child = leaf("child");
3114        child.parent = Some("group".to_string());
3115        let edges = (0..edge_count)
3116            .map(|index| {
3117                let mut edge = edge(format!("cross-{index}").as_str(), "child", "outer");
3118                edge.label = Some(Label {
3119                    width: 20.0,
3120                    height: 10.0,
3121                });
3122                edge
3123            })
3124            .collect();
3125        flat_graph(
3126            vec![
3127                group("group", None, HierarchyHandling::SeparateChildren),
3128                child,
3129                leaf("outer"),
3130            ],
3131            edges,
3132        )
3133    }
3134
3135    fn deep_cross_scope_graph(depth: usize, edge_count: usize) -> Graph {
3136        let mut graph = deep_separate_graph(depth);
3137        graph.options.layered.hierarchy_handling = HierarchyHandling::SeparateChildren;
3138        graph.nodes.push(leaf("outer"));
3139        graph.edges = (0..edge_count)
3140            .map(|index| edge(format!("deep-cross-{index}").as_str(), "terminal", "outer"))
3141            .collect();
3142        graph
3143    }
3144
3145    fn synthetic_scope_arena(
3146        index: &HierarchyIndex<'_>,
3147        points_per_segment: usize,
3148    ) -> Vec<Option<ScopeLayout>> {
3149        index
3150            .scopes
3151            .iter()
3152            .map(|scope| {
3153                let nodes = scope
3154                    .nodes
3155                    .iter()
3156                    .map(|node| {
3157                        let node = &index.graph.nodes[*node];
3158                        NodeLayout {
3159                            id: node.id.clone(),
3160                            x: 50.0,
3161                            y: 50.0,
3162                            width: node.width.max(1.0),
3163                            height: node.height.max(1.0),
3164                        }
3165                    })
3166                    .collect();
3167                let mut edge_metadata = HashMap::with_capacity(scope.edges.len());
3168                let edges = scope
3169                    .edges
3170                    .iter()
3171                    .map(|scoped| {
3172                        let source = &index.graph.edges[scoped.original];
3173                        let segment = scoped.segment.map(|segment| SegmentedEdgeMetadata {
3174                            segment,
3175                            model_order: Some(index.edge_model_order[scoped.original]),
3176                            order: scoped
3177                                .segment_order
3178                                .expect("synthetic segmented edge keeps path order"),
3179                            count: scoped.segment_count,
3180                        });
3181                        edge_metadata.insert(
3182                            source.id.clone(),
3183                            ScopeEdgeMetadata {
3184                                original: scoped.original,
3185                                segment,
3186                            },
3187                        );
3188                        EdgeLayout {
3189                            id: source.id.clone(),
3190                            points: (0..points_per_segment)
3191                                .map(|point| Point {
3192                                    x: point as f64,
3193                                    y: point as f64,
3194                                })
3195                                .collect(),
3196                            labels: scoped
3197                                .carries_label
3198                                .then_some(EdgeLabelLayout {
3199                                    terminal: None,
3200                                    x: 1.0,
3201                                    y: 1.0,
3202                                    width: 20.0,
3203                                    height: 10.0,
3204                                })
3205                                .into_iter()
3206                                .collect(),
3207                        }
3208                    })
3209                    .collect();
3210                Some(ScopeLayout {
3211                    size_constraints_active: false,
3212                    label_margin: source_port::LMargin::default(),
3213                    content_shifts: HashMap::new(),
3214                    layout: LayoutResult { nodes, edges },
3215                    size: source_port::LSize {
3216                        width: 100.0,
3217                        height: 100.0,
3218                    },
3219                    edge_metadata,
3220                })
3221            })
3222            .collect()
3223    }
3224
3225    #[derive(Debug)]
3226    struct RecordingWorkControl {
3227        remaining: usize,
3228        checked: usize,
3229        charged: usize,
3230    }
3231
3232    impl RecordingWorkControl {
3233        fn unlimited() -> Self {
3234            Self {
3235                remaining: usize::MAX,
3236                checked: 0,
3237                charged: 0,
3238            }
3239        }
3240    }
3241
3242    impl WorkControl for RecordingWorkControl {
3243        fn check(&mut self, units: usize) -> std::result::Result<(), WorkError> {
3244            self.checked = self
3245                .checked
3246                .checked_add(units)
3247                .ok_or(WorkError::ArithmeticOverflow)?;
3248            if units > self.remaining {
3249                return Err(WorkError::Interrupted);
3250            }
3251            Ok(())
3252        }
3253
3254        fn charge(&mut self, units: usize) -> std::result::Result<(), WorkError> {
3255            if units > self.remaining {
3256                return Err(WorkError::Interrupted);
3257            }
3258            self.remaining -= units;
3259            self.charged = self
3260                .charged
3261                .checked_add(units)
3262                .ok_or(WorkError::ArithmeticOverflow)?;
3263            Ok(())
3264        }
3265    }
3266
3267    #[test]
3268    fn flat_scope_omits_unused_terminal_payload_at_a_fixed_budget() {
3269        for count in [0, 1, 8192] {
3270            let mut source_edge = edge("ab", "A", "B");
3271            source_edge.terminal_labels = vec![
3272                TerminalLabel {
3273                    key: TerminalLabelKey::StartLeft,
3274                    label: Label {
3275                        width: 20.0,
3276                        height: 12.0
3277                    },
3278                };
3279                count
3280            ];
3281            let mut graph = flat_graph(vec![leaf("A"), leaf("B")], vec![source_edge]);
3282            graph.options.algorithm = Algorithm::MrTree;
3283            let index =
3284                HierarchyIndex::build(&graph, &mut RecordingWorkControl::unlimited()).unwrap();
3285            let mut work = RecordingWorkControl {
3286                remaining: 3,
3287                checked: 0,
3288                charged: 0,
3289            };
3290            let (flat, _) = index.materialize_flat_scope(0, &[], &mut work).unwrap();
3291            assert_eq!(work.charged, 3);
3292            assert!(flat.edges[0].terminal_labels.is_empty());
3293            assert_eq!(flat.edges[0].terminal_labels.capacity(), 0);
3294            assert_eq!(graph.edges[0].terminal_labels.len(), count);
3295        }
3296    }
3297
3298    #[test]
3299    fn separate_children_hierarchy_index_has_unique_linear_ownership() {
3300        for depth in [8, 16, 32, 64, 128, 256] {
3301            let graph = deep_separate_graph(depth);
3302            let mut work_control = RecordingWorkControl::unlimited();
3303            let index = HierarchyIndex::build(&graph, &mut work_control).unwrap();
3304
3305            assert_eq!(index.scopes.len(), depth + 1);
3306            assert_eq!(index.postorder.len(), index.scopes.len());
3307            assert_eq!(index.postorder.last(), Some(&0));
3308            assert_eq!(
3309                index
3310                    .scopes
3311                    .iter()
3312                    .map(|scope| scope.nodes.len())
3313                    .sum::<usize>(),
3314                graph.nodes.len()
3315            );
3316            let mut node_owners = vec![0usize; graph.nodes.len()];
3317            for scope in &index.scopes {
3318                for node in &scope.nodes {
3319                    node_owners[*node] += 1;
3320                }
3321            }
3322            assert!(node_owners.into_iter().all(|owners| owners == 1));
3323            assert_eq!(work_control.checked, work_control.charged);
3324        }
3325    }
3326
3327    #[test]
3328    fn separate_children_wrapper_work_is_linear_in_unique_items() {
3329        for depth in [8, 16, 32, 64, 128, 256] {
3330            let graph = deep_separate_graph(depth);
3331            let mut work_control = RecordingWorkControl::unlimited();
3332            let index = HierarchyIndex::build(&graph, &mut work_control).unwrap();
3333            let arena = std::iter::repeat_with(|| None)
3334                .take(index.scopes.len())
3335                .collect::<Vec<Option<ScopeLayout>>>();
3336            for scope in index.postorder.iter().copied() {
3337                index
3338                    .materialize_scope(scope, &arena, &mut work_control)
3339                    .unwrap();
3340            }
3341
3342            assert_eq!(work_control.charged, graph.nodes.len() * 3);
3343            assert_eq!(work_control.checked, work_control.charged);
3344        }
3345    }
3346
3347    #[test]
3348    fn hierarchy_index_work_is_linear_in_emitted_boundary_segments() {
3349        for depth in [4usize, 8, 16] {
3350            let mut baseline_work = RecordingWorkControl::unlimited();
3351            HierarchyIndex::build(&deep_cross_scope_graph(depth, 0), &mut baseline_work).unwrap();
3352
3353            for edge_count in [1usize, 4, 16] {
3354                let graph = deep_cross_scope_graph(depth, edge_count);
3355                let mut work_control = RecordingWorkControl::unlimited();
3356                let index = HierarchyIndex::build(&graph, &mut work_control).unwrap();
3357                let segment_count = index
3358                    .scopes
3359                    .iter()
3360                    .map(|scope| scope.edges.len())
3361                    .sum::<usize>();
3362
3363                assert_eq!(segment_count, edge_count * (depth + 1));
3364                // Each edge contributes two indexed descriptor visits. The combined owner/section
3365                // walk then charges exactly once for every hierarchy-local section it emits.
3366                assert_eq!(
3367                    work_control.charged - baseline_work.charged,
3368                    2 * edge_count + segment_count
3369                );
3370            }
3371        }
3372    }
3373
3374    #[test]
3375    fn elk_wrapper_export_and_flatten_work_is_linear_in_cross_scope_geometry() {
3376        const POINTS_PER_SEGMENT: usize = 5;
3377
3378        for edge_count in [1usize, 8, 32, 128] {
3379            let graph = repeated_cross_scope_graph(edge_count);
3380            let mut index_work = RecordingWorkControl::unlimited();
3381            let index = HierarchyIndex::build(&graph, &mut index_work).unwrap();
3382            assert_eq!(index.scopes.len(), 2);
3383            assert_eq!(
3384                index
3385                    .scopes
3386                    .iter()
3387                    .map(|scope| scope.edges.len())
3388                    .sum::<usize>(),
3389                edge_count * 2
3390            );
3391
3392            let mut flatten_work = RecordingWorkControl::unlimited();
3393            let result = flatten_scope_layouts(
3394                &index,
3395                synthetic_scope_arena(&index, POINTS_PER_SEGMENT),
3396                &mut flatten_work,
3397            )
3398            .unwrap();
3399
3400            // 2 scope-scan units + 2E geometry-scan units + (9 + 5E) structural units
3401            // + 2 * (10E points + E labels + 2E edge records) geometry units.
3402            assert_eq!(flatten_work.charged, 11 + 33 * edge_count);
3403            assert_eq!(flatten_work.checked, flatten_work.charged);
3404            assert_eq!(result.nodes.len(), graph.nodes.len());
3405            assert_eq!(result.edges.len(), edge_count);
3406
3407            let flat = flat_graph(
3408                vec![leaf("source"), leaf("target")],
3409                (0..edge_count)
3410                    .map(|index| {
3411                        let mut edge = edge(format!("flat-{index}").as_str(), "source", "target");
3412                        edge.label = Some(Label {
3413                            width: 20.0,
3414                            height: 10.0,
3415                        });
3416                        edge
3417                    })
3418                    .collect(),
3419            );
3420            let imported =
3421                source_port::import_graph(&graph_to_source_input(&flat).unwrap()).unwrap();
3422            let sort_work = match edge_count {
3423                1 => 0,
3424                8 => 24,
3425                32 => 160,
3426                128 => 896,
3427                _ => unreachable!("test matrix is fixed"),
3428            };
3429            // Two nodes, five linear export units per labelled straight edge, and the independent
3430            // E*ceil(log2(E)) comparison-sort bound used by the final Mermaid model-order pass.
3431            assert_eq!(
3432                source_graph_output_work_units(&imported),
3433                Ok(2 + 5 * edge_count + sort_work)
3434            );
3435        }
3436    }
3437
3438    #[test]
3439    fn output_sort_work_is_checked_and_superlinear() {
3440        assert_eq!(comparison_sort_work_units(0), Ok(0));
3441        assert_eq!(comparison_sort_work_units(1), Ok(0));
3442        assert_eq!(comparison_sort_work_units(2), Ok(2));
3443        assert_eq!(comparison_sort_work_units(3), Ok(6));
3444        assert_eq!(comparison_sort_work_units(8), Ok(24));
3445        assert_eq!(
3446            comparison_sort_work_units(usize::MAX),
3447            Err(WorkError::ArithmeticOverflow)
3448        );
3449    }
3450
3451    #[test]
3452    fn flatten_work_is_linear_in_points_at_fixed_cross_scope_cardinality() {
3453        const EDGE_COUNT: usize = 8;
3454        let graph = repeated_cross_scope_graph(EDGE_COUNT);
3455        let mut index_work = RecordingWorkControl::unlimited();
3456        let index = HierarchyIndex::build(&graph, &mut index_work).unwrap();
3457        let segment_count = index
3458            .scopes
3459            .iter()
3460            .map(|scope| scope.edges.len())
3461            .sum::<usize>();
3462        assert_eq!(segment_count, EDGE_COUNT * 2);
3463
3464        let measured = [1usize, 8, 64].map(|points_per_segment| {
3465            let mut work_control = RecordingWorkControl::unlimited();
3466            flatten_scope_layouts(
3467                &index,
3468                synthetic_scope_arena(&index, points_per_segment),
3469                &mut work_control,
3470            )
3471            .unwrap();
3472            (points_per_segment, work_control.charged)
3473        });
3474
3475        for pair in measured.windows(2) {
3476            let (before_points, before_work) = pair[0];
3477            let (after_points, after_work) = pair[1];
3478            assert_eq!(
3479                after_work - before_work,
3480                2 * segment_count * (after_points - before_points)
3481            );
3482        }
3483    }
3484
3485    #[test]
3486    fn flatten_geometry_execution_budget_is_atomic() {
3487        const EDGE_COUNT: usize = 4;
3488        const POINTS_PER_SEGMENT: usize = 5;
3489        // 2 scope-scan + 8 geometry-scan planning units, then one 29 structural + 104 geometry
3490        // execution tranche. A failed execution check must retain only the completed planning work.
3491        const PLANNING_WORK: usize = 10;
3492        const EXECUTION_WORK: usize = 133;
3493        const REQUIRED: usize = PLANNING_WORK + EXECUTION_WORK;
3494
3495        let graph = repeated_cross_scope_graph(EDGE_COUNT);
3496        let mut index_work = RecordingWorkControl::unlimited();
3497        let index = HierarchyIndex::build(&graph, &mut index_work).unwrap();
3498
3499        let mut below = RecordingWorkControl {
3500            remaining: REQUIRED - 1,
3501            checked: 0,
3502            charged: 0,
3503        };
3504        let error = flatten_scope_layouts(
3505            &index,
3506            synthetic_scope_arena(&index, POINTS_PER_SEGMENT),
3507            &mut below,
3508        )
3509        .unwrap_err();
3510        assert_eq!(error.work_error(), Some(WorkError::Interrupted));
3511        assert_eq!(below.charged, PLANNING_WORK);
3512        assert_eq!(below.remaining, EXECUTION_WORK - 1);
3513
3514        for extra in [0usize, 1] {
3515            let mut accepted = RecordingWorkControl {
3516                remaining: REQUIRED + extra,
3517                checked: 0,
3518                charged: 0,
3519            };
3520            let result = flatten_scope_layouts(
3521                &index,
3522                synthetic_scope_arena(&index, POINTS_PER_SEGMENT),
3523                &mut accepted,
3524            )
3525            .unwrap();
3526            assert_eq!(result.edges.len(), EDGE_COUNT);
3527            assert_eq!(accepted.charged, REQUIRED);
3528            assert_eq!(accepted.remaining, extra);
3529        }
3530    }
3531
3532    #[test]
3533    fn separate_children_edges_have_one_owner_and_output_sensitive_segments() {
3534        let mut a = leaf("a");
3535        a.parent = Some("left".to_string());
3536        let mut a2 = leaf("a2");
3537        a2.parent = Some("left".to_string());
3538        let mut b = leaf("b");
3539        b.parent = Some("right".to_string());
3540        let graph = flat_graph(
3541            vec![
3542                group("left", None, HierarchyHandling::SeparateChildren),
3543                a,
3544                a2,
3545                group("right", None, HierarchyHandling::SeparateChildren),
3546                b,
3547                leaf("outer"),
3548            ],
3549            vec![
3550                edge("a-a2", "a", "a2"),
3551                edge("a-outer", "a", "outer"),
3552                edge("a-b", "a", "b"),
3553                edge("left-a", "left", "a"),
3554            ],
3555        );
3556        let mut work_control = RecordingWorkControl::unlimited();
3557        let index = HierarchyIndex::build(&graph, &mut work_control).unwrap();
3558
3559        let mut owners = vec![0usize; graph.edges.len()];
3560        let mut segments = vec![0usize; graph.edges.len()];
3561        for scope in &index.scopes {
3562            for edge in &scope.owned_edges {
3563                owners[*edge] += 1;
3564            }
3565            for edge in &scope.edges {
3566                segments[edge.original] += 1;
3567            }
3568        }
3569        assert_eq!(owners, vec![1, 1, 1, 1]);
3570        assert_eq!(segments, vec![1, 2, 3, 1]);
3571    }
3572
3573    #[test]
3574    fn hierarchy_index_rejects_duplicate_edge_ids_before_scope_metadata_can_alias() {
3575        let graph = flat_graph(
3576            vec![leaf("a"), leaf("b"), leaf("c")],
3577            vec![edge("duplicate", "a", "b"), edge("duplicate", "a", "c")],
3578        );
3579        let mut work_control = RecordingWorkControl::unlimited();
3580
3581        let error = HierarchyIndex::build(&graph, &mut work_control).unwrap_err();
3582
3583        assert!(matches!(
3584            error,
3585            Error::SourceImport(source_port::ImportError::DuplicateEdge { id })
3586                if id == "duplicate"
3587        ));
3588    }
3589
3590    #[test]
3591    fn separate_children_segment_edge_order_is_unique_within_materialized_scope() {
3592        let mut nested_group = group("nested", Some("group"), HierarchyHandling::SeparateChildren);
3593        nested_group.label = None;
3594        let mut source = leaf("source");
3595        source.parent = Some("nested".to_string());
3596        let mut sibling = leaf("sibling");
3597        sibling.parent = Some("group".to_string());
3598        let graph = flat_graph(
3599            vec![
3600                group("group", None, HierarchyHandling::SeparateChildren),
3601                nested_group,
3602                source,
3603                sibling,
3604                leaf("root-target"),
3605            ],
3606            vec![
3607                edge("to-sibling", "source", "sibling"),
3608                edge("to-root", "source", "root-target"),
3609            ],
3610        );
3611        let mut work_control = RecordingWorkControl::unlimited();
3612        let index = HierarchyIndex::build(&graph, &mut work_control).unwrap();
3613        let nested_scope = index.child_scope_by_anchor[1].unwrap();
3614        let arena = std::iter::repeat_with(|| None)
3615            .take(index.scopes.len())
3616            .collect::<Vec<Option<ScopeLayout>>>();
3617
3618        let (_, segments, _) = index
3619            .materialize_scope(nested_scope, &arena, &mut work_control)
3620            .unwrap();
3621
3622        assert_eq!(
3623            segments
3624                .iter()
3625                .map(|segment| segment.edge.model_order)
3626                .collect::<Vec<_>>(),
3627            vec![Some(0), Some(0)]
3628        );
3629        assert_eq!(
3630            segments
3631                .iter()
3632                .map(|segment| segment.edge_order)
3633                .collect::<Vec<_>>(),
3634            vec![0, 1]
3635        );
3636    }
3637
3638    #[test]
3639    fn separate_children_layout_is_small_stack_safe_and_deterministic() {
3640        let graph = deep_separate_graph(256);
3641        let first = std::thread::Builder::new()
3642            .name("elk-separate-children-small-stack".to_string())
3643            .stack_size(128 * 1024)
3644            .spawn(move || layout(&graph))
3645            .unwrap()
3646            .join()
3647            .expect("separate-children layout must not overflow the worker stack")
3648            .unwrap();
3649        assert_eq!(first.nodes.len(), 257);
3650
3651        let replay_graph = deep_separate_graph(256);
3652        let replayed = layout(&replay_graph).unwrap();
3653        assert_eq!(first, replayed);
3654    }
3655
3656    #[test]
3657    fn source_graph_dump_is_small_stack_safe_for_deep_hierarchy() {
3658        let depth = 256;
3659        let graph = deep_include_graph(depth);
3660        let dump = std::thread::Builder::new()
3661            .name("elk-source-dump-small-stack".to_string())
3662            .stack_size(128 * 1024)
3663            .spawn(move || {
3664                SourcePhaseDiagnostics::from_graph(&graph)
3665                    .unwrap()
3666                    .graph_dump()
3667            })
3668            .unwrap()
3669            .join()
3670            .expect("source graph dump must not overflow the worker stack");
3671
3672        assert_eq!(
3673            dump.lines()
3674                .filter(|line| line.trim_start().starts_with("graph "))
3675                .count(),
3676            depth + 1
3677        );
3678    }
3679
3680    #[test]
3681    fn separate_children_cross_boundary_edges_merge_once_with_one_label() {
3682        let mut a = leaf("a");
3683        a.parent = Some("left".to_string());
3684        let mut b = leaf("b");
3685        b.parent = Some("right".to_string());
3686        let mut descendant_to_outer = edge("a-outer", "a", "outer");
3687        descendant_to_outer.label = Some(Label {
3688            width: 36.0,
3689            height: 14.0,
3690        });
3691        let graph = flat_graph(
3692            vec![
3693                group("left", None, HierarchyHandling::SeparateChildren),
3694                a,
3695                group("right", None, HierarchyHandling::SeparateChildren),
3696                b,
3697                leaf("outer"),
3698            ],
3699            vec![descendant_to_outer, edge("a-b", "a", "b")],
3700        );
3701
3702        let result = layout(&graph).unwrap();
3703        for edge_id in ["a-outer", "a-b"] {
3704            let matches = result
3705                .edges
3706                .iter()
3707                .filter(|edge| edge.id == edge_id)
3708                .collect::<Vec<_>>();
3709            assert_eq!(matches.len(), 1, "edge {edge_id} must be flattened once");
3710            assert!(matches[0].points.len() >= 2);
3711            assert!(
3712                matches[0]
3713                    .points
3714                    .iter()
3715                    .all(|point| point.x.is_finite() && point.y.is_finite())
3716            );
3717        }
3718        assert_eq!(
3719            result
3720                .edges
3721                .iter()
3722                .find(|edge| edge.id == "a-outer")
3723                .unwrap()
3724                .labels
3725                .len(),
3726            1
3727        );
3728    }
3729
3730    #[test]
3731    fn separate_children_cross_boundary_edges_keep_owner_model_order() {
3732        let mut left = leaf("left");
3733        left.parent = Some("group".to_string());
3734        let mut right = leaf("right");
3735        right.parent = Some("group".to_string());
3736        let mut graph = flat_graph(
3737            vec![
3738                group("group", None, HierarchyHandling::SeparateChildren),
3739                left,
3740                right,
3741                leaf("outer-a"),
3742                leaf("outer-b"),
3743            ],
3744            vec![
3745                edge("child-local", "left", "right"),
3746                edge("cross-boundary", "left", "outer-a"),
3747                edge("root-local", "outer-a", "outer-b"),
3748            ],
3749        );
3750        graph.options.layered.consider_model_order = true;
3751
3752        let mut work_control = RecordingWorkControl::unlimited();
3753        let index = HierarchyIndex::build(&graph, &mut work_control).unwrap();
3754        let arena = std::iter::repeat_with(|| None)
3755            .take(index.scopes.len())
3756            .collect::<Vec<Option<ScopeLayout>>>();
3757        let (input, segments, _) = index
3758            .materialize_scope(0, &arena, &mut work_control)
3759            .unwrap();
3760        let imported = source_port::import_graph_at_seed_scope_and_segments_with_work_control(
3761            &input,
3762            &index.scopes[0].seed_scope,
3763            &segments,
3764            &mut work_control,
3765        )
3766        .unwrap();
3767
3768        let model_order = |edge_id: &str| {
3769            imported
3770                .edges
3771                .iter()
3772                .find(|edge| edge.id == edge_id)
3773                .unwrap_or_else(|| panic!("missing imported edge {edge_id}"))
3774                .model_order
3775        };
3776        assert_eq!(model_order("cross-boundary"), Some(0));
3777        assert_eq!(model_order("root-local"), Some(1));
3778
3779        let result = layout(&graph).unwrap();
3780        assert_eq!(
3781            result
3782                .edges
3783                .iter()
3784                .map(|edge| edge.id.as_str())
3785                .collect::<Vec<_>>(),
3786            vec!["cross-boundary", "root-local", "child-local"]
3787        );
3788    }
3789
3790    fn assert_direct_parent_child_edge_precedes_later_root_edge(source: &str, target: &str) {
3791        let mut child = leaf("child");
3792        child.parent = Some("group".to_string());
3793        let graph = flat_graph(
3794            vec![
3795                group("group", None, HierarchyHandling::SeparateChildren),
3796                child,
3797                leaf("root-a"),
3798                leaf("root-b"),
3799            ],
3800            vec![
3801                edge("parent-child", source, target),
3802                edge("root-local", "root-a", "root-b"),
3803            ],
3804        );
3805        let mut work_control = RecordingWorkControl::unlimited();
3806        let index = HierarchyIndex::build(&graph, &mut work_control).unwrap();
3807
3808        let result =
3809            flatten_scope_layouts(&index, synthetic_scope_arena(&index, 2), &mut work_control)
3810                .unwrap();
3811
3812        assert_eq!(
3813            result
3814                .edges
3815                .iter()
3816                .map(|edge| edge.id.as_str())
3817                .collect::<Vec<_>>(),
3818            ["parent-child", "root-local"]
3819        );
3820    }
3821
3822    #[test]
3823    fn parent_to_direct_child_edge_keeps_owner_scope_order_when_flattened() {
3824        assert_direct_parent_child_edge_precedes_later_root_edge("group", "child");
3825    }
3826
3827    #[test]
3828    fn direct_child_to_parent_edge_keeps_owner_scope_order_when_flattened() {
3829        assert_direct_parent_child_edge_precedes_later_root_edge("child", "group");
3830    }
3831
3832    #[test]
3833    fn elk_work_control_interrupts_before_hierarchy_index_allocation() {
3834        let graph = deep_separate_graph(8);
3835        let initial_budget = graph.nodes.len() - 1;
3836        let mut work_control = RecordingWorkControl {
3837            remaining: initial_budget,
3838            checked: 0,
3839            charged: 0,
3840        };
3841
3842        let error = layout_with_work_control(&graph, &mut work_control).unwrap_err();
3843
3844        assert_eq!(error.work_error(), Some(WorkError::Interrupted));
3845        assert_eq!(work_control.remaining, initial_budget);
3846        assert_eq!(work_control.charged, 0);
3847    }
3848
3849    #[test]
3850    fn source_backed_layout_uses_default_median_layer_for_cross_hierarchy_center_label() {
3851        let group = |id: &str, parent: Option<&str>, label: Label| Node {
3852            id: id.to_string(),
3853            kind: NodeKind::Group,
3854            container: Default::default(),
3855            label_text: None,
3856            width: 0.0,
3857            height: 0.0,
3858            parent: parent.map(str::to_string),
3859            direction: None,
3860            hierarchy_handling: Some(HierarchyHandling::IncludeChildren),
3861            layer_constraint: None,
3862            port_alignment: None,
3863            label: Some(label),
3864        };
3865        let child = |id: &str, parent: &str, width: f64| Node {
3866            parent: Some(parent.to_string()),
3867            width,
3868            height: 54.0,
3869            ..leaf(id)
3870        };
3871        let labelled_edge = |id: &str, source: &str, target: &str, width: f64| Edge {
3872            label: Some(Label {
3873                width,
3874                height: 24.0,
3875            }),
3876            ..edge(id, source, target)
3877        };
3878        let graph = flat_graph(
3879            vec![
3880                group(
3881                    "container_Alpha",
3882                    None,
3883                    Label {
3884                        width: 116.859375,
3885                        height: 22.0,
3886                    },
3887                ),
3888                group(
3889                    "container_Beta",
3890                    Some("container_Alpha"),
3891                    Label {
3892                        width: 109.171875,
3893                        height: 22.0,
3894                    },
3895                ),
3896                child("process_C", "container_Beta", 131.28125),
3897                child("Process_D", "container_Beta", 130.78125),
3898                child("process_A", "container_Alpha", 131.15625),
3899                child("process_B", "container_Alpha", 130.765625),
3900            ],
3901            vec![
3902                edge("C-D", "process_C", "Process_D"),
3903                edge("A-B", "process_A", "process_B"),
3904                labelled_edge("B-Beta", "process_B", "container_Beta", 99.03125),
3905                labelled_edge("A-C", "process_A", "process_C", 66.609375),
3906            ],
3907        );
3908
3909        let result = layout(&graph).unwrap();
3910
3911        let alpha = result
3912            .nodes
3913            .iter()
3914            .find(|node| node.id == "container_Alpha")
3915            .expect("outer compound node");
3916        let cross_hierarchy_label = result
3917            .edges
3918            .iter()
3919            .find(|edge| edge.id == "A-C")
3920            .and_then(|edge| edge.labels.first())
3921            .expect("cross-hierarchy center label");
3922        let sibling_label = result
3923            .edges
3924            .iter()
3925            .find(|edge| edge.id == "B-Beta")
3926            .and_then(|edge| edge.labels.first())
3927            .expect("sibling center label");
3928
3929        // elkjs 0.9.3 with Mermaid 12 root and container options.
3930        assert_eq!(alpha.width, 295.375);
3931        assert_eq!(cross_hierarchy_label.x, 36.0);
3932        assert_eq!(cross_hierarchy_label.y, 192.0);
3933        assert_eq!(cross_hierarchy_label.width, 66.609375);
3934        assert_eq!(sibling_label.x, 167.9921875);
3935        assert_eq!(sibling_label.y, 255.0);
3936    }
3937
3938    #[test]
3939    fn source_backed_layout_accounts_for_inline_label_edge_thickness() {
3940        let mut a1 = leaf("a1");
3941        a1.parent = Some("one".to_string());
3942        a1.width = 76.796875;
3943        a1.height = 54.0;
3944        let mut a2 = leaf("a2");
3945        a2.parent = Some("one".to_string());
3946        a2.width = 76.796875;
3947        a2.height = 54.0;
3948        let mut first = edge("e1", "a1", "a2");
3949        first.label = Some(Label {
3950            width: 13.109375,
3951            height: 24.0,
3952        });
3953        let mut second = edge("e2", "a1", "a2");
3954        second.label = first.label;
3955        let mut graph = flat_graph(
3956            vec![
3957                Node {
3958                    id: "one".to_string(),
3959                    kind: NodeKind::Group,
3960                    container: Default::default(),
3961                    label_text: None,
3962                    width: 0.0,
3963                    height: 0.0,
3964                    parent: None,
3965                    direction: None,
3966                    hierarchy_handling: None,
3967                    layer_constraint: None,
3968                    port_alignment: None,
3969                    label: Some(Label {
3970                        width: 26.046875,
3971                        height: 22.0,
3972                    }),
3973                },
3974                a1,
3975                a2,
3976            ],
3977            vec![first, second],
3978        );
3979        graph.direction = Direction::Left;
3980
3981        let result = layout(&graph).unwrap();
3982        let group = result.nodes.iter().find(|node| node.id == "one").unwrap();
3983        let first = result.edges.iter().find(|edge| edge.id == "e1").unwrap();
3984        let second = result.edges.iter().find(|edge| edge.id == "e2").unwrap();
3985
3986        // elkjs 0.9.3 with Mermaid 12 root and container options.
3987        assert_eq!(group.width, 334.703125);
3988        assert_eq!(group.height, 145.0);
3989        assert_eq!(first.labels[0].x, 172.796875);
3990        assert_eq!(first.labels[0].y, 108.0);
3991        assert!((first.points[0].y - 103.4).abs() < 1e-9);
3992        assert_eq!(first.points[2].y, 120.5);
3993        assert_eq!(second.labels[0].x, 172.796875);
3994        assert_eq!(second.labels[0].y, 63.0);
3995        assert!((second.points[0].y - 92.6).abs() < 1e-9);
3996        assert_eq!(second.points[2].y, 75.5);
3997    }
3998
3999    #[test]
4000    fn source_backed_layout_places_connected_nodes_in_direction_order() {
4001        let graph = flat_graph(vec![leaf("A"), leaf("B")], vec![edge("A-B", "A", "B")]);
4002
4003        let result = layout(&graph).unwrap();
4004
4005        let a = result.nodes.iter().find(|node| node.id == "A").unwrap();
4006        let b = result.nodes.iter().find(|node| node.id == "B").unwrap();
4007        let edge = result.edges.iter().find(|edge| edge.id == "A-B").unwrap();
4008        assert!(b.y > a.y);
4009        assert!(edge.points.len() >= 2);
4010        assert_eq!(edge.points.first().unwrap().y, a.y + a.height / 2.0);
4011        assert_eq!(edge.points.last().unwrap().y, b.y - b.height / 2.0);
4012    }
4013
4014    #[test]
4015    fn source_backed_layout_honors_left_right_direction() {
4016        let mut graph = flat_graph(vec![leaf("A"), leaf("B")], vec![edge("A-B", "A", "B")]);
4017        graph.direction = Direction::Right;
4018
4019        let result = layout(&graph).unwrap();
4020
4021        let a = result.nodes.iter().find(|node| node.id == "A").unwrap();
4022        let b = result.nodes.iter().find(|node| node.id == "B").unwrap();
4023        assert!(b.x > a.x);
4024    }
4025
4026    #[test]
4027    fn source_ported_layout_rejects_unported_routing_before_layout() {
4028        let mut graph = flat_graph(vec![leaf("A"), leaf("B")], vec![edge("A-B", "A", "B")]);
4029        graph.options.layered.edge_routing = EdgeRouting::Polyline;
4030
4031        assert!(matches!(
4032            layout(&graph),
4033            Err(Error::SourcePipeline(
4034                source_port::PipelineError::UnsupportedProcessor {
4035                    kind: source_port::ProcessorKind::PolylineEdgeRouter,
4036                }
4037            ))
4038        ));
4039    }
4040
4041    #[test]
4042    fn leaf_label_measurements_do_not_create_layered_margins() {
4043        // Pinned elkjs 0.9.3 replay of newshapesset2_lr_allpairs_059 with the local
4044        // measured shapes. Treating the hidden 120px bolt/circle labels as fixed ELK
4045        // labels previously added 85 + 106 = 191px to the final node's x position.
4046        let sizes = [
4047            (169.4, 87.0),
4048            (172.0, 127.23614471649148),
4049            (35.0, 70.0),
4050            (14.0, 14.0),
4051            (162.0, 76.0),
4052        ];
4053        let nodes = sizes
4054            .into_iter()
4055            .enumerate()
4056            .map(|(i, (width, height))| Node {
4057                width,
4058                height,
4059                label: Some(Label {
4060                    width: 120.0,
4061                    height: if i == 0 { 63.0 } else { 42.0 },
4062                }),
4063                ..leaf(&format!("n{i}{i}"))
4064            })
4065            .collect();
4066        let mut edges = Vec::new();
4067        for from in 0..5 {
4068            for to in from + 1..5 {
4069                edges.push(edge(
4070                    &format!("L_n{from}{from}_n{to}{to}_0"),
4071                    &format!("n{from}{from}"),
4072                    &format!("n{to}{to}"),
4073                ));
4074            }
4075        }
4076        let mut graph = flat_graph(nodes, edges);
4077        graph.direction = Direction::Right;
4078        let input = graph_to_source_input(&graph).unwrap();
4079        assert!(input.nodes.iter().all(|node| node.label.is_none()));
4080        assert!(graph.nodes.iter().all(|node| node.label.is_some()));
4081        let actual = layout(&graph).unwrap();
4082        for (id, expected_x) in [
4083            ("n00", 96.7),
4084            ("n11", 327.4),
4085            ("n22", 470.9),
4086            ("n33", 575.4),
4087            ("n44", 723.4),
4088        ] {
4089            let node = actual.nodes.iter().find(|node| node.id == id).unwrap();
4090            assert!((node.x - expected_x).abs() < 1e-8, "{node:?}");
4091        }
4092        for node in &mut graph.nodes {
4093            node.label = None;
4094        }
4095        assert_eq!(actual, layout(&graph).unwrap());
4096    }
4097
4098    #[test]
4099    fn layered_scopes_preserve_group_labels_but_ignore_leaf_measurements() {
4100        for handling in [
4101            HierarchyHandling::IncludeChildren,
4102            HierarchyHandling::SeparateChildren,
4103        ] {
4104            let mut child = leaf("child");
4105            child.width = 14.0;
4106            child.height = 14.0;
4107            child.parent = Some("frame".into());
4108            child.label = Some(Label {
4109                width: 120.0,
4110                height: 42.0,
4111            });
4112            let mut frame = group("frame", None, handling);
4113            frame.label = Some(Label {
4114                width: 160.0,
4115                height: 24.0,
4116            });
4117            let mut graph = flat_graph(vec![frame, child], vec![]);
4118            if handling == HierarchyHandling::IncludeChildren {
4119                let input = graph_to_source_input(&graph).unwrap();
4120                assert!(
4121                    input
4122                        .nodes
4123                        .iter()
4124                        .find(|node| node.id == "frame")
4125                        .unwrap()
4126                        .label
4127                        .is_some()
4128                );
4129                assert!(
4130                    input
4131                        .nodes
4132                        .iter()
4133                        .find(|node| node.id == "child")
4134                        .unwrap()
4135                        .label
4136                        .is_none()
4137                );
4138            }
4139            let actual = layout(&graph).unwrap();
4140            graph.nodes[1].label = None;
4141            assert_eq!(actual, layout(&graph).unwrap(), "{handling:?}");
4142            graph.nodes[0].label = None;
4143            let without_title = layout(&graph).unwrap();
4144            let frame_size = |result: &LayoutResult| {
4145                let node = result.nodes.iter().find(|node| node.id == "frame").unwrap();
4146                (node.width, node.height)
4147            };
4148            assert_ne!(
4149                frame_size(&actual),
4150                frame_size(&without_title),
4151                "{handling:?}"
4152            );
4153        }
4154    }
4155
4156    #[test]
4157    fn source_backed_layout_excludes_empty_group_labels_from_elk_geometry() {
4158        let empty_group = Node {
4159            id: "B".to_string(),
4160            kind: NodeKind::Group,
4161            container: Default::default(),
4162            label_text: None,
4163            width: 0.0,
4164            height: 0.0,
4165            parent: None,
4166            direction: None,
4167            hierarchy_handling: None,
4168            layer_constraint: None,
4169            port_alignment: None,
4170            label: Some(Label {
4171                width: 9.0625,
4172                height: 22.0,
4173            }),
4174        };
4175        let mut laid_out_group = leaf("A");
4176        laid_out_group.width = 191.328125;
4177        laid_out_group.height = 105.0;
4178        let mut graph = flat_graph(vec![empty_group, laid_out_group], vec![]);
4179        graph.direction = Direction::Right;
4180
4181        let result = layout(&graph).unwrap();
4182        let empty_group = result.nodes.iter().find(|node| node.id == "B").unwrap();
4183        let laid_out_group = result.nodes.iter().find(|node| node.id == "A").unwrap();
4184
4185        assert_eq!(empty_group.width, 0.0);
4186        assert_eq!(empty_group.height, 0.0);
4187        assert_eq!(laid_out_group.y - laid_out_group.height / 2.0, 52.0);
4188    }
4189
4190    #[test]
4191    fn source_backed_layout_routes_long_edge_after_joiner() {
4192        let graph = flat_graph(
4193            vec![leaf("A"), leaf("B"), leaf("C")],
4194            vec![
4195                edge("A-B", "A", "B"),
4196                edge("B-C", "B", "C"),
4197                edge("A-C", "A", "C"),
4198            ],
4199        );
4200
4201        let result = layout(&graph).unwrap();
4202
4203        let long = result.edges.iter().find(|edge| edge.id == "A-C").unwrap();
4204        assert_eq!(
4205            result.edges.iter().filter(|edge| edge.id == "A-C").count(),
4206            1
4207        );
4208        assert!(long.points.len() > 4);
4209    }
4210
4211    #[test]
4212    fn source_backed_layout_exports_edge_label_layouts() {
4213        let mut labelled = edge("A-C", "A", "C");
4214        labelled.label = Some(Label {
4215            width: 48.0,
4216            height: 12.0,
4217        });
4218        let graph = flat_graph(
4219            vec![leaf("A"), leaf("B"), leaf("C")],
4220            vec![edge("A-B", "A", "B"), edge("B-C", "B", "C"), labelled],
4221        );
4222
4223        let result = layout(&graph).unwrap();
4224
4225        let edge = result.edges.iter().find(|edge| edge.id == "A-C").unwrap();
4226        let label = edge
4227            .labels
4228            .first()
4229            .expect("source-backed ELK should export placed edge label bounds");
4230        assert_eq!(label.width, 48.0);
4231        assert_eq!(label.height, 12.0);
4232        assert!(label.x.is_finite());
4233        assert!(label.y.is_finite());
4234    }
4235
4236    #[test]
4237    fn layered_options_to_source_propagates_inside_self_loops_activate() {
4238        let mut graph = flat_graph(vec![leaf("A")], vec![]);
4239        graph.options.layered.inside_self_loops_activate = true;
4240
4241        let input = graph_to_source_input(&graph).unwrap();
4242
4243        assert!(input.options.inside_self_loops_activate);
4244    }
4245
4246    #[test]
4247    fn layered_options_to_source_preserves_upstream_random_seed_sentinel() {
4248        let mut graph = flat_graph(vec![leaf("A")], vec![]);
4249        graph.options.layered.random_seed = 0;
4250
4251        let input = graph_to_source_input(&graph).unwrap();
4252
4253        assert_eq!(input.options.random_seed, 0);
4254    }
4255
4256    #[test]
4257    fn raw_layout_rejects_unseeded_elk_zero_but_operation_seed_is_replayable() {
4258        use std::num::NonZeroU64;
4259
4260        let mut graph = flat_graph(vec![leaf("A"), leaf("B")], vec![edge("A-B", "A", "B")]);
4261        graph.options.layered.random_seed = 0;
4262
4263        assert!(matches!(
4264            layout(&graph),
4265            Err(Error::SourcePipeline(source_port::PipelineError::RandomSeed(
4266                source_port::RandomSeedError::Unresolved { graph_path }
4267            ))) if graph_path == "root"
4268        ));
4269
4270        let operation_seed = ElkOperationSeed::from_operation_seed(
4271            NonZeroU64::new(0x6d65_726d_616e).expect("nonzero operation seed"),
4272        );
4273        let first =
4274            layout_with_operation_seed(&graph, operation_seed).expect("deterministic layout");
4275        let replayed = layout_with_operation_seed(&graph, operation_seed).expect("replayed layout");
4276
4277        assert_eq!(first, replayed);
4278    }
4279
4280    #[test]
4281    fn source_phase_diagnostics_uses_the_same_zero_seed_boundary() {
4282        use std::num::NonZeroU64;
4283
4284        let mut graph = flat_graph(vec![leaf("A"), leaf("B")], vec![edge("A-B", "A", "B")]);
4285        graph.options.layered.random_seed = 0;
4286
4287        let mut raw = SourcePhaseDiagnostics::from_graph(&graph).expect("diagnostic session");
4288        assert!(matches!(
4289            raw.execute_all(),
4290            Err(Error::SourcePipeline(source_port::PipelineError::RandomSeed(
4291                source_port::RandomSeedError::Unresolved { graph_path }
4292            ))) if graph_path == "root"
4293        ));
4294
4295        let operation_seed = ElkOperationSeed::from_operation_seed(
4296            NonZeroU64::new(0x6469_6167_6e6f_7374).expect("nonzero operation seed"),
4297        );
4298        let mut first =
4299            SourcePhaseDiagnostics::from_graph_with_operation_seed(&graph, operation_seed)
4300                .expect("seeded diagnostic session");
4301        let mut replayed =
4302            SourcePhaseDiagnostics::from_graph_with_operation_seed(&graph, operation_seed)
4303                .expect("replayed seeded diagnostic session");
4304
4305        assert_eq!(
4306            first.execute_all().unwrap(),
4307            replayed.execute_all().unwrap()
4308        );
4309    }
4310
4311    #[test]
4312    fn graph_to_source_input_propagates_inside_self_loop_edge_flag() {
4313        let graph = flat_graph(
4314            vec![leaf("A")],
4315            vec![Edge {
4316                inside_self_loops_yo: true,
4317                ..edge("A-A", "A", "A")
4318            }],
4319        );
4320
4321        let input = graph_to_source_input(&graph).unwrap();
4322
4323        assert!(input.edges[0].inside_self_loops_yo);
4324    }
4325
4326    #[test]
4327    fn source_graph_export_applies_graph_offset_and_padding_to_layout() {
4328        let mut graph = LGraph::new("root", SourceLayeredOptions::default());
4329        graph.offset = LPoint { x: 1.0, y: 2.0 };
4330        graph.padding = source_port::LPadding {
4331            top: 7.0,
4332            right: 0.0,
4333            bottom: 0.0,
4334            left: 12.0,
4335        };
4336
4337        let mut a = source_port::LNode::new("A", 10.0, 20.0, None);
4338        a.position = LPoint { x: 3.0, y: 5.0 };
4339        let mut b = source_port::LNode::new("B", 10.0, 20.0, None);
4340        b.position = LPoint { x: 50.0, y: 60.0 };
4341        graph.layerless_nodes.push(a);
4342        graph.layerless_nodes.push(b);
4343
4344        let source = graph
4345            .add_port(
4346                0,
4347                source_port::PortType::Output,
4348                source_port::PortSide::South,
4349                LPoint { x: 5.0, y: 20.0 },
4350            )
4351            .unwrap();
4352        let target = graph
4353            .add_port(
4354                1,
4355                source_port::PortType::Input,
4356                source_port::PortSide::North,
4357                LPoint { x: 5.0, y: 0.0 },
4358            )
4359            .unwrap();
4360
4361        let mut label = source_port::LLabel::new("label", 6.0, 7.0);
4362        label.position = LPoint { x: 30.0, y: 40.0 };
4363        graph
4364            .add_edge(source_port::LayeredEdge {
4365                id: "A-B".to_string(),
4366                source,
4367                target,
4368                source_node_id: "A".to_string(),
4369                target_node_id: "B".to_string(),
4370                labels: vec![label],
4371                minlen: 1,
4372                reversed: false,
4373                bend_points: vec![LPoint { x: 20.0, y: 30.0 }],
4374                model_order: None,
4375                priority_direction: 0,
4376                priority_shortness: 0,
4377                priority_straightness: 0,
4378                thickness: 0.0,
4379                original_opposite_port: None,
4380                compound_segment: None,
4381            })
4382            .unwrap();
4383
4384        let result = source_graph_to_layout_result(&graph);
4385
4386        let a = result.nodes.iter().find(|node| node.id == "A").unwrap();
4387        let b = result.nodes.iter().find(|node| node.id == "B").unwrap();
4388        let edge = result.edges.iter().find(|edge| edge.id == "A-B").unwrap();
4389        assert_eq!(a.x, 21.0);
4390        assert_eq!(a.y, 24.0);
4391        assert_eq!(b.x, 68.0);
4392        assert_eq!(b.y, 79.0);
4393        assert_eq!(edge.points[0], Point { x: 21.0, y: 34.0 });
4394        assert_eq!(edge.points[1], Point { x: 33.0, y: 39.0 });
4395        assert_eq!(edge.points[2], Point { x: 68.0, y: 69.0 });
4396        assert_eq!(edge.labels[0].x, 43.0);
4397        assert_eq!(edge.labels[0].y, 49.0);
4398    }
4399
4400    #[test]
4401    fn source_graph_export_groups_compound_segments_by_original_edge_id() {
4402        let mut graph = LGraph::new("root", SourceLayeredOptions::default());
4403        graph
4404            .layerless_nodes
4405            .push(source_port::LNode::new("A", 10.0, 20.0, None));
4406        graph
4407            .layerless_nodes
4408            .push(source_port::LNode::new("B", 10.0, 20.0, None));
4409
4410        let source = graph
4411            .add_port(
4412                0,
4413                source_port::PortType::Output,
4414                source_port::PortSide::South,
4415                LPoint { x: 5.0, y: 20.0 },
4416            )
4417            .unwrap();
4418        let target = graph
4419            .add_port(
4420                1,
4421                source_port::PortType::Input,
4422                source_port::PortSide::North,
4423                LPoint { x: 5.0, y: 0.0 },
4424            )
4425            .unwrap();
4426
4427        let segment_edge = graph
4428            .add_edge(source_port::LayeredEdge {
4429                id: "merged-segment".to_string(),
4430                source,
4431                target,
4432                source_node_id: "A".to_string(),
4433                target_node_id: "B".to_string(),
4434                labels: Vec::new(),
4435                minlen: 1,
4436                reversed: false,
4437                bend_points: Vec::new(),
4438                model_order: None,
4439                priority_direction: 0,
4440                priority_shortness: 0,
4441                priority_straightness: 0,
4442                thickness: 0.0,
4443                original_opposite_port: None,
4444                compound_segment: None,
4445            })
4446            .unwrap();
4447        graph
4448            .cross_hierarchy_edges
4449            .push(source_port::CrossHierarchyEdge {
4450                original_edge_id: "A-B".to_string(),
4451                original_model_order: None,
4452                graph_id: "root".to_string(),
4453                edge: segment_edge,
4454                segment: source_port::CompoundEdgeSegment::Output { depth: 0 },
4455            });
4456
4457        let result = source_graph_to_layout_result(&graph);
4458
4459        assert!(result.edges.iter().any(|edge| edge.id == "A-B"));
4460        assert!(!result.edges.iter().any(|edge| edge.id == "merged-segment"));
4461    }
4462
4463    #[test]
4464    fn compound_segment_counting_order_matches_elk_cross_hierarchy_order() {
4465        let segment = |segment| CompoundEdgeLayoutSegment {
4466            original_edge_id: "edge".to_string(),
4467            segment,
4468            model_order: None,
4469            edge: EdgeLayout {
4470                id: "edge".to_string(),
4471                points: Vec::new(),
4472                labels: Vec::new(),
4473            },
4474        };
4475        let mut segments = vec![
4476            segment(source_port::CompoundEdgeSegment::Input { depth: 4 }),
4477            segment(source_port::CompoundEdgeSegment::Output { depth: 5 }),
4478            segment(source_port::CompoundEdgeSegment::Input { depth: 2 }),
4479            segment(source_port::CompoundEdgeSegment::Output { depth: 3 }),
4480            segment(source_port::CompoundEdgeSegment::Output { depth: 4 }),
4481            segment(source_port::CompoundEdgeSegment::Input { depth: 3 }),
4482        ];
4483
4484        order_compound_layout_segments(&mut segments);
4485
4486        assert_eq!(
4487            segments
4488                .into_iter()
4489                .map(|segment| segment.segment)
4490                .collect::<Vec<_>>(),
4491            vec![
4492                source_port::CompoundEdgeSegment::Output { depth: 5 },
4493                source_port::CompoundEdgeSegment::Output { depth: 4 },
4494                source_port::CompoundEdgeSegment::Output { depth: 3 },
4495                source_port::CompoundEdgeSegment::Input { depth: 2 },
4496                source_port::CompoundEdgeSegment::Input { depth: 3 },
4497                source_port::CompoundEdgeSegment::Input { depth: 4 },
4498            ]
4499        );
4500    }
4501
4502    #[test]
4503    fn source_graph_export_all_original_edges_for_shared_compound_segment() {
4504        let mut graph = LGraph::new("root", SourceLayeredOptions::default());
4505        graph
4506            .layerless_nodes
4507            .push(source_port::LNode::new("A", 10.0, 20.0, None));
4508        graph
4509            .layerless_nodes
4510            .push(source_port::LNode::new("B", 10.0, 20.0, None));
4511
4512        let source = graph
4513            .add_port(
4514                0,
4515                source_port::PortType::Output,
4516                source_port::PortSide::South,
4517                LPoint { x: 5.0, y: 20.0 },
4518            )
4519            .unwrap();
4520        let target = graph
4521            .add_port(
4522                1,
4523                source_port::PortType::Input,
4524                source_port::PortSide::North,
4525                LPoint { x: 5.0, y: 0.0 },
4526            )
4527            .unwrap();
4528
4529        let segment_edge = graph
4530            .add_edge(source_port::LayeredEdge {
4531                id: "merged-segment".to_string(),
4532                source,
4533                target,
4534                source_node_id: "A".to_string(),
4535                target_node_id: "B".to_string(),
4536                labels: Vec::new(),
4537                minlen: 1,
4538                reversed: false,
4539                bend_points: Vec::new(),
4540                model_order: None,
4541                priority_direction: 0,
4542                priority_shortness: 0,
4543                priority_straightness: 0,
4544                thickness: 0.0,
4545                original_opposite_port: None,
4546                compound_segment: None,
4547            })
4548            .unwrap();
4549
4550        for original_edge_id in ["A-B-1", "A-B-2"] {
4551            graph
4552                .cross_hierarchy_edges
4553                .push(source_port::CrossHierarchyEdge {
4554                    original_edge_id: original_edge_id.to_string(),
4555                    original_model_order: None,
4556                    graph_id: "root".to_string(),
4557                    edge: segment_edge,
4558                    segment: source_port::CompoundEdgeSegment::Output { depth: 0 },
4559                });
4560        }
4561
4562        let result = source_graph_to_layout_result(&graph);
4563
4564        assert!(result.edges.iter().any(|edge| edge.id == "A-B-1"));
4565        assert!(result.edges.iter().any(|edge| edge.id == "A-B-2"));
4566        assert!(!result.edges.iter().any(|edge| edge.id == "merged-segment"));
4567    }
4568
4569    #[test]
4570    fn source_graph_export_filters_shared_compound_segment_labels_by_original_edge() {
4571        let mut graph = LGraph::new("root", SourceLayeredOptions::default());
4572        graph
4573            .layerless_nodes
4574            .push(source_port::LNode::new("A", 10.0, 20.0, None));
4575        graph
4576            .layerless_nodes
4577            .push(source_port::LNode::new("B", 10.0, 20.0, None));
4578
4579        let source = graph
4580            .add_port(
4581                0,
4582                source_port::PortType::Output,
4583                source_port::PortSide::South,
4584                LPoint { x: 5.0, y: 20.0 },
4585            )
4586            .unwrap();
4587        let target = graph
4588            .add_port(
4589                1,
4590                source_port::PortType::Input,
4591                source_port::PortSide::North,
4592                LPoint { x: 5.0, y: 0.0 },
4593            )
4594            .unwrap();
4595        let mut first_label = source_port::LLabel::new("first", 10.0, 4.0);
4596        first_label.original_label_edge = Some("A-B-1".to_string());
4597        let mut second_label = source_port::LLabel::new("second", 20.0, 4.0);
4598        second_label.original_label_edge = Some("A-B-2".to_string());
4599
4600        let segment_edge = graph
4601            .add_edge(source_port::LayeredEdge {
4602                id: "merged-segment".to_string(),
4603                source,
4604                target,
4605                source_node_id: "A".to_string(),
4606                target_node_id: "B".to_string(),
4607                labels: vec![first_label, second_label],
4608                minlen: 1,
4609                reversed: false,
4610                bend_points: Vec::new(),
4611                model_order: None,
4612                priority_direction: 0,
4613                priority_shortness: 0,
4614                priority_straightness: 0,
4615                thickness: 0.0,
4616                original_opposite_port: None,
4617                compound_segment: None,
4618            })
4619            .unwrap();
4620
4621        for original_edge_id in ["A-B-1", "A-B-2"] {
4622            graph
4623                .cross_hierarchy_edges
4624                .push(source_port::CrossHierarchyEdge {
4625                    original_edge_id: original_edge_id.to_string(),
4626                    original_model_order: None,
4627                    graph_id: "root".to_string(),
4628                    edge: segment_edge,
4629                    segment: source_port::CompoundEdgeSegment::Output { depth: 0 },
4630                });
4631        }
4632
4633        let result = source_graph_to_layout_result(&graph);
4634        let first = result.edges.iter().find(|edge| edge.id == "A-B-1").unwrap();
4635        let second = result.edges.iter().find(|edge| edge.id == "A-B-2").unwrap();
4636
4637        assert_eq!(first.labels.len(), 1);
4638        assert_eq!(first.labels[0].width, 10.0);
4639        assert_eq!(second.labels.len(), 1);
4640        assert_eq!(second.labels[0].width, 20.0);
4641    }
4642
4643    #[test]
4644    fn source_backed_layout_exports_nested_compound_nodes_with_parent_offset() {
4645        let mut child = leaf("A");
4646        child.parent = Some("cluster".to_string());
4647        let mut second_child = leaf("B");
4648        second_child.parent = Some("cluster".to_string());
4649        let mut graph = flat_graph(
4650            vec![
4651                Node {
4652                    id: "cluster".to_string(),
4653                    kind: NodeKind::Group,
4654                    container: Default::default(),
4655                    label_text: None,
4656                    width: 0.0,
4657                    height: 0.0,
4658                    parent: None,
4659                    direction: Some(Direction::Down),
4660                    hierarchy_handling: None,
4661                    layer_constraint: None,
4662                    port_alignment: None,
4663                    label: None,
4664                },
4665                child,
4666                second_child,
4667            ],
4668            vec![edge("A-B", "A", "B")],
4669        );
4670        graph.options.layered.hierarchy_handling = HierarchyHandling::IncludeChildren;
4671
4672        let result = layout(&graph).unwrap();
4673
4674        let cluster = result
4675            .nodes
4676            .iter()
4677            .find(|node| node.id == "cluster")
4678            .unwrap();
4679        let a = result.nodes.iter().find(|node| node.id == "A").unwrap();
4680        let b = result.nodes.iter().find(|node| node.id == "B").unwrap();
4681        let edge = result.edges.iter().find(|edge| edge.id == "A-B").unwrap();
4682        assert_eq!(result.nodes.len(), 3);
4683        assert!(cluster.width >= a.width);
4684        assert!(cluster.height >= b.y - a.y);
4685        assert!(a.y > cluster.y - cluster.height / 2.0);
4686        assert!(b.y < cluster.y + cluster.height / 2.0);
4687        assert!(b.y > a.y);
4688        assert_eq!(edge.points.first().unwrap().y, a.y + a.height / 2.0);
4689        assert_eq!(edge.points.last().unwrap().y, b.y - b.height / 2.0);
4690    }
4691
4692    #[test]
4693    fn source_backed_layout_routes_cross_hierarchy_edge() {
4694        let mut child = leaf("A");
4695        child.parent = Some("cluster".to_string());
4696        let mut graph = flat_graph(
4697            vec![
4698                Node {
4699                    id: "cluster".to_string(),
4700                    kind: NodeKind::Group,
4701                    container: Default::default(),
4702                    label_text: None,
4703                    width: 0.0,
4704                    height: 0.0,
4705                    parent: None,
4706                    direction: Some(Direction::Down),
4707                    hierarchy_handling: None,
4708                    layer_constraint: None,
4709                    port_alignment: None,
4710                    label: None,
4711                },
4712                child,
4713            ],
4714            vec![edge("cluster-A", "cluster", "A")],
4715        );
4716        graph.options.layered.hierarchy_handling = HierarchyHandling::IncludeChildren;
4717
4718        let result = layout(&graph).unwrap();
4719
4720        let cluster = result
4721            .nodes
4722            .iter()
4723            .find(|node| node.id == "cluster")
4724            .unwrap();
4725        let child = result.nodes.iter().find(|node| node.id == "A").unwrap();
4726        let edge = result
4727            .edges
4728            .iter()
4729            .find(|edge| edge.id == "cluster-A")
4730            .unwrap();
4731        assert_eq!(result.nodes.len(), 2);
4732        assert!(edge.points.len() >= 2);
4733        assert!(
4734            edge.points.first().unwrap().x >= cluster.x - cluster.width / 2.0
4735                && edge.points.first().unwrap().x <= cluster.x + cluster.width / 2.0
4736        );
4737        assert_eq!(edge.points.last().unwrap().x, child.x);
4738    }
4739
4740    #[test]
4741    fn source_backed_layout_exports_edge_from_nested_child_to_outer_node() {
4742        let mut child = leaf("A");
4743        child.parent = Some("cluster".to_string());
4744        let mut graph = flat_graph(
4745            vec![
4746                Node {
4747                    id: "cluster".to_string(),
4748                    kind: NodeKind::Group,
4749                    container: Default::default(),
4750                    label_text: None,
4751                    width: 0.0,
4752                    height: 0.0,
4753                    parent: None,
4754                    direction: Some(Direction::Down),
4755                    hierarchy_handling: None,
4756                    layer_constraint: None,
4757                    port_alignment: None,
4758                    label: None,
4759                },
4760                child,
4761                leaf("B"),
4762            ],
4763            vec![edge("A-B", "A", "B")],
4764        );
4765        graph.options.layered.hierarchy_handling = HierarchyHandling::IncludeChildren;
4766
4767        let result = layout(&graph).unwrap();
4768        let b = result.nodes.iter().find(|node| node.id == "B").unwrap();
4769        let edge = result
4770            .edges
4771            .iter()
4772            .find(|edge| edge.id == "A-B")
4773            .expect("cross-hierarchy child edge should be exported");
4774        assert!(edge.points.len() >= 2);
4775        assert!(
4776            edge.points
4777                .iter()
4778                .all(|point| point.x.is_finite() && point.y.is_finite())
4779        );
4780        assert_eq!(edge.points.last().unwrap().x, b.x);
4781    }
4782
4783    #[test]
4784    fn source_backed_layout_recursively_lays_out_separate_children() {
4785        let mut child = leaf("A");
4786        child.parent = Some("cluster".to_string());
4787        let mut second_child = leaf("B");
4788        second_child.parent = Some("cluster".to_string());
4789        let mut graph = flat_graph(
4790            vec![
4791                Node {
4792                    id: "cluster".to_string(),
4793                    kind: NodeKind::Group,
4794                    container: Default::default(),
4795                    label_text: None,
4796                    width: 0.0,
4797                    height: 0.0,
4798                    parent: None,
4799                    direction: Some(Direction::Right),
4800                    hierarchy_handling: Some(HierarchyHandling::SeparateChildren),
4801                    layer_constraint: None,
4802                    port_alignment: None,
4803                    label: Some(Label {
4804                        width: 42.0,
4805                        height: 18.0,
4806                    }),
4807                },
4808                child,
4809                second_child,
4810                leaf("outer"),
4811            ],
4812            vec![
4813                edge("A-B", "A", "B"),
4814                edge("cluster-outer", "cluster", "outer"),
4815            ],
4816        );
4817        graph.direction = Direction::Down;
4818        graph.options.layered.hierarchy_handling = HierarchyHandling::IncludeChildren;
4819
4820        let result = layout(&graph).unwrap();
4821
4822        let cluster = result
4823            .nodes
4824            .iter()
4825            .find(|node| node.id == "cluster")
4826            .unwrap();
4827        let a = result.nodes.iter().find(|node| node.id == "A").unwrap();
4828        let b = result.nodes.iter().find(|node| node.id == "B").unwrap();
4829        let outer = result.nodes.iter().find(|node| node.id == "outer").unwrap();
4830        let inner_edge = result.edges.iter().find(|edge| edge.id == "A-B").unwrap();
4831        let outer_edge = result
4832            .edges
4833            .iter()
4834            .find(|edge| edge.id == "cluster-outer")
4835            .unwrap();
4836
4837        assert!(cluster.width >= b.x + b.width / 2.0 - (a.x - a.width / 2.0));
4838        assert!(cluster.height >= 18.0);
4839        assert!(a.x < b.x);
4840        assert!(outer.y > cluster.y);
4841        assert_eq!(inner_edge.points.first().unwrap().y, a.y);
4842        assert_eq!(inner_edge.points.last().unwrap().y, b.y);
4843        assert_eq!(outer_edge.points.first().unwrap().x, cluster.x);
4844    }
4845}