gitlimes 0.1.0

Fast, low-memory git history CLI: colored log, branches, author stats and a unicode commit graph
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
//! Streaming lane assignment.
//!
//! A "lane" is a vertical column in the drawing. Each lane remembers the single
//! commit hash it is currently waiting to see. Because the state is one entry
//! per *open* lane rather than one per commit, memory is bounded by how many
//! branches are simultaneously in flight - typically a handful - and never by
//! the length of the history.

/// One open lane: the commit it waits for, plus a colour that stays with it for
/// its whole life so a branch keeps one colour even as it moves columns.
#[derive(Clone, Debug, PartialEq)]
struct Lane {
    waiting_for: String,
    color: usize,
    /// Value of `Lanes::clock` when a commit was last seen in this lane. Used
    /// to pick a victim when the table is full.
    touched: u64,
}

/// Hard ceiling on open lanes.
///
/// A lane is normally retired when the commit it waits for arrives. That
/// assumption breaks whenever git is not showing the whole graph - `--author`,
/// `--since`, a path filter, a shallow clone - because `%P` still names parents
/// the filter hides, and those lanes would wait forever. Left unbounded, the
/// table then grows with the number of commits shown, which is exactly the
/// thing this tool promises never to do.
///
/// Real unfiltered history stays far below this: the widest repository measured
/// during development peaked at 53 concurrent lanes.
pub const MAX_LANES: usize = 64;

/// What happened at one commit, in terms the renderer can draw without knowing
/// anything about git.
///
/// A commit occupies up to four rows, and the occupancy snapshots say which
/// lanes are drawn on each:
///
/// ```text
/// before   |/      lanes fold in from above
/// at       *       the commit itself
/// (at)     |\      lanes branch out below
/// after     /      lanes slide left into freed columns
/// ```
#[derive(Debug, PartialEq)]
pub struct Step {
    /// Column the commit's dot sits in.
    pub col: usize,
    /// Lane occupancy on the fold row, above the dot.
    pub before: Vec<bool>,
    /// Lane occupancy on the dot's own row.
    pub at: Vec<bool>,
    /// Lane occupancy on the shift row, before compaction slides lanes left.
    pub pre_shift: Vec<bool>,
    /// Lane occupancy once branching and compaction are done.
    pub after: Vec<bool>,
    /// Lanes that were also waiting for this commit and fold into `col`.
    /// These are fork points: one parent with two children.
    pub closing: Vec<usize>,
    /// Lanes this commit's extra parents continue in. An edge is drawn from
    /// `col` out to each of them.
    pub opening: Vec<usize>,
    /// Lanes sliding left to fill freed columns, as `(from, to)` pairs. Every
    /// move is exactly one column, so the shift reads as a single diagonal.
    pub shifts: Vec<(usize, usize)>,
    /// True when the commit has more than one parent.
    pub is_merge: bool,
    /// Lane colours by column, before compaction.
    pub colors: Vec<usize>,
    /// Lane colours by column, after compaction.
    pub colors_after: Vec<usize>,
    /// Colour of the commit's own dot.
    pub dot_color: usize,
}

impl Step {
    pub fn width(&self) -> usize {
        self.before
            .len()
            .max(self.at.len())
            .max(self.pre_shift.len())
            .max(self.after.len())
    }
}

#[derive(Default)]
pub struct Lanes {
    slots: Vec<Option<Lane>>,
    next_color: usize,
    clock: u64,
    evicted: bool,
}

impl Lanes {
    pub fn new() -> Lanes {
        Lanes::default()
    }

    /// True if some lane is waiting for this commit.
    #[cfg(test)]
    fn awaits(&self, hash: &str) -> bool {
        self.find(hash).is_some()
    }

    /// Number of currently open lanes. This is the whole of the graph's state,
    /// and the tests assert on it to pin the memory invariant.
    pub fn open(&self) -> usize {
        self.slots.iter().filter(|s| s.is_some()).count()
    }

    /// Highest column in use. Compaction keeps this close to `open()`; without
    /// it, closed lanes would leave holes and the drawing would drift right.
    pub fn width(&self) -> usize {
        self.slots
            .iter()
            .rposition(|s| s.is_some())
            .map_or(0, |i| i + 1)
    }

