diff options
Diffstat (limited to 'libjava/classpath/gnu/java/util/regex/RETokenRepeated.java')
| -rw-r--r-- | libjava/classpath/gnu/java/util/regex/RETokenRepeated.java | 639 |
1 files changed, 639 insertions, 0 deletions
diff --git a/libjava/classpath/gnu/java/util/regex/RETokenRepeated.java b/libjava/classpath/gnu/java/util/regex/RETokenRepeated.java new file mode 100644 index 000000000..cd8635396 --- /dev/null +++ b/libjava/classpath/gnu/java/util/regex/RETokenRepeated.java @@ -0,0 +1,639 @@ +/* gnu/regexp/RETokenRepeated.java + Copyright (C) 2006 Free Software Foundation, Inc. + +This file is part of GNU Classpath. + +GNU Classpath is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU Classpath is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU Classpath; see the file COPYING. If not, write to the +Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301 USA. + +Linking this library statically or dynamically with other modules is +making a combined work based on this library. Thus, the terms and +conditions of the GNU General Public License cover the whole +combination. + +As a special exception, the copyright holders of this library give you +permission to link this library with independent modules to produce an +executable, regardless of the license terms of these independent +modules, and to copy and distribute the resulting executable under +terms of your choice, provided that you also meet, for each linked +independent module, the terms and conditions of the license of that +module. An independent module is a module which is not derived from +or based on this library. If you modify this library, you may extend +this exception to your version of the library, but you are not +obligated to do so. If you do not wish to do so, delete this +exception statement from your version. */ + + +package gnu.java.util.regex; + +import gnu.java.lang.CPStringBuilder; + +import java.util.ArrayDeque; +import java.util.Deque; + +final class RETokenRepeated extends REToken +{ + private REToken token; + private int min, max; + private boolean stingy; + private boolean possessive; + private int tokenFixedLength; + + RETokenRepeated (int subIndex, REToken token, int min, int max) + { + super (subIndex); + this.token = token; + this.min = min; + this.max = max; + if (token.returnsFixedLengthMatches ()) + { + tokenFixedLength = token.getMaximumLength (); + } + else + { + tokenFixedLength = -1; + } + } + + /** Sets the minimal matching mode to true. */ + void makeStingy () + { + stingy = true; + } + + /** Queries if this token has minimal matching enabled. */ + boolean isStingy () + { + return stingy; + } + + /** Sets possessive matching mode to true. */ + void makePossessive () + { + possessive = true; + } + + /** Queries if this token has possessive matching enabled. */ + boolean isPossessive () + { + return possessive; + } + + /** + * The minimum length of a repeated token is the minimum length + * of the token multiplied by the minimum number of times it must + * match. + */ + int getMinimumLength () + { + return (min * token.getMinimumLength ()); + } + + int getMaximumLength () + { + if (max == Integer.MAX_VALUE) + return Integer.MAX_VALUE; + int tmax = token.getMaximumLength (); + if (tmax == Integer.MAX_VALUE) + return tmax; + return (max * tmax); + } + + // The comment "MUST make a clone" below means that some tests + // failed without doing clone(), + + private static class DoablesFinder + { + private REToken tk; + private CharIndexed input; + private REMatch rematch; + private boolean findFirst; + + private DoablesFinder (REToken tk, CharIndexed input, REMatch mymatch) + { + this.tk = tk; + this.input = input; + this.rematch = (REMatch) mymatch.clone (); // MUST make a clone + this.rematch.backtrackStack = new BacktrackStack (); + findFirst = true; + } + + private REMatch find () + { + int origin = rematch.index; + REMatch rem; + if (findFirst) + { + rem = tk.findMatch (input, rematch); + findFirst = false; + } + else + { + while (true) + { + if (rematch.backtrackStack.empty ()) + { + rem = null; + break; + } + BacktrackStack.Backtrack bt = rematch.backtrackStack.pop (); + rem = bt.token.backtrack (bt.input, bt.match, bt.param); + if (rem != null) + break; + } + } + if (rem == null) + return null; + if (rem.index == origin) + rem.empty = true; + rematch = rem; + return (REMatch) rem.clone (); // MUST make a clone. + } + + boolean noMore () + { + return rematch.backtrackStack.empty (); + } + } + + REMatch findMatch (CharIndexed input, REMatch mymatch) + { + if (tokenFixedLength >= 0) + return findMatchFixedLength (input, mymatch); + BacktrackStack stack = new BacktrackStack (); + stack.push (new StackedInfo (input, 0, mymatch, null, null)); + return findMatch (stack); + } + + REMatch backtrack (CharIndexed input, REMatch mymatch, Object param) + { + if (tokenFixedLength >= 0) + return backtrackFixedLength (input, mymatch, param); + return findMatch ((BacktrackStack) param); + } + + private static class StackedInfo extends BacktrackStack.Backtrack + { + int numRepeats; + int[] visited; + DoablesFinder finder; + StackedInfo (CharIndexed input, int numRepeats, REMatch match, + int[]visited, DoablesFinder finder) + { + super (null, input, match, null); + this.numRepeats = numRepeats; + this.visited = visited; + this.finder = finder; + } + } + + private static class FindMatchControl + { + DoablesFinder finder; + FindMatchControl (DoablesFinder finder) + { + this.finder = finder; + } + } + + private REMatch findMatch (BacktrackStack stack) + { + return findMatch (stack, new ArrayDeque < FindMatchControl > ()); + } + + private REMatch findMatch (BacktrackStack stack, + Deque < FindMatchControl > controlStack) + { + REMatch result = null; + StackedInfo si = null; + CharIndexed input = null; + int numRepeats = 0; + REMatch mymatch = null; + int[] visited = null; + DoablesFinder finder = null; + + // Avoid using recursive calls because a match can be very long. + + // This is the first entry point of this method. + // If you want to call this method recursively and you need the + // result returned, save necessary information in a FindMatchControl + // object and push it to controlStack, then continue from this point. + // You can check the result after exiting MAIN_LOOP. + MAIN_LOOP0: + while (true) + { + + // This is the second entry point of this method. + // If you want to call this method recursively but you do not need the + // result returned, just continue from this point. + MAIN_LOOP: + while (true) + { + + if (stack.empty ()) + break MAIN_LOOP; + si = (StackedInfo) (stack.peek ()); + input = si.input; + numRepeats = si.numRepeats; + mymatch = si.match; + visited = si.visited; + finder = si.finder; + + if (mymatch.backtrackStack == null) + mymatch.backtrackStack = new BacktrackStack (); + + if (numRepeats >= max) + { + stack.pop (); + REMatch m1 = matchRest (input, mymatch); + if (m1 != null) + { + if (!stack.empty ()) + { + m1.backtrackStack.push (new BacktrackStack. + Backtrack (this, input, + mymatch, stack)); + } + result = m1; + break MAIN_LOOP; + } + if (stingy) + { + continue MAIN_LOOP; + } + break MAIN_LOOP; + } + + if (finder == null) + { + finder = new DoablesFinder (token, input, mymatch); + si.finder = finder; + } + + if (numRepeats < min) + { + while (true) + { + REMatch doable = finder.find (); + if (doable == null) + { + if (stack.empty ()) + return null; + stack.pop (); + continue MAIN_LOOP; + } + if (finder.noMore ()) + stack.pop (); + int newNumRepeats = (doable.empty ? min : numRepeats + 1); + stack. + push (new + StackedInfo (input, newNumRepeats, doable, + visited, null)); + continue MAIN_LOOP; + } + } + + if (visited == null) + visited = initVisited (); + + if (stingy) + { + REMatch nextMatch = finder.find (); + if (nextMatch != null && !nextMatch.empty) + { + stack. + push (new + StackedInfo (input, numRepeats + 1, nextMatch, + visited, null)); + } + else + { + stack.pop (); + } + REMatch m1 = matchRest (input, mymatch); + if (m1 != null) + { + if (!stack.empty ()) + { + m1.backtrackStack.push (new BacktrackStack. + Backtrack (this, input, + mymatch, stack)); + } + result = m1; + break MAIN_LOOP; + } + else + { + continue MAIN_LOOP; + } + } + + visited = addVisited (mymatch.index, visited); + + TryAnotherResult taresult = + tryAnother (stack, input, mymatch, numRepeats, finder, visited); + visited = taresult.visited; + switch (taresult.status) + { + case TryAnotherResult.TRY_FURTHER: + controlStack.push (new FindMatchControl (finder)); + continue MAIN_LOOP0; + case TryAnotherResult.RESULT_FOUND: + result = taresult.result; + break MAIN_LOOP; + } + + if (!stack.empty ()) + { + stack.pop (); + } + if (possessive) + { + stack.clear (); + } + REMatch m1 = matchRest (input, mymatch); + if (m1 != null) + { + if (!stack.empty ()) + { + m1.backtrackStack.push (new BacktrackStack. + Backtrack (this, input, mymatch, + stack)); + } + result = m1; + break MAIN_LOOP; + } + + } // MAIN_LOOP + + if (controlStack.isEmpty ()) + return result; + FindMatchControl control = controlStack.pop (); + if (possessive) + { + return result; + } + if (result != null) + { + result.backtrackStack.push (new BacktrackStack. + Backtrack (this, input, mymatch, + stack)); + return result; + } + + finder = control.finder; + + TryAnotherResult taresult = + tryAnother (stack, input, mymatch, numRepeats, finder, visited); + visited = taresult.visited; + switch (taresult.status) + { + case TryAnotherResult.TRY_FURTHER: + controlStack.push (new FindMatchControl (finder)); + continue MAIN_LOOP0; + case TryAnotherResult.RESULT_FOUND: + return taresult.result; + } + continue MAIN_LOOP0; + + } // MAIN_LOOP0 + } + + private static class TryAnotherResult + { + REMatch result; + int status; + static final int RESULT_FOUND = 1; + static final int TRY_FURTHER = 2; + static final int NOTHING_FOUND = 3; + int[] visited; + } + + private TryAnotherResult tryAnother (BacktrackStack stack, + CharIndexed input, REMatch mymatch, + int numRepeats, DoablesFinder finder, + int[]visited) + { + + TryAnotherResult taresult = new TryAnotherResult (); + taresult.visited = visited; + + DO_THIS: + { + + boolean emptyMatchFound = false; + + DO_ONE_DOABLE: + while (true) + { + + REMatch doable = finder.find (); + if (doable == null) + { + break DO_THIS; + } + if (doable.empty) + emptyMatchFound = true; + + if (!emptyMatchFound) + { + int n = doable.index; + if (visitedContains (n, visited)) + { + continue DO_ONE_DOABLE; + } + visited = addVisited (n, visited); + stack. + push (new + StackedInfo (input, numRepeats + 1, doable, visited, + null)); + taresult.visited = visited; + taresult.status = TryAnotherResult.TRY_FURTHER; + return taresult; + } + else + { + REMatch m1 = matchRest (input, doable); + if (possessive) + { + taresult.result = m1; + taresult.status = TryAnotherResult.RESULT_FOUND; + return taresult; + } + if (m1 != null) + { + if (!stack.empty ()) + { + m1.backtrackStack.push (new BacktrackStack. + Backtrack (this, input, mymatch, + stack)); + } + taresult.result = m1; + taresult.status = TryAnotherResult.RESULT_FOUND; + return taresult; + } + } + + } // DO_ONE_DOABLE + + } // DO_THIS + + taresult.status = TryAnotherResult.NOTHING_FOUND; + return taresult; + + } + + boolean match (CharIndexed input, REMatch mymatch) + { + setHitEnd (input, mymatch); + REMatch m1 = findMatch (input, mymatch); + if (m1 != null) + { + mymatch.assignFrom (m1); + return true; + } + return false; + } + + // Array visited is an array of character positions we have already + // visited. visited[0] is used to store the effective length of the + // array. + private static int[] initVisited () + { + int[] visited = new int[32]; + visited[0] = 0; + return visited; + } + + private static boolean visitedContains (int n, int[]visited) + { + // Experience tells that for a small array like this, + // simple linear search is faster than binary search. + for (int i = 1; i < visited[0]; i++) + { + if (n == visited[i]) + return true; + } + return false; + } + + private static int[] addVisited (int n, int[]visited) + { + if (visitedContains (n, visited)) + return visited; + if (visited[0] >= visited.length - 1) + { + int[] newvisited = new int[visited.length + 32]; + System.arraycopy (visited, 0, newvisited, 0, visited.length); + visited = newvisited; + } + visited[0]++; + visited[visited[0]] = n; + return visited; + } + + private REMatch matchRest (CharIndexed input, final REMatch newMatch) + { + if (next (input, newMatch)) + { + return newMatch; + } + return null; + } + + private REMatch findMatchFixedLength (CharIndexed input, REMatch mymatch) + { + if (mymatch.backtrackStack == null) + mymatch.backtrackStack = new BacktrackStack (); + int numRepeats = + token.findFixedLengthMatches (input, (REMatch) mymatch.clone (), max); + if (numRepeats == Integer.MAX_VALUE) + numRepeats = min; + int count = numRepeats - min + 1; + if (count <= 0) + return null; + int index = 0; + if (!stingy) + index = mymatch.index + (tokenFixedLength * numRepeats); + else + index = mymatch.index + (tokenFixedLength * min); + return findMatchFixedLength (input, mymatch, index, count); + } + + private REMatch backtrackFixedLength (CharIndexed input, REMatch mymatch, + Object param) + { + int[] params = (int[]) param; + int index = params[0]; + int count = params[1]; + return findMatchFixedLength (input, mymatch, index, count); + } + + private REMatch findMatchFixedLength (CharIndexed input, REMatch mymatch, + int index, int count) + { + REMatch tryMatch = (REMatch) mymatch.clone (); + while (true) + { + tryMatch.index = index; + REMatch m = matchRest (input, tryMatch); + count--; + if (stingy) + index += tokenFixedLength; + else + index -= tokenFixedLength; + if (possessive) + return m; + if (m != null) + { + if (count > 0) + { + m.backtrackStack.push (new BacktrackStack. + Backtrack (this, input, mymatch, + new int[] + { + index, count})); + } + return m; + } + if (count <= 0) + return null; + } + } + + void dump (CPStringBuilder os) + { + os.append ("(?:"); + token.dumpAll (os); + os.append (')'); + if ((max == Integer.MAX_VALUE) && (min <= 1)) + os.append ((min == 0) ? '*' : '+'); + else if ((min == 0) && (max == 1)) + os.append ('?'); + else + { + os.append ('{').append (min); + if (max > min) + { + os.append (','); + if (max != Integer.MAX_VALUE) + os.append (max); + } + os.append ('}'); + } + if (stingy) + os.append ('?'); + } +} |