src/com/stevesoft/pat/RegOpt.java

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