{"thread":{"id":"45511","subject":"[PATCH v3 0/2] [GSoC] remove_subtree(): reimplement using iterators","startedAt":"2017-03-25T18:13:07Z","lastAt":"2017-03-28T17:13:41Z","messageCount":6,"participants":["Daniel Ferreira","Michael Haggerty","Stefan Beller"],"isPatch":true,"patchVersion":3,"patchTotal":2},"messages":[{"id":"315401","messageId":"1490465551-71056-1-git-send-email-bnmvco@gmail.com","threadId":"45511","inReplyTo":null,"subject":"[PATCH v3 0/2] [GSoC] remove_subtree(): reimplement using iterators","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-03-25T18:12:29Z","receivedAt":"2017-03-25T18:13:07Z","isPatch":true,"sender":{"key":"bnmvco@gmail.com","avatar":"https://avatars.githubusercontent.com/u/735397?v=4"},"body":"This is the third version of the GSoC microproject\nof refactoring remove_subtree() from recursively using\nreaddir() to use dir_iterator. Below are the threads for\nother versions:\n\nv1: https://public-inbox.org/git/CAGZ79kZwT-9mHTiOJ5CEjk2wDFkn6+NcogjX0=vjhsAh16ANYg@mail.gmail.com/T/#mae023e7a7d7626f00e0923833c4359f5af493730\nv2: https://public-inbox.org/git/CACsJy8Dxh-QPBBLfaFWPAWUsbA9GVXA7x+mXLjEvYKhk1zOpig@mail.gmail.com/T/#t\n\nDuy suggested adding features to dir_iterator might go\nbeyond the intention of a microproject, but I figured I\nmight go for it to learn more about the project.\n\nThe dir_iterator reimplementation has been tested in a\nseparate binary I created (and linked with libgit.a) to\nreproduce remove_subtree()'s contents. As pointed out in the\nlast thread, git's tests for this function were unable to\ncatch a daunting bug I had introduced, and I still haven't\nbeen able to come up with a way to reproduce remove_subtree()\nbeing called. Any help?\n\nThank you all again for all the reviews.\n\nDaniel Ferreira (2):\n  dir_iterator: iterate over dir after its contents\n  remove_subtree(): reimplement using iterators\n\n dir-iterator.c | 100 ++++++++++++++++++++++++++++++++++++++++++++-------------\n dir-iterator.h |   7 ++++\n entry.c        |  32 +++++++-----------\n 3 files changed, 95 insertions(+), 44 deletions(-)\n\n--\n2.7.4 (Apple Git-66)\n\n"},{"id":"315402","messageId":"1490465551-71056-3-git-send-email-bnmvco@gmail.com","threadId":"45511","inReplyTo":"1490465551-71056-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v3 2/2] [GSoC] remove_subtree(): reimplement using iterators","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-03-25T18:12:31Z","receivedAt":"2017-03-25T18:14:44Z","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 | 32 +++++++++++---------------------\n 1 file changed, 11 insertions(+), 21 deletions(-)\n\ndiff --git a/entry.c b/entry.c\nindex c6eea24..670ffeb 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,17 @@ 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);\n+\tditer->options.iterate_dirs_after_files = 1;\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":"315403","messageId":"1490465551-71056-2-git-send-email-bnmvco@gmail.com","threadId":"45511","inReplyTo":"1490465551-71056-1-git-send-email-bnmvco@gmail.com","subject":"[PATCH v3 1/2] [GSoC] dir_iterator: iterate over dir after its contents","fromName":"Daniel Ferreira","fromEmail":"bnmvco@gmail.com","sentAt":"2017-03-25T18:12:30Z","receivedAt":"2017-03-25T18:20:26Z","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 a directory\npath only after having iterated through its contents. This feature was\npredicted, although not implemented by 0fe5043 (\"dir_iterator: new API\nfor iterating over a directory tree\", 2016-06-18).\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\nAn \"options\" member has been added to the dir_iterator struct. It\ncontains the \"iterate_dirs_after_files\" flag, that enables the feature\nwhen set to 1. Default behavior continues to be iterating over directory\npaths before its contents.\n\nTwo inline functions have been added to dir_iterator's code to avoid\ncode repetition inside dir_iterator_advance() and make code more clear.\n\nNo particular functions or wrappers for setting the options struct's\nfields have been added to avoid either breaking the current dir_iterator\nAPI or over-engineering an extremely simple option architecture.\n\nSigned-off-by: Daniel Ferreira <bnmvco@gmail.com>\n---\n dir-iterator.c | 100 ++++++++++++++++++++++++++++++++++++++++++++-------------\n dir-iterator.h |   7 ++++\n 2 files changed, 84 insertions(+), 23 deletions(-)\n\ndiff --git a/dir-iterator.c b/dir-iterator.c\nindex 34182a9..833d56a 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@@ -77,18 +114,16 @@ 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->base.options.iterate_dirs_after_files) {\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\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 +139,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@@ -120,16 +155,33 @@ 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->base.options.iterate_dirs_after_files) {\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\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,26 +190,26 @@ 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+\n+\t\t\tif (set_iterator_data(iter, level))\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 * 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\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 (S_ISDIR(iter->base.st.st_mode) &&\n+\t\t\titer->base.options.iterate_dirs_after_files) {\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@@ -190,6 +242,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->base.options.iterate_dirs_after_files = 0;\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..4304913 100644\n--- a/dir-iterator.h\n+++ b/dir-iterator.h\n@@ -38,7 +38,14 @@\n  * dir_iterator_advance() again.\n  */\n\n+struct dir_iterator_options {\n+\tunsigned iterate_dirs_after_files : 1;\n+};\n+\n struct dir_iterator {\n+\t/* Options for dir_iterator */\n+\tstruct dir_iterator_options options;\n+\n \t/* The current path: */\n \tstruct strbuf path;\n\n--\n2.7.4 (Apple Git-66)\n\n"},{"id":"315484","messageId":"c9b6276a-331f-f42e-94b4-bb38109485a4@alum.mit.edu","threadId":"45511","inReplyTo":"1490465551-71056-2-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v3 1/2] [GSoC] dir_iterator: iterate over dir after its contents","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-03-26T22:40:28Z","receivedAt":"2017-03-26T22:40:48Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 03/25/2017 07:12 PM, Daniel Ferreira wrote:\n> Create an option for the dir_iterator API to iterate over a directory\n> path only after having iterated through its 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> \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> \n> An \"options\" member has been added to the dir_iterator struct. It\n> contains the \"iterate_dirs_after_files\" flag, that enables the feature\n> when set to 1. Default behavior continues to be iterating over directory\n> paths before its contents.\n> \n> Two inline functions have been added to dir_iterator's code to avoid\n> code repetition inside dir_iterator_advance() and make code more clear.\n> \n> No particular functions or wrappers for setting the options struct's\n> fields have been added to avoid either breaking the current dir_iterator\n> API or over-engineering an extremely simple option architecture.\n\nThis patch would be easier to read if it were split into two: one\nextracting the new functions and changing old code to use them, and a\nsecond adding the new functionality. As one patch, is is hard to see\nquickly which changes have what purpose.\n\nI also suggest adding a new `unsigned int flags` parameter to\n`dir_iterator_begin`. I think that's more natural, because it doesn't\nmake sense to change the iteration order during an iteration. It's not\nmuch of a problem to change the API given that all callers are in the\nsame codebase. If you were to forget to convert any callers (or if a\ndifferent in-flight patch series were to add a new caller using the old\ncall style), the compiler would complain, and the problem would be\nobvious and easy to fix.\n\nI didn't actually read the patch carefully yet because I don't have time\nthis evening to seek out the interesting parts in the long diff.\n\nMichael\n\n> [...]\n\n"},{"id":"315485","messageId":"f8beff4b-8e50-99ac-715d-549ae40bba0c@alum.mit.edu","threadId":"45511","inReplyTo":"1490465551-71056-2-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v3 1/2] [GSoC] dir_iterator: iterate over dir after its contents","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-03-26T22:48:40Z","receivedAt":"2017-03-26T22:49:08Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 03/25/2017 07:12 PM, Daniel Ferreira wrote:\n> Create an option for the dir_iterator API to iterate over a directory\n> path only after having iterated through its 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> \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> \n> An \"options\" member has been added to the dir_iterator struct. It\n> contains the \"iterate_dirs_after_files\" flag, that enables the feature\n> when set to 1. Default behavior continues to be iterating over directory\n> paths before its contents.\n> \n> Two inline functions have been added to dir_iterator's code to avoid\n> code repetition inside dir_iterator_advance() and make code more clear.\n> \n> No particular functions or wrappers for setting the options struct's\n> fields have been added to avoid either breaking the current dir_iterator\n> API or over-engineering an extremely simple option architecture.\n> \n> Signed-off-by: Daniel Ferreira <bnmvco@gmail.com>\n> ---\n>  dir-iterator.c | 100 ++++++++++++++++++++++++++++++++++++++++++++-------------\n>  dir-iterator.h |   7 ++++\n>  2 files changed, 84 insertions(+), 23 deletions(-)\n> \n> [...]\n> diff --git a/dir-iterator.h b/dir-iterator.h\n> index 27739e6..4304913 100644\n> --- a/dir-iterator.h\n> +++ b/dir-iterator.h\n> @@ -38,7 +38,14 @@\n>   * dir_iterator_advance() again.\n>   */\n> \n> +struct dir_iterator_options {\n> +\tunsigned iterate_dirs_after_files : 1;\n> +};\n> +\n>  struct dir_iterator {\n> +\t/* Options for dir_iterator */\n> +\tstruct dir_iterator_options options;\n> +\n>  \t/* The current path: */\n>  \tstruct strbuf path;\n\nAnother thing I noticed: the name of this option,\n`iterate_dirs_after_files`, is a little bit misleading. If I understand\ncorrectly, it doesn't make the iteration process files before\ndirectories within a single directory; rather, it ensures that\nsubdirectories and their contents are processed before the containing\ndirectory. Therefore, a better name might be something like \"depth_first\".\n\nI should mention that I like the overall idea to add this new feature\nand use it to simplify `remove_subtree()`.\n\nMichael\n\n"},{"id":"315574","messageId":"CAGZ79kYtpmURSQWPumobA=e3JBFjKhWCdv_LPhKCd71ZRwMovA@mail.gmail.com","threadId":"45511","inReplyTo":"1490465551-71056-1-git-send-email-bnmvco@gmail.com","subject":"Re: [PATCH v3 0/2] [GSoC] remove_subtree(): reimplement using iterators","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-03-28T17:13:10Z","receivedAt":"2017-03-28T17:13:41Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Sat, Mar 25, 2017 at 11:12 AM, Daniel Ferreira <bnmvco@gmail.com> wrote:\n> This is the third version of the GSoC microproject\n> of refactoring remove_subtree() from recursively using\n> readdir() to use dir_iterator. Below are the threads for\n> other versions:\n>\n> v1: https://public-inbox.org/git/CAGZ79kZwT-9mHTiOJ5CEjk2wDFkn6+NcogjX0=vjhsAh16ANYg@mail.gmail.com/T/#mae023e7a7d7626f00e0923833c4359f5af493730\n> v2: https://public-inbox.org/git/CACsJy8Dxh-QPBBLfaFWPAWUsbA9GVXA7x+mXLjEvYKhk1zOpig@mail.gmail.com/T/#t\n>\n> Duy suggested adding features to dir_iterator might go\n> beyond the intention of a microproject, but I figured I\n> might go for it to learn more about the project.\n>\n> The dir_iterator reimplementation has been tested in a\n> separate binary I created (and linked with libgit.a) to\n> reproduce remove_subtree()'s contents. As pointed out in the\n> last thread, git's tests for this function were unable to\n> catch a daunting bug I had introduced, and I still haven't\n> been able to come up with a way to reproduce remove_subtree()\n> being called. Any help?\n>\n\nI would think a test llike the following would work:\n\ntest_expect_success 'remove nested subtrees' '\n    test_commit initial &&\n    mkdir -p dir/with/nested/dir &&\n    echo content >dir/with/nested/dir/file &&\n    echo content >dir/file &&\n    git add dir/with/nested/dir/file dir/file &&\n    git commit -a -m \"commit directory structure\" &&\n    git checkout initial &&\n    ! test dir\n'\n"}]}