summaryrefslogtreecommitdiff
path: root/chapter14
diff options
context:
space:
mode:
authorCliff Click <cliffc@acm.org>2026-10-03 14:03:48 -0700
committerCliff Click <cliffc@acm.org>2026-10-03 14:03:48 -0700
commit22df891893d30e9906d0b14fc3ae5d8e67d500b2 (patch)
tree2bda142f92febc8b26f1cabd4bb0c46d1864f34b /chapter14
parentc3958e34c0de21df52e57e47e4f47ffe6464f138 (diff)
downloadSimple-22df891893d30e9906d0b14fc3ae5d8e67d500b2.tar.gz
Simple-22df891893d30e9906d0b14fc3ae5d8e67d500b2.zip
Chapter renumber, and split ch 17
Renumber chapters 10a, 10b, 11, 12, 13, 14 -> 10, 11, 13, 12, [11,14]. Split ch 17 into a 17a and 17b; shuffle around im/mutable syntax to be consistent, and present it more slowly. THe new immutable syntax is pushed through all later chapters
Diffstat (limited to 'chapter14')
-rw-r--r--chapter14/README.md106
-rw-r--r--chapter14/chapter14.iml28
-rw-r--r--chapter14/src/main/java/com/seaofnodes/simple/type/TypeStruct.java14
-rw-r--r--chapter14/src/test/java/com/seaofnodes/simple/Chapter10bTest.java64
-rw-r--r--chapter14/src/test/java/com/seaofnodes/simple/Chapter11Test.java578
-rw-r--r--chapter14/src/test/java/com/seaofnodes/simple/Chapter12Test.java219
-rw-r--r--chapter14/src/test/java/com/seaofnodes/simple/Chapter13Test.java553
-rw-r--r--chapter14/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java95
8 files changed, 886 insertions, 771 deletions
diff --git a/chapter14/README.md b/chapter14/README.md
index 50009f4a..84207f52 100644
--- a/chapter14/README.md
+++ b/chapter14/README.md
@@ -1,27 +1,79 @@
-# Chapter 14: Narrow types
+# Chapter 14: Numeric Types
[Previous: Chapter 13](../chapter13/README.md) |
[Next: Chapter 15](../chapter15/README.md)
# Table of Contents
-1. [Narrow Word Types](#narrow-or-sub-word-types)
-2. [Overflow handling](#overflow-handling)
-3. [Integer ranges](#integer-ranges)
-4. [Bitwise operations](#bitwise-operations)
-5. [Precedence](#precedence)
-6. [Type lattice](#type-implementation)
-7. [Nodes](#nodes)
+1. [Floating-point arithmetic](#floating-point-arithmetic)
+2. [Narrow Word Types](#narrow-or-sub-word-types)
+3. [Overflow handling](#overflow-handling)
+4. [Integer ranges](#integer-ranges)
+5. [Bitwise operations](#bitwise-operations)
+6. [Precedence](#precedence)
+7. [Type lattice](#type-implementation)
+8. [Nodes](#nodes)
-In this chapter, we add sub-word integer types.
+With structs, reference fields, and scheduling in place, this chapter extends
+the numeric values they carry. We add floating-point arithmetic, narrow
+integer and float types, and integer ranges.
You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter14) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter13...linear-chapter14) it to the previous chapter.
-## Narrow or sub-word types
+## Floating-point arithmetic
+
+Floating point values start with the `flt` type and compute IEEE754 64-bit arithmetic.
+Integer expressions auto-widen to floats when involved in a float expression.
+
+```java
+flt f = 0.5;
+int x = 2;
+f = f+x; // Auto-widen x to 2.0, result is 2.5
+f = f+true; // Since bools are just synonyms for integers 0,1 they auto-widen also
+```
-Narrow or sub-word integer types refer to integer data types that occupy less memory (fewer bits) than the standard or "full-width" (typically 32 or 64 bits) integer types provided by a system or programming language.
+There is no corresponding way right now to round a `flt` back to an `int`:
+```java
+int x = 3.14; // error
+```
+
+Here is Newton's method for computing a square root:
+```java
+flt guess = arg; // Initial guess is just argument
+while( true ) {
+ // Next guess from Newton's method
+ flt next = (arg/guess + guess)/2;
+ // Break if hit fixed point
+ if( next == guess ) break;
+ guess = next;
+}
+return guess;
+```
+When run with argument 2, produces 1.414213562373095.
+Floating point operations have their own Nodes:
+
+| Node | Op |
+|------------------------|----------------------|
+| AddF, SubF, MulF, DivF | Basic binary FP ops |
+| MinusF | Unary negate |
+| EQF, LTF, LEF | FP compare operators |
+
+The parser uses [`Node.widen()`](src/main/java/com/seaofnodes/simple/node/Node.java)
+to choose the floating-point operation and insert `ToFloatNode` conversions.
+The float lattice has constants between `TOP` and `BOT`, like the integer
+lattice before ranges. [`TypeFloat`](src/main/java/com/seaofnodes/simple/type/TypeFloat.java)
+also records whether a value fits `f32`; assigning to `f32` rounds it to that
+precision. Conversion from float back to integer remains a separate, pending
+language feature.
+
+
+## Narrow or sub-word types
+
+Narrow or sub-word integer types refer to integer data types that occupy less
+memory (fewer bits) than the standard or "full-width" (typically 32 or 64 bits)
+integer types provided by a system or programming language.
As a prelude to arrays, especially arrays of bytes common in all networking
codes, Simple needs some way to manipulate sub-word integer types.
@@ -209,11 +261,11 @@ This is the same as regular additions:
public long value() { assert isConstant(); return _min; }
```
-#### Truncate(2)
+#### More Truncate
```java
u8 a = arg; // arg & 255
-u8 b = arg; // arg & 255(same as a)
+u8 b = arg; // arg & 255 (same as a)
u8 c = a + b; // (arg&255)*2, type = TypeInteger.BOT
return c; // (((arg&255)*2)&255), type = TypeInteger.U8
```
@@ -224,9 +276,9 @@ on the expression to keep it in the valid boundaries.
## Integer ranges
-Link hacker's delight here.
-For range math, visit:[^1]
+For general range math, visit Hackers Delight:[^1]
+
## Bitwise operations
We support the following bitwise operators:
And `&`, Or `|`, Xor `^`, Shift left `<<`, Shift right `>>`, Shift right zero `>>>`
@@ -242,6 +294,8 @@ And `&`, Or `|`, Xor `^`, Shift left `<<`, Shift right `>>`, Shift right zero `>
Note `>>>` is a logical shift and not an arithmetic shift.
+Here is a sample of peephole opts on these logical operations:
+
#### AndNode:
##### lhs & -1 = lhs;
@@ -305,7 +359,7 @@ arg + 123 & 3 = (arg + 123) & 3
## Type Implementation
-The ![Integer](../chapter10a/docs/type-integer.svg) `TypeInteger` class is
+The ![Integer](../chapter10/docs/type-integer.svg) `TypeInteger` class is
reworked to support a full range of min/max values. At this time, only some
power-of-2 sized ranges are exposed to the programmer but the optimizer
internally supports all ranges. The MEET operation takes the min-of-mins and
@@ -321,17 +375,18 @@ Example: the `i8` type has the range `[-128...127]`.
Example: the `dual` of `bool` is `[1...0]` (just swap min and max).
-The ![Float](../docs/type-float.svg) `TypeFloat` class is also reworked to support 32-bit and 64-bit sizes.
+The ![Float](../docs/type-float.svg) `TypeFloat` class introduced here supports
+both 32-bit and 64-bit sizes.
The integer range diagram is schematic: it shows the boolean range and its
-dual as examples among the possible ranges. The other domains retain the
+dual as examples among the possible ranges. The other domains retain the
named structs, nullable pointers, and precise memory aliases from earlier chapters.
![Graph1](./docs/lattice.svg)
### meet:
-Meet of two ranges:
+The Meet of two ranges:
```java
@Override
public Type xmeet(Type other) {
@@ -340,17 +395,14 @@ TypeInteger i = (TypeInteger)other; // Contract
return make(Math.min(_min,i._min), Math.max(_max,i._max));
}
```
-Combine all values that could possibly occur within either range.
-## Nodes
-
-Added this Chapter are some bit-manipulation Nodes representing common hardware
-ops to mask, shift, sign-extend and round bits. The truncation and extension
-logic uses these. They are otherwise very similar to the previous
-`Add/Sub/Mul/Div` Nodes but with slightly different constant math and
-slightly different `idealize()` calls.
+This combines all values that could possibly occur within either range.
+Also, the implementation is trivial.
[^1]: Hacker's delight.
4-2 Propagating Bounds through Adds and Subtracts
+
+The next chapter uses these numeric types for array lengths, indexing, and
+element storage, including byte arrays.
diff --git a/chapter14/chapter14.iml b/chapter14/chapter14.iml
new file mode 100644
index 00000000..4c719b6d
--- /dev/null
+++ b/chapter14/chapter14.iml
@@ -0,0 +1,28 @@
+<?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/chapter14" />
+ <output-test url="file://$MODULE_DIR$/../build/idea/test/chapter14" />
+ <exclude-output />
+ <content url="file://$MODULE_DIR$">
+ <sourceFolder url="file://$MODULE_DIR$/src/main/java" isTestSource="false" />
+ <sourceFolder url="file://$MODULE_DIR$/src/test/java" isTestSource="true" />
+ <excludeFolder url="file://$MODULE_DIR$/build" />
+ <excludeFolder url="file://$MODULE_DIR$/target" />
+ </content>
+ <orderEntry type="inheritedJdk" />
+ <orderEntry type="sourceFolder" forTests="false" />
+ <orderEntry type="module" module-name="graph" />
+ <orderEntry type="module" module-name="print" />
+ <orderEntry type="module-library" scope="TEST">
+ <library name="JUnit4">
+ <CLASSES>
+ <root url="jar://$MODULE_DIR$/lib/junit-4.12.jar!/" />
+ <root url="jar://$MODULE_DIR$/lib/hamcrest-core-1.3.jar!/" />
+ </CLASSES>
+ <JAVADOC />
+ <SOURCES />
+ </library>
+ </orderEntry>
+ </component>
+</module>
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter14/src/main/java/com/seaofnodes/simple/type/TypeStruct.java
index 2599a383..8ad59a39 100644
--- a/chapter14/src/main/java/com/seaofnodes/simple/type/TypeStruct.java
+++ b/chapter14/src/main/java/com/seaofnodes/simple/type/TypeStruct.java
@@ -8,14 +8,12 @@ import java.util.ArrayList;
*/
public class TypeStruct extends Type {
- // A Struct has a name and a set of fields; the fields themselves have
- // names and types. Briefly during parsing its allowed to have a
- // forward-ref to a Struct; in this case the _fields array is null.
- // Its illegal to attempt to load a field from a forward-ref struct.
- //
- // During the normal optimization run, struct types "bottom out" at further
- // struct references, so we don't have to handle e.g. cyclic types. The
- // "bottom out" is again the forward-ref struct.
+ // 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;
diff --git a/chapter14/src/test/java/com/seaofnodes/simple/Chapter10bTest.java b/chapter14/src/test/java/com/seaofnodes/simple/Chapter10bTest.java
deleted file mode 100644
index 6f094cfb..00000000
--- a/chapter14/src/test/java/com/seaofnodes/simple/Chapter10bTest.java
+++ /dev/null
@@ -1,64 +0,0 @@
-package com.seaofnodes.simple;
-
-import com.seaofnodes.simple.node.*;
-import com.seaofnodes.simple.evaluator.Evaluator;
-import org.junit.Test;
-import static org.junit.Assert.*;
-
-public class Chapter10bTest {
- @Test public void testIndependentField() {
- var stop = new Parser("""
- struct S { int x; int y; }
- S s = new S;
- s.x = 42;
- while (arg > 0) { s.y = s.y + arg; arg = arg - 1; }
- return s.x;
- """).parse().iterate();
- assertEquals("return 42;",stop.toString());
- assertEquals(42L,Evaluator.evaluate(stop,5));
- assertNull(stop.walk(n -> n instanceof LoadNode ? n : null));
- }
-
- @Test public void testParallelMemoryPhis() {
- var stop = new Parser("""
- struct S { int x; int y; int z; }
- S a = new S; S b = new S;
- S p = a; if (arg) p = b;
- while (arg > 0) {
- a.x = p.x + arg;
- a.y = p.y + 2;
- a.z = p.z + 3;
- arg = arg - 1;
- }
- return a;
- """).parse().iterate();
- int[] phis = {0};
- stop.walk(n -> {
- if (n instanceof MemPhiNode) phis[0]++;
- if (n instanceof MemMergeNode m && m.in(1) instanceof BulkMemPhiNode b)
- for(int a=b._aliases.nextSetBit(0); a>=0; a=b._aliases.nextSetBit(a+1))
- assertTrue(a<m.nIns() && m.in(a)!=null);
- assertFalse(n instanceof PhiNode && n.isMem() &&
- !(n instanceof MemPhiNode) && !(n instanceof BulkMemPhiNode));
- return null;
- });
- assertTrue(phis[0]>=3);
- assertArrayEquals(new Object[]{1L,2L,3L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields());
- }
-
- @Test public void testLateSliceWorklist() throws ReflectiveOperationException {
- // Seed 97 exposed a store selecting a bulk predecessor without queuing
- // it. Keep both the worklist assertion and the final heap check.
- for (int seed : new int[]{0,97,123,456}) {
- var parser = new Parser(Chapter10Test.NESTED_MEMORY);
- var field = IterPeeps.class.getDeclaredField("WORK");
- field.setAccessible(true);
- Object work = field.get(null);
- field = work.getClass().getDeclaredField("_R");
- field.setAccessible(true);
- ((java.util.Random)field.get(work)).setSeed(seed);
- var stop = parser.parse().iterate();
- assertArrayEquals(new Object[]{9L,25L,17L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields());
- }
- }
-}
diff --git a/chapter14/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter14/src/test/java/com/seaofnodes/simple/Chapter11Test.java
index d2e300b1..5f92c9c1 100644
--- a/chapter14/src/test/java/com/seaofnodes/simple/Chapter11Test.java
+++ b/chapter14/src/test/java/com/seaofnodes/simple/Chapter11Test.java
@@ -1,532 +1,64 @@
package com.seaofnodes.simple;
-
+import com.seaofnodes.simple.node.*;
import com.seaofnodes.simple.evaluator.Evaluator;
-import com.seaofnodes.simple.node.StopNode;
import org.junit.Test;
-
-
-import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.*;
public class Chapter11Test {
-
- // A placeholder test used to rapidly rotate through fuzzer produced issues
- @Test
- public void testFuzzer() {
- Parser parser = new Parser(
-"""
-while(-----arg) {
- while(-arg) {
- while(-----arg*---0) {
- int N=--false==false<--arg;
- while(N<-4==N) {
- N=N+N;
- }
- }
- {
- int kzEl_r7EYz=3*----0!=-arg<(37*--97!=0/arg==arg)<=-(--arg!=0);
- while(kzEl_r7EYz<---1) {
- kzEl_r7EYz=kzEl_r7EYz+kzEl_r7EYz*arg>=24;
- if(7) continue;
- kzEl_r7EYz=false;
- if(-kzEl_r7EYz+arg<-3) continue;
- else {
- while(kzEl_r7EYz) continue;
- arg=----3;
- kzEl_r7EYz=-(-----arg*1>-kzEl_r7EYz);
- int v2uF_4ba=9;
- }
- }
- }
- int pjcp7rv=arg;
- {
- int m2ya3=--arg-pjcp7rv;
- while(m2ya3<-----pjcp7rv>=pjcp7rv+--pjcp7rv!=---pjcp7rv!=-arg<---(-m2ya3)>m2ya3<=-----true>14!=--m2ya3) {
- m2ya3=m2ya3+-(--0<=false<pjcp7rv/arg<=-true);
- while((--m2ya3)<--arg<-----arg*false!=arg<pjcp7rv*arg) {
- pjcp7rv=-3+-arg;
- break;
- }
- while(-3) {
- while(67+0-61) m2ya3=m2ya3;
- if(----pjcp7rv==---(---arg)) pjcp7rv=0!=-23;
- else pjcp7rv=----89;
- while(m2ya3!=m2ya3<pjcp7rv) m2ya3=1;
- while(--arg<=pjcp7rv) pjcp7rv=-32<=-m2ya3+62;
- }
- break;
- }
- }
- {
- int arg=-1<-9!=(-arg>=-pjcp7rv>=arg<=arg);
- while(arg<-arg) {
- arg=arg+--arg;
- {
- while((--93)--pjcp7rv*-pjcp7rv+arg) arg=0-(6>=(--(---41/(0))!=--pjcp7rv)>=---2*33);
- pjcp7rv=11;
- int c=pjcp7rv;
- if(--107) break;
- else break;
- }
- }
- }
- pjcp7rv=pjcp7rv;
- int aR0Wkua=-pjcp7rv==pjcp7rv;
- {
- if(-0!=-0) while(-true) break;
- else {
- while(aR0Wkua) pjcp7rv=-0/pjcp7rv;
- pjcp7rv=pjcp7rv;
- }
- }
- }
- if(-arg) {
- {
- int Isdlt0fr91=0!=arg;
- while(Isdlt0fr91<-Isdlt0fr91==-Isdlt0fr91+true) {
- Isdlt0fr91=Isdlt0fr91+-1!=true;
- if(-arg) if(--arg<=Isdlt0fr91) Isdlt0fr91=-Isdlt0fr91;
- int i=---arg<---arg!=--40;
- {
- int jVX43Ln4Dm=-(6)==-Isdlt0fr91/----0;
- while(jVX43Ln4Dm<--(3-3)) {
- jVX43Ln4Dm=jVX43Ln4Dm+-0<25;
- i=24<--(jVX43Ln4Dm);
- }
- }
- i=(arg!=----false>=7);
- int Te=5>-arg;
- break;
- }
- }
- arg=arg!=--true/arg;
- {
- int UX=arg;
- while(UX<-3*arg) {
- UX=UX+arg/-1;
- arg=-3--(-UX--47<arg==--arg==arg)/arg--UX>=-arg;
- if(---12) while(-UX) break;
- break;
- }
- }
- continue;
- }
- if(arg) arg=--0;
- else if(1) continue;
- int DtTlhjYq=19==arg;
- {
- arg=--DtTlhjYq<=(DtTlhjYq/---DtTlhjYq<=-DtTlhjYq);
- if(---arg) continue;
- else {
- int Zsl=40;
- while(Zsl<--Zsl--false>((Zsl))==Zsl!=--DtTlhjYq-DtTlhjYq-DtTlhjYq) {
- Zsl=Zsl+arg;
- }
- }
- if((arg)) if(-DtTlhjYq) {
- }
- else while(((2)==3*arg/DtTlhjYq)<=0==---arg) return false;
- else {
- int lwbF=arg>=0;
- while(lwbF<57) {
- lwbF=lwbF+--(-arg+lwbF)>=-2>=arg!=arg;
- arg=----0+0;
- while(49) break;
- if(true) DtTlhjYq=-----arg;
- DtTlhjYq=0!=-----(0);
- }
- }
- arg=---arg!=DtTlhjYq/--0;
- DtTlhjYq=-DtTlhjYq/(--arg<arg);
- if(32) {
- int q=-DtTlhjYq;
- while(q<arg*(0*q)/0) {
- q=q+DtTlhjYq;
- DtTlhjYq=arg;
- }
- }
- else if(--arg) if(15) break;
- else arg=0==arg<=-55>DtTlhjYq;
- else {
- }
- DtTlhjYq=-0;
- {
- while((0)<-arg) DtTlhjYq=-DtTlhjYq;
- }
- if(30/--(arg)>=0) DtTlhjYq=-0>=arg;
- else {
- int Y2wcIQJ=--DtTlhjYq*---11;
- if(arg==arg) {
- Y2wcIQJ=-----Y2wcIQJ;
- Y2wcIQJ=Y2wcIQJ<7;
- if(DtTlhjYq) arg=arg;
- else break;
- while(-arg!=-31==(false<=-15>=-DtTlhjYq+--6*-----Y2wcIQJ<=---arg!=-Y2wcIQJ<=---0<-arg*--Y2wcIQJ)) DtTlhjYq=arg!=3;
- }
- continue;
- }
- arg=DtTlhjYq;
- arg=--3/(---arg)>=80>=-DtTlhjYq<=DtTlhjYq;
- arg=51+---(-true)!=arg!=----1==-DtTlhjYq;
- if(11<=arg) if((arg)+79<32+(-arg)) continue;
- else if(true==DtTlhjYq) break;
- break;
- }
-}
-if(arg!=62==arg) {
- while(---arg) {
- {
- int bhmDacPM=arg/arg;
- while(bhmDacPM<arg) {
- bhmDacPM=bhmDacPM+80*((-bhmDacPM)/---bhmDacPM>1)<bhmDacPM-2!=7;
- arg=-0;
- arg=bhmDacPM>=-arg+-arg;
- break;
- }
- }
- int arg=true;
- arg=arg<=arg;
- {
- int KlC=30;
- while(KlC<-2) {
- KlC=KlC+-1!=25<=-KlC>KlC>----0;
- int Ij=arg>=-arg<=---10;
- {
- int LAbgurVa2R=-arg!=Ij;
- while(LAbgurVa2R<-true) {
- LAbgurVa2R=LAbgurVa2R+Ij;
- KlC=-LAbgurVa2R;
- Ij=42*(-Ij>true);
- while(Ij) arg=KlC;
- KlC=-----7>-(--KlC<--7)==-LAbgurVa2R;
- }
- }
- int a=Ij<=-KlC;
- if(Ij) {
- int r1W=a!=-false;
- }
- else {
- arg=56>=Ij;
- while(54) break;
- arg=8>=-(a<--Ij)/a>=-a-KlC;
- }
- int Yt_T=KlC;
- arg=KlC;
- }
+ @Test public void testIndependentField() {
+ var stop = new Parser("""
+ struct S { int x; int y; }
+ S s = new S;
+ s.x = 42;
+ while (arg > 0) { s.y = s.y + arg; arg = arg - 1; }
+ return s.x;
+ """).parse().iterate();
+ assertEquals("return 42;",stop.toString());
+ assertEquals(42L,Evaluator.evaluate(stop,5));
+ assertNull(stop.walk(n -> n instanceof LoadNode ? n : null));
+ }
+
+ @Test public void testParallelMemoryPhis() {
+ var stop = new Parser("""
+ struct S { int x; int y; int z; }
+ S a = new S; S b = new S;
+ S p = a; if (arg) p = b;
+ while (arg > 0) {
+ a.x = p.x + arg;
+ a.y = p.y + 2;
+ a.z = p.z + 3;
+ arg = arg - 1;
+ }
+ return a;
+ """).parse().iterate();
+ int[] phis = {0};
+ stop.walk(n -> {
+ if (n instanceof MemPhiNode) phis[0]++;
+ if (n instanceof MemMergeNode m && m.in(1) instanceof BulkMemPhiNode b)
+ for(int a=b._aliases.nextSetBit(0); a>=0; a=b._aliases.nextSetBit(a+1))
+ assertTrue(a<m.nIns() && m.in(a)!=null);
+ assertFalse(n instanceof PhiNode && n.isMem() &&
+ !(n instanceof MemPhiNode) && !(n instanceof BulkMemPhiNode));
+ return null;
+ });
+ assertTrue(phis[0]>=3);
+ assertArrayEquals(new Object[]{1L,2L,3L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields());
+ }
+
+ @Test public void testLateSliceWorklist() throws ReflectiveOperationException {
+ // Seed 97 exposed a store selecting a bulk predecessor without queuing
+ // it. Keep both the worklist assertion and the final heap check.
+ for (int seed : new int[]{0,97,123,456}) {
+ var parser = new Parser(Chapter10Test.NESTED_MEMORY);
+ var field = IterPeeps.class.getDeclaredField("WORK");
+ field.setAccessible(true);
+ Object work = field.get(null);
+ field = work.getClass().getDeclaredField("_R");
+ field.setAccessible(true);
+ ((java.util.Random)field.get(work)).setSeed(seed);
+ var stop = parser.parse().iterate();
+ assertArrayEquals(new Object[]{9L,25L,17L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields());
}
- if(----false/--arg/12+-----0) if(-9+-arg) while(arg!=(arg)) arg=--1>=-71-arg!=---(--arg*11+102)/--arg;
- else if(----arg) continue;
- if(-arg-arg) {
- arg=-(-arg)*--(-3)<(-7==-arg----arg);
- {
- int arg=arg;
- while(arg<-0>arg==-arg-(-arg>1+11)) {
- arg=arg+6-arg!=--0>---30>=---arg<=arg/(3)+---arg;
- }
- }
- arg=-arg+arg;
- arg=--47+-arg<1>arg*(-arg==-arg--0>3);
- arg=(----arg)!=arg+--59;
- arg=--4+arg==-(arg)-arg;
- }
- else {
- while(--true-----true*-25+-18>arg>=-----(-arg)---13) {
- arg=-0+--true<false;
- continue;
- }
- arg=true<=arg;
- break;
- }
- arg=arg*22<--(0+-arg);
- {
- continue;
- }
- }
- arg=1*---((3<=true)==---2);
- arg=7+-(-1);
- return arg+--true;
-}
-else {
- int o3ypEsewxM=-(---arg);
- int vzXB=(-(---11<=--o3ypEsewxM>=--0))<=-0/-arg;
- int L=-arg;
- int B4mHcrf=---vzXB;
- int oZWGdzZl=-o3ypEsewxM;
- int K6tQqa1=11;
- while(0!=--L) {
- int sdZfTM=vzXB*true+K6tQqa1;
- while(sdZfTM<false) {
- sdZfTM=sdZfTM+arg;
- sdZfTM=oZWGdzZl;
- K6tQqa1=-K6tQqa1;
- arg=---K6tQqa1;
- while((3+-K6tQqa1)<oZWGdzZl) {
- if(-----(-1)) sdZfTM=-false;
- {}
- }
- K6tQqa1=vzXB!=-(B4mHcrf+-7>false);
- sdZfTM=vzXB;
- }
- }
- L=false;
- while(31) B4mHcrf=arg;
- oZWGdzZl=-0<--oZWGdzZl<=--2;
- if(K6tQqa1>=20<=46) {
- if(-1+-L) if(oZWGdzZl) {
- int wmhv=-----0;
- }
- int arg=0;
- o3ypEsewxM=---(oZWGdzZl);
- return -oZWGdzZl/0;
- }
- else if(arg) {
- int yKk5=B4mHcrf>=4>K6tQqa1<-B4mHcrf/o3ypEsewxM;
- return -K6tQqa1;
- }
- else {
- if(---0) {
- {}
- {}
- }
- return o3ypEsewxM;
- }
-}
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("Stop[ return 9; return 0; return 0; return 0; ]", stop.toString());
- }
-
-
- @Test
- public void testPrimes() {
- Parser parser = new Parser(
-"""
-if( arg < 2 ) return 0;
-int primeCount = 1;
-int prime = 3;
-while( prime <= arg ) {
- int isPrime = 1;
- // Check for even case, so the next loop need only check odds
- if( (prime/2)*2 == prime )
- continue;
- // Check odds up to sqrt of prime
- int j = 3;
- while( j*j <= prime ) {
- if( (prime/j)*j == prime ) {
- isPrime = 0;
- break;
- }
- j = j + 2;
- }
- if( isPrime )
- primeCount = primeCount + 1;
- prime = prime + 2;
-}
-return primeCount;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("Stop[ return 0; return Phi(Loop21,1,Phi(Region88,Phi_primeCount,Phi(Region82,(Phi_primeCount+1),Phi_primeCount))); ]", stop.toString());
- assertEquals(0L, Evaluator.evaluate(stop, 1)); // No primes 1 or below
- assertEquals(1L, Evaluator.evaluate(stop, 2)); // 2
- assertEquals(2L, Evaluator.evaluate(stop, 3)); // 2, 3
- assertEquals(2L, Evaluator.evaluate(stop, 4)); // 2, 3
- assertEquals(3L, Evaluator.evaluate(stop, 5)); // 2, 3, 5
- assertEquals(4L, Evaluator.evaluate(stop, 10)); // 2, 3, 5, 7
- }
-
- @Test
- public void testAntiDeps1() {
- Parser parser = new Parser(
-"""
-struct S { int f; }
-S v=new S;
-v.f = 2;
-int i=new S.f;
-i=v.f;
-if (arg) v.f=1;
-return i;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return .f;", stop.toString());
- }
-
- @Test
- public void testAntiDeps2() {
- Parser parser = new Parser(
-"""
-struct S { int f; }
-S v = new S;
-S t = new S;
-int i = 0;
-if (arg) {
- if (arg+1) v = t;
- i = v.f;
-} else {
- v.f = 2;
-}
-return i;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Region37,.f,0);", stop.toString());
- }
-
- @Test
- public void testAntiDeps3() {
- Parser parser = new Parser(
-"""
-struct S { int f; }
-S v0 = new S;
-S? v1;
-if (arg) v1 = new S;
-if (v1) {
- v0.f = v1.f;
-} else {
- v0.f = 2;
-}
-return v0;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return new S;", stop.toString());
- }
-
-
- @Test
- public void testAntiDeps4() {
- Parser parser = new Parser(
-"""
-struct S { int f; }
-S v = new S;
-S t = new S;
-int i = v.f;
-if (arg+1) arg= 0;
-while (arg) v.f = 2;
-return i;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return .f;", stop.toString());
- }
-
- @Test
- public void testAntiDeps5() {
- Parser parser = new Parser(
-"""
-struct S { int f; }
-S v = new S;
-while(1) {
- while(arg+1) { arg=arg-1; }
- if (arg) break;
- v.f = 2;
-}
-return v;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return new S;", stop.toString());
- }
-
- @Test
- public void testAntiDeps6() {
- Parser parser = new Parser(
-"""
-struct s { int v; }
-s ptr=new s;
-while( -arg )
- ptr = new s;
-while(1)
- arg = arg+ptr.v;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("Stop[ return 0; return 0; ]", stop.toString());
- }
-
- @Test
- public void testAntiDeps7() {
- Parser parser = new Parser(
-"""
-struct S { int f; }
-S v = new S;
-S t = new S;
-int i = v.f;
-while (arg) {
- v.f = arg;
- arg = arg-1;
-}
-return i;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return .f;", stop.toString());
- }
-
- @Test
- public void testAntiDeps8() {
- Parser parser = new Parser(
-"""
-struct S { int f; }
-S v = new S;
-S t = new S;
-while(arg) {
- arg=arg-1;
- int f = v.f;
- v.f = 2;
- if (arg) arg = f;
- else v.f = 3;
-}
-return arg;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Loop17,arg,Phi(Region41,.f,0));", stop.toString());
- }
-
- @Test
- public void testAntiDeps9() {
- Parser parser = new Parser(
-"""
-struct S { int f; }
-S v = new S;
-S t = new S;
-if (arg) {
- v.f=2;
- int i=t.f;
- v.f=i;
-}
-return v;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return new S;", stop.toString());
- }
-
- @Test
- public void testExample2() {
- Parser parser = new Parser(
- """
-struct S { int f; }
-S v = new S;
-int i = arg;
-while (arg > 0) {
- int j = i/3;
- if (arg == 5)
- v.f = j;
- arg = arg - 1;
-}
-return v;
- """);
- StopNode stop = parser.parse().iterate();
- //assertEquals("return new S;", stop.toString());
- }
-
- @Test
- public void testSplit() {
- Parser parser = new Parser(
- """
-struct S { int f; }
-S s = new S;
-if( arg==0 ) s.f = 1;
-else if (arg == 1) s.f = 1;
-return s.f;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Region43,1,Phi(Region38,1,0));", stop.toString());
- assertEquals(1L, Evaluator.evaluate(stop, 0));
- assertEquals(1L, Evaluator.evaluate(stop, 1));
- assertEquals(0L, Evaluator.evaluate(stop, 2));
}
}
diff --git a/chapter14/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter14/src/test/java/com/seaofnodes/simple/Chapter12Test.java
index 998053ec..e84da36a 100644
--- a/chapter14/src/test/java/com/seaofnodes/simple/Chapter12Test.java
+++ b/chapter14/src/test/java/com/seaofnodes/simple/Chapter12Test.java
@@ -2,82 +2,221 @@ 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 testSubZeroFloat() {
- var stop = new Parser("flt x = arg; return 0-x;").parse().iterate();
- // Compare strings so +0.0 and -0.0 remain distinct.
- assertEquals("0.0", Evaluator.evaluate(stop,0).toString());
- assertEquals("-1.0", Evaluator.evaluate(stop,1).toString());
+ @Test
+ public void testJig() {
+ Parser parser = new Parser(
+"""
+return 3.14;
+""");
+ StopNode stop = parser.parse().iterate();
+ assertEquals("return 3.14;", stop.toString());
+ assertEquals(3.14, Evaluator.evaluate(stop, 0));
}
- @Test public void testDeadNumericReturns() {
- for( String[] test : new String[][] {
- {"if(1) return 7; else return 2.5;", "7"},
- {"if(0) return 7; else return 2.5;", "2.5"},
- {"return 7; return 2.5;", "7"},
- {"return 2.5; return 7;", "2.5"}
- } ) {
- String src = test[0];
- var stop = new Parser(src).parse().iterate();
- assertEquals(src,test[1],com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,0).toString());
- }
+ @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 'i'",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 int0 { int i; flt0? f; }
+struct flt0 { flt f; int0? i; }
+int0 i0 = new int0;
+i0.i = 17;
+flt0 f0 = new flt0;
+f0.f = 3.14;
+i0.f = f0;
+f0.i = i0;
+return f0.i.f.i.i;
+""");
+ StopNode stop = parser.parse().iterate();
+ assertEquals("return 17;", stop.toString());
+ }
@Test
- public void testJig() {
+ public void testNullRef0() {
Parser parser = new Parser(
"""
-return 3.14;
+struct N { N next; int i; }
+N n = new N;
+return n.next;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return 3.14;", stop.toString());
- assertEquals(3.14, Evaluator.evaluate(stop, 0));
+ assertEquals("return null;", stop.toString());
}
@Test
- public void testFloat() {
+ public void testNullRef1() {
Parser parser = new Parser(
"""
-return 3.14;
+struct N { N next; int i; }
+N n = new N;
+n.next = new N;
+return n.next;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return 3.14;", stop.toString());
- assertEquals(3.14, Evaluator.evaluate(stop, 0));
+ assertEquals("return new N;", stop.toString());
}
@Test
- public void testSquareRoot() {
+ public void testNullRef2() {
Parser parser = new Parser(
"""
-flt guess = arg;
-while( 1 ) {
- flt next = (arg/guess + guess)/2;
- if( next == guess ) break;
- guess = next;
-}
-return guess;
+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 testNullRef3() {
+ Parser parser = new Parser(
+"""
+struct N { N next; int i; }
+N n = new N;
+n.i = 3.14;
+return n.i;
+""");
+ try { parser.parse().iterate(); fail(); }
+ catch( Exception e ) { assertEquals("Cannot store 3.14 into field int i",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 Phi(Loop10,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)/2.0));", stop.toString());
- assertEquals(3.0, Evaluator.evaluate(stop, 9));
- assertEquals(1.414213562373095, Evaluator.evaluate(stop, 2));
+ assertEquals("return 0;", stop.toString());
+ assertEquals(0L, Evaluator.evaluate(stop, 0));
+ }
+
+ @Test
+ public void testForwardRef0() {
+ 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 testFPOps() {
+ public void testForwardRef1() {
Parser parser = new Parser(
"""
-flt x = arg;
-return x+1==x;
+struct S1 { S2? s; }
+struct S2 { int x; }
+return new S1.s=new S2;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return ((flt)arg==(ToFloat+1.0));", stop.toString());
- assertEquals(0L, Evaluator.evaluate(stop, 1));
+ 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/chapter14/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter14/src/test/java/com/seaofnodes/simple/Chapter13Test.java
index 15f97b79..34d71d9b 100644
--- a/chapter14/src/test/java/com/seaofnodes/simple/Chapter13Test.java
+++ b/chapter14/src/test/java/com/seaofnodes/simple/Chapter13Test.java
@@ -1,197 +1,532 @@
package com.seaofnodes.simple;
+
import com.seaofnodes.simple.evaluator.Evaluator;
import com.seaofnodes.simple.node.StopNode;
-import org.junit.Ignore;
import org.junit.Test;
+
+
import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.fail;
public class Chapter13Test {
+
+ // A placeholder test used to rapidly rotate through fuzzer produced issues
@Test
- public void testJig() {
+ public void testFuzzer() {
Parser parser = new Parser(
"""
-return 3.14;
+while(-----arg) {
+ while(-arg) {
+ while(-----arg*---0) {
+ int N=--false==false<--arg;
+ while(N<-4==N) {
+ N=N+N;
+ }
+ }
+ {
+ int kzEl_r7EYz=3*----0!=-arg<(37*--97!=0/arg==arg)<=-(--arg!=0);
+ while(kzEl_r7EYz<---1) {
+ kzEl_r7EYz=kzEl_r7EYz+kzEl_r7EYz*arg>=24;
+ if(7) continue;
+ kzEl_r7EYz=false;
+ if(-kzEl_r7EYz+arg<-3) continue;
+ else {
+ while(kzEl_r7EYz) continue;
+ arg=----3;
+ kzEl_r7EYz=-(-----arg*1>-kzEl_r7EYz);
+ int v2uF_4ba=9;
+ }
+ }
+ }
+ int pjcp7rv=arg;
+ {
+ int m2ya3=--arg-pjcp7rv;
+ while(m2ya3<-----pjcp7rv>=pjcp7rv+--pjcp7rv!=---pjcp7rv!=-arg<---(-m2ya3)>m2ya3<=-----true>14!=--m2ya3) {
+ m2ya3=m2ya3+-(--0<=false<pjcp7rv/arg<=-true);
+ while((--m2ya3)<--arg<-----arg*false!=arg<pjcp7rv*arg) {
+ pjcp7rv=-3+-arg;
+ break;
+ }
+ while(-3) {
+ while(67+0-61) m2ya3=m2ya3;
+ if(----pjcp7rv==---(---arg)) pjcp7rv=0!=-23;
+ else pjcp7rv=----89;
+ while(m2ya3!=m2ya3<pjcp7rv) m2ya3=1;
+ while(--arg<=pjcp7rv) pjcp7rv=-32<=-m2ya3+62;
+ }
+ break;
+ }
+ }
+ {
+ int arg=-1<-9!=(-arg>=-pjcp7rv>=arg<=arg);
+ while(arg<-arg) {
+ arg=arg+--arg;
+ {
+ while((--93)--pjcp7rv*-pjcp7rv+arg) arg=0-(6>=(--(---41/(0))!=--pjcp7rv)>=---2*33);
+ pjcp7rv=11;
+ int c=pjcp7rv;
+ if(--107) break;
+ else break;
+ }
+ }
+ }
+ pjcp7rv=pjcp7rv;
+ int aR0Wkua=-pjcp7rv==pjcp7rv;
+ {
+ if(-0!=-0) while(-true) break;
+ else {
+ while(aR0Wkua) pjcp7rv=-0/pjcp7rv;
+ pjcp7rv=pjcp7rv;
+ }
+ }
+ }
+ if(-arg) {
+ {
+ int Isdlt0fr91=0!=arg;
+ while(Isdlt0fr91<-Isdlt0fr91==-Isdlt0fr91+true) {
+ Isdlt0fr91=Isdlt0fr91+-1!=true;
+ if(-arg) if(--arg<=Isdlt0fr91) Isdlt0fr91=-Isdlt0fr91;
+ int i=---arg<---arg!=--40;
+ {
+ int jVX43Ln4Dm=-(6)==-Isdlt0fr91/----0;
+ while(jVX43Ln4Dm<--(3-3)) {
+ jVX43Ln4Dm=jVX43Ln4Dm+-0<25;
+ i=24<--(jVX43Ln4Dm);
+ }
+ }
+ i=(arg!=----false>=7);
+ int Te=5>-arg;
+ break;
+ }
+ }
+ arg=arg!=--true/arg;
+ {
+ int UX=arg;
+ while(UX<-3*arg) {
+ UX=UX+arg/-1;
+ arg=-3--(-UX--47<arg==--arg==arg)/arg--UX>=-arg;
+ if(---12) while(-UX) break;
+ break;
+ }
+ }
+ continue;
+ }
+ if(arg) arg=--0;
+ else if(1) continue;
+ int DtTlhjYq=19==arg;
+ {
+ arg=--DtTlhjYq<=(DtTlhjYq/---DtTlhjYq<=-DtTlhjYq);
+ if(---arg) continue;
+ else {
+ int Zsl=40;
+ while(Zsl<--Zsl--false>((Zsl))==Zsl!=--DtTlhjYq-DtTlhjYq-DtTlhjYq) {
+ Zsl=Zsl+arg;
+ }
+ }
+ if((arg)) if(-DtTlhjYq) {
+ }
+ else while(((2)==3*arg/DtTlhjYq)<=0==---arg) return false;
+ else {
+ int lwbF=arg>=0;
+ while(lwbF<57) {
+ lwbF=lwbF+--(-arg+lwbF)>=-2>=arg!=arg;
+ arg=----0+0;
+ while(49) break;
+ if(true) DtTlhjYq=-----arg;
+ DtTlhjYq=0!=-----(0);
+ }
+ }
+ arg=---arg!=DtTlhjYq/--0;
+ DtTlhjYq=-DtTlhjYq/(--arg<arg);
+ if(32) {
+ int q=-DtTlhjYq;
+ while(q<arg*(0*q)/0) {
+ q=q+DtTlhjYq;
+ DtTlhjYq=arg;
+ }
+ }
+ else if(--arg) if(15) break;
+ else arg=0==arg<=-55>DtTlhjYq;
+ else {
+ }
+ DtTlhjYq=-0;
+ {
+ while((0)<-arg) DtTlhjYq=-DtTlhjYq;
+ }
+ if(30/--(arg)>=0) DtTlhjYq=-0>=arg;
+ else {
+ int Y2wcIQJ=--DtTlhjYq*---11;
+ if(arg==arg) {
+ Y2wcIQJ=-----Y2wcIQJ;
+ Y2wcIQJ=Y2wcIQJ<7;
+ if(DtTlhjYq) arg=arg;
+ else break;
+ while(-arg!=-31==(false<=-15>=-DtTlhjYq+--6*-----Y2wcIQJ<=---arg!=-Y2wcIQJ<=---0<-arg*--Y2wcIQJ)) DtTlhjYq=arg!=3;
+ }
+ continue;
+ }
+ arg=DtTlhjYq;
+ arg=--3/(---arg)>=80>=-DtTlhjYq<=DtTlhjYq;
+ arg=51+---(-true)!=arg!=----1==-DtTlhjYq;
+ if(11<=arg) if((arg)+79<32+(-arg)) continue;
+ else if(true==DtTlhjYq) break;
+ break;
+ }
+}
+if(arg!=62==arg) {
+ while(---arg) {
+ {
+ int bhmDacPM=arg/arg;
+ while(bhmDacPM<arg) {
+ bhmDacPM=bhmDacPM+80*((-bhmDacPM)/---bhmDacPM>1)<bhmDacPM-2!=7;
+ arg=-0;
+ arg=bhmDacPM>=-arg+-arg;
+ break;
+ }
+ }
+ int arg=true;
+ arg=arg<=arg;
+ {
+ int KlC=30;
+ while(KlC<-2) {
+ KlC=KlC+-1!=25<=-KlC>KlC>----0;
+ int Ij=arg>=-arg<=---10;
+ {
+ int LAbgurVa2R=-arg!=Ij;
+ while(LAbgurVa2R<-true) {
+ LAbgurVa2R=LAbgurVa2R+Ij;
+ KlC=-LAbgurVa2R;
+ Ij=42*(-Ij>true);
+ while(Ij) arg=KlC;
+ KlC=-----7>-(--KlC<--7)==-LAbgurVa2R;
+ }
+ }
+ int a=Ij<=-KlC;
+ if(Ij) {
+ int r1W=a!=-false;
+ }
+ else {
+ arg=56>=Ij;
+ while(54) break;
+ arg=8>=-(a<--Ij)/a>=-a-KlC;
+ }
+ int Yt_T=KlC;
+ arg=KlC;
+ }
+ }
+ if(----false/--arg/12+-----0) if(-9+-arg) while(arg!=(arg)) arg=--1>=-71-arg!=---(--arg*11+102)/--arg;
+ else if(----arg) continue;
+ if(-arg-arg) {
+ arg=-(-arg)*--(-3)<(-7==-arg----arg);
+ {
+ int arg=arg;
+ while(arg<-0>arg==-arg-(-arg>1+11)) {
+ arg=arg+6-arg!=--0>---30>=---arg<=arg/(3)+---arg;
+ }
+ }
+ arg=-arg+arg;
+ arg=--47+-arg<1>arg*(-arg==-arg--0>3);
+ arg=(----arg)!=arg+--59;
+ arg=--4+arg==-(arg)-arg;
+ }
+ else {
+ while(--true-----true*-25+-18>arg>=-----(-arg)---13) {
+ arg=-0+--true<false;
+ continue;
+ }
+ arg=true<=arg;
+ break;
+ }
+ arg=arg*22<--(0+-arg);
+ {
+ continue;
+ }
+ }
+ arg=1*---((3<=true)==---2);
+ arg=7+-(-1);
+ return arg+--true;
+}
+else {
+ int o3ypEsewxM=-(---arg);
+ int vzXB=(-(---11<=--o3ypEsewxM>=--0))<=-0/-arg;
+ int L=-arg;
+ int B4mHcrf=---vzXB;
+ int oZWGdzZl=-o3ypEsewxM;
+ int K6tQqa1=11;
+ while(0!=--L) {
+ int sdZfTM=vzXB*true+K6tQqa1;
+ while(sdZfTM<false) {
+ sdZfTM=sdZfTM+arg;
+ sdZfTM=oZWGdzZl;
+ K6tQqa1=-K6tQqa1;
+ arg=---K6tQqa1;
+ while((3+-K6tQqa1)<oZWGdzZl) {
+ if(-----(-1)) sdZfTM=-false;
+ {}
+ }
+ K6tQqa1=vzXB!=-(B4mHcrf+-7>false);
+ sdZfTM=vzXB;
+ }
+ }
+ L=false;
+ while(31) B4mHcrf=arg;
+ oZWGdzZl=-0<--oZWGdzZl<=--2;
+ if(K6tQqa1>=20<=46) {
+ if(-1+-L) if(oZWGdzZl) {
+ int wmhv=-----0;
+ }
+ int arg=0;
+ o3ypEsewxM=---(oZWGdzZl);
+ return -oZWGdzZl/0;
+ }
+ else if(arg) {
+ int yKk5=B4mHcrf>=4>K6tQqa1<-B4mHcrf/o3ypEsewxM;
+ return -K6tQqa1;
+ }
+ else {
+ if(---0) {
+ {}
+ {}
+ }
+ return o3ypEsewxM;
+ }
+}
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return 3.14;", stop.toString());
- assertEquals(3.14, Evaluator.evaluate(stop, 0));
+ assertEquals("Stop[ return 9; return 0; return 0; return 0; ]", stop.toString());
}
+
@Test
- public void testLinkedList0() {
+ public void testPrimes() {
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( arg < 2 ) return 0;
+int primeCount = 1;
+int prime = 3;
+while( prime <= arg ) {
+ int isPrime = 1;
+ // Check for even case, so the next loop need only check odds
+ if( (prime/2)*2 == prime )
+ continue;
+ // Check odds up to sqrt of prime
+ int j = 3;
+ while( j*j <= prime ) {
+ if( (prime/j)*j == prime ) {
+ isPrime = 0;
+ break;
+ }
+ j = j + 2;
+ }
+ if( isPrime )
+ primeCount = primeCount + 1;
+ prime = prime + 2;
}
-return head.next.i;
+return primeCount;
""");
- try { parser.parse().iterate(); fail(); }
- catch( Exception e ) { assertEquals("Might be null accessing 'i'",e.getMessage()); }
+ StopNode stop = parser.parse().iterate();
+ assertEquals("Stop[ return 0; return Phi(Loop21,1,Phi(Region88,Phi_primeCount,Phi(Region82,(Phi_primeCount+1),Phi_primeCount))); ]", stop.toString());
+ assertEquals(0L, Evaluator.evaluate(stop, 1)); // No primes 1 or below
+ assertEquals(1L, Evaluator.evaluate(stop, 2)); // 2
+ assertEquals(2L, Evaluator.evaluate(stop, 3)); // 2, 3
+ assertEquals(2L, Evaluator.evaluate(stop, 4)); // 2, 3
+ assertEquals(3L, Evaluator.evaluate(stop, 5)); // 2, 3, 5
+ assertEquals(4L, Evaluator.evaluate(stop, 10)); // 2, 3, 5, 7
}
@Test
- public void testLinkedList1() {
+ public void testAntiDeps1() {
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;
+struct S { int f; }
+S v=new S;
+v.f = 2;
+int i=new S.f;
+i=v.f;
+if (arg) v.f=1;
+return i;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("Stop[ return 0; return 1; return .i; ]", stop.toString());
- assertEquals(2L, Evaluator.evaluate(stop, 3));
+ assertEquals("return .f;", stop.toString());
}
@Test
- public void testCoRecur() {
+ public void testAntiDeps2() {
Parser parser = new Parser(
"""
-struct int0 { int i; flt0? f; }
-struct flt0 { flt f; int0? i; }
-int0 i0 = new int0;
-i0.i = 17;
-flt0 f0 = new flt0;
-f0.f = 3.14;
-i0.f = f0;
-f0.i = i0;
-return f0.i.f.i.i;
+struct S { int f; }
+S v = new S;
+S t = new S;
+int i = 0;
+if (arg) {
+ if (arg+1) v = t;
+ i = v.f;
+} else {
+ v.f = 2;
+}
+return i;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return 17;", stop.toString());
+ assertEquals("return Phi(Region37,.f,0);", stop.toString());
}
@Test
- public void testNullRef0() {
+ public void testAntiDeps3() {
Parser parser = new Parser(
"""
-struct N { N next; int i; }
-N n = new N;
-return n.next;
+struct S { int f; }
+S v0 = new S;
+S? v1;
+if (arg) v1 = new S;
+if (v1) {
+ v0.f = v1.f;
+} else {
+ v0.f = 2;
+}
+return v0;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return null;", stop.toString());
+ assertEquals("return new S;", stop.toString());
}
+
@Test
- public void testNullRef1() {
+ public void testAntiDeps4() {
Parser parser = new Parser(
"""
-struct N { N next; int i; }
-N n = new N;
-n.next = new N;
-return n.next;
+struct S { int f; }
+S v = new S;
+S t = new S;
+int i = v.f;
+if (arg+1) arg= 0;
+while (arg) v.f = 2;
+return i;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return new N;", stop.toString());
+ assertEquals("return .f;", stop.toString());
}
@Test
- public void testNullRef2() {
+ public void testAntiDeps5() {
Parser parser = new Parser(
"""
-struct N { N next; int i; }
-N n = new N;
-n.next = null;
-return n.next;
+struct S { int f; }
+S v = new S;
+while(1) {
+ while(arg+1) { arg=arg-1; }
+ if (arg) break;
+ v.f = 2;
+}
+return v;
""");
- try { parser.parse().iterate(); fail(); }
- catch( Exception e ) { assertEquals("Cannot store null into field *N next",e.getMessage()); }
+ StopNode stop = parser.parse().iterate();
+ assertEquals("return new S;", stop.toString());
}
@Test
- public void testNullRef3() {
+ public void testAntiDeps6() {
Parser parser = new Parser(
"""
-struct N { N next; int i; }
-N n = new N;
-n.i = 3.14;
-return n.i;
+struct s { int v; }
+s ptr=new s;
+while( -arg )
+ ptr = new s;
+while(1)
+ arg = arg+ptr.v;
""");
- try { parser.parse().iterate(); fail(); }
- catch( Exception e ) { assertEquals("Cannot store 3.14 into field int i",e.getMessage()); }
+ StopNode stop = parser.parse().iterate();
+ assertEquals("Stop[ return 0; return 0; ]", stop.toString());
}
@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()); }
+ public void testAntiDeps7() {
+ Parser parser = new Parser(
+"""
+struct S { int f; }
+S v = new S;
+S t = new S;
+int i = v.f;
+while (arg) {
+ v.f = arg;
+ arg = arg-1;
+}
+return i;
+""");
+ StopNode stop = parser.parse().iterate();
+ assertEquals("return .f;", stop.toString());
}
@Test
- public void testEmpty() {
+ public void testAntiDeps8() {
Parser parser = new Parser(
"""
-struct S{};
+struct S { int f; }
+S v = new S;
+S t = new S;
+while(arg) {
+ arg=arg-1;
+ int f = v.f;
+ v.f = 2;
+ if (arg) arg = f;
+ else v.f = 3;
+}
+return arg;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return 0;", stop.toString());
- assertEquals(0L, Evaluator.evaluate(stop, 0));
+ assertEquals("return Phi(Loop17,arg,Phi(Region41,.f,0));", stop.toString());
}
@Test
- public void testForwardRef0() {
+ public void testAntiDeps9() {
Parser parser = new Parser(
"""
-struct S1 { S2 s; }
-return new S2;
+struct S { int f; }
+S v = new S;
+S t = new S;
+if (arg) {
+ v.f=2;
+ int i=t.f;
+ v.f=i;
+}
+return v;
""");
- try { parser.parse().iterate(); fail(); }
- catch( Exception e ) { assertEquals("Unknown struct type 'S2'",e.getMessage()); }
+ StopNode stop = parser.parse().iterate();
+ assertEquals("return new S;", stop.toString());
}
@Test
- public void testForwardRef1() {
+ public void testExample2() {
Parser parser = new Parser(
-"""
-struct S1 { S2? s; }
-struct S2 { int x; }
-return new S1.s=new S2;
-""");
+ """
+struct S { int f; }
+S v = new S;
+int i = arg;
+while (arg > 0) {
+ int j = i/3;
+ if (arg == 5)
+ v.f = j;
+ arg = arg - 1;
+}
+return v;
+ """);
StopNode stop = parser.parse().iterate();
- assertEquals("return new S1;", stop.toString());
+ //assertEquals("return new S;", stop.toString());
}
@Test
- public void testcheckNull() {
+ public void testSplit() {
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;
+ """
+struct S { int f; }
+S s = new S;
+if( arg==0 ) s.f = 1;
+else if (arg == 1) s.f = 1;
+return s.f;
""");
- try { parser.parse().iterate(); fail(); }
- catch( Exception e ) { assertEquals("Might be null accessing 'i'",e.getMessage()); }
+ StopNode stop = parser.parse().iterate();
+ assertEquals("return Phi(Region43,1,Phi(Region38,1,0));", stop.toString());
+ assertEquals(1L, Evaluator.evaluate(stop, 0));
+ assertEquals(1L, Evaluator.evaluate(stop, 1));
+ assertEquals(0L, Evaluator.evaluate(stop, 2));
}
-
}
diff --git a/chapter14/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java b/chapter14/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java
new file mode 100644
index 00000000..f2b51da2
--- /dev/null
+++ b/chapter14/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java
@@ -0,0 +1,95 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.evaluator.Evaluator;
+import com.seaofnodes.simple.node.StopNode;
+import org.junit.Ignore;
+import org.junit.Test;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.fail;
+
+public class Chapter14FloatTest {
+ @Test public void testSubZeroFloat() {
+ var stop = new Parser("flt x = arg; return 0-x;").parse().iterate();
+ // Compare strings so +0.0 and -0.0 remain distinct.
+ assertEquals("0.0", Evaluator.evaluate(stop,0).toString());
+ assertEquals("-1.0", Evaluator.evaluate(stop,1).toString());
+ }
+
+ @Test public void testDeadNumericReturns() {
+ for( String[] test : new String[][] {
+ {"if(1) return 7; else return 2.5;", "7"},
+ {"if(0) return 7; else return 2.5;", "2.5"},
+ {"return 7; return 2.5;", "7"},
+ {"return 2.5; return 7;", "2.5"}
+ } ) {
+ String src = test[0];
+ var stop = new Parser(src).parse().iterate();
+ assertEquals(src,test[1],com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,0).toString());
+ }
+ }
+
+
+ @Test
+ public void testJig() {
+ Parser parser = new Parser(
+"""
+return 3.14;
+""");
+ StopNode stop = parser.parse().iterate();
+ assertEquals("return 3.14;", stop.toString());
+ assertEquals(3.14, Evaluator.evaluate(stop, 0));
+ }
+
+ @Test
+ public void testFloat() {
+ Parser parser = new Parser(
+"""
+return 3.14;
+""");
+ StopNode stop = parser.parse().iterate();
+ assertEquals("return 3.14;", stop.toString());
+ assertEquals(3.14, Evaluator.evaluate(stop, 0));
+ }
+
+ @Test
+ public void testSquareRoot() {
+ Parser parser = new Parser(
+"""
+flt guess = arg;
+while( 1 ) {
+ flt next = (arg/guess + guess)/2;
+ if( next == guess ) break;
+ guess = next;
+}
+return guess;
+""");
+ StopNode stop = parser.parse().iterate();
+ assertEquals("return Phi(Loop10,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)/2.0));", stop.toString());
+ assertEquals(3.0, Evaluator.evaluate(stop, 9));
+ assertEquals(1.414213562373095, Evaluator.evaluate(stop, 2));
+ }
+
+ @Test
+ public void testFPOps() {
+ Parser parser = new Parser(
+"""
+flt x = arg;
+return x+1==x;
+""");
+ StopNode stop = parser.parse().iterate();
+ assertEquals("return ((flt)arg==(ToFloat+1.0));", stop.toString());
+ assertEquals(0L, Evaluator.evaluate(stop, 1));
+ }
+ @Test
+ public void testReferenceFieldRejectsFloat() {
+ Parser parser = new Parser(
+"""
+struct N { N next; int i; }
+N n = new N;
+n.i = 3.14;
+return n.i;
+""");
+ try { parser.parse().iterate(); fail(); }
+ catch( Exception e ) { assertEquals("Cannot store 3.14 into field int i",e.getMessage()); }
+ }
+}