iterator.c 58.2 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 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) {

		if (git_repository__cvar(&precompose, repo, GIT_CVAR_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 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347
	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 */
		assert(p[path_len]);

		/* 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 409 410
	iter->base.type = GIT_ITERATOR_TYPE_EMPTY;
	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
	memset(new_frame, 0, sizeof(tree_iterator_frame));
547

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

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

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

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

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

565 566
	git_array_foreach(dup->entries, i, tree_entry) {
		new_entry = git_pool_malloc(&iter->entry_pool, 1);
567
		GIT_ERROR_CHECK_ALLOC(new_entry);
568

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

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

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

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

585 586
	return error;
}
587

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

594 595 596 597 598
GIT_INLINE(int) tree_iterator_frame_push_neighbors(
	tree_iterator *iter,
	tree_iterator_frame *parent_frame,
	tree_iterator_frame *frame,
	const char *filename)
599
{
600 601 602 603 604 605
	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;
606

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

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

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

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

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

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

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

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

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

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

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

		if (error)
			break;
645

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

	return error;
650 651
}

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

659 660 661 662
	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;
663

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

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

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

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

687
	assert(iter->frames.size);
688

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

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

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

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

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

	git_vector_free(&frame->similar_trees);

706
	git_buf_dispose(&frame->path);
707 708
}

709 710
static int tree_iterator_current(
	const git_index_entry **out, git_iterator *i)
711
{
712
	tree_iterator *iter = (tree_iterator *)i;
713

714 715
	if (!iterator__has_been_accessed(i))
		return iter->base.cb->advance(out, i);
716

717 718
	if (!iter->frames.size) {
		*out = NULL;
719
		return GIT_ITEROVER;
720
	}
721

722
	*out = &iter->entry;
723
	return 0;
724 725
}

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

733
	frame->current = entry;
734

735 736 737 738 739
	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);
740 741
}

742
static int tree_iterator_advance(const git_index_entry **out, git_iterator *i)
743
{
744 745
	tree_iterator *iter = (tree_iterator *)i;
	int error = 0;
746

747
	iter->base.flags |= GIT_ITERATOR_FIRST_ACCESS;
748

749 750 751 752 753 754 755 756 757 758
	/* 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;
		}
759

760 761 762 763 764
		/* no more entries in this frame.  pop the frame out */
		if (frame->next_idx == frame->entries.length) {
			tree_iterator_frame_pop(iter);
			continue;
		}
765

766 767 768 769 770
		/* 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);
771

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

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

785 786
		if ((error = tree_iterator_compute_path(&iter->entry_path, entry)) < 0)
			break;
787

788
		/* if this path is before our start, advance over this entry */
789
		if (!iterator_has_started(&iter->base, iter->entry_path.ptr, false))
790
			continue;
791

792
		/* if this path is after our end, stop */
793
		if (iterator_has_ended(&iter->base, iter->entry_path.ptr)) {
794 795 796
			error = GIT_ITEROVER;
			break;
		}
797

798
		/* if we have a list of paths we're interested in, examine it */
799
		if (!iterator_pathlist_next_is(&iter->base, iter->entry_path.ptr))
800
			continue;
801

802
		is_tree = git_tree_entry__is_tree(entry->tree_entry);
803

804 805
		/* if we are *not* including trees then advance over this entry */
		if (is_tree && !iterator__include_trees(iter)) {
806

807 808 809 810 811 812 813
			/* 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;
814
			}
815 816

			continue;
817
		}
818 819 820 821 822 823 824 825 826 827 828

		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;
	}
829 830

	if (out)
831
		*out = (error == 0) ? &iter->entry : NULL;
832 833 834 835

	return error;
}

836 837
static int tree_iterator_advance_into(
	const git_index_entry **out, git_iterator *i)
838
{
839 840 841 842
	tree_iterator *iter = (tree_iterator *)i;
    tree_iterator_frame *frame;
	tree_iterator_entry *prev_entry;
	int error;
843

844 845
	if (out)
		*out = NULL;
846

847 848 849 850 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.
	 */
	assert(iterator__do_autoexpand(i) ^ (prev_entry != NULL));

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

863 864 865 866 867 868 869 870
		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);
871 872
}

873 874 875 876 877 878 879 880 881
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);
}

882
static void tree_iterator_clear(tree_iterator *iter)
883
{
884 885
	while (iter->frames.size)
		tree_iterator_frame_pop(iter);
886

887
	git_array_clear(iter->frames);
888

889 890
	git_pool_clear(&iter->entry_pool);
	git_buf_clear(&iter->entry_path);
891

892
	iterator_clear(&iter->base);
893 894
}

895
static int tree_iterator_init(tree_iterator *iter)
896
{
897 898 899
	int error;

	git_pool_init(&iter->entry_pool, sizeof(tree_iterator_entry));
900

901 902
	if ((error = tree_iterator_frame_init(iter, iter->root, NULL)) < 0)
		return error;
903

904 905 906
	iter->base.flags &= ~GIT_ITERATOR_FIRST_ACCESS;

	return 0;
907
}
908

909
static int tree_iterator_reset(git_iterator *i)
910
{
911
	tree_iterator *iter = (tree_iterator *)i;
912

913 914
	tree_iterator_clear(iter);
	return tree_iterator_init(iter);
915 916
}

917
static void tree_iterator_free(git_iterator *i)
918
{
919
	tree_iterator *iter = (tree_iterator *)i;
920

921
	tree_iterator_clear(iter);
922

923
	git_tree_free(iter->root);
924
	git_buf_dispose(&iter->entry_path);
925 926
}

