[RFC PATCH 07/15] cache_tree_update(): Capability to handle tree entries missing from index

[Elijah Newren <newren@gmail.com>]

cache_tree_update() will write trees using the index.  With sparse clones,
the index will only contain entries matching the sparse limits, meaning
that the index does not provide enough information to write complete tree
objects.  Having cache_tree_update() take a tree (typically HEAD), will
allow new complete trees to be constructed by using entries from the
specified tree outside the sparse limits together with the index.

Of course, in the non-sparse clone case, cache_tree_update() needs no tree
to be provided since the index contains all relevant information.  So
providing NULL as the tree is supported as another way of getting the
traditional behavior.

This patch only provides the new capability without invoking it; subsequent
patches will update callers of cache_tree_update() to provide a relevant
tree.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 cache-tree.c |   88 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 87 insertions(+), 1 deletions(-)

diff --git a/cache-tree.c b/cache-tree.c
index c60cf91..2ba6a76 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -2,6 +2,7 @@
 #include "tree.h"
 #include "tree-walk.h"
 #include "cache-tree.h"
+#include "diff.h"  /* FIXME: for tree_entry_interesting; maybe it should be in tree-walk.h? */
 
 #ifndef DEBUG
 #define DEBUG 0
@@ -232,15 +233,91 @@ int cache_tree_fully_valid(struct cache_tree *it)
 	return 1;
 }
 
+static void setup_tree_desc(struct tree_desc *desc, struct tree* tree)
+{
+	if (git_sparse_pathspecs && tree)
+		init_tree_desc(desc, tree->buffer, tree->size);
+	else
+		init_tree_desc(desc, NULL, 0);
+}
+
+static struct tree* find_non_sparse_subtree(struct tree_desc *desc,
+					    const char *path,
+					    int pathlen)
+{
+	struct name_entry entry;
+
+	if (!git_sparse_pathspecs)
+		return NULL; /* No tree needed or useful */
+
+	while (tree_entry(desc, &entry))
+		  if (!memcmp(entry.path, path, pathlen) &&
+		      strlen(entry.path) == pathlen) {
+			struct tree *subtree = lookup_tree(entry.sha1);
+			if (parse_tree(subtree) < 0)
+				die("bad tree %s", sha1_to_hex(entry.sha1));
+			return subtree;
+		  }
+	return NULL;
+}
+
+static void add_missing_paths_before(const char *path,
+				     int pathlen,
+				     int baselen,
+				     struct tree_desc *desc,
+				     struct strbuf *buffer)
+{
+	if (!git_sparse_pathspecs)
+		return; /* No paths are missing */
+
+	for (; desc->size; update_tree_entry(desc)) {
+		struct name_entry entry = desc->entry;
+		int entlen = strlen(entry.path);
+
+		/* We only want paths before path */
+		if (path)
+			/*
+			 * FIXME: if entlen < pathlen, do I need to
+			 * use strncmp instead? Does entry.path being
+			 * NUL-terminated ensure memcmp exits
+			 * early?
+			 */
+			if (memcmp(entry.path,
+				   path+baselen,
+				   pathlen-baselen) >= 0)
+				break;
+
+		/* We only want paths "missing" from index due to sparsity */
+		if (path) {
+			int show = tree_entry_interesting(desc,
+							  path,
+							  baselen,
+							  &git_sparse_diffopts);
+			if (show == 2) {
+				desc->size = 0;
+				break;
+			}
+			else if (show > 0)
+				continue;
+		}
+
+		strbuf_grow(buffer, entlen + 100);
+		strbuf_addf(buffer, "%o %.*s%c", entry.mode, entlen, entry.path, '\0');
+		strbuf_add(buffer, entry.sha1, 20);
+	}
+}
+
 static int update_one(struct cache_tree *it,
 		      struct cache_entry **cache,
 		      int entries,
+		      struct tree *non_sparse_tree,
 		      const char *base,
 		      int baselen,
 		      int missing_ok,
 		      int dryrun)
 {
 	struct strbuf buffer;
+	struct tree_desc desc;
 	int i;
 
 	if (0 <= it->entry_count && has_sha1_file(it->sha1))
@@ -257,9 +334,11 @@ static int update_one(struct cache_tree *it,
 	/*
 	 * Find the subtrees and update them.
 	 */
+	setup_tree_desc(&desc, non_sparse_tree);
 	for (i = 0; i < entries; i++) {
 		struct cache_entry *ce = cache[i];
 		struct cache_tree_sub *sub;
+		struct tree *subtree;
 		const char *path, *slash;
 		int pathlen, sublen, subcnt;
 
@@ -280,8 +359,10 @@ static int update_one(struct cache_tree *it,
 		sub = find_subtree(it, path + baselen, sublen, 1);
 		if (!sub->cache_tree)
 			sub->cache_tree = cache_tree();
+		subtree = find_non_sparse_subtree(&desc, path+baselen, sublen);
 		subcnt = update_one(sub->cache_tree,
 				    cache + i, entries - i,
+				    subtree,
 				    path,
 				    baselen + sublen + 1,
 				    missing_ok,
@@ -298,6 +379,7 @@ static int update_one(struct cache_tree *it,
 	 * Then write out the tree object for this level.
 	 */
 	strbuf_init(&buffer, 8192);
+	setup_tree_desc(&desc, non_sparse_tree);
 
 	for (i = 0; i < entries; i++) {
 		struct cache_entry *ce = cache[i];
@@ -309,6 +391,8 @@ static int update_one(struct cache_tree *it,
 
 		path = ce->name;
 		pathlen = ce_namelen(ce);
+		add_missing_paths_before(path, pathlen, baselen,
+					 &desc, &buffer);
 		if (pathlen <= baselen || memcmp(base, path, baselen))
 			break; /* at the end of this level */
 
@@ -346,6 +430,7 @@ static int update_one(struct cache_tree *it,
 			mode, entlen, path + baselen);
 #endif
 	}
+	add_missing_paths_before(NULL, 0, 0, &desc, &buffer);
 
 	if (dryrun)
 		hash_sha1_file(buffer.buf, buffer.len, tree_type, it->sha1);
@@ -374,7 +459,8 @@ int cache_tree_update(struct cache_tree *it,
 	i = verify_cache(cache, entries);
 	if (i)
 		return i;
-	i = update_one(it, cache, entries, "", 0, missing_ok, dryrun);
+
+	i = update_one(it, cache, entries, NULL, "", 0, missing_ok, dryrun);
 	if (i < 0)
 		return i;
 	return 0;
-- 
1.7.2.2.140.gd06af