[PATCH WIP 0/3] git log --exclude

[PATCH WIP 0/3] git log --exclude

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

This series adds --exclude that uses .gitignore mechanism remove
commits whose changes that are _entirely_ excluded. The main patch is
2/3 where it teaches diff_tree_* about struct exclude_list.

Because it uses .gitignore mechanism, beware that these patterns do
not behave exactly like pathspecs (patterns without slashes match
every directory, for example)

I tried these commands

  time git log --stat >/dev/null
  time git log --stat --exclude=Documentation >/dev/null

The former took 37 secs, the latter 40 secs. Not bad, but there is
definitely room for improvement. skip_excludes() should be able to
point out whether an entire directory is excluded and skip the whole
directory (as opposed to descending in and checking files one by one
now, in fear of negative patterns). These kinds of optimizations
benefit sparse checkout too.

I think I made a mistake somewhere because the above command seems to
remove more commits than it should... Regardless,
"git log --exclude=po" on gnome-shell looks sooo clean.

Nguyễn Thái Ngọc Duy (3):
  diff-no-index: rename read_directory to avoid conflict from dir.h
  tree-diff: teach it to understand exclude patterns
  log: add --exclude option

 diff-no-index.c |    6 ++--
 diff.h          |   11 ++++++++++
 revision.c      |    7 ++++-
 revision.h      |    2 +
 tree-diff.c     |   58 +++++++++++++++++++++++++++++++++++++++++++++++++++---
 5 files changed, 75 insertions(+), 9 deletions(-)

-- 
1.7.3.1.256.g2539c.dirty

[PATCH WIP 1/3] diff-no-index: rename read_directory to avoid conflict from dir.h

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

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

diff --git a/diff-no-index.c b/diff-no-index.c
index 3a36144..927abb7 100644
--- a/diff-no-index.c
+++ b/diff-no-index.c
@@ -16,7 +16,7 @@
 #include "builtin.h"
 #include "string-list.h"
 
-static int read_directory(const char *path, struct string_list *list)
+static int read_entire_directory(const char *path, struct string_list *list)
 {
 	DIR *dir;
 	struct dirent *e;
@@ -68,9 +68,9 @@ static int queue_diff(struct diff_options *o,
 		struct string_list p2 = STRING_LIST_INIT_DUP;
 		int len1 = 0, len2 = 0, i1, i2, ret = 0;
 
-		if (name1 && read_directory(name1, &p1))
+		if (name1 && read_entire_directory(name1, &p1))
 			return -1;
-		if (name2 && read_directory(name2, &p2)) {
+		if (name2 && read_entire_directory(name2, &p2)) {
 			string_list_clear(&p1, 0);
 			return -1;
 		}
-- 
1.7.3.1.256.g2539c.dirty

[PATCH WIP 2/3] tree-diff: teach it to understand exclude patterns

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

We introduce a new set of API, diff_tree_*_with_exclude, that also
exclude entries based on .gitignore patterns.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 diff.h      |   11 +++++++++++
 tree-diff.c |   58 ++++++++++++++++++++++++++++++++++++++++++++++++++++++----
 2 files changed, 65 insertions(+), 4 deletions(-)

diff --git a/diff.h b/diff.h
index 8c66b59..51c8a5f 100644
--- a/diff.h
+++ b/diff.h
@@ -12,6 +12,7 @@ struct diff_queue_struct;
 struct strbuf;
 struct diff_filespec;
 struct userdiff_driver;
+struct exclude_list;
 
 typedef void (*change_fn_t)(struct diff_options *options,
 		 unsigned old_mode, unsigned new_mode,
@@ -170,8 +171,18 @@ extern void diff_tree_setup_paths(const char **paths, struct diff_options *);
 extern void diff_tree_release_paths(struct diff_options *);
 extern int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
 		     const char *base, struct diff_options *opt);
+extern int diff_tree_with_exclude(struct tree_desc *t1, struct tree_desc *t2,
+				  const char *base, struct diff_options *opt,
+				  struct exclude_list *el,
+				  int def_excl1, int def_excl2);
 extern int diff_tree_sha1(const unsigned char *old, const unsigned char *new,
 			  const char *base, struct diff_options *opt);
+extern int diff_tree_sha1_with_exclude(const unsigned char *old,
+				       const unsigned char *new,
+				       const char *base,
+				       struct diff_options *opt,
+				       struct exclude_list *el,
+				       int def_excl1, int def_excl2);
 extern int diff_root_tree_sha1(const unsigned char *new, const char *base,
                                struct diff_options *opt);
 
diff --git a/tree-diff.c b/tree-diff.c
index b3cc2e4..9938ccf 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -5,12 +5,14 @@
 #include "diff.h"
 #include "diffcore.h"
 #include "tree.h"
+#include "dir.h"
 
 static void show_entry(struct diff_options *opt, const char *prefix,
 		       struct tree_desc *desc, struct strbuf *base);
 
 static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2,
-			      struct strbuf *base, struct diff_options *opt)
+			      struct strbuf *base, struct diff_options *opt,
+			      struct exclude_list *el, int def_excl1, int def_excl2)
 {
 	unsigned mode1, mode2;
 	const char *path1, *path2;
@@ -52,7 +54,8 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2,
 				    sha1, sha2, base->buf, 0, 0);
 		}
 		strbuf_addch(base, '/');
