OXYGENHUB
# 19c71c828f86 oxygenhub / crates / hub / src / render / graph.rs
4.4 KiB · Rust · last changed Milestone 0.1: browse 1 month ago source blame history raw
1 
//! Lane layout for the history graph (hub spec §6.7): each change takes a
2 
//! lane, its first dependency continues that lane, other dependencies
3 
//! take free lanes, so edges flow downward from a change to what it
4 
//! depends on. Ported from the VS Code extension's webview.
5
6 
use std::collections::HashMap;
7
8 
/// A row of the graph: the change's lane and the edges to the rows below.
9 
#[derive(Clone, Debug, PartialEq, Eq)]
10 
pub struct Row {
11 
    pub lane: usize,
12 
    /// `(from_lane, to_lane)` for each dependency drawn from this row.
13 
    pub edges: Vec<(usize, usize)>,
14 
    /// Lanes that pass through this row without touching it.
15 
    pub through: Vec<usize>,
16 
}
17
18 
/// `changes` newest first as `(hash, deps)`. Dependencies outside the list
19 
/// end their lane at the bottom.
20 
pub fn layout(changes: &[(String, Vec<String>)]) -> Vec<Row> {
21 
    let mut active: Vec<Option<String>> = Vec::new();
22 
    let mut rows = Vec::with_capacity(changes.len());
23 
    let known: std::collections::HashSet<&str> = changes.iter().map(|(h, _)| h.as_str()).collect();
24 
    let mut lanes: HashMap<String, usize> = HashMap::new();
25 
    for (hash, deps) in changes {
26 
        let lane = match active.iter().position(|a| a.as_deref() == Some(hash)) {
27 
            Some(l) => l,
28 
            None => match active.iter().position(|a| a.is_none()) {
29 
                Some(l) => {
30 
                    active[l] = Some(hash.clone());
31 
                    l
32 
                }
33 
                None => {
34 
                    active.push(Some(hash.clone()));
35 
                    active.len() - 1
36 
                }
37 
            },
38 
        };
39 
        lanes.insert(hash.clone(), lane);
40 
        let mut edges = Vec::new();
41 
        let deps: Vec<&String> = deps.iter().filter(|d| known.contains(d.as_str())).collect();
42 
        active[lane] = None;
43 
        for (i, d) in deps.iter().enumerate() {
44 
            let target = match active.iter().position(|a| a.as_deref() == Some(d.as_str())) {
45 
                Some(l) => l,
46 
                None => {
47 
                    let l = if i == 0 && active[lane].is_none() {
48 
                        lane
49 
                    } else {
50 
                        match active.iter().position(|a| a.is_none()) {
51 
                            Some(l) => l,
52 
                            None => {
53 
                                active.push(None);
54 
                                active.len() - 1
55 
                            }
56 
                        }
57 
                    };
58 
                    active[l] = Some((*d).clone());
59 
                    l
60 
                }
61 
            };
62 
            edges.push((lane, target));
63 
        }
64 
        let through: Vec<usize> = active
65 
            .iter()
66 
            .enumerate()
67 
            .filter(|(l, a)| a.is_some() && *l != lane && !edges.iter().any(|e| e.1 == *l))
68 
            .map(|(l, _)| l)
69 
            .collect();
70 
        rows.push(Row { lane, edges, through });
71 
        // Trim trailing free lanes so the graph stays narrow.
72 
        while active.last().is_some_and(|a| a.is_none()) {
73 
            active.pop();
74 
        }
75 
    }
76 
    rows
77 
}
78
79 
pub fn width(rows: &[Row]) -> usize {
80 
    rows.iter()
81 
        .map(|r| r.lane.max(r.edges.iter().map(|e| e.1).max().unwrap_or(0)).max(r.through.iter().copied().max().unwrap_or(0)))
82 
        .max()
83 
        .map(|m| m + 1)
84 
        .unwrap_or(1)
85 
}
86
87 
#[cfg(test)]
88 
mod tests {
89 
    use super::*;
90
91 
    fn c(h: &str, deps: &[&str]) -> (String, Vec<String>) {
92 
        (h.into(), deps.iter().map(|d| d.to_string()).collect())
93 
    }
94
95 
    #[test]
96 
    fn linear_history_is_one_lane() {
97 
        let rows = layout(&[c("c", &["b"]), c("b", &["a"]), c("a", &[])]);
98 
        assert!(rows.iter().all(|r| r.lane == 0), "{rows:?}");
99 
        assert_eq!(rows[0].edges, vec![(0, 0)]);
100 
        assert_eq!(width(&rows), 1);
101 
    }
102
103 
    #[test]
104 
    fn independent_changes_take_lanes_and_rejoin() {
105 
        // d depends on b and c, which both depend on a: a diamond.
106 
        let rows = layout(&[c("d", &["b", "c"]), c("b", &["a"]), c("c", &["a"]), c("a", &[])]);
107 
        assert_eq!(rows[0].lane, 0);
108 
        assert_eq!(rows[0].edges, vec![(0, 0), (0, 1)]);
109 
        assert_eq!(rows[1].lane, 0);
110 
        assert_eq!(rows[2].lane, 1);
111 
        assert_eq!(rows[2].edges, vec![(1, 0)], "c joins a's lane");
112 
        assert_eq!(rows[3].lane, 0);
113 
        assert_eq!(width(&rows), 2);
114 
        // Two heads with no common change: two lanes throughout.
115 
        let rows = layout(&[c("x", &[]), c("y", &[])]);
116 
        assert_eq!((rows[0].lane, rows[1].lane), (0, 0), "a lane is reused once its change is drawn");
117 
    }
118 
}