iterator.c 27.9 KB
Newer Older
1
/*
Edward Thomson committed
2
 * Copyright (C) the libgit2 contributors. All rights reserved.
3 4 5 6 7 8 9 10 11
 *
 * 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"
#include "tree.h"
#include "ignore.h"
#include "buffer.h"
12
#include "git2/submodule.h"
13
#include <ctype.h>
14

15 16 17 18 19 20 21 22 23
#define ITERATOR_SET_CB(P,NAME_LC) do { \
	(P)->cb.current = NAME_LC ## _iterator__current; \
	(P)->cb.at_end  = NAME_LC ## _iterator__at_end; \
	(P)->cb.advance = NAME_LC ## _iterator__advance; \
	(P)->cb.seek    = NAME_LC ## _iterator__seek; \
	(P)->cb.reset   = NAME_LC ## _iterator__reset; \
	(P)->cb.free    = NAME_LC ## _iterator__free; \
	} while (0)

24 25 26
#define ITERATOR_BASE_INIT(P,NAME_LC,NAME_UC) do { \
	(P) = git__calloc(1, sizeof(NAME_LC ## _iterator)); \
	GITERR_CHECK_ALLOC(P); \
27
	(P)->base.type    = GIT_ITERATOR_TYPE_ ## NAME_UC; \
28 29
	(P)->base.cb    = &(P)->cb; \
	ITERATOR_SET_CB(P,NAME_LC); \
30 31
	(P)->base.start   = start ? git__strdup(start) : NULL; \
	(P)->base.end     = end ? git__strdup(end) : NULL; \
32 33
	if ((start && !(P)->base.start) || (end && !(P)->base.end)) { \
		git__free(P); return -1; } \
34
	(P)->base.prefixcomp = git__prefixcmp; \
35 36
	} while (0)

37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
static int iterator__reset_range(
	git_iterator *iter, const char *start, const char *end)
{
	if (start) {
		if (iter->start)
			git__free(iter->start);
		iter->start = git__strdup(start);
		GITERR_CHECK_ALLOC(iter->start);
	}

	if (end) {
		if (iter->end)
			git__free(iter->end);
		iter->end = git__strdup(end);
		GITERR_CHECK_ALLOC(iter->end);
	}

	return 0;
}
56

57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
static int iterator_update_ignore_case(
	git_iterator *iter,
	git_iterator_flag_t flags)
{
	int error = 0, ignore_case = -1;

	if ((flags & GIT_ITERATOR_IGNORE_CASE) != 0)
		ignore_case = true;
	else if ((flags & GIT_ITERATOR_DONT_IGNORE_CASE) != 0)
		ignore_case = false;
	else {
		git_index *index;

		if (!(error = git_repository_index__weakptr(&index, iter->repo)))
			ignore_case = (index->ignore_case != false);
	}

	if (ignore_case > 0)
		iter->flags = (iter->flags | GIT_ITERATOR_IGNORE_CASE);
	else if (ignore_case == 0)
		iter->flags = (iter->flags & ~GIT_ITERATOR_IGNORE_CASE);

79 80 81
	iter->prefixcomp = ((iter->flags & GIT_ITERATOR_IGNORE_CASE) != 0) ?
		git__prefixcmp_icase : git__prefixcmp;

82 83 84
	return error;
}

85 86 87 88 89 90 91 92 93 94 95 96 97 98
static int empty_iterator__no_item(
	git_iterator *iter, const git_index_entry **entry)
{
	GIT_UNUSED(iter);
	*entry = NULL;
	return 0;
}

static int empty_iterator__at_end(git_iterator *iter)
{
	GIT_UNUSED(iter);
	return 1;
}

99 100
static int empty_iterator__reset(
	git_iterator *iter, const char *start, const char *end)
101
{
102
	GIT_UNUSED(iter); GIT_UNUSED(start); GIT_UNUSED(end);
103 104 105
	return 0;
}

106 107
static int empty_iterator__seek(git_iterator *iter, const char *prefix)
{
108
	GIT_UNUSED(iter); GIT_UNUSED(prefix);
109 110 111
	return -1;
}

112 113 114 115 116
static void empty_iterator__free(git_iterator *iter)
{
	GIT_UNUSED(iter);
}

117 118 119 120 121
typedef struct {
	git_iterator base;
	git_iterator_callbacks cb;
} empty_iterator;

122
int git_iterator_for_nothing(git_iterator **iter, git_iterator_flag_t flags)
123
{
124
	empty_iterator *i = git__calloc(1, sizeof(empty_iterator));
125 126
	GITERR_CHECK_ALLOC(i);

127
	i->base.type  = GIT_ITERATOR_TYPE_EMPTY;
128
	i->base.cb    = &i->cb;
129
	i->base.flags = flags;
130 131 132 133 134 135
	i->cb.current = empty_iterator__no_item;
	i->cb.at_end  = empty_iterator__at_end;
	i->cb.advance = empty_iterator__no_item;
	i->cb.seek    = empty_iterator__seek;
	i->cb.reset   = empty_iterator__reset;
	i->cb.free    = empty_iterator__free;
136

137
	*iter = (git_iterator *)i;
138 139 140 141

	return 0;
}

142

143 144
typedef struct tree_iterator_frame tree_iterator_frame;
struct tree_iterator_frame {
145
	tree_iterator_frame *next, *prev;
146
	git_tree *tree;
147
	char *start;
148
	size_t startlen;
149
	size_t index;
150 151
	void **icase_map;
	void *icase_data[GIT_FLEX_ARRAY];
152
};
153 154

typedef struct {
155
	git_iterator base;
156
	git_iterator_callbacks cb;
157
	tree_iterator_frame *stack, *tail;
158 159
	git_index_entry entry;
	git_buf path;
160
	bool path_has_filename;
161
} tree_iterator;
162

163
GIT_INLINE(const git_tree_entry *)tree_iterator__tree_entry(tree_iterator *ti)
164
{
165 166 167 168 169 170 171
	tree_iterator_frame *tf = ti->stack;

	if (tf->index >= git_tree_entrycount(tf->tree))
		return NULL;

	return git_tree_entry_byindex(
		tf->tree, tf->icase_map ? (size_t)tf->icase_map[tf->index] : tf->index);
172 173
}

174 175 176 177 178 179 180 181 182 183 184 185
static char *tree_iterator__current_filename(
	tree_iterator *ti, const git_tree_entry *te)
{
	if (!ti->path_has_filename) {
		if (git_buf_joinpath(&ti->path, ti->path.ptr, te->filename) < 0)
			return NULL;
		ti->path_has_filename = true;
	}

	return ti->path.ptr;
}

186
static void tree_iterator__free_frame(tree_iterator_frame *tf)
187
{
188 189
	if (!tf)
		return;
190

191
	git_tree_free(tf->tree);
192 193
	tf->tree = NULL;

194 195 196
	git__free(tf);
}

197
static bool tree_iterator__pop_frame(tree_iterator *ti)
198
{
199 200 201 202 203 204 205 206
	tree_iterator_frame *tf = ti->stack;

	/* don't free the initial tree/frame */
	if (!tf->next)
		return false;

	ti->stack = tf->next;
	ti->stack->prev = NULL;
