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                 GIT_ASSERT_WITH_RETVAL(p[path_len], ITERATOR_PATHLIST_NONE);
 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 int 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         GIT_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         return 0;
 710 }
 711
 712 static int tree_iterator_current(
 713         const git_index_entry **out, git_iterator *i)
 714 {
 715         tree_iterator *iter = (tree_iterator *)i;
 716
 717         if (!iterator__has_been_accessed(i))
 718                 return iter->base.cb->advance(out, i);
 719
 720         if (!iter->frames.size) {
 721                 *out = NULL;
 722                 return GIT_ITEROVER;
 723         }
 724
 725         *out = &iter->entry;
 726         return 0;
 727 }
 728
 729 static void tree_iterator_set_current(
 730         tree_iterator *iter,
 731         tree_iterator_frame *frame,
 732         tree_iterator_entry *entry)
 733 {
 734         git_tree_entry *tree_entry = entry->tree_entry;
 735
 736         frame->current = entry;
 737
 738         memset(&iter->entry, 0x0, sizeof(git_index_entry));
 739
 740         iter->entry.mode = tree_entry->attr;
 741         iter->entry.path = iter->entry_path.ptr;
 742         git_oid_cpy(&iter->entry.id, tree_entry->oid);
 743 }
 744
 745 static int tree_iterator_advance(const git_index_entry **out, git_iterator *i)
 746 {
 747         tree_iterator *iter = (tree_iterator *)i;
 748         int error = 0;
 749
 750         iter->base.flags |= GIT_ITERATOR_FIRST_ACCESS;
 751
 752         /* examine tree entries until we find the next one to return */
 753         while (true) {
 754                 tree_iterator_entry *prev_entry, *entry;
 755                 tree_iterator_frame *frame;
 756                 bool is_tree;
 757
 758                 if ((frame = tree_iterator_current_frame(iter)) == NULL) {
 759                         error = GIT_ITEROVER;
 760                         break;
 761                 }
 762
 763                 /* no more entries in this frame.  pop the frame out */
 764                 if (frame->next_idx == frame->entries.length) {
 765                         if ((error = tree_iterator_frame_pop(iter)) < 0)
 766                                 break;
 767
 768                         continue;
 769                 }
 770
 771                 /* we may have coalesced the contents of case-insensitively same-named
 772                  * directories, so do the sort now.
 773                  */
 774                 if (frame->next_idx == 0 && !git_vector_is_sorted(&frame->entries))
 775                         git_vector_sort(&frame->entries);
 776
 777                 /* we have more entries in the current frame, that's our next entry */
 778                 prev_entry = tree_iterator_current_entry(frame);
 779                 entry = frame->entries.contents[frame->next_idx];
 780                 frame->next_idx++;
 781
 782                 /* we can have collisions when iterating case insensitively.  (eg,
 783                  * 'A/a' and 'a/A').  squash this one if it's already been seen.
 784                  */
 785                 if (iterator__ignore_case(&iter->base) &&
 786                         prev_entry &&
 787                         tree_iterator_entry_cmp_icase(prev_entry, entry) == 0)
 788                         continue;
 789
 790                 if ((error = tree_iterator_compute_path(&iter->entry_path, entry)) < 0)
 791                         break;
 792
 793                 /* if this path is before our start, advance over this entry */
 794                 if (!iterator_has_started(&iter->base, iter->entry_path.ptr, false))
 795                         continue;
 796
 797                 /* if this path is after our end, stop */
 798                 if (iterator_has_ended(&iter->base, iter->entry_path.ptr)) {
 799                         error = GIT_ITEROVER;
 800                         break;
 801                 }
 802
 803                 /* if we have a list of paths we're interested in, examine it */
 804                 if (!iterator_pathlist_next_is(&iter->base, iter->entry_path.ptr))
 805                         continue;
 806
 807                 is_tree = git_tree_entry__is_tree(entry->tree_entry);
 808
 809                 /* if we are *not* including trees then advance over this entry */
 810                 if (is_tree && !iterator__include_trees(iter)) {
 811
 812                         /* if we've found a tree (and are not returning it to the caller)
 813                          * and we are autoexpanding, then we want to return the first
 814                          * child.  push the new directory and advance.
 815                          */
 816                         if (iterator__do_autoexpand(iter)) {
 817                                 if ((error = tree_iterator_frame_push(iter, entry)) < 0)
 818                                         break;
 819                         }
 820
 821                         continue;
 822                 }
 823
 824                 tree_iterator_set_current(iter, frame, entry);
 825
 826                 /* if we are autoexpanding, then push this as a new frame, so that
 827                  * the next call to `advance` will dive into this directory.
 828                  */
 829                 if (is_tree && iterator__do_autoexpand(iter))
 830                         error = tree_iterator_frame_push(iter, entry);
 831
 832                 break;
 833         }
 834
 835         if (out)
 836                 *out = (error == 0) ? &iter->entry : NULL;
 837
 838         return error;
 839 }
 840
 841 static int tree_iterator_advance_into(
 842         const git_index_entry **out, git_iterator *i)
 843 {
 844         tree_iterator *iter = (tree_iterator *)i;
 845         tree_iterator_frame *frame;
 846         tree_iterator_entry *prev_entry;
 847         int error;
 848
 849         if (out)
 850                 *out = NULL;
 851
 852         if ((frame = tree_iterator_current_frame(iter)) == NULL)
 853                 return GIT_ITEROVER;
 854
 855         /* get the last seen entry */
 856         prev_entry = tree_iterator_current_entry(frame);
 857
 858         /* it's legal to call advance_into when auto-expand is on.  in this case,
 859          * we will have pushed a new (empty) frame on to the stack for this
 860          * new directory.  since it's empty, its current_entry should be null.
 861          */
 862         GIT_ASSERT(iterator__do_autoexpand(i) ^ (prev_entry != NULL));
 863
 864         if (prev_entry) {
 865                 if (!git_tree_entry__is_tree(prev_entry->tree_entry))
 866                         return 0;
 867
 868                 if ((error = tree_iterator_frame_push(iter, prev_entry)) < 0)
 869                         return error;
 870         }
 871
 872         /* we've advanced into the directory in question, let advance
 873          * find the first entry
 874          */
 875         return tree_iterator_advance(out, i);
 876 }
 877
 878 static int tree_iterator_advance_over(
 879         const git_index_entry **out,
 880         git_iterator_status_t *status,
 881         git_iterator *i)
 882 {
 883         *status = GIT_ITERATOR_STATUS_NORMAL;
 884         return git_iterator_advance(out, i);
 885 }
 886
 887 static void tree_iterator_clear(tree_iterator *iter)
 888 {
 889         while (iter->frames.size)
 890                 tree_iterator_frame_pop(iter);
 891
 892         git_array_clear(iter->frames);
 893
 894         git_pool_clear(&iter->entry_pool);
 895         git_buf_clear(&iter->entry_path);
 896
 897         iterator_clear(&iter->base);
 898 }
 899
 900 static int tree_iterator_init(tree_iterator *iter)
 901 {
 902         int error;
 903
 904         if ((error = git_pool_init(&iter->entry_pool, sizeof(tree_iterator_entry))) < 0 ||
 905             (error = tree_iterator_frame_init(iter, iter->root, NULL)) < 0)
 906                 return error;
 907
 908         iter->base.flags &= ~GIT_ITERATOR_FIRST_ACCESS;
 909
 910         return 0;
 911 }
 912
 913 static int tree_iterator_reset(git_iterator *i)
 914 {
 915         tree_iterator *iter = (tree_iterator *)i;
 916
 917         tree_iterator_clear(iter);
 918         return tree_iterator_init(iter);
 919 }
 920
 921 static void tree_iterator_free(git_iterator *i)
 922 {
 923         tree_iterator *iter = (tree_iterator *)i;
 924
 925         tree_iterator_clear(iter);
 926
 927         git_tree_free(iter->root);
 928         git_buf_dispose(&iter->entry_path);
 929 }
 930
 931 int git_iterator_for_tree(
 932         git_iterator **out,
 933         git_tree *tree,
 934         git_iterator_options *options)
 935 {
 936         tree_iterator *iter;
 937         int error;
 938
 939         static git_iterator_callbacks callbacks = {
 940                 tree_iterator_current,
 941                 tree_iterator_advance,
 942                 tree_iterator_advance_into,
 943                 tree_iterator_advance_over,
 944                 tree_iterator_reset,
 945                 tree_iterator_free
 946         };
 947
 948         *out = NULL;
 949
 950         if (tree == NULL)
 951                 return git_iterator_for_nothing(out, options);
 952
 953         iter = git__calloc(1, sizeof(tree_iterator));
 954         GIT_ERROR_CHECK_ALLOC(iter);
 955
 956         iter->base.type = GIT_ITERATOR_TREE;
 957         iter->base.cb = &callbacks;
 958
 959         if ((error = iterator_init_common(&iter->base,
 960                         git_tree_owner(tree), NULL, options)) < 0 ||
 961                 (error = git_tree_dup(&iter->root, tree)) < 0 ||
 962                 (error = tree_iterator_init(iter)) < 0)
 963                 goto on_error;
 964
 965         *out = &iter->base;
 966         return 0;
 967
 968 on_error:
 969         git_iterator_free(&iter->base);
 970         return error;
 971 }
 972
 973 int git_iterator_current_tree_entry(
 974         const git_tree_entry **tree_entry, git_iterator *i)
 975 {
 976         tree_iterator *iter;
 977         tree_iterator_frame *frame;
 978         tree_iterator_entry *entry;
 979
 980         GIT_ASSERT(i->type == GIT_ITERATOR_TREE);
 981
 982         iter = (tree_iterator *)i;
 983
 984         frame = tree_iterator_current_frame(iter);
 985         entry = tree_iterator_current_entry(frame);
 986
 987         *tree_entry = entry->tree_entry;
 988         return 0;
 989 }
 990
 991 int git_iterator_current_parent_tree(
 992         const git_tree **parent_tree, git_iterator *i, size_t depth)
 993 {
 994         tree_iterator *iter;
 995         tree_iterator_frame *frame;
 996
 997         GIT_ASSERT(i->type == GIT_ITERATOR_TREE);
 998
 999         iter = (tree_iterator *)i;
1000
1001         GIT_ASSERT(depth < iter->frames.size);
1002         frame = &iter->frames.ptr[iter->frames.size-depth-1];
1003
1004         *parent_tree = frame->tree;
1005         return 0;
1006 }
1007
1008 /* Filesystem iterator */
1009
1010 typedef struct {
1011         struct stat st;
1012         size_t path_len;
1013         iterator_pathlist_search_t match;
1014         git_oid id;
1015         char path[GIT_FLEX_ARRAY];
1016 } filesystem_iterator_entry;
1017
1018 typedef struct {
1019         git_vector entries;
1020         git_pool entry_pool;
1021         size_t next_idx;
1022
1023         size_t path_len;
1024         int is_ignored;
1025 } filesystem_iterator_frame;
1026
1027 typedef struct {
1028         git_iterator base;
1029         char *root;
1030         size_t root_len;
1031
1032         unsigned int dirload_flags;
1033
1034         git_tree *tree;
1035         git_index *index;
1036         git_vector index_snapshot;
1037
1038         git_array_t(filesystem_iterator_frame) frames;
1039         git_ignores ignores;
1040
1041         /* info about the current entry */
1042         git_index_entry entry;
1043         git_buf current_path;
1044         int current_is_ignored;
1045
1046         /* temporary buffer for advance_over */
1047         git_buf tmp_buf;
1048 } filesystem_iterator;
1049
1050
1051 GIT_INLINE(filesystem_iterator_frame *) filesystem_iterator_parent_frame(
1052         filesystem_iterator *iter)
1053 {
1054         return iter->frames.size > 1 ?
1055                 &iter->frames.ptr[iter->frames.size-2] : NULL;
1056 }
1057
1058 GIT_INLINE(filesystem_iterator_frame *) filesystem_iterator_current_frame(
1059         filesystem_iterator *iter)
1060 {
1061         return iter->frames.size ? &iter->frames.ptr[iter->frames.size-1] : NULL;
1062 }
1063
1064 GIT_INLINE(filesystem_iterator_entry *) filesystem_iterator_current_entry(
1065         filesystem_iterator_frame *frame)
1066 {
1067         return frame->next_idx == 0 ?
1068                 NULL : frame->entries.contents[frame->next_idx-1];
1069 }
1070
1071 static int filesystem_iterator_entry_cmp(const void *_a, const void *_b)
1072 {
1073         const filesystem_iterator_entry *a = (const filesystem_iterator_entry *)_a;
1074         const filesystem_iterator_entry *b = (const filesystem_iterator_entry *)_b;
1075
1076         return git__strcmp(a->path, b->path);
1077 }
1078
1079 static int filesystem_iterator_entry_cmp_icase(const void *_a, const void *_b)
1080 {
1081         const filesystem_iterator_entry *a = (const filesystem_iterator_entry *)_a;
1082         const filesystem_iterator_entry *b = (const filesystem_iterator_entry *)_b;
1083
1084         return git__strcasecmp(a->path, b->path);
1085 }
1086
1087 #define FILESYSTEM_MAX_DEPTH 100
1088
1089 /**
1090  * Figure out if an entry is a submodule.
1091  *
1092  * We consider it a submodule if the path is listed as a submodule in
1093  * either the tree or the index.
1094  */
1095 static int filesystem_iterator_is_submodule(
1096         bool *out, filesystem_iterator *iter, const char *path, size_t path_len)
1097 {
1098         bool is_submodule = false;
1099         int error;
1100
1101         *out = false;
1102
1103         /* first see if this path is a submodule in HEAD */
1104         if (iter->tree) {
1105                 git_tree_entry *entry;
1106
1107                 error = git_tree_entry_bypath(&entry, iter->tree, path);
1108
1109                 if (error < 0 && error != GIT_ENOTFOUND)
1110                         return error;
1111
1112                 if (!error) {
1113                         is_submodule = (entry->attr == GIT_FILEMODE_COMMIT);
1114                         git_tree_entry_free(entry);
1115                 }
1116         }
1117
1118         if (!is_submodule && iter->base.index) {
1119                 size_t pos;
1120
1121                 error = git_index_snapshot_find(&pos,
1122                         &iter->index_snapshot, iter->base.entry_srch, path, path_len, 0);
1123
1124                 if (error < 0 && error != GIT_ENOTFOUND)
1125                         return error;
1126
1127                 if (!error) {
1128                         git_index_entry *e = git_vector_get(&iter->index_snapshot, pos);
1129                         is_submodule = (e->mode == GIT_FILEMODE_COMMIT);
1130                 }
1131         }
1132
1133         *out = is_submodule;
1134         return 0;
1135 }
1136
1137 static void filesystem_iterator_frame_push_ignores(
1138         filesystem_iterator *iter,
1139         filesystem_iterator_entry *frame_entry,
1140         filesystem_iterator_frame *new_frame)
1141 {
1142         filesystem_iterator_frame *previous_frame;
1143         const char *path = frame_entry ? frame_entry->path : "";
1144
1145         if (!iterator__honor_ignores(&iter->base))
1146                 return;
1147
1148         if (git_ignore__lookup(&new_frame->is_ignored,
1149                         &iter->ignores, path, GIT_DIR_FLAG_TRUE) < 0) {
1150                 git_error_clear();
1151                 new_frame->is_ignored = GIT_IGNORE_NOTFOUND;
1152         }
1153
1154         /* if this is not the top level directory... */
1155         if (frame_entry) {
1156                 const char *relative_path;
1157
1158                 previous_frame = filesystem_iterator_parent_frame(iter);
1159
1160                 /* push new ignores for files in this directory */
1161                 relative_path = frame_entry->path + previous_frame->path_len;
1162
1163                 /* inherit ignored from parent if no rule specified */
1164                 if (new_frame->is_ignored <= GIT_IGNORE_NOTFOUND)
1165                         new_frame->is_ignored = previous_frame->is_ignored;
1166
1167                 git_ignore__push_dir(&iter->ignores, relative_path);
1168         }
1169 }
1170
1171 static void filesystem_iterator_frame_pop_ignores(
1172         filesystem_iterator *iter)
1173 {
1174         if (iterator__honor_ignores(&iter->base))
1175                 git_ignore__pop_dir(&iter->ignores);
1176 }
1177
1178 GIT_INLINE(bool) filesystem_iterator_examine_path(
1179         bool *is_dir_out,
1180         iterator_pathlist_search_t *match_out,
1181         filesystem_iterator *iter,
1182         filesystem_iterator_entry *frame_entry,
1183         const char *path,
1184         size_t path_len)
1185 {
1186         bool is_dir = 0;
1187         iterator_pathlist_search_t match = ITERATOR_PATHLIST_FULL;
1188
1189         *is_dir_out = false;
1190         *match_out = ITERATOR_PATHLIST_NONE;
1191
1192         if (iter->base.start_len) {
1193                 int cmp = iter->base.strncomp(path, iter->base.start, path_len);
1194
1195                 /* we haven't stat'ed `path` yet, so we don't yet know if it's a
1196                  * directory or not.  special case if the current path may be a
1197                  * directory that matches the start prefix.
1198                  */
1199                 if (cmp == 0) {
1200                         if (iter->base.start[path_len] == '/')
1201                                 is_dir = true;
1202
1203                         else if (iter->base.start[path_len] != '\0')
1204                                 cmp = -1;
1205                 }
1206
1207                 if (cmp < 0)
1208                         return false;
1209         }
1210
1211         if (iter->base.end_len) {
1212                 int cmp = iter->base.strncomp(path, iter->base.end, iter->base.end_len);
1213
1214                 if (cmp > 0)
1215                         return false;
1216         }
1217
1218         /* if we have a pathlist that we're limiting to, examine this path now
1219          * to avoid a `stat` if we're not interested in the path.
1220          */
1221         if (iter->base.pathlist.length) {
1222                 /* if our parent was explicitly included, so too are we */
1223                 if (frame_entry && frame_entry->match != ITERATOR_PATHLIST_IS_PARENT)
1224                         match = ITERATOR_PATHLIST_FULL;
1225                 else
1226                         match = iterator_pathlist_search(&iter->base, path, path_len);
1227
1228                 if (match == ITERATOR_PATHLIST_NONE)
1229                         return false;
1230
1231                 /* Ensure that the pathlist entry lines up with what we expected */
1232                 if (match == ITERATOR_PATHLIST_IS_DIR ||
1233                         match == ITERATOR_PATHLIST_IS_PARENT)
1234                         is_dir = true;
1235         }
1236
1237         *is_dir_out = is_dir;
1238         *match_out = match;
1239         return true;
1240 }
1241
1242 GIT_INLINE(bool) filesystem_iterator_is_dot_git(
1243         filesystem_iterator *iter, const char *path, size_t path_len)
1244 {
1245         size_t len;
1246
1247         if (!iterator__ignore_dot_git(&iter->base))
1248                 return false;
1249
1250         if ((len = path_len) < 4)
1251                 return false;
1252
1253         if (path[len - 1] == '/')
1254                 len--;
1255
1256         if (git__tolower(path[len - 1]) != 't' ||
1257                 git__tolower(path[len - 2]) != 'i' ||
1258                 git__tolower(path[len - 3]) != 'g' ||
1259                 git__tolower(path[len - 4]) != '.')
1260                 return false;
1261
1262         return (len == 4 || path[len - 5] == '/');
1263 }
1264
1265 static int filesystem_iterator_entry_hash(
1266         filesystem_iterator *iter,
1267         filesystem_iterator_entry *entry)
1268 {
1269         git_buf fullpath = GIT_BUF_INIT;
1270         int error;
1271
1272         if (S_ISDIR(entry->st.st_mode)) {
1273                 memset(&entry->id, 0, GIT_OID_RAWSZ);
1274                 return 0;
1275         }
1276
1277         if (iter->base.type == GIT_ITERATOR_WORKDIR)
1278                 return git_repository_hashfile(&entry->id,
1279                         iter->base.repo, entry->path, GIT_OBJECT_BLOB, NULL);
1280
1281         if (!(error = git_buf_joinpath(&fullpath, iter->root, entry->path)) &&
1282             !(error = git_path_validate_workdir_buf(iter->base.repo, &fullpath)))
1283                 error = git_odb_hashfile(&entry->id, fullpath.ptr, GIT_OBJECT_BLOB);
1284
1285         git_buf_dispose(&fullpath);
1286         return error;
1287 }
1288
1289 static int filesystem_iterator_entry_init(
1290         filesystem_iterator_entry **out,
1291         filesystem_iterator *iter,
1292         filesystem_iterator_frame *frame,
1293         const char *path,
1294         size_t path_len,
1295         struct stat *statbuf,
1296         iterator_pathlist_search_t pathlist_match)
1297 {
1298         filesystem_iterator_entry *entry;
1299         size_t entry_size;
1300         int error = 0;
1301
1302         *out = NULL;
1303
1304         /* Make sure to append two bytes, one for the path's null
1305          * termination, one for a possible trailing '/' for folders.
1306          */
1307         GIT_ERROR_CHECK_ALLOC_ADD(&entry_size,
1308                 sizeof(filesystem_iterator_entry), path_len);
1309         GIT_ERROR_CHECK_ALLOC_ADD(&entry_size, entry_size, 2);
1310
1311         entry = git_pool_malloc(&frame->entry_pool, entry_size);
1312         GIT_ERROR_CHECK_ALLOC(entry);
1313
1314         entry->path_len = path_len;
1315         entry->match = pathlist_match;
1316         memcpy(entry->path, path, path_len);
1317         memcpy(&entry->st, statbuf, sizeof(struct stat));
1318
1319         /* Suffix directory paths with a '/' */
1320         if (S_ISDIR(entry->st.st_mode))
1321                 entry->path[entry->path_len++] = '/';
1322
1323         entry->path[entry->path_len] = '\0';
1324
1325         if (iter->base.flags & GIT_ITERATOR_INCLUDE_HASH)
1326                 error = filesystem_iterator_entry_hash(iter, entry);
1327
1328         if (!error)
1329                 *out = entry;
1330
1331         return error;
1332 }
1333
1334 static int filesystem_iterator_frame_push(
1335         filesystem_iterator *iter,
1336         filesystem_iterator_entry *frame_entry)
1337 {
1338         filesystem_iterator_frame *new_frame = NULL;
1339         git_path_diriter diriter = GIT_PATH_DIRITER_INIT;
1340         git_buf root = GIT_BUF_INIT;
1341         const char *path;
1342         filesystem_iterator_entry *entry;
1343         struct stat statbuf;
1344         size_t path_len;
1345         int error;
1346
1347         if (iter->frames.size == FILESYSTEM_MAX_DEPTH) {
1348                 git_error_set(GIT_ERROR_REPOSITORY,
1349                         "directory nesting too deep (%"PRIuZ")", iter->frames.size);
1350                 return -1;
1351         }
1352
1353         new_frame = git_array_alloc(iter->frames);
1354         GIT_ERROR_CHECK_ALLOC(new_frame);
1355
1356         memset(new_frame, 0, sizeof(filesystem_iterator_frame));
1357
1358         if (frame_entry)
1359                 git_buf_joinpath(&root, iter->root, frame_entry->path);
1360         else
1361                 git_buf_puts(&root, iter->root);
1362
1363         if (git_buf_oom(&root) ||
1364             git_path_validate_workdir_buf(iter->base.repo, &root) < 0) {
1365                 error = -1;
1366                 goto done;
1367         }
1368
1369         new_frame->path_len = frame_entry ? frame_entry->path_len : 0;
1370
1371         /* Any error here is equivalent to the dir not existing, skip over it */
1372         if ((error = git_path_diriter_init(
1373                         &diriter, root.ptr, iter->dirload_flags)) < 0) {
1374                 error = GIT_ENOTFOUND;
1375                 goto done;
1376         }
1377
1378         if ((error = git_vector_init(&new_frame->entries, 64,
1379                         iterator__ignore_case(&iter->base) ?
1380                         filesystem_iterator_entry_cmp_icase :
1381                         filesystem_iterator_entry_cmp)) < 0)
1382                 goto done;
1383
1384         if ((error = git_pool_init(&new_frame->entry_pool, 1)) < 0)
1385                 goto done;
1386
1387         /* check if this directory is ignored */
1388         filesystem_iterator_frame_push_ignores(iter, frame_entry, new_frame);
1389
1390         while ((error = git_path_diriter_next(&diriter)) == 0) {
1391                 iterator_pathlist_search_t pathlist_match = ITERATOR_PATHLIST_FULL;
1392                 bool dir_expected = false;
1393
1394                 if ((error = git_path_diriter_fullpath(&path, &path_len, &diriter)) < 0 ||
1395                     (error = git_path_validate_workdir_with_len(iter->base.repo, path, path_len)) < 0)
1396                         goto done;
1397
1398                 GIT_ASSERT(path_len > iter->root_len);
1399
1400                 /* remove the prefix if requested */
1401                 path += iter->root_len;
1402                 path_len -= iter->root_len;
1403
1404                 /* examine start / end and the pathlist to see if this path is in it.
1405                  * note that since we haven't yet stat'ed the path, we cannot know
1406                  * whether it's a directory yet or not, so this can give us an
1407                  * expected type (S_IFDIR or S_IFREG) that we should examine)
1408                  */
1409                 if (!filesystem_iterator_examine_path(&dir_expected, &pathlist_match,
1410                         iter, frame_entry, path, path_len))
1411                         continue;
1412
1413                 /* TODO: don't need to stat if assume unchanged for this path and
1414                  * we have an index, we can just copy the data out of it.
1415                  */
1416
1417                 if ((error = git_path_diriter_stat(&statbuf, &diriter)) < 0) {
1418                         /* file was removed between readdir and lstat */
1419                         if (error == GIT_ENOTFOUND)
1420                                 continue;
1421
1422                         /* treat the file as unreadable */
1423                         memset(&statbuf, 0, sizeof(statbuf));
1424                         statbuf.st_mode = GIT_FILEMODE_UNREADABLE;
1425
1426                         error = 0;
1427                 }
1428
1429                 iter->base.stat_calls++;
1430
1431                 /* Ignore wacky things in the filesystem */
1432                 if (!S_ISDIR(statbuf.st_mode) &&
1433                         !S_ISREG(statbuf.st_mode) &&
1434                         !S_ISLNK(statbuf.st_mode) &&
1435                         statbuf.st_mode != GIT_FILEMODE_UNREADABLE)
1436                         continue;
1437
1438                 if (filesystem_iterator_is_dot_git(iter, path, path_len))
1439                         continue;
1440
1441                 /* convert submodules to GITLINK and remove trailing slashes */
1442                 if (S_ISDIR(statbuf.st_mode)) {
1443                         bool submodule = false;
1444
1445                         if ((error = filesystem_iterator_is_submodule(&submodule,
1446                                         iter, path, path_len)) < 0)
1447                                 goto done;
1448
1449                         if (submodule)
1450                                 statbuf.st_mode = GIT_FILEMODE_COMMIT;
1451                 }
1452
1453                 /* Ensure that the pathlist entry lines up with what we expected */
1454                 else if (dir_expected)
1455                         continue;
1456
1457                 if ((error = filesystem_iterator_entry_init(&entry,
1458                         iter, new_frame, path, path_len, &statbuf, pathlist_match)) < 0)
1459                         goto done;
1460
1461                 git_vector_insert(&new_frame->entries, entry);
1462         }
1463
1464         if (error == GIT_ITEROVER)
1465                 error = 0;
1466
1467         /* sort now that directory suffix is added */
1468         git_vector_sort(&new_frame->entries);
1469
1470 done:
1471         if (error < 0)
1472                 git_array_pop(iter->frames);
1473
1474         git_buf_dispose(&root);
1475         git_path_diriter_free(&diriter);
1476         return error;
1477 }
1478
1479 GIT_INLINE(int) filesystem_iterator_frame_pop(filesystem_iterator *iter)
1480 {
1481         filesystem_iterator_frame *frame;
1482
1483         GIT_ASSERT(iter->frames.size);
1484
1485         frame = git_array_pop(iter->frames);
1486         filesystem_iterator_frame_pop_ignores(iter);
1487
1488         git_pool_clear(&frame->entry_pool);
1489         git_vector_free(&frame->entries);
1490
1491         return 0;
1492 }
1493
1494 static void filesystem_iterator_set_current(
1495         filesystem_iterator *iter,
1496         filesystem_iterator_entry *entry)
1497 {
1498         /*
1499          * Index entries are limited to 32 bit timestamps.  We can safely
1500          * cast this since workdir times are only used in the cache; any
1501          * mismatch will cause a hash recomputation which is unfortunate
1502          * but affects only people who set their filetimes to 2038.
1503          * (Same with the file size.)
1504          */
1505         iter->entry.ctime.seconds = (int32_t)entry->st.st_ctime;
1506         iter->entry.mtime.seconds = (int32_t)entry->st.st_mtime;
1507
1508 #if defined(GIT_USE_NSEC)
1509         iter->entry.ctime.nanoseconds = entry->st.st_ctime_nsec;
1510         iter->entry.mtime.nanoseconds = entry->st.st_mtime_nsec;
1511 #else
1512         iter->entry.ctime.nanoseconds = 0;
1513         iter->entry.mtime.nanoseconds = 0;
1514 #endif
1515
1516         iter->entry.dev = entry->st.st_dev;
1517         iter->entry.ino = entry->st.st_ino;
1518         iter->entry.mode = git_futils_canonical_mode(entry->st.st_mode);
1519         iter->entry.uid = entry->st.st_uid;
1520         iter->entry.gid = entry->st.st_gid;
1521         iter->entry.file_size = (uint32_t)entry->st.st_size;
1522
1523         if (iter->base.flags & GIT_ITERATOR_INCLUDE_HASH)
1524                 git_oid_cpy(&iter->entry.id, &entry->id);
1525
1526         iter->entry.path = entry->path;
1527
1528         iter->current_is_ignored = GIT_IGNORE_UNCHECKED;
1529 }
1530
1531 static int filesystem_iterator_current(
1532         const git_index_entry **out, git_iterator *i)
1533 {
1534         filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1535
1536         if (!iterator__has_been_accessed(i))
1537                 return iter->base.cb->advance(out, i);
1538
1539         if (!iter->frames.size) {
1540                 *out = NULL;
1541                 return GIT_ITEROVER;
1542         }
1543
1544         *out = &iter->entry;
1545         return 0;
1546 }
1547
1548 static int filesystem_iterator_is_dir(
1549         bool *is_dir,
1550         const filesystem_iterator *iter,
1551         const filesystem_iterator_entry *entry)
1552 {
1553         struct stat st;
1554         git_buf fullpath = GIT_BUF_INIT;
1555         int error = 0;
1556
1557         if (S_ISDIR(entry->st.st_mode)) {
1558                 *is_dir = 1;
1559                 goto done;
1560         }
1561
1562         if (!iterator__descend_symlinks(iter) || !S_ISLNK(entry->st.st_mode)) {
1563                 *is_dir = 0;
1564                 goto done;
1565         }
1566
1567         if ((error = git_buf_joinpath(&fullpath, iter->root, entry->path)) < 0 ||
1568             (error = git_path_validate_workdir_buf(iter->base.repo, &fullpath)) < 0 ||
1569             (error = p_stat(fullpath.ptr, &st)) < 0)
1570                 goto done;
1571
1572         *is_dir = S_ISDIR(st.st_mode);
1573
1574 done:
1575         git_buf_dispose(&fullpath);
1576         return error;
1577 }
1578
1579 static int filesystem_iterator_advance(
1580         const git_index_entry **out, git_iterator *i)
1581 {
1582         filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1583         bool is_dir;
1584         int error = 0;
1585
1586         iter->base.flags |= GIT_ITERATOR_FIRST_ACCESS;
1587
1588         /* examine filesystem entries until we find the next one to return */
1589         while (true) {
1590                 filesystem_iterator_frame *frame;
1591                 filesystem_iterator_entry *entry;
1592
1593                 if ((frame = filesystem_iterator_current_frame(iter)) == NULL) {
1594                         error = GIT_ITEROVER;
1595                         break;
1596                 }
1597
1598                 /* no more entries in this frame.  pop the frame out */
1599                 if (frame->next_idx == frame->entries.length) {
1600                         filesystem_iterator_frame_pop(iter);
1601                         continue;
1602                 }
1603
1604                 /* we have more entries in the current frame, that's our next entry */
1605                 entry = frame->entries.contents[frame->next_idx];
1606                 frame->next_idx++;
1607
1608                 if ((error = filesystem_iterator_is_dir(&is_dir, iter, entry)) < 0)
1609                         break;
1610
1611                 if (is_dir) {
1612                         if (iterator__do_autoexpand(iter)) {
1613                                 error = filesystem_iterator_frame_push(iter, entry);
1614
1615                                 /* may get GIT_ENOTFOUND due to races or permission problems
1616                                  * that we want to quietly swallow
1617                                  */
1618                                 if (error == GIT_ENOTFOUND)
1619                                         continue;
1620                                 else if (error < 0)
1621                                         break;
1622                         }
1623
1624                         if (!iterator__include_trees(iter))
1625                                 continue;
1626                 }
1627
1628                 filesystem_iterator_set_current(iter, entry);
1629                 break;
1630         }
1631
1632         if (out)
1633                 *out = (error == 0) ? &iter->entry : NULL;
1634
1635         return error;
1636 }
1637
1638 static int filesystem_iterator_advance_into(
1639         const git_index_entry **out, git_iterator *i)
1640 {
1641         filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1642         filesystem_iterator_frame *frame;
1643         filesystem_iterator_entry *prev_entry;
1644         int error;
1645
1646         if (out)
1647                 *out = NULL;
1648
1649         if ((frame = filesystem_iterator_current_frame(iter)) == NULL)
1650                 return GIT_ITEROVER;
1651
1652         /* get the last seen entry */
1653         prev_entry = filesystem_iterator_current_entry(frame);
1654
1655         /* it's legal to call advance_into when auto-expand is on.  in this case,
1656          * we will have pushed a new (empty) frame on to the stack for this
1657          * new directory.  since it's empty, its current_entry should be null.
1658          */
1659         GIT_ASSERT(iterator__do_autoexpand(i) ^ (prev_entry != NULL));
1660
1661         if (prev_entry) {
1662                 if (prev_entry->st.st_mode != GIT_FILEMODE_COMMIT &&
1663                         !S_ISDIR(prev_entry->st.st_mode))
1664                         return 0;
1665
1666                 if ((error = filesystem_iterator_frame_push(iter, prev_entry)) < 0)
1667                         return error;
1668         }
1669
1670         /* we've advanced into the directory in question, let advance
1671          * find the first entry
1672          */
1673         return filesystem_iterator_advance(out, i);
1674 }
1675
1676 int git_iterator_current_workdir_path(git_buf **out, git_iterator *i)
1677 {
1678         filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1679         const git_index_entry *entry;
1680
1681         if (i->type != GIT_ITERATOR_FS &&
1682                 i->type != GIT_ITERATOR_WORKDIR) {
1683                 *out = NULL;
1684                 return 0;
1685         }
1686
1687         git_buf_truncate(&iter->current_path, iter->root_len);
1688
1689         if (git_iterator_current(&entry, i) < 0 ||
1690                 git_buf_puts(&iter->current_path, entry->path) < 0)
1691                 return -1;
1692
1693         *out = &iter->current_path;
1694         return 0;
1695 }
1696
1697 GIT_INLINE(git_dir_flag) entry_dir_flag(git_index_entry *entry)
1698 {
1699 #if defined(GIT_WIN32) && !defined(__MINGW32__)
1700         return (entry && entry->mode) ?
1701                 (S_ISDIR(entry->mode) ? GIT_DIR_FLAG_TRUE : GIT_DIR_FLAG_FALSE) :
1702                 GIT_DIR_FLAG_UNKNOWN;
1703 #else
1704         GIT_UNUSED(entry);
1705         return GIT_DIR_FLAG_UNKNOWN;
1706 #endif
1707 }
1708
1709 static void filesystem_iterator_update_ignored(filesystem_iterator *iter)
1710 {
1711         filesystem_iterator_frame *frame;
1712         git_dir_flag dir_flag = entry_dir_flag(&iter->entry);
1713
1714         if (git_ignore__lookup(&iter->current_is_ignored,
1715                         &iter->ignores, iter->entry.path, dir_flag) < 0) {
1716                 git_error_clear();
1717                 iter->current_is_ignored = GIT_IGNORE_NOTFOUND;
1718         }
1719
1720         /* use ignore from containing frame stack */
1721         if (iter->current_is_ignored <= GIT_IGNORE_NOTFOUND) {
1722                 frame = filesystem_iterator_current_frame(iter);
1723                 iter->current_is_ignored = frame->is_ignored;
1724         }
1725 }
1726
1727 GIT_INLINE(bool) filesystem_iterator_current_is_ignored(
1728         filesystem_iterator *iter)
1729 {
1730         if (iter->current_is_ignored == GIT_IGNORE_UNCHECKED)
1731                 filesystem_iterator_update_ignored(iter);
1732
1733         return (iter->current_is_ignored == GIT_IGNORE_TRUE);
1734 }
1735
1736 bool git_iterator_current_is_ignored(git_iterator *i)
1737 {
1738         filesystem_iterator *iter = NULL;
1739
1740         if (i->type != GIT_ITERATOR_WORKDIR)
1741                 return false;
1742
1743         iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1744
1745         return filesystem_iterator_current_is_ignored(iter);
1746 }
1747
1748 bool git_iterator_current_tree_is_ignored(git_iterator *i)
1749 {
1750         filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1751         filesystem_iterator_frame *frame;
1752
1753         if (i->type != GIT_ITERATOR_WORKDIR)
1754                 return false;
1755
1756         frame = filesystem_iterator_current_frame(iter);
1757         return (frame->is_ignored == GIT_IGNORE_TRUE);
1758 }
1759
1760 static int filesystem_iterator_advance_over(
1761         const git_index_entry **out,
1762         git_iterator_status_t *status,
1763         git_iterator *i)
1764 {
1765         filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1766         filesystem_iterator_frame *current_frame;
1767         filesystem_iterator_entry *current_entry;
1768         const git_index_entry *entry = NULL;
1769         const char *base;
1770         int error = 0;
1771
1772         *out = NULL;
1773         *status = GIT_ITERATOR_STATUS_NORMAL;
1774
1775         GIT_ASSERT(iterator__has_been_accessed(i));
1776
1777         current_frame = filesystem_iterator_current_frame(iter);
1778         GIT_ASSERT(current_frame);
1779
1780         current_entry = filesystem_iterator_current_entry(current_frame);
1781         GIT_ASSERT(current_entry);
1782
1783         if ((error = git_iterator_current(&entry, i)) < 0)
1784                 return error;
1785
1786         if (!S_ISDIR(entry->mode)) {
1787                 if (filesystem_iterator_current_is_ignored(iter))
1788                         *status = GIT_ITERATOR_STATUS_IGNORED;
1789
1790                 return filesystem_iterator_advance(out, i);
1791         }
1792
1793         git_buf_clear(&iter->tmp_buf);
1794         if ((error = git_buf_puts(&iter->tmp_buf, entry->path)) < 0)
1795                 return error;
1796
1797         base = iter->tmp_buf.ptr;
1798
1799         /* scan inside the directory looking for files.  if we find nothing,
1800          * we will remain EMPTY.  if we find any ignored item, upgrade EMPTY to
1801          * IGNORED.  if we find a real actual item, upgrade all the way to NORMAL
1802          * and then stop.
1803          *
1804          * however, if we're here looking for a pathlist item (but are not
1805          * actually in the pathlist ourselves) then start at FILTERED instead of
1806          * EMPTY.  callers then know that this path was not something they asked
1807          * about.
1808          */
1809         *status = current_entry->match == ITERATOR_PATHLIST_IS_PARENT ?
1810                 GIT_ITERATOR_STATUS_FILTERED : GIT_ITERATOR_STATUS_EMPTY;
1811
1812         while (entry && !iter->base.prefixcomp(entry->path, base)) {
1813                 if (filesystem_iterator_current_is_ignored(iter)) {
1814                         /* if we found an explicitly ignored item, then update from
1815                          * EMPTY to IGNORED
1816                          */
1817                         *status = GIT_ITERATOR_STATUS_IGNORED;
1818                 } else if (S_ISDIR(entry->mode)) {
1819                         error = filesystem_iterator_advance_into(&entry, i);
1820
1821                         if (!error)
1822                                 continue;
1823
1824                         /* this directory disappeared, ignore it */
1825                         else if (error == GIT_ENOTFOUND)
1826                                 error = 0;
1827
1828                         /* a real error occurred */
1829                         else
1830                                 break;
1831                 } else {
1832                         /* we found a non-ignored item, treat parent as untracked */
1833                         *status = GIT_ITERATOR_STATUS_NORMAL;
1834                         break;
1835                 }
1836
1837                 if ((error = git_iterator_advance(&entry, i)) < 0)
1838                         break;
1839         }
1840
1841         /* wrap up scan back to base directory */
1842         while (entry && !iter->base.prefixcomp(entry->path, base)) {
1843                 if ((error = git_iterator_advance(&entry, i)) < 0)
1844                         break;
1845         }
1846
1847         if (!error)
1848                 *out = entry;
1849
1850         return error;
1851 }
1852
1853 static void filesystem_iterator_clear(filesystem_iterator *iter)
1854 {
1855         while (iter->frames.size)
1856                 filesystem_iterator_frame_pop(iter);
1857
1858         git_array_clear(iter->frames);
1859         git_ignore__free(&iter->ignores);
1860
1861         git_buf_dispose(&iter->tmp_buf);
1862
1863         iterator_clear(&iter->base);
1864 }
1865
1866 static int filesystem_iterator_init(filesystem_iterator *iter)
1867 {
1868         int error;
1869
1870         if (iterator__honor_ignores(&iter->base) &&
1871                 (error = git_ignore__for_path(iter->base.repo,
1872                         ".gitignore", &iter->ignores)) < 0)
1873                 return error;
1874
1875         if ((error = filesystem_iterator_frame_push(iter, NULL)) < 0)
1876                 return error;
1877
1878         iter->base.flags &= ~GIT_ITERATOR_FIRST_ACCESS;
1879
1880         return 0;
1881 }
1882
1883 static int filesystem_iterator_reset(git_iterator *i)
1884 {
1885         filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1886
1887         filesystem_iterator_clear(iter);
1888         return filesystem_iterator_init(iter);
1889 }
1890
1891 static void filesystem_iterator_free(git_iterator *i)
1892 {
1893         filesystem_iterator *iter = GIT_CONTAINER_OF(i, filesystem_iterator, base);
1894         git__free(iter->root);
1895         git_buf_dispose(&iter->current_path);
1896         git_tree_free(iter->tree);
1897         if (iter->index)
1898                 git_index_snapshot_release(&iter->index_snapshot, iter->index);
1899         filesystem_iterator_clear(iter);
1900 }
1901
1902 static int iterator_for_filesystem(
1903         git_iterator **out,
1904         git_repository *repo,
1905         const char *root,
1906         git_index *index,
1907         git_tree *tree,
1908         git_iterator_t type,
1909         git_iterator_options *options)
1910 {
1911         filesystem_iterator *iter;
1912         size_t root_len;
1913         int error;
1914
1915         static git_iterator_callbacks callbacks = {
1916                 filesystem_iterator_current,
1917                 filesystem_iterator_advance,
1918                 filesystem_iterator_advance_into,
1919                 filesystem_iterator_advance_over,
1920                 filesystem_iterator_reset,
1921                 filesystem_iterator_free
1922         };
1923
1924         *out = NULL;
1925
1926         if (root == NULL)
1927                 return git_iterator_for_nothing(out, options);
1928
1929         iter = git__calloc(1, sizeof(filesystem_iterator));
1930         GIT_ERROR_CHECK_ALLOC(iter);
1931
1932         iter->base.type = type;
1933         iter->base.cb = &callbacks;
1934
1935         root_len = strlen(root);
1936
1937         iter->root = git__malloc(root_len+2);
1938         GIT_ERROR_CHECK_ALLOC(iter->root);
1939
1940         memcpy(iter->root, root, root_len);
1941
1942         if (root_len == 0 || root[root_len-1] != '/') {
1943                 iter->root[root_len] = '/';
1944                 root_len++;
1945         }
1946         iter->root[root_len] = '\0';
1947         iter->root_len = root_len;
1948
1949         if ((error = git_buf_puts(&iter->current_path, iter->root)) < 0)
1950                 goto on_error;
1951
1952         if ((error = iterator_init_common(&iter->base, repo, index, options)) < 0)
1953                 goto on_error;
1954
1955         if (tree && (error = git_tree_dup(&iter->tree, tree)) < 0)
1956                 goto on_error;
1957
1958         if (index &&
1959                 (error = git_index_snapshot_new(&iter->index_snapshot, index)) < 0)
1960                 goto on_error;
1961
1962         iter->index = index;
1963         iter->dirload_flags =
1964                 (iterator__ignore_case(&iter->base) ? GIT_PATH_DIR_IGNORE_CASE : 0) |
1965                 (iterator__flag(&iter->base, PRECOMPOSE_UNICODE) ?
1966                          GIT_PATH_DIR_PRECOMPOSE_UNICODE : 0);
1967
1968         if ((error = filesystem_iterator_init(iter)) < 0)
1969                 goto on_error;
1970
1971         *out = &iter->base;
1972         return 0;
1973
1974 on_error:
1975         git_iterator_free(&iter->base);
1976         return error;
1977 }
1978
1979 int git_iterator_for_filesystem(
1980         git_iterator **out,
1981         const char *root,
1982         git_iterator_options *options)
1983 {
1984         return iterator_for_filesystem(out,
1985                 NULL, root, NULL, NULL, GIT_ITERATOR_FS, options);
1986 }
1987
1988 int git_iterator_for_workdir_ext(
1989         git_iterator **out,
1990         git_repository *repo,
1991         const char *repo_workdir,
1992         git_index *index,
1993         git_tree *tree,
1994         git_iterator_options *given_opts)
1995 {
1996         git_iterator_options options = GIT_ITERATOR_OPTIONS_INIT;
1997
1998         if (!repo_workdir) {
1999                 if (git_repository__ensure_not_bare(repo, "scan working directory") < 0)
2000                         return GIT_EBAREREPO;
2001
2002                 repo_workdir = git_repository_workdir(repo);
2003         }
2004
2005         /* upgrade to a workdir iterator, adding necessary internal flags */
2006         if (given_opts)
2007                 memcpy(&options, given_opts, sizeof(git_iterator_options));
2008
2009         options.flags |= GIT_ITERATOR_HONOR_IGNORES |
2010                 GIT_ITERATOR_IGNORE_DOT_GIT;
2011
2012         return iterator_for_filesystem(out,
2013                 repo, repo_workdir, index, tree, GIT_ITERATOR_WORKDIR, &options);
2014 }
2015
2016
2017 /* Index iterator */
2018
2019
2020 typedef struct {
2021         git_iterator base;
2022         git_vector entries;
2023         size_t next_idx;
2024
2025         /* the pseudotree entry */
2026         git_index_entry tree_entry;
2027         git_buf tree_buf;
2028         bool skip_tree;
2029
2030         const git_index_entry *entry;
2031 } index_iterator;
2032
2033 static int index_iterator_current(
2034         const git_index_entry **out, git_iterator *i)
2035 {
2036         index_iterator *iter = (index_iterator *)i;
2037
2038         if (!iterator__has_been_accessed(i))
2039                 return iter->base.cb->advance(out, i);
2040
2041         if (iter->entry == NULL) {
2042                 *out = NULL;
2043                 return GIT_ITEROVER;
2044         }
2045
2046         *out = iter->entry;
2047         return 0;
2048 }
2049
2050 static bool index_iterator_create_pseudotree(
2051         const git_index_entry **out,
2052         index_iterator *iter,
2053         const char *path)
2054 {
2055         const char *prev_path, *relative_path, *dirsep;
2056         size_t common_len;
2057
2058         prev_path = iter->entry ? iter->entry->path : "";
2059
2060         /* determine if the new path is in a different directory from the old */
2061         common_len = git_path_common_dirlen(prev_path, path);
2062         relative_path = path + common_len;
2063
2064         if ((dirsep = strchr(relative_path, '/')) == NULL)
2065                 return false;
2066
2067         git_buf_clear(&iter->tree_buf);
2068         git_buf_put(&iter->tree_buf, path, (dirsep - path) + 1);
2069
2070         iter->tree_entry.mode = GIT_FILEMODE_TREE;
2071         iter->tree_entry.path = iter->tree_buf.ptr;
2072
2073         *out = &iter->tree_entry;
2074         return true;
2075 }
2076
2077 static int index_iterator_skip_pseudotree(index_iterator *iter)
2078 {
2079         GIT_ASSERT(iterator__has_been_accessed(&iter->base));
2080         GIT_ASSERT(S_ISDIR(iter->entry->mode));
2081
2082         while (true) {
2083                 const git_index_entry *next_entry = NULL;
2084
2085                 if (++iter->next_idx >= iter->entries.length)
2086                         return GIT_ITEROVER;
2087
2088                 next_entry = iter->entries.contents[iter->next_idx];
2089
2090                 if (iter->base.strncomp(iter->tree_buf.ptr, next_entry->path,
2091                         iter->tree_buf.size) != 0)
2092                         break;
2093         }
2094
2095         iter->skip_tree = false;
2096         return 0;
2097 }
2098
2099 static int index_iterator_advance(
2100         const git_index_entry **out, git_iterator *i)
2101 {
2102         index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2103         const git_index_entry *entry = NULL;
2104         bool is_submodule;
2105         int error = 0;
2106
2107         iter->base.flags |= GIT_ITERATOR_FIRST_ACCESS;
2108
2109         while (true) {
2110                 if (iter->next_idx >= iter->entries.length) {
2111                         error = GIT_ITEROVER;
2112                         break;
2113                 }
2114
2115                 /* we were not asked to expand this pseudotree.  advance over it. */
2116                 if (iter->skip_tree) {
2117                         index_iterator_skip_pseudotree(iter);
2118                         continue;
2119                 }
2120
2121                 entry = iter->entries.contents[iter->next_idx];
2122                 is_submodule = S_ISGITLINK(entry->mode);
2123
2124                 if (!iterator_has_started(&iter->base, entry->path, is_submodule)) {
2125                         iter->next_idx++;
2126                         continue;
2127                 }
2128
2129                 if (iterator_has_ended(&iter->base, entry->path)) {
2130                         error = GIT_ITEROVER;
2131                         break;
2132                 }
2133
2134                 /* if we have a list of paths we're interested in, examine it */
2135                 if (!iterator_pathlist_next_is(&iter->base, entry->path)) {
2136                         iter->next_idx++;
2137                         continue;
2138                 }
2139
2140                 /* if this is a conflict, skip it unless we're including conflicts */
2141                 if (git_index_entry_is_conflict(entry) &&
2142                         !iterator__include_conflicts(&iter->base)) {
2143                         iter->next_idx++;
2144                         continue;
2145                 }
2146
2147                 /* we've found what will be our next _file_ entry.  but if we are
2148                  * returning trees entries, we may need to return a pseudotree
2149                  * entry that will contain this.  don't advance over this entry,
2150                  * though, we still need to return it on the next `advance`.
2151                  */
2152                 if (iterator__include_trees(&iter->base) &&
2153                         index_iterator_create_pseudotree(&entry, iter, entry->path)) {
2154
2155                         /* Note whether this pseudo tree should be expanded or not */
2156                         iter->skip_tree = iterator__dont_autoexpand(&iter->base);
2157                         break;
2158                 }
2159
2160                 iter->next_idx++;
2161                 break;
2162         }
2163
2164         iter->entry = (error == 0) ? entry : NULL;
2165
2166         if (out)
2167                 *out = iter->entry;
2168
2169         return error;
2170 }
2171
2172 static int index_iterator_advance_into(
2173         const git_index_entry **out, git_iterator *i)
2174 {
2175         index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2176
2177         if (! S_ISDIR(iter->tree_entry.mode)) {
2178                 if (out)
2179                         *out = NULL;
2180
2181                 return 0;
2182         }
2183
2184         iter->skip_tree = false;
2185         return index_iterator_advance(out, i);
2186 }
2187
2188 static int index_iterator_advance_over(
2189         const git_index_entry **out,
2190         git_iterator_status_t *status,
2191         git_iterator *i)
2192 {
2193         index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2194         const git_index_entry *entry;
2195         int error;
2196
2197         if ((error = index_iterator_current(&entry, i)) < 0)
2198                 return error;
2199
2200         if (S_ISDIR(entry->mode))
2201                 index_iterator_skip_pseudotree(iter);
2202
2203         *status = GIT_ITERATOR_STATUS_NORMAL;
2204         return index_iterator_advance(out, i);
2205 }
2206
2207 static void index_iterator_clear(index_iterator *iter)
2208 {
2209         iterator_clear(&iter->base);
2210 }
2211
2212 static int index_iterator_init(index_iterator *iter)
2213 {
2214         iter->base.flags &= ~GIT_ITERATOR_FIRST_ACCESS;
2215         iter->next_idx = 0;
2216         iter->skip_tree = false;
2217         return 0;
2218 }
2219
2220 static int index_iterator_reset(git_iterator *i)
2221 {
2222         index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2223
2224         index_iterator_clear(iter);
2225         return index_iterator_init(iter);
2226 }
2227
2228 static void index_iterator_free(git_iterator *i)
2229 {
2230         index_iterator *iter = GIT_CONTAINER_OF(i, index_iterator, base);
2231
2232         git_index_snapshot_release(&iter->entries, iter->base.index);
2233         git_buf_dispose(&iter->tree_buf);
2234 }
2235
2236 int git_iterator_for_index(
2237         git_iterator **out,
2238         git_repository *repo,
2239         git_index  *index,
2240         git_iterator_options *options)
2241 {
2242         index_iterator *iter;
2243         int error;
2244
2245         static git_iterator_callbacks callbacks = {
2246                 index_iterator_current,
2247                 index_iterator_advance,
2248                 index_iterator_advance_into,
2249                 index_iterator_advance_over,
2250                 index_iterator_reset,
2251                 index_iterator_free
2252         };
2253
2254         *out = NULL;
2255
2256         if (index == NULL)
2257                 return git_iterator_for_nothing(out, options);
2258
2259         iter = git__calloc(1, sizeof(index_iterator));
2260         GIT_ERROR_CHECK_ALLOC(iter);
2261
2262         iter->base.type = GIT_ITERATOR_INDEX;
2263         iter->base.cb = &callbacks;
2264
2265         if ((error = iterator_init_common(&iter->base, repo, index, options)) < 0 ||
2266                 (error = git_index_snapshot_new(&iter->entries, index)) < 0 ||
2267                 (error = index_iterator_init(iter)) < 0)
2268                 goto on_error;
2269
2270         git_vector_set_cmp(&iter->entries, iterator__ignore_case(&iter->base) ?
2271                 git_index_entry_icmp : git_index_entry_cmp);
2272         git_vector_sort(&iter->entries);
2273
2274         *out = &iter->base;
2275         return 0;
2276
2277 on_error:
2278         git_iterator_free(&iter->base);
2279         return error;
2280 }
2281
2282
2283 /* Iterator API */
2284
2285 int git_iterator_reset_range(
2286         git_iterator *i, const char *start, const char *end)
2287 {
2288         if (iterator_reset_range(i, start, end) < 0)
2289                 return -1;
2290
2291         return i->cb->reset(i);
2292 }
2293
2294 int git_iterator_set_ignore_case(git_iterator *i, bool ignore_case)
2295 {
2296         GIT_ASSERT(!iterator__has_been_accessed(i));
2297         iterator_set_ignore_case(i, ignore_case);
2298         return 0;
2299 }
2300
2301 void git_iterator_free(git_iterator *iter)
2302 {
2303         if (iter == NULL)
2304                 return;
2305
2306         iter->cb->free(iter);
2307
2308         git_vector_free(&iter->pathlist);
2309         git__free(iter->start);
2310         git__free(iter->end);
2311
2312         memset(iter, 0, sizeof(*iter));
2313
2314         git__free(iter);
2315 }
2316
2317 int git_iterator_foreach(
2318         git_iterator *iterator,
2319         git_iterator_foreach_cb cb,
2320         void *data)
2321 {
2322         const git_index_entry *iterator_item;
2323         int error = 0;
2324
2325         if ((error = git_iterator_current(&iterator_item, iterator)) < 0)
2326                 goto done;
2327
2328         if ((error = cb(iterator_item, data)) != 0)
2329                 goto done;
2330
2331         while (true) {
2332                 if ((error = git_iterator_advance(&iterator_item, iterator)) < 0)
2333                         goto done;
2334
2335                 if ((error = cb(iterator_item, data)) != 0)
2336                         goto done;
2337         }
2338
2339 done:
2340         if (error == GIT_ITEROVER)
2341                 error = 0;
2342
2343         return error;
2344 }
2345
2346 int git_iterator_walk(
2347         git_iterator **iterators,
2348         size_t cnt,
2349         git_iterator_walk_cb cb,
2350         void *data)
2351 {
2352         const git_index_entry **iterator_item;  /* next in each iterator */
2353         const git_index_entry **cur_items;              /* current path in each iter */
2354         const git_index_entry *first_match;
2355         size_t i, j;
2356         int error = 0;
2357
2358         iterator_item = git__calloc(cnt, sizeof(git_index_entry *));
2359         cur_items = git__calloc(cnt, sizeof(git_index_entry *));
2360
2361         GIT_ERROR_CHECK_ALLOC(iterator_item);
2362         GIT_ERROR_CHECK_ALLOC(cur_items);
2363
2364         /* Set up the iterators */
2365         for (i = 0; i < cnt; i++) {
2366                 error = git_iterator_current(&iterator_item[i], iterators[i]);
2367
2368                 if (error < 0 && error != GIT_ITEROVER)
2369                         goto done;
2370         }
2371
2372         while (true) {
2373                 for (i = 0; i < cnt; i++)
2374                         cur_items[i] = NULL;
2375
2376                 first_match = NULL;
2377
2378                 /* Find the next path(s) to consume from each iterator */
2379                 for (i = 0; i < cnt; i++) {
2380                         if (iterator_item[i] == NULL)
2381                                 continue;
2382
2383                         if (first_match == NULL) {
2384                                 first_match = iterator_item[i];
2385                                 cur_items[i] = iterator_item[i];
2386                         } else {
2387                                 int path_diff = git_index_entry_cmp(iterator_item[i], first_match);
2388
2389                                 if (path_diff < 0) {
2390                                         /* Found an index entry that sorts before the one we're
2391                                          * looking at.  Forget that we've seen the other and
2392                                          * look at the other iterators for this path.
2393                                          */
2394                                         for (j = 0; j < i; j++)
2395                                                 cur_items[j] = NULL;
2396
2397                                         first_match = iterator_item[i];
2398                                         cur_items[i] = iterator_item[i];
2399                                 } else if (path_diff == 0) {
2400                                         cur_items[i] = iterator_item[i];
2401                                 }
2402                         }
2403                 }
2404
2405                 if (first_match == NULL)
2406                         break;
2407
2408                 if ((error = cb(cur_items, data)) != 0)
2409                         goto done;
2410
2411                 /* Advance each iterator that participated */
2412                 for (i = 0; i < cnt; i++) {
2413                         if (cur_items[i] == NULL)
2414                                 continue;
2415
2416                         error = git_iterator_advance(&iterator_item[i], iterators[i]);
2417
2418                         if (error < 0 && error != GIT_ITEROVER)
2419                                 goto done;
2420                 }
2421         }
2422
2423 done:
2424         git__free((git_index_entry **)iterator_item);
2425         git__free((git_index_entry **)cur_items);
2426
2427         if (error == GIT_ITEROVER)
2428                 error = 0;
2429
2430         return error;
2431 }