iterator.c 58.7 KB
Newer Older
1
/*
Edward Thomson committed
2
 * Copyright (C) the libgit2 contributors. All rights reserved.
3 4 5 6 7 8
 *
 * This file is part of libgit2, distributed under the GNU GPL v2 with
 * a Linking Exception. For full terms see the included COPYING file.
 */

#include "iterator.h"
9

10
#include "tree.h"
11
#include "index.h"
12

13 14 15
#define GIT_ITERATOR_FIRST_ACCESS   (1 << 15)
#define GIT_ITERATOR_HONOR_IGNORES  (1 << 16)
#define GIT_ITERATOR_IGNORE_DOT_GIT (1 << 17)
16

17 18 19 20 21 22
#define iterator__flag(I,F) ((((git_iterator *)(I))->flags & GIT_ITERATOR_ ## F) != 0)
#define iterator__ignore_case(I)       iterator__flag(I,IGNORE_CASE)
#define iterator__include_trees(I)     iterator__flag(I,INCLUDE_TREES)
#define iterator__dont_autoexpand(I)   iterator__flag(I,DONT_AUTOEXPAND)
#define iterator__do_autoexpand(I)    !iterator__flag(I,DONT_AUTOEXPAND)
#define iterator__include_conflicts(I) iterator__flag(I,INCLUDE_CONFLICTS)
23
#define iterator__has_been_accessed(I) iterator__flag(I,FIRST_ACCESS)
24 25
#define iterator__honor_ignores(I)     iterator__flag(I,HONOR_IGNORES)
#define iterator__ignore_dot_git(I)    iterator__flag(I,IGNORE_DOT_GIT)
26
#define iterator__descend_symlinks(I)  iterator__flag(I,DESCEND_SYMLINKS)
27

28

Edward Thomson committed
29
static void iterator_set_ignore_case(git_iterator *iter, bool ignore_case)
30
{
Edward Thomson committed
31 32 33 34
	if (ignore_case)
		iter->flags |= GIT_ITERATOR_IGNORE_CASE;
	else
		iter->flags &= ~GIT_ITERATOR_IGNORE_CASE;
35

Edward Thomson committed
36 37 38
	iter->strcomp = ignore_case ? git__strcasecmp : git__strcmp;
	iter->strncomp = ignore_case ? git__strncasecmp : git__strncmp;
	iter->prefixcomp = ignore_case ? git__prefixcmp_icase : git__prefixcmp;
39
	iter->entry_srch = ignore_case ? git_index_entry_isrch : git_index_entry_srch;
40 41

	git_vector_set_cmp(&iter->pathlist, (git_vector_cmp)iter->strcomp);
42
}
43

44 45 46
static int iterator_range_init(
	git_iterator *iter, const char *start, const char *end)
{
47
	if (start && *start) {
48
		iter->start = git__strdup(start);
49
		GIT_ERROR_CHECK_ALLOC(iter->start);
50 51

		iter->start_len = strlen(iter->start);
52 53
	}

54
	if (end && *end) {
55
		iter->end = git__strdup(end);
56
		GIT_ERROR_CHECK_ALLOC(iter->end);
57 58

		iter->end_len = strlen(iter->end);
59 60 61 62 63 64 65 66 67 68 69 70 71
	}

	iter->started = (iter->start == NULL);
	iter->ended = false;

	return 0;
}

static void iterator_range_free(git_iterator *iter)
{
	if (iter->start) {
		git__free(iter->start);
		iter->start = NULL;
72
		iter->start_len = 0;
73 74 75 76 77
	}

	if (iter->end) {
		git__free(iter->end);
		iter->end = NULL;
78
		iter->end_len = 0;
79 80 81
	}
}

Edward Thomson committed
82
static int iterator_reset_range(
83 84 85 86 87 88 89 90 91 92
	git_iterator *iter, const char *start, const char *end)
{
	iterator_range_free(iter);
	return iterator_range_init(iter, start, end);
}

static int iterator_pathlist_init(git_iterator *iter, git_strarray *pathlist)
{
	size_t i;

Edward Thomson committed
93
	if (git_vector_init(&iter->pathlist, pathlist->count, NULL) < 0)
94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109
		return -1;

	for (i = 0; i < pathlist->count; i++) {
		if (!pathlist->strings[i])
			continue;

		if (git_vector_insert(&iter->pathlist, pathlist->strings[i]) < 0)
			return -1;
	}

	return 0;
}

static int iterator_init_common(
	git_iterator *iter,
	git_repository *repo,
110
	git_index *index,
111 112 113 114 115
	git_iterator_options *given_opts)
{
	static git_iterator_options default_opts = GIT_ITERATOR_OPTIONS_INIT;
	git_iterator_options *options = given_opts ? given_opts : &default_opts;
	bool ignore_case;
116
	int precompose;
117 118 119
	int error;

	iter->repo = repo;
120
	iter->index = index;
121 122 123 124 125 126
	iter->flags = options->flags;

	if ((iter->flags & GIT_ITERATOR_IGNORE_CASE) != 0) {
		ignore_case = true;
	} else if ((iter->flags & GIT_ITERATOR_DONT_IGNORE_CASE) != 0) {
		ignore_case = false;
127
	} else if (repo) {
128 129 130 131 132 133 134 135 136 137 138
		git_index *index;

		if ((error = git_repository_index__weakptr(&index, iter->repo)) < 0)
			return error;

		ignore_case = !!index->ignore_case;

		if (ignore_case == 1)
			iter->flags |= GIT_ITERATOR_IGNORE_CASE;
		else
			iter->flags |= GIT_ITERATOR_DONT_IGNORE_CASE;
139 140 141 142 143 144 145 146 147
	} else {
		ignore_case = false;
	}

	/* try to look up precompose and set flag if appropriate */
	if (repo &&
		(iter->flags & GIT_ITERATOR_PRECOMPOSE_UNICODE) == 0 &&
		(iter->flags & GIT_ITERATOR_DONT_PRECOMPOSE_UNICODE) == 0) {

148
		if (git_repository__configmap_lookup(&precompose, repo, GIT_CONFIGMAP_PRECOMPOSE) < 0)
149
			git_error_clear();
150 151
		else if (precompose)
			iter->flags |= GIT_ITERATOR_PRECOMPOSE_UNICODE;
152 153 154 155 156 157 158 159 160
	}

	if ((iter->flags & GIT_ITERATOR_DONT_AUTOEXPAND))
		iter->flags |= GIT_ITERATOR_INCLUDE_TREES;

	if ((error = iterator_range_init(iter, options->start, options->end)) < 0 ||
		(error = iterator_pathlist_init(iter, &options->pathlist)) < 0)
		return error;

Edward Thomson committed
161
	iterator_set_ignore_case(iter, ignore_case);
162 163 164 165 166 167 168
	return 0;
}

static void iterator_clear(git_iterator *iter)
{
	iter->started = false;
	iter->ended = false;
169
	iter->stat_calls = 0;
170 171 172 173
	iter->pathlist_walk_idx = 0;
	iter->flags &= ~GIT_ITERATOR_FIRST_ACCESS;
}

174 175
GIT_INLINE(bool) iterator_has_started(
	git_iterator *iter, const char *path, bool is_submodule)
176 177 178 179 180 181 182 183 184 185 186
{
	size_t path_len;

	if (iter->start == NULL || iter->started == true)
		return true;

	/* the starting path is generally a prefix - we have started once we
	 * are prefixed by this path
	 */
	iter->started = (iter->prefixcomp(path, iter->start) >= 0);

187 188 189 190 191 192 193 194 195 196 197 198 199
	if (iter->started)
		return true;

	path_len = strlen(path);

	/* if, however, we are a submodule, then we support `start` being
	 * suffixed with a `/` for crazy legacy reasons.  match `submod`
	 * with a start path of `submod/`.
	 */
	if (is_submodule && iter->start_len && path_len == iter->start_len - 1 &&
		iter->start[iter->start_len-1] == '/')
		return true;

200 201 202 203
	/* if, however, our current path is a directory, and our starting path
	 * is _beneath_ that directory, then recurse into the directory (even
	 * though we have not yet "started")
	 */
204
	if (path_len > 0 && path[path_len-1] == '/' &&
205 206 207
		iter->strncomp(path, iter->start, path_len) == 0)
		return true;

208
	return false;
209 210
}

211
GIT_INLINE(bool) iterator_has_ended(git_iterator *iter, const char *path)
212
{
213
	if (iter->end == NULL)
214
		return false;
215 216
	else if (iter->ended)
		return true;
217 218 219 220 221

	iter->ended = (iter->prefixcomp(path, iter->end) > 0);
	return iter->ended;
}

222 223
/* walker for the index and tree iterator that allows it to walk the sorted
 * pathlist entries alongside sorted iterator entries.
224
 */
225
static bool iterator_pathlist_next_is(git_iterator *iter, const char *path)
226 227 228 229 230 231 232 233
{
	char *p;
	size_t path_len, p_len, cmp_len, i;
	int cmp;

	if (iter->pathlist.length == 0)
		return true;

Edward Thomson committed
234 235
	git_vector_sort(&iter->pathlist);

236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275
	path_len = strlen(path);

	/* for comparison, drop the trailing slash on the current '/' */
	if (path_len && path[path_len-1] == '/')
		path_len--;

	for (i = iter->pathlist_walk_idx; i < iter->pathlist.length; i++) {
		p = iter->pathlist.contents[i];
		p_len = strlen(p);

		if (p_len && p[p_len-1] == '/')
			p_len--;

		cmp_len = min(path_len, p_len);

		/* see if the pathlist entry is a prefix of this path */
		cmp = iter->strncomp(p, path, cmp_len);

		/* prefix match - see if there's an exact match, or if we were
		 * given a path that matches the directory
		 */
		if (cmp == 0) {
			/* if this pathlist entry is not suffixed with a '/' then
			 * it matches a path that is a file or a directory.
			 * (eg, pathlist = "foo" and path is "foo" or "foo/" or
			 * "foo/something")
			 */
			if (p[cmp_len] == '\0' &&
				(path[cmp_len] == '\0' || path[cmp_len] == '/'))
				return true;

			/* if this pathlist entry _is_ suffixed with a '/' then
			 * it matches only paths that are directories.
			 * (eg, pathlist = "foo/" and path is "foo/" or "foo/something")
			 */
			if (p[cmp_len] == '/' && path[cmp_len] == '/')
				return true;
		}

		/* this pathlist entry sorts before the given path, try the next */
276
		else if (cmp < 0) {
277 278 279 280 281 282 283 284 285 286 287 288 289
			iter->pathlist_walk_idx++;
			continue;
		}

		/* this pathlist sorts after the given path, no match. */
		else if (cmp > 0) {
			break;
		}
	}

	return false;
}

