Chapter 1: Introduction

Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>

5 files changed, 460 insertions, 0 deletions

diff --git a/transpile-tests/src/main/java/com/seaofnodes/simple/transpile/AstVisitor.java b/transpile-tests/src/main/java/com/seaofnodes/simple/transpile/AstVisitor.java
new file mode 100644
index 00000000..19709b9e
--- /dev/null
+++ b/transpile-tests/src/main/java/com/seaofnodes/simple/transpile/AstVisitor.java
@@ -0,0 +1,173 @@
+package com.seaofnodes.simple.transpile;
+
+import com.sun.source.tree.*;
+import com.sun.source.util.TreeScanner;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+
+class AstVisitor extends TreeScanner<Void, Void> {
+    final HashMap<String, TestClass> results = new HashMap<>();
+
+    private String className;
+    private TestMethod current;
+    private boolean inCatch;
+
+    @Override
+    public Void visitClass(ClassTree node, Void unused) {
+        var name = node.getSimpleName().toString();
+        if (name.matches("Chapter\\d+Test")) {
+            var backup = className;
+            className = name;
+            super.visitClass(node, unused);
+            className = backup;
+        }
+        return null;
+    }
+
+    @Override
+    public Void visitMethod(MethodTree node, Void unused) {
+        if (className != null) {
+            current = new TestMethod();
+            current.name = node.getName().toString();
+            super.visitMethod(node, unused);
+            results.compute(className, (k, v) -> {
+                if (v == null)
+                    v = new TestClass(className, new ArrayList<>());
+                v.methods().add(current);
+                return v;
+            });
+            current = null;
+        }
+        return null;
+    }
+
+    @Override
+    public Void visitMethodInvocation(MethodInvocationTree node, Void unused) {
+        if (current != null) {
+            var methodSelect = node.getMethodSelect().toString();
+            var args = node.getArguments();
+
+            if (methodSelect.endsWith(".parse")) {
+                current.showAfterParse = switch (args.size()) {
+                    case 0 -> false;
+                    case 1 -> (Boolean) literal(args.getFirst());
+                    default -> throw new RuntimeException("unexpected parse arguments" + node);
+                };
+            }
+            if (methodSelect.endsWith(".iterate")) {
+                current.iterate = true;
+                current.showAfterIterate = switch (args.size()) {
+                    case 0 -> false;
+                    case 1 -> (Boolean) literal(args.getFirst());
+                    default -> throw new RuntimeException("unexpected parse arguments" + node);
+                };
+            }
+            if (methodSelect.endsWith("assertEquals")) {
+                if (inCatch) {
+                    if (args.size() != 2)
+                        throw new RuntimeException("Unexpected number of arguments " + node);
+                    if (args.get(1).toString().contains("e.getMessage()")) {
+                        current.parseErrorMessage = (String) literal(args.get(0));
+                    }
+                } else {
+                    if (args.size() != 2)
+                        throw new RuntimeException("Unexpected number of arguments " + node);
+                    if (args.get(1).toString().contains("evaluate(")) {
+                        // visit evaluate(..) or evaluate(..).toString()
+                        var eval = args.get(1).accept(new TreeScanner<MethodInvocationTree, Void>() {
+                            @Override
+                            public MethodInvocationTree reduce(MethodInvocationTree r1, MethodInvocationTree r2) {
+                                return r1 != null ? r1 : r2;
+                            }
+
+                            @Override
+                            public MethodInvocationTree visitMethodInvocation(MethodInvocationTree n, Void unused1) {
+                                if (n.getMethodSelect().toString().endsWith(".evaluate"))
+                                    return n;
+                                return super.visitMethodInvocation(n, unused1);
+                            }
+                        }, null);
+
+                        Object result = literal(args.get(0));
+                        var evalArgs = eval.getArguments();
+                        if (evalArgs.size() != 2 || !evalArgs.get(0).toString().equals("stop"))
+                            throw new IllegalArgumentException("Unexpected eval arguments " + node);
+                        long parameter = Long.parseLong(literal(evalArgs.get(1)).toString());
+                        current.evaluations.add(new TestMethod.Evaluation(result, parameter));
+                    } else if (args.get(1).toString().endsWith(".toString()") || args.get(1).toString().endsWith(".print()")) {
+                        if (current.assertStopEquals == null) {
+                            // Assume the first one prints the stop node. Ignore assertions from evaluator:
+                            //     assertEquals("int[] {\n  # :int;\n  [] :int;\n}",obj.struct().toString());
+                            current.assertStopEquals = (String) literal(args.get(0));
+                        }
+                    }
+                }
+            }
+            if (methodSelect.endsWith("assertTrue")) {
+                var arg = args.getFirst().toString();
+                current.assertStopRetCtrlIsProj = arg.contains("stop.ret().ctrl() instanceof ProjNode");
+                current.assertStopRetCtrlIsCProj = arg.contains("stop.ret().ctrl() instanceof CProjNode");
+                current.assertStopRetCtrlIsRegion = arg.contains("stop.ret().ctrl() instanceof RegionNode");
+            }
+            if (methodSelect.endsWith("prettyPrint")) {
+                if (args.size() < 2 || args.size() > 3 || !args.get(0).toString().equals("stop") || !args.get(1).toString().equals("99"))
+                    throw new RuntimeException("unexpected prettyPrint args " + node);
+                current.irPrinter = true;
+                current.irPrinterLLVM = args.size() == 3 && (Boolean) literal(args.get(2));
+            }
+        }
+        return super.visitMethodInvocation(node, unused); // otherwise we would miss the first part of new Parser("").parse()
+    }
+
+    @Override
+    public Void visitNewClass(NewClassTree node, Void unused) {
+        if (current != null) {
+            if (node.getIdentifier().toString().equals("Parser")) {
+                var args = node.getArguments();
+                switch (args.size()) {
+                    case 1 -> {
+                    }
+                    case 2 -> current.parserArg = switch (args.get(1).toString()) {
+                        case "TypeInteger.BOT" -> new TestMethod.Arg.IntBot();
+                        case "TypeInteger.TOP" -> new TestMethod.Arg.IntTop();
+                        case String s -> {
+                            var parts = s.split("[()]");
+                            if (parts.length != 2 | !parts[0].equals("TypeInteger.constant"))
+                                throw new RuntimeException("Unexpected Argument " + s);
+                            yield new TestMethod.Arg.IntConstant(Long.parseLong(parts[1]));
+                        }
+                    };
+                    default -> throw new RuntimeException("Parser constructor with unexpected arguments: " + node);
+                }
+                current.parserInput = (String) literal(args.get(0));
+            } else if (node.getIdentifier().toString().equals("GraphVisualizer")) {
+                // only happens in Chapter02Tests
+                current.showAfterParse = true;
+            }
+        }
+        return super.visitNewClass(node, unused);
+    }
+
+    @Override
+    public Void visitCatch(CatchTree node, Void unused) {
+        inCatch = true;
+        super.visitCatch(node, unused);
+        inCatch = false;
+        return null;
+    }
+
+    @Override
+    public Void visitAssignment(AssignmentTree node, Void unused) {
+        if (current != null && node.getVariable().toString().equals("Node._disablePeephole")) {
+            if ((Boolean) literal(node.getExpression())) {
+                current.disablePeephole = true;
+            }
+        }
+        return super.visitAssignment(node, unused);
+    }
+
+    private Object literal(ExpressionTree t) {
+        return ((LiteralTree) t).getValue();
+    }
+}
diff --git a/transpile-tests/src/main/java/com/seaofnodes/simple/transpile/JUnitParser.java b/transpile-tests/src/main/java/com/seaofnodes/simple/transpile/JUnitParser.java
new file mode 100644
index 00000000..2db2a08c
--- /dev/null
+++ b/transpile-tests/src/main/java/com/seaofnodes/simple/transpile/JUnitParser.java
@@ -0,0 +1,71 @@
+package com.seaofnodes.simple.transpile;
+
+import com.sun.source.util.JavacTask;
+
+import javax.tools.ToolProvider;
+import java.io.File;
+import java.io.IOException;
+import java.nio.file.FileVisitResult;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.nio.file.SimpleFileVisitor;
+import java.nio.file.attribute.BasicFileAttributes;
+import java.util.*;
+
+import static java.util.Comparator.comparing;
+
+public class JUnitParser {
+
+    /**
+     * @param simpleRepo The path to the project root
+     * @return A sorted map from chapter name to a sorted list of parsed test classes.
+     */
+    public static TreeMap<String, List<TestClass>> parseRepository(Path simpleRepo) throws IOException {
+        var chapters = new TreeMap<String, List<TestClass>>();
+        var inputs = simpleRepo.toFile().listFiles(File::isDirectory);
+        if (inputs == null)
+            throw new IOException("failed to read Simple project root");
+        Arrays.sort(inputs);
+        for (File file : inputs) {
+            var chapter = file.getName();
+            if (chapter.matches("chapter\\d+")) {
+                chapters.put(chapter, parseChapter(file.toPath()));
+            }
+        }
+        return chapters;
+    }
+
+    /**
+     * @param input The path to a chapter in the repository.
+     * @return a sorted list of parsed test classes
+     */
+    public static List<TestClass> parseChapter(Path input) throws IOException {
+        var tests = new ArrayList<Path>();
+        Files.walkFileTree(input, Set.of(), 20, new SimpleFileVisitor<>() {
+            @Override
+            public FileVisitResult visitFile(Path file, BasicFileAttributes attrs) {
+                if (file.getFileName().toString().matches("Chapter\\d+Test\\.java")) {
+                    tests.add(file);
+                }
+                return FileVisitResult.CONTINUE;
+            }
+        });
+
+        var compiler = ToolProvider.getSystemJavaCompiler();
+        var compilationUnits = compiler
+                .getStandardFileManager(null, null, null)
+                .getJavaFileObjectsFromPaths(tests);
+
+        var task = (JavacTask) compiler.getTask(null, null, null, null, null, compilationUnits);
+
+        var visitor = new AstVisitor();
+        for (var tree : task.parse()) {
+            try { tree.accept(visitor, null); }
+            catch( IllegalArgumentException iae ) {}
+        }
+
+        var testClasses = new ArrayList<>(visitor.results.values());
+        testClasses.sort(comparing(TestClass::name));
+        return testClasses;
+    }
+}
diff --git a/transpile-tests/src/main/java/com/seaofnodes/simple/transpile/TestClass.java b/transpile-tests/src/main/java/com/seaofnodes/simple/transpile/TestClass.java
new file mode 100644
index 00000000..5bb5609c
--- /dev/null
+++ b/transpile-tests/src/main/java/com/seaofnodes/simple/transpile/TestClass.java
@@ -0,0 +1,6 @@
+package com.seaofnodes.simple.transpile;
+
+import java.util.ArrayList;
+
+public record TestClass(String name, ArrayList<TestMethod> methods) {
+}
diff --git a/transpile-tests/src/main/java/com/seaofnodes/simple/transpile/TestMethod.java b/transpile-tests/src/main/java/com/seaofnodes/simple/transpile/TestMethod.java
new file mode 100644
index 00000000..d0c6cfa8
--- /dev/null
+++ b/transpile-tests/src/main/java/com/seaofnodes/simple/transpile/TestMethod.java
@@ -0,0 +1,39 @@
+package com.seaofnodes.simple.transpile;
+
+import java.util.ArrayList;
+
+public class TestMethod {
+    public String name;
+    public String parserInput;
+    public Arg parserArg;
+    // if this is set you can ignore the rest
+    public String parseErrorMessage;
+    public boolean disablePeephole;
+    public boolean showAfterParse;
+    public boolean iterate;
+    public boolean showAfterIterate;
+    public boolean irPrinter;
+    public boolean irPrinterLLVM;
+    public String assertStopEquals;
+    public boolean assertStopRetCtrlIsProj;
+    public boolean assertStopRetCtrlIsCProj;
+    public boolean assertStopRetCtrlIsRegion;
+    public final ArrayList<Evaluation> evaluations = new ArrayList<>();
+
+    public sealed interface Arg {
+        record IntBot() implements Arg {
+        }
+
+        record IntTop() implements Arg {
+        }
+
+        record IntConstant(long value) implements Arg {
+        }
+    }
+
+    /**
+     * result is a literal value
+     **/
+    public record Evaluation(Object result, long parameter) {
+    }
+}
diff --git a/transpile-tests/src/main/java/com/seaofnodes/simple/transpile/printers/RustPrinter.java b/transpile-tests/src/main/java/com/seaofnodes/simple/transpile/printers/RustPrinter.java
new file mode 100644
index 00000000..115a075a
--- /dev/null
+++ b/transpile-tests/src/main/java/com/seaofnodes/simple/transpile/printers/RustPrinter.java
@@ -0,0 +1,171 @@
+package com.seaofnodes.simple.transpile.printers;
+
+import com.seaofnodes.simple.transpile.JUnitParser;
+import com.seaofnodes.simple.transpile.TestClass;
+import com.seaofnodes.simple.transpile.TestMethod;
+
+import java.io.BufferedOutputStream;
+import java.io.IOException;
+import java.io.PrintStream;
+import java.nio.charset.StandardCharsets;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.util.ArrayList;
+import java.util.List;
+
+public class RustPrinter {
+
+    public static void main(String[] args) throws Exception {
+        if (args.length != 2) {
+            System.out.println("Usage: <path-to-simple-repo> <output-dir>");
+            System.exit(1);
+        }
+        var printer = new RustPrinter();
+        var output = Path.of(args[1]);
+
+        for (var e : JUnitParser.parseRepository(Path.of(args[0])).entrySet()) {
+            printer.printToFile(e.getKey(), e.getValue(), output);
+        }
+    }
+
+    private void printToFile(String chapter, List<TestClass> testClasses, Path outputDirectory) throws IOException, InterruptedException {
+        var output = outputDirectory.resolve(chapter);
+        Files.createDirectories(output);
+        for (var testClass : testClasses) {
+            var outputFile = output.resolve(testClass.name().replace("Test", "").toLowerCase() + ".rs");
+            System.out.println(outputFile);
+            Files.write(outputFile, printAndRustfmt(testClass.methods()));
+        }
+    }
+
+    private byte[] printAndRustfmt(ArrayList<TestMethod> tests) throws IOException, InterruptedException {
+        var p = Runtime.getRuntime().exec(new String[]{"rustfmt"});
+        try (var print = new PrintStream(new BufferedOutputStream(p.getOutputStream()))) {
+            printFile(tests, print);
+        }
+        p.waitFor();
+
+        var errors = new String(p.getErrorStream().readAllBytes(), StandardCharsets.UTF_8);
+        if (!errors.isEmpty() || p.exitValue() != 0) {
+            throw new RuntimeException("rustfmt exit=" + p.exitValue() + " stderr=" + errors);
+        }
+
+        return p.getInputStream().readAllBytes();
+    }
+
+    private void printFile(ArrayList<TestMethod> tests, PrintStream out) {
+        out.println("""
+                use crate::datastructures::arena::DroplessArena;
+                use crate::sea_of_nodes::parser::Parser;
+                use crate::sea_of_nodes::types::Types;""");
+
+        if (tests.stream().anyMatch(t -> t.assertStopRetCtrlIsProj || t.assertStopRetCtrlIsCProj || t.assertStopRetCtrlIsRegion)) {
+            out.println("use crate::sea_of_nodes::nodes::Op;");
+        }
+        if (tests.stream().anyMatch(t -> t.parseErrorMessage != null && !t.iterate)) {
+            out.println("use crate::sea_of_nodes::tests::test_error;");
+        }
+        if (tests.stream().anyMatch(t -> t.parseErrorMessage != null && t.iterate)) {
+            out.println("use crate::sea_of_nodes::tests::test_error_iterate;");
+        }
+        if (tests.stream().anyMatch(t -> t.irPrinter && !t.irPrinterLLVM)) {
+            out.println("use crate::sea_of_nodes::ir_printer::pretty_print;");
+        }
+        if (tests.stream().anyMatch(t -> t.irPrinterLLVM)) {
+            out.println("use crate::sea_of_nodes::ir_printer::pretty_print_llvm;");
+        }
+        if (tests.stream().anyMatch(t -> !t.evaluations.isEmpty())) {
+            out.println("use crate::sea_of_nodes::tests::evaluator::{evaluate, Object};");
+        }
+
+        for (TestMethod test : tests) {
+            printTest(test, out);
+        }
+    }
+
+    private void printTest(TestMethod test, PrintStream out) {
+        out.println();
+        out.println("#[test]");
+        out.println("fn " + snakeCase(test.name) + "() {");
+        if (test.parseErrorMessage != null) {
+            if (test.iterate) {
+                out.println("test_error_iterate(" + string(test.parserInput) + ", " + string(test.parseErrorMessage) + ");");
+            } else {
+                out.println("test_error(" + string(test.parserInput) + ", " + string(test.parseErrorMessage) + ");");
+            }
+        } else if (test.parserInput != null) {
+            out.println("let arena = DroplessArena::new();");
+            out.println("let types = Types::new(&arena);");
+            if (test.parserArg == null) {
+                out.println("let mut parser = Parser::new(" + string(test.parserInput) + ", &types);");
+            } else {
+                out.printf("let mut parser = Parser::new_with_arg(%s, &types, %s);\n", string(test.parserInput), switch (test.parserArg) {
+                    case TestMethod.Arg.IntBot ignored -> "types.ty_int_bot";
+                    case TestMethod.Arg.IntTop ignored -> "types.ty_int_top";
+                    case TestMethod.Arg.IntConstant c -> "types.get_int(" + c.value() + ")";
+                });
+            }
+            if (test.disablePeephole) {
+                out.println("parser.nodes.disable_peephole = true;");
+            }
+            out.println("let stop = parser.parse().unwrap();");
+            if (test.showAfterParse) {
+                out.println("parser.show_graph();");
+            }
+            if (test.iterate) {
+                out.println("parser.iterate(stop);");
+                out.println("parser.type_check(stop).unwrap();\n");
+            }
+            if (test.showAfterIterate) {
+                out.println("parser.show_graph();");
+            }
+            if (test.irPrinter) {
+                out.println("println!(\"{}\", pretty_print" + (test.irPrinterLLVM ? "_llvm" : "") + "(&parser.nodes, stop, 99));");
+            }
+            if (test.assertStopEquals != null) {
+                out.println("assert_eq!(parser.print(stop), " + string(test.assertStopEquals) + ");");
+            }
+            if (test.assertStopRetCtrlIsProj) {
+                out.println("assert!(matches!(parser.nodes.ret_ctrl(stop), Op::Proj(_)));");
+            }
+            if (test.assertStopRetCtrlIsCProj) {
+                out.println("assert!(matches!(parser.nodes.ret_ctrl(stop), Op::CProj(_)));");
+            }
+            if (test.assertStopRetCtrlIsRegion) {
+                out.println("assert!(matches!(parser.nodes.ret_ctrl(stop), Op::Region{..}));");
+            }
+            for (var evaluation : test.evaluations) {
+                var result = switch (evaluation.result()) {
+                    case null -> "Object::Null";
+                    case Integer l -> "Object::Long(" + l + ")";
+                    case Long l -> "Object::Long(" + l + ")";
+                    case Float d -> "Object::Double(" + d + ")";
+                    case Double d -> "Object::Double(" + d + ")";
+                    case String s -> string(s);
+                    default ->
+                            throw new RuntimeException("unexpected evaluation result: " + evaluation.result().getClass());
+                };
+                out.println("assert_eq!(" + result + ", evaluate(&parser.nodes, stop, Some(" + evaluation.parameter() + "), None).1);");
+            }
+        } else {
+            out.println("todo!();");
+        }
+        out.println("}");
+    }
+
+    private String string(String value) {
+        var escaped = value.replace("\\", "\\\\")
+                .replace("\r", "\\r")
+                .replace("\t", "\\t")
+                .replace("\"", "\\\"");
+        if (escaped.contains("\n")) {
+            return "\"\\\n" + escaped + "\"";
+        } else {
+            return "\"" + escaped + "\"";
+        }
+    }
+
+    private String snakeCase(String identifier) {
+        return identifier.replaceAll("([A-Z]+)|([0-9]+)", "_$0").toLowerCase();
+    }
+}