[PATCH 0/5] Sparse checkout fixes

[PATCH 0/5] Sparse checkout fixes

[Nguyễn Thái Ngọc Duy]

[on top of nd/maint-fix-add-typo-detection]

This fixes a sparse pattern sometimes won't match a directory if
 - it does not end with a slash
 - it has wildcards

The series also improves performance a bit, thanks to 3/5, skip-worktree
bits are precomputed.

Improvements in the previous round [1] are left out. I will need to
polish them a bit more.

[1] http://thread.gmane.org/gmane.comp.version-control.git/161477

Nguyễn Thái Ngọc Duy (5):
  cache.h: remove surrounding brackes and realign CE_* constants
  dir.c: add free_excludes()
  unpack-trees: move all skip-worktree checks back to unpack_trees()
  unpack-trees: fix sparse checkout's "unable to match directories"
  Revert "excluded_1(): support exclude files in index"

 Documentation/git-read-tree.txt      |    7 -
 cache.h                              |   26 ++--
 dir.c                                |   19 ++-
 dir.h                                |    1 +
 t/t1011-read-tree-sparse-checkout.sh |   14 ++-
 unpack-trees.c                       |  240 ++++++++++++++++++++++++++++++----
 6 files changed, 254 insertions(+), 53 deletions(-)

-- 
1.7.3.2.316.gda8b3

[PATCH 1/5] cache.h: remove surrounding brackes and realign CE_* constants

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 cache.h |   25 ++++++++++++-------------
 1 files changed, 12 insertions(+), 13 deletions(-)

