diff options
90 files changed, 3892 insertions, 3315 deletions
diff --git a/chapter01/README.md b/chapter01/README.md index d4882f8a..e7ea73bc 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -1,4 +1,4 @@ -# Chapter 1 +# Chapter 1: Introduction In this chapter we aim to compile simple scripts such as: diff --git a/chapter01/docs/Makefile b/chapter01/docs/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/chapter01/docs/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java index d79d23ff..8975a165 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java @@ -31,8 +31,22 @@ public class Parser { } public ReturnNode parse() { - require("return"); - return parseReturn(); + 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"); } /** @@ -89,7 +103,9 @@ public class Parser { // 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); } + // 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); } @@ -174,10 +190,18 @@ public class Parser { 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()); } @@ -186,13 +210,16 @@ public class Parser { boolean isNumber(char ch) {return Character.isDigit(ch);} private long parseNumber() { - int start = _position; - while (isNumber(nextChar())) ; - String snum = new String(_input, start, --_position - start); + 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) { diff --git a/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 738ed702..6989d0b9 100644 --- a/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -44,7 +44,7 @@ public class Chapter01Test { new Parser("ret").parse(); fail(); } catch( RuntimeException e ) { - assertEquals("Syntax error, expected return: ret",e.getMessage()); + assertEquals("Syntax error, expected a statement: ret",e.getMessage()); } } @@ -82,4 +82,25 @@ public class Chapter01Test { exceptionRule.expectMessage("Syntax error, expected integer literal"); new Parser("return -100;").parse(); } + + @Test + public void testBad6() { + try { + new Parser("return100").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected a statement: return100",e.getMessage()); + } + } + + @Test + public void testBad7() { + try { + new Parser("return 1;}").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, unexpected }",e.getMessage()); + } + } + } diff --git a/chapter02/README.md b/chapter02/README.md index 4b912465..500e9ae8 100644 --- a/chapter02/README.md +++ b/chapter02/README.md @@ -1,4 +1,4 @@ -# Chapter 2 +# Chapter 2: Arithmetic In this chapter we extend the language grammar to include arithmetic operations such as addition, subtraction, multiplication, division, and unary minus. This allows us to write statements such as: diff --git a/chapter02/docs/Makefile b/chapter02/docs/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/chapter02/docs/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/chapter02/src/main/java/com/seaofnodes/simple/Parser.java b/chapter02/src/main/java/com/seaofnodes/simple/Parser.java index 155cd353..f106bd47 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/Parser.java @@ -34,8 +34,22 @@ public class Parser { String src() { return new String( _lexer._input ); } public ReturnNode parse() { - require("return"); - return (ReturnNode) parseReturn(); + 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"); } /** @@ -133,7 +147,9 @@ public class Parser { // 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); } + // 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); } @@ -224,10 +240,18 @@ public class Parser { 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()); } @@ -236,13 +260,16 @@ public class Parser { boolean isNumber(char ch) {return Character.isDigit(ch);} private Type parseNumber() { - int start = _position; - while (isNumber(nextChar())) ; - String snum = new String(_input, start, --_position - start); + String snum = parseNumberString(); if (snum.length() > 1 && snum.charAt(0) == '0') throw error("Syntax error: integer values cannot start with '0'"); return TypeInteger.constant(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) { diff --git a/chapter02/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter02/src/test/java/com/seaofnodes/simple/Chapter01Test.java new file mode 100644 index 00000000..49edfb5b --- /dev/null +++ b/chapter02/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -0,0 +1,99 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter01Test { + + @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(TypeInteger.constant(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(TypeInteger.constant(0),con._type); + } + + @Test + public void testBad1() { + try { + new Parser("ret").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected a statement: ret",e.getMessage()); + } + } + + @Test + public void testBad2() { + try { + new Parser("return 0123;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); + } + } + + @Test + public void testNotBad3() { + // this test used to fail in chapter 1 + assertEquals("return 12;", new Parser("return --12;").parse().print()); + } + + @Test + public void testBad4() { + try { + new Parser("return 100").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected ;: ",e.getMessage()); + } + } + + @Test + public void testNotBad5() { + // this test used to fail in chapter 1 + assertEquals("return -100;", new Parser("return -100;").parse().print()); + } + + @Test + public void testBad6() { + try { + new Parser("return100").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected a statement: return100",e.getMessage()); + } + } + + @Test + public void testBad7() { + try { + new Parser("return 1;}").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, unexpected }",e.getMessage()); + } + } + +} diff --git a/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java index 35464955..36e62f9b 100644 --- a/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -2,19 +2,14 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Rule; import org.junit.Test; -import org.junit.rules.ExpectedException; import static org.junit.Assert.*; public class Chapter02Test { - @Rule - public ExpectedException exceptionRule = ExpectedException.none(); - @Test - public void testChapter2ParseGrammar() { + public void testParseGrammar() { Node._disablePeephole = true; // disable peephole so we can observe full graph Parser parser = new Parser("return 1+2*3+-5;"); ReturnNode ret = parser.parse(); @@ -25,42 +20,42 @@ public class Chapter02Test { } @Test - public void testChapter2AddPeephole() { + public void testAddPeephole() { Parser parser = new Parser("return 1+2;"); ReturnNode ret = parser.parse(); assertEquals("return 3;", ret.print()); } @Test - public void testChapter2SubPeephole() { + public void testSubPeephole() { Parser parser = new Parser("return 1-2;"); ReturnNode ret = parser.parse(); assertEquals("return -1;", ret.print()); } @Test - public void testChapter2MulPeephole() { + public void testMulPeephole() { Parser parser = new Parser("return 2*3;"); ReturnNode ret = parser.parse(); assertEquals("return 6;", ret.print()); } @Test - public void testChapter2DivPeephole() { + public void testDivPeephole() { Parser parser = new Parser("return 6/3;"); ReturnNode ret = parser.parse(); assertEquals("return 2;", ret.print()); } @Test - public void testChapter2MinusPeephole() { + public void testMinusPeephole() { Parser parser = new Parser("return 6/-3;"); ReturnNode ret = parser.parse(); assertEquals("return -2;", ret.print()); } @Test - public void testChapter2Example() { + public void testExample() { Parser parser = new Parser("return 1+2*3+-5;"); ReturnNode ret = parser.parse(); assertEquals("return 2;", ret.print()); @@ -68,71 +63,4 @@ public class Chapter02Test { System.out.println(gv.generateDotOutput(parser)); } - @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(TypeInteger.constant(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(TypeInteger.constant(0),con._type); - } - - @Test - public void testBad1() { - try { - new Parser("ret").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected return: ret",e.getMessage()); - } - } - - @Test - public void testBad2() { - try { - new Parser("return 0123;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); - } - } - - @Test - public void testNotBad3() { - // this test used to fail in chapter 1 - assertEquals("return 12;", new Parser("return --12;").parse().print()); - } - - @Test - public void testBad4() { - try { - new Parser("return 100").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected ;: ",e.getMessage()); - } - } - - @Test - public void testNotBad5() { - // this test used to fail in chapter 1 - assertEquals("return -100;", new Parser("return -100;").parse().print()); - } } diff --git a/chapter03/README.md b/chapter03/README.md index 7b0d22cb..0fb08e9a 100644 --- a/chapter03/README.md +++ b/chapter03/README.md @@ -1,4 +1,4 @@ -# Chapter 3 +# Chapter 3: Variable Declarations In this chapter we extend the language grammar to allow variable declarations. This allows us to write: diff --git a/chapter03/docs/Makefile b/chapter03/docs/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/chapter03/docs/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java index 9c7ebaca..4fb5b6ed 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java @@ -363,6 +363,7 @@ public class Parser { String getAnyNextToken() { if (isEOF()) return ""; if (isIdStart(peek())) return parseId(); + if (isNumber(peek())) return parseNumberString(); if (isPunctuation(peek())) return parsePunctuation(); return String.valueOf(peek()); } @@ -371,13 +372,16 @@ public class Parser { boolean isNumber(char ch) {return Character.isDigit(ch);} private Type parseNumber() { - int start = _position; - while (isNumber(nextChar())) ; - String snum = new String(_input, start, --_position - start); + String snum = parseNumberString(); if (snum.length() > 1 && snum.charAt(0) == '0') throw error("Syntax error: integer values cannot start with '0'"); return TypeInteger.constant(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) { diff --git a/chapter03/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter03/src/test/java/com/seaofnodes/simple/Chapter01Test.java new file mode 100644 index 00000000..311ca23b --- /dev/null +++ b/chapter03/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -0,0 +1,99 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter01Test { + + @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(TypeInteger.constant(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(TypeInteger.constant(0),con._type); + } + + @Test + public void testBad1() { + try { + new Parser("ret").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected =: ",e.getMessage()); + } + } + + @Test + public void testBad2() { + try { + new Parser("return 0123;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); + } + } + + @Test + public void testNotBad3() { + // this test used to fail in chapter 1 + assertEquals("return 12;", new Parser("return --12;").parse().print()); + } + + @Test + public void testBad4() { + try { + new Parser("return 100").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected ;: ",e.getMessage()); + } + } + + @Test + public void testNotBad5() { + // this test used to fail in chapter 1 + assertEquals("return -100;", new Parser("return -100;").parse().print()); + } + + @Test + public void testBad6() { + try { + new Parser("return100").parse(); + fail(); + } catch( RuntimeException e ) { + 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()); + } + } + +} diff --git a/chapter03/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter03/src/test/java/com/seaofnodes/simple/Chapter02Test.java new file mode 100644 index 00000000..60ee8874 --- /dev/null +++ b/chapter03/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -0,0 +1,66 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter02Test { + + @Test + public void testParseGrammar() { + Parser parser = new Parser("return 1+2*3+-5;"); + Node._disablePeephole = true; // disable peephole so we can observe full graph + ReturnNode ret = parser.parse(); + assertEquals("return (1+((2*3)+(-5)));", ret.print()); + GraphVisualizer gv = new GraphVisualizer(); + System.out.println(gv.generateDotOutput(parser)); + Node._disablePeephole = false; + } + + @Test + public void testAddPeephole() { + Parser parser = new Parser("return 1+2;"); + ReturnNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testSubPeephole() { + Parser parser = new Parser("return 1-2;"); + ReturnNode ret = parser.parse(); + assertEquals("return -1;", ret.print()); + } + + @Test + public void testMulPeephole() { + Parser parser = new Parser("return 2*3;"); + ReturnNode ret = parser.parse(); + assertEquals("return 6;", ret.print()); + } + + @Test + public void testDivPeephole() { + Parser parser = new Parser("return 6/3;"); + ReturnNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + + @Test + public void testMinusPeephole() { + Parser parser = new Parser("return 6/-3;"); + ReturnNode ret = parser.parse(); + assertEquals("return -2;", ret.print()); + } + + @Test + public void testExample() { + 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)); + } + +} diff --git a/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 965a100a..950d87fe 100644 --- a/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -2,17 +2,12 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Rule; import org.junit.Test; -import org.junit.rules.ExpectedException; import static org.junit.Assert.*; public class Chapter03Test { - @Rule - public ExpectedException exceptionRule = ExpectedException.none(); - @Test public void testVarDecl() { Parser parser = new Parser("int a=1; return a;"); @@ -61,131 +56,8 @@ public class Chapter03Test { } @Test - public void testChapter2ParseGrammar() { - Parser parser = new Parser("return 1+2*3+-5;"); - Node._disablePeephole = true; // disable peephole so we can observe full graph - ReturnNode ret = parser.parse(); - assertEquals("return (1+((2*3)+(-5)));", ret.print()); - GraphVisualizer gv = new GraphVisualizer(); - System.out.println(gv.generateDotOutput(parser)); - 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)); - } - - @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(TypeInteger.constant(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(TypeInteger.constant(0),con._type); - } - - @Test public void testBad1() { try { - new Parser("ret").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected =: ",e.getMessage()); - } - } - - @Test - public void testBad2() { - try { - new Parser("return 0123;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); - } - } - - @Test - public void testNotBad3() { - // this test used to fail in chapter 1 - assertEquals("return 12;", new Parser("return --12;").parse().print()); - } - - @Test - public void testBad4() { - try { - new Parser("return 100").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected ;: ",e.getMessage()); - } - } - - @Test - public void testNotBad5() { - // this test used to fail in chapter 1 - assertEquals("return -100;", new Parser("return -100;").parse().print()); - } - - @Test - public void testBad6() { - try { new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); fail(); } catch( RuntimeException e ) { @@ -193,14 +65,4 @@ public class Chapter03Test { } } - @Test - public void testBad7() { - try { - new Parser("return 1;}").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, unexpected }",e.getMessage()); - } - } - } diff --git a/chapter04/README.md b/chapter04/README.md index 03c6c53f..1f300937 100644 --- a/chapter04/README.md +++ b/chapter04/README.md @@ -1,4 +1,4 @@ -# Chapter 4 +# Chapter 4: External Argument and Comparisons In this chapter we extend the language grammar with following features: diff --git a/chapter04/docs/Makefile b/chapter04/docs/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/chapter04/docs/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/chapter04/docs/build-graphs.sh b/chapter04/docs/build-graphs.sh deleted file mode 100644 index e736a386..00000000 --- a/chapter04/docs/build-graphs.sh +++ /dev/null @@ -1 +0,0 @@ -dot -Tsvg lattice.gv > lattice.svg diff --git a/chapter04/src/main/java/com/seaofnodes/simple/Parser.java b/chapter04/src/main/java/com/seaofnodes/simple/Parser.java index e42613e2..3359f14e 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/Parser.java @@ -406,6 +406,7 @@ public class Parser { String getAnyNextToken() { if (isEOF()) return ""; if (isIdStart(peek())) return parseId(); + if (isNumber(peek())) return parseNumberString(); if (isPunctuation(peek())) return parsePunctuation(); return String.valueOf(peek()); } @@ -414,13 +415,16 @@ public class Parser { boolean isNumber(char ch) {return Character.isDigit(ch);} private Type parseNumber() { - int start = _position; - while (isNumber(nextChar())) ; - String snum = new String(_input, start, --_position - start); + String snum = parseNumberString(); if (snum.length() > 1 && snum.charAt(0) == '0') throw error("Syntax error: integer values cannot start with '0'"); return TypeInteger.constant(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) { diff --git a/chapter04/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter04/src/test/java/com/seaofnodes/simple/Chapter01Test.java new file mode 100644 index 00000000..3d568337 --- /dev/null +++ b/chapter04/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -0,0 +1,99 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter01Test { + + @Test + public void testSimpleProgram() { + Parser parser = new Parser("return 1;"); + ReturnNode ret = parser.parse(); + StartNode start = Parser.START; + + assertTrue(ret.ctrl() instanceof ProjNode); + Node expr = ret.expr(); + if( expr instanceof ConstantNode con ) { + assertEquals(start,con.in(0)); + assertEquals(TypeInteger.constant(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(TypeInteger.constant(0),con._type); + } + + @Test + public void testBad1() { + try { + new Parser("ret").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected =: ",e.getMessage()); + } + } + + @Test + public void testBad2() { + try { + new Parser("return 0123;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); + } + } + + @Test + public void testNotBad3() { + // this test used to fail in chapter 1 + assertEquals("return 12;", new Parser("return --12;").parse().print()); + } + + @Test + public void testBad4() { + try { + new Parser("return 100").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected ;: ",e.getMessage()); + } + } + + @Test + public void testNotBad5() { + // this test used to fail in chapter 1 + assertEquals("return -100;", new Parser("return -100;").parse().print()); + } + + @Test + public void testBad6() { + try { + new Parser("return100").parse(); + fail(); + } catch( RuntimeException e ) { + 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()); + } + } + +} diff --git a/chapter04/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter04/src/test/java/com/seaofnodes/simple/Chapter02Test.java new file mode 100644 index 00000000..60ee8874 --- /dev/null +++ b/chapter04/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -0,0 +1,66 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter02Test { + + @Test + public void testParseGrammar() { + Parser parser = new Parser("return 1+2*3+-5;"); + Node._disablePeephole = true; // disable peephole so we can observe full graph + ReturnNode ret = parser.parse(); + assertEquals("return (1+((2*3)+(-5)));", ret.print()); + GraphVisualizer gv = new GraphVisualizer(); + System.out.println(gv.generateDotOutput(parser)); + Node._disablePeephole = false; + } + + @Test + public void testAddPeephole() { + Parser parser = new Parser("return 1+2;"); + ReturnNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testSubPeephole() { + Parser parser = new Parser("return 1-2;"); + ReturnNode ret = parser.parse(); + assertEquals("return -1;", ret.print()); + } + + @Test + public void testMulPeephole() { + Parser parser = new Parser("return 2*3;"); + ReturnNode ret = parser.parse(); + assertEquals("return 6;", ret.print()); + } + + @Test + public void testDivPeephole() { + Parser parser = new Parser("return 6/3;"); + ReturnNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + + @Test + public void testMinusPeephole() { + Parser parser = new Parser("return 6/-3;"); + ReturnNode ret = parser.parse(); + assertEquals("return -2;", ret.print()); + } + + @Test + public void testExample() { + 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)); + } + +} diff --git a/chapter04/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter04/src/test/java/com/seaofnodes/simple/Chapter03Test.java new file mode 100644 index 00000000..950d87fe --- /dev/null +++ b/chapter04/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -0,0 +1,68 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter03Test { + + @Test + public void testVarDecl() { + Parser parser = new Parser("int a=1; return a;"); + ReturnNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testVarAdd() { + Parser parser = new Parser("int a=1; int b=2; return a+b;"); + ReturnNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testVarScope() { + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); + ReturnNode ret = parser.parse(); + assertEquals("return 4;", ret.print()); + } + + @Test + public void testVarScopeNoPeephole() { + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;"); + Node._disablePeephole = true; + ReturnNode ret = parser.parse(); + Node._disablePeephole = false; + assertEquals("return (1+3);", ret.print()); + } + + @Test + public void testVarDist() { + Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;"); + ReturnNode ret = parser.parse(); + assertEquals("return 8;", ret.print()); + } + + @Test + public void testSelfAssign() { + try { + new Parser("int a=a; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'a'",e.getMessage()); + } + } + + @Test + public void testBad1() { + try { + new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected }: ",e.getMessage()); + } + } + +} diff --git a/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java index 5757fc59..9f1535b3 100644 --- a/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -2,61 +2,56 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Rule; import org.junit.Test; -import org.junit.rules.ExpectedException; import static org.junit.Assert.*; public class Chapter04Test { - @Rule - public ExpectedException exceptionRule = ExpectedException.none(); - @Test - public void testChapter4Peephole() { + public void testPeephole() { Parser parser = new Parser("return 1+arg+2; #showGraph;"); ReturnNode ret = parser.parse(); assertEquals("return (arg+3);", ret.print()); } @Test - public void testChapter4Peephole2() { + public void testPeephole2() { Parser parser = new Parser("return (1+arg)+2;"); ReturnNode ret = parser.parse(); assertEquals("return (arg+3);", ret.print()); } @Test - public void testChapter4Add0() { + public void testAdd0() { Parser parser = new Parser("return 0+arg;"); ReturnNode ret = parser.parse(); assertEquals("return arg;", ret.print()); } @Test - public void testChapter4AddAddMul() { + public void testAddAddMul() { Parser parser = new Parser("return arg+0+arg;"); ReturnNode ret = parser.parse(); assertEquals("return (arg*2);", ret.print()); } @Test - public void testChapter4Peephole3() { + public void testPeephole3() { Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;"); ReturnNode ret = parser.parse(); assertEquals("return ((arg*2)+6);", ret.print()); } @Test - public void testChapter4Mul1() { + public void testMul1() { Parser parser = new Parser("return 1*arg;"); ReturnNode ret = parser.parse(); assertEquals("return arg;", ret.print()); } @Test - public void testChapter4VarArg() { + public void testVarArg() { Parser parser = new Parser("return arg; #showGraph;", TypeInteger.BOT); ReturnNode ret = parser.parse(); assertTrue(ret.in(0) instanceof ProjNode); @@ -64,56 +59,56 @@ public class Chapter04Test { } @Test - public void testChapter4ConstantArg() { + public void testConstantArg() { Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2)); ReturnNode ret = parser.parse(); assertEquals("return 2;", ret.print()); } @Test - public void testChapter4CompEq() { + public void testCompEq() { Parser parser = new Parser("return 3==3; #showGraph;"); ReturnNode ret = parser.parse(); assertEquals("return 1;", ret.print()); } @Test - public void testChapter4CompEq2() { + public void testCompEq2() { Parser parser = new Parser("return 3==4; #showGraph;"); ReturnNode ret = parser.parse(); assertEquals("return 0;", ret.print()); } @Test - public void testChapter4CompNEq() { + public void testCompNEq() { Parser parser = new Parser("return 3!=3; #showGraph;"); ReturnNode ret = parser.parse(); assertEquals("return 0;", ret.print()); } @Test - public void testChapter4CompNEq2() { + public void testCompNEq2() { Parser parser = new Parser("return 3!=4; #showGraph;"); ReturnNode ret = parser.parse(); assertEquals("return 1;", ret.print()); } @Test - public void testChapter4Bug1() { + public void testBug1() { Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;"); ReturnNode ret = parser.parse(); assertEquals("return (arg+3);", ret.print()); } @Test - public void testChapter4Bug2() { + public void testBug2() { Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;"); ReturnNode ret = parser.parse(); assertEquals("return (arg+1);", ret.print()); } @Test - public void testChapter4Bug3() { + public void testBug3() { try { new Parser("inta=1; return a;").parse(); fail(); @@ -123,200 +118,10 @@ public class Chapter04Test { } @Test - public void testChapter4Bug4() { + public void testBug4() { Parser parser = new Parser("return -arg;"); ReturnNode ret = parser.parse(); assertEquals("return (-arg);", ret.print()); } - @Test - public void testVarDecl() { - Parser parser = new Parser("int a=1; return a;"); - ReturnNode ret = parser.parse(); - assertEquals("return 1;", ret.print()); - } - - @Test - public void testVarAdd() { - Parser parser = new Parser("int a=1; int b=2; return a+b;"); - ReturnNode ret = parser.parse(); - assertEquals("return 3;", ret.print()); - } - - @Test - public void testVarScope() { - Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); - ReturnNode ret = parser.parse(); - assertEquals("return 4;", ret.print()); - } - - @Test - public void testVarScopeNoPeephole() { - Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;"); - Node._disablePeephole = true; - ReturnNode ret = parser.parse(); - Node._disablePeephole = false; - assertEquals("return (1+3);", ret.print()); - } - - @Test - public void testVarDist() { - Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;"); - ReturnNode ret = parser.parse(); - assertEquals("return 8;", ret.print()); - } - - @Test - public void testSelfAssign() { - try { - new Parser("int a=a; return a;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Undefined name 'a'",e.getMessage()); - } - } - - @Test - public void testChapter2ParseGrammar() { - Parser parser = new Parser("return 1+2*3+-5;"); - Node._disablePeephole = true; // disable peephole so we can observe full graph - ReturnNode ret = parser.parse(); - assertEquals("return (1+((2*3)+(-5)));", ret.print()); - GraphVisualizer gv = new GraphVisualizer(); - System.out.println(gv.generateDotOutput(parser)); - 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)); - } - - @Test - public void testSimpleProgram() { - Parser parser = new Parser("return 1;"); - ReturnNode ret = parser.parse(); - StartNode start = Parser.START; - - assertTrue(ret.ctrl() instanceof ProjNode); - Node expr = ret.expr(); - if( expr instanceof ConstantNode con ) { - assertEquals(start,con.in(0)); - assertEquals(TypeInteger.constant(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(TypeInteger.constant(0),con._type); - } - - @Test - public void testBad1() { - try { - new Parser("ret").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected =: ",e.getMessage()); - } - } - - @Test - public void testBad2() { - try { - new Parser("return 0123;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); - } - } - - @Test - public void testNotBad3() { - // this test used to fail in chapter 1 - assertEquals("return 12;", new Parser("return --12;").parse().print()); - } - - @Test - public void testBad4() { - try { - new Parser("return 100").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected ;: ",e.getMessage()); - } - } - - @Test - public void testNotBad5() { - // this test used to fail in chapter 1 - assertEquals("return -100;", new Parser("return -100;").parse().print()); - } - - @Test - public void testBad6() { - try { - new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); - fail(); - } catch( RuntimeException e ) { - 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()); - } - } - } diff --git a/chapter05/README.md b/chapter05/README.md index cf95b545..4d36e40c 100644 --- a/chapter05/README.md +++ b/chapter05/README.md @@ -1,4 +1,4 @@ -# Chapter 5 +# Chapter 5: If Statement, Phi, and Region In this chapter we extend the language grammar with the following features: diff --git a/chapter05/docs/Makefile b/chapter05/docs/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/chapter05/docs/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java index ff58fc25..8a02766f 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java @@ -476,6 +476,7 @@ public class Parser { String getAnyNextToken() { if (isEOF()) return ""; if (isIdStart(peek())) return parseId(); + if (isNumber(peek())) return parseNumberString(); if (isPunctuation(peek())) return parsePunctuation(); return String.valueOf(peek()); } @@ -484,13 +485,16 @@ public class Parser { boolean isNumber(char ch) {return Character.isDigit(ch);} private Type parseNumber() { - int start = _position; - while (isNumber(nextChar())) ; - String snum = new String(_input, start, --_position - start); + String snum = parseNumberString(); if (snum.length() > 1 && snum.charAt(0) == '0') throw error("Syntax error: integer values cannot start with '0'"); return TypeInteger.constant(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) { diff --git a/chapter05/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter05/src/test/java/com/seaofnodes/simple/Chapter01Test.java new file mode 100644 index 00000000..547c36f8 --- /dev/null +++ b/chapter05/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -0,0 +1,100 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter01Test { + + @Test + public void testSimpleProgram() { + Parser parser = new Parser("return 1;"); + StopNode stop = parser.parse(); + StartNode start = Parser.START; + ReturnNode ret = (ReturnNode)stop.in(0); + + assertTrue(ret.ctrl() instanceof ProjNode); + Node expr = ret.expr(); + if( expr instanceof ConstantNode con ) { + assertEquals(start,con.in(0)); + assertEquals(TypeInteger.constant(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(TypeInteger.constant(0),con._type); + } + + @Test + public void testBad1() { + try { + new Parser("ret").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected =: ",e.getMessage()); + } + } + + @Test + public void testBad2() { + try { + new Parser("return 0123;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); + } + } + + @Test + public void testNotBad3() { + // this test used to fail in chapter 1 + assertEquals("return 12;", new Parser("return --12;").parse().print()); + } + + @Test + public void testBad4() { + try { + new Parser("return 100").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected ;: ",e.getMessage()); + } + } + + @Test + public void testNotBad5() { + // this test used to fail in chapter 1 + assertEquals("return -100;", new Parser("return -100;").parse().print()); + } + + @Test + public void testBad6() { + try { + new Parser("return100").parse(); + fail(); + } catch( RuntimeException e ) { + 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()); + } + } + +} diff --git a/chapter05/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter05/src/test/java/com/seaofnodes/simple/Chapter02Test.java new file mode 100644 index 00000000..4085ed7e --- /dev/null +++ b/chapter05/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -0,0 +1,66 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter02Test { + + @Test + public void testParseGrammar() { + Parser parser = new Parser("return 1+2*3+-5;"); + Node._disablePeephole = true; // disable peephole so we can observe full graph + StopNode ret = parser.parse(); + assertEquals("return (1+((2*3)+(-5)));", ret.print()); + GraphVisualizer gv = new GraphVisualizer(); + System.out.println(gv.generateDotOutput(parser)); + Node._disablePeephole = false; + } + + @Test + public void testAddPeephole() { + Parser parser = new Parser("return 1+2;"); + StopNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testSubPeephole() { + Parser parser = new Parser("return 1-2;"); + StopNode ret = parser.parse(); + assertEquals("return -1;", ret.print()); + } + + @Test + public void testMulPeephole() { + Parser parser = new Parser("return 2*3;"); + StopNode ret = parser.parse(); + assertEquals("return 6;", ret.print()); + } + + @Test + public void testDivPeephole() { + Parser parser = new Parser("return 6/3;"); + StopNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + + @Test + public void testMinusPeephole() { + Parser parser = new Parser("return 6/-3;"); + StopNode ret = parser.parse(); + assertEquals("return -2;", ret.print()); + } + + @Test + public void testExample() { + Parser parser = new Parser("return 1+2*3+-5;"); + StopNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + GraphVisualizer gv = new GraphVisualizer(); + System.out.println(gv.generateDotOutput(parser)); + } + +} diff --git a/chapter05/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter05/src/test/java/com/seaofnodes/simple/Chapter03Test.java new file mode 100644 index 00000000..407fbe48 --- /dev/null +++ b/chapter05/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -0,0 +1,68 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter03Test { + + @Test + public void testVarDecl() { + Parser parser = new Parser("int a=1; return a;"); + StopNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testVarAdd() { + Parser parser = new Parser("int a=1; int b=2; return a+b;"); + StopNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testVarScope() { + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); + StopNode ret = parser.parse(); + assertEquals("return 4;", ret.print()); + } + + @Test + public void testVarScopeNoPeephole() { + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;"); + Node._disablePeephole = true; + StopNode ret = parser.parse(); + Node._disablePeephole = false; + assertEquals("return (1+3);", ret.print()); + } + + @Test + public void testVarDist() { + Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 8;", ret.print()); + } + + @Test + public void testSelfAssign() { + try { + new Parser("int a=a; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'a'",e.getMessage()); + } + } + + @Test + public void testBad1() { + try { + new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected }: ",e.getMessage()); + } + } + +} diff --git a/chapter05/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter05/src/test/java/com/seaofnodes/simple/Chapter04Test.java new file mode 100644 index 00000000..cde23324 --- /dev/null +++ b/chapter05/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -0,0 +1,128 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter04Test { + + @Test + public void testPeephole() { + Parser parser = new Parser("return 1+arg+2; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return (arg+3);", ret.print()); + } + + @Test + public void testPeephole2() { + Parser parser = new Parser("return (1+arg)+2;"); + StopNode ret = parser.parse(); + assertEquals("return (arg+3);", ret.print()); + } + + @Test + public void testAdd0() { + Parser parser = new Parser("return 0+arg;"); + StopNode ret = parser.parse(); + assertEquals("return arg;", ret.print()); + } + + @Test + public void testAddAddMul() { + Parser parser = new Parser("return arg+0+arg;"); + StopNode ret = parser.parse(); + assertEquals("return (arg*2);", ret.print()); + } + + @Test + public void testPeephole3() { + Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return ((arg*2)+6);", ret.print()); + } + + @Test + public void testMul1() { + Parser parser = new Parser("return 1*arg;"); + StopNode ret = parser.parse(); + assertEquals("return arg;", ret.print()); + } + + @Test + public void testVarArg() { + Parser parser = new Parser("return arg; #showGraph;"); + StopNode stop = parser.parse(); + ReturnNode ret = stop.ret(); + assertTrue(ret.in(0) instanceof ProjNode); + assertTrue(ret.in(1) instanceof ProjNode); + } + + @Test + public void testConstantArg() { + Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2)); + StopNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + + @Test + public void testCompEq() { + Parser parser = new Parser("return 3==3; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testCompEq2() { + Parser parser = new Parser("return 3==4; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 0;", ret.print()); + } + + @Test + public void testCompNEq() { + Parser parser = new Parser("return 3!=3; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 0;", ret.print()); + } + + @Test + public void testCompNEq2() { + Parser parser = new Parser("return 3!=4; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testBug1() { + Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return (arg+3);", ret.print()); + } + + @Test + public void testBug2() { + Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return (arg+1);", ret.print()); + } + + @Test + public void testBug3() { + try { + new Parser("inta=1; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'inta'",e.getMessage()); + } + } + + @Test + public void testBug4() { + Parser parser = new Parser("return -arg;"); + StopNode ret = parser.parse(); + assertEquals("return (-arg);", ret.print()); + } + +} diff --git a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 97666d27..b5fcbeaf 100644 --- a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -2,16 +2,14 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Rule; import org.junit.Test; -import org.junit.rules.ExpectedException; import static org.junit.Assert.*; public class Chapter05Test { @Test - public void testChapter5IfStmt() { + public void testIfStmt() { Parser parser = new Parser( """ int a = 1; @@ -28,7 +26,7 @@ return a;"""); } @Test - public void testChapter5Test() { + public void testTest() { Parser parser = new Parser( """ int c = 3; @@ -43,7 +41,7 @@ return c;""", TypeInteger.BOT); } @Test - public void testChapter5Return2() { + public void testReturn2() { Parser parser = new Parser( """ if( arg==1 ) @@ -56,7 +54,7 @@ else } @Test - public void testChapter5IfMergeB() { + public void testIfMergeB() { Parser parser = new Parser( """ int a=arg+1; @@ -71,7 +69,7 @@ return a+b;"""); } @Test - public void testChapter5IfMerge2() { + public void testIfMerge2() { Parser parser = new Parser( """ int a=arg+1; @@ -86,7 +84,7 @@ return a+b;"""); } @Test - public void testChapter5Merge3() { + public void testMerge3() { Parser parser = new Parser( """ int a=1; @@ -106,7 +104,7 @@ return a; } @Test - public void testChapter5Merge4() { + public void testMerge4() { Parser parser = new Parser( """ int a=0; @@ -122,7 +120,7 @@ return arg+a+b; } @Test - public void testChapter5Merge5() { + public void testMerge5() { Parser parser = new Parser( """ int a=arg==2; @@ -136,13 +134,13 @@ return a;"""); } @Test - public void testChapter5True() { + public void testTrue() { StopNode stop = new Parser("return true;").parse(); assertEquals("return 1;",stop.toString()); } @Test - public void testChapter5HalfDef() { + public void testHalfDef() { try { new Parser("if( arg==1 ) int b=2; return b;").parse(); fail(); @@ -152,7 +150,7 @@ return a;"""); } @Test - public void testChapter5HalfDef2() { + public void testHalfDef2() { try { new Parser("if( arg==1 ) { int b=2; } else { int b=3; } return b;").parse(); fail(); @@ -162,7 +160,17 @@ return a;"""); } @Test - public void testChapter5BadNum() { + public void testRegress1() { + try { + new Parser("if(arg==2) int a=1; else int b=2; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Cannot define a new name on one arm of an if",e.getMessage()); + } + } + + @Test + public void testBadNum() { try { new Parser("return 1-;").parse(); fail(); @@ -172,7 +180,7 @@ return a;"""); } @Test - public void testChapter5Keyword1() { + public void testKeyword1() { try { new Parser("int true=0; return true;").parse(); fail(); @@ -182,7 +190,7 @@ return a;"""); } @Test - public void testChapter5Keyword2() { + public void testKeyword2() { try { new Parser("int else=arg; if(else) else=2; else else=1; return else;").parse(); fail(); @@ -192,7 +200,7 @@ return a;"""); } @Test - public void testChapter5Keyword3() { + public void testKeyword3() { try { new Parser("int a=1; ififif(arg)inta=2;return a;").parse(); fail(); @@ -201,312 +209,4 @@ return a;"""); } } - @Test - public void testChapter4Peephole() { - Parser parser = new Parser("return 1+arg+2; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return (arg+3);", ret.print()); - } - - @Test - public void testChapter4Peephole2() { - Parser parser = new Parser("return (1+arg)+2;"); - StopNode ret = parser.parse(); - assertEquals("return (arg+3);", ret.print()); - } - - @Test - public void testChapter4Add0() { - Parser parser = new Parser("return 0+arg;"); - StopNode ret = parser.parse(); - assertEquals("return arg;", ret.print()); - } - - @Test - public void testChapter4AddAddMul() { - Parser parser = new Parser("return arg+0+arg;"); - StopNode ret = parser.parse(); - assertEquals("return (arg*2);", ret.print()); - } - - @Test - public void testChapter4Peephole3() { - Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return ((arg*2)+6);", ret.print()); - } - - @Test - public void testChapter4Mul1() { - Parser parser = new Parser("return 1*arg;"); - StopNode ret = parser.parse(); - assertEquals("return arg;", ret.print()); - } - - @Test - public void testChapter4VarArg() { - Parser parser = new Parser("return arg; #showGraph;"); - StopNode stop = parser.parse(); - ReturnNode ret = stop.ret(); - assertTrue(ret.in(0) instanceof ProjNode); - assertTrue(ret.in(1) instanceof ProjNode); - } - - @Test - public void testChapter4ConstantArg() { - Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2)); - StopNode ret = parser.parse(); - assertEquals("return 2;", ret.print()); - } - - @Test - public void testChapter4CompEq() { - Parser parser = new Parser("return 3==3; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return 1;", ret.print()); - } - - @Test - public void testChapter4CompEq2() { - Parser parser = new Parser("return 3==4; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return 0;", ret.print()); - } - - @Test - public void testChapter4CompNEq() { - Parser parser = new Parser("return 3!=3; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return 0;", ret.print()); - } - - @Test - public void testChapter4CompNEq2() { - Parser parser = new Parser("return 3!=4; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return 1;", ret.print()); - } - - @Test - public void testChapter4Bug1() { - Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return (arg+3);", ret.print()); - } - - @Test - public void testChapter4Bug2() { - Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return (arg+1);", ret.print()); - } - - @Test - public void testChapter4Bug3() { - try { - new Parser("inta=1; return a;").parse(); - fail(); - } catch( RuntimeException e ) { - 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() { - Parser parser = new Parser("int a=1; return a;"); - StopNode ret = parser.parse(); - assertEquals("return 1;", ret.print()); - } - - @Test - public void testVarAdd() { - Parser parser = new Parser("int a=1; int b=2; return a+b;"); - StopNode ret = parser.parse(); - assertEquals("return 3;", ret.print()); - } - - @Test - public void testVarScope() { - Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); - StopNode ret = parser.parse(); - assertEquals("return 4;", ret.print()); - } - - @Test - public void testVarScopeNoPeephole() { - Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;"); - Node._disablePeephole = true; - StopNode ret = parser.parse(); - Node._disablePeephole = false; - assertEquals("return (1+3);", ret.print()); - } - - @Test - public void testVarDist() { - Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return 8;", ret.print()); - } - - @Test - public void testSelfAssign() { - try { - new Parser("int a=a; return a;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Undefined name 'a'",e.getMessage()); - } - } - - @Test - public void testChapter2ParseGrammar() { - Parser parser = new Parser("return 1+2*3+-5;"); - Node._disablePeephole = true; // disable peephole so we can observe full graph - StopNode ret = parser.parse(); - assertEquals("return (1+((2*3)+(-5)));", ret.print()); - GraphVisualizer gv = new GraphVisualizer(); - System.out.println(gv.generateDotOutput(parser)); - Node._disablePeephole = false; - } - - @Test - public void testChapter2AddPeephole() { - Parser parser = new Parser("return 1+2;"); - StopNode ret = parser.parse(); - assertEquals("return 3;", ret.print()); - } - - @Test - public void testChapter2SubPeephole() { - Parser parser = new Parser("return 1-2;"); - StopNode ret = parser.parse(); - assertEquals("return -1;", ret.print()); - } - - @Test - public void testChapter2MulPeephole() { - Parser parser = new Parser("return 2*3;"); - StopNode ret = parser.parse(); - assertEquals("return 6;", ret.print()); - } - - @Test - public void testChapter2DivPeephole() { - Parser parser = new Parser("return 6/3;"); - StopNode ret = parser.parse(); - assertEquals("return 2;", ret.print()); - } - - @Test - public void testChapter2MinusPeephole() { - Parser parser = new Parser("return 6/-3;"); - StopNode ret = parser.parse(); - assertEquals("return -2;", ret.print()); - } - - @Test - public void testChapter2Example() { - Parser parser = new Parser("return 1+2*3+-5;"); - StopNode ret = parser.parse(); - assertEquals("return 2;", ret.print()); - GraphVisualizer gv = new GraphVisualizer(); - System.out.println(gv.generateDotOutput(parser)); - } - - @Test - public void testSimpleProgram() { - Parser parser = new Parser("return 1;"); - StopNode stop = parser.parse(); - StartNode start = Parser.START; - ReturnNode ret = (ReturnNode)stop.in(0); - - assertTrue(ret.ctrl() instanceof ProjNode); - Node expr = ret.expr(); - if( expr instanceof ConstantNode con ) { - assertEquals(start,con.in(0)); - assertEquals(TypeInteger.constant(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(TypeInteger.constant(0),con._type); - } - - @Test - public void testBad1() { - try { - new Parser("ret").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected =: ",e.getMessage()); - } - } - - @Test - public void testBad2() { - try { - new Parser("return 0123;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); - } - } - - @Test - public void testNotBad3() { - // this test used to fail in chapter 1 - assertEquals("return 12;", new Parser("return --12;").parse().print()); - } - - @Test - public void testBad4() { - try { - new Parser("return 100").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected ;: ",e.getMessage()); - } - } - - @Test - public void testNotBad5() { - // this test used to fail in chapter 1 - assertEquals("return -100;", new Parser("return -100;").parse().print()); - } - - @Test - public void testBad6() { - try { - new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); - fail(); - } catch( RuntimeException e ) { - 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()); - } - } - } diff --git a/chapter06/README.md b/chapter06/README.md index cb265f5b..1c09be27 100644 --- a/chapter06/README.md +++ b/chapter06/README.md @@ -1,4 +1,4 @@ -# Chapter 6 +# Chapter 6: Peepholes for If In this chapter we do not add new language features. Our goal is to add peephole optimization to `if` statements. diff --git a/chapter06/docs/Makefile b/chapter06/docs/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/chapter06/docs/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/chapter06/docs/build-graphs.sh b/chapter06/docs/build-graphs.sh deleted file mode 100644 index 6b3f5bb2..00000000 --- a/chapter06/docs/build-graphs.sh +++ /dev/null @@ -1,12 +0,0 @@ -dot -Tsvg 06-graph1-pre.gv > 06-graph1-pre.svg -dot -Tsvg 06-graph1-post.gv > 06-graph1-post.svg -dot -Tsvg 06-graph2-pre.gv > 06-graph2-pre.svg -dot -Tsvg 06-graph2-post.gv > 06-graph2-post.svg -dot -Tsvg 06-graph3-nonconst.gv > 06-graph3-nonconst.svg -dot -Tsvg 06-graph3-nonconst-peephole.gv > 06-graph3-nonconst-peephole.svg -dot -Tsvg 06-graph3-true.gv > 06-graph3-true.svg -dot -Tsvg 06-graph3-false.gv > 06-graph3-false.svg -dot -Tsvg 06-graph4-nonconst.gv > 06-graph4-nonconst.svg -dot -Tsvg 06-graph4-true.gv > 06-graph4-true.svg -dot -Tsvg 06-graph4-arg2.gv > 06-graph4-arg2.svg -dot -Tsvg lattice.gv > lattice.svg diff --git a/chapter06/src/main/java/com/seaofnodes/simple/Parser.java b/chapter06/src/main/java/com/seaofnodes/simple/Parser.java index 54c5b15c..83eaa099 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/Parser.java @@ -477,6 +477,7 @@ public class Parser { String getAnyNextToken() { if (isEOF()) return ""; if (isIdStart(peek())) return parseId(); + if (isNumber(peek())) return parseNumberString(); if (isPunctuation(peek())) return parsePunctuation(); return String.valueOf(peek()); } @@ -485,13 +486,16 @@ public class Parser { boolean isNumber(char ch) {return Character.isDigit(ch);} private Type parseNumber() { - int start = _position; - while (isNumber(nextChar())) ; - String snum = new String(_input, start, --_position - start); + String snum = parseNumberString(); if (snum.length() > 1 && snum.charAt(0) == '0') throw error("Syntax error: integer values cannot start with '0'"); return TypeInteger.constant(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) { diff --git a/chapter06/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter06/src/test/java/com/seaofnodes/simple/Chapter01Test.java new file mode 100644 index 00000000..547c36f8 --- /dev/null +++ b/chapter06/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -0,0 +1,100 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter01Test { + + @Test + public void testSimpleProgram() { + Parser parser = new Parser("return 1;"); + StopNode stop = parser.parse(); + StartNode start = Parser.START; + ReturnNode ret = (ReturnNode)stop.in(0); + + assertTrue(ret.ctrl() instanceof ProjNode); + Node expr = ret.expr(); + if( expr instanceof ConstantNode con ) { + assertEquals(start,con.in(0)); + assertEquals(TypeInteger.constant(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(TypeInteger.constant(0),con._type); + } + + @Test + public void testBad1() { + try { + new Parser("ret").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected =: ",e.getMessage()); + } + } + + @Test + public void testBad2() { + try { + new Parser("return 0123;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); + } + } + + @Test + public void testNotBad3() { + // this test used to fail in chapter 1 + assertEquals("return 12;", new Parser("return --12;").parse().print()); + } + + @Test + public void testBad4() { + try { + new Parser("return 100").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected ;: ",e.getMessage()); + } + } + + @Test + public void testNotBad5() { + // this test used to fail in chapter 1 + assertEquals("return -100;", new Parser("return -100;").parse().print()); + } + + @Test + public void testBad6() { + try { + new Parser("return100").parse(); + fail(); + } catch( RuntimeException e ) { + 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()); + } + } + +} diff --git a/chapter06/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter06/src/test/java/com/seaofnodes/simple/Chapter02Test.java new file mode 100644 index 00000000..4085ed7e --- /dev/null +++ b/chapter06/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -0,0 +1,66 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter02Test { + + @Test + public void testParseGrammar() { + Parser parser = new Parser("return 1+2*3+-5;"); + Node._disablePeephole = true; // disable peephole so we can observe full graph + StopNode ret = parser.parse(); + assertEquals("return (1+((2*3)+(-5)));", ret.print()); + GraphVisualizer gv = new GraphVisualizer(); + System.out.println(gv.generateDotOutput(parser)); + Node._disablePeephole = false; + } + + @Test + public void testAddPeephole() { + Parser parser = new Parser("return 1+2;"); + StopNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testSubPeephole() { + Parser parser = new Parser("return 1-2;"); + StopNode ret = parser.parse(); + assertEquals("return -1;", ret.print()); + } + + @Test + public void testMulPeephole() { + Parser parser = new Parser("return 2*3;"); + StopNode ret = parser.parse(); + assertEquals("return 6;", ret.print()); + } + + @Test + public void testDivPeephole() { + Parser parser = new Parser("return 6/3;"); + StopNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + + @Test + public void testMinusPeephole() { + Parser parser = new Parser("return 6/-3;"); + StopNode ret = parser.parse(); + assertEquals("return -2;", ret.print()); + } + + @Test + public void testExample() { + Parser parser = new Parser("return 1+2*3+-5;"); + StopNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + GraphVisualizer gv = new GraphVisualizer(); + System.out.println(gv.generateDotOutput(parser)); + } + +} diff --git a/chapter06/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter06/src/test/java/com/seaofnodes/simple/Chapter03Test.java new file mode 100644 index 00000000..407fbe48 --- /dev/null +++ b/chapter06/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -0,0 +1,68 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter03Test { + + @Test + public void testVarDecl() { + Parser parser = new Parser("int a=1; return a;"); + StopNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testVarAdd() { + Parser parser = new Parser("int a=1; int b=2; return a+b;"); + StopNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testVarScope() { + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); + StopNode ret = parser.parse(); + assertEquals("return 4;", ret.print()); + } + + @Test + public void testVarScopeNoPeephole() { + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;"); + Node._disablePeephole = true; + StopNode ret = parser.parse(); + Node._disablePeephole = false; + assertEquals("return (1+3);", ret.print()); + } + + @Test + public void testVarDist() { + Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 8;", ret.print()); + } + + @Test + public void testSelfAssign() { + try { + new Parser("int a=a; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'a'",e.getMessage()); + } + } + + @Test + public void testBad1() { + try { + new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected }: ",e.getMessage()); + } + } + +} diff --git a/chapter06/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter06/src/test/java/com/seaofnodes/simple/Chapter04Test.java new file mode 100644 index 00000000..cde23324 --- /dev/null +++ b/chapter06/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -0,0 +1,128 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter04Test { + + @Test + public void testPeephole() { + Parser parser = new Parser("return 1+arg+2; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return (arg+3);", ret.print()); + } + + @Test + public void testPeephole2() { + Parser parser = new Parser("return (1+arg)+2;"); + StopNode ret = parser.parse(); + assertEquals("return (arg+3);", ret.print()); + } + + @Test + public void testAdd0() { + Parser parser = new Parser("return 0+arg;"); + StopNode ret = parser.parse(); + assertEquals("return arg;", ret.print()); + } + + @Test + public void testAddAddMul() { + Parser parser = new Parser("return arg+0+arg;"); + StopNode ret = parser.parse(); + assertEquals("return (arg*2);", ret.print()); + } + + @Test + public void testPeephole3() { + Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return ((arg*2)+6);", ret.print()); + } + + @Test + public void testMul1() { + Parser parser = new Parser("return 1*arg;"); + StopNode ret = parser.parse(); + assertEquals("return arg;", ret.print()); + } + + @Test + public void testVarArg() { + Parser parser = new Parser("return arg; #showGraph;"); + StopNode stop = parser.parse(); + ReturnNode ret = stop.ret(); + assertTrue(ret.in(0) instanceof ProjNode); + assertTrue(ret.in(1) instanceof ProjNode); + } + + @Test + public void testConstantArg() { + Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2)); + StopNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + + @Test + public void testCompEq() { + Parser parser = new Parser("return 3==3; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testCompEq2() { + Parser parser = new Parser("return 3==4; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 0;", ret.print()); + } + + @Test + public void testCompNEq() { + Parser parser = new Parser("return 3!=3; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 0;", ret.print()); + } + + @Test + public void testCompNEq2() { + Parser parser = new Parser("return 3!=4; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testBug1() { + Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return (arg+3);", ret.print()); + } + + @Test + public void testBug2() { + Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return (arg+1);", ret.print()); + } + + @Test + public void testBug3() { + try { + new Parser("inta=1; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'inta'",e.getMessage()); + } + } + + @Test + public void testBug4() { + Parser parser = new Parser("return -arg;"); + StopNode ret = parser.parse(); + assertEquals("return (-arg);", ret.print()); + } + +} diff --git a/chapter06/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter06/src/test/java/com/seaofnodes/simple/Chapter05Test.java new file mode 100644 index 00000000..fa576700 --- /dev/null +++ b/chapter06/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -0,0 +1,214 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Rule; +import org.junit.Test; +import org.junit.rules.ExpectedException; + +import static org.junit.Assert.*; + +public class Chapter05Test { + + @Test + public void testIfStmt() { + Parser parser = new Parser( +""" +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; + #showGraph; +} +#showGraph; +return a;"""); + StopNode ret = parser.parse(true); + assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString()); + } + + @Test + public void testTest() { + Parser parser = new Parser( +""" +int c = 3; +int b = 2; +if (arg == 1) { + b = 3; + c = 4; +} +return c;""", TypeInteger.BOT); + StopNode ret = parser.parse(true); + assertEquals("return Phi(Region16,4,3);", ret.toString()); + } + + @Test + public void testReturn2() { + 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 testIfMergeB() { + 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 testIfMerge2() { + 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 testMerge3() { + 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 testMerge4() { + 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 testMerge5() { + 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()); + } + + @Test + public void testTrue() { + StopNode stop = new Parser("return true;").parse(); + assertEquals("return 1;",stop.toString()); + } + + @Test + public void testHalfDef() { + try { + new Parser("if( arg==1 ) int b=2; return b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Cannot define a new name on one arm of an if",e.getMessage()); + } + } + + @Test + public void testHalfDef2() { + try { + new Parser("if( arg==1 ) { int b=2; } else { int b=3; } return b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'b'",e.getMessage()); + } + } + + @Test + public void testRegress1() { + try { + new Parser("if(arg==2) int a=1; else int b=2; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Cannot define a new name on one arm of an if",e.getMessage()); + } + } + + @Test + public void testBadNum() { + try { + new Parser("return 1-;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected an identifier or expression: ;",e.getMessage()); + } + } + + @Test + public void testKeyword1() { + try { + new Parser("int true=0; return true;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Expected an identifier, found 'true'",e.getMessage()); + } + } + + @Test + public void testKeyword2() { + try { + new Parser("int else=arg; if(else) else=2; else else=1; return else;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Expected an identifier, found 'else'",e.getMessage()); + } + } + + @Test + public void testKeyword3() { + try { + new Parser("int a=1; ififif(arg)inta=2;return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected =: (",e.getMessage()); + } + } + +} diff --git a/chapter06/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter06/src/test/java/com/seaofnodes/simple/Chapter06Test.java index fbafad2f..0a61d358 100644 --- a/chapter06/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/chapter06/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -9,7 +9,7 @@ import static org.junit.Assert.*; public class Chapter06Test { @Test - public void testChapter6PeepholeReturn() { + public void testPeepholeReturn() { Parser parser = new Parser( """ if( true ) return 2; @@ -21,7 +21,7 @@ return 1; } @Test - public void testChapter6PeepholeRotate() { + public void testPeepholeRotate() { Parser parser = new Parser( """ int a = 1; @@ -34,7 +34,7 @@ return (arg < a) < 3; } @Test - public void testChapter6PeepholeCFG() { + public void testPeepholeCFG() { Parser parser = new Parser( """ int a=1; @@ -50,7 +50,7 @@ return a; } @Test - public void testChapter6IfIf() { + public void testIfIf() { Parser parser = new Parser( """ int a=1; @@ -69,7 +69,7 @@ return b;""", TypeInteger.BOT); } @Test - public void testChapter6IfArgIf() { + public void testIfArgIf() { Parser parser = new Parser( """ int a=1; @@ -88,7 +88,7 @@ return b;""", TypeInteger.BOT); } @Test - public void testChapter6Merge3With2() { + public void testMerge3With2() { Parser parser = new Parser( """ int a=1; @@ -108,7 +108,7 @@ return a; } @Test - public void testChapter6Merge3With1() { + public void testMerge3With1() { Parser parser = new Parser( """ int a=1; @@ -128,7 +128,7 @@ return a; } @Test - public void testChapter6Merge3Peephole() { + public void testMerge3Peephole() { Parser parser = new Parser( """ int a=1; @@ -148,7 +148,7 @@ return a; } @Test - public void testChapter6Merge3Peephole1() { + public void testMerge3Peephole1() { Parser parser = new Parser( """ int a=1; @@ -168,7 +168,7 @@ return a; } @Test - public void testChapter6Merge3Peephole3() { + public void testMerge3Peephole3() { Parser parser = new Parser( """ int a=1; @@ -188,7 +188,7 @@ return a; } @Test - public void testChapter6Demo1NonConst() { + public void testDemo1NonConst() { Parser parser = new Parser(""" int a = 0; int b = 1; @@ -205,7 +205,7 @@ return a+b; @Test - public void testChapter6Demo1True() { + public void testDemo1True() { Parser parser = new Parser(""" int a = 0; int b = 1; @@ -221,7 +221,7 @@ return a+b; } @Test - public void testChapter6Demo1False() { + public void testDemo1False() { Parser parser = new Parser(""" int a = 0; int b = 1; @@ -237,7 +237,7 @@ return a+b; } @Test - public void testChapter6Demo2NonConst() { + public void testDemo2NonConst() { Parser parser = new Parser(""" int a = 0; int b = 1; @@ -256,7 +256,7 @@ return a+b+c; @Test - public void testChapter6Demo2True() { + public void testDemo2True() { Parser parser = new Parser(""" int a = 0; int b = 1; @@ -274,7 +274,7 @@ return a+b+c; } @Test - public void testChapter6Demo2arg2() { + public void testDemo2arg2() { Parser parser = new Parser(""" int a = 0; int b = 1; @@ -291,505 +291,4 @@ return a+b+c; assertEquals("return 5;", ret.toString()); } - - - @Test - public void testChapter5IfStmt() { - Parser parser = new Parser( -""" -int a = 1; -if (arg == 1) - a = arg+2; -else { - a = arg-3; - #showGraph; -} -#showGraph; -return a;"""); - StopNode ret = parser.parse(true); - assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString()); - } - - @Test - public void testChapter5Test() { - Parser parser = new Parser( -""" -int c = 3; -int b = 2; -if (arg == 1) { - b = 3; - c = 4; -} -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); - 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;"""); - 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;"""); - 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); - 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); - 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;"""); - StopNode ret = parser.parse(true); - assertEquals("return (arg==Phi(Region16,3,2));", ret.toString()); - } - - @Test - public void testChapter5True() { - StopNode stop = new Parser("return true;").parse(); - assertEquals("return 1;",stop.toString()); - } - - @Test - public void testChapter5HalfDef() { - try { - new Parser("if( arg==1 ) int b=2; return b;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Cannot define a new name on one arm of an if",e.getMessage()); - } - } - - @Test - public void testChapter5HalfDef2() { - try { - new Parser("if( arg==1 ) { int b=2; } else { int b=3; } return b;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Undefined name 'b'",e.getMessage()); - } - } - - @Test - public void testChapter5BadNum() { - try { - new Parser("return 1-;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected an identifier or expression: ;",e.getMessage()); - } - } - - @Test - public void testChapter5Keyword1() { - try { - new Parser("int true=0; return true;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Expected an identifier, found 'true'",e.getMessage()); - } - } - - @Test - public void testChapter5Keyword2() { - try { - new Parser("int else=arg; if(else) else=2; else else=1; return else;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Expected an identifier, found 'else'",e.getMessage()); - } - } - - @Test - public void testChapter5Keyword3() { - try { - new Parser("int a=1; ififif(arg)inta=2;return a;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected =: (",e.getMessage()); - } - } - - @Test - public void testChapter4Peephole() { - Parser parser = new Parser("return 1+arg+2; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return (arg+3);", ret.print()); - } - - @Test - public void testChapter4Peephole2() { - Parser parser = new Parser("return (1+arg)+2;"); - StopNode ret = parser.parse(); - assertEquals("return (arg+3);", ret.print()); - } - - @Test - public void testChapter4Add0() { - Parser parser = new Parser("return 0+arg;"); - StopNode ret = parser.parse(); - assertEquals("return arg;", ret.print()); - } - - @Test - public void testChapter4AddAddMul() { - Parser parser = new Parser("return arg+0+arg;"); - StopNode ret = parser.parse(); - assertEquals("return (arg*2);", ret.print()); - } - - @Test - public void testChapter4Peephole3() { - Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return ((arg*2)+6);", ret.print()); - } - - @Test - public void testChapter4Mul1() { - Parser parser = new Parser("return 1*arg;"); - StopNode ret = parser.parse(); - assertEquals("return arg;", ret.print()); - } - - @Test - public void testChapter4VarArg() { - Parser parser = new Parser("return arg; #showGraph;"); - StopNode stop = parser.parse(); - ReturnNode ret = stop.ret(); - assertTrue(ret.in(0) instanceof ProjNode); - assertTrue(ret.in(1) instanceof ProjNode); - } - - @Test - public void testChapter4ConstantArg() { - Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2)); - StopNode ret = parser.parse(); - assertEquals("return 2;", ret.print()); - } - - @Test - public void testChapter4CompEq() { - Parser parser = new Parser("return 3==3; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return 1;", ret.print()); - } - - @Test - public void testChapter4CompEq2() { - Parser parser = new Parser("return 3==4; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return 0;", ret.print()); - } - - @Test - public void testChapter4CompNEq() { - Parser parser = new Parser("return 3!=3; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return 0;", ret.print()); - } - - @Test - public void testChapter4CompNEq2() { - Parser parser = new Parser("return 3!=4; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return 1;", ret.print()); - } - - @Test - public void testChapter4Bug1() { - Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return (arg+3);", ret.print()); - } - - @Test - public void testChapter4Bug2() { - Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return (arg+1);", ret.print()); - } - - @Test - public void testChapter4Bug3() { - try { - new Parser("inta=1; return a;").parse(); - fail(); - } catch( RuntimeException e ) { - 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() { - Parser parser = new Parser("int a=1; return a;"); - StopNode ret = parser.parse(); - assertEquals("return 1;", ret.print()); - } - - @Test - public void testVarAdd() { - Parser parser = new Parser("int a=1; int b=2; return a+b;"); - StopNode ret = parser.parse(); - assertEquals("return 3;", ret.print()); - } - - @Test - public void testVarScope() { - Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); - StopNode ret = parser.parse(); - assertEquals("return 4;", ret.print()); - } - - @Test - public void testVarScopeNoPeephole() { - Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;"); - Node._disablePeephole = true; - StopNode ret = parser.parse(); - Node._disablePeephole = false; - assertEquals("return (1+3);", ret.print()); - } - - @Test - public void testVarDist() { - Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return 8;", ret.print()); - } - - @Test - public void testSelfAssign() { - try { - new Parser("int a=a; return a;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Undefined name 'a'",e.getMessage()); - } - } - - @Test - public void testChapter2ParseGrammar() { - Parser parser = new Parser("return 1+2*3+-5;"); - Node._disablePeephole = true; // disable peephole so we can observe full graph - StopNode ret = parser.parse(); - assertEquals("return (1+((2*3)+(-5)));", ret.print()); - GraphVisualizer gv = new GraphVisualizer(); - System.out.println(gv.generateDotOutput(parser)); - Node._disablePeephole = false; - } - - @Test - public void testChapter2AddPeephole() { - Parser parser = new Parser("return 1+2;"); - StopNode ret = parser.parse(); - assertEquals("return 3;", ret.print()); - } - - @Test - public void testChapter2SubPeephole() { - Parser parser = new Parser("return 1-2;"); - StopNode ret = parser.parse(); - assertEquals("return -1;", ret.print()); - } - - @Test - public void testChapter2MulPeephole() { - Parser parser = new Parser("return 2*3;"); - StopNode ret = parser.parse(); - assertEquals("return 6;", ret.print()); - } - - @Test - public void testChapter2DivPeephole() { - Parser parser = new Parser("return 6/3;"); - StopNode ret = parser.parse(); - assertEquals("return 2;", ret.print()); - } - - @Test - public void testChapter2MinusPeephole() { - Parser parser = new Parser("return 6/-3;"); - StopNode ret = parser.parse(); - assertEquals("return -2;", ret.print()); - } - - @Test - public void testChapter2Example() { - Parser parser = new Parser("return 1+2*3+-5;"); - StopNode ret = parser.parse(); - assertEquals("return 2;", ret.print()); - GraphVisualizer gv = new GraphVisualizer(); - System.out.println(gv.generateDotOutput(parser)); - } - - @Test - public void testSimpleProgram() { - Parser parser = new Parser("return 1;"); - StopNode stop = parser.parse(); - StartNode start = Parser.START; - ReturnNode ret = (ReturnNode)stop.in(0); - - assertTrue(ret.ctrl() instanceof ProjNode); - Node expr = ret.expr(); - if( expr instanceof ConstantNode con ) { - assertEquals(start,con.in(0)); - assertEquals(TypeInteger.constant(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(TypeInteger.constant(0),con._type); - } - - @Test - public void testBad1() { - try { - new Parser("ret").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected =: ",e.getMessage()); - } - } - - @Test - public void testBad2() { - try { - new Parser("return 0123;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); - } - } - - @Test - public void testNotBad3() { - // this test used to fail in chapter 1 - assertEquals("return 12;", new Parser("return --12;").parse().print()); - } - - @Test - public void testBad4() { - try { - new Parser("return 100").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected ;: ",e.getMessage()); - } - } - - @Test - public void testNotBad5() { - // this test used to fail in chapter 1 - assertEquals("return -100;", new Parser("return -100;").parse().print()); - } - - @Test - public void testBad6() { - try { - new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); - fail(); - } catch( RuntimeException e ) { - 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()); - } - } - } diff --git a/chapter07/README.md b/chapter07/README.md index 03181d18..fe4c0625 100644 --- a/chapter07/README.md +++ b/chapter07/README.md @@ -1,4 +1,4 @@ -# Chapter 7 +# Chapter 7: While Statement In this chapter we introduce the `while` statement. diff --git a/chapter07/docs/Makefile b/chapter07/docs/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/chapter07/docs/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/chapter07/docs/build-graphs.sh b/chapter07/docs/build-graphs.sh deleted file mode 100644 index 27b2b72f..00000000 --- a/chapter07/docs/build-graphs.sh +++ /dev/null @@ -1,6 +0,0 @@ -dot -Tsvg 07-graph1.gv > 07-graph1.svg -dot -Tsvg 07-graph2.gv > 07-graph2.svg -dot -Tsvg 07-graph3.gv > 07-graph3.svg -dot -Tsvg 07-graph4.gv > 07-graph4.svg - - diff --git a/chapter07/src/main/java/com/seaofnodes/simple/Parser.java b/chapter07/src/main/java/com/seaofnodes/simple/Parser.java index 349b2ce7..b4418ced 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/Parser.java @@ -547,6 +547,7 @@ public class Parser { String getAnyNextToken() { if (isEOF()) return ""; if (isIdStart(peek())) return parseId(); + if (isNumber(peek())) return parseNumberString(); if (isPunctuation(peek())) return parsePunctuation(); return String.valueOf(peek()); } @@ -555,13 +556,16 @@ public class Parser { boolean isNumber(char ch) {return Character.isDigit(ch);} private Type parseNumber() { - int start = _position; - while (isNumber(nextChar())) ; - String snum = new String(_input, start, --_position - start); + String snum = parseNumberString(); if (snum.length() > 1 && snum.charAt(0) == '0') throw error("Syntax error: integer values cannot start with '0'"); return TypeInteger.constant(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) { diff --git a/chapter07/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter07/src/test/java/com/seaofnodes/simple/Chapter01Test.java new file mode 100644 index 00000000..547c36f8 --- /dev/null +++ b/chapter07/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -0,0 +1,100 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter01Test { + + @Test + public void testSimpleProgram() { + Parser parser = new Parser("return 1;"); + StopNode stop = parser.parse(); + StartNode start = Parser.START; + ReturnNode ret = (ReturnNode)stop.in(0); + + assertTrue(ret.ctrl() instanceof ProjNode); + Node expr = ret.expr(); + if( expr instanceof ConstantNode con ) { + assertEquals(start,con.in(0)); + assertEquals(TypeInteger.constant(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(TypeInteger.constant(0),con._type); + } + + @Test + public void testBad1() { + try { + new Parser("ret").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected =: ",e.getMessage()); + } + } + + @Test + public void testBad2() { + try { + new Parser("return 0123;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); + } + } + + @Test + public void testNotBad3() { + // this test used to fail in chapter 1 + assertEquals("return 12;", new Parser("return --12;").parse().print()); + } + + @Test + public void testBad4() { + try { + new Parser("return 100").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected ;: ",e.getMessage()); + } + } + + @Test + public void testNotBad5() { + // this test used to fail in chapter 1 + assertEquals("return -100;", new Parser("return -100;").parse().print()); + } + + @Test + public void testBad6() { + try { + new Parser("return100").parse(); + fail(); + } catch( RuntimeException e ) { + 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()); + } + } + +} diff --git a/chapter07/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter07/src/test/java/com/seaofnodes/simple/Chapter02Test.java new file mode 100644 index 00000000..4085ed7e --- /dev/null +++ b/chapter07/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -0,0 +1,66 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter02Test { + + @Test + public void testParseGrammar() { + Parser parser = new Parser("return 1+2*3+-5;"); + Node._disablePeephole = true; // disable peephole so we can observe full graph + StopNode ret = parser.parse(); + assertEquals("return (1+((2*3)+(-5)));", ret.print()); + GraphVisualizer gv = new GraphVisualizer(); + System.out.println(gv.generateDotOutput(parser)); + Node._disablePeephole = false; + } + + @Test + public void testAddPeephole() { + Parser parser = new Parser("return 1+2;"); + StopNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testSubPeephole() { + Parser parser = new Parser("return 1-2;"); + StopNode ret = parser.parse(); + assertEquals("return -1;", ret.print()); + } + + @Test + public void testMulPeephole() { + Parser parser = new Parser("return 2*3;"); + StopNode ret = parser.parse(); + assertEquals("return 6;", ret.print()); + } + + @Test + public void testDivPeephole() { + Parser parser = new Parser("return 6/3;"); + StopNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + + @Test + public void testMinusPeephole() { + Parser parser = new Parser("return 6/-3;"); + StopNode ret = parser.parse(); + assertEquals("return -2;", ret.print()); + } + + @Test + public void testExample() { + Parser parser = new Parser("return 1+2*3+-5;"); + StopNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + GraphVisualizer gv = new GraphVisualizer(); + System.out.println(gv.generateDotOutput(parser)); + } + +} diff --git a/chapter07/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter07/src/test/java/com/seaofnodes/simple/Chapter03Test.java new file mode 100644 index 00000000..407fbe48 --- /dev/null +++ b/chapter07/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -0,0 +1,68 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter03Test { + + @Test + public void testVarDecl() { + Parser parser = new Parser("int a=1; return a;"); + StopNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testVarAdd() { + Parser parser = new Parser("int a=1; int b=2; return a+b;"); + StopNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testVarScope() { + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); + StopNode ret = parser.parse(); + assertEquals("return 4;", ret.print()); + } + + @Test + public void testVarScopeNoPeephole() { + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;"); + Node._disablePeephole = true; + StopNode ret = parser.parse(); + Node._disablePeephole = false; + assertEquals("return (1+3);", ret.print()); + } + + @Test + public void testVarDist() { + Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 8;", ret.print()); + } + + @Test + public void testSelfAssign() { + try { + new Parser("int a=a; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'a'",e.getMessage()); + } + } + + @Test + public void testBad1() { + try { + new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected }: ",e.getMessage()); + } + } + +} diff --git a/chapter07/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter07/src/test/java/com/seaofnodes/simple/Chapter04Test.java new file mode 100644 index 00000000..cde23324 --- /dev/null +++ b/chapter07/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -0,0 +1,128 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter04Test { + + @Test + public void testPeephole() { + Parser parser = new Parser("return 1+arg+2; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return (arg+3);", ret.print()); + } + + @Test + public void testPeephole2() { + Parser parser = new Parser("return (1+arg)+2;"); + StopNode ret = parser.parse(); + assertEquals("return (arg+3);", ret.print()); + } + + @Test + public void testAdd0() { + Parser parser = new Parser("return 0+arg;"); + StopNode ret = parser.parse(); + assertEquals("return arg;", ret.print()); + } + + @Test + public void testAddAddMul() { + Parser parser = new Parser("return arg+0+arg;"); + StopNode ret = parser.parse(); + assertEquals("return (arg*2);", ret.print()); + } + + @Test + public void testPeephole3() { + Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return ((arg*2)+6);", ret.print()); + } + + @Test + public void testMul1() { + Parser parser = new Parser("return 1*arg;"); + StopNode ret = parser.parse(); + assertEquals("return arg;", ret.print()); + } + + @Test + public void testVarArg() { + Parser parser = new Parser("return arg; #showGraph;"); + StopNode stop = parser.parse(); + ReturnNode ret = stop.ret(); + assertTrue(ret.in(0) instanceof ProjNode); + assertTrue(ret.in(1) instanceof ProjNode); + } + + @Test + public void testConstantArg() { + Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2)); + StopNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + + @Test + public void testCompEq() { + Parser parser = new Parser("return 3==3; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testCompEq2() { + Parser parser = new Parser("return 3==4; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 0;", ret.print()); + } + + @Test + public void testCompNEq() { + Parser parser = new Parser("return 3!=3; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 0;", ret.print()); + } + + @Test + public void testCompNEq2() { + Parser parser = new Parser("return 3!=4; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testBug1() { + Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return (arg+3);", ret.print()); + } + + @Test + public void testBug2() { + Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return (arg+1);", ret.print()); + } + + @Test + public void testBug3() { + try { + new Parser("inta=1; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'inta'",e.getMessage()); + } + } + + @Test + public void testBug4() { + Parser parser = new Parser("return -arg;"); + StopNode ret = parser.parse(); + assertEquals("return (-arg);", ret.print()); + } + +} diff --git a/chapter07/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter07/src/test/java/com/seaofnodes/simple/Chapter05Test.java new file mode 100644 index 00000000..99e35d0a --- /dev/null +++ b/chapter07/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -0,0 +1,214 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Rule; +import org.junit.Test; +import org.junit.rules.ExpectedException; + +import static org.junit.Assert.*; + +public class Chapter05Test { + + @Test + public void testIfStmt() { + Parser parser = new Parser( +""" +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; + #showGraph; +} +#showGraph; +return a;"""); + StopNode ret = parser.parse(true); + assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString()); + } + + @Test + public void testTest() { + Parser parser = new Parser( +""" +int c = 3; +int b = 2; +if (arg == 1) { + b = 3; + c = 4; +} +return c;""", TypeInteger.BOT); + StopNode ret = parser.parse(true); + assertEquals("return Phi(Region16,4,3);", ret.toString()); + } + + @Test + public void testReturn2() { + 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 testIfMergeB() { + 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 testIfMerge2() { + 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(Region,4,5));", ret.toString()); + } + + @Test + public void testMerge3() { + 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 testMerge4() { + 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 testMerge5() { + 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()); + } + + @Test + public void testTrue() { + StopNode stop = new Parser("return true;").parse(); + assertEquals("return 1;",stop.toString()); + } + + @Test + public void testHalfDef() { + try { + new Parser("if( arg==1 ) int b=2; return b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Cannot define a new name on one arm of an if",e.getMessage()); + } + } + + @Test + public void testHalfDef2() { + try { + new Parser("if( arg==1 ) { int b=2; } else { int b=3; } return b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'b'",e.getMessage()); + } + } + + @Test + public void testRegress1() { + try { + new Parser("if(arg==2) int a=1; else int b=2; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Cannot define a new name on one arm of an if",e.getMessage()); + } + } + + @Test + public void testBadNum() { + try { + new Parser("return 1-;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected an identifier or expression: ;",e.getMessage()); + } + } + + @Test + public void testKeyword1() { + try { + new Parser("int true=0; return true;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Expected an identifier, found 'true'",e.getMessage()); + } + } + + @Test + public void testKeyword2() { + try { + new Parser("int else=arg; if(else) else=2; else else=1; return else;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Expected an identifier, found 'else'",e.getMessage()); + } + } + + @Test + public void testKeyword3() { + try { + new Parser("int a=1; ififif(arg)inta=2;return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected =: (",e.getMessage()); + } + } + +} diff --git a/chapter07/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter07/src/test/java/com/seaofnodes/simple/Chapter06Test.java new file mode 100644 index 00000000..618c8ca6 --- /dev/null +++ b/chapter07/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -0,0 +1,294 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter06Test { + + @Test + public void testPeepholeReturn() { + Parser parser = new Parser( +""" +if( true ) return 2; +return 1; +"""); + StopNode stop = parser.parse(true); + assertEquals("return 2;", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testPeepholeRotate() { + Parser parser = new Parser( +""" +int a = 1; +if (arg) + a = 2; +return (arg < a) < 3; +"""); + StopNode stop = parser.parse(false); + assertEquals("return ((arg<Phi(Region12,2,1))<3);", stop.toString()); + } + + @Test + public void testPeepholeCFG() { + Parser parser = new Parser( +""" +int a=1; +if( true ) + a=2; +else + a=3; +return a; +"""); + StopNode stop = parser.parse(true); + assertEquals("return 2;", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testIfIf() { + Parser parser = new Parser( +""" +int a=1; +if( arg!=1 ) + a=2; +else + a=3; +int b=4; +if( a==2 ) + b=42; +else + b=5; +return b;""", TypeInteger.BOT); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Region32,42,5);", stop.toString()); + } + + @Test + public void testIfArgIf() { + Parser parser = new Parser( +""" +int a=1; +if( 1==1 ) + a=2; +else + a=3; +int b=4; +if( arg==2 ) + b=a; +else + b=5; +return b;""", TypeInteger.BOT); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Region28,2,5);", stop.toString()); + } + + @Test + public void testMerge3With2() { + 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.constant(2)); + StopNode stop = parser.parse(); + assertEquals("return 5;", stop.toString()); + } + + @Test + public void testMerge3With1() { + 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; +""", TypeInteger.constant(1)); + StopNode stop = parser.parse(true); + assertEquals("return 3;", stop.toString()); + } + + @Test + public void testMerge3Peephole() { + Parser parser = new Parser( +""" +int a=1; +if( arg==1 ) + if( 1==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +""", TypeInteger.BOT); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Region36,3,Phi(Region34,4,5));", stop.toString()); + } + + @Test + public void testMerge3Peephole1() { + Parser parser = new Parser( +""" +int a=1; +if( arg==1 ) + if( 1==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +""", TypeInteger.constant(1)); + StopNode stop = parser.parse(true); + assertEquals("return 3;", stop.toString()); + } + + @Test + public void testMerge3Peephole3() { + Parser parser = new Parser( +""" +int a=1; +if( arg==1 ) + if( 1==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +""", TypeInteger.constant(3)); + StopNode stop = parser.parse(true); + assertEquals("return 4;", stop.toString()); + } + + @Test + public void testDemo1NonConst() { + Parser parser = new Parser(""" +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; +"""); + StopNode ret = parser.parse(true); + assertEquals("return Phi(Region22,4,1);", ret.toString()); + } + + + @Test + public void testDemo1True() { + Parser parser = new Parser(""" +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; +""", TypeInteger.constant(1)); + StopNode ret = parser.parse(true); + assertEquals("return 4;", ret.toString()); + } + + @Test + public void testDemo1False() { + Parser parser = new Parser(""" +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; +""", TypeInteger.constant(0)); + StopNode ret = parser.parse(true); + assertEquals("return 1;", ret.toString()); + } + + @Test + public void testDemo2NonConst() { + Parser parser = new Parser(""" +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; +"""); + StopNode ret = parser.parse(true); + assertEquals("return (Phi(Region33,Phi(Region22,2,3),0)+Phi(Region,3,1));", ret.toString()); + } + + + @Test + public void testDemo2True() { + Parser parser = new Parser(""" +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; +""", TypeInteger.constant(1)); + StopNode ret = parser.parse(true); + assertEquals("return 6;", ret.toString()); + } + + @Test + public void testDemo2arg2() { + Parser parser = new Parser(""" +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; +""", TypeInteger.constant(2)); + StopNode ret = parser.parse(true); + assertEquals("return 5;", ret.toString()); + } + +} diff --git a/chapter07/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/chapter07/src/test/java/com/seaofnodes/simple/Chapter07Test.java index 9afcc49a..2e34b520 100644 --- a/chapter07/src/test/java/com/seaofnodes/simple/Chapter07Test.java +++ b/chapter07/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -9,7 +9,7 @@ import static org.junit.Assert.*; public class Chapter07Test { @Test - public void testChapter7Example() { + public void testExample() { Parser parser = new Parser( """ while(arg < 10) { @@ -26,9 +26,8 @@ public class Chapter07Test { } @Test - public void testChapter7Regression() { + public void testRegression() { Parser parser = new Parser( - """ int a = 1; if(arg){}else{ @@ -43,9 +42,8 @@ return a; } @Test - public void testChapter7WhileNested() { + public void testWhileNested() { Parser parser = new Parser( - """ int sum = 0; int i = 0; @@ -65,7 +63,7 @@ return sum; } @Test - public void testChapter7WhileScope() { + public void testWhileScope() { Parser parser = new Parser( """ int a = 1; @@ -85,7 +83,7 @@ return b; } @Test - public void testChapter7WhileNestedIfAndInc() { + public void testWhileNestedIfAndInc() { Parser parser = new Parser( """ int a = 1; @@ -106,7 +104,7 @@ return b; @Test - public void testChapter7While() { + public void testWhile() { Parser parser = new Parser( """ int a = 1; @@ -124,7 +122,7 @@ return a; } @Test - public void testChapter7WhilePeep() { + public void testWhilePeep() { Parser parser = new Parser( """ int a = 1; @@ -140,7 +138,7 @@ return a; } @Test - public void testChapter7While2() { + public void testWhile2() { Parser parser = new Parser( """ int a = 1; @@ -156,7 +154,7 @@ return a; } @Test - public void testChapter7While2Peep() { + public void testWhile2Peep() { Parser parser = new Parser( """ int a = 1; @@ -170,7 +168,7 @@ return a; } @Test - public void testChapter7While3() { + public void testWhile3() { Parser parser = new Parser( """ int a = 1; @@ -188,7 +186,7 @@ return a; } @Test - public void testChapter7While3Peep() { + public void testWhile3Peep() { Parser parser = new Parser( """ int a = 1; @@ -204,7 +202,7 @@ return a; } @Test - public void testChapter7While4() { + public void testWhile4() { Parser parser = new Parser( """ int a = 1; @@ -223,7 +221,7 @@ return a; } @Test - public void testChapter7While4Peep() { + public void testWhile4Peep() { Parser parser = new Parser( """ int a = 1; @@ -239,788 +237,4 @@ return a; assertTrue(stop.ret().ctrl() instanceof ProjNode); } - @Test - public void testChapter6PeepholeReturn() { - Parser parser = new Parser( -""" -if( true ) return 2; -return 1; -"""); - StopNode stop = parser.parse(true); - assertEquals("return 2;", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); - } - - @Test - public void testChapter6PeepholeRotate() { - Parser parser = new Parser( -""" -int a = 1; -if (arg) - a = 2; -return (arg < a) < 3; -"""); - StopNode stop = parser.parse(false); - assertEquals("return ((arg<Phi(Region12,2,1))<3);", stop.toString()); - } - - @Test - public void testChapter6PeepholeCFG() { - Parser parser = new Parser( -""" -int a=1; -if( true ) - a=2; -else - a=3; -return a; -"""); - StopNode stop = parser.parse(true); - assertEquals("return 2;", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); - } - - @Test - public void testChapter6IfIf() { - Parser parser = new Parser( -""" -int a=1; -if( arg!=1 ) - a=2; -else - a=3; -int b=4; -if( a==2 ) - b=42; -else - b=5; -return b;""", TypeInteger.BOT); - StopNode stop = parser.parse(true); - assertEquals("return Phi(Region32,42,5);", stop.toString()); - } - - @Test - public void testChapter6IfArgIf() { - Parser parser = new Parser( -""" -int a=1; -if( 1==1 ) - a=2; -else - a=3; -int b=4; -if( arg==2 ) - b=a; -else - b=5; -return b;""", TypeInteger.BOT); - StopNode stop = parser.parse(true); - assertEquals("return Phi(Region28,2,5);", stop.toString()); - } - - @Test - public void testChapter6Merge3With2() { - 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.constant(2)); - StopNode stop = parser.parse(); - assertEquals("return 5;", stop.toString()); - } - - @Test - public void testChapter6Merge3With1() { - 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; -""", TypeInteger.constant(1)); - StopNode stop = parser.parse(true); - assertEquals("return 3;", stop.toString()); - } - - @Test - public void testChapter6Merge3Peephole() { - Parser parser = new Parser( -""" -int a=1; -if( arg==1 ) - if( 1==2 ) - a=2; - else - a=3; -else if( arg==3 ) - a=4; -else - a=5; -return a; -""", TypeInteger.BOT); - StopNode stop = parser.parse(true); - assertEquals("return Phi(Region36,3,Phi(Region34,4,5));", stop.toString()); - } - - @Test - public void testChapter6Merge3Peephole1() { - Parser parser = new Parser( -""" -int a=1; -if( arg==1 ) - if( 1==2 ) - a=2; - else - a=3; -else if( arg==3 ) - a=4; -else - a=5; -return a; -""", TypeInteger.constant(1)); - StopNode stop = parser.parse(true); - assertEquals("return 3;", stop.toString()); - } - - @Test - public void testChapter6Merge3Peephole3() { - Parser parser = new Parser( -""" -int a=1; -if( arg==1 ) - if( 1==2 ) - a=2; - else - a=3; -else if( arg==3 ) - a=4; -else - a=5; -return a; -""", TypeInteger.constant(3)); - StopNode stop = parser.parse(true); - assertEquals("return 4;", stop.toString()); - } - - @Test - public void testChapter6Demo1NonConst() { - Parser parser = new Parser(""" -int a = 0; -int b = 1; -if( arg ) { - a = 2; - if( arg ) { b = 2; } - else b = 3; -} -return a+b; -"""); - StopNode ret = parser.parse(true); - assertEquals("return Phi(Region22,4,1);", ret.toString()); - } - - - @Test - public void testChapter6Demo1True() { - Parser parser = new Parser(""" -int a = 0; -int b = 1; -if( arg ) { - a = 2; - if( arg ) { b = 2; } - else b = 3; -} -return a+b; -""", TypeInteger.constant(1)); - StopNode ret = parser.parse(true); - assertEquals("return 4;", ret.toString()); - } - - @Test - public void testChapter6Demo1False() { - Parser parser = new Parser(""" -int a = 0; -int b = 1; -if( arg ) { - a = 2; - if( arg ) { b = 2; } - else b = 3; -} -return a+b; -""", TypeInteger.constant(0)); - StopNode ret = parser.parse(true); - assertEquals("return 1;", ret.toString()); - } - - @Test - public void testChapter6Demo2NonConst() { - Parser parser = new Parser(""" -int a = 0; -int b = 1; -int c = 0; -if( arg ) { - a = 1; - if( arg==2 ) { c=2; } else { c=3; } - if( arg ) { b = 2; } - else b = 3; -} -return a+b+c; -"""); - StopNode ret = parser.parse(true); - assertEquals("return (Phi(Region33,Phi(Region22,2,3),0)+Phi(Region,3,1));", ret.toString()); - } - - - @Test - public void testChapter6Demo2True() { - Parser parser = new Parser(""" -int a = 0; -int b = 1; -int c = 0; -if( arg ) { - a = 1; - if( arg==2 ) { c=2; } else { c=3; } - if( arg ) { b = 2; } - else b = 3; -} -return a+b+c; -""", TypeInteger.constant(1)); - StopNode ret = parser.parse(true); - assertEquals("return 6;", ret.toString()); - } - - @Test - public void testChapter6Demo2arg2() { - Parser parser = new Parser(""" -int a = 0; -int b = 1; -int c = 0; -if( arg ) { - a = 1; - if( arg==2 ) { c=2; } else { c=3; } - if( arg ) { b = 2; } - else b = 3; -} -return a+b+c; -""", TypeInteger.constant(2)); - StopNode ret = parser.parse(true); - assertEquals("return 5;", ret.toString()); - } - - - - @Test - public void testChapter5IfStmt() { - Parser parser = new Parser( -""" -int a = 1; -if (arg == 1) - a = arg+2; -else { - a = arg-3; - #showGraph; -} -#showGraph; -return a;"""); - StopNode ret = parser.parse(true); - assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString()); - } - - @Test - public void testChapter5Test() { - Parser parser = new Parser( -""" -int c = 3; -int b = 2; -if (arg == 1) { - b = 3; - c = 4; -} -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); - 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;"""); - 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;"""); - StopNode ret = parser.parse(true); - assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region,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); - 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); - 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;"""); - StopNode ret = parser.parse(true); - assertEquals("return (arg==Phi(Region16,3,2));", ret.toString()); - } - - @Test - public void testChapter5True() { - StopNode stop = new Parser("return true;").parse(); - assertEquals("return 1;",stop.toString()); - } - - @Test - public void testChapter5HalfDef() { - try { - new Parser("if( arg==1 ) int b=2; return b;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Cannot define a new name on one arm of an if",e.getMessage()); - } - } - - @Test - public void testChapter5HalfDef2() { - try { - new Parser("if( arg==1 ) { int b=2; } else { int b=3; } return b;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Undefined name 'b'",e.getMessage()); - } - } - - @Test - public void testChapter5BadNum() { - try { - new Parser("return 1-;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected an identifier or expression: ;",e.getMessage()); - } - } - - @Test - public void testChapter5Keyword1() { - try { - new Parser("int true=0; return true;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Expected an identifier, found 'true'",e.getMessage()); - } - } - - @Test - public void testChapter5Keyword2() { - try { - new Parser("int else=arg; if(else) else=2; else else=1; return else;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Expected an identifier, found 'else'",e.getMessage()); - } - } - - @Test - public void testChapter5Keyword3() { - try { - new Parser("int a=1; ififif(arg)inta=2;return a;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected =: (",e.getMessage()); - } - } - - @Test - public void testChapter4Peephole() { - Parser parser = new Parser("return 1+arg+2; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return (arg+3);", ret.print()); - } - - @Test - public void testChapter4Peephole2() { - Parser parser = new Parser("return (1+arg)+2;"); - StopNode ret = parser.parse(); - assertEquals("return (arg+3);", ret.print()); - } - - @Test - public void testChapter4Add0() { - Parser parser = new Parser("return 0+arg;"); - StopNode ret = parser.parse(); - assertEquals("return arg;", ret.print()); - } - - @Test - public void testChapter4AddAddMul() { - Parser parser = new Parser("return arg+0+arg;"); - StopNode ret = parser.parse(); - assertEquals("return (arg*2);", ret.print()); - } - - @Test - public void testChapter4Peephole3() { - Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return ((arg*2)+6);", ret.print()); - } - - @Test - public void testChapter4Mul1() { - Parser parser = new Parser("return 1*arg;"); - StopNode ret = parser.parse(); - assertEquals("return arg;", ret.print()); - } - - @Test - public void testChapter4VarArg() { - Parser parser = new Parser("return arg; #showGraph;"); - StopNode stop = parser.parse(); - ReturnNode ret = stop.ret(); - assertTrue(ret.in(0) instanceof ProjNode); - assertTrue(ret.in(1) instanceof ProjNode); - } - - @Test - public void testChapter4ConstantArg() { - Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2)); - StopNode ret = parser.parse(); - assertEquals("return 2;", ret.print()); - } - - @Test - public void testChapter4CompEq() { - Parser parser = new Parser("return 3==3; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return 1;", ret.print()); - } - - @Test - public void testChapter4CompEq2() { - Parser parser = new Parser("return 3==4; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return 0;", ret.print()); - } - - @Test - public void testChapter4CompNEq() { - Parser parser = new Parser("return 3!=3; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return 0;", ret.print()); - } - - @Test - public void testChapter4CompNEq2() { - Parser parser = new Parser("return 3!=4; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return 1;", ret.print()); - } - - @Test - public void testChapter4Bug1() { - Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return (arg+3);", ret.print()); - } - - @Test - public void testChapter4Bug2() { - Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return (arg+1);", ret.print()); - } - - @Test - public void testChapter4Bug3() { - try { - new Parser("inta=1; return a;").parse(); - fail(); - } catch( RuntimeException e ) { - 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() { - Parser parser = new Parser("int a=1; return a;"); - StopNode ret = parser.parse(); - assertEquals("return 1;", ret.print()); - } - - @Test - public void testVarAdd() { - Parser parser = new Parser("int a=1; int b=2; return a+b;"); - StopNode ret = parser.parse(); - assertEquals("return 3;", ret.print()); - } - - @Test - public void testVarScope() { - Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); - StopNode ret = parser.parse(); - assertEquals("return 4;", ret.print()); - } - - @Test - public void testVarScopeNoPeephole() { - Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;"); - Node._disablePeephole = true; - StopNode ret = parser.parse(); - Node._disablePeephole = false; - assertEquals("return (1+3);", ret.print()); - } - - @Test - public void testVarDist() { - Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return 8;", ret.print()); - } - - @Test - public void testSelfAssign() { - try { - new Parser("int a=a; return a;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Undefined name 'a'",e.getMessage()); - } - } - - @Test - public void testChapter2ParseGrammar() { - Parser parser = new Parser("return 1+2*3+-5;"); - Node._disablePeephole = true; // disable peephole so we can observe full graph - StopNode ret = parser.parse(); - assertEquals("return (1+((2*3)+(-5)));", ret.print()); - GraphVisualizer gv = new GraphVisualizer(); - System.out.println(gv.generateDotOutput(parser)); - Node._disablePeephole = false; - } - - @Test - public void testChapter2AddPeephole() { - Parser parser = new Parser("return 1+2;"); - StopNode ret = parser.parse(); - assertEquals("return 3;", ret.print()); - } - - @Test - public void testChapter2SubPeephole() { - Parser parser = new Parser("return 1-2;"); - StopNode ret = parser.parse(); - assertEquals("return -1;", ret.print()); - } - - @Test - public void testChapter2MulPeephole() { - Parser parser = new Parser("return 2*3;"); - StopNode ret = parser.parse(); - assertEquals("return 6;", ret.print()); - } - - @Test - public void testChapter2DivPeephole() { - Parser parser = new Parser("return 6/3;"); - StopNode ret = parser.parse(); - assertEquals("return 2;", ret.print()); - } - - @Test - public void testChapter2MinusPeephole() { - Parser parser = new Parser("return 6/-3;"); - StopNode ret = parser.parse(); - assertEquals("return -2;", ret.print()); - } - - @Test - public void testChapter2Example() { - Parser parser = new Parser("return 1+2*3+-5;"); - StopNode ret = parser.parse(); - assertEquals("return 2;", ret.print()); - GraphVisualizer gv = new GraphVisualizer(); - System.out.println(gv.generateDotOutput(parser)); - } - - @Test - public void testSimpleProgram() { - Parser parser = new Parser("return 1;"); - StopNode stop = parser.parse(); - StartNode start = Parser.START; - ReturnNode ret = (ReturnNode)stop.in(0); - - assertTrue(ret.ctrl() instanceof ProjNode); - Node expr = ret.expr(); - if( expr instanceof ConstantNode con ) { - assertEquals(start,con.in(0)); - assertEquals(TypeInteger.constant(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(TypeInteger.constant(0),con._type); - } - - @Test - public void testBad1() { - try { - new Parser("ret").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected =: ",e.getMessage()); - } - } - - @Test - public void testBad2() { - try { - new Parser("return 0123;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); - } - } - - @Test - public void testNotBad3() { - // this test used to fail in chapter 1 - assertEquals("return 12;", new Parser("return --12;").parse().print()); - } - - @Test - public void testBad4() { - try { - new Parser("return 100").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected ;: ",e.getMessage()); - } - } - - @Test - public void testNotBad5() { - // this test used to fail in chapter 1 - assertEquals("return -100;", new Parser("return -100;").parse().print()); - } - - @Test - public void testBad6() { - try { - new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); - fail(); - } catch( RuntimeException e ) { - 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()); - } - } - } diff --git a/chapter08/README.md b/chapter08/README.md index 4c095912..41d6c11c 100644 --- a/chapter08/README.md +++ b/chapter08/README.md @@ -1,4 +1,4 @@ -# Chapter 8 +# Chapter 8: Lazy Phis, Break, Continue, and Evaluator In this chapter: diff --git a/chapter08/docs/Makefile b/chapter08/docs/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/chapter08/docs/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/chapter08/docs/build-graphs.sh b/chapter08/docs/build-graphs.sh deleted file mode 100644 index f660790b..00000000 --- a/chapter08/docs/build-graphs.sh +++ /dev/null @@ -1,6 +0,0 @@ -dot -Tsvg 08-graph1.gv > 08-graph1.svg -dot -Tsvg 08-graph2.gv > 08-graph2.svg -dot -Tsvg 08-graph3.gv > 08-graph3.svg - - - diff --git a/chapter08/src/main/java/com/seaofnodes/simple/Parser.java b/chapter08/src/main/java/com/seaofnodes/simple/Parser.java index d4b0c327..eae6e0c6 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/Parser.java @@ -594,6 +594,7 @@ public class Parser { String getAnyNextToken() { if (isEOF()) return ""; if (isIdStart(peek())) return parseId(); + if (isNumber(peek())) return parseNumberString(); if (isPunctuation(peek())) return parsePunctuation(); return String.valueOf(peek()); } @@ -602,13 +603,16 @@ public class Parser { boolean isNumber(char ch) {return Character.isDigit(ch);} private Type parseNumber() { - int start = _position; - while (isNumber(nextChar())) ; - String snum = new String(_input, start, --_position - start); + String snum = parseNumberString(); if (snum.length() > 1 && snum.charAt(0) == '0') throw error("Syntax error: integer values cannot start with '0'"); return TypeInteger.constant(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) { diff --git a/chapter08/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter08/src/test/java/com/seaofnodes/simple/Chapter01Test.java new file mode 100644 index 00000000..13b42f96 --- /dev/null +++ b/chapter08/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -0,0 +1,100 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter01Test { + + @Test + public void testSimpleProgram() { + Parser parser = new Parser("return 1;"); + StopNode stop = parser.parse(); + StartNode start = Parser.START; + ReturnNode ret = (ReturnNode)stop.in(0); + + assertTrue(ret.ctrl() instanceof ProjNode); + Node expr = ret.expr(); + if( expr instanceof ConstantNode con ) { + assertEquals(start,con.in(0)); + assertEquals(TypeInteger.constant(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 && con._type instanceof TypeInteger ) + assertEquals(TypeInteger.constant(0),con._type); + } + + @Test + public void testBad1() { + try { + new Parser("ret").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected =: ",e.getMessage()); + } + } + + @Test + public void testBad2() { + try { + new Parser("return 0123;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); + } + } + + @Test + public void testNotBad3() { + // this test used to fail in chapter 1 + assertEquals("return 12;", new Parser("return --12;").parse().print()); + } + + @Test + public void testBad4() { + try { + new Parser("return 100").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected ;: ",e.getMessage()); + } + } + + @Test + public void testNotBad5() { + // this test used to fail in chapter 1 + assertEquals("return -100;", new Parser("return -100;").parse().print()); + } + + @Test + public void testBad6() { + try { + new Parser("return100").parse(); + fail(); + } catch( RuntimeException e ) { + 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()); + } + } + +} diff --git a/chapter08/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter08/src/test/java/com/seaofnodes/simple/Chapter02Test.java new file mode 100644 index 00000000..4085ed7e --- /dev/null +++ b/chapter08/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -0,0 +1,66 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter02Test { + + @Test + public void testParseGrammar() { + Parser parser = new Parser("return 1+2*3+-5;"); + Node._disablePeephole = true; // disable peephole so we can observe full graph + StopNode ret = parser.parse(); + assertEquals("return (1+((2*3)+(-5)));", ret.print()); + GraphVisualizer gv = new GraphVisualizer(); + System.out.println(gv.generateDotOutput(parser)); + Node._disablePeephole = false; + } + + @Test + public void testAddPeephole() { + Parser parser = new Parser("return 1+2;"); + StopNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testSubPeephole() { + Parser parser = new Parser("return 1-2;"); + StopNode ret = parser.parse(); + assertEquals("return -1;", ret.print()); + } + + @Test + public void testMulPeephole() { + Parser parser = new Parser("return 2*3;"); + StopNode ret = parser.parse(); + assertEquals("return 6;", ret.print()); + } + + @Test + public void testDivPeephole() { + Parser parser = new Parser("return 6/3;"); + StopNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + + @Test + public void testMinusPeephole() { + Parser parser = new Parser("return 6/-3;"); + StopNode ret = parser.parse(); + assertEquals("return -2;", ret.print()); + } + + @Test + public void testExample() { + Parser parser = new Parser("return 1+2*3+-5;"); + StopNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + GraphVisualizer gv = new GraphVisualizer(); + System.out.println(gv.generateDotOutput(parser)); + } + +} diff --git a/chapter08/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter08/src/test/java/com/seaofnodes/simple/Chapter03Test.java new file mode 100644 index 00000000..407fbe48 --- /dev/null +++ b/chapter08/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -0,0 +1,68 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter03Test { + + @Test + public void testVarDecl() { + Parser parser = new Parser("int a=1; return a;"); + StopNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testVarAdd() { + Parser parser = new Parser("int a=1; int b=2; return a+b;"); + StopNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testVarScope() { + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); + StopNode ret = parser.parse(); + assertEquals("return 4;", ret.print()); + } + + @Test + public void testVarScopeNoPeephole() { + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;"); + Node._disablePeephole = true; + StopNode ret = parser.parse(); + Node._disablePeephole = false; + assertEquals("return (1+3);", ret.print()); + } + + @Test + public void testVarDist() { + Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 8;", ret.print()); + } + + @Test + public void testSelfAssign() { + try { + new Parser("int a=a; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'a'",e.getMessage()); + } + } + + @Test + public void testBad1() { + try { + new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected }: ",e.getMessage()); + } + } + +} diff --git a/chapter08/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter08/src/test/java/com/seaofnodes/simple/Chapter04Test.java new file mode 100644 index 00000000..cde23324 --- /dev/null +++ b/chapter08/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -0,0 +1,128 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter04Test { + + @Test + public void testPeephole() { + Parser parser = new Parser("return 1+arg+2; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return (arg+3);", ret.print()); + } + + @Test + public void testPeephole2() { + Parser parser = new Parser("return (1+arg)+2;"); + StopNode ret = parser.parse(); + assertEquals("return (arg+3);", ret.print()); + } + + @Test + public void testAdd0() { + Parser parser = new Parser("return 0+arg;"); + StopNode ret = parser.parse(); + assertEquals("return arg;", ret.print()); + } + + @Test + public void testAddAddMul() { + Parser parser = new Parser("return arg+0+arg;"); + StopNode ret = parser.parse(); + assertEquals("return (arg*2);", ret.print()); + } + + @Test + public void testPeephole3() { + Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return ((arg*2)+6);", ret.print()); + } + + @Test + public void testMul1() { + Parser parser = new Parser("return 1*arg;"); + StopNode ret = parser.parse(); + assertEquals("return arg;", ret.print()); + } + + @Test + public void testVarArg() { + Parser parser = new Parser("return arg; #showGraph;"); + StopNode stop = parser.parse(); + ReturnNode ret = stop.ret(); + assertTrue(ret.in(0) instanceof ProjNode); + assertTrue(ret.in(1) instanceof ProjNode); + } + + @Test + public void testConstantArg() { + Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2)); + StopNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + + @Test + public void testCompEq() { + Parser parser = new Parser("return 3==3; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testCompEq2() { + Parser parser = new Parser("return 3==4; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 0;", ret.print()); + } + + @Test + public void testCompNEq() { + Parser parser = new Parser("return 3!=3; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 0;", ret.print()); + } + + @Test + public void testCompNEq2() { + Parser parser = new Parser("return 3!=4; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testBug1() { + Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return (arg+3);", ret.print()); + } + + @Test + public void testBug2() { + Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return (arg+1);", ret.print()); + } + + @Test + public void testBug3() { + try { + new Parser("inta=1; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'inta'",e.getMessage()); + } + } + + @Test + public void testBug4() { + Parser parser = new Parser("return -arg;"); + StopNode ret = parser.parse(); + assertEquals("return (-arg);", ret.print()); + } + +} diff --git a/chapter08/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter08/src/test/java/com/seaofnodes/simple/Chapter05Test.java new file mode 100644 index 00000000..ea348968 --- /dev/null +++ b/chapter08/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -0,0 +1,212 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter05Test { + + @Test + public void testIfStmt() { + Parser parser = new Parser( +""" +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; + #showGraph; +} +#showGraph; +return a;"""); + StopNode ret = parser.parse(true); + assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString()); + } + + @Test + public void testTest() { + Parser parser = new Parser( +""" +int c = 3; +int b = 2; +if (arg == 1) { + b = 3; + c = 4; +} +return c;""", TypeInteger.BOT); + StopNode ret = parser.parse(true); + assertEquals("return Phi(Region16,4,3);", ret.toString()); + } + + @Test + public void testReturn2() { + 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 testIfMergeB() { + 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 testIfMerge2() { + 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(Region,4,5));", ret.toString()); + } + + @Test + public void testMerge3() { + 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 testMerge4() { + 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 testMerge5() { + 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()); + } + + @Test + public void testTrue() { + StopNode stop = new Parser("return true;").parse(); + assertEquals("return 1;",stop.toString()); + } + + @Test + public void testHalfDef() { + try { + new Parser("if( arg==1 ) int b=2; return b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Cannot define a new name on one arm of an if",e.getMessage()); + } + } + + @Test + public void testHalfDef2() { + try { + new Parser("if( arg==1 ) { int b=2; } else { int b=3; } return b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'b'",e.getMessage()); + } + } + + @Test + public void testRegress1() { + try { + new Parser("if(arg==2) int a=1; else int b=2; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Cannot define a new name on one arm of an if",e.getMessage()); + } + } + + @Test + public void testBadNum() { + try { + new Parser("return 1-;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected an identifier or expression: ;",e.getMessage()); + } + } + + @Test + public void testKeyword1() { + try { + new Parser("int true=0; return true;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Expected an identifier, found 'true'",e.getMessage()); + } + } + + @Test + public void testKeyword2() { + try { + new Parser("int else=arg; if(else) else=2; else else=1; return else;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Expected an identifier, found 'else'",e.getMessage()); + } + } + + @Test + public void testKeyword3() { + try { + new Parser("int a=1; ififif(arg)inta=2;return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected =: (",e.getMessage()); + } + } + +} diff --git a/chapter08/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter08/src/test/java/com/seaofnodes/simple/Chapter06Test.java new file mode 100644 index 00000000..618c8ca6 --- /dev/null +++ b/chapter08/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -0,0 +1,294 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter06Test { + + @Test + public void testPeepholeReturn() { + Parser parser = new Parser( +""" +if( true ) return 2; +return 1; +"""); + StopNode stop = parser.parse(true); + assertEquals("return 2;", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testPeepholeRotate() { + Parser parser = new Parser( +""" +int a = 1; +if (arg) + a = 2; +return (arg < a) < 3; +"""); + StopNode stop = parser.parse(false); + assertEquals("return ((arg<Phi(Region12,2,1))<3);", stop.toString()); + } + + @Test + public void testPeepholeCFG() { + Parser parser = new Parser( +""" +int a=1; +if( true ) + a=2; +else + a=3; +return a; +"""); + StopNode stop = parser.parse(true); + assertEquals("return 2;", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testIfIf() { + Parser parser = new Parser( +""" +int a=1; +if( arg!=1 ) + a=2; +else + a=3; +int b=4; +if( a==2 ) + b=42; +else + b=5; +return b;""", TypeInteger.BOT); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Region32,42,5);", stop.toString()); + } + + @Test + public void testIfArgIf() { + Parser parser = new Parser( +""" +int a=1; +if( 1==1 ) + a=2; +else + a=3; +int b=4; +if( arg==2 ) + b=a; +else + b=5; +return b;""", TypeInteger.BOT); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Region28,2,5);", stop.toString()); + } + + @Test + public void testMerge3With2() { + 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.constant(2)); + StopNode stop = parser.parse(); + assertEquals("return 5;", stop.toString()); + } + + @Test + public void testMerge3With1() { + 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; +""", TypeInteger.constant(1)); + StopNode stop = parser.parse(true); + assertEquals("return 3;", stop.toString()); + } + + @Test + public void testMerge3Peephole() { + Parser parser = new Parser( +""" +int a=1; +if( arg==1 ) + if( 1==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +""", TypeInteger.BOT); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Region36,3,Phi(Region34,4,5));", stop.toString()); + } + + @Test + public void testMerge3Peephole1() { + Parser parser = new Parser( +""" +int a=1; +if( arg==1 ) + if( 1==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +""", TypeInteger.constant(1)); + StopNode stop = parser.parse(true); + assertEquals("return 3;", stop.toString()); + } + + @Test + public void testMerge3Peephole3() { + Parser parser = new Parser( +""" +int a=1; +if( arg==1 ) + if( 1==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +""", TypeInteger.constant(3)); + StopNode stop = parser.parse(true); + assertEquals("return 4;", stop.toString()); + } + + @Test + public void testDemo1NonConst() { + Parser parser = new Parser(""" +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; +"""); + StopNode ret = parser.parse(true); + assertEquals("return Phi(Region22,4,1);", ret.toString()); + } + + + @Test + public void testDemo1True() { + Parser parser = new Parser(""" +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; +""", TypeInteger.constant(1)); + StopNode ret = parser.parse(true); + assertEquals("return 4;", ret.toString()); + } + + @Test + public void testDemo1False() { + Parser parser = new Parser(""" +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; +""", TypeInteger.constant(0)); + StopNode ret = parser.parse(true); + assertEquals("return 1;", ret.toString()); + } + + @Test + public void testDemo2NonConst() { + Parser parser = new Parser(""" +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; +"""); + StopNode ret = parser.parse(true); + assertEquals("return (Phi(Region33,Phi(Region22,2,3),0)+Phi(Region,3,1));", ret.toString()); + } + + + @Test + public void testDemo2True() { + Parser parser = new Parser(""" +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; +""", TypeInteger.constant(1)); + StopNode ret = parser.parse(true); + assertEquals("return 6;", ret.toString()); + } + + @Test + public void testDemo2arg2() { + Parser parser = new Parser(""" +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; +""", TypeInteger.constant(2)); + StopNode ret = parser.parse(true); + assertEquals("return 5;", ret.toString()); + } + +} diff --git a/chapter08/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/chapter08/src/test/java/com/seaofnodes/simple/Chapter07Test.java new file mode 100644 index 00000000..696839d9 --- /dev/null +++ b/chapter08/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -0,0 +1,240 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter07Test { + + @Test + public void testExample() { + Parser parser = new Parser( + """ + while(arg < 10) { + arg = arg + 1; + #showGraph; + } + return arg; + """); + Node._disablePeephole = true; + StopNode stop = parser.parse(true); + assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + Node._disablePeephole = false; + } + + @Test + public void testRegression() { + Parser parser = new Parser( +""" +int a = 1; +if(arg){}else{ + while(a < 10) { + a = a + 1; + } +} +return a; +"""); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Region22,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString()); + } + + @Test + public void testWhileNested() { + Parser parser = new Parser( +""" +int sum = 0; +int i = 0; +while(i < arg) { + i = i + 1; + int j = 0; + while( j < arg ) { + sum = sum + j; + j = j + 1; + } +} +return sum; +"""); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Loop8,0,Phi(Loop20,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); + System.out.println(IRPrinter.prettyPrint(stop,99)); + } + + @Test + public void testWhileScope() { + Parser parser = new Parser( +""" +int a = 1; +int b = 2; +while(a < 10) { + if (a == 2) a = 3; + else b = 4; +} +return b; +"""); + Node._disablePeephole = true; + StopNode stop = parser.parse(true); + assertEquals("return Phi(Loop8,2,Phi(Region26,Phi_b,4));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + Node._disablePeephole = false; + System.out.println(IRPrinter.prettyPrint(stop,99)); + } + + @Test + public void testWhileNestedIfAndInc() { + Parser parser = new Parser( +""" +int a = 1; +int b = 2; +while(a < 10) { + if (a == 2) a = 3; + else b = 4; + b = b + 1; + a = a + 1; +} +return b; +"""); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Loop8,2,(Phi(Region26,Phi_b,4)+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + System.out.println(IRPrinter.prettyPrint(stop,99)); + } + + + @Test + public void testWhile() { + Parser parser = new Parser( +""" +int a = 1; +while(a < 10) { + a = a + 1; + a = a + 2; +} +return a; +"""); + Node._disablePeephole = true; + StopNode stop = parser.parse(true); + assertEquals("return Phi(Loop7,1,((Phi_a+1)+2));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + Node._disablePeephole = false; + } + + @Test + public void testWhilePeep() { + Parser parser = new Parser( +""" +int a = 1; +while(a < 10) { + a = a + 1; + a = a + 2; +} +return a; +"""); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Loop7,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testWhile2() { + Parser parser = new Parser( +""" +int a = 1; +while(arg) a = 2; +return a; +"""); + Node._disablePeephole = true; + StopNode stop = parser.parse(true); + assertEquals("return Phi(Loop7,1,2);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + Node._disablePeephole = false; + System.out.println(IRPrinter.prettyPrint(stop,99)); + } + + @Test + public void testWhile2Peep() { + Parser parser = new Parser( +""" +int a = 1; +while(arg) a = 2; +return a; +"""); + StopNode stop = parser.parse(false); + assertEquals("return Phi(Loop7,1,2);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + System.out.println(IRPrinter.prettyPrint(stop, 99)); + } + + @Test + public void testWhile3() { + Parser parser = new Parser( +""" +int a = 1; +while(a < 10) { + int b = a + 1; + a = b + 2; +} +return a; +"""); + Node._disablePeephole = true; + StopNode stop = parser.parse(true); + assertEquals("return Phi(Loop7,1,((Phi_a+1)+2));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + Node._disablePeephole = false; + } + + @Test + public void testWhile3Peep() { + Parser parser = new Parser( +""" +int a = 1; +while(a < 10) { + int b = a + 1; + a = b + 2; +} +return a; +"""); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Loop7,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testWhile4() { + Parser parser = new Parser( +""" +int a = 1; +int b = 2; +while(a < 10) { + int b = a + 1; + a = b + 2; +} +return a; +"""); + Node._disablePeephole = true; + StopNode stop = parser.parse(true); + assertEquals("return Phi(Loop8,1,((Phi_a+1)+2));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + Node._disablePeephole = false; + } + + @Test + public void testWhile4Peep() { + Parser parser = new Parser( +""" +int a = 1; +int b = 2; +while(a < 10) { + int b = a + 1; + a = b + 2; +} +return a; +"""); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + +} diff --git a/chapter08/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/chapter08/src/test/java/com/seaofnodes/simple/Chapter08Test.java index f8bbfaa3..d7f9f521 100644 --- a/chapter08/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/chapter08/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -20,7 +20,7 @@ public class Chapter08Test { } @Test - public void testChapter8Ex6() { + public void testEx6() { Parser parser = new Parser( """ while(arg < 10) { @@ -41,7 +41,7 @@ return arg; @Test - public void testChapter8Ex5() { + public void testEx5() { Parser parser = new Parser( """ int a = 1; @@ -63,7 +63,7 @@ return a; @Test - public void testChapter8Ex4() { + public void testEx4() { Parser parser = new Parser( """ while(arg < 10) { @@ -81,7 +81,7 @@ return arg; } @Test - public void testChapter8Ex3() { + public void testEx3() { Parser parser = new Parser( """ while(arg < 10) { @@ -98,7 +98,7 @@ return arg; @Test - public void testChapter8Ex2() { + public void testEx2() { Parser parser = new Parser( """ while(arg < 10) { @@ -117,7 +117,7 @@ return arg; @Test - public void testChapter8Ex1() { + public void testEx1() { Parser parser = new Parser( """ while(arg < 10) { @@ -133,7 +133,7 @@ return arg; } @Test - public void testChapter8Regress1() { + public void testRegress1() { Parser parser = new Parser( """ while( arg < 10 ) { @@ -149,14 +149,14 @@ return arg; } @Test - public void testChapter8Regress2() { + public void testRegress2() { Parser parser = new Parser("if(1) return 0; else while(arg>--arg) arg=arg+1; return 0;"); StopNode stop = parser.parse(true); assertEquals("Stop[ return 0; return 0; ]", stop.toString()); } @Test - public void testChapter8BreakOutsideLoop() { + public void testBreakOutsideLoop() { try { new Parser(""" if(arg <= 10) { @@ -172,7 +172,7 @@ return arg; } @Test - public void testChapter8Regress3() { + public void testRegress3() { Parser parser = new Parser(""" while(arg < 10) { break; @@ -184,7 +184,7 @@ return arg; } @Test - public void testChapter8Regress4() { + public void testRegress4() { Parser parser = new Parser(""" int a = 1; while(arg < 10) { @@ -202,7 +202,7 @@ return a; } @Test - public void testChapter8Regress5() { + public void testRegress5() { Parser parser = new Parser(""" int a = 1; while(1) { @@ -217,1030 +217,4 @@ return a; assertTrue(stop.ret().ctrl() instanceof RegionNode); } - @Test - public void testChapter7Example() { - Parser parser = new Parser( - """ - while(arg < 10) { - arg = arg + 1; - #showGraph; - } - return arg; - """); - Node._disablePeephole = true; - StopNode stop = parser.parse(true); - assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); - Node._disablePeephole = false; - } - - @Test - public void testChapter7Regression() { - Parser parser = new Parser( - -""" -int a = 1; -if(arg){}else{ - while(a < 10) { - a = a + 1; - } -} -return a; -"""); - StopNode stop = parser.parse(true); - assertEquals("return Phi(Region22,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString()); - } - - @Test - public void testChapter7WhileNested() { - Parser parser = new Parser( - -""" -int sum = 0; -int i = 0; -while(i < arg) { - i = i + 1; - int j = 0; - while( j < arg ) { - sum = sum + j; - j = j + 1; - } -} -return sum; -"""); - StopNode stop = parser.parse(true); - assertEquals("return Phi(Loop8,0,Phi(Loop20,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); - System.out.println(IRPrinter.prettyPrint(stop,99)); - } - - @Test - public void testChapter7WhileScope() { - Parser parser = new Parser( -""" -int a = 1; -int b = 2; -while(a < 10) { - if (a == 2) a = 3; - else b = 4; -} -return b; -"""); - Node._disablePeephole = true; - StopNode stop = parser.parse(true); - assertEquals("return Phi(Loop8,2,Phi(Region26,Phi_b,4));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); - Node._disablePeephole = false; - System.out.println(IRPrinter.prettyPrint(stop,99)); - } - - @Test - public void testChapter7WhileNestedIfAndInc() { - Parser parser = new Parser( -""" -int a = 1; -int b = 2; -while(a < 10) { - if (a == 2) a = 3; - else b = 4; - b = b + 1; - a = a + 1; -} -return b; -"""); - StopNode stop = parser.parse(true); - assertEquals("return Phi(Loop8,2,(Phi(Region26,Phi_b,4)+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); - System.out.println(IRPrinter.prettyPrint(stop,99)); - } - - - @Test - public void testChapter7While() { - Parser parser = new Parser( -""" -int a = 1; -while(a < 10) { - a = a + 1; - a = a + 2; -} -return a; -"""); - Node._disablePeephole = true; - StopNode stop = parser.parse(true); - assertEquals("return Phi(Loop7,1,((Phi_a+1)+2));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); - Node._disablePeephole = false; - } - - @Test - public void testChapter7WhilePeep() { - Parser parser = new Parser( -""" -int a = 1; -while(a < 10) { - a = a + 1; - a = a + 2; -} -return a; -"""); - StopNode stop = parser.parse(true); - assertEquals("return Phi(Loop7,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); - } - - @Test - public void testChapter7While2() { - Parser parser = new Parser( -""" -int a = 1; -while(arg) a = 2; -return a; -"""); - Node._disablePeephole = true; - StopNode stop = parser.parse(true); - assertEquals("return Phi(Loop7,1,2);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); - Node._disablePeephole = false; - System.out.println(IRPrinter.prettyPrint(stop,99)); - } - - @Test - public void testChapter7While2Peep() { - Parser parser = new Parser( -""" -int a = 1; -while(arg) a = 2; -return a; -"""); - StopNode stop = parser.parse(false); - assertEquals("return Phi(Loop7,1,2);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); - System.out.println(IRPrinter.prettyPrint(stop, 99)); - } - - @Test - public void testChapter7While3() { - Parser parser = new Parser( -""" -int a = 1; -while(a < 10) { - int b = a + 1; - a = b + 2; -} -return a; -"""); - Node._disablePeephole = true; - StopNode stop = parser.parse(true); - assertEquals("return Phi(Loop7,1,((Phi_a+1)+2));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); - Node._disablePeephole = false; - } - - @Test - public void testChapter7While3Peep() { - Parser parser = new Parser( -""" -int a = 1; -while(a < 10) { - int b = a + 1; - a = b + 2; -} -return a; -"""); - StopNode stop = parser.parse(true); - assertEquals("return Phi(Loop7,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); - } - - @Test - public void testChapter7While4() { - Parser parser = new Parser( -""" -int a = 1; -int b = 2; -while(a < 10) { - int b = a + 1; - a = b + 2; -} -return a; -"""); - Node._disablePeephole = true; - StopNode stop = parser.parse(true); - assertEquals("return Phi(Loop8,1,((Phi_a+1)+2));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); - Node._disablePeephole = false; - } - - @Test - public void testChapter7While4Peep() { - Parser parser = new Parser( -""" -int a = 1; -int b = 2; -while(a < 10) { - int b = a + 1; - a = b + 2; -} -return a; -"""); - StopNode stop = parser.parse(true); - assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); - } - - @Test - public void testChapter6PeepholeReturn() { - Parser parser = new Parser( -""" -if( true ) return 2; -return 1; -"""); - StopNode stop = parser.parse(true); - assertEquals("return 2;", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); - } - - @Test - public void testChapter6PeepholeRotate() { - Parser parser = new Parser( -""" -int a = 1; -if (arg) - a = 2; -return (arg < a) < 3; -"""); - StopNode stop = parser.parse(false); - assertEquals("return ((arg<Phi(Region12,2,1))<3);", stop.toString()); - } - - @Test - public void testChapter6PeepholeCFG() { - Parser parser = new Parser( -""" -int a=1; -if( true ) - a=2; -else - a=3; -return a; -"""); - StopNode stop = parser.parse(true); - assertEquals("return 2;", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); - } - - @Test - public void testChapter6IfIf() { - Parser parser = new Parser( -""" -int a=1; -if( arg!=1 ) - a=2; -else - a=3; -int b=4; -if( a==2 ) - b=42; -else - b=5; -return b;""", TypeInteger.BOT); - StopNode stop = parser.parse(true); - assertEquals("return Phi(Region32,42,5);", stop.toString()); - } - - @Test - public void testChapter6IfArgIf() { - Parser parser = new Parser( -""" -int a=1; -if( 1==1 ) - a=2; -else - a=3; -int b=4; -if( arg==2 ) - b=a; -else - b=5; -return b;""", TypeInteger.BOT); - StopNode stop = parser.parse(true); - assertEquals("return Phi(Region28,2,5);", stop.toString()); - } - - @Test - public void testChapter6Merge3With2() { - 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.constant(2)); - StopNode stop = parser.parse(); - assertEquals("return 5;", stop.toString()); - } - - @Test - public void testChapter6Merge3With1() { - 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; -""", TypeInteger.constant(1)); - StopNode stop = parser.parse(true); - assertEquals("return 3;", stop.toString()); - } - - @Test - public void testChapter6Merge3Peephole() { - Parser parser = new Parser( -""" -int a=1; -if( arg==1 ) - if( 1==2 ) - a=2; - else - a=3; -else if( arg==3 ) - a=4; -else - a=5; -return a; -""", TypeInteger.BOT); - StopNode stop = parser.parse(true); - assertEquals("return Phi(Region36,3,Phi(Region34,4,5));", stop.toString()); - } - - @Test - public void testChapter6Merge3Peephole1() { - Parser parser = new Parser( -""" -int a=1; -if( arg==1 ) - if( 1==2 ) - a=2; - else - a=3; -else if( arg==3 ) - a=4; -else - a=5; -return a; -""", TypeInteger.constant(1)); - StopNode stop = parser.parse(true); - assertEquals("return 3;", stop.toString()); - } - - @Test - public void testChapter6Merge3Peephole3() { - Parser parser = new Parser( -""" -int a=1; -if( arg==1 ) - if( 1==2 ) - a=2; - else - a=3; -else if( arg==3 ) - a=4; -else - a=5; -return a; -""", TypeInteger.constant(3)); - StopNode stop = parser.parse(true); - assertEquals("return 4;", stop.toString()); - } - - @Test - public void testChapter6Demo1NonConst() { - Parser parser = new Parser(""" -int a = 0; -int b = 1; -if( arg ) { - a = 2; - if( arg ) { b = 2; } - else b = 3; -} -return a+b; -"""); - StopNode ret = parser.parse(true); - assertEquals("return Phi(Region22,4,1);", ret.toString()); - } - - - @Test - public void testChapter6Demo1True() { - Parser parser = new Parser(""" -int a = 0; -int b = 1; -if( arg ) { - a = 2; - if( arg ) { b = 2; } - else b = 3; -} -return a+b; -""", TypeInteger.constant(1)); - StopNode ret = parser.parse(true); - assertEquals("return 4;", ret.toString()); - } - - @Test - public void testChapter6Demo1False() { - Parser parser = new Parser(""" -int a = 0; -int b = 1; -if( arg ) { - a = 2; - if( arg ) { b = 2; } - else b = 3; -} -return a+b; -""", TypeInteger.constant(0)); - StopNode ret = parser.parse(true); - assertEquals("return 1;", ret.toString()); - } - - @Test - public void testChapter6Demo2NonConst() { - Parser parser = new Parser(""" -int a = 0; -int b = 1; -int c = 0; -if( arg ) { - a = 1; - if( arg==2 ) { c=2; } else { c=3; } - if( arg ) { b = 2; } - else b = 3; -} -return a+b+c; -"""); - StopNode ret = parser.parse(true); - assertEquals("return (Phi(Region33,Phi(Region22,2,3),0)+Phi(Region,3,1));", ret.toString()); - } - - - @Test - public void testChapter6Demo2True() { - Parser parser = new Parser(""" -int a = 0; -int b = 1; -int c = 0; -if( arg ) { - a = 1; - if( arg==2 ) { c=2; } else { c=3; } - if( arg ) { b = 2; } - else b = 3; -} -return a+b+c; -""", TypeInteger.constant(1)); - StopNode ret = parser.parse(true); - assertEquals("return 6;", ret.toString()); - } - - @Test - public void testChapter6Demo2arg2() { - Parser parser = new Parser(""" -int a = 0; -int b = 1; -int c = 0; -if( arg ) { - a = 1; - if( arg==2 ) { c=2; } else { c=3; } - if( arg ) { b = 2; } - else b = 3; -} -return a+b+c; -""", TypeInteger.constant(2)); - StopNode ret = parser.parse(true); - assertEquals("return 5;", ret.toString()); - } - - - - @Test - public void testChapter5IfStmt() { - Parser parser = new Parser( -""" -int a = 1; -if (arg == 1) - a = arg+2; -else { - a = arg-3; - #showGraph; -} -#showGraph; -return a;"""); - StopNode ret = parser.parse(true); - assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString()); - } - - @Test - public void testChapter5Test() { - Parser parser = new Parser( -""" -int c = 3; -int b = 2; -if (arg == 1) { - b = 3; - c = 4; -} -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); - 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;"""); - 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;"""); - StopNode ret = parser.parse(true); - assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region,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); - 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); - 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;"""); - StopNode ret = parser.parse(true); - assertEquals("return (arg==Phi(Region16,3,2));", ret.toString()); - } - - @Test - public void testChapter5True() { - StopNode stop = new Parser("return true;").parse(); - assertEquals("return 1;",stop.toString()); - } - - @Test - public void testChapter5HalfDef() { - try { - new Parser("if( arg==1 ) int b=2; return b;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Cannot define a new name on one arm of an if",e.getMessage()); - } - } - - @Test - public void testChapter5HalfDef2() { - try { - new Parser("if( arg==1 ) { int b=2; } else { int b=3; } return b;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Undefined name 'b'",e.getMessage()); - } - } - - @Test - public void testChapter5Regress1() { - try { - new Parser("if(arg==2) int a=1; else int b=2; return a;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Cannot define a new name on one arm of an if",e.getMessage()); - } - } - - - @Test - public void testChapter5BadNum() { - try { - new Parser("return 1-;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected an identifier or expression: ;",e.getMessage()); - } - } - - @Test - public void testChapter5Keyword1() { - try { - new Parser("int true=0; return true;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Expected an identifier, found 'true'",e.getMessage()); - } - } - - @Test - public void testChapter5Keyword2() { - try { - new Parser("int else=arg; if(else) else=2; else else=1; return else;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Expected an identifier, found 'else'",e.getMessage()); - } - } - - @Test - public void testChapter5Keyword3() { - try { - new Parser("int a=1; ififif(arg)inta=2;return a;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected =: (",e.getMessage()); - } - } - - @Test - public void testChapter4Peephole() { - Parser parser = new Parser("return 1+arg+2; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return (arg+3);", ret.print()); - } - - @Test - public void testChapter4Peephole2() { - Parser parser = new Parser("return (1+arg)+2;"); - StopNode ret = parser.parse(); - assertEquals("return (arg+3);", ret.print()); - } - - @Test - public void testChapter4Add0() { - Parser parser = new Parser("return 0+arg;"); - StopNode ret = parser.parse(); - assertEquals("return arg;", ret.print()); - } - - @Test - public void testChapter4AddAddMul() { - Parser parser = new Parser("return arg+0+arg;"); - StopNode ret = parser.parse(); - assertEquals("return (arg*2);", ret.print()); - } - - @Test - public void testChapter4Peephole3() { - Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return ((arg*2)+6);", ret.print()); - } - - @Test - public void testChapter4Mul1() { - Parser parser = new Parser("return 1*arg;"); - StopNode ret = parser.parse(); - assertEquals("return arg;", ret.print()); - } - - @Test - public void testChapter4VarArg() { - Parser parser = new Parser("return arg; #showGraph;"); - StopNode stop = parser.parse(); - ReturnNode ret = stop.ret(); - assertTrue(ret.in(0) instanceof ProjNode); - assertTrue(ret.in(1) instanceof ProjNode); - } - - @Test - public void testChapter4ConstantArg() { - Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2)); - StopNode ret = parser.parse(); - assertEquals("return 2;", ret.print()); - } - - @Test - public void testChapter4CompEq() { - Parser parser = new Parser("return 3==3; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return 1;", ret.print()); - } - - @Test - public void testChapter4CompEq2() { - Parser parser = new Parser("return 3==4; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return 0;", ret.print()); - } - - @Test - public void testChapter4CompNEq() { - Parser parser = new Parser("return 3!=3; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return 0;", ret.print()); - } - - @Test - public void testChapter4CompNEq2() { - Parser parser = new Parser("return 3!=4; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return 1;", ret.print()); - } - - @Test - public void testChapter4Bug1() { - Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return (arg+3);", ret.print()); - } - - @Test - public void testChapter4Bug2() { - Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return (arg+1);", ret.print()); - } - - @Test - public void testChapter4Bug3() { - try { - new Parser("inta=1; return a;").parse(); - fail(); - } catch( RuntimeException e ) { - 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() { - Parser parser = new Parser("int a=1; return a;"); - StopNode ret = parser.parse(); - assertEquals("return 1;", ret.print()); - } - - @Test - public void testVarAdd() { - Parser parser = new Parser("int a=1; int b=2; return a+b;"); - StopNode ret = parser.parse(); - assertEquals("return 3;", ret.print()); - } - - @Test - public void testVarScope() { - Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); - StopNode ret = parser.parse(); - assertEquals("return 4;", ret.print()); - } - - @Test - public void testVarScopeNoPeephole() { - Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;"); - Node._disablePeephole = true; - StopNode ret = parser.parse(); - Node._disablePeephole = false; - assertEquals("return (1+3);", ret.print()); - } - - @Test - public void testVarDist() { - Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;"); - StopNode ret = parser.parse(); - assertEquals("return 8;", ret.print()); - } - - @Test - public void testSelfAssign() { - try { - new Parser("int a=a; return a;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Undefined name 'a'",e.getMessage()); - } - } - - @Test - public void testChapter2ParseGrammar() { - Parser parser = new Parser("return 1+2*3+-5;"); - Node._disablePeephole = true; // disable peephole so we can observe full graph - StopNode ret = parser.parse(); - assertEquals("return (1+((2*3)+(-5)));", ret.print()); - GraphVisualizer gv = new GraphVisualizer(); - System.out.println(gv.generateDotOutput(parser)); - Node._disablePeephole = false; - } - - @Test - public void testChapter2AddPeephole() { - Parser parser = new Parser("return 1+2;"); - StopNode ret = parser.parse(); - assertEquals("return 3;", ret.print()); - } - - @Test - public void testChapter2SubPeephole() { - Parser parser = new Parser("return 1-2;"); - StopNode ret = parser.parse(); - assertEquals("return -1;", ret.print()); - } - - @Test - public void testChapter2MulPeephole() { - Parser parser = new Parser("return 2*3;"); - StopNode ret = parser.parse(); - assertEquals("return 6;", ret.print()); - } - - @Test - public void testChapter2DivPeephole() { - Parser parser = new Parser("return 6/3;"); - StopNode ret = parser.parse(); - assertEquals("return 2;", ret.print()); - } - - @Test - public void testChapter2MinusPeephole() { - Parser parser = new Parser("return 6/-3;"); - StopNode ret = parser.parse(); - assertEquals("return -2;", ret.print()); - } - - @Test - public void testChapter2Example() { - Parser parser = new Parser("return 1+2*3+-5;"); - StopNode ret = parser.parse(); - assertEquals("return 2;", ret.print()); - GraphVisualizer gv = new GraphVisualizer(); - System.out.println(gv.generateDotOutput(parser)); - } - - @Test - public void testSimpleProgram() { - Parser parser = new Parser("return 1;"); - StopNode stop = parser.parse(); - StartNode start = Parser.START; - ReturnNode ret = (ReturnNode)stop.in(0); - - assertTrue(ret.ctrl() instanceof ProjNode); - Node expr = ret.expr(); - if( expr instanceof ConstantNode con ) { - assertEquals(start,con.in(0)); - assertEquals(TypeInteger.constant(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 && con._type instanceof TypeInteger ) - assertEquals(TypeInteger.constant(0),con._type); - } - - @Test - public void testBad1() { - try { - new Parser("ret").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected =: ",e.getMessage()); - } - } - - @Test - public void testBad2() { - try { - new Parser("return 0123;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); - } - } - - @Test - public void testNotBad3() { - // this test used to fail in chapter 1 - assertEquals("return 12;", new Parser("return --12;").parse().print()); - } - - @Test - public void testBad4() { - try { - new Parser("return 100").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected ;: ",e.getMessage()); - } - } - - @Test - public void testNotBad5() { - // this test used to fail in chapter 1 - assertEquals("return -100;", new Parser("return -100;").parse().print()); - } - - @Test - public void testBad6() { - try { - new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); - fail(); - } catch( RuntimeException e ) { - 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()); - } - } - } diff --git a/chapter08/src/test/java/com/seaofnodes/simple/Fuzzer08Test.java b/chapter08/src/test/java/com/seaofnodes/simple/FuzzerWrap.java index ee635c22..82a6a472 100644 --- a/chapter08/src/test/java/com/seaofnodes/simple/Fuzzer08Test.java +++ b/chapter08/src/test/java/com/seaofnodes/simple/FuzzerWrap.java @@ -10,9 +10,9 @@ import static org.junit.Assert.assertTrue; /** * To use the fuzzer run the <code>fuzzPeeps</code> methods. * This can be done from IntelliJ Gui or remove the `@Ignore` annotation and start the test case from the command line - * via <code>mvn clean test -Dtest=com.seaofnodes.simple.Fuzzer08Test#fuzzPeeps</code> + * via <code>mvn clean test -Dtest=com.seaofnodes.simple.FuzzerWrap#fuzzPeeps</code> */ -public class Fuzzer08Test { +public class FuzzerWrap { @Test @Ignore diff --git a/chapter09/README.md b/chapter09/README.md index c6846bed..b8ff8af1 100644 --- a/chapter09/README.md +++ b/chapter09/README.md @@ -1,4 +1,4 @@ -# Chapter 9 +# Chapter 9: Global Value Numbering and Iterative Peepholes In this chapter: diff --git a/chapter09/docs/Makefile b/chapter09/docs/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/chapter09/docs/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/chapter09/docs/build-graphs.sh b/chapter09/docs/build-graphs.sh deleted file mode 100644 index dbd22623..00000000 --- a/chapter09/docs/build-graphs.sh +++ /dev/null @@ -1,6 +0,0 @@ -dot -Tsvg 09-graph1.gv > 09-graph1.svg -dot -Tsvg 09-graph2.gv > 09-graph2.svg -dot -Tsvg 09-graph3.gv > 09-graph3.svg -dot -Tsvg 09-graph4.gv > 09-graph4.svg -dot -Tsvg 09-graph5.gv > 09-graph5.svg -dot -Tsvg 09-graph6.gv > 09-graph6.svg diff --git a/chapter09/src/main/java/com/seaofnodes/simple/Parser.java b/chapter09/src/main/java/com/seaofnodes/simple/Parser.java index b3aeeb22..c4ce71eb 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter09/src/main/java/com/seaofnodes/simple/Parser.java @@ -615,6 +615,7 @@ public class Parser { String getAnyNextToken() { if (isEOF()) return ""; if (isIdStart(peek())) return parseId(); + if (isNumber(peek())) return parseNumberString(); if (isPunctuation(peek())) return parsePunctuation(); return String.valueOf(peek()); } @@ -623,13 +624,16 @@ public class Parser { boolean isNumber(char ch) {return Character.isDigit(ch);} private Type parseNumber() { - int start = _position; - while (isNumber(nextChar())) ; - String snum = new String(_input, start, --_position - start); + String snum = parseNumberString(); if (snum.length() > 1 && snum.charAt(0) == '0') throw error("Syntax error: integer values cannot start with '0'"); return TypeInteger.constant(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) { diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 5abfc4cf..13b42f96 100644 --- a/chapter09/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -2,9 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; @@ -37,6 +35,15 @@ public class Chapter01Test { assertEquals(TypeInteger.constant(0),con._type); } + @Test + public void testBad1() { + try { + new Parser("ret").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected =: ",e.getMessage()); + } + } @Test public void testBad2() { @@ -47,4 +54,47 @@ public class Chapter01Test { assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); } } + + @Test + public void testNotBad3() { + // this test used to fail in chapter 1 + assertEquals("return 12;", new Parser("return --12;").parse().print()); + } + + @Test + public void testBad4() { + try { + new Parser("return 100").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected ;: ",e.getMessage()); + } + } + + @Test + public void testNotBad5() { + // this test used to fail in chapter 1 + assertEquals("return -100;", new Parser("return -100;").parse().print()); + } + + @Test + public void testBad6() { + try { + new Parser("return100").parse(); + fail(); + } catch( RuntimeException e ) { + 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()); + } + } + } diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter02Test.java index 3dd22e39..2deba460 100644 --- a/chapter09/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -2,9 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; @@ -65,35 +63,4 @@ public class Chapter02Test { System.out.println(gv.generateDotOutput(parser)); } - @Test - public void testBad1() { - try { - new Parser("ret").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected =: ",e.getMessage()); - } - } - @Test - public void testNotBad3() { - // this test used to fail in chapter 1 - assertEquals("return 12;", new Parser("return --12;").parse().print()); - } - - @Test - public void testBad4() { - try { - new Parser("return 100").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected ;: ",e.getMessage()); - } - } - - @Test - public void testNotBad5() { - // this test used to fail in chapter 1 - assertEquals("return -100;", new Parser("return -100;").parse().print()); - } - } diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 6bcfcc4b..407fbe48 100644 --- a/chapter09/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -2,9 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; @@ -58,7 +56,7 @@ public class Chapter03Test { } @Test - public void testBad6() { + public void testBad1() { try { new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); fail(); diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter04Test.java index 5a024e77..cde23324 100644 --- a/chapter09/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -2,9 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 24ae80b8..c82914a1 100644 --- a/chapter09/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -2,9 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; @@ -203,7 +201,7 @@ return a;"""); } @Test - public void testKeyword3() { + public void testKeyword3() { try { new Parser("int a=1; ififif(arg)inta=2;return a;").parse(); fail(); @@ -212,14 +210,4 @@ return a;"""); } } - @Test - public void testBad7() { - try { - new Parser("return 1;}").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, unexpected }",e.getMessage()); - } - } - } diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter06Test.java index 5fece2e2..e5961223 100644 --- a/chapter09/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -2,9 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter07Test.java index d42af6c3..2c378623 100644 --- a/chapter09/src/test/java/com/seaofnodes/simple/Chapter07Test.java +++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -2,15 +2,12 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; public class Chapter07Test { - @Test public void testExample() { Parser parser = new Parser( @@ -31,7 +28,6 @@ public class Chapter07Test { @Test public void testRegression() { Parser parser = new Parser( - """ int a = 1; if(arg){}else{ @@ -48,7 +44,6 @@ return a; @Test public void testWhileNested() { Parser parser = new Parser( - """ int sum = 0; int i = 0; @@ -241,4 +236,5 @@ return a; assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } + } diff --git a/chapter09/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/chapter09/src/test/java/com/seaofnodes/simple/FuzzerWrap.java index efd76481..bb3bec1c 100644 --- a/chapter09/src/test/java/com/seaofnodes/simple/FuzzerWrap.java +++ b/chapter09/src/test/java/com/seaofnodes/simple/FuzzerWrap.java @@ -10,11 +10,12 @@ import static org.junit.Assert.assertTrue; /** * To use the fuzzer run the <code>fuzzPeeps</code> methods. * This can be done from IntelliJ Gui or remove the `@Ignore` annotation and start the test case from the command line - * via <code>mvn clean test -Dtest=com.seaofnodes.simple.Fuzzer08Test#fuzzPeeps</code> + * via <code>mvn clean test -Dtest=com.seaofnodes.simple.FuzzerWrap#fuzzPeeps</code> */ public class FuzzerWrap { @Test + @Ignore public void fuzzPeeps() { var fuzzer = new Fuzzer(); for (int i=0; i<1000000; i++) diff --git a/chapter10/README.md b/chapter10/README.md index bd46a70e..62c4844b 100644 --- a/chapter10/README.md +++ b/chapter10/README.md @@ -1,4 +1,4 @@ -# Chapter 10 +# Chapter 10: Structs and Memory In this chapter: diff --git a/chapter10/docs/Makefile b/chapter10/docs/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/chapter10/docs/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/chapter10/docs/build-graphs.sh b/chapter10/docs/build-graphs.sh deleted file mode 100644 index 67dd302f..00000000 --- a/chapter10/docs/build-graphs.sh +++ /dev/null @@ -1,5 +0,0 @@ -dot -Tsvg example1.gv > example1.svg -dot -Tsvg example2a.gv > example2a.svg -dot -Tsvg example2b.gv > example2b.svg -dot -Tsvg example2c.gv > example2c.svg -dot -Tsvg lattice.gv > lattice.svg diff --git a/chapter10/src/main/java/com/seaofnodes/simple/Parser.java b/chapter10/src/main/java/com/seaofnodes/simple/Parser.java index def37bae..9a1b4465 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/Parser.java @@ -785,6 +785,7 @@ public class Parser { String getAnyNextToken() { if (isEOF()) return ""; if (isIdStart(peek())) return parseId(); + if (isNumber(peek())) return parseNumberString(); if (isPunctuation(peek())) return parsePunctuation(); return String.valueOf(peek()); } @@ -793,13 +794,16 @@ public class Parser { boolean isNumber(char ch) {return Character.isDigit(ch);} private Type parseNumber() { - int start = _position; - while (isNumber(nextChar())) ; - String snum = new String(_input, start, --_position - start); + String snum = parseNumberString(); if (snum.length() > 1 && snum.charAt(0) == '0') throw error("Syntax error: integer values cannot start with '0'"); return TypeInteger.constant(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) { diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 5abfc4cf..89882b2f 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -2,9 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; @@ -37,6 +35,15 @@ public class Chapter01Test { assertEquals(TypeInteger.constant(0),con._type); } + @Test + public void testBad1() { + try { + new Parser("ret").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'ret'",e.getMessage()); + } + } @Test public void testBad2() { @@ -47,4 +54,47 @@ public class Chapter01Test { assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); } } + + @Test + public void testNotBad3() { + // this test used to fail in chapter 1 + assertEquals("return 12;", new Parser("return --12;").parse().print()); + } + + @Test + public void testBad4() { + try { + new Parser("return 100").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected ;: ",e.getMessage()); + } + } + + @Test + public void testNotBad5() { + // this test used to fail in chapter 1 + assertEquals("return -100;", new Parser("return -100;").parse().print()); + } + + @Test + public void testBad6() { + try { + new Parser("return100").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'return100'",e.getMessage()); + } + } + + @Test + public void testBad7() { + try { + new Parser("return 1;}").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, unexpected }",e.getMessage()); + } + } + } diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter02Test.java index 107225ae..2deba460 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -2,9 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; @@ -65,35 +63,4 @@ public class Chapter02Test { System.out.println(gv.generateDotOutput(parser)); } - @Test - public void testBad1() { - try { - new Parser("ret").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Undefined name 'ret'",e.getMessage()); - } - } - @Test - public void testNotBad3() { - // this test used to fail in chapter 1 - assertEquals("return 12;", new Parser("return --12;").parse().print()); - } - - @Test - public void testBad4() { - try { - new Parser("return 100").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected ;: ",e.getMessage()); - } - } - - @Test - public void testNotBad5() { - // this test used to fail in chapter 1 - assertEquals("return -100;", new Parser("return -100;").parse().print()); - } - } diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 6bcfcc4b..407fbe48 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -2,9 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; @@ -58,7 +56,7 @@ public class Chapter03Test { } @Test - public void testBad6() { + public void testBad1() { try { new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); fail(); diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter04Test.java index 5a024e77..cde23324 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -2,9 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter05Test.java index e82aa7da..44fff0c0 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -2,9 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; @@ -203,7 +201,7 @@ return a;"""); } @Test - public void testKeyword3() { + public void testKeyword3() { try { new Parser("int a=1; ififif(arg)inta=2;return a;").parse(); fail(); @@ -212,14 +210,4 @@ return a;"""); } } - @Test - public void testBad7() { - try { - new Parser("return 1;}").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, unexpected }",e.getMessage()); - } - } - } diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter06Test.java index 6c24992c..d30bd43d 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -2,9 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter07Test.java index 29d16f32..a5cddb68 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/Chapter07Test.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -2,15 +2,12 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; public class Chapter07Test { - @Test public void testExample() { Parser parser = new Parser( @@ -47,7 +44,6 @@ return a; @Test public void testWhileNested() { Parser parser = new Parser( - """ int sum = 0; int i = 0; @@ -240,4 +236,5 @@ return a; assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } + } diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java index f7388ff9..2e1ae1aa 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -3,7 +3,6 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StopNode; import com.seaofnodes.simple.type.*; -import org.junit.Assert; import org.junit.Test; import java.util.Arrays; diff --git a/chapter10/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/chapter10/src/test/java/com/seaofnodes/simple/FuzzerWrap.java index 699711fc..bb3bec1c 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/FuzzerWrap.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/FuzzerWrap.java @@ -10,12 +10,12 @@ import static org.junit.Assert.assertTrue; /** * To use the fuzzer run the <code>fuzzPeeps</code> methods. * This can be done from IntelliJ Gui or remove the `@Ignore` annotation and start the test case from the command line - * via <code>mvn clean test -Dtest=com.seaofnodes.simple.Fuzzer08Test#fuzzPeeps</code> + * via <code>mvn clean test -Dtest=com.seaofnodes.simple.FuzzerWrap#fuzzPeeps</code> */ public class FuzzerWrap { - @Ignore @Test + @Ignore public void fuzzPeeps() { var fuzzer = new Fuzzer(); for (int i=0; i<1000000; i++) |