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

#include "common.h"
#include "commit.h"
#include "tree.h"
11 12
#include "git2/repository.h"
#include "git2/object.h"
13

14
#define DEFAULT_TREE_SIZE 16
15
#define MAX_FILEMODE_BYTES 6
16

nulltoken committed
17
static bool valid_filemode(const int filemode)
18
{
nulltoken committed
19 20 21 22 23
	return (filemode == GIT_FILEMODE_TREE
		|| filemode == GIT_FILEMODE_BLOB
		|| filemode == GIT_FILEMODE_BLOB_EXECUTABLE
		|| filemode == GIT_FILEMODE_LINK
		|| filemode == GIT_FILEMODE_COMMIT);
24 25
}

26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
GIT_INLINE(git_filemode_t) normalize_filemode(git_filemode_t filemode)
{
	/* Tree bits set, but it's not a commit */
	if (filemode & GIT_FILEMODE_TREE && !(filemode & 0100000))
		return GIT_FILEMODE_TREE;

	/* If any of the x bits is set */
	if (filemode & 0111)
		return GIT_FILEMODE_BLOB_EXECUTABLE;

	/* 16XXXX means commit */
	if ((filemode & GIT_FILEMODE_COMMIT) == GIT_FILEMODE_COMMIT)
		return GIT_FILEMODE_COMMIT;

	/* 12XXXX means commit */
	if ((filemode & GIT_FILEMODE_LINK) == GIT_FILEMODE_LINK)
		return GIT_FILEMODE_LINK;

	/* Otherwise, return a blob */
	return GIT_FILEMODE_BLOB;
}

48 49
static int valid_entry_name(const char *filename)
{
50 51 52 53 54 55
	return *filename != '\0' &&
		strchr(filename, '/') == NULL &&
		(*filename != '.' ||
		 (strcmp(filename, ".") != 0 &&
		  strcmp(filename, "..") != 0 &&
		  strcmp(filename, DOT_GIT) != 0));
56 57
}

58
static int entry_sort_cmp(const void *a, const void *b)
59
{
60 61 62
	const git_tree_entry *e1 = (const git_tree_entry *)a;
	const git_tree_entry *e2 = (const git_tree_entry *)b;

63
	return git_path_cmp(
64
		e1->filename, e1->filename_len, git_tree_entry__is_tree(e1),
65 66
		e2->filename, e2->filename_len, git_tree_entry__is_tree(e2),
		git__strncmp);
67 68
}

69
int git_tree_entry_cmp(const git_tree_entry *e1, const git_tree_entry *e2)
70
{
71
	return entry_sort_cmp(e1, e2);
72 73
}

74
int git_tree_entry_icmp(const git_tree_entry *e1, const git_tree_entry *e2)
75
{
76 77 78 79
	return git_path_cmp(
		e1->filename, e1->filename_len, git_tree_entry__is_tree(e1),
		e2->filename, e2->filename_len, git_tree_entry__is_tree(e2),
		git__strncasecmp);
80 81
}

82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
static git_tree_entry *alloc_entry(const char *filename)
{
	git_tree_entry *entry = NULL;
	size_t filename_len = strlen(filename);

	entry = git__malloc(sizeof(git_tree_entry) + filename_len + 1);
	if (!entry)
		return NULL;

	memset(entry, 0x0, sizeof(git_tree_entry));
	memcpy(entry->filename, filename, filename_len);
	entry->filename[filename_len] = 0;
	entry->filename_len = filename_len;

	return entry;
}
98

99 100 101 102 103
struct tree_key_search {
	const char *filename;
	size_t filename_len;
};

104
static int homing_search_cmp(const void *key, const void *array_member)
105
{
106 107
	const struct tree_key_search *ksearch = key;
	const git_tree_entry *entry = array_member;
108

109 110
	const size_t len1 = ksearch->filename_len;
	const size_t len2 = entry->filename_len;
111

112 113 114 115 116
	return memcmp(
		ksearch->filename,
		entry->filename,
		len1 < len2 ? len1 : len2
	);
117 118
}

