tree.c 31.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
#include "fileops.h"
14 15
#include "tree-cache.h"
#include "index.h"
16

17
#define DEFAULT_TREE_SIZE 16
18
#define MAX_FILEMODE_BYTES 6
19

20 21 22
#define TREE_ENTRY_CHECK_NAMELEN(n) \
	if (n > UINT16_MAX) { giterr_set(GITERR_INVALID, "tree entry path too long"); }

nulltoken committed
23
static bool valid_filemode(const int filemode)
24
{
nulltoken committed
25 26 27 28 29
	return (filemode == GIT_FILEMODE_TREE
		|| filemode == GIT_FILEMODE_BLOB
		|| filemode == GIT_FILEMODE_BLOB_EXECUTABLE
		|| filemode == GIT_FILEMODE_LINK
		|| filemode == GIT_FILEMODE_COMMIT);
30 31
}

32 33 34
GIT_INLINE(git_filemode_t) normalize_filemode(git_filemode_t filemode)
{
	/* Tree bits set, but it's not a commit */
35
	if (GIT_MODE_TYPE(filemode) == GIT_FILEMODE_TREE)
36 37
		return GIT_FILEMODE_TREE;

38
	/* If any of the x bits are set */
39
	if (GIT_PERMS_IS_EXEC(filemode))
40 41 42
		return GIT_FILEMODE_BLOB_EXECUTABLE;

	/* 16XXXX means commit */
43
	if (GIT_MODE_TYPE(filemode) == GIT_FILEMODE_COMMIT)
44 45
		return GIT_FILEMODE_COMMIT;

46
	/* 12XXXX means symlink */
47
	if (GIT_MODE_TYPE(filemode) == GIT_FILEMODE_LINK)
48 49 50 51 52 53
		return GIT_FILEMODE_LINK;

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

54
static int valid_entry_name(git_repository *repo, const char *filename)
55
{
56
	return *filename != '\0' &&
57 58
		git_path_isvalid(repo, filename,
		GIT_PATH_REJECT_TRAVERSAL | GIT_PATH_REJECT_DOT_GIT | GIT_PATH_REJECT_SLASH);
59 60
}

61
static int entry_sort_cmp(const void *a, const void *b)
62
{
63 64 65
	const git_tree_entry *e1 = (const git_tree_entry *)a;
	const git_tree_entry *e2 = (const git_tree_entry *)b;

66
	return git_path_cmp(
67
		e1->filename, e1->filename_len, git_tree_entry__is_tree(e1),
68 69
		e2->filename, e2->filename_len, git_tree_entry__is_tree(e2),
		git__strncmp);
70 71
}

72
int git_tree_entry_cmp(const git_tree_entry *e1, const git_tree_entry *e2)
73
{
74
	return entry_sort_cmp(e1, e2);
75 76
}

77
int git_tree_entry_icmp(const git_tree_entry *e1, const git_tree_entry *e2)
78
{
79 80 81 82
	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);
83 84
}

85
/**
86 87
 * Allocate a new self-contained entry, with enough space after it to
 * store the filename and the id.
88
 */
89
static git_tree_entry *alloc_entry(const char *filename, size_t filename_len, const git_oid *id)
90 91
{
	git_tree_entry *entry = NULL;
92
	size_t tree_len;
93

94
	TREE_ENTRY_CHECK_NAMELEN(filename_len);
95

96 97 98
	if (GIT_ADD_SIZET_OVERFLOW(&tree_len, sizeof(git_tree_entry), filename_len) ||
	    GIT_ADD_SIZET_OVERFLOW(&tree_len, tree_len, 1) ||
	    GIT_ADD_SIZET_OVERFLOW(&tree_len, tree_len, GIT_OID_RAWSZ))
99 100
		return NULL;

101
	entry = git__calloc(1, tree_len);
102
	if (!entry)
103 104
		return NULL;

105
	{
106 107 108 109 110 111 112 113 114 115 116 117
		char *filename_ptr;
		void *id_ptr;

		filename_ptr = ((char *) entry) + sizeof(git_tree_entry);
		memcpy(filename_ptr, filename, filename_len);
		entry->filename = filename_ptr;

		id_ptr = filename_ptr + filename_len + 1;
		git_oid_cpy(id_ptr, id);
		entry->oid = id_ptr;
	}

118
	entry->filename_len = (uint16_t)filename_len;
119 120 121 122

	return entry;
}

123 124
struct tree_key_search {
	const char *filename;
125
	uint16_t filename_len;
126 127
};

128
static int homing_search_cmp(const void *key, const void *array_member)
129
{
130 131
	const struct tree_key_search *ksearch = key;
	const git_tree_entry *entry = array_member;
132

133 134
	const uint16_t len1 = ksearch->filename_len;
	const uint16_t len2 = entry->filename_len;
135

136 137 138 139 140
	return memcmp(
		ksearch->filename,
		entry->filename,
		len1 < len2 ? len1 : len2
	);
141 142
}

