1 files changed, 263 insertions, 169 deletions

diff --git a/libjava/classpath/gnu/regexp/RETokenRepeated.java b/libjava/classpath/gnu/regexp/RETokenRepeated.java
index 2d019c53cbd..1bad4c79292 100644
--- a/libjava/classpath/gnu/regexp/RETokenRepeated.java
+++ b/libjava/classpath/gnu/regexp/RETokenRepeated.java
@@ -38,20 +38,27 @@ exception statement from your version. */
 
 package gnu.regexp;
 
-import java.util.Vector;
-import java.util.Arrays;
+// import java.util.Vector;
+// import java.util.Stack;
 
 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. */
@@ -90,69 +97,235 @@ final class RETokenRepeated extends REToken {
 	return (max * tmax);
     }
 
-    private static REMatch findDoables(REToken tk,
-			CharIndexed input, REMatch mymatch) {
-
-	    REMatch.REMatchList doables = new REMatch.REMatchList();
-
-	    // try next repeat at all possible positions
-	    for (REMatch current = mymatch;
-		 current != null; current = current.next) {
-		REMatch recurrent = (REMatch) current.clone();
-		int origin = recurrent.index;
-		tk = (REToken) tk.clone();
-		tk.next = tk.uncle = null;
-		recurrent.matchFlags |= REMatch.MF_FIND_ALL;
-		if (tk.match(input, recurrent)) {
-		    for (REMatch m = recurrent; m != null; m = m.next) {
-			m.matchFlags &= ~REMatch.MF_FIND_ALL;
+    // 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;
 		    }
-		    if (recurrent.index == origin) recurrent.empty = true;
-		    // add all items in current to doables array
-		    doables.addTail(recurrent);
+		    BacktrackStack.Backtrack bt = rematch.backtrackStack.pop();
+		    rem = bt.token.backtrack(bt.input, bt.match, bt.param);
+		    if (rem != null) break;
 		}
 	    }
-	    return doables.head;
+	    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();
+	}
     }
 
-    // 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...
+    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);
+    }
 
-    // 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?
+    REMatch backtrack(CharIndexed input, REMatch mymatch, Object param) {
+        if (tokenFixedLength >= 0) return backtrackFixedLength(input, mymatch, param);
+	return findMatch((BacktrackStack)param);
+    }
 
-    boolean match(CharIndexed input, REMatch mymatch) {
+    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;
+	}
+    }
 
-        boolean stopMatchingIfSatisfied =
-		(mymatch.matchFlags & REMatch.MF_FIND_ALL) == 0;
+    private REMatch findMatch(BacktrackStack stack) {
+        // Avoid using recursive calls.
+	MAIN_LOOP:
+	while (true) {
+
+	if (stack.empty()) return null;
+	StackedInfo si = (StackedInfo)(stack.peek());
+	CharIndexed input = si.input;
+        int numRepeats = si.numRepeats;
+        REMatch mymatch = si.match;
+	int[] visited = si.visited;
+        DoablesFinder 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));
+		}
+		return m1;
+	    }
+	    if (stingy) {
+		continue MAIN_LOOP;
+	    }
+	    return null;
+	}
 
-	REMatch newMatch = matchMinimum(input, mymatch);
-	if (newMatch == null) return false;
+        if (finder == null) {
+	    finder = new DoablesFinder(token, input, mymatch);
+	    si.finder = finder;
+	}
 
-	// Array of positions we have already visited
-	int[] visited = initVisited();
-	for (REMatch m = newMatch; m != null; m = m.next) {
-	    visited = addVisited(m.index, visited);
+        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;
+	    }
 	}
 
-	int max1 = decreaseMax(max, min);
+	if (visited == null) visited = initVisited();
 
-	newMatch = _match(input, newMatch, max1,
-	    stopMatchingIfSatisfied, visited);
-	if (newMatch != null) {
-	    mymatch.assignFrom(newMatch);
-	    return true;
+	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));
+		}
+	        return m1;
+	    }
+	    else {
+		continue MAIN_LOOP;
+	    }
 	}
-	return false;
-    }
 
-    private static int decreaseMax(int m, int n) {
-        if (m == Integer.MAX_VALUE) return m;
-	return m - n;
+	visited = addVisited(mymatch.index, visited);
+
+	DO_THIS:
+	do {
+
+	    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)) {
+		    visited = addVisited(n, visited);
+	        }
+		else {
+		    continue DO_ONE_DOABLE;
+		}
+	        stack.push(new StackedInfo(
+		    input, numRepeats + 1, doable, visited, null));
+	        REMatch m1 = findMatch(stack);
+		if (possessive) {
+		    return m1;
+		}
+		if (m1 != null) {
+		    m1.backtrackStack.push(new BacktrackStack.Backtrack(
+                        this, input, mymatch, stack));
+		    return m1;
+		}
+	    }
+	    else {
+	        REMatch m1 = matchRest(input, doable);
+		if (possessive) {
+		    return m1;
+		}
+	        if (m1 != null) {
+		    if (! stack.empty()) {
+		        m1.backtrackStack.push(new BacktrackStack.Backtrack(
+                            this, input, mymatch, stack));
+		    } 
+		    return m1;
+		}
+	    }
+
+	    } // DO_ONE_DOABLE
+
+	} while (false); // DO_THIS only once;
+
+	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));
+	    }
+	    return m1;
+	}
+
+	} // MAIN_LOOP
     }
 
