1 /*
2 * Copyright (C) the libgit2 contributors. All rights reserved.
3 *
4 * This file is part of libgit2, distributed under the GNU GPL v2 with
5 * a Linking Exception. For full terms see the included COPYING file.
6 */
7
8 #include "tree.h"
9
10 #include "commit.h"
11 #include "git2/repository.h"
12 #include "git2/object.h"
13 #include "fileops.h"
14 #include "tree-cache.h"
15 #include "index.h"
16
17 #define DEFAULT_TREE_SIZE 16
18 #define MAX_FILEMODE_BYTES 6
19
20 #define TREE_ENTRY_CHECK_NAMELEN(n) \
21 if (n > UINT16_MAX) { git_error_set(GIT_ERROR_INVALID, "tree entry path too long"); }
22
valid_filemode(const int filemode)23 static bool valid_filemode(const int filemode)
24 {
25 return (filemode == GIT_FILEMODE_TREE
26 || filemode == GIT_FILEMODE_BLOB
27 || filemode == GIT_FILEMODE_BLOB_EXECUTABLE
28 || filemode == GIT_FILEMODE_LINK
29 || filemode == GIT_FILEMODE_COMMIT);
30 }
31
normalize_filemode(git_filemode_t filemode)32 GIT_INLINE(git_filemode_t) normalize_filemode(git_filemode_t filemode)
33 {
34 /* Tree bits set, but it's not a commit */
35 if (GIT_MODE_TYPE(filemode) == GIT_FILEMODE_TREE)
36 return GIT_FILEMODE_TREE;
37
38 /* If any of the x bits are set */
39 if (GIT_PERMS_IS_EXEC(filemode))
40 return GIT_FILEMODE_BLOB_EXECUTABLE;
41
42 /* 16XXXX means commit */
43 if (GIT_MODE_TYPE(filemode) == GIT_FILEMODE_COMMIT)
44 return GIT_FILEMODE_COMMIT;
45
46 /* 12XXXX means symlink */
47 if (GIT_MODE_TYPE(filemode) == GIT_FILEMODE_LINK)
48 return GIT_FILEMODE_LINK;
49
50 /* Otherwise, return a blob */
51 return GIT_FILEMODE_BLOB;
52 }
53
valid_entry_name(git_repository * repo,const char * filename)54 static int valid_entry_name(git_repository *repo, const char *filename)
55 {
56 return *filename != '\0' &&
57 git_path_isvalid(repo, filename, 0,
58 GIT_PATH_REJECT_TRAVERSAL | GIT_PATH_REJECT_DOT_GIT | GIT_PATH_REJECT_SLASH);
59 }
60
entry_sort_cmp(const void * a,const void * b)61 static int entry_sort_cmp(const void *a, const void *b)
62 {
63 const git_tree_entry *e1 = (const git_tree_entry *)a;
64 const git_tree_entry *e2 = (const git_tree_entry *)b;
65
66 return git_path_cmp(
67 e1->filename, e1->filename_len, git_tree_entry__is_tree(e1),
68 e2->filename, e2->filename_len, git_tree_entry__is_tree(e2),
69 git__strncmp);
70 }
71
git_tree_entry_cmp(const git_tree_entry * e1,const git_tree_entry * e2)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 /**
78 * Allocate a new self-contained entry, with enough space after it to
79 * store the filename and the id.
80 */
alloc_entry(const char * filename,size_t filename_len,const git_oid * id)81 static git_tree_entry *alloc_entry(const char *filename, size_t filename_len, const git_oid *id)
82 {
83 git_tree_entry *entry = NULL;
84 size_t tree_len;
85
86 TREE_ENTRY_CHECK_NAMELEN(filename_len);
87
88 if (GIT_ADD_SIZET_OVERFLOW(&tree_len, sizeof(git_tree_entry), filename_len) ||
89 GIT_ADD_SIZET_OVERFLOW(&tree_len, tree_len, 1) ||
90 GIT_ADD_SIZET_OVERFLOW(&tree_len, tree_len, GIT_OID_RAWSZ))
91 return NULL;
92
93 entry = git__calloc(1, tree_len);
94 if (!entry)
95 return NULL;
96
97 {
98 char *filename_ptr;
99 void *id_ptr;
100
101 filename_ptr = ((char *) entry) + sizeof(git_tree_entry);
102 memcpy(filename_ptr, filename, filename_len);
103 entry->filename = filename_ptr;
104
105 id_ptr = filename_ptr + filename_len + 1;
106 git_oid_cpy(id_ptr, id);
107 entry->oid = id_ptr;
108 }
109
110 entry->filename_len = (uint16_t)filename_len;
111
112 return entry;
113 }
114
115 struct tree_key_search {
116 const char *filename;
117 uint16_t filename_len;
118 };
119
homing_search_cmp(const void * key,const void * array_member)120 static int homing_search_cmp(const void *key, const void *array_member)
121 {
122 const struct tree_key_search *ksearch = key;
123 const git_tree_entry *entry = array_member;
124
125 const uint16_t len1 = ksearch->filename_len;
126 const uint16_t len2 = entry->filename_len;
127
128 return memcmp(
129 ksearch->filename,
130 entry->filename,
131 len1 < len2 ? len1 : len2
132 );
133 }
134
135 /*
136 * Search for an entry in a given tree.
137 *
138 * Note that this search is performed in two steps because
139 * of the way tree entries are sorted internally in git:
140 *
141 * Entries in a tree are not sorted alphabetically; two entries
142 * with the same root prefix will have different positions
143 * depending on whether they are folders (subtrees) or normal files.
144 *
145 * Consequently, it is not possible to find an entry on the tree
146 * with a binary search if you don't know whether the filename
147 * you're looking for is a folder or a normal file.
148 *
149 * To work around this, we first perform a homing binary search
150 * on the tree, using the minimal length root prefix of our filename.
151 * Once the comparisons for this homing search start becoming
152 * ambiguous because of folder vs file sorting, we look linearly
153 * around the area for our target file.
154 */
tree_key_search(size_t * at_pos,const git_tree * tree,const char * filename,size_t filename_len)155 static int tree_key_search(
156 size_t *at_pos,
157 const git_tree *tree,
158 const char *filename,
159 size_t filename_len)
160 {
161 struct tree_key_search ksearch;
162 const git_tree_entry *entry;
163 size_t homing, i;
164
165 TREE_ENTRY_CHECK_NAMELEN(filename_len);
166
167 ksearch.filename = filename;
168 ksearch.filename_len = (uint16_t)filename_len;
169
170 /* Initial homing search; find an entry on the tree with
171 * the same prefix as the filename we're looking for */
172
173 if (git_array_search(&homing,
174 tree->entries, &homing_search_cmp, &ksearch) < 0)
175 return GIT_ENOTFOUND; /* just a signal error; not passed back to user */
176
177 /* We found a common prefix. Look forward as long as
178 * there are entries that share the common prefix */
179 for (i = homing; i < tree->entries.size; ++i) {
180 entry = git_array_get(tree->entries, i);
181
182 if (homing_search_cmp(&ksearch, entry) < 0)
183 break;
184
185 if (entry->filename_len == filename_len &&
186 memcmp(filename, entry->filename, filename_len) == 0) {
187 if (at_pos)
188 *at_pos = i;
189
190 return 0;
191 }
192 }
193
194 /* If we haven't found our filename yet, look backwards
195 * too as long as we have entries with the same prefix */
196 if (homing > 0) {
197 i = homing - 1;
198
199 do {
200 entry = git_array_get(tree->entries, i);
201
202 if (homing_search_cmp(&ksearch, entry) > 0)
203 break;
204
205 if (entry->filename_len == filename_len &&
206 memcmp(filename, entry->filename, filename_len) == 0) {
207 if (at_pos)
208 *at_pos = i;
209
210 return 0;
211 }
212 } while (i-- > 0);
213 }
214
215 /* The filename doesn't exist at all */
216 return GIT_ENOTFOUND;
217 }
218
git_tree_entry_free(git_tree_entry * entry)219 void git_tree_entry_free(git_tree_entry *entry)
220 {
221 if (entry == NULL)
222 return;
223
224 git__free(entry);
225 }
226
git_tree_entry_dup(git_tree_entry ** dest,const git_tree_entry * source)227 int git_tree_entry_dup(git_tree_entry **dest, const git_tree_entry *source)
228 {
229 git_tree_entry *cpy;
230
231 assert(source);
232
233 cpy = alloc_entry(source->filename, source->filename_len, source->oid);
234 if (cpy == NULL)
235 return -1;
236
237 cpy->attr = source->attr;
238
239 *dest = cpy;
240 return 0;
241 }
242
git_tree__free(void * _tree)243 void git_tree__free(void *_tree)
244 {
245 git_tree *tree = _tree;
246
247 git_odb_object_free(tree->odb_obj);
248 git_array_clear(tree->entries);
249 git__free(tree);
250 }
251
git_tree_entry_filemode(const git_tree_entry * entry)252 git_filemode_t git_tree_entry_filemode(const git_tree_entry *entry)
253 {
254 return normalize_filemode(entry->attr);
255 }
256
git_tree_entry_filemode_raw(const git_tree_entry * entry)257 git_filemode_t git_tree_entry_filemode_raw(const git_tree_entry *entry)
258 {
259 return entry->attr;
260 }
261
git_tree_entry_name(const git_tree_entry * entry)262 const char *git_tree_entry_name(const git_tree_entry *entry)
263 {
264 assert(entry);
265 return entry->filename;
266 }
267
git_tree_entry_id(const git_tree_entry * entry)268 const git_oid *git_tree_entry_id(const git_tree_entry *entry)
269 {
270 assert(entry);
271 return entry->oid;
272 }
273
git_tree_entry_type(const git_tree_entry * entry)274 git_object_t git_tree_entry_type(const git_tree_entry *entry)
275 {
276 assert(entry);
277
278 if (S_ISGITLINK(entry->attr))
279 return GIT_OBJECT_COMMIT;
280 else if (S_ISDIR(entry->attr))
281 return GIT_OBJECT_TREE;
282 else
283 return GIT_OBJECT_BLOB;
284 }
285
git_tree_entry_to_object(git_object ** object_out,git_repository * repo,const git_tree_entry * entry)286 int git_tree_entry_to_object(
287 git_object **object_out,
288 git_repository *repo,
289 const git_tree_entry *entry)
290 {
291 assert(entry && object_out);
292 return git_object_lookup(object_out, repo, entry->oid, GIT_OBJECT_ANY);
293 }
294
entry_fromname(const git_tree * tree,const char * name,size_t name_len)295 static const git_tree_entry *entry_fromname(
296 const git_tree *tree, const char *name, size_t name_len)
297 {
298 size_t idx;
299
300 if (tree_key_search(&idx, tree, name, name_len) < 0)
301 return NULL;
302
303 return git_array_get(tree->entries, idx);
304 }
305
git_tree_entry_byname(const git_tree * tree,const char * filename)306 const git_tree_entry *git_tree_entry_byname(
307 const git_tree *tree, const char *filename)
308 {
309 assert(tree && filename);
310
311 return entry_fromname(tree, filename, strlen(filename));
312 }
313
git_tree_entry_byindex(const git_tree * tree,size_t idx)314 const git_tree_entry *git_tree_entry_byindex(
315 const git_tree *tree, size_t idx)
316 {
317 assert(tree);
318 return git_array_get(tree->entries, idx);
319 }
320
git_tree_entry_byid(const git_tree * tree,const git_oid * id)321 const git_tree_entry *git_tree_entry_byid(
322 const git_tree *tree, const git_oid *id)
323 {
324 size_t i;
325 const git_tree_entry *e;
326
327 assert(tree);
328
329 git_array_foreach(tree->entries, i, e) {
330 if (memcmp(&e->oid->id, &id->id, sizeof(id->id)) == 0)
331 return e;
332 }
333
334 return NULL;
335 }
336
git_tree_entrycount(const git_tree * tree)337 size_t git_tree_entrycount(const git_tree *tree)
338 {
339 assert(tree);
340 return tree->entries.size;
341 }
342
git_treebuilder_entrycount(git_treebuilder * bld)343 unsigned int git_treebuilder_entrycount(git_treebuilder *bld)
344 {
345 assert(bld);
346
347 return git_strmap_num_entries(bld->map);
348 }
349
tree_error(const char * str,const char * path)350 static int tree_error(const char *str, const char *path)
351 {
352 if (path)
353 git_error_set(GIT_ERROR_TREE, "%s - %s", str, path);
354 else
355 git_error_set(GIT_ERROR_TREE, "%s", str);
356 return -1;
357 }
358
parse_mode(uint16_t * mode_out,const char * buffer,size_t buffer_len,const char ** buffer_out)359 static int parse_mode(uint16_t *mode_out, const char *buffer, size_t buffer_len, const char **buffer_out)
360 {
361 int32_t mode;
362 int error;
363
364 if (!buffer_len || git__isspace(*buffer))
365 return -1;
366
367 if ((error = git__strntol32(&mode, buffer, buffer_len, buffer_out, 8)) < 0)
368 return error;
369
370 if (mode < 0 || mode > UINT16_MAX)
371 return -1;
372
373 *mode_out = mode;
374
375 return 0;
376 }
377
git_tree__parse_raw(void * _tree,const char * data,size_t size)378 int git_tree__parse_raw(void *_tree, const char *data, size_t size)
379 {
380 git_tree *tree = _tree;
381 const char *buffer;
382 const char *buffer_end;
383
384 buffer = data;
385 buffer_end = buffer + size;
386
387 tree->odb_obj = NULL;
388 git_array_init_to_size(tree->entries, DEFAULT_TREE_SIZE);
389 GIT_ERROR_CHECK_ARRAY(tree->entries);
390
391 while (buffer < buffer_end) {
392 git_tree_entry *entry;
393 size_t filename_len;
394 const char *nul;
395 uint16_t attr;
396
397 if (parse_mode(&attr, buffer, buffer_end - buffer, &buffer) < 0 || !buffer)
398 return tree_error("failed to parse tree: can't parse filemode", NULL);
399
400 if (buffer >= buffer_end || (*buffer++) != ' ')
401 return tree_error("failed to parse tree: missing space after filemode", NULL);
402
403 if ((nul = memchr(buffer, 0, buffer_end - buffer)) == NULL)
404 return tree_error("failed to parse tree: object is corrupted", NULL);
405
406 if ((filename_len = nul - buffer) == 0 || filename_len > UINT16_MAX)
407 return tree_error("failed to parse tree: can't parse filename", NULL);
408
409 if ((buffer_end - (nul + 1)) < GIT_OID_RAWSZ)
410 return tree_error("failed to parse tree: can't parse OID", NULL);
411
412 /* Allocate the entry */
413 {
414 entry = git_array_alloc(tree->entries);
415 GIT_ERROR_CHECK_ALLOC(entry);
416
417 entry->attr = attr;
418 entry->filename_len = (uint16_t)filename_len;
419 entry->filename = buffer;
420 entry->oid = (git_oid *) ((char *) buffer + filename_len + 1);
421 }
422
423 buffer += filename_len + 1;
424 buffer += GIT_OID_RAWSZ;
425 }
426
427 return 0;
428 }
429
git_tree__parse(void * _tree,git_odb_object * odb_obj)430 int git_tree__parse(void *_tree, git_odb_object *odb_obj)
431 {
432 git_tree *tree = _tree;
433
434 if ((git_tree__parse_raw(tree,
435 git_odb_object_data(odb_obj),
436 git_odb_object_size(odb_obj))) < 0)
437 return -1;
438
439 if (git_odb_object_dup(&tree->odb_obj, odb_obj) < 0)
440 return -1;
441
442 return 0;
443 }
444
find_next_dir(const char * dirname,git_index * index,size_t start)445 static size_t find_next_dir(const char *dirname, git_index *index, size_t start)
446 {
447 size_t dirlen, i, entries = git_index_entrycount(index);
448
449 dirlen = strlen(dirname);
450 for (i = start; i < entries; ++i) {
451 const git_index_entry *entry = git_index_get_byindex(index, i);
452 if (strlen(entry->path) < dirlen ||
453 memcmp(entry->path, dirname, dirlen) ||
454 (dirlen > 0 && entry->path[dirlen] != '/')) {
455 break;
456 }
457 }
458
459 return i;
460 }
461
otype_from_mode(git_filemode_t filemode)462 static git_object_t otype_from_mode(git_filemode_t filemode)
463 {
464 switch (filemode) {
465 case GIT_FILEMODE_TREE:
466 return GIT_OBJECT_TREE;
467 case GIT_FILEMODE_COMMIT:
468 return GIT_OBJECT_COMMIT;
469 default:
470 return GIT_OBJECT_BLOB;
471 }
472 }
473
check_entry(git_repository * repo,const char * filename,const git_oid * id,git_filemode_t filemode)474 static int check_entry(git_repository *repo, const char *filename, const git_oid *id, git_filemode_t filemode)
475 {
476 if (!valid_filemode(filemode))
477 return tree_error("failed to insert entry: invalid filemode for file", filename);
478
479 if (!valid_entry_name(repo, filename))
480 return tree_error("failed to insert entry: invalid name for a tree entry", filename);
481
482 if (git_oid_iszero(id))
483 return tree_error("failed to insert entry: invalid null OID", filename);
484
485 if (filemode != GIT_FILEMODE_COMMIT &&
486 !git_object__is_valid(repo, id, otype_from_mode(filemode)))
487 return tree_error("failed to insert entry: invalid object specified", filename);
488
489 return 0;
490 }
491
append_entry(git_treebuilder * bld,const char * filename,const git_oid * id,git_filemode_t filemode,bool validate)492 static int append_entry(
493 git_treebuilder *bld,
494 const char *filename,
495 const git_oid *id,
496 git_filemode_t filemode,
497 bool validate)
498 {
499 git_tree_entry *entry;
500 int error = 0;
501
502 if (validate && ((error = check_entry(bld->repo, filename, id, filemode)) < 0))
503 return error;
504
505 entry = alloc_entry(filename, strlen(filename), id);
506 GIT_ERROR_CHECK_ALLOC(entry);
507
508 entry->attr = (uint16_t)filemode;
509
510 git_strmap_insert(bld->map, entry->filename, entry, &error);
511 if (error < 0) {
512 git_tree_entry_free(entry);
513 git_error_set(GIT_ERROR_TREE, "failed to append entry %s to the tree builder", filename);
514 return -1;
515 }
516
517 return 0;
518 }
519
write_tree(git_oid * oid,git_repository * repo,git_index * index,const char * dirname,size_t start,git_buf * shared_buf)520 static int write_tree(
521 git_oid *oid,
522 git_repository *repo,
523 git_index *index,
524 const char *dirname,
525 size_t start,
526 git_buf *shared_buf)
527 {
528 git_treebuilder *bld = NULL;
529 size_t i, entries = git_index_entrycount(index);
530 int error;
531 size_t dirname_len = strlen(dirname);
532 const git_tree_cache *cache;
533
534 cache = git_tree_cache_get(index->tree, dirname);
535 if (cache != NULL && cache->entry_count >= 0){
536 git_oid_cpy(oid, &cache->oid);
537 return (int)find_next_dir(dirname, index, start);
538 }
539
540 if ((error = git_treebuilder_new(&bld, repo, NULL)) < 0 || bld == NULL)
541 return -1;
542
543 /*
544 * This loop is unfortunate, but necessary. The index doesn't have
545 * any directores, so we need to handle that manually, and we
546 * need to keep track of the current position.
547 */
548 for (i = start; i < entries; ++i) {
549 const git_index_entry *entry = git_index_get_byindex(index, i);
550 const char *filename, *next_slash;
551
552 /*
553 * If we've left our (sub)tree, exit the loop and return. The
554 * first check is an early out (and security for the
555 * third). The second check is a simple prefix comparison. The
556 * third check catches situations where there is a directory
557 * win32/sys and a file win32mmap.c. Without it, the following
558 * code believes there is a file win32/mmap.c
559 */
560 if (strlen(entry->path) < dirname_len ||
561 memcmp(entry->path, dirname, dirname_len) ||
562 (dirname_len > 0 && entry->path[dirname_len] != '/')) {
563 break;
564 }
565
566 filename = entry->path + dirname_len;
567 if (*filename == '/')
568 filename++;
569 next_slash = strchr(filename, '/');
570 if (next_slash) {
571 git_oid sub_oid;
572 int written;
573 char *subdir, *last_comp;
574
575 subdir = git__strndup(entry->path, next_slash - entry->path);
576 GIT_ERROR_CHECK_ALLOC(subdir);
577
578 /* Write out the subtree */
579 written = write_tree(&sub_oid, repo, index, subdir, i, shared_buf);
580 if (written < 0) {
581 git__free(subdir);
582 goto on_error;
583 } else {
584 i = written - 1; /* -1 because of the loop increment */
585 }
586
587 /*
588 * We need to figure out what we want toinsert
589 * into this tree. If we're traversing
590 * deps/zlib/, then we only want to write
591 * 'zlib' into the tree.
592 */
593 last_comp = strrchr(subdir, '/');
594 if (last_comp) {
595 last_comp++; /* Get rid of the '/' */
596 } else {
597 last_comp = subdir;
598 }
599
600 error = append_entry(bld, last_comp, &sub_oid, S_IFDIR, true);
601 git__free(subdir);
602 if (error < 0)
603 goto on_error;
604 } else {
605 error = append_entry(bld, filename, &entry->id, entry->mode, true);
606 if (error < 0)
607 goto on_error;
608 }
609 }
610
611 if (git_treebuilder_write_with_buffer(oid, bld, shared_buf) < 0)
612 goto on_error;
613
614 git_treebuilder_free(bld);
615 return (int)i;
616
617 on_error:
618 git_treebuilder_free(bld);
619 return -1;
620 }
621
git_tree__write_index(git_oid * oid,git_index * index,git_repository * repo)622 int git_tree__write_index(
623 git_oid *oid, git_index *index, git_repository *repo)
624 {
625 int ret;
626 git_tree *tree;
627 git_buf shared_buf = GIT_BUF_INIT;
628 bool old_ignore_case = false;
629
630 assert(oid && index && repo);
631
632 if (git_index_has_conflicts(index)) {
633 git_error_set(GIT_ERROR_INDEX,
634 "cannot create a tree from a not fully merged index.");
635 return GIT_EUNMERGED;
636 }
637
638 if (index->tree != NULL && index->tree->entry_count >= 0) {
639 git_oid_cpy(oid, &index->tree->oid);
640 return 0;
641 }
642
643 /* The tree cache didn't help us; we'll have to write
644 * out a tree. If the index is ignore_case, we must
645 * make it case-sensitive for the duration of the tree-write
646 * operation. */
647
648 if (index->ignore_case) {
649 old_ignore_case = true;
650 git_index__set_ignore_case(index, false);
651 }
652
653 ret = write_tree(oid, repo, index, "", 0, &shared_buf);
654 git_buf_dispose(&shared_buf);
655
656 if (old_ignore_case)
657 git_index__set_ignore_case(index, true);
658
659 index->tree = NULL;
660
661 if (ret < 0)
662 return ret;
663
664 git_pool_clear(&index->tree_pool);
665
666 if ((ret = git_tree_lookup(&tree, repo, oid)) < 0)
667 return ret;
668
669 /* Read the tree cache into the index */
670 ret = git_tree_cache_read_tree(&index->tree, tree, &index->tree_pool);
671 git_tree_free(tree);
672
673 return ret;
674 }
675
git_treebuilder_new(git_treebuilder ** builder_p,git_repository * repo,const git_tree * source)676 int git_treebuilder_new(
677 git_treebuilder **builder_p,
678 git_repository *repo,
679 const git_tree *source)
680 {
681 git_treebuilder *bld;
682 size_t i;
683
684 assert(builder_p && repo);
685
686 bld = git__calloc(1, sizeof(git_treebuilder));
687 GIT_ERROR_CHECK_ALLOC(bld);
688
689 bld->repo = repo;
690
691 if (git_strmap_alloc(&bld->map) < 0) {
692 git__free(bld);
693 return -1;
694 }
695
696 if (source != NULL) {
697 git_tree_entry *entry_src;
698
699 git_array_foreach(source->entries, i, entry_src) {
700 if (append_entry(
701 bld, entry_src->filename,
702 entry_src->oid,
703 entry_src->attr,
704 false) < 0)
705 goto on_error;
706 }
707 }
708
709 *builder_p = bld;
710 return 0;
711
712 on_error:
713 git_treebuilder_free(bld);
714 return -1;
715 }
716
git_treebuilder_insert(const git_tree_entry ** entry_out,git_treebuilder * bld,const char * filename,const git_oid * id,git_filemode_t filemode)717 int git_treebuilder_insert(
718 const git_tree_entry **entry_out,
719 git_treebuilder *bld,
720 const char *filename,
721 const git_oid *id,
722 git_filemode_t filemode)
723 {
724 git_tree_entry *entry;
725 int error;
726 size_t pos;
727
728 assert(bld && id && filename);
729
730 if ((error = check_entry(bld->repo, filename, id, filemode)) < 0)
731 return error;
732
733 pos = git_strmap_lookup_index(bld->map, filename);
734 if (git_strmap_valid_index(bld->map, pos)) {
735 entry = git_strmap_value_at(bld->map, pos);
736 git_oid_cpy((git_oid *) entry->oid, id);
737 } else {
738 entry = alloc_entry(filename, strlen(filename), id);
739 GIT_ERROR_CHECK_ALLOC(entry);
740
741 git_strmap_insert(bld->map, entry->filename, entry, &error);
742
743 if (error < 0) {
744 git_tree_entry_free(entry);
745 git_error_set(GIT_ERROR_TREE, "failed to insert %s", filename);
746 return -1;
747 }
748 }
749
750 entry->attr = filemode;
751
752 if (entry_out)
753 *entry_out = entry;
754
755 return 0;
756 }
757
treebuilder_get(git_treebuilder * bld,const char * filename)758 static git_tree_entry *treebuilder_get(git_treebuilder *bld, const char *filename)
759 {
760 git_tree_entry *entry = NULL;
761 size_t pos;
762
763 assert(bld && filename);
764
765 pos = git_strmap_lookup_index(bld->map, filename);
766 if (git_strmap_valid_index(bld->map, pos))
767 entry = git_strmap_value_at(bld->map, pos);
768
769 return entry;
770 }
771
git_treebuilder_get(git_treebuilder * bld,const char * filename)772 const git_tree_entry *git_treebuilder_get(git_treebuilder *bld, const char *filename)
773 {
774 return treebuilder_get(bld, filename);
775 }
776
git_treebuilder_remove(git_treebuilder * bld,const char * filename)777 int git_treebuilder_remove(git_treebuilder *bld, const char *filename)
778 {
779 git_tree_entry *entry = treebuilder_get(bld, filename);
780
781 if (entry == NULL)
782 return tree_error("failed to remove entry: file isn't in the tree", filename);
783
784 git_strmap_delete(bld->map, filename);
785 git_tree_entry_free(entry);
786
787 return 0;
788 }
789
git_treebuilder_write(git_oid * oid,git_treebuilder * bld)790 int git_treebuilder_write(git_oid *oid, git_treebuilder *bld)
791 {
792 int error;
793 git_buf buffer = GIT_BUF_INIT;
794
795 error = git_treebuilder_write_with_buffer(oid, bld, &buffer);
796
797 git_buf_dispose(&buffer);
798 return error;
799 }
800
git_treebuilder_write_with_buffer(git_oid * oid,git_treebuilder * bld,git_buf * tree)801 int git_treebuilder_write_with_buffer(git_oid *oid, git_treebuilder *bld, git_buf *tree)
802 {
803 int error = 0;
804 size_t i, entrycount;
805 git_odb *odb;
806 git_tree_entry *entry;
807 git_vector entries = GIT_VECTOR_INIT;
808
809 assert(bld);
810 assert(tree);
811
812 git_buf_clear(tree);
813
814 entrycount = git_strmap_num_entries(bld->map);
815 if ((error = git_vector_init(&entries, entrycount, entry_sort_cmp)) < 0)
816 goto out;
817
818 if (tree->asize == 0 &&
819 (error = git_buf_grow(tree, entrycount * 72)) < 0)
820 goto out;
821
822 git_strmap_foreach_value(bld->map, entry, {
823 if ((error = git_vector_insert(&entries, entry)) < 0)
824 goto out;
825 });
826
827 git_vector_sort(&entries);
828
829 for (i = 0; i < entries.length && !error; ++i) {
830 entry = git_vector_get(&entries, i);
831
832 git_buf_printf(tree, "%o ", entry->attr);
833 git_buf_put(tree, entry->filename, entry->filename_len + 1);
834 git_buf_put(tree, (char *)entry->oid->id, GIT_OID_RAWSZ);
835
836 if (git_buf_oom(tree)) {
837 error = -1;
838 goto out;
839 }
840 }
841
842 if ((error = git_repository_odb__weakptr(&odb, bld->repo)) == 0)
843 error = git_odb_write(oid, odb, tree->ptr, tree->size, GIT_OBJECT_TREE);
844
845 out:
846 git_vector_free(&entries);
847
848 return error;
849 }
850
git_treebuilder_filter(git_treebuilder * bld,git_treebuilder_filter_cb filter,void * payload)851 void git_treebuilder_filter(
852 git_treebuilder *bld,
853 git_treebuilder_filter_cb filter,
854 void *payload)
855 {
856 const char *filename;
857 git_tree_entry *entry;
858
859 assert(bld && filter);
860
861 git_strmap_foreach(bld->map, filename, entry, {
862 if (filter(entry, payload)) {
863 git_strmap_delete(bld->map, filename);
864 git_tree_entry_free(entry);
865 }
866 });
867 }
868
git_treebuilder_clear(git_treebuilder * bld)869 void git_treebuilder_clear(git_treebuilder *bld)
870 {
871 git_tree_entry *e;
872
873 assert(bld);
874
875 git_strmap_foreach_value(bld->map, e, git_tree_entry_free(e));
876 git_strmap_clear(bld->map);
877 }
878
git_treebuilder_free(git_treebuilder * bld)879 void git_treebuilder_free(git_treebuilder *bld)
880 {
881 if (bld == NULL)
882 return;
883
884 git_treebuilder_clear(bld);
885 git_strmap_free(bld->map);
886 git__free(bld);
887 }
888
subpath_len(const char * path)889 static size_t subpath_len(const char *path)
890 {
891 const char *slash_pos = strchr(path, '/');
892 if (slash_pos == NULL)
893 return strlen(path);
894
895 return slash_pos - path;
896 }
897
git_tree_entry_bypath(git_tree_entry ** entry_out,const git_tree * root,const char * path)898 int git_tree_entry_bypath(
899 git_tree_entry **entry_out,
900 const git_tree *root,
901 const char *path)
902 {
903 int error = 0;
904 git_tree *subtree;
905 const git_tree_entry *entry;
906 size_t filename_len;
907
908 /* Find how long is the current path component (i.e.
909 * the filename between two slashes */
910 filename_len = subpath_len(path);
911
912 if (filename_len == 0) {
913 git_error_set(GIT_ERROR_TREE, "invalid tree path given");
914 return GIT_ENOTFOUND;
915 }
916
917 entry = entry_fromname(root, path, filename_len);
918
919 if (entry == NULL) {
920 git_error_set(GIT_ERROR_TREE,
921 "the path '%.*s' does not exist in the given tree", (int) filename_len, path);
922 return GIT_ENOTFOUND;
923 }
924
925 switch (path[filename_len]) {
926 case '/':
927 /* If there are more components in the path...
928 * then this entry *must* be a tree */
929 if (!git_tree_entry__is_tree(entry)) {
930 git_error_set(GIT_ERROR_TREE,
931 "the path '%.*s' exists but is not a tree", (int) filename_len, path);
932 return GIT_ENOTFOUND;
933 }
934
935 /* If there's only a slash left in the path, we
936 * return the current entry; otherwise, we keep
937 * walking down the path */
938 if (path[filename_len + 1] != '\0')
939 break;
940 /* fall through */
941 case '\0':
942 /* If there are no more components in the path, return
943 * this entry */
944 return git_tree_entry_dup(entry_out, entry);
945 }
946
947 if (git_tree_lookup(&subtree, root->object.repo, entry->oid) < 0)
948 return -1;
949
950 error = git_tree_entry_bypath(
951 entry_out,
952 subtree,
953 path + filename_len + 1
954 );
955
956 git_tree_free(subtree);
957 return error;
958 }
959
tree_walk(const git_tree * tree,git_treewalk_cb callback,git_buf * path,void * payload,bool preorder)960 static int tree_walk(
961 const git_tree *tree,
962 git_treewalk_cb callback,
963 git_buf *path,
964 void *payload,
965 bool preorder)
966 {
967 int error = 0;
968 size_t i;
969 const git_tree_entry *entry;
970
971 git_array_foreach(tree->entries, i, entry) {
972 if (preorder) {
973 error = callback(path->ptr, entry, payload);
974 if (error < 0) { /* negative value stops iteration */
975 git_error_set_after_callback_function(error, "git_tree_walk");
976 break;
977 }
978 if (error > 0) { /* positive value skips this entry */
979 error = 0;
980 continue;
981 }
982 }
983
984 if (git_tree_entry__is_tree(entry)) {
985 git_tree *subtree;
986 size_t path_len = git_buf_len(path);
987
988 error = git_tree_lookup(&subtree, tree->object.repo, entry->oid);
989 if (error < 0)
990 break;
991
992 /* append the next entry to the path */
993 git_buf_puts(path, entry->filename);
994 git_buf_putc(path, '/');
995
996 if (git_buf_oom(path))
997 error = -1;
998 else
999 error = tree_walk(subtree, callback, path, payload, preorder);
1000
1001 git_tree_free(subtree);
1002 if (error != 0)
1003 break;
1004
1005 git_buf_truncate(path, path_len);
1006 }
1007
1008 if (!preorder) {
1009 error = callback(path->ptr, entry, payload);
1010 if (error < 0) { /* negative value stops iteration */
1011 git_error_set_after_callback_function(error, "git_tree_walk");
1012 break;
1013 }
1014 error = 0;
1015 }
1016 }
1017
1018 return error;
1019 }
1020
git_tree_walk(const git_tree * tree,git_treewalk_mode mode,git_treewalk_cb callback,void * payload)1021 int git_tree_walk(
1022 const git_tree *tree,
1023 git_treewalk_mode mode,
1024 git_treewalk_cb callback,
1025 void *payload)
1026 {
1027 int error = 0;
1028 git_buf root_path = GIT_BUF_INIT;
1029
1030 if (mode != GIT_TREEWALK_POST && mode != GIT_TREEWALK_PRE) {
1031 git_error_set(GIT_ERROR_INVALID, "invalid walking mode for tree walk");
1032 return -1;
1033 }
1034
1035 error = tree_walk(
1036 tree, callback, &root_path, payload, (mode == GIT_TREEWALK_PRE));
1037
1038 git_buf_dispose(&root_path);
1039
1040 return error;
1041 }
1042
compare_entries(const void * _a,const void * _b)1043 static int compare_entries(const void *_a, const void *_b)
1044 {
1045 const git_tree_update *a = (git_tree_update *) _a;
1046 const git_tree_update *b = (git_tree_update *) _b;
1047
1048 return strcmp(a->path, b->path);
1049 }
1050
on_dup_entry(void ** old,void * new)1051 static int on_dup_entry(void **old, void *new)
1052 {
1053 GIT_UNUSED(old); GIT_UNUSED(new);
1054
1055 git_error_set(GIT_ERROR_TREE, "duplicate entries given for update");
1056 return -1;
1057 }
1058
1059 /*
1060 * We keep the previous tree and the new one at each level of the
1061 * stack. When we leave a level we're done with that tree and we can
1062 * write it out to the odb.
1063 */
1064 typedef struct {
1065 git_treebuilder *bld;
1066 git_tree *tree;
1067 char *name;
1068 } tree_stack_entry;
1069
1070 /** Count how many slashes (i.e. path components) there are in this string */
count_slashes(const char * path)1071 GIT_INLINE(size_t) count_slashes(const char *path)
1072 {
1073 size_t count = 0;
1074 const char *slash;
1075
1076 while ((slash = strchr(path, '/')) != NULL) {
1077 count++;
1078 path = slash + 1;
1079 }
1080
1081 return count;
1082 }
1083
next_component(git_buf * out,const char * in)1084 static bool next_component(git_buf *out, const char *in)
1085 {
1086 const char *slash = strchr(in, '/');
1087
1088 git_buf_clear(out);
1089
1090 if (slash)
1091 git_buf_put(out, in, slash - in);
1092
1093 return !!slash;
1094 }
1095
create_popped_tree(tree_stack_entry * current,tree_stack_entry * popped,git_buf * component)1096 static int create_popped_tree(tree_stack_entry *current, tree_stack_entry *popped, git_buf *component)
1097 {
1098 int error;
1099 git_oid new_tree;
1100
1101 git_tree_free(popped->tree);
1102
1103 /* If the tree would be empty, remove it from the one higher up */
1104 if (git_treebuilder_entrycount(popped->bld) == 0) {
1105 git_treebuilder_free(popped->bld);
1106 error = git_treebuilder_remove(current->bld, popped->name);
1107 git__free(popped->name);
1108 return error;
1109 }
1110
1111 error = git_treebuilder_write(&new_tree, popped->bld);
1112 git_treebuilder_free(popped->bld);
1113
1114 if (error < 0) {
1115 git__free(popped->name);
1116 return error;
1117 }
1118
1119 /* We've written out the tree, now we have to put the new value into its parent */
1120 git_buf_clear(component);
1121 git_buf_puts(component, popped->name);
1122 git__free(popped->name);
1123
1124 GIT_ERROR_CHECK_ALLOC(component->ptr);
1125
1126 /* Error out if this would create a D/F conflict in this update */
1127 if (current->tree) {
1128 const git_tree_entry *to_replace;
1129 to_replace = git_tree_entry_byname(current->tree, component->ptr);
1130 if (to_replace && git_tree_entry_type(to_replace) != GIT_OBJECT_TREE) {
1131 git_error_set(GIT_ERROR_TREE, "D/F conflict when updating tree");
1132 return -1;
1133 }
1134 }
1135
1136 return git_treebuilder_insert(NULL, current->bld, component->ptr, &new_tree, GIT_FILEMODE_TREE);
1137 }
1138
git_tree_create_updated(git_oid * out,git_repository * repo,git_tree * baseline,size_t nupdates,const git_tree_update * updates)1139 int git_tree_create_updated(git_oid *out, git_repository *repo, git_tree *baseline, size_t nupdates, const git_tree_update *updates)
1140 {
1141 git_array_t(tree_stack_entry) stack = GIT_ARRAY_INIT;
1142 tree_stack_entry *root_elem;
1143 git_vector entries;
1144 int error;
1145 size_t i;
1146 git_buf component = GIT_BUF_INIT;
1147
1148 if ((error = git_vector_init(&entries, nupdates, compare_entries)) < 0)
1149 return error;
1150
1151 /* Sort the entries for treversal */
1152 for (i = 0 ; i < nupdates; i++) {
1153 if ((error = git_vector_insert_sorted(&entries, (void *) &updates[i], on_dup_entry)) < 0)
1154 goto cleanup;
1155 }
1156
1157 root_elem = git_array_alloc(stack);
1158 GIT_ERROR_CHECK_ALLOC(root_elem);
1159 memset(root_elem, 0, sizeof(*root_elem));
1160
1161 if (baseline && (error = git_tree_dup(&root_elem->tree, baseline)) < 0)
1162 goto cleanup;
1163
1164 if ((error = git_treebuilder_new(&root_elem->bld, repo, root_elem->tree)) < 0)
1165 goto cleanup;
1166
1167 for (i = 0; i < nupdates; i++) {
1168 const git_tree_update *last_update = i == 0 ? NULL : git_vector_get(&entries, i-1);
1169 const git_tree_update *update = git_vector_get(&entries, i);
1170 size_t common_prefix = 0, steps_up, j;
1171 const char *path;
1172
1173 /* Figure out how much we need to change from the previous tree */
1174 if (last_update)
1175 common_prefix = git_path_common_dirlen(last_update->path, update->path);
1176
1177 /*
1178 * The entries are sorted, so when we find we're no
1179 * longer in the same directory, we need to abandon
1180 * the old tree (steps up) and dive down to the next
1181 * one.
1182 */
1183 steps_up = last_update == NULL ? 0 : count_slashes(&last_update->path[common_prefix]);
1184
1185 for (j = 0; j < steps_up; j++) {
1186 tree_stack_entry *current, *popped = git_array_pop(stack);
1187 assert(popped);
1188
1189 current = git_array_last(stack);
1190 assert(current);
1191
1192 if ((error = create_popped_tree(current, popped, &component)) < 0)
1193 goto cleanup;
1194 }
1195
1196 /* Now that we've created the trees we popped from the stack, let's go back down */
1197 path = &update->path[common_prefix];
1198 while (next_component(&component, path)) {
1199 tree_stack_entry *last, *new_entry;
1200 const git_tree_entry *entry;
1201
1202 last = git_array_last(stack);
1203 entry = last->tree ? git_tree_entry_byname(last->tree, component.ptr) : NULL;
1204 if (!entry)
1205 entry = treebuilder_get(last->bld, component.ptr);
1206
1207 if (entry && git_tree_entry_type(entry) != GIT_OBJECT_TREE) {
1208 git_error_set(GIT_ERROR_TREE, "D/F conflict when updating tree");
1209 error = -1;
1210 goto cleanup;
1211 }
1212
1213 new_entry = git_array_alloc(stack);
1214 GIT_ERROR_CHECK_ALLOC(new_entry);
1215 memset(new_entry, 0, sizeof(*new_entry));
1216
1217 new_entry->tree = NULL;
1218 if (entry && (error = git_tree_lookup(&new_entry->tree, repo, git_tree_entry_id(entry))) < 0)
1219 goto cleanup;
1220
1221 if ((error = git_treebuilder_new(&new_entry->bld, repo, new_entry->tree)) < 0)
1222 goto cleanup;
1223
1224 new_entry->name = git__strdup(component.ptr);
1225 GIT_ERROR_CHECK_ALLOC(new_entry->name);
1226
1227 /* Get to the start of the next component */
1228 path += component.size + 1;
1229 }
1230
1231 /* After all that, we're finally at the place where we want to perform the update */
1232 switch (update->action) {
1233 case GIT_TREE_UPDATE_UPSERT:
1234 {
1235 /* Make sure we're replacing something of the same type */
1236 tree_stack_entry *last = git_array_last(stack);
1237 char *basename = git_path_basename(update->path);
1238 const git_tree_entry *e = git_treebuilder_get(last->bld, basename);
1239 if (e && git_tree_entry_type(e) != git_object__type_from_filemode(update->filemode)) {
1240 git__free(basename);
1241 git_error_set(GIT_ERROR_TREE, "cannot replace '%s' with '%s' at '%s'",
1242 git_object_type2string(git_tree_entry_type(e)),
1243 git_object_type2string(git_object__type_from_filemode(update->filemode)),
1244 update->path);
1245 error = -1;
1246 goto cleanup;
1247 }
1248
1249 error = git_treebuilder_insert(NULL, last->bld, basename, &update->id, update->filemode);
1250 git__free(basename);
1251 break;
1252 }
1253 case GIT_TREE_UPDATE_REMOVE:
1254 {
1255 char *basename = git_path_basename(update->path);
1256 error = git_treebuilder_remove(git_array_last(stack)->bld, basename);
1257 git__free(basename);
1258 break;
1259 }
1260 default:
1261 git_error_set(GIT_ERROR_TREE, "unknown action for update");
1262 error = -1;
1263 goto cleanup;
1264 }
1265
1266 if (error < 0)
1267 goto cleanup;
1268 }
1269
1270 /* We're done, go up the stack again and write out the tree */
1271 {
1272 tree_stack_entry *current = NULL, *popped = NULL;
1273 while ((popped = git_array_pop(stack)) != NULL) {
1274 current = git_array_last(stack);
1275 /* We've reached the top, current is the root tree */
1276 if (!current)
1277 break;
1278
1279 if ((error = create_popped_tree(current, popped, &component)) < 0)
1280 goto cleanup;
1281 }
1282
1283 /* Write out the root tree */
1284 git__free(popped->name);
1285 git_tree_free(popped->tree);
1286
1287 error = git_treebuilder_write(out, popped->bld);
1288 git_treebuilder_free(popped->bld);
1289 if (error < 0)
1290 goto cleanup;
1291 }
1292
1293 cleanup:
1294 {
1295 tree_stack_entry *e;
1296 while ((e = git_array_pop(stack)) != NULL) {
1297 git_treebuilder_free(e->bld);
1298 git_tree_free(e->tree);
1299 git__free(e->name);
1300 }
1301 }
1302
1303 git_buf_dispose(&component);
1304 git_array_clear(stack);
1305 git_vector_free(&entries);
1306 return error;
1307 }
1308