927
int git_iterator_for_tree(
928
	git_iterator **out,
929
	git_tree *tree,
930
	git_iterator_options *options)
931
{
932
	tree_iterator *iter;
933
	int error;
934 935 936 937 938

	static git_iterator_callbacks callbacks = {
		tree_iterator_current,
		tree_iterator_advance,
		tree_iterator_advance_into,
939
		tree_iterator_advance_over,
940 941 942 943 944
		tree_iterator_reset,
		tree_iterator_free
	};

	*out = NULL;
945 946

	if (tree == NULL)
947
		return git_iterator_for_nothing(out, options);
948

949
	iter = git__calloc(1, sizeof(tree_iterator));
950
	GIT_ERROR_CHECK_ALLOC(iter);
951

952 953
	iter->base.type = GIT_ITERATOR_TYPE_TREE;
	iter->base.cb = &callbacks;
954

955
	if ((error = iterator_init_common(&iter->base,
956
			git_tree_owner(tree), NULL, options)) < 0 ||
957 958 959
		(error = git_tree_dup(&iter->root, tree)) < 0 ||
		(error = tree_iterator_init(iter)) < 0)
		goto on_error;
960

961 962
	*out = &iter->base;
	return 0;
963

964 965 966 967
on_error:
	git_iterator_free(&iter->base);
	return error;
}
968

969 970 971 972 973 974
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;
975

976 977 978 979 980 981 982 983
	assert(i->type == GIT_ITERATOR_TYPE_TREE);

	iter = (tree_iterator *)i;

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

	*tree_entry = entry->tree_entry;
984
	return 0;
985
}
986

987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001
int git_iterator_current_parent_tree(
	const git_tree **parent_tree, git_iterator *i, size_t depth)
{
	tree_iterator *iter;
	tree_iterator_frame *frame;

	assert(i->type == GIT_ITERATOR_TYPE_TREE);

	iter = (tree_iterator *)i;

	assert(depth < iter->frames.size);
	frame = &iter->frames.ptr[iter->frames.size-depth-1];

	*parent_tree = frame->tree;
	return 0;
1002 1003
}

1004 1005 1006 1007 1008 1009
/* Filesystem iterator */

typedef struct {
	struct stat st;
	size_t path_len;
	iterator_pathlist_search_t match;
1010
	git_oid id;
1011 1012 1013 1014 1015 1016 1017
	char path[GIT_FLEX_ARRAY];
} filesystem_iterator_entry;

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

1019 1020 1021
	size_t path_len;
	int is_ignored;
} filesystem_iterator_frame;
1022 1023

typedef struct {
1024
	git_iterator base;
1025 1026 1027 1028 1029 1030
	char *root;
	size_t root_len;

	unsigned int dirload_flags;

	git_tree *tree;
1031
	git_index *index;
1032
	git_vector index_snapshot;
1033

1034 1035
	git_array_t(filesystem_iterator_frame) frames;
	git_ignores ignores;
1036

1037 1038 1039 1040
	/* info about the current entry */
	git_index_entry entry;
	git_buf current_path;
	int current_is_ignored;
1041

1042 1043 1044 1045 1046 1047 1048 1049 1050 1051
	/* 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;
1052 1053
}

1054 1055
GIT_INLINE(filesystem_iterator_frame *) filesystem_iterator_current_frame(
	filesystem_iterator *iter)
1056
{
1057 1058
	return iter->frames.size ? &iter->frames.ptr[iter->frames.size-1] : NULL;
}
1059

1060 1061 1062 1063 1064 1065
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];
}
1066

1067 1068 1069 1070
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;
1071

1072 1073
	return git__strcmp(a->path, b->path);
}
1074

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

1080
	return git__strcasecmp(a->path, b->path);
1081 1082
}

1083 1084 1085 1086 1087 1088 1089 1090
#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
1091
static int filesystem_iterator_is_submodule(
1092
	bool *out, filesystem_iterator *iter, const char *path, size_t path_len)
1093
{
1094 1095
	bool is_submodule = false;
	int error;
1096

1097
	*out = false;
1098

1099 1100 1101
	/* first see if this path is a submodule in HEAD */
	if (iter->tree) {
		git_tree_entry *entry;
1102

1103
		error = git_tree_entry_bypath(&entry, iter->tree, path);
1104

1105 1106
		if (error < 0 && error != GIT_ENOTFOUND)
			return error;
1107

1108 1109 1110 1111 1112
		if (!error) {
			is_submodule = (entry->attr == GIT_FILEMODE_COMMIT);
			git_tree_entry_free(entry);
		}
	}
1113

1114
	if (!is_submodule && iter->base.index) {
1115
		size_t pos;
1116

1117 1118
		error = git_index_snapshot_find(&pos,
			&iter->index_snapshot, iter->base.entry_srch, path, path_len, 0);
1119

1120 1121
		if (error < 0 && error != GIT_ENOTFOUND)
			return error;
1122

1123 1124 1125 1126 1127
		if (!error) {
			git_index_entry *e = git_vector_get(&iter->index_snapshot, pos);
			is_submodule = (e->mode == GIT_FILEMODE_COMMIT);
		}
	}
1128

1129
	*out = is_submodule;
1130 1131 1132
	return 0;
}

1133 1134 1135 1136
static void filesystem_iterator_frame_push_ignores(
	filesystem_iterator *iter,
	filesystem_iterator_entry *frame_entry,
	filesystem_iterator_frame *new_frame)
