]>
Commit | Line | Data |
---|---|---|
75ef3f4a JH |
1 | #include "cache.h" |
2 | #include "commit.h" | |
3 | #include "refs.h" | |
2085b16a JH |
4 | #include "diff.h" |
5 | #include "diffcore.h" | |
56881843 | 6 | #include "notes.h" |
75ef3f4a JH |
7 | #include "notes-merge.h" |
8 | ||
2085b16a JH |
9 | struct notes_merge_pair { |
10 | unsigned char obj[20], base[20], local[20], remote[20]; | |
11 | }; | |
12 | ||
75ef3f4a JH |
13 | void init_notes_merge_options(struct notes_merge_options *o) |
14 | { | |
15 | memset(o, 0, sizeof(struct notes_merge_options)); | |
16 | o->verbosity = NOTES_MERGE_VERBOSITY_DEFAULT; | |
17 | } | |
18 | ||
19 | #define OUTPUT(o, v, ...) \ | |
20 | do { \ | |
21 | if ((o)->verbosity >= (v)) { \ | |
22 | printf(__VA_ARGS__); \ | |
23 | puts(""); \ | |
24 | } \ | |
25 | } while (0) | |
26 | ||
2085b16a JH |
27 | static int path_to_sha1(const char *path, unsigned char *sha1) |
28 | { | |
29 | char hex_sha1[40]; | |
30 | int i = 0; | |
31 | while (*path && i < 40) { | |
32 | if (*path != '/') | |
33 | hex_sha1[i++] = *path; | |
34 | path++; | |
35 | } | |
36 | if (*path || i != 40) | |
37 | return -1; | |
38 | return get_sha1_hex(hex_sha1, sha1); | |
39 | } | |
40 | ||
41 | static int verify_notes_filepair(struct diff_filepair *p, unsigned char *sha1) | |
42 | { | |
43 | switch (p->status) { | |
44 | case DIFF_STATUS_MODIFIED: | |
45 | assert(p->one->mode == p->two->mode); | |
46 | assert(!is_null_sha1(p->one->sha1)); | |
47 | assert(!is_null_sha1(p->two->sha1)); | |
48 | break; | |
49 | case DIFF_STATUS_ADDED: | |
50 | assert(is_null_sha1(p->one->sha1)); | |
51 | break; | |
52 | case DIFF_STATUS_DELETED: | |
53 | assert(is_null_sha1(p->two->sha1)); | |
54 | break; | |
55 | default: | |
56 | return -1; | |
57 | } | |
58 | assert(!strcmp(p->one->path, p->two->path)); | |
59 | return path_to_sha1(p->one->path, sha1); | |
60 | } | |
61 | ||
62 | static struct notes_merge_pair *find_notes_merge_pair_pos( | |
63 | struct notes_merge_pair *list, int len, unsigned char *obj, | |
64 | int insert_new, int *occupied) | |
65 | { | |
66 | /* | |
67 | * Both diff_tree_remote() and diff_tree_local() tend to process | |
68 | * merge_pairs in ascending order. Therefore, cache last returned | |
69 | * index, and search sequentially from there until the appropriate | |
70 | * position is found. | |
71 | * | |
72 | * Since inserts only happen from diff_tree_remote() (which mainly | |
73 | * _appends_), we don't care that inserting into the middle of the | |
74 | * list is expensive (using memmove()). | |
75 | */ | |
76 | static int last_index; | |
77 | int i = last_index < len ? last_index : len - 1; | |
78 | int prev_cmp = 0, cmp = -1; | |
79 | while (i >= 0 && i < len) { | |
80 | cmp = hashcmp(obj, list[i].obj); | |
81 | if (!cmp) /* obj belongs @ i */ | |
82 | break; | |
83 | else if (cmp < 0 && prev_cmp <= 0) /* obj belongs < i */ | |
84 | i--; | |
85 | else if (cmp < 0) /* obj belongs between i-1 and i */ | |
86 | break; | |
87 | else if (cmp > 0 && prev_cmp >= 0) /* obj belongs > i */ | |
88 | i++; | |
89 | else /* if (cmp > 0) */ { /* obj belongs between i and i+1 */ | |
90 | i++; | |
91 | break; | |
92 | } | |
93 | prev_cmp = cmp; | |
94 | } | |
95 | if (i < 0) | |
96 | i = 0; | |
97 | /* obj belongs at, or immediately preceding, index i (0 <= i <= len) */ | |
98 | ||
99 | if (!cmp) | |
100 | *occupied = 1; | |
101 | else { | |
102 | *occupied = 0; | |
103 | if (insert_new && i < len) { | |
104 | memmove(list + i + 1, list + i, | |
105 | (len - i) * sizeof(struct notes_merge_pair)); | |
106 | memset(list + i, 0, sizeof(struct notes_merge_pair)); | |
107 | } | |
108 | } | |
109 | last_index = i; | |
110 | return list + i; | |
111 | } | |
112 | ||
113 | static unsigned char uninitialized[20] = | |
114 | "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" \ | |
115 | "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff"; | |
116 | ||
117 | static struct notes_merge_pair *diff_tree_remote(struct notes_merge_options *o, | |
118 | const unsigned char *base, | |
119 | const unsigned char *remote, | |
120 | int *num_changes) | |
121 | { | |
122 | struct diff_options opt; | |
123 | struct notes_merge_pair *changes; | |
124 | int i, len = 0; | |
125 | ||
126 | trace_printf("\tdiff_tree_remote(base = %.7s, remote = %.7s)\n", | |
127 | sha1_to_hex(base), sha1_to_hex(remote)); | |
128 | ||
129 | diff_setup(&opt); | |
130 | DIFF_OPT_SET(&opt, RECURSIVE); | |
131 | opt.output_format = DIFF_FORMAT_NO_OUTPUT; | |
132 | if (diff_setup_done(&opt) < 0) | |
133 | die("diff_setup_done failed"); | |
134 | diff_tree_sha1(base, remote, "", &opt); | |
135 | diffcore_std(&opt); | |
136 | ||
137 | changes = xcalloc(diff_queued_diff.nr, sizeof(struct notes_merge_pair)); | |
138 | ||
139 | for (i = 0; i < diff_queued_diff.nr; i++) { | |
140 | struct diff_filepair *p = diff_queued_diff.queue[i]; | |
141 | struct notes_merge_pair *mp; | |
142 | int occupied; | |
143 | unsigned char obj[20]; | |
144 | ||
145 | if (verify_notes_filepair(p, obj)) { | |
146 | trace_printf("\t\tCannot merge entry '%s' (%c): " | |
147 | "%.7s -> %.7s. Skipping!\n", p->one->path, | |
148 | p->status, sha1_to_hex(p->one->sha1), | |
149 | sha1_to_hex(p->two->sha1)); | |
150 | continue; | |
151 | } | |
152 | mp = find_notes_merge_pair_pos(changes, len, obj, 1, &occupied); | |
153 | if (occupied) { | |
154 | /* We've found an addition/deletion pair */ | |
155 | assert(!hashcmp(mp->obj, obj)); | |
156 | if (is_null_sha1(p->one->sha1)) { /* addition */ | |
157 | assert(is_null_sha1(mp->remote)); | |
158 | hashcpy(mp->remote, p->two->sha1); | |
159 | } else if (is_null_sha1(p->two->sha1)) { /* deletion */ | |
160 | assert(is_null_sha1(mp->base)); | |
161 | hashcpy(mp->base, p->one->sha1); | |
162 | } else | |
163 | assert(!"Invalid existing change recorded"); | |
164 | } else { | |
165 | hashcpy(mp->obj, obj); | |
166 | hashcpy(mp->base, p->one->sha1); | |
167 | hashcpy(mp->local, uninitialized); | |
168 | hashcpy(mp->remote, p->two->sha1); | |
169 | len++; | |
170 | } | |
171 | trace_printf("\t\tStored remote change for %s: %.7s -> %.7s\n", | |
172 | sha1_to_hex(mp->obj), sha1_to_hex(mp->base), | |
173 | sha1_to_hex(mp->remote)); | |
174 | } | |
175 | diff_flush(&opt); | |
176 | diff_tree_release_paths(&opt); | |
177 | ||
178 | *num_changes = len; | |
179 | return changes; | |
180 | } | |
181 | ||
182 | static void diff_tree_local(struct notes_merge_options *o, | |
183 | struct notes_merge_pair *changes, int len, | |
184 | const unsigned char *base, | |
185 | const unsigned char *local) | |
186 | { | |
187 | struct diff_options opt; | |
188 | int i; | |
189 | ||
190 | trace_printf("\tdiff_tree_local(len = %i, base = %.7s, local = %.7s)\n", | |
191 | len, sha1_to_hex(base), sha1_to_hex(local)); | |
192 | ||
193 | diff_setup(&opt); | |
194 | DIFF_OPT_SET(&opt, RECURSIVE); | |
195 | opt.output_format = DIFF_FORMAT_NO_OUTPUT; | |
196 | if (diff_setup_done(&opt) < 0) | |
197 | die("diff_setup_done failed"); | |
198 | diff_tree_sha1(base, local, "", &opt); | |
199 | diffcore_std(&opt); | |
200 | ||
201 | for (i = 0; i < diff_queued_diff.nr; i++) { | |
202 | struct diff_filepair *p = diff_queued_diff.queue[i]; | |
203 | struct notes_merge_pair *mp; | |
204 | int match; | |
205 | unsigned char obj[20]; | |
206 | ||
207 | if (verify_notes_filepair(p, obj)) { | |
208 | trace_printf("\t\tCannot merge entry '%s' (%c): " | |
209 | "%.7s -> %.7s. Skipping!\n", p->one->path, | |
210 | p->status, sha1_to_hex(p->one->sha1), | |
211 | sha1_to_hex(p->two->sha1)); | |
212 | continue; | |
213 | } | |
214 | mp = find_notes_merge_pair_pos(changes, len, obj, 0, &match); | |
215 | if (!match) { | |
216 | trace_printf("\t\tIgnoring local-only change for %s: " | |
217 | "%.7s -> %.7s\n", sha1_to_hex(obj), | |
218 | sha1_to_hex(p->one->sha1), | |
219 | sha1_to_hex(p->two->sha1)); | |
220 | continue; | |
221 | } | |
222 | ||
223 | assert(!hashcmp(mp->obj, obj)); | |
224 | if (is_null_sha1(p->two->sha1)) { /* deletion */ | |
225 | /* | |
226 | * Either this is a true deletion (1), or it is part | |
227 | * of an A/D pair (2), or D/A pair (3): | |
228 | * | |
229 | * (1) mp->local is uninitialized; set it to null_sha1 | |
230 | * (2) mp->local is not uninitialized; don't touch it | |
231 | * (3) mp->local is uninitialized; set it to null_sha1 | |
232 | * (will be overwritten by following addition) | |
233 | */ | |
234 | if (!hashcmp(mp->local, uninitialized)) | |
235 | hashclr(mp->local); | |
236 | } else if (is_null_sha1(p->one->sha1)) { /* addition */ | |
237 | /* | |
238 | * Either this is a true addition (1), or it is part | |
239 | * of an A/D pair (2), or D/A pair (3): | |
240 | * | |
241 | * (1) mp->local is uninitialized; set to p->two->sha1 | |
242 | * (2) mp->local is uninitialized; set to p->two->sha1 | |
243 | * (3) mp->local is null_sha1; set to p->two->sha1 | |
244 | */ | |
245 | assert(is_null_sha1(mp->local) || | |
246 | !hashcmp(mp->local, uninitialized)); | |
247 | hashcpy(mp->local, p->two->sha1); | |
248 | } else { /* modification */ | |
249 | /* | |
250 | * This is a true modification. p->one->sha1 shall | |
251 | * match mp->base, and mp->local shall be uninitialized. | |
252 | * Set mp->local to p->two->sha1. | |
253 | */ | |
254 | assert(!hashcmp(p->one->sha1, mp->base)); | |
255 | assert(!hashcmp(mp->local, uninitialized)); | |
256 | hashcpy(mp->local, p->two->sha1); | |
257 | } | |
258 | trace_printf("\t\tStored local change for %s: %.7s -> %.7s\n", | |
259 | sha1_to_hex(mp->obj), sha1_to_hex(mp->base), | |
260 | sha1_to_hex(mp->local)); | |
261 | } | |
262 | diff_flush(&opt); | |
263 | diff_tree_release_paths(&opt); | |
264 | } | |
265 | ||
266 | static int merge_changes(struct notes_merge_options *o, | |
267 | struct notes_merge_pair *changes, int *num_changes, | |
268 | struct notes_tree *t) | |
269 | { | |
270 | int i, conflicts = 0; | |
271 | ||
272 | trace_printf("\tmerge_changes(num_changes = %i)\n", *num_changes); | |
273 | for (i = 0; i < *num_changes; i++) { | |
274 | struct notes_merge_pair *p = changes + i; | |
275 | trace_printf("\t\t%.7s: %.7s -> %.7s/%.7s\n", | |
276 | sha1_to_hex(p->obj), sha1_to_hex(p->base), | |
277 | sha1_to_hex(p->local), sha1_to_hex(p->remote)); | |
278 | ||
279 | if (!hashcmp(p->base, p->remote)) { | |
280 | /* no remote change; nothing to do */ | |
281 | trace_printf("\t\t\tskipping (no remote change)\n"); | |
282 | } else if (!hashcmp(p->local, p->remote)) { | |
283 | /* same change in local and remote; nothing to do */ | |
284 | trace_printf("\t\t\tskipping (local == remote)\n"); | |
285 | } else if (!hashcmp(p->local, uninitialized) || | |
286 | !hashcmp(p->local, p->base)) { | |
287 | /* no local change; adopt remote change */ | |
288 | trace_printf("\t\t\tno local change, adopted remote\n"); | |
289 | if (add_note(t, p->obj, p->remote, | |
290 | combine_notes_overwrite)) | |
291 | die("BUG: combine_notes_overwrite failed"); | |
292 | } else { | |
293 | /* need file-level merge between local and remote */ | |
294 | trace_printf("\t\t\tneed content-level merge\n"); | |
295 | conflicts += 1; /* TODO */ | |
296 | } | |
297 | } | |
298 | ||
299 | return conflicts; | |
300 | } | |
301 | ||
302 | static int merge_from_diffs(struct notes_merge_options *o, | |
303 | const unsigned char *base, | |
304 | const unsigned char *local, | |
305 | const unsigned char *remote, struct notes_tree *t) | |
306 | { | |
307 | struct notes_merge_pair *changes; | |
308 | int num_changes, conflicts; | |
309 | ||
310 | trace_printf("\tmerge_from_diffs(base = %.7s, local = %.7s, " | |
311 | "remote = %.7s)\n", sha1_to_hex(base), sha1_to_hex(local), | |
312 | sha1_to_hex(remote)); | |
313 | ||
314 | changes = diff_tree_remote(o, base, remote, &num_changes); | |
315 | diff_tree_local(o, changes, num_changes, base, local); | |
316 | ||
317 | conflicts = merge_changes(o, changes, &num_changes, t); | |
318 | free(changes); | |
319 | ||
320 | OUTPUT(o, 4, "Merge result: %i unmerged notes and a %s notes tree", | |
321 | conflicts, t->dirty ? "dirty" : "clean"); | |
322 | ||
323 | return conflicts ? -1 : 1; | |
324 | } | |
325 | ||
56881843 JH |
326 | void create_notes_commit(struct notes_tree *t, struct commit_list *parents, |
327 | const char *msg, unsigned char *result_sha1) | |
328 | { | |
329 | unsigned char tree_sha1[20]; | |
330 | ||
331 | assert(t->initialized); | |
332 | ||
333 | if (write_notes_tree(t, tree_sha1)) | |
334 | die("Failed to write notes tree to database"); | |
335 | ||
336 | if (!parents) { | |
337 | /* Deduce parent commit from t->ref */ | |
338 | unsigned char parent_sha1[20]; | |
339 | if (!read_ref(t->ref, parent_sha1)) { | |
340 | struct commit *parent = lookup_commit(parent_sha1); | |
341 | if (!parent || parse_commit(parent)) | |
342 | die("Failed to find/parse commit %s", t->ref); | |
343 | commit_list_insert(parent, &parents); | |
344 | } | |
345 | /* else: t->ref points to nothing, assume root/orphan commit */ | |
346 | } | |
347 | ||
348 | if (commit_tree(msg, tree_sha1, parents, result_sha1, NULL)) | |
349 | die("Failed to commit notes tree to database"); | |
350 | } | |
351 | ||
75ef3f4a | 352 | int notes_merge(struct notes_merge_options *o, |
2085b16a | 353 | struct notes_tree *local_tree, |
75ef3f4a JH |
354 | unsigned char *result_sha1) |
355 | { | |
356 | unsigned char local_sha1[20], remote_sha1[20]; | |
357 | struct commit *local, *remote; | |
358 | struct commit_list *bases = NULL; | |
2085b16a | 359 | const unsigned char *base_sha1, *base_tree_sha1; |
75ef3f4a JH |
360 | int result = 0; |
361 | ||
362 | assert(o->local_ref && o->remote_ref); | |
2085b16a | 363 | assert(!strcmp(o->local_ref, local_tree->ref)); |
75ef3f4a JH |
364 | hashclr(result_sha1); |
365 | ||
366 | trace_printf("notes_merge(o->local_ref = %s, o->remote_ref = %s)\n", | |
367 | o->local_ref, o->remote_ref); | |
368 | ||
369 | /* Dereference o->local_ref into local_sha1 */ | |
370 | if (!resolve_ref(o->local_ref, local_sha1, 0, NULL)) | |
371 | die("Failed to resolve local notes ref '%s'", o->local_ref); | |
372 | else if (!check_ref_format(o->local_ref) && is_null_sha1(local_sha1)) | |
373 | local = NULL; /* local_sha1 == null_sha1 indicates unborn ref */ | |
374 | else if (!(local = lookup_commit_reference(local_sha1))) | |
375 | die("Could not parse local commit %s (%s)", | |
376 | sha1_to_hex(local_sha1), o->local_ref); | |
377 | trace_printf("\tlocal commit: %.7s\n", sha1_to_hex(local_sha1)); | |
378 | ||
379 | /* Dereference o->remote_ref into remote_sha1 */ | |
380 | if (get_sha1(o->remote_ref, remote_sha1)) { | |
381 | /* | |
382 | * Failed to get remote_sha1. If o->remote_ref looks like an | |
383 | * unborn ref, perform the merge using an empty notes tree. | |
384 | */ | |
385 | if (!check_ref_format(o->remote_ref)) { | |
386 | hashclr(remote_sha1); | |
387 | remote = NULL; | |
388 | } else { | |
389 | die("Failed to resolve remote notes ref '%s'", | |
390 | o->remote_ref); | |
391 | } | |
392 | } else if (!(remote = lookup_commit_reference(remote_sha1))) { | |
393 | die("Could not parse remote commit %s (%s)", | |
394 | sha1_to_hex(remote_sha1), o->remote_ref); | |
395 | } | |
396 | trace_printf("\tremote commit: %.7s\n", sha1_to_hex(remote_sha1)); | |
397 | ||
398 | if (!local && !remote) | |
399 | die("Cannot merge empty notes ref (%s) into empty notes ref " | |
400 | "(%s)", o->remote_ref, o->local_ref); | |
401 | if (!local) { | |
402 | /* result == remote commit */ | |
403 | hashcpy(result_sha1, remote_sha1); | |
404 | goto found_result; | |
405 | } | |
406 | if (!remote) { | |
407 | /* result == local commit */ | |
408 | hashcpy(result_sha1, local_sha1); | |
409 | goto found_result; | |
410 | } | |
411 | assert(local && remote); | |
412 | ||
413 | /* Find merge bases */ | |
414 | bases = get_merge_bases(local, remote, 1); | |
415 | if (!bases) { | |
416 | base_sha1 = null_sha1; | |
2085b16a | 417 | base_tree_sha1 = (unsigned char *)EMPTY_TREE_SHA1_BIN; |
75ef3f4a JH |
418 | OUTPUT(o, 4, "No merge base found; doing history-less merge"); |
419 | } else if (!bases->next) { | |
420 | base_sha1 = bases->item->object.sha1; | |
2085b16a | 421 | base_tree_sha1 = bases->item->tree->object.sha1; |
75ef3f4a JH |
422 | OUTPUT(o, 4, "One merge base found (%.7s)", |
423 | sha1_to_hex(base_sha1)); | |
424 | } else { | |
425 | /* TODO: How to handle multiple merge-bases? */ | |
426 | base_sha1 = bases->item->object.sha1; | |
2085b16a | 427 | base_tree_sha1 = bases->item->tree->object.sha1; |
75ef3f4a JH |
428 | OUTPUT(o, 3, "Multiple merge bases found. Using the first " |
429 | "(%.7s)", sha1_to_hex(base_sha1)); | |
430 | } | |
431 | ||
432 | OUTPUT(o, 4, "Merging remote commit %.7s into local commit %.7s with " | |
433 | "merge-base %.7s", sha1_to_hex(remote->object.sha1), | |
434 | sha1_to_hex(local->object.sha1), sha1_to_hex(base_sha1)); | |
435 | ||
436 | if (!hashcmp(remote->object.sha1, base_sha1)) { | |
437 | /* Already merged; result == local commit */ | |
438 | OUTPUT(o, 2, "Already up-to-date!"); | |
439 | hashcpy(result_sha1, local->object.sha1); | |
440 | goto found_result; | |
441 | } | |
442 | if (!hashcmp(local->object.sha1, base_sha1)) { | |
443 | /* Fast-forward; result == remote commit */ | |
444 | OUTPUT(o, 2, "Fast-forward"); | |
445 | hashcpy(result_sha1, remote->object.sha1); | |
446 | goto found_result; | |
447 | } | |
448 | ||
2085b16a JH |
449 | result = merge_from_diffs(o, base_tree_sha1, local->tree->object.sha1, |
450 | remote->tree->object.sha1, local_tree); | |
451 | ||
452 | if (result > 0) { /* successful non-trivial merge */ | |
453 | /* Commit result */ | |
454 | struct commit_list *parents = NULL; | |
455 | commit_list_insert(remote, &parents); /* LIFO order */ | |
456 | commit_list_insert(local, &parents); | |
457 | create_notes_commit(local_tree, parents, o->commit_msg, | |
458 | result_sha1); | |
459 | } | |
75ef3f4a JH |
460 | |
461 | found_result: | |
462 | free_commit_list(bases); | |
463 | trace_printf("notes_merge(): result = %i, result_sha1 = %.7s\n", | |
464 | result, sha1_to_hex(result_sha1)); | |
465 | return result; | |
466 | } |