5 static int score_missing(unsigned mode
, const char *path
)
11 else if (S_ISLNK(mode
))
18 static int score_differs(unsigned mode1
, unsigned mode2
, const char *path
)
22 if (S_ISDIR(mode1
) != S_ISDIR(mode2
))
24 else if (S_ISLNK(mode1
) != S_ISLNK(mode2
))
31 static int score_matches(unsigned mode1
, unsigned mode2
, const char *path
)
35 /* Heh, we found SHA-1 collisions between different kind of objects */
36 if (S_ISDIR(mode1
) != S_ISDIR(mode2
))
38 else if (S_ISLNK(mode1
) != S_ISLNK(mode2
))
41 else if (S_ISDIR(mode1
))
43 else if (S_ISLNK(mode1
))
50 static void *fill_tree_desc_strict(struct tree_desc
*desc
,
51 const struct object_id
*hash
)
54 enum object_type type
;
57 buffer
= read_sha1_file(hash
->hash
, &type
, &size
);
59 die("unable to read tree (%s)", oid_to_hex(hash
));
61 die("%s is not a tree", oid_to_hex(hash
));
62 init_tree_desc(desc
, buffer
, size
);
66 static int base_name_entries_compare(const struct name_entry
*a
,
67 const struct name_entry
*b
)
69 return base_name_compare(a
->path
, tree_entry_len(a
), a
->mode
,
70 b
->path
, tree_entry_len(b
), b
->mode
);
74 * Inspect two trees, and give a score that tells how similar they are.
76 static int score_trees(const struct object_id
*hash1
, const struct object_id
*hash2
)
80 void *one_buf
= fill_tree_desc_strict(&one
, hash1
);
81 void *two_buf
= fill_tree_desc_strict(&two
, hash2
);
85 struct name_entry e1
, e2
;
86 int got_entry_from_one
= tree_entry(&one
, &e1
);
87 int got_entry_from_two
= tree_entry(&two
, &e2
);
90 if (got_entry_from_one
&& got_entry_from_two
)
91 cmp
= base_name_entries_compare(&e1
, &e2
);
92 else if (got_entry_from_one
)
93 /* two lacks this entry */
95 else if (got_entry_from_two
)
96 /* two has more entries */
102 /* path1 does not appear in two */
103 score
+= score_missing(e1
.mode
, e1
.path
);
105 /* path2 does not appear in one */
106 score
+= score_missing(e2
.mode
, e2
.path
);
107 else if (oidcmp(e1
.oid
, e2
.oid
))
108 /* they are different */
109 score
+= score_differs(e1
.mode
, e2
.mode
, e1
.path
);
111 /* same subtree or blob */
112 score
+= score_matches(e1
.mode
, e2
.mode
, e1
.path
);
120 * Match one itself and its subtrees with two and pick the best match.
122 static void match_trees(const struct object_id
*hash1
,
123 const struct object_id
*hash2
,
129 struct tree_desc one
;
130 void *one_buf
= fill_tree_desc_strict(&one
, hash1
);
134 const struct object_id
*elem
;
138 elem
= tree_entry_extract(&one
, &path
, &mode
);
141 score
= score_trees(elem
, hash2
);
142 if (*best_score
< score
) {
144 *best_match
= xstrfmt("%s%s", base
, path
);
148 char *newbase
= xstrfmt("%s%s/", base
, path
);
149 match_trees(elem
, hash2
, best_score
, best_match
,
150 newbase
, recurse_limit
- 1);
155 update_tree_entry(&one
);
161 * A tree "oid1" has a subdirectory at "prefix". Come up with a tree object by
162 * replacing it with another tree "oid2".
164 static int splice_tree(const struct object_id
*oid1
, const char *prefix
,
165 const struct object_id
*oid2
, struct object_id
*result
)
171 struct tree_desc desc
;
172 struct object_id
*rewrite_here
;
173 const struct object_id
*rewrite_with
;
174 struct object_id subtree
;
175 enum object_type type
;
178 subpath
= strchrnul(prefix
, '/');
179 toplen
= subpath
- prefix
;
183 buf
= read_sha1_file(oid1
->hash
, &type
, &sz
);
185 die("cannot read tree %s", oid_to_hex(oid1
));
186 init_tree_desc(&desc
, buf
, sz
);
192 const struct object_id
*oid
;
194 oid
= tree_entry_extract(&desc
, &name
, &mode
);
195 if (strlen(name
) == toplen
&&
196 !memcmp(name
, prefix
, toplen
)) {
198 die("entry %s in tree %s is not a tree", name
,
200 rewrite_here
= (struct object_id
*)oid
;
203 update_tree_entry(&desc
);
206 die("entry %.*s not found in tree %s", toplen
, prefix
,
209 status
= splice_tree(rewrite_here
, subpath
, oid2
, &subtree
);
212 rewrite_with
= &subtree
;
216 oidcpy(rewrite_here
, rewrite_with
);
217 status
= write_sha1_file(buf
, sz
, tree_type
, result
->hash
);
223 * We are trying to come up with a merge between one and two that
224 * results in a tree shape similar to one. The tree two might
225 * correspond to a subtree of one, in which case it needs to be
226 * shifted down by prefixing otherwise empty directories. On the
227 * other hand, it could cover tree one and we might need to pick a
230 void shift_tree(const struct object_id
*hash1
,
231 const struct object_id
*hash2
,
232 struct object_id
*shifted
,
237 int add_score
, del_score
;
240 * NEEDSWORK: this limits the recursion depth to hardcoded
241 * value '2' to avoid excessive overhead.
246 add_score
= del_score
= score_trees(hash1
, hash2
);
247 add_prefix
= xcalloc(1, 1);
248 del_prefix
= xcalloc(1, 1);
251 * See if one's subtree resembles two; if so we need to prefix
252 * two with a few fake trees to match the prefix.
254 match_trees(hash1
, hash2
, &add_score
, &add_prefix
, "", depth_limit
);
257 * See if two's subtree resembles one; if so we need to
258 * pick only subtree of two.
260 match_trees(hash2
, hash1
, &del_score
, &del_prefix
, "", depth_limit
);
262 /* Assume we do not have to do any shifting */
263 oidcpy(shifted
, hash2
);
265 if (add_score
< del_score
) {
266 /* We need to pick a subtree of two */
272 if (get_tree_entry(hash2
->hash
, del_prefix
, shifted
->hash
, &mode
))
273 die("cannot find path %s in tree %s",
274 del_prefix
, oid_to_hex(hash2
));
281 splice_tree(hash1
, add_prefix
, hash2
, shifted
);
285 * The user says the trees will be shifted by this much.
286 * Unfortunately we cannot fundamentally tell which one to
287 * be prefixed, as recursive merge can work in either direction.
289 void shift_tree_by(const struct object_id
*hash1
,
290 const struct object_id
*hash2
,
291 struct object_id
*shifted
,
292 const char *shift_prefix
)
294 struct object_id sub1
, sub2
;
295 unsigned mode1
, mode2
;
296 unsigned candidate
= 0;
298 /* Can hash2 be a tree at shift_prefix in tree hash1? */
299 if (!get_tree_entry(hash1
->hash
, shift_prefix
, sub1
.hash
, &mode1
) &&
303 /* Can hash1 be a tree at shift_prefix in tree hash2? */
304 if (!get_tree_entry(hash2
->hash
, shift_prefix
, sub2
.hash
, &mode2
) &&
308 if (candidate
== 3) {
309 /* Both are plausible -- we need to evaluate the score */
310 int best_score
= score_trees(hash1
, hash2
);
314 score
= score_trees(&sub1
, hash2
);
315 if (score
> best_score
) {
319 score
= score_trees(&sub2
, hash1
);
320 if (score
> best_score
)
325 /* Neither is plausible -- do not shift */
326 oidcpy(shifted
, hash2
);
332 * shift tree2 down by adding shift_prefix above it
335 splice_tree(hash1
, shift_prefix
, hash2
, shifted
);
338 * shift tree2 up by removing shift_prefix from it
341 oidcpy(shifted
, &sub2
);