🬐 🬠 🬞🬂🬏 🬟 🬑 🬟 🬑 642c6a16.. ╭642c6a16..╮ see-em: 🬋🬋🬋 🬋🬋🬋 🬋 🬋 files │diff │ refs discuss issues new login 🬐 🬠 🬐 🬠 🬑 🬟 🬰 ╰──────────╯ user
╭──────────╮ │← previous│ ╰──────────╯ ╭ changed ────────────╮ │src/search_commit.zig│ ╰─────────────────────╯ ╭─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╮ │202 if (rf.readHead(.xit, repo_opts, read_state, io, &head_buffer) catch null) |head| switch (head) { │ │203 .ref => |ref| default_tip = try rf.readRecur(.xit, repo_opts, read_state, io, .{ .ref = .{ .kind = .head, .name = ref.name } }),│ │204 .oid => {}, │ │206 - }; │ │207 - │ │208 - // an entry whose commit is gone can't be walked from, so it isn't a │ │209 - // candidate. │ │210 - const unbased = for (missing.values()) |item| { │ │211 - if (item.base == null) break true; │ │212 - } else false; │ │213 - if (unbased) for (existing.keys()) |oid| { │ │214 - var commit = obj.Object(.xit, repo_opts).initCommit(read_state, io, allocator, &oid) catch continue; │ │215 - defer commit.deinit(); │ │216 - try versions.append(aa, .{ .oid = oid, .timestamp = commit.content.commit.metadata.timestamp }); │ │205 }; │ │206 │ │207 try work.appendSlice(aa, missing.values()); │ ╰─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯ ╭─────────────────────────────────────────────────────────────────────╮ │212 } │ │213 }.lessThan); │ │214 │ │227 - for (existing.keys()) |oid| { │ │215 + for (versions.keys()) |oid| { │ │216 if (!wanted.contains(oid)) try gone.append(aa, oid);│ │217 } │ │218 } │ ╰─────────────────────────────────────────────────────────────────────╯ ╭──────────────────────────────────────────────────────────────────────────────────────────────────╮ │221 │ │222 { │ │223 const index_hash = hash.hashInt(repo_opts.hash, index_key); │ │236 - │ │237 - var message: std.ArrayList(u8) = .empty; │ │238 - defer message.deinit(allocator); │ │224 │ │225 for (work.items) |item| { │ │226 const index = try DB.HashMap(.read_write).init(try moment.putCursor(index_hash));│ ╰──────────────────────────────────────────────────────────────────────────────────────────────────╯ ╭────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╮ │242 - const base = item.base orelse nearestVersion(repo_opts.hash, versions.items, default_tip, item.timestamp); │ │227 + const base = item.base orelse nearestVersion(repo_opts.hash, versions, default_tip, item.timestamp); │ │228 │ │244 - var oid_bytes: [hash.byteLen(repo_opts.hash)]u8 = undefined; │ │245 - _ = try std.fmt.hexToBytes(&oid_bytes, &item.oid); │ │246 - const oid_int = hash.bytesToInt(repo_opts.hash, &oid_bytes); │ │247 - try index.putKey(oid_int, .{ .bytes = &oid_bytes }); │ │229 + var entry: Entry = undefined; │ │230 + _ = try std.fmt.hexToBytes(entry[0..oid_len], &item.oid); │ │231 + std.mem.writeInt(u64, entry[oid_len..], item.timestamp, .big); │ │232 + const oid_int = hash.bytesToInt(repo_opts.hash, entry[0..oid_len]); │ │233 + try index.putKey(oid_int, .{ .bytes = &entry }); │ │234 var version_cursor = try index.putCursor(oid_int); │ │235 if (base) |base_oid| { │ │236 const base_cursor = (try index.getCursor(try hash.hexToInt(repo_opts.hash, &base_oid))) orelse return error.InvalidCommitIndex;│ ╰────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯ ╭──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╮ │237 try version_cursor.write(.{ .slot = base_cursor.slot() }); │ │238 } │ │239 const version = try DB.SortedMap(.read_write).init(version_cursor); │ │254 - │ │255 - var diff_arena = std.heap.ArenaAllocator.init(allocator); │ │256 - defer diff_arena.deinit(); │ │257 - const diff = try commitDiff(repo_opts, state.readOnly(), io, allocator, diff_arena.allocator(), if (base) |*base_oid| base_oid else null, &item.oid, progress_ctx_maybe);│ │240 │ │259 - // the walk is done, so the messages left to read are the total │ │260 - progress.report(repo_opts, io, progress_ctx_maybe, .{ .text = "Indexing commits" }); │ │261 - progress.report(repo_opts, io, progress_ctx_maybe, .{ .start = .{ .kind = .writing_patch, .estimated_total_items = diff.removed.len + diff.added.len } }); │ │262 - for (diff.removed) |commit| { │ │263 - if (progress.cancelled(repo_opts, progress_ctx_maybe)) return error.ClientGone; │ │264 - defer progress.report(repo_opts, io, progress_ctx_maybe, .{ .complete_one = .writing_patch }); │ │265 - const key = try readPosting(repo_opts, state.readOnly(), io, allocator, &message, commit); │ │266 - try srch.remove(DB, version, allocator, &key, message.items); │ │267 - } │ │268 - for (diff.added) |commit| { │ │269 - if (progress.cancelled(repo_opts, progress_ctx_maybe)) return error.ClientGone; │ │270 - defer progress.report(repo_opts, io, progress_ctx_maybe, .{ .complete_one = .writing_patch }); │ │271 - const key = try readPosting(repo_opts, state.readOnly(), io, allocator, &message, commit); │ │272 - try srch.add(DB, version, allocator, &key, message.items); │ │241 + if (base) |*base_oid| { │ │242 + try derive(repo_opts, state.readOnly(), io, allocator, version, base_oid, &item.oid, progress_ctx_maybe); │ │243 + } else { │ │244 + try indexHistory(repo_opts, state.readOnly(), io, allocator, version, &item.oid, progress_ctx_maybe); │ │245 } │ │274 - progress.report(repo_opts, io, progress_ctx_maybe, .{ .end = .writing_patch }); │ │246 │ │276 - try versions.append(aa, .{ .oid = item.oid, .timestamp = item.timestamp }); │ │247 + try versions.put(aa, item.oid, item.timestamp); │ │248 // the next version copies this one's slot, so everything │ │249 // written so far has to be shared rather than mutated │ │250 try state.core.db.freeze(); │ ╰──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯ ╭───────────────────────────────────────────────────────────────────────────────────╮ │257 return true; │ │258 } │ │259 │ │289 -// the version a tip committed at `timestamp` derives from when no push names │ │260 +// the version a tip committed at `timestamp` derives from when no move names │ │261 // one: the default branch's unless it is newer than the tip, else the nearest│ │262 // older one, else the oldest. a guess by dates that only the cost rides on. │ │263 fn nearestVersion( │ ╰───────────────────────────────────────────────────────────────────────────────────╯ ╭──────────────────────────────────────────────────────────────────────────────────╮ │264 comptime hash_kind: hash.HashKind, │ │294 - versions: []const Commit(hash_kind), │ │265 + versions: std.AutoArrayHashMapUnmanaged([hash.hexLen(hash_kind)]u8, u64),│ │266 default_tip: ?[hash.hexLen(hash_kind)]u8, │ │267 timestamp: u64, │ │268 ) ?[hash.hexLen(hash_kind)]u8 { │ ╰──────────────────────────────────────────────────────────────────────────────────╯ ╭─────────────────────────────────────────────────────────────────────────────────────────────────╮ │298 - var older: ?Commit(hash_kind) = null; │ │299 - var oldest: ?Commit(hash_kind) = null; │ │300 - for (versions) |version| { │ │301 - if (version.timestamp <= timestamp) { │ │302 - if (default_tip) |oid| if (std.mem.eql(u8, &oid, &version.oid)) return oid; │ │303 - const nearer = if (older) |found| version.timestamp > found.timestamp else true;│ │304 - if (nearer) older = version; │ │269 + var older: ?[hash.hexLen(hash_kind)]u8 = null; │ │270 + var older_timestamp: u64 = 0; │ │271 + var oldest: ?[hash.hexLen(hash_kind)]u8 = null; │ │272 + var oldest_timestamp: u64 = std.math.maxInt(u64); │ │273 + for (versions.keys(), versions.values()) |oid, version_timestamp| { │ │274 + if (version_timestamp <= timestamp) { │ │275 + if (default_tip) |tip| if (std.mem.eql(u8, &tip, &oid)) return tip; │ │276 + if (older == null or version_timestamp > older_timestamp) { │ │277 + older = oid; │ │278 + older_timestamp = version_timestamp; │ │279 + } │ │280 } │ │306 - const earlier = if (oldest) |found| version.timestamp < found.timestamp else true; │ │307 - if (earlier) oldest = version; │ │281 + if (version_timestamp < oldest_timestamp) { │ │282 + oldest = oid; │ │283 + oldest_timestamp = version_timestamp; │ │284 + } │ │285 } │ │309 - return if (older orelse oldest) |version| version.oid else null; │ │286 + return older orelse oldest; │ │287 } │ │288 │ │312 -// the commit this push moved a ref to `tip` from, when it has a version to │ │313 -// derive from. │ │314 -fn pushedFrom( │ │289 +// the commit a move took a ref to `tip` from, when it has a version to derive │ │290 +// from. │ │291 +fn movedFrom( │ │292 comptime repo_opts: rp.RepoOpts(.xit), │ │316 - updates: ?[]const xit.net_server_receive_pack.AppliedRefUpdate, │ │293 + moves: []const Move, │ │294 tip: *const [hash.hexLen(repo_opts.hash)]u8, │ │318 - existing: std.AutoArrayHashMapUnmanaged([hash.hexLen(repo_opts.hash)]u8, void), │ │295 + versions: std.AutoArrayHashMapUnmanaged([hash.hexLen(repo_opts.hash)]u8, u64), │ │296 ) ?[hash.hexLen(repo_opts.hash)]u8 { │ │320 - for (updates orelse &.{}) |update| { │ │321 - if (!std.mem.eql(u8, update.new_oid, tip)) continue; │ │322 - if (update.old_oid.len != hash.hexLen(repo_opts.hash)) continue; │ │297 + for (moves) |move| { │ │298 + if (!std.mem.eql(u8, move.new_oid, tip)) continue; │ │299 + if (move.old_oid.len != hash.hexLen(repo_opts.hash)) continue; │ │300 var oid: [hash.hexLen(repo_opts.hash)]u8 = undefined; │ │324 - @memcpy(&oid, update.old_oid); │ │325 - if (existing.contains(oid)) return oid; │ │301 + @memcpy(&oid, move.old_oid); │ │302 + if (versions.contains(oid)) return oid; │ │303 } │ │304 return null; │ │305 } │ ╰─────────────────────────────────────────────────────────────────────────────────────────────────╯ ╭──────────────────────────────────────────────────────────────────────────────────╮ │306 │ │330 -// read `commit`'s message into `message` and return the doc key it indexes │ │331 -// under. │ │332 -fn readPosting( │ │307 +// turn a copy of `base_tip`'s version into `tip`'s by moving the postings of│ │308 +// the commits the two don't share │ │309 +fn derive( │ │310 comptime repo_opts: rp.RepoOpts(.xit), │ │311 state: rp.Repo(.xit, repo_opts).State(.read_only), │ │312 io: std.Io, │ ╰──────────────────────────────────────────────────────────────────────────────────╯ ╭───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╮ │313 allocator: std.mem.Allocator, │ │337 - message: *std.ArrayList(u8), │ │338 - commit: Commit(repo_opts.hash), │ │339 -) ![docKeyLen(repo_opts.hash)]u8 { │ │340 - message.clearRetainingCapacity(); │ │341 - var object = try obj.Object(.xit, repo_opts).init(state, io, allocator, &commit.oid); │ │342 - defer object.deinit(); │ │343 - object.readMessage(allocator, message, .limited(srch.max_indexed_bytes)) catch |err| switch (err) { │ │344 - // only the indexed prefix matters │ │345 - error.StreamTooLong => {}, │ │346 - else => |e| return e, │ │347 - }; │ │348 - return docKey(repo_opts.hash, commit.timestamp, &commit.oid); │ │314 + version: rp.Repo(.xit, repo_opts).DB.SortedMap(.read_write), │ │315 + base_tip: *const [hash.hexLen(repo_opts.hash)]u8, │ │316 + tip: *const [hash.hexLen(repo_opts.hash)]u8, │ │317 + progress_ctx_maybe: ?repo_opts.ProgressCtx, │ │318 +) !void { │ │319 + const DB = rp.Repo(.xit, repo_opts).DB; │ │320 + const Ancestry = mrg.Ancestry(.xit, repo_opts); │ │321 + var ancestry = try Ancestry.init(state, io, allocator, base_tip, tip); │ │322 + defer ancestry.deinit(); │ │323 + │ │324 + progress.report(repo_opts, io, progress_ctx_maybe, .{ .start = .{ .kind = .walking_commit, .estimated_total_items = 0 } }); │ │325 + try ancestry.finish(progress_ctx_maybe); │ │326 + progress.report(repo_opts, io, progress_ctx_maybe, .{ .end = .walking_commit }); │ │327 + │ │328 + // the walk stops at the shared history, so it trusts timestamps: a │ │329 + // commit dated later than a descendant can be passed from the base │ │330 + // side before the tip turns out to reach it too, and its postings are │ │331 + // then dropped. settling that would mean walking the whole history. │ │332 + // a wrong addition only re-puts postings, so a fast-forward removes │ │333 + // nothing, which the base tip picking up the tip's flag proves. │ │334 + const base_node = ancestry.nodes.get(ancestry.tips[0]) orelse unreachable; │ │335 + const fast_forward = base_node.flags & Ancestry.two != 0; │ │336 + │ │337 + // a commit one tip alone reaches has postings to move. tag objects are │ │338 + // peeled through, not walked. │ │339 + var total: usize = 0; │ │340 + var counted = ancestry.nodes.valueIterator(); │ │341 + while (counted.next()) |node| { │ │342 + if (node.tag_target != null) continue; │ │343 + switch (node.flags & Ancestry.both) { │ │344 + Ancestry.one => total += @intFromBool(!fast_forward), │ │345 + Ancestry.two => total += 1, │ │346 + else => {}, │ │347 + } │ │348 + } │ │349 + │ │350 + var message: std.ArrayList(u8) = .empty; │ │351 + defer message.deinit(allocator); │ │352 + │ │353 + progress.report(repo_opts, io, progress_ctx_maybe, .{ .text = "Indexing commits" }); │ │354 + progress.report(repo_opts, io, progress_ctx_maybe, .{ .start = .{ .kind = .writing_patch, .estimated_total_items = total } });│ │355 + var iter = ancestry.nodes.iterator(); │ │356 + while (iter.next()) |entry| { │ │357 + if (entry.value_ptr.tag_target != null) continue; │ │358 + const flags = entry.value_ptr.flags & Ancestry.both; │ │359 + if (flags == Ancestry.both or flags == 0 or (flags == Ancestry.one and fast_forward)) continue; │ │360 + if (progress.cancelled(repo_opts, progress_ctx_maybe)) return error.ClientGone; │ │361 + defer progress.report(repo_opts, io, progress_ctx_maybe, .{ .complete_one = .writing_patch }); │ │362 + │ │363 + var object = try obj.Object(.xit, repo_opts).init(state, io, allocator, entry.key_ptr); │ │364 + defer object.deinit(); │ │365 + const key = try readPosting(repo_opts, allocator, &message, &object); │ │366 + if (flags == Ancestry.one) { │ │367 + try srch.remove(DB, version, allocator, &key, message.items); │ │368 + } else { │ │369 + try srch.add(DB, version, allocator, &key, message.items); │ │370 + } │ │371 + } │ │372 + progress.report(repo_opts, io, progress_ctx_maybe, .{ .end = .writing_patch }); │ │373 } │ │374 │ │351 -// what `tip` reaches that `base_tip` doesn't, and the other way round, built │ │352 -// into `aa`. with no base the whole history is added. │ │353 -fn commitDiff( │ │375 +// index every commit `tip` reaches into an empty `version`, as the walk │ │376 +// reaches it │ │377 +fn indexHistory( │ │378 comptime repo_opts: rp.RepoOpts(.xit), │ │379 state: rp.Repo(.xit, repo_opts).State(.read_only), │ │380 io: std.Io, │ ╰───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯ ╭──────╮ │next →│ ╰──────╯