From 461cf59f8924f174d7a0dcc3d77f576d93ed29a4 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Wed, 18 Jan 2006 14:47:30 -0800 Subject: rev-list: stop when the file disappears The one thing I've considered doing (I really should) is to add a "stop when you don't find the file" option to "git-rev-list". This patch does some of the work towards that: it removes the "parent" thing when the file disappears, so a "git annotate" could do do something like git-rev-list --remove-empty --parents HEAD -- "$filename" and it would get a good graph that stops when the filename disappears (it's not perfect though: it won't remove all the unintersting commits). It also simplifies the logic of finding tree differences a bit, at the cost of making it a tad less efficient. The old logic was two-phase: it would first simplify _only_ merges tree as it traversed the tree, and then simplify the linear parts of the remainder independently. That was pretty optimal from an efficiency standpoint because it avoids doing any comparisons that we can see are unnecessary, but it made it much harder to understand than it really needed to be. The new logic is a lot more straightforward, and compares the trees as it traverses the graph (ie everything is a single phase). That makes it much easier to stop graph traversal at any point where a file disappears. As an example, let's say that you have a git repository that has had a file called "A" some time in the past. That file gets renamed to B, and then gets renamed back again to A. The old "git-rev-list" would show two commits: the commit that renames B to A (because it changes A) _and_ as its parent the commit that renames A to B (because it changes A). With the new --remove-empty flag, git-rev-list will show just the commit that renames B to A as the "root" commit, and stop traversal there (because that's what you want for "annotate" - you want to stop there, and for every "root" commit you then separately see if it really is a new file, or if the paths history disappeared because it was renamed from some other file). With this patch, you should be able to basically do a "poor mans 'git annotate'" with a fairly simple loop: push("HEAD", "$filename") while (revision,filename = pop()) { for each i in $(git-rev-list --parents --remove-empty $revision -- "$filename") pseudo-parents($i) = git-rev-list parents for that line if (pseudo-parents($i) is non-empty) { show diff of $i against pseudo-parents continue } /* See if the _real_ parents of $i had a rename */ parent($i) = real-parent($i) if (find-rename in $parent($i)->$i) push $parent($i), "old-name" } which should be doable in perl or something (doing stacks in shell is just too painful to be worth it, so I'm not going to do this). Anybody want to try? Linus --- rev-list.c | 136 +++++++++++++++++++++++++++++++++++-------------------------- 1 file changed, 78 insertions(+), 58 deletions(-) (limited to 'rev-list.c') diff --git a/rev-list.c b/rev-list.c index e00e6fc76d..7d3ddc6ad5 100644 --- a/rev-list.c +++ b/rev-list.c @@ -54,6 +54,7 @@ static int stop_traversal = 0; static int topo_order = 0; static int no_merges = 0; static const char **paths = NULL; +static int remove_empty_trees = 0; static void show_commit(struct commit *commit) { @@ -424,14 +425,33 @@ static void mark_edges_uninteresting(struct commit_list *list) } } -static int is_different = 0; +#define TREE_SAME 0 +#define TREE_NEW 1 +#define TREE_DIFFERENT 2 +static int tree_difference = TREE_SAME; static void file_add_remove(struct diff_options *options, int addremove, unsigned mode, const unsigned char *sha1, const char *base, const char *path) { - is_different = 1; + int diff = TREE_DIFFERENT; + + /* + * Is it an add of a new file? It means that + * the old tree didn't have it at all, so we + * will turn "TREE_SAME" -> "TREE_NEW", but + * leave any "TREE_DIFFERENT" alone (and if + * it already was "TREE_NEW", we'll keep it + * "TREE_NEW" of course). + */ + if (addremove == '+') { + diff = tree_difference; + if (diff != TREE_SAME) + return; + diff = TREE_NEW; + } + tree_difference = diff; } static void file_change(struct diff_options *options, @@ -440,7 +460,7 @@ static void file_change(struct diff_options *options, const unsigned char *new_sha1, const char *base, const char *path) { - is_different = 1; + tree_difference = TREE_DIFFERENT; } static struct diff_options diff_opt = { @@ -449,12 +469,16 @@ static struct diff_options diff_opt = { .change = file_change, }; -static int same_tree(struct tree *t1, struct tree *t2) +static int compare_tree(struct tree *t1, struct tree *t2) { - is_different = 0; + if (!t1) + return TREE_NEW; + if (!t2) + return TREE_DIFFERENT; + tree_difference = TREE_SAME; if (diff_tree_sha1(t1->object.sha1, t2->object.sha1, "", &diff_opt) < 0) - return 0; - return !is_different; + return TREE_DIFFERENT; + return tree_difference; } static int same_tree_as_empty(struct tree *t1) @@ -474,28 +498,55 @@ static int same_tree_as_empty(struct tree *t1) empty.buf = ""; empty.size = 0; - is_different = 0; + tree_difference = 0; retval = diff_tree(&empty, &real, "", &diff_opt); free(tree); - return retval >= 0 && !is_different; + return retval >= 0 && !tree_difference; } -static struct commit *try_to_simplify_merge(struct commit *commit, struct commit_list *parent) +static void try_to_simplify_commit(struct commit *commit) { + struct commit_list **pp, *parent; + if (!commit->tree) - return NULL; + return; - while (parent) { + if (!commit->parents) { + if (!same_tree_as_empty(commit->tree)) + commit->object.flags |= TREECHANGE; + return; + } + + pp = &commit->parents; + while ((parent = *pp) != NULL) { struct commit *p = parent->item; - parent = parent->next; + + if (p->object.flags & UNINTERESTING) { + pp = &parent->next; + continue; + } + parse_commit(p); - if (!p->tree) + switch (compare_tree(p->tree, commit->tree)) { + case TREE_SAME: + parent->next = NULL; + commit->parents = parent; + return; + + case TREE_NEW: + if (remove_empty_trees && same_tree_as_empty(p->tree)) { + *pp = parent->next; + continue; + } + /* fallthrough */ + case TREE_DIFFERENT: + pp = &parent->next; continue; - if (same_tree(commit->tree, p->tree)) - return p; + } + die("bad tree compare for commit %s", sha1_to_hex(commit->object.sha1)); } - return NULL; + commit->object.flags |= TREECHANGE; } static void add_parents_to_list(struct commit *commit, struct commit_list **list) @@ -531,20 +582,14 @@ static void add_parents_to_list(struct commit *commit, struct commit_list **list } /* - * Ok, the commit wasn't uninteresting. If it - * is a merge, try to find the parent that has - * no differences in the path set if one exists. + * Ok, the commit wasn't uninteresting. Try to + * simplify the commit history and find the parent + * that has no differences in the path set if one exists. */ - if (paths && parent && parent->next) { - struct commit *preferred; - - preferred = try_to_simplify_merge(commit, parent); - if (preferred) { - parent->item = preferred; - parent->next = NULL; - } - } + if (paths) + try_to_simplify_commit(commit); + parent = commit->parents; while (parent) { struct commit *p = parent->item; @@ -558,33 +603,6 @@ static void add_parents_to_list(struct commit *commit, struct commit_list **list } } -static void compress_list(struct commit_list *list) -{ - while (list) { - struct commit *commit = list->item; - struct commit_list *parent = commit->parents; - list = list->next; - - if (!parent) { - if (!same_tree_as_empty(commit->tree)) - commit->object.flags |= TREECHANGE; - continue; - } - - /* - * Exactly one parent? Check if it leaves the tree - * unchanged - */ - if (!parent->next) { - struct tree *t1 = commit->tree; - struct tree *t2 = parent->item->tree; - if (!t1 || !t2 || same_tree(t1, t2)) - continue; - } - commit->object.flags |= TREECHANGE; - } -} - static struct commit_list *limit_list(struct commit_list *list) { struct commit_list *newlist = NULL; @@ -614,8 +632,6 @@ static struct commit_list *limit_list(struct commit_list *list) } if (tree_objects) mark_edges_uninteresting(newlist); - if (paths && dense) - compress_list(newlist); if (bisect_list) newlist = find_bisection(newlist); return newlist; @@ -808,6 +824,10 @@ int main(int argc, const char **argv) dense = 0; continue; } + if (!strcmp(arg, "--remove-empty")) { + remove_empty_trees = 1; + continue; + } if (!strcmp(arg, "--")) { i++; break; -- cgit 1.2.3-korg From 93b74bca86f59b8df410b6fd4803b88ee0f304bf Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Fri, 27 Jan 2006 01:39:24 -0800 Subject: rev-list --remove-empty: add minimum help and doc entry. Signed-off-by: Junio C Hamano --- Documentation/git-rev-list.txt | 4 ++++ rev-list.c | 1 + 2 files changed, 5 insertions(+) (limited to 'rev-list.c') diff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt index f9146f1900..1c6146c764 100644 --- a/Documentation/git-rev-list.txt +++ b/Documentation/git-rev-list.txt @@ -14,6 +14,7 @@ SYNOPSIS [ \--min-age=timestamp ] [ \--sparse ] [ \--no-merges ] + [ \--remove-empty ] [ \--all ] [ [ \--merge-order [ \--show-breaks ] ] | [ \--topo-order ] ] [ \--parents ] @@ -80,6 +81,9 @@ OPTIONS (still subject to count and age limitation), but apply merge simplification nevertheless. +--remove-empty:: + Stop when a given path disappears from the tree. + --all:: Pretend as if all the refs in `$GIT_DIR/refs/` are listed on the command line as . diff --git a/rev-list.c b/rev-list.c index 7d3ddc6ad5..5bc38fea66 100644 --- a/rev-list.c +++ b/rev-list.c @@ -21,6 +21,7 @@ static const char rev_list_usage[] = " --min-age=epoch\n" " --sparse\n" " --no-merges\n" +" --remove-empty\n" " --all\n" " ordering output:\n" " --merge-order [ --show-breaks ]\n" -- cgit 1.2.3-korg From b2d4c56f2f370481c80e478ac323ebb13eece807 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Wed, 25 Jan 2006 02:37:40 -0800 Subject: diff-tree: abbreviate merge parent object names with --abbrev --pretty. When --abbrev is in effect, abbreviate the merge parent names in prettyprinted output. Signed-off-by: Junio C Hamano --- commit.c | 19 ++++++++++++++----- commit.h | 2 +- diff-tree.c | 2 +- rev-list.c | 2 +- show-branch.c | 2 +- 5 files changed, 18 insertions(+), 9 deletions(-) (limited to 'rev-list.c') diff --git a/commit.c b/commit.c index b8bf35e860..244104f930 100644 --- a/commit.c +++ b/commit.c @@ -426,9 +426,10 @@ static int is_empty_line(const char *line, int len) return !len; } -static int add_parent_info(enum cmit_fmt fmt, char *buf, const char *line, int parents) +static int add_parent_info(enum cmit_fmt fmt, char *buf, const char *line, int parents, int abbrev) { int offset = 0; + unsigned char sha1[20]; if (fmt == CMIT_FMT_ONELINE) return offset; @@ -437,17 +438,25 @@ static int add_parent_info(enum cmit_fmt fmt, char *buf, const char *line, int p break; case 2: /* Go back to the previous line: 40 characters of previous parent, and one '\n' */ - offset = sprintf(buf, "Merge: %.40s\n", line-41); + if (abbrev && !get_sha1_hex(line-41, sha1)) + offset = sprintf(buf, "Merge: %s\n", + find_unique_abbrev(sha1, abbrev)); + else + offset = sprintf(buf, "Merge: %.40s\n", line-41); /* Fallthrough */ default: /* Replace the previous '\n' with a space */ buf[offset-1] = ' '; - offset += sprintf(buf + offset, "%.40s\n", line+7); + if (abbrev && !get_sha1_hex(line+7, sha1)) + offset += sprintf(buf + offset, "%s\n", + find_unique_abbrev(sha1, abbrev)); + else + offset += sprintf(buf + offset, "%.40s\n", line+7); } return offset; } -unsigned long pretty_print_commit(enum cmit_fmt fmt, const char *msg, unsigned long len, char *buf, unsigned long space) +unsigned long pretty_print_commit(enum cmit_fmt fmt, const char *msg, unsigned long len, char *buf, unsigned long space, int abbrev) { int hdr = 1, body = 0; unsigned long offset = 0; @@ -488,7 +497,7 @@ unsigned long pretty_print_commit(enum cmit_fmt fmt, const char *msg, unsigned l if (!memcmp(line, "parent ", 7)) { if (linelen != 48) die("bad parent line in commit"); - offset += add_parent_info(fmt, buf + offset, line, ++parents); + offset += add_parent_info(fmt, buf + offset, line, ++parents, abbrev); } /* diff --git a/commit.h b/commit.h index 9c4a244bd9..a8c20964e0 100644 --- a/commit.h +++ b/commit.h @@ -48,7 +48,7 @@ enum cmit_fmt { }; extern enum cmit_fmt get_commit_format(const char *arg); -extern unsigned long pretty_print_commit(enum cmit_fmt fmt, const char *msg, unsigned long len, char *buf, unsigned long space); +extern unsigned long pretty_print_commit(enum cmit_fmt fmt, const char *msg, unsigned long len, char *buf, unsigned long space, int abbrev); /** Removes the first commit from a list sorted by date, and adds all * of its parents. diff --git a/diff-tree.c b/diff-tree.c index efa2b9476e..efa17d14a4 100644 --- a/diff-tree.c +++ b/diff-tree.c @@ -84,7 +84,7 @@ static const char *generate_header(const unsigned char *commit_sha1, diff_unique_abbrev(parent_sha1, abbrev) : "root"); offset += pretty_print_commit(commit_format, msg, len, this_header + offset, - sizeof(this_header) - offset); + sizeof(this_header) - offset, abbrev); return this_header; } diff --git a/rev-list.c b/rev-list.c index e00e6fc76d..5fad300635 100644 --- a/rev-list.c +++ b/rev-list.c @@ -81,7 +81,7 @@ static void show_commit(struct commit *commit) if (verbose_header) { static char pretty_header[16384]; - pretty_print_commit(commit_format, commit->buffer, ~0, pretty_header, sizeof(pretty_header)); + pretty_print_commit(commit_format, commit->buffer, ~0, pretty_header, sizeof(pretty_header), 0); printf("%s%c", pretty_header, hdr_termination); } fflush(stdout); diff --git a/show-branch.c b/show-branch.c index 7a0dcc649e..d06e577401 100644 --- a/show-branch.c +++ b/show-branch.c @@ -259,7 +259,7 @@ static void show_one_commit(struct commit *commit, int no_name) struct commit_name *name = commit->object.util; if (commit->object.parsed) pretty_print_commit(CMIT_FMT_ONELINE, commit->buffer, ~0, - pretty, sizeof(pretty)); + pretty, sizeof(pretty), 0); else strcpy(pretty, "(unavailable)"); if (!strncmp(pretty, "[PATCH] ", 8)) -- cgit 1.2.3-korg From 3815f423ae39bf774de3c268c6d3e3b72128a4e5 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Fri, 27 Jan 2006 01:54:59 -0800 Subject: pretty_print_commit(): pass commit object instead of commit->buffer. Signed-off-by: Junio C Hamano --- commit.c | 3 ++- commit.h | 2 +- diff-tree.c | 11 +++++------ rev-list.c | 2 +- show-branch.c | 2 +- 5 files changed, 10 insertions(+), 10 deletions(-) (limited to 'rev-list.c') diff --git a/commit.c b/commit.c index 244104f930..e8f53e8966 100644 --- a/commit.c +++ b/commit.c @@ -456,12 +456,13 @@ static int add_parent_info(enum cmit_fmt fmt, char *buf, const char *line, int p return offset; } -unsigned long pretty_print_commit(enum cmit_fmt fmt, const char *msg, unsigned long len, char *buf, unsigned long space, int abbrev) +unsigned long pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit, unsigned long len, char *buf, unsigned long space, int abbrev) { int hdr = 1, body = 0; unsigned long offset = 0; int parents = 0; int indent = (fmt == CMIT_FMT_ONELINE) ? 0 : 4; + const char *msg = commit->buffer; for (;;) { const char *line = msg; diff --git a/commit.h b/commit.h index a8c20964e0..986b22de8a 100644 --- a/commit.h +++ b/commit.h @@ -48,7 +48,7 @@ enum cmit_fmt { }; extern enum cmit_fmt get_commit_format(const char *arg); -extern unsigned long pretty_print_commit(enum cmit_fmt fmt, const char *msg, unsigned long len, char *buf, unsigned long space, int abbrev); +extern unsigned long pretty_print_commit(enum cmit_fmt fmt, const struct commit *, unsigned long len, char *buf, unsigned long space, int abbrev); /** Removes the first commit from a list sorted by date, and adds all * of its parents. diff --git a/diff-tree.c b/diff-tree.c index efa17d14a4..44bc2381c9 100644 --- a/diff-tree.c +++ b/diff-tree.c @@ -64,12 +64,13 @@ static int diff_root_tree(const unsigned char *new, const char *base) static const char *generate_header(const unsigned char *commit_sha1, const unsigned char *parent_sha1, - const char *msg) + const struct commit *commit) { static char this_header[16384]; int offset; unsigned long len; int abbrev = diff_options.abbrev; + const char *msg = commit->buffer; if (!verbose_header) return sha1_to_hex(commit_sha1); @@ -82,7 +83,7 @@ static const char *generate_header(const unsigned char *commit_sha1, offset += sprintf(this_header + offset, "(from %s)\n", parent_sha1 ? diff_unique_abbrev(parent_sha1, abbrev) : "root"); - offset += pretty_print_commit(commit_format, msg, len, + offset += pretty_print_commit(commit_format, commit, len, this_header + offset, sizeof(this_header) - offset, abbrev); return this_header; @@ -103,7 +104,7 @@ static int diff_tree_commit(const unsigned char *commit_sha1) /* Root commit? */ if (show_root_diff && !commit->parents) { - header = generate_header(sha1, NULL, commit->buffer); + header = generate_header(sha1, NULL, commit); diff_root_tree(commit_sha1, ""); } @@ -113,9 +114,7 @@ static int diff_tree_commit(const unsigned char *commit_sha1) for (parents = commit->parents; parents; parents = parents->next) { struct commit *parent = parents->item; - header = generate_header(sha1, - parent->object.sha1, - commit->buffer); + header = generate_header(sha1, parent->object.sha1, commit); diff_tree_sha1_top(parent->object.sha1, commit_sha1, ""); if (!header && verbose_header) { header_prefix = "\ndiff-tree "; diff --git a/rev-list.c b/rev-list.c index 5fad300635..334713ab66 100644 --- a/rev-list.c +++ b/rev-list.c @@ -81,7 +81,7 @@ static void show_commit(struct commit *commit) if (verbose_header) { static char pretty_header[16384]; - pretty_print_commit(commit_format, commit->buffer, ~0, pretty_header, sizeof(pretty_header), 0); + pretty_print_commit(commit_format, commit, ~0, pretty_header, sizeof(pretty_header), 0); printf("%s%c", pretty_header, hdr_termination); } fflush(stdout); diff --git a/show-branch.c b/show-branch.c index d06e577401..ffe7456a6a 100644 --- a/show-branch.c +++ b/show-branch.c @@ -258,7 +258,7 @@ static void show_one_commit(struct commit *commit, int no_name) char pretty[256], *cp; struct commit_name *name = commit->object.util; if (commit->object.parsed) - pretty_print_commit(CMIT_FMT_ONELINE, commit->buffer, ~0, + pretty_print_commit(CMIT_FMT_ONELINE, commit, ~0, pretty, sizeof(pretty), 0); else strcpy(pretty, "(unavailable)"); -- cgit 1.2.3-korg