119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138
/*
 * Search for an entry in a given tree.
 *
 * Note that this search is performed in two steps because
 * of the way tree entries are sorted internally in git:
 *
 * Entries in a tree are not sorted alphabetically; two entries
 * with the same root prefix will have different positions
 * depending on whether they are folders (subtrees) or normal files.
 *
 * Consequently, it is not possible to find an entry on the tree
 * with a binary search if you don't know whether the filename
 * you're looking for is a folder or a normal file.
 *
 * To work around this, we first perform a homing binary search
 * on the tree, using the minimal length root prefix of our filename.
 * Once the comparisons for this homing search start becoming
 * ambiguous because of folder vs file sorting, we look linearly
 * around the area for our target file.
 */
139
static int tree_key_search(
140
	size_t *at_pos, git_vector *entries, const char *filename, size_t filename_len)
141
{
142 143
	struct tree_key_search ksearch;
	const git_tree_entry *entry;
144
	size_t homing, i;
145

146
	ksearch.filename = filename;
147
	ksearch.filename_len = filename_len;
148

149 150
	/* Initial homing search; find an entry on the tree with
	 * the same prefix as the filename we're looking for */
151 152
	if (git_vector_bsearch2(&homing, entries, &homing_search_cmp, &ksearch) < 0)
		return GIT_ENOTFOUND;
153 154 155

	/* We found a common prefix. Look forward as long as
	 * there are entries that share the common prefix */
156
	for (i = homing; i < entries->length; ++i) {
157 158
		entry = entries->contents[i];

159
		if (homing_search_cmp(&ksearch, entry) < 0)
160 161
			break;

162
		if (entry->filename_len == filename_len &&
163 164 165 166 167 168
			memcmp(filename, entry->filename, filename_len) == 0) {
			if (at_pos)
				*at_pos = i;

			return 0;
		}
169
	}
170

171 172
	/* If we haven't found our filename yet, look backwards
	 * too as long as we have entries with the same prefix */
173 174
	if (homing > 0) {
		i = homing - 1;
175

176 177
		do {
			entry = entries->contents[i];
178

179 180 181 182 183 184 185 186 187 188 189
			if (homing_search_cmp(&ksearch, entry) > 0)
				break;

			if (entry->filename_len == filename_len &&
				memcmp(filename, entry->filename, filename_len) == 0) {
				if (at_pos)
					*at_pos = i;

				return 0;
			}
		} while (i-- > 0);
190 191 192
	}

	/* The filename doesn't exist at all */
193
	return GIT_ENOTFOUND;
194 195
}

196 197
void git_tree_entry_free(git_tree_entry *entry)
{
198 199 200
	if (entry == NULL)
		return;

201 202 203
	git__free(entry);
}

204
git_tree_entry *git_tree_entry_dup(const git_tree_entry *entry)
205 206 207 208 209 210 211 212 213 214 215 216 217
{
	size_t total_size;
	git_tree_entry *copy;

	assert(entry);

	total_size = sizeof(git_tree_entry) + entry->filename_len + 1;

	copy = git__malloc(total_size);
	if (!copy)
		return NULL;

	memcpy(copy, entry, total_size);
218

219 220 221
	return copy;
}

Vicent Marti committed
222
void git_tree__free(git_tree *tree)
223
{
224 225
	size_t i;
	git_tree_entry *e;
226

227
	git_vector_foreach(&tree->entries, i, e)
228
		git_tree_entry_free(e);
229

230
	git_vector_free(&tree->entries);
231
	git__free(tree);
232 233
}

Russell Belfer committed
234
const git_oid *git_tree_id(const git_tree *t)
235
{
Russell Belfer committed
236 237 238 239 240 241
	return git_object_id((const git_object *)t);
}

git_repository *git_tree_owner(const git_tree *t)
{
	return git_object_owner((const git_object *)t);
242 243
}

244
git_filemode_t git_tree_entry_filemode(const git_tree_entry *entry)
245
{
246
	return (git_filemode_t)entry->attr;
247 248
}

249
const char *git_tree_entry_name(const git_tree_entry *entry)
250
{
251
	assert(entry);
252 253
	return entry->filename;
}
254

255
const git_oid *git_tree_entry_id(const git_tree_entry *entry)
256
{
257
	assert(entry);
258
	return &entry->oid;
259 260
}

261 262 263 264 265 266 267 268 269 270 271 272
git_otype git_tree_entry_type(const git_tree_entry *entry)
{
	assert(entry);

	if (S_ISGITLINK(entry->attr))
		return GIT_OBJ_COMMIT;
	else if (S_ISDIR(entry->attr))
		return GIT_OBJ_TREE;
	else
		return GIT_OBJ_BLOB;
}

