1 /* gnu/regexp/RETokenRepeated.java
2 Copyright (C) 2006 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. */
39 package gnu
.java
.util
.regex
;
41 import gnu
.java
.lang
.CPStringBuilder
;
43 import java
.util
.ArrayDeque
;
44 import java
.util
.Deque
;
46 final class RETokenRepeated
extends REToken
48 private REToken token
;
50 private boolean stingy
;
51 private boolean possessive
;
52 private int tokenFixedLength
;
54 RETokenRepeated (int subIndex
, REToken token
, int min
, int max
)
60 if (token
.returnsFixedLengthMatches ())
62 tokenFixedLength
= token
.getMaximumLength ();
66 tokenFixedLength
= -1;
70 /** Sets the minimal matching mode to true. */
76 /** Queries if this token has minimal matching enabled. */
82 /** Sets possessive matching mode to true. */
83 void makePossessive ()
88 /** Queries if this token has possessive matching enabled. */
89 boolean isPossessive ()
95 * The minimum length of a repeated token is the minimum length
96 * of the token multiplied by the minimum number of times it must
99 int getMinimumLength ()
101 return (min
* token
.getMinimumLength ());
104 int getMaximumLength ()
106 if (max
== Integer
.MAX_VALUE
)
107 return Integer
.MAX_VALUE
;
108 int tmax
= token
.getMaximumLength ();
109 if (tmax
== Integer
.MAX_VALUE
)
114 // The comment "MUST make a clone" below means that some tests
115 // failed without doing clone(),
117 private static class DoablesFinder
120 private CharIndexed input
;
121 private REMatch rematch
;
122 private boolean findFirst
;
124 private DoablesFinder (REToken tk
, CharIndexed input
, REMatch mymatch
)
128 this.rematch
= (REMatch
) mymatch
.clone (); // MUST make a clone
129 this.rematch
.backtrackStack
= new BacktrackStack ();
133 private REMatch
find ()
135 int origin
= rematch
.index
;
139 rem
= tk
.findMatch (input
, rematch
);
146 if (rematch
.backtrackStack
.empty ())
151 BacktrackStack
.Backtrack bt
= rematch
.backtrackStack
.pop ();
152 rem
= bt
.token
.backtrack (bt
.input
, bt
.match
, bt
.param
);
159 if (rem
.index
== origin
)
162 return (REMatch
) rem
.clone (); // MUST make a clone.
167 return rematch
.backtrackStack
.empty ();
171 REMatch
findMatch (CharIndexed input
, REMatch mymatch
)
173 if (tokenFixedLength
>= 0)
174 return findMatchFixedLength (input
, mymatch
);
175 BacktrackStack stack
= new BacktrackStack ();
176 stack
.push (new StackedInfo (input
, 0, mymatch
, null, null));
177 return findMatch (stack
);
180 REMatch
backtrack (CharIndexed input
, REMatch mymatch
, Object param
)
182 if (tokenFixedLength
>= 0)
183 return backtrackFixedLength (input
, mymatch
, param
);
184 return findMatch ((BacktrackStack
) param
);
187 private static class StackedInfo
extends BacktrackStack
.Backtrack
191 DoablesFinder finder
;
192 StackedInfo (CharIndexed input
, int numRepeats
, REMatch match
,
193 int[]visited
, DoablesFinder finder
)
195 super (null, input
, match
, null);
196 this.numRepeats
= numRepeats
;
197 this.visited
= visited
;
198 this.finder
= finder
;
202 private static class FindMatchControl
204 DoablesFinder finder
;
205 FindMatchControl (DoablesFinder finder
)
207 this.finder
= finder
;
211 private REMatch
findMatch (BacktrackStack stack
)
213 return findMatch (stack
, new ArrayDeque
< FindMatchControl
> ());
216 private REMatch
findMatch (BacktrackStack stack
,
217 Deque
< FindMatchControl
> controlStack
)
219 REMatch result
= null;
220 StackedInfo si
= null;
221 CharIndexed input
= null;
223 REMatch mymatch
= null;
224 int[] visited
= null;
225 DoablesFinder finder
= null;
227 // Avoid using recursive calls because a match can be very long.
229 // This is the first entry point of this method.
230 // If you want to call this method recursively and you need the
231 // result returned, save necessary information in a FindMatchControl
232 // object and push it to controlStack, then continue from this point.
233 // You can check the result after exiting MAIN_LOOP.
238 // This is the second entry point of this method.
239 // If you want to call this method recursively but you do not need the
240 // result returned, just continue from this point.
247 si
= (StackedInfo
) (stack
.peek ());
249 numRepeats
= si
.numRepeats
;
251 visited
= si
.visited
;
254 if (mymatch
.backtrackStack
== null)
255 mymatch
.backtrackStack
= new BacktrackStack ();
257 if (numRepeats
>= max
)
260 REMatch m1
= matchRest (input
, mymatch
);
265 m1
.backtrackStack
.push (new BacktrackStack
.
266 Backtrack (this, input
,
281 finder
= new DoablesFinder (token
, input
, mymatch
);
285 if (numRepeats
< min
)
289 REMatch doable
= finder
.find ();
297 if (finder
.noMore ())
299 int newNumRepeats
= (doable
.empty ? min
: numRepeats
+ 1);
302 StackedInfo (input
, newNumRepeats
, doable
,
309 visited
= initVisited ();
313 REMatch nextMatch
= finder
.find ();
314 if (nextMatch
!= null && !nextMatch
.empty
)
318 StackedInfo (input
, numRepeats
+ 1, nextMatch
,
325 REMatch m1
= matchRest (input
, mymatch
);
330 m1
.backtrackStack
.push (new BacktrackStack
.
331 Backtrack (this, input
,
343 visited
= addVisited (mymatch
.index
, visited
);
345 TryAnotherResult taresult
=
346 tryAnother (stack
, input
, mymatch
, numRepeats
, finder
, visited
);
347 visited
= taresult
.visited
;
348 switch (taresult
.status
)
350 case TryAnotherResult
.TRY_FURTHER
:
351 controlStack
.push (new FindMatchControl (finder
));
353 case TryAnotherResult
.RESULT_FOUND
:
354 result
= taresult
.result
;
366 REMatch m1
= matchRest (input
, mymatch
);
371 m1
.backtrackStack
.push (new BacktrackStack
.
372 Backtrack (this, input
, mymatch
,
381 if (controlStack
.isEmpty ())
383 FindMatchControl control
= controlStack
.pop ();
390 result
.backtrackStack
.push (new BacktrackStack
.
391 Backtrack (this, input
, mymatch
,
396 finder
= control
.finder
;
398 TryAnotherResult taresult
=
399 tryAnother (stack
, input
, mymatch
, numRepeats
, finder
, visited
);
400 visited
= taresult
.visited
;
401 switch (taresult
.status
)
403 case TryAnotherResult
.TRY_FURTHER
:
404 controlStack
.push (new FindMatchControl (finder
));
406 case TryAnotherResult
.RESULT_FOUND
:
407 return taresult
.result
;
414 private static class TryAnotherResult
418 static final int RESULT_FOUND
= 1;
419 static final int TRY_FURTHER
= 2;
420 static final int NOTHING_FOUND
= 3;
424 private TryAnotherResult
tryAnother (BacktrackStack stack
,
425 CharIndexed input
, REMatch mymatch
,
426 int numRepeats
, DoablesFinder finder
,
430 TryAnotherResult taresult
= new TryAnotherResult ();
431 taresult
.visited
= visited
;
436 boolean emptyMatchFound
= false;
442 REMatch doable
= finder
.find ();
448 emptyMatchFound
= true;
450 if (!emptyMatchFound
)
452 int n
= doable
.index
;
453 if (visitedContains (n
, visited
))
455 continue DO_ONE_DOABLE
;
457 visited
= addVisited (n
, visited
);
460 StackedInfo (input
, numRepeats
+ 1, doable
, visited
,
462 taresult
.visited
= visited
;
463 taresult
.status
= TryAnotherResult
.TRY_FURTHER
;
468 REMatch m1
= matchRest (input
, doable
);
471 taresult
.result
= m1
;
472 taresult
.status
= TryAnotherResult
.RESULT_FOUND
;
479 m1
.backtrackStack
.push (new BacktrackStack
.
480 Backtrack (this, input
, mymatch
,
483 taresult
.result
= m1
;
484 taresult
.status
= TryAnotherResult
.RESULT_FOUND
;
493 taresult
.status
= TryAnotherResult
.NOTHING_FOUND
;
498 boolean match (CharIndexed input
, REMatch mymatch
)
500 setHitEnd (input
, mymatch
);
501 REMatch m1
= findMatch (input
, mymatch
);
504 mymatch
.assignFrom (m1
);
510 // Array visited is an array of character positions we have already
511 // visited. visited[0] is used to store the effective length of the
513 private static int[] initVisited ()
515 int[] visited
= new int[32];
520 private static boolean visitedContains (int n
, int[]visited
)
522 // Experience tells that for a small array like this,
523 // simple linear search is faster than binary search.
524 for (int i
= 1; i
< visited
[0]; i
++)
532 private static int[] addVisited (int n
, int[]visited
)
534 if (visitedContains (n
, visited
))
536 if (visited
[0] >= visited
.length
- 1)
538 int[] newvisited
= new int[visited
.length
+ 32];
539 System
.arraycopy (visited
, 0, newvisited
, 0, visited
.length
);
540 visited
= newvisited
;
543 visited
[visited
[0]] = n
;
547 private REMatch
matchRest (CharIndexed input
, final REMatch newMatch
)
549 if (next (input
, newMatch
))
556 private REMatch
findMatchFixedLength (CharIndexed input
, REMatch mymatch
)
558 if (mymatch
.backtrackStack
== null)
559 mymatch
.backtrackStack
= new BacktrackStack ();
561 token
.findFixedLengthMatches (input
, (REMatch
) mymatch
.clone (), max
);
562 if (numRepeats
== Integer
.MAX_VALUE
)
564 int count
= numRepeats
- min
+ 1;
569 index
= mymatch
.index
+ (tokenFixedLength
* numRepeats
);
571 index
= mymatch
.index
+ (tokenFixedLength
* min
);
572 return findMatchFixedLength (input
, mymatch
, index
, count
);
575 private REMatch
backtrackFixedLength (CharIndexed input
, REMatch mymatch
,
578 int[] params
= (int[]) param
;
579 int index
= params
[0];
580 int count
= params
[1];
581 return findMatchFixedLength (input
, mymatch
, index
, count
);
584 private REMatch
findMatchFixedLength (CharIndexed input
, REMatch mymatch
,
585 int index
, int count
)
587 REMatch tryMatch
= (REMatch
) mymatch
.clone ();
590 tryMatch
.index
= index
;
591 REMatch m
= matchRest (input
, tryMatch
);
594 index
+= tokenFixedLength
;
596 index
-= tokenFixedLength
;
603 m
.backtrackStack
.push (new BacktrackStack
.
604 Backtrack (this, input
, mymatch
,
616 void dump (CPStringBuilder os
)
621 if ((max
== Integer
.MAX_VALUE
) && (min
<= 1))
622 os
.append ((min
== 0) ?
'*' : '+');
623 else if ((min
== 0) && (max
== 1))
627 os
.append ('{').append (min
);
631 if (max
!= Integer
.MAX_VALUE
)