tree.c 31.9 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
 */

#include "tree.h"
9 10

#include "commit.h"
11 12
#include "git2/repository.h"
#include "git2/object.h"
13
#include "futils.h"
14 15
#include "tree-cache.h"
#include "index.h"
16
#include "path.h"
17

18
#define DEFAULT_TREE_SIZE 16
19
#define MAX_FILEMODE_BYTES 6
20

21
#define TREE_ENTRY_CHECK_NAMELEN(n) \
22
	if (n > UINT16_MAX) { git_error_set(GIT_ERROR_INVALID, "tree entry path too long"); }
23

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

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

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

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

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

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

55
static int valid_entry_name(git_repository *repo, const char *filename)
56
{
57
	return *filename != '\0' &&
58
		git_path_is_valid(repo, filename, 0,
59
		GIT_FS_PATH_REJECT_TRAVERSAL | GIT_PATH_REJECT_DOT_GIT | GIT_FS_PATH_REJECT_SLASH);
60 61
}

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

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

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

78
/**
79 80
 * Allocate a new self-contained entry, with enough space after it to
 * store the filename and the id.
81
 */
82
static git_tree_entry *alloc_entry(const char *filename, size_t filename_len, const git_oid *id)
83 84
{
	git_tree_entry *entry = NULL;
85
	size_t tree_len;
86

87
	TREE_ENTRY_CHECK_NAMELEN(filename_len);
88

89 90 91
	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))
92 93
		return NULL;

94
	entry = git__calloc(1, tree_len);
95
	if (!entry)
96 97
		return NULL;

98
	{
99 100 101 102 103 104 105 106 107 108 109 110
		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;
	}

111
	entry->filename_len = (uint16_t)filename_len;
112 113 114 115

	return entry;
}

116 117
struct tree_key_search {
	const char *filename;
118
	uint16_t filename_len;
119 120
};

121
static int homing_search_cmp(const void *key, const void *array_member)
122
{
123 124
	const struct tree_key_search *ksearch = key;
	const git_tree_entry *entry = array_member;
125

126 127
	const uint16_t len1 = ksearch->filename_len;
	const uint16_t len2 = entry->filename_len;
128

129 130 131 132 133
	return memcmp(
		ksearch->filename,
		entry->filename,
		len1 < len2 ? len1 : len2
	);
134 135
}

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

166 167
	TREE_ENTRY_CHECK_NAMELEN(filename_len);

168
	ksearch.filename = filename;
169
	ksearch.filename_len = (uint16_t)filename_len;
170

171 172
	/* Initial homing search; find an entry on the tree with
	 * the same prefix as the filename we're looking for */
173 174 175

	if (git_array_search(&homing,
		tree->entries, &homing_search_cmp, &ksearch) < 0)
176
		return GIT_ENOTFOUND; /* just a signal error; not passed back to user */
177 178 179

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

183
		if (homing_search_cmp(&ksearch, entry) < 0)
184 185
			break;

186
		if (entry->filename_len == filename_len &&
187 188 189 190 191 192
			memcmp(filename, entry->filename, filename_len) == 0) {
			if (at_pos)
				*at_pos = i;

			return 0;
		}
193
	}
194

195 196
	/* If we haven't found our filename yet, look backwards
	 * too as long as we have entries with the same prefix */
197 198
	if (homing > 0) {
		i = homing - 1;
199

200
		do {
201
			entry = git_array_get(tree->entries, i);
202

203 204 205 206 207 208 209 210 211 212 213
			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);
214 215 216
	}

	/* The filename doesn't exist at all */
217
	return GIT_ENOTFOUND;
218 219
}

220 221
void git_tree_entry_free(git_tree_entry *entry)
{
222
	if (entry == NULL)
223 224
		return;

225 226 227
	git__free(entry);
}

228
int git_tree_entry_dup(git_tree_entry **dest, const git_tree_entry *source)
229
{
230 231
	git_tree_entry *cpy;

Edward Thomson committed
232
	GIT_ASSERT_ARG(source);
233

234 235
	cpy = alloc_entry(source->filename, source->filename_len, source->oid);
	if (cpy == NULL)
236
		return -1;
237

238 239 240
	cpy->attr = source->attr;

	*dest = cpy;
241
	return 0;
242 243
}

