{"thread":{"id":"45613","subject":"[PATCH v8 0/5] [GSoC] remove_subtree(): reimplement using iterators","startedAt":"2017-04-06T01:39:43Z","lastAt":"2017-04-17T06:53:03Z","messageCount":11,"participants":["Daniel Ferreira","Daniel Ferreira (theiostream)","Stefan Beller","Michael Haggerty"],"isPatch":true,"patchVersion":8,"patchTotal":5},"messages":[{"id":"316248","messageId":"1491442767-54068-1-git-send-email-bnmvco@gmail.com","threadId":"45613","inReplyTo":null,"subject":"[PATCH v8 0/5] [GSoC] remove_subtree(): reimplement using iterators","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-06T01:39:22Z","receivedAt":"2017-04-06T01:39:43Z","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\nv7: https://public-inbox.org/git/1491163388-41255-1-git-send-email-bnmvco@gmail.com/T/#t\n\nTravis CI build: https://travis-ci.org/theiostream/git/jobs/219111182\n\nIn this version, I applied pretty much all suggestions Michael and Stefan had\nfor the patch.\n\nMichael, regarding the patch you sent for parsing the arguments on the\ntest-dir-iterator helper, I did not squash because it'd generate too many\nmerge conflicts. I just preferred add your code manually. Let me know how I\ncan properly credit you for it.\n\nThe only \"controversial\" part of this code is how I ended up caching the result\nof lstat() on the dir_iterator_level struct. Having to handle the case of the\nroot directory ended up making set_iterator_data() way more complicated (having\nto handle the case of level->stat not being set by push_dir_level()), as well\nas required the introduction of st_is_set member in the level struct. This issue\nwould be solved if we could lstat() the root dir on dir_iterator_begin() and\npossibly return an error there. Regardless, I appreciate other suggestions to\nmake this less complex.\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                  | 247 +++++++++++++++++++++++++++++-----------\n dir-iterator.h                  |  35 ++++--\n entry.c                         |  39 +++----\n refs/files-backend.c            |   2 +-\n t/helper/.gitignore             |   1 +\n t/helper/test-dir-iterator.c    |  48 ++++++++\n t/t0065-dir-iterator.sh         |  93 +++++++++++++++\n t/t2000-checkout-cache-clash.sh |  11 ++\n 9 files changed, 373 insertions(+), 104 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":"316249","messageId":"1491442767-54068-2-git-send-email-bnmvco@gmail.com","threadId":"45613","inReplyTo":"1491442767-54068-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v8 1/5] dir_iterator: add tests for dir_iterator API","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-06T01:39:23Z","receivedAt":"2017-04-06T01:39:44Z","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 | 29 +++++++++++++++++++++++\n t/t0065-dir-iterator.sh      | 55 ++++++++++++++++++++++++++++++++++++++++++++\n 4 files changed, 86 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..0394a13\n--- /dev/null\n+++ b/t/helper/test-dir-iterator.c\n@@ -0,0 +1,29 @@\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\tdie(\"BUG: test-dir-iterator needs one argument\");\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 if (S_ISREG(diter->st.st_mode))\n+\t\t\tprintf(\"[f] \");\n+\t\telse\n+\t\t\tprintf(\"[?] \");\n+\n+\t\tprintf(\"(%s) [%s] %s\\n\", diter->relative_path, diter->basename, 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..b6d76dd\n--- /dev/null\n+++ b/t/t0065-dir-iterator.sh\n@@ -0,0 +1,55 @@\n+#!/bin/sh\n+\n+test_description='Test directory iteration.'\n+\n+. ./test-lib.sh\n+\n+test_expect_success 'setup' '\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+\tmkdir -p dir2/a/b/c/ &&\n+\t>dir2/a/b/c/d\n+'\n+\n+cat >expect-sorted-output <<-\\EOF &&\n+[d] (a) [a] ./dir/a\n+[d] (a/b) [b] ./dir/a/b\n+[d] (a/b/c) [c] ./dir/a/b/c\n+[d] (d) [d] ./dir/d\n+[d] (d/e) [e] ./dir/d/e\n+[d] (d/e/d) [d] ./dir/d/e/d\n+[f] (a/b/c/d) [d] ./dir/a/b/c/d\n+[f] (a/e) [e] ./dir/a/e\n+[f] (b) [b] ./dir/b\n+[f] (c) [c] ./dir/c\n+[f] (d/e/d/a) [a] ./dir/d/e/d/a\n+EOF\n+\n+test_expect_success 'dir-iterator should iterate through all files' '\n+\ttest-dir-iterator ./dir >out &&\n+\tsort <out >./actual-pre-order-sorted-output &&\n+\n+\ttest_cmp expect-sorted-output actual-pre-order-sorted-output\n+'\n+\n+cat >expect-pre-order-output <<-\\EOF &&\n+[d] (a) [a] ./dir2/a\n+[d] (a/b) [b] ./dir2/a/b\n+[d] (a/b/c) [c] ./dir2/a/b/c\n+[f] (a/b/c/d) [d] ./dir2/a/b/c/d\n+EOF\n+\n+test_expect_success 'dir-iterator should list files in the correct order' '\n+\ttest-dir-iterator ./dir2 >actual-pre-order-output &&\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":"316250","messageId":"1491442767-54068-3-git-send-email-bnmvco@gmail.com","threadId":"45613","inReplyTo":"1491442767-54068-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v8 2/5] remove_subtree(): test removing nested directories","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-06T01:39:24Z","receivedAt":"2017-04-06T01:39:53Z","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":"316251","messageId":"1491442767-54068-5-git-send-email-bnmvco@gmail.com","threadId":"45613","inReplyTo":"1491442767-54068-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v8 4/5] dir_iterator: refactor state machine model","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-06T01:39:26Z","receivedAt":"2017-04-06T01:39:55Z","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               | 216 ++++++++++++++++++++++++++++++-------------\n dir-iterator.h               |  35 +++++--\n refs/files-backend.c         |   2 +-\n t/helper/test-dir-iterator.c |  27 +++++-\n t/t0065-dir-iterator.sh      |  44 ++++++++-\n 5 files changed, 245 insertions(+), 79 deletions(-)\n\ndiff --git a/dir-iterator.c b/dir-iterator.c\nindex 9e073a0..4c919d1 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,9 +18,20 @@ 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+\t/*\n+\t * The stat structure for the directory this level represents.\n+\t * It comes with a st_is_set flag which indicates whether it is,\n+\t * in fact, set.\n+\t */\n+\tunsigned st_is_set : 1;\n+\tstruct stat st;\n };\n \n /*\n@@ -48,15 +57,23 @@ 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 void push_dir_level(struct dir_iterator_int *iter, struct dir_iterator_level *level)\n+static void push_dir_level(struct dir_iterator_int *iter,\n+\t\tstruct dir_iterator_level *level, struct stat *st)\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+\tlevel->st_is_set = 1;\n+\tlevel->st = *st;\n }\n \n static int pop_dir_level(struct dir_iterator_int *iter)\n@@ -64,29 +81,73 @@ static int pop_dir_level(struct dir_iterator_int *iter)\n \treturn --iter->levels_nr;\n }\n \n-static int set_iterator_data(struct dir_iterator_int *iter, struct dir_iterator_level *level)\n+static int set_iterator_data(struct dir_iterator_int *iter,\n+\t\tstruct dir_iterator_level *level)\n {\n-\tif (lstat(iter->base.path.buf, &iter->base.st) < 0) {\n+\tchar *last_path_component;\n+\n+\tif (level->dir_state != DIR_STATE_ITERATING && level->st_is_set) {\n+\t\titer->base.st = level->st;\n+\t} else if (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\telse if (!level->st_is_set) {\n+\t\t\t/*\n+\t\t\t * When we are iterating over the root directory, we\n+\t\t\t * are forced to initialize the level stat here, since\n+\t\t\t * we cannot lstat() on dir_iterator_begin() before pushing\n+\t\t\t * the root level.\n+\t\t\t */\n+\t\t\tlevel->st = iter->base.st;\n+\t\t\tlevel->st_is_set = 1;\n+\t\t}\n+\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 * 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-\titer->base.basename =\n-\t\titer->base.path.buf + level->prefix_len;\n-\tlevel->dir_state = DIR_STATE_ITER;\n+\tif (level->dir_state != DIR_STATE_ITERATING &&\n+\t\titer->levels_nr == 1) {\n+\t\titer->base.relative_path = \".\";\n+\n+\t\t/* If we have a path like './dir', we'll get everything\n+\t\t * after the last slash a basename. If we don't find a\n+\t\t * slash (e.g. 'dir'), we return the whole path. */\n+\t\tlast_path_component = strrchr(iter->base.path.buf, '/');\n+\t\titer->base.basename = last_path_component ?\n+\t\t\tlast_path_component + 1 : iter->base.path.buf;\n+\t} else {\n+\t\titer->base.relative_path =\n+\t\t\titer->base.path.buf + iter->levels[0].prefix_len;\n+\n+\t\tif (S_ISDIR(iter->base.st.st_mode))\n+\t\t\titer->base.basename =\n+\t\t\t\titer->base.path.buf + iter->levels[iter->levels_nr - 2].prefix_len;\n+\t\telse\n+\t\t\titer->base.basename =\n+\t\t\t\titer->base.path.buf + level->prefix_len;\n+\t}\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 +158,26 @@ 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\t/*\n+\t\t\t\t\t * This will only error if we fail to lstat() the\n+\t\t\t\t\t * root directory. In this case, we bail.\n+\t\t\t\t\t */\n+\t\t\t\t\tif (set_iterator_data(iter, level)) {\n+\t\t\t\t\t\tlevel->dir_state = DIR_STATE_EXHAUSTED;\n+\t\t\t\t\t\tcontinue;\n+\t\t\t\t\t}\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 +187,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 +226,42 @@ 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, &iter->base.st);\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\t/*\n+\t\t\t\t\t * In this state, set_iterator_data() should never return\n+\t\t\t\t\t * an error.\n+\t\t\t\t\t */\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 +287,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 +295,17 @@ 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+\titer->levels[0].st_is_set = 0;\n \n \treturn dir_iterator;\n }\ndiff --git a/dir-iterator.h b/dir-iterator.h\nindex 27739e6..4d8ab75 100644\n--- a/dir-iterator.h\n+++ b/dir-iterator.h\n@@ -5,19 +5,17 @@\n  * Iterate over a directory tree.\n  *\n  * Iterate over a directory tree, recursively, including paths of all\n- * types and hidden paths. Skip \".\" and \"..\" entries and don't follow\n- * symlinks except for the original path.\n+ * types and hidden paths. Skip \".\" and \"..\" entries.\n  *\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 +36,26 @@\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 if either\n+ * DIR_ITERATOR_PRE_ORDER_TRAVERSAL or DIR_ITERATOR_POST_ORDER_TRAVERSAL\n+ * is set.\n+ *\n+ * All flags can be used in any combination.\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 +75,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 0394a13..9ac3fa7 100644\n--- a/t/helper/test-dir-iterator.c\n+++ b/t/helper/test-dir-iterator.c\n@@ -4,15 +4,34 @@\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+\n \tstruct strbuf path = STRBUF_INIT;\n \tstruct dir_iterator *diter;\n \n-\tif (argc < 2)\n-\t\tdie(\"BUG: test-dir-iterator needs one argument\");\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\telse if (!strcmp(*myargv, \"--post-order\"))\n+\t\t\tflag |= DIR_ITERATOR_POST_ORDER_TRAVERSAL;\n+\t\telse if (!strcmp(*myargv, \"--list-root-dir\"))\n+\t\t\tflag |= DIR_ITERATOR_LIST_ROOT_DIR;\n+\t\telse if (!strcmp(*myargv, \"--\")) {\n+\t\t\tmyargc--;\n+\t\t\tmyargv++;\n+\t\t\tbreak;\n+\t\t} else\n+\t\t   die(\"Unrecognized option: %s\", *myargv);\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+\tstrbuf_addstr(&path, *myargv);\n \n-\tditer = dir_iterator_begin(path.buf);\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 b6d76dd..458c57e 100755\n--- a/t/t0065-dir-iterator.sh\n+++ b/t/t0065-dir-iterator.sh\n@@ -33,12 +33,19 @@ cat >expect-sorted-output <<-\\EOF &&\n EOF\n \n test_expect_success 'dir-iterator should iterate through all files' '\n-\ttest-dir-iterator ./dir >out &&\n+\ttest-dir-iterator --pre-order ./dir >out &&\n \tsort <out >./actual-pre-order-sorted-output &&\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+\ttest-dir-iterator --post-order ./dir >out &&\n+\tsort <out >actual-post-order-sorted-output &&\n+\n+\ttest_cmp expect-sorted-output actual-post-order-sorted-output\n+'\n+\n cat >expect-pre-order-output <<-\\EOF &&\n [d] (a) [a] ./dir2/a\n [d] (a/b) [b] ./dir2/a/b\n@@ -46,10 +53,41 @@ cat >expect-pre-order-output <<-\\EOF &&\n [f] (a/b/c/d) [d] ./dir2/a/b/c/d\n EOF\n \n-test_expect_success 'dir-iterator should list files in the correct order' '\n-\ttest-dir-iterator ./dir2 >actual-pre-order-output &&\n+test_expect_success 'dir-iterator should list files properly on pre-order mode' '\n+\ttest-dir-iterator --pre-order ./dir2 >actual-pre-order-output &&\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) [d] ./dir2/a/b/c/d\n+[d] (a/b/c) [c] ./dir2/a/b/c\n+[d] (a/b) [b] ./dir2/a/b\n+[d] (a) [a] ./dir2/a\n+EOF\n+\n+test_expect_success 'dir-iterator should list files properly on post-order mode' '\n+\ttest-dir-iterator --post-order ./dir2 >actual-post-order-output &&\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] (.) [dir2] ./dir2\n+[d] (a) [a] ./dir2/a\n+[d] (a/b) [b] ./dir2/a/b\n+[d] (a/b/c) [c] ./dir2/a/b/c\n+[f] (a/b/c/d) [d] ./dir2/a/b/c/d\n+[d] (a/b/c) [c] ./dir2/a/b/c\n+[d] (a/b) [b] ./dir2/a/b\n+[d] (a) [a] ./dir2/a\n+[d] (.) [dir2] ./dir2\n+EOF\n+\n+test_expect_success 'dir-iterator should list files properly on pre-order + post-order + root-dir mode' '\n+\ttest-dir-iterator --pre-order --post-order --list-root-dir ./dir2 >actual-pre-order-post-order-root-dir-output &&\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":"316252","messageId":"1491442767-54068-4-git-send-email-bnmvco@gmail.com","threadId":"45613","inReplyTo":"1491442767-54068-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v8 3/5] dir_iterator: add helpers to dir_iterator_advance","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-06T01:39:25Z","receivedAt":"2017-04-06T01:39:57Z","isPatch":true,"sender":{"key":"bnmvco@gmail.com","avatar":"https://avatars.githubusercontent.com/u/735397?v=4"},"body":"Create helpers to dir_iterator_advance(). Make dir_iterator_advance()'s\ncode more legible and allow some behavior to be 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..9e073a0 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 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 int pop_dir_level(struct dir_iterator_int *iter)\n+{\n+\treturn --iter->levels_nr;\n+}\n+\n+static 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":"316253","messageId":"1491442767-54068-6-git-send-email-bnmvco@gmail.com","threadId":"45613","inReplyTo":"1491442767-54068-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v8 5/5] remove_subtree(): reimplement using iterators","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-06T01:39:27Z","receivedAt":"2017-04-06T01:40:00Z","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 | 39 +++++++++++++--------------------------\n 1 file changed, 13 insertions(+), 26 deletions(-)\n\ndiff --git a/entry.c b/entry.c\nindex d2b512d..d543ccf 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,18 @@ 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,\n+\t\tDIR_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 +299,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":"316709","messageId":"CAEA2_RJfcOc6FD41FNzU9LYs2xfzGZJxQyb2x8txuQqUE8RtNQ@mail.gmail.com","threadId":"45613","inReplyTo":"1491442767-54068-1-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v8 0/5] [GSoC] remove_subtree(): reimplement using iterators","fromName":"Daniel Ferreira (theiostream)","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-13T00:06:57Z","receivedAt":"2017-04-13T00:07:34Z","isPatch":true,"sender":{"key":"bnmvco@gmail.com","avatar":"https://avatars.githubusercontent.com/u/735397?v=4"},"body":"Hey there! I'm sorry for bothering you, but any chance you might have\noverlooked this patch for a review? (I'm just not familiar with how\nlong patches usually take to be reviewed, and since I always got an\nanswer within two days of sending it I wondered if you may have just\nnot noticed it.)\n\n-- Daniel.\n\nOn Wed, Apr 5, 2017 at 10:39 PM, Daniel Ferreira <bnmvco@gmail.com> wrote:\n> This is the seventh version of a patch series that implements the GSoC\n> microproject of converting a recursive call to readdir() to use dir_iterator.\n>\n> v1: https://public-inbox.org/git/CAGZ79kZwT-9mHTiOJ5CEjk2wDFkn6+NcogjX0=vjhsAh16ANYg@mail.gmail.com/T/#t\n> v2: https://public-inbox.org/git/CACsJy8Dxh-QPBBLfaFWPAWUsbA9GVXA7x+mXLjEvYKhk1zOpig@mail.gmail.com/T/#t\n> v3: https://public-inbox.org/git/CAGZ79kYtpmURSQWPumobA=e3JBFjKhWCdv_LPhKCd71ZRwMovA@mail.gmail.com/T/#t\n> v4: https://public-inbox.org/git/1490747533-89143-1-git-send-email-bnmvco@gmail.com/T/#e437a63e0c22c00c69b5d92977c9b438ed2b9fd3a\n> v5: https://public-inbox.org/git/1490844730-47634-1-git-send-email-bnmvco@gmail.com/T/#m2323f15e45de699f2e09364f40a62e17047cf453\n> v6: https://public-inbox.org/git/1491107726-21504-1-git-send-email-bnmvco@gmail.com/T/#t\n> v7: https://public-inbox.org/git/1491163388-41255-1-git-send-email-bnmvco@gmail.com/T/#t\n>\n> Travis CI build: https://travis-ci.org/theiostream/git/jobs/219111182\n>\n> In this version, I applied pretty much all suggestions Michael and Stefan had\n> for the patch.\n>\n> Michael, regarding the patch you sent for parsing the arguments on the\n> test-dir-iterator helper, I did not squash because it'd generate too many\n> merge conflicts. I just preferred add your code manually. Let me know how I\n> can properly credit you for it.\n>\n> The only \"controversial\" part of this code is how I ended up caching the result\n> of lstat() on the dir_iterator_level struct. Having to handle the case of the\n> root directory ended up making set_iterator_data() way more complicated (having\n> to handle the case of level->stat not being set by push_dir_level()), as well\n> as required the introduction of st_is_set member in the level struct. This issue\n> would be solved if we could lstat() the root dir on dir_iterator_begin() and\n> possibly return an error there. Regardless, I appreciate other suggestions to\n> make this less complex.\n>\n> Daniel 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                  | 247 +++++++++++++++++++++++++++++-----------\n>  dir-iterator.h                  |  35 ++++--\n>  entry.c                         |  39 +++----\n>  refs/files-backend.c            |   2 +-\n>  t/helper/.gitignore             |   1 +\n>  t/helper/test-dir-iterator.c    |  48 ++++++++\n>  t/t0065-dir-iterator.sh         |  93 +++++++++++++++\n>  t/t2000-checkout-cache-clash.sh |  11 ++\n>  9 files changed, 373 insertions(+), 104 deletions(-)\n>  create mode 100644 t/helper/test-dir-iterator.c\n>  create mode 100755 t/t0065-dir-iterator.sh\n>\n> --\n> 2.7.4 (Apple Git-66)\n>\n"},{"id":"316710","messageId":"CAGZ79kaH0ihJ-zFX5zdK-av0Aqxi1ebCEqj5smb2Zu9pKRG8oA@mail.gmail.com","threadId":"45613","inReplyTo":"1491442767-54068-2-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v8 1/5] dir_iterator: add tests for dir_iterator API","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-04-13T00:42:57Z","receivedAt":"2017-04-13T00:43:08Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Wed, Apr 5, 2017 at 6:39 PM, Daniel Ferreira <bnmvco@gmail.com> wrote:\n\n> +int cmd_main(int argc, const char **argv) {\n\nStyle (minor nit, in case resend is needed):\n\nWe only put the { brace on the same line for statements\n(if, for, while, switch), not for function declarations.\n\nI tried to find a good rationale for it, this is the most sufficient I\ncould find\nhttps://www.kernel.org/doc/Documentation/process/coding-style.rst\n(section 3):\n\n    Heretic people all over the world have claimed that this inconsistency\n    is ...  well ...  inconsistent, but all right-thinking people know that\n    (a) K&R are **right** and (b) K&R are right.  Besides, functions are\n    special anyway (you can't nest them in C).\n"},{"id":"316711","messageId":"CAGZ79kbTjVSRgWc5su89pL5t_mSEubjT_cQ0Onu4EdcKVmyL7w@mail.gmail.com","threadId":"45613","inReplyTo":"CAEA2_RJfcOc6FD41FNzU9LYs2xfzGZJxQyb2x8txuQqUE8RtNQ@mail.gmail.com","subject":"Re: [PATCH v8 0/5] [GSoC] remove_subtree(): reimplement using iterators","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-04-13T00:50:24Z","receivedAt":"2017-04-13T00:50:30Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Wed, Apr 12, 2017 at 5:06 PM, Daniel Ferreira (theiostream)\n<bnmvco@gmail.com> wrote:\n> Hey there! I'm sorry for bothering you, but any chance you might have\n> overlooked this patch for a review?\n\nSort of. I read through them and found no issue back then, but did\nnot reply anticipating someone else would .\n\n>  (I'm just not familiar with how\n> long patches usually take to be reviewed, and since I always got an\n> answer within two days of sending it I wondered if you may have just\n> not noticed it.)\n\nI reviewed it again and found just a very minor nit, no need for a resend\nif that is the only nit.\n\nThanks,\nStefan\n"},{"id":"316988","messageId":"a60b2ed6-2b99-b134-05af-7c8492a6949c@alum.mit.edu","threadId":"45613","inReplyTo":"1491442767-54068-1-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v8 0/5] [GSoC] remove_subtree(): reimplement using iterators","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-04-17T06:29:14Z","receivedAt":"2017-04-17T06:29:29Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 04/06/2017 03:39 AM, Daniel Ferreira wrote:\n> This is the seventh version of a patch series that implements the GSoC\n> microproject of converting a recursive call to readdir() to use dir_iterator.\n> \n> v1: https://public-inbox.org/git/CAGZ79kZwT-9mHTiOJ5CEjk2wDFkn6+NcogjX0=vjhsAh16ANYg@mail.gmail.com/T/#t\n> v2: https://public-inbox.org/git/CACsJy8Dxh-QPBBLfaFWPAWUsbA9GVXA7x+mXLjEvYKhk1zOpig@mail.gmail.com/T/#t\n> v3: https://public-inbox.org/git/CAGZ79kYtpmURSQWPumobA=e3JBFjKhWCdv_LPhKCd71ZRwMovA@mail.gmail.com/T/#t\n> v4: https://public-inbox.org/git/1490747533-89143-1-git-send-email-bnmvco@gmail.com/T/#e437a63e0c22c00c69b5d92977c9b438ed2b9fd3a\n> v5: https://public-inbox.org/git/1490844730-47634-1-git-send-email-bnmvco@gmail.com/T/#m2323f15e45de699f2e09364f40a62e17047cf453\n> v6: https://public-inbox.org/git/1491107726-21504-1-git-send-email-bnmvco@gmail.com/T/#t\n> v7: https://public-inbox.org/git/1491163388-41255-1-git-send-email-bnmvco@gmail.com/T/#t\n> \n> Travis CI build: https://travis-ci.org/theiostream/git/jobs/219111182\n> \n> In this version, I applied pretty much all suggestions Michael and Stefan had\n> for the patch.\n> \n> Michael, regarding the patch you sent for parsing the arguments on the\n> test-dir-iterator helper, I did not squash because it'd generate too many\n> merge conflicts. I just preferred add your code manually. Let me know how I\n> can properly credit you for it.\n\nIt's a small enough bit of code that you don't have to credit me.\nHowever, technically you should add a\n\n    Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n\nline to your patch that includes my code, which you are allowed to do\nbecause I included that line in the email where I suggested the change [1].\n\n> The only \"controversial\" part of this code is how I ended up caching the result\n> of lstat() on the dir_iterator_level struct. Having to handle the case of the\n> root directory ended up making set_iterator_data() way more complicated (having\n> to handle the case of level->stat not being set by push_dir_level()), as well\n> as required the introduction of st_is_set member in the level struct. This issue\n> would be solved if we could lstat() the root dir on dir_iterator_begin() and\n> possibly return an error there. Regardless, I appreciate other suggestions to\n> make this less complex.\n\nI agree that this adds a lot of code complexity. But I think your\nsuggestion to move the initial `lstat()` call to `dir_iterator_begin()`\nis a good one. It could return NULL on error (being careful not to leak\nmemory of course). It should be careful to leave `errno` set\nappropriately, which would allow the caller to see why it failed (i.e.,\nbecause the directory didn't exist, or the path was not a directory, or\nwhatever). In that case, probably `dir_iterator_begin()` could call\n`push_dir_level()`, eliminating a bit of repeated code at the same time.\n\nThis would also fix an anomaly in the current code: currently, if the\ntop-level \"directory\" is not a directory, it is nevertheless reported\nback to the caller during `DIR_ITERATOR_PRE_ORDER_TRAVERSAL` and *again*\nduring `DIR_ITERATOR_POST_ORDER_TRAVERSAL`. Instead,\n`dir_iterator_begin()` would report an error and the caller would not be\nmisled.\n\n> Hey there! I'm sorry for bothering you, but any chance you might have\n> overlooked this patch for a review? (I'm just not familiar with how\n> long patches usually take to be reviewed, and since I always got an\n> answer within two days of sending it I wondered if you may have just\n> not noticed it.)\n\nIt's pretty common for response times to vary wildly in open source\n(Junio being a notable exception). People often work on open source in\ntheir spare time, and disappear and reappear without notice based on\nwhat else is going on in their lives. For this reason, it is really\nimportant to submit changes in small batches as early as possible\n(especially in GSoC) and continue working on the next batch while\nwaiting for review on earlier batches. If you find yourself with nothing\nelse to work on, maybe spend some time reviewing *other* people's\npatches, which is also a valuable contribution.\n\nThat being said, if you are waiting for a response from particular\nperson, after a wait it is OK to write them an email asking if they will\nhave time to get to it (realizing that the answer might be \"no\").\nProbably such an email should be to the person directly, and not CCed to\nthe mailing list.\n\nMichael\n\n[1]\nhttp://public-inbox.org/git/bfd5d9a07139dbc6eb1fd1dc82ffb38dbbefee1e.1491286711.git.mhagger@alum.mit.edu/\n\n"},{"id":"316989","messageId":"9b8dd7f4-89d7-1257-4187-bfe362009253@alum.mit.edu","threadId":"45613","inReplyTo":"1491442767-54068-5-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v8 4/5] dir_iterator: refactor state machine model","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-04-17T06:52:53Z","receivedAt":"2017-04-17T06:53:03Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 04/06/2017 03:39 AM, 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> \n> Signed-off-by: Daniel Ferreira <bnmvco@gmail.com>\n> ---\n>  dir-iterator.c               | 216 ++++++++++++++++++++++++++++++-------------\n>  dir-iterator.h               |  35 +++++--\n>  refs/files-backend.c         |   2 +-\n>  t/helper/test-dir-iterator.c |  27 +++++-\n>  t/t0065-dir-iterator.sh      |  44 ++++++++-\n>  5 files changed, 245 insertions(+), 79 deletions(-)\n> \n> diff --git a/dir-iterator.c b/dir-iterator.c\n> index 9e073a0..4c919d1 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,9 +18,20 @@ 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> +\t/*\n> +\t * The stat structure for the directory this level represents.\n> +\t * It comes with a st_is_set flag which indicates whether it is,\n> +\t * in fact, set.\n> +\t */\n> +\tunsigned st_is_set : 1;\n\nIn another email I just agreed with you that it would probably be\ncleaner to call `lstat()` on the top-level directory from\n`dir_iterator_begin()`. But if that weren't an option, rather than\nadding a new state variable `st_is_set`, it might be more natural to add\na new value, say `DIR_STATE_INITIALIZING`, to `dir_state`, and do the\nspecial case initialization in the main loop in `dir_iterator_advance()`\nrather than in `set_iterator_data()`.\n\n> +\tstruct stat st;\n>  };\n>  \n>  /*\n> @@ -48,15 +57,23 @@ 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 void push_dir_level(struct dir_iterator_int *iter, struct dir_iterator_level *level)\n> +static void push_dir_level(struct dir_iterator_int *iter,\n> +\t\tstruct dir_iterator_level *level, struct stat *st)\n\nThe `level` argument is no longer used.\n\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> +\tlevel->st_is_set = 1;\n> +\tlevel->st = *st;\n>  }\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 +158,26 @@ 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`de` is only used in one branch of the `if` statement. Its definition\ncould be moved there.\n\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\nThese two `if` statements can be combined into one:\n\n\t\t\t/* We may not want the root directory to be iterated over */\n\t\t\tif ((iter->flags & DIR_ITERATOR_PRE_ORDER_TRAVERSAL) &&\n\t\t\t    (iter->levels_nr != 1 ||\n\t\t\t     (iter->flags & DIR_ITERATOR_LIST_ROOT_DIR))) {\n\t\t\t\t/* ... */\n\n\n> +\t\t\t\t\t/*\n> +\t\t\t\t\t * This will only error if we fail to lstat() the\n> +\t\t\t\t\t * root directory. In this case, we bail.\n> +\t\t\t\t\t */\n> +\t\t\t\t\tif (set_iterator_data(iter, level)) {\n> +\t\t\t\t\t\tlevel->dir_state = DIR_STATE_EXHAUSTED;\n> +\t\t\t\t\t\tcontinue;\n> +\t\t\t\t\t}\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> [...]\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\nActually, this iterator *doesn't* care about directories. If you look up\nin `files_reflog_iterator_advance()`, only entries for which\n`S_ISREG(diter->st.st_mode)` are processed. So you can set the flag to\n0. (You still need to retain the `S_ISREG()` check, though, to exclude\nother types of files.)\n\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 0394a13..9ac3fa7 100644\n> --- a/t/helper/test-dir-iterator.c\n> +++ b/t/helper/test-dir-iterator.c\n> @@ -4,15 +4,34 @@\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> +\n>  \tstruct strbuf path = STRBUF_INIT;\n>  \tstruct dir_iterator *diter;\n>  \n> -\tif (argc < 2)\n> -\t\tdie(\"BUG: test-dir-iterator needs one argument\");\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\telse if (!strcmp(*myargv, \"--post-order\"))\n> +\t\t\tflag |= DIR_ITERATOR_POST_ORDER_TRAVERSAL;\n> +\t\telse if (!strcmp(*myargv, \"--list-root-dir\"))\n> +\t\t\tflag |= DIR_ITERATOR_LIST_ROOT_DIR;\n> +\t\telse if (!strcmp(*myargv, \"--\")) {\n> +\t\t\tmyargc--;\n> +\t\t\tmyargv++;\n> +\t\t\tbreak;\n> +\t\t} else\n> +\t\t   die(\"Unrecognized option: %s\", *myargv);\n\nThe indentation above is wrong.\n\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> +\tstrbuf_addstr(&path, *myargv);\n>  \n> -\tditer = dir_iterator_begin(path.buf);\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> [...]\n\nMichael\n\n"}]}