[PATCH 2/5] packfile: recover delta cycles through duplicate entries

@@ -10,6 +10,7 @@
 #include "dir.h"
 #include "packfile.h"
 #include "delta.h"
+#include "ewah/ewok.h"
 #include "hash-lookup.h"
 #include "commit.h"
 #include "object.h"

@@ -1077,6 +1078,160 @@ static int get_delta_base_oid(struct packed_git *p,
 		return -1;
 }
 
+/*
+ * Search duplicate representations for a chain ending in a full object.
+ * Representations of the same OID are interchangeable as delta bases.
+ *
+ * Each path entry is the search frame for one OID. It walks that OID's
+ * contiguous .idx entries and retains the chosen entry's .pack offset
+ * for replay.
+ */
+struct delta_path_entry {
+	off_t selected_offset; /* zero until a candidate is selected */
+	uint32_t next; /* index position of the next candidate */
+	uint32_t remaining; /* total number of candidates remaining */
+};
+
+struct delta_path {
+	struct delta_path_entry *entries;
+	size_t nr, alloc;
+};
+
+static int push_oid_group(struct packed_git *p,
+			  const struct object_id *oid,
+			  struct bitmap *visited, struct delta_path *path)
+{
+	struct object_id candidate;
+	struct delta_path_entry *entry;
+	uint32_t first_index_pos, group_index_pos, index_pos;
+
+	/*
+	 * Determine the range of index positions referring to duplicate
+	 * copies of the given object.
+	 *
+	 * Any position within that range is OK, since we will determine
+	 * the exact range below.
+	 */
+	if (!bsearch_pack(oid, p, &group_index_pos))
+		return 0;
+	if (bitmap_get(visited, group_index_pos))
+		return 0;
+
+	first_index_pos = group_index_pos;
+	while (first_index_pos > 0) {
+		if (nth_packed_object_id(&candidate, p, first_index_pos - 1) < 0)
+			return -1;
+		if (!oideq(&candidate, oid))
+			break;
+		first_index_pos--;
+	}
+
+	for (index_pos = first_index_pos; index_pos < p->num_objects; index_pos++) {
+		if (nth_packed_object_id(&candidate, p, index_pos) < 0)
+			return -1;
+		if (!oideq(&candidate, oid))
+			break;
+	}
+
+	bitmap_set(visited, group_index_pos);
+
+	ALLOC_GROW(path->entries, path->nr + 1, path->alloc);
+	entry = &path->entries[path->nr++];
+	entry->selected_offset = 0;
+	entry->next = first_index_pos;
+	entry->remaining = index_pos - first_index_pos;
+
+	return 1;
+}
+
+static enum object_type find_delta_path(struct packed_git *p,
+					struct pack_window **w_curs,
+					off_t offset,
+					struct delta_path *path)
+{
+	struct object_id oid;
+	uint32_t pack_pos;
+	struct bitmap *visited;
+	enum object_type result = OBJ_BAD;
+
+	if (offset_to_pack_pos(p, offset, &pack_pos) < 0)
+		return OBJ_BAD;
+	if (nth_packed_object_id(&oid, p, pack_pos_to_index(p, pack_pos)) < 0)
+		return OBJ_BAD;
+
+	visited = bitmap_new();
+	if (push_oid_group(p, &oid, visited, path) != 1)
+		goto done;
+
+	/*
+	 * Search depth-first for a chain ending in a full object. Each frame
+	 * tries every representation of one OID; a delta pushes its base OID,
+	 * while exhausting a frame backtracks to its parent.
+	 */
+	while (path->nr) {
+		struct delta_path_entry *entry = &path->entries[path->nr - 1];
+		enum object_type candidate_type;
+		off_t curpos;
+		size_t size;
+
+		/*
+		 * This OID has no path to a full object. Let its parent try
+		 * another representation; exhausting the root fails the search.
+		 */
+		if (!entry->remaining) {
+			path->nr--;
+			continue;
+		}
+
+		entry->selected_offset =
+			nth_packed_object_offset(p, entry->next++);
+		entry->remaining--;
+		curpos = entry->selected_offset;
+		candidate_type = unpack_object_header(p, w_curs, &curpos, &size);
+
+		/*
+		 * A full object terminates the chain, and its type is
+		 * inherited by every delta above it. A delta continues
+		 * at its base; any other type rejects only this
+		 * representation.
+		 */
+		switch (candidate_type) {
+		case OBJ_COMMIT:
+		case OBJ_TREE:
+		case OBJ_BLOB:
+		case OBJ_TAG:
+			result = candidate_type;
+			goto done;
+		case OBJ_OFS_DELTA:
+		case OBJ_REF_DELTA:
+			break;
+		default:
+			/*
+			 * A bad or unknown type rejects only this copy;
+			 * another representation of the same OID may
+			 * still work.
+			 */
+			continue;
+		}
+
+		/*
+		 * Descend to this delta's base. A malformed reference
+		 * or a missing or already-visited base rejects this
+		 * copy. A newly pushed base is examined next; an index
+		 * error aborts the search.
+		 */
+		if (get_delta_base_oid(p, w_curs, curpos, &oid, candidate_type,
+				       entry->selected_offset))
+			continue;
+		if (push_oid_group(p, &oid, visited, path) < 0)
+			goto done;
+	}
+
+done:
+	bitmap_free(visited);
+	return result;
+}
+
 static int retry_bad_packed_offset(struct repository *r,
 				   struct packed_git *p,
 				   off_t obj_offset)