244
void git_tree__free(void *_tree)
245
{
246
	git_tree *tree = _tree;
247

248
	git_odb_object_free(tree->odb_obj);
249
	git_array_clear(tree->entries);
250
	git__free(tree);
251 252
}

253
git_filemode_t git_tree_entry_filemode(const git_tree_entry *entry)
254
{
255 256 257 258 259 260
	return normalize_filemode(entry->attr);
}

git_filemode_t git_tree_entry_filemode_raw(const git_tree_entry *entry)
{
	return entry->attr;
261 262
}

263
const char *git_tree_entry_name(const git_tree_entry *entry)
264
{
Edward Thomson committed
265
	GIT_ASSERT_ARG_WITH_RETVAL(entry, NULL);
266 267
	return entry->filename;
}
268

269
const git_oid *git_tree_entry_id(const git_tree_entry *entry)
270
{
Edward Thomson committed
271
	GIT_ASSERT_ARG_WITH_RETVAL(entry, NULL);
272
	return entry->oid;
273 274
}

275
git_object_t git_tree_entry_type(const git_tree_entry *entry)
276
{
Edward Thomson committed
277
	GIT_ASSERT_ARG_WITH_RETVAL(entry, GIT_OBJECT_INVALID);
278 279

	if (S_ISGITLINK(entry->attr))
280
		return GIT_OBJECT_COMMIT;
281
	else if (S_ISDIR(entry->attr))
282
		return GIT_OBJECT_TREE;
283
	else
284
		return GIT_OBJECT_BLOB;
285 286
}

Vicent Martí committed
287 288 289 290
int git_tree_entry_to_object(
	git_object **object_out,
	git_repository *repo,
	const git_tree_entry *entry)
291
{
Edward Thomson committed
292 293 294
	GIT_ASSERT_ARG(entry);
	GIT_ASSERT_ARG(object_out);

295
	return git_object_lookup(object_out, repo, entry->oid, GIT_OBJECT_ANY);
296 297
}

298
static const git_tree_entry *entry_fromname(
299
	const git_tree *tree, const char *name, size_t name_len)
300
{
301 302
	size_t idx;

303
	if (tree_key_search(&idx, tree, name, name_len) < 0)
304 305
		return NULL;

306
	return git_array_get(tree->entries, idx);
307 308
}

309
const git_tree_entry *git_tree_entry_byname(
310
	const git_tree *tree, const char *filename)
311
{
Edward Thomson committed
312 313
	GIT_ASSERT_ARG_WITH_RETVAL(tree, NULL);
	GIT_ASSERT_ARG_WITH_RETVAL(filename, NULL);
314

315 316 317
	return entry_fromname(tree, filename, strlen(filename));
}

318
const git_tree_entry *git_tree_entry_byindex(
319
	const git_tree *tree, size_t idx)
320
{
Edward Thomson committed
321
	GIT_ASSERT_ARG_WITH_RETVAL(tree, NULL);
322
	return git_array_get(tree->entries, idx);
323 324
}

325 326
const git_tree_entry *git_tree_entry_byid(
	const git_tree *tree, const git_oid *id)
327
{
328 329
	size_t i;
	const git_tree_entry *e;
330

Edward Thomson committed
331
	GIT_ASSERT_ARG_WITH_RETVAL(tree, NULL);
332

333
	git_array_foreach(tree->entries, i, e) {
334
		if (memcmp(&e->oid->id, &id->id, sizeof(id->id)) == 0)
335 336 337 338 339 340
			return e;
	}

	return NULL;
}

341
size_t git_tree_entrycount(const git_tree *tree)
342
{
Edward Thomson committed
343
	GIT_ASSERT_ARG_WITH_RETVAL(tree, 0);
344
	return tree->entries.size;
345 346
}

