tree-walk.c

   1 #include "cache.h"
   2 #include "tree-walk.h"
   3 #include "unpack-trees.h"
   4 #include "tree.h"
   5
   6 static const char *get_mode(const char *str, unsigned int *modep)
   7 {
   8         unsigned char c;
   9         unsigned int mode = 0;
  10
  11         if (*str == ' ')
  12                 return NULL;
  13
  14         while ((c = *str++) != ' ') {
  15                 if (c < '0' || c > '7')
  16                         return NULL;
  17                 mode = (mode << 3) + (c - '0');
  18         }
  19         *modep = mode;
  20         return str;
  21 }
  22
  23 static void decode_tree_entry(struct tree_desc *desc, const char *buf, unsigned long size)
  24 {
  25         const char *path;
  26         unsigned int mode, len;
  27
  28         if (size < 24 || buf[size - 21])
  29                 die("corrupt tree file");
  30
  31         path = get_mode(buf, &mode);
  32         if (!path || !*path)
  33                 die("corrupt tree file");
  34         len = strlen(path) + 1;
  35
  36         /* Initialize the descriptor entry */
  37         desc->entry.path = path;
  38         desc->entry.mode = mode;
  39         desc->entry.sha1 = (const unsigned char *)(path + len);
  40 }
  41
  42 void init_tree_desc(struct tree_desc *desc, const void *buffer, unsigned long size)
  43 {
  44         desc->buffer = buffer;
  45         desc->size = size;
  46         if (size)
  47                 decode_tree_entry(desc, buffer, size);
  48 }
  49
  50 void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)
  51 {
  52         unsigned long size = 0;
  53         void *buf = NULL;
  54
  55         if (sha1) {
  56                 buf = read_object_with_reference(sha1, tree_type, &size, NULL);
  57                 if (!buf)
  58                         die("unable to read tree %s", sha1_to_hex(sha1));
  59         }
  60         init_tree_desc(desc, buf, size);
  61         return buf;
  62 }
  63
  64 static void entry_clear(struct name_entry *a)
  65 {
  66         memset(a, 0, sizeof(*a));
  67 }
  68
  69 static void entry_extract(struct tree_desc *t, struct name_entry *a)
  70 {
  71         *a = t->entry;
  72 }
  73
  74 void update_tree_entry(struct tree_desc *desc)
  75 {
  76         const void *buf = desc->buffer;
  77         const unsigned char *end = desc->entry.sha1 + 20;
  78         unsigned long size = desc->size;
  79         unsigned long len = end - (const unsigned char *)buf;
  80
  81         if (size < len)
  82                 die("corrupt tree file");
  83         buf = end;
  84         size -= len;
  85         desc->buffer = buf;
  86         desc->size = size;
  87         if (size)
  88                 decode_tree_entry(desc, buf, size);
  89 }
  90
  91 int tree_entry(struct tree_desc *desc, struct name_entry *entry)
  92 {
  93         if (!desc->size)
  94                 return 0;
  95
  96         *entry = desc->entry;
  97         update_tree_entry(desc);
  98         return 1;
  99 }
 100
 101 void setup_traverse_info(struct traverse_info *info, const char *base)
 102 {
 103         int pathlen = strlen(base);
 104         static struct traverse_info dummy;
 105
 106         memset(info, 0, sizeof(*info));
 107         if (pathlen && base[pathlen-1] == '/')
 108                 pathlen--;
 109         info->pathlen = pathlen ? pathlen + 1 : 0;
 110         info->name.path = base;
 111         info->name.sha1 = (void *)(base + pathlen + 1);
 112         if (pathlen)
 113                 info->prev = &dummy;
 114 }
 115
 116 char *make_traverse_path(char *path, const struct traverse_info *info, const struct name_entry *n)
 117 {
 118         int len = tree_entry_len(n->path, n->sha1);
 119         int pathlen = info->pathlen;
 120
 121         path[pathlen + len] = 0;
 122         for (;;) {
 123                 memcpy(path + pathlen, n->path, len);
 124                 if (!pathlen)
 125                         break;
 126                 path[--pathlen] = '/';
 127                 n = &info->name;
 128                 len = tree_entry_len(n->path, n->sha1);
 129                 info = info->prev;
 130                 pathlen -= len;
 131         }
 132         return path;
 133 }
 134
 135 struct tree_desc_skip {
 136         struct tree_desc_skip *prev;
 137         const void *ptr;
 138 };
 139
 140 struct tree_desc_x {
 141         struct tree_desc d;
 142         struct tree_desc_skip *skip;
 143 };
 144
 145 static int name_compare(const char *a, int a_len,
 146                         const char *b, int b_len)
 147 {
 148         int len = (a_len < b_len) ? a_len : b_len;
 149         int cmp = memcmp(a, b, len);
 150         if (cmp)
 151                 return cmp;
 152         return (a_len - b_len);
 153 }
 154
 155 static int check_entry_match(const char *a, int a_len, const char *b, int b_len)
 156 {
 157         /*
 158          * The caller wants to pick *a* from a tree or nothing.
 159          * We are looking at *b* in a tree.
 160          *
 161          * (0) If a and b are the same name, we are trivially happy.
 162          *
 163          * There are three possibilities where *a* could be hiding
 164          * behind *b*.
 165          *
 166          * (1) *a* == "t",   *b* == "ab"  i.e. *b* sorts earlier than *a* no
 167          *                                matter what.
 168          * (2) *a* == "t",   *b* == "t-2" and "t" is a subtree in the tree;
 169          * (3) *a* == "t-2", *b* == "t"   and "t-2" is a blob in the tree.
 170          *
 171          * Otherwise we know *a* won't appear in the tree without
 172          * scanning further.
 173          */
 174
 175         int cmp = name_compare(a, a_len, b, b_len);
 176
 177         /* Most common case first -- reading sync'd trees */
 178         if (!cmp)
 179                 return cmp;
 180
 181         if (0 < cmp) {
 182                 /* a comes after b; it does not matter if it is case (3)
 183                 if (b_len < a_len && !memcmp(a, b, b_len) && a[b_len] < '/')
 184                         return 1;
 185                 */
 186                 return 1; /* keep looking */
 187         }
 188
 189         /* b comes after a; are we looking at case (2)? */
 190         if (a_len < b_len && !memcmp(a, b, a_len) && b[a_len] < '/')
 191                 return 1; /* keep looking */
 192
 193         return -1; /* a cannot appear in the tree */
 194 }
 195
 196 /*
 197  * From the extended tree_desc, extract the first name entry, while
 198  * paying attention to the candidate "first" name.  Most importantly,
 199  * when looking for an entry, if there are entries that sorts earlier
 200  * in the tree object representation than that name, skip them and
 201  * process the named entry first.  We will remember that we haven't
 202  * processed the first entry yet, and in the later call skip the
 203  * entry we processed early when update_extended_entry() is called.
 204  *
 205  * E.g. if the underlying tree object has these entries:
 206  *
 207  *    blob    "t-1"
 208  *    blob    "t-2"
 209  *    tree    "t"
 210  *    blob    "t=1"
 211  *
 212  * and the "first" asks for "t", remember that we still need to
 213  * process "t-1" and "t-2" but extract "t".  After processing the
 214  * entry "t" from this call, the caller will let us know by calling
 215  * update_extended_entry() that we can remember "t" has been processed
 216  * already.
 217  */
 218
 219 static void extended_entry_extract(struct tree_desc_x *t,
 220                                    struct name_entry *a,
 221                                    const char *first,
 222                                    int first_len)
 223 {
 224         const char *path;
 225         int len;
 226         struct tree_desc probe;
 227         struct tree_desc_skip *skip;
 228
 229         /*
 230          * Extract the first entry from the tree_desc, but skip the
 231          * ones that we already returned in earlier rounds.
 232          */
 233         while (1) {
 234                 if (!t->d.size) {
 235                         entry_clear(a);
 236                         break; /* not found */
 237                 }
 238                 entry_extract(&t->d, a);
 239                 for (skip = t->skip; skip; skip = skip->prev)
 240                         if (a->path == skip->ptr)
 241                                 break; /* found */
 242                 if (!skip)
 243                         break;
 244                 /* We have processed this entry already. */
 245                 update_tree_entry(&t->d);
 246         }
 247
 248         if (!first || !a->path)
 249                 return;
 250
 251         /*
 252          * The caller wants "first" from this tree, or nothing.
 253          */
 254         path = a->path;
 255         len = tree_entry_len(a->path, a->sha1);
 256         switch (check_entry_match(first, first_len, path, len)) {
 257         case -1:
 258                 entry_clear(a);
 259         case 0:
 260                 return;
 261         default:
 262                 break;
 263         }
 264
 265         /*
 266          * We need to look-ahead -- we suspect that a subtree whose
 267          * name is "first" may be hiding behind the current entry "path".
 268          */
 269         probe = t->d;
 270         while (probe.size) {
 271                 entry_extract(&probe, a);
 272                 path = a->path;
 273                 len = tree_entry_len(a->path, a->sha1);
 274                 switch (check_entry_match(first, first_len, path, len)) {
 275                 case -1:
 276                         entry_clear(a);
 277                 case 0:
 278                         return;
 279                 default:
 280                         update_tree_entry(&probe);
 281                         break;
 282                 }
 283                 /* keep looking */
 284         }
 285         entry_clear(a);
 286 }
 287
 288 static void update_extended_entry(struct tree_desc_x *t, struct name_entry *a)
 289 {
 290         if (t->d.entry.path == a->path) {
 291                 update_tree_entry(&t->d);
 292         } else {
 293                 /* we have returned this entry early */
 294                 struct tree_desc_skip *skip = xmalloc(sizeof(*skip));
 295                 skip->ptr = a->path;
 296                 skip->prev = t->skip;
 297                 t->skip = skip;
 298         }
 299 }
 300
 301 static void free_extended_entry(struct tree_desc_x *t)
 302 {
 303         struct tree_desc_skip *p, *s;
 304
 305         for (s = t->skip; s; s = p) {
 306                 p = s->prev;
 307                 free(s);
 308         }
 309 }
 310
 311 int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
 312 {
 313         int ret = 0;
 314         int error = 0;
 315         struct name_entry *entry = xmalloc(n*sizeof(*entry));
 316         int i;
 317         struct tree_desc_x *tx = xcalloc(n, sizeof(*tx));
 318
 319         for (i = 0; i < n; i++)
 320                 tx[i].d = t[i];
 321
 322         for (;;) {
 323                 unsigned long mask, dirmask;
 324                 const char *first = NULL;
 325                 int first_len = 0;
 326                 struct name_entry *e;
 327                 int len;
 328
 329                 for (i = 0; i < n; i++) {
 330                         e = entry + i;
 331                         extended_entry_extract(tx + i, e, NULL, 0);
 332                 }
 333
 334                 /*
 335                  * A tree may have "t-2" at the current location even
 336                  * though it may have "t" that is a subtree behind it,
 337                  * and another tree may return "t".  We want to grab
 338                  * all "t" from all trees to match in such a case.
 339                  */
 340                 for (i = 0; i < n; i++) {
 341                         e = entry + i;
 342                         if (!e->path)
 343                                 continue;
 344                         len = tree_entry_len(e->path, e->sha1);
 345                         if (!first) {
 346                                 first = e->path;
 347                                 first_len = len;
 348                                 continue;
 349                         }
 350                         if (name_compare(e->path, len, first, first_len) < 0) {
 351                                 first = e->path;
 352                                 first_len = len;
 353                         }
 354                 }
 355
 356                 if (first) {
 357                         for (i = 0; i < n; i++) {
 358                                 e = entry + i;
 359                                 extended_entry_extract(tx + i, e, first, first_len);
 360                                 /* Cull the ones that are not the earliest */
 361                                 if (!e->path)
 362                                         continue;
 363                                 len = tree_entry_len(e->path, e->sha1);
 364                                 if (name_compare(e->path, len, first, first_len))
 365                                         entry_clear(e);
 366                         }
 367                 }
 368
 369                 /* Now we have in entry[i] the earliest name from the trees */
 370                 mask = 0;
 371                 dirmask = 0;
 372                 for (i = 0; i < n; i++) {
 373                         if (!entry[i].path)
 374                                 continue;
 375                         mask |= 1ul << i;
 376                         if (S_ISDIR(entry[i].mode))
 377                                 dirmask |= 1ul << i;
 378                 }
 379                 if (!mask)
 380                         break;
 381                 ret = info->fn(n, mask, dirmask, entry, info);
 382                 if (ret < 0) {
 383                         error = ret;
 384                         if (!info->show_all_errors)
 385                                 break;
 386                 }
 387                 mask &= ret;
 388                 ret = 0;
 389                 for (i = 0; i < n; i++)
 390                         if (mask & (1ul << i))
 391                                 update_extended_entry(tx + i, entry + i);
 392         }
 393         free(entry);
 394         for (i = 0; i < n; i++)
 395                 free_extended_entry(tx + i);
 396         free(tx);
 397         return error;
 398 }
 399
 400 static int find_tree_entry(struct tree_desc *t, const char *name, unsigned char *result, unsigned *mode)
 401 {
 402         int namelen = strlen(name);
 403         while (t->size) {
 404                 const char *entry;
 405                 const unsigned char *sha1;
 406                 int entrylen, cmp;
 407
 408                 sha1 = tree_entry_extract(t, &entry, mode);
 409                 update_tree_entry(t);
 410                 entrylen = tree_entry_len(entry, sha1);
 411                 if (entrylen > namelen)
 412                         continue;
 413                 cmp = memcmp(name, entry, entrylen);
 414                 if (cmp > 0)
 415                         continue;
 416                 if (cmp < 0)
 417                         break;
 418                 if (entrylen == namelen) {
 419                         hashcpy(result, sha1);
 420                         return 0;
 421                 }
 422                 if (name[entrylen] != '/')
 423                         continue;
 424                 if (!S_ISDIR(*mode))
 425                         break;
 426                 if (++entrylen == namelen) {
 427                         hashcpy(result, sha1);
 428                         return 0;
 429                 }
 430                 return get_tree_entry(sha1, name + entrylen, result, mode);
 431         }
 432         return -1;
 433 }
 434
 435 int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned char *sha1, unsigned *mode)
 436 {
 437         int retval;
 438         void *tree;
 439         unsigned long size;
 440         struct tree_desc t;
 441         unsigned char root[20];
 442
 443         tree = read_object_with_reference(tree_sha1, tree_type, &size, root);
 444         if (!tree)
 445                 return -1;
 446
 447         if (name[0] == '\0') {
 448                 hashcpy(sha1, root);
 449                 free(tree);
 450                 return 0;
 451         }
 452
 453         init_tree_desc(&t, tree, size);
 454         retval = find_tree_entry(&t, name, sha1, mode);
 455         free(tree);
 456         return retval;
 457 }
 458
 459 /*
 460  * Is a tree entry interesting given the pathspec we have?
 461  *
 462  * Pre-condition: baselen == 0 || base[baselen-1] == '/'
 463  *
 464  * Return:
 465  *  - 2 for "yes, and all subsequent entries will be"
 466  *  - 1 for yes
 467  *  - zero for no
 468  *  - negative for "no, and no subsequent entries will be either"
 469  */
 470 int tree_entry_interesting(const struct name_entry *entry,
 471                            const struct strbuf *base_buf,
 472                            const struct pathspec *ps)
 473 {
 474         int i;
 475         int pathlen, baselen = base_buf->len;
 476         int never_interesting = -1;
 477         const char *base = base_buf->buf;
 478
 479         if (!ps || !ps->nr)
 480                 return 2;
 481
 482         pathlen = tree_entry_len(entry->path, entry->sha1);
 483
 484         for (i = 0; i < ps->nr; i++) {
 485                 const struct pathspec_item *item = ps->items+i;
 486                 const char *match = item->match;
 487                 int matchlen = item->len;
 488                 int m = -1; /* signals that we haven't called strncmp() */
 489
 490                 if (baselen >= matchlen) {
 491                         /* If it doesn't match, move along... */
 492                         if (strncmp(base, match, matchlen))
 493                                 continue;
 494
 495                         /*
 496                          * If the base is a subdirectory of a path which
 497                          * was specified, all of them are interesting.
 498                          */
 499                         if (!matchlen ||
 500                             base[matchlen] == '/' ||
 501                             match[matchlen - 1] == '/')
 502                                 return 2;
 503
 504                         /* Just a random prefix match */
 505                         continue;
 506                 }
 507
 508                 /* Does the base match? */
 509                 if (strncmp(base, match, baselen))
 510                         continue;
 511
 512                 match += baselen;
 513                 matchlen -= baselen;
 514
 515                 if (never_interesting) {
 516                         /*
 517                          * We have not seen any match that sorts later
 518                          * than the current path.
 519                          */
 520
 521                         /*
 522                          * Does match sort strictly earlier than path
 523                          * with their common parts?
 524                          */
 525                         m = strncmp(match, entry->path,
 526                                     (matchlen < pathlen) ? matchlen : pathlen);
 527                         if (m < 0)
 528                                 continue;
 529
 530                         /*
 531                          * If we come here even once, that means there is at
 532                          * least one pathspec that would sort equal to or
 533                          * later than the path we are currently looking at.
 534                          * In other words, if we have never reached this point
 535                          * after iterating all pathspecs, it means all
 536                          * pathspecs are either outside of base, or inside the
 537                          * base but sorts strictly earlier than the current
 538                          * one.  In either case, they will never match the
 539                          * subsequent entries.  In such a case, we initialized
 540                          * the variable to -1 and that is what will be
 541                          * returned, allowing the caller to terminate early.
 542                          */
 543                         never_interesting = 0;
 544                 }
 545
 546                 if (pathlen > matchlen)
 547                         continue;
 548
 549                 if (matchlen > pathlen) {
 550                         if (match[pathlen] != '/')
 551                                 continue;
 552                         if (!S_ISDIR(entry->mode))
 553                                 continue;
 554                 }
 555
 556                 if (m == -1)
 557                         /*
 558                          * we cheated and did not do strncmp(), so we do
 559                          * that here.
 560                          */
 561                         m = strncmp(match, entry->path, pathlen);
 562
 563                 /*
 564                  * If common part matched earlier then it is a hit,
 565                  * because we rejected the case where path is not a
 566                  * leading directory and is shorter than match.
 567                  */
 568                 if (!m)
 569                         return 1;
 570         }
 571         return never_interesting; /* No matches */
 572 }