HAXY

▄▀▀▀ ▄ ▄▀▀▀▀▀▀▄ ▀▀▀▀▀▄ ▀▀▀▀▀▀▀▀▀▀ ▄▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀▄ ▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀ ▄▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▄▀▀▀ ▀▀▀▀▀▄▀▀▀▀ ▀ ▀▀▀▀▀▀▄▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀▄ ▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀ ▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▄ ▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄ ▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄ ▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ ▀▄ ▀▀▀▀▀▀▀▀▀▀▀▄▀▀▀▀▀▀ ▀▀ ▄▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ ▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄ ▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ ▀▀▀▀▄▄▄▄▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ ▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ ▀▀▄ ▀▀▀▀▄▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ ▄▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ ▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄▀▀▀▀▀▀▀▀▀▀▀ ▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄▀▀▀▀▀▀▀▀▀▀ ▀▄▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄▀▀▀▀▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ ▀ ▀▀▀▀ ▀▀▀▀▀▀▀▀▀ ▀▀▀▀▄▀▀▀▀▀▀ ▀ ▀▀ ▀▀▀▀▀▀▀▀▀ ▀▀▀▄▀▀▀▀▀▀▀ ▀ ▀▀ ▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀ ▀▄ ▀▀ ▀▀▀▀▀▀ ▀▀▀▀▀▀▀ ▀▀ ▀▀▀ ▀▀▀▀▀▀ ▀▀▀▀▀▀▄ ▀▀ ▀▀ ▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀ ▀ ▀▀▀ ▀▀▀▀▀▀▄▀ ▀▀▀▀▀▀▀ ▀ ▀▀▀ ▄▀▀▀▀▀▄▄ ▀▀▀▀▄▄▀▀ ▀ ▀▀▀ ▀▀▀▀▀▀▀▀▄ ▀▀▀▄▀▀▀ ▀▀ ▀▀▀ ▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀ ▀▀ ▀▀▀▀▀▀▀▀▀▀▀▄▀ ▀▀▀▀▀▀▀▀▄ ▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀ ▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄▄▀▀▀▀▀ ▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄▀▀▀ ▀▄ ▄▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄ ▀▀▄▀▀▀▄▀▀▀▀ ▀▀▀▀▄ ▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀ ▀▀ ▀▀▀▀▀ ▀▀▀

╭─────────────╮ │scroll to top│ ╰─────────────╯ ╭ search_commit.zig ────────────────────────────────────────────╮ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ╰───────────────────────────────────────────────────────────────╯

╭────╮ ╭ clone ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ╮ │http│ ssh │ │ ╰────╯ ╰ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ╯

