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

@@ -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;