1137
{
1138 1139
	filesystem_iterator_frame *previous_frame;
	const char *path = frame_entry ? frame_entry->path : "";
1140

1141 1142 1143 1144 1145
	if (!iterator__honor_ignores(&iter->base))
		return;

	if (git_ignore__lookup(&new_frame->is_ignored,
			&iter->ignores, path, GIT_DIR_FLAG_TRUE) < 0) {
1146
		git_error_clear();
1147
		new_frame->is_ignored = GIT_IGNORE_NOTFOUND;
1148 1149
	}

1150 1151 1152
	/* if this is not the top level directory... */
	if (frame_entry) {
		const char *relative_path;
1153

1154
		previous_frame = filesystem_iterator_parent_frame(iter);
1155

1156 1157 1158 1159 1160 1161 1162 1163 1164
		/* 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);
	}
1165 1166
}

1167 1168
static void filesystem_iterator_frame_pop_ignores(
	filesystem_iterator *iter)
1169
{
1170 1171
	if (iterator__honor_ignores(&iter->base))
		git_ignore__pop_dir(&iter->ignores);
1172 1173
}

1174 1175 1176 1177 1178 1179 1180
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)
1181
{
1182 1183
	bool is_dir = 0;
	iterator_pathlist_search_t match = ITERATOR_PATHLIST_FULL;
1184

1185
	*is_dir_out = false;
Edward Thomson committed
1186
	*match_out = ITERATOR_PATHLIST_NONE;
1187

1188 1189
	if (iter->base.start_len) {
		int cmp = iter->base.strncomp(path, iter->base.start, path_len);
1190

1191 1192 1193 1194 1195 1196 1197
		/* 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;
1198

1199 1200
			else if (iter->base.start[path_len] != '\0')
				cmp = -1;
1201 1202
		}

1203 1204
		if (cmp < 0)
			return false;
1205
	}
1206

1207 1208
	if (iter->base.end_len) {
		int cmp = iter->base.strncomp(path, iter->base.end, iter->base.end_len);
1209

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

1214 1215
	/* 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.
1216
	 */
1217 1218 1219 1220 1221 1222
	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);
1223

Edward Thomson committed
1224
		if (match == ITERATOR_PATHLIST_NONE)
1225
			return false;
1226

1227 1228 1229 1230
		/* 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;
1231 1232
	}

1233 1234 1235
	*is_dir_out = is_dir;
	*match_out = match;
	return true;
1236 1237
}

1238 1239
GIT_INLINE(bool) filesystem_iterator_is_dot_git(
	filesystem_iterator *iter, const char *path, size_t path_len)
1240
{
1241
	size_t len;
1242

1243 1244
	if (!iterator__ignore_dot_git(&iter->base))
		return false;
1245

1246 1247
	if ((len = path_len) < 4)
		return false;
1248

1249 1250
	if (path[len - 1] == '/')
		len--;
1251

1252 1253 1254 1255 1256
	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;
1257

1258
	return (len == 4 || path[len - 5] == '/');
1259 1260
}

1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274
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;
	}

	if (iter->base.type == GIT_ITERATOR_TYPE_WORKDIR)
		return git_repository_hashfile(&entry->id,
1275
			iter->base.repo, entry->path, GIT_OBJECT_BLOB, NULL);
1276 1277

	if (!(error = git_buf_joinpath(&fullpath, iter->root, entry->path)))
1278
		error = git_odb_hashfile(&entry->id, fullpath.ptr, GIT_OBJECT_BLOB);
1279 1280 1281 1282 1283 1284 1285 1286

	git_buf_dispose(&fullpath);
	return error;
}

static int filesystem_iterator_entry_init(
	filesystem_iterator_entry **out,
	filesystem_iterator *iter,
1287 1288 1289 1290 1291
	filesystem_iterator_frame *frame,
	const char *path,
	size_t path_len,
	struct stat *statbuf,
	iterator_pathlist_search_t pathlist_match)
1292
{
1293 1294
	filesystem_iterator_entry *entry;
	size_t entry_size;
1295 1296 1297
	int error = 0;

	*out = NULL;
1298

1299 1300 1301
	/* Make sure to append two bytes, one for the path's null
	 * termination, one for a possible trailing '/' for folders.
	 */
1302
	GIT_ERROR_CHECK_ALLOC_ADD(&entry_size,
1303
		sizeof(filesystem_iterator_entry), path_len);
1304
	GIT_ERROR_CHECK_ALLOC_ADD(&entry_size, entry_size, 2);
1305 1306

	entry = git_pool_malloc(&frame->entry_pool, entry_size);
1307
	GIT_ERROR_CHECK_ALLOC(entry);
1308

1309 1310 1311 1312
	entry->path_len = path_len;
	entry->match = pathlist_match;
	memcpy(entry->path, path, path_len);
	memcpy(&entry->st, statbuf, sizeof(struct stat));
1313

1314 1315 1316
	/* Suffix directory paths with a '/' */
	if (S_ISDIR(entry->st.st_mode))
		entry->path[entry->path_len++] = '/';
1317

1318
	entry->path[entry->path_len] = '\0';
1319

1320 1321 1322 1323 1324 1325 1326
	if (iter->base.flags & GIT_ITERATOR_INCLUDE_HASH)
		error = filesystem_iterator_entry_hash(iter, entry);

	if (!error)
		*out = entry;

	return error;
1327
}
1328

1329 1330 1331
static int filesystem_iterator_frame_push(
	filesystem_iterator *iter,
	filesystem_iterator_entry *frame_entry)
