1 /* gnu/regexp/RETokenRepeated.java
2 Copyright (C) 1998-2001, 2004 Free Software Foundation, Inc.
4 This file is part of GNU Classpath.
6 GNU Classpath is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU Classpath is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU Classpath; see the file COPYING. If not, write to the
18 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21 Linking this library statically or dynamically with other modules is
22 making a combined work based on this library. Thus, the terms and
23 conditions of the GNU General Public License cover the whole
26 As a special exception, the copyright holders of this library give you
27 permission to link this library with independent modules to produce an
28 executable, regardless of the license terms of these independent
29 modules, and to copy and distribute the resulting executable under
30 terms of your choice, provided that you also meet, for each linked
31 independent module, the terms and conditions of the license of that
32 module. An independent module is a module which is not derived from
33 or based on this library. If you modify this library, you may extend
34 this exception to your version of the library, but you are not
35 obligated to do so. If you do not wish to do so, delete this
36 exception statement from your version. */
41 import java
.util
.Vector
;
43 final class RETokenRepeated
extends REToken
{
44 private REToken token
;
46 private boolean stingy
;
47 private boolean possessive
;
49 RETokenRepeated(int subIndex
, REToken token
, int min
, int max
) {
56 /** Sets the minimal matching mode to true. */
61 /** Queries if this token has minimal matching enabled. */
66 /** Sets possessive matching mode to true. */
67 void makePossessive() {
71 /** Queries if this token has possessive matching enabled. */
72 boolean isPossessive() {
77 * The minimum length of a repeated token is the minimum length
78 * of the token multiplied by the minimum number of times it must
81 int getMinimumLength() {
82 return (min
* token
.getMinimumLength());
85 // We do need to save every possible point, but the number of clone()
86 // invocations here is really a killer for performance on non-stingy
87 // repeat operators. I'm open to suggestions...
89 // Hypothetical question: can you have a RE that matches 1 times,
90 // 3 times, 5 times, but not 2 times or 4 times? Does having
91 // the subexpression back-reference operator allow that?
93 boolean match(CharIndexed input
, REMatch mymatch
) {
94 // number of times we've matched so far
97 // Possible positions for the next repeat to match at
98 REMatch newMatch
= mymatch
;
102 // Add the '0-repeats' index
103 // positions.elementAt(z) == position [] in input after <<z>> matches
104 Vector positions
= new Vector();
105 positions
.addElement(newMatch
);
107 // Declare variables used in loop
111 int lastIndex
= mymatch
.index
;
114 // Check for stingy match for each possibility.
115 if (stingy
&& (numRepeats
>= min
)) {
116 REMatch result
= matchRest(input
, newMatch
);
117 if (result
!= null) {
118 mymatch
.assignFrom(result
);
126 // try next repeat at all possible positions
127 for (current
= newMatch
; current
!= null; current
= current
.next
) {
128 recurrent
= (REMatch
) current
.clone();
129 if (token
.match(input
, recurrent
)) {
130 // add all items in current to doables array
131 if (doables
== null) {
133 doablesLast
= recurrent
;
135 // Order these from longest to shortest
136 // Start by assuming longest (more repeats)
137 doablesLast
.next
= recurrent
;
139 // Find new doablesLast
140 while (doablesLast
.next
!= null) {
141 doablesLast
= doablesLast
.next
;
145 // if none of the possibilities worked out, break out of do/while
146 if (doables
== null) break;
148 // reassign where the next repeat can match
151 // increment how many repeats we've successfully found
154 positions
.addElement(newMatch
);
156 // doables.index == lastIndex means an empty string
157 // was the longest that matched this token.
158 // We break here, otherwise we will fall into an endless loop.
159 if (doables
.index
== lastIndex
) {
160 if (numRepeats
< min
) numRepeats
= min
;
163 lastIndex
= doables
.index
;
164 } while (numRepeats
< max
);
166 // If there aren't enough repeats, then fail
167 if (numRepeats
< min
) return false;
169 // We're greedy, but ease off until a true match is found
170 int posIndex
= positions
.size();
172 // At this point we've either got too many or just the right amount.
173 // See if this numRepeats works with the rest of the regexp.
174 REMatch allResults
= null;
175 REMatch allResultsLast
= null;
177 REMatch results
= null;
178 int indexCount
= posIndex
- min
;
179 if (indexCount
<= 0) {
180 // This case occurs when we exited the previous do loop before
181 // numRepeats >= min because an empty string matched the token.
182 // In this case, an empty string can match as many times as
186 while (indexCount
-- > 0) {
188 newMatch
= (REMatch
) positions
.elementAt(posIndex
);
189 results
= matchRest(input
, newMatch
);
190 if (results
!= null) {
191 if (allResults
== null) {
192 allResults
= results
;
193 allResultsLast
= results
;
195 // Order these from longest to shortest
196 // Start by assuming longest (more repeats)
197 allResultsLast
.next
= results
;
199 // Find new doablesLast
200 while (allResultsLast
.next
!= null) {
201 allResultsLast
= allResultsLast
.next
;
204 // else did not match rest of the tokens, try again on smaller sample
205 // or break out when performing possessive matching
206 if (possessive
) break;
208 if (allResults
!= null) {
209 mymatch
.assignFrom(allResults
); // does this get all?
212 // If we fall out, no matches.
216 private REMatch
matchRest(CharIndexed input
, final REMatch newMatch
) {
217 REMatch current
, single
;
218 REMatch doneIndex
= null;
219 REMatch doneIndexLast
= null;
220 // Test all possible matches for this number of repeats
221 for (current
= newMatch
; current
!= null; current
= current
.next
) {
222 // clone() separates a single match from the chain
223 single
= (REMatch
) current
.clone();
224 if (next(input
, single
)) {
225 // chain results to doneIndex
226 if (doneIndex
== null) {
228 doneIndexLast
= single
;
230 doneIndexLast
.next
= single
;
232 // Find new doneIndexLast
233 while (doneIndexLast
.next
!= null) {
234 doneIndexLast
= doneIndexLast
.next
;
241 void dump(StringBuffer os
) {
245 if ((max
== Integer
.MAX_VALUE
) && (min
<= 1))
246 os
.append( (min
== 0) ?
'*' : '+' );
247 else if ((min
== 0) && (max
== 1))
250 os
.append('{').append(min
);
253 if (max
!= Integer
.MAX_VALUE
) os
.append(max
);
257 if (stingy
) os
.append('?');