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  * Another pathological example how this thing used to fail to mark an
  86  * ancestor of a merge base as UNINTERESTING before we introduced the
  87  * postprocessing phase (mark_reachable_commits).
  88  *
  89  *                2
  90  *                H
  91  *          1    / \
  92  *          G   A   \
  93  *          |\ /     \
  94  *          | B       \
  95  *          |  \       \
  96  *           \  C       F
  97  *            \  \     /
  98  *             \  D   /
  99  *              \ |  /
 100  *               \| /
 101  *                E
 102  *
 103  *       list                   A B C D E F G H
 104  *       G1 H2                  - - - - - - 1 2
 105  *       H2 E1 B1               - 1 - - 1 - 1 2
 106  *       F2 E1 B1 A2            2 1 - - 1 2 1 2
 107  *       E3 B1 A2               2 1 - - 3 2 1 2
 108  *       B1 A2                  2 1 - - 3 2 1 2
 109  *       C1 A2                  2 1 1 - 3 2 1 2
 110  *       D1 A2                  2 1 1 1 3 2 1 2
 111  *       A2                     2 1 1 1 3 2 1 2
 112  *       B3                     2 3 1 1 3 2 1 2
 113  *       C7                     2 3 7 1 3 2 1 2
 114  *
 115  * At this point, unfortunately, everybody in the list is
 116  * uninteresting, so we fail to complete the following two
 117  * steps to fully marking uninteresting commits.
 118  *
 119  *       D7                     2 3 7 7 3 2 1 2
 120  *       E7                     2 3 7 7 7 2 1 2
 121  *
 122  * and we ended up showing E as an interesting merge base.
 123  * The postprocessing phase re-injects C and continues traversal
 124  * to contaminate D and E.
 125  */
 126
 127 static void mark_reachable_commits(struct commit_list *result,
 128                                    struct commit_list *list)
 129 {
 130         struct commit_list *tmp;
 131
 132         /*
 133          * Postprocess to fully contaminate the well.
 134          */
 135         for (tmp = result; tmp; tmp = tmp->next) {
 136                 struct commit *c = tmp->item;
 137                 /* Reinject uninteresting ones to list,
 138                  * so we can scan their parents.
 139                  */
 140                 if (c->object.flags & UNINTERESTING)
 141                         commit_list_insert(c, &list);
 142         }
 143         while (list) {
 144                 struct commit *c = list->item;
 145                 struct commit_list *parents;
 146
 147                 tmp = list;
 148                 list = list->next;
 149                 free(tmp);
 150
 151                 /* Anything taken out of the list is uninteresting, so
 152                  * mark all its parents uninteresting.  We do not
 153                  * parse new ones (we already parsed all the relevant
 154                  * ones).
 155                  */
 156                 parents = c->parents;
 157                 while (parents) {
 158                         struct commit *p = parents->item;
 159                         parents = parents->next;
 160                         if (!(p->object.flags & UNINTERESTING)) {
 161                                 p->object.flags |= UNINTERESTING;
 162                                 commit_list_insert(p, &list);
 163                         }
 164                 }
 165         }
 166 }
 167
 168 struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2)
 169 {
 170         struct commit_list *list = NULL;
 171         struct commit_list *result = NULL;
 172         struct commit_list *tmp = NULL;
 173
 174         if (rev1 == rev2)
 175                 return commit_list_insert(rev1, &result);
 176
 177         parse_commit(rev1);
 178         parse_commit(rev2);
 179
 180         rev1->object.flags |= PARENT1;
 181         rev2->object.flags |= PARENT2;
 182         insert_by_date(rev1, &list);
 183         insert_by_date(rev2, &list);
 184
 185         while (interesting(list)) {
 186                 struct commit *commit = list->item;
 187                 struct commit_list *parents;
 188                 int flags = commit->object.flags
 189                         & (PARENT1 | PARENT2 | UNINTERESTING);
 190
 191                 tmp = list;
 192                 list = list->next;
 193                 free(tmp);
 194                 if (flags == (PARENT1 | PARENT2)) {
 195                         insert_by_date(commit, &result);
 196
 197                         /* Mark parents of a found merge uninteresting */
 198                         flags |= UNINTERESTING;
 199                 }
 200                 parents = commit->parents;
 201                 while (parents) {
 202                         struct commit *p = parents->item;
 203                         parents = parents->next;
 204                         if ((p->object.flags & flags) == flags)
 205                                 continue;
 206                         parse_commit(p);
 207                         p->object.flags |= flags;
 208                         insert_by_date(p, &list);
 209                 }
 210         }
 211
 212         if (!result)
 213                 return NULL;
 214
 215         if (result->next && list)
 216                 mark_reachable_commits(result, list);
 217
 218         /* cull duplicates */
 219         for (tmp = result, list = NULL; tmp; ) {
 220                 struct commit *commit = tmp->item;
 221                 struct commit_list *next = tmp->next;
 222                 if (commit->object.flags & UNINTERESTING) {
 223                         if (list != NULL)
 224                                 list->next = next;
 225                         free(tmp);
 226                 } else {
 227                         if (list == NULL)
 228                                 result = tmp;
 229                         list = tmp;
 230                         commit->object.flags |= UNINTERESTING;
 231                 }
 232
 233                 tmp = next;
 234         }
 235
 236         /* reset flags */
 237         clear_commit_marks(rev1, PARENT1 | PARENT2 | UNINTERESTING);
 238         clear_commit_marks(rev2, PARENT1 | PARENT2 | UNINTERESTING);
 239
 240         return result;
 241 }
 242
 243 static int show_all = 0;
 244
 245 static int merge_base(struct commit *rev1, struct commit *rev2)
 246 {
 247         struct commit_list *result = get_merge_bases(rev1, rev2);
 248
 249         if (!result)
 250                 return 1;
 251
 252         while (result) {
 253                 printf("%s\n", sha1_to_hex(result->item->object.sha1));
 254                 if (!show_all)
 255                         return 0;
 256                 result = result->next;
 257         }
 258
 259         return 0;
 260 }
 261
 262 static const char merge_base_usage[] =
 263 "git-merge-base [--all] <commit-id> <commit-id>";
 264
 265 int main(int argc, char **argv)
 266 {
 267         struct commit *rev1, *rev2;
 268         unsigned char rev1key[20], rev2key[20];
 269
 270         setup_git_directory();
 271         git_config(git_default_config);
 272
 273         while (1 < argc && argv[1][0] == '-') {
 274                 char *arg = argv[1];
 275                 if (!strcmp(arg, "-a") || !strcmp(arg, "--all"))
 276                         show_all = 1;
 277                 else
 278                         usage(merge_base_usage);
 279                 argc--; argv++;
 280         }
 281         if (argc != 3)
 282                 usage(merge_base_usage);
 283         if (get_sha1(argv[1], rev1key))
 284                 die("Not a valid object name %s", argv[1]);
 285         if (get_sha1(argv[2], rev2key))
 286                 die("Not a valid object name %s", argv[2]);
 287         rev1 = lookup_commit_reference(rev1key);
 288         rev2 = lookup_commit_reference(rev2key);
 289         if (!rev1 || !rev2)
 290                 return 1;
 291         return merge_base(rev1, rev2);
 292 }