    pub fn advance(&mut self, hash: &str, parents: &[&str]) -> Step {
        self.clock += 1;
        let col = match self.find(hash) {
            Some(i) => i,
            // A commit nothing is waiting for is a branch tip; give it a lane.
            None => self.claim(hash),
        };
        if let Some(lane) = self.slots[col].as_mut() {
            lane.touched = self.clock;
        }

        let before = self.snapshot();

        // Any other lane waiting for this same commit is a second child; it
        // folds into this column.
        let mut closing = Vec::new();
        for j in 0..self.slots.len() {
            if j != col
                && self.slots[j]
                    .as_ref()
                    .is_some_and(|l| l.waiting_for == hash)
            {
                self.slots[j] = None;
                closing.push(j);
            }
        }

        let at = self.snapshot();
        let dot_color = self.slots[col].as_ref().map_or(0, |l| l.color);

        // The first parent inherits this lane - keeping its colour - so
        // mainline history stays in one straight, consistently coloured column.
        match parents.first() {
            Some(p) => {
                if let Some(lane) = self.slots[col].as_mut() {
                    lane.waiting_for = (*p).to_string();
                }
            }
            None => self.slots[col] = None,
        }

        let mut opening = Vec::new();
        for p in parents.iter().skip(1) {
            let k = match self.find(p) {
                Some(k) => k,
                None => self.claim(p),
            };
            if k != col {
                opening.push(k);
            }
        }

        let colors = self.color_map();
        let pre_shift = self.snapshot();
        let shifts = self.compact();

        Step {
            col,
            before,
            at,
            pre_shift,
            after: self.snapshot(),
            closing,
            opening,
            shifts,
            is_merge: parents.len() > 1,
            colors,
            colors_after: self.color_map(),
            dot_color,
        }
    }

    /// Slides every lane one column left where the column to its left is free.
    /// One pass moves each lane at most once, so the shift is always a single
    /// clean diagonal; repeated commits finish the job for wider gaps.
    fn compact(&mut self) -> Vec<(usize, usize)> {
        let mut shifts = Vec::new();
        for i in 0..self.slots.len().saturating_sub(1) {
            if self.slots[i].is_none() && self.slots[i + 1].is_some() {
                self.slots[i] = self.slots[i + 1].take();
                shifts.push((i + 1, i));
            }
        }
        while matches!(self.slots.last(), Some(None)) {
            self.slots.pop();
        }
        shifts
    }

    fn find(&self, hash: &str) -> Option<usize> {
        self.slots
            .iter()
            .position(|s| s.as_ref().is_some_and(|l| l.waiting_for == hash))
    }

    /// True once a lane has been evicted, which means the drawing has lost at
    /// least one edge and is no longer an exact rendering of the history.
    ///
    /// The caller is expected to say so rather than present an approximation as
    /// the real thing.
    pub fn evicted(&self) -> bool {
        self.evicted
    }

    /// Reuses the leftmost free lane so the drawing stays narrow.
    ///
    /// At [`MAX_LANES`] the table stops growing and the lane that has gone
    /// longest without a commit is evicted instead, so a filtered log whose
    /// parents never arrive cannot grow the table without bound.
    ///
    /// A lane touched by the commit currently being drawn is never a candidate.
    /// Every lane claimed during one `advance` shares the same `touched` value,
    /// so a plain "stalest wins" would pick the first of them - the commit's own
    /// column - and the merge would lose its own first-parent edge and later
    /// redraw that parent as an unrelated tip. When nothing else can be evicted,
    /// the table grows past the ceiling: the excess is bounded by one commit's
    /// parent count, which is a property of that commit and not of how long the
    /// history is.
    fn claim(&mut self, hash: &str) -> usize {
        let lane = Lane {
            waiting_for: hash.to_string(),
            color: self.next_color,
            touched: self.clock,
        };
        self.next_color = self.next_color.wrapping_add(1);
        if let Some(i) = self.slots.iter().position(|s| s.is_none()) {
            self.slots[i] = Some(lane);
            return i;
        }
        if self.slots.len() < MAX_LANES {
            self.slots.push(Some(lane));
            return self.slots.len() - 1;
        }
        let victim = self
            .slots
            .iter()
            .enumerate()
            .filter(|(_, s)| s.as_ref().is_some_and(|l| l.touched < self.clock))
            .min_by_key(|(_, s)| s.as_ref().map_or(0, |l| l.touched))
            .map(|(i, _)| i);
        match victim {
            Some(i) => {
                // An edge is about to be lost; the caller must not present the
                // result as an exact drawing.
                self.evicted = true;
                self.slots[i] = Some(lane);
                i
            }
            None => {
                self.slots.push(Some(lane));
                self.slots.len() - 1
            }
        }
    }

