match-trees.c

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