347
size_t git_treebuilder_entrycount(git_treebuilder *bld)
348
{
Edward Thomson committed
349
	GIT_ASSERT_ARG_WITH_RETVAL(bld, 0);
350

351
	return git_strmap_size(bld->map);
352 353
}

354
GIT_INLINE(void) set_error(const char *str, const char *path)
355
{
356
	if (path)
357
		git_error_set(GIT_ERROR_TREE, "%s - %s", str, path);
358
	else
359
		git_error_set(GIT_ERROR_TREE, "%s", str);
360 361 362 363 364
}

static int tree_error(const char *str, const char *path)
{
	set_error(str, path);
365 366
	return -1;
}
367

368 369 370 371 372 373
static int tree_parse_error(const char *str, const char *path)
{
	set_error(str, path);
	return GIT_EINVALID;
}

374
static int parse_mode(uint16_t *mode_out, const char *buffer, size_t buffer_len, const char **buffer_out)
375
{
376 377
	int32_t mode;
	int error;
378

379
	if (!buffer_len || git__isspace(*buffer))
380 381
		return -1;

382 383 384 385 386 387 388
	if ((error = git__strntol32(&mode, buffer, buffer_len, buffer_out, 8)) < 0)
		return error;

	if (mode < 0 || mode > UINT16_MAX)
		return -1;

	*mode_out = mode;
389 390 391 392

	return 0;
}

393
int git_tree__parse_raw(void *_tree, const char *data, size_t size)
394
{
395
	git_tree *tree = _tree;
396 397 398
	const char *buffer;
	const char *buffer_end;

399 400
	buffer = data;
	buffer_end = buffer + size;
401

402
	tree->odb_obj = NULL;
403
	git_array_init_to_size(tree->entries, DEFAULT_TREE_SIZE);
404
	GIT_ERROR_CHECK_ARRAY(tree->entries);
405

406 407
	while (buffer < buffer_end) {
		git_tree_entry *entry;
408 409
		size_t filename_len;
		const char *nul;
410
		uint16_t attr;
411

412
		if (parse_mode(&attr, buffer, buffer_end - buffer, &buffer) < 0 || !buffer)
413
			return tree_parse_error("failed to parse tree: can't parse filemode", NULL);
414

415
		if (buffer >= buffer_end || (*buffer++) != ' ')
416
			return tree_parse_error("failed to parse tree: missing space after filemode", NULL);
417

418
		if ((nul = memchr(buffer, 0, buffer_end - buffer)) == NULL)
419
			return tree_parse_error("failed to parse tree: object is corrupted", NULL);
420

421
		if ((filename_len = nul - buffer) == 0 || filename_len > UINT16_MAX)
422
			return tree_parse_error("failed to parse tree: can't parse filename", NULL);
423 424

		if ((buffer_end - (nul + 1)) < GIT_OID_RAWSZ)
425
			return tree_parse_error("failed to parse tree: can't parse OID", NULL);
426

427
		/* Allocate the entry */
428
		{
429
			entry = git_array_alloc(tree->entries);
430
			GIT_ERROR_CHECK_ALLOC(entry);
431 432

			entry->attr = attr;
433
			entry->filename_len = (uint16_t)filename_len;
434 435
			entry->filename = buffer;
			entry->oid = (git_oid *) ((char *) buffer + filename_len + 1);
436
		}
437

438
		buffer += filename_len + 1;
439 440 441
		buffer += GIT_OID_RAWSZ;
	}

442
	return 0;
443
}
444

445 446 447
int git_tree__parse(void *_tree, git_odb_object *odb_obj)
{
	git_tree *tree = _tree;
448 449 450
	const char *data = git_odb_object_data(odb_obj);
	size_t size = git_odb_object_size(odb_obj);
	int error;
451

452 453 454
	if ((error = git_tree__parse_raw(tree, data, size)) < 0 ||
	    (error = git_odb_object_dup(&tree->odb_obj, odb_obj)) < 0)
		return error;
455

456
	return error;
457 458
}

