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