{"action":"created","comment":{"url":"https://api.github.com/repos/NixOS/nixpkgs/pulls/comments/46765520","id":46765520,"diff_hunk":"@@ -193,6 +193,38 @@ rec {\n       if len < 2 then list\n       else (sort strictLess pivot.left) ++  [ first ] ++  (sort strictLess pivot.right));\n \n+  # Depth-First Search (DFS) for `list != []`.\n+  #\n+  # `before a b == true` means that `b` depends on `a` (there's an\n+  # edge from `b` to `a`).\n+  listDfs = before: list:\n+   let\n+     dfs' = us: visited: rest:\n+       let\n+         b = partition (x: before x us) rest;\n+       in if length b.right == 0\n+          # if nothing is before us\n+          then { minimal = us; inherit visited rest; }\n+          # else grab the first one before us and continue\n+          else dfs' (head b.right)\n+                    ([ us ] ++ visited)\n+                    (tail b.right ++ b.wrong);\n+   in dfs' (head list) [] (tail list);\n+\n+  # Sort a list based on a partial ordering using DFS. This\n+  # implementation is O(N^2) in the best case, if your ordering is\n+  # linear, use `sort` instead.\n+  #\n+  # `before a b == true` means that `b` should be after `a`\n+  # in the result.\n+  toposort = before: list:","path":"lib/lists.nix","position":28,"original_position":28,"commit_id":"39f00bf273348eca63c638c955811aeb3a0f4697","original_commit_id":"39f00bf273348eca63c638c955811aeb3a0f4697","user":{"login":"oxij","id":391919,"avatar_url":"https://avatars.githubusercontent.com/u/391919?v=3","gravatar_id":"","url":"https://api.github.com/users/oxij","html_url":"https://github.com/oxij","followers_url":"https://api.github.com/users/oxij/followers","following_url":"https://api.github.com/users/oxij/following{/other_user}","gists_url":"https://api.github.com/users/oxij/gists{/gist_id}","starred_url":"https://api.github.com/users/oxij/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/oxij/subscriptions","organizations_url":"https://api.github.com/users/oxij/orgs","repos_url":"https://api.github.com/users/oxij/repos","events_url":"https://api.github.com/users/oxij/events{/privacy}","received_events_url":"https://api.github.com/users/oxij/received_events","type":"User","site_admin":false},"body":"You mean in the comment there? Because the next patch in the list is a\ngood example in itself.\n","created_at":"2015-12-06T01:41:01Z","updated_at":"2015-12-06T01:41:01Z","html_url":"https://github.com/NixOS/nixpkgs/pull/11484#discussion_r46765520","pull_request_url":"https://api.github.com/repos/NixOS/nixpkgs/pulls/11484","_links":{"self":{"href":"https://api.github.com/repos/NixOS/nixpkgs/pulls/comments/46765520"},"html":{"href":"https://github.com/NixOS/nixpkgs/pull/11484#discussion_r46765520"},"pull_request":{"href":"https://api.github.com/repos/NixOS/nixpkgs/pulls/11484"}}},"pull_request":{"url":"https://api.github.com/repos/NixOS/nixpkgs/pulls/11484","id":52755655,"html_url":"https://github.com/NixOS/nixpkgs/pull/11484","diff_url":"https://github.com/NixOS/nixpkgs/pull/11484.diff","patch_url":"https://github.com/NixOS/nixpkgs/pull/11484.patch","issue_url":"https://api.github.com/repos/NixOS/nixpkgs/issues/11484","number":11484,"state":"open","locked":false,"title":"lib: add toposort, nixos: use toposort for fileSystems to properly support bind and move mounts","user":{"login":"oxij","id":391919,"avatar_url":"https://avatars.githubusercontent.com/u/391919?v=3","gravatar_id":"","url":"https://api.github.com/users/oxij","html_url":"https://github.com/oxij","followers_url":"https://api.github.com/users/oxij/followers","following_url":"https://api.github.com/users/oxij/following{/other_user}","gists_url":"https://api.github.com/users/oxij/gists{/gist_id}","starred_url":"https://api.github.com/users/oxij/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/oxij/subscriptions","organizations_url":"https://api.github.com/users/oxij/orgs","repos_url":"https://api.github.com/users/oxij/repos","events_url":"https://api.github.com/users/oxij/events{/privacy}","received_events_url":"https://api.github.com/users/oxij/received_events","type":"User","site_admin":false},"body":"","created_at":"2015-12-05T14:11:43Z","updated_at":"2015-12-06T01:41:01Z","closed_at":null,"merged_at":null,"merge_commit_sha":"d78490e64bba1366f44e63d56d13f22a611b12fc","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/NixOS/nixpkgs/pulls/11484/commits","review_comments_url":"https://api.github.com/repos/NixOS/nixpkgs/pulls/11484/comments","review_comment_url":"https://api.github.com/repos/NixOS/nixpkgs/pulls/comments{/number}","comments_url":"https://api.github.com/repos/NixOS/nixpkgs/issues/11484/comments","statuses_url":"https://api.github.com/repos/NixOS/nixpkgs/statuses/39f00bf273348eca63c638c955811aeb3a0f4697","head":{"label":"oxij:nixos-toposort-filesystems","ref":"nixos-toposort-filesystems","sha":"39f00bf273348eca63c638c955811aeb3a0f4697","user":{"login":"oxij","id":391919,"avatar_url":"https://avatars.githubusercontent.com/u/391919?v=3","gravatar_id":"","url":"https://api.github.com/users/oxij","html_url":"https://github.com/oxij","followers_url":"https://api.github.com/users/oxij/followers","following_url":"https://api.github.com/users/oxij/following{/other_user}","gists_url":"https://api.github.com/users/oxij/gists{/gist_id}","starred_url":"https://api.github.com/users/oxij/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/oxij/subscriptions","organizations_url":"https://api.github.com/users/oxij/orgs","repos_url":"https://api.github.com/users/oxij/repos","events_url":"https://api.github.com/users/oxij/events{/privacy}","received_events_url":"https://api.github.com/users/oxij/received_events","type":"User","site_admin":false},"repo":{"id":4931866,"name":"nixpkgs","full_name":"oxij/nixpkgs","owner":{"login":"oxij","id":391919,"avatar_url":"https://avatars.githubusercontent.com/u/391919?v=3","gravatar_id":"","url":"https://api.github.com/users/oxij","html_url":"https://github.com/oxij","followers_url":"https://api.github.com/users/oxij/followers","following_url":"https://api.github.com/users/oxij/following{/other_user}","gists_url":"https://api.github.com/users/oxij/gists{/gist_id}","starred_url":"https://api.github.com/users/oxij/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/oxij/subscriptions","organizations_url":"https://api.github.com/users/oxij/orgs","repos_url":"https://api.github.com/users/oxij/repos","events_url":"https://api.github.com/users/oxij/events{/privacy}","received_events_url":"https://api.github.com/users/oxij/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/oxij/nixpkgs","description":"Nix Packages collection","fork":true,"url":"https://api.github.com/repos/oxij/nixpkgs","forks_url":"https://api.github.com/repos/oxij/nixpkgs/forks","keys_url":"https://api.github.com/repos/oxij/nixpkgs/keys{/key_id}","collaborators_url":"https://api.github.com/repos/oxij/nixpkgs/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/oxij/nixpkgs/teams","hooks_url":"https://api.github.com/repos/oxij/nixpkgs/hooks","issue_events_url":"https://api.github.com/repos/oxij/nixpkgs/issues/events{/number}","events_url":"https://api.github.com/repos/oxij/nixpkgs/events","assignees_url":"https://api.github.com/repos/oxij/nixpkgs/assignees{/user}","branches_url":"https://api.github.com/repos/oxij/nixpkgs/branches{/branch}","tags_url":"https://api.github.com/repos/oxij/nixpkgs/tags","blobs_url":"https://api.github.com/repos/oxij/nixpkgs/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/oxij/nixpkgs/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/oxij/nixpkgs/git/refs{/sha}","trees_url":"https://api.github.com/repos/oxij/nixpkgs/git/trees{/sha}","statuses_url":"https://api.github.com/repos/oxij/nixpkgs/statuses/{sha}","languages_url":"https://api.github.com/repos/oxij/nixpkgs/languages","stargazers_url":"https://api.github.com/repos/oxij/nixpkgs/stargazers","contributors_url":"https://api.github.com/repos/oxij/nixpkgs/contributors","subscribers_url":"https://api.github.com/repos/oxij/nixpkgs/subscribers","subscription_url":"https://api.github.com/repos/oxij/nixpkgs/subscription","commits_url":"https://api.github.com/repos/oxij/nixpkgs/commits{/sha}","git_commits_url":"https://api.github.com/repos/oxij/nixpkgs/git/commits{/sha}","comments_url":"https://api.github.com/repos/oxij/nixpkgs/comments{/number}","issue_comment_url":"https://api.github.com/repos/oxij/nixpkgs/issues/comments{/number}","contents_url":"https://api.github.com/repos/oxij/nixpkgs/contents/{+path}","compare_url":"https://api.github.com/repos/oxij/nixpkgs/compare/{base}...{head}","merges_url":"https://api.github.com/repos/oxij/nixpkgs/merges","archive_url":"https://api.github.com/repos/oxij/nixpkgs/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/oxij/nixpkgs/downloads","issues_url":"https://api.github.com/repos/oxij/nixpkgs/issues{/number}","pulls_url":"https://api.github.com/repos/oxij/nixpkgs/pulls{/number}","milestones_url":"https://api.github.com/repos/oxij/nixpkgs/milestones{/number}","notifications_url":"https://api.github.com/repos/oxij/nixpkgs/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/oxij/nixpkgs/labels{/name}","releases_url":"https://api.github.com/repos/oxij/nixpkgs/releases{/id}","created_at":"2012-07-06T22:22:29Z","updated_at":"2014-06-13T00:57:56Z","pushed_at":"2015-12-05T15:33:45Z","git_url":"git://github.com/oxij/nixpkgs.git","ssh_url":"git@github.com:oxij/nixpkgs.git","clone_url":"https://github.com/oxij/nixpkgs.git","svn_url":"https://github.com/oxij/nixpkgs","homepage":null,"size":299966,"stargazers_count":1,"watchers_count":1,"language":"Shell","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":1,"default_branch":"master"}},"base":{"label":"NixOS:master","ref":"master","sha":"2a3e9dfdd458d83062cbe2902fdb672619259fc4","user":{"login":"NixOS","id":487568,"avatar_url":"https://avatars.githubusercontent.com/u/487568?v=3","gravatar_id":"","url":"https://api.github.com/users/NixOS","html_url":"https://github.com/NixOS","followers_url":"https://api.github.com/users/NixOS/followers","following_url":"https://api.github.com/users/NixOS/following{/other_user}","gists_url":"https://api.github.com/users/NixOS/gists{/gist_id}","starred_url":"https://api.github.com/users/NixOS/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/NixOS/subscriptions","organizations_url":"https://api.github.com/users/NixOS/orgs","repos_url":"https://api.github.com/users/NixOS/repos","events_url":"https://api.github.com/users/NixOS/events{/privacy}","received_events_url":"https://api.github.com/users/NixOS/received_events","type":"Organization","site_admin":false},"repo":{"id":4542716,"name":"nixpkgs","full_name":"NixOS/nixpkgs","owner":{"login":"NixOS","id":487568,"avatar_url":"https://avatars.githubusercontent.com/u/487568?v=3","gravatar_id":"","url":"https://api.github.com/users/NixOS","html_url":"https://github.com/NixOS","followers_url":"https://api.github.com/users/NixOS/followers","following_url":"https://api.github.com/users/NixOS/following{/other_user}","gists_url":"https://api.github.com/users/NixOS/gists{/gist_id}","starred_url":"https://api.github.com/users/NixOS/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/NixOS/subscriptions","organizations_url":"https://api.github.com/users/NixOS/orgs","repos_url":"https://api.github.com/users/NixOS/repos","events_url":"https://api.github.com/users/NixOS/events{/privacy}","received_events_url":"https://api.github.com/users/NixOS/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/NixOS/nixpkgs","description":"Nix Packages collection","fork":false,"url":"https://api.github.com/repos/NixOS/nixpkgs","forks_url":"https://api.github.com/repos/NixOS/nixpkgs/forks","keys_url":"https://api.github.com/repos/NixOS/nixpkgs/keys{/key_id}","collaborators_url":"https://api.github.com/repos/NixOS/nixpkgs/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/NixOS/nixpkgs/teams","hooks_url":"https://api.github.com/repos/NixOS/nixpkgs/hooks","issue_events_url":"https://api.github.com/repos/NixOS/nixpkgs/issues/events{/number}","events_url":"https://api.github.com/repos/NixOS/nixpkgs/events","assignees_url":"https://api.github.com/repos/NixOS/nixpkgs/assignees{/user}","branches_url":"https://api.github.com/repos/NixOS/nixpkgs/branches{/branch}","tags_url":"https://api.github.com/repos/NixOS/nixpkgs/tags","blobs_url":"https://api.github.com/repos/NixOS/nixpkgs/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/NixOS/nixpkgs/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/NixOS/nixpkgs/git/refs{/sha}","trees_url":"https://api.github.com/repos/NixOS/nixpkgs/git/trees{/sha}","statuses_url":"https://api.github.com/repos/NixOS/nixpkgs/statuses/{sha}","languages_url":"https://api.github.com/repos/NixOS/nixpkgs/languages","stargazers_url":"https://api.github.com/repos/NixOS/nixpkgs/stargazers","contributors_url":"https://api.github.com/repos/NixOS/nixpkgs/contributors","subscribers_url":"https://api.github.com/repos/NixOS/nixpkgs/subscribers","subscription_url":"https://api.github.com/repos/NixOS/nixpkgs/subscription","commits_url":"https://api.github.com/repos/NixOS/nixpkgs/commits{/sha}","git_commits_url":"https://api.github.com/repos/NixOS/nixpkgs/git/commits{/sha}","comments_url":"https://api.github.com/repos/NixOS/nixpkgs/comments{/number}","issue_comment_url":"https://api.github.com/repos/NixOS/nixpkgs/issues/comments{/number}","contents_url":"https://api.github.com/repos/NixOS/nixpkgs/contents/{+path}","compare_url":"https://api.github.com/repos/NixOS/nixpkgs/compare/{base}...{head}","merges_url":"https://api.github.com/repos/NixOS/nixpkgs/merges","archive_url":"https://api.github.com/repos/NixOS/nixpkgs/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/NixOS/nixpkgs/downloads","issues_url":"https://api.github.com/repos/NixOS/nixpkgs/issues{/number}","pulls_url":"https://api.github.com/repos/NixOS/nixpkgs/pulls{/number}","milestones_url":"https://api.github.com/repos/NixOS/nixpkgs/milestones{/number}","notifications_url":"https://api.github.com/repos/NixOS/nixpkgs/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/NixOS/nixpkgs/labels{/name}","releases_url":"https://api.github.com/repos/NixOS/nixpkgs/releases{/id}","created_at":"2012-06-04T02:49:46Z","updated_at":"2015-12-05T20:52:11Z","pushed_at":"2015-12-05T23:41:09Z","git_url":"git://github.com/NixOS/nixpkgs.git","ssh_url":"git@github.com:NixOS/nixpkgs.git","clone_url":"https://github.com/NixOS/nixpkgs.git","svn_url":"https://github.com/NixOS/nixpkgs","homepage":null,"size":305670,"stargazers_count":859,"watchers_count":859,"language":"Nix","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":1148,"mirror_url":null,"open_issues_count":1100,"forks":1148,"open_issues":1100,"watchers":859,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/NixOS/nixpkgs/pulls/11484"},"html":{"href":"https://github.com/NixOS/nixpkgs/pull/11484"},"issue":{"href":"https://api.github.com/repos/NixOS/nixpkgs/issues/11484"},"comments":{"href":"https://api.github.com/repos/NixOS/nixpkgs/issues/11484/comments"},"review_comments":{"href":"https://api.github.com/repos/NixOS/nixpkgs/pulls/11484/comments"},"review_comment":{"href":"https://api.github.com/repos/NixOS/nixpkgs/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/NixOS/nixpkgs/pulls/11484/commits"},"statuses":{"href":"https://api.github.com/repos/NixOS/nixpkgs/statuses/39f00bf273348eca63c638c955811aeb3a0f4697"}}}}