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