290
typedef enum {
Edward Thomson committed
291
	ITERATOR_PATHLIST_NONE = 0,
292 293 294 295 296 297 298 299 300 301 302 303 304
	ITERATOR_PATHLIST_IS_FILE = 1,
	ITERATOR_PATHLIST_IS_DIR = 2,
	ITERATOR_PATHLIST_IS_PARENT = 3,
	ITERATOR_PATHLIST_FULL = 4,
} iterator_pathlist_search_t;

static iterator_pathlist_search_t iterator_pathlist_search(
	git_iterator *iter, const char *path, size_t path_len)
{
	const char *p;
	size_t idx;
	int error;

Edward Thomson committed
305 306 307 308 309
	if (iter->pathlist.length == 0)
		return ITERATOR_PATHLIST_FULL;

	git_vector_sort(&iter->pathlist);

310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332
	error = git_vector_bsearch2(&idx, &iter->pathlist,
		(git_vector_cmp)iter->strcomp, path);

	/* the given path was found in the pathlist.  since the pathlist only
	 * matches directories when they're suffixed with a '/', analyze the
	 * path string to determine whether it's a directory or not.
	 */
	if (error == 0) {
		if (path_len && path[path_len-1] == '/')
			return ITERATOR_PATHLIST_IS_DIR;

		return ITERATOR_PATHLIST_IS_FILE;
	}

	/* at this point, the path we're examining may be a directory (though we
	 * don't know that yet, since we're avoiding a stat unless it's necessary)
	 * so walk the pathlist looking for the given path with a '/' after it,
	 */
	while ((p = git_vector_get(&iter->pathlist, idx)) != NULL) {
		if (iter->prefixcomp(p, path) != 0)
			break;

		/* an exact match would have been matched by the bsearch above */
333
		GIT_ASSERT_WITH_RETVAL(p[path_len], ITERATOR_PATHLIST_NONE);
334 335 336 337 338 339 340 341 342 343 344 345 346 347

		/* is this a literal directory entry (eg `foo/`) or a file beneath */
		if (p[path_len] == '/') {
			return (p[path_len+1] == '\0') ?
				ITERATOR_PATHLIST_IS_DIR :
				ITERATOR_PATHLIST_IS_PARENT;
		}

		if (p[path_len] > '/')
			break;

		idx++;
	}

Edward Thomson committed
348
	return ITERATOR_PATHLIST_NONE;
349 350
}

351 352
/* Empty iterator */

353
static int empty_iterator_noop(const git_index_entry **e, git_iterator *i)
354 355
{
	GIT_UNUSED(i);
Edward Thomson committed
356 357 358 359

	if (e)
		*e = NULL;

360
	return GIT_ITEROVER;
361 362
}

363 364 365 366 367 368
static int empty_iterator_advance_over(
	const git_index_entry **e,
	git_iterator_status_t *s,
	git_iterator *i)
{
	*s = GIT_ITERATOR_STATUS_EMPTY;
Edward Thomson committed
369
	return empty_iterator_noop(e, i);
370 371 372
}

static int empty_iterator_reset(git_iterator *i)
373 374 375 376 377
{
	GIT_UNUSED(i);
	return 0;
}

378
static void empty_iterator_free(git_iterator *i)
379
{
380
	GIT_UNUSED(i);
381 382
}

383 384 385 386 387
typedef struct {
	git_iterator base;
	git_iterator_callbacks cb;
} empty_iterator;

388
int git_iterator_for_nothing(
389
	git_iterator **out,
390
	git_iterator_options *options)
391
{
392 393 394 395 396 397 398 399 400 401
	empty_iterator *iter;

	static git_iterator_callbacks callbacks = {
		empty_iterator_noop,
		empty_iterator_noop,
		empty_iterator_noop,
		empty_iterator_advance_over,
		empty_iterator_reset,
		empty_iterator_free
	};
402

403
	*out = NULL;
404

405
	iter = git__calloc(1, sizeof(empty_iterator));
406
	GIT_ERROR_CHECK_ALLOC(iter);
407

408
	iter->base.type = GIT_ITERATOR_EMPTY;
409 410
	iter->base.cb = &callbacks;
	iter->base.flags = options->flags;
411

412
	*out = &iter->base;
413 414 415
	return 0;
}

416
/* Tree iterator */
417

418 419 420 421
typedef struct {
	git_tree_entry *tree_entry;
	const char *parent_path;
} tree_iterator_entry;
422

423 424
typedef struct {
	git_tree *tree;
425

426 427 428
	/* path to this particular frame (folder) */
	git_buf path;

429 430 431 432 433
	/* a sorted list of the entries for this frame (folder), these are
	 * actually pointers to the iterator's entry pool.
	 */
	git_vector entries;
	tree_iterator_entry *current;
434

435
	size_t next_idx;
436

437 438 439 440 441
	/* on case insensitive iterations, we also have an array of other
	 * paths that were case insensitively equal to this one, and their
	 * tree objects.  we have coalesced the tree entries into this frame.
	 * a child `tree_iterator_entry` will contain a pointer to its actual
	 * parent path.
442
	 */
443
	git_vector similar_trees;
444 445
	git_array_t(git_buf) similar_paths;
} tree_iterator_frame;
446 447

typedef struct {
448
	git_iterator base;
449 450 451
	git_tree *root;
	git_array_t(tree_iterator_frame) frames;

452
	git_index_entry entry;
453 454 455 456
	git_buf entry_path;

	/* a pool of entries to reduce the number of allocations */
	git_pool entry_pool;
457
} tree_iterator;
458

459 460
GIT_INLINE(tree_iterator_frame *) tree_iterator_parent_frame(
	tree_iterator *iter)
461
{
462 463
	return iter->frames.size > 1 ?
		&iter->frames.ptr[iter->frames.size-2] : NULL;
464 465
}

466 467
GIT_INLINE(tree_iterator_frame *) tree_iterator_current_frame(
	tree_iterator *iter)
468
{
469
	return iter->frames.size ? &iter->frames.ptr[iter->frames.size-1] : NULL;
470
}
471

472 473
GIT_INLINE(int) tree_entry_cmp(
	const git_tree_entry *a, const git_tree_entry *b, bool icase)
474
{
475 476 477
	return git_path_cmp(
		a->filename, a->filename_len, a->attr == GIT_FILEMODE_TREE,
		b->filename, b->filename_len, b->attr == GIT_FILEMODE_TREE,
478
		icase ? git__strncasecmp : git__strncmp);
479 480
}

481 482
GIT_INLINE(int) tree_iterator_entry_cmp_icase(
	const void *ptr_a, const void *ptr_b)
483
{
484 485
	const tree_iterator_entry *a = (const tree_iterator_entry *)ptr_a;
	const tree_iterator_entry *b = (const tree_iterator_entry *)ptr_b;
486

487
	return tree_entry_cmp(a->tree_entry, b->tree_entry, true);
488 489
}

490
static int tree_iterator_entry_sort_icase(const void *ptr_a, const void *ptr_b)
491
{
492 493
	const tree_iterator_entry *a = (const tree_iterator_entry *)ptr_a;
	const tree_iterator_entry *b = (const tree_iterator_entry *)ptr_b;
494

495
	int c = tree_entry_cmp(a->tree_entry, b->tree_entry, true);
496

497 498 499 500 501 502 503 504 505
	/* stabilize the sort order for filenames that are (case insensitively)
	 * the same by examining the parent path (case sensitively) before
	 * falling back to a case sensitive sort of the filename.
	 */
	if (!c && a->parent_path != b->parent_path)
		c = git__strcmp(a->parent_path, b->parent_path);

	if (!c)
		c = tree_entry_cmp(a->tree_entry, b->tree_entry, false);
506

507
	return c;
508 509
}

510 511 512
static int tree_iterator_compute_path(
	git_buf *out,
	tree_iterator_entry *entry)
513
{
514
	git_buf_clear(out);
515

516 517 518 519
	if (entry->parent_path)
		git_buf_joinpath(out, entry->parent_path, entry->tree_entry->filename);
	else
		git_buf_puts(out, entry->tree_entry->filename);
520

521 522
	if (git_tree_entry__is_tree(entry->tree_entry))
		git_buf_putc(out, '/');
523

524 525
	if (git_buf_oom(out))
		return -1;
526

527
	return 0;
528 529
}

530 531 532 533
static int tree_iterator_frame_init(
	tree_iterator *iter,
	git_tree *tree,
	tree_iterator_entry *frame_entry)
534
{
535 536 537 538 539 540
	tree_iterator_frame *new_frame = NULL;
	tree_iterator_entry *new_entry;
	git_tree *dup = NULL;
	git_tree_entry *tree_entry;
	git_vector_cmp cmp;
	size_t i;
541
	int error = 0;
542

543
	new_frame = git_array_alloc(iter->frames);
544
	GIT_ERROR_CHECK_ALLOC(new_frame);
545

546 547
	if ((error = git_tree_dup(&dup, tree)) < 0)
		goto done;
548

549 550
	memset(new_frame, 0x0, sizeof(tree_iterator_frame));
	new_frame->tree = dup;
551

552
	if (frame_entry &&
553
	    (error = tree_iterator_compute_path(&new_frame->path, frame_entry)) < 0)
554
		goto done;
555

556 557
	cmp = iterator__ignore_case(&iter->base) ?
		tree_iterator_entry_sort_icase : NULL;
558

559 560
	if ((error = git_vector_init(&new_frame->entries,
				     dup->entries.size, cmp)) < 0)
561
		goto done;
562

563
	git_array_foreach(dup->entries, i, tree_entry) {
564 565 566 567 568
		if ((new_entry = git_pool_malloc(&iter->entry_pool, 1)) == NULL) {
			git_error_set_oom();
			error = -1;
			goto done;
		}
569

570 571
		new_entry->tree_entry = tree_entry;
		new_entry->parent_path = new_frame->path.ptr;
572

573 574
		if ((error = git_vector_insert(&new_frame->entries, new_entry)) < 0)
			goto done;
575 576
	}

577 578
	git_vector_set_sorted(&new_frame->entries,
		!iterator__ignore_case(&iter->base));
579

580 581 582 583 584
done:
	if (error < 0) {
		git_tree_free(dup);
		git_array_pop(iter->frames);
	}
585

586 587
	return error;
}
588

589 590 591 592
GIT_INLINE(tree_iterator_entry *) tree_iterator_current_entry(
	tree_iterator_frame *frame)
{
	return frame->current;
593
}
594

595 596 597 598 599
GIT_INLINE(int) tree_iterator_frame_push_neighbors(
	tree_iterator *iter,
	tree_iterator_frame *parent_frame,
	tree_iterator_frame *frame,
	const char *filename)
