iterator.c 59.3 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
#include "path.h"
13

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

18 19 20 21 22 23
#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)
24
#define iterator__has_been_accessed(I) iterator__flag(I,FIRST_ACCESS)
25 26
#define iterator__honor_ignores(I)     iterator__flag(I,HONOR_IGNORES)
#define iterator__ignore_dot_git(I)    iterator__flag(I,IGNORE_DOT_GIT)
27
#define iterator__descend_symlinks(I)  iterator__flag(I,DESCEND_SYMLINKS)
28

29

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

Edward Thomson committed
37 38 39
	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;
40
	iter->entry_srch = ignore_case ? git_index_entry_isrch : git_index_entry_srch;
41 42

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

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

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

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

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

	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;
73
		iter->start_len = 0;
74 75 76 77 78
	}

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

Edward Thomson committed
83
static int iterator_reset_range(
84 85 86 87 88 89 90 91 92 93
	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
94
	if (git_vector_init(&iter->pathlist, pathlist->count, NULL) < 0)
95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110
		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,
111
	git_index *index,
112 113 114 115 116
	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;
117
	int precompose;
118 119 120
	int error;

	iter->repo = repo;
121
	iter->index = index;
122 123 124 125 126 127
	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;
128
	} else if (repo) {
129 130 131 132 133 134 135 136 137 138 139
		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;
140 141 142 143 144 145 146 147 148
	} 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) {

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

	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
162
	iterator_set_ignore_case(iter, ignore_case);
163 164 165 166 167 168 169
	return 0;
}

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

175 176
GIT_INLINE(bool) iterator_has_started(
	git_iterator *iter, const char *path, bool is_submodule)
177 178 179 180 181 182 183 184 185 186 187
{
	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);

188 189 190 191 192 193 194 195 196 197 198 199 200
	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;

201 202 203 204
	/* 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")
	 */
205
	if (path_len > 0 && path[path_len-1] == '/' &&
206 207 208
		iter->strncomp(path, iter->start, path_len) == 0)
		return true;

209
	return false;
210 211
}

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

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

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

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

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

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 276
	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 */
277
		else if (cmp < 0) {
278 279 280 281 282 283 284 285 286 287 288 289 290
			iter->pathlist_walk_idx++;
			continue;
		}

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

	return false;
}

291
typedef enum {
Edward Thomson committed
292
	ITERATOR_PATHLIST_NONE = 0,
293 294 295
	ITERATOR_PATHLIST_IS_FILE = 1,
	ITERATOR_PATHLIST_IS_DIR = 2,
	ITERATOR_PATHLIST_IS_PARENT = 3,
296
	ITERATOR_PATHLIST_FULL = 4
297 298 299 300 301 302 303 304 305
} 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
306 307 308 309 310
	if (iter->pathlist.length == 0)
		return ITERATOR_PATHLIST_FULL;

	git_vector_sort(&iter->pathlist);

311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333
	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 */
334
		GIT_ASSERT_WITH_RETVAL(p[path_len], ITERATOR_PATHLIST_NONE);
335 336 337 338 339 340 341 342 343 344 345 346 347 348

		/* 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
349
	return ITERATOR_PATHLIST_NONE;
350 351
}

352 353
/* Empty iterator */

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

	if (e)
		*e = NULL;

361
	return GIT_ITEROVER;
362 363
}

364 365 366 367 368 369
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
370
	return empty_iterator_noop(e, i);
371 372 373
}

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

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

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

389
int git_iterator_for_nothing(
390
	git_iterator **out,
391
	git_iterator_options *options)
392
{
393 394 395 396 397 398 399 400 401 402
	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
	};
403

404
	*out = NULL;
405

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

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

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

417
/* Tree iterator */
418

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

424 425
typedef struct {
	git_tree *tree;
426

427
	/* path to this particular frame (folder) */
428
	git_str path;
429

430 431 432 433 434
	/* 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;
435

436
	size_t next_idx;
437

438 439 440 441 442
	/* 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.
443
	 */
444
	git_vector similar_trees;
445
	git_array_t(git_str) similar_paths;
446
} tree_iterator_frame;
447 448

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

453
	git_index_entry entry;
454
	git_str entry_path;
455 456 457

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

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

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

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

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

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

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

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

498 499 500 501 502 503 504 505 506
	/* 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);
507

508
	return c;
509 510
}

511
static int tree_iterator_compute_path(
512
	git_str *out,
513
	tree_iterator_entry *entry)
514
{
515
	git_str_clear(out);
516

517
	if (entry->parent_path)
518
		git_str_joinpath(out, entry->parent_path, entry->tree_entry->filename);
519
	else
520
		git_str_puts(out, entry->tree_entry->filename);
521

522
	if (git_tree_entry__is_tree(entry->tree_entry))
523
		git_str_putc(out, '/');
524

525
	if (git_str_oom(out))
526
		return -1;
527

528
	return 0;
529 530
}

531 532 533 534
static int tree_iterator_frame_init(
	tree_iterator *iter,
	git_tree *tree,
	tree_iterator_entry *frame_entry)
535
{
536 537 538 539 540 541
	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;
542
	int error = 0;
543

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

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

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

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

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

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

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

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

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

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

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

587 588
	return error;
}
589

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

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

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

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

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

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

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

625
		memset(path, 0, sizeof(git_str));
626

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

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

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

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

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

		if (error)
			break;
647

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

	return error;
652 653
}

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

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

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

669 670 671 672 673 674 675
	/* 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);
676

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

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

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

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

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

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

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

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

	git_vector_free(&frame->similar_trees);

708
	git_str_dispose(&frame->path);
709 710

	return 0;
711 712
}

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

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

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

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

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

737
	frame->current = entry;
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;
743
	git_oid_cpy(&iter->entry.id, &tree_entry->oid);
744 745
}

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

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

753 754 755 756 757 758 759 760 761 762
	/* 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;
		}
763

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

769 770
			continue;
		}
771

772 773 774 775 776
		/* 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);
777

778 779 780 781
		/* 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++;
782

783 784 785 786 787 788 789
		/* 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;
790

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

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

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

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

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

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

813 814 815 816 817 818 819
			/* 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;
820
			}
821 822

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

		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;
	}
835 836

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

	return error;
}

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

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

853 854 855 856 857 858 859 860 861 862
	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.
	 */