1332
{
1333 1334 1335 1336 1337 1338 1339 1340
	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;
1341

1342
	if (iter->frames.size == FILESYSTEM_MAX_DEPTH) {
1343
		git_error_set(GIT_ERROR_REPOSITORY,
1344
			"directory nesting too deep (%"PRIuZ")", iter->frames.size);
1345
		return -1;
1346
	}
1347

1348
	new_frame = git_array_alloc(iter->frames);
1349
	GIT_ERROR_CHECK_ALLOC(new_frame);
1350

1351
	memset(new_frame, 0, sizeof(filesystem_iterator_frame));
1352

1353 1354
	if (frame_entry)
		git_buf_joinpath(&root, iter->root, frame_entry->path);
1355
	else
1356
		git_buf_puts(&root, iter->root);
1357

1358 1359 1360 1361 1362 1363
	if (git_buf_oom(&root)) {
		error = -1;
		goto done;
	}

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

1365
	/* Any error here is equivalent to the dir not existing, skip over it */
1366
	if ((error = git_path_diriter_init(
1367
			&diriter, root.ptr, iter->dirload_flags)) < 0) {
1368
		error = GIT_ENOTFOUND;
1369
		goto done;
1370
	}
1371

1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382
	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;

	git_pool_init(&new_frame->entry_pool, 1);

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

1383
	while ((error = git_path_diriter_next(&diriter)) == 0) {
1384 1385 1386
		iterator_pathlist_search_t pathlist_match = ITERATOR_PATHLIST_FULL;
		bool dir_expected = false;

1387 1388 1389
		if ((error = git_path_diriter_fullpath(&path, &path_len, &diriter)) < 0)
			goto done;

1390
		assert(path_len > iter->root_len);
1391 1392

		/* remove the prefix if requested */
1393 1394
		path += iter->root_len;
		path_len -= iter->root_len;
1395

1396 1397 1398 1399
		/* 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)
1400
		 */
1401 1402
		if (!filesystem_iterator_examine_path(&dir_expected, &pathlist_match,
			iter, frame_entry, path, path_len))
1403 1404
			continue;

1405 1406
		/* 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.
1407 1408
		 */

1409 1410 1411 1412
		if ((error = git_path_diriter_stat(&statbuf, &diriter)) < 0) {
			/* file was removed between readdir and lstat */
			if (error == GIT_ENOTFOUND)
				continue;
1413

1414 1415 1416
			/* treat the file as unreadable */
			memset(&statbuf, 0, sizeof(statbuf));
			statbuf.st_mode = GIT_FILEMODE_UNREADABLE;
1417

1418 1419
			error = 0;
		}
1420

1421
		iter->base.stat_calls++;
1422

1423 1424 1425 1426 1427 1428
		/* 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;
1429

1430
		if (filesystem_iterator_is_dot_git(iter, path, path_len))
1431
			continue;
1432 1433 1434 1435 1436

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

Edward Thomson committed
1437 1438
			if ((error = filesystem_iterator_is_submodule(&submodule,
					iter, path, path_len)) < 0)
1439 1440 1441 1442
				goto done;

			if (submodule)
				statbuf.st_mode = GIT_FILEMODE_COMMIT;
1443 1444
		}

1445
		/* Ensure that the pathlist entry lines up with what we expected */
1446
		else if (dir_expected)
1447 1448
			continue;

1449 1450 1451
		if ((error = filesystem_iterator_entry_init(&entry,
			iter, new_frame, path, path_len, &statbuf, pathlist_match)) < 0)
			goto done;
1452 1453

		git_vector_insert(&new_frame->entries, entry);
1454 1455 1456 1457 1458 1459
	}

	if (error == GIT_ITEROVER)
		error = 0;

	/* sort now that directory suffix is added */
1460
	git_vector_sort(&new_frame->entries);
1461 1462

done:
1463 1464 1465
	if (error < 0)
		git_array_pop(iter->frames);

1466
	git_buf_dispose(&root);
1467 1468 1469 1470
	git_path_diriter_free(&diriter);
	return error;
}

1471
GIT_INLINE(void) filesystem_iterator_frame_pop(filesystem_iterator *iter)
1472
{
1473
	filesystem_iterator_frame *frame;
1474

1475
	assert(iter->frames.size);
1476

1477 1478
	frame = git_array_pop(iter->frames);
	filesystem_iterator_frame_pop_ignores(iter);
1479

1480 1481 1482
	git_pool_clear(&frame->entry_pool);
	git_vector_free(&frame->entries);
}
1483

