╭─────────────╮ │scroll to top│ ╰─────────────╯ ╭───────────────────────────────────────────────────────────────╮ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ╰───────────────────────────────────────────────────────────────╯
🬐 🬠 🬞🬂🬏 🬟 🬑 🬟 🬑 ╭master╮ master haxy: 🬋🬋🬋 🬋🬋🬋 🬋 🬋 │files │ commits refs discuss issues patches new login 🬐 🬠 🬐 🬠 🬑 🬟 🬰 ╰──────╯ (712) user
╭ find file ─ ─ ─ ─ ─ ─ ─ ─ ─ ─╮ ╭────╮ ╭ clone ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─╮ │ │ │http│ ssh │ │ ╰ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─╯ ╰────╯ ╰ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─╯
.. embed/ event/ test/ ui/ command.zig diff3.zig event.zig find.zig fork.zig lib.zig main.zig main_wasm.zig markdown.zig notify.zig patch.zig progress.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
92 }; 93 94 var arena = std.heap.ArenaAllocator.init(allocator); 95 defer arena.deinit(); 96 const aa = arena.allocator(); 97 98 var work: std.ArrayList(Work) = .empty; 99 var gone: std.ArrayList(Oid) = .empty; 100 var default_tip: ?Oid = null; 101 // the versions in the index, each with its commit's timestamp. the ones 102 // built here join them, so a later tip can derive from an earlier one. 103 var versions: std.AutoArrayHashMapUnmanaged(Oid, u64) = .empty; 104 105 { 106 const read_state = state.readOnly(); 107 108 if (try moment.getCursor(hash.hashInt(repo_opts.hash, index_key))) |index_cursor| { 109 const index = try DB.HashMap(.read_only).init(index_cursor); 110 var iter = try index.iterator(); 111 while (try iter.next()) |cursor| { 112 const pair = try cursor.readKeyValuePair(); 113 var entry: Entry = undefined; 114 if ((try pair.key_cursor.readBytes(&entry)).len != entry.len) return error.InvalidCommitIndex; 115 const oid = std.fmt.bytesToHex(entry[0..oid_len].*, .lower); 116 try versions.put(aa, oid, std.mem.readInt(u64, entry[oid_len..], .big)); 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 rf.RefIterator(.xit, repo_opts).init(read_state, io, allocator, .head, .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 rf.readRecur(.xit, repo_opts, read_state, io, .{ .ref = .{ .kind = .head, .name = ref.name } })) orelse continue); 128 } 129 } 130 { 131 var tags = try rf.RefIterator(.xit, repo_opts).init(read_state, io, allocator, .tag, .beginning); 132 defer tags.deinit(); 133 while (try tags.next()) |ref| { 134 try tips.append(aa, (try rf.readRecur(.xit, repo_opts, read_state, io, .{ .ref = .{ .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 (versions.contains(tip)) { 145 try wanted.put(aa, tip, {}); 146 continue; 147 } 148 var commit = obj.Object(.xit, repo_opts).initCommit(read_state, io, allocator, &tip) catch continue; 149 defer commit.deinit(); 150 try wanted.put(aa, commit.oid, {}); 151 if (versions.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 = movedFrom(repo_opts, moves, &tip, versions); 159 } 160 161 var head_buffer: [rf.MAX_REF_CONTENT_SIZE]u8 = undefined; 162 if (rf.readHead(.xit, repo_opts, read_state, io, &head_buffer) catch null) |head| switch (head) { 163 .ref => |ref| default_tip = try rf.readRecur(.xit, repo_opts, read_state, io, .{ .ref = .{ .kind = .head, .name = ref.name } }), 164 .oid => {}, 165 }; 166 167 try work.appendSlice(aa, missing.values()); 168 // oldest first, so a later tip derives from an earlier one 169 std.mem.sort(Work, work.items, {}, struct { 170 fn lessThan(_: void, a: Work, b: Work) bool { 171 return a.timestamp < b.timestamp; 172 } 173 }.lessThan); 174 175 for (versions.keys()) |oid| { 176 if (!wanted.contains(oid)) try gone.append(aa, oid); 177 } 178 } 179 180 if (work.items.len == 0 and gone.items.len == 0) return false; 181 182 { 183 const index_hash = hash.hashInt(repo_opts.hash, index_key); 184 185 for (work.items) |item| { 186 const index = try DB.HashMap(.read_write).init(try moment.putCursor(index_hash)); 187 const base = item.base orelse nearestVersion(repo_opts.hash, versions, default_tip, item.timestamp); 188 189 var entry: Entry = undefined; 190 _ = try std.fmt.hexToBytes(entry[0..oid_len], &item.oid); 191 std.mem.writeInt(u64, entry[oid_len..], item.timestamp, .big); 192 const oid_int = hash.bytesToInt(repo_opts.hash, entry[0..oid_len]); 193 try index.putKey(oid_int, .{ .bytes = &entry }); 194 var version_cursor = try index.putCursor(oid_int); 195 if (base) |base_oid| { 196 const base_cursor = (try index.getCursor(try hash.hexToInt(repo_opts.hash, &base_oid))) orelse return error.InvalidCommitIndex; 197 try version_cursor.write(.{ .slot = base_cursor.slot() }); 198 } 199 const version = try DB.SortedMap(.read_write).init(version_cursor); 200 201 if (base) |*base_oid| { 202 try derive(repo_opts, state.readOnly(), io, allocator, version, base_oid, &item.oid, progress_ctx_maybe); 203 } else { 204 try indexHistory(repo_opts, state.readOnly(), io, allocator, version, &item.oid, progress_ctx_maybe); 205 } 206 207 try versions.put(aa, item.oid, item.timestamp); 208 // the next version copies this one's slot, so everything 209 // written so far has to be shared rather than mutated 210 try state.core.db.freeze(); 211 } 212 213 // removing last keeps a tip that is going away available as a base 214 const index = try DB.HashMap(.read_write).init(try moment.putCursor(index_hash)); 215 for (gone.items) |oid| _ = try index.remove(try hash.hexToInt(repo_opts.hash, &oid)); 216 } 217 return true; 218 } 219 220 // the version a tip committed at `timestamp` derives from when no move names 221 // one: the default branch's unless it is newer than the tip, else the nearest 222 // older one, else the oldest. a guess by dates that only the cost rides on. 223 fn nearestVersion( 224 comptime hash_kind: hash.HashKind, 225 versions: std.AutoArrayHashMapUnmanaged([hash.hexLen(hash_kind)]u8, u64), 226 default_tip: ?[hash.hexLen(hash_kind)]u8, 227 timestamp: u64, 228 ) ?[hash.hexLen(hash_kind)]u8 { 229 var older: ?[hash.hexLen(hash_kind)]u8 = null; 230 var older_timestamp: u64 = 0; 231 var oldest: ?[hash.hexLen(hash_kind)]u8 = null; 232 var oldest_timestamp: u64 = std.math.maxInt(u64); 233 for (versions.keys(), versions.values()) |oid, version_timestamp| { 234 if (version_timestamp <= timestamp) { 235 if (default_tip) |tip| if (std.mem.eql(u8, &tip, &oid)) return tip; 236 if (older == null or version_timestamp > older_timestamp) { 237 older = oid; 238 older_timestamp = version_timestamp; 239 } 240 } 241 if (version_timestamp < oldest_timestamp) { 242 oldest = oid; 243 oldest_timestamp = version_timestamp; 244 } 245 } 246 return older orelse oldest; 247 } 248 249 // the commit a move took a ref to `tip` from, when it has a version to derive 250 // from. 251 fn movedFrom( 252 comptime repo_opts: rp.RepoOpts(.xit), 253 moves: []const Move, 254 tip: *const [hash.hexLen(repo_opts.hash)]u8, 255 versions: std.AutoArrayHashMapUnmanaged([hash.hexLen(repo_opts.hash)]u8, u64), 256 ) ?[hash.hexLen(repo_opts.hash)]u8 { 257 for (moves) |move| { 258 if (!std.mem.eql(u8, move.new_oid, tip)) continue; 259 if (move.old_oid.len != hash.hexLen(repo_opts.hash)) continue; 260 var oid: [hash.hexLen(repo_opts.hash)]u8 = undefined; 261 @memcpy(&oid, move.old_oid); 262 if (versions.contains(oid)) return oid; 263 } 264 return null; 265 } 266 267 // turn a copy of `base_tip`'s version into `tip`'s by moving the postings of 268 // the commits the two don't share 269 fn derive( 270 comptime repo_opts: rp.RepoOpts(.xit), 271 state: rp.Repo(.xit, repo_opts).State(.read_only), 272 io: std.Io, 273 allocator: std.mem.Allocator, 274 version: rp.Repo(.xit, repo_opts).DB.SortedMap(.read_write), 275 base_tip: *const [hash.hexLen(repo_opts.hash)]u8, 276 tip: *const [hash.hexLen(repo_opts.hash)]u8, 277 progress_ctx_maybe: ?repo_opts.ProgressCtx, 278 ) !void { 279 const DB = rp.Repo(.xit, repo_opts).DB; 280 const Ancestry = mrg.Ancestry(.xit, repo_opts); 281 var ancestry = try Ancestry.init(state, io, allocator, base_tip, tip); 282 defer ancestry.deinit(); 283 284 progress.report(repo_opts, io, progress_ctx_maybe, .{ .start = .{ .kind = .walking_commit, .estimated_total_items = 0 } }); 285 try ancestry.finish(progress_ctx_maybe); 286 progress.report(repo_opts, io, progress_ctx_maybe, .{ .end = .walking_commit }); 287 288 // the walk stops at the shared history, so it trusts timestamps: a 289 // commit dated later than a descendant can be passed from the base 290 // side before the tip turns out to reach it too, and its postings are 291 // then dropped. settling that would mean walking the whole history. 292 // a wrong addition only re-puts postings, so a fast-forward removes 293 // nothing, which the base tip picking up the tip's flag proves. 294 const base_node = ancestry.nodes.get(ancestry.tips[0]) orelse unreachable; 295 const fast_forward = base_node.flags & Ancestry.two != 0; 296 297 // a commit one tip alone reaches has postings to move. tag objects are 298 // peeled through, not walked. 299 var total: usize = 0; 300 var counted = ancestry.nodes.valueIterator(); 301 while (counted.next()) |node| { 302 if (node.tag_target != null) continue; 303 switch (node.flags & Ancestry.both) { 304 Ancestry.one => total += @intFromBool(!fast_forward), 305 Ancestry.two => total += 1, 306 else => {}, 307 } 308 } 309 310 var message: std.ArrayList(u8) = .empty; 311 defer message.deinit(allocator); 312 313 progress.report(repo_opts, io, progress_ctx_maybe, .{ .text = "Indexing commits" }); 314 progress.report(repo_opts, io, progress_ctx_maybe, .{ .start = .{ .kind = .writing_patch, .estimated_total_items = total } }); 315 var iter = ancestry.nodes.iterator(); 316 while (iter.next()) |entry| { 317 if (entry.value_ptr.tag_target != null) continue; 318 const flags = entry.value_ptr.flags & Ancestry.both; 319 if (flags == Ancestry.both or flags == 0 or (flags == Ancestry.one and fast_forward)) continue; 320 if (progress.cancelled(repo_opts, progress_ctx_maybe)) return error.ClientGone; 321 defer progress.report(repo_opts, io, progress_ctx_maybe, .{ .complete_one = .writing_patch }); 322 323 var object = try obj.Object(.xit, repo_opts).init(state, io, allocator, entry.key_ptr); 324 defer object.deinit(); 325 const key = try readPosting(repo_opts, allocator, &message, &object); 326 const removed = flags == Ancestry.one; 327 try srch.replace(DB, version, allocator, &key, if (removed) message.items else "", if (removed) "" else message.items); 328 } 329 progress.report(repo_opts, io, progress_ctx_maybe, .{ .end = .writing_patch }); 330 } 331 332 // index every commit `tip` reaches into an empty `version`, as the walk 333 // reaches it. 334 // TODO: the walk holds every visited oid in memory. if that proves too costly 335 // for large repositories, consider indexing first-parent history only, which 336 // needs no visited set and matches the commits list. 337 fn indexHistory( 338 comptime repo_opts: rp.RepoOpts(.xit), 339 state: rp.Repo(.xit, repo_opts).State(.read_only), 340 io: std.Io, 341 allocator: std.mem.Allocator, 342 version: rp.Repo(.xit, repo_opts).DB.SortedMap(.read_write), 343 tip: *const [hash.hexLen(repo_opts.hash)]u8, 344 progress_ctx_maybe: ?repo_opts.ProgressCtx, 345 ) !void { 346 const DB = rp.Repo(.xit, repo_opts).DB; 347 348 var message: std.ArrayList(u8) = .empty; 349 defer message.deinit(allocator); 350 351 // a whole history has no count until it is walked, so it reports the 352 // commits indexed so far 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 = 0 } }); 355 var iter = try obj.ObjectIterator(.xit, repo_opts).init(state, io, allocator, .{ .kind = .commit }); 356 defer iter.deinit(); 357 try iter.include(tip); 358 while (try iter.next(allocator)) |object| { 359 defer object.deinit(); 360 if (progress.cancelled(repo_opts, progress_ctx_maybe)) return error.ClientGone; 361 const key = try readPosting(repo_opts, allocator, &message, object); 362 try srch.replace(DB, version, allocator, &key, "", message.items); 363 progress.report(repo_opts, io, progress_ctx_maybe, .{ .complete_one = .writing_patch }); 364 } 365 progress.report(repo_opts, io, progress_ctx_maybe, .{ .end = .writing_patch }); 366 } 367 368 // replace `message` with the indexed prefix of `object`'s message and return 369 // the doc key it indexes under 370 fn readPosting( 371 comptime repo_opts: rp.RepoOpts(.xit), 372 allocator: std.mem.Allocator, 373 message: *std.ArrayList(u8), 374 object: *obj.Object(.xit, repo_opts), 375 ) ![docKeyLen(repo_opts.hash)]u8 { 376 message.clearRetainingCapacity(); 377 object.readMessage(allocator, message, .limited(srch.max_indexed_bytes)) catch |err| switch (err) { 378 // only the indexed prefix matters 379 error.StreamTooLong => {}, 380 else => |e| return e, 381 }; 382 return docKey(repo_opts.hash, object.content.commit.metadata.timestamp, &object.oid); 383 } 384