Skip to main content

triskel/
lib.rs

1//! Layered ("Sugiyama-style") directed graph layout, specialised for control
2//! flow graphs.
3//!
4//! Implements the algorithm from [Towards Better CFG Layouts][paper] (Royer,
5//! Tronel and Vinçont, Workshop on Binary Analysis Research 2025). The idea is
6//! that CFGs are not arbitrary graphs: they are built from nested
7//! single-entry/single-exit regions, and laying those out as units — rather
8//! than flattening everything into one layered pass — produces a drawing that
9//! matches how an analyst reads the code. See [`layout::LayoutMode::Sese`].
10//!
11//! The original C++ implementation lives at [triskellib/triskel].
12//!
13//! [paper]: https://hal.science/hal-04996939/
14//! [triskellib/triskel]: https://github.com/triskellib/triskel
15//!
16//! Pipeline (top-to-bottom, run per weakly-connected component):
17//!
18//! 1. [`cycle`] — reverse back-edges so the remaining phases see a DAG (rooted
19//!    at the entry, so the entry stays the top rank). Self-loops are held out of
20//!    the layered graph by [`layout`] and drawn as a loop off the node's right
21//!    face once it is positioned.
22//! 2. [`rank`] — assign each node a rank (layer) via network simplex.
23//! 3. [`segment`] — decompose long edges into Eiglsperger segments (p/q
24//!    endpoints + one pass-through segment), avoiding a dummy node per layer.
25//! 4. [`order`] — within-rank ordering / crossing reduction.
26//! 5. [`coordinate`] — x-coordinate assignment (segment-aware Brandes–Köpf).
27//! 6. [`router`] — turn the positioned graph into edge waypoints.
28//! 7. [`render`] — SVG/HTML output.
29//!
30//! The public entry point is [`layout::LayoutBuilder`]. By default each weak
31//! component runs as one flat layered graph. [`layout::LayoutMode::Sese`] is an
32//! opt-in CFG mode: canonical edge-based SESE regions are replaced by sized
33//! proxies, laid out bottom-up, expanded, and then routed through explicit
34//! obstacle-free boundary corridors. Weak components are still packed side by
35//! side.
36//!
37//! # Example
38//!
39//! ```
40//! use jstd::{Identifier, graph::owning::OwningGraph};
41//! use triskel::layout::{LayoutBuilder, NodeGeometry};
42//!
43//! #[derive(Identifier)]
44//! struct NodeId(usize);
45//! #[derive(Identifier)]
46//! struct EdgeId(usize);
47//!
48//! // A diamond: entry branches and rejoins.
49//! let mut graph = OwningGraph::<NodeId, EdgeId, (), ()>::default();
50//! let entry = graph.make_node(());
51//! let left = graph.make_node(());
52//! let right = graph.make_node(());
53//! let join = graph.make_node(());
54//! graph.make_edge(entry, left, ());
55//! graph.make_edge(entry, right, ());
56//! graph.make_edge(left, join, ());
57//! graph.make_edge(right, join, ());
58//!
59//! let layout = LayoutBuilder::new(&graph)
60//!     .root(entry)
61//!     .geometry(|_| NodeGeometry { width: 60.0, height: 30.0 })
62//!     .build()
63//!     .expect("the diamond lays out");
64//!
65//! // Every node has coordinates, and the entry is on the top rank.
66//! let entry_box = layout.get_node(entry).unwrap();
67//! for node in [left, right, join] {
68//!     assert!(layout.get_node(node).unwrap().y > entry_box.y);
69//! }
70//!
71//! let svg = layout.render_svg();
72//! assert!(svg.starts_with("<svg"));
73//! ```
74
75pub mod coordinate;
76pub mod cycle;
77pub mod energy;
78pub(crate) mod geometry;
79pub(crate) mod hammock;
80pub mod layout;
81pub mod order;
82pub mod rank;
83pub mod render;
84pub mod router;
85pub mod segment;