]>
git.ipfire.org Git - thirdparty/git.git/blob - match-trees.c
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
))
51 * Inspect two trees, and give a score that tells how similar they are.
53 static int score_trees(const unsigned char *hash1
, const unsigned char *hash2
)
57 void *one_buf
, *two_buf
;
59 enum object_type type
;
62 one_buf
= read_sha1_file(hash1
, &type
, &size
);
64 die("unable to read tree (%s)", sha1_to_hex(hash1
));
66 die("%s is not a tree", sha1_to_hex(hash1
));
67 init_tree_desc(&one
, one_buf
, size
);
68 two_buf
= read_sha1_file(hash2
, &type
, &size
);
70 die("unable to read tree (%s)", sha1_to_hex(hash2
));
72 die("%s is not a tree", sha1_to_hex(hash2
));
73 init_tree_desc(&two
, two_buf
, size
);
74 while (one
.size
| two
.size
) {
75 const unsigned char *elem1
= elem1
;
76 const unsigned char *elem2
= elem2
;
77 const char *path1
= path1
;
78 const char *path2
= path2
;
79 unsigned mode1
= mode1
;
80 unsigned mode2
= mode2
;
84 elem1
= tree_entry_extract(&one
, &path1
, &mode1
);
86 elem2
= tree_entry_extract(&two
, &path2
, &mode2
);
89 /* two has more entries */
90 score
+= score_missing(mode2
, path2
);
91 update_tree_entry(&two
);
95 /* two lacks this entry */
96 score
+= score_missing(mode1
, path1
);
97 update_tree_entry(&one
);
100 cmp
= base_name_compare(path1
, strlen(path1
), mode1
,
101 path2
, strlen(path2
), mode2
);
103 /* path1 does not appear in two */
104 score
+= score_missing(mode1
, path1
);
105 update_tree_entry(&one
);
109 /* path2 does not appear in one */
110 score
+= score_missing(mode2
, path2
);
111 update_tree_entry(&two
);
114 else if (hashcmp(elem1
, elem2
))
115 /* they are different */
116 score
+= score_differs(mode1
, mode2
, path1
);
118 /* same subtree or blob */
119 score
+= score_matches(mode1
, mode2
, path1
);
120 update_tree_entry(&one
);
121 update_tree_entry(&two
);
129 * Match one itself and its subtrees with two and pick the best match.
131 static void match_trees(const unsigned char *hash1
,
132 const unsigned char *hash2
,
138 struct tree_desc one
;
140 enum object_type type
;
143 one_buf
= read_sha1_file(hash1
, &type
, &size
);
145 die("unable to read tree (%s)", sha1_to_hex(hash1
));
146 if (type
!= OBJ_TREE
)
147 die("%s is not a tree", sha1_to_hex(hash1
));
148 init_tree_desc(&one
, one_buf
, size
);
152 const unsigned char *elem
;
156 elem
= tree_entry_extract(&one
, &path
, &mode
);
159 score
= score_trees(elem
, hash2
);
160 if (*best_score
< score
) {
162 newpath
= xmalloc(strlen(base
) + strlen(path
) + 1);
163 sprintf(newpath
, "%s%s", base
, path
);
165 *best_match
= newpath
;
170 newbase
= xmalloc(strlen(base
) + strlen(path
) + 2);
171 sprintf(newbase
, "%s%s/", base
, path
);
172 match_trees(elem
, hash2
, best_score
, best_match
,
173 newbase
, recurse_limit
- 1);
178 update_tree_entry(&one
);
184 * A tree "hash1" has a subdirectory at "prefix". Come up with a
185 * tree object by replacing it with another tree "hash2".
187 static int splice_tree(const unsigned char *hash1
,
189 const unsigned char *hash2
,
190 unsigned char *result
)
196 struct tree_desc desc
;
197 unsigned char *rewrite_here
;
198 const unsigned char *rewrite_with
;
199 unsigned char subtree
[20];
200 enum object_type type
;
203 subpath
= strchr(prefix
, '/');
205 toplen
= strlen(prefix
);
207 toplen
= subpath
- prefix
;
211 buf
= read_sha1_file(hash1
, &type
, &sz
);
213 die("cannot read tree %s", sha1_to_hex(hash1
));
214 init_tree_desc(&desc
, buf
, sz
);
220 const unsigned char *sha1
;
222 sha1
= tree_entry_extract(&desc
, &name
, &mode
);
223 if (strlen(name
) == toplen
&&
224 !memcmp(name
, prefix
, toplen
)) {
226 die("entry %s in tree %s is not a tree",
227 name
, sha1_to_hex(hash1
));
228 rewrite_here
= (unsigned char *) sha1
;
231 update_tree_entry(&desc
);
234 die("entry %.*s not found in tree %s",
235 toplen
, prefix
, sha1_to_hex(hash1
));
237 status
= splice_tree(rewrite_here
, subpath
, hash2
, subtree
);
240 rewrite_with
= subtree
;
243 rewrite_with
= hash2
;
244 hashcpy(rewrite_here
, rewrite_with
);
245 status
= write_sha1_file(buf
, sz
, tree_type
, result
);
251 * We are trying to come up with a merge between one and two that
252 * results in a tree shape similar to one. The tree two might
253 * correspond to a subtree of one, in which case it needs to be
254 * shifted down by prefixing otherwise empty directories. On the
255 * other hand, it could cover tree one and we might need to pick a
258 void shift_tree(const unsigned char *hash1
,
259 const unsigned char *hash2
,
260 unsigned char *shifted
,
265 int add_score
, del_score
;
267 add_score
= del_score
= score_trees(hash1
, hash2
);
268 add_prefix
= xcalloc(1, 1);
269 del_prefix
= xcalloc(1, 1);
272 * See if one's subtree resembles two; if so we need to prefix
273 * two with a few fake trees to match the prefix.
275 match_trees(hash1
, hash2
, &add_score
, &add_prefix
, "", depth_limit
);
278 * See if two's subtree resembles one; if so we need to
279 * pick only subtree of two.
281 match_trees(hash2
, hash1
, &del_score
, &del_prefix
, "", depth_limit
);
283 /* Assume we do not have to do any shifting */
284 hashcpy(shifted
, hash2
);
286 if (add_score
< del_score
) {
287 /* We need to pick a subtree of two */
293 if (get_tree_entry(hash2
, del_prefix
, shifted
, &mode
))
294 die("cannot find path %s in tree %s",
295 del_prefix
, sha1_to_hex(hash2
));
302 splice_tree(hash1
, add_prefix
, hash2
, shifted
);