use std::collections::HashMap;
use super::{shapes, Glyph, Label, PlacedCluster, PlacedEdgeLabel, PlacedNode, Size};
use crate::preview::mermaid::flowchart::Direction;
use crate::preview::mermaid::layout::Point;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
pub enum Routing {
#[default]
Splines,
Orthogonal,
}
impl Routing {
pub fn parse(s: &str) -> Routing {
match s {
"konoma-orthogonal" => Routing::Orthogonal,
_ => Routing::Splines,
}
}
}
pub const PORT_INSET: f64 = super::svg::NODE_STROKE_WIDTH / 2.0 + 1.0;
pub const PORT_SPACING: f64 = 16.0;
pub const PORT_CLEARANCE: f64 = 8.0;
pub(super) const FAN_ELIGIBLE_MIN_BRANCHES: usize = 3;
const SELF_LOOP_PORT_OFFSET: f64 = 8.0;
const SELF_LOOP_OUTSET: f64 = 20.0;
pub(crate) const SELF_LOOP_LABEL_GAP: f64 = 4.0;
pub(crate) const BAR_PORT_PAD: f64 = 16.0;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
enum Side {
Top,
Bottom,
Left,
Right,
}
impl Side {
fn opposite(self) -> Side {
match self {
Side::Top => Side::Bottom,
Side::Bottom => Side::Top,
Side::Left => Side::Right,
Side::Right => Side::Left,
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Axis {
Flow,
Cross,
}
fn flow(direction: Direction, p: &Point) -> f64 {
match direction {
Direction::TopToBottom | Direction::BottomToTop => p.y,
Direction::LeftToRight | Direction::RightToLeft => p.x,
}
}
fn cross(direction: Direction, p: &Point) -> f64 {
match direction {
Direction::TopToBottom | Direction::BottomToTop => p.x,
Direction::LeftToRight | Direction::RightToLeft => p.y,
}
}
fn make(direction: Direction, flow_v: f64, cross_v: f64) -> Point {
match direction {
Direction::TopToBottom | Direction::BottomToTop => Point::new(cross_v, flow_v),
Direction::LeftToRight | Direction::RightToLeft => Point::new(flow_v, cross_v),
}
}
fn flow_face(direction: Direction, delta: f64) -> Side {
match direction {
Direction::TopToBottom | Direction::BottomToTop => {
if delta >= 0.0 {
Side::Bottom
} else {
Side::Top
}
}
Direction::LeftToRight | Direction::RightToLeft => {
if delta >= 0.0 {
Side::Right
} else {
Side::Left
}
}
}
}
fn flow_rank_delta(rank_a: Option<i32>, rank_b: Option<i32>, geo_delta: f64) -> f64 {
match (rank_a, rank_b) {
(Some(ra), Some(rb)) if ra != rb => (ra - rb) as f64,
_ => geo_delta,
}
}
fn cross_face(direction: Direction, delta: f64) -> Side {
match direction {
Direction::TopToBottom | Direction::BottomToTop => {
if delta >= 0.0 {
Side::Right
} else {
Side::Left
}
}
Direction::LeftToRight | Direction::RightToLeft => {
if delta >= 0.0 {
Side::Bottom
} else {
Side::Top
}
}
}
}
fn axis_of(direction: Direction, side: Side) -> Axis {
let top_bottom_is_flow = matches!(direction, Direction::TopToBottom | Direction::BottomToTop);
match (top_bottom_is_flow, side) {
(true, Side::Top | Side::Bottom) => Axis::Flow,
(true, Side::Left | Side::Right) => Axis::Cross,
(false, Side::Left | Side::Right) => Axis::Flow,
(false, Side::Top | Side::Bottom) => Axis::Cross,
}
}
fn dominant_face(direction: Direction, center: &Point, reference: &Point) -> Side {
let dflow = flow(direction, reference) - flow(direction, center);
let dcross = cross(direction, reference) - cross(direction, center);
if dflow.abs() >= dcross.abs() {
flow_face(direction, dflow)
} else {
cross_face(direction, dcross)
}
}
fn self_loop_canonical_face(direction: Direction) -> Side {
match direction {
Direction::LeftToRight | Direction::RightToLeft => Side::Top,
Direction::TopToBottom | Direction::BottomToTop => Side::Right,
}
}
fn face_center_coord(node: &PlacedNode, side: Side) -> f64 {
match side {
Side::Top | Side::Bottom => node.center.x,
Side::Left | Side::Right => node.center.y,
}
}
fn face_port(node: &PlacedNode, side: Side, inset: f64) -> Point {
port_at(node, side, face_center_coord(node, side), inset)
}
fn port_at(node: &PlacedNode, side: Side, coord: f64, inset: f64) -> Point {
let (l, t, r, b) = node.bounds();
match side {
Side::Top => Point::new(coord, t - inset),
Side::Bottom => Point::new(coord, b + inset),
Side::Left => Point::new(l - inset, coord),
Side::Right => Point::new(r + inset, coord),
}
}
const EPS: f64 = 1e-6;
fn bridge(direction: Direction, a: &Point, b: &Point, leave: Axis, enter: Axis) -> Vec<Point> {
match (leave, enter) {
(Axis::Flow, Axis::Cross) => {
let corner = make(direction, flow(direction, b), cross(direction, a));
vec![corner, b.clone()]
}
(Axis::Cross, Axis::Flow) => {
let corner = make(direction, flow(direction, a), cross(direction, b));
vec![corner, b.clone()]
}
(Axis::Flow, Axis::Flow) => {
if (cross(direction, a) - cross(direction, b)).abs() < EPS {
vec![b.clone()]
} else {
let mid = (flow(direction, a) + flow(direction, b)) / 2.0;
vec![
make(direction, mid, cross(direction, a)),
make(direction, mid, cross(direction, b)),
b.clone(),
]
}
}
(Axis::Cross, Axis::Cross) => {
if (flow(direction, a) - flow(direction, b)).abs() < EPS {
vec![b.clone()]
} else {
let mid = (cross(direction, a) + cross(direction, b)) / 2.0;
vec![
make(direction, flow(direction, a), mid),
make(direction, flow(direction, b), mid),
b.clone(),
]
}
}
}
}
#[derive(Debug, Clone, Copy)]
struct EdgeShape {
reverse: bool,
self_loop_fixed: bool,
aligned: bool,
staircase: bool,
fan_lane: bool,
rank_lane_bend: Option<f64>,
cross_lane_bend: Option<f64>,
aside: bool,
source_side: Side,
source_axis: Axis,
target_side: Side,
target_axis: Axis,
}
fn is_flow_flow_bend(shape: &EdgeShape) -> bool {
!shape.aligned && shape.source_axis == Axis::Flow && shape.target_axis == Axis::Flow
}
fn rides_the_perimeter(shape: &EdgeShape) -> bool {
shape.reverse || shape.aside
}
fn routes_last(shape: &EdgeShape, source: &PlacedNode, target: &PlacedNode) -> bool {
rides_the_perimeter(shape) && source.id != target.id
}
fn main_flow_polylines(
edges: &[EligibleEdge],
shapes: &[Option<EdgeShape>],
by_id: &HashMap<&str, &PlacedNode>,
points: &HashMap<String, Vec<Point>>,
) -> Vec<Vec<Point>> {
edges
.iter()
.zip(shapes)
.filter_map(|(e, s)| {
let shape = s.as_ref()?;
let (&source, &target) = (by_id.get(e.source)?, by_id.get(e.target)?);
if routes_last(shape, source, target) {
return None;
}
points.get(e.id).cloned()
})
.collect()
}
fn aside_route_stays_local(
source: &PlacedNode,
target: &PlacedNode,
nodes: &[PlacedNode],
frames: &[PlacedNode],
) -> bool {
let (sl, st, sr, sb) = source.bounds();
let (tl, tt, tr, tb) = target.bounds();
let (l, t, r, b) = (sl.min(tl), st.min(tt), sr.max(tr), sb.max(tb));
let clear = |(nl, nt, nr, nb): (f64, f64, f64, f64)| -> bool {
nl >= r - EPS || nr <= l + EPS || nt >= b - EPS || nb <= t + EPS
};
let holds = |(fl, ft, fr, fb): (f64, f64, f64, f64), n: &PlacedNode| -> bool {
n.center.x >= fl && n.center.x <= fr && n.center.y >= ft && n.center.y <= fb
};
nodes
.iter()
.all(|n| n.id == source.id || n.id == target.id || clear(n.bounds()))
&& frames.iter().all(|f| {
let bounds = f.bounds();
holds(bounds, source) || holds(bounds, target) || clear(bounds)
})
}
fn is_bar(node: &PlacedNode) -> bool {
matches!(node.shape, Glyph::Bar { .. })
}
pub(crate) const COLLISION_MARGIN: f64 = 4.0;
pub(crate) fn segment_crosses_node(a: &Point, b: &Point, node: &PlacedNode) -> bool {
segment_crosses_node_padded(a, b, node, COLLISION_MARGIN)
}
fn segment_crosses_node_padded(a: &Point, b: &Point, node: &PlacedNode, margin: f64) -> bool {
let (l, t, r, bo) = node.bounds();
let (l, t, r, bo) = (l - margin, t - margin, r + margin, bo + margin);
if (a.y - b.y).abs() < EPS {
let y = a.y;
let (x0, x1) = (a.x.min(b.x), a.x.max(b.x));
y >= t && y <= bo && x1 >= l && x0 <= r
} else if (a.x - b.x).abs() < EPS {
let x = a.x;
let (y0, y1) = (a.y.min(b.y), a.y.max(b.y));
x >= l && x <= r && y1 >= t && y0 <= bo
} else {
false
}
}
pub(crate) fn staircase_punctures_its_own_endpoint(
points: &[Point],
source: Option<&PlacedNode>,
target: Option<&PlacedNode>,
) -> bool {
points.windows(2).any(|w| {
source.is_some_and(|n| segment_crosses_node_padded(&w[0], &w[1], n, 0.0))
|| target.is_some_and(|n| segment_crosses_node_padded(&w[0], &w[1], n, 0.0))
})
}
fn shape_crosses_a_node(
direction: Direction,
source: &PlacedNode,
target: &PlacedNode,
shape: &EdgeShape,
nodes: &[PlacedNode],
) -> bool {
let source_port = face_port(source, shape.source_side, PORT_INSET);
let target_port = face_port(target, shape.target_side, PORT_INSET);
let mut pts = vec![source_port.clone()];
if let (Some(bend), Some(lane)) = (shape.rank_lane_bend, shape.cross_lane_bend) {
pts.extend(cross_lane_route(
direction,
lane,
bend,
&source_port,
&target_port,
));
} else if let Some(bend) = shape.rank_lane_bend {
pts.extend(bend_at(direction, bend, &source_port, &target_port));
} else {
pts.extend(bridge(
direction,
&source_port,
&target_port,
shape.source_axis,
shape.target_axis,
));
}
let source_is_real = nodes.iter().any(|n| n.id == source.id);
let target_is_real = nodes.iter().any(|n| n.id == target.id);
for w in pts.windows(2) {
for node in nodes {
if node.id == source.id || node.id == target.id {
continue;
}
if segment_crosses_node(&w[0], &w[1], node) {
return true;
}
}
if (source_is_real && segment_crosses_node_padded(&w[0], &w[1], source, 0.0))
|| (target_is_real && segment_crosses_node_padded(&w[0], &w[1], target, 0.0))
{
return true;
}
}
false
}
#[allow(clippy::too_many_arguments)]
fn classify(
direction: Direction,
source: &PlacedNode,
target: &PlacedNode,
raw: &[Point],
source_rank: Option<i32>,
target_rank: Option<i32>,
source_out_degree: usize,
target_in_degree: usize,
nodes: &[PlacedNode],
frames: &[PlacedNode],
source_is_cluster: bool,
fixed_self_loops: bool,
aside: bool,
main_flow: &[Vec<Point>],
) -> EdgeShape {
if fixed_self_loops && source.id == target.id {
let side = self_loop_canonical_face(direction);
return EdgeShape {
reverse: true,
self_loop_fixed: true,
aligned: false,
staircase: false,
fan_lane: false,
rank_lane_bend: None,
cross_lane_bend: None,
aside: false,
source_side: side,
source_axis: axis_of(direction, side),
target_side: side,
target_axis: axis_of(direction, side),
};
}
let is_reverse = matches!((source_rank, target_rank), (Some(sr), Some(tr)) if tr <= sr);
let nothing_between = is_reverse && source_is_cluster && {
let target_far = flow(direction, &target.center) + flow_extent(direction, target);
let source_near = flow(direction, &source.center) - flow_extent(direction, source);
target_far <= source_near + EPS
&& !nodes.iter().any(|n| {
if n.id == source.id || n.id == target.id {
return false;
}
let near = flow(direction, &n.center) - flow_extent(direction, n);
let far = flow(direction, &n.center) + flow_extent(direction, n);
far > target_far + EPS && near < source_near - EPS
})
};
if nothing_between {
} else if aside
&& source.id != target.id
&& !aside_route_stays_local(source, target, nodes, frames)
{
let ring = expand_bounds(
box_bounds(nodes, frames, [source, target]),
PERIMETER_MARGIN,
);
let (source_side, target_side) = perimeter_faces(source, target, ring, nodes, main_flow);
return EdgeShape {
reverse: is_reverse,
self_loop_fixed: false,
aligned: false,
staircase: false,
fan_lane: false,
rank_lane_bend: None,
cross_lane_bend: None,
aside: true,
source_side,
source_axis: axis_of(direction, source_side),
target_side,
target_axis: axis_of(direction, target_side),
};
} else if is_reverse {
let mut deduped = raw.to_vec();
super::edges::dedupe(&mut deduped);
let interior: Vec<Point> = if deduped.len() > 2 {
deduped[1..deduped.len() - 1].to_vec()
} else {
Vec::new()
};
let lane_face = |node: &PlacedNode, at_node: &Point, on_chain: &Point| -> Option<Side> {
let dcross = cross(direction, on_chain) - cross(direction, at_node);
let reach = cross_extent(direction, node);
(dcross.abs() > reach).then(|| cross_face(direction, dcross))
};
let ref_start = interior
.first()
.cloned()
.unwrap_or_else(|| target.center.clone());
let ref_end = interior
.last()
.cloned()
.unwrap_or_else(|| source.center.clone());
let source_side = interior
.first()
.zip(raw.first())
.and_then(|(on_chain, at_node)| lane_face(source, at_node, on_chain))
.unwrap_or_else(|| dominant_face(direction, &source.center, &ref_start));
let target_side = interior
.last()
.zip(raw.last())
.and_then(|(on_chain, at_node)| lane_face(target, at_node, on_chain))
.unwrap_or_else(|| dominant_face(direction, &target.center, &ref_end));
return EdgeShape {
reverse: true,
self_loop_fixed: false,
aligned: false,
staircase: false,
fan_lane: false,
rank_lane_bend: None,
cross_lane_bend: None,
aside: false,
source_side,
source_axis: axis_of(direction, source_side),
target_side,
target_axis: axis_of(direction, target_side),
};
}
let dcross = cross(direction, &target.center) - cross(direction, &source.center);
if dcross.abs() < 0.5 {
let delta = flow(direction, &target.center) - flow(direction, &source.center);
let source_side = flow_face(direction, delta);
let target_side = source_side.opposite();
let mut shape = EdgeShape {
reverse: false,
self_loop_fixed: false,
aligned: true,
staircase: false,
fan_lane: false,
rank_lane_bend: None,
cross_lane_bend: None,
aside: false,
source_side,
source_axis: Axis::Flow,
target_side,
target_axis: Axis::Flow,
};
if shape_crosses_a_node(direction, source, target, &shape, nodes) {
shape.staircase = true;
}
return shape;
}
let dflow = flow(direction, &target.center) - flow(direction, &source.center);
if dflow.abs() < 0.5 {
let source_side = cross_face(direction, dcross);
let target_side = source_side.opposite();
let mut shape = EdgeShape {
reverse: false,
self_loop_fixed: false,
aligned: true,
staircase: false,
fan_lane: false,
rank_lane_bend: None,
cross_lane_bend: None,
aside: false,
source_side,
source_axis: Axis::Cross,
target_side,
target_axis: Axis::Cross,
};
if shape_crosses_a_node(direction, source, target, &shape, nodes) {
shape.staircase = true;
}
return shape;
}
let branching = source_out_degree > 1 || target_in_degree <= 1;
let marker_anchored =
matches!(source.shape, Glyph::StateStart) || matches!(target.shape, Glyph::StateEnd);
let bar_anchored =
matches!(source.shape, Glyph::Bar { .. }) || matches!(target.shape, Glyph::Bar { .. });
let branching = branching && !matches!(source.shape, Glyph::StateStart) && !bar_anchored;
let (branch_source_side, branch_target_side) = (
cross_face(
direction,
cross(direction, &target.center) - cross(direction, &source.center),
),
flow_face(
direction,
flow_rank_delta(
source_rank,
target_rank,
flow(direction, &source.center) - flow(direction, &target.center),
),
),
);
let (merge_source_side, merge_target_side) = (
flow_face(
direction,
flow_rank_delta(
target_rank,
source_rank,
flow(direction, &target.center) - flow(direction, &source.center),
),
),
flow_face(
direction,
flow_rank_delta(
source_rank,
target_rank,
flow(direction, &source.center) - flow(direction, &target.center),
),
),
);
let fan_eligible = branching && source_out_degree > FAN_ELIGIBLE_MIN_BRANCHES;
let fan_shape = fan_eligible.then_some(EdgeShape {
reverse: false,
self_loop_fixed: false,
aligned: false,
staircase: false,
fan_lane: true,
rank_lane_bend: None,
cross_lane_bend: None,
aside: false,
source_side: merge_source_side,
source_axis: Axis::Flow,
target_side: branch_target_side,
target_axis: Axis::Flow,
});
let (source_side, target_side) = if branching {
(branch_source_side, branch_target_side)
} else {
(merge_source_side, merge_target_side)
};
let mut shape = EdgeShape {
reverse: false,
self_loop_fixed: false,
aligned: false,
staircase: false,
fan_lane: false,
rank_lane_bend: None,
cross_lane_bend: None,
aside: false,
source_side,
source_axis: axis_of(direction, source_side),
target_side,
target_axis: axis_of(direction, target_side),
};
if let Some(fan_shape) = fan_shape {
if !shape_crosses_a_node(direction, source, target, &fan_shape, nodes) {
return fan_shape;
}
}
if bar_anchored {
return shape;
}
if marker_anchored && shape_crosses_a_node(direction, source, target, &shape, nodes) {
shape.staircase = true;
return shape;
}
if shape_crosses_a_node(direction, source, target, &shape, nodes) {
let (alt_source_side, alt_target_side) = if branching {
(merge_source_side, merge_target_side)
} else {
(branch_source_side, branch_target_side)
};
let alt = EdgeShape {
reverse: false,
self_loop_fixed: false,
aligned: false,
staircase: false,
fan_lane: false,
rank_lane_bend: None,
cross_lane_bend: None,
aside: false,
source_side: alt_source_side,
source_axis: axis_of(direction, alt_source_side),
target_side: alt_target_side,
target_axis: axis_of(direction, alt_target_side),
};
if shape_crosses_a_node(direction, source, target, &alt, nodes) {
let flow_flow_base = if shape.source_axis == Axis::Flow {
shape
} else {
alt
};
let candidates = rank_lane_gap_bends(
direction,
source,
target,
flow_flow_base.target_side,
nodes,
!branching,
);
for &bend in &candidates {
let mut candidate = flow_flow_base;
candidate.rank_lane_bend = Some(bend);
if !shape_crosses_a_node(direction, source, target, &candidate, nodes) {
return candidate;
}
}
if branching {
let cross_base = if shape.source_axis == Axis::Cross {
shape
} else {
alt
};
for &bend in &candidates {
for lane in cross_lane_bends(
direction,
source,
target,
cross_base.source_side,
bend,
nodes,
frames,
) {
let mut candidate = cross_base;
candidate.rank_lane_bend = Some(bend);
candidate.cross_lane_bend = Some(lane);
if !shape_crosses_a_node(direction, source, target, &candidate, nodes) {
return candidate;
}
}
}
}
if !branching {
if let Some(&bend) = candidates.first() {
let mut candidate = flow_flow_base;
candidate.rank_lane_bend = Some(bend);
return candidate;
}
}
shape = alt;
shape.staircase = true;
} else {
shape = alt;
}
}
shape
}
fn retreat_fixed_self_loops(
direction: Direction,
edges: &[EligibleEdge],
shapes: &mut [Option<EdgeShape>],
) {
let mut occupied: std::collections::HashSet<(String, Side)> = std::collections::HashSet::new();
for (edge, shape) in edges.iter().zip(shapes.iter()) {
let Some(shape) = shape else { continue };
if shape.self_loop_fixed {
continue;
}
occupied.insert((edge.source.to_string(), shape.source_side));
occupied.insert((edge.target.to_string(), shape.target_side));
}
for (edge, shape) in edges.iter().zip(shapes.iter_mut()) {
let Some(shape) = shape else { continue };
if !shape.self_loop_fixed {
continue;
}
if occupied.contains(&(edge.source.to_string(), shape.source_side)) {
let flipped = shape.source_side.opposite();
shape.source_side = flipped;
shape.target_side = flipped;
shape.source_axis = axis_of(direction, flipped);
shape.target_axis = axis_of(direction, flipped);
}
}
}
#[allow(clippy::too_many_arguments)]
fn route_with_ports(
direction: Direction,
shape: &EdgeShape,
source: &PlacedNode,
target: &PlacedNode,
source_coord: f64,
target_coord: f64,
raw: &[Point],
ring: (f64, f64, f64, f64),
nodes: &[PlacedNode],
fan_step: Option<f64>,
) -> Vec<Point> {
if shape.self_loop_fixed {
return route_state_self_loop(source, shape.source_side);
}
let source_port = port_at(source, shape.source_side, source_coord, PORT_INSET);
let target_port = port_at(target, shape.target_side, target_coord, PORT_INSET);
let mut points = if shape.staircase || (shape.reverse && source.id == target.id) {
let staircase = route_staircase_with_ports(
direction,
shape,
source_port.clone(),
target_port.clone(),
raw,
);
let source_is_real = nodes.iter().any(|n| n.id == source.id);
let target_is_real = nodes.iter().any(|n| n.id == target.id);
let staircase = if shape.staircase
&& staircase_punctures_its_own_endpoint(
&staircase,
source_is_real.then_some(source),
target_is_real.then_some(target),
) {
let mut resynthesised = vec![source_port.clone()];
resynthesised.extend(bridge(
direction,
&source_port,
&target_port,
shape.source_axis,
shape.target_axis,
));
resynthesised
} else {
staircase
};
clear_local_route(staircase, nodes, (source.id.as_str(), target.id.as_str()))
} else if rides_the_perimeter(shape) {
let ids = (source.id.as_str(), target.id.as_str());
let blocked = |a: &Point, b: &Point| segment_crosses_any_node(a, b, nodes, ids);
let routed = route_perimeter(
shape.source_side,
shape.target_side,
source_port,
target_port,
ring,
&blocked,
);
clear_self_puncture(routed, source, target)
} else if shape.fan_lane {
route_fan_lane(
direction,
shape,
source,
&source_port,
&target_port,
fan_step,
)
} else if let Some(bend) = shape.rank_lane_bend {
let mut out = vec![source_port.clone()];
match shape.cross_lane_bend {
Some(lane) => out.extend(cross_lane_route(
direction,
lane,
bend,
&source_port,
&target_port,
)),
None => out.extend(bend_at(direction, bend, &source_port, &target_port)),
}
clear_local_route(out, nodes, (source.id.as_str(), target.id.as_str()))
} else {
let mut out = vec![source_port.clone()];
out.extend(bridge(
direction,
&source_port,
&target_port,
shape.source_axis,
shape.target_axis,
));
if matches!(source.shape, Glyph::Bar { .. }) || matches!(target.shape, Glyph::Bar { .. }) {
out = clear_local_route(out, nodes, (source.id.as_str(), target.id.as_str()));
}
out
};
super::edges::dedupe(&mut points);
if points.len() < 2 {
points = vec![source.center.clone(), target.center.clone()];
}
points
}
fn route_state_self_loop(node: &PlacedNode, side: Side) -> Vec<Point> {
let centre = face_center_coord(node, side);
let (out_coord, in_coord) = (
centre - SELF_LOOP_PORT_OFFSET,
centre + SELF_LOOP_PORT_OFFSET,
);
let out_port = port_at(node, side, out_coord, PORT_INSET);
let in_port = port_at(node, side, in_coord, PORT_INSET);
let out_corner = port_at(node, side, out_coord, SELF_LOOP_OUTSET);
let in_corner = port_at(node, side, in_coord, SELF_LOOP_OUTSET);
vec![out_port, out_corner, in_corner, in_port]
}
fn outward_sign(side: Side) -> f64 {
match side {
Side::Right | Side::Bottom => 1.0,
Side::Left | Side::Top => -1.0,
}
}
fn flow_extent(direction: Direction, node: &PlacedNode) -> f64 {
match direction {
Direction::TopToBottom | Direction::BottomToTop => node.size.h / 2.0,
Direction::LeftToRight | Direction::RightToLeft => node.size.w / 2.0,
}
}
fn bend_at(direction: Direction, bend_flow: f64, a: &Point, b: &Point) -> Vec<Point> {
vec![
make(direction, bend_flow, cross(direction, a)),
make(direction, bend_flow, cross(direction, b)),
b.clone(),
]
}
fn cross_lane_route(
direction: Direction,
lane: f64,
bend_flow: f64,
a: &Point,
b: &Point,
) -> Vec<Point> {
let hop = make(direction, flow(direction, a), lane);
let mut out = vec![hop.clone()];
out.extend(bend_at(direction, bend_flow, &hop, b));
out
}
fn cross_lane_bends(
direction: Direction,
source: &PlacedNode,
target: &PlacedNode,
source_side: Side,
bend_flow: f64,
nodes: &[PlacedNode],
frames: &[PlacedNode],
) -> Vec<f64> {
let sign = outward_sign(source_side);
let port_cross = cross(direction, &face_port(source, source_side, PORT_INSET));
let target_cross = cross(direction, &target.center);
let source_flow = flow(direction, &source.center);
let (run_lo, run_hi) = (source_flow.min(bend_flow), source_flow.max(bend_flow));
let holds = |b: &PlacedNode, p: &Point| {
let (x0, y0, x1, y1) = b.bounds();
p.x >= x0 - EPS && p.x <= x1 + EPS && p.y >= y0 - EPS && p.y <= y1 + EPS
};
let mut spans: Vec<(f64, f64)> = Vec::new();
let mut content: Option<(f64, f64)> = None;
for (b, is_frame) in nodes
.iter()
.map(|n| (n, false))
.chain(frames.iter().map(|f| (f, true)))
{
let lo_cross = cross(direction, &b.center) - cross_extent(direction, b);
let hi_cross = cross(direction, &b.center) + cross_extent(direction, b);
content = Some(match content {
Some((lo, hi)) => (lo.min(lo_cross), hi.max(hi_cross)),
None => (lo_cross, hi_cross),
});
if b.id == source.id || b.id == target.id {
continue;
}
if is_frame && (holds(b, &source.center) || holds(b, &target.center)) {
continue;
}
let lo_flow = flow(direction, &b.center) - flow_extent(direction, b);
let hi_flow = flow(direction, &b.center) + flow_extent(direction, b);
if hi_flow < run_lo - COLLISION_MARGIN || lo_flow > run_hi + COLLISION_MARGIN {
continue;
}
spans.push((lo_cross, hi_cross));
}
spans.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(std::cmp::Ordering::Equal));
let mut merged: Vec<(f64, f64)> = Vec::with_capacity(spans.len());
for (lo, hi) in spans {
match merged.last_mut() {
Some(last) if lo <= last.1 + EPS => last.1 = last.1.max(hi),
_ => merged.push((lo, hi)),
}
}
let outward = |lane: f64| sign * (lane - port_cross) > EPS;
let mut lanes: Vec<f64> = merged
.windows(2)
.filter(|w| w[1].0 - w[0].1 >= 2.0 * PORT_CLEARANCE)
.map(|w| (w[0].1 + w[1].0) / 2.0)
.filter(|&lane| outward(lane))
.collect();
lanes.sort_by(|a, b| {
(a - target_cross)
.abs()
.partial_cmp(&(b - target_cross).abs())
.unwrap_or(std::cmp::Ordering::Equal)
});
if let (Some((content_lo, content_hi)), Some(first), Some(last)) =
(content, merged.first(), merged.last())
{
let (wall, room) = if sign < 0.0 {
(first.0, first.0 - content_lo)
} else {
(last.1, content_hi - last.1)
};
let lane = wall + sign * PORT_SPACING;
if room >= 2.0 * PORT_SPACING && outward(lane) {
lanes.push(lane);
}
}
lanes.truncate(RANK_LANE_MAX_CANDIDATES);
lanes
}
const RANK_LANE_MAX_CANDIDATES: usize = 6;
fn rank_lane_gap_bends(
direction: Direction,
source: &PlacedNode,
target: &PlacedNode,
target_side: Side,
nodes: &[PlacedNode],
extended: bool,
) -> Vec<f64> {
let sign = outward_sign(target_side);
let entry_boundary = flow(direction, &target.center) + sign * flow_extent(direction, target);
let dist = |p: f64| sign * (p - entry_boundary);
let at_dist = |d: f64| entry_boundary + sign * d;
let source_facing = flow(direction, &source.center) - sign * flow_extent(direction, source);
let max_dist = if extended {
dist(source_facing)
} else {
dist(source_facing) / 2.0
};
let mut walls: Vec<(f64, f64)> = nodes
.iter()
.filter(|n| n.id != target.id && n.id != source.id)
.filter_map(|n| {
let near = flow(direction, &n.center) - sign * flow_extent(direction, n);
let far = flow(direction, &n.center) + sign * flow_extent(direction, n);
let d = dist(near);
(d > EPS && d <= max_dist).then_some((near, far))
})
.collect();
walls.sort_by(|a, b| {
dist(a.0)
.partial_cmp(&dist(b.0))
.unwrap_or(std::cmp::Ordering::Equal)
});
let mut cursor_dist = 0.0; let mut out = Vec::new();
for &(near, far) in walls.iter().take(RANK_LANE_MAX_CANDIDATES) {
let near_dist = dist(near);
let gap_width = near_dist - cursor_dist;
if gap_width > EPS {
let offset = if gap_width <= 2.0 * PORT_CLEARANCE {
gap_width / 2.0
} else {
(gap_width * 0.4).clamp(PORT_CLEARANCE, gap_width - PORT_CLEARANCE)
};
out.push(at_dist(cursor_dist + offset));
}
cursor_dist = cursor_dist.max(dist(far));
}
if extended && out.len() < RANK_LANE_MAX_CANDIDATES {
let gap_width = max_dist - cursor_dist;
if gap_width > EPS {
let offset = if gap_width <= 2.0 * PORT_CLEARANCE {
gap_width / 2.0
} else {
(gap_width * 0.4).clamp(PORT_CLEARANCE, gap_width - PORT_CLEARANCE)
};
out.push(at_dist(cursor_dist + offset));
}
}
out
}
fn nest_merge_target_hops(
direction: Direction,
edges: &[EligibleEdge],
by_id: &HashMap<&str, &PlacedNode>,
shapes: &mut [Option<EdgeShape>],
eviction: &Eviction,
) {
let is_merge_hop_candidate = |i: usize| -> bool {
edges[i].target_in_degree > 1
&& shapes[i].as_ref().is_some_and(|s| {
!s.aligned
&& !rides_the_perimeter(s)
&& !s.staircase
&& !s.fan_lane
&& s.source_axis == Axis::Flow
&& s.target_axis == Axis::Flow
})
};
let mut groups: HashMap<&str, Vec<usize>> = HashMap::new();
for (i, edge) in edges.iter().enumerate() {
if is_merge_hop_candidate(i) {
groups.entry(edge.target).or_default().push(i);
}
}
struct Candidate {
idx: usize,
orig_dist: f64,
max_reach: f64,
span: f64,
source_port: Point,
target_port: Point,
src_y: f64,
tgt_y: f64,
}
for idxs in groups.into_values() {
if idxs.len() < 2 {
continue;
}
let Some(target_side) = shapes[idxs[0]].as_ref().map(|s| s.target_side) else {
continue;
};
let Some(&target) = by_id.get(edges[idxs[0]].target) else {
continue;
};
let sign = outward_sign(target_side);
let entry_boundary =
flow(direction, &target.center) + sign * flow_extent(direction, target);
let dist = |p: f64| sign * (p - entry_boundary);
let mut candidates: Vec<Candidate> = idxs
.iter()
.filter_map(|&i| {
let shape = shapes[i].as_ref()?;
let &source = by_id.get(edges[i].source)?;
let src_y = eviction
.source_coord
.get(edges[i].id)
.copied()
.unwrap_or_else(|| face_center_coord(source, shape.source_side));
let tgt_y = eviction
.target_coord
.get(edges[i].id)
.copied()
.unwrap_or_else(|| face_center_coord(target, target_side));
let source_port = port_at(source, shape.source_side, src_y, PORT_INSET);
let target_port = port_at(target, target_side, tgt_y, PORT_INSET);
let bend = shape.rank_lane_bend.unwrap_or_else(|| {
(flow(direction, &source_port) + flow(direction, &target_port)) / 2.0
});
let source_facing =
flow(direction, &source.center) - sign * flow_extent(direction, source);
Some(Candidate {
idx: i,
orig_dist: dist(bend),
max_reach: dist(source_facing),
span: (cross(direction, &source_port) - cross(direction, &target_port)).abs(),
source_port,
target_port,
src_y,
tgt_y,
})
})
.collect();
if candidates.len() < 2 {
continue;
}
candidates.sort_by(|a, b| {
a.max_reach
.partial_cmp(&b.max_reach)
.unwrap_or(std::cmp::Ordering::Equal)
.then_with(|| {
b.span
.partial_cmp(&a.span)
.unwrap_or(std::cmp::Ordering::Equal)
})
});
let mut placed: Vec<[Point; 4]> = Vec::with_capacity(candidates.len());
let mut new_hops: Vec<(usize, f64)> = Vec::with_capacity(candidates.len());
for c in &candidates {
let mut d = c.orig_dist.max(0.0);
let build = |d: f64| -> [Point; 4] {
let hop = entry_boundary + sign * d;
[
c.source_port.clone(),
make(direction, hop, c.src_y),
make(direction, hop, c.tgt_y),
c.target_port.clone(),
]
};
let mut route = build(d);
let mut guard = 0;
while guard < RANK_LANE_MAX_CANDIDATES
&& d + PORT_CLEARANCE <= c.max_reach
&& placed.iter().any(|p| {
polylines_cross(&route, p)
|| hop_legs_crowd(direction, &route, p, PORT_CLEARANCE)
})
{
d += PORT_CLEARANCE;
route = build(d);
guard += 1;
}
new_hops.push((c.idx, entry_boundary + sign * d));
placed.push(route);
}
for (idx, hop) in new_hops {
if let Some(shape) = shapes[idx].as_mut() {
shape.rank_lane_bend = Some(hop);
}
}
}
}
fn hop_legs_crowd(direction: Direction, a: &[Point; 4], b: &[Point; 4], min_gap: f64) -> bool {
if (flow(direction, &a[1]) - flow(direction, &b[1])).abs() >= min_gap - EPS {
return false;
}
let span = |r: &[Point; 4]| {
let (p, q) = (cross(direction, &r[1]), cross(direction, &r[2]));
(p.min(q), p.max(q))
};
let (a_lo, a_hi) = span(a);
let (b_lo, b_hi) = span(b);
a_lo.max(b_lo) < a_hi.min(b_hi) - EPS
}
pub(crate) fn polylines_cross(a: &[Point], b: &[Point]) -> bool {
a.windows(2).any(|wa| {
b.windows(2).any(|wb| {
segment_crossing(wa, wb).is_some()
|| segments_overlap_collinearly(&wa[0], &wa[1], &wb[0], &wb[1])
})
})
}
fn segments_overlap_collinearly(a1: &Point, a2: &Point, b1: &Point, b2: &Point) -> bool {
let a_vertical = (a1.x - a2.x).abs() < EPS;
let b_vertical = (b1.x - b2.x).abs() < EPS;
if a_vertical != b_vertical {
return false; }
if a_vertical {
if (a1.x - b1.x).abs() >= EPS {
return false;
}
let (a_lo, a_hi) = (a1.y.min(a2.y), a1.y.max(a2.y));
let (b_lo, b_hi) = (b1.y.min(b2.y), b1.y.max(b2.y));
a_lo < b_hi - EPS && b_lo < a_hi - EPS
} else {
if (a1.y - b1.y).abs() >= EPS {
return false;
}
let (a_lo, a_hi) = (a1.x.min(a2.x), a1.x.max(a2.x));
let (b_lo, b_hi) = (b1.x.min(b2.x), b1.x.max(b2.x));
a_lo < b_hi - EPS && b_lo < a_hi - EPS
}
}
fn route_fan_lane(
direction: Direction,
shape: &EdgeShape,
source: &PlacedNode,
source_port: &Point,
target_port: &Point,
step_hint: Option<f64>,
) -> Vec<Point> {
let step = step_hint.unwrap_or_else(|| {
let center = face_center_coord(source, shape.source_side);
let offset = cross(direction, source_port) - center;
let k = (offset.abs() / PORT_SPACING).round().max(1.0);
PORT_CLEARANCE * k
});
let bend_flow = flow(direction, source_port) + outward_sign(shape.source_side) * step;
let (lo, hi) = (
flow(direction, source_port).min(flow(direction, target_port)),
flow(direction, source_port).max(flow(direction, target_port)),
);
if bend_flow <= lo || bend_flow >= hi {
let mut out = vec![source_port.clone()];
out.extend(bridge(
direction,
source_port,
target_port,
shape.source_axis,
shape.target_axis,
));
return out;
}
vec![
source_port.clone(),
make(direction, bend_flow, cross(direction, source_port)),
make(direction, bend_flow, cross(direction, target_port)),
target_port.clone(),
]
}
fn route_staircase_with_ports(
direction: Direction,
shape: &EdgeShape,
source_port: Point,
target_port: Point,
raw: &[Point],
) -> Vec<Point> {
let mut deduped = raw.to_vec();
super::edges::dedupe(&mut deduped);
let interior: Vec<Point> = if deduped.len() > 2 {
deduped[1..deduped.len() - 1].to_vec()
} else {
Vec::new()
};
let mut out = vec![source_port.clone()];
let mut prev = source_port;
let mut prev_axis = shape.source_axis;
for w in &interior {
out.extend(bridge(direction, &prev, w, prev_axis, Axis::Flow));
prev = w.clone();
prev_axis = Axis::Flow;
}
out.extend(bridge(
direction,
&prev,
&target_port,
prev_axis,
shape.target_axis,
));
out
}
fn clear_local_route(
mut points: Vec<Point>,
nodes: &[PlacedNode],
ids: (&str, &str),
) -> Vec<Point> {
const MAX_PASSES: usize = 8;
for _ in 0..MAX_PASSES {
let mut hit: Option<(usize, usize)> = None; 'search: for (i, w) in points.windows(2).enumerate() {
let (a, b) = (&w[0], &w[1]);
let horizontal = (a.y - b.y).abs() < EPS;
let vertical = (a.x - b.x).abs() < EPS;
if !horizontal && !vertical {
continue; }
for (ni, n) in nodes.iter().enumerate() {
if n.id == ids.0 || n.id == ids.1 {
continue;
}
if segment_crosses_node(a, b, n) {
hit = Some((i, ni));
break 'search;
}
}
}
let Some((i, ni)) = hit else {
break;
};
points = local_detour(points, i, &nodes[ni], nodes, ids);
points = remove_spikes(points);
}
points
}
fn remove_spikes(mut points: Vec<Point>) -> Vec<Point> {
loop {
let mut removed = false;
let mut k = 0;
while k + 2 < points.len() {
let last = points.len() - 1;
if k + 2 != last
&& (points[k].x - points[k + 2].x).abs() < EPS
&& (points[k].y - points[k + 2].y).abs() < EPS
{
points.remove(k + 2);
points.remove(k + 1);
removed = true;
} else {
k += 1;
}
}
if !removed {
break;
}
}
points
}
fn local_detour(
points: Vec<Point>,
i: usize,
node: &PlacedNode,
nodes: &[PlacedNode],
ids: (&str, &str),
) -> Vec<Point> {
let (a, b) = (&points[i], &points[i + 1]);
let horizontal = (a.y - b.y).abs() < EPS;
let old_c = if horizontal { a.y } else { a.x };
let coord_of = |p: &Point| if horizontal { p.y } else { p.x };
let moving_of = |p: &Point| if horizontal { p.x } else { p.y };
let at = |constant: f64, moving: f64| {
if horizontal {
Point::new(moving, constant)
} else {
Point::new(constant, moving)
}
};
let constant_range = |n: &PlacedNode| -> (f64, f64) {
let (l, t, r, bo) = n.bounds();
if horizontal {
(t - COLLISION_MARGIN - 1.0, bo + COLLISION_MARGIN + 1.0)
} else {
(l - COLLISION_MARGIN - 1.0, r + COLLISION_MARGIN + 1.0)
}
};
let moving_range = |n: &PlacedNode| -> (f64, f64) {
let (l, t, r, bo) = n.bounds();
if horizontal {
(l - COLLISION_MARGIN - 1.0, r + COLLISION_MARGIN + 1.0)
} else {
(t - COLLISION_MARGIN - 1.0, bo + COLLISION_MARGIN + 1.0)
}
};
let mut run_start = i;
while run_start > 0 && (coord_of(&points[run_start - 1]) - old_c).abs() < EPS {
run_start -= 1;
}
let mut run_end = i + 1;
while run_end + 1 < points.len() && (coord_of(&points[run_end + 1]) - old_c).abs() < EPS {
run_end += 1;
}
let (m_start, m_end) = (moving_of(&points[run_start]), moving_of(&points[run_end]));
let inc = m_end >= m_start;
let (run_lo, run_hi) = (m_start.min(m_end), m_start.max(m_end));
let relevant: Vec<&PlacedNode> = nodes
.iter()
.filter(|n| n.id != ids.0 && n.id != ids.1)
.filter(|n| {
let (mlo, mhi) = moving_range(n);
mlo <= run_hi && mhi >= run_lo
})
.collect();
let (mut c_lo, mut c_hi) = constant_range(node);
loop {
let mut grew = false;
for n in &relevant {
let (nc_lo, nc_hi) = constant_range(n);
if nc_lo <= c_hi && nc_hi >= c_lo && (nc_lo < c_lo || nc_hi > c_hi) {
c_lo = c_lo.min(nc_lo);
c_hi = c_hi.max(nc_hi);
grew = true;
}
}
if !grew {
break;
}
}
let new_c = if old_c <= (c_lo + c_hi) / 2.0 {
c_lo
} else {
c_hi
};
let (mut m_lo, mut m_hi) = (f64::INFINITY, f64::NEG_INFINITY);
for n in &relevant {
let (clo, chi) = constant_range(n);
if clo <= old_c && chi >= old_c {
let (mlo, mhi) = moving_range(n);
m_lo = m_lo.min(mlo.max(run_lo));
m_hi = m_hi.max(mhi.min(run_hi));
}
}
if m_lo > m_hi {
return points;
}
let (entry, exit) = if inc { (m_lo, m_hi) } else { (m_hi, m_lo) };
let can_move_start = run_start != 0 && (moving_of(&points[run_start]) - entry).abs() < EPS;
let can_move_end =
run_end != points.len() - 1 && (moving_of(&points[run_end]) - exit).abs() < EPS;
let mut out = Vec::with_capacity(points.len() + 4);
out.extend_from_slice(&points[..run_start]);
if can_move_start {
out.push(at(new_c, entry));
} else {
out.push(points[run_start].clone());
out.push(at(old_c, entry));
out.push(at(new_c, entry));
}
out.push(at(new_c, exit));
if can_move_end {
} else {
out.push(at(old_c, exit));
out.push(points[run_end].clone());
}
out.extend_from_slice(&points[run_end + 1..]);
out
}
fn clear_self_puncture(
mut points: Vec<Point>,
source: &PlacedNode,
target: &PlacedNode,
) -> Vec<Point> {
const MAX_PASSES: usize = 4;
for _ in 0..MAX_PASSES {
let mut fix: Option<(f64, f64, bool)> = None; 'search: for w in points.windows(2) {
let (a, b) = (&w[0], &w[1]);
let horizontal = (a.y - b.y).abs() < EPS;
let vertical = (a.x - b.x).abs() < EPS;
if !horizontal && !vertical {
continue;
}
for n in [source, target] {
if segment_crosses_node_padded(a, b, n, 0.0) {
let (l, t, r, bo) = n.bounds();
fix = Some(if horizontal {
let y = a.y;
let new_y = if y <= (t + bo) / 2.0 {
t - COLLISION_MARGIN - 1.0
} else {
bo + COLLISION_MARGIN + 1.0
};
(y, new_y, true)
} else {
let x = a.x;
let new_x = if x <= (l + r) / 2.0 {
l - COLLISION_MARGIN - 1.0
} else {
r + COLLISION_MARGIN + 1.0
};
(x, new_x, false)
});
break 'search;
}
}
}
let Some((old_c, new_c, horizontal)) = fix else {
break;
};
for p in &mut points {
if horizontal && (p.y - old_c).abs() < EPS {
p.y = new_c;
} else if !horizontal && (p.x - old_c).abs() < EPS {
p.x = new_c;
}
}
}
points
}
pub const PERIMETER_MARGIN: f64 = 16.0;
pub const PERIMETER_LANE_SPACING: f64 = 8.0;
fn union_bounds(rects: impl Iterator<Item = (f64, f64, f64, f64)>) -> (f64, f64, f64, f64) {
let mut l = f64::INFINITY;
let mut t = f64::INFINITY;
let mut r = f64::NEG_INFINITY;
let mut b = f64::NEG_INFINITY;
for (rl, rt, rr, rb) in rects {
l = l.min(rl);
t = t.min(rt);
r = r.max(rr);
b = b.max(rb);
}
if !l.is_finite() {
return (0.0, 0.0, 0.0, 0.0);
}
(l, t, r, b)
}
fn box_bounds(
nodes: &[PlacedNode],
frames: &[PlacedNode],
extra: [&PlacedNode; 2],
) -> (f64, f64, f64, f64) {
union_bounds(nodes.iter().chain(frames).chain(extra).map(|n| n.bounds()))
}
fn content_bounds(nodes: &[PlacedNode], clusters: &[PlacedCluster]) -> (f64, f64, f64, f64) {
union_bounds(
nodes
.iter()
.map(|n| n.bounds())
.chain(clusters.iter().map(|c| c.bounds())),
)
}
fn expand_bounds(bounds: (f64, f64, f64, f64), by: f64) -> (f64, f64, f64, f64) {
(bounds.0 - by, bounds.1 - by, bounds.2 + by, bounds.3 + by)
}
fn ring_touch(side: Side, port: &Point, ring: (f64, f64, f64, f64)) -> Point {
let (l, t, r, b) = ring;
match side {
Side::Top => Point::new(port.x, t),
Side::Bottom => Point::new(port.x, b),
Side::Left => Point::new(l, port.y),
Side::Right => Point::new(r, port.y),
}
}
fn segment_crosses_any_node(
a: &Point,
b: &Point,
nodes: &[PlacedNode],
exclude: (&str, &str),
) -> bool {
nodes
.iter()
.any(|n| n.id != exclude.0 && n.id != exclude.1 && segment_crosses_node(a, b, n))
}
fn safe_ring_exit(
side: Side,
port: &Point,
ring: (f64, f64, f64, f64),
blocked: &dyn Fn(&Point, &Point) -> bool,
) -> Vec<Point> {
let (l, t, r, b) = ring;
let direct = ring_touch(side, port, ring);
let hop = match side {
Side::Top => Point::new(port.x, port.y - PORT_CLEARANCE),
Side::Bottom => Point::new(port.x, port.y + PORT_CLEARANCE),
Side::Left => Point::new(port.x - PORT_CLEARANCE, port.y),
Side::Right => Point::new(port.x + PORT_CLEARANCE, port.y),
};
let l_shape = |corner: f64| -> Vec<Point> {
match side {
Side::Top | Side::Bottom => vec![hop.clone(), Point::new(corner, hop.y)],
Side::Left | Side::Right => vec![hop.clone(), Point::new(hop.x, corner)],
}
};
let (near, far) = match side {
Side::Top | Side::Bottom => {
if (port.x - l) <= (r - port.x) {
(l, r)
} else {
(r, l)
}
}
Side::Left | Side::Right => {
if (port.y - t) <= (b - port.y) {
(t, b)
} else {
(b, t)
}
}
};
let candidates: [Vec<Point>; 3] = [vec![direct.clone()], l_shape(near), l_shape(far)];
for cand in &candidates {
let mut prev = port.clone();
let mut clear = true;
for p in cand {
if blocked(&prev, p) {
clear = false;
break;
}
prev = p.clone();
}
if clear {
return cand.clone();
}
}
vec![direct]
}
fn ring_perimeter_dist(ring: (f64, f64, f64, f64), p: &Point) -> f64 {
let (l, t, r, b) = ring;
let w = r - l;
let h = b - t;
let d_top = (p.y - t).abs();
let d_bottom = (p.y - b).abs();
let d_left = (p.x - l).abs();
let d_right = (p.x - r).abs();
let m = d_top.min(d_bottom).min(d_left).min(d_right);
if m == d_top {
(p.x - l).clamp(0.0, w)
} else if m == d_right {
w + (p.y - t).clamp(0.0, h)
} else if m == d_bottom {
w + h + (r - p.x).clamp(0.0, w)
} else {
w + h + w + (b - p.y).clamp(0.0, h)
}
}
fn ring_corners(ring: (f64, f64, f64, f64)) -> [(f64, Point); 4] {
let (l, t, r, b) = ring;
let w = r - l;
let h = b - t;
[
(0.0, Point::new(l, t)),
(w, Point::new(r, t)),
(w + h, Point::new(r, b)),
(2.0 * w + h, Point::new(l, b)),
]
}
fn corners_between_clockwise(ring: (f64, f64, f64, f64), from: f64, to: f64) -> Vec<Point> {
let w = ring.2 - ring.0;
let h = ring.3 - ring.1;
let perim = 2.0 * (w + h);
if perim <= 0.0 {
return Vec::new();
}
let span = (to - from).rem_euclid(perim);
let mut out: Vec<(f64, Point)> = ring_corners(ring)
.into_iter()
.filter_map(|(dist, p)| {
let rel = (dist - from).rem_euclid(perim);
(rel > EPS && rel < span - EPS).then_some((rel, p))
})
.collect();
out.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(std::cmp::Ordering::Equal));
out.into_iter().map(|(_, p)| p).collect()
}
fn ring_path(ring: (f64, f64, f64, f64), a: &Point, b: &Point) -> Vec<Point> {
let w = ring.2 - ring.0;
let h = ring.3 - ring.1;
let perim = 2.0 * (w + h);
if perim <= 0.0 {
return Vec::new();
}
let da = ring_perimeter_dist(ring, a);
let db = ring_perimeter_dist(ring, b);
let cw_span = (db - da).rem_euclid(perim);
let ccw_span = perim - cw_span;
if cw_span <= ccw_span {
corners_between_clockwise(ring, da, db)
} else {
let mut v = corners_between_clockwise(ring, db, da);
v.reverse();
v
}
}
fn route_perimeter(
source_side: Side,
target_side: Side,
source_port: Point,
target_port: Point,
ring: (f64, f64, f64, f64),
blocked: &dyn Fn(&Point, &Point) -> bool,
) -> Vec<Point> {
let source_exit = safe_ring_exit(source_side, &source_port, ring, blocked);
let target_exit = safe_ring_exit(target_side, &target_port, ring, blocked);
let source_ring = source_exit
.last()
.cloned()
.unwrap_or_else(|| source_port.clone());
let target_ring = target_exit
.last()
.cloned()
.unwrap_or_else(|| target_port.clone());
let mut out = vec![source_port];
out.extend(source_exit);
out.extend(ring_path(ring, &source_ring, &target_ring));
out.push(target_ring);
out.extend(target_exit.into_iter().rev().skip(1));
out.push(target_port);
collapse_retraced(&mut out);
out
}
fn collapse_retraced(points: &mut Vec<Point>) {
points.dedup_by(|a, b| (a.x - b.x).abs() < EPS && (a.y - b.y).abs() < EPS);
let mut i = 1;
while i + 1 < points.len() {
let (a, b, c) = (&points[i - 1], &points[i], &points[i + 1]);
let (in_dx, in_dy) = (b.x - a.x, b.y - a.y);
let (out_dx, out_dy) = (c.x - b.x, c.y - b.y);
let antiparallel = (in_dx * out_dx + in_dy * out_dy) < -EPS
&& (in_dx * out_dy - in_dy * out_dx).abs() < EPS;
if antiparallel {
points.remove(i);
points.dedup_by(|a, b| (a.x - b.x).abs() < EPS && (a.y - b.y).abs() < EPS);
i = i.saturating_sub(1).max(1);
} else {
i += 1;
}
}
}
fn perimeter_faces(
source: &PlacedNode,
target: &PlacedNode,
ring: (f64, f64, f64, f64),
nodes: &[PlacedNode],
main_flow: &[Vec<Point>],
) -> (Side, Side) {
let mut best: Option<(PerimeterCost, (Side, Side))> = None;
for (cost, sides) in perimeter_face_candidates(source, target, ring, nodes, main_flow) {
let rank = |c: &PerimeterCost| (c.0, c.1, c.2);
let better = best.as_ref().is_none_or(|(seen, _)| {
rank(&cost) < rank(seen) || (rank(&cost) == rank(seen) && cost.3 < seen.3 - EPS)
});
if better {
best = Some((cost, sides));
}
}
best.map(|(_, sides)| sides)
.unwrap_or((Side::Top, Side::Top))
}
fn perimeter_face_candidates(
source: &PlacedNode,
target: &PlacedNode,
ring: (f64, f64, f64, f64),
nodes: &[PlacedNode],
main_flow: &[Vec<Point>],
) -> Vec<(PerimeterCost, (Side, Side))> {
let ids = (source.id.as_str(), target.id.as_str());
let blocked = |a: &Point, b: &Point| segment_crosses_any_node(a, b, nodes, ids);
let mut out = Vec::with_capacity(PERIMETER_FACE_ORDER.len() * PERIMETER_FACE_ORDER.len());
for &source_side in &PERIMETER_FACE_ORDER {
for &target_side in &PERIMETER_FACE_ORDER {
let route = route_perimeter(
source_side,
target_side,
face_port(source, source_side, PORT_INSET),
face_port(target, target_side, PORT_INSET),
ring,
&blocked,
);
let punctures =
staircase_punctures_its_own_endpoint(&route, Some(source), Some(target));
out.push((
(
usize::from(punctures),
crossings_with(&route, main_flow),
route.len().saturating_sub(2),
polyline_length(&route),
),
(source_side, target_side),
));
}
}
out
}
pub(crate) fn fewest_perimeter_crossings(
source: &PlacedNode,
target: &PlacedNode,
nodes: &[PlacedNode],
clusters: &[PlacedCluster],
main_flow: &[Vec<Point>],
) -> usize {
let frames = cluster_node_boxes(clusters);
let ring = expand_bounds(
box_bounds(nodes, &frames, [source, target]),
PERIMETER_MARGIN,
);
let candidates = perimeter_face_candidates(source, target, ring, nodes, main_flow);
let clean = candidates.iter().any(|(c, _)| c.0 == 0);
candidates
.iter()
.filter(|(c, _)| !clean || c.0 == 0)
.map(|(c, _)| c.1)
.min()
.unwrap_or(0)
}
fn crossings_with(route: &[Point], main_flow: &[Vec<Point>]) -> usize {
route
.windows(2)
.map(|w| {
main_flow
.iter()
.flat_map(|other| other.windows(2))
.filter(|o| segment_crossing(w, o).is_some())
.count()
})
.sum()
}
type PerimeterCost = (usize, usize, usize, f64);
const PERIMETER_FACE_ORDER: [Side; 4] = [Side::Right, Side::Bottom, Side::Left, Side::Top];
fn polyline_length(points: &[Point]) -> f64 {
points
.windows(2)
.map(|w| (w[1].x - w[0].x).hypot(w[1].y - w[0].y))
.sum()
}
#[allow(clippy::too_many_arguments)]
pub fn route_edge(
direction: Direction,
source: &PlacedNode,
target: &PlacedNode,
raw: &[Point],
source_rank: Option<i32>,
target_rank: Option<i32>,
source_out_degree: usize,
target_in_degree: usize,
) -> Vec<Point> {
let shape = classify(
direction,
source,
target,
raw,
source_rank,
target_rank,
source_out_degree,
target_in_degree,
&[],
&[],
false,
false,
false,
&[],
);
let source_coord = face_center_coord(source, shape.source_side);
let target_coord = face_center_coord(target, shape.target_side);
let both = [source.clone(), target.clone()];
let ring = expand_bounds(content_bounds(&both, &[]), PERIMETER_MARGIN);
route_with_ports(
direction,
&shape,
source,
target,
source_coord,
target_coord,
raw,
ring,
&both,
None,
)
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum FaceEnd {
Source,
Target,
}
struct FaceClaim {
edge_id: String,
end: FaceEnd,
other_tangent: f64,
aligned: bool,
trunk: bool,
fan_lane: bool,
}
pub struct EligibleEdge<'a> {
pub id: &'a str,
pub source: &'a str,
pub target: &'a str,
pub raw: &'a [Point],
pub source_rank: Option<i32>,
pub target_rank: Option<i32>,
pub source_out_degree: usize,
pub target_in_degree: usize,
pub aside: bool,
}
pub struct RoutedFlowchart {
pub points: HashMap<String, Vec<Point>>,
pub required_size: HashMap<String, Size>,
pub pass_through_eligible: std::collections::HashSet<String>,
pub bar_geometry: HashMap<String, (Point, Size)>,
}
fn is_pass_through_shape(shape: &EdgeShape) -> bool {
shape.source_axis == Axis::Flow
&& !shape.fan_lane
&& !rides_the_perimeter(shape)
&& !shape.staircase
}
struct Eviction {
source_coord: HashMap<String, f64>,
target_coord: HashMap<String, f64>,
required_size: HashMap<String, Size>,
fan_step: HashMap<String, f64>,
}
fn evict(
by_id: &HashMap<&str, &PlacedNode>,
edges: &[EligibleEdge],
shapes: &[Option<EdgeShape>],
chain_next: &HashMap<String, String>,
) -> Eviction {
let mut groups: HashMap<(String, Side), Vec<FaceClaim>> = HashMap::new();
for (edge, shape) in edges.iter().zip(shapes) {
let Some(shape) = shape else { continue };
let (Some(&source), Some(&target)) = (by_id.get(edge.source), by_id.get(edge.target))
else {
continue;
};
if shape.self_loop_fixed {
continue;
}
let is_trunk = chain_next.get(edge.source).map(String::as_str) == Some(edge.target);
if !matches!(source.shape, Glyph::Bar { .. }) {
groups
.entry((edge.source.to_string(), shape.source_side))
.or_default()
.push(FaceClaim {
edge_id: edge.id.to_string(),
end: FaceEnd::Source,
other_tangent: tangent_coord(shape.source_side, &target.center),
aligned: shape.aligned,
trunk: is_trunk,
fan_lane: shape.fan_lane,
});
}
if matches!(target.shape, Glyph::Bar { .. }) {
continue;
}
groups
.entry((edge.target.to_string(), shape.target_side))
.or_default()
.push(FaceClaim {
edge_id: edge.id.to_string(),
end: FaceEnd::Target,
other_tangent: tangent_coord(shape.target_side, &source.center),
aligned: shape.aligned,
trunk: false,
fan_lane: false,
});
}
let mut source_coord: HashMap<String, f64> = HashMap::new();
let mut target_coord: HashMap<String, f64> = HashMap::new();
let mut required_size: HashMap<String, Size> = HashMap::new();
let mut fan_step: HashMap<String, f64> = HashMap::new();
for ((node_id, side), mut claims) in groups {
let Some(&node) = by_id.get(node_id.as_str()) else {
continue;
};
claims.sort_by(|a, b| {
a.other_tangent
.partial_cmp(&b.other_tangent)
.unwrap_or(std::cmp::Ordering::Equal)
.then_with(|| a.edge_id.cmp(&b.edge_id))
});
let n = claims.len();
let anchor = claims.iter().position(|c| c.aligned || c.trunk);
let mut max_abs_offset = 0.0_f64;
for (i, claim) in claims.iter().enumerate() {
let offset = match anchor {
Some(anchor) => (i as f64 - anchor as f64) * PORT_SPACING,
None => (i as f64 - (n as f64 - 1.0) / 2.0) * PORT_SPACING,
};
max_abs_offset = max_abs_offset.max(offset.abs());
let coord = face_center_coord(node, side) + offset;
match claim.end {
FaceEnd::Source => {
source_coord.insert(claim.edge_id.clone(), coord);
}
FaceEnd::Target => {
target_coord.insert(claim.edge_id.clone(), coord);
}
}
}
if let Some(anchor) = anchor {
let mut ranks: Vec<(String, f64)> = Vec::new();
let mut outer_neg = 0.0_f64;
let mut outer_pos = 0.0_f64;
for (i, claim) in claims.iter().enumerate() {
if !claim.fan_lane {
continue;
}
let offset = (i as f64 - anchor as f64) * PORT_SPACING;
let k = (offset.abs() / PORT_SPACING).round().max(1.0);
if offset < 0.0 {
outer_neg = outer_neg.max(k);
} else {
outer_pos = outer_pos.max(k);
}
ranks.push((claim.edge_id.clone(), k));
}
let outer_rank = outer_neg.max(outer_pos);
if outer_rank > 0.0 {
for (edge_id, k) in ranks {
let nested_k = outer_rank + 2.0 - k;
fan_step.insert(edge_id, PORT_CLEARANCE * nested_k);
}
}
}
if matches!(node.shape, Glyph::StateStart | Glyph::StateEnd) {
continue;
}
let required_flat = if n == 0 {
0.0
} else {
2.0 * (max_abs_offset + PORT_CLEARANCE)
};
let chamfer_allowance = if node.shape == Glyph::ChamferedRect {
2.0 * shapes::CHAMFER
} else {
0.0
};
let needed = required_flat + chamfer_allowance;
let entry = required_size.entry(node_id).or_insert(Size::new(0.0, 0.0));
match side {
Side::Top | Side::Bottom => entry.w = entry.w.max(needed),
Side::Left | Side::Right => entry.h = entry.h.max(needed),
}
}
Eviction {
source_coord,
target_coord,
required_size,
fan_step,
}
}
type BarPortsResult = (
HashMap<String, f64>,
HashMap<String, f64>,
HashMap<String, (f64, f64)>,
);
fn bar_ports(
direction: Direction,
by_id: &HashMap<&str, &PlacedNode>,
edges: &[EligibleEdge],
shapes: &[Option<EdgeShape>],
eviction: &Eviction,
cluster_boxes: &[PlacedNode],
) -> BarPortsResult {
let port_limits = |bar: &PlacedNode| -> Option<(f64, f64)> {
let inner = cluster_boxes
.iter()
.filter(|c| {
let (l, t, r, b) = c.bounds();
bar.center.x >= l && bar.center.x <= r && bar.center.y >= t && bar.center.y <= b
})
.min_by(|a, b| {
(a.size.w * a.size.h)
.partial_cmp(&(b.size.w * b.size.h))
.unwrap_or(std::cmp::Ordering::Equal)
})?;
let inset = super::clusters::PAD + BAR_PORT_PAD;
let (lo, hi) = (
cross(direction, &inner.center) - cross_extent(direction, inner) + inset,
cross(direction, &inner.center) + cross_extent(direction, inner) - inset,
);
(hi > lo).then_some((lo, hi))
};
#[derive(Default)]
struct BarFaces {
upstream: Vec<(String, f64)>,
downstream: Vec<(String, f64)>,
}
let mut bars: HashMap<String, BarFaces> = HashMap::new();
for (edge, shape) in edges.iter().zip(shapes) {
if shape.is_none() {
continue;
}
let (Some(&source), Some(&target)) = (by_id.get(edge.source), by_id.get(edge.target))
else {
continue;
};
if matches!(source.shape, Glyph::Bar { .. }) {
let c = eviction
.target_coord
.get(edge.id)
.copied()
.unwrap_or_else(|| cross(direction, &target.center));
bars.entry(edge.source.to_string())
.or_default()
.downstream
.push((edge.id.to_string(), c));
}
if matches!(target.shape, Glyph::Bar { .. }) {
let c = eviction
.source_coord
.get(edge.id)
.copied()
.unwrap_or_else(|| cross(direction, &source.center));
bars.entry(edge.target.to_string())
.or_default()
.upstream
.push((edge.id.to_string(), c));
}
}
let mut source_coord = HashMap::new();
let mut target_coord = HashMap::new();
let mut spans: HashMap<String, (f64, f64)> = HashMap::new();
for (bar_id, faces) in bars {
let centroid = if faces.downstream.len() == 1 && faces.upstream.len() > 1 {
Some(faces.upstream.iter().map(|(_, c)| c).sum::<f64>() / faces.upstream.len() as f64)
} else {
None
};
let limits = by_id.get(bar_id.as_str()).and_then(|bar| port_limits(bar));
let clamp = |c: f64| match limits {
Some((lo, hi)) => c.clamp(lo, hi),
None => c,
};
let mut lo = f64::INFINITY;
let mut hi = f64::NEG_INFINITY;
for (id, c) in faces.downstream {
let c = clamp(centroid.unwrap_or(c));
lo = lo.min(c);
hi = hi.max(c);
source_coord.insert(id, c);
}
for (id, c) in faces.upstream {
let c = clamp(c);
lo = lo.min(c);
hi = hi.max(c);
target_coord.insert(id, c);
}
if lo.is_finite() {
spans.insert(bar_id, (lo, hi));
}
}
(source_coord, target_coord, spans)
}
fn straddle_bar_ports(
nodes: &[PlacedNode],
spans: &HashMap<String, (f64, f64)>,
) -> Vec<PlacedNode> {
nodes
.iter()
.cloned()
.map(|mut n| {
let Some(&(lo, hi)) = spans.get(&n.id) else {
return n;
};
let Glyph::Bar { horizontal } = n.shape else {
return n;
};
let lo = lo - BAR_PORT_PAD;
let hi = hi + BAR_PORT_PAD;
let length = (hi - lo).max(2.0 * BAR_PORT_PAD);
let mid = (lo + hi) / 2.0;
if horizontal {
n.center.x = mid;
n.size.w = length;
} else {
n.center.y = mid;
n.size.h = length;
}
n
})
.collect()
}
type BuildShapesResult = (
Vec<Option<EdgeShape>>,
Eviction,
HashMap<String, (f64, f64)>,
);
#[allow(clippy::too_many_arguments)]
fn build_shapes_and_eviction<'a>(
direction: Direction,
nodes: &'a [PlacedNode],
by_id: &HashMap<&'a str, &'a PlacedNode>,
edges: &[EligibleEdge],
cluster_boxes: &[PlacedNode],
cluster_ids: &std::collections::HashSet<&str>,
fixed_self_loops: bool,
chain_next: &HashMap<String, String>,
main_flow: &[Vec<Point>],
) -> BuildShapesResult {
let mut shapes: Vec<Option<EdgeShape>> = edges
.iter()
.map(|e| {
let (Some(&source), Some(&target)) = (by_id.get(e.source), by_id.get(e.target)) else {
return None;
};
Some(classify(
direction,
source,
target,
e.raw,
e.source_rank,
e.target_rank,
e.source_out_degree,
e.target_in_degree,
nodes,
cluster_boxes,
cluster_ids.contains(e.source),
fixed_self_loops,
e.aside,
main_flow,
))
})
.collect();
retreat_fixed_self_loops(direction, edges, &mut shapes);
let mut eviction = evict(by_id, edges, &shapes, chain_next);
let (bar_source_coord, bar_target_coord, bar_spans) =
bar_ports(direction, by_id, edges, &shapes, &eviction, cluster_boxes);
eviction.source_coord.extend(bar_source_coord);
eviction.target_coord.extend(bar_target_coord);
(shapes, eviction, bar_spans)
}
fn perimeter_lanes<'a>(
by_id: &HashMap<&str, &PlacedNode>,
edges: &[EligibleEdge<'a>],
shapes: &[Option<EdgeShape>],
) -> HashMap<&'a str, usize> {
let mut ids: Vec<&str> = edges
.iter()
.zip(shapes)
.filter_map(|(e, s)| {
let s = s.as_ref()?;
let (Some(&source), Some(&target)) = (by_id.get(e.source), by_id.get(e.target)) else {
return None;
};
(rides_the_perimeter(s) && source.id != target.id).then_some(e.id)
})
.collect();
ids.sort_unstable();
ids.into_iter().enumerate().map(|(i, id)| (id, i)).collect()
}
fn cluster_as_node(c: &PlacedCluster) -> PlacedNode {
PlacedNode {
id: c.id.clone(),
shape: Glyph::default(),
center: c.center.clone(),
size: c.size,
label: Label::measure(""),
panel: None,
series: None,
mark: None,
style: None,
}
}
fn cluster_node_boxes(clusters: &[PlacedCluster]) -> Vec<PlacedNode> {
clusters.iter().map(cluster_as_node).collect()
}
fn build_by_id<'a>(
nodes: &'a [PlacedNode],
cluster_boxes: &'a [PlacedNode],
) -> HashMap<&'a str, &'a PlacedNode> {
let mut by_id: HashMap<&str, &PlacedNode> = nodes.iter().map(|n| (n.id.as_str(), n)).collect();
for cb in cluster_boxes {
by_id.entry(cb.id.as_str()).or_insert(cb);
}
by_id
}
pub fn route_flowchart(
direction: Direction,
nodes: &[PlacedNode],
clusters: &[PlacedCluster],
edges: &[EligibleEdge],
chain_next: &HashMap<String, String>,
fixed_self_loops: bool,
) -> RoutedFlowchart {
let cluster_boxes = cluster_node_boxes(clusters);
let by_id = build_by_id(nodes, &cluster_boxes);
let cluster_ids: std::collections::HashSet<&str> =
clusters.iter().map(|c| c.id.as_str()).collect();
let (_, _, bar_spans) = build_shapes_and_eviction(
direction,
nodes,
&by_id,
edges,
&cluster_boxes,
&cluster_ids,
fixed_self_loops,
chain_next,
&[],
);
let nodes_owned = straddle_bar_ports(nodes, &bar_spans);
let bar_geometry: HashMap<String, (Point, Size)> = nodes_owned
.iter()
.filter(|n| bar_spans.contains_key(&n.id))
.map(|n| (n.id.clone(), (n.center.clone(), n.size)))
.collect();
let nodes: &[PlacedNode] = &nodes_owned;
let cluster_boxes = cluster_node_boxes(clusters);
let by_id = build_by_id(nodes, &cluster_boxes);
let (mut shapes, mut eviction, _) = build_shapes_and_eviction(
direction,
nodes,
&by_id,
edges,
&cluster_boxes,
&cluster_ids,
fixed_self_loops,
chain_next,
&[],
);
nest_merge_target_hops(direction, edges, &by_id, &mut shapes, &eviction);
let base_bounds = content_bounds(nodes, clusters);
let mut lane_of = perimeter_lanes(&by_id, edges, &shapes);
let mut points = HashMap::with_capacity(edges.len());
route_pass(
RoutePass {
direction,
edges,
shapes: &shapes,
by_id: &by_id,
eviction: &eviction,
lane_of: &lane_of,
base_bounds,
nodes,
},
false,
&mut points,
);
if shapes.iter().flatten().any(|s| s.aside) {
let main_flow = main_flow_polylines(edges, &shapes, &by_id, &points);
let (mut retry_shapes, retry_eviction, _) = build_shapes_and_eviction(
direction,
nodes,
&by_id,
edges,
&cluster_boxes,
&cluster_ids,
fixed_self_loops,
chain_next,
&main_flow,
);
let moved = shapes.iter().zip(&retry_shapes).any(|(was, now)| {
matches!((was, now), (Some(was), Some(now))
if was.aside
&& (was.source_side != now.source_side || was.target_side != now.target_side))
});
if moved {
nest_merge_target_hops(direction, edges, &by_id, &mut retry_shapes, &retry_eviction);
shapes = retry_shapes;
eviction = retry_eviction;
lane_of = perimeter_lanes(&by_id, edges, &shapes);
points.clear();
route_pass(
RoutePass {
direction,
edges,
shapes: &shapes,
by_id: &by_id,
eviction: &eviction,
lane_of: &lane_of,
base_bounds,
nodes,
},
false,
&mut points,
);
}
}
route_pass(
RoutePass {
direction,
edges,
shapes: &shapes,
by_id: &by_id,
eviction: &eviction,
lane_of: &lane_of,
base_bounds,
nodes,
},
true,
&mut points,
);
let pass_through_eligible: std::collections::HashSet<String> = edges
.iter()
.zip(&shapes)
.filter_map(|(e, s)| {
s.as_ref()
.filter(|s| is_pass_through_shape(s))
.map(|_| e.id.to_string())
})
.collect();
RoutedFlowchart {
points,
required_size: eviction.required_size,
pass_through_eligible,
bar_geometry,
}
}
struct RoutePass<'a> {
direction: Direction,
edges: &'a [EligibleEdge<'a>],
shapes: &'a [Option<EdgeShape>],
by_id: &'a HashMap<&'a str, &'a PlacedNode>,
eviction: &'a Eviction,
lane_of: &'a HashMap<&'a str, usize>,
base_bounds: (f64, f64, f64, f64),
nodes: &'a [PlacedNode],
}
fn route_pass(pass: RoutePass, riders: bool, points: &mut HashMap<String, Vec<Point>>) {
let RoutePass {
direction,
edges,
shapes,
by_id,
eviction,
lane_of,
base_bounds,
nodes,
} = pass;
for (edge, shape) in edges.iter().zip(shapes) {
let Some(shape) = shape else { continue };
let (Some(&source), Some(&target)) = (by_id.get(edge.source), by_id.get(edge.target))
else {
continue;
};
if routes_last(shape, source, target) != riders {
continue;
}
let source_coord = eviction
.source_coord
.get(edge.id)
.copied()
.unwrap_or_else(|| face_center_coord(source, shape.source_side));
let target_coord = eviction
.target_coord
.get(edge.id)
.copied()
.unwrap_or_else(|| face_center_coord(target, shape.target_side));
let ring = match lane_of.get(edge.id) {
Some(&lane) => expand_bounds(
base_bounds,
PERIMETER_MARGIN + lane as f64 * PERIMETER_LANE_SPACING,
),
None => base_bounds,
};
let routed = route_with_ports(
direction,
shape,
source,
target,
source_coord,
target_coord,
edge.raw,
ring,
nodes,
eviction.fan_step.get(edge.id).copied(),
);
let routed = remove_spikes(routed);
points.insert(edge.id.to_string(), routed);
}
}
pub const LABEL_CLEARANCE: f64 = 16.0;
pub struct LabelSlot {
pub center: Point,
pub length: f64,
pub is_flow_axis: bool,
pub horizontal: bool,
}
fn segment_is_vertical(a: &Point, b: &Point) -> bool {
(a.x - b.x).abs() < EPS
}
pub fn label_slot(direction: Direction, points: &[Point]) -> Option<LabelSlot> {
label_slot_clear(direction, points, &|_| 0)
}
pub fn label_slot_clear(
direction: Direction,
points: &[Point],
covered: &dyn Fn(&Point) -> usize,
) -> Option<LabelSlot> {
if points.len() < 2 {
return points.first().map(|p| LabelSlot {
center: p.clone(),
length: 0.0,
is_flow_axis: false,
horizontal: true,
});
}
let flow_is_vertical = matches!(direction, Direction::TopToBottom | Direction::BottomToTop);
let total = super::edges::length(points);
let mut best: Option<(usize, usize, f64, bool, f64)> = None;
let mut run = 0.0;
for (i, w) in points.windows(2).enumerate() {
let (a, b) = (&w[0], &w[1]);
let vertical = segment_is_vertical(a, b);
let len = (b.x - a.x).hypot(b.y - a.y);
let is_flow = vertical == flow_is_vertical;
let center = Point::new((a.x + b.x) / 2.0, (a.y + b.y) / 2.0);
let from_mid = (run + len / 2.0 - total / 2.0).abs();
run += len;
let n = covered(¢er);
let better = match best {
None => true,
Some((_, best_n, best_len, best_is_flow, best_mid)) => {
if n != best_n {
n < best_n
} else if is_flow != best_is_flow {
is_flow
} else if (len - best_len).abs() > EPS {
len > best_len
} else {
from_mid < best_mid - EPS
}
}
};
if better {
best = Some((i, n, len, is_flow, from_mid));
}
}
let (i, _, len, is_flow, _) = best?;
let (a, b) = (&points[i], &points[i + 1]);
Some(LabelSlot {
center: Point::new((a.x + b.x) / 2.0, (a.y + b.y) / 2.0),
length: len,
is_flow_axis: is_flow,
horizontal: !segment_is_vertical(a, b),
})
}
pub fn plate_coverage(
center: &Point,
size: Size,
own_id: &str,
routes: &HashMap<String, Vec<Point>>,
nodes: &[PlacedNode],
frames: &[PlacedCluster],
) -> usize {
let (l, t, r, b) = (
center.x - size.w / 2.0,
center.y - size.h / 2.0,
center.x + size.w / 2.0,
center.y + size.h / 2.0,
);
let mut n = routes
.iter()
.filter(|(id, pts)| {
id.as_str() != own_id
&& pts
.windows(2)
.any(|w| segment_crosses_rect(&w[0], &w[1], center, size))
})
.count();
n += nodes
.iter()
.filter(|node| {
let (nl, nt, nr, nb) = node.bounds();
nl < r - EPS && nr > l + EPS && nt < b - EPS && nb > t + EPS
})
.count();
n += frames
.iter()
.filter(|frame| {
let (fl, ft, fr, fb) = frame.bounds();
let corners = [
(Point::new(fl, ft), Point::new(fr, ft)),
(Point::new(fl, fb), Point::new(fr, fb)),
(Point::new(fl, ft), Point::new(fl, fb)),
(Point::new(fr, ft), Point::new(fr, fb)),
];
corners
.iter()
.any(|(a, b)| segment_crosses_rect(a, b, center, size))
})
.count();
n
}
pub fn label_min_length(plate_size: Size, horizontal: bool) -> f64 {
(if horizontal {
plate_size.w
} else {
plate_size.h
}) + 2.0 * LABEL_CLEARANCE
}
fn cross_extent(direction: Direction, node: &PlacedNode) -> f64 {
match direction {
Direction::TopToBottom | Direction::BottomToTop => node.size.w / 2.0,
Direction::LeftToRight | Direction::RightToLeft => node.size.h / 2.0,
}
}
#[derive(Debug, Clone, Default)]
pub struct LaneUnits {
of_node: HashMap<String, String>,
ancestors: HashMap<String, Vec<String>>,
members: HashMap<String, Vec<String>>,
pad: HashMap<String, f64>,
}
impl LaneUnits {
pub fn build(tree: &super::clusters::Tree, nodes: &[PlacedNode]) -> LaneUnits {
let placed: std::collections::HashSet<&str> = nodes.iter().map(|n| n.id.as_str()).collect();
let mut of_node: HashMap<String, String> = HashMap::new();
for n in nodes {
let Some(unit) = tree.outermost(&n.id) else {
continue;
};
of_node.insert(n.id.clone(), unit.to_string());
}
let mut blocks: Vec<&super::clusters::Cluster> = tree.iter().collect();
blocks.sort_by_key(|b| b.depth);
let mut members: HashMap<String, Vec<String>> = HashMap::new();
let mut ancestors: HashMap<String, Vec<String>> = HashMap::new();
for b in &blocks {
let held: Vec<String> = tree
.descendants(&b.id)
.into_iter()
.filter(|d| placed.contains(d))
.map(str::to_string)
.collect();
if held.is_empty() {
continue;
}
for id in &held {
ancestors.entry(id.clone()).or_default().push(b.id.clone());
}
members.insert(b.id.clone(), held);
}
let mut pad: HashMap<String, f64> = HashMap::new();
for b in blocks.iter().rev() {
let inner = b
.child_clusters
.iter()
.filter_map(|c| pad.get(c).copied())
.fold(0.0_f64, f64::max);
pad.insert(b.id.clone(), super::clusters::PAD + inner);
}
pad.retain(|id, _| members.contains_key(id));
LaneUnits {
of_node,
ancestors,
members,
pad,
}
}
pub fn unit_of<'a>(&'a self, id: &'a str) -> &'a str {
self.of_node.get(id).map(String::as_str).unwrap_or(id)
}
pub fn separating_unit<'a>(&'a self, id: &'a str, other: &str) -> &'a str {
self.ancestors
.get(id)
.into_iter()
.flatten()
.find(|block| {
!self
.members
.get(block.as_str())
.is_some_and(|held| held.iter().any(|m| m == other))
})
.map(String::as_str)
.unwrap_or(id)
}
pub fn is_block(&self, unit: &str) -> bool {
self.members.contains_key(unit)
}
pub fn members_of(&self, unit: &str) -> Vec<&str> {
self.members
.get(unit)
.map(|ids| ids.iter().map(String::as_str).collect())
.unwrap_or_default()
}
pub fn frame_pad(&self, unit: &str) -> f64 {
self.pad.get(unit).copied().unwrap_or(0.0)
}
pub fn band(
&self,
direction: Direction,
nodes: &[PlacedNode],
index: &HashMap<String, usize>,
unit: &str,
) -> (f64, f64) {
let Some(ids) = self.members.get(unit) else {
let Some(&i) = index.get(unit) else {
return (0.0, 0.0);
};
let (c, half) = (
cross(direction, &nodes[i].center),
cross_extent(direction, &nodes[i]),
);
return (c - half, c + half);
};
let (mut lo, mut hi) = (f64::INFINITY, f64::NEG_INFINITY);
for id in ids {
let Some(&i) = index.get(id) else { continue };
let (c, half) = (
cross(direction, &nodes[i].center),
cross_extent(direction, &nodes[i]),
);
lo = lo.min(c - half);
hi = hi.max(c + half);
}
if !lo.is_finite() {
return (0.0, 0.0);
}
let pad = self.pad.get(unit).copied().unwrap_or(0.0);
(lo - pad, hi + pad)
}
pub fn shift(
&self,
direction: Direction,
nodes: &mut [PlacedNode],
index: &HashMap<String, usize>,
unit: &str,
delta: f64,
) {
if delta.abs() <= EPS {
return;
}
match self.members.get(unit) {
Some(ids) => {
for id in ids {
if let Some(&i) = index.get(id) {
nodes[i].center = shift_cross(direction, &nodes[i].center, delta);
}
}
}
None => {
if let Some(&i) = index.get(unit) {
nodes[i].center = shift_cross(direction, &nodes[i].center, delta);
}
}
}
}
}
const MERGE_MEDIAN_MIN_SOURCES: usize = 3;
pub(super) fn merge_trunk_index(sources: &[&str], on_a_lane: &dyn Fn(&str) -> bool) -> usize {
let on_lane: Vec<usize> = sources
.iter()
.enumerate()
.filter(|(_, s)| on_a_lane(s))
.map(|(i, _)| i)
.collect();
match on_lane.as_slice() {
[only] => *only,
_ => sources.len() / 2,
}
}
struct PureMerge {
target: String,
sources: Vec<String>,
}
fn pure_merges(
node_rank: &HashMap<String, i32>,
candidates: &[(String, String)],
is_bar_id: &dyn Fn(&str) -> bool,
) -> Vec<PureMerge> {
let mut ranks: Vec<i32> = node_rank.values().copied().collect();
ranks.sort_unstable();
ranks.dedup();
let mut targets: Vec<&str> = Vec::new();
for (_, t) in candidates {
if !targets.contains(&t.as_str()) {
targets.push(t.as_str());
}
}
let mut merges = Vec::new();
for target in targets {
if is_bar_id(target) {
continue;
}
let Some(&target_rank) = node_rank.get(target) else {
continue;
};
let Some(&below) = ranks.iter().rev().find(|&&r| r < target_rank) else {
continue; };
let mut sources: Vec<String> = Vec::new();
for (s, t) in candidates {
if t != target || is_bar_id(s) || node_rank.get(s) != Some(&below) {
continue;
}
if !sources.iter().any(|seen| seen == s) {
sources.push(s.clone());
}
}
if sources.len() < MERGE_MEDIAN_MIN_SOURCES {
continue;
}
let fans_out = candidates.iter().any(|(s, t)| {
t != target && node_rank.get(t) == Some(&target_rank) && sources.contains(s)
});
if fans_out {
continue;
}
merges.push(PureMerge {
target: target.to_string(),
sources,
});
}
merges
}
fn promote_merge_trunks(
window: &mut Vec<&(String, String)>,
merges: &[PureMerge],
used_in: &std::collections::HashSet<String>,
) {
for merge in merges {
let sources: Vec<&str> = merge.sources.iter().map(String::as_str).collect();
let trunk = sources[merge_trunk_index(&sources, &|id| used_in.contains(id))];
let (Some(from), Some(to)) = (
window
.iter()
.position(|(s, t)| s == trunk && *t == merge.target),
window.iter().position(|(_, t)| *t == merge.target),
) else {
continue; };
if from != to {
let edge = window.remove(from);
window.insert(to, edge);
}
}
}
#[must_use = "a moved node's self-loop raw waypoints go stale unless this delta is applied back — see this function's own doc"]
pub fn align_straight_lanes(
direction: Direction,
nodes: &mut [PlacedNode],
node_rank: &HashMap<String, i32>,
candidates: &[(String, String)],
units: &LaneUnits,
) -> (HashMap<String, f64>, HashMap<String, String>) {
align_straight_lanes_with(direction, nodes, node_rank, candidates, None, units)
}
pub(super) fn align_straight_lanes_with(
direction: Direction,
nodes: &mut [PlacedNode],
node_rank: &HashMap<String, i32>,
candidates: &[(String, String)],
preselected: Option<&HashMap<String, String>>,
units: &LaneUnits,
) -> (HashMap<String, f64>, HashMap<String, String>) {
if nodes.len() < 2 {
return (HashMap::new(), HashMap::new());
}
let id_index: HashMap<String, usize> = nodes
.iter()
.enumerate()
.map(|(i, n)| (n.id.clone(), i))
.collect();
let initial_cross: Vec<f64> = nodes.iter().map(|n| cross(direction, &n.center)).collect();
let mut by_rank: HashMap<i32, Vec<usize>> = HashMap::new();
for (id, &rank) in node_rank {
if let Some(&i) = id_index.get(id) {
by_rank.entry(rank).or_default().push(i);
}
}
for ids in by_rank.values_mut() {
ids.sort_by(|&a, &b| {
cross(direction, &nodes[a].center)
.partial_cmp(&cross(direction, &nodes[b].center))
.unwrap_or(std::cmp::Ordering::Equal)
.then_with(|| nodes[a].id.cmp(&nodes[b].id))
});
}
let merges = pure_merges(node_rank, candidates, &|id| {
id_index.get(id).is_some_and(|&i| is_bar(&nodes[i]))
});
let next: HashMap<String, String> = if let Some(pre) = preselected {
pre.clone()
} else {
let mut used_out: std::collections::HashSet<String> = std::collections::HashSet::new();
let mut used_in: std::collections::HashSet<String> = std::collections::HashSet::new();
let mut next: HashMap<String, String> = HashMap::new();
let continues: std::collections::HashSet<&str> =
candidates.iter().map(|(s, _)| s.as_str()).collect();
let mut ranks: Vec<i32> = node_rank.values().copied().collect();
ranks.sort_unstable();
ranks.dedup();
for window in ranks.windows(2) {
let (r, next_r) = (window[0], window[1]);
let mut pair_candidates: Vec<&(String, String)> = candidates
.iter()
.filter(|(s, t)| node_rank.get(s) == Some(&r) && node_rank.get(t) == Some(&next_r))
.collect();
let mut targets_by_source: HashMap<&str, Vec<f64>> = HashMap::new();
for (s, t) in &pair_candidates {
targets_by_source
.entry(s.as_str())
.or_default()
.push(cross(direction, &nodes[id_index[t]].center));
}
for v in targets_by_source.values_mut() {
v.sort_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal));
}
let median_of = |s: &str| -> f64 {
let v = &targets_by_source[s];
let n = v.len();
if n % 2 == 1 {
v[n / 2]
} else {
(v[n / 2 - 1] + v[n / 2]) / 2.0
}
};
pair_candidates.sort_by(|(s1, t1), (s2, t2)| {
used_in
.contains(s2.as_str())
.cmp(&used_in.contains(s1.as_str()))
.then_with(|| {
let sc1 = cross(direction, &nodes[id_index[s1]].center);
let sc2 = cross(direction, &nodes[id_index[s2]].center);
sc1.partial_cmp(&sc2).unwrap_or(std::cmp::Ordering::Equal)
})
.then_with(|| {
continues
.contains(t2.as_str())
.cmp(&continues.contains(t1.as_str()))
})
.then_with(|| {
let tc1 = cross(direction, &nodes[id_index[t1]].center);
let tc2 = cross(direction, &nodes[id_index[t2]].center);
let d1 = (tc1 - median_of(s1)).abs();
let d2 = (tc2 - median_of(s2)).abs();
if (d1 - d2).abs() < EPS {
std::cmp::Ordering::Equal
} else {
d1.partial_cmp(&d2).unwrap_or(std::cmp::Ordering::Equal)
}
})
.then_with(|| {
let tc1 = cross(direction, &nodes[id_index[t1]].center);
let tc2 = cross(direction, &nodes[id_index[t2]].center);
tc1.partial_cmp(&tc2).unwrap_or(std::cmp::Ordering::Equal)
})
.then_with(|| s1.cmp(s2))
.then_with(|| t1.cmp(t2))
});
promote_merge_trunks(&mut pair_candidates, &merges, &used_in);
for (s, t) in pair_candidates {
if used_out.contains(s) || used_in.contains(t) {
continue;
}
if is_bar(&nodes[id_index[s]]) || is_bar(&nodes[id_index[t]]) {
continue;
}
used_out.insert(s.clone());
used_in.insert(t.clone());
next.insert(s.clone(), t.clone());
}
}
next
};
let used_out: std::collections::HashSet<String> = next.keys().cloned().collect();
let used_in: std::collections::HashSet<String> = next.values().cloned().collect();
let mut chains: Vec<Vec<String>> = Vec::new();
for s in &used_out {
if used_in.contains(s) {
continue; }
let mut chain = vec![s.clone()];
let mut cur = s.clone();
while let Some(nxt) = next.get(&cur) {
chain.push(nxt.clone());
cur = nxt.clone();
}
chains.push(chain);
}
chains.sort();
let mut chain_desired: HashMap<usize, f64> = HashMap::new();
let mut moved_units: std::collections::HashSet<String> = std::collections::HashSet::new();
for chain in &chains {
if chain.len() < 2 {
continue;
}
let mut items: Vec<(&str, f64)> = Vec::new();
for id in chain {
let unit = units.unit_of(id);
if items.iter().any(|(u, _)| *u == unit) {
continue;
}
items.push((unit, cross(direction, &nodes[id_index[id]].center)));
}
let avg: f64 = items.iter().map(|(_, c)| *c).sum::<f64>() / items.len() as f64;
let mut mine: std::collections::HashSet<&str> = std::collections::HashSet::new();
for (unit, anchor_cross) in &items {
if !units.is_block(unit) {
continue;
}
if !moved_units.insert((*unit).to_string()) {
continue;
}
mine.insert(unit);
units.shift(direction, nodes, &id_index, unit, avg - anchor_cross);
}
for id in chain {
let unit = units.unit_of(id);
if units.is_block(unit) && !mine.contains(unit) {
continue;
}
let i = id_index[id];
let flow_v = flow(direction, &nodes[i].center);
nodes[i].center = make(direction, flow_v, avg);
chain_desired.insert(i, avg);
}
}
for merge in &merges {
let trunk = match next.iter().find(|(_, t)| **t == merge.target) {
Some((s, _)) if merge.sources.contains(s) => s.clone(),
_ => continue, };
let Some(&ti) = id_index.get(trunk.as_str()) else {
continue;
};
let delta = cross(direction, &nodes[ti].center) - initial_cross[ti];
if delta.abs() <= EPS {
continue;
}
let mut moved: std::collections::HashSet<String> =
std::collections::HashSet::from([units.unit_of(&trunk).to_string()]);
for sibling in &merge.sources {
let Some(&si) = id_index.get(sibling.as_str()) else {
continue;
};
if chain_desired.contains_key(&si) {
continue;
}
let unit = units.unit_of(sibling).to_string();
if !moved.insert(unit.clone()) {
continue;
}
units.shift(direction, nodes, &id_index, &unit, delta);
}
}
for bar in nodes
.iter()
.filter(|n| is_bar(n))
.map(|n| n.id.clone())
.collect::<Vec<String>>()
{
let inputs: Vec<&str> = candidates
.iter()
.filter(|(_, t)| *t == bar)
.map(|(s, _)| s.as_str())
.collect();
let outputs: Vec<&str> = candidates
.iter()
.filter(|(s, _)| *s == bar)
.map(|(_, t)| t.as_str())
.collect();
let ([out], true) = (outputs.as_slice(), inputs.len() > 1) else {
continue;
};
let (Some(&oi), true) = (id_index.get(*out), !inputs.is_empty()) else {
continue;
};
let centroid = inputs
.iter()
.filter_map(|s| {
let unit = units.separating_unit(s, &bar);
if unit == *s {
let &i = id_index.get(*s)?;
Some(cross(direction, &nodes[i].center))
} else {
let (lo, hi) = units.band(direction, nodes, &id_index, unit);
Some((lo + hi) / 2.0)
}
})
.sum::<f64>()
/ inputs.len() as f64;
let delta = centroid - cross(direction, &nodes[oi].center);
if delta.abs() <= EPS {
continue;
}
let lane = chains
.iter()
.find(|c| c.iter().any(|id| id == out))
.cloned()
.unwrap_or_else(|| vec![(*out).to_string()]);
let mut shifted: std::collections::HashSet<String> = std::collections::HashSet::new();
for id in &lane {
let unit = units.unit_of(id).to_string();
if shifted.insert(unit.clone()) {
units.shift(direction, nodes, &id_index, &unit, delta);
}
if let Some(&i) = id_index.get(id.as_str()) {
if let Some(desired) = chain_desired.get_mut(&i) {
*desired += delta;
}
}
}
}
let mut swept: Vec<i32> = by_rank.keys().copied().collect();
swept.sort_unstable();
for rank in swept {
let ids = &by_rank[&rank];
let mut prev: Option<usize> = None;
for &i in ids {
let Some(p) = prev.replace(i) else {
continue; };
let (behind, ahead) = (
units
.separating_unit(&nodes[p].id, &nodes[i].id)
.to_string(),
units
.separating_unit(&nodes[i].id, &nodes[p].id)
.to_string(),
);
let (_, far_behind) = units.band(direction, nodes, &id_index, &behind);
let (lo_ahead, _) = units.band(direction, nodes, &id_index, &ahead);
if lo_ahead < far_behind + super::ORTHO_NODE_SEP {
let delta = far_behind + super::ORTHO_NODE_SEP - lo_ahead;
units.shift(direction, nodes, &id_index, &ahead, delta);
}
}
}
let mut reclaimed: Vec<i32> = by_rank.keys().copied().collect();
reclaimed.sort_unstable();
for rank in reclaimed {
let ids = &by_rank[&rank];
for (slot, &i) in ids.iter().enumerate() {
let Some(&desired) = chain_desired.get(&i) else {
continue;
};
let current = cross(direction, &nodes[i].center);
if current <= desired + EPS {
continue; }
let predecessor = slot.checked_sub(1).and_then(|s| ids.get(s)).copied();
let unit = match predecessor {
Some(p) => units.separating_unit(&nodes[i].id, &nodes[p].id),
None => units.unit_of(&nodes[i].id),
}
.to_string();
let (lo, _) = units.band(direction, nodes, &id_index, &unit);
let max_far = lo + (desired - current) - super::ORTHO_NODE_SEP;
let predecessor_allows = match predecessor {
None => true, Some(p) => {
let behind = units
.separating_unit(&nodes[p].id, &nodes[i].id)
.to_string();
let (_, far_behind) = units.band(direction, nodes, &id_index, &behind);
far_behind <= max_far + EPS
}
};
if predecessor_allows {
units.shift(direction, nodes, &id_index, &unit, desired - current);
}
}
}
let deltas = nodes
.iter()
.enumerate()
.filter_map(|(i, n)| {
let delta = cross(direction, &n.center) - initial_cross[i];
(delta.abs() > EPS).then(|| (n.id.clone(), delta))
})
.collect();
(deltas, next)
}
pub fn shift_cross(direction: Direction, p: &Point, delta: f64) -> Point {
make(direction, flow(direction, p), cross(direction, p) + delta)
}
#[derive(Debug, Clone, PartialEq)]
pub struct DeadEndTier {
pub block: String,
pub members: Vec<String>,
pub side: f64,
}
pub fn place_dead_end_tiers(
direction: Direction,
nodes: &mut [PlacedNode],
tree: &super::clusters::Tree,
units: &LaneUnits,
chain_next: &HashMap<String, String>,
edges: &[(String, String, bool)],
) -> Vec<DeadEndTier> {
if nodes.len() < 2 || tree.is_empty() {
return Vec::new();
}
let index: HashMap<String, usize> = nodes
.iter()
.enumerate()
.map(|(i, n)| (n.id.clone(), i))
.collect();
let heads: std::collections::HashSet<&str> = chain_next.values().map(String::as_str).collect();
let mut chain_of: HashMap<&str, usize> = HashMap::new();
let mut chain_ids: Vec<&str> = chain_next
.keys()
.map(String::as_str)
.filter(|s| !heads.contains(s))
.collect();
chain_ids.sort_unstable();
for (ci, head) in chain_ids.into_iter().enumerate() {
let mut cur = head;
chain_of.insert(cur, ci);
while let Some(next) = chain_next.get(cur) {
cur = next.as_str();
if chain_of.insert(cur, ci).is_some() {
break; }
}
}
let mut blocks: Vec<&super::clusters::Cluster> = tree.iter().collect();
blocks.sort_by(|a, b| a.depth.cmp(&b.depth).then_with(|| a.id.cmp(&b.id)));
let mut placed: Vec<DeadEndTier> = Vec::new();
let mut spoken_for: std::collections::HashSet<String> = std::collections::HashSet::new();
for block in blocks {
let members: Vec<String> = tree
.descendants(&block.id)
.into_iter()
.filter(|m| index.contains_key(*m))
.map(str::to_string)
.collect();
if members.is_empty() || members.iter().any(|m| spoken_for.contains(m)) {
continue;
}
let is_member = |id: &str| members.iter().any(|m| m == id);
if edges.iter().any(|(t, _, _)| is_member(t)) {
continue;
}
if members.iter().any(|m| chain_of.contains_key(m.as_str())) {
continue;
}
let mut sources: Vec<&str> = Vec::new();
let mut first_source: HashMap<&str, &str> = HashMap::new();
let mut fed_from_inside = false;
for (t, h, aside) in edges {
if !is_member(h) {
continue;
}
if is_member(t) {
fed_from_inside = true;
break;
}
if *aside {
continue;
}
if !sources.contains(&t.as_str()) {
sources.push(t.as_str());
}
first_source.entry(h.as_str()).or_insert(t.as_str());
}
if fed_from_inside
|| sources.len() < 2
|| members
.iter()
.any(|m| !first_source.contains_key(m.as_str()))
{
continue;
}
let Some(&lane) = chain_of.get(sources[0]) else {
continue;
};
if sources.iter().any(|s| chain_of.get(*s) != Some(&lane)) {
continue;
}
let lane_cross = cross(direction, &nodes[index[sources[0]]].center);
if sources
.iter()
.any(|s| (cross(direction, &nodes[index[*s]].center) - lane_cross).abs() >= 0.5)
{
continue;
}
let mut ordered: Vec<(String, f64)> = members
.iter()
.map(|m| {
let src = first_source[m.as_str()];
(m.clone(), flow(direction, &nodes[index[src]].center))
})
.collect();
ordered.sort_by(|a, b| {
a.1.partial_cmp(&b.1)
.unwrap_or(std::cmp::Ordering::Equal)
.then_with(|| a.0.cmp(&b.0))
});
let mut prev_far = f64::NEG_INFINITY;
for (id, want) in &mut ordered {
let half = flow_extent(direction, &nodes[index[id.as_str()]]);
if *want - half < prev_far + super::ORTHO_NODE_SEP {
*want = prev_far + super::ORTHO_NODE_SEP + half;
}
prev_far = *want + half;
}
let (span_lo, span_hi) = ordered.iter().fold(
(f64::INFINITY, f64::NEG_INFINITY),
|(lo, hi), (id, want)| {
let half = flow_extent(direction, &nodes[index[id.as_str()]]);
(lo.min(want - half), hi.max(want + half))
},
);
let anchor = ordered[0].0.as_str();
let mut side_units: [std::collections::HashSet<String>; 2] = Default::default();
for n in nodes.iter() {
if is_member(&n.id) {
continue;
}
let c = cross(direction, &n.center);
let half = cross_extent(direction, n);
if (c - lane_cross).abs() <= half {
continue; }
let (n_lo, n_hi) = (
flow(direction, &n.center) - flow_extent(direction, n),
flow(direction, &n.center) + flow_extent(direction, n),
);
if n_hi < span_lo || n_lo > span_hi {
continue;
}
let slot = usize::from(c > lane_cross);
side_units[slot].insert(units.separating_unit(&n.id, anchor).to_string());
}
let side = if side_units[1].len() > side_units[0].len() {
-1.0
} else {
1.0
};
let lane_half = nodes
.iter()
.filter(|n| {
(cross(direction, &n.center) - lane_cross).abs() < 0.5
&& flow(direction, &n.center) >= span_lo
&& flow(direction, &n.center) <= span_hi
})
.map(|n| cross_extent(direction, n))
.fold(0.0_f64, f64::max);
let near_is_top =
side > 0.0 && matches!(direction, Direction::LeftToRight | Direction::RightToLeft);
let pad_near = frame_near_pad(tree, &block.id, near_is_top);
let mut out_near = side * lane_cross + lane_half + super::ORTHO_NODE_SEP;
for n in nodes.iter() {
if is_member(&n.id) {
continue;
}
let unit = units.separating_unit(&n.id, anchor).to_string();
let (lo, hi) = units.band(direction, nodes, &index, &unit);
let (u_lo, u_hi) = unit_flow_span(direction, nodes, &index, units, &unit);
if u_hi < span_lo || u_lo > span_hi {
continue;
}
let far = (side * lo).max(side * hi);
out_near = out_near.max(far + super::ORTHO_NODE_SEP);
}
let member_near = out_near + pad_near;
for (id, want) in &ordered {
let i = index[id.as_str()];
let half = cross_extent(direction, &nodes[i]);
nodes[i].center = make(direction, *want, side * (member_near + half));
}
spoken_for.extend(members.iter().cloned());
placed.push(DeadEndTier {
block: block.id.clone(),
members: ordered.into_iter().map(|(id, _)| id).collect(),
side,
});
}
placed
}
fn frame_near_pad(tree: &super::clusters::Tree, id: &str, near_is_top: bool) -> f64 {
let Some(block) = tree.get(id) else {
return 0.0;
};
let title = Label::measure(&block.title);
let own = super::clusters::PAD
+ if near_is_top && !title.is_blank() {
title.height + super::clusters::TITLE_PAD_Y * 2.0
} else {
0.0
};
let inner = block
.child_clusters
.iter()
.map(|c| frame_near_pad(tree, c, near_is_top))
.fold(0.0_f64, f64::max);
own + inner
}
fn unit_flow_span(
direction: Direction,
nodes: &[PlacedNode],
index: &HashMap<String, usize>,
units: &LaneUnits,
unit: &str,
) -> (f64, f64) {
let ids: Vec<&str> = if units.is_block(unit) {
units.members_of(unit)
} else {
vec![unit]
};
let (mut lo, mut hi) = (f64::INFINITY, f64::NEG_INFINITY);
for id in ids {
let Some(&i) = index.get(id) else { continue };
lo = lo.min(flow(direction, &nodes[i].center) - flow_extent(direction, &nodes[i]));
hi = hi.max(flow(direction, &nodes[i].center) + flow_extent(direction, &nodes[i]));
}
if lo.is_finite() {
(lo, hi)
} else {
(0.0, 0.0)
}
}
#[must_use]
pub fn clear_foreign_cluster_overlaps(
direction: Direction,
nodes: &mut [PlacedNode],
placed_clusters: &[PlacedCluster],
tree: &super::clusters::Tree,
) -> bool {
let units = LaneUnits::build(tree, nodes);
let id_index: HashMap<String, usize> = nodes
.iter()
.enumerate()
.map(|(i, n)| (n.id.clone(), i))
.collect();
let mut moved = false;
for cluster in placed_clusters {
let (cl, ct, cr, cb) = cluster.bounds();
let hits: Vec<String> = nodes
.iter()
.filter(|node| !tree.touches(&node.id, &cluster.id))
.filter(|node| {
let (nl, nt, nr, nb) = node.bounds();
nr.min(cr) - nl.max(cl) > 0.0 && nb.min(cb) - nt.max(ct) > 0.0
})
.map(|node| node.id.clone())
.collect();
for id in hits {
let unit = units.unit_of(&id).to_string();
let (band_lo, band_hi) = units.band(direction, nodes, &id_index, &unit);
let (near_cross, far_cross) = match direction {
Direction::TopToBottom | Direction::BottomToTop => (cl, cr),
Direction::LeftToRight | Direction::RightToLeft => (ct, cb),
};
let margin = if unit == id {
PERIMETER_MARGIN
} else {
super::ORTHO_NODE_SEP
};
let to_near = (near_cross - margin) - band_hi;
let to_far = (far_cross + margin) - band_lo;
let delta = if to_near.abs() <= to_far.abs() {
to_near
} else {
to_far
};
units.shift(direction, nodes, &id_index, &unit, delta);
moved = true;
}
}
moved
}
fn tangent_coord(side: Side, p: &Point) -> f64 {
match side {
Side::Top | Side::Bottom => p.x,
Side::Left | Side::Right => p.y,
}
}
fn face_flat_half_extent(node: &PlacedNode, side: Side) -> f64 {
let full = match side {
Side::Top | Side::Bottom => node.size.w,
Side::Left | Side::Right => node.size.h,
};
let chamfer_allowance = if node.shape == Glyph::ChamferedRect {
2.0 * shapes::CHAMFER
} else {
0.0
};
(full - chamfer_allowance).max(0.0) / 2.0
}
fn ports_on_face(
node_id: &str,
side: Side,
exclude_edge_id: &str,
edges: &[EligibleEdge],
shapes: &[Option<EdgeShape>],
points: &HashMap<String, Vec<Point>>,
) -> Vec<f64> {
let mut out = Vec::new();
for (edge, shape) in edges.iter().zip(shapes) {
if edge.id == exclude_edge_id {
continue;
}
let Some(shape) = shape else { continue };
let Some(pts) = points.get(edge.id) else {
continue;
};
if pts.is_empty() {
continue;
}
if edge.source == node_id && shape.source_side == side {
out.push(tangent_coord(side, &pts[0]));
}
if edge.target == node_id && shape.target_side == side {
out.push(tangent_coord(side, &pts[pts.len() - 1]));
}
}
out
}
fn push_outward(node: &PlacedNode, side: Side, cur: f64, occupied: &[f64]) -> f64 {
let center = face_center_coord(node, side);
let dir = if cur >= center { 1.0 } else { -1.0 };
let half_extent = face_flat_half_extent(node, side);
let candidate = cur + dir * PORT_SPACING;
if (candidate - center).abs() > half_extent {
return cur;
}
if occupied.iter().any(|&o| (o - candidate).abs() <= EPS) {
return cur;
}
candidate
}
fn segment_crosses_plate(a: &Point, b: &Point, plate: &PlacedEdgeLabel) -> bool {
segment_crosses_rect(a, b, &plate.center, plate.size)
}
pub(crate) fn segment_crosses_plate_box(a: &Point, b: &Point, center: &Point, size: Size) -> bool {
segment_crosses_rect(a, b, center, size)
}
fn segment_crosses_rect(a: &Point, b: &Point, center: &Point, size: Size) -> bool {
let (l, t, r, bo) = (
center.x - size.w / 2.0,
center.y - size.h / 2.0,
center.x + size.w / 2.0,
center.y + size.h / 2.0,
);
if (a.y - b.y).abs() < EPS {
let y = a.y;
let (x0, x1) = (a.x.min(b.x), a.x.max(b.x));
y >= t && y <= bo && x1 >= l && x0 <= r
} else if (a.x - b.x).abs() < EPS {
let x = a.x;
let (y0, y1) = (a.y.min(b.y), a.y.max(b.y));
x >= l && x <= r && y1 >= t && y0 <= bo
} else {
false
}
}
pub fn separate_coincident_detours(
direction: Direction,
nodes: &[PlacedNode],
clusters: &[PlacedCluster],
edges: &[EligibleEdge],
points: &mut HashMap<String, Vec<Point>>,
) {
let cluster_boxes = cluster_node_boxes(clusters);
let by_id = build_by_id(nodes, &cluster_boxes);
let cluster_ids: std::collections::HashSet<&str> =
clusters.iter().map(|c| c.id.as_str()).collect();
let mut detour_ids: Vec<&str> = edges
.iter()
.filter_map(|e| {
let (Some(&source), Some(&target)) = (by_id.get(e.source), by_id.get(e.target)) else {
return None;
};
let shape = classify(
direction,
source,
target,
e.raw,
e.source_rank,
e.target_rank,
e.source_out_degree,
e.target_in_degree,
nodes,
&cluster_boxes,
cluster_ids.contains(e.source),
false,
e.aside,
&[],
);
((rides_the_perimeter(&shape)
|| shape.staircase
|| shape.cross_lane_bend.is_some()
|| is_flow_flow_bend(&shape))
&& source.id != target.id)
.then_some(e.id)
})
.collect();
detour_ids.sort_unstable();
const MAX_PASSES: usize = 4;
for _ in 0..MAX_PASSES {
let mut fix: Option<(&str, f64, f64, bool)> = None; 'search: for (i, &id_a) in detour_ids.iter().enumerate() {
for &id_b in &detour_ids[i + 1..] {
let (Some(ea), Some(eb)) = (
edges.iter().find(|e| e.id == id_a),
edges.iter().find(|e| e.id == id_b),
) else {
continue;
};
if ea.source == eb.source
|| ea.source == eb.target
|| ea.target == eb.source
|| ea.target == eb.target
{
continue; }
let (Some(pa), Some(pb)) = (points.get(id_a), points.get(id_b)) else {
continue;
};
for wa in pa.windows(2) {
for wb in pb.windows(2) {
let vert_a = (wa[0].x - wa[1].x).abs() < EPS;
let vert_b = (wb[0].x - wb[1].x).abs() < EPS;
if vert_a && vert_b && (wa[0].x - wb[0].x).abs() < EPS {
let (y0a, y1a) = (wa[0].y.min(wa[1].y), wa[0].y.max(wa[1].y));
let (y0b, y1b) = (wb[0].y.min(wb[1].y), wb[0].y.max(wb[1].y));
if y0a < y1b - EPS && y0b < y1a - EPS {
fix =
Some((id_b, wb[0].x, wb[0].x + PERIMETER_LANE_SPACING, false));
break 'search;
}
}
let horiz_a = (wa[0].y - wa[1].y).abs() < EPS;
let horiz_b = (wb[0].y - wb[1].y).abs() < EPS;
if horiz_a && horiz_b && (wa[0].y - wb[0].y).abs() < EPS {
let (x0a, x1a) = (wa[0].x.min(wa[1].x), wa[0].x.max(wa[1].x));
let (x0b, x1b) = (wb[0].x.min(wb[1].x), wb[0].x.max(wb[1].x));
if x0a < x1b - EPS && x0b < x1a - EPS {
fix = Some((id_b, wb[0].y, wb[0].y + PERIMETER_LANE_SPACING, true));
break 'search;
}
}
}
}
}
}
let Some((id, old_c, new_c, horizontal)) = fix else {
break;
};
let (Some(ends), Some(pts)) = (
edges
.iter()
.find(|e| e.id == id)
.map(|e| (e.source, e.target)),
points.get(id),
) else {
continue;
};
let moved = |c: f64| {
let mut out = pts.clone();
for p in out.iter_mut() {
if horizontal && (p.y - old_c).abs() < EPS {
p.y = c;
} else if !horizontal && (p.x - old_c).abs() < EPS {
p.x = c;
}
}
out
};
let clear = |candidate: &[Point]| {
!candidate
.windows(2)
.any(|w| segment_crosses_any_node(&w[0], &w[1], nodes, ends))
};
let back_c = old_c - (new_c - old_c);
let new_c = if clear(&moved(new_c)) || !clear(&moved(back_c)) {
new_c
} else {
back_c
};
if let Some(pts) = points.get_mut(id) {
for p in pts.iter_mut() {
if horizontal && (p.y - old_c).abs() < EPS {
p.y = new_c;
} else if !horizontal && (p.x - old_c).abs() < EPS {
p.x = new_c;
}
}
}
}
}
pub fn avoid_label_plates(
direction: Direction,
nodes: &[PlacedNode],
clusters: &[PlacedCluster],
edges: &[EligibleEdge],
points: &mut HashMap<String, Vec<Point>>,
plates: &mut HashMap<String, PlacedEdgeLabel>,
chain_next: &HashMap<String, String>,
) {
let cluster_boxes = cluster_node_boxes(clusters);
let by_id = build_by_id(nodes, &cluster_boxes);
let cluster_ids: std::collections::HashSet<&str> =
clusters.iter().map(|c| c.id.as_str()).collect();
let shapes_of = |main_flow: &[Vec<Point>]| -> Vec<Option<EdgeShape>> {
edges
.iter()
.map(|e| {
let (Some(&source), Some(&target)) = (by_id.get(e.source), by_id.get(e.target))
else {
return None;
};
Some(classify(
direction,
source,
target,
e.raw,
e.source_rank,
e.target_rank,
e.source_out_degree,
e.target_in_degree,
nodes,
&cluster_boxes,
cluster_ids.contains(e.source),
false,
e.aside,
main_flow,
))
})
.collect()
};
let shapes = shapes_of(&[]);
let shapes = if shapes.iter().flatten().any(|s| s.aside) {
let main_flow = main_flow_polylines(edges, &shapes, &by_id, points);
shapes_of(&main_flow)
} else {
shapes
};
let base_bounds = content_bounds(nodes, clusters);
let lane_of = perimeter_lanes(&by_id, edges, &shapes);
let fan_step = evict(&by_id, edges, &shapes, chain_next).fan_step;
for (edge, shape) in edges.iter().zip(&shapes) {
let Some(shape) = shape else { continue };
let (Some(&source), Some(&target)) = (by_id.get(edge.source), by_id.get(edge.target))
else {
continue;
};
if rides_the_perimeter(shape) && source.id != target.id {
let Some(pts) = points.get(edge.id) else {
continue;
};
if pts.len() < 2 {
continue;
}
let crosses_a_plate = pts.windows(2).any(|w| {
plates
.iter()
.any(|(id, plate)| id != edge.id && segment_crosses_plate(&w[0], &w[1], plate))
});
if !crosses_a_plate {
continue;
}
let Some(&lane) = lane_of.get(edge.id) else {
continue; };
let ring = expand_bounds(
base_bounds,
PERIMETER_MARGIN + lane as f64 * PERIMETER_LANE_SPACING,
);
let source_port = pts[0].clone();
let target_port = pts[pts.len() - 1].clone();
let ids = (edge.source, edge.target);
let blocked = |a: &Point, b: &Point| {
segment_crosses_any_node(a, b, nodes, ids)
|| plates
.iter()
.any(|(id, plate)| id != edge.id && segment_crosses_plate(a, b, plate))
};
let rebuilt = route_perimeter(
shape.source_side,
shape.target_side,
source_port,
target_port,
ring,
&blocked,
);
if let Some(size) = plates.get(edge.id).map(|p| p.size) {
if let Some(slot) = label_slot_clear(direction, &rebuilt, &|center| {
plate_coverage(center, size, edge.id, points, nodes, clusters)
}) {
if let Some(plate) = plates.get_mut(edge.id) {
plate.center = slot.center;
}
}
}
points.insert(edge.id.to_string(), rebuilt);
continue;
}
if shape.reverse {
continue; }
let Some(pts) = points.get(edge.id).cloned() else {
continue;
};
if pts.len() < 2 {
continue;
}
let n = pts.len();
let crosses_foreign = |a: &Point, b: &Point| {
plates
.iter()
.any(|(id, plate)| id != edge.id && segment_crosses_plate(a, b, plate))
};
let mut new_source_coord = None;
if crosses_foreign(&pts[0], &pts[1]) {
let cur = tangent_coord(shape.source_side, &pts[0]);
let occupied = ports_on_face(
source.id.as_str(),
shape.source_side,
edge.id,
edges,
&shapes,
points,
);
new_source_coord = Some(push_outward(source, shape.source_side, cur, &occupied));
}
let mut new_target_coord = None;
if crosses_foreign(&pts[n - 2], &pts[n - 1]) {
let cur = tangent_coord(shape.target_side, &pts[n - 1]);
let occupied = ports_on_face(
target.id.as_str(),
shape.target_side,
edge.id,
edges,
&shapes,
points,
);
new_target_coord = Some(push_outward(target, shape.target_side, cur, &occupied));
}
if new_source_coord.is_none() && new_target_coord.is_none() {
continue;
}
let source_coord =
new_source_coord.unwrap_or_else(|| tangent_coord(shape.source_side, &pts[0]));
let target_coord =
new_target_coord.unwrap_or_else(|| tangent_coord(shape.target_side, &pts[n - 1]));
let rebuilt = route_with_ports(
direction,
shape,
source,
target,
source_coord,
target_coord,
edge.raw,
(0.0, 0.0, 0.0, 0.0),
nodes,
fan_step.get(edge.id).copied(),
);
if let Some(size) = plates.get(edge.id).map(|p| p.size) {
if let Some(slot) = label_slot_clear(direction, &rebuilt, &|center| {
plate_coverage(center, size, edge.id, points, nodes, clusters)
}) {
if let Some(plate) = plates.get_mut(edge.id) {
plate.center = slot.center;
}
}
}
points.insert(edge.id.to_string(), rebuilt);
}
}
pub const CROSSING_GAP: f64 = 12.0;
pub(crate) fn segment_crossing(a: &[Point], b: &[Point]) -> Option<Point> {
let (a0, a1) = (&a[0], &a[1]);
let (b0, b1) = (&b[0], &b[1]);
let a_vert = (a0.x - a1.x).abs() < EPS;
let b_horiz = (b0.y - b1.y).abs() < EPS;
if a_vert && b_horiz {
let x = a0.x;
let (ay0, ay1) = (a0.y.min(a1.y), a0.y.max(a1.y));
let y = b0.y;
let (bx0, bx1) = (b0.x.min(b1.x), b0.x.max(b1.x));
if x > bx0 + EPS && x < bx1 - EPS && y > ay0 + EPS && y < ay1 - EPS {
return Some(Point::new(x, y));
}
return None;
}
let a_horiz = (a0.y - a1.y).abs() < EPS;
let b_vert = (b0.x - b1.x).abs() < EPS;
if a_horiz && b_vert {
return segment_crossing(b, a);
}
None
}
fn gap_around(points: &[Point], seg_idx: usize, cross: &Point) -> (Point, Point) {
let half = CROSSING_GAP / 2.0;
let seg_start = &points[seg_idx];
let to_cross = (cross.x - seg_start.x).hypot(cross.y - seg_start.y);
let s = super::edges::length(&points[..=seg_idx]) + to_cross;
let total = super::edges::length(points);
let lo = (s - half).max(0.0);
let hi = (s + half).min(total);
let g0 = super::edges::point_at_arc_distance(points, lo).unwrap_or_else(|| cross.clone());
let g1 = super::edges::point_at_arc_distance(points, hi).unwrap_or_else(|| cross.clone());
(g0, g1)
}
pub fn insert_crossing_gaps(
direction: Direction,
nodes: &[PlacedNode],
clusters: &[PlacedCluster],
edges: &[EligibleEdge],
points: &HashMap<String, Vec<Point>>,
) -> HashMap<String, Vec<(Point, Point)>> {
let cluster_boxes = cluster_node_boxes(clusters);
let by_id = build_by_id(nodes, &cluster_boxes);
let cluster_ids: std::collections::HashSet<&str> =
clusters.iter().map(|c| c.id.as_str()).collect();
let is_perimeter: HashMap<&str, bool> = edges
.iter()
.filter_map(|e| {
let (Some(&source), Some(&target)) = (by_id.get(e.source), by_id.get(e.target)) else {
return None;
};
let shape = classify(
direction,
source,
target,
e.raw,
e.source_rank,
e.target_rank,
e.source_out_degree,
e.target_in_degree,
nodes,
&cluster_boxes,
cluster_ids.contains(e.source),
false,
e.aside,
&[],
);
Some((
e.id,
(rides_the_perimeter(&shape) || shape.staircase) && source.id != target.id,
))
})
.collect();
let mut gaps: HashMap<String, Vec<(Point, Point)>> = HashMap::new();
for i in 0..edges.len() {
for j in (i + 1)..edges.len() {
let (ei, ej) = (edges[i].id, edges[j].id);
let (Some(pi), Some(pj)) = (points.get(ei), points.get(ej)) else {
continue;
};
let (pi_perimeter, pj_perimeter) = (
is_perimeter.get(ei).copied().unwrap_or(false),
is_perimeter.get(ej).copied().unwrap_or(false),
);
if !pi_perimeter && !pj_perimeter {
for (seg_idx, wi) in pi.windows(2).enumerate() {
for (seg_jdx, wj) in pj.windows(2).enumerate() {
let Some(cross) = segment_crossing(wi, wj) else {
continue;
};
if segment_is_vertical(&wi[0], &wi[1]) {
let (g0, g1) = gap_around(pj, seg_jdx, &cross);
gaps.entry(ej.to_string()).or_default().push((g0, g1));
} else {
let (g0, g1) = gap_around(pi, seg_idx, &cross);
gaps.entry(ei.to_string()).or_default().push((g0, g1));
}
}
}
continue;
}
let cut_on_i = if pi_perimeter && pj_perimeter {
ei > ej
} else {
pi_perimeter
};
let (cut_id, cut_pts, other_pts) = if cut_on_i { (ei, pi, pj) } else { (ej, pj, pi) };
for (seg_idx, wc) in cut_pts.windows(2).enumerate() {
for wo in other_pts.windows(2) {
if let Some(cross) = segment_crossing(wc, wo) {
let (g0, g1) = gap_around(cut_pts, seg_idx, &cross);
gaps.entry(cut_id.to_string()).or_default().push((g0, g1));
}
}
}
}
}
gaps
}
#[cfg(test)]
mod tests {
use super::*;
use crate::preview::mermaid::render::Label;
fn node(id: &str, cx: f64, cy: f64, w: f64, h: f64) -> PlacedNode {
PlacedNode {
id: id.to_string(),
shape: Glyph::default(),
center: Point::new(cx, cy),
size: Size::new(w, h),
label: Label::measure(""),
panel: None,
series: None,
mark: None,
style: None,
}
}
#[test]
fn an_aside_is_local_only_when_no_other_unit_lies_between_its_ends() {
let a = node("A", 0.0, 0.0, 40.0, 40.0);
let b = node("B", 200.0, 0.0, 40.0, 40.0);
let ends = [a.clone(), b.clone()];
assert!(
aside_route_stays_local(&a, &b, &ends, &[]),
"two boxes with nothing at all between them"
);
let between = node("S", 100.0, 0.0, 60.0, 60.0);
assert!(
!aside_route_stays_local(&a, &b, &ends, &[between]),
"a frame holding neither end is a third unit's band, and the route may not cut it"
);
let own = node("S2", 0.0, 0.0, 80.0, 80.0);
assert!(
aside_route_stays_local(&a, &b, &ends, &[own]),
"a frame holding one of the two ends is that end's own band, not something in the way"
);
let third = node("C", 100.0, 0.0, 40.0, 40.0);
assert!(
!aside_route_stays_local(&a, &b, &[a.clone(), b.clone(), third], &[]),
"a third node between the two ends"
);
}
#[test]
fn label_slot_takes_a_clear_segment_over_a_better_shaped_covered_one() {
let pts = vec![
Point::new(0.0, 0.0),
Point::new(0.0, 100.0),
Point::new(60.0, 100.0),
Point::new(60.0, 150.0),
];
let covered = |c: &Point| usize::from((c.x - 0.0).abs() < 1.0 && (c.y - 50.0).abs() < 1.0);
let slot =
label_slot_clear(Direction::TopToBottom, &pts, &covered).expect("must return a slot");
assert!(
(slot.center.x - 60.0).abs() < 1e-9 && (slot.center.y - 125.0).abs() < 1e-9,
"the clear leg must win over the longer covered one: {:?}",
slot.center
);
let slot = label_slot(Direction::TopToBottom, &pts).expect("must return a slot");
assert!(
(slot.center.x - 0.0).abs() < 1e-9 && (slot.center.y - 50.0).abs() < 1e-9,
"with nothing in the way the longest flow-axis leg still wins: {:?}",
slot.center
);
}
#[test]
fn label_slot_breaks_an_exact_length_tie_by_distance_to_the_arc_midpoint() {
let pts = vec![
Point::new(0.0, 0.0),
Point::new(0.0, 50.0),
Point::new(40.0, 50.0),
Point::new(40.0, 100.0),
Point::new(140.0, 100.0),
];
let slot = label_slot(Direction::TopToBottom, &pts).expect("must return a slot");
assert!(
(slot.center.x - 40.0).abs() < 1e-9 && (slot.center.y - 75.0).abs() < 1e-9,
"the tied leg nearer the arc midpoint must win: {:?}",
slot.center
);
}
#[test]
fn plate_coverage_counts_a_foreign_line_a_node_box_and_a_frame_border() {
let size = Size::new(40.0, 20.0);
let at = Point::new(100.0, 100.0);
let mut routes: HashMap<String, Vec<Point>> = HashMap::new();
routes.insert(
"own".to_string(),
vec![Point::new(0.0, 100.0), Point::new(200.0, 100.0)],
);
assert_eq!(
plate_coverage(&at, size, "own", &routes, &[], &[]),
0,
"a plate always sits on its own line — that is what 線上プレート means"
);
routes.insert(
"other".to_string(),
vec![Point::new(100.0, 0.0), Point::new(100.0, 200.0)],
);
assert_eq!(
plate_coverage(&at, size, "own", &routes, &[], &[]),
1,
"a foreign line under the plate counts"
);
let box_node = node("N", 100.0, 100.0, 30.0, 30.0);
assert_eq!(
plate_coverage(
&at,
size,
"own",
&routes,
std::slice::from_ref(&box_node),
&[]
),
2,
"a node box under the plate counts too — nodes are painted over edges"
);
let frame = |cx: f64, cy: f64, w: f64, h: f64| PlacedCluster {
id: "F".to_string(),
title: Label::measure(""),
center: Point::new(cx, cy),
size: Size::new(w, h),
parent: None,
depth: 0,
dashed: false,
filled: true,
sections: Vec::new(),
title_strip: false,
};
assert_eq!(
plate_coverage(
&at,
size,
"own",
&routes,
&[],
&[frame(100.0, 0.0, 400.0, 220.0)]
),
2,
"a frame border under the plate counts"
);
assert_eq!(
plate_coverage(
&at,
size,
"own",
&routes,
&[],
&[frame(100.0, 100.0, 400.0, 400.0)]
),
1,
"a frame that merely holds the plate does not"
);
}
#[test]
fn label_slot_prefers_the_flow_axis_segment_even_when_a_cross_axis_one_is_longer() {
let pts = vec![
Point::new(0.0, 0.0),
Point::new(0.0, 10.0),
Point::new(200.0, 10.0),
];
let slot = label_slot(Direction::TopToBottom, &pts).expect("2+ points must return a slot");
assert!(
slot.is_flow_axis,
"{slot:?}",
slot = (slot.center, slot.length)
);
assert!(
(slot.length - 10.0).abs() < 1e-9,
"must pick the 10px flow-axis leg, not the 200px cross-axis one: {}",
slot.length
);
assert!((slot.center.x - 0.0).abs() < 1e-9 && (slot.center.y - 5.0).abs() < 1e-9);
}
#[test]
fn label_slot_picks_the_longer_of_two_flow_axis_segments() {
let pts = vec![
Point::new(0.0, 0.0),
Point::new(0.0, 30.0),
Point::new(20.0, 30.0),
Point::new(20.0, 130.0),
];
let slot = label_slot(Direction::TopToBottom, &pts).expect("must return a slot");
assert!(slot.is_flow_axis);
assert!((slot.length - 100.0).abs() < 1e-9, "{}", slot.length);
assert!((slot.center.x - 20.0).abs() < 1e-9 && (slot.center.y - 80.0).abs() < 1e-9);
let pts = vec![
Point::new(0.0, 0.0),
Point::new(0.0, 200.0), Point::new(20.0, 200.0), Point::new(20.0, 230.0), Point::new(270.0, 230.0), ];
let slot = label_slot(Direction::TopToBottom, &pts).expect("must return a slot");
assert!(
(slot.length - 200.0).abs() < 1e-9
&& (slot.center.x - 0.0).abs() < 1e-9
&& (slot.center.y - 100.0).abs() < 1e-9,
"the longer flow-axis leg wins even when a shorter one sits nearer the midpoint: \
length {} at {:?}",
slot.length,
slot.center
);
}
#[test]
fn label_slot_falls_back_to_a_cross_axis_segment_when_no_flow_axis_leg_exists() {
let pts = vec![Point::new(0.0, 0.0), Point::new(50.0, 0.0)];
let slot = label_slot(Direction::TopToBottom, &pts).expect("must return a slot");
assert!(!slot.is_flow_axis);
assert!(
slot.horizontal,
"a horizontal-only polyline must report horizontal=true"
);
}
#[test]
fn label_slot_handles_a_single_point_defensively() {
let pts = vec![Point::new(5.0, 5.0)];
let slot = label_slot(Direction::TopToBottom, &pts).expect("a single point is Some");
assert_eq!(slot.length, 0.0);
assert_eq!(slot.center, Point::new(5.0, 5.0));
}
#[test]
fn label_min_length_uses_width_for_a_horizontal_segment_and_height_for_a_vertical_one() {
let plate = Size::new(100.0, 20.0);
assert!((label_min_length(plate, true) - (100.0 + 2.0 * LABEL_CLEARANCE)).abs() < 1e-9);
assert!((label_min_length(plate, false) - (20.0 + 2.0 * LABEL_CLEARANCE)).abs() < 1e-9);
}
#[test]
fn safe_ring_exit_l_shape_stops_at_the_ring_not_the_far_corner() {
let ring = (0.0, 0.0, 600.0, 400.0);
for side in [Side::Top, Side::Bottom, Side::Left, Side::Right] {
let port = match side {
Side::Top => Point::new(300.0, 50.0),
Side::Bottom => Point::new(300.0, 350.0),
Side::Left => Point::new(50.0, 200.0),
Side::Right => Point::new(550.0, 200.0),
};
let direct = ring_touch(side, &port, ring);
let blocked = |a: &Point, b: &Point| *a == port && *b == direct;
let exit = safe_ring_exit(side, &port, ring, &blocked);
assert_eq!(
exit.len(),
2,
"{side:?}: the L-shaped fallback must be exactly [hop, ring-touch], not a third \
leg out to the far corner: {exit:?}"
);
let touch = &exit[1];
match side {
Side::Top | Side::Bottom => {
assert!(
(touch.y - exit[0].y).abs() < 1e-9,
"{side:?}: the ring touch point must stay at the hop's own y, not travel \
on to direct's ({}): {touch:?}",
direct.y
);
}
Side::Left | Side::Right => {
assert!(
(touch.x - exit[0].x).abs() < 1e-9,
"{side:?}: the ring touch point must stay at the hop's own x, not travel \
on to direct's ({}): {touch:?}",
direct.x
);
}
}
}
}
#[test]
fn route_perimeter_never_retraces_a_leg_it_just_drew() {
let ring = (0.0, 0.0, 200.0, 400.0);
let source_port = Point::new(120.0, 300.0);
let target_port = Point::new(120.0, 250.0);
let blocked =
|a: &Point, b: &Point| (a.x - 120.0).abs() < 1e-9 && (b.x - ring.2).abs() < 1e-9;
let route = route_perimeter(
Side::Right,
Side::Right,
source_port.clone(),
target_port.clone(),
ring,
&blocked,
);
for w in route.windows(3) {
let (a, b, c) = (&w[0], &w[1], &w[2]);
let dot = (b.x - a.x) * (c.x - b.x) + (b.y - a.y) * (c.y - b.y);
let cross = (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
assert!(
!(dot < -EPS && cross.abs() < EPS),
"the route doubles straight back at {b:?}: {route:?}"
);
}
assert_eq!(route.first(), Some(&source_port), "{route:?}");
assert_eq!(route.last(), Some(&target_port), "{route:?}");
assert_eq!(route.len(), 4, "{route:?}");
}
#[test]
fn collapse_retraced_removes_a_doubling_back_even_through_a_duplicated_point() {
let mut pts = vec![
Point::new(0.0, 100.0),
Point::new(8.0, 100.0),
Point::new(8.0, 200.0),
Point::new(8.0, 200.0),
Point::new(8.0, 20.0),
Point::new(0.0, 20.0),
];
collapse_retraced(&mut pts);
assert_eq!(
pts,
vec![
Point::new(0.0, 100.0),
Point::new(8.0, 100.0),
Point::new(8.0, 20.0),
Point::new(0.0, 20.0),
]
);
let mut plain = vec![
Point::new(0.0, 0.0),
Point::new(50.0, 0.0),
Point::new(50.0, 80.0),
];
let before = plain.clone();
collapse_retraced(&mut plain);
assert_eq!(plain, before);
}
#[test]
fn perimeter_l_shape_fallback_spans_only_the_ports_own_separation_in_every_direction() {
for direction in [
Direction::TopToBottom,
Direction::BottomToTop,
Direction::LeftToRight,
Direction::RightToLeft,
] {
let (hi, lo, mid) = match direction {
Direction::TopToBottom | Direction::BottomToTop => (
node("hi", 100.0, 0.0, 60.0, 40.0),
node("lo", 100.0, 300.0, 60.0, 40.0),
node("mid", 100.0, 150.0, 60.0, 40.0),
),
Direction::LeftToRight | Direction::RightToLeft => (
node("hi", 0.0, 100.0, 40.0, 60.0),
node("lo", 300.0, 100.0, 40.0, 60.0),
node("mid", 150.0, 100.0, 40.0, 60.0),
),
};
let nodes = vec![hi.clone(), lo.clone(), mid.clone()];
let raw = vec![lo.center.clone(), mid.center.clone(), hi.center.clone()];
let edges = vec![EligibleEdge {
id: "back",
source: "lo",
target: "hi",
raw: &raw,
source_rank: Some(1),
target_rank: Some(0),
source_out_degree: 1,
target_in_degree: 1,
aside: false,
}];
let routed = route_flowchart(
direction,
&nodes,
&[],
&edges,
&std::collections::HashMap::new(),
false,
);
let pts = &routed.points["back"];
for w in pts.windows(2) {
let dx = (w[1].x - w[0].x).abs();
let dy = (w[1].y - w[0].y).abs();
assert!(
dx < 1e-9 || dy < 1e-9,
"{direction:?}: perimeter route must stay axis-parallel: {w:?}"
);
}
let longest = pts
.windows(2)
.map(|w| (w[1].x - w[0].x).hypot(w[1].y - w[0].y))
.fold(0.0_f64, f64::max);
let needed = match direction {
Direction::TopToBottom | Direction::BottomToTop => {
(lo.center.y - hi.center.y).abs()
}
Direction::LeftToRight | Direction::RightToLeft => {
(lo.center.x - hi.center.x).abs()
}
};
assert!(
longest <= needed + 1.0,
"{direction:?}: the ring run is {longest}px, more than the ~{needed}px the two \
ports actually need — the far-corner bug is back: {pts:?}"
);
}
}
#[test]
fn avoid_label_plates_ignores_a_self_loop() {
let a = node("A", 100.0, 100.0, 60.0, 40.0);
let nodes = vec![a];
let raw = vec![
Point::new(130.0, 90.0),
Point::new(160.0, 90.0),
Point::new(160.0, 110.0),
Point::new(130.0, 110.0),
];
let edges = vec![EligibleEdge {
id: "loop",
source: "A",
target: "A",
raw: &raw,
source_rank: Some(0),
target_rank: Some(0),
source_out_degree: 2,
target_in_degree: 2,
aside: false,
}];
let routed = route_flowchart(
Direction::TopToBottom,
&nodes,
&[],
&edges,
&std::collections::HashMap::new(),
false,
);
let mut points = routed.points;
let before = points["loop"].clone();
let mut plates: HashMap<String, PlacedEdgeLabel> = HashMap::new();
plates.insert(
"someone-elses-label".to_string(),
PlacedEdgeLabel {
center: Point::new(100.0, 100.0),
size: Size::new(400.0, 400.0),
label: Label::measure("x"),
},
);
avoid_label_plates(
Direction::TopToBottom,
&nodes,
&[],
&edges,
&mut points,
&mut plates,
&std::collections::HashMap::new(),
);
assert_eq!(points["loop"], before, "a self-loop must never be rebuilt");
}
#[test]
fn avoid_label_plates_reroutes_a_perimeter_edge_off_a_plate_it_can_actually_clear() {
let a = node("A", 100.0, 0.0, 60.0, 40.0);
let d = node("D", 100.0, 200.0, 60.0, 40.0);
let nodes = vec![a, d];
let raw = vec![
Point::new(100.0, 180.0),
Point::new(100.0, 100.0),
Point::new(100.0, 20.0),
];
let edges = vec![EligibleEdge {
id: "da",
source: "D",
target: "A",
raw: &raw,
source_rank: Some(2),
target_rank: Some(0),
source_out_degree: 1,
target_in_degree: 1,
aside: false,
}];
let routed = route_flowchart(
Direction::TopToBottom,
&nodes,
&[],
&edges,
&std::collections::HashMap::new(),
false,
);
let mut points = routed.points;
let mut plates: HashMap<String, PlacedEdgeLabel> = HashMap::new();
plates.insert(
"b-labels-edge".to_string(),
PlacedEdgeLabel {
center: Point::new(100.0, 100.0),
size: Size::new(80.0, 20.0),
label: Label::measure("x"),
},
);
let crosses_plate = |pts: &[Point], plate: &PlacedEdgeLabel| {
pts.windows(2)
.any(|w| segment_crosses_plate(&w[0], &w[1], plate))
};
assert!(
crosses_plate(&points["da"], &plates["b-labels-edge"]),
"fixture must reproduce the bug before the fix runs: {:?}",
points["da"]
);
avoid_label_plates(
Direction::TopToBottom,
&nodes,
&[],
&edges,
&mut points,
&mut plates,
&std::collections::HashMap::new(),
);
assert!(
!crosses_plate(&points["da"], &plates["b-labels-edge"]),
"the rerouted line must actually clear the plate: {:?}",
points["da"]
);
for w in points["da"].windows(2) {
let dx = (w[1].x - w[0].x).abs();
let dy = (w[1].y - w[0].y).abs();
assert!(
dx < 1e-9 || dy < 1e-9,
"rerouted line must stay axis-parallel: {w:?}"
);
}
}
#[test]
fn avoid_label_plates_pushes_a_staircase_forward_edges_port_off_a_plate() {
let a = node("A", 42.6689453125, 30.7, 69.337890625, 45.4);
let b = node("B", 42.6689453125, 137.76666666666668, 69.337890625, 45.4);
let c = node("C", 102.39306640625, 30.7, 190.1103515625, 45.4);
let d = node(
"D",
162.39306640625,
137.76666666666668,
70.1103515625,
45.4,
);
let nodes = vec![a, b, c, d];
let edges = vec![EligibleEdge {
id: "ad",
source: "A",
target: "D",
raw: &[],
source_rank: Some(0),
target_rank: Some(1),
source_out_degree: 2,
target_in_degree: 2,
aside: false,
}];
let shape = classify(
Direction::LeftToRight,
&nodes[0],
&nodes[3],
&[],
Some(0),
Some(1),
2,
2,
&nodes,
&[],
false,
false,
false,
&[],
);
assert!(
shape.staircase,
"the fixture must actually reach `staircase` (both the branch and the merge attempt \
must cross `C`'s box): {shape:?}"
);
let source_port = port_at(
&nodes[0],
shape.source_side,
face_center_coord(&nodes[0], shape.source_side),
PORT_INSET,
);
let target_port = port_at(
&nodes[3],
shape.target_side,
face_center_coord(&nodes[3], shape.target_side),
PORT_INSET,
);
let before = bridge(
Direction::LeftToRight,
&source_port,
&target_port,
shape.source_axis,
shape.target_axis,
);
let before: Vec<Point> = std::iter::once(source_port.clone()).chain(before).collect();
let mut points: HashMap<String, Vec<Point>> = HashMap::new();
points.insert("ad".to_string(), before.clone());
let stub_mid = Point::new(
(before[0].x + before[1].x) / 2.0,
(before[0].y + before[1].y) / 2.0,
);
let mut plates: HashMap<String, PlacedEdgeLabel> = HashMap::new();
plates.insert(
"someone-elses-label".to_string(),
PlacedEdgeLabel {
center: stub_mid,
size: Size::new(40.0, 20.0),
label: Label::measure("x"),
},
);
let crosses_plate = |pts: &[Point], plate: &PlacedEdgeLabel| {
pts.windows(2)
.any(|w| segment_crosses_plate(&w[0], &w[1], plate))
};
assert!(
crosses_plate(&before, &plates["someone-elses-label"]),
"fixture must reproduce the crossing before the fix runs: {before:?}"
);
avoid_label_plates(
Direction::LeftToRight,
&nodes,
&[],
&edges,
&mut points,
&mut plates,
&std::collections::HashMap::new(),
);
assert_ne!(
points["ad"], before,
"the staircase edge's port must actually move: {:?}",
points["ad"]
);
assert!(
!crosses_plate(&points["ad"], &plates["someone-elses-label"]),
"the rerouted staircase line must clear the plate: {:?}",
points["ad"]
);
for w in points["ad"].windows(2) {
let dx = (w[1].x - w[0].x).abs();
let dy = (w[1].y - w[0].y).abs();
assert!(
dx < 1e-9 || dy < 1e-9,
"rerouted line must stay axis-parallel: {w:?}"
);
}
}
#[test]
fn dominant_face_at_exactly_45_degrees_prefers_the_flow_face() {
let center = Point::new(0.0, 0.0);
let reference = Point::new(50.0, 50.0); assert_eq!(
dominant_face(Direction::TopToBottom, ¢er, &reference),
Side::Bottom,
"an exact 45° tie must resolve to the flow face (Bottom, since dflow >= 0), not the \
cross face (Right)"
);
assert_eq!(
dominant_face(Direction::LeftToRight, ¢er, &reference),
Side::Right,
"the same 45° tie under LR must resolve to the flow face (Right), not the cross face \
(Bottom)"
);
}
#[test]
fn safe_ring_exit_l_shape_tie_prefers_the_first_side_named_in_the_near_far_pair() {
let ring = (0.0, 0.0, 600.0, 400.0);
let port = Point::new(300.0, 50.0); let direct = ring_touch(Side::Top, &port, ring);
let blocked = |a: &Point, b: &Point| *a == port && *b == direct;
let exit = safe_ring_exit(Side::Top, &port, ring, &blocked);
assert_eq!(exit.len(), 2, "must take the L-shaped fallback: {exit:?}");
assert!(
(exit[1].x - ring.0).abs() < 1e-9,
"an exact near/far tie must resolve to the ring's LEFT side (tried first), not the \
right: {exit:?}"
);
}
#[test]
fn label_slot_keeps_the_first_segment_on_an_exact_length_tie() {
let pts = vec![
Point::new(0.0, 0.0),
Point::new(0.0, 50.0), Point::new(20.0, 50.0), Point::new(20.0, 100.0), ];
let slot = label_slot(Direction::TopToBottom, &pts).expect("must return a slot");
assert!(slot.is_flow_axis);
assert!((slot.length - 50.0).abs() < 1e-9, "{}", slot.length);
assert!(
(slot.center.x - 0.0).abs() < 1e-9 && (slot.center.y - 25.0).abs() < 1e-9,
"an exact-length tie must keep the FIRST segment (centre (0,25)), not the second \
(centre (20,75)): {:?}",
slot.center
);
}
#[test]
fn perimeter_lanes_are_assigned_by_edge_id_not_declaration_order() {
let a = node("A", 0.0, 0.0, 40.0, 30.0);
let b = node("B", 0.0, 200.0, 40.0, 30.0);
let by_id: HashMap<&str, &PlacedNode> = [("A", &a), ("B", &b)].into_iter().collect();
let edges = vec![
EligibleEdge {
id: "b_edge",
source: "B",
target: "A",
raw: &[],
source_rank: Some(2),
target_rank: Some(0),
source_out_degree: 1,
target_in_degree: 1,
aside: false,
},
EligibleEdge {
id: "a_edge",
source: "B",
target: "A",
raw: &[],
source_rank: Some(2),
target_rank: Some(0),
source_out_degree: 1,
target_in_degree: 1,
aside: false,
},
];
let back_shape = EdgeShape {
reverse: true,
self_loop_fixed: false,
aligned: false,
staircase: false,
fan_lane: false,
rank_lane_bend: None,
cross_lane_bend: None,
aside: false,
source_side: Side::Top,
source_axis: Axis::Cross,
target_side: Side::Bottom,
target_axis: Axis::Cross,
};
let shapes = vec![Some(back_shape), Some(back_shape)];
let lanes = perimeter_lanes(&by_id, &edges, &shapes);
assert_eq!(
lanes.get("a_edge").copied(),
Some(0),
"the alphabetically-smaller edge id must get lane 0 regardless of declaration order: \
{lanes:?}"
);
assert_eq!(lanes.get("b_edge").copied(), Some(1), "{lanes:?}");
}
#[test]
fn push_outward_stands_still_rather_than_step_over_a_sibling() {
let a = node("A", 0.0, 0.0, 200.0, 40.0);
let occupied = [-PORT_SPACING, PORT_SPACING];
let pushed = push_outward(&a, Side::Bottom, 0.0, &occupied);
assert_eq!(
pushed, 0.0,
"a blocked nudge must keep its own coordinate, never hop over {occupied:?}"
);
}
#[test]
fn push_outward_never_reorders_a_dense_face() {
let a = node("A", 0.0, 0.0, 400.0, 40.0);
for n in 1..=9usize {
let offsets: Vec<f64> = (0..n)
.map(|i| (i as f64 - (n as f64 - 1.0) / 2.0) * PORT_SPACING)
.collect();
for &cur in &offsets {
let occupied: Vec<f64> = offsets.iter().copied().filter(|&o| o != cur).collect();
let pushed = push_outward(&a, Side::Bottom, cur, &occupied);
assert!(
occupied.iter().all(|&o| (o - pushed).abs() > EPS),
"n={n} cur={cur}: pushed {pushed} collided with {occupied:?}"
);
assert!(
occupied
.iter()
.all(|&o| (o < cur) == (o < pushed) && (o > cur) == (o > pushed)),
"n={n} cur={cur}: pushed {pushed} stepped over a sibling in {occupied:?}"
);
}
}
}
#[test]
fn push_outward_gives_up_rather_than_leave_the_nodes_flat_run() {
let a = node("A", 0.0, 0.0, 20.0, 40.0); let pushed = push_outward(&a, Side::Bottom, 0.0, &[]);
assert_eq!(pushed, 0.0, "must give up and keep the original coordinate");
}
#[test]
fn ports_on_face_reads_only_the_named_face_excluding_the_edge_itself() {
let a = node("A", 100.0, 100.0, 200.0, 40.0);
let b = node("B", 100.0, 200.0, 60.0, 40.0);
let c = node("C", 100.0, 200.0, 60.0, 40.0);
let d = node("D", 250.0, 100.0, 60.0, 40.0);
let nodes = [a, b, c, d];
let make_edge = |id, target| EligibleEdge {
id,
source: "A",
target,
raw: &[] as &[Point],
source_rank: Some(0),
target_rank: Some(1),
source_out_degree: 3,
target_in_degree: 1,
aside: false,
};
let edges = vec![
make_edge("ab", "B"),
make_edge("ac", "C"),
make_edge("ad", "D"),
];
let shapes: Vec<Option<EdgeShape>> = vec![
Some(EdgeShape {
reverse: false,
self_loop_fixed: false,
aligned: false,
staircase: false,
fan_lane: false,
rank_lane_bend: None,
cross_lane_bend: None,
aside: false,
source_side: Side::Bottom,
source_axis: Axis::Cross,
target_side: Side::Top,
target_axis: Axis::Cross,
}),
Some(EdgeShape {
reverse: false,
self_loop_fixed: false,
aligned: false,
staircase: false,
fan_lane: false,
rank_lane_bend: None,
cross_lane_bend: None,
aside: false,
source_side: Side::Bottom,
source_axis: Axis::Cross,
target_side: Side::Top,
target_axis: Axis::Cross,
}),
Some(EdgeShape {
reverse: false,
self_loop_fixed: false,
aligned: false,
staircase: false,
fan_lane: false,
rank_lane_bend: None,
cross_lane_bend: None,
aside: false,
source_side: Side::Right,
source_axis: Axis::Flow,
target_side: Side::Left,
target_axis: Axis::Flow,
}),
];
let mut points: HashMap<String, Vec<Point>> = HashMap::new();
points.insert(
"ab".to_string(),
vec![Point::new(84.0, 120.0), Point::new(84.0, 180.0)],
);
points.insert(
"ac".to_string(),
vec![Point::new(116.0, 120.0), Point::new(116.0, 180.0)],
);
points.insert(
"ad".to_string(),
vec![Point::new(200.0, 100.0), Point::new(220.0, 100.0)],
);
let occupied = ports_on_face(&nodes[0].id, Side::Bottom, "ac", &edges, &shapes, &points);
assert_eq!(
occupied,
vec![84.0],
"must see `ab`'s Bottom port, not `ac` (excluded) or `ad` (a different face)"
);
}
#[test]
fn routing_parse_is_permissive() {
assert_eq!(Routing::parse("konoma-orthogonal"), Routing::Orthogonal);
assert_eq!(Routing::parse("splines"), Routing::Splines);
assert_eq!(Routing::parse(""), Routing::Splines);
assert_eq!(Routing::parse("Orthogonal"), Routing::Splines);
assert_eq!(Routing::parse("orthogonal"), Routing::Splines);
assert_eq!(Routing::parse("xyz"), Routing::Splines);
}
#[test]
fn aligned_lr_edge_is_a_straight_two_point_line() {
let a = node("A", 0.0, 100.0, 80.0, 40.0);
let b = node("B", 200.0, 100.0, 80.0, 40.0);
let pts = route_edge(Direction::LeftToRight, &a, &b, &[], Some(0), Some(1), 1, 1);
assert_eq!(pts.len(), 2);
assert!((pts[0].y - pts[1].y).abs() < 1e-9, "flat: {pts:?}");
assert!(pts[0].x > 0.0 && pts[0].x < pts[1].x, "{pts:?}");
}
#[test]
fn branch_lr_edge_bends_once_and_lands_perpendicular() {
let a = node("A", 0.0, 0.0, 80.0, 40.0);
let b = node("B", 200.0, 100.0, 80.0, 40.0);
let pts = route_edge(Direction::LeftToRight, &a, &b, &[], Some(0), Some(1), 2, 1);
assert_eq!(pts.len(), 3, "{pts:?}");
assert!((pts[0].x - pts[1].x).abs() < 1e-9, "{pts:?}");
assert!((pts[1].y - pts[2].y).abs() < 1e-9, "{pts:?}");
}
#[test]
fn merge_lr_edge_now_bends_twice_entering_the_flow_axis_face() {
let a = node("A", 0.0, 0.0, 80.0, 40.0);
let b = node("B", 200.0, 100.0, 80.0, 40.0);
let pts = route_edge(Direction::LeftToRight, &a, &b, &[], Some(0), Some(1), 1, 2);
assert_eq!(pts.len(), 4, "{pts:?}");
assert!((pts[0].y - pts[1].y).abs() < 1e-9, "{pts:?}");
assert!((pts[1].x - pts[2].x).abs() < 1e-9, "{pts:?}");
assert!((pts[1].x - 100.0).abs() < 1e-9, "{pts:?}");
assert!((pts[2].y - pts[3].y).abs() < 1e-9, "{pts:?}");
}
#[test]
fn reverse_edge_is_detected_by_rank_and_stays_axis_parallel() {
let a = node("A", 200.0, 0.0, 80.0, 40.0);
let b = node("B", 0.0, 0.0, 80.0, 40.0);
let raw = vec![
Point::new(160.0, 0.0),
Point::new(100.0, -60.0),
Point::new(40.0, 0.0),
];
let pts = route_edge(Direction::LeftToRight, &a, &b, &raw, Some(2), Some(0), 1, 1);
assert!(pts.len() >= 2);
for w in pts.windows(2) {
let dx = (w[1].x - w[0].x).abs();
let dy = (w[1].y - w[0].y).abs();
assert!(dx < 1e-9 || dy < 1e-9, "diagonal segment: {w:?}");
}
}
#[test]
fn all_four_directions_produce_only_axis_parallel_segments() {
for direction in [
Direction::TopToBottom,
Direction::BottomToTop,
Direction::LeftToRight,
Direction::RightToLeft,
] {
let a = node("A", 0.0, 0.0, 80.0, 40.0);
let b = node("B", 150.0, 90.0, 80.0, 40.0);
for (sr, tr, out_d, in_d) in [(0, 1, 1, 1), (0, 1, 2, 1), (0, 1, 1, 2), (1, 0, 1, 1)] {
let pts = route_edge(direction, &a, &b, &[], Some(sr), Some(tr), out_d, in_d);
for w in pts.windows(2) {
let dx = (w[1].x - w[0].x).abs();
let dy = (w[1].y - w[0].y).abs();
assert!(
dx < 1e-9 || dy < 1e-9,
"{direction:?} sr={sr} tr={tr}: diagonal segment {w:?}"
);
}
}
}
}
fn route_all<'a>(
direction: Direction,
nodes: &[PlacedNode],
edges: &[EligibleEdge<'a>],
) -> RoutedFlowchart {
route_flowchart(
direction,
nodes,
&[],
edges,
&std::collections::HashMap::new(),
false,
)
}
fn three_branches_into<'a>(target: &'a str) -> Vec<EligibleEdge<'a>> {
vec![
EligibleEdge {
id: "e1",
source: "X",
target,
raw: &[],
source_rank: Some(0),
target_rank: Some(1),
source_out_degree: 2,
target_in_degree: 3,
aside: false,
},
EligibleEdge {
id: "e2",
source: "Y",
target,
raw: &[],
source_rank: Some(0),
target_rank: Some(1),
source_out_degree: 2,
target_in_degree: 3,
aside: false,
},
EligibleEdge {
id: "e3",
source: "Z",
target,
raw: &[],
source_rank: Some(0),
target_rank: Some(1),
source_out_degree: 2,
target_in_degree: 3,
aside: false,
},
]
}
#[test]
fn three_incoming_edges_get_16px_ports_symmetric_about_the_face_and_clear_of_corners() {
let target = node("T", 500.0, 300.0, 300.0, 60.0);
let x = node("X", 50.0, 50.0, 60.0, 40.0);
let y = node("Y", 950.0, 150.0, 60.0, 40.0);
let z = node("Z", 1400.0, 250.0, 60.0, 40.0);
let nodes = vec![target.clone(), x.clone(), y.clone(), z.clone()];
let edges = three_branches_into("T");
let routed = route_all(Direction::TopToBottom, &nodes, &edges);
let tip_x = routed.points["e1"].last().unwrap().x;
let tip_y = routed.points["e2"].last().unwrap().x;
let tip_z = routed.points["e3"].last().unwrap().x;
let mut xs = [tip_x, tip_y, tip_z];
xs.sort_by(|a, b| a.partial_cmp(b).unwrap());
assert!((xs[1] - target.center.x).abs() < 1e-9, "{xs:?}");
assert!((xs[1] - xs[0] - PORT_SPACING).abs() < 1e-9, "{xs:?}");
assert!((xs[2] - xs[1] - PORT_SPACING).abs() < 1e-9, "{xs:?}");
assert!(tip_x < tip_y && tip_y < tip_z, "{tip_x} {tip_y} {tip_z}");
let half_width = target.size.w / 2.0;
for x in xs {
let from_center = (x - target.center.x).abs();
assert!(
half_width - from_center >= PORT_CLEARANCE - 1e-9,
"port at {from_center}px from centre must clear the corner by {PORT_CLEARANCE}px \
(half-width {half_width}): {xs:?}"
);
}
}
#[test]
fn an_aligned_edge_keeps_the_centre_port_and_siblings_move_outward() {
let a = node("A", 300.0, 0.0, 60.0, 40.0);
let b = node("B", 300.0, 200.0, 60.0, 40.0);
let c = node("C", 100.0, 70.0, 60.0, 40.0);
let d = node("D", 500.0, 140.0, 60.0, 40.0);
let nodes = vec![a.clone(), b.clone(), c.clone(), d.clone()];
let edges = vec![
EligibleEdge {
id: "ab",
source: "A",
target: "B",
raw: &[],
source_rank: Some(0),
target_rank: Some(1),
source_out_degree: 1,
target_in_degree: 3,
aside: false,
},
EligibleEdge {
id: "cb",
source: "C",
target: "B",
raw: &[],
source_rank: Some(0),
target_rank: Some(1),
source_out_degree: 2,
target_in_degree: 3,
aside: false,
},
EligibleEdge {
id: "db",
source: "D",
target: "B",
raw: &[],
source_rank: Some(0),
target_rank: Some(1),
source_out_degree: 2,
target_in_degree: 3,
aside: false,
},
];
let routed = route_all(Direction::TopToBottom, &nodes, &edges);
let ab_tip = routed.points["ab"].last().unwrap();
let cb_tip = routed.points["cb"].last().unwrap();
let db_tip = routed.points["db"].last().unwrap();
assert!(
(ab_tip.x - b.center.x).abs() < 1e-9,
"the aligned edge must keep the centre port: {ab_tip:?}"
);
for (name, tip) in [("cb", cb_tip), ("db", db_tip)] {
assert!(
(tip.x - b.center.x).abs() > 1e-9,
"{name}: the branching sibling must not share the centre port: {tip:?}"
);
assert!(
((tip.x - b.center.x).abs() - PORT_SPACING).abs() < 1e-9,
"{name}: the sibling must sit exactly one port-spacing away: {tip:?}"
);
}
}
#[test]
fn a_chain_selected_trunk_keeps_the_centre_port_even_when_geometry_never_aligned_it() {
let s = node("S", 100.0, 200.0, 60.0, 40.0);
let t = node("T", 400.0, 600.0, 60.0, 40.0); let u = node("U", 400.0, 120.0, 60.0, 40.0);
let v = node("V", 400.0, 180.0, 60.0, 40.0);
let w = node("W", 400.0, 240.0, 60.0, 40.0);
let nodes = vec![s.clone(), t.clone(), u.clone(), v.clone(), w.clone()];
let edge = |id: &'static str, target: &'static str| EligibleEdge {
id,
source: "S",
target,
raw: &[],
source_rank: Some(0),
target_rank: Some(1),
source_out_degree: 4,
target_in_degree: 1,
aside: false,
};
let edges = vec![
edge("st", "T"),
edge("su", "U"),
edge("sv", "V"),
edge("sw", "W"),
];
let mut chain_next = HashMap::new();
chain_next.insert("S".to_string(), "T".to_string());
let routed = route_flowchart(
Direction::LeftToRight,
&nodes,
&[],
&edges,
&chain_next,
false,
);
let st_port = routed.points["st"].first().unwrap();
assert!(
(st_port.y - s.center.y).abs() < 1e-9,
"the chain-selected trunk (S->T) must keep S's own face centre even though T is not \
geometrically aligned: {st_port:?}"
);
for (name, id) in [("su", "su"), ("sv", "sv"), ("sw", "sw")] {
let port = routed.points[id].first().unwrap();
assert!(
(port.y - s.center.y).abs() > 1e-9,
"{name}: a non-trunk sibling must not also claim the centre port: {port:?}"
);
}
}
#[test]
fn a_faces_port_order_follows_the_axis_that_face_distributes_on() {
let a = node("A", 300.0, 300.0, 200.0, 40.0);
let p = node("P", 100.0, 100.0, 40.0, 40.0);
let q = node("Q", 500.0, 100.0, 40.0, 40.0);
let nodes = [a.clone(), p.clone(), q.clone()];
let by_id: HashMap<&str, &PlacedNode> = nodes.iter().map(|n| (n.id.as_str(), n)).collect();
let into_top = EdgeShape {
reverse: false,
self_loop_fixed: false,
aligned: false,
staircase: false,
fan_lane: false,
rank_lane_bend: None,
cross_lane_bend: None,
aside: false,
source_side: Side::Bottom,
source_axis: Axis::Cross,
target_side: Side::Top,
target_axis: Axis::Cross,
};
let edge = |id: &'static str, source: &'static str| EligibleEdge {
id,
source,
target: "A",
raw: &[],
source_rank: Some(0),
target_rank: Some(1),
source_out_degree: 1,
target_in_degree: 2,
aside: false,
};
let edges = vec![edge("zz", "P"), edge("aa", "Q")];
let shapes = vec![Some(into_top), Some(into_top)];
let eviction = evict(&by_id, &edges, &shapes, &HashMap::new());
let (from_p, from_q) = (eviction.target_coord["zz"], eviction.target_coord["aa"]);
assert!(
from_p < from_q,
"the port for the edge from P (x=100) must sit before the one from Q (x=500) along \
the face's own axis: P at {from_p}, Q at {from_q}"
);
}
#[test]
fn a_narrow_node_grows_to_fit_its_ports_and_a_roomy_one_does_not() {
let narrow = node("NARROW", 0.0, 300.0, 20.0, 40.0);
let roomy = node("ROOMY", 500.0, 300.0, 300.0, 40.0);
let x = node("X", -50.0, 50.0, 40.0, 30.0);
let y = node("Y", 225.0, 150.0, 40.0, 30.0);
let z = node("Z", 490.0, 250.0, 40.0, 30.0);
let nodes = vec![
narrow.clone(),
roomy.clone(),
x.clone(),
y.clone(),
z.clone(),
];
let routed_narrow = route_all(
Direction::TopToBottom,
&nodes,
&three_branches_into("NARROW"),
);
let required_w = routed_narrow.required_size["NARROW"].w;
assert!(
(required_w - 48.0).abs() < 1e-9,
"3 ports need (3-1)*16 + 2*8 = 48px of flat run: got {required_w}"
);
let routed_roomy = route_all(
Direction::TopToBottom,
&nodes,
&three_branches_into("ROOMY"),
);
assert!(
!routed_roomy.required_size.contains_key("ROOMY")
|| routed_roomy.required_size["ROOMY"].w <= roomy.size.w,
"a face that already fits its ports must not ask to grow: {:?}",
routed_roomy.required_size.get("ROOMY")
);
}
#[test]
fn chamfered_rect_required_size_adds_the_chamfer_allowance_on_top_of_the_flat_run() {
let mut target = node("T", 300.0, 300.0, 20.0, 40.0);
target.shape = Glyph::ChamferedRect;
let x = node("X", 200.0, 100.0, 40.0, 30.0);
let y = node("Y", 400.0, 100.0, 40.0, 30.0);
let nodes = vec![target.clone(), x.clone(), y.clone()];
let edges = vec![
EligibleEdge {
id: "e1",
source: "X",
target: "T",
raw: &[],
source_rank: Some(0),
target_rank: Some(1),
source_out_degree: 2,
target_in_degree: 2,
aside: false,
},
EligibleEdge {
id: "e2",
source: "Y",
target: "T",
raw: &[],
source_rank: Some(0),
target_rank: Some(1),
source_out_degree: 2,
target_in_degree: 2,
aside: false,
},
];
let routed = route_all(Direction::TopToBottom, &nodes, &edges);
let required_w = routed.required_size["T"].w;
assert!(
(required_w - 44.0).abs() < 1e-9,
"expected 32px flat run + 12px chamfer allowance = 44px: got {required_w}"
);
}
#[test]
fn eviction_keeps_every_port_exactly_port_inset_outside_the_node() {
let target = node("T", 500.0, 300.0, 300.0, 60.0);
let x = node("X", 50.0, 50.0, 60.0, 40.0);
let y = node("Y", 950.0, 150.0, 60.0, 40.0);
let z = node("Z", 1400.0, 250.0, 60.0, 40.0);
let nodes = vec![target.clone(), x.clone(), y.clone(), z.clone()];
let edges = three_branches_into("T");
let routed = route_all(Direction::TopToBottom, &nodes, &edges);
let (_, top, _, _) = target.bounds();
for id in ["e1", "e2", "e3"] {
let tip = routed.points[id].last().unwrap();
assert!(
(tip.y - (top - PORT_INSET)).abs() < 1e-9,
"{id}: evicted port must still sit exactly PORT_INSET outside the face: {tip:?}"
);
}
}
fn ranks(pairs: &[(&str, i32)]) -> HashMap<String, i32> {
pairs.iter().map(|(id, r)| (id.to_string(), *r)).collect()
}
fn edge(source: &str, target: &str) -> (String, String) {
(source.to_string(), target.to_string())
}
#[test]
fn a_straight_chain_across_three_ranks_aligns_onto_the_average_cross_coordinate() {
let mut nodes = vec![
node("A", 0.0, 0.0, 40.0, 30.0),
node("B", 50.0, 100.0, 40.0, 30.0),
node("C", 100.0, 200.0, 40.0, 30.0),
];
let node_rank = ranks(&[("A", 0), ("B", 1), ("C", 2)]);
let candidates = [edge("A", "B"), edge("B", "C")];
let _ = align_straight_lanes(
Direction::TopToBottom,
&mut nodes,
&node_rank,
&candidates,
&LaneUnits::default(),
);
for n in &nodes {
assert!(
(n.center.x - 50.0).abs() < 1e-9,
"{}: expected x=50 (the chain's average), got {:?}",
n.id,
n.center
);
}
assert_eq!(nodes[0].center.y, 0.0);
assert_eq!(nodes[1].center.y, 100.0);
assert_eq!(nodes[2].center.y, 200.0);
}
#[test]
fn tie_break_prefers_a_target_that_continues_the_chain_over_a_leaf() {
let mut nodes = vec![
node("C", 0.0, 50.0, 40.0, 30.0),
node("LEAF1", 100.0, 0.0, 40.0, 30.0),
node("LEAF2", 100.0, 100.0, 40.0, 30.0),
node("TRUNK", 100.0, 50.0, 40.0, 30.0),
node("NEXT", 200.0, 999.0, 40.0, 30.0),
];
let node_rank = ranks(&[
("C", 0),
("LEAF1", 1),
("LEAF2", 1),
("TRUNK", 1),
("NEXT", 2),
]);
let candidates = [
edge("C", "LEAF1"),
edge("C", "LEAF2"),
edge("C", "TRUNK"),
edge("TRUNK", "NEXT"),
];
let (_, chain_sources) = align_straight_lanes(
Direction::LeftToRight,
&mut nodes,
&node_rank,
&candidates,
&LaneUnits::default(),
);
let by_id: HashMap<&str, &PlacedNode> = nodes.iter().map(|n| (n.id.as_str(), n)).collect();
assert_eq!(
by_id["C"].center.y,
by_id["TRUNK"].center.y,
"C must align with TRUNK (the target that itself continues), not LEAF1: {:?}",
nodes
.iter()
.map(|n| (n.id.as_str(), n.center.y))
.collect::<Vec<_>>()
);
assert!(
chain_sources.contains_key("C") && chain_sources.contains_key("TRUNK"),
"both chain links' own sources must be reported back: {chain_sources:?}"
);
assert_eq!(
chain_sources.get("C").map(String::as_str),
Some("TRUNK"),
"the returned map must name TRUNK as C's own selected target, not merely list C: \
{chain_sources:?}"
);
}
#[test]
fn tie_break_prefers_extending_an_already_selected_chain_over_a_fresh_pick() {
let mut nodes = vec![
node("MM", 0.0, 100.0, 40.0, 30.0),
node("RS", 100.0, 100.0, 40.0, 30.0),
node("IM", 100.0, 0.0, 40.0, 30.0),
node("FIT", 200.0, 50.0, 40.0, 30.0),
];
let node_rank = ranks(&[("MM", 0), ("IM", 0), ("RS", 1), ("FIT", 2)]);
let candidates = [edge("MM", "RS"), edge("RS", "FIT"), edge("IM", "FIT")];
let (_, chain_sources) = align_straight_lanes(
Direction::LeftToRight,
&mut nodes,
&node_rank,
&candidates,
&LaneUnits::default(),
);
assert!(
chain_sources.contains_key("RS"),
"RS must have been selected to extend the MM -> RS -> FIT chain: {chain_sources:?}"
);
assert!(
!chain_sources.contains_key("IM"),
"IM (a fresh, unrelated pick) must lose the tie to RS (already mid-chain): \
{chain_sources:?}"
);
}
#[test]
fn tie_break_prefers_the_smaller_cross_coordinate() {
let mut nodes = vec![
node("S1", 10.0, 0.0, 40.0, 30.0),
node("S2", 500.0, 0.0, 40.0, 30.0),
node("T", 50.0, 100.0, 40.0, 30.0),
];
let node_rank = ranks(&[("S1", 0), ("S2", 0), ("T", 1)]);
let candidates = [edge("S1", "T"), edge("S2", "T")];
let _ = align_straight_lanes(
Direction::TopToBottom,
&mut nodes,
&node_rank,
&candidates,
&LaneUnits::default(),
);
let by_id: HashMap<&str, &PlacedNode> = nodes.iter().map(|n| (n.id.as_str(), n)).collect();
assert!(
(by_id["T"].center.x - 30.0).abs() < 1e-9,
"T must align with S1 (30), not S2 (275): {:?}",
by_id["T"].center
);
assert_eq!(
by_id["S2"].center.x, 500.0,
"S2 lost the tie and must be left exactly where it started"
);
}
#[test]
fn merge_trunk_index_takes_the_median_source_in_declaration_order() {
let never = |_: &str| false;
assert_eq!(merge_trunk_index(&["a", "b", "c"], &never), 1);
assert_eq!(merge_trunk_index(&["a", "b", "c", "d"], &never), 2);
assert_eq!(merge_trunk_index(&["a", "b", "c", "d", "e"], &never), 2);
assert_eq!(merge_trunk_index(&["a", "b"], &never), 1);
}
#[test]
fn merge_trunk_index_keeps_the_lane_on_the_one_source_that_already_has_one() {
let sources = ["a", "b", "c"];
assert_eq!(merge_trunk_index(&sources, &|id| id == "a"), 0);
assert_eq!(merge_trunk_index(&sources, &|id| id == "c"), 2);
assert_eq!(
merge_trunk_index(&sources, &|id| id == "a" || id == "c"),
1,
"two spines cannot both keep their lane, so the median decides"
);
assert_eq!(merge_trunk_index(&sources, &|_| false), 1);
}
#[test]
fn pure_merges_needs_three_sources_that_go_nowhere_else() {
let never_a_bar = |_: &str| false;
let node_rank = ranks(&[("A", 0), ("B", 0), ("C", 0), ("T", 1), ("U", 1)]);
let plain = [edge("A", "T"), edge("B", "T"), edge("C", "T")];
let found = pure_merges(&node_rank, &plain, &never_a_bar);
assert_eq!(found.len(), 1, "three sources into one target is a merge");
assert_eq!(found[0].target, "T");
assert_eq!(
found[0].sources,
vec!["A".to_string(), "B".to_string(), "C".to_string()],
"sources come back in declaration order, which is what the median is taken over"
);
let two = [edge("A", "T"), edge("B", "T")];
assert!(
pure_merges(&node_rank, &two, &never_a_bar).is_empty(),
"two sources keep §10-1 item 2's own greedy"
);
let bipartite = [
edge("A", "T"),
edge("B", "T"),
edge("C", "T"),
edge("A", "U"),
];
assert!(
pure_merges(&node_rank, &bipartite, &never_a_bar).is_empty(),
"a source that also fans out on the same rank is not a pure merge"
);
}
#[test]
fn a_pure_merge_puts_the_median_source_on_the_lane_and_moves_the_stack_with_it() {
let mut nodes = vec![
node("S1", 0.0, 0.0, 40.0, 30.0),
node("S2", 70.0, 0.0, 40.0, 30.0),
node("S3", 140.0, 0.0, 40.0, 30.0),
node("T", 200.0, 100.0, 40.0, 30.0),
node("U", 200.0, 200.0, 40.0, 30.0),
];
let node_rank = ranks(&[("S1", 0), ("S2", 0), ("S3", 0), ("T", 1), ("U", 2)]);
let candidates = [
edge("S1", "T"),
edge("S2", "T"),
edge("S3", "T"),
edge("T", "U"),
];
let _ = align_straight_lanes(
Direction::TopToBottom,
&mut nodes,
&node_rank,
&candidates,
&LaneUnits::default(),
);
let by_id: HashMap<&str, &PlacedNode> = nodes.iter().map(|n| (n.id.as_str(), n)).collect();
let (s1, s2, s3, t) = (
by_id["S1"].center.x,
by_id["S2"].center.x,
by_id["S3"].center.x,
by_id["T"].center.x,
);
assert!(
(t - s2).abs() < 1e-9,
"T must sit on S2, the median source, not on S1 the leftmost: S1={s1} S2={s2} T={t}"
);
assert!(
(s2 - s1 - 70.0).abs() < 1e-9 && (s3 - s2 - 70.0).abs() < 1e-9,
"the three sources keep the one pitch they started with: {s1} {s2} {s3}"
);
}
#[test]
fn a_pure_merge_leaves_a_lane_carrying_source_on_its_own_spine() {
let mut nodes = vec![
node("S0", 70.0, -100.0, 40.0, 30.0),
node("S1", 0.0, 0.0, 40.0, 30.0),
node("S2", 70.0, 0.0, 40.0, 30.0),
node("S3", 140.0, 0.0, 40.0, 30.0),
node("T", 200.0, 100.0, 40.0, 30.0),
];
let node_rank = ranks(&[("S0", 0), ("S1", 1), ("S2", 1), ("S3", 1), ("T", 2)]);
let candidates = [
edge("S0", "S1"),
edge("S1", "T"),
edge("S2", "T"),
edge("S3", "T"),
];
let (_, next) = align_straight_lanes(
Direction::TopToBottom,
&mut nodes,
&node_rank,
&candidates,
&LaneUnits::default(),
);
assert_eq!(
next.get("S1").map(String::as_str),
Some("T"),
"S1 already carries the S0 --> S1 lane, so the merge must not take it away: {next:?}"
);
assert!(
!next.contains_key("S2"),
"S2 is the median, but the spine clause outranks it: {next:?}"
);
}
#[test]
fn the_median_distance_key_ties_for_a_two_candidate_fan_despite_float_noise() {
let mut nodes = vec![
node("MD", 0.0, 351.4, 40.0, 30.0),
node("MM", 100.0, 264.09999999999997, 40.0, 30.0),
node("MA", 100.0, 381.4, 40.0, 30.0),
node("RS", 200.0, 300.0, 40.0, 30.0),
];
let mid = (264.09999999999997_f64 + 381.4) / 2.0;
assert_ne!(
(264.09999999999997_f64 - mid).abs(),
(381.4_f64 - mid).abs(),
"the fixture must actually exhibit the noise it exists for"
);
let node_rank = ranks(&[("MD", 0), ("MM", 1), ("MA", 1), ("RS", 2)]);
let candidates = [
edge("MD", "MA"),
edge("MD", "MM"),
edge("MM", "RS"),
edge("MA", "RS"),
];
let (_, next) = align_straight_lanes(
Direction::LeftToRight,
&mut nodes,
&node_rank,
&candidates,
&LaneUnits::default(),
);
assert_eq!(
next.get("MD").map(String::as_str),
Some("MM"),
"a two-candidate fan is tied on the median key, so the smaller target cross takes the \
lane — never whichever side the floating-point error happened to fall on: {next:?}"
);
}
#[test]
fn tie_break_second_key_prefers_the_smaller_target_cross_coordinate_when_sources_tie() {
let mut nodes = vec![
node("S", 100.0, 0.0, 40.0, 30.0),
node("Zed", 20.0, 100.0, 40.0, 30.0),
node("Alef", 500.0, 100.0, 40.0, 30.0),
];
let node_rank = ranks(&[("S", 0), ("Zed", 1), ("Alef", 1)]);
let candidates = [edge("S", "Alef"), edge("S", "Zed")];
let _ = align_straight_lanes(
Direction::TopToBottom,
&mut nodes,
&node_rank,
&candidates,
&LaneUnits::default(),
);
let by_id: HashMap<&str, &PlacedNode> = nodes.iter().map(|n| (n.id.as_str(), n)).collect();
assert!(
(by_id["S"].center.x - 60.0).abs() < 1e-9,
"S must align with Zed (the smaller-cross target), landing at (100+20)/2=60, not \
(100+500)/2=300: {:?}",
by_id["S"].center
);
assert_eq!(
by_id["Alef"].center.x, 500.0,
"Alef lost the second-key tie-break and must be left exactly where it started"
);
}
#[test]
fn a_three_way_leaf_fan_picks_the_cross_order_middle_target_not_the_smallest() {
let mut nodes = vec![
node("S", 0.0, 0.0, 40.0, 30.0),
node("TOP", 100.0, 0.0, 40.0, 30.0),
node("MID", 100.0, 50.0, 40.0, 30.0),
node("BOTTOM", 100.0, 150.0, 40.0, 30.0),
];
let node_rank = ranks(&[("S", 0), ("TOP", 1), ("MID", 1), ("BOTTOM", 1)]);
let candidates = [edge("S", "TOP"), edge("S", "MID"), edge("S", "BOTTOM")];
let (_, chain_next) = align_straight_lanes(
Direction::LeftToRight,
&mut nodes,
&node_rank,
&candidates,
&LaneUnits::default(),
);
assert_eq!(
chain_next.get("S").map(String::as_str),
Some("MID"),
"S must pick MID (the cross-order middle target), not TOP (the smallest): \
{chain_next:?}"
);
}
#[test]
fn overlap_resolution_pushes_the_later_node_without_reordering() {
let mut nodes = vec![
node("A", 0.0, 0.0, 40.0, 30.0),
node("C", 100.0, 0.0, 40.0, 30.0),
node("P", 200.0, 100.0, 40.0, 30.0),
node("Q", 210.0, 100.0, 40.0, 30.0),
];
let node_rank = ranks(&[("A", 0), ("C", 0), ("P", 1), ("Q", 1)]);
let candidates = [edge("A", "P"), edge("C", "Q")];
let _ = align_straight_lanes(
Direction::TopToBottom,
&mut nodes,
&node_rank,
&candidates,
&LaneUnits::default(),
);
let by_id: HashMap<&str, &PlacedNode> = nodes.iter().map(|n| (n.id.as_str(), n)).collect();
assert!(
(by_id["P"].center.x - 100.0).abs() < 1e-9,
"P is first in rank order and never needs pushing: {:?}",
by_id["P"].center
);
assert!(
(by_id["Q"].center.x - 164.0).abs() < 1e-9,
"Q must be pushed to exactly P's far edge (120) + ORTHO_NODE_SEP(24) + Q's \
half-width(20) = 164, not left at its own aligned 155: {:?}",
by_id["Q"].center
);
}
fn crossing_gaps(cut_points: Vec<Point>, other_points: Vec<Point>) -> Vec<(Point, Point)> {
let nodes = vec![
node("P", 0.0, -500.0, 4.0, 4.0),
node("Q", 0.0, 500.0, 4.0, 4.0),
node("M", -1000.0, -1000.0, 4.0, 4.0),
node("N", 1000.0, -700.0, 4.0, 4.0),
];
let edges = [
EligibleEdge {
id: "cut",
source: "P",
target: "Q",
raw: &[],
source_rank: Some(1),
target_rank: Some(0),
source_out_degree: 1,
target_in_degree: 1,
aside: false,
},
EligibleEdge {
id: "other",
source: "M",
target: "N",
raw: &[],
source_rank: Some(0),
target_rank: Some(1),
source_out_degree: 1,
target_in_degree: 1,
aside: false,
},
];
let mut points = HashMap::new();
points.insert("cut".to_string(), cut_points);
points.insert("other".to_string(), other_points);
let gaps = insert_crossing_gaps(Direction::TopToBottom, &nodes, &[], &edges, &points);
gaps.get("cut").cloned().unwrap_or_default()
}
#[test]
fn crossing_gap_mid_segment_is_the_full_12px() {
let cut = vec![
Point::new(0.0, 0.0),
Point::new(0.0, 20.0),
Point::new(30.0, 20.0),
];
let other = vec![Point::new(-10.0, 10.0), Point::new(10.0, 10.0)];
let gaps = crossing_gaps(cut, other);
assert_eq!(gaps.len(), 1, "{gaps:?}");
let (g0, g1) = &gaps[0];
assert!(
(g0.x - 0.0).abs() < 1e-9 && (g0.y - 4.0).abs() < 1e-9,
"{g0:?}"
);
assert!(
(g1.x - 0.0).abs() < 1e-9 && (g1.y - 16.0).abs() < 1e-9,
"{g1:?}"
);
let width = (g1.x - g0.x).hypot(g1.y - g0.y);
assert!((width - CROSSING_GAP).abs() < 1e-9, "{width}");
}
#[test]
fn crossing_gap_straddling_a_corner_still_totals_12px_by_arc_length() {
let cut = vec![
Point::new(0.0, 0.0),
Point::new(0.0, 20.0),
Point::new(30.0, 20.0),
];
let other = vec![Point::new(-10.0, 17.0), Point::new(10.0, 17.0)];
let gaps = crossing_gaps(cut, other);
assert_eq!(gaps.len(), 1, "{gaps:?}");
let (g0, g1) = &gaps[0];
assert!(
(g0.x - 0.0).abs() < 1e-9 && (g0.y - 11.0).abs() < 1e-9,
"g0 must stay on the vertical leg at arc length 11: {g0:?}"
);
assert!(
(g1.x - 3.0).abs() < 1e-9 && (g1.y - 20.0).abs() < 1e-9,
"g1 must continue 3px past the corner onto the horizontal leg: {g1:?}"
);
let chord = (g1.x - g0.x).hypot(g1.y - g0.y);
assert!(
chord < CROSSING_GAP - 1.0,
"the chord must actually be shorter than CROSSING_GAP for this test to mean anything: \
{chord}"
);
let corner = Point::new(0.0, 20.0);
let arc = crate::preview::mermaid::render::edges::length(&[g0.clone(), corner, g1.clone()]);
assert!((arc - CROSSING_GAP).abs() < 1e-9, "{arc}");
}
#[test]
fn crossing_gap_near_a_port_is_clamped_to_the_room_available() {
let cut = vec![Point::new(0.0, 0.0), Point::new(0.0, 8.0)];
let other = vec![Point::new(-10.0, 3.0), Point::new(10.0, 3.0)];
let gaps = crossing_gaps(cut, other);
assert_eq!(gaps.len(), 1, "{gaps:?}");
let (g0, g1) = &gaps[0];
assert!(
(g0.x - 0.0).abs() < 1e-9 && (g0.y - 0.0).abs() < 1e-9,
"g0 must clamp to the polyline's own start: {g0:?}"
);
assert!(
(g1.x - 0.0).abs() < 1e-9 && (g1.y - 8.0).abs() < 1e-9,
"g1 must clamp to the polyline's own end: {g1:?}"
);
let width = (g1.x - g0.x).hypot(g1.y - g0.y);
assert!(
width < CROSSING_GAP,
"a polyline shorter than CROSSING_GAP can only ever give back less than it: {width}"
);
}
#[allow(clippy::type_complexity)]
fn main_vs_main_crossing_gaps(
horiz_points: Vec<Point>,
vert_points: Vec<Point>,
) -> (Vec<(Point, Point)>, Vec<(Point, Point)>) {
let nodes = vec![
node("H0", -1000.0, 0.0, 4.0, 4.0),
node("H1", 1000.0, 0.0, 4.0, 4.0),
node("V0", 0.0, -1000.0, 4.0, 4.0),
node("V1", 0.0, 1000.0, 4.0, 4.0),
];
let edges = [
EligibleEdge {
id: "horiz",
source: "H0",
target: "H1",
raw: &[],
source_rank: None,
target_rank: None,
source_out_degree: 1,
target_in_degree: 1,
aside: false,
},
EligibleEdge {
id: "vert",
source: "V0",
target: "V1",
raw: &[],
source_rank: Some(0),
target_rank: Some(1),
source_out_degree: 1,
target_in_degree: 1,
aside: false,
},
];
let mut points = HashMap::new();
points.insert("horiz".to_string(), horiz_points);
points.insert("vert".to_string(), vert_points);
let gaps = insert_crossing_gaps(Direction::TopToBottom, &nodes, &[], &edges, &points);
(
gaps.get("horiz").cloned().unwrap_or_default(),
gaps.get("vert").cloned().unwrap_or_default(),
)
}
#[test]
fn two_main_edges_crossing_cut_the_horizontal_one_not_the_vertical_one() {
let horiz = vec![Point::new(-50.0, 0.0), Point::new(50.0, 0.0)];
let vert = vec![Point::new(0.0, -50.0), Point::new(0.0, 50.0)];
let (horiz_gaps, vert_gaps) = main_vs_main_crossing_gaps(horiz, vert);
assert_eq!(
horiz_gaps.len(),
1,
"the horizontal edge must carry the gap: {horiz_gaps:?}"
);
assert!(
vert_gaps.is_empty(),
"the vertical edge must stay whole: {vert_gaps:?}"
);
let (g0, g1) = &horiz_gaps[0];
assert!(
(g0.y - 0.0).abs() < 1e-9 && (g1.y - 0.0).abs() < 1e-9,
"the gap must sit on the horizontal edge's own (y=0) line: {horiz_gaps:?}"
);
}
#[test]
fn two_main_edges_crossing_ignore_which_one_is_named_first() {
let vert = vec![Point::new(0.0, -50.0), Point::new(0.0, 50.0)];
let horiz = vec![Point::new(-50.0, 0.0), Point::new(50.0, 0.0)];
let (horiz_named_gaps, vert_named_gaps) = main_vs_main_crossing_gaps(vert, horiz);
assert!(
horiz_named_gaps.is_empty(),
"the edge named \"horiz\" is drawing the *vertical* line here and must stay whole: \
{horiz_named_gaps:?}"
);
assert_eq!(
vert_named_gaps.len(),
1,
"the edge named \"vert\" is drawing the *horizontal* line here and must carry the \
gap: {vert_named_gaps:?}"
);
}
#[test]
fn rank_lane_gap_bends_finds_the_single_gap_upstream_of_the_target() {
let a = node("A", 0.0, 0.0, 80.0, 40.0); let b = node("B", 300.0, 150.0, 200.0, 40.0); let c = node("C", 600.0, 300.0, 80.0, 40.0); let nodes = vec![a.clone(), b, c.clone()];
let bends = rank_lane_gap_bends(Direction::LeftToRight, &a, &c, Side::Left, &nodes, false);
assert_eq!(
bends.len(),
1,
"only B's own right edge (400) sits upstream of C's own left edge (560): {bends:?}"
);
assert!(
bends[0] > 400.0 && bends[0] < 560.0,
"the bend must sit inside the gap (400, 560): {}",
bends[0]
);
}
#[test]
fn rank_lane_gap_bends_orders_multiple_gaps_nearest_target_first() {
let a = node("A", 0.0, 0.0, 80.0, 40.0);
let d = node("D", 380.0, 150.0, 80.0, 40.0); let b = node("B", 500.0, 150.0, 100.0, 40.0); let c = node("C", 800.0, 300.0, 80.0, 40.0); let nodes = vec![a.clone(), d, b, c.clone()];
let bends = rank_lane_gap_bends(Direction::LeftToRight, &a, &c, Side::Left, &nodes, false);
assert_eq!(bends.len(), 2, "{bends:?}");
assert!(
bends[0] > 550.0 && bends[0] < 760.0,
"nearest gap first: {bends:?}"
);
assert!(
bends[1] > 420.0 && bends[1] < 450.0,
"second candidate is the next gap out, past B's own body: {bends:?}"
);
}
#[test]
fn rank_lane_gap_bends_is_empty_when_target_is_the_first_column() {
let a = node("A", 0.0, 0.0, 80.0, 40.0);
let c = node("C", 600.0, 0.0, 80.0, 40.0);
let nodes = vec![a.clone(), c.clone()];
let bends = rank_lane_gap_bends(Direction::LeftToRight, &a, &c, Side::Left, &nodes, false);
assert!(bends.is_empty(), "{bends:?}");
}
#[test]
fn rank_lane_gap_bends_stays_within_the_nearer_half_of_the_source_target_span() {
let a = node("A", 0.0, 0.0, 80.0, 40.0);
let e = node("E", 120.0, 150.0, 40.0, 40.0); let c = node("C", 600.0, 300.0, 80.0, 40.0);
let nodes = vec![a.clone(), e, c.clone()];
let bends = rank_lane_gap_bends(Direction::LeftToRight, &a, &c, Side::Left, &nodes, false);
assert!(
bends.is_empty(),
"a wall this close to A must be out of the nearer-half scope: {bends:?}"
);
}
#[test]
fn classify_uses_a_rank_lane_bend_when_both_ordinary_attempts_collide() {
let a = node("A", 0.0, 0.0, 80.0, 40.0);
let b1 = node("B1", 500.0, 150.0, 100.0, 280.0); let b2 = node("B2", 300.0, 300.0, 200.0, 40.0); let c = node("C", 1000.0, 300.0, 80.0, 40.0); let nodes = vec![a.clone(), b1.clone(), b2.clone(), c.clone()];
let shape = classify(
Direction::LeftToRight,
&a,
&c,
&[],
Some(0),
Some(1),
1, 2, &nodes,
&[],
false,
false,
false,
&[],
);
assert!(
shape.rank_lane_bend.is_some(),
"both ordinary attempts must have collided, landing on a rank-lane bend: {shape:?}"
);
assert!(
!shape.staircase,
"a working rank-lane bend must pre-empt staircase: {shape:?}"
);
assert_eq!(shape.source_axis, Axis::Flow, "{shape:?}");
assert_eq!(shape.target_axis, Axis::Flow, "{shape:?}");
let source_port = port_at(
&a,
shape.source_side,
face_center_coord(&a, shape.source_side),
PORT_INSET,
);
let target_port = port_at(
&c,
shape.target_side,
face_center_coord(&c, shape.target_side),
PORT_INSET,
);
let bend = shape.rank_lane_bend.unwrap();
let mut pts = vec![source_port.clone()];
pts.extend(bend_at(
Direction::LeftToRight,
bend,
&source_port,
&target_port,
));
for w in pts.windows(2) {
assert!(
!segment_crosses_node(&w[0], &w[1], &b1),
"segment {w:?} must not cross B1: {pts:?}"
);
assert!(
!segment_crosses_node(&w[0], &w[1], &b2),
"segment {w:?} must not cross B2: {pts:?}"
);
}
}
#[test]
fn clear_local_route_keeps_the_exit_port_pinned_and_still_clears_the_obstacle() {
let a = node("A", 0.0, 100.0, 80.0, 40.0);
let b = node("B", 400.0, 300.0, 80.0, 40.0);
let obstacle = node("OBSTACLE", 120.0, 100.0, 80.0, 40.0);
let nodes = vec![a.clone(), b.clone(), obstacle.clone()];
let port_a = port_at(
&a,
Side::Right,
face_center_coord(&a, Side::Right),
PORT_INSET,
);
let port_b = port_at(
&b,
Side::Left,
face_center_coord(&b, Side::Left),
PORT_INSET,
);
let bend_flow = 200.0;
let mut points = vec![port_a.clone()];
points.extend(bend_at(Direction::LeftToRight, bend_flow, &port_a, &port_b));
assert!(
segment_crosses_node(&points[0], &points[1], &obstacle),
"fixture must genuinely cross OBSTACLE before the fix runs: {points:?}"
);
let fixed = clear_local_route(points, &nodes, (a.id.as_str(), b.id.as_str()));
assert_eq!(
fixed[0], port_a,
"A's own port must stay exactly on its assigned face slot: {fixed:?}"
);
assert_eq!(
*fixed.last().unwrap(),
port_b,
"B's own port must stay exactly on its assigned face slot: {fixed:?}"
);
assert!(
(fixed[0].y - fixed[1].y).abs() < EPS && (fixed[0].x - fixed[1].x).abs() > EPS,
"A must still leave its own Right face horizontally (perpendicular exit, §10-1 item \
1): {fixed:?}"
);
for w in fixed.windows(2) {
let (dx, dy) = ((w[1].x - w[0].x).abs(), (w[1].y - w[0].y).abs());
assert!(
dx < EPS || dy < EPS,
"every segment must stay axis-parallel: {w:?} in {fixed:?}"
);
assert!(
!segment_crosses_node(&w[0], &w[1], &obstacle),
"the fixed route must still clear OBSTACLE: {w:?} in {fixed:?}"
);
}
}
#[test]
fn clear_local_route_keeps_the_entry_port_pinned_and_still_clears_the_obstacle() {
let a = node("A", 0.0, 100.0, 80.0, 40.0);
let b = node("B", 400.0, 300.0, 80.0, 40.0);
let obstacle = node("OBSTACLE", 280.0, 300.0, 80.0, 40.0);
let nodes = vec![a.clone(), b.clone(), obstacle.clone()];
let port_a = port_at(
&a,
Side::Right,
face_center_coord(&a, Side::Right),
PORT_INSET,
);
let port_b = port_at(
&b,
Side::Left,
face_center_coord(&b, Side::Left),
PORT_INSET,
);
let bend_flow = 200.0;
let mut points = vec![port_a.clone()];
points.extend(bend_at(Direction::LeftToRight, bend_flow, &port_a, &port_b));
let last = points.len() - 1;
assert!(
segment_crosses_node(&points[last - 1], &points[last], &obstacle),
"fixture must genuinely cross OBSTACLE before the fix runs: {points:?}"
);
assert!(
!segment_crosses_node(&points[0], &points[1], &obstacle),
"fixture's own exit leg must NOT cross OBSTACLE (isolates the entry-leg case): \
{points:?}"
);
let fixed = clear_local_route(points, &nodes, (a.id.as_str(), b.id.as_str()));
assert_eq!(
fixed[0], port_a,
"A's own port must stay exactly on its assigned face slot: {fixed:?}"
);
assert_eq!(
*fixed.last().unwrap(),
port_b,
"B's own port must stay exactly on its assigned face slot: {fixed:?}"
);
let n = fixed.len();
assert!(
(fixed[n - 1].y - fixed[n - 2].y).abs() < EPS
&& (fixed[n - 1].x - fixed[n - 2].x).abs() > EPS,
"B must still be entered horizontally on its own Left face (perpendicular entry, \
§10-1 item 1): {fixed:?}"
);
for w in fixed.windows(2) {
let (dx, dy) = ((w[1].x - w[0].x).abs(), (w[1].y - w[0].y).abs());
assert!(
dx < EPS || dy < EPS,
"every segment must stay axis-parallel: {w:?} in {fixed:?}"
);
assert!(
!segment_crosses_node(&w[0], &w[1], &obstacle),
"the fixed route must still clear OBSTACLE: {w:?} in {fixed:?}"
);
}
}
#[test]
fn merge_hop_legs_nest_even_when_one_sibling_branches_and_neither_leg_is_crossed() {
let a = node("A", 100.0, 40.0, 80.0, 40.0);
let b = node("B", 100.0, 80.0, 74.0, 40.0);
let m = node("M", 400.0, 100.0, 80.0, 120.0);
let nodes = [a, b, m];
let edges = vec![
EligibleEdge {
id: "am",
source: "A",
target: "M",
raw: &[],
source_rank: Some(0),
target_rank: Some(1),
source_out_degree: 2,
target_in_degree: 2,
aside: false,
},
EligibleEdge {
id: "bm",
source: "B",
target: "M",
raw: &[],
source_rank: Some(0),
target_rank: Some(1),
source_out_degree: 1,
target_in_degree: 2,
aside: false,
},
];
let routed = route_all(Direction::LeftToRight, &nodes, &edges);
let am = &routed.points["am"];
let bm = &routed.points["bm"];
assert_eq!(am.len(), 4, "A->M must draw the four-point hop: {am:?}");
assert_eq!(bm.len(), 4, "B->M must draw the four-point hop: {bm:?}");
let span = |p: &Vec<Point>| (p[1].y.min(p[2].y), p[1].y.max(p[2].y));
let (a_lo, a_hi) = span(am);
let (b_lo, b_hi) = span(bm);
assert!(
a_lo.max(b_lo) < a_hi.min(b_hi) - EPS,
"the fixture must put the two legs alongside each other, or it proves nothing: \
{am:?} / {bm:?}"
);
let apart = (am[1].x - bm[1].x).abs();
assert!(
apart >= PORT_CLEARANCE - EPS,
"A->M's and B->M's hop legs sit {apart}px apart, less than §10-3's own \
{PORT_CLEARANCE}px nested-lane pitch: {am:?} / {bm:?}"
);
}
#[test]
fn perimeter_faces_takes_a_longer_way_round_over_crossing_the_main_flow() {
let a = node("A", 100.0, 100.0, 80.0, 40.0);
let b = node("B", 400.0, 100.0, 80.0, 40.0);
let flow = vec![vec![Point::new(250.0, 95.0), Point::new(250.0, 1000.0)]];
let plain = [a.clone(), b.clone()];
let ring = expand_bounds(box_bounds(&plain, &[], [&a, &b]), PERIMETER_MARGIN);
assert_eq!(
perimeter_faces(&a, &b, ring, &plain, &[]),
(Side::Bottom, Side::Bottom),
"with no main flow to see, the tie still resolves the way PERIMETER_FACE_ORDER says"
);
assert_eq!(
perimeter_faces(&a, &b, ring, &plain, &flow),
(Side::Top, Side::Top),
"the bottom run crosses the main flow and the top one does not, at the same 2 corners"
);
let walled = [a.clone(), b.clone(), node("W", 100.0, 40.0, 120.0, 20.0)];
let ring = expand_bounds(box_bounds(&walled, &[], [&a, &b]), PERIMETER_MARGIN);
assert_eq!(
perimeter_faces(&a, &b, ring, &walled, &[]),
(Side::Bottom, Side::Bottom),
"blind to the main flow, the two-corner bottom pair is the cheapest there is"
);
assert_eq!(
perimeter_faces(&a, &b, ring, &walled, &flow),
(Side::Left, Side::Top),
"three corners and 560.5px that cross nothing beat two corners and 328.5px that cut \
the main flow — a crossing outranks both corners and length"
);
}
#[test]
fn perimeter_faces_takes_the_fewest_corners_and_moves_off_a_blocked_side() {
let a = node("A", 100.0, 100.0, 80.0, 40.0);
let b = node("B", 400.0, 100.0, 80.0, 40.0);
let pair = [a.clone(), b.clone()];
let ring = expand_bounds(box_bounds(&pair, &[], [&a, &b]), PERIMETER_MARGIN);
assert_eq!(
perimeter_faces(&a, &b, ring, &pair, &[]),
(Side::Bottom, Side::Bottom),
"with nothing in the way both ends should reach the same ring side"
);
let wall = node("W", 250.0, 130.0, 300.0, 20.0);
let blocked = [a.clone(), b.clone(), wall];
let ring = expand_bounds(box_bounds(&blocked, &[], [&a, &b]), PERIMETER_MARGIN);
assert_eq!(
perimeter_faces(&a, &b, ring, &blocked, &[]),
(Side::Top, Side::Top),
"the bottom is blocked, so the cheapest pair is the top"
);
}
}