git

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 "object-store-ll.h"
10
#include "trace2.h"
11
#include "tree.h"
12
#include "pathspec.h"
13
#include "json-writer.h"
14
#include "environment.h"
15

16
static 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

49
static 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

64
void 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

73
int 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

85
void *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 = read_object_with_reference(r, 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

101
static void entry_clear(struct name_entry *a)
102
{
103
	memset(a, 0, sizeof(*a));
104
}
105

106
static void entry_extract(struct tree_desc *t, struct name_entry *a)
107
{
108
	*a = t->entry;
109
}
110

111
static 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

129
void 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

137
int 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

151
int 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

161
int 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

172
static int traverse_trees_atexit_registered;
173
static int traverse_trees_count;
174
static int traverse_trees_cur_depth;
175
static int traverse_trees_max_depth;
176

177
static 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

191
void 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

211
char *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

241
void 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

253
struct tree_desc_skip {
254
	struct tree_desc_skip *prev;
255
	const void *ptr;
256
};
257

258
struct tree_desc_x {
259
	struct tree_desc d;
260
	struct tree_desc_skip *skip;
261
};
262

263
static 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

327
static 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

396
static 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

409
static 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

419
static 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

433
int 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

560
struct dir_state {
561
	void *tree;
562
	unsigned long size;
563
	struct object_id oid;
564
};
565

566
static 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

603
int 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 = read_object_with_reference(r, 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
 */
657
enum 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(&current_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 = read_object_with_reference(r,
685
							  &current_tree_oid,
686
							  OBJ_TREE, &size,
687
							  &root);
688
			if (!tree)
689
				goto done;
690

691
			ALLOC_GROW(parents, parents_nr + 1, parents_alloc);
692
			parents[parents_nr].tree = tree;
693
			parents[parents_nr].size = size;
694
			oidcpy(&parents[parents_nr].oid, &root);
695
			parents_nr++;
696

697
			if (namebuf.buf[0] == '\0') {
698
				oidcpy(result, &root);
699
				retval = FOUND;
700
				goto done;
701
			}
702

703
			if (!size)
704
				goto done;
705

706
			/* descend */
707
			init_tree_desc(&t, &current_tree_oid, tree, size);
708
		}
709

710
		/* Handle symlinks to e.g. a//b by removing leading slashes */
711
		while (namebuf.buf[0] == '/') {
712
			strbuf_remove(&namebuf, 0, 1);
713
		}
714

715
		/* Split namebuf into a first component and a remainder */
716
		if ((first_slash = strchr(namebuf.buf, '/'))) {
717
			*first_slash = 0;
718
			remainder = first_slash + 1;
719
		}
720

721
		if (!strcmp(namebuf.buf, "..")) {
722
			struct dir_state *parent;
723
			/*
724
			 * We could end up with .. in the namebuf if it
725
			 * appears in a symlink.
726
			 */
727

728
			if (parents_nr == 1) {
729
				if (remainder)
730
					*first_slash = '/';
731
				strbuf_add(result_path, namebuf.buf,
732
					   namebuf.len);
733
				*mode = 0;
734
				retval = FOUND;
735
				goto done;
736
			}
737
			parent = &parents[parents_nr - 1];
738
			free(parent->tree);
739
			parents_nr--;
740
			parent = &parents[parents_nr - 1];
741
			init_tree_desc(&t, &parent->oid, parent->tree, parent->size);
742
			strbuf_remove(&namebuf, 0, remainder ? 3 : 2);
743
			continue;
744
		}
745

746
		/* We could end up here via a symlink to dir/.. */
747
		if (namebuf.buf[0] == '\0') {
748
			oidcpy(result, &parents[parents_nr - 1].oid);
749
			retval = FOUND;
750
			goto done;
751
		}
752

753
		/* Look up the first (or only) path component in the tree. */
754
		find_result = find_tree_entry(r, &t, namebuf.buf,
755
					      &current_tree_oid, mode);
756
		if (find_result) {
757
			goto done;
758
		}
759

760
		if (S_ISDIR(*mode)) {
761
			if (!remainder) {
762
				oidcpy(result, &current_tree_oid);
763
				retval = FOUND;
764
				goto done;
765
			}
766
			/* Descend the tree */
767
			t.buffer = NULL;
768
			strbuf_remove(&namebuf, 0,
769
				      1 + first_slash - namebuf.buf);
770
		} else if (S_ISREG(*mode)) {
771
			if (!remainder) {
772
				oidcpy(result, &current_tree_oid);
773
				retval = FOUND;
774
			} else {
775
				retval = NOT_DIR;
776
			}
777
			goto done;
778
		} else if (S_ISLNK(*mode)) {
779
			/* Follow a symlink */
780
			unsigned long link_len;
781
			size_t len;
782
			char *contents, *contents_start;
783
			struct dir_state *parent;
784
			enum object_type type;
785

786
			if (follows_remaining-- == 0) {
787
				/* Too many symlinks followed */
788
				retval = SYMLINK_LOOP;
789
				goto done;
790
			}
791

792
			/*
793
			 * At this point, we have followed at a least
794
			 * one symlink, so on error we need to report this.
795
			 */
796
			retval = DANGLING_SYMLINK;
797

798
			contents = repo_read_object_file(r,
799
						    &current_tree_oid, &type,
800
						    &link_len);
801

802
			if (!contents)
803
				goto done;
804

805
			if (contents[0] == '/') {
806
				strbuf_addstr(result_path, contents);
807
				free(contents);
808
				*mode = 0;
809
				retval = FOUND;
810
				goto done;
811
			}
812

813
			if (remainder)
814
				len = first_slash - namebuf.buf;
815
			else
816
				len = namebuf.len;
817

818
			contents_start = contents;
819

820
			parent = &parents[parents_nr - 1];
821
			init_tree_desc(&t, &parent->oid, parent->tree, parent->size);
822
			strbuf_splice(&namebuf, 0, len,
823
				      contents_start, link_len);
824
			if (remainder)
825
				namebuf.buf[link_len] = '/';
826
			free(contents);
827
		}
828
	}
829
done:
830
	for (i = 0; i < parents_nr; i++)
831
		free(parents[i].tree);
832
	free(parents);
833

834
	strbuf_release(&namebuf);
835
	return retval;
836
}
837