    /// Occupancy with trailing empties dropped, so row widths track the lanes
    /// actually in use.
    fn snapshot(&self) -> Vec<bool> {
        let mut v: Vec<bool> = self.slots.iter().map(|s| s.is_some()).collect();
        while matches!(v.last(), Some(false)) {
            v.pop();
        }
        v
    }

    fn color_map(&self) -> Vec<usize> {
        self.slots
            .iter()
            .map(|s| s.as_ref().map_or(0, |l| l.color))
            .collect()
    }
}

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

    #[test]
    fn linear_history_stays_in_one_lane() {
        let mut l = Lanes::new();
        let a = l.advance("a", &["b"]);
        let b = l.advance("b", &["c"]);
        let c = l.advance("c", &[]);
        for s in [&a, &b] {
            assert_eq!(s.col, 0);
            assert_eq!(s.before, vec![true]);
            assert_eq!(s.after, vec![true]);
            assert!(s.closing.is_empty() && s.opening.is_empty());
            assert!(s.shifts.is_empty());
        }
        // A root commit closes its lane.
        assert_eq!(c.at, vec![true]);
        assert_eq!(c.after, Vec::<bool>::new());
    }

    #[test]
    fn merge_opens_a_lane_and_fork_closes_it() {
        // m merges mainline `a` with side branch `s`; both reach root `r`.
        let mut l = Lanes::new();

        let m = l.advance("m", &["a", "s"]);
        assert_eq!(m.col, 0);
        assert!(m.is_merge);
        assert_eq!(m.at, vec![true], "the dot sits alone before branching");
        assert_eq!(m.opening, vec![1], "the side parent gets its own lane");
        assert_eq!(m.after, vec![true, true]);

        let a = l.advance("a", &["r"]);
        assert_eq!(a.col, 0);
        assert!(a.opening.is_empty() && a.closing.is_empty());

        let s = l.advance("s", &["r"]);
        assert_eq!(s.col, 1);
        // Both lanes now wait for r, but nothing folds until r is reached.
        assert_eq!(s.after, vec![true, true]);

        let r = l.advance("r", &[]);
        assert_eq!(r.col, 0, "the fork resolves into the leftmost lane");
        assert_eq!(r.before, vec![true, true], "both lanes are live above it");
        assert_eq!(r.closing, vec![1], "the second lane folds in");
        assert_eq!(r.at, vec![true], "and is gone by the dot's own row");
        assert_eq!(l.open(), 0);
    }

    #[test]
    fn octopus_merge_opens_every_extra_parent() {
        let mut l = Lanes::new();
        let m = l.advance("m", &["p1", "p2", "p3"]);
        assert!(m.is_merge);
        assert_eq!(m.opening, vec![1, 2]);
        assert_eq!(m.after, vec![true, true, true]);
        assert_eq!(l.open(), 3);
    }

    #[test]
    fn a_branch_keeps_its_colour_for_life() {
        let mut l = Lanes::new();
        let m = l.advance("m", &["a", "s"]);
        let side = m.colors_after[1];
        assert_ne!(side, m.dot_color, "a new branch gets its own colour");
        l.advance("a", &["r"]);
        let s = l.advance("s", &["r"]);
        assert_eq!(s.dot_color, side, "the side branch keeps that colour");
    }

    #[test]
    fn a_freed_column_is_closed_up_by_shifting() {
        // Lane 0 ends while lane 1 is still live; lane 1 must slide into it
        // rather than leaving a permanent hole.
        let mut l = Lanes::new();
        l.advance("m", &["a", "s"]);
        let a = l.advance("a", &[]);
        assert_eq!(a.shifts, vec![(1, 0)], "the live lane slides left");
        assert_eq!(a.after, vec![true]);
        assert_eq!(l.width(), 1, "no hole is left behind");
    }

    #[test]
    fn compaction_keeps_width_near_the_number_of_live_lanes() {
        // Open five lanes, then close the leftmost ones and confirm the table
        // closes up instead of drifting right.
        let mut l = Lanes::new();
        l.advance("m", &["p0", "p1", "p2", "p3", "p4"]);
        assert_eq!(l.width(), 5);
        for h in ["p0", "p1", "p2"] {
            l.advance(h, &[]);
        }
        // Two lanes remain; a few more commits let compaction finish closing up.
        for h in ["p3", "p4"] {
            l.advance(h, &[&format!("{}-next", h)]);
        }
        assert_eq!(l.open(), 2);
        assert_eq!(l.width(), 2, "width tracks live lanes, not peak lanes");
    }

    #[test]
    fn a_filtered_log_cannot_grow_the_lane_table_without_bound() {
        // Every commit names a parent that never arrives - what `--author`,
        // `--since` and path filters actually do, since %P still points at
        // commits the filter hides. Without a ceiling this grows one lane per
        // commit, which breaks the whole memory promise.
        let mut l = Lanes::new();
        for i in 0..5_000u32 {
            let hash = format!("commit-{}", i);
            let missing = format!("never-shown-{}", i);
            l.advance(&hash, &[missing.as_str()]);
            assert!(
                l.open() <= MAX_LANES,
                "lane table reached {} at commit {}",
                l.open(),
                i
            );
        }
        assert_eq!(l.open(), MAX_LANES, "the ceiling is what bounds it");
    }

    #[test]
    fn a_merge_wider_than_the_ceiling_keeps_every_parent() {
        // Every lane claimed during one advance shares the same `touched`, so a
        // plain "stalest wins" picked the first of them - the commit's own
        // column. The merge then lost its own first-parent edge, and that
        // parent was later redrawn as an unrelated tip.
        let parents: Vec<String> = (0..MAX_LANES + 2).map(|i| format!("p{:03}", i)).collect();
        let refs: Vec<&str> = parents.iter().map(String::as_str).collect();

        let mut l = Lanes::new();
        let s = l.advance("octopus", &refs);

        assert_eq!(
            s.opening.len(),
            refs.len() - 1,
            "every parent past the first needs its own lane"
        );
        assert!(
            l.awaits(&parents[0]),
            "the merge must still be waiting for its own first parent"
        );
        assert!(
            !l.evicted(),
            "growing for one commit's parents is not an eviction"
        );
        // The excess is bounded by this commit's parent count, not by history.
        assert_eq!(l.open(), refs.len());
    }

    #[test]
    fn eviction_is_reported_so_the_drawing_is_not_passed_off_as_exact() {
        let mut l = Lanes::new();
        assert!(!l.evicted());
        // Fill the table with lanes whose parents never arrive, then force one
        // more claim in a later tick so a stale lane is a valid victim.
        for i in 0..MAX_LANES as u32 {
            l.advance(&format!("c{}", i), &[format!("p{}", i).as_str()]);
        }
        assert_eq!(l.open(), MAX_LANES);
        assert!(!l.evicted(), "the table filled without evicting anything");

        l.advance("one-too-many", &["another"]);
        assert!(l.evicted(), "an edge was dropped and nobody was told");
    }

    #[test]
    fn eviction_takes_the_stalest_lane() {
        let mut l = Lanes::new();
        // Fill the table with lanes whose parents never arrive.
        for i in 0..MAX_LANES as u32 {
            l.advance(&format!("c{}", i), &[format!("p{}", i).as_str()]);
        }
        assert_eq!(l.open(), MAX_LANES);
        // Touch the oldest lane so it is no longer the stalest, then force an
        // eviction; that lane must survive.
        let revived = l.advance("p0", &["p0-next"]);
        let col = revived.col;
        l.advance("brand-new", &["another"]);
        assert!(
            l.awaits("p0-next"),
            "the freshly touched lane was evicted instead of a stale one"
        );
        let _ = col;
    }

    #[test]
    fn state_is_bounded_by_open_lanes_not_history() {
        let mut l = Lanes::new();
        // 10k linear commits must never grow the lane table past one entry.
        for i in 0..10_000u32 {
            let h = i.to_string();
            let p = (i + 1).to_string();
            l.advance(&h, &[p.as_str()]);
            assert_eq!(l.open(), 1);
        }
    }
}