Replace Parser scopes with ScopeNode (#14)

Fixes #12 
* Replace Parser scopes with ScopeNode

Basically move the Stack of HashMaps to a ScopeNode, with wrappers.
The HashMap maps String names to Integer indices; inputs to the ScopeNode.
This way, the ScopeNode keeps alive Nodes that are only alive because they are alive in the HashMap.

Fix bug isDead -> isUnused in deadCodeElim.
Support routines for adding/removing edges in ScopeNode.
Set $ctrl to null after a Return; there is no control.
Regression tests.

* One more test case

7 files changed, 191 insertions, 73 deletions

diff --git a/chapter04/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter04/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
index 38bc1356..f73bfd3c 100644
--- a/chapter04/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
+++ b/chapter04/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -34,13 +34,13 @@ public class GraphVisualizer {
         nodes(sb, all);
         
         // Now the scopes, in a cluster no edges
-        scopes(sb, parser._scopes);
+        scopes(sb, parser._scope);
 
         // Walk the Node edges
         nodeEdges(sb, all);
 
         // Walk the Scope edges
-        scopeEdges(sb, parser._scopes);
+        scopeEdges(sb, parser._scope);
         
         sb.append("}\n");
         return sb.toString();
@@ -95,10 +95,10 @@ public class GraphVisualizer {
         sb.append("\t}\n");     // End Node cluster
     }
 
-    private void scopes( StringBuilder sb, Stack<HashMap<String,Node>> scopes) {
+    private void scopes( StringBuilder sb, ScopeNode scopenode) {
         sb.append("\tnode [shape=plaintext];\n");
         int level=0;
-        for( HashMap<String,Node> scope : scopes ) {
+        for( HashMap<String,Integer> scope : scopenode._scopes ) {
             sb.append("\tsubgraph cluster_").append(level).append(" {\n"); // Magic "cluster_" in the subgraph name
             String scopeName = makeScopeName(level);
             sb.append("\t\t").append(scopeName).append(" [label=<\n");
@@ -145,17 +145,18 @@ public class GraphVisualizer {
     }
     
     // Walk the scope edges
-    private void scopeEdges( StringBuilder sb, Stack<HashMap<String,Node>> scopes) {
+    private void scopeEdges( StringBuilder sb, ScopeNode scopenode ) {
         sb.append("\tedge [style=dashed color=cornflowerblue];\n");
         int level=0;
-        for( HashMap<String,Node> scope : scopes ) {
+        for( HashMap<String,Integer> scope : scopenode._scopes ) {
             String scopeName = makeScopeName(level);
             for( String name : scope.keySet() ) {
+                Node def = scopenode.in(scope.get(name));
+                if( def==null ) continue;
                 sb.append("\t")
                   .append(scopeName).append(":")
                   .append('"').append(makePortName(scopeName, name)).append('"') // wrap port name with quotes because $ctrl is not valid unquoted
                   .append(" -> ");
-                Node def = scope.get(name);
                 if( def instanceof ProjNode proj ) {
                     String mname = proj.ctrl().uniqueName();
                     sb.append(mname).append(":p").append(proj._idx);
@@ -175,9 +176,9 @@ public class GraphVisualizer {
         for( Node n : start._outputs )
             walk(all, n);
         // Scan symbol tables
-        for( HashMap<String,Node> scope : parser._scopes )
-            for (Node n : scope.values())
-                walk(all, n);
+        for( HashMap<String,Integer> scope : parser._scope._scopes )
+            for (Integer i : scope.values())
+                walk(all, parser._scope.in(i));
         return all.values();
     }
 
@@ -185,6 +186,7 @@ public class GraphVisualizer {
      * Walk a subgraph and populate distinct nodes in the all list.
      */
     private void walk(HashMap<Integer, Node> all, Node n) {
+        if(n == null ) return;
         if (all.get(n._nid) != null) return; // Been there, done that
         all.put(n._nid, n);
         for (Node c : n._inputs)
diff --git a/chapter04/src/main/java/com/seaofnodes/simple/Parser.java b/chapter04/src/main/java/com/seaofnodes/simple/Parser.java
index 36fec5d5..a6872106 100644
--- a/chapter04/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter04/src/main/java/com/seaofnodes/simple/Parser.java
@@ -26,15 +26,14 @@ public class Parser {
     private final Lexer _lexer;
 
     /**
-     * Stack of lexical scopes, each scope is a symbol table
-     * that binds variable names to Nodes.
-     * The top of this stack represents current scope.
+     * Stack of lexical scopes, each scope is a symbol table that binds
+     * variable names to Nodes.  The top of this stack represents current scope.
      */
-    public Stack<HashMap<String, Node>> _scopes;
+    public ScopeNode _scope;
 
     public Parser(String source, TypeInteger arg) {
         _lexer = new Lexer(source);
-        _scopes = new Stack<>();
+        _scope = new ScopeNode();
         Node.reset();
         START = new StartNode(new Type[]{ Type.CONTROL, arg });
         START.peephole();
@@ -47,46 +46,17 @@ public class Parser {
     String src() { return new String( _lexer._input ); }
 
     public ReturnNode parse() {
-        _scopes.push(new HashMap<>());
+        _scope.push();
         try {
-            define("$ctrl", new ProjNode(START, 0, "$ctrl").peephole());
-            define("arg"  , new ProjNode(START, 1, "arg"  ).peephole());
+            _scope.define("$ctrl", new ProjNode(START, 0, "$ctrl").peephole());
+            _scope.define("arg"  , new ProjNode(START, 1, "arg"  ).peephole());
             return (ReturnNode) parseBlock();
         }
         finally {
-            _scopes.pop();
+            _scope.pop();
         }
     }
 
-    // Create a new name in current scope
-    private Node define(String name, Node n) {
-        _scopes.lastElement().put(name, n);
-        return n;
-    }
-
-    // If the name is present in any scope, then redefine
-    private Node update(String name, Node n) {
-        for (int i = _scopes.size() - 1; i >= 0; i--) {
-            HashMap<String, Node> scope = _scopes.get(i);
-            Node old = scope.get(name);
-            if (old != null) { // Found prior def
-                if (old.nOuts() == 0) old.kill(); // Delete old ref
-                scope.put(name, n); // Update existing ref
-                return n;
-            }
-        }
-        throw error("Undefined name '" + name + "'");
-    }
-
-    // Lookup a name in all scopes
-    private Node lookup(String name) {
-        for (int i = _scopes.size() - 1; i >= 0; i--) {
-            var n = _scopes.get(i).get(name);
-            if (n != null) return n;
-        }
-        throw error("Undefined name '" + name + "'");
-    }
-
     /**
      * Parses a block
      *
@@ -96,14 +66,14 @@ public class Parser {
      */
     private Node parseBlock() {
         // Enter a new scope
-        _scopes.push(new HashMap<>());
+        _scope.push();
         Node n = null;
         while (!match("}") && !_lexer.isEOF()) {
             Node n0 = parseStatement();
             if (n0 != null) n = n0; // Allow null returns from eg showGraph
         }
         // Exit scope
-        _scopes.pop();
+        _scope.pop();
         return n;
     }
 
@@ -123,7 +93,8 @@ public class Parser {
     }
 
     /**
-     * Parses returnStatement; "return" already parsed
+     * Parses a return statement; "return" already parsed.
+     * The $ctrl edge is killed.
      *
      * <pre>
      *     'return' expr ;
@@ -131,7 +102,9 @@ public class Parser {
      */
     private Node parseReturn() {
         var expr = require(parseExpression(), ";");
-        return new ReturnNode(lookup("$ctrl"), expr);
+        Node ret = new ReturnNode(_scope.lookup("$ctrl"), expr);
+        _scope.update("$ctrl",null);
+        return ret;
     }
 
     /**
@@ -154,7 +127,9 @@ public class Parser {
         var name = requireId();
         require("=");
         var expr = require(parseExpression(), ";");
-        return update(name, expr);
+        if( _scope.update(name, expr)==null )
+            throw error("Undefined name '" + name + "'");
+        return expr;
     }
 
     /**
@@ -169,7 +144,9 @@ public class Parser {
         var name = requireId();
         require("=");
         var expr = require(parseExpression(), ";");
-        return define(name, expr);
+        if( _scope.define(name,expr) == null )
+            throw error("Redefining name '" + name + "'");
+        return expr;
     }
 
     /**
@@ -242,7 +219,11 @@ public class Parser {
     private Node parsePrimary() {
         if (_lexer.isNumber()) return parseIntegerLiteral();
         if (match("(")) return require(parseExpression(), ")");
-        return lookup(requireId()).peephole();
+        String name = requireId();
+        Node id = _scope.lookup(name);
+        if( id==null )
+            throw error("Undefined name '" + name + "'");
+        return id.peephole();
     }
 
     /**
diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index 5b4f8af9..ec85bf1f 100644
--- a/chapter04/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -30,7 +30,7 @@ public class ConstantNode extends Node {
 
     @Override
     StringBuilder _print1(StringBuilder sb) {
-        return _type._print(sb);
+        return _con._print(sb);
     }
     
     @Override
diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java
index 45c4e11a..8d698d1b 100644
--- a/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -162,7 +162,7 @@ public abstract class Node {
     private Node deadCodeElim(Node m) {
         // If self is going dead and not being returned here (Nodes returned
         // from peephole commonly have no uses (yet)), then kill self.
-        if( m != this && isDead() ) {
+        if( m != this && isUnused() ) {
             // Killing self - and since self recursively kills self's inputs we
             // might end up killing 'm', which we are returning as a live Node.
             // So we add a bogus extra null output edge to stop kill().
@@ -192,18 +192,36 @@ public abstract class Node {
      */
     Node set_def(int idx, Node new_def ) {
         Node old_def = in(idx);
-        if( old_def != null &&  // If the old def exists, remove a use->def edge
+        if( old_def == new_def ) return this; // No change
+        if( old_def != null &&  // If the old def exists, remove a def->use edge
             old_def.delUse(this) ) // If we removed the last use, the old def is now dead
             old_def.kill();     // Kill old def
         // Set the new_def over the old (killed) edge
         _inputs.set(idx,new_def);
-        // If new def is not null, add the corresponding use->def edge
+        // If new def is not null, add the corresponding def->use edge
         if( new_def != null )
             new_def._outputs.add(this);
         // Return self for easy flow-coding
         return this;
     }
 
+    /**
+     * Add a new def to an existing Node.  Keep the edges correct by
+     * adding the corresponding <em>def->use</em> edge.
+     *
+     * @param new_def the new definition, appended to the end of existing definitions
+     * @return new_def for flow coding
+     */
+    Node add_def(Node new_def) {
+        // Add use->def edge
+        _inputs.add(new_def);
+        // If new def is not null, add the corresponding def->use edge
+        if( new_def != null )
+            new_def._outputs.add(this);
+        return new_def;
+    }
+
+    
     // Breaks the edge invariants, used temporarily
     private void addUse(Node n) { _outputs.add(n); }
 
@@ -221,19 +239,27 @@ public abstract class Node {
         return lidx==0;
     }
 
+    // Shortcut for "popping" n nodes.  A "pop" is basically a
+    // set_def(last,null) followed by lowering the nIns() count.
+    void pop_n(int n) {
+        for( int i=0; i<n; i++ ) {
+            Node old_def = _inputs.remove(_inputs.size()-1);
+            if( old_def != null &&     // If it exists and
+                old_def.delUse(this) ) // If we removed the last use, the old def is now dead
+                old_def.kill();        // Kill old def
+        }
+    }
+  
     /**
      * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em>
      * to null.  This may recursively kill more Nodes and is basically dead
-     * code elimination.  This function is co-recursive with {@link #set_def}.
+     * code elimination.  This function is co-recursive with {@link #pop_n}.
      */
     public void kill( ) {
-        assert isUnused();    // Has no uses, so it is dead
-        for( int i=0; i<nIns(); i++ )
-            set_def(i,null);  // Set all inputs to null, recursively killing unused Nodes
-        _inputs.clear();      // Flag as dead
-        _outputs.clear();     // Flag as dead
-        _type=null;           // Flag as dead
-        assert isDead();      // Really dead now
+        assert isUnused();      // Has no uses, so it is dead
+        pop_n(nIns());          // Set all inputs to null, recursively killing unused Nodes
+        _type=null;             // Flag as dead
+        assert isDead();        // Really dead now
     }
 
     // Mostly used for asserts and printing.
diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
new file mode 100644
index 00000000..8bd81e82
--- /dev/null
+++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -0,0 +1,88 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.TypeBot;
+
+import java.util.*;
+
+/**
+ * The Scope node is a purely parser helper - it tracks names to nodes with a
+ * stack of scopes.
+ */
+public class ScopeNode extends Node {
+
+    /**
+     * Stack of lexical scopes, each scope is a symbol table
+     * that binds variable names to Nodes.
+     * The top of this stack represents current scope.
+     */
+    public final Stack<HashMap<String, Integer>> _scopes = new Stack<>();
+  
+    @Override
+    public String label() { return "Scope"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        for( HashMap<String,Integer> scope : _scopes ) {
+            sb.append("[");
+            boolean first=true;
+            for( String name : scope.keySet() ) {
+                if( !first ) sb.append(", ");
+                first=false;
+                sb.append(name).append(":");
+                Node n = in(scope.get(name));
+                if( n==null ) sb.append("null");
+                else n._print0(sb);
+            }
+            sb.append("]");
+        }
+        return sb;
+    }
+  
+    @Override
+    public TypeBot compute() { return TypeBot.BOTTOM; }
+
+    @Override
+    public Node idealize() { return null; }
+
+    // Add an empty lexical scope
+    public void push() {
+        _scopes.push(new HashMap<>());
+    }
+
+    // Remove the current lexical scope, killing all unused nodes.
+    public void pop() {
+        HashMap<String,Integer> scope = _scopes.pop();
+        pop_n(scope.size());
+    }
+
+    // Create a new name in the current scope
+    public Node define( String name, Node n ) {
+        HashMap<String,Integer> scope = _scopes.lastElement();
+        if( scope.put(name,nIns()) != null )
+            return null;        // Double define
+        return add_def(n);
+    }
+
+    // Lookup a name in all scopes
+    public Node lookup(String name) {
+        for (int i = _scopes.size() - 1; i >= 0; i--) {
+            var idx = _scopes.get(i).get(name);
+            if (idx != null) return in(idx);
+        }
+        return null;
+    }
+
+
+    // If the name is present in any scope, then redefine
+    public Node update(String name, Node n) {
+        for (int i = _scopes.size() - 1; i >= 0; i--) {
+            HashMap<String, Integer> scope = _scopes.get(i);
+            Integer idx = scope.get(name);
+            if (idx != null)           // Found prior def
+                return set_def(idx,n); // Update def in scope
+        }
+        return null;
+    }
+
+
+}
diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 0618a42f..b59e3375 100644
--- a/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -5,9 +5,11 @@ import com.seaofnodes.simple.type.TypeBot;
 import com.seaofnodes.simple.type.TypeTuple;
 
 /**
- * The Start node represents the start of the function.  For now, we do not have any inputs to Start because our function does not
- * yet accept parameters.  When we add parameters the value of Start will be a tuple, and will require Projections to extract the values.
- * We discuss this in detail in Chapter 9: Functions and Calls.
+ * The Start node represents the start of the function.  For now, we do not
+ * have any inputs to Start because our function does not yet accept
+ * parameters.  When we add parameters the value of Start will be a tuple, and
+ * will require Projections to extract the values.  We discuss this in detail
+ * in Chapter 9: Functions and Calls.
  */
 public class StartNode extends MultiNode implements Control {
 
@@ -27,9 +29,7 @@ public class StartNode extends MultiNode implements Control {
     }
   
     @Override
-    public TypeTuple compute() {
-        return _args;
-    }
+    public TypeTuple compute() { return _args; }
 
     @Override
     public Node idealize() { return null; }
diff --git a/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java
index 988e3608..8cc78af0 100644
--- a/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java
+++ b/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java
@@ -99,6 +99,20 @@ public class Chapter04Test {
     }
 
     @Test
+    public void testChapter4Bug1() {
+        Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;", TypeInteger.BOT);
+        ReturnNode ret = parser.parse();
+        assertEquals("return (Proj_3+3);", ret.print());
+    }
+
+    @Test
+    public void testChapter4Bug2() {
+        Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;", TypeInteger.BOT);
+        ReturnNode ret = parser.parse();
+        assertEquals("return (Proj_3+1);", ret.print());
+    }
+
+    @Test
     public void testVarDecl() {
         Parser parser = new Parser("int a=1; return a;");
         ReturnNode ret = parser.parse();
@@ -135,6 +149,13 @@ public class Chapter04Test {
         assertEquals("return 8;", ret.print());
     }
 
+    @Test
+    public void testSelfAssign() {
+        exceptionRule.expect(RuntimeException.class);
+        exceptionRule.expectMessage("Undefined name 'a'");
+        new Parser("int a=a; return a;").parse();
+    }
+
 
     @Test
     public void testChapter2ParseGrammar() {