838
static int match_entry(const struct pathspec_item *item,
839
		       const struct name_entry *entry, int pathlen,
840
		       const char *match, int matchlen,
841
		       enum interesting *never_interesting)
842
{
843
	int m = -1; /* signals that we haven't called strncmp() */
844

845
	if (item->magic & PATHSPEC_ICASE)
846
		/*
847
		 * "Never interesting" trick requires exact
848
		 * matching. We could do something clever with inexact
849
		 * matching, but it's trickier (and not to forget that
850
		 * strcasecmp is locale-dependent, at least in
851
		 * glibc). Just disable it for now. It can't be worse
852
		 * than the wildcard's codepath of '[Tt][Hi][Is][Ss]'
853
		 * pattern.
854
		 */
855
		*never_interesting = entry_not_interesting;
856
	else if (*never_interesting != entry_not_interesting) {
857
		/*
858
		 * We have not seen any match that sorts later
859
		 * than the current path.
860
		 */
861

862
		/*
863
		 * Does match sort strictly earlier than path
864
		 * with their common parts?
865
		 */
866
		m = strncmp(match, entry->path,
867
			    (matchlen < pathlen) ? matchlen : pathlen);
868
		if (m < 0)
869
			return 0;
870

871
		/*
872
		 * If we come here even once, that means there is at
873
		 * least one pathspec that would sort equal to or
874
		 * later than the path we are currently looking at.
875
		 * In other words, if we have never reached this point
876
		 * after iterating all pathspecs, it means all
877
		 * pathspecs are either outside of base, or inside the
878
		 * base but sorts strictly earlier than the current
879
		 * one.  In either case, they will never match the
880
		 * subsequent entries.  In such a case, we initialized
881
		 * the variable to -1 and that is what will be
882
		 * returned, allowing the caller to terminate early.
883
		 */
884
		*never_interesting = entry_not_interesting;
885
	}
886

887
	if (pathlen > matchlen)
888
		return 0;
889

890
	if (matchlen > pathlen) {
891
		if (match[pathlen] != '/')
892
			return 0;
893
		/*
894
		 * Reject non-directories as partial pathnames, except
895
		 * when match is a submodule with a trailing slash and
896
		 * nothing else (to handle 'submod/' and 'submod'
897
		 * uniformly).
898
		 */
899
		if (!S_ISDIR(entry->mode) &&
900
		    (!S_ISGITLINK(entry->mode) || matchlen > pathlen + 1))
901
			return 0;
902
	}
903

904
	if (m == -1)
905
		/*
906
		 * we cheated and did not do strncmp(), so we do
907
		 * that here.
908
		 */
909
		m = ps_strncmp(item, match, entry->path, pathlen);
910

911
	/*
912
	 * If common part matched earlier then it is a hit,
913
	 * because we rejected the case where path is not a
914
	 * leading directory and is shorter than match.
915
	 */
916
	if (!m)
917
		/*
918
		 * match_entry does not check if the prefix part is
919
		 * matched case-sensitively. If the entry is a
920
		 * directory and part of prefix, it'll be rematched
921
		 * eventually by basecmp with special treatment for
922
		 * the prefix.
923
		 */
924
		return 1;
925

926
	return 0;
927
}
928