207

208 209 210 211
	tree_iterator__free_frame(tf);

	return true;
}
212

213 214 215 216
static int tree_iterator__to_end(tree_iterator *ti)
{
	while (tree_iterator__pop_frame(ti)) /* pop all */;
	ti->stack->index = git_tree_entrycount(ti->stack->tree);
217 218 219
	return 0;
}

220
static int tree_iterator__current(
221 222
	git_iterator *self, const git_index_entry **entry)
{
223 224
	tree_iterator *ti = (tree_iterator *)self;
	const git_tree_entry *te = tree_iterator__tree_entry(ti);
225

226 227
	if (entry)
		*entry = NULL;
228 229

	if (te == NULL)
230
		return 0;
231 232 233

	ti->entry.mode = te->attr;
	git_oid_cpy(&ti->entry.oid, &te->oid);
234 235 236

	ti->entry.path = tree_iterator__current_filename(ti, te);
	if (ti->entry.path == NULL)
237 238
		return -1;

239
	if (ti->base.end && ti->base.prefixcomp(ti->entry.path, ti->base.end) > 0)
240
		return tree_iterator__to_end(ti);
241

242 243
	if (entry)
		*entry = &ti->entry;
244

245
	return 0;
246 247
}

248
static int tree_iterator__at_end(git_iterator *self)
249
{
250
	return (tree_iterator__tree_entry((tree_iterator *)self) == NULL);
251 252
}

253 254 255 256 257
static int tree_iterator__icase_map_cmp(const void *a, const void *b, void *data)
{
	git_tree *tree = data;
	const git_tree_entry *te1 = git_tree_entry_byindex(tree, (size_t)a);
	const git_tree_entry *te2 = git_tree_entry_byindex(tree, (size_t)b);
258

259 260 261
	return te1 ? (te2 ? git_tree_entry_icmp(te1, te2) : 1) : -1;
}

262
static int tree_iterator__frame_start_icmp(const void *key, const void *el)
263 264
{
	const tree_iterator_frame *tf = (const tree_iterator_frame *)key;
265 266
	const git_tree_entry *te = git_tree_entry_byindex(tf->tree, (size_t)el);
	size_t minlen = min(tf->startlen, te->filename_len);
267

268
	return git__strncasecmp(tf->start, te->filename, minlen);
269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292
}

static void tree_iterator__frame_seek_start(tree_iterator_frame *tf)
{
	if (!tf->start)
		tf->index = 0;
	else if (!tf->icase_map)
		tf->index = git_tree__prefix_position(tf->tree, tf->start);
	else {
		if (!git__bsearch(
				tf->icase_map, git_tree_entrycount(tf->tree),
				tf, tree_iterator__frame_start_icmp, &tf->index))
		{
			while (tf->index > 0) {
				/* move back while previous entry is still prefixed */
				if (tree_iterator__frame_start_icmp(
						tf, (const void *)(tf->index - 1)))
					break;
				tf->index--;
			}
		}
	}
}

293
static tree_iterator_frame *tree_iterator__alloc_frame(
294
	tree_iterator *ti, git_tree *tree, char *start)
