tiny.sql.branch

1const std = @import("std");2const version = @import("version.zig");34const Allocator = std.mem.Allocator;56const BranchError = error{7    CommitNotFound,8    NonFastForward,9};1011pub const Error = Allocator.Error || BranchError;1213pub const CommitEntry = struct {14    hash: version.Hash,15    parents: []const version.Hash = &.{},16};1718pub const Checkout = struct {19    name: []const u8,20    head: version.Hash,21    working: version.WorkingSet,2223    pub fn init(ref: version.Ref, root: version.Hash) Checkout {24        return .{25            .name = ref.name,26            .head = ref.target,27            .working = version.WorkingSet.init(root),28        };29    }3031    pub fn withWorking(self: Checkout, root: version.Hash) Checkout {32        return .{33            .name = self.name,34            .head = self.head,35            .working = self.working.withWorking(root),36        };37    }3839    pub fn stage(self: Checkout) Checkout {40        return .{41            .name = self.name,42            .head = self.head,43            .working = self.working.stage(),44        };45    }4647    pub fn advance(self: Checkout, head: version.Hash, root: version.Hash) Checkout {48        return .{49            .name = self.name,50            .head = head,51            .working = self.working.advance(root),52        };53    }54};5556const Ancestor = struct {57    hash: version.Hash,58    depth: usize,59};6061const StackEntry = struct {62    hash: version.Hash,63    depth: usize,64};6566pub fn commitEntry(commit: version.Commit) CommitEntry {67    return .{68        .hash = commit.hash,69        .parents = commit.parents,70    };71}7273pub fn checkout(ref: version.Ref, root: version.Hash) Checkout {74    return Checkout.init(ref, root);75}7677pub fn canFastForward(allocator: Allocator, entries: []const CommitEntry, current: version.Hash, target: version.Hash) Error!bool {78    return try containsAncestor(allocator, entries, target, current);79}8081pub fn fastForwardRef(allocator: Allocator, entries: []const CommitEntry, ref: *version.Ref, target: version.Hash) Error!void {82    if (!try canFastForward(allocator, entries, ref.target, target)) return error.NonFastForward;83    ref.target = target;84}8586pub fn mergeBase(allocator: Allocator, entries: []const CommitEntry, left: version.Hash, right: version.Hash) Error!?version.Hash {87    var left_ancestors = try ancestors(allocator, entries, left);88    defer left_ancestors.deinit(allocator);89    var right_ancestors = try ancestors(allocator, entries, right);90    defer right_ancestors.deinit(allocator);9192    var best: ?Ancestor = null;93    var best_score: usize = 0;94    for (left_ancestors.items) |left_ancestor| {95        for (right_ancestors.items) |right_ancestor| {96            if (!version.same(left_ancestor.hash, right_ancestor.hash)) continue;97            const score = left_ancestor.depth + right_ancestor.depth;98            if (best == null or score < best_score) {99                best = .{100                    .hash = left_ancestor.hash,101                    .depth = score,102                };103                best_score = score;104            }105        }106    }107108    return if (best) |ancestor| ancestor.hash else null;109}110111fn containsAncestor(allocator: Allocator, entries: []const CommitEntry, descendant: version.Hash, ancestor: version.Hash) Error!bool {112    var found = try ancestors(allocator, entries, descendant);113    defer found.deinit(allocator);114    for (found.items) |entry| {115        if (version.same(entry.hash, ancestor)) return true;116    }117    return false;118}119120fn ancestors(allocator: Allocator, entries: []const CommitEntry, start: version.Hash) Error!std.ArrayList(Ancestor) {121    var found: std.ArrayList(Ancestor) = .empty;122    errdefer found.deinit(allocator);123    var stack: std.ArrayList(StackEntry) = .empty;124    defer stack.deinit(allocator);125126    try stack.append(allocator, .{ .hash = start, .depth = 0 });127    while (stack.pop()) |next| {128        if (contains(found.items, next.hash)) continue;129        try found.append(allocator, .{130            .hash = next.hash,131            .depth = next.depth,132        });133134        const commit = find(entries, next.hash) orelse return error.CommitNotFound;135        for (commit.parents) |parent| {136            try stack.append(allocator, .{137                .hash = parent,138                .depth = next.depth + 1,139            });140        }141    }142143    return found;144}145146fn contains(entries: []const Ancestor, hash: version.Hash) bool {147    for (entries) |entry| {148        if (version.same(entry.hash, hash)) return true;149    }150    return false;151}152153fn find(entries: []const CommitEntry, hash: version.Hash) ?CommitEntry {154    for (entries) |entry| {155        if (version.same(entry.hash, hash)) return entry;156    }157    return null;158}159160test "branch fast-forward follows commit ancestry" {161    const root_commit = version.Commit.init(version.emptyHash("root"), &.{});162    var left_parents = [_]version.Hash{root_commit.hash};163    const left_commit = version.Commit.init(version.emptyHash("left"), left_parents[0..]);164    var right_parents = [_]version.Hash{left_commit.hash};165    const right_commit = version.Commit.init(version.emptyHash("right"), right_parents[0..]);166    var side_parents = [_]version.Hash{left_commit.hash};167    const side_commit = version.Commit.init(version.emptyHash("side"), side_parents[0..]);168    const entries = [_]CommitEntry{169        commitEntry(root_commit),170        commitEntry(left_commit),171        commitEntry(right_commit),172        commitEntry(side_commit),173    };174175    try std.testing.expect(try canFastForward(std.testing.allocator, entries[0..], left_commit.hash, right_commit.hash));176    try std.testing.expect(!try canFastForward(std.testing.allocator, entries[0..], side_commit.hash, right_commit.hash));177178    var ref = version.Ref{179        .name = "main",180        .target = left_commit.hash,181    };182    try fastForwardRef(std.testing.allocator, entries[0..], &ref, right_commit.hash);183    try std.testing.expect(version.same(ref.target, right_commit.hash));184    try std.testing.expectError(error.NonFastForward, fastForwardRef(std.testing.allocator, entries[0..], &ref, side_commit.hash));185}186187test "branch merge base chooses nearest common ancestor" {188    const root_commit = version.Commit.init(version.emptyHash("root"), &.{});189    var first_parents = [_]version.Hash{root_commit.hash};190    const first_commit = version.Commit.init(version.emptyHash("first"), first_parents[0..]);191    var left_parents = [_]version.Hash{first_commit.hash};192    const left_commit = version.Commit.init(version.emptyHash("left"), left_parents[0..]);193    var right_parents = [_]version.Hash{first_commit.hash};194    const right_commit = version.Commit.init(version.emptyHash("right"), right_parents[0..]);195    const entries = [_]CommitEntry{196        commitEntry(root_commit),197        commitEntry(first_commit),198        commitEntry(left_commit),199        commitEntry(right_commit),200    };201202    const base = (try mergeBase(std.testing.allocator, entries[0..], left_commit.hash, right_commit.hash)).?;203    try std.testing.expect(version.same(first_commit.hash, base));204}205206test "branch checkout keeps head and working state explicit" {207    const head = version.emptyHash("head-commit");208    const root = version.emptyHash("head-root");209    const working = version.emptyHash("working");210    const next = version.emptyHash("next-commit");211    const next_root = version.emptyHash("next-root");212213    const initial = checkout(.{214        .name = "main",215        .target = head,216    }, root);217218    try std.testing.expectEqualStrings("main", initial.name);219    try std.testing.expect(version.same(head, initial.head));220    try std.testing.expect(version.same(root, initial.working.base));221    try std.testing.expect(!initial.working.dirty());222    try std.testing.expect(!initial.working.hasStaged());223224    const changed = initial.withWorking(working);225    try std.testing.expect(version.same(head, changed.head));226    try std.testing.expect(changed.working.dirty());227    try std.testing.expect(!changed.working.hasStaged());228229    const staged = changed.stage();230    try std.testing.expect(staged.working.hasStaged());231    try std.testing.expect(version.same(working, staged.working.staged));232233    const advanced = staged.advance(next, next_root);234    try std.testing.expect(version.same(next, advanced.head));235    try std.testing.expect(version.same(next_root, advanced.working.base));236    try std.testing.expect(!advanced.working.dirty());237    try std.testing.expect(!advanced.working.hasStaged());238}239240test "branch ancestry rejects missing commits" {241    const root_commit = version.Commit.init(version.emptyHash("root"), &.{});242    const missing = version.emptyHash("missing");243    const entries = [_]CommitEntry{commitEntry(root_commit)};244245    try std.testing.expectError(error.CommitNotFound, canFastForward(std.testing.allocator, entries[0..], root_commit.hash, missing));246}

1pub const branch = @import("branch.zig");