+++ /dev/null
-/*
- * gnu/regexp/RETokenRepeated.java
- * Copyright (C) 1998-2001 Wes Biggs
- *
- * This library is free software; you can redistribute it and/or modify
- * it under the terms of the GNU Lesser General Public License as published
- * by the Free Software Foundation; either version 2.1 of the License, or
- * (at your option) any later version.
- *
- * This library 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 Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
- */
-
-package gnu.regexp;
-import java.util.Vector;
-
-final class RETokenRepeated extends REToken {
- private REToken token;
- private int min,max;
- private boolean stingy;
-
- RETokenRepeated(int subIndex, REToken token, int min, int max) {
- super(subIndex);
- this.token = token;
- this.min = min;
- this.max = max;
- }
-
- /** Sets the minimal matching mode to true. */
- void makeStingy() {
- stingy = true;
- }
-
- /** Queries if this token has minimal matching enabled. */
- boolean isStingy() {
- return stingy;
- }
-
- /**
- * 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());
- }
-
- // We do need to save every possible point, but the number of clone()
- // invocations here is really a killer for performance on non-stingy
- // repeat operators. I'm open to suggestions...
-
- // Hypothetical question: can you have a RE that matches 1 times,
- // 3 times, 5 times, but not 2 times or 4 times? Does having
- // the subexpression back-reference operator allow that?
-
- boolean match(CharIndexed input, REMatch mymatch) {
- // number of times we've matched so far
- int numRepeats = 0;
-
- // Possible positions for the next repeat to match at
- REMatch newMatch = mymatch;
- REMatch last = null;
- REMatch current;
-
- // Add the '0-repeats' index
- // positions.elementAt(z) == position [] in input after <<z>> matches
- Vector positions = new Vector();
- positions.addElement(newMatch);
-
- // Declare variables used in loop
- REMatch doables;
- REMatch doablesLast;
- REMatch recurrent;
-
- do {
- // Check for stingy match for each possibility.
- if (stingy && (numRepeats >= min)) {
- REMatch result = matchRest(input, newMatch);
- if (result != null) {
- mymatch.assignFrom(result);
- return true;
- }
- }
-
- doables = null;
- doablesLast = null;
-
- // try next repeat at all possible positions
- for (current = newMatch; current != null; current = current.next) {
- recurrent = (REMatch) current.clone();
- if (token.match(input, recurrent)) {
- // add all items in current to doables array
- if (doables == null) {
- doables = recurrent;
- doablesLast = recurrent;
- } else {
- // Order these from longest to shortest
- // Start by assuming longest (more repeats)
- doablesLast.next = recurrent;
- }
- // Find new doablesLast
- while (doablesLast.next != null) {
- doablesLast = doablesLast.next;
- }
- }
- }
- // if none of the possibilities worked out, break out of do/while
- if (doables == null) break;
-
- // reassign where the next repeat can match
- newMatch = doables;
-
- // increment how many repeats we've successfully found
- ++numRepeats;
-
- positions.addElement(newMatch);
- } while (numRepeats < max);
-
- // If there aren't enough repeats, then fail
- if (numRepeats < min) return false;
-
- // We're greedy, but ease off until a true match is found
- int posIndex = positions.size();
-
- // At this point we've either got too many or just the right amount.
- // See if this numRepeats works with the rest of the regexp.
- REMatch allResults = null;
- REMatch allResultsLast = null;
-
- REMatch results = null;
- while (--posIndex >= min) {
- newMatch = (REMatch) positions.elementAt(posIndex);
- results = matchRest(input, newMatch);
- if (results != null) {
- if (allResults == null) {
- allResults = results;
- allResultsLast = results;
- } else {
- // Order these from longest to shortest
- // Start by assuming longest (more repeats)
- allResultsLast.next = results;
- }
- // Find new doablesLast
- while (allResultsLast.next != null) {
- allResultsLast = allResultsLast.next;
- }
- }
- // else did not match rest of the tokens, try again on smaller sample
- }
- if (allResults != null) {
- mymatch.assignFrom(allResults); // does this get all?
- return true;
- }
- // If we fall out, no matches.
- return false;
- }
-
- private REMatch matchRest(CharIndexed input, final REMatch newMatch) {
- REMatch current, single;
- REMatch doneIndex = null;
- REMatch doneIndexLast = null;
- // Test all possible matches for this number of repeats
- for (current = newMatch; current != null; current = current.next) {
- // clone() separates a single match from the chain
- single = (REMatch) current.clone();
- if (next(input, single)) {
- // chain results to doneIndex
- if (doneIndex == null) {
- doneIndex = single;
- doneIndexLast = single;
- } else {
- doneIndexLast.next = single;
- }
- // Find new doneIndexLast
- while (doneIndexLast.next != null) {
- doneIndexLast = doneIndexLast.next;
- }
- }
- }
- return doneIndex;
- }
-
- void dump(StringBuffer 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('?');
- }
-}
projects / org.ibex.core.git / blobdiff