src/com/stevesoft/pat/Regex.java

   1 //
   2 // This software is now distributed according to
   3 // the Lesser Gnu Public License.  Please see
   4 // http://www.gnu.org/copyleft/lesser.txt for
   5 // the details.
   6 //    -- Happy Computing!
   7 //
   8 package com.stevesoft.pat;
   9
  10 import jalview.util.MessageManager;
  11
  12 import java.io.File;
  13 import java.io.FilenameFilter;
  14 import java.util.BitSet;
  15 import java.util.Hashtable;
  16
  17 import com.stevesoft.pat.wrap.StringWrap;
  18
  19 /** Matches a Unicode punctuation character. */
  20 class UnicodePunct extends UniValidator
  21 {
  22   @Override
  23   public int validate(StringLike s, int from, int to)
  24   {
  25     return from < s.length() && Prop.isPunct(s.charAt(from)) ? to : -1;
  26   }
  27 }
  28
  29 /** Matches a Unicode white space character. */
  30 class UnicodeWhite extends UniValidator
  31 {
  32   @Override
  33   public int validate(StringLike s, int from, int to)
  34   {
  35     return from < s.length() && Prop.isWhite(s.charAt(from)) ? to : -1;
  36   }
  37 }
  38
  39 /**
  40  * Matches a character that is not a Unicode punctuation character.
  41  */
  42 class NUnicodePunct extends UniValidator
  43 {
  44   @Override
  45   public int validate(StringLike s, int from, int to)
  46   {
  47     return from < s.length() && !Prop.isPunct(s.charAt(from)) ? to : -1;
  48   }
  49 }
  50
  51 /**
  52  * Matches a character that is not a Unicode white space character.
  53  */
  54 class NUnicodeWhite extends UniValidator
  55 {
  56   @Override
  57   public int validate(StringLike s, int from, int to)
  58   {
  59     return from < s.length() && !Prop.isWhite(s.charAt(from)) ? to : -1;
  60   }
  61 }
  62
  63 /** Matches a Unicode word character: an alphanumeric or underscore. */
  64 class UnicodeW extends UniValidator
  65 {
  66   @Override
  67   public int validate(StringLike s, int from, int to)
  68   {
  69     if (from >= s.length())
  70     {
  71       return -1;
  72     }
  73     char c = s.charAt(from);
  74     return (Prop.isAlphabetic(c) || Prop.isDecimalDigit(c) || c == '_') ? to
  75             : -1;
  76   }
  77 }
  78
  79 /** Matches a character that is not a Unicode alphanumeric or underscore. */
  80 class NUnicodeW extends UniValidator
  81 {
  82   @Override
  83   public int validate(StringLike s, int from, int to)
  84   {
  85     if (from >= s.length())
  86     {
  87       return -1;
  88     }
  89     char c = s.charAt(from);
  90     return !(Prop.isAlphabetic(c) || Prop.isDecimalDigit(c) || c == '_')
  91             ? to
  92             : -1;
  93   }
  94 }
  95
  96 /** Matches a Unicode decimal digit. */
  97 class UnicodeDigit extends UniValidator
  98 {
  99   @Override
 100   public int validate(StringLike s, int from, int to)
 101   {
 102     return from < s.length() && Prop.isDecimalDigit(s.charAt(from)) ? to
 103             : -1;
 104   }
 105 }
 106
 107 /** Matches a character that is not a Unicode digit. */
 108 class NUnicodeDigit extends UniValidator
 109 {
 110   @Override
 111   public int validate(StringLike s, int from, int to)
 112   {
 113     return from < s.length() && !Prop.isDecimalDigit(s.charAt(from)) ? to
 114             : -1;
 115   }
 116 }
 117
 118 /** Matches a Unicode math character. */
 119 class UnicodeMath extends UniValidator
 120 {
 121   @Override
 122   public int validate(StringLike s, int from, int to)
 123   {
 124     return from < s.length() && Prop.isMath(s.charAt(from)) ? to : -1;
 125   }
 126 }
 127
 128 /** Matches a non-math Unicode character. */
 129 class NUnicodeMath extends UniValidator
 130 {
 131   @Override
 132   public int validate(StringLike s, int from, int to)
 133   {
 134     return from < s.length() && !Prop.isMath(s.charAt(from)) ? to : -1;
 135   }
 136 }
 137
 138 /** Matches a Unicode currency symbol. */
 139 class UnicodeCurrency extends UniValidator
 140 {
 141   @Override
 142   public int validate(StringLike s, int from, int to)
 143   {
 144     return from < s.length() && Prop.isCurrency(s.charAt(from)) ? to : -1;
 145   }
 146 }
 147
 148 /** Matches a non-currency symbol Unicode character. */
 149 class NUnicodeCurrency extends UniValidator
 150 {
 151   @Override
 152   public int validate(StringLike s, int from, int to)
 153   {
 154     return from < s.length() && !Prop.isCurrency(s.charAt(from)) ? to : -1;
 155   }
 156 }
 157
 158 /** Matches a Unicode alphabetic character. */
 159 class UnicodeAlpha extends UniValidator
 160 {
 161   @Override
 162   public int validate(StringLike s, int from, int to)
 163   {
 164     return from < s.length() && Prop.isAlphabetic(s.charAt(from)) ? to : -1;
 165   }
 166 }
 167
 168 /** Matches a non-alphabetic Unicode character. */
 169 class NUnicodeAlpha extends UniValidator
 170 {
 171   @Override
 172   public int validate(StringLike s, int from, int to)
 173   {
 174     return from < s.length() && !Prop.isAlphabetic(s.charAt(from)) ? to
 175             : -1;
 176   }
 177 }
 178
 179 /** Matches an upper case Unicode character. */
 180 class UnicodeUpper extends UniValidator
 181 {
 182   @Override
 183   public int validate(StringLike s, int from, int to)
 184   {
 185     return from < s.length() && isUpper(s.charAt(from)) ? to : -1;
 186   }
 187
 188   final boolean isUpper(char c)
 189   {
 190     return c == CaseMgr.toUpperCase(c) && c != CaseMgr.toLowerCase(c);
 191   }
 192 }
 193
 194 /** Matches an upper case Unicode character. */
 195 class UnicodeLower extends UniValidator
 196 {
 197   @Override
 198   public int validate(StringLike s, int from, int to)
 199   {
 200     return from < s.length() && isLower(s.charAt(from)) ? to : -1;
 201   }
 202
 203   final boolean isLower(char c)
 204   {
 205     return c != CaseMgr.toUpperCase(c) && c == CaseMgr.toLowerCase(c);
 206   }
 207 }
 208
 209 /**
 210  * Regex provides the parser which constructs the linked list of Pattern classes
 211  * from a String.
 212  * <p>
 213  * For the purpose of this documentation, the fact that java interprets the
 214  * backslash will be ignored. In practice, however, you will need a double
 215  * backslash to obtain a string that contains a single backslash character.
 216  * Thus, the example pattern "\b" should really be typed as "\\b" inside java
 217  * code.
 218  * <p>
 219  * Note that Regex is part of package "com.stevesoft.pat". To use it, simply
 220  * import com.stevesoft.pat.Regex at the top of your file.
 221  * <p>
 222  * Regex is made with a constructor that takes a String that defines the regular
 223  * expression. Thus, for example
 224  *
 225  * <pre>
 226  * Regex r = new Regex(&quot;[a-c]*&quot;);
 227  * </pre>
 228  *
 229  * matches any number of characters so long as the are 'a', 'b', or 'c').
 230  * <p>
 231  * To attempt to match the Pattern to a given string, you can use either the
 232  * search(String) member function, or the matchAt(String,int position) member
 233  * function. These functions return a boolean which tells you whether or not the
 234  * thing worked, and sets the methods "charsMatched()" and "matchedFrom()" in
 235  * the Regex object appropriately.
 236  * <p>
 237  * The portion of the string before the match can be obtained by the left()
 238  * member, and the portion after the match can be obtained by the right()
 239  * member.
 240  * <p>
 241  * Essentially, this package implements a syntax that is very much like the perl
 242  * 5 regular expression syntax.
 243  *
 244  * Longer example:
 245  *
 246  * <pre>
 247  * Regex r = new Regex(&quot;x(a|b)y&quot;);
 248  * r.matchAt(&quot;xay&quot;, 0);
 249  * System.out.println(&quot;sub = &quot; + r.stringMatched(1));
 250  * </pre>
 251  *
 252  * The above would print "sub = a".
 253  *
 254  * <pre>
 255  *  r.left() // would return &quot;x&quot;
 256  *  r.right() // would return &quot;y&quot;
 257  * </pre>
 258  *
 259  * <p>
 260  * Differences between this package and perl5:<br>
 261  * The extended Pattern for setting flags, is now supported, but the flags are
 262  * different. "(?i)" tells the pattern to ignore case, "(?Q)" sets the
 263  * "dontMatchInQuotes" flag, and "(?iQ)" sets them both. You can change the
 264  * escape character. The pattern
 265  *
 266  * <pre>
 267  * (?e=#)#d+
 268  * </pre>
 269  *
 270  * is the same as
 271  *
 272  * <pre>
 273  * \d+
 274  * </pre>
 275  *
 276  * , but note that the sequence
 277  *
 278  * <pre>
 279  * (?e=#)
 280  * </pre>
 281  *
 282  * <b>must</b> occur at the very beginning of the pattern. There may be other
 283  * small differences as well. I will either make my package conform or note them
 284  * as I become aware of them.
 285  * <p>
 286  * This package supports additional patterns not in perl5: <center> <table *
 287  * border=1>
 288  * <tr>
 289  * <td>(?@())</td>
 290  * <td>Group</td>
 291  * <td>This matches all characters between the '(' character and the balancing
 292  * ')' character. Thus, it will match "()" as well as "(())". The balancing
 293  * characters are arbitrary, thus (?@{}) matches on "{}" and "{{}}".</td>
 294  * <tr>
 295  * <td>(?&lt1)</td>
 296  * <td>Backup</td>
 297  * <td>Moves the pointer backwards within the text. This allows you to make a
 298  * "look behind." It fails if it attempts to move to a position before the
 299  * beginning of the string. "x(?&lt1)" is equivalent to "(?=x)". The number, 1
 300  * in this example, is the number of characters to move backwards.</td>
 301  * </table>
 302  * </center>
 303  * </dl>
 304  *
 305  * @author Steven R. Brandt
 306  * @version package com.stevesoft.pat, release 1.5.3
 307  * @see Pattern
 308  */
 309 public class Regex extends RegRes implements FilenameFilter
 310 {
 311   /**
 312    * BackRefOffset gives the identity number of the first pattern. Version 1.0
 313    * used zero, version 1.1 uses 1 to be more compatible with perl.
 314    */
 315   static int BackRefOffset = 1;
 316
 317   private static Pattern none = new NoPattern();
 318
 319   Pattern thePattern = none;
 320
 321   patInt minMatch = new patInt(0);
 322
 323   static Hashtable validators = new Hashtable();
 324   static
 325   {
 326     define("p", "(?>1)", new UnicodePunct());
 327     define("P", "(?>1)", new NUnicodePunct());
 328     define("s", "(?>1)", new UnicodeWhite());
 329     define("S", "(?>1)", new NUnicodeWhite());
 330     define("w", "(?>1)", new UnicodeW());
 331     define("W", "(?>1)", new NUnicodeW());
 332     define("d", "(?>1)", new UnicodeDigit());
 333     define("D", "(?>1)", new NUnicodeDigit());
 334     define("m", "(?>1)", new UnicodeMath());
 335     define("M", "(?>1)", new NUnicodeMath());
 336     define("c", "(?>1)", new UnicodeCurrency());
 337     define("C", "(?>1)", new NUnicodeCurrency());
 338     define("a", "(?>1)", new UnicodeAlpha());
 339     define("A", "(?>1)", new NUnicodeAlpha());
 340     define("uc", "(?>1)", new UnicodeUpper());
 341     define("lc", "(?>1)", new UnicodeLower());
 342   }
 343
 344   /** Set the dontMatch in quotes flag. */
 345   public void setDontMatchInQuotes(boolean b)
 346   {
 347     dontMatchInQuotes = b;
 348   }
 349
 350   /** Find out if the dontMatchInQuotes flag is enabled. */
 351   public boolean getDontMatchInQuotes()
 352   {
 353     return dontMatchInQuotes;
 354   }
 355
 356   boolean dontMatchInQuotes = false;
 357
 358   /**
 359    * Set the state of the ignoreCase flag. If set to true, then the pattern
 360    * matcher will ignore case when searching for a match.
 361    */
 362   public void setIgnoreCase(boolean b)
 363   {
 364     ignoreCase = b;
 365   }
 366
 367   /**
 368    * Get the state of the ignoreCase flag. Returns true if we are ignoring the
 369    * case of the pattern, false otherwise.
 370    */
 371   public boolean getIgnoreCase()
 372   {
 373     return ignoreCase;
 374   }
 375
 376   boolean ignoreCase = false;
 377
 378   static boolean defaultMFlag = false;
 379
 380   /**
 381    * Set the default value of the m flag. If it is set to true, then the MFlag
 382    * will be on for any regex search executed.
 383    */
 384   public static void setDefaultMFlag(boolean mFlag)
 385   {
 386     defaultMFlag = mFlag;
 387   }
 388
 389   /**
 390    * Get the default value of the m flag. If it is set to true, then the MFlag
 391    * will be on for any regex search executed.
 392    */
 393   public static boolean getDefaultMFlag()
 394   {
 395     return defaultMFlag;
 396   }
 397
 398   /**
 399    * Initializes the object without a Pattern. To supply a Pattern use
 400    * compile(String s).
 401    *
 402    * @see com.stevesoft.pat.Regex#compile(java.lang.String)
 403    */
 404   public Regex()
 405   {
 406   }
 407
 408   /**
 409    * Create and compile a Regex, but do not throw any exceptions. If you wish to
 410    * have exceptions thrown for syntax errors, you must use the Regex(void)
 411    * constructor to create the Regex object, and then call the compile method.
 412    * Therefore, you should only call this method when you know your pattern is
 413    * right. I will probably become more like
 414    *
 415    * @see com.stevesoft.pat.Regex#search(java.lang.String)
 416    * @see com.stevesoft.pat.Regex#compile(java.lang.String)
 417    */
 418   public Regex(String s)
 419   {
 420     try
 421     {
 422       compile(s);
 423     } catch (RegSyntax rs)
 424     {
 425     }
 426   }
 427
 428   ReplaceRule rep = null;
 429
 430   /**
 431    * Create and compile both a Regex and a ReplaceRule.
 432    *
 433    * @see com.stevesoft.pat.ReplaceRule
 434    * @see com.stevesoft.pat.Regex#compile(java.lang.String)
 435    */
 436   public Regex(String s, String rp)
 437   {
 438     this(s);
 439     rep = ReplaceRule.perlCode(rp);
 440   }
 441
 442   /**
 443    * Create and compile a Regex, but give it the ReplaceRule specified. This
 444    * allows the user finer control of the Replacement process, if that is
 445    * desired.
 446    *
 447    * @see com.stevesoft.pat.ReplaceRule
 448    * @see com.stevesoft.pat.Regex#compile(java.lang.String)
 449    */
 450   public Regex(String s, ReplaceRule rp)
 451   {
 452     this(s);
 453     rep = rp;
 454   }
 455
 456   /**
 457    * Change the ReplaceRule of this Regex by compiling a new one using String
 458    * rp.
 459    */
 460   public void setReplaceRule(String rp)
 461   {
 462     rep = ReplaceRule.perlCode(rp);
 463     repr = null; // Clear Replacer history
 464   }
 465
 466   /** Change the ReplaceRule of this Regex to rp. */
 467   public void setReplaceRule(ReplaceRule rp)
 468   {
 469     rep = rp;
 470   }
 471
 472   /**
 473    * Test to see if a custom defined rule exists.
 474    *
 475    * @see com.stevesoft.pat#define(java.lang.String,java.lang.String,Validator)
 476    */
 477   public static boolean isDefined(String nm)
 478   {
 479     return validators.get(nm) != null;
 480   }
 481
 482   /**
 483    * Removes a custom defined rule.
 484    *
 485    * @see com.stevesoft.pat#define(java.lang.String,java.lang.String,Validator)
 486    */
 487   public static void undefine(String nm)
 488   {
 489     validators.remove(nm);
 490   }
 491
 492   /**
 493    * Defines a method to create a new rule. See test/deriv2.java and
 494    * test/deriv3.java for examples of how to use it.
 495    */
 496   public static void define(String nm, String pat, Validator v)
 497   {
 498     v.pattern = pat;
 499     validators.put(nm, v);
 500   }
 501
 502   /**
 503    * Defines a shorthand for a pattern. The pattern will be invoked by a string
 504    * that has the form "(??"+nm+")".
 505    */
 506   public static void define(String nm, String pat)
 507   {
 508     validators.put(nm, pat);
 509   }
 510
 511   /** Get the current ReplaceRule. */
 512   public ReplaceRule getReplaceRule()
 513   {
 514     return rep;
 515   }
 516
 517   Replacer repr = null;
 518
 519   final Replacer _getReplacer()
 520   {
 521     return repr == null ? repr = new Replacer() : repr;
 522   }
 523
 524   public Replacer getReplacer()
 525   {
 526     if (repr == null)
 527     {
 528       repr = new Replacer();
 529     }
 530     repr.rh.me = this;
 531     repr.rh.prev = null;
 532     return repr;
 533   }
 534
 535   /**
 536    * Replace the first occurence of this pattern in String s according to the
 537    * ReplaceRule.
 538    *
 539    * @see com.stevesoft.pat.ReplaceRule
 540    * @see com.stevesoft.pat.Regex#getReplaceRule()
 541    */
 542   public String replaceFirst(String s)
 543   {
 544     return _getReplacer().replaceFirstRegion(s, this, 0, s.length())
 545             .toString();
 546   }
 547
 548   /**
 549    * Replace the first occurence of this pattern in String s beginning with
 550    * position pos according to the ReplaceRule.
 551    *
 552    * @see com.stevesoft.pat.ReplaceRule
 553    * @see com.stevesoft.pat.Regex#getReplaceRule()
 554    */
 555   public String replaceFirstFrom(String s, int pos)
 556   {
 557     return _getReplacer().replaceFirstRegion(s, this, pos, s.length())
 558             .toString();
 559   }
 560
 561   /**
 562    * Replace the first occurence of this pattern in String s beginning with
 563    * position start and ending with end according to the ReplaceRule.
 564    *
 565    * @see com.stevesoft.pat.ReplaceRule
 566    * @see com.stevesoft.pat.Regex#getReplaceRule()
 567    */
 568   public String replaceFirstRegion(String s, int start, int end)
 569   {
 570     return _getReplacer().replaceFirstRegion(s, this, start, end)
 571             .toString();
 572   }
 573
 574   /**
 575    * Replace all occurences of this pattern in String s according to the
 576    * ReplaceRule.
 577    *
 578    * @see com.stevesoft.pat.ReplaceRule
 579    * @see com.stevesoft.pat.Regex#getReplaceRule()
 580    */
 581   public String replaceAll(String s)
 582   {
 583     return _getReplacer().replaceAllRegion(s, this, 0, s.length())
 584             .toString();
 585   }
 586
 587   public StringLike replaceAll(StringLike s)
 588   {
 589     return _getReplacer().replaceAllRegion(s, this, 0, s.length());
 590   }
 591
 592   /**
 593    * Replace all occurences of this pattern in String s beginning with position
 594    * pos according to the ReplaceRule.
 595    *
 596    * @see com.stevesoft.pat.ReplaceRule
 597    * @see com.stevesoft.pat.Regex#getReplaceRule()
 598    */
 599   public String replaceAllFrom(String s, int pos)
 600   {
 601     return _getReplacer().replaceAllRegion(s, this, pos, s.length())
 602             .toString();
 603   }
 604
 605   /**
 606    * Replace all occurences of this pattern in String s beginning with position
 607    * start and ending with end according to the ReplaceRule.
 608    *
 609    * @see com.stevesoft.pat.ReplaceRule
 610    * @see com.stevesoft.pat.Regex#getReplaceRule()
 611    */
 612   public String replaceAllRegion(String s, int start, int end)
 613   {
 614     return _getReplacer().replaceAllRegion(s, this, start, end).toString();
 615   }
 616
 617   /** Essentially clones the Regex object */
 618   public Regex(Regex r)
 619   {
 620     super(r);
 621     dontMatchInQuotes = r.dontMatchInQuotes;
 622     esc = r.esc;
 623     ignoreCase = r.ignoreCase;
 624     gFlag = r.gFlag;
 625     if (r.rep == null)
 626     {
 627       rep = null;
 628     }
 629     else
 630     {
 631       rep = (ReplaceRule) r.rep.clone();
 632     }
 633     /*
 634      * try { compile(r.toString()); } catch(RegSyntax r_) {}
 635      */
 636     thePattern = r.thePattern.clone(new Hashtable());
 637     minMatch = r.minMatch;
 638     skipper = r.skipper;
 639   }
 640
 641   /**
 642    * By default, the escape character is the backslash, but you can make it
 643    * anything you want by setting this variable.
 644    */
 645   public char esc = Pattern.ESC;
 646
 647   /**
 648    * This method compiles a regular expression, making it possible to call the
 649    * search or matchAt methods.
 650    *
 651    * @exception com.stevesoft.pat.RegSyntax
 652    *              is thrown if a syntax error is encountered in the pattern. For
 653    *              example, "x{3,1}" or "*a" are not valid patterns.
 654    * @see com.stevesoft.pat.Regex#search
 655    * @see com.stevesoft.pat.Regex#matchAt
 656    */
 657   public void compile(String prepat) throws RegSyntax
 658   {
 659     String postpat = parsePerl.codify(prepat, true);
 660     String pat = postpat == null ? prepat : postpat;
 661     minMatch = null;
 662     ignoreCase = false;
 663     dontMatchInQuotes = false;
 664     Rthings mk = new Rthings(this);
 665     int offset = mk.val;
 666     String newpat = pat;
 667     thePattern = none;
 668     p = null;
 669     or = null;
 670     minMatch = new patInt(0);
 671     StrPos sp = new StrPos(pat, 0);
 672     if (sp.incMatch("(?e="))
 673     {
 674       char newEsc = sp.c;
 675       sp.inc();
 676       if (sp.match(')'))
 677       {
 678         newpat = reEscape(pat.substring(6), newEsc, Pattern.ESC);
 679       }
 680     }
 681     else if (esc != Pattern.ESC)
 682     {
 683       newpat = reEscape(pat, esc, Pattern.ESC);
 684     }
 685     thePattern = _compile(newpat, mk);
 686     numSubs_ = mk.val - offset;
 687     mk.set(this);
 688   }
 689
 690   /*
 691    * If a Regex is compared against a Regex, a check is done to see that the
 692    * patterns are equal as well as the most recent match. If a Regex is compare
 693    * with a RegRes, only the result of the most recent match is compared.
 694    */
 695   @Override
 696   public boolean equals(Object o)
 697   {
 698     if (o instanceof Regex)
 699     {
 700       if (toString().equals(o.toString()))
 701       {
 702         return super.equals(o);
 703       }
 704       else
 705       {
 706         return false;
 707       }
 708     }
 709     else
 710     {
 711       return super.equals(o);
 712     }
 713   }
 714
 715   /** A clone by any other name would smell as sweet. */
 716   @Override
 717   public Object clone()
 718   {
 719     return new Regex(this);
 720   }
 721
 722   /** Return a clone of the underlying RegRes object. */
 723   public RegRes result()
 724   {
 725     return (RegRes) super.clone();
 726   }
 727
 728   // prep sets global variables of class
 729   // Pattern so that it can access them
 730   // during an attempt at a match
 731   Pthings pt = new Pthings();
 732
 733   final Pthings prep(StringLike s)
 734   {
 735     // if(gFlag)
 736     pt.lastPos = matchedTo();
 737     if (pt.lastPos < 0)
 738     {
 739       pt.lastPos = 0;
 740     }
 741     if ((s == null ? null : s.unwrap()) != (src == null ? null
 742             : s.unwrap()))
 743     {
 744       pt.lastPos = 0;
 745     }
 746     src = s;
 747     pt.dotDoesntMatchCR = dotDoesntMatchCR && (!sFlag);
 748     pt.mFlag = (mFlag | defaultMFlag);
 749     pt.ignoreCase = ignoreCase;
 750     pt.no_check = false;
 751     if (pt.marks != null)
 752     {
 753       for (int i = 0; i < pt.marks.length; i++)
 754       {
 755         pt.marks[i] = -1;
 756       }
 757     }
 758     pt.marks = null;
 759     pt.nMarks = numSubs_;
 760     pt.src = s;
 761     if (dontMatchInQuotes)
 762     {
 763       setCbits(s, pt);
 764     }
 765     else
 766     {
 767       pt.cbits = null;
 768     }
 769     return pt;
 770   }
 771
 772   /**
 773    * Attempt to match a Pattern beginning at a specified location within the
 774    * string.
 775    *
 776    * @see com.stevesoft.pat.Regex#search
 777    */
 778   public boolean matchAt(String s, int start_pos)
 779   {
 780     return _search(s, start_pos, start_pos);
 781   }
 782
 783   /**
 784    * Attempt to match a Pattern beginning at a specified location within the
 785    * StringLike.
 786    *
 787    * @see com.stevesoft.pat.Regex#search
 788    */
 789   public boolean matchAt(StringLike s, int start_pos)
 790   {
 791     return _search(s, start_pos, start_pos);
 792   }
 793
 794   /**
 795    * Search through a String for the first occurrence of a match.
 796    *
 797    * @see com.stevesoft.pat.Regex#searchFrom
 798    * @see com.stevesoft.pat.Regex#matchAt
 799    */
 800   public boolean search(String s)
 801   {
 802     if (s == null)
 803     {
 804       throw new NullPointerException(MessageManager
 805               .getString("exception.null_string_given_to_regex_search"));
 806     }
 807     return _search(s, 0, s.length());
 808   }
 809
 810   public boolean search(StringLike sl)
 811   {
 812     if (sl == null)
 813     {
 814       throw new NullPointerException(MessageManager.getString(
 815               "exception.null_string_like_given_to_regex_search"));
 816     }
 817     return _search(sl, 0, sl.length());
 818   }
 819
 820   public boolean reverseSearch(String s)
 821   {
 822     if (s == null)
 823     {
 824       throw new NullPointerException(MessageManager.getString(
 825               "exception.null_string_given_to_regex_reverse_search"));
 826     }
 827     return _reverseSearch(s, 0, s.length());
 828   }
 829
 830   public boolean reverseSearch(StringLike sl)
 831   {
 832     if (sl == null)
 833     {
 834       throw new NullPointerException(MessageManager.getString(
 835               "exception.null_string_like_given_to_regex_reverse_search"));
 836     }
 837     return _reverseSearch(sl, 0, sl.length());
 838   }
 839
 840   /**
 841    * Search through a String for the first occurence of a match, but start at
 842    * position
 843    *
 844    * <pre>
 845    * start
 846    * </pre>
 847    */
 848   public boolean searchFrom(String s, int start)
 849   {
 850     if (s == null)
 851     {
 852       throw new NullPointerException(MessageManager.getString(
 853               "exception.null_string_like_given_to_regex_search_from"));
 854     }
 855     return _search(s, start, s.length());
 856   }
 857
 858   public boolean searchFrom(StringLike s, int start)
 859   {
 860     if (s == null)
 861     {
 862       throw new NullPointerException(MessageManager.getString(
 863               "exception.null_string_like_given_to_regex_search_from"));
 864     }
 865     return _search(s, start, s.length());
 866   }
 867
 868   /**
 869    * Search through a region of a String for the first occurence of a match.
 870    */
 871   public boolean searchRegion(String s, int start, int end)
 872   {
 873     if (s == null)
 874     {
 875       throw new NullPointerException(MessageManager.getString(
 876               "exception.null_string_like_given_to_regex_search_region"));
 877     }
 878     return _search(s, start, end);
 879   }
 880
 881   /**
 882    * Set this to change the default behavior of the "." pattern. By default it
 883    * now matches perl's behavior and fails to match the '\n' character.
 884    */
 885   public static boolean dotDoesntMatchCR = true;
 886
 887   StringLike gFlags;
 888
 889   int gFlagto = 0;
 890
 891   boolean gFlag = false;
 892
 893   /** Set the 'g' flag */
 894   public void setGFlag(boolean b)
 895   {
 896     gFlag = b;
 897   }
 898
 899   /** Get the state of the 'g' flag. */
 900   public boolean getGFlag()
 901   {
 902     return gFlag;
 903   }
 904
 905   boolean sFlag = false;
 906
 907   /** Get the state of the sFlag */
 908   public boolean getSFlag()
 909   {
 910     return sFlag;
 911   }
 912
 913   boolean mFlag = false;
 914
 915   /** Get the state of the sFlag */
 916   public boolean getMFlag()
 917   {
 918     return mFlag;
 919   }
 920
 921   final boolean _search(String s, int start, int end)
 922   {
 923     return _search(new StringWrap(s), start, end);
 924   }
 925
 926   final boolean _search(StringLike s, int start, int end)
 927   {
 928     if (gFlag && gFlagto > 0 && gFlags != null
 929             && s.unwrap() == gFlags.unwrap())
 930     {
 931       start = gFlagto;
 932     }
 933     gFlags = null;
 934
 935     Pthings pt = prep(s);
 936
 937     int up = (minMatch == null ? end : end - minMatch.i);
 938
 939     if (up < start && end >= start)
 940     {
 941       up = start;
 942     }
 943
 944     if (skipper == null)
 945     {
 946       for (int i = start; i <= up; i++)
 947       {
 948         charsMatched_ = thePattern.matchAt(s, i, pt);
 949         if (charsMatched_ >= 0)
 950         {
 951           matchFrom_ = thePattern.mfrom;
 952           marks = pt.marks;
 953           gFlagto = matchFrom_ + charsMatched_;
 954           gFlags = s;
 955           return didMatch_ = true;
 956         }
 957       }
 958     }
 959     else
 960     {
 961       pt.no_check = true;
 962       for (int i = start; i <= up; i++)
 963       {
 964         i = skipper.find(src, i, up);
 965         if (i < 0)
 966         {
 967           charsMatched_ = matchFrom_ = -1;
 968           return didMatch_ = false;
 969         }
 970         charsMatched_ = thePattern.matchAt(s, i, pt);
 971         if (charsMatched_ >= 0)
 972         {
 973           matchFrom_ = thePattern.mfrom;
 974           marks = pt.marks;
 975           gFlagto = matchFrom_ + charsMatched_;
 976           gFlags = s;
 977           return didMatch_ = true;
 978         }
 979       }
 980     }
 981     return didMatch_ = false;
 982   }
 983
 984   /*
 985    * final boolean _search(LongStringLike s,long start,long end) { if(gFlag &&
 986    * gFlagto > 0 && s==gFlags) start = gFlagto; gFlags = null;
 987    *
 988    * Pthings pt=prep(s);
 989    *
 990    * int up = end;//(minMatch == null ? end : end-minMatch.i);
 991    *
 992    * if(up < start && end >= start) up = start;
 993    *
 994    * if(skipper == null) { for(long i=start;i<=up;i++) { charsMatched_ =
 995    * thePattern.matchAt(s,i,pt); if(charsMatched_ >= 0) { matchFrom_ =
 996    * thePattern.mfrom; marks = pt.marks; gFlagto = matchFrom_+charsMatched_;
 997    * return didMatch_=true; } } } else { pt.no_check = true; for(long
 998    * i=start;i<=up;i++) { i = skipper.find(src,i,up); if(i<0) { charsMatched_ =
 999    * matchFrom_ = -1; return didMatch_ = false; } charsMatched_ =
1000    * thePattern.matchAt(s,i,pt); if(charsMatched_ >= 0) { matchFrom_ =
1001    * thePattern.mfrom; marks = pt.marks; gFlagto = matchFrom_+charsMatched_;
1002    * gFlags = s; return didMatch_=true; } else { i = s.adjustIndex(i); up =
1003    * s.adjustEnd(i); } } } return didMatch_=false; }
1004    */
1005
1006   boolean _reverseSearch(String s, int start, int end)
1007   {
1008     return _reverseSearch(new StringWrap(s), start, end);
1009   }
1010
1011   boolean _reverseSearch(StringLike s, int start, int end)
1012   {
1013     if (gFlag && gFlagto > 0 && s.unwrap() == gFlags.unwrap())
1014     {
1015       end = gFlagto;
1016     }
1017     gFlags = null;
1018     Pthings pt = prep(s);
1019     for (int i = end; i >= start; i--)
1020     {
1021       charsMatched_ = thePattern.matchAt(s, i, pt);
1022       if (charsMatched_ >= 0)
1023       {
1024         matchFrom_ = thePattern.mfrom;
1025         marks = pt.marks;
1026         gFlagto = matchFrom_ - 1;
1027         gFlags = s;
1028         return didMatch_ = true;
1029       }
1030     }
1031     return didMatch_ = false;
1032   }
1033
1034   // This routine sets the cbits variable
1035   // of class Pattern. Cbits is true for
1036   // the bit corresponding to a character inside
1037   // a set of quotes.
1038   static StringLike lasts = null;
1039
1040   static BitSet lastbs = null;
1041
1042   static void setCbits(StringLike s, Pthings pt)
1043   {
1044     if (s == lasts)
1045     {
1046       pt.cbits = lastbs;
1047       return;
1048     }
1049     BitSet bs = new BitSet(s.length());
1050     char qc = ' ';
1051     boolean setBit = false;
1052     for (int i = 0; i < s.length(); i++)
1053     {
1054       if (setBit)
1055       {
1056         bs.set(i);
1057       }
1058       char c = s.charAt(i);
1059       if (!setBit && c == '"')
1060       {
1061         qc = c;
1062         setBit = true;
1063         bs.set(i);
1064       }
1065       else if (!setBit && c == '\'')
1066       {
1067         qc = c;
1068         setBit = true;
1069         bs.set(i);
1070       }
1071       else if (setBit && c == qc)
1072       {
1073         setBit = false;
1074       }
1075       else if (setBit && c == '\\' && i + 1 < s.length())
1076       {
1077         i++;
1078         if (setBit)
1079         {
1080           bs.set(i);
1081         }
1082       }
1083     }
1084     pt.cbits = lastbs = bs;
1085     lasts = s;
1086   }
1087
1088   // Wanted user to over-ride this in alpha version,
1089   // but it wasn't really necessary because of this trick:
1090   Regex newRegex()
1091   {
1092     try
1093     {
1094       return getClass().getDeclaredConstructor().newInstance();
1095     } catch (InstantiationException ie)
1096     {
1097       return null;
1098     } catch (IllegalAccessException iae)
1099     {
1100       return null;
1101     } catch (ReflectiveOperationException roe)
1102     {
1103       return null;
1104     }
1105   }
1106
1107   /**
1108    * Only needed for creating your own extensions of Regex. This method adds the
1109    * next Pattern in the chain of patterns or sets the Pattern if it is the
1110    * first call.
1111    */
1112   protected void add(Pattern p2)
1113   {
1114     if (p == null)
1115     {
1116       p = p2;
1117     }
1118     else
1119     {
1120       p.add(p2);
1121       p2 = p;
1122     }
1123   }
1124
1125   /**
1126    * You only need to use this method if you are creating your own extentions to
1127    * Regex. compile1 compiles one Pattern element, it can be over-ridden to
1128    * allow the Regex compiler to understand new syntax. See deriv.java for an
1129    * example. This routine is the heart of class Regex. Rthings has one integer
1130    * member called intValue, it is used to keep track of the number of ()'s in
1131    * the Pattern.
1132    *
1133    * @exception com.stevesoft.pat.RegSyntax
1134    *              is thrown when a nonsensensical pattern is supplied. For
1135    *              example, a pattern beginning with *.
1136    */
1137   protected void compile1(StrPos sp, Rthings mk) throws RegSyntax
1138   {
1139     if (sp.match('['))
1140     {
1141       sp.inc();
1142       add(matchBracket(sp));
1143     }
1144     else if (sp.match('|'))
1145     {
1146       if (or == null)
1147       {
1148         or = new Or();
1149       }
1150       if (p == null)
1151       {
1152         p = new NullPattern();
1153       }
1154       or.addOr(p);
1155       p = null;
1156     }
1157     else if (sp.incMatch("(?<"))
1158     {
1159       patInt i = sp.getPatInt();
1160       if (i == null)
1161       {
1162         RegSyntaxError.endItAll("No int after (?<");
1163       }
1164       add(new Backup(i.intValue()));
1165       if (!sp.match(')'))
1166       {
1167         RegSyntaxError.endItAll("No ) after (?<");
1168       }
1169     }
1170     else if (sp.incMatch("(?>"))
1171     {
1172       patInt i = sp.getPatInt();
1173       if (i == null)
1174       {
1175         RegSyntaxError.endItAll("No int after (?>");
1176       }
1177       add(new Backup(-i.intValue()));
1178       if (!sp.match(')'))
1179       {
1180         RegSyntaxError.endItAll("No ) after (?<");
1181       }
1182     }
1183     else if (sp.incMatch("(?@"))
1184     {
1185       char op = sp.c;
1186       sp.inc();
1187       char cl = sp.c;
1188       sp.inc();
1189       if (!sp.match(')'))
1190       {
1191         RegSyntaxError.endItAll("(?@ does not have closing paren");
1192       }
1193       add(new Group(op, cl));
1194     }
1195     else if (sp.incMatch("(?#"))
1196     {
1197       while (!sp.match(')'))
1198       {
1199         sp.inc();
1200       }
1201     }
1202     else if (sp.dontMatch && sp.c == 'w')
1203     {
1204       // Regex r = new Regex();
1205       // r._compile("[a-zA-Z0-9_]",mk);
1206       // add(new Goop("\\w",r.thePattern));
1207       Bracket b = new Bracket(false);
1208       b.addOr(new Range('a', 'z'));
1209       b.addOr(new Range('A', 'Z'));
1210       b.addOr(new Range('0', '9'));
1211       b.addOr(new oneChar('_'));
1212       add(b);
1213     }
1214     else if (sp.dontMatch && sp.c == 'G')
1215     {
1216       add(new BackG());
1217     }
1218     else if (sp.dontMatch && sp.c == 's')
1219     {
1220       // Regex r = new Regex();
1221       // r._compile("[ \t\n\r\b]",mk);
1222       // add(new Goop("\\s",r.thePattern));
1223       Bracket b = new Bracket(false);
1224       b.addOr(new oneChar((char) 32));
1225       b.addOr(new Range((char) 8, (char) 10));
1226       b.addOr(new oneChar((char) 13));
1227       add(b);
1228     }
1229     else if (sp.dontMatch && sp.c == 'd')
1230     {
1231       // Regex r = new Regex();
1232       // r._compile("[0-9]",mk);
1233       // add(new Goop("\\d",r.thePattern));
1234       Range digit = new Range('0', '9');
1235       digit.printBrackets = true;
1236       add(digit);
1237     }
1238     else if (sp.dontMatch && sp.c == 'W')
1239     {
1240       // Regex r = new Regex();
1241       // r._compile("[^a-zA-Z0-9_]",mk);
1242       // add(new Goop("\\W",r.thePattern));
1243       Bracket b = new Bracket(true);
1244       b.addOr(new Range('a', 'z'));
1245       b.addOr(new Range('A', 'Z'));
1246       b.addOr(new Range('0', '9'));
1247       b.addOr(new oneChar('_'));
1248       add(b);
1249     }
1250     else if (sp.dontMatch && sp.c == 'S')
1251     {
1252       // Regex r = new Regex();
1253       // r._compile("[^ \t\n\r\b]",mk);
1254       // add(new Goop("\\S",r.thePattern));
1255       Bracket b = new Bracket(true);
1256       b.addOr(new oneChar((char) 32));
1257       b.addOr(new Range((char) 8, (char) 10));
1258       b.addOr(new oneChar((char) 13));
1259       add(b);
1260     }
1261     else if (sp.dontMatch && sp.c == 'D')
1262     {
1263       // Regex r = new Regex();
1264       // r._compile("[^0-9]",mk);
1265       // add(new Goop("\\D",r.thePattern));
1266       Bracket b = new Bracket(true);
1267       b.addOr(new Range('0', '9'));
1268       add(b);
1269     }
1270     else if (sp.dontMatch && sp.c == 'B')
1271     {
1272       Regex r = new Regex();
1273       r._compile("(?!" + back_slash + "b)", mk);
1274       add(r.thePattern);
1275     }
1276     else if (isOctalString(sp))
1277     {
1278       int d = sp.c - '0';
1279       sp.inc();
1280       d = 8 * d + sp.c - '0';
1281       StrPos sp2 = new StrPos(sp);
1282       sp2.inc();
1283       if (isOctalDigit(sp2, false))
1284       {
1285         sp.inc();
1286         d = 8 * d + sp.c - '0';
1287       }
1288       add(new oneChar((char) d));
1289     }
1290     else if (sp.dontMatch && sp.c >= '1' && sp.c <= '9')
1291     {
1292       int iv = sp.c - '0';
1293       StrPos s2 = new StrPos(sp);
1294       s2.inc();
1295       if (!s2.dontMatch && s2.c >= '0' && s2.c <= '9')
1296       {
1297         iv = 10 * iv + (s2.c - '0');
1298         sp.inc();
1299       }
1300       add(new BackMatch(iv));
1301     }
1302     else if (sp.dontMatch && sp.c == 'b')
1303     {
1304       add(new Boundary());
1305     }
1306     else if (sp.match('\b'))
1307     {
1308       add(new Boundary());
1309     }
1310     else if (sp.match('$'))
1311     {
1312       add(new End(true));
1313     }
1314     else if (sp.dontMatch && sp.c == 'Z')
1315     {
1316       add(new End(false));
1317     }
1318     else if (sp.match('.'))
1319     {
1320       add(new Any());
1321     }
1322     else if (sp.incMatch("(??"))
1323     {
1324       StringBuffer sb = new StringBuffer();
1325       StringBuffer sb2 = new StringBuffer();
1326       while (!sp.match(')') && !sp.match(':'))
1327       {
1328         sb.append(sp.c);
1329         sp.inc();
1330       }
1331       if (sp.incMatch(":"))
1332       {
1333         while (!sp.match(')'))
1334         {
1335           sb2.append(sp.c);
1336           sp.inc();
1337         }
1338       }
1339       String sbs = sb.toString();
1340       if (validators.get(sbs) instanceof String)
1341       {
1342         String pat = (String) validators.get(sbs);
1343         Regex r = newRegex();
1344         Rthings rth = new Rthings(this);
1345         rth.noBackRefs = true;
1346         r._compile(pat, rth);
1347         add(r.thePattern);
1348       }
1349       else
1350       {
1351         Custom cm = new Custom(sb.toString());
1352         if (cm.v != null)
1353         {
1354           Validator v2 = cm.v.arg(sb2.toString());
1355           if (v2 != null)
1356           {
1357             v2.argsave = sb2.toString();
1358             String p = cm.v.pattern;
1359             cm.v = v2;
1360             v2.pattern = p;
1361           }
1362           Regex r = newRegex();
1363           Rthings rth = new Rthings(this);
1364           rth.noBackRefs = true;
1365           r._compile(cm.v.pattern, rth);
1366           cm.sub = r.thePattern;
1367           cm.sub.add(new CustomEndpoint(cm));
1368           cm.sub.setParent(cm);
1369           add(cm);
1370         }
1371       }
1372     }
1373     else if (sp.match('('))
1374     {
1375       mk.parenLevel++;
1376       Regex r = newRegex();
1377       // r.or = new Or();
1378       sp.inc();
1379       if (sp.incMatch("?:"))
1380       {
1381         r.or = new Or();
1382       }
1383       else if (sp.incMatch("?="))
1384       {
1385         r.or = new lookAhead(false);
1386       }
1387       else if (sp.incMatch("?!"))
1388       {
1389         r.or = new lookAhead(true);
1390       }
1391       else if (sp.match('?'))
1392       {
1393         sp.inc();
1394         do
1395         {
1396           if (sp.c == 'i')
1397           {
1398             mk.ignoreCase = true;
1399           }
1400           if (sp.c == 'Q')
1401           {
1402             mk.dontMatchInQuotes = true;
1403           }
1404           if (sp.c == 'o')
1405           {
1406             mk.optimizeMe = true;
1407           }
1408           if (sp.c == 'g')
1409           {
1410             mk.gFlag = true;
1411           }
1412           if (sp.c == 's')
1413           {
1414             mk.sFlag = true;
1415           }
1416           if (sp.c == 'm')
1417           {
1418             mk.mFlag = true;
1419           }
1420           sp.inc();
1421         } while (!sp.match(')') && !sp.eos);
1422         r = null;
1423         mk.parenLevel--;
1424         if (sp.eos) // throw new RegSyntax
1425         {
1426           RegSyntaxError.endItAll("Unclosed ()");
1427         }
1428       }
1429       else
1430       { // just ordinary parenthesis
1431         r.or = mk.noBackRefs ? new Or() : new OrMark(mk.val++);
1432       }
1433       if (r != null)
1434       {
1435         add(r._compile(sp, mk));
1436       }
1437     }
1438     else if (sp.match('^'))
1439     {
1440       add(new Start(true));
1441     }
1442     else if (sp.dontMatch && sp.c == 'A')
1443     {
1444       add(new Start(false));
1445     }
1446     else if (sp.match('*'))
1447     {
1448       addMulti(new patInt(0), new patInf());
1449     }
1450     else if (sp.match('+'))
1451     {
1452       addMulti(new patInt(1), new patInf());
1453     }
1454     else if (sp.match('?'))
1455     {
1456       addMulti(new patInt(0), new patInt(1));
1457     }
1458     else if (sp.match('{'))
1459     {
1460       boolean bad = false;
1461       StrPos sp2 = new StrPos(sp);
1462       // StringBuffer sb = new StringBuffer();
1463       sp.inc();
1464       patInt i1 = sp.getPatInt();
1465       patInt i2 = null;
1466       if (sp.match('}'))
1467       {
1468         i2 = i1;
1469       }
1470       else
1471       {
1472         if (!sp.match(','))
1473         {
1474           /*
1475            * RegSyntaxError.endItAll( "String \"{"+i2+ "\" should be followed
1476            * with , or }");
1477            */
1478           bad = true;
1479         }
1480         sp.inc();
1481         if (sp.match('}'))
1482         {
1483           i2 = new patInf();
1484         }
1485         else
1486         {
1487           i2 = sp.getPatInt();
1488         }
1489       }
1490       if (i1 == null || i2 == null)
1491       {
1492         /*
1493          * throw new RegSyntax("Badly formatted Multi: " +"{"+i1+","+i2+"}");
1494          */
1495         bad = true;
1496       }
1497       if (bad)
1498       {
1499         sp.dup(sp2);
1500         add(new oneChar(sp.c));
1501       }
1502       else
1503       {
1504         addMulti(i1, i2);
1505       }
1506     }
1507     else if (sp.escMatch('x') && next2Hex(sp))
1508     {
1509       sp.inc();
1510       int d = getHexDigit(sp);
1511       sp.inc();
1512       d = 16 * d + getHexDigit(sp);
1513       add(new oneChar((char) d));
1514     }
1515     else if (sp.escMatch('c'))
1516     {
1517       sp.inc();
1518       if (sp.c < Ctrl.cmap.length)
1519       {
1520         add(new oneChar(Ctrl.cmap[sp.c]));
1521       }
1522       else
1523       {
1524         add(new oneChar(sp.c));
1525       }
1526     }
1527     else if (sp.escMatch('f'))
1528     {
1529       add(new oneChar((char) 12));
1530     }
1531     else if (sp.escMatch('a'))
1532     {
1533       add(new oneChar((char) 7));
1534     }
1535     else if (sp.escMatch('t'))
1536     {
1537       add(new oneChar('\t'));
1538     }
1539     else if (sp.escMatch('n'))
1540     {
1541       add(new oneChar('\n'));
1542     }
1543     else if (sp.escMatch('r'))
1544     {
1545       add(new oneChar('\r'));
1546     }
1547     else if (sp.escMatch('b'))
1548     {
1549       add(new oneChar('\b'));
1550     }
1551     else if (sp.escMatch('e'))
1552     {
1553       add(new oneChar((char) 27));
1554     }
1555     else
1556     {
1557       add(new oneChar(sp.c));
1558       if (sp.match(')'))
1559       {
1560         RegSyntaxError.endItAll("Unmatched right paren in pattern");
1561       }
1562     }
1563   }
1564
1565   // compiles all Pattern elements, internal method
1566   private Pattern _compile(String pat, Rthings mk) throws RegSyntax
1567   {
1568     minMatch = null;
1569     sFlag = mFlag = ignoreCase = gFlag = false;
1570     StrPos sp = new StrPos(pat, 0);
1571     thePattern = _compile(sp, mk);
1572     pt.marks = null;
1573     return thePattern;
1574   }
1575
1576   Pattern p = null;
1577
1578   Or or = null;
1579
1580   Pattern _compile(StrPos sp, Rthings mk) throws RegSyntax
1581   {
1582     while (!(sp.eos || (or != null && sp.match(')'))))
1583     {
1584       compile1(sp, mk);
1585       sp.inc();
1586     }
1587     if (sp.match(')'))
1588     {
1589       mk.parenLevel--;
1590     }
1591     else if (sp.eos && mk.parenLevel != 0)
1592     {
1593       RegSyntaxError.endItAll("Unclosed Parenthesis! lvl=" + mk.parenLevel);
1594     }
1595     if (or != null)
1596     {
1597       if (p == null)
1598       {
1599         p = new NullPattern();
1600       }
1601       or.addOr(p);
1602       return or;
1603     }
1604     return p == null ? new NullPattern() : p;
1605   }
1606
1607   // add a multi object to the end of the chain
1608   // which applies to the last object
1609   void addMulti(patInt i1, patInt i2) throws RegSyntax
1610   {
1611     Pattern last, last2;
1612     for (last = p; last != null && last.next != null; last = last.next)
1613     {
1614       ;
1615     }
1616     if (last == null || last == p)
1617     {
1618       last2 = null;
1619     }
1620     else
1621     {
1622       for (last2 = p; last2.next != last; last2 = last2.next)
1623       {
1624         ;
1625       }
1626     }
1627     if (last instanceof Multi && i1.intValue() == 0 && i2.intValue() == 1)
1628     {
1629       ((Multi) last).matchFewest = true;
1630     }
1631     else if (last instanceof FastMulti && i1.intValue() == 0
1632             && i2.intValue() == 1)
1633     {
1634       ((FastMulti) last).matchFewest = true;
1635     }
1636     else if (last instanceof DotMulti && i1.intValue() == 0
1637             && i2.intValue() == 1)
1638     {
1639       ((DotMulti) last).matchFewest = true;
1640     }
1641     else if (last instanceof Multi || last instanceof DotMulti
1642             || last instanceof FastMulti)
1643     {
1644       throw new RegSyntax("Syntax error.");
1645     }
1646     else if (last2 == null)
1647     {
1648       p = mkMulti(i1, i2, p);
1649     }
1650     else
1651     {
1652       last2.next = mkMulti(i1, i2, last);
1653     }
1654   }
1655
1656   final static Pattern mkMulti(patInt lo, patInt hi, Pattern p)
1657           throws RegSyntax
1658   {
1659     if (p instanceof Any && p.next == null)
1660     {
1661       return new DotMulti(lo, hi);
1662     }
1663     return RegOpt.safe4fm(p) ? (Pattern) new FastMulti(lo, hi, p)
1664             : (Pattern) new Multi(lo, hi, p);
1665   }
1666
1667   // process the bracket operator
1668   Pattern matchBracket(StrPos sp) throws RegSyntax
1669   {
1670     Bracket ret;
1671     if (sp.match('^'))
1672     {
1673       ret = new Bracket(true);
1674       sp.inc();
1675     }
1676     else
1677     {
1678       ret = new Bracket(false);
1679     }
1680     if (sp.match(']'))
1681     {
1682       // throw new RegSyntax
1683       RegSyntaxError.endItAll("Unmatched []");
1684     }
1685
1686     while (!sp.eos && !sp.match(']'))
1687     {
1688       StrPos s1 = new StrPos(sp);
1689       s1.inc();
1690       StrPos s1_ = new StrPos(s1);
1691       s1_.inc();
1692       if (s1.match('-') && !s1_.match(']'))
1693       {
1694         StrPos s2 = new StrPos(s1);
1695         s2.inc();
1696         if (!s2.eos)
1697         {
1698           ret.addOr(new Range(sp.c, s2.c));
1699         }
1700         sp.inc();
1701         sp.inc();
1702       }
1703       else if (sp.escMatch('Q'))
1704       {
1705         sp.inc();
1706         while (!sp.escMatch('E'))
1707         {
1708           ret.addOr(new oneChar(sp.c));
1709           sp.inc();
1710         }
1711       }
1712       else if (sp.escMatch('d'))
1713       {
1714         ret.addOr(new Range('0', '9'));
1715       }
1716       else if (sp.escMatch('s'))
1717       {
1718         ret.addOr(new oneChar((char) 32));
1719         ret.addOr(new Range((char) 8, (char) 10));
1720         ret.addOr(new oneChar((char) 13));
1721       }
1722       else if (sp.escMatch('w'))
1723       {
1724         ret.addOr(new Range('a', 'z'));
1725         ret.addOr(new Range('A', 'Z'));
1726         ret.addOr(new Range('0', '9'));
1727         ret.addOr(new oneChar('_'));
1728       }
1729       else if (sp.escMatch('D'))
1730       {
1731         ret.addOr(new Range((char) 0, (char) 47));
1732         ret.addOr(new Range((char) 58, (char) 65535));
1733       }
1734       else if (sp.escMatch('S'))
1735       {
1736         ret.addOr(new Range((char) 0, (char) 7));
1737         ret.addOr(new Range((char) 11, (char) 12));
1738         ret.addOr(new Range((char) 14, (char) 31));
1739         ret.addOr(new Range((char) 33, (char) 65535));
1740       }
1741       else if (sp.escMatch('W'))
1742       {
1743         ret.addOr(new Range((char) 0, (char) 64));
1744         ret.addOr(new Range((char) 91, (char) 94));
1745         ret.addOr(new oneChar((char) 96));
1746         ret.addOr(new Range((char) 123, (char) 65535));
1747       }
1748       else if (sp.escMatch('x') && next2Hex(sp))
1749       {
1750         sp.inc();
1751         int d = getHexDigit(sp);
1752         sp.inc();
1753         d = 16 * d + getHexDigit(sp);
1754         ret.addOr(new oneChar((char) d));
1755       }
1756       else if (sp.escMatch('a'))
1757       {
1758         ret.addOr(new oneChar((char) 7));
1759       }
1760       else if (sp.escMatch('f'))
1761       {
1762         ret.addOr(new oneChar((char) 12));
1763       }
1764       else if (sp.escMatch('e'))
1765       {
1766         ret.addOr(new oneChar((char) 27));
1767       }
1768       else if (sp.escMatch('n'))
1769       {
1770         ret.addOr(new oneChar('\n'));
1771       }
1772       else if (sp.escMatch('t'))
1773       {
1774         ret.addOr(new oneChar('\t'));
1775       }
1776       else if (sp.escMatch('r'))
1777       {
1778         ret.addOr(new oneChar('\r'));
1779       }
1780       else if (sp.escMatch('c'))
1781       {
1782         sp.inc();
1783         if (sp.c < Ctrl.cmap.length)
1784         {
1785           ret.addOr(new oneChar(Ctrl.cmap[sp.c]));
1786         }
1787         else
1788         {
1789           ret.addOr(new oneChar(sp.c));
1790         }
1791       }
1792       else if (isOctalString(sp))
1793       {
1794         int d = sp.c - '0';
1795         sp.inc();
1796         d = 8 * d + sp.c - '0';
1797         StrPos sp2 = new StrPos(sp);
1798         sp2.inc();
1799         if (isOctalDigit(sp2, false))
1800         {
1801           sp.inc();
1802           d = 8 * d + sp.c - '0';
1803         }
1804         ret.addOr(new oneChar((char) d));
1805       }
1806       else
1807       {
1808         ret.addOr(new oneChar(sp.c));
1809       }
1810       sp.inc();
1811     }
1812     return ret;
1813   }
1814
1815   /**
1816    * Converts the stored Pattern to a String -- this is a decompile. Note that
1817    * \t and \n will really print out here, Not just the two character
1818    * representations. Also be prepared to see some strange output if your
1819    * characters are not printable.
1820    */
1821   @Override
1822   public String toString()
1823   {
1824     if (false && thePattern == null)
1825     {
1826       return "";
1827     }
1828     else
1829     {
1830       StringBuffer sb = new StringBuffer();
1831       if (esc != Pattern.ESC)
1832       {
1833         sb.append("(?e=");
1834         sb.append(esc);
1835         sb.append(")");
1836       }
1837       if (gFlag || mFlag || !dotDoesntMatchCR || sFlag || ignoreCase
1838               || dontMatchInQuotes || optimized())
1839       {
1840         sb.append("(?");
1841         if (ignoreCase)
1842         {
1843           sb.append("i");
1844         }
1845         if (mFlag)
1846         {
1847           sb.append("m");
1848         }
1849         if (sFlag || !dotDoesntMatchCR)
1850         {
1851           sb.append("s");
1852         }
1853         if (dontMatchInQuotes)
1854         {
1855           sb.append("Q");
1856         }
1857         if (optimized())
1858         {
1859           sb.append("o");
1860         }
1861         if (gFlag)
1862         {
1863           sb.append("g");
1864         }
1865         sb.append(")");
1866       }
1867       String patstr = thePattern.toString();
1868       if (esc != Pattern.ESC)
1869       {
1870         patstr = reEscape(patstr, Pattern.ESC, esc);
1871       }
1872       sb.append(patstr);
1873       return sb.toString();
1874     }
1875   }
1876
1877   // Re-escape Pattern, allows us to use a different escape
1878   // character.
1879   static String reEscape(String s, char oldEsc, char newEsc)
1880   {
1881     if (oldEsc == newEsc)
1882     {
1883       return s;
1884     }
1885     int i;
1886     StringBuffer sb = new StringBuffer();
1887     for (i = 0; i < s.length(); i++)
1888     {
1889       if (s.charAt(i) == oldEsc && i + 1 < s.length())
1890       {
1891         if (s.charAt(i + 1) == oldEsc)
1892         {
1893           sb.append(oldEsc);
1894         }
1895         else
1896         {
1897           sb.append(newEsc);
1898           sb.append(s.charAt(i + 1));
1899         }
1900         i++;
1901       }
1902       else if (s.charAt(i) == newEsc)
1903       {
1904         sb.append(newEsc);
1905         sb.append(newEsc);
1906       }
1907       else
1908       {
1909         sb.append(s.charAt(i));
1910       }
1911     }
1912     return sb.toString();
1913   }
1914
1915   /**
1916    * This method implements FilenameFilter, allowing one to use a Regex to
1917    * search through a directory using File.list. There is a FileRegex now that
1918    * does this better.
1919    *
1920    * @see com.stevesoft.pat.FileRegex
1921    */
1922   @Override
1923   public boolean accept(File dir, String s)
1924   {
1925     return search(s);
1926   }
1927
1928   /** The version of this package */
1929   final static public String version()
1930   {
1931     return "lgpl release 1.5.3";
1932   }
1933
1934   /**
1935    * Once this method is called, the state of variables ignoreCase and
1936    * dontMatchInQuotes should not be changed as the results will be
1937    * unpredictable. However, search and matchAt will run more quickly. Note that
1938    * you can check to see if the pattern has been optimized by calling the
1939    * optimized() method.
1940    * <p>
1941    * This method will attempt to rewrite your pattern in a way that makes it
1942    * faster (not all patterns execute at the same speed). In general, "(?: ...
1943    * )" will be faster than "( ... )" so if you don't need the backreference,
1944    * you should group using the former pattern.
1945    * <p>
1946    * It will also introduce new pattern elements that you can't get to
1947    * otherwise, for example if you have a large table of strings, i.e. the
1948    * months of the year "(January|February|...)" optimize() will make a
1949    * Hashtable that takes it to the next appropriate pattern element --
1950    * eliminating the need for a linear search.
1951    *
1952    * @see com.stevesoft.pat.Regex#optimized
1953    * @see com.stevesoft.pat.Regex#ignoreCase
1954    * @see com.stevesoft.pat.Regex#dontMatchInQuotes
1955    * @see com.stevesoft.pat.Regex#matchAt
1956    * @see com.stevesoft.pat.Regex#search
1957    */
1958   public void optimize()
1959   {
1960     if (optimized() || thePattern == null)
1961     {
1962       return;
1963     }
1964     minMatch = new patInt(0); // thePattern.countMinChars();
1965     thePattern = RegOpt.opt(thePattern, ignoreCase, dontMatchInQuotes);
1966     skipper = Skip.findSkip(this);
1967     // RegOpt.setParents(this);
1968     return;
1969   }
1970
1971   Skip skipper;
1972
1973   /**
1974    * This function returns true if the optimize method has been called.
1975    */
1976   public boolean optimized()
1977   {
1978     return minMatch != null;
1979   }
1980
1981   /**
1982    * A bit of syntactic surgar for those who want to make their code look more
1983    * perl-like. To use this initialize your Regex object by saying:
1984    *
1985    * <pre>
1986    *       Regex r1 = Regex.perlCode(&quot;s/hello/goodbye/&quot;);
1987    *       Regex r2 = Regex.perlCode(&quot;s'fish'frog'i&quot;);
1988    *       Regex r3 = Regex.perlCode(&quot;m'hello');
1989    * </pre>
1990    *
1991    * The i for ignoreCase is supported in this syntax, as well as m, s, and x.
1992    * The g flat is a bit of a special case.
1993    * <p>
1994    * If you wish to replace all occurences of a pattern, you do not put a 'g' in
1995    * the perlCode, but call Regex's replaceAll method.
1996    * <p>
1997    * If you wish to simply and only do a search for r2's pattern, you can do
1998    * this by calling the searchFrom method method repeatedly, or by calling
1999    * search repeatedly if the g flag is set.
2000    * <p>
2001    * Note: Currently perlCode does <em>not</em> support the (?e=#) syntax for
2002    * changing the escape character.
2003    */
2004
2005   public static Regex perlCode(String s)
2006   {
2007     // this file is big enough, see parsePerl.java
2008     // for this function.
2009     return parsePerl.parse(s);
2010   }
2011
2012   static final char back_slash = '\\';
2013
2014   /**
2015    * Checks to see if there are only literal and no special pattern elements in
2016    * this Regex.
2017    */
2018   public boolean isLiteral()
2019   {
2020     Pattern x = thePattern;
2021     while (x != null)
2022     {
2023       if (x instanceof oneChar)
2024       {
2025         ;
2026       }
2027       else if (x instanceof Skipped)
2028       {
2029         ;
2030       }
2031       else
2032       {
2033         return false;
2034       }
2035       x = x.next;
2036     }
2037     return true;
2038   }
2039
2040   /**
2041    * You only need to know about this if you are inventing your own pattern
2042    * elements.
2043    */
2044   public patInt countMinChars()
2045   {
2046     return thePattern.countMinChars();
2047   }
2048
2049   /**
2050    * You only need to know about this if you are inventing your own pattern
2051    * elements.
2052    */
2053   public patInt countMaxChars()
2054   {
2055     return thePattern.countMaxChars();
2056   }
2057
2058   boolean isHexDigit(StrPos sp)
2059   {
2060     boolean r = !sp.eos && !sp.dontMatch
2061             && ((sp.c >= '0' && sp.c <= '9') || (sp.c >= 'a' && sp.c <= 'f')
2062                     || (sp.c >= 'A' && sp.c <= 'F'));
2063     return r;
2064   }
2065
2066   boolean isOctalDigit(StrPos sp, boolean first)
2067   {
2068     boolean r = !sp.eos && !(first ^ sp.dontMatch) && sp.c >= '0'
2069             && sp.c <= '7';
2070     return r;
2071   }
2072
2073   int getHexDigit(StrPos sp)
2074   {
2075     if (sp.c >= '0' && sp.c <= '9')
2076     {
2077       return sp.c - '0';
2078     }
2079     if (sp.c >= 'a' && sp.c <= 'f')
2080     {
2081       return sp.c - 'a' + 10;
2082     }
2083     return sp.c - 'A' + 10;
2084   }
2085
2086   boolean next2Hex(StrPos sp)
2087   {
2088     StrPos sp2 = new StrPos(sp);
2089     sp2.inc();
2090     if (!isHexDigit(sp2))
2091     {
2092       return false;
2093     }
2094     sp2.inc();
2095     if (!isHexDigit(sp2))
2096     {
2097       return false;
2098     }
2099     return true;
2100   }
2101
2102   boolean isOctalString(StrPos sp)
2103   {
2104     if (!isOctalDigit(sp, true))
2105     {
2106       return false;
2107     }
2108     StrPos sp2 = new StrPos(sp);
2109     sp2.inc();
2110     if (!isOctalDigit(sp2, false))
2111     {
2112       return false;
2113     }
2114     return true;
2115   }
2116 }