THIS IS A TEST INSTANCE ONLY! REPOSITORIES CAN BE DELETED AT ANY TIME!

Git Source Code Mirror - This is a publish-only repository and all pull requests are ignored. Please follow Documentation/SubmittingPatches procedure for any of your improvements.
git
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

366 lines
8.5KB

  1. #include "cache.h"
  2. #include "tree.h"
  3. #include "tree-walk.h"
  4. #include "object-store.h"
  5. static int score_missing(unsigned mode)
  6. {
  7. int score;
  8. if (S_ISDIR(mode))
  9. score = -1000;
  10. else if (S_ISLNK(mode))
  11. score = -500;
  12. else
  13. score = -50;
  14. return score;
  15. }
  16. static int score_differs(unsigned mode1, unsigned mode2)
  17. {
  18. int score;
  19. if (S_ISDIR(mode1) != S_ISDIR(mode2))
  20. score = -100;
  21. else if (S_ISLNK(mode1) != S_ISLNK(mode2))
  22. score = -50;
  23. else
  24. score = -5;
  25. return score;
  26. }
  27. static int score_matches(unsigned mode1, unsigned mode2)
  28. {
  29. int score;
  30. /* Heh, we found SHA-1 collisions between different kind of objects */
  31. if (S_ISDIR(mode1) != S_ISDIR(mode2))
  32. score = -100;
  33. else if (S_ISLNK(mode1) != S_ISLNK(mode2))
  34. score = -50;
  35. else if (S_ISDIR(mode1))
  36. score = 1000;
  37. else if (S_ISLNK(mode1))
  38. score = 500;
  39. else
  40. score = 250;
  41. return score;
  42. }
  43. static void *fill_tree_desc_strict(struct tree_desc *desc,
  44. const struct object_id *hash)
  45. {
  46. void *buffer;
  47. enum object_type type;
  48. unsigned long size;
  49. buffer = read_object_file(hash, &type, &size);
  50. if (!buffer)
  51. die("unable to read tree (%s)", oid_to_hex(hash));
  52. if (type != OBJ_TREE)
  53. die("%s is not a tree", oid_to_hex(hash));
  54. init_tree_desc(desc, buffer, size);
  55. return buffer;
  56. }
  57. static int base_name_entries_compare(const struct name_entry *a,
  58. const struct name_entry *b)
  59. {
  60. return base_name_compare(a->path, tree_entry_len(a), a->mode,
  61. b->path, tree_entry_len(b), b->mode);
  62. }
  63. /*
  64. * Inspect two trees, and give a score that tells how similar they are.
  65. */
  66. static int score_trees(const struct object_id *hash1, const struct object_id *hash2)
  67. {
  68. struct tree_desc one;
  69. struct tree_desc two;
  70. void *one_buf = fill_tree_desc_strict(&one, hash1);
  71. void *two_buf = fill_tree_desc_strict(&two, hash2);
  72. int score = 0;
  73. for (;;) {
  74. int cmp;
  75. if (one.size && two.size)
  76. cmp = base_name_entries_compare(&one.entry, &two.entry);
  77. else if (one.size)
  78. /* two lacks this entry */
  79. cmp = -1;
  80. else if (two.size)
  81. /* two has more entries */
  82. cmp = 1;
  83. else
  84. break;
  85. if (cmp < 0) {
  86. /* path1 does not appear in two */
  87. score += score_missing(one.entry.mode);
  88. update_tree_entry(&one);
  89. } else if (cmp > 0) {
  90. /* path2 does not appear in one */
  91. score += score_missing(two.entry.mode);
  92. update_tree_entry(&two);
  93. } else {
  94. /* path appears in both */
  95. if (!oideq(&one.entry.oid, &two.entry.oid)) {
  96. /* they are different */
  97. score += score_differs(one.entry.mode,
  98. two.entry.mode);
  99. } else {
  100. /* same subtree or blob */
  101. score += score_matches(one.entry.mode,
  102. two.entry.mode);
  103. }
  104. update_tree_entry(&one);
  105. update_tree_entry(&two);
  106. }
  107. }
  108. free(one_buf);
  109. free(two_buf);
  110. return score;
  111. }
  112. /*
  113. * Match one itself and its subtrees with two and pick the best match.
  114. */
  115. static void match_trees(const struct object_id *hash1,
  116. const struct object_id *hash2,
  117. int *best_score,
  118. char **best_match,
  119. const char *base,
  120. int recurse_limit)
  121. {
  122. struct tree_desc one;
  123. void *one_buf = fill_tree_desc_strict(&one, hash1);
  124. while (one.size) {
  125. const char *path;
  126. const struct object_id *elem;
  127. unsigned short mode;
  128. int score;
  129. elem = tree_entry_extract(&one, &path, &mode);
  130. if (!S_ISDIR(mode))
  131. goto next;
  132. score = score_trees(elem, hash2);
  133. if (*best_score < score) {
  134. free(*best_match);
  135. *best_match = xstrfmt("%s%s", base, path);
  136. *best_score = score;
  137. }
  138. if (recurse_limit) {
  139. char *newbase = xstrfmt("%s%s/", base, path);
  140. match_trees(elem, hash2, best_score, best_match,
  141. newbase, recurse_limit - 1);
  142. free(newbase);
  143. }
  144. next:
  145. update_tree_entry(&one);
  146. }
  147. free(one_buf);
  148. }
  149. /*
  150. * A tree "oid1" has a subdirectory at "prefix". Come up with a tree object by
  151. * replacing it with another tree "oid2".
  152. */
  153. static int splice_tree(const struct object_id *oid1, const char *prefix,
  154. const struct object_id *oid2, struct object_id *result)
  155. {
  156. char *subpath;
  157. int toplen;
  158. char *buf;
  159. unsigned long sz;
  160. struct tree_desc desc;
  161. unsigned char *rewrite_here;
  162. const struct object_id *rewrite_with;
  163. struct object_id subtree;
  164. enum object_type type;
  165. int status;
  166. subpath = strchrnul(prefix, '/');
  167. toplen = subpath - prefix;
  168. if (*subpath)
  169. subpath++;
  170. buf = read_object_file(oid1, &type, &sz);
  171. if (!buf)
  172. die("cannot read tree %s", oid_to_hex(oid1));
  173. init_tree_desc(&desc, buf, sz);
  174. rewrite_here = NULL;
  175. while (desc.size) {
  176. const char *name;
  177. unsigned short mode;
  178. tree_entry_extract(&desc, &name, &mode);
  179. if (strlen(name) == toplen &&
  180. !memcmp(name, prefix, toplen)) {
  181. if (!S_ISDIR(mode))
  182. die("entry %s in tree %s is not a tree", name,
  183. oid_to_hex(oid1));
  184. /*
  185. * We cast here for two reasons:
  186. *
  187. * - to flip the "char *" (for the path) to "unsigned
  188. * char *" (for the hash stored after it)
  189. *
  190. * - to discard the "const"; this is OK because we
  191. * know it points into our non-const "buf"
  192. */
  193. rewrite_here = (unsigned char *)(desc.entry.path +
  194. strlen(desc.entry.path) +
  195. 1);
  196. break;
  197. }
  198. update_tree_entry(&desc);
  199. }
  200. if (!rewrite_here)
  201. die("entry %.*s not found in tree %s", toplen, prefix,
  202. oid_to_hex(oid1));
  203. if (*subpath) {
  204. struct object_id tree_oid;
  205. hashcpy(tree_oid.hash, rewrite_here);
  206. status = splice_tree(&tree_oid, subpath, oid2, &subtree);
  207. if (status)
  208. return status;
  209. rewrite_with = &subtree;
  210. } else {
  211. rewrite_with = oid2;
  212. }
  213. hashcpy(rewrite_here, rewrite_with->hash);
  214. status = write_object_file(buf, sz, tree_type, result);
  215. free(buf);
  216. return status;
  217. }
  218. /*
  219. * We are trying to come up with a merge between one and two that
  220. * results in a tree shape similar to one. The tree two might
  221. * correspond to a subtree of one, in which case it needs to be
  222. * shifted down by prefixing otherwise empty directories. On the
  223. * other hand, it could cover tree one and we might need to pick a
  224. * subtree of it.
  225. */
  226. void shift_tree(struct repository *r,
  227. const struct object_id *hash1,
  228. const struct object_id *hash2,
  229. struct object_id *shifted,
  230. int depth_limit)
  231. {
  232. char *add_prefix;
  233. char *del_prefix;
  234. int add_score, del_score;
  235. /*
  236. * NEEDSWORK: this limits the recursion depth to hardcoded
  237. * value '2' to avoid excessive overhead.
  238. */
  239. if (!depth_limit)
  240. depth_limit = 2;
  241. add_score = del_score = score_trees(hash1, hash2);
  242. add_prefix = xcalloc(1, 1);
  243. del_prefix = xcalloc(1, 1);
  244. /*
  245. * See if one's subtree resembles two; if so we need to prefix
  246. * two with a few fake trees to match the prefix.
  247. */
  248. match_trees(hash1, hash2, &add_score, &add_prefix, "", depth_limit);
  249. /*
  250. * See if two's subtree resembles one; if so we need to
  251. * pick only subtree of two.
  252. */
  253. match_trees(hash2, hash1, &del_score, &del_prefix, "", depth_limit);
  254. /* Assume we do not have to do any shifting */
  255. oidcpy(shifted, hash2);
  256. if (add_score < del_score) {
  257. /* We need to pick a subtree of two */
  258. unsigned short mode;
  259. if (!*del_prefix)
  260. return;
  261. if (get_tree_entry(r, hash2, del_prefix, shifted, &mode))
  262. die("cannot find path %s in tree %s",
  263. del_prefix, oid_to_hex(hash2));
  264. return;
  265. }
  266. if (!*add_prefix)
  267. return;
  268. splice_tree(hash1, add_prefix, hash2, shifted);
  269. }
  270. /*
  271. * The user says the trees will be shifted by this much.
  272. * Unfortunately we cannot fundamentally tell which one to
  273. * be prefixed, as recursive merge can work in either direction.
  274. */
  275. void shift_tree_by(struct repository *r,
  276. const struct object_id *hash1,
  277. const struct object_id *hash2,
  278. struct object_id *shifted,
  279. const char *shift_prefix)
  280. {
  281. struct object_id sub1, sub2;
  282. unsigned short mode1, mode2;
  283. unsigned candidate = 0;
  284. /* Can hash2 be a tree at shift_prefix in tree hash1? */
  285. if (!get_tree_entry(r, hash1, shift_prefix, &sub1, &mode1) &&
  286. S_ISDIR(mode1))
  287. candidate |= 1;
  288. /* Can hash1 be a tree at shift_prefix in tree hash2? */
  289. if (!get_tree_entry(r, hash2, shift_prefix, &sub2, &mode2) &&
  290. S_ISDIR(mode2))
  291. candidate |= 2;
  292. if (candidate == 3) {
  293. /* Both are plausible -- we need to evaluate the score */
  294. int best_score = score_trees(hash1, hash2);
  295. int score;
  296. candidate = 0;
  297. score = score_trees(&sub1, hash2);
  298. if (score > best_score) {
  299. candidate = 1;
  300. best_score = score;
  301. }
  302. score = score_trees(&sub2, hash1);
  303. if (score > best_score)
  304. candidate = 2;
  305. }
  306. if (!candidate) {
  307. /* Neither is plausible -- do not shift */
  308. oidcpy(shifted, hash2);
  309. return;
  310. }
  311. if (candidate == 1)
  312. /*
  313. * shift tree2 down by adding shift_prefix above it
  314. * to match tree1.
  315. */
  316. splice_tree(hash1, shift_prefix, hash2, shifted);
  317. else
  318. /*
  319. * shift tree2 up by removing shift_prefix from it
  320. * to match tree1.
  321. */
  322. oidcpy(shifted, &sub2);
  323. }