{"thread":{"id":"45591","subject":"[PATCH v7 0/5] [GSoC] remove_subtree(): reimplement using iterators","startedAt":"2017-04-02T20:05:19Z","lastAt":"2017-04-04T06:36:59Z","messageCount":13,"participants":["Daniel Ferreira","Michael Haggerty","Daniel Ferreira (theiostream)","Stefan Beller"],"isPatch":true,"patchVersion":7,"patchTotal":5},"messages":[{"id":"316071","messageId":"1491163388-41255-1-git-send-email-bnmvco@gmail.com","threadId":"45591","inReplyTo":null,"subject":"[PATCH v7 0/5] [GSoC] remove_subtree(): reimplement using iterators","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-02T20:03:03Z","receivedAt":"2017-04-02T20:05:19Z","isPatch":true,"sender":{"key":"bnmvco@gmail.com","avatar":"https://avatars.githubusercontent.com/u/735397?v=4"},"body":"This is the seventh 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\nv6: https://public-inbox.org/git/1491107726-21504-1-git-send-email-bnmvco@gmail.com/T/#t\n\nI screwed up in v6 because I had introduced a bug that in case git tried to open\na directory that did not exist using dir_iterator, the program would segfault. This\nwas amended and all commits are passing the tests. Sorry for not having tested\nmy changes properly.\n\nCI build: https://travis-ci.org/theiostream/git\n\nSince the changes in v6 were not reviewed, I'll just copy what was sent\nback there.\n\n> Back in v5, Michael had a number of suggestions, all of which were applied\n> to this version (including a slightly modified version of his \"biggish rewrite\"\n> project to make dir_iterator's state machine simpler). The only suggestion that\n> did not make it into this series was that of not traversing into subdirectories,\n> since I believe it would be better off in another series that actually required\n> that feature (that is, I do not want a series to implement a feature it will\n> not need). The same goes for Junio's thought on a flag to list *only* directories\n> and no files on the v4 discussion.\n\n> Junio and Peff's comments about how to write to files in the tests were also\n> considered, and the tests were adjusted.\n\n> I chose to squash both the state machine refactor and the addition of the\n> new flags in a single commit. I do not know whether you will feel this is\n> the right choice but it seemed natural, since most of the state machine's\n> new logic would not even make sense without encompassing the new features.\n> I am, of course, open for feedback on this decision.\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                  | 196 ++++++++++++++++++++++++++--------------\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, 316 insertions(+), 102 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":"316072","messageId":"1491163388-41255-2-git-send-email-bnmvco@gmail.com","threadId":"45591","inReplyTo":"1491163388-41255-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v7 1/5] dir_iterator: add tests for dir_iterator API","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-02T20:03:04Z","receivedAt":"2017-04-02T20:05:23Z","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 9b36068..41ce9ab 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -614,6 +614,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 758ed2e..a7d74d3 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":"316073","messageId":"1491163388-41255-3-git-send-email-bnmvco@gmail.com","threadId":"45591","inReplyTo":"1491163388-41255-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v7 2/5] remove_subtree(): test removing nested directories","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-02T20:03:05Z","receivedAt":"2017-04-02T20:05:28Z","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":"316074","messageId":"1491163388-41255-4-git-send-email-bnmvco@gmail.com","threadId":"45591","inReplyTo":"1491163388-41255-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v7 3/5] dir_iterator: add helpers to dir_iterator_advance","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-02T20:03:06Z","receivedAt":"2017-04-02T20:05:36Z","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":"316075","messageId":"1491163388-41255-5-git-send-email-bnmvco@gmail.com","threadId":"45591","inReplyTo":"1491163388-41255-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v7 4/5] dir_iterator: refactor state machine model","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-02T20:03:07Z","receivedAt":"2017-04-02T20:05:43Z","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               | 155 +++++++++++++++++++++++++++----------------\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, 183 insertions(+), 69 deletions(-)\n\ndiff --git a/dir-iterator.c b/dir-iterator.c\nindex ce8bf81..18b7e68 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@@ -107,64 +141,35 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)\n \t\t\tlevel->prefix_len = iter->base.path.len;\n \n \t\t\tlevel->dir = opendir(iter->base.path.buf);\n-\t\t\tif (!level->dir && errno != ENOENT) {\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\tif (!level->dir) {\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 * 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\tpush_dir_level(iter, level);\n+\t\t\t\tif (errno != ENOENT) {\n+\t\t\t\t\twarning(\"error opening 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_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 +180,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 +237,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 +245,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..c29dc68 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\"), DIR_ITERATOR_PRE_ORDER_TRAVERSAL);\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":"316076","messageId":"1491163388-41255-6-git-send-email-bnmvco@gmail.com","threadId":"45591","inReplyTo":"1491163388-41255-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v7 5/5] remove_subtree(): reimplement using iterators","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-02T20:03:08Z","receivedAt":"2017-04-02T20:05:47Z","isPatch":true,"sender":{"key":"bnmvco@gmail.com","avatar":"https://avatars.githubusercontent.com/u/735397?v=4"},"body":"From: Daniel Ferreira <daniel.calibeta@gmail.com>\n\nUse 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 d2b512d..bd06f41 100644\n--- a/entry.c\n+++ b/entry.c\n@@ -3,6 +3,8 @@\n #include \"dir.h\"\n #include \"streaming.h\"\n #include \"submodule.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@@ -45,33 +47,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@@ -312,7 +298,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":"316080","messageId":"76c92397-8e15-b2fb-432f-0ae3d987ffa8@alum.mit.edu","threadId":"45591","inReplyTo":"1491163388-41255-5-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v7 4/5] dir_iterator: refactor state machine model","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-04-03T03:36:49Z","receivedAt":"2017-04-03T03:37:04Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 04/02/2017 10:03 PM, Daniel Ferreira 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\nNice. I think this version is a lot more understandable than the old\ncode. I also think it's getting very close to done.\n\n> Signed-off-by: Daniel Ferreira <bnmvco@gmail.com>\n> ---\n>  dir-iterator.c               | 155 +++++++++++++++++++++++++++----------------\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, 183 insertions(+), 69 deletions(-)\n> \n> diff --git a/dir-iterator.c b/dir-iterator.c\n> index ce8bf81..18b7e68 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\nDoesn't `iter->base.basename` also need special handling in this case?\n\n> +\t}\n> +\telse {\n\nThe Git project standard is to including the `else` on the same line as\nthe curly brace ending the `if` block:\n\n\t} else {\n\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\nIt would be a tiny improvement in readability to change the check\n`iter->levels_nr != 1` to `iters->levels_nr > 1`, to help make it\nclearer that this code block is not about `iters->level_nr == 0`.\n\n> +\t\t\t\t\tset_iterator_data(iter, level);\n\nset_iterator_data() reports errors by returning -1, but here (and in the\nDIR_ITERATOR_POST_ORDER_TRAVERSAL code block below) you fail to check\nthe return value.\n\nIf you are thinking to yourself \"that can't happen because I already\nchecked `lstat()` in a previous iteration of the loop\", remember that\nanother process might be changing things on the filesystem at the same\ntime as the iteration is running (\"TOCTOU\").\n\nBut of course that would make for slightly strange behavior if, during\nthe PRE_ORDER_TRAVERSAL, a directory is readable, but by the time of the\nPOST_ORDER_TRAVERSAL, it has disappeared. The iteration might list the\ncontents of a directory but not the POST_ORDER_TRAVERSAL of the\ndirectory itself. Or, if both PRE and POST are being used, there would\nbe an \"entering directory\" event but no matching \"leaving directory\"\nevent, which could be confusing to a hypothetical caller who expects the\n\"entering directory\" and \"leaving directory\" events to match up in pairs.\n\nFurthermore, you are calling `lstat()` more often than necessary. This\nfunction is quite expensive on Windows.\n\nYou could solve all three problems by running `lstat()` on the directory\nonce the first time you see it, storing its value in the\n`dir_iterator_level`, and copying that value to `iter->base.st` when it\nis needed. (This would fix the second problem by removing the need for a\nfailing `set_iterator_data()` call during the POST_ORDER_TRAVERSAL phase\nof processing a directory.)\n\nThis would mean that we might return stale `lstat()` data to the caller,\nbut note that `lstat()` data is *always* stale, because it is always\npossible that another process changes it the nanosecond after our\nprocess reads it. So it's a possibility that the caller has to deal with\nin any case.\n\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> @@ -107,64 +141,35 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)\n>  \t\t\tlevel->prefix_len = iter->base.path.len;\n>  \n>  \t\t\tlevel->dir = opendir(iter->base.path.buf);\n> -\t\t\tif (!level->dir && errno != ENOENT) {\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\tif (!level->dir) {\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 * 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\tpush_dir_level(iter, level);\n> +\t\t\t\tif (errno != ENOENT) {\n> +\t\t\t\t\twarning(\"error opening 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_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 +180,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\nAs far as I can tell, you got the logic in this complicated big loop\ncorrect on the first try (well, if we ignore v6 :-) ), even as you added\nnew features. I think that's good evidence that the new structure is\nmore comprehensible than the old, plus the new tests probably helped.\nThat's a big win!\n\n> @@ -201,7 +237,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 +245,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>  }\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\nI think it would be useful to mention here that the three options can be\nused in any combination.\n\nThe documentation for `DIR_ITERATOR_LIST_ROOT_DIR` isn't precisely\naccurate. If neither of the `*_ORDER_TRAVERSAL` options is specified,\nthen the root directory is not included in the iteration even if this\noption is specified. I think this is enough of a boundary case that it\ndoesn't really matter if you change the behavior or change the\ndocumentation, but one way or another please make them agree.\n\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\nThe sentence above should be updated now that you have implemented\n`DIR_ITERATOR_LIST_ROOT_DIR`.\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..c29dc68 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\"), DIR_ITERATOR_PRE_ORDER_TRAVERSAL);\n>  \treturn 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>  \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\nIt's not ideal that the test code depends on the numerical values of the\nflag constants, and it makes the tests harder to understand. It would be\nbetter if this program were to accept options like `--pre-order`,\n`--post-order`, etc., as I suggested in an earlier round of review.\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))\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>  \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\nThe setup done in the test above is identical to the setup for the test\nbefore it. Similarly, the last three tests also all use the same setup.\nPlease put all of the setup code in an extra \"pseudo-test\" at the top of\nthe file, to avoid duplication:\n\ntest_expect_success 'setup' '\n\tmkdir -p dir1 &&\n\tmkdir -p dir1/a/b/c/ &&\n\t>dir1/b &&\n\t>dir1/c &&\n\tmkdir -p dir1/d/e/d/ &&\n\t>dir1/a/b/c/d &&\n\t>dir1/a/e &&\n\t>dir1/d/e/d/a &&\n\n\tmkdir -p dir2/a/b/c/ &&\n\t>dir2/a/b/c/d\n'\n\nNote that at least one of the test directories has to be renamed so that\nthey don't conflict with each other.\n\nThere is no need for the individual tests to delete their test\ndirectories; the test harness will take care of that. But if you *did*\nneed to clean up after a test, you should do it like this:\n\n\tmkdir foo &&\n\ttest_when_finished \"rm -rf foo\" &&\n\t...tests involving foo...\n\nThe advantage of `test_when_finished` is that it ensures that the\ncleanup code is run even if some part of the test fails.\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\nMichael\n\n"},{"id":"316081","messageId":"92bd74cc-1ad9-608b-f431-017d35ce72bc@alum.mit.edu","threadId":"45591","inReplyTo":"1491163388-41255-6-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v7 5/5] remove_subtree(): reimplement using iterators","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-04-03T03:42:10Z","receivedAt":"2017-04-03T03:42:20Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 04/02/2017 10:03 PM, Daniel Ferreira wrote:\n> From: Daniel Ferreira <daniel.calibeta@gmail.com>\n> \n> Use dir_iterator to traverse through remove_subtree()'s directory tree,\n> avoiding the need for recursive calls to readdir(). Simplify\n> remove_subtree()'s code.\n> \n> A conversion similar in purpose was previously done at 46d092a\n> (\"for_each_reflog(): reimplement using iterators\", 2016-05-21).\n> \n> Signed-off-by: Daniel Ferreira <bnmvco@gmail.com>\n\nThis patch has a different author email than the others. If possible,\nplease choose one email address that you will use for your commits, and\ntry to be consistent.\n\n> ---\n>  entry.c | 38 ++++++++++++--------------------------\n>  1 file changed, 12 insertions(+), 26 deletions(-)\n> \n> diff --git a/entry.c b/entry.c\n> index d2b512d..bd06f41 100644\n> --- a/entry.c\n> +++ b/entry.c\n> @@ -3,6 +3,8 @@\n>  #include \"dir.h\"\n>  #include \"streaming.h\"\n>  #include \"submodule.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> @@ -45,33 +47,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\nThe line above is way too long. Try to limit lines to 80 characters max.\n(This is documented in `Documentation/CodingGuidelines`.)\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> @@ -312,7 +298,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> \n\nThat's a gratifying decrease in code size :-)\n\nMichael\n\n"},{"id":"316102","messageId":"CAEA2_R+EBbrD1rbcrP598AKJAEZDZfGY-ED8g+ehgAaL9tLG8A@mail.gmail.com","threadId":"45591","inReplyTo":"76c92397-8e15-b2fb-432f-0ae3d987ffa8@alum.mit.edu","subject":"Re: [PATCH v7 4/5] dir_iterator: refactor state machine model","fromName":"Daniel Ferreira (theiostream)","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-03T18:03:43Z","receivedAt":"2017-04-03T18:04:20Z","isPatch":true,"sender":{"key":"bnmvco@gmail.com","avatar":"https://avatars.githubusercontent.com/u/735397?v=4"},"body":"On Mon, Apr 3, 2017 at 12:36 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:\n> As far as I can tell, you got the logic in this complicated big loop\n> correct on the first try (well, if we ignore v6 :-) ), even as you added\n> new features. I think that's good evidence that the new structure is\n> more comprehensible than the old, plus the new tests probably helped.\n> That's a big win!\n\nThanks for ignoring v6 ;)\n\nAnother gain is that the other proposed features (only iterate over\ndirectories, do not recurse into subdirectories) are also quite easy\nto add with this new structure.\n\n> It's not ideal that the test code depends on the numerical values of the\n> flag constants, and it makes the tests harder to understand. It would be\n> better if this program were to accept options like `--pre-order`,\n> `--post-order`, etc., as I suggested in an earlier round of review.\n\nAlthough it does make tests harder to understand, if we were to\nspecify how to iterate with human-readable flags we'd add the getopt()\n+ flag configuration overhead to this helper program to be able to\nhandle all cases properly. Additionally, new flags added to\ndir_iterator would have to edit the test program as well, generating\nextra work.\n\nI personally think that the string describing the test in the script\nis enough to explain what the flag-as-argument is doing for the sake\nof readability. The only gain I see in your suggestion is that we\navoid the programmer committing errors calculating the flag by hand\nwhen writing the test.\n\nThat said, I'd appreciate some more thought on this.\n\n> Michael\n>\n\nThanks for the review. I agree with all other points and I'll address\nthem in a next series.\n"},{"id":"316116","messageId":"CAGZ79ka032GPTp1Y5GH5joKm1_arf4GAywPXipt869MobRwrVA@mail.gmail.com","threadId":"45591","inReplyTo":"1491163388-41255-2-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v7 1/5] dir_iterator: add tests for dir_iterator API","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-04-03T22:31:37Z","receivedAt":"2017-04-03T22:31:43Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Sun, Apr 2, 2017 at 1:03 PM, Daniel Ferreira <bnmvco@gmail.com> wrote:\n> Create t/helper/test-dir-iterator.c, which prints relevant information\n> about a directory tree iterated over with dir_iterator.\n>\n> Create t/t0065-dir-iterator.sh, which tests that dir_iterator does\n> iterate through a whole directory tree.\n>\n> Signed-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>\n> diff --git a/Makefile b/Makefile\n> index 9b36068..41ce9ab 100644\n> --- a/Makefile\n> +++ b/Makefile\n> @@ -614,6 +614,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\n> diff --git a/t/helper/.gitignore b/t/helper/.gitignore\n> index 758ed2e..a7d74d3 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\n> diff --git a/t/helper/test-dir-iterator.c b/t/helper/test-dir-iterator.c\n> new file mode 100644\n> index 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> +       struct strbuf path = STRBUF_INIT;\n> +       struct dir_iterator *diter;\n> +\n> +       if (argc < 2) {\n\nCoding style: please use no braces for single statements after\ncontrol structures (if, for, while).\n\nInstead of just returning 1 (which is harder to diagnose in an\ninteractive shell for users who do not know the details of this\nprogram), we could\n\n    die(\"BUG: test-dir-iterator takes exactly one argument\");\n\n> +               return 1;\n> +       }\n> +\n> +       strbuf_add(&path, argv[1], strlen(argv[1]));\n> +\n> +       diter = dir_iterator_begin(path.buf);\n> +\n> +       while (dir_iterator_advance(diter) == ITER_OK) {\n> +               if (S_ISDIR(diter->st.st_mode))\n> +                       printf(\"[d] \");\n> +               else\n> +                       printf(\"[f] \");\n\nIn the operating system there are more 'st_mode's than\njust directory or file, e.g. symbolic link.\n\nMaybe\n\n    else if (S_ISREG(diter->st.st_mode))\n        printf(\"[f] \");\n    else\n        printf(\"[?]\");\n\nto catch the unknown things better instead of\ndefaulting them to regular files?\n\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> +       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 | sort >./actual-pre-order-sorted-output &&\n\nWe just had some micro projects that were trying to get rid of git\ncommands on the upstream of a pipe, to better observe\nthe exit codes of the programs that we write here. I think it is\nnot as critical for test helpers, but the it would be better to diagnose\nan error when we had\n\n    test-dir-iterator ./dir >out &&\n    sort <out >actual &&\n    test_cmp expect actual\n\nas in case of an error we'd stop early in the && chain at test-dir-iterator\n(and if that would use the die() function we'd even get some error message\non stderr).\n\n> +       rm -rf dir &&\n\nI'd put that cleanup first via\ntest_expect_success 'title' '\n    test_when_finished \"rm -rf dir\" &&\n    mkdir ... &&\n    ...\n'\n\nBy doing so, an inspection is easier afterwards.\nWhen this test breaks, you'd want to debug it via e.g.\n\n  cd t\n  ./t0065-dir-iterator.sh -d -i -v -x # see README for all the nice flags)\n\nwhich in case of error would stop at e.g. test_cmp failing. But at that\npoint of the test we already removed the files so it is impossible to inspect\nwhat was on the file system, without adding a test_pause before the rm.\n\n> +\n> +       test_cmp expect-sorted-output actual-pre-order-sorted-output\n\nUsually the file names are shorter (expect, actual), but I do not\nmind encoding some expectation in them.\n\nThanks,\nStefan\n"},{"id":"316117","messageId":"CAGZ79kbrPjKV=Gi0AHHwSAS_DviysvpSd_6g-w-XuD0R3ceDwg@mail.gmail.com","threadId":"45591","inReplyTo":"1491163388-41255-3-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v7 2/5] remove_subtree(): test removing nested directories","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-04-03T22:35:23Z","receivedAt":"2017-04-03T22:35:29Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Sun, Apr 2, 2017 at 1:03 PM, Daniel Ferreira <bnmvco@gmail.com> wrote:\n> Test removing a nested directory when an attempt is made to restore the\n> index to a state where it does not exist. A similar test could be found\n> previously in t/t2000-checkout-cache-clash.sh, but it did not check for\n> nested directories, which could allow a faulty implementation of\n> remove_subtree() pass the tests.\n>\n> Signed-off-by: Daniel Ferreira <bnmvco@gmail.com>\n> ---\n>  t/t2000-checkout-cache-clash.sh | 11 +++++++++++\n>  1 file changed, 11 insertions(+)\n>\n> diff --git a/t/t2000-checkout-cache-clash.sh b/t/t2000-checkout-cache-clash.sh\n> index 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>         git checkout-index -a -f --prefix=there/\n>  '\n>\n> +test_expect_success 'git checkout-index -f should remove nested subtrees' '\n> +       echo content >path &&\n> +       git update-index --add path &&\n> +       rm path &&\n> +       mkdir -p path/with/nested/paths &&\n> +       echo content >path/file1 &&\n> +       echo content >path/with/nested/paths/file2 &&\n> +       git checkout-index -f -a &&\n> +       test ! -d path\n> +'\n> +\n\nLooks good to me.\n\nThanks,\nStefan\n"},{"id":"316120","messageId":"CAGZ79kYrH73WrXyw+JypdSVfgpvduL-mUVZ3yyEUuib4BTZ9uw@mail.gmail.com","threadId":"45591","inReplyTo":"1491163388-41255-4-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v7 3/5] dir_iterator: add helpers to dir_iterator_advance","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-04-03T22:48:40Z","receivedAt":"2017-04-03T22:48:46Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Sun, Apr 2, 2017 at 1:03 PM, Daniel Ferreira <bnmvco@gmail.com> wrote:\n> Create inline helpers to dir_iterator_advance(). Make\n> dir_iterator_advance()'s code more legible and allow some behavior to\n> be reusable.\n>\n> Signed-off-by: Daniel Ferreira <bnmvco@gmail.com>\n> ---\n\n\n> +static inline void push_dir_level(struct dir_iterator_int *iter, struct dir_iterator_level *level)\n\nSometimes we use inline, sometimes we do not:\n$ git grep \"static inline\" -- *.c |wc -l\n84\n$ git grep \"static inline\" -- *.h |wc -l\n130\n# approximate a function definition:\n$ git grep -e \"static\" -- *.c  |grep \"(\"|wc -l\n2971\n\nSo I think we'd want to have the inline keyword in\nthe header only (when the code is actually to be inlined).\nAs a C file is one translation unit, the compiler can figure\nout best whether to inline a particular static function on\nits own.\n\nThe rest looks good to me,\n\nThanks,\nStefan\n"},{"id":"316134","messageId":"bfd5d9a07139dbc6eb1fd1dc82ffb38dbbefee1e.1491286711.git.mhagger@alum.mit.edu","threadId":"45591","inReplyTo":"CAEA2_R+EBbrD1rbcrP598AKJAEZDZfGY-ED8g+ehgAaL9tLG8A@mail.gmail.com","subject":"Re: [PATCH v7 4/5] dir_iterator: refactor state machine model","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-04-04T06:36:35Z","receivedAt":"2017-04-04T06:36:59Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\nDaniel,\n\n> Although it does make tests harder to understand, if we were to\n> specify how to iterate with human-readable flags we'd add the getopt()\n> + flag configuration overhead to this helper program to be able to\n> handle all cases properly. Additionally, new flags added to\n> dir_iterator would have to edit the test program as well, generating\n> extra work.\n\nI think you're exaggerating the amount of extra work. I think all you\nneed to do is squash the attached patch into your patch 4/5, for the\ngain of only 14 lines of simple code, four of which could be deleted\nif you don't care about supporting \"--\". Supporting hypothetical\nfuture new options would cost exactly two more lines for each option.\nPlus, this also fixes the handling of more than two args.\n\nIt might be even shorter if you use `parse_options()`, but that seems\nlike overkill here.\n\nOn the plus side, anybody can now change the `DIR_ITERATOR_*`\nconstants without breaking things, or grep for them to find all of the\nplaces that they are used. Plus the test code is more readable.\n\nIn my opinion that is a win.\n\nMichael\n\n t/helper/test-dir-iterator.c | 28 +++++++++++++++++++++-------\n t/t0065-dir-iterator.sh      | 10 +++++-----\n 2 files changed, 26 insertions(+), 12 deletions(-)\n\ndiff --git a/t/helper/test-dir-iterator.c b/t/helper/test-dir-iterator.c\nindex a1b8c78434..c2eb2ca1f9 100644\n--- a/t/helper/test-dir-iterator.c\n+++ b/t/helper/test-dir-iterator.c\n@@ -4,18 +4,32 @@\n #include \"dir-iterator.h\"\n \n int cmd_main(int argc, const char **argv) {\n+\tconst char **myargv = argv;\n+\tint myargc = argc;\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+\tunsigned flag = 0;\n+\n+\twhile (--myargc && starts_with(*++myargv, \"--\")) {\n+\t\tif (!strcmp(*myargv, \"--pre-order\")) {\n+\t\t\tflag |= DIR_ITERATOR_PRE_ORDER_TRAVERSAL;\n+\t\t} else if (!strcmp(*myargv, \"--post-order\")) {\n+\t\t\tflag |= DIR_ITERATOR_POST_ORDER_TRAVERSAL;\n+\t\t} else if (!strcmp(*myargv, \"--list-root-dir\")) {\n+\t\t\tflag |= DIR_ITERATOR_LIST_ROOT_DIR;\n+\t\t} else if (!strcmp(*myargv, \"--\")) {\n+\t\t\tmyargc--;\n+\t\t\tmyargv++;\n+\t\t\tbreak;\n+\t\t} else {\n+\t\t\tdie(\"Unrecognized option: %s\", *myargv);\n+\t\t}\n \t}\n \n-\tstrbuf_add(&path, argv[1], strlen(argv[1]));\n+\tif (myargc != 1)\n+\t\tdie(\"expected exactly one non-option argument\");\n \n-\tif (argc == 3)\n-\t\tflag = atoi(argv[2]);\n+\tstrbuf_addstr(&path, *myargv);\n \n \tditer = dir_iterator_begin(path.buf, flag);\n \ndiff --git a/t/t0065-dir-iterator.sh b/t/t0065-dir-iterator.sh\nindex ade3ee0e7e..4819e6181d 100755\n--- a/t/t0065-dir-iterator.sh\n+++ b/t/t0065-dir-iterator.sh\n@@ -28,7 +28,7 @@ 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 1 | sort >./actual-pre-order-sorted-output &&\n+\ttest-dir-iterator --pre-order ./dir | sort >./actual-pre-order-sorted-output &&\n \trm -rf dir &&\n \n \ttest_cmp expect-sorted-output actual-pre-order-sorted-output\n@@ -44,7 +44,7 @@ test_expect_success 'dir-iterator should iterate through all files on post-order\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+\ttest-dir-iterator --post-order ./dir | sort >actual-post-order-sorted-output &&\n \trm -rf dir &&\n \n \ttest_cmp expect-sorted-output actual-post-order-sorted-output\n@@ -61,7 +61,7 @@ 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 1 >actual-pre-order-output &&\n+\ttest-dir-iterator --pre-order ./dir >actual-pre-order-output &&\n \trm -rf dir &&\n \n \ttest_cmp expect-pre-order-output actual-pre-order-output\n@@ -78,7 +78,7 @@ 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+\ttest-dir-iterator --post-order ./dir >actual-post-order-output &&\n \trm -rf dir &&\n \n \ttest_cmp expect-post-order-output actual-post-order-output\n@@ -100,7 +100,7 @@ test_expect_success 'dir-iterator should list files properly on pre-order + post\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+\ttest-dir-iterator --pre-order --post-order --list-root-dir ./dir >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-- \n2.11.0\n\n"}]}