diff options
author | Linus Torvalds <torvalds@ppc970.osdl.org> | 2005-06-17 22:54:50 -0700 |
---|---|---|
committer | Linus Torvalds <torvalds@ppc970.osdl.org> | 2005-06-17 22:54:50 -0700 |
commit | 8b3a1e056f2107deedfdada86046971c9ad7bb87 (patch) | |
tree | 6414aac945a94018a479560bc4a7894826cab95a | |
parent | 753fd78458b6d7d0e65ce0ebe7b62e1bc55f3992 (diff) | |
download | git-8b3a1e056f2107deedfdada86046971c9ad7bb87.tar.gz git-8b3a1e056f2107deedfdada86046971c9ad7bb87.tar.xz |
git-rev-list: add "--bisect" flag to find the "halfway" point
This is useful for doing binary searching for problems. You start with
a known good and known bad point, and you then test the "halfway" point
in between:
git-rev-list --bisect bad ^good
and you test that. If that one tests good, you now still have a known
bad case, but two known good points, and you can bisect again:
git-rev-list --bisect bad ^good1 ^good2
and test that point. If that point is bad, you now use that as your
known-bad starting point:
git-rev-list --bisect newbad ^good1 ^good2
and basically at every iteration you shrink your list of commits by
half: you're binary searching for the point where the troubles started,
even though there isn't a nice linear ordering.
-rw-r--r-- | rev-list.c | 80 |
1 files changed, 80 insertions, 0 deletions
diff --git a/rev-list.c b/rev-list.c index b526ad4e0..c7ebd2f03 100644 --- a/rev-list.c +++ b/rev-list.c @@ -4,6 +4,7 @@ #define SEEN (1u << 0) #define INTERESTING (1u << 1) +#define COUNTED (1u << 2) static const char rev_list_usage[] = "usage: git-rev-list [OPTION] commit-id <commit-id>\n" @@ -14,6 +15,7 @@ static const char rev_list_usage[] = " --pretty\n" " --merge-order [ --show-breaks ]"; +static int bisect_list = 0; static int verbose_header = 0; static int show_parents = 0; static int hdr_termination = 0; @@ -115,6 +117,78 @@ static int everybody_uninteresting(struct commit_list *list) return 1; } +/* + * This is a truly stupid algorithm, but it's only + * used for bisection, and we just don't care enough. + * + * We care just barely enough to avoid recursing for + * non-merge entries. + */ +static int count_distance(struct commit_list *entry) +{ + int nr = 0; + + while (entry) { + struct commit *commit = entry->item; + struct commit_list *p; + + if (commit->object.flags & (UNINTERESTING | COUNTED)) + break; + nr++; + commit->object.flags |= COUNTED; + p = commit->parents; + entry = p; + if (p) { + p = p->next; + while (p) { + nr += count_distance(p); + p = p->next; + } + } + } + return nr; +} + +static int clear_distance(struct commit_list *list) +{ + while (list) { + struct commit *commit = list->item; + commit->object.flags &= ~COUNTED; + list = list->next; + } +} + +static struct commit_list *find_bisection(struct commit_list *list) +{ + int nr, closest; + struct commit_list *p, *best; + + nr = 0; + p = list; + while (p) { + nr++; + p = p->next; + } + closest = 0; + best = list; + + p = list; + while (p) { + int distance = count_distance(p); + clear_distance(list); + if (nr - distance < distance) + distance = nr - distance; + if (distance > closest) { + best = p; + closest = distance; + } + p = p->next; + } + if (best) + best->next = NULL; + return best; +} + struct commit_list *limit_list(struct commit_list *list) { struct commit_list *newlist = NULL; @@ -131,6 +205,8 @@ struct commit_list *limit_list(struct commit_list *list) } p = &commit_list_insert(commit, p)->next; } while (list); + if (bisect_list) + newlist = find_bisection(newlist); return newlist; } @@ -186,6 +262,10 @@ int main(int argc, char **argv) show_parents = 1; continue; } + if (!strcmp(arg, "--bisect")) { + bisect_list = 1; + continue; + } if (!strncmp(arg, "--merge-order", 13)) { merge_order = 1; continue; |