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