1484 1485 1486 1487
static void filesystem_iterator_set_current(
	filesystem_iterator *iter,
	filesystem_iterator_entry *entry)
{
1488 1489 1490 1491 1492 1493 1494 1495 1496
	/*
	 * 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;
1497

1498
#if defined(GIT_USE_NSEC)
1499
	iter->entry.ctime.nanoseconds = entry->st.st_ctime_nsec;
1500
	iter->entry.mtime.nanoseconds = entry->st.st_mtime_nsec;
1501 1502 1503
#else
	iter->entry.ctime.nanoseconds = 0;
	iter->entry.mtime.nanoseconds = 0;
1504
#endif
1505

1506 1507 1508 1509 1510
	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;
1511
	iter->entry.file_size = (uint32_t)entry->st.st_size;
1512

1513 1514 1515
	if (iter->base.flags & GIT_ITERATOR_INCLUDE_HASH)
		git_oid_cpy(&iter->entry.id, &entry->id);

1516
	iter->entry.path = entry->path;
1517

1518
	iter->current_is_ignored = GIT_IGNORE_UNCHECKED;
1519 1520
}

1521 1522
static int filesystem_iterator_current(
	const git_index_entry **out, git_iterator *i)
1523
{
1524
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1525

1526 1527
	if (!iterator__has_been_accessed(i))
		return iter->base.cb->advance(out, i);
1528

1529 1530 1531 1532
	if (!iter->frames.size) {
		*out = NULL;
		return GIT_ITEROVER;
	}
1533

1534 1535
	*out = &iter->entry;
	return 0;
1536 1537
}

1538 1539 1540 1541
static int filesystem_iterator_is_dir(
	bool *is_dir,
	const filesystem_iterator *iter,
	const filesystem_iterator_entry *entry)
1542 1543
{
	struct stat st;
1544 1545
	git_buf fullpath = GIT_BUF_INIT;
	int error = 0;
1546

1547 1548 1549 1550 1551 1552 1553 1554 1555
	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;
	}
1556

1557 1558 1559 1560 1561 1562 1563
	if ((error = git_buf_joinpath(&fullpath, iter->root, entry->path)) < 0 ||
		(error = p_stat(fullpath.ptr, &st)) < 0)
		goto done;

	*is_dir = S_ISDIR(st.st_mode);

done:
1564
	git_buf_dispose(&fullpath);
1565
	return error;
1566 1567
}

1568 1569
static int filesystem_iterator_advance(
	const git_index_entry **out, git_iterator *i)
1570
{
1571
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1572
	bool is_dir;
1573 1574
	int error = 0;

1575
	iter->base.flags |= GIT_ITERATOR_FIRST_ACCESS;
1576

1577 1578 1579 1580
	/* examine filesystem entries until we find the next one to return */
	while (true) {
		filesystem_iterator_frame *frame;
		filesystem_iterator_entry *entry;
1581

1582 1583 1584 1585
		if ((frame = filesystem_iterator_current_frame(iter)) == NULL) {
			error = GIT_ITEROVER;
			break;
		}
1586

1587 1588 1589 1590 1591
		/* no more entries in this frame.  pop the frame out */
		if (frame->next_idx == frame->entries.length) {
			filesystem_iterator_frame_pop(iter);
			continue;
		}
1592

1593 1594 1595
		/* we have more entries in the current frame, that's our next entry */
		entry = frame->entries.contents[frame->next_idx];
		frame->next_idx++;
1596

1597 1598 1599 1600
		if ((error = filesystem_iterator_is_dir(&is_dir, iter, entry)) < 0)
			break;

		if (is_dir) {
1601 1602
			if (iterator__do_autoexpand(iter)) {
				error = filesystem_iterator_frame_push(iter, entry);
1603

1604 1605 1606 1607 1608 1609 1610 1611
				/* 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;
			}
1612

1613 1614 1615
			if (!iterator__include_trees(iter))
				continue;
		}
1616

1617 1618
		filesystem_iterator_set_current(iter, entry);
		break;
1619
	}
1620 1621 1622 1623 1624

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

	return error;
1625
}
1626

1627 1628
static int filesystem_iterator_advance_into(
	const git_index_entry **out, git_iterator *i)
1629
{
1630
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1631 1632
	filesystem_iterator_frame *frame;
	filesystem_iterator_entry *prev_entry;
1633 1634
	int error;

1635 1636
	if (out)
		*out = NULL;
1637

1638 1639
	if ((frame = filesystem_iterator_current_frame(iter)) == NULL)
		return GIT_ITEROVER;
1640

1641 1642
	/* get the last seen entry */
	prev_entry = filesystem_iterator_current_entry(frame);
1643

1644 1645 1646 1647 1648
	/* 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.
	 */
	assert(iterator__do_autoexpand(i) ^ (prev_entry != NULL));
1649

1650 1651 1652 1653
	if (prev_entry) {
		if (prev_entry->st.st_mode != GIT_FILEMODE_COMMIT &&
			!S_ISDIR(prev_entry->st.st_mode))
			return 0;
1654

1655
		if ((error = filesystem_iterator_frame_push(iter, prev_entry)) < 0)
1656 1657 1658
			return error;
	}

1659 1660 1661 1662
	/* we've advanced into the directory in question, let advance
	 * find the first entry
	 */
	return filesystem_iterator_advance(out, i);
1663 1664
}

1665
int git_iterator_current_workdir_path(git_buf **out, git_iterator *i)
1666
{
1667
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1668
	const git_index_entry *entry;
1669

1670 1671 1672 1673 1674
	if (i->type != GIT_ITERATOR_TYPE_FS &&
		i->type != GIT_ITERATOR_TYPE_WORKDIR) {
		*out = NULL;
		return 0;
	}
1675

1676
	git_buf_truncate(&iter->current_path, iter->root_len);
1677

1678 1679 1680
	if (git_iterator_current(&entry, i) < 0 ||
		git_buf_puts(&iter->current_path, entry->path) < 0)
		return -1;
1681

1682 1683 1684
	*out = &iter->current_path;
	return 0;
}
1685

1686 1687 1688 1689 1690 1691 1692 1693 1694 1695
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
1696 1697
}

1698
static void filesystem_iterator_update_ignored(filesystem_iterator *iter)
1699
{
1700 1701
	filesystem_iterator_frame *frame;
	git_dir_flag dir_flag = entry_dir_flag(&iter->entry);
1702

1703 1704
	if (git_ignore__lookup(&iter->current_is_ignored,
			&iter->ignores, iter->entry.path, dir_flag) < 0) {
1705
		git_error_clear();
1706 1707
		iter->current_is_ignored = GIT_IGNORE_NOTFOUND;
	}
1708

1709 1710 1711 1712 1713
	/* 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;
	}
1714 1715
}

1716 1717
GIT_INLINE(bool) filesystem_iterator_current_is_ignored(
	filesystem_iterator *iter)
1718
{
1719 1720
	if (iter->current_is_ignored == GIT_IGNORE_UNCHECKED)
		filesystem_iterator_update_ignored(iter);
1721

1722
	return (iter->current_is_ignored == GIT_IGNORE_TRUE);
1723 1724
}

1725
bool git_iterator_current_is_ignored(git_iterator *i)
1726
{
1727 1728
	filesystem_iterator *iter = NULL;

1729 1730
	if (i->type != GIT_ITERATOR_TYPE_WORKDIR)
		return false;
1731

1732 1733 1734
	iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);

	return filesystem_iterator_current_is_ignored(iter);
1735
}
1736

1737 1738
bool git_iterator_current_tree_is_ignored(git_iterator *i)
{
1739
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1740
	filesystem_iterator_frame *frame;
1741

1742 1743
	if (i->type != GIT_ITERATOR_TYPE_WORKDIR)
		return false;
1744

1745 1746 1747
	frame = filesystem_iterator_current_frame(iter);
	return (frame->is_ignored == GIT_IGNORE_TRUE);
}
1748

1749 1750 1751 1752 1753
static int filesystem_iterator_advance_over(
	const git_index_entry **out,
	git_iterator_status_t *status,
	git_iterator *i)
{
1754
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1755 1756 1757 1758 1759
	filesystem_iterator_frame *current_frame;
	filesystem_iterator_entry *current_entry;
	const git_index_entry *entry = NULL;
	const char *base;
	int error = 0;
1760

1761 1762
	*out = NULL;
	*status = GIT_ITERATOR_STATUS_NORMAL;
1763

1764
	assert(iterator__has_been_accessed(i));
1765

1766 1767 1768 1769
	current_frame = filesystem_iterator_current_frame(iter);
	assert(current_frame);
	current_entry = filesystem_iterator_current_entry(current_frame);
	assert(current_entry);
1770

1771 1772
	if ((error = git_iterator_current(&entry, i)) < 0)
		return error;
1773

1774 1775 1776
	if (!S_ISDIR(entry->mode)) {
		if (filesystem_iterator_current_is_ignored(iter))
			*status = GIT_ITERATOR_STATUS_IGNORED;
1777

1778
		return filesystem_iterator_advance(out, i);
1779
	}
1780

1781 1782 1783
	git_buf_clear(&iter->tmp_buf);
	if ((error = git_buf_puts(&iter->tmp_buf, entry->path)) < 0)
		return error;
1784

1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798
	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;
1799

1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810
	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;
1811

1812 1813 1814
			/* this directory disappeared, ignore it */
			else if (error == GIT_ENOTFOUND)
				error = 0;
1815

1816 1817 1818
			/* a real error occurred */
			else
				break;
1819
		} else {
1820 1821 1822
			/* we found a non-ignored item, treat parent as untracked */
			*status = GIT_ITERATOR_STATUS_NORMAL;
			break;
1823
		}
1824 1825 1826 1827 1828 1829 1830 1831 1832

		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;
1833 1834
	}

1835 1836 1837
	if (!error)
		*out = entry;

1838 1839 1840
	return error;
}