Vicent Martí committed
273 274 275 276
int git_tree_entry_to_object(
	git_object **object_out,
	git_repository *repo,
	const git_tree_entry *entry)
277
{
Vicent Marti committed
278
	assert(entry && object_out);
Vicent Marti committed
279
	return git_object_lookup(object_out, repo, &entry->oid, GIT_OBJ_ANY);
280 281
}

282 283
static const git_tree_entry *entry_fromname(
	git_tree *tree, const char *name, size_t name_len)
284
{
285 286 287
	size_t idx;

	if (tree_key_search(&idx, &tree->entries, name, name_len) < 0)
288 289 290
		return NULL;

	return git_vector_get(&tree->entries, idx);
291 292
}

293 294
const git_tree_entry *git_tree_entry_byname(
	git_tree *tree, const char *filename)
295 296 297 298 299
{
	assert(tree && filename);
	return entry_fromname(tree, filename, strlen(filename));
}

300 301
const git_tree_entry *git_tree_entry_byindex(
	git_tree *tree, size_t idx)
302
{
303
	assert(tree);
304
	return git_vector_get(&tree->entries, idx);
305 306
}

307 308
const git_tree_entry *git_tree_entry_byoid(
	const git_tree *tree, const git_oid *oid)
309
{
310 311
	size_t i;
	const git_tree_entry *e;
312 313 314 315 316 317 318 319 320 321 322

	assert(tree);

	git_vector_foreach(&tree->entries, i, e) {
		if (memcmp(&e->oid.id, &oid->id, sizeof(oid->id)) == 0)
			return e;
	}

	return NULL;
}

Vicent Martí committed
323
int git_tree__prefix_position(git_tree *tree, const char *path)
324 325 326
{
	git_vector *entries = &tree->entries;
	struct tree_key_search ksearch;
327
	size_t at_pos;
328

329 330 331
	if (!path)
		return 0;

332 333 334 335
	ksearch.filename = path;
	ksearch.filename_len = strlen(path);

	/* Find tree entry with appropriate prefix */
336
	git_vector_bsearch2(&at_pos, entries, &homing_search_cmp, &ksearch);
337 338 339 340 341 342 343 344 345 346 347 348 349

	for (; at_pos < entries->length; ++at_pos) {
		const git_tree_entry *entry = entries->contents[at_pos];
		if (homing_search_cmp(&ksearch, entry) < 0)
			break;
	}

	for (; at_pos > 0; --at_pos) {
		const git_tree_entry *entry = entries->contents[at_pos - 1];
		if (homing_search_cmp(&ksearch, entry) > 0)
			break;
	}

350
	return (int)at_pos;
351 352
}

353
size_t git_tree_entrycount(const git_tree *tree)
354
{
355
	assert(tree);
356
	return tree->entries.length;
357 358
}

359 360 361
unsigned int git_treebuilder_entrycount(git_treebuilder *bld)
{
	assert(bld);
362
	return (unsigned int)bld->entrycount;
363 364
}

365
static int tree_error(const char *str, const char *path)
366
{
367 368 369 370
	if (path)
		giterr_set(GITERR_TREE, "%s - %s", str, path);
	else
		giterr_set(GITERR_TREE, "%s", str);
371 372
	return -1;
}
373

374 375 376 377
static int tree_parse_buffer(git_tree *tree, const char *buffer, const char *buffer_end)
{
	if (git_vector_init(&tree->entries, DEFAULT_TREE_SIZE, entry_sort_cmp) < 0)
		return -1;
378

379 380
	while (buffer < buffer_end) {
		git_tree_entry *entry;
381
		int attr;
382

383
		if (git__strtol32(&attr, buffer, &buffer, 8) < 0 || !buffer)
384
			return tree_error("Failed to parse tree. Can't parse filemode", NULL);
385

386 387
		attr = normalize_filemode(attr); /* make sure to normalize the filemode */

388
		if (*buffer++ != ' ')
389
			return tree_error("Failed to parse tree. Object is corrupted", NULL);
390

391
		if (memchr(buffer, 0, buffer_end - buffer) == NULL)
392
			return tree_error("Failed to parse tree. Object is corrupted", NULL);
393

394 395 396 397 398
		/** Allocate the entry and store it in the entries vector */
		{
			entry = alloc_entry(buffer);
			GITERR_CHECK_ALLOC(entry);

399 400
			if (git_vector_insert(&tree->entries, entry) < 0) {
				git__free(entry);
401
				return -1;
402
			}
403 404 405

			entry->attr = attr;
		}
406

407 408
		while (buffer < buffer_end && *buffer != 0)
			buffer++;
409

410
		buffer++;
411

Vicent Marti committed
412
		git_oid_fromraw(&entry->oid, (const unsigned char *)buffer);
413 414 415
		buffer += GIT_OID_RAWSZ;
	}

416
	return 0;
417
}
418

