Chapter 3: Variable Declarations

Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
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: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: tannal <tannal2409@gmail.com>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: godalming123 <68993177+godalming123@users.noreply.github.com>
Co-authored-by: RobertObkircher <robert.obkircher@gmail.com>

5 files changed, 303 insertions, 12 deletions

diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java
index f59b0f25..e6cb84f8 100644
--- a/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/src/main/java/com/seaofnodes/simple/Parser.java
@@ -5,6 +5,8 @@ import com.seaofnodes.graph.GraphObserver;
 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
@@ -32,33 +34,73 @@ 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);
         PARSER = this;
         Node.reset();
+        _scope = new ScopeNode();
         START = new StartNode();
     }
 
     String src() { return new String( _lexer._input ); }
 
     public ReturnNode parse() {
-        var ret = (ReturnNode) parseStatement();
+        var ret = (ReturnNode) parseBlock();
         if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken());
         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; // Empty statements can return null
+        };
+        // 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(";")) return null; // Empty statement
+        else return parseExpressionStatement();
     }
 
     /**
@@ -74,6 +116,43 @@ public class Parser {
         return new ReturnNode(START, expr).peephole();
     }
 
+
+
+    /**
+     * 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:
      *
@@ -138,7 +217,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 + "'");
     }
 
     /**
@@ -159,6 +242,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); }
@@ -256,6 +348,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 3c0c3905..54687b2e 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -83,6 +83,13 @@ public abstract class Node extends BaseNode<Node> {
      * 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
@@ -105,6 +112,22 @@ public abstract class Node extends BaseNode<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> void addUse(N n) { _outputs.add(n); }
 
@@ -116,16 +139,25 @@ public abstract class Node extends BaseNode<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
     }
@@ -197,4 +229,24 @@ public abstract class Node extends BaseNode<Node> {
      * Node unique id generator, and is done as part of making a new Parser.
      */
     public static void reset() { UNIQUE_ID = 1; }
+
+    /**
+     * 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..95c25391
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -0,0 +1,130 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.print.ExprPrinter;
+
+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
+    protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) {
+        p.p(label());
+        for( HashMap<String,Integer> scope : _scopes ) {
+            p.p("[");
+            boolean first=true;
+            for( String name : scope.keySet() ) {
+                if( !first ) p.p(", ");
+                first=false;
+                p.p(name).p(":");
+                Node n = in(scope.get(name));
+                if( n==null ) p.p("null");
+                else p.n(n);
+            }
+            p.p("]");
+        }
+        return p;
+    }
+
+    /**
+     * 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); }
+
+}
diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
index 8f2f31ec..c97aaf55 100644
--- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
+++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
@@ -5,16 +5,21 @@ import com.seaofnodes.graph.GraphSnapshot.*;
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.node.Node;
 
-/** Chapter 2's view of the IR; browser, transport and layout are shared. */
+/** Chapter 3's view of the IR; browser, transport and layout are shared. */
 public class SimpleGraphAdapter extends GraphAdapter<Node> {
 
+    @Override protected String[] edgeNames(Node n) {
+        return n instanceof ScopeNode scope && n.nIns()!=0 ? scope.reverseNames() : null;
+    }
+
     @Override protected Kind kind(Node n) {
+        if( n instanceof ScopeNode ) return Kind.SCOPE;
         if( n instanceof StartNode ) return Kind.CTRL;
         return n.isCFG() ? Kind.CTRL : Kind.DATA;
     }
 
     @Override protected Role role(Node n, int i) {
-        if( n instanceof ConstantNode ) return Role.ASSOC;
+        if( n instanceof ScopeNode || n instanceof ConstantNode ) return Role.ASSOC;
         if( i == 0 ) return Role.CTRL;
         return Role.DATA;
     }
diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java
index a17bf796..2dc5d844 100644
--- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java
+++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java
@@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node;
 import java.util.ArrayList;
 import java.io.IOException;
 
-/** Chapter 2's compilation context; capture and event bookkeeping are shared. */
+/** Chapter 3's compilation context; capture and event bookkeeping are shared. */
 public class SimpleGraphObserver extends GraphCapture<Node> {
     private Parser _parser;
     private Node _ret;
@@ -30,6 +30,7 @@ public class SimpleGraphObserver extends GraphCapture<Node> {
         _parser = null;
         _ret = null;
     }
+    @Override protected Node scope() { return _parser._scope; }
     @Override protected void roots(ArrayList<Node> roots) {
         roots.add(Parser.START);
         roots.add(_ret);