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"
24 #include "xdiff-interface.h"
27 * We have many arrays of size 3. Whenever we have such an array, the
28 * indices refer to one of the sides of the three-way merge. This is so
29 * pervasive that the constants 0, 1, and 2 are used in many places in the
30 * code (especially in arithmetic operations to find the other side's index
31 * or to compute a relevant mask), but sometimes these enum names are used
32 * to aid code clarity.
34 * See also 'filemask' and 'dirmask' in struct conflict_info; the "ith side"
35 * referred to there is one of these three sides.
43 struct merge_options_internal
{
45 * paths: primary data structure in all of merge ort.
48 * * are full relative paths from the toplevel of the repository
49 * (e.g. "drivers/firmware/raspberrypi.c").
50 * * store all relevant paths in the repo, both directories and
51 * files (e.g. drivers, drivers/firmware would also be included)
52 * * these keys serve to intern all the path strings, which allows
53 * us to do pointer comparison on directory names instead of
54 * strcmp; we just have to be careful to use the interned strings.
56 * The values of paths:
57 * * either a pointer to a merged_info, or a conflict_info struct
58 * * merged_info contains all relevant information for a
59 * non-conflicted entry.
60 * * conflict_info contains a merged_info, plus any additional
61 * information about a conflict such as the higher orders stages
62 * involved and the names of the paths those came from (handy
63 * once renames get involved).
64 * * a path may start "conflicted" (i.e. point to a conflict_info)
65 * and then a later step (e.g. three-way content merge) determines
66 * it can be cleanly merged, at which point it'll be marked clean
67 * and the algorithm will ignore any data outside the contained
68 * merged_info for that entry
69 * * If an entry remains conflicted, the merged_info portion of a
70 * conflict_info will later be filled with whatever version of
71 * the file should be placed in the working directory (e.g. an
72 * as-merged-as-possible variation that contains conflict markers).
77 * conflicted: a subset of keys->values from "paths"
79 * conflicted is basically an optimization between process_entries()
80 * and record_conflicted_index_entries(); the latter could loop over
81 * ALL the entries in paths AGAIN and look for the ones that are
82 * still conflicted, but since process_entries() has to loop over
83 * all of them, it saves the ones it couldn't resolve in this strmap
84 * so that record_conflicted_index_entries() can iterate just the
87 struct strmap conflicted
;
90 * current_dir_name: temporary var used in collect_merge_info_callback()
92 * Used to set merged_info.directory_name; see documentation for that
93 * variable and the requirements placed on that field.
95 const char *current_dir_name
;
97 /* call_depth: recursion level counter for merging merge bases */
101 struct version_info
{
102 struct object_id oid
;
107 /* if is_null, ignore result. otherwise result has oid & mode */
108 struct version_info result
;
112 * clean: whether the path in question is cleanly merged.
114 * see conflict_info.merged for more details.
119 * basename_offset: offset of basename of path.
121 * perf optimization to avoid recomputing offset of final '/'
122 * character in pathname (0 if no '/' in pathname).
124 size_t basename_offset
;
127 * directory_name: containing directory name.
129 * Note that we assume directory_name is constructed such that
130 * strcmp(dir1_name, dir2_name) == 0 iff dir1_name == dir2_name,
131 * i.e. string equality is equivalent to pointer equality. For this
132 * to hold, we have to be careful setting directory_name.
134 const char *directory_name
;
137 struct conflict_info
{
139 * merged: the version of the path that will be written to working tree
141 * WARNING: It is critical to check merged.clean and ensure it is 0
142 * before reading any conflict_info fields outside of merged.
143 * Allocated merge_info structs will always have clean set to 1.
144 * Allocated conflict_info structs will have merged.clean set to 0
145 * initially. The merged.clean field is how we know if it is safe
146 * to access other parts of conflict_info besides merged; if a
147 * conflict_info's merged.clean is changed to 1, the rest of the
148 * algorithm is not allowed to look at anything outside of the
149 * merged member anymore.
151 struct merged_info merged
;
153 /* oids & modes from each of the three trees for this path */
154 struct version_info stages
[3];
156 /* pathnames for each stage; may differ due to rename detection */
157 const char *pathnames
[3];
159 /* Whether this path is/was involved in a directory/file conflict */
160 unsigned df_conflict
:1;
163 * For filemask and dirmask, the ith bit corresponds to whether the
164 * ith entry is a file (filemask) or a directory (dirmask). Thus,
165 * filemask & dirmask is always zero, and filemask | dirmask is at
166 * most 7 but can be less when a path does not appear as either a
167 * file or a directory on at least one side of history.
169 * Note that these masks are related to enum merge_side, as the ith
170 * entry corresponds to side i.
172 * These values come from a traverse_trees() call; more info may be
173 * found looking at tree-walk.h's struct traverse_info,
174 * particularly the documentation above the "fn" member (note that
175 * filemask = mask & ~dirmask from that documentation).
181 * Optimization to track which stages match, to avoid the need to
182 * recompute it in multiple steps. Either 0 or at least 2 bits are
183 * set; if at least 2 bits are set, their corresponding stages match.
185 unsigned match_mask
:3;
188 static int err(struct merge_options
*opt
, const char *err
, ...)
191 struct strbuf sb
= STRBUF_INIT
;
193 strbuf_addstr(&sb
, "error: ");
194 va_start(params
, err
);
195 strbuf_vaddf(&sb
, err
, params
);
204 static int collect_merge_info_callback(int n
,
206 unsigned long dirmask
,
207 struct name_entry
*names
,
208 struct traverse_info
*info
)
212 * common ancestor (mbase) has mask 1, and stored in index 0 of names
213 * head of side 1 (side1) has mask 2, and stored in index 1 of names
214 * head of side 2 (side2) has mask 4, and stored in index 2 of names
216 struct merge_options
*opt
= info
->data
;
217 struct merge_options_internal
*opti
= opt
->priv
;
218 struct conflict_info
*ci
;
219 struct name_entry
*p
;
222 unsigned filemask
= mask
& ~dirmask
;
223 unsigned mbase_null
= !(mask
& 1);
224 unsigned side1_null
= !(mask
& 2);
225 unsigned side2_null
= !(mask
& 4);
226 unsigned side1_matches_mbase
= (!side1_null
&& !mbase_null
&&
227 names
[0].mode
== names
[1].mode
&&
228 oideq(&names
[0].oid
, &names
[1].oid
));
229 unsigned side2_matches_mbase
= (!side2_null
&& !mbase_null
&&
230 names
[0].mode
== names
[2].mode
&&
231 oideq(&names
[0].oid
, &names
[2].oid
));
232 unsigned sides_match
= (!side1_null
&& !side2_null
&&
233 names
[1].mode
== names
[2].mode
&&
234 oideq(&names
[1].oid
, &names
[2].oid
));
236 /* n = 3 is a fundamental assumption. */
238 BUG("Called collect_merge_info_callback wrong");
241 * A bunch of sanity checks verifying that traverse_trees() calls
242 * us the way I expect. Could just remove these at some point,
243 * though maybe they are helpful to future code readers.
245 assert(mbase_null
== is_null_oid(&names
[0].oid
));
246 assert(side1_null
== is_null_oid(&names
[1].oid
));
247 assert(side2_null
== is_null_oid(&names
[2].oid
));
248 assert(!mbase_null
|| !side1_null
|| !side2_null
);
249 assert(mask
> 0 && mask
< 8);
252 * Get the name of the relevant filepath, which we'll pass to
253 * setup_path_info() for tracking.
258 len
= traverse_path_len(info
, p
->pathlen
);
260 /* +1 in both of the following lines to include the NUL byte */
261 fullpath
= xmalloc(len
+ 1);
262 make_traverse_path(fullpath
, len
+ 1, info
, p
->path
, p
->pathlen
);
265 * TODO: record information about the path other than all zeros,
266 * so we can resolve later in process_entries.
268 ci
= xcalloc(1, sizeof(struct conflict_info
));
269 strmap_put(&opti
->paths
, fullpath
, ci
);
271 /* If dirmask, recurse into subdirectories */
273 struct traverse_info newinfo
;
274 struct tree_desc t
[3];
275 void *buf
[3] = {NULL
, NULL
, NULL
};
276 const char *original_dir_name
;
279 ci
->match_mask
&= filemask
;
282 newinfo
.name
= p
->path
;
283 newinfo
.namelen
= p
->pathlen
;
284 newinfo
.pathlen
= st_add3(newinfo
.pathlen
, p
->pathlen
, 1);
286 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++) {
287 if (i
== 1 && side1_matches_mbase
)
289 else if (i
== 2 && side2_matches_mbase
)
291 else if (i
== 2 && sides_match
)
294 const struct object_id
*oid
= NULL
;
297 buf
[i
] = fill_tree_descriptor(opt
->repo
,
303 original_dir_name
= opti
->current_dir_name
;
304 opti
->current_dir_name
= fullpath
;
305 ret
= traverse_trees(NULL
, 3, t
, &newinfo
);
306 opti
->current_dir_name
= original_dir_name
;
308 for (i
= MERGE_BASE
; i
<= MERGE_SIDE2
; i
++)
318 static int collect_merge_info(struct merge_options
*opt
,
319 struct tree
*merge_base
,
324 struct tree_desc t
[3];
325 struct traverse_info info
;
326 const char *toplevel_dir_placeholder
= "";
328 opt
->priv
->current_dir_name
= toplevel_dir_placeholder
;
329 setup_traverse_info(&info
, toplevel_dir_placeholder
);
330 info
.fn
= collect_merge_info_callback
;
332 info
.show_all_errors
= 1;
334 parse_tree(merge_base
);
337 init_tree_desc(t
+ 0, merge_base
->buffer
, merge_base
->size
);
338 init_tree_desc(t
+ 1, side1
->buffer
, side1
->size
);
339 init_tree_desc(t
+ 2, side2
->buffer
, side2
->size
);
341 ret
= traverse_trees(NULL
, 3, t
, &info
);
346 static int detect_and_process_renames(struct merge_options
*opt
,
347 struct tree
*merge_base
,
354 * Rename detection works by detecting file similarity. Here we use
355 * a really easy-to-implement scheme: files are similar IFF they have
356 * the same filename. Therefore, by this scheme, there are no renames.
358 * TODO: Actually implement a real rename detection scheme.
363 static void process_entries(struct merge_options
*opt
,
364 struct object_id
*result_oid
)
366 die("Not yet implemented.");
369 void merge_switch_to_result(struct merge_options
*opt
,
371 struct merge_result
*result
,
372 int update_worktree_and_index
,
373 int display_update_msgs
)
375 die("Not yet implemented");
376 merge_finalize(opt
, result
);
379 void merge_finalize(struct merge_options
*opt
,
380 struct merge_result
*result
)
382 die("Not yet implemented");
385 static void merge_start(struct merge_options
*opt
, struct merge_result
*result
)
387 /* Sanity checks on opt */
390 assert(opt
->branch1
&& opt
->branch2
);
392 assert(opt
->detect_directory_renames
>= MERGE_DIRECTORY_RENAMES_NONE
&&
393 opt
->detect_directory_renames
<= MERGE_DIRECTORY_RENAMES_TRUE
);
394 assert(opt
->rename_limit
>= -1);
395 assert(opt
->rename_score
>= 0 && opt
->rename_score
<= MAX_SCORE
);
396 assert(opt
->show_rename_progress
>= 0 && opt
->show_rename_progress
<= 1);
398 assert(opt
->xdl_opts
>= 0);
399 assert(opt
->recursive_variant
>= MERGE_VARIANT_NORMAL
&&
400 opt
->recursive_variant
<= MERGE_VARIANT_THEIRS
);
403 * detect_renames, verbosity, buffer_output, and obuf are ignored
404 * fields that were used by "recursive" rather than "ort" -- but
405 * sanity check them anyway.
407 assert(opt
->detect_renames
>= -1 &&
408 opt
->detect_renames
<= DIFF_DETECT_COPY
);
409 assert(opt
->verbosity
>= 0 && opt
->verbosity
<= 5);
410 assert(opt
->buffer_output
<= 2);
411 assert(opt
->obuf
.len
== 0);
413 assert(opt
->priv
== NULL
);
415 /* Default to histogram diff. Actually, just hardcode it...for now. */
416 opt
->xdl_opts
= DIFF_WITH_ALG(opt
, HISTOGRAM_DIFF
);
418 /* Initialization of opt->priv, our internal merge data */
419 opt
->priv
= xcalloc(1, sizeof(*opt
->priv
));
422 * Although we initialize opt->priv->paths with strdup_strings=0,
423 * that's just to avoid making yet another copy of an allocated
424 * string. Putting the entry into paths means we are taking
425 * ownership, so we will later free it.
427 * In contrast, conflicted just has a subset of keys from paths, so
428 * we don't want to free those (it'd be a duplicate free).
430 strmap_init_with_options(&opt
->priv
->paths
, NULL
, 0);
431 strmap_init_with_options(&opt
->priv
->conflicted
, NULL
, 0);
435 * Originally from merge_trees_internal(); heavily adapted, though.
437 static void merge_ort_nonrecursive_internal(struct merge_options
*opt
,
438 struct tree
*merge_base
,
441 struct merge_result
*result
)
443 struct object_id working_tree_oid
;
445 if (collect_merge_info(opt
, merge_base
, side1
, side2
) != 0) {
447 * TRANSLATORS: The %s arguments are: 1) tree hash of a merge
448 * base, and 2-3) the trees for the two trees we're merging.
450 err(opt
, _("collecting merge info failed for trees %s, %s, %s"),
451 oid_to_hex(&merge_base
->object
.oid
),
452 oid_to_hex(&side1
->object
.oid
),
453 oid_to_hex(&side2
->object
.oid
));
458 result
->clean
= detect_and_process_renames(opt
, merge_base
,
460 process_entries(opt
, &working_tree_oid
);
462 /* Set return values */
463 result
->tree
= parse_tree_indirect(&working_tree_oid
);
464 /* existence of conflicted entries implies unclean */
465 result
->clean
&= strmap_empty(&opt
->priv
->conflicted
);
466 if (!opt
->priv
->call_depth
) {
467 result
->priv
= opt
->priv
;
472 void merge_incore_nonrecursive(struct merge_options
*opt
,
473 struct tree
*merge_base
,
476 struct merge_result
*result
)
478 assert(opt
->ancestor
!= NULL
);
479 merge_start(opt
, result
);
480 merge_ort_nonrecursive_internal(opt
, merge_base
, side1
, side2
, result
);
483 void merge_incore_recursive(struct merge_options
*opt
,
484 struct commit_list
*merge_bases
,
485 struct commit
*side1
,
486 struct commit
*side2
,
487 struct merge_result
*result
)
489 die("Not yet implemented");