HAXY

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

╭ changed ────╮ │src/event.zig│ ╰─────────────╯ ╭──────────────────────────────────────────────────────────────────────────────────╮ │655 repo_dir: std.Io.Dir, │ │656 db_file: std.Io.File, │ │657 db: *DB, │ │658 + // map of each object id to its children │ │659 parent_to_children: DB.HashMap(.read_write), │ │660 // tracking pending parents is necessary because a child can only │ │661 // be returned after all of its unconsumed parents have been returned│ ╰──────────────────────────────────────────────────────────────────────────────────╯ ╭──────────────────────────────────────────────────────────────────────────────────────────────╮ │662 child_to_pending_parents: DB.HashMap(.read_write), │ │662 - oid_queue: std.AutoArrayHashMapUnmanaged([hash.byteLen(repo_opts.hash)]u8, void),│ │663 - allocator: std.mem.Allocator, │ │663 + // queue of object ids that are ready to be returned from `next` │ │664 + ready_queue: DB.ArrayList(.read_write), │ │665 + ready_queue_index: u64, │ │666 + // the object id at the tip of this branch │ │667 newest_object_id: ?[hash.byteLen(repo_opts.hash)]u8, │ │668 + // the object id furthest back in the history that hasn't been consumed │ │669 oldest_object_id: ?[hash.byteLen(repo_opts.hash)]u8, │ │670 │ │671 pub fn init( │ ╰──────────────────────────────────────────────────────────────────────────────────────────────╯ ╭───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╮ │698 │ │699 const child_to_pending_parents_cursor = try map.putCursor(hash.hashInt(repo_opts.hash, "child->pending-parents"));│ │700 const child_to_pending_parents = try DB.HashMap(.read_write).init(child_to_pending_parents_cursor); │ │701 + │ │702 + const ready_queue_cursor = try map.putCursor(hash.hashInt(repo_opts.hash, "ready-queue")); │ │703 + const ready_queue = try DB.ArrayList(.read_write).init(ready_queue_cursor); │ │704 │ │705 var self = Self{ │ │706 .repo_dir = state.core.repo_dir, │ ╰───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯ ╭──────────────────────────────────────────────────────────────────────────╮ │708 .db = db_ptr, │ │709 .parent_to_children = parent_to_children, │ │710 .child_to_pending_parents = child_to_pending_parents,│ │704 - .oid_queue = .{}, │ │705 - .allocator = allocator, │ │711 + .ready_queue = ready_queue, │ │712 + .ready_queue_index = 0, │ │713 .newest_object_id = null, │ │714 .oldest_object_id = null, │ │715 }; │ ╰──────────────────────────────────────────────────────────────────────────╯ ╭──────────────────────────────────────────────────────────────────────────╮ │725 allocator.destroy(self.db.core.memory.buffer); │ │726 self.repo_dir.deleteFile(io, db_name) catch {}; │ │727 allocator.destroy(self.db); │ │721 - self.oid_queue.deinit(allocator); │ │728 } │ │729 │ │730 pub fn next(self: *Self) !?[hash.byteLen(repo_opts.hash)]u8 {│ ╰──────────────────────────────────────────────────────────────────────────╯ ╭──────────────────────────────────────────────────────────────────────────────────────────────────────╮ │725 - if (self.oid_queue.count() == 0) return null; │ │731 + if (self.ready_queue_index >= try self.ready_queue.count()) return null; │ │732 │ │727 - // OOM risk: large merge graphs can make this queue grow unbounded │ │728 - const oid = self.oid_queue.keys()[0]; │ │729 - self.oid_queue.swapRemoveAt(0); │ │733 + const oid = try readOidFromList(self.ready_queue.readOnly(), self.ready_queue_index);│ │734 + self.ready_queue_index += 1; │ │735 │ │736 try self.enqueueChildren(&oid); │ │737 return oid; │ ╰──────────────────────────────────────────────────────────────────────────────────────────────────────╯ ╭─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╮ │745 haxy_moments: DB.HashMap(.read_only), │ │746 ref: rf.Ref, │ │747 ) !void { │ │743 - // OOM risk: ObjectIterator keeps its queue and visited/excluded set │ │744 - // in memory, so an extremely large reachable history can grow unbounded │ │745 - var commit_iter = try obj.ObjectIterator(.xit, repo_opts, .full).init(state, io, allocator, .{ .kind = .commit }); │ │746 - defer commit_iter.deinit(); │ │748 + const map = try DB.HashMap(.read_write).init(self.db.rootCursor()); │ │749 │ │748 - const head_oid = (try rf.readRecur(.xit, repo_opts, state, io, .{ .ref = ref })) orelse return error.OidNotFound; │ │749 - try commit_iter.include(&head_oid); │ │750 + const walk_queue_cursor = try map.putCursor(hash.hashInt(repo_opts.hash, "walk-queue")); │ │751 + const walk_queue = try DB.ArrayList(.read_write).init(walk_queue_cursor); │ │752 + var walk_queue_index: u64 = 0; │ │753 │ │751 - while (try commit_iter.next(allocator)) |commit_object| { │ │752 - defer commit_object.deinit(); │ │754 + const seen_commits_cursor = try map.putCursor(hash.hashInt(repo_opts.hash, "seen-commits")); │ │755 + const seen_commits = try DB.HashSet(.read_write).init(seen_commits_cursor); │ │756 + │ │757 + const head_oid_hex = (try rf.readRecur(.xit, repo_opts, state, io, .{ .ref = ref })) orelse return error.OidNotFound; │ │758 + var head_oid: [hash.byteLen(repo_opts.hash)]u8 = undefined; │ │759 + _ = try std.fmt.hexToBytes(&head_oid, &head_oid_hex); │ │760 + try walk_queue.append(.{ .bytes = &head_oid }); │ │761 │ │754 - var oid: [hash.byteLen(repo_opts.hash)]u8 = undefined; │ │755 - _ = try std.fmt.hexToBytes(&oid, &commit_object.oid); │ │762 + while (walk_queue_index < try walk_queue.count()) { │ │763 + const oid = try readOidFromList(walk_queue.readOnly(), walk_queue_index); │ │764 const oid_int = hash.bytesToInt(repo_opts.hash, &oid); │ │765 + │ │766 + walk_queue_index += 1; │ │767 │ │758 - // if this object id has already been consumed, prune its ancestry from │ │759 - // the iterator. other queued paths, such as the second parent of a │ │760 - // merge commit, can still be walked until they hit a consumed commit │ │761 - // or run out of history. │ │768 + // if we've seen this object id, skip it │ │769 + if (null != try seen_commits.getCursor(oid_int)) { │ │770 + continue; │ │771 + } │ │772 + │ │773 + try seen_commits.put(oid_int, .{ .bytes = &oid }); │ │774 + │ │775 + var commit_object = try obj.Object(.xit, repo_opts, .full).init(state, io, allocator, &std.fmt.bytesToHex(oid, .lower));│ │776 + defer commit_object.deinit(); │ │777 + │ │778 + // if this object id has already been consumed, skip it │ │779 if (null != try haxy_moments.getCursor(oid_int)) { │ │763 - try commit_iter.exclude(&commit_object.oid); │ │780 continue; │ │781 } │ │782 │ ╰─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯ ╭───────────────────────────────────────────────────────────────────────────────────────────────────────╮ │790 _ = try std.fmt.hexToBytes(&parent_oid_bytes, parent_oid); │ │791 const parent_oid_int = hash.bytesToInt(repo_opts.hash, &parent_oid_bytes); │ │792 │ │777 - if (null != try haxy_moments.getCursor(parent_oid_int)) continue; │ │793 + // if this object id has already been consumed, skip it │ │794 + if (null != try haxy_moments.getCursor(parent_oid_int)) { │ │795 + continue; │ │796 + } │ │797 │ │798 + // if this object id hasn't already been seen, add it to the walk queue │ │799 + if (null == try seen_commits.getCursor(parent_oid_int)) { │ │800 + try walk_queue.append(.{ .bytes = &parent_oid_bytes }); │ │801 + } │ │802 + │ │803 const children_cursor = try self.parent_to_children.putCursor(parent_oid_int);│ │780 - const children = try DB.CountedHashSet(.read_write).init(children_cursor); │ │804 + const children = try DB.HashSet(.read_write).init(children_cursor); │ │805 try children.put(oid_int, .{ .bytes = &oid }); │ │806 pending_parent_count += 1; │ │807 } │ ╰───────────────────────────────────────────────────────────────────────────────────────────────────────╯ ╭───────────────────────────────────────────────────────────────────────────────────────────────────────────╮ │808 │ │809 if (pending_parent_count == 0) { │ │786 - try self.oid_queue.put(allocator, oid, {}); │ │810 + try self.ready_queue.append(.{ .bytes = &oid }); │ │811 } else { │ │812 try self.child_to_pending_parents.put(oid_int, .{ .uint = pending_parent_count });│ │813 } │ ╰───────────────────────────────────────────────────────────────────────────────────────────────────────────╯ ╭──────────────────────────────────────────────────────────────────────────────────────────────────────╮ │817 fn enqueueChildren(self: *Self, oid: *const [hash.byteLen(repo_opts.hash)]u8) !void { │ │818 const oid_int = hash.bytesToInt(repo_opts.hash, oid); │ │819 const children_cursor = try self.parent_to_children.getCursor(oid_int) orelse return;│ │796 - const children = try DB.CountedHashSet(.read_only).init(children_cursor); │ │820 + const children = try DB.HashSet(.read_only).init(children_cursor); │ │821 var children_iter = try children.iterator(); │ │822 │ │823 while (try children_iter.next()) |*child_cursor| { │ ╰──────────────────────────────────────────────────────────────────────────────────────────────────────╯ ╭──────╮ │next →│ ╰──────╯