295
{
296 297 298
	size_t i, max_i = git_tree_entrycount(tree);
	tree_iterator_frame *tf =
		git__calloc(1, sizeof(tree_iterator_frame) + max_i * sizeof(void *));
299 300 301 302 303 304 305
	if (!tf)
		return NULL;

	tf->tree = tree;

	if (start && *start) {
		tf->start = start;
306
		tf->startlen = strlen(start);
307 308
	}

309 310 311 312 313 314 315 316 317 318 319 320 321 322 323
	if (!max_i)
		return tf;

	if ((ti->base.flags & GIT_ITERATOR_IGNORE_CASE) != 0) {
		tf->icase_map = tf->icase_data;

		for (i = 0; i < max_i; ++i)
			tf->icase_map[i] = (void *)i;

		git__tsort_r(
			tf->icase_map, max_i, tree_iterator__icase_map_cmp, tf->tree);
	}

	tree_iterator__frame_seek_start(tf);

324 325
	return tf;
}
326

327 328 329 330 331 332
static int tree_iterator__expand_tree(tree_iterator *ti)
{
	int error;
	git_tree *subtree;
	const git_tree_entry *te = tree_iterator__tree_entry(ti);
	tree_iterator_frame *tf;
333
	char *relpath;
334

Vicent Martí committed
335
	while (te != NULL && git_tree_entry__is_tree(te)) {
336 337 338 339 340
		if (git_buf_joinpath(&ti->path, ti->path.ptr, te->filename) < 0)
			return -1;

		/* check that we have not passed the range end */
		if (ti->base.end != NULL &&
341
			ti->base.prefixcomp(ti->path.ptr, ti->base.end) > 0)
342 343
			return tree_iterator__to_end(ti);

Russell Belfer committed
344
		if ((error = git_tree_lookup(&subtree, ti->base.repo, &te->oid)) < 0)
345 346
			return error;

347 348 349 350
		relpath = NULL;

		/* apply range start to new frame if relevant */
		if (ti->stack->start &&
351
			ti->base.prefixcomp(ti->stack->start, te->filename) == 0)
352
		{
353 354
			if (ti->stack->start[te->filename_len] == '/')
				relpath = ti->stack->start + te->filename_len + 1;
355 356
		}

357
		if ((tf = tree_iterator__alloc_frame(ti, subtree, relpath)) == NULL)
358
			return -1;
359 360 361

		tf->next  = ti->stack;
		ti->stack = tf;
362
		tf->next->prev = tf;
363 364

		te = tree_iterator__tree_entry(ti);
365 366
	}

367
	return 0;
368 369
}

370
static int tree_iterator__advance(
371
	git_iterator *self, const git_index_entry **entry)
372
{
373
	int error = 0;
374
	tree_iterator *ti = (tree_iterator *)self;
schu committed
375
	const git_tree_entry *te = NULL;
376

377 378 379
	if (entry != NULL)
		*entry = NULL;

380
	if (ti->path_has_filename) {
381
		git_buf_rtruncate_at_char(&ti->path, '/');
382 383
		ti->path_has_filename = false;
	}
384

385
	while (1) {
386 387 388
		++ti->stack->index;

		if ((te = tree_iterator__tree_entry(ti)) != NULL)
389 390
			break;

391 392
		if (!tree_iterator__pop_frame(ti))
			break; /* no frames left to pop */
393 394

		git_buf_rtruncate_at_char(&ti->path, '/');
395 396
	}

Vicent Martí committed
397
	if (te && git_tree_entry__is_tree(te))
398
		error = tree_iterator__expand_tree(ti);
399

400
	if (!error)
401
		error = tree_iterator__current(self, entry);
402 403

	return error;
404 405
}

406 407 408 409 410 411 412 413 414 415
static int tree_iterator__seek(git_iterator *self, const char *prefix)
{
	GIT_UNUSED(self);
	GIT_UNUSED(prefix);
	/* pop stack until matches prefix */
	/* seek item in current frame matching prefix */
	/* push stack which matches prefix */
	return -1;
}

416
static void tree_iterator__free(git_iterator *self)
417
{
418
	tree_iterator *ti = (tree_iterator *)self;
419 420 421 422 423 424

	while (tree_iterator__pop_frame(ti)) /* pop all */;

	tree_iterator__free_frame(ti->stack);
	ti->stack = ti->tail = NULL;

425 426 427
	git_buf_free(&ti->path);
}

428 429
static int tree_iterator__reset(
	git_iterator *self, const char *start, const char *end)
430 431
{
	tree_iterator *ti = (tree_iterator *)self;
432

433
	while (tree_iterator__pop_frame(ti)) /* pop all */;
434

435 436 437
	if (iterator__reset_range(self, start, end) < 0)
		return -1;

438 439
	/* reset start position */
	tree_iterator__frame_seek_start(ti->stack);
440 441

	git_buf_clear(&ti->path);
442
	ti->path_has_filename = false;
443

444 445 446
	return tree_iterator__expand_tree(ti);
}

447 448 449
int git_iterator_for_tree_range(
	git_iterator **iter,
	git_tree *tree,
450
	git_iterator_flag_t flags,
451 452
	const char *start,
	const char *end)