863
	GIT_ASSERT(iterator__do_autoexpand(i) ^ (prev_entry != NULL));
864 865 866 867

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

869 870 871 872 873 874 875 876
		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);
877 878
}

879 880 881 882 883 884 885 886 887
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);
}

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

893
	git_array_clear(iter->frames);
894

895
	git_pool_clear(&iter->entry_pool);
896
	git_str_clear(&iter->entry_path);
897

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

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

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

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

	return 0;
912
}
913

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

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

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

926
	tree_iterator_clear(iter);
927

928
	git_tree_free(iter->root);
929
	git_str_dispose(&iter->entry_path);
930 931
}

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

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

	*out = NULL;
950 951

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

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

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

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

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

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

974 975 976 977 978 979
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;
980

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

	iter = (tree_iterator *)i;

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

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

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

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

	iter = (tree_iterator *)i;

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

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

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

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

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

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

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

	unsigned int dirload_flags;

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

1039 1040
	git_oid_t oid_type;

1041 1042
	git_array_t(filesystem_iterator_frame) frames;
	git_ignores ignores;
1043

1044 1045
	/* info about the current entry */
	git_index_entry entry;
1046
	git_str current_path;
1047
	int current_is_ignored;
1048

1049
	/* temporary buffer for advance_over */
1050
	git_str tmp_buf;
1051 1052 1053 1054 1055 1056 1057 1058
} 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;
1059 1060
}

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

1067 1068 1069 1070 1071 1072
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];
}
1073

1074 1075 1076 1077
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;
1078

1079 1080
	return git__strcmp(a->path, b->path);
}
1081

1082 1083 1084 1085
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;
1086

1087
	return git__strcasecmp(a->path, b->path);
1088 1089
}

1090 1091 1092 1093 1094 1095 1096 1097
#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
1098
static int filesystem_iterator_is_submodule(
1099
	bool *out, filesystem_iterator *iter, const char *path, size_t path_len)
