Andrew's git / gitweb.git /
923256c821582f38daffed4fb0df2a97fe66d74b
   1#include <stdlib.h>
   2#include "cache.h"
   3#include "commit.h"
   4
   5#define PARENT1 1
   6#define PARENT2 2
   7#define UNINTERESTING 4
   8
   9static struct commit *interesting(struct commit_list *list)
  10{
  11        while (list) {
  12                struct commit *commit = list->item;
  13                list = list->next;
  14                if (commit->object.flags & UNINTERESTING)
  15                        continue;
  16                return commit;
  17        }
  18        return NULL;
  19}
  20
  21/*
  22 * A pathological example of how this thing works.
  23 *
  24 * Suppose we had this commit graph, where chronologically
  25 * the timestamp on the commit are A <= B <= C <= D <= E <= F
  26 * and we are trying to figure out the merge base for E and F
  27 * commits.
  28 *
  29 *                  F
  30 *                 / \
  31 *            E   A   D
  32 *             \ /   /  
  33 *              B   /
  34 *               \ /
  35 *                C
  36 *
  37 * First we push E and F to list to be processed.  E gets bit 1
  38 * and F gets bit 2.  The list becomes:
  39 *
  40 *     list=F(2) E(1), result=empty
  41 *
  42 * Then we pop F, the newest commit, from the list.  Its flag is 2.
  43 * We scan its parents, mark them reachable from the side that F is
  44 * reachable from, and push them to the list:
  45 *
  46 *     list=E(1) D(2) A(2), result=empty
  47 *
  48 * Next pop E and do the same.
  49 *
  50 *     list=D(2) B(1) A(2), result=empty
  51 *
  52 * Next pop D and do the same.
  53 *
  54 *     list=C(2) B(1) A(2), result=empty
  55 *
  56 * Next pop C and do the same.
  57 *
  58 *     list=B(1) A(2), result=empty
  59 *
  60 * Now it is B's turn.  We mark its parent, C, reachable from B's side,
  61 * and push it to the list:
  62 *
  63 *     list=C(3) A(2), result=empty
  64 *
  65 * Now pop C and notice it has flags==3.  It is placed on the result list,
  66 * and the list now contains:
  67 *
  68 *     list=A(2), result=C(3)
  69 *
  70 * We pop A and do the same.
  71 * 
  72 *     list=B(3), result=C(3)
  73 *
  74 * Next, we pop B and something very interesting happens.  It has flags==3
  75 * so it is also placed on the result list, and its parents are marked
  76 * uninteresting, retroactively, and placed back on the list:
  77 *
  78 *    list=C(7), result=C(7) B(3)
  79 * 
  80 * Now, list does not have any interesting commit.  So we find the newest
  81 * commit from the result list that is not marked uninteresting.  Which is
  82 * commit B.
  83 */
  84
  85static struct commit *common_ancestor(struct commit *rev1, struct commit *rev2)
  86{
  87        struct commit_list *list = NULL;
  88        struct commit_list *result = NULL;
  89
  90        if (rev1 == rev2)
  91                return rev1;
  92
  93        parse_commit(rev1);
  94        parse_commit(rev2);
  95
  96        rev1->object.flags |= 1;
  97        rev2->object.flags |= 2;
  98        insert_by_date(rev1, &list);
  99        insert_by_date(rev2, &list);
 100
 101        while (interesting(list)) {
 102                struct commit *commit = list->item;
 103                struct commit_list *tmp = list, *parents;
 104                int flags = commit->object.flags & 7;
 105
 106                list = list->next;
 107                free(tmp);
 108                if (flags == 3) {
 109                        insert_by_date(commit, &result);
 110
 111                        /* Mark children of a found merge uninteresting */
 112                        flags |= UNINTERESTING;
 113                }
 114                parents = commit->parents;
 115                while (parents) {
 116                        struct commit *p = parents->item;
 117                        parents = parents->next;
 118                        if ((p->object.flags & flags) == flags)
 119                                continue;
 120                        parse_commit(p);
 121                        p->object.flags |= flags;
 122                        insert_by_date(p, &list);
 123                }
 124        }
 125        return interesting(result);
 126}
 127
 128int main(int argc, char **argv)
 129{
 130        struct commit *rev1, *rev2, *ret;
 131        unsigned char rev1key[20], rev2key[20];
 132
 133        if (argc != 3 ||
 134            get_sha1(argv[1], rev1key) ||
 135            get_sha1(argv[2], rev2key)) {
 136                usage("git-merge-base <commit-id> <commit-id>");
 137        }
 138        rev1 = lookup_commit_reference(rev1key);
 139        rev2 = lookup_commit_reference(rev2key);
 140        if (!rev1 || !rev2)
 141                return 1;
 142        ret = common_ancestor(rev1, rev2);
 143        if (!ret)
 144                return 1;
 145        printf("%s\n", sha1_to_hex(ret->object.sha1));
 146        return 0;
 147}