╭─────────────╮ │scroll to top│ ╰─────────────╯ ╭ search_commit.zig ────────────────────────────────────────────╮ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ╰───────────────────────────────────────────────────────────────╯
🬐 🬠 🬞🬂🬏 🬟 🬑 🬟 🬑 ╭26a37d20..╮ 26a37d20.. see-em: 🬋🬋🬋 🬋🬋🬋 🬋 🬋 │files │ commits refs discuss issues new login 🬐 🬠 🬐 🬠 🬑 🬟 🬰 ╰──────────╯ (555) user
╭────╮ ╭ clone ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ╮ │http│ ssh │ │ ╰────╯ ╰ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ╯
.. embed/ event/ test/ ui/ command.zig diff3.zig event.zig find.zig fork.zig lib.zig main.zig main_wasm.zig patch.zig push.zig search.zig ╭─────────────────────────────────╮ │search_commit.zig │ ╰─────────────────────────────────╯ search_thread.zig serve.zig serve_common.zig serve_http.zig serve_ssh.zig serve_ssh_protocol.zig test.zig testnet.zig try.zig ui.zig web.zig
127 // it derives from (null = walk the whole history). 128 const Work = struct { 129 oid: Oid, 130 timestamp: u64, 131 base: ?Oid, 132 }; 133 134 var arena = std.heap.ArenaAllocator.init(allocator); 135 defer arena.deinit(); 136 const aa = arena.allocator(); 137 138 var work: std.ArrayList(Work) = .empty; 139 var gone: std.ArrayList(Oid) = .empty; 140 var default_tip: ?Oid = null; 141 // the versions a new tip can derive from 142 var versions: std.ArrayList(Tip) = .empty; 143 144 { 145 const read_state = state.readOnly(); 146 147 // the commits that already have a version 148 var existing: std.AutoArrayHashMapUnmanaged(Oid, void) = .empty; 149 if (try moment.getCursor(hash.hashInt(repo_opts.hash, index_key))) |index_cursor| { 150 const index = try DB.HashMap(.read_only).init(index_cursor); 151 var iter = try index.iterator(); 152 while (try iter.next()) |cursor| { 153 const pair = try cursor.readKeyValuePair(); 154 var oid_bytes: [hash.byteLen(repo_opts.hash)]u8 = undefined; 155 if ((try pair.key_cursor.readBytes(&oid_bytes)).len != oid_bytes.len) return error.InvalidCommitIndex; 156 try existing.put(aa, std.fmt.bytesToHex(oid_bytes, .lower), {}); 157 } 158 } 159 160 // what every head except the events branch and every tag points at 161 var tips: std.ArrayList(Oid) = .empty; 162 { 163 var branches = try rf.RefIterator(.xit, repo_opts).init(read_state, io, allocator, .head, .beginning); 164 defer branches.deinit(); 165 while (try branches.next()) |ref| { 166 if (std.mem.eql(u8, ref.name, evt.events_ref.name)) continue; 167 try tips.append(aa, (try rf.readRecur(.xit, repo_opts, read_state, io, .{ .ref = .{ .kind = .head, .name = ref.name } })) orelse continue); 168 } 169 } 170 { 171 var tags = try rf.RefIterator(.xit, repo_opts).init(read_state, io, allocator, .tag, .beginning); 172 defer tags.deinit(); 173 while (try tags.next()) |ref| { 174 try tips.append(aa, (try rf.readRecur(.xit, repo_opts, read_state, io, .{ .ref = .{ .kind = .tag, .name = ref.name } })) orelse continue); 175 } 176 } 177 178 // the commits a version is wanted for, annotated tags peeled. refs 179 // sharing a commit share its version. 180 var wanted: std.AutoArrayHashMapUnmanaged(Oid, void) = .empty; 181 var missing: std.AutoArrayHashMapUnmanaged(Oid, Work) = .empty; 182 for (tips.items) |tip| { 183 // a tip that already has a version needs no reading 184 if (existing.contains(tip)) { 185 try wanted.put(aa, tip, {}); 186 continue; 187 } 188 var commit = obj.Object(.xit, repo_opts).initCommit(read_state, io, allocator, &tip) catch continue; 189 defer commit.deinit(); 190 try wanted.put(aa, commit.oid, {}); 191 if (existing.contains(commit.oid)) continue; 192 const entry = try missing.getOrPut(aa, commit.oid); 193 if (!entry.found_existing) entry.value_ptr.* = .{ 194 .oid = commit.oid, 195 .timestamp = commit.content.commit.metadata.timestamp, 196 .base = null, 197 }; 198 if (entry.value_ptr.base == null) entry.value_ptr.base = pushedFrom(repo_opts, updates, &tip, existing); 199 } 200 201 var head_buffer: [rf.MAX_REF_CONTENT_SIZE]u8 = undefined; 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 => {}, 205 }; 206 207 // an entry whose commit is gone can't be walked from, so it isn't a 208 // candidate. 209 const unbased = for (missing.values()) |item| { 210 if (item.base == null) break true; 211 } else false; 212 if (unbased) for (existing.keys()) |oid| { 213 var commit = obj.Object(.xit, repo_opts).initCommit(read_state, io, allocator, &oid) catch continue; 214 defer commit.deinit(); 215 try versions.append(aa, .{ .oid = oid, .timestamp = commit.content.commit.metadata.timestamp }); 216 }; 217 218 try work.appendSlice(aa, missing.values()); 219 // oldest first, so a later tip derives from an earlier one 220 std.mem.sort(Work, work.items, {}, struct { 221 fn lessThan(_: void, a: Work, b: Work) bool { 222 return a.timestamp < b.timestamp; 223 } 224 }.lessThan); 225 226 for (existing.keys()) |oid| { 227 if (!wanted.contains(oid)) try gone.append(aa, oid); 228 } 229 } 230 231 if (work.items.len == 0 and gone.items.len == 0) return false; 232 233 { 234 const index_hash = hash.hashInt(repo_opts.hash, index_key); 235 236 var message: std.ArrayList(u8) = .empty; 237 defer message.deinit(allocator); 238 239 for (work.items) |item| { 240 const index = try DB.HashMap(.read_write).init(try moment.putCursor(index_hash)); 241 const base = item.base orelse nearestVersion(repo_opts.hash, versions.items, default_tip, item.timestamp); 242 243 var oid_bytes: [hash.byteLen(repo_opts.hash)]u8 = undefined; 244 _ = try std.fmt.hexToBytes(&oid_bytes, &item.oid); 245 const oid_int = hash.bytesToInt(repo_opts.hash, &oid_bytes); 246 try index.putKey(oid_int, .{ .bytes = &oid_bytes }); 247 var version_cursor = try index.putCursor(oid_int); 248 if (base) |base_oid| { 249 const base_cursor = (try index.getCursor(try hash.hexToInt(repo_opts.hash, &base_oid))) orelse return error.InvalidCommitIndex; 250 try version_cursor.write(.{ .slot = base_cursor.slot() }); 251 } 252 const version = try DB.SortedMap(.read_write).init(version_cursor); 253 254 var diff_arena = std.heap.ArenaAllocator.init(allocator); 255 defer diff_arena.deinit(); 256 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); 257 258 // the walk is done, so the messages left to read are the total 259 serve_common.reportProgress(repo_opts, io, progress_ctx_maybe, .{ .text = "Indexing commits" }); 260 serve_common.reportProgress(repo_opts, io, progress_ctx_maybe, .{ .start = .{ .kind = .writing_patch, .estimated_total_items = diff.removed.len + diff.added.len } }); 261 for (diff.removed) |commit| { 262 if (serve_common.progressCancelled(repo_opts, progress_ctx_maybe)) return error.ClientGone; 263 defer serve_common.reportProgress(repo_opts, io, progress_ctx_maybe, .{ .complete_one = .writing_patch }); 264 const key = try readPosting(repo_opts, state.readOnly(), io, allocator, &message, commit); 265 try srch.remove(DB, version, allocator, &key, message.items); 266 } 267 for (diff.added) |commit| { 268 if (serve_common.progressCancelled(repo_opts, progress_ctx_maybe)) return error.ClientGone; 269 defer serve_common.reportProgress(repo_opts, io, progress_ctx_maybe, .{ .complete_one = .writing_patch }); 270 const key = try readPosting(repo_opts, state.readOnly(), io, allocator, &message, commit); 271 try srch.add(DB, version, allocator, &key, message.items); 272 } 273 serve_common.reportProgress(repo_opts, io, progress_ctx_maybe, .{ .end = .writing_patch }); 274 275 try versions.append(aa, .{ .oid = item.oid, .timestamp = item.timestamp }); 276 // the next version copies this one's slot, so everything 277 // written so far has to be shared rather than mutated 278 try state.core.db.freeze(); 279 } 280 281 // removing last keeps a tip that is going away available as a base 282 const index = try DB.HashMap(.read_write).init(try moment.putCursor(index_hash)); 283 for (gone.items) |oid| _ = try index.remove(try hash.hexToInt(repo_opts.hash, &oid)); 284 } 285 return true; 286 } 287 288 // the version a tip committed at `timestamp` derives from when no push names 289 // one: the default branch's unless it is newer than the tip, else the nearest 290 // older one, else the oldest. a guess by dates that only the cost rides on. 291 fn nearestVersion( 292 comptime hash_kind: hash.HashKind, 293 versions: []const Commit(hash_kind), 294 default_tip: ?[hash.hexLen(hash_kind)]u8, 295 timestamp: u64, 296 ) ?[hash.hexLen(hash_kind)]u8 { 297 var older: ?Commit(hash_kind) = null; 298 var oldest: ?Commit(hash_kind) = null; 299 for (versions) |version| { 300 if (version.timestamp <= timestamp) { 301 if (default_tip) |oid| if (std.mem.eql(u8, &oid, &version.oid)) return oid; 302 const nearer = if (older) |found| version.timestamp > found.timestamp else true; 303 if (nearer) older = version; 304 } 305 const earlier = if (oldest) |found| version.timestamp < found.timestamp else true; 306 if (earlier) oldest = version; 307 } 308 return if (older orelse oldest) |version| version.oid else null; 309 } 310 311 // the commit this push moved a ref to `tip` from, when it has a version to 312 // derive from. 313 fn pushedFrom( 314 comptime repo_opts: rp.RepoOpts(.xit), 315 updates: ?[]const xit.net_server_receive_pack.AppliedRefUpdate, 316 tip: *const [hash.hexLen(repo_opts.hash)]u8, 317 existing: std.AutoArrayHashMapUnmanaged([hash.hexLen(repo_opts.hash)]u8, void), 318 ) ?[hash.hexLen(repo_opts.hash)]u8 { 319 for (updates orelse &.{}) |update| { 320 if (!std.mem.eql(u8, update.new_oid, tip)) continue; 321 if (update.old_oid.len != hash.hexLen(repo_opts.hash)) continue; 322 var oid: [hash.hexLen(repo_opts.hash)]u8 = undefined; 323 @memcpy(&oid, update.old_oid); 324 if (existing.contains(oid)) return oid; 325 } 326 return null; 327 } 328 329 // read `commit`'s message into `message` and return the doc key it indexes 330 // under. 331 fn readPosting( 332 comptime repo_opts: rp.RepoOpts(.xit), 333 state: rp.Repo(.xit, repo_opts).State(.read_only), 334 io: std.Io, 335 allocator: std.mem.Allocator, 336 message: *std.ArrayList(u8), 337 commit: Commit(repo_opts.hash), 338 ) ![docKeyLen(repo_opts.hash)]u8 { 339 message.clearRetainingCapacity(); 340 var object = try obj.Object(.xit, repo_opts).init(state, io, allocator, &commit.oid); 341 defer object.deinit(); 342 object.readMessage(allocator, message, .limited(srch.max_indexed_bytes)) catch |err| switch (err) { 343 // only the indexed prefix matters 344 error.StreamTooLong => {}, 345 else => |e| return e, 346 }; 347 return docKey(repo_opts.hash, commit.timestamp, &commit.oid); 348 } 349 350 // what `tip` reaches that `base_tip` doesn't, and the other way round, built 351 // into `aa`. with no base the whole history is added. 352 fn commitDiff( 353 comptime repo_opts: rp.RepoOpts(.xit), 354 state: rp.Repo(.xit, repo_opts).State(.read_only), 355 io: std.Io, 356 allocator: std.mem.Allocator, 357 aa: std.mem.Allocator, 358 base_tip: ?*const [hash.hexLen(repo_opts.hash)]u8, 359 tip: *const [hash.hexLen(repo_opts.hash)]u8, 360 progress_ctx_maybe: ?repo_opts.ProgressCtx, 361 ) !struct { removed: []const Commit(repo_opts.hash), added: []const Commit(repo_opts.hash) } { 362 var removed: std.ArrayList(Commit(repo_opts.hash)) = .empty; 363 var added: std.ArrayList(Commit(repo_opts.hash)) = .empty; 364 365 if (base_tip) |base| { 366 const Ancestry = mrg.Ancestry(.xit, repo_opts); 367 var ancestry = try Ancestry.init(state, io, allocator, base, tip); 368 defer ancestry.deinit(); 369 try ancestry.finish(); 370 371 // timestamps only choose the walk's order, so a commit the base reached 372 // can be passed before the tip turns out to reach it too. that can only 373 // make a removal wrong, never an addition. a fast-forward removes 374 // nothing, which the base tip picking up the tip's flag proves. anything 375 // else is settled by walking until nothing is left to carry down. 376 const base_node = ancestry.nodes.get(ancestry.tips[0]) orelse unreachable; 377 const fast_forward = base_node.flags & Ancestry.two != 0; 378 if (!fast_forward) { 379 var candidates = false; 380 var flagged = ancestry.nodes.valueIterator(); 381 while (flagged.next()) |node| { 382 if (node.flags & Ancestry.both == Ancestry.one) candidates = true; 383 } 384 if (candidates) while (try ancestry.step()) {}; 385 } 386 387 var iter = ancestry.nodes.iterator(); 388 while (iter.next()) |entry| { 389 // tag objects are peeled through, not walked 390 if (entry.value_ptr.tag_target != null) continue; 391 const commit = Commit(repo_opts.hash){ .oid = entry.key_ptr.*, .timestamp = entry.value_ptr.timestamp }; 392 switch (entry.value_ptr.flags & Ancestry.both) { 393 Ancestry.one => if (!fast_forward) try removed.append(aa, commit), 394 Ancestry.two => try added.append(aa, commit), 395 else => {}, 396 } 397 } 398 } else { 399 // a whole history has no count until it is walked, so the walk reports 400 // the commits it has reached so far 401 serve_common.reportProgress(repo_opts, io, progress_ctx_maybe, .{ .text = "Walking commits" }); 402 serve_common.reportProgress(repo_opts, io, progress_ctx_maybe, .{ .start = .{ .kind = .writing_patch, .estimated_total_items = 0 } }); 403 var iter = try obj.ObjectIterator(.xit, repo_opts).init(state, io, allocator, .{ .kind = .commit }); 404 defer iter.deinit(); 405 try iter.include(tip); 406 while (try iter.next(allocator)) |object| { 407 defer object.deinit(); 408 try added.append(aa, .{ .oid = object.oid, .timestamp = object.content.commit.metadata.timestamp }); 409 serve_common.reportProgress(repo_opts, io, progress_ctx_maybe, .{ .complete_one = .writing_patch }); 410 } 411 serve_common.reportProgress(repo_opts, io, progress_ctx_maybe, .{ .end = .writing_patch }); 412 } 413 414 return .{ .removed = removed.items, .added = added.items }; 415 } 416