453 454
{
	int error;
455 456 457
	tree_iterator *ti;

	if (tree == NULL)
458
		return git_iterator_for_nothing(iter, flags);
459

460 461 462
	if ((error = git_tree__dup(&tree, tree)) < 0)
		return error;

463
	ITERATOR_BASE_INIT(ti, tree, TREE);
464

Russell Belfer committed
465
	ti->base.repo = git_tree_owner(tree);
466 467 468 469

	if ((error = iterator_update_ignore_case((git_iterator *)ti, flags)) < 0)
		goto fail;

470
	ti->stack = ti->tail = tree_iterator__alloc_frame(ti, tree, ti->base.start);
471

472
	if ((error = tree_iterator__expand_tree(ti)) < 0)
473 474 475 476
		goto fail;

	*iter = (git_iterator *)ti;
	return 0;
477

478 479
fail:
	git_iterator_free((git_iterator *)ti);
480 481 482 483 484
	return error;
}


typedef struct {
485
	git_iterator base;
486
	git_iterator_callbacks cb;
487
	git_index *index;
488
	size_t current;
489
} index_iterator;
490

491
static int index_iterator__current(
492 493
	git_iterator *self, const git_index_entry **entry)
{
494
	index_iterator *ii = (index_iterator *)self;
Ben Straub committed
495
	const git_index_entry *ie = git_index_get_byindex(ii->index, ii->current);
496 497 498 499

	if (entry)
		*entry = ie;

500
	return 0;
501 502
}

503
static int index_iterator__at_end(git_iterator *self)
504
{
505
	index_iterator *ii = (index_iterator *)self;
506 507 508
	return (ii->current >= git_index_entrycount(ii->index));
}

509 510 511 512 513 514 515 516 517 518 519
static void index_iterator__skip_conflicts(
	index_iterator *ii)
{
	size_t entrycount = git_index_entrycount(ii->index);
	const git_index_entry *ie;

	while (ii->current < entrycount) {
		ie = git_index_get_byindex(ii->index, ii->current);

		if (ie == NULL ||
			(ii->base.end != NULL &&
520
			 ii->base.prefixcomp(ie->path, ii->base.end) > 0)) {
521 522 523 524 525 526 527 528 529 530 531
			ii->current = entrycount;
			break;
		}

		if (git_index_entry_stage(ie) == 0)
			break;

		ii->current++;
	}
}

532
static int index_iterator__advance(
533
	git_iterator *self, const git_index_entry **entry)
534
{
535
	index_iterator *ii = (index_iterator *)self;
536

537 538
	if (ii->current < git_index_entrycount(ii->index))
		ii->current++;
539

540 541
	index_iterator__skip_conflicts(ii);

542 543 544 545 546 547 548 549 550
	return index_iterator__current(self, entry);
}

static int index_iterator__seek(git_iterator *self, const char *prefix)
{
	GIT_UNUSED(self);
	GIT_UNUSED(prefix);
	/* find last item before prefix */
	return -1;
551 552
}

553 554
static int index_iterator__reset(
	git_iterator *self, const char *start, const char *end)
555 556
{
	index_iterator *ii = (index_iterator *)self;
557 558
	if (iterator__reset_range(self, start, end) < 0)
		return -1;
559 560 561
	ii->current = ii->base.start ?
		git_index__prefix_position(ii->index, ii->base.start) : 0;
	index_iterator__skip_conflicts(ii);
562
	return 0;
563 564
}

565
static void index_iterator__free(git_iterator *self)
566
{
567
	index_iterator *ii = (index_iterator *)self;
568
	git_index_free(ii->index);
569 570 571
	ii->index = NULL;
}

572 573
int git_iterator_for_index_range(
	git_iterator **iter,
574
	git_index  *index,
575
	git_iterator_flag_t flags,
576 577
	const char *start,
	const char *end)
578
{
579
	index_iterator *ii;
580

581 582
	GIT_UNUSED(flags);

583
	ITERATOR_BASE_INIT(ii, index, INDEX);
584

Russell Belfer committed
585
	ii->base.repo = git_index_owner(index);
586
	if (index->ignore_case) {
587
		ii->base.flags |= GIT_ITERATOR_IGNORE_CASE;
588 589
		ii->base.prefixcomp = git__prefixcmp_icase;
	}
590 591
	ii->index = index;
	GIT_REFCOUNT_INC(index);
592

593
	index_iterator__reset((git_iterator *)ii, NULL, NULL);
594

595 596 597
	*iter = (git_iterator *)ii;

	return 0;
598 599 600
}


601 602 603 604
typedef struct workdir_iterator_frame workdir_iterator_frame;
struct workdir_iterator_frame {
	workdir_iterator_frame *next;
	git_vector entries;
605
	size_t index;
606 607
};

608
typedef struct {
609
	git_iterator base;
610
	git_iterator_callbacks cb;
611
	workdir_iterator_frame *stack;
612
	int (*entrycmp)(const void *pfx, const void *item);
613 614 615
	git_ignores ignores;
	git_index_entry entry;
	git_buf path;
616
	size_t root_len;
617
	int is_ignored;
618 619
} workdir_iterator;

620 621 622 623 624 625 626 627
GIT_INLINE(bool) path_is_dotgit(const git_path_with_stat *ps)
{
	if (!ps)
		return false;
	else {
		const char *path = ps->path;
		size_t len  = ps->path_len;

628 629 630 631 632 633 634 635 636 637
		if (len < 4)
			return false;
		if (path[len - 1] == '/')
			len--;
		if (tolower(path[len - 1]) != 't' ||
			tolower(path[len - 2]) != 'i' ||
			tolower(path[len - 3]) != 'g' ||
			tolower(path[len - 4]) != '.')
			return false;
		return (len == 4 || path[len - 5] == '/');
638 639 640
	}
}

