Chapter 3: Variable Declarations

Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: Yichen Yan <oraluben@outlook.com>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Tamas Hadhazy <helsgithub15@gmail.com>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>

4 files changed, 366 insertions, 13 deletions

diff --git a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
index 4c625be1..9dfac52d 100644
--- a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
+++ b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -17,7 +17,7 @@ public class GraphVisualizer {
         // nodes in the graph.
         Collection<Node> all = findAll(parser);
         StringBuilder sb = new StringBuilder();
-        sb.append("digraph chapter02 {\n");
+        sb.append("digraph chapter03 {\n");
         sb.append("/*\n");
         sb.append(parser.src());
         sb.append("\n*/\n");
@@ -39,9 +39,15 @@ public class GraphVisualizer {
         // Just the Nodes first, in a cluster no edges
         nodes(sb, all);
 
+        // Now the scopes, in a cluster no edges
+        scopes(sb, parser._scope);
+
         // Walk the Node edges
         nodeEdges(sb, all);
 
+        // Walk the Scope edges
+        scopeEdges(sb, parser._scope);
+
         sb.append("}\n");
         return sb.toString();
     }
@@ -51,6 +57,8 @@ public class GraphVisualizer {
         // Just the Nodes first, in a cluster no edges
         sb.append("\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name
         for( Node n : all ) {
+            if( n instanceof ScopeNode )
+                continue; // Do not emit, rolled into Scope cluster already
             sb.append("\t\t").append(n.uniqueName()).append(" [ ");
             String lab = n.glabel();
             // control nodes have box shape
@@ -63,6 +71,30 @@ public class GraphVisualizer {
         sb.append("\t}\n");     // End Node cluster
     }
 
+    private void scopes( StringBuilder sb, ScopeNode scopenode) {
+        sb.append("\tnode [shape=plaintext];\n");
+        int level=0;
+        for( HashMap<String,Integer> scope : scopenode._scopes ) {
+            String scopeName = makeScopeName(scopenode, level);
+            sb.append("\tsubgraph cluster_").append(scopeName).append(" {\n"); // Magic "cluster_" in the subgraph name
+            sb.append("\t\t").append(scopeName).append(" [label=<\n");
+            sb.append("\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n");
+            // Add the scope level
+            sb.append("\t\t\t<TR><TD BGCOLOR=\"cyan\">").append(level).append("</TD>");
+            for( String name : scope.keySet() )
+                sb.append("<TD PORT=\"").append(makePortName(scopeName, name)).append("\">").append(name).append("</TD>");
+            sb.append("</TR>\n");
+            sb.append("\t\t\t</TABLE>>];\n");
+            level++;
+        }
+        // Scope clusters nest, so the graphics shows the nested scopes, so
+        // they are not closed as they are printed; so they just keep nesting.
+        // We close them all at once here.
+        sb.append( "\t}\n".repeat( level ) ); // End all Scope clusters
+    }
+
+    private String makeScopeName(ScopeNode sn, int level) { return sn.uniqueName() + "_" + level; }
+    private String makePortName(String scopeName, String varName) { return scopeName + "_" + varName; }
 
     // Walk the node edges
     private void nodeEdges(StringBuilder sb, Collection<Node> all) {
@@ -70,6 +102,9 @@ public class GraphVisualizer {
         sb.append("\tedge [ fontname=Helvetica, fontsize=8 ];\n");
         for( Node n : all ) {
             // In this chapter we do display the Constant->Start edge;
+            // ScopeNodes are done separately
+            if( n instanceof ScopeNode )
+                continue;
             int i=0;
             for( Node def : n._inputs ) {
                 if( def != null ) {
@@ -90,6 +125,26 @@ public class GraphVisualizer {
         }
     }
 
+    // Walk the scope edges
+    private void scopeEdges( StringBuilder sb, ScopeNode scopenode ) {
+        sb.append("\tedge [style=dashed color=cornflowerblue];\n");
+        int level=0;
+        for( HashMap<String,Integer> scope : scopenode._scopes ) {
+            String scopeName = makeScopeName(scopenode, 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(" -> ");
+                sb.append(def.uniqueName());
+                sb.append(";\n");
+            }
+            level++;
+        }
+    }
+
     /**
      * Finds all nodes in the graph.
      */
@@ -98,6 +153,10 @@ public class GraphVisualizer {
         final HashMap<Integer, Node> all = new HashMap<>();
         for( Node n : start._outputs )
             walk(all, n);
+        // Scan symbol tables
+        for( HashMap<String,Integer> scope : parser._scope._scopes )
+            for (Integer i : scope.values())
+                walk(all, parser._scope.in(i));
         return all.values();
     }
 
@@ -105,6 +164,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/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java
index 72da8eeb..fa1a852c 100644
--- a/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/src/main/java/com/seaofnodes/simple/Parser.java
@@ -3,6 +3,8 @@ package com.seaofnodes.simple;
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.*;
 
+import java.util.*;
+
 /**
  * The Parser converts a Simple source program to the Sea of Nodes intermediate
  * representation directly in one pass. There is no intermediate Abstract
@@ -24,32 +26,75 @@ public class Parser {
     // The Lexer.  Thin wrapper over a byte[] buffer with a cursor.
     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.
+     */
+    public ScopeNode _scope;
+
+    /**
+     * List of keywords disallowed as identifiers
+     */
+    private final HashSet<String> KEYWORDS = new HashSet<>(){{
+            add("int");
+            add("return");
+        }};
+
 
     public Parser(String source) {
         _lexer = new Lexer(source);
         Node.reset();
+        _scope = new ScopeNode();
         START = new StartNode();
     }
 
     String src() { return new String( _lexer._input ); }
 
-    public ReturnNode parse() {
-        var ret = (ReturnNode) parseStatement();
+    public ReturnNode parse() { return parse(false); }
+    public ReturnNode parse(boolean show) {
+        var ret = (ReturnNode) parseBlock();
         if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken());
+        if( show ) showGraph();
         return ret;
     }
 
     /**
+     * Parses a block
+     *
+     * <pre>
+     *     '{' statements '}'
+     * </pre>
+     * Does not parse the opening or closing '{}'
+     * @return a {@link Node} or {@code null}
+     */
+    private Node parseBlock() {
+        // Enter a new scope
+        _scope.push();
+        Node n = null;
+        while (!peek('}') && !_lexer.isEOF()) {
+            Node n0 = parseStatement();
+            if (n0 != null) n = n0; // Allow null returns from eg showGraph
+        };
+        // Exit scope
+        _scope.pop();
+        return n;
+    }
+
+    /**
      * Parses a statement
      *
      * <pre>
-     *     returnStatement
+     *     returnStatement | declStatement | blockStatement | expressionStatement
      * </pre>
      * @return a {@link Node} or {@code null}
      */
     private Node parseStatement() {
-        if (matchx("return")) return parseReturn();
-        throw errorSyntax("a statement");
+        if (matchx("return")  ) return parseReturn();
+        else if (matchx("int")) return parseDecl();
+        else if (match ("{"  )) return require(parseBlock(),"}");
+        else if (matchx("#showGraph")) return require(showGraph(),";");
+        else if (matchx(";")) return null; // Empty statement
+        else return parseExpressionStatement();
     }
 
     /**
@@ -66,6 +111,50 @@ public class Parser {
     }
 
     /**
+     * Dumps out the node graph
+     * @return {@code null}
+     */
+    private Node showGraph() {
+        System.out.println(new GraphVisualizer().generateDotOutput(this));
+        return null;
+    }
+
+    /**
+     * Parses an expression statement
+     *
+     * <pre>
+     *     name '=' expression ';'
+     * </pre>
+     * @return an expression {@link Node}, never {@code null}
+     */
+    private Node parseExpressionStatement() {
+        var name = requireId();
+        require("=");
+        var expr = require(parseExpression(), ";");
+        if( _scope.update(name, expr)==null )
+            throw error("Undefined name '" + name + "'");
+        return expr;
+    }
+
+    /**
+     * Parses a declStatement
+     *
+     * <pre>
+     *     'int' name = expression ';'
+     * </pre>
+     * @return an expression {@link Node}, never {@code null}
+     */
+    private Node parseDecl() {
+        // Type is 'int' for now
+        var name = requireId();
+        require("=");
+        var expr = require(parseExpression(), ";");
+        if( _scope.define(name,expr) == null )
+            throw error("Redefining name '" + name + "'");
+        return expr;
+    }
+
+    /**
      * Parse an expression of the form:
      *
      * <pre>
@@ -129,7 +218,11 @@ public class Parser {
     private Node parsePrimary() {
         if( _lexer.isNumber() ) return parseIntegerLiteral();
         if( match("(") ) return require(parseExpression(), ")");
-        throw errorSyntax("integer literal");
+        String name = _lexer.matchId();
+        if( name == null) throw errorSyntax("an identifier or expression");
+        Node n = _scope.lookup(name);
+        if( n!=null ) return n;
+        throw error("Undefined name '" + name + "'");
     }
 
     /**
@@ -150,6 +243,15 @@ public class Parser {
     private boolean match (String syntax) { return _lexer.match (syntax); }
     // Match must be "exact", not be followed by more id letters
     private boolean matchx(String syntax) { return _lexer.matchx(syntax); }
+    // Return true and do NOT skip if 'ch' is next
+    private boolean peek(char ch) { return _lexer.peek(ch); }
+
+    // Require and return an identifier
+    private String requireId() {
+        String id = _lexer.matchId();
+        if (id != null && !KEYWORDS.contains(id) ) return id;
+        throw error("Expected an identifier, found '"+id+"'");
+    }
 
     // Require an exact match
     private void require(String syntax) { require(null, syntax); }
@@ -247,6 +349,17 @@ public class Parser {
             return false;
         }
 
+        private boolean peek(char ch) {
+            skipWhiteSpace();
+            return peek()==ch;
+        }
+
+        // Return an identifier or null
+        String matchId() {
+            skipWhiteSpace();
+            return isIdStart(peek()) ? parseId() : null;
+        }
+
         // Used for errors
         String getAnyNextToken() {
             if (isEOF()) return "";
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index 6f47f9eb..82357f9b 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -126,10 +126,18 @@ public abstract class Node {
     public boolean isCFG() { return false; }
 
 
+
     /**
      * 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
@@ -152,6 +160,22 @@ public abstract class Node {
         return new_def;
     }
 
+    /**
+     * 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 addDef(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.addUse(this);
+        return new_def;
+    }
+
     // Breaks the edge invariants, used temporarily
     protected <N extends Node> N addUse(Node n) { _outputs.add(n); return (N)this; }
 
@@ -163,16 +187,25 @@ public abstract class Node {
         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 popN(int n) {
+        for( int i=0; i<n; i++ ) {
+            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
+        }
+    }
+
     /**
      * 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 #setDef}.
+     * code elimination.  This function is co-recursive with {@link #popN}.
      */
     public void kill( ) {
         assert isUnused();      // Has no uses, so it is dead
-        for( int i=0; i<nIns(); i++ )
-            setDef(i,null);  // Set all inputs to null, recursively killing unused Nodes
-        _inputs.clear();
+        popN(nIns());          // Set all inputs to null, recursively killing unused Nodes
         _type=null;             // Flag as dead
         assert isDead();        // Really dead now
     }
@@ -218,7 +251,6 @@ public abstract class Node {
         return this;            // No progress
     }
 
-
     /**
      * This function needs to be
      * <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a>
@@ -243,5 +275,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/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
new file mode 100644
index 00000000..379ef033
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -0,0 +1,128 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+
+import java.util.*;
+
+/**
+ * The Scope node is purely a parser helper - it tracks names to nodes with a
+ * stack of scopes.
+ * @see <a href="file:../../../../../../../../chapter03/README.md">chapter03/README.md</a>
+ */
+public class ScopeNode extends Node {
+
+    /**
+     * A Stack of symbol tables; a symbol table is a map from names to node indices.
+     */
+    public final Stack<HashMap<String, Integer>> _scopes;
+
+
+    // A new ScopeNode
+    public ScopeNode() {
+        _scopes = new Stack<>();
+        _type = Type.BOTTOM;
+    }
+
+
+    @Override public String label() { return "Scope"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        sb.append(label());
+        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;
+    }
+
+    /**
+     * Recover the names for all variable bindings.
+     * The result is an array of names that is aligned with the
+     * inputs to the Node.
+     * <p>
+     * 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; }
+
+    @Override public Node idealize() { return null; }
+
+    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> syms = _scopes.lastElement();
+        if( syms.put(name,nIns()) != null )
+            return null;        // Double define
+        return addDef(n);
+    }
+    /**
+     * Lookup a name in all scopes starting from most deeply nested.
+     * <p>
+     * @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
+     * <p>
+     * @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.
+     * <p>
+     * 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);
+    }
+
+    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); }
+
+}