match-trees.c

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