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