-		diff_tree_sha1(sha1, sha2, base->buf, opt);
+		diff_tree_sha1_with_exclude(sha1, sha2, base->buf, opt,
+					    el, def_excl1, def_excl2);
 	} else {
 		opt->change(opt, mode1, mode2, sha1, sha2, base->buf, 0, 0);
 	}
@@ -113,6 +116,31 @@ static void show_entry(struct diff_options *opt, const char *prefix,
 	strbuf_setlen(base, old_baselen);
 }
 
+static int skip_excludes(struct tree_desc *t, struct strbuf *base,
+			 struct exclude_list *el, int defval)
+{
+	for (; t->size; update_tree_entry(t)) {
+		/*
+		 * excluded_from_list only cares whether dtype is
+		 * DT_DIR or something else (except DT_UNKNOWN). Any
+		 * other value would do
+		 */
+		int dtype = S_ISDIR(t->entry.mode) ? DT_DIR : DT_REG;
+		int ret = excluded_from_list(base->buf, base->len, t->entry.path,
+					     &dtype, el);
+
+		/* If undecided, use matching result of parent dir in defval */
+		if (ret < 0)
+			ret = defval;
+
+		if (ret == 1 && dtype == DT_REG)
+			;
+		else
+			return ret;
+	}
+	return defval;
+}
+
 static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,
 			       struct diff_options *opt, int *match)
 {
@@ -130,9 +158,17 @@ static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,
 int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
 	      const char *base_str, struct diff_options *opt)
 {
+	return diff_tree_with_exclude(t1, t2, base_str, opt, NULL, 0, 0);
+}
+
+int diff_tree_with_exclude(struct tree_desc *t1, struct tree_desc *t2,
+			   const char *base_str, struct diff_options *opt,
+			   struct exclude_list *el, int def_excl1, int def_excl2)
+{
 	struct strbuf base;
 	int baselen = strlen(base_str);
 	int t1_match = 0, t2_match = 0;
+	int excl1 = 0, excl2 = 0;
 
 	/* Enable recursion indefinitely */
 	opt->pathspec.recursive = DIFF_OPT_TST(opt, RECURSIVE);
@@ -148,6 +184,10 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
 			skip_uninteresting(t1, &base, opt, &t1_match);
 			skip_uninteresting(t2, &base, opt, &t2_match);
 		}
