lib/sql/src/branch.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const version = @import("version.zig");
3
4 const Allocator = std.mem.Allocator;
5
6 const BranchError = error{
7 CommitNotFound,
8 NonFastForward,
9 };
10
11 pub const Error = Allocator.Error || BranchError;
12
13 pub const CommitEntry = struct {
14 hash: version.Hash,
15 parents: []const version.Hash = &.{},
16 };
17
18 pub const Checkout = struct {
19 name: []const u8,
20 head: version.Hash,
21 working: version.WorkingSet,
22
23 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 }
30
31 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 }
38
39 pub fn stage(self: Checkout) Checkout {
40 return .{
41 .name = self.name,
42 .head = self.head,
43 .working = self.working.stage(),
44 };
45 }
46
47 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 };
55
56 const Ancestor = struct {
57 hash: version.Hash,
58 depth: usize,
59 };
60
61 const StackEntry = struct {
62 hash: version.Hash,
63 depth: usize,
64 };
65
66 pub fn commitEntry(commit: version.Commit) CommitEntry {
67 return .{
68 .hash = commit.hash,
69 .parents = commit.parents,
70 };
71 }
72
73 pub fn checkout(ref: version.Ref, root: version.Hash) Checkout {
74 return Checkout.init(ref, root);
75 }
76
77 pub fn canFastForward(allocator: Allocator, entries: []const CommitEntry, current: version.Hash, target: version.Hash) Error!bool {
78 return try containsAncestor(allocator, entries, target, current);
79 }
80
81 pub 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 }
85
86 pub 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);
91
92 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 }
107
108 return if (best) |ancestor| ancestor.hash else null;
109 }
110
111 fn 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 }
119
120 fn 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);
125
126 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 });
133
134 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 }
142
143 return found;
144 }
145
146 fn 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 }
152
153 fn 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 }
159
160 test "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 };
174
175 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));
177
178 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 }
186
187 test "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 };
201
202 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 }
205
206 test "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");
212
213 const initial = checkout(.{
214 .name = "main",
215 .target = head,
216 }, root);
217
218 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());
223
224 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());
228
229 const staged = changed.stage();
230 try std.testing.expect(staged.working.hasStaged());
231 try std.testing.expect(version.same(working, staged.working.staged));
232
233 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 }
239
240 test "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)};
244
245 try std.testing.expectError(error.CommitNotFound, canFastForward(std.testing.allocator, entries[0..], root_commit.hash, missing));
246 }