1100
{
1101 1102
	bool is_submodule = false;
	int error;
1103

1104
	*out = false;
1105

1106 1107 1108
	/* first see if this path is a submodule in HEAD */
	if (iter->tree) {
		git_tree_entry *entry;
1109

1110
		error = git_tree_entry_bypath(&entry, iter->tree, path);
1111

1112 1113
		if (error < 0 && error != GIT_ENOTFOUND)
			return error;
1114

1115 1116 1117 1118 1119
		if (!error) {
			is_submodule = (entry->attr == GIT_FILEMODE_COMMIT);
			git_tree_entry_free(entry);
		}
	}
1120

1121
	if (!is_submodule && iter->base.index) {
1122
		size_t pos;
1123

1124 1125
		error = git_index_snapshot_find(&pos,
			&iter->index_snapshot, iter->base.entry_srch, path, path_len, 0);
1126

1127 1128
		if (error < 0 && error != GIT_ENOTFOUND)
			return error;
1129

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

1136
	*out = is_submodule;
1137 1138 1139
	return 0;
}

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

1148 1149 1150 1151 1152
	if (!iterator__honor_ignores(&iter->base))
		return;

	if (git_ignore__lookup(&new_frame->is_ignored,
			&iter->ignores, path, GIT_DIR_FLAG_TRUE) < 0) {
1153
		git_error_clear();
1154
		new_frame->is_ignored = GIT_IGNORE_NOTFOUND;
1155 1156
	}

1157 1158 1159
	/* if this is not the top level directory... */
	if (frame_entry) {
		const char *relative_path;
1160

1161
		previous_frame = filesystem_iterator_parent_frame(iter);
1162

1163 1164 1165 1166 1167 1168 1169 1170 1171
		/* 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);
	}
1172 1173
}

1174 1175
static void filesystem_iterator_frame_pop_ignores(
	filesystem_iterator *iter)
1176
{
1177 1178
	if (iterator__honor_ignores(&iter->base))
		git_ignore__pop_dir(&iter->ignores);
1179 1180
}

1181 1182 1183 1184 1185 1186 1187
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)
1188
{
1189 1190
	bool is_dir = 0;
	iterator_pathlist_search_t match = ITERATOR_PATHLIST_FULL;
1191

1192
	*is_dir_out = false;
Edward Thomson committed
1193
	*match_out = ITERATOR_PATHLIST_NONE;
1194

1195 1196
	if (iter->base.start_len) {
		int cmp = iter->base.strncomp(path, iter->base.start, path_len);
1197

1198 1199 1200 1201 1202 1203 1204
		/* 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;
1205

1206 1207
			else if (iter->base.start[path_len] != '\0')
				cmp = -1;
1208 1209
		}

1210 1211
		if (cmp < 0)
			return false;
1212
	}
1213

1214 1215
	if (iter->base.end_len) {
		int cmp = iter->base.strncomp(path, iter->base.end, iter->base.end_len);
1216

1217 1218
		if (cmp > 0)
			return false;
1219
	}
1220

1221 1222
	/* 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.
1223
	 */
1224 1225 1226 1227 1228 1229
	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);
1230

Edward Thomson committed
1231
		if (match == ITERATOR_PATHLIST_NONE)
1232
			return false;
1233

1234 1235 1236 1237
		/* 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;
1238 1239
	}

1240 1241 1242
	*is_dir_out = is_dir;
	*match_out = match;
	return true;
1243 1244
}

1245 1246
GIT_INLINE(bool) filesystem_iterator_is_dot_git(
	filesystem_iterator *iter, const char *path, size_t path_len)
1247
{
1248
	size_t len;
1249

1250 1251
	if (!iterator__ignore_dot_git(&iter->base))
		return false;
1252

1253 1254
	if ((len = path_len) < 4)
		return false;
1255

1256 1257
	if (path[len - 1] == '/')
		len--;
1258

1259 1260 1261 1262 1263
	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;
1264

1265
	return (len == 4 || path[len - 5] == '/');
1266 1267
}

1268 1269 1270 1271
static int filesystem_iterator_entry_hash(
	filesystem_iterator *iter,
	filesystem_iterator_entry *entry)
{
1272
	git_str fullpath = GIT_STR_INIT;
1273 1274 1275
	int error;

	if (S_ISDIR(entry->st.st_mode)) {
1276
		memset(&entry->id, 0, git_oid_size(iter->oid_type));
1277 1278 1279
		return 0;
	}

1280
	if (iter->base.type == GIT_ITERATOR_WORKDIR)
1281
		return git_repository_hashfile(&entry->id,
1282
			iter->base.repo, entry->path, GIT_OBJECT_BLOB, NULL);
1283

1284
	if (!(error = git_str_joinpath(&fullpath, iter->root, entry->path)) &&
1285
	    !(error = git_path_validate_str_length(iter->base.repo, &fullpath)))
1286
		error = git_odb__hashfile(&entry->id, fullpath.ptr, GIT_OBJECT_BLOB, iter->oid_type);
1287

1288
	git_str_dispose(&fullpath);
1289 1290 1291 1292 1293 1294
	return error;
}

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

	*out = NULL;
1306

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

	entry = git_pool_malloc(&frame->entry_pool, entry_size);
1315
	GIT_ERROR_CHECK_ALLOC(entry);
1316

1317 1318 1319 1320
	entry->path_len = path_len;
	entry->match = pathlist_match;
	memcpy(entry->path, path, path_len);
	memcpy(&entry->st, statbuf, sizeof(struct stat));
1321

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

1326
	entry->path[entry->path_len] = '\0';
1327

1328 1329 1330 1331 1332 1333 1334
	if (iter->base.flags & GIT_ITERATOR_INCLUDE_HASH)
		error = filesystem_iterator_entry_hash(iter, entry);

	if (!error)
		*out = entry;

	return error;
1335
}
1336

1337 1338 1339
static int filesystem_iterator_frame_push(
	filesystem_iterator *iter,
	filesystem_iterator_entry *frame_entry)
1340
{
1341
	filesystem_iterator_frame *new_frame = NULL;
1342
	git_fs_path_diriter diriter = GIT_FS_PATH_DIRITER_INIT;
1343
	git_str root = GIT_STR_INIT;
1344 1345 1346 1347 1348
	const char *path;
	filesystem_iterator_entry *entry;
	struct stat statbuf;
	size_t path_len;
	int error;
1349

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

1356
	new_frame = git_array_alloc(iter->frames);
1357
	GIT_ERROR_CHECK_ALLOC(new_frame);
1358

1359
	memset(new_frame, 0, sizeof(filesystem_iterator_frame));
1360

1361
	if (frame_entry)
1362
		git_str_joinpath(&root, iter->root, frame_entry->path);
1363
	else
1364
		git_str_puts(&root, iter->root);
1365

1366
	if (git_str_oom(&root) ||
1367
	    git_path_validate_str_length(iter->base.repo, &root) < 0) {
1368 1369 1370 1371 1372
		error = -1;
		goto done;
	}

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

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

1381 1382 1383 1384 1385 1386
	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;

1387 1388
	if ((error = git_pool_init(&new_frame->entry_pool, 1)) < 0)
		goto done;
1389 1390 1391 1392

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

1393
	while ((error = git_fs_path_diriter_next(&diriter)) == 0) {
1394
		iterator_pathlist_search_t pathlist_match = ITERATOR_PATHLIST_FULL;
1395
		git_str path_str = GIT_STR_INIT;
1396 1397
		bool dir_expected = false;

1398 1399 1400 1401 1402 1403 1404
		if ((error = git_fs_path_diriter_fullpath(&path, &path_len, &diriter)) < 0)
			goto done;

		path_str.ptr = (char *)path;
		path_str.size = path_len;

		if ((error = git_path_validate_str_length(iter->base.repo, &path_str)) < 0)
1405 1406
			goto done;

1407
		GIT_ASSERT(path_len > iter->root_len);
1408 1409

		/* remove the prefix if requested */
1410 1411
		path += iter->root_len;
		path_len -= iter->root_len;
1412

1413 1414 1415 1416
		/* 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)
1417
		 */
1418 1419
		if (!filesystem_iterator_examine_path(&dir_expected, &pathlist_match,
			iter, frame_entry, path, path_len))
1420 1421
			continue;

1422 1423
		/* 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.
1424 1425
		 */

1426
		if ((error = git_fs_path_diriter_stat(&statbuf, &diriter)) < 0) {
1427 1428 1429
			/* file was removed between readdir and lstat */
			if (error == GIT_ENOTFOUND)
				continue;
1430

1431 1432 1433
			/* treat the file as unreadable */
			memset(&statbuf, 0, sizeof(statbuf));
			statbuf.st_mode = GIT_FILEMODE_UNREADABLE;
1434

1435 1436
			error = 0;
		}
1437

1438
		iter->base.stat_calls++;
1439

1440 1441 1442 1443 1444 1445
		/* 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;
1446

1447
		if (filesystem_iterator_is_dot_git(iter, path, path_len))
1448
			continue;
1449 1450 1451 1452 1453

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

Edward Thomson committed
1454 1455
			if ((error = filesystem_iterator_is_submodule(&submodule,
					iter, path, path_len)) < 0)
1456 1457 1458 1459
				goto done;

			if (submodule)
				statbuf.st_mode = GIT_FILEMODE_COMMIT;
1460 1461
		}

1462
		/* Ensure that the pathlist entry lines up with what we expected */
1463
		else if (dir_expected)
1464 1465
			continue;

1466 1467 1468
		if ((error = filesystem_iterator_entry_init(&entry,
			iter, new_frame, path, path_len, &statbuf, pathlist_match)) < 0)
			goto done;
1469 1470

		git_vector_insert(&new_frame->entries, entry);
1471 1472 1473 1474 1475 1476
	}

	if (error == GIT_ITEROVER)
		error = 0;

	/* sort now that directory suffix is added */