600
{
601 602 603 604 605 606
	tree_iterator_entry *entry, *new_entry;
	git_tree *tree = NULL;
	git_tree_entry *tree_entry;
	git_buf *path;
	size_t new_size, i;
	int error = 0;
607

608 609
	while (parent_frame->next_idx < parent_frame->entries.length) {
		entry = parent_frame->entries.contents[parent_frame->next_idx];
610

611 612
		if (strcasecmp(filename, entry->tree_entry->filename) != 0)
			break;
613

614 615 616
		if ((error = git_tree_lookup(&tree,
			iter->base.repo, entry->tree_entry->oid)) < 0)
			break;
617

618 619 620
		if (git_vector_insert(&parent_frame->similar_trees, tree) < 0)
			break;

621
		path = git_array_alloc(parent_frame->similar_paths);
622
		GIT_ERROR_CHECK_ALLOC(path);
623

624
		memset(path, 0, sizeof(git_buf));
625

626 627
		if ((error = tree_iterator_compute_path(path, entry)) < 0)
			break;
628

629
		GIT_ERROR_CHECK_ALLOC_ADD(&new_size,
630 631
			frame->entries.length, tree->entries.size);
		git_vector_size_hint(&frame->entries, new_size);
632

633 634
		git_array_foreach(tree->entries, i, tree_entry) {
			new_entry = git_pool_malloc(&iter->entry_pool, 1);
635
			GIT_ERROR_CHECK_ALLOC(new_entry);
636 637 638

			new_entry->tree_entry = tree_entry;
			new_entry->parent_path = path->ptr;
639

640 641 642 643 644 645
			if ((error = git_vector_insert(&frame->entries, new_entry)) < 0)
				break;
		}

		if (error)
			break;
646

647
		parent_frame->next_idx++;
648
	}
649 650

	return error;
651 652
}

653 654
GIT_INLINE(int) tree_iterator_frame_push(
	tree_iterator *iter, tree_iterator_entry *entry)
655
{
656 657 658
	tree_iterator_frame *parent_frame, *frame;
	git_tree *tree = NULL;
	int error;
659

660 661 662 663
	if ((error = git_tree_lookup(&tree,
			iter->base.repo, entry->tree_entry->oid)) < 0 ||
		(error = tree_iterator_frame_init(iter, tree, entry)) < 0)
		goto done;
664

665 666
	parent_frame = tree_iterator_parent_frame(iter);
	frame = tree_iterator_current_frame(iter);
667

668 669 670 671 672 673 674
	/* if we're case insensitive, then we may have another directory that
	 * is (case insensitively) equal to this one.  coalesce those children
	 * into this tree.
	 */
	if (iterator__ignore_case(&iter->base))
		error = tree_iterator_frame_push_neighbors(iter,
			parent_frame, frame, entry->tree_entry->filename);
675

676 677 678 679
done:
	git_tree_free(tree);
	return error;
}
680

681
static int tree_iterator_frame_pop(tree_iterator *iter)
682 683
{
	tree_iterator_frame *frame;
684
	git_buf *buf = NULL;
685 686
	git_tree *tree;
	size_t i;
687

688
	GIT_ASSERT(iter->frames.size);
689

690
	frame = git_array_pop(iter->frames);
691

692 693
	git_vector_free(&frame->entries);
	git_tree_free(frame->tree);
694 695 696

	do {
		buf = git_array_pop(frame->similar_paths);
697
		git_buf_dispose(buf);
698 699 700
	} while (buf != NULL);

	git_array_clear(frame->similar_paths);
701 702 703 704 705 706

	git_vector_foreach(&frame->similar_trees, i, tree)
		git_tree_free(tree);

	git_vector_free(&frame->similar_trees);

707
	git_buf_dispose(&frame->path);
708 709

	return 0;
710 711
}

712 713
static int tree_iterator_current(
	const git_index_entry **out, git_iterator *i)
714
{
715
	tree_iterator *iter = (tree_iterator *)i;
716

717 718
	if (!iterator__has_been_accessed(i))
		return iter->base.cb->advance(out, i);
719

720 721
	if (!iter->frames.size) {
		*out = NULL;
722
		return GIT_ITEROVER;
723
	}
724

725
	*out = &iter->entry;
726
	return 0;
727 728
}

729 730 731 732
static void tree_iterator_set_current(
	tree_iterator *iter,
	tree_iterator_frame *frame,
	tree_iterator_entry *entry)
733
{
734
	git_tree_entry *tree_entry = entry->tree_entry;
735

736
	frame->current = entry;
737

738 739 740 741 742
	memset(&iter->entry, 0x0, sizeof(git_index_entry));

	iter->entry.mode = tree_entry->attr;
	iter->entry.path = iter->entry_path.ptr;
	git_oid_cpy(&iter->entry.id, tree_entry->oid);
743 744
}

745
static int tree_iterator_advance(const git_index_entry **out, git_iterator *i)
746
{
747 748
	tree_iterator *iter = (tree_iterator *)i;
	int error = 0;
749

750
	iter->base.flags |= GIT_ITERATOR_FIRST_ACCESS;
751

752 753 754 755 756 757 758 759 760 761
	/* examine tree entries until we find the next one to return */
	while (true) {
		tree_iterator_entry *prev_entry, *entry;
		tree_iterator_frame *frame;
		bool is_tree;

		if ((frame = tree_iterator_current_frame(iter)) == NULL) {
			error = GIT_ITEROVER;
			break;
		}
762

763 764
		/* no more entries in this frame.  pop the frame out */
		if (frame->next_idx == frame->entries.length) {
765 766 767
			if ((error = tree_iterator_frame_pop(iter)) < 0)
				break;

768 769
			continue;
		}
770

771 772 773 774 775
		/* we may have coalesced the contents of case-insensitively same-named
		 * directories, so do the sort now.
		 */
		if (frame->next_idx == 0 && !git_vector_is_sorted(&frame->entries))
			git_vector_sort(&frame->entries);
776

777 778 779 780
		/* we have more entries in the current frame, that's our next entry */
		prev_entry = tree_iterator_current_entry(frame);
		entry = frame->entries.contents[frame->next_idx];
		frame->next_idx++;
781

782 783 784 785 786 787 788
		/* we can have collisions when iterating case insensitively.  (eg,
		 * 'A/a' and 'a/A').  squash this one if it's already been seen.
		 */
		if (iterator__ignore_case(&iter->base) &&
			prev_entry &&
			tree_iterator_entry_cmp_icase(prev_entry, entry) == 0)
			continue;
789

790 791
		if ((error = tree_iterator_compute_path(&iter->entry_path, entry)) < 0)
			break;
792

793
		/* if this path is before our start, advance over this entry */
794
		if (!iterator_has_started(&iter->base, iter->entry_path.ptr, false))
795
			continue;
796

797
		/* if this path is after our end, stop */
798
		if (iterator_has_ended(&iter->base, iter->entry_path.ptr)) {
799 800 801
			error = GIT_ITEROVER;
			break;
		}
802

803
		/* if we have a list of paths we're interested in, examine it */
804
		if (!iterator_pathlist_next_is(&iter->base, iter->entry_path.ptr))
805
			continue;
806

807
		is_tree = git_tree_entry__is_tree(entry->tree_entry);
808

809 810
		/* if we are *not* including trees then advance over this entry */
		if (is_tree && !iterator__include_trees(iter)) {
811

812 813 814 815 816 817 818
			/* if we've found a tree (and are not returning it to the caller)
			 * and we are autoexpanding, then we want to return the first
			 * child.  push the new directory and advance.
			 */
			if (iterator__do_autoexpand(iter)) {
				if ((error = tree_iterator_frame_push(iter, entry)) < 0)
					break;
819
			}
820 821

			continue;
822
		}
823 824 825 826 827 828 829 830 831 832 833

		tree_iterator_set_current(iter, frame, entry);

		/* if we are autoexpanding, then push this as a new frame, so that
		 * the next call to `advance` will dive into this directory.
		 */
		if (is_tree && iterator__do_autoexpand(iter))
			error = tree_iterator_frame_push(iter, entry);

		break;
	}
834 835

	if (out)
836
		*out = (error == 0) ? &iter->entry : NULL;
837 838 839 840

	return error;
}

841 842
static int tree_iterator_advance_into(
	const git_index_entry **out, git_iterator *i)
843
{
844
	tree_iterator *iter = (tree_iterator *)i;
845
	tree_iterator_frame *frame;
846 847
	tree_iterator_entry *prev_entry;
	int error;
848

849 850
	if (out)
		*out = NULL;
851

852 853 854 855 856 857 858 859 860 861
	if ((frame = tree_iterator_current_frame(iter)) == NULL)
		return GIT_ITEROVER;

	/* get the last seen entry */
	prev_entry = tree_iterator_current_entry(frame);

	/* it's legal to call advance_into when auto-expand is on.  in this case,
	 * we will have pushed a new (empty) frame on to the stack for this
	 * new directory.  since it's empty, its current_entry should be null.
	 */
862
	GIT_ASSERT(iterator__do_autoexpand(i) ^ (prev_entry != NULL));
863 864 865 866

	if (prev_entry) {
		if (!git_tree_entry__is_tree(prev_entry->tree_entry))
			return 0;
867

868 869 870 871 872 873 874 875
		if ((error = tree_iterator_frame_push(iter, prev_entry)) < 0)
			return error;
	}

	/* we've advanced into the directory in question, let advance
	 * find the first entry
	 */
	return tree_iterator_advance(out, i);
876 877
}

878 879 880 881 882 883 884 885 886
static int tree_iterator_advance_over(
	const git_index_entry **out,
	git_iterator_status_t *status,
	git_iterator *i)
{
	*status = GIT_ITERATOR_STATUS_NORMAL;
	return git_iterator_advance(out, i);
}

887
static void tree_iterator_clear(tree_iterator *iter)
888
{
889 890
	while (iter->frames.size)
		tree_iterator_frame_pop(iter);
891

892
	git_array_clear(iter->frames);
893

894 895
	git_pool_clear(&iter->entry_pool);
	git_buf_clear(&iter->entry_path);
896

897
	iterator_clear(&iter->base);
898 899
}

900
static int tree_iterator_init(tree_iterator *iter)
901
{
902 903
	int error;

904 905
	if ((error = git_pool_init(&iter->entry_pool, sizeof(tree_iterator_entry))) < 0 ||
	    (error = tree_iterator_frame_init(iter, iter->root, NULL)) < 0)
906
		return error;
907

908 909 910
	iter->base.flags &= ~GIT_ITERATOR_FIRST_ACCESS;

	return 0;
911
}
912

913
static int tree_iterator_reset(git_iterator *i)
914
{
915
	tree_iterator *iter = (tree_iterator *)i;
916

917 918
	tree_iterator_clear(iter);
	return tree_iterator_init(iter);
919 920
}