Vicent Marti committed
419
int git_tree__parse(git_tree *tree, git_odb_object *obj)
420
{
Vicent Marti committed
421 422
	assert(tree);
	return tree_parse_buffer(tree, (char *)obj->raw.data, (char *)obj->raw.data + obj->raw.len);
423 424
}

425
static size_t find_next_dir(const char *dirname, git_index *index, size_t start)
426
{
427
	size_t dirlen, i, entries = git_index_entrycount(index);
428 429 430

	dirlen = strlen(dirname);
	for (i = start; i < entries; ++i) {
Ben Straub committed
431
		const git_index_entry *entry = git_index_get_byindex(index, i);
432 433 434 435 436 437 438 439 440 441
		if (strlen(entry->path) < dirlen ||
		    memcmp(entry->path, dirname, dirlen) ||
			(dirlen > 0 && entry->path[dirlen] != '/')) {
			break;
		}
	}

	return i;
}

442 443 444 445
static int append_entry(
	git_treebuilder *bld,
	const char *filename,
	const git_oid *id,
nulltoken committed
446
	git_filemode_t filemode)
447 448 449
{
	git_tree_entry *entry;

450
	if (!valid_entry_name(filename))
451
		return tree_error("Failed to insert entry. Invalid name for a tree entry", filename);
452

453
	entry = alloc_entry(filename);
454
	GITERR_CHECK_ALLOC(entry);
455 456

	git_oid_cpy(&entry->oid, id);
nulltoken committed
457
	entry->attr = (uint16_t)filemode;
458

459 460
	if (git_vector_insert(&bld->entries, entry) < 0) {
		git__free(entry);
461
		return -1;
462
	}
463

464
	bld->entrycount++;
465
	return 0;
466 467
}

468 469 470 471 472
static int write_tree(
	git_oid *oid,
	git_repository *repo,
	git_index *index,
	const char *dirname,
473
	size_t start)
474
{
475
	git_treebuilder *bld = NULL;
476
	size_t i, entries = git_index_entrycount(index);
477 478
	int error;
	size_t dirname_len = strlen(dirname);
479 480 481 482 483
	const git_tree_cache *cache;

	cache = git_tree_cache_get(index->tree, dirname);
	if (cache != NULL && cache->entries >= 0){
		git_oid_cpy(oid, &cache->oid);
484
		return (int)find_next_dir(dirname, index, start);
485
	}
486

487
	if ((error = git_treebuilder_create(&bld, NULL)) < 0 || bld == NULL)
488
		return -1;
489

490 491 492 493 494 495
	/*
	 * This loop is unfortunate, but necessary. The index doesn't have
	 * any directores, so we need to handle that manually, and we
	 * need to keep track of the current position.
	 */
	for (i = start; i < entries; ++i) {
Ben Straub committed
496
		const git_index_entry *entry = git_index_get_byindex(index, i);
497
		const char *filename, *next_slash;
498 499 500 501 502 503 504 505 506 507 508 509

	/*
	 * If we've left our (sub)tree, exit the loop and return. The
	 * first check is an early out (and security for the
	 * third). The second check is a simple prefix comparison. The
	 * third check catches situations where there is a directory
	 * win32/sys and a file win32mmap.c. Without it, the following
	 * code believes there is a file win32/mmap.c
	 */
		if (strlen(entry->path) < dirname_len ||
		    memcmp(entry->path, dirname, dirname_len) ||
		    (dirname_len > 0 && entry->path[dirname_len] != '/')) {
510
			break;
511
		}
512

513 514 515 516 517 518 519 520 521 522
		filename = entry->path + dirname_len;
		if (*filename == '/')
			filename++;
		next_slash = strchr(filename, '/');
		if (next_slash) {
			git_oid sub_oid;
			int written;
			char *subdir, *last_comp;

			subdir = git__strndup(entry->path, next_slash - entry->path);
523
			GITERR_CHECK_ALLOC(subdir);
524

525
			/* Write out the subtree */
526
			written = write_tree(&sub_oid, repo, index, subdir, i);
527
			if (written < 0) {
528 529
				tree_error("Failed to write subtree", subdir);
				git__free(subdir);
530
				goto on_error;
531 532
			} else {
				i = written - 1; /* -1 because of the loop increment */
533
			}
534

535 536 537 538 539 540 541 542 543 544 545 546
			/*
			 * We need to figure out what we want toinsert
			 * into this tree. If we're traversing
			 * deps/zlib/, then we only want to write
			 * 'zlib' into the tree.
			 */
			last_comp = strrchr(subdir, '/');
			if (last_comp) {
				last_comp++; /* Get rid of the '/' */
			} else {
				last_comp = subdir;
			}
547

548
			error = append_entry(bld, last_comp, &sub_oid, S_IFDIR);
549
			git__free(subdir);
550
			if (error < 0)
551
				goto on_error;
552
		} else {
553
			error = append_entry(bld, filename, &entry->oid, entry->mode);
554
			if (error < 0)
555
				goto on_error;
556
		}
557
	}
558

559 560
	if (git_treebuilder_write(oid, repo, bld) < 0)
		goto on_error;
561

562
	git_treebuilder_free(bld);
563
	return (int)i;
564

565 566 567
on_error:
	git_treebuilder_free(bld);
	return -1;
568 569
}