143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162
/*
 * 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.
 */
163
static int tree_key_search(
164 165 166 167
	size_t *at_pos,
	const git_tree *tree,
	const char *filename,
	size_t filename_len)
168
{
169 170
	struct tree_key_search ksearch;
	const git_tree_entry *entry;
171
	size_t homing, i;
172

173 174
	TREE_ENTRY_CHECK_NAMELEN(filename_len);

175
	ksearch.filename = filename;
176
	ksearch.filename_len = (uint16_t)filename_len;
177

178 179
	/* Initial homing search; find an entry on the tree with
	 * the same prefix as the filename we're looking for */
180 181 182

	if (git_array_search(&homing,
		tree->entries, &homing_search_cmp, &ksearch) < 0)
183
		return GIT_ENOTFOUND; /* just a signal error; not passed back to user */
184 185 186

	/* We found a common prefix. Look forward as long as
	 * there are entries that share the common prefix */
187 188
	for (i = homing; i < tree->entries.size; ++i) {
		entry = git_array_get(tree->entries, i);
189

190
		if (homing_search_cmp(&ksearch, entry) < 0)
191 192
			break;

193
		if (entry->filename_len == filename_len &&
194 195 196 197 198 199
			memcmp(filename, entry->filename, filename_len) == 0) {
			if (at_pos)
				*at_pos = i;

			return 0;
		}
200
	}
201

202 203
	/* If we haven't found our filename yet, look backwards
	 * too as long as we have entries with the same prefix */
204 205
	if (homing > 0) {
		i = homing - 1;
206

207
		do {
208
			entry = git_array_get(tree->entries, i);
209

210 211 212 213 214 215 216 217 218 219 220
			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);
221 222 223
	}

	/* The filename doesn't exist at all */
224
	return GIT_ENOTFOUND;
225 226
}

227 228
void git_tree_entry_free(git_tree_entry *entry)
{
229
	if (entry == NULL)
230 231
		return;

232 233 234
	git__free(entry);
}

235
int git_tree_entry_dup(git_tree_entry **dest, const git_tree_entry *source)
236
{
237 238
	git_tree_entry *cpy;

239
	assert(source);
240

241 242
	cpy = alloc_entry(source->filename, source->filename_len, source->oid);
	if (cpy == NULL)
243
		return -1;
244

245 246 247
	cpy->attr = source->attr;

	*dest = cpy;
248
	return 0;
249 250
}

251
void git_tree__free(void *_tree)
252
{
253
	git_tree *tree = _tree;
254

255
	git_odb_object_free(tree->odb_obj);
256
	git_array_clear(tree->entries);
257
	git__free(tree);
258 259
}

260
git_filemode_t git_tree_entry_filemode(const git_tree_entry *entry)
261
{
262 263 264 265 266 267
	return normalize_filemode(entry->attr);
}

git_filemode_t git_tree_entry_filemode_raw(const git_tree_entry *entry)
{
	return entry->attr;
268 269
}

270
const char *git_tree_entry_name(const git_tree_entry *entry)
271
{
272
	assert(entry);
273 274
	return entry->filename;
}
275

276
const git_oid *git_tree_entry_id(const git_tree_entry *entry)
277
{
278
	assert(entry);
279
	return entry->oid;
280 281
}

282 283 284 285 286 287 288 289 290 291 292 293
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
294 295 296 297
int git_tree_entry_to_object(
	git_object **object_out,
	git_repository *repo,
	const git_tree_entry *entry)
298
{
Vicent Marti committed
299
	assert(entry && object_out);
300
	return git_object_lookup(object_out, repo, entry->oid, GIT_OBJ_ANY);
301 302
}

303
static const git_tree_entry *entry_fromname(
304
	const git_tree *tree, const char *name, size_t name_len)
305
{
306 307
	size_t idx;

308
	if (tree_key_search(&idx, tree, name, name_len) < 0)
309 310
		return NULL;

311
	return git_array_get(tree->entries, idx);
312 313
}

314
const git_tree_entry *git_tree_entry_byname(
315
	const git_tree *tree, const char *filename)
316 317
{
	assert(tree && filename);
318

319 320 321
	return entry_fromname(tree, filename, strlen(filename));
}

322
const git_tree_entry *git_tree_entry_byindex(
323
	const git_tree *tree, size_t idx)
324
{
325
	assert(tree);
326
	return git_array_get(tree->entries, idx);
327 328
}

329 330
const git_tree_entry *git_tree_entry_byid(
	const git_tree *tree, const git_oid *id)
331
{
332 333
	size_t i;
	const git_tree_entry *e;
334 335 336

	assert(tree);

337
	git_array_foreach(tree->entries, i, e) {
338
		if (memcmp(&e->oid->id, &id->id, sizeof(id->id)) == 0)
339 340 341 342 343 344
			return e;
	}

	return NULL;
}

