{"action":"opened","issue":{"url":"https://api.github.com/repos/swift-lang/swift-t/issues/4","labels_url":"https://api.github.com/repos/swift-lang/swift-t/issues/4/labels{/name}","comments_url":"https://api.github.com/repos/swift-lang/swift-t/issues/4/comments","events_url":"https://api.github.com/repos/swift-lang/swift-t/issues/4/events","html_url":"https://github.com/swift-lang/swift-t/issues/4","id":70233569,"number":4,"title":"Circular dependency detection in parser","user":{"login":"jmjwozniak","id":2934178,"avatar_url":"https://avatars.githubusercontent.com/u/2934178?v=3","gravatar_id":"","url":"https://api.github.com/users/jmjwozniak","html_url":"https://github.com/jmjwozniak","followers_url":"https://api.github.com/users/jmjwozniak/followers","following_url":"https://api.github.com/users/jmjwozniak/following{/other_user}","gists_url":"https://api.github.com/users/jmjwozniak/gists{/gist_id}","starred_url":"https://api.github.com/users/jmjwozniak/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jmjwozniak/subscriptions","organizations_url":"https://api.github.com/users/jmjwozniak/orgs","repos_url":"https://api.github.com/users/jmjwozniak/repos","events_url":"https://api.github.com/users/jmjwozniak/events{/privacy}","received_events_url":"https://api.github.com/users/jmjwozniak/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/swift-lang/swift-t/labels/auto-migrated","name":"auto-migrated","color":"ededed"},{"url":"https://api.github.com/repos/swift-lang/swift-t/labels/Component-STP","name":"Component-STP","color":"ededed"},{"url":"https://api.github.com/repos/swift-lang/swift-t/labels/Priority-Low","name":"Priority-Low","color":"ededed"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2015-04-22T20:59:28Z","updated_at":"2015-04-22T20:59:29Z","closed_at":null,"body":"_From @GoogleCodeExporter on April 22, 2015 18:50_\n\n```\nDetect circular dependencies leading to deadlock.\n\nE.g. \na = b;\nb = c;\nc = a;\n\nor with conditionals\n\nc = a + 2;\nif (...) {\n   a = b;\n} else {\n   a = c;\n}\n\nThe basic strategy to do this would be to construct a dataflow graph and then \ncheck for cycles or dead-ends.  E.g. in a procedure there will be some set of \nvariables A which start off with an initial value (including arguments, and \nvariables which are initialised to a constant value).  If we follow all \n\"depends-on\" links from a variable v back through the graph, all paths should \nterminate at a variable in the set A.  If there is a cycle, or if the path \nterminates at an uninitialised variable, we have a deadlock.  There are a \ncouple of complications I see:\n* conditional statements - the value of the variable could come from one branch \nor another, so need to have some kind of OR operator (like the Phi operator \nfrom SSA) to represent this\n* loops - I'm not sure what the implications of these are yet\n* assigning to array members.  Sometimes we can work out exactly which array \nindex is assigned, but in general we don't know, so we will have to have \nspecial treatment in the dataflow graph for the unknown array indices\n```\n\nOriginal issue reported on code.google.com by `tim.g.ar...@gmail.com` on 8 Feb 2012 at 3:38\n* Blocked on: #78\n\n_Copied from original issue: jmjwozniak/exm-issues#79_"}}