Chapter 1: Introduction

Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: hadha <helsgithub15@gmail.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: Jun Kawasaki <jun784@gmail.com>

7 files changed, 448 insertions, 0 deletions

diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java
new file mode 100644
index 00000000..c2ea3734
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/Parser.java
@@ -0,0 +1,253 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+
+/**
+ * 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.
+ * <p>
+ * This is a simple recursive descent parser. All lexical analysis is done here as well.
+ */
+public class Parser {
+
+    public int pos() { return _lexer._position; }
+
+
+    /**
+     * A Global Static, unique to each compilation.  This is a public, so we
+     * can make constants everywhere without having to thread the StartNode
+     * through the entire parser and optimizer.
+     * <p>
+     * To make the compiler multithreaded, this field will have to move into a TLS.
+     */
+    public static StartNode START;
+
+    // The Lexer.  Thin wrapper over a byte[] buffer with a cursor.
+    private final Lexer _lexer;
+
+
+    public Parser(String source) {
+        _lexer = new Lexer(source);
+        Node.reset();
+        START = new StartNode();
+    }
+
+    public ReturnNode parse() {
+        var ret = (ReturnNode) parseStatement();
+        if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken());
+        return ret;
+    }
+
+    /**
+     * Parses a statement
+     *
+     * <pre>
+     *     returnStatement
+     * </pre>
+     * @return a {@link Node} or {@code null}
+     */
+    private Node parseStatement() {
+        if (matchx("return")) return parseReturn();
+        throw errorSyntax("a statement");
+    }
+
+    /**
+     * Parses a return statement; "return" already parsed.
+     *
+     * <pre>
+     *     'return' expr ;
+     * </pre>
+     * @return an expression {@link Node}, never {@code null}
+     */
+    private ReturnNode parseReturn() {
+        var expr = require(parseExpression(), ";");
+        return new ReturnNode(START, expr);
+    }
+
+    /**
+     * Parse an expression of the form:
+     *
+     * <pre>
+     *     expr : primaryExpr
+     * </pre>
+     * @return an expression {@link Node}, never {@code null}
+     */
+    private Node parseExpression() {
+        return parsePrimary();
+    }
+
+    /**
+     * Parse a primary expression:
+     *
+     * <pre>
+     *     primaryExpr : integerLiteral
+     * </pre>
+     */
+    private Node parsePrimary() {
+        _lexer.skipWhiteSpace();
+        if (_lexer.isNumber())
+            return parseIntegerLiteral();
+        throw error("Syntax error, expected integer literal");
+    }
+
+    /**
+     * Parse integer literal
+     *
+     * <pre>
+     *     integerLiteral: [1-9][0-9]* | [0]
+     * </pre>
+     */
+    private ConstantNode parseIntegerLiteral() {
+        return new ConstantNode(_lexer.parseNumber());
+    }
+
+    //////////////////////////////////
+    // Utilities for lexical analysis
+
+    // Return true and skip if "syntax" is next in the stream.
+    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); }
+
+    // Require an exact match
+    private void require(String syntax) { require(null, syntax); }
+    private Node require(Node n, String syntax) {
+        if (match(syntax)) return n;
+        throw errorSyntax(syntax);
+    }
+
+    RuntimeException errorSyntax(String syntax) {
+        return error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken());
+    }
+
+    static RuntimeException error(String errorMessage) {
+        return new RuntimeException(errorMessage);
+    }
+
+    ////////////////////////////////////
+    // Lexer components
+
+    private static class Lexer {
+
+        // Input buffer; an array of text bytes read from a file or a string
+        private final byte[] _input;
+        // Tracks current position in input buffer
+        private int _position = 0;
+
+        /**
+         * Record the source text for lexing
+         */
+        public Lexer(String source) {
+            this(source.getBytes());
+        }
+
+        /**
+         * Direct from disk file source
+         */
+        public Lexer(byte[] buf) {
+            _input = buf;
+        }
+
+        // True if at EOF
+        private boolean isEOF() {
+            return _position >= _input.length;
+        }
+
+        // Peek next character, or report EOF
+        private char peek() {
+            return isEOF() ? Character.MAX_VALUE   // Special value that causes parsing to terminate
+                    : (char) _input[_position];
+        }
+
+        private char nextChar() {
+            char ch = peek();
+            _position++;
+            return ch;
+        }
+
+        // True if a white space
+        private boolean isWhiteSpace() {
+            return peek() <= ' '; // Includes all the use space, tab, newline, CR
+        }
+
+        /**
+         * Return the next non-white-space character
+         */
+        private void skipWhiteSpace() {
+            while (isWhiteSpace()) _position++;
+        }
+
+
+        // Return true, if we find "syntax" after skipping white space; also
+        // then advance the cursor past syntax.
+        // Return false otherwise, and do not advance the cursor.
+        boolean match(String syntax) {
+            skipWhiteSpace();
+            int len = syntax.length();
+            if (_position + len > _input.length) return false;
+            for (int i = 0; i < len; i++)
+                if ((char) _input[_position + i] != syntax.charAt(i))
+                    return false;
+            _position += len;
+            return true;
+        }
+
+        boolean matchx(String syntax) {
+            if( !match(syntax) ) return false;
+            if( !isIdLetter(peek()) ) return true;
+            _position -= syntax.length();
+            return false;
+        }
+
+        // Used for errors
+        String getAnyNextToken() {
+            if (isEOF()) return "";
+            if (isIdStart(peek())) return parseId();
+            if (isNumber(peek())) return parseNumberString();
+            if (isPunctuation(peek())) return parsePunctuation();
+            return String.valueOf(peek());
+        }
+
+        boolean isNumber() {return isNumber(peek());}
+        boolean isNumber(char ch) {return Character.isDigit(ch);}
+
+        private long parseNumber() {
+            String snum = parseNumberString();
+            if (snum.length() > 1 && snum.charAt(0) == '0')
+                throw error("Syntax error: integer values cannot start with '0'");
+            return Long.parseLong(snum);
+        }
+        private String parseNumberString() {
+            int start = _position;
+            while (isNumber(nextChar())) ;
+            return new String(_input, start, --_position - start);
+        }
+
+        // First letter of an identifier
+        private boolean isIdStart(char ch) {
+            return Character.isAlphabetic(ch) || ch == '_';
+        }
+
+        // All characters of an identifier, e.g. "_x123"
+        private boolean isIdLetter(char ch) {
+            return Character.isLetterOrDigit(ch) || ch == '_';
+        }
+
+        private String parseId() {
+            int start = _position;
+            while (isIdLetter(nextChar())) ;
+            return new String(_input, start, --_position - start);
+        }
+
+        private boolean isPunctuation(char ch) {
+            return "=;[]<>(){}+-/*!".indexOf(ch) != -1;
+        }
+
+        private String parsePunctuation() {
+            int start = _position;
+            return new String(_input, start, 1);
+        }
+    }
+
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
new file mode 100644
index 00000000..01d9cbe1
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -0,0 +1,29 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.Parser;
+
+/**
+ * A Constant node represents a constant value.  At present, the only constants
+ * that we allow are integer literals; therefore Constants contain an integer
+ * value. As we add other types of constants, we will refactor how we represent
+ * Constants.
+ * <p>
+ * Constants have no semantic inputs. However, we set Start as an input to
+ * Constants to enable a forward graph walk.  This edge carries no semantic
+ * meaning, and it is present <em>solely</em> to allow visitation.
+ * <p>
+ * The Constant's value is the value stored in it.
+ */
+public class ConstantNode extends Node {
+
+    @Override public String label() { return "Con"; }
+    @Override protected String format() { return Long.toString(_value); }
+    @Override protected String repeatName() { return null; }
+
+    public final long _value;
+
+    public ConstantNode(long value) {
+        super(Parser.START);
+        _value = value;
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
new file mode 100644
index 00000000..ed88e86e
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -0,0 +1,71 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.print.BaseNode;
+
+import java.util.*;
+
+/**
+ * All Nodes in the Sea of Nodes IR inherit from the Node class.
+ * The Node class provides common functionality used by all subtypes.
+ * Subtypes of Node specialize by overriding methods.
+ */
+public abstract class Node extends BaseNode<Node> {
+
+    /**
+     * Inputs to the node. These are use-def references to Nodes.
+     * <p>
+     * Generally fixed length, ordered, nulls allowed, no unused trailing space.
+     * Ordering is required because e.g. "a/b" is different from "b/a".
+     * The first input (offset 0) is often a {@link #isCFG} node.
+     */
+    public final ArrayList<Node> _inputs;
+
+    /**
+     * 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>
+     * Outputs directly match inputs, making a directed graph that can be
+     * walked in either direction.  These outputs are typically used for
+     * efficient optimizations but otherwise have no semantics meaning.
+     */
+    public final ArrayList<Node> _outputs;
+
+    /**
+     * A private Global Static mutable counter, for unique node id generation.
+     * To make the compiler multi-threaded, this field will have to move into a TLS.
+     * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values.
+     * */
+    private static int UNIQUE_ID = 1;
+
+    protected Node(Node... inputs) {
+        super(UNIQUE_ID++); // allocate unique dense ID
+        _inputs = new ArrayList<>();
+        Collections.addAll(_inputs,inputs);
+        _outputs = new ArrayList<>();
+        for( Node n : _inputs )
+            if( n != null )
+                n._outputs.add( this );
+    }
+
+    /**
+     * Gets the ith input node
+     * @param i Offset of the input node
+     * @return Input node or null
+     */
+    public Node in(int i) { return _inputs.get(i); }
+
+    public int nIns() { return _inputs.size(); }
+
+    public Node out(int i) { return _outputs.get(i); }
+
+    public int nOuts() { return _outputs.size(); }
+
+    public boolean isUnused() { return nOuts() == 0; }
+
+    /**
+     * 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; }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
new file mode 100644
index 00000000..85bbc83f
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -0,0 +1,23 @@
+package com.seaofnodes.simple.node;
+
+/**
+ * The Return node has two inputs.  The first input is a control node and the
+ * second is the data node that supplies the return value.
+ * <p>
+ * In this presentation, Return functions as a Stop node, since multiple <code>return</code> statements are not possible.
+ * The Stop node will be introduced in Chapter 6 when we implement <code>if</code> statements.
+ * <p>
+ * The Return's output is the value from the data node.
+ */
+public class ReturnNode extends Node {
+
+    public ReturnNode(Node ctrl, Node data) {
+        super(ctrl, data);
+    }
+
+    public Node ctrl() { return in(0); }
+    public Node expr() { return in(1); }
+
+    @Override public boolean isCFG() { return true; }
+
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java
new file mode 100644
index 00000000..04bd6bb4
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -0,0 +1,16 @@
+package com.seaofnodes.simple.node;
+
+/**
+ * The Start node represents the start of the function.  For now, we do not have any inputs to Start because our function does not
+ * yet accept parameters.  When we add parameters the value of Start will be a tuple, and will require Projections to extract the values.
+ * We discuss this in detail in Chapter 9: Functions and Calls.
+ */
+public class StartNode extends Node {
+
+    public StartNode(/*arguments go here*/) {
+        super();
+    }
+
+    @Override public boolean isCFG() { return true; }
+
+}
diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
new file mode 100644
index 00000000..20ee6aed
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
@@ -0,0 +1,21 @@
+package com.seaofnodes.simple.print;
+
+import com.seaofnodes.graph.GraphAdapter;
+import com.seaofnodes.graph.GraphSnapshot.*;
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.node.Node;
+
+/** Chapter 1's view of the IR; browser, transport and layout are shared. */
+public class SimpleGraphAdapter extends GraphAdapter<Node> {
+
+    @Override protected Kind kind(Node n) {
+        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( 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
new file mode 100644
index 00000000..1c78e4dd
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java
@@ -0,0 +1,35 @@
+package com.seaofnodes.simple.print;
+
+import com.seaofnodes.graph.GraphCapture;
+import com.seaofnodes.graph.GraphViewer;
+import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.node.Node;
+import java.util.ArrayList;
+import java.io.IOException;
+
+/** Chapter 1's compilation context; capture and event bookkeeping are shared. */
+public class SimpleGraphObserver extends GraphCapture<Node> {
+    private Parser _parser;
+    private Node _ret;
+    private String _phase;
+    public SimpleGraphObserver() { super(new SimpleGraphAdapter()); }
+    public static void main(String[] args) throws IOException {
+        GraphViewer.run(new SimpleGraphObserver());
+    }
+    @Override protected void compile(String src) {
+        _parser = new Parser(src);
+        _phase = "Parse";
+        _ret = _parser.parse();
+        phase(_phase);
+    }
+    @Override protected String phase() { return _phase; }
+    @Override protected int pos() { return "Parse".equals(_phase) ? _parser.pos() : -1; }
+    @Override protected void detach() {
+        _parser = null;
+        _ret = null;
+    }
+    @Override protected void roots(ArrayList<Node> roots) {
+        roots.add(Parser.START);
+        roots.add(_ret);
+    }
+}