merge-base.c

   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
   9 static 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
  85 static 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
 128 int 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 }