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 "futils.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 GIT_ASSERT_ARG(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 GIT_ASSERT_ARG_WITH_RETVAL(entry, NULL);
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 GIT_ASSERT_ARG_WITH_RETVAL(entry, NULL);
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 GIT_ASSERT_ARG_WITH_RETVAL(entry, GIT_OBJECT_INVALID);
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 GIT_ASSERT_ARG(entry);
292 GIT_ASSERT_ARG(object_out);
293
294 return git_object_lookup(object_out, repo, entry->oid, GIT_OBJECT_ANY);
295 }
296
entry_fromname(const git_tree * tree,const char * name,size_t name_len)297 static const git_tree_entry *entry_fromname(
298 const git_tree *tree, const char *name, size_t name_len)
299 {
300 size_t idx;
301
302 if (tree_key_search(&idx, tree, name, name_len) < 0)
303 return NULL;
304
305 return git_array_get(tree->entries, idx);
306 }
307
git_tree_entry_byname(const git_tree * tree,const char * filename)308 const git_tree_entry *git_tree_entry_byname(
309 const git_tree *tree, const char *filename)
310 {
311 GIT_ASSERT_ARG_WITH_RETVAL(tree, NULL);
312 GIT_ASSERT_ARG_WITH_RETVAL(filename, NULL);
313
314 return entry_fromname(tree, filename, strlen(filename));
315 }
316
git_tree_entry_byindex(const git_tree * tree,size_t idx)317 const git_tree_entry *git_tree_entry_byindex(
318 const git_tree *tree, size_t idx)
319 {
320 GIT_ASSERT_ARG_WITH_RETVAL(tree, NULL);
321 return git_array_get(tree->entries, idx);
322 }
323
git_tree_entry_byid(const git_tree * tree,const git_oid * id)324 const git_tree_entry *git_tree_entry_byid(
325 const git_tree *tree, const git_oid *id)
326 {
327 size_t i;
328 const git_tree_entry *e;
329
330 GIT_ASSERT_ARG_WITH_RETVAL(tree, NULL);
331
332 git_array_foreach(tree->entries, i, e) {
333 if (memcmp(&e->oid->id, &id->id, sizeof(id->id)) == 0)
334 return e;
335 }
336
337 return NULL;
338 }
339
git_tree_entrycount(const git_tree * tree)340 size_t git_tree_entrycount(const git_tree *tree)
341 {
342 GIT_ASSERT_ARG_WITH_RETVAL(tree, 0);
343 return tree->entries.size;
344 }
345
git_treebuilder_entrycount(git_treebuilder * bld)346 size_t git_treebuilder_entrycount(git_treebuilder *bld)
347 {
348 GIT_ASSERT_ARG_WITH_RETVAL(bld, 0);
349
350 return git_strmap_size(bld->map);
351 }
352
tree_error(const char * str,const char * path)353 static int tree_error(const char *str, const char *path)
354 {
355 if (path)
356 git_error_set(GIT_ERROR_TREE, "%s - %s", str, path);
357 else
358 git_error_set(GIT_ERROR_TREE, "%s", str);
359 return -1;
360 }
361
parse_mode(uint16_t * mode_out,const char * buffer,size_t buffer_len,const char ** buffer_out)362 static int parse_mode(uint16_t *mode_out, const char *buffer, size_t buffer_len, const char **buffer_out)
363 {
364 int32_t mode;
365 int error;
366
367 if (!buffer_len || git__isspace(*buffer))
368 return -1;
369
370 if ((error = git__strntol32(&mode, buffer, buffer_len, buffer_out, 8)) < 0)
371 return error;
372
373 if (mode < 0 || mode > UINT16_MAX)
374 return -1;
375
376 *mode_out = mode;
377
378 return 0;
379 }
380
git_tree__parse_raw(void * _tree,const char * data,size_t size)381 int git_tree__parse_raw(void *_tree, const char *data, size_t size)
382 {
383 git_tree *tree = _tree;
384 const char *buffer;
385 const char *buffer_end;
386
387 buffer = data;
388 buffer_end = buffer + size;
389
390 tree->odb_obj = NULL;
391 git_array_init_to_size(tree->entries, DEFAULT_TREE_SIZE);
392 GIT_ERROR_CHECK_ARRAY(tree->entries);
393
394 while (buffer < buffer_end) {
395 git_tree_entry *entry;
396 size_t filename_len;
397 const char *nul;
398 uint16_t attr;
399
400 if (parse_mode(&attr, buffer, buffer_end - buffer, &buffer) < 0 || !buffer)
401 return tree_error("failed to parse tree: can't parse filemode", NULL);
402
403 if (buffer >= buffer_end || (*buffer++) != ' ')
404 return tree_error("failed to parse tree: missing space after filemode", NULL);
405
406 if ((nul = memchr(buffer, 0, buffer_end - buffer)) == NULL)
407 return tree_error("failed to parse tree: object is corrupted", NULL);
408
409 if ((filename_len = nul - buffer) == 0 || filename_len > UINT16_MAX)
410 return tree_error("failed to parse tree: can't parse filename", NULL);
411
412 if ((buffer_end - (nul + 1)) < GIT_OID_RAWSZ)
413 return tree_error("failed to parse tree: can't parse OID", NULL);
414
415 /* Allocate the entry */
416 {
417 entry = git_array_alloc(tree->entries);
418 GIT_ERROR_CHECK_ALLOC(entry);
419
420 entry->attr = attr;
421 entry->filename_len = (uint16_t)filename_len;
422 entry->filename = buffer;
423 entry->oid = (git_oid *) ((char *) buffer + filename_len + 1);
424 }
425
426 buffer += filename_len + 1;
427 buffer += GIT_OID_RAWSZ;
428 }
429
430 return 0;
431 }
432
git_tree__parse(void * _tree,git_odb_object * odb_obj)433 int git_tree__parse(void *_tree, git_odb_object *odb_obj)
434 {
435 git_tree *tree = _tree;
436
437 if ((git_tree__parse_raw(tree,
438 git_odb_object_data(odb_obj),
439 git_odb_object_size(odb_obj))) < 0)
440 return -1;
441
442 if (git_odb_object_dup(&tree->odb_obj, odb_obj) < 0)
443 return -1;
444
445 return 0;
446 }
447
find_next_dir(const char * dirname,git_index * index,size_t start)448 static size_t find_next_dir(const char *dirname, git_index *index, size_t start)
449 {
450 size_t dirlen, i, entries = git_index_entrycount(index);
451
452 dirlen = strlen(dirname);
453 for (i = start; i < entries; ++i) {
454 const git_index_entry *entry = git_index_get_byindex(index, i);
455 if (strlen(entry->path) < dirlen ||
456 memcmp(entry->path, dirname, dirlen) ||
457 (dirlen > 0 && entry->path[dirlen] != '/')) {
458 break;
459 }
460 }
461
462 return i;
463 }
464
otype_from_mode(git_filemode_t filemode)465 static git_object_t otype_from_mode(git_filemode_t filemode)
466 {
467 switch (filemode) {
468 case GIT_FILEMODE_TREE:
469 return GIT_OBJECT_TREE;
470 case GIT_FILEMODE_COMMIT:
471 return GIT_OBJECT_COMMIT;
472 default:
473 return GIT_OBJECT_BLOB;
474 }
475 }
476
check_entry(git_repository * repo,const char * filename,const git_oid * id,git_filemode_t filemode)477 static int check_entry(git_repository *repo, const char *filename, const git_oid *id, git_filemode_t filemode)
478 {
479 if (!valid_filemode(filemode))
480 return tree_error("failed to insert entry: invalid filemode for file", filename);
481
482 if (!valid_entry_name(repo, filename))
483 return tree_error("failed to insert entry: invalid name for a tree entry", filename);
484
485 if (git_oid_is_zero(id))
486 return tree_error("failed to insert entry: invalid null OID", filename);
487
488 if (filemode != GIT_FILEMODE_COMMIT &&
489 !git_object__is_valid(repo, id, otype_from_mode(filemode)))
490 return tree_error("failed to insert entry: invalid object specified", filename);
491
492 return 0;
493 }
494
append_entry(git_treebuilder * bld,const char * filename,const git_oid * id,git_filemode_t filemode,bool validate)495 static int append_entry(
496 git_treebuilder *bld,
497 const char *filename,
498 const git_oid *id,
499 git_filemode_t filemode,
500 bool validate)
501 {
502 git_tree_entry *entry;
503 int error = 0;
504
505 if (validate && ((error = check_entry(bld->repo, filename, id, filemode)) < 0))
506 return error;
507
508 entry = alloc_entry(filename, strlen(filename), id);
509 GIT_ERROR_CHECK_ALLOC(entry);
510
511 entry->attr = (uint16_t)filemode;
512
513 if ((error = git_strmap_set(bld->map, entry->filename, entry)) < 0) {
514 git_tree_entry_free(entry);
515 git_error_set(GIT_ERROR_TREE, "failed to append entry %s to the tree builder", filename);
516 return -1;
517 }
518
519 return 0;
520 }
521
write_tree(git_oid * oid,git_repository * repo,git_index * index,const char * dirname,size_t start,git_buf * shared_buf)522 static int write_tree(
523 git_oid *oid,
524 git_repository *repo,
525 git_index *index,
526 const char *dirname,
527 size_t start,
528 git_buf *shared_buf)
529 {
530 git_treebuilder *bld = NULL;
531 size_t i, entries = git_index_entrycount(index);
532 int error;
533 size_t dirname_len = strlen(dirname);
534 const git_tree_cache *cache;
535
536 cache = git_tree_cache_get(index->tree, dirname);
537 if (cache != NULL && cache->entry_count >= 0){
538 git_oid_cpy(oid, &cache->oid);
539 return (int)find_next_dir(dirname, index, start);
540 }
541
542 if ((error = git_treebuilder_new(&bld, repo, NULL)) < 0 || bld == NULL)
543 return -1;
544
545 /*
546 * This loop is unfortunate, but necessary. The index doesn't have
547 * any directores, so we need to handle that manually, and we
548 * need to keep track of the current position.
549 */
550 for (i = start; i < entries; ++i) {
551 const git_index_entry *entry = git_index_get_byindex(index, i);
552 const char *filename, *next_slash;
553
554 /*
555 * If we've left our (sub)tree, exit the loop and return. The
556 * first check is an early out (and security for the
557 * third). The second check is a simple prefix comparison. The
558 * third check catches situations where there is a directory
559 * win32/sys and a file win32mmap.c. Without it, the following
560 * code believes there is a file win32/mmap.c
561 */
562 if (strlen(entry->path) < dirname_len ||
563 memcmp(entry->path, dirname, dirname_len) ||
564 (dirname_len > 0 && entry->path[dirname_len] != '/')) {
565 break;
566 }
567
568 filename = entry->path + dirname_len;
569 if (*filename == '/')
570 filename++;
571 next_slash = strchr(filename, '/');
572 if (next_slash) {
573 git_oid sub_oid;
574 int written;
575 char *subdir, *last_comp;
576
577 subdir = git__strndup(entry->path, next_slash - entry->path);
578 GIT_ERROR_CHECK_ALLOC(subdir);
579
580 /* Write out the subtree */
581 written = write_tree(&sub_oid, repo, index, subdir, i, shared_buf);
582 if (written < 0) {
583 git__free(subdir);
584 goto on_error;
585 } else {
586 i = written - 1; /* -1 because of the loop increment */
587 }
588
589 /*
590 * We need to figure out what we want toinsert
591 * into this tree. If we're traversing
592 * deps/zlib/, then we only want to write
593 * 'zlib' into the tree.
594 */
595 last_comp = strrchr(subdir, '/');
596 if (last_comp) {
597 last_comp++; /* Get rid of the '/' */
598 } else {
599 last_comp = subdir;
600 }
601
602 error = append_entry(bld, last_comp, &sub_oid, S_IFDIR, true);
603 git__free(subdir);
604 if (error < 0)
605 goto on_error;
606 } else {
607 error = append_entry(bld, filename, &entry->id, entry->mode, true);
608 if (error < 0)
609 goto on_error;
610 }
611 }
612
613 if (git_treebuilder_write_with_buffer(oid, bld, shared_buf) < 0)
614 goto on_error;
615
616 git_treebuilder_free(bld);
617 return (int)i;
618
619 on_error:
620 git_treebuilder_free(bld);
621 return -1;
622 }
623
git_tree__write_index(git_oid * oid,git_index * index,git_repository * repo)624 int git_tree__write_index(
625 git_oid *oid, git_index *index, git_repository *repo)
626 {
627 int ret;
628 git_tree *tree;
629 git_buf shared_buf = GIT_BUF_INIT;
630 bool old_ignore_case = false;
631
632 GIT_ASSERT_ARG(oid);
633 GIT_ASSERT_ARG(index);
634 GIT_ASSERT_ARG(repo);
635
636 if (git_index_has_conflicts(index)) {
637 git_error_set(GIT_ERROR_INDEX,
638 "cannot create a tree from a not fully merged index.");
639 return GIT_EUNMERGED;
640 }
641
642 if (index->tree != NULL && index->tree->entry_count >= 0) {
643 git_oid_cpy(oid, &index->tree->oid);
644 return 0;
645 }
646
647 /* The tree cache didn't help us; we'll have to write
648 * out a tree. If the index is ignore_case, we must
649 * make it case-sensitive for the duration of the tree-write
650 * operation. */
651
652 if (index->ignore_case) {
653 old_ignore_case = true;
654 git_index__set_ignore_case(index, false);
655 }
656
657 ret = write_tree(oid, repo, index, "", 0, &shared_buf);
658 git_buf_dispose(&shared_buf);
659
660 if (old_ignore_case)
661 git_index__set_ignore_case(index, true);
662
663 index->tree = NULL;
664
665 if (ret < 0)
666 return ret;
667
668 git_pool_clear(&index->tree_pool);
669
670 if ((ret = git_tree_lookup(&tree, repo, oid)) < 0)
671 return ret;
672
673 /* Read the tree cache into the index */
674 ret = git_tree_cache_read_tree(&index->tree, tree, &index->tree_pool);
675 git_tree_free(tree);
676
677 return ret;
678 }
679
git_treebuilder_new(git_treebuilder ** builder_p,git_repository * repo,const git_tree * source)680 int git_treebuilder_new(
681 git_treebuilder **builder_p,
682 git_repository *repo,
683 const git_tree *source)
684 {
685 git_treebuilder *bld;
686 size_t i;
687
688 GIT_ASSERT_ARG(builder_p);
689 GIT_ASSERT_ARG(repo);
690
691 bld = git__calloc(1, sizeof(git_treebuilder));
692 GIT_ERROR_CHECK_ALLOC(bld);
693
694 bld->repo = repo;
695
696 if (git_strmap_new(&bld->map) < 0) {
697 git__free(bld);
698 return -1;
699 }
700
701 if (source != NULL) {
702 git_tree_entry *entry_src;
703
704 git_array_foreach(source->entries, i, entry_src) {
705 if (append_entry(
706 bld, entry_src->filename,
707 entry_src->oid,
708 entry_src->attr,
709 false) < 0)
710 goto on_error;
711 }
712 }
713
714 *builder_p = bld;
715 return 0;
716
717 on_error:
718 git_treebuilder_free(bld);
719 return -1;
720 }
721
git_treebuilder_insert(const git_tree_entry ** entry_out,git_treebuilder * bld,const char * filename,const git_oid * id,git_filemode_t filemode)722 int git_treebuilder_insert(
723 const git_tree_entry **entry_out,
724 git_treebuilder *bld,
725 const char *filename,
726 const git_oid *id,
727 git_filemode_t filemode)
728 {
729 git_tree_entry *entry;
730 int error;
731
732 GIT_ASSERT_ARG(bld);
733 GIT_ASSERT_ARG(id);
734 GIT_ASSERT_ARG(filename);
735
736 if ((error = check_entry(bld->repo, filename, id, filemode)) < 0)
737 return error;
738
739 if ((entry = git_strmap_get(bld->map, filename)) != NULL) {
740 git_oid_cpy((git_oid *) entry->oid, id);
741 } else {
742 entry = alloc_entry(filename, strlen(filename), id);
743 GIT_ERROR_CHECK_ALLOC(entry);
744
745 if ((error = git_strmap_set(bld->map, entry->filename, entry)) < 0) {
746 git_tree_entry_free(entry);
747 git_error_set(GIT_ERROR_TREE, "failed to insert %s", filename);
748 return -1;
749 }
750 }
751
752 entry->attr = filemode;
753
754 if (entry_out)
755 *entry_out = entry;
756
757 return 0;
758 }
759
treebuilder_get(git_treebuilder * bld,const char * filename)760 static git_tree_entry *treebuilder_get(git_treebuilder *bld, const char *filename)
761 {
762 GIT_ASSERT_ARG_WITH_RETVAL(bld, NULL);
763 GIT_ASSERT_ARG_WITH_RETVAL(filename, NULL);
764
765 return git_strmap_get(bld->map, filename);
766 }
767
git_treebuilder_get(git_treebuilder * bld,const char * filename)768 const git_tree_entry *git_treebuilder_get(git_treebuilder *bld, const char *filename)
769 {
770 return treebuilder_get(bld, filename);
771 }
772
git_treebuilder_remove(git_treebuilder * bld,const char * filename)773 int git_treebuilder_remove(git_treebuilder *bld, const char *filename)
774 {
775 git_tree_entry *entry = treebuilder_get(bld, filename);
776
777 if (entry == NULL)
778 return tree_error("failed to remove entry: file isn't in the tree", filename);
779
780 git_strmap_delete(bld->map, filename);
781 git_tree_entry_free(entry);
782
783 return 0;
784 }
785
git_treebuilder_write(git_oid * oid,git_treebuilder * bld)786 int git_treebuilder_write(git_oid *oid, git_treebuilder *bld)
787 {
788 int error;
789 git_buf buffer = GIT_BUF_INIT;
790
791 error = git_treebuilder_write_with_buffer(oid, bld, &buffer);
792
793 git_buf_dispose(&buffer);
794 return error;
795 }
796
git_treebuilder_write_with_buffer(git_oid * oid,git_treebuilder * bld,git_buf * tree)797 int git_treebuilder_write_with_buffer(git_oid *oid, git_treebuilder *bld, git_buf *tree)
798 {
799 int error = 0;
800 size_t i, entrycount;
801 git_odb *odb;
802 git_tree_entry *entry;
803 git_vector entries = GIT_VECTOR_INIT;
804
805 GIT_ASSERT_ARG(bld);
806 GIT_ASSERT_ARG(tree);
807
808 git_buf_clear(tree);
809
810 entrycount = git_strmap_size(bld->map);
811 if ((error = git_vector_init(&entries, entrycount, entry_sort_cmp)) < 0)
812 goto out;
813
814 if (tree->asize == 0 &&
815 (error = git_buf_grow(tree, entrycount * 72)) < 0)
816 goto out;
817
818 git_strmap_foreach_value(bld->map, entry, {
819 if ((error = git_vector_insert(&entries, entry)) < 0)
820 goto out;
821 });
822
823 git_vector_sort(&entries);
824
825 for (i = 0; i < entries.length && !error; ++i) {
826 entry = git_vector_get(&entries, i);
827
828 git_buf_printf(tree, "%o ", entry->attr);
829 git_buf_put(tree, entry->filename, entry->filename_len + 1);
830 git_buf_put(tree, (char *)entry->oid->id, GIT_OID_RAWSZ);
831
832 if (git_buf_oom(tree)) {
833 error = -1;
834 goto out;
835 }
836 }
837
838 if ((error = git_repository_odb__weakptr(&odb, bld->repo)) == 0)
839 error = git_odb_write(oid, odb, tree->ptr, tree->size, GIT_OBJECT_TREE);
840
841 out:
842 git_vector_free(&entries);
843
844 return error;
845 }
846
git_treebuilder_filter(git_treebuilder * bld,git_treebuilder_filter_cb filter,void * payload)847 int git_treebuilder_filter(
848 git_treebuilder *bld,
849 git_treebuilder_filter_cb filter,
850 void *payload)
851 {
852 const char *filename;
853 git_tree_entry *entry;
854
855 GIT_ASSERT_ARG(bld);
856 GIT_ASSERT_ARG(filter);
857
858 git_strmap_foreach(bld->map, filename, entry, {
859 if (filter(entry, payload)) {
860 git_strmap_delete(bld->map, filename);
861 git_tree_entry_free(entry);
862 }
863 });
864
865 return 0;
866 }
867
git_treebuilder_clear(git_treebuilder * bld)868 int git_treebuilder_clear(git_treebuilder *bld)
869 {
870 git_tree_entry *e;
871
872 GIT_ASSERT_ARG(bld);
873
874 git_strmap_foreach_value(bld->map, e, git_tree_entry_free(e));
875 git_strmap_clear(bld->map);
876
877 return 0;
878 }
879
git_treebuilder_free(git_treebuilder * bld)880 void git_treebuilder_free(git_treebuilder *bld)
881 {
882 if (bld == NULL)
883 return;
884
885 git_treebuilder_clear(bld);
886 git_strmap_free(bld->map);
887 git__free(bld);
888 }
889
subpath_len(const char * path)890 static size_t subpath_len(const char *path)
891 {
892 const char *slash_pos = strchr(path, '/');
893 if (slash_pos == NULL)
894 return strlen(path);
895
896 return slash_pos - path;
897 }
898
git_tree_entry_bypath(git_tree_entry ** entry_out,const git_tree * root,const char * path)899 int git_tree_entry_bypath(
900 git_tree_entry **entry_out,
901 const git_tree *root,
902 const char *path)
903 {
904 int error = 0;
905 git_tree *subtree;
906 const git_tree_entry *entry;
907 size_t filename_len;
908
909 /* Find how long is the current path component (i.e.
910 * the filename between two slashes */
911 filename_len = subpath_len(path);
912
913 if (filename_len == 0) {
914 git_error_set(GIT_ERROR_TREE, "invalid tree path given");
915 return GIT_ENOTFOUND;
916 }
917
918 entry = entry_fromname(root, path, filename_len);
919
920 if (entry == NULL) {
921 git_error_set(GIT_ERROR_TREE,
922 "the path '%.*s' does not exist in the given tree", (int) filename_len, path);
923 return GIT_ENOTFOUND;
924 }
925
926 switch (path[filename_len]) {
927 case '/':
928 /* If there are more components in the path...
929 * then this entry *must* be a tree */
930 if (!git_tree_entry__is_tree(entry)) {
931 git_error_set(GIT_ERROR_TREE,
932 "the path '%.*s' exists but is not a tree", (int) filename_len, path);
933 return GIT_ENOTFOUND;
934 }
935
936 /* If there's only a slash left in the path, we
937 * return the current entry; otherwise, we keep
938 * walking down the path */
939 if (path[filename_len + 1] != '\0')
940 break;
941 /* fall through */
942 case '\0':
943 /* If there are no more components in the path, return
944 * this entry */
945 return git_tree_entry_dup(entry_out, entry);
946 }
947
948 if (git_tree_lookup(&subtree, root->object.repo, entry->oid) < 0)
949 return -1;
950
951 error = git_tree_entry_bypath(
952 entry_out,
953 subtree,
954 path + filename_len + 1
955 );
956
957 git_tree_free(subtree);
958 return error;
959 }
960
tree_walk(const git_tree * tree,git_treewalk_cb callback,git_buf * path,void * payload,bool preorder)961 static int tree_walk(
962 const git_tree *tree,
963 git_treewalk_cb callback,
964 git_buf *path,
965 void *payload,
966 bool preorder)
967 {
968 int error = 0;
969 size_t i;
970 const git_tree_entry *entry;
971
972 git_array_foreach(tree->entries, i, entry) {
973 if (preorder) {
974 error = callback(path->ptr, entry, payload);
975 if (error < 0) { /* negative value stops iteration */
976 git_error_set_after_callback_function(error, "git_tree_walk");
977 break;
978 }
979 if (error > 0) { /* positive value skips this entry */
980 error = 0;
981 continue;
982 }
983 }
984
985 if (git_tree_entry__is_tree(entry)) {
986 git_tree *subtree;
987 size_t path_len = git_buf_len(path);
988
989 error = git_tree_lookup(&subtree, tree->object.repo, entry->oid);
990 if (error < 0)
991 break;
992
993 /* append the next entry to the path */
994 git_buf_puts(path, entry->filename);
995 git_buf_putc(path, '/');
996
997 if (git_buf_oom(path))
998 error = -1;
999 else
1000 error = tree_walk(subtree, callback, path, payload, preorder);
1001
1002 git_tree_free(subtree);
1003 if (error != 0)
1004 break;
1005
1006 git_buf_truncate(path, path_len);
1007 }
1008
1009 if (!preorder) {
1010 error = callback(path->ptr, entry, payload);
1011 if (error < 0) { /* negative value stops iteration */
1012 git_error_set_after_callback_function(error, "git_tree_walk");
1013 break;
1014 }
1015 error = 0;
1016 }
1017 }
1018
1019 return error;
1020 }
1021
git_tree_walk(const git_tree * tree,git_treewalk_mode mode,git_treewalk_cb callback,void * payload)1022 int git_tree_walk(
1023 const git_tree *tree,
1024 git_treewalk_mode mode,
1025 git_treewalk_cb callback,
1026 void *payload)
1027 {
1028 int error = 0;
1029 git_buf root_path = GIT_BUF_INIT;
1030
1031 if (mode != GIT_TREEWALK_POST && mode != GIT_TREEWALK_PRE) {
1032 git_error_set(GIT_ERROR_INVALID, "invalid walking mode for tree walk");
1033 return -1;
1034 }
1035
1036 error = tree_walk(
1037 tree, callback, &root_path, payload, (mode == GIT_TREEWALK_PRE));
1038
1039 git_buf_dispose(&root_path);
1040
1041 return error;
1042 }
1043
compare_entries(const void * _a,const void * _b)1044 static int compare_entries(const void *_a, const void *_b)
1045 {
1046 const git_tree_update *a = (git_tree_update *) _a;
1047 const git_tree_update *b = (git_tree_update *) _b;
1048
1049 return strcmp(a->path, b->path);
1050 }
1051
on_dup_entry(void ** old,void * new)1052 static int on_dup_entry(void **old, void *new)
1053 {
1054 GIT_UNUSED(old); GIT_UNUSED(new);
1055
1056 git_error_set(GIT_ERROR_TREE, "duplicate entries given for update");
1057 return -1;
1058 }
1059
1060 /*
1061 * We keep the previous tree and the new one at each level of the
1062 * stack. When we leave a level we're done with that tree and we can
1063 * write it out to the odb.
1064 */
1065 typedef struct {
1066 git_treebuilder *bld;
1067 git_tree *tree;
1068 char *name;
1069 } tree_stack_entry;
1070
1071 /** Count how many slashes (i.e. path components) there are in this string */
count_slashes(const char * path)1072 GIT_INLINE(size_t) count_slashes(const char *path)
1073 {
1074 size_t count = 0;
1075 const char *slash;
1076
1077 while ((slash = strchr(path, '/')) != NULL) {
1078 count++;
1079 path = slash + 1;
1080 }
1081
1082 return count;
1083 }
1084
next_component(git_buf * out,const char * in)1085 static bool next_component(git_buf *out, const char *in)
1086 {
1087 const char *slash = strchr(in, '/');
1088
1089 git_buf_clear(out);
1090
1091 if (slash)
1092 git_buf_put(out, in, slash - in);
1093
1094 return !!slash;
1095 }
1096
create_popped_tree(tree_stack_entry * current,tree_stack_entry * popped,git_buf * component)1097 static int create_popped_tree(tree_stack_entry *current, tree_stack_entry *popped, git_buf *component)
1098 {
1099 int error;
1100 git_oid new_tree;
1101
1102 git_tree_free(popped->tree);
1103
1104 /* If the tree would be empty, remove it from the one higher up */
1105 if (git_treebuilder_entrycount(popped->bld) == 0) {
1106 git_treebuilder_free(popped->bld);
1107 error = git_treebuilder_remove(current->bld, popped->name);
1108 git__free(popped->name);
1109 return error;
1110 }
1111
1112 error = git_treebuilder_write(&new_tree, popped->bld);
1113 git_treebuilder_free(popped->bld);
1114
1115 if (error < 0) {
1116 git__free(popped->name);
1117 return error;
1118 }
1119
1120 /* We've written out the tree, now we have to put the new value into its parent */
1121 git_buf_clear(component);
1122 git_buf_puts(component, popped->name);
1123 git__free(popped->name);
1124
1125 GIT_ERROR_CHECK_ALLOC(component->ptr);
1126
1127 /* Error out if this would create a D/F conflict in this update */
1128 if (current->tree) {
1129 const git_tree_entry *to_replace;
1130 to_replace = git_tree_entry_byname(current->tree, component->ptr);
1131 if (to_replace && git_tree_entry_type(to_replace) != GIT_OBJECT_TREE) {
1132 git_error_set(GIT_ERROR_TREE, "D/F conflict when updating tree");
1133 return -1;
1134 }
1135 }
1136
1137 return git_treebuilder_insert(NULL, current->bld, component->ptr, &new_tree, GIT_FILEMODE_TREE);
1138 }
1139
git_tree_create_updated(git_oid * out,git_repository * repo,git_tree * baseline,size_t nupdates,const git_tree_update * updates)1140 int git_tree_create_updated(git_oid *out, git_repository *repo, git_tree *baseline, size_t nupdates, const git_tree_update *updates)
1141 {
1142 git_array_t(tree_stack_entry) stack = GIT_ARRAY_INIT;
1143 tree_stack_entry *root_elem;
1144 git_vector entries;
1145 int error;
1146 size_t i;
1147 git_buf component = GIT_BUF_INIT;
1148
1149 if ((error = git_vector_init(&entries, nupdates, compare_entries)) < 0)
1150 return error;
1151
1152 /* Sort the entries for treversal */
1153 for (i = 0 ; i < nupdates; i++) {
1154 if ((error = git_vector_insert_sorted(&entries, (void *) &updates[i], on_dup_entry)) < 0)
1155 goto cleanup;
1156 }
1157
1158 root_elem = git_array_alloc(stack);
1159 GIT_ERROR_CHECK_ALLOC(root_elem);
1160 memset(root_elem, 0, sizeof(*root_elem));
1161
1162 if (baseline && (error = git_tree_dup(&root_elem->tree, baseline)) < 0)
1163 goto cleanup;
1164
1165 if ((error = git_treebuilder_new(&root_elem->bld, repo, root_elem->tree)) < 0)
1166 goto cleanup;
1167
1168 for (i = 0; i < nupdates; i++) {
1169 const git_tree_update *last_update = i == 0 ? NULL : git_vector_get(&entries, i-1);
1170 const git_tree_update *update = git_vector_get(&entries, i);
1171 size_t common_prefix = 0, steps_up, j;
1172 const char *path;
1173
1174 /* Figure out how much we need to change from the previous tree */
1175 if (last_update)
1176 common_prefix = git_path_common_dirlen(last_update->path, update->path);
1177
1178 /*
1179 * The entries are sorted, so when we find we're no
1180 * longer in the same directory, we need to abandon
1181 * the old tree (steps up) and dive down to the next
1182 * one.
1183 */
1184 steps_up = last_update == NULL ? 0 : count_slashes(&last_update->path[common_prefix]);
1185
1186 for (j = 0; j < steps_up; j++) {
1187 tree_stack_entry *current, *popped = git_array_pop(stack);
1188 GIT_ASSERT(popped);
1189
1190 current = git_array_last(stack);
1191 GIT_ASSERT(current);
1192
1193 if ((error = create_popped_tree(current, popped, &component)) < 0)
1194 goto cleanup;
1195 }
1196
1197 /* Now that we've created the trees we popped from the stack, let's go back down */
1198 path = &update->path[common_prefix];
1199 while (next_component(&component, path)) {
1200 tree_stack_entry *last, *new_entry;
1201 const git_tree_entry *entry;
1202
1203 last = git_array_last(stack);
1204 entry = last->tree ? git_tree_entry_byname(last->tree, component.ptr) : NULL;
1205 if (!entry)
1206 entry = treebuilder_get(last->bld, component.ptr);
1207
1208 if (entry && git_tree_entry_type(entry) != GIT_OBJECT_TREE) {
1209 git_error_set(GIT_ERROR_TREE, "D/F conflict when updating tree");
1210 error = -1;
1211 goto cleanup;
1212 }
1213
1214 new_entry = git_array_alloc(stack);
1215 GIT_ERROR_CHECK_ALLOC(new_entry);
1216 memset(new_entry, 0, sizeof(*new_entry));
1217
1218 new_entry->tree = NULL;
1219 if (entry && (error = git_tree_lookup(&new_entry->tree, repo, git_tree_entry_id(entry))) < 0)
1220 goto cleanup;
1221
1222 if ((error = git_treebuilder_new(&new_entry->bld, repo, new_entry->tree)) < 0)
1223 goto cleanup;
1224
1225 new_entry->name = git__strdup(component.ptr);
1226 GIT_ERROR_CHECK_ALLOC(new_entry->name);
1227
1228 /* Get to the start of the next component */
1229 path += component.size + 1;
1230 }
1231
1232 /* After all that, we're finally at the place where we want to perform the update */
1233 switch (update->action) {
1234 case GIT_TREE_UPDATE_UPSERT:
1235 {
1236 /* Make sure we're replacing something of the same type */
1237 tree_stack_entry *last = git_array_last(stack);
1238 char *basename = git_path_basename(update->path);
1239 const git_tree_entry *e = git_treebuilder_get(last->bld, basename);
1240 if (e && git_tree_entry_type(e) != git_object__type_from_filemode(update->filemode)) {
1241 git__free(basename);
1242 git_error_set(GIT_ERROR_TREE, "cannot replace '%s' with '%s' at '%s'",
1243 git_object_type2string(git_tree_entry_type(e)),
1244 git_object_type2string(git_object__type_from_filemode(update->filemode)),
1245 update->path);
1246 error = -1;
1247 goto cleanup;
1248 }
1249
1250 error = git_treebuilder_insert(NULL, last->bld, basename, &update->id, update->filemode);
1251 git__free(basename);
1252 break;
1253 }
1254 case GIT_TREE_UPDATE_REMOVE:
1255 {
1256 char *basename = git_path_basename(update->path);
1257 error = git_treebuilder_remove(git_array_last(stack)->bld, basename);
1258 git__free(basename);
1259 break;
1260 }
1261 default:
1262 git_error_set(GIT_ERROR_TREE, "unknown action for update");
1263 error = -1;
1264 goto cleanup;
1265 }
1266
1267 if (error < 0)
1268 goto cleanup;
1269 }
1270
1271 /* We're done, go up the stack again and write out the tree */
1272 {
1273 tree_stack_entry *current = NULL, *popped = NULL;
1274 while ((popped = git_array_pop(stack)) != NULL) {
1275 current = git_array_last(stack);
1276 /* We've reached the top, current is the root tree */
1277 if (!current)
1278 break;
1279
1280 if ((error = create_popped_tree(current, popped, &component)) < 0)
1281 goto cleanup;
1282 }
1283
1284 /* Write out the root tree */
1285 git__free(popped->name);
1286 git_tree_free(popped->tree);
1287
1288 error = git_treebuilder_write(out, popped->bld);
1289 git_treebuilder_free(popped->bld);
1290 if (error < 0)
1291 goto cleanup;
1292 }
1293
1294 cleanup:
1295 {
1296 tree_stack_entry *e;
1297 while ((e = git_array_pop(stack)) != NULL) {
1298 git_treebuilder_free(e->bld);
1299 git_tree_free(e->tree);
1300 git__free(e->name);
1301 }
1302 }
1303
1304 git_buf_dispose(&component);
1305 git_array_clear(stack);
1306 git_vector_free(&entries);
1307 return error;
1308 }
1309