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

   1 /* gnu/regexp/RETokenOneOf.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 package gnu.java.util.regex;
  39
  40 import gnu.java.lang.CPStringBuilder;
  41
  42 import java.util.ArrayDeque;
  43 import java.util.ArrayList;
  44 import java.util.Deque;
  45 import java.util.List;
  46
  47 final class RETokenOneOf extends REToken
  48 {
  49   private final List < REToken > options;
  50   private boolean negative;
  51   // True if this RETokenOneOf is supposed to match only one character,
  52   // which is typically the case of a character class expression.
  53   private boolean matchesOneChar;
  54
  55   private final List < Object > addition;
  56   // This ArrayList addition is used to store nested character classes.
  57   // For example, if the original expression is
  58   //    [2-7a-c[f-k][m-z]&&[^p-v][st]]
  59   // the basic part /2-7a-c/ is stored in the ArrayList options, and
  60   // the additional part /[f-k][m-z]&&[^p-v][st]/ is stored in the
  61   // ArrayList addition in the following order (Reverse Polish Notation):
  62   //           -- The matching result of the basic part is assumed here.
  63   //    [f-k]  -- REToken
  64   //    "|"    -- or
  65   //    [m-z]  -- REToken
  66   //    "|"    -- or
  67   //    false
  68   //    [^p-v] -- REToken
  69   //    "|"    -- or
  70   //    [st]   -- REToken
  71   //    "|"    -- or
  72   //    "&"    -- and
  73   //
  74   // As it is clear from the explanation above, the ArrayList addition is
  75   // effective only when this REToken originates from a character class
  76   // expression.
  77
  78   // This constructor is used for convenience when we know the set beforehand,
  79   // e.g. \d --> new RETokenOneOf("0123456789",false, ..)
  80   //      \D --> new RETokenOneOf("0123456789",true, ..)
  81
  82     RETokenOneOf (int subIndex, String optionsStr, boolean negative,
  83                   boolean insens)
  84   {
  85     super (subIndex);
  86     options = new ArrayList < REToken > ();
  87     this.negative = negative;
  88     for (int i = 0; i < optionsStr.length (); i++)
  89       options.add (new RETokenChar (subIndex, optionsStr.charAt (i), insens));
  90     matchesOneChar = true;
  91     addition = null;
  92   }
  93
  94   RETokenOneOf (int subIndex, List < REToken > options, boolean negative)
  95   {
  96     this (subIndex, options, null, negative);
  97   }
  98
  99   RETokenOneOf (int subIndex, List < REToken > options,
 100                 List < Object > addition, boolean negative)
 101   {
 102     super (subIndex);
 103     this.options = options;
 104     this.addition = addition;
 105     this.negative = negative;
 106     matchesOneChar = (negative || addition != null);
 107   }
 108
 109   int getMinimumLength ()
 110   {
 111     if (matchesOneChar)
 112       return 1;
 113     int min = Integer.MAX_VALUE;
 114     int x;
 115   for (REToken t:options)
 116       {
 117         if ((x = t.getMinimumLength ()) < min)
 118           min = x;
 119       }
 120     return min;
 121   }
 122
 123   int getMaximumLength ()
 124   {
 125     if (matchesOneChar)
 126       return 1;
 127     int max = 0;
 128     int x;
 129   for (REToken t:options)
 130       {
 131         if ((x = t.getMaximumLength ()) > max)
 132           max = x;
 133       }
 134     return max;
 135   }
 136
 137   boolean match (CharIndexed input, REMatch mymatch)
 138   {
 139     setHitEnd (input, mymatch);
 140     if (matchesOneChar)
 141       return matchOneChar (input, mymatch);
 142     else
 143       return matchOneRE (input, mymatch);
 144   }
 145
 146   boolean matchOneChar (CharIndexed input, REMatch mymatch)
 147   {
 148     REMatch tryMatch;
 149     boolean tryOnly;
 150     if (addition == null)
 151       {
 152         tryMatch = mymatch;
 153         tryOnly = false;
 154       }
 155     else
 156       {
 157         tryMatch = (REMatch) mymatch.clone ();
 158         tryOnly = true;
 159       }
 160     boolean b = negative ?
 161       matchN (input, tryMatch, tryOnly) : matchP (input, tryMatch, tryOnly);
 162     if (addition == null)
 163       return b;
 164
 165     final Deque < Boolean > stack = new ArrayDeque < Boolean > ();
 166     stack.push (new Boolean (b));
 167   for (Object obj:addition)
 168       {
 169         if (obj instanceof REToken)
 170           {
 171             b = ((REToken) obj).match (input, (REMatch) mymatch.clone ());
 172             stack.push (new Boolean (b));
 173           }
 174         else if (obj instanceof Boolean)
 175           {
 176             stack.push ((Boolean) obj);
 177           }
 178         else if (obj.equals ("|"))
 179           {
 180             b = stack.pop ();
 181             b = stack.pop () || b;
 182             stack.push (new Boolean (b));
 183           }
 184         else if (obj.equals ("&"))
 185           {
 186             b = stack.pop ();
 187             b = stack.pop () && b;
 188             stack.push (new Boolean (b));
 189           }
 190         else
 191           {
 192             throw new RuntimeException ("Invalid object found");
 193           }
 194       }
 195     if (stack.pop ())
 196       {
 197         ++mymatch.index;
 198         return next (input, mymatch);
 199       }
 200     return false;
 201   }
 202
 203   private boolean matchN (CharIndexed input, REMatch mymatch, boolean tryOnly)
 204   {
 205     if (input.charAt (mymatch.index) == CharIndexed.OUT_OF_BOUNDS)
 206       return false;
 207
 208   for (REToken tk:options)
 209       {
 210         REMatch tryMatch = (REMatch) mymatch.clone ();
 211         if (tk.match (input, tryMatch))
 212           {                     // match was successful
 213             return false;
 214           }                     // is a match
 215       }                         // try next option
 216
 217     if (tryOnly)
 218       return true;
 219     ++mymatch.index;
 220     return next (input, mymatch);
 221   }
 222
 223   private boolean matchP (CharIndexed input, REMatch mymatch, boolean tryOnly)
 224   {
 225   for (REToken tk:options)
 226       {
 227         REMatch tryMatch = (REMatch) mymatch.clone ();
 228         if (tk.match (input, tryMatch))
 229           {                     // match was successful
 230             if (tryOnly)
 231               return true;
 232             if (next (input, tryMatch))
 233               {
 234                 mymatch.assignFrom (tryMatch);
 235                 return true;
 236               }
 237           }
 238       }
 239     return false;
 240   }
 241
 242   private boolean matchOneRE (CharIndexed input, REMatch mymatch)
 243   {
 244     REMatch newMatch = findMatch (input, mymatch);
 245     if (newMatch != null)
 246       {
 247         mymatch.assignFrom (newMatch);
 248         return true;
 249       }
 250     return false;
 251   }
 252
 253   REMatch findMatch (CharIndexed input, REMatch mymatch)
 254   {
 255     if (matchesOneChar)
 256       return super.findMatch (input, mymatch);
 257     return findMatch (input, mymatch, 0);
 258   }
 259
 260   REMatch backtrack (CharIndexed input, REMatch mymatch, Object param)
 261   {
 262     return findMatch (input, mymatch, ((Integer) param).intValue ());
 263   }
 264
 265   private REMatch findMatch (CharIndexed input, REMatch mymatch,
 266                              int optionIndex)
 267   {
 268     for (int i = optionIndex; i < options.size (); i++)
 269       {
 270         REToken tk = options.get (i);
 271         tk = (REToken) tk.clone ();
 272         tk.chain (getNext ());
 273         REMatch tryMatch = (REMatch) mymatch.clone ();
 274         if (tryMatch.backtrackStack == null)
 275           {
 276             tryMatch.backtrackStack = new BacktrackStack ();
 277           }
 278         boolean stackPushed = false;
 279         if (i + 1 < options.size ())
 280           {
 281             tryMatch.backtrackStack.push (new BacktrackStack.
 282                                           Backtrack (this, input, mymatch,
 283                                                      i + 1));
 284             stackPushed = true;
 285           }
 286         if (tk.match (input, tryMatch))
 287           {
 288             return tryMatch;
 289           }
 290         if (stackPushed)
 291           tryMatch.backtrackStack.pop ();
 292       }
 293     return null;
 294   }
 295
 296   boolean returnsFixedLengthMatches ()
 297   {
 298     return matchesOneChar;
 299   }
 300
 301   int findFixedLengthMatches (CharIndexed input, REMatch mymatch, int max)
 302   {
 303     if (!matchesOneChar)
 304       return super.findFixedLengthMatches (input, mymatch, max);
 305     int numRepeats = 0;
 306     REMatch m = (REMatch) mymatch.clone ();
 307     REToken tk = (REToken) this.clone ();
 308     tk.chain (null);
 309     while (true)
 310       {
 311         if (numRepeats >= max)
 312           break;
 313         m = tk.findMatch (input, m);
 314         if (m == null)
 315           break;
 316         numRepeats++;
 317       }
 318     return numRepeats;
 319   }
 320
 321   void dump (CPStringBuilder os)
 322   {
 323     os.append (negative ? "[^" : "(?:");
 324     for (int i = 0; i < options.size (); i++)
 325       {
 326         if (!negative && (i > 0))
 327           os.append ('|');
 328         options.get (i).dumpAll (os);
 329       }
 330     os.append (negative ? ']' : ')');
 331   }
 332 }