345
int git_tree__prefix_position(const git_tree *tree, const char *path)
346 347
{
	struct tree_key_search ksearch;
348
	size_t at_pos, path_len;
349

350 351 352
	if (!path)
		return 0;

353 354 355
	path_len = strlen(path);
	TREE_ENTRY_CHECK_NAMELEN(path_len);

356
	ksearch.filename = path;
357
	ksearch.filename_len = (uint16_t)path_len;
358 359

	/* Find tree entry with appropriate prefix */
360 361
	git_array_search(
		&at_pos, tree->entries, &homing_search_cmp, &ksearch);
362

363 364
	for (; at_pos < tree->entries.size; ++at_pos) {
		const git_tree_entry *entry = git_array_get(tree->entries, at_pos);
365 366 367 368 369
		if (homing_search_cmp(&ksearch, entry) < 0)
			break;
	}

	for (; at_pos > 0; --at_pos) {
370 371 372
		const git_tree_entry *entry =
			git_array_get(tree->entries, at_pos - 1);

373 374 375 376
		if (homing_search_cmp(&ksearch, entry) > 0)
			break;
	}

377
	return (int)at_pos;
378 379
}

380
size_t git_tree_entrycount(const git_tree *tree)
381
{
382
	assert(tree);
383
	return tree->entries.size;
384 385
}

386 387 388
unsigned int git_treebuilder_entrycount(git_treebuilder *bld)
{
	assert(bld);
389 390

	return git_strmap_num_entries(bld->map);
391 392
}

393
static int tree_error(const char *str, const char *path)
394
{
395 396 397 398
	if (path)
		giterr_set(GITERR_TREE, "%s - %s", str, path);
	else
		giterr_set(GITERR_TREE, "%s", str);
399 400
	return -1;
}
401

402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420
static int parse_mode(unsigned int *modep, const char *buffer, const char **buffer_out)
{
	unsigned char c;
	unsigned int mode = 0;

	if (*buffer == ' ')
		return -1;

	while ((c = *buffer++) != ' ') {
		if (c < '0' || c > '7')
			return -1;
		mode = (mode << 3) + (c - '0');
	}
	*modep = mode;
	*buffer_out = buffer;

	return 0;
}

421
int git_tree__parse(void *_tree, git_odb_object *odb_obj)
422
{
423
	git_tree *tree = _tree;
424 425 426 427 428 429 430 431
	const char *buffer;
	const char *buffer_end;

	if (git_odb_object_dup(&tree->odb_obj, odb_obj) < 0)
		return -1;

	buffer = git_odb_object_data(tree->odb_obj);
	buffer_end = buffer + git_odb_object_size(tree->odb_obj);
432

433 434
	git_array_init_to_size(tree->entries, DEFAULT_TREE_SIZE);
	GITERR_CHECK_ARRAY(tree->entries);
435

436 437
	while (buffer < buffer_end) {
		git_tree_entry *entry;
438 439
		size_t filename_len;
		const char *nul;
440
		unsigned int attr;
441

442
		if (parse_mode(&attr, buffer, &buffer) < 0 || !buffer)
443
			return tree_error("Failed to parse tree. Can't parse filemode", NULL);
444

445
		if ((nul = memchr(buffer, 0, buffer_end - buffer)) == NULL)
446
			return tree_error("Failed to parse tree. Object is corrupted", NULL);
447

448 449 450 451 452 453
		if ((filename_len = nul - buffer) == 0)
			return tree_error("Failed to parse tree. Can't parse filename", NULL);

		if ((buffer_end - (nul + 1)) < GIT_OID_RAWSZ)
			return tree_error("Failed to parse tree. Can't parse OID", NULL);

454
		/* Allocate the entry */
455
		{
456
			entry = git_array_alloc(tree->entries);
457 458 459
			GITERR_CHECK_ALLOC(entry);

			entry->attr = attr;
460 461 462
			entry->filename_len = filename_len;
			entry->filename = buffer;
			entry->oid = (git_oid *) ((char *) buffer + filename_len + 1);
463
		}
464

465
		buffer += filename_len + 1;
466 467 468
		buffer += GIT_OID_RAWSZ;
	}

469
	return 0;
470
}
471

472
static size_t find_next_dir(const char *dirname, git_index *index, size_t start)
473
{
474
	size_t dirlen, i, entries = git_index_entrycount(index);
475 476 477

	dirlen = strlen(dirname);
	for (i = start; i < entries; ++i) {
Ben Straub committed
478
		const git_index_entry *entry = git_index_get_byindex(index, i);
479 480 481 482 483 484 485 486 487 488
		if (strlen(entry->path) < dirlen ||
		    memcmp(entry->path, dirname, dirlen) ||
			(dirlen > 0 && entry->path[dirlen] != '/')) {
			break;
		}
	}

	return i;
}

489 490 491 492
static int append_entry(
	git_treebuilder *bld,
	const char *filename,
	const git_oid *id,
nulltoken committed
493
	git_filemode_t filemode)
