{"action":"created","comment":{"url":"https://api.github.com/repos/D-Programming-Language/phobos/pulls/comments/25757413","id":25757413,"diff_hunk":"@@ -1225,26 +1221,37 @@ private template TimSortImpl(alias pred, R)\n             stack[stackLen++] = Slice(i, runLen);\n             i += runLen;\n \n-            // Collapse stack so that (e1 >= e2 + e3 && e2 >= e3)\n+            // Collapse stack so that (e1 > e2 + e3 && e2 > e3)\n             // STACK is | ... e1 e2 e3 >\n             while (stackLen > 1)\n             {\n-                immutable run3 = stackLen - 1;\n-                immutable run2 = stackLen - 2;\n-                immutable run1 = stackLen - 3;\n-                if (stackLen >= 3 && stack[run1].length <= stack[run2].length + stack[run3].length)\n+                immutable run1 = stackLen - 4;\n+                immutable run2 = stackLen - 3;\n+                immutable run3 = stackLen - 2;\n+                immutable run4 = stackLen - 1;\n+                \n+                if (stackLen > 2 && stack[run2].length <= stack[run3].length + stack[run4].length || \n+                    stackLen > 3 && stack[run1].length <= stack[run3].length + stack[run2].length )\n                 {\n-                    immutable at = stack[run1].length <= stack[run3].length\n-                        ? run1 : run2;\n+                    immutable at = stack[run2].length < stack[run4].length ? run2 : run3;\n                     mergeAt(range, stack[0 .. stackLen], at, minGallop, temp);\n-                    --stackLen;\n+                    \n                 }\n-                else if (stack[run2].length <= stack[run3].length)\n+                else if (stack[run3].length > stack[run4].length) break;\n+                else mergeAt(range, stack[0 .. stackLen], run3, minGallop, temp);\n+                \n+                stackLen -= 1;\n+            }\n+            \n+            // Assert that the code above established the invariant correctly\n+            debug","path":"std/algorithm/sorting.d","position":49,"original_position":49,"commit_id":"323b512596470227893f3682474db2b4df36a673","original_commit_id":"323b512596470227893f3682474db2b4df36a673","user":{"login":"Orvid","id":709247,"avatar_url":"https://avatars.githubusercontent.com/u/709247?v=3","gravatar_id":"","url":"https://api.github.com/users/Orvid","html_url":"https://github.com/Orvid","followers_url":"https://api.github.com/users/Orvid/followers","following_url":"https://api.github.com/users/Orvid/following{/other_user}","gists_url":"https://api.github.com/users/Orvid/gists{/gist_id}","starred_url":"https://api.github.com/users/Orvid/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Orvid/subscriptions","organizations_url":"https://api.github.com/users/Orvid/orgs","repos_url":"https://api.github.com/users/Orvid/repos","events_url":"https://api.github.com/users/Orvid/events{/privacy}","received_events_url":"https://api.github.com/users/Orvid/received_events","type":"User","site_admin":false},"body":"`version (assert)` would be the correct way to denote this I believe. (as this is a contract)","created_at":"2015-03-04T07:59:08Z","updated_at":"2015-03-04T07:59:08Z","html_url":"https://github.com/D-Programming-Language/phobos/pull/3029#discussion_r25757413","pull_request_url":"https://api.github.com/repos/D-Programming-Language/phobos/pulls/3029","_links":{"self":{"href":"https://api.github.com/repos/D-Programming-Language/phobos/pulls/comments/25757413"},"html":{"href":"https://github.com/D-Programming-Language/phobos/pull/3029#discussion_r25757413"},"pull_request":{"href":"https://api.github.com/repos/D-Programming-Language/phobos/pulls/3029"}}},"pull_request":{"url":"https://api.github.com/repos/D-Programming-Language/phobos/pulls/3029","id":30249876,"html_url":"https://github.com/D-Programming-Language/phobos/pull/3029","diff_url":"https://github.com/D-Programming-Language/phobos/pull/3029.diff","patch_url":"https://github.com/D-Programming-Language/phobos/pull/3029.patch","issue_url":"https://api.github.com/repos/D-Programming-Language/phobos/issues/3029","number":3029,"state":"open","locked":false,"title":"Fix Issue 14223 - TimSort algorithm is incorrect","user":{"login":"Xinok","id":1572264,"avatar_url":"https://avatars.githubusercontent.com/u/1572264?v=3","gravatar_id":"","url":"https://api.github.com/users/Xinok","html_url":"https://github.com/Xinok","followers_url":"https://api.github.com/users/Xinok/followers","following_url":"https://api.github.com/users/Xinok/following{/other_user}","gists_url":"https://api.github.com/users/Xinok/gists{/gist_id}","starred_url":"https://api.github.com/users/Xinok/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Xinok/subscriptions","organizations_url":"https://api.github.com/users/Xinok/orgs","repos_url":"https://api.github.com/users/Xinok/repos","events_url":"https://api.github.com/users/Xinok/events{/privacy}","received_events_url":"https://api.github.com/users/Xinok/received_events","type":"User","site_admin":false},"body":"This fixes the issue described in [this article](http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/) which found most implementations of Timsort are incorrect. I took the fix provided in that article and adapted it to the Phobos implementation.\r\n\r\nI don't have a formal proof that my fix is correct. However, I added a check to debug builds which traverses the stack and confirms that the invariant of the stack is preserved. I also found a few test cases which broke the invariant on the old implementation but work correctly with this new fix. I added a unittest for the simplest of these cases.\r\n\r\nA few other minor changes:\r\n* The comment describing the invariant was wrong so I corrected that.\r\n* uninitializedArray now works correctly in CTFE so there's no more need for the __ctfe check.\r\n* I corrected a few cases of unsigned integer underflow, e.g. `at == stack.length - 2`.","created_at":"2015-03-01T22:08:36Z","updated_at":"2015-03-04T07:59:08Z","closed_at":null,"merged_at":null,"merge_commit_sha":"84ada85583a5c77354a426c1c35af37fd9bd37ac","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/D-Programming-Language/phobos/pulls/3029/commits","review_comments_url":"https://api.github.com/repos/D-Programming-Language/phobos/pulls/3029/comments","review_comment_url":"https://api.github.com/repos/D-Programming-Language/phobos/pulls/comments{/number}","comments_url":"https://api.github.com/repos/D-Programming-Language/phobos/issues/3029/comments","statuses_url":"https://api.github.com/repos/D-Programming-Language/phobos/statuses/323b512596470227893f3682474db2b4df36a673","head":{"label":"Xinok:issue_14223","ref":"issue_14223","sha":"323b512596470227893f3682474db2b4df36a673","user":{"login":"Xinok","id":1572264,"avatar_url":"https://avatars.githubusercontent.com/u/1572264?v=3","gravatar_id":"","url":"https://api.github.com/users/Xinok","html_url":"https://github.com/Xinok","followers_url":"https://api.github.com/users/Xinok/followers","following_url":"https://api.github.com/users/Xinok/following{/other_user}","gists_url":"https://api.github.com/users/Xinok/gists{/gist_id}","starred_url":"https://api.github.com/users/Xinok/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Xinok/subscriptions","organizations_url":"https://api.github.com/users/Xinok/orgs","repos_url":"https://api.github.com/users/Xinok/repos","events_url":"https://api.github.com/users/Xinok/events{/privacy}","received_events_url":"https://api.github.com/users/Xinok/received_events","type":"User","site_admin":false},"repo":{"id":31511984,"name":"phobos","full_name":"Xinok/phobos","owner":{"login":"Xinok","id":1572264,"avatar_url":"https://avatars.githubusercontent.com/u/1572264?v=3","gravatar_id":"","url":"https://api.github.com/users/Xinok","html_url":"https://github.com/Xinok","followers_url":"https://api.github.com/users/Xinok/followers","following_url":"https://api.github.com/users/Xinok/following{/other_user}","gists_url":"https://api.github.com/users/Xinok/gists{/gist_id}","starred_url":"https://api.github.com/users/Xinok/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Xinok/subscriptions","organizations_url":"https://api.github.com/users/Xinok/orgs","repos_url":"https://api.github.com/users/Xinok/repos","events_url":"https://api.github.com/users/Xinok/events{/privacy}","received_events_url":"https://api.github.com/users/Xinok/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/Xinok/phobos","description":"The standard library of the D programming language","fork":true,"url":"https://api.github.com/repos/Xinok/phobos","forks_url":"https://api.github.com/repos/Xinok/phobos/forks","keys_url":"https://api.github.com/repos/Xinok/phobos/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Xinok/phobos/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Xinok/phobos/teams","hooks_url":"https://api.github.com/repos/Xinok/phobos/hooks","issue_events_url":"https://api.github.com/repos/Xinok/phobos/issues/events{/number}","events_url":"https://api.github.com/repos/Xinok/phobos/events","assignees_url":"https://api.github.com/repos/Xinok/phobos/assignees{/user}","branches_url":"https://api.github.com/repos/Xinok/phobos/branches{/branch}","tags_url":"https://api.github.com/repos/Xinok/phobos/tags","blobs_url":"https://api.github.com/repos/Xinok/phobos/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Xinok/phobos/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Xinok/phobos/git/refs{/sha}","trees_url":"https://api.github.com/repos/Xinok/phobos/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Xinok/phobos/statuses/{sha}","languages_url":"https://api.github.com/repos/Xinok/phobos/languages","stargazers_url":"https://api.github.com/repos/Xinok/phobos/stargazers","contributors_url":"https://api.github.com/repos/Xinok/phobos/contributors","subscribers_url":"https://api.github.com/repos/Xinok/phobos/subscribers","subscription_url":"https://api.github.com/repos/Xinok/phobos/subscription","commits_url":"https://api.github.com/repos/Xinok/phobos/commits{/sha}","git_commits_url":"https://api.github.com/repos/Xinok/phobos/git/commits{/sha}","comments_url":"https://api.github.com/repos/Xinok/phobos/comments{/number}","issue_comment_url":"https://api.github.com/repos/Xinok/phobos/issues/comments{/number}","contents_url":"https://api.github.com/repos/Xinok/phobos/contents/{+path}","compare_url":"https://api.github.com/repos/Xinok/phobos/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Xinok/phobos/merges","archive_url":"https://api.github.com/repos/Xinok/phobos/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Xinok/phobos/downloads","issues_url":"https://api.github.com/repos/Xinok/phobos/issues{/number}","pulls_url":"https://api.github.com/repos/Xinok/phobos/pulls{/number}","milestones_url":"https://api.github.com/repos/Xinok/phobos/milestones{/number}","notifications_url":"https://api.github.com/repos/Xinok/phobos/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Xinok/phobos/labels{/name}","releases_url":"https://api.github.com/repos/Xinok/phobos/releases{/id}","created_at":"2015-03-01T21:45:30Z","updated_at":"2015-03-01T21:50:21Z","pushed_at":"2015-03-01T21:55:02Z","git_url":"git://github.com/Xinok/phobos.git","ssh_url":"git@github.com:Xinok/phobos.git","clone_url":"https://github.com/Xinok/phobos.git","svn_url":"https://github.com/Xinok/phobos","homepage":"dlang.org/phobos","size":38249,"stargazers_count":0,"watchers_count":0,"language":"D","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"D-Programming-Language:master","ref":"master","sha":"4f3c90aaa3f47404647993eab2e92b53a9bfa4b9","user":{"login":"D-Programming-Language","id":565913,"avatar_url":"https://avatars.githubusercontent.com/u/565913?v=3","gravatar_id":"","url":"https://api.github.com/users/D-Programming-Language","html_url":"https://github.com/D-Programming-Language","followers_url":"https://api.github.com/users/D-Programming-Language/followers","following_url":"https://api.github.com/users/D-Programming-Language/following{/other_user}","gists_url":"https://api.github.com/users/D-Programming-Language/gists{/gist_id}","starred_url":"https://api.github.com/users/D-Programming-Language/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/D-Programming-Language/subscriptions","organizations_url":"https://api.github.com/users/D-Programming-Language/orgs","repos_url":"https://api.github.com/users/D-Programming-Language/repos","events_url":"https://api.github.com/users/D-Programming-Language/events{/privacy}","received_events_url":"https://api.github.com/users/D-Programming-Language/received_events","type":"Organization","site_admin":false},"repo":{"id":1257084,"name":"phobos","full_name":"D-Programming-Language/phobos","owner":{"login":"D-Programming-Language","id":565913,"avatar_url":"https://avatars.githubusercontent.com/u/565913?v=3","gravatar_id":"","url":"https://api.github.com/users/D-Programming-Language","html_url":"https://github.com/D-Programming-Language","followers_url":"https://api.github.com/users/D-Programming-Language/followers","following_url":"https://api.github.com/users/D-Programming-Language/following{/other_user}","gists_url":"https://api.github.com/users/D-Programming-Language/gists{/gist_id}","starred_url":"https://api.github.com/users/D-Programming-Language/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/D-Programming-Language/subscriptions","organizations_url":"https://api.github.com/users/D-Programming-Language/orgs","repos_url":"https://api.github.com/users/D-Programming-Language/repos","events_url":"https://api.github.com/users/D-Programming-Language/events{/privacy}","received_events_url":"https://api.github.com/users/D-Programming-Language/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/D-Programming-Language/phobos","description":"The standard library of the D programming language","fork":false,"url":"https://api.github.com/repos/D-Programming-Language/phobos","forks_url":"https://api.github.com/repos/D-Programming-Language/phobos/forks","keys_url":"https://api.github.com/repos/D-Programming-Language/phobos/keys{/key_id}","collaborators_url":"https://api.github.com/repos/D-Programming-Language/phobos/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/D-Programming-Language/phobos/teams","hooks_url":"https://api.github.com/repos/D-Programming-Language/phobos/hooks","issue_events_url":"https://api.github.com/repos/D-Programming-Language/phobos/issues/events{/number}","events_url":"https://api.github.com/repos/D-Programming-Language/phobos/events","assignees_url":"https://api.github.com/repos/D-Programming-Language/phobos/assignees{/user}","branches_url":"https://api.github.com/repos/D-Programming-Language/phobos/branches{/branch}","tags_url":"https://api.github.com/repos/D-Programming-Language/phobos/tags","blobs_url":"https://api.github.com/repos/D-Programming-Language/phobos/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/D-Programming-Language/phobos/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/D-Programming-Language/phobos/git/refs{/sha}","trees_url":"https://api.github.com/repos/D-Programming-Language/phobos/git/trees{/sha}","statuses_url":"https://api.github.com/repos/D-Programming-Language/phobos/statuses/{sha}","languages_url":"https://api.github.com/repos/D-Programming-Language/phobos/languages","stargazers_url":"https://api.github.com/repos/D-Programming-Language/phobos/stargazers","contributors_url":"https://api.github.com/repos/D-Programming-Language/phobos/contributors","subscribers_url":"https://api.github.com/repos/D-Programming-Language/phobos/subscribers","subscription_url":"https://api.github.com/repos/D-Programming-Language/phobos/subscription","commits_url":"https://api.github.com/repos/D-Programming-Language/phobos/commits{/sha}","git_commits_url":"https://api.github.com/repos/D-Programming-Language/phobos/git/commits{/sha}","comments_url":"https://api.github.com/repos/D-Programming-Language/phobos/comments{/number}","issue_comment_url":"https://api.github.com/repos/D-Programming-Language/phobos/issues/comments{/number}","contents_url":"https://api.github.com/repos/D-Programming-Language/phobos/contents/{+path}","compare_url":"https://api.github.com/repos/D-Programming-Language/phobos/compare/{base}...{head}","merges_url":"https://api.github.com/repos/D-Programming-Language/phobos/merges","archive_url":"https://api.github.com/repos/D-Programming-Language/phobos/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/D-Programming-Language/phobos/downloads","issues_url":"https://api.github.com/repos/D-Programming-Language/phobos/issues{/number}","pulls_url":"https://api.github.com/repos/D-Programming-Language/phobos/pulls{/number}","milestones_url":"https://api.github.com/repos/D-Programming-Language/phobos/milestones{/number}","notifications_url":"https://api.github.com/repos/D-Programming-Language/phobos/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/D-Programming-Language/phobos/labels{/name}","releases_url":"https://api.github.com/repos/D-Programming-Language/phobos/releases{/id}","created_at":"2011-01-15T07:00:06Z","updated_at":"2015-03-03T21:07:10Z","pushed_at":"2015-03-03T21:54:52Z","git_url":"git://github.com/D-Programming-Language/phobos.git","ssh_url":"git@github.com:D-Programming-Language/phobos.git","clone_url":"https://github.com/D-Programming-Language/phobos.git","svn_url":"https://github.com/D-Programming-Language/phobos","homepage":"dlang.org/phobos","size":67521,"stargazers_count":571,"watchers_count":571,"language":"D","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":376,"mirror_url":null,"open_issues_count":55,"forks":376,"open_issues":55,"watchers":571,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/D-Programming-Language/phobos/pulls/3029"},"html":{"href":"https://github.com/D-Programming-Language/phobos/pull/3029"},"issue":{"href":"https://api.github.com/repos/D-Programming-Language/phobos/issues/3029"},"comments":{"href":"https://api.github.com/repos/D-Programming-Language/phobos/issues/3029/comments"},"review_comments":{"href":"https://api.github.com/repos/D-Programming-Language/phobos/pulls/3029/comments"},"review_comment":{"href":"https://api.github.com/repos/D-Programming-Language/phobos/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/D-Programming-Language/phobos/pulls/3029/commits"},"statuses":{"href":"https://api.github.com/repos/D-Programming-Language/phobos/statuses/323b512596470227893f3682474db2b4df36a673"}}}}