tree-walk.c

   1 #include "cache.h"
   2 #include "tree-walk.h"
   3 #include "unpack-trees.h"
   4 #include "dir.h"
   5 #include "object-store.h"
   6 #include "tree.h"
   7 #include "pathspec.h"
   8
   9 static const char *get_mode(const char *str, unsigned int *modep)
  10 {
  11         unsigned char c;
  12         unsigned int mode = 0;
  13
  14         if (*str == ' ')
  15                 return NULL;
  16
  17         while ((c = *str++) != ' ') {
  18                 if (c < '0' || c > '7')
  19                         return NULL;
  20                 mode = (mode << 3) + (c - '0');
  21         }
  22         *modep = mode;
  23         return str;
  24 }
  25
  26 static int decode_tree_entry(struct tree_desc *desc, const char *buf, unsigned long size, struct strbuf *err)
  27 {
  28         const char *path;
  29         unsigned int mode, len;
  30         const unsigned hashsz = the_hash_algo->rawsz;
  31
  32         if (size < hashsz + 3 || buf[size - (hashsz + 1)]) {
  33                 strbuf_addstr(err, _("too-short tree object"));
  34                 return -1;
  35         }
  36
  37         path = get_mode(buf, &mode);
  38         if (!path) {
  39                 strbuf_addstr(err, _("malformed mode in tree entry"));
  40                 return -1;
  41         }
  42         if (!*path) {
  43                 strbuf_addstr(err, _("empty filename in tree entry"));
  44                 return -1;
  45         }
  46 #ifdef GIT_WINDOWS_NATIVE
  47         if (protect_ntfs && strchr(path, '\\')) {
  48                 strbuf_addf(err, _("filename in tree entry contains backslash: '%s'"), path);
  49                 return -1;
  50         }
  51 #endif
  52         len = strlen(path) + 1;
  53
  54         /* Initialize the descriptor entry */
  55         desc->entry.path = path;
  56         desc->entry.mode = canon_mode(mode);
  57         desc->entry.pathlen = len - 1;
  58         hashcpy(desc->entry.oid.hash, (const unsigned char *)path + len);
  59
  60         return 0;
  61 }
  62
  63 static int init_tree_desc_internal(struct tree_desc *desc, const void *buffer, unsigned long size, struct strbuf *err)
  64 {
  65         desc->buffer = buffer;
  66         desc->size = size;
  67         if (size)
  68                 return decode_tree_entry(desc, buffer, size, err);
  69         return 0;
  70 }
  71
  72 void init_tree_desc(struct tree_desc *desc, const void *buffer, unsigned long size)
  73 {
  74         struct strbuf err = STRBUF_INIT;
  75         if (init_tree_desc_internal(desc, buffer, size, &err))
  76                 die("%s", err.buf);
  77         strbuf_release(&err);
  78 }
  79
  80 int init_tree_desc_gently(struct tree_desc *desc, const void *buffer, unsigned long size)
  81 {
  82         struct strbuf err = STRBUF_INIT;
  83         int result = init_tree_desc_internal(desc, buffer, size, &err);
  84         if (result)
  85                 error("%s", err.buf);
  86         strbuf_release(&err);
  87         return result;
  88 }
  89
  90 void *fill_tree_descriptor(struct tree_desc *desc, const struct object_id *oid)
  91 {
  92         unsigned long size = 0;
  93         void *buf = NULL;
  94
  95         if (oid) {
  96                 buf = read_object_with_reference(oid, tree_type, &size, NULL);
  97                 if (!buf)
  98                         die("unable to read tree %s", oid_to_hex(oid));
  99         }
 100         init_tree_desc(desc, buf, size);
 101         return buf;
 102 }
 103
 104 static void entry_clear(struct name_entry *a)
 105 {
 106         memset(a, 0, sizeof(*a));
 107 }
 108
 109 static void entry_extract(struct tree_desc *t, struct name_entry *a)
 110 {
 111         *a = t->entry;
 112 }
 113
 114 static int update_tree_entry_internal(struct tree_desc *desc, struct strbuf *err)
 115 {
 116         const void *buf = desc->buffer;
 117         const unsigned char *end = (const unsigned char *)desc->entry.path + desc->entry.pathlen + 1 + the_hash_algo->rawsz;
 118         unsigned long size = desc->size;
 119         unsigned long len = end - (const unsigned char *)buf;
 120
 121         if (size < len)
 122                 die(_("too-short tree file"));
 123         buf = end;
 124         size -= len;
 125         desc->buffer = buf;
 126         desc->size = size;
 127         if (size)
 128                 return decode_tree_entry(desc, buf, size, err);
 129         return 0;
 130 }
 131
 132 void update_tree_entry(struct tree_desc *desc)
 133 {
 134         struct strbuf err = STRBUF_INIT;
 135         if (update_tree_entry_internal(desc, &err))
 136                 die("%s", err.buf);
 137         strbuf_release(&err);
 138 }
 139
 140 int update_tree_entry_gently(struct tree_desc *desc)
 141 {
 142         struct strbuf err = STRBUF_INIT;
 143         if (update_tree_entry_internal(desc, &err)) {
 144                 error("%s", err.buf);
 145                 strbuf_release(&err);
 146                 /* Stop processing this tree after error */
 147                 desc->size = 0;
 148                 return -1;
 149         }
 150         strbuf_release(&err);
 151         return 0;
 152 }
 153
 154 int tree_entry(struct tree_desc *desc, struct name_entry *entry)
 155 {
 156         if (!desc->size)
 157                 return 0;
 158
 159         *entry = desc->entry;
 160         update_tree_entry(desc);
 161         return 1;
 162 }
 163
 164 int tree_entry_gently(struct tree_desc *desc, struct name_entry *entry)
 165 {
 166         if (!desc->size)
 167                 return 0;
 168
 169         *entry = desc->entry;
 170         if (update_tree_entry_gently(desc))
 171                 return 0;
 172         return 1;
 173 }
 174
 175 void setup_traverse_info(struct traverse_info *info, const char *base)
 176 {
 177         int pathlen = strlen(base);
 178         static struct traverse_info dummy;
 179
 180         memset(info, 0, sizeof(*info));
 181         if (pathlen && base[pathlen-1] == '/')
 182                 pathlen--;
 183         info->pathlen = pathlen ? pathlen + 1 : 0;
 184         info->name.path = base;
 185         info->name.pathlen = pathlen;
 186         if (pathlen) {
 187                 hashcpy(info->name.oid.hash, (const unsigned char *)base + pathlen + 1);
 188                 info->prev = &dummy;
 189         }
 190 }
 191
 192 char *make_traverse_path(char *path, const struct traverse_info *info, const struct name_entry *n)
 193 {
 194         int len = tree_entry_len(n);
 195         int pathlen = info->pathlen;
 196
 197         path[pathlen + len] = 0;
 198         for (;;) {
 199                 memcpy(path + pathlen, n->path, len);
 200                 if (!pathlen)
 201                         break;
 202                 path[--pathlen] = '/';
 203                 n = &info->name;
 204                 len = tree_entry_len(n);
 205                 info = info->prev;
 206                 pathlen -= len;
 207         }
 208         return path;
 209 }
 210
 211 struct tree_desc_skip {
 212         struct tree_desc_skip *prev;
 213         const void *ptr;
 214 };
 215
 216 struct tree_desc_x {
 217         struct tree_desc d;
 218         struct tree_desc_skip *skip;
 219 };
 220
 221 static int check_entry_match(const char *a, int a_len, const char *b, int b_len)
 222 {
 223         /*
 224          * The caller wants to pick *a* from a tree or nothing.
 225          * We are looking at *b* in a tree.
 226          *
 227          * (0) If a and b are the same name, we are trivially happy.
 228          *
 229          * There are three possibilities where *a* could be hiding
 230          * behind *b*.
 231          *
 232          * (1) *a* == "t",   *b* == "ab"  i.e. *b* sorts earlier than *a* no
 233          *                                matter what.
 234          * (2) *a* == "t",   *b* == "t-2" and "t" is a subtree in the tree;
 235          * (3) *a* == "t-2", *b* == "t"   and "t-2" is a blob in the tree.
 236          *
 237          * Otherwise we know *a* won't appear in the tree without
 238          * scanning further.
 239          */
 240
 241         int cmp = name_compare(a, a_len, b, b_len);
 242
 243         /* Most common case first -- reading sync'd trees */
 244         if (!cmp)
 245                 return cmp;
 246
 247         if (0 < cmp) {
 248                 /* a comes after b; it does not matter if it is case (3)
 249                 if (b_len < a_len && !memcmp(a, b, b_len) && a[b_len] < '/')
 250                         return 1;
 251                 */
 252                 return 1; /* keep looking */
 253         }
 254
 255         /* b comes after a; are we looking at case (2)? */
 256         if (a_len < b_len && !memcmp(a, b, a_len) && b[a_len] < '/')
 257                 return 1; /* keep looking */
 258
 259         return -1; /* a cannot appear in the tree */
 260 }
 261
 262 /*
 263  * From the extended tree_desc, extract the first name entry, while
 264  * paying attention to the candidate "first" name.  Most importantly,
 265  * when looking for an entry, if there are entries that sorts earlier
 266  * in the tree object representation than that name, skip them and
 267  * process the named entry first.  We will remember that we haven't
 268  * processed the first entry yet, and in the later call skip the
 269  * entry we processed early when update_extended_entry() is called.
 270  *
 271  * E.g. if the underlying tree object has these entries:
 272  *
 273  *    blob    "t-1"
 274  *    blob    "t-2"
 275  *    tree    "t"
 276  *    blob    "t=1"
 277  *
 278  * and the "first" asks for "t", remember that we still need to
 279  * process "t-1" and "t-2" but extract "t".  After processing the
 280  * entry "t" from this call, the caller will let us know by calling
 281  * update_extended_entry() that we can remember "t" has been processed
 282  * already.
 283  */
 284
 285 static void extended_entry_extract(struct tree_desc_x *t,
 286                                    struct name_entry *a,
 287                                    const char *first,
 288                                    int first_len)
 289 {
 290         const char *path;
 291         int len;
 292         struct tree_desc probe;
 293         struct tree_desc_skip *skip;
 294
 295         /*
 296          * Extract the first entry from the tree_desc, but skip the
 297          * ones that we already returned in earlier rounds.
 298          */
 299         while (1) {
 300                 if (!t->d.size) {
 301                         entry_clear(a);
 302                         break; /* not found */
 303                 }
 304                 entry_extract(&t->d, a);
 305                 for (skip = t->skip; skip; skip = skip->prev)
 306                         if (a->path == skip->ptr)
 307                                 break; /* found */
 308                 if (!skip)
 309                         break;
 310                 /* We have processed this entry already. */
 311                 update_tree_entry(&t->d);
 312         }
 313
 314         if (!first || !a->path)
 315                 return;
 316
 317         /*
 318          * The caller wants "first" from this tree, or nothing.
 319          */
 320         path = a->path;
 321         len = tree_entry_len(a);
 322         switch (check_entry_match(first, first_len, path, len)) {
 323         case -1:
 324                 entry_clear(a);
 325         case 0:
 326                 return;
 327         default:
 328                 break;
 329         }
 330
 331         /*
 332          * We need to look-ahead -- we suspect that a subtree whose
 333          * name is "first" may be hiding behind the current entry "path".
 334          */
 335         probe = t->d;
 336         while (probe.size) {
 337                 entry_extract(&probe, a);
 338                 path = a->path;
 339                 len = tree_entry_len(a);
 340                 switch (check_entry_match(first, first_len, path, len)) {
 341                 case -1:
 342                         entry_clear(a);
 343                 case 0:
 344                         return;
 345                 default:
 346                         update_tree_entry(&probe);
 347                         break;
 348                 }
 349                 /* keep looking */
 350         }
 351         entry_clear(a);
 352 }
 353
 354 static void update_extended_entry(struct tree_desc_x *t, struct name_entry *a)
 355 {
 356         if (t->d.entry.path == a->path) {
 357                 update_tree_entry(&t->d);
 358         } else {
 359                 /* we have returned this entry early */
 360                 struct tree_desc_skip *skip = xmalloc(sizeof(*skip));
 361                 skip->ptr = a->path;
 362                 skip->prev = t->skip;
 363                 t->skip = skip;
 364         }
 365 }
 366
 367 static void free_extended_entry(struct tree_desc_x *t)
 368 {
 369         struct tree_desc_skip *p, *s;
 370
 371         for (s = t->skip; s; s = p) {
 372                 p = s->prev;
 373                 free(s);
 374         }
 375 }
 376
 377 static inline int prune_traversal(struct index_state *istate,
 378                                   struct name_entry *e,
 379                                   struct traverse_info *info,
 380                                   struct strbuf *base,
 381                                   int still_interesting)
 382 {
 383         if (!info->pathspec || still_interesting == 2)
 384                 return 2;
 385         if (still_interesting < 0)
 386                 return still_interesting;
 387         return tree_entry_interesting(istate, e, base,
 388                                       0, info->pathspec);
 389 }
 390
 391 int traverse_trees(struct index_state *istate,
 392                    int n, struct tree_desc *t,
 393                    struct traverse_info *info)
 394 {
 395         int error = 0;
 396         struct name_entry *entry = xmalloc(n*sizeof(*entry));
 397         int i;
 398         struct tree_desc_x *tx = xcalloc(n, sizeof(*tx));
 399         struct strbuf base = STRBUF_INIT;
 400         int interesting = 1;
 401         char *traverse_path;
 402
 403         for (i = 0; i < n; i++)
 404                 tx[i].d = t[i];
 405
 406         if (info->prev) {
 407                 strbuf_grow(&base, info->pathlen);
 408                 make_traverse_path(base.buf, info->prev, &info->name);
 409                 base.buf[info->pathlen-1] = '/';
 410                 strbuf_setlen(&base, info->pathlen);
 411                 traverse_path = xstrndup(base.buf, info->pathlen);
 412         } else {
 413                 traverse_path = xstrndup(info->name.path, info->pathlen);
 414         }
 415         info->traverse_path = traverse_path;
 416         for (;;) {
 417                 int trees_used;
 418                 unsigned long mask, dirmask;
 419                 const char *first = NULL;
 420                 int first_len = 0;
 421                 struct name_entry *e = NULL;
 422                 int len;
 423
 424                 for (i = 0; i < n; i++) {
 425                         e = entry + i;
 426                         extended_entry_extract(tx + i, e, NULL, 0);
 427                 }
 428
 429                 /*
 430                  * A tree may have "t-2" at the current location even
 431                  * though it may have "t" that is a subtree behind it,
 432                  * and another tree may return "t".  We want to grab
 433                  * all "t" from all trees to match in such a case.
 434                  */
 435                 for (i = 0; i < n; i++) {
 436                         e = entry + i;
 437                         if (!e->path)
 438                                 continue;
 439                         len = tree_entry_len(e);
 440                         if (!first) {
 441                                 first = e->path;
 442                                 first_len = len;
 443                                 continue;
 444                         }
 445                         if (name_compare(e->path, len, first, first_len) < 0) {
 446                                 first = e->path;
 447                                 first_len = len;
 448                         }
 449                 }
 450
 451                 if (first) {
 452                         for (i = 0; i < n; i++) {
 453                                 e = entry + i;
 454                                 extended_entry_extract(tx + i, e, first, first_len);
 455                                 /* Cull the ones that are not the earliest */
 456                                 if (!e->path)
 457                                         continue;
 458                                 len = tree_entry_len(e);
 459                                 if (name_compare(e->path, len, first, first_len))
 460                                         entry_clear(e);
 461                         }
 462                 }
 463
 464                 /* Now we have in entry[i] the earliest name from the trees */
 465                 mask = 0;
 466                 dirmask = 0;
 467                 for (i = 0; i < n; i++) {
 468                         if (!entry[i].path)
 469                                 continue;
 470                         mask |= 1ul << i;
 471                         if (S_ISDIR(entry[i].mode))
 472                                 dirmask |= 1ul << i;
 473                         e = &entry[i];
 474                 }
 475                 if (!mask)
 476                         break;
 477                 interesting = prune_traversal(istate, e, info, &base, interesting);
 478                 if (interesting < 0)
 479                         break;
 480                 if (interesting) {
 481                         trees_used = info->fn(n, mask, dirmask, entry, info);
 482                         if (trees_used < 0) {
 483                                 error = trees_used;
 484                                 if (!info->show_all_errors)
 485                                         break;
 486                         }
 487                         mask &= trees_used;
 488                 }
 489                 for (i = 0; i < n; i++)
 490                         if (mask & (1ul << i))
 491                                 update_extended_entry(tx + i, entry + i);
 492         }
 493         free(entry);
 494         for (i = 0; i < n; i++)
 495                 free_extended_entry(tx + i);
 496         free(tx);
 497         free(traverse_path);
 498         info->traverse_path = NULL;
 499         strbuf_release(&base);
 500         return error;
 501 }
 502
 503 struct dir_state {
 504         void *tree;
 505         unsigned long size;
 506         struct object_id oid;
 507 };
 508
 509 static int find_tree_entry(struct tree_desc *t, const char *name, struct object_id *result, unsigned *mode)
 510 {
 511         int namelen = strlen(name);
 512         while (t->size) {
 513                 const char *entry;
 514                 struct object_id oid;
 515                 int entrylen, cmp;
 516
 517                 oidcpy(&oid, tree_entry_extract(t, &entry, mode));
 518                 entrylen = tree_entry_len(&t->entry);
 519                 update_tree_entry(t);
 520                 if (entrylen > namelen)
 521                         continue;
 522                 cmp = memcmp(name, entry, entrylen);
 523                 if (cmp > 0)
 524                         continue;
 525                 if (cmp < 0)
 526                         break;
 527                 if (entrylen == namelen) {
 528                         oidcpy(result, &oid);
 529                         return 0;
 530                 }
 531                 if (name[entrylen] != '/')
 532                         continue;
 533                 if (!S_ISDIR(*mode))
 534                         break;
 535                 if (++entrylen == namelen) {
 536                         oidcpy(result, &oid);
 537                         return 0;
 538                 }
 539                 return get_tree_entry(&oid, name + entrylen, result, mode);
 540         }
 541         return -1;
 542 }
 543
 544 int get_tree_entry(const struct object_id *tree_oid, const char *name, struct object_id *oid, unsigned *mode)
 545 {
 546         int retval;
 547         void *tree;
 548         unsigned long size;
 549         struct object_id root;
 550
 551         tree = read_object_with_reference(tree_oid, tree_type, &size, &root);
 552         if (!tree)
 553                 return -1;
 554
 555         if (name[0] == '\0') {
 556                 oidcpy(oid, &root);
 557                 free(tree);
 558                 return 0;
 559         }
 560
 561         if (!size) {
 562                 retval = -1;
 563         } else {
 564                 struct tree_desc t;
 565                 init_tree_desc(&t, tree, size);
 566                 retval = find_tree_entry(&t, name, oid, mode);
 567         }
 568         free(tree);
 569         return retval;
 570 }
 571
 572 /*
 573  * This is Linux's built-in max for the number of symlinks to follow.
 574  * That limit, of course, does not affect git, but it's a reasonable
 575  * choice.
 576  */
 577 #define GET_TREE_ENTRY_FOLLOW_SYMLINKS_MAX_LINKS 40
 578
 579 /**
 580  * Find a tree entry by following symlinks in tree_sha (which is
 581  * assumed to be the root of the repository).  In the event that a
 582  * symlink points outside the repository (e.g. a link to /foo or a
 583  * root-level link to ../foo), the portion of the link which is
 584  * outside the repository will be returned in result_path, and *mode
 585  * will be set to 0.  It is assumed that result_path is uninitialized.
 586  * If there are no symlinks, or the end result of the symlink chain
 587  * points to an object inside the repository, result will be filled in
 588  * with the sha1 of the found object, and *mode will hold the mode of
 589  * the object.
 590  *
 591  * See the code for enum get_oid_result for a description of
 592  * the return values.
 593  */
 594 enum get_oid_result get_tree_entry_follow_symlinks(struct object_id *tree_oid, const char *name, struct object_id *result, struct strbuf *result_path, unsigned *mode)
 595 {
 596         int retval = MISSING_OBJECT;
 597         struct dir_state *parents = NULL;
 598         size_t parents_alloc = 0;
 599         size_t i, parents_nr = 0;
 600         struct object_id current_tree_oid;
 601         struct strbuf namebuf = STRBUF_INIT;
 602         struct tree_desc t;
 603         int follows_remaining = GET_TREE_ENTRY_FOLLOW_SYMLINKS_MAX_LINKS;
 604
 605         init_tree_desc(&t, NULL, 0UL);
 606         strbuf_addstr(&namebuf, name);
 607         oidcpy(&current_tree_oid, tree_oid);
 608
 609         while (1) {
 610                 int find_result;
 611                 char *first_slash;
 612                 char *remainder = NULL;
 613
 614                 if (!t.buffer) {
 615                         void *tree;
 616                         struct object_id root;
 617                         unsigned long size;
 618                         tree = read_object_with_reference(&current_tree_oid,
 619                                                           tree_type, &size,
 620                                                           &root);
 621                         if (!tree)
 622                                 goto done;
 623
 624                         ALLOC_GROW(parents, parents_nr + 1, parents_alloc);
 625                         parents[parents_nr].tree = tree;
 626                         parents[parents_nr].size = size;
 627                         oidcpy(&parents[parents_nr].oid, &root);
 628                         parents_nr++;
 629
 630                         if (namebuf.buf[0] == '\0') {
 631                                 oidcpy(result, &root);
 632                                 retval = FOUND;
 633                                 goto done;
 634                         }
 635
 636                         if (!size)
 637                                 goto done;
 638
 639                         /* descend */
 640                         init_tree_desc(&t, tree, size);
 641                 }
 642
 643                 /* Handle symlinks to e.g. a//b by removing leading slashes */
 644                 while (namebuf.buf[0] == '/') {
 645                         strbuf_remove(&namebuf, 0, 1);
 646                 }
 647
 648                 /* Split namebuf into a first component and a remainder */
 649                 if ((first_slash = strchr(namebuf.buf, '/'))) {
 650                         *first_slash = 0;
 651                         remainder = first_slash + 1;
 652                 }
 653
 654                 if (!strcmp(namebuf.buf, "..")) {
 655                         struct dir_state *parent;
 656                         /*
 657                          * We could end up with .. in the namebuf if it
 658                          * appears in a symlink.
 659                          */
 660
 661                         if (parents_nr == 1) {
 662                                 if (remainder)
 663                                         *first_slash = '/';
 664                                 strbuf_add(result_path, namebuf.buf,
 665                                            namebuf.len);
 666                                 *mode = 0;
 667                                 retval = FOUND;
 668                                 goto done;
 669                         }
 670                         parent = &parents[parents_nr - 1];
 671                         free(parent->tree);
 672                         parents_nr--;
 673                         parent = &parents[parents_nr - 1];
 674                         init_tree_desc(&t, parent->tree, parent->size);
 675                         strbuf_remove(&namebuf, 0, remainder ? 3 : 2);
 676                         continue;
 677                 }
 678
 679                 /* We could end up here via a symlink to dir/.. */
 680                 if (namebuf.buf[0] == '\0') {
 681                         oidcpy(result, &parents[parents_nr - 1].oid);
 682                         retval = FOUND;
 683                         goto done;
 684                 }
 685
 686                 /* Look up the first (or only) path component in the tree. */
 687                 find_result = find_tree_entry(&t, namebuf.buf,
 688                                               &current_tree_oid, mode);
 689                 if (find_result) {
 690                         goto done;
 691                 }
 692
 693                 if (S_ISDIR(*mode)) {
 694                         if (!remainder) {
 695                                 oidcpy(result, &current_tree_oid);
 696                                 retval = FOUND;
 697                                 goto done;
 698                         }
 699                         /* Descend the tree */
 700                         t.buffer = NULL;
 701                         strbuf_remove(&namebuf, 0,
 702                                       1 + first_slash - namebuf.buf);
 703                 } else if (S_ISREG(*mode)) {
 704                         if (!remainder) {
 705                                 oidcpy(result, &current_tree_oid);
 706                                 retval = FOUND;
 707                         } else {
 708                                 retval = NOT_DIR;
 709                         }
 710                         goto done;
 711                 } else if (S_ISLNK(*mode)) {
 712                         /* Follow a symlink */
 713                         unsigned long link_len;
 714                         size_t len;
 715                         char *contents, *contents_start;
 716                         struct dir_state *parent;
 717                         enum object_type type;
 718
 719                         if (follows_remaining-- == 0) {
 720                                 /* Too many symlinks followed */
 721                                 retval = SYMLINK_LOOP;
 722                                 goto done;
 723                         }
 724
 725                         /*
 726                          * At this point, we have followed at a least
 727                          * one symlink, so on error we need to report this.
 728                          */
 729                         retval = DANGLING_SYMLINK;
 730
 731                         contents = read_object_file(&current_tree_oid, &type,
 732                                                     &link_len);
 733
 734                         if (!contents)
 735                                 goto done;
 736
 737                         if (contents[0] == '/') {
 738                                 strbuf_addstr(result_path, contents);
 739                                 free(contents);
 740                                 *mode = 0;
 741                                 retval = FOUND;
 742                                 goto done;
 743                         }
 744
 745                         if (remainder)
 746                                 len = first_slash - namebuf.buf;
 747                         else
 748                                 len = namebuf.len;
 749
 750                         contents_start = contents;
 751
 752                         parent = &parents[parents_nr - 1];
 753                         init_tree_desc(&t, parent->tree, parent->size);
 754                         strbuf_splice(&namebuf, 0, len,
 755                                       contents_start, link_len);
 756                         if (remainder)
 757                                 namebuf.buf[link_len] = '/';
 758                         free(contents);
 759                 }
 760         }
 761 done:
 762         for (i = 0; i < parents_nr; i++)
 763                 free(parents[i].tree);
 764         free(parents);
 765
 766         strbuf_release(&namebuf);
 767         return retval;
 768 }
 769
 770 static int match_entry(const struct pathspec_item *item,
 771                        const struct name_entry *entry, int pathlen,
 772                        const char *match, int matchlen,
 773                        enum interesting *never_interesting)
 774 {
 775         int m = -1; /* signals that we haven't called strncmp() */
 776
 777         if (item->magic & PATHSPEC_ICASE)
 778                 /*
 779                  * "Never interesting" trick requires exact
 780                  * matching. We could do something clever with inexact
 781                  * matching, but it's trickier (and not to forget that
 782                  * strcasecmp is locale-dependent, at least in
 783                  * glibc). Just disable it for now. It can't be worse
 784                  * than the wildcard's codepath of '[Tt][Hi][Is][Ss]'
 785                  * pattern.
 786                  */
 787                 *never_interesting = entry_not_interesting;
 788         else if (*never_interesting != entry_not_interesting) {
 789                 /*
 790                  * We have not seen any match that sorts later
 791                  * than the current path.
 792                  */
 793
 794                 /*
 795                  * Does match sort strictly earlier than path
 796                  * with their common parts?
 797                  */
 798                 m = strncmp(match, entry->path,
 799                             (matchlen < pathlen) ? matchlen : pathlen);
 800                 if (m < 0)
 801                         return 0;
 802
 803                 /*
 804                  * If we come here even once, that means there is at
 805                  * least one pathspec that would sort equal to or
 806                  * later than the path we are currently looking at.
 807                  * In other words, if we have never reached this point
 808                  * after iterating all pathspecs, it means all
 809                  * pathspecs are either outside of base, or inside the
 810                  * base but sorts strictly earlier than the current
 811                  * one.  In either case, they will never match the
 812                  * subsequent entries.  In such a case, we initialized
 813                  * the variable to -1 and that is what will be
 814                  * returned, allowing the caller to terminate early.
 815                  */
 816                 *never_interesting = entry_not_interesting;
 817         }
 818
 819         if (pathlen > matchlen)
 820                 return 0;
 821
 822         if (matchlen > pathlen) {
 823                 if (match[pathlen] != '/')
 824                         return 0;
 825                 if (!S_ISDIR(entry->mode) && !S_ISGITLINK(entry->mode))
 826                         return 0;
 827         }
 828
 829         if (m == -1)
 830                 /*
 831                  * we cheated and did not do strncmp(), so we do
 832                  * that here.
 833                  */
 834                 m = ps_strncmp(item, match, entry->path, pathlen);
 835
 836         /*
 837          * If common part matched earlier then it is a hit,
 838          * because we rejected the case where path is not a
 839          * leading directory and is shorter than match.
 840          */
 841         if (!m)
 842                 /*
 843                  * match_entry does not check if the prefix part is
 844                  * matched case-sensitively. If the entry is a
 845                  * directory and part of prefix, it'll be rematched
 846                  * eventually by basecmp with special treatment for
 847                  * the prefix.
 848                  */
 849                 return 1;
 850
 851         return 0;
 852 }
 853
 854 /* :(icase)-aware string compare */
 855 static int basecmp(const struct pathspec_item *item,
 856                    const char *base, const char *match, int len)
 857 {
 858         if (item->magic & PATHSPEC_ICASE) {
 859                 int ret, n = len > item->prefix ? item->prefix : len;
 860                 ret = strncmp(base, match, n);
 861                 if (ret)
 862                         return ret;
 863                 base += n;
 864                 match += n;
 865                 len -= n;
 866         }
 867         return ps_strncmp(item, base, match, len);
 868 }
 869
 870 static int match_dir_prefix(const struct pathspec_item *item,
 871                             const char *base,
 872                             const char *match, int matchlen)
 873 {
 874         if (basecmp(item, base, match, matchlen))
 875                 return 0;
 876
 877         /*
 878          * If the base is a subdirectory of a path which
 879          * was specified, all of them are interesting.
 880          */
 881         if (!matchlen ||
 882             base[matchlen] == '/' ||
 883             match[matchlen - 1] == '/')
 884                 return 1;
 885
 886         /* Just a random prefix match */
 887         return 0;
 888 }
 889
 890 /*
 891  * Perform matching on the leading non-wildcard part of
 892  * pathspec. item->nowildcard_len must be greater than zero. Return
 893  * non-zero if base is matched.
 894  */
 895 static int match_wildcard_base(const struct pathspec_item *item,
 896                                const char *base, int baselen,
 897                                int *matched)
 898 {
 899         const char *match = item->match;
 900         /* the wildcard part is not considered in this function */
 901         int matchlen = item->nowildcard_len;
 902
 903         if (baselen) {
 904                 int dirlen;
 905                 /*
 906                  * Return early if base is longer than the
 907                  * non-wildcard part but it does not match.
 908                  */
 909                 if (baselen >= matchlen) {
 910                         *matched = matchlen;
 911                         return !basecmp(item, base, match, matchlen);
 912                 }
 913
 914                 dirlen = matchlen;
 915                 while (dirlen && match[dirlen - 1] != '/')
 916                         dirlen--;
 917
 918                 /*
 919                  * Return early if base is shorter than the
 920                  * non-wildcard part but it does not match. Note that
 921                  * base ends with '/' so we are sure it really matches
 922                  * directory
 923                  */
 924                 if (basecmp(item, base, match, baselen))
 925                         return 0;
 926                 *matched = baselen;
 927         } else
 928                 *matched = 0;
 929         /*
 930          * we could have checked entry against the non-wildcard part
 931          * that is not in base and does similar never_interesting
 932          * optimization as in match_entry. For now just be happy with
 933          * base comparison.
 934          */
 935         return entry_interesting;
 936 }
 937
 938 /*
 939  * Is a tree entry interesting given the pathspec we have?
 940  *
 941  * Pre-condition: either baselen == base_offset (i.e. empty path)
 942  * or base[baselen-1] == '/' (i.e. with trailing slash).
 943  */
 944 static enum interesting do_match(struct index_state *istate,
 945                                  const struct name_entry *entry,
 946                                  struct strbuf *base, int base_offset,
 947                                  const struct pathspec *ps,
 948                                  int exclude)
 949 {
 950         int i;
 951         int pathlen, baselen = base->len - base_offset;
 952         enum interesting never_interesting = ps->has_wildcard ?
 953                 entry_not_interesting : all_entries_not_interesting;
 954
 955         GUARD_PATHSPEC(ps,
 956                        PATHSPEC_FROMTOP |
 957                        PATHSPEC_MAXDEPTH |
 958                        PATHSPEC_LITERAL |
 959                        PATHSPEC_GLOB |
 960                        PATHSPEC_ICASE |
 961                        PATHSPEC_EXCLUDE |
 962                        PATHSPEC_ATTR);
 963
 964         if (!ps->nr) {
 965                 if (!ps->recursive ||
 966                     !(ps->magic & PATHSPEC_MAXDEPTH) ||
 967                     ps->max_depth == -1)
 968                         return all_entries_interesting;
 969                 return within_depth(base->buf + base_offset, baselen,
 970                                     !!S_ISDIR(entry->mode),
 971                                     ps->max_depth) ?
 972                         entry_interesting : entry_not_interesting;
 973         }
 974
 975         pathlen = tree_entry_len(entry);
 976
 977         for (i = ps->nr - 1; i >= 0; i--) {
 978                 const struct pathspec_item *item = ps->items+i;
 979                 const char *match = item->match;
 980                 const char *base_str = base->buf + base_offset;
 981                 int matchlen = item->len, matched = 0;
 982
 983                 if ((!exclude &&   item->magic & PATHSPEC_EXCLUDE) ||
 984                     ( exclude && !(item->magic & PATHSPEC_EXCLUDE)))
 985                         continue;
 986
 987                 if (baselen >= matchlen) {
 988                         /* If it doesn't match, move along... */
 989                         if (!match_dir_prefix(item, base_str, match, matchlen))
 990                                 goto match_wildcards;
 991
 992                         if (!ps->recursive ||
 993                             !(ps->magic & PATHSPEC_MAXDEPTH) ||
 994                             ps->max_depth == -1) {
 995                                 if (!item->attr_match_nr)
 996                                         return all_entries_interesting;
 997                                 else
 998                                         goto interesting;
 999                         }
1000
1001                         if (within_depth(base_str + matchlen + 1,
1002                                          baselen - matchlen - 1,
1003                                          !!S_ISDIR(entry->mode),
1004                                          ps->max_depth))
1005                                 goto interesting;
1006                         else
1007                                 return entry_not_interesting;
1008                 }
1009
1010                 /* Either there must be no base, or the base must match. */
1011                 if (baselen == 0 || !basecmp(item, base_str, match, baselen)) {
1012                         if (match_entry(item, entry, pathlen,
1013                                         match + baselen, matchlen - baselen,
1014                                         &never_interesting))
1015                                 goto interesting;
1016
1017                         if (item->nowildcard_len < item->len) {
1018                                 if (!git_fnmatch(item, match + baselen, entry->path,
1019                                                  item->nowildcard_len - baselen))
1020                                         goto interesting;
1021
1022                                 /*
1023                                  * Match all directories. We'll try to
1024                                  * match files later on.
1025                                  */
1026                                 if (ps->recursive && S_ISDIR(entry->mode))
1027                                         return entry_interesting;
1028
1029                                 /*
1030                                  * When matching against submodules with
1031                                  * wildcard characters, ensure that the entry
1032                                  * at least matches up to the first wild
1033                                  * character.  More accurate matching can then
1034                                  * be performed in the submodule itself.
1035                                  */
1036                                 if (ps->recurse_submodules &&
1037                                     S_ISGITLINK(entry->mode) &&
1038                                     !ps_strncmp(item, match + baselen,
1039                                                 entry->path,
1040                                                 item->nowildcard_len - baselen))
1041                                         goto interesting;
1042                         }
1043
1044                         continue;
1045                 }
1046
1047 match_wildcards:
1048                 if (item->nowildcard_len == item->len)
1049                         continue;
1050
1051                 if (item->nowildcard_len &&
1052                     !match_wildcard_base(item, base_str, baselen, &matched))
1053                         continue;
1054
1055                 /*
1056                  * Concatenate base and entry->path into one and do
1057                  * fnmatch() on it.
1058                  *
1059                  * While we could avoid concatenation in certain cases
1060                  * [1], which saves a memcpy and potentially a
1061                  * realloc, it turns out not worth it. Measurement on
1062                  * linux-2.6 does not show any clear improvements,
1063                  * partly because of the nowildcard_len optimization
1064                  * in git_fnmatch(). Avoid micro-optimizations here.
1065                  *
1066                  * [1] if match_wildcard_base() says the base
1067                  * directory is already matched, we only need to match
1068                  * the rest, which is shorter so _in theory_ faster.
1069                  */
1070
1071                 strbuf_add(base, entry->path, pathlen);
1072
1073                 if (!git_fnmatch(item, match, base->buf + base_offset,
1074                                  item->nowildcard_len)) {
1075                         strbuf_setlen(base, base_offset + baselen);
1076                         goto interesting;
1077                 }
1078
1079                 /*
1080                  * When matching against submodules with
1081                  * wildcard characters, ensure that the entry
1082                  * at least matches up to the first wild
1083                  * character.  More accurate matching can then
1084                  * be performed in the submodule itself.
1085                  */
1086                 if (ps->recurse_submodules && S_ISGITLINK(entry->mode) &&
1087                     !ps_strncmp(item, match, base->buf + base_offset,
1088                                 item->nowildcard_len)) {
1089                         strbuf_setlen(base, base_offset + baselen);
1090                         goto interesting;
1091                 }
1092
1093                 strbuf_setlen(base, base_offset + baselen);
1094
1095                 /*
1096                  * Match all directories. We'll try to match files
1097                  * later on.
1098                  * max_depth is ignored but we may consider support it
1099                  * in future, see
1100                  * https://public-inbox.org/git/7vmxo5l2g4.fsf@alter.siamese.dyndns.org/
1101                  */
1102                 if (ps->recursive && S_ISDIR(entry->mode))
1103                         return entry_interesting;
1104                 continue;
1105 interesting:
1106                 if (item->attr_match_nr) {
1107                         int ret;
1108
1109                         /*
1110                          * Must not return all_entries_not_interesting
1111                          * prematurely. We do not know if all entries do not
1112                          * match some attributes with current attr API.
1113                          */
1114                         never_interesting = entry_not_interesting;
1115
1116                         /*
1117                          * Consider all directories interesting (because some
1118                          * of those files inside may match some attributes
1119                          * even though the parent dir does not)
1120                          *
1121                          * FIXME: attributes _can_ match directories and we
1122                          * can probably return all_entries_interesting or
1123                          * all_entries_not_interesting here if matched.
1124                          */
1125                         if (S_ISDIR(entry->mode))
1126                                 return entry_interesting;
1127
1128                         strbuf_add(base, entry->path, pathlen);
1129                         ret = match_pathspec_attrs(istate, base->buf + base_offset,
1130                                                    base->len - base_offset, item);
1131                         strbuf_setlen(base, base_offset + baselen);
1132                         if (!ret)
1133                                 continue;
1134                 }
1135                 return entry_interesting;
1136         }
1137         return never_interesting; /* No matches */
1138 }
1139
1140 /*
1141  * Is a tree entry interesting given the pathspec we have?
1142  *
1143  * Pre-condition: either baselen == base_offset (i.e. empty path)
1144  * or base[baselen-1] == '/' (i.e. with trailing slash).
1145  */
1146 enum interesting tree_entry_interesting(struct index_state *istate,
1147                                         const struct name_entry *entry,
1148                                         struct strbuf *base, int base_offset,
1149                                         const struct pathspec *ps)
1150 {
1151         enum interesting positive, negative;
1152         positive = do_match(istate, entry, base, base_offset, ps, 0);
1153
1154         /*
1155          * case | entry | positive | negative | result
1156          * -----+-------+----------+----------+-------
1157          *   1  |  file |   -1     |  -1..2   |  -1
1158          *   2  |  file |    0     |  -1..2   |   0
1159          *   3  |  file |    1     |   -1     |   1
1160          *   4  |  file |    1     |    0     |   1
1161          *   5  |  file |    1     |    1     |   0
1162          *   6  |  file |    1     |    2     |   0
1163          *   7  |  file |    2     |   -1     |   2
1164          *   8  |  file |    2     |    0     |   1
1165          *   9  |  file |    2     |    1     |   0
1166          *  10  |  file |    2     |    2     |  -1
1167          * -----+-------+----------+----------+-------
1168          *  11  |  dir  |   -1     |  -1..2   |  -1
1169          *  12  |  dir  |    0     |  -1..2   |   0
1170          *  13  |  dir  |    1     |   -1     |   1
1171          *  14  |  dir  |    1     |    0     |   1
1172          *  15  |  dir  |    1     |    1     |   1 (*)
1173          *  16  |  dir  |    1     |    2     |   0
1174          *  17  |  dir  |    2     |   -1     |   2
1175          *  18  |  dir  |    2     |    0     |   1
1176          *  19  |  dir  |    2     |    1     |   1 (*)
1177          *  20  |  dir  |    2     |    2     |  -1
1178          *
1179          * (*) An exclude pattern interested in a directory does not
1180          * necessarily mean it will exclude all of the directory. In
1181          * wildcard case, it can't decide until looking at individual
1182          * files inside. So don't write such directories off yet.
1183          */
1184
1185         if (!(ps->magic & PATHSPEC_EXCLUDE) ||
1186             positive <= entry_not_interesting) /* #1, #2, #11, #12 */
1187                 return positive;
1188
1189         negative = do_match(istate, entry, base, base_offset, ps, 1);
1190
1191         /* #8, #18 */
1192         if (positive == all_entries_interesting &&
1193             negative == entry_not_interesting)
1194                 return entry_interesting;
1195
1196         /* #3, #4, #7, #13, #14, #17 */
1197         if (negative <= entry_not_interesting)
1198                 return positive;
1199
1200         /* #15, #19 */
1201         if (S_ISDIR(entry->mode) &&
1202             positive >= entry_interesting &&
1203             negative == entry_interesting)
1204                 return entry_interesting;
1205
1206         if ((positive == entry_interesting &&
1207              negative >= entry_interesting) || /* #5, #6, #16 */
1208             (positive == all_entries_interesting &&
1209              negative == entry_interesting)) /* #9 */
1210                 return entry_not_interesting;
1211
1212         return all_entries_not_interesting; /* #10, #20 */
1213 }