src/iterator.c

   1 /*
   2  * Copyright (C) the libgit2 contributors. All rights reserved.
   3  *
   4  * This file is part of libgit2, distributed under the GNU GPL v2 with
   5  * a Linking Exception. For full terms see the included COPYING file.
   6  */
   7
   8 #include "iterator.h"
   9
  10 #include "tree.h"
  11 #include "index.h"
  12
  13 #define GIT_ITERATOR_FIRST_ACCESS   (1 << 15)
  14 #define GIT_ITERATOR_HONOR_IGNORES  (1 << 16)
  15 #define GIT_ITERATOR_IGNORE_DOT_GIT (1 << 17)
  16
  17 #define iterator__flag(I,F) ((((git_iterator *)(I))->flags & GIT_ITERATOR_ ## F) != 0)
  18 #define iterator__ignore_case(I)       iterator__flag(I,IGNORE_CASE)
  19 #define iterator__include_trees(I)     iterator__flag(I,INCLUDE_TREES)
  20 #define iterator__dont_autoexpand(I)   iterator__flag(I,DONT_AUTOEXPAND)
  21 #define iterator__do_autoexpand(I)    !iterator__flag(I,DONT_AUTOEXPAND)
  22 #define iterator__include_conflicts(I) iterator__flag(I,INCLUDE_CONFLICTS)
  23 #define iterator__has_been_accessed(I) iterator__flag(I,FIRST_ACCESS)
  24 #define iterator__honor_ignores(I)     iterator__flag(I,HONOR_IGNORES)
  25 #define iterator__ignore_dot_git(I)    iterator__flag(I,IGNORE_DOT_GIT)
  26 #define iterator__descend_symlinks(I)  iterator__flag(I,DESCEND_SYMLINKS)
  27
  28
  29 static void iterator_set_ignore_case(git_iterator *iter, bool ignore_case)
  30 {
  31         if (ignore_case)
  32                 iter->flags |= GIT_ITERATOR_IGNORE_CASE;
  33         else
  34                 iter->flags &= ~GIT_ITERATOR_IGNORE_CASE;
  35
  36         iter->strcomp = ignore_case ? git__strcasecmp : git__strcmp;
  37         iter->strncomp = ignore_case ? git__strncasecmp : git__strncmp;
  38         iter->prefixcomp = ignore_case ? git__prefixcmp_icase : git__prefixcmp;
  39         iter->entry_srch = ignore_case ? git_index_entry_isrch : git_index_entry_srch;
  40
  41         git_vector_set_cmp(&iter->pathlist, (git_vector_cmp)iter->strcomp);
  42 }
  43
  44 static int iterator_range_init(
  45         git_iterator *iter, const char *start, const char *end)
  46 {
  47         if (start && *start) {
  48                 iter->start = git__strdup(start);
  49                 GIT_ERROR_CHECK_ALLOC(iter->start);
  50
  51                 iter->start_len = strlen(iter->start);
  52         }
  53
  54         if (end && *end) {
  55                 iter->end = git__strdup(end);
  56                 GIT_ERROR_CHECK_ALLOC(iter->end);
  57
  58                 iter->end_len = strlen(iter->end);
  59         }
  60
  61         iter->started = (iter->start == NULL);
  62         iter->ended = false;
  63
  64         return 0;
  65 }
  66
  67 static void iterator_range_free(git_iterator *iter)
  68 {
  69         if (iter->start) {
  70                 git__free(iter->start);
  71                 iter->start = NULL;
  72                 iter->start_len = 0;
  73         }
  74
  75         if (iter->end) {
  76                 git__free(iter->end);
  77                 iter->end = NULL;
  78                 iter->end_len = 0;
  79         }
  80 }
  81
  82 static int iterator_reset_range(
  83         git_iterator *iter, const char *start, const char *end)
  84 {
  85         iterator_range_free(iter);
  86         return iterator_range_init(iter, start, end);
  87 }
  88
  89 static int iterator_pathlist_init(git_iterator *iter, git_strarray *pathlist)
  90 {
  91         size_t i;
  92
  93         if (git_vector_init(&iter->pathlist, pathlist->count, NULL) < 0)
  94                 return -1;
  95
  96         for (i = 0; i < pathlist->count; i++) {
  97                 if (!pathlist->strings[i])
  98                         continue;
  99
 100                 if (git_vector_insert(&iter->pathlist, pathlist->strings[i]) < 0)
 101                         return -1;
 102         }
 103
 104         return 0;
 105 }
 106
 107 static int iterator_init_common(
 108         git_iterator *iter,
 109         git_repository *repo,
 110         git_index *index,
 111         git_iterator_options *given_opts)
 112 {
 113         static git_iterator_options default_opts = GIT_ITERATOR_OPTIONS_INIT;
 114         git_iterator_options *options = given_opts ? given_opts : &default_opts;
 115         bool ignore_case;
 116         int precompose;
 117         int error;
 118
 119         iter->repo = repo;
 120         iter->index = index;
 121         iter->flags = options->flags;
 122
 123         if ((iter->flags & GIT_ITERATOR_IGNORE_CASE) != 0) {
 124                 ignore_case = true;
 125         } else if ((iter->flags & GIT_ITERATOR_DONT_IGNORE_CASE) != 0) {
 126                 ignore_case = false;
 127         } else if (repo) {
 128                 git_index *index;
 129
 130                 if ((error = git_repository_index__weakptr(&index, iter->repo)) < 0)
 131                         return error;
 132
 133                 ignore_case = !!index->ignore_case;
 134
 135                 if (ignore_case == 1)
 136                         iter->flags |= GIT_ITERATOR_IGNORE_CASE;
 137                 else
 138                         iter->flags |= GIT_ITERATOR_DONT_IGNORE_CASE;
 139         } else {
 140                 ignore_case = false;
 141         }
 142
 143         /* try to look up precompose and set flag if appropriate */
 144         if (repo &&
 145                 (iter->flags & GIT_ITERATOR_PRECOMPOSE_UNICODE) == 0 &&
 146                 (iter->flags & GIT_ITERATOR_DONT_PRECOMPOSE_UNICODE) == 0) {
 147
 148                 if (git_repository__configmap_lookup(&precompose, repo, GIT_CONFIGMAP_PRECOMPOSE) < 0)
 149                         git_error_clear();
 150                 else if (precompose)
 151                         iter->flags |= GIT_ITERATOR_PRECOMPOSE_UNICODE;
 152         }
 153
 154         if ((iter->flags & GIT_ITERATOR_DONT_AUTOEXPAND))
 155                 iter->flags |= GIT_ITERATOR_INCLUDE_TREES;
 156
 157         if ((error = iterator_range_init(iter, options->start, options->end)) < 0 ||
 158                 (error = iterator_pathlist_init(iter, &options->pathlist)) < 0)
 159                 return error;
 160
 161         iterator_set_ignore_case(iter, ignore_case);
 162         return 0;
 163 }
 164
 165 static void iterator_clear(git_iterator *iter)
 166 {
 167         iter->started = false;
 168         iter->ended = false;
 169         iter->stat_calls = 0;
 170         iter->pathlist_walk_idx = 0;
 171         iter->flags &= ~GIT_ITERATOR_FIRST_ACCESS;
 172 }
 173
 174 GIT_INLINE(bool) iterator_has_started(
 175         git_iterator *iter, const char *path, bool is_submodule)
 176 {
 177         size_t path_len;
 178
 179         if (iter->start == NULL || iter->started == true)
 180                 return true;
 181
 182         /* the starting path is generally a prefix - we have started once we
 183          * are prefixed by this path
 184          */
 185         iter->started = (iter->prefixcomp(path, iter->start) >= 0);
 186
 187         if (iter->started)
 188                 return true;
 189
 190         path_len = strlen(path);
 191
 192         /* if, however, we are a submodule, then we support `start` being
 193          * suffixed with a `/` for crazy legacy reasons.  match `submod`
 194          * with a start path of `submod/`.
 195          */
 196         if (is_submodule && iter->start_len && path_len == iter->start_len - 1 &&
 197                 iter->start[iter->start_len-1] == '/')
 198                 return true;
 199
 200         /* if, however, our current path is a directory, and our starting path
 201          * is _beneath_ that directory, then recurse into the directory (even
 202          * though we have not yet "started")
 203          */
 204         if (path_len > 0 && path[path_len-1] == '/' &&
 205                 iter->strncomp(path, iter->start, path_len) == 0)
 206                 return true;
 207
 208         return false;
 209 }
 210
 211 GIT_INLINE(bool) iterator_has_ended(git_iterator *iter, const char *path)
 212 {
 213         if (iter->end == NULL)
 214                 return false;
 215         else if (iter->ended)
 216                 return true;
 217
 218         iter->ended = (iter->prefixcomp(path, iter->end) > 0);
 219         return iter->ended;
 220 }
 221
 222 /* walker for the index and tree iterator that allows it to walk the sorted
 223  * pathlist entries alongside sorted iterator entries.
 224  */
 225 static bool iterator_pathlist_next_is(git_iterator *iter, const char *path)
 226 {
 227         char *p;
 228         size_t path_len, p_len, cmp_len, i;
 229         int cmp;
 230
 231         if (iter->pathlist.length == 0)
 232                 return true;
 233
 234         git_vector_sort(&iter->pathlist);
 235
 236         path_len = strlen(path);
 237
 238         /* for comparison, drop the trailing slash on the current '/' */
 239         if (path_len && path[path_len-1] == '/')
 240                 path_len--;
 241
 242         for (i = iter->pathlist_walk_idx; i < iter->pathlist.length; i++) {
 243                 p = iter->pathlist.contents[i];
 244                 p_len = strlen(p);
 245
 246                 if (p_len && p[p_len-1] == '/')
 247                         p_len--;
 248
 249                 cmp_len = min(path_len, p_len);
 250
 251                 /* see if the pathlist entry is a prefix of this path */
 252                 cmp = iter->strncomp(p, path, cmp_len);
 253
 254                 /* prefix match - see if there's an exact match, or if we were
 255                  * given a path that matches the directory
 256                  */
 257                 if (cmp == 0) {
 258                         /* if this pathlist entry is not suffixed with a '/' then
 259                          * it matches a path that is a file or a directory.
 260                          * (eg, pathlist = "foo" and path is "foo" or "foo/" or
 261                          * "foo/something")
 262                          */
 263                         if (p[cmp_len] == '\0' &&
 264                                 (path[cmp_len] == '\0' || path[cmp_len] == '/'))
 265                                 return true;
 266
 267                         /* if this pathlist entry _is_ suffixed with a '/' then
 268                          * it matches only paths that are directories.
 269                          * (eg, pathlist = "foo/" and path is "foo/" or "foo/something")
 270                          */
 271                         if (p[cmp_len] == '/' && path[cmp_len] == '/')
 272                                 return true;
 273                 }
 274
 275                 /* this pathlist entry sorts before the given path, try the next */
 276                 else if (cmp < 0) {
 277                         iter->pathlist_walk_idx++;
 278                         continue;
 279                 }
 280
 281                 /* this pathlist sorts after the given path, no match. */
 282                 else if (cmp > 0) {
 283                         break;
 284                 }
 285         }
 286
 287         return false;
 288 }
 289
 290 typedef enum {
 291         ITERATOR_PATHLIST_NONE = 0,
 292         ITERATOR_PATHLIST_IS_FILE = 1,
 293         ITERATOR_PATHLIST_IS_DIR = 2,
 294         ITERATOR_PATHLIST_IS_PARENT = 3,
 295         ITERATOR_PATHLIST_FULL = 4,
 296 } iterator_pathlist_search_t;
 297
 298 static iterator_pathlist_search_t iterator_pathlist_search(
 299         git_iterator *iter, const char *path, size_t path_len)
 300 {
 301         const char *p;
 302         size_t idx;
 303         int error;
 304
 305         if (iter->pathlist.length == 0)
 306                 return ITERATOR_PATHLIST_FULL;
 307
 308         git_vector_sort(&iter->pathlist);
 309
 310         error = git_vector_bsearch2(&idx, &iter->pathlist,
 311                 (git_vector_cmp)iter->strcomp, path);
 312
 313         /* the given path was found in the pathlist.  since the pathlist only
 314          * matches directories when they're suffixed with a '/', analyze the
 315          * path string to determine whether it's a directory or not.
 316          */
 317         if (error == 0) {
 318                 if (path_len && path[path_len-1] == '/')
 319                         return ITERATOR_PATHLIST_IS_DIR;
 320
 321                 return ITERATOR_PATHLIST_IS_FILE;
 322         }
 323
 324         /* at this point, the path we're examining may be a directory (though we
 325          * don't know that yet, since we're avoiding a stat unless it's necessary)
 326          * so walk the pathlist looking for the given path with a '/' after it,
 327          */
 328         while ((p = git_vector_get(&iter->pathlist, idx)) != NULL) {
 329                 if (iter->prefixcomp(p, path) != 0)
 330                         break;
 331
 332                 /* an exact match would have been matched by the bsearch above */
 333                 assert(p[path_len]);
 334
 335                 /* is this a literal directory entry (eg `foo/`) or a file beneath */
 336                 if (p[path_len] == '/') {
 337                         return (p[path_len+1] == '\0') ?
 338                                 ITERATOR_PATHLIST_IS_DIR :
 339                                 ITERATOR_PATHLIST_IS_PARENT;
 340                 }
 341
 342                 if (p[path_len] > '/')
 343                         break;
 344
 345                 idx++;
 346         }
 347
 348         return ITERATOR_PATHLIST_NONE;
 349 }
 350
 351 /* Empty iterator */
 352
 353 static int empty_iterator_noop(const git_index_entry **e, git_iterator *i)
 354 {
 355         GIT_UNUSED(i);
 356
 357         if (e)
 358                 *e = NULL;
 359
 360         return GIT_ITEROVER;
 361 }
 362
 363 static int empty_iterator_advance_over(
 364         const git_index_entry **e,
 365         git_iterator_status_t *s,
 366         git_iterator *i)
 367 {
 368         *s = GIT_ITERATOR_STATUS_EMPTY;
 369         return empty_iterator_noop(e, i);
 370 }
 371
 372 static int empty_iterator_reset(git_iterator *i)
 373 {
 374         GIT_UNUSED(i);
 375         return 0;
 376 }
 377
 378 static void empty_iterator_free(git_iterator *i)
 379 {
 380         GIT_UNUSED(i);
 381 }
 382
 383 typedef struct {
 384         git_iterator base;
 385         git_iterator_callbacks cb;
 386 } empty_iterator;
 387
 388 int git_iterator_for_nothing(
 389         git_iterator **out,
 390         git_iterator_options *options)
 391 {
 392         empty_iterator *iter;
 393
 394         static git_iterator_callbacks callbacks = {
 395                 empty_iterator_noop,
 396                 empty_iterator_noop,
 397                 empty_iterator_noop,
 398                 empty_iterator_advance_over,
 399                 empty_iterator_reset,
 400                 empty_iterator_free
 401         };
 402
 403         *out = NULL;
 404
 405         iter = git__calloc(1, sizeof(empty_iterator));
 406         GIT_ERROR_CHECK_ALLOC(iter);
 407
 408         iter->base.type = GIT_ITERATOR_EMPTY;
 409         iter->base.cb = &callbacks;
 410         iter->base.flags = options->flags;
 411
 412         *out = &iter->base;
 413         return 0;
 414 }
 415
 416 /* Tree iterator */
 417
 418 typedef struct {
 419         git_tree_entry *tree_entry;
 420         const char *parent_path;
 421 } tree_iterator_entry;
 422
 423 typedef struct {
 424         git_tree *tree;
 425
 426         /* path to this particular frame (folder) */
 427         git_buf path;
 428
 429         /* a sorted list of the entries for this frame (folder), these are
 430          * actually pointers to the iterator's entry pool.
 431          */
 432         git_vector entries;
 433         tree_iterator_entry *current;
 434
 435         size_t next_idx;
 436
 437         /* on case insensitive iterations, we also have an array of other
 438          * paths that were case insensitively equal to this one, and their
 439          * tree objects.  we have coalesced the tree entries into this frame.
 440          * a child `tree_iterator_entry` will contain a pointer to its actual
 441          * parent path.
 442          */
 443         git_vector similar_trees;
 444         git_array_t(git_buf) similar_paths;
 445 } tree_iterator_frame;
 446
 447 typedef struct {
 448         git_iterator base;
 449         git_tree *root;
 450         git_array_t(tree_iterator_frame) frames;
 451
 452         git_index_entry entry;
 453         git_buf entry_path;
 454
 455         /* a pool of entries to reduce the number of allocations */
 456         git_pool entry_pool;
 457 } tree_iterator;
 458
 459 GIT_INLINE(tree_iterator_frame *) tree_iterator_parent_frame(
 460         tree_iterator *iter)
 461 {
 462         return iter->frames.size > 1 ?
 463                 &iter->frames.ptr[iter->frames.size-2] : NULL;
 464 }
 465
 466 GIT_INLINE(tree_iterator_frame *) tree_iterator_current_frame(
 467         tree_iterator *iter)
 468 {
 469         return iter->frames.size ? &iter->frames.ptr[iter->frames.size-1] : NULL;
 470 }
 471
 472 GIT_INLINE(int) tree_entry_cmp(
 473         const git_tree_entry *a, const git_tree_entry *b, bool icase)
 474 {
 475         return git_path_cmp(
 476                 a->filename, a->filename_len, a->attr == GIT_FILEMODE_TREE,
 477                 b->filename, b->filename_len, b->attr == GIT_FILEMODE_TREE,
 478                 icase ? git__strncasecmp : git__strncmp);
 479 }
 480
 481 GIT_INLINE(int) tree_iterator_entry_cmp_icase(
 482         const void *ptr_a, const void *ptr_b)
 483 {
 484         const tree_iterator_entry *a = (const tree_iterator_entry *)ptr_a;
 485         const tree_iterator_entry *b = (const tree_iterator_entry *)ptr_b;
 486
 487         return tree_entry_cmp(a->tree_entry, b->tree_entry, true);
 488 }
 489
 490 static int tree_iterator_entry_sort_icase(const void *ptr_a, const void *ptr_b)
 491 {
 492         const tree_iterator_entry *a = (const tree_iterator_entry *)ptr_a;
 493         const tree_iterator_entry *b = (const tree_iterator_entry *)ptr_b;
 494
 495         int c = tree_entry_cmp(a->tree_entry, b->tree_entry, true);
 496
 497         /* stabilize the sort order for filenames that are (case insensitively)
 498          * the same by examining the parent path (case sensitively) before
 499          * falling back to a case sensitive sort of the filename.
 500          */
 501         if (!c && a->parent_path != b->parent_path)
 502                 c = git__strcmp(a->parent_path, b->parent_path);
 503
 504         if (!c)
 505                 c = tree_entry_cmp(a->tree_entry, b->tree_entry, false);
 506
 507         return c;
 508 }
 509
 510 static int tree_iterator_compute_path(
 511         git_buf *out,
 512         tree_iterator_entry *entry)
 513 {
 514         git_buf_clear(out);
 515
 516         if (entry->parent_path)
 517                 git_buf_joinpath(out, entry->parent_path, entry->tree_entry->filename);
 518         else
 519                 git_buf_puts(out, entry->tree_entry->filename);
 520
 521         if (git_tree_entry__is_tree(entry->tree_entry))
 522                 git_buf_putc(out, '/');
 523
 524         if (git_buf_oom(out))
 525                 return -1;
 526
 527         return 0;
 528 }
 529
 530 static int tree_iterator_frame_init(
 531         tree_iterator *iter,
 532         git_tree *tree,
 533         tree_iterator_entry *frame_entry)
 534 {
 535         tree_iterator_frame *new_frame = NULL;
 536         tree_iterator_entry *new_entry;
 537         git_tree *dup = NULL;
 538         git_tree_entry *tree_entry;
 539         git_vector_cmp cmp;
 540         size_t i;
 541         int error = 0;
 542
 543         new_frame = git_array_alloc(iter->frames);
 544         GIT_ERROR_CHECK_ALLOC(new_frame);
 545
 546         if ((error = git_tree_dup(&dup, tree)) < 0)
 547                 goto done;
 548
 549         memset(new_frame, 0x0, sizeof(tree_iterator_frame));
 550         new_frame->tree = dup;
 551
 552         if (frame_entry &&
 553             (error = tree_iterator_compute_path(&new_frame->path, frame_entry)) < 0)
 554                 goto done;
 555
 556         cmp = iterator__ignore_case(&iter->base) ?
 557                 tree_iterator_entry_sort_icase : NULL;
 558
 559         if ((error = git_vector_init(&new_frame->entries,
 560                                      dup->entries.size, cmp)) < 0)
 561                 goto done;
 562
 563         git_array_foreach(dup->entries, i, tree_entry) {
 564                 if ((new_entry = git_pool_malloc(&iter->entry_pool, 1)) == NULL) {
 565                         git_error_set_oom();
 566                         error = -1;
 567                         goto done;
 568                 }
 569
 570                 new_entry->tree_entry = tree_entry;
 571                 new_entry->parent_path = new_frame->path.ptr;
 572
 573                 if ((error = git_vector_insert(&new_frame->entries, new_entry)) < 0)
 574                         goto done;
 575         }
 576
 577         git_vector_set_sorted(&new_frame->entries,
 578                 !iterator__ignore_case(&iter->base));
 579
 580 done:
 581         if (error < 0) {
 582                 git_tree_free(dup);
 583                 git_array_pop(iter->frames);
 584         }
 585
 586         return error;
 587 }
 588
 589 GIT_INLINE(tree_iterator_entry *) tree_iterator_current_entry(
 590         tree_iterator_frame *frame)
 591 {
 592         return frame->current;
 593 }
 594
 595 GIT_INLINE(int) tree_iterator_frame_push_neighbors(
 596         tree_iterator *iter,
 597         tree_iterator_frame *parent_frame,
 598         tree_iterator_frame *frame,
 599         const char *filename)
 600 {
 601         tree_iterator_entry *entry, *new_entry;
 602         git_tree *tree = NULL;
 603         git_tree_entry *tree_entry;
 604         git_buf *path;
 605         size_t new_size, i;
 606         int error = 0;
 607
 608         while (parent_frame->next_idx < parent_frame->entries.length) {
 609                 entry = parent_frame->entries.contents[parent_frame->next_idx];
 610
 611                 if (strcasecmp(filename, entry->tree_entry->filename) != 0)
 612                         break;
 613
 614                 if ((error = git_tree_lookup(&tree,
 615                         iter->base.repo, entry->tree_entry->oid)) < 0)
 616                         break;
 617
 618                 if (git_vector_insert(&parent_frame->similar_trees, tree) < 0)
 619                         break;
 620
 621                 path = git_array_alloc(parent_frame->similar_paths);
 622                 GIT_ERROR_CHECK_ALLOC(path);
 623
 624                 memset(path, 0, sizeof(git_buf));
 625
 626                 if ((error = tree_iterator_compute_path(path, entry)) < 0)
 627                         break;
 628
 629                 GIT_ERROR_CHECK_ALLOC_ADD(&new_size,
 630                         frame->entries.length, tree->entries.size);
 631                 git_vector_size_hint(&frame->entries, new_size);
 632
 633                 git_array_foreach(tree->entries, i, tree_entry) {
 634                         new_entry = git_pool_malloc(&iter->entry_pool, 1);
 635                         GIT_ERROR_CHECK_ALLOC(new_entry);
 636
 637                         new_entry->tree_entry = tree_entry;
 638                         new_entry->parent_path = path->ptr;
 639
 640                         if ((error = git_vector_insert(&frame->entries, new_entry)) < 0)
 641                                 break;
 642                 }
 643
 644                 if (error)
 645                         break;
 646
 647                 parent_frame->next_idx++;
 648         }
 649
 650         return error;
 651 }
 652
 653 GIT_INLINE(int) tree_iterator_frame_push(
 654         tree_iterator *iter, tree_iterator_entry *entry)
 655 {
 656         tree_iterator_frame *parent_frame, *frame;
 657         git_tree *tree = NULL;
 658         int error;
 659
 660         if ((error = git_tree_lookup(&tree,
 661                         iter->base.repo, entry->tree_entry->oid)) < 0 ||
 662                 (error = tree_iterator_frame_init(iter, tree, entry)) < 0)
 663                 goto done;
 664
 665         parent_frame = tree_iterator_parent_frame(iter);
 666         frame = tree_iterator_current_frame(iter);
 667
 668         /* if we're case insensitive, then we may have another directory that
 669          * is (case insensitively) equal to this one.  coalesce those children
 670          * into this tree.
 671          */
 672         if (iterator__ignore_case(&iter->base))
 673                 error = tree_iterator_frame_push_neighbors(iter,
 674                         parent_frame, frame, entry->tree_entry->filename);
 675
 676 done:
 677         git_tree_free(tree);
 678         return error;
 679 }
 680
 681 static void tree_iterator_frame_pop(tree_iterator *iter)
 682 {
 683         tree_iterator_frame *frame;
 684         git_buf *buf = NULL;
 685         git_tree *tree;
 686         size_t i;
 687
 688         assert(iter->frames.size);
 689
 690         frame = git_array_pop(iter->frames);
 691
 692         git_vector_free(&frame->entries);
 693         git_tree_free(frame->tree);
 694
 695         do {
 696                 buf = git_array_pop(frame->similar_paths);
 697                 git_buf_dispose(buf);
 698         } while (buf != NULL);
 699
 700         git_array_clear(frame->similar_paths);
 701
 702         git_vector_foreach(&frame->similar_trees, i, tree)
 703                 git_tree_free(tree);
 704
 705         git_vector_free(&frame->similar_trees);
 706
 707         git_buf_dispose(&frame->path);
 708 }
 709
 710 static int tree_iterator_current(
 711         const git_index_entry **out, git_iterator *i)
 712 {
 713         tree_iterator *iter = (tree_iterator *)i;
 714
 715         if (!iterator__has_been_accessed(i))
 716                 return iter->base.cb->advance(out, i);
 717
 718         if (!iter->frames.size) {
 719                 *out = NULL;
 720                 return GIT_ITEROVER;
 721         }
 722
 723         *out = &iter->entry;
 724         return 0;
 725 }
 726
 727 static void tree_iterator_set_current(
 728         tree_iterator *iter,
 729         tree_iterator_frame *frame,
 730         tree_iterator_entry *entry)
 731 {
 732         git_tree_entry *tree_entry = entry->tree_entry;
 733
 734         frame->current = entry;
 735
 736         memset(&iter->entry, 0x0, sizeof(git_index_entry));
 737
 738         iter->entry.mode = tree_entry->attr;
 739         iter->entry.path = iter->entry_path.ptr;
 740         git_oid_cpy(&iter->entry.id, tree_entry->oid);
 741 }
 742
 743 static int tree_iterator_advance(const git_index_entry **out, git_iterator *i)
 744 {
 745         tree_iterator *iter = (tree_iterator *)i;
 746         int error = 0;
 747
 748         iter->base.flags |= GIT_ITERATOR_FIRST_ACCESS;
 749
 750         /* examine tree entries until we find the next one to return */
 751         while (true) {
 752                 tree_iterator_entry *prev_entry, *entry;
 753                 tree_iterator_frame *frame;
 754                 bool is_tree;
 755
 756                 if ((frame = tree_iterator_current_frame(iter)) == NULL) {
 757                         error = GIT_ITEROVER;
 758                         break;
 759                 }
 760
 761                 /* no more entries in this frame.  pop the frame out */
 762                 if (frame->next_idx == frame->entries.length) {
 763                         tree_iterator_frame_pop(iter);
 764                         continue;
 765                 }
 766
 767                 /* we may have coalesced the contents of case-insensitively same-named
 768                  * directories, so do the sort now.
 769                  */
 770                 if (frame->next_idx == 0 && !git_vector_is_sorted(&frame->entries))
 771                         git_vector_sort(&frame->entries);
 772
 773                 /* we have more entries in the current frame, that's our next entry */
 774                 prev_entry = tree_iterator_current_entry(frame);
 775                 entry = frame->entries.contents[frame->next_idx];
 776                 frame->next_idx++;
 777
 778                 /* we can have collisions when iterating case insensitively.  (eg,
 779                  * 'A/a' and 'a/A').  squash this one if it's already been seen.
 780                  */
 781                 if (iterator__ignore_case(&iter->base) &&
 782                         prev_entry &&
 783                         tree_iterator_entry_cmp_icase(prev_entry, entry) == 0)
 784                         continue;
 785
 786                 if ((error = tree_iterator_compute_path(&iter->entry_path, entry)) < 0)
 787                         break;
 788
 789                 /* if this path is before our start, advance over this entry */
 790                 if (!iterator_has_started(&iter->base, iter->entry_path.ptr, false))
 791                         continue;
 792
 793                 /* if this path is after our end, stop */
 794                 if (iterator_has_ended(&iter->base, iter->entry_path.ptr)) {
 795                         error = GIT_ITEROVER;
 796                         break;
 797                 }
 798
 799                 /* if we have a list of paths we're interested in, examine it */
 800                 if (!iterator_pathlist_next_is(&iter->base, iter->entry_path.ptr))
 801                         continue;
 802
 803                 is_tree = git_tree_entry__is_tree(entry->tree_entry);
 804
 805                 /* if we are *not* including trees then advance over this entry */
 806                 if (is_tree && !iterator__include_trees(iter)) {
 807
 808                         /* if we've found a tree (and are not returning it to the caller)
 809                          * and we are autoexpanding, then we want to return the first
 810                          * child.  push the new directory and advance.
 811                          */
 812                         if (iterator__do_autoexpand(iter)) {
 813                                 if ((error = tree_iterator_frame_push(iter, entry)) < 0)
 814                                         break;
 815                         }
 816
 817                         continue;
 818                 }
 819
 820                 tree_iterator_set_current(iter, frame, entry);
 821
 822                 /* if we are autoexpanding, then push this as a new frame, so that
 823                  * the next call to `advance` will dive into this directory.
 824                  */
 825                 if (is_tree && iterator__do_autoexpand(iter))
 826                         error = tree_iterator_frame_push(iter, entry);
 827
 828                 break;
 829         }
 830
 831         if (out)
 832                 *out = (error == 0) ? &iter->entry : NULL;
 833
 834         return error;
 835 }
 836
 837 static int tree_iterator_advance_into(
 838         const git_index_entry **out, git_iterator *i)
 839 {
 840         tree_iterator *iter = (tree_iterator *)i;
 841     tree_iterator_frame *frame;
 842         tree_iterator_entry *prev_entry;
 843         int error;
 844
 845         if (out)
 846                 *out = NULL;
 847
 848         if ((frame = tree_iterator_current_frame(iter)) == NULL)
 849                 return GIT_ITEROVER;
 850
 851         /* get the last seen entry */
 852         prev_entry = tree_iterator_current_entry(frame);
 853
 854         /* it's legal to call advance_into when auto-expand is on.  in this case,
 855          * we will have pushed a new (empty) frame on to the stack for this
 856          * new directory.  since it's empty, its current_entry should be null.
 857          */
 858         assert(iterator__do_autoexpand(i) ^ (prev_entry != NULL));
 859
 860         if (prev_entry) {
 861                 if (!git_tree_entry__is_tree(prev_entry->tree_entry))
 862                         return 0;
 863
 864                 if ((error = tree_iterator_frame_push(iter, prev_entry)) < 0)
 865                         return error;
 866         }
 867
 868         /* we've advanced into the directory in question, let advance
 869          * find the first entry
 870          */
 871         return tree_iterator_advance(out, i);
 872 }
 873
 874 static int tree_iterator_advance_over(
 875         const git_index_entry **out,
 876         git_iterator_status_t *status,
 877         git_iterator *i)
 878 {
 879         *status = GIT_ITERATOR_STATUS_NORMAL;
 880         return git_iterator_advance(out, i);
 881 }
 882
 883 static void tree_iterator_clear(tree_iterator *iter)
 884 {
 885         while (iter->frames.size)
 886                 tree_iterator_frame_pop(iter);
 887
 888         git_array_clear(iter->frames);
 889
 890         git_pool_clear(&iter->entry_pool);
 891         git_buf_clear(&iter->entry_path);
 892
 893         iterator_clear(&iter->base);
 894 }
 895
 896 static int tree_iterator_init(tree_iterator *iter)
 897 {
 898         int error;
 899
 900         if ((error = git_pool_init(&iter->entry_pool, sizeof(tree_iterator_entry))) < 0 ||
 901             (error = tree_iterator_frame_init(iter, iter->root, NULL)) < 0)
 902                 return error;
 903
 904         iter->base.flags &= ~GIT_ITERATOR_FIRST_ACCESS;
 905
 906         return 0;
 907 }
 908
 909 static int tree_iterator_reset(git_iterator *i)
 910 {
 911         tree_iterator *iter = (tree_iterator *)i;
 912
 913         tree_iterator_clear(iter);
 914         return tree_iterator_init(iter);
 915 }
 916
 917 static void tree_iterator_free(git_iterator *i)
 918 {
 919         tree_iterator *iter = (tree_iterator *)i;
 920
 921         tree_iterator_clear(iter);
 922
 923         git_tree_free(iter->root);
 924         git_buf_dispose(&iter->entry_path);
 925 }
 926
 927 int git_iterator_for_tree(
 928         git_iterator **out,
 929         git_tree *tree,
 930         git_iterator_options *options)
 931 {
 932         tree_iterator *iter;
 933         int error;
 934
 935         static git_iterator_callbacks callbacks = {
 936                 tree_iterator_current,
 937                 tree_iterator_advance,
 938                 tree_iterator_advance_into,
 939                 tree_iterator_advance_over,
 940                 tree_iterator_reset,
 941                 tree_iterator_free
 942         };
 943
 944         *out = NULL;
 945
 946         if (tree == NULL)
 947                 return git_iterator_for_nothing(out, options);
 948
 949         iter = git__calloc(1, sizeof(tree_iterator));
 950         GIT_ERROR_CHECK_ALLOC(iter);
 951
 952         iter->base.type = GIT_ITERATOR_TREE;
 953         iter->base.cb = &callbacks;
 954
 955         if ((error = iterator_init_common(&iter->base,
 956                         git_tree_owner(tree), NULL, options)) < 0 ||
 957                 (error = git_tree_dup(&iter->root, tree)) < 0 ||
 958                 (error = tree_iterator_init(iter)) < 0)
 959                 goto on_error;
 960
 961         *out = &iter->base;
 962         return 0;
 963
 964 on_error:
 965         git_iterator_free(&iter->base);
 966         return error;
 967 }
 968
 969 int git_iterator_current_tree_entry(
 970         const git_tree_entry **tree_entry, git_iterator *i)
 971 {
 972         tree_iterator *iter;
 973         tree_iterator_frame *frame;
 974         tree_iterator_entry *entry;
 975
 976         assert(i->type == GIT_ITERATOR_TREE);
 977
 978         iter = (tree_iterator *)i;
 979
 980         frame = tree_iterator_current_frame(iter);
 981         entry = tree_iterator_current_entry(frame);
 982
 983         *tree_entry = entry->tree_entry;
 984         return 0;
 985 }
 986
 987 int git_iterator_current_parent_tree(
 988         const git_tree **parent_tree, git_iterator *i, size_t depth)
 989 {
 990         tree_iterator *iter;
 991         tree_iterator_frame *frame;
 992
 993         assert(i->type == GIT_ITERATOR_TREE);
 994
 995         iter = (tree_iterator *)i;
 996
 997         assert(depth < iter->frames.size);
 998         frame = &iter->frames.ptr[iter->frames.size-depth-1];
 999
1000         *parent_tree = frame->tree;
1001         return 0;
1002 }
1003
1004 /* Filesystem iterator */
1005
1006 typedef struct {
1007         struct stat st;
1008         size_t path_len;
1009         iterator_pathlist_search_t match;
1010         git_oid id;
1011         char path[GIT_FLEX_ARRAY];
1012 } filesystem_iterator_entry;
1013
1014 typedef struct {
1015         git_vector entries;
1016         git_pool entry_pool;
1017         size_t next_idx;
1018
1019         size_t path_len;
1020         int is_ignored;
1021 } filesystem_iterator_frame;
1022
1023 typedef struct {
1024         git_iterator base;
1025         char *root;
1026         size_t root_len;
1027
1028         unsigned int dirload_flags;
1029
1030         git_tree *tree;
1031         git_index *index;
1032         git_vector index_snapshot;
1033
1034         git_array_t(filesystem_iterator_frame) frames;
1035         git_ignores ignores;
1036
1037         /* info about the current entry */
1038         git_index_entry entry;
1039         git_buf current_path;
1040         int current_is_ignored;
1041
1042         /* temporary buffer for advance_over */
1043         git_buf tmp_buf;
1044 } filesystem_iterator;
1045
1046
1047 GIT_INLINE(filesystem_iterator_frame *) filesystem_iterator_parent_frame(
1048         filesystem_iterator *iter)
1049 {
1050         return iter->frames.size > 1 ?
1051                 &iter->frames.ptr[iter->frames.size-2] : NULL;
1052 }
1053
1054 GIT_INLINE(filesystem_iterator_frame *) filesystem_iterator_current_frame(
1055         filesystem_iterator *iter)
1056 {
1057         return iter->frames.size ? &iter->frames.ptr[iter->frames.size-1] : NULL;
1058 }
1059
1060 GIT_INLINE(filesystem_iterator_entry *) filesystem_iterator_current_entry(
1061         filesystem_iterator_frame *frame)
1062 {
1063         return frame->next_idx == 0 ?
1064                 NULL : frame->entries.contents[frame->next_idx-1];
1065 }
1066
1067 static int filesystem_iterator_entry_cmp(const void *_a, const void *_b)
1068 {
1069         const filesystem_iterator_entry *a = (const filesystem_iterator_entry *)_a;
1070         const filesystem_iterator_entry *b = (const filesystem_iterator_entry *)_b;
1071
1072         return git__strcmp(a->path, b->path);
1073 }
1074
1075 static int filesystem_iterator_entry_cmp_icase(const void *_a, const void *_b)
1076 {
1077         const filesystem_iterator_entry *a = (const filesystem_iterator_entry *)_a;
1078         const filesystem_iterator_entry *b = (const filesystem_iterator_entry *)_b;
1079
1080         return git__strcasecmp(a->path, b->path);
1081 }
1082
1083 #define FILESYSTEM_MAX_DEPTH 100
1084
1085 /**
1086  * Figure out if an entry is a submodule.
1087  *
1088  * We consider it a submodule if the path is listed as a submodule in
1089  * either the tree or the index.
1090  */
1091 static int filesystem_iterator_is_submodule(
1092         bool *out, filesystem_iterator *iter, const char *path, size_t path_len)
1093 {
1094         bool is_submodule = false;
1095         int error;
1096
1097         *out = false;
1098
1099         /* first see if this path is a submodule in HEAD */
1100         if (iter->tree) {
1101                 git_tree_entry *entry;
1102
1103                 error = git_tree_entry_bypath(&entry, iter->tree, path);
1104
1105                 if (error < 0 && error != GIT_ENOTFOUND)
1106                         return error;
1107
1108                 if (!error) {
1109                         is_submodule = (entry->attr == GIT_FILEMODE_COMMIT);
1110                         git_tree_entry_free(entry);
1111                 }
1112         }
1113
1114         if (!is_submodule && iter->base.index) {
1115                 size_t pos;
1116
1117                 error = git_index_snapshot_find(&pos,
1118                         &iter->index_snapshot, iter->base.entry_srch, path, path_len, 0);
1119
1120                 if (error < 0 && error != GIT_ENOTFOUND)
1121                         return error;
1122
1123                 if (!error) {
1124                         git_index_entry *e = git_vector_get(&iter->index_snapshot, pos);
1125                         is_submodule = (e->mode == GIT_FILEMODE_COMMIT);
1126                 }
1127         }
1128
1129         *out = is_submodule;
1130         return 0;
1131 }
1132
1133 static void filesystem_iterator_frame_push_ignores(
1134         filesystem_iterator *iter,
1135         filesystem_iterator_entry *frame_entry,
1136         filesystem_iterator_frame *new_frame)
1137 {
1138         filesystem_iterator_frame *previous_frame;
1139         const char *path = frame_entry ? frame_entry->path : "";
1140
1141         if (!iterator__honor_ignores(&iter->base))
1142                 return;
1143
1144         if (git_ignore__lookup(&new_frame->is_ignored,
1145                         &iter->ignores, path, GIT_DIR_FLAG_TRUE) < 0) {
1146                 git_error_clear();
1147                 new_frame->is_ignored = GIT_IGNORE_NOTFOUND;
1148         }
1149
1150         /* if this is not the top level directory... */
1151         if (frame_entry) {
1152                 const char *relative_path;
1153
1154                 previous_frame = filesystem_iterator_parent_frame(iter);
1155
1156                 /* push new ignores for files in this directory */
1157                 relative_path = frame_entry->path + previous_frame->path_len;
1158
1159                 /* inherit ignored from parent if no rule specified */
1160                 if (new_frame->is_ignored <= GIT_IGNORE_NOTFOUND)
1161                         new_frame->is_ignored = previous_frame->is_ignored;
1162
1163                 git_ignore__push_dir(&iter->ignores, relative_path);
1164         }
1165 }
1166
1167 static void filesystem_iterator_frame_pop_ignores(
1168         filesystem_iterator *iter)
1169 {
1170         if (iterator__honor_ignores(&iter->base))
1171                 git_ignore__pop_dir(&iter->ignores);
1172 }
1173
1174 GIT_INLINE(bool) filesystem_iterator_examine_path(
1175         bool *is_dir_out,
1176         iterator_pathlist_search_t *match_out,
1177         filesystem_iterator *iter,
1178         filesystem_iterator_entry *frame_entry,
1179         const char *path,
1180         size_t path_len)
1181 {
1182         bool is_dir = 0;
1183         iterator_pathlist_search_t match = ITERATOR_PATHLIST_FULL;
1184
1185         *is_dir_out = false;
1186         *match_out = ITERATOR_PATHLIST_NONE;
1187
1188         if (iter->base.start_len) {
1189                 int cmp = iter->base.strncomp(path, iter->base.start, path_len);
1190
1191                 /* we haven't stat'ed `path` yet, so we don't yet know if it's a
1192                  * directory or not.  special case if the current path may be a
1193                  * directory that matches the start prefix.
1194                  */
1195                 if (cmp == 0) {
1196                         if (iter->base.start[path_len] == '/')
1197                                 is_dir = true;
1198
1199                         else if (iter->base.start[path_len] != '\0')
1200                                 cmp = -1;
1201                 }
1202
1203                 if (cmp < 0)
1204                         return false;
1205         }
1206
1207         if (iter->base.end_len) {
1208                 int cmp = iter->base.strncomp(path, iter->base.end, iter->base.end_len);
1209
1210                 if (cmp > 0)
1211                         return false;
1212         }
1213
1214         /* if we have a pathlist that we're limiting to, examine this path now
1215          * to avoid a `stat` if we're not interested in the path.
1216          */
1217         if (iter->base.pathlist.length) {
1218                 /* if our parent was explicitly included, so too are we */
1219                 if (frame_entry && frame_entry->match != ITERATOR_PATHLIST_IS_PARENT)
1220                         match = ITERATOR_PATHLIST_FULL;
1221                 else
1222                         match = iterator_pathlist_search(&iter->base, path, path_len);
1223
1224                 if (match == ITERATOR_PATHLIST_NONE)
1225                         return false;
1226
1227                 /* Ensure that the pathlist entry lines up with what we expected */
1228                 if (match == ITERATOR_PATHLIST_IS_DIR ||
1229                         match == ITERATOR_PATHLIST_IS_PARENT)
1230                         is_dir = true;
1231         }
1232
1233         *is_dir_out = is_dir;
1234         *match_out = match;
1235         return true;
1236 }
1237
1238 GIT_INLINE(bool) filesystem_iterator_is_dot_git(
1239         filesystem_iterator *iter, const char *path, size_t path_len)
1240 {
1241         size_t len;
1242
1243         if (!iterator__ignore_dot_git(&iter->base))
1244                 return false;
1245
1246         if ((len = path_len) < 4)
1247                 return false;
1248
1249         if (path[len - 1] == '/')
1250                 len--;
1251
1252         if (git__tolower(path[len - 1]) != 't' ||
1253                 git__tolower(path[len - 2]) != 'i' ||
1254                 git__tolower(path[len - 3]) != 'g' ||
1255                 git__tolower(path[len - 4]) != '.')
1256                 return false;
1257
1258         return (len == 4 || path[len - 5] == '/');
1259 }
1260
1261 static int filesystem_iterator_entry_hash(
1262         filesystem_iterator *iter,
1263         filesystem_iterator_entry *entry)
1264 {
1265         git_buf fullpath = GIT_BUF_INIT;
1266         int error;
1267
1268         if (S_ISDIR(entry->st.st_mode)) {
1269                 memset(&entry->id, 0, GIT_OID_RAWSZ);
1270                 return 0;
1271         }
1272
1273         if (iter->base.type == GIT_ITERATOR_WORKDIR)
1274                 return git_repository_hashfile(&entry->id,
1275                         iter->base.repo, entry->path, GIT_OBJECT_BLOB, NULL);
1276
1277         if (!(error = git_buf_joinpath(&fullpath, iter->root, entry->path)))
1278                 error = git_odb_hashfile(&entry->id, fullpath.ptr, GIT_OBJECT_BLOB);
1279
1280         git_buf_dispose(&fullpath);
1281         return error;
1282 }
1283
1284 static int filesystem_iterator_entry_init(
1285         filesystem_iterator_entry **out,
1286         filesystem_iterator *iter,
1287         filesystem_iterator_frame *frame,
1288         const char *path,
1289         size_t path_len,
1290         struct stat *statbuf,
1291         iterator_pathlist_search_t pathlist_match)
1292 {
1293         filesystem_iterator_entry *entry;
1294         size_t entry_size;
1295         int error = 0;
1296
1297         *out = NULL;
1298
1299         /* Make sure to append two bytes, one for the path's null
1300          * termination, one for a possible trailing '/' for folders.
1301          */
1302         GIT_ERROR_CHECK_ALLOC_ADD(&entry_size,
1303                 sizeof(filesystem_iterator_entry), path_len);
1304         GIT_ERROR_CHECK_ALLOC_ADD(&entry_size, entry_size, 2);
1305
1306         entry = git_pool_malloc(&frame->entry_pool, entry_size);
1307         GIT_ERROR_CHECK_ALLOC(entry);
1308
1309         entry->path_len = path_len;
1310         entry->match = pathlist_match;
1311         memcpy(entry->path, path, path_len);
1312         memcpy(&entry->st, statbuf, sizeof(struct stat));
1313
1314         /* Suffix directory paths with a '/' */
1315         if (S_ISDIR(entry->st.st_mode))
1316                 entry->path[entry->path_len++] = '/';
1317
1318         entry->path[entry->path_len] = '\0';
1319
1320         if (iter->base.flags & GIT_ITERATOR_INCLUDE_HASH)
1321                 error = filesystem_iterator_entry_hash(iter, entry);
1322
1323         if (!error)
1324                 *out = entry;
1325
1326         return error;
1327 }
1328
1329 static int filesystem_iterator_frame_push(
1330         filesystem_iterator *iter,
1331         filesystem_iterator_entry *frame_entry)
1332 {
1333         filesystem_iterator_frame *new_frame = NULL;
1334         git_path_diriter diriter = GIT_PATH_DIRITER_INIT;
1335         git_buf root = GIT_BUF_INIT;
1336         const char *path;
1337         filesystem_iterator_entry *entry;
1338         struct stat statbuf;
1339         size_t path_len;
1340         int error;
1341
1342         if (iter->frames.size == FILESYSTEM_MAX_DEPTH) {
1343                 git_error_set(GIT_ERROR_REPOSITORY,
1344                         "directory nesting too deep (%"PRIuZ")", iter->frames.size);
1345                 return -1;
1346         }
1347
1348         new_frame = git_array_alloc(iter->frames);
1349         GIT_ERROR_CHECK_ALLOC(new_frame);
1350
1351         memset(new_frame, 0, sizeof(filesystem_iterator_frame));
1352
1353         if (frame_entry)
1354                 git_buf_joinpath(&root, iter->root, frame_entry->path);
1355         else
1356                 git_buf_puts(&root, iter->root);
1357
1358         if (git_buf_oom(&root)) {
1359                 error = -1;
1360                 goto done;
1361         }
1362
1363         new_frame->path_len = frame_entry ? frame_entry->path_len : 0;
1364
1365         /* Any error here is equivalent to the dir not existing, skip over it */
1366         if ((error = git_path_diriter_init(
1367                         &diriter, root.ptr, iter->dirload_flags)) < 0) {
1368                 error = GIT_ENOTFOUND;
1369                 goto done;
1370         }
1371
1372         if ((error = git_vector_init(&new_frame->entries, 64,
1373                         iterator__ignore_case(&iter->base) ?
1374                         filesystem_iterator_entry_cmp_icase :
1375                         filesystem_iterator_entry_cmp)) < 0)
1376                 goto done;
1377
1378         if ((error = git_pool_init(&new_frame->entry_pool, 1)) < 0)
1379                 goto done;
1380
1381         /* check if this directory is ignored */
1382         filesystem_iterator_frame_push_ignores(iter, frame_entry, new_frame);
1383
1384         while ((error = git_path_diriter_next(&diriter)) == 0) {
1385                 iterator_pathlist_search_t pathlist_match = ITERATOR_PATHLIST_FULL;
1386                 bool dir_expected = false;
1387
1388                 if ((error = git_path_diriter_fullpath(&path, &path_len, &diriter)) < 0)
1389                         goto done;
1390
1391                 assert(path_len > iter->root_len);
1392
1393                 /* remove the prefix if requested */
1394                 path += iter->root_len;
1395                 path_len -= iter->root_len;
1396
1397                 /* examine start / end and the pathlist to see if this path is in it.
1398                  * note that since we haven't yet stat'ed the path, we cannot know
1399                  * whether it's a directory yet or not, so this can give us an
1400                  * expected type (S_IFDIR or S_IFREG) that we should examine)
1401                  */
1402                 if (!filesystem_iterator_examine_path(&dir_expected, &pathlist_match,
1403                         iter, frame_entry, path, path_len))
1404                         continue;
1405
1406                 /* TODO: don't need to stat if assume unchanged for this path and
1407                  * we have an index, we can just copy the data out of it.
1408                  */
1409
1410                 if ((error = git_path_diriter_stat(&statbuf, &diriter)) < 0) {
1411                         /* file was removed between readdir and lstat */
1412                         if (error == GIT_ENOTFOUND)
1413                                 continue;
1414
1415                         /* treat the file as unreadable */
1416                         memset(&statbuf, 0, sizeof(statbuf));
1417                         statbuf.st_mode = GIT_FILEMODE_UNREADABLE;
1418
1419                         error = 0;
1420                 }
1421
1422                 iter->base.stat_calls++;
1423
1424                 /* Ignore wacky things in the filesystem */
1425                 if (!S_ISDIR(statbuf.st_mode) &&
1426                         !S_ISREG(statbuf.st_mode) &&
1427                         !S_ISLNK(statbuf.st_mode) &&
1428                         statbuf.st_mode != GIT_FILEMODE_UNREADABLE)
1429                         continue;
1430
1431                 if (filesystem_iterator_is_dot_git(iter, path, path_len))
1432                         continue;
1433
1434                 /* convert submodules to GITLINK and remove trailing slashes */
1435                 if (S_ISDIR(statbuf.st_mode)) {
1436                         bool submodule = false;
1437
1438                         if ((error = filesystem_iterator_is_submodule(&submodule,
1439                                         iter, path, path_len)) < 0)
1440                                 goto done;
1441
1442                         if (submodule)
1443                                 statbuf.st_mode = GIT_FILEMODE_COMMIT;
1444                 }
1445
1446                 /* Ensure that the pathlist entry lines up with what we expected */
1447                 else if (dir_expected)
1448                         continue;
1449
1450                 if ((error = filesystem_iterator_entry_init(&entry,
1451                         iter, new_frame, path, path_len, &statbuf, pathlist_match)) < 0)
1452                         goto done;
1453
1454                 git_vector_insert(&new_frame->entries, entry);
1455         }
1456
1457         if (error == GIT_ITEROVER)
1458                 error = 0;
1459
1460         /* sort now that directory suffix is added */
1461         git_vector_sort(&new_frame->entries);
1462
1463 done:
1464         if (error < 0)
1465                 git_array_pop(iter->frames);
1466
1467         git_buf_dispose(&root);
1468         git_path_diriter_free(&diriter);
1469         return error;
1470 }
1471
1472 GIT_INLINE(void) filesystem_iterator_frame_pop(filesystem_iterator *iter)
1473 {
1474         filesystem_iterator_frame *frame;
1475
1476         assert(iter->frames.size);
1477
1478         frame = git_array_pop(iter->frames);
1479         filesystem_iterator_frame_pop_ignores(iter);
1480
1481         git_pool_clear(&frame->entry_pool);
1482         git_vector_free(&frame->entries);
1483 }
1484
1485 static void filesystem_iterator_set_current(
1486         filesystem_iterator *iter,
1487         filesystem_iterator_entry *entry)
1488 {
1489         /*
1490          * Index entries are limited to 32 bit timestamps.  We can safely
1491          * cast this since workdir times are only used in the cache; any
1492          * mismatch will cause a hash recomputation which is unfortunate
1493          * but affects only people who set their filetimes to 2038.
1494          * (Same with the file size.)
1495          */
1496         iter->entry.ctime.seconds = (int32_t)entry->st.st_ctime;
1497         iter->entry.mtime.seconds = (int32_t)entry->st.st_mtime;
1498
1499 #if defined(GIT_USE_NSEC)
1500         iter->entry.ctime.nanoseconds = entry->st.st_ctime_nsec;
1501         iter->entry.mtime.nanoseconds = entry->st.st_mtime_nsec;
1502 #else
1503         iter->entry.ctime.nanoseconds = 0;
1504         iter->entry.mtime.nanoseconds = 0;
1505 #endif
1506
1507         iter->entry.dev = entry->st.st_dev;
1508         iter->entry.ino = entry->st.st_ino;
1509         iter->entry.mode = git_futils_canonical_mode(entry->st.st_mode);
1510         iter->entry.uid = entry->st.st_uid;
1511         iter->entry.gid = entry->st.st_gid;
1512         iter->entry.file_size = (uint32_t)entry->st.st_size;
1513
1514         if (iter->base.flags & GIT_ITERATOR_INCLUDE_HASH)
1515                 git_oid_cpy(&iter->entry.id, &entry->id);
1516
1517         iter->entry.path = entry->path;
1518
1519         iter->current_is_ignored = GIT_IGNORE_UNCHECKED;
1520 }
1521
1522 static int filesystem_iterator_current(
1523         const git_index_entry **out, git_iterator *i)
1524 {
1525         filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1526
1527         if (!iterator__has_been_accessed(i))
1528                 return iter->base.cb->advance(out, i);
1529
1530         if (!iter->frames.size) {
1531                 *out = NULL;
1532                 return GIT_ITEROVER;
1533         }
1534
1535         *out = &iter->entry;
1536         return 0;
1537 }
1538
1539 static int filesystem_iterator_is_dir(
1540         bool *is_dir,
1541         const filesystem_iterator *iter,
1542         const filesystem_iterator_entry *entry)
1543 {
1544         struct stat st;
1545         git_buf fullpath = GIT_BUF_INIT;
1546         int error = 0;
1547
1548         if (S_ISDIR(entry->st.st_mode)) {
1549                 *is_dir = 1;
1550                 goto done;
1551         }
1552
1553         if (!iterator__descend_symlinks(iter) || !S_ISLNK(entry->st.st_mode)) {
1554                 *is_dir = 0;
1555                 goto done;
1556         }
1557
1558         if ((error = git_buf_joinpath(&fullpath, iter->root, entry->path)) < 0 ||
1559                 (error = p_stat(fullpath.ptr, &st)) < 0)
1560                 goto done;
1561
1562         *is_dir = S_ISDIR(st.st_mode);
1563
1564 done:
1565         git_buf_dispose(&fullpath);
1566         return error;
1567 }
1568
1569 static int filesystem_iterator_advance(
1570         const git_index_entry **out, git_iterator *i)
1571 {
1572         filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1573         bool is_dir;
1574         int error = 0;
1575
1576         iter->base.flags |= GIT_ITERATOR_FIRST_ACCESS;
1577
1578         /* examine filesystem entries until we find the next one to return */
1579         while (true) {
1580                 filesystem_iterator_frame *frame;
1581                 filesystem_iterator_entry *entry;
1582
1583                 if ((frame = filesystem_iterator_current_frame(iter)) == NULL) {
1584                         error = GIT_ITEROVER;
1585                         break;
1586                 }
1587
1588                 /* no more entries in this frame.  pop the frame out */
1589                 if (frame->next_idx == frame->entries.length) {
1590                         filesystem_iterator_frame_pop(iter);
1591                         continue;
1592                 }
1593
1594                 /* we have more entries in the current frame, that's our next entry */
1595                 entry = frame->entries.contents[frame->next_idx];
1596                 frame->next_idx++;
1597
1598                 if ((error = filesystem_iterator_is_dir(&is_dir, iter, entry)) < 0)
1599                         break;
1600
1601                 if (is_dir) {
1602                         if (iterator__do_autoexpand(iter)) {
1603                                 error = filesystem_iterator_frame_push(iter, entry);
1604
1605                                 /* may get GIT_ENOTFOUND due to races or permission problems
1606                                  * that we want to quietly swallow
1607                                  */
1608                                 if (error == GIT_ENOTFOUND)
1609                                         continue;
1610                                 else if (error < 0)
1611                                         break;
1612                         }
1613
1614                         if (!iterator__include_trees(iter))
1615                                 continue;
1616                 }
1617
1618                 filesystem_iterator_set_current(iter, entry);
1619                 break;
1620         }
1621
1622         if (out)
1623                 *out = (error == 0) ? &iter->entry : NULL;
1624
1625         return error;
1626 }
1627
1628 static int filesystem_iterator_advance_into(
1629         const git_index_entry **out, git_iterator *i)
1630 {
1631         filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1632         filesystem_iterator_frame *frame;
1633         filesystem_iterator_entry *prev_entry;
1634         int error;
1635
1636         if (out)
1637                 *out = NULL;
1638
1639         if ((frame = filesystem_iterator_current_frame(iter)) == NULL)
1640                 return GIT_ITEROVER;
1641
1642         /* get the last seen entry */
1643         prev_entry = filesystem_iterator_current_entry(frame);
1644
1645         /* it's legal to call advance_into when auto-expand is on.  in this case,
1646          * we will have pushed a new (empty) frame on to the stack for this
1647          * new directory.  since it's empty, its current_entry should be null.
1648          */
1649         assert(iterator__do_autoexpand(i) ^ (prev_entry != NULL));
1650
1651         if (prev_entry) {
1652                 if (prev_entry->st.st_mode != GIT_FILEMODE_COMMIT &&
1653                         !S_ISDIR(prev_entry->st.st_mode))
1654                         return 0;
1655
1656                 if ((error = filesystem_iterator_frame_push(iter, prev_entry)) < 0)
1657                         return error;
1658         }
1659
1660         /* we've advanced into the directory in question, let advance
1661          * find the first entry
1662          */
1663         return filesystem_iterator_advance(out, i);
1664 }
1665
1666 int git_iterator_current_workdir_path(git_buf **out, git_iterator *i)
1667 {
1668         filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1669         const git_index_entry *entry;
1670
1671         if (i->type != GIT_ITERATOR_FS &&
1672                 i->type != GIT_ITERATOR_WORKDIR) {
1673                 *out = NULL;
1674                 return 0;
1675         }
1676
1677         git_buf_truncate(&iter->current_path, iter->root_len);
1678
1679         if (git_iterator_current(&entry, i) < 0 ||
1680                 git_buf_puts(&iter->current_path, entry->path) < 0)
1681                 return -1;
1682
1683         *out = &iter->current_path;
1684         return 0;
1685 }
1686
1687 GIT_INLINE(git_dir_flag) entry_dir_flag(git_index_entry *entry)
1688 {
1689 #if defined(GIT_WIN32) && !defined(__MINGW32__)
1690         return (entry && entry->mode) ?
1691                 (S_ISDIR(entry->mode) ? GIT_DIR_FLAG_TRUE : GIT_DIR_FLAG_FALSE) :
1692                 GIT_DIR_FLAG_UNKNOWN;
1693 #else
1694         GIT_UNUSED(entry);
1695         return GIT_DIR_FLAG_UNKNOWN;
1696 #endif
1697 }
1698
1699 static void filesystem_iterator_update_ignored(filesystem_iterator *iter)
1700 {
1701         filesystem_iterator_frame *frame;
1702         git_dir_flag dir_flag = entry_dir_flag(&iter->entry);
1703
1704         if (git_ignore__lookup(&iter->current_is_ignored,
1705                         &iter->ignores, iter->entry.path, dir_flag) < 0) {
1706                 git_error_clear();
1707                 iter->current_is_ignored = GIT_IGNORE_NOTFOUND;
1708         }
1709
1710         /* use ignore from containing frame stack */
1711         if (iter->current_is_ignored <= GIT_IGNORE_NOTFOUND) {
1712                 frame = filesystem_iterator_current_frame(iter);
1713                 iter->current_is_ignored = frame->is_ignored;
1714         }
1715 }
1716
1717 GIT_INLINE(bool) filesystem_iterator_current_is_ignored(
1718         filesystem_iterator *iter)
1719 {
1720         if (iter->current_is_ignored == GIT_IGNORE_UNCHECKED)
1721                 filesystem_iterator_update_ignored(iter);
1722
1723         return (iter->current_is_ignored == GIT_IGNORE_TRUE);
1724 }
1725
1726 bool git_iterator_current_is_ignored(git_iterator *i)
1727 {
1728         filesystem_iterator *iter = NULL;
1729
1730         if (i->type != GIT_ITERATOR_WORKDIR)
1731                 return false;
1732
1733         iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1734
1735         return filesystem_iterator_current_is_ignored(iter);
1736 }
1737
1738 bool git_iterator_current_tree_is_ignored(git_iterator *i)
1739 {
1740         filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1741         filesystem_iterator_frame *frame;
1742
1743         if (i->type != GIT_ITERATOR_WORKDIR)
1744                 return false;
1745
1746         frame = filesystem_iterator_current_frame(iter);
1747         return (frame->is_ignored == GIT_IGNORE_TRUE);
1748 }
1749
1750 static int filesystem_iterator_advance_over(
1751         const git_index_entry **out,
1752         git_iterator_status_t *status,
1753         git_iterator *i)
1754 {
1755         filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1756         filesystem_iterator_frame *current_frame;
1757         filesystem_iterator_entry *current_entry;
1758         const git_index_entry *entry = NULL;
1759         const char *base;
1760         int error = 0;
1761
1762         *out = NULL;
1763         *status = GIT_ITERATOR_STATUS_NORMAL;
1764
1765         assert(iterator__has_been_accessed(i));
1766
1767         current_frame = filesystem_iterator_current_frame(iter);
1768         assert(current_frame);
1769         current_entry = filesystem_iterator_current_entry(current_frame);
1770         assert(current_entry);
1771
1772         if ((error = git_iterator_current(&entry, i)) < 0)
1773                 return error;
1774
1775         if (!S_ISDIR(entry->mode)) {
1776                 if (filesystem_iterator_current_is_ignored(iter))
1777                         *status = GIT_ITERATOR_STATUS_IGNORED;
1778
1779                 return filesystem_iterator_advance(out, i);
1780         }
1781
1782         git_buf_clear(&iter->tmp_buf);
1783         if ((error = git_buf_puts(&iter->tmp_buf, entry->path)) < 0)
1784                 return error;
1785
1786         base = iter->tmp_buf.ptr;
1787
1788         /* scan inside the directory looking for files.  if we find nothing,
1789          * we will remain EMPTY.  if we find any ignored item, upgrade EMPTY to
1790          * IGNORED.  if we find a real actual item, upgrade all the way to NORMAL
1791          * and then stop.
1792          *
1793          * however, if we're here looking for a pathlist item (but are not
1794          * actually in the pathlist ourselves) then start at FILTERED instead of
1795          * EMPTY.  callers then know that this path was not something they asked
1796          * about.
1797          */
1798         *status = current_entry->match == ITERATOR_PATHLIST_IS_PARENT ?
1799                 GIT_ITERATOR_STATUS_FILTERED : GIT_ITERATOR_STATUS_EMPTY;
1800
1801         while (entry && !iter->base.prefixcomp(entry->path, base)) {
1802                 if (filesystem_iterator_current_is_ignored(iter)) {
1803                         /* if we found an explicitly ignored item, then update from
1804                          * EMPTY to IGNORED
1805                          */
1806                         *status = GIT_ITERATOR_STATUS_IGNORED;
1807                 } else if (S_ISDIR(entry->mode)) {
1808                         error = filesystem_iterator_advance_into(&entry, i);
1809
1810                         if (!error)
1811                                 continue;
1812
1813                         /* this directory disappeared, ignore it */
1814                         else if (error == GIT_ENOTFOUND)
1815                                 error = 0;
1816
1817                         /* a real error occurred */
1818                         else
1819                                 break;
1820                 } else {
1821                         /* we found a non-ignored item, treat parent as untracked */
1822                         *status = GIT_ITERATOR_STATUS_NORMAL;
1823                         break;
1824                 }
1825
1826                 if ((error = git_iterator_advance(&entry, i)) < 0)
1827                         break;
1828         }
1829
1830         /* wrap up scan back to base directory */
1831         while (entry && !iter->base.prefixcomp(entry->path, base)) {
1832                 if ((error = git_iterator_advance(&entry, i)) < 0)
1833                         break;
1834         }
1835
1836         if (!error)
1837                 *out = entry;
1838
1839         return error;
1840 }
1841
1842 static void filesystem_iterator_clear(filesystem_iterator *iter)
1843 {
1844         while (iter->frames.size)
1845                 filesystem_iterator_frame_pop(iter);
1846
1847         git_array_clear(iter->frames);
1848         git_ignore__free(&iter->ignores);
1849
1850         git_buf_dispose(&iter->tmp_buf);
1851
1852         iterator_clear(&iter->base);
1853 }
1854
1855 static int filesystem_iterator_init(filesystem_iterator *iter)
1856 {
1857         int error;
1858
1859         if (iterator__honor_ignores(&iter->base) &&
1860                 (error = git_ignore__for_path(iter->base.repo,
1861                         ".gitignore", &iter->ignores)) < 0)
1862                 return error;
1863
1864         if ((error = filesystem_iterator_frame_push(iter, NULL)) < 0)
1865                 return error;
1866
1867         iter->base.flags &= ~GIT_ITERATOR_FIRST_ACCESS;
1868
1869         return 0;
1870 }
1871
1872 static int filesystem_iterator_reset(git_iterator *i)
1873 {
1874         filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1875
1876         filesystem_iterator_clear(iter);
1877         return filesystem_iterator_init(iter);
1878 }
1879
1880 static void filesystem_iterator_free(git_iterator *i)
1881 {
1882         filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1883         git__free(iter->root);
1884         git_buf_dispose(&iter->current_path);
1885         git_tree_free(iter->tree);
1886         if (iter->index)
1887                 git_index_snapshot_release(&iter->index_snapshot, iter->index);
1888         filesystem_iterator_clear(iter);
1889 }
1890
1891 static int iterator_for_filesystem(
1892         git_iterator **out,
1893         git_repository *repo,
1894         const char *root,
1895         git_index *index,
1896         git_tree *tree,
1897         git_iterator_t type,
1898         git_iterator_options *options)
1899 {
1900         filesystem_iterator *iter;
1901         size_t root_len;
1902         int error;
1903
1904         static git_iterator_callbacks callbacks = {
1905                 filesystem_iterator_current,
1906                 filesystem_iterator_advance,
1907                 filesystem_iterator_advance_into,
1908                 filesystem_iterator_advance_over,
1909                 filesystem_iterator_reset,
1910                 filesystem_iterator_free
1911         };
1912
1913         *out = NULL;
1914
1915         if (root == NULL)
1916                 return git_iterator_for_nothing(out, options);
1917
1918         iter = git__calloc(1, sizeof(filesystem_iterator));
1919         GIT_ERROR_CHECK_ALLOC(iter);
1920
1921         iter->base.type = type;
1922         iter->base.cb = &callbacks;
1923
1924         root_len = strlen(root);
1925
1926         iter->root = git__malloc(root_len+2);
1927         GIT_ERROR_CHECK_ALLOC(iter->root);
1928
1929         memcpy(iter->root, root, root_len);
1930
1931         if (root_len == 0 || root[root_len-1] != '/') {
1932                 iter->root[root_len] = '/';
1933                 root_len++;
1934         }
1935         iter->root[root_len] = '\0';
1936         iter->root_len = root_len;
1937
1938         if ((error = git_buf_puts(&iter->current_path, iter->root)) < 0)
1939                 goto on_error;
1940
1941         if ((error = iterator_init_common(&iter->base, repo, index, options)) < 0)
1942                 goto on_error;
1943
1944         if (tree && (error = git_tree_dup(&iter->tree, tree)) < 0)
1945                 goto on_error;
1946
1947         if (index &&
1948                 (error = git_index_snapshot_new(&iter->index_snapshot, index)) < 0)
1949                 goto on_error;
1950
1951         iter->index = index;
1952         iter->dirload_flags =
1953                 (iterator__ignore_case(&iter->base) ? GIT_PATH_DIR_IGNORE_CASE : 0) |
1954                 (iterator__flag(&iter->base, PRECOMPOSE_UNICODE) ?
1955                          GIT_PATH_DIR_PRECOMPOSE_UNICODE : 0);
1956
1957         if ((error = filesystem_iterator_init(iter)) < 0)
1958                 goto on_error;
1959
1960         *out = &iter->base;
1961         return 0;
1962
1963 on_error:
1964         git_iterator_free(&iter->base);
1965         return error;
1966 }
1967
1968 int git_iterator_for_filesystem(
1969         git_iterator **out,
1970         const char *root,
1971         git_iterator_options *options)
1972 {
1973         return iterator_for_filesystem(out,
1974                 NULL, root, NULL, NULL, GIT_ITERATOR_FS, options);
1975 }
1976
1977 int git_iterator_for_workdir_ext(
1978         git_iterator **out,
1979         git_repository *repo,
1980         const char *repo_workdir,
1981         git_index *index,
1982         git_tree *tree,
1983         git_iterator_options *given_opts)
1984 {
1985         git_iterator_options options = GIT_ITERATOR_OPTIONS_INIT;
1986
1987         if (!repo_workdir) {
1988                 if (git_repository__ensure_not_bare(repo, "scan working directory") < 0)
1989                         return GIT_EBAREREPO;
1990
1991                 repo_workdir = git_repository_workdir(repo);
1992         }
1993
1994         /* upgrade to a workdir iterator, adding necessary internal flags */
1995         if (given_opts)
1996                 memcpy(&options, given_opts, sizeof(git_iterator_options));
1997
1998         options.flags |= GIT_ITERATOR_HONOR_IGNORES |
1999                 GIT_ITERATOR_IGNORE_DOT_GIT;
2000
2001         return iterator_for_filesystem(out,
2002                 repo, repo_workdir, index, tree, GIT_ITERATOR_WORKDIR, &options);
2003 }
2004
2005
2006 /* Index iterator */
2007
2008
2009 typedef struct {
2010         git_iterator base;
2011         git_vector entries;
2012         size_t next_idx;
2013
2014         /* the pseudotree entry */
2015         git_index_entry tree_entry;
2016         git_buf tree_buf;
2017         bool skip_tree;
2018
2019         const git_index_entry *entry;
2020 } index_iterator;
2021
2022 static int index_iterator_current(
2023         const git_index_entry **out, git_iterator *i)
2024 {
2025         index_iterator *iter = (index_iterator *)i;
2026
2027         if (!iterator__has_been_accessed(i))
2028                 return iter->base.cb->advance(out, i);
2029
2030         if (iter->entry == NULL) {
2031                 *out = NULL;
2032                 return GIT_ITEROVER;
2033         }
2034
2035         *out = iter->entry;
2036         return 0;
2037 }
2038
2039 static bool index_iterator_create_pseudotree(
2040         const git_index_entry **out,
2041         index_iterator *iter,
2042         const char *path)
2043 {
2044         const char *prev_path, *relative_path, *dirsep;
2045         size_t common_len;
2046
2047         prev_path = iter->entry ? iter->entry->path : "";
2048
2049         /* determine if the new path is in a different directory from the old */
2050         common_len = git_path_common_dirlen(prev_path, path);
2051         relative_path = path + common_len;
2052
2053         if ((dirsep = strchr(relative_path, '/')) == NULL)
2054                 return false;
2055
2056         git_buf_clear(&iter->tree_buf);
2057         git_buf_put(&iter->tree_buf, path, (dirsep - path) + 1);
2058
2059         iter->tree_entry.mode = GIT_FILEMODE_TREE;
2060         iter->tree_entry.path = iter->tree_buf.ptr;
2061
2062         *out = &iter->tree_entry;
2063         return true;
2064 }
2065
2066 static int index_iterator_skip_pseudotree(index_iterator *iter)
2067 {
2068         assert(iterator__has_been_accessed(&iter->base));
2069         assert(S_ISDIR(iter->entry->mode));
2070
2071         while (true) {
2072                 const git_index_entry *next_entry = NULL;
2073
2074                 if (++iter->next_idx >= iter->entries.length)
2075                         return GIT_ITEROVER;
2076
2077                 next_entry = iter->entries.contents[iter->next_idx];
2078
2079                 if (iter->base.strncomp(iter->tree_buf.ptr, next_entry->path,
2080                         iter->tree_buf.size) != 0)
2081                         break;
2082         }
2083
2084         iter->skip_tree = false;
2085         return 0;
2086 }
2087
2088 static int index_iterator_advance(
2089         const git_index_entry **out, git_iterator *i)
2090 {
2091         index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2092         const git_index_entry *entry = NULL;
2093         bool is_submodule;
2094         int error = 0;
2095
2096         iter->base.flags |= GIT_ITERATOR_FIRST_ACCESS;
2097
2098         while (true) {
2099                 if (iter->next_idx >= iter->entries.length) {
2100                         error = GIT_ITEROVER;
2101                         break;
2102                 }
2103
2104                 /* we were not asked to expand this pseudotree.  advance over it. */
2105                 if (iter->skip_tree) {
2106                         index_iterator_skip_pseudotree(iter);
2107                         continue;
2108                 }
2109
2110                 entry = iter->entries.contents[iter->next_idx];
2111                 is_submodule = S_ISGITLINK(entry->mode);
2112
2113                 if (!iterator_has_started(&iter->base, entry->path, is_submodule)) {
2114                         iter->next_idx++;
2115                         continue;
2116                 }
2117
2118                 if (iterator_has_ended(&iter->base, entry->path)) {
2119                         error = GIT_ITEROVER;
2120                         break;
2121                 }
2122
2123                 /* if we have a list of paths we're interested in, examine it */
2124                 if (!iterator_pathlist_next_is(&iter->base, entry->path)) {
2125                         iter->next_idx++;
2126                         continue;
2127                 }
2128
2129                 /* if this is a conflict, skip it unless we're including conflicts */
2130                 if (git_index_entry_is_conflict(entry) &&
2131                         !iterator__include_conflicts(&iter->base)) {
2132                         iter->next_idx++;
2133                         continue;
2134                 }
2135
2136                 /* we've found what will be our next _file_ entry.  but if we are
2137                  * returning trees entries, we may need to return a pseudotree
2138                  * entry that will contain this.  don't advance over this entry,
2139                  * though, we still need to return it on the next `advance`.
2140                  */
2141                 if (iterator__include_trees(&iter->base) &&
2142                         index_iterator_create_pseudotree(&entry, iter, entry->path)) {
2143
2144                         /* Note whether this pseudo tree should be expanded or not */
2145                         iter->skip_tree = iterator__dont_autoexpand(&iter->base);
2146                         break;
2147                 }
2148
2149                 iter->next_idx++;
2150                 break;
2151         }
2152
2153         iter->entry = (error == 0) ? entry : NULL;
2154
2155         if (out)
2156                 *out = iter->entry;
2157
2158         return error;
2159 }
2160
2161 static int index_iterator_advance_into(
2162         const git_index_entry **out, git_iterator *i)
2163 {
2164         index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2165
2166         if (! S_ISDIR(iter->tree_entry.mode)) {
2167                 if (out)
2168                         *out = NULL;
2169
2170                 return 0;
2171         }
2172
2173         iter->skip_tree = false;
2174         return index_iterator_advance(out, i);
2175 }
2176
2177 static int index_iterator_advance_over(
2178         const git_index_entry **out,
2179         git_iterator_status_t *status,
2180         git_iterator *i)
2181 {
2182         index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2183         const git_index_entry *entry;
2184         int error;
2185
2186         if ((error = index_iterator_current(&entry, i)) < 0)
2187                 return error;
2188
2189         if (S_ISDIR(entry->mode))
2190                 index_iterator_skip_pseudotree(iter);
2191
2192         *status = GIT_ITERATOR_STATUS_NORMAL;
2193         return index_iterator_advance(out, i);
2194 }
2195
2196 static void index_iterator_clear(index_iterator *iter)
2197 {
2198         iterator_clear(&iter->base);
2199 }
2200
2201 static int index_iterator_init(index_iterator *iter)
2202 {
2203         iter->base.flags &= ~GIT_ITERATOR_FIRST_ACCESS;
2204         iter->next_idx = 0;
2205         iter->skip_tree = false;
2206         return 0;
2207 }
2208
2209 static int index_iterator_reset(git_iterator *i)
2210 {
2211         index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2212
2213         index_iterator_clear(iter);
2214         return index_iterator_init(iter);
2215 }
2216
2217 static void index_iterator_free(git_iterator *i)
2218 {
2219         index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2220
2221         git_index_snapshot_release(&iter->entries, iter->base.index);
2222         git_buf_dispose(&iter->tree_buf);
2223 }
2224
2225 int git_iterator_for_index(
2226         git_iterator **out,
2227         git_repository *repo,
2228         git_index  *index,
2229         git_iterator_options *options)
2230 {
2231         index_iterator *iter;
2232         int error;
2233
2234         static git_iterator_callbacks callbacks = {
2235                 index_iterator_current,
2236                 index_iterator_advance,
2237                 index_iterator_advance_into,
2238                 index_iterator_advance_over,
2239                 index_iterator_reset,
2240                 index_iterator_free
2241         };
2242
2243         *out = NULL;
2244
2245         if (index == NULL)
2246                 return git_iterator_for_nothing(out, options);
2247
2248         iter = git__calloc(1, sizeof(index_iterator));
2249         GIT_ERROR_CHECK_ALLOC(iter);
2250
2251         iter->base.type = GIT_ITERATOR_INDEX;
2252         iter->base.cb = &callbacks;
2253
2254         if ((error = iterator_init_common(&iter->base, repo, index, options)) < 0 ||
2255                 (error = git_index_snapshot_new(&iter->entries, index)) < 0 ||
2256                 (error = index_iterator_init(iter)) < 0)
2257                 goto on_error;
2258
2259         git_vector_set_cmp(&iter->entries, iterator__ignore_case(&iter->base) ?
2260                 git_index_entry_icmp : git_index_entry_cmp);
2261         git_vector_sort(&iter->entries);
2262
2263         *out = &iter->base;
2264         return 0;
2265
2266 on_error:
2267         git_iterator_free(&iter->base);
2268         return error;
2269 }
2270
2271
2272 /* Iterator API */
2273
2274 int git_iterator_reset_range(
2275         git_iterator *i, const char *start, const char *end)
2276 {
2277         if (iterator_reset_range(i, start, end) < 0)
2278                 return -1;
2279
2280         return i->cb->reset(i);
2281 }
2282
2283 void git_iterator_set_ignore_case(git_iterator *i, bool ignore_case)
2284 {
2285         assert(!iterator__has_been_accessed(i));
2286         iterator_set_ignore_case(i, ignore_case);
2287 }
2288
2289 void git_iterator_free(git_iterator *iter)
2290 {
2291         if (iter == NULL)
2292                 return;
2293
2294         iter->cb->free(iter);
2295
2296         git_vector_free(&iter->pathlist);
2297         git__free(iter->start);
2298         git__free(iter->end);
2299
2300         memset(iter, 0, sizeof(*iter));
2301
2302         git__free(iter);
2303 }
2304
2305 int git_iterator_foreach(
2306         git_iterator *iterator,
2307         git_iterator_foreach_cb cb,
2308         void *data)
2309 {
2310         const git_index_entry *iterator_item;
2311         int error = 0;
2312
2313         if ((error = git_iterator_current(&iterator_item, iterator)) < 0)
2314                 goto done;
2315
2316         if ((error = cb(iterator_item, data)) != 0)
2317                 goto done;
2318
2319         while (true) {
2320                 if ((error = git_iterator_advance(&iterator_item, iterator)) < 0)
2321                         goto done;
2322
2323                 if ((error = cb(iterator_item, data)) != 0)
2324                         goto done;
2325         }
2326
2327 done:
2328         if (error == GIT_ITEROVER)
2329                 error = 0;
2330
2331         return error;
2332 }
2333
2334 int git_iterator_walk(
2335         git_iterator **iterators,
2336         size_t cnt,
2337         git_iterator_walk_cb cb,
2338         void *data)
2339 {
2340         const git_index_entry **iterator_item;  /* next in each iterator */
2341         const git_index_entry **cur_items;              /* current path in each iter */
2342         const git_index_entry *first_match;
2343         size_t i, j;
2344         int error = 0;
2345
2346         iterator_item = git__calloc(cnt, sizeof(git_index_entry *));
2347         cur_items = git__calloc(cnt, sizeof(git_index_entry *));
2348
2349         GIT_ERROR_CHECK_ALLOC(iterator_item);
2350         GIT_ERROR_CHECK_ALLOC(cur_items);
2351
2352         /* Set up the iterators */
2353         for (i = 0; i < cnt; i++) {
2354                 error = git_iterator_current(&iterator_item[i], iterators[i]);
2355
2356                 if (error < 0 && error != GIT_ITEROVER)
2357                         goto done;
2358         }
2359
2360         while (true) {
2361                 for (i = 0; i < cnt; i++)
2362                         cur_items[i] = NULL;
2363
2364                 first_match = NULL;
2365
2366                 /* Find the next path(s) to consume from each iterator */
2367                 for (i = 0; i < cnt; i++) {
2368                         if (iterator_item[i] == NULL)
2369                                 continue;
2370
2371                         if (first_match == NULL) {
2372                                 first_match = iterator_item[i];
2373                                 cur_items[i] = iterator_item[i];
2374                         } else {
2375                                 int path_diff = git_index_entry_cmp(iterator_item[i], first_match);
2376
2377                                 if (path_diff < 0) {
2378                                         /* Found an index entry that sorts before the one we're
2379                                          * looking at.  Forget that we've seen the other and
2380                                          * look at the other iterators for this path.
2381                                          */
2382                                         for (j = 0; j < i; j++)
2383                                                 cur_items[j] = NULL;
2384
2385                                         first_match = iterator_item[i];
2386                                         cur_items[i] = iterator_item[i];
2387                                 } else if (path_diff == 0) {
2388                                         cur_items[i] = iterator_item[i];
2389                                 }
2390                         }
2391                 }
2392
2393                 if (first_match == NULL)
2394                         break;
2395
2396                 if ((error = cb(cur_items, data)) != 0)
2397                         goto done;
2398
2399                 /* Advance each iterator that participated */
2400                 for (i = 0; i < cnt; i++) {
2401                         if (cur_items[i] == NULL)
2402                                 continue;
2403
2404                         error = git_iterator_advance(&iterator_item[i], iterators[i]);
2405
2406                         if (error < 0 && error != GIT_ITEROVER)
2407                                 goto done;
2408                 }
2409         }
2410
2411 done:
2412         git__free((git_index_entry **)iterator_item);
2413         git__free((git_index_entry **)cur_items);
2414
2415         if (error == GIT_ITEROVER)
2416                 error = 0;
2417
2418         return error;
2419 }