570 571
int git_tree__write_index(
	git_oid *oid, git_index *index, git_repository *repo)
572
{
573
	int ret;
574
	bool old_ignore_case = false;
575

576
	assert(oid && index && repo);
577

578 579 580 581 582 583
	if (git_index_has_conflicts(index)) {
		giterr_set(GITERR_INDEX,
			"Cannot create a tree from a not fully merged index.");
		return GIT_EUNMERGED;
	}

584 585
	if (index->tree != NULL && index->tree->entries >= 0) {
		git_oid_cpy(oid, &index->tree->oid);
586
		return 0;
587 588
	}

589
	/* The tree cache didn't help us; we'll have to write
590
	 * out a tree. If the index is ignore_case, we must
591 592 593 594 595
	 * make it case-sensitive for the duration of the tree-write
	 * operation. */

	if (index->ignore_case) {
		old_ignore_case = true;
596
		git_index__set_ignore_case(index, false);
597 598
	}

599
	ret = write_tree(oid, repo, index, "", 0);
600 601

	if (old_ignore_case)
602
		git_index__set_ignore_case(index, true);
603

604
	return ret < 0 ? ret : 0;
605
}
606 607 608 609

int git_treebuilder_create(git_treebuilder **builder_p, const git_tree *source)
{
	git_treebuilder *bld;
610
	size_t i, source_entries = DEFAULT_TREE_SIZE;
611 612 613 614

	assert(builder_p);

	bld = git__calloc(1, sizeof(git_treebuilder));
615
	GITERR_CHECK_ALLOC(bld);
616 617 618 619

	if (source != NULL)
		source_entries = source->entries.length;

620 621
	if (git_vector_init(&bld->entries, source_entries, entry_sort_cmp) < 0)
		goto on_error;
622 623

	if (source != NULL) {
624
		git_tree_entry *entry_src;
625

626
		git_vector_foreach(&source->entries, i, entry_src) {
627 628 629
			if (append_entry(
				bld, entry_src->filename,
				&entry_src->oid,
630
				entry_src->attr) < 0)
631
				goto on_error;
632 633 634 635
		}
	}

	*builder_p = bld;
636 637 638 639 640
	return 0;

on_error:
	git_treebuilder_free(bld);
	return -1;
641 642
}

643 644 645 646 647
int git_treebuilder_insert(
	const git_tree_entry **entry_out,
	git_treebuilder *bld,
	const char *filename,
	const git_oid *id,
nulltoken committed
648
	git_filemode_t filemode)
