Merge branch 'ps/odb-generic-object-name-handling'

Object name handling (disambiguation and abbreviation) has been
refactored to be backend-generic, moving logic into the respective
object database backends.

* ps/odb-generic-object-name-handling:
  odb: introduce generic `odb_find_abbrev_len()`
  object-file: move logic to compute packed abbreviation length
  object-name: move logic to compute loose abbreviation length
  object-name: simplify computing common prefixes
  object-name: abbreviate loose object names without `disambiguate_state`
  object-name: merge `update_candidates()` and `match_prefix()`
  object-name: backend-generic `get_short_oid()`
  object-name: backend-generic `repo_collect_ambiguous()`
  object-name: extract function to parse object ID prefixes
  object-name: move logic to iterate through packed prefixed objects
  object-name: move logic to iterate through loose prefixed objects
  odb: introduce `struct odb_for_each_object_options`
  oidtree: extend iteration to allow for arbitrary return codes
  oidtree: modernize the code a bit
  object-file: fix sparse 'plain integer as NULL pointer' error

1 files changed, 92 insertions, 7 deletions

diff --git a/odb.c b/odb.c
index 350e23f3c0..3f94a53df1 100644
--- a/odb.c
+++ b/odb.c
@@ -12,6 +12,7 @@
 #include "midx.h"
 #include "object-file-convert.h"
 #include "object-file.h"
+#include "object-name.h"
 #include "odb.h"
 #include "packfile.h"
 #include "path.h"
@@ -896,20 +897,20 @@ int odb_freshen_object(struct object_database *odb,
 	return 0;
 }
 
-int odb_for_each_object(struct object_database *odb,
-			const struct object_info *request,
-			odb_for_each_object_cb cb,
-			void *cb_data,
-			unsigned flags)
+int odb_for_each_object_ext(struct object_database *odb,
+			    const struct object_info *request,
+			    odb_for_each_object_cb cb,
+			    void *cb_data,
+			    const struct odb_for_each_object_options *opts)
 {
 	int ret;
 
 	odb_prepare_alternates(odb);
 	for (struct odb_source *source = odb->sources; source; source = source->next) {
-		if (flags & ODB_FOR_EACH_OBJECT_LOCAL_ONLY && !source->local)
+		if (opts->flags & ODB_FOR_EACH_OBJECT_LOCAL_ONLY && !source->local)
 			continue;
 
-		ret = odb_source_for_each_object(source, request, cb, cb_data, flags);
+		ret = odb_source_for_each_object(source, request, cb, cb_data, opts);
 		if (ret)
 			return ret;
 	}
@@ -917,6 +918,18 @@ int odb_for_each_object(struct object_database *odb,
 	return 0;
 }
 
+int odb_for_each_object(struct object_database *odb,
+			const struct object_info *request,
+			odb_for_each_object_cb cb,
+			void *cb_data,
+			unsigned flags)
+{
+	struct odb_for_each_object_options opts = {
+		.flags = flags,
+	};
+	return odb_for_each_object_ext(odb, request, cb, cb_data, &opts);
+}
+
 int odb_count_objects(struct object_database *odb,
 		      enum odb_count_objects_flags flags,
 		      unsigned long *out)
@@ -952,6 +965,78 @@ out:
 	return ret;
 }
 
+/*
+ * Return the slot of the most-significant bit set in "val". There are various
+ * ways to do this quickly with fls() or __builtin_clzl(), but speed is
+ * probably not a big deal here.
+ */
+static unsigned msb(unsigned long val)
+{
+	unsigned r = 0;
+	while (val >>= 1)
+		r++;
+	return r;
+}
+
+int odb_find_abbrev_len(struct object_database *odb,
+			const struct object_id *oid,
+			int min_length,
+			unsigned *out)
+{
+	const struct git_hash_algo *algo =
+		oid->algo ? &hash_algos[oid->algo] : odb->repo->hash_algo;
+	const unsigned hexsz = algo->hexsz;
+	unsigned len;
+	int ret;
+
+	if (min_length < 0) {
+		unsigned long count;
+
+		if (odb_count_objects(odb, ODB_COUNT_OBJECTS_APPROXIMATE, &count) < 0)
+			count = 0;
+
+		/*
+		 * Add one because the MSB only tells us the highest bit set,
+		 * not including the value of all the _other_ bits (so "15"
+		 * is only one off of 2^4, but the MSB is the 3rd bit.
+		 */
+		len = msb(count) + 1;
+		/*
+		 * We now know we have on the order of 2^len objects, which
+		 * expects a collision at 2^(len/2). But we also care about hex
+		 * chars, not bits, and there are 4 bits per hex. So all
+		 * together we need to divide by 2 and round up.
+		 */
+		len = DIV_ROUND_UP(len, 2);
+		/*
+		 * For very small repos, we stick with our regular fallback.
+		 */
+		if (len < FALLBACK_DEFAULT_ABBREV)
+			len = FALLBACK_DEFAULT_ABBREV;
+	} else {
+		len = min_length;
+	}
+
+	if (len >= hexsz || !len) {
+		*out = hexsz;
+		ret = 0;
+		goto out;
+	}
+
+	odb_prepare_alternates(odb);
+	for (struct odb_source *source = odb->sources; source; source = source->next) {
+		ret = odb_source_find_abbrev_len(source, oid, len, &len);
+		if (ret)
+			goto out;
+	}
+
+	ret = 0;
+	*out = len;
+
+out:
+	return ret;
+}
+
 void odb_assert_oid_type(struct object_database *odb,
 			 const struct object_id *oid, enum object_type expect)
 {