459
static size_t find_next_dir(const char *dirname, git_index *index, size_t start)
460
{
461
	size_t dirlen, i, entries = git_index_entrycount(index);
462 463 464

	dirlen = strlen(dirname);
	for (i = start; i < entries; ++i) {
Ben Straub committed
465
		const git_index_entry *entry = git_index_get_byindex(index, i);
466 467 468 469 470 471 472 473 474 475
		if (strlen(entry->path) < dirlen ||
		    memcmp(entry->path, dirname, dirlen) ||
			(dirlen > 0 && entry->path[dirlen] != '/')) {
			break;
		}
	}

	return i;
}

476
static git_object_t otype_from_mode(git_filemode_t filemode)
477 478 479
{
	switch (filemode) {
	case GIT_FILEMODE_TREE:
480
		return GIT_OBJECT_TREE;
481
	case GIT_FILEMODE_COMMIT:
482
		return GIT_OBJECT_COMMIT;
483
	default:
484
		return GIT_OBJECT_BLOB;
485 486 487 488 489 490 491 492 493 494 495
	}
}

static int check_entry(git_repository *repo, const char *filename, const git_oid *id, git_filemode_t filemode)
{
	if (!valid_filemode(filemode))
		return tree_error("failed to insert entry: invalid filemode for file", filename);

	if (!valid_entry_name(repo, filename))
		return tree_error("failed to insert entry: invalid name for a tree entry", filename);

496
	if (git_oid_is_zero(id))
497 498 499 500 501 502 503 504 505
		return tree_error("failed to insert entry: invalid null OID", filename);

	if (filemode != GIT_FILEMODE_COMMIT &&
	    !git_object__is_valid(repo, id, otype_from_mode(filemode)))
		return tree_error("failed to insert entry: invalid object specified", filename);

	return 0;
}

506 507 508
static int git_treebuilder__write_with_buffer(
	git_oid *oid,
	git_treebuilder *bld,
509
	git_str *buf)
510 511 512 513 514 515 516
{
	int error = 0;
	size_t i, entrycount;
	git_odb *odb;
	git_tree_entry *entry;
	git_vector entries = GIT_VECTOR_INIT;

517
	git_str_clear(buf);
518 519 520 521 522 523

	entrycount = git_strmap_size(bld->map);
	if ((error = git_vector_init(&entries, entrycount, entry_sort_cmp)) < 0)
		goto out;

	if (buf->asize == 0 &&
524
	    (error = git_str_grow(buf, entrycount * 72)) < 0)
525 526 527 528 529 530 531 532 533 534 535 536
		goto out;

	git_strmap_foreach_value(bld->map, entry, {
		if ((error = git_vector_insert(&entries, entry)) < 0)
			goto out;
	});

	git_vector_sort(&entries);

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

537 538 539
		git_str_printf(buf, "%o ", entry->attr);
		git_str_put(buf, entry->filename, entry->filename_len + 1);
		git_str_put(buf, (char *)entry->oid->id, GIT_OID_RAWSZ);
540

541
		if (git_str_oom(buf)) {
542 543 544 545 546 547 548 549 550 551 552 553 554 555
			error = -1;
			goto out;
		}
	}

	if ((error = git_repository_odb__weakptr(&odb, bld->repo)) == 0)
		error = git_odb_write(oid, odb, buf->ptr, buf->size, GIT_OBJECT_TREE);

out:
	git_vector_free(&entries);

	return error;
}

556 557 558 559
static int append_entry(
	git_treebuilder *bld,
	const char *filename,
	const git_oid *id,
560
	git_filemode_t filemode,
561
	bool validate)
562 563
{
	git_tree_entry *entry;
564
	int error = 0;
565

566 567
	if (validate && ((error = check_entry(bld->repo, filename, id, filemode)) < 0))
		return error;
568

569
	entry = alloc_entry(filename, strlen(filename), id);
570
	GIT_ERROR_CHECK_ALLOC(entry);
571

nulltoken committed
572
	entry->attr = (uint16_t)filemode;
573

574
	if ((error = git_strmap_set(bld->map, entry->filename, entry)) < 0) {
575
		git_tree_entry_free(entry);
576
		git_error_set(GIT_ERROR_TREE, "failed to append entry %s to the tree builder", filename);
577
		return -1;
578
	}
579

580
	return 0;
581 582
}