649 650
{
	git_tree_entry *entry;
651
	size_t pos;
652 653 654

	assert(bld && id && filename);

nulltoken committed
655
	if (!valid_filemode(filemode))
656
		return tree_error("Failed to insert entry. Invalid filemode for file", filename);
657

658
	if (!valid_entry_name(filename))
659
		return tree_error("Failed to insert entry. Invalid name for a tree entry", filename);
660

661
	if (!tree_key_search(&pos, &bld->entries, filename, strlen(filename))) {
662
		entry = git_vector_get(&bld->entries, pos);
663
		if (entry->removed) {
664
			entry->removed = 0;
665 666
			bld->entrycount++;
		}
667
	} else {
668
		entry = alloc_entry(filename);
669
		GITERR_CHECK_ALLOC(entry);
670

671 672
		if (git_vector_insert(&bld->entries, entry) < 0) {
			git__free(entry);
673
			return -1;
674
		}
675 676

		bld->entrycount++;
677 678
	}

679 680 681 682
	git_oid_cpy(&entry->oid, id);
	entry->attr = filemode;

	if (entry_out)
683 684
		*entry_out = entry;

685
	return 0;
686 687
}

688
static git_tree_entry *treebuilder_get(git_treebuilder *bld, const char *filename)
689
{
690
	size_t idx;
691 692 693 694
	git_tree_entry *entry;

	assert(bld && filename);

695
	if (tree_key_search(&idx, &bld->entries, filename, strlen(filename)) < 0)
696 697 698 699 700 701 702 703 704
		return NULL;

	entry = git_vector_get(&bld->entries, idx);
	if (entry->removed)
		return NULL;

	return entry;
}

705 706 707 708 709
const git_tree_entry *git_treebuilder_get(git_treebuilder *bld, const char *filename)
{
	return treebuilder_get(bld, filename);
}

710 711
int git_treebuilder_remove(git_treebuilder *bld, const char *filename)
{
712
	git_tree_entry *remove_ptr = treebuilder_get(bld, filename);
713 714

	if (remove_ptr == NULL || remove_ptr->removed)
715
		return tree_error("Failed to remove entry. File isn't in the tree", filename);
716 717

	remove_ptr->removed = 1;
718
	bld->entrycount--;
719
	return 0;
720 721 722 723
}

int git_treebuilder_write(git_oid *oid, git_repository *repo, git_treebuilder *bld)
{
724 725
	int error = 0;
	size_t i;
726
	git_buf tree = GIT_BUF_INIT;
727
	git_odb *odb;
728 729 730

	assert(bld);

731
	git_vector_sort(&bld->entries);
732

733
	/* Grow the buffer beforehand to an estimated size */
734
	error = git_buf_grow(&tree, bld->entries.length * 72);
735

736 737
	for (i = 0; i < bld->entries.length && !error; ++i) {
		git_tree_entry *entry = git_vector_get(&bld->entries, i);
738 739 740 741

		if (entry->removed)
			continue;

742 743 744
		git_buf_printf(&tree, "%o ", entry->attr);
		git_buf_put(&tree, entry->filename, entry->filename_len + 1);
		git_buf_put(&tree, (char *)entry->oid.id, GIT_OID_RAWSZ);
745

746 747 748
		if (git_buf_oom(&tree))
			error = -1;
	}
749

750 751 752
	if (!error &&
		!(error = git_repository_odb__weakptr(&odb, repo)))
		error = git_odb_write(oid, odb, tree.ptr, tree.size, GIT_OBJ_TREE);
753

754
	git_buf_free(&tree);
755
	return error;
756 757
}

758 759 760 761
void git_treebuilder_filter(
	git_treebuilder *bld,
	git_treebuilder_filter_cb filter,
	void *payload)
762
{
763 764
	size_t i;
	git_tree_entry *entry;
765 766 767

	assert(bld && filter);

768
	git_vector_foreach(&bld->entries, i, entry) {
769
		if (!entry->removed && filter(entry, payload)) {
770
			entry->removed = 1;
771 772
			bld->entrycount--;
		}
773 774 775 776 777
	}
}

void git_treebuilder_clear(git_treebuilder *bld)
{
778 779 780
	size_t i;
	git_tree_entry *e;

781 782
	assert(bld);

783
	git_vector_foreach(&bld->entries, i, e)
784
		git_tree_entry_free(e);
785 786

	git_vector_clear(&bld->entries);
787
	bld->entrycount = 0;
788 789 790 791
}

void git_treebuilder_free(git_treebuilder *bld)
{
792 793 794
	if (bld == NULL)
		return;

795 796
	git_treebuilder_clear(bld);
	git_vector_free(&bld->entries);
797
	git__free(bld);
798 799
}

800 801 802 803 804 805 806 807 808 809 810
static size_t subpath_len(const char *path)
{
	const char *slash_pos = strchr(path, '/');
	if (slash_pos == NULL)
		return strlen(path);

	return slash_pos - path;
}

