unicode: update the width tables to Unicode 15
[git.git] / tree-walk.c
blob74f4d710e8f0f28410fae49a6b9c31bf1045e0ca
1 #include "cache.h"
2 #include "tree-walk.h"
3 #include "dir.h"
4 #include "object-store.h"
5 #include "tree.h"
6 #include "pathspec.h"
7 #include "json-writer.h"
9 static const char *get_mode(const char *str, unsigned int *modep)
11 unsigned char c;
12 unsigned int mode = 0;
14 if (*str == ' ')
15 return NULL;
17 while ((c = *str++) != ' ') {
18 if (c < '0' || c > '7')
19 return NULL;
20 mode = (mode << 3) + (c - '0');
22 *modep = mode;
23 return str;
26 static int decode_tree_entry(struct tree_desc *desc, const char *buf, unsigned long size, struct strbuf *err)
28 const char *path;
29 unsigned int mode, len;
30 const unsigned hashsz = the_hash_algo->rawsz;
32 if (size < hashsz + 3 || buf[size - (hashsz + 1)]) {
33 strbuf_addstr(err, _("too-short tree object"));
34 return -1;
37 path = get_mode(buf, &mode);
38 if (!path) {
39 strbuf_addstr(err, _("malformed mode in tree entry"));
40 return -1;
42 if (!*path) {
43 strbuf_addstr(err, _("empty filename in tree entry"));
44 return -1;
46 len = strlen(path) + 1;
48 /* Initialize the descriptor entry */
49 desc->entry.path = path;
50 desc->entry.mode = (desc->flags & TREE_DESC_RAW_MODES) ? mode : canon_mode(mode);
51 desc->entry.pathlen = len - 1;
52 oidread(&desc->entry.oid, (const unsigned char *)path + len);
54 return 0;
57 static int init_tree_desc_internal(struct tree_desc *desc, const void *buffer,
58 unsigned long size, struct strbuf *err,
59 enum tree_desc_flags flags)
61 desc->buffer = buffer;
62 desc->size = size;
63 desc->flags = flags;
64 if (size)
65 return decode_tree_entry(desc, buffer, size, err);
66 return 0;
69 void init_tree_desc(struct tree_desc *desc, const void *buffer, unsigned long size)
71 struct strbuf err = STRBUF_INIT;
72 if (init_tree_desc_internal(desc, buffer, size, &err, 0))
73 die("%s", err.buf);
74 strbuf_release(&err);
77 int init_tree_desc_gently(struct tree_desc *desc, const void *buffer, unsigned long size,
78 enum tree_desc_flags flags)
80 struct strbuf err = STRBUF_INIT;
81 int result = init_tree_desc_internal(desc, buffer, size, &err, flags);
82 if (result)
83 error("%s", err.buf);
84 strbuf_release(&err);
85 return result;
88 void *fill_tree_descriptor(struct repository *r,
89 struct tree_desc *desc,
90 const struct object_id *oid)
92 unsigned long size = 0;
93 void *buf = NULL;
95 if (oid) {
96 buf = read_object_with_reference(r, oid, OBJ_TREE, &size, NULL);
97 if (!buf)
98 die("unable to read tree %s", oid_to_hex(oid));
100 init_tree_desc(desc, buf, size);
101 return buf;
104 static void entry_clear(struct name_entry *a)
106 memset(a, 0, sizeof(*a));
109 static void entry_extract(struct tree_desc *t, struct name_entry *a)
111 *a = t->entry;
114 static int update_tree_entry_internal(struct tree_desc *desc, struct strbuf *err)
116 const void *buf = desc->buffer;
117 const unsigned char *end = (const unsigned char *)desc->entry.path + desc->entry.pathlen + 1 + the_hash_algo->rawsz;
118 unsigned long size = desc->size;
119 unsigned long len = end - (const unsigned char *)buf;
121 if (size < len)
122 die(_("too-short tree file"));
123 buf = end;
124 size -= len;
125 desc->buffer = buf;
126 desc->size = size;
127 if (size)
128 return decode_tree_entry(desc, buf, size, err);
129 return 0;
132 void update_tree_entry(struct tree_desc *desc)
134 struct strbuf err = STRBUF_INIT;
135 if (update_tree_entry_internal(desc, &err))
136 die("%s", err.buf);
137 strbuf_release(&err);
140 int update_tree_entry_gently(struct tree_desc *desc)
142 struct strbuf err = STRBUF_INIT;
143 if (update_tree_entry_internal(desc, &err)) {
144 error("%s", err.buf);
145 strbuf_release(&err);
146 /* Stop processing this tree after error */
147 desc->size = 0;
148 return -1;
150 strbuf_release(&err);
151 return 0;
154 int tree_entry(struct tree_desc *desc, struct name_entry *entry)
156 if (!desc->size)
157 return 0;
159 *entry = desc->entry;
160 update_tree_entry(desc);
161 return 1;
164 int tree_entry_gently(struct tree_desc *desc, struct name_entry *entry)
166 if (!desc->size)
167 return 0;
169 *entry = desc->entry;
170 if (update_tree_entry_gently(desc))
171 return 0;
172 return 1;
175 static int traverse_trees_atexit_registered;
176 static int traverse_trees_count;
177 static int traverse_trees_cur_depth;
178 static int traverse_trees_max_depth;
180 static void trace2_traverse_trees_statistics_atexit(void)
182 struct json_writer jw = JSON_WRITER_INIT;
184 jw_object_begin(&jw, 0);
185 jw_object_intmax(&jw, "traverse_trees_count", traverse_trees_count);
186 jw_object_intmax(&jw, "traverse_trees_max_depth", traverse_trees_max_depth);
187 jw_end(&jw);
189 trace2_data_json("traverse_trees", the_repository, "statistics", &jw);
191 jw_release(&jw);
194 void setup_traverse_info(struct traverse_info *info, const char *base)
196 size_t pathlen = strlen(base);
197 static struct traverse_info dummy;
199 memset(info, 0, sizeof(*info));
200 if (pathlen && base[pathlen-1] == '/')
201 pathlen--;
202 info->pathlen = pathlen ? pathlen + 1 : 0;
203 info->name = base;
204 info->namelen = pathlen;
205 if (pathlen)
206 info->prev = &dummy;
208 if (trace2_is_enabled() && !traverse_trees_atexit_registered) {
209 atexit(trace2_traverse_trees_statistics_atexit);
210 traverse_trees_atexit_registered = 1;
214 char *make_traverse_path(char *path, size_t pathlen,
215 const struct traverse_info *info,
216 const char *name, size_t namelen)
218 /* Always points to the end of the name we're about to add */
219 size_t pos = st_add(info->pathlen, namelen);
221 if (pos >= pathlen)
222 BUG("too small buffer passed to make_traverse_path");
224 path[pos] = 0;
225 for (;;) {
226 if (pos < namelen)
227 BUG("traverse_info pathlen does not match strings");
228 pos -= namelen;
229 memcpy(path + pos, name, namelen);
231 if (!pos)
232 break;
233 path[--pos] = '/';
235 if (!info)
236 BUG("traverse_info ran out of list items");
237 name = info->name;
238 namelen = info->namelen;
239 info = info->prev;
241 return path;
244 void strbuf_make_traverse_path(struct strbuf *out,
245 const struct traverse_info *info,
246 const char *name, size_t namelen)
248 size_t len = traverse_path_len(info, namelen);
250 strbuf_grow(out, len);
251 make_traverse_path(out->buf + out->len, out->alloc - out->len,
252 info, name, namelen);
253 strbuf_setlen(out, out->len + len);
256 struct tree_desc_skip {
257 struct tree_desc_skip *prev;
258 const void *ptr;
261 struct tree_desc_x {
262 struct tree_desc d;
263 struct tree_desc_skip *skip;
266 static int check_entry_match(const char *a, int a_len, const char *b, int b_len)
269 * The caller wants to pick *a* from a tree or nothing.
270 * We are looking at *b* in a tree.
272 * (0) If a and b are the same name, we are trivially happy.
274 * There are three possibilities where *a* could be hiding
275 * behind *b*.
277 * (1) *a* == "t", *b* == "ab" i.e. *b* sorts earlier than *a* no
278 * matter what.
279 * (2) *a* == "t", *b* == "t-2" and "t" is a subtree in the tree;
280 * (3) *a* == "t-2", *b* == "t" and "t-2" is a blob in the tree.
282 * Otherwise we know *a* won't appear in the tree without
283 * scanning further.
286 int cmp = name_compare(a, a_len, b, b_len);
288 /* Most common case first -- reading sync'd trees */
289 if (!cmp)
290 return cmp;
292 if (0 < cmp) {
293 /* a comes after b; it does not matter if it is case (3)
294 if (b_len < a_len && !memcmp(a, b, b_len) && a[b_len] < '/')
295 return 1;
297 return 1; /* keep looking */
300 /* b comes after a; are we looking at case (2)? */
301 if (a_len < b_len && !memcmp(a, b, a_len) && b[a_len] < '/')
302 return 1; /* keep looking */
304 return -1; /* a cannot appear in the tree */
308 * From the extended tree_desc, extract the first name entry, while
309 * paying attention to the candidate "first" name. Most importantly,
310 * when looking for an entry, if there are entries that sorts earlier
311 * in the tree object representation than that name, skip them and
312 * process the named entry first. We will remember that we haven't
313 * processed the first entry yet, and in the later call skip the
314 * entry we processed early when update_extended_entry() is called.
316 * E.g. if the underlying tree object has these entries:
318 * blob "t-1"
319 * blob "t-2"
320 * tree "t"
321 * blob "t=1"
323 * and the "first" asks for "t", remember that we still need to
324 * process "t-1" and "t-2" but extract "t". After processing the
325 * entry "t" from this call, the caller will let us know by calling
326 * update_extended_entry() that we can remember "t" has been processed
327 * already.
330 static void extended_entry_extract(struct tree_desc_x *t,
331 struct name_entry *a,
332 const char *first,
333 int first_len)
335 const char *path;
336 int len;
337 struct tree_desc probe;
338 struct tree_desc_skip *skip;
341 * Extract the first entry from the tree_desc, but skip the
342 * ones that we already returned in earlier rounds.
344 while (1) {
345 if (!t->d.size) {
346 entry_clear(a);
347 break; /* not found */
349 entry_extract(&t->d, a);
350 for (skip = t->skip; skip; skip = skip->prev)
351 if (a->path == skip->ptr)
352 break; /* found */
353 if (!skip)
354 break;
355 /* We have processed this entry already. */
356 update_tree_entry(&t->d);
359 if (!first || !a->path)
360 return;
363 * The caller wants "first" from this tree, or nothing.
365 path = a->path;
366 len = tree_entry_len(a);
367 switch (check_entry_match(first, first_len, path, len)) {
368 case -1:
369 entry_clear(a);
370 case 0:
371 return;
372 default:
373 break;
377 * We need to look-ahead -- we suspect that a subtree whose
378 * name is "first" may be hiding behind the current entry "path".
380 probe = t->d;
381 while (probe.size) {
382 entry_extract(&probe, a);
383 path = a->path;
384 len = tree_entry_len(a);
385 switch (check_entry_match(first, first_len, path, len)) {
386 case -1:
387 entry_clear(a);
388 case 0:
389 return;
390 default:
391 update_tree_entry(&probe);
392 break;
394 /* keep looking */
396 entry_clear(a);
399 static void update_extended_entry(struct tree_desc_x *t, struct name_entry *a)
401 if (t->d.entry.path == a->path) {
402 update_tree_entry(&t->d);
403 } else {
404 /* we have returned this entry early */
405 struct tree_desc_skip *skip = xmalloc(sizeof(*skip));
406 skip->ptr = a->path;
407 skip->prev = t->skip;
408 t->skip = skip;
412 static void free_extended_entry(struct tree_desc_x *t)
414 struct tree_desc_skip *p, *s;
416 for (s = t->skip; s; s = p) {
417 p = s->prev;
418 free(s);
422 static inline int prune_traversal(struct index_state *istate,
423 struct name_entry *e,
424 struct traverse_info *info,
425 struct strbuf *base,
426 int still_interesting)
428 if (!info->pathspec || still_interesting == 2)
429 return 2;
430 if (still_interesting < 0)
431 return still_interesting;
432 return tree_entry_interesting(istate, e, base,
433 0, info->pathspec);
436 int traverse_trees(struct index_state *istate,
437 int n, struct tree_desc *t,
438 struct traverse_info *info)
440 int error = 0;
441 struct name_entry entry[MAX_TRAVERSE_TREES];
442 int i;
443 struct tree_desc_x tx[ARRAY_SIZE(entry)];
444 struct strbuf base = STRBUF_INIT;
445 int interesting = 1;
446 char *traverse_path;
448 traverse_trees_count++;
449 traverse_trees_cur_depth++;
451 if (traverse_trees_cur_depth > traverse_trees_max_depth)
452 traverse_trees_max_depth = traverse_trees_cur_depth;
454 if (n >= ARRAY_SIZE(entry))
455 BUG("traverse_trees() called with too many trees (%d)", n);
457 for (i = 0; i < n; i++) {
458 tx[i].d = t[i];
459 tx[i].skip = NULL;
462 if (info->prev) {
463 strbuf_make_traverse_path(&base, info->prev,
464 info->name, info->namelen);
465 strbuf_addch(&base, '/');
466 traverse_path = xstrndup(base.buf, base.len);
467 } else {
468 traverse_path = xstrndup(info->name, info->pathlen);
470 info->traverse_path = traverse_path;
471 for (;;) {
472 int trees_used;
473 unsigned long mask, dirmask;
474 const char *first = NULL;
475 int first_len = 0;
476 struct name_entry *e = NULL;
477 int len;
479 for (i = 0; i < n; i++) {
480 e = entry + i;
481 extended_entry_extract(tx + i, e, NULL, 0);
485 * A tree may have "t-2" at the current location even
486 * though it may have "t" that is a subtree behind it,
487 * and another tree may return "t". We want to grab
488 * all "t" from all trees to match in such a case.
490 for (i = 0; i < n; i++) {
491 e = entry + i;
492 if (!e->path)
493 continue;
494 len = tree_entry_len(e);
495 if (!first) {
496 first = e->path;
497 first_len = len;
498 continue;
500 if (name_compare(e->path, len, first, first_len) < 0) {
501 first = e->path;
502 first_len = len;
506 if (first) {
507 for (i = 0; i < n; i++) {
508 e = entry + i;
509 extended_entry_extract(tx + i, e, first, first_len);
510 /* Cull the ones that are not the earliest */
511 if (!e->path)
512 continue;
513 len = tree_entry_len(e);
514 if (name_compare(e->path, len, first, first_len))
515 entry_clear(e);
519 /* Now we have in entry[i] the earliest name from the trees */
520 mask = 0;
521 dirmask = 0;
522 for (i = 0; i < n; i++) {
523 if (!entry[i].path)
524 continue;
525 mask |= 1ul << i;
526 if (S_ISDIR(entry[i].mode))
527 dirmask |= 1ul << i;
528 e = &entry[i];
530 if (!mask)
531 break;
532 interesting = prune_traversal(istate, e, info, &base, interesting);
533 if (interesting < 0)
534 break;
535 if (interesting) {
536 trees_used = info->fn(n, mask, dirmask, entry, info);
537 if (trees_used < 0) {
538 error = trees_used;
539 if (!info->show_all_errors)
540 break;
542 mask &= trees_used;
544 for (i = 0; i < n; i++)
545 if (mask & (1ul << i))
546 update_extended_entry(tx + i, entry + i);
548 for (i = 0; i < n; i++)
549 free_extended_entry(tx + i);
550 free(traverse_path);
551 info->traverse_path = NULL;
552 strbuf_release(&base);
554 traverse_trees_cur_depth--;
555 return error;
558 struct dir_state {
559 void *tree;
560 unsigned long size;
561 struct object_id oid;
564 static int find_tree_entry(struct repository *r, struct tree_desc *t,
565 const char *name, struct object_id *result,
566 unsigned short *mode)
568 int namelen = strlen(name);
569 while (t->size) {
570 const char *entry;
571 struct object_id oid;
572 int entrylen, cmp;
574 oidcpy(&oid, tree_entry_extract(t, &entry, mode));
575 entrylen = tree_entry_len(&t->entry);
576 update_tree_entry(t);
577 if (entrylen > namelen)
578 continue;
579 cmp = memcmp(name, entry, entrylen);
580 if (cmp > 0)
581 continue;
582 if (cmp < 0)
583 break;
584 if (entrylen == namelen) {
585 oidcpy(result, &oid);
586 return 0;
588 if (name[entrylen] != '/')
589 continue;
590 if (!S_ISDIR(*mode))
591 break;
592 if (++entrylen == namelen) {
593 oidcpy(result, &oid);
594 return 0;
596 return get_tree_entry(r, &oid, name + entrylen, result, mode);
598 return -1;
601 int get_tree_entry(struct repository *r,
602 const struct object_id *tree_oid,
603 const char *name,
604 struct object_id *oid,
605 unsigned short *mode)
607 int retval;
608 void *tree;
609 unsigned long size;
610 struct object_id root;
612 tree = read_object_with_reference(r, tree_oid, OBJ_TREE, &size, &root);
613 if (!tree)
614 return -1;
616 if (name[0] == '\0') {
617 oidcpy(oid, &root);
618 free(tree);
619 return 0;
622 if (!size) {
623 retval = -1;
624 } else {
625 struct tree_desc t;
626 init_tree_desc(&t, tree, size);
627 retval = find_tree_entry(r, &t, name, oid, mode);
629 free(tree);
630 return retval;
634 * This is Linux's built-in max for the number of symlinks to follow.
635 * That limit, of course, does not affect git, but it's a reasonable
636 * choice.
638 #define GET_TREE_ENTRY_FOLLOW_SYMLINKS_MAX_LINKS 40
641 * Find a tree entry by following symlinks in tree_sha (which is
642 * assumed to be the root of the repository). In the event that a
643 * symlink points outside the repository (e.g. a link to /foo or a
644 * root-level link to ../foo), the portion of the link which is
645 * outside the repository will be returned in result_path, and *mode
646 * will be set to 0. It is assumed that result_path is uninitialized.
647 * If there are no symlinks, or the end result of the symlink chain
648 * points to an object inside the repository, result will be filled in
649 * with the sha1 of the found object, and *mode will hold the mode of
650 * the object.
652 * See the code for enum get_oid_result for a description of
653 * the return values.
655 enum get_oid_result get_tree_entry_follow_symlinks(struct repository *r,
656 struct object_id *tree_oid, const char *name,
657 struct object_id *result, struct strbuf *result_path,
658 unsigned short *mode)
660 int retval = MISSING_OBJECT;
661 struct dir_state *parents = NULL;
662 size_t parents_alloc = 0;
663 size_t i, parents_nr = 0;
664 struct object_id current_tree_oid;
665 struct strbuf namebuf = STRBUF_INIT;
666 struct tree_desc t;
667 int follows_remaining = GET_TREE_ENTRY_FOLLOW_SYMLINKS_MAX_LINKS;
669 init_tree_desc(&t, NULL, 0UL);
670 strbuf_addstr(&namebuf, name);
671 oidcpy(&current_tree_oid, tree_oid);
673 while (1) {
674 int find_result;
675 char *first_slash;
676 char *remainder = NULL;
678 if (!t.buffer) {
679 void *tree;
680 struct object_id root;
681 unsigned long size;
682 tree = read_object_with_reference(r,
683 &current_tree_oid,
684 OBJ_TREE, &size,
685 &root);
686 if (!tree)
687 goto done;
689 ALLOC_GROW(parents, parents_nr + 1, parents_alloc);
690 parents[parents_nr].tree = tree;
691 parents[parents_nr].size = size;
692 oidcpy(&parents[parents_nr].oid, &root);
693 parents_nr++;
695 if (namebuf.buf[0] == '\0') {
696 oidcpy(result, &root);
697 retval = FOUND;
698 goto done;
701 if (!size)
702 goto done;
704 /* descend */
705 init_tree_desc(&t, tree, size);
708 /* Handle symlinks to e.g. a//b by removing leading slashes */
709 while (namebuf.buf[0] == '/') {
710 strbuf_remove(&namebuf, 0, 1);
713 /* Split namebuf into a first component and a remainder */
714 if ((first_slash = strchr(namebuf.buf, '/'))) {
715 *first_slash = 0;
716 remainder = first_slash + 1;
719 if (!strcmp(namebuf.buf, "..")) {
720 struct dir_state *parent;
722 * We could end up with .. in the namebuf if it
723 * appears in a symlink.
726 if (parents_nr == 1) {
727 if (remainder)
728 *first_slash = '/';
729 strbuf_add(result_path, namebuf.buf,
730 namebuf.len);
731 *mode = 0;
732 retval = FOUND;
733 goto done;
735 parent = &parents[parents_nr - 1];
736 free(parent->tree);
737 parents_nr--;
738 parent = &parents[parents_nr - 1];
739 init_tree_desc(&t, parent->tree, parent->size);
740 strbuf_remove(&namebuf, 0, remainder ? 3 : 2);
741 continue;
744 /* We could end up here via a symlink to dir/.. */
745 if (namebuf.buf[0] == '\0') {
746 oidcpy(result, &parents[parents_nr - 1].oid);
747 retval = FOUND;
748 goto done;
751 /* Look up the first (or only) path component in the tree. */
752 find_result = find_tree_entry(r, &t, namebuf.buf,
753 &current_tree_oid, mode);
754 if (find_result) {
755 goto done;
758 if (S_ISDIR(*mode)) {
759 if (!remainder) {
760 oidcpy(result, &current_tree_oid);
761 retval = FOUND;
762 goto done;
764 /* Descend the tree */
765 t.buffer = NULL;
766 strbuf_remove(&namebuf, 0,
767 1 + first_slash - namebuf.buf);
768 } else if (S_ISREG(*mode)) {
769 if (!remainder) {
770 oidcpy(result, &current_tree_oid);
771 retval = FOUND;
772 } else {
773 retval = NOT_DIR;
775 goto done;
776 } else if (S_ISLNK(*mode)) {
777 /* Follow a symlink */
778 unsigned long link_len;
779 size_t len;
780 char *contents, *contents_start;
781 struct dir_state *parent;
782 enum object_type type;
784 if (follows_remaining-- == 0) {
785 /* Too many symlinks followed */
786 retval = SYMLINK_LOOP;
787 goto done;
791 * At this point, we have followed at a least
792 * one symlink, so on error we need to report this.
794 retval = DANGLING_SYMLINK;
796 contents = repo_read_object_file(r,
797 &current_tree_oid, &type,
798 &link_len);
800 if (!contents)
801 goto done;
803 if (contents[0] == '/') {
804 strbuf_addstr(result_path, contents);
805 free(contents);
806 *mode = 0;
807 retval = FOUND;
808 goto done;
811 if (remainder)
812 len = first_slash - namebuf.buf;
813 else
814 len = namebuf.len;
816 contents_start = contents;
818 parent = &parents[parents_nr - 1];
819 init_tree_desc(&t, parent->tree, parent->size);
820 strbuf_splice(&namebuf, 0, len,
821 contents_start, link_len);
822 if (remainder)
823 namebuf.buf[link_len] = '/';
824 free(contents);
827 done:
828 for (i = 0; i < parents_nr; i++)
829 free(parents[i].tree);
830 free(parents);
832 strbuf_release(&namebuf);
833 return retval;
836 static int match_entry(const struct pathspec_item *item,
837 const struct name_entry *entry, int pathlen,
838 const char *match, int matchlen,
839 enum interesting *never_interesting)
841 int m = -1; /* signals that we haven't called strncmp() */
843 if (item->magic & PATHSPEC_ICASE)
845 * "Never interesting" trick requires exact
846 * matching. We could do something clever with inexact
847 * matching, but it's trickier (and not to forget that
848 * strcasecmp is locale-dependent, at least in
849 * glibc). Just disable it for now. It can't be worse
850 * than the wildcard's codepath of '[Tt][Hi][Is][Ss]'
851 * pattern.
853 *never_interesting = entry_not_interesting;
854 else if (*never_interesting != entry_not_interesting) {
856 * We have not seen any match that sorts later
857 * than the current path.
861 * Does match sort strictly earlier than path
862 * with their common parts?
864 m = strncmp(match, entry->path,
865 (matchlen < pathlen) ? matchlen : pathlen);
866 if (m < 0)
867 return 0;
870 * If we come here even once, that means there is at
871 * least one pathspec that would sort equal to or
872 * later than the path we are currently looking at.
873 * In other words, if we have never reached this point
874 * after iterating all pathspecs, it means all
875 * pathspecs are either outside of base, or inside the
876 * base but sorts strictly earlier than the current
877 * one. In either case, they will never match the
878 * subsequent entries. In such a case, we initialized
879 * the variable to -1 and that is what will be
880 * returned, allowing the caller to terminate early.
882 *never_interesting = entry_not_interesting;
885 if (pathlen > matchlen)
886 return 0;
888 if (matchlen > pathlen) {
889 if (match[pathlen] != '/')
890 return 0;
892 * Reject non-directories as partial pathnames, except
893 * when match is a submodule with a trailing slash and
894 * nothing else (to handle 'submod/' and 'submod'
895 * uniformly).
897 if (!S_ISDIR(entry->mode) &&
898 (!S_ISGITLINK(entry->mode) || matchlen > pathlen + 1))
899 return 0;
902 if (m == -1)
904 * we cheated and did not do strncmp(), so we do
905 * that here.
907 m = ps_strncmp(item, match, entry->path, pathlen);
910 * If common part matched earlier then it is a hit,
911 * because we rejected the case where path is not a
912 * leading directory and is shorter than match.
914 if (!m)
916 * match_entry does not check if the prefix part is
917 * matched case-sensitively. If the entry is a
918 * directory and part of prefix, it'll be rematched
919 * eventually by basecmp with special treatment for
920 * the prefix.
922 return 1;
924 return 0;
927 /* :(icase)-aware string compare */
928 static int basecmp(const struct pathspec_item *item,
929 const char *base, const char *match, int len)
931 if (item->magic & PATHSPEC_ICASE) {
932 int ret, n = len > item->prefix ? item->prefix : len;
933 ret = strncmp(base, match, n);
934 if (ret)
935 return ret;
936 base += n;
937 match += n;
938 len -= n;
940 return ps_strncmp(item, base, match, len);
943 static int match_dir_prefix(const struct pathspec_item *item,
944 const char *base,
945 const char *match, int matchlen)
947 if (basecmp(item, base, match, matchlen))
948 return 0;
951 * If the base is a subdirectory of a path which
952 * was specified, all of them are interesting.
954 if (!matchlen ||
955 base[matchlen] == '/' ||
956 match[matchlen - 1] == '/')
957 return 1;
959 /* Just a random prefix match */
960 return 0;
964 * Perform matching on the leading non-wildcard part of
965 * pathspec. item->nowildcard_len must be greater than zero. Return
966 * non-zero if base is matched.
968 static int match_wildcard_base(const struct pathspec_item *item,
969 const char *base, int baselen,
970 int *matched)
972 const char *match = item->match;
973 /* the wildcard part is not considered in this function */
974 int matchlen = item->nowildcard_len;
976 if (baselen) {
977 int dirlen;
979 * Return early if base is longer than the
980 * non-wildcard part but it does not match.
982 if (baselen >= matchlen) {
983 *matched = matchlen;
984 return !basecmp(item, base, match, matchlen);
987 dirlen = matchlen;
988 while (dirlen && match[dirlen - 1] != '/')
989 dirlen--;
992 * Return early if base is shorter than the
993 * non-wildcard part but it does not match. Note that
994 * base ends with '/' so we are sure it really matches
995 * directory
997 if (basecmp(item, base, match, baselen))
998 return 0;
999 *matched = baselen;
1000 } else
1001 *matched = 0;
1003 * we could have checked entry against the non-wildcard part
1004 * that is not in base and does similar never_interesting
1005 * optimization as in match_entry. For now just be happy with
1006 * base comparison.
1008 return entry_interesting;
1012 * Is a tree entry interesting given the pathspec we have?
1014 * Pre-condition: either baselen == base_offset (i.e. empty path)
1015 * or base[baselen-1] == '/' (i.e. with trailing slash).
1017 static enum interesting do_match(struct index_state *istate,
1018 const struct name_entry *entry,
1019 struct strbuf *base, int base_offset,
1020 const struct pathspec *ps,
1021 int exclude)
1023 int i;
1024 int pathlen, baselen = base->len - base_offset;
1025 enum interesting never_interesting = ps->has_wildcard ?
1026 entry_not_interesting : all_entries_not_interesting;
1028 GUARD_PATHSPEC(ps,
1029 PATHSPEC_FROMTOP |
1030 PATHSPEC_MAXDEPTH |
1031 PATHSPEC_LITERAL |
1032 PATHSPEC_GLOB |
1033 PATHSPEC_ICASE |
1034 PATHSPEC_EXCLUDE |
1035 PATHSPEC_ATTR);
1037 if (!ps->nr) {
1038 if (!ps->recursive ||
1039 !(ps->magic & PATHSPEC_MAXDEPTH) ||
1040 ps->max_depth == -1)
1041 return all_entries_interesting;
1042 return within_depth(base->buf + base_offset, baselen,
1043 !!S_ISDIR(entry->mode),
1044 ps->max_depth) ?
1045 entry_interesting : entry_not_interesting;
1048 pathlen = tree_entry_len(entry);
1050 for (i = ps->nr - 1; i >= 0; i--) {
1051 const struct pathspec_item *item = ps->items+i;
1052 const char *match = item->match;
1053 const char *base_str = base->buf + base_offset;
1054 int matchlen = item->len, matched = 0;
1056 if ((!exclude && item->magic & PATHSPEC_EXCLUDE) ||
1057 ( exclude && !(item->magic & PATHSPEC_EXCLUDE)))
1058 continue;
1060 if (baselen >= matchlen) {
1061 /* If it doesn't match, move along... */
1062 if (!match_dir_prefix(item, base_str, match, matchlen))
1063 goto match_wildcards;
1065 if (!ps->recursive ||
1066 !(ps->magic & PATHSPEC_MAXDEPTH) ||
1067 ps->max_depth == -1) {
1068 if (!item->attr_match_nr)
1069 return all_entries_interesting;
1070 else
1071 goto interesting;
1074 if (within_depth(base_str + matchlen + 1,
1075 baselen - matchlen - 1,
1076 !!S_ISDIR(entry->mode),
1077 ps->max_depth))
1078 goto interesting;
1079 else
1080 return entry_not_interesting;
1083 /* Either there must be no base, or the base must match. */
1084 if (baselen == 0 || !basecmp(item, base_str, match, baselen)) {
1085 if (match_entry(item, entry, pathlen,
1086 match + baselen, matchlen - baselen,
1087 &never_interesting))
1088 goto interesting;
1090 if (item->nowildcard_len < item->len) {
1091 if (!git_fnmatch(item, match + baselen, entry->path,
1092 item->nowildcard_len - baselen))
1093 goto interesting;
1096 * Match all directories. We'll try to
1097 * match files later on.
1099 if (ps->recursive && S_ISDIR(entry->mode))
1100 return entry_interesting;
1103 * When matching against submodules with
1104 * wildcard characters, ensure that the entry
1105 * at least matches up to the first wild
1106 * character. More accurate matching can then
1107 * be performed in the submodule itself.
1109 if (ps->recurse_submodules &&
1110 S_ISGITLINK(entry->mode) &&
1111 !ps_strncmp(item, match + baselen,
1112 entry->path,
1113 item->nowildcard_len - baselen))
1114 goto interesting;
1117 continue;
1120 match_wildcards:
1121 if (item->nowildcard_len == item->len)
1122 continue;
1124 if (item->nowildcard_len &&
1125 !match_wildcard_base(item, base_str, baselen, &matched))
1126 continue;
1129 * Concatenate base and entry->path into one and do
1130 * fnmatch() on it.
1132 * While we could avoid concatenation in certain cases
1133 * [1], which saves a memcpy and potentially a
1134 * realloc, it turns out not worth it. Measurement on
1135 * linux-2.6 does not show any clear improvements,
1136 * partly because of the nowildcard_len optimization
1137 * in git_fnmatch(). Avoid micro-optimizations here.
1139 * [1] if match_wildcard_base() says the base
1140 * directory is already matched, we only need to match
1141 * the rest, which is shorter so _in theory_ faster.
1144 strbuf_add(base, entry->path, pathlen);
1146 if (!git_fnmatch(item, match, base->buf + base_offset,
1147 item->nowildcard_len)) {
1148 strbuf_setlen(base, base_offset + baselen);
1149 goto interesting;
1153 * When matching against submodules with
1154 * wildcard characters, ensure that the entry
1155 * at least matches up to the first wild
1156 * character. More accurate matching can then
1157 * be performed in the submodule itself.
1159 if (ps->recurse_submodules && S_ISGITLINK(entry->mode) &&
1160 !ps_strncmp(item, match, base->buf + base_offset,
1161 item->nowildcard_len)) {
1162 strbuf_setlen(base, base_offset + baselen);
1163 goto interesting;
1166 strbuf_setlen(base, base_offset + baselen);
1169 * Match all directories. We'll try to match files
1170 * later on.
1171 * max_depth is ignored but we may consider support it
1172 * in future, see
1173 * https://lore.kernel.org/git/7vmxo5l2g4.fsf@alter.siamese.dyndns.org/
1175 if (ps->recursive && S_ISDIR(entry->mode))
1176 return entry_interesting;
1177 continue;
1178 interesting:
1179 if (item->attr_match_nr) {
1180 int ret;
1183 * Must not return all_entries_not_interesting
1184 * prematurely. We do not know if all entries do not
1185 * match some attributes with current attr API.
1187 never_interesting = entry_not_interesting;
1190 * Consider all directories interesting (because some
1191 * of those files inside may match some attributes
1192 * even though the parent dir does not)
1194 * FIXME: attributes _can_ match directories and we
1195 * can probably return all_entries_interesting or
1196 * all_entries_not_interesting here if matched.
1198 if (S_ISDIR(entry->mode))
1199 return entry_interesting;
1201 strbuf_add(base, entry->path, pathlen);
1202 ret = match_pathspec_attrs(istate, base->buf + base_offset,
1203 base->len - base_offset, item);
1204 strbuf_setlen(base, base_offset + baselen);
1205 if (!ret)
1206 continue;
1208 return entry_interesting;
1210 return never_interesting; /* No matches */
1214 * Is a tree entry interesting given the pathspec we have?
1216 * Pre-condition: either baselen == base_offset (i.e. empty path)
1217 * or base[baselen-1] == '/' (i.e. with trailing slash).
1219 enum interesting tree_entry_interesting(struct index_state *istate,
1220 const struct name_entry *entry,
1221 struct strbuf *base, int base_offset,
1222 const struct pathspec *ps)
1224 enum interesting positive, negative;
1225 positive = do_match(istate, entry, base, base_offset, ps, 0);
1228 * case | entry | positive | negative | result
1229 * -----+-------+----------+----------+-------
1230 * 1 | file | -1 | -1..2 | -1
1231 * 2 | file | 0 | -1..2 | 0
1232 * 3 | file | 1 | -1 | 1
1233 * 4 | file | 1 | 0 | 1
1234 * 5 | file | 1 | 1 | 0
1235 * 6 | file | 1 | 2 | 0
1236 * 7 | file | 2 | -1 | 2
1237 * 8 | file | 2 | 0 | 1
1238 * 9 | file | 2 | 1 | 0
1239 * 10 | file | 2 | 2 | -1
1240 * -----+-------+----------+----------+-------
1241 * 11 | dir | -1 | -1..2 | -1
1242 * 12 | dir | 0 | -1..2 | 0
1243 * 13 | dir | 1 | -1 | 1
1244 * 14 | dir | 1 | 0 | 1
1245 * 15 | dir | 1 | 1 | 1 (*)
1246 * 16 | dir | 1 | 2 | 0
1247 * 17 | dir | 2 | -1 | 2
1248 * 18 | dir | 2 | 0 | 1
1249 * 19 | dir | 2 | 1 | 1 (*)
1250 * 20 | dir | 2 | 2 | -1
1252 * (*) An exclude pattern interested in a directory does not
1253 * necessarily mean it will exclude all of the directory. In
1254 * wildcard case, it can't decide until looking at individual
1255 * files inside. So don't write such directories off yet.
1258 if (!(ps->magic & PATHSPEC_EXCLUDE) ||
1259 positive <= entry_not_interesting) /* #1, #2, #11, #12 */
1260 return positive;
1262 negative = do_match(istate, entry, base, base_offset, ps, 1);
1264 /* #8, #18 */
1265 if (positive == all_entries_interesting &&
1266 negative == entry_not_interesting)
1267 return entry_interesting;
1269 /* #3, #4, #7, #13, #14, #17 */
1270 if (negative <= entry_not_interesting)
1271 return positive;
1273 /* #15, #19 */
1274 if (S_ISDIR(entry->mode) &&
1275 positive >= entry_interesting &&
1276 negative == entry_interesting)
1277 return entry_interesting;
1279 if ((positive == entry_interesting &&
1280 negative >= entry_interesting) || /* #5, #6, #16 */
1281 (positive == all_entries_interesting &&
1282 negative == entry_interesting)) /* #9 */
1283 return entry_not_interesting;
1285 return all_entries_not_interesting; /* #10, #20 */