Applied fix for #12 to chapter 3 (#15)

ScopeNode added to chapter 3
Revised the description for Chapter 3 and 4 to include ScopeNode.

4 files changed, 169 insertions, 67 deletions

diff --git a/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
index 5f3f52d0..dc5358f4 100644
--- a/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
+++ b/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -1,9 +1,6 @@
 package com.seaofnodes.simple;
 
-import com.seaofnodes.simple.node.ConstantNode;
-import com.seaofnodes.simple.node.Control;
-import com.seaofnodes.simple.node.Node;
-import com.seaofnodes.simple.node.StartNode;
+import com.seaofnodes.simple.node.*;
 
 import java.util.*;
 
@@ -33,13 +30,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();
@@ -61,10 +58,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");
@@ -102,13 +99,13 @@ 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() )
-                sb.append("\t").append(scopeName).append(":").append(makePortName(scopeName, name)).append(" -> ").append(scope.get(name).uniqueName()).append(";\n");
+                sb.append("\t").append(scopeName).append(":").append(makePortName(scopeName, name)).append(" -> ").append(scopenode.in(scope.get(name)).uniqueName()).append(";\n");
             level++;
         }
     }
@@ -126,9 +123,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();
     }
 
diff --git a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java
index 13b25e60..12e156ed 100644
--- a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter03/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) {
         _lexer = new Lexer(source);
-        _scopes = new Stack<>();
+        _scope = new ScopeNode();
         Node.reset();
         START = new StartNode();
     }
@@ -43,35 +42,6 @@ public class Parser {
         return (ReturnNode) parseBlock();
     }
 
-    // Create a new name in current scope
-    private Node define(String name, Node n) {
-        // new name
-        _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
@@ -82,14 +52,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;
     }
 
@@ -140,7 +110,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;
     }
 
     /**
@@ -155,7 +127,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;
     }
 
     /**
@@ -217,7 +191,11 @@ public class Parser {
     private Node parsePrimary() {
         if (_lexer.isNumber()) return parseIntegerLiteral();
         if (match("(")) return require(parseExpression(), ")");
-        return lookup(requireId());
+        String name = requireId();
+        Node id = _scope.lookup(name);
+        if( id==null )
+            throw error("Undefined name '" + name + "'");
+        return id;
     }
 
     /**
diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java
index 5528f296..6b7d673a 100644
--- a/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -152,27 +152,65 @@ public abstract class Node {
      * @param idx which def to set
      * @param new_def the new definition
      */
-    void set_def(int idx, Node new_def ) {
+    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
-            ArrayList<Node> outs = old_def._outputs;
-            int lidx = outs.size()-1; // Last index
-            
-            // This 1-line hack compresses an element out of an ArrayList
-            // without having to copy the contents.  The last element is
-            // stuffed over the deleted element, and then the size is reduced.            
-            outs.set(outs.indexOf(this),outs.get(lidx));
-            outs.remove(lidx);  // Reduce ArrayList size without copying anything
-            if( lidx == 0 )     // If we removed the last use, the old def is now dead
+        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); }
+
+    // Remove node 'use' from 'def's (i.e. our) output list, by compressing the list in-place.
+    // Return true if the output list is empty afterward.
+    // Error is 'use' does not exist; ok for 'use' to be null.
+    private boolean delUse( Node use ) {
+        ArrayList<Node> outs = _outputs;
+        int lidx = outs.size()-1; // Last index
+        // This 1-line hack compresses an element out of an ArrayList
+        // without having to copy the contents.  The last element is
+        // stuffed over the deleted element, and then the size is reduced.
+        outs.set(outs.indexOf(use),outs.get(lidx));
+        outs.remove(lidx);  // Reduce ArrayList size without copying anything
+        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
+        }
     }
-    
   
     /**
      * Current computed type for this Node.  This value changes as the graph
diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
new file mode 100644
index 00000000..c7d6edb9
--- /dev/null
+++ b/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -0,0 +1,89 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.TypeBot;
+
+import java.util.HashMap;
+import java.util.Stack;
+
+/**
+ * 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 _print(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._print(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;
+    }
+
+
+}