1477
	git_vector_sort(&new_frame->entries);
1478 1479

done:
1480 1481 1482
	if (error < 0)
		git_array_pop(iter->frames);

1483
	git_str_dispose(&root);
1484
	git_fs_path_diriter_free(&diriter);
1485 1486 1487
	return error;
}

1488
GIT_INLINE(int) filesystem_iterator_frame_pop(filesystem_iterator *iter)
1489
{
1490
	filesystem_iterator_frame *frame;
1491

1492
	GIT_ASSERT(iter->frames.size);
1493

1494 1495
	frame = git_array_pop(iter->frames);
	filesystem_iterator_frame_pop_ignores(iter);
1496

1497 1498
	git_pool_clear(&frame->entry_pool);
	git_vector_free(&frame->entries);
1499 1500

	return 0;
1501
}
1502

1503 1504 1505 1506
static void filesystem_iterator_set_current(
	filesystem_iterator *iter,
	filesystem_iterator_entry *entry)
{
1507 1508 1509 1510 1511 1512 1513 1514 1515
	/*
	 * 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;
1516

1517
#if defined(GIT_USE_NSEC)
1518
	iter->entry.ctime.nanoseconds = entry->st.st_ctime_nsec;
1519
	iter->entry.mtime.nanoseconds = entry->st.st_mtime_nsec;
1520 1521 1522
#else
	iter->entry.ctime.nanoseconds = 0;
	iter->entry.mtime.nanoseconds = 0;
1523
#endif
1524

1525 1526 1527 1528 1529
	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;
1530
	iter->entry.file_size = (uint32_t)entry->st.st_size;
1531

1532 1533
	if (iter->base.flags & GIT_ITERATOR_INCLUDE_HASH)
		git_oid_cpy(&iter->entry.id, &entry->id);
Edward Thomson committed
1534
	else
1535
		git_oid_clear(&iter->entry.id, iter->oid_type);
1536

1537
	iter->entry.path = entry->path;
1538

1539
	iter->current_is_ignored = GIT_IGNORE_UNCHECKED;
1540 1541
}

1542 1543
static int filesystem_iterator_current(
	const git_index_entry **out, git_iterator *i)
1544
{
1545
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1546

1547 1548
	if (!iterator__has_been_accessed(i))
		return iter->base.cb->advance(out, i);
1549

1550 1551 1552 1553
	if (!iter->frames.size) {
		*out = NULL;
		return GIT_ITEROVER;
	}
1554

1555 1556
	*out = &iter->entry;
	return 0;
1557 1558
}

1559 1560 1561 1562
static int filesystem_iterator_is_dir(
	bool *is_dir,
	const filesystem_iterator *iter,
	const filesystem_iterator_entry *entry)
1563 1564
{
	struct stat st;
1565
	git_str fullpath = GIT_STR_INIT;
1566
	int error = 0;
1567

1568 1569 1570 1571 1572 1573 1574 1575 1576
	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;
	}
1577

1578
	if ((error = git_str_joinpath(&fullpath, iter->root, entry->path)) < 0 ||
1579
	    (error = git_path_validate_str_length(iter->base.repo, &fullpath)) < 0 ||
1580
	    (error = p_stat(fullpath.ptr, &st)) < 0)
1581 1582 1583 1584 1585
		goto done;

	*is_dir = S_ISDIR(st.st_mode);

done:
1586
	git_str_dispose(&fullpath);
1587
	return error;
1588 1589
}

1590 1591
static int filesystem_iterator_advance(
	const git_index_entry **out, git_iterator *i)
1592
{
1593
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1594
	bool is_dir;
1595 1596
	int error = 0;

1597
	iter->base.flags |= GIT_ITERATOR_FIRST_ACCESS;
1598

1599 1600 1601 1602
	/* examine filesystem entries until we find the next one to return */
	while (true) {
		filesystem_iterator_frame *frame;
		filesystem_iterator_entry *entry;
1603

1604 1605 1606 1607
		if ((frame = filesystem_iterator_current_frame(iter)) == NULL) {
			error = GIT_ITEROVER;
			break;
		}
1608

1609 1610 1611 1612 1613
		/* no more entries in this frame.  pop the frame out */
		if (frame->next_idx == frame->entries.length) {
			filesystem_iterator_frame_pop(iter);
			continue;
		}
1614

1615 1616 1617
		/* we have more entries in the current frame, that's our next entry */
		entry = frame->entries.contents[frame->next_idx];
		frame->next_idx++;
1618

1619 1620 1621 1622
		if ((error = filesystem_iterator_is_dir(&is_dir, iter, entry)) < 0)
			break;

		if (is_dir) {
1623 1624
			if (iterator__do_autoexpand(iter)) {
				error = filesystem_iterator_frame_push(iter, entry);
1625

1626 1627 1628 1629 1630 1631 1632 1633
				/* 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;
			}
1634

1635 1636 1637
			if (!iterator__include_trees(iter))
				continue;
		}
1638

1639 1640
		filesystem_iterator_set_current(iter, entry);
		break;
1641
	}
1642 1643 1644 1645 1646

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

	return error;
1647
}
1648

1649 1650
static int filesystem_iterator_advance_into(
	const git_index_entry **out, git_iterator *i)
1651
{
1652
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1653 1654
	filesystem_iterator_frame *frame;
	filesystem_iterator_entry *prev_entry;
1655 1656
	int error;

1657 1658
	if (out)
		*out = NULL;
1659

1660 1661
	if ((frame = filesystem_iterator_current_frame(iter)) == NULL)
		return GIT_ITEROVER;
1662

1663 1664
	/* get the last seen entry */
	prev_entry = filesystem_iterator_current_entry(frame);
1665

1666 1667 1668 1669
	/* 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.
	 */
1670
	GIT_ASSERT(iterator__do_autoexpand(i) ^ (prev_entry != NULL));
1671

1672 1673 1674 1675
	if (prev_entry) {
		if (prev_entry->st.st_mode != GIT_FILEMODE_COMMIT &&
			!S_ISDIR(prev_entry->st.st_mode))
			return 0;
1676

1677
		if ((error = filesystem_iterator_frame_push(iter, prev_entry)) < 0)
1678 1679 1680
			return error;
	}

1681 1682 1683 1684
	/* we've advanced into the directory in question, let advance
	 * find the first entry
	 */
	return filesystem_iterator_advance(out, i);
1685 1686
}

1687
int git_iterator_current_workdir_path(git_str **out, git_iterator *i)
1688
{
1689
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1690
	const git_index_entry *entry;
1691

1692 1693
	if (i->type != GIT_ITERATOR_FS &&
		i->type != GIT_ITERATOR_WORKDIR) {
1694 1695 1696
		*out = NULL;
		return 0;
	}
1697

1698
	git_str_truncate(&iter->current_path, iter->root_len);
1699

1700
	if (git_iterator_current(&entry, i) < 0 ||
1701
		git_str_puts(&iter->current_path, entry->path) < 0)
1702
		return -1;
1703

1704 1705 1706
	*out = &iter->current_path;
	return 0;
}
1707

1708 1709 1710 1711 1712 1713 1714 1715 1716 1717
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
1718 1719
}

1720
static void filesystem_iterator_update_ignored(filesystem_iterator *iter)
1721
{
1722 1723
	filesystem_iterator_frame *frame;
	git_dir_flag dir_flag = entry_dir_flag(&iter->entry);
1724

1725 1726
	if (git_ignore__lookup(&iter->current_is_ignored,
			&iter->ignores, iter->entry.path, dir_flag) < 0) {
1727
		git_error_clear();
1728 1729
		iter->current_is_ignored = GIT_IGNORE_NOTFOUND;
	}
1730

1731 1732 1733 1734 1735
	/* 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;
	}
1736 1737
}

1738 1739
GIT_INLINE(bool) filesystem_iterator_current_is_ignored(
	filesystem_iterator *iter)
1740
{
1741 1742
	if (iter->current_is_ignored == GIT_IGNORE_UNCHECKED)
		filesystem_iterator_update_ignored(iter);
1743

1744
	return (iter->current_is_ignored == GIT_IGNORE_TRUE);
1745 1746
}

1747
bool git_iterator_current_is_ignored(git_iterator *i)
1748
{
1749 1750
	filesystem_iterator *iter = NULL;

1751
	if (i->type != GIT_ITERATOR_WORKDIR)
1752
		return false;
1753

1754 1755 1756
	iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);

	return filesystem_iterator_current_is_ignored(iter);
1757
}
1758

1759 1760
bool git_iterator_current_tree_is_ignored(git_iterator *i)
{
1761
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1762
	filesystem_iterator_frame *frame;
1763

1764
	if (i->type != GIT_ITERATOR_WORKDIR)
1765
		return false;
1766

1767 1768 1769
	frame = filesystem_iterator_current_frame(iter);
	return (frame->is_ignored == GIT_IGNORE_TRUE);
}
1770

1771 1772 1773 1774 1775
static int filesystem_iterator_advance_over(
	const git_index_entry **out,
	git_iterator_status_t *status,
	git_iterator *i)
{
1776
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1777 1778 1779 1780 1781
	filesystem_iterator_frame *current_frame;
	filesystem_iterator_entry *current_entry;
	const git_index_entry *entry = NULL;
	const char *base;
	int error = 0;
1782

1783 1784
	*out = NULL;
	*status = GIT_ITERATOR_STATUS_NORMAL;
1785

1786
	GIT_ASSERT(iterator__has_been_accessed(i));
1787

1788
	current_frame = filesystem_iterator_current_frame(iter);
1789 1790
	GIT_ASSERT(current_frame);

1791
	current_entry = filesystem_iterator_current_entry(current_frame);
1792
	GIT_ASSERT(current_entry);
1793

1794 1795
	if ((error = git_iterator_current(&entry, i)) < 0)
		return error;
1796

1797 1798 1799
	if (!S_ISDIR(entry->mode)) {
		if (filesystem_iterator_current_is_ignored(iter))
			*status = GIT_ITERATOR_STATUS_IGNORED;
1800

1801
		return filesystem_iterator_advance(out, i);
1802
	}
1803

1804 1805
	git_str_clear(&iter->tmp_buf);
	if ((error = git_str_puts(&iter->tmp_buf, entry->path)) < 0)
1806
		return error;
1807

1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821
	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;
1822

1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833
	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;
1834

1835 1836 1837
			/* this directory disappeared, ignore it */
			else if (error == GIT_ENOTFOUND)
				error = 0;
1838

1839 1840 1841
			/* a real error occurred */
			else
				break;
1842
		} else {
1843 1844 1845
			/* we found a non-ignored item, treat parent as untracked */
			*status = GIT_ITERATOR_STATUS_NORMAL;
			break;
1846
		}
1847 1848 1849 1850 1851 1852 1853 1854 1855

		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;
1856 1857
	}

1858 1859 1860
	if (!error)
		*out = entry;

1861 1862 1863
	return error;
}

