Something went wrong. Try again.
A history browser for git, a replacement for gitk, drawn with Vulkan on Wayland.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! Where each commit's node and edges go in the graph, worked out a row at//! a time as the history arrives.//!//! A lane is waiting for a commit: the parent some commit above it named.//! When that commit's row comes, it takes the leftmost lane waiting for it,//! and every other lane waiting for it converges on it there and is free.//! A commit no lane is waiting for — a branch's tip — takes the first free//! lane. Its first parent then goes on in its own lane, and each other//! parent joins a lane already waiting for that parent, or a free one.//!//! The history is in topological order, so a parent always comes after//! every child that names it, and a lane waiting for a commit is always//! met. A lane waiting for one that never comes — a parent outside the//! range asked for — runs to the bottom.//!//! Each line of descent has a color, given when it starts and kept, so//! that more history arriving never repaints what is already there.//!//! This is pure: commit IDs in, lanes and edges out, nothing about pixels.
const std = @import("std");const Allocator = std.mem.Allocator;
const ObjectId = @import("../history/History.zig").ObjectId;
const Layout = @This();
gpa: Allocator,rows: std.ArrayList(Row) = .empty,edges: std.ArrayList(Edge) = .empty,/// The lanes now, at the bottom of the last row: what each is waiting for,/// or null for a free one.lanes: std.ArrayList(?Slot) = .empty,next_color: u16 = 0,
pub const Lane = u16;
/// A lane waiting for a commit, and the color of the line in it.const Slot = struct { want: ObjectId, color: u16,};
/// Which part of a row an edge crosses: from the row's top to its node,/// from its node to its bottom, or the whole height, passing by.pub const Half = enum(u16) { top, bottom, full };
/// A line in a row from lane `from` to lane `to`. In the top half it ends/// at the node, in the bottom half it starts there.pub const Edge = extern struct { from: Lane, to: Lane, color: u16, half: Half,};
pub const Row = struct { /// The node's lane, and its color. lane: Lane, color: u16, /// How many lanes the row uses, at its top or its bottom. width: Lane, edges_start: u32, edges_len: u32,};
pub fn init(gpa: Allocator) Layout { return .{ .gpa = gpa };}
pub fn deinit(l: *Layout) void { l.rows.deinit(l.gpa); l.edges.deinit(l.gpa); l.lanes.deinit(l.gpa); l.* = undefined;}
/// Forgets everything, for a reload.pub fn clear(l: *Layout) void { l.rows.clearRetainingCapacity(); l.edges.clearRetainingCapacity(); l.lanes.clearRetainingCapacity(); l.next_color = 0;}
pub fn len(l: *const Layout) usize { return l.rows.items.len;}
pub fn edgesOf(l: *const Layout, row: *const Row) []const Edge { return l.edges.items[row.edges_start..][0..row.edges_len];}
pub const Error = Allocator.Error || error{ /// More lanes, rows or edges than are numbered. TooLarge,};
/// Lays out the next row: the commit `id`, whose parents are `parents`.pub fn add(l: *Layout, id: ObjectId, parents: []const ObjectId) Error!void { const gpa = l.gpa; const edges_start = std.math.cast(u32, l.edges.items.len) orelse return error.TooLarge; const width_before = l.lanes.items.len;
// Where the node goes: the leftmost lane waiting for it, or a free one. var node: ?usize = null; for (l.lanes.items, 0..) |slot, i| if (slot) |s| if (s.want.eql(id)) { node = i; break; }; const color: u16 = if (node) |n| l.lanes.items[n].?.color else l.newColor();
// The top half: what comes in. Every lane waiting for this commit ends // at the node; every other lane passes by, and is drawn once, whole, // below, if it still does at the bottom. var passing: std.ArrayList(Lane) = .empty; defer passing.deinit(gpa); for (l.lanes.items, 0..) |slot, i| { const s = slot orelse continue; if (s.want.eql(id)) { try l.edges.append(gpa, .{ .from = try lane(i), .to = try lane(node.?), .color = s.color, .half = .top }); l.lanes.items[i] = null; } else try passing.append(gpa, try lane(i)); } const node_lane = node orelse try l.freeLane();
// The bottom half: what goes out, to each parent's lane. if (parents.len > 0) { l.lanes.items[node_lane] = .{ .want = parents[0], .color = color }; try l.edges.append(gpa, .{ .from = try lane(node_lane), .to = try lane(node_lane), .color = color, .half = .bottom }); } for (parents[@min(1, parents.len)..]) |p| { // A merge's other parents: a lane already waiting for one, or a // line of descent of its own. const target, const c = for (l.lanes.items, 0..) |slot, i| { if (slot) |s| if (s.want.eql(p)) break .{ i, s.color }; } else blk: { const i = try l.freeLane(); const nc = l.newColor(); l.lanes.items[i] = .{ .want = p, .color = nc }; break :blk .{ i, nc }; }; try l.edges.append(gpa, .{ .from = try lane(node_lane), .to = try lane(target), .color = c, .half = .bottom }); } for (passing.items) |i| { const s = l.lanes.items[i].?; try l.edges.append(gpa, .{ .from = i, .to = i, .color = s.color, .half = .full }); }
const width = @max(width_before, l.lanes.items.len, node_lane + 1); while (l.lanes.items.len > 0 and l.lanes.items[l.lanes.items.len - 1] == null) _ = l.lanes.pop();
try l.rows.append(gpa, .{ .lane = try lane(node_lane), .color = color, .width = try lane(width), .edges_start = edges_start, .edges_len = @intCast(l.edges.items.len - edges_start), });}
/// The first free lane, opening one at the right if none is.fn freeLane(l: *Layout) Error!usize { for (l.lanes.items, 0..) |slot, i| if (slot == null) return i; if (l.lanes.items.len >= std.math.maxInt(Lane)) return error.TooLarge; try l.lanes.append(l.gpa, null); return l.lanes.items.len - 1;}
fn newColor(l: *Layout) u16 { defer l.next_color +%= 1; return l.next_color;}
fn lane(i: usize) Error!Lane { return std.math.cast(Lane, i) orelse error.TooLarge;}
// ---------------------------------------------------------------------------
const testing = std.testing;
fn testId(n: u32) ObjectId { var o: ObjectId = .{ .len = 20 }; std.mem.writeInt(u32, o.bytes[0..4], n + 1, .little); return o;}
/// Checks what has to hold of any layout: everything in bounds, and the/// lanes at the bottom of each row the same as those at the top of the/// next, so that every line is unbroken.fn check(l: *const Layout) !void { var below: std.AutoArrayHashMapUnmanaged(Lane, u16) = .empty; defer below.deinit(testing.allocator); for (l.rows.items, 0..) |*row, r| { try testing.expect(row.lane < row.width); var above: std.AutoArrayHashMapUnmanaged(Lane, u16) = .empty; defer above.deinit(testing.allocator); var next: std.AutoArrayHashMapUnmanaged(Lane, u16) = .empty; errdefer next.deinit(testing.allocator); for (l.edgesOf(row)) |e| { try testing.expect(e.from < row.width and e.to < row.width); switch (e.half) { .top => { try testing.expectEqual(row.lane, e.to); try above.put(testing.allocator, e.from, e.color); }, .bottom => { try testing.expectEqual(row.lane, e.from); try next.put(testing.allocator, e.to, e.color); }, .full => { try testing.expectEqual(e.from, e.to); try above.put(testing.allocator, e.from, e.color); try next.put(testing.allocator, e.to, e.color); }, } } // What came down from the row before is what this one takes in, // in the same colors. if (r > 0) { try testing.expectEqual(below.count(), above.count()); var it = below.iterator(); while (it.next()) |kv| try testing.expectEqual(kv.value_ptr.*, above.get(kv.key_ptr.*).?); } below.deinit(testing.allocator); below = next; }}
test "a straight line of commits is one lane" { var l: Layout = .init(testing.allocator); defer l.deinit(); try l.add(testId(0), &.{testId(1)}); try l.add(testId(1), &.{testId(2)}); try l.add(testId(2), &.{}); try check(&l); for (l.rows.items) |r| { try testing.expectEqual(@as(Lane, 0), r.lane); try testing.expectEqual(l.rows.items[0].color, r.color); } try testing.expectEqual(@as(usize, 0), l.lanes.items.len);}
test "a merge opens a lane, and the fork closes it" { var l: Layout = .init(testing.allocator); defer l.deinit(); // 0 merges 1 and 2, which both come from 3. try l.add(testId(0), &.{ testId(1), testId(2) }); try l.add(testId(1), &.{testId(3)}); try l.add(testId(2), &.{testId(3)}); try l.add(testId(3), &.{}); try check(&l); try testing.expectEqual(@as(Lane, 0), l.rows.items[0].lane); try testing.expectEqual(@as(Lane, 2), l.rows.items[0].width); try testing.expectEqual(@as(Lane, 0), l.rows.items[1].lane); try testing.expectEqual(@as(Lane, 1), l.rows.items[2].lane); // The fork: both lanes end on it. try testing.expectEqual(@as(Lane, 0), l.rows.items[3].lane); var tops: usize = 0; for (l.edgesOf(&l.rows.items[3])) |e| { if (e.half == .top) tops += 1; } try testing.expectEqual(@as(usize, 2), tops); // The merged branch has a color of its own, kept down its lane. try testing.expect(l.rows.items[2].color != l.rows.items[1].color);}
test "two tips take two lanes" { var l: Layout = .init(testing.allocator); defer l.deinit(); try l.add(testId(0), &.{testId(2)}); try l.add(testId(1), &.{testId(2)}); try l.add(testId(2), &.{}); try check(&l); try testing.expectEqual(@as(Lane, 1), l.rows.items[1].lane); // Lane 0 passes by row 1. var full: usize = 0; for (l.edgesOf(&l.rows.items[1])) |e| { if (e.half == .full and e.from == 0) full += 1; } try testing.expectEqual(@as(usize, 1), full);}
test "a freed lane is used again" { var l: Layout = .init(testing.allocator); defer l.deinit(); // 0 merges 1 and 2; 2 is a root, freeing lane 1; then 1 merges 3 and // 4, and 4 takes lane 1 again. try l.add(testId(0), &.{ testId(1), testId(2) }); try l.add(testId(2), &.{}); try l.add(testId(1), &.{ testId(3), testId(4) }); try l.add(testId(4), &.{}); try l.add(testId(3), &.{}); try check(&l); try testing.expectEqual(@as(Lane, 1), l.rows.items[3].lane); try testing.expectEqual(@as(Lane, 2), l.rows.items[3].width);}
test "a parent that never comes runs to the bottom" { var l: Layout = .init(testing.allocator); defer l.deinit(); try l.add(testId(0), &.{ testId(1), testId(99) }); try l.add(testId(1), &.{}); try check(&l); try testing.expectEqual(@as(usize, 2), l.lanes.items.len); try testing.expect(l.lanes.items[1].?.want.eql(testId(99)));}
test "any history in topological order lays out unbroken" { try std.testing.fuzz({}, struct { fn run(_: void, smith: *std.testing.Smith) anyerror!void { var l: Layout = .init(testing.allocator); defer l.deinit(); const n = smith.valueRangeLessThan(u32, 1, 80); var parents: [4]ObjectId = undefined; for (0..n) |i| { // Parents come later, as topological order has them; some // are outside the history altogether. const k = smith.valueRangeLessThan(u32, 0, 4); for (parents[0..k]) |*p| { p.* = testId(smith.valueRangeLessThan(u32, @intCast(i + 1), n + 4)); } try l.add(testId(@intCast(i)), parents[0..k]); } try check(&l); // Every lane still waiting is waiting for a commit that never // came. for (l.lanes.items) |slot| if (slot) |s| { const n_seen = std.mem.readInt(u32, s.want.bytes[0..4], .little) - 1; try testing.expect(n_seen >= n); }; } }.run, .{});}