Backport some of the code refactoring to previous chapters (#50)

* #44 Revise docs and comments

* #44 Add starting scope to xScopes

* #44 back some of the code refactoring port to previous chapters

* #44 add_def should not be public

* #44 add_def should not be public. Rename method names so that they are camelcase

7 files changed, 227 insertions, 123 deletions

diff --git a/chapter03/README.md b/chapter03/README.md
index 3e6cebfe..07d8fe3e 100644
--- a/chapter03/README.md
+++ b/chapter03/README.md
@@ -19,16 +19,16 @@ Here is the [complete language grammar](docs/03-grammar.md) for this chapter.
 
 To recap, our list of Nodes are:
 
-| Node Name  | Type    | Description                        | Inputs                                                           | Value                                                 |
-|------------|---------|------------------------------------|------------------------------------------------------------------|-------------------------------------------------------|
-| Start      | Control | Start of function                  | None                                                             | None for now as we do not have function arguments yet |
-| Return     | Control | End of function                    | Predecessor control node, Data node value                        | Return value of the function                          |
-| Constant   | Data    | Constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant                                 |
-| Add        | Data    | Add two values                     | Two data nodes, values are added, order not important            | Result of the add operation                           |
-| Sub        | Data    | Subtract a value from another      | Two data nodes, values are subtracted, order matters             | Result of the subtract                                |
-| Mul        | Data    | Multiply two values                | Two data nodes, values are multiplied, order not important       | Result of the multiply                                |
-| Div        | Data    | Divide a value by another          | Two data nodes, values are divided, order matters                | Result of the division                                |
-| UnaryMinus | Data    | Negate a value                     | One data node, value is negated                                  | Result of the unary minus                             |
+| Node Name | Type    | Description                        | Inputs                                                           | Value                                                 |
+|-----------|---------|------------------------------------|------------------------------------------------------------------|-------------------------------------------------------|
+| Start     | Control | Start of function                  | None                                                             | None for now as we do not have function arguments yet |
+| Return    | Control | End of function                    | Predecessor control node, Data node value                        | Return value of the function                          |
+| Constant  | Data    | Constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant                                 |
+| Add       | Data    | Add two values                     | Two data nodes, values are added, order not important            | Result of the add operation                           |
+| Sub       | Data    | Subtract a value from another      | Two data nodes, values are subtracted, order matters             | Result of the subtract                                |
+| Mul       | Data    | Multiply two values                | Two data nodes, values are multiplied, order not important       | Result of the multiply                                |
+| Div       | Data    | Divide a value by another          | Two data nodes, values are divided, order matters                | Result of the division                                |
+| Minus     | Data    | Negate a value                     | One data node, value is negated                                  | Result of the unary minus                             |
 
 In this chapter we introduce:
 
diff --git a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java
index c8195882..60761f04 100644
--- a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java
@@ -52,14 +52,10 @@ public class Parser {
 
     public ReturnNode parse() { return parse(false); }
     public ReturnNode parse(boolean show) {
-        try {
-            var ret = (ReturnNode) parseBlock();
-            if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken());
-            return ret;
-        }
-        finally {
-            if( show ) showGraph();
-        }
+        var ret = (ReturnNode) parseBlock();
+        if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken());
+        if( show ) showGraph();
+        return ret;
     }
 
     /**
@@ -409,5 +405,4 @@ public class Parser {
             return new String(_input, start, 1);
         }
     }
-
 }
diff --git a/chapter03/src/main/java/com/seaofnodes/simple/Utils.java b/chapter03/src/main/java/com/seaofnodes/simple/Utils.java
new file mode 100644
index 00000000..4d663c25
--- /dev/null
+++ b/chapter03/src/main/java/com/seaofnodes/simple/Utils.java
@@ -0,0 +1,39 @@
+package com.seaofnodes.simple;
+
+import java.util.ArrayList;
+
+public class Utils {
+    public static RuntimeException TODO() { return TODO("Not yet implemented"); }
+    public static RuntimeException TODO(String msg) { return new RuntimeException(msg); }
+
+    /**
+     *  Fast, constant-time, element removal.  Does not preserve order
+     *
+     *  @param array ArrayList to modify
+     *  @param i element to be removed
+     *  @return element removed
+     */
+    public static <E> E del(ArrayList<E> array, int i) {
+        if ( i >= 0 && i < array.size() ) {
+            E tmp = array.get(i);
+            E last = array.removeLast();
+            if (i < array.size()) array.set(i, last);
+            return tmp;
+        }
+        return null;
+    }
+
+    /**
+     * Search a list for an element by reference
+     *
+     * @param ary List to search in
+     * @param x Object to be searched
+     * @return >= 0 on success, -1 on failure
+     */
+    public static <E> int find( ArrayList<E> ary, E x ) {
+        for( int i=0; i<ary.size(); i++ )
+            if( ary.get(i)==x )
+                return i;
+        return -1;
+    }
+}
\ No newline at end of file
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 43dc6fa5..91bde29d 100644
--- a/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
 
 import java.util.*;
