diff options
| author | dibyendumajumdar <mobile@majumdar.org.uk> | 2023-08-25 23:16:07 +0100 |
|---|---|---|
| committer | dibyendumajumdar <mobile@majumdar.org.uk> | 2023-08-25 23:16:07 +0100 |
| commit | 9a2ab9bb803aa4da2a6007cc2e945d6bc1fe0b39 (patch) | |
| tree | 05dcb2c2b972538dba2da0429ba9705e09dc8e96 | |
| parent | b6098a9b9166da962676e33de31e93ace260d686 (diff) | |
| download | Simple-9a2ab9bb803aa4da2a6007cc2e945d6bc1fe0b39.tar.gz Simple-9a2ab9bb803aa4da2a6007cc2e945d6bc1fe0b39.zip | |
Reorganized the project as multi-maven module
Updated README
Added language module with grammar
Split the code into common and chapter01 modules.
Removed a number of utility classes that were imported from AA.
Added github workflow file.
38 files changed, 8892 insertions, 402 deletions
diff --git a/.github/workflows/maven.yml b/.github/workflows/maven.yml new file mode 100644 index 00000000..48ad1d91 --- /dev/null +++ b/.github/workflows/maven.yml @@ -0,0 +1,18 @@ +name: Java CI with Maven + +on: [push] + +jobs: + test: + + runs-on: ubuntu-latest + + steps: + - uses: actions/checkout@v3 + - name: Set up JDK 17 + uses: actions/setup-java@v3 + with: + java-version: '17' + distribution: 'temurin' + - name: Build with Maven + run: mvn --batch-mode --update-snapshots verify
\ No newline at end of file @@ -195,4 +195,7 @@ local.properties # Eclipse Core .project # JDT-specific (Eclipse Java Development Tools) -.classpath
\ No newline at end of file +.classpath + +.idea/* +*.iml
\ No newline at end of file @@ -2,9 +2,38 @@ A Simple showcase for the Sea-of-Nodes compiler IR This repo is intended to demonstrate the Sea-of-Nodes compiler IR. -The Sea-of-Nodes is the core IR inside of HotSpot's C2 compiler and Google's V8 compiler and Sun/Oracle's Graal compiler. + +The Sea-of-Nodes is the core IR inside of HotSpot's C2 compiler +and Google's V8 compiler and Sun/Oracle's Graal compiler. + Since we are show casing the SoN IR, the *language* being implemented is less important. We're using a very simple language similar to C or Java, but with far fewer features. -The Sea-of-Nodes is used for machine code generation in these industrial strength systems - but for this demonstration the backend is both difficult and less important. -This repo also is not intended to be a complete language in any sense, and so the backend will probably start with levering C or Java. +The Sea-of-Nodes is used for machine code generation in these industrial +strength systems - but for this demonstration the backend is both difficult +and less important. + +This repo also is not intended to be a complete language in any sense, +and so the backend will probably start with levering C or Java. + +## Chapters + +The following is a rough plan, subject to change. + +The Common chapter defines code that will be reused throughout. + +The remaining chapters will each be self-sufficient and complete; in the sense that each chapter will fully implement +a subset of the simple language. Each chapter will also include a detailed commentary on relevant aspects of the +Sea Of Nodes intermediate representation. + +The simple language will be a small subset of C. +* [Common](common/README.md): Common utilities including a lexer. +* [Language](language/README.md): definition. +* [Chapter 1](chapter01/README.md): Simple control flow statements, `if` and `while`. Variables of `int` type. Simple + arithmetic such as addition, subtraction, multiplication, division. Non-zero values will be truthy. +* Chapter 2: Function calls. +* Chapter 3: Comparison operators. +* Chapter 4: Boolean operators `&&`, `||` and `!`. +* Chapter 5: `float` and one dimensional static length array type. +* Chapter 6: Visualize Sea of Nodes IR. +* Chapter 7: Optimizations - tbc
\ No newline at end of file diff --git a/chapter01/README.md b/chapter01/README.md new file mode 100644 index 00000000..e69de29b --- /dev/null +++ b/chapter01/README.md diff --git a/chapter01/docs/01-grammar.md b/chapter01/docs/01-grammar.md new file mode 100644 index 00000000..e69de29b --- /dev/null +++ b/chapter01/docs/01-grammar.md diff --git a/chapter01/pom.xml b/chapter01/pom.xml new file mode 100644 index 00000000..842e67e9 --- /dev/null +++ b/chapter01/pom.xml @@ -0,0 +1,22 @@ +<?xml version="1.0" encoding="UTF-8"?> +<project xmlns="http://maven.apache.org/POM/4.0.0" + xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" + xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"> + <modelVersion>4.0.0</modelVersion> + <parent> + <groupId>com.seaofnodes</groupId> + <artifactId>simple</artifactId> + <version>1.0</version> + </parent> + <artifactId>chapter01</artifactId> + <packaging>jar</packaging> + <name>Chapter 1</name> + + <dependencies> + <dependency> + <groupId>com.seaofnodes</groupId> + <artifactId>common</artifactId> + <version>1.0</version> + </dependency> + </dependencies> +</project>
\ No newline at end of file diff --git a/src/main/java/com/seaofnodes/simple/parser/Ast.java b/chapter01/src/main/java/com/seaofnodes/simple/parser/Ast.java index a93b230f..a93b230f 100644 --- a/src/main/java/com/seaofnodes/simple/parser/Ast.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/parser/Ast.java diff --git a/src/main/java/com/seaofnodes/simple/parser/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/parser/Parser.java index f7b29f40..b36942d4 100644 --- a/src/main/java/com/seaofnodes/simple/parser/Parser.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/parser/Parser.java @@ -19,7 +19,7 @@ package com.seaofnodes.simple.parser; import com.seaofnodes.simple.common.CompilerException; import com.seaofnodes.simple.lexer.ecstasy.Lexer; import com.seaofnodes.simple.lexer.ecstasy.Token; -import com.seaofnodes.util.Severity; +import com.seaofnodes.simple.common.Severity; public class Parser { final Lexer lexer; diff --git a/src/test/java/com/seaofnodes/simple/lexer/TestParser.java b/chapter01/src/test/java/com/seaofnodes/simple/lexer/TestParser.java index 7d2f3752..a89c1f6a 100644 --- a/src/test/java/com/seaofnodes/simple/lexer/TestParser.java +++ b/chapter01/src/test/java/com/seaofnodes/simple/lexer/TestParser.java @@ -20,8 +20,8 @@ import com.seaofnodes.simple.lexer.ecstasy.Lexer; import com.seaofnodes.simple.lexer.ecstasy.Source; import com.seaofnodes.simple.parser.Ast; import com.seaofnodes.simple.parser.Parser; -import org.junit.jupiter.api.Assertions; -import org.junit.jupiter.api.Test; +import org.junit.Assert; +import org.junit.Test; public class TestParser { @@ -32,7 +32,7 @@ public class TestParser { Lexer lexer = new Lexer(new Source(source), new ErrorListener()); Parser parser = new Parser(lexer); var ast = parser.parse(); - Assertions.assertTrue(ast instanceof Ast.Block + Assert.assertTrue(ast instanceof Ast.Block && ((Ast.Block) ast).stmtList.size() == 1); } @@ -42,7 +42,7 @@ public class TestParser { Lexer lexer = new Lexer(new Source(source), new ErrorListener()); Parser parser = new Parser(lexer); var ast = parser.parse(); - Assertions.assertTrue(ast instanceof Ast.Block + Assert.assertTrue(ast instanceof Ast.Block && ((Ast.Block) ast).stmtList.size() == 2); } diff --git a/common/README.md b/common/README.md new file mode 100644 index 00000000..d6a5dbb8 --- /dev/null +++ b/common/README.md @@ -0,0 +1,7 @@ +# Common Utilities + +In this module certain common utilities are defined that +will be reused throughout the project. + +* Lexer - the lexer is based upon the one in Ecstasy Programming Language. Its feature rich enough that we do not + expect to have to modify it much.
\ No newline at end of file diff --git a/common/pom.xml b/common/pom.xml new file mode 100644 index 00000000..e70fcf1d --- /dev/null +++ b/common/pom.xml @@ -0,0 +1,14 @@ +<?xml version="1.0" encoding="UTF-8"?> +<project xmlns="http://maven.apache.org/POM/4.0.0" + xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" + xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"> + <modelVersion>4.0.0</modelVersion> + <parent> + <groupId>com.seaofnodes</groupId> + <artifactId>simple</artifactId> + <version>1.0</version> + </parent> + <artifactId>common</artifactId> + <packaging>jar</packaging> + <name>Common Stuff</name> +</project>
\ No newline at end of file diff --git a/src/main/java/com/seaofnodes/simple/common/CompilerException.java b/common/src/main/java/com/seaofnodes/simple/common/CompilerException.java index 518dcde6..518dcde6 100644 --- a/src/main/java/com/seaofnodes/simple/common/CompilerException.java +++ b/common/src/main/java/com/seaofnodes/simple/common/CompilerException.java diff --git a/common/src/main/java/com/seaofnodes/simple/common/ErrorListener.java b/common/src/main/java/com/seaofnodes/simple/common/ErrorListener.java new file mode 100644 index 00000000..29ca46b6 --- /dev/null +++ b/common/src/main/java/com/seaofnodes/simple/common/ErrorListener.java @@ -0,0 +1,266 @@ +package com.seaofnodes.simple.common; + +import java.text.MessageFormat; + +import java.util.Arrays; + +import com.seaofnodes.simple.lexer.ecstasy.Source; + +import static com.seaofnodes.util.Handy.quotedString; + + +/** + * A listener for errors being reported about source code, compilation, assembly, or verification of + * XVM structures. + */ +public class ErrorListener + { + // ----- API ----------------------------------------------------------------------------------- + + /** + * Handles the logging of an error that originates in Ecstasy source code. + * + * @param severity the severity level of the error; one of + * {@link Severity#INFO}, {@link Severity#WARNING}, + * {@link Severity#ERROR}, or {@link Severity#FATAL} + * @param sCode the error code that identifies the error message + * @param aoParam the parameters for the error message; may be null + * @param source the source code (optional) + * @param lPosStart the position in the source where the error was detected + * @param lPosEnd the position in the source at which the error concluded + * + * @return true to attempt to abort the process that reported the error, or + * false to attempt to continue the process + */ + public void log(Severity severity, String sCode, Object[] aoParam, + Source source, long lPosStart, long lPosEnd) + { + System.err.println(new ErrorInfo(severity, sCode, aoParam, source, lPosStart, lPosEnd)); + } + + + // ----- inner class: ErrorInfo ---------------------------------------------------------------- + + /** + * Represents the information logged for a single error. + */ + class ErrorInfo + { + /** + * Construct an ErrorInfo object. + * + * @param severity the severity level of the error; one of + * {@link Severity#INFO}, {@link Severity#WARNING, + * {@link Severity#ERROR}, or {@link Severity#FATAL} + * @param sCode the error code that identifies the error message + * @param aoParam the parameters for the error message; may be null + * @param source the source code + * @param lPosStart the starting position in the source code + * @param lPosEnd the ending position in the source code + */ + public ErrorInfo(Severity severity, String sCode, Object[] aoParam, + Source source, long lPosStart, long lPosEnd) + { + m_severity = severity; + m_sCode = sCode; + m_aoParam = aoParam; + m_source = source; + m_lPosStart = lPosStart; + m_lPosEnd = lPosEnd; + } + + /** + * Construct an ErrorInfo object. + * + * @param severity the severity level of the error; one of + * {@link Severity#INFO}, {@link Severity#WARNING, + * {@link Severity#ERROR}, or {@link Severity#FATAL} + * @param sCode the error code that identifies the error message + * @param aoParam the parameters for the error message; may be null + */ + public ErrorInfo(Severity severity, String sCode, Object[] aoParam) + { + m_severity = severity; + m_sCode = sCode; + m_aoParam = aoParam; + // TODO need to be able to ask the XVM structure for the source & location + } + + /** + * @return the Severity of the error + */ + public Severity getSeverity() + { + return m_severity; + } + + /** + * @return the error code + */ + public String getCode() + { + return m_sCode; + } + + /** + * @return the error message parameters + */ + public Object[] getParams() + { + return m_aoParam; + } + + /** + * Produce a localized message based on the error code and related parameters. + * + * @return a formatted message for display that includes the error code + */ + public String getMessage() + { + return getMessageText(); + } + + /** + * Produce a localized message based on the error code and related parameters. + * + * @return a formatted message for display that doesn't include the error code + */ + public String getMessageText() + { + return MessageFormat.format(getCode(), getParams()); + } + + /** + * @return the source code + */ + public Source getSource() + { + return m_source; + } + + /** + * @return the line number (zero based) at which the error occurred + */ + public int getLine() + { + return Source.calculateLine(m_lPosStart); + } + + /** + * @return the offset (zero based) at which the error occurred + */ + public int getOffset() + { + return Source.calculateOffset(m_lPosStart); + } + + /** + * @return the line number (zero based) at which the error concluded + */ + public int getEndLine() + { + return Source.calculateLine(m_lPosEnd); + } + + /** + * @return the offset (zero based) at which the error concluded + */ + public int getEndOffset() + { + return Source.calculateOffset(m_lPosEnd); + } + + /** + * @return an ID that allows redundant errors to be filtered out + */ + public String genUID() + { + StringBuilder sb = new StringBuilder(); + sb.append(m_severity.ordinal()) + .append(':') + .append(m_sCode); + + if (m_aoParam != null) + { + sb.append('#') + .append(Arrays.hashCode(m_aoParam)); + } + + if (!m_sCode.startsWith("VERIFY")) + { + if (m_source != null) + { + sb.append(':') + .append(m_source.getFileName()) + .append(':') + .append(m_lPosStart) + .append(':') + .append(m_lPosStart); + } + } + + return sb.toString(); + } + + @Override + public String toString() + { + StringBuilder sb = new StringBuilder(); + + // source code location + if (m_source != null) + { + String sFile = m_source.getFileName(); + if (sFile != null) + { + sb.append(sFile) + .append(':').append(getLine() + 1) + .append(' '); + } + + sb.append("[") + .append(getLine() + 1) + .append(':') + .append(getOffset() + 1); + + if (getEndLine() != getLine() || getEndOffset() != getOffset()) + { + sb.append("..") + .append(getEndLine() + 1) + .append(':') + .append(getEndOffset() + 1); + } + + sb.append("] "); + } + + + // localized message + sb.append(getMessage()); + + // source code snippet + if (m_source != null && m_lPosStart != m_lPosEnd) + { + String sSource = m_source.toString(m_lPosStart, m_lPosEnd); + if (sSource.length() > 80) + { + sSource = sSource.substring(0, 77) + "..."; + } + + sb.append(" (") + .append(quotedString(sSource)) + .append(')'); + } + + return sb.toString(); + } + + private final Severity m_severity; + private final String m_sCode; + private final Object[] m_aoParam; + private Source m_source; + private long m_lPosStart; + private long m_lPosEnd; + } + + }
\ No newline at end of file diff --git a/common/src/main/java/com/seaofnodes/simple/common/Severity.java b/common/src/main/java/com/seaofnodes/simple/common/Severity.java new file mode 100644 index 00000000..f3325d52 --- /dev/null +++ b/common/src/main/java/com/seaofnodes/simple/common/Severity.java @@ -0,0 +1,19 @@ +package com.seaofnodes.simple.common; + + +/** + * Severity levels. + */ +public enum Severity + { + NONE, INFO, WARNING, ERROR, FATAL; + + public String desc() + { + String sName = name(); + StringBuilder sb = new StringBuilder(sName.length()); + sb.append(sName.charAt(0)); + sb.append(sName.substring(1).toLowerCase()); + return sb.toString(); + } + } diff --git a/src/main/java/com/seaofnodes/simple/lexer/aa/Lexer.java b/common/src/main/java/com/seaofnodes/simple/lexer/aa/Lexer.java index 162cdea1..162cdea1 100644 --- a/src/main/java/com/seaofnodes/simple/lexer/aa/Lexer.java +++ b/common/src/main/java/com/seaofnodes/simple/lexer/aa/Lexer.java diff --git a/common/src/main/java/com/seaofnodes/simple/lexer/ecstasy/Lexer.java b/common/src/main/java/com/seaofnodes/simple/lexer/ecstasy/Lexer.java new file mode 100644 index 00000000..90571ffd --- /dev/null +++ b/common/src/main/java/com/seaofnodes/simple/lexer/ecstasy/Lexer.java @@ -0,0 +1,3041 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is + * The Ecstasy Project (https://github.com/xtclang/). + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ +package com.seaofnodes.simple.lexer.ecstasy; + +import java.math.BigDecimal; +import java.math.BigInteger; + +import java.net.IDN; + +import java.util.ArrayList; +import java.util.Iterator; +import java.util.NoSuchElementException; + +import java.util.function.Consumer; + +import com.seaofnodes.simple.common.ErrorListener; +import com.seaofnodes.simple.lexer.ecstasy.Token.Id; +import com.seaofnodes.util.PackedInteger; +import com.seaofnodes.simple.common.Severity; + +import static com.seaofnodes.util.Handy.*; + +/** + * An XTC source code parser supporting both demand-based and stream-based + * parsing. + */ +public class Lexer + implements Iterator<Token> + { + // ----- constructors -------------------------------------------------------------------------- + + /** + * Construct an XTC lexical analyzer. + * + * @param source the source to parse + */ + public Lexer(Source source, ErrorListener errorListener) + { + if (source == null) + { + throw new IllegalArgumentException("Source required"); + } + if (errorListener == null) + { + throw new IllegalArgumentException("ErrorListener required"); + } + + m_source = source; + m_errorListener = errorListener; + + eatWhitespace(); + } + + /** + * @param parent a Lexer that this Lexer can delegate to + */ + protected Lexer(Lexer parent) + { + m_source = parent.m_source; + m_errorListener = parent.m_errorListener; + m_fWhitespace = parent.m_fWhitespace; + } + + + // ----- Iterator methods ---------------------------------------------------------------------- + + @Override + public boolean hasNext() + { + return m_source.hasNext(); + } + + /** + * Validate the specified identifier. + * + * @param sName the identifier + * + * @return true iff the identifier is a lexically valid identifier + */ + public static boolean isValidIdentifier(String sName) + { + if (sName == null) + { + return false; + } + + int cch = sName.length(); + if (cch == 0) + { + return false; + } + + if (!isIdentifierStart(sName.charAt(0))) + { + return false; + } + + for (int i = 1; i < cch; ++i) + { + if (!isIdentifierPart(sName.charAt(i))) + { + return false; + } + } + + // check if it is a reserved word + return Id.valueByText(sName) == null; + } + + + // ----- public API ---------------------------------------------------------------------------- + + /** + * Lexically analyze the source, emitting a stream of tokens to the specified consumer. + * + * @param consumer the Token Consumer + */ + public void emit(Consumer<Token> consumer) + { + while (m_source.hasNext()) + { + consumer.accept(next()); + } + } + + /** + * Create a temporary lexer that provides a stream of tokens as specified. + * + * @param atoken the tokens to stream + * + * @return a new Lexer + */ + public Lexer createLexer(Token[] atoken) + { + return new Lexer(this) + { + int iNext = 0; + + @Override + public boolean hasNext() + { + return iNext < atoken.length; + } + + @Override + public Token next() + { + if (hasNext()) + { + return atoken[iNext++]; + } + throw new NoSuchElementException(); + } + + @Override + public long mark() + { + return iNext; + } + + @Override + public void restore(long lPos) + { + iNext = (int) lPos; + } + }; + } + + + // ----- internal ------------------------------------------------------------------------------ + + /** + * Validate the specified RFC1035 label. + * + * @param sName the RFC1035 label + * + * @return true iff the name is a lexically valid RFC1035 label + */ + public static boolean isValidRFC1035Label(String sName) + { + if (sName == null) + { + return false; + } + + // internationalization support; see https://tools.ietf.org/html/rfc5894 + // convert the label to an ASCII label + try + { + sName = IDN.toASCII(sName); + } + catch (IllegalArgumentException e) + { + return false; + } + + int cch = sName.length(); + if (cch == 0 || cch > 63) + { + return false; + } + + if (!isAsciiLetter(sName.charAt(0))) + { + return false; + } + + for (int i = 1; i < cch; ++i) + { + char ch = sName.charAt(i); + if (!(isAsciiLetter(ch) || isDigit(ch) || i < cch - 1 && ch == '-')) + { + return false; + } + } + + return true; + } + + /** + * Validate the specified module name. + * + * @param sName the module name + * + * @return true iff the name is a lexically valid qualified module name + */ + public static boolean isValidQualifiedModule(String sName) + { + if (sName == null) + { + return false; + } + + String[] asName = parseDelimitedString(sName, '.'); + int cNames = asName.length; + if (cNames < 1) + { + return false; + } + + // the first simple name must be a valid identifier + if (!isValidIdentifier(asName[0])) + { + return false; + } + + // the identifier must be followed by a domain name, which is composed of at least two + // RFC1035 labels + if (cNames == 2) + { + return false; + } + + // check the optional domain name + for (int i = 1; i < cNames; ++i) + { + if (!isValidRFC1035Label(asName[i])) + { + return false; + } + } + + return true; + } + + @Override + public Token next() + { + boolean fWhitespaceBefore = m_fWhitespace; + Token token = eatToken(); + boolean fWhitespaceAfter = eatWhitespace(); + token.noteWhitespace(fWhitespaceBefore, fWhitespaceAfter); + return token; + } + + /** + * Eat a string literal. + * + * @return a string literal as a token + */ + protected Token eatStringLiteral(long lInitPos) + { + return eatStringChars(lInitPos, false, false); + } + + /** + * Eat a string literal that is in the freeform/multi-line form. + * + * @return a string literal as a token + */ + protected Token eatMultilineLiteral(long lInitPos) + { + return eatStringChars(lInitPos, false, true); + } + + /** + * Eat a template literal. A template literal is a string literal that may contain expressions; + * for example: + * <blockquote><code><pre> + * $"x={x}" + * </pre></code></blockquote> + * + * @param lInitPos the start of the template literal + * + * @return the resulting token + */ + protected Token eatTemplateLiteral(long lInitPos) + { + return eatStringChars(lInitPos, true, false); + } + + /** + * Eat a template literal that uses the multi-line format. A template literal is a string + * literal that may contain expressions; for example: + * <blockquote><code><pre> + * $|# TOML doc + * |[name] + * |first = "{person.firstname}" + * |last = "{person.lastname}" + * </pre></code></blockquote> + * + * @param lInitPos the start of the template literal + * + * @return the resulting token + */ + protected Token eatMultilineTemplateLiteral(long lInitPos) + { + return eatStringChars(lInitPos, true, true); + } + + /** + * Eat the characters defined as whitespace, which include line terminators and the file + * terminator. Whitespace does not include comments. + */ + protected boolean eatWhitespace() + { + boolean fWhitespace = false; + Source source = m_source; + while (source.hasNext()) + { + if (isWhitespace(nextChar())) + { + fWhitespace = true; + } + else + { + // put back the non-whitespace character + source.rewind(); + break; + } + } + m_fWhitespace = fWhitespace; + return fWhitespace; + } + + protected boolean isMultilineContinued() + { + long lPrev = mark(); + Source source = m_source; + while (source.hasNext()) + { + char ch = source.next(); + if (!isWhitespace(ch)) + { + if (ch == '|') + { + return true; + } + break; + } + } + + restore(lPrev); + return false; + } + + /** + * Eat an inline template expression that begins with a '{' and ends with a '}'. The contents + * <b>between</b> the opening and closing curlies are returned as an array of tokens. + * + * @param fMultiline true iff this is a multi-line format + * + * @return the tokens found between the opening and closing curly braces + */ + protected Token[] eatTemplateExpression(boolean fMultiline) + { + int nPrevLine = m_source.getLine(); + long lInitPos = m_source.getPosition(); + expect('{'); + long lPrevPos = mark(); + int cDepth = 1; + ArrayList<Token> tokens = new ArrayList<>(); + while (true) + { + Token token = next(); + int nLine = Source.calculateLine(token.getEndPosition()); + if (nLine != nPrevLine) + { + if (!fMultiline || token.getId() != Id.BIT_OR + || Source.calculateLine(token.getStartPosition()) != nLine) + { + // either it's not a multi-line literal, or the new line doesn't start with '|', + // or a token crosses a line boundary; log error: newline in string + restore(lPrevPos); + log(Severity.ERROR, STRING_NO_TERM, null, lInitPos); + return tokens.toArray(new Token[0]); + } + + nPrevLine = nLine; + continue; // skip this '|' token + } + + switch (token.getId()) + { + case L_CURLY: + ++cDepth; + break; + + case R_CURLY: + if (--cDepth <= 0) + { + if (token.hasTrailingWhitespace()) + { + // don't steal the whitespace; we're inside a literal! + m_source.setPosition(token.getEndPosition()); + } + + return tokens.toArray(new Token[0]); + } + break; + } + + tokens.add(token); + lPrevPos = mark(); + } + } + + /** + * Parse the binary literal value. + * + * @param lInitPos the location of the "#" at the start of the binary literal value + * @param fMultiline true iff the format is a multiline format + * + * @return the binary literal + */ + protected Token eatBinaryLiteral(long lInitPos, boolean fMultiline) + { + StringBuilder sb = new StringBuilder(); + Source source = m_source; + boolean fFirst = true; + while (source.hasNext()) + { + char ch = source.next(); + if (isHexit(ch)) + { + sb.append(ch); + } + else if (ch == '_') + { + if (fFirst) + { + // it's an error to start with an underscore + log(Severity.ERROR, ILLEGAL_HEX, new Object[] {String.valueOf(ch)}, lInitPos); + } + // ignore the _ (it's used for spacing within the literal) + } + else if (!fMultiline) + { + // the first non-hexit / non-underscore character indicates an end-of-value + source.rewind(); + break; + } + else if (isWhitespace(ch)) + { + // ignore whitespace, unless it's newline + if (isLineTerminator(ch) && !isMultilineContinued()) + { + source.rewind(); + break; + } + } + else + { + // error + log(Severity.ERROR, ILLEGAL_HEX, new Object[] {String.valueOf(ch)}, lInitPos); + source.rewind(); + break; + } + + fFirst = false; + } + + return new Token(lInitPos, source.getPosition(), Id.LIT_BINSTR, + toBinary(sb.toString().toCharArray())); + } + + protected byte[] toBinary(char[] ach) + { + int cch = ach.length; + int ofch = 0; + int cb = (cch + 1) / 2; + int ofb = 0; + byte[] ab = new byte[cb]; + if ((cch & 0x1) != 0) + { + // odd number of characters means that the first nibble is a pre-pended zero + ab[ofb++] = (byte) hexitValue(ach[ofch++]); + } + while (ofb < cb) + { + ab[ofb++] = (byte) ( (hexitValue(ach[ofch++]) << 4) + + hexitValue(ach[ofch++]) ); + } + + return ab; + } + + /** + * Parse a single token. + * + * @return the next Token + */ + protected Token eatToken() + { + Source source = m_source; + long lInitPos = source.getPosition(); + char chInit = nextChar(); + + switch (chInit) + { + case '{': + return new Token(lInitPos, source.getPosition(), Id.L_CURLY); + case '}': + return new Token(lInitPos, source.getPosition(), Id.R_CURLY); + case '(': + return new Token(lInitPos, source.getPosition(), Id.L_PAREN); + case ')': + return new Token(lInitPos, source.getPosition(), Id.R_PAREN); + case '[': + return new Token(lInitPos, source.getPosition(), Id.L_SQUARE); + case ']': + return new Token(lInitPos, source.getPosition(), Id.R_SQUARE); + + case ';': + return new Token(lInitPos, source.getPosition(), Id.SEMICOLON); + case ',': + return new Token(lInitPos, source.getPosition(), Id.COMMA); + + case '.': + if (source.hasNext()) + { + switch (nextChar()) + { + case '.': + if (source.hasNext()) + { + switch (nextChar()) + { + case '/': + return new Token(lInitPos, source.getPosition(), Id.DIR_PARENT); + + case '<': + return new Token(lInitPos, source.getPosition(), Id.I_RANGE_E); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.I_RANGE_I); + + case '/': + return new Token(lInitPos, source.getPosition(), Id.DIR_CUR); + + case '0': case '1': case '2': case '3': case '4': + case '5': case '6': case '7': case '8': case '9': + source.rewind(); + source.rewind(); + return eatNumericLiteral(); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.DOT); + + case '$': + if (source.hasNext()) + { + switch (nextChar()) + { + case '\"': + return eatTemplateLiteral(lInitPos); + + case '|': + return eatMultilineTemplateLiteral(lInitPos); + + case '/': + // it is a file name + source.rewind(); + return new Token(lInitPos, source.getPosition(), Id.STR_FILE); + + case '.': + if (source.hasNext()) + { + switch (nextChar()) + { + case '.': + if (source.hasNext()) + { + if (nextChar() == '/') + { + // it is a file name starting with "../" + source.rewind(); + source.rewind(); + source.rewind(); + return new Token(lInitPos, source.getPosition(), Id.STR_FILE); + } + + source.rewind(); + } + break; + + case '/': + // it is a file name starting with "./" + source.rewind(); + source.rewind(); + return new Token(lInitPos, source.getPosition(), Id.STR_FILE); + } + + source.rewind(); + } + break; + } + + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.IDENTIFIER, "$"); + + case '#': + if (source.hasNext()) + { + switch (nextChar()) + { + case '.': + case '/': + // it is a file name + source.rewind(); + return new Token(lInitPos, source.getPosition(), Id.BIN_FILE); + + case '|': + return eatBinaryLiteral(lInitPos, true); + + default: + // fall through (it will be an error) + case '0': case '1': case '2': case '3': case '4': + case '5': case '6': case '7': case '8': case '9': + case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': + case 'A': case 'B': case 'C': case 'D': case 'E': case 'F': + source.rewind(); + // fall through + } + } + return eatBinaryLiteral(lInitPos, false); + + case '@': + return new Token(lInitPos, source.getPosition(), Id.AT); + + case '?': + if (source.hasNext()) + { + switch (nextChar()) + { + case '=': + return new Token(lInitPos, source.getPosition(), Id.COND_NN_ASN); + + case ':': + if (source.hasNext()) + { + if (nextChar() == '=') + { + return new Token(lInitPos, source.getPosition(), Id.COND_ELSE_ASN); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.COND_ELSE); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.COND); + + case ':': + if (source.hasNext()) + { + if (nextChar() == '=') + { + return new Token(lInitPos, source.getPosition(), Id.COND_ASN); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.COLON); + + case '+': + if (source.hasNext()) + { + switch (nextChar()) + { + case '+': + return new Token(lInitPos, source.getPosition(), Id.INC); + + case '=': + return new Token(lInitPos, source.getPosition(), Id.ADD_ASN); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.ADD); + + case '-': + if (source.hasNext()) + { + switch (nextChar()) + { + case '-': + return new Token(lInitPos, source.getPosition(), Id.DEC); + + case '>': + return new Token(lInitPos, source.getPosition(), Id.LAMBDA); + + case '=': + return new Token(lInitPos, source.getPosition(), Id.SUB_ASN); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.SUB); + + case '*': + if (source.hasNext()) + { + if (nextChar() == '=') + { + return new Token(lInitPos, source.getPosition(), Id.MUL_ASN); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.MUL); + + case '/': + if (source.hasNext()) + { + switch (nextChar()) + { + case '/': + return eatSingleLineComment(lInitPos); + + case '*': + return eatEnclosedComment(lInitPos); + + case '=': + return new Token(lInitPos, source.getPosition(), Id.DIV_ASN); + + case '%': + return new Token(lInitPos, source.getPosition(), Id.DIVREM); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.DIV); + + case '<': + if (source.hasNext()) + { + switch (nextChar()) + { + case '<': + if (source.hasNext()) + { + if (nextChar() == '=') + { + return new Token(lInitPos, source.getPosition(), Id.SHL_ASN); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.SHL); + + case '-': + return new Token(lInitPos, source.getPosition(), Id.ASN_EXPR); + + case '=': + if (source.hasNext()) + { + if (nextChar() == '>') + { + return new Token(lInitPos, source.getPosition(), Id.COMP_ORD); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.COMP_LTEQ); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.COMP_LT); + + case '>': + if (source.hasNext()) + { + switch (nextChar()) + { + case '>': + if (source.hasNext()) + { + switch (nextChar()) + { + case '>': + if (source.hasNext()) + { + if (nextChar() == '=') + { + return new Token(lInitPos, source.getPosition(), Id.USHR_ASN); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.USHR); + + case '=': + return new Token(lInitPos, source.getPosition(), Id.SHR_ASN); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.SHR); + + case '.': + if (source.hasNext()) + { + if (nextChar() == '.') + { + if (source.hasNext()) + { + if (nextChar() == '<') + { + return new Token(lInitPos, source.getPosition(), Id.E_RANGE_E); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.E_RANGE_I); + } + source.rewind(); + } + break; + + case '=': + return new Token(lInitPos, source.getPosition(), Id.COMP_GTEQ); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.COMP_GT); + + case '&': + if (source.hasNext()) + { + switch (nextChar()) + { + case '&': + if (source.hasNext()) + { + if (nextChar() == '=') + { + return new Token(lInitPos, source.getPosition(), Id.COND_AND_ASN); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.COND_AND); + + case '=': + return new Token(lInitPos, source.getPosition(), Id.BIT_AND_ASN); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.BIT_AND); + + case '|': + if (source.hasNext()) + { + switch (nextChar()) + { + case '|': + if (source.hasNext()) + { + if (nextChar() == '=') + { + return new Token(lInitPos, source.getPosition(), Id.COND_OR_ASN); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.COND_OR); + + case '=': + return new Token(lInitPos, source.getPosition(), Id.BIT_OR_ASN); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.BIT_OR); + + case '=': + if (source.hasNext()) + { + if (nextChar() == '=') + { + return new Token(lInitPos, source.getPosition(), Id.COMP_EQ); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.ASN); + + case '%': + if (source.hasNext()) + { + if (nextChar() == '=') + { + return new Token(lInitPos, source.getPosition(), Id.MOD_ASN); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.MOD); + + case '!': + if (source.hasNext()) + { + if (nextChar() == '=') + { + return new Token(lInitPos, source.getPosition(), Id.COMP_NEQ); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.NOT); + + case '^': + if (source.hasNext()) + { + switch (nextChar()) + { + case '^': + return new Token(lInitPos, source.getPosition(), Id.COND_XOR); + + case '=': + return new Token(lInitPos, source.getPosition(), Id.BIT_XOR_ASN); + + case '(': + return new Token(lInitPos, source.getPosition(), Id.ASYNC_PAREN); + } + source.rewind(); + } + return new Token(lInitPos, source.getPosition(), Id.BIT_XOR); + + case '~': + return new Token(lInitPos, source.getPosition(), Id.BIT_NOT); + + case '0': case '1': case '2': case '3': case '4': + case '5': case '6': case '7': case '8': case '9': + source.rewind(); + return eatNumericLiteral(); + + case '\'': + return eatCharLiteral(lInitPos); + + case '\"': + return eatStringLiteral(lInitPos); + + case '\\': + if (source.hasNext()) + { + if (nextChar() == '|') + { + return eatMultilineLiteral(lInitPos); + } + source.rewind(); + } + // fall through + + default: + if (!isIdentifierStart(chInit)) + { + log(Severity.ERROR, ILLEGAL_CHAR, new Object[]{quotedChar(chInit)}, lInitPos); + } + // fall through + case 'A':case 'B':case 'C':case 'D':case 'E':case 'F':case 'G': + case 'H':case 'I':case 'J':case 'K':case 'L':case 'M':case 'N': + case 'O':case 'P':case 'Q':case 'R':case 'S':case 'T':case 'U': + case 'V':case 'W':case 'X':case 'Y':case 'Z': + case 'a':case 'b':case 'c':case 'd':case 'e':case 'f':case 'g': + case 'h':case 'i':case 'j':case 'k':case 'l':case 'm':case 'n': + case 'o':case 'p':case 'q':case 'r':case 's':case 't':case 'u': + case 'v':case 'w':case 'x':case 'y':case 'z': + case '_': + { + while (source.hasNext()) + { + if (!isIdentifierPart(nextChar())) + { + source.rewind(); + break; + } + } + + String name = extractSource(lInitPos); + long lPos = source.getPosition(); + if (source.hasNext()) + { + char chNext = source.next(); + if (name.equals(Id.TODO.TEXT)) + { + source.rewind(); + if (chNext == '(') + { + return new Token(lInitPos, source.getPosition(), Id.TODO, null); + } + else + { + // parse the to-do statement in the same manner as a single line comment + Token comment = eatSingleLineComment(lInitPos); + return new Token(comment.getStartPosition(), comment.getEndPosition(), + Id.TODO, comment.getValue()); + } + } + else if (chNext == ':') + { + if (Token.Id.valueByPrefix(name) != null) + { + // check for a legal suffix, e.g. "this:private" + while (source.hasNext()) + { + if (!isIdentifierPart(nextChar())) + { + source.rewind(); + break; + } + } + + String full = extractSource(lInitPos); + if (Id.valueByContextSensitiveText(full) != null) + { + name = full; + } + else + { + // false alarm; back up and just take "this" + source.setPosition(lPos); + } + } + else + { + // check for suffix of private / protected / public / struct (etc.) + long lPosSuffix = source.getPosition(); + while (source.hasNext()) + { + if (!isIdentifierPart(nextChar())) + { + source.rewind(); + break; + } + } + String suffix = extractSource(lPosSuffix); + source.setPosition(lPosSuffix); // back up past the suffix + + Token.Id idNum = null; + boolean fFloat = false; + if (Id.valueByText(suffix) == null && source.hasNext() && !isWhitespace(peekChar())) + { + switch (name) + { + case "Bit": + idNum = Id.LIT_BIT; + break; + + case "Nibble": + idNum = Id.LIT_NIBBLE; + break; + + case "Int": + idNum = Id.LIT_INTA; + break; + case "Int8": + idNum = Id.LIT_INT8; + break; + case "Int16": + idNum = Id.LIT_INT16; + break; + case "Int32": + idNum = Id.LIT_INT32; + break; + case "Int64": + idNum = Id.LIT_INT64; + break; + case "Int128": + idNum = Id.LIT_INT128; + break; + case "IntN": + idNum = Id.LIT_INTN; + break; + + case "UInt": + idNum = Id.LIT_UINTA; + break; + case "Byte": + case "UInt8": + idNum = Id.LIT_UINT8; + break; + case "UInt16": + idNum = Id.LIT_UINT16; + break; + case "UInt32": + idNum = Id.LIT_UINT32; + break; + case "UInt64": + idNum = Id.LIT_UINT64; + break; + case "UInt128": + idNum = Id.LIT_UINT128; + break; + case "UIntN": + idNum = Id.LIT_UINTN; + break; + + case "Dec": + idNum = Id.LIT_DECA; + fFloat = true; + break; + case "Dec32": + idNum = Id.LIT_DEC32; + fFloat = true; + break; + case "Dec64": + idNum = Id.LIT_DEC64; + fFloat = true; + break; + case "Dec128": + idNum = Id.LIT_DEC128; + fFloat = true; + break; + case "DecN": + idNum = Id.LIT_DECN; + fFloat = true; + break; + + case "Float8e4": + idNum = Id.LIT_FLOAT8E4; + fFloat = true; + break; + case "Float8e5": + idNum = Id.LIT_FLOAT8E5; + fFloat = true; + break; + case "BFloat16": + idNum = Id.LIT_BFLOAT16; + fFloat = true; + break; + case "Float16": + idNum = Id.LIT_FLOAT16; + fFloat = true; + break; + case "Float32": + idNum = Id.LIT_FLOAT32; + fFloat = true; + break; + case "Float64": + idNum = Id.LIT_FLOAT64; + fFloat = true; + break; + case "Float128": + idNum = Id.LIT_FLOAT128; + fFloat = true; + break; + case "FloatN": + idNum = Id.LIT_FLOATN; + fFloat = true; + break; + + case "Date": + return eatDate(lInitPos, false); + case "TimeOfDay": + return eatTimeOfDay(lInitPos, false); + case "Time": + return eatTime(lInitPos); + case "TimeZone": + return eatTimeZone(lInitPos); + case "Duration": + return eatDuration(lInitPos); + + default: + source.rewind(); // back up past the ':' + } + + if (idNum != null) + { + Token tokNum = eatNumericLiteral(); + switch (tokNum.getId()) + { + case LIT_DEC: + case LIT_FLOAT: + if (!fFloat) + { + // we were expecting an integer + log(Severity.ERROR, ILLEGAL_NUMBER, new Object[] { + extractSource(lInitPos, tokNum.getEndPosition())}, + lInitPos); + return tokNum; + } + // fall through + case LIT_INT: + return tokNum.refine(idNum); + + default: + throw new IllegalStateException("id=" + idNum); + } + } + } + else + { + source.rewind(); // back up past the ':' + } + } + } + else + { + source.rewind(); + } + } + + Id id = Id.valueByText(name); + return new Token(lInitPos, source.getPosition(), id == null ? Id.IDENTIFIER : id, name); + } + } + } + + /** + * Eat a character literal. + * + * @return a character literal as a token + */ + protected Token eatCharLiteral(long lInitPos) + { + Source source = m_source; + long lPosChar = source.getPosition(); + + char ch = '?'; + boolean term = false; + if (source.hasNext()) + { + switch (ch = source.next()) + { + case '\'': + if (source.hasNext()) + { + if (source.next() == '\'') + { + // assume the previous one should have been escaped + source.rewind(); + log(Severity.ERROR, CHAR_BAD_ESC, null, lPosChar); + } + else + { + // assume the encountered quote that we thought was supposed to be + // the character value was instead supposed to be closing quote + source.rewind(); + source.rewind(); + log(Severity.ERROR, CHAR_NO_CHAR, null, lPosChar, lPosChar); + } + } + break; + + case '\\': + // process escaped char + switch (ch = source.next()) + { + case '\r': + case '\n': + case 0x000B: // VT Vertical Tab + case 0x000C: // FF Form Feed + case 0x0085: // NEL Next Line + case 0x2028: // LS Line Separator + case 0x2029: // PS Paragraph Separator + // log error: newline in string + source.rewind(); + log(Severity.ERROR, CHAR_NO_TERM, null, lInitPos); + // assume it wasn't supposed to be an escape + ch = '\\'; + break; + + case '\\': + case '\'': + case '\"': + break; + + case '0': + ch = '\000'; + break; + case 'b': + ch = '\b'; + break; + case 'd': + ch = '\177'; + break; + case 'e': + ch = '\033'; + break; + case 'f': + ch = '\f'; + break; + case 'n': + ch = '\n'; + break; + case 'r': + ch = '\r'; + break; + case 't': + ch = '\t'; + break; + case 'v': + ch = '\013'; + break; + case 'z': + ch = '\032'; + break; + + default: + // log error: bad escape + log(Severity.ERROR, CHAR_BAD_ESC, null, lPosChar); + break; + } + break; + + case '\r': + case '\n': + case 0x000B: // VT Vertical Tab + case 0x000C: // FF Form Feed + case 0x0085: // NEL Next Line + case 0x2028: // LS Line Separator + case 0x2029: // PS Paragraph Separator + // log error: newline in string + source.rewind(); + log(Severity.ERROR, CHAR_NO_TERM, null, lInitPos); + break; + + default: + break; + } + + if (source.hasNext()) + { + if (source.next() == '\'') + { + term = true; + } + else + { + source.rewind(); + } + } + } + + if (!term) + { + // log error: unterminated string + log(Severity.ERROR, CHAR_NO_TERM, null, lInitPos); + } + + return new Token(lInitPos, source.getPosition(), Id.LIT_CHAR, Character.valueOf(ch)); + } + + /** + * Eat the character contents of a string literal, including the string literal portion(s) of a + * template literal. + * + * @param lInitPos the location of the start of the literal (the position of the {@code $} or + * the {@code "}) + * @param fTemplate true iff this is a template literal + * @param fMultiline true iff this is a multi-line format + * + * @return the resulting token + */ + protected Token eatStringChars(long lInitPos, boolean fTemplate, boolean fMultiline) + { + Source source = m_source; + + StringBuilder sb = new StringBuilder(); + ArrayList list = fTemplate ? new ArrayList<>() : null; + long lPosStart = lInitPos; + Appending: while (true) + { + if (source.hasNext()) + { + char ch = source.next(); + switch (ch) + { + case '\"': + if (fMultiline) + { + sb.append(ch); + break; + } + break Appending; + + case '\\': + if (fMultiline) + { + if (source.hasNext()) + { + if (isLineTerminator(source.next()) && isMultilineContinued()) + { + continue; // Appending; + } + source.rewind(); + } + + if (!fTemplate) + { + sb.append(ch); + break; + } + } + + // process escaped char + switch (ch = source.next()) + { + case '\r': + case '\n': + case 0x000B: // VT Vertical Tab + case 0x000C: // FF Form Feed + case 0x0085: // NEL Next Line + case 0x2028: // LS Line Separator + case 0x2029: // PS Paragraph Separator + // log error: newline in string + source.rewind(); + log(Severity.ERROR, STRING_NO_TERM, null, lInitPos); + // assume it wasn't supposed to be an escape + sb.append('\\'); + break Appending; + + case '\\': + sb.append('\\'); + break; + case '\'': + sb.append('\''); + break; + case '\"': + sb.append('\"'); + break; + + case '0': + sb.append('\000'); + break; + case 'b': + sb.append('\b'); + break; + case 'd': + sb.append('\177'); + break; + case 'e': + sb.append('\033'); + break; + case 'f': + sb.append('\f'); + break; + case 'n': + sb.append('\n'); + break; + case 'r': + sb.append('\r'); + break; + case 't': + sb.append('\t'); + break; + case 'v': + sb.append('\013'); + break; + case 'z': + sb.append('\032'); + break; + + case '{': + if (fTemplate) + { + sb.append('{'); + break; + } + // fall through + + default: + // log error: bad escape + long lPosEscEnd = source.getPosition(); + source.rewind(); + source.rewind(); + log(Severity.ERROR, STRING_BAD_ESC, null, + source.getPosition(), lPosEscEnd); + source.setPosition(lPosEscEnd); + + // assume it wasn't supposed to be an escape: + // append both the escape char and the escaped char + sb.append('\\') + .append(ch); + break; + } + break; + + case '\r': + case '\n': + case 0x000B: // VT Vertical Tab + case 0x000C: // FF Form Feed + case 0x0085: // NEL Next Line + case 0x2028: // LS Line Separator + case 0x2029: // PS Paragraph Separator + if (fMultiline) + { + boolean fCRLF = false; + if (ch == '\r' && source.hasNext()) + { + if (source.next() == '\n') + { + fCRLF = true; + } + else + { + source.rewind(); + } + } + + // eat whitespace and look for a continuation character + if (isMultilineContinued()) + { + // it is a multi-line continuation, so include the newline that we + // just ate in the resulting text + if (fCRLF) + { + sb.append("\r\n"); + } + else + { + sb.append(ch); + } + break; + } + else + { + // leave the newline in place (it's not part of the multiline) + source.rewind(); + if (fCRLF) + { + source.rewind(); + } + } + } + else + { + // not a multi-line literal; log error: newline in string + source.rewind(); + log(Severity.ERROR, STRING_NO_TERM, null, lInitPos); + } + break Appending; + + case '{': + if (fTemplate) + { + source.rewind(); + long lPosEndText = source.getPosition(); + + // eat from the opening { to the closing } (inclusive of both) + Token[] aTokens = eatTemplateExpression(fMultiline); + int cTokens = aTokens.length; + + // if the last token was '=', then add the entire expression up to that + // point as literal text, and discard the '=' + if (cTokens > 1 && aTokens[cTokens-1].getId() == Id.ASN) + { + Token[] aTokensOld = aTokens; + aTokens = new Token[--cTokens]; + System.arraycopy(aTokensOld, 0, aTokens, 0, cTokens); + + sb.append(source.toString(aTokensOld[0].getStartPosition(), + aTokensOld[cTokens].getEndPosition())); + } + + if (sb.length() > 0) + { + list.add(new Token(lPosStart, lPosEndText, Id.LIT_STRING, sb.toString())); + sb = new StringBuilder(); + } + + list.add(aTokens); + + // start eating a new string portion of the template from this point + lPosStart = source.getPosition(); + break; + } + // fall through + + default: + sb.append(ch); + break; + } + } + else + { + // log error: unterminated string + log(Severity.ERROR, STRING_NO_TERM, null, lInitPos); + } + } + + if (fTemplate) + { + long lPosCur = source.getPosition(); + if (sb.length() > 0) + { + list.add(new Token(lPosStart, lPosCur, Id.LIT_STRING, sb.toString())); + } + else if (list.isEmpty()) + { + return new Token(lPosStart, lPosCur, Id.LIT_STRING, ""); + } + return new Token(lInitPos, lPosCur, Id.TEMPLATE, list.toArray()); + } + + return new Token(lPosStart, source.getPosition(), Id.LIT_STRING, sb.toString()); + } + + /** + * Eat a numeric literal. + * + * @return the numeric literal as a Token + */ + protected Token eatNumericLiteral() + { + Source source = m_source; + long lStartPos = source.getPosition(); + + // eat the first part of the number (or the entire number, if it is an integer literal) + int[] results = new int[2]; + PackedInteger piWhole = eatIntegerLiteral(results); + int mantissaRadix = results[0]; + int signScalar = results[1]; + + // parse optional '.' + value + PackedInteger piFraction = null; + int fractionalDigits = 0; + if (source.hasNext()) + { + if (source.next() == '.') + { + // could be ".." + if (source.hasNext()) + { + boolean fNotDecimal = source.next() == '.'; + // whatever it was, spit it back out + source.rewind(); + + // if it's not "..", it could be something else, e.g. a method name on type Int + if (!fNotDecimal && !isNextCharDigit(mantissaRadix)) + { + fNotDecimal = true; + } + + if (fNotDecimal) + { + // spit back out the first dot + source.rewind(); + + return new Token(lStartPos, source.getPosition(), Id.LIT_INT, piWhole); + } + } + + piFraction = eatDigits(false, mantissaRadix, results); + fractionalDigits = results[0]; + + if (fractionalDigits == 0) + { + log(Severity.ERROR, ILLEGAL_NUMBER, lStartPos, lStartPos); + } + } + else + { + source.rewind(); + } + } + + // parse optional exponent + PackedInteger piExp = null; + boolean mustBeBinary = false; + if (source.hasNext()) + { + char ch = source.next(); + switch (ch) + { + case 'E': case 'e': + piExp = eatIntegerLiteral(null); + break; + + case 'P': case 'p': + piExp = eatIntegerLiteral(null); + mustBeBinary = true; + break; + + default: + // anything else should be whitespace or some type of operator/separator + long lEndPos = source.getPosition(); + source.rewind(); + if (isIdentifierPart(ch)) + { + log(Severity.ERROR, ILLEGAL_NUMBER, lStartPos, + source.getPosition(), lEndPos); + } + break; + } + } + + long lPosEnd = source.getPosition(); + if (piFraction == null && piExp == null) + { + return new Token(lStartPos, lPosEnd, Id.LIT_INT, piWhole); + } + else if (!mustBeBinary && mantissaRadix == 10) + { + // convert to IEEE-754 decimal floating point format + // note: for now it is simply stored in the literal token as a BigDecimal + BigInteger biWhole = piWhole.getBigInteger(); + BigDecimal dec; + if (piFraction == null) + { + dec = new BigDecimal(biWhole); + } + else + { + if (biWhole.signum() < 0) + { + biWhole = biWhole.negate(); + } + dec = new BigDecimal(biWhole.multiply(BigInteger.TEN.pow(fractionalDigits)) + .add(piFraction.getBigInteger()), fractionalDigits); + if (signScalar < 0) + { + // the unfortunate side-effect of not having a -0 + dec = dec.negate(); + } + } + if (piExp != null) + { + long lExp = piExp.getLong(); + if (lExp > 6144 || lExp < (1-6144)) + { + log(Severity.ERROR, ILLEGAL_NUMBER, lStartPos, + lStartPos, lPosEnd); + } + else + { + dec = dec.scaleByPowerOfTen((int) lExp); + } + } + return new Token(lStartPos, lPosEnd, Id.LIT_DEC, dec); + } + else + { + // convert to IEEE-754 binary floating point format + // note: for now it is simply stored in the literal token as a String + return new Token(lStartPos, lPosEnd, Id.LIT_FLOAT, extractSource(lStartPos, lPosEnd)); + } + } + + /** + * The next character must begin an integer literal. Parse it and return it as a PackedInteger. + * + * @param otherResults either null, or an array of up to two "int" elements, to allow for + * multiple "out" values from this method, the first of which is the radix + * and the second is the sign (<tt>-1</tt> or <tt>+1</tt>) + * + * @return a PackedInteger + */ + protected PackedInteger eatIntegerLiteral(int[] otherResults) + { + Source source = m_source; + + // the first character could be a sign (+ or -) + boolean fNeg = false; + char ch = needCharOrElse(ILLEGAL_NUMBER); + if (ch == '+' || ch == '-') + { + fNeg = (ch == '-'); + ch = needCharOrElse(ILLEGAL_NUMBER); + } + + // if the next character is '0', it is potentially part of a prefix denoting a radix + int radix = 10; + if (ch == '0' && source.hasNext()) + { + switch (nextChar()) + { + case 'B': + case 'b': + radix = 2; + break; + case 'o': + radix = 8; + break; + case 'X': + case 'x': + radix = 16; + break; + default: + source.rewind(); + source.rewind(); + break; + } + } + else + { + source.rewind(); + } + + // don't you just wish that Java had multiple return values? + if (otherResults != null) + { + if (otherResults.length > 0) + { + otherResults[0] = radix; + } + if (otherResults.length > 1) + { + otherResults[1] = fNeg ? -1 : 1; + } + } + + PackedInteger pi = eatDigits(fNeg, radix, null); + + PossibleSuffix: if (radix == 10 && source.hasNext()) + { + // allow KI/KB, MI/MB, GI/GB TI/TB, PI/PB, EI/EB, ZI/ZB, YI/YB + int iMul; + switch (nextChar()) + { + case 'K': case 'k': + iMul = 0; + break; + + case 'M': case 'm': + iMul = 1; + break; + + case 'G': case 'g': + iMul = 2; + break; + + case 'T': case 't': + iMul = 3; + break; + + case 'P': case 'p': + iMul = 4; + break; + + case 'E': case 'e': + iMul = 5; + break; + + case 'Z': case 'z': + iMul = 6; + break; + + case 'Y': case 'y': + iMul = 7; + break; + + default: + source.rewind(); + break PossibleSuffix; + } + + PackedInteger[] factors = PackedInteger.xB_FACTORS; + if (source.hasNext()) + { + switch (nextChar()) + { + case 'B': case 'b': + break; + + case 'I': case 'i': + if (source.hasNext()) + { + char optionalB = source.next(); + if (!(optionalB == 'B' || optionalB == 'b')) + { + source.rewind(); + } + } + factors = PackedInteger.xI_FACTORS; + break; + + case '+': case '-': + case '0': case '1': case '2': case '3': case '4': + case '5': case '6': case '7': case '8': case '9': + if (iMul == 4 || iMul == 5) + { + // the "P" or the "E" is for an exponent + source.rewind(); + source.rewind(); + break PossibleSuffix; + } + default: + source.rewind(); + break; + } + } + + pi = pi.mul(factors[iMul]); + } + + return pi; + } + + /** + * @return the value, or a negative value if there was no number or the number overflowed + */ + protected long eatUnsignedLong() + { + long n = 0; + if (isNextCharDigit(10)) + { + do + { + if (n < 0) + { + return n; + } + + n = n * 10 + (nextChar() - '0'); + } + while (isNextCharDigit(10)); + + return n; + } + else + { + return -1; + } + } + + protected boolean isNextCharDigit(int radix) + { + boolean fDigit = false; + + Source source = m_source; + if (source.hasNext()) + { + switch (nextChar()) + { + case 'A': case 'B': case 'C': case 'D': case 'E': case 'F': + case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': + fDigit = radix >= 16; + break; + + case '9': case '8': + fDigit = radix >= 10; + break; + + case '7': case '6': case '5': case '4': case '3': case '2': + fDigit = radix >= 8; + break; + + case '1': + case '0': + fDigit = true; + break; + + default: + break; + } + source.rewind(); + } + + return fDigit; + } + + /** + * The next character must begin a sequence of digits of the specified radix. Parse it and + * return it as a PackedInteger. + * + * @return a PackedInteger + */ + protected PackedInteger eatDigits(boolean fNeg, int radix, int[] digitCount) + { + long lValue = 0; + BigInteger bigint = null; // just in case + boolean fError = false; + int cDigits = 0; + + Source source = m_source; + long lStartPos = source.getPosition(); + Parsing: while (source.hasNext()) + { + long lPos = source.getPosition(); + char ch = nextChar(); + switch (ch) + { + case 'A': case 'B': case 'C': case 'D': case 'E': case 'F': + case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': + if (radix < 16) + { + // "e" is used as the decimal exponent indicator + if (ch != 'E' && ch != 'e') + { + if (!fError) + { + log(Severity.ERROR, ILLEGAL_NUMBER, lStartPos, lPos); + fError = true; + } + } + source.rewind(); + break Parsing; + } + break; + + case '9': case '8': + if (radix < 10) + { + if (!fError) + { + log(Severity.ERROR, ILLEGAL_NUMBER, lStartPos, lPos); + fError = true; + } + // while an error was encountered, it was at least a digit, so continue + // parsing those digits (even if they are bad) + continue; // Parsing; + } + break; + + case '7': case '6': case '5': case '4': case '3': case '2': + if (radix < 8) + { + if (!fError) + { + log(Severity.ERROR, ILLEGAL_NUMBER, lStartPos, lPos); + fError = true; + } + // while an error was encountered, it was at least a digit, so continue + // parsing those digits (even if they are bad) + continue; // Parsing; + } + break; + + case '1': case '0': + break; + + case '_': + if (cDigits == 0 && !fError) + { + // it's an error to start the sequence of digits with an underscore + log(Severity.ERROR, ILLEGAL_NUMBER, lStartPos, lPos); + fError = true; + } + continue; // Parsing; + + default: + // anything else (including '.') means go to the next step + source.rewind(); + break Parsing; + } + + if (bigint == null) + { + lValue = lValue * radix + hexitValue(ch); + if (lValue > 0x00FFFFFFFFFFFFFFL) + { + bigint = BigInteger.valueOf(fNeg ? -lValue : lValue); + } + } + else + { + bigint = bigint.multiply(BigInteger.valueOf(radix)).add(BigInteger.valueOf(hexitValue(ch))); + } + ++cDigits; + } + + if (!fError && cDigits == 0) + { + log(Severity.ERROR, ILLEGAL_NUMBER, lStartPos, lStartPos); + } + + if (digitCount != null && digitCount.length > 0) + { + digitCount[0] = cDigits; + } + return bigint == null ? new PackedInteger(fNeg ? -lValue : lValue) : new PackedInteger(bigint); + } + + /** + * Eat a literal ISO-8601 datetime value (the Ecstasy "Time" class). + * + * @param lInitPos the location of the start of the literal token + * + * @return the literal as a Token + */ + protected Token eatTime(long lInitPos) + { + Token tokDate = eatDate(lInitPos, true); + if (!(match('t') || expect('T'))) + { + log(Severity.ERROR, BAD_TIME, new Object[] {tokDate.getValue()}, + tokDate.getStartPosition(), tokDate.getEndPosition()); + return tokDate; + } + + Token tokTimeOfDay = eatTimeOfDay(lInitPos, true); + long lEndPos = tokTimeOfDay.getEndPosition(); + + String sDT = tokDate.getValue() + "T" + tokTimeOfDay.getValue(); + if (match('Z') || match('z') || match('+') || match('-')) + { + m_source.rewind(); + Token tokZone = eatTimeZone(lInitPos); + sDT += tokZone.getValue(); + lEndPos = tokZone.getEndPosition(); + } + + return new Token(lInitPos, lEndPos, Id.LIT_TIME, sDT); + } + + /** + * Eat a literal ISO-8601 timezone value. + * + * @param lInitPos the location of the start of the literal token + * + * @return the literal as a Token + */ + protected Token eatTimeZone(long lInitPos) + { + if (match('Z') || match('z')) + { + peekNotIdentifierOrNumber(); + return new Token(lInitPos, m_source.getPosition(), Id.LIT_TIMEZONE, "Z"); + } + + long lStart = m_source.getPosition(); + int nHour = 0; + int nMin = 0; + if (match('-') || expect('+')) + { + if ((nHour = eatDigits(2)) >= 0) + { + if (match(':') || isNextCharDigit(10)) + { + if ((nMin = eatDigits(2)) >= 0) + { + peekNotIdentifierOrNumber(); + } + } + else + { + peekNotIdentifierOrNumber(); + } + } + } + long lEnd = m_source.getPosition(); + String sZone = extractSource(lStart, lEnd); + + if (nHour >= 0 && nMin >= 0) + { + if (nHour > 16 || nMin > 59) + { + log(Severity.ERROR, BAD_TIMEZONE, new Object[] {sZone}, lStart, lEnd); + } + } + + return new Token(lInitPos, lEnd, Id.LIT_TIMEZONE, sZone); + } + + /** + * Eat a specified number of decimal digits, and convert them to an integer. + * + * @param digitCount the number of digits to eat + * + * @return the parsed integer value, or the negative thereof if an error was encountered + */ + protected int eatDigits(int digitCount) + { + long lPosStart = m_source.getPosition(); + + int n = 0; + for (int i = 0; i < digitCount; ++i) + { + if (!isNextCharDigit(10)) + { + log(Severity.ERROR, EXPECTED_DIGITS, new Object[] {digitCount, i}, lPosStart); + return -n; + } + + n = n * 10 + (nextChar() - '0'); + } + return n; + } + + /** + * Eat a literal ISO-8601 date value. + * + * @param lInitPos the location of the start of the literal token + * @param fContinued true if this is just part of a larger literal + * + * @return the literal as a Token + */ + protected Token eatDate(long lInitPos, boolean fContinued) + { + Source source = m_source; + long lLitPos = source.getPosition(); + + int nYear; + int nMonth = 0; + int nDay = 0; + + if ((nYear = eatDigits(4)) >= 0) + { + boolean fSep = match('-'); + if ((nMonth = eatDigits(2)) >= 0) + { + if (fSep) + { + expect('-'); + } + if ((nDay = eatDigits(2)) >= 0) + { + if (!fContinued) + { + peekNotIdentifierOrNumber(); + } + } + } + } + + long lEndPos = source.getPosition(); + String sDate = extractSource(lLitPos, lEndPos); + if (nYear >= 0 && nMonth >= 0 && nDay >= 0) + { + if (nYear < 1582 || nMonth < 1 || nMonth > 12 || nDay < 1 || nDay > 31) + { + log(Severity.ERROR, BAD_DATE, new Object[] {sDate}, lLitPos, lEndPos); + } + } + + return new Token(lInitPos, lEndPos, Id.LIT_DATE, sDate); + } + + /** + * Eat a literal ISO-8601 time value (the Ecstasy "TimeOfDay" class). + * + * @param lInitPos the location of the start of the literal token + * @param fContinued true if this is just part of a larger literal + * + * @return the literal as a Token + */ + protected Token eatTimeOfDay(long lInitPos, boolean fContinued) + { + Source source = m_source; + long lStart = source.getPosition(); + + int nHour; + int nMin = 0; + int nSec = 0; + long nPicos = 0; + int cDigits; + + if ((nHour = eatDigits(2)) >= 0) + { + boolean fSep = match(':'); + if ((nMin = eatDigits(2)) >= 0) + { + if (fSep && match(':') || !fSep && isNextCharDigit(10)) + { + nSec = eatDigits(2); + if (match('.')) + { + if (isNextCharDigit(10)) + { + cDigits = 0; + do + { + char ch = nextChar(); + if (++cDigits <= 12) + { + nPicos = nPicos * 10 + (ch - '0'); + } + } + while (isNextCharDigit(10)); + + // scale the integer value up to picos (trillionths) + while (++cDigits <= 12) + { + nPicos *= 10; + } + } + else + { + // the dot isn't part of the time-of-day + source.rewind(); + } + } + } + if (!fContinued) + { + peekNotIdentifierOrNumber(); + } + } + } + + long lEnd = source.getPosition(); + String sTime = extractSource(lStart, lEnd); + if (nHour >= 0 && nMin >= 0 && nSec >= 0) + { + if (nHour > 23 || nMin > 59 || nSec > 59 && !(nHour == 23 && nMin == 59 && nSec == 60)) + { + log(Severity.ERROR, BAD_TIME_OF_DAY, new Object[] {sTime}, lStart, lEnd); + } + } + + return new Token(lInitPos, lEnd, Id.LIT_TIMEOFDAY, sTime); + } + + /** + * Obtain a cookie that represents the Lexer's current location. + * + * @return a position cookie + */ + public long mark() + { + // this adds a bit of information to the source's position info + long lPos = m_source.getPosition(); + assert (lPos & (1L << 63)) == 0L; + if (m_fWhitespace) + { + lPos |= (1L << 63); + } + return lPos; + } + + /** + * Using a previously returned Lexer position cookie, restore that state of the lexer. + * + * @param lPos a position cookie previously returned from {@link #mark()} + */ + public void restore(long lPos) + { + m_fWhitespace = (lPos & (1L << 63)) != 0L; + m_source.setPosition(lPos & ~(1L << 63)); + } + + /** + * Obtain the character located at a previously returned position cookie, but the state of the + * Lexer after this call must match that from before the call. + * + * @param lPos a previously returned position cookie + * + * @return the character at the specified position + */ + public char charAt(long lPos) + { + long lPrev = mark(); + restore(lPos); + char ch = nextChar(); + restore(lPrev); + return ch; + } + + /** + * Eat a literal ISO-8601 duration value. + * + * @param lInitPos the location of the start of the literal token + * + * @return the literal as a Token + */ + protected Token eatDuration(long lInitPos) + { + Source source = m_source; + long lStart = source.getPosition(); + + // Stages: + // Y, M, D, (T), H, M, S + // 1 2 3 4 5 6 7 . 8 + + boolean fErr = false; + if (!match('P')) + { + match('p'); + } + + int nPrevStage = match('T') ? 4 : 0; + Loop: while (true) + { + long lPos = source.getPosition(); + long lVal = eatUnsignedLong(); + if (lVal < 0) + { + source.setPosition(lPos); + break; + } + + char ch = nextChar(); + switch (ch) + { + case 'Y': + case 'y': + if (nPrevStage >= 1) + { + fErr = true; + } + nPrevStage = Math.max(1, nPrevStage); + break; + + case 'M': + case 'm': + if (nPrevStage >= 2) + { + // parse as minute + if (nPrevStage < 4) + { + fErr = true; + } + nPrevStage = Math.max(6, nPrevStage); + } + else + { + // parse as month + nPrevStage = Math.max(2, nPrevStage); + } + break; + + case 'D': + case 'd': + if (nPrevStage >= 3) + { + fErr = true; + } + nPrevStage = Math.max(3, nPrevStage); + break; + + case 'H': + case 'h': + if (nPrevStage >= 5) + { + fErr = true; + } + nPrevStage = Math.max(5, nPrevStage); + break; + + case 'S': + case 's': + break Loop; + + case '.': + if (nPrevStage >= 7) + { + fErr = true; + } + nPrevStage = Math.max(7, nPrevStage); + break; + + default: + source.rewind(); + fErr = true; + break Loop; + } + + if (match('T') || match('t')) + { + if (nPrevStage >= 4) + { + fErr = true; + } + else + { + nPrevStage = 4; + } + } + } + + long lEnd = source.getPosition(); + String sDuration = extractSource(lStart, lEnd).toUpperCase(); + + if (fErr) + { + log(Severity.ERROR, BAD_DURATION, new Object[] {sDuration}, lStart, lEnd); + } + else + { + peekNotIdentifierOrNumber(); + } + + return new Token(lStart, lEnd, Id.LIT_DURATION, sDuration); + } + + /** + * Eat a single line aka end-of-line comment. + * + * @return the comment as a Token + */ + protected Token eatSingleLineComment(long lPosTokenStart) + { + Source source = m_source; + long lPosTextStart = source.getPosition(); + while (source.hasNext()) + { + if (isLineTerminator(nextChar())) + { + source.rewind(); + break; + } + } + long lPosEnd = source.getPosition(); + return new Token(lPosTokenStart, lPosEnd, Id.EOL_COMMENT, + extractSource(lPosTextStart, lPosEnd)); + } + + /** + * Eat a multi-line aka enclosed comment. + * + * @return the comment as a Token + */ + protected Token eatEnclosedComment(long lPosTokenStart) + { + Source source = m_source; + long lPosTextStart = source.getPosition(); + + boolean fAsterisk = false; + while (source.hasNext()) + { + char chNext = nextChar(); + if (chNext == '*') + { + fAsterisk = true; + } + else if (fAsterisk && chNext == '/') + { + long lPosTokenEnd = source.getPosition(); + source.rewind(); + source.rewind(); + long lPosTextEnd = source.getPosition(); + source.setPosition(lPosTokenEnd); + return new Token(lPosTokenStart, lPosTokenEnd, Id.ENC_COMMENT, + extractSource(lPosTextStart, lPosTextEnd)); + } + else + { + fAsterisk = false; + } + } + + // missing the enclosing "*/" + log(Severity.ERROR, EXPECTED_ENDCOMMENT, null, lPosTextStart); + + // just pretend that the rest of the file was all one big comment + long lPosEnd = source.getPosition(); + return new Token(lPosTokenStart, lPosEnd, Id.ENC_COMMENT, + extractSource(lPosTextStart, lPosEnd)); + } + + /** + * Get the next character of source code, making sure that it is the specified character. + * + * @param ch the desired character + * + * @return true iff the next character was matched + */ + protected boolean match(char ch) + { + char chActual; + try + { + chActual = nextChar(); + } + catch (NoSuchElementException e) + { + log(Severity.ERROR, UNEXPECTED_EOF, null, m_source.getPosition()); + return false; + } + + if (chActual != ch) + { + m_source.rewind(); + return false; + } + + return true; + } + + /** + * Get the next character of source code, making sure that it is the specified character. + * + * @param ch the expected character + * + * @return true iff the next character was found + */ + protected boolean expect(char ch) + { + char chActual; + try + { + chActual = nextChar(); + } + catch (NoSuchElementException e) + { + log(Severity.ERROR, UNEXPECTED_EOF, null, m_source.getPosition()); + return false; + } + + if (chActual != ch) + { + log(Severity.ERROR, EXPECTED_CHAR, + new Object[] {String.valueOf(ch), String.valueOf(chActual)}, + m_source.getPosition()); + return false; + } + + return true; + } + + protected boolean matchCaseInsens(String s) + { + for (int i = 0, c = s.length(); i < c; ++i) + { + char ch = s.charAt(i); + if (match(ch) || match(Character.toLowerCase(ch)) || match(Character.toUpperCase(ch))) + { + continue; + } + return false; + } + + char ch = peekChar(); + return !(isIdentifierPart(ch) && !isDigit(ch)); + } + + /** + * Verify that the next character is NOT a number or an identifier char. + */ + protected void peekNotIdentifierOrNumber() + { + char ch = nextChar(); + long lEnd = m_source.getPosition(); + m_source.rewind(); + if (ch >= '0' && ch <= '9' || isIdentifierPart(ch)) + { + log(Severity.ERROR, UNEXPECTED_CHAR, new Object[] {ch}, m_source.getPosition(), lEnd); + } + } + + protected String extractSource(long lPosStart) + { + return extractSource(lPosStart, m_source.getPosition()); + } + + protected String extractSource(long lPosStart, long lPosEnd) + { + return m_source.toString(lPosStart, lPosEnd); + } + + /** + * Log an error (without error params) using the current position in the script as the end + * position for the error. + */ + public void log(Severity severity, String sCode, long lPosPrev, long lPosStart) + { + log(severity, sCode, lPosPrev, lPosStart, m_source.getPosition()); + } + + /** + * Log an error (without error params). + */ + protected void log(Severity severity, String sCode, long lPosPrev, long lPosStart, long lPosEnd) + { + if (lPosPrev == lPosStart) + { + m_source.rewind(); + lPosPrev = m_source.getPosition(); + m_source.next(); + } + + log(severity, sCode, new Object[]{extractSource(lPosPrev, lPosEnd)}, lPosStart, lPosEnd); + } + + /** + * Log an error using the current position in the script as the end position for the error. + */ + protected void log(Severity severity, String sCode, Object[] aoParam, long lPosStart) + { + log(severity, sCode, aoParam, lPosStart, m_source.getPosition()); + } + + /** + * Log an error. + */ + protected void log(Severity severity, String sCode, Object[] aoParam, long lPosStart, long lPosEnd) + { + m_errorListener.log(severity, sCode, aoParam, m_source, lPosStart, lPosEnd); + } + + + // ----- helper methods ------------------------------------------------------------------------ + + /** + * Determine if the specified character is white-space. + * + * @param ch the character to evaluate + * + * @return true iff the character is defined as an XTC <i>SpacingElement</i> + */ + public static boolean isWhitespace(char ch) + { + // optimize for the ASCII range + if (ch < 128) + { + // this handles the following cases: + // U+0009 9 HT Horizontal Tab + // U+000A 10 LF Line Feed + // U+000B 11 VT Vertical Tab + // U+000C 12 FF Form Feed + // U+000D 13 CR Carriage Return + // U+001A 26 SUB End-of-File, or “control-Z” + // U+001C 28 FS File Separator + // U+001D 29 GS Group Separator + // U+001E 30 RS Record Separator + // U+001F 31 US Unit Separator + // U+0020 32 SP Space + // 2 1 0 + // 0FEDCBA9876543210FEDCBA9 + return ch <= 32 && ch >= 9 && ((1 << (ch-9)) & 0b111110100000000000011111) != 0; + } + + // this handles the following cases: + // U+0085 133 NEL Next Line + // U+00A0 160 Non-breaking space + // U+1680 5760 Ogham Space Mark + // U+2000 8192 En Quad + // U+2001 8193 Em Quad + // U+2002 8194 En Space + // U+2003 8195 Em Space + // U+2004 8196 Three-Per-Em Space + // U+2005 8197 Four-Per-Em Space + // U+2006 8198 Six-Per-Em Space + // U+2007 8199 Figure Space + // U+2008 8200 Punctuation Space + // U+2009 8201 Thin Space + // U+200A 8202 Hair Space + // U+2028 8232 LS Line Separator + // U+2029 8233 PS Paragraph Separator + // U+202F 8239 Narrow No-Break Space + switch (ch) + { + case 0x0085: + case 0x00A0: + case 0x1680: + case 0x2000: + case 0x2001: + case 0x2002: + case 0x2003: + case 0x2004: + case 0x2005: + case 0x2006: + case 0x2007: + case 0x2008: + case 0x2009: + case 0x200A: + case 0x2028: + case 0x2029: + case 0x202F: + case 0x205F: + case 0x3000: + return true; + + default: + return false; + } + } + + /** + * Determine if the specified character is a line terminator. + * + * @param ch the character to evaluate + * + * @return true iff the character is defined as an XTC <i>LineTerminator</i> + */ + public static boolean isLineTerminator(char ch) + { + // optimize for the ASCII range + if (ch < 128) + { + // this handles the following cases: + // U+000A 10 LF Line Feed + // U+000B 11 VT Vertical Tab + // U+000C 12 FF Form Feed + // U+000D 13 CR Carriage Return + return ch >= 10 && ch <= 13; + } + + // this handles the following cases: + // U+0085 133 NEL Next Line + // U+2028 8232 LS Line Separator + // U+2029 8233 PS Paragraph Separator + return ch == 0x0085 | ch == 0x2028 | ch == 0x2029; + } + + /** + * Determine if the specified character can be used as the first character of an identifier. + * + * @param ch the character to evaluate + * + * @return true iff the specified character can be the start of an + * identifier + */ + public static boolean isIdentifierStart(char ch) + { + return Character.isUnicodeIdentifierStart(ch) || ch == '_'; + } + + /** + * Determine if the specified character can be part of an identifier. + * + * @param ch the character to evaluate + * + * @return true iff the specified character can be part of an identifier + */ + public static boolean isIdentifierPart(char ch) + { + return Character.isUnicodeIdentifierPart(ch) || ch == '_'; + } + + /** + * Get the next character of source code, but do not move the current location. + */ + protected char peekChar() + { + char ch = m_source.next(); + m_source.rewind(); + return ch; + } + + /** + * Get the next character of source code, but do some additional checks on the character to make + * sure it's legal, such as checking for an illegal SUB character. + */ + protected char nextChar() + { + Source source = m_source; + char ch = source.next(); + + // it is illegal for the SUB aka EOF character to occur + // anywhere in the source other than at the end + if (ch == EOF && source.hasNext()) + { + // back up to get the location of the SUB character + long lPos = source.getPosition(); + source.rewind(); + long lStartPos = source.getPosition(); + source.setPosition(lPos); + + log(Severity.ERROR, UNEXPECTED_EOF, null, lStartPos); + } + + return ch; + } + + /** + * Get the next character of source code, but do some additional checks on the character to make + * sure it's legal, such as checking for an illegal SUB character. + */ + protected char needCharOrElse(String sError) + { + try + { + return nextChar(); + } + catch (NoSuchElementException e) + { + log(Severity.ERROR, sError, m_source.getPosition(), m_source.getPosition()); + } + + // already logged an error; just pretend we hit a closing brace (since all roads should have + // gone there) + return '}'; + } + + + // ----- constants ----------------------------------------------------------------------------- + + /** + * Unicode: Horizontal Tab. + */ + public static final char HT = 0x0009; + /** + * Unicode: Line Feed. + */ + public static final char LF = 0x000A; + /** + * Unicode: Vertical Tab. + */ + public static final char VT = 0x000B; + /** + * Unicode: Form Feed. + */ + public static final char FF = 0x000C; + /** + * Unicode: Carriage Return. + */ + public static final char CR = 0x000D; + /** + * Unicode: End-Of-File aka control-z aka SUB. + */ + public static final char EOF = 0x001A; + /** + * Unicode: File Separator. + */ + public static final char FS = 0x001C; + /** + * Unicode: Group Separator. + */ + public static final char GS = 0x001D; + /** + * Unicode: Record Separator. + */ + public static final char RS = 0x001E; + /** + * Unicode: Unit Separator. + */ + public static final char US = 0x001F; + /** + * Unicode: Next Line. + */ + public static final char NEL = 0x0085; + /** + * Unicode: Non-Breaking Space aka " ". + */ + public static final char NBS = 0x00A0; + /** + * Unicode: Line Separator. + */ + public static final char LS = 0x2028; + /** + * Unicode: Paragraph Separator. + */ + public static final char PS = 0x2029; + + /** + * Unexpected End-Of-File (SUB character). + */ + public static final String UNEXPECTED_EOF = "LEXER-01"; + /** + * Expected a comment-ending "star slash" but never found one. + */ + public static final String EXPECTED_ENDCOMMENT = "LEXER-02"; + /** + * A character was encountered that cannot be the start of a valid token. + */ + public static final String ILLEGAL_CHAR = "LEXER-03"; + /** + * Number format exception. + */ + public static final String ILLEGAL_NUMBER = "LEXER-04"; + /** + * An illegal character literal, missing closing quote. + */ + public static final String CHAR_NO_TERM = "LEXER-05"; + /** + * An illegally escaped character literal. + */ + public static final String CHAR_BAD_ESC = "LEXER-06"; + /** + * An illegal character literal missing the character. + */ + public static final String CHAR_NO_CHAR = "LEXER-07"; + /** + * An illegally terminated string literal. + */ + public static final String STRING_NO_TERM = "LEXER-08"; + /** + * An illegally escaped string literal. + */ + public static final String STRING_BAD_ESC = "LEXER-09"; + /** + * An illegal hex (binary) literal. + */ + public static final String ILLEGAL_HEX = "LEXER-10"; + /** + * Expected {0}; found {1}. + */ + public static final String EXPECTED_CHAR = "LEXER-11"; + /** + * {0} digits were required; only {1} digits were found. + */ + public static final String EXPECTED_DIGITS = "LEXER-12"; + /** + * Invalid ISO-8601 date {0}; ... + */ + public static final String BAD_DATE = "LEXER-13"; + /** + * Invalid ISO-8601 time {0}; ... + */ + public static final String BAD_TIME_OF_DAY = "LEXER-14"; + /** + * Invalid ISO-8601 datetime {0}; ... + */ + public static final String BAD_TIME = "LEXER-15"; + /** + * Invalid ISO-8601 timezone {0}; ... + */ + public static final String BAD_TIMEZONE = "LEXER-16"; + /** + * Invalid ISO-8601 duration {0}; ... + */ + public static final String BAD_DURATION = "LEXER-17"; + /** + * Unexpected character: {0} + */ + public static final String UNEXPECTED_CHAR = "LEXER-18"; + + + // ----- data members -------------------------------------------------------------------------- + + /** + * The Source to parse. + */ + private final Source m_source; + + /** + * The ErrorListener to report errors to. + */ + private final ErrorListener m_errorListener; + + /** + * Keeps track of whether whitespace was encountered. + */ + private boolean m_fWhitespace; + }
\ No newline at end of file diff --git a/common/src/main/java/com/seaofnodes/simple/lexer/ecstasy/Source.java b/common/src/main/java/com/seaofnodes/simple/lexer/ecstasy/Source.java new file mode 100644 index 00000000..6800138a --- /dev/null +++ b/common/src/main/java/com/seaofnodes/simple/lexer/ecstasy/Source.java @@ -0,0 +1,826 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is + * The Ecstasy Project (https://github.com/xtclang/). + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ +package com.seaofnodes.simple.lexer.ecstasy; + + +import java.io.File; +import java.io.IOException; +import java.io.InputStream; + +import java.nio.file.Path; + +import java.util.Arrays; +import java.util.NoSuchElementException; + +import com.seaofnodes.util.Handy; + +import static com.seaofnodes.simple.lexer.ecstasy.Lexer.isLineTerminator; +import static com.seaofnodes.util.Handy.*; + + +/** + * A representation of an XTC source code file, handling the first two phases of lexical analysis + * (line termination, location and unicode escapes). + */ +public class Source implements Cloneable + { + // ----- constructors -------------------------------------------------------------------------- + + /** + * Construct a Source directly from a String of XTC source code. + * + * @param sScript the XTC source code, as a String + */ + public Source(String sScript) + { + this(sScript.toCharArray()); + } + + /** + * Construct a Source directly from a String of XTC source code. + * + * @param sScript the XTC source code, as a String + */ + public Source(String sScript, int cDepth) + { + this(sScript.toCharArray()); + m_cDirDepth = cDepth; + } + + /** + * Construct a Source by reading the XTC source code from a file. + * + * @param file the File containing the XTC source code to load + * + * @param cDepth the number of directories up the source code can include files from + * + * @throws IOException + */ + public Source(File file, int cDepth) + throws IOException + { + this(readFileChars(file)); + m_file = file; + m_cDirDepth = cDepth; + setFileName(file.getPath()); + } + + /** + * Construct a Source from an input stream. + * + * @param stream the InputStream + */ + public Source(InputStream stream) + { + this(fromInputStream(stream)); + } + + /** + * Read a char[] from a stream. Inefficient, but predictable. + * + * @param stream the stream to vacuum + * + * @return the contents of the stream, as a char[] + */ + private static char[] fromInputStream(InputStream stream) + { + try + { + StringBuilder sb = new StringBuilder(); + int n; + while ((n = stream.read()) >= 0) + { + sb.append((char) n); + } + return sb.toString().toCharArray(); + } + catch (IOException e) + { + throw new RuntimeException(e); + } + } + + /** + * Construct a Source directly from a character array containing the XTC + * source code. Note that the passed array is retained -- not copied! -- by + * this constructor. + * + * @param ach the XTC source code, as a character array + */ + Source(char[] ach) + { + assert ach != null; + m_ach = ach; + m_cch = ach.length; + } + + + // ----- public API ---------------------------------------------------------------------------- + + /** + * @return the file name, if one has been configured + */ + public String getFileName() + { + return m_sFile; + } + + /** + * @return the simple file name, if a file is available + */ + public String getSimpleFileName() + { + return m_file == null ? "<no file>" : m_file.getName(); + } + + /** + * Specify the name of the file that the source comes from. This is automatically configured by + * the File-based constructor. + * + * @param sFile the file name + */ + public void setFileName(String sFile) + { + if (m_sFile == null) + { + m_sFile = sFile; + } + else if (!m_sFile.equals(sFile)) + { + throw new IllegalStateException("file name cannot be modified"); + } + } + + /** + * Determine the File referenced from inside another source file using the "File" or "Dir" + * BNF constructions. + * + * @param sFile a string put together from identifier tokens, "." tokens, "/" tokens, "./" + * tokens, and "../" tokens, following the rules defined in the Ecstasy BNF + * + * @return the File for the file or directory, or null if unresolvable + */ + public File resolvePath(String sFile) + { + if (m_file == null || sFile.length() == 0) + { + return null; + } + + File file = m_file.getParentFile(); + boolean fRoot = sFile.startsWith("/"); + m_cUp = 0; + if (fRoot) + { + // it's not absolute; it's relative to the directory containing the module + while (m_cUp < m_cDirDepth) + { + file = file.getParentFile(); + assert file != null; + ++m_cUp; + } + sFile = sFile.substring(1); + } + + if (sFile.length() == 0) + { + return file.isDirectory() ? file : null; + } + + boolean fRequireDir = sFile.endsWith("/"); + if (fRequireDir) + { + sFile = sFile.substring(0, sFile.length()-1); + } + + String[] segments = Handy.parseDelimitedString(sFile, '/'); + for (String segment : segments) + { + if (segment.length() == 0) + { + return null; + } + + if (segment.equals(".")) + { + // nothing to do + } + else if (segment.equals("..")) + { + file = file.getParentFile(); + if (file == null || ++m_cUp > m_cDirDepth) + { + return null; + } + } + else + { + if (file.exists() && !file.isDirectory()) + { + return null; + } + + file = new File(file, segment); + --m_cUp; + } + } + + if (!file.exists()) + { + // the file may be in the "symmetrical" resources directory + File fileSrc = getSubDir("x"); + File fileRes = getSubDir("resources"); + if (fileSrc != null && fileRes != null) + { + if (fRoot) + { + file = new File(fileRes, sFile); + } + else + { + Path path = file.toPath().normalize(); + Path pathSrc = fileSrc.toPath().normalize(); + Path pathRes = fileRes.toPath().normalize(); + Path pathRel = pathSrc.relativize(path); + file = pathRes.resolve(pathRel).toFile(); + } + if (!file.exists()) + { + return null; + } + } + } + + return fRequireDir && !file.isDirectory() ? null : file; + } + private transient int m_cUp; // Java needs multiple return values. This is a hack. + + /** + * @return the directory containing the module, or null if it cannot be determined + */ + private File getTopDir() + { + if (m_file == null) + { + return null; + } + + File file = m_file.getAbsoluteFile().getParentFile(); + for (int i = 0, c = m_cDirDepth; i < c; ++i) + { + file = file.getParentFile(); + if (file == null) + { + return null; + } + } + return file; + } + + /** + * @param sChild the name of the child directory + * + * @return the specified directory at the same level as the top directory, if it exists + */ + private File getSubDir(String sChild) + { + File file = getTopDir(); + if (file != null && file.exists() && file.isDirectory()) + { + file = file.getParentFile(); + if (file != null && file.exists() && file.isDirectory()) + { + file = new File(file, sChild); + if (file.exists() && file.isDirectory()) + { + return file; + } + } + } + return null; + } + + + /** + * Load a file (as text) referenced from inside another source file. + * + * @param sFile a string put together from identifier tokens, "/" tokens, "./" tokens, and + * "../" tokens + * + * @return the Source, or null + */ + public Source includeString(String sFile) + throws IOException + { + File file = resolvePath(sFile); + if (file == null) + { + return null; + } + + if (file.equals(m_file)) + { + return clone(); + } + + if (file.exists() && file.isFile() && file.canRead()) + { + return new Source(file, m_cDirDepth - m_cUp); + } + + return null; + } + + /** + * Load a file (as binary) referenced from inside another source file. + * + * @param sFile a string put together from identifier tokens, "/" tokens, "./" tokens, and + * "../" tokens + * + * @return the binary contents of the file, or null + */ + public byte[] includeBinary(String sFile) + throws IOException + { + File file = resolvePath(sFile); + if (file == null) + { + return null; + } + + if (file.exists() && file.isFile() && file.canRead()) + { + return Handy.readFileBytes(file); + } + + return null; + } + + /** + * Determine if there are more characters in the source. + * + * @return true iff there are still more characters + */ + public boolean hasNext() + { + return m_of < m_cch; + } + + /** + * Obtain the next character of the source. Note that unicode escapes are + * processed such that the sequence of characters "U+0024" in the source + * would return only the single character '$'. Similarly, the combination + * of CR+LF ("\r\n") is returned as the single character LF ('\n'). + * + * @return the next character from the source + * + * @throws NoSuchElementException if an attempt is made to advance past + * the end + */ + public char next() + { + final char[] ach = m_ach; + final int cch = m_cch; + + int of = m_of; + if (of >= cch) + { + throw new NoSuchElementException(); + } + + char ch = ach[of++]; + + // check for new line + if (Lexer.isLineTerminator(ch)) + { + // handle the special case of CR:LF by treating it as a single LF + // character + if (ch == '\r' && of < cch && ach[of] == '\n') + { + ++of; + ch = '\n'; + } + + ++m_iLine; + m_iLineOffset = 0; + } + else + { + int cchAdjust = 1; + + // check for a unicode escape + if (ch == '\\' && of + 4 < cch + && isHexit(ach[of+1]) + && isHexit(ach[of+2]) + && isHexit(ach[of+3]) + && isHexit(ach[of+4])) + { + final char chU = ach[of]; + if (chU == 'u') + { + // 4-hexit unicode escape + int nch = hexitValue(ach[of+1]) << 12 + | hexitValue(ach[of+2]) << 8 + | hexitValue(ach[of+3]) << 4 + | hexitValue(ach[of+4]); + + ch = (char) nch; + of += 5; + cchAdjust += 5; + m_fEscapesEncountered = true; + } + else if (chU == 'U' && of + 8 < cch + && isHexit(ach[of+5]) + && isHexit(ach[of+6]) + && isHexit(ach[of+7]) + && isHexit(ach[of+8])) + { + // 8-hexit unicode escape + int nch = hexitValue(ach[of+1]) << 28 + | hexitValue(ach[of+2]) << 24 + | hexitValue(ach[of+3]) << 20 + | hexitValue(ach[of+4]) << 16 + | hexitValue(ach[of+5]) << 12 + | hexitValue(ach[of+6]) << 8 + | hexitValue(ach[of+7]) << 4 + | hexitValue(ach[of+8]); + + // unfortunately Java does not support characters with code- + // points beyond 16 bits; we could theoretically split this + // up into a Unicode "surrogate pair", but that is not + // supported by this class at this time + ch = nch > Character.MAX_VALUE ? '?' : (char) nch; + of += 9; + cchAdjust += 9; + m_fEscapesEncountered = true; + } + } + + // a negative line offset indicates that the offset is not currently + // being tracked because a line terminator was put back + if (m_iLineOffset >= 0) + { + m_iLineOffset += cchAdjust; + } + } + + m_of = of; + return ch; + } + + /** + * Undo a previously made call to the {@link #next()} method by "rewinding" + * one character. In parsing terminology, this is often referred to as a + * "put back char" operation. + * + * @throws NoSuchElementException if an attempt is made to rewind past the + * beginning + */ + public void rewind() + { + int of = m_of; + if (of <= 0) + { + throw new NoSuchElementException(); + } + + // determine what the immediately preceding character was + --of; + final char[] ach = m_ach; + final char ch = ach[of]; + // if the line feed is immediately preceded by a carriage return, then + // back up past them both (they are treated as a single line feed) + if (isLineTerminator(ch)) + { + if (ch == '\n' && of > 0 && ach[of-1] == '\r') + { + --of; + } + + --m_iLine; + + // instead of determining the line offset in the previous line that + // we just rewound to, defer the calculation until it is needed + m_iLineOffset = -1; + } + else + { + int cchAdjust = 1; + + if (m_fEscapesEncountered + && isHexit(ch) && of >= 5 + && isHexit(ach[of-1]) + && isHexit(ach[of-2]) + && isHexit(ach[of-3])) + { + if (ach[of-5] == '\\' && ach[of-4] == 'u') + { + of -= 5; + cchAdjust += 5; + } + else if (of >= 9 && ach[of-9] == '\\' && ach[of-8] == 'U' + && isHexit(ach[of-7]) + && isHexit(ach[of-6]) + && isHexit(ach[of-5]) + && isHexit(ach[of-4])) + { + of -= 9; + cchAdjust += 9; + } + } + + // a negative line offset indicates that the offset is not currently + // being tracked because a line terminator was put back + if (m_iLineOffset >= 0) + { + m_iLineOffset -= cchAdjust; + } + } + + m_of = of; + } + + /** + * Determine the current line number within the source. + * + * @return the zero-based line number + */ + public int getLine() + { + return m_iLine; + } + + /** + * Determine the offset within the current line of the source. + * + * @return the zero-based offset within the current line + */ + public int getOffset() + { + int iLineOffset = m_iLineOffset; + if (iLineOffset < 0) + { + // go back until a line terminator is found + iLineOffset = 0; + for (int of = m_of; of > 0; ) + { + if (isLineTerminator(m_ach[--of])) + { + break; + } + + ++iLineOffset; + } + + m_iLineOffset = iLineOffset; + } + + return iLineOffset; + } + + /** + * Obtain a token that represents the current location within the source. + * + * @return a position token + */ + public long getPosition() + { + // use the line-offset accessor to force the re-calculation if necessary + final int iLineOffset = getOffset(); + + // up to 24 bits for offset, 20 bits for line and line offset + assert m_of >= 0; + assert m_iLine >= 0; + assert iLineOffset >= 0; + if (m_of > 0xFFFFFF || m_iLine > 0xFFFFF || iLineOffset >= 0xFFFFF) + { + throw new IllegalStateException(); + } + + return (((long) m_of & 0xFFFFFF) << 40) + | (((long) m_iLine & 0x0FFFFF) << 20) + | (((long) iLineOffset & 0x0FFFFF) ); + } + + /** + * Using a previously returned position token, set the current position + * within the source to the position indicated by the token. + * + * @param lPosition a previously returned position token + */ + public void setPosition(long lPosition) + { + m_of = ((int) (lPosition >>> 40)) & 0xFFFFFF; + m_iLine = ((int) (lPosition >>> 20)) & 0x0FFFFF; + m_iLineOffset = ((int) (lPosition )) & 0x0FFFFF; + } + + /** + * Determine the line number from a previously returned position token. + * + * @param lPosition a position token + * + * @return the zero-based line number of the specified position + */ + public static int calculateLine(long lPosition) + { + return ((int) (lPosition >>> 20)) & 0x0FFFFF; + } + + /** + * Determine the offset within the line from a previously returned position + * token. + * + * @param lPosition a position token + * + * @return the zero-based offset within the line of the specified position + */ + public static int calculateOffset(long lPosition) + { + return ((int) lPosition) & 0x0FFFFF; + } + + /** + * Obtain the string of characters starting from one position and proceeding + * to another position. The current position is not affected by this method. + * + * @param lPositionFrom a position token to start from (inclusive) + * @param lPositionTo a position token to end at (exclusive) + * + * @return the String of characters from the first to the second specified + * position + */ + public String toString(long lPositionFrom, long lPositionTo) + { + long lPositionSave = getPosition(); + + setPosition(lPositionFrom); + final int ofEnd = ((int) (lPositionTo >>> 40)) & 0xFFFFFF; + assert ofEnd >= m_of; + char[] ach = new char[ofEnd - m_of]; + int cch = 0; + while (m_of < ofEnd) + { + ach[cch++] = next(); + } + + setPosition(lPositionSave); + return new String(ach, 0, cch); + } + + /** + * @return a clone of this Source, but with the position reset to the beginning of the source + * code + */ + public Source clone() + { + try + { + Source that = (Source) super.clone(); + that.reset(); + return that; + } + catch (CloneNotSupportedException e) + { + throw new RuntimeException(e); + } + } + + /** + * Reset the position to the very beginning of the source code. + */ + public void reset() + { + m_of = 0; + m_iLine = 0; + m_iLineOffset = 0; + } + + /** + * @return a String intended to make this usable in a debugger + */ + public String toString() + { + long lCur = getPosition(); + + String sIntro = "..."; + for (int i = 0; i < 20; ++i) + { + try + { + rewind(); + } + catch (NoSuchElementException e) + { + sIntro = ""; + break; + } + } + long lPre = getPosition(); + setPosition(lCur); + + String sEpilogue = "..."; + for (int i = 0; i < 20; ++i) + { + try + { + next(); + } + catch (NoSuchElementException e) + { + sEpilogue = "(EOF)"; + break; + } + } + long lPost = getPosition(); + setPosition(lCur); + + String sPre = toString(lPre, lCur); + String sPost = toString(lCur, lPost); + + StringBuilder sb = new StringBuilder(sIntro); + appendString(sb, sPre); + char[] achIndent = new char[sb.length()]; + Arrays.fill(achIndent, ' '); + + appendString(sb, sPost) + .append(sEpilogue) + .append('\n') + .append(new String(achIndent)) + .append('^'); + return sb.toString(); + } + + /** + * Obtain the underlying data that the source represents. + * + * @return the whole of the unprocessed source, as a String + */ + public String toRawString() + { + return new String(m_ach); + } + + + // ----- data members -------------------------------------------------------------------------- + + /** + * The source code. + */ + private final char[] m_ach; + + /** + * The length of the source code. + */ + private final int m_cch; + + /** + * The current offset within the source code. + */ + private int m_of; + + /** + * The current source code line number. + */ + private int m_iLine; + + /** + * The current offset within the current line of source code. + */ + private int m_iLineOffset; + + /** + * Set to true iff Unicode escapes have been encountered. + */ + private boolean m_fEscapesEncountered; + + /** + * The file name that the source comes from. + */ + private String m_sFile; + + /** + * The file that the source comes from. + */ + private File m_file; + + /** + * The directory depth within the module of the file that the source comes from. + */ + private int m_cDirDepth; + }
\ No newline at end of file diff --git a/common/src/main/java/com/seaofnodes/simple/lexer/ecstasy/Token.java b/common/src/main/java/com/seaofnodes/simple/lexer/ecstasy/Token.java new file mode 100644 index 00000000..271d8fbc --- /dev/null +++ b/common/src/main/java/com/seaofnodes/simple/lexer/ecstasy/Token.java @@ -0,0 +1,870 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is + * The Ecstasy Project (https://github.com/xtclang/). + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ + +package com.seaofnodes.simple.lexer.ecstasy; + + +import com.seaofnodes.simple.common.ErrorListener; +import com.seaofnodes.simple.common.Severity; + +import java.util.HashMap; +import java.util.Map; + +import static com.seaofnodes.util.Handy.appendChar; +import static com.seaofnodes.util.Handy.appendString; + + +/** + * Representation of a language token. + */ +public class Token + implements Cloneable + { + // ----- constructors -------------------------------------------------------------------------- + + /** + * Construct an XTC token. + * + * @param lStartPos starting position in the Source (inclusive) + * @param lEndPos ending position in the Source (exclusive) + * @param id identity of the token + */ + public Token(long lStartPos, long lEndPos, Id id) + { + this(lStartPos, lEndPos, id, null); + } + + /** + * Construct an XTC token. + * + * @param lStartPos starting position in the Source (inclusive) + * @param lEndPos ending position in the Source (exclusive) + * @param id identity of the token + * @param oValue value of the token (if it is a literal) + */ + public Token(long lStartPos, long lEndPos, Id id, Object oValue) + { + m_lStartPos = lStartPos; + m_lEndPos = lEndPos; + m_id = id; + m_oValue = oValue; + } + + /** + * Record whitespace information onto the token. + * + * @param fWhitespaceBefore + * @param fWhitespaceAfter + */ + public void noteWhitespace(boolean fWhitespaceBefore, boolean fWhitespaceAfter) + { + m_fLeadingWhitespace = fWhitespaceBefore; + m_fTrailingWhitespace = fWhitespaceAfter; + } + + + // ----- accessors ----------------------------------------------------------------------------- + + /** + * Determine the starting position in the source at which this token occurs. + * + * @return the Source position of the token + */ + public long getStartPosition() + { + return m_lStartPos; + } + + /** + * Determine the ending position (exclusive) in the source for this token. + * + * @return the Source position of the end of the token + */ + public long getEndPosition() + { + return m_lEndPos; + } + + /** + * Determine if this token follows whitespace in the source. + * + * @return true iff this token follows whitespace + */ + public boolean hasLeadingWhitespace() + { + return m_fLeadingWhitespace; + } + + /** + * Determine if this token precedes whitespace in the source. + * + * @return true iff this token is followed by whitespace + */ + public boolean hasTrailingWhitespace() + { + return m_fTrailingWhitespace; + } + + /** + * Determine the identity of the token. + * + * @return the identity of the token + */ + public Id getId() + { + return m_id; + } + + /** + * Determine the value of the token. + * + * @return the value of the token, or null + */ + public Object getValue() + { + return m_oValue; + } + + /** + * Helper to get the value as text, if there is a value, otherwise to get the token id's text. + * Use only for debugging or when the token is known to be a String. + * + * @return the String form of the token + */ + public String getValueText() + { + return m_oValue == null ? m_id.TEXT : m_oValue.toString(); + } + + /** + * @return true iff this is an identifier is a "special name" + */ + public boolean isSpecial() + { + if (m_id == Id.IDENTIFIER) + { + Id keywordId = Id.valueByContextSensitiveText((String) getValue()); + return keywordId != null && keywordId.Special; + } + + return false; + } + + /** + * @return true iff this is an identifier is a context-sensitive name + */ + public boolean isContextSensitive() + { + return m_id == Id.IDENTIFIER && Id.valueByContextSensitiveText((String) getValue()) != null; + } + + public boolean isComment() + { + return m_id == Id.ENC_COMMENT || m_id == Id.EOL_COMMENT; + } + + /** + * If the token is an identifier that is also a context sensitive keyword, obtain that keyword. + * + * @return a keyword token that represents the same text as this identifier token + */ + public Token convertToKeyword() + { + if (m_id != Id.IDENTIFIER) + { + throw new IllegalStateException("not an identifier! (" + this + ")"); + } + + Id id = Id.valueByContextSensitiveText((String) getValue()); + if (id == null) + { + throw new IllegalStateException("missing context sensitive keyword for: " + getValue()); + } + + return new Token(m_lStartPos, m_lEndPos, id, m_oValue); + } + + /** + * If the token is a context sensitive keyword that was an identifier, obtain the identifier. + * + * @return a token that is not a context sensitive keyword + */ + public Token desensitize() + { + return m_id.ContextSensitive ? new Token(m_lStartPos, m_lEndPos, Id.IDENTIFIER, m_oValue) : this; + } + + /** + * Refine the token identity to a more specific identity. + * + * @param id the refined identity + */ + Token refine(Id id) + { + m_id = id; + return this; + } + + /** + * Allow a token to be "peeled off" the front of this token, if possible. This mutates this + * token, such that it is what remains after the returned token was peeled off. + * + * @param id the token to peel off of this token + * @param source the source from which this token was created, which is necessary in order to + * calculate the exact position between any peeled-off token and this token + * + * @return the requested token that was peeled off of this token, if possible, otherwise null + */ + public Token peel(Id id, Source source) + { + Id newId = null; + + if (id == Id.COMP_GT) + { + switch (m_id) + { + default: + return null; + + case USHR_ASN: + newId = Id.SHR_ASN; + break; + + case USHR: + newId = Id.SHR; + break; + + case SHR_ASN: + newId = Id.COMP_GTEQ; + break; + + case SHR: + newId = Id.COMP_GT; + break; + + case COMP_GTEQ: + newId = Id.ASN; + break; + } + } + else if (id == Id.COMP_LT) + { + switch (m_id) + { + default: + return null; + + case SHL_ASN: + newId = Id.COMP_LTEQ; + break; + + case SHL: + newId = Id.COMP_LT; + break; + + // note: there are no legitimate use cases for peeling "<" off of "<=" or "<=>" + // case COMP_LTEQ: + // newId = Id.ASN; + // break; + } + } + + if (newId == null) + { + return null; + } + + // get the location of "this" token + long start = m_lStartPos; + + // get the location of the end of the new peeled token / start of this token (adjusted) + long current = source.getPosition(); + source.setPosition(start); + source.next(); + long middle = source.getPosition(); + source.setPosition(current); + + // adjust this token + m_lStartPos = middle; + m_id = newId; + + // return the new token + return new Token(start, middle, id); + } + + /** + * Allow a token to be "un-peeled off" from the front of that following token, if possible. + * + * @param that the token following this token + * + * @return the new token, or null if the two tokens cannot be annealed + */ + public Token anneal(Token that) + { + if (m_id == Id.COMP_LT && this.m_lEndPos == that.m_lStartPos) + { + switch (that.m_id) + { + case COMP_LTEQ: + return new Token(this.m_lStartPos, that.m_lEndPos, Id.SHL_ASN); + + case COMP_LT: + return new Token(this.m_lStartPos, that.m_lEndPos, Id.SHL); + } + } + + return null; + } + + /** + * Obtain the actual string of characters from the source code for this token. + * + * @param source the source code + * + * @return the string of characters corresponding to this token, extracted from the source + */ + public String getString(Source source) + { + return source.toString(m_lStartPos, m_lEndPos); + } + + /** + * Helper to log an error related to this Token. + * + * @param severity the severity level of the error; one of {@link Severity#INFO}, + * {@link Severity#WARNING}, {@link Severity#ERROR}, or {@link Severity#FATAL} + * @param sCode the error code that identifies the error message + * @param aoParam the parameters for the error message; may be null + * + * @return true to attempt to abort the process that reported the error, or false to attempt to + * continue the process + */ + public void log(ErrorListener errs, Source source, Severity severity, String sCode, Object... aoParam) + { + if (aoParam == null || aoParam.length == 0) + { + aoParam = new Object[] {source == null ? toString() : getString(source)}; + } + + errs.log(severity, sCode, aoParam, source, + source == null ? 0L : getStartPosition(), source == null ? 0L : getEndPosition()); + } + + + // ----- Object methods ------------------------------------------------------------------------ + + public String toDebugString() + { + return "[" + + Source.calculateLine(m_lStartPos) + + "," + + Source.calculateOffset(m_lStartPos) + + " - " + + Source.calculateLine(m_lEndPos) + + "," + + Source.calculateOffset(m_lEndPos) + + "] " + this; + } + + @Override + public String toString() + { + StringBuilder sb = new StringBuilder(); + + switch (m_id) + { + case LIT_CHAR: + { + sb.append('\''); + appendChar(sb, (Character) m_oValue); + sb.append('\''); + } + break; + + case LIT_STRING: + sb.append('\"'); + appendString(sb, (String) m_oValue); + sb.append('\"'); + break; + + case LIT_INT: + case LIT_DEC: + case LIT_FLOAT: + sb.append(m_oValue); + break; + + case LIT_BIT: + case LIT_NIBBLE: + case LIT_INT8: + case LIT_INT16: + case LIT_INT32: + case LIT_INT64: + case LIT_INT128: + case LIT_INTN: + case LIT_UINT8: + case LIT_UINT16: + case LIT_UINT32: + case LIT_UINT64: + case LIT_UINT128: + case LIT_UINTN: + case LIT_DEC32: + case LIT_DEC64: + case LIT_DEC128: + case LIT_DECN: + case LIT_FLOAT16: + case LIT_FLOAT32: + case LIT_FLOAT64: + case LIT_FLOAT128: + case LIT_FLOATN: + case LIT_BFLOAT16: + sb.append(m_id.TEXT) + .append(':') + .append(m_oValue); + break; + + case IDENTIFIER: + sb.append("name:") + .append(m_oValue); + break; + + case ENC_COMMENT: + { + String sComment = (String) m_oValue; + if (sComment.length() > 47) + { + sComment = sComment.substring(0, 44) + "..."; + } + appendString(sb.append("/*"), sComment).append("*/"); + } + break; + + case EOL_COMMENT: + { + String sComment = (String) m_oValue; + if (sComment.length() > 50) + { + sComment = sComment.substring(0, 47) + "..."; + } + appendString(sb.append("//"), sComment); + } + break; + + default: + sb.append(m_id.TEXT); + break; + } + + return sb.toString(); + } + + public Token clone() + { + try + { + return (Token) super.clone(); + } + catch (CloneNotSupportedException e) + { + throw new IllegalStateException(e); + } + } + + + // ----- Token identities ---------------------------------------------------------------------- + + /** + * Token Identity. + */ + public enum Id + { + COLON (":" ), + SEMICOLON (";" ), + COMMA ("," ), + DOT ("." ), + I_RANGE_I (".." ), // inclusive range + E_RANGE_I (">.." ), // exclusive start + I_RANGE_E ("..<" ), // exclusive end + E_RANGE_E (">..<" ), // exclusive range + DIR_CUR ("./" ), + DIR_PARENT ("../" ), + STR_FILE ("$" ), + BIN_FILE ("#" ), + AT ("@" ), + COND ("?" ), + L_PAREN ("(" ), + ASYNC_PAREN ("^(" ), + R_PAREN (")" ), + L_CURLY ("{" ), + R_CURLY ("}" ), + L_SQUARE ("[" ), + R_SQUARE ("]" ), + ADD ("+" ), + SUB ("-" ), + MUL ("*" ), + DIV ("/" ), + MOD ("%" ), + DIVREM ("/%" ), + SHL ("<<" ), + SHR (">>" ), + USHR (">>>" ), + BIT_AND ("&" ), + BIT_OR ("|" ), + BIT_XOR ("^" ), + BIT_NOT ("~" ), + NOT ("!" ), + COND_AND ("&&" ), + COND_XOR ("^^" ), + COND_OR ("||" ), + COND_ELSE ("?:" ), + ASN ("=" ), + ADD_ASN ("+=" ), + SUB_ASN ("-=" ), + MUL_ASN ("*=" ), + DIV_ASN ("/=" ), + MOD_ASN ("%=" ), + SHL_ASN ("<<=" ), + SHR_ASN (">>=" ), + USHR_ASN (">>>=" ), + BIT_AND_ASN ("&=" ), + BIT_OR_ASN ("|=" ), + BIT_XOR_ASN ("^=" ), + COND_AND_ASN ("&&=" ), + COND_OR_ASN ("||=" ), + COND_ASN (":=" ), + COND_NN_ASN ("?=" ), // NN -> Not Null + COND_ELSE_ASN("?:=" ), + COMP_EQ ("==" ), + COMP_NEQ ("!=" ), + COMP_ORD ("<=>" ), + COMP_LT ("<" ), + COMP_LTEQ ("<=" ), + COMP_GT (">" ), + COMP_GTEQ (">=" ), + INC ("++" ), + DEC ("--" ), + LAMBDA ("->" ), + ASN_EXPR ("<-" ), + ANY ("_" ), + ALLOW ("allow" , true), + AS ("as" ), + ASSERT ("assert" ), + ASSERT_RND ("assert:rnd" ), + ASSERT_ARG ("assert:arg" ), + ASSERT_BOUNDS("assert:bounds" ), + ASSERT_TODO ("assert:TODO" ), + ASSERT_ONCE ("assert:once" ), + ASSERT_TEST ("assert:test" ), + ASSERT_DBG ("assert:debug" ), + AVOID ("avoid" , true), + BREAK ("break" ), + CASE ("case" ), + CATCH ("catch" ), + CLASS ("class" ), + CONDITIONAL ("conditional" ), + CONST ("const" ), + CONSTRUCT ("construct" ), + CONTINUE ("continue" ), + DEFAULT ("default" ), + DELEGATES ("delegates" , true), + DESIRED ("desired" , true), + DO ("do" ), + ELSE ("else" ), + EMBEDDED ("embedded" , true), + ENUM ("enum" ), + EXTENDS ("extends" , true), + FINALLY ("finally" ), + FOR ("for" ), + FUNCTION ("function" ), + IF ("if" ), + IMMUTABLE ("immutable" ), + IMPLEMENTS ("implements" , true), + IMPORT ("import" ), + INCORPORATES ("incorporates" , true), + INJECT ("inject" , true), + INTERFACE ("interface" ), + INTO ("into" , true), + IS ("is" ), + MIXIN ("mixin" ), + MODULE ("module" ), + NEW ("new" ), + OPTIONAL ("optional" , true), + OUTER ("outer" , true, true), + PACKAGE ("package" ), + PREFER ("prefer" , true), + PRIVATE ("private" ), + PROTECTED ("protected" ), + PUBLIC ("public" ), + REQUIRED ("required" , true), + RETURN ("return" ), + SERVICE ("service" ), + STATIC ("static" ), + STRUCT ("struct" ), + SUPER ("super" , true, true), + SWITCH ("switch" ), + THIS ("this" , true, true), + THIS_CLASS ("this:class" , true, true), + THIS_MODULE ("this:module" , true, true), + THIS_PRI ("this:private" , true, true), + THIS_PRO ("this:protected" , true, true), + THIS_PUB ("this:public" , true, true), + THIS_SERV ("this:service" , true, true), + THIS_STRUCT ("this:struct" , true, true), + THIS_TARGET ("this:target" , true, true), + THROW ("throw" ), + TODO ("TODO" ), + TRY ("try" ), + TYPEDEF ("typedef" ), + USING ("using" ), + VAL ("val" , true), + VAR ("var" , true), + VOID ("void" ), + WHILE ("while" ), + IDENTIFIER (null ), + EOL_COMMENT (null ), + ENC_COMMENT (null ), + LIT_BIT (null ), + LIT_NIBBLE (null ), + LIT_CHAR (null ), + LIT_STRING (null ), + LIT_BINSTR (null ), + LIT_INT (null ), // integer literal + LIT_INTA ("Int" , true, true), // automatically sized integer + LIT_INT8 ("Int8" , true, true), + LIT_INT16 ("Int16" , true, true), + LIT_INT32 ("Int32" , true, true), + LIT_INT64 ("Int64" , true, true), + LIT_INT128 ("Int128" , true, true), + LIT_INTN ("IntN" , true, true), + LIT_UINT8 ("UInt8" , true, true), + LIT_UINTA ("UInt" , true, true), // automatically sized unsigned integer + LIT_UINT16 ("UInt16" , true, true), + LIT_UINT32 ("UInt32" , true, true), + LIT_UINT64 ("UInt64" , true, true), + LIT_UINT128 ("UInt128" , true, true), + LIT_UINTN ("UIntN" , true, true), + LIT_DEC (null ), // decimal floating point literal + LIT_DECA ("Dec" , true, true), // automatically sized decimal + LIT_DEC32 ("Dec32" , true, true), + LIT_DEC64 ("Dec64" , true, true), + LIT_DEC128 ("Dec128" , true, true), + LIT_DECN ("DecN" , true, true), + LIT_FLOAT (null ), // binary floating point literal + LIT_FLOAT8E4 ("Float8e4" , true, true), + LIT_FLOAT8E5 ("Float8e5" , true, true), + LIT_BFLOAT16 ("BFloat16" , true, true), + LIT_FLOAT16 ("Float16" , true, true), + LIT_FLOAT32 ("Float32" , true, true), + LIT_FLOAT64 ("Float64" , true, true), + LIT_FLOAT128 ("Float128" , true, true), + LIT_FLOATN ("FloatN" , true, true), + LIT_DATE (null ), + LIT_TIMEOFDAY(null ), + LIT_TIME (null ), + LIT_TIMEZONE (null ), + LIT_DURATION (null ), + LIT_VERSION (null ), + LIT_PATH (null ), // generated by the Parser, not by the Lexer + TEMPLATE ("{...}" ), // not a real token + EOF ("EOF" ), // end of token stream + ENUM_VAL ("enum-value" ); // not a real token + + /** + * Constructor. + * + * @param sText a textual representation of the token, or null + */ + Id(final String sText) + { + this(sText, false); + } + + /** + * Constructor. + * + * @param sText a textual representation of the token, or null + */ + Id(final String sText, boolean fContextSensitive) + { + this(sText, fContextSensitive, false); + } + + Id(final String sText, boolean fContextSensitive, boolean fSpecial) + { + TEXT = sText; + this.ContextSensitive = fContextSensitive; + this.Special = fSpecial; + } + + @Override + public String toString() + { + return TEXT == null ? super.toString() : '\"' + TEXT + '"'; + } + + /** + * Look up an Id enum by its ordinal. + * + * @param i the ordinal + * + * @return the Format enum for the specified ordinal + */ + public static Id valueOf(int i) + { + return IDs[i]; + } + + /** + * Look up an Id enum by its {@link #TEXT}. + * + * @param sText the textual representation of the Id + * + * @return an instance of Id, or null if there is no matching + * {@link #TEXT} + */ + public static Id valueByText(String sText) + { + return KEYWORDS.get(sText); + } + + /** + * Look up an Id enum by its {@link #TEXT}, including context-sensitive keywords. + * + * @param sText the textual representation of the Id + * + * @return an instance of Id, or null if there is no matching + * {@link #TEXT} + */ + public static Id valueByContextSensitiveText(String sText) + { + return ALL_KEYWORDS.get(sText); + } + + /** + * Look up an Id enum by its {@link #TEXT}, and if it is one of the keywords that has both + * a normal and one-or-more suffixed forms, then return the Id of the normal form. + * + * @param sText the possible keyword + * + * @return the Id of the "normal form" of the keyword, iff suffixed forms also exist + */ + public static Id valueByPrefix(String sText) + { + return PREFIXES.get(sText); + } + + /** + * All of the Format enums. + */ + private static final Id[] IDs = Id.values(); + + /** + * String representations of tokens that have constant representations, excluding context- + * sensitive keywords. + */ + private static final Map<String, Id> KEYWORDS = new HashMap<>(); + /** + * String representations of all tokens that have constant representations. + */ + private static final Map<String, Id> ALL_KEYWORDS = new HashMap<>(); + + /** + * String representations of tokens that have both "normal" and "suffixed" representations. + */ + private static final Map<String, Id> PREFIXES = new HashMap<>(); + + static + { + for (Id id : IDs) + { + String sText = id.TEXT; + if (sText != null && sText.length() > 0) + { + char ch = sText.charAt(0); + if (ch >= 'A' && ch <= 'Z' || ch >= 'a' && ch <= 'z' || ch == '_') + { + ALL_KEYWORDS.put(sText, id); + + if (!id.ContextSensitive) + { + KEYWORDS.put(sText, id); + } + + int ofColon = sText.indexOf(':'); + if (ofColon > 0) + { + Id prefix = ALL_KEYWORDS.get(sText.substring(0, ofColon)); + if (prefix != null) + { + PREFIXES.put(prefix.TEXT, prefix); + } + } + } + } + } + } + + /** + * A textual representation of the token, if it has a constant textual representation; + * otherwise null. + */ + final public String TEXT; + + /** + * True if the token is context-sensitive, i.e. if it is not always a reserved word. + */ + final boolean ContextSensitive; + + /** + * True if the token is a special name. + */ + final boolean Special; + } + + + // ----- data members -------------------------------------------------------------------------- + + /** + * Starting position (inclusive) in the source of this token. + */ + private long m_lStartPos; + + /** + * Ending position (exclusive) in the source of this token. + */ + private final long m_lEndPos; + + /** + * Identifier of the token. + */ + private Id m_id; + + /** + * Value of the Token (if it is a literal). + */ + private final Object m_oValue; + + /** + * Each token knows if it follows whitespace. + */ + private boolean m_fLeadingWhitespace; + + /** + * Each token knows if it has whitespace following. + */ + private boolean m_fTrailingWhitespace; + } diff --git a/src/main/java/com/seaofnodes/util/Ary.java b/common/src/main/java/com/seaofnodes/util/Ary.java index 36654a7f..36654a7f 100644 --- a/src/main/java/com/seaofnodes/util/Ary.java +++ b/common/src/main/java/com/seaofnodes/util/Ary.java diff --git a/src/main/java/com/seaofnodes/util/AryInt.java b/common/src/main/java/com/seaofnodes/util/AryInt.java index 000f4809..000f4809 100644 --- a/src/main/java/com/seaofnodes/util/AryInt.java +++ b/common/src/main/java/com/seaofnodes/util/AryInt.java diff --git a/common/src/main/java/com/seaofnodes/util/Handy.java b/common/src/main/java/com/seaofnodes/util/Handy.java new file mode 100644 index 00000000..f3496f8c --- /dev/null +++ b/common/src/main/java/com/seaofnodes/util/Handy.java @@ -0,0 +1,1778 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is + * The Ecstasy Project (https://github.com/xtclang/). + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ +package com.seaofnodes.util; + + +import java.io.BufferedInputStream; +import java.io.DataInput; +import java.io.DataOutput; +import java.io.EOFException; +import java.io.File; +import java.io.FileInputStream; +import java.io.FileNotFoundException; +import java.io.InputStream; +import java.io.IOException; +import java.io.UTFDataFormatException; + +import java.lang.reflect.Array; + +import java.nio.ByteBuffer; +import java.nio.CharBuffer; + +import java.nio.charset.Charset; + +import java.util.ArrayList; +import java.util.Arrays; + + +/** + * Handy static methods. + */ +public class Handy + { + // ----- String formatting --------------------------------------------------------------------- + + /** + * Take the passed nibble (the low order 4 bits of the int) and return the corresponding hexit + * (hexadecimal digit) in the range of '0' - 'F'. + * + * @param n the nibble value + * + * @return the hexadecimal representation of the passed nibble + */ + public static char nibbleToChar(int n) + { + n = n & 0xF; + return (n <= 9) + ? (char) ('0' + n) + : (char) ('A' - 0xA + n); + } + + /** + * Render the passed byte (the low order 8 bits of the int) into the passed StringBuilder as + * two hexadecimal digits. + * + * @param sb the StringBuilder to append to + * @param n the byte value + * + * @return the StringBuilder + */ + public static StringBuilder appendByteAsHex(StringBuilder sb, int n) + { + return sb.append(nibbleToChar(n >> 4)) + .append(nibbleToChar(n)); + } + + /** + * Format the passed byte (the low order 8 bits of the int) into a String of the form "0xFF". + * + * @param n the byte value + * + * @return a String representation of the byte + */ + public static String byteToHexString(int n) + { + return appendByteAsHex(new StringBuilder(4).append("0x"), n).toString(); + } + + /** + * Append a portion of a byte array to a StringBuilder as a sequence of hex digits. + * + * @param sb the StringBuilder to append to + * @param ab the byte array + * @param of the offset of the first byte in the byte array to render + * @param cb the number bytes from the byte array to render + * + * @return the StringBuilder + */ + public static StringBuilder appendByteArrayAsHex(StringBuilder sb, byte[] ab, int of, int cb) + { + sb.ensureCapacity(sb.length() + cb * 2); + while (--cb >= 0) + { + int n = ab[of++]; + sb.append(nibbleToChar(n >> 4)) + .append(nibbleToChar(n)); + } + return sb; + } + + /** + * Append the contents of a byte array to a StringBuilder as a sequence of hex digits. + * + * @param sb the StringBuilder to append to + * @param ab the byte array + * + * @return the StringBuilder + */ + public static StringBuilder appendByteArrayAsHex(StringBuilder sb, byte[] ab) + { + return appendByteArrayAsHex(sb, ab, 0, ab.length); + } + + /** + * Format a portion of the passed byte array into a String of the form "0x01234FF". + * + * @param ab the byte array + * @param of the offset of the first byte in the byte array to render + * @param cb the number bytes from the byte array to render + * + * @return a String representation of the byte array + */ + public static String byteArrayToHexString(byte[] ab, int of, int cb) + { + return appendByteArrayAsHex(new StringBuilder(2 + cb * 2).append("0x"), + ab, of, cb).toString(); + } + + /** + * Format the passed byte array into a String of the form "0x01234FF". + * + * @param ab the byte array + * + * @return a String representation of the byte array + */ + public static String byteArrayToHexString(byte[] ab) + { + return byteArrayToHexString(ab, 0, ab.length); + } + + /** + * Convert a String of hex digits into a <tt>byte[]</tt>. + * + * @param s a String of hexadecimal digits; the leading "0x" is optional + * + * @return a byte array + */ + public static byte[] hexStringToByteArray(String s) + { + int ofch = 0; + int cch = s.length(); + int ofb = 0; + int cb = (cch + 1) / 2; + + // check for (and skip) the "0x" prefix + if (s.charAt(0) == '0' && (s.charAt(1) == 'x' || s.charAt(1) == 'X')) + { + ofch += 2; + --cb; + } + + final byte[] ab = new byte[cb]; + + // handle the case where the first nibble is an implied (missing) '0' + if ((cch & 0x1) != 0) + { + ab[ofb++] = (byte) hexitValue(s.charAt(ofch++)); + } + + // convert the remaining pairs of hexits to bytes + while (ofch < cch) + { + ab[ofb++] = (byte) (hexitValue(s.charAt(ofch)) << 4 | hexitValue(s.charAt(ofch+1))); + ofch += 2; + } + + return ab; + } + + /** + * Format bytes from the passed byte array as a "hex dump", useful for debugging. + * + * @param ab the byte array + * @param of the offset of the first byte to show in the hex + * dump + * @param cb the number of bytes to show in the hex dump + * @param cBytesPerLine the number of bytes to show in each line of the hex + * dump + * + * @return a String containing the hex dump + */ + public static String byteArrayToHexDump(byte[] ab, int of, int cb, int cBytesPerLine) + { + assert ab != null; + assert of >= 0 && cb >= 0 && of + cb <= ab.length; + assert cBytesPerLine > 0; + + // first figure out how many digits it will take to show the address + final int cchAddr = countHexDigits(of + cb) + 1 & ~0x01; + + // format is 12F0: 00 12 32 A0 ????\n + // line length is addressLen + 4*cbPerLine + 3 + final int cch = cchAddr + cBytesPerLine * 4 + 3; + final char[] ach = new char[cch]; + Arrays.fill(ach, ' '); + ach[cchAddr] = ':'; + ach[cch-1] = '\n'; + + final int cLines = Math.max((cb + cBytesPerLine - 1) / cBytesPerLine, 1); + final StringBuilder sb = new StringBuilder(cLines * cch); + final int ofHex = cchAddr + 2; + final int ofChar = ofHex + cBytesPerLine * 3; + + for (int iLine = 0; iLine < cLines; ++iLine) + { + // format the address + renderIntToHex(of, ach, 0, cchAddr); + + for (int iByte = 0; iByte < cBytesPerLine; ++iByte) + { + if (cb > 0) + { + int b = ab[of]; + renderByteToHex(b, ach, ofHex + iByte * 3); + + char ch = (char) (b & 0xFF); + ach[ofChar + iByte] = Character.isISOControl(ch) ? '.' : ch; + } + else + { + ach[ofHex + iByte * 3 ] = ' '; + ach[ofHex + iByte * 3 + 1] = ' '; + ach[ofChar + iByte ] = ' '; + } + + ++of; + --cb; + } + + sb.append(ach, 0, iLine < cLines - 1 ? cch : cch - 1); + } + + return sb.toString(); + } + + /** + * Format bytes from the passed byte array as a "hex dump", useful for debugging. + * + * @param ab the byte array + * @param cBytesPerLine the number of bytes to show in each line of the hex + * dump + * + * @return a String containing the hex dump + */ + public static String byteArrayToHexDump(byte[] ab, int cBytesPerLine) + { + return byteArrayToHexDump(ab, 0, ab.length, cBytesPerLine); + } + + /** + * Convert an array of bytes to a long value. + * + * @param ab the array of bytes + * @param of the starting index + * + * @return the long value + */ + public static long byteArrayToLong(byte[] ab, int of) + { + return ((long) (ab[of++]) << 56) + + ((long) (ab[of++] & 0xFF) << 48) + + ((long) (ab[of++] & 0xFF) << 40) + + ((long) (ab[of++] & 0xFF) << 32) + + ((long) (ab[of++] & 0xFF) << 24) + + ( (ab[of++] & 0xFF) << 16) + + ( (ab[of++] & 0xFF) << 8 ) + + ( ab[of ] & 0xFF ); + } + + /** + * Produce an array of bytes for the specified long value. + * + * @param l the long value + * + * @return the byte array + */ + static public byte[] toByteArray(long l) + { + return new byte[] + { + (byte) (l >> 56), + (byte) (l >> 48), + (byte) (l >> 40), + (byte) (l >> 32), + (byte) (l >> 24), + (byte) (l >> 16), + (byte) (l >> 8 ), + (byte) l, + }; + } + + /** + * Render the bytes of the specified long value into an array of bytes at the specified location. + * + * @param l the long value + * @param ab the byte array to copy into + * @param ab the byte array offset to write the long value at + * + * @return the byte array + */ + static public void toByteArray(long l, byte[] ab, int of) + { + ab[of++] = (byte) (l >> 56); + ab[of++] = (byte) (l >> 48); + ab[of++] = (byte) (l >> 40); + ab[of++] = (byte) (l >> 32); + ab[of++] = (byte) (l >> 24); + ab[of++] = (byte) (l >> 16); + ab[of++] = (byte) (l >> 8 ); + ab[of ] = (byte) l; + } + + /** + * Determine how many hex digits it will take to render the passed <tt>int</tt> value as an + * <b>unsigned</b> hex value. + * + * @param n the int value, which is treated as an unsigned 32-bit value + * + * @return the number of hex digits required to render the int value + */ + public static int countHexDigits(int n) + { + return Math.max((32 - Integer.numberOfLeadingZeros(n) + 3) / 4, 1); + } + + /** + * Render the passed <tt>int</tt> into the passed StringBuilder as the specified number of hex + * digits. + * + * @param sb the StringBuilder to append to + * @param n the int value + * @param cch the number of hex digits to render + * + * @return the StringBuilder + */ + public static StringBuilder appendIntAsHex(StringBuilder sb, int n, int cch) + { + assert cch >= 0 && cch <= 8; + for (int cBits = (cch-1) * 4; cBits >= 0; cBits -= 4) + { + sb.append(nibbleToChar(n >> cBits)); + } + return sb; + } + + /** + * Render the passed <tt>int</tt> into the passed StringBuilder as 8 hexadecimal digits. + * + * @param sb the StringBuilder to append to + * @param n the int value + * + * @return the StringBuilder + */ + public static StringBuilder appendIntAsHex(StringBuilder sb, int n) + { + return appendIntAsHex(sb, n, 8); + } + + /** + * Format the passed <tt>int</tt> into a String of the form "0x12345678". + * + * @param n the byte value + * + * @return a hexadecimal String representation of the value + */ + public static String intToHexString(int n) + { + return appendIntAsHex(new StringBuilder(10).append("0x"), n).toString(); + } + + /** + * Determine how many hex digits it will take to render the passed <tt>long</tt> value as an + * <b>unsigned</b> hex value. + * + * @param n the long value, which is treated as an unsigned 64-bit value + * + * @return the number of hex digits required to render the long value + */ + public static int countHexDigits(long n) + { + return Math.max((64 - Long.numberOfLeadingZeros(n) + 3) / 4, 1); + } + + /** + * Render the passed <tt>long</tt> into the passed StringBuilder as the specified number of hex + * digits. + * + * @param sb the StringBuilder to append to + * @param n the long value + * @param cch the number of hex digits to render + * + * @return the StringBuilder + */ + public static StringBuilder appendLongAsHex(StringBuilder sb, long n, int cch) + { + assert cch >= 0 && cch <= 16; + for (int cBits = (cch-1) * 4; cBits >= 0; cBits -= 4) + { + sb.append(nibbleToChar((int) (n >> cBits))); + } + return sb; + } + + /** + * Render the passed <tt>long</tt> into the passed StringBuilder as 16 hexadecimal digits. + * + * @param sb the StringBuilder to append to + * @param n the long value + * + * @return the StringBuilder + */ + public static StringBuilder appendLongAsHex(StringBuilder sb, long n) + { + return appendLongAsHex(sb, n, 16); + } + + + /** + * Format the passed <tt>int</tt> into a String of the form "0x12345678". + * + * @param n the byte value + * + * @return a hexadecimal String representation of the value + */ + public static String longToHexString(long n) + { + return appendLongAsHex(new StringBuilder(18).append("0x"), n).toString(); + } + + /** + * Format the specified byte value into the passed char array as two hex digits. + * + * @param n the byte value + * @param ach the char array to render into + * @param of the offset into the char array for the first hex digit + * + * @return the offset of the first character after the two hex digits + */ + public static int renderByteToHex(int n, char[] ach, int of) + { + ach[of ] = nibbleToChar(n >> 4); + ach[of+1] = nibbleToChar(n); + return of + 2; + } + + /** + * Format the specified int value into the passed char array as the specified number of hex + * digits. + * + * @param n the int value + * @param ach the char array to render into + * @param of the offset into the char array for the first hex digit + * @param cch the number of hex digits to render + * + * @return the offset of the first character after the last hex digit + */ + public static int renderIntToHex(int n, char[] ach, int of, int cch) + { + for (int i = 0; i < cch; ++i) + { + ach[of+cch-i-1] = nibbleToChar(n); + n >>>= 4; + } + return of + cch; + } + + /** + * Format the specified long value into the passed char array as the specified number of hex + * digits. + * + * @param n the long value + * @param ach the char array to render into + * @param of the offset into the char array for the first hex digit + * @param cch the number of hex digits to render + * + * @return the offset of the first character after the last hex digit + */ + public static int renderLongToHex(long n, char[] ach, int of, int cch) + { + for (int i = 0; i < cch; ++i) + { + ach[of+cch-i-1] = nibbleToChar((int) n); + n >>>= 4; + } + return of + cch; + } + + /** + * Determine if the specified character is a decimal digit. + * + * @param ch a character + * + * @return true iff the character is a decimal digit + */ + public static boolean isDigit(char ch) + { + return ch >= '0' & ch <= '9'; + } + + /** + * For a decimal digit, determine its integer value. + * + * @param ch a decimal digit + * + * @return the integer value of the specified decimal digit + */ + public static int digitValue(char ch) + { + assert isDigit(ch); + return ch - '0'; + } + + /** + * Determine if the specified character is a hexadecimal digit. + * + * @param ch a character + * + * @return true iff the character is a hexadecimal digit + */ + public static boolean isHexit(char ch) + { + // hexits in the unicode range appear in this order: + // {..., 0, ..., 9, ..., A, ..., F, ..., a, ..., f, ...} + // so a hexit has to be in the range 0..f, and the entire character + // range from 0..f is only 0x36 (so it fits inside a long mask) + return ch >= '0' & ch <= 'f' & ((1L << ('f' - ch)) & + // 3 4 5 6 + // 0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456 + // 0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[/]^_`abcdef + 0b01111111111000000011111100000000000000000000000000111111L) != 0; + } + + /** + * For a hexadecimal digit, determine its integer value. + * + * @param ch a hexadecimal digit + * + * @return the integer value of the specified hexadecimal digit + */ + public static int hexitValue(char ch) + { + assert isHexit(ch); + return ch <= '9' ? ch - '0' : (ch | 0x20) - ('a' - 0xA); + } + + /** + * Determine if the specified character is an ASCII letter, which is in the range 'A' to 'Z', + * or 'a' to 'z'. + * + * @param ch the character to test + * + * @return true iff the character is an ASCII letter + */ + public static boolean isAsciiLetter(char ch) + { + // ASCII letters in the unicode range appear in this order: + // {..., A, ..., Z, ..., a, ..., z, ...} + return ch >= 'A' & ch <= 'z' & ((1L << ('z' - ch)) & + // 4 5 6 7 + // 123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789A + // ABCDEFGHIJKLMNOPQRSTUVWXYZ[/]^_`abcdefghijklmnopqrstuvwxyz + 0b01111111111111111111111111100000011111111111111111111111111L) != 0; + } + + + // ----- String manipulation ------------------------------------------------------------------- + + /** + * Count the number occurrences of the specified character in the passed String. + * + * @param s the String to scan + * @param ch the character to scan for + * + * @return the number of occurrences of the character + */ + public static int countChar(String s, char ch) + { + int c = 0; + int of = s.indexOf(ch); + while (of >= 0) + { + ++c; + of = s.indexOf(ch, of + 1); + } + return c; + } + + /** + * Using the specified delimiter, parse the passed String into an array of Strings, each of + * which occurred in the original String but separated by the specified delimiter. + * + * @param s the String to parse + * @param chDelim the character delimiter + * + * @return the array of Strings parsed from the passed String + */ + public static String[] parseDelimitedString(String s, char chDelim) + { + if (s == null) + { + return null; + } + + if (s.length() == 0) + { + return NO_ARGS; + } + + int of = s.indexOf(chDelim); + if (of < 0) + { + return new String[] {s}; + } + + ArrayList<String> list = new ArrayList<>(); + int ofPrev = 0; + do + { + list.add(s.substring(ofPrev, of)); + ofPrev = of + 1; + of = s.indexOf(chDelim, ofPrev); + } + while (of >= 0); + list.add(s.substring(ofPrev)); + return list.toArray(NO_ARGS); + } + + /** + * Create a string containing the specified number of the specified character. + * + * @param ch the character to duplicate + * @param cch the size of the resulting string + * + * @return a string containing the specified number of the specified character + */ + public static String dup(char ch, int cch) + { + StringBuilder sb = new StringBuilder(cch); + while (cch-- > 0) + { + sb.append(ch); + } + return sb.toString(); + } + + /** + * Indent each line of the passed text by prepending the specified indentation String. + * + * @param sText the text to indent + * @param sIndent the indentation to use + * + * @return the indented String + */ + public static String indentLines(String sText, String sIndent) + { + int cchOld = sText.length(); + if (cchOld == 0) + { + return ""; + } + + int cLines = countChar(sText, '\n') + 1; + int cchNew = cchOld + cLines * sIndent.length(); + StringBuilder sb = new StringBuilder(cchNew); + + int ofLine = 0; + int ofNewline = sText.indexOf('\n'); + while (ofNewline >= 0) + { + if (ofNewline > ofLine) + { + sb.append(sIndent); + } + sb.append(sText, ofLine, ofNewline + 1); + + ofLine = ofNewline + 1; + ofNewline = sText.indexOf('\n', ofLine); + } + + if (ofLine < cchOld) + { + sb.append(sIndent) + .append(sText, ofLine, cchOld); + } + + return sb.toString(); + } + + /** + * Determine if the specified character needs to be escaped in order to be displayed. + * + * @param ch the character to evaluate + * + * @return true iff the character should be escaped in order to be displayed + */ + public static boolean isCharEscaped(char ch) + { + if (ch < 0x80) + { + return ch < 0x20 || ch == '\'' || ch == '\"' || ch == '\\' || ch == 0x7F; + } + else + { + return !Character.isValidCodePoint(ch) || + Character.getType(ch) == Character.CONTROL || + ch == '\u2028' || ch == '\u2029'; + } + } + + /** + * Append the specified character to the StringBuilder, escaping if necessary. + * + * @param sb the StringBuilder to append to + * @param ch the character to escape + * + * @return the StringBuilder + */ + public static StringBuilder appendChar(StringBuilder sb, char ch) + { + if (isCharEscaped(ch)) + { + switch (ch) + { + case '\\': + return sb.append("\\\\"); + case '\b': + return sb.append("\\b"); + case '\f': + return sb.append("\\f"); + case '\n': + return sb.append("\\n"); + case '\r': + return sb.append("\\r"); + case '\t': + return sb.append("\\t"); + case '\'': + return sb.append("\\'"); + case '\"': + return sb.append("\\\""); + case 0x7F: // DEL + return sb.append("\\d"); + default: + return appendIntAsHex(sb.append('\\').append('u'), ch, 4); + } + } + else + { + return sb.append(ch); + } + } + + /** + * Render a character as it would appear as a constant in source code. + * + * @param ch the character to quote + * + * @return a string showing the specified character, escaped if necessary + */ + public static String quotedChar(char ch) + { + return appendChar(new StringBuilder(9).append('\''), ch).append('\'').toString(); + } + + /** + * Append the specified String to the StringBuilder, escaping if and as necessary. + * + * @param sb the StringBuilder to append to + * @param s the String to escape as necessary + * + * @return the StringBuilder + */ + public static StringBuilder appendString(StringBuilder sb, String s) + { + for (int of = 0, cch = s.length(); of < cch; ++of) + { + appendChar(sb, s.charAt(of)); + } + return sb; + } + + /** + * Render a String as it would appear as a constant in source code. + * + * @param s the String to quote + * + * @return a String showing the quoted version of the passed String, + * escaping characters if and when necessary + */ + public static String quotedString(String s) + { + return appendString(new StringBuilder(s.length() + 2).append('\"'), s).append( + '\"').toString(); + } + + + // ----- packed integers ----------------------------------------------------------------------- + + /** + * Read a variable-length encoded integer value from a stream. + * + * @param in a <tt>DataInput</tt> stream to read from + * + * @return a <tt>long</tt> value + * + * @throws IOException if an I/O exception occurs + * @throws NumberFormatException if the integer does not fit into + * a <tt>long</tt> value + */ + public static long readPackedLong(DataInput in) + throws IOException + { + return PackedInteger.readLong(in); + } + + /** + * Write a signed 64-bit integer to a stream using variable-length encoding. + * + * @param out the <tt>DataOutput</tt> stream to write to + * @param n the <tt>long</tt> value to write + * + * @throws IOException if an I/O exception occurs + */ + public static void writePackedLong(DataOutput out, long n) + throws IOException + { + PackedInteger.writeLong(out, n); + } + + /** + * Read a variable-length encoded 32-bit integer from a stream. + * + * @param in a <tt>DataInput</tt> stream to read from + * + * @return an <tt>int</tt> value in the range <tt>Integer.MIN_VALUE..Integer.MAX_VALUE</tt> + * + * @throws java.io.IOException if an I/O exception occurs + */ + public static int readPackedInt(DataInput in) + throws IOException + { + long n = readPackedLong(in); + if (n < Integer.MIN_VALUE || n > Integer.MAX_VALUE) + { + throw new IOException("value (" + n + ") exceeds 32-bit range"); + } + + return (int) n; + } + + /** + * Read a variable-length encoded 32-bit integer magnitude from a stream. + * <p> + * Note that while the XVM itself is a 64-bit machine, Java does not support 64-bit (or even + * unsigned 32-bit) magnitudes. This method is a convenience method that verifies that the + * magnitude is within a range supported by Java. + * + * @param in a <tt>DataInput</tt> stream to read from + * + * @return an <tt>int</tt> value in the range <tt>0..Integer.MAX_VALUE</tt> + * + * @throws java.io.IOException if an I/O exception occurs + */ + public static int readMagnitude(DataInput in) + throws IOException + { + long n = readPackedLong(in); + if (n > Integer.MAX_VALUE) + { + // this is unsupported in Java; arrays are limited in size + // by their use of signed 32-bit magnitudes and indexes + throw new IOException("magnitude (" + n + ") exceeds 32-bit maximum"); + } + else if (n < 0) + { + throw new IOException("negative magnitude (" + n + ") is illegal"); + } + + return (int) n; + } + + /** + * Read a variable-length encoded 32-bit integer index from a stream. + * <p> + * Note that while the XVM itself is a 64-bit machine, Java does not support 64-bit (or even + * unsigned 32-bit) indexes. This method is a convenience method that verifies that the index is + * within a range supported by Java. + * + * @param in a <tt>DataInput</tt> stream to read from + * + * @return an <tt>int</tt> value in the range <tt>0..Integer.MAX_VALUE</tt>, + * or <tt>-1</tt> + * + * @throws java.io.IOException if an I/O exception occurs + */ + public static int readIndex(DataInput in) + throws IOException + { + long n = readPackedLong(in); + if (n > Integer.MAX_VALUE) + { + // this is unsupported in Java; arrays are limited in size + // by their use of signed 32-bit magnitudes and indexes + throw new IOException("index (" + n + ") exceeds 32-bit maximum"); + } + else if (n < -1) + { + throw new IOException("negative index (" + n + ") is illegal"); + } + + return (int) n; + } + + + // ----- unicode ------------------------------------------------------------------------------- + + /** + * Read a single unicode character (code-point) from the passed DataInput, encoded using the + * UTF-8 format. + * + * @param in the DataInput to read from + * + * @return a Unicode code-point (which can exceed the 16-bit <tt>char</tt> + * type in Java) + * + * @throws IOException if an I/O exception occurs while reading the data, + * or if a UTF-8 format error is detected + */ + public static int readUtf8Char(DataInput in) + throws IOException + { + int b = in.readUnsignedByte(); + if ((b & 0x80) == 0) + { + // ASCII - single byte 0xxxxxxx format + return b; + } + + // otherwise the format is based on the number of high-order 1-bits: + // #1s first byte trailing # trailing bits code-points + // --- ---------- -------- ---------- ---- ----------------------- + // 2 110xxxxx 10xxxxxx 1 11 U+0080 - U+07FF + // 3 1110xxxx 10xxxxxx 2 16 U+0800 - U+FFFF + // 4 11110xxx 10xxxxxx 3 21 U+10000 - U+1FFFFF + // 5 111110xx 10xxxxxx 4 26 U+200000 - U+3FFFFFF + // 6 1111110x 10xxxxxx 5 31 U+4000000 - U+7FFFFFFF + switch (Integer.highestOneBit(~(0xFFFFFF00 | b))) + { + case 0b00100000: // 2-byte format + return (b & 0b00011111) << 6 | nextCharBits(in); + case 0b00010000: // 3-byte format + return (b & 0b00001111) << 12 | nextCharBits(in) << 6 | nextCharBits(in); + case 0b00001000: // 4-byte format + return (b & 0b00000111) << 18 | nextCharBits(in) << 12 | nextCharBits(in) << 6 | nextCharBits(in); + case 0b00000100: // 5-byte format + return (b & 0b00000011) << 24 | nextCharBits(in) << 18 | nextCharBits(in) << 12 | nextCharBits(in) << 6 | nextCharBits(in); + case 0b00000010: // 6-byte format + return (b & 0b00000001) << 30 | nextCharBits(in) << 24 | nextCharBits(in) << 18 | nextCharBits(in) << 12 | nextCharBits(in) << 6 | nextCharBits(in); + default: + throw new UTFDataFormatException("initial byte: " + byteToHexString(b)); + } + } + + /** + * Internal: Read a UTF-8 continuation byte and validate/decode it. + * + * @param in the DataInput to read from + * + * @return the 6 bits of UTF-8 data from the continuation byte + * + * @throws IOException if an I/O exception occurs while reading the data, + * or if a UTF-8 format error is detected + */ + private static int nextCharBits(DataInput in) + throws IOException + { + int n = in.readUnsignedByte(); + if ((n & 0b11000000) != 0b10000000) + { + throw new UTFDataFormatException("trailing unicode byte does not match 10xxxxxx"); + } + return n & 0b00111111; + } + + /** + * Write a single unicode character (code-point) to the passed DataOutput, encoding using the + * UTF-8 format. + * + * @param out the DataOutput to write to + * @param ch the char to write out as UTF-8 + * + * @return a Unicode code-point (which can exceed the 16-bit <tt>char</tt> + * type in Java) + * + * @throws IOException if an I/O exception occurs while writing the data, + * or if a UTF-8 format error is detected + */ + public static void writeUtf8Char(DataOutput out, int ch) + throws IOException + { + if ((ch & ~0x7F) == 0) + { + // ASCII - single byte 0xxxxxxx format + out.write(ch); + return; + } + + // otherwise the format is based on the number of significant bits: + // bits code-points first byte trailing # trailing + // ---- ----------------------- ---------- -------- ---------- + // 11 U+0080 - U+07FF 110xxxxx 10xxxxxx 1 + // 16 U+0800 - U+FFFF 1110xxxx 10xxxxxx 2 + // 21 U+10000 - U+1FFFFF 11110xxx 10xxxxxx 3 + // 26 U+200000 - U+3FFFFFF 111110xx 10xxxxxx 4 + // 31 U+4000000 - U+7FFFFFFF 1111110x 10xxxxxx 5 + int cTrail; + switch (Integer.highestOneBit(ch)) + { + case 0b00000000000000000000000010000000: + case 0b00000000000000000000000100000000: + case 0b00000000000000000000001000000000: + case 0b00000000000000000000010000000000: + out.write(0b11000000 | ch >>> 6); + cTrail = 1; + break; + + case 0b00000000000000000000100000000000: + case 0b00000000000000000001000000000000: + case 0b00000000000000000010000000000000: + case 0b00000000000000000100000000000000: + case 0b00000000000000001000000000000000: + out.write(0b11100000 | ch >>> 12); + cTrail = 2; + break; + case 0b00000000000000010000000000000000: + case 0b00000000000000100000000000000000: + case 0b00000000000001000000000000000000: + case 0b00000000000010000000000000000000: + case 0b00000000000100000000000000000000: + out.write(0b11110000 | ch >>> 18); + cTrail = 3; + break; + case 0b00000000001000000000000000000000: + case 0b00000000010000000000000000000000: + case 0b00000000100000000000000000000000: + case 0b00000001000000000000000000000000: + case 0b00000010000000000000000000000000: + out.write(0b11111000 | ch >>> 24); + cTrail = 4; + break; + case 0b00000100000000000000000000000000: + case 0b00001000000000000000000000000000: + case 0b00010000000000000000000000000000: + case 0b00100000000000000000000000000000: + case 0b01000000000000000000000000000000: + out.write(0b11111100 | ch >>> 30); + cTrail = 5; + break; + + default: + throw new UTFDataFormatException("illegal character: " + intToHexString(ch)); + } + + // write out trailing bytes; each has the same "10xxxxxx" format with 6 + // bits of data + while (cTrail > 0) + { + out.write(0b10_000000 | (ch >>> --cTrail * 6 & 0b00_111111)); + } + } + + /** + * Read a length-encoded string of unicode characters (code-point) from the passed DataInput, + * encoded using the UTF-8 format. The format is the number of bytes in the stream used for the + * UTF-8 character encoding, encoded as a packed integer, followed by the difference in the + * number of bytes and the number of characters, the difference being 0 or greater, encoded as + * a packed integer, followed by the specified number of characters, encoded using UTF-8. + * + * @param in the DataInput to read from + * + * @return a Unicode code-point (which can exceed the 16-bit <tt>char</tt> + * type in Java) + * + * @throws IOException if an I/O exception occurs while reading the data, + * or if a UTF-8 format error is detected + */ + public static String readUtf8String(DataInput in) + throws IOException + { + int cb = readMagnitude(in); + int cch = cb - readMagnitude(in); + StringBuilder sb = new StringBuilder(cch); + for (int ofch = 0; ofch < cch; ++ofch) + { + int ch = readUtf8Char(in); + if (ch >= 0xFFFF) + { + if (!Character.isSupplementaryCodePoint(ch)) + { + throw new UTFDataFormatException( + "Character is outside of UTF-16 (including supplemental) range: " + + intToHexString(ch)); + } + + // the "supplemental" range is composed of two UTF-16 characters + sb.append(Character.highSurrogate(ch)) // "leading" + .append(Character.lowSurrogate(ch)); // "trailing" + } + else + { + sb.append((char) ch); + } + } + + return sb.toString(); + } + + /** + * Write a length-encoded string of unicode characters (code-points) to the passed DataOutput, + * encoding using the UTF-8 format. The length encoding is the number of bytes in the stream + * used for the UTF-8 character encoding, encoded as a packed integer, followed by the + * difference in the number of bytes and the number of characters, the difference being 0 or + * greater, encoded as a packed integer. + * + * @param out the DataOutput to write to + * @param s the String to write out as UTF-8 + * + * @throws IOException if an I/O exception occurs while writing the data, + * or if a UTF-8 format error is detected + */ + public static void writeUtf8String(DataOutput out, String s) + throws IOException + { + // figure out the actual number of unicode code-points (not the number + // of "Java chars") and how many bytes the UTF-8 format will use + final int cch = s.length(); // count of UTF-16 "Java chars" + final int[] anch = new int[cch]; // array of unicode code points + int cb = 0; // count of bytes + int cnch = 0; // count of unicode code points + for (int ofch = 0; ofch < cch; ++ofch) + { + char ch = s.charAt(ofch); + int nch; + if (Character.isSurrogate(ch)) + { + // first character must be a high surrogate + if (!Character.isHighSurrogate(ch)) + { + throw new UTFDataFormatException( + "low surrogate unexpected: " + intToHexString(ch)); + } + + // next character must be a low surrogate + char ch2; + if (++ofch >= cch || !Character.isLowSurrogate(ch2 = s.charAt(ofch))) + { + throw new UTFDataFormatException( + "low surrogate expected after: " + intToHexString(ch)); + } + + nch = Character.toCodePoint(ch, ch2); + } + else + { + nch = ch; + } + + anch[cnch++] = nch; + cb += calcUtf8Length(nch); + } + + // write out the UTF-8 form of the String + assert cb >= cnch; + writePackedLong(out, cb); + writePackedLong(out, cb - cnch); + for (int of = 0; of < cnch; ++of) + { + writeUtf8Char(out, anch[of]); + } + } + + /** + * Internal: Calculate the UTF-8 length for a particular code-point. + * + * @param ch the unicode character + * + * @return the number of bytes required to format the unicode character to + * UTF-8 + * + * @throws UTFDataFormatException if an invalid character is passed + */ + private static int calcUtf8Length(int ch) + throws IOException + { + if ((ch & ~0x7F) == 0) + { + // ASCII - single byte 0xxxxxxx format + return 1; + } + + switch (Integer.highestOneBit(ch)) + { + case 0b00000000000000000000000010000000: + case 0b00000000000000000000000100000000: + case 0b00000000000000000000001000000000: + case 0b00000000000000000000010000000000: + return 2; + + case 0b00000000000000000000100000000000: + case 0b00000000000000000001000000000000: + case 0b00000000000000000010000000000000: + case 0b00000000000000000100000000000000: + case 0b00000000000000001000000000000000: + return 3; + + case 0b00000000000000010000000000000000: + case 0b00000000000000100000000000000000: + case 0b00000000000001000000000000000000: + case 0b00000000000010000000000000000000: + case 0b00000000000100000000000000000000: + return 4; + + case 0b00000000001000000000000000000000: + case 0b00000000010000000000000000000000: + case 0b00000000100000000000000000000000: + case 0b00000001000000000000000000000000: + case 0b00000010000000000000000000000000: + return 5; + + case 0b00000100000000000000000000000000: + case 0b00001000000000000000000000000000: + case 0b00010000000000000000000000000000: + case 0b00100000000000000000000000000000: + case 0b01000000000000000000000000000000: + return 6; + + default: + throw new UTFDataFormatException("illegal character: " + intToHexString(ch)); + } + } + + // ----- file I/O ------------------------------------------------------------------------------ + + /** + * Open the specified file as an InputStream. + * + * @param file the file to open + * + * @return an InputStream to the specified file + * + * @throws IOException if an IOException occurs while reading the + * FileStructure + */ + public static InputStream toInputStream(File file) + throws IOException + { + if (!file.exists()) + { + throw new IOException("file does not exist: " + file); + } + + if (!file.isFile() || !file.canRead()) + { + throw new IOException("not a readable file: " + file); + } + + return new BufferedInputStream(new FileInputStream(file)); + } + + /** + * Read the raw bytes contained in the specified file. + * + * @param file the file to read + * + * @return the binary contents of the file + * + * @throws IOException indicates a failure to read the binary contents + * of the specified file + */ + public static byte[] readFileBytes(File file) + throws IOException + { + if (file == null) + { + throw new IllegalArgumentException("file required"); + } + + if (!file.exists() || !file.isFile()) + { + throw new FileNotFoundException(file.toString()); + } + + final long lcb = file.length(); + if (lcb == 0L) + { + return EMPTY_BYTE_ARRAY; + } + else if (lcb > Integer.MAX_VALUE - 1024) + { + // assume a maximum byte array size just under 2GB + throw new IOException("file exceeds max supported length (2GB): " + + file + "=" + lcb + " bytes"); + } + + // read the complete contents of the file + int cb = (int) lcb; + byte[] ab = new byte[cb]; + try (FileInputStream stream = new FileInputStream(file)) + { + for (int of = 0; of < cb; ) + { + int cbChunk = stream.read(ab, of, cb-of); + if (cbChunk < 0) + { + throw new EOFException("unexpected end-of-file: " + file); + } + of += cbChunk; + } + } + + if (file.length() != lcb) + { + throw new IOException("file was concurrently modified while being read: " + file); + } + + return ab; + } + + /** + * Read the text contents of the specified file. Supported formats are ASCII, UTF-8, UTF-16, and + * UTF-32; failure to identify any of those formats will cause the default encoding to be used. + * + * @param file the file to read + * + * @return the character contents of the file + * + * @throws IOException indicates a failure to read the character contents + * of the specified file + */ + public static char[] readFileChars(File file) + throws IOException + { + return readFileChars(file, null); + } + + /** + * Read the text contents of the specified file using the specified encoding. If no encoding is + * specified, then determine the encoding in the manner specified by {@link #readFileChars(File)}. + * + * @param file the file to read + * @param sEncoding the specific encoding to use, or null to attempt to + * determine the encoding automatically + * + * @return the character contents of the file + * + * @throws IOException indicates a failure to read the character contents + * of the specified file + */ + public static char[] readFileChars(File file, String sEncoding) + throws IOException + { + byte[] ab = readFileBytes(file); + int cb = ab.length; + if (cb == 0) + { + return EMPTY_CHAR_ARRAY; + } + + // check to see if there is a byte order mark + int cbBOM = 0; + if (sEncoding == null) + { + switch (cb) + { + default: + if (ab[0] == 0x00 && ab[1] == 0x00 && (ab[2] & 0xFF) == 0xFE && (ab[3] & 0xFF) == 0xFF) + { + sEncoding = "UTF-32BE"; + cbBOM = 4; + break; + } + else if ((ab[0] & 0xFF) == 0xFF && (ab[1] & 0xFF) == 0xFE && ab[2] == 0x00 && ab[3] == 0x00) + { + sEncoding = "UTF-32LE"; + cbBOM = 4; + break; + } + case 3: + if ((ab[0] & 0xFF) == 0xEF && (ab[1] & 0xFF) == 0xBB && (ab[2] & 0xFF) == 0xBF) + { + sEncoding = "UTF-8"; + cbBOM = 3; + break; + } + case 2: + if ((ab[0] & 0xFF) == 0xFE && (ab[1] & 0xFF) == 0xFF) + { + sEncoding = "UTF-16BE"; + cbBOM = 2; + break; + } + else if ((ab[0] & 0xFF) == 0xFF && (ab[1] & 0xFF) == 0xFE) + { + sEncoding = "UTF-16LE"; + cbBOM = 2; + break; + } + case 1: + case 0: + } + } + + scan: if (sEncoding == null) + { + // quick scan to verify that the contents are ASCII + char[] ach = new char[cb]; + for (int of = 0; of < cb; ++of) + { + int b = ab[of] & 0xFF; + if (b > 0x7F) + { + // use default encoding + break scan; + } + ach[of] = (char) (b & 0xFF); + } + return ach; + } + + // use the encoding that was specified or otherwise determined, or fall + // back to the default encoding + Charset charset = sEncoding == null ? Charset.defaultCharset() : Charset.forName(sEncoding); + ByteBuffer bytebuf = ByteBuffer.wrap(ab, cbBOM, cb - cbBOM); + CharBuffer charbuf = charset.decode(bytebuf); + char[] ach = new char[charbuf.length()]; + charbuf.get(ach); + return ach; + } + + + // ----- array and collection helpers ---------------------------------------------------------- + + /** + * Given an array of "base" elements and an array of elements that are being evaluated as some + * form of "addition" to those base elements, determine if there are any duplicates, and return + * an array that contains the non-duplicates. + * + * @param aoBase the array of "base" elements + * @param aoAdd the array of the elements being evaluated in addition to the base elements + * + * @return an array containing all of the elements from the {@code aoAdd} array that are not + * duplicates of elements in the {@code aoBase} array + */ + public static <T> T[] dedupAdds(T[] aoBase, T[] aoAdd) + { + // there's a fair likelihood that *ALL* of the "adds" will be duplicates, and a fair + // likelihood that *NONE* of the "adds" will be unique, so assume both up front, and only + // de-optimize when *BOTH* of those two things have been proven to be false + int cBase = aoBase.length; + int cAdd = aoAdd.length; + boolean fAllDups = true; + boolean fNoDups = true; + ArrayList<T> listDeDup = null; + NextLayer: for (int iAdd = 0; iAdd < cAdd; ++iAdd) + { + T oAdd = aoAdd[iAdd]; + for (int iBase = 0; iBase < cBase; ++iBase) + { + if (oAdd.equals(aoBase[iBase])) + { + // we found a duplicate; is it the first one? + if (fNoDups) + { + fNoDups = false; + + // if we already know that there are some that are NOT duplicates, then we + // need to start maintaining a list of non-duplicates to add; since this is + // the first duplicate encountered, just take everything up to this point + if (!fAllDups) + { + assert listDeDup == null; + listDeDup = startList(aoAdd, iAdd); + } + } + + // this one was a duplicate, so advance to the next thing to add + continue NextLayer; + } + } + + // this one to add is NOT a duplicate; is it the first one? + if (fAllDups) + { + fAllDups = false; + + // if we already know that there are duplicates (i.e. NOT no duplicates), then we + // need to start maintaining a list of non-duplicates (starting with this one) + if (!fNoDups) + { + assert listDeDup == null; + listDeDup = new ArrayList<>(); + } + } + + // if, for whatever reason, we are maintaining a list of non-duplicates by this point, + // and since we just verified that this is a non-duplicate, then add it to the list + if (listDeDup != null) + { + listDeDup.add(oAdd); + } + } + + // at this point, we finished our check for duplicates; if there are no duplicates, then + // the original array of things to add is the result + if (fNoDups) + { + assert listDeDup == null; + return aoAdd; + } + + // otherwise, there are duplicates, which boils down into two possibilities: they're all + // duplicates (so we return an empty array), or just some are duplicates (in which case + // there is a list of the ones that are NOT duplicates that we should return) + int cResult = listDeDup == null ? 0 : listDeDup.size(); + T[] aoResult = (T[]) Array.newInstance(aoAdd.getClass().getComponentType(), cResult); + if (cResult > 0) + { + aoResult = listDeDup.toArray(aoResult); + } + return aoResult; + } + + /** + * Glue two arrays together. + * + * @param aoBase the first array + * @param aoAdd the second array + * + * @return an array containing all of the elements of both passed arrays + */ + public static <T> T[] append(T[] aoBase, T[] aoAdd) + { + int cBase = aoBase.length; + if (cBase == 0) + { + return aoAdd; + } + + int cAdd = aoAdd.length; + if (cAdd == 0) + { + return aoBase; + } + + int cResult = cBase + cAdd; + T[] aoResult = (T[]) Array.newInstance(aoAdd.getClass().getComponentType(), cResult); + System.arraycopy(aoBase, 0, aoResult, 0, cBase); + System.arraycopy(aoAdd, 0, aoResult, cBase, cAdd); + return aoResult; + } + + /** + * Add the specified element at the top of the specified array. + * + * @param aoBase the array to add to + * @param oAdd the element to append at the head + * + * @return an array containing all the elements + */ + public static <T> T[] appendHead(T[] aoBase, T oAdd) + { + int c = aoBase.length; + T[] aNew = (T[]) Array.newInstance(oAdd.getClass(), c + 1); + + aNew[0] = oAdd; + System.arraycopy(aoBase, 0, aNew, 1, c); + return aNew; + } + + /** + * Create an ArrayList that contains the first {@code c} elements of the array {@code ao}. + * + * @param ao an array of T + * @param c the number of elements of the array to put into the new list + * + * @return a new ArrayList of the first {@code c} elements of the {@code ao} array + */ + public static <T> ArrayList<T> startList(T[] ao, int c) + { + return appendList(new ArrayList<>(), ao, 0, c); + } + + /** + * Append the specified elements from the passed array to the list. + * + * @param list a list of T to add to + * @param ao an array of T to obtain the values-to-add from + * @param of the offset into the array + * @param c the number of elements from the array to add to the list + * + * @return the list + */ + public static <T> ArrayList<T> appendList(ArrayList<T> list, T[] ao, int of, int c) + { + for (int ofEnd = of+c; of < ofEnd; ++of) + { + list.add(ao[of]); + } + return list; + } + + + // ----- hashing & equality -------------------------------------------------------------------- + + /** + * Perform a hash of the object. This performs a deep hash on arrays. + * + * @param o any object, or null + * + * @return a hashcode + */ + public static int hashCode(final Object o) + { + return Hash.of(o); + } + + /** + * Perform a comparison for equality. The types of the objects must be equal + * as well. This performs a deep comparison on arrays. + * + * @param o1 any object, or null + * @param o2 any object, or null + * + * @return true iff <tt>o1</tt> is equals to <tt>o2</tt> + */ + public static boolean equals(final Object o1, final Object o2) + { + if (o1 == null) + { + return o2 == null; + } + if (o2 == null) + { + return false; + } + + final Class clz1 = o1.getClass(); + final Class clz2 = o1.getClass(); + if (clz1 != clz2) + { + return false; + } + + Class<?> clzComp = clz1.getComponentType(); + return clzComp == null || clzComp != clz2.getComponentType() + ? o1.equals(o2) + : clzComp.isPrimitive() + ? clzComp == int .class ? Arrays.equals( (int[]) o1, (int[]) o2) + : clzComp == long .class ? Arrays.equals( (long[]) o1, (long[]) o2) + : clzComp == byte .class ? Arrays.equals( (byte[]) o1, (byte[]) o2) + : clzComp == char .class ? Arrays.equals( (char[]) o1, (char[]) o2) + : clzComp == double.class ? Arrays.equals( (double[]) o1, (double[]) o2) + : clzComp == float .class ? Arrays.equals( (float[]) o1, (float[]) o2) + : clzComp == short .class ? Arrays.equals( (short[]) o1, (short[]) o2) + : Arrays.equals((boolean[]) o1, (boolean[]) o2) + : Arrays.equals((Object[]) o1, (Object[]) o2); + } + + /** + * Perform a comparison of two arrays for ordering. This performs a deep + * comparison on the arrays. + * + * @param ao1 an array of Comparable, or null + * @param ao2 an array of Comparable, or null + * + * @return negative, zero, or positive iff <tt>ao1</tt> is less than, equal + * to, or greater than <tt>ao2</tt> + */ + public static int compareArrays(final Comparable[] ao1, final Comparable[] ao2) + { + if (ao1 == ao2) + { + return 0; + } + + if (ao1 == null) + { + return -1; + } + + if (ao2 == null) + { + return 1; + } + + final int c1 = ao1.length; + final int c2 = ao2.length; + for (int i = 0, c = Math.min(c1, c2); i < c; ++i) + { + final int n = ao1[i].compareTo(ao2[i]); + if (n != 0) + { + return n; + } + } + + return c1 - c2; + } + + /** + * Verify that the array is non-null and all elements are non-null. + * + * @param ao an array of objects + * + * @return true iff all elements are non-null + * + * @throws IllegalArgumentException if the array is null, or any elements + * of the array are null + */ + public static boolean checkElementsNonNull(Object[] ao) + { + if (ao == null) + { + throw new IllegalArgumentException("array is null"); + } + + for (Object o : ao) + { + if (o == null) + { + throw new IllegalArgumentException("array element is null"); + } + } + + return true; + } + + + // ----- constants ----------------------------------------------------------------------------- + + /** + * A constant empty array of <tt>byte</tt>. + */ + public final static byte[] EMPTY_BYTE_ARRAY = new byte[0]; + + /** + * A constant empty array of <tt>char</tt>. + */ + public final static char[] EMPTY_CHAR_ARRAY = new char[0]; + + /** + * A constant empty array of <tt>String</tt>. + */ + public final static String[] NO_ARGS = new String[0]; + }
\ No newline at end of file diff --git a/common/src/main/java/com/seaofnodes/util/Hash.java b/common/src/main/java/com/seaofnodes/util/Hash.java new file mode 100644 index 00000000..65626755 --- /dev/null +++ b/common/src/main/java/com/seaofnodes/util/Hash.java @@ -0,0 +1,299 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is + * The Ecstasy Project (https://github.com/xtclang/). + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ +package com.seaofnodes.util; + +import java.util.Arrays; + +/** + * Helper functions for producing compound hashes. + * + * <p> + * For example given a class with fields {@code a, b, c, d} of any type, a compound hash can be + * computed via: + * <pre>{@code + * int hash = Hash.of(a, + * Hash.of(b, + * Hash.of(c, + * Hash.of(d)))); + * } + * </pre> + * + * @author mf + */ +public final class Hash + { + private Hash() + { + // blocked constructor + } + + /** + * Incorporate a value into a running hash. + * + * @param v the value (or hash) to incorporate into the running hash + * @param h the running hash to combine with + * + * @return the compound hash + */ + public static int of(int v, int h) + { + return 31 * h + v; + } + + /** + * Incorporate a value into a running hash. + * + * @param v the value to incorporate into the hash + * @param h the running hash to combine with + * + * @return the compound hash + */ + public static int of(boolean v, int h) + { + return of(of(v), h); + } + + /** + * Incorporate a value into a running hash. + * + * @param v the value to incorporate into the hash + * @param h the running hash to combine with + * + * @return the compound hash + */ + public static int of(byte v, int h) + { + return of(of(v), h); + } + + /** + * Incorporate a value into a running hash. + * + * @param v the value to incorporate into the hash + * @param h the running hash to combine with + * + * @return the compound hash + */ + public static int of(char v, int h) + { + return of(of(v), h); + } + + /** + * Incorporate a value into a running hash. + * + * @param v the value to incorporate into the hash + * @param h the running hash to combine with + * + * @return the compound hash + */ + public static int of(short v, int h) + { + return of(of(v), h); + } + + /** + * Incorporate a value into a running hash. + * + * @param v the value to incorporate into the hash + * @param h the running hash to combine with + * + * @return the compound hash + */ + public static int of(float v, int h) + { + return of(of(v), h); + } + + /** + * Incorporate a value into a running hash. + * + * @param v the value to incorporate into the hash + * @param h the running hash to combine with + * + * @return the compound hash + */ + public static int of(long v, int h) + { + return of(of(v), h); + } + + /** + * Incorporate a value into a running hash. + * + * @param v the value to incorporate into the hash + * @param h the running hash to combine with + * + * @return the compound hash + */ + public static int of(double v, int h) + { + return of(of(v), h); + } + + /** + * Incorporate a value into a running hash. + * + * @param v the value to incorporate into the hash + * @param h the running hash to combine with + * + * @return the compound hash + */ + public static int of(Object v, int h) + { + return of(of(v), h); + } + + /** + * Return a hash of the value. + * + * @param v the value + * + * @return the hash + */ + public static int of(boolean v) + { + return Boolean.hashCode(v); + } + + /** + * Return a hash of the value. + * + * @param v the value + * + * @return the hash + */ + public static int of(byte v) + { + return Byte.hashCode(v); + } + + /** + * Return a hash of the value. + * + * @param v the value + * + * @return the hash + */ + public static int of(short v) + { + return Short.hashCode(v); + } + + /** + * Return a hash of the value. + * + * @param v the value + * + * @return the hash + */ + public static int of(char v) + { + return Character.hashCode(v); + } + + /** + * Return a hash of the value. + * + * @param v the value + * + * @return the hash + */ + public static int of(int v) + { + return Integer.hashCode(v); + } + + /** + * Return a hash of the value. + * + * @param v the value + * + * @return the hash + */ + public static int of(float v) + { + return Float.hashCode(v); + } + + /** + * Return a hash of the value. + * + * @param v the value + * + * @return the hash + */ + public static int of(long v) + { + return Long.hashCode(v); + } + + /** + * Return a hash of the value. + * + * @param v the value + * + * @return the hash + */ + public static int of(double v) + { + return Double.hashCode(v); + } + + /** + * Return a hash of the value. + * + * <p> + * If the value is an array the hash will be via {@link java.util.Arrays#hashCode}. + * + * @param v the value + * + * @return the hash + */ + public static int of(Object v) + { + return v == null + ? 0 + : v.getClass().isArray() + ? ofArray(v) + : v.hashCode(); + } + + /** + * Return the hash of an array. + * + * @param v the non-null array + * + * @return the hash + */ + private static int ofArray(Object v) + { + Class<?> clzComp = v.getClass().getComponentType(); + return + clzComp.isPrimitive() + ? clzComp == int .class ? Arrays.hashCode( (int[]) v) + : clzComp == long .class ? Arrays.hashCode( (long[]) v) + : clzComp == byte .class ? Arrays.hashCode( (byte[]) v) + : clzComp == char .class ? Arrays.hashCode( (char[]) v) + : clzComp == double.class ? Arrays.hashCode( (double[]) v) + : clzComp == float .class ? Arrays.hashCode( (float[]) v) + : clzComp == short .class ? Arrays.hashCode( (short[]) v) + : Arrays.hashCode((boolean[]) v) + : Arrays.hashCode((Object[]) v); + } + } diff --git a/common/src/main/java/com/seaofnodes/util/PackedInteger.java b/common/src/main/java/com/seaofnodes/util/PackedInteger.java new file mode 100644 index 00000000..e032f8d0 --- /dev/null +++ b/common/src/main/java/com/seaofnodes/util/PackedInteger.java @@ -0,0 +1,1360 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is + * The Ecstasy Project (https://github.com/xtclang/). + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ +package com.seaofnodes.util; + + +import java.io.DataInput; +import java.io.DataOutput; +import java.io.IOException; + +import java.math.BigInteger; + + +/** + * A PackedInteger represents a signed, 2's-complement integer of 1-8192 bits (1-1024 bytes) in + * size. (The size limit is arbitrary, and temporary.) + * <p/> + * Values up to 8 bytes can be accessed as a <tt>long</tt> value, while values of any size can be + * accessed as a BigInteger. + * <p/> + * The storage format is compressed as much as possible. There are five storage formats: + * <ul><li> + * <b>Tiny</b>: For a value in the range -64..63 (7 bits), the value can be encoded in one byte. + * The least significant 7 bits of the value are shifted left by 1 bit, and the 0x1 bit is set to 1. + * When reading in a packed integer, if bit 0x1 of the first byte is 1, then it's Tiny. + * </li><li> + * <b>Small</b>: For a value in the range -4096..4095 (13 bits), the value can be encoded in two + * bytes. The first byte contains the value 0x2 (010) in the least significant 3 bits, and bits 8-12 + * of the integer in bits 3-7; the second byte contains bits 0-7 of the integer. + * </li><li> + * <b>Medium</b>: For a value in the range -1048576..1048575 (21 bits), the value can be encoded in + * three bytes. The first byte contains the value 0x6 (110) in the least significant 3 bits, and + * bits 16-20 of the integer in bits 3-7; the second byte contains bits 8-15 of the integer; the + * third byte contains bits 0-7 of the integer. + * </li><li> + * <b>Large</b>: For a value in the range -(2^503)..2^503-1 (63 bytes), a value with `{@code s}` + * significant bits can be encoded in no less than {@code 1+max(1,(s+7)/8)} bytes; let `{@code b}` + * be the selected encoding length, in bytes. The first byte contains the value 0x0 (00) in the + * least significant 2 bits, and the least 6 significant bits of {@code (b-2)} in bits 2-7. The + * following {@code (b-1)} bytes contain the least significant {@code (b-1)*8} bits of the integer. + * </li><li> + * <b>Huge</b>: For any larger value (arbitrarily limited to the range -(2^8191)..2^8191-1 (1KB)), + * the first byte is 0b111111_00, followed by an embedded packed integer specifying the number of + * significant bytes of the enclosing packed integer, followed by that number of bytes of data. + * </li></ul> + * <p/> + * To maximize density and minimize pipeline stalls, the algorithms in this file use the smallest + * possible encoding for each value. Since an 8 significant-bit value can be encoded in two bytes + * using either a small or large encoding, we choose large to eliminate the potential for a + * (conditional-induced) pipeline stall. Since a 14..16 significant-bit value can be encoded in + * three bytes using either a medium or large encoding, we choose large for the same reason. + * <pre><code> + * significant bits encoding bytes + * ---------------- -------- ----- + * <= 7 Tiny 1 + * 8 Large 2 + * 9-13 Small 2 + * 14-16 Large 3 + * 17-21 Medium 3 + * >= 22 Large 4 or more + * >= 512 Huge * + * </code></pre> + * <p/> + * Similarly, by examining the least significant 3 bits of the first byte of an encoded value, the + * encoding can be determined as follows: + * <pre><code> + * first byte encoding bytes + * ---------- -------- ----- + * ???????1 Tiny 1 + * ?????010 Small 2 + * ?????110 Medium 3 + * ??????00 Large 2-65 + * 11111100 Huge * + * </code></pre> + */ +public class PackedInteger + implements Comparable<PackedInteger> + { + // ----- constructors -------------------------------------------------------------------------- + + /** + * Construct an uninitialized PackedInteger. + */ + public PackedInteger() + { + } + + /** + * Construct a PackedInteger using a <tt>long</tt> value. + * + * @param lVal the <tt>long</tt> value for the PackedInteger + */ + public PackedInteger(long lVal) + { + setLong(lVal); + } + + /** + * Construct a PackedInteger using a <tt>BigInteger</tt> value. + * + * @param bigint the <tt>BigInteger</tt> value for the PackedInteger + */ + public PackedInteger(BigInteger bigint) + { + setBigInteger(bigint); + } + + /** + * Construct a PackedInteger by reading the packed value from a DataInput + * stream. + * + * @param in a DataInput stream to read from + * + * @throws IOException if an I/O exception occurs while reading the data + */ + public PackedInteger(DataInput in) + throws IOException + { + readObject(in); + } + + + // ----- public methods ------------------------------------------------------------------------ + + /** + * Obtain a PackedInteger that has the specified <tt>long</tt> value. This + * method is useful for taking advantage of the built-in "cache" of + * commonly-used PackedInteger instances. + * + * @param lVal the <tt>long</tt> value for the PackedInteger + */ + public static PackedInteger valueOf(long lVal) + { + if (lVal >= CACHE_MIN & lVal <= CACHE_MAX) + { + final int iCache = (int) (lVal - CACHE_MIN); + + PackedInteger pint = CACHE[iCache]; + if (pint == null) + { + pint = new PackedInteger(lVal); + CACHE[iCache] = pint; + } + + return pint; + } + + return new PackedInteger(lVal); + } + + /** + * The size of the "native" 2's-complement signed integer that would be + * necessary to hold the value. + * + * @return a value between 1 and 32 inclusive + */ + public int getSignedByteSize() + { + verifyInitialized(); + + int nBytes = m_fBig + ? calculateSignedByteCount(m_bigint) + : Math.max(1, (((64 - Long.numberOfLeadingZeros(Math.max(m_lValue, ~m_lValue))) & 0x3F) + 7) / 8); + + assert nBytes >= 1 && nBytes <= 1024; // arbitrary limit + return nBytes; + } + + /** + * The size of the unsigned integer that would be necessary to hold the value. + * + * @return a value between 1 and 32 inclusive + */ + public int getUnsignedByteSize() + { + verifyInitialized(); + if (m_fBig && m_bigint.signum() < 0) + { + throw new IllegalStateException("negative value"); + } + + int nBytes = m_fBig + ? calculateUnsignedByteCount(m_bigint) + : Math.max(1, (((64 - Long.numberOfLeadingZeros(m_lValue)) + 7) / 8)); + + assert nBytes >= 1 && nBytes <= 32; // arbitrary limit of 32 for the prototype + return nBytes; + } + + /** + * Determine if the value of the PackedInteger is "big". The value is + * considered to be "big" if it cannot fit into a <tt>long</tt>. + * + * @return true if the value of the PackedInteger does not fit into a long + */ + public boolean isBig() + { + verifyInitialized(); + return m_fBig; + } + + /** + * Range check the PackedInteger. + * + * @param nLo the low end of the range (inclusive) + * @param nHi the high end of the range (inclusive) + * + * @return true iff the PackedInteger is in the specified range + */ + public boolean checkRange(long nLo, long nHi) + { + if (isBig()) + { + return false; + } + + return m_lValue >= nLo && m_lValue <= nHi; + } + + /** + * @return true iff the value is less than zero + */ + public boolean isNegative() + { + verifyInitialized(); + return m_fBig + ? m_bigint.signum() < 0 + : m_lValue < 0; + } + + /** + * Helper to grab the value as an int, with a range check to be safe. + * + * @return the value as a 32-bit signed int + */ + public int getInt() + { + long n = getLong(); + if (n < Integer.MIN_VALUE || n > Integer.MAX_VALUE) + { + throw new IllegalStateException("too big!"); + } + + return (int) n; + } + + /** + * Obtain the <tt>long</tt> value of the PackedInteger. If the PackedInteger + * is "big", i.e. if the {@link #isBig} method returns <tt>true</tt>, then + * this method will throw an IllegalStateException, because the value cannot + * be expressed as a <tt>long</tt> without losing data. + * + * @return the <tt>long</tt> value of this PackedInteger + * + * @throws IllegalStateException if the value of this PackedInteger does not + * fit into a long + */ + public long getLong() + { + verifyInitialized(); + if (m_fBig && m_lValue == 0) + { + throw new IllegalStateException("too big!"); + } + + return m_lValue; + } + + /** + * Initialize the PackedInteger using a <tt>long</tt> value. + * + * @param lVal the <tt>long</tt> value for the PackedInteger + */ + public void setLong(long lVal) + { + verifyUninitialized(); + m_lValue = lVal; + m_fInitialized = true; + } + + /** + * Obtain the BigInteger value of the PackedInteger. Whether or not the + * PackedInteger value is too large to be held in a <tt>long</tt>, the + * caller can request the BigInteger value; one will be lazily instantiated + * (and subsequently cached) if necessary. + * + * @return the BigInteger that represents the integer value of this + * PackedInteger object + */ + public BigInteger getBigInteger() + { + verifyInitialized(); + BigInteger bigint = m_bigint; + if (bigint == null) + { + bigint = BigInteger.valueOf(m_lValue); + m_bigint = bigint; + } + return bigint; + } + + /** + * Initialize the PackedInteger using a BigInteger value. + * + * @param bigint the BigInteger value for the PackedInteger + */ + public void setBigInteger(BigInteger bigint) + { + verifyUninitialized(); + + if (bigint == null) + { + throw new IllegalArgumentException("big integer value required"); + } + + // determine if the number of bytes allows the BigInteger value to be + // stored in a long value + if (!(m_fBig = calculateSignedByteCount(bigint) > 8)) + { + m_lValue = bigint.longValue(); + } + else + { + if (calculateUnsignedByteCount(bigint) <= 8) + { + // the unsigned value still fits the long + m_lValue = bigint.longValue(); + } + else + { + m_lValue = 0; + } + } + + m_bigint = bigint; + m_fInitialized = true; + } + + /** + * @return the negated form of this packed integer + */ + public PackedInteger negate() + { + return new PackedInteger(this.getBigInteger().negate()); + } + + /** + * @return the complemented form of this packed integer + */ + public PackedInteger complement() + { + return new PackedInteger(this.getBigInteger().not()); + } + + /** + * @return the packed integer that is one less than this packed integer + */ + public PackedInteger previous() + { + return sub(ONE); + } + + /** + * @return the packed integer that is one more than this packed integer + */ + public PackedInteger next() + { + return add(ONE); + } + + /** + * Add the value of a specified PackedInteger to this PackedInteger, resulting in a new + * PackedInteger. + * + * @param that a second PackedInteger to add to this + * + * @return the resulting PackedInteger + */ + public PackedInteger add(PackedInteger that) + { + return new PackedInteger(this.getBigInteger().add(that.getBigInteger())); + } + + /** + * Subtract the value of a specified PackedInteger from this PackedInteger, resulting in a new + * PackedInteger. + * + * @param that a second PackedInteger to subtract from this + * + * @return the resulting PackedInteger + */ + public PackedInteger sub(PackedInteger that) + { + return new PackedInteger(this.getBigInteger().subtract(that.getBigInteger())); + } + + /** + * Multiply the value of a specified PackedInteger by this PackedInteger, resulting in a new + * PackedInteger. + * + * @param that a second PackedInteger to multiply this by + * + * @return the resulting PackedInteger + */ + public PackedInteger mul(PackedInteger that) + { + return new PackedInteger(this.getBigInteger().multiply(that.getBigInteger())); + } + + /** + * Divide the value of this PackedInteger by the specified PackedInteger, resulting in a new + * PackedInteger. + * + * @param that a second PackedInteger to divide this by + * + * @return the resulting PackedInteger + */ + public PackedInteger div(PackedInteger that) + { + return new PackedInteger(this.getBigInteger().divide(that.getBigInteger())); + } + + /** + * Calculate the modulo of the value of this PackedInteger and the value of a specified + * PackedInteger, resulting in a new PackedInteger. + * + * @param that a second PackedInteger to divide this by, resulting in a modulo + * + * @return the resulting PackedInteger (never negative - modulo not remainder!) + */ + public PackedInteger mod(PackedInteger that) + { + return new PackedInteger(this.getBigInteger().mod(that.getBigInteger())); + } + + /** + * Divide the value of this PackedInteger by the specified PackedInteger, resulting in a new + * PackedInteger quotient and a new PackedInteger remainder. + * + * @param that a second PackedInteger to divide this by + * + * @return an array of the resulting PackedInteger quotient and remainder + */ + public PackedInteger[] divrem(PackedInteger that) + { + BigInteger [] aBigInt = this.getBigInteger().divideAndRemainder(that.getBigInteger()); + PackedInteger[] aPacked = new PackedInteger[2]; + aPacked[0] = new PackedInteger(aBigInt[0]); + aPacked[1] = new PackedInteger(aBigInt[1]); + return aPacked; + } + + /** + * Calculate the bit-and of the value of this PackedInteger and the value of a specified + * PackedInteger, resulting in a new PackedInteger. + * + * @param that a second PackedInteger to bit-and with this PackedInteger + * + * @return the resulting PackedInteger + */ + public PackedInteger and(PackedInteger that) + { + return new PackedInteger(this.getBigInteger().and(that.getBigInteger())); + } + + /** + * Calculate the bit-or of the value of this PackedInteger and the value of a specified + * PackedInteger, resulting in a new PackedInteger. + * + * @param that a second PackedInteger to bit-or with this PackedInteger + * + * @return the resulting PackedInteger + */ + public PackedInteger or(PackedInteger that) + { + return new PackedInteger(this.getBigInteger().or(that.getBigInteger())); + } + + /** + * Calculate the bit-xor of the value of this PackedInteger and the value of a specified + * PackedInteger, resulting in a new PackedInteger. + * + * @param that a second PackedInteger to bit-xor with this PackedInteger + * + * @return the resulting PackedInteger + */ + public PackedInteger xor(PackedInteger that) + { + return new PackedInteger(this.getBigInteger().xor(that.getBigInteger())); + } + + /** + * Shift left the bits in the value of this PackedInteger by the value of a specified + * PackedInteger, resulting in a new PackedInteger. + * + * @param that a second PackedInteger specifying the shift amount + * + * @return the resulting PackedInteger + */ + public PackedInteger shl(PackedInteger that) + { + return shl(that.getInt()); + } + + /** + * Shift left the bits in the value of this PackedInteger by the specified count, + * resulting in a new PackedInteger. + * + * @param count the shift count + * + * @return the resulting PackedInteger + */ + public PackedInteger shl(int count) + { + return new PackedInteger(this.getBigInteger().shiftLeft(count)); + } + + /** + * Logical shift right the bits in the value of this PackedInteger by the value of a specified + * PackedInteger, resulting in a new PackedInteger. + * + * @param that a second PackedInteger specifying the shift amount + * + * @return the resulting PackedInteger + */ + public PackedInteger shr(PackedInteger that) + { + return shr(that.getInt()); + } + + /** + * Logical shift right the bits in the value of this PackedInteger by the specified count, + * resulting in a new PackedInteger. + * + * @param count the shift count + * + * @return the resulting PackedInteger + */ + public PackedInteger shr(int count) + { + return count <= 0 + ? this + : new PackedInteger(this.getBigInteger().shiftRight(count)); + } + + /** + * Arithmetic (aka "unsigned") shift right the bits in the value of this PackedInteger by the + * value of a specified PackedInteger, resulting in a new PackedInteger. + * + * @param that a second PackedInteger specifying the shift amount + * + * @return the resulting PackedInteger + */ + public PackedInteger ushr(PackedInteger that) + { + return shr(that.getInt()); + } + + /** + * Arithmetic (aka "unsigned") shift right the bits in the value of this PackedInteger by the + * specified count, resulting in a new PackedInteger. + * + * @param count the shift count + * + * @return the resulting PackedInteger + */ + public PackedInteger ushr(int count) + { + return shr(count); + } + + /** + * Compare the value of a specified PackedInteger with the value of this PackedInteger. + * + * @param that a second PackedInteger to compare to + * + * @return -1, 0, or 1 if this is less than, equal to, or greater than that + */ + public int cmp(PackedInteger that) + { + return this.getBigInteger().compareTo(that.getBigInteger()); + } + + /** + * Format the PackedInteger as a String of the specified radix, including a radix prefix for + * any non-decimal radix. + * + * @param radix 2, 8, 10, or 16 + * + * @return the String value of this PackedInteger in the format of the specified radix + */ + public String toString(int radix) + { + if (radix == 10) + { + return toString(); + } + + StringBuilder sb = new StringBuilder(); + if (isNegative()) + { + sb.append('-'); + } + + switch (radix) + { + case 2: + sb.append("0b"); + break; + + case 8: + sb.append("0o"); + break; + + case 16: + sb.append("0x"); + break; + + default: + throw new IllegalArgumentException("radix=" + radix); + } + + sb.append(isBig() + ? getBigInteger().abs().toString(radix) + : Long.toUnsignedString(Math.abs(getLong()), radix)); + + return sb.toString(); + } + + /** + * Read a PackedInteger from a stream. + * + * @param in a DataInput stream to read from + * + * @throws IOException if an I/O exception occurs while reading the data + */ + public void readObject(DataInput in) + throws IOException + { + verifyUninitialized(); + + final int b = in.readByte(); + // check for large or huge format with more than 8 trailing bytes (needs BigInteger) + if ((b & 0b11) == 0b00 && (b & 0b111000_00) != 0) + { + final int cBytes; + if ((b & 0xFF) == 0b111111_00) + { + // huge format + long len = readLong(in); + if (len > 1024) + { + throw new IOException("integer size of " + len + " bytes; maximum is 1024"); + } + cBytes = (int) len; + } + else + { + // large format + cBytes = 1 + ((b & 0xFC) >>> 2); + } + + final byte[] ab = new byte[cBytes]; + in.readFully(ab); + setBigInteger(new BigInteger(ab)); + } + else + { + // tiny, small, medium, and large (up to 8 trailing bytes) format values fit into + // a Java long + setLong(readLong(in, b)); + } + } + + /** + * Write a PackedInteger to a stream. + * + * @param out a DataOutput stream to write to + * + * @throws IOException if an I/O exception occurs while writing the data + */ + public void writeObject(DataOutput out) + throws IOException + { + verifyInitialized(); + + if (isBig()) + { + // the value is supposed to be "big", so figure out how many bytes + // (minimum) it needs to hold its significant bits + byte[] ab = m_bigint.toByteArray(); + int cb = ab.length; + int of = 0; + + // truncate any redundant bytes + boolean fNeg = (ab[0] & 0x80) != 0; + int bSkip = fNeg ? 0xFF : 0x00; + while (of < cb-1 && ab[of] == bSkip && (ab[of+1] & 0x80) == (bSkip & 0x80)) + { + ++of; + } + cb -= of; + assert cb > 8 && cb <= 1024; + + if (cb < 64) + { + // large format: length encoded in 6 MSBs of first byte, then the bytes of the int + out.writeByte((cb-1) << 2); + } + else + { + // huge format: first byte is 0, then the length as a packed int, then the bytes + out.writeByte(0b111111_00); + writeLong(out, cb); + } + out.write(ab, of, cb); + } + else + { + writeLong(out, m_lValue); + } + } + + /** + * Verify that the PackedInteger is still uninitialized (has no integer + * value). + * + * @throws IllegalStateException if the value of the PackedInteger has + * already been set + */ + public void verifyUninitialized() + { + if (m_fInitialized) + { + throw new IllegalStateException("already initialized"); + } + } + + /** + * Verify that the PackedInteger has been successfully initialized to an + * integer value. + * + * @throws IllegalStateException if the value of the PackedInteger has + * <b>not</b> yet been set + */ + public void verifyInitialized() + { + if (!m_fInitialized) + { + throw new IllegalStateException("not yet initialized"); + } + } + + + // ----- Object methods ------------------------------------------------------------------------ + + @Override + public int hashCode() + { + return isBig() ? m_bigint.hashCode() : Long.hashCode(m_lValue); + } + + @Override + public boolean equals(Object obj) + { + if (!(obj instanceof PackedInteger that)) + { + return false; + } + + return this.isBig() + ? that.isBig() && this.getBigInteger().equals(that.getBigInteger()) + : !that.isBig() && this.getLong() == that.getLong(); + } + + @Override + public String toString() + { + return isBig() ? m_bigint.toString() : Long.toString(m_lValue); + } + + + // ----- Comparable methods -------------------------------------------------------------------- + + @Override + public int compareTo(PackedInteger that) + { + if (this.isBig() || that.isBig()) + { + return this.getBigInteger().compareTo(that.getBigInteger()); + } + + long lThis = this.m_lValue; + long lThat = that.m_lValue; + return Long.compare(lThis, lThat); + } + + + // ----- public helpers ------------------------------------------------------------------------ + + /** + * Write a signed 64-bit integer to a stream using variable-length + * encoding. + * + * @param out the <tt>DataOutput</tt> stream to write to + * @param l the <tt>long</tt> value to write + * + * @throws IOException if an I/O exception occurs + */ + public static void writeLong(DataOutput out, long l) + throws IOException + { + // test for Tiny + if (l <= 63 && l >= -64) + { + out.writeByte(((int) l) << 1 | 0x01); + return; + } + + final int cBits = 65 - Long.numberOfLeadingZeros(Math.max(l, ~l)); + + // test for Small and Medium + int i = (int) l; + if (((1L << cBits) & 0x3E3E00L) != 0) // test against bits 9-13 and 17-21 + { + if (cBits <= 13) + { + out.writeShort(0b010_00000000 // 0x2 marker at 0..2 in byte #1 + | (i & 0x1F00) << 3 // bits 8..12 at 3..7 in byte #1 + | (i & 0x00FF)); // bits 0..7 at 0..7 in byte #2 + } + else + { + out.writeByte(0b110 // 0x6 marker at 0..2 in byte #1 + | (i & 0x1F0000) >>> 13); // bits 16..20 at 3..7 in byte #1 + out.writeShort(i); // bits 8..15 at 0..7 in byte #2 + } // bits 0..7 at 0..7 in byte #3 + return; + } + + int cBytes = (cBits + 7) >>> 3; + out.writeByte((cBytes - 1) << 2); + switch (cBytes) + { + case 1: + out.writeByte(i); + break; + case 2: + out.writeShort(i); + break; + case 3: + out.writeByte(i >>> 16); + out.writeShort(i); + break; + case 4: + out.writeInt(i); + break; + case 5: + out.writeByte((int) (l >>> 32)); + out.writeInt(i); + break; + case 6: + out.writeShort((int) (l >>> 32)); + out.writeInt(i); + break; + case 7: + out.writeByte((int) (l >>> 48)); + out.writeShort((int) (l >>> 32)); + out.writeInt(i); + break; + case 8: + out.writeLong(l); + break; + default: + throw new IllegalStateException("n=" + l); + } + } + + /** + * Read a variable-length encoded integer value from a stream. + * + * @param in a <tt>DataInput</tt> stream to read from + * + * @return a <tt>long</tt> value + * + * @throws IOException if an I/O exception occurs + * @throws NumberFormatException if the integer does not fit into + * a <tt>long</tt> value + */ + public static long readLong(DataInput in) + throws IOException + { + return readLong(in, in.readByte()); + } + + /** + * Determine the number of bytes of the packed integer at the specified offset in the provided + * byte array. + * + * @param ab the byte array containing a packed integer + * @param of the byte offset at which the packed integer is located + * + * @return the number of bytes used to encode the packed integer + */ + public static int packedLength(byte[] ab, int of) + { + int b = ab[of]; + if ((b & 0x01) != 0) + { + // Tiny format + return 1; + } + + if ((b & 0x02) != 0) + { + // Small or Medium format + return ((b & 0x04) == 0) ? 2 : 3; + } + + if ((b & 0xFF) == 0b111111_00) + { + // Huge format + long lVals = unpackInt(ab, of+1); + return 1 + (int) (lVals >>> 32) + (int) lVals; + } + + // Large format + return 2 + ((b & 0xFC) >>> 2); + } + + /** + * Determine the number of bytes that the specified value would use if it were packed. + * + * @param n the long integer value to estimate a packed length for + * + * @return the smallest number of bytes necessary to encode the packed integer + */ + public static int packedLength(long n) + { + // test for Tiny + if (n <= 63 && n >= -64) + { + return 1; + } + + // test for Small and Medium + final int cBits = 65 - Long.numberOfLeadingZeros(Math.max(n, ~n)); + if (((1L << cBits) & 0x3E3E00L) != 0) // test against bits 9-13 and 17-21 + { + return cBits <= 13 ? 2 : 3; + } + + // Large format + int cBytes = (cBits + 7) >>> 3; + return 1 + cBytes; + } + + /** + * Extract an integer from a byte array, and report back both the integer value and its size in + * terms of the number of bytes. + * + * @param ab the byte array to unpack an integer from + * @param of the byte offset at which the integer is located + * + * @return the int value encoded as bits 0..31, and the number of bytes used by the value + * encoded as bits 32..63 + */ + public static long unpackInt(byte[] ab, int of) + { + int n; + int cb; + + int b = ab[of]; + if ((b & 0x01) != 0) + { + // Tiny format: the first bit of the first byte is used to indicate a single byte + // format, in which the entire value is contained in the 7 MSBs + n = b >> 1; + cb = 1; + } + else if ((b & 0x02) != 0) + { + // the third bit is used to indicate 0: 1 trailing byte, or 1: 2 trailing bytes + if ((b & 0x04) == 0) + { + // Small format: bits 3..7 of the first byte are bits 8..12 of the result, and the + // next byte provides bits 0..7 of the result (note: and then also sign-extend) + n = (b & 0xFFFFFFF8) << 5 | ab[of+1] & 0xFF; + cb = 2; + } + else + { + // Medium format: bits 3..7 of the first byte are bits 16..20 of the result, and the + // next byte provides bits 8..15 of the result, and the next byte provides bits 0..7 + // of the result (note: and then also sign-extend) + n = (b & 0xFFFFFFF8) << 13 | (ab[of+1] & 0xFF) << 8 | ab[of+2] & 0xFF; + cb = 3; + } + } + else + { + // Large format: the first two bits of the first byte are 0, so bits 2..7 of the + // first byte are the trailing number of bytes minus 1 + // Huge format: the first byte is 0b111111_00, so it is followed by a packed integer + // that specifies the length of this packed integer + final int cBytes; + if ((b & 0xFF) == 0b111111_00) + { + // Huge format + long lVals = unpackInt(ab, of+1); + int cbcb = (int) (lVals >>> 32); + cBytes = (int) lVals; + cb = 1 + cbcb + cBytes; + of += 1 + cbcb; + } + else + { + // Large format + cBytes = 1 + ((b & 0xFC) >>> 2); + cb = 1 + cBytes; + ++of; + } + + switch (cBytes) + { + case 1: + n = ab[of]; + break; + case 2: + n = ab[of] << 8 | ab[of+1] & 0xFF; + break; + case 3: + n = ab[of] << 16 | (ab[of+1] & 0xFF) << 8 | ab[of+2] & 0xFF; + break; + case 4: + n = ab[of] << 24 | (ab[of+1] & 0xFF) << 16 | (ab[of+2] & 0xFF) << 8 | ab[of+3] & 0xFF; + break; + default: + throw new IllegalStateException("# trailing bytes=" + cBytes); + } + } + + return ((long) cb) << 32 | n & 0xFFFFFFFFL; + } + + + // ----- internal ------------------------------------------------------------------------------ + + private static long readLong(DataInput in, int b) + throws IOException + { + if ((b & 0x01) != 0) + { + // Tiny format: the first bit of the first byte is used to indicate a single byte + // format, in which the entire value is contained in the 7 MSBs + return b >> 1; + } + + if ((b & 0x02) != 0) + { + // the third bit is used to indicate 0: 1 trailing byte, or 1: 2 trailing bytes + if ((b & 0x04) == 0) + { + // Small format: bits 3..7 of the first byte are bits 8..12 of the result, and the + // next byte provides bits 0..7 of the result (note: and then also sign-extend) + return (long) (b & 0xFFFFFFF8) << 5 | in.readUnsignedByte(); + } + else + { + // Medium format: bits 3..7 of the first byte are bits 16..20 of the result, and the + // next byte provides bits 8..15 of the result, and the next byte provides bits 0..7 + // of the result (note: and then also sign-extend) + return (long) (b & 0xFFFFFFF8) << 13 | in.readUnsignedShort(); + } + } + + // Large format: the first two bits of the first byte are 0, so bits 2..7 of the + // first byte are the trailing number of bytes minus 1 + // Huge format: the first byte is 0, so it is followed by a packed integer that + // specifies the length of this packed integer + int cBytes = (b & 0xFF) == 0b111111_00 ? (int) readLong(in) : 1 + ((b & 0xFC) >>> 2); + switch (cBytes) + { + case 1: + return in.readByte(); + case 2: + return in.readShort(); + case 3: + return in.readByte() << 16 | in.readUnsignedShort(); + case 4: + return in.readInt(); + case 5: + return ((long) in.readByte()) << 32 | readUnsignedInt(in); + case 6: + return ((long) in.readShort()) << 32 | readUnsignedInt(in); + case 7: + return ((long) in.readByte()) << 48 + | ((long) in.readUnsignedShort()) << 32 + | readUnsignedInt(in); + case 8: + return in.readLong(); + default: + throw new IllegalStateException("# trailing bytes=" + cBytes); + } + } + + private static long readUnsignedInt(DataInput in) + throws IOException + { + return in.readInt() & 0xFFFFFFFFL; + } + + /** + * Determine how many bytes is necessary to hold the specified BigInteger. + * + * @return the minimum number of bytes to hold the integer value in + * 2s-complement form + * + * @throws IllegalArgumentException if the BigInteger is out of range + */ + private static int calculateSignedByteCount(BigInteger bigint) + { + return bigint.bitLength() / 8 + 1; + } + + /** + * Determine how many bytes is necessary to hold the specified BigInteger. + * + * @return the minimum number of bytes to hold the integer value in + * 2s-complement form + * + * @throws IllegalArgumentException if the BigInteger is out of range + */ + private static int calculateUnsignedByteCount(BigInteger bigint) + { + return (bigint.bitLength() + 7) / 8; + } + + + // ----- data members -------------------------------------------------------------------------- + + /** + * Set to true once the value has been set. + */ + private boolean m_fInitialized; + + /** + * Set to true if the value is too large to fit into a <tt>long</tt> (for signed values). + */ + private boolean m_fBig; + + /** + * The <tt>long</tt> value if the value fits into a <tt>long</tt>. Note, the value could be "big", + * as a signed one but still fit the long as unsigned. + */ + private long m_lValue; + + /** + * The <tt>BigInteger</tt> value, which is non-null in several different + * cases, including if the PackedInteger was constructed with a BigInteger + * value, if the value was set to a BigInteger, or if the BigInteger was + * lazily instantiated by a call to {@link #getBigInteger}. + */ + private BigInteger m_bigint; + + /** + * Cache of PackedInteger instances for small integers. + */ + private static final PackedInteger[] CACHE = new PackedInteger[0x1000]; + + + // ----- constants ----------------------------------------------------------------------------- + + /** + * Smallest integer value to cache. One quarter of the cache size is + * reserved for small negative integer values. + */ + private static final long CACHE_MIN = -(CACHE.length >> 2); + + /** + * Largest integer value to cache. Three-quarters of the cache size is + * reserved for small positive integer values. + */ + private static final long CACHE_MAX = CACHE_MIN + CACHE.length - 1; + + /** + * The PackedInteger for the value <tt>0</tt>. Also used as the smallest 1-, 2-, 4-, + * 8-, 16-, and 32-byte <b>un</b>signed integer value. + */ + public static final PackedInteger ZERO = valueOf(0L); + /** + * The PackedInteger for the value <tt>1</tt>. + */ + public static final PackedInteger ONE = valueOf(1L); + /** + * The PackedInteger for the value <tt>-1</tt>. + */ + public static final PackedInteger NEG_ONE = valueOf(-1L); + + /** + * Smallest 1-byte (8-bit) signed integer value. + */ + public static final PackedInteger SINT1_MIN = valueOf(-0x80L); + /** + * Smallest 2-byte (16-bit) signed integer value. + */ + public static final PackedInteger SINT2_MIN = valueOf(-0x8000L); + /** + * Smallest 4-byte (32-bit) signed integer value. + */ + public static final PackedInteger SINT4_MIN = valueOf(-0x80000000L); + /** + * Smallest 8-byte (64-bit) signed integer value. + */ + public static final PackedInteger SINT8_MIN = valueOf(-0x8000000000000000L); + /** + * Smallest 16-byte (128-bit) signed integer value. + */ + public static final PackedInteger SINT16_MIN = new PackedInteger(new BigInteger("-8" + "0".repeat(31), 16)); + /** + * Smallest N-byte signed integer value (arbitrary 1KB limit). + */ + public static final PackedInteger SINTN_MIN = new PackedInteger(new BigInteger("-8" + "0".repeat(2047), 16)); + /** + * Largest 1-byte (8-bit) signed integer value. + */ + public static final PackedInteger SINT1_MAX = valueOf(0x7F); + /** + * Largest 2-byte (16-bit) signed integer value. + */ + public static final PackedInteger SINT2_MAX = valueOf(0x7FFF); + /** + * Largest 4-byte (32-bit) signed integer value. + */ + public static final PackedInteger SINT4_MAX = valueOf(0x7FFF_FFFF); + /** + * Largest 8-byte (64-bit) signed integer value. + */ + public static final PackedInteger SINT8_MAX = valueOf(0x7FFF_FFFF_FFFF_FFFFL); + /** + * Largest 16-byte (128-bit) signed integer value. + */ + public static final PackedInteger SINT16_MAX = new PackedInteger(new BigInteger("7" + "F".repeat(31), 16)); + /** + * Largest N-byte signed integer value (arbitrary 1KB limit). + */ + public static final PackedInteger SINTN_MAX = new PackedInteger(new BigInteger("7" + "F".repeat(2047), 16)); + /** + * Largest 1-byte (8-bit) unsigned integer value. + */ + public static final PackedInteger UINT1_MAX = valueOf(0xFF); + /** + * Largest 2-byte (16-bit) unsigned integer value. + */ + public static final PackedInteger UINT2_MAX = valueOf(0xFFFF); + /** + * Largest 4-byte (32-bit) unsigned integer value. + */ + public static final PackedInteger UINT4_MAX = valueOf(0xFFFF_FFFFL); + /** + * Largest 8-byte (64-bit) unsigned integer value. + */ + public static final PackedInteger UINT8_MAX = new PackedInteger(new BigInteger("F".repeat(16), 16)); + /** + * Largest 16-byte (128-bit) unsigned integer value. + */ + public static final PackedInteger UINT16_MAX = new PackedInteger(new BigInteger("F".repeat(32), 16)); + /** + * Largest N-byte unsigned integer value (arbitrary 1KB limit). + */ + public static final PackedInteger UINTN_MAX = SINTN_MAX; + + /** + * Decimal "Kilo". + */ + public static final PackedInteger KB = valueOf(1000); + /** + * Binary "Kilo". + */ + public static final PackedInteger KI = valueOf(1024); + /** + * Decimal "Mega". + */ + public static final PackedInteger MB = valueOf(1000 * 1000); + /** + * Binary "Mega". + */ + public static final PackedInteger MI = valueOf(1024 * 1024); + /** + * Decimal "Giga". + */ + public static final PackedInteger GB = valueOf(1000 * 1000 * 1000); + /** + * Binary "Giga". + */ + public static final PackedInteger GI = valueOf(1024 * 1024 * 1024); + /** + * Decimal "Tera". + */ + public static final PackedInteger TB = valueOf(1000L * 1000 * 1000 * 1000); + /** + * Binary "Tera". + */ + public static final PackedInteger TI = valueOf(1024L * 1024 * 1024 * 1024); + /** + * Decimal "Peta". + */ + public static final PackedInteger PB = valueOf(1000L * 1000 * 1000 * 1000 * 1000); + /** + * Binary "Peta". + */ + public static final PackedInteger PI = valueOf(1024L * 1024 * 1024 * 1024 * 1024); + /** + * Decimal "Exa". + */ + public static final PackedInteger EB = valueOf(1000L * 1000 * 1000 * 1000 * 1000 * 1000); + /** + * Binary "Exa". + */ + public static final PackedInteger EI = valueOf(1024L * 1024 * 1024 * 1024 * 1024 * 1024); + /** + * Decimal "Zetta". + */ + public static final PackedInteger ZB = EB.mul(KB); + /** + * Binary "Zetta". + */ + public static final PackedInteger ZI = EI.mul(KI); + /** + * Decimal "Yotta". + */ + public static final PackedInteger YB = ZB.mul(KB); + /** + * Binary "Yotta". + */ + public static final PackedInteger YI = ZI.mul(KI); + + /** + * The decimal (1000x) factors. + */ + public static final PackedInteger[] xB_FACTORS = {KB, MB, GB, TB, PB, EB, ZB, YB, }; + /** + * The binary (1024x) factors. + */ + public static final PackedInteger[] xI_FACTORS = {KI, MI, GI, TI, PI, EI, ZI, YI, }; + }
\ No newline at end of file diff --git a/src/main/java/com/seaofnodes/util/SB.java b/common/src/main/java/com/seaofnodes/util/SB.java index 4481ce71..4481ce71 100644 --- a/src/main/java/com/seaofnodes/util/SB.java +++ b/common/src/main/java/com/seaofnodes/util/SB.java diff --git a/src/main/java/com/seaofnodes/util/Util.java b/common/src/main/java/com/seaofnodes/util/Util.java index e559a799..e559a799 100644 --- a/src/main/java/com/seaofnodes/util/Util.java +++ b/common/src/main/java/com/seaofnodes/util/Util.java diff --git a/src/main/java/com/seaofnodes/util/VBitSet.java b/common/src/main/java/com/seaofnodes/util/VBitSet.java index 5d00a9e4..5d00a9e4 100644 --- a/src/main/java/com/seaofnodes/util/VBitSet.java +++ b/common/src/main/java/com/seaofnodes/util/VBitSet.java diff --git a/src/test/java/com/seaofnodes/simple/lexer/TestLexer.java b/common/src/test/java/com/seaofnodes/simple/lexer/TestLexer.java index 18a4634d..ef29d963 100644 --- a/src/test/java/com/seaofnodes/simple/lexer/TestLexer.java +++ b/common/src/test/java/com/seaofnodes/simple/lexer/TestLexer.java @@ -19,8 +19,8 @@ import com.seaofnodes.simple.common.ErrorListener; import com.seaofnodes.simple.lexer.ecstasy.Lexer; import com.seaofnodes.simple.lexer.ecstasy.Source; import com.seaofnodes.simple.lexer.ecstasy.Token; -import org.junit.jupiter.api.Assertions; -import org.junit.jupiter.api.Test; +import org.junit.Assert; +import org.junit.Test; public class TestLexer { @@ -30,8 +30,8 @@ public class TestLexer { final String source = "//a comment\nx"; Lexer lexer = new Lexer(new Source(source), new ErrorListener()); Token token = lexer.next(); - Assertions.assertEquals(token.getId(), Token.Id.EOL_COMMENT); + Assert.assertEquals(token.getId(), Token.Id.EOL_COMMENT); token = lexer.next(); - Assertions.assertEquals("x", token.getValueText()); + Assert.assertEquals("x", token.getValueText()); } } diff --git a/language/.gitignore b/language/.gitignore new file mode 100644 index 00000000..58314a2c --- /dev/null +++ b/language/.gitignore @@ -0,0 +1,28 @@ +# Compiled class file +*.class + +# Log file +*.log + +# BlueJ files +*.ctxt + +# Mobile Tools for Java (J2ME) +.mtj.tmp/ + +# Package Files # +*.jar +*.war +*.nar +*.ear +*.zip +*.tar.gz +*.rar + +# virtual machine crash logs, see http://www.java.com/en/download/help/error_hotspot.xml +hs_err_pid* + +target/* + +.idea +*.iml
\ No newline at end of file diff --git a/language/README.md b/language/README.md new file mode 100644 index 00000000..09593ab5 --- /dev/null +++ b/language/README.md @@ -0,0 +1,6 @@ +# Simple Demo Language + +The language is a small subset of the C language. + +The grammar of the language is not yet finalized, but for the current definition, +please look at [grammar](src/main/antlr4/com/seaofnodes/simple/antlr/SimpleLanguage.g4).
\ No newline at end of file diff --git a/language/examples/all-features.lang b/language/examples/all-features.lang new file mode 100644 index 00000000..132e4b9c --- /dev/null +++ b/language/examples/all-features.lang @@ -0,0 +1,21 @@ +int i; +int j; + +i = 0; +j = 100; +while ( 1 ) +{ + i = i + 1; + j = j - 1; + if (i >= j) + break; +} + +if (1) + i = i + 5; +else if (2) + i = i - 1; +else +{ + j = 0; +}
\ No newline at end of file diff --git a/language/pom.xml b/language/pom.xml new file mode 100644 index 00000000..7d748aa1 --- /dev/null +++ b/language/pom.xml @@ -0,0 +1,80 @@ +<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" + xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"> + <modelVersion>4.0.0</modelVersion> + <parent> + <groupId>com.seaofnodes</groupId> + <artifactId>simple</artifactId> + <version>1.0</version> + </parent> + <artifactId>language-grammar</artifactId> + <packaging>jar</packaging> + <name>SeaOfNodes Demo Simple Language Grammar</name> + <properties> + <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding> + <maven.compiler.target>17</maven.compiler.target> + <maven.compiler.source>17</maven.compiler.source> + <antlr4test-maven-plugin.version>1.22</antlr4test-maven-plugin.version> + <antlr.version>4.11.1</antlr.version> + <antlr4test-maven-plugin.version>1.21</antlr4test-maven-plugin.version> + <junit.version>4.13.2</junit.version> + </properties> + <dependencies> + <dependency> + <groupId>org.antlr</groupId> + <artifactId>antlr4-runtime</artifactId> + <version>${antlr.version}</version> + <type>jar</type> + <scope>compile</scope> + </dependency> + </dependencies> + <build> + <pluginManagement> + <plugins> + <plugin> + <groupId>org.apache.maven.plugins</groupId> + <artifactId>maven-compiler-plugin</artifactId> + <version>3.10.1</version> + </plugin> + </plugins> + </pluginManagement> + <plugins> + <plugin> + <groupId>org.antlr</groupId> + <artifactId>antlr4-maven-plugin</artifactId> + <version>${antlr.version}</version> + <configuration> + <visitor>true</visitor> + <listener>true</listener> + </configuration> + <executions> + <execution> + <phase>generate-sources</phase> + <goals> + <goal>antlr4</goal> + </goals> + </execution> + </executions> + </plugin> + <plugin> + <groupId>com.khubla.antlr</groupId> + <artifactId>antlr4test-maven-plugin</artifactId> + <version>${antlr4test-maven-plugin.version}</version> + <configuration> + <verbose>false</verbose> + <showTree>false</showTree> + <entryPoint>program</entryPoint> + <grammarName>SimpleLanguage</grammarName> + <packageName>com.seaofnodes.simple.antlr</packageName> + <exampleFiles>examples/</exampleFiles> + </configuration> + <executions> + <execution> + <goals> + <goal>test</goal> + </goals> + </execution> + </executions> + </plugin> + </plugins> + </build> +</project> diff --git a/language/src/main/antlr4/com/seaofnodes/simple/antlr/SimpleLanguage.g4 b/language/src/main/antlr4/com/seaofnodes/simple/antlr/SimpleLanguage.g4 new file mode 100644 index 00000000..6779e5a2 --- /dev/null +++ b/language/src/main/antlr4/com/seaofnodes/simple/antlr/SimpleLanguage.g4 @@ -0,0 +1,170 @@ +grammar SimpleLanguage; + +program + : declaration* statement+ EOF + ; + +declaration + : type IDENTIFIER ';' + ; + +type + : 'int' + ; + +statement + : 'if' '(' expression ')' statement + | 'if' '(' expression ')' statement 'else' statement + | 'while' '(' expression ')' statement + | IDENTIFIER '=' expression ';' + | '{' declaration* statement+ '}' + | 'break' ';' + ; + +expression + : primaryExpression # PrimaryExpression_ + | ('-' | '!') expression # UnaryExpression + | expression ('*' | '/' ) expression # ArithmeticOrLogicalExpression + | expression ('+' | '-') expression # ArithmeticOrLogicalExpression + | expression ('==' | '!='| '>'| '<'| '>='| '<=') expression # ComparisonExpression + | expression '&&' expression # BooleanExpression + | expression '||' expression # BooleanExpression + ; + +primaryExpression + : + | INTEGER_LITERAL + | IDENTIFIER + | '(' expression ')' + ; + +/////////////////////////////////////////////////////////////////// + +IDENTIFIER + : IDENTIFIER_NONDIGIT + ( IDENTIFIER_NONDIGIT + | DEC_DIGIT + )* + ; + +fragment +IDENTIFIER_NONDIGIT + : NON_DIGIT + | UNIVERSAL_CHARACTER_NAME + ; + +fragment +NON_DIGIT + : [a-zA-Z_] + ; + + +fragment +UNIVERSAL_CHARACTER_NAME + : '\\u' HEX_QUAD + | '\\U' HEX_QUAD HEX_QUAD + ; + +fragment +HEX_QUAD + : HEX_DIGIT HEX_DIGIT HEX_DIGIT HEX_DIGIT + ; + +// tokens char and string +CHAR_LITERAL + : '\'' + ( + ~['\\\n\r\t] + | QUOTE_ESCAPE + | ASCII_ESCAPE + | UNICODE_ESCAPE + ) '\'' + ; + +STRING_LITERAL + : '"' + ( + ~["] + | QUOTE_ESCAPE + | ASCII_ESCAPE + | UNICODE_ESCAPE + | ESC_NEWLINE + )* '"' + ; +RAW_STRING_LITERAL: 'r' RAW_STRING_CONTENT; +fragment RAW_STRING_CONTENT: '#' RAW_STRING_CONTENT '#' | '"' .*? '"'; +BYTE_LITERAL: 'b\'' (. | QUOTE_ESCAPE | BYTE_ESCAPE) '\''; + +BYTE_STRING_LITERAL: 'b"' (~["] | QUOTE_ESCAPE | BYTE_ESCAPE)* '"'; +RAW_BYTE_STRING_LITERAL: 'br' RAW_STRING_CONTENT; +fragment ASCII_ESCAPE: '\\x' OCT_DIGIT HEX_DIGIT | COMMON_ESCAPE; +fragment BYTE_ESCAPE: '\\x' HEX_DIGIT HEX_DIGIT | COMMON_ESCAPE; +fragment COMMON_ESCAPE: '\\' [nrt\\0]; +fragment UNICODE_ESCAPE + : '\\u{' HEX_DIGIT HEX_DIGIT? HEX_DIGIT? HEX_DIGIT? HEX_DIGIT? HEX_DIGIT? '}' + ; +fragment QUOTE_ESCAPE: '\\' ['"]; +fragment ESC_NEWLINE: '\\' '\n'; + +// number +INTEGER_LITERAL + : + ( + DEC_LITERAL + | BIN_LITERAL + | OCT_LITERAL + | HEX_LITERAL + ) INTEGER_SUFFIX? + ; +DEC_LITERAL: DEC_DIGIT (DEC_DIGIT | '_')*; +HEX_LITERAL: '0x' '_'* HEX_DIGIT (HEX_DIGIT | '_')*; +OCT_LITERAL: '0o' '_'* OCT_DIGIT (OCT_DIGIT | '_')*; +BIN_LITERAL: '0b' '_'* [01] [01_]*; +FLOAT_LITERAL + : DEC_LITERAL + ( + '.' DEC_LITERAL + )? FLOAT_EXPONENT? FLOAT_SUFFIX? + ; + +fragment INTEGER_SUFFIX + : 'u8' + | 'u16' + | 'u32' + | 'u64' + | 'u128' + | 'usize' + | 'i8' + | 'i16' + | 'i32' + | 'i64' + | 'i128' + | 'isize' + ; + +fragment FLOAT_SUFFIX: 'f32' | 'f64'; +fragment FLOAT_EXPONENT: [eE] [+-]? '_'* DEC_LITERAL; +fragment OCT_DIGIT: [0-7]; +fragment DEC_DIGIT: [0-9]; +fragment HEX_DIGIT: [0-9a-fA-F]; + + +WHITESPACE + : [ \t]+ + -> skip + ; + +NEWLINE + : ( '\r' '\n'? + | '\n' + ) + -> skip + ; + +LINE_COMMENT + : '//' ~[\r\n]* + -> skip + ; + + +ANY: . ;
\ No newline at end of file @@ -1,35 +1,41 @@ -<?xml version="1.0" encoding="UTF-8"?> <project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" - xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"> + xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 + http://maven.apache.org/maven-v4_0_0.xsd"> <modelVersion>4.0.0</modelVersion> <groupId>com.seaofnodes</groupId> <artifactId>simple</artifactId> - <version>1.0-SNAPSHOT</version> - <packaging>jar</packaging> - <name>Simple Programming Language</name> - <description>Simple language implementation to demonstrate Sea of Nodes IR</description> + <packaging>pom</packaging> + <version>1.0</version> + <name>SeaOfNodes Simple Programming Language</name> + <description>A simple language implementation to demonstrate Sea of Nodes IR</description> <url>https://github.com/SeaOfNodes/Simple</url> + <licenses> + <license> + <name>Apache License Version 2.0</name> + <url>http://www.apache.org/licenses/LICENSE-2.0</url> + </license> + </licenses> + + <modules> + <module>common</module> + <module>language</module> + <module>chapter01</module> + </modules> <properties> <maven.compiler.source>17</maven.compiler.source> <maven.compiler.target>17</maven.compiler.target> <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding> + <junit.version>4.13.2</junit.version> </properties> <dependencies> <dependency> - <groupId>org.jctools</groupId> - <artifactId>jctools-core</artifactId> - <version>4.0.1</version> - </dependency> - - <dependency> - <groupId>org.junit.jupiter</groupId> - <artifactId>junit-jupiter-engine</artifactId> - <version>5.9.1</version> - <scope>test</scope> + <groupId>junit</groupId> + <artifactId>junit</artifactId> + <version>${junit.version}</version> </dependency> </dependencies> diff --git a/src/main/java/com/seaofnodes/util/BitSetSparse.java b/src/main/java/com/seaofnodes/util/BitSetSparse.java deleted file mode 100644 index 09d2f039..00000000 --- a/src/main/java/com/seaofnodes/util/BitSetSparse.java +++ /dev/null @@ -1,41 +0,0 @@ -/** - * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Contributor(s): - * - * The Initial Developer of the Original Software is Cliff Click. - * - * This file is part of the Sea Of Nodes Simple Programming language - * implementation. See https://github.com/SeaOfNodes/Simple - * - * The contents of this file are subject to the terms of the - * Apache License Version 2 (the "APL"). You may not use this - * file except in compliance with the License. A copy of the - * APL may be obtained from: - * http://www.apache.org/licenses/LICENSE-2.0 - */ - -package com.seaofnodes.util; - -import org.jctools.maps.NonBlockingHashMapLong; - -// Simple sparse bitset, with a test-and-set. -public class BitSetSparse { - NonBlockingHashMapLong<String> _set = new NonBlockingHashMapLong<>(); - public boolean tset(int b0, int b1) { return tset(((long)b0<<32)|b1); } - public boolean clr (int b0, int b1) { return clr (((long)b0<<32)|b1); } - public boolean tset(long b) { return _set.put(b,"")!=null; } - public boolean clr (long b) { return _set.remove(b)!=null; } - public boolean test(long b) { return _set.get(b)!=null; } - public BitSetSparse clear() { _set.clear(true); return this; } - public int size() { return _set.size(); } - public int cardinality() { return _set.size(); } - @Override public String toString() { - if( _set.size()==0 ) return "[]"; - SB sb = new SB().p('['); - for( long i : _set.keySetLong() ) - if( i >= (1L<<32) ) sb.p('(').p(i>>32).p(',').p(i&0xFFFFFFFFL).p(')').p(','); - else sb.p(i).p(','); - return sb.unchar().p(']').toString(); - } -} diff --git a/src/main/java/com/seaofnodes/util/IBitSet.java b/src/main/java/com/seaofnodes/util/IBitSet.java deleted file mode 100644 index d0d97585..00000000 --- a/src/main/java/com/seaofnodes/util/IBitSet.java +++ /dev/null @@ -1,164 +0,0 @@ -/** - * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Contributor(s): - * - * The Initial Developer of the Original Software is Cliff Click. - * - * This file is part of the Sea Of Nodes Simple Programming language - * implementation. See https://github.com/SeaOfNodes/Simple - * - * The contents of this file are subject to the terms of the - * Apache License Version 2 (the "APL"). You may not use this - * file except in compliance with the License. A copy of the - * APL may be obtained from: - * http://www.apache.org/licenses/LICENSE-2.0 - */ - -package com.seaofnodes.util; - -import java.util.Iterator; - -// Standard bit-set but supports the notion of an 'infinite extension' of 1. -// i.e. all bits past the end are either 0 or 1. -// Supports update-in-place, mutable, NOT hash-consed -public class IBitSet implements Iterable<Integer> { - private boolean _sign; // false=infinite zeros, true=infinite ones - private final AryInt _bits = new AryInt(); - - // Since mutable, please do not mutate these - public static final IBitSet EMPTY = new IBitSet(); - public static final IBitSet FULL = new IBitSet().flip(); - - private static int idx (int i) { return i>>5; } - private static int mask(int i) { return 1<<(i&31); } - - // Test; returns the value - public boolean tst(int idx) { return _sign != _tst(idx); } - private boolean _tst(int idx) { return (_bits.atX(idx(idx)) & mask(idx)) != 0; } - - // Test and set; returns the old value - public boolean set(int idx) { return _sign ? !_clr(idx) : _set(idx); } - public boolean clr(int idx) { return _sign ? !_set(idx) : _clr(idx); } - - private boolean _set(int idx) { - int widx = idx (idx); - int mask = mask(idx); - int bits = _bits.atX(widx); - _bits.setX(widx, bits | mask); - return (bits&mask)!=0; - } - private boolean _clr(int idx) { - int widx = idx (idx); - int mask = mask(idx); - int bits = _bits.atX(widx); - _bits.setX(widx, bits & ~mask); - while( _bits._len>0 && _bits.last()==0 ) _bits.pop(); // Shrink - return (bits&mask)!=0; - } - // Constant-time, invert all bits - public IBitSet flip() { _sign=!_sign; return this; } - - public int bitCount() { - assert !_sign; // Infinite if sign is set - int sum=0; - for( int i=0; i<_bits._len; i++ ) - sum += Integer.bitCount(_bits._es[i]); - return sum; - } - public int max( ) { - assert !_sign; // Infinite if sign is set - if( _bits._len==0 ) return 0; - return (31 - Integer.numberOfLeadingZeros(_bits.last()))+((_bits._len-1)<<5); - } - - private int wd(int x) { return _bits._es[x]; } - private int xd(int x) { - int b = _bits.atX(x); // zero extend if off end - return _sign ? ~b : b;// adjust for sign - } - - public IBitSet clear() { - _sign=false; - _bits.clear(); - return this; - } - - // OR-into-this - public IBitSet or( IBitSet bs ) { - _sign |= bs._sign; - for( int i=0; i<bs._bits._len; i++ ) - _bits.setX(i,_bits.atX(i)|bs.wd(i)); - return this; - } - // SUBTRACT-from-this - public void subtract( IBitSet bs ) { - for( int i=0; i<bs._bits._len; i++ ) - _bits.setX(i,_bits.atX(i)&~bs.wd(i)); - } - // True if set is empty. The flipped set is never empty. - public boolean is_empty() { return _bits._len==0 && !_sign; } - - // False if any bits in common - public boolean disjoint( IBitSet bs ) { - if( is_empty() ) return true; // Empty set must be disjoint - if( bs.is_empty() ) return true; // Empty set must be disjoint - if( _sign && bs._sign ) return false; // Both extensions are set - IBitSet min = this; - if( _bits._len > bs._bits._len ) { min=bs; bs=this; } // max in bs - if( min._sign && min._bits._len < bs._bits._len ) return false; // Extension in min overlaps last bits in max - for( int i=0; i<min._bits._len; i++ ) - if( (min.wd(i)&bs.wd(i))!= 0 ) - return false; - return true; - } - - // Does 'this' subset 'bs'? - // True if all bits in common: "bs== this.OR (bs)". - public boolean subsetsX( IBitSet bs ) { - assert !bs.is_empty(); // Undefined - int max=Math.max(_bits._len,bs._bits._len); - for( int i=0; i<max; i++ ) - if( (xd(i)|bs.xd(i)) != bs.xd(i) ) // All bits in common - return false; - return true; - } - - @Override public String toString() { return toString(new SB()).toString(); } - public SB toString(SB sb) { - if( _bits._len==0 ) return sb.p(_sign?"[...]":"[]"); - int x = -1; // No range-in-process - sb.p('['); - for( int i=0; i<_bits._len*32+1; i++ ) { - if( tst(i) ) { - if( x==-1 ) x=i; // Start a range - } else { - if( x!=-1 ) { // End a range - if( x+1==i ) sb.p(x).p(','); - else if( x+2==i ) sb.p(x).p(',').p(i-1).p(','); - else sb.p(x).p("...").p(i-1).p(','); - x = -1; - } - } - } - if( x != -1 ) sb.p(x).p("...,"); // Close open range - return sb.unchar().p(']'); - } - - /** @return an iterator */ - @Override public Iterator<Integer> iterator() { return new Iter(); } - private class Iter implements Iterator<Integer> { - int _i=-1; - @Override public boolean hasNext() { - int idx; - while( (idx=idx(++_i)) < _bits._len ) - if( (_bits._es[idx]&mask(_i)) != 0 ) - return true; - return false; - } - @Override public Integer next() { - if( idx(_i) < _bits._len ) return _i; - throw new java.util.NoSuchElementException(); - } - } -} diff --git a/src/main/java/com/seaofnodes/util/IHashMap.java b/src/main/java/com/seaofnodes/util/IHashMap.java deleted file mode 100644 index 2f1a1d12..00000000 --- a/src/main/java/com/seaofnodes/util/IHashMap.java +++ /dev/null @@ -1,34 +0,0 @@ -/** - * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Contributor(s): - * - * The Initial Developer of the Original Software is Cliff Click. - * - * This file is part of the Sea Of Nodes Simple Programming language - * implementation. See https://github.com/SeaOfNodes/Simple - * - * The contents of this file are subject to the terms of the - * Apache License Version 2 (the "APL"). You may not use this - * file except in compliance with the License. A copy of the - * APL may be obtained from: - * http://www.apache.org/licenses/LICENSE-2.0 - */ - -package com.seaofnodes.util; - -import org.jctools.maps.NonBlockingHashMap; - -import java.util.Set; - -@SuppressWarnings("unchecked") -public class IHashMap { - private final NonBlockingHashMap _map = new NonBlockingHashMap(); - public <T> T put(T kv) { _map.put(kv,kv); return kv; } - public <T> T put(T k, T v) { _map.put(k,v); return v; } - public <T> T get(T key) { return (T)_map.get(key); } - public void remove(Object key) { _map.remove(key); } - public void clear() { _map.clear(); } - public boolean isEmpty() { return _map.isEmpty(); } - public <T> Set<T> keySet() { return _map.keySet(); } -} diff --git a/src/main/java/com/seaofnodes/util/UtilUnsafe.java b/src/main/java/com/seaofnodes/util/UtilUnsafe.java deleted file mode 100644 index c98f0d21..00000000 --- a/src/main/java/com/seaofnodes/util/UtilUnsafe.java +++ /dev/null @@ -1,55 +0,0 @@ -/** - * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Contributor(s): - * - * The Initial Developer of the Original Software is Cliff Click. - * - * This file is part of the Sea Of Nodes Simple Programming language - * implementation. See https://github.com/SeaOfNodes/Simple - * - * The contents of this file are subject to the terms of the - * Apache License Version 2 (the "APL"). You may not use this - * file except in compliance with the License. A copy of the - * APL may be obtained from: - * http://www.apache.org/licenses/LICENSE-2.0 - */ - -package com.seaofnodes.util; - -import java.lang.reflect.Field; - -import sun.misc.Unsafe; - -/** - * Simple class to obtain access to the {@link Unsafe} object. {@link Unsafe} - * is required to allow efficient CAS operations on arrays. Note that the - * versions in java.util.concurrent.atomic, such as {@link - * java.util.concurrent.atomic.AtomicLongArray}, require extra memory ordering - * guarantees which are generally not needed in these algorithms and are also - * expensive on most processors. - */ -public class UtilUnsafe { - private UtilUnsafe() { } // dummy private constructor - static final Unsafe UNSAFE = getUnsafe(); - /** Fetch the Unsafe. Use With Caution. */ - public static Unsafe getUnsafe() { - // Not on bootclasspath - if( UtilUnsafe.class.getClassLoader() == null ) - return Unsafe.getUnsafe(); - try { - final Field fld = Unsafe.class.getDeclaredField("theUnsafe"); - fld.setAccessible(true); - return (Unsafe) fld.get(UtilUnsafe.class); - } catch (Exception e) { - throw new RuntimeException("Could not obtain access to sun.misc.Unsafe", e); - } - } - - static final long fieldOffset( Class clz, String field ) { - Field f = null; - try { f = clz.getDeclaredField(field); } - catch( java.lang.NoSuchFieldException e ) { throw new RuntimeException(e); } - return UNSAFE.objectFieldOffset(f); - } -} diff --git a/src/main/java/com/seaofnodes/util/Work.java b/src/main/java/com/seaofnodes/util/Work.java deleted file mode 100644 index 4f34ed21..00000000 --- a/src/main/java/com/seaofnodes/util/Work.java +++ /dev/null @@ -1,79 +0,0 @@ -/** - * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Contributor(s): - * - * The Initial Developer of the Original Software is Cliff Click. - * - * This file is part of the Sea Of Nodes Simple Programming language - * implementation. See https://github.com/SeaOfNodes/Simple - * - * The contents of this file are subject to the terms of the - * Apache License Version 2 (the "APL"). You may not use this - * file except in compliance with the License. A copy of the - * APL may be obtained from: - * http://www.apache.org/licenses/LICENSE-2.0 - */ - -package com.seaofnodes.util; - -import java.util.function.IntSupplier; - -// Simple worklist. Filters dups on a add. -// Constant-time remove until empty. -// Supports psuedo random pop. -@SuppressWarnings("unchecked") -public class Work<E extends IntSupplier> extends BitSetSparse { - private final Ary<E> _work = new Ary(new Object[1],0); - private int _rseed; // Psuedo-random draw - private int _idx; // Next item to get - public Work() { this(123); } // Default seed - public Work(int rseed) { _rseed = rseed; } - public int len() { return _work._len; } - public boolean isEmpty() { return _work.isEmpty(); } - public E add(E e) { // Add, filtering dups - if( e!=null && !tset(e.getAsInt()) ) - _work.push(e); - return e; - } - public void setSeed(int rseed ) { - assert _work.isEmpty(); - _rseed = rseed; - _idx = 0; - } - @Override public Work clear() { - super.clear(); - _work.clear(); - return this; - } - // Bulk adders - public void add(E[] es) { if(es!=null) for( E e : es ) add(e); } - public void addAll(Ary<? extends E> es) { if( es!=null ) for( E e : es ) add(e); } - public void addAll(Work<E> work) { for( Object o : work._work ) add((E)o); } - public boolean on(E e) { return test(e.getAsInt()); } - // Pull a psuedo-random element. Order depends on rseed. - public E pop() { - if( _work._len==0 ) return null; - _idx = (_idx+_rseed)&((1<<30)-1); - E e = _work.del( _idx % _work._len ); - clr(e.getAsInt()); - return e; - } - public E pop_last() { - if( _work._len==0 ) return null; - E e = _work.pop(); - clr(e.getAsInt()); - return e; - } - // Get/delete "idx"th elements; error if OOB. - public E at(int idx) { return _work.at(idx); } - public void del(int idx) { clr((_work.del(idx)).getAsInt()); } - public String print_work() { return _work.toString(); } - @Override public String toString() { - if( _set.size()==0 ) return "[]"; - SB sb = new SB().p('['); - for( E e : _work ) - sb.p(e.getAsInt()).p(','); - return sb.unchar().p(']').toString(); - } -} |