2 * Copyright (C) the libgit2 contributors. All rights reserved.
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.
11 #include "git2/repository.h"
12 #include "git2/object.h"
14 #include "tree-cache.h"
18 #define DEFAULT_TREE_SIZE 16
19 #define MAX_FILEMODE_BYTES 6
21 #define TREE_ENTRY_CHECK_NAMELEN(n) \
22 if (n > UINT16_MAX) { git_error_set(GIT_ERROR_INVALID, "tree entry path too long"); }
24 static bool valid_filemode(const int filemode
)
26 return (filemode
== GIT_FILEMODE_TREE
27 || filemode
== GIT_FILEMODE_BLOB
28 || filemode
== GIT_FILEMODE_BLOB_EXECUTABLE
29 || filemode
== GIT_FILEMODE_LINK
30 || filemode
== GIT_FILEMODE_COMMIT
);
33 GIT_INLINE(git_filemode_t
) normalize_filemode(git_filemode_t filemode
)
35 /* Tree bits set, but it's not a commit */
36 if (GIT_MODE_TYPE(filemode
) == GIT_FILEMODE_TREE
)
37 return GIT_FILEMODE_TREE
;
39 /* If any of the x bits are set */
40 if (GIT_PERMS_IS_EXEC(filemode
))
41 return GIT_FILEMODE_BLOB_EXECUTABLE
;
43 /* 16XXXX means commit */
44 if (GIT_MODE_TYPE(filemode
) == GIT_FILEMODE_COMMIT
)
45 return GIT_FILEMODE_COMMIT
;
47 /* 12XXXX means symlink */
48 if (GIT_MODE_TYPE(filemode
) == GIT_FILEMODE_LINK
)
49 return GIT_FILEMODE_LINK
;
51 /* Otherwise, return a blob */
52 return GIT_FILEMODE_BLOB
;
55 static int valid_entry_name(git_repository
*repo
, const char *filename
)
57 return *filename
!= '\0' &&
58 git_path_is_valid(repo
, filename
, 0,
59 GIT_FS_PATH_REJECT_TRAVERSAL
| GIT_PATH_REJECT_DOT_GIT
| GIT_FS_PATH_REJECT_SLASH
);
62 static int entry_sort_cmp(const void *a
, const void *b
)
64 const git_tree_entry
*e1
= (const git_tree_entry
*)a
;
65 const git_tree_entry
*e2
= (const git_tree_entry
*)b
;
67 return git_fs_path_cmp(
68 e1
->filename
, e1
->filename_len
, git_tree_entry__is_tree(e1
),
69 e2
->filename
, e2
->filename_len
, git_tree_entry__is_tree(e2
),
73 int git_tree_entry_cmp(const git_tree_entry
*e1
, const git_tree_entry
*e2
)
75 return entry_sort_cmp(e1
, e2
);
79 * Allocate a new self-contained entry, with enough space after it to
80 * store the filename and the id.
82 static git_tree_entry
*alloc_entry(const char *filename
, size_t filename_len
, const git_oid
*id
)
84 git_tree_entry
*entry
= NULL
;
87 TREE_ENTRY_CHECK_NAMELEN(filename_len
);
89 if (GIT_ADD_SIZET_OVERFLOW(&tree_len
, sizeof(git_tree_entry
), filename_len
) ||
90 GIT_ADD_SIZET_OVERFLOW(&tree_len
, tree_len
, 1) ||
91 GIT_ADD_SIZET_OVERFLOW(&tree_len
, tree_len
, GIT_OID_RAWSZ
))
94 entry
= git__calloc(1, tree_len
);
102 filename_ptr
= ((char *) entry
) + sizeof(git_tree_entry
);
103 memcpy(filename_ptr
, filename
, filename_len
);
104 entry
->filename
= filename_ptr
;
106 id_ptr
= filename_ptr
+ filename_len
+ 1;
107 git_oid_cpy(id_ptr
, id
);
111 entry
->filename_len
= (uint16_t)filename_len
;
116 struct tree_key_search
{
117 const char *filename
;
118 uint16_t filename_len
;
121 static int homing_search_cmp(const void *key
, const void *array_member
)
123 const struct tree_key_search
*ksearch
= key
;
124 const git_tree_entry
*entry
= array_member
;
126 const uint16_t len1
= ksearch
->filename_len
;
127 const uint16_t len2
= entry
->filename_len
;
132 len1
< len2
? len1
: len2
137 * Search for an entry in a given tree.
139 * Note that this search is performed in two steps because
140 * of the way tree entries are sorted internally in git:
142 * Entries in a tree are not sorted alphabetically; two entries
143 * with the same root prefix will have different positions
144 * depending on whether they are folders (subtrees) or normal files.
146 * Consequently, it is not possible to find an entry on the tree
147 * with a binary search if you don't know whether the filename
148 * you're looking for is a folder or a normal file.
150 * To work around this, we first perform a homing binary search
151 * on the tree, using the minimal length root prefix of our filename.
152 * Once the comparisons for this homing search start becoming
153 * ambiguous because of folder vs file sorting, we look linearly
154 * around the area for our target file.
156 static int tree_key_search(
158 const git_tree
*tree
,
159 const char *filename
,
162 struct tree_key_search ksearch
;
163 const git_tree_entry
*entry
;
166 TREE_ENTRY_CHECK_NAMELEN(filename_len
);
168 ksearch
.filename
= filename
;
169 ksearch
.filename_len
= (uint16_t)filename_len
;
171 /* Initial homing search; find an entry on the tree with
172 * the same prefix as the filename we're looking for */
174 if (git_array_search(&homing
,
175 tree
->entries
, &homing_search_cmp
, &ksearch
) < 0)
176 return GIT_ENOTFOUND
; /* just a signal error; not passed back to user */
178 /* We found a common prefix. Look forward as long as
179 * there are entries that share the common prefix */
180 for (i
= homing
; i
< tree
->entries
.size
; ++i
) {
181 entry
= git_array_get(tree
->entries
, i
);
183 if (homing_search_cmp(&ksearch
, entry
) < 0)
186 if (entry
->filename_len
== filename_len
&&
187 memcmp(filename
, entry
->filename
, filename_len
) == 0) {
195 /* If we haven't found our filename yet, look backwards
196 * too as long as we have entries with the same prefix */
201 entry
= git_array_get(tree
->entries
, i
);
203 if (homing_search_cmp(&ksearch
, entry
) > 0)
206 if (entry
->filename_len
== filename_len
&&
207 memcmp(filename
, entry
->filename
, filename_len
) == 0) {
216 /* The filename doesn't exist at all */
217 return GIT_ENOTFOUND
;
220 void git_tree_entry_free(git_tree_entry
*entry
)
228 int git_tree_entry_dup(git_tree_entry
**dest
, const git_tree_entry
*source
)
232 GIT_ASSERT_ARG(source
);
234 cpy
= alloc_entry(source
->filename
, source
->filename_len
, source
->oid
);
238 cpy
->attr
= source
->attr
;
244 void git_tree__free(void *_tree
)
246 git_tree
*tree
= _tree
;
248 git_odb_object_free(tree
->odb_obj
);
249 git_array_clear(tree
->entries
);
253 git_filemode_t
git_tree_entry_filemode(const git_tree_entry
*entry
)
255 return normalize_filemode(entry
->attr
);
258 git_filemode_t
git_tree_entry_filemode_raw(const git_tree_entry
*entry
)
263 const char *git_tree_entry_name(const git_tree_entry
*entry
)
265 GIT_ASSERT_ARG_WITH_RETVAL(entry
, NULL
);
266 return entry
->filename
;
269 const git_oid
*git_tree_entry_id(const git_tree_entry
*entry
)
271 GIT_ASSERT_ARG_WITH_RETVAL(entry
, NULL
);
275 git_object_t
git_tree_entry_type(const git_tree_entry
*entry
)
277 GIT_ASSERT_ARG_WITH_RETVAL(entry
, GIT_OBJECT_INVALID
);
279 if (S_ISGITLINK(entry
->attr
))
280 return GIT_OBJECT_COMMIT
;
281 else if (S_ISDIR(entry
->attr
))
282 return GIT_OBJECT_TREE
;
284 return GIT_OBJECT_BLOB
;
287 int git_tree_entry_to_object(
288 git_object
**object_out
,
289 git_repository
*repo
,
290 const git_tree_entry
*entry
)
292 GIT_ASSERT_ARG(entry
);
293 GIT_ASSERT_ARG(object_out
);
295 return git_object_lookup(object_out
, repo
, entry
->oid
, GIT_OBJECT_ANY
);
298 static const git_tree_entry
*entry_fromname(
299 const git_tree
*tree
, const char *name
, size_t name_len
)
303 if (tree_key_search(&idx
, tree
, name
, name_len
) < 0)
306 return git_array_get(tree
->entries
, idx
);
309 const git_tree_entry
*git_tree_entry_byname(
310 const git_tree
*tree
, const char *filename
)
312 GIT_ASSERT_ARG_WITH_RETVAL(tree
, NULL
);
313 GIT_ASSERT_ARG_WITH_RETVAL(filename
, NULL
);
315 return entry_fromname(tree
, filename
, strlen(filename
));
318 const git_tree_entry
*git_tree_entry_byindex(
319 const git_tree
*tree
, size_t idx
)
321 GIT_ASSERT_ARG_WITH_RETVAL(tree
, NULL
);
322 return git_array_get(tree
->entries
, idx
);
325 const git_tree_entry
*git_tree_entry_byid(
326 const git_tree
*tree
, const git_oid
*id
)
329 const git_tree_entry
*e
;
331 GIT_ASSERT_ARG_WITH_RETVAL(tree
, NULL
);
333 git_array_foreach(tree
->entries
, i
, e
) {
334 if (memcmp(&e
->oid
->id
, &id
->id
, sizeof(id
->id
)) == 0)
341 size_t git_tree_entrycount(const git_tree
*tree
)
343 GIT_ASSERT_ARG_WITH_RETVAL(tree
, 0);
344 return tree
->entries
.size
;
347 size_t git_treebuilder_entrycount(git_treebuilder
*bld
)
349 GIT_ASSERT_ARG_WITH_RETVAL(bld
, 0);
351 return git_strmap_size(bld
->map
);
354 GIT_INLINE(void) set_error(const char *str
, const char *path
)
357 git_error_set(GIT_ERROR_TREE
, "%s - %s", str
, path
);
359 git_error_set(GIT_ERROR_TREE
, "%s", str
);
362 static int tree_error(const char *str
, const char *path
)
364 set_error(str
, path
);
368 static int tree_parse_error(const char *str
, const char *path
)
370 set_error(str
, path
);
374 static int parse_mode(uint16_t *mode_out
, const char *buffer
, size_t buffer_len
, const char **buffer_out
)
379 if (!buffer_len
|| git__isspace(*buffer
))
382 if ((error
= git__strntol32(&mode
, buffer
, buffer_len
, buffer_out
, 8)) < 0)
385 if (mode
< 0 || mode
> UINT16_MAX
)
393 int git_tree__parse_raw(void *_tree
, const char *data
, size_t size
)
395 git_tree
*tree
= _tree
;
397 const char *buffer_end
;
400 buffer_end
= buffer
+ size
;
402 tree
->odb_obj
= NULL
;
403 git_array_init_to_size(tree
->entries
, DEFAULT_TREE_SIZE
);
404 GIT_ERROR_CHECK_ARRAY(tree
->entries
);
406 while (buffer
< buffer_end
) {
407 git_tree_entry
*entry
;
412 if (parse_mode(&attr
, buffer
, buffer_end
- buffer
, &buffer
) < 0 || !buffer
)
413 return tree_parse_error("failed to parse tree: can't parse filemode", NULL
);
415 if (buffer
>= buffer_end
|| (*buffer
++) != ' ')
416 return tree_parse_error("failed to parse tree: missing space after filemode", NULL
);
418 if ((nul
= memchr(buffer
, 0, buffer_end
- buffer
)) == NULL
)
419 return tree_parse_error("failed to parse tree: object is corrupted", NULL
);
421 if ((filename_len
= nul
- buffer
) == 0 || filename_len
> UINT16_MAX
)
422 return tree_parse_error("failed to parse tree: can't parse filename", NULL
);
424 if ((buffer_end
- (nul
+ 1)) < GIT_OID_RAWSZ
)
425 return tree_parse_error("failed to parse tree: can't parse OID", NULL
);
427 /* Allocate the entry */
429 entry
= git_array_alloc(tree
->entries
);
430 GIT_ERROR_CHECK_ALLOC(entry
);
433 entry
->filename_len
= (uint16_t)filename_len
;
434 entry
->filename
= buffer
;
435 entry
->oid
= (git_oid
*) ((char *) buffer
+ filename_len
+ 1);
438 buffer
+= filename_len
+ 1;
439 buffer
+= GIT_OID_RAWSZ
;
445 int git_tree__parse(void *_tree
, git_odb_object
*odb_obj
)
447 git_tree
*tree
= _tree
;
448 const char *data
= git_odb_object_data(odb_obj
);
449 size_t size
= git_odb_object_size(odb_obj
);
452 if ((error
= git_tree__parse_raw(tree
, data
, size
)) < 0 ||
453 (error
= git_odb_object_dup(&tree
->odb_obj
, odb_obj
)) < 0)
459 static size_t find_next_dir(const char *dirname
, git_index
*index
, size_t start
)
461 size_t dirlen
, i
, entries
= git_index_entrycount(index
);
463 dirlen
= strlen(dirname
);
464 for (i
= start
; i
< entries
; ++i
) {
465 const git_index_entry
*entry
= git_index_get_byindex(index
, i
);
466 if (strlen(entry
->path
) < dirlen
||
467 memcmp(entry
->path
, dirname
, dirlen
) ||
468 (dirlen
> 0 && entry
->path
[dirlen
] != '/')) {
476 static git_object_t
otype_from_mode(git_filemode_t filemode
)
479 case GIT_FILEMODE_TREE
:
480 return GIT_OBJECT_TREE
;
481 case GIT_FILEMODE_COMMIT
:
482 return GIT_OBJECT_COMMIT
;
484 return GIT_OBJECT_BLOB
;
488 static int check_entry(git_repository
*repo
, const char *filename
, const git_oid
*id
, git_filemode_t filemode
)
490 if (!valid_filemode(filemode
))
491 return tree_error("failed to insert entry: invalid filemode for file", filename
);
493 if (!valid_entry_name(repo
, filename
))
494 return tree_error("failed to insert entry: invalid name for a tree entry", filename
);
496 if (git_oid_is_zero(id
))
497 return tree_error("failed to insert entry: invalid null OID", filename
);
499 if (filemode
!= GIT_FILEMODE_COMMIT
&&
500 !git_object__is_valid(repo
, id
, otype_from_mode(filemode
)))
501 return tree_error("failed to insert entry: invalid object specified", filename
);
506 static int git_treebuilder__write_with_buffer(
508 git_treebuilder
*bld
,
512 size_t i
, entrycount
;
514 git_tree_entry
*entry
;
515 git_vector entries
= GIT_VECTOR_INIT
;
519 entrycount
= git_strmap_size(bld
->map
);
520 if ((error
= git_vector_init(&entries
, entrycount
, entry_sort_cmp
)) < 0)
523 if (buf
->asize
== 0 &&
524 (error
= git_str_grow(buf
, entrycount
* 72)) < 0)
527 git_strmap_foreach_value(bld
->map
, entry
, {
528 if ((error
= git_vector_insert(&entries
, entry
)) < 0)
532 git_vector_sort(&entries
);
534 for (i
= 0; i
< entries
.length
&& !error
; ++i
) {
535 entry
= git_vector_get(&entries
, i
);
537 git_str_printf(buf
, "%o ", entry
->attr
);
538 git_str_put(buf
, entry
->filename
, entry
->filename_len
+ 1);
539 git_str_put(buf
, (char *)entry
->oid
->id
, GIT_OID_RAWSZ
);
541 if (git_str_oom(buf
)) {
547 if ((error
= git_repository_odb__weakptr(&odb
, bld
->repo
)) == 0)
548 error
= git_odb_write(oid
, odb
, buf
->ptr
, buf
->size
, GIT_OBJECT_TREE
);
551 git_vector_free(&entries
);
556 static int append_entry(
557 git_treebuilder
*bld
,
558 const char *filename
,
560 git_filemode_t filemode
,
563 git_tree_entry
*entry
;
566 if (validate
&& ((error
= check_entry(bld
->repo
, filename
, id
, filemode
)) < 0))
569 entry
= alloc_entry(filename
, strlen(filename
), id
);
570 GIT_ERROR_CHECK_ALLOC(entry
);
572 entry
->attr
= (uint16_t)filemode
;
574 if ((error
= git_strmap_set(bld
->map
, entry
->filename
, entry
)) < 0) {
575 git_tree_entry_free(entry
);
576 git_error_set(GIT_ERROR_TREE
, "failed to append entry %s to the tree builder", filename
);
583 static int write_tree(
585 git_repository
*repo
,
591 git_treebuilder
*bld
= NULL
;
592 size_t i
, entries
= git_index_entrycount(index
);
594 size_t dirname_len
= strlen(dirname
);
595 const git_tree_cache
*cache
;
597 cache
= git_tree_cache_get(index
->tree
, dirname
);
598 if (cache
!= NULL
&& cache
->entry_count
>= 0){
599 git_oid_cpy(oid
, &cache
->oid
);
600 return (int)find_next_dir(dirname
, index
, start
);
603 if ((error
= git_treebuilder_new(&bld
, repo
, NULL
)) < 0 || bld
== NULL
)
607 * This loop is unfortunate, but necessary. The index doesn't have
608 * any directories, so we need to handle that manually, and we
609 * need to keep track of the current position.
611 for (i
= start
; i
< entries
; ++i
) {
612 const git_index_entry
*entry
= git_index_get_byindex(index
, i
);
613 const char *filename
, *next_slash
;
616 * If we've left our (sub)tree, exit the loop and return. The
617 * first check is an early out (and security for the
618 * third). The second check is a simple prefix comparison. The
619 * third check catches situations where there is a directory
620 * win32/sys and a file win32mmap.c. Without it, the following
621 * code believes there is a file win32/mmap.c
623 if (strlen(entry
->path
) < dirname_len
||
624 memcmp(entry
->path
, dirname
, dirname_len
) ||
625 (dirname_len
> 0 && entry
->path
[dirname_len
] != '/')) {
629 filename
= entry
->path
+ dirname_len
;
630 if (*filename
== '/')
632 next_slash
= strchr(filename
, '/');
636 char *subdir
, *last_comp
;
638 subdir
= git__strndup(entry
->path
, next_slash
- entry
->path
);
639 GIT_ERROR_CHECK_ALLOC(subdir
);
641 /* Write out the subtree */
642 written
= write_tree(&sub_oid
, repo
, index
, subdir
, i
, shared_buf
);
647 i
= written
- 1; /* -1 because of the loop increment */
651 * We need to figure out what we want toinsert
652 * into this tree. If we're traversing
653 * deps/zlib/, then we only want to write
654 * 'zlib' into the tree.
656 last_comp
= strrchr(subdir
, '/');
658 last_comp
++; /* Get rid of the '/' */
663 error
= append_entry(bld
, last_comp
, &sub_oid
, S_IFDIR
, true);
668 error
= append_entry(bld
, filename
, &entry
->id
, entry
->mode
, true);
674 if (git_treebuilder__write_with_buffer(oid
, bld
, shared_buf
) < 0)
677 git_treebuilder_free(bld
);
681 git_treebuilder_free(bld
);
685 int git_tree__write_index(
686 git_oid
*oid
, git_index
*index
, git_repository
*repo
)
690 git_str shared_buf
= GIT_STR_INIT
;
691 bool old_ignore_case
= false;
694 GIT_ASSERT_ARG(index
);
695 GIT_ASSERT_ARG(repo
);
697 if (git_index_has_conflicts(index
)) {
698 git_error_set(GIT_ERROR_INDEX
,
699 "cannot create a tree from a not fully merged index.");
700 return GIT_EUNMERGED
;
703 if (index
->tree
!= NULL
&& index
->tree
->entry_count
>= 0) {
704 git_oid_cpy(oid
, &index
->tree
->oid
);
708 /* The tree cache didn't help us; we'll have to write
709 * out a tree. If the index is ignore_case, we must
710 * make it case-sensitive for the duration of the tree-write
713 if (index
->ignore_case
) {
714 old_ignore_case
= true;
715 git_index__set_ignore_case(index
, false);
718 ret
= write_tree(oid
, repo
, index
, "", 0, &shared_buf
);
719 git_str_dispose(&shared_buf
);
722 git_index__set_ignore_case(index
, true);
729 git_pool_clear(&index
->tree_pool
);
731 if ((ret
= git_tree_lookup(&tree
, repo
, oid
)) < 0)
734 /* Read the tree cache into the index */
735 ret
= git_tree_cache_read_tree(&index
->tree
, tree
, &index
->tree_pool
);
741 int git_treebuilder_new(
742 git_treebuilder
**builder_p
,
743 git_repository
*repo
,
744 const git_tree
*source
)
746 git_treebuilder
*bld
;
749 GIT_ASSERT_ARG(builder_p
);
750 GIT_ASSERT_ARG(repo
);
752 bld
= git__calloc(1, sizeof(git_treebuilder
));
753 GIT_ERROR_CHECK_ALLOC(bld
);
757 if (git_strmap_new(&bld
->map
) < 0) {
762 if (source
!= NULL
) {
763 git_tree_entry
*entry_src
;
765 git_array_foreach(source
->entries
, i
, entry_src
) {
767 bld
, entry_src
->filename
,
779 git_treebuilder_free(bld
);
783 int git_treebuilder_insert(
784 const git_tree_entry
**entry_out
,
785 git_treebuilder
*bld
,
786 const char *filename
,
788 git_filemode_t filemode
)
790 git_tree_entry
*entry
;
795 GIT_ASSERT_ARG(filename
);
797 if ((error
= check_entry(bld
->repo
, filename
, id
, filemode
)) < 0)
800 if ((entry
= git_strmap_get(bld
->map
, filename
)) != NULL
) {
801 git_oid_cpy((git_oid
*) entry
->oid
, id
);
803 entry
= alloc_entry(filename
, strlen(filename
), id
);
804 GIT_ERROR_CHECK_ALLOC(entry
);
806 if ((error
= git_strmap_set(bld
->map
, entry
->filename
, entry
)) < 0) {
807 git_tree_entry_free(entry
);
808 git_error_set(GIT_ERROR_TREE
, "failed to insert %s", filename
);
813 entry
->attr
= filemode
;
821 static git_tree_entry
*treebuilder_get(git_treebuilder
*bld
, const char *filename
)
823 GIT_ASSERT_ARG_WITH_RETVAL(bld
, NULL
);
824 GIT_ASSERT_ARG_WITH_RETVAL(filename
, NULL
);
826 return git_strmap_get(bld
->map
, filename
);
829 const git_tree_entry
*git_treebuilder_get(git_treebuilder
*bld
, const char *filename
)
831 return treebuilder_get(bld
, filename
);
834 int git_treebuilder_remove(git_treebuilder
*bld
, const char *filename
)
836 git_tree_entry
*entry
= treebuilder_get(bld
, filename
);
839 return tree_error("failed to remove entry: file isn't in the tree", filename
);
841 git_strmap_delete(bld
->map
, filename
);
842 git_tree_entry_free(entry
);
847 int git_treebuilder_write(git_oid
*oid
, git_treebuilder
*bld
)
852 return git_treebuilder__write_with_buffer(oid
, bld
, &bld
->write_cache
);
855 int git_treebuilder_filter(
856 git_treebuilder
*bld
,
857 git_treebuilder_filter_cb filter
,
860 const char *filename
;
861 git_tree_entry
*entry
;
864 GIT_ASSERT_ARG(filter
);
866 git_strmap_foreach(bld
->map
, filename
, entry
, {
867 if (filter(entry
, payload
)) {
868 git_strmap_delete(bld
->map
, filename
);
869 git_tree_entry_free(entry
);
876 int git_treebuilder_clear(git_treebuilder
*bld
)
882 git_strmap_foreach_value(bld
->map
, e
, git_tree_entry_free(e
));
883 git_strmap_clear(bld
->map
);
888 void git_treebuilder_free(git_treebuilder
*bld
)
893 git_str_dispose(&bld
->write_cache
);
894 git_treebuilder_clear(bld
);
895 git_strmap_free(bld
->map
);
899 static size_t subpath_len(const char *path
)
901 const char *slash_pos
= strchr(path
, '/');
902 if (slash_pos
== NULL
)
905 return slash_pos
- path
;
908 int git_tree_entry_bypath(
909 git_tree_entry
**entry_out
,
910 const git_tree
*root
,
915 const git_tree_entry
*entry
;
918 /* Find how long is the current path component (i.e.
919 * the filename between two slashes */
920 filename_len
= subpath_len(path
);
922 if (filename_len
== 0) {
923 git_error_set(GIT_ERROR_TREE
, "invalid tree path given");
924 return GIT_ENOTFOUND
;
927 entry
= entry_fromname(root
, path
, filename_len
);
930 git_error_set(GIT_ERROR_TREE
,
931 "the path '%.*s' does not exist in the given tree", (int) filename_len
, path
);
932 return GIT_ENOTFOUND
;
935 switch (path
[filename_len
]) {
937 /* If there are more components in the path...
938 * then this entry *must* be a tree */
939 if (!git_tree_entry__is_tree(entry
)) {
940 git_error_set(GIT_ERROR_TREE
,
941 "the path '%.*s' exists but is not a tree", (int) filename_len
, path
);
942 return GIT_ENOTFOUND
;
945 /* If there's only a slash left in the path, we
946 * return the current entry; otherwise, we keep
947 * walking down the path */
948 if (path
[filename_len
+ 1] != '\0')
952 /* If there are no more components in the path, return
954 return git_tree_entry_dup(entry_out
, entry
);
957 if (git_tree_lookup(&subtree
, root
->object
.repo
, entry
->oid
) < 0)
960 error
= git_tree_entry_bypath(
963 path
+ filename_len
+ 1
966 git_tree_free(subtree
);
970 static int tree_walk(
971 const git_tree
*tree
,
972 git_treewalk_cb callback
,
979 const git_tree_entry
*entry
;
981 git_array_foreach(tree
->entries
, i
, entry
) {
983 error
= callback(path
->ptr
, entry
, payload
);
984 if (error
< 0) { /* negative value stops iteration */
985 git_error_set_after_callback_function(error
, "git_tree_walk");
988 if (error
> 0) { /* positive value skips this entry */
994 if (git_tree_entry__is_tree(entry
)) {
996 size_t path_len
= git_str_len(path
);
998 error
= git_tree_lookup(&subtree
, tree
->object
.repo
, entry
->oid
);
1002 /* append the next entry to the path */
1003 git_str_puts(path
, entry
->filename
);
1004 git_str_putc(path
, '/');
1006 if (git_str_oom(path
))
1009 error
= tree_walk(subtree
, callback
, path
, payload
, preorder
);
1011 git_tree_free(subtree
);
1015 git_str_truncate(path
, path_len
);
1019 error
= callback(path
->ptr
, entry
, payload
);
1020 if (error
< 0) { /* negative value stops iteration */
1021 git_error_set_after_callback_function(error
, "git_tree_walk");
1032 const git_tree
*tree
,
1033 git_treewalk_mode mode
,
1034 git_treewalk_cb callback
,
1038 git_str root_path
= GIT_STR_INIT
;
1040 if (mode
!= GIT_TREEWALK_POST
&& mode
!= GIT_TREEWALK_PRE
) {
1041 git_error_set(GIT_ERROR_INVALID
, "invalid walking mode for tree walk");
1046 tree
, callback
, &root_path
, payload
, (mode
== GIT_TREEWALK_PRE
));
1048 git_str_dispose(&root_path
);
1053 static int compare_entries(const void *_a
, const void *_b
)
1055 const git_tree_update
*a
= (git_tree_update
*) _a
;
1056 const git_tree_update
*b
= (git_tree_update
*) _b
;
1058 return strcmp(a
->path
, b
->path
);
1061 static int on_dup_entry(void **old
, void *new)
1063 GIT_UNUSED(old
); GIT_UNUSED(new);
1065 git_error_set(GIT_ERROR_TREE
, "duplicate entries given for update");
1070 * We keep the previous tree and the new one at each level of the
1071 * stack. When we leave a level we're done with that tree and we can
1072 * write it out to the odb.
1075 git_treebuilder
*bld
;
1080 /** Count how many slashes (i.e. path components) there are in this string */
1081 GIT_INLINE(size_t) count_slashes(const char *path
)
1086 while ((slash
= strchr(path
, '/')) != NULL
) {
1094 static bool next_component(git_str
*out
, const char *in
)
1096 const char *slash
= strchr(in
, '/');
1101 git_str_put(out
, in
, slash
- in
);
1106 static int create_popped_tree(tree_stack_entry
*current
, tree_stack_entry
*popped
, git_str
*component
)
1111 git_tree_free(popped
->tree
);
1113 /* If the tree would be empty, remove it from the one higher up */
1114 if (git_treebuilder_entrycount(popped
->bld
) == 0) {
1115 git_treebuilder_free(popped
->bld
);
1116 error
= git_treebuilder_remove(current
->bld
, popped
->name
);
1117 git__free(popped
->name
);
1121 error
= git_treebuilder_write(&new_tree
, popped
->bld
);
1122 git_treebuilder_free(popped
->bld
);
1125 git__free(popped
->name
);
1129 /* We've written out the tree, now we have to put the new value into its parent */
1130 git_str_clear(component
);
1131 git_str_puts(component
, popped
->name
);
1132 git__free(popped
->name
);
1134 GIT_ERROR_CHECK_ALLOC(component
->ptr
);
1136 /* Error out if this would create a D/F conflict in this update */
1137 if (current
->tree
) {
1138 const git_tree_entry
*to_replace
;
1139 to_replace
= git_tree_entry_byname(current
->tree
, component
->ptr
);
1140 if (to_replace
&& git_tree_entry_type(to_replace
) != GIT_OBJECT_TREE
) {
1141 git_error_set(GIT_ERROR_TREE
, "D/F conflict when updating tree");
1146 return git_treebuilder_insert(NULL
, current
->bld
, component
->ptr
, &new_tree
, GIT_FILEMODE_TREE
);
1149 int git_tree_create_updated(git_oid
*out
, git_repository
*repo
, git_tree
*baseline
, size_t nupdates
, const git_tree_update
*updates
)
1151 git_array_t(tree_stack_entry
) stack
= GIT_ARRAY_INIT
;
1152 tree_stack_entry
*root_elem
;
1156 git_str component
= GIT_STR_INIT
;
1158 if ((error
= git_vector_init(&entries
, nupdates
, compare_entries
)) < 0)
1161 /* Sort the entries for treversal */
1162 for (i
= 0 ; i
< nupdates
; i
++) {
1163 if ((error
= git_vector_insert_sorted(&entries
, (void *) &updates
[i
], on_dup_entry
)) < 0)
1167 root_elem
= git_array_alloc(stack
);
1168 GIT_ERROR_CHECK_ALLOC(root_elem
);
1169 memset(root_elem
, 0, sizeof(*root_elem
));
1171 if (baseline
&& (error
= git_tree_dup(&root_elem
->tree
, baseline
)) < 0)
1174 if ((error
= git_treebuilder_new(&root_elem
->bld
, repo
, root_elem
->tree
)) < 0)
1177 for (i
= 0; i
< nupdates
; i
++) {
1178 const git_tree_update
*last_update
= i
== 0 ? NULL
: git_vector_get(&entries
, i
-1);
1179 const git_tree_update
*update
= git_vector_get(&entries
, i
);
1180 size_t common_prefix
= 0, steps_up
, j
;
1183 /* Figure out how much we need to change from the previous tree */
1185 common_prefix
= git_fs_path_common_dirlen(last_update
->path
, update
->path
);
1188 * The entries are sorted, so when we find we're no
1189 * longer in the same directory, we need to abandon
1190 * the old tree (steps up) and dive down to the next
1193 steps_up
= last_update
== NULL
? 0 : count_slashes(&last_update
->path
[common_prefix
]);
1195 for (j
= 0; j
< steps_up
; j
++) {
1196 tree_stack_entry
*current
, *popped
= git_array_pop(stack
);
1199 current
= git_array_last(stack
);
1200 GIT_ASSERT(current
);
1202 if ((error
= create_popped_tree(current
, popped
, &component
)) < 0)
1206 /* Now that we've created the trees we popped from the stack, let's go back down */
1207 path
= &update
->path
[common_prefix
];
1208 while (next_component(&component
, path
)) {
1209 tree_stack_entry
*last
, *new_entry
;
1210 const git_tree_entry
*entry
;
1212 last
= git_array_last(stack
);
1213 entry
= last
->tree
? git_tree_entry_byname(last
->tree
, component
.ptr
) : NULL
;
1215 entry
= treebuilder_get(last
->bld
, component
.ptr
);
1217 if (entry
&& git_tree_entry_type(entry
) != GIT_OBJECT_TREE
) {
1218 git_error_set(GIT_ERROR_TREE
, "D/F conflict when updating tree");
1223 new_entry
= git_array_alloc(stack
);
1224 GIT_ERROR_CHECK_ALLOC(new_entry
);
1225 memset(new_entry
, 0, sizeof(*new_entry
));
1227 new_entry
->tree
= NULL
;
1228 if (entry
&& (error
= git_tree_lookup(&new_entry
->tree
, repo
, git_tree_entry_id(entry
))) < 0)
1231 if ((error
= git_treebuilder_new(&new_entry
->bld
, repo
, new_entry
->tree
)) < 0)
1234 new_entry
->name
= git__strdup(component
.ptr
);
1235 GIT_ERROR_CHECK_ALLOC(new_entry
->name
);
1237 /* Get to the start of the next component */
1238 path
+= component
.size
+ 1;
1241 /* After all that, we're finally at the place where we want to perform the update */
1242 switch (update
->action
) {
1243 case GIT_TREE_UPDATE_UPSERT
:
1245 /* Make sure we're replacing something of the same type */
1246 tree_stack_entry
*last
= git_array_last(stack
);
1247 char *basename
= git_fs_path_basename(update
->path
);
1248 const git_tree_entry
*e
= git_treebuilder_get(last
->bld
, basename
);
1249 if (e
&& git_tree_entry_type(e
) != git_object__type_from_filemode(update
->filemode
)) {
1250 git__free(basename
);
1251 git_error_set(GIT_ERROR_TREE
, "cannot replace '%s' with '%s' at '%s'",
1252 git_object_type2string(git_tree_entry_type(e
)),
1253 git_object_type2string(git_object__type_from_filemode(update
->filemode
)),
1259 error
= git_treebuilder_insert(NULL
, last
->bld
, basename
, &update
->id
, update
->filemode
);
1260 git__free(basename
);
1263 case GIT_TREE_UPDATE_REMOVE
:
1265 tree_stack_entry
*last
= git_array_last(stack
);
1266 char *basename
= git_fs_path_basename(update
->path
);
1267 error
= git_treebuilder_remove(last
->bld
, basename
);
1268 git__free(basename
);
1272 git_error_set(GIT_ERROR_TREE
, "unknown action for update");
1281 /* We're done, go up the stack again and write out the tree */
1283 tree_stack_entry
*current
= NULL
, *popped
= NULL
;
1284 while ((popped
= git_array_pop(stack
)) != NULL
) {
1285 current
= git_array_last(stack
);
1286 /* We've reached the top, current is the root tree */
1290 if ((error
= create_popped_tree(current
, popped
, &component
)) < 0)
1294 /* Write out the root tree */
1295 git__free(popped
->name
);
1296 git_tree_free(popped
->tree
);
1298 error
= git_treebuilder_write(out
, popped
->bld
);
1299 git_treebuilder_free(popped
->bld
);
1306 tree_stack_entry
*e
;
1307 while ((e
= git_array_pop(stack
)) != NULL
) {
1308 git_treebuilder_free(e
->bld
);
1309 git_tree_free(e
->tree
);
1314 git_str_dispose(&component
);
1315 git_array_clear(stack
);
1316 git_vector_free(&entries
);
1320 /* Deprecated Functions */
1322 #ifndef GIT_DEPRECATE_HARD
1324 int git_treebuilder_write_with_buffer(git_oid
*oid
, git_treebuilder
*bld
, git_buf
*buf
)
1328 return git_treebuilder_write(oid
, bld
);