494 495
{
	git_tree_entry *entry;
496
	int error = 0;
497

498
	if (!valid_entry_name(bld->repo, filename))
499
		return tree_error("Failed to insert entry. Invalid name for a tree entry", filename);
500

501
	entry = alloc_entry(filename, strlen(filename), id);
502
	GITERR_CHECK_ALLOC(entry);
503

nulltoken committed
504
	entry->attr = (uint16_t)filemode;
505

506
	git_strmap_insert(bld->map, entry->filename, entry, &error);
507
	if (error < 0) {
508
		git_tree_entry_free(entry);
509
		giterr_set(GITERR_TREE, "failed to append entry %s to the tree builder", filename);
510
		return -1;
511
	}
512

513
	return 0;
514 515
}

516 517 518 519 520
static int write_tree(
	git_oid *oid,
	git_repository *repo,
	git_index *index,
	const char *dirname,
521 522
	size_t start,
	git_buf *shared_buf)
523
{
524
	git_treebuilder *bld = NULL;
525
	size_t i, entries = git_index_entrycount(index);
526 527
	int error;
	size_t dirname_len = strlen(dirname);
528 529 530
	const git_tree_cache *cache;

	cache = git_tree_cache_get(index->tree, dirname);
531
	if (cache != NULL && cache->entry_count >= 0){
532
		git_oid_cpy(oid, &cache->oid);
533
		return (int)find_next_dir(dirname, index, start);
534
	}
535

536
	if ((error = git_treebuilder_new(&bld, repo, NULL)) < 0 || bld == NULL)
537
		return -1;
538

539 540 541 542 543 544
	/*
	 * 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
545
		const git_index_entry *entry = git_index_get_byindex(index, i);
546
		const char *filename, *next_slash;
547 548 549 550 551 552 553 554 555 556 557 558

	/*
	 * 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] != '/')) {
559
			break;
560
		}
561

562 563 564 565 566 567 568 569 570 571
		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);
572
			GITERR_CHECK_ALLOC(subdir);
573

574
			/* Write out the subtree */
575
			written = write_tree(&sub_oid, repo, index, subdir, i, shared_buf);
576
			if (written < 0) {
577
				git__free(subdir);
578
				goto on_error;
579 580
			} else {
				i = written - 1; /* -1 because of the loop increment */
581
			}
582

583 584 585 586 587 588 589 590 591 592 593 594
			/*
			 * 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;
			}
595

596
			error = append_entry(bld, last_comp, &sub_oid, S_IFDIR);
597
			git__free(subdir);
598
			if (error < 0)
599
				goto on_error;
600
		} else {
601
			error = append_entry(bld, filename, &entry->id, entry->mode);
602
			if (error < 0)
603
				goto on_error;
604
		}
605
	}
606

607
	if (git_treebuilder_write_with_buffer(oid, bld, shared_buf) < 0)
608
		goto on_error;
609

610
	git_treebuilder_free(bld);
611
	return (int)i;
612

613 614 615
on_error:
	git_treebuilder_free(bld);
	return -1;
616 617
}

618 619
int git_tree__write_index(
	git_oid *oid, git_index *index, git_repository *repo)
620
{
621
	int ret;
622
	git_tree *tree;
623
	git_buf shared_buf = GIT_BUF_INIT;
624
	bool old_ignore_case = false;
625

626
	assert(oid && index && repo);
627

628 629
	if (git_index_has_conflicts(index)) {
		giterr_set(GITERR_INDEX,
630
			"cannot create a tree from a not fully merged index.");
631 632 633
		return GIT_EUNMERGED;
	}

634
	if (index->tree != NULL && index->tree->entry_count >= 0) {
635
		git_oid_cpy(oid, &index->tree->oid);
636
		return 0;
637 638
	}

639
	/* The tree cache didn't help us; we'll have to write
640
	 * out a tree. If the index is ignore_case, we must
641 642 643 644 645
	 * make it case-sensitive for the duration of the tree-write
	 * operation. */

	if (index->ignore_case) {
		old_ignore_case = true;
646
		git_index__set_ignore_case(index, false);
647 648
	}

649 650
	ret = write_tree(oid, repo, index, "", 0, &shared_buf);
	git_buf_free(&shared_buf);
651 652

	if (old_ignore_case)
653
		git_index__set_ignore_case(index, true);
654

655 656 657 658 659 660 661 662 663 664 665 666 667 668 669
	index->tree = NULL;

	if (ret < 0)
		return ret;

	git_pool_clear(&index->tree_pool);

	if ((ret = git_tree_lookup(&tree, repo, oid)) < 0)
		return ret;

	/* Read the tree cache into the index */
	ret = git_tree_cache_read_tree(&index->tree, tree, &index->tree_pool);
	git_tree_free(tree);

	return ret;
670
}
671

672
int git_treebuilder_new(
673 674 675
	git_treebuilder **builder_p,
	git_repository *repo,
	const git_tree *source)
