lanes.rs 94.5%

188 of 199 lines run, 36 of 49 functions · run #394 on proposal/151 · run missed

//! Lane layout for drawing history as a graph: each change takes a lane,
//! its first dependency continues that lane, other dependencies take free
//! lanes, so edges flow from a change down to what it depends on. Shared
//! by `oxy log` and hosts, so every view draws the same picture.

use crate::hash::ChangeHash;
use std::collections::{HashMap, HashSet};

/// A row of the graph: the change's lane and the edges drawn from it.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Row {
    pub lane: usize,
    /// `(from_lane, to_lane)` for each dependency drawn from this row to
    /// the rows below.
    pub edges: Vec<(usize, usize)>,
    /// Lanes that pass through this row without touching it.
    pub through: Vec<usize>,
}

/// `changes` newest first as `(hash, deps)`. A dependency outside the
/// list ends its lane at the bottom.
pub fn layout(changes: &[(ChangeHash, Vec<ChangeHash>)]) -> Vec<Row> {
    let mut active: Vec<Option<ChangeHash>> = Vec::new();
    let mut rows = Vec::with_capacity(changes.len());
    let known: HashSet<&ChangeHash> = changes.iter().map(|(h, _)| h).collect();
    let mut lanes: HashMap<ChangeHash, usize> = HashMap::new();
    for (hash, deps) in changes {
        let lane = match active.iter().position(|a| a.as_ref() == Some(hash)) {
            Some(l) => l,
            None => match active.iter().position(|a| a.is_none()) {
                Some(l) => {
                    active[l] = Some(*hash);
                    l
                }
                None => {
                    active.push(Some(*hash));
                    active.len() - 1
                }
            },
        };
        lanes.insert(*hash, lane);
        let mut edges = Vec::new();
        let deps: Vec<&ChangeHash> = deps.iter().filter(|d| known.contains(d)).collect();
        active[lane] = None;
        for (i, d) in deps.iter().enumerate() {
            let target = match active.iter().position(|a| a.as_ref() == Some(*d)) {
                Some(l) => l,
                None => {
                    let l = if i == 0 && active[lane].is_none() {
                        lane
                    } else {
                        match active.iter().position(|a| a.is_none()) {
                            Some(l) => l,
                            None => {
                                active.push(None);
                                active.len() - 1
                            }
                        }
                    };
                    active[l] = Some(**d);
                    l
                }
            };
            edges.push((lane, target));
        }
        let through: Vec<usize> = active
            .iter()
            .enumerate()
            .filter(|(l, a)| a.is_some() && *l != lane && !edges.iter().any(|e| e.1 == *l))
            .map(|(l, _)| l)
            .collect();
        rows.push(Row {
            lane,
            edges,
            through,
        });
        while active.last().is_some_and(|a| a.is_none()) {
            active.pop();
        }
    }
    rows
}

/// The number of lanes the rows use.
pub fn width(rows: &[Row]) -> usize {
    rows.iter()
        .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))
        })
        .max()
        .map(|m| m + 1)
        .unwrap_or(1)
}

/// One cell of a graph row's lower line, the line under the change.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Cell {
    /// Nothing in this column.
    Blank,
    /// A lane carries on down.
    Line,
    /// The change's lane ends at a dependency not drawn (too far down, or
    /// not in the list): `~`.
    Elided,
    /// The left end of a join: this lane carries on, and the lane to its
    /// right turns into it (`├`).
    JoinLeft,
    /// A join passes a column with no lane (`─`).
    JoinPass,
    /// A join crosses a lane that carries on (`┼`).
    JoinCross,
    /// The right end of a join: this lane turns left and ends (`╯`).
    JoinRight,
}

/// A row of the drawn graph: the change's column, which other columns
/// carry a lane past it, and the line under it.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct GraphRow {
    pub column: usize,
    /// Columns with a lane on the change's own line, besides its own.
    pub passing: Vec<usize>,
    /// The line under the change, one cell per column.
    pub below: Vec<Cell>,
}

