libjava/classpath/gnu/java/util/regex/RETokenRepeated.java

   1 /* gnu/regexp/RETokenRepeated.java
   2    Copyright (C) 2006 Free Software Foundation, Inc.
   3
   4 This file is part of GNU Classpath.
   5
   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)
   9 any later version.
  10
  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.
  15
  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
  19 02110-1301 USA.
  20
  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
  24 combination.
  25
  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. */
  37
  38
  39 package gnu.java.util.regex;
  40
  41 // import java.util.Vector;
  42 // import java.util.Stack;
  43
  44 final class RETokenRepeated extends REToken {
  45     private REToken token;
  46     private int min,max;
  47     private boolean stingy;
  48     private boolean possessive;
  49     private int tokenFixedLength;
  50
  51     RETokenRepeated(int subIndex, REToken token, int min, int max) {
  52         super(subIndex);
  53         this.token = token;
  54         this.min = min;
  55         this.max = max;
  56         if (token.returnsFixedLengthMatches()) {
  57             tokenFixedLength = token.getMaximumLength();
  58         }
  59         else {
  60             tokenFixedLength = -1;
  61         }
  62     }
  63
  64     /** Sets the minimal matching mode to true. */
  65     void makeStingy() {
  66         stingy = true;
  67     }
  68
  69     /** Queries if this token has minimal matching enabled. */
  70     boolean isStingy() {
  71         return stingy;
  72     }
  73
  74     /** Sets possessive matching mode to true. */
  75     void makePossessive() {
  76         possessive = true;
  77     }
  78
  79     /** Queries if this token has possessive matching enabled. */
  80     boolean isPossessive() {
  81         return possessive;
  82     }
  83
  84     /**
  85      * The minimum length of a repeated token is the minimum length
  86      * of the token multiplied by the minimum number of times it must
  87      * match.
  88      */
  89     int getMinimumLength() {
  90         return (min * token.getMinimumLength());
  91     }
  92
  93     int getMaximumLength() {
  94         if (max == Integer.MAX_VALUE) return Integer.MAX_VALUE;
  95         int tmax = token.getMaximumLength();
  96         if (tmax == Integer.MAX_VALUE) return tmax;
  97         return (max * tmax);
  98     }
  99
 100     // The comment "MUST make a clone" below means that some tests
 101     // failed without doing clone(),
 102
 103     private static class DoablesFinder {
 104         private REToken tk;
 105         private CharIndexed input;
 106         private REMatch rematch;
 107         private boolean findFirst;
 108
 109         private DoablesFinder(REToken tk, CharIndexed input, REMatch mymatch) {
 110             this.tk = tk;
 111             this.input = input;
 112             this.rematch = (REMatch) mymatch.clone(); // MUST make a clone
 113             this.rematch.backtrackStack = new BacktrackStack();
 114             findFirst = true;
 115         }
 116
 117         private REMatch find() {
 118             int origin = rematch.index;
 119             REMatch rem;
 120             if (findFirst) {
 121                 rem = tk.findMatch(input, rematch);
 122                 findFirst = false;
 123             }
 124             else {
 125                 while (true) {
 126                     if (rematch.backtrackStack.empty()) {
 127                         rem = null;
 128                         break;
 129                     }
 130                     BacktrackStack.Backtrack bt = rematch.backtrackStack.pop();
 131                     rem = bt.token.backtrack(bt.input, bt.match, bt.param);
 132                     if (rem != null) break;
 133                 }
 134             }
 135             if (rem == null) return null;
 136             if (rem.index == origin) rem.empty = true;
 137             rematch = rem;
 138             return (REMatch) rem.clone(); // MUST make a clone.
 139         }
 140
 141         boolean noMore() {
 142             return rematch.backtrackStack.empty();
 143         }
 144     }
 145
 146     REMatch findMatch(CharIndexed input, REMatch mymatch) {
 147         if (tokenFixedLength >= 0) return findMatchFixedLength(input, mymatch);
 148         BacktrackStack stack = new BacktrackStack();
 149         stack.push(new StackedInfo(input, 0, mymatch, null, null));
 150         return findMatch(stack);
 151     }
 152
 153     REMatch backtrack(CharIndexed input, REMatch mymatch, Object param) {
 154         if (tokenFixedLength >= 0) return backtrackFixedLength(input, mymatch, param);
 155         return findMatch((BacktrackStack)param);
 156     }
 157
 158     private static class StackedInfo extends BacktrackStack.Backtrack {
 159         int numRepeats;
 160         int[] visited;
 161         DoablesFinder finder;
 162         StackedInfo(CharIndexed input, int numRepeats, REMatch match,
 163                 int[] visited, DoablesFinder finder) {
 164             super(null, input, match, null);
 165             this.numRepeats = numRepeats;
 166             this.visited = visited;
 167             this.finder = finder;
 168         }
 169     }
 170
 171     private REMatch findMatch(BacktrackStack stack) {
 172         // Avoid using recursive calls.
 173         MAIN_LOOP:
 174         while (true) {
 175
 176         if (stack.empty()) return null;
 177         StackedInfo si = (StackedInfo)(stack.peek());
 178         CharIndexed input = si.input;
 179         int numRepeats = si.numRepeats;
 180         REMatch mymatch = si.match;
 181         int[] visited = si.visited;
 182         DoablesFinder finder = si.finder;
 183
 184         if (mymatch.backtrackStack == null)
 185           mymatch.backtrackStack = new BacktrackStack();
 186
 187         if (numRepeats >= max) {
 188             stack.pop();
 189             REMatch m1 = matchRest(input, mymatch);
 190             if (m1 != null) {
 191                 if (! stack.empty()) {
 192                     m1.backtrackStack.push(new BacktrackStack.Backtrack(
 193                         this, input, mymatch, stack));
 194                 }
 195                 return m1;
 196             }
 197             if (stingy) {
 198                 continue MAIN_LOOP;
 199             }
 200             return null;
 201         }
 202
 203         if (finder == null) {
 204             finder = new DoablesFinder(token, input, mymatch);
 205             si.finder = finder;
 206         }
 207
 208         if (numRepeats < min) {
 209             while (true) {
 210                 REMatch doable = finder.find();
 211                 if (doable == null) {
 212                     if (stack.empty()) return null;
 213                     stack.pop();
 214                     continue MAIN_LOOP;
 215                 }
 216                 if (finder.noMore()) stack.pop();
 217                 int newNumRepeats = (doable.empty ? min : numRepeats + 1);
 218                 stack.push(new StackedInfo(
 219                     input, newNumRepeats, doable, visited, null));
 220                 continue MAIN_LOOP;
 221             }
 222         }
 223
 224         if (visited == null) visited = initVisited();
 225
 226         if (stingy) {
 227             REMatch nextMatch = finder.find();
 228             if (nextMatch != null && !nextMatch.empty) {
 229                 stack.push(new StackedInfo(
 230                     input, numRepeats + 1, nextMatch, visited, null));
 231             }
 232             else {
 233                 stack.pop();
 234             }
 235             REMatch m1 = matchRest(input, mymatch);
 236             if (m1 != null) {
 237                 if (!stack.empty()) {
 238                     m1.backtrackStack.push(new BacktrackStack.Backtrack(
 239                         this, input, mymatch, stack));
 240                 }
 241                 return m1;
 242             }
 243             else {
 244                 continue MAIN_LOOP;
 245             }
 246         }
 247
 248         visited = addVisited(mymatch.index, visited);
 249
 250         DO_THIS:
 251         do {
 252
 253             boolean emptyMatchFound = false;
 254
 255             DO_ONE_DOABLE:
 256             while (true) {
 257
 258             REMatch doable = finder.find();
 259             if (doable == null) {
 260                 break DO_THIS;
 261             }
 262             if (doable.empty) emptyMatchFound = true;
 263
 264             if (!emptyMatchFound) {
 265                 int n = doable.index;
 266                 if (! visitedContains(n, visited)) {
 267                     visited = addVisited(n, visited);
 268                 }
 269                 else {
 270                     continue DO_ONE_DOABLE;
 271                 }
 272                 stack.push(new StackedInfo(
 273                     input, numRepeats + 1, doable, visited, null));
 274                 REMatch m1 = findMatch(stack);
 275                 if (possessive) {
 276                     return m1;
 277                 }
 278                 if (m1 != null) {
 279                     m1.backtrackStack.push(new BacktrackStack.Backtrack(
 280                         this, input, mymatch, stack));
 281                     return m1;
 282                 }
 283             }
 284             else {
 285                 REMatch m1 = matchRest(input, doable);
 286                 if (possessive) {
 287                     return m1;
 288                 }
 289                 if (m1 != null) {
 290                     if (! stack.empty()) {
 291                         m1.backtrackStack.push(new BacktrackStack.Backtrack(
 292                             this, input, mymatch, stack));
 293                     }
 294                     return m1;
 295                 }
 296             }
 297
 298             } // DO_ONE_DOABLE
 299
 300         } while (false); // DO_THIS only once;
 301
 302         if (!stack.empty()) {
 303             stack.pop();
 304         }
 305         if (possessive) {
 306             stack.clear();
 307         }
 308         REMatch m1 = matchRest(input, mymatch);
 309         if (m1 != null) {
 310             if (! stack.empty()) {
 311                 m1.backtrackStack.push(new BacktrackStack.Backtrack(
 312                     this, input, mymatch, stack));
 313             }
 314             return m1;
 315         }
 316
 317         } // MAIN_LOOP
 318     }
 319
 320     boolean match(CharIndexed input, REMatch mymatch) {
 321         REMatch m1 = findMatch(input, mymatch);
 322         if (m1 != null) {
 323             mymatch.assignFrom(m1);
 324             return true;
 325         }
 326         return false;
 327     }
 328
 329     // Array visited is an array of character positions we have already
 330     // visited. visited[0] is used to store the effective length of the
 331     // array.
 332     private static int[] initVisited() {
 333         int[] visited = new int[32];
 334         visited[0] = 0;
 335         return visited;
 336     }
 337
 338     private static boolean visitedContains(int n, int[] visited) {
 339         // Experience tells that for a small array like this,
 340         // simple linear search is faster than binary search.
 341         for (int i = 1; i < visited[0]; i++) {
 342             if (n == visited[i]) return true;
 343         }
 344         return false;
 345     }
 346
 347     private static int[] addVisited(int n, int[] visited) {
 348         if (visitedContains(n, visited)) return visited;
 349         if (visited[0] >= visited.length - 1) {
 350             int[] newvisited = new int[visited.length + 32];
 351             System.arraycopy(visited, 0, newvisited, 0, visited.length);
 352             visited = newvisited;
 353         }
 354         visited[0]++;
 355         visited[visited[0]] = n;
 356         return visited;
 357     }
 358
 359     private REMatch matchRest(CharIndexed input, final REMatch newMatch) {
 360         if (next(input, newMatch)) {
 361             return newMatch;
 362         }
 363         return null;
 364     }
 365
 366     private REMatch findMatchFixedLength(CharIndexed input, REMatch mymatch) {
 367         if (mymatch.backtrackStack == null)
 368           mymatch.backtrackStack = new BacktrackStack();
 369         int numRepeats = token.findFixedLengthMatches(input, (REMatch)mymatch.clone(), max);
 370         if (numRepeats == Integer.MAX_VALUE) numRepeats = min;
 371         int count = numRepeats - min + 1;
 372         if (count <= 0) return null;
 373         int index = 0;
 374         if (!stingy) index = mymatch.index + (tokenFixedLength * numRepeats);
 375         else index = mymatch.index + (tokenFixedLength * min);
 376         return findMatchFixedLength(input, mymatch, index, count);
 377     }
 378
 379     private REMatch backtrackFixedLength(CharIndexed input, REMatch mymatch,
 380             Object param) {
 381         int[] params = (int[])param;
 382         int index = params[0];
 383         int count = params[1];
 384         return findMatchFixedLength(input, mymatch, index, count);
 385     }
 386
 387     private REMatch findMatchFixedLength(CharIndexed input, REMatch mymatch,
 388                     int index, int count) {
 389         REMatch tryMatch = (REMatch) mymatch.clone();
 390         while (true) {
 391             tryMatch.index = index;
 392             REMatch m = matchRest(input, tryMatch);
 393             count--;
 394             if (stingy) index += tokenFixedLength;
 395             else index -= tokenFixedLength;
 396             if (possessive) return m;
 397             if (m != null) {
 398                 if (count > 0) {
 399                     m.backtrackStack.push(new BacktrackStack.Backtrack(
 400                         this, input, mymatch,
 401                         new int[] {index, count}));
 402                 }
 403                 return m;
 404             }
 405             if (count <= 0) return null;
 406         }
 407     }
 408
 409     void dump(StringBuffer os) {
 410         os.append("(?:");
 411         token.dumpAll(os);
 412         os.append(')');
 413         if ((max == Integer.MAX_VALUE) && (min <= 1))
 414             os.append( (min == 0) ? '*' : '+' );
 415         else if ((min == 0) && (max == 1))
 416             os.append('?');
 417         else {
 418             os.append('{').append(min);
 419             if (max > min) {
 420                 os.append(',');
 421                 if (max != Integer.MAX_VALUE) os.append(max);
 422             }
 423             os.append('}');
 424         }
 425         if (stingy) os.append('?');
 426     }
 427 }