Chapter 2 (#4)

* Start on Chapter 2.

* Start on Chapter 2.

* Refactor

* Refactor

* Initial attempt at peephole opt for add operation

* cleanup unused import

* Start on graph visualizer

* Start on graph visualizer

* Rework chapter 2

Add a short discourse on the Types, and provide a Bottom type.

Make a final toString; require each Node to specify its special printing via label().

Add a recursing printer called print(); toString is used by default in the debugger and so cannot be recursive.

Make the peephole rules based on a proper Type and idealize calls.
Big comments about the Type computations.

Every node picks up a _print, compute and idealize() call.

Rename long arith ops Divide, UnaryMinus, Multiply, Subtract into shorter uniform-length names.  Cleans up the parser where he does the precedence op parsing.

Rework Parser:
- Drop Token class, its all Strings except in the one place we know a number is coming
- Embed the Lexer as a field in the Parser, instead of trying to pass it around everywhere in the Parser
- StartNode becomes a read-only global, so we don't have to pass it around everywhere in the Parser AND optimizer.
- Lexer matches on strings and returns strings.  Match and consume *at the moment* instead of carrying around a current token/string and forcing the next-token after consuming the current one.
- All parse subexpressions shrink by 1/2 after these changes.

* Initial writeup of Chapter 2

* Initial writeup of Chapter 2

* Initial writeup of Chapter 2

* Initial writeup of Chapter 2

* Remove range

* progress Chapter 2

Drop integer ranges.
Broader lattice pic.
Lots of prose changes in the readme.
Fixed title in gviz dot generation.
Fixed bug with peephole making redundant constants.

* Implement compute for all the arithmetic node types
Add a flag to switch off peephole so we can see the full graph
Add post peephole graph to writeup

* Implement compute for all the arithmetic node types
Add a flag to switch off peephole so we can see the full graph
Add post peephole graph to writeup

* Fix bad path to the svg

* Update pre-peephole diagram

* Add dead code elimination

...and a set_def to proper update graph edges.

* Update README.md

* Cleanup the GraphVisualizer a bit.
Update the graphs.
Update the chapter list as chapter 3 deleted, and chapter 4 is now chapter 3.

---------

Co-authored-by: Cliff Click <cliffc@acm.org>

1 files changed, 125 insertions, 0 deletions

diff --git a/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java
new file mode 100644
index 00000000..ba9ae448
--- /dev/null
+++ b/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java
@@ -0,0 +1,125 @@
+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.type.TypeInteger;
+import org.junit.Test;
+
+import static org.junit.Assert.*;
+
+public class Chapter02Test {
+
+    @Test
+    public void testChapter2ParseGrammar() {
+        Node._disablePeephole = true; // disable peephole so we can observe full graph
+        Parser parser = new Parser("return 1+2*3+-5;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return (1+((2*3)+(-5)));", ret.print());
+        GraphVisualizer gv = new GraphVisualizer();
+        System.out.println(gv.generateDotOutput(Parser.START));
+        Node._disablePeephole = false;
+    }
+
+    @Test
+    public void testChapter2AddPeephole() {
+        Parser parser = new Parser("return 1+2;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return 3;", ret.print());
+    }
+
+    @Test
+    public void testChapter2SubPeephole() {
+        Parser parser = new Parser("return 1-2;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return -1;", ret.print());
+    }
+
+    @Test
+    public void testChapter2MulPeephole() {
+        Parser parser = new Parser("return 2*3;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return 6;", ret.print());
+    }
+
+    @Test
+    public void testChapter2DivPeephole() {
+        Parser parser = new Parser("return 6/3;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return 2;", ret.print());
+    }
+
+    @Test
+    public void testChapter2MinusPeephole() {
+        Parser parser = new Parser("return 6/-3;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return -2;", ret.print());
+    }
+
+    @Test
+    public void testChapter2Example() {
+        Parser parser = new Parser("return 1+2*3+-5;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return 2;", ret.print());
+        GraphVisualizer gv = new GraphVisualizer();
+        System.out.println(gv.generateDotOutput(Parser.START));
+    }
+
+    @Test
+    public void testSimpleProgram() {
+        Parser parser = new Parser("return 1;");
+        ReturnNode ret = parser.parse();
+        StartNode start = Parser.START;
+        
+        assertEquals(start, ret.ctrl());
+        Node expr = ret.expr();
+        if( expr instanceof ConstantNode con ) {
+            assertEquals(start,con.in(0));
+            assertEquals(new TypeInteger(1), con._type);
+        } else {
+            fail();
+        }
+    }
+
+    @Test
+    public void testZero() {
+        Parser parser = new Parser("return 0;");
+        parser.parse();
+        StartNode start = Parser.START;
+        for( Node use : start._outputs )
+            if( use instanceof ConstantNode con )
+                assertEquals(new TypeInteger(0),con._type);
+    }
+
+    @Test
+    public void testBad1() {
+        try { new Parser("ret").parse(); }
+        catch( RuntimeException e ) { assertEquals("Syntax error, expected return: ret",e.getMessage()); }
+    }
+
+    @Test
+    public void testBad2() {
+        try { new Parser("return 0123;").parse(); }
+        catch( RuntimeException e ) { assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); }
+    }
+
+    @Test
+    public void testBad3() {
+        try { new Parser("return --12;").parse(); }
+        catch( RuntimeException e ) { assertEquals("Syntax error, expected integer literal: -",e.getMessage()); }
+    }
+
+    @Test
+    public void testBad4() {
+        try { new Parser("return 100").parse(); }
+        catch( RuntimeException e ) { assertTrue(e.getMessage().contains("Syntax error, expected ;:")); }
+    }
+
+    // Negative numbers require unary operator support that is not in scope
+    @Test
+    public void testBad5() {
+        try { new Parser("return -100;").parse(); }
+        catch( RuntimeException e ) { assertEquals("Syntax error, expected integer literal: -", e.getMessage()); }
+    }
+}