Line data Source code
1 : //! The layout of the dataflow canvas: script boxes of statement rows, flowing from left to right.
2 : //!
3 : //! The layout has two levels. Inside a box the statements are stacked in script order, every statement is a row
4 : //! of the same height and the chart of a visualized statement follows its row, so the box geometry is fixed by the
5 : //! script. Between the boxes, the layered layout of the Eclipse Layout Kernel (elk-rs) places the boxes and routes
6 : //! the edges: every box is a node with a port per connected statement row, inputs on its left border and outputs on
7 : //! its right border at the centers of the rows, and the edges are routed orthogonally, the edges out of one port
8 : //! share their first segments.
9 : //!
10 : //! - Without hints ELK arranges the connected boxes in layers in the order of the session, the consumers of a box
11 : //! stack in one column. The connected parts are packed by ELK, boxes without edges go into rows below them.
12 : //! - With hints, where the boxes were, ELK lays out interactively, every connected part on its own: the columns follow
13 : //! the x of the boxes, the order in a column their y, and a box keeps its y where it does not overlap another. A
14 : //! dropped box goes into the column under its center, or into a new column in a gap between two columns. A layout
15 : //! that starts from where an earlier one put every box reproduces it.
16 :
17 : use std::collections::{BTreeMap, BTreeSet};
18 :
19 : /// The sizes of the dataflow canvas, in canvas pixels. The defaults are the sizes of the canvas of the app and of
20 : /// the dataflow snapshots: the app reads them from the dataflow wasm module, this is the one place to change them.
21 : #[derive(Clone, Copy, Debug, PartialEq)]
22 : pub struct DataflowLayoutConfig {
23 : /// The width of a box
24 : pub box_width: f64,
25 : /// The width of a box with a chart, a chart or a table is wider than high
26 : pub chart_box_width: f64,
27 : /// The width of the box of an input or an attachment
28 : pub input_box_width: f64,
29 : /// The height of the header of a box, a collapsed box is its header
30 : pub header_height: f64,
31 : /// The height of a statement row
32 : pub row_height: f64,
33 : /// The space between the header, the rows and the bottom of a box
34 : pub row_padding: f64,
35 : /// The height of the chart below a visualized statement
36 : pub chart_height: f64,
37 : /// The bounds of the width of a resized box
38 : pub min_box_width: f64,
39 : pub max_box_width: f64,
40 : /// The bounds of the height of a resized chart
41 : pub min_chart_height: f64,
42 : pub max_chart_height: f64,
43 : /// The least horizontal space between the columns, wider where the edges between them need more rails
44 : pub layer_gap: f64,
45 : /// The least vertical space between the boxes of a column
46 : pub box_gap: f64,
47 : /// The space between two parallel edges
48 : pub edge_gap: f64,
49 : /// The space between an edge and a box
50 : pub edge_box_gap: f64,
51 : /// A dropped box that is this close to lining up a row with a row it is connected to lines it up, so that the
52 : /// edge between them runs straight instead of making a small hop
53 : pub align_snap: f64,
54 : /// The boxes without edges per row
55 : pub isolated_per_row: usize,
56 : /// The grid that drags and resizes on the canvas snap to, the layout does not snap
57 : pub grid: f64,
58 : }
59 :
60 : impl Default for DataflowLayoutConfig {
61 55 : fn default() -> Self {
62 55 : Self {
63 55 : box_width: 280.0,
64 55 : chart_box_width: 480.0,
65 55 : input_box_width: 200.0,
66 55 : header_height: 32.0,
67 55 : row_height: 32.0,
68 55 : row_padding: 8.0,
69 55 : chart_height: 200.0,
70 55 : min_box_width: 200.0,
71 55 : max_box_width: 1600.0,
72 55 : min_chart_height: 96.0,
73 55 : max_chart_height: 1200.0,
74 55 : layer_gap: 144.0,
75 55 : box_gap: 48.0,
76 55 : edge_gap: 16.0,
77 55 : edge_box_gap: 24.0,
78 55 : align_snap: 24.0,
79 55 : isolated_per_row: 4,
80 55 : grid: 8.0,
81 55 : }
82 55 : }
83 : }
84 :
85 : /// A script box
86 : #[derive(Clone, Debug, Default, PartialEq)]
87 : pub struct DataflowLayoutBox {
88 : /// The number of statements
89 : pub statements: u32,
90 : /// The statement whose chart follows its row
91 : pub chart_statement: Option<u32>,
92 : /// Is the box collapsed to its header?
93 : pub collapsed: bool,
94 : /// The width of the box, the width of the config if absent, the chart box width with a chart
95 : pub width: Option<f64>,
96 : /// The height of the chart, the chart height of the config if absent
97 : pub chart_height: Option<f64>,
98 : /// Is the box an input or an attachment? It is `input_box_width` wide by default.
99 : pub input: bool,
100 : /// Where the box was, e.g. saved in its `@flow` tag or where the last layout put it
101 : pub hint: Option<(f64, f64)>,
102 : /// Was the box just dropped at its hint by the user? The hints of the other boxes place the layout.
103 : pub dropped: bool,
104 : }
105 :
106 : /// An edge between statements of two boxes
107 : #[derive(Clone, Copy, Debug, PartialEq, Eq)]
108 : pub struct DataflowLayoutEdge {
109 : pub from_box: u32,
110 : pub from_statement: u32,
111 : pub to_box: u32,
112 : pub to_statement: u32,
113 : }
114 :
115 : /// The geometry of a box
116 : #[derive(Clone, Debug, Default, PartialEq)]
117 : pub struct DataflowBoxGeometry {
118 : pub x: f64,
119 : pub y: f64,
120 : pub width: f64,
121 : pub height: f64,
122 : /// The top of every statement row, relative to the box. The rows of a collapsed box are its header.
123 : pub rows: Vec<f64>,
124 : }
125 :
126 : impl DataflowBoxGeometry {
127 : /// The vertical center of the row of a statement, relative to the box
128 356 : pub(crate) fn port(&self, statement: u32, config: &DataflowLayoutConfig) -> f64 {
129 356 : match self.rows.get(statement as usize) {
130 356 : Some(&top) if self.height > config.header_height => top + config.row_height / 2.0,
131 2 : _ => config.header_height / 2.0,
132 : }
133 356 : }
134 : }
135 :
136 : /// The route of an edge between statements of two boxes, by the box and statement of its source and its target: the
137 : /// points of a polyline of horizontal and vertical segments from the right border of the source box to the left
138 : /// border of the target box
139 : pub type DataflowEdgeRoute = ((u32, u32, u32, u32), Vec<(f64, f64)>);
140 :
141 : /// The geometry of a box without its position
142 237 : fn box_geometry(b: &DataflowLayoutBox, config: &DataflowLayoutConfig) -> DataflowBoxGeometry {
143 237 : let default_width = if b.input {
144 9 : config.input_box_width
145 228 : } else if b.chart_statement.is_some() {
146 31 : config.chart_box_width
147 : } else {
148 197 : config.box_width
149 : };
150 237 : let mut geometry = DataflowBoxGeometry { width: b.width.unwrap_or(default_width), ..Default::default() };
151 237 : if b.collapsed || b.statements == 0 {
152 5 : geometry.rows = vec![0.0; b.statements as usize];
153 5 : geometry.height = config.header_height;
154 5 : return geometry;
155 232 : }
156 232 : let mut y = config.header_height + config.row_padding;
157 269 : for statement in 0..b.statements {
158 269 : geometry.rows.push(y);
159 269 : y += config.row_height;
160 269 : if b.chart_statement == Some(statement) {
161 31 : y += config.row_padding + b.chart_height.unwrap_or(config.chart_height);
162 238 : }
163 : }
164 232 : geometry.height = y + config.row_padding;
165 232 : geometry
166 237 : }
167 :
168 : /// The edges between different boxes
169 62 : fn box_edges(edges: &[DataflowLayoutEdge], count: usize) -> Vec<DataflowLayoutEdge> {
170 142 : edges.iter().filter(|e| e.from_box != e.to_box && (e.from_box as usize) < count && (e.to_box as usize) < count).copied().collect()
171 62 : }
172 :
173 : /// The connected parts of the graph, by their first box. Boxes without edges are left out.
174 23 : fn components(count: usize, edges: &[DataflowLayoutEdge]) -> Vec<Vec<usize>> {
175 23 : let mut parent: Vec<usize> = (0..count).collect();
176 246 : fn find(parent: &mut [usize], i: usize) -> usize {
177 246 : let mut root = i;
178 332 : while parent[root] != root {
179 86 : root = parent[root];
180 86 : }
181 246 : parent[i] = root;
182 246 : root
183 246 : }
184 70 : for e in edges {
185 70 : let (a, b) = (find(&mut parent, e.from_box as usize), find(&mut parent, e.to_box as usize));
186 70 : parent[a.max(b)] = a.min(b);
187 70 : }
188 70 : let connected: BTreeSet<usize> = edges.iter().flat_map(|e| [e.from_box as usize, e.to_box as usize]).collect();
189 23 : let mut out: Vec<Vec<usize>> = Vec::new();
190 23 : let mut roots: Vec<usize> = Vec::new();
191 111 : for i in (0..count).filter(|i| connected.contains(i)) {
192 106 : let root = find(&mut parent, i);
193 106 : match roots.iter().position(|&r| r == root) {
194 70 : Some(c) => out[c].push(i),
195 36 : None => {
196 36 : roots.push(root);
197 36 : out.push(vec![i]);
198 36 : }
199 : }
200 : }
201 23 : out
202 23 : }
203 :
204 : /// Put boxes into rows of `isolated_per_row` from a top left corner, returns the bottom of the rows with a gap
205 69 : fn place_in_rows(boxes: &[usize], (left, mut top): (f64, f64), config: &DataflowLayoutConfig, geometry: &mut [DataflowBoxGeometry]) -> f64 {
206 69 : for row in boxes.chunks(config.isolated_per_row.max(1)) {
207 17 : let mut x = left;
208 17 : let mut height: f64 = 0.0;
209 27 : for &i in row {
210 27 : geometry[i].x = x;
211 27 : geometry[i].y = top;
212 27 : x += geometry[i].width + config.box_gap;
213 27 : height = height.max(geometry[i].height);
214 27 : }
215 17 : top += height + config.box_gap;
216 : }
217 69 : top
218 69 : }
219 :
220 : /// Lay out the boxes
221 17 : pub fn compute_dataflow_layout(boxes: &[DataflowLayoutBox], edges: &[DataflowLayoutEdge], config: &DataflowLayoutConfig) -> Vec<DataflowBoxGeometry> {
222 17 : compute_dataflow_layout_with_routes(boxes, edges, config).0
223 17 : }
224 :
225 : /// Lay out the boxes, with the routes of the edges between boxes
226 62 : pub fn compute_dataflow_layout_with_routes(
227 62 : boxes: &[DataflowLayoutBox],
228 62 : edges: &[DataflowLayoutEdge],
229 62 : config: &DataflowLayoutConfig,
230 62 : ) -> (Vec<DataflowBoxGeometry>, Vec<DataflowEdgeRoute>) {
231 233 : let mut geometry: Vec<DataflowBoxGeometry> = boxes.iter().map(|b| box_geometry(b, config)).collect();
232 62 : let edges = box_edges(edges, boxes.len());
233 : // A drop is laid out twice: the second layout starts where the first one put every box, like a reload does, so
234 : // the canvas shows what a reload shows
235 62 : let routes = if boxes.iter().any(|b| b.dropped) {
236 7 : arrange(boxes, &edges, config, &mut geometry);
237 7 : let settled: Vec<DataflowLayoutBox> =
238 39 : boxes.iter().zip(geometry.iter()).map(|(b, g)| DataflowLayoutBox { hint: Some((g.x, g.y)), dropped: false, ..b.clone() }).collect();
239 7 : arrange(&settled, &edges, config, &mut geometry)
240 : } else {
241 55 : arrange(boxes, &edges, config, &mut geometry)
242 : };
243 62 : (geometry, routes)
244 62 : }
245 :
246 : /// How far apart the seeds of two columns are, more than the widest box
247 : const COLUMN_SPREAD: f64 = 10000.0;
248 :
249 : /// The column of a center x: the columns are the runs of overlapping x ranges of the boxes that stay, a center in the
250 : /// gap between two columns is a new column between them. Returns the index of the column, halves for the gaps.
251 106 : fn column_of(columns: &[(f64, f64)], center: f64) -> f64 {
252 182 : for (i, &(x0, x1)) in columns.iter().enumerate() {
253 182 : if center < x0 {
254 3 : return i as f64 - 0.5;
255 179 : }
256 179 : if center <= x1 {
257 97 : return i as f64;
258 82 : }
259 : }
260 6 : columns.len() as f64 - 0.5
261 106 : }
262 :
263 : /// Arrange the boxes once, from their hints if they have any
264 69 : fn arrange(boxes: &[DataflowLayoutBox], edges: &[DataflowLayoutEdge], config: &DataflowLayoutConfig, geometry: &mut [DataflowBoxGeometry]) -> Vec<DataflowEdgeRoute> {
265 69 : let count = geometry.len();
266 168 : let linked: BTreeSet<usize> = edges.iter().flat_map(|e| [e.from_box as usize, e.to_box as usize]).collect();
267 186 : if !boxes.iter().any(|b| b.hint.is_some()) {
268 : // ELK packs the connected boxes, the boxes without edges go into rows below them
269 161 : let connected: Vec<usize> = (0..count).filter(|b| linked.contains(b)).collect();
270 46 : let routes = if connected.is_empty() { Vec::new() } else { elk(boxes, edges, config, geometry, &connected, &vec![None; count], false) };
271 136 : let left = connected.iter().map(|&b| geometry[b].x).fold(f64::INFINITY, f64::min);
272 136 : let bottom = connected.iter().map(|&b| geometry[b].y + geometry[b].height).fold(f64::NEG_INFINITY, f64::max);
273 46 : let corner = if left.is_finite() { (left, bottom + config.box_gap * 2.0) } else { (0.0, 0.0) };
274 161 : let isolated: Vec<usize> = (0..count).filter(|b| !linked.contains(b)).collect();
275 46 : place_in_rows(&isolated, corner, config, geometry);
276 46 : return routes;
277 23 : }
278 : // Interactive: every connected part on its own, so that moving a box in one part leaves the others alone
279 23 : let mut routes = Vec::new();
280 23 : let mut fresh: Vec<Vec<usize>> = Vec::new();
281 37 : for part in components(count, edges) {
282 38 : if !part.iter().any(|&b| boxes[b].hint.is_some()) {
283 0 : fresh.push(part);
284 0 : continue;
285 36 : }
286 : // A box without a hint starts right of its producers or left of its consumers that have one, with the row of
287 : // the edge level with the row at its other end
288 36 : let mut seeds: Vec<Option<(f64, f64)>> = boxes.iter().map(|b| b.hint).collect();
289 106 : for &b in &part {
290 106 : if seeds[b].is_some() {
291 100 : continue;
292 6 : }
293 6 : let producers: Vec<(f64, f64)> = edges
294 6 : .iter()
295 12 : .filter(|e| e.to_box as usize == b)
296 6 : .filter_map(|e| {
297 5 : let p = &geometry[e.from_box as usize];
298 5 : boxes[e.from_box as usize].hint.map(|(x, y)| (x + p.width, y + p.port(e.from_statement, config) - geometry[b].port(e.to_statement, config)))
299 5 : })
300 6 : .collect();
301 6 : let consumers: Vec<(f64, f64)> = edges
302 6 : .iter()
303 12 : .filter(|e| e.from_box as usize == b)
304 6 : .filter_map(|e| {
305 2 : let c = &geometry[e.to_box as usize];
306 2 : boxes[e.to_box as usize].hint.map(|(x, y)| (x, y + c.port(e.to_statement, config) - geometry[b].port(e.from_statement, config)))
307 2 : })
308 6 : .collect();
309 6 : seeds[b] = if let Some(&(x, y)) = producers.iter().max_by(|a, b| a.0.total_cmp(&b.0)) {
310 4 : Some((x + config.layer_gap, y))
311 : } else {
312 2 : consumers.iter().min_by(|a, b| a.0.total_cmp(&b.0)).map(|&(x, y)| (x - config.layer_gap - geometry[b].width, y))
313 : };
314 : }
315 : // A dropped box that almost lines up a row with a connected row of a box that stays lines it up
316 106 : for &b in part.iter().filter(|&&b| boxes[b].dropped) {
317 7 : let Some((x, y)) = seeds[b] else { continue };
318 26 : let deltas = edges.iter().filter_map(|e| {
319 26 : let (this, this_statement, other, other_statement) = if e.to_box as usize == b {
320 7 : (b, e.to_statement, e.from_box as usize, e.from_statement)
321 19 : } else if e.from_box as usize == b {
322 2 : (b, e.from_statement, e.to_box as usize, e.to_statement)
323 : } else {
324 17 : return None;
325 : };
326 9 : let (_, other_y) = boxes[other].hint.filter(|_| !boxes[other].dropped)?;
327 9 : Some(other_y + geometry[other].port(other_statement, config) - (y + geometry[this].port(this_statement, config)))
328 26 : });
329 9 : if let Some(delta) = deltas.filter(|d| d.abs() <= config.align_snap).min_by(|a, b| a.abs().total_cmp(&b.abs())) {
330 2 : seeds[b] = Some((x, y + delta));
331 5 : }
332 : }
333 : // ELK forms its columns from overlapping x ranges, a wide or dropped box would merge two columns. The seeds put
334 : // every box at the column of its center instead, far apart: the boxes that stay form the columns.
335 36 : let mut ranges: Vec<(f64, f64)> =
336 106 : part.iter().filter(|&&b| !boxes[b].dropped).filter_map(|&b| boxes[b].hint.map(|(x, _)| (x, x + geometry[b].width))).collect();
337 62 : ranges.sort_by(|a, b| a.0.total_cmp(&b.0));
338 36 : let mut columns: Vec<(f64, f64)> = Vec::new();
339 93 : for (x0, x1) in ranges {
340 93 : match columns.last_mut() {
341 57 : Some(last) if x0 < last.1 => last.1 = last.1.max(x1),
342 79 : _ => columns.push((x0, x1)),
343 : }
344 : }
345 106 : for &b in &part {
346 106 : if let Some((x, y)) = seeds[b] {
347 106 : seeds[b] = Some((column_of(&columns, x + geometry[b].width / 2.0) * COLUMN_SPREAD, y));
348 106 : }
349 : }
350 36 : routes.extend(elk(boxes, edges, config, geometry, &part, &seeds, true));
351 : }
352 : // Boxes without edges keep their hints, the others and the parts without any hint go below everything
353 111 : let mut placed: Vec<usize> = (0..count).filter(|&b| linked.contains(&b) && !fresh.iter().any(|p| p.contains(&b))).collect();
354 23 : let mut loose: Vec<usize> = Vec::new();
355 111 : for b in (0..count).filter(|b| !linked.contains(b)) {
356 5 : match boxes[b].hint {
357 3 : Some((x, y)) => {
358 3 : geometry[b].x = x;
359 3 : geometry[b].y = y;
360 3 : placed.push(b);
361 3 : }
362 2 : None => loose.push(b),
363 : }
364 : }
365 109 : let left = placed.iter().map(|&b| geometry[b].x).fold(f64::INFINITY, f64::min);
366 23 : let left = if left.is_finite() { left } else { 0.0 };
367 109 : let bottom = placed.iter().map(|&b| geometry[b].y + geometry[b].height).fold(f64::NEG_INFINITY, f64::max);
368 23 : let mut top = if bottom.is_finite() { bottom + config.box_gap * 2.0 } else { 0.0 };
369 23 : for part in fresh {
370 0 : let part_routes = elk(boxes, edges, config, geometry, &part, &vec![None; count], false);
371 0 : let (x0, y0) = part.iter().fold((f64::INFINITY, f64::INFINITY), |(x, y), &b| (x.min(geometry[b].x), y.min(geometry[b].y)));
372 0 : let (dx, dy) = (left - x0, top - y0);
373 0 : for &b in &part {
374 0 : geometry[b].x += dx;
375 0 : geometry[b].y += dy;
376 0 : }
377 0 : top = part.iter().map(|&b| geometry[b].y + geometry[b].height).fold(top, f64::max) + config.box_gap * 2.0;
378 0 : routes.extend(part_routes.into_iter().map(|(k, points)| (k, points.into_iter().map(|(x, y)| (x + dx, y + dy)).collect())));
379 : }
380 23 : place_in_rows(&loose, (left, top), config, geometry);
381 23 : routes
382 69 : }
383 :
384 : /// Lay out a subset of the boxes with ELK, interactively at the seeds of the boxes, and move an interactive layout
385 : /// back by the offset that most of its boxes with hints share: ELK moves a layout to the origin.
386 76 : fn elk(
387 76 : boxes: &[DataflowLayoutBox],
388 76 : edges: &[DataflowLayoutEdge],
389 76 : config: &DataflowLayoutConfig,
390 76 : geometry: &mut [DataflowBoxGeometry],
391 76 : subset: &[usize],
392 76 : seeds: &[Option<(f64, f64)>],
393 76 : interactive: bool,
394 76 : ) -> Vec<DataflowEdgeRoute> {
395 : use org_eclipse_elk_alg_layered::org::eclipse::elk::alg::layered::layered_layout_provider::LayeredLayoutProvider;
396 : use org_eclipse_elk_alg_layered::org::eclipse::elk::alg::layered::options::{
397 : CrossingMinimizationStrategy, CycleBreakingStrategy, LayeredOptions, LayeringStrategy, NodePlacementStrategy,
398 : OrderingStrategy,
399 : };
400 : use org_eclipse_elk_alg_layered::org::eclipse::elk::alg::layered::plain_java_initialization::initialize_plain_java_layout;
401 : use org_eclipse_elk_core::org::eclipse::elk::core::math::ElkPadding;
402 : use org_eclipse_elk_core::org::eclipse::elk::core::options::{CoreOptions, Direction, EdgeRouting, PortConstraints, PortSide, SizeConstraint};
403 : use org_eclipse_elk_core::org::eclipse::elk::core::util::BasicProgressMonitor;
404 : use org_eclipse_elk_core::org::eclipse::elk::core::IGraphLayoutEngine;
405 : use org_eclipse_elk_graph::org::eclipse::elk::graph::properties::Property;
406 : use org_eclipse_elk_graph::org::eclipse::elk::graph::util::ElkGraphUtil;
407 : use org_eclipse_elk_graph::org::eclipse::elk::graph::{ElkConnectableShapeRef, ElkNodeRef, ElkPortRef};
408 :
409 1656 : fn set_node<T: Clone + Send + Sync + 'static>(node: &ElkNodeRef, property: &Property<T>, value: T) {
410 1656 : node.borrow_mut().connectable().shape().graph_element().properties_mut().set_property(property, Some(value));
411 1656 : }
412 305 : fn set_port<T: Clone + Send + Sync + 'static>(port: &ElkPortRef, property: &Property<T>, value: T) {
413 305 : port.borrow_mut().connectable().shape().graph_element().properties_mut().set_property(property, Some(value));
414 305 : }
415 :
416 76 : initialize_plain_java_layout();
417 76 : let graph = ElkGraphUtil::create_graph();
418 76 : set_node(&graph, CoreOptions::DIRECTION, Direction::Right);
419 76 : set_node(&graph, CoreOptions::PADDING, ElkPadding::with_any(0.0));
420 76 : set_node(&graph, LayeredOptions::SPACING_NODE_NODE, config.box_gap);
421 76 : set_node(&graph, LayeredOptions::SPACING_NODE_NODE_BETWEEN_LAYERS, config.layer_gap);
422 76 : set_node(&graph, LayeredOptions::SPACING_COMPONENT_COMPONENT, config.box_gap * 2.0);
423 76 : set_node(&graph, LayeredOptions::SPACING_EDGE_EDGE, config.edge_gap);
424 76 : set_node(&graph, LayeredOptions::SPACING_EDGE_EDGE_BETWEEN_LAYERS, config.edge_gap);
425 76 : set_node(&graph, LayeredOptions::SPACING_EDGE_NODE, config.edge_box_gap);
426 76 : set_node(&graph, LayeredOptions::SPACING_EDGE_NODE_BETWEEN_LAYERS, config.edge_box_gap);
427 : // Orthogonal routes, the edges out of one port share their first segments
428 76 : set_node(&graph, LayeredOptions::EDGE_ROUTING, EdgeRouting::Orthogonal);
429 76 : set_node(&graph, LayeredOptions::MERGE_EDGES, true);
430 76 : if interactive {
431 36 : // The phases keep what the user arranged: the cycles, the columns by x, the order in a column by y and the y
432 36 : // of the boxes. A part is laid out on its own.
433 36 : set_node(&graph, LayeredOptions::CYCLE_BREAKING_STRATEGY, CycleBreakingStrategy::Interactive);
434 36 : set_node(&graph, LayeredOptions::LAYERING_STRATEGY, LayeringStrategy::Interactive);
435 36 : set_node(&graph, LayeredOptions::CROSSING_MINIMIZATION_STRATEGY, CrossingMinimizationStrategy::Interactive);
436 36 : set_node(&graph, LayeredOptions::NODE_PLACEMENT_STRATEGY, NodePlacementStrategy::Interactive);
437 36 : set_node(&graph, LayeredOptions::CONSIDER_MODEL_ORDER_STRATEGY, OrderingStrategy::None);
438 36 : set_node(&graph, LayeredOptions::SEPARATE_CONNECTED_COMPONENTS, false);
439 62 : } else {
440 40 : // The order of the session, ELK packs the parts
441 40 : set_node(&graph, LayeredOptions::NODE_PLACEMENT_STRATEGY, NodePlacementStrategy::NetworkSimplex);
442 40 : set_node(&graph, LayeredOptions::CONSIDER_MODEL_ORDER_STRATEGY, OrderingStrategy::NodesAndEdges);
443 40 : set_node(&graph, LayeredOptions::SEPARATE_CONNECTED_COMPONENTS, true);
444 40 : }
445 :
446 76 : let mut in_subset = vec![false; geometry.len()];
447 242 : for &b in subset {
448 242 : in_subset[b] = true;
449 242 : }
450 228 : let edges: Vec<DataflowLayoutEdge> = edges.iter().filter(|e| in_subset[e.from_box as usize] && in_subset[e.to_box as usize]).copied().collect();
451 76 : let mut connected: Vec<(BTreeSet<u32>, BTreeSet<u32>)> = vec![Default::default(); geometry.len()];
452 76 : let mut unique: BTreeSet<(u32, u32, u32, u32)> = BTreeSet::new();
453 168 : for e in &edges {
454 168 : connected[e.to_box as usize].0.insert(e.to_statement);
455 168 : connected[e.from_box as usize].1.insert(e.from_statement);
456 168 : unique.insert((e.from_box, e.from_statement, e.to_box, e.to_statement));
457 168 : }
458 76 : let mut nodes = Vec::with_capacity(subset.len());
459 76 : let mut ports: BTreeMap<(u32, bool, u32), ElkPortRef> = BTreeMap::new();
460 242 : for &b in subset {
461 242 : let (g, (ins, outs)) = (&geometry[b], &connected[b]);
462 242 : let node = ElkGraphUtil::create_node(Some(graph.clone()));
463 242 : node.borrow_mut().connectable().shape().set_dimensions(g.width, g.height);
464 242 : if let Some((x, y)) = seeds[b] {
465 106 : node.borrow_mut().connectable().shape().set_location(x, y);
466 185 : }
467 242 : set_node(&node, CoreOptions::NODE_SIZE_CONSTRAINTS, SizeConstraint::fixed());
468 242 : set_node(&node, CoreOptions::PORT_CONSTRAINTS, PortConstraints::FixedPos);
469 484 : for (output, statements) in [(false, ins), (true, outs)] {
470 484 : for &statement in statements {
471 305 : let port = ElkGraphUtil::create_port(Some(node.clone()));
472 305 : port.borrow_mut().connectable().shape().set_location(if output { g.width } else { 0.0 }, g.port(statement, config));
473 305 : set_port(&port, CoreOptions::PORT_SIDE, if output { PortSide::East } else { PortSide::West });
474 305 : ports.insert((b as u32, output, statement), port);
475 : }
476 : }
477 242 : nodes.push(node);
478 : }
479 76 : let mut elk_edges = Vec::new();
480 168 : for (from, fs, to, ts) in unique {
481 168 : let (Some(source), Some(target)) = (ports.get(&(from, true, fs)), ports.get(&(to, false, ts))) else { continue };
482 168 : let edge = ElkGraphUtil::create_simple_edge(ElkConnectableShapeRef::Port(source.clone()), ElkConnectableShapeRef::Port(target.clone()));
483 168 : elk_edges.push(((from, fs, to, ts), edge));
484 : }
485 76 : LayeredLayoutProvider::new().layout(&graph, &mut BasicProgressMonitor::new());
486 242 : for (&b, node) in subset.iter().zip(&nodes) {
487 242 : let mut node = node.borrow_mut();
488 242 : let shape = node.connectable().shape();
489 242 : geometry[b].x = shape.x();
490 242 : geometry[b].y = shape.y();
491 242 : }
492 : // ELK moves the layout to the origin, an interactive layout moves back by the offset that most of its boxes with
493 : // hints share: the boxes that ELK left where they were. A dropped box does not count.
494 76 : let mut offset = (0.0, 0.0);
495 76 : if interactive {
496 106 : let anchors = subset.iter().filter(|&&b| boxes[b].hint.is_some() && !boxes[b].dropped).count();
497 36 : let mut counts: Vec<((i64, i64), usize)> = Vec::new();
498 106 : for &b in subset.iter().filter(|&&b| !(boxes[b].dropped && anchors > 0)) {
499 99 : if let Some((x, y)) = boxes[b].hint {
500 93 : let key = ((x - geometry[b].x).round() as i64, (y - geometry[b].y).round() as i64);
501 93 : match counts.iter_mut().find(|(k, _)| *k == key) {
502 56 : Some((_, n)) => *n += 1,
503 37 : None => counts.push((key, 1)),
504 : }
505 6 : }
506 : }
507 : // The most frequent offset, the first one among equals
508 37 : if let Some(((dx, dy), _)) = counts.iter().fold(None::<&((i64, i64), usize)>, |best, c| if best.is_none_or(|b| c.1 > b.1) { Some(c) } else { best }) {
509 36 : offset = (*dx as f64, *dy as f64);
510 36 : }
511 106 : for &b in subset {
512 106 : geometry[b].x += offset.0;
513 106 : geometry[b].y += offset.1;
514 106 : }
515 40 : }
516 76 : let mut routes: Vec<DataflowEdgeRoute> = elk_edges
517 76 : .into_iter()
518 168 : .map(|(key, edge)| {
519 168 : let mut points = Vec::new();
520 168 : let mut edge = edge.borrow_mut();
521 168 : for section in edge.sections().iter() {
522 168 : let mut section = section.borrow_mut();
523 168 : points.push((section.start_x() + offset.0, section.start_y() + offset.1));
524 168 : points.extend(section.bend_points().iter().map(|p| (p.borrow().x() + offset.0, p.borrow().y() + offset.1)));
525 168 : points.push((section.end_x() + offset.0, section.end_y() + offset.1));
526 : }
527 168 : (key, points)
528 168 : })
529 76 : .collect();
530 76 : center_rails(&mut routes, subset, geometry);
531 76 : routes
532 76 : }
533 :
534 : /// ELK puts the vertical segments of the edges between two columns next to the left column, center them in the gap
535 : /// instead: away from the boxes on both sides. The segments of a gap move together, so their order and the space
536 : /// between them stay.
537 76 : fn center_rails(routes: &mut [DataflowEdgeRoute], subset: &[usize], geometry: &[DataflowBoxGeometry]) {
538 242 : let mut ranges: Vec<(f64, f64)> = subset.iter().map(|&b| (geometry[b].x, geometry[b].x + geometry[b].width)).collect();
539 202 : ranges.sort_by(|a, b| a.0.total_cmp(&b.0));
540 76 : let mut columns: Vec<(f64, f64)> = Vec::new();
541 242 : for (x0, x1) in ranges {
542 242 : match columns.last_mut() {
543 166 : Some(last) if x0 < last.1 => last.1 = last.1.max(x1),
544 184 : _ => columns.push((x0, x1)),
545 : }
546 : }
547 108 : for gap in columns.windows(2).map(|w| (w[0].1, w[1].0)) {
548 630 : let inside = |x: f64| x > gap.0 && x < gap.1;
549 108 : let rails: Vec<f64> =
550 508 : routes.iter().flat_map(|(_, points)| points.windows(2).filter(|w| w[0].0 == w[1].0 && inside(w[0].0)).map(|w| w[0].0)).collect();
551 108 : let (Some(lo), Some(hi)) = (rails.iter().copied().reduce(f64::min), rails.iter().copied().reduce(f64::max)) else { continue };
552 50 : let shift = ((gap.0 + gap.1) / 2.0 - (lo + hi) / 2.0).round();
553 155 : for (_, points) in routes.iter_mut() {
554 508 : for p in points.iter_mut().filter(|p| inside(p.0)) {
555 132 : p.0 += shift;
556 132 : }
557 : }
558 : }
559 76 : }
560 :
561 : #[cfg(test)]
562 : mod tests {
563 : use super::*;
564 :
565 44 : fn data(statements: u32) -> DataflowLayoutBox {
566 44 : DataflowLayoutBox { statements, ..Default::default() }
567 44 : }
568 :
569 10 : fn chart() -> DataflowLayoutBox {
570 10 : DataflowLayoutBox { statements: 1, chart_statement: Some(0), ..Default::default() }
571 10 : }
572 :
573 33 : fn edge(from_box: u32, from_statement: u32, to_box: u32, to_statement: u32) -> DataflowLayoutEdge {
574 33 : DataflowLayoutEdge { from_box, from_statement, to_box, to_statement }
575 33 : }
576 :
577 : /// The boxes with hints where a layout put them
578 10 : fn hinted(boxes: &[DataflowLayoutBox], geometry: &[DataflowBoxGeometry]) -> Vec<DataflowLayoutBox> {
579 57 : boxes.iter().zip(geometry).map(|(b, g)| DataflowLayoutBox { hint: Some((g.x, g.y)), ..b.clone() }).collect()
580 10 : }
581 :
582 : /// A source, two consumers of it, a chart of the first consumer, and a pair of boxes on their own
583 5 : fn two_parts() -> (Vec<DataflowLayoutBox>, Vec<DataflowLayoutEdge>) {
584 5 : let boxes = vec![data(2), data(1), data(1), chart(), data(1), data(1)];
585 5 : let edges = vec![edge(0, 0, 1, 0), edge(0, 1, 2, 0), edge(1, 0, 3, 0), edge(4, 0, 5, 0)];
586 5 : (boxes, edges)
587 5 : }
588 :
589 3 : fn assert_no_overlaps(geometry: &[DataflowBoxGeometry]) {
590 15 : for (i, a) in geometry.iter().enumerate() {
591 33 : for b in &geometry[i + 1..] {
592 33 : let overlap = a.x < b.x + b.width && b.x < a.x + a.width && a.y < b.y + b.height && b.y < a.y + a.height;
593 33 : assert!(!overlap, "{a:?} overlaps {b:?}");
594 : }
595 : }
596 3 : }
597 :
598 : #[test]
599 1 : fn box_geometry_stacks_rows_and_charts() {
600 1 : let config = DataflowLayoutConfig::default();
601 1 : let g = box_geometry(&DataflowLayoutBox { statements: 2, chart_statement: Some(0), ..Default::default() }, &config);
602 1 : assert_eq!(g.rows, vec![40.0, 40.0 + 32.0 + 8.0 + 200.0]);
603 1 : assert_eq!(g.height, 40.0 + 32.0 + 8.0 + 200.0 + 32.0 + 8.0);
604 : // A box with a chart is wider than a box without one
605 1 : assert_eq!(g.width, config.chart_box_width);
606 1 : assert_eq!(box_geometry(&DataflowLayoutBox { statements: 2, ..Default::default() }, &config).width, config.box_width);
607 : // A box with its own size, e.g. from a resized `@flow` tag
608 1 : let sized = DataflowLayoutBox { statements: 2, chart_statement: Some(0), width: Some(400.0), chart_height: Some(96.0), ..Default::default() };
609 1 : let sized = box_geometry(&sized, &config);
610 1 : assert_eq!(sized.width, 400.0);
611 1 : assert_eq!(sized.rows, vec![40.0, 40.0 + 32.0 + 8.0 + 96.0]);
612 1 : let collapsed = box_geometry(&DataflowLayoutBox { statements: 2, collapsed: true, ..Default::default() }, &config);
613 1 : assert_eq!(collapsed.height, 32.0);
614 1 : assert_eq!(collapsed.port(1, &config), 16.0);
615 1 : }
616 :
617 : #[test]
618 1 : fn flows_left_to_right_and_aligns_the_connected_rows() {
619 1 : let config = DataflowLayoutConfig::default();
620 1 : let boxes = [data(2), data(1), data(1)];
621 1 : let edges = [edge(0, 1, 1, 0), edge(1, 0, 2, 0)];
622 1 : let g = compute_dataflow_layout(&boxes, &edges, &config);
623 1 : assert!(g[0].x + g[0].width < g[1].x && g[1].x + g[1].width < g[2].x);
624 : // The row a box reads is level with the row it reads it from
625 1 : assert_eq!(g[0].y + g[0].port(1, &config), g[1].y + g[1].port(0, &config));
626 1 : assert_eq!(g[1].y + g[1].port(0, &config), g[2].y + g[2].port(0, &config));
627 1 : }
628 :
629 : #[test]
630 1 : fn survives_cycles() {
631 1 : let boxes = [data(1), data(1), data(1)];
632 1 : let edges = [edge(0, 0, 1, 0), edge(1, 0, 2, 0), edge(2, 0, 0, 0)];
633 1 : let (g, routes) = compute_dataflow_layout_with_routes(&boxes, &edges, &DataflowLayoutConfig::default());
634 1 : assert_no_overlaps(&g);
635 1 : assert_eq!(routes.len(), 3);
636 1 : }
637 :
638 : #[test]
639 1 : fn a_fan_out_stays_one_column() {
640 1 : let config = DataflowLayoutConfig::default();
641 1 : let boxes = [data(1), chart(), chart(), chart(), chart(), chart()];
642 5 : let edges: Vec<_> = (1..6).map(|i| edge(0, 0, i, 0)).collect();
643 1 : let g = compute_dataflow_layout(&boxes, &edges, &config);
644 5 : assert_eq!(g[1..].iter().map(|g| g.x as i64).collect::<BTreeSet<_>>().len(), 1);
645 : // In the order of the session, from top to bottom
646 4 : assert!(g[1..].windows(2).all(|w| w[0].y < w[1].y));
647 1 : assert_no_overlaps(&g);
648 1 : }
649 :
650 : #[test]
651 1 : fn boxes_without_edges_go_into_rows_below() {
652 1 : let config = DataflowLayoutConfig::default();
653 1 : let boxes = [data(1), data(1), data(1), data(1), data(1), data(1), data(1)];
654 1 : let g = compute_dataflow_layout(&boxes, &[edge(0, 0, 1, 0)], &config);
655 1 : let bottom = g[0].y.max(g[1].y) + 80.0;
656 5 : assert!(g[2..].iter().all(|b| b.y > bottom));
657 1 : assert_eq!(g[2].y, g[5].y);
658 1 : assert!(g[6].y > g[2].y);
659 1 : assert_eq!(g[6].x, g[2].x);
660 1 : }
661 :
662 : #[test]
663 1 : fn reload_reproduces_the_layout_and_its_routes() {
664 1 : let config = DataflowLayoutConfig::default();
665 1 : let (boxes, edges) = two_parts();
666 1 : let (first, routes) = compute_dataflow_layout_with_routes(&boxes, &edges, &config);
667 1 : assert_eq!(routes.len(), edges.len());
668 1 : let (reloaded, reloaded_routes) = compute_dataflow_layout_with_routes(&hinted(&boxes, &first), &edges, &config);
669 1 : assert_eq!(reloaded, first);
670 1 : assert_eq!(reloaded_routes, routes);
671 : // Orthogonal routes from the right border of the source row to the left border of the target row
672 4 : for ((from, fs, to, ts), points) in &routes {
673 4 : let (f, t) = (&first[*from as usize], &first[*to as usize]);
674 4 : assert_eq!(points.first(), Some(&(f.x + f.width, f.y + f.port(*fs, &config))));
675 4 : assert_eq!(points.last(), Some(&(t.x, t.y + t.port(*ts, &config))));
676 6 : assert!(points.windows(2).all(|w| w[0].0 == w[1].0 || w[0].1 == w[1].1));
677 : }
678 1 : }
679 :
680 : #[test]
681 1 : fn a_drop_keeps_the_y_and_the_column_and_leaves_the_others() {
682 1 : let config = DataflowLayoutConfig::default();
683 1 : let (boxes, edges) = two_parts();
684 1 : let first = compute_dataflow_layout(&boxes, &edges, &config);
685 : // The second consumer goes far down in its column
686 1 : let mut dropped = hinted(&boxes, &first);
687 1 : dropped[2].hint = Some((first[2].x + 20.0, first[2].y + 400.0));
688 1 : dropped[2].dropped = true;
689 1 : let after = compute_dataflow_layout(&dropped, &edges, &config);
690 1 : assert_eq!((after[2].x, after[2].y), (first[2].x, first[2].y + 400.0));
691 5 : for i in [0, 1, 3, 4, 5] {
692 5 : assert_eq!((after[i].x, after[i].y), (first[i].x, first[i].y), "box {i} moved");
693 : }
694 1 : assert_no_overlaps(&after);
695 : // The layout after the drop reloads as it is
696 1 : assert_eq!(compute_dataflow_layout(&hinted(&boxes, &after), &edges, &config), after);
697 1 : }
698 :
699 : #[test]
700 1 : fn a_drop_into_a_gap_makes_a_column() {
701 1 : let config = DataflowLayoutConfig::default();
702 1 : let (boxes, edges) = two_parts();
703 1 : let first = compute_dataflow_layout(&boxes, &edges, &config);
704 : // The chart of the first consumer is dropped with its center in the gap between the source and the consumers
705 1 : let mut dropped = hinted(&boxes, &first);
706 1 : let gap = (first[0].x + first[0].width + first[1].x) / 2.0;
707 1 : dropped[3].hint = Some((gap - first[3].width / 2.0, first[3].y));
708 1 : dropped[3].dropped = true;
709 1 : let after = compute_dataflow_layout(&dropped, &edges, &config);
710 : // The chart reads the first consumer, so its new column right of the source pushes the consumer right of it
711 1 : assert!(after[3].x > after[0].x + after[0].width);
712 1 : assert!(after[1].x > after[3].x + after[3].width);
713 : // The other part stays
714 1 : assert_eq!((after[4].x, after[4].y, after[5].x, after[5].y), (first[4].x, first[4].y, first[5].x, first[5].y));
715 1 : }
716 :
717 : #[test]
718 1 : fn a_box_without_a_hint_goes_next_to_its_producer() {
719 1 : let config = DataflowLayoutConfig::default();
720 1 : let (boxes, edges) = two_parts();
721 1 : let first = compute_dataflow_layout(&boxes, &edges, &config);
722 1 : let mut hints = hinted(&boxes, &first);
723 1 : hints[3].hint = None;
724 1 : let after = compute_dataflow_layout(&hints, &edges, &config);
725 1 : assert!(after[3].x > after[1].x + after[1].width);
726 : // Level with the row it reads
727 1 : assert_eq!(after[3].y + after[3].port(0, &config), after[1].y + after[1].port(0, &config));
728 5 : for i in [0, 1, 2, 4, 5] {
729 5 : assert_eq!((after[i].x, after[i].y), (first[i].x, first[i].y), "box {i} moved");
730 : }
731 1 : }
732 :
733 : #[test]
734 1 : fn rails_run_in_the_middle_of_the_gap_between_columns() {
735 1 : let config = DataflowLayoutConfig::default();
736 : // Two consumers of two rows, the lower one dropped further down: its edge needs a rail
737 1 : let boxes = [data(2), data(1), data(1)];
738 1 : let edges = [edge(0, 0, 1, 0), edge(0, 1, 2, 0)];
739 1 : let first = compute_dataflow_layout(&boxes, &edges, &config);
740 1 : let mut dropped = hinted(&boxes, &first);
741 1 : dropped[2].hint = Some((first[2].x, first[2].y + 200.0));
742 1 : dropped[2].dropped = true;
743 1 : let (g, routes) = compute_dataflow_layout_with_routes(&dropped, &edges, &config);
744 1 : let gap = (g[0].x + g[0].width, g[2].x);
745 2 : let rail = routes.iter().find(|(k, _)| k.2 == 2).unwrap().1.windows(2).find(|w| w[0].0 == w[1].0).unwrap()[0].0;
746 1 : assert!((rail - (gap.0 + gap.1) / 2.0).abs() <= 1.0, "rail at {rail} in {gap:?}");
747 1 : }
748 :
749 : #[test]
750 1 : fn a_drop_close_to_a_straight_edge_lines_up_the_rows() {
751 1 : let config = DataflowLayoutConfig::default();
752 1 : let (boxes, edges) = two_parts();
753 1 : let first = compute_dataflow_layout(&boxes, &edges, &config);
754 4 : let row = |g: &[DataflowBoxGeometry], b: usize, s: u32| g[b].y + g[b].port(s, &config);
755 : // The chart goes 400 down and an offset further, then its producer is dropped 400 down: the row of the
756 : // producer is the offset away from the row of the chart and lines up with it within `align_snap`
757 2 : for (offset, snaps) in [(10.0, true), (config.align_snap + 8.0, false)] {
758 2 : let mut dropped = hinted(&boxes, &first);
759 2 : dropped[3].hint = Some((first[3].x, first[3].y + 400.0 + offset));
760 2 : dropped[3].dropped = true;
761 2 : let moved = compute_dataflow_layout(&dropped, &edges, &config);
762 2 : let mut again = hinted(&boxes, &moved);
763 2 : again[1].hint = Some((moved[1].x, moved[1].y + 400.0));
764 2 : again[1].dropped = true;
765 2 : let after = compute_dataflow_layout(&again, &edges, &config);
766 2 : assert_eq!(row(&after, 1, 0) == row(&after, 3, 0), snaps, "offset {offset}");
767 : }
768 1 : }
769 :
770 : #[test]
771 1 : fn boxes_without_edges_keep_their_hints() {
772 1 : let config = DataflowLayoutConfig::default();
773 1 : let boxes = [DataflowLayoutBox { hint: Some((120.0, 40.0)), ..data(1) }, data(1)];
774 1 : let g = compute_dataflow_layout(&boxes, &[], &config);
775 1 : assert_eq!((g[0].x, g[0].y), (120.0, 40.0));
776 : // A box without a hint goes below, at their left edge
777 1 : assert_eq!(g[1].x, 120.0);
778 1 : assert!(g[1].y > 40.0 + g[0].height);
779 1 : }
780 : }
|
