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