Add tokeniser

12 files changed, 316 insertions, 0 deletions

diff --git a/src/main/java/org/shedlang/compiler/errors/CompilerError.java b/src/main/java/org/shedlang/compiler/errors/CompilerError.java
new file mode 100644
index 00000000..edfd9262
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/errors/CompilerError.java
@@ -0,0 +1,7 @@
+package org.shedlang.compiler.errors;
+
+public class CompilerError extends RuntimeException {
+    public CompilerError(String message) {
+        super(message);
+    }
+}
diff --git a/src/main/java/org/shedlang/compiler/errors/InternalCompilerError.java b/src/main/java/org/shedlang/compiler/errors/InternalCompilerError.java
new file mode 100644
index 00000000..8ef02b7b
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/errors/InternalCompilerError.java
@@ -0,0 +1,7 @@
+package org.shedlang.compiler.errors;
+
+public class InternalCompilerError extends CompilerError {
+    public InternalCompilerError(String message) {
+        super(message);
+    }
+}
diff --git a/src/main/java/org/shedlang/compiler/errors/SourceError.java b/src/main/java/org/shedlang/compiler/errors/SourceError.java
new file mode 100644
index 00000000..2dfac789
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/errors/SourceError.java
@@ -0,0 +1,16 @@
+package org.shedlang.compiler.errors;
+
+import org.shedlang.compiler.sources.Source;
+
+public class SourceError extends CompilerError {
+    private final Source source;
+
+    public SourceError(String message, Source source) {
+        super(message);
+        this.source = source;
+    }
+
+    public Source getSource() {
+        return source;
+    }
+}
diff --git a/src/main/java/org/shedlang/compiler/sources/FileFragmentSource.java b/src/main/java/org/shedlang/compiler/sources/FileFragmentSource.java
new file mode 100644
index 00000000..4fc8889a
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/sources/FileFragmentSource.java
@@ -0,0 +1,53 @@
+package org.shedlang.compiler.sources;
+
+record FileFragmentSource(
+    String filename,
+    String contents,
+    int characterIndexStart,
+    int characterIndexEnd
+) implements Source {
+    static FileFragmentSource file(String filename, String contents) {
+        return new FileFragmentSource(filename, contents, 0, contents.length());
+    }
+
+    @Override
+    public String describe() {
+        var lines = contents.split("\n");
+        var position = 0;
+
+        for (var lineIndex = 0; lineIndex < lines.length; lineIndex++) {
+            var line = lines[lineIndex];
+            var nextLinePosition = position + line.length() + 1;
+            if (nextLinePosition > characterIndexStart || nextLinePosition >= contents.length()) {
+                return context(
+                    line,
+                    lineIndex,
+                    characterIndexStart - position
+                );
+            }
+            position = nextLinePosition;
+        }
+        throw new RuntimeException("should be impossible (but evidently isn't)");
+    }
+
+    @Override
+    public Source at(int characterIndexStart, int characterIndexEnd) {
+        return new FileFragmentSource(
+            filename,
+            contents,
+            this.characterIndexStart + characterIndexStart,
+            // TODO: check this is less than characterIndexEnd
+            this.characterIndexStart + characterIndexEnd
+        );
+    }
+
+    public Source end() {
+        return at(contents.length(), contents.length());
+    }
+
+    private String context(String line, int lineIndex, int columnIndex) {
+        var lineNumber = lineIndex + 1;
+        var columnNumber = columnIndex + 1;
+        return filename + ":" + lineNumber + ":" + columnNumber + "\n" + line + "\n" + " ".repeat(columnIndex) + "^";
+    }
+}
diff --git a/src/main/java/org/shedlang/compiler/sources/NullSource.java b/src/main/java/org/shedlang/compiler/sources/NullSource.java
new file mode 100644
index 00000000..e4f0948f
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/sources/NullSource.java
@@ -0,0 +1,24 @@
+package org.shedlang.compiler.sources;
+
+class NullSource implements Source {
+    private NullSource() {
+
+    }
+
+    static final NullSource INSTANCE = new NullSource();
+
+    @Override
+    public String contents() {
+        return "";
+    }
+
+    @Override
+    public String describe() {
+        return "(null)";
+    }
+
+    @Override
+    public Source at(int characterIndexStart, int characterIndexEnd) {
+        return this;
+    }
+}
diff --git a/src/main/java/org/shedlang/compiler/sources/Source.java b/src/main/java/org/shedlang/compiler/sources/Source.java
new file mode 100644
index 00000000..b40f3b63
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/sources/Source.java
@@ -0,0 +1,7 @@
+package org.shedlang.compiler.sources;
+
+public interface Source {
+    String contents();
+    String describe();
+    Source at(int characterIndexStart, int characterIndexEnd);
+}
diff --git a/src/main/java/org/shedlang/compiler/sources/Sources.java b/src/main/java/org/shedlang/compiler/sources/Sources.java
new file mode 100644
index 00000000..c815d1e0
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/sources/Sources.java
@@ -0,0 +1,9 @@
+package org.shedlang.compiler.sources;
+
+public class Sources {
+    public static Source NULL = NullSource.INSTANCE;
+
+    public static Source file(String filename, String contents) {
+        return FileFragmentSource.file(filename, contents);
+    }
+}
diff --git a/src/main/java/org/shedlang/compiler/tokeniser/InfinitelyPaddedIterator.java b/src/main/java/org/shedlang/compiler/tokeniser/InfinitelyPaddedIterator.java
new file mode 100644
index 00000000..534020d9
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/tokeniser/InfinitelyPaddedIterator.java
@@ -0,0 +1,31 @@
+package org.shedlang.compiler.tokeniser;
+
+import java.util.List;
+
+public class InfinitelyPaddedIterator<T> {
+    private final List<T> elements;
+    private final T end;
+    private int index = 0;
+
+    public InfinitelyPaddedIterator(List<T> elements, T end) {
+        this.elements = elements;
+        this.end = end;
+    }
+
+    public T get() {
+        return get(0);
+    }
+
+    public T get(int offset) {
+        var index = this.index + offset;
+        if (index < elements.size()) {
+            return elements.get(index);
+        } else {
+            return end;
+        }
+    }
+
+    public void moveNext() {
+        index++;
+    }
+}
diff --git a/src/main/java/org/shedlang/compiler/tokeniser/RegexTokeniser.java b/src/main/java/org/shedlang/compiler/tokeniser/RegexTokeniser.java
new file mode 100644
index 00000000..942960a3
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/tokeniser/RegexTokeniser.java
@@ -0,0 +1,71 @@
+package org.shedlang.compiler.tokeniser;
+
+import org.shedlang.compiler.sources.Source;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.regex.Pattern;
+import java.util.stream.Collectors;
+import java.util.stream.IntStream;
+
+public class RegexTokeniser<T> {
+    public static <T> TokenRule<T> rule(T type, String regex) {
+        var pattern = Pattern.compile(regex);
+
+        if (pattern.matcher("").groupCount() != 0) {
+            throw new RuntimeException("regex cannot contain any groups");
+        }
+
+        return new TokenRule<T>(type, pattern);
+    }
+
+    public static class TokenRule<T> {
+        private final T type;
+        private final Pattern regex;
+
+        private TokenRule(T type, Pattern regex) {
+            this.type = type;
+            this.regex = regex;
+        }
+    }
+
+    private final Pattern pattern;
+    private final List<T> rules;
+
+    public RegexTokeniser(T unknown, List<TokenRule<T>> rules) {
+        var allRules = new ArrayList<>(rules);
+        allRules.add(rule(unknown, "."));
+
+        this.pattern = Pattern.compile(
+            allRules.stream()
+                .map(rule -> "(" + rule.regex.pattern() + ")")
+                .collect(Collectors.joining("|"))
+        );
+
+        this.rules = allRules.stream()
+            .map(rule -> rule.type)
+            .collect(Collectors.toList());
+    }
+
+    public List<Token<T>> tokenise(Source source) {
+        var matcher = pattern.matcher(source.contents());
+        var tokens = new ArrayList<Token<T>>();
+
+        while (matcher.lookingAt()) {
+            var groupIndex = IntStream.rangeClosed(1, this.rules.size())
+                .filter(index -> matcher.group(index) != null)
+                .findFirst()
+                .getAsInt();
+
+            var tokenType = this.rules.get(groupIndex - 1);
+            tokens.add(new Token<>(
+                source.at(matcher.regionStart(), matcher.end()),
+                tokenType,
+                matcher.group()
+            ));
+            matcher.region(matcher.end(), source.contents().length());
+        }
+
+        return tokens;
+    }
+}
diff --git a/src/main/java/org/shedlang/compiler/tokeniser/Token.java b/src/main/java/org/shedlang/compiler/tokeniser/Token.java
new file mode 100644
index 00000000..e79d89eb
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/tokeniser/Token.java
@@ -0,0 +1,13 @@
+package org.shedlang.compiler.tokeniser;
+
+import org.shedlang.compiler.sources.Source;
+
+public record Token<T>(Source source, T tokenType, String value) {
+    public static <T> Token<T> token(Source source, T tokenType, String value) {
+        return new Token<T>(source, tokenType, value);
+    }
+
+    public String describe() {
+        return tokenType + ": " + value;
+    }
+}
diff --git a/src/main/java/org/shedlang/compiler/tokeniser/TokenIterator.java b/src/main/java/org/shedlang/compiler/tokeniser/TokenIterator.java
new file mode 100644
index 00000000..4133cc01
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/tokeniser/TokenIterator.java
@@ -0,0 +1,51 @@
+package org.shedlang.compiler.tokeniser;
+
+import java.util.List;
+
+public class TokenIterator<TTokenType> {
+    private final InfinitelyPaddedIterator<Token<TTokenType>> tokens;
+
+    public TokenIterator(List<Token<TTokenType>> tokens, Token<TTokenType> end) {
+        this.tokens = new InfinitelyPaddedIterator<>(tokens, end);
+    }
+
+    public void skip(TTokenType tokenType) {
+        nextValue(tokenType);
+    }
+
+    public String nextValue(TTokenType tokenType) {
+        var token = tokens.get();
+        if (token.tokenType().equals(tokenType)) {
+            tokens.moveNext();
+            return token.value();
+        } else {
+            throw new UnexpectedTokenException(
+                tokenType.toString(),
+                token.tokenType() + " \"" + token.value() + "\"",
+                token.source()
+            );
+        }
+    }
+
+    public boolean isNext(TTokenType tokenType) {
+        return tokens.get().tokenType().equals(tokenType);
+    }
+
+    public boolean isNext(TTokenType tokenType1, TTokenType tokenType2) {
+        return tokens.get().tokenType().equals(tokenType1) &&
+            tokens.get(1).tokenType().equals(tokenType2);
+    }
+
+    public boolean trySkip(TTokenType tokenType) {
+        if (isNext(tokenType)) {
+            tokens.moveNext();
+            return true;
+        } else {
+            return false;
+        }
+    }
+
+    public Token<TTokenType> peek() {
+        return tokens.get();
+    }
+}
diff --git a/src/main/java/org/shedlang/compiler/tokeniser/UnexpectedTokenException.java b/src/main/java/org/shedlang/compiler/tokeniser/UnexpectedTokenException.java
new file mode 100644
index 00000000..701f38e8
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/tokeniser/UnexpectedTokenException.java
@@ -0,0 +1,27 @@
+package org.shedlang.compiler.tokeniser;
+
+import org.shedlang.compiler.errors.SourceError;
+import org.shedlang.compiler.sources.Source;
+
+public class UnexpectedTokenException extends SourceError {
+    private final String expected;
+    private final String actual;
+
+    public UnexpectedTokenException(
+        String expected,
+        String actual,
+        Source source
+    ) {
+        super("Expected: " + expected + "\nBut got: " + actual, source);
+        this.expected = expected;
+        this.actual = actual;
+    }
+
+    public String getExpected() {
+        return expected;
+    }
+
+    public String getActual() {
+        return actual;
+    }
+}