File Coverage

deps/libgit2/src/tree.c
Criterion Covered Total %
statement 366 590 62.0
branch 194 436 44.5
condition n/a
subroutine n/a
pod n/a
total 560 1026 54.5


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