int git_tree_entry_bypath(
	git_tree_entry **entry_out,
811
	git_tree *root,
812
	const char *path)
813
{
814
	int error = 0;
815
	git_tree *subtree;
816 817
	const git_tree_entry *entry;
	size_t filename_len;
818

819 820 821
	/* Find how long is the current path component (i.e.
	 * the filename between two slashes */
	filename_len = subpath_len(path);
822

823 824 825
	if (filename_len == 0) {
		giterr_set(GITERR_TREE, "Invalid tree path given");
		return GIT_ENOTFOUND;
826
	}
827

828
	entry = entry_fromname(root, path, filename_len);
829

830 831
	if (entry == NULL) {
		giterr_set(GITERR_TREE,
832
			"The path '%s' does not exist in the given tree", path);
833
		return GIT_ENOTFOUND;
834
	}
835

836
	switch (path[filename_len]) {
837
	case '/':
838 839 840 841 842
		/* If there are more components in the path...
		 * then this entry *must* be a tree */
		if (!git_tree_entry__is_tree(entry)) {
			giterr_set(GITERR_TREE,
				"The path '%s' does not exist in the given tree", path);
843
			return GIT_ENOTFOUND;
844 845 846 847 848 849 850 851 852 853 854
		}

		/* If there's only a slash left in the path, we 
		 * return the current entry; otherwise, we keep
		 * walking down the path */
		if (path[filename_len + 1] != '\0')
			break;

	case '\0':
		/* If there are no more components in the path, return
		 * this entry */
855
		*entry_out = git_tree_entry_dup(entry);
856 857
		return 0;
	}
858

859
	if (git_tree_lookup(&subtree, root->object.repo, &entry->oid) < 0)
860
		return -1;
861

862 863
	error = git_tree_entry_bypath(
		entry_out,
864
		subtree,
865
		path + filename_len + 1
866
	);
867

868
	git_tree_free(subtree);
869 870 871
	return error;
}

872
static int tree_walk(
Ben Straub committed
873
	const git_tree *tree,
874
	git_treewalk_cb callback,
875
	git_buf *path,
876 877
	void *payload,
	bool preorder)
878
{
879
	int error = 0;
880
	size_t i;
881
	const git_tree_entry *entry;
882

883
	git_vector_foreach(&tree->entries, i, entry) {
884 885 886 887
		if (preorder) {
			error = callback(path->ptr, entry, payload);
			if (error > 0)
				continue;
888 889
			if (error < 0) {
				giterr_clear();
890
				return GIT_EUSER;
891
			}
892
		}
893

Vicent Martí committed
894
		if (git_tree_entry__is_tree(entry)) {
895
			git_tree *subtree;
nulltoken committed
896
			size_t path_len = git_buf_len(path);
897

898 899
			if ((error = git_tree_lookup(
				&subtree, tree->object.repo, &entry->oid)) < 0)
900
				break;
901

902 903 904
			/* append the next entry to the path */
			git_buf_puts(path, entry->filename);
			git_buf_putc(path, '/');
905

906
			if (git_buf_oom(path))
907
				return -1;
908

909 910 911
			error = tree_walk(subtree, callback, path, payload, preorder);
			if (error != 0)
				break;
912

913
			git_buf_truncate(path, path_len);
914
			git_tree_free(subtree);
915
		}
916

917
		if (!preorder && callback(path->ptr, entry, payload) < 0) {
918
			giterr_clear();
919
			error = GIT_EUSER;
920
			break;
921
		}
922 923
	}

924
	return error;
925 926
}

927
int git_tree_walk(
Ben Straub committed
928
	const git_tree *tree,
929 930 931
	git_treewalk_mode mode,
	git_treewalk_cb callback,
	void *payload)
932
{
933
	int error = 0;
934
	git_buf root_path = GIT_BUF_INIT;
935

936
	if (mode != GIT_TREEWALK_POST && mode != GIT_TREEWALK_PRE) {
937 938
		giterr_set(GITERR_INVALID, "Invalid walking mode for tree walk");
		return -1;
939
	}
940

941 942 943
	error = tree_walk(
		tree, callback, &root_path, payload, (mode == GIT_TREEWALK_PRE));

944 945 946
	git_buf_free(&root_path);

	return error;
947
}
948