2 * "Ostensibly Recursive's Twin" merge strategy, or "ort" for short. Meant
3 * as a drop-in replacement for the "recursive" merge strategy, allowing one
6 * git merge [-s recursive]
12 * Note: git's parser allows the space between '-s' and its argument to be
13 * missing. (Should I have backronymed "ham", "alsa", "kip", "nap, "alvo",
14 * "cale", "peedy", or "ins" instead of "ort"?)
18 #include "merge-ort.h"
21 #include "cache-tree.h"
22 #include "commit-reach.h"
26 #include "object-store.h"
29 #include "unpack-trees.h"
30 #include "xdiff-interface.h"
33 * We have many arrays of size 3. Whenever we have such an array, the
34 * indices refer to one of the sides of the three-way merge. This is so
35 * pervasive that the constants 0, 1, and 2 are used in many places in the
36 * code (especially in arithmetic operations to find the other side's index
37 * or to compute a relevant mask), but sometimes these enum names are used
38 * to aid code clarity.
40 * See also 'filemask' and 'dirmask' in struct conflict_info; the "ith side"
41 * referred to there is one of these three sides.
49 struct merge_options_internal
{
51 * paths: primary data structure in all of merge ort.
54 * * are full relative paths from the toplevel of the repository
55 * (e.g. "drivers/firmware/raspberrypi.c").
56 * * store all relevant paths in the repo, both directories and
57 * files (e.g. drivers, drivers/firmware would also be included)
58 * * these keys serve to intern all the path strings, which allows
59 * us to do pointer comparison on directory names instead of
60 * strcmp; we just have to be careful to use the interned strings.
62 * The values of paths:
63 * * either a pointer to a merged_info, or a conflict_info struct
64 * * merged_info contains all relevant information for a
65 * non-conflicted entry.
66 * * conflict_info contains a merged_info, plus any additional
67 * information about a conflict such as the higher orders stages
68 * involved and the names of the paths those came from (handy
69 * once renames get involved).
70 * * a path may start "conflicted" (i.e. point to a conflict_info)
71 * and then a later step (e.g. three-way content merge) determines
72 * it can be cleanly merged, at which point it'll be marked clean
73 * and the algorithm will ignore any data outside the contained
74 * merged_info for that entry
75 * * If an entry remains conflicted, the merged_info portion of a
76 * conflict_info will later be filled with whatever version of
77 * the file should be placed in the working directory (e.g. an
78 * as-merged-as-possible variation that contains conflict markers).
83 * conflicted: a subset of keys->values from "paths"
85 * conflicted is basically an optimization between process_entries()
86 * and record_conflicted_index_entries(); the latter could loop over
87 * ALL the entries in paths AGAIN and look for the ones that are
88 * still conflicted, but since process_entries() has to loop over
89 * all of them, it saves the ones it couldn't resolve in this strmap
90 * so that record_conflicted_index_entries() can iterate just the
93 struct strmap conflicted
;
96 * current_dir_name: temporary var used in collect_merge_info_callback()
98 * Used to set merged_info.directory_name; see documentation for that
99 * variable and the requirements placed on that field.
101 const char *current_dir_name
;
103 /* call_depth: recursion level counter for merging merge bases */
107 struct version_info
{
108 struct object_id oid
;
113 /* if is_null, ignore result. otherwise result has oid & mode */
114 struct version_info result
;
118 * clean: whether the path in question is cleanly merged.
120 * see conflict_info.merged for more details.
125 * basename_offset: offset of basename of path.
127 * perf optimization to avoid recomputing offset of final '/'
128 * character in pathname (0 if no '/' in pathname).
130 size_t basename_offset
;
133 * directory_name: containing directory name.
135 * Note that we assume directory_name is constructed such that
136 * strcmp(dir1_name, dir2_name) == 0 iff dir1_name == dir2_name,
137 * i.e. string equality is equivalent to pointer equality. For this
138 * to hold, we have to be careful setting directory_name.
140 const char *directory_name
;
143 struct conflict_info
{
145 * merged: the version of the path that will be written to working tree
147 * WARNING: It is critical to check merged.clean and ensure it is 0
148 * before reading any conflict_info fields outside of merged.
149 * Allocated merge_info structs will always have clean set to 1.
150 * Allocated conflict_info structs will have merged.clean set to 0
151 * initially. The merged.clean field is how we know if it is safe
152 * to access other parts of conflict_info besides merged; if a
153 * conflict_info's merged.clean is changed to 1, the rest of the
154 * algorithm is not allowed to look at anything outside of the
155 * merged member anymore.
157 struct merged_info merged
;
159 /* oids & modes from each of the three trees for this path */
160 struct version_info stages
[3];
162 /* pathnames for each stage; may differ due to rename detection */
163 const char *pathnames
[3];
165 /* Whether this path is/was involved in a directory/file conflict */
166 unsigned df_conflict
:1;
169 * For filemask and dirmask, the ith bit corresponds to whether the
170 * ith entry is a file (filemask) or a directory (dirmask). Thus,
171 * filemask & dirmask is always zero, and filemask | dirmask is at
172 * most 7 but can be less when a path does not appear as either a
173 * file or a directory on at least one side of history.
175 * Note that these masks are related to enum merge_side, as the ith
176 * entry corresponds to side i.
178 * These values come from a traverse_trees() call; more info may be
179 * found looking at tree-walk.h's struct traverse_info,
180 * particularly the documentation above the "fn" member (note that
181 * filemask = mask & ~dirmask from that documentation).
187 * Optimization to track which stages match, to avoid the need to
188 * recompute it in multiple steps. Either 0 or at least 2 bits are
189 * set; if at least 2 bits are set, their corresponding stages match.
191 unsigned match_mask
:3;
195 * For the next three macros, see warning for conflict_info.merged.
197 * In each of the below, mi is a struct merged_info*, and ci was defined
198 * as a struct conflict_info* (but we need to verify ci isn't actually
199 * pointed at a struct merged_info*).
201 * INITIALIZE_CI: Assign ci to mi but only if it's safe; set to NULL otherwise.
202 * VERIFY_CI: Ensure that something we assigned to a conflict_info* is one.
203 * ASSIGN_AND_VERIFY_CI: Similar to VERIFY_CI but do assignment first.
205 #define INITIALIZE_CI(ci, mi) do { \
206 (ci) = (!(mi) || (mi)->clean) ? NULL : (struct conflict_info *)(mi); \
208 #define VERIFY_CI(ci) assert(ci && !ci->merged.clean);
209 #define ASSIGN_AND_VERIFY_CI(ci, mi) do { \
210 (ci) = (struct conflict_info *)(mi); \
211 assert((ci) && !(mi)->clean); \
214 static void free_strmap_strings(struct strmap
*map
)
216 struct hashmap_iter iter
;
217 struct strmap_entry
*entry
;
219 strmap_for_each_entry(map
, &iter
, entry
) {
220 free((char*)entry
->key
);
224 static int err(struct merge_options
*opt
, const char *err
, ...)
227 struct strbuf sb
= STRBUF_INIT
;
229 strbuf_addstr(&sb
, "error: ");
230 va_start(params
, err
);
231 strbuf_vaddf(&sb
, err
, params
);
240 static void setup_path_info(struct merge_options
*opt
,
241 struct string_list_item
*result
,
242 const char *current_dir_name
,
243 int current_dir_name_len
,
244 char *fullpath
, /* we'll take over ownership */
245 struct name_entry
*names
,
246 struct name_entry
*merged_version
,
247 unsigned is_null
, /* boolean */
248 unsigned df_conflict
, /* boolean */
251 int resolved
/* boolean */)
253 /* result->util is void*, so mi is a convenience typed variable */
254 struct merged_info
*mi
;
256 assert(!is_null
|| resolved
);
257 assert(!df_conflict
|| !resolved
); /* df_conflict implies !resolved */
258 assert(resolved
== (merged_version
!= NULL
));
260 mi
= xcalloc(1, resolved
? sizeof(struct merged_info
) :
261 sizeof(struct conflict_info
));
262 mi
->directory_name
= current_dir_name
;
263 mi
->basename_offset
= current_dir_name_len
;
264 mi
->clean
= !!resolved
;
266 mi
->result
.mode
= merged_version
->mode
;
267 oidcpy(&mi
->result
.oid
, &merged_version
->oid
);
268 mi
->is_null
= !!is_null
;
271 struct conflict_info
*ci
;
273 ASSIGN_AND_VERIFY_CI(ci
, mi
);
274 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
275 ci
->pathnames
[i
] = fullpath
;
276 ci
->stages
[i
].mode
= names
[i
].mode
;
277 oidcpy(&ci
->stages
[i
].oid
, &names
[i
].oid
);
279 ci
->filemask
= filemask
;
280 ci
->dirmask
= dirmask
;
281 ci
->df_conflict
= !!df_conflict
;
284 * Assume is_null for now, but if we have entries
285 * under the directory then when it is complete in
286 * write_completed_directory() it'll update this.
287 * Also, for D/F conflicts, we have to handle the
288 * directory first, then clear this bit and process
289 * the file to see how it is handled -- that occurs
290 * near the top of process_entry().
294 strmap_put(&opt
->priv
->paths
, fullpath
, mi
);
295 result
->string
= fullpath
;
299 static int collect_merge_info_callback(int n
,
301 unsigned long dirmask
,
302 struct name_entry
*names
,
303 struct traverse_info
*info
)
307 * common ancestor (mbase) has mask 1, and stored in index 0 of names
308 * head of side 1 (side1) has mask 2, and stored in index 1 of names
309 * head of side 2 (side2) has mask 4, and stored in index 2 of names
311 struct merge_options
*opt
= info
->data
;
312 struct merge_options_internal
*opti
= opt
->priv
;
313 struct string_list_item pi
; /* Path Info */
314 struct conflict_info
*ci
; /* typed alias to pi.util (which is void*) */
315 struct name_entry
*p
;
318 const char *dirname
= opti
->current_dir_name
;
319 unsigned filemask
= mask
& ~dirmask
;
320 unsigned match_mask
= 0; /* will be updated below */
321 unsigned mbase_null
= !(mask
& 1);
322 unsigned side1_null
= !(mask
& 2);
323 unsigned side2_null
= !(mask
& 4);
324 unsigned side1_matches_mbase
= (!side1_null
&& !mbase_null
&&
325 names
[0].mode
== names
[1].mode
&&
326 oideq(&names
[0].oid
, &names
[1].oid
));
327 unsigned side2_matches_mbase
= (!side2_null
&& !mbase_null
&&
328 names
[0].mode
== names
[2].mode
&&
329 oideq(&names
[0].oid
, &names
[2].oid
));
330 unsigned sides_match
= (!side1_null
&& !side2_null
&&
331 names
[1].mode
== names
[2].mode
&&
332 oideq(&names
[1].oid
, &names
[2].oid
));
335 * Note: When a path is a file on one side of history and a directory
336 * in another, we have a directory/file conflict. In such cases, if
337 * the conflict doesn't resolve from renames and deletions, then we
338 * always leave directories where they are and move files out of the
339 * way. Thus, while struct conflict_info has a df_conflict field to
340 * track such conflicts, we ignore that field for any directories at
341 * a path and only pay attention to it for files at the given path.
342 * The fact that we leave directories were they are also means that
343 * we do not need to worry about getting additional df_conflict
344 * information propagated from parent directories down to children
345 * (unlike, say traverse_trees_recursive() in unpack-trees.c, which
346 * sets a newinfo.df_conflicts field specifically to propagate it).
348 unsigned df_conflict
= (filemask
!= 0) && (dirmask
!= 0);
350 /* n = 3 is a fundamental assumption. */
352 BUG("Called collect_merge_info_callback wrong");
355 * A bunch of sanity checks verifying that traverse_trees() calls
356 * us the way I expect. Could just remove these at some point,
357 * though maybe they are helpful to future code readers.
359 assert(mbase_null
== is_null_oid(&names
[0].oid
));
360 assert(side1_null
== is_null_oid(&names
[1].oid
));
361 assert(side2_null
== is_null_oid(&names
[2].oid
));
362 assert(!mbase_null
|| !side1_null
|| !side2_null
);
363 assert(mask
> 0 && mask
< 8);
365 /* Determine match_mask */
366 if (side1_matches_mbase
)
367 match_mask
= (side2_matches_mbase
? 7 : 3);
368 else if (side2_matches_mbase
)
370 else if (sides_match
)
374 * Get the name of the relevant filepath, which we'll pass to
375 * setup_path_info() for tracking.
380 len
= traverse_path_len(info
, p
->pathlen
);
382 /* +1 in both of the following lines to include the NUL byte */
383 fullpath
= xmalloc(len
+ 1);
384 make_traverse_path(fullpath
, len
+ 1, info
, p
->path
, p
->pathlen
);
387 * If mbase, side1, and side2 all match, we can resolve early. Even
388 * if these are trees, there will be no renames or anything
391 if (side1_matches_mbase
&& side2_matches_mbase
) {
392 /* mbase, side1, & side2 all match; use mbase as resolution */
393 setup_path_info(opt
, &pi
, dirname
, info
->pathlen
, fullpath
,
394 names
, names
+0, mbase_null
, 0,
395 filemask
, dirmask
, 1);
400 * Record information about the path so we can resolve later in
403 setup_path_info(opt
, &pi
, dirname
, info
->pathlen
, fullpath
,
404 names
, NULL
, 0, df_conflict
, filemask
, dirmask
, 0);
408 ci
->match_mask
= match_mask
;
410 /* If dirmask, recurse into subdirectories */
412 struct traverse_info newinfo
;
413 struct tree_desc t
[3];
414 void *buf
[3] = {NULL
, NULL
, NULL
};
415 const char *original_dir_name
;
418 ci
->match_mask
&= filemask
;
421 newinfo
.name
= p
->path
;
422 newinfo
.namelen
= p
->pathlen
;
423 newinfo
.pathlen
= st_add3(newinfo
.pathlen
, p
->pathlen
, 1);
425 * If this directory we are about to recurse into cared about
426 * its parent directory (the current directory) having a D/F
427 * conflict, then we'd propagate the masks in this way:
428 * newinfo.df_conflicts |= (mask & ~dirmask);
429 * But we don't worry about propagating D/F conflicts. (See
430 * comment near setting of local df_conflict variable near
431 * the beginning of this function).
434 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
435 if (i
== 1 && side1_matches_mbase
)
437 else if (i
== 2 && side2_matches_mbase
)
439 else if (i
== 2 && sides_match
)
442 const struct object_id
*oid
= NULL
;
445 buf
[i
] = fill_tree_descriptor(opt
->repo
,
451 original_dir_name
= opti
->current_dir_name
;
452 opti
->current_dir_name
= pi
.string
;
453 ret
= traverse_trees(NULL
, 3, t
, &newinfo
);
454 opti
->current_dir_name
= original_dir_name
;
456 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++)
466 static int collect_merge_info(struct merge_options
*opt
,
467 struct tree
*merge_base
,
472 struct tree_desc t
[3];
473 struct traverse_info info
;
474 const char *toplevel_dir_placeholder
= "";
476 opt
->priv
->current_dir_name
= toplevel_dir_placeholder
;
477 setup_traverse_info(&info
, toplevel_dir_placeholder
);
478 info
.fn
= collect_merge_info_callback
;
480 info
.show_all_errors
= 1;
482 parse_tree(merge_base
);
485 init_tree_desc(t
+ 0, merge_base
->buffer
, merge_base
->size
);
486 init_tree_desc(t
+ 1, side1
->buffer
, side1
->size
);
487 init_tree_desc(t
+ 2, side2
->buffer
, side2
->size
);
489 ret
= traverse_trees(NULL
, 3, t
, &info
);
494 static int detect_and_process_renames(struct merge_options
*opt
,
495 struct tree
*merge_base
,
502 * Rename detection works by detecting file similarity. Here we use
503 * a really easy-to-implement scheme: files are similar IFF they have
504 * the same filename. Therefore, by this scheme, there are no renames.
506 * TODO: Actually implement a real rename detection scheme.
511 static int string_list_df_name_compare(const char *one
, const char *two
)
513 int onelen
= strlen(one
);
514 int twolen
= strlen(two
);
516 * Here we only care that entries for D/F conflicts are
517 * adjacent, in particular with the file of the D/F conflict
518 * appearing before files below the corresponding directory.
519 * The order of the rest of the list is irrelevant for us.
521 * To achieve this, we sort with df_name_compare and provide
522 * the mode S_IFDIR so that D/F conflicts will sort correctly.
523 * We use the mode S_IFDIR for everything else for simplicity,
524 * since in other cases any changes in their order due to
525 * sorting cause no problems for us.
527 int cmp
= df_name_compare(one
, onelen
, S_IFDIR
,
528 two
, twolen
, S_IFDIR
);
530 * Now that 'foo' and 'foo/bar' compare equal, we have to make sure
531 * that 'foo' comes before 'foo/bar'.
535 return onelen
- twolen
;
538 struct directory_versions
{
540 * versions: list of (basename -> version_info)
542 * The basenames are in reverse lexicographic order of full pathnames,
543 * as processed in process_entries(). This puts all entries within
544 * a directory together, and covers the directory itself after
545 * everything within it, allowing us to write subtrees before needing
546 * to record information for the tree itself.
548 struct string_list versions
;
551 * offsets: list of (full relative path directories -> integer offsets)
553 * Since versions contains basenames from files in multiple different
554 * directories, we need to know which entries in versions correspond
555 * to which directories. Values of e.g.
559 * Would mean that entries 0-1 of versions are files in the toplevel
560 * directory, entries 2-4 are files under src/, and the remaining
561 * entries starting at index 5 are files under src/moduleA/.
563 struct string_list offsets
;
566 * last_directory: directory that previously processed file found in
568 * last_directory starts NULL, but records the directory in which the
569 * previous file was found within. As soon as
570 * directory(current_file) != last_directory
571 * then we need to start updating accounting in versions & offsets.
572 * Note that last_directory is always the last path in "offsets" (or
573 * NULL if "offsets" is empty) so this exists just for quick access.
575 const char *last_directory
;
577 /* last_directory_len: cached computation of strlen(last_directory) */
578 unsigned last_directory_len
;
581 static int tree_entry_order(const void *a_
, const void *b_
)
583 const struct string_list_item
*a
= a_
;
584 const struct string_list_item
*b
= b_
;
586 const struct merged_info
*ami
= a
->util
;
587 const struct merged_info
*bmi
= b
->util
;
588 return base_name_compare(a
->string
, strlen(a
->string
), ami
->result
.mode
,
589 b
->string
, strlen(b
->string
), bmi
->result
.mode
);
592 static void write_tree(struct object_id
*result_oid
,
593 struct string_list
*versions
,
597 size_t maxlen
= 0, extra
;
598 unsigned int nr
= versions
->nr
- offset
;
599 struct strbuf buf
= STRBUF_INIT
;
600 struct string_list relevant_entries
= STRING_LIST_INIT_NODUP
;
604 * We want to sort the last (versions->nr-offset) entries in versions.
605 * Do so by abusing the string_list API a bit: make another string_list
606 * that contains just those entries and then sort them.
608 * We won't use relevant_entries again and will let it just pop off the
609 * stack, so there won't be allocation worries or anything.
611 relevant_entries
.items
= versions
->items
+ offset
;
612 relevant_entries
.nr
= versions
->nr
- offset
;
613 QSORT(relevant_entries
.items
, relevant_entries
.nr
, tree_entry_order
);
615 /* Pre-allocate some space in buf */
616 extra
= hash_size
+ 8; /* 8: 6 for mode, 1 for space, 1 for NUL char */
617 for (i
= 0; i
< nr
; i
++) {
618 maxlen
+= strlen(versions
->items
[offset
+i
].string
) + extra
;
620 strbuf_grow(&buf
, maxlen
);
622 /* Write each entry out to buf */
623 for (i
= 0; i
< nr
; i
++) {
624 struct merged_info
*mi
= versions
->items
[offset
+i
].util
;
625 struct version_info
*ri
= &mi
->result
;
626 strbuf_addf(&buf
, "%o %s%c",
628 versions
->items
[offset
+i
].string
, '\0');
629 strbuf_add(&buf
, ri
->oid
.hash
, hash_size
);
632 /* Write this object file out, and record in result_oid */
633 write_object_file(buf
.buf
, buf
.len
, tree_type
, result_oid
);
634 strbuf_release(&buf
);
637 static void record_entry_for_tree(struct directory_versions
*dir_metadata
,
639 struct merged_info
*mi
)
641 const char *basename
;
644 /* nothing to record */
647 basename
= path
+ mi
->basename_offset
;
648 assert(strchr(basename
, '/') == NULL
);
649 string_list_append(&dir_metadata
->versions
,
650 basename
)->util
= &mi
->result
;
653 static void write_completed_directory(struct merge_options
*opt
,
654 const char *new_directory_name
,
655 struct directory_versions
*info
)
657 const char *prev_dir
;
658 struct merged_info
*dir_info
= NULL
;
662 * Some explanation of info->versions and info->offsets...
664 * process_entries() iterates over all relevant files AND
665 * directories in reverse lexicographic order, and calls this
666 * function. Thus, an example of the paths that process_entries()
667 * could operate on (along with the directories for those paths
672 * src/moduleB/umm.c src/moduleB
673 * src/moduleB/stuff.h src/moduleB
674 * src/moduleB/baz.c src/moduleB
676 * src/moduleA/foo.c src/moduleA
677 * src/moduleA/bar.c src/moduleA
684 * always contains the unprocessed entries and their
685 * version_info information. For example, after the first five
686 * entries above, info->versions would be:
688 * xtract.c <xtract.c's version_info>
689 * token.txt <token.txt's version_info>
690 * umm.c <src/moduleB/umm.c's version_info>
691 * stuff.h <src/moduleB/stuff.h's version_info>
692 * baz.c <src/moduleB/baz.c's version_info>
694 * Once a subdirectory is completed we remove the entries in
695 * that subdirectory from info->versions, writing it as a tree
696 * (write_tree()). Thus, as soon as we get to src/moduleB,
697 * info->versions would be updated to
699 * xtract.c <xtract.c's version_info>
700 * token.txt <token.txt's version_info>
701 * moduleB <src/moduleB's version_info>
705 * helps us track which entries in info->versions correspond to
706 * which directories. When we are N directories deep (e.g. 4
707 * for src/modA/submod/subdir/), we have up to N+1 unprocessed
708 * directories (+1 because of toplevel dir). Corresponding to
709 * the info->versions example above, after processing five entries
710 * info->offsets will be:
715 * which is used to know that xtract.c & token.txt are from the
716 * toplevel dirctory, while umm.c & stuff.h & baz.c are from the
717 * src/moduleB directory. Again, following the example above,
718 * once we need to process src/moduleB, then info->offsets is
724 * which says that moduleB (and only moduleB so far) is in the
727 * One unique thing to note about info->offsets here is that
728 * "src" was not added to info->offsets until there was a path
729 * (a file OR directory) immediately below src/ that got
732 * Since process_entry() just appends new entries to info->versions,
733 * write_completed_directory() only needs to do work if the next path
734 * is in a directory that is different than the last directory found
739 * If we are working with the same directory as the last entry, there
740 * is no work to do. (See comments above the directory_name member of
741 * struct merged_info for why we can use pointer comparison instead of
744 if (new_directory_name
== info
->last_directory
)
748 * If we are just starting (last_directory is NULL), or last_directory
749 * is a prefix of the current directory, then we can just update
750 * info->offsets to record the offset where we started this directory
751 * and update last_directory to have quick access to it.
753 if (info
->last_directory
== NULL
||
754 !strncmp(new_directory_name
, info
->last_directory
,
755 info
->last_directory_len
)) {
756 uintptr_t offset
= info
->versions
.nr
;
758 info
->last_directory
= new_directory_name
;
759 info
->last_directory_len
= strlen(info
->last_directory
);
761 * Record the offset into info->versions where we will
762 * start recording basenames of paths found within
763 * new_directory_name.
765 string_list_append(&info
->offsets
,
766 info
->last_directory
)->util
= (void*)offset
;
771 * The next entry that will be processed will be within
772 * new_directory_name. Since at this point we know that
773 * new_directory_name is within a different directory than
774 * info->last_directory, we have all entries for info->last_directory
775 * in info->versions and we need to create a tree object for them.
777 dir_info
= strmap_get(&opt
->priv
->paths
, info
->last_directory
);
779 offset
= (uintptr_t)info
->offsets
.items
[info
->offsets
.nr
-1].util
;
780 if (offset
== info
->versions
.nr
) {
782 * Actually, we don't need to create a tree object in this
783 * case. Whenever all files within a directory disappear
784 * during the merge (e.g. unmodified on one side and
785 * deleted on the other, or files were renamed elsewhere),
786 * then we get here and the directory itself needs to be
787 * omitted from its parent tree as well.
789 dir_info
->is_null
= 1;
792 * Write out the tree to the git object directory, and also
793 * record the mode and oid in dir_info->result.
795 dir_info
->is_null
= 0;
796 dir_info
->result
.mode
= S_IFDIR
;
797 write_tree(&dir_info
->result
.oid
, &info
->versions
, offset
,
798 opt
->repo
->hash_algo
->rawsz
);
802 * We've now used several entries from info->versions and one entry
803 * from info->offsets, so we get rid of those values.
806 info
->versions
.nr
= offset
;
809 * Now we've taken care of the completed directory, but we need to
810 * prepare things since future entries will be in
811 * new_directory_name. (In particular, process_entry() will be
812 * appending new entries to info->versions.) So, we need to make
813 * sure new_directory_name is the last entry in info->offsets.
815 prev_dir
= info
->offsets
.nr
== 0 ? NULL
:
816 info
->offsets
.items
[info
->offsets
.nr
-1].string
;
817 if (new_directory_name
!= prev_dir
) {
818 uintptr_t c
= info
->versions
.nr
;
819 string_list_append(&info
->offsets
,
820 new_directory_name
)->util
= (void*)c
;
823 /* And, of course, we need to update last_directory to match. */
824 info
->last_directory
= new_directory_name
;
825 info
->last_directory_len
= strlen(info
->last_directory
);
828 /* Per entry merge function */
829 static void process_entry(struct merge_options
*opt
,
831 struct conflict_info
*ci
,
832 struct directory_versions
*dir_metadata
)
835 assert(ci
->filemask
>= 0 && ci
->filemask
<= 7);
836 /* ci->match_mask == 7 was handled in collect_merge_info_callback() */
837 assert(ci
->match_mask
== 0 || ci
->match_mask
== 3 ||
838 ci
->match_mask
== 5 || ci
->match_mask
== 6);
841 record_entry_for_tree(dir_metadata
, path
, &ci
->merged
);
842 if (ci
->filemask
== 0)
843 /* nothing else to handle */
845 assert(ci
->df_conflict
);
848 if (ci
->df_conflict
) {
849 die("Not yet implemented.");
853 * NOTE: Below there is a long switch-like if-elseif-elseif... block
854 * which the code goes through even for the df_conflict cases
855 * above. Well, it will once we don't die-not-implemented above.
857 if (ci
->match_mask
) {
858 ci
->merged
.clean
= 1;
859 if (ci
->match_mask
== 6) {
860 /* stages[1] == stages[2] */
861 ci
->merged
.result
.mode
= ci
->stages
[1].mode
;
862 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[1].oid
);
864 /* determine the mask of the side that didn't match */
865 unsigned int othermask
= 7 & ~ci
->match_mask
;
866 int side
= (othermask
== 4) ? 2 : 1;
868 ci
->merged
.result
.mode
= ci
->stages
[side
].mode
;
869 ci
->merged
.is_null
= !ci
->merged
.result
.mode
;
870 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[side
].oid
);
872 assert(othermask
== 2 || othermask
== 4);
873 assert(ci
->merged
.is_null
==
874 (ci
->filemask
== ci
->match_mask
));
876 } else if (ci
->filemask
>= 6 &&
877 (S_IFMT
& ci
->stages
[1].mode
) !=
878 (S_IFMT
& ci
->stages
[2].mode
)) {
880 * Two different items from (file/submodule/symlink)
882 die("Not yet implemented.");
883 } else if (ci
->filemask
>= 6) {
885 * TODO: Needs a two-way or three-way content merge, but we're
886 * just being lazy and copying the version from HEAD and
887 * leaving it as conflicted.
889 ci
->merged
.clean
= 0;
890 ci
->merged
.result
.mode
= ci
->stages
[1].mode
;
891 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[1].oid
);
892 } else if (ci
->filemask
== 3 || ci
->filemask
== 5) {
894 die("Not yet implemented.");
895 } else if (ci
->filemask
== 2 || ci
->filemask
== 4) {
896 /* Added on one side */
897 int side
= (ci
->filemask
== 4) ? 2 : 1;
898 ci
->merged
.result
.mode
= ci
->stages
[side
].mode
;
899 oidcpy(&ci
->merged
.result
.oid
, &ci
->stages
[side
].oid
);
900 ci
->merged
.clean
= !ci
->df_conflict
;
901 } else if (ci
->filemask
== 1) {
902 /* Deleted on both sides */
903 ci
->merged
.is_null
= 1;
904 ci
->merged
.result
.mode
= 0;
905 oidcpy(&ci
->merged
.result
.oid
, &null_oid
);
906 ci
->merged
.clean
= 1;
910 * If still conflicted, record it separately. This allows us to later
911 * iterate over just conflicted entries when updating the index instead
912 * of iterating over all entries.
914 if (!ci
->merged
.clean
)
915 strmap_put(&opt
->priv
->conflicted
, path
, ci
);
916 record_entry_for_tree(dir_metadata
, path
, &ci
->merged
);
919 static void process_entries(struct merge_options
*opt
,
920 struct object_id
*result_oid
)
922 struct hashmap_iter iter
;
923 struct strmap_entry
*e
;
924 struct string_list plist
= STRING_LIST_INIT_NODUP
;
925 struct string_list_item
*entry
;
926 struct directory_versions dir_metadata
= { STRING_LIST_INIT_NODUP
,
927 STRING_LIST_INIT_NODUP
,
930 if (strmap_empty(&opt
->priv
->paths
)) {
931 oidcpy(result_oid
, opt
->repo
->hash_algo
->empty_tree
);
935 /* Hack to pre-allocate plist to the desired size */
936 ALLOC_GROW(plist
.items
, strmap_get_size(&opt
->priv
->paths
), plist
.alloc
);
938 /* Put every entry from paths into plist, then sort */
939 strmap_for_each_entry(&opt
->priv
->paths
, &iter
, e
) {
940 string_list_append(&plist
, e
->key
)->util
= e
->value
;
942 plist
.cmp
= string_list_df_name_compare
;
943 string_list_sort(&plist
);
946 * Iterate over the items in reverse order, so we can handle paths
947 * below a directory before needing to handle the directory itself.
949 * This allows us to write subtrees before we need to write trees,
950 * and it also enables sane handling of directory/file conflicts
951 * (because it allows us to know whether the directory is still in
952 * the way when it is time to process the file at the same path).
954 for (entry
= &plist
.items
[plist
.nr
-1]; entry
>= plist
.items
; --entry
) {
955 char *path
= entry
->string
;
957 * NOTE: mi may actually be a pointer to a conflict_info, but
958 * we have to check mi->clean first to see if it's safe to
959 * reassign to such a pointer type.
961 struct merged_info
*mi
= entry
->util
;
963 write_completed_directory(opt
, mi
->directory_name
,
966 record_entry_for_tree(&dir_metadata
, path
, mi
);
968 struct conflict_info
*ci
= (struct conflict_info
*)mi
;
969 process_entry(opt
, path
, ci
, &dir_metadata
);
973 if (dir_metadata
.offsets
.nr
!= 1 ||
974 (uintptr_t)dir_metadata
.offsets
.items
[0].util
!= 0) {
975 printf("dir_metadata.offsets.nr = %d (should be 1)\n",
976 dir_metadata
.offsets
.nr
);
977 printf("dir_metadata.offsets.items[0].util = %u (should be 0)\n",
978 (unsigned)(uintptr_t)dir_metadata
.offsets
.items
[0].util
);
980 BUG("dir_metadata accounting completely off; shouldn't happen");
982 write_tree(result_oid
, &dir_metadata
.versions
, 0,
983 opt
->repo
->hash_algo
->rawsz
);
984 string_list_clear(&plist
, 0);
985 string_list_clear(&dir_metadata
.versions
, 0);
986 string_list_clear(&dir_metadata
.offsets
, 0);
989 static int checkout(struct merge_options
*opt
,
993 /* Switch the index/working copy from old to new */
995 struct tree_desc trees
[2];
996 struct unpack_trees_options unpack_opts
;
998 memset(&unpack_opts
, 0, sizeof(unpack_opts
));
999 unpack_opts
.head_idx
= -1;
1000 unpack_opts
.src_index
= opt
->repo
->index
;
1001 unpack_opts
.dst_index
= opt
->repo
->index
;
1003 setup_unpack_trees_porcelain(&unpack_opts
, "merge");
1006 * NOTE: if this were just "git checkout" code, we would probably
1007 * read or refresh the cache and check for a conflicted index, but
1008 * builtin/merge.c or sequencer.c really needs to read the index
1009 * and check for conflicted entries before starting merging for a
1010 * good user experience (no sense waiting for merges/rebases before
1011 * erroring out), so there's no reason to duplicate that work here.
1014 /* 2-way merge to the new branch */
1015 unpack_opts
.update
= 1;
1016 unpack_opts
.merge
= 1;
1017 unpack_opts
.quiet
= 0; /* FIXME: sequencer might want quiet? */
1018 unpack_opts
.verbose_update
= (opt
->verbosity
> 2);
1019 unpack_opts
.fn
= twoway_merge
;
1020 if (1/* FIXME: opts->overwrite_ignore*/) {
1021 unpack_opts
.dir
= xcalloc(1, sizeof(*unpack_opts
.dir
));
1022 unpack_opts
.dir
->flags
|= DIR_SHOW_IGNORED
;
1023 setup_standard_excludes(unpack_opts
.dir
);
1026 init_tree_desc(&trees
[0], prev
->buffer
, prev
->size
);
1028 init_tree_desc(&trees
[1], next
->buffer
, next
->size
);
1030 ret
= unpack_trees(2, trees
, &unpack_opts
);
1031 clear_unpack_trees_porcelain(&unpack_opts
);
1032 dir_clear(unpack_opts
.dir
);
1033 FREE_AND_NULL(unpack_opts
.dir
);
1037 static int record_conflicted_index_entries(struct merge_options
*opt
,
1038 struct index_state
*index
,
1039 struct strmap
*paths
,
1040 struct strmap
*conflicted
)
1042 struct hashmap_iter iter
;
1043 struct strmap_entry
*e
;
1045 int original_cache_nr
;
1047 if (strmap_empty(conflicted
))
1050 original_cache_nr
= index
->cache_nr
;
1052 /* Put every entry from paths into plist, then sort */
1053 strmap_for_each_entry(conflicted
, &iter
, e
) {
1054 const char *path
= e
->key
;
1055 struct conflict_info
*ci
= e
->value
;
1057 struct cache_entry
*ce
;
1063 * The index will already have a stage=0 entry for this path,
1064 * because we created an as-merged-as-possible version of the
1065 * file and checkout() moved the working copy and index over
1068 * However, previous iterations through this loop will have
1069 * added unstaged entries to the end of the cache which
1070 * ignore the standard alphabetical ordering of cache
1071 * entries and break invariants needed for index_name_pos()
1072 * to work. However, we know the entry we want is before
1073 * those appended cache entries, so do a temporary swap on
1074 * cache_nr to only look through entries of interest.
1076 SWAP(index
->cache_nr
, original_cache_nr
);
1077 pos
= index_name_pos(index
, path
, strlen(path
));
1078 SWAP(index
->cache_nr
, original_cache_nr
);
1080 if (ci
->filemask
!= 1)
1081 BUG("Conflicted %s but nothing in basic working tree or index; this shouldn't happen", path
);
1082 cache_tree_invalidate_path(index
, path
);
1084 ce
= index
->cache
[pos
];
1087 * Clean paths with CE_SKIP_WORKTREE set will not be
1088 * written to the working tree by the unpack_trees()
1089 * call in checkout(). Our conflicted entries would
1090 * have appeared clean to that code since we ignored
1091 * the higher order stages. Thus, we need override
1092 * the CE_SKIP_WORKTREE bit and manually write those
1093 * files to the working disk here.
1095 * TODO: Implement this CE_SKIP_WORKTREE fixup.
1099 * Mark this cache entry for removal and instead add
1100 * new stage>0 entries corresponding to the
1101 * conflicts. If there are many conflicted entries, we
1102 * want to avoid memmove'ing O(NM) entries by
1103 * inserting the new entries one at a time. So,
1104 * instead, we just add the new cache entries to the
1105 * end (ignoring normal index requirements on sort
1106 * order) and sort the index once we're all done.
1108 ce
->ce_flags
|= CE_REMOVE
;
1111 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
1112 struct version_info
*vi
;
1113 if (!(ci
->filemask
& (1ul << i
)))
1115 vi
= &ci
->stages
[i
];
1116 ce
= make_cache_entry(index
, vi
->mode
, &vi
->oid
,
1118 add_index_entry(index
, ce
, ADD_CACHE_JUST_APPEND
);
1123 * Remove the unused cache entries (and invalidate the relevant
1124 * cache-trees), then sort the index entries to get the conflicted
1125 * entries we added to the end into their right locations.
1127 remove_marked_cache_entries(index
, 1);
1128 QSORT(index
->cache
, index
->cache_nr
, cmp_cache_name_compare
);
1133 void merge_switch_to_result(struct merge_options
*opt
,
1135 struct merge_result
*result
,
1136 int update_worktree_and_index
,
1137 int display_update_msgs
)
1139 assert(opt
->priv
== NULL
);
1140 if (result
->clean
>= 0 && update_worktree_and_index
) {
1141 struct merge_options_internal
*opti
= result
->priv
;
1143 if (checkout(opt
, head
, result
->tree
)) {
1144 /* failure to function */
1149 if (record_conflicted_index_entries(opt
, opt
->repo
->index
,
1151 &opti
->conflicted
)) {
1152 /* failure to function */
1158 if (display_update_msgs
) {
1159 /* TODO: print out CONFLICT and other informational messages. */
1162 merge_finalize(opt
, result
);
1165 void merge_finalize(struct merge_options
*opt
,
1166 struct merge_result
*result
)
1168 struct merge_options_internal
*opti
= result
->priv
;
1170 assert(opt
->priv
== NULL
);
1173 * We marked opti->paths with strdup_strings = 0, so that we
1174 * wouldn't have to make another copy of the fullpath created by
1175 * make_traverse_path from setup_path_info(). But, now that we've
1176 * used it and have no other references to these strings, it is time
1177 * to deallocate them.
1179 free_strmap_strings(&opti
->paths
);
1180 strmap_clear(&opti
->paths
, 1);
1183 * All keys and values in opti->conflicted are a subset of those in
1184 * opti->paths. We don't want to deallocate anything twice, so we
1185 * don't free the keys and we pass 0 for free_values.
1187 strmap_clear(&opti
->conflicted
, 0);
1188 FREE_AND_NULL(opti
);
1191 static void merge_start(struct merge_options
*opt
, struct merge_result
*result
)
1193 /* Sanity checks on opt */
1196 assert(opt
->branch1
&& opt
->branch2
);
1198 assert(opt
->detect_directory_renames
>= MERGE_DIRECTORY_RENAMES_NONE
&&
1199 opt
->detect_directory_renames
<= MERGE_DIRECTORY_RENAMES_TRUE
);
1200 assert(opt
->rename_limit
>= -1);
1201 assert(opt
->rename_score
>= 0 && opt
->rename_score
<= MAX_SCORE
);
1202 assert(opt
->show_rename_progress
>= 0 && opt
->show_rename_progress
<= 1);
1204 assert(opt
->xdl_opts
>= 0);
1205 assert(opt
->recursive_variant
>= MERGE_VARIANT_NORMAL
&&
1206 opt
->recursive_variant
<= MERGE_VARIANT_THEIRS
);
1209 * detect_renames, verbosity, buffer_output, and obuf are ignored
1210 * fields that were used by "recursive" rather than "ort" -- but
1211 * sanity check them anyway.
1213 assert(opt
->detect_renames
>= -1 &&
1214 opt
->detect_renames
<= DIFF_DETECT_COPY
);
1215 assert(opt
->verbosity
>= 0 && opt
->verbosity
<= 5);
1216 assert(opt
->buffer_output
<= 2);
1217 assert(opt
->obuf
.len
== 0);
1219 assert(opt
->priv
== NULL
);
1221 /* Default to histogram diff. Actually, just hardcode it...for now. */
1222 opt
->xdl_opts
= DIFF_WITH_ALG(opt
, HISTOGRAM_DIFF
);
1224 /* Initialization of opt->priv, our internal merge data */
1225 opt
->priv
= xcalloc(1, sizeof(*opt
->priv
));
1228 * Although we initialize opt->priv->paths with strdup_strings=0,
1229 * that's just to avoid making yet another copy of an allocated
1230 * string. Putting the entry into paths means we are taking
1231 * ownership, so we will later free it.
1233 * In contrast, conflicted just has a subset of keys from paths, so
1234 * we don't want to free those (it'd be a duplicate free).
1236 strmap_init_with_options(&opt
->priv
->paths
, NULL
, 0);
1237 strmap_init_with_options(&opt
->priv
->conflicted
, NULL
, 0);
1241 * Originally from merge_trees_internal(); heavily adapted, though.
1243 static void merge_ort_nonrecursive_internal(struct merge_options
*opt
,
1244 struct tree
*merge_base
,
1247 struct merge_result
*result
)
1249 struct object_id working_tree_oid
;
1251 if (collect_merge_info(opt
, merge_base
, side1
, side2
) != 0) {
1253 * TRANSLATORS: The %s arguments are: 1) tree hash of a merge
1254 * base, and 2-3) the trees for the two trees we're merging.
1256 err(opt
, _("collecting merge info failed for trees %s, %s, %s"),
1257 oid_to_hex(&merge_base
->object
.oid
),
1258 oid_to_hex(&side1
->object
.oid
),
1259 oid_to_hex(&side2
->object
.oid
));
1264 result
->clean
= detect_and_process_renames(opt
, merge_base
,
1266 process_entries(opt
, &working_tree_oid
);
1268 /* Set return values */
1269 result
->tree
= parse_tree_indirect(&working_tree_oid
);
1270 /* existence of conflicted entries implies unclean */
1271 result
->clean
&= strmap_empty(&opt
->priv
->conflicted
);
1272 if (!opt
->priv
->call_depth
) {
1273 result
->priv
= opt
->priv
;
1278 void merge_incore_nonrecursive(struct merge_options
*opt
,
1279 struct tree
*merge_base
,
1282 struct merge_result
*result
)
1284 assert(opt
->ancestor
!= NULL
);
1285 merge_start(opt
, result
);
1286 merge_ort_nonrecursive_internal(opt
, merge_base
, side1
, side2
, result
);
1289 void merge_incore_recursive(struct merge_options
*opt
,
1290 struct commit_list
*merge_bases
,
1291 struct commit
*side1
,
1292 struct commit
*side2
,
1293 struct merge_result
*result
)
1295 die("Not yet implemented");