929
/* :(icase)-aware string compare */
930
static int basecmp(const struct pathspec_item *item,
931
		   const char *base, const char *match, int len)
932
{
933
	if (item->magic & PATHSPEC_ICASE) {
934
		int ret, n = len > item->prefix ? item->prefix : len;
935
		ret = strncmp(base, match, n);
936
		if (ret)
937
			return ret;
938
		base += n;
939
		match += n;
940
		len -= n;
941
	}
942
	return ps_strncmp(item, base, match, len);
943
}
944

945
static int match_dir_prefix(const struct pathspec_item *item,
946
			    const char *base,
947
			    const char *match, int matchlen)
948
{
949
	if (basecmp(item, base, match, matchlen))
950
		return 0;
951

952
	/*
953
	 * If the base is a subdirectory of a path which
954
	 * was specified, all of them are interesting.
955
	 */
956
	if (!matchlen ||
957
	    base[matchlen] == '/' ||
958
	    match[matchlen - 1] == '/')
959
		return 1;
960

961
	/* Just a random prefix match */
962
	return 0;
963
}
964

965
/*
966
 * Perform matching on the leading non-wildcard part of
967
 * pathspec. item->nowildcard_len must be greater than zero. Return
968
 * non-zero if base is matched.
969
 */
970
static int match_wildcard_base(const struct pathspec_item *item,
971
			       const char *base, int baselen,
972
			       int *matched)
973
{
974
	const char *match = item->match;
975
	/* the wildcard part is not considered in this function */
976
	int matchlen = item->nowildcard_len;
977

978
	if (baselen) {
979
		int dirlen;
980
		/*
981
		 * Return early if base is longer than the
982
		 * non-wildcard part but it does not match.
983
		 */
984
		if (baselen >= matchlen) {
985
			*matched = matchlen;
986
			return !basecmp(item, base, match, matchlen);
987
		}
988

989
		dirlen = matchlen;
990
		while (dirlen && match[dirlen - 1] != '/')
991
			dirlen--;
992

993
		/*
994
		 * Return early if base is shorter than the
995
		 * non-wildcard part but it does not match. Note that
996
		 * base ends with '/' so we are sure it really matches
997
		 * directory
998
		 */
999
		if (basecmp(item, base, match, baselen))
1000
			return 0;
1001
		*matched = baselen;
1002
	} else
1003
		*matched = 0;
1004
	/*
1005
	 * we could have checked entry against the non-wildcard part
1006
	 * that is not in base and does similar never_interesting
1007
	 * optimization as in match_entry. For now just be happy with
1008
	 * base comparison.
1009
	 */
1010
	return entry_interesting;
1011
}
1012