1841
static void filesystem_iterator_clear(filesystem_iterator *iter)
1842
{
1843 1844
	while (iter->frames.size)
		filesystem_iterator_frame_pop(iter);
1845

1846 1847
	git_array_clear(iter->frames);
	git_ignore__free(&iter->ignores);
1848

1849
	git_buf_dispose(&iter->tmp_buf);
1850

1851
	iterator_clear(&iter->base);
1852
}
1853

1854
static int filesystem_iterator_init(filesystem_iterator *iter)
1855
{
1856
	int error;
1857

1858 1859 1860 1861
	if (iterator__honor_ignores(&iter->base) &&
		(error = git_ignore__for_path(iter->base.repo,
			".gitignore", &iter->ignores)) < 0)
		return error;
1862

1863 1864
	if ((error = filesystem_iterator_frame_push(iter, NULL)) < 0)
		return error;
1865

1866
	iter->base.flags &= ~GIT_ITERATOR_FIRST_ACCESS;
1867

1868
	return 0;
1869 1870
}

1871
static int filesystem_iterator_reset(git_iterator *i)
1872
{
1873
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1874

1875 1876 1877
	filesystem_iterator_clear(iter);
	return filesystem_iterator_init(iter);
}
1878

1879 1880
static void filesystem_iterator_free(git_iterator *i)
{
1881
	filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1882
	git__free(iter->root);
1883
	git_buf_dispose(&iter->current_path);
1884
	git_tree_free(iter->tree);
1885 1886
	if (iter->index)
		git_index_snapshot_release(&iter->index_snapshot, iter->index);
1887
	filesystem_iterator_clear(iter);
1888 1889
}

1890 1891 1892 1893 1894 1895 1896 1897
static int iterator_for_filesystem(
	git_iterator **out,
	git_repository *repo,
	const char *root,
	git_index *index,
	git_tree *tree,
	git_iterator_type_t type,
	git_iterator_options *options)
1898
{
1899 1900 1901
	filesystem_iterator *iter;
	size_t root_len;
	int error;
1902

1903 1904 1905 1906 1907 1908 1909 1910
	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
	};
1911

1912
	*out = NULL;
1913

1914 1915
	if (root == NULL)
		return git_iterator_for_nothing(out, options);
1916

1917
	iter = git__calloc(1, sizeof(filesystem_iterator));
1918
	GIT_ERROR_CHECK_ALLOC(iter);
1919

1920 1921 1922
	iter->base.type = type;
	iter->base.cb = &callbacks;