921
static void tree_iterator_free(git_iterator *i)
922
{
923
	tree_iterator *iter = (tree_iterator *)i;
924

925
	tree_iterator_clear(iter);
926

927
	git_tree_free(iter->root);
928
	git_buf_dispose(&iter->entry_path);
929 930
}

931
int git_iterator_for_tree(
932
	git_iterator **out,
933
	git_tree *tree,
934
	git_iterator_options *options)
935
{
936
	tree_iterator *iter;
937
	int error;
938 939 940 941 942

	static git_iterator_callbacks callbacks = {
		tree_iterator_current,
		tree_iterator_advance,
		tree_iterator_advance_into,
943
		tree_iterator_advance_over,
944 945 946 947 948
		tree_iterator_reset,
		tree_iterator_free
	};

	*out = NULL;
949 950

	if (tree == NULL)
951
		return git_iterator_for_nothing(out, options);
952

953
	iter = git__calloc(1, sizeof(tree_iterator));
954
	GIT_ERROR_CHECK_ALLOC(iter);
955

956
	iter->base.type = GIT_ITERATOR_TREE;
957
	iter->base.cb = &callbacks;
958

959
	if ((error = iterator_init_common(&iter->base,
960
			git_tree_owner(tree), NULL, options)) < 0 ||
961 962 963
		(error = git_tree_dup(&iter->root, tree)) < 0 ||
		(error = tree_iterator_init(iter)) < 0)
		goto on_error;
964

965 966
	*out = &iter->base;
	return 0;
967

968 969 970 971
on_error:
	git_iterator_free(&iter->base);
	return error;
}
972

973 974 975 976 977 978
int git_iterator_current_tree_entry(
	const git_tree_entry **tree_entry, git_iterator *i)
{
	tree_iterator *iter;
	tree_iterator_frame *frame;
	tree_iterator_entry *entry;
979

980
	GIT_ASSERT(i->type == GIT_ITERATOR_TREE);
981 982 983 984 985 986 987

	iter = (tree_iterator *)i;

	frame = tree_iterator_current_frame(iter);
	entry = tree_iterator_current_entry(frame);

	*tree_entry = entry->tree_entry;
988
	return 0;
989
}
990

991 992 993 994 995 996
int git_iterator_current_parent_tree(
	const git_tree **parent_tree, git_iterator *i, size_t depth)
{
	tree_iterator *iter;
	tree_iterator_frame *frame;

997
	GIT_ASSERT(i->type == GIT_ITERATOR_TREE);
998 999 1000

	iter = (tree_iterator *)i;

1001
	GIT_ASSERT(depth < iter->frames.size);
1002 1003 1004 1005
	frame = &iter->frames.ptr[iter->frames.size-depth-1];

	*parent_tree = frame->tree;
	return 0;
1006 1007
}

1008 1009 1010 1011 1012 1013
/* Filesystem iterator */

typedef struct {
	struct stat st;
	size_t path_len;
	iterator_pathlist_search_t match;
1014
	git_oid id;
1015 1016 1017 1018 1019 1020 1021
	char path[GIT_FLEX_ARRAY];
} filesystem_iterator_entry;

typedef struct {
	git_vector entries;
	git_pool entry_pool;
	size_t next_idx;
1022

1023 1024 1025
	size_t path_len;
	int is_ignored;
} filesystem_iterator_frame;
1026 1027

typedef struct {
1028
	git_iterator base;
1029 1030 1031 1032 1033 1034
	char *root;
	size_t root_len;

	unsigned int dirload_flags;

	git_tree *tree;
1035
	git_index *index;
1036
	git_vector index_snapshot;
1037

1038 1039
	git_array_t(filesystem_iterator_frame) frames;
	git_ignores ignores;
1040

1041 1042 1043 1044
	/* info about the current entry */
	git_index_entry entry;
	git_buf current_path;
	int current_is_ignored;
1045

1046 1047 1048 1049 1050 1051 1052 1053 1054 1055
	/* temporary buffer for advance_over */
	git_buf tmp_buf;
} filesystem_iterator;


GIT_INLINE(filesystem_iterator_frame *) filesystem_iterator_parent_frame(
	filesystem_iterator *iter)
{
	return iter->frames.size > 1 ?
		&iter->frames.ptr[iter->frames.size-2] : NULL;
1056 1057
}

1058 1059
GIT_INLINE(filesystem_iterator_frame *) filesystem_iterator_current_frame(
	filesystem_iterator *iter)
1060
{
1061 1062
	return iter->frames.size ? &iter->frames.ptr[iter->frames.size-1] : NULL;
}
1063

1064 1065 1066 1067 1068 1069
GIT_INLINE(filesystem_iterator_entry *) filesystem_iterator_current_entry(
	filesystem_iterator_frame *frame)
{
	return frame->next_idx == 0 ?
		NULL : frame->entries.contents[frame->next_idx-1];
}
1070

1071 1072 1073 1074
static int filesystem_iterator_entry_cmp(const void *_a, const void *_b)
{
	const filesystem_iterator_entry *a = (const filesystem_iterator_entry *)_a;
	const filesystem_iterator_entry *b = (const filesystem_iterator_entry *)_b;
1075

1076 1077
	return git__strcmp(a->path, b->path);
}
1078

1079 1080 1081 1082
static int filesystem_iterator_entry_cmp_icase(const void *_a, const void *_b)
{
	const filesystem_iterator_entry *a = (const filesystem_iterator_entry *)_a;
	const filesystem_iterator_entry *b = (const filesystem_iterator_entry *)_b;
1083

1084
	return git__strcasecmp(a->path, b->path);
1085 1086
}

1087 1088 1089 1090 1091 1092 1093 1094
#define FILESYSTEM_MAX_DEPTH 100

/**
 * Figure out if an entry is a submodule.
 *
 * We consider it a submodule if the path is listed as a submodule in
 * either the tree or the index.
 */
Edward Thomson committed
1095
static int filesystem_iterator_is_submodule(
1096
	bool *out, filesystem_iterator *iter, const char *path, size_t path_len)
1097
{
1098 1099
	bool is_submodule = false;
	int error;
1100

1101
	*out = false;
1102

1103 1104 1105
	/* first see if this path is a submodule in HEAD */
	if (iter->tree) {
		git_tree_entry *entry;
1106

1107
		error = git_tree_entry_bypath(&entry, iter->tree, path);
1108

1109 1110
		if (error < 0 && error != GIT_ENOTFOUND)
			return error;
1111

1112 1113 1114 1115 1116
		if (!error) {
			is_submodule = (entry->attr == GIT_FILEMODE_COMMIT);
			git_tree_entry_free(entry);
		}
	}
1117

1118
	if (!is_submodule && iter->base.index) {
1119
		size_t pos;
1120

1121 1122
		error = git_index_snapshot_find(&pos,
			&iter->index_snapshot, iter->base.entry_srch, path, path_len, 0);
1123

1124 1125
		if (error < 0 && error != GIT_ENOTFOUND)
			return error;
1126

1127 1128 1129 1130 1131
		if (!error) {
			git_index_entry *e = git_vector_get(&iter->index_snapshot, pos);
			is_submodule = (e->mode == GIT_FILEMODE_COMMIT);
		}
	}
1132

1133
	*out = is_submodule;
1134 1135 1136
	return 0;
}

1137 1138 1139 1140
static void filesystem_iterator_frame_push_ignores(
	filesystem_iterator *iter,
	filesystem_iterator_entry *frame_entry,
	filesystem_iterator_frame *new_frame)
1141
{
1142 1143
	filesystem_iterator_frame *previous_frame;
	const char *path = frame_entry ? frame_entry->path : "";
1144

1145 1146 1147 1148 1149
	if (!iterator__honor_ignores(&iter->base))
		return;

	if (git_ignore__lookup(&new_frame->is_ignored,
			&iter->ignores, path, GIT_DIR_FLAG_TRUE) < 0) {
1150
		git_error_clear();
1151
		new_frame->is_ignored = GIT_IGNORE_NOTFOUND;
1152 1153
	}

1154 1155 1156
	/* if this is not the top level directory... */
	if (frame_entry) {
		const char *relative_path;
1157

1158
		previous_frame = filesystem_iterator_parent_frame(iter);
1159

1160 1161 1162 1163 1164 1165 1166 1167 1168
		/* push new ignores for files in this directory */
		relative_path = frame_entry->path + previous_frame->path_len;

		/* inherit ignored from parent if no rule specified */
		if (new_frame->is_ignored <= GIT_IGNORE_NOTFOUND)
			new_frame->is_ignored = previous_frame->is_ignored;

		git_ignore__push_dir(&iter->ignores, relative_path);
	}
1169 1170
}

1171 1172
static void filesystem_iterator_frame_pop_ignores(
	filesystem_iterator *iter)
1173
{
1174 1175
	if (iterator__honor_ignores(&iter->base))
		git_ignore__pop_dir(&iter->ignores);
1176 1177
}

1178 1179 1180 1181 1182 1183 1184
GIT_INLINE(bool) filesystem_iterator_examine_path(
	bool *is_dir_out,
	iterator_pathlist_search_t *match_out,
	filesystem_iterator *iter,
	filesystem_iterator_entry *frame_entry,
	const char *path,
	size_t path_len)
1185
{
1186 1187
	bool is_dir = 0;
	iterator_pathlist_search_t match = ITERATOR_PATHLIST_FULL;
1188

1189
	*is_dir_out = false;
Edward Thomson committed
1190
	*match_out = ITERATOR_PATHLIST_NONE;
1191

1192 1193
	if (iter->base.start_len) {
		int cmp = iter->base.strncomp(path, iter->base.start, path_len);
1194

1195 1196 1197 1198 1199 1200 1201
		/* we haven't stat'ed `path` yet, so we don't yet know if it's a
		 * directory or not.  special case if the current path may be a
		 * directory that matches the start prefix.
		 */
		if (cmp == 0) {
			if (iter->base.start[path_len] == '/')
				is_dir = true;
1202

1203 1204
			else if (iter->base.start[path_len] != '\0')
				cmp = -1;
1205 1206
		}

1207 1208
		if (cmp < 0)
			return false;
1209
	}
1210

1211 1212
	if (iter->base.end_len) {
		int cmp = iter->base.strncomp(path, iter->base.end, iter->base.end_len);
1213

1214 1215
		if (cmp > 0)
			return false;
1216
	}
1217

1218 1219
	/* if we have a pathlist that we're limiting to, examine this path now
	 * to avoid a `stat` if we're not interested in the path.
1220
	 */
1221 1222 1223 1224 1225 1226
	if (iter->base.pathlist.length) {
		/* if our parent was explicitly included, so too are we */
		if (frame_entry && frame_entry->match != ITERATOR_PATHLIST_IS_PARENT)
			match = ITERATOR_PATHLIST_FULL;
		else
			match = iterator_pathlist_search(&iter->base, path, path_len);
1227

Edward Thomson committed
1228
		if (match == ITERATOR_PATHLIST_NONE)
1229
			return false;
1230

1231 1232 1233 1234
		/* Ensure that the pathlist entry lines up with what we expected */
		if (match == ITERATOR_PATHLIST_IS_DIR ||
			match == ITERATOR_PATHLIST_IS_PARENT)
			is_dir = true;
1235 1236
	}

1237 1238 1239
	*is_dir_out = is_dir;
	*match_out = match;
	return true;
1240 1241
}