1013
/*
1014
 * Is a tree entry interesting given the pathspec we have?
1015
 *
1016
 * Pre-condition: either baselen == 0 (i.e. empty path)
1017
 * or base[baselen-1] == '/' (i.e. with trailing slash).
1018
 */
1019
static enum interesting do_match(struct index_state *istate,
1020
				 const struct name_entry *entry,
1021
				 struct strbuf *base,
1022
				 const struct pathspec *ps,
1023
				 int exclude)
1024
{
1025
	int i;
1026
	int pathlen, baselen = base->len;
1027
	enum interesting never_interesting = ps->has_wildcard ?
1028
		entry_not_interesting : all_entries_not_interesting;
1029

1030
	GUARD_PATHSPEC(ps,
1031
		       PATHSPEC_FROMTOP |
1032
		       PATHSPEC_MAXDEPTH |
1033
		       PATHSPEC_LITERAL |
1034
		       PATHSPEC_GLOB |
1035
		       PATHSPEC_ICASE |
1036
		       PATHSPEC_EXCLUDE |
1037
		       PATHSPEC_ATTR);
1038

1039
	if (!ps->nr) {
1040
		if (!ps->recursive ||
1041
		    !(ps->magic & PATHSPEC_MAXDEPTH) ||
1042
		    ps->max_depth == -1)
1043
			return all_entries_interesting;
1044
		return within_depth(base->buf, baselen,
1045
				    !!S_ISDIR(entry->mode),
1046
				    ps->max_depth) ?
1047
			entry_interesting : entry_not_interesting;
1048
	}
1049

1050
	pathlen = tree_entry_len(entry);
1051

1052
	for (i = ps->nr - 1; i >= 0; i--) {
1053
		const struct pathspec_item *item = ps->items+i;
1054
		const char *match = item->match;
1055
		const char *base_str = base->buf;
1056
		int matchlen = item->len, matched = 0;
1057

1058
		if ((!exclude &&   item->magic & PATHSPEC_EXCLUDE) ||
1059
		    ( exclude && !(item->magic & PATHSPEC_EXCLUDE)))
1060
			continue;
1061

1062
		if (baselen >= matchlen) {
1063
			/* If it doesn't match, move along... */
1064
			if (!match_dir_prefix(item, base_str, match, matchlen))
1065
				goto match_wildcards;
1066

1067
			if (!ps->recursive ||
1068
			    !(ps->magic & PATHSPEC_MAXDEPTH) ||
1069
			    ps->max_depth == -1) {
1070
				if (!item->attr_match_nr)
1071
					return all_entries_interesting;
1072
				else
1073
					goto interesting;
1074
			}
1075

1076
			if (within_depth(base_str + matchlen + 1,
1077
					 baselen - matchlen - 1,
1078
					 !!S_ISDIR(entry->mode),
1079
					 ps->max_depth))
1080
				goto interesting;
1081
			else
1082
				return entry_not_interesting;
1083
		}
1084

1085
		/* Either there must be no base, or the base must match. */
1086
		if (baselen == 0 || !basecmp(item, base_str, match, baselen)) {
1087
			if (match_entry(item, entry, pathlen,
1088
					match + baselen, matchlen - baselen,
1089
					&never_interesting))
1090
				goto interesting;
1091

1092
			if (item->nowildcard_len < item->len) {
1093
				if (!git_fnmatch(item, match + baselen, entry->path,
1094
						 item->nowildcard_len - baselen))
1095
					goto interesting;
1096

1097
				/*
1098
				 * Match all directories. We'll try to
1099
				 * match files later on.
1100
				 */
1101
				if (ps->recursive && S_ISDIR(entry->mode))
1102
					return entry_interesting;
1103

1104
				/*
1105
				 * When matching against submodules with
1106
				 * wildcard characters, ensure that the entry
1107
				 * at least matches up to the first wild
1108
				 * character.  More accurate matching can then
1109
				 * be performed in the submodule itself.
1110
				 */
1111
				if (ps->recurse_submodules &&
1112
				    S_ISGITLINK(entry->mode) &&
1113
				    !ps_strncmp(item, match + baselen,
1114
						entry->path,
1115
						item->nowildcard_len - baselen))
1116
					goto interesting;
1117
			}
1118

1119
			continue;
1120
		}
1121

1122
match_wildcards:
1123
		if (item->nowildcard_len == item->len)
1124
			continue;
1125

1126
		if (item->nowildcard_len &&
1127
		    !match_wildcard_base(item, base_str, baselen, &matched))
1128
			continue;
1129

1130
		/*
1131
		 * Concatenate base and entry->path into one and do
1132
		 * fnmatch() on it.
1133
		 *
1134
		 * While we could avoid concatenation in certain cases
1135
		 * [1], which saves a memcpy and potentially a
1136
		 * realloc, it turns out not worth it. Measurement on
1137
		 * linux-2.6 does not show any clear improvements,
1138
		 * partly because of the nowildcard_len optimization
1139
		 * in git_fnmatch(). Avoid micro-optimizations here.
1140
		 *
1141
		 * [1] if match_wildcard_base() says the base
1142
		 * directory is already matched, we only need to match
1143
		 * the rest, which is shorter so _in theory_ faster.
1144
		 */
1145

1146
		strbuf_add(base, entry->path, pathlen);
1147

1148
		if (!git_fnmatch(item, match, base->buf,
1149
				 item->nowildcard_len)) {
1150
			strbuf_setlen(base, baselen);
1151
			goto interesting;
1152
		}
1153

1154
		/*
1155
		 * When matching against submodules with
1156
		 * wildcard characters, ensure that the entry
1157
		 * at least matches up to the first wild
1158
		 * character.  More accurate matching can then
1159
		 * be performed in the submodule itself.
1160
		 */
1161
		if (ps->recurse_submodules && S_ISGITLINK(entry->mode) &&
1162
		    !ps_strncmp(item, match, base->buf,
1163
				item->nowildcard_len)) {
1164
			strbuf_setlen(base, baselen);
1165
			goto interesting;
1166
		}
1167

1168
		strbuf_setlen(base, baselen);
1169

1170
		/*
1171
		 * Match all directories. We'll try to match files
1172
		 * later on.
1173
		 * max_depth is ignored but we may consider support it
1174
		 * in future, see
1175
		 * https://lore.kernel.org/git/7vmxo5l2g4.fsf@alter.siamese.dyndns.org/
1176
		 */
1177
		if (ps->recursive && S_ISDIR(entry->mode))
1178
			return entry_interesting;
1179
		continue;
1180
interesting:
1181
		if (item->attr_match_nr) {
1182
			int ret;
1183

1184
			/*
1185
			 * Must not return all_entries_not_interesting
1186
			 * prematurely. We do not know if all entries do not
1187
			 * match some attributes with current attr API.
1188
			 */
1189
			never_interesting = entry_not_interesting;
1190

1191
			/*
1192
			 * Consider all directories interesting (because some
1193
			 * of those files inside may match some attributes
1194
			 * even though the parent dir does not)
1195
			 *
1196
			 * FIXME: attributes _can_ match directories and we
1197
			 * can probably return all_entries_interesting or
1198
			 * all_entries_not_interesting here if matched.
1199
			 */
1200
			if (S_ISDIR(entry->mode))
1201
				return entry_interesting;
1202

1203
			strbuf_add(base, entry->path, pathlen);
1204
			ret = match_pathspec_attrs(istate, base->buf,
1205
						   base->len, item);
1206
			strbuf_setlen(base, baselen);
1207
			if (!ret)
1208
				continue;
1209
		}
1210
		return entry_interesting;
1211
	}
1212
	return never_interesting; /* No matches */
1213
}
1214

