{"thread":{"id":"45587","subject":"[PATCH v6 0/5] [GSoC] remove_subtree(): reimplement using iterators","startedAt":"2017-04-02T04:35:50Z","lastAt":"2017-04-02T05:36:10Z","messageCount":8,"participants":["Daniel Ferreira","Daniel Ferreira (theiostream)","Michael Haggerty"],"isPatch":true,"patchVersion":6,"patchTotal":5},"messages":[{"id":"316039","messageId":"1491107726-21504-1-git-send-email-bnmvco@gmail.com","threadId":"45587","inReplyTo":null,"subject":"[PATCH v6 0/5] [GSoC] remove_subtree(): reimplement using iterators","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-02T04:35:21Z","receivedAt":"2017-04-02T04:35:50Z","isPatch":true,"sender":{"key":"bnmvco@gmail.com","avatar":"https://avatars.githubusercontent.com/u/735397?v=4"},"body":"This is the sixth version of a patch series that implements the GSoC\nmicroproject of converting a recursive call to readdir() to use dir_iterator.\n\nv1: https://public-inbox.org/git/CAGZ79kZwT-9mHTiOJ5CEjk2wDFkn6+NcogjX0=vjhsAh16ANYg@mail.gmail.com/T/#t\nv2: https://public-inbox.org/git/CACsJy8Dxh-QPBBLfaFWPAWUsbA9GVXA7x+mXLjEvYKhk1zOpig@mail.gmail.com/T/#t\nv3: https://public-inbox.org/git/CAGZ79kYtpmURSQWPumobA=e3JBFjKhWCdv_LPhKCd71ZRwMovA@mail.gmail.com/T/#t\nv4: https://public-inbox.org/git/1490747533-89143-1-git-send-email-bnmvco@gmail.com/T/#e437a63e0c22c00c69b5d92977c9b438ed2b9fd3a\nv5: https://public-inbox.org/git/1490844730-47634-1-git-send-email-bnmvco@gmail.com/T/#m2323f15e45de699f2e09364f40a62e17047cf453\n\nBack in v5, Michael had a number of suggestions, all of which were applied\nto this version (including a slightly modified version of his \"biggish rewrite\"\nproject to make dir_iterator's state machine simpler). The only suggestion that\ndid not make it into this series was that of not traversing into subdirectories,\nsince I believe it would be better off in another series that actually required\nthat feature (that is, I do not want a series to implement a feature it will\nnot need). The same goes for Junio's thought on a flag to list *only* directories\nand no files on the v4 discussion.\n\nJunio and Peff's comments about how to write to files in the tests were also\nconsidered, and the tests were adjusted.\n\nI chose to squash both the state machine refactor and the addition of the\nnew flags in a single commit. I do not know whether you will feel this is\nthe right choice but it seemed natural, since most of the state machine's\nnew logic would not even make sense without encompassing the new features.\nI am, of course, open for feedback on this decision.\n\nTo Michael and Duy, thanks -- really -- for the encouraging comments! :)\nI never regarded this microproject purely as a means to fulfill a GSoC\nrequirement, but as a way to get to learn more about Git, so I'm surely\nnot giving it up.\n\nOnce again, thanks for all the previous reviews,\nDaniel.\n\nDaniel Ferreira (5):\n  dir_iterator: add tests for dir_iterator API\n  remove_subtree(): test removing nested directories\n  dir_iterator: add helpers to dir_iterator_advance\n  dir_iterator: refactor state machine model\n  remove_subtree(): reimplement using iterators\n\n Makefile                        |   1 +\n dir-iterator.c                  | 190 ++++++++++++++++++++++++++--------------\n dir-iterator.h                  |  28 ++++--\n entry.c                         |  38 +++-----\n refs/files-backend.c            |   2 +-\n t/helper/.gitignore             |   1 +\n t/helper/test-dir-iterator.c    |  32 +++++++\n t/t0065-dir-iterator.sh         | 109 +++++++++++++++++++++++\n t/t2000-checkout-cache-clash.sh |  11 +++\n 9 files changed, 312 insertions(+), 100 deletions(-)\n create mode 100644 t/helper/test-dir-iterator.c\n create mode 100755 t/t0065-dir-iterator.sh\n\n--\n2.7.4 (Apple Git-66)\n\n"},{"id":"316040","messageId":"1491107726-21504-2-git-send-email-bnmvco@gmail.com","threadId":"45587","inReplyTo":"1491107726-21504-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v6 1/5] dir_iterator: add tests for dir_iterator API","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-02T04:35:22Z","receivedAt":"2017-04-02T04:36:00Z","isPatch":true,"sender":{"key":"bnmvco@gmail.com","avatar":"https://avatars.githubusercontent.com/u/735397?v=4"},"body":"Create t/helper/test-dir-iterator.c, which prints relevant information\nabout a directory tree iterated over with dir_iterator.\n\nCreate t/t0065-dir-iterator.sh, which tests that dir_iterator does\niterate through a whole directory tree.\n\nSigned-off-by: Daniel Ferreira <bnmvco@gmail.com>\n---\n Makefile                     |  1 +\n t/helper/.gitignore          |  1 +\n t/helper/test-dir-iterator.c | 28 +++++++++++++++++++++++\n t/t0065-dir-iterator.sh      | 54 ++++++++++++++++++++++++++++++++++++++++++++\n 4 files changed, 84 insertions(+)\n create mode 100644 t/helper/test-dir-iterator.c\n create mode 100755 t/t0065-dir-iterator.sh\n\ndiff --git a/Makefile b/Makefile\nindex a5a11e7..d0245f3 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -607,6 +607,7 @@ TEST_PROGRAMS_NEED_X += test-ctype\n TEST_PROGRAMS_NEED_X += test-config\n TEST_PROGRAMS_NEED_X += test-date\n TEST_PROGRAMS_NEED_X += test-delta\n+TEST_PROGRAMS_NEED_X += test-dir-iterator\n TEST_PROGRAMS_NEED_X += test-dump-cache-tree\n TEST_PROGRAMS_NEED_X += test-dump-split-index\n TEST_PROGRAMS_NEED_X += test-dump-untracked-cache\ndiff --git a/t/helper/.gitignore b/t/helper/.gitignore\nindex d6e8b36..9c9656d 100644\n--- a/t/helper/.gitignore\n+++ b/t/helper/.gitignore\n@@ -3,6 +3,7 @@\n /test-config\n /test-date\n /test-delta\n+/test-dir-iterator\n /test-dump-cache-tree\n /test-dump-split-index\n /test-dump-untracked-cache\ndiff --git a/t/helper/test-dir-iterator.c b/t/helper/test-dir-iterator.c\nnew file mode 100644\nindex 0000000..06f03fc\n--- /dev/null\n+++ b/t/helper/test-dir-iterator.c\n@@ -0,0 +1,28 @@\n+#include \"git-compat-util.h\"\n+#include \"strbuf.h\"\n+#include \"iterator.h\"\n+#include \"dir-iterator.h\"\n+\n+int cmd_main(int argc, const char **argv) {\n+\tstruct strbuf path = STRBUF_INIT;\n+\tstruct dir_iterator *diter;\n+\n+\tif (argc < 2) {\n+\t\treturn 1;\n+\t}\n+\n+\tstrbuf_add(&path, argv[1], strlen(argv[1]));\n+\n+\tditer = dir_iterator_begin(path.buf);\n+\n+\twhile (dir_iterator_advance(diter) == ITER_OK) {\n+\t\tif (S_ISDIR(diter->st.st_mode))\n+\t\t\tprintf(\"[d] \");\n+\t\telse\n+\t\t\tprintf(\"[f] \");\n+\n+\t\tprintf(\"(%s) %s\\n\", diter->relative_path, diter->path.buf);\n+\t}\n+\n+\treturn 0;\n+}\ndiff --git a/t/t0065-dir-iterator.sh b/t/t0065-dir-iterator.sh\nnew file mode 100755\nindex 0000000..b857c07\n--- /dev/null\n+++ b/t/t0065-dir-iterator.sh\n@@ -0,0 +1,54 @@\n+#!/bin/sh\n+\n+test_description='Test directory iteration.'\n+\n+. ./test-lib.sh\n+\n+cat >expect-sorted-output <<-\\EOF &&\n+[d] (a) ./dir/a\n+[d] (a/b) ./dir/a/b\n+[d] (a/b/c) ./dir/a/b/c\n+[d] (d) ./dir/d\n+[d] (d/e) ./dir/d/e\n+[d] (d/e/d) ./dir/d/e/d\n+[f] (a/b/c/d) ./dir/a/b/c/d\n+[f] (a/e) ./dir/a/e\n+[f] (b) ./dir/b\n+[f] (c) ./dir/c\n+[f] (d/e/d/a) ./dir/d/e/d/a\n+EOF\n+\n+test_expect_success 'dir-iterator should iterate through all files' '\n+\tmkdir -p dir &&\n+\tmkdir -p dir/a/b/c/ &&\n+\t>dir/b &&\n+\t>dir/c &&\n+\tmkdir -p dir/d/e/d/ &&\n+\t>dir/a/b/c/d &&\n+\t>dir/a/e &&\n+\t>dir/d/e/d/a &&\n+\n+\ttest-dir-iterator ./dir | sort >./actual-pre-order-sorted-output &&\n+\trm -rf dir &&\n+\n+\ttest_cmp expect-sorted-output actual-pre-order-sorted-output\n+'\n+\n+cat >expect-pre-order-output <<-\\EOF &&\n+[d] (a) ./dir/a\n+[d] (a/b) ./dir/a/b\n+[d] (a/b/c) ./dir/a/b/c\n+[f] (a/b/c/d) ./dir/a/b/c/d\n+EOF\n+\n+test_expect_success 'dir-iterator should list files in the correct order' '\n+\tmkdir -p dir/a/b/c/ &&\n+\t>dir/a/b/c/d &&\n+\n+\ttest-dir-iterator ./dir >actual-pre-order-output &&\n+\trm -rf dir &&\n+\n+\ttest_cmp expect-pre-order-output actual-pre-order-output\n+'\n+\n+test_done\n--\n2.7.4 (Apple Git-66)\n\n"},{"id":"316041","messageId":"1491107726-21504-3-git-send-email-bnmvco@gmail.com","threadId":"45587","inReplyTo":"1491107726-21504-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v6 2/5] remove_subtree(): test removing nested directories","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-02T04:35:23Z","receivedAt":"2017-04-02T04:36:03Z","isPatch":true,"sender":{"key":"bnmvco@gmail.com","avatar":"https://avatars.githubusercontent.com/u/735397?v=4"},"body":"Test removing a nested directory when an attempt is made to restore the\nindex to a state where it does not exist. A similar test could be found\npreviously in t/t2000-checkout-cache-clash.sh, but it did not check for\nnested directories, which could allow a faulty implementation of\nremove_subtree() pass the tests.\n\nSigned-off-by: Daniel Ferreira <bnmvco@gmail.com>\n---\n t/t2000-checkout-cache-clash.sh | 11 +++++++++++\n 1 file changed, 11 insertions(+)\n\ndiff --git a/t/t2000-checkout-cache-clash.sh b/t/t2000-checkout-cache-clash.sh\nindex de3edb5..ac10ba3 100755\n--- a/t/t2000-checkout-cache-clash.sh\n+++ b/t/t2000-checkout-cache-clash.sh\n@@ -57,4 +57,15 @@ test_expect_success SYMLINKS 'checkout-index -f twice with --prefix' '\n \tgit checkout-index -a -f --prefix=there/\n '\n\n+test_expect_success 'git checkout-index -f should remove nested subtrees' '\n+\techo content >path &&\n+\tgit update-index --add path &&\n+\trm path &&\n+\tmkdir -p path/with/nested/paths &&\n+\techo content >path/file1 &&\n+\techo content >path/with/nested/paths/file2 &&\n+\tgit checkout-index -f -a &&\n+\ttest ! -d path\n+'\n+\n test_done\n--\n2.7.4 (Apple Git-66)\n\n"},{"id":"316042","messageId":"1491107726-21504-4-git-send-email-bnmvco@gmail.com","threadId":"45587","inReplyTo":"1491107726-21504-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v6 3/5] dir_iterator: add helpers to dir_iterator_advance","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-02T04:35:24Z","receivedAt":"2017-04-02T04:36:05Z","isPatch":true,"sender":{"key":"bnmvco@gmail.com","avatar":"https://avatars.githubusercontent.com/u/735397?v=4"},"body":"Create inline helpers to dir_iterator_advance(). Make\ndir_iterator_advance()'s code more legible and allow some behavior to\nbe reusable.\n\nSigned-off-by: Daniel Ferreira <bnmvco@gmail.com>\n---\n dir-iterator.c | 65 +++++++++++++++++++++++++++++++++++++---------------------\n 1 file changed, 42 insertions(+), 23 deletions(-)\n\ndiff --git a/dir-iterator.c b/dir-iterator.c\nindex 34182a9..ce8bf81 100644\n--- a/dir-iterator.c\n+++ b/dir-iterator.c\n@@ -50,6 +50,43 @@ struct dir_iterator_int {\n \tstruct dir_iterator_level *levels;\n };\n\n+static inline void push_dir_level(struct dir_iterator_int *iter, struct dir_iterator_level *level)\n+{\n+\tlevel->dir_state = DIR_STATE_RECURSE;\n+\tALLOC_GROW(iter->levels, iter->levels_nr + 1,\n+\t\t   iter->levels_alloc);\n+\tlevel = &iter->levels[iter->levels_nr++];\n+\tlevel->initialized = 0;\n+}\n+\n+static inline int pop_dir_level(struct dir_iterator_int *iter)\n+{\n+\treturn --iter->levels_nr;\n+}\n+\n+static inline int set_iterator_data(struct dir_iterator_int *iter, struct dir_iterator_level *level)\n+{\n+\tif (lstat(iter->base.path.buf, &iter->base.st) < 0) {\n+\t\tif (errno != ENOENT)\n+\t\t\twarning(\"error reading path '%s': %s\",\n+\t\t\t\titer->base.path.buf,\n+\t\t\t\tstrerror(errno));\n+\t\treturn -1;\n+\t}\n+\n+\t/*\n+\t * We have to set these each time because\n+\t * the path strbuf might have been realloc()ed.\n+\t */\n+\titer->base.relative_path =\n+\t\titer->base.path.buf + iter->levels[0].prefix_len;\n+\titer->base.basename =\n+\t\titer->base.path.buf + level->prefix_len;\n+\tlevel->dir_state = DIR_STATE_ITER;\n+\n+\treturn 0;\n+}\n+\n int dir_iterator_advance(struct dir_iterator *dir_iterator)\n {\n \tstruct dir_iterator_int *iter =\n@@ -84,11 +121,7 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)\n \t\t\t\t * over; now prepare to iterate into\n \t\t\t\t * it.\n \t\t\t\t */\n-\t\t\t\tlevel->dir_state = DIR_STATE_RECURSE;\n-\t\t\t\tALLOC_GROW(iter->levels, iter->levels_nr + 1,\n-\t\t\t\t\t   iter->levels_alloc);\n-\t\t\t\tlevel = &iter->levels[iter->levels_nr++];\n-\t\t\t\tlevel->initialized = 0;\n+\t\t\t\tpush_dir_level(iter, level);\n \t\t\t\tcontinue;\n \t\t\t} else {\n \t\t\t\t/*\n@@ -104,7 +137,7 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)\n \t\t\t * This level is exhausted (or wasn't opened\n \t\t\t * successfully); pop up a level.\n \t\t\t */\n-\t\t\tif (--iter->levels_nr == 0)\n+\t\t\tif (pop_dir_level(iter) == 0)\n \t\t\t\treturn dir_iterator_abort(dir_iterator);\n\n \t\t\tcontinue;\n@@ -129,7 +162,7 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)\n \t\t\t\t\t\titer->base.path.buf, strerror(errno));\n\n \t\t\t\tlevel->dir = NULL;\n-\t\t\t\tif (--iter->levels_nr == 0)\n+\t\t\t\tif (pop_dir_level(iter) == 0)\n \t\t\t\t\treturn dir_iterator_abort(dir_iterator);\n \t\t\t\tbreak;\n \t\t\t}\n@@ -138,23 +171,9 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)\n \t\t\t\tcontinue;\n\n \t\t\tstrbuf_addstr(&iter->base.path, de->d_name);\n-\t\t\tif (lstat(iter->base.path.buf, &iter->base.st) < 0) {\n-\t\t\t\tif (errno != ENOENT)\n-\t\t\t\t\twarning(\"error reading path '%s': %s\",\n-\t\t\t\t\t\titer->base.path.buf,\n-\t\t\t\t\t\tstrerror(errno));\n-\t\t\t\tcontinue;\n-\t\t\t}\n\n-\t\t\t/*\n-\t\t\t * We have to set these each time because\n-\t\t\t * the path strbuf might have been realloc()ed.\n-\t\t\t */\n-\t\t\titer->base.relative_path =\n-\t\t\t\titer->base.path.buf + iter->levels[0].prefix_len;\n-\t\t\titer->base.basename =\n-\t\t\t\titer->base.path.buf + level->prefix_len;\n-\t\t\tlevel->dir_state = DIR_STATE_ITER;\n+\t\t\tif (set_iterator_data(iter, level))\n+\t\t\t\tcontinue;\n\n \t\t\treturn ITER_OK;\n \t\t}\n--\n2.7.4 (Apple Git-66)\n\n"},{"id":"316043","messageId":"1491107726-21504-5-git-send-email-bnmvco@gmail.com","threadId":"45587","inReplyTo":"1491107726-21504-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v6 4/5] dir_iterator: refactor state machine model","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-02T04:35:25Z","receivedAt":"2017-04-02T04:36:10Z","isPatch":true,"sender":{"key":"bnmvco@gmail.com","avatar":"https://avatars.githubusercontent.com/u/735397?v=4"},"body":"Perform major refactor of dir_iterator_advance(). dir_iterator has\nceased to rely on a convoluted state machine mechanism of two loops and\ntwo state variables (level.initialized and level.dir_state). This serves\nto ease comprehension of the iterator mechanism and ease addition of new\nfeatures to the iterator.\n\nCreate an option for the dir_iterator API to iterate over subdirectories\nonly after having iterated through their contents. This feature was\npredicted, although not implemented by 0fe5043 (\"dir_iterator: new API\nfor iterating over a directory tree\", 2016-06-18). This is useful for\nrecursively removing a directory and calling rmdir() on a directory only\nafter all of its contents have been wiped.\n\nAdd an option for the dir_iterator API to iterate over the root\ndirectory (the one it was initialized with) as well.\n\nAdd the \"flags\" parameter to dir_iterator_create, allowing for the\naforementioned new features to be enabled. The new default behavior\n(i.e. flags set to 0) does not iterate over directories. Flag\nDIR_ITERATOR_PRE_ORDER_TRAVERSAL iterates over a directory before doing\nso over its contents. DIR_ITERATOR_POST_ORDER_TRAVERSAL iterates over a\ndirectory after doing so over its contents. DIR_ITERATOR_LIST_ROOT_DIR\niterates over the root directory. These flags do not conflict with each\nother and may be used simultaneously.\n\nAmend a call to dir_iterator_begin() in refs/files-backend.c to pass\nthe flags parameter introduced.\n\nImprove t/t0065-dir-iterator.sh and t/helper/test-dir-iterator.c to\ntest \"post-order\" and \"iterate-over-root\" modes.\n\nSigned-off-by: Daniel Ferreira <bnmvco@gmail.com>\n---\n dir-iterator.c               | 149 +++++++++++++++++++++++++++----------------\n dir-iterator.h               |  28 ++++++--\n refs/files-backend.c         |   2 +-\n t/helper/test-dir-iterator.c |   6 +-\n t/t0065-dir-iterator.sh      |  61 +++++++++++++++++-\n 5 files changed, 179 insertions(+), 67 deletions(-)\n\ndiff --git a/dir-iterator.c b/dir-iterator.c\nindex ce8bf81..4b23889 100644\n--- a/dir-iterator.c\n+++ b/dir-iterator.c\n@@ -4,8 +4,6 @@\n #include \"dir-iterator.h\"\n \n struct dir_iterator_level {\n-\tint initialized;\n-\n \tDIR *dir;\n \n \t/*\n@@ -20,8 +18,11 @@ struct dir_iterator_level {\n \t * iteration and also iterated into):\n \t */\n \tenum {\n-\t\tDIR_STATE_ITER,\n-\t\tDIR_STATE_RECURSE\n+\t\tDIR_STATE_PUSHED,\n+\t\tDIR_STATE_PRE_ITERATION,\n+\t\tDIR_STATE_ITERATING,\n+\t\tDIR_STATE_POST_ITERATION,\n+\t\tDIR_STATE_EXHAUSTED\n \t} dir_state;\n };\n \n@@ -48,15 +49,20 @@ struct dir_iterator_int {\n \t * that will be included in this iteration.\n \t */\n \tstruct dir_iterator_level *levels;\n+\n+\t/* Holds the flags passed to dir_iterator_begin(). */\n+\tunsigned flags;\n };\n \n static inline void push_dir_level(struct dir_iterator_int *iter, struct dir_iterator_level *level)\n {\n-\tlevel->dir_state = DIR_STATE_RECURSE;\n \tALLOC_GROW(iter->levels, iter->levels_nr + 1,\n \t\t   iter->levels_alloc);\n+\n+\t/* Push a new level */\n \tlevel = &iter->levels[iter->levels_nr++];\n-\tlevel->initialized = 0;\n+\tlevel->dir = NULL;\n+\tlevel->dir_state = DIR_STATE_PUSHED;\n }\n \n static inline int pop_dir_level(struct dir_iterator_int *iter)\n@@ -75,18 +81,35 @@ static inline int set_iterator_data(struct dir_iterator_int *iter, struct dir_it\n \t}\n \n \t/*\n-\t * We have to set these each time because\n-\t * the path strbuf might have been realloc()ed.\n+\t * Check if we are dealing with the root directory as an\n+\t * item that's being iterated through.\n \t */\n-\titer->base.relative_path =\n-\t\titer->base.path.buf + iter->levels[0].prefix_len;\n+\tif (level->dir_state != DIR_STATE_ITERATING &&\n+\t\titer->levels_nr == 1) {\n+\t\titer->base.relative_path = \".\";\n+\t}\n+\telse {\n+\t\titer->base.relative_path =\n+\t\t\titer->base.path.buf + iter->levels[0].prefix_len;\n+\t}\n \titer->base.basename =\n \t\titer->base.path.buf + level->prefix_len;\n-\tlevel->dir_state = DIR_STATE_ITER;\n \n \treturn 0;\n }\n \n+/*\n+ * This function uses a state machine with the following states:\n+ * -> DIR_STATE_PUSHED: the directory has been pushed to the\n+ * iterator traversal tree.\n+ * -> DIR_STATE_PRE_ITERATION: the directory is *NOT* initialized. The\n+ * dirpath has already been returned if pre-order traversal is set.\n+ * -> DIR_STATE_ITERATING: the directory is initialized. We are traversing\n+ * through it.\n+ * -> DIR_STATE_POST_ITERATION: the directory has been iterated through.\n+ * We are ready to close it.\n+ * -> DIR_STATE_EXHAUSTED: the directory is closed and ready to be popped.\n+ */\n int dir_iterator_advance(struct dir_iterator *dir_iterator)\n {\n \tstruct dir_iterator_int *iter =\n@@ -97,7 +120,18 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)\n \t\t\t&iter->levels[iter->levels_nr - 1];\n \t\tstruct dirent *de;\n \n-\t\tif (!level->initialized) {\n+\t\tif (level->dir_state == DIR_STATE_PUSHED) {\n+\t\t\tlevel->dir_state = DIR_STATE_PRE_ITERATION;\n+\n+\t\t\tif (iter->flags & DIR_ITERATOR_PRE_ORDER_TRAVERSAL) {\n+\t\t\t\t/* We may not want the root directory to be iterated over */\n+\t\t\t\tif (iter->levels_nr != 1 ||\n+\t\t\t\t\t(iter->flags & DIR_ITERATOR_LIST_ROOT_DIR)) {\n+\t\t\t\t\tset_iterator_data(iter, level);\n+\t\t\t\t\treturn ITER_OK;\n+\t\t\t\t}\n+\t\t\t}\n+\t\t} else if (level->dir_state == DIR_STATE_PRE_ITERATION) {\n \t\t\t/*\n \t\t\t * Note: dir_iterator_begin() ensures that\n \t\t\t * path is not the empty string.\n@@ -108,63 +142,32 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)\n \n \t\t\tlevel->dir = opendir(iter->base.path.buf);\n \t\t\tif (!level->dir && errno != ENOENT) {\n+\t\t\t\t/*\n+\t\t\t\t * This level wasn't opened sucessfully; pretend we\n+\t\t\t\t * iterated through it already.\n+\t\t\t\t */\n \t\t\t\twarning(\"error opening directory %s: %s\",\n \t\t\t\t\titer->base.path.buf, strerror(errno));\n-\t\t\t\t/* Popping the level is handled below */\n-\t\t\t}\n \n-\t\t\tlevel->initialized = 1;\n-\t\t} else if (S_ISDIR(iter->base.st.st_mode)) {\n-\t\t\tif (level->dir_state == DIR_STATE_ITER) {\n-\t\t\t\t/*\n-\t\t\t\t * The directory was just iterated\n-\t\t\t\t * over; now prepare to iterate into\n-\t\t\t\t * it.\n-\t\t\t\t */\n-\t\t\t\tpush_dir_level(iter, level);\n+\t\t\t\tlevel->dir_state = DIR_STATE_POST_ITERATION;\n \t\t\t\tcontinue;\n-\t\t\t} else {\n-\t\t\t\t/*\n-\t\t\t\t * The directory has already been\n-\t\t\t\t * iterated over and iterated into;\n-\t\t\t\t * we're done with it.\n-\t\t\t\t */\n \t\t\t}\n-\t\t}\n \n-\t\tif (!level->dir) {\n-\t\t\t/*\n-\t\t\t * This level is exhausted (or wasn't opened\n-\t\t\t * successfully); pop up a level.\n-\t\t\t */\n-\t\t\tif (pop_dir_level(iter) == 0)\n-\t\t\t\treturn dir_iterator_abort(dir_iterator);\n-\n-\t\t\tcontinue;\n-\t\t}\n-\n-\t\t/*\n-\t\t * Loop until we find an entry that we can give back\n-\t\t * to the caller:\n-\t\t */\n-\t\twhile (1) {\n+\t\t\tlevel->dir_state = DIR_STATE_ITERATING;\n+\t\t} else if (level->dir_state == DIR_STATE_ITERATING) {\n \t\t\tstrbuf_setlen(&iter->base.path, level->prefix_len);\n \t\t\terrno = 0;\n \t\t\tde = readdir(level->dir);\n \n \t\t\tif (!de) {\n-\t\t\t\t/* This level is exhausted; pop up a level. */\n+\t\t\t\t/* In case of readdir() error */\n \t\t\t\tif (errno) {\n \t\t\t\t\twarning(\"error reading directory %s: %s\",\n \t\t\t\t\t\titer->base.path.buf, strerror(errno));\n-\t\t\t\t} else if (closedir(level->dir))\n-\t\t\t\t\twarning(\"error closing directory %s: %s\",\n-\t\t\t\t\t\titer->base.path.buf, strerror(errno));\n+\t\t\t\t}\n \n-\t\t\t\tlevel->dir = NULL;\n-\t\t\t\tif (pop_dir_level(iter) == 0)\n-\t\t\t\t\treturn dir_iterator_abort(dir_iterator);\n-\t\t\t\tbreak;\n+\t\t\t\tlevel->dir_state = DIR_STATE_POST_ITERATION;\n+\t\t\t\tcontinue;\n \t\t\t}\n \n \t\t\tif (is_dot_or_dotdot(de->d_name))\n@@ -175,7 +178,38 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)\n \t\t\tif (set_iterator_data(iter, level))\n \t\t\t\tcontinue;\n \n+\t\t\tif (S_ISDIR(iter->base.st.st_mode)) {\n+\t\t\t\tpush_dir_level(iter, level);\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\n \t\t\treturn ITER_OK;\n+\t\t} else if (level->dir_state == DIR_STATE_POST_ITERATION) {\n+\t\t\tif (level->dir != NULL && closedir(level->dir)) {\n+\t\t\t\twarning(\"error closing directory %s: %s\",\n+\t\t\t\t\titer->base.path.buf, strerror(errno));\n+\t\t\t}\n+\t\t\tlevel->dir_state = DIR_STATE_EXHAUSTED;\n+\n+\t\t\tstrbuf_setlen(&iter->base.path, level->prefix_len);\n+\t\t\t/*\n+\t\t\t * Since we are iterating through the dirpath\n+\t\t\t * after we have gone through it, we still need\n+\t\t\t * to get rid of the trailing slash we appended.\n+\t\t\t */\n+\t\t\tstrbuf_strip_suffix(&iter->base.path, \"/\");\n+\n+\t\t\tif (iter->flags & DIR_ITERATOR_POST_ORDER_TRAVERSAL) {\n+\t\t\t\t/* We may not want the root directory to be iterated over */\n+\t\t\t\tif (iter->levels_nr != 1 ||\n+\t\t\t\t\t(iter->flags & DIR_ITERATOR_LIST_ROOT_DIR)) {\n+\t\t\t\t\tset_iterator_data(iter, level);\n+\t\t\t\t\treturn ITER_OK;\n+\t\t\t\t}\n+\t\t\t}\n+\t\t} else if (level->dir_state == DIR_STATE_EXHAUSTED) {\n+\t\t\tif (pop_dir_level(iter) == 0)\n+\t\t\t\treturn dir_iterator_abort(dir_iterator);\n \t\t}\n \t}\n }\n@@ -201,7 +235,7 @@ int dir_iterator_abort(struct dir_iterator *dir_iterator)\n \treturn ITER_DONE;\n }\n \n-struct dir_iterator *dir_iterator_begin(const char *path)\n+struct dir_iterator *dir_iterator_begin(const char *path, unsigned flags)\n {\n \tstruct dir_iterator_int *iter = xcalloc(1, sizeof(*iter));\n \tstruct dir_iterator *dir_iterator = &iter->base;\n@@ -209,13 +243,16 @@ struct dir_iterator *dir_iterator_begin(const char *path)\n \tif (!path || !*path)\n \t\tdie(\"BUG: empty path passed to dir_iterator_begin()\");\n \n+\titer->flags = flags;\n+\n \tstrbuf_init(&iter->base.path, PATH_MAX);\n \tstrbuf_addstr(&iter->base.path, path);\n \n \tALLOC_GROW(iter->levels, 10, iter->levels_alloc);\n \n \titer->levels_nr = 1;\n-\titer->levels[0].initialized = 0;\n+\titer->levels[0].dir = NULL;\n+\titer->levels[0].dir_state = DIR_STATE_PUSHED;\n \n \treturn dir_iterator;\n }\ndiff --git a/dir-iterator.h b/dir-iterator.h\nindex 27739e6..0e82f36 100644\n--- a/dir-iterator.h\n+++ b/dir-iterator.h\n@@ -11,13 +11,12 @@\n  * Every time dir_iterator_advance() is called, update the members of\n  * the dir_iterator structure to reflect the next path in the\n  * iteration. The order that paths are iterated over within a\n- * directory is undefined, but directory paths are always iterated\n- * over before the subdirectory contents.\n+ * directory is undefined.\n  *\n  * A typical iteration looks like this:\n  *\n  *     int ok;\n- *     struct iterator *iter = dir_iterator_begin(path);\n+ *     struct iterator *iter = dir_iterator_begin(path, flags);\n  *\n  *     while ((ok = dir_iterator_advance(iter)) == ITER_OK) {\n  *             if (want_to_stop_iteration()) {\n@@ -38,6 +37,22 @@\n  * dir_iterator_advance() again.\n  */\n \n+/*\n+ * Possible flags for dir_iterator_begin().\n+ *\n+ * -> DIR_ITERATOR_PRE_ORDER_TRAVERSAL: the iterator shall return\n+ * a dirpath it has found before iterating through that directory's\n+ * contents.\n+ * -> DIR_ITERATOR_POST_ORDER_TRAVERSAL: the iterator shall return\n+ * a dirpath it has found after iterating through that directory's\n+ * contents.\n+ * -> DIR_ITERATOR_LIST_ROOT_DIR: the iterator shall return the dirpath\n+ * of the root directory it is iterating through.\n+ */\n+#define DIR_ITERATOR_PRE_ORDER_TRAVERSAL (1 << 0)\n+#define DIR_ITERATOR_POST_ORDER_TRAVERSAL (1 << 1)\n+#define DIR_ITERATOR_LIST_ROOT_DIR (1 << 2)\n+\n struct dir_iterator {\n \t/* The current path: */\n \tstruct strbuf path;\n@@ -57,15 +72,16 @@ struct dir_iterator {\n };\n \n /*\n- * Start a directory iteration over path. Return a dir_iterator that\n- * holds the internal state of the iteration.\n+ * Start a directory iteration over path, with options specified in\n+ * 'flags'. Return a dir_iterator that holds the internal state of\n+ * the iteration.\n  *\n  * The iteration includes all paths under path, not including path\n  * itself and not including \".\" or \"..\" entries.\n  *\n  * path is the starting directory. An internal copy will be made.\n  */\n-struct dir_iterator *dir_iterator_begin(const char *path);\n+struct dir_iterator *dir_iterator_begin(const char *path, unsigned flags);\n \n /*\n  * Advance the iterator to the first or next item and return ITER_OK.\ndiff --git a/refs/files-backend.c b/refs/files-backend.c\nindex 50188e9..b4bba74 100644\n--- a/refs/files-backend.c\n+++ b/refs/files-backend.c\n@@ -3346,7 +3346,7 @@ static struct ref_iterator *files_reflog_iterator_begin(struct ref_store *ref_st\n \tfiles_downcast(ref_store, 0, \"reflog_iterator_begin\");\n \n \tbase_ref_iterator_init(ref_iterator, &files_reflog_iterator_vtable);\n-\titer->dir_iterator = dir_iterator_begin(git_path(\"logs\"));\n+\titer->dir_iterator = dir_iterator_begin(git_path(\"logs\"), 0);\n \treturn ref_iterator;\n }\n \ndiff --git a/t/helper/test-dir-iterator.c b/t/helper/test-dir-iterator.c\nindex 06f03fc..a1b8c78 100644\n--- a/t/helper/test-dir-iterator.c\n+++ b/t/helper/test-dir-iterator.c\n@@ -6,6 +6,7 @@\n int cmd_main(int argc, const char **argv) {\n \tstruct strbuf path = STRBUF_INIT;\n \tstruct dir_iterator *diter;\n+\tunsigned flag = DIR_ITERATOR_PRE_ORDER_TRAVERSAL;\n \n \tif (argc < 2) {\n \t\treturn 1;\n@@ -13,7 +14,10 @@ int cmd_main(int argc, const char **argv) {\n \n \tstrbuf_add(&path, argv[1], strlen(argv[1]));\n \n-\tditer = dir_iterator_begin(path.buf);\n+\tif (argc == 3)\n+\t\tflag = atoi(argv[2]);\n+\n+\tditer = dir_iterator_begin(path.buf, flag);\n \n \twhile (dir_iterator_advance(diter) == ITER_OK) {\n \t\tif (S_ISDIR(diter->st.st_mode))\ndiff --git a/t/t0065-dir-iterator.sh b/t/t0065-dir-iterator.sh\nindex b857c07..ade3ee0 100755\n--- a/t/t0065-dir-iterator.sh\n+++ b/t/t0065-dir-iterator.sh\n@@ -28,12 +28,28 @@ test_expect_success 'dir-iterator should iterate through all files' '\n \t>dir/a/e &&\n \t>dir/d/e/d/a &&\n \n-\ttest-dir-iterator ./dir | sort >./actual-pre-order-sorted-output &&\n+\ttest-dir-iterator ./dir 1 | sort >./actual-pre-order-sorted-output &&\n \trm -rf dir &&\n \n \ttest_cmp expect-sorted-output actual-pre-order-sorted-output\n '\n \n+test_expect_success 'dir-iterator should iterate through all files on post-order mode' '\n+\tmkdir -p dir &&\n+\tmkdir -p dir/a/b/c/ &&\n+\t>dir/b &&\n+\t>dir/c &&\n+\tmkdir -p dir/d/e/d/ &&\n+\t>dir/a/b/c/d &&\n+\t>dir/a/e &&\n+\t>dir/d/e/d/a &&\n+\n+\ttest-dir-iterator ./dir 2 | sort >actual-post-order-sorted-output &&\n+\trm -rf dir &&\n+\n+\ttest_cmp expect-sorted-output actual-post-order-sorted-output\n+'\n+\n cat >expect-pre-order-output <<-\\EOF &&\n [d] (a) ./dir/a\n [d] (a/b) ./dir/a/b\n@@ -41,14 +57,53 @@ cat >expect-pre-order-output <<-\\EOF &&\n [f] (a/b/c/d) ./dir/a/b/c/d\n EOF\n \n-test_expect_success 'dir-iterator should list files in the correct order' '\n+test_expect_success 'dir-iterator should list files properly on pre-order mode' '\n \tmkdir -p dir/a/b/c/ &&\n \t>dir/a/b/c/d &&\n \n-\ttest-dir-iterator ./dir >actual-pre-order-output &&\n+\ttest-dir-iterator ./dir 1 >actual-pre-order-output &&\n \trm -rf dir &&\n \n \ttest_cmp expect-pre-order-output actual-pre-order-output\n '\n \n+cat >expect-post-order-output <<-\\EOF &&\n+[f] (a/b/c/d) ./dir/a/b/c/d\n+[d] (a/b/c) ./dir/a/b/c\n+[d] (a/b) ./dir/a/b\n+[d] (a) ./dir/a\n+EOF\n+\n+test_expect_success 'dir-iterator should list files properly on post-order mode' '\n+\tmkdir -p dir/a/b/c/ &&\n+\t>dir/a/b/c/d &&\n+\n+\ttest-dir-iterator ./dir 2 >actual-post-order-output &&\n+\trm -rf dir &&\n+\n+\ttest_cmp expect-post-order-output actual-post-order-output\n+'\n+\n+cat >expect-pre-order-post-order-root-dir-output <<-\\EOF &&\n+[d] (.) ./dir\n+[d] (a) ./dir/a\n+[d] (a/b) ./dir/a/b\n+[d] (a/b/c) ./dir/a/b/c\n+[f] (a/b/c/d) ./dir/a/b/c/d\n+[d] (a/b/c) ./dir/a/b/c\n+[d] (a/b) ./dir/a/b\n+[d] (a) ./dir/a\n+[d] (.) ./dir\n+EOF\n+\n+test_expect_success 'dir-iterator should list files properly on pre-order + post-order + root-dir mode' '\n+\tmkdir -p dir/a/b/c/ &&\n+\t>dir/a/b/c/d &&\n+\n+\ttest-dir-iterator ./dir 7 >actual-pre-order-post-order-root-dir-output &&\n+\trm -rf dir &&\n+\n+\ttest_cmp expect-pre-order-post-order-root-dir-output actual-pre-order-post-order-root-dir-output\n+'\n+\n test_done\n-- \n2.7.4 (Apple Git-66)\n\n"},{"id":"316044","messageId":"1491107726-21504-6-git-send-email-bnmvco@gmail.com","threadId":"45587","inReplyTo":"1491107726-21504-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v6 5/5] remove_subtree(): reimplement using iterators","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-02T04:35:26Z","receivedAt":"2017-04-02T04:36:14Z","isPatch":true,"sender":{"key":"bnmvco@gmail.com","avatar":"https://avatars.githubusercontent.com/u/735397?v=4"},"body":"Use dir_iterator to traverse through remove_subtree()'s directory tree,\navoiding the need for recursive calls to readdir(). Simplify\nremove_subtree()'s code.\n\nA conversion similar in purpose was previously done at 46d092a\n(\"for_each_reflog(): reimplement using iterators\", 2016-05-21).\n\nSigned-off-by: Daniel Ferreira <bnmvco@gmail.com>\n---\n entry.c | 38 ++++++++++++--------------------------\n 1 file changed, 12 insertions(+), 26 deletions(-)\n\ndiff --git a/entry.c b/entry.c\nindex c6eea24..309b9ad 100644\n--- a/entry.c\n+++ b/entry.c\n@@ -2,6 +2,8 @@\n #include \"blob.h\"\n #include \"dir.h\"\n #include \"streaming.h\"\n+#include \"iterator.h\"\n+#include \"dir-iterator.h\"\n\n static void create_directories(const char *path, int path_len,\n \t\t\t       const struct checkout *state)\n@@ -44,33 +46,17 @@ static void create_directories(const char *path, int path_len,\n \tfree(buf);\n }\n\n-static void remove_subtree(struct strbuf *path)\n+static void remove_subtree(const char *path)\n {\n-\tDIR *dir = opendir(path->buf);\n-\tstruct dirent *de;\n-\tint origlen = path->len;\n-\n-\tif (!dir)\n-\t\tdie_errno(\"cannot opendir '%s'\", path->buf);\n-\twhile ((de = readdir(dir)) != NULL) {\n-\t\tstruct stat st;\n-\n-\t\tif (is_dot_or_dotdot(de->d_name))\n-\t\t\tcontinue;\n-\n-\t\tstrbuf_addch(path, '/');\n-\t\tstrbuf_addstr(path, de->d_name);\n-\t\tif (lstat(path->buf, &st))\n-\t\t\tdie_errno(\"cannot lstat '%s'\", path->buf);\n-\t\tif (S_ISDIR(st.st_mode))\n-\t\t\tremove_subtree(path);\n-\t\telse if (unlink(path->buf))\n-\t\t\tdie_errno(\"cannot unlink '%s'\", path->buf);\n-\t\tstrbuf_setlen(path, origlen);\n+\tstruct dir_iterator *diter = dir_iterator_begin(path, DIR_ITERATOR_POST_ORDER_TRAVERSAL | DIR_ITERATOR_LIST_ROOT_DIR);\n+\n+\twhile (dir_iterator_advance(diter) == ITER_OK) {\n+\t\tif (S_ISDIR(diter->st.st_mode)) {\n+\t\t\tif (rmdir(diter->path.buf))\n+\t\t\t\tdie_errno(\"cannot rmdir '%s'\", diter->path.buf);\n+\t\t} else if (unlink(diter->path.buf))\n+\t\t\tdie_errno(\"cannot unlink '%s'\", diter->path.buf);\n \t}\n-\tclosedir(dir);\n-\tif (rmdir(path->buf))\n-\t\tdie_errno(\"cannot rmdir '%s'\", path->buf);\n }\n\n static int create_file(const char *path, unsigned int mode)\n@@ -282,7 +268,7 @@ int checkout_entry(struct cache_entry *ce,\n \t\t\t\treturn 0;\n \t\t\tif (!state->force)\n \t\t\t\treturn error(\"%s is a directory\", path.buf);\n-\t\t\tremove_subtree(&path);\n+\t\t\tremove_subtree(path.buf);\n \t\t} else if (unlink(path.buf))\n \t\t\treturn error_errno(\"unable to unlink old '%s'\", path.buf);\n \t} else if (state->not_new)\n--\n2.7.4 (Apple Git-66)\n\n"},{"id":"316045","messageId":"CAEA2_RJuxw+sZ0CABCfTMnY+Wy5KD2totG76FDWfpH1Uht2taw@mail.gmail.com","threadId":"45587","inReplyTo":"1491107726-21504-5-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v6 4/5] dir_iterator: refactor state machine model","fromName":"Daniel Ferreira (theiostream)","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-02T04:46:16Z","receivedAt":"2017-04-02T04:46:54Z","isPatch":true,"sender":{"key":"bnmvco@gmail.com","avatar":"https://avatars.githubusercontent.com/u/735397?v=4"},"body":"Gah, I just realized I failed to correct refs/files-backend.c's\nbehavior and kept 0 instead of DIR_ITERATOR_PRE_ORDER_TRAVERSAL as its\nflag. I'll correct this on a v7, but I'll wait for the rest of your\nreviews before sending that revision.\n\nOn Sun, Apr 2, 2017 at 1:35 AM, Daniel Ferreira <bnmvco@gmail.com> wrote:\n> Perform major refactor of dir_iterator_advance(). dir_iterator has\n> ceased to rely on a convoluted state machine mechanism of two loops and\n> two state variables (level.initialized and level.dir_state). This serves\n> to ease comprehension of the iterator mechanism and ease addition of new\n> features to the iterator.\n>\n> Create an option for the dir_iterator API to iterate over subdirectories\n> only after having iterated through their contents. This feature was\n> predicted, although not implemented by 0fe5043 (\"dir_iterator: new API\n> for iterating over a directory tree\", 2016-06-18). This is useful for\n> recursively removing a directory and calling rmdir() on a directory only\n> after all of its contents have been wiped.\n>\n> Add an option for the dir_iterator API to iterate over the root\n> directory (the one it was initialized with) as well.\n>\n> Add the \"flags\" parameter to dir_iterator_create, allowing for the\n> aforementioned new features to be enabled. The new default behavior\n> (i.e. flags set to 0) does not iterate over directories. Flag\n> DIR_ITERATOR_PRE_ORDER_TRAVERSAL iterates over a directory before doing\n> so over its contents. DIR_ITERATOR_POST_ORDER_TRAVERSAL iterates over a\n> directory after doing so over its contents. DIR_ITERATOR_LIST_ROOT_DIR\n> iterates over the root directory. These flags do not conflict with each\n> other and may be used simultaneously.\n>\n> Amend a call to dir_iterator_begin() in refs/files-backend.c to pass\n> the flags parameter introduced.\n>\n> Improve t/t0065-dir-iterator.sh and t/helper/test-dir-iterator.c to\n> test \"post-order\" and \"iterate-over-root\" modes.\n>\n> Signed-off-by: Daniel Ferreira <bnmvco@gmail.com>\n> ---\n>  dir-iterator.c               | 149 +++++++++++++++++++++++++++----------------\n>  dir-iterator.h               |  28 ++++++--\n>  refs/files-backend.c         |   2 +-\n>  t/helper/test-dir-iterator.c |   6 +-\n>  t/t0065-dir-iterator.sh      |  61 +++++++++++++++++-\n>  5 files changed, 179 insertions(+), 67 deletions(-)\n>\n> diff --git a/dir-iterator.c b/dir-iterator.c\n> index ce8bf81..4b23889 100644\n> --- a/dir-iterator.c\n> +++ b/dir-iterator.c\n> @@ -4,8 +4,6 @@\n>  #include \"dir-iterator.h\"\n>\n>  struct dir_iterator_level {\n> -       int initialized;\n> -\n>         DIR *dir;\n>\n>         /*\n> @@ -20,8 +18,11 @@ struct dir_iterator_level {\n>          * iteration and also iterated into):\n>          */\n>         enum {\n> -               DIR_STATE_ITER,\n> -               DIR_STATE_RECURSE\n> +               DIR_STATE_PUSHED,\n> +               DIR_STATE_PRE_ITERATION,\n> +               DIR_STATE_ITERATING,\n> +               DIR_STATE_POST_ITERATION,\n> +               DIR_STATE_EXHAUSTED\n>         } dir_state;\n>  };\n>\n> @@ -48,15 +49,20 @@ struct dir_iterator_int {\n>          * that will be included in this iteration.\n>          */\n>         struct dir_iterator_level *levels;\n> +\n> +       /* Holds the flags passed to dir_iterator_begin(). */\n> +       unsigned flags;\n>  };\n>\n>  static inline void push_dir_level(struct dir_iterator_int *iter, struct dir_iterator_level *level)\n>  {\n> -       level->dir_state = DIR_STATE_RECURSE;\n>         ALLOC_GROW(iter->levels, iter->levels_nr + 1,\n>                    iter->levels_alloc);\n> +\n> +       /* Push a new level */\n>         level = &iter->levels[iter->levels_nr++];\n> -       level->initialized = 0;\n> +       level->dir = NULL;\n> +       level->dir_state = DIR_STATE_PUSHED;\n>  }\n>\n>  static inline int pop_dir_level(struct dir_iterator_int *iter)\n> @@ -75,18 +81,35 @@ static inline int set_iterator_data(struct dir_iterator_int *iter, struct dir_it\n>         }\n>\n>         /*\n> -        * We have to set these each time because\n> -        * the path strbuf might have been realloc()ed.\n> +        * Check if we are dealing with the root directory as an\n> +        * item that's being iterated through.\n>          */\n> -       iter->base.relative_path =\n> -               iter->base.path.buf + iter->levels[0].prefix_len;\n> +       if (level->dir_state != DIR_STATE_ITERATING &&\n> +               iter->levels_nr == 1) {\n> +               iter->base.relative_path = \".\";\n> +       }\n> +       else {\n> +               iter->base.relative_path =\n> +                       iter->base.path.buf + iter->levels[0].prefix_len;\n> +       }\n>         iter->base.basename =\n>                 iter->base.path.buf + level->prefix_len;\n> -       level->dir_state = DIR_STATE_ITER;\n>\n>         return 0;\n>  }\n>\n> +/*\n> + * This function uses a state machine with the following states:\n> + * -> DIR_STATE_PUSHED: the directory has been pushed to the\n> + * iterator traversal tree.\n> + * -> DIR_STATE_PRE_ITERATION: the directory is *NOT* initialized. The\n> + * dirpath has already been returned if pre-order traversal is set.\n> + * -> DIR_STATE_ITERATING: the directory is initialized. We are traversing\n> + * through it.\n> + * -> DIR_STATE_POST_ITERATION: the directory has been iterated through.\n> + * We are ready to close it.\n> + * -> DIR_STATE_EXHAUSTED: the directory is closed and ready to be popped.\n> + */\n>  int dir_iterator_advance(struct dir_iterator *dir_iterator)\n>  {\n>         struct dir_iterator_int *iter =\n> @@ -97,7 +120,18 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)\n>                         &iter->levels[iter->levels_nr - 1];\n>                 struct dirent *de;\n>\n> -               if (!level->initialized) {\n> +               if (level->dir_state == DIR_STATE_PUSHED) {\n> +                       level->dir_state = DIR_STATE_PRE_ITERATION;\n> +\n> +                       if (iter->flags & DIR_ITERATOR_PRE_ORDER_TRAVERSAL) {\n> +                               /* We may not want the root directory to be iterated over */\n> +                               if (iter->levels_nr != 1 ||\n> +                                       (iter->flags & DIR_ITERATOR_LIST_ROOT_DIR)) {\n> +                                       set_iterator_data(iter, level);\n> +                                       return ITER_OK;\n> +                               }\n> +                       }\n> +               } else if (level->dir_state == DIR_STATE_PRE_ITERATION) {\n>                         /*\n>                          * Note: dir_iterator_begin() ensures that\n>                          * path is not the empty string.\n> @@ -108,63 +142,32 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)\n>\n>                         level->dir = opendir(iter->base.path.buf);\n>                         if (!level->dir && errno != ENOENT) {\n> +                               /*\n> +                                * This level wasn't opened sucessfully; pretend we\n> +                                * iterated through it already.\n> +                                */\n>                                 warning(\"error opening directory %s: %s\",\n>                                         iter->base.path.buf, strerror(errno));\n> -                               /* Popping the level is handled below */\n> -                       }\n>\n> -                       level->initialized = 1;\n> -               } else if (S_ISDIR(iter->base.st.st_mode)) {\n> -                       if (level->dir_state == DIR_STATE_ITER) {\n> -                               /*\n> -                                * The directory was just iterated\n> -                                * over; now prepare to iterate into\n> -                                * it.\n> -                                */\n> -                               push_dir_level(iter, level);\n> +                               level->dir_state = DIR_STATE_POST_ITERATION;\n>                                 continue;\n> -                       } else {\n> -                               /*\n> -                                * The directory has already been\n> -                                * iterated over and iterated into;\n> -                                * we're done with it.\n> -                                */\n>                         }\n> -               }\n>\n> -               if (!level->dir) {\n> -                       /*\n> -                        * This level is exhausted (or wasn't opened\n> -                        * successfully); pop up a level.\n> -                        */\n> -                       if (pop_dir_level(iter) == 0)\n> -                               return dir_iterator_abort(dir_iterator);\n> -\n> -                       continue;\n> -               }\n> -\n> -               /*\n> -                * Loop until we find an entry that we can give back\n> -                * to the caller:\n> -                */\n> -               while (1) {\n> +                       level->dir_state = DIR_STATE_ITERATING;\n> +               } else if (level->dir_state == DIR_STATE_ITERATING) {\n>                         strbuf_setlen(&iter->base.path, level->prefix_len);\n>                         errno = 0;\n>                         de = readdir(level->dir);\n>\n>                         if (!de) {\n> -                               /* This level is exhausted; pop up a level. */\n> +                               /* In case of readdir() error */\n>                                 if (errno) {\n>                                         warning(\"error reading directory %s: %s\",\n>                                                 iter->base.path.buf, strerror(errno));\n> -                               } else if (closedir(level->dir))\n> -                                       warning(\"error closing directory %s: %s\",\n> -                                               iter->base.path.buf, strerror(errno));\n> +                               }\n>\n> -                               level->dir = NULL;\n> -                               if (pop_dir_level(iter) == 0)\n> -                                       return dir_iterator_abort(dir_iterator);\n> -                               break;\n> +                               level->dir_state = DIR_STATE_POST_ITERATION;\n> +                               continue;\n>                         }\n>\n>                         if (is_dot_or_dotdot(de->d_name))\n> @@ -175,7 +178,38 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)\n>                         if (set_iterator_data(iter, level))\n>                                 continue;\n>\n> +                       if (S_ISDIR(iter->base.st.st_mode)) {\n> +                               push_dir_level(iter, level);\n> +                               continue;\n> +                       }\n> +\n>                         return ITER_OK;\n> +               } else if (level->dir_state == DIR_STATE_POST_ITERATION) {\n> +                       if (level->dir != NULL && closedir(level->dir)) {\n> +                               warning(\"error closing directory %s: %s\",\n> +                                       iter->base.path.buf, strerror(errno));\n> +                       }\n> +                       level->dir_state = DIR_STATE_EXHAUSTED;\n> +\n> +                       strbuf_setlen(&iter->base.path, level->prefix_len);\n> +                       /*\n> +                        * Since we are iterating through the dirpath\n> +                        * after we have gone through it, we still need\n> +                        * to get rid of the trailing slash we appended.\n> +                        */\n> +                       strbuf_strip_suffix(&iter->base.path, \"/\");\n> +\n> +                       if (iter->flags & DIR_ITERATOR_POST_ORDER_TRAVERSAL) {\n> +                               /* We may not want the root directory to be iterated over */\n> +                               if (iter->levels_nr != 1 ||\n> +                                       (iter->flags & DIR_ITERATOR_LIST_ROOT_DIR)) {\n> +                                       set_iterator_data(iter, level);\n> +                                       return ITER_OK;\n> +                               }\n> +                       }\n> +               } else if (level->dir_state == DIR_STATE_EXHAUSTED) {\n> +                       if (pop_dir_level(iter) == 0)\n> +                               return dir_iterator_abort(dir_iterator);\n>                 }\n>         }\n>  }\n> @@ -201,7 +235,7 @@ int dir_iterator_abort(struct dir_iterator *dir_iterator)\n>         return ITER_DONE;\n>  }\n>\n> -struct dir_iterator *dir_iterator_begin(const char *path)\n> +struct dir_iterator *dir_iterator_begin(const char *path, unsigned flags)\n>  {\n>         struct dir_iterator_int *iter = xcalloc(1, sizeof(*iter));\n>         struct dir_iterator *dir_iterator = &iter->base;\n> @@ -209,13 +243,16 @@ struct dir_iterator *dir_iterator_begin(const char *path)\n>         if (!path || !*path)\n>                 die(\"BUG: empty path passed to dir_iterator_begin()\");\n>\n> +       iter->flags = flags;\n> +\n>         strbuf_init(&iter->base.path, PATH_MAX);\n>         strbuf_addstr(&iter->base.path, path);\n>\n>         ALLOC_GROW(iter->levels, 10, iter->levels_alloc);\n>\n>         iter->levels_nr = 1;\n> -       iter->levels[0].initialized = 0;\n> +       iter->levels[0].dir = NULL;\n> +       iter->levels[0].dir_state = DIR_STATE_PUSHED;\n>\n>         return dir_iterator;\n>  }\n> diff --git a/dir-iterator.h b/dir-iterator.h\n> index 27739e6..0e82f36 100644\n> --- a/dir-iterator.h\n> +++ b/dir-iterator.h\n> @@ -11,13 +11,12 @@\n>   * Every time dir_iterator_advance() is called, update the members of\n>   * the dir_iterator structure to reflect the next path in the\n>   * iteration. The order that paths are iterated over within a\n> - * directory is undefined, but directory paths are always iterated\n> - * over before the subdirectory contents.\n> + * directory is undefined.\n>   *\n>   * A typical iteration looks like this:\n>   *\n>   *     int ok;\n> - *     struct iterator *iter = dir_iterator_begin(path);\n> + *     struct iterator *iter = dir_iterator_begin(path, flags);\n>   *\n>   *     while ((ok = dir_iterator_advance(iter)) == ITER_OK) {\n>   *             if (want_to_stop_iteration()) {\n> @@ -38,6 +37,22 @@\n>   * dir_iterator_advance() again.\n>   */\n>\n> +/*\n> + * Possible flags for dir_iterator_begin().\n> + *\n> + * -> DIR_ITERATOR_PRE_ORDER_TRAVERSAL: the iterator shall return\n> + * a dirpath it has found before iterating through that directory's\n> + * contents.\n> + * -> DIR_ITERATOR_POST_ORDER_TRAVERSAL: the iterator shall return\n> + * a dirpath it has found after iterating through that directory's\n> + * contents.\n> + * -> DIR_ITERATOR_LIST_ROOT_DIR: the iterator shall return the dirpath\n> + * of the root directory it is iterating through.\n> + */\n> +#define DIR_ITERATOR_PRE_ORDER_TRAVERSAL (1 << 0)\n> +#define DIR_ITERATOR_POST_ORDER_TRAVERSAL (1 << 1)\n> +#define DIR_ITERATOR_LIST_ROOT_DIR (1 << 2)\n> +\n>  struct dir_iterator {\n>         /* The current path: */\n>         struct strbuf path;\n> @@ -57,15 +72,16 @@ struct dir_iterator {\n>  };\n>\n>  /*\n> - * Start a directory iteration over path. Return a dir_iterator that\n> - * holds the internal state of the iteration.\n> + * Start a directory iteration over path, with options specified in\n> + * 'flags'. Return a dir_iterator that holds the internal state of\n> + * the iteration.\n>   *\n>   * The iteration includes all paths under path, not including path\n>   * itself and not including \".\" or \"..\" entries.\n>   *\n>   * path is the starting directory. An internal copy will be made.\n>   */\n> -struct dir_iterator *dir_iterator_begin(const char *path);\n> +struct dir_iterator *dir_iterator_begin(const char *path, unsigned flags);\n>\n>  /*\n>   * Advance the iterator to the first or next item and return ITER_OK.\n> diff --git a/refs/files-backend.c b/refs/files-backend.c\n> index 50188e9..b4bba74 100644\n> --- a/refs/files-backend.c\n> +++ b/refs/files-backend.c\n> @@ -3346,7 +3346,7 @@ static struct ref_iterator *files_reflog_iterator_begin(struct ref_store *ref_st\n>         files_downcast(ref_store, 0, \"reflog_iterator_begin\");\n>\n>         base_ref_iterator_init(ref_iterator, &files_reflog_iterator_vtable);\n> -       iter->dir_iterator = dir_iterator_begin(git_path(\"logs\"));\n> +       iter->dir_iterator = dir_iterator_begin(git_path(\"logs\"), 0);\n>         return ref_iterator;\n>  }\n>\n> diff --git a/t/helper/test-dir-iterator.c b/t/helper/test-dir-iterator.c\n> index 06f03fc..a1b8c78 100644\n> --- a/t/helper/test-dir-iterator.c\n> +++ b/t/helper/test-dir-iterator.c\n> @@ -6,6 +6,7 @@\n>  int cmd_main(int argc, const char **argv) {\n>         struct strbuf path = STRBUF_INIT;\n>         struct dir_iterator *diter;\n> +       unsigned flag = DIR_ITERATOR_PRE_ORDER_TRAVERSAL;\n>\n>         if (argc < 2) {\n>                 return 1;\n> @@ -13,7 +14,10 @@ int cmd_main(int argc, const char **argv) {\n>\n>         strbuf_add(&path, argv[1], strlen(argv[1]));\n>\n> -       diter = dir_iterator_begin(path.buf);\n> +       if (argc == 3)\n> +               flag = atoi(argv[2]);\n> +\n> +       diter = dir_iterator_begin(path.buf, flag);\n>\n>         while (dir_iterator_advance(diter) == ITER_OK) {\n>                 if (S_ISDIR(diter->st.st_mode))\n> diff --git a/t/t0065-dir-iterator.sh b/t/t0065-dir-iterator.sh\n> index b857c07..ade3ee0 100755\n> --- a/t/t0065-dir-iterator.sh\n> +++ b/t/t0065-dir-iterator.sh\n> @@ -28,12 +28,28 @@ test_expect_success 'dir-iterator should iterate through all files' '\n>         >dir/a/e &&\n>         >dir/d/e/d/a &&\n>\n> -       test-dir-iterator ./dir | sort >./actual-pre-order-sorted-output &&\n> +       test-dir-iterator ./dir 1 | sort >./actual-pre-order-sorted-output &&\n>         rm -rf dir &&\n>\n>         test_cmp expect-sorted-output actual-pre-order-sorted-output\n>  '\n>\n> +test_expect_success 'dir-iterator should iterate through all files on post-order mode' '\n> +       mkdir -p dir &&\n> +       mkdir -p dir/a/b/c/ &&\n> +       >dir/b &&\n> +       >dir/c &&\n> +       mkdir -p dir/d/e/d/ &&\n> +       >dir/a/b/c/d &&\n> +       >dir/a/e &&\n> +       >dir/d/e/d/a &&\n> +\n> +       test-dir-iterator ./dir 2 | sort >actual-post-order-sorted-output &&\n> +       rm -rf dir &&\n> +\n> +       test_cmp expect-sorted-output actual-post-order-sorted-output\n> +'\n> +\n>  cat >expect-pre-order-output <<-\\EOF &&\n>  [d] (a) ./dir/a\n>  [d] (a/b) ./dir/a/b\n> @@ -41,14 +57,53 @@ cat >expect-pre-order-output <<-\\EOF &&\n>  [f] (a/b/c/d) ./dir/a/b/c/d\n>  EOF\n>\n> -test_expect_success 'dir-iterator should list files in the correct order' '\n> +test_expect_success 'dir-iterator should list files properly on pre-order mode' '\n>         mkdir -p dir/a/b/c/ &&\n>         >dir/a/b/c/d &&\n>\n> -       test-dir-iterator ./dir >actual-pre-order-output &&\n> +       test-dir-iterator ./dir 1 >actual-pre-order-output &&\n>         rm -rf dir &&\n>\n>         test_cmp expect-pre-order-output actual-pre-order-output\n>  '\n>\n> +cat >expect-post-order-output <<-\\EOF &&\n> +[f] (a/b/c/d) ./dir/a/b/c/d\n> +[d] (a/b/c) ./dir/a/b/c\n> +[d] (a/b) ./dir/a/b\n> +[d] (a) ./dir/a\n> +EOF\n> +\n> +test_expect_success 'dir-iterator should list files properly on post-order mode' '\n> +       mkdir -p dir/a/b/c/ &&\n> +       >dir/a/b/c/d &&\n> +\n> +       test-dir-iterator ./dir 2 >actual-post-order-output &&\n> +       rm -rf dir &&\n> +\n> +       test_cmp expect-post-order-output actual-post-order-output\n> +'\n> +\n> +cat >expect-pre-order-post-order-root-dir-output <<-\\EOF &&\n> +[d] (.) ./dir\n> +[d] (a) ./dir/a\n> +[d] (a/b) ./dir/a/b\n> +[d] (a/b/c) ./dir/a/b/c\n> +[f] (a/b/c/d) ./dir/a/b/c/d\n> +[d] (a/b/c) ./dir/a/b/c\n> +[d] (a/b) ./dir/a/b\n> +[d] (a) ./dir/a\n> +[d] (.) ./dir\n> +EOF\n> +\n> +test_expect_success 'dir-iterator should list files properly on pre-order + post-order + root-dir mode' '\n> +       mkdir -p dir/a/b/c/ &&\n> +       >dir/a/b/c/d &&\n> +\n> +       test-dir-iterator ./dir 7 >actual-pre-order-post-order-root-dir-output &&\n> +       rm -rf dir &&\n> +\n> +       test_cmp expect-pre-order-post-order-root-dir-output actual-pre-order-post-order-root-dir-output\n> +'\n> +\n>  test_done\n> --\n> 2.7.4 (Apple Git-66)\n>\n"},{"id":"316046","messageId":"235ce437-9f87-e309-cec4-8214bb76b47f@alum.mit.edu","threadId":"45587","inReplyTo":"CAEA2_RJuxw+sZ0CABCfTMnY+Wy5KD2totG76FDWfpH1Uht2taw@mail.gmail.com","subject":"Re: [PATCH v6 4/5] dir_iterator: refactor state machine model","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-04-02T05:35:55Z","receivedAt":"2017-04-02T05:36:10Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 04/02/2017 06:46 AM, Daniel Ferreira (theiostream) wrote:\n> Gah, I just realized I failed to correct refs/files-backend.c's\n> behavior and kept 0 instead of DIR_ITERATOR_PRE_ORDER_TRAVERSAL as its\n> flag. I'll correct this on a v7, but I'll wait for the rest of your\n> reviews before sending that revision.\n\nEven if I make that change, a lot of tests fail, both when I run the\ntests against your commit 4/5 and when I run them against 5/5.\n\nI tested by applying your patch series to the current upstream master\nbranch. When I apply the patches, there is one conflict (related to\n#includes), in entry.c. Maybe the failure is because you are working\nfrom a different branch point. What commit are you branching your series\noff of?\n\nYou should definitely run the full test suite against each of your\ncommits before you submit. One convenient way to do so is with my tool\n`git-test` [1], which runs the tests and keeps track of their results to\navoid testing the same commit over and over again:\n\n    # One-time setup (adjust the \"-j\" values based on what's\n    # fastest on your computer):\n    git test add \"make -j8 && make -j16 test\"\n\n    # Run tests against a range of commits:\n    git test run master..mybranch\n\nEven better is to run the tests in a separate linked worktree, so that\nyou can continue working in your main repository while the tests are\nrunning. The `git-test` README explains how.\n\nIt also speeds things up (and gives better output) if you use `prove` to\nrun the tests, and run the tests on a ramdisk if possible. To do so, I\ninclude the following lines in my `config.mak`:\n\n    TMP := /var/tmp\n    ROOT := $(TMP)/git-tests-$(shell git rev-parse --show-toplevel |\nsha1sum | head -c10)\n    DEFAULT_TEST_TARGET = prove\n    GIT_TEST_OPTS = -q --root=$(ROOT) --tee\n    GIT_PROVE_OPTS = --timer --jobs 16 --state=fresh,hot,slow,save\n\n(On my system `/var/tmp` is a ramdisk.)\n\nFinally, when I submit a patch series, I usually also push a copy to my\nGitHub fork of the project and include a reference to that branch in my\ncover letter. That makes it easier for casual readers to fetch the code\nand/or look at it online, and also makes it 100% clear what branch point\nI've chosen. This is by no means obligatory but I find it helpful.\n\nThere doesn't seem to be much point reviewing broken code, so I'll wait\nfor your feedback and/or fix.\n\nMichael\n\n[1] https://github.com/mhagger/git-test\n\n"}]}