Line data    Source code

       1              : //! Orthogonal routes of the edges of the dataflow canvas around its boxes, for the edges that the layout did not
       2              : //! route: the edges of a box that was moved, or of a box that another box was moved onto.
       3              : //!
       4              : //! An edge leaves the right border of its source box and enters the left border of its target box, at the rows of
       5              : //! their statements. ortho-router builds a grid of the lines through the boxes grown by a margin and the stubs of
       6              : //! the ports, searches the shortest route with few bends through it, and spreads routes that share a channel apart.
       7              : 
       8              : use crate::layout::DataflowLayoutConfig;
       9              : use crate::ortho_router::{Connector, Options, Point, Port, Rect, Router, Side};
      10              : 
      11              : /// What a bend costs, as a length
      12              : const ROUTE_BEND_PENALTY: f64 = 40.0;
      13              : 
      14              : /// A box that routes go around
      15              : #[derive(Clone, Copy, Debug, PartialEq)]
      16              : pub struct RouteBox {
      17              :     pub x: f64,
      18              :     pub y: f64,
      19              :     pub width: f64,
      20              :     pub height: f64,
      21              : }
      22              : 
      23              : /// An edge to route: from a point on the right border of a box to a point on the left border of a box
      24              : #[derive(Clone, Copy, Debug, PartialEq)]
      25              : pub struct RouteRequestEdge {
      26              :     pub from: (f64, f64),
      27              :     pub to: (f64, f64),
      28              : }
      29              : 
      30              : /// Route edges around boxes as polylines of horizontal and vertical segments, `None` for an edge without a way
      31              : /// around the boxes. Routes keep `edge_box_gap` to the boxes, routes that share a channel spread `edge_gap` apart.
      32            2 : pub fn route_edges(boxes: &[RouteBox], edges: &[RouteRequestEdge], config: &DataflowLayoutConfig) -> Vec<Option<Vec<(f64, f64)>>> {
      33            9 :     let point = |(x, y): (f64, f64)| Point { x: x as f32, y: y as f32 };
      34            2 :     let options = Options { margin: config.edge_box_gap as f32, bend_penalty: ROUTE_BEND_PENALTY as f32, spacing: config.edge_gap as f32 };
      35            2 :     let mut router = Router::new(options)
      36            5 :         .with_obstacles(boxes.iter().map(|b| Rect::from_min_size(point((b.x, b.y)), b.width as f32, b.height as f32)));
      37            2 :     let connectors: Vec<Connector> = edges.iter().map(|e| Connector::new(Port::new(point(e.from), Side::Right), Port::new(point(e.to), Side::Left))).collect();
      38            2 :     router
      39            2 :         .route_all(&connectors)
      40            2 :         .into_iter()
      41           12 :         .map(|route| route.routed.then(|| route.points.iter().map(|p| (p.x as f64, p.y as f64)).collect()))
      42            2 :         .collect()
      43            2 : }
      44              : 
      45              : #[cfg(test)]
      46              : mod tests {
      47              :     use super::*;
      48              : 
      49            5 :     fn rect(x: f64, y: f64, width: f64, height: f64) -> RouteBox {
      50            5 :         RouteBox { x, y, width, height }
      51            5 :     }
      52              : 
      53              :     /// Does a polyline pass through the inside of a box?
      54            1 :     fn crosses(points: &[(f64, f64)], b: &RouteBox) -> bool {
      55            5 :         points.windows(2).any(|w| {
      56            5 :             let (x0, x1) = (w[0].0.min(w[1].0), w[0].0.max(w[1].0));
      57            5 :             let (y0, y1) = (w[0].1.min(w[1].1), w[0].1.max(w[1].1));
      58            5 :             x0 < b.x + b.width && x1 > b.x && y0 < b.y + b.height && y1 > b.y
      59            5 :         })
      60            1 :     }
      61              : 
      62              :     #[test]
      63            1 :     fn routes_around_a_box_in_the_way_with_right_angles() {
      64            1 :         let boxes = [rect(0.0, 0.0, 100.0, 60.0), rect(200.0, 0.0, 100.0, 60.0), rect(400.0, 0.0, 100.0, 60.0)];
      65            1 :         let routes = route_edges(&boxes, &[RouteRequestEdge { from: (100.0, 30.0), to: (400.0, 30.0) }], &DataflowLayoutConfig::default());
      66            1 :         let points = routes[0].as_ref().expect("a route");
      67            1 :         assert_eq!(points.first(), Some(&(100.0, 30.0)));
      68            1 :         assert_eq!(points.last(), Some(&(400.0, 30.0)));
      69            1 :         assert!(!crosses(points, &boxes[1]));
      70            5 :         assert!(points.windows(2).all(|w| w[0].0 == w[1].0 || w[0].1 == w[1].1));
      71            1 :     }
      72              : 
      73              :     #[test]
      74            1 :     fn routes_back_to_a_box_on_the_left_around_both() {
      75            1 :         let boxes = [rect(0.0, 0.0, 100.0, 60.0), rect(200.0, 0.0, 100.0, 60.0)];
      76            1 :         let routes = route_edges(&boxes, &[RouteRequestEdge { from: (300.0, 30.0), to: (0.0, 30.0) }], &DataflowLayoutConfig::default());
      77            1 :         let points = routes[0].as_ref().expect("a route");
      78            3 :         assert!(points.iter().any(|p| p.1 < 0.0 || p.1 > 60.0));
      79            5 :         assert!(points.windows(2).all(|w| w[0].0 == w[1].0 || w[0].1 == w[1].1));
      80            1 :     }
      81              : }