1923
	root_len = strlen(root);
1924

1925
	iter->root = git__malloc(root_len+2);
1926
	GIT_ERROR_CHECK_ALLOC(iter->root);
1927

1928
	memcpy(iter->root, root, root_len);
1929

1930 1931 1932
	if (root_len == 0 || root[root_len-1] != '/') {
		iter->root[root_len] = '/';
		root_len++;
1933
	}
1934 1935
	iter->root[root_len] = '\0';
	iter->root_len = root_len;
1936

1937 1938
	if ((error = git_buf_puts(&iter->current_path, iter->root)) < 0)
		goto on_error;
1939

1940
	if ((error = iterator_init_common(&iter->base, repo, index, options)) < 0)
1941 1942 1943 1944 1945
		goto on_error;

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

1946
	if (index &&
1947 1948 1949
		(error = git_index_snapshot_new(&iter->index_snapshot, index)) < 0)
		goto on_error;

1950
	iter->index = index;
1951 1952 1953 1954
	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);
1955

1956 1957
	if ((error = filesystem_iterator_init(iter)) < 0)
		goto on_error;
1958

1959
	*out = &iter->base;
1960
	return 0;
1961 1962 1963 1964

on_error:
	git_iterator_free(&iter->base);
	return error;
1965 1966
}

1967 1968 1969 1970
int git_iterator_for_filesystem(
	git_iterator **out,
	const char *root,
	git_iterator_options *options)
1971
{
1972 1973
	return iterator_for_filesystem(out,
		NULL, root, NULL, NULL, GIT_ITERATOR_TYPE_FS, options);
1974 1975
}

1976
int git_iterator_for_workdir_ext(
1977
	git_iterator **out,
1978
	git_repository *repo,
1979
	const char *repo_workdir,
1980 1981
	git_index *index,
	git_tree *tree,
1982
	git_iterator_options *given_opts)
1983
{
1984
	git_iterator_options options = GIT_ITERATOR_OPTIONS_INIT;
1985

1986 1987 1988
	if (!repo_workdir) {
		if (git_repository__ensure_not_bare(repo, "scan working directory") < 0)
			return GIT_EBAREREPO;
1989

1990
		repo_workdir = git_repository_workdir(repo);
1991 1992
	}

1993 1994 1995
	/* upgrade to a workdir iterator, adding necessary internal flags */
	if (given_opts)
		memcpy(&options, given_opts, sizeof(git_iterator_options));
1996

1997 1998
	options.flags |= GIT_ITERATOR_HONOR_IGNORES |
		GIT_ITERATOR_IGNORE_DOT_GIT;
1999

2000 2001
	return iterator_for_filesystem(out,
		repo, repo_workdir, index, tree, GIT_ITERATOR_TYPE_WORKDIR, &options);
2002 2003
}

2004

2005
/* Index iterator */
2006

2007

2008 2009 2010
typedef struct {
	git_iterator base;
	git_vector entries;
2011 2012 2013
	size_t next_idx;

	/* the pseudotree entry */
2014
	git_index_entry tree_entry;
2015 2016 2017 2018
	git_buf tree_buf;
	bool skip_tree;

	const git_index_entry *entry;
2019
} index_iterator;
2020

2021 2022
static int index_iterator_current(
	const git_index_entry **out, git_iterator *i)
2023
{
2024
	index_iterator *iter = (index_iterator *)i;
2025

2026 2027 2028 2029 2030 2031
	if (!iterator__has_been_accessed(i))
		return iter->base.cb->advance(out, i);

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

2034 2035
	*out = iter->entry;
	return 0;
2036 2037
}

2038 2039 2040 2041
static bool index_iterator_create_pseudotree(
	const git_index_entry **out,
	index_iterator *iter,
	const char *path)
2042
{
2043 2044
	const char *prev_path, *relative_path, *dirsep;
	size_t common_len;
2045

2046
	prev_path = iter->entry ? iter->entry->path : "";
2047

2048 2049 2050
	/* 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;
2051

2052 2053
	if ((dirsep = strchr(relative_path, '/')) == NULL)
		return false;
2054

2055 2056
	git_buf_clear(&iter->tree_buf);
	git_buf_put(&iter->tree_buf, path, (dirsep - path) + 1);
2057

2058 2059
	iter->tree_entry.mode = GIT_FILEMODE_TREE;
	iter->tree_entry.path = iter->tree_buf.ptr;
2060

2061 2062
	*out = &iter->tree_entry;
	return true;
2063 2064
}

2065
static int index_iterator_skip_pseudotree(index_iterator *iter)
2066
{
2067 2068
	assert(iterator__has_been_accessed(&iter->base));
	assert(S_ISDIR(iter->entry->mode));
2069

2070 2071
	while (true) {
		const git_index_entry *next_entry = NULL;
2072

2073 2074
		if (++iter->next_idx >= iter->entries.length)
			return GIT_ITEROVER;
2075

2076
		next_entry = iter->entries.contents[iter->next_idx];
2077

2078 2079 2080 2081
		if (iter->base.strncomp(iter->tree_buf.ptr, next_entry->path,
			iter->tree_buf.size) != 0)
			break;
	}
2082

2083
	iter->skip_tree = false;
2084
	return 0;
2085 2086
}

2087 2088
static int index_iterator_advance(
	const git_index_entry **out, git_iterator *i)
2089
{
2090
	index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2091
	const git_index_entry *entry = NULL;
2092
	bool is_submodule;
2093
	int error = 0;
2094

2095
	iter->base.flags |= GIT_ITERATOR_FIRST_ACCESS;
2096

2097 2098 2099 2100 2101
	while (true) {
		if (iter->next_idx >= iter->entries.length) {
			error = GIT_ITEROVER;
			break;
		}
2102

2103 2104 2105 2106 2107
		/* we were not asked to expand this pseudotree.  advance over it. */
		if (iter->skip_tree) {
			index_iterator_skip_pseudotree(iter);
			continue;
		}
2108

2109
		entry = iter->entries.contents[iter->next_idx];
2110
		is_submodule = S_ISGITLINK(entry->mode);
2111

2112
		if (!iterator_has_started(&iter->base, entry->path, is_submodule)) {
2113 2114 2115
			iter->next_idx++;
			continue;
		}
2116

2117
		if (iterator_has_ended(&iter->base, entry->path)) {
2118 2119 2120
			error = GIT_ITEROVER;
			break;
		}
2121

2122 2123 2124 2125 2126
		/* 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;
		}
2127

2128 2129 2130 2131 2132 2133
		/* 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;
		}
2134

2135 2136 2137 2138 2139 2140 2141
		/* 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)) {
2142

2143 2144 2145
			/* Note whether this pseudo tree should be expanded or not */
			iter->skip_tree = iterator__dont_autoexpand(&iter->base);
			break;
2146 2147
		}

