Re: Add merge-base
Dear diary, on Sun, Apr 17, 2005 at 05:27:13PM CEST, I got a letter where Daniel Barkalow <barkalow@iabervon.org> told me that...
> merge-base finds one of the best common ancestors of a pair of commits. In
> particular, it finds one of the ones which is fewest commits away from the
> further of the heads.
What does it return when I have
A -- C
\/ \
/\ /
B -- D? >:)
I assume just either A or B, randomly?
I think it would be best if it could list all the "first-class" matches (both A and B in this case), each on a separate line; this way the overlay tools could choose an algorithm to evaluate those further as they see fit - e.g. sort them by time (you might aid that by listing the commit time in front of them), then take the first n and try to diff them all and take the one with least changes (as suggested by Linus).
And if someone doesn't care, he just does | head -n 1 | cut -f 2.
Show 15 quoted lines
> Index: merge-base.c
> ===================================================================
> --- /dev/null (tree:37a0b01b85c2999243674d48bfc71cdba0e5518e)
> +++ d662b707e11391f6cfe597fd4d0bf9c41d34d01a/merge-base.c (mode:100644 sha1:0f85e7d9e9a896d1142a54170ddf1159f11f9cdd)
> @@ -0,0 +1,108 @@
> +#include <stdlib.h>
> +#include "cache.h"
> +#include "revision.h"
> +
> +struct revision *common_ancestor(struct revision *rev1, struct revision *rev2)
> +{
> + struct parent *parent;
> +
> + struct parent *rev1list = malloc(sizeof(struct parent));
> + struct parent *rev2list = malloc(sizeof(struct parent));Did I overlook anything or you could have just a single revlist?
> +
I smell trailing whitespaces!
Show 20 quoted lines
> + struct parent *posn, *temp;
> +
> + rev1list->parent = rev1;
> + rev1list->next = NULL;
> +
> + rev2list->parent = rev2;
> + rev2list->next = NULL;
> +
> + while (rev1list || rev2list) {
> + posn = rev1list;
> + rev1list = NULL;
> + while (posn) {
> + parse_commit_object(posn->parent);
> + if (posn->parent->flags & 0x0001) {
> + /*
> + printf("1 already seen %s %x\n",
> + sha1_to_hex(posn->parent->sha1),
> + posn->parent->flags);
> + */
> + // do nothingMostly for consistency, I'd prefer you to use /* */ comments in general.
I think a terrified squeak at stderr in this situation (possibly suggesting fsck-cache) might be appropriate.
> + } else if (posn->parent->flags & 0x0002) {
> + // XXXX free listsHmm, so, why not free the lists?
Show 50 quoted lines
> + return posn->parent;
> + } else {
> + /*
> + printf("1 based on %s\n",
> + sha1_to_hex(posn->parent->sha1));
> + */
> + posn->parent->flags |= 0x0001;
> +
> + parent = posn->parent->parent;
> + while (parent) {
> + temp = malloc(sizeof(struct parent));
> + temp->next = rev1list;
> + temp->parent = parent->parent;
> + rev1list = temp;
> + parent = parent->next;
> + }
> + }
> + posn = posn->next;
> + }
> + posn = rev2list;
> + rev2list = NULL;
> + while (posn) {
> + parse_commit_object(posn->parent);
> + if (posn->parent->flags & 0x0002) {
> + /*
> + printf("2 already seen %s\n",
> + sha1_to_hex(posn->parent->sha1));
> + */
> + // do nothing
> + } else if (posn->parent->flags & 0x0001) {
> + // XXXX free lists
> + return posn->parent;
> + } else {
> + /*
> + printf("2 based on %s\n",
> + sha1_to_hex(posn->parent->sha1));
> + */
> + posn->parent->flags |= 0x0002;
> +
> + parent = posn->parent->parent;
> + while (parent) {
> + temp = malloc(sizeof(struct parent));
> + temp->next = rev2list;
> + temp->parent = parent->parent;
> + rev2list = temp;
> + parent = parent->next;
> + }
> + }
> + posn = posn->next;
> + }Symmetrical notes apply to this half. Actually, they are too similar. What about factoring them to a common function?
Show 8 quoted lines
> + }
> + return NULL;
> +}
> +
> +int main(int argc, char **argv)
> +{
> + struct revision *rev1, *rev2, *ret;
> + unsigned char rev1key[20], rev2key[20];Show 14 quoted lines
> + if (argc != 3 ||
> + get_sha1_hex(argv[1], rev1key) ||
> + get_sha1_hex(argv[2], rev2key)) {
> + usage("mergebase <commit-id> <commit-id>");
> + }
> + rev1 = lookup_rev(rev1key);
> + rev2 = lookup_rev(rev2key);
> + ret = common_ancestor(rev1, rev2);
> + if (ret) {
> + printf("%s\n", sha1_to_hex(ret->sha1));
> + return 0;
> + } else {
> + printf("Sorry.\n");
> + return 1;Please stay silent if you don't have anything useful to say.
> + }
> +
> +}
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
C++: an octopus made by nailing extra legs onto a dog. -- Steve Taylor
Daniel Barkalow