1242 1243
GIT_INLINE(bool) filesystem_iterator_is_dot_git(
	filesystem_iterator *iter, const char *path, size_t path_len)
1244
{
1245
	size_t len;
1246

1247 1248
	if (!iterator__ignore_dot_git(&iter->base))
		return false;
1249

1250 1251
	if ((len = path_len) < 4)
		return false;
1252

1253 1254
	if (path[len - 1] == '/')
		len--;
1255

1256 1257 1258 1259 1260
	if (git__tolower(path[len - 1]) != 't' ||
		git__tolower(path[len - 2]) != 'i' ||
		git__tolower(path[len - 3]) != 'g' ||
		git__tolower(path[len - 4]) != '.')
		return false;
1261

1262
	return (len == 4 || path[len - 5] == '/');
1263 1264
}

1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276
static int filesystem_iterator_entry_hash(
	filesystem_iterator *iter,
	filesystem_iterator_entry *entry)
{
	git_buf fullpath = GIT_BUF_INIT;
	int error;

	if (S_ISDIR(entry->st.st_mode)) {
		memset(&entry->id, 0, GIT_OID_RAWSZ);
		return 0;
	}

1277
	if (iter->base.type == GIT_ITERATOR_WORKDIR)
1278
		return git_repository_hashfile(&entry->id,
1279
			iter->base.repo, entry->path, GIT_OBJECT_BLOB, NULL);
1280

1281 1282
	if (!(error = git_buf_joinpath(&fullpath, iter->root, entry->path)) &&
	    !(error = git_path_validate_workdir_buf(iter->base.repo, &fullpath)))
1283
		error = git_odb_hashfile(&entry->id, fullpath.ptr, GIT_OBJECT_BLOB);
1284 1285 1286 1287 1288 1289 1290 1291

	git_buf_dispose(&fullpath);
	return error;
}

static int filesystem_iterator_entry_init(
	filesystem_iterator_entry **out,
	filesystem_iterator *iter,
1292 1293 1294 1295 1296
	filesystem_iterator_frame *frame,
	const char *path,
	size_t path_len,
	struct stat *statbuf,
	iterator_pathlist_search_t pathlist_match)
1297
{
1298 1299
	filesystem_iterator_entry *entry;
	size_t entry_size;
1300 1301 1302
	int error = 0;

	*out = NULL;
1303

1304 1305 1306
	/* Make sure to append two bytes, one for the path's null
	 * termination, one for a possible trailing '/' for folders.
	 */
1307
	GIT_ERROR_CHECK_ALLOC_ADD(&entry_size,
1308
		sizeof(filesystem_iterator_entry), path_len);
1309
	GIT_ERROR_CHECK_ALLOC_ADD(&entry_size, entry_size, 2);
1310 1311

	entry = git_pool_malloc(&frame->entry_pool, entry_size);
1312
	GIT_ERROR_CHECK_ALLOC(entry);
1313

1314 1315 1316 1317
	entry->path_len = path_len;
	entry->match = pathlist_match;
	memcpy(entry->path, path, path_len);
	memcpy(&entry->st, statbuf, sizeof(struct stat));
1318

1319 1320 1321
	/* Suffix directory paths with a '/' */
	if (S_ISDIR(entry->st.st_mode))
		entry->path[entry->path_len++] = '/';
1322

1323
	entry->path[entry->path_len] = '\0';
1324

1325 1326 1327 1328 1329 1330 1331
	if (iter->base.flags & GIT_ITERATOR_INCLUDE_HASH)
		error = filesystem_iterator_entry_hash(iter, entry);

	if (!error)
		*out = entry;

	return error;
1332
}
1333

1334 1335 1336
static int filesystem_iterator_frame_push(
	filesystem_iterator *iter,
	filesystem_iterator_entry *frame_entry)
1337
{
1338 1339 1340 1341 1342 1343 1344 1345
	filesystem_iterator_frame *new_frame = NULL;
	git_path_diriter diriter = GIT_PATH_DIRITER_INIT;
	git_buf root = GIT_BUF_INIT;
	const char *path;
	filesystem_iterator_entry *entry;
	struct stat statbuf;
	size_t path_len;
	int error;
1346

1347
	if (iter->frames.size == FILESYSTEM_MAX_DEPTH) {
1348
		git_error_set(GIT_ERROR_REPOSITORY,
1349
			"directory nesting too deep (%"PRIuZ")", iter->frames.size);
1350
		return -1;
1351
	}
1352

1353
	new_frame = git_array_alloc(iter->frames);
1354
	GIT_ERROR_CHECK_ALLOC(new_frame);
1355

1356
	memset(new_frame, 0, sizeof(filesystem_iterator_frame));
1357

1358 1359
	if (frame_entry)
		git_buf_joinpath(&root, iter->root, frame_entry->path);
1360
	else
1361
		git_buf_puts(&root, iter->root);
1362

1363 1364
	if (git_buf_oom(&root) ||
	    git_path_validate_workdir_buf(iter->base.repo, &root) < 0) {
1365 1366 1367 1368 1369
		error = -1;
		goto done;
	}

	new_frame->path_len = frame_entry ? frame_entry->path_len : 0;
1370

1371
	/* Any error here is equivalent to the dir not existing, skip over it */
1372
	if ((error = git_path_diriter_init(
1373
			&diriter, root.ptr, iter->dirload_flags)) < 0) {
1374
		error = GIT_ENOTFOUND;
1375
		goto done;
1376
	}
1377

1378 1379 1380 1381 1382 1383
	if ((error = git_vector_init(&new_frame->entries, 64,
			iterator__ignore_case(&iter->base) ?
			filesystem_iterator_entry_cmp_icase :
			filesystem_iterator_entry_cmp)) < 0)
		goto done;

1384 1385
	if ((error = git_pool_init(&new_frame->entry_pool, 1)) < 0)
		goto done;
1386 1387 1388 1389

	/* check if this directory is ignored */
	filesystem_iterator_frame_push_ignores(iter, frame_entry, new_frame);

1390
	while ((error = git_path_diriter_next(&diriter)) == 0) {
1391 1392 1393
		iterator_pathlist_search_t pathlist_match = ITERATOR_PATHLIST_FULL;
		bool dir_expected = false;

1394 1395
		if ((error = git_path_diriter_fullpath(&path, &path_len, &diriter)) < 0 ||
		    (error = git_path_validate_workdir_with_len(iter->base.repo, path, path_len)) < 0)
1396 1397
			goto done;

1398
		GIT_ASSERT(path_len > iter->root_len);
1399 1400

		/* remove the prefix if requested */
1401 1402
		path += iter->root_len;
		path_len -= iter->root_len;
1403

1404 1405 1406 1407
		/* examine start / end and the pathlist to see if this path is in it.
		 * note that since we haven't yet stat'ed the path, we cannot know
		 * whether it's a directory yet or not, so this can give us an
		 * expected type (S_IFDIR or S_IFREG) that we should examine)
1408
		 */
1409 1410
		if (!filesystem_iterator_examine_path(&dir_expected, &pathlist_match,
			iter, frame_entry, path, path_len))
1411 1412
			continue;

1413 1414
		/* TODO: don't need to stat if assume unchanged for this path and
		 * we have an index, we can just copy the data out of it.
1415 1416
		 */

1417 1418 1419 1420
		if ((error = git_path_diriter_stat(&statbuf, &diriter)) < 0) {
			/* file was removed between readdir and lstat */
			if (error == GIT_ENOTFOUND)
				continue;
1421

1422 1423 1424
			/* treat the file as unreadable */
			memset(&statbuf, 0, sizeof(statbuf));
			statbuf.st_mode = GIT_FILEMODE_UNREADABLE;
1425

1426 1427
			error = 0;
		}
1428

1429
		iter->base.stat_calls++;
1430

1431 1432 1433 1434 1435 1436
		/* Ignore wacky things in the filesystem */
		if (!S_ISDIR(statbuf.st_mode) &&
			!S_ISREG(statbuf.st_mode) &&
			!S_ISLNK(statbuf.st_mode) &&
			statbuf.st_mode != GIT_FILEMODE_UNREADABLE)
			continue;
1437

1438
		if (filesystem_iterator_is_dot_git(iter, path, path_len))
1439
			continue;
1440 1441 1442 1443 1444

		/* convert submodules to GITLINK and remove trailing slashes */
		if (S_ISDIR(statbuf.st_mode)) {
			bool submodule = false;

Edward Thomson committed
1445 1446
			if ((error = filesystem_iterator_is_submodule(&submodule,
					iter, path, path_len)) < 0)
1447 1448 1449 1450
				goto done;

			if (submodule)
				statbuf.st_mode = GIT_FILEMODE_COMMIT;
1451 1452
		}

1453
		/* Ensure that the pathlist entry lines up with what we expected */
1454
		else if (dir_expected)
1455 1456
			continue;

1457 1458 1459
		if ((error = filesystem_iterator_entry_init(&entry,
			iter, new_frame, path, path_len, &statbuf, pathlist_match)) < 0)
			goto done;
1460 1461

		git_vector_insert(&new_frame->entries, entry);
1462 1463 1464 1465 1466 1467
	}

	if (error == GIT_ITEROVER)
		error = 0;

	/* sort now that directory suffix is added */
1468
	git_vector_sort(&new_frame->entries);
1469 1470

done:
1471 1472 1473
	if (error < 0)
		git_array_pop(iter->frames);

1474
	git_buf_dispose(&root);
1475 1476 1477 1478
	git_path_diriter_free(&diriter);
	return error;
}

1479
GIT_INLINE(int) filesystem_iterator_frame_pop(filesystem_iterator *iter)
1480
{
1481
	filesystem_iterator_frame *frame;
1482

1483
	GIT_ASSERT(iter->frames.size);
1484

1485 1486
	frame = git_array_pop(iter->frames);
	filesystem_iterator_frame_pop_ignores(iter);
1487

1488 1489
	git_pool_clear(&frame->entry_pool);
	git_vector_free(&frame->entries);
1490 1491

	return 0;
1492
}
1493

