src/com/stevesoft/pat/RegOpt.java

   1 //
   2 // This software is now distributed according to
   3 // the Lesser Gnu Public License.  Please see
   4 // http://www.gnu.org/copyleft/lesser.txt for
   5 // the details.
   6 //    -- Happy Computing!
   7 //
   8 package com.stevesoft.pat;
   9
  10 import java.util.*;
  11
  12 /** This class is just like oneChar, but doesn't worry about case. */
  13 class FastChar extends oneChar
  14 {
  15   FastChar(char c)
  16   {
  17     super(c);
  18   }
  19
  20   public int matchInternal(int p, Pthings pt)
  21   {
  22     return (p < pt.src.length() && pt.src.charAt(p) == c) ? nextMatch(
  23             p + 1, pt) : -1;
  24   }
  25
  26   Pattern clone1(Hashtable h)
  27   {
  28     return new FastChar(c);
  29   }
  30 }
  31
  32 /**
  33  * This class is a hashtable keyed by Character Objects. It is used to match
  34  * things of the form (?:a..|b..|c..|..) match with greater efficiency -- by
  35  * using a Hashtable that indexes into the group of patterns.
  36  */
  37 class Branch extends Pattern
  38 {
  39   Hashtable h = new Hashtable();
  40
  41   // We need to keep track of the order
  42   // of the keys -- if we don't then
  43   // recompiling the output of toString
  44   // may produce errors by re-ordering
  45   // ()'s and changing the id number of
  46   // the backreference associated with
  47   // a subpattern.
  48   Vector keys = new Vector();
  49
  50   Branch()
  51   {
  52   }
  53
  54   Pattern clone1(Hashtable x)
  55   {
  56     Branch b = new Branch();
  57     b.keys = (Vector) keys.clone();
  58     x.put(this, b);
  59     x.put(b, b);
  60
  61     for (int i = 0; i < keys.size(); i++)
  62     {
  63       Pattern p = (Pattern) h.get(keys.elementAt(i));
  64       b.h.put(keys.elementAt(i), p.clone(x));
  65     }
  66     return b;
  67   }
  68
  69   // this function eliminates Branches with 0 or 1 elements.
  70   final Pattern reduce(boolean ignoreCase, boolean dontMinQ)
  71   {
  72     if (h.size() == 1)
  73     {
  74       Enumeration e = h.keys();
  75       Character c = (Character) e.nextElement();
  76       Pattern oc;
  77       if (ignoreCase || dontMinQ)
  78       {
  79         oc = new oneChar(c.charValue());
  80       }
  81       else
  82       {
  83         oc = new FastChar(c.charValue());
  84       }
  85       oc.next = (Pattern) h.get(c);
  86       oc.add(next);
  87       return oc;
  88     }
  89     else if (h.size() == 0)
  90     {
  91       return null;
  92     }
  93     return this;
  94   }
  95
  96   public patInt maxChars()
  97   {
  98     Enumeration e = h.keys();
  99     patInt count = new patInt(0);
 100     while (e.hasMoreElements())
 101     {
 102       Object key = e.nextElement();
 103       Pattern pa = (Pattern) h.get(key);
 104       patInt pi = pa.maxChars();
 105       pi.inc();
 106       count.maxeq(pi);
 107     }
 108     return count;
 109   }
 110
 111   public patInt minChars()
 112   {
 113     Enumeration e = h.keys();
 114     patInt count = new patInt(0);
 115     while (e.hasMoreElements())
 116     {
 117       Object key = e.nextElement();
 118       Pattern pa = (Pattern) h.get(key);
 119       patInt pi = pa.minChars();
 120       pi.inc();
 121       count.mineq(pi);
 122     }
 123     return count;
 124   }
 125
 126   // adds a oneChar object to this Branch
 127   void addc(oneChar o, boolean ignoreCase, boolean dontMinQ)
 128   {
 129     Pattern n = o.next;
 130     if (n == null)
 131     {
 132       n = new NullPattern();
 133     }
 134     else
 135     {
 136       n = RegOpt.opt(n, ignoreCase, dontMinQ);
 137     }
 138     n.setParent(this);
 139     set(new Character(o.c), n, ignoreCase, dontMinQ);
 140     if (ignoreCase)
 141     {
 142       if (o.c != o.altc)
 143       {
 144         set(new Character(o.altc), n, ignoreCase, dontMinQ);
 145       }
 146       if (o.c != o.altc2 && o.altc != o.altc2)
 147       {
 148         set(new Character(o.altc2), n, ignoreCase, dontMinQ);
 149       }
 150     }
 151   }
 152
 153   void set(Character c, Pattern n, boolean igc, boolean dontMinQ)
 154   {
 155     Pattern p = (Pattern) h.get(c);
 156     next = null;
 157     // This letter is not yet used in the Branch object.
 158     // We need to add it.
 159     if (p == null)
 160     {
 161       if (n instanceof Or)
 162       {
 163         // A NullPattern is prepended to an Or
 164         // to prevent confusing this object.
 165         // For example: (boo|bug) => (b(?:oo|ug))
 166         // during this process. However, we
 167         // want (b(?:oo|ell)|bug)
 168         NullPattern np = new NullPattern();
 169         np.add(n);
 170         h.put(c, np);
 171       }
 172       else
 173       {
 174         h.put(c, n);
 175       }
 176       // Make sure we remember the order things were
 177       // added into the Branch object so that we can
 178       // properly convert it to a String.
 179       keys.addElement(c);
 180     }
 181     else if (p instanceof Or)
 182     {
 183       ((Or) p).addOr(n);
 184     }
 185     else if (p instanceof oneChar && n instanceof oneChar
 186             && ((oneChar) p).c != ((oneChar) n).c)
 187     {
 188       Branch b = new Branch();
 189       b.addc((oneChar) p, igc, dontMinQ);
 190       b.addc((oneChar) n, igc, dontMinQ);
 191       h.put(c, b);
 192       b.setParent(this);
 193     }
 194     else if (p instanceof Branch && n instanceof oneChar)
 195     {
 196       ((Branch) p).addc((oneChar) n, igc, dontMinQ);
 197       n.setParent(p);
 198     }
 199     else
 200     {
 201       // Create an Or object to receive the variety
 202       // of branches in the pattern if the current letter
 203       // is matched. We do not attempt to make these
 204       // sub-branches into a Branch object yet.
 205       Or o = new Or();
 206       o.setParent(this);
 207
 208       // Remove NullPattern from p -- it's no longer needed.
 209       if (p instanceof NullPattern && p.parent == null && p.next != null)
 210       {
 211         o.addOr(p.next);
 212       }
 213       else
 214       {
 215         o.addOr(p);
 216       }
 217       o.addOr(n);
 218
 219       Pattern optpat = RegOpt.opt(o, igc, dontMinQ);
 220       h.put(c, optpat);
 221       optpat.setParent(this);
 222     }
 223   }
 224
 225   public String toString()
 226   {
 227     StringBuffer sb = new StringBuffer();
 228     // should protect this...
 229     sb.append("(?:(?#branch)"); // Hashtable)");
 230     for (int i = 0; i < keys.size(); i++)
 231     {
 232       Character c = (Character) keys.elementAt(i);
 233       sb.append(c);
 234       sb.append(h.get(c));
 235       if (i + 1 < keys.size())
 236       {
 237         sb.append("|");
 238       }
 239     }
 240     sb.append(")");
 241     sb.append(nextString());
 242     return sb.toString();
 243   }
 244
 245   public int matchInternal(int pos, Pthings pt)
 246   {
 247     if (pos >= pt.src.length())
 248     {
 249       return -1;
 250     }
 251     Pattern n = (Pattern) h.get(new Character(pt.src.charAt(pos)));
 252     if (n == null)
 253     {
 254       return -1;
 255     }
 256     if (pt.cbits != null && pt.cbits.get(pos))
 257     {
 258       return -1;
 259     }
 260     return n.matchInternal(pos + 1, pt);
 261   }
 262 }
 263
 264 /**
 265  * This is just a place to put the optimizing function. It is never instantiated
 266  * as an Object. It just sorts through the RegOpt looking for things it can
 267  * change and make faster.
 268  */
 269 public class RegOpt
 270 {
 271   static Pattern opt(Pattern p, boolean ignoreCase, boolean dontMinQ)
 272   {
 273     if (p == null)
 274     {
 275       return p;
 276     }
 277     if (p instanceof Bracket)
 278     {
 279       Bracket b = (Bracket) p;
 280       // FastBracket is the only special
 281       // optimized class to have its own
 282       // source file.
 283       p = FastBracket.process(b, ignoreCase);
 284       // if(!(p instanceof FastBracket)
 285       // p = Switch.process(b,ignoreCase);
 286       p.next = b.next;
 287       p.parent = b.parent;
 288     }
 289     else if (p instanceof oneChar && !ignoreCase && !dontMinQ)
 290     {
 291       oneChar o = (oneChar) p;
 292       p = new FastChar(o.c);
 293       p.next = o.next;
 294       p.parent = o.parent;
 295     }
 296     else if (p instanceof Or && ((Or) p).leftForm().equals("(?:")
 297             && ((Or) p).v.size() == 1)
 298     { // Eliminate this Or Object.
 299       Or o = (Or) p;
 300       p = (Pattern) o.v.elementAt(0);
 301       p.setParent(null);
 302       p = RegOpt.opt(p, ignoreCase, dontMinQ);
 303       p.add(o.next);
 304     }
 305     else if (p instanceof Or)
 306     {
 307       Or o = (Or) p;
 308       o.pv = null;
 309       Vector v = o.v;
 310       o.v = new Vector();
 311       Branch b = new Branch();
 312       b.parent = o.parent;
 313       for (int i = 0; i < v.size(); i++)
 314       {
 315         Pattern pp = (Pattern) v.elementAt(i);
 316         // We want to have at least two oneChar's in
 317         // the Or Object to consider making a Branch.
 318         if (pp instanceof oneChar
 319                 && (b.h.size() >= 1 || (i + 1 < v.size() && v
 320                         .elementAt(i + 1) instanceof oneChar)))
 321         {
 322           b.addc((oneChar) pp, ignoreCase, dontMinQ);
 323         }
 324         else
 325         {
 326           if (b.keys.size() > 0)
 327           {
 328             Pattern p2 = (Pattern) b.reduce(ignoreCase, dontMinQ);
 329             if (p2 != null)
 330             {
 331               o.addOr(p2);
 332               b = new Branch();
 333               b.parent = o.parent;
 334             }
 335           }
 336           o.addOr(opt(pp, ignoreCase, dontMinQ));
 337         }
 338       }
 339       if (b.keys.size() > 0)
 340       {
 341         Pattern p2 = (Pattern) b.reduce(ignoreCase, dontMinQ);
 342         if (p2 != null)
 343         {
 344           o.addOr(p2);
 345         }
 346       }
 347       if (o.v.size() == 1 && o.leftForm().equals("(?:"))
 348       { // Eliminate Or Object
 349         p = (Pattern) o.v.elementAt(0);
 350         p.setParent(null);
 351         p = RegOpt.opt(p, ignoreCase, dontMinQ);
 352         p.add(o.next);
 353       }
 354     }
 355     else if (p instanceof FastMulti)
 356     {
 357       PatternSub ps = (PatternSub) p;
 358       ps.sub = RegOpt.opt(ps.sub, ignoreCase, dontMinQ);
 359     }
 360     else if (p instanceof Multi && safe4fm(((PatternSub) p).sub))
 361     {
 362       Multi m = (Multi) p;
 363       FastMulti fm = null;
 364       try
 365       {
 366         fm = new FastMulti(m.a, m.b, opt(m.sub, ignoreCase, dontMinQ));
 367       } catch (RegSyntax rs)
 368       {
 369       }
 370       fm.parent = m.parent;
 371       fm.matchFewest = m.matchFewest;
 372       fm.next = m.next;
 373       p = fm;
 374     }
 375     if (p.next != null)
 376     {
 377       p.next = opt(p.next, ignoreCase, dontMinQ);
 378     }
 379     return p;
 380   }
 381
 382   final static boolean safe4fm(Pattern x)
 383   {
 384     while (x != null)
 385     {
 386       if (x instanceof Bracket)
 387       {
 388         ;
 389       }
 390       else if (x instanceof Range)
 391       {
 392         ;
 393       }
 394       else if (x instanceof oneChar)
 395       {
 396         ;
 397       }
 398       else if (x instanceof Any)
 399       {
 400         ;
 401       }
 402       else if (x instanceof Custom
 403               && ((Custom) x).v instanceof UniValidator)
 404       {
 405         ;
 406       }
 407       else if (x instanceof Or)
 408       {
 409         Or o = (Or) x;
 410         if (!o.leftForm().equals("(?:"))
 411         {
 412           return false;
 413         }
 414         patInt lo = o.countMinChars();
 415         patInt hi = o.countMaxChars();
 416         if (!lo.equals(hi))
 417         {
 418           return false;
 419         }
 420         for (int i = 0; i < o.v.size(); i++)
 421         {
 422           if (!safe4fm((Pattern) o.v.elementAt(i)))
 423           {
 424             return false;
 425           }
 426         }
 427       }
 428       else
 429       {
 430         return false;
 431       }
 432       x = x.next;
 433     }
 434     return true;
 435   }
 436   /*
 437    * public static void setParents(Regex r) { setParents(r.thePattern,null); }
 438    * static void setParents(Pattern p,Pattern x) { if(p instanceof PatternSub &&
 439    * !(p instanceof FastMulti) && !(p instanceof DotMulti)) RegOpt.setParents(
 440    * ((PatternSub)p).sub, p); else if(p instanceof Or && !(p instanceof
 441    * Bracket)) { Or o = (Or)p; for(int i=0;i<o.v.size();i++)
 442    * RegOpt.setParents((Pattern)o.v.elementAt(i),o); } else if(p instanceof
 443    * Branch) { Branch b = (Branch)p; Enumeration e = b.h.keys();
 444    * while(e.hasMoreElements()) { Object o = e.nextElement(); RegOpt.setParents(
 445    * (Pattern)b.h.get(o), b); } } if(p.next == null) p.parent = x; else {
 446    * p.parent = null; RegOpt.setParents(p.next,x); } }
 447    */
 448 }