641 642
static workdir_iterator_frame *workdir_iterator__alloc_frame(
	workdir_iterator *wi)
643 644
{
	workdir_iterator_frame *wf = git__calloc(1, sizeof(workdir_iterator_frame));
645 646
	git_vector_cmp entry_compare = CASESELECT(
		(wi->base.flags & GIT_ITERATOR_IGNORE_CASE) != 0,
647
		git_path_with_stat_cmp_icase, git_path_with_stat_cmp);
648

649
	if (wf == NULL)
650
		return NULL;
651

652
	if (git_vector_init(&wf->entries, 0, entry_compare) != 0) {
653 654 655
		git__free(wf);
		return NULL;
	}
656

657 658
	return wf;
}
659

660
static void workdir_iterator__free_frame(workdir_iterator_frame *wf)
661 662
{
	unsigned int i;
663
	git_path_with_stat *path;
664

665
	git_vector_foreach(&wf->entries, i, path)
666
		git__free(path);
667 668
	git_vector_free(&wf->entries);
	git__free(wf);
669 670
}

671
static int workdir_iterator__update_entry(workdir_iterator *wi);
672

673
static int workdir_iterator__entry_cmp_case(const void *pfx, const void *item)
674 675
{
	const git_path_with_stat *ps = item;
676
	return git__prefixcmp((const char *)pfx, ps->path);
677 678
}

679
static int workdir_iterator__entry_cmp_icase(const void *pfx, const void *item)
680 681
{
	const git_path_with_stat *ps = item;
682 683 684 685 686 687 688 689 690 691
	return git__prefixcmp_icase((const char *)pfx, ps->path);
}

static void workdir_iterator__seek_frame_start(
	workdir_iterator *wi, workdir_iterator_frame *wf)
{
	if (!wf)
		return;

	if (wi->base.start)
692
		git_vector_bsearch2(
693 694 695 696 697 698
			&wf->index, &wf->entries, wi->entrycmp, wi->base.start);
	else
		wf->index = 0;

	if (path_is_dotgit(git_vector_get(&wf->entries, wf->index)))
		wf->index++;
699 700
}

701
static int workdir_iterator__expand_dir(workdir_iterator *wi)
702 703
{
	int error;
704
	workdir_iterator_frame *wf = workdir_iterator__alloc_frame(wi);
705
	GITERR_CHECK_ALLOC(wf);
706

707
	error = git_path_dirload_with_stat(
708 709
		wi->path.ptr, wi->root_len,
		(wi->base.flags & GIT_ITERATOR_IGNORE_CASE) != 0,
710 711
		wi->base.start, wi->base.end, &wf->entries);

712
	if (error < 0 || wf->entries.length == 0) {
713
		workdir_iterator__free_frame(wf);
714 715 716
		return GIT_ENOTFOUND;
	}

717
	workdir_iterator__seek_frame_start(wi, wf);
718

719
	/* only push new ignores if this is not top level directory */
720
	if (wi->stack != NULL) {
721
		ssize_t slash_pos = git_buf_rfind_next(&wi->path, '/');
722 723 724
		(void)git_ignore__push_dir(&wi->ignores, &wi->path.ptr[slash_pos + 1]);
	}

725 726 727
	wf->next  = wi->stack;
	wi->stack = wf;

728
	return workdir_iterator__update_entry(wi);
729 730
}

731
static int workdir_iterator__current(
732 733
	git_iterator *self, const git_index_entry **entry)
{
734
	workdir_iterator *wi = (workdir_iterator *)self;
735
	*entry = (wi->entry.path == NULL) ? NULL : &wi->entry;
736
	return 0;
737 738
}

739
static int workdir_iterator__at_end(git_iterator *self)
740
{
741
	return (((workdir_iterator *)self)->entry.path == NULL);
742 743
}

744
static int workdir_iterator__advance(
745
	git_iterator *self, const git_index_entry **entry)
746
{
747
	int error;
748 749
	workdir_iterator *wi = (workdir_iterator *)self;
	workdir_iterator_frame *wf;
750
	git_path_with_stat *next;
751

752
	if (entry != NULL)
753 754
		*entry = NULL;

755
	if (wi->entry.path == NULL)
756
		return 0;
757

758 759
	while (1) {
		wf   = wi->stack;
760
		next = git_vector_get(&wf->entries, ++wf->index);
761

762
		if (next != NULL) {
763
			/* match git's behavior of ignoring anything named ".git" */
764
			if (path_is_dotgit(next))
765 766 767 768 769
				continue;
			/* else found a good entry */
			break;
		}

770 771
		/* pop stack if anything is left to pop */
		if (!wf->next) {
772
			memset(&wi->entry, 0, sizeof(wi->entry));
773
			return 0;
774
		}
775 776 777 778

		wi->stack = wf->next;
		workdir_iterator__free_frame(wf);
		git_ignore__pop_dir(&wi->ignores);
779 780
	}

781
	error = workdir_iterator__update_entry(wi);
782

783
	if (!error && entry != NULL)
784
		error = workdir_iterator__current(self, entry);
785 786

	return error;
787 788
}

