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