/// Lay out `changes` (newest first, as `(hash, deps)`) for a terminal
/// graph. A change's dependencies form a wide graph, since a change builds
/// on whatever last touched the lines it edits, so only one edge is drawn
/// per change: to its newest dependency, the change it most directly
/// builds on. An edge longer than `max_edge` rows, or to a change not in
/// the list, is elided (`~`), as are the other dependencies, so the
/// picture keeps to a few lanes. Two lanes heading for the same change
/// join into the left one.
pub fn graph(changes: &[(ChangeHash, Vec<ChangeHash>)], max_edge: usize) -> Vec<GraphRow> {
    let index: HashMap<&ChangeHash, usize> = changes
        .iter()
        .enumerate()
        .map(|(i, (h, _))| (h, i))
        .collect();
    let mut active: Vec<Option<ChangeHash>> = Vec::new();
    let mut rows = Vec::with_capacity(changes.len());
    for (i, (hash, deps)) in changes.iter().enumerate() {
        let column = match active.iter().position(|a| a.as_ref() == Some(hash)) {
            Some(c) => c,
            None => match active.iter().position(Option::is_none) {
                Some(c) => {
                    active[c] = Some(*hash);
                    c
                }
                None => {
                    active.push(Some(*hash));
                    active.len() - 1
                }
            },
        };
        let passing: Vec<usize> = active
            .iter()
            .enumerate()
            .filter(|(c, a)| *c != column && a.is_some())
            .map(|(c, _)| c)
            .collect();
        // The newest dependency below this row (the list is newest first).
        let nearest = deps
            .iter()
            .filter_map(|d| index.get(d).copied())
            .filter(|&j| j > i)
            .min();
        let parent = nearest.filter(|&j| j - i <= max_edge).map(|j| changes[j].0);
        active[column] = None;
        let mut join: Option<(usize, usize)> = None;
        if let Some(p) = parent {
            match active.iter().position(|a| a.as_ref() == Some(&p)) {
                // Another lane already heads there: join the two, leftwards.
                Some(other) => {
                    let (left, right) = (other.min(column), other.max(column));
                    active[right] = None;
                    active[left] = Some(p);
                    join = Some((left, right));
                }
                None => active[column] = Some(p),
            }
        }
        let width = active.len().max(column + 1);
        let mut below = vec![Cell::Blank; width];
        for (c, a) in active.iter().enumerate() {
            if a.is_some() {
                below[c] = Cell::Line;
            }
        }
        if let Some((left, right)) = join {
            below[left] = Cell::JoinLeft;
            for cell in below.iter_mut().take(right).skip(left + 1) {
                *cell = if *cell == Cell::Line {
                    Cell::JoinCross
                } else {
                    Cell::JoinPass
                };
            }
            below[right] = Cell::JoinRight;
        } else if parent.is_none() && !deps.is_empty() {
            below[column] = Cell::Elided;
        }
        while below.len() > 1 && below.last() == Some(&Cell::Blank) {
            below.pop();
        }
        rows.push(GraphRow {
            column,
            passing,
            below,
        });
        while active.last().is_some_and(Option::is_none) {
            active.pop();
        }
    }
    rows
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::hash::ObjectRef;

    fn h(n: u8) -> ChangeHash {
        ObjectRef([n; 32])
    }

    #[test]
    fn linear_history_is_one_lane() {
        let rows = layout(&[(h(3), vec![h(2)]), (h(2), vec![h(1)]), (h(1), vec![])]);
        assert!(rows.iter().all(|r| r.lane == 0), "{rows:?}");
        assert_eq!(rows[0].edges, vec![(0, 0)]);
        assert_eq!(width(&rows), 1);
    }

    #[test]
    fn a_diamond_takes_two_lanes_and_rejoins() {
        let rows = layout(&[
            (h(4), vec![h(2), h(3)]),
            (h(2), vec![h(1)]),
            (h(3), vec![h(1)]),
            (h(1), vec![]),
        ]);
        assert_eq!(rows[0].edges, vec![(0, 0), (0, 1)]);
        assert_eq!(rows[2].lane, 1);
        assert_eq!(
            rows[2].edges,
            vec![(1, 0)],
            "the second branch joins the first lane"
        );
        assert_eq!(width(&rows), 2);
    }

    #[test]
    fn the_graph_draws_the_newest_dependency_and_joins_lanes_left() {
        // 4 and 3 both build on 2; 2 on 1; 3 also depends on 1 (not drawn).
        let rows = graph(
            &[
                (h(4), vec![h(2)]),
                (h(3), vec![h(1), h(2)]),
                (h(2), vec![h(1)]),
                (h(1), vec![]),
            ],
            12,
        );
        assert_eq!(rows[0].column, 0);
        assert_eq!(rows[0].below, vec![Cell::Line]);
        assert_eq!(rows[1].column, 1, "a second head takes a new lane");
        assert_eq!(rows[1].passing, vec![0]);
        assert_eq!(rows[1].below, vec![Cell::JoinLeft, Cell::JoinRight]);
        assert_eq!(rows[2].column, 0);
        assert_eq!(rows[3].below, vec![Cell::Blank], "a root ends its lane");
    }

    #[test]
    fn a_long_edge_is_elided() {
        let mut changes = vec![(h(100), vec![h(1)])];
        for n in (2..=20).rev() {
            changes.push((h(n), vec![]));
        }
        changes.push((h(1), vec![]));
        let rows = graph(&changes, 5);
        assert_eq!(rows[0].below, vec![Cell::Elided]);
        assert!(
            rows.iter().all(|r| r.below.len() == 1),
            "one lane all the way"
        );
        let rows = graph(&changes, 100);
        assert_eq!(rows[0].below, vec![Cell::Line], "drawn when short enough");
    }
}

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

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	2×	pub fn layout(changes: &[(ChangeHash, Vec<ChangeHash>)]) -> Vec<Row> {
23	2×	let mut active: Vec<Option<ChangeHash>> = Vec::new();
24	2×	let mut rows = Vec::with_capacity(changes.len());
25	2×	let known: HashSet<&ChangeHash> = changes.iter().map(\|(h, _)\| h).collect();
26	2×	let mut lanes: HashMap<ChangeHash, usize> = HashMap::new();
27	7×	for (hash, deps) in changes {
28	7×	let lane = match active.iter().position(\|a\| a.as_ref() == Some(hash)) {
29	5×	Some(l) => l,
30	2×	None => match active.iter().position(\|a\| a.is_none()) {
31	0×	Some(l) => {
32	0×	active[l] = Some(*hash);
33	0×	l
34		}
35		None => {
36	2×	active.push(Some(*hash));
37	2×	active.len() - 1
38		}
39		},
40		};
41	7×	lanes.insert(*hash, lane);
42	7×	let mut edges = Vec::new();
43	7×	let deps: Vec<&ChangeHash> = deps.iter().filter(\|d\| known.contains(d)).collect();
44	7×	active[lane] = None;
45	7×	for (i, d) in deps.iter().enumerate() {
46	7×	let target = match active.iter().position(\|a\| a.as_ref() == Some(*d)) {
47	1×	Some(l) => l,
48		None => {
49	5×	let l = if i == 0 && active[lane].is_none() {
50	4×	lane
51		} else {
52	1×	match active.iter().position(\|a\| a.is_none()) {
53	0×	Some(l) => l,
54		None => {
55	1×	active.push(None);
56	1×	active.len() - 1
57		}
58		}
59		};
60	5×	active[l] = Some(**d);
61	5×	l
62		}
63		};
64	6×	edges.push((lane, target));
65		}
66	7×	let through: Vec<usize> = active
67	7×	.iter()
68	7×	.enumerate()
69	10×	.filter(\|(l, a)\| a.is_some() && l != lane && !edges.iter().any(\|e\| e.1 == l))
70	7×	.map(\|(l, _)\| l)
71	7×	.collect();
72	7×	rows.push(Row {
73	7×	lane,
74	7×	edges,
75	7×	through,
76	7×	});
77	10×	while active.last().is_some_and(\|a\| a.is_none()) {
78	3×	active.pop();
79	3×	}
80		}
81	2×	rows
82	2×	}
83
84		/// The number of lanes the rows use.
85	2×	pub fn width(rows: &[Row]) -> usize {
86	2×	rows.iter()
87	7×	.map(\|r\| {
88	7×	r.lane
89	7×	.max(r.edges.iter().map(\|e\| e.1).max().unwrap_or(0))
90	7×	.max(r.through.iter().copied().max().unwrap_or(0))
91	7×	})
92	2×	.max()
93	2×	.map(\|m\| m + 1)
94	2×	.unwrap_or(1)
95	2×	}
96
97		/// One cell of a graph row's lower line, the line under the change.
98		#[derive(Clone, Copy, Debug, PartialEq, Eq)]
99		pub enum Cell {
100		/// Nothing in this column.
101		Blank,
102		/// A lane carries on down.
103		Line,
104		/// The change's lane ends at a dependency not drawn (too far down, or
105		/// not in the list): `~`.
106		Elided,
107		/// The left end of a join: this lane carries on, and the lane to its
108		/// right turns into it (`├`).
109		JoinLeft,
110		/// A join passes a column with no lane (`─`).
111		JoinPass,
112		/// A join crosses a lane that carries on (`┼`).
113		JoinCross,
114		/// The right end of a join: this lane turns left and ends (`╯`).
115		JoinRight,
116		}
117
118		/// A row of the drawn graph: the change's column, which other columns
119		/// carry a lane past it, and the line under it.
120		#[derive(Clone, Debug, PartialEq, Eq)]
121		pub struct GraphRow {
122		pub column: usize,
123		/// Columns with a lane on the change's own line, besides its own.
124		pub passing: Vec<usize>,
125		/// The line under the change, one cell per column.
126		pub below: Vec<Cell>,
127		}
128
129		/// Lay out `changes` (newest first, as `(hash, deps)`) for a terminal
130		/// graph. A change's dependencies form a wide graph, since a change builds
131		/// on whatever last touched the lines it edits, so only one edge is drawn
132		/// per change: to its newest dependency, the change it most directly
133		/// builds on. An edge longer than `max_edge` rows, or to a change not in
134		/// the list, is elided (`~`), as are the other dependencies, so the
135		/// picture keeps to a few lanes. Two lanes heading for the same change
136		/// join into the left one.
137	4×	pub fn graph(changes: &[(ChangeHash, Vec<ChangeHash>)], max_edge: usize) -> Vec<GraphRow> {
138	4×	let index: HashMap<&ChangeHash, usize> = changes
139	4×	.iter()
140	4×	.enumerate()
141	50×	.map(\|(i, (h, _))\| (h, i))
142	4×	.collect();
143	4×	let mut active: Vec<Option<ChangeHash>> = Vec::new();
144	4×	let mut rows = Vec::with_capacity(changes.len());
145	50×	for (i, (hash, deps)) in changes.iter().enumerate() {
146	50×	let column = match active.iter().position(\|a\| a.as_ref() == Some(hash)) {
147	5×	Some(c) => c,
148	45×	None => match active.iter().position(Option::is_none) {
149	0×	Some(c) => {
150	0×	active[c] = Some(*hash);
151	0×	c
152		}
153		None => {
154	45×	active.push(Some(*hash));
155	45×	active.len() - 1
156		}
157		},
158		};
159	50×	let passing: Vec<usize> = active
160	50×	.iter()
161	50×	.enumerate()
162	71×	.filter(\|(c, a)\| *c != column && a.is_some())
163	50×	.map(\|(c, _)\| c)
164	50×	.collect();
165		// The newest dependency below this row (the list is newest first).
166	50×	let nearest = deps
167	50×	.iter()
168	50×	.filter_map(\|d\| index.get(d).copied())
169	50×	.filter(\|&j\| j > i)
170	50×	.min();
171	50×	let parent = nearest.filter(\|&j\| j - i <= max_edge).map(\|j\| changes[j].0);
172	50×	active[column] = None;
173	50×	let mut join: Option<(usize, usize)> = None;
174	50×	if let Some(p) = parent {
175	7×	match active.iter().position(\|a\| a.as_ref() == Some(&p)) {
176		// Another lane already heads there: join the two, leftwards.
177	2×	Some(other) => {
178	2×	let (left, right) = (other.min(column), other.max(column));
179	2×	active[right] = None;
180	2×	active[left] = Some(p);
181	2×	join = Some((left, right));
182	2×	}
183	5×	None => active[column] = Some(p),
184		}
185	43×	}
186	50×	let width = active.len().max(column + 1);
187	50×	let mut below = vec![Cell::Blank; width];
188	71×	for (c, a) in active.iter().enumerate() {
189	71×	if a.is_some() {
190	26×	below[c] = Cell::Line;
191	45×	}
192		}
193	50×	if let Some((left, right)) = join {
194	2×	below[left] = Cell::JoinLeft;
195	2×	for cell in below.iter_mut().take(right).skip(left + 1) {
196	0×	cell = if cell == Cell::Line {
197	0×	Cell::JoinCross
198		} else {
199	0×	Cell::JoinPass
200		};
201		}
202	2×	below[right] = Cell::JoinRight;
203	48×	} else if parent.is_none() && !deps.is_empty() {
204	1×	below[column] = Cell::Elided;
205	47×	}
206	69×	while below.len() > 1 && below.last() == Some(&Cell::Blank) {
207	19×	below.pop();
208	19×	}
209	50×	rows.push(GraphRow {
210	50×	column,
211	50×	passing,
212	50×	below,
213	50×	});
214	95×	while active.last().is_some_and(Option::is_none) {
215	45×	active.pop();
216	45×	}
217		}
218	4×	rows
219	4×	}
220
221		#[cfg(test)]
222		mod tests {
223		use super::*;
224		use crate::hash::ObjectRef;
225
226	43×	fn h(n: u8) -> ChangeHash {
227	43×	ObjectRef([n; 32])
228	43×	}
229
230		#[test]
231	1×	fn linear_history_is_one_lane() {
232	1×	let rows = layout(&[(h(3), vec![h(2)]), (h(2), vec![h(1)]), (h(1), vec![])]);
233	3×	assert!(rows.iter().all(\|r\| r.lane == 0), "{rows:?}");
234	1×	assert_eq!(rows[0].edges, vec![(0, 0)]);
235	1×	assert_eq!(width(&rows), 1);
236	1×	}
237
238		#[test]
239	1×	fn a_diamond_takes_two_lanes_and_rejoins() {
240	1×	let rows = layout(&[
241	1×	(h(4), vec![h(2), h(3)]),
242	1×	(h(2), vec![h(1)]),
243	1×	(h(3), vec![h(1)]),
244	1×	(h(1), vec![]),
245	1×	]);
246	1×	assert_eq!(rows[0].edges, vec![(0, 0), (0, 1)]);
247	1×	assert_eq!(rows[2].lane, 1);
248	1×	assert_eq!(
249	1×	rows[2].edges,
250	1×	vec![(1, 0)],
251		"the second branch joins the first lane"
252		);
253	1×	assert_eq!(width(&rows), 2);
254	1×	}
255
256		#[test]
257	1×	fn the_graph_draws_the_newest_dependency_and_joins_lanes_left() {
258		// 4 and 3 both build on 2; 2 on 1; 3 also depends on 1 (not drawn).
259	1×	let rows = graph(
260	1×	&[
261	1×	(h(4), vec![h(2)]),
262	1×	(h(3), vec![h(1), h(2)]),
263	1×	(h(2), vec![h(1)]),
264	1×	(h(1), vec![]),
265	1×	],
266		12,
267		);
268	1×	assert_eq!(rows[0].column, 0);
269	1×	assert_eq!(rows[0].below, vec![Cell::Line]);
270	1×	assert_eq!(rows[1].column, 1, "a second head takes a new lane");
271	1×	assert_eq!(rows[1].passing, vec![0]);
272	1×	assert_eq!(rows[1].below, vec![Cell::JoinLeft, Cell::JoinRight]);
273	1×	assert_eq!(rows[2].column, 0);
274	1×	assert_eq!(rows[3].below, vec![Cell::Blank], "a root ends its lane");
275	1×	}
276
277		#[test]
278	1×	fn a_long_edge_is_elided() {
279	1×	let mut changes = vec![(h(100), vec![h(1)])];
280	19×	for n in (2..=20).rev() {
281	19×	changes.push((h(n), vec![]));
282	19×	}
283	1×	changes.push((h(1), vec![]));
284	1×	let rows = graph(&changes, 5);
285	1×	assert_eq!(rows[0].below, vec![Cell::Elided]);
286	1×	assert!(
287	21×	rows.iter().all(\|r\| r.below.len() == 1),
288		"one lane all the way"
289		);
290	1×	let rows = graph(&changes, 100);
291	1×	assert_eq!(rows[0].below, vec![Cell::Line], "drawn when short enough");
292	1×	}
293		}

Coverage / crates/oxy-core/src/lanes.rs 94.5%

Keyboard