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 #include "tree.h"
  10 #include "ignore.h"
  11 #include "buffer.h"
  12 #include "git2/submodule.h"
  13 #include <ctype.h>
  14
  15 #define ITERATOR_SET_CB(P,NAME_LC) do { \
  16         (P)->cb.current = NAME_LC ## _iterator__current; \
  17         (P)->cb.at_end  = NAME_LC ## _iterator__at_end; \
  18         (P)->cb.advance = NAME_LC ## _iterator__advance; \
  19         (P)->cb.seek    = NAME_LC ## _iterator__seek; \
  20         (P)->cb.reset   = NAME_LC ## _iterator__reset; \
  21         (P)->cb.free    = NAME_LC ## _iterator__free; \
  22         } while (0)
  23
  24 #define ITERATOR_BASE_INIT(P,NAME_LC,NAME_UC) do { \
  25         (P) = git__calloc(1, sizeof(NAME_LC ## _iterator)); \
  26         GITERR_CHECK_ALLOC(P); \
  27         (P)->base.type    = GIT_ITERATOR_TYPE_ ## NAME_UC; \
  28         (P)->base.cb    = &(P)->cb; \
  29         ITERATOR_SET_CB(P,NAME_LC); \
  30         (P)->base.start   = start ? git__strdup(start) : NULL; \
  31         (P)->base.end     = end ? git__strdup(end) : NULL; \
  32         if ((start && !(P)->base.start) || (end && !(P)->base.end)) { \
  33                 git__free(P); return -1; } \
  34         (P)->base.prefixcomp = git__prefixcmp; \
  35         } while (0)
  36
  37 static int iterator__reset_range(
  38         git_iterator *iter, const char *start, const char *end)
  39 {
  40         if (start) {
  41                 if (iter->start)
  42                         git__free(iter->start);
  43                 iter->start = git__strdup(start);
  44                 GITERR_CHECK_ALLOC(iter->start);
  45         }
  46
  47         if (end) {
  48                 if (iter->end)
  49                         git__free(iter->end);
  50                 iter->end = git__strdup(end);
  51                 GITERR_CHECK_ALLOC(iter->end);
  52         }
  53
  54         return 0;
  55 }
  56
  57 static int iterator_update_ignore_case(
  58         git_iterator *iter,
  59         git_iterator_flag_t flags)
  60 {
  61         int error = 0, ignore_case = -1;
  62
  63         if ((flags & GIT_ITERATOR_IGNORE_CASE) != 0)
  64                 ignore_case = true;
  65         else if ((flags & GIT_ITERATOR_DONT_IGNORE_CASE) != 0)
  66                 ignore_case = false;
  67         else {
  68                 git_index *index;
  69
  70                 if (!(error = git_repository_index__weakptr(&index, iter->repo)))
  71                         ignore_case = (index->ignore_case != false);
  72         }
  73
  74         if (ignore_case > 0)
  75                 iter->flags = (iter->flags | GIT_ITERATOR_IGNORE_CASE);
  76         else if (ignore_case == 0)
  77                 iter->flags = (iter->flags & ~GIT_ITERATOR_IGNORE_CASE);
  78
  79         iter->prefixcomp = ((iter->flags & GIT_ITERATOR_IGNORE_CASE) != 0) ?
  80                 git__prefixcmp_icase : git__prefixcmp;
  81
  82         return error;
  83 }
  84
  85 static int empty_iterator__no_item(
  86         git_iterator *iter, const git_index_entry **entry)
  87 {
  88         GIT_UNUSED(iter);
  89         *entry = NULL;
  90         return 0;
  91 }
  92
  93 static int empty_iterator__at_end(git_iterator *iter)
  94 {
  95         GIT_UNUSED(iter);
  96         return 1;
  97 }
  98
  99 static int empty_iterator__reset(
 100         git_iterator *iter, const char *start, const char *end)
 101 {
 102         GIT_UNUSED(iter); GIT_UNUSED(start); GIT_UNUSED(end);
 103         return 0;
 104 }
 105
 106 static int empty_iterator__seek(git_iterator *iter, const char *prefix)
 107 {
 108         GIT_UNUSED(iter); GIT_UNUSED(prefix);
 109         return -1;
 110 }
 111
 112 static void empty_iterator__free(git_iterator *iter)
 113 {
 114         GIT_UNUSED(iter);
 115 }
 116
 117 typedef struct {
 118         git_iterator base;
 119         git_iterator_callbacks cb;
 120 } empty_iterator;
 121
 122 int git_iterator_for_nothing(git_iterator **iter, git_iterator_flag_t flags)
 123 {
 124         empty_iterator *i = git__calloc(1, sizeof(empty_iterator));
 125         GITERR_CHECK_ALLOC(i);
 126
 127         i->base.type  = GIT_ITERATOR_TYPE_EMPTY;
 128         i->base.cb    = &i->cb;
 129         i->base.flags = flags;
 130         i->cb.current = empty_iterator__no_item;
 131         i->cb.at_end  = empty_iterator__at_end;
 132         i->cb.advance = empty_iterator__no_item;
 133         i->cb.seek    = empty_iterator__seek;
 134         i->cb.reset   = empty_iterator__reset;
 135         i->cb.free    = empty_iterator__free;
 136
 137         *iter = (git_iterator *)i;
 138
 139         return 0;
 140 }
 141
 142
 143 typedef struct tree_iterator_frame tree_iterator_frame;
 144 struct tree_iterator_frame {
 145         tree_iterator_frame *next, *prev;
 146         git_tree *tree;
 147         char *start;
 148         size_t startlen;
 149         size_t index;
 150         void **icase_map;
 151         void *icase_data[GIT_FLEX_ARRAY];
 152 };
 153
 154 typedef struct {
 155         git_iterator base;
 156         git_iterator_callbacks cb;
 157         tree_iterator_frame *stack, *tail;
 158         git_index_entry entry;
 159         git_buf path;
 160         bool path_has_filename;
 161 } tree_iterator;
 162
 163 GIT_INLINE(const git_tree_entry *)tree_iterator__tree_entry(tree_iterator *ti)
 164 {
 165         tree_iterator_frame *tf = ti->stack;
 166
 167         if (tf->index >= git_tree_entrycount(tf->tree))
 168                 return NULL;
 169
 170         return git_tree_entry_byindex(
 171                 tf->tree, tf->icase_map ? (size_t)tf->icase_map[tf->index] : tf->index);
 172 }
 173
 174 static char *tree_iterator__current_filename(
 175         tree_iterator *ti, const git_tree_entry *te)
 176 {
 177         if (!ti->path_has_filename) {
 178                 if (git_buf_joinpath(&ti->path, ti->path.ptr, te->filename) < 0)
 179                         return NULL;
 180                 ti->path_has_filename = true;
 181         }
 182
 183         return ti->path.ptr;
 184 }
 185
 186 static void tree_iterator__free_frame(tree_iterator_frame *tf)
 187 {
 188         if (!tf)
 189                 return;
 190
 191         git_tree_free(tf->tree);
 192         tf->tree = NULL;
 193
 194         git__free(tf);
 195 }
 196
 197 static bool tree_iterator__pop_frame(tree_iterator *ti)
 198 {
 199         tree_iterator_frame *tf = ti->stack;
 200
 201         /* don't free the initial tree/frame */
 202         if (!tf->next)
 203                 return false;
 204
 205         ti->stack = tf->next;
 206         ti->stack->prev = NULL;
 207
 208         tree_iterator__free_frame(tf);
 209
 210         return true;
 211 }
 212
 213 static int tree_iterator__to_end(tree_iterator *ti)
 214 {
 215         while (tree_iterator__pop_frame(ti)) /* pop all */;
 216         ti->stack->index = git_tree_entrycount(ti->stack->tree);
 217         return 0;
 218 }
 219
 220 static int tree_iterator__current(
 221         git_iterator *self, const git_index_entry **entry)
 222 {
 223         tree_iterator *ti = (tree_iterator *)self;
 224         const git_tree_entry *te = tree_iterator__tree_entry(ti);
 225
 226         if (entry)
 227                 *entry = NULL;
 228
 229         if (te == NULL)
 230                 return 0;
 231
 232         ti->entry.mode = te->attr;
 233         git_oid_cpy(&ti->entry.oid, &te->oid);
 234
 235         ti->entry.path = tree_iterator__current_filename(ti, te);
 236         if (ti->entry.path == NULL)
 237                 return -1;
 238
 239         if (ti->base.end && ti->base.prefixcomp(ti->entry.path, ti->base.end) > 0)
 240                 return tree_iterator__to_end(ti);
 241
 242         if (entry)
 243                 *entry = &ti->entry;
 244
 245         return 0;
 246 }
 247
 248 static int tree_iterator__at_end(git_iterator *self)
 249 {
 250         return (tree_iterator__tree_entry((tree_iterator *)self) == NULL);
 251 }
 252
 253 static int tree_iterator__icase_map_cmp(const void *a, const void *b, void *data)
 254 {
 255         git_tree *tree = data;
 256         const git_tree_entry *te1 = git_tree_entry_byindex(tree, (size_t)a);
 257         const git_tree_entry *te2 = git_tree_entry_byindex(tree, (size_t)b);
 258
 259         return te1 ? (te2 ? git_tree_entry_icmp(te1, te2) : 1) : -1;
 260 }
 261
 262 static int tree_iterator__frame_start_icmp(const void *key, const void *el)
 263 {
 264         const tree_iterator_frame *tf = (const tree_iterator_frame *)key;
 265         const git_tree_entry *te = git_tree_entry_byindex(tf->tree, (size_t)el);
 266         size_t minlen = min(tf->startlen, te->filename_len);
 267
 268         return git__strncasecmp(tf->start, te->filename, minlen);
 269 }
 270
 271 static void tree_iterator__frame_seek_start(tree_iterator_frame *tf)
 272 {
 273         if (!tf->start)
 274                 tf->index = 0;
 275         else if (!tf->icase_map)
 276                 tf->index = git_tree__prefix_position(tf->tree, tf->start);
 277         else {
 278                 if (!git__bsearch(
 279                                 tf->icase_map, git_tree_entrycount(tf->tree),
 280                                 tf, tree_iterator__frame_start_icmp, &tf->index))
 281                 {
 282                         while (tf->index > 0) {
 283                                 /* move back while previous entry is still prefixed */
 284                                 if (tree_iterator__frame_start_icmp(
 285                                                 tf, (const void *)(tf->index - 1)))
 286                                         break;
 287                                 tf->index--;
 288                         }
 289                 }
 290         }
 291 }
 292
 293 static tree_iterator_frame *tree_iterator__alloc_frame(
 294         tree_iterator *ti, git_tree *tree, char *start)
 295 {
 296         size_t i, max_i = git_tree_entrycount(tree);
 297         tree_iterator_frame *tf =
 298                 git__calloc(1, sizeof(tree_iterator_frame) + max_i * sizeof(void *));
 299         if (!tf)
 300                 return NULL;
 301
 302         tf->tree = tree;
 303
 304         if (start && *start) {
 305                 tf->start = start;
 306                 tf->startlen = strlen(start);
 307         }
 308
 309         if (!max_i)
 310                 return tf;
 311
 312         if ((ti->base.flags & GIT_ITERATOR_IGNORE_CASE) != 0) {
 313                 tf->icase_map = tf->icase_data;
 314
 315                 for (i = 0; i < max_i; ++i)
 316                         tf->icase_map[i] = (void *)i;
 317
 318                 git__tsort_r(
 319                         tf->icase_map, max_i, tree_iterator__icase_map_cmp, tf->tree);
 320         }
 321
 322         tree_iterator__frame_seek_start(tf);
 323
 324         return tf;
 325 }
 326
 327 static int tree_iterator__expand_tree(tree_iterator *ti)
 328 {
 329         int error;
 330         git_tree *subtree;
 331         const git_tree_entry *te = tree_iterator__tree_entry(ti);
 332         tree_iterator_frame *tf;
 333         char *relpath;
 334
 335         while (te != NULL && git_tree_entry__is_tree(te)) {
 336                 if (git_buf_joinpath(&ti->path, ti->path.ptr, te->filename) < 0)
 337                         return -1;
 338
 339                 /* check that we have not passed the range end */
 340                 if (ti->base.end != NULL &&
 341                         ti->base.prefixcomp(ti->path.ptr, ti->base.end) > 0)
 342                         return tree_iterator__to_end(ti);
 343
 344                 if ((error = git_tree_lookup(&subtree, ti->base.repo, &te->oid)) < 0)
 345                         return error;
 346
 347                 relpath = NULL;
 348
 349                 /* apply range start to new frame if relevant */
 350                 if (ti->stack->start &&
 351                         ti->base.prefixcomp(ti->stack->start, te->filename) == 0)
 352                 {
 353                         if (ti->stack->start[te->filename_len] == '/')
 354                                 relpath = ti->stack->start + te->filename_len + 1;
 355                 }
 356
 357                 if ((tf = tree_iterator__alloc_frame(ti, subtree, relpath)) == NULL)
 358                         return -1;
 359
 360                 tf->next  = ti->stack;
 361                 ti->stack = tf;
 362                 tf->next->prev = tf;
 363
 364                 te = tree_iterator__tree_entry(ti);
 365         }
 366
 367         return 0;
 368 }
 369
 370 static int tree_iterator__advance(
 371         git_iterator *self, const git_index_entry **entry)
 372 {
 373         int error = 0;
 374         tree_iterator *ti = (tree_iterator *)self;
 375         const git_tree_entry *te = NULL;
 376
 377         if (entry != NULL)
 378                 *entry = NULL;
 379
 380         if (ti->path_has_filename) {
 381                 git_buf_rtruncate_at_char(&ti->path, '/');
 382                 ti->path_has_filename = false;
 383         }
 384
 385         while (1) {
 386                 ++ti->stack->index;
 387
 388                 if ((te = tree_iterator__tree_entry(ti)) != NULL)
 389                         break;
 390
 391                 if (!tree_iterator__pop_frame(ti))
 392                         break; /* no frames left to pop */
 393
 394                 git_buf_rtruncate_at_char(&ti->path, '/');
 395         }
 396
 397         if (te && git_tree_entry__is_tree(te))
 398                 error = tree_iterator__expand_tree(ti);
 399
 400         if (!error)
 401                 error = tree_iterator__current(self, entry);
 402
 403         return error;
 404 }
 405
 406 static int tree_iterator__seek(git_iterator *self, const char *prefix)
 407 {
 408         GIT_UNUSED(self);
 409         GIT_UNUSED(prefix);
 410         /* pop stack until matches prefix */
 411         /* seek item in current frame matching prefix */
 412         /* push stack which matches prefix */
 413         return -1;
 414 }
 415
 416 static void tree_iterator__free(git_iterator *self)
 417 {
 418         tree_iterator *ti = (tree_iterator *)self;
 419
 420         while (tree_iterator__pop_frame(ti)) /* pop all */;
 421
 422         tree_iterator__free_frame(ti->stack);
 423         ti->stack = ti->tail = NULL;
 424
 425         git_buf_free(&ti->path);
 426 }
 427
 428 static int tree_iterator__reset(
 429         git_iterator *self, const char *start, const char *end)
 430 {
 431         tree_iterator *ti = (tree_iterator *)self;
 432
 433         while (tree_iterator__pop_frame(ti)) /* pop all */;
 434
 435         if (iterator__reset_range(self, start, end) < 0)
 436                 return -1;
 437
 438         /* reset start position */
 439         tree_iterator__frame_seek_start(ti->stack);
 440
 441         git_buf_clear(&ti->path);
 442         ti->path_has_filename = false;
 443
 444         return tree_iterator__expand_tree(ti);
 445 }
 446
 447 int git_iterator_for_tree_range(
 448         git_iterator **iter,
 449         git_tree *tree,
 450         git_iterator_flag_t flags,
 451         const char *start,
 452         const char *end)
 453 {
 454         int error;
 455         tree_iterator *ti;
 456
 457         if (tree == NULL)
 458                 return git_iterator_for_nothing(iter, flags);
 459
 460         if ((error = git_tree__dup(&tree, tree)) < 0)
 461                 return error;
 462
 463         ITERATOR_BASE_INIT(ti, tree, TREE);
 464
 465         ti->base.repo = git_tree_owner(tree);
 466
 467         if ((error = iterator_update_ignore_case((git_iterator *)ti, flags)) < 0)
 468                 goto fail;
 469
 470         ti->stack = ti->tail = tree_iterator__alloc_frame(ti, tree, ti->base.start);
 471
 472         if ((error = tree_iterator__expand_tree(ti)) < 0)
 473                 goto fail;
 474
 475         *iter = (git_iterator *)ti;
 476         return 0;
 477
 478 fail:
 479         git_iterator_free((git_iterator *)ti);
 480         return error;
 481 }
 482
 483
 484 typedef struct {
 485         git_iterator base;
 486         git_iterator_callbacks cb;
 487         git_index *index;
 488         size_t current;
 489 } index_iterator;
 490
 491 static int index_iterator__current(
 492         git_iterator *self, const git_index_entry **entry)
 493 {
 494         index_iterator *ii = (index_iterator *)self;
 495         const git_index_entry *ie = git_index_get_byindex(ii->index, ii->current);
 496
 497         if (entry)
 498                 *entry = ie;
 499
 500         return 0;
 501 }
 502
 503 static int index_iterator__at_end(git_iterator *self)
 504 {
 505         index_iterator *ii = (index_iterator *)self;
 506         return (ii->current >= git_index_entrycount(ii->index));
 507 }
 508
 509 static void index_iterator__skip_conflicts(
 510         index_iterator *ii)
 511 {
 512         size_t entrycount = git_index_entrycount(ii->index);
 513         const git_index_entry *ie;
 514
 515         while (ii->current < entrycount) {
 516                 ie = git_index_get_byindex(ii->index, ii->current);
 517
 518                 if (ie == NULL ||
 519                         (ii->base.end != NULL &&
 520                          ii->base.prefixcomp(ie->path, ii->base.end) > 0)) {
 521                         ii->current = entrycount;
 522                         break;
 523                 }
 524
 525                 if (git_index_entry_stage(ie) == 0)
 526                         break;
 527
 528                 ii->current++;
 529         }
 530 }
 531
 532 static int index_iterator__advance(
 533         git_iterator *self, const git_index_entry **entry)
 534 {
 535         index_iterator *ii = (index_iterator *)self;
 536
 537         if (ii->current < git_index_entrycount(ii->index))
 538                 ii->current++;
 539
 540         index_iterator__skip_conflicts(ii);
 541
 542         return index_iterator__current(self, entry);
 543 }
 544
 545 static int index_iterator__seek(git_iterator *self, const char *prefix)
 546 {
 547         GIT_UNUSED(self);
 548         GIT_UNUSED(prefix);
 549         /* find last item before prefix */
 550         return -1;
 551 }
 552
 553 static int index_iterator__reset(
 554         git_iterator *self, const char *start, const char *end)
 555 {
 556         index_iterator *ii = (index_iterator *)self;
 557         if (iterator__reset_range(self, start, end) < 0)
 558                 return -1;
 559         ii->current = ii->base.start ?
 560                 git_index__prefix_position(ii->index, ii->base.start) : 0;
 561         index_iterator__skip_conflicts(ii);
 562         return 0;
 563 }
 564
 565 static void index_iterator__free(git_iterator *self)
 566 {
 567         index_iterator *ii = (index_iterator *)self;
 568         git_index_free(ii->index);
 569         ii->index = NULL;
 570 }
 571
 572 int git_iterator_for_index_range(
 573         git_iterator **iter,
 574         git_index  *index,
 575         git_iterator_flag_t flags,
 576         const char *start,
 577         const char *end)
 578 {
 579         index_iterator *ii;
 580
 581         GIT_UNUSED(flags);
 582
 583         ITERATOR_BASE_INIT(ii, index, INDEX);
 584
 585         ii->base.repo = git_index_owner(index);
 586         if (index->ignore_case) {
 587                 ii->base.flags |= GIT_ITERATOR_IGNORE_CASE;
 588                 ii->base.prefixcomp = git__prefixcmp_icase;
 589         }
 590         ii->index = index;
 591         GIT_REFCOUNT_INC(index);
 592
 593         index_iterator__reset((git_iterator *)ii, NULL, NULL);
 594
 595         *iter = (git_iterator *)ii;
 596
 597         return 0;
 598 }
 599
 600
 601 typedef struct workdir_iterator_frame workdir_iterator_frame;
 602 struct workdir_iterator_frame {
 603         workdir_iterator_frame *next;
 604         git_vector entries;
 605         size_t index;
 606 };
 607
 608 typedef struct {
 609         git_iterator base;
 610         git_iterator_callbacks cb;
 611         workdir_iterator_frame *stack;
 612         int (*entrycmp)(const void *pfx, const void *item);
 613         git_ignores ignores;
 614         git_index_entry entry;
 615         git_buf path;
 616         size_t root_len;
 617         int is_ignored;
 618 } workdir_iterator;
 619
 620 GIT_INLINE(bool) path_is_dotgit(const git_path_with_stat *ps)
 621 {
 622         if (!ps)
 623                 return false;
 624         else {
 625                 const char *path = ps->path;
 626                 size_t len  = ps->path_len;
 627
 628                 if (len < 4)
 629                         return false;
 630                 if (path[len - 1] == '/')
 631                         len--;
 632                 if (tolower(path[len - 1]) != 't' ||
 633                         tolower(path[len - 2]) != 'i' ||
 634                         tolower(path[len - 3]) != 'g' ||
 635                         tolower(path[len - 4]) != '.')
 636                         return false;
 637                 return (len == 4 || path[len - 5] == '/');
 638         }
 639 }
 640
 641 static workdir_iterator_frame *workdir_iterator__alloc_frame(
 642         workdir_iterator *wi)
 643 {
 644         workdir_iterator_frame *wf = git__calloc(1, sizeof(workdir_iterator_frame));
 645         git_vector_cmp entry_compare = CASESELECT(
 646                 (wi->base.flags & GIT_ITERATOR_IGNORE_CASE) != 0,
 647                 git_path_with_stat_cmp_icase, git_path_with_stat_cmp);
 648
 649         if (wf == NULL)
 650                 return NULL;
 651
 652         if (git_vector_init(&wf->entries, 0, entry_compare) != 0) {
 653                 git__free(wf);
 654                 return NULL;
 655         }
 656
 657         return wf;
 658 }
 659
 660 static void workdir_iterator__free_frame(workdir_iterator_frame *wf)
 661 {
 662         unsigned int i;
 663         git_path_with_stat *path;
 664
 665         git_vector_foreach(&wf->entries, i, path)
 666                 git__free(path);
 667         git_vector_free(&wf->entries);
 668         git__free(wf);
 669 }
 670
 671 static int workdir_iterator__update_entry(workdir_iterator *wi);
 672
 673 static int workdir_iterator__entry_cmp_case(const void *pfx, const void *item)
 674 {
 675         const git_path_with_stat *ps = item;
 676         return git__prefixcmp((const char *)pfx, ps->path);
 677 }
 678
 679 static int workdir_iterator__entry_cmp_icase(const void *pfx, const void *item)
 680 {
 681         const git_path_with_stat *ps = item;
 682         return git__prefixcmp_icase((const char *)pfx, ps->path);
 683 }
 684
 685 static void workdir_iterator__seek_frame_start(
 686         workdir_iterator *wi, workdir_iterator_frame *wf)
 687 {
 688         if (!wf)
 689                 return;
 690
 691         if (wi->base.start)
 692                 git_vector_bsearch2(
 693                         &wf->index, &wf->entries, wi->entrycmp, wi->base.start);
 694         else
 695                 wf->index = 0;
 696
 697         if (path_is_dotgit(git_vector_get(&wf->entries, wf->index)))
 698                 wf->index++;
 699 }
 700
 701 static int workdir_iterator__expand_dir(workdir_iterator *wi)
 702 {
 703         int error;
 704         workdir_iterator_frame *wf = workdir_iterator__alloc_frame(wi);
 705         GITERR_CHECK_ALLOC(wf);
 706
 707         error = git_path_dirload_with_stat(
 708                 wi->path.ptr, wi->root_len,
 709                 (wi->base.flags & GIT_ITERATOR_IGNORE_CASE) != 0,
 710                 wi->base.start, wi->base.end, &wf->entries);
 711
 712         if (error < 0 || wf->entries.length == 0) {
 713                 workdir_iterator__free_frame(wf);
 714                 return GIT_ENOTFOUND;
 715         }
 716
 717         workdir_iterator__seek_frame_start(wi, wf);
 718
 719         /* only push new ignores if this is not top level directory */
 720         if (wi->stack != NULL) {
 721                 ssize_t slash_pos = git_buf_rfind_next(&wi->path, '/');
 722                 (void)git_ignore__push_dir(&wi->ignores, &wi->path.ptr[slash_pos + 1]);
 723         }
 724
 725         wf->next  = wi->stack;
 726         wi->stack = wf;
 727
 728         return workdir_iterator__update_entry(wi);
 729 }
 730
 731 static int workdir_iterator__current(
 732         git_iterator *self, const git_index_entry **entry)
 733 {
 734         workdir_iterator *wi = (workdir_iterator *)self;
 735         *entry = (wi->entry.path == NULL) ? NULL : &wi->entry;
 736         return 0;
 737 }
 738
 739 static int workdir_iterator__at_end(git_iterator *self)
 740 {
 741         return (((workdir_iterator *)self)->entry.path == NULL);
 742 }
 743
 744 static int workdir_iterator__advance(
 745         git_iterator *self, const git_index_entry **entry)
 746 {
 747         int error;
 748         workdir_iterator *wi = (workdir_iterator *)self;
 749         workdir_iterator_frame *wf;
 750         git_path_with_stat *next;
 751
 752         if (entry != NULL)
 753                 *entry = NULL;
 754
 755         if (wi->entry.path == NULL)
 756                 return 0;
 757
 758         while (1) {
 759                 wf   = wi->stack;
 760                 next = git_vector_get(&wf->entries, ++wf->index);
 761
 762                 if (next != NULL) {
 763                         /* match git's behavior of ignoring anything named ".git" */
 764                         if (path_is_dotgit(next))
 765                                 continue;
 766                         /* else found a good entry */
 767                         break;
 768                 }
 769
 770                 /* pop stack if anything is left to pop */
 771                 if (!wf->next) {
 772                         memset(&wi->entry, 0, sizeof(wi->entry));
 773                         return 0;
 774                 }
 775
 776                 wi->stack = wf->next;
 777                 workdir_iterator__free_frame(wf);
 778                 git_ignore__pop_dir(&wi->ignores);
 779         }
 780
 781         error = workdir_iterator__update_entry(wi);
 782
 783         if (!error && entry != NULL)
 784                 error = workdir_iterator__current(self, entry);
 785
 786         return error;
 787 }
 788
 789 static int workdir_iterator__seek(git_iterator *self, const char *prefix)
 790 {
 791         GIT_UNUSED(self);
 792         GIT_UNUSED(prefix);
 793         /* pop stack until matching prefix */
 794         /* find prefix item in current frame */
 795         /* push subdirectories as deep as possible while matching */
 796         return 0;
 797 }
 798
 799 static int workdir_iterator__reset(
 800         git_iterator *self, const char *start, const char *end)
 801 {
 802         workdir_iterator *wi = (workdir_iterator *)self;
 803
 804         while (wi->stack != NULL && wi->stack->next != NULL) {
 805                 workdir_iterator_frame *wf = wi->stack;
 806                 wi->stack = wf->next;
 807                 workdir_iterator__free_frame(wf);
 808                 git_ignore__pop_dir(&wi->ignores);
 809         }
 810
 811         if (iterator__reset_range(self, start, end) < 0)
 812                 return -1;
 813
 814         workdir_iterator__seek_frame_start(wi, wi->stack);
 815
 816         return workdir_iterator__update_entry(wi);
 817 }
 818
 819 static void workdir_iterator__free(git_iterator *self)
 820 {
 821         workdir_iterator *wi = (workdir_iterator *)self;
 822
 823         while (wi->stack != NULL) {
 824                 workdir_iterator_frame *wf = wi->stack;
 825                 wi->stack = wf->next;
 826                 workdir_iterator__free_frame(wf);
 827         }
 828
 829         git_ignore__free(&wi->ignores);
 830         git_buf_free(&wi->path);
 831 }
 832
 833 static int workdir_iterator__update_entry(workdir_iterator *wi)
 834 {
 835         git_path_with_stat *ps =
 836                 git_vector_get(&wi->stack->entries, wi->stack->index);
 837
 838         git_buf_truncate(&wi->path, wi->root_len);
 839         memset(&wi->entry, 0, sizeof(wi->entry));
 840
 841         if (!ps)
 842                 return 0;
 843
 844         if (git_buf_put(&wi->path, ps->path, ps->path_len) < 0)
 845                 return -1;
 846
 847         if (wi->base.end &&
 848                 wi->base.prefixcomp(wi->path.ptr + wi->root_len, wi->base.end) > 0)
 849                 return 0;
 850
 851         wi->entry.path = ps->path;
 852
 853         /* skip over .git entries */
 854         if (path_is_dotgit(ps))
 855                 return workdir_iterator__advance((git_iterator *)wi, NULL);
 856
 857         wi->is_ignored = -1;
 858
 859         git_index_entry__init_from_stat(&wi->entry, &ps->st);
 860
 861         /* need different mode here to keep directories during iteration */
 862         wi->entry.mode = git_futils_canonical_mode(ps->st.st_mode);
 863
 864         /* if this is a file type we don't handle, treat as ignored */
 865         if (wi->entry.mode == 0) {
 866                 wi->is_ignored = 1;
 867                 return 0;
 868         }
 869
 870         /* detect submodules */
 871         if (S_ISDIR(wi->entry.mode)) {
 872                 int res = git_submodule_lookup(NULL, wi->base.repo, wi->entry.path);
 873                 bool is_submodule = (res == 0);
 874                 if (res == GIT_ENOTFOUND)
 875                         giterr_clear();
 876
 877                 /* if submodule, mark as GITLINK and remove trailing slash */
 878                 if (is_submodule) {
 879                         size_t len = strlen(wi->entry.path);
 880                         assert(wi->entry.path[len - 1] == '/');
 881                         wi->entry.path[len - 1] = '\0';
 882                         wi->entry.mode = S_IFGITLINK;
 883                 }
 884         }
 885
 886         return 0;
 887 }
 888
 889 int git_iterator_for_workdir_range(
 890         git_iterator **iter,
 891         git_repository *repo,
 892         git_iterator_flag_t flags,
 893         const char *start,
 894         const char *end)
 895 {
 896         int error;
 897         workdir_iterator *wi;
 898
 899         assert(iter && repo);
 900
 901         if ((error = git_repository__ensure_not_bare(
 902                         repo, "scan working directory")) < 0)
 903                 return error;
 904
 905         ITERATOR_BASE_INIT(wi, workdir, WORKDIR);
 906         wi->base.repo = repo;
 907
 908         if ((error = iterator_update_ignore_case((git_iterator *)wi, flags)) < 0)
 909                 goto fail;
 910
 911         if (git_buf_sets(&wi->path, git_repository_workdir(repo)) < 0 ||
 912                 git_path_to_dir(&wi->path) < 0 ||
 913                 git_ignore__for_path(repo, "", &wi->ignores) < 0)
 914         {
 915                 git__free(wi);
 916                 return -1;
 917         }
 918
 919         wi->root_len = wi->path.size;
 920         wi->entrycmp = (wi->base.flags & GIT_ITERATOR_IGNORE_CASE) != 0 ?
 921                 workdir_iterator__entry_cmp_icase : workdir_iterator__entry_cmp_case;
 922
 923         if ((error = workdir_iterator__expand_dir(wi)) < 0) {
 924                 if (error != GIT_ENOTFOUND)
 925                         goto fail;
 926                 giterr_clear();
 927         }
 928
 929         *iter = (git_iterator *)wi;
 930         return 0;
 931
 932 fail:
 933         git_iterator_free((git_iterator *)wi);
 934         return error;
 935 }
 936
 937
 938 typedef struct {
 939         /* replacement callbacks */
 940         git_iterator_callbacks cb;
 941         /* original iterator values */
 942         git_iterator_callbacks *orig;
 943         git_iterator_type_t orig_type;
 944         /* spoolandsort data */
 945         git_vector entries;
 946         git_pool entry_pool;
 947         git_pool string_pool;
 948         size_t position;
 949 } spoolandsort_callbacks;
 950
 951 static int spoolandsort_iterator__current(
 952         git_iterator *self, const git_index_entry **entry)
 953 {
 954         spoolandsort_callbacks *scb = (spoolandsort_callbacks *)self->cb;
 955
 956         *entry = (const git_index_entry *)
 957                 git_vector_get(&scb->entries, scb->position);
 958
 959         return 0;
 960 }
 961
 962 static int spoolandsort_iterator__at_end(git_iterator *self)
 963 {
 964         spoolandsort_callbacks *scb = (spoolandsort_callbacks *)self->cb;
 965
 966         return 0 == scb->entries.length || scb->entries.length - 1 <= scb->position;
 967 }
 968
 969 static int spoolandsort_iterator__advance(
 970         git_iterator *self, const git_index_entry **entry)
 971 {
 972         spoolandsort_callbacks *scb = (spoolandsort_callbacks *)self->cb;
 973
 974         *entry = (const git_index_entry *)
 975                 git_vector_get(&scb->entries, ++scb->position);
 976
 977         return 0;
 978 }
 979
 980 static int spoolandsort_iterator__seek(git_iterator *self, const char *prefix)
 981 {
 982         GIT_UNUSED(self);
 983         GIT_UNUSED(prefix);
 984
 985         return -1;
 986 }
 987
 988 static int spoolandsort_iterator__reset(
 989         git_iterator *self, const char *start, const char *end)
 990 {
 991         spoolandsort_callbacks *scb = (spoolandsort_callbacks *)self->cb;
 992
 993         GIT_UNUSED(start); GIT_UNUSED(end);
 994
 995         scb->position = 0;
 996
 997         return 0;
 998 }
 999
1000 static void spoolandsort_iterator__free_callbacks(spoolandsort_callbacks *scb)
1001 {
1002         git_pool_clear(&scb->string_pool);
1003         git_pool_clear(&scb->entry_pool);
1004         git_vector_free(&scb->entries);
1005         git__free(scb);
1006 }
1007
1008 void git_iterator_spoolandsort_pop(git_iterator *self)
1009 {
1010         spoolandsort_callbacks *scb = (spoolandsort_callbacks *)self->cb;
1011
1012         if (self->type != GIT_ITERATOR_TYPE_SPOOLANDSORT)
1013                 return;
1014
1015         self->cb   = scb->orig;
1016         self->type = scb->orig_type;
1017         self->flags ^= GIT_ITERATOR_IGNORE_CASE;
1018
1019         spoolandsort_iterator__free_callbacks(scb);
1020 }
1021
1022 static void spoolandsort_iterator__free(git_iterator *self)
1023 {
1024         git_iterator_spoolandsort_pop(self);
1025         self->cb->free(self);
1026 }
1027
1028 int git_iterator_spoolandsort_push(git_iterator *iter, bool ignore_case)
1029 {
1030         const git_index_entry *item;
1031         spoolandsort_callbacks *scb;
1032         int (*entrycomp)(const void *a, const void *b);
1033
1034         if (((iter->flags & GIT_ITERATOR_IGNORE_CASE) != 0) == (ignore_case != 0))
1035                 return 0;
1036
1037         if (iter->type == GIT_ITERATOR_TYPE_EMPTY) {
1038                 iter->flags = (iter->flags ^ GIT_ITERATOR_IGNORE_CASE);
1039                 return 0;
1040         }
1041
1042         scb = git__calloc(1, sizeof(spoolandsort_callbacks));
1043         GITERR_CHECK_ALLOC(scb);
1044
1045         ITERATOR_SET_CB(scb,spoolandsort);
1046
1047         scb->orig      = iter->cb;
1048         scb->orig_type = iter->type;
1049         scb->position  = 0;
1050
1051         entrycomp = ignore_case ? git_index_entry__cmp_icase : git_index_entry__cmp;
1052
1053         if (git_vector_init(&scb->entries, 16, entrycomp) < 0 ||
1054                 git_pool_init(&scb->entry_pool, sizeof(git_index_entry), 0) < 0 ||
1055                 git_pool_init(&scb->string_pool, 1, 0) < 0 ||
1056                 git_iterator_current(iter, &item) < 0)
1057                 goto fail;
1058
1059         while (item) {
1060                 git_index_entry *clone = git_pool_malloc(&scb->entry_pool, 1);
1061                 if (!clone)
1062                         goto fail;
1063
1064                 memcpy(clone, item, sizeof(git_index_entry));
1065
1066                 if (item->path) {
1067                         clone->path = git_pool_strdup(&scb->string_pool, item->path);
1068                         if (!clone->path)
1069                                 goto fail;
1070                 }
1071
1072                 if (git_vector_insert(&scb->entries, clone) < 0)
1073                         goto fail;
1074
1075                 if (git_iterator_advance(iter, &item) < 0)
1076                         goto fail;
1077         }
1078
1079         git_vector_sort(&scb->entries);
1080
1081         iter->cb   = (git_iterator_callbacks *)scb;
1082         iter->type = GIT_ITERATOR_TYPE_SPOOLANDSORT;
1083         iter->flags ^= GIT_ITERATOR_IGNORE_CASE;
1084
1085         return 0;
1086
1087 fail:
1088         spoolandsort_iterator__free_callbacks(scb);
1089         return -1;
1090 }
1091
1092
1093 void git_iterator_free(git_iterator *iter)
1094 {
1095         if (iter == NULL)
1096                 return;
1097
1098         iter->cb->free(iter);
1099
1100         git__free(iter->start);
1101         git__free(iter->end);
1102
1103         memset(iter, 0, sizeof(*iter));
1104
1105         git__free(iter);
1106 }
1107
1108 git_index *git_iterator_index_get_index(git_iterator *iter)
1109 {
1110         if (iter->type == GIT_ITERATOR_TYPE_INDEX)
1111                 return ((index_iterator *)iter)->index;
1112
1113         if (iter->type == GIT_ITERATOR_TYPE_SPOOLANDSORT &&
1114                 ((spoolandsort_callbacks *)iter->cb)->orig_type == GIT_ITERATOR_TYPE_INDEX)
1115                 return ((index_iterator *)iter)->index;
1116
1117         return NULL;
1118 }
1119
1120 git_iterator_type_t git_iterator_inner_type(git_iterator *iter)
1121 {
1122         if (iter->type == GIT_ITERATOR_TYPE_SPOOLANDSORT)
1123                 return ((spoolandsort_callbacks *)iter->cb)->orig_type;
1124
1125         return iter->type;
1126 }
1127
1128 int git_iterator_current_tree_entry(
1129         git_iterator *iter, const git_tree_entry **tree_entry)
1130 {
1131         *tree_entry = (iter->type != GIT_ITERATOR_TYPE_TREE) ? NULL :
1132                 tree_iterator__tree_entry((tree_iterator *)iter);
1133         return 0;
1134 }
1135
1136 int git_iterator_current_parent_tree(
1137         git_iterator *iter,
1138         const char *parent_path,
1139         const git_tree **tree_ptr)
1140 {
1141         tree_iterator *ti = (tree_iterator *)iter;
1142         tree_iterator_frame *tf;
1143         const char *scan = parent_path;
1144         int (*strncomp)(const char *a, const char *b, size_t sz);
1145
1146         if (iter->type != GIT_ITERATOR_TYPE_TREE || ti->stack == NULL)
1147                 goto notfound;
1148
1149         strncomp = ((iter->flags & GIT_ITERATOR_IGNORE_CASE) != 0) ?
1150                 git__strncasecmp : git__strncmp;
1151
1152         for (tf = ti->tail; tf != NULL; tf = tf->prev) {
1153                 const git_tree_entry *te;
1154
1155                 if (!*scan) {
1156                         *tree_ptr = tf->tree;
1157                         return 0;
1158                 }
1159
1160                 te = git_tree_entry_byindex(tf->tree,
1161                         tf->icase_map ? (size_t)tf->icase_map[tf->index] : tf->index);
1162
1163                 if (strncomp(scan, te->filename, te->filename_len) != 0)
1164                         goto notfound;
1165
1166                 scan += te->filename_len;
1167
1168                 if (*scan) {
1169                         if (*scan != '/')
1170                                 goto notfound;
1171                         scan++;
1172                 }
1173         }
1174
1175 notfound:
1176         *tree_ptr = NULL;
1177         return 0;
1178 }
1179
1180 int git_iterator_current_is_ignored(git_iterator *iter)
1181 {
1182         workdir_iterator *wi = (workdir_iterator *)iter;
1183
1184         if (iter->type != GIT_ITERATOR_TYPE_WORKDIR)
1185                 return 0;
1186
1187         if (wi->is_ignored != -1)
1188                 return wi->is_ignored;
1189
1190         if (git_ignore__lookup(&wi->ignores, wi->entry.path, &wi->is_ignored) < 0)
1191                 wi->is_ignored = 1;
1192
1193         return wi->is_ignored;
1194 }
1195
1196 int git_iterator_advance_into_directory(
1197         git_iterator *iter, const git_index_entry **entry)
1198 {
1199         workdir_iterator *wi = (workdir_iterator *)iter;
1200
1201         if (iter->type == GIT_ITERATOR_TYPE_WORKDIR &&
1202                 wi->entry.path &&
1203                 (wi->entry.mode == GIT_FILEMODE_TREE ||
1204                  wi->entry.mode == GIT_FILEMODE_COMMIT))
1205         {
1206                 if (workdir_iterator__expand_dir(wi) < 0)
1207                         /* if error loading or if empty, skip the directory. */
1208                         return workdir_iterator__advance(iter, entry);
1209         }
1210
1211         return entry ? git_iterator_current(iter, entry) : 0;
1212 }
1213
1214 int git_iterator_cmp(git_iterator *iter, const char *path_prefix)
1215 {
1216         const git_index_entry *entry;
1217
1218         /* a "done" iterator is after every prefix */
1219         if (git_iterator_current(iter, &entry) < 0 ||
1220                 entry == NULL)
1221                 return 1;
1222
1223         /* a NULL prefix is after any valid iterator */
1224         if (!path_prefix)
1225                 return -1;
1226
1227         return iter->prefixcomp(entry->path, path_prefix);
1228 }
1229
1230 int git_iterator_current_workdir_path(git_iterator *iter, git_buf **path)
1231 {
1232         workdir_iterator *wi = (workdir_iterator *)iter;
1233
1234         if (iter->type != GIT_ITERATOR_TYPE_WORKDIR || !wi->entry.path)
1235                 *path = NULL;
1236         else
1237                 *path = &wi->path;
1238
1239         return 0;
1240 }
1241