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 * 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 127static 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 168struct 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 243static int show_all = 0; 244 245static 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 262static const char merge_base_usage[] = 263"git-merge-base [--all] <commit-id> <commit-id>"; 264 265int 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}