git-remote-hg: add the helper
[git/dscho.git] / match-trees.c
blob26f7ed143e0649b6377ea427b5c57ca7ddb663d3
1 #include "cache.h"
2 #include "tree.h"
3 #include "tree-walk.h"
5 static int score_missing(unsigned mode, const char *path)
7         int score;
9         if (S_ISDIR(mode))
10                 score = -1000;
11         else if (S_ISLNK(mode))
12                 score = -500;
13         else
14                 score = -50;
15         return score;
18 static int score_differs(unsigned mode1, unsigned mode2, const char *path)
20         int score;
22         if (S_ISDIR(mode1) != S_ISDIR(mode2))
23                 score = -100;
24         else if (S_ISLNK(mode1) != S_ISLNK(mode2))
25                 score = -50;
26         else
27                 score = -5;
28         return score;
31 static int score_matches(unsigned mode1, unsigned mode2, const char *path)
33         int score;
35         /* Heh, we found SHA-1 collisions between different kind of objects */
36         if (S_ISDIR(mode1) != S_ISDIR(mode2))
37                 score = -100;
38         else if (S_ISLNK(mode1) != S_ISLNK(mode2))
39                 score = -50;
41         else if (S_ISDIR(mode1))
42                 score = 1000;
43         else if (S_ISLNK(mode1))
44                 score = 500;
45         else
46                 score = 250;
47         return score;
51  * Inspect two trees, and give a score that tells how similar they are.
52  */
53 static int score_trees(const unsigned char *hash1, const unsigned char *hash2)
55         struct tree_desc one;
56         struct tree_desc two;
57         void *one_buf, *two_buf;
58         int score = 0;
59         enum object_type type;
60         unsigned long size;
62         one_buf = read_sha1_file(hash1, &type, &size);
63         if (!one_buf)
64                 die("unable to read tree (%s)", sha1_to_hex(hash1));
65         if (type != OBJ_TREE)
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);
69         if (!two_buf)
70                 die("unable to read tree (%s)", sha1_to_hex(hash2));
71         if (type != OBJ_TREE)
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;
81                 int cmp;
83                 if (one.size)
84                         elem1 = tree_entry_extract(&one, &path1, &mode1);
85                 if (two.size)
86                         elem2 = tree_entry_extract(&two, &path2, &mode2);
88                 if (!one.size) {
89                         /* two has more entries */
90                         score += score_missing(mode2, path2);
91                         update_tree_entry(&two);
92                         continue;
93                 }
94                 if (!two.size) {
95                         /* two lacks this entry */
96                         score += score_missing(mode1, path1);
97                         update_tree_entry(&one);
98                         continue;
99                 }
100                 cmp = base_name_compare(path1, strlen(path1), mode1,
101                                         path2, strlen(path2), mode2);
102                 if (cmp < 0) {
103                         /* path1 does not appear in two */
104                         score += score_missing(mode1, path1);
105                         update_tree_entry(&one);
106                         continue;
107                 }
108                 else if (cmp > 0) {
109                         /* path2 does not appear in one */
110                         score += score_missing(mode2, path2);
111                         update_tree_entry(&two);
112                         continue;
113                 }
114                 else if (hashcmp(elem1, elem2))
115                         /* they are different */
116                         score += score_differs(mode1, mode2, path1);
117                 else
118                         /* same subtree or blob */
119                         score += score_matches(mode1, mode2, path1);
120                 update_tree_entry(&one);
121                 update_tree_entry(&two);
122         }
123         free(one_buf);
124         free(two_buf);
125         return score;
129  * Match one itself and its subtrees with two and pick the best match.
130  */
131 static void match_trees(const unsigned char *hash1,
132                         const unsigned char *hash2,
133                         int *best_score,
134                         char **best_match,
135                         const char *base,
136                         int recurse_limit)
138         struct tree_desc one;
139         void *one_buf;
140         enum object_type type;
141         unsigned long size;
143         one_buf = read_sha1_file(hash1, &type, &size);
144         if (!one_buf)
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);
150         while (one.size) {
151                 const char *path;
152                 const unsigned char *elem;
153                 unsigned mode;
154                 int score;
156                 elem = tree_entry_extract(&one, &path, &mode);
157                 if (!S_ISDIR(mode))
158                         goto next;
159                 score = score_trees(elem, hash2);
160                 if (*best_score < score) {
161                         char *newpath;
162                         newpath = xmalloc(strlen(base) + strlen(path) + 1);
163                         sprintf(newpath, "%s%s", base, path);
164                         free(*best_match);
165                         *best_match = newpath;
166                         *best_score = score;
167                 }
168                 if (recurse_limit) {
169                         char *newbase;
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);
174                         free(newbase);
175                 }
177         next:
178                 update_tree_entry(&one);
179         }
180         free(one_buf);
184  * A tree "hash1" has a subdirectory at "prefix".  Come up with a
185  * tree object by replacing it with another tree "hash2".
186  */
187 static int splice_tree(const unsigned char *hash1,
188                        const char *prefix,
189                        const unsigned char *hash2,
190                        unsigned char *result)
192         char *subpath;
193         int toplen;
194         char *buf;
195         unsigned long sz;
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;
201         int status;
203         subpath = strchr(prefix, '/');
204         if (!subpath)
205                 toplen = strlen(prefix);
206         else {
207                 toplen = subpath - prefix;
208                 subpath++;
209         }
211         buf = read_sha1_file(hash1, &type, &sz);
212         if (!buf)
213                 die("cannot read tree %s", sha1_to_hex(hash1));
214         init_tree_desc(&desc, buf, sz);
216         rewrite_here = NULL;
217         while (desc.size) {
218                 const char *name;
219                 unsigned mode;
220                 const unsigned char *sha1;
222                 sha1 = tree_entry_extract(&desc, &name, &mode);
223                 if (strlen(name) == toplen &&
224                     !memcmp(name, prefix, toplen)) {
225                         if (!S_ISDIR(mode))
226                                 die("entry %s in tree %s is not a tree",
227                                     name, sha1_to_hex(hash1));
228                         rewrite_here = (unsigned char *) sha1;
229                         break;
230                 }
231                 update_tree_entry(&desc);
232         }
233         if (!rewrite_here)
234                 die("entry %.*s not found in tree %s",
235                     toplen, prefix, sha1_to_hex(hash1));
236         if (subpath) {
237                 status = splice_tree(rewrite_here, subpath, hash2, subtree);
238                 if (status)
239                         return status;
240                 rewrite_with = subtree;
241         }
242         else
243                 rewrite_with = hash2;
244         hashcpy(rewrite_here, rewrite_with);
245         status = write_sha1_file(buf, sz, tree_type, result);
246         free(buf);
247         return status;
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
256  * subtree of it.
257  */
258 void shift_tree(const unsigned char *hash1,
259                 const unsigned char *hash2,
260                 unsigned char *shifted,
261                 int depth_limit)
263         char *add_prefix;
264         char *del_prefix;
265         int add_score, del_score;
267         /*
268          * NEEDSWORK: this limits the recursion depth to hardcoded
269          * value '2' to avoid excessive overhead.
270          */
271         if (!depth_limit)
272                 depth_limit = 2;
274         add_score = del_score = score_trees(hash1, hash2);
275         add_prefix = xcalloc(1, 1);
276         del_prefix = xcalloc(1, 1);
278         /*
279          * See if one's subtree resembles two; if so we need to prefix
280          * two with a few fake trees to match the prefix.
281          */
282         match_trees(hash1, hash2, &add_score, &add_prefix, "", depth_limit);
284         /*
285          * See if two's subtree resembles one; if so we need to
286          * pick only subtree of two.
287          */
288         match_trees(hash2, hash1, &del_score, &del_prefix, "", depth_limit);
290         /* Assume we do not have to do any shifting */
291         hashcpy(shifted, hash2);
293         if (add_score < del_score) {
294                 /* We need to pick a subtree of two */
295                 unsigned mode;
297                 if (!*del_prefix)
298                         return;
300                 if (get_tree_entry(hash2, del_prefix, shifted, &mode))
301                         die("cannot find path %s in tree %s",
302                             del_prefix, sha1_to_hex(hash2));
303                 return;
304         }
306         if (!*add_prefix)
307                 return;
309         splice_tree(hash1, add_prefix, hash2, shifted);
313  * The user says the trees will be shifted by this much.
314  * Unfortunately we cannot fundamentally tell which one to
315  * be prefixed, as recursive merge can work in either direction.
316  */
317 void shift_tree_by(const unsigned char *hash1,
318                    const unsigned char *hash2,
319                    unsigned char *shifted,
320                    const char *shift_prefix)
322         unsigned char sub1[20], sub2[20];
323         unsigned mode1, mode2;
324         unsigned candidate = 0;
326         /* Can hash2 be a tree at shift_prefix in tree hash1? */
327         if (!get_tree_entry(hash1, shift_prefix, sub1, &mode1) &&
328             S_ISDIR(mode1))
329                 candidate |= 1;
331         /* Can hash1 be a tree at shift_prefix in tree hash2? */
332         if (!get_tree_entry(hash2, shift_prefix, sub2, &mode2) &&
333             S_ISDIR(mode2))
334                 candidate |= 2;
336         if (candidate == 3) {
337                 /* Both are plausible -- we need to evaluate the score */
338                 int best_score = score_trees(hash1, hash2);
339                 int score;
341                 candidate = 0;
342                 score = score_trees(sub1, hash2);
343                 if (score > best_score) {
344                         candidate = 1;
345                         best_score = score;
346                 }
347                 score = score_trees(sub2, hash1);
348                 if (score > best_score)
349                         candidate = 2;
350         }
352         if (!candidate) {
353                 /* Neither is plausible -- do not shift */
354                 hashcpy(shifted, hash2);
355                 return;
356         }
358         if (candidate == 1)
359                 /*
360                  * shift tree2 down by adding shift_prefix above it
361                  * to match tree1.
362                  */
363                 splice_tree(hash1, shift_prefix, hash2, shifted);
364         else
365                 /*
366                  * shift tree2 up by removing shift_prefix from it
367                  * to match tree1.
368                  */
369                 hashcpy(shifted, sub2);