{"action":"created","comment":{"url":"https://api.github.com/repos/yast/yast-nfs-client/pulls/comments/27649601","id":27649601,"diff_hunk":"@@ -0,0 +1,137 @@\n+/**\n+ * File:\n+ *   toposort.ycp\n+ *\n+ * Module:\n+ *   System Services (Runlevel) (formerly known as Runlevel Editor)\n+ *\n+ * Summary:\n+ *   Topological sorting for script dependencies\n+ *\n+ * Authors:\n+ *   Martin Vidner <mvidner@suse.cz>\n+ *\n+ * $Id$\n+ */\n+\n+{\n+    import \"Map\";\n+    import \"String\";\n+\n+    /**\n+     * Topologically sort a directed acyclic graph, ie. linearize a\n+     * partial ordering.\n+     * (what if the graph is a multigraph??)\n+     * @param dag A DAG as a map:\n+     *  nodes are keys, values are lists of nodes that are reached\n+     *  by an edge from the respective key.\n+     * @return [out, rest]<br>\n+     *  out: a list containing the keys of the map in topological order<br>\n+     *  rest: a list, empty if the graph was acyclic, otherwise it is\n+     *   a superset of the nodes forming the cycle\n+     *   and \"out\" is a partial result\n+     */\n+    define list< list<string> > TopologicalSort (map<string, list<string> > dag) {\n+        list<string> out = [];\n+        map<string, integer> in_degree =\n+            (map<string, integer>) mapmap (string vertex, list<string> targets,\n+                                           dag,\n+                                           ``($[vertex: 0]));\n+        foreach (string vertex, list<string> targets, dag, ``{\n+            foreach (string target, targets, ``{\n+                in_degree[target] = in_degree[target]:0 + 1;\n+            });\n+        });\n+\n+        while (size (in_degree) > 0)\n+        {\n+            // get the vertices that can go next because they have zero in degree\n+            map<string, integer> next_m =\n+                (map<string, integer>) filter (string vertex, integer d,\n+                                               in_degree,\n+                                               ``(d == 0));\n+            if (size (next_m) == 0)\n+            {\n+                // the graph is cyclic!\n+                break;\n+            }\n+            foreach (string vertex, integer dummy, next_m, ``{\n+                out = add(out, vertex);\n+            });\n+            // remove the vertices\n+            in_degree = (map<string, integer>) filter (string vertex, integer d,\n+                                                       in_degree,\n+                                                       ``(d != 0));\n+            // remove the edges that were leading from them\n+            foreach (string vertex, integer dummy, next_m, ``{\n+                foreach (string target, dag[vertex]:[], ``{\n+                    in_degree[target] = in_degree[target]:0 - 1;\n+                });\n+            });\n+        }\n+\n+        list<string> rest = (list<string>) maplist (string k, integer v, in_degree, ``( k )); //mapkeys\n+        if (size (rest) > 0)\n+        {\n+            y2error (\"Cyclic subgraph found, remainder has %1 nodes: %2\",\n+                     size (rest), rest);\n+        }\n+        return [out, rest];\n+    }\n+\n+    /**\n+     * TopologicalSort as implemented above only works on graphs\n+     * with string vertices.\n+     * Now we will\n+     * 1. generalize it to arbitrary data (\"things\")\n+     * 2. exploit the order of keys in map<string, ...> to produce a *stable*\n+     *    topological sort (one that preserves the order of unrelated vertices)\n+     */\n+    typedef any thing_t;","path":"src/include/nfs/toposort.ycp","position":90,"original_position":90,"commit_id":"bb8aea2b897ac7378b297b4c203c5b0b819c75fd","original_commit_id":"bb8aea2b897ac7378b297b4c203c5b0b819c75fd","user":{"login":"mvidner","id":102056,"avatar_url":"https://avatars.githubusercontent.com/u/102056?v=3","gravatar_id":"","url":"https://api.github.com/users/mvidner","html_url":"https://github.com/mvidner","followers_url":"https://api.github.com/users/mvidner/followers","following_url":"https://api.github.com/users/mvidner/following{/other_user}","gists_url":"https://api.github.com/users/mvidner/gists{/gist_id}","starred_url":"https://api.github.com/users/mvidner/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mvidner/subscriptions","organizations_url":"https://api.github.com/users/mvidner/orgs","repos_url":"https://api.github.com/users/mvidner/repos","events_url":"https://api.github.com/users/mvidner/events{/privacy}","received_events_url":"https://api.github.com/users/mvidner/received_events","type":"User","site_admin":false},"body":"It can be anything, as long as all of the anythings are of the same type in here:\r\n```cpp\r\n list<list<thing_t> > StableTopologicalSort(list<thing_t> things,  boolean(thing_t, thing_t) edge);\r\n```\r\n\r\nIt is a hint that those `any` are related, as opposed to this:\r\n```cpp\r\nany GenericBinaryFunction(any a, any b);\r\n```","created_at":"2015-04-02T11:37:48Z","updated_at":"2015-04-02T11:37:48Z","html_url":"https://github.com/yast/yast-nfs-client/pull/43#discussion_r27649601","pull_request_url":"https://api.github.com/repos/yast/yast-nfs-client/pulls/43","_links":{"self":{"href":"https://api.github.com/repos/yast/yast-nfs-client/pulls/comments/27649601"},"html":{"href":"https://github.com/yast/yast-nfs-client/pull/43#discussion_r27649601"},"pull_request":{"href":"https://api.github.com/repos/yast/yast-nfs-client/pulls/43"}}},"pull_request":{"url":"https://api.github.com/repos/yast/yast-nfs-client/pulls/43","id":32303669,"html_url":"https://github.com/yast/yast-nfs-client/pull/43","diff_url":"https://github.com/yast/yast-nfs-client/pull/43.diff","patch_url":"https://github.com/yast/yast-nfs-client/pull/43.patch","issue_url":"https://api.github.com/repos/yast/yast-nfs-client/issues/43","number":43,"state":"open","locked":false,"title":"Fix fstab reordering (L3 bsc#922307)","user":{"login":"mvidner","id":102056,"avatar_url":"https://avatars.githubusercontent.com/u/102056?v=3","gravatar_id":"","url":"https://api.github.com/users/mvidner","html_url":"https://github.com/mvidner","followers_url":"https://api.github.com/users/mvidner/followers","following_url":"https://api.github.com/users/mvidner/following{/other_user}","gists_url":"https://api.github.com/users/mvidner/gists{/gist_id}","starred_url":"https://api.github.com/users/mvidner/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mvidner/subscriptions","organizations_url":"https://api.github.com/users/mvidner/orgs","repos_url":"https://api.github.com/users/mvidner/repos","events_url":"https://api.github.com/users/mvidner/events{/privacy}","received_events_url":"https://api.github.com/users/mvidner/received_events","type":"User","site_admin":false},"body":"Consider path dependencies between mount points, allowing eg. a local mount on top of an NFS mount point ([bsc#922307](https://bugzilla.suse.com/show_bug.cgi?id=922307)).\r\n\r\nSymlinks are not handled here: they can occur anywhere within a nested mount so handling them is too complex for little benefit (noone has complained so far).\r\n","created_at":"2015-03-31T09:14:41Z","updated_at":"2015-04-02T11:37:48Z","closed_at":null,"merged_at":null,"merge_commit_sha":"b2cdc09c5ed256a930b9ada3e7e34ea83672b88d","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/yast/yast-nfs-client/pulls/43/commits","review_comments_url":"https://api.github.com/repos/yast/yast-nfs-client/pulls/43/comments","review_comment_url":"https://api.github.com/repos/yast/yast-nfs-client/pulls/comments{/number}","comments_url":"https://api.github.com/repos/yast/yast-nfs-client/issues/43/comments","statuses_url":"https://api.github.com/repos/yast/yast-nfs-client/statuses/bb8aea2b897ac7378b297b4c203c5b0b819c75fd","head":{"label":"yast:merge-fstabs","ref":"merge-fstabs","sha":"bb8aea2b897ac7378b297b4c203c5b0b819c75fd","user":{"login":"yast","id":909990,"avatar_url":"https://avatars.githubusercontent.com/u/909990?v=3","gravatar_id":"","url":"https://api.github.com/users/yast","html_url":"https://github.com/yast","followers_url":"https://api.github.com/users/yast/followers","following_url":"https://api.github.com/users/yast/following{/other_user}","gists_url":"https://api.github.com/users/yast/gists{/gist_id}","starred_url":"https://api.github.com/users/yast/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yast/subscriptions","organizations_url":"https://api.github.com/users/yast/orgs","repos_url":"https://api.github.com/users/yast/repos","events_url":"https://api.github.com/users/yast/events{/privacy}","received_events_url":"https://api.github.com/users/yast/received_events","type":"Organization","site_admin":false},"repo":{"id":4368161,"name":"yast-nfs-client","full_name":"yast/yast-nfs-client","owner":{"login":"yast","id":909990,"avatar_url":"https://avatars.githubusercontent.com/u/909990?v=3","gravatar_id":"","url":"https://api.github.com/users/yast","html_url":"https://github.com/yast","followers_url":"https://api.github.com/users/yast/followers","following_url":"https://api.github.com/users/yast/following{/other_user}","gists_url":"https://api.github.com/users/yast/gists{/gist_id}","starred_url":"https://api.github.com/users/yast/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yast/subscriptions","organizations_url":"https://api.github.com/users/yast/orgs","repos_url":"https://api.github.com/users/yast/repos","events_url":"https://api.github.com/users/yast/events{/privacy}","received_events_url":"https://api.github.com/users/yast/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/yast/yast-nfs-client","description":"YaST module nfs-client","fork":false,"url":"https://api.github.com/repos/yast/yast-nfs-client","forks_url":"https://api.github.com/repos/yast/yast-nfs-client/forks","keys_url":"https://api.github.com/repos/yast/yast-nfs-client/keys{/key_id}","collaborators_url":"https://api.github.com/repos/yast/yast-nfs-client/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/yast/yast-nfs-client/teams","hooks_url":"https://api.github.com/repos/yast/yast-nfs-client/hooks","issue_events_url":"https://api.github.com/repos/yast/yast-nfs-client/issues/events{/number}","events_url":"https://api.github.com/repos/yast/yast-nfs-client/events","assignees_url":"https://api.github.com/repos/yast/yast-nfs-client/assignees{/user}","branches_url":"https://api.github.com/repos/yast/yast-nfs-client/branches{/branch}","tags_url":"https://api.github.com/repos/yast/yast-nfs-client/tags","blobs_url":"https://api.github.com/repos/yast/yast-nfs-client/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/yast/yast-nfs-client/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/yast/yast-nfs-client/git/refs{/sha}","trees_url":"https://api.github.com/repos/yast/yast-nfs-client/git/trees{/sha}","statuses_url":"https://api.github.com/repos/yast/yast-nfs-client/statuses/{sha}","languages_url":"https://api.github.com/repos/yast/yast-nfs-client/languages","stargazers_url":"https://api.github.com/repos/yast/yast-nfs-client/stargazers","contributors_url":"https://api.github.com/repos/yast/yast-nfs-client/contributors","subscribers_url":"https://api.github.com/repos/yast/yast-nfs-client/subscribers","subscription_url":"https://api.github.com/repos/yast/yast-nfs-client/subscription","commits_url":"https://api.github.com/repos/yast/yast-nfs-client/commits{/sha}","git_commits_url":"https://api.github.com/repos/yast/yast-nfs-client/git/commits{/sha}","comments_url":"https://api.github.com/repos/yast/yast-nfs-client/comments{/number}","issue_comment_url":"https://api.github.com/repos/yast/yast-nfs-client/issues/comments{/number}","contents_url":"https://api.github.com/repos/yast/yast-nfs-client/contents/{+path}","compare_url":"https://api.github.com/repos/yast/yast-nfs-client/compare/{base}...{head}","merges_url":"https://api.github.com/repos/yast/yast-nfs-client/merges","archive_url":"https://api.github.com/repos/yast/yast-nfs-client/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/yast/yast-nfs-client/downloads","issues_url":"https://api.github.com/repos/yast/yast-nfs-client/issues{/number}","pulls_url":"https://api.github.com/repos/yast/yast-nfs-client/pulls{/number}","milestones_url":"https://api.github.com/repos/yast/yast-nfs-client/milestones{/number}","notifications_url":"https://api.github.com/repos/yast/yast-nfs-client/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/yast/yast-nfs-client/labels{/name}","releases_url":"https://api.github.com/repos/yast/yast-nfs-client/releases{/id}","created_at":"2012-05-18T10:24:52Z","updated_at":"2015-03-04T16:32:13Z","pushed_at":"2015-03-31T14:50:17Z","git_url":"git://github.com/yast/yast-nfs-client.git","ssh_url":"git@github.com:yast/yast-nfs-client.git","clone_url":"https://github.com/yast/yast-nfs-client.git","svn_url":"https://github.com/yast/yast-nfs-client","homepage":"http://en.opensuse.org/Portal:YaST","size":1364,"stargazers_count":2,"watchers_count":2,"language":"Ruby","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":9,"mirror_url":null,"open_issues_count":1,"forks":9,"open_issues":1,"watchers":2,"default_branch":"master"}},"base":{"label":"yast:Code-11-SP3","ref":"Code-11-SP3","sha":"a362df44d6950a9527f870908426ed61d0280f3a","user":{"login":"yast","id":909990,"avatar_url":"https://avatars.githubusercontent.com/u/909990?v=3","gravatar_id":"","url":"https://api.github.com/users/yast","html_url":"https://github.com/yast","followers_url":"https://api.github.com/users/yast/followers","following_url":"https://api.github.com/users/yast/following{/other_user}","gists_url":"https://api.github.com/users/yast/gists{/gist_id}","starred_url":"https://api.github.com/users/yast/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yast/subscriptions","organizations_url":"https://api.github.com/users/yast/orgs","repos_url":"https://api.github.com/users/yast/repos","events_url":"https://api.github.com/users/yast/events{/privacy}","received_events_url":"https://api.github.com/users/yast/received_events","type":"Organization","site_admin":false},"repo":{"id":4368161,"name":"yast-nfs-client","full_name":"yast/yast-nfs-client","owner":{"login":"yast","id":909990,"avatar_url":"https://avatars.githubusercontent.com/u/909990?v=3","gravatar_id":"","url":"https://api.github.com/users/yast","html_url":"https://github.com/yast","followers_url":"https://api.github.com/users/yast/followers","following_url":"https://api.github.com/users/yast/following{/other_user}","gists_url":"https://api.github.com/users/yast/gists{/gist_id}","starred_url":"https://api.github.com/users/yast/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yast/subscriptions","organizations_url":"https://api.github.com/users/yast/orgs","repos_url":"https://api.github.com/users/yast/repos","events_url":"https://api.github.com/users/yast/events{/privacy}","received_events_url":"https://api.github.com/users/yast/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/yast/yast-nfs-client","description":"YaST module nfs-client","fork":false,"url":"https://api.github.com/repos/yast/yast-nfs-client","forks_url":"https://api.github.com/repos/yast/yast-nfs-client/forks","keys_url":"https://api.github.com/repos/yast/yast-nfs-client/keys{/key_id}","collaborators_url":"https://api.github.com/repos/yast/yast-nfs-client/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/yast/yast-nfs-client/teams","hooks_url":"https://api.github.com/repos/yast/yast-nfs-client/hooks","issue_events_url":"https://api.github.com/repos/yast/yast-nfs-client/issues/events{/number}","events_url":"https://api.github.com/repos/yast/yast-nfs-client/events","assignees_url":"https://api.github.com/repos/yast/yast-nfs-client/assignees{/user}","branches_url":"https://api.github.com/repos/yast/yast-nfs-client/branches{/branch}","tags_url":"https://api.github.com/repos/yast/yast-nfs-client/tags","blobs_url":"https://api.github.com/repos/yast/yast-nfs-client/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/yast/yast-nfs-client/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/yast/yast-nfs-client/git/refs{/sha}","trees_url":"https://api.github.com/repos/yast/yast-nfs-client/git/trees{/sha}","statuses_url":"https://api.github.com/repos/yast/yast-nfs-client/statuses/{sha}","languages_url":"https://api.github.com/repos/yast/yast-nfs-client/languages","stargazers_url":"https://api.github.com/repos/yast/yast-nfs-client/stargazers","contributors_url":"https://api.github.com/repos/yast/yast-nfs-client/contributors","subscribers_url":"https://api.github.com/repos/yast/yast-nfs-client/subscribers","subscription_url":"https://api.github.com/repos/yast/yast-nfs-client/subscription","commits_url":"https://api.github.com/repos/yast/yast-nfs-client/commits{/sha}","git_commits_url":"https://api.github.com/repos/yast/yast-nfs-client/git/commits{/sha}","comments_url":"https://api.github.com/repos/yast/yast-nfs-client/comments{/number}","issue_comment_url":"https://api.github.com/repos/yast/yast-nfs-client/issues/comments{/number}","contents_url":"https://api.github.com/repos/yast/yast-nfs-client/contents/{+path}","compare_url":"https://api.github.com/repos/yast/yast-nfs-client/compare/{base}...{head}","merges_url":"https://api.github.com/repos/yast/yast-nfs-client/merges","archive_url":"https://api.github.com/repos/yast/yast-nfs-client/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/yast/yast-nfs-client/downloads","issues_url":"https://api.github.com/repos/yast/yast-nfs-client/issues{/number}","pulls_url":"https://api.github.com/repos/yast/yast-nfs-client/pulls{/number}","milestones_url":"https://api.github.com/repos/yast/yast-nfs-client/milestones{/number}","notifications_url":"https://api.github.com/repos/yast/yast-nfs-client/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/yast/yast-nfs-client/labels{/name}","releases_url":"https://api.github.com/repos/yast/yast-nfs-client/releases{/id}","created_at":"2012-05-18T10:24:52Z","updated_at":"2015-03-04T16:32:13Z","pushed_at":"2015-03-31T14:50:17Z","git_url":"git://github.com/yast/yast-nfs-client.git","ssh_url":"git@github.com:yast/yast-nfs-client.git","clone_url":"https://github.com/yast/yast-nfs-client.git","svn_url":"https://github.com/yast/yast-nfs-client","homepage":"http://en.opensuse.org/Portal:YaST","size":1364,"stargazers_count":2,"watchers_count":2,"language":"Ruby","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":9,"mirror_url":null,"open_issues_count":1,"forks":9,"open_issues":1,"watchers":2,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/yast/yast-nfs-client/pulls/43"},"html":{"href":"https://github.com/yast/yast-nfs-client/pull/43"},"issue":{"href":"https://api.github.com/repos/yast/yast-nfs-client/issues/43"},"comments":{"href":"https://api.github.com/repos/yast/yast-nfs-client/issues/43/comments"},"review_comments":{"href":"https://api.github.com/repos/yast/yast-nfs-client/pulls/43/comments"},"review_comment":{"href":"https://api.github.com/repos/yast/yast-nfs-client/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/yast/yast-nfs-client/pulls/43/commits"},"statuses":{"href":"https://api.github.com/repos/yast/yast-nfs-client/statuses/bb8aea2b897ac7378b297b4c203c5b0b819c75fd"}}}}