789 790 791 792 793 794 795 796 797 798
static int workdir_iterator__seek(git_iterator *self, const char *prefix)
{
	GIT_UNUSED(self);
	GIT_UNUSED(prefix);
	/* pop stack until matching prefix */
	/* find prefix item in current frame */
	/* push subdirectories as deep as possible while matching */
	return 0;
}

799 800
static int workdir_iterator__reset(
	git_iterator *self, const char *start, const char *end)
801 802
{
	workdir_iterator *wi = (workdir_iterator *)self;
803

804 805 806 807 808 809
	while (wi->stack != NULL && wi->stack->next != NULL) {
		workdir_iterator_frame *wf = wi->stack;
		wi->stack = wf->next;
		workdir_iterator__free_frame(wf);
		git_ignore__pop_dir(&wi->ignores);
	}
810 811 812 813 814 815 816

	if (iterator__reset_range(self, start, end) < 0)
		return -1;

	workdir_iterator__seek_frame_start(wi, wi->stack);

	return workdir_iterator__update_entry(wi);
817 818
}

819
static void workdir_iterator__free(git_iterator *self)
820
{
821
	workdir_iterator *wi = (workdir_iterator *)self;
822

823 824 825 826
	while (wi->stack != NULL) {
		workdir_iterator_frame *wf = wi->stack;
		wi->stack = wf->next;
		workdir_iterator__free_frame(wf);
827 828 829 830 831 832
	}

	git_ignore__free(&wi->ignores);
	git_buf_free(&wi->path);
}

833
static int workdir_iterator__update_entry(workdir_iterator *wi)
834
{
835 836
	git_path_with_stat *ps =
		git_vector_get(&wi->stack->entries, wi->stack->index);
837

838
	git_buf_truncate(&wi->path, wi->root_len);
839 840 841 842 843
	memset(&wi->entry, 0, sizeof(wi->entry));

	if (!ps)
		return 0;

844 845
	if (git_buf_put(&wi->path, ps->path, ps->path_len) < 0)
		return -1;
846

847 848
	if (wi->base.end &&
		wi->base.prefixcomp(wi->path.ptr + wi->root_len, wi->base.end) > 0)
849 850
		return 0;

851
	wi->entry.path = ps->path;
852

853
	/* skip over .git entries */
854
	if (path_is_dotgit(ps))
855
		return workdir_iterator__advance((git_iterator *)wi, NULL);
856

857
	wi->is_ignored = -1;
858

859
	git_index_entry__init_from_stat(&wi->entry, &ps->st);
860 861

	/* need different mode here to keep directories during iteration */
862
	wi->entry.mode = git_futils_canonical_mode(ps->st.st_mode);
863 864

	/* if this is a file type we don't handle, treat as ignored */
865 866
	if (wi->entry.mode == 0) {
		wi->is_ignored = 1;
867
		return 0;
868
	}
869

870
	/* detect submodules */
871
	if (S_ISDIR(wi->entry.mode)) {
Russell Belfer committed
872
		int res = git_submodule_lookup(NULL, wi->base.repo, wi->entry.path);
873 874 875
		bool is_submodule = (res == 0);
		if (res == GIT_ENOTFOUND)
			giterr_clear();
876 877 878 879 880 881 882 883

		/* if submodule, mark as GITLINK and remove trailing slash */
		if (is_submodule) {
			size_t len = strlen(wi->entry.path);
			assert(wi->entry.path[len - 1] == '/');
			wi->entry.path[len - 1] = '\0';
			wi->entry.mode = S_IFGITLINK;
		}
Russell Belfer committed
884
	}
885

886
	return 0;
887 888
}

889 890 891
int git_iterator_for_workdir_range(
	git_iterator **iter,
	git_repository *repo,
892
	git_iterator_flag_t flags,
893 894
	const char *start,
	const char *end)
895 896
{
	int error;
897
	workdir_iterator *wi;
898

899 900
	assert(iter && repo);

901 902
	if ((error = git_repository__ensure_not_bare(
			repo, "scan working directory")) < 0)
903
		return error;
904 905

	ITERATOR_BASE_INIT(wi, workdir, WORKDIR);
Russell Belfer committed
906
	wi->base.repo = repo;
907

908 909
	if ((error = iterator_update_ignore_case((git_iterator *)wi, flags)) < 0)
		goto fail;
910

911 912 913 914
	if (git_buf_sets(&wi->path, git_repository_workdir(repo)) < 0 ||
		git_path_to_dir(&wi->path) < 0 ||
		git_ignore__for_path(repo, "", &wi->ignores) < 0)
	{
915
		git__free(wi);
916
		return -1;
917 918 919
	}

	wi->root_len = wi->path.size;
920
	wi->entrycmp = (wi->base.flags & GIT_ITERATOR_IGNORE_CASE) != 0 ?
921
		workdir_iterator__entry_cmp_icase : workdir_iterator__entry_cmp_case;
922

923
	if ((error = workdir_iterator__expand_dir(wi)) < 0) {
924 925 926
		if (error != GIT_ENOTFOUND)
			goto fail;
		giterr_clear();
927 928 929
	}

	*iter = (git_iterator *)wi;
930
	return 0;
931

932 933
fail:
	git_iterator_free((git_iterator *)wi);
934 935 936
	return error;
}

937

