src/gnu/regexp/RETokenRepeated.java

   1 /*
   2  *  gnu/regexp/RETokenRepeated.java
   3  *  Copyright (C) 1998-2001 Wes Biggs
   4  *
   5  *  This library is free software; you can redistribute it and/or modify
   6  *  it under the terms of the GNU Lesser General Public License as published
   7  *  by the Free Software Foundation; either version 2.1 of the License, or
   8  *  (at your option) any later version.
   9  *
  10  *  This library is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *  GNU Lesser General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU Lesser General Public License
  16  *  along with this program; if not, write to the Free Software
  17  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18  */
  19
  20 package gnu.regexp;
  21 import java.util.Vector;
  22
  23 final class RETokenRepeated extends REToken {
  24     private REToken token;
  25     private int min,max;
  26     private boolean stingy;
  27
  28     RETokenRepeated(int subIndex, REToken token, int min, int max) {
  29         super(subIndex);
  30         this.token = token;
  31         this.min = min;
  32         this.max = max;
  33     }
  34
  35     /** Sets the minimal matching mode to true. */
  36     void makeStingy() {
  37         stingy = true;
  38     }
  39
  40     /** Queries if this token has minimal matching enabled. */
  41     boolean isStingy() {
  42         return stingy;
  43     }
  44
  45     /**
  46      * The minimum length of a repeated token is the minimum length
  47      * of the token multiplied by the minimum number of times it must
  48      * match.
  49      */
  50     int getMinimumLength() {
  51         return (min * token.getMinimumLength());
  52     }
  53
  54     // We do need to save every possible point, but the number of clone()
  55     // invocations here is really a killer for performance on non-stingy
  56     // repeat operators.  I'm open to suggestions...
  57
  58     // Hypothetical question: can you have a RE that matches 1 times,
  59     // 3 times, 5 times, but not 2 times or 4 times?  Does having
  60     // the subexpression back-reference operator allow that?
  61
  62     boolean match(CharIndexed input, REMatch mymatch) {
  63         // number of times we've matched so far
  64         int numRepeats = 0;
  65
  66         // Possible positions for the next repeat to match at
  67         REMatch newMatch = mymatch;
  68         REMatch last = null;
  69         REMatch current;
  70
  71         // Add the '0-repeats' index
  72         // positions.elementAt(z) == position [] in input after <<z>> matches
  73         Vector positions = new Vector();
  74         positions.addElement(newMatch);
  75
  76         // Declare variables used in loop
  77         REMatch doables;
  78         REMatch doablesLast;
  79         REMatch recurrent;
  80
  81         do {
  82             // Check for stingy match for each possibility.
  83             if (stingy && (numRepeats >= min)) {
  84                 REMatch result = matchRest(input, newMatch);
  85                 if (result != null) {
  86                     mymatch.assignFrom(result);
  87                     return true;
  88                 }
  89             }
  90
  91             doables = null;
  92             doablesLast = null;
  93
  94             // try next repeat at all possible positions
  95             for (current = newMatch; current != null; current = current.next) {
  96                 recurrent = (REMatch) current.clone();
  97                 if (token.match(input, recurrent)) {
  98                     // add all items in current to doables array
  99                     if (doables == null) {
 100                         doables = recurrent;
 101                         doablesLast = recurrent;
 102                     } else {
 103                         // Order these from longest to shortest
 104                         // Start by assuming longest (more repeats)
 105                         doablesLast.next = recurrent;
 106                     }
 107                     // Find new doablesLast
 108                     while (doablesLast.next != null) {
 109                         doablesLast = doablesLast.next;
 110                     }
 111                 }
 112             }
 113             // if none of the possibilities worked out, break out of do/while
 114             if (doables == null) break;
 115
 116             // reassign where the next repeat can match
 117             newMatch = doables;
 118
 119             // increment how many repeats we've successfully found
 120             ++numRepeats;
 121
 122             positions.addElement(newMatch);
 123         } while (numRepeats < max);
 124
 125         // If there aren't enough repeats, then fail
 126         if (numRepeats < min) return false;
 127
 128         // We're greedy, but ease off until a true match is found
 129         int posIndex = positions.size();
 130
 131         // At this point we've either got too many or just the right amount.
 132         // See if this numRepeats works with the rest of the regexp.
 133         REMatch allResults = null;
 134         REMatch allResultsLast = null;
 135
 136         REMatch results = null;
 137         while (--posIndex >= min) {
 138             newMatch = (REMatch) positions.elementAt(posIndex);
 139             results = matchRest(input, newMatch);
 140             if (results != null) {
 141                 if (allResults == null) {
 142                     allResults = results;
 143                     allResultsLast = results;
 144                 } else {
 145                     // Order these from longest to shortest
 146                     // Start by assuming longest (more repeats)
 147                     allResultsLast.next = results;
 148                 }
 149                 // Find new doablesLast
 150                 while (allResultsLast.next != null) {
 151                     allResultsLast = allResultsLast.next;
 152                 }
 153             }
 154             // else did not match rest of the tokens, try again on smaller sample
 155         }
 156         if (allResults != null) {
 157             mymatch.assignFrom(allResults); // does this get all?
 158             return true;
 159         }
 160         // If we fall out, no matches.
 161         return false;
 162     }
 163
 164     private REMatch matchRest(CharIndexed input, final REMatch newMatch) {
 165         REMatch current, single;
 166         REMatch doneIndex = null;
 167         REMatch doneIndexLast = null;
 168         // Test all possible matches for this number of repeats
 169         for (current = newMatch; current != null; current = current.next) {
 170             // clone() separates a single match from the chain
 171             single = (REMatch) current.clone();
 172             if (next(input, single)) {
 173                 // chain results to doneIndex
 174                 if (doneIndex == null) {
 175                     doneIndex = single;
 176                     doneIndexLast = single;
 177                 } else {
 178                     doneIndexLast.next = single;
 179                 }
 180                 // Find new doneIndexLast
 181                 while (doneIndexLast.next != null) {
 182                     doneIndexLast = doneIndexLast.next;
 183                 }
 184             }
 185         }
 186         return doneIndex;
 187     }
 188
 189     void dump(StringBuffer os) {
 190         os.append("(?:");
 191         token.dumpAll(os);
 192         os.append(')');
 193         if ((max == Integer.MAX_VALUE) && (min <= 1))
 194             os.append( (min == 0) ? '*' : '+' );
 195         else if ((min == 0) && (max == 1))
 196             os.append('?');
 197         else {
 198             os.append('{').append(min);
 199             if (max > min) {
 200                 os.append(',');
 201                 if (max != Integer.MAX_VALUE) os.append(max);
 202             }
 203             os.append('}');
 204         }
 205         if (stingy) os.append('?');
 206     }
 207 }