+		if (el && el->nr) {
+			excl1 = skip_excludes(t1, &base, el, def_excl1);
+			excl2 = skip_excludes(t2, &base, el, def_excl2);
+		}
 		if (!t1->size) {
 			if (!t2->size)
 				break;
@@ -160,7 +200,7 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
 			update_tree_entry(t1);
 			continue;
 		}
-		switch (compare_tree_entry(t1, t2, &base, opt)) {
+		switch (compare_tree_entry(t1, t2, &base, opt, el, excl1, excl2)) {
 		case -1:
 			update_tree_entry(t1);
 			continue;
@@ -267,6 +307,16 @@ static void try_to_follow_renames(struct tree_desc *t1, struct tree_desc *t2, co
 
 int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base, struct diff_options *opt)
 {
+	return diff_tree_sha1_with_exclude(old, new, base, opt, NULL, 0, 0);
+}
+
+int diff_tree_sha1_with_exclude(const unsigned char *old,
+				const unsigned char *new,
+				const char *base,
+				struct diff_options *opt,
+				struct exclude_list *el,
+				int def_excl1, int def_excl2)
+{
 	void *tree1, *tree2;
 	struct tree_desc t1, t2;
 	unsigned long size1, size2;
@@ -280,7 +330,7 @@ int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const cha
 		die("unable to read destination tree (%s)", sha1_to_hex(new));
 	init_tree_desc(&t1, tree1, size1);
 	init_tree_desc(&t2, tree2, size2);
-	retval = diff_tree(&t1, &t2, base, opt);
+	retval = diff_tree_with_exclude(&t1, &t2, base, opt, el, def_excl1, def_excl2);
 	if (!*base && DIFF_OPT_TST(opt, FOLLOW_RENAMES) && diff_might_be_rename()) {
 		init_tree_desc(&t1, tree1, size1);
 		init_tree_desc(&t2, tree2, size2);
-- 
1.7.3.1.256.g2539c.dirty

[PATCH WIP 3/3] log: add --exclude option

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

This only helps filtering out commits whose changes are _entirely_ filtered out.
This does not affect patch generate (--patch, --stat and so on)

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

diff --git a/revision.c b/revision.c
index c46cfaa..8472553 100644
--- a/revision.c
+++ b/revision.c
@@ -334,8 +334,8 @@ static int rev_compare_tree(struct rev_info *revs, struct commit *parent, struct
 
 	tree_difference = REV_TREE_SAME;
 	DIFF_OPT_CLR(&revs->pruning, HAS_CHANGES);
-	if (diff_tree_sha1(t1->object.sha1, t2->object.sha1, "",
-			   &revs->pruning) < 0)
+	if (diff_tree_sha1_with_exclude(t1->object.sha1, t2->object.sha1, "",
+					&revs->pruning, &revs->el, 0, 0) < 0)
 		return REV_TREE_DIFFERENT;
 	return tree_difference;
 }
@@ -1454,6 +1454,9 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg
 		return argcount;
 	} else if (!strcmp(arg, "--log-size")) {
 		revs->show_log_size = 1;
+	} else if (!prefixcmp(arg, "--exclude=")) {
+		add_exclude(arg + 10, "", 0, &revs->el);
+		revs->prune = 1;
 	}
 	/*
 	 * Grepping the commit log
diff --git a/revision.h b/revision.h
index 3d64ada..3709959 100644
--- a/revision.h
+++ b/revision.h
@@ -4,6 +4,7 @@
 #include "parse-options.h"
 #include "grep.h"
 #include "notes.h"
+#include "dir.h"
 
 #define SEEN		(1u<<0)
 #define UNINTERESTING   (1u<<1)
@@ -133,6 +134,7 @@ struct rev_info {
 	/* diff info for patches and for paths limiting */
 	struct diff_options diffopt;
 	struct diff_options pruning;
+	struct exclude_list el;
 
 	struct reflog_walk_info *reflog_info;
 	struct decoration children;
-- 
1.7.3.1.256.g2539c.dirty

Re: [PATCH WIP 0/3] git log --exclude

[Matthieu Moy]

Nguyễn Thái Ngọc Duy <pclouds@gmail.com> writes:

> This series adds --exclude that uses .gitignore mechanism remove
> commits whose changes that are _entirely_ excluded.

I'd see this --exclude as the opposite of specifying files, i.e. in a
repository containing directories A, B and C,

git log --exclude=B

would be the same as

git log A C

If I understand correctly, it's not the case with your implementation
because

> Because it uses .gitignore mechanism, beware that these patterns do
> not behave exactly like pathspecs

and because "git log --stat A C" (or --patch) will show the diff only
for A and C for commits touching all directories.

-- 
Matthieu Moy
http://www-verimag.imag.fr/~moy/

Re: [PATCH WIP 0/3] git log --exclude

[Nguyen Thai Ngoc Duy]

2011/10/5 Matthieu Moy <Matthieu.Moy@grenoble-inp.fr>:
> Nguyễn Thái Ngọc Duy <pclouds@gmail.com> writes:
>
>> This series adds --exclude that uses .gitignore mechanism remove
>> commits whose changes that are _entirely_ excluded.
>
> I'd see this --exclude as the opposite of specifying files, i.e. in a
> repository containing directories A, B and C,
>
> git log --exclude=B
>
> would be the same as
>
> git log A C

I think I emphasized it too much. "git log --exclude=B/ A B C" should
be equivalent to "git log A C". If changes touch A or C, then no
matter they touch B, the commit will always be in. If changes only
touch B, neither A nor B, then the commit is removed, exactly the same
case with "git log A C".

>> Because it uses .gitignore mechanism, beware that these patterns do
>> not behave exactly like pathspecs

if you specify --exclude=B, then A/.../B, C/.../B are all removed. A
subtle difference between pathspec and .gitignore.

> and because "git log --stat A C" (or --patch) will show the diff only
> for A and C for commits touching all directories.

I'll take care of --patch and friends later. They both (--patch and
commit pruning) use the same diff mechanism, if we get it right for
for commit pruning, --patch will come nicely.
-- 
Duy

Re: [PATCH WIP 0/3] git log --exclude

[Junio C Hamano]

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

> This series adds --exclude that uses .gitignore mechanism remove
> commits whose changes that are _entirely_ excluded.

I really do not want to see the exclude patterns nor mechanism used for
this. This will unnecessarily impact the long term design of narrow clones
I had in mind.

The way I envisioned the narrow cloning would work like this [*1*]:

 * The narrowed set of paths is an attribute of the local repository. It
   is not tied to the history nor the current working tree state, so the
   information does not live in the index or in the history. A new file
   $GIT_DIR/narrowed-paths specifies a list of pathspecs. We call a
   repository with such a file "a narrowed repository".

 * The objects that live in a narrowed repository are subset of the
   objects in an unnarrowed repository that records the same
   history. Objects are not modified in any way when transferring into
   a narrowed repository. E.g. if you clone git.git but limit the tree to
   Documentation/ and builtin/, you will get _all_ commit objects, even
   the ones that do _not_ touch these two directories, and the top level
   tree objects. These top level tree objects _do_ record the object names
   for paths outside the narrowed area. To facilitate local history
   traversal, we may add either grafts or replace entries to "gather" away
   commits that do not touch the narrowed area, but this is not essential.

 * "struct pathspec" gains a handful of new fields to carry the set of
   narrowing pathspecs taken from $GIT_DIR/narrowed-paths file down the
   callchain. When we decide to see if a given path matches the pathspec
   and/or is worth descending into, we use these pathspecs to reject
   anything that is outside of the narrowed area before applying user
   supplied pathspec. We use narrowing pathspecs even for the whole tree
   operation.

 * "fsck", "prune" and friends that do not use user-supplied pathspec will
   learn the narrowed-paths so that the tree entries that describe objects
   outside the narrowed area (e.g. "Makefile" in the top-level tree in a
   repository narrowed to "Documentation/" and "builtin/") are ignored.

   I looked at fsck and unpack-objects (surprise, but it does seem to need
   some work) a few months ago for this exact purpose, and it appeared
   doable.

We may want to be able to say something like "I want Documentation/ but
not Documentaion/howto/", and for that to work, narrowed-paths needs to be
able to express negative matches. And in _that_ context, we will need
negative pathspec matches (and I think during the last round of pathspec
updates we identified where the support for ":(no):pathspec" needs to be
added in the codepath). 

You could say "Use pathspec for inclusion and ignore patterns for
exclusion", but I do not think that inconsistency has merits.

For the purpose of "log --exclude" [*2*], I do not mind too much if the UI
expressed negative pathspecs using such a new command line option, but I
think it would be more natural to say (notations aside):

	$ git log -- ':(no):po' .

and define the behaviour of user-supplied pathspec limiter this way:

 * Paths are matched from left to right;

 * First match determines the fate of the path;

 * A match with negative pathspec means "the path in question does _not_
   match".


[Footnote]

*1* Unlike the "This is _one_ possible way" I usually give in discussions,
this is "The narrow clone _must_ work like this, if we were to add it".

*2* I would suggest not using --exclude to avoid giving users a wrong
impression that this might have something to do with exclude patterns. How
about calling it "--filter-out" instead?

Re: [PATCH WIP 0/3] git log --exclude

[Jeff King]

On Wed, Oct 05, 2011 at 10:20:30AM -0700, Junio C Hamano wrote:

> The way I envisioned the narrow cloning would work like this [*1*]:
> 
>  * The narrowed set of paths is an attribute of the local repository. It
>    is not tied to the history nor the current working tree state, so the
>    information does not live in the index or in the history. A new file
>    $GIT_DIR/narrowed-paths specifies a list of pathspecs. We call a
>    repository with such a file "a narrowed repository".
> 
>  * The objects that live in a narrowed repository are subset of the
>    objects in an unnarrowed repository that records the same
>    history. Objects are not modified in any way when transferring into
>    a narrowed repository. E.g. if you clone git.git but limit the tree to
>    Documentation/ and builtin/, you will get _all_ commit objects, even
>    the ones that do _not_ touch these two directories, and the top level
>    tree objects. These top level tree objects _do_ record the object names
>    for paths outside the narrowed area. To facilitate local history
>    traversal, we may add either grafts or replace entries to "gather" away
>    commits that do not touch the narrowed area, but this is not essential.

I'm really just a bystander on this topic, and haven't given it too much
thought. But one stumbling block I see for narrow clone is how narrow
repositories will interact with object transfer from other repositories.

For example, if I have a narrow git.git that omits Documentation, and I
do a "git fetch" from a non-narrow repository, then how do we tell the
non-narrow remote that we don't have blobs in Documentation, and that
they should not be used as delta bases for any objects that are sent?

The current protocol relies on certain repository properties on the
remote end that narrow clone will violate. I don't see a way around that
without a protocol extension to communicate the narrowness. What will
that extension look like?

-Peff

Re: [PATCH WIP 0/3] git log --exclude

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> The current protocol relies on certain repository properties on the
> remote end that narrow clone will violate. I don't see a way around that
> without a protocol extension to communicate the narrowness. What will
> that extension look like?

It would have to involve exchanging "I have/am interested in the paths
that match these pathspecs". I do not mind if our initial implementation
did not support anything other than fetching into a narrow from full and
pushing from a narrow to full. The second iteration could add fetching and
pushing between two narrows with the same set of narrowing pathspecs.

As to widening the area after a clone is made, I do not mind and if our
initial impementation only supported widening the area in a stupid way
(e.g. semi-equivalent of initial clone with the widened set of narrowing
pathspecs).

Re: [PATCH WIP 0/3] git log --exclude

[Nguyen Thai Ngoc Duy]

2011/10/7 Jeff King <peff@peff.net>:
> I'm really just a bystander on this topic, and haven't given it too much
> thought. But one stumbling block I see for narrow clone is how narrow
> repositories will interact with object transfer from other repositories.
>
> For example, if I have a narrow git.git that omits Documentation, and I
> do a "git fetch" from a non-narrow repository, then how do we tell the
> non-narrow remote that we don't have blobs in Documentation, and that
> they should not be used as delta bases for any objects that are sent?

Pretty much how shallow cloned repos interacts. In shallow clone we
send depth info. In narrow clone, we send width info, in terms of
(restricted) pathspec. With pathspec (possibly plus exclude rules but
this possibility is getting smaller), I can express "fetch this
directory only", or "fetch this directory, but not this subdirectory
(because I already have it)".

We can prohibit certain use cases at client side just like shallow clone.

> The current protocol relies on certain repository properties on the
> remote end that narrow clone will violate. I don't see a way around that
> without a protocol extension to communicate the narrowness. What will
> that extension look like?

Something like this

http://thread.gmane.org/gmane.comp.version-control.git/155427/focus=155613
-- 
Duy

Re: [PATCH WIP 0/3] git log --exclude

[Nguyen Thai Ngoc Duy]

2011/10/6 Junio C Hamano <gitster@pobox.com>:
> For the purpose of "log --exclude" [*2*], I do not mind too much if the UI
> expressed negative pathspecs using such a new command line option, but I
> think it would be more natural to say (notations aside):
>
>        $ git log -- ':(no):po' .
>
> and define the behaviour of user-supplied pathspec limiter this way:
>
>  * Paths are matched from left to right;
>
>  * First match determines the fate of the path;
>
>  * A match with negative pathspec means "the path in question does _not_
>   match".

Things have changed a bit since last time I touched negative pathspec.
Because of depth limit support [1], pathspecs have to be sorted, which
means we cannot keep pathspec in original order to match from left to
right.

There may be a solution to mix depth limit and negative pathspec. I
haven't thought carefully about that because I lean towards a simpler
behaviour that only allows one negation level: a file is in if it
matches any positive pathspecs and none of negative ones.

This is enough if narrow clones consist of positive pathspec only. I
really doubt if users would want to make a narrow clone that "contains
A but not A/B, storage-wise".

[1] 86e4ca6 (tree_entry_interesting(): fix depth limit with
overlapping pathspecs)
-- 
Duy

Re: [PATCH WIP 0/3] git log --exclude

[Junio C Hamano]

Nguyen Thai Ngoc Duy <pclouds@gmail.com> writes:

> There may be a solution to mix depth limit and negative pathspec. I
> haven't thought carefully about that because I lean towards a simpler
> behaviour that only allows one negation level: a file is in if it
> matches any positive pathspecs and none of negative ones.

I tend to think it probably is acceptable solution to define "struct
pathspec" to have one positive and one negative set, traversing and
declaring a match on what matches something from the positive set only if
it does not match anything in the negative set.

That is similar to how we define revision ranges in the sense that the
range notation to have two ranges (A..B C..D) does not mean union of two
sets (A..B + C..D), but is difference between two unions ((B D)-(A C)).

> This is enough if narrow clones consist of positive pathspec only. I
> really doubt if users would want to make a narrow clone that "contains
> A but not A/B, storage-wise".

And if you define "struct pathspec" to have one positive and one negative
set, you do not have to limit narrow clone only to positive. The repository
specific narrow pathspec will have one such "struct pathspec", but the
user may give us from the command line another "struct pathspec". At
runtime, we would merge them to form into one negative and one positive
set, and apply the same rule: nothing that matches any negative will
appear in the traversal or in the output.