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.
12 #include "git2/submodule.h"
15 #define ITERATOR_SET_CB(P,NAME_LC) do { \
16 (P)->cb.current = NAME_LC ## _iterator__current; \
17 (P)->cb.advance = NAME_LC ## _iterator__advance; \
18 (P)->cb.advance_into = NAME_LC ## _iterator__advance_into; \
19 (P)->cb.seek = NAME_LC ## _iterator__seek; \
20 (P)->cb.reset = NAME_LC ## _iterator__reset; \
21 (P)->cb.at_end = NAME_LC ## _iterator__at_end; \
22 (P)->cb.free = NAME_LC ## _iterator__free; \
25 #define ITERATOR_CASE_FLAGS \
26 (GIT_ITERATOR_IGNORE_CASE | GIT_ITERATOR_DONT_IGNORE_CASE)
28 #define ITERATOR_BASE_INIT(P,NAME_LC,NAME_UC,REPO) do { \
29 (P) = git__calloc(1, sizeof(NAME_LC ## _iterator)); \
30 GITERR_CHECK_ALLOC(P); \
31 (P)->base.type = GIT_ITERATOR_TYPE_ ## NAME_UC; \
32 (P)->base.cb = &(P)->cb; \
33 ITERATOR_SET_CB(P,NAME_LC); \
34 (P)->base.repo = (REPO); \
35 (P)->base.start = start ? git__strdup(start) : NULL; \
36 (P)->base.end = end ? git__strdup(end) : NULL; \
37 if ((start && !(P)->base.start) || (end && !(P)->base.end)) { \
38 git__free(P); return -1; } \
39 (P)->base.prefixcomp = git__prefixcmp; \
40 (P)->base.flags = flags & ~ITERATOR_CASE_FLAGS; \
41 if ((P)->base.flags & GIT_ITERATOR_DONT_AUTOEXPAND) \
42 (P)->base.flags |= GIT_ITERATOR_INCLUDE_TREES; \
45 #define iterator__flag(I,F) ((((git_iterator *)(I))->flags & GIT_ITERATOR_ ## F) != 0)
46 #define iterator__ignore_case(I) iterator__flag(I,IGNORE_CASE)
47 #define iterator__include_trees(I) iterator__flag(I,INCLUDE_TREES)
48 #define iterator__dont_autoexpand(I) iterator__flag(I,DONT_AUTOEXPAND)
49 #define iterator__do_autoexpand(I) !iterator__flag(I,DONT_AUTOEXPAND)
51 #define iterator__end(I) ((git_iterator *)(I))->end
52 #define iterator__past_end(I,PATH) \
53 (iterator__end(I) && ((git_iterator *)(I))->prefixcomp((PATH),iterator__end(I)) > 0)
56 static int iterator__reset_range(
57 git_iterator
*iter
, const char *start
, const char *end
)
61 git__free(iter
->start
);
62 iter
->start
= git__strdup(start
);
63 GITERR_CHECK_ALLOC(iter
->start
);
69 iter
->end
= git__strdup(end
);
70 GITERR_CHECK_ALLOC(iter
->end
);
76 static int iterator__update_ignore_case(
78 git_iterator_flag_t flags
)
80 int error
= 0, ignore_case
= -1;
82 if ((flags
& GIT_ITERATOR_IGNORE_CASE
) != 0)
84 else if ((flags
& GIT_ITERATOR_DONT_IGNORE_CASE
) != 0)
89 if (!(error
= git_repository_index__weakptr(&index
, iter
->repo
)))
90 ignore_case
= (index
->ignore_case
!= false);
94 iter
->flags
= (iter
->flags
| GIT_ITERATOR_IGNORE_CASE
);
95 else if (ignore_case
== 0)
96 iter
->flags
= (iter
->flags
& ~GIT_ITERATOR_IGNORE_CASE
);
98 iter
->prefixcomp
= iterator__ignore_case(iter
) ?
99 git__prefixcmp_icase
: git__prefixcmp
;
104 GIT_INLINE(void) iterator__clear_entry(const git_index_entry
**entry
)
106 if (entry
) *entry
= NULL
;
110 static int empty_iterator__noop(const git_index_entry
**e
, git_iterator
*i
)
113 iterator__clear_entry(e
);
117 static int empty_iterator__seek(git_iterator
*i
, const char *p
)
119 GIT_UNUSED(i
); GIT_UNUSED(p
);
123 static int empty_iterator__reset(git_iterator
*i
, const char *s
, const char *e
)
125 GIT_UNUSED(i
); GIT_UNUSED(s
); GIT_UNUSED(e
);
129 static int empty_iterator__at_end(git_iterator
*i
)
135 static void empty_iterator__free(git_iterator
*i
)
142 git_iterator_callbacks cb
;
145 int git_iterator_for_nothing(
147 git_iterator_flag_t flags
,
153 #define empty_iterator__current empty_iterator__noop
154 #define empty_iterator__advance empty_iterator__noop
155 #define empty_iterator__advance_into empty_iterator__noop
157 ITERATOR_BASE_INIT(i
, empty
, EMPTY
, NULL
);
159 if ((flags
& GIT_ITERATOR_IGNORE_CASE
) != 0)
160 i
->base
.flags
|= GIT_ITERATOR_IGNORE_CASE
;
162 *iter
= (git_iterator
*)i
;
167 typedef struct tree_iterator_entry tree_iterator_entry
;
168 struct tree_iterator_entry
{
169 tree_iterator_entry
*parent
;
170 const git_tree_entry
*te
;
174 typedef struct tree_iterator_frame tree_iterator_frame
;
175 struct tree_iterator_frame
{
176 tree_iterator_frame
*up
, *down
;
178 size_t n_entries
; /* items in this frame */
179 size_t current
; /* start of currently active range in frame */
180 size_t next
; /* start of next range in frame */
185 tree_iterator_entry
*entries
[GIT_FLEX_ARRAY
];
190 git_iterator_callbacks cb
;
191 tree_iterator_frame
*head
, *root
;
193 git_index_entry entry
;
195 int path_ambiguities
;
196 bool path_has_filename
;
197 int (*strncomp
)(const char *a
, const char *b
, size_t sz
);
200 static char *tree_iterator__current_filename(
201 tree_iterator
*ti
, const git_tree_entry
*te
)
203 if (!ti
->path_has_filename
) {
204 if (git_buf_joinpath(&ti
->path
, ti
->path
.ptr
, te
->filename
) < 0)
207 if (git_tree_entry__is_tree(te
) && git_buf_putc(&ti
->path
, '/') < 0)
210 ti
->path_has_filename
= true;
216 static void tree_iterator__rewrite_filename(tree_iterator
*ti
)
218 tree_iterator_entry
*scan
= ti
->head
->entries
[ti
->head
->current
];
219 ssize_t strpos
= ti
->path
.size
;
220 const git_tree_entry
*te
;
222 if (strpos
&& ti
->path
.ptr
[strpos
- 1] == '/')
225 for (; scan
&& (te
= scan
->te
); scan
= scan
->parent
) {
226 strpos
-= te
->filename_len
;
227 memcpy(&ti
->path
.ptr
[strpos
], te
->filename
, te
->filename_len
);
228 strpos
-= 1; /* separator */
232 static int tree_iterator__te_cmp(
233 const git_tree_entry
*a
,
234 const git_tree_entry
*b
,
235 int (*compare
)(const char *, const char *, size_t))
238 a
->filename
, a
->filename_len
, a
->attr
== GIT_FILEMODE_TREE
,
239 b
->filename
, b
->filename_len
, b
->attr
== GIT_FILEMODE_TREE
,
243 static int tree_iterator__ci_cmp(const void *a
, const void *b
, void *p
)
245 const tree_iterator_entry
*ae
= a
, *be
= b
;
246 int cmp
= tree_iterator__te_cmp(ae
->te
, be
->te
, git__strncasecmp
);
249 /* stabilize sort order among equivalent names */
250 if (!ae
->parent
->te
|| !be
->parent
->te
)
251 cmp
= tree_iterator__te_cmp(ae
->te
, be
->te
, git__strncmp
);
253 cmp
= tree_iterator__ci_cmp(ae
->parent
, be
->parent
, p
);
259 static int tree_iterator__search_cmp(const void *key
, const void *val
, void *p
)
261 const tree_iterator_frame
*tf
= key
;
262 const git_tree_entry
*te
= ((tree_iterator_entry
*)val
)->te
;
265 tf
->start
, tf
->startlen
, false,
266 te
->filename
, te
->filename_len
, te
->attr
== GIT_FILEMODE_TREE
,
267 ((tree_iterator
*)p
)->strncomp
);
270 static int tree_iterator__set_next(tree_iterator
*ti
, tree_iterator_frame
*tf
)
273 const git_tree_entry
*te
, *last
= NULL
;
275 tf
->next
= tf
->current
;
277 for (; tf
->next
< tf
->n_entries
; tf
->next
++, last
= te
) {
278 te
= tf
->entries
[tf
->next
]->te
;
280 if (last
&& tree_iterator__te_cmp(last
, te
, ti
->strncomp
))
283 /* load trees for items in [current,next) range */
284 if (git_tree_entry__is_tree(te
) &&
285 (error
= git_tree_lookup(
286 &tf
->entries
[tf
->next
]->tree
, ti
->base
.repo
, &te
->oid
)) < 0)
290 if (tf
->next
> tf
->current
+ 1)
291 ti
->path_ambiguities
++;
293 if (last
&& !tree_iterator__current_filename(ti
, last
))
299 GIT_INLINE(bool) tree_iterator__at_tree(tree_iterator
*ti
)
301 return (ti
->head
->current
< ti
->head
->n_entries
&&
302 ti
->head
->entries
[ti
->head
->current
]->tree
!= NULL
);
305 static int tree_iterator__push_frame(tree_iterator
*ti
)
308 tree_iterator_frame
*head
= ti
->head
, *tf
= NULL
;
309 size_t i
, n_entries
= 0;
311 if (head
->current
>= head
->n_entries
|| !head
->entries
[head
->current
]->tree
)
314 for (i
= head
->current
; i
< head
->next
; ++i
)
315 n_entries
+= git_tree_entrycount(head
->entries
[i
]->tree
);
317 tf
= git__calloc(sizeof(tree_iterator_frame
) +
318 n_entries
* sizeof(tree_iterator_entry
*), 1);
319 GITERR_CHECK_ALLOC(tf
);
321 tf
->n_entries
= n_entries
;
327 for (i
= head
->current
, n_entries
= 0; i
< head
->next
; ++i
) {
328 git_tree
*tree
= head
->entries
[i
]->tree
;
329 size_t j
, max_j
= git_tree_entrycount(tree
);
331 for (j
= 0; j
< max_j
; ++j
) {
332 tree_iterator_entry
*entry
= git_pool_malloc(&ti
->pool
, 1);
333 GITERR_CHECK_ALLOC(entry
);
335 entry
->parent
= head
->entries
[i
];
336 entry
->te
= git_tree_entry_byindex(tree
, j
);
339 tf
->entries
[n_entries
++] = entry
;
343 /* if ignore_case, sort entries case insensitively */
344 if (iterator__ignore_case(ti
))
346 (void **)tf
->entries
, tf
->n_entries
, tree_iterator__ci_cmp
, tf
);
348 /* pick tf->current based on "start" (or start at zero) */
349 if (head
->startlen
> 0) {
350 git__bsearch_r((void **)tf
->entries
, tf
->n_entries
, head
,
351 tree_iterator__search_cmp
, ti
, &tf
->current
);
353 while (tf
->current
&&
354 !tree_iterator__search_cmp(head
, tf
->entries
[tf
->current
-1], ti
))
357 if ((tf
->start
= strchr(head
->start
, '/')) != NULL
) {
359 tf
->startlen
= strlen(tf
->start
);
363 ti
->path_has_filename
= false;
365 if ((error
= tree_iterator__set_next(ti
, tf
)) < 0)
368 /* autoexpand as needed */
369 if (!iterator__include_trees(ti
) && tree_iterator__at_tree(ti
))
370 return tree_iterator__push_frame(ti
);
375 static bool tree_iterator__move_to_next(
376 tree_iterator
*ti
, tree_iterator_frame
*tf
)
378 if (tf
->next
> tf
->current
+ 1)
379 ti
->path_ambiguities
--;
381 if (!tf
->up
) { /* at root */
382 tf
->current
= tf
->next
;
386 for (; tf
->current
< tf
->next
; tf
->current
++) {
387 git_tree_free(tf
->entries
[tf
->current
]->tree
);
388 tf
->entries
[tf
->current
]->tree
= NULL
;
391 return (tf
->current
< tf
->n_entries
);
394 static bool tree_iterator__pop_frame(tree_iterator
*ti
, bool final
)
396 tree_iterator_frame
*tf
= ti
->head
;
402 ti
->head
->down
= NULL
;
404 tree_iterator__move_to_next(ti
, tf
);
406 if (!final
) { /* if final, don't bother to clean up */
407 git_pool_free_array(&ti
->pool
, tf
->n_entries
, (void **)tf
->entries
);
408 git_buf_rtruncate_at_char(&ti
->path
, '/');
416 static int tree_iterator__pop_all(tree_iterator
*ti
, bool to_end
, bool final
)
418 while (tree_iterator__pop_frame(ti
, final
)) /* pop to root */;
421 ti
->head
->current
= to_end
? ti
->head
->n_entries
: 0;
422 ti
->path_ambiguities
= 0;
423 git_buf_clear(&ti
->path
);
429 static int tree_iterator__current(
430 const git_index_entry
**entry
, git_iterator
*self
)
432 tree_iterator
*ti
= (tree_iterator
*)self
;
433 tree_iterator_frame
*tf
= ti
->head
;
434 const git_tree_entry
*te
;
436 iterator__clear_entry(entry
);
438 if (tf
->current
>= tf
->n_entries
)
440 te
= tf
->entries
[tf
->current
]->te
;
442 ti
->entry
.mode
= te
->attr
;
443 git_oid_cpy(&ti
->entry
.oid
, &te
->oid
);
445 ti
->entry
.path
= tree_iterator__current_filename(ti
, te
);
446 GITERR_CHECK_ALLOC(ti
->entry
.path
);
448 if (ti
->path_ambiguities
> 0)
449 tree_iterator__rewrite_filename(ti
);
451 if (iterator__past_end(ti
, ti
->entry
.path
))
452 return tree_iterator__pop_all(ti
, true, false);
460 static int tree_iterator__advance_into(
461 const git_index_entry
**entry
, git_iterator
*self
)
464 tree_iterator
*ti
= (tree_iterator
*)self
;
466 iterator__clear_entry(entry
);
468 if (tree_iterator__at_tree(ti
) &&
469 !(error
= tree_iterator__push_frame(ti
)))
470 error
= tree_iterator__current(entry
, self
);
475 static int tree_iterator__advance(
476 const git_index_entry
**entry
, git_iterator
*self
)
479 tree_iterator
*ti
= (tree_iterator
*)self
;
480 tree_iterator_frame
*tf
= ti
->head
;
482 iterator__clear_entry(entry
);
484 if (tf
->current
> tf
->n_entries
)
487 if (iterator__do_autoexpand(ti
) && iterator__include_trees(ti
) &&
488 tree_iterator__at_tree(ti
))
489 return tree_iterator__advance_into(entry
, self
);
491 if (ti
->path_has_filename
) {
492 git_buf_rtruncate_at_char(&ti
->path
, '/');
493 ti
->path_has_filename
= false;
496 /* scan forward and up, advancing in frame or popping frame when done */
497 while (!tree_iterator__move_to_next(ti
, tf
) &&
498 tree_iterator__pop_frame(ti
, false))
501 /* find next and load trees */
502 if ((error
= tree_iterator__set_next(ti
, tf
)) < 0)
505 /* deal with include_trees / auto_expand as needed */
506 if (!iterator__include_trees(ti
) && tree_iterator__at_tree(ti
))
507 return tree_iterator__advance_into(entry
, self
);
509 return tree_iterator__current(entry
, self
);
512 static int tree_iterator__seek(git_iterator
*self
, const char *prefix
)
514 GIT_UNUSED(self
); GIT_UNUSED(prefix
);
518 static int tree_iterator__reset(
519 git_iterator
*self
, const char *start
, const char *end
)
521 tree_iterator
*ti
= (tree_iterator
*)self
;
523 tree_iterator__pop_all(ti
, false, false);
525 if (iterator__reset_range(self
, start
, end
) < 0)
528 return tree_iterator__push_frame(ti
); /* re-expand root tree */
531 static int tree_iterator__at_end(git_iterator
*self
)
533 tree_iterator
*ti
= (tree_iterator
*)self
;
534 return (ti
->head
->current
>= ti
->head
->n_entries
);
537 static void tree_iterator__free(git_iterator
*self
)
539 tree_iterator
*ti
= (tree_iterator
*)self
;
541 tree_iterator__pop_all(ti
, true, false);
543 git_tree_free(ti
->head
->entries
[0]->tree
);
545 git_pool_clear(&ti
->pool
);
546 git_buf_free(&ti
->path
);
549 static int tree_iterator__create_root_frame(tree_iterator
*ti
, git_tree
*tree
)
551 size_t sz
= sizeof(tree_iterator_frame
) + sizeof(tree_iterator_entry
);
552 tree_iterator_frame
*root
= git__calloc(sz
, sizeof(char));
553 GITERR_CHECK_ALLOC(root
);
557 root
->start
= ti
->base
.start
;
558 root
->startlen
= root
->start
? strlen(root
->start
) : 0;
559 root
->entries
[0] = git_pool_mallocz(&ti
->pool
, 1);
560 GITERR_CHECK_ALLOC(root
->entries
[0]);
561 root
->entries
[0]->tree
= tree
;
563 ti
->head
= ti
->root
= root
;
568 int git_iterator_for_tree(
571 git_iterator_flag_t flags
,
579 return git_iterator_for_nothing(iter
, flags
, start
, end
);
581 if ((error
= git_object_dup((git_object
**)&tree
, (git_object
*)tree
)) < 0)
584 ITERATOR_BASE_INIT(ti
, tree
, TREE
, git_tree_owner(tree
));
586 if ((error
= iterator__update_ignore_case((git_iterator
*)ti
, flags
)) < 0)
588 ti
->strncomp
= iterator__ignore_case(ti
) ? git__strncasecmp
: git__strncmp
;
590 if ((error
= git_pool_init(&ti
->pool
, sizeof(tree_iterator_entry
),0)) < 0 ||
591 (error
= tree_iterator__create_root_frame(ti
, tree
)) < 0 ||
592 (error
= tree_iterator__push_frame(ti
)) < 0) /* expand root now */
595 *iter
= (git_iterator
*)ti
;
599 git_iterator_free((git_iterator
*)ti
);
606 git_iterator_callbacks cb
;
609 /* when not in autoexpand mode, use these to represent "tree" state */
612 char restore_terminator
;
613 git_index_entry tree_entry
;
616 static const git_index_entry
*index_iterator__index_entry(index_iterator
*ii
)
618 const git_index_entry
*ie
= git_index_get_byindex(ii
->index
, ii
->current
);
620 if (ie
!= NULL
&& iterator__past_end(ii
, ie
->path
)) {
621 ii
->current
= git_index_entrycount(ii
->index
);
628 static const git_index_entry
*index_iterator__skip_conflicts(index_iterator
*ii
)
630 const git_index_entry
*ie
;
632 while ((ie
= index_iterator__index_entry(ii
)) != NULL
&&
633 git_index_entry_stage(ie
) != 0)
639 static void index_iterator__next_prefix_tree(index_iterator
*ii
)
643 if (!iterator__include_trees(ii
))
646 slash
= strchr(&ii
->partial
.ptr
[ii
->partial_pos
], '/');
649 ii
->partial_pos
= (slash
- ii
->partial
.ptr
) + 1;
650 ii
->restore_terminator
= ii
->partial
.ptr
[ii
->partial_pos
];
651 ii
->partial
.ptr
[ii
->partial_pos
] = '\0';
653 ii
->partial_pos
= ii
->partial
.size
;
656 if (index_iterator__index_entry(ii
) == NULL
)
657 ii
->partial_pos
= ii
->partial
.size
;
660 static int index_iterator__first_prefix_tree(index_iterator
*ii
)
662 const git_index_entry
*ie
= index_iterator__skip_conflicts(ii
);
663 const char *scan
, *prior
, *slash
;
665 if (!ie
|| !iterator__include_trees(ii
))
668 /* find longest common prefix with prior index entry */
669 for (scan
= slash
= ie
->path
, prior
= ii
->partial
.ptr
;
670 *scan
&& *scan
== *prior
; ++scan
, ++prior
)
674 if (git_buf_sets(&ii
->partial
, ie
->path
) < 0)
677 ii
->partial_pos
= (slash
- ie
->path
) + 1;
678 index_iterator__next_prefix_tree(ii
);
683 #define index_iterator__at_tree(I) \
684 (iterator__include_trees(I) && (I)->partial_pos < (I)->partial.size)
686 static int index_iterator__current(
687 const git_index_entry
**entry
, git_iterator
*self
)
689 index_iterator
*ii
= (index_iterator
*)self
;
690 const git_index_entry
*ie
= git_index_get_byindex(ii
->index
, ii
->current
);
692 if (ie
!= NULL
&& index_iterator__at_tree(ii
)) {
693 ii
->tree_entry
.path
= ii
->partial
.ptr
;
694 ie
= &ii
->tree_entry
;
703 static int index_iterator__at_end(git_iterator
*self
)
705 index_iterator
*ii
= (index_iterator
*)self
;
706 return (ii
->current
>= git_index_entrycount(ii
->index
));
709 static int index_iterator__advance(
710 const git_index_entry
**entry
, git_iterator
*self
)
712 index_iterator
*ii
= (index_iterator
*)self
;
713 size_t entrycount
= git_index_entrycount(ii
->index
);
714 const git_index_entry
*ie
;
716 if (index_iterator__at_tree(ii
)) {
717 if (iterator__do_autoexpand(ii
)) {
718 ii
->partial
.ptr
[ii
->partial_pos
] = ii
->restore_terminator
;
719 index_iterator__next_prefix_tree(ii
);
721 /* advance to sibling tree (i.e. find entry with new prefix) */
722 while (ii
->current
< entrycount
) {
725 if (!(ie
= git_index_get_byindex(ii
->index
, ii
->current
)) ||
726 ii
->base
.prefixcomp(ie
->path
, ii
->partial
.ptr
) != 0)
730 if (index_iterator__first_prefix_tree(ii
) < 0)
734 if (ii
->current
< entrycount
)
737 if (index_iterator__first_prefix_tree(ii
) < 0)
741 return index_iterator__current(entry
, self
);
744 static int index_iterator__advance_into(
745 const git_index_entry
**entry
, git_iterator
*self
)
747 index_iterator
*ii
= (index_iterator
*)self
;
748 const git_index_entry
*ie
= git_index_get_byindex(ii
->index
, ii
->current
);
750 if (ie
!= NULL
&& index_iterator__at_tree(ii
)) {
751 if (ii
->restore_terminator
)
752 ii
->partial
.ptr
[ii
->partial_pos
] = ii
->restore_terminator
;
753 index_iterator__next_prefix_tree(ii
);
756 return index_iterator__current(entry
, self
);
759 static int index_iterator__seek(git_iterator
*self
, const char *prefix
)
761 GIT_UNUSED(self
); GIT_UNUSED(prefix
);
765 static int index_iterator__reset(
766 git_iterator
*self
, const char *start
, const char *end
)
768 index_iterator
*ii
= (index_iterator
*)self
;
769 const git_index_entry
*ie
;
771 if (iterator__reset_range(self
, start
, end
) < 0)
774 ii
->current
= ii
->base
.start
?
775 git_index__prefix_position(ii
->index
, ii
->base
.start
) : 0;
777 if ((ie
= index_iterator__skip_conflicts(ii
)) == NULL
)
780 if (git_buf_sets(&ii
->partial
, ie
->path
) < 0)
785 if (ii
->base
.start
) {
786 size_t startlen
= strlen(ii
->base
.start
);
788 ii
->partial_pos
= (startlen
> ii
->partial
.size
) ?
789 ii
->partial
.size
: startlen
;
792 index_iterator__next_prefix_tree(ii
);
797 static void index_iterator__free(git_iterator
*self
)
799 index_iterator
*ii
= (index_iterator
*)self
;
800 git_index_free(ii
->index
);
803 git_buf_free(&ii
->partial
);
806 int git_iterator_for_index(
809 git_iterator_flag_t flags
,
815 ITERATOR_BASE_INIT(ii
, index
, INDEX
, git_index_owner(index
));
817 if (index
->ignore_case
) {
818 ii
->base
.flags
|= GIT_ITERATOR_IGNORE_CASE
;
819 ii
->base
.prefixcomp
= git__prefixcmp_icase
;
823 GIT_REFCOUNT_INC(index
);
825 git_buf_init(&ii
->partial
, 0);
826 ii
->tree_entry
.mode
= GIT_FILEMODE_TREE
;
828 index_iterator__reset((git_iterator
*)ii
, NULL
, NULL
);
830 *iter
= (git_iterator
*)ii
;
836 typedef struct fs_iterator_frame fs_iterator_frame
;
837 struct fs_iterator_frame
{
838 fs_iterator_frame
*next
;
845 git_iterator_callbacks cb
;
846 fs_iterator_frame
*stack
;
847 git_index_entry entry
;
853 #define FS_MAX_DEPTH 100
855 static fs_iterator_frame
*fs_iterator__alloc_frame(fs_iterator
*fi
)
857 fs_iterator_frame
*ff
= git__calloc(1, sizeof(fs_iterator_frame
));
858 git_vector_cmp entry_compare
= CASESELECT(
859 iterator__ignore_case(fi
),
860 git_path_with_stat_cmp_icase
, git_path_with_stat_cmp
);
862 if (ff
&& git_vector_init(&ff
->entries
, 0, entry_compare
) < 0) {
870 static void fs_iterator__free_frame(fs_iterator_frame
*ff
)
873 git_path_with_stat
*path
;
875 git_vector_foreach(&ff
->entries
, i
, path
)
877 git_vector_free(&ff
->entries
);
881 static int fs_iterator__update_entry(fs_iterator
*fi
);
883 static int fs_iterator__entry_cmp(const void *i
, const void *item
)
885 const fs_iterator
*fi
= (const fs_iterator
*)i
;
886 const git_path_with_stat
*ps
= item
;
887 return fi
->base
.prefixcomp(fi
->base
.start
, ps
->path
);
890 static void fs_iterator__seek_frame_start(
891 fs_iterator
*fi
, fs_iterator_frame
*ff
)
898 &ff
->index
, &ff
->entries
, fs_iterator__entry_cmp
, fi
);
903 static int fs_iterator__expand_dir(fs_iterator
*fi
)
906 fs_iterator_frame
*ff
;
908 ff
= fs_iterator__alloc_frame(fi
);
909 GITERR_CHECK_ALLOC(ff
);
911 error
= git_path_dirload_with_stat(
912 fi
->path
.ptr
, fi
->root_len
, iterator__ignore_case(fi
),
913 fi
->base
.start
, fi
->base
.end
, &ff
->entries
);
915 if (error
< 0 || ff
->entries
.length
== 0) {
916 fs_iterator__free_frame(ff
);
917 return GIT_ENOTFOUND
;
920 if (++(fi
->depth
) > FS_MAX_DEPTH
) {
921 giterr_set(GITERR_REPOSITORY
,
922 "Directory nesting is too deep (%d)", fi
->depth
);
923 fs_iterator__free_frame(ff
);
927 fs_iterator__seek_frame_start(fi
, ff
);
929 ff
->next
= fi
->stack
;
932 return fs_iterator__update_entry(fi
);
935 static int fs_iterator__current(
936 const git_index_entry
**entry
, git_iterator
*self
)
938 fs_iterator
*fi
= (fs_iterator
*)self
;
940 *entry
= (fi
->entry
.path
== NULL
) ? NULL
: &fi
->entry
;
944 static int fs_iterator__at_end(git_iterator
*self
)
946 return (((fs_iterator
*)self
)->entry
.path
== NULL
);
949 static int fs_iterator__advance_into(
950 const git_index_entry
**entry
, git_iterator
*iter
)
953 fs_iterator
*fi
= (fs_iterator
*)iter
;
955 iterator__clear_entry(entry
);
957 /* Allow you to explicitly advance into a commit/submodule (as well as a
958 * tree) to avoid cases where an entry is mislabeled as a submodule in
959 * the working directory. The fs iterator will never have COMMMIT
960 * entries on it's own, but a wrapper might add them.
962 if (fi
->entry
.path
!= NULL
&&
963 (fi
->entry
.mode
== GIT_FILEMODE_TREE
||
964 fi
->entry
.mode
== GIT_FILEMODE_COMMIT
))
965 /* returns GIT_ENOTFOUND if the directory is empty */
966 error
= fs_iterator__expand_dir(fi
);
969 error
= fs_iterator__current(entry
, iter
);
974 static int fs_iterator__advance(
975 const git_index_entry
**entry
, git_iterator
*self
)
978 fs_iterator
*fi
= (fs_iterator
*)self
;
979 fs_iterator_frame
*ff
;
980 git_path_with_stat
*next
;
982 /* given include_trees & autoexpand, we might have to go into a tree */
983 if (iterator__do_autoexpand(fi
) &&
984 fi
->entry
.path
!= NULL
&&
985 fi
->entry
.mode
== GIT_FILEMODE_TREE
)
987 error
= fs_iterator__advance_into(entry
, self
);
989 /* continue silently past empty directories if autoexpanding */
990 if (error
!= GIT_ENOTFOUND
)
999 while (fi
->entry
.path
!= NULL
) {
1001 next
= git_vector_get(&ff
->entries
, ++ff
->index
);
1006 /* pop stack if anything is left to pop */
1008 memset(&fi
->entry
, 0, sizeof(fi
->entry
));
1012 fi
->stack
= ff
->next
;
1014 fs_iterator__free_frame(ff
);
1017 error
= fs_iterator__update_entry(fi
);
1019 if (!error
&& entry
!= NULL
)
1020 error
= fs_iterator__current(entry
, self
);
1025 static int fs_iterator__seek(git_iterator
*self
, const char *prefix
)
1029 /* pop stack until matching prefix */
1030 /* find prefix item in current frame */
1031 /* push subdirectories as deep as possible while matching */
1035 static int fs_iterator__reset(
1036 git_iterator
*self
, const char *start
, const char *end
)
1038 fs_iterator
*fi
= (fs_iterator
*)self
;
1040 while (fi
->stack
!= NULL
&& fi
->stack
->next
!= NULL
) {
1041 fs_iterator_frame
*ff
= fi
->stack
;
1042 fi
->stack
= ff
->next
;
1043 fs_iterator__free_frame(ff
);
1047 if (iterator__reset_range(self
, start
, end
) < 0)
1050 fs_iterator__seek_frame_start(fi
, fi
->stack
);
1052 return fs_iterator__update_entry(fi
);
1055 static void fs_iterator__free(git_iterator
*self
)
1057 fs_iterator
*fi
= (fs_iterator
*)self
;
1059 while (fi
->stack
!= NULL
) {
1060 fs_iterator_frame
*ff
= fi
->stack
;
1061 fi
->stack
= ff
->next
;
1062 fs_iterator__free_frame(ff
);
1065 git_buf_free(&fi
->path
);
1068 static int fs_iterator__update_entry(fs_iterator
*fi
)
1070 git_path_with_stat
*ps
=
1071 git_vector_get(&fi
->stack
->entries
, fi
->stack
->index
);
1073 git_buf_truncate(&fi
->path
, fi
->root_len
);
1074 memset(&fi
->entry
, 0, sizeof(fi
->entry
));
1079 if (git_buf_put(&fi
->path
, ps
->path
, ps
->path_len
) < 0)
1082 if (iterator__past_end(fi
, fi
->path
.ptr
+ fi
->root_len
))
1085 fi
->entry
.path
= ps
->path
;
1086 git_index_entry__init_from_stat(&fi
->entry
, &ps
->st
);
1088 /* need different mode here to keep directories during iteration */
1089 fi
->entry
.mode
= git_futils_canonical_mode(ps
->st
.st_mode
);
1091 /* if this isn't a tree, then we're done */
1092 if (fi
->entry
.mode
!= GIT_FILEMODE_TREE
)
1095 if (iterator__include_trees(fi
))
1098 return fs_iterator__advance(NULL
, (git_iterator
*)fi
);
1101 int git_iterator_for_filesystem(
1104 git_iterator_flag_t flags
,
1111 ITERATOR_BASE_INIT(fi
, fs
, FS
, NULL
);
1113 if ((flags
& GIT_ITERATOR_IGNORE_CASE
) != 0)
1114 fi
->base
.flags
|= GIT_ITERATOR_IGNORE_CASE
;
1116 if (git_buf_sets(&fi
->path
, root
) < 0 || git_path_to_dir(&fi
->path
) < 0) {
1120 fi
->root_len
= fi
->path
.size
;
1122 if ((error
= fs_iterator__expand_dir(fi
)) < 0) {
1123 if (error
!= GIT_ENOTFOUND
)
1128 *out
= (git_iterator
*)fi
;
1132 git_iterator_free((git_iterator
*)fi
);
1137 #define WORKDIR_MAX_DEPTH 100
1139 typedef struct workdir_iterator_frame workdir_iterator_frame
;
1140 struct workdir_iterator_frame
{
1141 workdir_iterator_frame
*next
;
1148 git_iterator_callbacks cb
;
1149 workdir_iterator_frame
*stack
;
1150 git_ignores ignores
;
1151 git_index_entry entry
;
1158 GIT_INLINE(bool) path_is_dotgit(const git_path_with_stat
*ps
)
1163 const char *path
= ps
->path
;
1164 size_t len
= ps
->path_len
;
1168 if (path
[len
- 1] == '/')
1170 if (tolower(path
[len
- 1]) != 't' ||
1171 tolower(path
[len
- 2]) != 'i' ||
1172 tolower(path
[len
- 3]) != 'g' ||
1173 tolower(path
[len
- 4]) != '.')
1175 return (len
== 4 || path
[len
- 5] == '/');
1179 static workdir_iterator_frame
*workdir_iterator__alloc_frame(
1180 workdir_iterator
*wi
)
1182 workdir_iterator_frame
*wf
= git__calloc(1, sizeof(workdir_iterator_frame
));
1183 git_vector_cmp entry_compare
= CASESELECT(
1184 iterator__ignore_case(wi
),
1185 git_path_with_stat_cmp_icase
, git_path_with_stat_cmp
);
1190 if (git_vector_init(&wf
->entries
, 0, entry_compare
) != 0) {
1198 static void workdir_iterator__free_frame(workdir_iterator_frame
*wf
)
1201 git_path_with_stat
*path
;
1203 git_vector_foreach(&wf
->entries
, i
, path
)
1205 git_vector_free(&wf
->entries
);
1209 static int workdir_iterator__update_entry(workdir_iterator
*wi
);
1211 static int workdir_iterator__entry_cmp(const void *i
, const void *item
)
1213 const workdir_iterator
*wi
= (const workdir_iterator
*)i
;
1214 const git_path_with_stat
*ps
= item
;
1215 return wi
->base
.prefixcomp(wi
->base
.start
, ps
->path
);
1218 static void workdir_iterator__seek_frame_start(
1219 workdir_iterator
*wi
, workdir_iterator_frame
*wf
)
1225 git_vector_bsearch2(
1226 &wf
->index
, &wf
->entries
, workdir_iterator__entry_cmp
, wi
);
1230 if (path_is_dotgit(git_vector_get(&wf
->entries
, wf
->index
)))
1234 static int workdir_iterator__expand_dir(workdir_iterator
*wi
)
1237 workdir_iterator_frame
*wf
;
1239 wf
= workdir_iterator__alloc_frame(wi
);
1240 GITERR_CHECK_ALLOC(wf
);
1242 error
= git_path_dirload_with_stat(
1243 wi
->path
.ptr
, wi
->root_len
, iterator__ignore_case(wi
),
1244 wi
->base
.start
, wi
->base
.end
, &wf
->entries
);
1246 if (error
< 0 || wf
->entries
.length
== 0) {
1247 workdir_iterator__free_frame(wf
);
1248 return GIT_ENOTFOUND
;
1251 if (++(wi
->depth
) > WORKDIR_MAX_DEPTH
) {
1252 giterr_set(GITERR_REPOSITORY
,
1253 "Working directory is too deep (%d)", wi
->depth
);
1254 workdir_iterator__free_frame(wf
);
1258 workdir_iterator__seek_frame_start(wi
, wf
);
1260 /* only push new ignores if this is not top level directory */
1261 if (wi
->stack
!= NULL
) {
1262 ssize_t slash_pos
= git_buf_rfind_next(&wi
->path
, '/');
1263 (void)git_ignore__push_dir(&wi
->ignores
, &wi
->path
.ptr
[slash_pos
+ 1]);
1266 wf
->next
= wi
->stack
;
1269 return workdir_iterator__update_entry(wi
);
1272 static int workdir_iterator__current(
1273 const git_index_entry
**entry
, git_iterator
*self
)
1275 workdir_iterator
*wi
= (workdir_iterator
*)self
;
1277 *entry
= (wi
->entry
.path
== NULL
) ? NULL
: &wi
->entry
;
1281 static int workdir_iterator__at_end(git_iterator
*self
)
1283 return (((workdir_iterator
*)self
)->entry
.path
== NULL
);
1286 static int workdir_iterator__advance_into(
1287 const git_index_entry
**entry
, git_iterator
*iter
)
1290 workdir_iterator
*wi
= (workdir_iterator
*)iter
;
1292 iterator__clear_entry(entry
);
1294 /* workdir iterator will allow you to explicitly advance into a
1295 * commit/submodule (as well as a tree) to avoid some cases where an
1296 * entry is mislabeled as a submodule in the working directory
1298 if (wi
->entry
.path
!= NULL
&&
1299 (wi
->entry
.mode
== GIT_FILEMODE_TREE
||
1300 wi
->entry
.mode
== GIT_FILEMODE_COMMIT
))
1301 /* returns GIT_ENOTFOUND if the directory is empty */
1302 error
= workdir_iterator__expand_dir(wi
);
1304 if (!error
&& entry
)
1305 error
= workdir_iterator__current(entry
, iter
);
1310 static int workdir_iterator__advance(
1311 const git_index_entry
**entry
, git_iterator
*self
)
1314 workdir_iterator
*wi
= (workdir_iterator
*)self
;
1315 workdir_iterator_frame
*wf
;
1316 git_path_with_stat
*next
;
1318 /* given include_trees & autoexpand, we might have to go into a tree */
1319 if (iterator__do_autoexpand(wi
) &&
1320 wi
->entry
.path
!= NULL
&&
1321 wi
->entry
.mode
== GIT_FILEMODE_TREE
)
1323 error
= workdir_iterator__advance_into(entry
, self
);
1325 /* continue silently past empty directories if autoexpanding */
1326 if (error
!= GIT_ENOTFOUND
)
1335 while (wi
->entry
.path
!= NULL
) {
1337 next
= git_vector_get(&wf
->entries
, ++wf
->index
);
1340 /* match git's behavior of ignoring anything named ".git" */
1341 if (path_is_dotgit(next
))
1343 /* else found a good entry */
1347 /* pop stack if anything is left to pop */
1349 memset(&wi
->entry
, 0, sizeof(wi
->entry
));
1353 wi
->stack
= wf
->next
;
1355 workdir_iterator__free_frame(wf
);
1356 git_ignore__pop_dir(&wi
->ignores
);
1359 error
= workdir_iterator__update_entry(wi
);
1361 if (!error
&& entry
!= NULL
)
1362 error
= workdir_iterator__current(entry
, self
);
1367 static int workdir_iterator__seek(git_iterator
*self
, const char *prefix
)
1371 /* pop stack until matching prefix */
1372 /* find prefix item in current frame */
1373 /* push subdirectories as deep as possible while matching */
1377 static int workdir_iterator__reset(
1378 git_iterator
*self
, const char *start
, const char *end
)
1380 workdir_iterator
*wi
= (workdir_iterator
*)self
;
1382 while (wi
->stack
!= NULL
&& wi
->stack
->next
!= NULL
) {
1383 workdir_iterator_frame
*wf
= wi
->stack
;
1384 wi
->stack
= wf
->next
;
1385 workdir_iterator__free_frame(wf
);
1386 git_ignore__pop_dir(&wi
->ignores
);
1390 if (iterator__reset_range(self
, start
, end
) < 0)
1393 workdir_iterator__seek_frame_start(wi
, wi
->stack
);
1395 return workdir_iterator__update_entry(wi
);
1398 static void workdir_iterator__free(git_iterator
*self
)
1400 workdir_iterator
*wi
= (workdir_iterator
*)self
;
1402 while (wi
->stack
!= NULL
) {
1403 workdir_iterator_frame
*wf
= wi
->stack
;
1404 wi
->stack
= wf
->next
;
1405 workdir_iterator__free_frame(wf
);
1408 git_ignore__free(&wi
->ignores
);
1409 git_buf_free(&wi
->path
);
1412 static int workdir_iterator__update_entry(workdir_iterator
*wi
)
1415 git_path_with_stat
*ps
=
1416 git_vector_get(&wi
->stack
->entries
, wi
->stack
->index
);
1418 git_buf_truncate(&wi
->path
, wi
->root_len
);
1419 memset(&wi
->entry
, 0, sizeof(wi
->entry
));
1424 /* skip over .git entries */
1425 if (path_is_dotgit(ps
))
1426 return workdir_iterator__advance(NULL
, (git_iterator
*)wi
);
1428 if (git_buf_put(&wi
->path
, ps
->path
, ps
->path_len
) < 0)
1431 if (iterator__past_end(wi
, wi
->path
.ptr
+ wi
->root_len
))
1434 wi
->entry
.path
= ps
->path
;
1436 wi
->is_ignored
= -1;
1438 git_index_entry__init_from_stat(&wi
->entry
, &ps
->st
);
1440 /* need different mode here to keep directories during iteration */
1441 wi
->entry
.mode
= git_futils_canonical_mode(ps
->st
.st_mode
);
1443 /* if this is a file type we don't handle, treat as ignored */
1444 if (wi
->entry
.mode
== 0) {
1449 /* if this isn't a tree, then we're done */
1450 if (wi
->entry
.mode
!= GIT_FILEMODE_TREE
)
1453 /* detect submodules */
1454 error
= git_submodule_lookup(NULL
, wi
->base
.repo
, wi
->entry
.path
);
1455 if (error
== GIT_ENOTFOUND
)
1458 if (error
== GIT_EEXISTS
) /* if contains .git, treat as untracked submod */
1461 /* if submodule, mark as GITLINK and remove trailing slash */
1463 size_t len
= strlen(wi
->entry
.path
);
1464 assert(wi
->entry
.path
[len
- 1] == '/');
1465 wi
->entry
.path
[len
- 1] = '\0';
1466 wi
->entry
.mode
= S_IFGITLINK
;
1470 if (iterator__include_trees(wi
))
1473 return workdir_iterator__advance(NULL
, (git_iterator
*)wi
);
1476 int git_iterator_for_workdir(
1477 git_iterator
**iter
,
1478 git_repository
*repo
,
1479 git_iterator_flag_t flags
,
1484 workdir_iterator
*wi
;
1486 assert(iter
&& repo
);
1488 if ((error
= git_repository__ensure_not_bare(
1489 repo
, "scan working directory")) < 0)
1492 ITERATOR_BASE_INIT(wi
, workdir
, WORKDIR
, repo
);
1494 if ((error
= iterator__update_ignore_case((git_iterator
*)wi
, flags
)) < 0)
1497 if (git_buf_sets(&wi
->path
, git_repository_workdir(repo
)) < 0 ||
1498 git_path_to_dir(&wi
->path
) < 0 ||
1499 git_ignore__for_path(repo
, "", &wi
->ignores
) < 0)
1504 wi
->root_len
= wi
->path
.size
;
1506 if ((error
= workdir_iterator__expand_dir(wi
)) < 0) {
1507 if (error
!= GIT_ENOTFOUND
)
1512 *iter
= (git_iterator
*)wi
;
1516 git_iterator_free((git_iterator
*)wi
);
1521 void git_iterator_free(git_iterator
*iter
)
1526 iter
->cb
->free(iter
);
1528 git__free(iter
->start
);
1529 git__free(iter
->end
);
1531 memset(iter
, 0, sizeof(*iter
));
1536 int git_iterator_set_ignore_case(git_iterator
*iter
, bool ignore_case
)
1538 bool desire_ignore_case
= (ignore_case
!= 0);
1540 if (iterator__ignore_case(iter
) == desire_ignore_case
)
1543 if (iter
->type
== GIT_ITERATOR_TYPE_EMPTY
) {
1544 if (desire_ignore_case
)
1545 iter
->flags
|= GIT_ITERATOR_IGNORE_CASE
;
1547 iter
->flags
&= ~GIT_ITERATOR_IGNORE_CASE
;
1549 giterr_set(GITERR_INVALID
,
1550 "Cannot currently set ignore case on non-empty iterators");
1557 git_index
*git_iterator_get_index(git_iterator
*iter
)
1559 if (iter
->type
== GIT_ITERATOR_TYPE_INDEX
)
1560 return ((index_iterator
*)iter
)->index
;
1564 int git_iterator_current_tree_entry(
1565 const git_tree_entry
**tree_entry
, git_iterator
*iter
)
1567 if (iter
->type
!= GIT_ITERATOR_TYPE_TREE
)
1570 tree_iterator_frame
*tf
= ((tree_iterator
*)iter
)->head
;
1571 *tree_entry
= (tf
->current
< tf
->n_entries
) ?
1572 tf
->entries
[tf
->current
]->te
: NULL
;
1578 int git_iterator_current_parent_tree(
1579 const git_tree
**tree_ptr
,
1581 const char *parent_path
)
1583 tree_iterator
*ti
= (tree_iterator
*)iter
;
1584 tree_iterator_frame
*tf
;
1585 const char *scan
= parent_path
;
1586 const git_tree_entry
*te
;
1590 if (iter
->type
!= GIT_ITERATOR_TYPE_TREE
)
1593 for (tf
= ti
->root
; *scan
; ) {
1594 if (!(tf
= tf
->down
) ||
1595 tf
->current
>= tf
->n_entries
||
1596 !(te
= tf
->entries
[tf
->current
]->te
) ||
1597 ti
->strncomp(scan
, te
->filename
, te
->filename_len
) != 0)
1600 scan
+= te
->filename_len
;
1605 *tree_ptr
= tf
->entries
[tf
->current
]->tree
;
1609 bool git_iterator_current_is_ignored(git_iterator
*iter
)
1611 workdir_iterator
*wi
= (workdir_iterator
*)iter
;
1613 if (iter
->type
!= GIT_ITERATOR_TYPE_WORKDIR
)
1616 if (wi
->is_ignored
!= -1)
1617 return (bool)(wi
->is_ignored
!= 0);
1619 if (git_ignore__lookup(&wi
->ignores
, wi
->entry
.path
, &wi
->is_ignored
) < 0)
1620 wi
->is_ignored
= true;
1622 return (bool)wi
->is_ignored
;
1625 int git_iterator_cmp(git_iterator
*iter
, const char *path_prefix
)
1627 const git_index_entry
*entry
;
1629 /* a "done" iterator is after every prefix */
1630 if (git_iterator_current(&entry
, iter
) < 0 || entry
== NULL
)
1633 /* a NULL prefix is after any valid iterator */
1637 return iter
->prefixcomp(entry
->path
, path_prefix
);
1640 int git_iterator_current_workdir_path(git_buf
**path
, git_iterator
*iter
)
1642 workdir_iterator
*wi
= (workdir_iterator
*)iter
;
1644 if (iter
->type
!= GIT_ITERATOR_TYPE_WORKDIR
|| !wi
->entry
.path
)