676 677
{
	git_treebuilder *bld;
678
	size_t i;
679

680
	assert(builder_p && repo);
681 682

	bld = git__calloc(1, sizeof(git_treebuilder));
683
	GITERR_CHECK_ALLOC(bld);
684

685 686
	bld->repo = repo;

687
	if (git_strmap_alloc(&bld->map) < 0) {
688
		git__free(bld);
689 690
		return -1;
	}
691 692

	if (source != NULL) {
693
		git_tree_entry *entry_src;
694

695
		git_array_foreach(source->entries, i, entry_src) {
696 697
			if (append_entry(
				bld, entry_src->filename,
698
				entry_src->oid,
699
				entry_src->attr) < 0)
700
				goto on_error;
701 702 703 704
		}
	}

	*builder_p = bld;
705 706 707 708 709
	return 0;

on_error:
	git_treebuilder_free(bld);
	return -1;
710 711
}

712 713 714 715 716 717 718 719 720 721 722 723
static git_otype otype_from_mode(git_filemode_t filemode)
{
	switch (filemode) {
	case GIT_FILEMODE_TREE:
		return GIT_OBJ_TREE;
	case GIT_FILEMODE_COMMIT:
		return GIT_OBJ_COMMIT;
	default:
		return GIT_OBJ_BLOB;
	}
}

724 725 726 727 728
int git_treebuilder_insert(
	const git_tree_entry **entry_out,
	git_treebuilder *bld,
	const char *filename,
	const git_oid *id,
nulltoken committed
729
	git_filemode_t filemode)
730 731
{
	git_tree_entry *entry;
732
	int error;
733
	git_strmap_iter pos;
734 735 736

	assert(bld && id && filename);

nulltoken committed
737
	if (!valid_filemode(filemode))
738
		return tree_error("Failed to insert entry. Invalid filemode for file", filename);
739

740
	if (!valid_entry_name(bld->repo, filename))
741
		return tree_error("Failed to insert entry. Invalid name for a tree entry", filename);
742

743 744
	if (filemode != GIT_FILEMODE_COMMIT &&
	    !git_object__is_valid(bld->repo, id, otype_from_mode(filemode)))
745 746
		return tree_error("Failed to insert entry; invalid object specified", filename);

747 748 749
	pos = git_strmap_lookup_index(bld->map, filename);
	if (git_strmap_valid_index(bld->map, pos)) {
		entry = git_strmap_value_at(bld->map, pos);
750
		git_oid_cpy((git_oid *) entry->oid, id);
751
	} else {
752
		entry = alloc_entry(filename, strlen(filename), id);
753
		GITERR_CHECK_ALLOC(entry);
754

755
		git_strmap_insert(bld->map, entry->filename, entry, &error);
756

757 758 759 760 761
		if (error < 0) {
			git_tree_entry_free(entry);
			giterr_set(GITERR_TREE, "failed to insert %s", filename);
			return -1;
		}
762 763
	}

764 765 766
	entry->attr = filemode;

	if (entry_out)
767 768
		*entry_out = entry;

769
	return 0;
770 771
}

772
static git_tree_entry *treebuilder_get(git_treebuilder *bld, const char *filename)
773
{
774 775
	git_tree_entry *entry = NULL;
	git_strmap_iter pos;
776 777 778

	assert(bld && filename);

779 780 781
	pos = git_strmap_lookup_index(bld->map, filename);
	if (git_strmap_valid_index(bld->map, pos))
		entry = git_strmap_value_at(bld->map, pos);
782 783 784 785

	return entry;
}

786 787 788 789 790
const git_tree_entry *git_treebuilder_get(git_treebuilder *bld, const char *filename)
{
	return treebuilder_get(bld, filename);
}

791 792
int git_treebuilder_remove(git_treebuilder *bld, const char *filename)
{
793
	git_tree_entry *entry = treebuilder_get(bld, filename);
794

795
	if (entry == NULL)
796
		return tree_error("Failed to remove entry. File isn't in the tree", filename);
797

798
	git_strmap_delete(bld->map, filename);
799
	git_tree_entry_free(entry);
800

801
	return 0;
802 803
}

804
int git_treebuilder_write(git_oid *oid, git_treebuilder *bld)
805
{
806 807 808 809 810 811 812 813 814 815 816
	int error;
	git_buf buffer = GIT_BUF_INIT;

	error = git_treebuilder_write_with_buffer(oid, bld, &buffer);

	git_buf_free(&buffer);
	return error;
}

int git_treebuilder_write_with_buffer(git_oid *oid, git_treebuilder *bld, git_buf *tree)
{
817
	int error = 0;
818
	size_t i, entrycount;
819
	git_odb *odb;
820 821
	git_tree_entry *entry;
	git_vector entries;
822 823

	assert(bld);
824 825 826
	assert(tree);

	git_buf_clear(tree);
827

828 829
	entrycount = git_strmap_num_entries(bld->map);
	if (git_vector_init(&entries, entrycount, entry_sort_cmp) < 0)
830
		return -1;
831

832 833 834 835
	if (tree->asize == 0 &&
		(error = git_buf_grow(tree, entrycount * 72)) < 0)
		return error;

836 837 838 839
	git_strmap_foreach_value(bld->map, entry, {
		if (git_vector_insert(&entries, entry) < 0)
			return -1;
	});
840

841 842 843 844
	git_vector_sort(&entries);

	for (i = 0; i < entries.length && !error; ++i) {
		git_tree_entry *entry = git_vector_get(&entries, i);
845

846 847 848
		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);
849

850
		if (git_buf_oom(tree))
851 852
			error = -1;
	}
