{"action":"created","issue":{"url":"https://api.github.com/repos/golang/go/issues/13861","labels_url":"https://api.github.com/repos/golang/go/issues/13861/labels{/name}","comments_url":"https://api.github.com/repos/golang/go/issues/13861/comments","events_url":"https://api.github.com/repos/golang/go/issues/13861/events","html_url":"https://github.com/golang/go/issues/13861","id":125500303,"number":13861,"title":"filepath: Walk output is not truly lexically sorted","user":{"login":"harshavardhana","id":622699,"avatar_url":"https://avatars.githubusercontent.com/u/622699?v=3","gravatar_id":"","url":"https://api.github.com/users/harshavardhana","html_url":"https://github.com/harshavardhana","followers_url":"https://api.github.com/users/harshavardhana/followers","following_url":"https://api.github.com/users/harshavardhana/following{/other_user}","gists_url":"https://api.github.com/users/harshavardhana/gists{/gist_id}","starred_url":"https://api.github.com/users/harshavardhana/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/harshavardhana/subscriptions","organizations_url":"https://api.github.com/users/harshavardhana/orgs","repos_url":"https://api.github.com/users/harshavardhana/repos","events_url":"https://api.github.com/users/harshavardhana/events{/privacy}","received_events_url":"https://api.github.com/users/harshavardhana/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2016-01-07T22:33:53Z","updated_at":"2016-01-07T23:55:32Z","closed_at":"2016-01-07T23:55:32Z","body":"The problem arises when recursively listing directories and files which have prefix in common. This issue occurred when we wrote 'mc mirror' where we had to match object names in a streaming manner coming from AWS S3 (lexically sorted) v/s lexically sorted filesystem. \r\n\r\nGolang existing code base here is the following output. \r\n```\r\n[2015-11-06 10:58:09 PST]   306B usr/local/Cellar/boost/1.59.0/include/boost/ratio/\r\n[2015-11-06 10:58:08 PST] 2.9KiB usr/local/Cellar/boost/1.59.0/include/boost/ratio/config.hpp\r\n[2015-11-06 10:58:19 PST]   170B usr/local/Cellar/boost/1.59.0/include/boost/ratio/detail/\r\n[2015-11-06 10:58:26 PST]   204B usr/local/Cellar/boost/1.59.0/include/boost/ratio/detail/mpl/\r\n[2015-11-06 10:58:26 PST] 2.1KiB usr/local/Cellar/boost/1.59.0/include/boost/ratio/detail/mpl/abs.hpp\r\n[2015-11-06 10:58:26 PST] 3.6KiB usr/local/Cellar/boost/1.59.0/include/boost/ratio/detail/mpl/gcd.hpp\r\n[2015-11-06 10:58:26 PST] 3.7KiB usr/local/Cellar/boost/1.59.0/include/boost/ratio/detail/mpl/lcm.hpp\r\n[2015-11-06 10:58:26 PST] 2.1KiB usr/local/Cellar/boost/1.59.0/include/boost/ratio/detail/mpl/sign.hpp\r\n[2015-11-06 10:58:19 PST]  13KiB usr/local/Cellar/boost/1.59.0/include/boost/ratio/detail/overflow_helpers.hpp\r\n[2015-11-06 10:58:19 PST]  37KiB usr/local/Cellar/boost/1.59.0/include/boost/ratio/detail/ratio_io.hpp\r\n[2015-11-06 10:58:09 PST]   493B usr/local/Cellar/boost/1.59.0/include/boost/ratio/include.hpp\r\n[2015-11-06 10:58:19 PST]   748B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/\r\n[2015-11-06 10:58:19 PST]   650B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/abs.hpp\r\n[2015-11-06 10:58:19 PST]   692B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/arithmetic.hpp\r\n[2015-11-06 10:58:19 PST]   610B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/comparison.hpp\r\n[2015-11-06 10:58:19 PST]   698B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/divides.hpp\r\n[2015-11-06 10:58:19 PST]   703B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/equal_to.hpp\r\n[2015-11-06 10:58:19 PST]   684B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/gcd.hpp\r\n[2015-11-06 10:58:19 PST]   699B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/greater.hpp\r\n[2015-11-06 10:58:19 PST]   741B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/greater_equal.hpp\r\n[2015-11-06 10:58:19 PST]   684B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/lcm.hpp\r\n[2015-11-06 10:58:19 PST]   678B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/less.hpp\r\n[2015-11-06 10:58:19 PST]   720B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/less_equal.hpp\r\n[2015-11-06 10:58:19 PST]   688B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/minus.hpp\r\n[2015-11-06 10:58:19 PST]   658B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/negate.hpp\r\n[2015-11-06 10:58:19 PST]   731B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/not_equal_to.hpp\r\n[2015-11-06 10:58:19 PST]   748B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/numeric_cast.hpp\r\n[2015-11-06 10:58:19 PST]   676B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/plus.hpp\r\n[2015-11-06 10:58:19 PST]   564B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/rational_c_tag.hpp\r\n[2015-11-06 10:58:19 PST]   542B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/rational_constant.hpp\r\n[2015-11-06 10:58:19 PST]   657B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/sign.hpp\r\n[2015-11-06 10:58:19 PST]   688B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/times.hpp\r\n[2015-11-06 10:58:09 PST] 8.7KiB usr/local/Cellar/boost/1.59.0/include/boost/ratio/ratio.hpp\r\n[2015-11-06 10:58:09 PST] 4.9KiB usr/local/Cellar/boost/1.59.0/include/boost/ratio/ratio_fwd.hpp\r\n[2015-11-06 10:58:09 PST]  24KiB usr/local/Cellar/boost/1.59.0/include/boost/ratio/ratio_io.hpp\r\n[2015-11-06 10:58:03 PST]   349B usr/local/Cellar/boost/1.59.0/include/boost/ratio.hpp\r\n```\r\n\r\n\r\nThe real problem happens inside readDirNames()\r\n\r\n```\r\n// readDirNames reads the directory named by dirname and returns\r\n   400\t// a sorted list of directory entries.\r\n   401\tfunc readDirNames(dirname string) ([]string, error) {\r\n   402\t\tf, err := os.Open(dirname)\r\n   403\t\tif err != nil {\r\n   404\t\t\treturn nil, err\r\n   405\t\t}\r\n   406\t\tnames, err := f.Readdirnames(-1)\r\n   407\t\tf.Close()\r\n   408\t\tif err != nil {\r\n   409\t\t\treturn nil, err\r\n   410\t\t}\r\n   411\t\tsort.Strings(names) --> Here! \r\n   412\t\treturn names, nil\r\n   413\t}\r\n``` \r\n\r\nThe directories are sorted along with files too for example if 'ratio.hpp'  is a file and 'ratio' is a directory 'ratio' becomes lexically higher which is incorrect since its a directory it should be sorted along with its 'trailing slash' , f.Readdirnames() removes any trailing slash for the list of names it replies back.  \r\n\r\nNow if you programmatically add trailing slash the results are as expected i.e 'ratio.hpp' and 'ratio/'  clearly ratio.hpp is lexically higher. \r\n\r\nI think the sorting behavior should change in filepath.Walk function to cater this behavior, since this is the right style of lexical sort.\r\n\r\nI wanted to open this issue and get some inputs from you all to see if its valid and discuss on a potential fix if any.  \r\n\r\nHere is a proposed fix for the issue.\r\n```\r\n// readDirNames reads the directory named by dirname and returns\r\n// a sorted list of directory entries.\r\nfunc readDirNames(dirname string) ([]string, error) {\r\n\tnames, err := readDirUnsortedNames(dirname)\r\n\tif err != nil {\r\n\t\treturn nil, err\r\n\t}\r\n\tsort.Strings(names)\r\n\treturn names, nil\r\n}\r\n\r\n// getRealName - gets the proper filename for sorting purposes\r\n// Readdir() filters out directory names without separators, add\r\n// them back for proper sorting results.\r\nfunc getRealName(info os.FileInfo) string {\r\n\tif info.IsDir() {\r\n\t\t// Make sure directory has its end separator.\r\n\t\treturn info.Name() + string(os.PathSeparator)\r\n\t}\r\n\treturn info.Name()\r\n}\r\n\r\nfunc readDirUnsortedNames(dirname string) ([]string, error) {\r\n\tf, err := os.Open(dirname)\r\n\tif err != nil {\r\n\t\treturn nil, err\r\n\t}\r\n\tnameInfos, err := f.Readdir(-1)\r\n\tf.Close()\r\n\tif err != nil {\r\n\t\treturn nil, err\r\n\t}\r\n\tvar names []string\r\n\tfor _, nameInfo := range nameInfos {\r\n\t\tnames = append(names, getRealName(nameInfo))\r\n\t}\r\n\treturn names, nil\r\n}\r\n```\r\n\r\nOutput after my modifications.\r\n```\r\n[2015-11-06 10:58:03 PST]   349B usr/local/Cellar/boost/1.59.0/include/boost/ratio.hpp\r\n[2015-11-06 10:58:09 PST]   306B usr/local/Cellar/boost/1.59.0/include/boost/ratio/\r\n[2015-11-06 10:58:08 PST] 2.9KiB usr/local/Cellar/boost/1.59.0/include/boost/ratio/config.hpp\r\n[2015-11-06 10:58:19 PST]   170B usr/local/Cellar/boost/1.59.0/include/boost/ratio/detail/\r\n[2015-11-06 10:58:26 PST]   204B usr/local/Cellar/boost/1.59.0/include/boost/ratio/detail/mpl/\r\n[2015-11-06 10:58:26 PST] 2.1KiB usr/local/Cellar/boost/1.59.0/include/boost/ratio/detail/mpl/abs.hpp\r\n[2015-11-06 10:58:26 PST] 3.6KiB usr/local/Cellar/boost/1.59.0/include/boost/ratio/detail/mpl/gcd.hpp\r\n[2015-11-06 10:58:26 PST] 3.7KiB usr/local/Cellar/boost/1.59.0/include/boost/ratio/detail/mpl/lcm.hpp\r\n[2015-11-06 10:58:26 PST] 2.1KiB usr/local/Cellar/boost/1.59.0/include/boost/ratio/detail/mpl/sign.hpp\r\n[2015-11-06 10:58:19 PST]  13KiB usr/local/Cellar/boost/1.59.0/include/boost/ratio/detail/overflow_helpers.hpp\r\n[2015-11-06 10:58:19 PST]  37KiB usr/local/Cellar/boost/1.59.0/include/boost/ratio/detail/ratio_io.hpp\r\n[2015-11-06 10:58:09 PST]   493B usr/local/Cellar/boost/1.59.0/include/boost/ratio/include.hpp\r\n[2015-11-06 10:58:19 PST]   748B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/\r\n[2015-11-06 10:58:19 PST]   650B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/abs.hpp\r\n[2015-11-06 10:58:19 PST]   692B usr/local/Cellar/boost/1.59.0/include/boost/ratio/mpl/arithmetic.hpp\r\n```\r\n\r\nNow you can see ratio.hpp is clearly the top one and listed before 'ratio/' \r\n\r\nThis way the output is truly lexically sorted. "},"comment":{"url":"https://api.github.com/repos/golang/go/issues/comments/169844152","html_url":"https://github.com/golang/go/issues/13861#issuecomment-169844152","issue_url":"https://api.github.com/repos/golang/go/issues/13861","id":169844152,"user":{"login":"ianlancetaylor","id":3194333,"avatar_url":"https://avatars.githubusercontent.com/u/3194333?v=3","gravatar_id":"","url":"https://api.github.com/users/ianlancetaylor","html_url":"https://github.com/ianlancetaylor","followers_url":"https://api.github.com/users/ianlancetaylor/followers","following_url":"https://api.github.com/users/ianlancetaylor/following{/other_user}","gists_url":"https://api.github.com/users/ianlancetaylor/gists{/gist_id}","starred_url":"https://api.github.com/users/ianlancetaylor/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ianlancetaylor/subscriptions","organizations_url":"https://api.github.com/users/ianlancetaylor/orgs","repos_url":"https://api.github.com/users/ianlancetaylor/repos","events_url":"https://api.github.com/users/ianlancetaylor/events{/privacy}","received_events_url":"https://api.github.com/users/ianlancetaylor/received_events","type":"User","site_admin":false},"created_at":"2016-01-07T23:55:32Z","updated_at":"2016-01-07T23:55:32Z","body":"The slash is not part of the name of the directory.  The function is working as documented.  I understand that you want a different sort, but I don't see a reason to change the currently documented behavior, especially since people may be depending on it today."}}