ls-tree: disable negative pathspec because it's not supported
[git] / tree-walk.c
1 #include "cache.h"
2 #include "tree-walk.h"
3 #include "unpack-trees.h"
4 #include "dir.h"
5 #include "tree.h"
6 #include "pathspec.h"
7
8 static const char *get_mode(const char *str, unsigned int *modep)
9 {
10         unsigned char c;
11         unsigned int mode = 0;
12
13         if (*str == ' ')
14                 return NULL;
15
16         while ((c = *str++) != ' ') {
17                 if (c < '0' || c > '7')
18                         return NULL;
19                 mode = (mode << 3) + (c - '0');
20         }
21         *modep = mode;
22         return str;
23 }
24
25 static void decode_tree_entry(struct tree_desc *desc, const char *buf, unsigned long size)
26 {
27         const char *path;
28         unsigned int mode, len;
29
30         if (size < 24 || buf[size - 21])
31                 die("corrupt tree file");
32
33         path = get_mode(buf, &mode);
34         if (!path || !*path)
35                 die("corrupt tree file");
36         len = strlen(path) + 1;
37
38         /* Initialize the descriptor entry */
39         desc->entry.path = path;
40         desc->entry.mode = canon_mode(mode);
41         desc->entry.sha1 = (const unsigned char *)(path + len);
42 }
43
44 void init_tree_desc(struct tree_desc *desc, const void *buffer, unsigned long size)
45 {
46         desc->buffer = buffer;
47         desc->size = size;
48         if (size)
49                 decode_tree_entry(desc, buffer, size);
50 }
51
52 void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)
53 {
54         unsigned long size = 0;
55         void *buf = NULL;
56
57         if (sha1) {
58                 buf = read_object_with_reference(sha1, tree_type, &size, NULL);
59                 if (!buf)
60                         die("unable to read tree %s", sha1_to_hex(sha1));
61         }
62         init_tree_desc(desc, buf, size);
63         return buf;
64 }
65
66 static void entry_clear(struct name_entry *a)
67 {
68         memset(a, 0, sizeof(*a));
69 }
70
71 static void entry_extract(struct tree_desc *t, struct name_entry *a)
72 {
73         *a = t->entry;
74 }
75
76 void update_tree_entry(struct tree_desc *desc)
77 {
78         const void *buf = desc->buffer;
79         const unsigned char *end = desc->entry.sha1 + 20;
80         unsigned long size = desc->size;
81         unsigned long len = end - (const unsigned char *)buf;
82
83         if (size < len)
84                 die("corrupt tree file");
85         buf = end;
86         size -= len;
87         desc->buffer = buf;
88         desc->size = size;
89         if (size)
90                 decode_tree_entry(desc, buf, size);
91 }
92
93 int tree_entry(struct tree_desc *desc, struct name_entry *entry)
94 {
95         if (!desc->size)
96                 return 0;
97
98         *entry = desc->entry;
99         update_tree_entry(desc);
100         return 1;
101 }
102
103 void setup_traverse_info(struct traverse_info *info, const char *base)
104 {
105         int pathlen = strlen(base);
106         static struct traverse_info dummy;
107
108         memset(info, 0, sizeof(*info));
109         if (pathlen && base[pathlen-1] == '/')
110                 pathlen--;
111         info->pathlen = pathlen ? pathlen + 1 : 0;
112         info->name.path = base;
113         info->name.sha1 = (void *)(base + pathlen + 1);
114         if (pathlen)
115                 info->prev = &dummy;
116 }
117
118 char *make_traverse_path(char *path, const struct traverse_info *info, const struct name_entry *n)
119 {
120         int len = tree_entry_len(n);
121         int pathlen = info->pathlen;
122
123         path[pathlen + len] = 0;
124         for (;;) {
125                 memcpy(path + pathlen, n->path, len);
126                 if (!pathlen)
127                         break;
128                 path[--pathlen] = '/';
129                 n = &info->name;
130                 len = tree_entry_len(n);
131                 info = info->prev;
132                 pathlen -= len;
133         }
134         return path;
135 }
136
137 struct tree_desc_skip {
138         struct tree_desc_skip *prev;
139         const void *ptr;
140 };
141
142 struct tree_desc_x {
143         struct tree_desc d;
144         struct tree_desc_skip *skip;
145 };
146
147 static int check_entry_match(const char *a, int a_len, const char *b, int b_len)
148 {
149         /*
150          * The caller wants to pick *a* from a tree or nothing.
151          * We are looking at *b* in a tree.
152          *
153          * (0) If a and b are the same name, we are trivially happy.
154          *
155          * There are three possibilities where *a* could be hiding
156          * behind *b*.
157          *
158          * (1) *a* == "t",   *b* == "ab"  i.e. *b* sorts earlier than *a* no
159          *                                matter what.
160          * (2) *a* == "t",   *b* == "t-2" and "t" is a subtree in the tree;
161          * (3) *a* == "t-2", *b* == "t"   and "t-2" is a blob in the tree.
162          *
163          * Otherwise we know *a* won't appear in the tree without
164          * scanning further.
165          */
166
167         int cmp = name_compare(a, a_len, b, b_len);
168
169         /* Most common case first -- reading sync'd trees */
170         if (!cmp)
171                 return cmp;
172
173         if (0 < cmp) {
174                 /* a comes after b; it does not matter if it is case (3)
175                 if (b_len < a_len && !memcmp(a, b, b_len) && a[b_len] < '/')
176                         return 1;
177                 */
178                 return 1; /* keep looking */
179         }
180
181         /* b comes after a; are we looking at case (2)? */
182         if (a_len < b_len && !memcmp(a, b, a_len) && b[a_len] < '/')
183                 return 1; /* keep looking */
184
185         return -1; /* a cannot appear in the tree */
186 }
187
188 /*
189  * From the extended tree_desc, extract the first name entry, while
190  * paying attention to the candidate "first" name.  Most importantly,
191  * when looking for an entry, if there are entries that sorts earlier
192  * in the tree object representation than that name, skip them and
193  * process the named entry first.  We will remember that we haven't
194  * processed the first entry yet, and in the later call skip the
195  * entry we processed early when update_extended_entry() is called.
196  *
197  * E.g. if the underlying tree object has these entries:
198  *
199  *    blob    "t-1"
200  *    blob    "t-2"
201  *    tree    "t"
202  *    blob    "t=1"
203  *
204  * and the "first" asks for "t", remember that we still need to
205  * process "t-1" and "t-2" but extract "t".  After processing the
206  * entry "t" from this call, the caller will let us know by calling
207  * update_extended_entry() that we can remember "t" has been processed
208  * already.
209  */
210
211 static void extended_entry_extract(struct tree_desc_x *t,
212                                    struct name_entry *a,
213                                    const char *first,
214                                    int first_len)
215 {
216         const char *path;
217         int len;
218         struct tree_desc probe;
219         struct tree_desc_skip *skip;
220
221         /*
222          * Extract the first entry from the tree_desc, but skip the
223          * ones that we already returned in earlier rounds.
224          */
225         while (1) {
226                 if (!t->d.size) {
227                         entry_clear(a);
228                         break; /* not found */
229                 }
230                 entry_extract(&t->d, a);
231                 for (skip = t->skip; skip; skip = skip->prev)
232                         if (a->path == skip->ptr)
233                                 break; /* found */
234                 if (!skip)
235                         break;
236                 /* We have processed this entry already. */
237                 update_tree_entry(&t->d);
238         }
239
240         if (!first || !a->path)
241                 return;
242
243         /*
244          * The caller wants "first" from this tree, or nothing.
245          */
246         path = a->path;
247         len = tree_entry_len(a);
248         switch (check_entry_match(first, first_len, path, len)) {
249         case -1:
250                 entry_clear(a);
251         case 0:
252                 return;
253         default:
254                 break;
255         }
256
257         /*
258          * We need to look-ahead -- we suspect that a subtree whose
259          * name is "first" may be hiding behind the current entry "path".
260          */
261         probe = t->d;
262         while (probe.size) {
263                 entry_extract(&probe, a);
264                 path = a->path;
265                 len = tree_entry_len(a);
266                 switch (check_entry_match(first, first_len, path, len)) {
267                 case -1:
268                         entry_clear(a);
269                 case 0:
270                         return;
271                 default:
272                         update_tree_entry(&probe);
273                         break;
274                 }
275                 /* keep looking */
276         }
277         entry_clear(a);
278 }
279
280 static void update_extended_entry(struct tree_desc_x *t, struct name_entry *a)
281 {
282         if (t->d.entry.path == a->path) {
283                 update_tree_entry(&t->d);
284         } else {
285                 /* we have returned this entry early */
286                 struct tree_desc_skip *skip = xmalloc(sizeof(*skip));
287                 skip->ptr = a->path;
288                 skip->prev = t->skip;
289                 t->skip = skip;
290         }
291 }
292
293 static void free_extended_entry(struct tree_desc_x *t)
294 {
295         struct tree_desc_skip *p, *s;
296
297         for (s = t->skip; s; s = p) {
298                 p = s->prev;
299                 free(s);
300         }
301 }
302
303 static inline int prune_traversal(struct name_entry *e,
304                                   struct traverse_info *info,
305                                   struct strbuf *base,
306                                   int still_interesting)
307 {
308         if (!info->pathspec || still_interesting == 2)
309                 return 2;
310         if (still_interesting < 0)
311                 return still_interesting;
312         return tree_entry_interesting(e, base, 0, info->pathspec);
313 }
314
315 int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
316 {
317         int error = 0;
318         struct name_entry *entry = xmalloc(n*sizeof(*entry));
319         int i;
320         struct tree_desc_x *tx = xcalloc(n, sizeof(*tx));
321         struct strbuf base = STRBUF_INIT;
322         int interesting = 1;
323
324         for (i = 0; i < n; i++)
325                 tx[i].d = t[i];
326
327         if (info->prev) {
328                 strbuf_grow(&base, info->pathlen);
329                 make_traverse_path(base.buf, info->prev, &info->name);
330                 base.buf[info->pathlen-1] = '/';
331                 strbuf_setlen(&base, info->pathlen);
332         }
333         for (;;) {
334                 int trees_used;
335                 unsigned long mask, dirmask;
336                 const char *first = NULL;
337                 int first_len = 0;
338                 struct name_entry *e = NULL;
339                 int len;
340
341                 for (i = 0; i < n; i++) {
342                         e = entry + i;
343                         extended_entry_extract(tx + i, e, NULL, 0);
344                 }
345
346                 /*
347                  * A tree may have "t-2" at the current location even
348                  * though it may have "t" that is a subtree behind it,
349                  * and another tree may return "t".  We want to grab
350                  * all "t" from all trees to match in such a case.
351                  */
352                 for (i = 0; i < n; i++) {
353                         e = entry + i;
354                         if (!e->path)
355                                 continue;
356                         len = tree_entry_len(e);
357                         if (!first) {
358                                 first = e->path;
359                                 first_len = len;
360                                 continue;
361                         }
362                         if (name_compare(e->path, len, first, first_len) < 0) {
363                                 first = e->path;
364                                 first_len = len;
365                         }
366                 }
367
368                 if (first) {
369                         for (i = 0; i < n; i++) {
370                                 e = entry + i;
371                                 extended_entry_extract(tx + i, e, first, first_len);
372                                 /* Cull the ones that are not the earliest */
373                                 if (!e->path)
374                                         continue;
375                                 len = tree_entry_len(e);
376                                 if (name_compare(e->path, len, first, first_len))
377                                         entry_clear(e);
378                         }
379                 }
380
381                 /* Now we have in entry[i] the earliest name from the trees */
382                 mask = 0;
383                 dirmask = 0;
384                 for (i = 0; i < n; i++) {
385                         if (!entry[i].path)
386                                 continue;
387                         mask |= 1ul << i;
388                         if (S_ISDIR(entry[i].mode))
389                                 dirmask |= 1ul << i;
390                         e = &entry[i];
391                 }
392                 if (!mask)
393                         break;
394                 interesting = prune_traversal(e, info, &base, interesting);
395                 if (interesting < 0)
396                         break;
397                 if (interesting) {
398                         trees_used = info->fn(n, mask, dirmask, entry, info);
399                         if (trees_used < 0) {
400                                 error = trees_used;
401                                 if (!info->show_all_errors)
402                                         break;
403                         }
404                         mask &= trees_used;
405                 }
406                 for (i = 0; i < n; i++)
407                         if (mask & (1ul << i))
408                                 update_extended_entry(tx + i, entry + i);
409         }
410         free(entry);
411         for (i = 0; i < n; i++)
412                 free_extended_entry(tx + i);
413         free(tx);
414         strbuf_release(&base);
415         return error;
416 }
417
418 static int find_tree_entry(struct tree_desc *t, const char *name, unsigned char *result, unsigned *mode)
419 {
420         int namelen = strlen(name);
421         while (t->size) {
422                 const char *entry;
423                 const unsigned char *sha1;
424                 int entrylen, cmp;
425
426                 sha1 = tree_entry_extract(t, &entry, mode);
427                 entrylen = tree_entry_len(&t->entry);
428                 update_tree_entry(t);
429                 if (entrylen > namelen)
430                         continue;
431                 cmp = memcmp(name, entry, entrylen);
432                 if (cmp > 0)
433                         continue;
434                 if (cmp < 0)
435                         break;
436                 if (entrylen == namelen) {
437                         hashcpy(result, sha1);
438                         return 0;
439                 }
440                 if (name[entrylen] != '/')
441                         continue;
442                 if (!S_ISDIR(*mode))
443                         break;
444                 if (++entrylen == namelen) {
445                         hashcpy(result, sha1);
446                         return 0;
447                 }
448                 return get_tree_entry(sha1, name + entrylen, result, mode);
449         }
450         return -1;
451 }
452
453 int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned char *sha1, unsigned *mode)
454 {
455         int retval;
456         void *tree;
457         unsigned long size;
458         unsigned char root[20];
459
460         tree = read_object_with_reference(tree_sha1, tree_type, &size, root);
461         if (!tree)
462                 return -1;
463
464         if (name[0] == '\0') {
465                 hashcpy(sha1, root);
466                 free(tree);
467                 return 0;
468         }
469
470         if (!size) {
471                 retval = -1;
472         } else {
473                 struct tree_desc t;
474                 init_tree_desc(&t, tree, size);
475                 retval = find_tree_entry(&t, name, sha1, mode);
476         }
477         free(tree);
478         return retval;
479 }
480
481 static int match_entry(const struct pathspec_item *item,
482                        const struct name_entry *entry, int pathlen,
483                        const char *match, int matchlen,
484                        enum interesting *never_interesting)
485 {
486         int m = -1; /* signals that we haven't called strncmp() */
487
488         if (item->magic & PATHSPEC_ICASE)
489                 /*
490                  * "Never interesting" trick requires exact
491                  * matching. We could do something clever with inexact
492                  * matching, but it's trickier (and not to forget that
493                  * strcasecmp is locale-dependent, at least in
494                  * glibc). Just disable it for now. It can't be worse
495                  * than the wildcard's codepath of '[Tt][Hi][Is][Ss]'
496                  * pattern.
497                  */
498                 *never_interesting = entry_not_interesting;
499         else if (*never_interesting != entry_not_interesting) {
500                 /*
501                  * We have not seen any match that sorts later
502                  * than the current path.
503                  */
504
505                 /*
506                  * Does match sort strictly earlier than path
507                  * with their common parts?
508                  */
509                 m = strncmp(match, entry->path,
510                             (matchlen < pathlen) ? matchlen : pathlen);
511                 if (m < 0)
512                         return 0;
513
514                 /*
515                  * If we come here even once, that means there is at
516                  * least one pathspec that would sort equal to or
517                  * later than the path we are currently looking at.
518                  * In other words, if we have never reached this point
519                  * after iterating all pathspecs, it means all
520                  * pathspecs are either outside of base, or inside the
521                  * base but sorts strictly earlier than the current
522                  * one.  In either case, they will never match the
523                  * subsequent entries.  In such a case, we initialized
524                  * the variable to -1 and that is what will be
525                  * returned, allowing the caller to terminate early.
526                  */
527                 *never_interesting = entry_not_interesting;
528         }
529
530         if (pathlen > matchlen)
531                 return 0;
532
533         if (matchlen > pathlen) {
534                 if (match[pathlen] != '/')
535                         return 0;
536                 if (!S_ISDIR(entry->mode) && !S_ISGITLINK(entry->mode))
537                         return 0;
538         }
539
540         if (m == -1)
541                 /*
542                  * we cheated and did not do strncmp(), so we do
543                  * that here.
544                  */
545                 m = ps_strncmp(item, match, entry->path, pathlen);
546
547         /*
548          * If common part matched earlier then it is a hit,
549          * because we rejected the case where path is not a
550          * leading directory and is shorter than match.
551          */
552         if (!m)
553                 /*
554                  * match_entry does not check if the prefix part is
555                  * matched case-sensitively. If the entry is a
556                  * directory and part of prefix, it'll be rematched
557                  * eventually by basecmp with special treatment for
558                  * the prefix.
559                  */
560                 return 1;
561
562         return 0;
563 }
564
565 /* :(icase)-aware string compare */
566 static int basecmp(const struct pathspec_item *item,
567                    const char *base, const char *match, int len)
568 {
569         if (item->magic & PATHSPEC_ICASE) {
570                 int ret, n = len > item->prefix ? item->prefix : len;
571                 ret = strncmp(base, match, n);
572                 if (ret)
573                         return ret;
574                 base += n;
575                 match += n;
576                 len -= n;
577         }
578         return ps_strncmp(item, base, match, len);
579 }
580
581 static int match_dir_prefix(const struct pathspec_item *item,
582                             const char *base,
583                             const char *match, int matchlen)
584 {
585         if (basecmp(item, base, match, matchlen))
586                 return 0;
587
588         /*
589          * If the base is a subdirectory of a path which
590          * was specified, all of them are interesting.
591          */
592         if (!matchlen ||
593             base[matchlen] == '/' ||
594             match[matchlen - 1] == '/')
595                 return 1;
596
597         /* Just a random prefix match */
598         return 0;
599 }
600
601 /*
602  * Perform matching on the leading non-wildcard part of
603  * pathspec. item->nowildcard_len must be greater than zero. Return
604  * non-zero if base is matched.
605  */
606 static int match_wildcard_base(const struct pathspec_item *item,
607                                const char *base, int baselen,
608                                int *matched)
609 {
610         const char *match = item->match;
611         /* the wildcard part is not considered in this function */
612         int matchlen = item->nowildcard_len;
613
614         if (baselen) {
615                 int dirlen;
616                 /*
617                  * Return early if base is longer than the
618                  * non-wildcard part but it does not match.
619                  */
620                 if (baselen >= matchlen) {
621                         *matched = matchlen;
622                         return !basecmp(item, base, match, matchlen);
623                 }
624
625                 dirlen = matchlen;
626                 while (dirlen && match[dirlen - 1] != '/')
627                         dirlen--;
628
629                 /*
630                  * Return early if base is shorter than the
631                  * non-wildcard part but it does not match. Note that
632                  * base ends with '/' so we are sure it really matches
633                  * directory
634                  */
635                 if (basecmp(item, base, match, baselen))
636                         return 0;
637                 *matched = baselen;
638         } else
639                 *matched = 0;
640         /*
641          * we could have checked entry against the non-wildcard part
642          * that is not in base and does similar never_interesting
643          * optimization as in match_entry. For now just be happy with
644          * base comparison.
645          */
646         return entry_interesting;
647 }
648
649 /*
650  * Is a tree entry interesting given the pathspec we have?
651  *
652  * Pre-condition: either baselen == base_offset (i.e. empty path)
653  * or base[baselen-1] == '/' (i.e. with trailing slash).
654  */
655 static enum interesting do_match(const struct name_entry *entry,
656                                  struct strbuf *base, int base_offset,
657                                  const struct pathspec *ps,
658                                  int exclude)
659 {
660         int i;
661         int pathlen, baselen = base->len - base_offset;
662         enum interesting never_interesting = ps->has_wildcard ?
663                 entry_not_interesting : all_entries_not_interesting;
664
665         GUARD_PATHSPEC(ps,
666                        PATHSPEC_FROMTOP |
667                        PATHSPEC_MAXDEPTH |
668                        PATHSPEC_LITERAL |
669                        PATHSPEC_GLOB |
670                        PATHSPEC_ICASE |
671                        PATHSPEC_EXCLUDE);
672
673         if (!ps->nr) {
674                 if (!ps->recursive ||
675                     !(ps->magic & PATHSPEC_MAXDEPTH) ||
676                     ps->max_depth == -1)
677                         return all_entries_interesting;
678                 return within_depth(base->buf + base_offset, baselen,
679                                     !!S_ISDIR(entry->mode),
680                                     ps->max_depth) ?
681                         entry_interesting : entry_not_interesting;
682         }
683
684         pathlen = tree_entry_len(entry);
685
686         for (i = ps->nr - 1; i >= 0; i--) {
687                 const struct pathspec_item *item = ps->items+i;
688                 const char *match = item->match;
689                 const char *base_str = base->buf + base_offset;
690                 int matchlen = item->len, matched = 0;
691
692                 if ((!exclude &&   item->magic & PATHSPEC_EXCLUDE) ||
693                     ( exclude && !(item->magic & PATHSPEC_EXCLUDE)))
694                         continue;
695
696                 if (baselen >= matchlen) {
697                         /* If it doesn't match, move along... */
698                         if (!match_dir_prefix(item, base_str, match, matchlen))
699                                 goto match_wildcards;
700
701                         if (!ps->recursive ||
702                             !(ps->magic & PATHSPEC_MAXDEPTH) ||
703                             ps->max_depth == -1)
704                                 return all_entries_interesting;
705
706                         return within_depth(base_str + matchlen + 1,
707                                             baselen - matchlen - 1,
708                                             !!S_ISDIR(entry->mode),
709                                             ps->max_depth) ?
710                                 entry_interesting : entry_not_interesting;
711                 }
712
713                 /* Either there must be no base, or the base must match. */
714                 if (baselen == 0 || !basecmp(item, base_str, match, baselen)) {
715                         if (match_entry(item, entry, pathlen,
716                                         match + baselen, matchlen - baselen,
717                                         &never_interesting))
718                                 return entry_interesting;
719
720                         if (item->nowildcard_len < item->len) {
721                                 if (!git_fnmatch(item, match + baselen, entry->path,
722                                                  item->nowildcard_len - baselen))
723                                         return entry_interesting;
724
725                                 /*
726                                  * Match all directories. We'll try to
727                                  * match files later on.
728                                  */
729                                 if (ps->recursive && S_ISDIR(entry->mode))
730                                         return entry_interesting;
731                         }
732
733                         continue;
734                 }
735
736 match_wildcards:
737                 if (item->nowildcard_len == item->len)
738                         continue;
739
740                 if (item->nowildcard_len &&
741                     !match_wildcard_base(item, base_str, baselen, &matched))
742                         continue;
743
744                 /*
745                  * Concatenate base and entry->path into one and do
746                  * fnmatch() on it.
747                  *
748                  * While we could avoid concatenation in certain cases
749                  * [1], which saves a memcpy and potentially a
750                  * realloc, it turns out not worth it. Measurement on
751                  * linux-2.6 does not show any clear improvements,
752                  * partly because of the nowildcard_len optimization
753                  * in git_fnmatch(). Avoid micro-optimizations here.
754                  *
755                  * [1] if match_wildcard_base() says the base
756                  * directory is already matched, we only need to match
757                  * the rest, which is shorter so _in theory_ faster.
758                  */
759
760                 strbuf_add(base, entry->path, pathlen);
761
762                 if (!git_fnmatch(item, match, base->buf + base_offset,
763                                  item->nowildcard_len)) {
764                         strbuf_setlen(base, base_offset + baselen);
765                         return entry_interesting;
766                 }
767                 strbuf_setlen(base, base_offset + baselen);
768
769                 /*
770                  * Match all directories. We'll try to match files
771                  * later on.
772                  * max_depth is ignored but we may consider support it
773                  * in future, see
774                  * http://thread.gmane.org/gmane.comp.version-control.git/163757/focus=163840
775                  */
776                 if (ps->recursive && S_ISDIR(entry->mode))
777                         return entry_interesting;
778         }
779         return never_interesting; /* No matches */
780 }
781
782 /*
783  * Is a tree entry interesting given the pathspec we have?
784  *
785  * Pre-condition: either baselen == base_offset (i.e. empty path)
786  * or base[baselen-1] == '/' (i.e. with trailing slash).
787  */
788 enum interesting tree_entry_interesting(const struct name_entry *entry,
789                                         struct strbuf *base, int base_offset,
790                                         const struct pathspec *ps)
791 {
792         enum interesting positive, negative;
793         positive = do_match(entry, base, base_offset, ps, 0);
794
795         /*
796          * case | entry | positive | negative | result
797          * -----+-------+----------+----------+-------
798          *   1  |  file |   -1     |  -1..2   |  -1
799          *   2  |  file |    0     |  -1..2   |   0
800          *   3  |  file |    1     |   -1     |   1
801          *   4  |  file |    1     |    0     |   1
802          *   5  |  file |    1     |    1     |   0
803          *   6  |  file |    1     |    2     |   0
804          *   7  |  file |    2     |   -1     |   2
805          *   8  |  file |    2     |    0     |   2
806          *   9  |  file |    2     |    1     |   0
807          *  10  |  file |    2     |    2     |  -1
808          * -----+-------+----------+----------+-------
809          *  11  |  dir  |   -1     |  -1..2   |  -1
810          *  12  |  dir  |    0     |  -1..2   |   0
811          *  13  |  dir  |    1     |   -1     |   1
812          *  14  |  dir  |    1     |    0     |   1
813          *  15  |  dir  |    1     |    1     |   1 (*)
814          *  16  |  dir  |    1     |    2     |   0
815          *  17  |  dir  |    2     |   -1     |   2
816          *  18  |  dir  |    2     |    0     |   2
817          *  19  |  dir  |    2     |    1     |   1 (*)
818          *  20  |  dir  |    2     |    2     |  -1
819          *
820          * (*) An exclude pattern interested in a directory does not
821          * necessarily mean it will exclude all of the directory. In
822          * wildcard case, it can't decide until looking at individual
823          * files inside. So don't write such directories off yet.
824          */
825
826         if (!(ps->magic & PATHSPEC_EXCLUDE) ||
827             positive <= entry_not_interesting) /* #1, #2, #11, #12 */
828                 return positive;
829
830         negative = do_match(entry, base, base_offset, ps, 1);
831
832         /* #3, #4, #7, #8, #13, #14, #17, #18 */
833         if (negative <= entry_not_interesting)
834                 return positive;
835
836         /* #15, #19 */
837         if (S_ISDIR(entry->mode) &&
838             positive >= entry_interesting &&
839             negative == entry_interesting)
840                 return entry_interesting;
841
842         if ((positive == entry_interesting &&
843              negative >= entry_interesting) || /* #5, #6, #16 */
844             (positive == all_entries_interesting &&
845              negative == entry_interesting)) /* #9 */
846                 return entry_not_interesting;
847
848         return all_entries_not_interesting; /* #10, #20 */
849 }