583 584 585 586 587
static int write_tree(
	git_oid *oid,
	git_repository *repo,
	git_index *index,
	const char *dirname,
588
	size_t start,
589
	git_str *shared_buf)
590
{
591
	git_treebuilder *bld = NULL;
592
	size_t i, entries = git_index_entrycount(index);
593 594
	int error;
	size_t dirname_len = strlen(dirname);
595 596 597
	const git_tree_cache *cache;

	cache = git_tree_cache_get(index->tree, dirname);
598
	if (cache != NULL && cache->entry_count >= 0){
599
		git_oid_cpy(oid, &cache->oid);
600
		return (int)find_next_dir(dirname, index, start);
601
	}
602

603
	if ((error = git_treebuilder_new(&bld, repo, NULL)) < 0 || bld == NULL)
604
		return -1;
605

606 607
	/*
	 * This loop is unfortunate, but necessary. The index doesn't have
Dimitris Apostolou committed
608
	 * any directories, so we need to handle that manually, and we
609 610 611
	 * need to keep track of the current position.
	 */
	for (i = start; i < entries; ++i) {
Ben Straub committed
612
		const git_index_entry *entry = git_index_get_byindex(index, i);
613
		const char *filename, *next_slash;
614 615 616 617 618 619 620 621 622 623 624 625

	/*
	 * 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] != '/')) {
626
			break;
627
		}
628

629 630 631 632 633 634 635 636 637 638
		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);
639
			GIT_ERROR_CHECK_ALLOC(subdir);
640

641
			/* Write out the subtree */
642
			written = write_tree(&sub_oid, repo, index, subdir, i, shared_buf);
643
			if (written < 0) {
644
				git__free(subdir);
645
				goto on_error;
646 647
			} else {
				i = written - 1; /* -1 because of the loop increment */
648
			}
649

650 651 652 653 654 655 656 657 658 659 660 661
			/*
			 * 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;
			}
662

663
			error = append_entry(bld, last_comp, &sub_oid, S_IFDIR, true);
664
			git__free(subdir);
665
			if (error < 0)
666
				goto on_error;
667
		} else {
668
			error = append_entry(bld, filename, &entry->id, entry->mode, true);
669
			if (error < 0)
670
				goto on_error;
671
		}
672
	}
673

674
	if (git_treebuilder__write_with_buffer(oid, bld, shared_buf) < 0)
675
		goto on_error;
676

677
	git_treebuilder_free(bld);
678
	return (int)i;
679

680 681 682
on_error:
	git_treebuilder_free(bld);
	return -1;
683 684
}

685 686
int git_tree__write_index(
	git_oid *oid, git_index *index, git_repository *repo)
687
{
688
	int ret;
689
	git_tree *tree;
690
	git_str shared_buf = GIT_STR_INIT;
691
	bool old_ignore_case = false;
692

Edward Thomson committed
693 694 695
	GIT_ASSERT_ARG(oid);
	GIT_ASSERT_ARG(index);
	GIT_ASSERT_ARG(repo);
696

697
	if (git_index_has_conflicts(index)) {
698
		git_error_set(GIT_ERROR_INDEX,
699
			"cannot create a tree from a not fully merged index.");
700 701 702
		return GIT_EUNMERGED;
	}

703
	if (index->tree != NULL && index->tree->entry_count >= 0) {
704
		git_oid_cpy(oid, &index->tree->oid);
705
		return 0;
706 707
	}

708
	/* The tree cache didn't help us; we'll have to write
709
	 * out a tree. If the index is ignore_case, we must
710 711 712 713 714
	 * make it case-sensitive for the duration of the tree-write
	 * operation. */

	if (index->ignore_case) {
		old_ignore_case = true;
715
		git_index__set_ignore_case(index, false);
716 717
	}

718
	ret = write_tree(oid, repo, index, "", 0, &shared_buf);
719
	git_str_dispose(&shared_buf);
720 721

	if (old_ignore_case)
722
		git_index__set_ignore_case(index, true);
723

724 725 726 727 728 729 730 731 732 733 734 735 736 737 738
	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;
739
}
740

741
int git_treebuilder_new(
742 743 744
	git_treebuilder **builder_p,
	git_repository *repo,
	const git_tree *source)
745 746
{
	git_treebuilder *bld;
747
	size_t i;
748

Edward Thomson committed
749 750
	GIT_ASSERT_ARG(builder_p);
	GIT_ASSERT_ARG(repo);
751 752

	bld = git__calloc(1, sizeof(git_treebuilder));
753
	GIT_ERROR_CHECK_ALLOC(bld);
754

755 756
	bld->repo = repo;

757
	if (git_strmap_new(&bld->map) < 0) {
758
		git__free(bld);
759 760
		return -1;
	}
761 762

	if (source != NULL) {
763
		git_tree_entry *entry_src;
764

765
		git_array_foreach(source->entries, i, entry_src) {
766 767
			if (append_entry(
				bld, entry_src->filename,
768
				entry_src->oid,
769
				entry_src->attr,
770
				false) < 0)
771
				goto on_error;
772 773 774 775
		}
	}

	*builder_p = bld;
776 777 778 779 780
	return 0;

on_error:
	git_treebuilder_free(bld);
	return -1;
781 782
}

783 784 785 786 787
int git_treebuilder_insert(
	const git_tree_entry **entry_out,
	git_treebuilder *bld,
	const char *filename,
	const git_oid *id,
nulltoken committed
788
	git_filemode_t filemode)
789 790
{
	git_tree_entry *entry;
791
	int error;
792

Edward Thomson committed
793 794 795
	GIT_ASSERT_ARG(bld);
	GIT_ASSERT_ARG(id);
	GIT_ASSERT_ARG(filename);
796

797 798
	if ((error = check_entry(bld->repo, filename, id, filemode)) < 0)
		return error;
799

800
	if ((entry = git_strmap_get(bld->map, filename)) != NULL) {
801
		git_oid_cpy((git_oid *) entry->oid, id);
802
	} else {
803
		entry = alloc_entry(filename, strlen(filename), id);
804
		GIT_ERROR_CHECK_ALLOC(entry);
805

806
		if ((error = git_strmap_set(bld->map, entry->filename, entry)) < 0) {
807
			git_tree_entry_free(entry);
808
			git_error_set(GIT_ERROR_TREE, "failed to insert %s", filename);
809 810
			return -1;
		}
811 812
	}

813 814 815
	entry->attr = filemode;

	if (entry_out)
816 817
		*entry_out = entry;

818
	return 0;
819 820
}

821
static git_tree_entry *treebuilder_get(git_treebuilder *bld, const char *filename)
822
{
Edward Thomson committed
823 824 825
	GIT_ASSERT_ARG_WITH_RETVAL(bld, NULL);
	GIT_ASSERT_ARG_WITH_RETVAL(filename, NULL);

826
	return git_strmap_get(bld->map, filename);
827 828
}

829 830 831 832 833
const git_tree_entry *git_treebuilder_get(git_treebuilder *bld, const char *filename)
{
	return treebuilder_get(bld, filename);
}

834 835
int git_treebuilder_remove(git_treebuilder *bld, const char *filename)
{
836
	git_tree_entry *entry = treebuilder_get(bld, filename);
837

838
	if (entry == NULL)
839
		return tree_error("failed to remove entry: file isn't in the tree", filename);
840

841
	git_strmap_delete(bld->map, filename);
842
	git_tree_entry_free(entry);
843

844
	return 0;
845 846
}

847
int git_treebuilder_write(git_oid *oid, git_treebuilder *bld)
848
{
849
	GIT_ASSERT_ARG(oid);
Edward Thomson committed
850
	GIT_ASSERT_ARG(bld);
851

852
	return git_treebuilder__write_with_buffer(oid, bld, &bld->write_cache);
853 854
}

855
int git_treebuilder_filter(
856 857 858
	git_treebuilder *bld,
	git_treebuilder_filter_cb filter,
	void *payload)
859
{
860
	const char *filename;
861
	git_tree_entry *entry;
862

Edward Thomson committed
863 864
	GIT_ASSERT_ARG(bld);
	GIT_ASSERT_ARG(filter);
865

866 867 868
	git_strmap_foreach(bld->map, filename, entry, {
			if (filter(entry, payload)) {
				git_strmap_delete(bld->map, filename);
869
				git_tree_entry_free(entry);
870 871
			}
	});
872 873

	return 0;
874 875
}

876
int git_treebuilder_clear(git_treebuilder *bld)
877
{
878 879
	git_tree_entry *e;

Edward Thomson committed
880
	GIT_ASSERT_ARG(bld);
881

882
	git_strmap_foreach_value(bld->map, e, git_tree_entry_free(e));
883
	git_strmap_clear(bld->map);
884 885

	return 0;
886 887 888 889
}

void git_treebuilder_free(git_treebuilder *bld)
{
890 891 892
	if (bld == NULL)
		return;

893
	git_str_dispose(&bld->write_cache);
894
	git_treebuilder_clear(bld);
895
	git_strmap_free(bld->map);
896
	git__free(bld);
897 898
}

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

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

922
	if (filename_len == 0) {
923
		git_error_set(GIT_ERROR_TREE, "invalid tree path given");
924
		return GIT_ENOTFOUND;
925
	}
926

927
	entry = entry_fromname(root, path, filename_len);
928

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

935
	switch (path[filename_len]) {
936
	case '/':
937 938 939
		/* If there are more components in the path...
		 * then this entry *must* be a tree */
		if (!git_tree_entry__is_tree(entry)) {
940
			git_error_set(GIT_ERROR_TREE,
941
				   "the path '%.*s' exists but is not a tree", (int) filename_len, path);
942
			return GIT_ENOTFOUND;
943 944
		}

945
		/* If there's only a slash left in the path, we
946 947 948 949
		 * return the current entry; otherwise, we keep
		 * walking down the path */
		if (path[filename_len + 1] != '\0')
			break;
950
		/* fall through */
951 952 953
	case '\0':
		/* If there are no more components in the path, return
		 * this entry */
954
		return git_tree_entry_dup(entry_out, entry);
955
	}
956

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

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

966
	git_tree_free(subtree);
967 968 969
	return error;
}

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

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