77 const Oid = [hash.hexLen(repo_opts.hash)]u8; 78 const Tip = Commit(repo_opts.hash); 79 80 // one version to build: the commit it covers, and the commit whose version 81 // it derives from (null = walk the whole history). 82 const Work = struct { 83 oid: Oid, 84 timestamp: u64, 85 base: ?Oid, 86 }; 87 88 var arena = std.heap.ArenaAllocator.init(allocator); 89 defer arena.deinit(); 90 const aa = arena.allocator(); 91 92 var work: std.ArrayList(Work) = .empty; 93 var gone: std.ArrayList(Oid) = .empty; 94 var default_tip: ?Oid = null; 95 // the versions a new tip can derive from 96 var versions: std.ArrayList(Tip) = .empty; 97 98 // held across the reads and the writes, so a concurrent refresh can't 99 // change the entries these decisions were made from. 100 try repo.core.db_file.lock(io, .exclusive); 101 defer repo.core.db_file.unlock(io); 102 103 { 104 var moment = try repo.core.latestMoment(); 105 const state = Repo.State(.read_only){ .core = &repo.core, .extra = .{ .moment = &moment } }; 106 107 // the commits that already have a version 108 var existing: std.AutoArrayHashMapUnmanaged(Oid, void) = .empty; 109 if (try moment.getCursor(hash.hashInt(repo_opts.hash, index_key))) |index_cursor| { 110 const index = try DB.HashMap(.read_only).init(index_cursor); 111 var iter = try index.iterator(); 112 while (try iter.next()) |cursor| { 113 const pair = try cursor.readKeyValuePair(); 114 var oid_bytes: [hash.byteLen(repo_opts.hash)]u8 = undefined; 115 if ((try pair.key_cursor.readBytes(&oid_bytes)).len != oid_bytes.len) return error.InvalidCommitIndex; 116 try existing.put(aa, std.fmt.bytesToHex(oid_bytes, .lower), {}); 117 } 118 } 119 120 // what every head except the events branch and every tag points at 121 var tips: std.ArrayList(Oid) = .empty; 122 { 123 var branches = try repo.listBranches(io, allocator, .beginning); 124 defer branches.deinit(); 125 while (try branches.next()) |ref| { 126 if (std.mem.eql(u8, ref.name, evt.events_ref.name)) continue; 127 try tips.append(aa, (try repo.readRef(io, .{ .kind = .head, .name = ref.name })) orelse continue); 128 } 129 } 130 { 131 var tags = try repo.listTags(io, allocator, .beginning); 132 defer tags.deinit(); 133 while (try tags.next()) |ref| { 134 try tips.append(aa, (try repo.readRef(io, .{ .kind = .tag, .name = ref.name })) orelse continue); 135 } 136 } 137 138 // the commits a version is wanted for, annotated tags peeled. refs 139 // sharing a commit share its version. 140 var wanted: std.AutoArrayHashMapUnmanaged(Oid, void) = .empty; 141 var missing: std.AutoArrayHashMapUnmanaged(Oid, Work) = .empty; 142 for (tips.items) |tip| { 143 // a tip that already has a version needs no reading 144 if (existing.contains(tip)) { 145 try wanted.put(aa, tip, {}); 146 continue; 147 } 148 var commit = obj.Object(.xit, repo_opts).initCommit(state, io, allocator, &tip) catch continue; 149 defer commit.deinit(); 150 try wanted.put(aa, commit.oid, {}); 151 if (existing.contains(commit.oid)) continue; 152 const entry = try missing.getOrPut(aa, commit.oid); 153 if (!entry.found_existing) entry.value_ptr.* = .{ 154 .oid = commit.oid, 155 .timestamp = commit.content.commit.metadata.timestamp, 156 .base = null, 157 }; 158 if (entry.value_ptr.base == null) entry.value_ptr.base = pushedFrom(repo_opts, updates, &tip, existing); 159 } 160 161 var head_buffer: [rf.MAX_REF_CONTENT_SIZE]u8 = undefined; 162 if (repo.head(io, &head_buffer)) |head| switch (head) { 163 .ref => |ref| default_tip = try repo.readRef(io, .{ .kind = .head, .name = ref.name }), 164 .oid => {}, 165 } else |_| {} 166 167 // an entry whose commit is gone can't be walked from, so it isn't a 168 // candidate. 169 const unbased = for (missing.values()) |item| { 170 if (item.base == null) break true; 171 } else false; 172 if (unbased) for (existing.keys()) |oid| { 173 var commit = obj.Object(.xit, repo_opts).initCommit(state, io, allocator, &oid) catch continue; 174 defer commit.deinit(); 175 try versions.append(aa, .{ .oid = oid, .timestamp = commit.content.commit.metadata.timestamp }); 176 }; 177 178 try work.appendSlice(aa, missing.values()); 179 // oldest first, so a later tip derives from an earlier one 180 std.mem.sort(Work, work.items, {}, struct { 181 fn lessThan(_: void, a: Work, b: Work) bool { 182 return a.timestamp < b.timestamp; 183 } 184 }.lessThan); 185 186 for (existing.keys()) |oid| { 187 if (!wanted.contains(oid)) try gone.append(aa, oid); 188 } 189 } 190 191 if (work.items.len == 0 and gone.items.len == 0) return; 192 193 const Save = struct { 194 core: *Repo.Core, 195 io: std.Io, 196 allocator: std.mem.Allocator, 197 work: []const Work, 198 gone: []const Oid, 199 aa: std.mem.Allocator, 200 default_tip: ?Oid, 201 versions: *std.ArrayList(Tip), 202 203 pub fn run(ctx: @This(), cursor: *DB.Cursor(.read_write)) !void { 204 var moment = try DB.HashMap(.read_write).init(cursor.*); 205 const state = Repo.State(.read_write){ .core = ctx.core, .extra = .{ .moment = &moment } }; 206 const index_hash = hash.hashInt(repo_opts.hash, index_key); 207 208 var message: std.ArrayList(u8) = .empty; 209 defer message.deinit(ctx.allocator); 210 211 for (ctx.work) |item| { 212 const index = try DB.HashMap(.read_write).init(try moment.putCursor(index_hash)); 213 const base = item.base orelse nearestVersion(repo_opts.hash, ctx.versions.items, ctx.default_tip, item.timestamp); 214 215 var oid_bytes: [hash.byteLen(repo_opts.hash)]u8 = undefined; 216 _ = try std.fmt.hexToBytes(&oid_bytes, &item.oid); 217 const oid_int = hash.bytesToInt(repo_opts.hash, &oid_bytes); 218 try index.putKey(oid_int, .{ .bytes = &oid_bytes }); 219 var version_cursor = try index.putCursor(oid_int); 220 if (base) |base_oid| { 221 const base_cursor = (try index.getCursor(try hash.hexToInt(repo_opts.hash, &base_oid))) orelse return error.InvalidCommitIndex; 222 try version_cursor.write(.{ .slot = base_cursor.slot() }); 223 } 224 const version = try DB.SortedMap(.read_write).init(version_cursor); 225 226 var diff_arena = std.heap.ArenaAllocator.init(ctx.allocator); 227 defer diff_arena.deinit(); 228 const diff = try commitDiff(repo_opts, state.readOnly(), ctx.io, ctx.allocator, diff_arena.allocator(), if (base) |*base_oid| base_oid else null, &item.oid); 229 for (diff.removed) |commit| { 230 const key = try readPosting(repo_opts, state.readOnly(), ctx.io, ctx.allocator, &message, commit); 231 try srch.remove(DB, version, ctx.allocator, &key, message.items); 232 } 233 for (diff.added) |commit| { 234 const key = try readPosting(repo_opts, state.readOnly(), ctx.io, ctx.allocator, &message, commit); 235 try srch.add(DB, version, ctx.allocator, &key, message.items); 236 } 237 238 try ctx.versions.append(ctx.aa, .{ .oid = item.oid, .timestamp = item.timestamp }); 239 // the next version copies this one's slot, so everything 240 // written so far has to be shared rather than mutated 241 try ctx.core.db.freeze(); 242 } 243 244 // removing last keeps a tip that is going away available as a base 245 const index = try DB.HashMap(.read_write).init(try moment.putCursor(index_hash)); 246 for (ctx.gone) |oid| _ = try index.remove(try hash.hexToInt(repo_opts.hash, &oid)); 247 } 248 }; 249 250 const history = try DB.ArrayList(.read_write).init(repo.core.db.rootCursor()); 251 try history.appendContext(.{ .slot = try history.getSlot(-1) }, Save{ 252 .core = &repo.core, 253 .io = io, 254 .allocator = allocator, 255 .work = work.items, 256 .gone = gone.items, 257 .aa = aa, 258 .default_tip = default_tip, 259 .versions = &versions, 260 }); 261 } 262 263 // the version a tip committed at `timestamp` derives from when no push names 264 // one: the default branch's unless it is newer than the tip, else the nearest 265 // older one, else the oldest. a guess by dates that only the cost rides on. 266 fn nearestVersion( 267 comptime hash_kind: hash.HashKind, 268 versions: []const Commit(hash_kind), 269 default_tip: ?[hash.hexLen(hash_kind)]u8, 270 timestamp: u64, 271 ) ?[hash.hexLen(hash_kind)]u8 { 272 var older: ?Commit(hash_kind) = null; 273 var oldest: ?Commit(hash_kind) = null; 274 for (versions) |version| { 275 if (version.timestamp <= timestamp) { 276 if (default_tip) |oid| if (std.mem.eql(u8, &oid, &version.oid)) return oid; 277 const nearer = if (older) |found| version.timestamp > found.timestamp else true; 278 if (nearer) older = version; 279 } 280 const earlier = if (oldest) |found| version.timestamp < found.timestamp else true; 281 if (earlier) oldest = version; 282 } 283 return if (older orelse oldest) |version| version.oid else null; 284 } 285 286 // the commit this push moved a ref to `tip` from, when it has a version to 287 // derive from. 288 fn pushedFrom( 289 comptime repo_opts: rp.RepoOpts(.xit), 290 updates: ?[]const xit.net_server_receive_pack.AppliedRefUpdate, 291 tip: *const [hash.hexLen(repo_opts.hash)]u8, 292 existing: std.AutoArrayHashMapUnmanaged([hash.hexLen(repo_opts.hash)]u8, void), 293 ) ?[hash.hexLen(repo_opts.hash)]u8 { 294 for (updates orelse &.{}) |update| { 295 if (!std.mem.eql(u8, update.new_oid, tip)) continue; 296 if (update.old_oid.len != hash.hexLen(repo_opts.hash)) continue; 297 var oid: [hash.hexLen(repo_opts.hash)]u8 = undefined; 298 @memcpy(&oid, update.old_oid); 299 if (existing.contains(oid)) return oid; 300 } 301 return null; 302 } 303 304 // read `commit`'s message into `message` and return the doc key it indexes 305 // under. 306 fn readPosting( 307 comptime repo_opts: rp.RepoOpts(.xit), 308 state: rp.Repo(.xit, repo_opts).State(.read_only), 309 io: std.Io, 310 allocator: std.mem.Allocator, 311 message: *std.ArrayList(u8), 312 commit: Commit(repo_opts.hash), 313 ) ![docKeyLen(repo_opts.hash)]u8 { 314 message.clearRetainingCapacity(); 315 var object = try obj.Object(.xit, repo_opts).init(state, io, allocator, &commit.oid); 316 defer object.deinit(); 317 object.readMessage(allocator, message, .limited(srch.max_indexed_bytes)) catch |err| switch (err) { 318 // only the indexed prefix matters 319 error.StreamTooLong => {}, 320 else => |e| return e, 321 }; 322 return docKey(repo_opts.hash, commit.timestamp, &commit.oid); 323 } 324 325 // what `tip` reaches that `base_tip` doesn't, and the other way round, built 326 // into `aa`. with no base the whole history is added. 327 fn commitDiff( 328 comptime repo_opts: rp.RepoOpts(.xit), 329 state: rp.Repo(.xit, repo_opts).State(.read_only), 330 io: std.Io, 331 allocator: std.mem.Allocator, 332 aa: std.mem.Allocator, 333 base_tip: ?*const [hash.hexLen(repo_opts.hash)]u8, 334 tip: *const [hash.hexLen(repo_opts.hash)]u8, 335 ) !struct { removed: []const Commit(repo_opts.hash), added: []const Commit(repo_opts.hash) } { 336 var removed: std.ArrayList(Commit(repo_opts.hash)) = .empty; 337 var added: std.ArrayList(Commit(repo_opts.hash)) = .empty; 338 339 if (base_tip) |base| { 340 const Ancestry = mrg.Ancestry(.xit, repo_opts); 341 var ancestry = try Ancestry.init(state, io, allocator, base, tip); 342 defer ancestry.deinit(); 343 try ancestry.finish(); 344 345 // timestamps only choose the walk's order, so a commit the base reached 346 // can be passed before the tip turns out to reach it too. that can only 347 // make a removal wrong, never an addition. a fast-forward removes 348 // nothing, which the base tip picking up the tip's flag proves. anything 349 // else is settled by walking until nothing is left to carry down. 350 const base_node = ancestry.nodes.get(ancestry.tips[0]) orelse unreachable; 351 const fast_forward = base_node.flags & Ancestry.two != 0; 352 if (!fast_forward) { 353 var candidates = false; 354 var flagged = ancestry.nodes.valueIterator(); 355 while (flagged.next()) |node| { 356 if (node.flags & Ancestry.both == Ancestry.one) candidates = true; 357 } 358 if (candidates) while (try ancestry.step()) {}; 359 } 360 361 var iter = ancestry.nodes.iterator(); 362 while (iter.next()) |entry| { 363 // tag objects are peeled through, not walked 364 if (entry.value_ptr.tag_target != null) continue; 365 const commit = Commit(repo_opts.hash){ .oid = entry.key_ptr.*, .timestamp = entry.value_ptr.timestamp }; 366 switch (entry.value_ptr.flags & Ancestry.both) { 367 Ancestry.one => if (!fast_forward) try removed.append(aa, commit), 368 Ancestry.two => try added.append(aa, commit), 369 else => {}, 370 } 371 } 372 } else { 373 var iter = try obj.ObjectIterator(.xit, repo_opts).init(state, io, allocator, .{ .kind = .commit }); 374 defer iter.deinit(); 375 try iter.include(tip); 376 while (try iter.next(allocator)) |object| { 377 defer object.deinit(); 378 try added.append(aa, .{ .oid = object.oid, .timestamp = object.content.commit.metadata.timestamp }); 379 } 380 } 381 382 return .{ .removed = removed.items, .added = added.items }; 383 } 384