7 #include "notes-merge.h"
9 struct notes_merge_pair
{
10 unsigned char obj
[20], base
[20], local
[20], remote
[20];
13 void init_notes_merge_options(struct notes_merge_options
*o
)
15 memset(o
, 0, sizeof(struct notes_merge_options
));
16 o
->verbosity
= NOTES_MERGE_VERBOSITY_DEFAULT
;
19 #define OUTPUT(o, v, ...) \
21 if ((o)->verbosity >= (v)) { \
22 printf(__VA_ARGS__); \
27 static int path_to_sha1(const char *path
, unsigned char *sha1
)
31 while (*path
&& i
< 40) {
33 hex_sha1
[i
++] = *path
;
38 return get_sha1_hex(hex_sha1
, sha1
);
41 static int verify_notes_filepair(struct diff_filepair
*p
, unsigned char *sha1
)
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
));
49 case DIFF_STATUS_ADDED
:
50 assert(is_null_sha1(p
->one
->sha1
));
52 case DIFF_STATUS_DELETED
:
53 assert(is_null_sha1(p
->two
->sha1
));
58 assert(!strcmp(p
->one
->path
, p
->two
->path
));
59 return path_to_sha1(p
->one
->path
, sha1
);
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
)
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
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()).
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 */
83 else if (cmp
< 0 && prev_cmp
<= 0) /* obj belongs < i */
85 else if (cmp
< 0) /* obj belongs between i-1 and i */
87 else if (cmp
> 0 && prev_cmp
>= 0) /* obj belongs > i */
89 else /* if (cmp > 0) */ { /* obj belongs between i and i+1 */
97 /* obj belongs at, or immediately preceding, index i (0 <= i <= len) */
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
));
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";
117 static struct notes_merge_pair
*diff_tree_remote(struct notes_merge_options
*o
,
118 const unsigned char *base
,
119 const unsigned char *remote
,
122 struct diff_options opt
;
123 struct notes_merge_pair
*changes
;
126 trace_printf("\tdiff_tree_remote(base = %.7s, remote = %.7s)\n",
127 sha1_to_hex(base
), sha1_to_hex(remote
));
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
);
137 changes
= xcalloc(diff_queued_diff
.nr
, sizeof(struct notes_merge_pair
));
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
;
143 unsigned char obj
[20];
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
));
152 mp
= find_notes_merge_pair_pos(changes
, len
, obj
, 1, &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
);
163 assert(!"Invalid existing change recorded");
165 hashcpy(mp
->obj
, obj
);
166 hashcpy(mp
->base
, p
->one
->sha1
);
167 hashcpy(mp
->local
, uninitialized
);
168 hashcpy(mp
->remote
, p
->two
->sha1
);
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
));
176 diff_tree_release_paths(&opt
);
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
)
187 struct diff_options opt
;
190 trace_printf("\tdiff_tree_local(len = %i, base = %.7s, local = %.7s)\n",
191 len
, sha1_to_hex(base
), sha1_to_hex(local
));
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
);
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
;
205 unsigned char obj
[20];
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
));
214 mp
= find_notes_merge_pair_pos(changes
, len
, obj
, 0, &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
));
223 assert(!hashcmp(mp
->obj
, obj
));
224 if (is_null_sha1(p
->two
->sha1
)) { /* deletion */
226 * Either this is a true deletion (1), or it is part
227 * of an A/D pair (2), or D/A pair (3):
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)
234 if (!hashcmp(mp
->local
, uninitialized
))
236 } else if (is_null_sha1(p
->one
->sha1
)) { /* addition */
238 * Either this is a true addition (1), or it is part
239 * of an A/D pair (2), or D/A pair (3):
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
245 assert(is_null_sha1(mp
->local
) ||
246 !hashcmp(mp
->local
, uninitialized
));
247 hashcpy(mp
->local
, p
->two
->sha1
);
248 } else { /* modification */
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.
254 assert(!hashcmp(p
->one
->sha1
, mp
->base
));
255 assert(!hashcmp(mp
->local
, uninitialized
));
256 hashcpy(mp
->local
, p
->two
->sha1
);
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
));
263 diff_tree_release_paths(&opt
);
266 static int merge_changes(struct notes_merge_options
*o
,
267 struct notes_merge_pair
*changes
, int *num_changes
,
268 struct notes_tree
*t
)
270 int i
, conflicts
= 0;
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
));
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");
293 /* need file-level merge between local and remote */
294 trace_printf("\t\t\tneed content-level merge\n");
295 conflicts
+= 1; /* TODO */
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
)
307 struct notes_merge_pair
*changes
;
308 int num_changes
, conflicts
;
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
));
314 changes
= diff_tree_remote(o
, base
, remote
, &num_changes
);
315 diff_tree_local(o
, changes
, num_changes
, base
, local
);
317 conflicts
= merge_changes(o
, changes
, &num_changes
, t
);
320 OUTPUT(o
, 4, "Merge result: %i unmerged notes and a %s notes tree",
321 conflicts
, t
->dirty
? "dirty" : "clean");
323 return conflicts
? -1 : 1;
326 void create_notes_commit(struct notes_tree
*t
, struct commit_list
*parents
,
327 const char *msg
, unsigned char *result_sha1
)
329 unsigned char tree_sha1
[20];
331 assert(t
->initialized
);
333 if (write_notes_tree(t
, tree_sha1
))
334 die("Failed to write notes tree to database");
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
);
345 /* else: t->ref points to nothing, assume root/orphan commit */
348 if (commit_tree(msg
, tree_sha1
, parents
, result_sha1
, NULL
))
349 die("Failed to commit notes tree to database");
352 int notes_merge(struct notes_merge_options
*o
,
353 struct notes_tree
*local_tree
,
354 unsigned char *result_sha1
)
356 unsigned char local_sha1
[20], remote_sha1
[20];
357 struct commit
*local
, *remote
;
358 struct commit_list
*bases
= NULL
;
359 const unsigned char *base_sha1
, *base_tree_sha1
;
362 assert(o
->local_ref
&& o
->remote_ref
);
363 assert(!strcmp(o
->local_ref
, local_tree
->ref
));
364 hashclr(result_sha1
);
366 trace_printf("notes_merge(o->local_ref = %s, o->remote_ref = %s)\n",
367 o
->local_ref
, o
->remote_ref
);
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
));
379 /* Dereference o->remote_ref into remote_sha1 */
380 if (get_sha1(o
->remote_ref
, remote_sha1
)) {
382 * Failed to get remote_sha1. If o->remote_ref looks like an
383 * unborn ref, perform the merge using an empty notes tree.
385 if (!check_ref_format(o
->remote_ref
)) {
386 hashclr(remote_sha1
);
389 die("Failed to resolve remote notes ref '%s'",
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
);
396 trace_printf("\tremote commit: %.7s\n", sha1_to_hex(remote_sha1
));
398 if (!local
&& !remote
)
399 die("Cannot merge empty notes ref (%s) into empty notes ref "
400 "(%s)", o
->remote_ref
, o
->local_ref
);
402 /* result == remote commit */
403 hashcpy(result_sha1
, remote_sha1
);
407 /* result == local commit */
408 hashcpy(result_sha1
, local_sha1
);
411 assert(local
&& remote
);
413 /* Find merge bases */
414 bases
= get_merge_bases(local
, remote
, 1);
416 base_sha1
= null_sha1
;
417 base_tree_sha1
= (unsigned char *)EMPTY_TREE_SHA1_BIN
;
418 OUTPUT(o
, 4, "No merge base found; doing history-less merge");
419 } else if (!bases
->next
) {
420 base_sha1
= bases
->item
->object
.sha1
;
421 base_tree_sha1
= bases
->item
->tree
->object
.sha1
;
422 OUTPUT(o
, 4, "One merge base found (%.7s)",
423 sha1_to_hex(base_sha1
));
425 /* TODO: How to handle multiple merge-bases? */
426 base_sha1
= bases
->item
->object
.sha1
;
427 base_tree_sha1
= bases
->item
->tree
->object
.sha1
;
428 OUTPUT(o
, 3, "Multiple merge bases found. Using the first "
429 "(%.7s)", sha1_to_hex(base_sha1
));
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
));
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
);
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
);
449 result
= merge_from_diffs(o
, base_tree_sha1
, local
->tree
->object
.sha1
,
450 remote
->tree
->object
.sha1
, local_tree
);
452 if (result
> 0) { /* successful non-trivial merge */
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
,
462 free_commit_list(bases
);
463 trace_printf("notes_merge(): result = %i, result_sha1 = %.7s\n",
464 result
, sha1_to_hex(result_sha1
));