diff --git a/cache.h b/cache.h
index 33decd9..4819cf5 100644
--- a/cache.h
+++ b/cache.h
@@ -170,26 +170,25 @@ struct cache_entry {
  *
  * In-memory only flags
  */
-#define CE_UPDATE    (0x10000)
-#define CE_REMOVE    (0x20000)
-#define CE_UPTODATE  (0x40000)
-#define CE_ADDED     (0x80000)
+#define CE_UPDATE              0x10000
+#define CE_REMOVE              0x20000
+#define CE_UPTODATE            0x40000
+#define CE_ADDED               0x80000
 
-#define CE_HASHED    (0x100000)
-#define CE_UNHASHED  (0x200000)
-#define CE_CONFLICTED (0x800000)
+#define CE_HASHED             0x100000
+#define CE_UNHASHED           0x200000
+#define CE_WT_REMOVE          0x400000 /* remove in work directory */
+#define CE_CONFLICTED         0x800000
 
-#define CE_WT_REMOVE (0x400000) /* remove in work directory */
-
-#define CE_UNPACKED  (0x1000000)
+#define CE_UNPACKED          0x1000000
 
 /*
  * Extended on-disk flags
  */
-#define CE_INTENT_TO_ADD 0x20000000
-#define CE_SKIP_WORKTREE 0x40000000
+#define CE_INTENT_TO_ADD    0x20000000
+#define CE_SKIP_WORKTREE    0x40000000
 /* CE_EXTENDED2 is for future extension */
-#define CE_EXTENDED2 0x80000000
+#define CE_EXTENDED2        0x80000000
 
 #define CE_EXTENDED_FLAGS (CE_INTENT_TO_ADD | CE_SKIP_WORKTREE)
 
-- 
1.7.3.2.316.gda8b3

Re: [PATCH 1/5] cache.h: remove surrounding brackes and realign CE_* constants

[Thiago Farina]

2010/11/26 Nguyễn Thái Ngọc Duy <pclouds@gmail.com>:
>
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
> ---
>  cache.h |   25 ++++++++++++-------------
>  1 files changed, 12 insertions(+), 13 deletions(-)
>
> diff --git a/cache.h b/cache.h
> index 33decd9..4819cf5 100644
> --- a/cache.h
> +++ b/cache.h
> @@ -170,26 +170,25 @@ struct cache_entry {
>  *
>  * In-memory only flags
>  */
> -#define CE_UPDATE    (0x10000)
> -#define CE_REMOVE    (0x20000)
> -#define CE_UPTODATE  (0x40000)
> -#define CE_ADDED     (0x80000)
> +#define CE_UPDATE              0x10000
> +#define CE_REMOVE              0x20000
> +#define CE_UPTODATE            0x40000
> +#define CE_ADDED               0x80000
>
Thanks for fixing this. Maybe these hex can be rewriting as 1 << 0, 1
<< 1 and so on?

[PATCH 1/5] cache.h: realign and use (1 << x) form for CE_* constants

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 2010/11/27 Thiago Farina <tfransosi@gmail.com>:
 > Thanks for fixing this. Maybe these hex can be rewriting as 1 << 0, 1
 > << 1 and so on?
 >

 It does look better. There a few 0xXXXX constants above, but they
 are short enough.

 cache.h |   25 ++++++++++++-------------
 1 files changed, 12 insertions(+), 13 deletions(-)

diff --git a/cache.h b/cache.h
index 33decd9..f9545a1 100644
--- a/cache.h
+++ b/cache.h
@@ -170,26 +170,25 @@ struct cache_entry {
  *
  * In-memory only flags
  */
-#define CE_UPDATE    (0x10000)
-#define CE_REMOVE    (0x20000)
-#define CE_UPTODATE  (0x40000)
-#define CE_ADDED     (0x80000)
+#define CE_UPDATE            (1 << 16)
+#define CE_REMOVE            (1 << 17)
+#define CE_UPTODATE          (1 << 18)
+#define CE_ADDED             (1 << 19)
 
-#define CE_HASHED    (0x100000)
-#define CE_UNHASHED  (0x200000)
-#define CE_CONFLICTED (0x800000)
+#define CE_HASHED            (1 << 20)
+#define CE_UNHASHED          (1 << 21)
+#define CE_WT_REMOVE         (1 << 22) /* remove in work directory */
+#define CE_CONFLICTED        (1 << 23)
 
-#define CE_WT_REMOVE (0x400000) /* remove in work directory */
-
-#define CE_UNPACKED  (0x1000000)
+#define CE_UNPACKED          (1 << 24)
 
 /*
  * Extended on-disk flags
  */
-#define CE_INTENT_TO_ADD 0x20000000
-#define CE_SKIP_WORKTREE 0x40000000
+#define CE_INTENT_TO_ADD     (1 << 29)
+#define CE_SKIP_WORKTREE     (1 << 30)
 /* CE_EXTENDED2 is for future extension */
-#define CE_EXTENDED2 0x80000000
+#define CE_EXTENDED2         (1 << 31)
 
 #define CE_EXTENDED_FLAGS (CE_INTENT_TO_ADD | CE_SKIP_WORKTREE)
 
-- 
1.7.3.2.316.gda8b3

[PATCH 2/5] dir.c: add free_excludes()

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 dir.c          |   12 ++++++++++++
 dir.h          |    1 +
 unpack-trees.c |    6 +-----
 3 files changed, 14 insertions(+), 5 deletions(-)

diff --git a/dir.c b/dir.c
index b2dfb69..39eb7a3 100644
--- a/dir.c
+++ b/dir.c
@@ -223,6 +223,18 @@ static void *read_skip_worktree_file_from_index(const char *path, size_t *size)
 	return data;
 }
 
+void free_excludes(struct exclude_list *el)
+{
+	int i;
+
+	for (i = 0; i < el->nr; i++)
+		free(el->excludes[i]);
+	free(el->excludes);
+
+	el->nr = 0;
+	el->excludes = NULL;
+}
+
 int add_excludes_from_file_to_list(const char *fname,
 				   const char *base,
 				   int baselen,
diff --git a/dir.h b/dir.h
index 278d84c..ce55008 100644
--- a/dir.h
+++ b/dir.h
@@ -78,6 +78,7 @@ extern int add_excludes_from_file_to_list(const char *fname, const char *base, i
 extern void add_excludes_from_file(struct dir_struct *, const char *fname);
 extern void add_exclude(const char *string, const char *base,
 			int baselen, struct exclude_list *which);
+extern void free_excludes(struct exclude_list *el);
 extern int file_exists(const char *);
 
 extern char *get_relative_cwd(char *buffer, int size, const char *dir);
diff --git a/unpack-trees.c b/unpack-trees.c
index 803445a..4d92412 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -945,11 +945,7 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 		*o->dst_index = o->result;
 
 done:
-	for (i = 0;i < el.nr;i++)
-		free(el.excludes[i]);
-	if (el.excludes)
-		free(el.excludes);
-
+	free_excludes(&el);
 	return ret;
 
 return_failed:
-- 
1.7.3.2.316.gda8b3

[PATCH 3/5] unpack-trees: move all skip-worktree checks back to unpack_trees()

[Nguyễn Thái Ngọc Duy]

Earlier, the will_have_skip_worktree() checks are done in various
places, which makes it hard to traverse the index tree-alike, required
by excluded_from_list(). This patch moves all the checks into two
loops in unpack_trees().

Entries in index in this operation can be classified into two
groups: ones already in index before unpack_trees() is called and ones
added to index after traverse_trees() is called.

In both groups, before checking file status on worktree, the future
skip-worktree bit must be checked, so that if an entry will be outside
worktree, worktree should not be checked.

For the first group, the future skip-worktree bit is precomputed and
stored as CE_NEW_SKIP_WORKTREE in the first loop before
traverse_trees() is called so that *way_merge() function does not need
to compute it again.

For the second group, because we don't know what entries will be in
this group until traverse_trees() finishes, operations that need
future skip-worktree check is delayed until CE_NEW_SKIP_WORKTREE is
computed in the second loop. CE_ADDED is used to mark entries in the
second group.

CE_ADDED and CE_NEW_SKIP_WORKTREE are temporary flags used in
unpack_trees().  CE_ADDED 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 |   82 +++++++++++++++++++++++++++++++++++++++++++++++++------
 2 files changed, 74 insertions(+), 9 deletions(-)

diff --git a/cache.h b/cache.h
index 4819cf5..52b998b 100644
--- a/cache.h
+++ b/cache.h
@@ -181,6 +181,7 @@ struct cache_entry {
 #define CE_CONFLICTED         0x800000
 
 #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 4d92412..a6518db 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;
@@ -333,7 +333,7 @@ static void mark_all_ce_unused(struct index_state *index)
 {
 	int i;
 	for (i = 0; i < index->cache_nr; i++)
-		index->cache[i]->ce_flags &= ~CE_UNPACKED;
+		index->cache[i]->ce_flags &= ~(CE_UNPACKED | CE_ADDED | CE_NEW_SKIP_WORKTREE);
 }
 
 static int locate_in_src_index(struct cache_entry *ce,
@@ -835,8 +835,33 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str
 }
 
 /*
+ * Set/Clear CE_NEW_SKIP_WORKTREE according to $GIT_DIR/info/sparse-checkout
+ */
+static void mark_new_skip_worktree(struct exclude_list *el,
+				   struct index_state *the_index,
+				   int select_flag, int skip_wt_flag)
+{
+	int i;
+
+	for (i = 0; i < the_index->cache_nr; i++) {
+		struct cache_entry *ce = the_index->cache[i];
+
+		if (select_flag && !(ce->ce_flags & select_flag))
+			continue;
+
+		if (!ce_stage(ce) && will_have_skip_worktree(ce, o))
+			ce->ce_flags |= skip_wt_flag;
+		else
+			ce->ce_flags &= ~skip_wt_flag;
+	}
+}
+
+static int verify_absent(struct cache_entry *, enum unpack_trees_error_types, struct unpack_trees_options *);
+/*
  * 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.
+ *
+ * CE_ADDED, CE_UNPACKED and CE_NEW_SKIP_WORKTREE are used internally
  */
 int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options *o)
 {
@@ -869,6 +894,12 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 	o->merge_size = len;
 	mark_all_ce_unused(o->src_index);
 
+	/*
+	 * Sparse checkout loop #1: set NEW_SKIP_WORKTREE on existing entries
+	 */
+	if (!o->skip_sparse_checkout)
+		mark_new_skip_worktree(o->el, o->src_index, 0, CE_NEW_SKIP_WORKTREE);
+
 	if (!dfc)
 		dfc = xcalloc(1, cache_entry_size(0));
 	o->df_conflict_entry = dfc;
@@ -922,9 +953,29 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 
 	if (!o->skip_sparse_checkout) {
 		int empty_worktree = 1;
-		for (i = 0;i < o->result.cache_nr;i++) {
+
+		/*
+		 * Sparse checkout loop #2: set NEW_SKIP_WORKTREE on entries not in loop #1
+		 * If the will have NEW_SKIP_WORKTREE, also set CE_SKIP_WORKTREE
+		 * so apply_sparse_checkout() won't attempt to remove it from worktree
+		 */
+		mark_new_skip_worktree(o->el, &o->result, CE_ADDED, CE_SKIP_WORKTREE | CE_NEW_SKIP_WORKTREE);
+
+		for (i = 0; i < o->result.cache_nr; i++) {
 			struct cache_entry *ce = o->result.cache[i];
 
+			/*
+			 * Entries marked with CE_ADDED in merged_entry() do not have
+			 * verify_absent() check (the check is effectively disabled
+			 * because CE_NEW_SKIP_WORKTREE is set unconditionally).
+			 *
+			 * Do the real check now because we have had
+			 * correct CE_NEW_SKIP_WORKTREE
+			 */
+			if (ce->ce_flags & CE_ADDED &&
+			    verify_absent(ce, ERROR_WOULD_LOSE_UNTRACKED_OVERWRITTEN, o))
+					return -1;
+
 			if (apply_sparse_checkout(ce, o)) {
 				ret = -1;
 				goto done;
@@ -1013,7 +1064,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);
 }
@@ -1200,7 +1251,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);
 }
@@ -1222,10 +1273,23 @@ static int merged_entry(struct cache_entry *merge, struct cache_entry *old,
 	int update = CE_UPDATE;
 
 	if (!old) {
+		/*
+		 * New index entries. In sparse checkout, the following
+		 * verify_absent() will be delayed until after
+		 * traverse_trees() finishes in unpack_trees(), then:
+		 *
+		 *  - CE_NEW_SKIP_WORKTREE will be computed correctly
+		 *  - verify_absent() be called again, this time with
+		 *    correct CE_NEW_SKIP_WORKTREE
+		 *
+		 * verify_absent() call here does nothing in sparse
+		 * checkout (i.e. o->skip_sparse_checkout == 0)
+		 */
+		update |= CE_ADDED;
+		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;
 		invalidate_ce_path(merge, o);
 	} else if (!(old->ce_flags & CE_CONFLICTED)) {
 		/*
@@ -1241,8 +1305,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 flags over */
+			update |= old->ce_flags & (CE_SKIP_WORKTREE | CE_NEW_SKIP_WORKTREE);
 			invalidate_ce_path(old, o);
 		}
 	} else {
-- 
1.7.3.2.316.gda8b3

[PATCH 3/5] unpack-trees: move all skip-worktree checks back to unpack_trees()

[Nguyễn Thái Ngọc Duy]

Earlier, the will_have_skip_worktree() checks are done in various
places, which makes it hard to traverse the index tree-alike, required
by excluded_from_list(). This patch moves all the checks into two
loops in unpack_trees().

Entries in index in this operation can be classified into two
groups: ones already in index before unpack_trees() is called and ones
added to index after traverse_trees() is called.

In both groups, before checking file status on worktree, the future
skip-worktree bit must be checked, so that if an entry will be outside
worktree, worktree should not be checked.

For the first group, the future skip-worktree bit is precomputed and
stored as CE_NEW_SKIP_WORKTREE in the first loop before
traverse_trees() is called so that *way_merge() function does not need
to compute it again.

For the second group, because we don't know what entries will be in
this group until traverse_trees() finishes, operations that need
future skip-worktree check is delayed until CE_NEW_SKIP_WORKTREE is
computed in the second loop. CE_ADDED is used to mark entries in the
second group.

CE_ADDED and CE_NEW_SKIP_WORKTREE are temporary flags used in
unpack_trees().  CE_ADDED 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>
---
 CE_NEW_SKIP_WORKTREE is changed to (1 << 25) instead of 0x2000000

 cache.h        |    1 +
 unpack-trees.c |   82 +++++++++++++++++++++++++++++++++++++++++++++++++------
 2 files changed, 74 insertions(+), 9 deletions(-)

diff --git a/cache.h b/cache.h
index f9545a1..cb69318 100644
--- a/cache.h
+++ b/cache.h
@@ -181,6 +181,7 @@ struct cache_entry {
 #define CE_CONFLICTED        (1 << 23)
 
 #define CE_UNPACKED          (1 << 24)
+#define CE_NEW_SKIP_WORKTREE (1 << 25)
 
 /*
  * Extended on-disk flags
diff --git a/unpack-trees.c b/unpack-trees.c
index 4d92412..a6518db 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;
@@ -333,7 +333,7 @@ static void mark_all_ce_unused(struct index_state *index)
 {
 	int i;
 	for (i = 0; i < index->cache_nr; i++)
-		index->cache[i]->ce_flags &= ~CE_UNPACKED;
+		index->cache[i]->ce_flags &= ~(CE_UNPACKED | CE_ADDED | CE_NEW_SKIP_WORKTREE);
 }
 
 static int locate_in_src_index(struct cache_entry *ce,
@@ -835,8 +835,33 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str
 }
 
 /*
+ * Set/Clear CE_NEW_SKIP_WORKTREE according to $GIT_DIR/info/sparse-checkout
+ */
+static void mark_new_skip_worktree(struct exclude_list *el,
+				   struct index_state *the_index,
+				   int select_flag, int skip_wt_flag)
+{
+	int i;
+
+	for (i = 0; i < the_index->cache_nr; i++) {
+		struct cache_entry *ce = the_index->cache[i];
+
+		if (select_flag && !(ce->ce_flags & select_flag))
+			continue;
+
+		if (!ce_stage(ce) && will_have_skip_worktree(ce, o))
+			ce->ce_flags |= skip_wt_flag;
+		else
+			ce->ce_flags &= ~skip_wt_flag;
+	}
+}
+
+static int verify_absent(struct cache_entry *, enum unpack_trees_error_types, struct unpack_trees_options *);
+/*
  * 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.
+ *
+ * CE_ADDED, CE_UNPACKED and CE_NEW_SKIP_WORKTREE are used internally
  */
 int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options *o)
 {
@@ -869,6 +894,12 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 	o->merge_size = len;
 	mark_all_ce_unused(o->src_index);
 
+	/*
+	 * Sparse checkout loop #1: set NEW_SKIP_WORKTREE on existing entries
+	 */
+	if (!o->skip_sparse_checkout)
+		mark_new_skip_worktree(o->el, o->src_index, 0, CE_NEW_SKIP_WORKTREE);
+
 	if (!dfc)
 		dfc = xcalloc(1, cache_entry_size(0));
 	o->df_conflict_entry = dfc;
@@ -922,9 +953,29 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 
 	if (!o->skip_sparse_checkout) {
 		int empty_worktree = 1;
-		for (i = 0;i < o->result.cache_nr;i++) {
+
+		/*
+		 * Sparse checkout loop #2: set NEW_SKIP_WORKTREE on entries not in loop #1
+		 * If the will have NEW_SKIP_WORKTREE, also set CE_SKIP_WORKTREE
+		 * so apply_sparse_checkout() won't attempt to remove it from worktree
+		 */
+		mark_new_skip_worktree(o->el, &o->result, CE_ADDED, CE_SKIP_WORKTREE | CE_NEW_SKIP_WORKTREE);
+
+		for (i = 0; i < o->result.cache_nr; i++) {
 			struct cache_entry *ce = o->result.cache[i];
 
+			/*
+			 * Entries marked with CE_ADDED in merged_entry() do not have
+			 * verify_absent() check (the check is effectively disabled
+			 * because CE_NEW_SKIP_WORKTREE is set unconditionally).
+			 *
+			 * Do the real check now because we have had
+			 * correct CE_NEW_SKIP_WORKTREE
+			 */
+			if (ce->ce_flags & CE_ADDED &&
+			    verify_absent(ce, ERROR_WOULD_LOSE_UNTRACKED_OVERWRITTEN, o))
+					return -1;
+
 			if (apply_sparse_checkout(ce, o)) {
 				ret = -1;
 				goto done;
@@ -1013,7 +1064,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);
 }
@@ -1200,7 +1251,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);
 }
@@ -1222,10 +1273,23 @@ static int merged_entry(struct cache_entry *merge, struct cache_entry *old,
 	int update = CE_UPDATE;
 
 	if (!old) {
+		/*
+		 * New index entries. In sparse checkout, the following
+		 * verify_absent() will be delayed until after
+		 * traverse_trees() finishes in unpack_trees(), then:
+		 *
+		 *  - CE_NEW_SKIP_WORKTREE will be computed correctly
+		 *  - verify_absent() be called again, this time with
+		 *    correct CE_NEW_SKIP_WORKTREE
+		 *
+		 * verify_absent() call here does nothing in sparse
+		 * checkout (i.e. o->skip_sparse_checkout == 0)
+		 */
+		update |= CE_ADDED;
+		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;
 		invalidate_ce_path(merge, o);
 	} else if (!(old->ce_flags & CE_CONFLICTED)) {
 		/*
@@ -1241,8 +1305,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 flags over */
+			update |= old->ce_flags & (CE_SKIP_WORKTREE | CE_NEW_SKIP_WORKTREE);
 			invalidate_ce_path(old, o);
 		}
 	} else {
-- 
1.7.3.2.316.gda8b3

[PATCH 4/5] unpack-trees: fix sparse checkout's "unable to match directories"

[Nguyễn Thái Ngọc Duy]

Matching index entries against an excludes file currently has two
problems.

First, there's no function to do it.  Code paths (like sparse
checkout) that wanted to try it would iterate over index entries and
for each index entry pass that path to excluded_from_list().  But that
is not how excluded_from_list() works; one is supposed to feed in each
ancester of a path before a given path to find out if it was excluded
because of some parent or grandparent matching a

  bigsubdirectory/

pattern despite the path not matching any .gitignore pattern directly.

Second, it's inefficient.  The excludes mechanism is supposed to let
us block off vast swaths of the filesystem as uninteresting; separately
checking every index entry doesn't fit that model.

Introduce a new function to take care of both these problems.  This
traverses the index in depth-first order (well, that's what order the
index is in) to mark un-excluded entries.

Maybe some day the in-core index format will be restructured to make
this sort of operation easier.  Or maybe we will want to try some
binary search based thing.  The interface is simple enough to allow
all those things.  Example:

  clear_ce_flags(the_index.cache, the_index.cache_nr,
                 CE_CANDIDATE, CE_CLEARME, exclude_list);

would clear the CE_CLEARME flag on all index entries with
CE_CANDIDATE flag and not matched by exclude_list.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 Documentation/git-read-tree.txt      |    7 --
 t/t1011-read-tree-sparse-checkout.sh |   14 +++-
 unpack-trees.c                       |  154 +++++++++++++++++++++++++++++++--
 3 files changed, 155 insertions(+), 20 deletions(-)

diff --git a/Documentation/git-read-tree.txt b/Documentation/git-read-tree.txt
index 2e78da4..f6037c4 100644
--- a/Documentation/git-read-tree.txt
+++ b/Documentation/git-read-tree.txt
@@ -412,13 +412,6 @@ turn `core.sparseCheckout` on in order to have sparse checkout
 support.
 
 
-BUGS
-----
-In order to match a directory with $GIT_DIR/info/sparse-checkout,
-trailing slash must be used. The form without trailing slash, while
-works with .gitignore, does not work with sparse checkout.
-
-
 SEE ALSO
 --------
 linkgit:git-write-tree[1]; linkgit:git-ls-files[1];
diff --git a/t/t1011-read-tree-sparse-checkout.sh b/t/t1011-read-tree-sparse-checkout.sh
index 8008fa2..67d9217 100755
--- a/t/t1011-read-tree-sparse-checkout.sh
+++ b/t/t1011-read-tree-sparse-checkout.sh
@@ -94,12 +94,20 @@ test_expect_success 'match directories with trailing slash' '
 	test -f sub/added
 '
 
-test_expect_failure 'match directories without trailing slash' '
-	echo init.t >.git/info/sparse-checkout &&
+test_expect_success 'match directories without trailing slash' '
 	echo sub >>.git/info/sparse-checkout &&
 	git read-tree -m -u HEAD &&
 	git ls-files -t >result &&
-	test_cmp expected.swt result &&
+	test_cmp expected.swt-noinit result &&
+	test ! -f init.t &&
+	test -f sub/added
+'
+
+test_expect_success 'match directory pattern' '
+	echo "s?b" >>.git/info/sparse-checkout &&
+	git read-tree -m -u HEAD &&
+	git ls-files -t >result &&
+	test_cmp expected.swt-noinit result &&
 	test ! -f init.t &&
 	test -f sub/added
 '
diff --git a/unpack-trees.c b/unpack-trees.c
index a6518db..06de723 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -245,15 +245,6 @@ static int check_updates(struct unpack_trees_options *o)
 static int verify_uptodate_sparse(struct cache_entry *ce, struct unpack_trees_options *o);
 static int verify_absent_sparse(struct cache_entry *ce, enum unpack_trees_error_types, struct unpack_trees_options *o);
 
-static int will_have_skip_worktree(const struct cache_entry *ce, struct unpack_trees_options *o)
-{
-	const char *basename;
-
-	basename = strrchr(ce->name, '/');
-	basename = basename ? basename+1 : ce->name;
-	return excluded_from_list(ce->name, ce_namelen(ce), basename, NULL, o->el) <= 0;
-}
-
 static int apply_sparse_checkout(struct cache_entry *ce, struct unpack_trees_options *o)
 {
 	int was_skip_worktree = ce_skip_worktree(ce);
@@ -834,6 +825,138 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str
 	return mask;
 }
 
+/* Whole directory matching */
+static int clear_ce_flags_dir(struct cache_entry **cache, int nr,
+			      char *prefix, int prefix_len,
+			      char *basename,
+			      int select_mask, int clear_mask,
+			      struct exclude_list *el)
+{
+	struct cache_entry **cache_end = cache + nr;
+	int dtype = DT_DIR;
+	int ret = excluded_from_list(prefix, prefix_len, basename, &dtype, el);
+
+	prefix[prefix_len++] = '/';
+
+	/* included, no clearing for any entries under this directory */
+	if (!ret) {
+		for (; cache != cache_end; cache++) {
+			struct cache_entry *ce = *cache;
+			if (strncmp(ce->name, prefix, prefix_len))
+				break;
+		}
+		return nr - (cache_end - cache);
+	}
+
+	/* excluded, clear all selected entries under this directory. */
+	if (ret == 1) {
+		for (; cache != cache_end; cache++) {
+			struct cache_entry *ce = *cache;
+			if (select_mask && !(ce->ce_flags & select_mask))
+				continue;
+			if (strncmp(ce->name, prefix, prefix_len))
+				break;
+			ce->ce_flags &= ~clear_mask;
+		}
+		return nr - (cache_end - cache);
+	}
+
+	return 0;
+}
+
+/*
+ * Traverse the index, find every entry that matches according to
+ * o->el. Do "ce_flags &= ~clear_mask" on those entries. Return the
+ * number of traversed entries.
+ *
+ * If select_mask is non-zero, only entries whose ce_flags has on of
+ * those bits enabled are traversed.
+ *
+ * cache	: pointer to an index entry
+ * prefix_len	: an offset to its path
+ *
+ * The current path ("prefix") including the trailing '/' is
+ *   cache[0]->name[0..(prefix_len-1)]
+ * Top level path has prefix_len zero.
+ */
+static int clear_ce_flags_1(struct cache_entry **cache, int nr,
+			    char *prefix, int prefix_len,
+			    int select_mask, int clear_mask,
+			    struct exclude_list *el)
+{
+	struct cache_entry **cache_end = cache + nr;
+
+	/*
+	 * Process all entries that have the given prefix and meet
+	 * select_mask condition
+	 */
+	while(cache != cache_end) {
+		struct cache_entry *ce = *cache;
+		const char *name, *slash;
+		int len, dtype;
+
+		if (select_mask && !(ce->ce_flags & select_mask)) {
+			cache++;
+			continue;
+		}
+
+		if (prefix_len && strncmp(ce->name, prefix, prefix_len))
+			break;
+
+		name = ce->name + prefix_len;
+		slash = strchr(name, '/');
+
+		/* If it's a directory, try whole directory match first */
+		if (slash) {
+			len = slash - name;
+			int processed;
+
+			memcpy(prefix + prefix_len, name, len);
+
+			/*
+			 * terminate the string (no trailing slash),
+			 * clear_c_f_dir needs it
+			 */
+			prefix[prefix_len + len] = '\0';
+			processed = clear_ce_flags_dir(cache, cache_end - cache,
+						       prefix, prefix_len + len,
+						       prefix + prefix_len,
+						       select_mask, clear_mask,
+						       el);
+
+			/* clear_c_f_dir eats a whole dir already? */
+			if (processed) {
+				cache += processed;
+				continue;
+			}
+
+			prefix[prefix_len + len++] = '/';
+			cache += clear_ce_flags_1(cache, cache_end - cache,
+						  prefix, prefix_len + len,
+						  select_mask, clear_mask, el);
+			continue;
+		}
+
+		/* Non-directory */
+		dtype = ce_to_dtype(ce);
+		if (excluded_from_list(ce->name, ce_namelen(ce), name, &dtype, el) > 0)
+			ce->ce_flags &= ~clear_mask;
+		cache++;
+	}
+	return nr - (cache_end - cache);
+}
+
+static int clear_ce_flags(struct cache_entry **cache, int nr,
+			    int select_mask, int clear_mask,
+			    struct exclude_list *el)
+{
+	char prefix[PATH_MAX];
+	return clear_ce_flags_1(cache, nr,
+				prefix, 0,
+				select_mask, clear_mask,
+				el);
+}
+
 /*
  * Set/Clear CE_NEW_SKIP_WORKTREE according to $GIT_DIR/info/sparse-checkout
  */
@@ -843,17 +966,28 @@ static void mark_new_skip_worktree(struct exclude_list *el,
 {
 	int i;
 
+	/*
+	 * 1. Pretend the narrowest worktree: only unmerged entries
+	 * are checked out
+	 */
 	for (i = 0; i < the_index->cache_nr; i++) {
 		struct cache_entry *ce = the_index->cache[i];
 
 		if (select_flag && !(ce->ce_flags & select_flag))
 			continue;
 
-		if (!ce_stage(ce) && will_have_skip_worktree(ce, o))
+		if (!ce_stage(ce))
 			ce->ce_flags |= skip_wt_flag;
 		else
 			ce->ce_flags &= ~skip_wt_flag;
 	}
+
+	/*
+	 * 2. Widen worktree according to sparse-checkout file.
+	 * Matched entries will have skip_wt_flag cleared (i.e. "in")
+	 */
+	clear_ce_flags(the_index->cache, the_index->cache_nr,
+		       select_flag, skip_wt_flag, el);
 }
 
 static int verify_absent(struct cache_entry *, enum unpack_trees_error_types, struct unpack_trees_options *);
-- 
1.7.3.2.316.gda8b3

[PATCH 5/5] Revert "excluded_1(): support exclude files in index"

[Nguyễn Thái Ngọc Duy]

This reverts commit c84de70781674a35b9bfd20aa5bc8c47582615df.
The commit provided a workaround for matching directories in
index. But it is no longer needed.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 dir.c |    7 -------
 1 files changed, 0 insertions(+), 7 deletions(-)

diff --git a/dir.c b/dir.c
index 39eb7a3..d059aa1 100644
--- a/dir.c
+++ b/dir.c
@@ -371,13 +371,6 @@ int excluded_from_list(const char *pathname,
 			int to_exclude = x->to_exclude;
 
 			if (x->flags & EXC_FLAG_MUSTBEDIR) {
-				if (!dtype) {
-					if (!prefixcmp(pathname, exclude) &&
-					    pathname[x->patternlen] == '/')
-						return to_exclude;
-					else
-						continue;
-				}
 				if (*dtype == DT_UNKNOWN)
 					*dtype = get_dtype(NULL, pathname, pathlen);
 				if (*dtype != DT_DIR)
-- 
1.7.3.2.316.gda8b3