diff options
25 files changed, 773 insertions, 187 deletions
@@ -55,7 +55,7 @@ The Simple language is styled after a subset of C or Java. analysis. One memory value in SSA. Loads, stores, and an executable evaluator. * [Chapter 11](docs/chapter11/README.md): Equivalence class aliasing. Lazy memory partitioning with `MemMerge`, `MemPhi`, and `BulkMemPhi`. -* Chapter 12: Reference fields, forward references and recursive structs. +* [Chapter 12](docs/chapter12/README.md): Reference fields, forward references and recursive structs. * Chapter 13: Global Code Motion - Scheduling. * Chapter 14: Numeric types: floats, narrow integers, ranges and rounding to `f32`. * Chapter 15: One dimensional static length array type, with array loads and stores. diff --git a/chapter11.iml b/chapter12.iml index 92b9e5ca..28f6886a 100644 --- a/chapter11.iml +++ b/chapter12.iml @@ -1,8 +1,8 @@ <?xml version="1.0" encoding="UTF-8"?> <module type="JAVA_MODULE" version="4"> <component name="NewModuleRootManager" inherit-compiler-output="false"> - <output url="file://$MODULE_DIR$/../build/idea/production/chapter11" /> - <output-test url="file://$MODULE_DIR$/../build/idea/test/chapter11" /> + <output url="file://$MODULE_DIR$/../build/idea/production/chapter12" /> + <output-test url="file://$MODULE_DIR$/../build/idea/test/chapter12" /> <exclude-output /> <content url="file://$MODULE_DIR$"> <sourceFolder url="file://$MODULE_DIR$/src/main/java" isTestSource="false" /> diff --git a/docs/chapter12/12-grammar.md b/docs/chapter12/12-grammar.md new file mode 100644 index 00000000..24199ede --- /dev/null +++ b/docs/chapter12/12-grammar.md @@ -0,0 +1,130 @@ +# Grammar for Chapter 12 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | structDeclaration + | declStatement + | blockStatement + | expressionStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatement + ; + +PRIMTYPE + : 'int' + ; + +field + : PRIMTYPE IDENTIFIER ';' + | structName ('?')? IDENTIFIER ';' + ; + +fields + : field+ + ; + +structDeclaration + : 'struct' IDENTIFIER '{' fields '}' + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + + +expressionStatement + : IDENTIFIER '=' expression ';' + | fieldExpression '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +structName + : IDENTIFIER + ; + +declStatement + : PRIMTYPE IDENTIFIER '=' expression ';' + | structName ('?')? IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | '!' unaryExpression + | primaryExpression + ; + +newExpression + : 'new' IDENTIFIER + ; + +fieldExpression + : primaryExpression '.' IDENTIFIER + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | 'true' + | 'false' + | 'null' + | newExpression + | '(' expression ')' + | fieldExpression + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DEC_DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/docs/chapter12/Makefile b/docs/chapter12/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter12/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/docs/chapter12/README.md b/docs/chapter12/README.md new file mode 100644 index 00000000..00071885 --- /dev/null +++ b/docs/chapter12/README.md @@ -0,0 +1,148 @@ +# Chapter 12: References + +[Previous: Chapter 11](../chapter11/README.md) | +[Next: Chapter 13](../chapter13/README.md) + +Chapters 10 and 11 gave structs integer fields and represented their memory +effects in SSA. This chapter lets fields contain references to other structs, +including structs whose definitions have not yet appeared. Linked lists and +mutually referring objects become possible without changing the memory graph. + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter12) +in the linear Git history and [compare it with Chapter 11](https://github.com/SeaOfNodes/Simple/compare/linear-chapter11...linear-chapter12). + +## Typed fields and forward references + +```java +struct Person { + int age; + FamilyTree? tree; +} +struct FamilyTree { + Person? father; + Person? mother; +} +``` + +The parser's `TYPES` table maps names to types. It initially contains `int` +(and any other primitive types, more are showing up in later chapters). When +`type()` recognizes a declaration using an unknown name, it installs a +name-only `TypeStruct`, with `_fields == null` - this a struct where we only +know the struct name, and no other information. A pointer to that struct is +enough to describe a reference field,`?` allows the pointer to be null. + +`parseStruct()` collects all fields before installing the complete struct in +`TYPES`. It replaces the table entry; it does not mutate the old type or +publish successive prefixes of the field list. Field aliases are allocated +with the completed declaration, as before. + +See [the parser](../../src/main/java/com/seaofnodes/simple/Parser.java), particularly +`type()`, `parseField()`, and `parseStruct()`, and the +[grammar](12-grammar.md). + +## Recursive structs: `L0` and `L1` + +```java +struct LLI { LLI? next; int i; } +``` + +Two descriptions are useful for remembering what the compiler actually builds: + +```text +L0 = TypeStruct("LLI", fields = null) +L1 = TypeStruct("LLI", fields = { next: pointer-to-L0?, i: int }) +TYPES["LLI"] = L1 +``` + +`L0` is created when parsing the `LLI? next` field. After the closing brace, +`L1` replaces it in the name table. The `next` field inside `L1` still points +to `L0`; it is not patched to point back to `L1`. + +The design is **immutable shallow references, resolved by name when needed**. +The runtime objects may form a cycle; their compiler type descriptions remain +finite and acyclic. This is an intentional decision to **stop recursive type +expansion**. Recursively substituting the completed definition into every +reference would either expand forever or require cyclic type interning, +equality, hashing, and lattice operations (which indeed show up in a lattice +chapter). + +[`TypeStruct`](../../src/main/java/com/seaofnodes/simple/type/TypeStruct.java) +instead stops at the name-only description. Its `dual()` and `glb()` leave that +description alone. Meeting a complete description with a name-only description +of the same struct yields the name-only description. That loses field detail +without losing the struct's identity. There is no pass trying to expand `L0` +into an ever deeper sequence of `L1`, `L2`, and so on. + +## Resolving a shallow reference + +When parsing `head.next`, `parsePostfix()` takes the pointer's struct name and +looks up the current declaration in `TYPES`. It gets the field layout and alias +from that declaration, even if the pointer's own type still contains `L0`. +Doing the lookup again for the next field access is sufficient for a chain +such as `head.next.next.i`. + +For a local declaration or assignment, `parseExpressionStatement()` also +resolves a name-only pointer before checking assignment compatibility. This +"deepening" changes the temporary type used for the check; it does not rewrite +the expression node's type or replace all old references in the graph. + +```java +struct LLI { LLI? next; int i; } +LLI? head = null; +while (arg) { + LLI x = new LLI; + x.next = head; + x.i = arg; + head = x; + arg = arg - 1; +} +if (!head) return 0; +LLI? next = head.next; +if (next == null) return 1; +return next.i; +``` + +The null checks refine the pointer on the surviving control path. In +particular, the false path of an `if` must record its refinement even when +there is no explicit `else`. Resolving a name supplies the field definition; +it does not prove that the pointer is non-null. + +## Initialization and incomplete definitions + +`newStruct()` initializes each field using its type's `makeInit()`: zero for +integers and null for references. Loads and Stores use the same aliases and +memory optimizations as Chapter 11. A Load from an initializing Store can +therefore fold to null. + +An unused forward reference need not ever be defined: + +```java +struct Holder { Missing? ref; } +Holder h = new Holder; +return h.ref; // null; no definition of Missing is needed +``` + +There is no way here to construct a non-null `Missing` without its complete +definition: `new Missing` is rejected. Accessing one of its fields also needs +a definition, as well as a non-null pointer. Simply mentioning a nullable +reference type does not impose a requirement to define it before the end of +the program. + +There is one temporary initialization allowance in this chapter: + +```java +struct N { N next; int i; } +N n = new N; +return n.next; // null, despite the non-null field declaration +``` + +The initializing Store may write null even into a non-null reference field. +An ordinary `n.next = null` is rejected. Chapter 16 adds constructors and +checks initialization; this chapter keeps the distinction explicit in +[`StoreNode`](../../src/main/java/com/seaofnodes/simple/node/StoreNode.java). + +The [reference tests](../../src/test/java/com/seaofnodes/simple/Chapter12Test.java) +exercise linked lists, mutual references, null checks, and incomplete types. +Run them with `make tests`; `make view` displays the same unscheduled graph. +Chapter 13 now has the memory and reference semantics it needs to introduce +global code motion, including load/store anti-dependencies. diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index df8d0b1c..a25edeb1 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -82,14 +82,15 @@ public class Parser { ScopeNode _continueScope; ScopeNode _breakScope; - // Mapping from a Struct name to a Struct. - public static Map<String, TypeStruct> OBJS = new HashMap<>(); + // Authoritative declarations, indexed by type name. + public static HashMap<String, Type> TYPES = new HashMap<>(); public Parser(String source, TypeInteger arg) { PARSER = this; Node.reset(); IterPeeps.reset(); - OBJS.clear(); + TYPES.clear(); + TYPES.put("int",TypeInteger.BOT); _lexer = new Lexer(source); _scope = new ScopeNode(); _continueScope = _breakScope = null; @@ -121,6 +122,8 @@ public class Parser { _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new ProjNode(START, 2, ScopeNode.ARG0).peephole()); _scope.define("$mem", TypeMem.BOT, new ProjNode(START, 1, "$mem").peephole()); parseBlock(); + if( ctrl()._type==Type.CONTROL ) + STOP.addReturn(new ReturnNode(ctrl(), new ConstantNode(TypeInteger.constant(0)).peephole(), _scope).peephole()); _scope.pop(); _xScopes.pop(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); @@ -158,7 +161,6 @@ public class Parser { private Node parseStatement() { if( false ) return null; else if (matchx("return") ) return parseReturn(); - else if (matchx("int") ) return parseDecl(TypeInteger.BOT); else if (match ("{") ) return require(parseBlock(),"}"); else if (matchx("if") ) return parseIf(); else if (matchx("while") ) return parseWhile(); @@ -174,40 +176,42 @@ public class Parser { /** * Parse a struct field. * <pre> - * int IDENTIFIER ; + * type IDENTIFIER ; * </pre> */ - private Field parseField(String sname) { - if( matchx("int") ) // Currently only parsing "int" type fields - return require(Field.make(requireId().intern(),TypeInteger.BOT),";"); - throw errorSyntax("A field type is expected, only type 'int' is supported at present"); + private Field parseField() { + Type t = type(); + if( t==null ) + throw errorSyntax("Requires a field type, found '"+_lexer.getAnyNextToken()+"'"); + return require(Field.make(requireId().intern(),t),";"); } /** - * Parse a struct declaration, and return the following statement. + * Parse a complete struct declaration. * Only allowed in top level scope. * Structs cannot be redefined. * - * @return The statement following the struct + * @return null */ private Node parseStruct() { if (_xScopes.size() > 1) throw errorSyntax("struct declarations can only appear in top level scope"); String typeName = requireId(); - if ( OBJS.containsKey(typeName)) throw errorSyntax("struct '" + typeName + "' cannot be redefined"); + Type t = TYPES.get(typeName); + if( t!=null && !(t instanceof TypeStruct ts && ts._fields==null) ) throw errorSyntax("struct '" + typeName + "' cannot be redefined"); ArrayList<Field> fields = new ArrayList<>(); require("{"); while (!peek('}') && !_lexer.isEOF()) { - Field field = parseField(typeName); + Field field = parseField(); if (fields.contains(field)) throw errorSyntax("Field '" + field + "' already defined in struct '" + typeName + "'"); fields.add(field); } require("}"); // Build and install the TypeStruct TypeStruct ts = TypeStruct.make(typeName, fields); + TYPES.put(typeName, ts); // Insert the struct name in the collection of all struct names _aliases.put(typeName,_alias); _alias += ts._fields.length; - OBJS.put(typeName, ts); // Insert the struct name in the collection of all struct names - return parseStatement(); + return null; } /** @@ -349,8 +353,8 @@ public class Parser { // Parse the false side _scope = fScope; // Restore scope, then parse else block if any ifF.unkeep(); // fScope already owns the false control + _scope.upcast(ifF,pred,true); // Up-cast predicate, also without an else if (matchx("else")) { - _scope.upcast(ifF,pred,true); // Up-cast predicate parseStatement(); fScope = _scope; } @@ -418,15 +422,18 @@ public class Parser { if( _scope.define(name,t,expr) == null ) throw error("Redefining name '" + name + "'"); } else { - Node n = _scope.lookup(name); - t = _scope.lookupDeclaredType(name); - if( n==null ) + if( _scope.lookup(name)==null ) throw error("Undefined name '" + name + "'"); - _scope.update(name,expr); + t = _scope.lookupDeclaredType(name); } - if( !expr._type.isa(t) ) - throw error("Type " + expr._type.str() + " is not of declared type " + t.str()); - return expr; + // Auto-deepen forward ref types + Type e = expr._type; + if( e instanceof TypeMemPtr tmp && tmp._obj._fields==null ) + e = tmp.make_from((TypeStruct)TYPES.get(tmp._obj._name)); + // Type is sane + if( !e.isa(t) ) + throw error("Type " + e.str() + " is not of declared type " + t.str()); + return _scope.update(name,expr); } // Parse a type-or-null @@ -434,38 +441,22 @@ public class Parser { int old = _lexer._position; String tname = _lexer.matchId(); if( tname==null ) return null; - if( tname.equals("int") ) return TypeInteger.BOT; - TypeStruct obj = OBJS.get(tname); - if( obj != null ) - return TypeMemPtr.make(obj,match("?")); - // Not a type; unwind the parse - _lexer._position = old; - return null; - } - - /** - * Parses a declStatement - * - * <pre> - * type name = expression ';' - * </pre> - * @return an expression {@link Node} - */ - private Node parseDecl(Type t) { - var name = requireId(); - var expr = match(";") - // Assign a null value - ? new ConstantNode(t.makeInit()).peephole() - // Assign "= expr;" - : require(require("=").parseExpression(), ";"); - if( !expr._type.isa(t) ) - throw error("Type " + expr._type.str() + " is not of declared type " + t.str()); - if( _scope.define(name,t,expr) == null ) - throw error("Redefining name '" + name + "'"); - return expr; + boolean nullable = match("?"); + Type t = TYPES.get(tname); + // Assume a forward-reference type + if( t == null ) { + int old2 = _lexer._position; + String id = _lexer.matchId(); + if( id==null ) { + _lexer._position = old; + return null; + } + TYPES.put(tname,t = TypeStruct.make(tname)); + _lexer._position = old2; // Reparse ID in caller + } + return t instanceof TypeStruct obj ? TypeMemPtr.make(obj,nullable) : t; } - /** * Parse an expression of the form: * @@ -571,15 +562,16 @@ public class Parser { * @return a primary {@link Node}, never {@code null} */ private Node parsePrimary() { - if( _lexer.isNumber() ) return parseIntegerLiteral(); + if( _lexer.isNumber(_lexer.peek()) ) return parseIntegerLiteral(); if( match("(") ) return require(parseExpression(), ")"); if( matchx("true" ) ) return new ConstantNode(TypeInteger.constant(1)).peephole(); - if( matchx("false") ) return new ConstantNode(TypeInteger.constant(0)).peephole(); + if( matchx("false") ) return new ConstantNode(TypeInteger.ZERO).peephole(); if( matchx("null" ) ) return new ConstantNode(TypeMemPtr.NULLPTR).peephole(); if( matchx("new") ) { String structName = requireId(); - TypeStruct obj = OBJS.get(structName); - if( obj == null) throw errorSyntax("Unknown struct type '" + structName + "'"); + Type t = TYPES.get(structName); + if( !(t instanceof TypeStruct obj) || obj._fields==null ) + throw error("Unknown struct type '" + structName + "'"); return newStruct(obj); } String name = _lexer.matchId(); @@ -592,12 +584,11 @@ public class Parser { /** * Return a NewNode but also generate instructions to initialize it. */ - private Node newStruct( TypeStruct obj ) { + private Node newStruct(TypeStruct obj) { Node n = new NewNode(TypeMemPtr.make(obj), ctrl()).peephole().keep(); - Node initValue = new ConstantNode(TypeInteger.constant(0)).peephole(); int alias = _aliases.get(obj._name); for( Field field : obj._fields ) { - store(field._fname,alias,n,initValue); + store(field._fname,alias,field._type,n,new ConstantNode(field._type.makeInit()).peephole(),true); alias++; } return n.unkeep(); @@ -607,9 +598,9 @@ public class Parser { private Node mem() { return _scope.lookup("$mem"); } private Node mem(Node n) { return _scope.update("$mem",n); } - private void store(String name, int alias, Node ptr, Node val) { + private void store(String name, int alias, Type glb, Node ptr, Node val, boolean init) { Node prior = mem().keep(); - Node st = new StoreNode(name,alias,prior,ptr,val).peephole(); + Node st = new StoreNode(name,alias,glb,null,prior,ptr,val,init).peephole(); mem(new MemMergeNode(prior,alias,st).peephole()); if( prior.unkeep().isUnused() ) prior.kill(); } @@ -629,7 +620,10 @@ public class Parser { throw error("Expected struct reference but got " + expr._type.str()); String name = requireId().intern(); - int idx = ptr._obj==null ? -1 : ptr._obj.find(name); + if( expr._type == TypeMemPtr.TOP ) throw error("Accessing field '" + name + "' from null"); + if( ptr._obj == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); + TypeStruct base = (TypeStruct)TYPES.get(ptr._obj._name); + int idx = base==null ? -1 : base.find(name); if( idx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); int alias = _aliases.get(ptr._obj._name)+idx; @@ -638,13 +632,14 @@ public class Parser { if( peek('=') ) _lexer._position--; else { Node val = parseExpression(); - store(name,alias,expr,val); + Type glb = base._fields[idx]._type; + store(name,alias,glb,expr,val,false); return expr; // "obj.a = expr" returns the expression while updating memory } } - Type declaredType = ptr._obj._fields[idx]._type; - return parsePostfix(new LoadNode(name, alias, declaredType, mem(), expr).peephole()); + Type declaredType = base._fields[idx]._type; + return parsePostfix(new LoadNode(name, alias, declaredType.glb(), mem(), expr).peephole()); } /** diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index e235d288..e993a20e 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -168,4 +168,9 @@ public class AddNode extends Node { } @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } + @Override public String err() { + if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; + if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 9bf36459..b2ee6939 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -14,7 +14,6 @@ import com.seaofnodes.simple.type.Field; */ public class LoadNode extends MemOpNode { - Type _declaredType; /** * Load a value from a ptr.field. * @@ -23,12 +22,11 @@ public class LoadNode extends MemOpNode { * @param memPtr The ptr to the struct from where we load a field */ public LoadNode(String name, int alias, Type glb, Node memSlice, Node memPtr) { - super(name, alias, memSlice, memPtr, null); - _declaredType = glb; + super(name, alias, glb, null, memSlice, memPtr); } @Override boolean canDrop(MemOpNode other, Node dep) { - return super.canDrop(other,dep) && _declaredType==((LoadNode)other)._declaredType && !clobbered(dep); + return super.canDrop(other,dep) && !clobbered(dep); } // Check only immediate memory users. Stores clobber memory; Phis and diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 44304bcb..7c6afb0c 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -11,11 +11,14 @@ public abstract class MemOpNode extends Node { public final String _name; public final int _alias; + public final Type _declaredType; - public MemOpNode(String name, int alias, Node memSlice, Node memPtr, Node value) { - super(null, memSlice, memPtr, value); + + public MemOpNode(String name, int alias, Type glb, Node... nodes ) { + super(nodes); _name = name; _alias = alias; + _declaredType = glb; } public Node mem() { return in(1); } @@ -25,7 +28,7 @@ public abstract class MemOpNode extends Node { // The caller has already checked the opcode, input shape and control. boolean canDrop(MemOpNode other, Node dep) { ptr().addDep(dep); - return _alias==other._alias && err()==null; + return _alias==other._alias && _declaredType==other._declaredType && err()==null; } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index 5592c52d..b0359a52 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -51,4 +51,9 @@ public class MulNode extends Node { return null; } @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); } + @Override public String err() { + if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; + if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 1d8e23f8..999e38fd 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -190,6 +190,7 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { */ public void kill( ) { unlock(); + moveDepsToWorklist(); assert isUnused(); // Has no uses, so it is dead _type=null; // Flag as dead while( nIns()>0 ) { // Set all inputs to null, recursively killing unused Nodes diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 026d5c50..e9eaaf2e 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -13,20 +13,26 @@ import com.seaofnodes.simple.type.*; */ public class StoreNode extends MemOpNode { + private final boolean _init; // Initializing writes are allowed to write null + /** * @param name The struct field we are assigning to * @param memSlice The memory alias node - this is updated after a Store * @param memPtr The ptr to the struct where we will store a value * @param value Value to be stored */ - public StoreNode(String name, int alias, Node memSlice, Node memPtr, Node value) { - super(name, alias, memSlice, memPtr, value); + public StoreNode(String name, int alias, Type glb, Node ctrl, Node memSlice, Node memPtr, Node value, boolean init) { + super(name, alias, glb, ctrl, memSlice, memPtr, value); + _init = init; } - @Override - public String label() { return "Store"; } - @Override - public boolean isMem() { return true; } + @Override boolean canDrop(MemOpNode other, Node dep) { + return super.canDrop(other,dep) && _init==((StoreNode)other)._init; + } + + @Override public String label() { return "." +_name+"="; } + @Override public boolean isMem() { return true; } + public Node val() { return in(3); } @Override @@ -53,7 +59,7 @@ public class StoreNode extends MemOpNode { // Must have exactly one use of "this" or you get weird // non-serializable memory effects in the worse case. st.checkNoUseBeyond(this) ) { - assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect + assert _name.equals(st._name); // Equiv class aliasing is perfect setDef(1,st.mem()); return this; } @@ -72,4 +78,11 @@ public class StoreNode extends MemOpNode { return false; } + @Override + String err() { + String err = super.err(); + if( err != null ) return err; + Type ptr = val()._type; + return _init || ptr.isa(_declaredType) ? null : "Cannot store "+ptr+" into field "+_declaredType+" "+_name; + } } diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index feb9e90f..5c852f94 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 11's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 12's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture<Node> { private Parser _parser; private Node _ret; diff --git a/src/main/java/com/seaofnodes/simple/type/Field.java b/src/main/java/com/seaofnodes/simple/type/Field.java index cdc58215..b2c006dd 100644 --- a/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/src/main/java/com/seaofnodes/simple/type/Field.java @@ -20,6 +20,7 @@ public class Field extends Type { _fname = fname; _type = type; } + // Make with existing alias public static Field make( String fname, Type type ) { return new Field(fname,type).intern(); } @@ -46,13 +47,13 @@ public class Field extends Type { boolean eq(Type t) { Field f = (Field)t; - return Utils.eq(_fname,f._fname) && _type==f._type; + return _fname.equals(f._fname) && _type==f._type; } @Override public StringBuilder print( StringBuilder sb ) { - return _type.print(sb.append(_fname).append(":")); + return _type.print(sb.append(_fname).append(" :")); } @Override public String str() { return _fname; } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/src/main/java/com/seaofnodes/simple/type/TypeMem.java index b6fc8824..38b3635a 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -15,7 +15,7 @@ public class TypeMem extends Type { // 0 means TOP, no slice. // -1 means BOT, all memory. // N means slice#N. - private final int _alias; + public final int _alias; private TypeMem(int alias) { super(TMEM); _alias = alias; } @@ -23,7 +23,6 @@ public class TypeMem extends Type { public static final TypeMem TOP = make( 0); public static final TypeMem BOT = make(-1); - public static void gather(ArrayList<Type> ts) { ts.add(make(1)); ts.add(BOT); } @Override @@ -40,7 +39,7 @@ public class TypeMem extends Type { } @Override - public Type glb() { return TypeMem.BOT; } + public Type glb() { return make(_alias); } @Override int hash() { return 9876543 + _alias; } @@ -62,5 +61,5 @@ public class TypeMem extends Type { }); } - @Override public String str() { return print(new StringBuilder()).toString(); } + @Override public String str() { return toString(); } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 6c874a93..5caa816d 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -13,21 +13,27 @@ import java.util.ArrayList; */ public class TypeMemPtr extends Type { // A TypeMemPtr is pair (obj,nil) - // where obj is one of - // (null,TypeStruct). - // where nil is one of - // (true,false) meaning an explicit null is allowed or not + // where obj is a TypeStruct, possibly TypeStruct.BOT + // where nil is an explicit null is allowed or not - public final TypeStruct _obj; // null, a TypeStruct, or sentinel TypeStruct.MANY + // Examples: + // (Person,false) - a not-nil Person + // (Person,true ) - a Person or a nil + // (BOT ,false) - a not-nil void* (unspecified struct) + // (TOP ,true ) - a nil + + public final TypeStruct _obj; public final boolean _nil; private TypeMemPtr(TypeStruct obj, boolean nil) { super(TMEMPTR); + assert obj!=null; _obj = obj; _nil = nil; } public static TypeMemPtr make(TypeStruct obj, boolean nil) { return new TypeMemPtr(obj, nil).intern(); } - public static TypeMemPtr make(TypeStruct obj) { return TypeMemPtr.make(obj, false); } + public static TypeMemPtr make(TypeStruct obj) { return make(obj, false); } + public TypeMemPtr make_from(TypeStruct obj) { return make(obj, _nil); } public static final TypeMemPtr BOT = make(TypeStruct.BOT,true); public static final TypeMemPtr TOP = BOT.dual(); @@ -43,17 +49,14 @@ public class TypeMemPtr extends Type { } @Override - public TypeMemPtr dual() { return TypeMemPtr.make(_obj==null ? null : _obj.dual(), !_nil); } + public TypeMemPtr dual() { return TypeMemPtr.make(_obj.dual(), !_nil); } @Override - public Type glb() { - if( _obj==null ) return BOT; - return make(_obj.glb(),true); - } + public Type glb() { return make(_obj.glb(),true); } @Override public TypeMemPtr makeInit() { return NULLPTR; } @Override - int hash() { return (_obj==null ? 0xDEADBEEF : _obj.hashCode()) ^ (_nil ? 1024 : 0); } + int hash() { return _obj.hashCode() ^ (_nil ? 1024 : 0); } @Override boolean eq(Type t) { diff --git a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 44741def..02de7cc8 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -8,9 +8,12 @@ import java.util.ArrayList; */ public class TypeStruct extends Type { - // For now in terms of the lattice - // a struct type just stays as is - + // Immutable shallow references, resolved by name in Parser.TYPES when needed. + // A name-only struct has _fields == null, even after its definition is known. + // For LLI { LLI? next; int i; }, L0 is name-only and L1.next points to L0; + // TYPES["LLI"] holds L1. We deliberately stop recursive type expansion here, + // keeping interning and lattice operations finite and acyclic. Never patch + // L0 into L1: field access looks up the complete declaration by name instead. public final String _name; public final Field[] _fields; @@ -20,13 +23,23 @@ public class TypeStruct extends Type { _fields = fields; } + // Forward-ref version + public static TypeStruct make(String name) { return new TypeStruct(name, null).intern(); } + // All fields directly listed public static TypeStruct make(String name, Field[] fields) { return new TypeStruct(name, fields).intern(); } + // Parser uses an ArrayList to gather the fields public static TypeStruct make(String name, ArrayList<Field> fields) { return make(name,fields.toArray(new Field[fields.size()])); } public static final TypeStruct TOP = make("$TOP",new Field [0]); public static final TypeStruct BOT = make("$BOT",new Field [0]); public static final TypeStruct TEST = make("test",new Field[]{Field.TEST}); - public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); } + + // A pair of self-cyclic types + private static final TypeStruct S1F = make("S1"); + private static final TypeStruct S2F = make("S2"); + public static final TypeStruct S1 = make("S1", new Field[]{ Field.make("a", TypeInteger.BOT), Field.make("s2",TypeMemPtr.make(S2F,false)) }); + private static final TypeStruct S2 = make("S2", new Field[]{ Field.make("b", TypeInteger.BOT), Field.make("s1",TypeMemPtr.make(S1F,false)) }); + public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); ts.add(S1); ts.add(S2); } public int find(String fname) { for( int i=0; i<_fields.length; i++ ) @@ -51,6 +64,8 @@ public class TypeStruct extends Type { // And the answer is: "don't ask". if( !_name.equals(that._name) ) return BOT; // It's a struct; that's about all we know + if( this._fields==null ) return this; + if( that._fields==null ) return that; // Now all fields should be the same, so just do field meets assert _fields.length == that._fields.length; Field[] flds = new Field[_fields.length]; @@ -63,6 +78,7 @@ public class TypeStruct extends Type { public TypeStruct dual() { if( this==TOP ) return BOT; if( this==BOT ) return TOP; + if( _fields == null ) return this; Field[] flds = new Field[_fields.length]; for( int i=0; i<_fields.length; i++ ) flds[i] = _fields[i].dual(); @@ -80,9 +96,10 @@ public class TypeStruct extends Type { return make(_name,flds); } private boolean _glb() { - for( Field f : _fields ) - if( f.glb() != f ) - return false; + if( _fields!=null ) + for( Field f : _fields ) + if( f.glb() != f ) + return false; return true; } @@ -91,6 +108,7 @@ public class TypeStruct extends Type { TypeStruct ts = (TypeStruct)t; // Invariant if( !_name.equals(ts._name) ) return false; + if( _fields == ts._fields ) return true; if( _fields.length!=ts._fields.length ) return false; for( int i = 0; i < _fields.length; i++ ) @@ -102,7 +120,9 @@ public class TypeStruct extends Type { @Override int hash() { long hash = _name.hashCode(); - for( Field f : _fields ) hash = Utils.rot(hash,13) ^ f.hashCode(); + if( _fields != null ) + for( Field f : _fields ) + hash = Utils.rot(hash,13) ^ f.hashCode(); return Utils.fold(hash); } @@ -110,11 +130,12 @@ public class TypeStruct extends Type { public StringBuilder print(StringBuilder sb) { if( this==BOT ) return sb.append("StructBot"); if( this==TOP ) return sb.append("StructTop"); - sb.append(_name).append(" {\n"); + sb.append(_name); + if( _fields == null ) return sb; // Forward reference struct, just print the name + sb.append(" {\n"); for( Field f : _fields ) { - sb.append(" ").append(f._fname).append(":"); - f._type.print(sb); - sb.append(";\n"); + sb.append(" ").append(f._fname).append(" :"); + f._type.print(sb).append(";\n"); } return sb.append("}"); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java index cf7bd6cf..97cd9940 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -37,7 +37,7 @@ if (arg == 1) { } return c;""", TypeInteger.BOT); StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region17,4,3);", ret.toString()); + assertEquals("return Phi(Region18,4,3);", ret.toString()); } @Test @@ -116,7 +116,7 @@ if( arg==0 ) return arg+a+b; """, TypeInteger.BOT); StopNode stop = parser.parse(); - assertEquals("return ((arg+Phi(Region14,1,0))+Phi(Region29,2,0));", stop.toString()); + assertEquals("return ((arg+Phi(Region16,1,0))+Phi(Region32,2,0));", stop.toString()); } @Test @@ -130,7 +130,7 @@ if( arg==1 ) } return a;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return (arg==Phi(Region17,3,2));", ret.toString()); + assertEquals("return (arg==Phi(Region18,3,2));", ret.toString()); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java index 920e26e3..9af11b68 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -30,7 +30,7 @@ if (arg) return (arg < a) < 3; """); StopNode stop = parser.parse().iterate(); - assertEquals("return ((arg<Phi(Region13,2,1))<3);", stop.toString()); + assertEquals("return ((arg<Phi(Region15,2,1))<3);", stop.toString()); } @Test @@ -200,7 +200,7 @@ if( arg ) { return a+b; """); StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region25,4,1);", ret.toString()); + assertEquals("return Phi(Region27,4,1);", ret.toString()); } @@ -251,7 +251,7 @@ if( arg ) { return a+b+c; """); StopNode ret = parser.parse().iterate(); - assertEquals("return (Phi(Region37,Phi(Region24,2,3),0)+Phi(Region,3,1));", ret.toString()); + assertEquals("return (Phi(Region39,Phi(Region24,2,3),0)+Phi(Region,3,1));", ret.toString()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/src/test/java/com/seaofnodes/simple/Chapter08Test.java index 4fa08bd9..02c3a301 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -24,7 +24,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region37,Phi(Region26,Phi(Loop7,arg,(Phi_arg+1)),Add),Add);", stop.toString()); + assertEquals("return Phi(Region38,Phi(Region26,Phi(Loop7,arg,(Phi_arg+1)),Add),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); Assert.assertEquals(5L, Evaluator.evaluate(stop, 1)); Assert.assertEquals(10L, Evaluator.evaluate(stop, 6)); @@ -47,7 +47,7 @@ while(arg < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop8,1,Phi(Region43,Phi_a,(Phi_a+1)));", stop.toString()); + assertEquals("return Phi(Loop8,1,Phi(Region45,Phi_a,(Phi_a+1)));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -66,7 +66,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region35,Phi(Loop7,arg,(Phi_arg+1)),Add);", stop.toString()); + assertEquals("return Phi(Region36,Phi(Loop7,arg,(Phi_arg+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 1b1920e8..b1fdc459 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -134,14 +134,14 @@ while(v1+arg) { } """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ ]", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test public void testWhile0() { Parser parser = new Parser("while(0) continue; if(0) arg=0;"); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ ]", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test @@ -153,7 +153,7 @@ if(0) while(0) { } """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ ]", stop.toString()); + assertEquals("return 0;", stop.toString()); } @@ -215,7 +215,7 @@ return -0+0+0; public void testFuzz3() { Parser parser = new Parser("int v0=0; while(0==69) while(v0) return 0;"); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ ]", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test @@ -260,7 +260,7 @@ while(0==1) while(v0) v0=1+v0; """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ ]", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 9a5e4677..e5d9b882 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -221,7 +221,7 @@ if( bar ) bar.a = 1; return bar; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region16,null,new Bar);", stop.toString()); + assertEquals("return Phi(Region31,(*void)Phi(Region18,null,new Bar),null);", stop.toString()); } @Test @@ -237,7 +237,7 @@ else bar.a = 1; return rez; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region34,4,3);", stop.toString()); + assertEquals("return Phi(Region37,4,3);", stop.toString()); } @Test @@ -290,8 +290,7 @@ while( i.x < i.len ) { return sum; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop16,0,(Phi(Loop,0,(Phi_$2+1))+Phi_sum));", stop.toString()); - assertEquals(10L,Evaluator.evaluate(stop,5)); + assertEquals("return Phi(Loop17,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); } @@ -311,7 +310,7 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,new s0,Phi(Region34,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop11,new s0,Phi(Region35,new s0,Phi_ret));", stop.toString()); } @Test @@ -328,7 +327,7 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop15,new s0,Phi(Region35,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop15,new s0,Phi(Region36,new s0,Phi_ret));", stop.toString()); } @@ -345,7 +344,7 @@ while(arg < 10) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,new s0,Phi(Region32,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop11,new s0,Phi(Region33,new s0,Phi_ret));", stop.toString()); } @Test @@ -375,7 +374,7 @@ if(0) { } """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ ]", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test @@ -449,7 +448,7 @@ while(0) {} } """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ ]", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/src/test/java/com/seaofnodes/simple/Chapter12Test.java new file mode 100644 index 00000000..0d4f3c97 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -0,0 +1,200 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.StopNode; +import com.seaofnodes.simple.type.TypeStruct; +import com.seaofnodes.simple.type.TypeMemPtr; +import org.junit.Ignore; +import org.junit.Test; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; +import static org.junit.Assert.assertNull; +import static org.junit.Assert.assertSame; + +public class Chapter12Test { + + @Test + public void testLinkedList0() { + Parser parser = new Parser( +""" +struct LLI { LLI? next; int i; } +LLI? head = null; +while( arg ) { + LLI x = new LLI; + x.next = head; + x.i = arg; + head = x; + arg = arg-1; +} +return head.next.i; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Might be null accessing 'next'",e.getMessage()); } + } + + @Test + public void testLinkedList1() { + Parser parser = new Parser( +""" +struct LLI { LLI? next; int i; } +LLI? head = null; +while( arg ) { + LLI x = new LLI; + x.next = head; + x.i = arg; + head = x; + arg = arg-1; +} +if( !head ) return 0; +LLI? next = head.next; +if( next==null ) return 1; +return next.i; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ return 0; return 1; return .i; ]", stop.toString()); + assertEquals(2L, Evaluator.evaluate(stop, 3)); + } + + @Test + public void testCoRecur() { + Parser parser = new Parser( +""" +struct Left { int i; Right? f; } +struct Right { int f; Left? i; } +Left left = new Left; +left.i = 17; +Right right = new Right; +right.f = 314; +left.f = right; +right.i = left; +return right.i.f.i.i; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 17;", stop.toString()); + } + + @Test + public void testNullReright() { + Parser parser = new Parser( +""" +struct N { N next; int i; } +N n = new N; +return n.next; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return null;", stop.toString()); + } + + @Test + public void testNullRef1() { + Parser parser = new Parser( +""" +struct N { N next; int i; } +N n = new N; +n.next = new N; +return n.next; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return new N;", stop.toString()); + } + + @Test + public void testNullRef2() { + Parser parser = new Parser( +""" +struct N { N next; int i; } +N n = new N; +n.next = null; +return n.next; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot store null into field *N next",e.getMessage()); } + } + + + @Test + public void testNullRef4() { + Parser parser = new Parser("-null-5/null-5"); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Expected an identifier, found 'null'",e.getMessage()); } + } + + @Test public void testNullRef5() { + Parser parser = new Parser("return null+42;"); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot 'Add' null",e.getMessage()); } + } + + @Test + public void testEmpty() { + Parser parser = new Parser( +""" +struct S{}; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testForwardReright() { + Parser parser = new Parser( +""" +struct S1 { S2 s; } +return new S2; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Unknown struct type 'S2'",e.getMessage()); } + } + + @Test + public void testForwardRef1() { + Parser parser = new Parser( +""" +struct S1 { S2? s; } +struct S2 { int x; } +return new S1.s=new S2; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return new S1;", stop.toString()); + } + + @Test + public void testcheckNull() { + Parser parser = new Parser( +""" +struct I {int i;} +struct P {I pi;} +P p1 = new P; +P p2 = new P; +p2.pi = new I; +p2.pi.i = 2; +if (arg) p1 = new P; +return p1.pi.i + 1; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Might be null accessing 'i'",e.getMessage()); } + } + + + @Test + public void testShallowRecursiveType() { + new Parser("struct LLI { LLI? next; int i; } return 0;").parse().iterate(); + TypeStruct l1 = (TypeStruct)Parser.TYPES.get("LLI"); + TypeStruct l0 = ((TypeMemPtr)l1._fields[0]._type)._obj; + assertEquals("LLI", l0._name); + assertNull(l0._fields); + assertEquals(2, l1._fields.length); + assertSame(l0, l1.meet(l0)); + assertSame(l0, l0.dual()); + assertSame(l0, l0.glb()); + } + + @Test + public void testUnusedForwardReference() { + StopNode stop = new Parser("struct Holder { Missing? ref; } Holder h = new Holder; return h.ref;") + .parse().iterate(); + assertEquals("return null;", stop.toString()); + assertNull(((TypeStruct)Parser.TYPES.get("Missing"))._fields); + } +} diff --git a/src/test/java/com/seaofnodes/simple/TypeTest.java b/src/test/java/com/seaofnodes/simple/TypeTest.java index f9c580cc..298fc6f8 100644 --- a/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -36,9 +36,9 @@ public class TypeTest { Assert.assertEquals(TypeMem .BOT, m2.meet(m3)); Assert.assertEquals(TypeMem .BOT, m3.meet(m4)); - Assert.assertEquals(TypeMem.BOT, m1.glb()); + Assert.assertEquals(m1, m1.glb()); Assert.assertEquals(m1, m1.dual()); - Assert.assertEquals(TypeMem.TOP, m1.glb().dual()); + Assert.assertEquals(m1, m1.glb().dual()); TypeMemPtr ptr1 = TypeMemPtr.make(s1); Assert.assertEquals(s1, ptr1._obj); diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index 155063ab..14baadba 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -3,9 +3,7 @@ package com.seaofnodes.simple.fuzzer; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.node.ScopeNode; -import java.util.ArrayList; -import java.util.HashSet; -import java.util.Random; +import java.util.*; import java.util.function.Predicate; /** @@ -22,6 +20,7 @@ public class ScriptGenerator { private static final int MAX_NAME_LENGTH = 10; private static final int MAX_BLOCK_DEPTH = 4; private static final int MAX_EXPRESSION_DEPTH = 10; + private static final int MAX_SUFFIX_RECURSIVE_DEPTH = 10; /** * Number of spaces per indentation @@ -68,12 +67,11 @@ public class ScriptGenerator { } private static class TypeStruct extends Type { - record Field (String name, Type type) {} - final Field[] fields; + record Field (String name, Type type, TypeStruct struct) {} + Field[] fields; final TypeNullable nullable = new TypeNullable(this); - TypeStruct(String name, Field[] fields) { + TypeStruct(String name) { super(name); - this.fields = fields; } boolean isa(Type other) { return this == other || other == nullable; } } @@ -144,6 +142,10 @@ public class ScriptGenerator { */ private final ArrayList<TypeStruct> structs = new ArrayList<>(); /** + * All forward declared structs + */ + private final ArrayList<TypeStruct> forwardStructs = new ArrayList<>(); + /** * Allow to declare structs. */ private boolean allowStructs = true; @@ -286,6 +288,7 @@ public class ScriptGenerator { for (var s:structs) { if (s.name.equals(name)) return s; } + for (var s:forwardStructs) if (s.name.equals(name)) return s; return null; } @@ -318,12 +321,18 @@ public class ScriptGenerator { return v; } + private <T> T randFromList(List<T> list) { + return list.get(random.nextInt(list.size())); + } + /** * Get a random structure name * @return A random structure name */ private String getStructName() { - if (!structs.isEmpty() && generateInvalid()) return structs.get(random.nextInt(structs.size())).name; + if (!structs.isEmpty() && generateInvalid()) return randFromList(structs).name; + if (!forwardStructs.isEmpty() && generateInvalid()) return randFromList(forwardStructs).name; + // Generate a new random struct name StringBuilder sb = getRandomName(); var v = sb.toString(); @@ -342,14 +351,26 @@ public class ScriptGenerator { * Get a random type * @return A random type */ - private Type getType() { - if (structs.isEmpty() || random.nextBoolean()) return TYPE_INT; - var idx = random.nextInt(structs.size()); - TypeStruct struct = structs.get(idx); + private Type getType(boolean allowForward) { + int t = random.nextInt(10); + if( t<5 || structs.isEmpty() ) return TYPE_INT; + if (allowForward && random.nextInt(10)==0) { + int i=random.nextInt(forwardStructs.size()+1); + if (i>0) return forwardStructs.get(i-1).nullable; + var name = getStructName(); + var struct = new TypeStruct(name); + forwardStructs.add(struct); + return struct.nullable; + } + TypeStruct struct = randFromList(structs); if (random.nextBoolean()) return struct.nullable; return struct; } + private Type getType() { + return getType(false); + } + /** * Generates a program and writes it into the string builder supplied in the constructor. * @return If the program is allowed to be invalid returns if something potentially invalid was generated. @@ -409,19 +430,29 @@ public class ScriptGenerator { * @return 0 */ public int genStruct() { - var name = getStructName(); + int idx = random.nextInt(forwardStructs.size()+10); + TypeStruct struct; + if (idx < 10) { + var name = getStructName(); + struct = new TypeStruct(name); + forwardStructs.add(struct); + } else { + struct = forwardStructs.get(idx-10); + } var fields = new TypeStruct.Field[generateInvalid() ? 0 : random.nextInt(10)]; - sb.append("struct ").append(name).append(" {\n"); + sb.append("struct ").append(struct.name).append(" {\n"); indentation += INDENTATION; for (int i=0; i<fields.length; i++) { var fieldName = getRandomName(); - var type = generateInvalid() ? getType() : TYPE_INT; + var type = getType(true); printIndentation().append(type.name).append(" ").append(fieldName).append(";\n"); - fields[i] = new TypeStruct.Field(fieldName.toString(), type); + fields[i] = new TypeStruct.Field(fieldName.toString(), type, struct); } indentation -= INDENTATION; printIndentation().append("}"); - structs.add(new TypeStruct(name, fields)); + struct.fields = fields; + forwardStructs.remove(struct); + structs.add(struct); return 0; } @@ -515,7 +546,7 @@ public class ScriptGenerator { */ public int genIf() { sb.append("if("); - genExpression(TYPE_INT); + genExpression(TYPE_INT, true); sb.append(") "); var stop = genStatementBlock(); if ((stop & FLAG_IF_WITHOUT_ELSE) == 0 && random.nextInt(10) > 3) { @@ -561,7 +592,7 @@ public class ScriptGenerator { */ public int genWhile() { sb.append("while("); - genExpression(TYPE_INT); + genExpression(TYPE_INT, true); sb.append(") "); loopDepth++; genStatementBlock(); @@ -587,17 +618,17 @@ public class ScriptGenerator { indentation += INDENTATION; String name = getVarName(); printIndentation().append("int ").append(name).append("="); - genExpression(TYPE_INT); + genExpression(TYPE_INT, true); sb.append(";\n"); addVariable(name, TYPE_INT); printIndentation().append("while(").append(name).append("<"); - genExpression(TYPE_INT); + genExpression(TYPE_INT, true); sb.append(") {\n"); indentation += INDENTATION; depth--; loopDepth++; printIndentation().append(name).append("=").append(name).append("+"); - genExpression(TYPE_INT); + genExpression(TYPE_INT, true); sb.append(";\n"); genStatements(); loopDepth--; @@ -621,7 +652,7 @@ public class ScriptGenerator { sb.append(generateInvalid() ? getRandomName() : type.name).append(" ").append(name); if (!(type instanceof TypeNullable) || random.nextBoolean()) { sb.append("="); - genExpression(type); + genExpression(type, true); } sb.append(";"); addVariable(name, type); @@ -656,7 +687,7 @@ public class ScriptGenerator { declared = field.type; } sb.append("="); - genExpression(declared); + genExpression(declared, true); sb.append(";"); return 0; } @@ -668,7 +699,7 @@ public class ScriptGenerator { public int genReturn() { var type = getType(); sb.append("return "); - genExpression(type); + genExpression(type, true); sb.append(";"); return FLAG_STOP; } @@ -677,70 +708,91 @@ public class ScriptGenerator { * Generate a binary expression. * This method does not care about operator precedence. */ - public void genExpression(Type type) { - if (generateInvalid()) type = getType(); + public void genExpression(Type type, boolean change) { + if (change && generateInvalid()) type = getType(); if (type != TYPE_INT) { - genUnary(type); + genUnary(type, false); return; } var num = randLog(MAX_BINARY_EXPRESSIONS_PER_EXPRESSION); while(num-->0) { - genUnary(TYPE_INT); + genUnary(type, false); sb.append(BINARY_OP[random.nextInt(BINARY_OP.length)]); } - genUnary(TYPE_INT); + genUnary(type, false); } /** * Generate a unary expression. */ - public void genUnary(Type type) { - if (generateInvalid()) type = getType(); + public void genUnary(Type type, boolean change) { + if (change && generateInvalid()) type = getType(); if (type != TYPE_INT) { - genSuffix(type); + genSuffix(type, false); return; } var num = randLog(MAX_UNARY_EXPRESSIONS_PER_EXPRESSION); while(num-->0) { sb.append(UNARY_OP[random.nextInt(UNARY_OP.length)]); } - genSuffix(TYPE_INT); + genSuffix(type, false); + } + + public TypeStruct.Field getField(Type type) { + int n=0; + for (var s: structs) { + for (var f: s.fields) { + if (f.type.isa(type)) n++; + } + } + if (n==0) return null; + n = random.nextInt(n); + for (var s: structs) { + for (var f: s.fields) { + if (f.type.isa(type)) if (n--==0) return f; + } + } + throw new AssertionError(); } /** * Generate */ - public void genSuffix(Type type) { - if (generateInvalid()) type = getType(); - if (type == TYPE_INT && random.nextBoolean()) { - var t = getType(); + public void genSuffix(Type type, boolean change) { + genSuffixRecursive(type, change, MAX_SUFFIX_RECURSIVE_DEPTH); + } + + public void genSuffixRecursive(Type type, boolean change, int depth) { + if (change && generateInvalid()) type = getType(); + if (depth > 0 && random.nextBoolean()) { if (generateInvalid()) { var field = getRandomName(); - genPrimary(t); + var t = getType(); + genSuffixRecursive(t, true, depth-1); sb.append(".").append(field); return; - } else if (t instanceof TypeStruct s && s.fields.length > 0) { - var field = s.fields[random.nextInt(s.fields.length)]; - if (field.type == TYPE_INT) { - genPrimary(t); + } else { + var field = getField(type); + if (field != null) { + genSuffixRecursive(field.struct, true, depth-1); sb.append(".").append(field.name); return; } } } - genPrimary(type); + genPrimary(type, false); } /** * Generate a primary expression. */ - public void genPrimary(Type type) { - if (generateInvalid()) type = getType(); + public void genPrimary(Type type, boolean change) { + if (change && generateInvalid()) type = getType(); var rand = random.nextInt(10); if (rand == 0 && exprDepth != 0) { sb.append("("); exprDepth--; - genExpression(type); + genExpression(type, false); exprDepth++; sb.append(")"); } else if (rand < 6) { @@ -762,8 +814,9 @@ public class ScriptGenerator { case 1 -> sb.append("false"); default -> sb.append(random.nextInt(1<<(rand-2))); } + } else if (type instanceof TypeNullable n) { - if (random.nextBoolean()) { + if ((n.base instanceof TypeStruct s && s.fields == null) || random.nextBoolean()) { sb.append("null"); } else { sb.append("new ").append(generateInvalid() ? getRandomName() : n.base.name); |