+    boolean match(CharIndexed input, REMatch 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.
@@ -183,134 +356,55 @@ final class RETokenRepeated extends REToken {
 	return visited;
     }
 
-    private REMatch _match(CharIndexed input, REMatch mymatch,
-    	    int max1, boolean stopMatchingIfSatisfied,
-	    int[] visited) {
-
-        if (max1 == 0) {
-	    return matchRest(input, mymatch);
-	}
-	max1 = decreaseMax(max1, 1);
-
-	REMatch.REMatchList allResults = new REMatch.REMatchList();
-
-	// Depth-first search
-
-	for (REMatch cur = mymatch; cur != null; cur = cur.next) {
-
-	    REMatch cur1 = (REMatch) cur.clone();
-
-	    if (stingy) {
-	        REMatch results = matchRest(input, cur1);
-	        if (results != null) {
-	            if (stopMatchingIfSatisfied) {
-		        return results;
-		    }
-		    allResults.addTail(results);
-	        }
-	    }
-
-	    DO_THIS:
-	    do {
-
-	    boolean emptyMatchFound = false;
-	    REMatch doables = findDoables(token, input, cur1);
-	    if (doables == null) break DO_THIS;
-	    if (doables.empty) emptyMatchFound = true;
-
-	    if (!emptyMatchFound) {
-	        REMatch.REMatchList list = new REMatch.REMatchList();
-	        for (REMatch m = doables; m != null; m = m.next) {
-	            REMatch m1 = (REMatch) m.clone();
-		    int n = m1.index;
-		    if (! visitedContains(n, visited)) {
-		        visited = addVisited(n, visited);
-		        list.addTail(m1);
-		    }
-	        }
-	        if (list.head == null) break DO_THIS;
-	        doables = list.head;
-	    }
-
-	    for (REMatch m = doables; m != null; m = m.next) {
-	        if (! emptyMatchFound) {
-	            REMatch m1 = _match(input, m, max1,
-		        stopMatchingIfSatisfied, visited);
-		    if (possessive) return m1;
-		    if (m1 != null) {
-	                if (stopMatchingIfSatisfied) {
-		            return m1;
-		        }
-		        allResults.addTail(m1);
-		    }
-	        }
-		else {
-		    REMatch m1 = matchRest(input, m);
-		    if (m1 != null) {
-		        if (stopMatchingIfSatisfied) {
-		            return m1;
-		        }
-		        allResults.addTail(m1);
-		    }
-		}
-	    }
-
-	    } while (false); // DO_THIS only once;
-
-	    // This point itself is a candidate.
-	    if (!stingy) {
-		REMatch m2 = matchRest(input, cur1);
-		if (m2 != null) {
-		    if (stopMatchingIfSatisfied) {
-		        return m2;
-		    }
-		    allResults.addTail(m2);
-	        }
-	    }
+    private REMatch matchRest(CharIndexed input, final REMatch newMatch) {
+	if (next(input, newMatch)) {
+	    return newMatch;
 	}
-
-        return allResults.head;
+	return null;
     }
 
-    private REMatch matchMinimum(CharIndexed input, final REMatch mymatch) {
-	// Possible positions for the next repeat to match at
-	REMatch newMatch = mymatch;
-
-	// number of times we've matched so far
-	int numRepeats = 0; 
-	
-	while (numRepeats < min) {
-	    REMatch doables = findDoables(token, input, newMatch);
-
-	    // if none of the possibilities worked out, 
-	    // it means that minimum number of repeats could not be found.
-	    if (doables == null) return null;
-	    
-	    // reassign where the next repeat can match
-	    newMatch = doables;
-	    
-	    // increment how many repeats we've successfully found
-	    ++numRepeats;
-	    
-	    if (newMatch.empty) break;
-	}
-	return newMatch;
+    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 matchRest(CharIndexed input, final REMatch newMatch) {
-	REMatch current, single;
-	REMatch.REMatchList doneIndex = new REMatch.REMatchList();
-	// 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
-		doneIndex.addTail(single);
+    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;
 	}
-	return doneIndex.head;
-    }
+    }		    
 
     void dump(StringBuffer os) {
 	os.append("(?:");