match-trees.c

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