1864
static void filesystem_iterator_clear(filesystem_iterator *iter)
1865
{
1866 1867
	while (iter->frames.size)
		filesystem_iterator_frame_pop(iter);
1868

1869 1870
	git_array_clear(iter->frames);
	git_ignore__free(&iter->ignores);
1871

1872
	git_str_dispose(&iter->tmp_buf);
1873

1874
	iterator_clear(&iter->base);
1875
}
1876

1877
static int filesystem_iterator_init(filesystem_iterator *iter)
1878
{
1879
	int error;
1880

1881 1882 1883 1884
	if (iterator__honor_ignores(&iter->base) &&
		(error = git_ignore__for_path(iter->base.repo,
			".gitignore", &iter->ignores)) < 0)
		return error;
1885

1886 1887
	if ((error = filesystem_iterator_frame_push(iter, NULL)) < 0)
		return error;
1888

1889
	iter->base.flags &= ~GIT_ITERATOR_FIRST_ACCESS;
1890

1891
	return 0;
1892 1893
}

1894
static int filesystem_iterator_reset(git_iterator *i)
1895
{
1896
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1897

1898 1899 1900
	filesystem_iterator_clear(iter);
	return filesystem_iterator_init(iter);
}
1901

1902 1903
static void filesystem_iterator_free(git_iterator *i)
{
1904
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1905
	git__free(iter->root);
1906
	git_str_dispose(&iter->current_path);
1907
	git_tree_free(iter->tree);
1908 1909
	if (iter->index)
		git_index_snapshot_release(&iter->index_snapshot, iter->index);
1910
	filesystem_iterator_clear(iter);
1911 1912
}

