{"thread":{"id":"45723","subject":"[PATCH v9 0/5] [GSoC] remove_subtree(): reimplement using iterators","startedAt":"2017-04-17T20:51:51Z","lastAt":"2017-04-18T18:45:34Z","messageCount":13,"participants":["Daniel Ferreira","Junio C Hamano","Stefan Beller"],"isPatch":true,"patchVersion":9,"patchTotal":5},"messages":[{"id":"317022","messageId":"1492462296-4990-1-git-send-email-bnmvco@gmail.com","threadId":"45723","inReplyTo":null,"subject":"[PATCH v9 0/5] [GSoC] remove_subtree(): reimplement using iterators","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-17T20:51:31Z","receivedAt":"2017-04-17T20:51:51Z","isPatch":true,"sender":{"key":"bnmvco@gmail.com","avatar":"https://avatars.githubusercontent.com/u/735397?v=4"},"body":"This is the ninth version of a patch series that implements the GSoC\nmicroproject of converting a recursive call to readdir() to use\ndir_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\nv8: https://public-inbox.org/git/a60b2ed6-2b99-b134-05af-7c8492a6949c@alum.mit.edu/T/#t\n\nTravis CI build: https://travis-ci.org/theiostream/git/builds/222919383\n\nI think this is the closest to a final version we've ever gotten. I\nfollowed all of Michael and Stefan's suggestions on top of v8, and with\nMichael's endorsement made dir_iterator_begin() return NULL and set\nerrno appropriately in case of an error.\n\nOn second thought, maybe the extra code complexity required from\ndir_iterator_begin()'s callers might be actually an advantage as\ndir_iterator grows to tackle more complex dir traversing challenges on\nGit. After all, we might want some special behavior depending on what\nthe given `path` is instead of always considering it valid and later\nbehaving as if it was an empty directory.\n\nThanks again for the reviews.\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                  | 252 +++++++++++++++++++++++++++++-----------\n dir-iterator.h                  |  35 ++++--\n entry.c                         |  42 +++----\n refs/files-backend.c            |  51 +++++---\n t/helper/.gitignore             |   1 +\n t/helper/test-dir-iterator.c    |  53 +++++++++\n t/t0065-dir-iterator.sh         | 113 ++++++++++++++++++\n t/t2000-checkout-cache-clash.sh |  11 ++\n 9 files changed, 435 insertions(+), 124 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":"317023","messageId":"1492462296-4990-2-git-send-email-bnmvco@gmail.com","threadId":"45723","inReplyTo":"1492462296-4990-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v9 1/5] dir_iterator: add tests for dir_iterator API","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-17T20:51:32Z","receivedAt":"2017-04-17T20:51:57Z","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 | 30 ++++++++++++++++++++++++\n t/t0065-dir-iterator.sh      | 55 ++++++++++++++++++++++++++++++++++++++++++++\n 4 files changed, 87 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 d595ea3..a5c1ac0 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..a7d1470\n--- /dev/null\n+++ b/t/helper/test-dir-iterator.c\n@@ -0,0 +1,30 @@\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+{\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":"317024","messageId":"1492462296-4990-3-git-send-email-bnmvco@gmail.com","threadId":"45723","inReplyTo":"1492462296-4990-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v9 2/5] remove_subtree(): test removing nested directories","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-17T20:51:33Z","receivedAt":"2017-04-17T20:51:59Z","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":"317025","messageId":"1492462296-4990-5-git-send-email-bnmvco@gmail.com","threadId":"45723","inReplyTo":"1492462296-4990-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v9 4/5] dir_iterator: refactor state machine model","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-17T20:51:35Z","receivedAt":"2017-04-17T20:52:06Z","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\nMake dir_iterator_begin() attempt to lstat() the path it receives, and\nreturn NULL and an appropriate errno if it fails or if the passed path\nwas not a directory.\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, as well as handle the case in which it\nfails to open the directory.\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>\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\n dir-iterator.c               | 223 ++++++++++++++++++++++++++++++-------------\n dir-iterator.h               |  35 +++++--\n refs/files-backend.c         |  51 ++++++----\n t/helper/test-dir-iterator.c |  31 +++++-\n t/t0065-dir-iterator.sh      |  66 ++++++++++++-\n 5 files changed, 305 insertions(+), 101 deletions(-)\n\ndiff --git a/dir-iterator.c b/dir-iterator.c\nindex 9e073a0..9394797 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,15 @@ 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/* The stat structure for the directory this level represents. */\n+\tstruct stat st;\n };\n \n /*\n@@ -48,15 +52,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, struct stat *st)\n {\n-\tlevel->dir_state = DIR_STATE_RECURSE;\n+\tstruct dir_iterator_level *level;\n+\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 = *st;\n }\n \n static int pop_dir_level(struct dir_iterator_int *iter)\n@@ -64,9 +76,14 @@ 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) {\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@@ -75,18 +92,48 @@ static int set_iterator_data(struct dir_iterator_int *iter, struct dir_iterator_\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/*\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\t */\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@@ -95,9 +142,26 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)\n \twhile (1) {\n \t\tstruct dir_iterator_level *level =\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\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\titer->levels_nr != 1 ||\n+\t\t\t\t(iter->flags & DIR_ITERATOR_LIST_ROOT_DIR))) {\n+\t\t\t\t/*\n+\t\t\t\t * This will only error if we fail to lstat() the\n+\t\t\t\t * root directory. In this case, we bail.\n+\t\t\t\t */\n+\t\t\t\tif (set_iterator_data(iter, level)) {\n+\t\t\t\t\tlevel->dir_state = DIR_STATE_EXHAUSTED;\n+\t\t\t\t\tcontinue;\n+\t\t\t\t}\n+\n+\t\t\t\treturn ITER_OK;\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 +171,37 @@ 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+\t\t\tlevel->dir_state = DIR_STATE_ITERATING;\n+\t\t} else if (level->dir_state == DIR_STATE_ITERATING) {\n+\t\t\tstruct dirent *de;\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\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 +212,41 @@ 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, &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\t/* We may not want the root directory to be iterated over */\n+\t\t\tif ((iter->flags & DIR_ITERATOR_POST_ORDER_TRAVERSAL) && (\n+\t\t\t\titer->levels_nr != 1 ||\n+\t\t\t\t(iter->flags & DIR_ITERATOR_LIST_ROOT_DIR))) {\n+\t\t\t\t/*\n+\t\t\t\t * In this state, set_iterator_data() should never return\n+\t\t\t\t * an error.\n+\t\t\t\t */\n+\t\t\t\tset_iterator_data(iter, level);\n+\t\t\t\treturn ITER_OK;\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,21 +272,41 @@ 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+\tstruct dir_iterator_int *iter;\n+\tstruct dir_iterator *dir_iterator;\n+\tstruct stat st;\n \n \tif (!path || !*path)\n \t\tdie(\"BUG: empty path passed to dir_iterator_begin()\");\n \n+\tif (lstat(path, &st) < 0) {\n+\t\tif (errno != ENOENT)\n+\t\t\twarning(\"error reading path '%s': %s\",\n+\t\t\t\t\tpath, strerror(errno));\n+\n+\t\treturn NULL;\n+\t}\n+\n+\tif (!S_ISDIR(st.st_mode)) {\n+\t\terrno = ENOTDIR;\n+\t\treturn NULL;\n+\t}\n+\n+\titer = xcalloc(1, sizeof(*iter));\n+\tdir_iterator = &iter->base;\n+\n+\titer->flags = flags;\n+\tdir_iterator->st = st;\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+\titer->levels_nr = 0;\n \n-\titer->levels_nr = 1;\n-\titer->levels[0].initialized = 0;\n+\tpush_dir_level(iter, &dir_iterator->st);\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..d376e1f 100644\n--- a/refs/files-backend.c\n+++ b/refs/files-backend.c\n@@ -3284,29 +3284,42 @@ static int files_reflog_iterator_advance(struct ref_iterator *ref_iterator)\n \tstruct dir_iterator *diter = iter->dir_iterator;\n \tint ok;\n \n-\twhile ((ok = dir_iterator_advance(diter)) == ITER_OK) {\n-\t\tint flags;\n-\n-\t\tif (!S_ISREG(diter->st.st_mode))\n-\t\t\tcontinue;\n-\t\tif (diter->basename[0] == '.')\n-\t\t\tcontinue;\n-\t\tif (ends_with(diter->basename, \".lock\"))\n-\t\t\tcontinue;\n+\tif (!iter->dir_iterator) {\n+\t\t/*\n+\t\t * If our dir_iterator is NULL at this stage, it means we failed\n+\t\t * to open the given path at dir_iterator_begin(), most likely due\n+\t\t * to it not existing.\n+\t\t *\n+\t\t * In this case, we pretend it was an empty directory and just\n+\t\t * iterate through nothing.\n+\t\t */\n+\t\tok = ITER_DONE;\n+\t} else {\n+\t\twhile ((ok = dir_iterator_advance(diter)) == ITER_OK) {\n+\t\t\tint flags;\n+\n+\t\t\tif (!S_ISREG(diter->st.st_mode))\n+\t\t\t\tcontinue;\n+\t\t\tif (diter->basename[0] == '.')\n+\t\t\t\tcontinue;\n+\t\t\tif (ends_with(diter->basename, \".lock\"))\n+\t\t\t\tcontinue;\n+\n+\t\t\tif (read_ref_full(diter->relative_path, 0,\n+\t\t\t\t\t  iter->oid.hash, &flags)) {\n+\t\t\t\terror(\"bad ref for %s\", diter->path.buf);\n+\t\t\t\tcontinue;\n+\t\t\t}\n \n-\t\tif (read_ref_full(diter->relative_path, 0,\n-\t\t\t\t  iter->oid.hash, &flags)) {\n-\t\t\terror(\"bad ref for %s\", diter->path.buf);\n-\t\t\tcontinue;\n+\t\t\titer->base.refname = diter->relative_path;\n+\t\t\titer->base.oid = &iter->oid;\n+\t\t\titer->base.flags = flags;\n+\t\t\treturn ITER_OK;\n \t\t}\n \n-\t\titer->base.refname = diter->relative_path;\n-\t\titer->base.oid = &iter->oid;\n-\t\titer->base.flags = flags;\n-\t\treturn ITER_OK;\n+\t\titer->dir_iterator = NULL;\n \t}\n \n-\titer->dir_iterator = NULL;\n \tif (ref_iterator_abort(ref_iterator) == ITER_ERROR)\n \t\tok = ITER_ERROR;\n \treturn ok;\n@@ -3346,7 +3359,7 @@ static struct ref_iterator *files_reflog_iterator_begin(struct ref_store *ref_st\n \tfiles_downcast(ref_store, 0, \"reflog_iterator_begin\");\n \n \tbase_ref_iterator_init(ref_iterator, &files_reflog_iterator_vtable);\n-\titer->dir_iterator = dir_iterator_begin(git_path(\"logs\"));\n+\titer->dir_iterator = dir_iterator_begin(git_path(\"logs\"), 0);\n \treturn ref_iterator;\n }\n \ndiff --git a/t/helper/test-dir-iterator.c b/t/helper/test-dir-iterator.c\nindex a7d1470..3b4948b 100644\n--- a/t/helper/test-dir-iterator.c\n+++ b/t/helper/test-dir-iterator.c\n@@ -5,15 +5,38 @@\n \n int cmd_main(int argc, const char **argv)\n {\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\tdie(\"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+\tif (diter == NULL) {\n+\t\tprintf(\"begin failed: %d\\n\", errno);\n+\t\treturn 0;\n+\t}\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..157593e 100755\n--- a/t/t0065-dir-iterator.sh\n+++ b/t/t0065-dir-iterator.sh\n@@ -15,7 +15,9 @@ test_expect_success 'setup' '\n \t>dir/d/e/d/a &&\n \n \tmkdir -p dir2/a/b/c/ &&\n-\t>dir2/a/b/c/d\n+\t>dir2/a/b/c/d &&\n+\n+\t>file\n '\n \n cat >expect-sorted-output <<-\\EOF &&\n@@ -33,12 +35,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 +55,59 @@ 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+cat >expect-non-existing-dir-output <<-\\EOF &&\n+begin failed: 2\n+EOF\n+\n+test_expect_success 'dir-iterator should return ENOENT upon opening non-existing directory' '\n+\ttest-dir-iterator ./dir3 >actual-non-existing-dir-output &&\n+\ttest_cmp expect-non-existing-dir-output actual-non-existing-dir-output\n+'\n+\n+cat >expect-not-a-directory-output <<-\\EOF &&\n+begin failed: 20\n+EOF\n+\n+test_expect_success 'dir-iterator should return ENOTDIR upon opening non-directory path' '\n+\ttest-dir-iterator ./file >actual-not-a-directory-output &&\n+\ttest_cmp expect-not-a-directory-output actual-not-a-directory-output\n+'\n+\n test_done\n-- \n2.7.4 (Apple Git-66)\n\n"},{"id":"317026","messageId":"1492462296-4990-4-git-send-email-bnmvco@gmail.com","threadId":"45723","inReplyTo":"1492462296-4990-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v9 3/5] dir_iterator: add helpers to dir_iterator_advance","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-17T20:51:34Z","receivedAt":"2017-04-17T20:52:21Z","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":"317027","messageId":"1492462296-4990-6-git-send-email-bnmvco@gmail.com","threadId":"45723","inReplyTo":"1492462296-4990-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v9 5/5] remove_subtree(): reimplement using iterators","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-17T20:51:36Z","receivedAt":"2017-04-17T20:52:22Z","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 | 42 ++++++++++++++++--------------------------\n 1 file changed, 16 insertions(+), 26 deletions(-)\n\ndiff --git a/entry.c b/entry.c\nindex d2b512d..a939432 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,21 @@ 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+\tif (!diter) {\n+\t\tdie_errno(\"cannot remove path '%s'\", path);\n+\t}\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 +302,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":"317075","messageId":"xmqqmvbefjar.fsf@gitster.mtv.corp.google.com","threadId":"45723","inReplyTo":"1492462296-4990-1-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v9 0/5] [GSoC] remove_subtree(): reimplement using iterators","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-04-18T04:09:48Z","receivedAt":"2017-04-18T04:10:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Daniel Ferreira <bnmvco@gmail.com> writes:\n\n> I think this is the closest to a final version we've ever gotten. I\n> followed all of Michael and Stefan's suggestions on top of v8, and with\n> Michael's endorsement made dir_iterator_begin() return NULL and set\n> errno appropriately in case of an error.\n>\n> On second thought, maybe the extra code complexity required from\n> dir_iterator_begin()'s callers might be actually an advantage as\n> dir_iterator grows to tackle more complex dir traversing challenges on\n> Git. After all, we might want some special behavior depending on what\n> the given `path` is instead of always considering it valid and later\n> behaving as if it was an empty directory.\n>\n> Thanks again for the reviews.\n\nI had a bit of trouble with phrasing here and there, but other than\nthat the series was a pleasant read overall.\n\nWill queue, anticipating \"Yeah, this is good as the final version\"\ncomments from reviewers.\n\nThanks.\n"},{"id":"317076","messageId":"xmqqinm2fj70.fsf@gitster.mtv.corp.google.com","threadId":"45723","inReplyTo":"1492462296-4990-2-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v9 1/5] dir_iterator: add tests for dir_iterator API","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-04-18T04:12:03Z","receivedAt":"2017-04-18T04:12:10Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Daniel Ferreira <bnmvco@gmail.com> writes:\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\nOK, if you can get multiple entries from a single directory, the\norder of these entries are not known because they come in readdir()\norder, and you'd need to sort the output to see if you got the same\nthing.  Sort of makes sense.\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\nAnd this example has only one item per each recursion level, so the\norder of output is predictable.  Again, makes sense.\n"},{"id":"317077","messageId":"xmqq8tmyfio6.fsf@gitster.mtv.corp.google.com","threadId":"45723","inReplyTo":"1492462296-4990-4-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v9 3/5] dir_iterator: add helpers to dir_iterator_advance","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-04-18T04:23:21Z","receivedAt":"2017-04-18T04:23:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Daniel Ferreira <bnmvco@gmail.com> writes:\n\n> Create helpers to dir_iterator_advance(). Make dir_iterator_advance()'s\n> code more legible and allow some behavior to be reusable.\n>\n> Signed-off-by: Daniel Ferreira <bnmvco@gmail.com>\n> ---\n\nThis is the kind of change we typically call \"refactoring\" ---\nfactoring out reusable helpers out of existing code, without\nchanging the behaviour of the code at all.\n\n> +static int set_iterator_data(struct dir_iterator_int *iter, struct dir_iterator_level *level)\n> +{\n\nIf you are going to fold line in a patch that immediately follows\nthis one, do so from the get-go here.\n\nI am not happy with the name of the function in that \"set data\" does\nnot convey as much information as it spends words.  \n\nConceptually, this is called once per each new directory entry\nreaddir() returns, and the most important \"iterator data\" that is\nset to iter structure per loop is to update iter->base.path with\nde->d_name; everything else is secondary and derived data from that.\nAnd from that point of view, I have trouble with this function not\ngetting \"de\" passed to it, but the most important setting is instead\ndone by its caller.\n\nIf the function were called \"adjust_iterator_data()\", I wouldn't\nfind this function so troubling, I guess; after the caller sets the\niter.base.path, all the secondary data that can be derived from it\nthat are used by the caller of \"advance\" are set by this function.\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"},{"id":"317078","messageId":"xmqq4lxmfi4b.fsf@gitster.mtv.corp.google.com","threadId":"45723","inReplyTo":"1492462296-4990-5-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v9 4/5] dir_iterator: refactor state machine model","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-04-18T04:35:16Z","receivedAt":"2017-04-18T04:35:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Daniel Ferreira <bnmvco@gmail.com> writes:\n\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\nI called 3/5 a \"refactoring\"; on the other hand, I wouldn't call\nthis refactoring--it is a major rewrite and/or enhancement.\n\nDrop \"convoluted...loops and variables\"; instead spend the same\nnumber of bits to explain how updated code is easier to follow.\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\nI had trouble understanding what you wanted to say with \"iterate\nover the root\" because the phrase sounded, at least to me, to mean\n\"opendir the root directory and repeatedly issue readdir() calls,\nreturning each entry returned by them\", and making that optional did\nnot make any sense to me.  I had to cheat by looking at the test\nscript to realize that you meant that the root directory that the\niterator is told to iterate over itself is also included in the\nresult, as opposed to the usual expectation that iterator would just\niterate over the contents of that directory recursively.  Perhaps\n\n    Add an option for the API to also include the initial directory\n    in the result.\n\nor something like that?\n\nBy the way, some other topic already took t0065, so I moved your\nt0065 over to t0066 while queuing.\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\nThese \"->\" somehow makes it very hard to read; are these meant to be\nbullets in a 5-item bulleted list, or do they mean more than that\n(e.g. as an arrow, you are trying to say from state PUSHED there is\na transition to PRE_ITERATION, etc.)?\n\nPRE_ITERATION says \"*NOT* initialized\"; has the directory been\nalready initialized in PUSHED state?  Instead of saying \"*NOT*\", it\nmay make it clearer if you say when it is initialized instead.\n"},{"id":"317079","messageId":"xmqqzifee3fo.fsf@gitster.mtv.corp.google.com","threadId":"45723","inReplyTo":"1492462296-4990-2-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v9 1/5] dir_iterator: add tests for dir_iterator API","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-04-18T04:37:47Z","receivedAt":"2017-04-18T04:37:57Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Daniel Ferreira <bnmvco@gmail.com> writes:\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\nModern tests create these test vectors inside test_expect_success\nblock, like so:\n\ntest_expect_success 'dir-iterator should iterate through all files' '\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\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"},{"id":"317083","messageId":"xmqqinm2e1sq.fsf@gitster.mtv.corp.google.com","threadId":"45723","inReplyTo":"1492462296-4990-5-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v9 4/5] dir_iterator: refactor state machine model","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-04-18T05:13:09Z","receivedAt":"2017-04-18T05:13:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Daniel Ferreira <bnmvco@gmail.com> writes:\n\n> ...\n> Signed-off-by: Daniel Ferreira <bnmvco@gmail.com>\n> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n\nI had an impression that you took Michael's code snippet and wrote\nthis patch, and if that is the case, the flow of the patch is from\nMichael to you to me, so these lines are out of order.\n\nDescribing which part of this patch owes Michael's contribution in\nthe log message would also not hurt.\n"},{"id":"317128","messageId":"CAGZ79kaBRS0SFAvrV4mN7-mVk+8QmPKPJMD55zPQ+A14ZzYFYA@mail.gmail.com","threadId":"45723","inReplyTo":"xmqqmvbefjar.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v9 0/5] [GSoC] remove_subtree(): reimplement using iterators","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-04-18T18:45:26Z","receivedAt":"2017-04-18T18:45:34Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Mon, Apr 17, 2017 at 9:09 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> Daniel Ferreira <bnmvco@gmail.com> writes:\n>\n>> I think this is the closest to a final version we've ever gotten. I\n>> followed all of Michael and Stefan's suggestions on top of v8, and with\n>> Michael's endorsement made dir_iterator_begin() return NULL and set\n>> errno appropriately in case of an error.\n>>\n>> On second thought, maybe the extra code complexity required from\n>> dir_iterator_begin()'s callers might be actually an advantage as\n>> dir_iterator grows to tackle more complex dir traversing challenges on\n>> Git. After all, we might want some special behavior depending on what\n>> the given `path` is instead of always considering it valid and later\n>> behaving as if it was an empty directory.\n>>\n>> Thanks again for the reviews.\n>\n> I had a bit of trouble with phrasing here and there, but other than\n> that the series was a pleasant read overall.\n>\n> Will queue, anticipating \"Yeah, this is good as the final version\"\n> comments from reviewers.\n\nyeah, it is.\n\nThanks,\nStefan\n"}]}