1494 1495 1496 1497
static void filesystem_iterator_set_current(
	filesystem_iterator *iter,
	filesystem_iterator_entry *entry)
{
1498 1499 1500 1501 1502 1503 1504 1505 1506
	/*
	 * Index entries are limited to 32 bit timestamps.  We can safely
	 * cast this since workdir times are only used in the cache; any
	 * mismatch will cause a hash recomputation which is unfortunate
	 * but affects only people who set their filetimes to 2038.
	 * (Same with the file size.)
	 */
	iter->entry.ctime.seconds = (int32_t)entry->st.st_ctime;
	iter->entry.mtime.seconds = (int32_t)entry->st.st_mtime;
1507

1508
#if defined(GIT_USE_NSEC)
1509
	iter->entry.ctime.nanoseconds = entry->st.st_ctime_nsec;
1510
	iter->entry.mtime.nanoseconds = entry->st.st_mtime_nsec;
1511 1512 1513
#else
	iter->entry.ctime.nanoseconds = 0;
	iter->entry.mtime.nanoseconds = 0;
1514
#endif
1515

1516 1517 1518 1519 1520
	iter->entry.dev = entry->st.st_dev;
	iter->entry.ino = entry->st.st_ino;
	iter->entry.mode = git_futils_canonical_mode(entry->st.st_mode);
	iter->entry.uid = entry->st.st_uid;
	iter->entry.gid = entry->st.st_gid;
1521
	iter->entry.file_size = (uint32_t)entry->st.st_size;
1522

1523 1524 1525
	if (iter->base.flags & GIT_ITERATOR_INCLUDE_HASH)
		git_oid_cpy(&iter->entry.id, &entry->id);

1526
	iter->entry.path = entry->path;
1527

1528
	iter->current_is_ignored = GIT_IGNORE_UNCHECKED;
1529 1530
}

1531 1532
static int filesystem_iterator_current(
	const git_index_entry **out, git_iterator *i)
1533
{
1534
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1535

1536 1537
	if (!iterator__has_been_accessed(i))
		return iter->base.cb->advance(out, i);
1538

1539 1540 1541 1542
	if (!iter->frames.size) {
		*out = NULL;
		return GIT_ITEROVER;
	}
1543

1544 1545
	*out = &iter->entry;
	return 0;
1546 1547
}

1548 1549 1550 1551
static int filesystem_iterator_is_dir(
	bool *is_dir,
	const filesystem_iterator *iter,
	const filesystem_iterator_entry *entry)
1552 1553
{
	struct stat st;
1554 1555
	git_buf fullpath = GIT_BUF_INIT;
	int error = 0;
1556

1557 1558 1559 1560 1561 1562 1563 1564 1565
	if (S_ISDIR(entry->st.st_mode)) {
		*is_dir = 1;
		goto done;
	}

	if (!iterator__descend_symlinks(iter) || !S_ISLNK(entry->st.st_mode)) {
		*is_dir = 0;
		goto done;
	}
1566

1567
	if ((error = git_buf_joinpath(&fullpath, iter->root, entry->path)) < 0 ||
1568 1569
	    (error = git_path_validate_workdir_buf(iter->base.repo, &fullpath)) < 0 ||
	    (error = p_stat(fullpath.ptr, &st)) < 0)
1570 1571 1572 1573 1574
		goto done;

	*is_dir = S_ISDIR(st.st_mode);

done:
1575
	git_buf_dispose(&fullpath);
1576
	return error;
1577 1578
}

1579 1580
static int filesystem_iterator_advance(
	const git_index_entry **out, git_iterator *i)
1581
{
1582
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1583
	bool is_dir;
1584 1585
	int error = 0;

1586
	iter->base.flags |= GIT_ITERATOR_FIRST_ACCESS;
1587

1588 1589 1590 1591
	/* examine filesystem entries until we find the next one to return */
	while (true) {
		filesystem_iterator_frame *frame;
		filesystem_iterator_entry *entry;
1592

1593 1594 1595 1596
		if ((frame = filesystem_iterator_current_frame(iter)) == NULL) {
			error = GIT_ITEROVER;
			break;
		}
1597

1598 1599 1600 1601 1602
		/* no more entries in this frame.  pop the frame out */
		if (frame->next_idx == frame->entries.length) {
			filesystem_iterator_frame_pop(iter);
			continue;
		}
1603

1604 1605 1606
		/* we have more entries in the current frame, that's our next entry */
		entry = frame->entries.contents[frame->next_idx];
		frame->next_idx++;
1607

1608 1609 1610 1611
		if ((error = filesystem_iterator_is_dir(&is_dir, iter, entry)) < 0)
			break;

		if (is_dir) {
1612 1613
			if (iterator__do_autoexpand(iter)) {
				error = filesystem_iterator_frame_push(iter, entry);
1614

1615 1616 1617 1618 1619 1620 1621 1622
				/* may get GIT_ENOTFOUND due to races or permission problems
				 * that we want to quietly swallow
				 */
				if (error == GIT_ENOTFOUND)
					continue;
				else if (error < 0)
					break;
			}
1623

1624 1625 1626
			if (!iterator__include_trees(iter))
				continue;
		}
1627

1628 1629
		filesystem_iterator_set_current(iter, entry);
		break;
1630
	}
1631 1632 1633 1634 1635

	if (out)
		*out = (error == 0) ? &iter->entry : NULL;

	return error;
1636
}
1637

1638 1639
static int filesystem_iterator_advance_into(
	const git_index_entry **out, git_iterator *i)
1640
{
1641
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1642 1643
	filesystem_iterator_frame *frame;
	filesystem_iterator_entry *prev_entry;
1644 1645
	int error;

1646 1647
	if (out)
		*out = NULL;
1648

1649 1650
	if ((frame = filesystem_iterator_current_frame(iter)) == NULL)
		return GIT_ITEROVER;
1651

1652 1653
	/* get the last seen entry */
	prev_entry = filesystem_iterator_current_entry(frame);
1654

1655 1656 1657 1658
	/* it's legal to call advance_into when auto-expand is on.  in this case,
	 * we will have pushed a new (empty) frame on to the stack for this
	 * new directory.  since it's empty, its current_entry should be null.
	 */
1659
	GIT_ASSERT(iterator__do_autoexpand(i) ^ (prev_entry != NULL));
1660

1661 1662 1663 1664
	if (prev_entry) {
		if (prev_entry->st.st_mode != GIT_FILEMODE_COMMIT &&
			!S_ISDIR(prev_entry->st.st_mode))
			return 0;
1665

1666
		if ((error = filesystem_iterator_frame_push(iter, prev_entry)) < 0)
1667 1668 1669
			return error;
	}

1670 1671 1672 1673
	/* we've advanced into the directory in question, let advance
	 * find the first entry
	 */
	return filesystem_iterator_advance(out, i);
1674 1675
}

1676
int git_iterator_current_workdir_path(git_buf **out, git_iterator *i)
1677
{
1678
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1679
	const git_index_entry *entry;
1680

1681 1682
	if (i->type != GIT_ITERATOR_FS &&
		i->type != GIT_ITERATOR_WORKDIR) {
1683 1684 1685
		*out = NULL;
		return 0;
	}
1686

1687
	git_buf_truncate(&iter->current_path, iter->root_len);
1688

1689 1690 1691
	if (git_iterator_current(&entry, i) < 0 ||
		git_buf_puts(&iter->current_path, entry->path) < 0)
		return -1;
1692

1693 1694 1695
	*out = &iter->current_path;
	return 0;
}
1696

1697 1698 1699 1700 1701 1702 1703 1704 1705 1706
GIT_INLINE(git_dir_flag) entry_dir_flag(git_index_entry *entry)
{
#if defined(GIT_WIN32) && !defined(__MINGW32__)
	return (entry && entry->mode) ?
		(S_ISDIR(entry->mode) ? GIT_DIR_FLAG_TRUE : GIT_DIR_FLAG_FALSE) :
		GIT_DIR_FLAG_UNKNOWN;
#else
	GIT_UNUSED(entry);
	return GIT_DIR_FLAG_UNKNOWN;
#endif
1707 1708
}

1709
static void filesystem_iterator_update_ignored(filesystem_iterator *iter)
1710
{
1711 1712
	filesystem_iterator_frame *frame;
	git_dir_flag dir_flag = entry_dir_flag(&iter->entry);
1713

1714 1715
	if (git_ignore__lookup(&iter->current_is_ignored,
			&iter->ignores, iter->entry.path, dir_flag) < 0) {
1716
		git_error_clear();
1717 1718
		iter->current_is_ignored = GIT_IGNORE_NOTFOUND;
	}
1719

1720 1721 1722 1723 1724
	/* use ignore from containing frame stack */
	if (iter->current_is_ignored <= GIT_IGNORE_NOTFOUND) {
		frame = filesystem_iterator_current_frame(iter);
		iter->current_is_ignored = frame->is_ignored;
	}
1725 1726
}

1727 1728
GIT_INLINE(bool) filesystem_iterator_current_is_ignored(
	filesystem_iterator *iter)
1729
{
1730 1731
	if (iter->current_is_ignored == GIT_IGNORE_UNCHECKED)
		filesystem_iterator_update_ignored(iter);
1732

1733
	return (iter->current_is_ignored == GIT_IGNORE_TRUE);
1734 1735
}

1736
bool git_iterator_current_is_ignored(git_iterator *i)
1737
{
1738 1739
	filesystem_iterator *iter = NULL;

1740
	if (i->type != GIT_ITERATOR_WORKDIR)
1741
		return false;
1742

1743 1744 1745
	iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);

	return filesystem_iterator_current_is_ignored(iter);
1746
}
1747

1748 1749
bool git_iterator_current_tree_is_ignored(git_iterator *i)
{
1750
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1751
	filesystem_iterator_frame *frame;
1752

1753
	if (i->type != GIT_ITERATOR_WORKDIR)
1754
		return false;
1755

1756 1757 1758
	frame = filesystem_iterator_current_frame(iter);
	return (frame->is_ignored == GIT_IGNORE_TRUE);
}
1759

