grit_lib/revwalk/graph/
layout.rs

1//! Lane-based graph layout (ASCII / Unicode) for commit history.
2
3use std::collections::HashMap;
4
5use crate::objects::ObjectId;
6
7/// Character set for graph rendering.
8#[derive(Clone, Copy, Debug, PartialEq, Eq)]
9pub struct GraphCharset {
10    /// Marker on the commit's lane (`*` or `●`).
11    pub commit: char,
12    /// Vertical lane continuation.
13    pub pipe: char,
14    /// Merge rail angling toward a secondary parent.
15    pub merge_right: char,
16    /// Merge rail angling from a secondary parent.
17    pub merge_left: char,
18    /// Reserved for octopus merge junctions.
19    pub merge_middle: char,
20}
21
22impl GraphCharset {
23    /// Git-compatible ASCII glyphs.
24    pub const ASCII: Self = Self {
25        commit: '*',
26        pipe: '|',
27        merge_right: '\\',
28        merge_left: '/',
29        merge_middle: '.',
30    };
31
32    /// Unicode box-drawing glyphs (when the terminal supports UTF-8).
33    pub const UNICODE: Self = Self {
34        commit: '●',
35        pipe: '│',
36        merge_right: '╲',
37        merge_left: '╱',
38        merge_middle: '┼',
39    };
40}
41
42/// One commit row fed into [`GraphLayout`].
43#[derive(Clone, Debug, PartialEq, Eq)]
44pub struct GraphCommitInput {
45    /// Commit id for this row.
46    pub id: ObjectId,
47    /// Display parents (already rewritten); newest-first walk uses parents stored oldest-first.
48    pub parents: Vec<ObjectId>,
49}
50
51/// Kind of graph line relative to a commit entry.
52#[derive(Clone, Copy, Debug, PartialEq, Eq)]
53pub enum GraphLineKind {
54    /// The line that carries the commit subject (contains the `*` marker).
55    Commit,
56    /// Extra graph padding before the next commit (merge rails).
57    Padding,
58}
59
60/// A rendered graph prefix (two columns per lane: glyph + space), without commit text.
61#[derive(Clone, Debug, PartialEq, Eq)]
62pub struct GraphRenderedLine {
63    /// Graph prefix; always ends with a space when non-empty.
64    pub prefix: String,
65    /// Whether this line is the commit line or padding.
66    pub kind: GraphLineKind,
67}
68
69/// Abstract lane topology for tests (column indices and parent edges).
70#[derive(Clone, Debug, PartialEq, Eq)]
71pub struct GraphRowTopology {
72    /// Column holding the commit marker for this row.
73    pub commit_column: usize,
74    /// Active lane indices after processing this row.
75    pub active_lanes: Vec<usize>,
76    /// Directed edges from child lane to parent lane for this commit.
77    pub edges: Vec<(usize, usize)>,
78}
79
80/// Incremental graph layout state.
81#[derive(Clone, Debug)]
82pub struct GraphLayout {
83    charset: GraphCharset,
84    /// Each lane tracks the next commit id flowing through it.
85    lanes: Vec<Option<ObjectId>>,
86    width: usize,
87    topologies: Vec<GraphRowTopology>,
88}
89
90impl Default for GraphLayout {
91    fn default() -> Self {
92        Self::new(GraphCharset::ASCII)
93    }
94}
95
96impl GraphLayout {
97    /// New layout using `charset`.
98    #[must_use]
99    pub fn new(charset: GraphCharset) -> Self {
100        Self {
101            charset,
102            lanes: Vec::new(),
103            width: 0,
104            topologies: Vec::new(),
105        }
106    }
107
108    /// Topologies recorded for each commit line (for unit tests).
109    #[must_use]
110    pub fn topologies(&self) -> &[GraphRowTopology] {
111        &self.topologies
112    }
113
114    /// Current graph width in columns (excluding trailing space after the last lane).
115    #[must_use]
116    pub fn width(&self) -> usize {
117        self.width
118    }
119
120    /// Consume commits in display order (newest first) and return graph lines grouped per commit.
121    #[must_use]
122    pub fn render(&mut self, commits: &[GraphCommitInput]) -> Vec<Vec<GraphRenderedLine>> {
123        let mut blocks = Vec::with_capacity(commits.len());
124        for commit in commits {
125            blocks.push(self.render_one(commit));
126        }
127        blocks
128    }
129
130    fn render_one(&mut self, commit: &GraphCommitInput) -> Vec<GraphRenderedLine> {
131        let parents = &commit.parents;
132        let mut lines = Vec::new();
133
134        if self.lanes_matching(commit.id) > 1 {
135            let pad = self.format_convergence();
136            self.width = self.width.max(pad.len());
137            lines.push(GraphRenderedLine {
138                prefix: pad,
139                kind: GraphLineKind::Padding,
140            });
141            self.collapse_lanes_to(commit.id);
142        }
143
144        let commit_lane = self.find_or_open_lane(commit.id);
145        let prefix = self.format_commit_row(commit_lane, parents);
146        self.width = self.width.max(prefix.len());
147        self.topologies
148            .push(self.record_topology(commit_lane, parents));
149        lines.push(GraphRenderedLine {
150            prefix,
151            kind: GraphLineKind::Commit,
152        });
153
154        if parents.len() > 1 {
155            let pad = self.format_post_merge(commit_lane);
156            self.width = self.width.max(pad.len());
157            lines.push(GraphRenderedLine {
158                prefix: pad,
159                kind: GraphLineKind::Padding,
160            });
161        }
162
163        self.advance_lanes(parents, commit_lane);
164        lines
165    }
166
167    fn lanes_matching(&self, id: ObjectId) -> usize {
168        self.lanes.iter().filter(|slot| **slot == Some(id)).count()
169    }
170
171    fn collapse_lanes_to(&mut self, id: ObjectId) {
172        let mut kept = false;
173        self.lanes.retain(|slot| {
174            if *slot == Some(id) {
175                if kept {
176                    return false;
177                }
178                kept = true;
179                return true;
180            }
181            slot.is_some()
182        });
183        if !kept {
184            self.lanes.push(Some(id));
185        }
186    }
187
188    fn find_or_open_lane(&mut self, id: ObjectId) -> usize {
189        if let Some(idx) = self.lanes.iter().position(|slot| *slot == Some(id)) {
190            return idx;
191        }
192        self.lanes.push(Some(id));
193        self.lanes.len() - 1
194    }
195
196    fn format_commit_row(&self, commit_lane: usize, parents: &[ObjectId]) -> String {
197        let cols = self.lane_count().max(commit_lane + 1);
198        let mut parts = Vec::with_capacity(cols);
199        for lane in 0..cols {
200            let cell = if lane == commit_lane {
201                if parents.len() > 1 {
202                    format!("{}   ", self.charset.commit)
203                } else {
204                    format!("{} ", self.charset.commit)
205                }
206            } else if self.lane_active(lane) {
207                format!("{} ", self.charset.pipe)
208            } else {
209                "  ".to_owned()
210            };
211            parts.push(cell);
212        }
213        parts.join("")
214    }
215
216    fn format_post_merge(&self, commit_lane: usize) -> String {
217        let cols = self.lane_count().max(commit_lane + 2);
218        let mut parts = Vec::with_capacity(cols);
219        for lane in 0..cols {
220            let cell = if lane == commit_lane {
221                format!("{} ", self.charset.pipe)
222            } else if lane == commit_lane + 1 {
223                format!("{} ", self.charset.merge_right)
224            } else if self.lane_active(lane) {
225                format!("{} ", self.charset.pipe)
226            } else {
227                "  ".to_owned()
228            };
229            parts.push(cell);
230        }
231        parts.join("")
232    }
233
234    fn format_convergence(&self) -> String {
235        let cols = self.lane_count();
236        let mut parts = Vec::with_capacity(cols);
237        for lane in 0..cols {
238            let cell = if lane == 0 {
239                format!("{}{} ", self.charset.pipe, self.charset.merge_left)
240            } else {
241                "  ".to_owned()
242            };
243            parts.push(cell);
244        }
245        parts.join("")
246    }
247
248    fn lane_count(&self) -> usize {
249        self.lanes.len()
250    }
251
252    fn lane_active(&self, lane: usize) -> bool {
253        self.lanes.get(lane).is_some_and(|s| s.is_some())
254    }
255
256    fn advance_lanes(&mut self, parents: &[ObjectId], commit_lane: usize) {
257        if parents.is_empty() {
258            if commit_lane < self.lanes.len() {
259                self.lanes[commit_lane] = None;
260            }
261            self.compact_lanes();
262            return;
263        }
264
265        let first = parents[0];
266        if commit_lane < self.lanes.len() {
267            self.lanes[commit_lane] = Some(first);
268        }
269
270        for &parent in parents.iter().skip(1) {
271            if self.lanes.contains(&Some(parent)) {
272                continue;
273            }
274            if let Some(empty) = self.lanes.iter().position(|slot| slot.is_none()) {
275                self.lanes[empty] = Some(parent);
276            } else {
277                self.lanes.push(Some(parent));
278            }
279        }
280        self.compact_lanes();
281    }
282
283    fn compact_lanes(&mut self) {
284        self.lanes.retain(|slot| slot.is_some());
285    }
286
287    fn record_topology(&self, commit_lane: usize, parents: &[ObjectId]) -> GraphRowTopology {
288        let mut edges = Vec::new();
289        let parent_to_lane: HashMap<ObjectId, usize> = self
290            .lanes
291            .iter()
292            .enumerate()
293            .filter_map(|(i, slot)| slot.map(|oid| (oid, i)))
294            .collect();
295        for parent in parents {
296            if let Some(&parent_lane) = parent_to_lane.get(parent) {
297                edges.push((commit_lane, parent_lane));
298            }
299        }
300        GraphRowTopology {
301            commit_column: commit_lane,
302            active_lanes: (0..self.lanes.len()).collect(),
303            edges,
304        }
305    }
306}
307
308#[cfg(test)]
309mod tests {
310    use super::*;
311    use crate::objects::ObjectId;
312
313    fn oid(n: u8) -> ObjectId {
314        ObjectId::from_bytes(&[n; 20]).expect("test oid")
315    }
316
317    fn flat_prefixes(blocks: &[Vec<GraphRenderedLine>]) -> String {
318        blocks
319            .iter()
320            .flat_map(|b| b.iter().map(|l| l.prefix.clone()))
321            .collect::<Vec<_>>()
322            .join("\n")
323    }
324
325    #[test]
326    fn graph_layout_linear() {
327        let c2 = oid(2);
328        let c1 = oid(1);
329        let c0 = oid(0);
330        let inputs = [
331            GraphCommitInput {
332                id: c2,
333                parents: vec![c1],
334            },
335            GraphCommitInput {
336                id: c1,
337                parents: vec![c0],
338            },
339            GraphCommitInput {
340                id: c0,
341                parents: vec![],
342            },
343        ];
344        let mut layout = GraphLayout::new(GraphCharset::ASCII);
345        let blocks = layout.render(&inputs);
346        assert!(flat_prefixes(&blocks).starts_with("* "));
347        assert_eq!(layout.topologies().len(), 3);
348    }
349
350    #[test]
351    fn graph_layout_merge_fork() {
352        let root = oid(0);
353        let main = oid(1);
354        let topic = oid(2);
355        let merge = oid(3);
356        let inputs = [
357            GraphCommitInput {
358                id: merge,
359                parents: vec![main, topic],
360            },
361            GraphCommitInput {
362                id: topic,
363                parents: vec![root],
364            },
365            GraphCommitInput {
366                id: main,
367                parents: vec![root],
368            },
369            GraphCommitInput {
370                id: root,
371                parents: vec![],
372            },
373        ];
374        let mut layout = GraphLayout::new(GraphCharset::ASCII);
375        let blocks = layout.render(&inputs);
376        let art = flat_prefixes(&blocks);
377        assert!(
378            art.contains('\\'),
379            "merge should draw a backslash rail: {art}"
380        );
381        assert!(art.contains('/'), "convergence should draw slash: {art}");
382        assert!(
383            art.contains("| *"),
384            "secondary branch should use pipe column: {art}"
385        );
386    }
387}
grit_lib/revwalk/graph/layout.rs

grit_lib/revwalk/graph/
layout.rs
