/*
* reserved comment block
* DO NOT REMOVE OR ALTER!
*/
/*
* Copyright 1999-2004 The Apache Software Foundation.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/**
* A regular expression compiler class. This class compiles a pattern string into a
* regular expression program interpretable by the RE evaluator class. The 'recompile'
* command line tool uses this compiler to pre-compile regular expressions for use
* with RE. For a description of the syntax accepted by RECompiler and what you can
* do with regular expressions, see the documentation for the RE matcher class.
*
* @see RE
* @see recompile
*
* @author <a href="mailto:jonl@muppetlabs.com">Jonathan Locke</a>
* @author <a href="mailto:gholam@xtra.co.nz">Michael McCallum</a>
*/
public class RECompiler
{
// The compiled program
// Input state for compiling regular expression
// Node flags
// Special types of 'escapes'
// {m,n} stacks
// Lookup table for POSIX character class names
static
{
}
/**
* Constructor. Creates (initially empty) storage for a regular expression program.
*/
public RECompiler()
{
// Start off with a generous, yet reasonable, initial size
instruction = new char[128];
lenInstruction = 0;
}
/**
* Ensures that n more characters can fit in the program buffer.
* If n more can't fit, then the size is doubled until it can.
* @param n Number of additional characters to ensure will fit.
*/
void ensure(int n)
{
// Get current program length
// If the current length + n more is too much
if (lenInstruction + n >= curlen)
{
// Double the size of the program array until n more will fit
while (lenInstruction + n >= curlen)
{
curlen *= 2;
}
// Allocate new program array and move data into it
char[] newInstruction = new char[curlen];
}
}
/**
* Emit a single character into the program stream.
* @param c Character to add
*/
void emit(char c)
{
// Make room for character
ensure(1);
// Add character
instruction[lenInstruction++] = c;
}
/**
* Inserts a node with a given opcode and opdata at insertAt. The node relative next
* pointer is initialized to 0.
* @param opcode Opcode for new node
* @param opdata Opdata for new node (only the low 16 bits are currently used)
* @param insertAt Index at which to insert the new node in the program
*/
{
// Make room for a new node
// Move everything from insertAt to the end down nodeSize elements
System.arraycopy(instruction, insertAt, instruction, insertAt + RE.nodeSize, lenInstruction - insertAt);
}
/**
* Appends a node to the end of a node chain
* @param node Start of node chain to traverse
* @param pointTo Node to have the tail of the chain point to
*/
{
// Traverse the chain until the next offset is 0
// while the 'node' is not the last in the chain
// and the 'node' is not the last in the program.
{
// if the node we are supposed to point to is in the chain then
// point to the end of the program instead.
// Michael McCallum <gholam@xtra.co.nz>
// FIXME: // This is a _hack_ to stop infinite programs.
// I believe that the implementation of the reluctant matches is wrong but
// have not worked out a better way yet.
}
}
// if we have reached the end of the program then dont set the pointTo.
// im not sure if this will break any thing but passes all the tests.
if ( node < lenInstruction ) {
// Point the last node in the chain to pointTo.
}
}
/**
* Adds a new node
* @param opcode Opcode for node
* @param opdata Opdata for node (only the low 16 bits are currently used)
* @return Index of new node in program
*/
{
// Make room for a new node
// Add new node at end
// Return index of new node
}
/**
* Throws a new internal error exception
* @exception Error Thrown in the event of an internal error.
*/
{
throw new Error("Internal error!");
}
/**
* Throws a new syntax error exception
* @exception RESyntaxException Thrown if the regular expression has invalid syntax.
*/
{
throw new RESyntaxException(s);
}
/**
* Allocate storage for brackets only as needed
*/
void allocBrackets()
{
// Allocate bracket stacks if not already done
if (bracketStart == null)
{
// Allocate storage
bracketStart = new int[maxBrackets];
bracketEnd = new int[maxBrackets];
bracketMin = new int[maxBrackets];
bracketOpt = new int[maxBrackets];
// Initialize to invalid values
for (int i = 0; i < maxBrackets; i++)
{
}
}
}
/** Enlarge storage for brackets only as needed. */
synchronized void reallocBrackets() {
// trick the tricky
if (bracketStart == null) {
}
// Initialize to invalid values
}
bracketEnd = new_bE;
bracketMin = new_bM;
bracketOpt = new_bO;
}
/**
* Match bracket {m,n} expression put results in bracket member variables
* @exception RESyntaxException Thrown if the regular expression has invalid syntax.
*/
{
// Current character must be a '{'
{
}
// Next char must be a digit
{
syntaxError("Expected digit");
}
// Get min ('m' of {m,n}) number
{
}
try
{
}
catch (NumberFormatException e)
{
syntaxError("Expected valid number");
}
// If out of input, fail
{
syntaxError("Expected comma or right bracket");
}
// If end of expr, optional limit is 0
{
idx++;
return;
}
// Must have at least {m,} and maybe {m,n}.
{
syntaxError("Expected comma");
}
// If out of input, fail
{
syntaxError("Expected comma or right bracket");
}
// If {m,} max is unlimited
{
idx++;
return;
}
// Next char must be a digit
{
syntaxError("Expected digit");
}
// Get max number
{
}
try
{
}
catch (NumberFormatException e)
{
syntaxError("Expected valid number");
}
// Optional repetitions must be >= 0
{
syntaxError("Bad range");
}
// Must have close brace
{
syntaxError("Missing close brace");
}
}
/**
* Match an escape sequence. Handles quoted chars and octal escapes as well
* as normal escape characters. Always advances the input stream by the
* right amount. This code "understands" the subtle difference between an
* octal escape and a backref. You can access the type of ESC_CLASS or
* ESC_COMPLEX or ESC_BACKREF by looking at pattern[idx - 1].
* @return ESC_* code or character if simple escape
* @exception RESyntaxException Thrown if the regular expression has invalid syntax.
*/
{
// "Shouldn't" happen
{
}
// Escape shouldn't occur as last character in string!
{
syntaxError("Escape terminates string");
}
// Switch on character after backslash
idx += 2;
switch (escapeChar)
{
return ESC_COMPLEX;
return ESC_CLASS;
case 'u':
case 'x':
{
// Exact required hex digits for escape type
// Parse up to hexDigits characters from input
int val = 0;
{
// Get char
// If it's a hexadecimal digit (0-9)
if (c >= '0' && c <= '9')
{
// Compute new value
}
else
{
// If it's a hexadecimal letter (a-f)
c = Character.toLowerCase(c);
if (c >= 'a' && c <= 'f')
{
// Compute new value
}
else
{
// If it's not a valid digit or hex letter, the escape must be invalid
// because hexDigits of input have not been absorbed yet.
}
}
}
return val;
}
case 't':
return '\t';
case 'n':
return '\n';
case 'r':
return '\r';
case 'f':
return '\f';
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
// An octal escape starts with a 0 or has two digits in a row
{
// Handle \nnn octal escapes
{
{
}
}
return val;
}
// It's actually a backreference (\[1-9]), not an escape
return ESC_BACKREF;
default:
// Simple quoting of a character
return escapeChar;
}
}
/**
* Compile a character class
* @return Index of class node
* @exception RESyntaxException Thrown if the regular expression has invalid syntax.
*/
{
// Check for bad calling or empty class
{
}
// Check for unterminated or empty class
{
syntaxError("Empty or unterminated class");
}
// Check for POSIX character class
{
// Skip colon
idx++;
// POSIX character classes are denoted with lowercase ASCII strings
{
idx++;
}
// Should be a ":]" to terminate the POSIX character class
{
// Get character class
// Select the POSIX class id
if (i != null)
{
// Move past colon and right bracket
idx += 2;
// Return new POSIX character class node
}
}
syntaxError("Invalid POSIX character class syntax");
}
// Try to build a class. Create OP_ANYOF node
// Parse class declaration
char last = CHAR_INVALID;
char simpleChar = 0;
boolean include = true;
boolean definingRange = false;
char rangeEnd;
{
// Switch on character
{
case '^':
{
}
idx++;
continue;
case '\\':
{
// Escape always advances the stream
int c;
switch (c = escape ())
{
case ESC_COMPLEX:
case ESC_BACKREF:
// Word boundaries and backrefs not allowed in a character class!
syntaxError("Bad character class");
case ESC_CLASS:
// Classes can't be an endpoint of a range
if (definingRange)
{
syntaxError("Bad character class");
}
// Handle specific type of class (some are ok)
{
syntaxError("Bad character class");
break;
// Fall through!
break;
}
// Make last char invalid (can't be a range start)
last = CHAR_INVALID;
break;
default:
// Escape is simple so treat as a simple char
simpleChar = (char) c;
break switchOnCharacter;
}
}
continue;
case '-':
// Start a range if one isn't already started
if (definingRange)
{
syntaxError("Bad class range");
}
definingRange = true;
// If no last character, start of range is 0
// Premature end of range. define up to Character.MAX_VALUE
{
break;
}
continue;
default:
break;
}
// Handle simple character simpleChar
if (definingRange)
{
// if we are defining a range make it now
// Actually create a range if the range is ok
if (rangeStart >= rangeEnd)
{
syntaxError("Bad character class");
}
// We are done defining the range
last = CHAR_INVALID;
definingRange = false;
}
else
{
// If simple character and not start of range, include it
{
}
last = simpleChar;
}
}
// Shouldn't be out of input
{
syntaxError("Unterminated character class");
}
// Absorb the ']' end of class marker
idx++;
// Emit character class definition
{
}
return ret;
}
/**
* Absorb an atomic character string. This method is a little tricky because
* it can un-include the last character of string if a closure operator follows.
* This is correct because *+? have higher precedence than concatentation (thus
* ABC* means AB(C*) and NOT (ABC)*).
* @return Index of new atom node
* @exception RESyntaxException Thrown if the regular expression has invalid syntax.
*/
{
// Create a string node
// Length of atom
int lenAtom = 0;
// Loop while we've got input
{
// Is there a next char?
{
// If the next 'char' is an escape, look past the whole escape
{
escape();
{
}
}
// Switch on next char
switch (c)
{
case '{':
case '?':
case '*':
case '+':
// If the next character is a closure operator and our atom is non-empty, the
// current character should bind to the closure operator rather than the atom
if (lenAtom != 0)
{
break atomLoop;
}
}
}
// Switch on current char
{
case ']':
case '^':
case '$':
case '.':
case '[':
case '(':
case ')':
case '|':
break atomLoop;
case '{':
case '?':
case '*':
case '+':
// We should have an atom by now
if (lenAtom == 0)
{
// No atom before closure
syntaxError("Missing operand to closure");
}
break atomLoop;
case '\\':
{
// Get the escaped character (advances input automatically)
int idxBeforeEscape = idx;
int c = escape();
// Check if it's a simple escape (as opposed to, say, a backreference)
{
// Not a simple escape, so backup to where we were before the escape.
break atomLoop;
}
// Add escaped char to atom
emit((char) c);
lenAtom++;
}
break;
default:
// Add normal character to atom
lenAtom++;
break;
}
}
// This "shouldn't" happen
if (lenAtom == 0)
{
}
// Emit the atom length into the program
return ret;
}
/**
* Match a terminal node.
* @param flags Flags
* @return Index of terminal node (closeable)
* @exception RESyntaxException Thrown if the regular expression has invalid syntax.
*/
{
{
case '[':
return characterClass();
case '(':
case ')':
syntaxError("Unexpected close paren");
case '|':
case ']':
syntaxError("Mismatched class");
case 0:
syntaxError("Unexpected end of input");
case '?':
case '+':
case '{':
case '*':
syntaxError("Missing operand to closure");
case '\\':
{
// Don't forget, escape() advances the input stream!
int idxBeforeEscape = idx;
// Switch on escaped character
switch (escape())
{
case ESC_CLASS:
case ESC_COMPLEX:
case ESC_BACKREF:
{
if (parens <= backreference)
{
syntaxError("Bad backreference");
}
}
default:
// We had a simple escape and we want to have it end up in
// an atom, so we back up and fall though to the default handling
break;
}
}
}
// Everything above either fails or returns.
// If it wasn't one of the above, it must be the start of an atom.
return atom();
}
/**
* Compile a possibly closured terminal
* @param flags Flags passed by reference
* @return Index of closured node
* @exception RESyntaxException Thrown if the regular expression has invalid syntax.
*/
{
// Before terminal
int idxBeforeTerminal = idx;
// Values to pass by reference to terminal()
int[] terminalFlags = { NODE_NORMAL };
// Get terminal symbol
// Or in flags from terminal symbol
// Advance input, set NODE_NULLABLE flag and do sanity checks
{
return ret;
}
boolean greedy = true;
switch (closureType)
{
case '?':
case '*':
// The current node can be null
case '+':
// Eat closure character
idx++;
case '{':
// Don't allow blantant stupidity
{
syntaxError("Bad closure operand");
}
{
syntaxError("Closure operand can't be nullable");
}
break;
}
// If the next character is a '?', make the closure non-greedy (reluctant)
{
idx++;
greedy = false;
}
if (greedy)
{
// Actually do the closure now
switch (closureType)
{
case '{':
{
// We look for our bracket in the list
boolean found = false;
int i;
for (i = 0; i < brackets; i++)
{
if (bracketStart[i] == idx)
{
found = true;
break;
}
}
// If its not in the list we parse the {m,n}
if (!found)
{
if (brackets >= maxBrackets)
{
}
bracket();
i = brackets++;
}
// Process min first
if (bracketMin[i]-- > 0)
{
// Rewind stream and run it through again - more matchers coming
for (int j = 0; j < brackets; j++) {
if (j != i && bracketStart[j] < idx
&& bracketStart[j] >= idxBeforeTerminal)
{
brackets--;
}
}
} else {
// Bug #1030: No optinal matches - no need to rewind
idx = bracketEnd[i];
}
break;
}
// Do the right thing for maximum ({m,})
if (bracketOpt[i] == bracketUnbounded)
{
// Drop through now and closure expression.
// We are done with the {m,} expr, so skip rest
closureType = '*';
bracketOpt[i] = 0;
idx = bracketEnd[i];
}
else
if (bracketOpt[i]-- > 0)
{
if (bracketOpt[i] > 0)
{
// More optional matchers - 'play it again sam!'
} else {
// Bug #1030: We are done - this one is last and optional
idx = bracketEnd[i];
}
// Drop through to optionally close
closureType = '?';
}
else
{
// Rollback terminal - neither min nor opt matchers present
// We are done. skip the rest of {m,n} expr
idx = bracketEnd[i];
break;
}
}
// Fall through!
case '?':
case '*':
if (!greedy)
{
break;
}
if (closureType == '?')
{
// X? is compiled as (X|)
}
if (closureType == '*')
{
// X* is compiled as (X{gotoX}|)
}
break;
case '+':
{
// X+ is compiled as X({gotoX}|)
int branch;
}
break;
}
}
else
{
// Add end after closured subexpr
// Actually do the closure now
switch (closureType)
{
case '?':
break;
case '*':
break;
case '+':
break;
}
// Point to the expr after the closure
}
return ret;
}
/**
* Compile one branch of an or operator (implements concatenation)
* @param flags Flags passed by reference
* @return Pointer to branch node
* @exception RESyntaxException Thrown if the regular expression has invalid syntax.
*/
{
// Get each possibly closured piece and concat
int node;
int chain = -1;
int[] closureFlags = new int[1];
boolean nullable = true;
{
// Get new node
{
nullable = false;
}
// If there's a chain, append to the end
if (chain != -1)
{
}
// Chain starts at current
}
// If we don't run loop, make a nothing node
if (chain == -1)
{
}
// Set nullable flag for this branch
if (nullable)
{
}
return ret;
}
/**
* Compile an expression with possible parens around it. Paren matching
* is done at this level so we can tie the branch tails together.
* @param flags Flag value passed by reference
* @return Node index of expression in instruction array
* @exception RESyntaxException Thrown if the regular expression has invalid syntax.
*/
{
// Create open paren node unless we were called from the top level (which has no parens)
int paren = -1;
int ret = -1;
int closeParens = parens;
{
// if its a cluster ( rather than a proper subexpression ie with backrefs )
{
paren = 2;
idx += 3;
}
else
{
paren = 1;
idx++;
}
}
// Create a branch node
if (ret == -1)
{
}
else
{
}
// Loop through branches
{
idx++;
}
// Create an ending node (either a close paren or an OP_END)
int end;
if ( paren > 0 )
{
{
idx++;
}
else
{
syntaxError("Missing close paren");
}
if ( paren == 1 )
{
}
else
{
}
}
else
{
}
// Append the ending node to the ret nodelist
// Hook the ends of each branch to the end node
int currentNode = ret;
// while the next node o
{
// If branch, make the end of the branch's operand chain point to the end node.
{
}
}
// Return the node list
return ret;
}
/**
* Compiles a regular expression pattern into a program runnable by the pattern
* matcher class 'RE'.
* @param pattern Regular expression pattern to compile (see RECompiler class
* for details).
* @return A compiled regular expression program.
* @exception RESyntaxException Thrown if the regular expression has invalid syntax.
* @see RECompiler
* @see RE
*/
{
// Initialize variables for compilation
// Initialize pass by reference flags value
int[] flags = { NODE_TOPLEVEL };
// Parse expression
// Should be at end of input
{
{
syntaxError("Unmatched close paren");
}
syntaxError("Unexpected input remains");
}
// Return the result
char[] ins = new char[lenInstruction];
}
/**
* Local, nested class for maintaining character ranges for character classes.
*/
class RERange
{
/**
* Deletes the range at a given index from the range lists
* @param index Index of range to delete from minRange and maxRange arrays.
*/
{
// Return if no elements left or index is out of range
{
return;
}
// Move elements down
{
{
}
}
// One less element now
num--;
}
/**
* Merges a range into the range list, coalescing ranges if possible.
* @param min Minimum end of range
* @param max Maximum end of range
*/
{
// Loop through ranges
for (int i = 0; i < num; i++)
{
// Min-max is subsumed by minRange[i]-maxRange[i]
{
return;
}
// Min-max subsumes minRange[i]-maxRange[i]
{
delete(i);
return;
}
// Min is in the range, but max is outside
{
delete(i);
return;
}
// Max is in the range, but min is outside
{
delete(i);
return;
}
}
// Must not overlap any other ranges
{
size *= 2;
}
num++;
}
/**
* Removes a range by deleting or shrinking all other ranges
* @param min Minimum end of range
* @param max Maximum end of range
*/
{
// Loop through ranges
for (int i = 0; i < num; i++)
{
// minRange[i]-maxRange[i] is subsumed by min-max
{
delete(i);
i--;
return;
}
// min-max is subsumed by minRange[i]-maxRange[i]
{
delete(i);
{
}
{
}
return;
}
// minRange is in the range, but maxRange is outside
{
return;
}
// maxRange is in the range, but minRange is outside
{
return;
}
}
}
/**
* Includes (or excludes) the range from min to max, inclusive.
* @param min Minimum end of range
* @param max Maximum end of range
* @param include True if range should be included. False otherwise.
*/
{
if (include)
{
}
else
{
}
}
/**
* Includes a range with the same min and max
* @param minmax Minimum and maximum end of range (inclusive)
* @param include True if range should be included. False otherwise.
*/
{
}
}
}