use std::cmp::Ordering;
use std::collections::{BTreeMap, HashMap, HashSet};
use crate::mermaid_engine::config::LayoutConfig;
use crate::mermaid_engine::ir::{DiagramKind, Graph};
use crate::mermaid_engine::theme::Theme;
use super::super::ranking::{compute_ranks_subset, order_rank_nodes, rank_edges_for_manual_layout};
use super::super::{NodeLayout, TextBlock, is_horizontal};
const LABEL_RANK_FONT_SCALE: f32 = 0.5;
const LABEL_RANK_MIN_GAP: f32 = 8.0;
fn build_ordering_edges(
layout_edges: &[crate::mermaid_engine::ir::Edge],
shifted_ranks: &HashMap<String, usize>,
rank_nodes: &mut [Vec<String>],
order_map: &mut HashMap<String, usize>,
label_dummy_at_rank: &HashMap<usize, (usize, String)>,
dummy_counter: &mut usize,
) -> Vec<crate::mermaid_engine::ir::Edge> {
let mut ordering_edges: Vec<crate::mermaid_engine::ir::Edge> = Vec::new();
for (edge_idx, edge) in layout_edges.iter().enumerate() {
let Some(&from_rank) = shifted_ranks.get(&edge.from) else {
continue;
};
let Some(&to_rank) = shifted_ranks.get(&edge.to) else {
continue;
};
if to_rank <= from_rank {
ordering_edges.push(edge.clone());
continue;
}
let span = to_rank - from_rank;
if span <= 1 {
ordering_edges.push(edge.clone());
continue;
}
let label_dummy_info = label_dummy_at_rank.get(&edge_idx);
let mut prev = edge.from.clone();
for step in 1..span {
let current_rank = from_rank + step;
let dummy_id = if let Some((lr, lid)) = label_dummy_info {
if current_rank == *lr {
lid.clone()
} else {
let id = format!("__dummy_{}__", *dummy_counter);
*dummy_counter += 1;
let order_idx = order_map.len();
order_map.insert(id.clone(), order_idx);
if let Some(bucket) = rank_nodes.get_mut(current_rank) {
bucket.push(id.clone());
}
id
}
} else {
let id = format!("__dummy_{}__", *dummy_counter);
*dummy_counter += 1;
let order_idx = order_map.len();
order_map.insert(id.clone(), order_idx);
if let Some(bucket) = rank_nodes.get_mut(current_rank) {
bucket.push(id.clone());
}
id
};
ordering_edges.push(crate::mermaid_engine::ir::Edge {
from: prev.clone(),
to: dummy_id.clone(),
label: None,
start_label: None,
end_label: None,
directed: true,
arrow_start: false,
arrow_end: false,
arrow_start_kind: None,
arrow_end_kind: None,
start_decoration: None,
end_decoration: None,
style: crate::mermaid_engine::ir::EdgeStyle::Solid,
});
prev = dummy_id;
}
ordering_edges.push(crate::mermaid_engine::ir::Edge {
from: prev,
to: edge.to.clone(),
label: None,
start_label: None,
end_label: None,
directed: true,
arrow_start: false,
arrow_end: false,
arrow_start_kind: None,
arrow_end_kind: None,
start_decoration: None,
end_decoration: None,
style: crate::mermaid_engine::ir::EdgeStyle::Solid,
});
}
ordering_edges
}
pub(in crate::mermaid_engine::layout) fn assign_positions_manual(
graph: &Graph,
layout_node_ids: &[String],
layout_set: &HashSet<String>,
nodes: &mut BTreeMap<String, NodeLayout>,
config: &LayoutConfig,
layout_edges: &[crate::mermaid_engine::ir::Edge],
theme: &Theme,
pre_measured_labels: &[Option<TextBlock>],
label_dummy_ids: &mut [Option<String>],
) {
let mut edge_labels_vec: Vec<Option<TextBlock>> = Vec::new();
let mut original_edge_indices: Vec<usize> = Vec::new();
let layout_edges: Vec<crate::mermaid_engine::ir::Edge> = layout_edges
.iter()
.enumerate()
.filter(|(_, edge)| layout_set.contains(&edge.from) && layout_set.contains(&edge.to))
.map(|(i, edge)| {
edge_labels_vec.push(pre_measured_labels.get(i).cloned().unwrap_or(None));
original_edge_indices.push(i);
edge.clone()
})
.collect();
let edge_labels = edge_labels_vec;
let rank_edges = rank_edges_for_manual_layout(graph, layout_node_ids, &layout_edges);
let mut ranks = compute_ranks_subset(layout_node_ids, &rank_edges, &graph.node_order);
if graph.kind == DiagramKind::Class {
let mut hierarchy_nodes: HashSet<String> = HashSet::new();
for edge in &layout_edges {
let has_open_triangle = matches!(
edge.arrow_start_kind,
Some(crate::mermaid_engine::ir::EdgeArrowhead::OpenTriangle)
) || matches!(
edge.arrow_end_kind,
Some(crate::mermaid_engine::ir::EdgeArrowhead::OpenTriangle)
);
if has_open_triangle {
hierarchy_nodes.insert(edge.from.clone());
hierarchy_nodes.insert(edge.to.clone());
}
}
if !hierarchy_nodes.is_empty() {
let min_hierarchy_rank = hierarchy_nodes
.iter()
.filter_map(|id| ranks.get(id).copied())
.min()
.unwrap_or(0);
let mut pending_updates: Vec<(String, usize)> = Vec::new();
for node_id in layout_node_ids {
if hierarchy_nodes.contains(node_id) {
continue;
}
let mut sum = 0.0f32;
let mut count = 0usize;
for edge in &layout_edges {
if edge.from == *node_id {
if let Some(rank) = ranks.get(&edge.to) {
sum += *rank as f32;
count += 1;
}
} else if edge.to == *node_id
&& let Some(rank) = ranks.get(&edge.from)
{
sum += *rank as f32;
count += 1;
}
}
if count == 0 {
continue;
}
let avg_neighbor_rank = (sum / count as f32).round().max(0.0) as usize;
let target_rank = avg_neighbor_rank.max(min_hierarchy_rank + 1);
let current_rank = ranks.get(node_id).copied().unwrap_or(0);
if target_rank > current_rank {
pending_updates.push((node_id.clone(), target_rank));
}
}
for (node_id, rank) in pending_updates {
ranks.insert(node_id, rank);
}
}
}
let mut max_rank = 0usize;
for rank in ranks.values() {
max_rank = max_rank.max(*rank);
}
let mut rank_nodes: Vec<Vec<String>> = vec![Vec::new(); max_rank + 1];
for node_id in layout_node_ids {
let rank = *ranks.get(node_id).unwrap_or(&0);
if let Some(bucket) = rank_nodes.get_mut(rank) {
bucket.push(node_id.clone());
}
}
let use_label_dummies = !matches!(
graph.kind,
DiagramKind::Flowchart
| DiagramKind::Class
| DiagramKind::Er
| DiagramKind::Requirement
| DiagramKind::State
);
let gaps_needing_label_rank: Vec<usize> = if use_label_dummies {
let mut gap_set: HashSet<usize> = HashSet::new();
for (idx, edge) in layout_edges.iter().enumerate() {
if edge_labels[idx].is_none() {
continue;
}
let from_rank = ranks.get(&edge.from).copied().unwrap_or(0);
let to_rank = ranks.get(&edge.to).copied().unwrap_or(0);
let lo = from_rank.min(to_rank);
let hi = from_rank.max(to_rank);
if hi > lo {
let mid_gap = lo + (hi - lo - 1) / 2;
gap_set.insert(mid_gap);
}
}
let mut v: Vec<usize> = gap_set.into_iter().collect();
v.sort();
v
} else {
Vec::new()
};
let mut rank_shift: Vec<usize> = vec![0; max_rank + 2];
{
let mut cumulative = 0;
for r in 0..=max_rank {
rank_shift[r] = cumulative;
if gaps_needing_label_rank.contains(&r) {
cumulative += 1;
}
}
rank_shift[max_rank + 1] = cumulative;
}
let total_new_ranks = if gaps_needing_label_rank.is_empty() {
0
} else {
rank_shift[max_rank + 1]
};
if total_new_ranks > 0 {
let new_max_rank = max_rank + total_new_ranks;
let mut new_rank_nodes: Vec<Vec<String>> = vec![Vec::new(); new_max_rank + 1];
for (old_rank, bucket) in rank_nodes.iter().enumerate() {
let new_rank = old_rank + rank_shift[old_rank];
new_rank_nodes[new_rank] = bucket.clone();
}
rank_nodes = new_rank_nodes;
}
let mut label_dummy_ranks: HashSet<usize> = HashSet::new();
let mut order_map = graph.node_order.clone();
let mut dummy_counter = 0usize;
if use_label_dummies {
for (idx, edge) in layout_edges.iter().enumerate() {
let Some(label) = &edge_labels[idx] else {
continue;
};
let from_rank = ranks.get(&edge.from).copied().unwrap_or(0);
let to_rank = ranks.get(&edge.to).copied().unwrap_or(0);
let lo = from_rank.min(to_rank);
let hi = from_rank.max(to_rank);
if hi <= lo {
continue;
}
let mid_gap = lo + (hi - lo - 1) / 2;
let label_rank = mid_gap + rank_shift[mid_gap] + 1;
label_dummy_ranks.insert(label_rank);
let dummy_id = format!("__elabel_{}_{}_{dummy_counter}__", edge.from, edge.to);
dummy_counter += 1;
let order_idx = order_map.len();
order_map.insert(dummy_id.clone(), order_idx);
let label_main_cap = (theme.font_size * 8.0).max(config.node_spacing * 1.3);
let (raw_main, raw_cross) = if is_horizontal(graph.direction) {
(label.width, label.height)
} else {
(label.height, label.width)
};
let main_dim = if raw_main > 0.0 {
raw_main.min(label_main_cap)
} else {
raw_main
};
let cross_dim = raw_cross;
nodes.insert(
dummy_id.clone(),
NodeLayout {
id: dummy_id.clone(),
x: 0.0,
y: 0.0,
width: if is_horizontal(graph.direction) {
main_dim
} else {
cross_dim
},
height: if is_horizontal(graph.direction) {
cross_dim
} else {
main_dim
},
label: TextBlock {
lines: vec![],
width: 0.0,
height: 0.0,
},
shape: crate::mermaid_engine::ir::NodeShape::Rectangle,
style: crate::mermaid_engine::ir::NodeStyle::default(),
link: None,
anchor_subgraph: None,
hidden: true,
icon: None,
},
);
if let Some(&orig_idx) = original_edge_indices.get(idx)
&& orig_idx < label_dummy_ids.len()
{
label_dummy_ids[orig_idx] = Some(dummy_id.clone());
}
if let Some(bucket) = rank_nodes.get_mut(label_rank) {
bucket.push(dummy_id);
}
}
}
let mut label_dummy_at_rank: HashMap<usize, (usize, String)> = HashMap::new();
for (idx, edge) in layout_edges.iter().enumerate() {
if edge_labels[idx].is_none() {
continue;
}
let from_rank = ranks.get(&edge.from).copied().unwrap_or(0);
let to_rank = ranks.get(&edge.to).copied().unwrap_or(0);
let lo = from_rank.min(to_rank);
let hi = from_rank.max(to_rank);
if hi <= lo {
continue;
}
let mid_gap = lo + (hi - lo - 1) / 2;
let label_rank = mid_gap + rank_shift[mid_gap] + 1;
if let Some(&orig_idx) = original_edge_indices.get(idx)
&& let Some(Some(dummy_id)) = label_dummy_ids.get(orig_idx)
{
label_dummy_at_rank.insert(idx, (label_rank, dummy_id.clone()));
}
}
let shifted_ranks: HashMap<String, usize> = ranks
.iter()
.map(|(id, &r)| (id.clone(), r + rank_shift[r]))
.collect();
let ordering_edges = build_ordering_edges(
&layout_edges,
&shifted_ranks,
&mut rank_nodes,
&mut order_map,
&label_dummy_at_rank,
&mut dummy_counter,
);
for bucket in &mut rank_nodes {
bucket.sort_by_key(|id| order_map.get(id).copied().unwrap_or(usize::MAX));
}
order_rank_nodes(
&mut rank_nodes,
&ordering_edges,
&order_map,
config.flowchart.order_passes,
);
let mut main_cursor = 0.0;
for (rank_idx, bucket) in rank_nodes.iter().enumerate() {
let mut max_main: f32 = 0.0;
let is_label_rank = label_dummy_ranks.contains(&rank_idx);
for node_id in bucket {
if let Some(node_layout) = nodes.get_mut(node_id) {
if is_horizontal(graph.direction) {
node_layout.x = main_cursor;
max_main = max_main.max(node_layout.width);
} else {
node_layout.y = main_cursor;
max_main = max_main.max(node_layout.height);
}
}
}
if max_main > 0.0 {
let gap = if is_label_rank {
(theme.font_size * LABEL_RANK_FONT_SCALE).max(LABEL_RANK_MIN_GAP)
} else {
config.rank_spacing
};
main_cursor += max_main + gap;
}
}
let mut incoming: HashMap<String, Vec<String>> = HashMap::new();
let mut outgoing: HashMap<String, Vec<String>> = HashMap::new();
for edge in &ordering_edges {
incoming
.entry(edge.to.clone())
.or_default()
.push(edge.from.clone());
outgoing
.entry(edge.from.clone())
.or_default()
.push(edge.to.clone());
}
let mut cross_pos: HashMap<String, f32> = HashMap::new();
for bucket in &rank_nodes {
for (idx, node_id) in bucket.iter().enumerate() {
if let Some(node) = nodes.get(node_id) {
let center = if is_horizontal(graph.direction) {
node.y + node.height / 2.0
} else {
node.x + node.width / 2.0
};
cross_pos.insert(node_id.clone(), center + idx as f32 * 0.01);
}
}
}
let mut place_rank = |rank_idx: usize,
use_incoming: bool,
nodes: &mut BTreeMap<String, NodeLayout>| {
let bucket = &rank_nodes[rank_idx];
if bucket.is_empty() {
return;
}
let neighbors = if use_incoming { &incoming } else { &outgoing };
let mut entries: Vec<(String, f32, f32, usize)> = Vec::new();
for (idx, node_id) in bucket.iter().enumerate() {
let Some(node) = nodes.get(node_id) else {
continue;
};
let mut neighbor_centers: Vec<f32> = Vec::new();
if let Some(list) = neighbors.get(node_id) {
for neighbor_id in list {
if let Some(center) = cross_pos.get(neighbor_id) {
neighbor_centers.push(*center);
}
}
}
let mut desired = if neighbor_centers.is_empty() {
cross_pos.get(node_id).copied().unwrap_or(0.0)
} else {
neighbor_centers.sort_by(|a, b| a.partial_cmp(b).unwrap_or(Ordering::Equal));
let mid = neighbor_centers.len() / 2;
if neighbor_centers.len() % 2 == 1 {
neighbor_centers[mid]
} else {
(neighbor_centers[mid - 1] + neighbor_centers[mid]) * 0.5
}
};
if let Some(current) = cross_pos.get(node_id) {
if !neighbor_centers.is_empty() {
desired = desired * 0.85 + current * 0.15;
} else {
desired = *current;
}
}
let half = if is_horizontal(graph.direction) {
node.height / 2.0
} else {
node.width / 2.0
};
entries.push((node_id.clone(), desired, half, idx));
}
entries.sort_by(|a, b| {
a.1.partial_cmp(&b.1)
.unwrap_or(Ordering::Equal)
.then_with(|| a.3.cmp(&b.3))
});
let desired_mean =
entries.iter().map(|(_, d, _, _)| *d).sum::<f32>() / entries.len() as f32;
let mut assigned: Vec<(String, f32, f32)> = Vec::new();
let mut prev_center: Option<f32> = None;
let mut prev_half = 0.0;
for (node_id, desired, half, _idx) in entries {
let center = if let Some(prev) = prev_center {
let min_center = prev + prev_half + half + config.node_spacing;
if desired < min_center {
min_center
} else {
desired
}
} else {
desired
};
assigned.push((node_id, center, half));
prev_center = Some(center);
prev_half = half;
}
let actual_mean = assigned.iter().map(|(_, c, _)| *c).sum::<f32>() / assigned.len() as f32;
let delta = desired_mean - actual_mean;
for (node_id, center, _half) in assigned {
let center = center + delta;
if let Some(node) = nodes.get_mut(&node_id) {
if is_horizontal(graph.direction) {
node.y = center - node.height / 2.0;
} else {
node.x = center - node.width / 2.0;
}
}
cross_pos.insert(node_id, center);
}
};
for _ in 0..config.flowchart.order_passes.max(1) {
for rank_idx in 0..rank_nodes.len() {
place_rank(rank_idx, true, nodes);
}
for rank_idx in (0..rank_nodes.len()).rev() {
place_rank(rank_idx, false, nodes);
}
}
}
#[cfg(all(test, feature = "mermaid_engine_internal_tests"))]
mod tests {
use super::*;
fn make_node_layout(id: &str) -> NodeLayout {
NodeLayout {
id: id.to_string(),
x: 0.0,
y: 0.0,
width: 60.0,
height: 36.0,
label: TextBlock {
lines: vec![id.to_string()],
width: 20.0,
height: 14.0,
},
shape: crate::mermaid_engine::ir::NodeShape::Rectangle,
style: crate::mermaid_engine::ir::NodeStyle::default(),
link: None,
anchor_subgraph: None,
hidden: false,
icon: None,
}
}
fn make_graph_node(id: &str) -> crate::mermaid_engine::ir::Node {
crate::mermaid_engine::ir::Node {
id: id.to_string(),
label: id.to_string(),
shape: crate::mermaid_engine::ir::NodeShape::Rectangle,
value: None,
icon: None,
}
}
fn make_edge(from: &str, to: &str, label: Option<&str>) -> crate::mermaid_engine::ir::Edge {
crate::mermaid_engine::ir::Edge {
from: from.to_string(),
to: to.to_string(),
label: label.map(str::to_string),
start_label: None,
end_label: None,
directed: true,
arrow_start: false,
arrow_end: true,
arrow_start_kind: None,
arrow_end_kind: None,
start_decoration: None,
end_decoration: None,
style: crate::mermaid_engine::ir::EdgeStyle::Solid,
}
}
#[test]
fn non_flowchart_layouts_can_insert_label_dummy_nodes() {
let mut graph = Graph::new();
graph.kind = DiagramKind::Packet;
graph.direction = crate::mermaid_engine::ir::Direction::TopDown;
for (idx, id) in ["A", "B", "C"].iter().enumerate() {
graph.nodes.insert((*id).to_string(), make_graph_node(id));
graph.node_order.insert((*id).to_string(), idx);
}
let edges = vec![
make_edge("A", "B", None),
make_edge("B", "C", Some("label")),
];
let layout_node_ids = vec!["A".to_string(), "B".to_string(), "C".to_string()];
let layout_set: HashSet<String> = layout_node_ids.iter().cloned().collect();
let mut nodes = BTreeMap::new();
for id in &layout_node_ids {
nodes.insert(id.clone(), make_node_layout(id));
}
let pre_measured_labels = vec![
None,
Some(TextBlock {
lines: vec!["label".to_string()],
width: 44.0,
height: 14.0,
}),
];
let mut label_dummy_ids = vec![None; edges.len()];
assign_positions_manual(
&graph,
&layout_node_ids,
&layout_set,
&mut nodes,
&LayoutConfig::default(),
&edges,
&Theme::modern(),
&pre_measured_labels,
&mut label_dummy_ids,
);
let dummy_id = label_dummy_ids[1].as_ref().expect("label dummy id");
let dummy = nodes.get(dummy_id).expect("dummy node present");
assert!(dummy.hidden);
}
#[test]
fn build_ordering_edges_retains_non_forward_edges() {
let edges = vec![make_edge("A", "B", None), make_edge("B", "A", None)];
let shifted_ranks = HashMap::from([("A".to_string(), 0usize), ("B".to_string(), 1usize)]);
let mut rank_nodes = vec![vec!["A".to_string()], vec!["B".to_string()]];
let mut order_map = HashMap::from([("A".to_string(), 0usize), ("B".to_string(), 1usize)]);
let mut dummy_counter = 0usize;
let ordering_edges = build_ordering_edges(
&edges,
&shifted_ranks,
&mut rank_nodes,
&mut order_map,
&HashMap::new(),
&mut dummy_counter,
);
assert!(
ordering_edges
.iter()
.any(|edge| edge.from == "A" && edge.to == "B")
);
assert!(
ordering_edges
.iter()
.any(|edge| edge.from == "B" && edge.to == "A")
);
}
}