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"
17 #define DEFAULT_TREE_SIZE 16
18 #define MAX_FILEMODE_BYTES 6
20 #define TREE_ENTRY_CHECK_NAMELEN(n) \
21 if (n > UINT16_MAX) { giterr_set(GITERR_INVALID, "tree entry path too long"); }
25 static bool valid_filemode(const int filemode
)
27 return (filemode
== GIT_FILEMODE_TREE
28 || filemode
== GIT_FILEMODE_BLOB
29 || filemode
== GIT_FILEMODE_BLOB_EXECUTABLE
30 || filemode
== GIT_FILEMODE_LINK
31 || filemode
== GIT_FILEMODE_COMMIT
);
34 GIT_INLINE(git_filemode_t
) normalize_filemode(git_filemode_t filemode
)
36 /* Tree bits set, but it's not a commit */
37 if (GIT_MODE_TYPE(filemode
) == GIT_FILEMODE_TREE
)
38 return GIT_FILEMODE_TREE
;
40 /* If any of the x bits are set */
41 if (GIT_PERMS_IS_EXEC(filemode
))
42 return GIT_FILEMODE_BLOB_EXECUTABLE
;
44 /* 16XXXX means commit */
45 if (GIT_MODE_TYPE(filemode
) == GIT_FILEMODE_COMMIT
)
46 return GIT_FILEMODE_COMMIT
;
48 /* 12XXXX means symlink */
49 if (GIT_MODE_TYPE(filemode
) == GIT_FILEMODE_LINK
)
50 return GIT_FILEMODE_LINK
;
52 /* Otherwise, return a blob */
53 return GIT_FILEMODE_BLOB
;
56 static int valid_entry_name(git_repository
*repo
, const char *filename
)
58 return *filename
!= '\0' &&
59 git_path_isvalid(repo
, filename
,
60 GIT_PATH_REJECT_TRAVERSAL
| GIT_PATH_REJECT_DOT_GIT
| GIT_PATH_REJECT_SLASH
);
63 static int entry_sort_cmp(const void *a
, const void *b
)
65 const git_tree_entry
*e1
= (const git_tree_entry
*)a
;
66 const git_tree_entry
*e2
= (const git_tree_entry
*)b
;
69 e1
->filename
, e1
->filename_len
, git_tree_entry__is_tree(e1
),
70 e2
->filename
, e2
->filename_len
, git_tree_entry__is_tree(e2
),
74 int git_tree_entry_cmp(const git_tree_entry
*e1
, const git_tree_entry
*e2
)
76 return entry_sort_cmp(e1
, e2
);
79 int git_tree_entry_icmp(const git_tree_entry
*e1
, const git_tree_entry
*e2
)
82 e1
->filename
, e1
->filename_len
, git_tree_entry__is_tree(e1
),
83 e2
->filename
, e2
->filename_len
, git_tree_entry__is_tree(e2
),
88 * Allocate a new self-contained entry, with enough space after it to
89 * store the filename and the id.
91 static git_tree_entry
*alloc_entry(const char *filename
, size_t filename_len
, const git_oid
*id
)
93 git_tree_entry
*entry
= NULL
;
96 TREE_ENTRY_CHECK_NAMELEN(filename_len
);
98 if (GIT_ADD_SIZET_OVERFLOW(&tree_len
, sizeof(git_tree_entry
), filename_len
) ||
99 GIT_ADD_SIZET_OVERFLOW(&tree_len
, tree_len
, 1) ||
100 GIT_ADD_SIZET_OVERFLOW(&tree_len
, tree_len
, GIT_OID_RAWSZ
))
103 entry
= git__calloc(1, tree_len
);
111 filename_ptr
= ((char *) entry
) + sizeof(git_tree_entry
);
112 memcpy(filename_ptr
, filename
, filename_len
);
113 entry
->filename
= filename_ptr
;
115 id_ptr
= filename_ptr
+ filename_len
+ 1;
116 git_oid_cpy(id_ptr
, id
);
120 entry
->filename_len
= (uint16_t)filename_len
;
125 struct tree_key_search
{
126 const char *filename
;
127 uint16_t filename_len
;
130 static int homing_search_cmp(const void *key
, const void *array_member
)
132 const struct tree_key_search
*ksearch
= key
;
133 const git_tree_entry
*entry
= array_member
;
135 const uint16_t len1
= ksearch
->filename_len
;
136 const uint16_t len2
= entry
->filename_len
;
141 len1
< len2
? len1
: len2
146 * Search for an entry in a given tree.
148 * Note that this search is performed in two steps because
149 * of the way tree entries are sorted internally in git:
151 * Entries in a tree are not sorted alphabetically; two entries
152 * with the same root prefix will have different positions
153 * depending on whether they are folders (subtrees) or normal files.
155 * Consequently, it is not possible to find an entry on the tree
156 * with a binary search if you don't know whether the filename
157 * you're looking for is a folder or a normal file.
159 * To work around this, we first perform a homing binary search
160 * on the tree, using the minimal length root prefix of our filename.
161 * Once the comparisons for this homing search start becoming
162 * ambiguous because of folder vs file sorting, we look linearly
163 * around the area for our target file.
165 static int tree_key_search(
167 const git_tree
*tree
,
168 const char *filename
,
171 struct tree_key_search ksearch
;
172 const git_tree_entry
*entry
;
175 TREE_ENTRY_CHECK_NAMELEN(filename_len
);
177 ksearch
.filename
= filename
;
178 ksearch
.filename_len
= (uint16_t)filename_len
;
180 /* Initial homing search; find an entry on the tree with
181 * the same prefix as the filename we're looking for */
183 if (git_array_search(&homing
,
184 tree
->entries
, &homing_search_cmp
, &ksearch
) < 0)
185 return GIT_ENOTFOUND
; /* just a signal error; not passed back to user */
187 /* We found a common prefix. Look forward as long as
188 * there are entries that share the common prefix */
189 for (i
= homing
; i
< tree
->entries
.size
; ++i
) {
190 entry
= git_array_get(tree
->entries
, i
);
192 if (homing_search_cmp(&ksearch
, entry
) < 0)
195 if (entry
->filename_len
== filename_len
&&
196 memcmp(filename
, entry
->filename
, filename_len
) == 0) {
204 /* If we haven't found our filename yet, look backwards
205 * too as long as we have entries with the same prefix */
210 entry
= git_array_get(tree
->entries
, i
);
212 if (homing_search_cmp(&ksearch
, entry
) > 0)
215 if (entry
->filename_len
== filename_len
&&
216 memcmp(filename
, entry
->filename
, filename_len
) == 0) {
225 /* The filename doesn't exist at all */
226 return GIT_ENOTFOUND
;
229 void git_tree_entry_free(git_tree_entry
*entry
)
237 int git_tree_entry_dup(git_tree_entry
**dest
, const git_tree_entry
*source
)
243 cpy
= alloc_entry(source
->filename
, source
->filename_len
, source
->oid
);
247 cpy
->attr
= source
->attr
;
253 void git_tree__free(void *_tree
)
255 git_tree
*tree
= _tree
;
257 git_odb_object_free(tree
->odb_obj
);
258 git_array_clear(tree
->entries
);
262 git_filemode_t
git_tree_entry_filemode(const git_tree_entry
*entry
)
264 return normalize_filemode(entry
->attr
);
267 git_filemode_t
git_tree_entry_filemode_raw(const git_tree_entry
*entry
)
272 const char *git_tree_entry_name(const git_tree_entry
*entry
)
275 return entry
->filename
;
278 const git_oid
*git_tree_entry_id(const git_tree_entry
*entry
)
284 git_otype
git_tree_entry_type(const git_tree_entry
*entry
)
288 if (S_ISGITLINK(entry
->attr
))
289 return GIT_OBJ_COMMIT
;
290 else if (S_ISDIR(entry
->attr
))
296 int git_tree_entry_to_object(
297 git_object
**object_out
,
298 git_repository
*repo
,
299 const git_tree_entry
*entry
)
301 assert(entry
&& object_out
);
302 return git_object_lookup(object_out
, repo
, entry
->oid
, GIT_OBJ_ANY
);
305 static const git_tree_entry
*entry_fromname(
306 const git_tree
*tree
, const char *name
, size_t name_len
)
310 if (tree_key_search(&idx
, tree
, name
, name_len
) < 0)
313 return git_array_get(tree
->entries
, idx
);
316 const git_tree_entry
*git_tree_entry_byname(
317 const git_tree
*tree
, const char *filename
)
319 assert(tree
&& filename
);
321 return entry_fromname(tree
, filename
, strlen(filename
));
324 const git_tree_entry
*git_tree_entry_byindex(
325 const git_tree
*tree
, size_t idx
)
328 return git_array_get(tree
->entries
, idx
);
331 const git_tree_entry
*git_tree_entry_byid(
332 const git_tree
*tree
, const git_oid
*id
)
335 const git_tree_entry
*e
;
339 git_array_foreach(tree
->entries
, i
, e
) {
340 if (memcmp(&e
->oid
->id
, &id
->id
, sizeof(id
->id
)) == 0)
347 int git_tree__prefix_position(const git_tree
*tree
, const char *path
)
349 struct tree_key_search ksearch
;
350 size_t at_pos
, path_len
;
355 path_len
= strlen(path
);
356 TREE_ENTRY_CHECK_NAMELEN(path_len
);
358 ksearch
.filename
= path
;
359 ksearch
.filename_len
= (uint16_t)path_len
;
361 /* Find tree entry with appropriate prefix */
363 &at_pos
, tree
->entries
, &homing_search_cmp
, &ksearch
);
365 for (; at_pos
< tree
->entries
.size
; ++at_pos
) {
366 const git_tree_entry
*entry
= git_array_get(tree
->entries
, at_pos
);
367 if (homing_search_cmp(&ksearch
, entry
) < 0)
371 for (; at_pos
> 0; --at_pos
) {
372 const git_tree_entry
*entry
=
373 git_array_get(tree
->entries
, at_pos
- 1);
375 if (homing_search_cmp(&ksearch
, entry
) > 0)
382 size_t git_tree_entrycount(const git_tree
*tree
)
385 return tree
->entries
.size
;
388 unsigned int git_treebuilder_entrycount(git_treebuilder
*bld
)
392 return git_strmap_num_entries(bld
->map
);
395 static int tree_error(const char *str
, const char *path
)
398 giterr_set(GITERR_TREE
, "%s - %s", str
, path
);
400 giterr_set(GITERR_TREE
, "%s", str
);
404 static int parse_mode(unsigned int *modep
, const char *buffer
, const char **buffer_out
)
407 unsigned int mode
= 0;
412 while ((c
= *buffer
++) != ' ') {
413 if (c
< '0' || c
> '7')
415 mode
= (mode
<< 3) + (c
- '0');
418 *buffer_out
= buffer
;
423 int git_tree__parse(void *_tree
, git_odb_object
*odb_obj
)
425 git_tree
*tree
= _tree
;
427 const char *buffer_end
;
429 if (git_odb_object_dup(&tree
->odb_obj
, odb_obj
) < 0)
432 buffer
= git_odb_object_data(tree
->odb_obj
);
433 buffer_end
= buffer
+ git_odb_object_size(tree
->odb_obj
);
435 git_array_init_to_size(tree
->entries
, DEFAULT_TREE_SIZE
);
436 GITERR_CHECK_ARRAY(tree
->entries
);
438 while (buffer
< buffer_end
) {
439 git_tree_entry
*entry
;
444 if (parse_mode(&attr
, buffer
, &buffer
) < 0 || !buffer
)
445 return tree_error("Failed to parse tree. Can't parse filemode", NULL
);
447 if ((nul
= memchr(buffer
, 0, buffer_end
- buffer
)) == NULL
)
448 return tree_error("Failed to parse tree. Object is corrupted", NULL
);
450 if ((filename_len
= nul
- buffer
) == 0)
451 return tree_error("Failed to parse tree. Can't parse filename", NULL
);
453 if ((buffer_end
- (nul
+ 1)) < GIT_OID_RAWSZ
)
454 return tree_error("Failed to parse tree. Can't parse OID", NULL
);
456 /* Allocate the entry */
458 entry
= git_array_alloc(tree
->entries
);
459 GITERR_CHECK_ALLOC(entry
);
462 entry
->filename_len
= filename_len
;
463 entry
->filename
= buffer
;
464 entry
->oid
= (git_oid
*) ((char *) buffer
+ filename_len
+ 1);
467 buffer
+= filename_len
+ 1;
468 buffer
+= GIT_OID_RAWSZ
;
474 static size_t find_next_dir(const char *dirname
, git_index
*index
, size_t start
)
476 size_t dirlen
, i
, entries
= git_index_entrycount(index
);
478 dirlen
= strlen(dirname
);
479 for (i
= start
; i
< entries
; ++i
) {
480 const git_index_entry
*entry
= git_index_get_byindex(index
, i
);
481 if (strlen(entry
->path
) < dirlen
||
482 memcmp(entry
->path
, dirname
, dirlen
) ||
483 (dirlen
> 0 && entry
->path
[dirlen
] != '/')) {
491 static int append_entry(
492 git_treebuilder
*bld
,
493 const char *filename
,
495 git_filemode_t filemode
)
497 git_tree_entry
*entry
;
500 if (!valid_entry_name(bld
->repo
, filename
))
501 return tree_error("Failed to insert entry. Invalid name for a tree entry", filename
);
503 entry
= alloc_entry(filename
, strlen(filename
), id
);
504 GITERR_CHECK_ALLOC(entry
);
506 entry
->attr
= (uint16_t)filemode
;
508 git_strmap_insert(bld
->map
, entry
->filename
, entry
, error
);
510 git_tree_entry_free(entry
);
511 giterr_set(GITERR_TREE
, "failed to append entry %s to the tree builder", filename
);
518 static int write_tree(
520 git_repository
*repo
,
525 git_treebuilder
*bld
= NULL
;
526 size_t i
, entries
= git_index_entrycount(index
);
528 size_t dirname_len
= strlen(dirname
);
529 const git_tree_cache
*cache
;
531 cache
= git_tree_cache_get(index
->tree
, dirname
);
532 if (cache
!= NULL
&& cache
->entry_count
>= 0){
533 git_oid_cpy(oid
, &cache
->oid
);
534 return (int)find_next_dir(dirname
, index
, start
);
537 if ((error
= git_treebuilder_new(&bld
, repo
, NULL
)) < 0 || bld
== NULL
)
541 * This loop is unfortunate, but necessary. The index doesn't have
542 * any directores, so we need to handle that manually, and we
543 * need to keep track of the current position.
545 for (i
= start
; i
< entries
; ++i
) {
546 const git_index_entry
*entry
= git_index_get_byindex(index
, i
);
547 const char *filename
, *next_slash
;
550 * If we've left our (sub)tree, exit the loop and return. The
551 * first check is an early out (and security for the
552 * third). The second check is a simple prefix comparison. The
553 * third check catches situations where there is a directory
554 * win32/sys and a file win32mmap.c. Without it, the following
555 * code believes there is a file win32/mmap.c
557 if (strlen(entry
->path
) < dirname_len
||
558 memcmp(entry
->path
, dirname
, dirname_len
) ||
559 (dirname_len
> 0 && entry
->path
[dirname_len
] != '/')) {
563 filename
= entry
->path
+ dirname_len
;
564 if (*filename
== '/')
566 next_slash
= strchr(filename
, '/');
570 char *subdir
, *last_comp
;
572 subdir
= git__strndup(entry
->path
, next_slash
- entry
->path
);
573 GITERR_CHECK_ALLOC(subdir
);
575 /* Write out the subtree */
576 written
= write_tree(&sub_oid
, repo
, index
, subdir
, i
);
581 i
= written
- 1; /* -1 because of the loop increment */
585 * We need to figure out what we want toinsert
586 * into this tree. If we're traversing
587 * deps/zlib/, then we only want to write
588 * 'zlib' into the tree.
590 last_comp
= strrchr(subdir
, '/');
592 last_comp
++; /* Get rid of the '/' */
597 error
= append_entry(bld
, last_comp
, &sub_oid
, S_IFDIR
);
602 error
= append_entry(bld
, filename
, &entry
->id
, entry
->mode
);
608 if (git_treebuilder_write(oid
, bld
) < 0)
611 git_treebuilder_free(bld
);
615 git_treebuilder_free(bld
);
619 int git_tree__write_index(
620 git_oid
*oid
, git_index
*index
, git_repository
*repo
)
624 bool old_ignore_case
= false;
626 assert(oid
&& index
&& repo
);
628 if (git_index_has_conflicts(index
)) {
629 giterr_set(GITERR_INDEX
,
630 "Cannot create a tree from a not fully merged index.");
631 return GIT_EUNMERGED
;
634 if (index
->tree
!= NULL
&& index
->tree
->entry_count
>= 0) {
635 git_oid_cpy(oid
, &index
->tree
->oid
);
639 /* The tree cache didn't help us; we'll have to write
640 * out a tree. If the index is ignore_case, we must
641 * make it case-sensitive for the duration of the tree-write
644 if (index
->ignore_case
) {
645 old_ignore_case
= true;
646 git_index__set_ignore_case(index
, false);
649 ret
= write_tree(oid
, repo
, index
, "", 0);
652 git_index__set_ignore_case(index
, true);
659 git_pool_clear(&index
->tree_pool
);
661 if ((ret
= git_tree_lookup(&tree
, repo
, oid
)) < 0)
664 /* Read the tree cache into the index */
665 ret
= git_tree_cache_read_tree(&index
->tree
, tree
, &index
->tree_pool
);
671 int git_treebuilder_new(
672 git_treebuilder
**builder_p
,
673 git_repository
*repo
,
674 const git_tree
*source
)
676 git_treebuilder
*bld
;
679 assert(builder_p
&& repo
);
681 bld
= git__calloc(1, sizeof(git_treebuilder
));
682 GITERR_CHECK_ALLOC(bld
);
686 if (git_strmap_alloc(&bld
->map
) < 0) {
691 if (source
!= NULL
) {
692 git_tree_entry
*entry_src
;
694 git_array_foreach(source
->entries
, i
, entry_src
) {
696 bld
, entry_src
->filename
,
698 entry_src
->attr
) < 0)
707 git_treebuilder_free(bld
);
711 static git_otype
otype_from_mode(git_filemode_t filemode
)
714 case GIT_FILEMODE_TREE
:
716 case GIT_FILEMODE_COMMIT
:
717 return GIT_OBJ_COMMIT
;
723 int git_treebuilder_insert(
724 const git_tree_entry
**entry_out
,
725 git_treebuilder
*bld
,
726 const char *filename
,
728 git_filemode_t filemode
)
730 git_tree_entry
*entry
;
734 assert(bld
&& id
&& filename
);
736 if (!valid_filemode(filemode
))
737 return tree_error("Failed to insert entry. Invalid filemode for file", filename
);
739 if (!valid_entry_name(bld
->repo
, filename
))
740 return tree_error("Failed to insert entry. Invalid name for a tree entry", filename
);
742 if (filemode
!= GIT_FILEMODE_COMMIT
&&
743 !git_object__is_valid(bld
->repo
, id
, otype_from_mode(filemode
)))
744 return tree_error("Failed to insert entry; invalid object specified", filename
);
746 pos
= git_strmap_lookup_index(bld
->map
, filename
);
747 if (git_strmap_valid_index(bld
->map
, pos
)) {
748 entry
= git_strmap_value_at(bld
->map
, pos
);
749 git_oid_cpy((git_oid
*) entry
->oid
, id
);
751 entry
= alloc_entry(filename
, strlen(filename
), id
);
752 GITERR_CHECK_ALLOC(entry
);
754 git_strmap_insert(bld
->map
, entry
->filename
, entry
, error
);
757 git_tree_entry_free(entry
);
758 giterr_set(GITERR_TREE
, "failed to insert %s", filename
);
763 entry
->attr
= filemode
;
771 static git_tree_entry
*treebuilder_get(git_treebuilder
*bld
, const char *filename
)
773 git_tree_entry
*entry
= NULL
;
776 assert(bld
&& filename
);
778 pos
= git_strmap_lookup_index(bld
->map
, filename
);
779 if (git_strmap_valid_index(bld
->map
, pos
))
780 entry
= git_strmap_value_at(bld
->map
, pos
);
785 const git_tree_entry
*git_treebuilder_get(git_treebuilder
*bld
, const char *filename
)
787 return treebuilder_get(bld
, filename
);
790 int git_treebuilder_remove(git_treebuilder
*bld
, const char *filename
)
792 git_tree_entry
*entry
= treebuilder_get(bld
, filename
);
795 return tree_error("Failed to remove entry. File isn't in the tree", filename
);
797 git_strmap_delete(bld
->map
, filename
);
798 git_tree_entry_free(entry
);
803 int git_treebuilder_write(git_oid
*oid
, git_treebuilder
*bld
)
806 size_t i
, entrycount
;
807 git_buf tree
= GIT_BUF_INIT
;
809 git_tree_entry
*entry
;
814 entrycount
= git_strmap_num_entries(bld
->map
);
815 if (git_vector_init(&entries
, entrycount
, entry_sort_cmp
) < 0)
818 git_strmap_foreach_value(bld
->map
, entry
, {
819 if (git_vector_insert(&entries
, entry
) < 0)
823 git_vector_sort(&entries
);
825 /* Grow the buffer beforehand to an estimated size */
826 error
= git_buf_grow(&tree
, entrycount
* 72);
828 for (i
= 0; i
< entries
.length
&& !error
; ++i
) {
829 git_tree_entry
*entry
= git_vector_get(&entries
, i
);
831 git_buf_printf(&tree
, "%o ", entry
->attr
);
832 git_buf_put(&tree
, entry
->filename
, entry
->filename_len
+ 1);
833 git_buf_put(&tree
, (char *)entry
->oid
->id
, GIT_OID_RAWSZ
);
835 if (git_buf_oom(&tree
))
841 !(error
= git_repository_odb__weakptr(&odb
, bld
->repo
)))
842 error
= git_odb_write(oid
, odb
, tree
.ptr
, tree
.size
, GIT_OBJ_TREE
);
845 git_vector_free(&entries
);
850 void git_treebuilder_filter(
851 git_treebuilder
*bld
,
852 git_treebuilder_filter_cb filter
,
855 const char *filename
;
856 git_tree_entry
*entry
;
858 assert(bld
&& filter
);
860 git_strmap_foreach(bld
->map
, filename
, entry
, {
861 if (filter(entry
, payload
)) {
862 git_strmap_delete(bld
->map
, filename
);
863 git_tree_entry_free(entry
);
868 void git_treebuilder_clear(git_treebuilder
*bld
)
874 git_strmap_foreach_value(bld
->map
, e
, git_tree_entry_free(e
));
875 git_strmap_clear(bld
->map
);
878 void git_treebuilder_free(git_treebuilder
*bld
)
883 git_treebuilder_clear(bld
);
884 git_strmap_free(bld
->map
);
888 static size_t subpath_len(const char *path
)
890 const char *slash_pos
= strchr(path
, '/');
891 if (slash_pos
== NULL
)
894 return slash_pos
- path
;
897 int git_tree_entry_bypath(
898 git_tree_entry
**entry_out
,
899 const git_tree
*root
,
904 const git_tree_entry
*entry
;
907 /* Find how long is the current path component (i.e.
908 * the filename between two slashes */
909 filename_len
= subpath_len(path
);
911 if (filename_len
== 0) {
912 giterr_set(GITERR_TREE
, "Invalid tree path given");
913 return GIT_ENOTFOUND
;
916 entry
= entry_fromname(root
, path
, filename_len
);
919 giterr_set(GITERR_TREE
,
920 "the path '%.*s' does not exist in the given tree", filename_len
, path
);
921 return GIT_ENOTFOUND
;
924 switch (path
[filename_len
]) {
926 /* If there are more components in the path...
927 * then this entry *must* be a tree */
928 if (!git_tree_entry__is_tree(entry
)) {
929 giterr_set(GITERR_TREE
,
930 "the path '%.*s' exists but is not a tree", filename_len
, path
);
931 return GIT_ENOTFOUND
;
934 /* If there's only a slash left in the path, we
935 * return the current entry; otherwise, we keep
936 * walking down the path */
937 if (path
[filename_len
+ 1] != '\0')
941 /* If there are no more components in the path, return
943 return git_tree_entry_dup(entry_out
, entry
);
946 if (git_tree_lookup(&subtree
, root
->object
.repo
, entry
->oid
) < 0)
949 error
= git_tree_entry_bypath(
952 path
+ filename_len
+ 1
955 git_tree_free(subtree
);
959 static int tree_walk(
960 const git_tree
*tree
,
961 git_treewalk_cb callback
,
968 const git_tree_entry
*entry
;
970 git_array_foreach(tree
->entries
, i
, entry
) {
972 error
= callback(path
->ptr
, entry
, payload
);
973 if (error
< 0) { /* negative value stops iteration */
974 giterr_set_after_callback_function(error
, "git_tree_walk");
977 if (error
> 0) { /* positive value skips this entry */
983 if (git_tree_entry__is_tree(entry
)) {
985 size_t path_len
= git_buf_len(path
);
987 error
= git_tree_lookup(&subtree
, tree
->object
.repo
, entry
->oid
);
991 /* append the next entry to the path */
992 git_buf_puts(path
, entry
->filename
);
993 git_buf_putc(path
, '/');
995 if (git_buf_oom(path
))
998 error
= tree_walk(subtree
, callback
, path
, payload
, preorder
);
1000 git_tree_free(subtree
);
1004 git_buf_truncate(path
, path_len
);
1008 error
= callback(path
->ptr
, entry
, payload
);
1009 if (error
< 0) { /* negative value stops iteration */
1010 giterr_set_after_callback_function(error
, "git_tree_walk");
1021 const git_tree
*tree
,
1022 git_treewalk_mode mode
,
1023 git_treewalk_cb callback
,
1027 git_buf root_path
= GIT_BUF_INIT
;
1029 if (mode
!= GIT_TREEWALK_POST
&& mode
!= GIT_TREEWALK_PRE
) {
1030 giterr_set(GITERR_INVALID
, "Invalid walking mode for tree walk");
1035 tree
, callback
, &root_path
, payload
, (mode
== GIT_TREEWALK_PRE
));
1037 git_buf_free(&root_path
);
1042 static int compare_entries(const void *_a
, const void *_b
)
1044 const git_tree_update
*a
= (git_tree_update
*) _a
;
1045 const git_tree_update
*b
= (git_tree_update
*) _b
;
1047 return strcmp(a
->path
, b
->path
);
1050 static int on_dup_entry(void **old
, void *new)
1052 GIT_UNUSED(old
); GIT_UNUSED(new);
1054 giterr_set(GITERR_TREE
, "duplicate entries given for update");
1059 * We keep the previous tree and the new one at each level of the
1060 * stack. When we leave a level we're done with that tree and we can
1061 * write it out to the odb.
1064 git_treebuilder
*bld
;
1069 /** Count how many slashes (i.e. path components) there are in this string */
1070 GIT_INLINE(size_t) count_slashes(const char *path
)
1075 while ((slash
= strchr(path
, '/')) != NULL
) {
1083 static bool next_component(git_buf
*out
, const char *in
)
1085 const char *slash
= strchr(in
, '/');
1090 git_buf_put(out
, in
, slash
- in
);
1095 static int create_popped_tree(tree_stack_entry
*current
, tree_stack_entry
*popped
, git_buf
*component
)
1100 git_tree_free(popped
->tree
);
1102 /* If the tree would be empty, remove it from the one higher up */
1103 if (git_treebuilder_entrycount(popped
->bld
) == 0) {
1104 git_treebuilder_free(popped
->bld
);
1105 error
= git_treebuilder_remove(current
->bld
, popped
->name
);
1106 git__free(popped
->name
);
1110 error
= git_treebuilder_write(&new_tree
, popped
->bld
);
1111 git_treebuilder_free(popped
->bld
);
1114 git__free(popped
->name
);
1118 /* We've written out the tree, now we have to put the new value into its parent */
1119 git_buf_clear(component
);
1120 git_buf_puts(component
, popped
->name
);
1121 git__free(popped
->name
);
1123 GITERR_CHECK_ALLOC(component
->ptr
);
1125 /* Error out if this would create a D/F conflict in this update */
1126 if (current
->tree
) {
1127 const git_tree_entry
*to_replace
;
1128 to_replace
= git_tree_entry_byname(current
->tree
, component
->ptr
);
1129 if (to_replace
&& git_tree_entry_type(to_replace
) != GIT_OBJ_TREE
) {
1130 giterr_set(GITERR_TREE
, "D/F conflict when updating tree");
1135 return git_treebuilder_insert(NULL
, current
->bld
, component
->ptr
, &new_tree
, GIT_FILEMODE_TREE
);
1138 int git_tree_create_updated(git_oid
*out
, git_repository
*repo
, git_tree
*baseline
, size_t nupdates
, const git_tree_update
*updates
)
1140 git_array_t(tree_stack_entry
) stack
= GIT_ARRAY_INIT
;
1141 tree_stack_entry
*root_elem
;
1145 git_buf component
= GIT_BUF_INIT
;
1147 if ((error
= git_vector_init(&entries
, nupdates
, compare_entries
)) < 0)
1150 /* Sort the entries for treversal */
1151 for (i
= 0 ; i
< nupdates
; i
++) {
1152 if ((error
= git_vector_insert_sorted(&entries
, (void *) &updates
[i
], on_dup_entry
)) < 0)
1156 root_elem
= git_array_alloc(stack
);
1157 GITERR_CHECK_ALLOC(root_elem
);
1158 memset(root_elem
, 0, sizeof(*root_elem
));
1160 if (baseline
&& (error
= git_tree_dup(&root_elem
->tree
, baseline
)) < 0)
1163 if ((error
= git_treebuilder_new(&root_elem
->bld
, repo
, root_elem
->tree
)) < 0)
1166 for (i
= 0; i
< nupdates
; i
++) {
1167 const git_tree_update
*last_update
= i
== 0 ? NULL
: &updates
[i
-1];
1168 const git_tree_update
*update
= &updates
[i
];
1169 size_t common_prefix
= 0, steps_up
, j
;
1172 /* Figure out how much we need to change from the previous tree */
1174 common_prefix
= git_path_common_dirlen(last_update
->path
, update
->path
);
1177 * The entries are sorted, so when we find we're no
1178 * longer in the same directory, we need to abandon
1179 * the old tree (steps up) and dive down to the next
1182 steps_up
= last_update
== NULL
? 0 : count_slashes(&last_update
->path
[common_prefix
]);
1184 for (j
= 0; j
< steps_up
; j
++) {
1185 tree_stack_entry
*current
, *popped
= git_array_pop(stack
);
1188 current
= git_array_last(stack
);
1191 if ((error
= create_popped_tree(current
, popped
, &component
)) < 0)
1195 /* Now that we've created the trees we popped from the stack, let's go back down */
1196 path
= &update
->path
[common_prefix
];
1197 while (next_component(&component
, path
)) {
1198 tree_stack_entry
*last
, *new_entry
;
1199 const git_tree_entry
*entry
;
1201 last
= git_array_last(stack
);
1202 entry
= last
->tree
? git_tree_entry_byname(last
->tree
, component
.ptr
) : NULL
;
1203 if (entry
&& git_tree_entry_type(entry
) != GIT_OBJ_TREE
) {
1204 giterr_set(GITERR_TREE
, "D/F conflict when updating tree");
1209 new_entry
= git_array_alloc(stack
);
1210 GITERR_CHECK_ALLOC(new_entry
);
1211 memset(new_entry
, 0, sizeof(*new_entry
));
1213 new_entry
->tree
= NULL
;
1214 if (entry
&& (error
= git_tree_lookup(&new_entry
->tree
, repo
, git_tree_entry_id(entry
))) < 0)
1217 if ((error
= git_treebuilder_new(&new_entry
->bld
, repo
, new_entry
->tree
)) < 0)
1220 new_entry
->name
= git__strdup(component
.ptr
);
1221 GITERR_CHECK_ALLOC(new_entry
->name
);
1223 /* Get to the start of the next component */
1224 path
+= component
.size
+ 1;
1227 /* After all that, we're finally at the place where we want to perform the update */
1228 switch (update
->action
) {
1229 case GIT_TREE_UPDATE_UPSERT
:
1231 /* Make sure we're replacing something of the same type */
1232 tree_stack_entry
*last
= git_array_last(stack
);
1233 char *basename
= git_path_basename(update
->path
);
1234 const git_tree_entry
*e
= git_treebuilder_get(last
->bld
, basename
);
1235 if (e
&& git_tree_entry_type(e
) != git_object__type_from_filemode(update
->filemode
)) {
1236 git__free(basename
);
1237 giterr_set(GITERR_TREE
, "Cannot replace '%s' with '%s' at '%s'",
1238 git_object_type2string(git_tree_entry_type(e
)),
1239 git_object_type2string(git_object__type_from_filemode(update
->filemode
)),
1245 error
= git_treebuilder_insert(NULL
, last
->bld
, basename
, &update
->id
, update
->filemode
);
1246 git__free(basename
);
1249 case GIT_TREE_UPDATE_REMOVE
:
1251 char *basename
= git_path_basename(update
->path
);
1252 error
= git_treebuilder_remove(git_array_last(stack
)->bld
, basename
);
1253 git__free(basename
);
1257 giterr_set(GITERR_TREE
, "unkown action for update");
1266 /* We're done, go up the stack again and write out the tree */
1268 tree_stack_entry
*current
= NULL
, *popped
= NULL
;
1269 while ((popped
= git_array_pop(stack
)) != NULL
) {
1270 current
= git_array_last(stack
);
1271 /* We've reached the top, current is the root tree */
1275 if ((error
= create_popped_tree(current
, popped
, &component
)) < 0)
1279 /* Write out the root tree */
1280 git__free(popped
->name
);
1281 git_tree_free(popped
->tree
);
1283 error
= git_treebuilder_write(out
, popped
->bld
);
1284 git_treebuilder_free(popped
->bld
);
1291 tree_stack_entry
*e
;
1292 while ((e
= git_array_pop(stack
)) != NULL
) {
1293 git_treebuilder_free(e
->bld
);
1294 git_tree_free(e
->tree
);
1299 git_buf_free(&component
);
1300 git_array_clear(stack
);
1301 git_vector_free(&entries
);