853

854
	if (!error &&
855
		!(error = git_repository_odb__weakptr(&odb, bld->repo)))
856
		error = git_odb_write(oid, odb, tree->ptr, tree->size, GIT_OBJ_TREE);
857

858 859
	git_vector_free(&entries);

860
	return error;
861 862
}

863
void git_treebuilder_filter(
864 865 866
	git_treebuilder *bld,
	git_treebuilder_filter_cb filter,
	void *payload)
867
{
868
	const char *filename;
869
	git_tree_entry *entry;
870 871 872

	assert(bld && filter);

873 874 875
	git_strmap_foreach(bld->map, filename, entry, {
			if (filter(entry, payload)) {
				git_strmap_delete(bld->map, filename);
876
				git_tree_entry_free(entry);
877 878
			}
	});
879 880 881 882
}

void git_treebuilder_clear(git_treebuilder *bld)
{
883 884
	git_tree_entry *e;

885 886
	assert(bld);

887
	git_strmap_foreach_value(bld->map, e, git_tree_entry_free(e));
888
	git_strmap_clear(bld->map);
889 890 891 892
}

void git_treebuilder_free(git_treebuilder *bld)
{
893 894 895
	if (bld == NULL)
		return;

896
	git_treebuilder_clear(bld);
897
	git_strmap_free(bld->map);
898
	git__free(bld);
899 900
}

901 902 903 904 905 906 907 908 909 910 911
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,
912
	const git_tree *root,
913
	const char *path)
914
{
915
	int error = 0;
916
	git_tree *subtree;
917 918
	const git_tree_entry *entry;
	size_t filename_len;
919

920 921 922
	/* Find how long is the current path component (i.e.
	 * the filename between two slashes */
	filename_len = subpath_len(path);
923

924
	if (filename_len == 0) {
925
		giterr_set(GITERR_TREE, "invalid tree path given");
926
		return GIT_ENOTFOUND;
927
	}
928

929
	entry = entry_fromname(root, path, filename_len);
930

931 932
	if (entry == NULL) {
		giterr_set(GITERR_TREE,
933
			   "the path '%.*s' does not exist in the given tree", (int) filename_len, path);
934
		return GIT_ENOTFOUND;
935
	}
936

937
	switch (path[filename_len]) {
938
	case '/':
939 940 941 942
		/* 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,
943
				   "the path '%.*s' exists but is not a tree", (int) filename_len, path);
944
			return GIT_ENOTFOUND;
945 946 947 948 949 950 951 952 953 954 955
		}

		/* 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 */
956
		return git_tree_entry_dup(entry_out, entry);
957
	}
958

959
	if (git_tree_lookup(&subtree, root->object.repo, entry->oid) < 0)
960
		return -1;
961

962 963
	error = git_tree_entry_bypath(
		entry_out,
964
		subtree,
965
		path + filename_len + 1
966
	);
967

968
	git_tree_free(subtree);
969 970 971
	return error;
}

972
static int tree_walk(
Ben Straub committed
973
	const git_tree *tree,
974
	git_treewalk_cb callback,
975
	git_buf *path,
976 977
	void *payload,
	bool preorder)
978
{
979
	int error = 0;
980
	size_t i;
981
	const git_tree_entry *entry;
982

983
	git_array_foreach(tree->entries, i, entry) {
984
		if (preorder) {
985 986 987 988 989 990
			error = callback(path->ptr, entry, payload);
			if (error < 0) { /* negative value stops iteration */
				giterr_set_after_callback_function(error, "git_tree_walk");
				break;
			}
			if (error > 0) { /* positive value skips this entry */
991
				error = 0;
992
				continue;
993
			}
994
		}
995

Vicent Martí committed
996
		if (git_tree_entry__is_tree(entry)) {
997
			git_tree *subtree;
nulltoken committed
998
			size_t path_len = git_buf_len(path);
999

1000
			error = git_tree_lookup(&subtree, tree->object.repo, entry->oid);
1001
			if (error < 0)
1002
				break;
1003

1004 1005 1006
			/* append the next entry to the path */
			git_buf_puts(path, entry->filename);
			git_buf_putc(path, '/');
1007

1008
			if (git_buf_oom(path))
1009 1010 1011
				error = -1;
			else
				error = tree_walk(subtree, callback, path, payload, preorder);
1012

1013
			git_tree_free(subtree);
1014 1015
			if (error != 0)
				break;
1016

1017
			git_buf_truncate(path, path_len);
1018
		}
1019

1020
		if (!preorder) {
1021 1022 1023 1024 1025
			error = callback(path->ptr, entry, payload);
			if (error < 0) { /* negative value stops iteration */
				giterr_set_after_callback_function(error, "git_tree_walk");
				break;
			}
1026 1027
			error = 0;
		}
1028 1029
	}

1030
	return error;
1031 1032
}

