[PATCH 02/10] unpack-trees: move all skip-worktree check back to unpack_trees()

["Nguyễn Thái Ngọc Duy" <pclouds@gmail.com>]

Earlier, the will_have_skip_worktree() checks are done in various places:

1. in verify_* functions to prevent absent/uptodate checks outside
   worktree
2. in merged_entry for new index entries
3. in apply_sparse_checkout() for all entries

In case all entries are added new ($GIT_DIR/index is missing) all the
above checks will be done for all entries, which in the worst case can
become cache_nr*el->nr*3 fnmatch() calls. Quite expensive.

By moving all will_have_skip_worktree() checks to unpack_trees(), we
now have two places to run the checks:

 - one before calling traverse_trees(), where all current index
   entries are checked.
 - one after traverse_trees(), where newly-added entries are checked.

In worst case, each entry will be checked once, or cache_nr*el->nr
fnmatch() calls at most. The two places are a loop over all entries,
which also makes optimization easier.

CE_ADDED is used to mark new entries. The flag is only used by
add_to_index(), which should not be called while unpack_trees() is
running.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 cache.h        |    1 +
 unpack-trees.c |   69 ++++++++++++++++++++++++++++++++++++++++++++++++++-----
 2 files changed, 63 insertions(+), 7 deletions(-)

diff --git a/cache.h b/cache.h
index 33decd9..d87708a 100644
--- a/cache.h
+++ b/cache.h
@@ -182,6 +182,7 @@ struct cache_entry {
 #define CE_WT_REMOVE (0x400000) /* remove in work directory */
 
 #define CE_UNPACKED  (0x1000000)
+#define CE_NEW_SKIP_WORKTREE (0x2000000)
 
 /*
  * Extended on-disk flags
diff --git a/unpack-trees.c b/unpack-trees.c
index 803445a..9acd9be 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -258,7 +258,7 @@ static int apply_sparse_checkout(struct cache_entry *ce, struct unpack_trees_opt
 {
 	int was_skip_worktree = ce_skip_worktree(ce);
 
-	if (!ce_stage(ce) && will_have_skip_worktree(ce, o))
+	if (ce->ce_flags & CE_NEW_SKIP_WORKTREE)
 		ce->ce_flags |= CE_SKIP_WORKTREE;
 	else
 		ce->ce_flags &= ~CE_SKIP_WORKTREE;
@@ -834,6 +834,49 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str
 	return mask;
 }
 
+static void set_new_skip_worktree_1(struct unpack_trees_options *o)
+{
+	int i;
+
+	for (i = 0;i < o->src_index->cache_nr;i++) {
+		struct cache_entry *ce = o->src_index->cache[i];
+		ce->ce_flags &= ~CE_ADDED;
+		if (!ce_stage(ce) && will_have_skip_worktree(ce, o))
+			ce->ce_flags |= CE_NEW_SKIP_WORKTREE;
+		else
+			ce->ce_flags &= ~CE_NEW_SKIP_WORKTREE;
+	}
+}
+
+static int verify_absent(struct cache_entry *, enum unpack_trees_error_types, struct unpack_trees_options *);
+static int set_new_skip_worktree_2(struct unpack_trees_options *o)
+{
+	int i;
+
+	/*
+	 * CE_ADDED marks new index entries. These have not been processed
+	 * by set_new_skip_worktree_1() so we do it here.
+	 */
+	for (i = 0;i < o->result.cache_nr;i++) {
+		struct cache_entry *ce = o->result.cache[i];
+
+		if (!(ce->ce_flags & CE_ADDED))
+			continue;
+
+		ce->ce_flags &= ~CE_ADDED;
+		if (!ce_stage(ce) && will_have_skip_worktree(ce, o))
+			ce->ce_flags |= CE_SKIP_WORKTREE | CE_NEW_SKIP_WORKTREE;
+		else
+			ce->ce_flags &= ~(CE_SKIP_WORKTREE | CE_NEW_SKIP_WORKTREE);
+
+		/* Left-over checks from merged_entry when old == NULL */
+		if (verify_absent(ce, ERROR_WOULD_LOSE_UNTRACKED_OVERWRITTEN, o))
+			return -1;
+	}
+
+	return 0;
+}
+
 /*
  * N-way merge "len" trees.  Returns 0 on success, -1 on failure to manipulate the
  * resulting index, -2 on failure to reflect the changes to the work tree.
@@ -862,6 +905,9 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 			o->el = &el;
 	}
 
+	if (!o->skip_sparse_checkout)
+		set_new_skip_worktree_1(o);
+
 	memset(&o->result, 0, sizeof(o->result));
 	o->result.initialized = 1;
 	o->result.timestamp.sec = o->src_index->timestamp.sec;
@@ -922,6 +968,10 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 
 	if (!o->skip_sparse_checkout) {
 		int empty_worktree = 1;
+
+		if (set_new_skip_worktree_2(o))
+			goto return_failed;
+
 		for (i = 0;i < o->result.cache_nr;i++) {
 			struct cache_entry *ce = o->result.cache[i];
 
@@ -1017,7 +1067,7 @@ static int verify_uptodate_1(struct cache_entry *ce,
 static int verify_uptodate(struct cache_entry *ce,
 			   struct unpack_trees_options *o)
 {
-	if (!o->skip_sparse_checkout && will_have_skip_worktree(ce, o))
+	if (!o->skip_sparse_checkout && (ce->ce_flags & CE_NEW_SKIP_WORKTREE))
 		return 0;
 	return verify_uptodate_1(ce, o, ERROR_NOT_UPTODATE_FILE);
 }
@@ -1204,7 +1254,7 @@ static int verify_absent(struct cache_entry *ce,
 			 enum unpack_trees_error_types error_type,
 			 struct unpack_trees_options *o)
 {
-	if (!o->skip_sparse_checkout && will_have_skip_worktree(ce, o))
+	if (!o->skip_sparse_checkout && (ce->ce_flags & CE_NEW_SKIP_WORKTREE))
 		return 0;
 	return verify_absent_1(ce, error_type, o);
 }
@@ -1226,10 +1276,15 @@ static int merged_entry(struct cache_entry *merge, struct cache_entry *old,
 	int update = CE_UPDATE;
 
 	if (!old) {
+		/*
+		 * Set CE_NEW_SKIP_WORKTREE on "merge" to make
+		 * verify_absent() no-op. The true check will be done
+		 * later on in unpack_trees().
+		 */
+		merge->ce_flags |= CE_NEW_SKIP_WORKTREE;
 		if (verify_absent(merge, ERROR_WOULD_LOSE_UNTRACKED_OVERWRITTEN, o))
 			return -1;
-		if (!o->skip_sparse_checkout && will_have_skip_worktree(merge, o))
-			update |= CE_SKIP_WORKTREE;
+		update |= CE_ADDED;
 		invalidate_ce_path(merge, o);
 	} else if (!(old->ce_flags & CE_CONFLICTED)) {
 		/*
@@ -1245,8 +1300,8 @@ static int merged_entry(struct cache_entry *merge, struct cache_entry *old,
 		} else {
 			if (verify_uptodate(old, o))
 				return -1;
-			if (ce_skip_worktree(old))
-				update |= CE_SKIP_WORKTREE;
+			/* Migrate old bits over */
+			update |= old->ce_flags & (CE_SKIP_WORKTREE | CE_NEW_SKIP_WORKTREE);
 			invalidate_ce_path(old, o);
 		}
 	} else {
-- 
1.7.3.2.210.g045198