2148 2149
		iter->next_idx++;
		break;
2150 2151
	}

2152 2153 2154 2155 2156 2157
	iter->entry = (error == 0) ? entry : NULL;

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

	return error;
2158 2159
}

2160 2161
static int index_iterator_advance_into(
	const git_index_entry **out, git_iterator *i)
2162
{
2163
	index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2164

2165
	if (! S_ISDIR(iter->tree_entry.mode)) {
Edward Thomson committed
2166 2167 2168
		if (out)
			*out = NULL;

2169
		return 0;
2170
	}
2171

2172 2173
	iter->skip_tree = false;
	return index_iterator_advance(out, i);
2174
}
2175

2176 2177 2178 2179
static int index_iterator_advance_over(
	const git_index_entry **out,
	git_iterator_status_t *status,
	git_iterator *i)
2180
{
2181
	index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2182 2183
	const git_index_entry *entry;
	int error;
2184

2185 2186
	if ((error = index_iterator_current(&entry, i)) < 0)
		return error;
2187

2188 2189
	if (S_ISDIR(entry->mode))
		index_iterator_skip_pseudotree(iter);
2190

2191 2192 2193
	*status = GIT_ITERATOR_STATUS_NORMAL;
	return index_iterator_advance(out, i);
}
2194

2195 2196 2197 2198
static void index_iterator_clear(index_iterator *iter)
{
	iterator_clear(&iter->base);
}
2199

2200 2201 2202 2203 2204 2205 2206
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;
}
2207

2208 2209
static int index_iterator_reset(git_iterator *i)
{
2210
	index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2211

2212 2213 2214
	index_iterator_clear(iter);
	return index_iterator_init(iter);
}
2215

2216
static void index_iterator_free(git_iterator *i)
2217
{
2218
	index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2219 2220

	git_index_snapshot_release(&iter->entries, iter->base.index);
2221
	git_buf_dispose(&iter->tree_buf);
2222 2223 2224
}

int git_iterator_for_index(
2225
	git_iterator **out,
2226 2227 2228 2229
	git_repository *repo,
	git_index  *index,
	git_iterator_options *options)
{
2230 2231
	index_iterator *iter;
	int error;
2232

2233 2234 2235 2236 2237 2238 2239 2240
	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
	};
2241

2242
	*out = NULL;
2243

2244 2245
	if (index == NULL)
		return git_iterator_for_nothing(out, options);
2246

2247
	iter = git__calloc(1, sizeof(index_iterator));
2248
	GIT_ERROR_CHECK_ALLOC(iter);
2249

2250 2251
	iter->base.type = GIT_ITERATOR_TYPE_INDEX;
	iter->base.cb = &callbacks;
2252

2253 2254 2255 2256
	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;
2257

2258 2259 2260
	git_vector_set_cmp(&iter->entries, iterator__ignore_case(&iter->base) ?
		git_index_entry_icmp : git_index_entry_cmp);
	git_vector_sort(&iter->entries);
2261

2262
	*out = &iter->base;
2263
	return 0;
2264 2265 2266 2267

on_error:
	git_iterator_free(&iter->base);
	return error;
2268
}
2269

2270

2271 2272
/* Iterator API */

Edward Thomson committed
2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286
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);
}

void git_iterator_set_ignore_case(git_iterator *i, bool ignore_case)
{
	assert(!iterator__has_been_accessed(i));
	iterator_set_ignore_case(i, ignore_case);
}
2287

2288 2289 2290 2291
void git_iterator_free(git_iterator *iter)
{
	if (iter == NULL)
		return;
2292

2293
	iter->cb->free(iter);
2294

2295 2296 2297
	git_vector_free(&iter->pathlist);
	git__free(iter->start);
	git__free(iter->end);
2298

2299
	memset(iter, 0, sizeof(*iter));
2300

2301 2302 2303
	git__free(iter);
}

2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332
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;
}

2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347
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 *));

2348 2349
	GIT_ERROR_CHECK_ALLOC(iterator_item);
	GIT_ERROR_CHECK_ALLOC(cur_items);
2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 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

	/* 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:
2411 2412
	git__free((git_index_entry **)iterator_item);
	git__free((git_index_entry **)cur_items);
2413

2414 2415 2416 2417 2418
	if (error == GIT_ITEROVER)
		error = 0;

	return error;
}