{"thread":{"id":"45532","subject":"[PATCH v4 0/5] [GSoC] remove_subtree(): reimplement using iterators","startedAt":"2017-03-29T00:34:48Z","lastAt":"2017-04-05T09:22:31Z","messageCount":19,"participants":["Daniel Ferreira","Michael Haggerty","Junio C Hamano","Duy Nguyen","Daniel Ferreira (theiostream)"],"isPatch":true,"patchVersion":4,"patchTotal":5},"messages":[{"id":"315637","messageId":"1490747533-89143-1-git-send-email-bnmvco@gmail.com","threadId":"45532","inReplyTo":null,"subject":"[PATCH v4 0/5] [GSoC] remove_subtree(): reimplement using iterators","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-03-29T00:32:08Z","receivedAt":"2017-03-29T00:34:48Z","isPatch":true,"sender":{"key":"bnmvco@gmail.com","avatar":"https://avatars.githubusercontent.com/u/735397?v=4"},"body":"Hi there,\n\nThis is the fourth version of the GSoC microproject of refactoring\nremove_subtree() from recursively using readdir() to use dir_iterator. Below\nare the threads for other versions:\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\n\nIn this version of the patch, I followed Michael's suggestion\nof splitting the commits responsible for adding the new feature to\ndir_iterator. His suggestion of using flags instead of an options\nstruct has also been adopted.\n\nThis version also contains a test that is finally able to test the\nfunction decently (not the one Stefan had suggested, which\ndid not result in a call to remove_subtree). I am just unsure about\nits location in t/. I'd appreciate suggestions to put it in a more\ndecent home.\n\nDaniel Ferreira (5):\n  dir_iterator: add helpers to dir_iterator_advance\n  dir_iterator: iterate over dir after its contents\n  remove_subtree(): reimplement using iterators\n  remove_subtree(): test removing nested directories\n  files_reflog_iterator: amend use of dir_iterator\n\n dir-iterator.c                  | 105 +++++++++++++++++++++++++++++++---------\n dir-iterator.h                  |  14 ++++--\n entry.c                         |  31 ++++--------\n refs/files-backend.c            |   2 +-\n t/t2000-checkout-cache-clash.sh |  11 +++++\n 5 files changed, 114 insertions(+), 49 deletions(-)\n\n--\n2.7.4 (Apple Git-66)\n\n"},{"id":"315638","messageId":"1490747533-89143-5-git-send-email-bnmvco@gmail.com","threadId":"45532","inReplyTo":"1490747533-89143-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v4 4/5] remove_subtree(): test removing nested directories","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-03-29T00:32:12Z","receivedAt":"2017-03-29T00:34:49Z","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":"315639","messageId":"1490747533-89143-6-git-send-email-bnmvco@gmail.com","threadId":"45532","inReplyTo":"1490747533-89143-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v4 5/5] files_reflog_iterator: amend use of dir_iterator","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-03-29T00:32:13Z","receivedAt":"2017-03-29T00:35:03Z","isPatch":true,"sender":{"key":"bnmvco@gmail.com","avatar":"https://avatars.githubusercontent.com/u/735397?v=4"},"body":"Amend a call to dir_iterator_begin() to pass the flags parameter\nintroduced in 3efb5c0 (\"dir_iterator: iterate over dir after its\ncontents\", 2017-28-03).\n\nSigned-off-by: Daniel Ferreira <bnmvco@gmail.com>\n---\n refs/files-backend.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/refs/files-backend.c b/refs/files-backend.c\nindex 50188e9..b4bba74 100644\n--- a/refs/files-backend.c\n+++ b/refs/files-backend.c\n@@ -3346,7 +3346,7 @@ static struct ref_iterator *files_reflog_iterator_begin(struct ref_store *ref_st\n \tfiles_downcast(ref_store, 0, \"reflog_iterator_begin\");\n\n \tbase_ref_iterator_init(ref_iterator, &files_reflog_iterator_vtable);\n-\titer->dir_iterator = dir_iterator_begin(git_path(\"logs\"));\n+\titer->dir_iterator = dir_iterator_begin(git_path(\"logs\"), 0);\n \treturn ref_iterator;\n }\n\n--\n2.7.4 (Apple Git-66)\n\n"},{"id":"315640","messageId":"1490747533-89143-2-git-send-email-bnmvco@gmail.com","threadId":"45532","inReplyTo":"1490747533-89143-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v4 1/5] dir_iterator: add helpers to dir_iterator_advance","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-03-29T00:32:09Z","receivedAt":"2017-03-29T00:35:20Z","isPatch":true,"sender":{"key":"bnmvco@gmail.com","avatar":"https://avatars.githubusercontent.com/u/735397?v=4"},"body":"Create inline helpers to dir_iterator_advance(). Make\ndir_iterator_advance()'s code more legible and allow some behavior to\nbe reusable.\n\nSigned-off-by: Daniel Ferreira <bnmvco@gmail.com>\n---\n dir-iterator.c | 65 +++++++++++++++++++++++++++++++++++++---------------------\n 1 file changed, 42 insertions(+), 23 deletions(-)\n\ndiff --git a/dir-iterator.c b/dir-iterator.c\nindex 34182a9..853c040 100644\n--- a/dir-iterator.c\n+++ b/dir-iterator.c\n@@ -50,6 +50,43 @@ struct dir_iterator_int {\n \tstruct dir_iterator_level *levels;\n };\n\n+static inline void push_dir_level(struct dir_iterator_int *iter, struct dir_iterator_level *level)\n+{\n+\tlevel->dir_state = DIR_STATE_RECURSE;\n+\tALLOC_GROW(iter->levels, iter->levels_nr + 1,\n+\t\t   iter->levels_alloc);\n+\tlevel = &iter->levels[iter->levels_nr++];\n+\tlevel->initialized = 0;\n+}\n+\n+static inline int pop_dir_level(struct dir_iterator_int *iter, struct dir_iterator_level *level)\n+{\n+\treturn --iter->levels_nr;\n+}\n+\n+static inline int set_iterator_data(struct dir_iterator_int *iter, struct dir_iterator_level *level)\n+{\n+\tif (lstat(iter->base.path.buf, &iter->base.st) < 0) {\n+\t\tif (errno != ENOENT)\n+\t\t\twarning(\"error reading path '%s': %s\",\n+\t\t\t\titer->base.path.buf,\n+\t\t\t\tstrerror(errno));\n+\t\treturn -1;\n+\t}\n+\n+\t/*\n+\t * We have to set these each time because\n+\t * the path strbuf might have been realloc()ed.\n+\t */\n+\titer->base.relative_path =\n+\t\titer->base.path.buf + iter->levels[0].prefix_len;\n+\titer->base.basename =\n+\t\titer->base.path.buf + level->prefix_len;\n+\tlevel->dir_state = DIR_STATE_ITER;\n+\n+\treturn 0;\n+}\n+\n int dir_iterator_advance(struct dir_iterator *dir_iterator)\n {\n \tstruct dir_iterator_int *iter =\n@@ -84,11 +121,7 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)\n \t\t\t\t * over; now prepare to iterate into\n \t\t\t\t * it.\n \t\t\t\t */\n-\t\t\t\tlevel->dir_state = DIR_STATE_RECURSE;\n-\t\t\t\tALLOC_GROW(iter->levels, iter->levels_nr + 1,\n-\t\t\t\t\t   iter->levels_alloc);\n-\t\t\t\tlevel = &iter->levels[iter->levels_nr++];\n-\t\t\t\tlevel->initialized = 0;\n+\t\t\t\tpush_dir_level(iter, level);\n \t\t\t\tcontinue;\n \t\t\t} else {\n \t\t\t\t/*\n@@ -104,7 +137,7 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)\n \t\t\t * This level is exhausted (or wasn't opened\n \t\t\t * successfully); pop up a level.\n \t\t\t */\n-\t\t\tif (--iter->levels_nr == 0)\n+\t\t\tif (pop_dir_level(iter, level) == 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, level) == 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":"315641","messageId":"1490747533-89143-4-git-send-email-bnmvco@gmail.com","threadId":"45532","inReplyTo":"1490747533-89143-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v4 3/5] remove_subtree(): reimplement using iterators","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-03-29T00:32:11Z","receivedAt":"2017-03-29T00:35:21Z","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 | 31 ++++++++++---------------------\n 1 file changed, 10 insertions(+), 21 deletions(-)\n\ndiff --git a/entry.c b/entry.c\nindex c6eea24..bbebd16 100644\n--- a/entry.c\n+++ b/entry.c\n@@ -2,6 +2,8 @@\n #include \"blob.h\"\n #include \"dir.h\"\n #include \"streaming.h\"\n+#include \"iterator.h\"\n+#include \"dir-iterator.h\"\n\n static void create_directories(const char *path, int path_len,\n \t\t\t       const struct checkout *state)\n@@ -46,29 +48,16 @@ static void create_directories(const char *path, int path_len,\n\n static void remove_subtree(struct strbuf *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+\tstruct dir_iterator *diter = dir_iterator_begin(path->buf, DIR_ITERATOR_DEPTH_FIRST);\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'\", path->buf);\n+\t\t} else if (unlink(diter->path.buf))\n \t\t\tdie_errno(\"cannot unlink '%s'\", path->buf);\n-\t\tstrbuf_setlen(path, origlen);\n \t}\n-\tclosedir(dir);\n+\n \tif (rmdir(path->buf))\n \t\tdie_errno(\"cannot rmdir '%s'\", path->buf);\n }\n--\n2.7.4 (Apple Git-66)\n\n"},{"id":"315642","messageId":"1490747533-89143-3-git-send-email-bnmvco@gmail.com","threadId":"45532","inReplyTo":"1490747533-89143-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v4 2/5] dir_iterator: iterate over dir after its contents","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-03-29T00:32:10Z","receivedAt":"2017-03-29T00:35:23Z","isPatch":true,"sender":{"key":"bnmvco@gmail.com","avatar":"https://avatars.githubusercontent.com/u/735397?v=4"},"body":"Create 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).\n\nAdd the \"flags\" parameter to dir_iterator_create, allowing for the\naforementioned \"depth-first\" iteration mode to be enabled. Currently,\nthe only acceptable flag is DIR_ITERATOR_DEPTH_FIRST.\n\nThis is useful for recursively removing a directory and calling rmdir()\non a directory only after all of its contents have been wiped.\n\nSigned-off-by: Daniel Ferreira <bnmvco@gmail.com>\n---\n dir-iterator.c | 46 ++++++++++++++++++++++++++++++++++++++++++----\n dir-iterator.h | 14 +++++++++++---\n 2 files changed, 53 insertions(+), 7 deletions(-)\n\ndiff --git a/dir-iterator.c b/dir-iterator.c\nindex 853c040..545d333 100644\n--- a/dir-iterator.c\n+++ b/dir-iterator.c\n@@ -48,6 +48,9 @@ struct dir_iterator_int {\n \t * that will be included in this iteration.\n \t */\n \tstruct dir_iterator_level *levels;\n+\n+\t/* Holds the flags passed to dir_iterator_begin(). */\n+\tunsigned flags;\n };\n\n static inline void push_dir_level(struct dir_iterator_int *iter, struct dir_iterator_level *level)\n@@ -114,12 +117,14 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)\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} else if (S_ISDIR(iter->base.st.st_mode) &&\n+\t\t!iter->flags & DIR_ITERATOR_DEPTH_FIRST) {\n \t\t\tif (level->dir_state == DIR_STATE_ITER) {\n \t\t\t\t/*\n \t\t\t\t * The directory was just iterated\n \t\t\t\t * over; now prepare to iterate into\n-\t\t\t\t * it.\n+\t\t\t\t * it (unless an option is set for us\n+\t\t\t\t * to do otherwise).\n \t\t\t\t */\n \t\t\t\tpush_dir_level(iter, level);\n \t\t\t\tcontinue;\n@@ -153,10 +158,27 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)\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/* This level is exhausted  */\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 (iter->flags & DIR_ITERATOR_DEPTH_FIRST) {\n+\t\t\t\t\t/* If we are handling dirpaths after their contents,\n+\t\t\t\t\t * we have to iterate over the directory now that we'll\n+\t\t\t\t\t * have finished iterating into it. */\n+\t\t\t\t\tlevel->dir = NULL;\n+\n+\t\t\t\t\tif (pop_dir_level(iter, level) == 0)\n+\t\t\t\t\t\treturn dir_iterator_abort(dir_iterator);\n+\n+\t\t\t\t\tlevel = &iter->levels[iter->levels_nr - 1];\n+\t\t\t\t\t/* Remove a trailing slash */\n+\t\t\t\t\tstrbuf_strip_suffix(&iter->base.path, \"/\");\n+\n+\t\t\t\t\tif (set_iterator_data(iter, level))\n+\t\t\t\t\t\tcontinue;\n+\n+\t\t\t\t\treturn ITER_OK;\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@@ -175,8 +197,22 @@ 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\t/*\n+\t\t\t * If we want to iterate dirs after files, we shall\n+\t\t\t * begin looking into them *before* we return the dir\n+\t\t\t * itself.\n+\t\t\t */\n+\t\t\tif (S_ISDIR(iter->base.st.st_mode) &&\n+\t\t\titer->flags & DIR_ITERATOR_DEPTH_FIRST) {\n+\t\t\t\tpush_dir_level(iter, level);\n+\t\t\t\tgoto continue_outer_loop;\n+\t\t\t}\n+\n \t\t\treturn ITER_OK;\n \t\t}\n+\n+continue_outer_loop:\n+\t\t;\n \t}\n }\n\n@@ -201,7 +237,7 @@ int dir_iterator_abort(struct dir_iterator *dir_iterator)\n \treturn ITER_DONE;\n }\n\n-struct dir_iterator *dir_iterator_begin(const char *path)\n+struct dir_iterator *dir_iterator_begin(const char *path, unsigned flags)\n {\n \tstruct dir_iterator_int *iter = xcalloc(1, sizeof(*iter));\n \tstruct dir_iterator *dir_iterator = &iter->base;\n@@ -209,6 +245,8 @@ 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\ndiff --git a/dir-iterator.h b/dir-iterator.h\nindex 27739e6..28ff3df 100644\n--- a/dir-iterator.h\n+++ b/dir-iterator.h\n@@ -38,6 +38,13 @@\n  * dir_iterator_advance() again.\n  */\n\n+/* Possible flags for dir_iterator_begin().\n+ *\n+ * DIR_ITERATOR_DEPTH_FIRST: ensures subdirectories and their contents\n+ * are iterated through before the containing directory.\n+ */\n+#define DIR_ITERATOR_DEPTH_FIRST (1 << 1)\n+\n struct dir_iterator {\n \t/* The current path: */\n \tstruct strbuf path;\n@@ -57,15 +64,16 @@ struct dir_iterator {\n };\n\n /*\n- * Start a directory iteration over path. Return a dir_iterator that\n- * holds the internal state of the iteration.\n+ * Start a directory iteration over path, with options specified in\n+ * 'flags'. Return a dir_iterator that holds the internal state of\n+ * the iteration.\n  *\n  * The iteration includes all paths under path, not including path\n  * itself and not including \".\" or \"..\" entries.\n  *\n  * path is the starting directory. An internal copy will be made.\n  */\n-struct dir_iterator *dir_iterator_begin(const char *path);\n+struct dir_iterator *dir_iterator_begin(const char *path, unsigned flags);\n\n /*\n  * Advance the iterator to the first or next item and return ITER_OK.\n--\n2.7.4 (Apple Git-66)\n\n"},{"id":"315649","messageId":"cdcbf8ce-6641-8a96-6805-b9ff6fa0f3e1@alum.mit.edu","threadId":"45532","inReplyTo":"1490747533-89143-2-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v4 1/5] dir_iterator: add helpers to dir_iterator_advance","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-03-29T04:32:19Z","receivedAt":"2017-03-29T04:32:38Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 03/29/2017 02:32 AM, Daniel Ferreira wrote:\n> Create inline helpers to dir_iterator_advance(). Make\n> dir_iterator_advance()'s code more legible and allow some behavior to\n> be reusable.\n\nThanks for breaking up the patches. That makes them a lot easier to review.\n\n> Signed-off-by: Daniel Ferreira <bnmvco@gmail.com>\n> ---\n>  dir-iterator.c | 65 +++++++++++++++++++++++++++++++++++++---------------------\n>  1 file changed, 42 insertions(+), 23 deletions(-)\n> \n> diff --git a/dir-iterator.c b/dir-iterator.c\n> index 34182a9..853c040 100644\n> --- a/dir-iterator.c\n> +++ b/dir-iterator.c\n> @@ -50,6 +50,43 @@ struct dir_iterator_int {\n>  \tstruct dir_iterator_level *levels;\n>  };\n> \n> +static inline void push_dir_level(struct dir_iterator_int *iter, struct dir_iterator_level *level)\n> +{\n> +\tlevel->dir_state = DIR_STATE_RECURSE;\n> +\tALLOC_GROW(iter->levels, iter->levels_nr + 1,\n> +\t\t   iter->levels_alloc);\n> +\tlevel = &iter->levels[iter->levels_nr++];\n> +\tlevel->initialized = 0;\n> +}\n> +\n> +static inline int pop_dir_level(struct dir_iterator_int *iter, struct dir_iterator_level *level)\n> +{\n> +\treturn --iter->levels_nr;\n> +}\n\n`pop_dir_level()` doesn't use its `level` argument; it can be removed.\n\n> [...]\n\nMichael\n\n"},{"id":"315657","messageId":"7a665631-da6a-4b9f-b9e7-750f2504eccd@alum.mit.edu","threadId":"45532","inReplyTo":"1490747533-89143-3-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v4 2/5] dir_iterator: iterate over dir after its contents","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-03-29T09:56:00Z","receivedAt":"2017-03-29T09:56:18Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 03/29/2017 02:32 AM, Daniel Ferreira wrote:\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).\n\nI admire your ambition at taking on this project. Even though the\n`dir_iterator` code is fairly short, it is quite intricate and it took\nme quite a bit of thought to get it right. Don't be discouraged by how\nmany iterations it takes to get a change like this accepted.\n\nWhen reviewing your changes, I realized that\n`dir_iterator_level::initialized` and `dir_iterator_level::dir_state`\nare somewhat redundant with each other in the pre-existing code. It\nwould be possible to add a third state, say `DIR_STATE_PUSH`, to the\nenum, and use that to replace the state that we now call `!initialized`.\n\nI'm not demanding that change, but it might make the bookkeeping in the\nnew code a little bit easier to understand, because the logic that\ndecides what to do based on setting of the new option would either\ntransition the level from `DIR_STATE_PUSH -> DIR_STATE_ITER ->\nDIR_STATE_RECURSE` (for pre-order traversal) or `DIR_STATE_PUSH ->\nDIR_STATE_RECURSE -> DIR_STATE_ITER` (for post-order traversal). I think\nthis could make the state machine clearer and thereby make it easier to\nreason about the code.\n\n> Add the \"flags\" parameter to dir_iterator_create, allowing for the\n> aforementioned \"depth-first\" iteration mode to be enabled. Currently,\n> the only acceptable flag is DIR_ITERATOR_DEPTH_FIRST.\n> \n> This is useful for recursively removing a directory and calling rmdir()\n> on a directory only after all of its contents have been wiped.\n\nThis patch changes the signature of `ref_iterator_begin()` without\nadjusting the caller in `refs/files-backend.c`. This means that the code\ndoesn't even compile after this patch is applied.\n\nThe Git project insists that the code compile and all tests pass after\neach and every commit. Among other things, this keeps the code\n\"bisectable\" using `git bisect`, which is a very useful property.\n\nI see that you adjust the caller later in the patch series, in\n\"files_reflog_iterator: amend use of dir_iterator\". Please squash that\npatch into this one.\n\nI also realize that I made a goof in my comments about v3 of this patch\nseries. Your new option is not choosing between \"depth-first\" and\n\"breadth-first\". Both types of iteration are depth-first. Really it is\nchoosing between pre-order and post-order traversal. So I think it would\nbe better to name the option `DIR_ITERATOR_POST_ORDER`. Sorry about that.\n\n> ---\n>  dir-iterator.c | 46 ++++++++++++++++++++++++++++++++++++++++++----\n>  dir-iterator.h | 14 +++++++++++---\n>  2 files changed, 53 insertions(+), 7 deletions(-)\n> \n> diff --git a/dir-iterator.c b/dir-iterator.c\n> index 853c040..545d333 100644\n> --- a/dir-iterator.c\n> +++ b/dir-iterator.c\n> @@ -48,6 +48,9 @@ struct dir_iterator_int {\n>  \t * that will be included in this iteration.\n>  \t */\n>  \tstruct dir_iterator_level *levels;\n> +\n> +\t/* Holds the flags passed to dir_iterator_begin(). */\n> +\tunsigned flags;\n>  };\n> \n>  static inline void push_dir_level(struct dir_iterator_int *iter, struct dir_iterator_level *level)\n> @@ -114,12 +117,14 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)\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} else if (S_ISDIR(iter->base.st.st_mode) &&\n> +\t\t!iter->flags & DIR_ITERATOR_DEPTH_FIRST) {\n\nYou need parentheses on the previous line:\n\n\t\t!(iter->flags & DIR_ITERATOR_DEPTH_FIRST)) {\n\nbecause otherwise it is interpreted as\n\n\t\t(!iter->flags) & DIR_ITERATOR_DEPTH_FIRST) {\n\nBTW, you should compile with stricter compiler options so that your\ncompiler warns you about problems like this. This is documented in\n`Documentation/CodingGuidelines` (along with lots more useful information):\n\n - As a Git developer we assume you have a reasonably modern compiler\n   and we recommend you to enable the DEVELOPER makefile knob to\n   ensure your patch is clear of all compiler warnings we care about,\n   by e.g. \"echo DEVELOPER=1 >>config.mak\".\n\nAlso, this line is not indented far enough. It should probably line up\nwith the inside of the opening parenthesis of the preceding line, like\n\n> +\t\t} else if (S_ISDIR(iter->base.st.st_mode) &&\n> +\t\t\t   !(iter->flags & DIR_ITERATOR_DEPTH_FIRST)) {\n\nBut let's dig a little bit deeper. Why don't the tests catch this coding\nerror? Currently there is only one option, `DIR_ITERATOR_DEPTH_FIRST`,\nso if that constant were defined to be 1 as expected, the code would\naccidentally work anyway (though it would break if another flag is ever\nadded). But in fact, you define `DIR_ITERATOR_DEPTH_FIRST` to be 2\n(probably unintentionally; see below), so this condition always\nevaluates to false!\n\nSo what's going on here? Why don't the tests fail?\n\nThe only pre-existing user of `dir_iterator` is\n`files_reflog_iterator_begin()`, and I think that none of the callers of\nthat function care whether the iteration is pre-order or post-order. So\nmaybe they're getting post-order iteration and just don't notice?\n\nBut no, that's not it either. For example, the following command, which\niterates over reflogs, gives different answers on your branch vs.\nstandard git:\n\n    $ git rev-list --all --reflog | sort >expected\n    $ ./git rev-list --all --reflog | sort >actual\n    $ git diff --no-index --numstat expected actual\n    0       1065    expected => actual\n\n(Adding the parentheses as suggested above makes the two outputs agree.)\n\nThe disagreement is not a surprise, because there isn't a corresponding\ncoding error in the code below that returns the directory itself in a\npost-order iteration. The net result appears to be that there is no\nrecursion at all into subdirectories when `DIR_ITERATOR_DEPTH_FIRST` is\nset. So due to this bug, we get neither a correct post-order iteration\nnor a correct pre-order iteration with the new option.\n\nIn summary, this is a trivial bug that is easy to fix, but it points to\nan alarming problem: our tests don't detect a pretty serious breakage in\nthe iteration over reflogs. And nothing is testing directory iteration\nitself, and in particular whether the new option is doing what it should.\n\nProbably the easiest way to remedy the latter problem would be to write\na little test helper program that iterates over an arbitrary directory\nand prints the names of the files that it finds, with a `--post-order`\noption that twiddles the new functionality. Then directory iteration\ncould be tested pretty easily by creating a few test directories and\nfiles, running the test helper, and checking its output (remembering\nthat the order of iteration at a *single directory level* is undefined).\nI think such a test is needed if we are to be confident that your\nchanges are correct.\n\n>  \t\t\tif (level->dir_state == DIR_STATE_ITER) {\n>  \t\t\t\t/*\n>  \t\t\t\t * The directory was just iterated\n>  \t\t\t\t * over; now prepare to iterate into\n> -\t\t\t\t * it.\n> +\t\t\t\t * it (unless an option is set for us\n> +\t\t\t\t * to do otherwise).\n>  \t\t\t\t */\n>  \t\t\t\tpush_dir_level(iter, level);\n>  \t\t\t\tcontinue;\n> @@ -153,10 +158,27 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)\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/* This level is exhausted  */\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 (iter->flags & DIR_ITERATOR_DEPTH_FIRST) {\n> +\t\t\t\t\t/* If we are handling dirpaths after their contents,\n> +\t\t\t\t\t * we have to iterate over the directory now that we'll\n> +\t\t\t\t\t * have finished iterating into it. */\n\nThe Git project style is to open and terminate multiline comments on\nseparate lines:\n\n        /*\n\t * If we are handling dirpaths after their contents,\n\t * we have to iterate over the directory now that we'll\n\t * have finished iterating into it.\n         */\n\nThe same problem appears elsewhere in your patch, too.\n\n> +\t\t\t\t\tlevel->dir = NULL;\n\nYou never call `closedir()` in this branch of the code, so you are\nleaking file descriptors. Meanwhile, I don't think there's a reason to\nset `dir->level` to `NULL` here, since it's just about to be popped off\nthe stack.\n\n> +\n> +\t\t\t\t\tif (pop_dir_level(iter, level) == 0)\n> +\t\t\t\t\t\treturn dir_iterator_abort(dir_iterator);\n> +\n> +\t\t\t\t\tlevel = &iter->levels[iter->levels_nr - 1];\n> +\t\t\t\t\t/* Remove a trailing slash */\n> +\t\t\t\t\tstrbuf_strip_suffix(&iter->base.path, \"/\");\n\nI think that unconditionally stripping trailing slashes prevents this\ncode from being used to iterate over the root directory, \"/\". It's\nprobably not a use case that will be needed, but it would be an\nunexpected surprise if anybody decided to do so.\n\nPlease either fix this or document the limitation.\n\n> +\n> +\t\t\t\t\tif (set_iterator_data(iter, level))\n> +\t\t\t\t\t\tcontinue;\n> +\n> +\t\t\t\t\treturn ITER_OK;\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> @@ -175,8 +197,22 @@ 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\t/*\n> +\t\t\t * If we want to iterate dirs after files, we shall\n> +\t\t\t * begin looking into them *before* we return the dir\n> +\t\t\t * itself.\n> +\t\t\t */\n> +\t\t\tif (S_ISDIR(iter->base.st.st_mode) &&\n> +\t\t\titer->flags & DIR_ITERATOR_DEPTH_FIRST) {\n\nThe line above is also indented incorrectly.\n\n> +\t\t\t\tpush_dir_level(iter, level);\n> +\t\t\t\tgoto continue_outer_loop;\n\nInstead of `goto`, couldn't you use `break` here?\n\n> +\t\t\t}\n> +\n>  \t\t\treturn ITER_OK;\n>  \t\t}\n> +\n> +continue_outer_loop:\n> +\t\t;\n>  \t}\n>  }\n> \n> @@ -201,7 +237,7 @@ int dir_iterator_abort(struct dir_iterator *dir_iterator)\n>  \treturn ITER_DONE;\n>  }\n> \n> -struct dir_iterator *dir_iterator_begin(const char *path)\n> +struct dir_iterator *dir_iterator_begin(const char *path, unsigned flags)\n>  {\n>  \tstruct dir_iterator_int *iter = xcalloc(1, sizeof(*iter));\n>  \tstruct dir_iterator *dir_iterator = &iter->base;\n> @@ -209,6 +245,8 @@ 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> diff --git a/dir-iterator.h b/dir-iterator.h\n> index 27739e6..28ff3df 100644\n> --- a/dir-iterator.h\n> +++ b/dir-iterator.h\n> @@ -38,6 +38,13 @@\n>   * dir_iterator_advance() again.\n>   */\n\nThe module docstring just above this hunk needs updating, too.\n\n> +/* Possible flags for dir_iterator_begin().\n> + *\n> + * DIR_ITERATOR_DEPTH_FIRST: ensures subdirectories and their contents\n> + * are iterated through before the containing directory.\n> + */\n> +#define DIR_ITERATOR_DEPTH_FIRST (1 << 1)\n> +\n\nNormally the first constant in a bitset gets the value `(1 << 0)`; i.e.,\n1. Is there a reason you use 2 here?\n\n> [...]\n\nMichael\n\n"},{"id":"315658","messageId":"679957e0-bb06-2dd9-bfc5-024da5ab49ce@alum.mit.edu","threadId":"45532","inReplyTo":"1490747533-89143-4-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v4 3/5] remove_subtree(): reimplement using iterators","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-03-29T10:01:12Z","receivedAt":"2017-03-29T10:01:26Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 03/29/2017 02:32 AM, Daniel Ferreira wrote:\n> Use dir_iterator to traverse through remove_subtree()'s directory tree,\n> avoiding the need for recursive calls to readdir(). Simplify\n> remove_subtree()'s code.\n> \n> A conversion similar in purpose was previously done at 46d092a\n> (\"for_each_reflog(): reimplement using iterators\", 2016-05-21).\n> \n> Signed-off-by: Daniel Ferreira <bnmvco@gmail.com>\n> ---\n>  entry.c | 31 ++++++++++---------------------\n>  1 file changed, 10 insertions(+), 21 deletions(-)\n> \n> diff --git a/entry.c b/entry.c\n> index c6eea24..bbebd16 100644\n> --- a/entry.c\n> +++ b/entry.c\n> @@ -2,6 +2,8 @@\n>  #include \"blob.h\"\n>  #include \"dir.h\"\n>  #include \"streaming.h\"\n> +#include \"iterator.h\"\n> +#include \"dir-iterator.h\"\n> \n>  static void create_directories(const char *path, int path_len,\n>  \t\t\t       const struct checkout *state)\n> @@ -46,29 +48,16 @@ static void create_directories(const char *path, int path_len,\n> \n>  static void remove_subtree(struct strbuf *path)\n\nThe reason that this function took a `strbuf` as argument was that it\nused to modify the strbuf while it was working. Now that `dir_iterator`\ndoes all of that work, you could simplify it to take a `const char *`\nargument, and change the caller to pass `path.buf`.\n\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> +\tstruct dir_iterator *diter = dir_iterator_begin(path->buf, DIR_ITERATOR_DEPTH_FIRST);\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'\", path->buf);\n> +\t\t} else if (unlink(diter->path.buf))\n>  \t\t\tdie_errno(\"cannot unlink '%s'\", path->buf);\n\nThe two `die_errno()` calls must be changed to use `diter->path.buf`\nrather than `path->buf`.\n\n> -\t\tstrbuf_setlen(path, origlen);\n>  \t}\n> -\tclosedir(dir);\n> +\n>  \tif (rmdir(path->buf))\n>  \t\tdie_errno(\"cannot rmdir '%s'\", path->buf);\n>  }\n\nMichael\n\n"},{"id":"315659","messageId":"8be27726-7de9-925c-47cd-60346206d635@alum.mit.edu","threadId":"45532","inReplyTo":"1490747533-89143-6-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v4 5/5] files_reflog_iterator: amend use of dir_iterator","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-03-29T10:45:16Z","receivedAt":"2017-03-29T10:49:09Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 03/29/2017 02:32 AM, Daniel Ferreira wrote:\n> Amend a call to dir_iterator_begin() to pass the flags parameter\n> introduced in 3efb5c0 (\"dir_iterator: iterate over dir after its\n> contents\", 2017-28-03).\n> \n> Signed-off-by: Daniel Ferreira <bnmvco@gmail.com>\n> ---\n>  refs/files-backend.c | 2 +-\n>  1 file changed, 1 insertion(+), 1 deletion(-)\n> \n> diff --git a/refs/files-backend.c b/refs/files-backend.c\n> index 50188e9..b4bba74 100644\n> --- a/refs/files-backend.c\n> +++ b/refs/files-backend.c\n> @@ -3346,7 +3346,7 @@ static struct ref_iterator *files_reflog_iterator_begin(struct ref_store *ref_st\n>  \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\nAs mentioned earlier, this patch should be squashed into patch [2/5].\n\nMichael\n\n"},{"id":"315661","messageId":"8eeadbe1-6a28-cee7-5dcb-5d408aac8925@alum.mit.edu","threadId":"45532","inReplyTo":"7a665631-da6a-4b9f-b9e7-750f2504eccd@alum.mit.edu","subject":"Re: [PATCH v4 2/5] dir_iterator: iterate over dir after its contents","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-03-29T10:44:13Z","receivedAt":"2017-03-29T11:41:59Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 03/29/2017 11:56 AM, Michael Haggerty wrote:\n> On 03/29/2017 02:32 AM, Daniel Ferreira wrote:\n>> [...]\n> [...]\n> The disagreement is not a surprise, because there isn't a corresponding\n> coding error in the code below that returns the directory itself in a\n> post-order iteration. The net result appears to be that there is no\n> recursion at all into subdirectories when `DIR_ITERATOR_DEPTH_FIRST` is\n> set. So due to this bug, we get neither a correct post-order iteration\n> nor a correct pre-order iteration with the new option.\n\nCorrection: the second-to-last sentence should read \"there is no\nrecursion at all into subdirectories when `DIR_ITERATOR_DEPTH_FIRST` is\n*NOT* set.\n\nMichael\n\n"},{"id":"315685","messageId":"xmqqk278av4x.fsf@gitster.mtv.corp.google.com","threadId":"45532","inReplyTo":"7a665631-da6a-4b9f-b9e7-750f2504eccd@alum.mit.edu","subject":"Re: [PATCH v4 2/5] dir_iterator: iterate over dir after its contents","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-03-29T16:46:22Z","receivedAt":"2017-03-29T16:46:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> writes:\n\n> I also realize that I made a goof in my comments about v3 of this patch\n> series. Your new option is not choosing between \"depth-first\" and\n> \"breadth-first\". Both types of iteration are depth-first. Really it is\n> choosing between pre-order and post-order traversal. So I think it would\n> be better to name the option `DIR_ITERATOR_POST_ORDER`. Sorry about that.\n\nThat solicits a natural reaction from a bystander.  Would an\nIN_ORDER option also be useful?  I am not demanding it to be added\nto this series, especially if there is no immediate need, but if we\nforesee that it would also make sense for some other callers, we\nwould at least want to make sure that the code after this addition\nof POST_ORDER is in a shape that is easy to add such an option\nlater.\n"},{"id":"315745","messageId":"e412ef09-276b-92df-d2c0-0bf2f80238d2@alum.mit.edu","threadId":"45532","inReplyTo":"xmqqk278av4x.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v4 2/5] dir_iterator: iterate over dir after its contents","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-03-30T04:59:45Z","receivedAt":"2017-03-30T04:59:56Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 03/29/2017 06:46 PM, Junio C Hamano wrote:\n> Michael Haggerty <mhagger@alum.mit.edu> writes:\n> \n>> I also realize that I made a goof in my comments about v3 of this patch\n>> series. Your new option is not choosing between \"depth-first\" and\n>> \"breadth-first\". Both types of iteration are depth-first. Really it is\n>> choosing between pre-order and post-order traversal. So I think it would\n>> be better to name the option `DIR_ITERATOR_POST_ORDER`. Sorry about that.\n> \n> That solicits a natural reaction from a bystander.  Would an\n> IN_ORDER option also be useful?  I am not demanding it to be added\n> to this series, especially if there is no immediate need, but if we\n> foresee that it would also make sense for some other callers, we\n> would at least want to make sure that the code after this addition\n> of POST_ORDER is in a shape that is easy to add such an option\n> later.\n\nI think IN_ORDER really only applies to *binary* trees, not arbitrary\ntrees like a filesystem.\n\nMichael\n\n"},{"id":"315747","messageId":"xmqqinmr70uc.fsf@gitster.mtv.corp.google.com","threadId":"45532","inReplyTo":"e412ef09-276b-92df-d2c0-0bf2f80238d2@alum.mit.edu","subject":"Re: [PATCH v4 2/5] dir_iterator: iterate over dir after its contents","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-03-30T06:08:59Z","receivedAt":"2017-03-30T06:09:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> writes:\n\n> I think IN_ORDER really only applies to *binary* trees, not arbitrary\n> trees like a filesystem.\n\nHow true.  Even if we were giving a sorted output (and dir-iterator\ndoesn't and there is no need for it to), dir/ should come before any\nof its contents, so for that application we can use pre-order, and\nthere is no sensible and useful definition of in-order.\n\nThanks.\n"},{"id":"315753","messageId":"1751d788-d1f1-1c97-b33b-f53dab78ef86@alum.mit.edu","threadId":"45532","inReplyTo":"xmqqinmr70uc.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v4 2/5] dir_iterator: iterate over dir after its contents","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-03-30T06:39:28Z","receivedAt":"2017-03-30T06:39:41Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 03/30/2017 08:08 AM, Junio C Hamano wrote:\n> Michael Haggerty <mhagger@alum.mit.edu> writes:\n> \n>> I think IN_ORDER really only applies to *binary* trees, not arbitrary\n>> trees like a filesystem.\n> \n> How true.  Even if we were giving a sorted output (and dir-iterator\n> doesn't and there is no need for it to), dir/ should come before any\n> of its contents, so for that application we can use pre-order, and\n> there is no sensible and useful definition of in-order.\n\nYour email got me thinking, though, that there is one generalization of\nthe concept of PRE_ORDER vs. POST_ORDER that would be both easy to\nimplement and potentially useful. Namely, flags could include the\nfollowing orthogonal options (instead of `DIR_ITERATOR_POST_ORDER)`:\n\n* DIR_ITERATOR_DIRS_BEFORE -- when this is set, directories\n  are included in the iteration *before* their contents.\n\n* DIR_ITERATOR_DIRS_AFTER -- when this is set, directories\n  are included in the iteration *after* their contents.\n\nEnabling one or the other of these options would select pre-order or\npost-order iteration.\n\nEnabling neither of them would mean that directory entries themselves\nare not included in the iteration at all, even though recursion would\nhappen *into* subdirectories. This option would surely be useful to some\ncaller somewhere (though it's easy for the caller to get the same effect\nitself via\n\n\tif (S_ISDIR(iter->base.st.st_mode))\n\t\tcontinue;\n\n).\n\nIt's even conceivable that enabling *both* options at the same time\nwould be useful, if the caller want to know when the processing of a\ndirectory is begun and also when it is finished (e.g., because it needs\nto load or unload a `.gitignore` file for that directory). If we wanted\nto make it easier for the caller figure out whether it is seeing an\n\"entering directory\" event vs. a \"leaving directory\" event, we could\nexpose something like the `dir_state` member in the iterator.\n\nWhile we're blue-skying, a\n\n* DIR_ITERATOR_RECURSE -- recurse into subdirectories\n\nwould make the set of possible options complete. If this option is not\nset, then the iteration would be over the entries in a single directory\nwithout traversing its subdirectories.\n\nI don't think any of this needs to be implemented now, but maybe keep it\nin mind if/when `dir_iterator` gets more users.\n\nMichael\n\n"},{"id":"315766","messageId":"CACsJy8DBa-oH3i+5P=iVr9NhJwsicZ43DO89WmvpYEQu90RrMw@mail.gmail.com","threadId":"45532","inReplyTo":"1751d788-d1f1-1c97-b33b-f53dab78ef86@alum.mit.edu","subject":"Re: [PATCH v4 2/5] dir_iterator: iterate over dir after its contents","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2017-03-30T11:08:05Z","receivedAt":"2017-03-30T11:08:41Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Mar 30, 2017 at 1:39 PM, Michael Haggerty <mhagger@alum.mit.edu> wrote:\n> * DIR_ITERATOR_RECURSE -- recurse into subdirectories\n>\n> would make the set of possible options complete. If this option is not\n> set, then the iteration would be over the entries in a single directory\n> without traversing its subdirectories.\n\nAnd would make it possible to use dir-iterator everywhere (except\nread_directory_recursiveky). That would be really nice :)\n-- \nDuy\n"},{"id":"315795","messageId":"xmqqmvc265hk.fsf@gitster.mtv.corp.google.com","threadId":"45532","inReplyTo":"1751d788-d1f1-1c97-b33b-f53dab78ef86@alum.mit.edu","subject":"Re: [PATCH v4 2/5] dir_iterator: iterate over dir after its contents","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-03-30T17:26:15Z","receivedAt":"2017-03-30T17:26:22Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> writes:\n\n> I don't think any of this needs to be implemented now, but maybe keep it\n> in mind if/when `dir_iterator` gets more users.\n\nOK.  One thing that was missing in your list was the opposite of \"do\nnot show directories\", i.e. \"show only directories\".  That should\nalso be easy to do (but we need to figure out a way to encode it in\nthe flag somehow) if it turns out to be useful later.\n\n\n"},{"id":"316037","messageId":"CAEA2_RKFwL8K=-QBYbmfbjJ44obB+PJit0pd5im0Jy_=E_-+MA@mail.gmail.com","threadId":"45532","inReplyTo":"CACsJy8DBa-oH3i+5P=iVr9NhJwsicZ43DO89WmvpYEQu90RrMw@mail.gmail.com","subject":"Re: [PATCH v4 2/5] dir_iterator: iterate over dir after its contents","fromName":"Daniel Ferreira (theiostream)","fromEmail":"bnmvco@gmail.com","sentAt":"2017-04-02T04:25:19Z","receivedAt":"2017-04-02T04:25:56Z","isPatch":true,"sender":{"key":"bnmvco@gmail.com","avatar":"https://avatars.githubusercontent.com/u/735397?v=4"},"body":"Why exactly would it not be applicable to read_directory_recursively()?\n\nOn Thu, Mar 30, 2017 at 8:08 AM, Duy Nguyen <pclouds@gmail.com> wrote:\n> On Thu, Mar 30, 2017 at 1:39 PM, Michael Haggerty <mhagger@alum.mit.edu> wrote:\n>> * DIR_ITERATOR_RECURSE -- recurse into subdirectories\n>>\n>> would make the set of possible options complete. If this option is not\n>> set, then the iteration would be over the entries in a single directory\n>> without traversing its subdirectories.\n>\n> And would make it possible to use dir-iterator everywhere (except\n> read_directory_recursiveky). That would be really nice :)\n> --\n> Duy\n"},{"id":"316182","messageId":"CACsJy8BTKHZqsJfbvmi9YgeaDyHK6wjBLf9dkBXfbZ=BRMa=pA@mail.gmail.com","threadId":"45532","inReplyTo":"CAEA2_RKFwL8K=-QBYbmfbjJ44obB+PJit0pd5im0Jy_=E_-+MA@mail.gmail.com","subject":"Re: [PATCH v4 2/5] dir_iterator: iterate over dir after its contents","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2017-04-05T09:21:45Z","receivedAt":"2017-04-05T09:22:31Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, Apr 2, 2017 at 11:25 AM, Daniel Ferreira (theiostream)\n<bnmvco@gmail.com> wrote:\n> Why exactly would it not be applicable to read_directory_recursively()?\n\nBecause that function is a beast (and probably should have \"beast\" in\nthe function name).\n\nThe function is supposed to read .gitignore, index file and whatever\nelse needed, traverse the directory and return the list of untracked\nfiles, or ignored files. It even has options to return a directory\npath, if all entries inside is ignored/untracked, instead of the list\nof files inside. On top of that, it has \"untracked cache\" to skip\ntraversing directories to speed up.\n\nUsing dir_iterator might be possible but we'll need to improve it a\nlot. read_directory_recursively() needs really fine control over\ntraversing: it can decide to not recurse in a subdirectory, it can\ndecide to ignore the rest of the entries in a directory and go back to\nits parent, and in the case of untracked cache, it can switch to\ntraversing the cache instead of on-disk directories.\n\nIt's possible, probably, but it's going to need quite a lot of work\n(and care, since I think there are corner cases that have been abused\nin real world and we just cannot change those behaviors). Using\niterator interface would be a good improvement to clean up the \"on\ndisk or on cache\" directory traversal there though.\n\n>\n> On Thu, Mar 30, 2017 at 8:08 AM, Duy Nguyen <pclouds@gmail.com> wrote:\n>> On Thu, Mar 30, 2017 at 1:39 PM, Michael Haggerty <mhagger@alum.mit.edu> wrote:\n>>> * DIR_ITERATOR_RECURSE -- recurse into subdirectories\n>>>\n>>> would make the set of possible options complete. If this option is not\n>>> set, then the iteration would be over the entries in a single directory\n>>> without traversing its subdirectories.\n>>\n>> And would make it possible to use dir-iterator everywhere (except\n>> read_directory_recursiveky). That would be really nice :)\n>> --\n>> Duy\n\n\n\n-- \nDuy\n"}]}