1760 1761 1762 1763 1764
static int filesystem_iterator_advance_over(
	const git_index_entry **out,
	git_iterator_status_t *status,
	git_iterator *i)
{
1765
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1766 1767 1768 1769 1770
	filesystem_iterator_frame *current_frame;
	filesystem_iterator_entry *current_entry;
	const git_index_entry *entry = NULL;
	const char *base;
	int error = 0;
1771

1772 1773
	*out = NULL;
	*status = GIT_ITERATOR_STATUS_NORMAL;
1774

1775
	GIT_ASSERT(iterator__has_been_accessed(i));
1776

1777
	current_frame = filesystem_iterator_current_frame(iter);
1778 1779
	GIT_ASSERT(current_frame);

1780
	current_entry = filesystem_iterator_current_entry(current_frame);
1781
	GIT_ASSERT(current_entry);
1782

1783 1784
	if ((error = git_iterator_current(&entry, i)) < 0)
		return error;
1785

1786 1787 1788
	if (!S_ISDIR(entry->mode)) {
		if (filesystem_iterator_current_is_ignored(iter))
			*status = GIT_ITERATOR_STATUS_IGNORED;
1789

1790
		return filesystem_iterator_advance(out, i);
1791
	}
1792

1793 1794 1795
	git_buf_clear(&iter->tmp_buf);
	if ((error = git_buf_puts(&iter->tmp_buf, entry->path)) < 0)
		return error;
1796

1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810
	base = iter->tmp_buf.ptr;

	/* scan inside the directory looking for files.  if we find nothing,
	 * we will remain EMPTY.  if we find any ignored item, upgrade EMPTY to
	 * IGNORED.  if we find a real actual item, upgrade all the way to NORMAL
	 * and then stop.
	 *
	 * however, if we're here looking for a pathlist item (but are not
	 * actually in the pathlist ourselves) then start at FILTERED instead of
	 * EMPTY.  callers then know that this path was not something they asked
	 * about.
	 */
	*status = current_entry->match == ITERATOR_PATHLIST_IS_PARENT ?
		GIT_ITERATOR_STATUS_FILTERED : GIT_ITERATOR_STATUS_EMPTY;
1811

1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822
	while (entry && !iter->base.prefixcomp(entry->path, base)) {
		if (filesystem_iterator_current_is_ignored(iter)) {
			/* if we found an explicitly ignored item, then update from
			 * EMPTY to IGNORED
			 */
			*status = GIT_ITERATOR_STATUS_IGNORED;
		} else if (S_ISDIR(entry->mode)) {
			error = filesystem_iterator_advance_into(&entry, i);

			if (!error)
				continue;
1823

1824 1825 1826
			/* this directory disappeared, ignore it */
			else if (error == GIT_ENOTFOUND)
				error = 0;
1827

1828 1829 1830
			/* a real error occurred */
			else
				break;
1831
		} else {
1832 1833 1834
			/* we found a non-ignored item, treat parent as untracked */
			*status = GIT_ITERATOR_STATUS_NORMAL;
			break;
1835
		}
1836 1837 1838 1839 1840 1841 1842 1843 1844

		if ((error = git_iterator_advance(&entry, i)) < 0)
			break;
	}

	/* wrap up scan back to base directory */
	while (entry && !iter->base.prefixcomp(entry->path, base)) {
		if ((error = git_iterator_advance(&entry, i)) < 0)
			break;
1845 1846
	}

1847 1848 1849
	if (!error)
		*out = entry;

1850 1851 1852
	return error;
}

1853
static void filesystem_iterator_clear(filesystem_iterator *iter)
1854
{
1855 1856
	while (iter->frames.size)
		filesystem_iterator_frame_pop(iter);
1857

1858 1859
	git_array_clear(iter->frames);
	git_ignore__free(&iter->ignores);
1860

1861
	git_buf_dispose(&iter->tmp_buf);
1862

1863
	iterator_clear(&iter->base);
1864
}
1865

1866
static int filesystem_iterator_init(filesystem_iterator *iter)
1867
{
1868
	int error;
1869

1870 1871 1872 1873
	if (iterator__honor_ignores(&iter->base) &&
		(error = git_ignore__for_path(iter->base.repo,
			".gitignore", &iter->ignores)) < 0)
		return error;
1874

1875 1876
	if ((error = filesystem_iterator_frame_push(iter, NULL)) < 0)
		return error;
1877

1878
	iter->base.flags &= ~GIT_ITERATOR_FIRST_ACCESS;
1879

1880
	return 0;
1881 1882
}

1883
static int filesystem_iterator_reset(git_iterator *i)
1884
{
1885
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1886

1887 1888 1889
	filesystem_iterator_clear(iter);
	return filesystem_iterator_init(iter);
}
1890

1891 1892
static void filesystem_iterator_free(git_iterator *i)
{
1893
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1894
	git__free(iter->root);
1895
	git_buf_dispose(&iter->current_path);
1896
	git_tree_free(iter->tree);
1897 1898
	if (iter->index)
		git_index_snapshot_release(&iter->index_snapshot, iter->index);
1899
	filesystem_iterator_clear(iter);
1900 1901
}

1902 1903 1904 1905 1906 1907
static int iterator_for_filesystem(
	git_iterator **out,
	git_repository *repo,
	const char *root,
	git_index *index,
	git_tree *tree,
1908
	git_iterator_t type,
1909
	git_iterator_options *options)
1910
{
1911 1912 1913
	filesystem_iterator *iter;
	size_t root_len;
	int error;
1914

1915 1916 1917 1918 1919 1920 1921 1922
	static git_iterator_callbacks callbacks = {
		filesystem_iterator_current,
		filesystem_iterator_advance,
		filesystem_iterator_advance_into,
		filesystem_iterator_advance_over,
		filesystem_iterator_reset,
		filesystem_iterator_free
	};
1923

1924
	*out = NULL;
1925

1926 1927
	if (root == NULL)
		return git_iterator_for_nothing(out, options);
1928

1929
	iter = git__calloc(1, sizeof(filesystem_iterator));
1930
	GIT_ERROR_CHECK_ALLOC(iter);
1931

1932 1933 1934
	iter->base.type = type;
	iter->base.cb = &callbacks;

1935
	root_len = strlen(root);
1936

1937
	iter->root = git__malloc(root_len+2);
1938
	GIT_ERROR_CHECK_ALLOC(iter->root);
1939

1940
	memcpy(iter->root, root, root_len);
1941

1942 1943 1944
	if (root_len == 0 || root[root_len-1] != '/') {
		iter->root[root_len] = '/';
		root_len++;
1945
	}
1946 1947
	iter->root[root_len] = '\0';
	iter->root_len = root_len;
1948

1949 1950
	if ((error = git_buf_puts(&iter->current_path, iter->root)) < 0)
		goto on_error;
1951

1952
	if ((error = iterator_init_common(&iter->base, repo, index, options)) < 0)
1953 1954 1955 1956 1957
		goto on_error;

	if (tree && (error = git_tree_dup(&iter->tree, tree)) < 0)
		goto on_error;

1958
	if (index &&
1959 1960 1961
		(error = git_index_snapshot_new(&iter->index_snapshot, index)) < 0)
		goto on_error;

1962
	iter->index = index;
1963 1964 1965 1966
	iter->dirload_flags =
		(iterator__ignore_case(&iter->base) ? GIT_PATH_DIR_IGNORE_CASE : 0) |
		(iterator__flag(&iter->base, PRECOMPOSE_UNICODE) ?
			 GIT_PATH_DIR_PRECOMPOSE_UNICODE : 0);
1967

1968 1969
	if ((error = filesystem_iterator_init(iter)) < 0)
		goto on_error;
1970

1971
	*out = &iter->base;
1972
	return 0;
1973 1974 1975 1976

on_error:
	git_iterator_free(&iter->base);
	return error;
1977 1978
}

1979 1980 1981 1982
int git_iterator_for_filesystem(
	git_iterator **out,
	const char *root,
	git_iterator_options *options)
1983
{
1984
	return iterator_for_filesystem(out,
1985
		NULL, root, NULL, NULL, GIT_ITERATOR_FS, options);
1986 1987
}

1988
int git_iterator_for_workdir_ext(
1989
	git_iterator **out,
1990
	git_repository *repo,
1991
	const char *repo_workdir,
1992 1993
	git_index *index,
	git_tree *tree,
1994
	git_iterator_options *given_opts)
1995
{
1996
	git_iterator_options options = GIT_ITERATOR_OPTIONS_INIT;
1997

1998 1999 2000
	if (!repo_workdir) {
		if (git_repository__ensure_not_bare(repo, "scan working directory") < 0)
			return GIT_EBAREREPO;
2001

2002
		repo_workdir = git_repository_workdir(repo);
2003 2004
	}

2005 2006 2007
	/* upgrade to a workdir iterator, adding necessary internal flags */
	if (given_opts)
		memcpy(&options, given_opts, sizeof(git_iterator_options));
2008

2009 2010
	options.flags |= GIT_ITERATOR_HONOR_IGNORES |
		GIT_ITERATOR_IGNORE_DOT_GIT;
2011

2012
	return iterator_for_filesystem(out,
2013
		repo, repo_workdir, index, tree, GIT_ITERATOR_WORKDIR, &options);
2014 2015
}

2016

2017
/* Index iterator */
2018

2019

2020 2021 2022
typedef struct {
	git_iterator base;
	git_vector entries;
2023 2024 2025
	size_t next_idx;

	/* the pseudotree entry */
2026
	git_index_entry tree_entry;
2027 2028 2029 2030
	git_buf tree_buf;
	bool skip_tree;

	const git_index_entry *entry;
2031
} index_iterator;
2032

2033 2034
static int index_iterator_current(
	const git_index_entry **out, git_iterator *i)
2035
{
2036
	index_iterator *iter = (index_iterator *)i;
2037

2038 2039 2040 2041 2042 2043
	if (!iterator__has_been_accessed(i))
		return iter->base.cb->advance(out, i);

	if (iter->entry == NULL) {
		*out = NULL;
		return GIT_ITEROVER;
2044 2045
	}

2046 2047
	*out = iter->entry;
	return 0;
2048 2049
}

2050 2051 2052 2053
static bool index_iterator_create_pseudotree(
	const git_index_entry **out,
	index_iterator *iter,
	const char *path)
2054
{
2055 2056
	const char *prev_path, *relative_path, *dirsep;
	size_t common_len;
2057

2058
	prev_path = iter->entry ? iter->entry->path : "";
2059

2060 2061 2062
	/* determine if the new path is in a different directory from the old */
	common_len = git_path_common_dirlen(prev_path, path);
	relative_path = path + common_len;
2063

2064 2065
	if ((dirsep = strchr(relative_path, '/')) == NULL)
		return false;
2066

2067 2068
	git_buf_clear(&iter->tree_buf);
	git_buf_put(&iter->tree_buf, path, (dirsep - path) + 1);
2069

2070 2071
	iter->tree_entry.mode = GIT_FILEMODE_TREE;
	iter->tree_entry.path = iter->tree_buf.ptr;
2072

2073 2074
	*out = &iter->tree_entry;
	return true;
2075 2076
}

