From a2a42257aaf2d78fd386f1bedd12f41bde3df119 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Sun, 1 Oct 2023 18:01:54 +0100 Subject: Chapter 3: Variable Declarations Co-authored-by: Cliff Click Co-authored-by: Yichen Yan Co-authored-by: Thalia Archibald Co-authored-by: Tamas Hadhazy Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> --- .../com/seaofnodes/simple/GraphVisualizer.java | 62 +++++++++- src/main/java/com/seaofnodes/simple/Parser.java | 125 +++++++++++++++++++- src/main/java/com/seaofnodes/simple/node/Node.java | 64 ++++++++++- .../java/com/seaofnodes/simple/node/ScopeNode.java | 128 +++++++++++++++++++++ .../java/com/seaofnodes/simple/Chapter01Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter02Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter03Test.java | 67 +++++++++++ 7 files changed, 436 insertions(+), 16 deletions(-) create mode 100644 src/main/java/com/seaofnodes/simple/node/ScopeNode.java create mode 100644 src/test/java/com/seaofnodes/simple/Chapter03Test.java (limited to 'src') 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 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 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\n"); + // Add the scope level + sb.append("\t\t\t"); + for( String name : scope.keySet() ) + sb.append(""); + sb.append("\n"); + sb.append("\t\t\t
").append(level).append("").append(name).append("
>];\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 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 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 all = new HashMap<>(); for( Node n : start._outputs ) walk(all, n); + // Scan symbol tables + for( HashMap 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 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 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 + * + * 
+     *     '{' statements '}'
+     *
+ * 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 * * 
-     *     returnStatement
+     *     returnStatement | declStatement | blockStatement | expressionStatement
      *
* @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(); } /** @@ -65,6 +110,50 @@ public class Parser { return new ReturnNode(START, expr).peephole(); } + /** + * Dumps out the node graph + * @return {@code null} + */ + private Node showGraph() { + System.out.println(new GraphVisualizer().generateDotOutput(this)); + return null; + } + + /** + * Parses an expression statement + * + * 
+     *     name '=' expression ';'
+     *
+ * @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 + * + * 
+     *     'int' name = expression ';'
+     *
+ * @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: * @@ -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 def into a Node. Keeps the edges correct, by removing * the corresponding use->def edge. This may make the original * def go dead. This function is co-recursive with {@link #kill}. + *

+ + * This method is the normal path for altering a Node, because it does the + * proper default edge maintenance. It also immediately 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 def->use 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 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; iuses, by setting all of its defs * 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; iMonotonic @@ -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 chapter03/README.md + */ +public class ScopeNode extends Node { + + /** + * A Stack of symbol tables; a symbol table is a map from names to node indices. + */ + public final Stack> _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 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. + *

+ * This is an expensive operation. + */ + public String[] reverseNames() { + String[] names = new String[nIns()]; + for( HashMap 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 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. + *

+ * @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); + } + + 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/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 49edfb5b..311ca23b 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -40,7 +40,7 @@ public class Chapter01Test { new Parser("ret").parse(); fail(); } catch( RuntimeException e ) { - assertEquals("Syntax error, expected a statement: ret",e.getMessage()); + assertEquals("Syntax error, expected =: ",e.getMessage()); } } @@ -82,7 +82,7 @@ public class Chapter01Test { new Parser("return100").parse(); fail(); } catch( RuntimeException e ) { - assertEquals("Syntax error, expected a statement: return100",e.getMessage()); + assertEquals("Syntax error, expected =: ",e.getMessage()); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/src/test/java/com/seaofnodes/simple/Chapter02Test.java index 36e62f9b..60ee8874 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -10,8 +10,8 @@ public class Chapter02Test { @Test public void testParseGrammar() { - 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(); diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java new file mode 100644 index 00000000..bdb1d9ea --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -0,0 +1,67 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter03Test { + + @Test + public void testVarDecl() { + Parser parser = new Parser("int a=1; return a;"); + ReturnNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testVarAdd() { + Parser parser = new Parser("int a=1; int b=2; return a+b;"); + ReturnNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testVarScope() { + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); + ReturnNode ret = parser.parse(); + assertEquals("return 4;", ret.print()); + } + + @Test + public void testVarScopeNoPeephole() { + 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()); + } + + @Test + public void testVarDist() { + Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;"); + ReturnNode ret = parser.parse(); + assertEquals("return 8;", ret.print()); + } + + @Test + public void testSelfAssign() { + try { + new Parser("int a=a; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'a'",e.getMessage()); + } + } + + @Test + public void testBad1() { + try { + new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected }: ",e.getMessage()); + } + } + +} -- cgit v1.2.3