1913 1914 1915 1916 1917 1918
static int iterator_for_filesystem(
	git_iterator **out,
	git_repository *repo,
	const char *root,
	git_index *index,
	git_tree *tree,
1919
	git_iterator_t type,
1920
	git_iterator_options *options)
1921
{
1922 1923 1924
	filesystem_iterator *iter;
	size_t root_len;
	int error;
1925

1926 1927 1928 1929 1930 1931 1932 1933
	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
	};
1934

1935
	*out = NULL;
1936

1937 1938
	if (root == NULL)
		return git_iterator_for_nothing(out, options);
1939

1940
	iter = git__calloc(1, sizeof(filesystem_iterator));
1941
	GIT_ERROR_CHECK_ALLOC(iter);
1942

1943 1944 1945
	iter->base.type = type;
	iter->base.cb = &callbacks;

1946
	root_len = strlen(root);
1947

1948
	iter->root = git__malloc(root_len+2);
1949
	GIT_ERROR_CHECK_ALLOC(iter->root);
1950

1951
	memcpy(iter->root, root, root_len);
1952

1953 1954 1955
	if (root_len == 0 || root[root_len-1] != '/') {
		iter->root[root_len] = '/';
		root_len++;
1956
	}
1957 1958
	iter->root[root_len] = '\0';
	iter->root_len = root_len;
1959

1960
	if ((error = git_str_puts(&iter->current_path, iter->root)) < 0)
1961
		goto on_error;
1962

1963
	if ((error = iterator_init_common(&iter->base, repo, index, options)) < 0)
1964 1965 1966 1967 1968
		goto on_error;

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

1969
	if (index &&
1970 1971 1972
		(error = git_index_snapshot_new(&iter->index_snapshot, index)) < 0)
		goto on_error;

1973
	iter->index = index;
1974
	iter->dirload_flags =
1975 1976
		(iterator__ignore_case(&iter->base) ?
			GIT_FS_PATH_DIR_IGNORE_CASE : 0) |
1977
		(iterator__flag(&iter->base, PRECOMPOSE_UNICODE) ?
1978
			GIT_FS_PATH_DIR_PRECOMPOSE_UNICODE : 0);