@@ -47,7 +48,7 @@ public abstract class Node {
 
     /**
      * A private Global Static mutable counter, for unique node id generation.
-     * To make the compiler multithreaded, this field will have to move into a TLS.
+     * To make the compiler multi-threaded, this field will have to move into a TLS.
      * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values.
      * */
     private static int UNIQUE_ID = 1;
@@ -70,7 +71,15 @@ public abstract class Node {
 
     // Graphical label, e.g. "+" or "Region" or "=="
     public String glabel() { return label(); }
+
+
+    // ------------------------------------------------------------------------
+    
+    // Debugger Printing.
     
+    // {@code toString} is what you get in the debugger.  It has to print 1
+    // line (because this is what a debugger typically displays by default) and
+    // has to be robust with broken graph/nodes.
     @Override
     public final String toString() {
         // TODO: This needs a lot of work
@@ -104,61 +113,33 @@ public abstract class Node {
 
     public int nIns() { return _inputs.size(); }
 
+    public Node out(int i) { return _outputs.get(i); }
+
     public int nOuts() { return _outputs.size(); }
 
     public boolean isUnused() { return nOuts() == 0; }
 
     public boolean isCFG() { return false; }
   
-    /**
-     * We allow disabling peephole opt so that we can observe the
-     * full graph, vs the optimized graph.
-     */
-    public static boolean _disablePeephole = false;
-
-    /**
-     * Try to peephole at this node and return a better replacement Node if
-     * possible.  We compute a {@link Type} and then check and replace:
-     * <ul>
-     * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li>
-     * <li>in a future chapter we will look for a
-     * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a>
-     * to eliminate.</li>
-     * <li>we ask the Node for a better replacement (again, none enabled in this chapter)</li>
-     * </ul>
-     */
-    public final Node peephole( ) {
-        // Compute initial or improved Type
-        Type type = _type = compute();
-        
-        if (_disablePeephole)
-            return this;        // Peephole optimizations turned off
-
-        // Replace constant computations from non-constants with a constant node
-        if (!(this instanceof ConstantNode) && type.isConstant()) {
-            kill();             // Kill `this` because replacing with a Constant
-            return new ConstantNode(type).peephole();
-        }
-
-        // Future chapter: Global Value Numbering goes here
-        
-        // Ask each node for a better replacement
-        Node n = idealize();
-        if( n != null ) return n;
-        
-        return this;            // No progress
-    }
 
+    
     /**
      * Change a <em>def</em> into a Node.  Keeps the edges correct, by removing
      * the corresponding <em>use->def</em> edge.  This may make the original
      * <em>def</em> go dead.  This function is co-recursive with {@link #kill}.
+     * <p>
+     
+     * This method is the normal path for altering a Node, because it does the
+     * proper default edge maintenance.  It also <em>immediately</em> kills
+     * Nodes that lose their last use; at times care must be taken to avoid
+     * killing Nodes that are being used without having an output Node.  This
+     * definitely happens in the middle of recursive {@link #peephole} calls.
      *     
      * @param idx which def to set
      * @param new_def the new definition
-     * @return this for flow coding
+     * @return new_def for flow coding
      */
-    Node set_def(int idx, Node new_def ) {
+    Node setDef(int idx, Node new_def ) {
         Node old_def = in(idx);
         if( old_def == new_def ) return this; // No change
         // If new def is not null, add the corresponding def->use edge
@@ -172,7 +153,7 @@ public abstract class Node {
         // Set the new_def over the old (killed) edge
         _inputs.set(idx,new_def);
         // Return self for easy flow-coding
-        return this;
+        return new_def;
     }
 
     /**
@@ -182,7 +163,7 @@ public abstract class Node {
      * @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) {
+    Node addDef(Node new_def) {
         // Add use->def edge
         _inputs.add(new_def);
         // If new def is not null, add the corresponding def->use edge
@@ -192,27 +173,21 @@ public abstract class Node {
     }
 
     // Breaks the edge invariants, used temporarily
-    private void addUse(Node n) { _outputs.add(n); }
+    protected <N extends Node> N addUse(Node n) { _outputs.add(n); return (N)this; }
 
     // 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.
     protected 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;
+        Utils.del(_outputs, Utils.find(_outputs, use));
+        return _outputs.size() == 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) {
+    void popN(int n) {
         for( int i=0; i<n; i++ ) {
-            Node old_def = _inputs.remove(_inputs.size()-1);
+            Node old_def = _inputs.removeLast();
             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
@@ -222,17 +197,55 @@ public abstract class Node {
     /**
      * 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 #pop_n}.
+     * code elimination.  This function is co-recursive with {@link #popN}.
      */
     public void kill( ) {
         assert isUnused();      // Has no uses, so it is dead
-        pop_n(nIns());          // Set all inputs to null, recursively killing unused Nodes
+        popN(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.
     boolean isDead() { return isUnused() && nIns()==0 && _type==null; }
+    /**
+     * We allow disabling peephole opt so that we can observe the
+     * full graph, vs the optimized graph.
+     */
+    public static boolean _disablePeephole = false;
+
+    /**
+     * Try to peephole at this node and return a better replacement Node if
+     * possible.  We compute a {@link Type} and then check and replace:
+     * <ul>
+     * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li>
+     * <li>in a future chapter we will look for a
+     * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a>
+     * to eliminate.</li>
+     * <li>we ask the Node for a better replacement (again, none enabled in this chapter)</li>
+     * </ul>
+     */
+    public final Node peephole( ) {
+        // Compute initial or improved Type
+        Type type = _type = compute();
+        
+        if (_disablePeephole)
+            return this;        // Peephole optimizations turned off
+
+        // Replace constant computations from non-constants with a constant node
+        if (!(this instanceof ConstantNode) && type.isConstant()) {
+            kill();             // Kill `this` because replacing with a Constant
+            return new ConstantNode(type).peephole();
+        }
+
+        // Future chapter: Global Value Numbering goes here
+        
+        // Ask each node for a better replacement
+        Node n = idealize();
+        if( n != null ) return n;
+        
+        return this;            // No progress
+    }
   
     /**
      * This function needs to be
@@ -258,5 +271,25 @@ public abstract class Node {
      * Used to allow repeating tests in the same JVM.  This just resets the
      * Node unique id generator, and is done as part of making a new Parser.
      */
-    public static void reset() { UNIQUE_ID = 1; }
+    public static void reset() { UNIQUE_ID = 1; _disablePeephole=false; }
+
+    /**
+     * Debugging utility to find a Node by index
+     */
+    public Node find(int nid) { return _find(new BitSet(),nid); }
+    private Node _find(BitSet visit, int nid) {
+        if( _nid==nid ) return this;
+        if( visit.get(_nid) ) return null;
+        visit.set(_nid);
+        for( Node def : _inputs )
+            if( def!=null ) {
+                Node rez = def._find(visit,nid);
+                if( rez != null ) return rez;
+            }
+        for( Node use : _outputs ) {
+            Node rez = use._find(visit,nid);
+            if( rez != null ) return rez;
+        }
+        return null;
+    }
 }
diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 49857533..7b42a2d0 100644
--- a/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -5,20 +5,23 @@ import com.seaofnodes.simple.type.Type;
 import java.util.*;
 
 /**
- * The Scope node is a purely parser helper - it tracks names to nodes with a
+ * The Scope node is purely a 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.
+     * Names for every input edge
      */
-    public final Stack<HashMap<String, Integer>> _scopes = new Stack<>();
+    public final Stack<HashMap<String, Integer>> _scopes;
 
-    // Reverse lookup for nicer graph printing
-    private final ArrayList<String> _rlabels = new ArrayList<>();
+
+    // A new ScopeNode
+    public ScopeNode() {
+        _scopes = new Stack<>();
+        _type = Type.BOTTOM;
+    }
+    
     
     @Override public String label() { return "Scope"; }
 
@@ -40,51 +43,85 @@ public class ScopeNode extends Node {
         }
         return sb;
     }
-  
-    @Override
-    public Type compute() { return Type.BOTTOM; }
 
-    @Override public Node idealize() { return null; }
-
-    // Add an empty lexical scope
-    public HashMap<String, Integer> push() {
-        return _scopes.push(new HashMap<>());
+    /**
+     * Recover the names for all variable bindings.
+     * The result is an array of names that is aligned with the
+     * inputs to the Node.
+     *
+     * This is an expensive operation.
+     */
+    public String[] reverseNames() {
+        String[] names = new String[nIns()];
+        for( HashMap<String,Integer> syms : _scopes )
+            for( String name : syms.keySet() )
+                names[syms.get(name)] = name;
+        return names;
     }
+    
+    @Override public Type compute() { return Type.BOTTOM; }
 
-    // Remove the current lexical scope, killing all unused nodes.
-    public void pop() {
-        HashMap<String,Integer> scope = _scopes.pop();
-        pop_n(scope.size());
-    }
+    @Override public Node idealize() { return null; }
 
-    // Create a new name in the current scope
+    public void push() { _scopes.push(new HashMap<>());  }
+    public void pop() { popN(_scopes.pop().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 )
+        HashMap<String,Integer> syms = _scopes.lastElement();
+        if( syms.put(name,nIns()) != null )
             return null;        // Double define
-        _rlabels.add(name);
-        return add_def(n);
+        return addDef(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;
+    /**
+     * Lookup a name in all scopes starting from most deeply nested.
+     *
+     * @param name Name to be looked up
+     * @see #update(String, Node, int)
+     */
+    public Node lookup( String name ) { return update(name,null,_scopes.size()-1);  }
+    /**
+     * If the name is present in any scope, then redefine else null
+     *
+     * @param name Name being redefined
+     * @param n    The node to bind to the name
+     */
+    public Node update( String name, Node n ) { return update(name,n,_scopes.size()-1); }
+    /**
+     * Both recursive lookup and update.
+     *
+     * A shared implementation allows us to create lazy phis both during
+     * lookups and updates; the lazy phi creation is part of chapter 8.
+     *
+     * @param name  Name whose binding is being updated or looked up
+     * @param n     If null, do a lookup, else update binding
+     * @param nestingLevel The starting nesting level
+     * @return node being looked up, or the one that was updated
+     */
+    private Node update( String name, Node n, int nestingLevel ) {
+        if( nestingLevel<0 ) return null;  // Missed in all scopes, not found
+        var syms = _scopes.get(nestingLevel); // Get the symbol table for nesting level
+        var idx = syms.get(name);
+        if( idx == null ) return update(name,n,nestingLevel-1); // Not found in this scope, recursively look in parent scope
+        Node old = in(idx);
+        // If n is null we are looking up rather than updating, hence return existing value
+        return n==null ? old : setDef(idx,n);
     }
 
-  
-    // 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;
-    }
+    public Node ctrl() { return in(0); }
+
+    /**
+     * The ctrl of a ScopeNode is always bound to the currently active
+     * control node in the graph, via a special name '$ctrl' that is not
+     * a valid identifier in the language grammar and hence cannot be
+     * referenced in Simple code.
+     *
+     * @param n The node to be bound to '$ctrl'
+     *
+     * @return Node that was bound
+     */
+    public Node ctrl(Node n) { return setDef(0,n); }
 
 }
diff --git a/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java
index 172cc632..5bd51611 100644
--- a/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -29,7 +29,7 @@ public class Type {
     public final byte _type;
 
     public boolean is_simple() { return _type < TSIMPLE; }
-    private static final String[] STRS = new String[]{"BOTTOM","TOP"};
+    private static final String[] STRS = new String[]{"Bot","Top"};
     protected Type(byte type) { _type = type; }
 
     public static final Type BOTTOM   = new Type( TBOT ); // ALL
diff --git a/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java
index d86b978f..5847fed4 100644
--- a/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java
+++ b/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java
@@ -36,8 +36,8 @@ public class Chapter03Test {
 
     @Test
     public void testVarScopeNoPeephole() {
-        Node._disablePeephole = true;
         Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;");
+        Node._disablePeephole = true;
         ReturnNode ret = parser.parse();
         Node._disablePeephole = false;
         assertEquals("return (1+3);", ret.print());
@@ -62,8 +62,8 @@ public class Chapter03Test {
 
     @Test
     public void testChapter2ParseGrammar() {
-        Node._disablePeephole = true; // disable peephole so we can observe full graph
         Parser parser = new Parser("return 1+2*3+-5;");
+        Node._disablePeephole = true; // disable peephole so we can observe full graph
         ReturnNode ret = parser.parse();
         assertEquals("return (1+((2*3)+(-5)));", ret.print());
         GraphVisualizer gv = new GraphVisualizer();