1033
int git_tree_walk(
Ben Straub committed
1034
	const git_tree *tree,
1035 1036 1037
	git_treewalk_mode mode,
	git_treewalk_cb callback,
	void *payload)
1038
{
1039
	int error = 0;
1040
	git_buf root_path = GIT_BUF_INIT;
1041

1042
	if (mode != GIT_TREEWALK_POST && mode != GIT_TREEWALK_PRE) {
1043
		giterr_set(GITERR_INVALID, "invalid walking mode for tree walk");
1044
		return -1;
1045
	}
1046

1047 1048 1049
	error = tree_walk(
		tree, callback, &root_path, payload, (mode == GIT_TREEWALK_PRE));

1050 1051 1052
	git_buf_free(&root_path);

	return error;
1053
}
1054

1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113
static int compare_entries(const void *_a, const void *_b)
{
	const git_tree_update *a = (git_tree_update *) _a;
	const git_tree_update *b = (git_tree_update *) _b;

	return strcmp(a->path, b->path);
}

static int on_dup_entry(void **old, void *new)
{
	GIT_UNUSED(old); GIT_UNUSED(new);

	giterr_set(GITERR_TREE, "duplicate entries given for update");
	return -1;
}

/*
 * We keep the previous tree and the new one at each level of the
 * stack. When we leave a level we're done with that tree and we can
 * write it out to the odb.
 */
typedef struct {
	git_treebuilder *bld;
	git_tree *tree;
	char *name;
} tree_stack_entry;

/** Count how many slashes (i.e. path components) there are in this string */
GIT_INLINE(size_t) count_slashes(const char *path)
{
	size_t count = 0;
	const char *slash;

	while ((slash = strchr(path, '/')) != NULL) {
		count++;
		path = slash + 1;
	}

	return count;
}

static bool next_component(git_buf *out, const char *in)
{
	const char *slash = strchr(in, '/');

	git_buf_clear(out);

	if (slash)
		git_buf_put(out, in, slash - in);

	return !!slash;
}

static int create_popped_tree(tree_stack_entry *current, tree_stack_entry *popped, git_buf *component)
{
	int error;
	git_oid new_tree;

	git_tree_free(popped->tree);
1114 1115 1116 1117 1118 1119 1120 1121 1122

	/* If the tree would be empty, remove it from the one higher up */
	if (git_treebuilder_entrycount(popped->bld) == 0) {
		git_treebuilder_free(popped->bld);
		error = git_treebuilder_remove(current->bld, popped->name);
		git__free(popped->name);
		return error;
	}

1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179
	error = git_treebuilder_write(&new_tree, popped->bld);
	git_treebuilder_free(popped->bld);

	if (error < 0) {
		git__free(popped->name);
		return error;
	}

	/* We've written out the tree, now we have to put the new value into its parent */
	git_buf_clear(component);
	git_buf_puts(component, popped->name);
	git__free(popped->name);

	GITERR_CHECK_ALLOC(component->ptr);

	/* Error out if this would create a D/F conflict in this update */
	if (current->tree) {
		const git_tree_entry *to_replace;
		to_replace = git_tree_entry_byname(current->tree, component->ptr);
		if (to_replace && git_tree_entry_type(to_replace) != GIT_OBJ_TREE) {
			giterr_set(GITERR_TREE, "D/F conflict when updating tree");
			return -1;
		}
	}

	return git_treebuilder_insert(NULL, current->bld, component->ptr, &new_tree, GIT_FILEMODE_TREE);
}

