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{ 11while(list) { 12struct commit *commit = list->item; 13 list = list->next; 14if(commit->object.flags & UNINTERESTING) 15continue; 16return commit; 17} 18return 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 can fail to mark an ancestor 86 * of a merge base as UNINTERESTING without the postprocessing phase. 87 * 88 * 2 89 * H 90 * 1 / \ 91 * G A \ 92 * |\ / \ 93 * | B \ 94 * | \ \ 95 * \ C F 96 * \ \ / 97 * \ D / 98 * \ | / 99 * \| / 100 * E 101 * 102 * list A B C D E F G H 103 * G1 H2 - - - - - - 1 2 104 * H2 E1 B1 - 1 - - 1 - 1 2 105 * F2 E1 B1 A2 2 1 - - 1 2 1 2 106 * E3 B1 A2 2 1 - - 3 2 1 2 107 * B1 A2 2 1 - - 3 2 1 2 108 * C1 A2 2 1 1 - 3 2 1 2 109 * D1 A2 2 1 1 1 3 2 1 2 110 * A2 2 1 1 1 3 2 1 2 111 * B3 2 3 1 1 3 2 1 2 112 * C7 2 3 7 1 3 2 1 2 113 * 114 * At this point, unfortunately, everybody in the list is 115 * uninteresting, so we fail to complete the following two 116 * steps to fully marking uninteresting commits. 117 * 118 * D7 2 3 7 7 3 2 1 2 119 * E7 2 3 7 7 7 2 1 2 120 * 121 * and we end up showing E as an interesting merge base. 122 */ 123 124static int show_all =0; 125 126static intmerge_base(struct commit *rev1,struct commit *rev2) 127{ 128struct commit_list *list = NULL; 129struct commit_list *result = NULL; 130struct commit_list *tmp = NULL; 131 132if(rev1 == rev2) { 133printf("%s\n",sha1_to_hex(rev1->object.sha1)); 134return0; 135} 136 137parse_commit(rev1); 138parse_commit(rev2); 139 140 rev1->object.flags |=1; 141 rev2->object.flags |=2; 142insert_by_date(rev1, &list); 143insert_by_date(rev2, &list); 144 145while(interesting(list)) { 146struct commit *commit = list->item; 147struct commit_list *parents; 148int flags = commit->object.flags &7; 149 150 tmp = list; 151 list = list->next; 152free(tmp); 153if(flags ==3) { 154insert_by_date(commit, &result); 155 156/* Mark parents of a found merge uninteresting */ 157 flags |= UNINTERESTING; 158} 159 parents = commit->parents; 160while(parents) { 161struct commit *p = parents->item; 162 parents = parents->next; 163if((p->object.flags & flags) == flags) 164continue; 165parse_commit(p); 166 p->object.flags |= flags; 167insert_by_date(p, &list); 168} 169} 170 171if(!result) 172return1; 173 174/* 175 * Postprocess to fully contaminate the well. 176 */ 177for(tmp = result; tmp; tmp = tmp->next) { 178struct commit *c = tmp->item; 179/* Reinject uninteresting ones to list, 180 * so we can scan their parents. 181 */ 182if(c->object.flags & UNINTERESTING) 183commit_list_insert(c, &list); 184} 185while(list) { 186struct commit *c = list->item; 187struct commit_list *parents; 188 189 tmp = list; 190 list = list->next; 191free(tmp); 192 193/* Anything taken out of the list is uninteresting, so 194 * mark all its parents uninteresting. We do not 195 * parse new ones (we already parsed all the relevant 196 * ones). 197 */ 198 parents = c->parents; 199while(parents) { 200struct commit *p = parents->item; 201 parents = parents->next; 202if(!(p->object.flags & UNINTERESTING)) { 203 p->object.flags |= UNINTERESTING; 204commit_list_insert(p, &list); 205} 206} 207} 208 209while(result) { 210struct commit *commit = result->item; 211 result = result->next; 212if(commit->object.flags & UNINTERESTING) 213continue; 214printf("%s\n",sha1_to_hex(commit->object.sha1)); 215if(!show_all) 216return0; 217 commit->object.flags |= UNINTERESTING; 218} 219return0; 220} 221 222static const char merge_base_usage[] = 223"git-merge-base [--all] <commit-id> <commit-id>"; 224 225intmain(int argc,char**argv) 226{ 227struct commit *rev1, *rev2; 228unsigned char rev1key[20], rev2key[20]; 229 230while(1< argc && argv[1][0] =='-') { 231char*arg = argv[1]; 232if(!strcmp(arg,"-a") || !strcmp(arg,"--all")) 233 show_all =1; 234else 235usage(merge_base_usage); 236 argc--; argv++; 237} 238if(argc !=3|| 239get_sha1(argv[1], rev1key) || 240get_sha1(argv[2], rev2key)) 241usage(merge_base_usage); 242 rev1 =lookup_commit_reference(rev1key); 243 rev2 =lookup_commit_reference(rev2key); 244if(!rev1 || !rev2) 245return1; 246returnmerge_base(rev1, rev2); 247}