1979

1980 1981
	iter->oid_type = options->oid_type;

1982 1983
	if ((error = filesystem_iterator_init(iter)) < 0)
		goto on_error;
1984

1985
	*out = &iter->base;
1986
	return 0;
1987 1988 1989 1990

on_error:
	git_iterator_free(&iter->base);
	return error;
1991 1992
}

1993 1994 1995
int git_iterator_for_filesystem(
	git_iterator **out,
	const char *root,
1996
	git_iterator_options *given_opts)
1997
{
1998 1999 2000 2001 2002
	git_iterator_options options = GIT_ITERATOR_OPTIONS_INIT;

	if (given_opts)
		memcpy(&options, given_opts, sizeof(git_iterator_options));

2003
	return iterator_for_filesystem(out,
2004
		NULL, root, NULL, NULL, GIT_ITERATOR_FS, &options);
2005 2006
}

2007
int git_iterator_for_workdir_ext(
2008
	git_iterator **out,
2009
	git_repository *repo,
2010
	const char *repo_workdir,
2011 2012
	git_index *index,
	git_tree *tree,
2013
	git_iterator_options *given_opts)
2014
{
2015
	git_iterator_options options = GIT_ITERATOR_OPTIONS_INIT;
2016

2017 2018 2019
	if (!repo_workdir) {
		if (git_repository__ensure_not_bare(repo, "scan working directory") < 0)
			return GIT_EBAREREPO;
2020

2021
		repo_workdir = git_repository_workdir(repo);
2022 2023
	}

2024 2025 2026
	/* upgrade to a workdir iterator, adding necessary internal flags */
	if (given_opts)
		memcpy(&options, given_opts, sizeof(git_iterator_options));
2027

2028 2029
	options.flags |= GIT_ITERATOR_HONOR_IGNORES |
		GIT_ITERATOR_IGNORE_DOT_GIT;
2030

2031 2032 2033 2034 2035 2036
	if (!options.oid_type)
		options.oid_type = repo->oid_type;
	else if (options.oid_type != repo->oid_type)
		git_error_set(GIT_ERROR_INVALID,
			"specified object ID type does not match repository object ID type");

2037
	return iterator_for_filesystem(out,
2038
		repo, repo_workdir, index, tree, GIT_ITERATOR_WORKDIR, &options);
2039 2040
}

2041

2042
/* Index iterator */
2043

2044

2045 2046 2047
typedef struct {
	git_iterator base;
	git_vector entries;
2048 2049 2050
	size_t next_idx;

	/* the pseudotree entry */
2051
	git_index_entry tree_entry;
2052
	git_str tree_buf;
2053 2054 2055
	bool skip_tree;

	const git_index_entry *entry;
2056
} index_iterator;
2057

2058 2059
static int index_iterator_current(
	const git_index_entry **out, git_iterator *i)
2060
{
2061
	index_iterator *iter = (index_iterator *)i;
2062

2063 2064 2065 2066 2067 2068
	if (!iterator__has_been_accessed(i))
		return iter->base.cb->advance(out, i);

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

2071 2072
	*out = iter->entry;
	return 0;
2073 2074
}

2075 2076 2077 2078
static bool index_iterator_create_pseudotree(
	const git_index_entry **out,
	index_iterator *iter,
	const char *path)
2079
{
2080 2081
	const char *prev_path, *relative_path, *dirsep;
	size_t common_len;
2082

2083
	prev_path = iter->entry ? iter->entry->path : "";
2084

2085
	/* determine if the new path is in a different directory from the old */
2086
	common_len = git_fs_path_common_dirlen(prev_path, path);
2087
	relative_path = path + common_len;
2088

2089 2090
	if ((dirsep = strchr(relative_path, '/')) == NULL)
		return false;
2091

2092 2093
	git_str_clear(&iter->tree_buf);
	git_str_put(&iter->tree_buf, path, (dirsep - path) + 1);
2094

2095 2096
	iter->tree_entry.mode = GIT_FILEMODE_TREE;
	iter->tree_entry.path = iter->tree_buf.ptr;
2097

2098 2099
	*out = &iter->tree_entry;
	return true;
2100 2101
}

2102
static int index_iterator_skip_pseudotree(index_iterator *iter)
2103
{
2104 2105
	GIT_ASSERT(iterator__has_been_accessed(&iter->base));
	GIT_ASSERT(S_ISDIR(iter->entry->mode));
2106

2107 2108
	while (true) {
		const git_index_entry *next_entry = NULL;
2109

2110 2111
		if (++iter->next_idx >= iter->entries.length)
			return GIT_ITEROVER;
2112

2113
		next_entry = iter->entries.contents[iter->next_idx];
2114

2115 2116 2117 2118
		if (iter->base.strncomp(iter->tree_buf.ptr, next_entry->path,
			iter->tree_buf.size) != 0)
			break;
	}
2119

2120
	iter->skip_tree = false;
2121
	return 0;
2122 2123
}

2124 2125
static int index_iterator_advance(
	const git_index_entry **out, git_iterator *i)