int git_tree_create_updated(git_oid *out, git_repository *repo, git_tree *baseline, size_t nupdates, const git_tree_update *updates)
{
	git_array_t(tree_stack_entry) stack = GIT_ARRAY_INIT;
	tree_stack_entry *root_elem;
	git_vector entries;
	int error;
	size_t i;
	git_buf component = GIT_BUF_INIT;

	if ((error = git_vector_init(&entries, nupdates, compare_entries)) < 0)
		return error;

	/* Sort the entries for treversal */
	for (i = 0 ; i < nupdates; i++)	{
		if ((error = git_vector_insert_sorted(&entries, (void *) &updates[i], on_dup_entry)) < 0)
			goto cleanup;
	}

	root_elem = git_array_alloc(stack);
	GITERR_CHECK_ALLOC(root_elem);
	memset(root_elem, 0, sizeof(*root_elem));

	if (baseline && (error = git_tree_dup(&root_elem->tree, baseline)) < 0)
		goto cleanup;

	if ((error = git_treebuilder_new(&root_elem->bld, repo, root_elem->tree)) < 0)
		goto cleanup;

	for (i = 0; i < nupdates; i++) {
1180 1181
		const git_tree_update *last_update = i == 0 ? NULL : git_vector_get(&entries, i-1);
		const git_tree_update *update = git_vector_get(&entries, i);
1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215
		size_t common_prefix = 0, steps_up, j;
		const char *path;

		/* Figure out how much we need to change from the previous tree */
		if (last_update)
			common_prefix = git_path_common_dirlen(last_update->path, update->path);

		/*
		 * The entries are sorted, so when we find we're no
		 * longer in the same directory, we need to abandon
		 * the old tree (steps up) and dive down to the next
		 * one.
		 */
		steps_up = last_update == NULL ? 0 : count_slashes(&last_update->path[common_prefix]);

		for (j = 0; j < steps_up; j++) {
			tree_stack_entry *current, *popped = git_array_pop(stack);
			assert(popped);

			current = git_array_last(stack);
			assert(current);

			if ((error = create_popped_tree(current, popped, &component)) < 0)
				goto cleanup;
		}

		/* Now that we've created the trees we popped from the stack, let's go back down */
		path = &update->path[common_prefix];
		while (next_component(&component, path)) {
			tree_stack_entry *last, *new_entry;
			const git_tree_entry *entry;

			last = git_array_last(stack);
			entry = last->tree ? git_tree_entry_byname(last->tree, component.ptr) : NULL;
1216 1217 1218
			if (!entry)
				entry = treebuilder_get(last->bld, component.ptr);

1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248
			if (entry && git_tree_entry_type(entry) != GIT_OBJ_TREE) {
				giterr_set(GITERR_TREE, "D/F conflict when updating tree");
				error = -1;
				goto cleanup;
			}

			new_entry = git_array_alloc(stack);
			GITERR_CHECK_ALLOC(new_entry);
			memset(new_entry, 0, sizeof(*new_entry));

			new_entry->tree = NULL;
			if (entry && (error = git_tree_lookup(&new_entry->tree, repo, git_tree_entry_id(entry))) < 0)
				goto cleanup;

			if ((error = git_treebuilder_new(&new_entry->bld, repo, new_entry->tree)) < 0)
				goto cleanup;

			new_entry->name = git__strdup(component.ptr);
			GITERR_CHECK_ALLOC(new_entry->name);

			/* Get to the start of the next component */
			path += component.size + 1;
		}

		/* After all that, we're finally at the place where we want to perform the update */
		switch (update->action) {
			case GIT_TREE_UPDATE_UPSERT:
			{
				/* Make sure we're replacing something of the same type */
				tree_stack_entry *last = git_array_last(stack);
1249
				char *basename = git_path_basename(update->path);
1250 1251
				const git_tree_entry *e = git_treebuilder_get(last->bld, basename);
				if (e && git_tree_entry_type(e) != git_object__type_from_filemode(update->filemode)) {
1252
					git__free(basename);
1253
					giterr_set(GITERR_TREE, "cannot replace '%s' with '%s' at '%s'",
1254 1255 1256
						   git_object_type2string(git_tree_entry_type(e)),
						   git_object_type2string(git_object__type_from_filemode(update->filemode)),
						   update->path);
1257 1258
					error = -1;
					goto cleanup;
1259 1260 1261
				}

				error = git_treebuilder_insert(NULL, last->bld, basename, &update->id, update->filemode);
1262
				git__free(basename);
1263 1264 1265
				break;
			}
			case GIT_TREE_UPDATE_REMOVE:
1266 1267 1268 1269
			{
				char *basename = git_path_basename(update->path);
				error = git_treebuilder_remove(git_array_last(stack)->bld, basename);
				git__free(basename);
1270
				break;
1271
			}
1272
			default:
1273
				giterr_set(GITERR_TREE, "unknown action for update");
1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314
				error = -1;
				goto cleanup;
		}

		if (error < 0)
			goto cleanup;
	}

	/* We're done, go up the stack again and write out the tree */
	{
		tree_stack_entry *current = NULL, *popped = NULL;
		while ((popped = git_array_pop(stack)) != NULL) {
			current = git_array_last(stack);
			/* We've reached the top, current is the root tree */
			if (!current)
				break;

			if ((error = create_popped_tree(current, popped, &component)) < 0)
				goto cleanup;
		}

		/* Write out the root tree */
		git__free(popped->name);
		git_tree_free(popped->tree);

		error = git_treebuilder_write(out, popped->bld);
		git_treebuilder_free(popped->bld);
		if (error < 0)
			goto cleanup;
	}

cleanup:
	{
		tree_stack_entry *e;
		while ((e = git_array_pop(stack)) != NULL) {
			git_treebuilder_free(e->bld);
			git_tree_free(e->tree);
			git__free(e->name);
		}
	}

1315
	git_buf_free(&component);
1316 1317 1318 1319
	git_array_clear(stack);
	git_vector_free(&entries);
	return error;
}