]>
Commit | Line | Data |
---|---|---|
17e5574b EN |
1 | /* |
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 | |
4 | * to replace | |
5 | * | |
6 | * git merge [-s recursive] | |
7 | * | |
8 | * with | |
9 | * | |
10 | * git merge -s ort | |
11 | * | |
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"?) | |
15 | */ | |
16 | ||
17 | #include "cache.h" | |
18 | #include "merge-ort.h" | |
19 | ||
5b59c3db | 20 | #include "strmap.h" |
231e2dd4 | 21 | #include "tree.h" |
5b59c3db EN |
22 | |
23 | struct merge_options_internal { | |
24 | /* | |
25 | * paths: primary data structure in all of merge ort. | |
26 | * | |
27 | * The keys of paths: | |
28 | * * are full relative paths from the toplevel of the repository | |
29 | * (e.g. "drivers/firmware/raspberrypi.c"). | |
30 | * * store all relevant paths in the repo, both directories and | |
31 | * files (e.g. drivers, drivers/firmware would also be included) | |
32 | * * these keys serve to intern all the path strings, which allows | |
33 | * us to do pointer comparison on directory names instead of | |
34 | * strcmp; we just have to be careful to use the interned strings. | |
35 | * | |
36 | * The values of paths: | |
37 | * * either a pointer to a merged_info, or a conflict_info struct | |
38 | * * merged_info contains all relevant information for a | |
39 | * non-conflicted entry. | |
40 | * * conflict_info contains a merged_info, plus any additional | |
41 | * information about a conflict such as the higher orders stages | |
42 | * involved and the names of the paths those came from (handy | |
43 | * once renames get involved). | |
44 | * * a path may start "conflicted" (i.e. point to a conflict_info) | |
45 | * and then a later step (e.g. three-way content merge) determines | |
46 | * it can be cleanly merged, at which point it'll be marked clean | |
47 | * and the algorithm will ignore any data outside the contained | |
48 | * merged_info for that entry | |
49 | * * If an entry remains conflicted, the merged_info portion of a | |
50 | * conflict_info will later be filled with whatever version of | |
51 | * the file should be placed in the working directory (e.g. an | |
52 | * as-merged-as-possible variation that contains conflict markers). | |
53 | */ | |
54 | struct strmap paths; | |
55 | ||
56 | /* | |
57 | * conflicted: a subset of keys->values from "paths" | |
58 | * | |
59 | * conflicted is basically an optimization between process_entries() | |
60 | * and record_conflicted_index_entries(); the latter could loop over | |
61 | * ALL the entries in paths AGAIN and look for the ones that are | |
62 | * still conflicted, but since process_entries() has to loop over | |
63 | * all of them, it saves the ones it couldn't resolve in this strmap | |
64 | * so that record_conflicted_index_entries() can iterate just the | |
65 | * relevant entries. | |
66 | */ | |
67 | struct strmap conflicted; | |
68 | ||
69 | /* | |
70 | * current_dir_name: temporary var used in collect_merge_info_callback() | |
71 | * | |
72 | * Used to set merged_info.directory_name; see documentation for that | |
73 | * variable and the requirements placed on that field. | |
74 | */ | |
75 | const char *current_dir_name; | |
76 | ||
77 | /* call_depth: recursion level counter for merging merge bases */ | |
78 | int call_depth; | |
79 | }; | |
80 | ||
81 | struct version_info { | |
82 | struct object_id oid; | |
83 | unsigned short mode; | |
84 | }; | |
85 | ||
86 | struct merged_info { | |
87 | /* if is_null, ignore result. otherwise result has oid & mode */ | |
88 | struct version_info result; | |
89 | unsigned is_null:1; | |
90 | ||
91 | /* | |
92 | * clean: whether the path in question is cleanly merged. | |
93 | * | |
94 | * see conflict_info.merged for more details. | |
95 | */ | |
96 | unsigned clean:1; | |
97 | ||
98 | /* | |
99 | * basename_offset: offset of basename of path. | |
100 | * | |
101 | * perf optimization to avoid recomputing offset of final '/' | |
102 | * character in pathname (0 if no '/' in pathname). | |
103 | */ | |
104 | size_t basename_offset; | |
105 | ||
106 | /* | |
107 | * directory_name: containing directory name. | |
108 | * | |
109 | * Note that we assume directory_name is constructed such that | |
110 | * strcmp(dir1_name, dir2_name) == 0 iff dir1_name == dir2_name, | |
111 | * i.e. string equality is equivalent to pointer equality. For this | |
112 | * to hold, we have to be careful setting directory_name. | |
113 | */ | |
114 | const char *directory_name; | |
115 | }; | |
116 | ||
117 | struct conflict_info { | |
118 | /* | |
119 | * merged: the version of the path that will be written to working tree | |
120 | * | |
121 | * WARNING: It is critical to check merged.clean and ensure it is 0 | |
122 | * before reading any conflict_info fields outside of merged. | |
123 | * Allocated merge_info structs will always have clean set to 1. | |
124 | * Allocated conflict_info structs will have merged.clean set to 0 | |
125 | * initially. The merged.clean field is how we know if it is safe | |
126 | * to access other parts of conflict_info besides merged; if a | |
127 | * conflict_info's merged.clean is changed to 1, the rest of the | |
128 | * algorithm is not allowed to look at anything outside of the | |
129 | * merged member anymore. | |
130 | */ | |
131 | struct merged_info merged; | |
132 | ||
133 | /* oids & modes from each of the three trees for this path */ | |
134 | struct version_info stages[3]; | |
135 | ||
136 | /* pathnames for each stage; may differ due to rename detection */ | |
137 | const char *pathnames[3]; | |
138 | ||
139 | /* Whether this path is/was involved in a directory/file conflict */ | |
140 | unsigned df_conflict:1; | |
141 | ||
142 | /* | |
143 | * For filemask and dirmask, the ith bit corresponds to whether the | |
144 | * ith entry is a file (filemask) or a directory (dirmask). Thus, | |
145 | * filemask & dirmask is always zero, and filemask | dirmask is at | |
146 | * most 7 but can be less when a path does not appear as either a | |
147 | * file or a directory on at least one side of history. | |
148 | * | |
149 | * Note that these masks are related to enum merge_side, as the ith | |
150 | * entry corresponds to side i. | |
151 | * | |
152 | * These values come from a traverse_trees() call; more info may be | |
153 | * found looking at tree-walk.h's struct traverse_info, | |
154 | * particularly the documentation above the "fn" member (note that | |
155 | * filemask = mask & ~dirmask from that documentation). | |
156 | */ | |
157 | unsigned filemask:3; | |
158 | unsigned dirmask:3; | |
159 | ||
160 | /* | |
161 | * Optimization to track which stages match, to avoid the need to | |
162 | * recompute it in multiple steps. Either 0 or at least 2 bits are | |
163 | * set; if at least 2 bits are set, their corresponding stages match. | |
164 | */ | |
165 | unsigned match_mask:3; | |
166 | }; | |
167 | ||
231e2dd4 EN |
168 | static int collect_merge_info(struct merge_options *opt, |
169 | struct tree *merge_base, | |
170 | struct tree *side1, | |
171 | struct tree *side2) | |
172 | { | |
173 | /* TODO: Implement this using traverse_trees() */ | |
174 | die("Not yet implemented."); | |
175 | } | |
176 | ||
177 | static int detect_and_process_renames(struct merge_options *opt, | |
178 | struct tree *merge_base, | |
179 | struct tree *side1, | |
180 | struct tree *side2) | |
181 | { | |
182 | int clean = 1; | |
183 | ||
184 | /* | |
185 | * Rename detection works by detecting file similarity. Here we use | |
186 | * a really easy-to-implement scheme: files are similar IFF they have | |
187 | * the same filename. Therefore, by this scheme, there are no renames. | |
188 | * | |
189 | * TODO: Actually implement a real rename detection scheme. | |
190 | */ | |
191 | return clean; | |
192 | } | |
193 | ||
194 | static void process_entries(struct merge_options *opt, | |
195 | struct object_id *result_oid) | |
196 | { | |
197 | die("Not yet implemented."); | |
198 | } | |
199 | ||
17e5574b EN |
200 | void merge_switch_to_result(struct merge_options *opt, |
201 | struct tree *head, | |
202 | struct merge_result *result, | |
203 | int update_worktree_and_index, | |
204 | int display_update_msgs) | |
205 | { | |
206 | die("Not yet implemented"); | |
207 | merge_finalize(opt, result); | |
208 | } | |
209 | ||
210 | void merge_finalize(struct merge_options *opt, | |
211 | struct merge_result *result) | |
212 | { | |
213 | die("Not yet implemented"); | |
214 | } | |
215 | ||
231e2dd4 EN |
216 | static void merge_start(struct merge_options *opt, struct merge_result *result) |
217 | { | |
218 | die("Not yet implemented."); | |
219 | } | |
220 | ||
221 | /* | |
222 | * Originally from merge_trees_internal(); heavily adapted, though. | |
223 | */ | |
224 | static void merge_ort_nonrecursive_internal(struct merge_options *opt, | |
225 | struct tree *merge_base, | |
226 | struct tree *side1, | |
227 | struct tree *side2, | |
228 | struct merge_result *result) | |
229 | { | |
230 | struct object_id working_tree_oid; | |
231 | ||
232 | collect_merge_info(opt, merge_base, side1, side2); | |
233 | result->clean = detect_and_process_renames(opt, merge_base, | |
234 | side1, side2); | |
235 | process_entries(opt, &working_tree_oid); | |
236 | ||
237 | /* Set return values */ | |
238 | result->tree = parse_tree_indirect(&working_tree_oid); | |
239 | /* existence of conflicted entries implies unclean */ | |
240 | result->clean &= strmap_empty(&opt->priv->conflicted); | |
241 | if (!opt->priv->call_depth) { | |
242 | result->priv = opt->priv; | |
243 | opt->priv = NULL; | |
244 | } | |
245 | } | |
246 | ||
17e5574b EN |
247 | void merge_incore_nonrecursive(struct merge_options *opt, |
248 | struct tree *merge_base, | |
249 | struct tree *side1, | |
250 | struct tree *side2, | |
251 | struct merge_result *result) | |
252 | { | |
231e2dd4 EN |
253 | assert(opt->ancestor != NULL); |
254 | merge_start(opt, result); | |
255 | merge_ort_nonrecursive_internal(opt, merge_base, side1, side2, result); | |
17e5574b EN |
256 | } |
257 | ||
258 | void merge_incore_recursive(struct merge_options *opt, | |
259 | struct commit_list *merge_bases, | |
260 | struct commit *side1, | |
261 | struct commit *side2, | |
262 | struct merge_result *result) | |
263 | { | |
264 | die("Not yet implemented"); | |
265 | } |