]>
Commit | Line | Data |
---|---|---|
492e0759 LT |
1 | #include "cache.h" |
2 | #include "diff.h" | |
3 | ||
4 | static const char merge_tree_usage[] = "git-merge-tree <base-tree> <branch1> <branch2>"; | |
5 | static int resolve_directories = 1; | |
6 | ||
7 | static void merge_trees(struct tree_desc t[3], const char *base); | |
8 | ||
9 | static void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1) | |
10 | { | |
11 | unsigned long size = 0; | |
12 | void *buf = NULL; | |
13 | ||
14 | if (sha1) { | |
15 | buf = read_object_with_reference(sha1, "tree", &size, NULL); | |
16 | if (!buf) | |
17 | die("unable to read tree %s", sha1_to_hex(sha1)); | |
18 | } | |
19 | desc->size = size; | |
20 | desc->buf = buf; | |
21 | return buf; | |
22 | } | |
23 | ||
24 | struct name_entry { | |
25 | const unsigned char *sha1; | |
26 | const char *path; | |
27 | unsigned int mode; | |
28 | int pathlen; | |
29 | }; | |
30 | ||
31 | static void entry_clear(struct name_entry *a) | |
32 | { | |
33 | memset(a, 0, sizeof(*a)); | |
34 | } | |
35 | ||
36 | static int entry_compare(struct name_entry *a, struct name_entry *b) | |
37 | { | |
38 | return base_name_compare( | |
39 | a->path, a->pathlen, a->mode, | |
40 | b->path, b->pathlen, b->mode); | |
41 | } | |
42 | ||
43 | static void entry_extract(struct tree_desc *t, struct name_entry *a) | |
44 | { | |
45 | a->sha1 = tree_entry_extract(t, &a->path, &a->mode); | |
46 | a->pathlen = strlen(a->path); | |
47 | } | |
48 | ||
49 | /* An empty entry never compares same, not even to another empty entry */ | |
50 | static int same_entry(struct name_entry *a, struct name_entry *b) | |
51 | { | |
52 | return a->sha1 && | |
53 | b->sha1 && | |
54 | !memcmp(a->sha1, b->sha1, 20) && | |
55 | a->mode == b->mode; | |
56 | } | |
57 | ||
01df5297 | 58 | static const char *sha1_to_hex_zero(const unsigned char *sha1) |
492e0759 | 59 | { |
01df5297 LT |
60 | if (sha1) |
61 | return sha1_to_hex(sha1); | |
62 | return "0000000000000000000000000000000000000000"; | |
63 | } | |
64 | ||
65 | static void resolve(const char *base, struct name_entry *branch1, struct name_entry *result) | |
66 | { | |
67 | char branch1_sha1[50]; | |
68 | ||
69 | /* If it's already branch1, don't bother showing it */ | |
70 | if (!branch1) | |
71 | return; | |
72 | memcpy(branch1_sha1, sha1_to_hex_zero(branch1->sha1), 41); | |
73 | ||
74 | printf("0 %06o->%06o %s->%s %s%s\n", | |
75 | branch1->mode, result->mode, | |
76 | branch1_sha1, sha1_to_hex_zero(result->sha1), | |
77 | base, result->path); | |
492e0759 LT |
78 | } |
79 | ||
80 | static int unresolved_directory(const char *base, struct name_entry n[3]) | |
81 | { | |
82 | int baselen; | |
83 | char *newbase; | |
84 | struct name_entry *p; | |
85 | struct tree_desc t[3]; | |
86 | void *buf0, *buf1, *buf2; | |
87 | ||
88 | if (!resolve_directories) | |
89 | return 0; | |
90 | p = n; | |
91 | if (!p->mode) { | |
92 | p++; | |
93 | if (!p->mode) | |
94 | p++; | |
95 | } | |
96 | if (!S_ISDIR(p->mode)) | |
97 | return 0; | |
98 | baselen = strlen(base); | |
99 | newbase = xmalloc(baselen + p->pathlen + 2); | |
100 | memcpy(newbase, base, baselen); | |
101 | memcpy(newbase + baselen, p->path, p->pathlen); | |
102 | memcpy(newbase + baselen + p->pathlen, "/", 2); | |
103 | ||
104 | buf0 = fill_tree_descriptor(t+0, n[0].sha1); | |
105 | buf1 = fill_tree_descriptor(t+1, n[1].sha1); | |
106 | buf2 = fill_tree_descriptor(t+2, n[2].sha1); | |
107 | merge_trees(t, newbase); | |
108 | ||
109 | free(buf0); | |
110 | free(buf1); | |
111 | free(buf2); | |
112 | free(newbase); | |
113 | return 1; | |
114 | } | |
115 | ||
116 | static void unresolved(const char *base, struct name_entry n[3]) | |
117 | { | |
118 | if (unresolved_directory(base, n)) | |
119 | return; | |
01df5297 LT |
120 | if (n[0].sha1) |
121 | printf("1 %06o %s %s%s\n", n[0].mode, sha1_to_hex(n[0].sha1), base, n[0].path); | |
122 | if (n[1].sha1) | |
123 | printf("2 %06o %s %s%s\n", n[1].mode, sha1_to_hex(n[1].sha1), base, n[1].path); | |
124 | if (n[2].sha1) | |
125 | printf("3 %06o %s %s%s\n", n[2].mode, sha1_to_hex(n[2].sha1), base, n[2].path); | |
492e0759 LT |
126 | } |
127 | ||
164dcb97 LT |
128 | typedef void (*traverse_callback_t)(int n, unsigned long mask, struct name_entry *entry, const char *base); |
129 | ||
130 | static void traverse_trees(int n, struct tree_desc *t, const char *base, traverse_callback_t callback) | |
492e0759 | 131 | { |
164dcb97 LT |
132 | struct name_entry *entry = xmalloc(n*sizeof(*entry)); |
133 | ||
492e0759 LT |
134 | for (;;) { |
135 | struct name_entry entry[3]; | |
164dcb97 | 136 | unsigned long mask = 0; |
492e0759 LT |
137 | int i, last; |
138 | ||
139 | last = -1; | |
164dcb97 | 140 | for (i = 0; i < n; i++) { |
492e0759 LT |
141 | if (!t[i].size) |
142 | continue; | |
143 | entry_extract(t+i, entry+i); | |
144 | if (last >= 0) { | |
145 | int cmp = entry_compare(entry+i, entry+last); | |
146 | ||
147 | /* | |
148 | * Is the new name bigger than the old one? | |
149 | * Ignore it | |
150 | */ | |
151 | if (cmp > 0) | |
152 | continue; | |
153 | /* | |
154 | * Is the new name smaller than the old one? | |
155 | * Ignore all old ones | |
156 | */ | |
157 | if (cmp < 0) | |
158 | mask = 0; | |
159 | } | |
164dcb97 | 160 | mask |= 1ul << i; |
492e0759 LT |
161 | last = i; |
162 | } | |
163 | if (!mask) | |
164 | break; | |
165 | ||
166 | /* | |
167 | * Update the tree entries we've walked, and clear | |
168 | * all the unused name-entries. | |
169 | */ | |
164dcb97 LT |
170 | for (i = 0; i < n; i++) { |
171 | if (mask & (1ul << i)) { | |
492e0759 LT |
172 | update_tree_entry(t+i); |
173 | continue; | |
174 | } | |
175 | entry_clear(entry + i); | |
176 | } | |
164dcb97 LT |
177 | callback(n, mask, entry, base); |
178 | } | |
179 | free(entry); | |
180 | } | |
492e0759 | 181 | |
164dcb97 LT |
182 | /* |
183 | * Merge two trees together (t[1] and t[2]), using a common base (t[0]) | |
184 | * as the origin. | |
185 | * | |
186 | * This walks the (sorted) trees in lock-step, checking every possible | |
187 | * name. Note that directories automatically sort differently from other | |
188 | * files (see "base_name_compare"), so you'll never see file/directory | |
189 | * conflicts, because they won't ever compare the same. | |
190 | * | |
191 | * IOW, if a directory changes to a filename, it will automatically be | |
192 | * seen as the directory going away, and the filename being created. | |
193 | * | |
194 | * Think of this as a three-way diff. | |
195 | * | |
196 | * The output will be either: | |
197 | * - successful merge | |
198 | * "0 mode sha1 filename" | |
199 | * NOTE NOTE NOTE! FIXME! We really really need to walk the index | |
200 | * in parallel with this too! | |
201 | * | |
202 | * - conflict: | |
203 | * "1 mode sha1 filename" | |
204 | * "2 mode sha1 filename" | |
205 | * "3 mode sha1 filename" | |
206 | * where not all of the 1/2/3 lines may exist, of course. | |
207 | * | |
208 | * The successful merge rules are the same as for the three-way merge | |
209 | * in git-read-tree. | |
210 | */ | |
211 | static void threeway_callback(int n, unsigned long mask, struct name_entry *entry, const char *base) | |
212 | { | |
213 | /* Same in both? */ | |
214 | if (same_entry(entry+1, entry+2)) { | |
215 | if (entry[0].sha1) { | |
216 | resolve(base, NULL, entry+1); | |
217 | return; | |
492e0759 | 218 | } |
164dcb97 | 219 | } |
492e0759 | 220 | |
164dcb97 LT |
221 | if (same_entry(entry+0, entry+1)) { |
222 | if (entry[2].sha1 && !S_ISDIR(entry[2].mode)) { | |
223 | resolve(base, entry+1, entry+2); | |
224 | return; | |
492e0759 | 225 | } |
164dcb97 | 226 | } |
492e0759 | 227 | |
164dcb97 LT |
228 | if (same_entry(entry+0, entry+2)) { |
229 | if (entry[1].sha1 && !S_ISDIR(entry[1].mode)) { | |
230 | resolve(base, NULL, entry+1); | |
231 | return; | |
492e0759 | 232 | } |
492e0759 | 233 | } |
164dcb97 LT |
234 | |
235 | unresolved(base, entry); | |
236 | } | |
237 | ||
238 | static void merge_trees(struct tree_desc t[3], const char *base) | |
239 | { | |
240 | traverse_trees(3, t, base, threeway_callback); | |
492e0759 LT |
241 | } |
242 | ||
243 | static void *get_tree_descriptor(struct tree_desc *desc, const char *rev) | |
244 | { | |
245 | unsigned char sha1[20]; | |
246 | void *buf; | |
247 | ||
248 | if (get_sha1(rev, sha1) < 0) | |
249 | die("unknown rev %s", rev); | |
250 | buf = fill_tree_descriptor(desc, sha1); | |
251 | if (!buf) | |
252 | die("%s is not a tree", rev); | |
253 | return buf; | |
254 | } | |
255 | ||
256 | int main(int argc, char **argv) | |
257 | { | |
258 | struct tree_desc t[3]; | |
259 | void *buf1, *buf2, *buf3; | |
260 | ||
261 | if (argc < 4) | |
262 | usage(merge_tree_usage); | |
263 | ||
264 | buf1 = get_tree_descriptor(t+0, argv[1]); | |
265 | buf2 = get_tree_descriptor(t+1, argv[2]); | |
266 | buf3 = get_tree_descriptor(t+2, argv[3]); | |
267 | merge_trees(t, ""); | |
268 | free(buf1); | |
269 | free(buf2); | |
270 | free(buf3); | |
271 | return 0; | |
272 | } |