Added git.git sha1 lookup method to replace simple binary search in pack backend.

Implemented find_unique_short_oid for pack backend, based on git sha1 lookup method;
finding an object given its full oid is just a particular case of searching
the unique object matching an oid prefix (short oid).

Added git_odb_read_unique_short_oid, which iterates over all the backends to
find and read the unique object matching the given oid prefix.

Added a git_object_lookup_short_oid method to find the unique object in
the repository matching a given oid prefix : it generalizes git_object_lookup
which now does nothing but calls git_object_lookup_short_oid.

1 files changed, 52 insertions, 9 deletions

diff --git a/src/object.c b/src/object.c
index d2e4da359..e6e976756 100644
--- a/src/object.c
+++ b/src/object.c
@@ -95,24 +95,63 @@ static int create_object(git_object **object_out, git_otype type)
 	return GIT_SUCCESS;
 }
 
-int git_object_lookup(git_object **object_out, git_repository *repo, const git_oid *id, git_otype type)
+int git_object_lookup_short_oid(git_object **object_out, git_repository *repo, const git_oid *id, unsigned int len, git_otype type)
 {
 	git_object *object = NULL;
 	git_odb_object *odb_obj;
 	int error = GIT_SUCCESS;
+	git_oid out_oid;
 
 	assert(repo && object_out && id);
 
-	object = git_cache_get(&repo->objects, id);
-	if (object != NULL) {
-		if (type != GIT_OBJ_ANY && type != object->type)
-			return git__throw(GIT_EINVALIDTYPE, "Failed to lookup object. The given type does not match the type on the ODB");
+	if (len == 0)
+		return git__throw(GIT_EAMBIGUOUSOIDPREFIX, "Failed to lookup object. Prefix length should be not be 0.");
+	if (len > GIT_OID_HEXSZ) {
+		len = GIT_OID_HEXSZ;
+	}
 
-		*object_out = object;
-		return GIT_SUCCESS;
+	if (len == GIT_OID_HEXSZ)  {
+		/* We want to match the full id : we can first look up in the cache,
+		 * since there is no need to check for non ambiguousity
+		 */
+		object = git_cache_get(&repo->objects, id);
+		if (object != NULL) {
+			if (type != GIT_OBJ_ANY && type != object->type)
+				return git__throw(GIT_EINVALIDTYPE, "Failed to lookup object. The given type does not match the type on the ODB");
+
+			*object_out = object;
+			return GIT_SUCCESS;
+		}
+
+		/* Object was not found in the cache, let's explore the backends.
+		 * We could just use git_odb_read_unique_short_oid,
+		 * it is the same cost for packed and loose object backends,
+		 * but it may be much more costly for sqlite and hiredis.
+		 */
+		error = git_odb_read(&odb_obj, repo->db, id);
+		git_oid_cpy(&out_oid, id);
+	} else {
+		git_oid short_oid;
+
+		/* We copy the first len*4 bits from id and fill the remaining with 0s */
+		memcpy(short_oid.id, id->id, (len + 1) / 2);
+		if (len % 2)
+			short_oid.id[len / 2] &= 0xF0;
+		memset(short_oid.id + (len + 1) / 2, 0, (GIT_OID_HEXSZ - len) / 2);
+
+		/* If len < GIT_OID_HEXSZ (a strict short oid was given), we have
+		 * 2 options :
+		 * - We always search in the cache first. If we find that short oid is
+		 *   ambiguous, we can stop. But in all the other cases, we must then
+		 *   explore all the backends (to find an object if there was match,
+		 *   or to check that oid is not ambiguous if we have found 1 match in
+		 *   the cache)
+		 * - We never explore the cache, go right to exploring the backends
+		 * We chose the latter : we explore directly the backends.
+		 */
+		error = git_odb_read_unique_short_oid(&out_oid, &odb_obj, repo->db, &short_oid, len);
 	}
 
-	error = git_odb_read(&odb_obj, repo->db, id);
 	if (error < GIT_SUCCESS)
 		return git__rethrow(error, "Failed to lookup object");
 
@@ -127,7 +166,7 @@ int git_object_lookup(git_object **object_out, git_repository *repo, const git_o
 		return git__rethrow(error, "Failed to lookup object");
 
 	/* Initialize parent object */
-	git_oid_cpy(&object->cached.oid, id);
+	git_oid_cpy(&object->cached.oid, &out_oid);
 	object->repo = repo;
 
 	switch (type) {
@@ -162,6 +201,10 @@ int git_object_lookup(git_object **object_out, git_repository *repo, const git_o
 	return GIT_SUCCESS;
 }
 
+int git_object_lookup(git_object **object_out, git_repository *repo, const git_oid *id, git_otype type) {
+	return git_object_lookup_short_oid(object_out, repo, id, GIT_OID_HEXSZ, type);
+}
+
 void git_object__free(void *_obj)
 {
 	git_object *object = (git_object *)_obj;