From 9a2ab9bb803aa4da2a6007cc2e945d6bc1fe0b39 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Fri, 25 Aug 2023 23:16:07 +0100 Subject: 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. --- common/README.md | 7 + common/pom.xml | 14 + .../simple/common/CompilerException.java | 11 + .../seaofnodes/simple/common/ErrorListener.java | 266 ++ .../com/seaofnodes/simple/common/Severity.java | 19 + .../java/com/seaofnodes/simple/lexer/aa/Lexer.java | 228 ++ .../com/seaofnodes/simple/lexer/ecstasy/Lexer.java | 3041 ++++++++++++++++++++ .../seaofnodes/simple/lexer/ecstasy/Source.java | 826 ++++++ .../com/seaofnodes/simple/lexer/ecstasy/Token.java | 870 ++++++ common/src/main/java/com/seaofnodes/util/Ary.java | 367 +++ .../src/main/java/com/seaofnodes/util/AryInt.java | 203 ++ .../src/main/java/com/seaofnodes/util/Handy.java | 1778 ++++++++++++ common/src/main/java/com/seaofnodes/util/Hash.java | 299 ++ .../java/com/seaofnodes/util/PackedInteger.java | 1360 +++++++++ common/src/main/java/com/seaofnodes/util/SB.java | 80 + common/src/main/java/com/seaofnodes/util/Util.java | 151 + .../src/main/java/com/seaofnodes/util/VBitSet.java | 27 + .../com/seaofnodes/simple/lexer/TestLexer.java | 37 + 18 files changed, 9584 insertions(+) create mode 100644 common/README.md create mode 100644 common/pom.xml create mode 100644 common/src/main/java/com/seaofnodes/simple/common/CompilerException.java create mode 100644 common/src/main/java/com/seaofnodes/simple/common/ErrorListener.java create mode 100644 common/src/main/java/com/seaofnodes/simple/common/Severity.java create mode 100644 common/src/main/java/com/seaofnodes/simple/lexer/aa/Lexer.java create mode 100644 common/src/main/java/com/seaofnodes/simple/lexer/ecstasy/Lexer.java create mode 100644 common/src/main/java/com/seaofnodes/simple/lexer/ecstasy/Source.java create mode 100644 common/src/main/java/com/seaofnodes/simple/lexer/ecstasy/Token.java create mode 100644 common/src/main/java/com/seaofnodes/util/Ary.java create mode 100644 common/src/main/java/com/seaofnodes/util/AryInt.java create mode 100644 common/src/main/java/com/seaofnodes/util/Handy.java create mode 100644 common/src/main/java/com/seaofnodes/util/Hash.java create mode 100644 common/src/main/java/com/seaofnodes/util/PackedInteger.java create mode 100644 common/src/main/java/com/seaofnodes/util/SB.java create mode 100644 common/src/main/java/com/seaofnodes/util/Util.java create mode 100644 common/src/main/java/com/seaofnodes/util/VBitSet.java create mode 100644 common/src/test/java/com/seaofnodes/simple/lexer/TestLexer.java (limited to 'common') 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 @@ + + + 4.0.0 + + com.seaofnodes + simple + 1.0 + + common + jar + Common Stuff + \ No newline at end of file diff --git a/common/src/main/java/com/seaofnodes/simple/common/CompilerException.java b/common/src/main/java/com/seaofnodes/simple/common/CompilerException.java new file mode 100644 index 00000000..518dcde6 --- /dev/null +++ b/common/src/main/java/com/seaofnodes/simple/common/CompilerException.java @@ -0,0 +1,11 @@ +package com.seaofnodes.simple.common; + +public class CompilerException extends RuntimeException { + public CompilerException(String message) { + super(message); + } + + public CompilerException(String message, Throwable cause) { + super(message, cause); + } +} 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/common/src/main/java/com/seaofnodes/simple/lexer/aa/Lexer.java b/common/src/main/java/com/seaofnodes/simple/lexer/aa/Lexer.java new file mode 100644 index 00000000..162cdea1 --- /dev/null +++ b/common/src/main/java/com/seaofnodes/simple/lexer/aa/Lexer.java @@ -0,0 +1,228 @@ +/** + * 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.simple.lexer.aa; + +import com.seaofnodes.util.AryInt; +import com.seaofnodes.util.SB; + +import java.text.NumberFormat; +import java.text.ParsePosition; + +public class Lexer { + private final String _srcName; // Source for error messages; usually a file name + private final byte[] _buf; + private int _x; // Parser index + private int _lastNWS; // Index of last non-white-space char + private final AryInt _lines; // char offset of each line + + private final NumberFormat _nf; + private final ParsePosition _pp; + private final String _str; + + public Lexer(String srcName, String source) + { + _srcName = srcName; + _buf = source.getBytes(); + _x = 0; + + // Set fields strictly for Java number parsing + _nf = NumberFormat.getInstance(); + _nf.setGroupingUsed(false); + _pp = new ParsePosition(0); + _str = source; // Keep a complete string copy for java number parsing + _lines = new AryInt();// + _lines.push(0); // Line 0 at offset 0 + } + + // Skip WS, return true&skip if match, false & do not skip if miss. + public boolean peek( char c ) { return peek1(skipWS(),c); } + public boolean peek_noWS( char c ) { return peek1(_x >= _buf.length ? -1 : _buf[_x],c); } + // Already skipped WS & have character; + // return true & skip if a match, false& do not skip if a miss. + public boolean peek1( byte c0, char c ) { + assert c0==-1 || c0== _buf[_x]; + if( c0!=c ) return false; + _x++; // Skip peeked character + return true; + } + // Already skipped WS & have character; + // return true&skip if match, false & do not skip if miss. + public boolean peek2( byte c0, String s2 ) { + if( c0 != s2.charAt(0) ) return false; + if( _x+1 >= _buf.length || _buf[_x+1] != s2.charAt(1) ) return false; + _x+=2; // Skip peeked characters + return true; + } + public boolean peek( String s ) { + if( !peek(s.charAt(0)) ) return false; + if( !peek_noWS(s.charAt(1)) ) { _x--; return false; } + return true; + } + // Peek 'c' and NOT followed by 'no' + public boolean peek_not( char c, char no ) { + byte c0 = skipWS(); + if( c0 != c || (_x+1 < _buf.length && _buf[_x+1] == no) ) return false; + _x++; + return true; + } + // Match any of these, and return the match or null + public String peek(String[] toks) { + for( String tok : toks ) if( peek1(tok) ) return tok; + return null; + } + public boolean peek1(String tok) { + for( int i=0; i= _buf.length || _buf[_x+i] != tok.charAt(i) ) + return false; + return true; + } + + + /** Advance parse pointer to the first non-whitespace character, and return + * that character, -1 otherwise. */ + public byte skipWS() { + int oldx = _x; + while( _x < _buf.length ) { + byte c = _buf[_x]; + if( c=='/' && _x+1 < _buf.length && _buf[_x+1]=='/' ) { skipEOL() ; continue; } + if( c=='/' && _x+1 < _buf.length && _buf[_x+1]=='*' ) { skipBlock(); continue; } + if( c=='\n' && _x+1 > _lines.last() ) _lines.push(_x+1); + if( !isWS(c) ) { + if( oldx-1 > _lastNWS && !isWS(_buf[oldx-1]) ) _lastNWS = oldx-1; + return c; + } + _x++; + } + return -1; + } + public void skipEOL () { while( _x < _buf.length && _buf[_x] != '\n' ) _x++; } + public void skipBlock() { throw new UnsupportedOperationException("Block comments not yet implemented"); } + // Advance parse pointer to next WS. Used for parser syntax error recovery. + public void skipNonWS() { + while( _x < _buf.length && !isWS(_buf[_x]) ) _x++; + } + + /** Return true if `c` passes a test */ + public static boolean isWS (byte c) { return c == ' ' || c == '\t' || c == '\n' || c == '\r'; } + public static boolean isAlpha0(byte c) { return ('a'<=c && c <= 'z') || ('A'<=c && c <= 'Z') || (c=='_'); } + public static boolean isAlpha1(byte c) { return isAlpha0(c) || ('0'<=c && c <= '9'); } + public static boolean isJava (byte c) { return isAlpha1(c) || (c=='$') || (c=='.'); } + public static boolean isDigit (byte c) { return '0' <= c && c <= '9'; } + + public String token() { skipWS(); return token0(); } + // Lexical tokens. Any alpha, followed by any alphanumerics is a alpha- + // token; alpha-tokens end with WS or any operator character. Any collection + // of the classic operator characters are a token, except that they will break + // un-ambiguously. + public String token0() { + if( _x >= _buf.length ) return null; + byte c=_buf[_x]; int x = _x; + if( isOp0(c) || (c=='_' && _x+1 < _buf.length && isOp0(_buf[_x+1])) ) + while( _x < _buf.length && isOp1(_buf[_x]) ) _x++; + else if( isAlpha0(c) ) + while( _x < _buf.length && isAlpha1(_buf[_x]) ) _x++; + else return null; // Not a token; specifically excludes e.g. all bytes >= 128, or most bytes < 32 + if( (c==':' || c==',') && _x-x==1 ) // Disallow bare ':' as a token; ambiguous with ?: and type annotations; same for ',' + { _x=x; return null; } // Unwind, not a token + if( c=='-' && _x-x>2 && _buf[x+1]=='>' ) // Disallow leading "->", confusing with function parameter list end; eg "not={x->!x}" + _x=x+2; // Just return the "->" + return new String(_buf,x,_x-x); + } + public boolean isOp(String s) { + if( s==null || s.isEmpty() ) return false; + byte c = (byte)s.charAt(0); + if( !isOp0(c) && (c!='_' || !isOp0((byte)s.charAt(1))) ) return false; + for( int i=1; i^[]~/&|".indexOf(c) != -1; } + public static boolean isOp1(byte c) { return isOp0(c) || ":?_{}".indexOf(c) != -1; } + + public String errLocMsg(String s) { + if( s.charAt(0)=='\n' ) return s; + // find line start + int a=_x; + while( a > 0 && _buf[a-1] != '\n' ) --a; + if( _buf[a]=='\r' ) a++; // do not include leading \n or \n\r + // find line end + int b=_x; + while( b < _buf.length && _buf[b] != '\n' ) b++; + if( b < _buf.length ) b--; // do not include trailing \n or \n\r + // Find line number. Bin-search returns the insertion-point, which is the NEXT + // line unless _x is exactly a line start. + int line = _lines.binary_search(_x); // Find zero-based line insertion point + if( line == _lines._len || _lines.at(line)>_x ) line--; + // error message using 1-based line + SB sb = new SB().p(_srcName).p(':').p(line+1).p(':').p(s).nl(); + sb.p(new String(_buf,a,b-a)).nl(); + int line_start = a; + for( int i=line_start; i<_x; i++ ) + sb.p(' '); + return sb.p('^').nl().toString(); + } + + @Override public String toString() { return new String(_buf,_x,_buf.length-_x); } + @Override public boolean equals(Object loc) { + if( this==loc ) return true; + if( !(loc instanceof Lexer p) ) return false; + return _x==p._x && _srcName.equals(p._srcName); + } + @Override public int hashCode() { + return _srcName.hashCode()+_x; + } +} 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 + { + // ----- 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 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: + * 
+     *   $"x={x}"
+     *
+ * + * @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: + * 
+     *    $|# TOML doc
+     *     |[name]
+     *     |first = "{person.firstname}"
+     *     |last = "{person.lastname}"
+     *
+ * + * @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 + * between 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 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 (-1 or +1) + * + * @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 SpacingElement + */ + 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 LineTerminator + */ + 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 ? "" : 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 KEYWORDS = new HashMap<>(); + /** + * String representations of all tokens that have constant representations. + */ + private static final Map ALL_KEYWORDS = new HashMap<>(); + + /** + * String representations of tokens that have both "normal" and "suffixed" representations. + */ + private static final Map 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/common/src/main/java/com/seaofnodes/util/Ary.java b/common/src/main/java/com/seaofnodes/util/Ary.java new file mode 100644 index 00000000..36654a7f --- /dev/null +++ b/common/src/main/java/com/seaofnodes/util/Ary.java @@ -0,0 +1,367 @@ +/** + * 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.Array; +import java.util.*; +import java.util.function.Function; +import java.util.function.Predicate; + +// ArrayList with saner syntax +public class Ary implements Iterable { + public E[] _es; + public int _len; + public Ary(E[] es) { this(es,es.length); } + public Ary(E[] es, int len) { if( es.length==0 ) es=Arrays.copyOf(es,1); _es=es; _len=len; } + @SuppressWarnings("unchecked") + public Ary(Class clazz) { this((E[]) Array.newInstance(clazz, 1),0); } + + /** @return list is empty */ + public boolean isEmpty() { return _len==0; } + /** @return active list length */ + public int len() { return _len; } + /** @param i element index + * @return element being returned; throws if OOB + * @exception ArrayIndexOutOfBoundsException if !(0 <= i < _len) + */ + public E at( int i ) { + range_check(i); + return _es[i]; + } + /** @param i element index + * @return element being returned, or null if OOB */ + public E atX( int i ) { + return i < _len ? _es[i] : null; + } + /** @return last element */ + public E last( ) { + range_check(0); + return _es[_len-1]; + } + public void last(int i) { + range_check(i); + E tmp = _es[i]; + _es[i] = _es[_len-1]; + _es[_len-1] = tmp; + } + + /** @return remove and return last element */ + public E pop( ) { + range_check(0); + return _es[--_len]; + } + + /** Add element in amortized constant time + * @param e Element to add at end of list + * @return 'this' for flow-coding */ + public Ary add( E e ) { + if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1)); + _es[_len++] = e; + return this; + } + + /** Add element in amortized constant time + * @param e Element to add at end of list + **/ + public E push( E e ) { + if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1)); + return (_es[_len++] = e); + } + + /** Slow, linear-time, element insert. Preserves order. + * @param i index to insert at, between 0 and _len inclusive. + * @param e Element to insert + */ + public void insert( int i, E e ) { + if( i < 0 || i>_len ) + throw new ArrayIndexOutOfBoundsException(""+i+" >= "+_len); + if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1)); + System.arraycopy(_es,i,_es,i+1,(_len++)-i); + _es[i] = e; + } + + /** Fast, constant-time, element removal. Does not preserve order + * @param i element to be removed + * @return element removed */ + public E del( int i ) { + range_check(i); + E tmp = _es[i]; + _es[i]=_es[--_len]; + return tmp; + } + + /** Element removal, using '=='. Does not preserve order. + * @param e element to be removed + * @return element removed */ + public E del( E e ) { + for( int i=0; i<_len; i++ ) { + E tmp = _es[i]; + if( tmp==e ) { + _es[i]=_es[--_len]; + return tmp; + } + } + return null; + } + + /** Slow, linear-time, element removal. Preserves order. + * @param i element to be removed + * @return element removed */ + public E remove( int i ) { + range_check(i); + E e = _es[i]; + System.arraycopy(_es,i+1,_es,i,(--_len)-i); + return e; + } + + /** Remove all elements */ + public void clear( ) { _len=0; } + + public void fill( E e ) { Arrays.fill(_es,0,_len,e); } + + /** Extend and set. null fills as needed and does not throw AIOOBE. + * @param i element to set + * @param e value to set + * @return old value + */ + public E setX( int i, E e ) { + if( i >= _len ) Arrays.fill(_es,_len,_es.length,null); + while( i>= _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + if( i >= _len ) _len = i+1; + return (_es[i] = e); + } + + /** Clear element. Does nothing if element is OOB, since these are clear by + * default. + * @param i element to clear + */ + public void clear( int i ) { if( i<_len ) _es[i]=null; } + + /** Set existing element + * @param i element to set + * @param e value to set + * @return old value + * @exception AIOOBE if !(0 <= i < _len) + */ + public E set( int i, E e ) { + range_check(i); + E old = _es[i]; + _es[i] = e; + return old; + } + + // Increment length, revealing the E behind the _len, or null + public E inc_len( ) { + if( _len >= _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + return _es[_len++]; + } + public Ary set_len( int len ) { + if( len > _len ) + while( len>= _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + _len = len; + while( _es.length > (len<<1) ) // Shrink if hugely too large + _es = Arrays.copyOf(_es,_es.length>>1); + Arrays.fill(_es,len,_es.length,null); + return this; + } + + /** @param c Collection to be added */ + public Ary addAll( Collection c ) { if( c!=null ) for( E e : c ) add(e); return this; } + + /** @param es Array to be added */ + public Ary addAll( F[] es ) { + if( es==null || es.length==0 ) return this; + while( _len+es.length > _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + System.arraycopy(es,0,_es,_len,es.length); + _len += es.length; + return this; + } + + /** @param c Collection to be added */ + public Ary addAll( Ary c ) { + if( c==null || c._len==0 ) return this; + while( _len+c._len > _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + System.arraycopy(c._es,0,_es,_len,c._len); + _len += c._len; + return this; + } + + /** @return compact array version */ + public E[] asAry() { return Arrays.copyOf(_es,_len); } + + /** @param f function to apply to each element. Updates in-place. */ + public Ary map_update( Function f ) { for( int i = 0; i<_len; i++ ) _es[i] = f.apply(_es[i]); return this; } + /** @param P filter out elements failing to pass the predicate; updates in + * place and shuffles list. + * @return this, for flow-coding */ + public Ary filter_update( Predicate P ) { + for( int i=0; i<_len; i++ ) + if( !P.test(_es[i]) ) + del(i--); + return this; + } + /** Sorts in-place + * @param c Comparator to sort by */ + public void sort_update(Comparator c ) { Arrays.sort(_es, 0, _len, c); } + /** Find the first matching element using ==, or -1 if none. Note that + * most del calls shuffle the list, so the first element might be random. + * @param e Element to find + * @return index of first matching element, or -1 if none */ + public int find( E e ) { + for( int i=0; i<_len; i++ ) if( _es[i]==e ) return i; + return -1; + } + /** Find the first element matching predicate P, or -1 if none. Note that + * most del calls shuffle the list, so the first element might be random. + * @param P Predicate to match + * @return index of first matching element, or -1 if none */ + public int find( Predicate P ) { + for( int i=0; i<_len; i++ ) if( P.test(_es[i]) ) return i; + return -1; + } + /** Find and replace the first matching element using ==. + * @param old Element to find + * @param nnn Element replacing old + * @return true if replacement happened */ + public boolean replace( E old, E nnn ) { + for( int i=0; i<_len; i++ ) if( _es[i]==old ) { _es[i]=nnn; return true; } + return false; + } + + + /** Merge-Or. Merge 2 sorted Arys, tossing out duplicates. Return a new + * sorted Ary with the merged list. Undefined if the original arrays are + * not sorted. Error if they are not of the same type. Elements must + * implement Comparable. + * @param a0 Sorted Ary to merge + * @param a1 Sorted Ary to merge + * @return A new sorted merged Ary + */ + public static > Ary merge_or( Ary a0, Ary a1 ) { + int i=0, j=0; + Ary res = new Ary<>(Arrays.copyOf(a0._es,a0._len+a1._len),0); + + while( i0 ) { res.add(y); j++; } + else { res.add(x); i++; j++; } + } + while( i Ary merge_or( Ary a0, Ary a1, Comparator cmpr, Predicate filter) { + int i=0, j=0; + Ary res = new Ary<>(Arrays.copyOf(a0._es,a0._len+a1._len),0); + + while( i0 ) { res.add(y); j++; } + else { res.add(x); i++; j++; } + } + while( i> Ary merge_and( Ary a0, Ary a1 ) { + int i=0, j=0; + Ary res = new Ary<>(Arrays.copyOf(a0._es,Math.min(a0._len,a1._len)),0); + while( i0 ) { j++; } + else { res.add(x); i++; j++; } + } + return res; + } + + /** @return an iterator */ + @Override public Iterator iterator() { return new Iter(); } + private class Iter implements Iterator { + int _i=0; + @Override public boolean hasNext() { return _i<_len; } + @Override public E next() { return _es[_i++]; } + } + + @Override public String toString() { + SB sb = new SB().p('{'); + for( int i=0; i<_len; i++ ) { + if( i>0 ) sb.p(','); + if( _es[i] != null ) sb.p(_es[i].toString()); + } + return sb.p('}').toString(); + } + + private void range_check( int i ) { + if( i < 0 || i>=_len ) + throw new ArrayIndexOutOfBoundsException(""+i+" >= "+_len); + } + + // Note that the hashCode() and equals() are not invariant to changes in the + // underlying array. If the hashCode() is used (e.g., inserting into a + // HashMap) and the then the array changes, the hashCode() will change also. + @Override public boolean equals( Object o ) { + if( this==o ) return true; + if( !(o instanceof Ary ary) ) return false; + if( _len != ary._len ) return false; + if( _es == ary._es ) return true; + for( int i=0; i<_len; i++ ) + if( !(_es[i]==null ? (ary._es[i] == null) : _es[i].equals(ary._es[i])) ) + return false; + return true; + } + @Override public int hashCode( ) { + int sum=_len; + for( int i=0; i<_len; i++ ) + sum += _es[i]==null ? 0 : _es[i].hashCode(); + return sum; + } + + public Ary deepCopy() { + return new Ary<>(_es.clone(),_len); + } +} diff --git a/common/src/main/java/com/seaofnodes/util/AryInt.java b/common/src/main/java/com/seaofnodes/util/AryInt.java new file mode 100644 index 00000000..000f4809 --- /dev/null +++ b/common/src/main/java/com/seaofnodes/util/AryInt.java @@ -0,0 +1,203 @@ +/** + * 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.Arrays; +import java.util.Collection; +import java.util.function.IntUnaryOperator; + +// ArrayList with saner syntax +public class AryInt { + public int[] _es; + public int _len; + public AryInt(int[] es) { this(es,es.length); } + public AryInt(int[] es, int len) { _es=es; _len=len; } + public AryInt() { this(new int[1],0); } + + /** @return list is empty */ + public boolean isEmpty() { return _len==0; } + /** @return active list length */ + public int len() { return _len; } + /** @param i element index + * @return element being returned; throws if OOB */ + public int at( int i ) { + range_check(i); + return _es[i]; + } + /** @param i element index + * @return element being returned, or 0 if OOB */ + public int atX( int i ) { + return i < _len ? _es[i] : 0; + } + /** @return last element */ + public int last( ) { + range_check(0); + return _es[_len-1]; + } + + /** @return remove and return last element */ + public int pop( ) { + range_check(0); + return _es[--_len]; + } + + /** Add element in amortized constant time + * @param e element to add at end of list + * @return 'this' for flow-coding */ + public AryInt push( int e ) { + if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1)); + _es[_len++] = e; + return this; + } + + /** Slow, linear-time, element insert. Preserves order. + * @param i index to insert at, between 0 and _len inclusive. + * @param e intlement to insert + */ + public void insert( int i, int e ) { + if( i < 0 || i>_len ) + throw new ArrayIndexOutOfBoundsException(""+i+" >= "+_len); + if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1)); + System.arraycopy(_es,i,_es,i+1,(_len++)-i); + _es[i] = e; + } + + /** Fast, constant-time, element removal. Does not preserve order + * @param i element to be removed + * @return element removed */ + public int del( int i ) { + range_check(i); + int tmp = _es[i]; + _es[i]=_es[--_len]; + return tmp; + } + + /** Slow, linear-time, element removal. Preserves order. + * @param i element to be removed + * @return element removed */ + public int remove( int i ) { + range_check(i); + int e = _es[i]; + System.arraycopy(_es,i+1,_es,i,(--_len)-i); + return e; + } + + /** Remove all elements */ + public void clear( ) { Arrays.fill(_es,0,_len,0); _len=0; } + + // Extend and set + public int setX( int i, int e ) { + while( i>= _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + if( i >= _len ) _len = i+1; + return (_es[i] = e); + } + + public int set( int i, int e ) { + range_check(i); + return (_es[i] = e); + } + + public AryInt set_as( int e ) { _es[0] = e; _len=1; return this; } + public AryInt set_len( int len ) { + if( len > _len ) + while( len>= _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + _len = len; + while( _es.length > (len<<1) ) // Shrink if hugely too large + _es = Arrays.copyOf(_es,_es.length>>1); + return this; + } + + /** @param c Collection to be added */ + public AryInt addAll( Collection c ) { for( int e : c ) push(e); return this; } + + /** @param es Array to be added */ + public AryInt addAll( int[] es ) { + if( es.length==0 ) return this; + while( _len+es.length > _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + System.arraycopy(es,0,_es,_len,es.length); + _len += es.length; + return this; + } + + public AryInt map_update( IntUnaryOperator f ) { for( int i = 0; i<_len; i++ ) _es[i] = f.applyAsInt(_es[i]); return this; } + + /** @return compact array version, using the internal base array where possible. */ + public int[] asAry() { return _len==_es.length ? _es : Arrays.copyOf(_es,_len); } + + /** Sorts in-place */ + public void sort_update() { Arrays.sort(_es, 0, _len); } + /** Find the first matching element using ==, or -1 if none. Note that + * most del calls shuffle the list, so the first element might be random. + * @param e intlement to find + * @return index of first matching element, or -1 if none */ + public int find( int e ) { + for( int i=0; i<_len; i++ ) if( _es[i]==e ) return i; + return -1; + } + + @Override public String toString() { + SB sb = new SB().p('['); + for( int i=0; i<_len; i++ ) + sb.p(_es[i]).p(','); + return sb.unchar().p(']').toString(); + } + + private void range_check( int i ) { + if( i < 0 || i>=_len ) + throw new ArrayIndexOutOfBoundsException(""+i+" >= "+_len); + } + + // Binary search sorted _es. Returns insertion point. + // Undefined results if _es is not sorted. + public int binary_search( int e ) { + int lo=0, hi=_len-1; + while( lo <= hi ) { + int mid = (hi + lo) >>> 1; // midpoint, rounded down + int mval = _es[mid]; + if( e==mval ) { + // If dups, get to the first. + while( mid>0 && e==_es[mid-1] ) mid--; + return mid; + } + if( e >mval ) lo = mid+1; + else hi = mid-1; + } + return lo; + } + + // Note that the hashCode() and equals() are not invariant to changes in the + // underlying array. If the hashCode() is used (e.g., inserting into a + // HashMap) and the then the array changes, the hashCode() will change also. + @Override public boolean equals( Object o ) { + if( this==o ) return true; + if( !(o instanceof AryInt) ) return false; + AryInt ary = (AryInt)o; + if( _len != ary._len ) return false; + if( _es == ary._es ) return true; + for( int i=0; i<_len; i++ ) + if( _es[i] != ary._es[i] ) + return false; + return true; + } + @Override public int hashCode( ) { + int sum=_len; + for( int i=0; i<_len; i++ ) + sum += _es[i]; + return sum; + } +} 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 byte[]. + * + * @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 int value as an + * unsigned 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 int 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 int 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 int 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 long value as an + * unsigned 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 long 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 long 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 int 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 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 DataInput stream to read from + * + * @return a long value + * + * @throws IOException if an I/O exception occurs + * @throws NumberFormatException if the integer does not fit into + * a long 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 DataOutput stream to write to + * @param n the long 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 DataInput stream to read from + * + * @return an int value in the range Integer.MIN_VALUE..Integer.MAX_VALUE + * + * @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. + *

+ * 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 DataInput stream to read from + * + * @return an int value in the range 0..Integer.MAX_VALUE + * + * @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. + *

+ * 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 DataInput stream to read from + * + * @return an int value in the range 0..Integer.MAX_VALUE, + * or -1 + * + * @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 char + * 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 char + * 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 char + * 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[] 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 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[] 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[] 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 ArrayList 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 ArrayList appendList(ArrayList 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 o1 is equals to o2 + */ + 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 ao1 is less than, equal + * to, or greater than ao2 + */ + 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 byte. + */ + public final static byte[] EMPTY_BYTE_ARRAY = new byte[0]; + + /** + * A constant empty array of char. + */ + public final static char[] EMPTY_CHAR_ARRAY = new char[0]; + + /** + * A constant empty array of String. + */ + 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. + * + *

+ * For example given a class with fields {@code a, b, c, d} of any type, a compound hash can be + * computed via: + * 

{@code
+ * int hash = Hash.of(a,
+ *            Hash.of(b,
+ *            Hash.of(c,
+ *            Hash.of(d))));
+ * }
+ *
+ * + * @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. + * + *

+ * 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.) + *

+ * Values up to 8 bytes can be accessed as a long value, while values of any size can be + * accessed as a BigInteger. + *

+ * The storage format is compressed as much as possible. There are five storage formats: + *

  • + * Tiny: 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. + *
  • + * Small: 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. + *
  • + * Medium: 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. + *
  • + * Large: 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. + *
  • + * Huge: 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. + *
+ *

+ * 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. + * 


+ *     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      *
+ *
+ *

+ * Similarly, by examining the least significant 3 bits of the first byte of an encoded value, the + * encoding can be determined as follows: + * 


+ *     first byte  encoding  bytes
+ *     ----------  --------  -----
+ *      ???????1   Tiny      1
+ *      ?????010   Small     2
+ *      ?????110   Medium    3
+ *      ??????00   Large     2-65
+ *      11111100   Huge      *
+ *
+ */ +public class PackedInteger + implements Comparable + { + // ----- constructors -------------------------------------------------------------------------- + + /** + * Construct an uninitialized PackedInteger. + */ + public PackedInteger() + { + } + + /** + * Construct a PackedInteger using a long value. + * + * @param lVal the long value for the PackedInteger + */ + public PackedInteger(long lVal) + { + setLong(lVal); + } + + /** + * Construct a PackedInteger using a BigInteger value. + * + * @param bigint the BigInteger 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 long value. This + * method is useful for taking advantage of the built-in "cache" of + * commonly-used PackedInteger instances. + * + * @param lVal the long 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 long. + * + * @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 long value of the PackedInteger. If the PackedInteger + * is "big", i.e. if the {@link #isBig} method returns true, then + * this method will throw an IllegalStateException, because the value cannot + * be expressed as a long without losing data. + * + * @return the long 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 long value. + * + * @param lVal the long 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 long, 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 + * not 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 DataOutput stream to write to + * @param l the long 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 DataInput stream to read from + * + * @return a long value + * + * @throws IOException if an I/O exception occurs + * @throws NumberFormatException if the integer does not fit into + * a long 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 long (for signed values). + */ + private boolean m_fBig; + + /** + * The long value if the value fits into a long. Note, the value could be "big", + * as a signed one but still fit the long as unsigned. + */ + private long m_lValue; + + /** + * The BigInteger 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 0. Also used as the smallest 1-, 2-, 4-, + * 8-, 16-, and 32-byte unsigned integer value. + */ + public static final PackedInteger ZERO = valueOf(0L); + /** + * The PackedInteger for the value 1. + */ + public static final PackedInteger ONE = valueOf(1L); + /** + * The PackedInteger for the value -1. + */ + 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/common/src/main/java/com/seaofnodes/util/SB.java b/common/src/main/java/com/seaofnodes/util/SB.java new file mode 100644 index 00000000..4481ce71 --- /dev/null +++ b/common/src/main/java/com/seaofnodes/util/SB.java @@ -0,0 +1,80 @@ +/** + * 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; + + +/** Tight/tiny StringBuilder wrapper. + * Short short names on purpose; so they don't obscure the printing. + * Can't believe this wasn't done long, long ago. */ +public final class SB { + private final StringBuilder _sb; + private int _indent = 0; + public SB( ) { _sb = new StringBuilder( ); } + public SB(String s) { _sb = new StringBuilder(s); } + public SB p( String s ) { _sb.append(s); return this; } + //public SB p( Type t ) { _sb.append(t.toString()); return this; } + public SB p( float s ) { + if( Float.isNaN(s) ) + _sb.append( "Float.NaN"); + else if( Float.isInfinite(s) ) { + _sb.append(s > 0 ? "Float.POSITIVE_INFINITY" : "Float.NEGATIVE_INFINITY"); + } else _sb.append(s); + return this; + } + public SB p( double s ) { + if( Double.isNaN(s) ) + _sb.append("Double.NaN"); + else if( Double.isInfinite(s) ) { + _sb.append(s > 0 ? "Double.POSITIVE_INFINITY" : "Double.NEGATIVE_INFINITY"); + } else _sb.append(s); + return this; + } + public SB p( char s ) { _sb.append(s); return this; } + public SB p( int s ) { _sb.append(s); return this; } + public SB p( long s ) { _sb.append(s); return this; } + public SB p( boolean s) { _sb.append(s); return this; } + // Not spelled "p" on purpose: too easy to accidentally say "p(1.0)" and + // suddenly call the autoboxed version. + public SB pobj( Object s ) { _sb.append(s.toString()); return this; } + public SB i( int d ) { for( int i=0; i int find( E[] es, E e ) { + for( int i=0; i>>(64-k)); } + private static long a,b,c; + private static int x; + static public void add_hash( long h ) { + switch( x ) { + case 0: a+=h; x++; return; + case 1: b+=h; x++; return; + case 2: c+=h; + a -= c; a ^= rot(c, 4); c += b; + b -= a; b ^= rot(a, 6); a += c; + c -= b; c ^= rot(b, 8); b += a; + a -= c; a ^= rot(c,16); c += b; + b -= a; b ^= rot(a,19); a += c; + c -= b; c ^= rot(b, 4); b += a; + x=0; + } + } + // Return the resulting hash, which is never 0 + static public long get_hash() { + if( x!=0 ) { + c ^= b; c -= rot(b,14); + a ^= c; a -= rot(c,11); + b ^= a; b -= rot(a,25); + c ^= b; c -= rot(b,16); + a ^= c; a -= rot(c, 4); + b ^= a; b -= rot(a,14); + c ^= b; c -= rot(b,24); + } + long hash=c; + if( hash==0 ) hash=b; + if( hash==0 ) hash=a; + if( hash==0 ) hash=0xcafebabe; + a=b=c=x=0; + return hash; + } + // Single-use hash spreader + static public long mix_hash(long h0) { + add_hash(h0); + return get_hash(); + } + static public long mix_hash( long h0, long h1 ) { + add_hash(h0); + add_hash(h1); + return get_hash(); + } + static public long mix_hash( long h0, long h1, long h2 ) { + add_hash(h0); + add_hash(h1); + add_hash(h2); + return get_hash(); + } + static public long mix_hash( long h0, long h1, long h2, long h3 ) { + add_hash(h0); + add_hash(h1); + add_hash(h2); + add_hash(h3); + return get_hash(); + } + static public long mix_hash( long h0, long h1, long h2, long h3, long h4 ) { + add_hash(h0); + add_hash(h1); + add_hash(h2); + add_hash(h3); + add_hash(h4); + return get_hash(); + } + + static public int gcd(int x, int y) { + if( x==0 || y== 0 ) return 0; + int a = Math.max(x,y), r; + int b = Math.min(x,y); + while((r=(a % b)) != 0) { a = b; b = r; } + return b; + } + + static public boolean isUpperCase( String s ) { + for( int i=0; ii && k>j; // Arrays were not equals, so at least one element from each copied to other + if( k < xs.length ) + throw new UnsupportedOperationException("Not implemented"); // Compact + return xs; + } + +} diff --git a/common/src/main/java/com/seaofnodes/util/VBitSet.java b/common/src/main/java/com/seaofnodes/util/VBitSet.java new file mode 100644 index 00000000..5d00a9e4 --- /dev/null +++ b/common/src/main/java/com/seaofnodes/util/VBitSet.java @@ -0,0 +1,27 @@ +/** + * 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.BitSet; + +public class VBitSet extends BitSet { + // Cannot override 'set' to return a value... :-P + public boolean tset(int idx) { boolean b = get(idx); set(idx); return b; } + public boolean test(int idx) { return get(idx); } + public VBitSet clr() { clear(); return this; } +} diff --git a/common/src/test/java/com/seaofnodes/simple/lexer/TestLexer.java b/common/src/test/java/com/seaofnodes/simple/lexer/TestLexer.java new file mode 100644 index 00000000..ef29d963 --- /dev/null +++ b/common/src/test/java/com/seaofnodes/simple/lexer/TestLexer.java @@ -0,0 +1,37 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * 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; + +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.Assert; +import org.junit.Test; + +public class TestLexer { + + @Test + public void testLexLineComment() + { + final String source = "//a comment\nx"; + Lexer lexer = new Lexer(new Source(source), new ErrorListener()); + Token token = lexer.next(); + Assert.assertEquals(token.getId(), Token.Id.EOL_COMMENT); + token = lexer.next(); + Assert.assertEquals("x", token.getValueText()); + } +} -- cgit v1.2.3