OXYGENHUB
# eae595568832 oxygen / crates / oxy-core / src / lanes.rs
4.0 KiB · Rust · last changed State is Send + Sync; shared lane layout; log_window 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 { lane, edges, through });
73 
        while active.last().is_some_and(|a| a.is_none()) {
74 
            active.pop();
75 
        }
76 
    }
77 
    rows
78 
}
79
80 
/// The number of lanes the rows use.
81 
pub fn width(rows: &[Row]) -> usize {
82 
    rows.iter()
83 
        .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)))
84 
        .max()
85 
        .map(|m| m + 1)
86 
        .unwrap_or(1)
87 
}
88
89 
#[cfg(test)]
90 
mod tests {
91 
    use super::*;
92 
    use crate::hash::ObjectRef;
93
94 
    fn h(n: u8) -> ChangeHash {
95 
        ObjectRef([n; 32])
96 
    }
97
98 
    #[test]
99 
    fn linear_history_is_one_lane() {
100 
        let rows = layout(&[(h(3), vec![h(2)]), (h(2), vec![h(1)]), (h(1), vec![])]);
101 
        assert!(rows.iter().all(|r| r.lane == 0), "{rows:?}");
102 
        assert_eq!(rows[0].edges, vec![(0, 0)]);
103 
        assert_eq!(width(&rows), 1);
104 
    }
105
106 
    #[test]
107 
    fn a_diamond_takes_two_lanes_and_rejoins() {
108 
        let rows = layout(&[(h(4), vec![h(2), h(3)]), (h(2), vec![h(1)]), (h(3), vec![h(1)]), (h(1), vec![])]);
109 
        assert_eq!(rows[0].edges, vec![(0, 0), (0, 1)]);
110 
        assert_eq!(rows[2].lane, 1);
111 
        assert_eq!(rows[2].edges, vec![(1, 0)], "the second branch joins the first lane");
112 
        assert_eq!(width(&rows), 2);
113 
    }
114 
}