// 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, .{});
}