diff options
Diffstat (limited to 'chapter03/src/main/java/com')
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; + } + + +} |