2126
{
2127
	index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2128
	const git_index_entry *entry = NULL;
2129
	bool is_submodule;
2130
	int error = 0;
2131

2132
	iter->base.flags |= GIT_ITERATOR_FIRST_ACCESS;
2133

2134 2135 2136 2137 2138
	while (true) {
		if (iter->next_idx >= iter->entries.length) {
			error = GIT_ITEROVER;
			break;
		}
2139

2140 2141 2142 2143 2144
		/* we were not asked to expand this pseudotree.  advance over it. */
		if (iter->skip_tree) {
			index_iterator_skip_pseudotree(iter);
			continue;
		}
2145

2146
		entry = iter->entries.contents[iter->next_idx];
2147
		is_submodule = S_ISGITLINK(entry->mode);
2148

2149
		if (!iterator_has_started(&iter->base, entry->path, is_submodule)) {
2150 2151 2152
			iter->next_idx++;
			continue;
		}
2153

2154
		if (iterator_has_ended(&iter->base, entry->path)) {
2155 2156 2157
			error = GIT_ITEROVER;
			break;
		}
2158

2159 2160 2161 2162 2163
		/* 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;
		}
2164

2165 2166 2167 2168 2169 2170
		/* 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;
		}
2171

2172 2173 2174 2175 2176 2177 2178
		/* 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)) {
2179

2180 2181 2182
			/* Note whether this pseudo tree should be expanded or not */
			iter->skip_tree = iterator__dont_autoexpand(&iter->base);
			break;
2183 2184
		}

2185 2186
		iter->next_idx++;
		break;
2187 2188
	}

2189 2190 2191 2192 2193 2194
	iter->entry = (error == 0) ? entry : NULL;

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

	return error;
2195 2196
}

2197 2198
static int index_iterator_advance_into(
	const git_index_entry **out, git_iterator *i)
2199
{
2200
	index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2201

2202
	if (! S_ISDIR(iter->tree_entry.mode)) {
Edward Thomson committed
2203 2204 2205
		if (out)
			*out = NULL;

2206
		return 0;
2207
	}
2208

2209 2210
	iter->skip_tree = false;
	return index_iterator_advance(out, i);
2211
}
2212

2213 2214 2215 2216
static int index_iterator_advance_over(
	const git_index_entry **out,
	git_iterator_status_t *status,
	git_iterator *i)
2217
{
2218
	index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2219 2220
	const git_index_entry *entry;
	int error;
2221

2222 2223
	if ((error = index_iterator_current(&entry, i)) < 0)
		return error;
2224

2225 2226
	if (S_ISDIR(entry->mode))
		index_iterator_skip_pseudotree(iter);
2227

2228 2229 2230
	*status = GIT_ITERATOR_STATUS_NORMAL;
	return index_iterator_advance(out, i);
}
2231

2232 2233 2234 2235
static void index_iterator_clear(index_iterator *iter)
{
	iterator_clear(&iter->base);
}
2236

2237 2238 2239 2240 2241 2242 2243
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;
}
2244

2245 2246
static int index_iterator_reset(git_iterator *i)
{
2247
	index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2248

2249 2250 2251
	index_iterator_clear(iter);
	return index_iterator_init(iter);
}
2252

2253
static void index_iterator_free(git_iterator *i)
2254
{
2255
	index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2256 2257

	git_index_snapshot_release(&iter->entries, iter->base.index);
2258
	git_str_dispose(&iter->tree_buf);
2259 2260 2261
}

int git_iterator_for_index(
2262
	git_iterator **out,
2263 2264 2265 2266
	git_repository *repo,
	git_index  *index,
	git_iterator_options *options)
{
2267 2268
	index_iterator *iter;
	int error;
2269

2270 2271 2272 2273 2274 2275 2276 2277
	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
	};
2278

2279
	*out = NULL;
2280

2281 2282
	if (index == NULL)
		return git_iterator_for_nothing(out, options);
2283

2284
	iter = git__calloc(1, sizeof(index_iterator));
2285
	GIT_ERROR_CHECK_ALLOC(iter);
2286

2287
	iter->base.type = GIT_ITERATOR_INDEX;
2288
	iter->base.cb = &callbacks;
2289

2290 2291 2292 2293
	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;
2294

2295 2296 2297
	git_vector_set_cmp(&iter->entries, iterator__ignore_case(&iter->base) ?
		git_index_entry_icmp : git_index_entry_cmp);
	git_vector_sort(&iter->entries);
2298

2299
	*out = &iter->base;
2300
	return 0;
2301 2302 2303 2304

on_error:
	git_iterator_free(&iter->base);
	return error;
2305
}
2306

2307

2308 2309
/* Iterator API */

Edward Thomson committed
2310 2311 2312 2313 2314 2315 2316 2317 2318
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);
}

2319
int git_iterator_set_ignore_case(git_iterator *i, bool ignore_case)
Edward Thomson committed
2320
{
2321
	GIT_ASSERT(!iterator__has_been_accessed(i));
Edward Thomson committed
2322
	iterator_set_ignore_case(i, ignore_case);
2323
	return 0;
Edward Thomson committed
2324
}
2325

2326 2327 2328 2329
void git_iterator_free(git_iterator *iter)
{
	if (iter == NULL)
		return;
2330

2331
	iter->cb->free(iter);
2332

2333 2334 2335
	git_vector_free(&iter->pathlist);
	git__free(iter->start);
	git__free(iter->end);
2336

2337
	memset(iter, 0, sizeof(*iter));
2338

2339 2340 2341
	git__free(iter);
}

2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370
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;
}

2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385
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 *));

2386 2387
	GIT_ERROR_CHECK_ALLOC(iterator_item);
	GIT_ERROR_CHECK_ALLOC(cur_items);
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 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448

	/* 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:
2449 2450
	git__free((git_index_entry **)iterator_item);
	git__free((git_index_entry **)cur_items);
2451

2452 2453 2454 2455 2456
	if (error == GIT_ITEROVER)
		error = 0;

	return error;
}