1215
/*
1216
 * Is a tree entry interesting given the pathspec we have?
1217
 *
1218
 * Pre-condition: either baselen == 0 (i.e. empty path)
1219
 * or base[baselen-1] == '/' (i.e. with trailing slash).
1220
 */
1221
enum interesting tree_entry_interesting(struct index_state *istate,
1222
					const struct name_entry *entry,
1223
					struct strbuf *base,
1224
					const struct pathspec *ps)
1225
{
1226
	enum interesting positive, negative;
1227
	positive = do_match(istate, entry, base, ps, 0);
1228

1229
	/*
1230
	 * case | entry | positive | negative | result
1231
	 * -----+-------+----------+----------+-------
1232
	 *   1  |  file |   -1     |  -1..2   |  -1
1233
	 *   2  |  file |    0     |  -1..2   |   0
1234
	 *   3  |  file |    1     |   -1     |   1
1235
	 *   4  |  file |    1     |    0     |   1
1236
	 *   5  |  file |    1     |    1     |   0
1237
	 *   6  |  file |    1     |    2     |   0
1238
	 *   7  |  file |    2     |   -1     |   2
1239
	 *   8  |  file |    2     |    0     |   1
1240
	 *   9  |  file |    2     |    1     |   0
1241
	 *  10  |  file |    2     |    2     |  -1
1242
	 * -----+-------+----------+----------+-------
1243
	 *  11  |  dir  |   -1     |  -1..2   |  -1
1244
	 *  12  |  dir  |    0     |  -1..2   |   0
1245
	 *  13  |  dir  |    1     |   -1     |   1
1246
	 *  14  |  dir  |    1     |    0     |   1
1247
	 *  15  |  dir  |    1     |    1     |   1 (*)
1248
	 *  16  |  dir  |    1     |    2     |   0
1249
	 *  17  |  dir  |    2     |   -1     |   2
1250
	 *  18  |  dir  |    2     |    0     |   1
1251
	 *  19  |  dir  |    2     |    1     |   1 (*)
1252
	 *  20  |  dir  |    2     |    2     |  -1
1253
	 *
1254
	 * (*) An exclude pattern interested in a directory does not
1255
	 * necessarily mean it will exclude all of the directory. In
1256
	 * wildcard case, it can't decide until looking at individual
1257
	 * files inside. So don't write such directories off yet.
1258
	 */
1259

1260
	if (!(ps->magic & PATHSPEC_EXCLUDE) ||
1261
	    positive <= entry_not_interesting) /* #1, #2, #11, #12 */
1262
		return positive;
1263

1264
	negative = do_match(istate, entry, base, ps, 1);
1265

1266
	/* #8, #18 */
1267
	if (positive == all_entries_interesting &&
1268
	    negative == entry_not_interesting)
1269
		return entry_interesting;
1270

1271
	/* #3, #4, #7, #13, #14, #17 */
1272
	if (negative <= entry_not_interesting)
1273
		return positive;
1274

1275
	/* #15, #19 */
1276
	if (S_ISDIR(entry->mode) &&
1277
	    positive >= entry_interesting &&
1278
	    negative == entry_interesting)
1279
		return entry_interesting;
1280

1281
	if ((positive == entry_interesting &&
1282
	     negative >= entry_interesting) || /* #5, #6, #16 */
1283
	    (positive == all_entries_interesting &&
1284
	     negative == entry_interesting)) /* #9 */
1285
		return entry_not_interesting;
1286

1287
	return all_entries_not_interesting; /* #10, #20 */
1288
}
1289