src/com/stevesoft/pat/RegOpt.java

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