@@ -1105,11 +1260,27 @@ static enum object_type packed_to_object_type(struct repository *r,
 {
 	off_t small_poi_stack[POI_STACK_PREALLOC];
 	off_t *poi_stack = small_poi_stack;
+	off_t root_offset = obj_offset;
 	int poi_stack_nr = 0, poi_stack_alloc = POI_STACK_PREALLOC;
 
 	while (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {
 		off_t base_offset;
 		size_t size;
+
+		if (poi_stack_nr > 0 && poi_stack_nr % 2 == 0 &&
+		    obj_offset == poi_stack[poi_stack_nr / 2]) {
+			struct delta_path path = { 0 };
+			/*
+			 * Normal lookup returned to the same pack
+			 * entry. Restart from the requested object
+			 * using alternate representations.
+			 */
+			type = find_delta_path(p, w_curs, root_offset, &path);
+			free(path.entries);
+			if (type == OBJ_BAD)
+				goto unwind;
+			break;
+		}
 		/* Push the object we're going to leave behind */
 		if (poi_stack_nr >= poi_stack_alloc && poi_stack == small_poi_stack) {
 			poi_stack_alloc = alloc_nr(poi_stack_nr);

@@ -1525,9 +1696,11 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,
 {
 	struct pack_window *w_curs = NULL;
 	off_t curpos = obj_offset;
+	off_t root_offset = obj_offset;
 	void *data = NULL;
 	size_t size;
 	enum object_type type;
+	struct delta_path path = { 0 };
 	struct unpack_entry_stack_ent small_delta_stack[UNPACK_ENTRY_STACK_PREALLOC];
 	struct unpack_entry_stack_ent *delta_stack = small_delta_stack;
 	int delta_stack_nr = 0, delta_stack_alloc = UNPACK_ENTRY_STACK_PREALLOC;

@@ -1553,6 +1726,22 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,
 			break;
 		}
 
+		if (!path.nr &&
+		    delta_stack_nr > 0 && delta_stack_nr % 2 == 0 &&
+		    obj_offset == delta_stack[delta_stack_nr / 2].obj_offset) {
+			/*
+			 * Normal lookup returned to the same pack
+			 * entry. Find an acyclic path if one exists,
+			 * discard this walk, and replay that path.
+			 */
+			if (find_delta_path(p, &w_curs, root_offset,
+					    &path) == OBJ_BAD)
+				break;
+			delta_stack_nr = 0;
+			curpos = obj_offset = path.entries[0].selected_offset;
+			continue;
+		}
+
 		if (do_check_packed_object_crc && p->index_version > 1) {
 			uint32_t pack_pos, index_pos;
 			off_t len;

@@ -1591,6 +1780,15 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,
 			break;
 		}
 
+		/* Use the base chosen by recovery, not the one from normal lookup. */
+		if (path.nr) {
+			size_t path_pos = (size_t)delta_stack_nr + 1;
+
+			if (path_pos >= path.nr)
+				BUG("alternate delta path ends in a delta");
+			base_offset = path.entries[path_pos].selected_offset;
+		}
+
 		/* push object, proceed to base */
 		if (delta_stack_nr >= delta_stack_alloc
 		    && delta_stack == small_delta_stack) {

@@ -1731,6 +1929,7 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,
 
 out:
 	unuse_pack(&w_curs);
+	free(path.entries);
 
 	if (delta_stack != small_delta_stack)
 		free(delta_stack);

@@ -9,6 +9,83 @@ test_description='test index-pack handling of delta cycles in packfiles'
 A=$(test_oid packlib_7_0)
 B=$(test_oid packlib_7_76)
 
+# Copy the entries from a complete pack without its header or trailer.
+pack_entries () {
+	entry_size=$(wc -c <"$1") &&
+	dd if="$1" bs=1 skip=12 \
+		count=$((entry_size - 12 - $(test_oid rawsz))) 2>/dev/null
+}
+
+# B as an OFS_DELTA against A at the given one-byte distance.
+pack_obj_b_ofs_a () {
+	pack_obj "$B" "$A" >b-ref.tmp &&
+	printf "\145" &&
+	printf "\\$(printf "%03o" "$1")" &&
+	dd if=b-ref.tmp bs=1 skip=$((1 + $(test_oid rawsz))) 2>/dev/null
+}
+
+# Return the base of the first one-byte-header REF_DELTA for the given OID.
+first_ref_base () {
+	idx=$(echo .git/objects/pack/*.idx) &&
+	offset=$(git show-index <"$idx" |
+		awk -v oid="$1" '$2 == oid { print $1; exit }') &&
+	dd if="${idx%.idx}.pack" bs=1 skip=$((offset + 1)) \
+		count=$(test_oid rawsz) 2>/dev/null |
+	test-tool hexdump |
+	tr -d " \n"
+}
+
+# The order of equal-OID entries in the .idx is unspecified. Retain a pack
+# which selects $1 as a delta against $2. Unless $3 is "-", also require the
+# first copy searched during recovery to be a REF_DELTA against $3.
+install_cycle () {
+	cycle_oid=$1 &&
+	cycle_base=$2 &&
+	first_base=$3 &&
+	shift 3 &&
+	for pack
+	do
+		clear_packs &&
+		git index-pack --fix-thin --stdin <"$pack" &&
+		selected_base=$(echo "$cycle_oid" |
+			git cat-file --batch-check="%(deltabase)") ||
+		return 1
+		if test "$selected_base" = "$cycle_base" &&
+		   { test "$first_base" = "-" ||
+		     test "$(first_ref_base "$cycle_oid")" = "$first_base"; }
+		then
+			return 0
+		fi
+	done
+	return 1
+}
+
+make_cycle_pack () {
+	cycle_pack=$1 &&
+	shift &&
+	test-tool -C alt-source pack-deltas --num-objects=6 >refs.tmp <<-EOF &&
+	REF_DELTA $T $X
+	REF_DELTA $X $1
+	REF_DELTA $Y $Z
+	REF_DELTA $Z $X
+	REF_DELTA $X $2
+	REF_DELTA $X $3
+	EOF
+	{
+		pack_header 8 &&
+		pack_entries refs.tmp &&
+		cat a-full &&
+		pack_obj_b_ofs_a "$a_full_size"
+	} >"$cycle_pack" &&
+	pack_trailer "$cycle_pack"
+}
+
+check_blob () {
+	test "$(git cat-file -t "$1")" = blob &&
+	git cat-file blob "$1" >actual &&
+	test_cmp_bin "$2" actual
+}
+
 # double-check our hand-constucted packs
 test_expect_success 'index-pack works with a single delta (A->B)' '
 	clear_packs &&

@@ -67,18 +144,77 @@ test_expect_success 'failover to an object in another pack' '
 '
 
 test_expect_success 'failover to a duplicate object in the same pack' '
-	clear_packs &&
+	{
+		pack_header 3 &&
+		pack_obj $A &&
+		pack_obj $B $A &&
+		pack_obj $A $B
+	} >recoverable-1.pack &&
+	pack_trailer recoverable-1.pack &&
 	{
 		pack_header 3 &&
 		pack_obj $A $B &&
 		pack_obj $B $A &&
 		pack_obj $A
-	} >recoverable.pack &&
-	pack_trailer recoverable.pack &&
+	} >recoverable-2.pack &&
+	pack_trailer recoverable-2.pack &&
 
-	# This cycle does not fail since the existence of a full copy
-	# of A in the pack allows us to resolve the cycle.
-	git index-pack --fix-thin --stdin <recoverable.pack
+	# The selected copy of A is part of the cycle, but the full copy
+	# lets both type and content lookups resolve it.
+	install_cycle "$A" "$B" - recoverable-1.pack recoverable-2.pack &&
+	printf "\7\0" >expect &&
+	check_blob "$A" expect
+'
+
+test_expect_success 'failover from a mixed REF/OFS cycle' '
+	pack_obj "$A" "$B" >a-ref &&
+	pack_obj "$B" >b-full &&
+	a_ref_size=$(wc -c <a-ref) &&
+	b_full_size=$(wc -c <b-full) &&
+
+	{
+		pack_header 3 &&
+		cat a-ref &&
+		cat b-full &&
+		pack_obj_b_ofs_a "$((a_ref_size + b_full_size))"
+	} >mixed-1.pack &&
+	pack_trailer mixed-1.pack &&
+	{
+		pack_header 3 &&
+		cat a-ref &&
+		pack_obj_b_ofs_a "$a_ref_size" &&
+		cat b-full
+	} >mixed-2.pack &&
+	pack_trailer mixed-2.pack &&
+
+	# The REF_DELTA for A selects the OFS_DELTA copy of B; the
+	# full B is its escape.
+	install_cycle "$B" "$A" - mixed-1.pack mixed-2.pack &&
+	printf "\7\0" >expect &&
+	check_blob "$A" expect
+'
+
+test_expect_success 'failover after a tail into a three-object delta cycle' '
+	git init alt-source &&
+	printf "\7\76" |
+		git -C alt-source hash-object -w --stdin >/dev/null &&
+	X=$(printf x | git -C alt-source hash-object -w --stdin) &&
+	Y=$(printf y | git -C alt-source hash-object -w --stdin) &&
+	Z=$(printf z | git -C alt-source hash-object -w --stdin) &&
+	printf "tail T\n" >tail &&
+	T=$(git -C alt-source hash-object -w --stdin <tail) &&
+
+	pack_obj "$A" >a-full &&
+	a_full_size=$(wc -c <a-full) &&
+	make_cycle_pack alternate-1.pack "$B" "$Y" "$Y" &&
+	make_cycle_pack alternate-2.pack "$Y" "$B" "$Y" &&
+	make_cycle_pack alternate-3.pack "$Y" "$Y" "$B" &&
+
+	# Lookup of T follows T->X->Y->Z->X. Recovery must exhaust that
+	# branch, then use X->B->A, whose final edge is an OFS_DELTA.
+	install_cycle "$X" "$Y" "$Y" \
+		alternate-1.pack alternate-2.pack alternate-3.pack &&
+	check_blob "$T" tail
 '
 
 test_expect_success 'index-pack works with thin pack A->B->C with B on disk' '