1#![forbid(unsafe_code)]
2
3use 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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
50pub struct ElkOperationSeed(source_port::OperationSeed);
51
52impl ElkOperationSeed {
53 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
70pub 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 pub fn from_graph(graph: &Graph) -> Result<Self> {
95 Self::from_graph_with_optional_operation_seed(graph, None)
96 }
97
98 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 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 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 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 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 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 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 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 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
244pub fn layout(graph: &Graph) -> Result<LayoutResult> {
247 let mut work_control = NoopWorkControl;
248 layout_with_work_control(graph, &mut work_control)
249}
250
251pub 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
259pub 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
273pub 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 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 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 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 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 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 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 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 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 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 return Err(Error::UnsupportedCrossProviderEdge {
1080 edge_id: edge.id.clone(),
1081 });
1082 }
1083 if scopes[owner].algorithm != Algorithm::Layered {
1084 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 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 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 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 self.edge_model_order[scoped.original]
1383 } else {
1384 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 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 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 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 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 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 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 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 ¤t.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 ¤t.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
2035fn 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 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 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
2762fn 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 for nested in [false, true] {
2954 let expected = if nested {
2955 [[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 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 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 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 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 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 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 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}