OXYGENHUB
# fd3f920f0b24 oxygen / crates / oxy-core / src / lanes.rs
4.2 KiB · Rust · last changed Roadmap: phase A done 1 month ago source blame history raw
1 
//! Lane layout for drawing history as a graph: each change takes a lane,
2 
//! its first dependency continues that lane, other dependencies take free
3 
//! lanes, so edges flow from a change down to what it depends on. Shared
4 
//! by `oxy log` and hosts, so every view draws the same picture.
5
6 
use crate::hash::ChangeHash;
7 
use std::collections::{HashMap, HashSet};
8
9 
/// A row of the graph: the change's lane and the edges drawn from it.
10 
#[derive(Clone, Debug, PartialEq, Eq)]
11 
pub struct Row {
12 
    pub lane: usize,
13 
    /// `(from_lane, to_lane)` for each dependency drawn from this row to
14 
    /// the rows below.
15 
    pub edges: Vec<(usize, usize)>,
16 
    /// Lanes that pass through this row without touching it.
17 
    pub through: Vec<usize>,
18 
}
19
20 
/// `changes` newest first as `(hash, deps)`. A dependency outside the
21 
/// list ends its lane at the bottom.
22 
pub fn layout(changes: &[(ChangeHash, Vec<ChangeHash>)]) -> Vec<Row> {
23 
    let mut active: Vec<Option<ChangeHash>> = Vec::new();
24 
    let mut rows = Vec::with_capacity(changes.len());
25 
    let known: HashSet<&ChangeHash> = changes.iter().map(|(h, _)| h).collect();
26 
    let mut lanes: HashMap<ChangeHash, usize> = HashMap::new();
27 
    for (hash, deps) in changes {
28 
        let lane = match active.iter().position(|a| a.as_ref() == Some(hash)) {
29 
            Some(l) => l,
30 
            None => match active.iter().position(|a| a.is_none()) {
31 
                Some(l) => {
32 
                    active[l] = Some(*hash);
33 
                    l
34 
                }
35 
                None => {
36 
                    active.push(Some(*hash));
37 
                    active.len() - 1
38 
                }
39 
            },
40 
        };
41 
        lanes.insert(*hash, lane);
42 
        let mut edges = Vec::new();
43 
        let deps: Vec<&ChangeHash> = deps.iter().filter(|d| known.contains(d)).collect();
44 
        active[lane] = None;
45 
        for (i, d) in deps.iter().enumerate() {
46 
            let target = match active.iter().position(|a| a.as_ref() == Some(*d)) {
47 
                Some(l) => l,
48 
                None => {
49 
                    let l = if i == 0 && active[lane].is_none() {
50 
                        lane
51 
                    } else {
52 
                        match active.iter().position(|a| a.is_none()) {
53 
                            Some(l) => l,
54 
                            None => {
55 
                                active.push(None);
56 
                                active.len() - 1
57 
                            }
58 
                        }
59 
                    };
60 
                    active[l] = Some(**d);
61 
                    l
62 
                }
63 
            };
64 
            edges.push((lane, target));
65 
        }
66 
        let through: Vec<usize> = active
67 
            .iter()
68 
            .enumerate()
69 
            .filter(|(l, a)| a.is_some() && *l != lane && !edges.iter().any(|e| e.1 == *l))
70 
            .map(|(l, _)| l)
71 
            .collect();
72 
        rows.push(Row {
73 
            lane,
74 
            edges,
75 
            through,
76 
        });
77 
        while active.last().is_some_and(|a| a.is_none()) {
78 
            active.pop();
79 
        }
80 
    }
81 
    rows
82 
}
83
84 
/// The number of lanes the rows use.
85 
pub fn width(rows: &[Row]) -> usize {
86 
    rows.iter()
87 
        .map(|r| {
88 
            r.lane
89 
                .max(r.edges.iter().map(|e| e.1).max().unwrap_or(0))
90 
                .max(r.through.iter().copied().max().unwrap_or(0))
91 
        })
92 
        .max()
93 
        .map(|m| m + 1)
94 
        .unwrap_or(1)
95 
}
96
97 
#[cfg(test)]
98 
mod tests {
99 
    use super::*;
100 
    use crate::hash::ObjectRef;
101
102 
    fn h(n: u8) -> ChangeHash {
103 
        ObjectRef([n; 32])
104 
    }
105
106 
    #[test]
107 
    fn linear_history_is_one_lane() {
108 
        let rows = layout(&[(h(3), vec![h(2)]), (h(2), vec![h(1)]), (h(1), vec![])]);
109 
        assert!(rows.iter().all(|r| r.lane == 0), "{rows:?}");
110 
        assert_eq!(rows[0].edges, vec![(0, 0)]);
111 
        assert_eq!(width(&rows), 1);
112 
    }
113
114 
    #[test]
115 
    fn a_diamond_takes_two_lanes_and_rejoins() {
116 
        let rows = layout(&[
117 
            (h(4), vec![h(2), h(3)]),
118 
            (h(2), vec![h(1)]),
119 
            (h(3), vec![h(1)]),
120 
            (h(1), vec![]),
121 
        ]);
122 
        assert_eq!(rows[0].edges, vec![(0, 0), (0, 1)]);
123 
        assert_eq!(rows[2].lane, 1);
124 
        assert_eq!(
125 
            rows[2].edges,
126 
            vec![(1, 0)],
127 
            "the second branch joins the first lane"
128 
        );
129 
        assert_eq!(width(&rows), 2);
130 
    }
131 
}