Vicent Martí committed
994
		if (git_tree_entry__is_tree(entry)) {
995
			git_tree *subtree;
996
			size_t path_len = git_str_len(path);
997

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

1002
			/* append the next entry to the path */
1003 1004
			git_str_puts(path, entry->filename);
			git_str_putc(path, '/');
1005

1006
			if (git_str_oom(path))
1007 1008 1009
				error = -1;
			else
				error = tree_walk(subtree, callback, path, payload, preorder);
1010

1011
			git_tree_free(subtree);
1012 1013
			if (error != 0)
				break;
1014

1015
			git_str_truncate(path, path_len);
1016
		}
1017

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

1028
	return error;
1029 1030
}

1031
int git_tree_walk(
Ben Straub committed
1032
	const git_tree *tree,
1033 1034 1035
	git_treewalk_mode mode,
	git_treewalk_cb callback,
	void *payload)
1036
{
1037
	int error = 0;
1038
	git_str root_path = GIT_STR_INIT;
1039

1040
	if (mode != GIT_TREEWALK_POST && mode != GIT_TREEWALK_PRE) {
1041
		git_error_set(GIT_ERROR_INVALID, "invalid walking mode for tree walk");
1042
		return -1;
1043
	}
1044

1045 1046 1047
	error = tree_walk(
		tree, callback, &root_path, payload, (mode == GIT_TREEWALK_PRE));

1048
	git_str_dispose(&root_path);
1049 1050

	return error;
1051
}
1052