938
typedef struct {
939 940 941 942 943 944
	/* replacement callbacks */
	git_iterator_callbacks cb;
	/* original iterator values */
	git_iterator_callbacks *orig;
	git_iterator_type_t orig_type;
	/* spoolandsort data */
945 946 947
	git_vector entries;
	git_pool entry_pool;
	git_pool string_pool;
948 949
	size_t position;
} spoolandsort_callbacks;
950 951 952 953

static int spoolandsort_iterator__current(
	git_iterator *self, const git_index_entry **entry)
{
954
	spoolandsort_callbacks *scb = (spoolandsort_callbacks *)self->cb;
955

956 957
	*entry = (const git_index_entry *)
		git_vector_get(&scb->entries, scb->position);
958 959 960 961 962 963

	return 0;
}

static int spoolandsort_iterator__at_end(git_iterator *self)
{
964
	spoolandsort_callbacks *scb = (spoolandsort_callbacks *)self->cb;
965

966
	return 0 == scb->entries.length || scb->entries.length - 1 <= scb->position;
967 968 969 970 971
}

static int spoolandsort_iterator__advance(
	git_iterator *self, const git_index_entry **entry)
{
972
	spoolandsort_callbacks *scb = (spoolandsort_callbacks *)self->cb;
973

974 975
	*entry = (const git_index_entry *)
		git_vector_get(&scb->entries, ++scb->position);
976 977 978 979 980 981 982 983 984 985 986 987

	return 0;
}

static int spoolandsort_iterator__seek(git_iterator *self, const char *prefix)
{
	GIT_UNUSED(self);
	GIT_UNUSED(prefix);

	return -1;
}

988 989
static int spoolandsort_iterator__reset(
	git_iterator *self, const char *start, const char *end)
990
{
991
	spoolandsort_callbacks *scb = (spoolandsort_callbacks *)self->cb;
992

993 994
	GIT_UNUSED(start); GIT_UNUSED(end);

995
	scb->position = 0;
996 997 998 999

	return 0;
}

1000
static void spoolandsort_iterator__free_callbacks(spoolandsort_callbacks *scb)
1001
{
1002 1003 1004 1005 1006
	git_pool_clear(&scb->string_pool);
	git_pool_clear(&scb->entry_pool);
	git_vector_free(&scb->entries);
	git__free(scb);
}
1007

1008 1009 1010 1011
void git_iterator_spoolandsort_pop(git_iterator *self)
{
	spoolandsort_callbacks *scb = (spoolandsort_callbacks *)self->cb;

1012
	if (self->type != GIT_ITERATOR_TYPE_SPOOLANDSORT)
1013 1014 1015 1016
		return;

	self->cb   = scb->orig;
	self->type = scb->orig_type;
1017
	self->flags ^= GIT_ITERATOR_IGNORE_CASE;
1018 1019

	spoolandsort_iterator__free_callbacks(scb);
1020 1021
}

1022 1023 1024 1025 1026 1027 1028
static void spoolandsort_iterator__free(git_iterator *self)
{
	git_iterator_spoolandsort_pop(self);
	self->cb->free(self);
}

int git_iterator_spoolandsort_push(git_iterator *iter, bool ignore_case)
1029 1030
{
	const git_index_entry *item;
1031 1032
	spoolandsort_callbacks *scb;
	int (*entrycomp)(const void *a, const void *b);
1033

1034
	if (((iter->flags & GIT_ITERATOR_IGNORE_CASE) != 0) == (ignore_case != 0))
1035
		return 0;
1036

1037 1038 1039 1040 1041
	if (iter->type == GIT_ITERATOR_TYPE_EMPTY) {
		iter->flags = (iter->flags ^ GIT_ITERATOR_IGNORE_CASE);
		return 0;
	}

1042 1043
	scb = git__calloc(1, sizeof(spoolandsort_callbacks));
	GITERR_CHECK_ALLOC(scb);
1044

1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062
	ITERATOR_SET_CB(scb,spoolandsort);

	scb->orig      = iter->cb;
	scb->orig_type = iter->type;
	scb->position  = 0;

	entrycomp = ignore_case ? git_index_entry__cmp_icase : git_index_entry__cmp;

	if (git_vector_init(&scb->entries, 16, entrycomp) < 0 ||
		git_pool_init(&scb->entry_pool, sizeof(git_index_entry), 0) < 0 ||
		git_pool_init(&scb->string_pool, 1, 0) < 0 ||
		git_iterator_current(iter, &item) < 0)
		goto fail;

	while (item) {
		git_index_entry *clone = git_pool_malloc(&scb->entry_pool, 1);
		if (!clone)
			goto fail;
1063 1064 1065

		memcpy(clone, item, sizeof(git_index_entry));

1066 1067 1068 1069
		if (item->path) {
			clone->path = git_pool_strdup(&scb->string_pool, item->path);
			if (!clone->path)
				goto fail;
1070 1071
		}

1072 1073
		if (git_vector_insert(&scb->entries, clone) < 0)
			goto fail;
1074

1075 1076
		if (git_iterator_advance(iter, &item) < 0)
			goto fail;
1077 1078
	}

1079
	git_vector_sort(&scb->entries);
1080

1081
	iter->cb   = (git_iterator_callbacks *)scb;
1082 1083
	iter->type = GIT_ITERATOR_TYPE_SPOOLANDSORT;
	iter->flags ^= GIT_ITERATOR_IGNORE_CASE;
1084 1085

	return 0;
1086 1087 1088 1089

fail:
	spoolandsort_iterator__free_callbacks(scb);
	return -1;
1090
}
1091

