Chapter 01 implementation

5 files changed, 183 insertions, 104 deletions

diff --git a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java
index bf9791a8..2feeddf9 100644
--- a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java
@@ -7,81 +7,92 @@ import java.text.ParseException;
 
 /**
  * The Parser converts a Simple source program to the Sea of Nodes intermediate representation
- * directly in one pass. There is no intermediate Abstract Syntax Tree structure. The parser also
- * does the lexical analysis of the input source.
+ * directly in one pass. There is no intermediate Abstract Syntax Tree structure.
+ *
+ * This is a simple recursive descent parser. All lexical analysis is done here as well.
  */
 public class Parser {
 
-    private Token currentToken;
+    /**
+     * Current token from lexer
+     */
+    private Token _curTok;
+
     private final NodeIDGenerator _idGenerator;
+
     private StartNode _startNode;
 
     public Parser() {
         _idGenerator = new NodeIDGenerator();
     }
 
-    public Node parse(String source) {
+    public StartNode parse(String source) {
         Lexer lexer = new Lexer(source);
-        _startNode = new StartNode(_idGenerator, new Node[0]);
         nextToken(lexer);
         return parseProgram(lexer);
     }
 
-    private Node parseProgram(Lexer lexer) {
+    private StartNode parseProgram(Lexer lexer) {
+        _startNode = new StartNode(_idGenerator);
         parseReturnStatement(lexer);
         return _startNode;
     }
 
-    private void nextToken(Lexer lexer) {
-        currentToken = lexer.next();
-    }
-
-    private boolean isToken(Token token, String value) {
-        return token._str.equals(value);
-    }
-
-    private void error(Token t, String errorMessage) {
-        throw new RuntimeException(errorMessage + ": " + t.toString());
-    }
-
-    private void matchPunctuation(Lexer lexer, String value) {
-        if (currentToken._kind == Token.Kind.PUNCT && isToken(currentToken, value)) {
-            nextToken(lexer);
-        } else {
-            error(currentToken, "syntax error, expected " + value + " got " + currentToken._str);
-        }
+    /**
+     * Parses return statement.
+     *
+     * <pre>
+     *     return expr ;
+     * </pre>
+     */
+    private ReturnNode parseReturnStatement(Lexer lexer) {
+        matchIdentifier(lexer, "return");
+        var returnExpr = parseExpression(lexer);
+        matchPunctuation(lexer, ";");
+        return new ReturnNode(_idGenerator, _startNode, returnExpr);
     }
 
-    private void matchIdentifier(Lexer lexer, String identifier) {
-        if (currentToken._kind == Token.Kind.IDENT && isToken(currentToken, identifier)) {
-            nextToken(lexer);
-        } else {
-            error(currentToken, "syntax error, expected " + identifier);
-        }
+    /**
+     * Parse an expression of the form:
+     *
+     * <pre>
+     *     expr : primaryExpr
+     * </pre>
+     */
+    private Node parseExpression(Lexer lexer) {
+        return parsePrimary(lexer);
     }
 
+    /**
+     * Parse a primary expression:
+     *
+     * <pre>
+     *     primaryExpr : nestedExpr | integerLiteral
+     * </pre>
+     */
     private Node parsePrimary(Lexer lexer) {
-        switch (currentToken._kind) {
+        switch (_curTok._kind) {
             case PUNCT -> {
                 /* Nested expression */
                 return parseNestedExpr(lexer);
             }
             case NUM -> {
-                return parseNumberConstant(lexer);
+                return parseIntegerLiteral(lexer);
             }
             default -> {
-                error(currentToken, "syntax error, expected nested expr or integer literal");
+                error(_curTok, "syntax error, expected nested expr or integer literal");
                 return null;
             }
         }
     }
 
-    private ConstantNode parseNumberConstant(Lexer lexer) {
-        var constantNode = new ConstantNode(_idGenerator, currentToken._num.longValue(), _startNode);
-        nextToken(lexer);
-        return constantNode;
-    }
-
+    /**
+     * Parse nested expression:
+     *
+     * <pre>
+     *     nestedExpr : ( expr )
+     * </pre>
+     */
     private Node parseNestedExpr(Lexer lexer) {
         matchPunctuation(lexer, "(");
         nextToken(lexer);
@@ -90,13 +101,53 @@ public class Parser {
         return node;
     }
 
-    private Node parseReturnStatement(Lexer lexer) {
-        matchIdentifier(lexer, "return");
-        var returnExpr = parsePrimary(lexer);
-        matchPunctuation(lexer, ";");
-        return new ReturnNode(_idGenerator, _startNode, returnExpr);
+    /**
+     * Parse integer literal
+     *
+     * <pre>
+     *     integerLiteral: [1-9][0-9]*
+     * </pre>
+     */
+    private ConstantNode parseIntegerLiteral(Lexer lexer) {
+        var constantNode = new ConstantNode(_idGenerator, _curTok._num.longValue(), _startNode);
+        nextToken(lexer);
+        return constantNode;
+    }
+
+    //////////////////////////////////
+    // Utilities for lexical analysis
+
+    private void nextToken(Lexer lexer) {
+        _curTok = lexer.next();
+    }
+
+    private boolean isToken(Token token, String value) {
+        return token._str.equals(value);
+    }
+
+    private void error(Token t, String errorMessage) {
+        throw new RuntimeException(errorMessage + ": " + t.toString());
     }
 
+    private void matchPunctuation(Lexer lexer, String value) {
+        if (_curTok._kind == Token.Kind.PUNCT && isToken(_curTok, value)) {
+            nextToken(lexer);
+        } else {
+            error(_curTok, "syntax error, expected " + value + " got " + _curTok._str);
+        }
+    }
+
+    private void matchIdentifier(Lexer lexer, String identifier) {
+        if (_curTok._kind == Token.Kind.IDENT && isToken(_curTok, identifier)) {
+            nextToken(lexer);
+        } else {
+            error(_curTok, "syntax error, expected " + identifier);
+        }
+    }
+
+    ////////////////////////////////////
+    // Lexer components
+
     static class Token {
 
         enum Kind {
@@ -145,12 +196,18 @@ public class Parser {
 
     static class Lexer {
 
+        /**
+         * Input buffer
+         */
         private final char[] _input;
         /**
          * Tracks current position in input buffer
          */
         private int _position = 0;
-        private char _curCh = ' ';
+        /**
+         * Current character
+         */
+        private char _cur = ' ';
 
         private final NumberFormat numberFormat;
 
@@ -171,7 +228,7 @@ public class Parser {
         }
 
         private boolean nextToken() {
-            _curCh = advance();
+            _cur = advance();
             return true;
         }
 
@@ -186,7 +243,7 @@ public class Parser {
         }
 
         private void skipWhitespace() {
-            while (isWhiteSpace(_curCh))
+            while (isWhiteSpace(_cur))
                 nextToken();
         }
 
@@ -195,15 +252,15 @@ public class Parser {
          * where n is a digit
          */
         private Token parseNumber() {
-            assert Character.isDigit(_curCh);
+            assert Character.isDigit(_cur);
             StringBuilder sb = new StringBuilder();
-            sb.append(_curCh);
-            while (nextToken() && Character.isDigit(_curCh))
-                sb.append(_curCh);
-            if (_curCh == '.') {
-                sb.append(_curCh);
-                while (nextToken() && Character.isDigit(_curCh))
-                    sb.append(_curCh);
+            sb.append(_cur);
+            while (nextToken() && Character.isDigit(_cur))
+                sb.append(_cur);
+            if (_cur == '.') {
+                sb.append(_cur);
+                while (nextToken() && Character.isDigit(_cur))
+                    sb.append(_cur);
             }
             String str = sb.toString();
             Number number = parseNumber(str);
@@ -227,11 +284,11 @@ public class Parser {
         }
 
         private Token parseIdentifier() {
-            assert isIdentifierStart(_curCh);
+            assert isIdentifierStart(_cur);
             StringBuilder sb = new StringBuilder();
-            sb.append(_curCh);
-            while (nextToken() && isIdentifierLetter(_curCh))
-                sb.append(_curCh);
+            sb.append(_cur);
+            while (nextToken() && isIdentifierLetter(_cur))
+                sb.append(_cur);
             return Token.newIdent(sb.toString());
         }
 
@@ -240,14 +297,14 @@ public class Parser {
          */
         public Token next() {
             skipWhitespace();
-            if (_curCh == 0)
+            if (_cur == 0)
                 return Token.EOF;
-            if (Character.isDigit(_curCh))
+            if (Character.isDigit(_cur))
                 return parseNumber();
-            if (isIdentifierLetter(_curCh))
+            if (isIdentifierLetter(_cur))
                 return parseIdentifier();
-            Token token = Token.newPunct(Character.toString(_curCh));
-            _curCh = ' ';
+            Token token = Token.newPunct(Character.toString(_cur));
+            _cur = ' ';
             return token;
         }
     }
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index d2f51cd8..31718a1d 100644
--- a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -1,8 +1,17 @@
 package com.seaofnodes.simple.node;
 
+/**
+ * The Constant node represents a constant value. At present, the only constants that we allow are integer literals; therefore the Constant node contains
+ * an integer value. As we add other types of constants, we will need to refactor how we represent Constant nodes.
+ * <p>
+ * The Constant node has no inputs. However, we set the Start node as an input to the Constant node to enable forward graph walk. This edge carries no semantic meaning,
+ * it is present _solely_ to allow visitation.
+ * <p>
+ * The Constant node's output is the value stored in it.
+ */
 public class ConstantNode extends Node {
 
-    long _value;
+    public final long _value;
 
     public ConstantNode(NodeIDGenerator idGenerator, long value, StartNode startNode) {
         super(idGenerator, OP_CONSTANT, startNode);
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java
index c3562b5d..e78ab19a 100644
--- a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -11,10 +11,18 @@ import java.util.List;
  */
 public class Node {
 
+    /**
+     * @see StartNode
+     */
     static final byte OP_START = 1;
-    static final byte OP_REGION = 2;
-    static final byte OP_RETURN = 3;
-    static final byte OP_CONSTANT = 4;
+    /**
+     * @see ReturnNode
+     */
+    static final byte OP_RETURN = 2;
+    /**
+     * @see ConstantNode
+     */
+    static final byte OP_CONSTANT = 3;
 
     /**
      * The opcode for this node
@@ -22,30 +30,43 @@ public class Node {
     public final byte _opCode;
 
     /**
-     * Each node has a unique ID within a compilation context
+     * Each node has a unique dense Node ID within a compilation context
+     * The ID is useful for debugging, for using as an offset in a bitvector,
+     * as well as for computing equality of nodes (to be implemented later).
      */
     public final int _nid;
 
     /**
-     * Inputs to the node.
-     *
+     * Inputs to the node. These are use-def references to Nodes.
+     * <p>
      * Generally fixed length, ordered, nulls allowed, no unused trailing space.
-     * The first input (offset 0) must be a Control node.
+     * The first input (offset 0) must be a Control nodes.
      * @see Control
      */
     public final List<Node> _inputs;
 
-    public final List<Node> _refs = new ArrayList<>();
+    /**
+     * Outputs reference Nodes that are not null and
+     * have this Node as an input. These nodes are users of this
+     * node, thus these are def-use references to Nodes.
+     * <p>
+     * Note that the outputs are derived from inputs, it appears that
+     * outputs are therefore a performance optimization to make it easier to
+     * traverse the graph. The Sea of Nodes documentation in chapter 1 does not
+     * mention these outputs list.
+     */
+    public final List<Node> _outputs;
 
     protected Node(NodeIDGenerator idGenerator, byte opCode, Node ...inputs)
     {
-        _nid = idGenerator.newNodeID();
+        _nid = idGenerator.newNodeID(); // allocate unique dense ID
         _opCode = opCode;
         _inputs = Arrays.asList(inputs);
+        _outputs = new ArrayList<>();
         for (int i = 0; i < _inputs.size(); i++) {
             Node n = _inputs.get(i);
             if (n != null)
-                n._refs.add(this);
+                n._outputs.add(this);
         }
     }
 
@@ -54,9 +75,13 @@ public class Node {
      * @param i Offset of the input node
      * @return Input node or null
      */
-    public Node in(int i) { return _inputs != null ? _inputs.get(i) : null; }
+    public Node in(int i) { return _inputs.get(i); }
 
-    public int numInputs() { return _inputs != null ? _inputs.size() : 0; }
+    public int numInputs() { return _inputs.size(); }
+
+    public Node out(int i) { return _outputs.get(i); }
+
+    public int numOutputs() { return _outputs.size(); }
 
     /**
      * Is this a control node, all control nodes are marked with
@@ -64,32 +89,7 @@ public class Node {
      */
     public boolean isControl() { return this instanceof Control; }
 
-    /**
-     * Hash is function of this nodes type, its _nid and
-     * inputs, or opcode + input_nids
-     */
-    @Override
-    public int hashCode() {
-        int sum = _opCode;
-        for (int i = 0; i < numInputs(); i++)
-            if (in(i) != null)
-                sum ^= in(i)._nid;
-        return sum;
-    }
-
-    /**
-     * Equals is opcode + input nids.
-     * Note that nodes are compared by reference.
+    /*
+     * hashCode and equals implementation to be added in later chapter.
      */
-    @Override
-    public boolean equals(Object o) {
-        if (this == o) return true;
-        if (!(o instanceof Node n)) return false;
-        if (_opCode != n._opCode) return false;
-        if (numInputs() != n.numInputs()) return false;
-        for (int i = 0; i < numInputs(); i++)
-            if (in(i) != n.in(i))
-                return false;
-        return true;
-    }
 }
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index 9c017eef..0b62cd4c 100644
--- a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -1,5 +1,13 @@
 package com.seaofnodes.simple.node;
 
+/**
+ * The Return node has two inputs. The first input is a control node. The second input is the data node that supplies the return value.
+ * <p>
+ * In this presentation, the Return node functions as the Stop node, since we are compiling a single unnamed function.
+ * A separate Stop node is not necessary. Compiling multiple functions is covered in Chapter 9: Functions and Calls.
+ * <p>
+ * The output of the Return node is the value it obtained from the data node.
+ */
 public class ReturnNode extends Node implements Control {
 
     public ReturnNode(NodeIDGenerator idGenerator, Node... inputs) {
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 4ae7f71a..7a9233a8 100644
--- a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -1,5 +1,10 @@
 package com.seaofnodes.simple.node;
 
+/**
+ * The Start node represents the start of the function. For now, we do not have any values in the Start node, this is because our function does not
+ * yet accept parameters. When we add parameters, the value of the Start node will be a tuple, and will require Projection nodes to extract the values.
+ * We discuss this in detail in Chapter 9: Functions and Calls.
+ */
 public class StartNode extends Node implements Control {
 
     public StartNode(NodeIDGenerator idGenerator, Node... inputs) {