en/object-list-with-pathspec (v3?)
cover en/object-list-with-pathspec (v3?)
Changes from last time is tree_entry_interesting() now takes struct exclude * as the pathspecs.
I think there'll be a bit of performance loss because diff_options.el is not initialized from the beginning. But that requires more changes outside tree-diff.c (makes sure that diff_options.el is copied properly, makes sure that diff_tree_setup_* is called ...) So one step at a time. I'm working on it.
Elijah Newren (2):
Add testcases showing how pathspecs are ignored with rev-list
--objects
Make rev-list --objects work together with pathspecs
Nguyễn Thái Ngọc Duy (3):
diff-no-index.c: rename read_directory() to read_dir()
tree-walk: move tree_entry_interesting() from tree-diff.c tree_entry_interesting(): remove dependency on struct diff_options
diff-no-index.c | 6 +- diff.h | 3 + list-objects.c | 25 ++++++++ revision.c | 8 ++- revision.h | 3 +- t/t6000-rev-list-misc.sh | 51 ++++++++++++++++ tree-diff.c | 145 +++++++++------------------------------------- tree-walk.c | 111 +++++++++++++++++++++++++++++++++++ tree-walk.h | 4 + 9 files changed, 233 insertions(+), 123 deletions(-) create mode 100755 t/t6000-rev-list-misc.sh
PATCH 1/5 diff-no-index.c: rename read_directory() to read_dir()
This name clashes with one in dir.h, to be included later on.
--- diff-no-index.c | 6 +++--- 1 files changed, 3 insertions(+), 3 deletions(-)
diff-no-index.c +3 -3
@@ -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_dir (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_dir (name1, &p1))return -1 ; -if (name2 &&read_directory (name2, &p2)) { +if (name2 &&read_dir (name2, &p2)) {string_list_clear (&p1,0 );return -1 ; }
Signature · 1 line
1.7.1.rc1.69.g24c2f7
PATCH 2/5 Add testcases showing how pathspecs are ignored with rev-list --objects
In reply to Nguyễn Thái Ngọc DuyFrom: Elijah Newren <[email protected]>
--- t/t6000-rev-list-misc.sh | 51 ++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 51 insertions(+), 0 deletions(-) create mode 100755 t/t6000-rev-list-misc.sh
t/t6000-rev-list-misc.sh new file +51 -0
@@ -0,0 +1,51 @@ +#!/bin/sh + +test_description='miscellaneous rev-list tests' + +. ./test-lib.sh + +test_expect_success setup ' + echo content1 >wanted_file && + echo content2 >unwanted_file && + git add wanted_file unwanted_file && + git commit -m one +' + +test_expect_failure 'rev-list --objects heeds pathspecs' ' + git rev-list --objects HEAD -- wanted_file >output && + grep wanted_file output && + ! grep unwanted_file output +' + +test_expect_failure 'rev-list --objects with pathspecs and deeper paths' ' + mkdir foo && + >foo/file && + git add foo/file && + git commit -m two && + + git rev-list --objects HEAD -- foo >output && + grep foo/file output && + + git rev-list --objects HEAD -- foo/file >output && + grep foo/file output && + ! grep unwanted_file output +' + +test_expect_failure 'rev-list --objects with pathspecs and copied files' ' + git checkout --orphan junio-testcase && + git rm -rf . && + + mkdir two && + echo frotz >one && + cp one two/three && + git add one two/three && + test_tick && + git commit -m that && + + ONE=$(git rev-parse HEAD:one) + git rev-list --objects HEAD two >output && + grep "$ONE two/three" output && + ! grep one output +' + +test_done
Signature · 1 line
1.7.1.rc1.69.g24c2f7
PATCH 3/5 tree-walk: move tree_entry_interesting() from tree-diff.c
In reply to Nguyễn Thái Ngọc Duy--- tree-diff.c | 114 ---------------------------------------------------------- tree-walk.c | 115 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ tree-walk.h | 3 ++ 3 files changed, 118 insertions(+), 114 deletions(-)
tree-diff.c +0 -114
@@ -82,120 +82,6 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, constreturn 0 ; } -/* -* Is a tree entry interesting given the pathspec we have? -* -* Return: -* - 2 for "yes, and all subsequent entries will be" -* - 1 for yes -* - zero for no -* - negative for "no, and no subsequent entries will be either" -*/ -static int tree_entry_interesting (struct tree_desc *desc,const char *base,int baselen,struct diff_options *opt) -{ -const char *path; -const unsigned char *sha1; -unsigned mode; -int i; -int pathlen; -int never_interesting =-1 ; - -if (!opt->nr_paths) -return 1 ; - - sha1 =tree_entry_extract (desc, &path, &mode); - - pathlen =tree_entry_len (path, sha1); - -for (i =0 ; i < opt->nr_paths; i++) { -const char *match = opt->paths[i]; -int matchlen = opt->pathlens[i]; -int m =-1 ;/* signals that we haven't called strncmp() */ - -if (baselen >= matchlen) { -/* If it doesn't match, move along... */ -if (strncmp (base, match, matchlen)) -continue ; - -/* -* If the base is a subdirectory of a path which -* was specified, all of them are interesting. -*/ -if (!matchlen || - base[matchlen] =='/' || - match[matchlen -1 ] =='/' ) -return 2 ; - -/* Just a random prefix match */ -continue ; - } - -/* Does the base match? */ -if (strncmp (base, match, baselen)) -continue ; - - match += baselen; - matchlen -= baselen; - -if (never_interesting) { -/* -* We have not seen any match that sorts later -* than the current path. -*/ - -/* -* Does match sort strictly earlier than path -* with their common parts? -*/ - m =strncmp (match, path, - (matchlen < pathlen) ? matchlen : pathlen); -if (m <0 ) -continue ; - -/* -* If we come here even once, that means there is at -* least one pathspec that would sort equal to or -* later than the path we are currently looking at. -* In other words, if we have never reached this point -* after iterating all pathspecs, it means all -* pathspecs are either outside of base, or inside the -* base but sorts strictly earlier than the current -* one. In either case, they will never match the -* subsequent entries. In such a case, we initialized -* the variable to -1 and that is what will be -* returned, allowing the caller to terminate early. -*/ - never_interesting =0 ; - } - -if (pathlen > matchlen) -continue ; - -if (matchlen > pathlen) { -if (match[pathlen] !='/' ) -continue ; -if (!S_ISDIR (mode)) -continue ; - } - -if (m ==-1 ) -/* -* we cheated and did not do strncmp(), so we do -* that here. -*/ - m =strncmp (match, path, pathlen); - -/* -* If common part matched earlier then it is a hit, -* because we rejected the case where path is not a -* leading directory and is shorter than match. -*/ -if (!m) -return 1 ; - } -return never_interesting;/* No matches */ -} -/* A whole sub-tree went away or appeared */ static void show_tree (struct diff_options *opt,const char *prefix,struct tree_desc *desc,const char *base,int baselen) {
tree-walk.c +115 -0
124 lines not on this page · raw message
tree-walk.h +3 -0
@@ -57,4 +57,7 @@ static inline int traverse_path_len(const struct traverse_info *info, const stru return info->pathlen + tree_entry_len(n->path, n->sha1); } +struct diff_options ; +extern int tree_entry_interesting (struct tree_desc *desc,const char *base,int baselen,struct diff_options *opt); +#endif
Signature · 1 line
1.7.1.rc1.69.g24c2f7
PATCH 4/5 tree_entry_interesting(): remove dependency on struct diff_options
In reply to Nguyễn Thái Ngọc DuyThis function can be potentially used in more places than just tree-diff.c. "struct diff_options" does not make much sense outside diff_tree_sha1().
Moreover people seem to be agree that diff machinery should learn proper pathspecs too (i.e. glob support [1] and stuff), not just treating pathspecs as tree prefix.
So instead of using pathspecs in diff_options.{nr_paths,paths,pathlens}, tree_entry_interesting() now uses struct exclude_list.
Struct exclude_list is also added to diff_options with the intention to replace {nr_paths,paths,pathlens} later on. But for now, it's just a temporary field.
--- diff.h | 3 +++ tree-diff.c | 31 ++++++++++++++++++++++++++++--- tree-walk.c | 26 +++++++++++--------------- tree-walk.h | 5 +++-- 4 files changed, 45 insertions(+), 20 deletions(-)
diff.h +3 -0
@@ -5,6 +5,7 @@#define DIFF_H #include "tree-walk.h" +#include "dir.h" struct rev_info ;struct diff_options ;
@@ -136,6 +137,7 @@ struct diff_options {int nr_paths;const char **paths;int *pathlens; +struct exclude_list el;change_fn_t change;add_remove_fn_t add_remove;diff_format_fn_t format_callback;
@@ -163,6 +165,7 @@ const char *diff_get_color(int diff_use_color, enum color_diff ix);extern const char mime_boundary_leader[];extern void diff_tree_setup_paths (const char **paths,struct diff_options *); +extern void diff_tree_setup_exclude_list (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);
tree-diff.c +28 -3
@@ -92,8 +92,7 @@ static void show_tree(struct diff_options *opt, const char *prefix, struct tree_if (all_interesting) show =1 ;else { - show =tree_entry_interesting (desc, base, baselen, - opt); + show =tree_entry_interesting (&desc->entry, base, baselen, &opt->el);if (show ==2 ) all_interesting =1 ; }
@@ -152,7 +151,7 @@ static void skip_uninteresting(struct tree_desc *t, const char *base, int baseleif (all_interesting) show =1 ;else { - show =tree_entry_interesting (t, base, baselen, opt); + show =tree_entry_interesting (&t->entry, base, baselen, &opt->el);if (show ==2 ) all_interesting =1 ; }
@@ -167,10 +166,34 @@ static void skip_uninteresting(struct tree_desc *t, const char *base, int basele } } +void diff_tree_setup_exclude_list (struct diff_options *opt) +{ +int i, size1, size2; + +memset (&opt->el,0 ,sizeof (opt->el)); + opt->el.nr = opt->nr_paths; +if (!opt->el.nr) +return ; + + size1 = opt->el.nr *sizeof (struct exclude *); + size2 = opt->el.nr *sizeof (struct exclude ); + opt->el.excludes =xmalloc (size1+size2); +memset (opt->el.excludes,0 , size1+size2); +for (i=0 ; i < opt->el.nr; i++) { +struct exclude *exc = ((struct exclude *)((char *)opt->el.excludes+size1))+i; + exc->base = opt->paths[i]; + exc->baselen = opt->pathlens[i]; + opt->el.excludes[i] = exc; + } +} +int diff_tree (struct tree_desc *t1,struct tree_desc *t2,const char *base,struct diff_options *opt) {int baselen =strlen (base); +struct exclude_list el; + el = opt->el;/* diff_tree() can be nested, save and restore opt->el later */ +diff_tree_setup_exclude_list (opt);for (;;) {if (DIFF_OPT_TST (opt,QUICK ) &&DIFF_OPT_TST (opt,HAS_CHANGES ))
@@ -204,6 +227,8 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2, const char *base, stru }die ("git diff-tree: internal error" ); } +free (opt->el.excludes); + opt->el = el;return 0 ; }
tree-walk.c +11 -15
@@ -2,7 +2,7 @@#include "tree-walk.h" #include "unpack-trees.h" #include "tree.h" -#include "diff.h" +#include "dir.h" static const char *get_mode (const char *str,unsigned int *modep) {
@@ -466,25 +466,21 @@ int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned ch* - zero for no * - negative for "no, and no subsequent entries will be either" */ -static int tree_entry_interesting (struct tree_desc *desc,const char *base,int baselen,struct diff_options *opt) +int tree_entry_interesting (const struct name_entry *entry,const char *base,int baselen, +const struct exclude_list *el) { -const char *path; -const unsigned char *sha1; -unsigned mode;int i;int pathlen;int never_interesting =-1 ; -if (!opt->nr_paths) +if (!el->nr)return 1 ; - sha1 =tree_entry_extract (desc, &path, &mode); - - pathlen =tree_entry_len (path, sha1); + pathlen =tree_entry_len (entry->path, entry->sha1); -for (i =0 ; i < opt->nr_paths; i++) { -const char *match = opt->paths[i]; -int matchlen = opt->pathlens[i]; +for (i =0 ; i < el->nr; i++) { +const char *match = el->excludes[i]->base; +int matchlen = el->excludes[i]->baselen;int m =-1 ;/* signals that we haven't called strncmp() */ if (baselen >= matchlen) {
@@ -522,7 +518,7 @@ static int tree_entry_interesting(struct tree_desc *desc, const char *base, int* Does match sort strictly earlier than path * with their common parts? */ - m =strncmp (match, path, + m =strncmp (match, entry->path, (matchlen < pathlen) ? matchlen : pathlen);if (m <0 )continue ;
@@ -549,7 +545,7 @@ static int tree_entry_interesting(struct tree_desc *desc, const char *base, intif (matchlen > pathlen) {if (match[pathlen] !='/' )continue ; -if (!S_ISDIR (mode)) +if (!S_ISDIR (entry->mode))continue ; }
@@ -558,7 +554,7 @@ static int tree_entry_interesting(struct tree_desc *desc, const char *base, int* we cheated and did not do strncmp(), so we do * that here. */ - m =strncmp (match, path, pathlen); + m =strncmp (match, entry->path, pathlen);/* * If common part matched earlier then it is a hit,
tree-walk.h +3 -2
@@ -57,7 +57,8 @@ static inline int traverse_path_len(const struct traverse_info *info, const stru return info->pathlen + tree_entry_len(n->path, n->sha1); } -struct diff_options ; -extern int tree_entry_interesting (struct tree_desc *desc,const char *base,int baselen,struct diff_options *opt); +struct exclude_list ; +extern int tree_entry_interesting (const struct name_entry *entry,const char *base,int baselen, +const struct exclude_list *el);#endif
Signature · 1 line
1.7.1.rc1.69.g24c2f7
PATCH 5/5 Make rev-list --objects work together with pathspecs
In reply to Nguyễn Thái Ngọc DuyFrom: Elijah Newren <[email protected]>
When traversing commits, the selection of commits would heed the list of pathspecs passed, but subsequent walking of the trees of those commits would not. This resulted in 'rev-list --objects HEAD -- <paths>' displaying objects at unwanted paths.
Have process_tree() call tree_entry_interesting() to determine which paths are interesting and should be walked.
Naturally, this change can provide a large speedup when paths are specified together with --objects, since many tree entries are now correctly ignored. Interestingly, though, this change also gives me a small (~1%) but repeatable speedup even when no paths are specified with --objects.
--- list-objects.c | 25 +++++++++++++++++++++++++ revision.c | 8 ++++++-- revision.h | 3 ++- t/t6000-rev-list-misc.sh | 6 +++--- 4 files changed, 36 insertions(+), 6 deletions(-)
list-objects.c +25 -0
@@ -67,6 +67,9 @@ static void process_tree(struct rev_info *revs,struct tree_desc desc;struct name_entry entry;struct name_path me; +int all_interesting = (revs->diffopt.nr_paths ==0 ); +char *full_prefix =NULL ; +int full_prefix_len =0 ;if (!revs->tree_objects)return ;
@@ -82,9 +85,28 @@ static void process_tree(struct rev_info *revs, me.elem = name; me.elem_len =strlen (name); +if (!all_interesting) { + full_prefix =path_name_impl (path, name,1 ); + full_prefix_len =strlen (full_prefix); + } +init_tree_desc (&desc, tree->buffer, tree->size);while (tree_entry (&desc, &entry)) { +if (!all_interesting) { +int showit =tree_entry_interesting (&entry, + full_prefix, + full_prefix_len, + &revs->diffopt.el); + +if (showit <0 ) +break ; +else if (!showit) +continue ; +else if (showit ==2 ) + all_interesting =1 ; + } +if (S_ISDIR (entry.mode)) process_tree(revs, lookup_tree(entry.sha1),
@@ -97,6 +119,7 @@ static void process_tree(struct rev_info *revs,lookup_blob (entry.sha1), show, &me, entry.path); } +free (full_prefix);free (tree->buffer); tree->buffer =NULL ; }
@@ -147,6 +170,7 @@ void traverse_commit_list(struct rev_info *revs,int i;struct commit *commit; +diff_tree_setup_exclude_list (&revs->diffopt);while ((commit =get_revision (revs)) !=NULL ) {add_pending_tree (revs, commit->tree);show_commit (commit, data);
@@ -181,4 +205,5 @@ void traverse_commit_list(struct rev_info *revs, revs->pending.alloc =0 ; revs->pending.objects =NULL ; } +free (revs->diffopt.el.excludes); }
revision.c +6 -2
@@ -16,7 +16,7 @@volatile show_early_output_fn_t show_early_output; -char *path_name (const struct name_path *path,const char *name) +char *path_name_impl (const struct name_path *path,const char *name,int isdir) {const struct name_path *p;char *n, *m;
@@ -27,7 +27,7 @@ char *path_name(const struct name_path *path, const char *name)if (p->elem_len) len += p->elem_len +1 ; } - n =xmalloc (len); + n =xmalloc (len + !!isdir); m = n + len - (nlen +1 );strcpy (m, name);for (p = path; p; p = p->up) {
@@ -37,6 +37,10 @@ char *path_name(const struct name_path *path, const char *name) m[p->elem_len] ='/' ; } } +if (isdir && len >1 ) { + n[len-1 ] ='/' ; + n[len] ='\0' ; + }return n; }
revision.h +2 -1
@@ -173,7 +173,8 @@ struct name_path {const char *elem; }; -char *path_name (const struct name_path *path,const char *name); +char *path_name_impl (const struct name_path *path,const char *name,int isdir); +#define path_name (path, name) path_name_impl(path, name, 0) extern void add_object(struct object *obj, struct object_array *p,
t/t6000-rev-list-misc.sh +3 -3
@@ -11,13 +11,13 @@ test_expect_success setup ' git commit -m one ' -test_expect_failure 'rev-list --objects heeds pathspecs' ' +test_expect_success 'rev-list --objects heeds pathspecs' ' git rev-list --objects HEAD -- wanted_file >output && grep wanted_file output && ! grep unwanted_file output ' -test_expect_failure 'rev-list --objects with pathspecs and deeper paths' ' +test_expect_success 'rev-list --objects with pathspecs and deeper paths' ' mkdir foo && >foo/file && git add foo/file &&
@@ -31,7 +31,7 @@ test_expect_failure 'rev-list --objects with pathspecs and deeper paths' ' ! grep unwanted_file output ' -test_expect_failure 'rev-list --objects with pathspecs and copied files' ' +test_expect_success 'rev-list --objects with pathspecs and copied files' ' git checkout --orphan junio-testcase && git rm -rf . &&
Signature · 1 line
1.7.1.rc1.69.g24c2f7
2010/9/7 Nguyễn Thái Ngọc Duy <[email protected]>:
Quoted 8 lines
Changes from last time is
tree_entry_interesting()now takes struct exclude * as the pathspecs.I think there'll be a bit of performance loss because diff_options.el is not initialized from the beginning. But that requires more changes outside
tree-diff.c(makes sure that diff_options.el is copied properly, makes sure that diff_tree_setup_* is called ...) So one step at a time. I'm working on it.
Looks reasonable to me so far. I believe your series already makes nr_paths, paths, and pathlens fields from diff_options unused (other than via exclude_list) -- yes? If so, that suggests that we could just modify diff_tree_setup_paths() to do the work that your new diff_tree_setup_exclude_lists() is doing (and to take an exclude_list* instead of a diff_options*). Then you wouldn't need to worry about doing the setup "on-the-fly" and the performance differences should go away.
Am I understanding correctly, and is that the route you're going?
2010/9/8 Elijah Newren <[email protected]>:
Quoted 10 lines
2010/9/7 Nguyễn Thái Ngọc Duy <[email protected]>:
Quoted 8 lines
Changes from last time is
tree_entry_interesting()now takes struct exclude * as the pathspecs.I think there'll be a bit of performance loss because diff_options.el is not initialized from the beginning. But that requires more changes outside
tree-diff.c(makes sure that diff_options.el is copied properly, makes sure that diff_tree_setup_* is called ...) So one step at a time. I'm working on it.
Quoted 8 lines
Looks reasonable to me so far. I believe your series already makes
nr_paths, paths, and pathlens fields fromdiff_optionsunused (other than viaexclude_list) -- yes? If so, that suggests that we could just modifydiff_tree_setup_paths()to do the work that your newdiff_tree_setup_exclude_lists()is doing (and to take an exclude_list* instead of a diff_options*). Then you wouldn't need to worry about doing the setup "on-the-fly" and the performance differences should go away.
They are used elsewhere, passed around as prune data, even fed to read_cache_preload().. so they won't go away soon.
Quoted 1 line
Am I understanding correctly, and is that the route you're going?
Yes. Except that both nr_paths, paths and pathlens will stay along with exclude_list. Getting rid of "paths" takes time (the other two fields are easier to deal with).
Signature · 1 line
Duy