Documentation: Preliminary docs on 'git notes merge'
[git/git.git] / notes-merge.c
CommitLineData
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
9struct notes_merge_pair {
10 unsigned char obj[20], base[20], local[20], remote[20];
11};
12
75ef3f4a
JH
13void 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
27static 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
41static 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
62static 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
113static 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
117static 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
182static 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
3228e671
JH
266static int merge_one_change(struct notes_merge_options *o,
267 struct notes_merge_pair *p, struct notes_tree *t)
268{
269 /*
270 * Return 0 if change was resolved (and added to notes_tree),
271 * 1 if conflict
272 */
273 switch (o->strategy) {
274 case NOTES_MERGE_RESOLVE_MANUAL:
275 return 1;
276 case NOTES_MERGE_RESOLVE_OURS:
277 OUTPUT(o, 2, "Using local notes for %s", sha1_to_hex(p->obj));
278 /* nothing to do */
279 return 0;
280 case NOTES_MERGE_RESOLVE_THEIRS:
281 OUTPUT(o, 2, "Using remote notes for %s", sha1_to_hex(p->obj));
282 if (add_note(t, p->obj, p->remote, combine_notes_overwrite))
283 die("BUG: combine_notes_overwrite failed");
284 return 0;
285 case NOTES_MERGE_RESOLVE_UNION:
286 OUTPUT(o, 2, "Concatenating local and remote notes for %s",
287 sha1_to_hex(p->obj));
288 if (add_note(t, p->obj, p->remote, combine_notes_concatenate))
289 die("failed to concatenate notes "
290 "(combine_notes_concatenate)");
291 return 0;
292 }
293 die("Unknown strategy (%i).", o->strategy);
294}
295
2085b16a
JH
296static int merge_changes(struct notes_merge_options *o,
297 struct notes_merge_pair *changes, int *num_changes,
298 struct notes_tree *t)
299{
300 int i, conflicts = 0;
301
302 trace_printf("\tmerge_changes(num_changes = %i)\n", *num_changes);
303 for (i = 0; i < *num_changes; i++) {
304 struct notes_merge_pair *p = changes + i;
305 trace_printf("\t\t%.7s: %.7s -> %.7s/%.7s\n",
306 sha1_to_hex(p->obj), sha1_to_hex(p->base),
307 sha1_to_hex(p->local), sha1_to_hex(p->remote));
308
309 if (!hashcmp(p->base, p->remote)) {
310 /* no remote change; nothing to do */
311 trace_printf("\t\t\tskipping (no remote change)\n");
312 } else if (!hashcmp(p->local, p->remote)) {
313 /* same change in local and remote; nothing to do */
314 trace_printf("\t\t\tskipping (local == remote)\n");
315 } else if (!hashcmp(p->local, uninitialized) ||
316 !hashcmp(p->local, p->base)) {
317 /* no local change; adopt remote change */
318 trace_printf("\t\t\tno local change, adopted remote\n");
319 if (add_note(t, p->obj, p->remote,
320 combine_notes_overwrite))
321 die("BUG: combine_notes_overwrite failed");
322 } else {
323 /* need file-level merge between local and remote */
324 trace_printf("\t\t\tneed content-level merge\n");
3228e671 325 conflicts += merge_one_change(o, p, t);
2085b16a
JH
326 }
327 }
328
329 return conflicts;
330}
331
332static int merge_from_diffs(struct notes_merge_options *o,
333 const unsigned char *base,
334 const unsigned char *local,
335 const unsigned char *remote, struct notes_tree *t)
336{
337 struct notes_merge_pair *changes;
338 int num_changes, conflicts;
339
340 trace_printf("\tmerge_from_diffs(base = %.7s, local = %.7s, "
341 "remote = %.7s)\n", sha1_to_hex(base), sha1_to_hex(local),
342 sha1_to_hex(remote));
343
344 changes = diff_tree_remote(o, base, remote, &num_changes);
345 diff_tree_local(o, changes, num_changes, base, local);
346
347 conflicts = merge_changes(o, changes, &num_changes, t);
348 free(changes);
349
350 OUTPUT(o, 4, "Merge result: %i unmerged notes and a %s notes tree",
351 conflicts, t->dirty ? "dirty" : "clean");
352
353 return conflicts ? -1 : 1;
354}
355
56881843
JH
356void create_notes_commit(struct notes_tree *t, struct commit_list *parents,
357 const char *msg, unsigned char *result_sha1)
358{
359 unsigned char tree_sha1[20];
360
361 assert(t->initialized);
362
363 if (write_notes_tree(t, tree_sha1))
364 die("Failed to write notes tree to database");
365
366 if (!parents) {
367 /* Deduce parent commit from t->ref */
368 unsigned char parent_sha1[20];
369 if (!read_ref(t->ref, parent_sha1)) {
370 struct commit *parent = lookup_commit(parent_sha1);
371 if (!parent || parse_commit(parent))
372 die("Failed to find/parse commit %s", t->ref);
373 commit_list_insert(parent, &parents);
374 }
375 /* else: t->ref points to nothing, assume root/orphan commit */
376 }
377
378 if (commit_tree(msg, tree_sha1, parents, result_sha1, NULL))
379 die("Failed to commit notes tree to database");
380}
381
75ef3f4a 382int notes_merge(struct notes_merge_options *o,
2085b16a 383 struct notes_tree *local_tree,
75ef3f4a
JH
384 unsigned char *result_sha1)
385{
386 unsigned char local_sha1[20], remote_sha1[20];
387 struct commit *local, *remote;
388 struct commit_list *bases = NULL;
2085b16a 389 const unsigned char *base_sha1, *base_tree_sha1;
75ef3f4a
JH
390 int result = 0;
391
392 assert(o->local_ref && o->remote_ref);
2085b16a 393 assert(!strcmp(o->local_ref, local_tree->ref));
75ef3f4a
JH
394 hashclr(result_sha1);
395
396 trace_printf("notes_merge(o->local_ref = %s, o->remote_ref = %s)\n",
397 o->local_ref, o->remote_ref);
398
399 /* Dereference o->local_ref into local_sha1 */
400 if (!resolve_ref(o->local_ref, local_sha1, 0, NULL))
401 die("Failed to resolve local notes ref '%s'", o->local_ref);
402 else if (!check_ref_format(o->local_ref) && is_null_sha1(local_sha1))
403 local = NULL; /* local_sha1 == null_sha1 indicates unborn ref */
404 else if (!(local = lookup_commit_reference(local_sha1)))
405 die("Could not parse local commit %s (%s)",
406 sha1_to_hex(local_sha1), o->local_ref);
407 trace_printf("\tlocal commit: %.7s\n", sha1_to_hex(local_sha1));
408
409 /* Dereference o->remote_ref into remote_sha1 */
410 if (get_sha1(o->remote_ref, remote_sha1)) {
411 /*
412 * Failed to get remote_sha1. If o->remote_ref looks like an
413 * unborn ref, perform the merge using an empty notes tree.
414 */
415 if (!check_ref_format(o->remote_ref)) {
416 hashclr(remote_sha1);
417 remote = NULL;
418 } else {
419 die("Failed to resolve remote notes ref '%s'",
420 o->remote_ref);
421 }
422 } else if (!(remote = lookup_commit_reference(remote_sha1))) {
423 die("Could not parse remote commit %s (%s)",
424 sha1_to_hex(remote_sha1), o->remote_ref);
425 }
426 trace_printf("\tremote commit: %.7s\n", sha1_to_hex(remote_sha1));
427
428 if (!local && !remote)
429 die("Cannot merge empty notes ref (%s) into empty notes ref "
430 "(%s)", o->remote_ref, o->local_ref);
431 if (!local) {
432 /* result == remote commit */
433 hashcpy(result_sha1, remote_sha1);
434 goto found_result;
435 }
436 if (!remote) {
437 /* result == local commit */
438 hashcpy(result_sha1, local_sha1);
439 goto found_result;
440 }
441 assert(local && remote);
442
443 /* Find merge bases */
444 bases = get_merge_bases(local, remote, 1);
445 if (!bases) {
446 base_sha1 = null_sha1;
2085b16a 447 base_tree_sha1 = (unsigned char *)EMPTY_TREE_SHA1_BIN;
75ef3f4a
JH
448 OUTPUT(o, 4, "No merge base found; doing history-less merge");
449 } else if (!bases->next) {
450 base_sha1 = bases->item->object.sha1;
2085b16a 451 base_tree_sha1 = bases->item->tree->object.sha1;
75ef3f4a
JH
452 OUTPUT(o, 4, "One merge base found (%.7s)",
453 sha1_to_hex(base_sha1));
454 } else {
455 /* TODO: How to handle multiple merge-bases? */
456 base_sha1 = bases->item->object.sha1;
2085b16a 457 base_tree_sha1 = bases->item->tree->object.sha1;
75ef3f4a
JH
458 OUTPUT(o, 3, "Multiple merge bases found. Using the first "
459 "(%.7s)", sha1_to_hex(base_sha1));
460 }
461
462 OUTPUT(o, 4, "Merging remote commit %.7s into local commit %.7s with "
463 "merge-base %.7s", sha1_to_hex(remote->object.sha1),
464 sha1_to_hex(local->object.sha1), sha1_to_hex(base_sha1));
465
466 if (!hashcmp(remote->object.sha1, base_sha1)) {
467 /* Already merged; result == local commit */
468 OUTPUT(o, 2, "Already up-to-date!");
469 hashcpy(result_sha1, local->object.sha1);
470 goto found_result;
471 }
472 if (!hashcmp(local->object.sha1, base_sha1)) {
473 /* Fast-forward; result == remote commit */
474 OUTPUT(o, 2, "Fast-forward");
475 hashcpy(result_sha1, remote->object.sha1);
476 goto found_result;
477 }
478
2085b16a
JH
479 result = merge_from_diffs(o, base_tree_sha1, local->tree->object.sha1,
480 remote->tree->object.sha1, local_tree);
481
482 if (result > 0) { /* successful non-trivial merge */
483 /* Commit result */
484 struct commit_list *parents = NULL;
485 commit_list_insert(remote, &parents); /* LIFO order */
486 commit_list_insert(local, &parents);
487 create_notes_commit(local_tree, parents, o->commit_msg,
488 result_sha1);
489 }
75ef3f4a
JH
490
491found_result:
492 free_commit_list(bases);
493 trace_printf("notes_merge(): result = %i, result_sha1 = %.7s\n",
494 result, sha1_to_hex(result_sha1));
495 return result;
496}