]> git.proxmox.com Git - libgit2.git/blame - src/tree.c
Disable ignore_case when writing the index to a tree
[libgit2.git] / src / tree.c
CommitLineData
225fe215 1/*
359fc2d2 2 * Copyright (C) the libgit2 contributors. All rights reserved.
225fe215 3 *
bb742ede
VM
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.
225fe215
VM
6 */
7
8#include "common.h"
9#include "commit.h"
225fe215 10#include "tree.h"
44908fe7
VM
11#include "git2/repository.h"
12#include "git2/object.h"
225fe215 13
c8f5ff8f 14#define DEFAULT_TREE_SIZE 16
9de27ad0 15#define MAX_FILEMODE_BYTES 6
c8f5ff8f 16
a7dbac0b 17static bool valid_filemode(const int filemode)
8e9bfa4c 18{
a7dbac0b 19 return (filemode == GIT_FILEMODE_TREE
20 || filemode == GIT_FILEMODE_BLOB
a7dbac0b 21 || filemode == GIT_FILEMODE_BLOB_EXECUTABLE
22 || filemode == GIT_FILEMODE_LINK
23 || filemode == GIT_FILEMODE_COMMIT);
0ad6efa1
VM
24}
25
f1c75b94
CMN
26GIT_INLINE(git_filemode_t) normalize_filemode(git_filemode_t filemode)
27{
28 /* Tree bits set, but it's not a commit */
29 if (filemode & GIT_FILEMODE_TREE && !(filemode & 0100000))
30 return GIT_FILEMODE_TREE;
31
32 /* If any of the x bits is set */
33 if (filemode & 0111)
34 return GIT_FILEMODE_BLOB_EXECUTABLE;
35
36 /* 16XXXX means commit */
37 if ((filemode & GIT_FILEMODE_COMMIT) == GIT_FILEMODE_COMMIT)
38 return GIT_FILEMODE_COMMIT;
39
40 /* 12XXXX means commit */
41 if ((filemode & GIT_FILEMODE_LINK) == GIT_FILEMODE_LINK)
42 return GIT_FILEMODE_LINK;
43
44 /* Otherwise, return a blob */
45 return GIT_FILEMODE_BLOB;
46}
47
28c1451a
VM
48static int valid_entry_name(const char *filename)
49{
cfeef7ce
RB
50 return *filename != '\0' &&
51 strchr(filename, '/') == NULL &&
52 (*filename != '.' ||
53 (strcmp(filename, ".") != 0 &&
54 strcmp(filename, "..") != 0 &&
55 strcmp(filename, DOT_GIT) != 0));
28c1451a
VM
56}
57
98527b5b 58int git_tree_entry_cmp(const git_tree_entry *e1, const git_tree_entry *e2)
28c1451a 59{
1744fafe 60 return git_path_cmp(
98527b5b
RB
61 e1->filename, e1->filename_len, git_tree_entry__is_tree(e1),
62 e2->filename, e2->filename_len, git_tree_entry__is_tree(e2));
63}
64
65int git_tree_entry_icmp(const git_tree_entry *e1, const git_tree_entry *e2)
66{
67 return git_path_icmp(
68 e1->filename, e1->filename_len, git_tree_entry__is_tree(e1),
69 e2->filename, e2->filename_len, git_tree_entry__is_tree(e2));
70}
71
72static int entry_sort_cmp(const void *a, const void *b)
73{
74 return git_tree_entry_cmp((const git_tree_entry *)a, (const git_tree_entry *)b);
28c1451a
VM
75}
76
0e2fcca8
VM
77static git_tree_entry *alloc_entry(const char *filename)
78{
79 git_tree_entry *entry = NULL;
80 size_t filename_len = strlen(filename);
81
82 entry = git__malloc(sizeof(git_tree_entry) + filename_len + 1);
83 if (!entry)
84 return NULL;
85
86 memset(entry, 0x0, sizeof(git_tree_entry));
87 memcpy(entry->filename, filename, filename_len);
88 entry->filename[filename_len] = 0;
89 entry->filename_len = filename_len;
90
91 return entry;
92}
28c1451a 93
761aa2aa
VM
94struct tree_key_search {
95 const char *filename;
96 size_t filename_len;
97};
98
28c1451a 99static int homing_search_cmp(const void *key, const void *array_member)
2a884588 100{
0cbbdc26
KS
101 const struct tree_key_search *ksearch = key;
102 const git_tree_entry *entry = array_member;
2a884588 103
28c1451a
VM
104 const size_t len1 = ksearch->filename_len;
105 const size_t len2 = entry->filename_len;
e6629d83 106
28c1451a
VM
107 return memcmp(
108 ksearch->filename,
109 entry->filename,
110 len1 < len2 ? len1 : len2
111 );
9de27ad0
SJ
112}
113
28c1451a
VM
114/*
115 * Search for an entry in a given tree.
116 *
117 * Note that this search is performed in two steps because
118 * of the way tree entries are sorted internally in git:
119 *
120 * Entries in a tree are not sorted alphabetically; two entries
121 * with the same root prefix will have different positions
122 * depending on whether they are folders (subtrees) or normal files.
123 *
124 * Consequently, it is not possible to find an entry on the tree
125 * with a binary search if you don't know whether the filename
126 * you're looking for is a folder or a normal file.
127 *
128 * To work around this, we first perform a homing binary search
129 * on the tree, using the minimal length root prefix of our filename.
130 * Once the comparisons for this homing search start becoming
131 * ambiguous because of folder vs file sorting, we look linearly
132 * around the area for our target file.
133 */
16248ee2 134static int tree_key_search(
11d9f6b3 135 size_t *at_pos, git_vector *entries, const char *filename, size_t filename_len)
2a884588 136{
28c1451a
VM
137 struct tree_key_search ksearch;
138 const git_tree_entry *entry;
11d9f6b3 139 size_t homing, i;
2a884588 140
28c1451a 141 ksearch.filename = filename;
0e2fcca8 142 ksearch.filename_len = filename_len;
e6629d83 143
28c1451a
VM
144 /* Initial homing search; find an entry on the tree with
145 * the same prefix as the filename we're looking for */
11d9f6b3
PK
146 if (git_vector_bsearch2(&homing, entries, &homing_search_cmp, &ksearch) < 0)
147 return GIT_ENOTFOUND;
28c1451a
VM
148
149 /* We found a common prefix. Look forward as long as
150 * there are entries that share the common prefix */
11d9f6b3 151 for (i = homing; i < entries->length; ++i) {
28c1451a
VM
152 entry = entries->contents[i];
153
181bbf14 154 if (homing_search_cmp(&ksearch, entry) < 0)
28c1451a
VM
155 break;
156
0e2fcca8 157 if (entry->filename_len == filename_len &&
11d9f6b3
PK
158 memcmp(filename, entry->filename, filename_len) == 0) {
159 if (at_pos)
160 *at_pos = i;
161
162 return 0;
163 }
8cf2de07 164 }
e6629d83 165
28c1451a
VM
166 /* If we haven't found our filename yet, look backwards
167 * too as long as we have entries with the same prefix */
11d9f6b3
PK
168 if (homing > 0) {
169 i = homing - 1;
e6629d83 170
11d9f6b3
PK
171 do {
172 entry = entries->contents[i];
e6629d83 173
11d9f6b3
PK
174 if (homing_search_cmp(&ksearch, entry) > 0)
175 break;
176
177 if (entry->filename_len == filename_len &&
178 memcmp(filename, entry->filename, filename_len) == 0) {
179 if (at_pos)
180 *at_pos = i;
181
182 return 0;
183 }
184 } while (i-- > 0);
28c1451a
VM
185 }
186
187 /* The filename doesn't exist at all */
904b67e6 188 return GIT_ENOTFOUND;
e6629d83
VM
189}
190
0e2fcca8
VM
191void git_tree_entry_free(git_tree_entry *entry)
192{
1c3edb30 193 if (entry == NULL)
194 return;
195
0e2fcca8
VM
196 git__free(entry);
197}
198
46ea40d9 199git_tree_entry *git_tree_entry_dup(const git_tree_entry *entry)
0e2fcca8
VM
200{
201 size_t total_size;
202 git_tree_entry *copy;
203
204 assert(entry);
205
206 total_size = sizeof(git_tree_entry) + entry->filename_len + 1;
207
208 copy = git__malloc(total_size);
209 if (!copy)
210 return NULL;
211
212 memcpy(copy, entry, total_size);
e120123e 213
0e2fcca8
VM
214 return copy;
215}
216
72a3fe42 217void git_tree__free(git_tree *tree)
225fe215 218{
e2237179
RB
219 size_t i;
220 git_tree_entry *e;
003c2690 221
e2237179 222 git_vector_foreach(&tree->entries, i, e)
0e2fcca8 223 git_tree_entry_free(e);
003c2690 224
c8f5ff8f 225 git_vector_free(&tree->entries);
3286c408 226 git__free(tree);
225fe215
VM
227}
228
9950d27a 229const git_oid *git_tree_id(const git_tree *t)
d45b4a9a 230{
9950d27a
RB
231 return git_object_id((const git_object *)t);
232}
233
234git_repository *git_tree_owner(const git_tree *t)
235{
236 return git_object_owner((const git_object *)t);
225fe215
VM
237}
238
9d7ac675 239git_filemode_t git_tree_entry_filemode(const git_tree_entry *entry)
003c2690 240{
9d7ac675 241 return (git_filemode_t)entry->attr;
003c2690
VM
242}
243
0ad6efa1 244const char *git_tree_entry_name(const git_tree_entry *entry)
003c2690 245{
c4b5bedc 246 assert(entry);
2a884588
VM
247 return entry->filename;
248}
003c2690 249
0ad6efa1 250const git_oid *git_tree_entry_id(const git_tree_entry *entry)
2a884588 251{
c4b5bedc 252 assert(entry);
2a884588 253 return &entry->oid;
003c2690
VM
254}
255
ff9a4c13
RG
256git_otype git_tree_entry_type(const git_tree_entry *entry)
257{
258 assert(entry);
259
260 if (S_ISGITLINK(entry->attr))
261 return GIT_OBJ_COMMIT;
262 else if (S_ISDIR(entry->attr))
263 return GIT_OBJ_TREE;
264 else
265 return GIT_OBJ_BLOB;
266}
267
9d0011fd
VM
268int git_tree_entry_to_object(
269 git_object **object_out,
270 git_repository *repo,
271 const git_tree_entry *entry)
003c2690 272{
1795f879 273 assert(entry && object_out);
72a3fe42 274 return git_object_lookup(object_out, repo, &entry->oid, GIT_OBJ_ANY);
122c3405
VM
275}
276
16248ee2
RB
277static const git_tree_entry *entry_fromname(
278 git_tree *tree, const char *name, size_t name_len)
2a884588 279{
11d9f6b3
PK
280 size_t idx;
281
282 if (tree_key_search(&idx, &tree->entries, name, name_len) < 0)
c4034e63
VM
283 return NULL;
284
285 return git_vector_get(&tree->entries, idx);
2a884588
VM
286}
287
16248ee2
RB
288const git_tree_entry *git_tree_entry_byname(
289 git_tree *tree, const char *filename)
0e2fcca8
VM
290{
291 assert(tree && filename);
292 return entry_fromname(tree, filename, strlen(filename));
293}
294
16248ee2
RB
295const git_tree_entry *git_tree_entry_byindex(
296 git_tree *tree, size_t idx)
003c2690 297{
c4b5bedc 298 assert(tree);
e5c80097 299 return git_vector_get(&tree->entries, idx);
003c2690
VM
300}
301
16248ee2
RB
302const git_tree_entry *git_tree_entry_byoid(
303 const git_tree *tree, const git_oid *oid)
2031760c 304{
16248ee2
RB
305 size_t i;
306 const git_tree_entry *e;
2031760c
RB
307
308 assert(tree);
309
310 git_vector_foreach(&tree->entries, i, e) {
311 if (memcmp(&e->oid.id, &oid->id, sizeof(oid->id)) == 0)
312 return e;
313 }
314
315 return NULL;
316}
317
9d0011fd 318int git_tree__prefix_position(git_tree *tree, const char *path)
41a82592
RB
319{
320 git_vector *entries = &tree->entries;
321 struct tree_key_search ksearch;
16248ee2 322 size_t at_pos;
41a82592 323
91e7d263
RB
324 if (!path)
325 return 0;
326
41a82592
RB
327 ksearch.filename = path;
328 ksearch.filename_len = strlen(path);
329
330 /* Find tree entry with appropriate prefix */
11d9f6b3 331 git_vector_bsearch2(&at_pos, entries, &homing_search_cmp, &ksearch);
41a82592
RB
332
333 for (; at_pos < entries->length; ++at_pos) {
334 const git_tree_entry *entry = entries->contents[at_pos];
335 if (homing_search_cmp(&ksearch, entry) < 0)
336 break;
337 }
338
339 for (; at_pos > 0; --at_pos) {
340 const git_tree_entry *entry = entries->contents[at_pos - 1];
341 if (homing_search_cmp(&ksearch, entry) > 0)
342 break;
343 }
344
16248ee2 345 return (int)at_pos;
41a82592
RB
346}
347
e120123e 348size_t git_tree_entrycount(const git_tree *tree)
003c2690 349{
c4b5bedc 350 assert(tree);
e120123e 351 return tree->entries.length;
003c2690
VM
352}
353
5fb98206
JW
354unsigned int git_treebuilder_entrycount(git_treebuilder *bld)
355{
356 assert(bld);
93ab370b 357 return (unsigned int)bld->entrycount;
5fb98206
JW
358}
359
cfeef7ce 360static int tree_error(const char *str, const char *path)
d8603ed9 361{
cfeef7ce
RB
362 if (path)
363 giterr_set(GITERR_TREE, "%s - %s", str, path);
364 else
365 giterr_set(GITERR_TREE, "%s", str);
3aa351ea
CMN
366 return -1;
367}
2a884588 368
3aa351ea
CMN
369static int tree_parse_buffer(git_tree *tree, const char *buffer, const char *buffer_end)
370{
371 if (git_vector_init(&tree->entries, DEFAULT_TREE_SIZE, entry_sort_cmp) < 0)
372 return -1;
e4def81a 373
003c2690
VM
374 while (buffer < buffer_end) {
375 git_tree_entry *entry;
0e2fcca8 376 int attr;
d8603ed9 377
f1c75b94 378 if (git__strtol32(&attr, buffer, &buffer, 8) < 0 || !buffer)
cfeef7ce 379 return tree_error("Failed to parse tree. Can't parse filemode", NULL);
8e9bfa4c 380
f1c75b94
CMN
381 attr = normalize_filemode(attr); /* make sure to normalize the filemode */
382
3aa351ea 383 if (*buffer++ != ' ')
cfeef7ce 384 return tree_error("Failed to parse tree. Object is corrupted", NULL);
d8603ed9 385
3aa351ea 386 if (memchr(buffer, 0, buffer_end - buffer) == NULL)
cfeef7ce 387 return tree_error("Failed to parse tree. Object is corrupted", NULL);
58519018 388
0e2fcca8
VM
389 /** Allocate the entry and store it in the entries vector */
390 {
391 entry = alloc_entry(buffer);
392 GITERR_CHECK_ALLOC(entry);
393
e2237179
RB
394 if (git_vector_insert(&tree->entries, entry) < 0) {
395 git__free(entry);
0e2fcca8 396 return -1;
e2237179 397 }
0e2fcca8
VM
398
399 entry->attr = attr;
400 }
d8603ed9 401
2a884588
VM
402 while (buffer < buffer_end && *buffer != 0)
403 buffer++;
003c2690 404
2a884588 405 buffer++;
d8603ed9 406
fa48608e 407 git_oid_fromraw(&entry->oid, (const unsigned char *)buffer);
d8603ed9 408 buffer += GIT_OID_RAWSZ;
d8603ed9
VM
409 }
410
3aa351ea 411 return 0;
d8603ed9 412}
58519018 413
72a3fe42 414int git_tree__parse(git_tree *tree, git_odb_object *obj)
58519018 415{
72a3fe42
VM
416 assert(tree);
417 return tree_parse_buffer(tree, (char *)obj->raw.data, (char *)obj->raw.data + obj->raw.len);
58519018
VM
418}
419
a8122b5d 420static size_t find_next_dir(const char *dirname, git_index *index, size_t start)
8255c69b 421{
a8122b5d 422 size_t dirlen, i, entries = git_index_entrycount(index);
8255c69b
CMN
423
424 dirlen = strlen(dirname);
425 for (i = start; i < entries; ++i) {
f45d51ff 426 const git_index_entry *entry = git_index_get_byindex(index, i);
8255c69b
CMN
427 if (strlen(entry->path) < dirlen ||
428 memcmp(entry->path, dirname, dirlen) ||
429 (dirlen > 0 && entry->path[dirlen] != '/')) {
430 break;
431 }
432 }
433
434 return i;
435}
436
0e2fcca8
VM
437static int append_entry(
438 git_treebuilder *bld,
439 const char *filename,
440 const git_oid *id,
a7dbac0b 441 git_filemode_t filemode)
9ef9e8c3
VM
442{
443 git_tree_entry *entry;
444
0d778b1a 445 if (!valid_entry_name(filename))
cfeef7ce 446 return tree_error("Failed to insert entry. Invalid name for a tree entry", filename);
0d778b1a 447
0e2fcca8 448 entry = alloc_entry(filename);
3aa351ea 449 GITERR_CHECK_ALLOC(entry);
9ef9e8c3 450
9ef9e8c3 451 git_oid_cpy(&entry->oid, id);
a7dbac0b 452 entry->attr = (uint16_t)filemode;
9ef9e8c3 453
e2237179
RB
454 if (git_vector_insert(&bld->entries, entry) < 0) {
455 git__free(entry);
3aa351ea 456 return -1;
e2237179 457 }
9ef9e8c3 458
93ab370b 459 bld->entrycount++;
3aa351ea 460 return 0;
9ef9e8c3
VM
461}
462
9462c471
VM
463static int write_tree(
464 git_oid *oid,
465 git_repository *repo,
466 git_index *index,
467 const char *dirname,
a8122b5d 468 size_t start)
47d8ec56 469{
4a619797 470 git_treebuilder *bld = NULL;
a8122b5d 471 size_t i, entries = git_index_entrycount(index);
4a619797
CMN
472 int error;
473 size_t dirname_len = strlen(dirname);
8255c69b
CMN
474 const git_tree_cache *cache;
475
476 cache = git_tree_cache_get(index->tree, dirname);
477 if (cache != NULL && cache->entries >= 0){
478 git_oid_cpy(oid, &cache->oid);
a8122b5d 479 return (int)find_next_dir(dirname, index, start);
8255c69b 480 }
29e1789b 481
a8122b5d 482 if ((error = git_treebuilder_create(&bld, NULL)) < 0 || bld == NULL)
3aa351ea 483 return -1;
932d1baf 484
4a619797
CMN
485 /*
486 * This loop is unfortunate, but necessary. The index doesn't have
487 * any directores, so we need to handle that manually, and we
488 * need to keep track of the current position.
489 */
490 for (i = start; i < entries; ++i) {
f45d51ff 491 const git_index_entry *entry = git_index_get_byindex(index, i);
16248ee2 492 const char *filename, *next_slash;
4a619797
CMN
493
494 /*
495 * If we've left our (sub)tree, exit the loop and return. The
496 * first check is an early out (and security for the
497 * third). The second check is a simple prefix comparison. The
498 * third check catches situations where there is a directory
499 * win32/sys and a file win32mmap.c. Without it, the following
500 * code believes there is a file win32/mmap.c
501 */
502 if (strlen(entry->path) < dirname_len ||
503 memcmp(entry->path, dirname, dirname_len) ||
504 (dirname_len > 0 && entry->path[dirname_len] != '/')) {
47d8ec56 505 break;
4a619797 506 }
932d1baf 507
4a619797
CMN
508 filename = entry->path + dirname_len;
509 if (*filename == '/')
510 filename++;
511 next_slash = strchr(filename, '/');
512 if (next_slash) {
513 git_oid sub_oid;
514 int written;
515 char *subdir, *last_comp;
516
517 subdir = git__strndup(entry->path, next_slash - entry->path);
3aa351ea 518 GITERR_CHECK_ALLOC(subdir);
29e1789b 519
4a619797 520 /* Write out the subtree */
9462c471 521 written = write_tree(&sub_oid, repo, index, subdir, i);
4a619797 522 if (written < 0) {
cfeef7ce
RB
523 tree_error("Failed to write subtree", subdir);
524 git__free(subdir);
3aa351ea 525 goto on_error;
4a619797
CMN
526 } else {
527 i = written - 1; /* -1 because of the loop increment */
29e1789b 528 }
932d1baf 529
4a619797
CMN
530 /*
531 * We need to figure out what we want toinsert
532 * into this tree. If we're traversing
533 * deps/zlib/, then we only want to write
534 * 'zlib' into the tree.
535 */
536 last_comp = strrchr(subdir, '/');
537 if (last_comp) {
538 last_comp++; /* Get rid of the '/' */
539 } else {
540 last_comp = subdir;
541 }
cfeef7ce 542
9ef9e8c3 543 error = append_entry(bld, last_comp, &sub_oid, S_IFDIR);
3286c408 544 git__free(subdir);
cfeef7ce 545 if (error < 0)
3aa351ea 546 goto on_error;
4a619797 547 } else {
9ef9e8c3 548 error = append_entry(bld, filename, &entry->oid, entry->mode);
cfeef7ce 549 if (error < 0)
3aa351ea 550 goto on_error;
47d8ec56 551 }
29e1789b 552 }
932d1baf 553
3aa351ea
CMN
554 if (git_treebuilder_write(oid, repo, bld) < 0)
555 goto on_error;
29e1789b 556
4a619797 557 git_treebuilder_free(bld);
a8122b5d 558 return (int)i;
4a619797 559
3aa351ea
CMN
560on_error:
561 git_treebuilder_free(bld);
562 return -1;
29e1789b
VM
563}
564
16248ee2
RB
565int git_tree__write_index(
566 git_oid *oid, git_index *index, git_repository *repo)
29e1789b 567{
3aa351ea 568 int ret;
3f0d0c85 569 bool old_ignore_case = false;
29e1789b 570
276ea401 571 assert(oid && index && repo);
47d8ec56 572
f92bcaea 573 if (git_index_has_conflicts(index)) {
574 giterr_set(GITERR_INDEX,
575 "Cannot create a tree from a not fully merged index.");
576 return GIT_EUNMERGED;
577 }
578
8255c69b
CMN
579 if (index->tree != NULL && index->tree->entries >= 0) {
580 git_oid_cpy(oid, &index->tree->oid);
3aa351ea 581 return 0;
8255c69b
CMN
582 }
583
3f0d0c85
PK
584 /* The tree cache didn't help us; we'll have to write
585 * out a tree. If the index is ignore_case, we'll must
586 * make it case-sensitive for the duration of the tree-write
587 * operation. */
588
589 if (index->ignore_case) {
590 old_ignore_case = true;
591 git_index_set_ignore_case(index, false);
592 }
593
3aa351ea 594 ret = write_tree(oid, repo, index, "", 0);
3f0d0c85
PK
595
596 if (old_ignore_case)
597 git_index_set_ignore_case(index, true);
598
3aa351ea 599 return ret < 0 ? ret : 0;
47d8ec56 600}
0ad6efa1 601
0ad6efa1
VM
602int git_treebuilder_create(git_treebuilder **builder_p, const git_tree *source)
603{
604 git_treebuilder *bld;
b8457baa 605 size_t i, source_entries = DEFAULT_TREE_SIZE;
0ad6efa1
VM
606
607 assert(builder_p);
608
609 bld = git__calloc(1, sizeof(git_treebuilder));
3aa351ea 610 GITERR_CHECK_ALLOC(bld);
0ad6efa1
VM
611
612 if (source != NULL)
613 source_entries = source->entries.length;
614
3aa351ea
CMN
615 if (git_vector_init(&bld->entries, source_entries, entry_sort_cmp) < 0)
616 goto on_error;
0ad6efa1
VM
617
618 if (source != NULL) {
e2237179 619 git_tree_entry *entry_src;
0ad6efa1 620
e2237179 621 git_vector_foreach(&source->entries, i, entry_src) {
66439b0b 622 if (append_entry(
623 bld, entry_src->filename,
624 &entry_src->oid,
f1c75b94 625 entry_src->attr) < 0)
3aa351ea 626 goto on_error;
0ad6efa1
VM
627 }
628 }
629
630 *builder_p = bld;
3aa351ea
CMN
631 return 0;
632
633on_error:
634 git_treebuilder_free(bld);
635 return -1;
0ad6efa1
VM
636}
637
0e2fcca8
VM
638int git_treebuilder_insert(
639 const git_tree_entry **entry_out,
640 git_treebuilder *bld,
641 const char *filename,
642 const git_oid *id,
a7dbac0b 643 git_filemode_t filemode)
0ad6efa1
VM
644{
645 git_tree_entry *entry;
11d9f6b3 646 size_t pos;
0ad6efa1
VM
647
648 assert(bld && id && filename);
649
a7dbac0b 650 if (!valid_filemode(filemode))
cfeef7ce 651 return tree_error("Failed to insert entry. Invalid filemode for file", filename);
0ad6efa1 652
28c1451a 653 if (!valid_entry_name(filename))
cfeef7ce 654 return tree_error("Failed to insert entry. Invalid name for a tree entry", filename);
f4ad64c1 655
11d9f6b3 656 if (!tree_key_search(&pos, &bld->entries, filename, strlen(filename))) {
0ad6efa1 657 entry = git_vector_get(&bld->entries, pos);
93ab370b 658 if (entry->removed) {
0ad6efa1 659 entry->removed = 0;
93ab370b
RB
660 bld->entrycount++;
661 }
0ad6efa1 662 } else {
0e2fcca8 663 entry = alloc_entry(filename);
3aa351ea 664 GITERR_CHECK_ALLOC(entry);
0ad6efa1 665
e2237179
RB
666 if (git_vector_insert(&bld->entries, entry) < 0) {
667 git__free(entry);
3aa351ea 668 return -1;
e2237179 669 }
93ab370b
RB
670
671 bld->entrycount++;
0ad6efa1
VM
672 }
673
11d9f6b3
PK
674 git_oid_cpy(&entry->oid, id);
675 entry->attr = filemode;
676
677 if (entry_out)
0ad6efa1
VM
678 *entry_out = entry;
679
3aa351ea 680 return 0;
0ad6efa1
VM
681}
682
0cbbdc26 683static git_tree_entry *treebuilder_get(git_treebuilder *bld, const char *filename)
0ad6efa1 684{
11d9f6b3 685 size_t idx;
0ad6efa1
VM
686 git_tree_entry *entry;
687
688 assert(bld && filename);
689
11d9f6b3 690 if (tree_key_search(&idx, &bld->entries, filename, strlen(filename)) < 0)
0ad6efa1
VM
691 return NULL;
692
693 entry = git_vector_get(&bld->entries, idx);
694 if (entry->removed)
695 return NULL;
696
697 return entry;
698}
699
0cbbdc26
KS
700const git_tree_entry *git_treebuilder_get(git_treebuilder *bld, const char *filename)
701{
702 return treebuilder_get(bld, filename);
703}
704
0ad6efa1
VM
705int git_treebuilder_remove(git_treebuilder *bld, const char *filename)
706{
0cbbdc26 707 git_tree_entry *remove_ptr = treebuilder_get(bld, filename);
0ad6efa1
VM
708
709 if (remove_ptr == NULL || remove_ptr->removed)
cfeef7ce 710 return tree_error("Failed to remove entry. File isn't in the tree", filename);
0ad6efa1
VM
711
712 remove_ptr->removed = 1;
93ab370b 713 bld->entrycount--;
3aa351ea 714 return 0;
0ad6efa1
VM
715}
716
717int git_treebuilder_write(git_oid *oid, git_repository *repo, git_treebuilder *bld)
718{
e2237179
RB
719 int error = 0;
720 size_t i;
afeecf4f 721 git_buf tree = GIT_BUF_INIT;
9462c471 722 git_odb *odb;
0ad6efa1
VM
723
724 assert(bld);
725
e2237179 726 git_vector_sort(&bld->entries);
0ad6efa1 727
afeecf4f 728 /* Grow the buffer beforehand to an estimated size */
e2237179 729 error = git_buf_grow(&tree, bld->entries.length * 72);
afeecf4f 730
e2237179
RB
731 for (i = 0; i < bld->entries.length && !error; ++i) {
732 git_tree_entry *entry = git_vector_get(&bld->entries, i);
0ad6efa1
VM
733
734 if (entry->removed)
735 continue;
736
afeecf4f
VM
737 git_buf_printf(&tree, "%o ", entry->attr);
738 git_buf_put(&tree, entry->filename, entry->filename_len + 1);
739 git_buf_put(&tree, (char *)entry->oid.id, GIT_OID_RAWSZ);
0ad6efa1 740
e2237179
RB
741 if (git_buf_oom(&tree))
742 error = -1;
743 }
9462c471 744
e2237179
RB
745 if (!error &&
746 !(error = git_repository_odb__weakptr(&odb, repo)))
747 error = git_odb_write(oid, odb, tree.ptr, tree.size, GIT_OBJ_TREE);
0ad6efa1 748
3aa351ea 749 git_buf_free(&tree);
e2237179 750 return error;
0ad6efa1
VM
751}
752
e120123e
RB
753void git_treebuilder_filter(
754 git_treebuilder *bld,
755 git_treebuilder_filter_cb filter,
756 void *payload)
0ad6efa1 757{
e2237179
RB
758 size_t i;
759 git_tree_entry *entry;
0ad6efa1
VM
760
761 assert(bld && filter);
762
e2237179 763 git_vector_foreach(&bld->entries, i, entry) {
93ab370b 764 if (!entry->removed && filter(entry, payload)) {
0ad6efa1 765 entry->removed = 1;
93ab370b
RB
766 bld->entrycount--;
767 }
0ad6efa1
VM
768 }
769}
770
771void git_treebuilder_clear(git_treebuilder *bld)
772{
e2237179
RB
773 size_t i;
774 git_tree_entry *e;
775
0ad6efa1
VM
776 assert(bld);
777
e2237179 778 git_vector_foreach(&bld->entries, i, e)
0e2fcca8 779 git_tree_entry_free(e);
0ad6efa1
VM
780
781 git_vector_clear(&bld->entries);
93ab370b 782 bld->entrycount = 0;
0ad6efa1
VM
783}
784
785void git_treebuilder_free(git_treebuilder *bld)
786{
b0b3b4e3 787 if (bld == NULL)
788 return;
789
0ad6efa1
VM
790 git_treebuilder_clear(bld);
791 git_vector_free(&bld->entries);
3286c408 792 git__free(bld);
0ad6efa1
VM
793}
794
0e2fcca8
VM
795static size_t subpath_len(const char *path)
796{
797 const char *slash_pos = strchr(path, '/');
798 if (slash_pos == NULL)
799 return strlen(path);
800
801 return slash_pos - path;
802}
803
804int git_tree_entry_bypath(
805 git_tree_entry **entry_out,
9432af36 806 git_tree *root,
0e2fcca8 807 const char *path)
3fa735ca 808{
e172cf08 809 int error = 0;
3fa735ca 810 git_tree *subtree;
0e2fcca8
VM
811 const git_tree_entry *entry;
812 size_t filename_len;
3fa735ca 813
0e2fcca8
VM
814 /* Find how long is the current path component (i.e.
815 * the filename between two slashes */
816 filename_len = subpath_len(path);
3fa735ca 817
0e2fcca8
VM
818 if (filename_len == 0) {
819 giterr_set(GITERR_TREE, "Invalid tree path given");
820 return GIT_ENOTFOUND;
3aa351ea 821 }
3fa735ca 822
0e2fcca8 823 entry = entry_fromname(root, path, filename_len);
3fa735ca 824
3aa351ea
CMN
825 if (entry == NULL) {
826 giterr_set(GITERR_TREE,
0e2fcca8 827 "The path '%s' does not exist in the given tree", path);
904b67e6 828 return GIT_ENOTFOUND;
3aa351ea 829 }
0ad6efa1 830
0e2fcca8 831 switch (path[filename_len]) {
2031760c 832 case '/':
0e2fcca8
VM
833 /* If there are more components in the path...
834 * then this entry *must* be a tree */
835 if (!git_tree_entry__is_tree(entry)) {
836 giterr_set(GITERR_TREE,
837 "The path '%s' does not exist in the given tree", path);
dc1f4b32 838 return GIT_ENOTFOUND;
0e2fcca8
VM
839 }
840
841 /* If there's only a slash left in the path, we
842 * return the current entry; otherwise, we keep
843 * walking down the path */
844 if (path[filename_len + 1] != '\0')
845 break;
846
847 case '\0':
848 /* If there are no more components in the path, return
849 * this entry */
46ea40d9 850 *entry_out = git_tree_entry_dup(entry);
0e2fcca8
VM
851 return 0;
852 }
9432af36 853
3aa351ea 854 if (git_tree_lookup(&subtree, root->object.repo, &entry->oid) < 0)
0e2fcca8 855 return -1;
3fa735ca 856
0e2fcca8
VM
857 error = git_tree_entry_bypath(
858 entry_out,
9432af36 859 subtree,
0e2fcca8 860 path + filename_len + 1
9432af36 861 );
3fa735ca 862
45e79e37 863 git_tree_free(subtree);
3fa735ca 864 return error;
865}
866
c6f42953 867static int tree_walk(
f45d51ff 868 const git_tree *tree,
9432af36 869 git_treewalk_cb callback,
97769280 870 git_buf *path,
c6f42953
MS
871 void *payload,
872 bool preorder)
da37654d 873{
e172cf08 874 int error = 0;
16248ee2 875 size_t i;
e2237179 876 const git_tree_entry *entry;
da37654d 877
e2237179 878 git_vector_foreach(&tree->entries, i, entry) {
a6bf1687
CMN
879 if (preorder) {
880 error = callback(path->ptr, entry, payload);
881 if (error > 0)
882 continue;
e2237179
RB
883 if (error < 0) {
884 giterr_clear();
a6bf1687 885 return GIT_EUSER;
e2237179 886 }
a6bf1687 887 }
da37654d 888
9d0011fd 889 if (git_tree_entry__is_tree(entry)) {
da37654d 890 git_tree *subtree;
fa6420f7 891 size_t path_len = git_buf_len(path);
da37654d 892
9432af36
VM
893 if ((error = git_tree_lookup(
894 &subtree, tree->object.repo, &entry->oid)) < 0)
97769280 895 break;
da37654d 896
97769280
RB
897 /* append the next entry to the path */
898 git_buf_puts(path, entry->filename);
899 git_buf_putc(path, '/');
da37654d 900
cb8a7961 901 if (git_buf_oom(path))
3aa351ea 902 return -1;
da37654d 903
2031760c
RB
904 error = tree_walk(subtree, callback, path, payload, preorder);
905 if (error != 0)
906 break;
da37654d 907
97769280 908 git_buf_truncate(path, path_len);
45e79e37 909 git_tree_free(subtree);
da37654d 910 }
c6f42953 911
a6bf1687 912 if (!preorder && callback(path->ptr, entry, payload) < 0) {
e2237179 913 giterr_clear();
b0d37669 914 error = GIT_EUSER;
2031760c 915 break;
b0d37669 916 }
da37654d
VM
917 }
918
2031760c 919 return error;
da37654d
VM
920}
921
e120123e 922int git_tree_walk(
f45d51ff 923 const git_tree *tree,
e120123e
RB
924 git_treewalk_mode mode,
925 git_treewalk_cb callback,
926 void *payload)
da37654d 927{
e172cf08 928 int error = 0;
97769280 929 git_buf root_path = GIT_BUF_INIT;
da37654d 930
e2237179 931 if (mode != GIT_TREEWALK_POST && mode != GIT_TREEWALK_PRE) {
e120123e
RB
932 giterr_set(GITERR_INVALID, "Invalid walking mode for tree walk");
933 return -1;
da37654d 934 }
97769280 935
e2237179
RB
936 error = tree_walk(
937 tree, callback, &root_path, payload, (mode == GIT_TREEWALK_PRE));
938
97769280
RB
939 git_buf_free(&root_path);
940
941 return error;
da37654d 942}
a1fdea28 943