2077
static int index_iterator_skip_pseudotree(index_iterator *iter)
2078
{
2079 2080
	GIT_ASSERT(iterator__has_been_accessed(&iter->base));
	GIT_ASSERT(S_ISDIR(iter->entry->mode));
2081

2082 2083
	while (true) {
		const git_index_entry *next_entry = NULL;
2084

2085 2086
		if (++iter->next_idx >= iter->entries.length)
			return GIT_ITEROVER;
2087

2088
		next_entry = iter->entries.contents[iter->next_idx];
2089

2090 2091 2092 2093
		if (iter->base.strncomp(iter->tree_buf.ptr, next_entry->path,
			iter->tree_buf.size) != 0)
			break;
	}
2094

2095
	iter->skip_tree = false;
2096
	return 0;
2097 2098
}

2099 2100
static int index_iterator_advance(
	const git_index_entry **out, git_iterator *i)
2101
{
2102
	index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2103
	const git_index_entry *entry = NULL;
2104
	bool is_submodule;
2105
	int error = 0;
2106

2107
	iter->base.flags |= GIT_ITERATOR_FIRST_ACCESS;
2108

2109 2110 2111 2112 2113
	while (true) {
		if (iter->next_idx >= iter->entries.length) {
			error = GIT_ITEROVER;
			break;
		}
2114

2115 2116 2117 2118 2119
		/* we were not asked to expand this pseudotree.  advance over it. */
		if (iter->skip_tree) {
			index_iterator_skip_pseudotree(iter);
			continue;
		}
2120

2121
		entry = iter->entries.contents[iter->next_idx];
2122
		is_submodule = S_ISGITLINK(entry->mode);
2123

2124
		if (!iterator_has_started(&iter->base, entry->path, is_submodule)) {
2125 2126 2127
			iter->next_idx++;
			continue;
		}
2128

2129
		if (iterator_has_ended(&iter->base, entry->path)) {
2130 2131 2132
			error = GIT_ITEROVER;
			break;
		}
2133

2134 2135 2136 2137 2138
		/* if we have a list of paths we're interested in, examine it */
		if (!iterator_pathlist_next_is(&iter->base, entry->path)) {
			iter->next_idx++;
			continue;
		}
2139

2140 2141 2142 2143 2144 2145
		/* if this is a conflict, skip it unless we're including conflicts */
		if (git_index_entry_is_conflict(entry) &&
			!iterator__include_conflicts(&iter->base)) {
			iter->next_idx++;
			continue;
		}
2146

2147 2148 2149 2150 2151 2152 2153
		/* we've found what will be our next _file_ entry.  but if we are
		 * returning trees entries, we may need to return a pseudotree
		 * entry that will contain this.  don't advance over this entry,
		 * though, we still need to return it on the next `advance`.
		 */
		if (iterator__include_trees(&iter->base) &&
			index_iterator_create_pseudotree(&entry, iter, entry->path)) {
2154

2155 2156 2157
			/* Note whether this pseudo tree should be expanded or not */
			iter->skip_tree = iterator__dont_autoexpand(&iter->base);
			break;
2158 2159
		}

2160 2161
		iter->next_idx++;
		break;
2162 2163
	}

2164 2165 2166 2167 2168 2169
	iter->entry = (error == 0) ? entry : NULL;

	if (out)
		*out = iter->entry;

	return error;
2170 2171
}

2172 2173
static int index_iterator_advance_into(
	const git_index_entry **out, git_iterator *i)
2174
{
2175
	index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2176

2177
	if (! S_ISDIR(iter->tree_entry.mode)) {
Edward Thomson committed
2178 2179 2180
		if (out)
			*out = NULL;

2181
		return 0;
2182
	}
2183

2184 2185
	iter->skip_tree = false;
	return index_iterator_advance(out, i);
2186
}
2187

2188 2189 2190 2191
static int index_iterator_advance_over(
	const git_index_entry **out,
	git_iterator_status_t *status,
	git_iterator *i)
2192
{
2193
	index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2194 2195
	const git_index_entry *entry;
	int error;
2196

2197 2198
	if ((error = index_iterator_current(&entry, i)) < 0)
		return error;
2199

2200 2201
	if (S_ISDIR(entry->mode))
		index_iterator_skip_pseudotree(iter);
2202

2203 2204 2205
	*status = GIT_ITERATOR_STATUS_NORMAL;
	return index_iterator_advance(out, i);
}
2206

2207 2208 2209 2210
static void index_iterator_clear(index_iterator *iter)
{
	iterator_clear(&iter->base);
}
2211

2212 2213 2214 2215 2216 2217 2218
static int index_iterator_init(index_iterator *iter)
{
	iter->base.flags &= ~GIT_ITERATOR_FIRST_ACCESS;
	iter->next_idx = 0;
	iter->skip_tree = false;
	return 0;
}
2219

2220 2221
static int index_iterator_reset(git_iterator *i)
{
2222
	index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2223

2224 2225 2226
	index_iterator_clear(iter);
	return index_iterator_init(iter);
}
2227

2228
static void index_iterator_free(git_iterator *i)
2229
{
2230
	index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2231 2232

	git_index_snapshot_release(&iter->entries, iter->base.index);
2233
	git_buf_dispose(&iter->tree_buf);
2234 2235 2236
}

int git_iterator_for_index(
2237
	git_iterator **out,
2238 2239 2240 2241
	git_repository *repo,
	git_index  *index,
	git_iterator_options *options)
{
2242 2243
	index_iterator *iter;
	int error;
2244

2245 2246 2247 2248 2249 2250 2251 2252
	static git_iterator_callbacks callbacks = {
		index_iterator_current,
		index_iterator_advance,
		index_iterator_advance_into,
		index_iterator_advance_over,
		index_iterator_reset,
		index_iterator_free
	};
2253

2254
	*out = NULL;
2255

2256 2257
	if (index == NULL)
		return git_iterator_for_nothing(out, options);
2258

2259
	iter = git__calloc(1, sizeof(index_iterator));
2260
	GIT_ERROR_CHECK_ALLOC(iter);
2261

2262
	iter->base.type = GIT_ITERATOR_INDEX;
2263
	iter->base.cb = &callbacks;
2264

2265 2266 2267 2268
	if ((error = iterator_init_common(&iter->base, repo, index, options)) < 0 ||
		(error = git_index_snapshot_new(&iter->entries, index)) < 0 ||
		(error = index_iterator_init(iter)) < 0)
		goto on_error;
2269

2270 2271 2272
	git_vector_set_cmp(&iter->entries, iterator__ignore_case(&iter->base) ?
		git_index_entry_icmp : git_index_entry_cmp);
	git_vector_sort(&iter->entries);
2273

2274
	*out = &iter->base;
2275
	return 0;
2276 2277 2278 2279

on_error:
	git_iterator_free(&iter->base);
	return error;
2280
}
2281

2282

2283 2284
/* Iterator API */

Edward Thomson committed
2285 2286 2287 2288 2289 2290 2291 2292 2293
int git_iterator_reset_range(
	git_iterator *i, const char *start, const char *end)
{
	if (iterator_reset_range(i, start, end) < 0)
		return -1;

	return i->cb->reset(i);
}

2294
int git_iterator_set_ignore_case(git_iterator *i, bool ignore_case)
Edward Thomson committed
2295
{
2296
	GIT_ASSERT(!iterator__has_been_accessed(i));
Edward Thomson committed
2297
	iterator_set_ignore_case(i, ignore_case);
2298
	return 0;
Edward Thomson committed
2299
}
2300

2301 2302 2303 2304
void git_iterator_free(git_iterator *iter)
{
	if (iter == NULL)
		return;
2305

2306
	iter->cb->free(iter);
2307

2308 2309 2310
	git_vector_free(&iter->pathlist);
	git__free(iter->start);
	git__free(iter->end);
2311

2312
	memset(iter, 0, sizeof(*iter));
2313

2314 2315 2316
	git__free(iter);
}

2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345
int git_iterator_foreach(
	git_iterator *iterator,
	git_iterator_foreach_cb cb,
	void *data)
{
	const git_index_entry *iterator_item;
	int error = 0;

	if ((error = git_iterator_current(&iterator_item, iterator)) < 0)
		goto done;

	if ((error = cb(iterator_item, data)) != 0)
		goto done;

	while (true) {
		if ((error = git_iterator_advance(&iterator_item, iterator)) < 0)
			goto done;

		if ((error = cb(iterator_item, data)) != 0)
			goto done;
	}

done:
	if (error == GIT_ITEROVER)
		error = 0;

	return error;
}

2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360
int git_iterator_walk(
	git_iterator **iterators,
	size_t cnt,
	git_iterator_walk_cb cb,
	void *data)
{
	const git_index_entry **iterator_item;	/* next in each iterator */
	const git_index_entry **cur_items;		/* current path in each iter */
	const git_index_entry *first_match;
	size_t i, j;
	int error = 0;

	iterator_item = git__calloc(cnt, sizeof(git_index_entry *));
	cur_items = git__calloc(cnt, sizeof(git_index_entry *));

2361 2362
	GIT_ERROR_CHECK_ALLOC(iterator_item);
	GIT_ERROR_CHECK_ALLOC(cur_items);
2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422 2423

	/* Set up the iterators */
	for (i = 0; i < cnt; i++) {
		error = git_iterator_current(&iterator_item[i], iterators[i]);

		if (error < 0 && error != GIT_ITEROVER)
			goto done;
	}

	while (true) {
		for (i = 0; i < cnt; i++)
			cur_items[i] = NULL;

		first_match = NULL;

		/* Find the next path(s) to consume from each iterator */
		for (i = 0; i < cnt; i++) {
			if (iterator_item[i] == NULL)
				continue;

			if (first_match == NULL) {
				first_match = iterator_item[i];
				cur_items[i] = iterator_item[i];
			} else {
				int path_diff = git_index_entry_cmp(iterator_item[i], first_match);

				if (path_diff < 0) {
					/* Found an index entry that sorts before the one we're
					 * looking at.  Forget that we've seen the other and
					 * look at the other iterators for this path.
					 */
					for (j = 0; j < i; j++)
						cur_items[j] = NULL;

					first_match = iterator_item[i];
					cur_items[i] = iterator_item[i];
				} else if (path_diff == 0) {
					cur_items[i] = iterator_item[i];
				}
			}
		}

		if (first_match == NULL)
			break;

		if ((error = cb(cur_items, data)) != 0)
			goto done;

		/* Advance each iterator that participated */
		for (i = 0; i < cnt; i++) {
			if (cur_items[i] == NULL)
				continue;

			error = git_iterator_advance(&iterator_item[i], iterators[i]);

			if (error < 0 && error != GIT_ITEROVER)
				goto done;
		}
	}

done:
2424 2425
	git__free((git_index_entry **)iterator_item);
	git__free((git_index_entry **)cur_items);
2426

2427 2428 2429 2430 2431
	if (error == GIT_ITEROVER)
		error = 0;

	return error;
}