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>

5 files changed, 93 insertions, 23 deletions

diff --git a/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
index f3942edb..01b5aeeb 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -146,7 +146,7 @@ public class GraphVisualizer {
     // Walk the node edges
     private void nodeEdges(StringBuilder sb, Collection<Node> all) {
         // All them edge labels
-	sb.append("\tedge [ fontname=Helvetica, fontsize=8 ];\n");
+        sb.append("\tedge [ fontname=Helvetica, fontsize=8 ];\n");
         for( Node n : all ) {
             // Do not display the Constant->Start edge;
             // ProjNodes handled by Multi;
@@ -155,16 +155,12 @@ public class GraphVisualizer {
                 continue;
             int i=0;
             for( Node def : n._inputs ) {
-                // Do not draw the Phi->Region edge (in red); instead Phis are
-                // on a line with their Region, and we draw an invisible line
-                // from the Region to the Phi, to force all the Phis to the
-                // right of the Region.
                 if( n instanceof PhiNode && def instanceof RegionNode ) {
-                    sb.append('\t').append(def.uniqueName());
+                    // Draw a dotted use->def edge from Phi to Region.
+                    sb.append('\t').append(n.uniqueName());
                     sb.append(" -> ");
-                    sb.append(n.uniqueName());
-                    sb.append(" [style=invis]\n");
-                    
+                    sb.append(def.uniqueName());
+                    sb.append(" [style=dotted taillabel=").append(i).append("];\n");
                 } else if( def != null ) {
                     // Most edges land here use->def
                     sb.append('\t').append(n.uniqueName()).append(" -> ");
@@ -176,7 +172,7 @@ public class GraphVisualizer {
                     sb.append("[taillabel=").append(i);
                     // control edges are colored red
                     if( def.isCFG() )
-                        sb.append("; color=red");
+                        sb.append(" color=red");
                     sb.append("];\n");
                 }
                 i++;
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
index 8bf343b3..a132fce0 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
@@ -94,6 +94,7 @@ public class Parser {
             _scope.define(CTRL , new ProjNode(START, 0, CTRL ).peephole());
             _scope.define("arg", new ProjNode(START, 1, "arg").peephole());
             parseBlock();
+            if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken());
             return STOP;
         }
         finally {
@@ -129,7 +130,7 @@ public class Parser {
      * Parses a statement
      *
      * <pre>
-     *     returnStatement | declStatement | blockStatement | expressionStatement
+     *     returnStatement | declStatement | blockStatement | ifStatement | expressionStatement
      * </pre>
      * @return a {@link Node} or {@code null}
      */
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java
index 834f4c11..533155d9 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java
@@ -20,7 +20,7 @@ public class MinusNode extends Node {
     @Override
     public Type compute() {
         if (in(1)._type instanceof TypeInteger i0)
-            return TypeInteger.constant(-i0.value());
+            return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0;
         return TypeBot.BOTTOM;
     }
 
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 64061030..61fac118 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -105,6 +105,10 @@ public class ScopeNode extends Node {
      * The new Scope is a full-fledged Node with proper use<->def edges.
      */
     public ScopeNode dup() {
+        // Our goals are:
+        // 1) duplicate the name bindings of the ScopeNode across all stack levels
+        // 2) Make the new ScopeNode a user of all the nodes bound
+        // 3) Ensure that the order of defs is the same to allow easy merging
         ScopeNode dup = new ScopeNode();
         for( HashMap<String, Integer> tab : _scopes )
             dup._scopes.push(new HashMap<>(tab));
@@ -114,6 +118,14 @@ public class ScopeNode extends Node {
         return dup;
     }
 
+    /**
+     * Merges the names whose node bindings differ, by creating Phi node for such names
+     * The names could occur at all stack levels, but a given name can only differ in the
+     * innermost stack level where the name is bound.
+     *
+     * @param that The ScopeNode to be merged into this
+     * @return A new Region node representing the merge point
+     */
     public RegionNode mergeScopes(ScopeNode that) {
         RegionNode r = (RegionNode)ctrl(new RegionNode(null,ctrl(), that.ctrl()).peephole());
         for( int i=1; i<nIns(); i++ )
diff --git a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java
index 0516fb73..e40136bd 100644
--- a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java
+++ b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java
@@ -21,8 +21,7 @@ else {
     #showGraph;
 }
 #showGraph;
-return a;
-""");
+return a;""");
         StopNode ret = parser.parse(true);
         assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString());
     }
@@ -36,50 +35,94 @@ if (arg == 1) {
     b = 3;
     c = 4;
 }
-return c;
-                """, TypeInteger.BOT);
-        StopNode ret = parser.parse();
+return c;""", TypeInteger.BOT);
+        StopNode ret = parser.parse(true);
         assertEquals("return Phi(Region16,4,3);", ret.toString());
     }
     
     @Test
     public void testChapter5Return2() {
-        Parser parser = new Parser("if( arg==1 ) return 3; else return 4; #showGraph;", TypeInteger.BOT);
+        Parser parser = new Parser("""
+if( arg==1 ) 
+    return 3; 
+else 
+    return 4; 
+#showGraph;""", TypeInteger.BOT);
         StopNode stop = parser.parse();
         assertEquals("Stop[ return 3; return 4; ]", stop.toString());
     }
     
     @Test
     public void testChapter5IfMergeB() {
-        Parser parser = new Parser("int a=arg+1; int b=0; if( arg==1 ) b=a; else b=a+1; return a+b;");
+        Parser parser = new Parser("""
+int a=arg+1;
+int b=0;
+if( arg==1 )
+    b=a;
+else
+    b=a+1;
+return a+b;""");
         StopNode ret = parser.parse(true);
         assertEquals("return ((arg*2)+Phi(Region20,2,3));", ret.toString());
     }
 
     @Test
     public void testChapter5IfMerge2() {
-        Parser parser = new Parser("int a=arg+1; int b=arg+2; if( arg==1 ) b=b+a; else a=b+1; return a+b;");
+        Parser parser = new Parser("""
+int a=arg+1;
+int b=arg+2;
+if( arg==1 )
+    b=b+a;
+else
+    a=b+1;
+return a+b;""");
         StopNode ret = parser.parse(true);
         assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region31,4,5));", ret.toString());
     }
 
     @Test
     public void testChapter5Merge3() {
-        Parser parser = new Parser("int a=1; if( arg==1 ) if( arg==2 ) a=2; else a=3; else if( arg==3 ) a=4; else a=5; return a; #showGraph;", TypeInteger.BOT);
+        Parser parser = new Parser("""
+int a=1;
+if( arg==1 )
+    if( arg==2 )
+        a=2;
+    else
+        a=3;
+else if( arg==3 )
+    a=4;
+else
+    a=5;
+return a;
+#showGraph;""", TypeInteger.BOT);
         StopNode stop = parser.parse();
         assertEquals("return Phi(Region33,Phi(Region21,2,3),Phi(Region31,4,5));", stop.toString());
     }
 
     @Test
     public void testChapter5Merge4() {
-        Parser parser = new Parser("int a=0;int b=0;if(arg)a=1;if(arg==0)b=2;return arg+a+b;#showGraph;", TypeInteger.BOT);
+        Parser parser = new Parser("""
+int a=0;
+int b=0;
+if( arg )
+    a=1;
+if( arg==0 )
+    b=2;
+return arg+a+b;
+#showGraph;""", TypeInteger.BOT);
         StopNode stop = parser.parse();
         assertEquals("return ((arg+Phi(Region13,1,0))+Phi(Region22,2,0));", stop.toString());
     }
 
     @Test
     public void testChapter5Merge5() {
-        Parser parser = new Parser("int a=arg==2;if(arg==1)a=arg==3;return a;");
+        Parser parser = new Parser("""
+int a=arg==2;
+if( arg==1 )
+{
+    a=arg==3;
+}
+return a;""");
         StopNode ret = parser.parse(true);
         assertEquals("return (arg==Phi(Region16,3,2));", ret.toString());
     }
@@ -259,6 +302,13 @@ return c;
             assertEquals("Undefined name 'inta'",e.getMessage());
         }
     }
+
+    @Test
+    public void testChapter4Bug4() {
+        Parser parser = new Parser("return -arg;");
+        StopNode ret = parser.parse();
+        assertEquals("return (-arg);", ret.print());
+    }
     
     @Test
     public void testVarDecl() {
@@ -440,4 +490,15 @@ return c;
             assertEquals("Syntax error, expected }: ",e.getMessage());
         }
     }
+
+    @Test
+    public void testBad7() {
+        try {
+            new Parser("return 1;}").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Syntax error, unexpected }",e.getMessage());
+        }
+    }
+
 }