1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107

void git_iterator_free(git_iterator *iter)
{
	if (iter == NULL)
		return;

	iter->cb->free(iter);

	git__free(iter->start);
	git__free(iter->end);

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

	git__free(iter);
}

1108 1109
git_index *git_iterator_index_get_index(git_iterator *iter)
{
1110
	if (iter->type == GIT_ITERATOR_TYPE_INDEX)
1111 1112
		return ((index_iterator *)iter)->index;

1113 1114
	if (iter->type == GIT_ITERATOR_TYPE_SPOOLANDSORT &&
		((spoolandsort_callbacks *)iter->cb)->orig_type == GIT_ITERATOR_TYPE_INDEX)
1115 1116
		return ((index_iterator *)iter)->index;

1117 1118 1119 1120 1121
	return NULL;
}

git_iterator_type_t git_iterator_inner_type(git_iterator *iter)
{
1122
	if (iter->type == GIT_ITERATOR_TYPE_SPOOLANDSORT)
1123
		return ((spoolandsort_callbacks *)iter->cb)->orig_type;
1124 1125 1126 1127

	return iter->type;
}

1128 1129 1130
int git_iterator_current_tree_entry(
	git_iterator *iter, const git_tree_entry **tree_entry)
{
1131
	*tree_entry = (iter->type != GIT_ITERATOR_TYPE_TREE) ? NULL :
1132
		tree_iterator__tree_entry((tree_iterator *)iter);
1133
	return 0;
1134 1135
}

1136 1137 1138 1139 1140 1141 1142 1143
int git_iterator_current_parent_tree(
	git_iterator *iter,
	const char *parent_path,
	const git_tree **tree_ptr)
{
	tree_iterator *ti = (tree_iterator *)iter;
	tree_iterator_frame *tf;
	const char *scan = parent_path;
1144
	int (*strncomp)(const char *a, const char *b, size_t sz);
1145

1146
	if (iter->type != GIT_ITERATOR_TYPE_TREE || ti->stack == NULL)
1147 1148
		goto notfound;

1149 1150 1151
	strncomp = ((iter->flags & GIT_ITERATOR_IGNORE_CASE) != 0) ?
		git__strncasecmp : git__strncmp;

1152 1153 1154 1155 1156 1157 1158 1159
	for (tf = ti->tail; tf != NULL; tf = tf->prev) {
		const git_tree_entry *te;

		if (!*scan) {
			*tree_ptr = tf->tree;
			return 0;
		}

1160 1161
		te = git_tree_entry_byindex(tf->tree,
			tf->icase_map ? (size_t)tf->icase_map[tf->index] : tf->index);
1162

1163
		if (strncomp(scan, te->filename, te->filename_len) != 0)
1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179
			goto notfound;

		scan += te->filename_len;

		if (*scan) {
			if (*scan != '/')
				goto notfound;
			scan++;
		}
	}

notfound:
	*tree_ptr = NULL;
	return 0;
}

1180 1181
int git_iterator_current_is_ignored(git_iterator *iter)
{
1182 1183
	workdir_iterator *wi = (workdir_iterator *)iter;

1184
	if (iter->type != GIT_ITERATOR_TYPE_WORKDIR)
1185 1186 1187 1188 1189 1190 1191 1192 1193
		return 0;

	if (wi->is_ignored != -1)
		return wi->is_ignored;

	if (git_ignore__lookup(&wi->ignores, wi->entry.path, &wi->is_ignored) < 0)
		wi->is_ignored = 1;

	return wi->is_ignored;
1194 1195 1196 1197 1198 1199 1200
}

int git_iterator_advance_into_directory(
	git_iterator *iter, const git_index_entry **entry)
{
	workdir_iterator *wi = (workdir_iterator *)iter;

1201
	if (iter->type == GIT_ITERATOR_TYPE_WORKDIR &&
1202
		wi->entry.path &&
1203 1204
		(wi->entry.mode == GIT_FILEMODE_TREE ||
		 wi->entry.mode == GIT_FILEMODE_COMMIT))
1205
	{
1206
		if (workdir_iterator__expand_dir(wi) < 0)
1207 1208 1209 1210
			/* if error loading or if empty, skip the directory. */
			return workdir_iterator__advance(iter, entry);
	}

1211
	return entry ? git_iterator_current(iter, entry) : 0;
1212
}
1213

1214
int git_iterator_cmp(git_iterator *iter, const char *path_prefix)
1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226
{
	const git_index_entry *entry;

	/* a "done" iterator is after every prefix */
	if (git_iterator_current(iter, &entry) < 0 ||
		entry == NULL)
		return 1;

	/* a NULL prefix is after any valid iterator */
	if (!path_prefix)
		return -1;

1227
	return iter->prefixcomp(entry->path, path_prefix);
1228 1229
}

1230 1231 1232 1233
int git_iterator_current_workdir_path(git_iterator *iter, git_buf **path)
{
	workdir_iterator *wi = (workdir_iterator *)iter;

1234
	if (iter->type != GIT_ITERATOR_TYPE_WORKDIR || !wi->entry.path)
1235 1236 1237 1238 1239 1240 1241
		*path = NULL;
	else
		*path = &wi->path;

	return 0;
}