1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064
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);

1065
	git_error_set(GIT_ERROR_TREE, "duplicate entries given for update");
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
	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;
}

1094
static bool next_component(git_str *out, const char *in)
1095 1096 1097
{
	const char *slash = strchr(in, '/');

1098
	git_str_clear(out);
1099 1100

	if (slash)
1101
		git_str_put(out, in, slash - in);
1102 1103 1104 1105

	return !!slash;
}

1106
static int create_popped_tree(tree_stack_entry *current, tree_stack_entry *popped, git_str *component)
1107 1108 1109 1110 1111
{
	int error;
	git_oid new_tree;

	git_tree_free(popped->tree);
1112 1113 1114 1115 1116 1117 1118 1119 1120

	/* 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;
	}

1121 1122 1123 1124 1125 1126 1127 1128 1129
	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 */
1130 1131
	git_str_clear(component);
	git_str_puts(component, popped->name);
1132 1133
	git__free(popped->name);

1134
	GIT_ERROR_CHECK_ALLOC(component->ptr);
1135 1136 1137 1138 1139

	/* 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);
1140
		if (to_replace && git_tree_entry_type(to_replace) != GIT_OBJECT_TREE) {
1141
			git_error_set(GIT_ERROR_TREE, "D/F conflict when updating tree");
1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155
			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;
1156
	git_str component = GIT_STR_INIT;
1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167

	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);
1168
	GIT_ERROR_CHECK_ALLOC(root_elem);
1169 1170 1171 1172 1173 1174 1175 1176 1177
	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++) {
1178 1179
		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);
1180 1181 1182 1183 1184
		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)
1185
			common_prefix = git_fs_path_common_dirlen(last_update->path, update->path);
1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196

		/*
		 * 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);
Edward Thomson committed
1197
			GIT_ASSERT(popped);
1198 1199

			current = git_array_last(stack);
Edward Thomson committed
1200
			GIT_ASSERT(current);
1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213

			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;
1214 1215 1216
			if (!entry)
				entry = treebuilder_get(last->bld, component.ptr);

1217
			if (entry && git_tree_entry_type(entry) != GIT_OBJECT_TREE) {
1218
				git_error_set(GIT_ERROR_TREE, "D/F conflict when updating tree");
1219 1220 1221 1222 1223
				error = -1;
				goto cleanup;
			}

			new_entry = git_array_alloc(stack);
1224
			GIT_ERROR_CHECK_ALLOC(new_entry);
1225 1226 1227 1228 1229 1230 1231 1232 1233 1234
			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);
1235
			GIT_ERROR_CHECK_ALLOC(new_entry->name);
1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246

			/* 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);
1247
				char *basename = git_fs_path_basename(update->path);
1248 1249
				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)) {
1250
					git__free(basename);
1251
					git_error_set(GIT_ERROR_TREE, "cannot replace '%s' with '%s' at '%s'",
1252 1253 1254
						   git_object_type2string(git_tree_entry_type(e)),
						   git_object_type2string(git_object__type_from_filemode(update->filemode)),
						   update->path);
1255 1256
					error = -1;
					goto cleanup;
1257 1258 1259
				}

				error = git_treebuilder_insert(NULL, last->bld, basename, &update->id, update->filemode);
1260
				git__free(basename);
1261 1262 1263
				break;
			}
			case GIT_TREE_UPDATE_REMOVE:
1264
			{
1265
				tree_stack_entry *last = git_array_last(stack);
1266
				char *basename = git_fs_path_basename(update->path);
1267
				error = git_treebuilder_remove(last->bld, basename);
1268
				git__free(basename);
1269
				break;
1270
			}
1271
			default:
1272
				git_error_set(GIT_ERROR_TREE, "unknown action for update");
1273 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
				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);
		}
	}

1314
	git_str_dispose(&component);
1315 1316 1317 1318
	git_array_clear(stack);
	git_vector_free(&entries);
	return error;
}
1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331

/* Deprecated Functions */

#ifndef GIT_DEPRECATE_HARD

int git_treebuilder_write_with_buffer(git_oid *oid, git_treebuilder *bld, git_buf *buf)
{
	GIT_UNUSED(buf);

	return git_treebuilder_write(oid, bld);
}

#endif