Backport changes in Chapter 5 to previous chapters and update Chapter5 documentation (#34)

* Backport changes from chapter 5 to older chapters (#30)

* Fix wrong indent

* Backport to chapter 4

* Backport to chapter 3

* Backport to chapter 2

* Backport to chapter 1

* Add if statement to comment (#32)

* Update visuals for chapters 1,2 & 3.
Reenable drawing of edges from constants to Start for these chapters.

* Update visuals for chapters 4.
Revise text to explain the labeling of edges in graphs and that we omit edge from Constant to Start nodes from chapter 4.

* Add code snippets for if statement parsing and the duplication and merging of ScopeNodes.
Explain how scopeNodes are duplicated and merged.

* Add constant check to minus node (#31)

* Fix closing root block with } (#33)

* Backport fix closing root block with } to chapter 4 and 3 (#35)

* Show use-def edge from Phi to Region as dotted edge.
Add example of Phi peephole.
Update visuals.
Add more examples.

* Fix visuals in chapter 1 and README in chapter 4.

* Remove subheading

* Adjust spaces

---------

Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>

6 files changed, 65 insertions, 87 deletions

diff --git a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java
index a71def25..e2c1ca71 100644
--- a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java
@@ -1,20 +1,16 @@
 package com.seaofnodes.simple;
 
-import com.seaofnodes.simple.node.ConstantNode;
-import com.seaofnodes.simple.node.Node;
-import com.seaofnodes.simple.node.ReturnNode;
-import com.seaofnodes.simple.node.StartNode;
+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.
- *
+ * 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 {
 
-    private final Lexer _lexer;
-
     /**
      * A Global Static, unique to each compilation.  This is a public, so we
      * can make constants everywhere without having to thread the StartNode
@@ -24,6 +20,10 @@ public class Parser {
      */
     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();
@@ -31,21 +31,21 @@ public class Parser {
     }
 
     public ReturnNode parse() {
+        require("return");
         return parseReturn();
     }
 
     /**
-     * Parses return statement.
+     * Parses a return statement; "return" already parsed.
      *
      * <pre>
-     *     return expr ;
+     *     'return' expr ;
      * </pre>
+     * @return an expression {@link Node}, never {@code null}
      */
     private ReturnNode parseReturn() {
-        require("return");
-        var returnExpr = parseExpression();
-        require(";");
-        return new ReturnNode(START, returnExpr);
+        var expr = require(parseExpression(), ";");
+        return new ReturnNode(START, expr);
     }
 
     /**
@@ -54,6 +54,7 @@ public class Parser {
      * <pre>
      *     expr : primaryExpr
      * </pre>
+     * @return an expression {@link Node}, never {@code null}
      */
     private Node parseExpression() {
         return parsePrimary();
@@ -81,25 +82,28 @@ public class Parser {
      * </pre>
      */
     private ConstantNode parseIntegerLiteral() {
-        return new ConstantNode(_lexer.parseNumber(), START);
-    }
-
-    static RuntimeException error(String errorMessage) {
-        return new RuntimeException(errorMessage);
+        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);
-    }
+    private boolean match(String syntax) { return _lexer.match(syntax); }
 
     // Require an exact match
-    private void require(String syntax) {
-        if (match(syntax)) return;
-        throw error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken());
+    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);
     }
 
     ////////////////////////////////////
@@ -152,8 +156,7 @@ public class Parser {
          * Return the next non-white-space character
          */
         private void skipWhiteSpace() {
-            while (isWhiteSpace())
-                _position++;
+            while (isWhiteSpace()) _position++;
         }
 
 
@@ -163,8 +166,7 @@ public class Parser {
         boolean match(String syntax) {
             skipWhiteSpace();
             int len = syntax.length();
-            if (_position + len > _input.length)
-                return false;
+            if (_position + len > _input.length) return false;
             for (int i = 0; i < len; i++)
                 if ((char) _input[_position + i] != syntax.charAt(i))
                     return false;
@@ -175,20 +177,13 @@ public class Parser {
         // Used for errors
         String getAnyNextToken() {
             if (isEOF()) return "";
-            if (isIdentifierStart(peek()))
-                return parseIdentifier();
-            if (isPunctuation(peek()))
-                return parsePunctuation();
+            if (isIdStart(peek())) return parseId();
+            if (isPunctuation(peek())) return parsePunctuation();
             return String.valueOf(peek());
         }
 
-        boolean isNumber() {
-            return isNumber(peek());
-        }
-
-        boolean isNumber(char ch) {
-            return Character.isDigit(ch);
-        }
+        boolean isNumber() {return isNumber(peek());}
+        boolean isNumber(char ch) {return Character.isDigit(ch);}
 
         private long parseNumber() {
             int start = _position;
@@ -200,18 +195,18 @@ public class Parser {
         }
 
         // First letter of an identifier 
-        private boolean isIdentifierStart(char ch) {
+        private boolean isIdStart(char ch) {
             return Character.isAlphabetic(ch) || ch == '_';
         }
 
         // All characters of an identifier, e.g. "_x123"
-        private boolean isIdentifierLetter(char ch) {
+        private boolean isIdLetter(char ch) {
             return Character.isLetterOrDigit(ch) || ch == '_';
         }
 
-        private String parseIdentifier() {
+        private String parseId() {
             int start = _position;
-            while (isIdentifierLetter(nextChar())) ;
+            while (isIdLetter(nextChar())) ;
             return new String(_input, start, --_position - start);
         }
 
@@ -222,8 +217,7 @@ public class Parser {
 
         private String parsePunctuation() {
             int start = _position;
-            if (isPunctuation(nextChar())) ;
-            return new String(_input, start, --_position - start);
+            return new String(_input, start, 1);
         }
     }
 
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 7644daf2..21f65084 100644
--- a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -1,5 +1,7 @@
 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
@@ -16,8 +18,8 @@ public class ConstantNode extends Node {
 
     public final long _value;
 
-    public ConstantNode(long value, StartNode startNode) {
-        super(startNode);
+    public ConstantNode(long value) {
+        super(Parser.START);
         _value = value;
     }
 }
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/Control.java b/chapter01/src/main/java/com/seaofnodes/simple/node/Control.java
deleted file mode 100644
index 48cf2b7a..00000000
--- a/chapter01/src/main/java/com/seaofnodes/simple/node/Control.java
+++ /dev/null
@@ -1,9 +0,0 @@
-package com.seaofnodes.simple.node;
-
-
-/**
- * Control interface is a marker interface to be implemented
- * by Control nodes.
- */
-public interface Control {
-}
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 b6ce3160..cf465e94 100644
--- a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -1,7 +1,6 @@
 package com.seaofnodes.simple.node;
 
-import java.util.ArrayList;
-import java.util.Collections;
+import java.util.*;
 
 /**
  * All Nodes in the Sea of Nodes IR inherit from the Node class.
@@ -22,8 +21,7 @@ public abstract class Node {
      * <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 Control node.
-     * @see Control
+     * The first input (offset 0) is often a {@link #isCFG} node.
      */
     public final ArrayList<Node> _inputs;
 
@@ -45,17 +43,16 @@ public abstract class Node {
      * */
     private static int UNIQUE_ID = 1;
 
-    protected Node(Node ...inputs) {
+    protected Node(Node... inputs) {
         _nid = UNIQUE_ID++; // allocate unique dense ID
         _inputs = new ArrayList<>();
         Collections.addAll(_inputs,inputs);
         _outputs = new ArrayList<>();
-        for( Node n : _inputs ) {
+        for( Node n : _inputs )
             if( n != null )
                 n._outputs.add( this );
-      }
     }
-
+    
     /**
      * Gets the ith input node
      * @param i Offset of the input node
@@ -65,23 +62,16 @@ public abstract class Node {
 
     public int nIns() { return _inputs.size(); }
 
-    /**
-     * Gets the ith output node
-     * @param i Offset of the output node
-     * @return Output node (not null)
-     */
-    public Node out(int i) { return _outputs.get(i); }
-
     public int nOuts() { return _outputs.size(); }
 
+    public boolean isUnused() { return nOuts() == 0; }
+
+    public boolean isCFG() { return false; }
+  
+
     /**
      * 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;
-    }
-    /*
-     * hashCode and equals implementation to be added in later chapter.
-     */
+    public static void reset() { UNIQUE_ID = 1; }
 }
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 a2321e2b..5e083cf2 100644
--- a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -9,17 +9,15 @@ package com.seaofnodes.simple.node;
  * <p>
  * The Return's output is the value from the data node.
  */
-public class ReturnNode extends Node implements Control {
+public class ReturnNode extends Node {
 
     public ReturnNode(Node ctrl, Node data) {
         super(ctrl, data);
     }
 
-    public Node ctrl() {
-        return in(0);
-    }
+    public Node ctrl() { return in(0); }
+    public Node expr() { return in(1); }
 
-    public Node expr() {
-        return in(1);
-    }
+    @Override public boolean isCFG() { return true; }
+  
 }
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 c29ba53c..04bd6bb4 100644
--- a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -5,9 +5,12 @@ package com.seaofnodes.simple.node;
  * 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 implements Control {
+public class StartNode extends Node {
 
     public StartNode(/*arguments go here*/) {
         super();
     }
+
+    @Override public boolean isCFG() { return true; }
+
 }