{"action":"created","comment":{"url":"https://api.github.com/repos/flix/flix/pulls/comments/109179142","pull_request_review_id":30267549,"id":109179142,"diff_hunk":"@@ -18,29 +18,207 @@ package ca.uwaterloo.flix.language.phase\n \n import ca.uwaterloo.flix.api.Flix\n import ca.uwaterloo.flix.language.CompilationError\n-import ca.uwaterloo.flix.language.ast.SimplifiedAst\n+import ca.uwaterloo.flix.language.ast.{SimplifiedAst, Symbol}\n+import ca.uwaterloo.flix.language.ast.SimplifiedAst.{Expression, Definition}\n import ca.uwaterloo.flix.util.Validation\n import ca.uwaterloo.flix.util.Validation._\n \n+import scala.collection.mutable\n+\n /**\n   * The Tree Shaking phase removes all unused function definitions.\n   *\n   * A function is considered reachable if it:\n   *\n   * (a) Appears in the global namespaces, takes zero arguments, and is not marked as synthetic.\n   * (b) Appears in a fact or a rule as a filter/transfer function.\n-  * (c) Appears in a function which itself is reachable.\n+  * (c) Appears in a lattice declaration.\n+  * (d) Appears in a function which itself is reachable.\n   */\n+\n object TreeShaker extends Phase[SimplifiedAst.Root, SimplifiedAst.Root] {\n \n   /**\n     * Performs tree shaking on the given AST `root`.\n     */\n   def run(root: SimplifiedAst.Root)(implicit flix: Flix): Validation[SimplifiedAst.Root, CompilationError] = {\n \n-    // TODO: Implement.\n+    /**\n+      * A queue of function definitions to be processed recursively.\n+      *\n+      * For example, if the queue contains the entry:\n+      *\n+      * -   f\n+      *\n+      * it means that the function definition f should be considered to determine new reachable functions.\n+      */\n+    val queue: mutable.Queue[Definition.Constant] = mutable.Queue.empty\n+\n+    /**\n+      * A map used to collect reachable functions (symbols and the corresponding definitions).\n+      */\n+    val reachableFunctions: mutable.Map[Symbol.DefnSym, Definition.Constant] = mutable.Map.empty\n+\n+    /**\n+      * Returns true iff the function definition `defn` is initially reachable by (a).\n+      *\n+      * That is, returns true iff `defn` satisfies:\n+      *\n+      *   (a) Appears in the global namespaces, takes zero arguments, and is not marked as synthetic.\n+      */\n+    def isReachableRoot(defn: Definition.Constant): Boolean = {\n+      defn.sym.namespace.isEmpty && defn.formals.isEmpty && !defn.isSynthetic\n+    }\n+\n+    /**\n+      * Searches the given SimplifiedAst.Term.Head `head` for reachable functions.\n+      */\n+    def visitTermHead(head: SimplifiedAst.Term.Head): Unit = {\n+      head match {\n+        case SimplifiedAst.Term.Head.Lit(lit, tpe, loc) => visitExp(lit)\n+        case SimplifiedAst.Term.Head.App(sym, args, tpe, loc) => newDefinitionSymbol(sym)\n+        case _ =>\n+      }\n+    }\n+\n+    /**\n+      * Searches the given SimplifiedAst.Term.Body `body` for reachable functions.\n+      */\n+    def visitTermBody(body: SimplifiedAst.Term.Body): Unit = {\n+      body match {\n+        case SimplifiedAst.Term.Body.Lit(exp, tpe, loc) => visitExp(exp)\n+        case _ =>\n+      }\n+    }\n+\n+    /**\n+      * Searches the given Expression `e0` for reachable functions.\n+      */\n+    def visitExp(e0: Expression): Unit =  e0 match {","path":"main/src/ca/uwaterloo/flix/language/phase/TreeShaker.scala","position":83,"original_position":83,"commit_id":"414a39ee4c3dcb7b7cddfc222593e21d7929574e","original_commit_id":"414a39ee4c3dcb7b7cddfc222593e21d7929574e","user":{"login":"magnus-madsen","id":2287953,"avatar_url":"https://avatars1.githubusercontent.com/u/2287953?v=3","gravatar_id":"","url":"https://api.github.com/users/magnus-madsen","html_url":"https://github.com/magnus-madsen","followers_url":"https://api.github.com/users/magnus-madsen/followers","following_url":"https://api.github.com/users/magnus-madsen/following{/other_user}","gists_url":"https://api.github.com/users/magnus-madsen/gists{/gist_id}","starred_url":"https://api.github.com/users/magnus-madsen/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/magnus-madsen/subscriptions","organizations_url":"https://api.github.com/users/magnus-madsen/orgs","repos_url":"https://api.github.com/users/magnus-madsen/repos","events_url":"https://api.github.com/users/magnus-madsen/events{/privacy}","received_events_url":"https://api.github.com/users/magnus-madsen/received_events","type":"User","site_admin":false},"body":"As before, I suggest that this returns a set of symbols.","created_at":"2017-03-31T14:57:51Z","updated_at":"2017-03-31T14:57:51Z","html_url":"https://github.com/flix/flix/pull/400#discussion_r109179142","pull_request_url":"https://api.github.com/repos/flix/flix/pulls/400","_links":{"self":{"href":"https://api.github.com/repos/flix/flix/pulls/comments/109179142"},"html":{"href":"https://github.com/flix/flix/pull/400#discussion_r109179142"},"pull_request":{"href":"https://api.github.com/repos/flix/flix/pulls/400"}}},"pull_request":{"url":"https://api.github.com/repos/flix/flix/pulls/400","id":112611998,"html_url":"https://github.com/flix/flix/pull/400","diff_url":"https://github.com/flix/flix/pull/400.diff","patch_url":"https://github.com/flix/flix/pull/400.patch","issue_url":"https://api.github.com/repos/flix/flix/issues/400","number":400,"state":"open","locked":false,"title":"Tree Shaking: Initial Progress and Questions","user":{"login":"liampalmer43","id":11587127,"avatar_url":"https://avatars2.githubusercontent.com/u/11587127?v=3","gravatar_id":"","url":"https://api.github.com/users/liampalmer43","html_url":"https://github.com/liampalmer43","followers_url":"https://api.github.com/users/liampalmer43/followers","following_url":"https://api.github.com/users/liampalmer43/following{/other_user}","gists_url":"https://api.github.com/users/liampalmer43/gists{/gist_id}","starred_url":"https://api.github.com/users/liampalmer43/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/liampalmer43/subscriptions","organizations_url":"https://api.github.com/users/liampalmer43/orgs","repos_url":"https://api.github.com/users/liampalmer43/repos","events_url":"https://api.github.com/users/liampalmer43/events{/privacy}","received_events_url":"https://api.github.com/users/liampalmer43/received_events","type":"User","site_admin":false},"body":"- Initial progress on the `TreeShaking` phase.","created_at":"2017-03-26T02:49:52Z","updated_at":"2017-03-31T14:57:51Z","closed_at":null,"merged_at":null,"merge_commit_sha":"59a123b35a2030d6d463bcf057f914ad31ae49ce","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/flix/flix/pulls/400/commits","review_comments_url":"https://api.github.com/repos/flix/flix/pulls/400/comments","review_comment_url":"https://api.github.com/repos/flix/flix/pulls/comments{/number}","comments_url":"https://api.github.com/repos/flix/flix/issues/400/comments","statuses_url":"https://api.github.com/repos/flix/flix/statuses/414a39ee4c3dcb7b7cddfc222593e21d7929574e","head":{"label":"liampalmer43:master","ref":"master","sha":"414a39ee4c3dcb7b7cddfc222593e21d7929574e","user":{"login":"liampalmer43","id":11587127,"avatar_url":"https://avatars2.githubusercontent.com/u/11587127?v=3","gravatar_id":"","url":"https://api.github.com/users/liampalmer43","html_url":"https://github.com/liampalmer43","followers_url":"https://api.github.com/users/liampalmer43/followers","following_url":"https://api.github.com/users/liampalmer43/following{/other_user}","gists_url":"https://api.github.com/users/liampalmer43/gists{/gist_id}","starred_url":"https://api.github.com/users/liampalmer43/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/liampalmer43/subscriptions","organizations_url":"https://api.github.com/users/liampalmer43/orgs","repos_url":"https://api.github.com/users/liampalmer43/repos","events_url":"https://api.github.com/users/liampalmer43/events{/privacy}","received_events_url":"https://api.github.com/users/liampalmer43/received_events","type":"User","site_admin":false},"repo":{"id":68549624,"name":"flix","full_name":"liampalmer43/flix","owner":{"login":"liampalmer43","id":11587127,"avatar_url":"https://avatars2.githubusercontent.com/u/11587127?v=3","gravatar_id":"","url":"https://api.github.com/users/liampalmer43","html_url":"https://github.com/liampalmer43","followers_url":"https://api.github.com/users/liampalmer43/followers","following_url":"https://api.github.com/users/liampalmer43/following{/other_user}","gists_url":"https://api.github.com/users/liampalmer43/gists{/gist_id}","starred_url":"https://api.github.com/users/liampalmer43/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/liampalmer43/subscriptions","organizations_url":"https://api.github.com/users/liampalmer43/orgs","repos_url":"https://api.github.com/users/liampalmer43/repos","events_url":"https://api.github.com/users/liampalmer43/events{/privacy}","received_events_url":"https://api.github.com/users/liampalmer43/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/liampalmer43/flix","description":"The Flix Programming Language","fork":true,"url":"https://api.github.com/repos/liampalmer43/flix","forks_url":"https://api.github.com/repos/liampalmer43/flix/forks","keys_url":"https://api.github.com/repos/liampalmer43/flix/keys{/key_id}","collaborators_url":"https://api.github.com/repos/liampalmer43/flix/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/liampalmer43/flix/teams","hooks_url":"https://api.github.com/repos/liampalmer43/flix/hooks","issue_events_url":"https://api.github.com/repos/liampalmer43/flix/issues/events{/number}","events_url":"https://api.github.com/repos/liampalmer43/flix/events","assignees_url":"https://api.github.com/repos/liampalmer43/flix/assignees{/user}","branches_url":"https://api.github.com/repos/liampalmer43/flix/branches{/branch}","tags_url":"https://api.github.com/repos/liampalmer43/flix/tags","blobs_url":"https://api.github.com/repos/liampalmer43/flix/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/liampalmer43/flix/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/liampalmer43/flix/git/refs{/sha}","trees_url":"https://api.github.com/repos/liampalmer43/flix/git/trees{/sha}","statuses_url":"https://api.github.com/repos/liampalmer43/flix/statuses/{sha}","languages_url":"https://api.github.com/repos/liampalmer43/flix/languages","stargazers_url":"https://api.github.com/repos/liampalmer43/flix/stargazers","contributors_url":"https://api.github.com/repos/liampalmer43/flix/contributors","subscribers_url":"https://api.github.com/repos/liampalmer43/flix/subscribers","subscription_url":"https://api.github.com/repos/liampalmer43/flix/subscription","commits_url":"https://api.github.com/repos/liampalmer43/flix/commits{/sha}","git_commits_url":"https://api.github.com/repos/liampalmer43/flix/git/commits{/sha}","comments_url":"https://api.github.com/repos/liampalmer43/flix/comments{/number}","issue_comment_url":"https://api.github.com/repos/liampalmer43/flix/issues/comments{/number}","contents_url":"https://api.github.com/repos/liampalmer43/flix/contents/{+path}","compare_url":"https://api.github.com/repos/liampalmer43/flix/compare/{base}...{head}","merges_url":"https://api.github.com/repos/liampalmer43/flix/merges","archive_url":"https://api.github.com/repos/liampalmer43/flix/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/liampalmer43/flix/downloads","issues_url":"https://api.github.com/repos/liampalmer43/flix/issues{/number}","pulls_url":"https://api.github.com/repos/liampalmer43/flix/pulls{/number}","milestones_url":"https://api.github.com/repos/liampalmer43/flix/milestones{/number}","notifications_url":"https://api.github.com/repos/liampalmer43/flix/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/liampalmer43/flix/labels{/name}","releases_url":"https://api.github.com/repos/liampalmer43/flix/releases{/id}","deployments_url":"https://api.github.com/repos/liampalmer43/flix/deployments","created_at":"2016-09-18T22:01:24Z","updated_at":"2016-09-18T22:01:25Z","pushed_at":"2017-03-29T23:52:07Z","git_url":"git://github.com/liampalmer43/flix.git","ssh_url":"git@github.com:liampalmer43/flix.git","clone_url":"https://github.com/liampalmer43/flix.git","svn_url":"https://github.com/liampalmer43/flix","homepage":"http://flix.github.io","size":48844,"stargazers_count":0,"watchers_count":0,"language":"Scala","has_issues":false,"has_projects":true,"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":"flix:master","ref":"master","sha":"863b933269ac463b556ff3adead70aab1e375cf3","user":{"login":"flix","id":16831634,"avatar_url":"https://avatars0.githubusercontent.com/u/16831634?v=3","gravatar_id":"","url":"https://api.github.com/users/flix","html_url":"https://github.com/flix","followers_url":"https://api.github.com/users/flix/followers","following_url":"https://api.github.com/users/flix/following{/other_user}","gists_url":"https://api.github.com/users/flix/gists{/gist_id}","starred_url":"https://api.github.com/users/flix/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/flix/subscriptions","organizations_url":"https://api.github.com/users/flix/orgs","repos_url":"https://api.github.com/users/flix/repos","events_url":"https://api.github.com/users/flix/events{/privacy}","received_events_url":"https://api.github.com/users/flix/received_events","type":"Organization","site_admin":false},"repo":{"id":37299718,"name":"flix","full_name":"flix/flix","owner":{"login":"flix","id":16831634,"avatar_url":"https://avatars0.githubusercontent.com/u/16831634?v=3","gravatar_id":"","url":"https://api.github.com/users/flix","html_url":"https://github.com/flix","followers_url":"https://api.github.com/users/flix/followers","following_url":"https://api.github.com/users/flix/following{/other_user}","gists_url":"https://api.github.com/users/flix/gists{/gist_id}","starred_url":"https://api.github.com/users/flix/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/flix/subscriptions","organizations_url":"https://api.github.com/users/flix/orgs","repos_url":"https://api.github.com/users/flix/repos","events_url":"https://api.github.com/users/flix/events{/privacy}","received_events_url":"https://api.github.com/users/flix/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/flix/flix","description":"The Flix Programming Language","fork":false,"url":"https://api.github.com/repos/flix/flix","forks_url":"https://api.github.com/repos/flix/flix/forks","keys_url":"https://api.github.com/repos/flix/flix/keys{/key_id}","collaborators_url":"https://api.github.com/repos/flix/flix/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/flix/flix/teams","hooks_url":"https://api.github.com/repos/flix/flix/hooks","issue_events_url":"https://api.github.com/repos/flix/flix/issues/events{/number}","events_url":"https://api.github.com/repos/flix/flix/events","assignees_url":"https://api.github.com/repos/flix/flix/assignees{/user}","branches_url":"https://api.github.com/repos/flix/flix/branches{/branch}","tags_url":"https://api.github.com/repos/flix/flix/tags","blobs_url":"https://api.github.com/repos/flix/flix/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/flix/flix/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/flix/flix/git/refs{/sha}","trees_url":"https://api.github.com/repos/flix/flix/git/trees{/sha}","statuses_url":"https://api.github.com/repos/flix/flix/statuses/{sha}","languages_url":"https://api.github.com/repos/flix/flix/languages","stargazers_url":"https://api.github.com/repos/flix/flix/stargazers","contributors_url":"https://api.github.com/repos/flix/flix/contributors","subscribers_url":"https://api.github.com/repos/flix/flix/subscribers","subscription_url":"https://api.github.com/repos/flix/flix/subscription","commits_url":"https://api.github.com/repos/flix/flix/commits{/sha}","git_commits_url":"https://api.github.com/repos/flix/flix/git/commits{/sha}","comments_url":"https://api.github.com/repos/flix/flix/comments{/number}","issue_comment_url":"https://api.github.com/repos/flix/flix/issues/comments{/number}","contents_url":"https://api.github.com/repos/flix/flix/contents/{+path}","compare_url":"https://api.github.com/repos/flix/flix/compare/{base}...{head}","merges_url":"https://api.github.com/repos/flix/flix/merges","archive_url":"https://api.github.com/repos/flix/flix/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/flix/flix/downloads","issues_url":"https://api.github.com/repos/flix/flix/issues{/number}","pulls_url":"https://api.github.com/repos/flix/flix/pulls{/number}","milestones_url":"https://api.github.com/repos/flix/flix/milestones{/number}","notifications_url":"https://api.github.com/repos/flix/flix/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/flix/flix/labels{/name}","releases_url":"https://api.github.com/repos/flix/flix/releases{/id}","deployments_url":"https://api.github.com/repos/flix/flix/deployments","created_at":"2015-06-12T03:20:35Z","updated_at":"2017-03-29T13:01:20Z","pushed_at":"2017-03-31T14:25:55Z","git_url":"git://github.com/flix/flix.git","ssh_url":"git@github.com:flix/flix.git","clone_url":"https://github.com/flix/flix.git","svn_url":"https://github.com/flix/flix","homepage":"http://flix.github.io","size":50662,"stargazers_count":103,"watchers_count":103,"language":"Scala","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":9,"mirror_url":null,"open_issues_count":78,"forks":9,"open_issues":78,"watchers":103,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/flix/flix/pulls/400"},"html":{"href":"https://github.com/flix/flix/pull/400"},"issue":{"href":"https://api.github.com/repos/flix/flix/issues/400"},"comments":{"href":"https://api.github.com/repos/flix/flix/issues/400/comments"},"review_comments":{"href":"https://api.github.com/repos/flix/flix/pulls/400/comments"},"review_comment":{"href":"https://api.github.com/repos/flix/flix/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/flix/flix/pulls/400/commits"},"statuses":{"href":"https://api.github.com/repos/flix/flix/statuses/414a39ee4c3dcb7b7cddfc222593e21d7929574e"}}}}
{"actor":{"display_login":"magnus-madsen"}}