6 #include "xdiff-interface.h"
10 #include "notes-merge.h"
12 struct notes_merge_pair
{
13 unsigned char obj
[20], base
[20], local
[20], remote
[20];
16 void init_notes_merge_options(struct notes_merge_options
*o
)
18 memset(o
, 0, sizeof(struct notes_merge_options
));
19 o
->verbosity
= NOTES_MERGE_VERBOSITY_DEFAULT
;
22 #define OUTPUT(o, v, ...) \
24 if ((o)->verbosity >= (v)) { \
25 printf(__VA_ARGS__); \
30 static int path_to_sha1(const char *path
, unsigned char *sha1
)
34 while (*path
&& i
< 40) {
36 hex_sha1
[i
++] = *path
;
41 return get_sha1_hex(hex_sha1
, sha1
);
44 static int verify_notes_filepair(struct diff_filepair
*p
, unsigned char *sha1
)
47 case DIFF_STATUS_MODIFIED
:
48 assert(p
->one
->mode
== p
->two
->mode
);
49 assert(!is_null_sha1(p
->one
->sha1
));
50 assert(!is_null_sha1(p
->two
->sha1
));
52 case DIFF_STATUS_ADDED
:
53 assert(is_null_sha1(p
->one
->sha1
));
55 case DIFF_STATUS_DELETED
:
56 assert(is_null_sha1(p
->two
->sha1
));
61 assert(!strcmp(p
->one
->path
, p
->two
->path
));
62 return path_to_sha1(p
->one
->path
, sha1
);
65 static struct notes_merge_pair
*find_notes_merge_pair_pos(
66 struct notes_merge_pair
*list
, int len
, unsigned char *obj
,
67 int insert_new
, int *occupied
)
70 * Both diff_tree_remote() and diff_tree_local() tend to process
71 * merge_pairs in ascending order. Therefore, cache last returned
72 * index, and search sequentially from there until the appropriate
75 * Since inserts only happen from diff_tree_remote() (which mainly
76 * _appends_), we don't care that inserting into the middle of the
77 * list is expensive (using memmove()).
79 static int last_index
;
80 int i
= last_index
< len
? last_index
: len
- 1;
81 int prev_cmp
= 0, cmp
= -1;
82 while (i
>= 0 && i
< len
) {
83 cmp
= hashcmp(obj
, list
[i
].obj
);
84 if (!cmp
) /* obj belongs @ i */
86 else if (cmp
< 0 && prev_cmp
<= 0) /* obj belongs < i */
88 else if (cmp
< 0) /* obj belongs between i-1 and i */
90 else if (cmp
> 0 && prev_cmp
>= 0) /* obj belongs > i */
92 else /* if (cmp > 0) */ { /* obj belongs between i and i+1 */
100 /* obj belongs at, or immediately preceding, index i (0 <= i <= len) */
106 if (insert_new
&& i
< len
) {
107 memmove(list
+ i
+ 1, list
+ i
,
108 (len
- i
) * sizeof(struct notes_merge_pair
));
109 memset(list
+ i
, 0, sizeof(struct notes_merge_pair
));
116 static unsigned char uninitialized
[20] =
117 "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" \
118 "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff";
120 static struct notes_merge_pair
*diff_tree_remote(struct notes_merge_options
*o
,
121 const unsigned char *base
,
122 const unsigned char *remote
,
125 struct diff_options opt
;
126 struct notes_merge_pair
*changes
;
129 trace_printf("\tdiff_tree_remote(base = %.7s, remote = %.7s)\n",
130 sha1_to_hex(base
), sha1_to_hex(remote
));
133 DIFF_OPT_SET(&opt
, RECURSIVE
);
134 opt
.output_format
= DIFF_FORMAT_NO_OUTPUT
;
135 if (diff_setup_done(&opt
) < 0)
136 die("diff_setup_done failed");
137 diff_tree_sha1(base
, remote
, "", &opt
);
140 changes
= xcalloc(diff_queued_diff
.nr
, sizeof(struct notes_merge_pair
));
142 for (i
= 0; i
< diff_queued_diff
.nr
; i
++) {
143 struct diff_filepair
*p
= diff_queued_diff
.queue
[i
];
144 struct notes_merge_pair
*mp
;
146 unsigned char obj
[20];
148 if (verify_notes_filepair(p
, obj
)) {
149 trace_printf("\t\tCannot merge entry '%s' (%c): "
150 "%.7s -> %.7s. Skipping!\n", p
->one
->path
,
151 p
->status
, sha1_to_hex(p
->one
->sha1
),
152 sha1_to_hex(p
->two
->sha1
));
155 mp
= find_notes_merge_pair_pos(changes
, len
, obj
, 1, &occupied
);
157 /* We've found an addition/deletion pair */
158 assert(!hashcmp(mp
->obj
, obj
));
159 if (is_null_sha1(p
->one
->sha1
)) { /* addition */
160 assert(is_null_sha1(mp
->remote
));
161 hashcpy(mp
->remote
, p
->two
->sha1
);
162 } else if (is_null_sha1(p
->two
->sha1
)) { /* deletion */
163 assert(is_null_sha1(mp
->base
));
164 hashcpy(mp
->base
, p
->one
->sha1
);
166 assert(!"Invalid existing change recorded");
168 hashcpy(mp
->obj
, obj
);
169 hashcpy(mp
->base
, p
->one
->sha1
);
170 hashcpy(mp
->local
, uninitialized
);
171 hashcpy(mp
->remote
, p
->two
->sha1
);
174 trace_printf("\t\tStored remote change for %s: %.7s -> %.7s\n",
175 sha1_to_hex(mp
->obj
), sha1_to_hex(mp
->base
),
176 sha1_to_hex(mp
->remote
));
179 diff_tree_release_paths(&opt
);
185 static void diff_tree_local(struct notes_merge_options
*o
,
186 struct notes_merge_pair
*changes
, int len
,
187 const unsigned char *base
,
188 const unsigned char *local
)
190 struct diff_options opt
;
193 trace_printf("\tdiff_tree_local(len = %i, base = %.7s, local = %.7s)\n",
194 len
, sha1_to_hex(base
), sha1_to_hex(local
));
197 DIFF_OPT_SET(&opt
, RECURSIVE
);
198 opt
.output_format
= DIFF_FORMAT_NO_OUTPUT
;
199 if (diff_setup_done(&opt
) < 0)
200 die("diff_setup_done failed");
201 diff_tree_sha1(base
, local
, "", &opt
);
204 for (i
= 0; i
< diff_queued_diff
.nr
; i
++) {
205 struct diff_filepair
*p
= diff_queued_diff
.queue
[i
];
206 struct notes_merge_pair
*mp
;
208 unsigned char obj
[20];
210 if (verify_notes_filepair(p
, obj
)) {
211 trace_printf("\t\tCannot merge entry '%s' (%c): "
212 "%.7s -> %.7s. Skipping!\n", p
->one
->path
,
213 p
->status
, sha1_to_hex(p
->one
->sha1
),
214 sha1_to_hex(p
->two
->sha1
));
217 mp
= find_notes_merge_pair_pos(changes
, len
, obj
, 0, &match
);
219 trace_printf("\t\tIgnoring local-only change for %s: "
220 "%.7s -> %.7s\n", sha1_to_hex(obj
),
221 sha1_to_hex(p
->one
->sha1
),
222 sha1_to_hex(p
->two
->sha1
));
226 assert(!hashcmp(mp
->obj
, obj
));
227 if (is_null_sha1(p
->two
->sha1
)) { /* deletion */
229 * Either this is a true deletion (1), or it is part
230 * of an A/D pair (2), or D/A pair (3):
232 * (1) mp->local is uninitialized; set it to null_sha1
233 * (2) mp->local is not uninitialized; don't touch it
234 * (3) mp->local is uninitialized; set it to null_sha1
235 * (will be overwritten by following addition)
237 if (!hashcmp(mp
->local
, uninitialized
))
239 } else if (is_null_sha1(p
->one
->sha1
)) { /* addition */
241 * Either this is a true addition (1), or it is part
242 * of an A/D pair (2), or D/A pair (3):
244 * (1) mp->local is uninitialized; set to p->two->sha1
245 * (2) mp->local is uninitialized; set to p->two->sha1
246 * (3) mp->local is null_sha1; set to p->two->sha1
248 assert(is_null_sha1(mp
->local
) ||
249 !hashcmp(mp
->local
, uninitialized
));
250 hashcpy(mp
->local
, p
->two
->sha1
);
251 } else { /* modification */
253 * This is a true modification. p->one->sha1 shall
254 * match mp->base, and mp->local shall be uninitialized.
255 * Set mp->local to p->two->sha1.
257 assert(!hashcmp(p
->one
->sha1
, mp
->base
));
258 assert(!hashcmp(mp
->local
, uninitialized
));
259 hashcpy(mp
->local
, p
->two
->sha1
);
261 trace_printf("\t\tStored local change for %s: %.7s -> %.7s\n",
262 sha1_to_hex(mp
->obj
), sha1_to_hex(mp
->base
),
263 sha1_to_hex(mp
->local
));
266 diff_tree_release_paths(&opt
);
269 static void check_notes_merge_worktree(struct notes_merge_options
*o
)
271 if (!o
->has_worktree
) {
273 * Must establish NOTES_MERGE_WORKTREE.
274 * Abort if NOTES_MERGE_WORKTREE already exists
276 if (file_exists(git_path(NOTES_MERGE_WORKTREE
))) {
277 if (advice_resolve_conflict
)
278 die("You have not concluded your previous "
279 "notes merge (%s exists).\nPlease, use "
280 "'git notes merge --commit' or 'git notes "
281 "merge --reset' to commit/abort the "
282 "previous merge before you start a new "
283 "notes merge.", git_path("NOTES_MERGE_*"));
285 die("You have not concluded your notes merge "
286 "(%s exists).", git_path("NOTES_MERGE_*"));
289 if (safe_create_leading_directories(git_path(
290 NOTES_MERGE_WORKTREE
"/.test")))
291 die_errno("unable to create directory %s",
292 git_path(NOTES_MERGE_WORKTREE
));
294 } else if (!file_exists(git_path(NOTES_MERGE_WORKTREE
)))
295 /* NOTES_MERGE_WORKTREE should already be established */
296 die("missing '%s'. This should not happen",
297 git_path(NOTES_MERGE_WORKTREE
));
300 static void write_buf_to_worktree(const unsigned char *obj
,
301 const char *buf
, unsigned long size
)
304 char *path
= git_path(NOTES_MERGE_WORKTREE
"/%s", sha1_to_hex(obj
));
305 if (safe_create_leading_directories(path
))
306 die_errno("unable to create directory for '%s'", path
);
307 if (file_exists(path
))
308 die("found existing file at '%s'", path
);
310 fd
= open(path
, O_WRONLY
| O_TRUNC
| O_CREAT
, 0666);
312 die_errno("failed to open '%s'", path
);
315 long ret
= write_in_full(fd
, buf
, size
);
320 die_errno("notes-merge");
322 die("notes-merge: disk full?");
331 static void write_note_to_worktree(const unsigned char *obj
,
332 const unsigned char *note
)
334 enum object_type type
;
336 void *buf
= read_sha1_file(note
, &type
, &size
);
339 die("cannot read note %s for object %s",
340 sha1_to_hex(note
), sha1_to_hex(obj
));
341 if (type
!= OBJ_BLOB
)
342 die("blob expected in note %s for object %s",
343 sha1_to_hex(note
), sha1_to_hex(obj
));
344 write_buf_to_worktree(obj
, buf
, size
);
348 static int ll_merge_in_worktree(struct notes_merge_options
*o
,
349 struct notes_merge_pair
*p
)
351 mmbuffer_t result_buf
;
352 mmfile_t base
, local
, remote
;
355 read_mmblob(&base
, p
->base
);
356 read_mmblob(&local
, p
->local
);
357 read_mmblob(&remote
, p
->remote
);
359 status
= ll_merge(&result_buf
, sha1_to_hex(p
->obj
), &base
, NULL
,
360 &local
, o
->local_ref
, &remote
, o
->remote_ref
, 0);
366 if ((status
< 0) || !result_buf
.ptr
)
367 die("Failed to execute internal merge");
369 write_buf_to_worktree(p
->obj
, result_buf
.ptr
, result_buf
.size
);
370 free(result_buf
.ptr
);
375 static int merge_one_change_manual(struct notes_merge_options
*o
,
376 struct notes_merge_pair
*p
,
377 struct notes_tree
*t
)
379 const char *lref
= o
->local_ref
? o
->local_ref
: "local version";
380 const char *rref
= o
->remote_ref
? o
->remote_ref
: "remote version";
382 trace_printf("\t\t\tmerge_one_change_manual(obj = %.7s, base = %.7s, "
383 "local = %.7s, remote = %.7s)\n",
384 sha1_to_hex(p
->obj
), sha1_to_hex(p
->base
),
385 sha1_to_hex(p
->local
), sha1_to_hex(p
->remote
));
387 OUTPUT(o
, 2, "Auto-merging notes for %s", sha1_to_hex(p
->obj
));
388 check_notes_merge_worktree(o
);
389 if (is_null_sha1(p
->local
)) {
390 /* D/F conflict, checkout p->remote */
391 assert(!is_null_sha1(p
->remote
));
392 OUTPUT(o
, 1, "CONFLICT (delete/modify): Notes for object %s "
393 "deleted in %s and modified in %s. Version from %s "
394 "left in tree.", sha1_to_hex(p
->obj
), lref
, rref
, rref
);
395 write_note_to_worktree(p
->obj
, p
->remote
);
396 } else if (is_null_sha1(p
->remote
)) {
397 /* D/F conflict, checkout p->local */
398 assert(!is_null_sha1(p
->local
));
399 OUTPUT(o
, 1, "CONFLICT (delete/modify): Notes for object %s "
400 "deleted in %s and modified in %s. Version from %s "
401 "left in tree.", sha1_to_hex(p
->obj
), rref
, lref
, lref
);
402 write_note_to_worktree(p
->obj
, p
->local
);
404 /* "regular" conflict, checkout result of ll_merge() */
405 const char *reason
= "content";
406 if (is_null_sha1(p
->base
))
408 assert(!is_null_sha1(p
->local
));
409 assert(!is_null_sha1(p
->remote
));
410 OUTPUT(o
, 1, "CONFLICT (%s): Merge conflict in notes for "
411 "object %s", reason
, sha1_to_hex(p
->obj
));
412 ll_merge_in_worktree(o
, p
);
415 trace_printf("\t\t\tremoving from partial merge result\n");
416 remove_note(t
, p
->obj
);
421 static int merge_one_change(struct notes_merge_options
*o
,
422 struct notes_merge_pair
*p
, struct notes_tree
*t
)
425 * Return 0 if change is successfully resolved (stored in notes_tree).
426 * Return 1 is change results in a conflict (NOT stored in notes_tree,
427 * but instead written to NOTES_MERGE_WORKTREE with conflict markers).
429 switch (o
->strategy
) {
430 case NOTES_MERGE_RESOLVE_MANUAL
:
431 return merge_one_change_manual(o
, p
, t
);
432 case NOTES_MERGE_RESOLVE_OURS
:
433 OUTPUT(o
, 2, "Using local notes for %s", sha1_to_hex(p
->obj
));
436 case NOTES_MERGE_RESOLVE_THEIRS
:
437 OUTPUT(o
, 2, "Using remote notes for %s", sha1_to_hex(p
->obj
));
438 if (add_note(t
, p
->obj
, p
->remote
, combine_notes_overwrite
))
439 die("BUG: combine_notes_overwrite failed");
441 case NOTES_MERGE_RESOLVE_UNION
:
442 OUTPUT(o
, 2, "Concatenating local and remote notes for %s",
443 sha1_to_hex(p
->obj
));
444 if (add_note(t
, p
->obj
, p
->remote
, combine_notes_concatenate
))
445 die("failed to concatenate notes "
446 "(combine_notes_concatenate)");
449 die("Unknown strategy (%i).", o
->strategy
);
452 static int merge_changes(struct notes_merge_options
*o
,
453 struct notes_merge_pair
*changes
, int *num_changes
,
454 struct notes_tree
*t
)
456 int i
, conflicts
= 0;
458 trace_printf("\tmerge_changes(num_changes = %i)\n", *num_changes
);
459 for (i
= 0; i
< *num_changes
; i
++) {
460 struct notes_merge_pair
*p
= changes
+ i
;
461 trace_printf("\t\t%.7s: %.7s -> %.7s/%.7s\n",
462 sha1_to_hex(p
->obj
), sha1_to_hex(p
->base
),
463 sha1_to_hex(p
->local
), sha1_to_hex(p
->remote
));
465 if (!hashcmp(p
->base
, p
->remote
)) {
466 /* no remote change; nothing to do */
467 trace_printf("\t\t\tskipping (no remote change)\n");
468 } else if (!hashcmp(p
->local
, p
->remote
)) {
469 /* same change in local and remote; nothing to do */
470 trace_printf("\t\t\tskipping (local == remote)\n");
471 } else if (!hashcmp(p
->local
, uninitialized
) ||
472 !hashcmp(p
->local
, p
->base
)) {
473 /* no local change; adopt remote change */
474 trace_printf("\t\t\tno local change, adopted remote\n");
475 if (add_note(t
, p
->obj
, p
->remote
,
476 combine_notes_overwrite
))
477 die("BUG: combine_notes_overwrite failed");
479 /* need file-level merge between local and remote */
480 trace_printf("\t\t\tneed content-level merge\n");
481 conflicts
+= merge_one_change(o
, p
, t
);
488 static int merge_from_diffs(struct notes_merge_options
*o
,
489 const unsigned char *base
,
490 const unsigned char *local
,
491 const unsigned char *remote
, struct notes_tree
*t
)
493 struct notes_merge_pair
*changes
;
494 int num_changes
, conflicts
;
496 trace_printf("\tmerge_from_diffs(base = %.7s, local = %.7s, "
497 "remote = %.7s)\n", sha1_to_hex(base
), sha1_to_hex(local
),
498 sha1_to_hex(remote
));
500 changes
= diff_tree_remote(o
, base
, remote
, &num_changes
);
501 diff_tree_local(o
, changes
, num_changes
, base
, local
);
503 conflicts
= merge_changes(o
, changes
, &num_changes
, t
);
506 OUTPUT(o
, 4, "Merge result: %i unmerged notes and a %s notes tree",
507 conflicts
, t
->dirty
? "dirty" : "clean");
509 return conflicts
? -1 : 1;
512 void create_notes_commit(struct notes_tree
*t
, struct commit_list
*parents
,
513 const char *msg
, unsigned char *result_sha1
)
515 unsigned char tree_sha1
[20];
517 assert(t
->initialized
);
519 if (write_notes_tree(t
, tree_sha1
))
520 die("Failed to write notes tree to database");
523 /* Deduce parent commit from t->ref */
524 unsigned char parent_sha1
[20];
525 if (!read_ref(t
->ref
, parent_sha1
)) {
526 struct commit
*parent
= lookup_commit(parent_sha1
);
527 if (!parent
|| parse_commit(parent
))
528 die("Failed to find/parse commit %s", t
->ref
);
529 commit_list_insert(parent
, &parents
);
531 /* else: t->ref points to nothing, assume root/orphan commit */
534 if (commit_tree(msg
, tree_sha1
, parents
, result_sha1
, NULL
))
535 die("Failed to commit notes tree to database");
538 int notes_merge(struct notes_merge_options
*o
,
539 struct notes_tree
*local_tree
,
540 unsigned char *result_sha1
)
542 unsigned char local_sha1
[20], remote_sha1
[20];
543 struct commit
*local
, *remote
;
544 struct commit_list
*bases
= NULL
;
545 const unsigned char *base_sha1
, *base_tree_sha1
;
548 assert(o
->local_ref
&& o
->remote_ref
);
549 assert(!strcmp(o
->local_ref
, local_tree
->ref
));
550 hashclr(result_sha1
);
552 trace_printf("notes_merge(o->local_ref = %s, o->remote_ref = %s)\n",
553 o
->local_ref
, o
->remote_ref
);
555 /* Dereference o->local_ref into local_sha1 */
556 if (!resolve_ref(o
->local_ref
, local_sha1
, 0, NULL
))
557 die("Failed to resolve local notes ref '%s'", o
->local_ref
);
558 else if (!check_ref_format(o
->local_ref
) && is_null_sha1(local_sha1
))
559 local
= NULL
; /* local_sha1 == null_sha1 indicates unborn ref */
560 else if (!(local
= lookup_commit_reference(local_sha1
)))
561 die("Could not parse local commit %s (%s)",
562 sha1_to_hex(local_sha1
), o
->local_ref
);
563 trace_printf("\tlocal commit: %.7s\n", sha1_to_hex(local_sha1
));
565 /* Dereference o->remote_ref into remote_sha1 */
566 if (get_sha1(o
->remote_ref
, remote_sha1
)) {
568 * Failed to get remote_sha1. If o->remote_ref looks like an
569 * unborn ref, perform the merge using an empty notes tree.
571 if (!check_ref_format(o
->remote_ref
)) {
572 hashclr(remote_sha1
);
575 die("Failed to resolve remote notes ref '%s'",
578 } else if (!(remote
= lookup_commit_reference(remote_sha1
))) {
579 die("Could not parse remote commit %s (%s)",
580 sha1_to_hex(remote_sha1
), o
->remote_ref
);
582 trace_printf("\tremote commit: %.7s\n", sha1_to_hex(remote_sha1
));
584 if (!local
&& !remote
)
585 die("Cannot merge empty notes ref (%s) into empty notes ref "
586 "(%s)", o
->remote_ref
, o
->local_ref
);
588 /* result == remote commit */
589 hashcpy(result_sha1
, remote_sha1
);
593 /* result == local commit */
594 hashcpy(result_sha1
, local_sha1
);
597 assert(local
&& remote
);
599 /* Find merge bases */
600 bases
= get_merge_bases(local
, remote
, 1);
602 base_sha1
= null_sha1
;
603 base_tree_sha1
= (unsigned char *)EMPTY_TREE_SHA1_BIN
;
604 OUTPUT(o
, 4, "No merge base found; doing history-less merge");
605 } else if (!bases
->next
) {
606 base_sha1
= bases
->item
->object
.sha1
;
607 base_tree_sha1
= bases
->item
->tree
->object
.sha1
;
608 OUTPUT(o
, 4, "One merge base found (%.7s)",
609 sha1_to_hex(base_sha1
));
611 /* TODO: How to handle multiple merge-bases? */
612 base_sha1
= bases
->item
->object
.sha1
;
613 base_tree_sha1
= bases
->item
->tree
->object
.sha1
;
614 OUTPUT(o
, 3, "Multiple merge bases found. Using the first "
615 "(%.7s)", sha1_to_hex(base_sha1
));
618 OUTPUT(o
, 4, "Merging remote commit %.7s into local commit %.7s with "
619 "merge-base %.7s", sha1_to_hex(remote
->object
.sha1
),
620 sha1_to_hex(local
->object
.sha1
), sha1_to_hex(base_sha1
));
622 if (!hashcmp(remote
->object
.sha1
, base_sha1
)) {
623 /* Already merged; result == local commit */
624 OUTPUT(o
, 2, "Already up-to-date!");
625 hashcpy(result_sha1
, local
->object
.sha1
);
628 if (!hashcmp(local
->object
.sha1
, base_sha1
)) {
629 /* Fast-forward; result == remote commit */
630 OUTPUT(o
, 2, "Fast-forward");
631 hashcpy(result_sha1
, remote
->object
.sha1
);
635 result
= merge_from_diffs(o
, base_tree_sha1
, local
->tree
->object
.sha1
,
636 remote
->tree
->object
.sha1
, local_tree
);
638 if (result
!= 0) { /* non-trivial merge (with or without conflicts) */
639 /* Commit (partial) result */
640 struct commit_list
*parents
= NULL
;
641 commit_list_insert(remote
, &parents
); /* LIFO order */
642 commit_list_insert(local
, &parents
);
643 create_notes_commit(local_tree
, parents
, o
->commit_msg
,
648 free_commit_list(bases
);
649 trace_printf("notes_merge(): result = %i, result_sha1 = %.7s\n",
650 result
, sha1_to_hex(result_sha1
));