[PATCH] Fix local pull that uses packs.
[git] / 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 }