freshlybakedca.ke
Git fork
1#define USE_THE_REPOSITORY_VARIABLE
2
3#include "git-compat-util.h"
4#include "tree-walk.h"
5#include "dir.h"
6#include "gettext.h"
7#include "hex.h"
8#include "object-file.h"
9#include "odb.h"
10#include "trace2.h"
11#include "tree.h"
12#include "pathspec.h"
13#include "json-writer.h"
14#include "environment.h"
15
16static int decode_tree_entry(struct tree_desc *desc, const char *buf, unsigned long size, struct strbuf *err)
17{
18 const char *path;
19 unsigned int len;
20 uint16_t mode;
21 const unsigned hashsz = desc->algo->rawsz;
22
23 if (size < hashsz + 3 || buf[size - (hashsz + 1)]) {
24 strbuf_addstr(err, _("too-short tree object"));
25 return -1;
26 }
27
28 path = parse_mode(buf, &mode);
29 if (!path) {
30 strbuf_addstr(err, _("malformed mode in tree entry"));
31 return -1;
32 }
33 if (!*path) {
34 strbuf_addstr(err, _("empty filename in tree entry"));
35 return -1;
36 }
37 len = strlen(path) + 1;
38
39 /* Initialize the descriptor entry */
40 desc->entry.path = path;
41 desc->entry.mode = (desc->flags & TREE_DESC_RAW_MODES) ? mode : canon_mode(mode);
42 desc->entry.pathlen = len - 1;
43 oidread(&desc->entry.oid, (const unsigned char *)path + len,
44 desc->algo);
45
46 return 0;
47}
48
49static int init_tree_desc_internal(struct tree_desc *desc,
50 const struct object_id *oid,
51 const void *buffer, unsigned long size,
52 struct strbuf *err,
53 enum tree_desc_flags flags)
54{
55 desc->algo = (oid && oid->algo) ? &hash_algos[oid->algo] : the_hash_algo;
56 desc->buffer = buffer;
57 desc->size = size;
58 desc->flags = flags;
59 if (size)
60 return decode_tree_entry(desc, buffer, size, err);
61 return 0;
62}
63
64void init_tree_desc(struct tree_desc *desc, const struct object_id *tree_oid,
65 const void *buffer, unsigned long size)
66{
67 struct strbuf err = STRBUF_INIT;
68 if (init_tree_desc_internal(desc, tree_oid, buffer, size, &err, 0))
69 die("%s", err.buf);
70 strbuf_release(&err);
71}
72
73int init_tree_desc_gently(struct tree_desc *desc, const struct object_id *oid,
74 const void *buffer, unsigned long size,
75 enum tree_desc_flags flags)
76{
77 struct strbuf err = STRBUF_INIT;
78 int result = init_tree_desc_internal(desc, oid, buffer, size, &err, flags);
79 if (result)
80 error("%s", err.buf);
81 strbuf_release(&err);
82 return result;
83}
84
85void *fill_tree_descriptor(struct repository *r,
86 struct tree_desc *desc,
87 const struct object_id *oid)
88{
89 unsigned long size = 0;
90 void *buf = NULL;
91
92 if (oid) {
93 buf = odb_read_object_peeled(r->objects, oid, OBJ_TREE, &size, NULL);
94 if (!buf)
95 die(_("unable to read tree (%s)"), oid_to_hex(oid));
96 }
97 init_tree_desc(desc, oid, buf, size);
98 return buf;
99}
100
101static void entry_clear(struct name_entry *a)
102{
103 memset(a, 0, sizeof(*a));
104}
105
106static void entry_extract(struct tree_desc *t, struct name_entry *a)
107{
108 *a = t->entry;
109}
110
111static int update_tree_entry_internal(struct tree_desc *desc, struct strbuf *err)
112{
113 const void *buf = desc->buffer;
114 const unsigned char *end = (const unsigned char *)desc->entry.path + desc->entry.pathlen + 1 + desc->algo->rawsz;
115 unsigned long size = desc->size;
116 unsigned long len = end - (const unsigned char *)buf;
117
118 if (size < len)
119 die(_("too-short tree file"));
120 buf = end;
121 size -= len;
122 desc->buffer = buf;
123 desc->size = size;
124 if (size)
125 return decode_tree_entry(desc, buf, size, err);
126 return 0;
127}
128
129void update_tree_entry(struct tree_desc *desc)
130{
131 struct strbuf err = STRBUF_INIT;
132 if (update_tree_entry_internal(desc, &err))
133 die("%s", err.buf);
134 strbuf_release(&err);
135}
136
137int update_tree_entry_gently(struct tree_desc *desc)
138{
139 struct strbuf err = STRBUF_INIT;
140 if (update_tree_entry_internal(desc, &err)) {
141 error("%s", err.buf);
142 strbuf_release(&err);
143 /* Stop processing this tree after error */
144 desc->size = 0;
145 return -1;
146 }
147 strbuf_release(&err);
148 return 0;
149}
150
151int tree_entry(struct tree_desc *desc, struct name_entry *entry)
152{
153 if (!desc->size)
154 return 0;
155
156 *entry = desc->entry;
157 update_tree_entry(desc);
158 return 1;
159}
160
161int tree_entry_gently(struct tree_desc *desc, struct name_entry *entry)
162{
163 if (!desc->size)
164 return 0;
165
166 *entry = desc->entry;
167 if (update_tree_entry_gently(desc))
168 return 0;
169 return 1;
170}
171
172static int traverse_trees_atexit_registered;
173static int traverse_trees_count;
174static int traverse_trees_cur_depth;
175static int traverse_trees_max_depth;
176
177static void trace2_traverse_trees_statistics_atexit(void)
178{
179 struct json_writer jw = JSON_WRITER_INIT;
180
181 jw_object_begin(&jw, 0);
182 jw_object_intmax(&jw, "traverse_trees_count", traverse_trees_count);
183 jw_object_intmax(&jw, "traverse_trees_max_depth", traverse_trees_max_depth);
184 jw_end(&jw);
185
186 trace2_data_json("traverse_trees", the_repository, "statistics", &jw);
187
188 jw_release(&jw);
189}
190
191void setup_traverse_info(struct traverse_info *info, const char *base)
192{
193 size_t pathlen = strlen(base);
194 static struct traverse_info dummy;
195
196 memset(info, 0, sizeof(*info));
197 if (pathlen && base[pathlen-1] == '/')
198 pathlen--;
199 info->pathlen = pathlen ? pathlen + 1 : 0;
200 info->name = base;
201 info->namelen = pathlen;
202 if (pathlen)
203 info->prev = &dummy;
204
205 if (trace2_is_enabled() && !traverse_trees_atexit_registered) {
206 atexit(trace2_traverse_trees_statistics_atexit);
207 traverse_trees_atexit_registered = 1;
208 }
209}
210
211char *make_traverse_path(char *path, size_t pathlen,
212 const struct traverse_info *info,
213 const char *name, size_t namelen)
214{
215 /* Always points to the end of the name we're about to add */
216 size_t pos = st_add(info->pathlen, namelen);
217
218 if (pos >= pathlen)
219 BUG("too small buffer passed to make_traverse_path");
220
221 path[pos] = 0;
222 for (;;) {
223 if (pos < namelen)
224 BUG("traverse_info pathlen does not match strings");
225 pos -= namelen;
226 memcpy(path + pos, name, namelen);
227
228 if (!pos)
229 break;
230 path[--pos] = '/';
231
232 if (!info)
233 BUG("traverse_info ran out of list items");
234 name = info->name;
235 namelen = info->namelen;
236 info = info->prev;
237 }
238 return path;
239}
240
241void strbuf_make_traverse_path(struct strbuf *out,
242 const struct traverse_info *info,
243 const char *name, size_t namelen)
244{
245 size_t len = traverse_path_len(info, namelen);
246
247 strbuf_grow(out, len);
248 make_traverse_path(out->buf + out->len, out->alloc - out->len,
249 info, name, namelen);
250 strbuf_setlen(out, out->len + len);
251}
252
253struct tree_desc_skip {
254 struct tree_desc_skip *prev;
255 const void *ptr;
256};
257
258struct tree_desc_x {
259 struct tree_desc d;
260 struct tree_desc_skip *skip;
261};
262
263static int check_entry_match(const char *a, int a_len, const char *b, int b_len)
264{
265 /*
266 * The caller wants to pick *a* from a tree or nothing.
267 * We are looking at *b* in a tree.
268 *
269 * (0) If a and b are the same name, we are trivially happy.
270 *
271 * There are three possibilities where *a* could be hiding
272 * behind *b*.
273 *
274 * (1) *a* == "t", *b* == "ab" i.e. *b* sorts earlier than *a* no
275 * matter what.
276 * (2) *a* == "t", *b* == "t-2" and "t" is a subtree in the tree;
277 * (3) *a* == "t-2", *b* == "t" and "t-2" is a blob in the tree.
278 *
279 * Otherwise we know *a* won't appear in the tree without
280 * scanning further.
281 */
282
283 int cmp = name_compare(a, a_len, b, b_len);
284
285 /* Most common case first -- reading sync'd trees */
286 if (!cmp)
287 return cmp;
288
289 if (0 < cmp) {
290 /* a comes after b; it does not matter if it is case (3)
291 if (b_len < a_len && !memcmp(a, b, b_len) && a[b_len] < '/')
292 return 1;
293 */
294 return 1; /* keep looking */
295 }
296
297 /* b comes after a; are we looking at case (2)? */
298 if (a_len < b_len && !memcmp(a, b, a_len) && b[a_len] < '/')
299 return 1; /* keep looking */
300
301 return -1; /* a cannot appear in the tree */
302}
303
304/*
305 * From the extended tree_desc, extract the first name entry, while
306 * paying attention to the candidate "first" name. Most importantly,
307 * when looking for an entry, if there are entries that sorts earlier
308 * in the tree object representation than that name, skip them and
309 * process the named entry first. We will remember that we haven't
310 * processed the first entry yet, and in the later call skip the
311 * entry we processed early when update_extended_entry() is called.
312 *
313 * E.g. if the underlying tree object has these entries:
314 *
315 * blob "t-1"
316 * blob "t-2"
317 * tree "t"
318 * blob "t=1"
319 *
320 * and the "first" asks for "t", remember that we still need to
321 * process "t-1" and "t-2" but extract "t". After processing the
322 * entry "t" from this call, the caller will let us know by calling
323 * update_extended_entry() that we can remember "t" has been processed
324 * already.
325 */
326
327static void extended_entry_extract(struct tree_desc_x *t,
328 struct name_entry *a,
329 const char *first,
330 int first_len)
331{
332 const char *path;
333 int len;
334 struct tree_desc probe;
335 struct tree_desc_skip *skip;
336
337 /*
338 * Extract the first entry from the tree_desc, but skip the
339 * ones that we already returned in earlier rounds.
340 */
341 while (1) {
342 if (!t->d.size) {
343 entry_clear(a);
344 break; /* not found */
345 }
346 entry_extract(&t->d, a);
347 for (skip = t->skip; skip; skip = skip->prev)
348 if (a->path == skip->ptr)
349 break; /* found */
350 if (!skip)
351 break;
352 /* We have processed this entry already. */
353 update_tree_entry(&t->d);
354 }
355
356 if (!first || !a->path)
357 return;
358
359 /*
360 * The caller wants "first" from this tree, or nothing.
361 */
362 path = a->path;
363 len = tree_entry_len(a);
364 switch (check_entry_match(first, first_len, path, len)) {
365 case -1:
366 entry_clear(a);
367 case 0:
368 return;
369 default:
370 break;
371 }
372
373 /*
374 * We need to look-ahead -- we suspect that a subtree whose
375 * name is "first" may be hiding behind the current entry "path".
376 */
377 probe = t->d;
378 while (probe.size) {
379 entry_extract(&probe, a);
380 path = a->path;
381 len = tree_entry_len(a);
382 switch (check_entry_match(first, first_len, path, len)) {
383 case -1:
384 entry_clear(a);
385 case 0:
386 return;
387 default:
388 update_tree_entry(&probe);
389 break;
390 }
391 /* keep looking */
392 }
393 entry_clear(a);
394}
395
396static void update_extended_entry(struct tree_desc_x *t, struct name_entry *a)
397{
398 if (t->d.entry.path == a->path) {
399 update_tree_entry(&t->d);
400 } else {
401 /* we have returned this entry early */
402 struct tree_desc_skip *skip = xmalloc(sizeof(*skip));
403 skip->ptr = a->path;
404 skip->prev = t->skip;
405 t->skip = skip;
406 }
407}
408
409static void free_extended_entry(struct tree_desc_x *t)
410{
411 struct tree_desc_skip *p, *s;
412
413 for (s = t->skip; s; s = p) {
414 p = s->prev;
415 free(s);
416 }
417}
418
419static inline int prune_traversal(struct index_state *istate,
420 struct name_entry *e,
421 struct traverse_info *info,
422 struct strbuf *base,
423 int still_interesting)
424{
425 if (!info->pathspec || still_interesting == 2)
426 return 2;
427 if (still_interesting < 0)
428 return still_interesting;
429 return tree_entry_interesting(istate, e, base,
430 info->pathspec);
431}
432
433int traverse_trees(struct index_state *istate,
434 int n, struct tree_desc *t,
435 struct traverse_info *info)
436{
437 int ret = 0;
438 struct name_entry *entry;
439 int i;
440 struct tree_desc_x *tx;
441 struct strbuf base = STRBUF_INIT;
442 int interesting = 1;
443 char *traverse_path;
444
445 if (traverse_trees_cur_depth > max_allowed_tree_depth)
446 return error("exceeded maximum allowed tree depth");
447
448 traverse_trees_count++;
449 traverse_trees_cur_depth++;
450
451 if (traverse_trees_cur_depth > traverse_trees_max_depth)
452 traverse_trees_max_depth = traverse_trees_cur_depth;
453
454 ALLOC_ARRAY(entry, n);
455 ALLOC_ARRAY(tx, n);
456
457 for (i = 0; i < n; i++) {
458 tx[i].d = t[i];
459 tx[i].skip = NULL;
460 }
461
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);
469 }
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;
478
479 for (i = 0; i < n; i++) {
480 e = entry + i;
481 extended_entry_extract(tx + i, e, NULL, 0);
482 }
483
484 /*
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.
489 */
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;
499 }
500 if (name_compare(e->path, len, first, first_len) < 0) {
501 first = e->path;
502 first_len = len;
503 }
504 }
505
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);
516 }
517 }
518
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];
529 }
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 ret = trees_used;
539 if (!info->show_all_errors)
540 break;
541 }
542 mask &= trees_used;
543 }
544 for (i = 0; i < n; i++)
545 if (mask & (1ul << i))
546 update_extended_entry(tx + i, entry + i);
547 }
548 for (i = 0; i < n; i++)
549 free_extended_entry(tx + i);
550 free(tx);
551 free(entry);
552 free(traverse_path);
553 info->traverse_path = NULL;
554 strbuf_release(&base);
555
556 traverse_trees_cur_depth--;
557 return ret;
558}
559
560struct dir_state {
561 void *tree;
562 unsigned long size;
563 struct object_id oid;
564};
565
566static int find_tree_entry(struct repository *r, struct tree_desc *t,
567 const char *name, struct object_id *result,
568 unsigned short *mode)
569{
570 int namelen = strlen(name);
571 while (t->size) {
572 const char *entry;
573 struct object_id oid;
574 int entrylen, cmp;
575
576 oidcpy(&oid, tree_entry_extract(t, &entry, mode));
577 entrylen = tree_entry_len(&t->entry);
578 update_tree_entry(t);
579 if (entrylen > namelen)
580 continue;
581 cmp = memcmp(name, entry, entrylen);
582 if (cmp > 0)
583 continue;
584 if (cmp < 0)
585 break;
586 if (entrylen == namelen) {
587 oidcpy(result, &oid);
588 return 0;
589 }
590 if (name[entrylen] != '/')
591 continue;
592 if (!S_ISDIR(*mode))
593 break;
594 if (++entrylen == namelen) {
595 oidcpy(result, &oid);
596 return 0;
597 }
598 return get_tree_entry(r, &oid, name + entrylen, result, mode);
599 }
600 return -1;
601}
602
603int get_tree_entry(struct repository *r,
604 const struct object_id *tree_oid,
605 const char *name,
606 struct object_id *oid,
607 unsigned short *mode)
608{
609 int retval;
610 void *tree;
611 unsigned long size;
612 struct object_id root;
613
614 tree = odb_read_object_peeled(r->objects, tree_oid, OBJ_TREE, &size, &root);
615 if (!tree)
616 return -1;
617
618 if (name[0] == '\0') {
619 oidcpy(oid, &root);
620 free(tree);
621 return 0;
622 }
623
624 if (!size) {
625 retval = -1;
626 } else {
627 struct tree_desc t;
628 init_tree_desc(&t, tree_oid, tree, size);
629 retval = find_tree_entry(r, &t, name, oid, mode);
630 }
631 free(tree);
632 return retval;
633}
634
635/*
636 * This is Linux's built-in max for the number of symlinks to follow.
637 * That limit, of course, does not affect git, but it's a reasonable
638 * choice.
639 */
640#define GET_TREE_ENTRY_FOLLOW_SYMLINKS_MAX_LINKS 40
641
642/**
643 * Find a tree entry by following symlinks in tree_sha (which is
644 * assumed to be the root of the repository). In the event that a
645 * symlink points outside the repository (e.g. a link to /foo or a
646 * root-level link to ../foo), the portion of the link which is
647 * outside the repository will be returned in result_path, and *mode
648 * will be set to 0. It is assumed that result_path is uninitialized.
649 * If there are no symlinks, or the end result of the symlink chain
650 * points to an object inside the repository, result will be filled in
651 * with the sha1 of the found object, and *mode will hold the mode of
652 * the object.
653 *
654 * See the code for enum get_oid_result for a description of
655 * the return values.
656 */
657enum get_oid_result get_tree_entry_follow_symlinks(struct repository *r,
658 struct object_id *tree_oid, const char *name,
659 struct object_id *result, struct strbuf *result_path,
660 unsigned short *mode)
661{
662 int retval = MISSING_OBJECT;
663 struct dir_state *parents = NULL;
664 size_t parents_alloc = 0;
665 size_t i, parents_nr = 0;
666 struct object_id current_tree_oid;
667 struct strbuf namebuf = STRBUF_INIT;
668 struct tree_desc t;
669 int follows_remaining = GET_TREE_ENTRY_FOLLOW_SYMLINKS_MAX_LINKS;
670
671 init_tree_desc(&t, NULL, NULL, 0UL);
672 strbuf_addstr(&namebuf, name);
673 oidcpy(¤t_tree_oid, tree_oid);
674
675 while (1) {
676 int find_result;
677 char *first_slash;
678 char *remainder = NULL;
679
680 if (!t.buffer) {
681 void *tree;
682 struct object_id root;
683 unsigned long size;
684 tree = odb_read_object_peeled(r->objects, ¤t_tree_oid,
685 OBJ_TREE, &size, &root);
686 if (!tree)
687 goto done;
688
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++;
694
695 if (namebuf.buf[0] == '\0') {
696 oidcpy(result, &root);
697 retval = FOUND;
698 goto done;
699 }
700
701 if (!size)
702 goto done;
703
704 /* descend */
705 init_tree_desc(&t, ¤t_tree_oid, tree, size);
706 }
707
708 /* Handle symlinks to e.g. a//b by removing leading slashes */
709 while (namebuf.buf[0] == '/') {
710 strbuf_remove(&namebuf, 0, 1);
711 }
712
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;
717 }
718
719 if (!strcmp(namebuf.buf, "..")) {
720 struct dir_state *parent;
721 /*
722 * We could end up with .. in the namebuf if it
723 * appears in a symlink.
724 */
725
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;
734 }
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->oid, parent->tree, parent->size);
740 strbuf_remove(&namebuf, 0, remainder ? 3 : 2);
741 continue;
742 }
743
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;
749 }
750
751 /* Look up the first (or only) path component in the tree. */
752 find_result = find_tree_entry(r, &t, namebuf.buf,
753 ¤t_tree_oid, mode);
754 if (find_result) {
755 goto done;
756 }
757
758 if (S_ISDIR(*mode)) {
759 if (!remainder) {
760 oidcpy(result, ¤t_tree_oid);
761 retval = FOUND;
762 goto done;
763 }
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, ¤t_tree_oid);
771 retval = FOUND;
772 } else {
773 retval = NOT_DIR;
774 }
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;
783
784 if (follows_remaining-- == 0) {
785 /* Too many symlinks followed */
786 retval = SYMLINK_LOOP;
787 goto done;
788 }
789
790 /*
791 * At this point, we have followed at a least
792 * one symlink, so on error we need to report this.
793 */
794 retval = DANGLING_SYMLINK;
795
796 contents = odb_read_object(r->objects,
797 ¤t_tree_oid, &type,
798 &link_len);
799
800 if (!contents)
801 goto done;
802
803 if (contents[0] == '/') {
804 strbuf_addstr(result_path, contents);
805 free(contents);
806 *mode = 0;
807 retval = FOUND;
808 goto done;
809 }
810
811 if (remainder)
812 len = first_slash - namebuf.buf;
813 else
814 len = namebuf.len;
815
816 contents_start = contents;
817
818 parent = &parents[parents_nr - 1];
819 init_tree_desc(&t, &parent->oid, 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);
825 }
826 }
827done:
828 for (i = 0; i < parents_nr; i++)
829 free(parents[i].tree);
830 free(parents);
831
832 strbuf_release(&namebuf);
833 return retval;
834}
835
836static 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)
840{
841 int m = -1; /* signals that we haven't called strncmp() */
842
843 if (item->magic & PATHSPEC_ICASE)
844 /*
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.
852 */
853 *never_interesting = entry_not_interesting;
854 else if (*never_interesting != entry_not_interesting) {
855 /*
856 * We have not seen any match that sorts later
857 * than the current path.
858 */
859
860 /*
861 * Does match sort strictly earlier than path
862 * with their common parts?
863 */
864 m = strncmp(match, entry->path,
865 (matchlen < pathlen) ? matchlen : pathlen);
866 if (m < 0)
867 return 0;
868
869 /*
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.
881 */
882 *never_interesting = entry_not_interesting;
883 }
884
885 if (pathlen > matchlen)
886 return 0;
887
888 if (matchlen > pathlen) {
889 if (match[pathlen] != '/')
890 return 0;
891 /*
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).
896 */
897 if (!S_ISDIR(entry->mode) &&
898 (!S_ISGITLINK(entry->mode) || matchlen > pathlen + 1))
899 return 0;
900 }
901
902 if (m == -1)
903 /*
904 * we cheated and did not do strncmp(), so we do
905 * that here.
906 */
907 m = ps_strncmp(item, match, entry->path, pathlen);
908
909 /*
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.
913 */
914 if (!m)
915 /*
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.
921 */
922 return 1;
923
924 return 0;
925}
926
927/* :(icase)-aware string compare */
928static int basecmp(const struct pathspec_item *item,
929 const char *base, const char *match, int len)
930{
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;
939 }
940 return ps_strncmp(item, base, match, len);
941}
942
943static int match_dir_prefix(const struct pathspec_item *item,
944 const char *base,
945 const char *match, int matchlen)
946{
947 if (basecmp(item, base, match, matchlen))
948 return 0;
949
950 /*
951 * If the base is a subdirectory of a path which
952 * was specified, all of them are interesting.
953 */
954 if (!matchlen ||
955 base[matchlen] == '/' ||
956 match[matchlen - 1] == '/')
957 return 1;
958
959 /* Just a random prefix match */
960 return 0;
961}
962
963/*
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.
967 */
968static int match_wildcard_base(const struct pathspec_item *item,
969 const char *base, int baselen,
970 int *matched)
971{
972 const char *match = item->match;
973 /* the wildcard part is not considered in this function */
974 int matchlen = item->nowildcard_len;
975
976 if (baselen) {
977 int dirlen;
978 /*
979 * Return early if base is longer than the
980 * non-wildcard part but it does not match.
981 */
982 if (baselen >= matchlen) {
983 *matched = matchlen;
984 return !basecmp(item, base, match, matchlen);
985 }
986
987 dirlen = matchlen;
988 while (dirlen && match[dirlen - 1] != '/')
989 dirlen--;
990
991 /*
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
996 */
997 if (basecmp(item, base, match, baselen))
998 return 0;
999 *matched = baselen;
1000 } else
1001 *matched = 0;
1002 /*
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.
1007 */
1008 return entry_interesting;
1009}
1010
1011/*
1012 * Is a tree entry interesting given the pathspec we have?
1013 *
1014 * Pre-condition: either baselen == 0 (i.e. empty path)
1015 * or base[baselen-1] == '/' (i.e. with trailing slash).
1016 */
1017static enum interesting do_match(struct index_state *istate,
1018 const struct name_entry *entry,
1019 struct strbuf *base,
1020 const struct pathspec *ps,
1021 int exclude)
1022{
1023 int i;
1024 int pathlen, baselen = base->len;
1025 enum interesting never_interesting = ps->has_wildcard ?
1026 entry_not_interesting : all_entries_not_interesting;
1027
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);
1036
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, baselen,
1043 !!S_ISDIR(entry->mode),
1044 ps->max_depth) ?
1045 entry_interesting : entry_not_interesting;
1046 }
1047
1048 pathlen = tree_entry_len(entry);
1049
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;
1054 int matchlen = item->len, matched = 0;
1055
1056 if ((!exclude && item->magic & PATHSPEC_EXCLUDE) ||
1057 ( exclude && !(item->magic & PATHSPEC_EXCLUDE)))
1058 continue;
1059
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;
1064
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;
1072 }
1073
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;
1081 }
1082
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;
1089
1090 if (item->nowildcard_len < item->len) {
1091 if (!git_fnmatch(item, match + baselen, entry->path,
1092 item->nowildcard_len - baselen))
1093 goto interesting;
1094
1095 /*
1096 * Match all directories. We'll try to
1097 * match files later on.
1098 */
1099 if (ps->recursive && S_ISDIR(entry->mode))
1100 return entry_interesting;
1101
1102 /*
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.
1108 */
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;
1115 }
1116
1117 continue;
1118 }
1119
1120match_wildcards:
1121 if (item->nowildcard_len == item->len)
1122 continue;
1123
1124 if (item->nowildcard_len &&
1125 !match_wildcard_base(item, base_str, baselen, &matched))
1126 continue;
1127
1128 /*
1129 * Concatenate base and entry->path into one and do
1130 * fnmatch() on it.
1131 *
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.
1138 *
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.
1142 */
1143
1144 strbuf_add(base, entry->path, pathlen);
1145
1146 if (!git_fnmatch(item, match, base->buf,
1147 item->nowildcard_len)) {
1148 strbuf_setlen(base, baselen);
1149 goto interesting;
1150 }
1151
1152 /*
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.
1158 */
1159 if (ps->recurse_submodules && S_ISGITLINK(entry->mode) &&
1160 !ps_strncmp(item, match, base->buf,
1161 item->nowildcard_len)) {
1162 strbuf_setlen(base, baselen);
1163 goto interesting;
1164 }
1165
1166 strbuf_setlen(base, baselen);
1167
1168 /*
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/
1174 */
1175 if (ps->recursive && S_ISDIR(entry->mode))
1176 return entry_interesting;
1177 continue;
1178interesting:
1179 if (item->attr_match_nr) {
1180 int ret;
1181
1182 /*
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.
1186 */
1187 never_interesting = entry_not_interesting;
1188
1189 /*
1190 * Consider all directories interesting (because some
1191 * of those files inside may match some attributes
1192 * even though the parent dir does not)
1193 *
1194 * FIXME: attributes _can_ match directories and we
1195 * can probably return all_entries_interesting or
1196 * all_entries_not_interesting here if matched.
1197 */
1198 if (S_ISDIR(entry->mode))
1199 return entry_interesting;
1200
1201 strbuf_add(base, entry->path, pathlen);
1202 ret = match_pathspec_attrs(istate, base->buf,
1203 base->len, item);
1204 strbuf_setlen(base, baselen);
1205 if (!ret)
1206 continue;
1207 }
1208 return entry_interesting;
1209 }
1210 return never_interesting; /* No matches */
1211}
1212
1213/*
1214 * Is a tree entry interesting given the pathspec we have?
1215 *
1216 * Pre-condition: either baselen == 0 (i.e. empty path)
1217 * or base[baselen-1] == '/' (i.e. with trailing slash).
1218 */
1219enum interesting tree_entry_interesting(struct index_state *istate,
1220 const struct name_entry *entry,
1221 struct strbuf *base,
1222 const struct pathspec *ps)
1223{
1224 enum interesting positive, negative;
1225 positive = do_match(istate, entry, base, ps, 0);
1226
1227 /*
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
1251 *
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.
1256 */
1257
1258 if (!(ps->magic & PATHSPEC_EXCLUDE) ||
1259 positive <= entry_not_interesting) /* #1, #2, #11, #12 */
1260 return positive;
1261
1262 negative = do_match(istate, entry, base, ps, 1);
1263
1264 /* #8, #18 */
1265 if (positive == all_entries_interesting &&
1266 negative == entry_not_interesting)
1267 return entry_interesting;
1268
1269 /* #3, #4, #7, #13, #14, #17 */
1270 if (negative <= entry_not_interesting)
1271 return positive;
1272
1273 /* #15, #19 */
1274 if (S_ISDIR(entry->mode) &&
1275 positive >= entry_interesting &&
1276 negative == entry_interesting)
1277 return entry_interesting;
1278
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;
1284
1285 return all_entries_not_interesting; /* #10, #20 */
1286}