1 // Scintilla source code edit control
3 ** Regular expression search library.
7 * regex - Regular expression pattern matching and replacement
9 * By: Ozan S. Yigit (oz)
10 * Dept. of Computer Science
13 * Original code available from http://www.cs.yorku.ca/~oz/
14 * Translation to C++ by Neil Hodgson neilh@scintilla.org
15 * Removed all use of register.
16 * Converted to modern function prototypes.
17 * Put all global/static variables into an object so this code can be
18 * used from multiple threads, etc.
19 * Some extensions by Philippe Lhoste PhiLho(a)GMX.net
21 * These routines are the PUBLIC DOMAIN equivalents of regex
22 * routines as found in 4.nBSD UN*X, with minor extensions.
24 * These routines are derived from various implementations found
25 * in software tools books, and Conroy's grep. They are NOT derived
26 * from licensed/restricted software.
27 * For more interesting/academic/complicated implementations,
28 * see Henry Spencer's regexp routines, or GNU Emacs pattern
31 * Modification history removed.
34 * RESearch::Compile: compile a regular expression into a NFA.
36 * const char *RESearch::Compile(const char *pattern, int length,
37 * bool caseSensitive, bool posix)
39 * Returns a short error string if they fail.
41 * RESearch::Execute: execute the NFA to match a pattern.
43 * int RESearch::Execute(characterIndexer &ci, int lp, int endp)
45 * RESearch::Substitute: substitute the matched portions in a new string.
47 * int RESearch::Substitute(CharacterIndexer &ci, char *src, char *dst)
49 * re_fail: failure routine for RESearch::Execute. (no longer used)
51 * void re_fail(char *msg, char op)
53 * Regular Expressions:
55 * [1] char matches itself, unless it is a special
56 * character (metachar): . \ [ ] * + ^ $
57 * and ( ) if posix option.
59 * [2] . matches any character.
61 * [3] \ matches the character following it, except:
62 * - \a, \b, \f, \n, \r, \t, \v match the corresponding C
63 * escape char, respectively BEL, BS, FF, LF, CR, TAB and VT;
64 * Note that \r and \n are never matched because Scintilla
65 * regex searches are made line per line
66 * (stripped of end-of-line chars).
67 * - if not in posix mode, when followed by a
68 * left or right round bracket (see [7]);
69 * - when followed by a digit 1 to 9 (see [8]);
70 * - when followed by a left or right angle bracket
72 * - when followed by d, D, s, S, w or W (see [10]);
73 * - when followed by x and two hexa digits (see [11].
74 * Backslash is used as an escape character for all
75 * other meta-characters, and itself.
77 * [4] [set] matches one of the characters in the set.
78 * If the first character in the set is "^",
79 * it matches the characters NOT in the set, i.e.
80 * complements the set. A shorthand S-E (start dash end)
81 * is used to specify a set of characters S up to
82 * E, inclusive. S and E must be characters, otherwise
83 * the dash is taken literally (eg. in expression [\d-a]).
84 * The special characters "]" and "-" have no special
85 * meaning if they appear as the first chars in the set.
86 * To include both, put - first: [-]A-Z]
87 * (or just backslash them).
90 * [-]|] matches these 3 chars,
92 * []-|] matches from ] to | chars
94 * [a-z] any lowercase alpha
96 * [^-]] any char except - and ]
98 * [^A-Z] any char except uppercase
103 * [5] * any regular expression form [1] to [4]
104 * (except [7], [8] and [9] forms of [3]),
105 * followed by closure char (*)
106 * matches zero or more matches of that form.
108 * [6] + same as [5], except it matches one or more.
109 * Both [5] and [6] are greedy (they match as much as possible).
111 * [7] a regular expression in the form [1] to [12], enclosed
112 * as \(form\) (or (form) with posix flag) matches what
113 * form matches. The enclosure creates a set of tags,
114 * used for [8] and for pattern substitution.
115 * The tagged forms are numbered starting from 1.
117 * [8] a \ followed by a digit 1 to 9 matches whatever a
118 * previously tagged regular expression ([7]) matched.
120 * [9] \< a regular expression starting with a \< construct
121 * \> and/or ending with a \> construct, restricts the
122 * pattern matching to the beginning of a word, and/or
123 * the end of a word. A word is defined to be a character
124 * string beginning and/or ending with the characters
125 * A-Z a-z 0-9 and _. Scintilla extends this definition
126 * by user setting. The word must also be preceded and/or
127 * followed by any character outside those mentioned.
129 * [10] \l a backslash followed by d, D, s, S, w or W,
130 * becomes a character class (both inside and
133 * D: any char except decimal digits
134 * s: whitespace (space, \t \n \r \f \v)
135 * S: any char except whitespace (see above)
136 * w: alphanumeric & underscore (changed by user setting)
137 * W: any char except alphanumeric & underscore (see above)
139 * [11] \xHH a backslash followed by x and two hexa digits,
140 * becomes the character whose Ascii code is equal
141 * to these digits. If not followed by two digits,
142 * it is 'x' char itself.
144 * [12] a composite regular expression xy where x and y
145 * are in the form [1] to [11] matches the longest
146 * match of x followed by a match for y.
148 * [13] ^ a regular expression starting with a ^ character
149 * $ and/or ending with a $ character, restricts the
150 * pattern matching to the beginning of the line,
151 * or the end of line. [anchors] Elsewhere in the
152 * pattern, ^ and $ are treated as ordinary characters.
157 * HCR's Hugh Redelmeier has been most helpful in various
158 * stages of development. He convinced me to include BOW
159 * and EOW constructs, originally invented by Rob Pike at
160 * the University of Toronto.
163 * Software tools Kernighan & Plauger
164 * Software tools in Pascal Kernighan & Plauger
165 * Grep [rsx-11 C dist] David Conroy
166 * ed - text editor Un*x Programmer's Manual
167 * Advanced editing on Un*x B. W. Kernighan
168 * RegExp routines Henry Spencer
172 * This implementation uses a bit-set representation for character
173 * classes for speed and compactness. Each character is represented
174 * by one bit in a 256-bit block. Thus, CCL always takes a
175 * constant 32 bytes in the internal nfa, and RESearch::Execute does a single
176 * bit comparison to locate the character in the set.
181 * compile: CHR f CHR o CLO CHR o END CLO ANY END END
182 * matches: fo foo fooo foobar fobar foxx ...
184 * pattern: fo[ob]a[rz]
185 * compile: CHR f CHR o CCL bitset CHR a CCL bitset END
186 * matches: fobar fooar fobaz fooaz
189 * compile: CHR f CHR o CHR o CHR \ CLO CHR \ END END
190 * matches: foo\ foo\\ foo\\\ ...
192 * pattern: \(foo\)[1-3]\1 (same as foo[1-3]foo)
193 * compile: BOT 1 CHR f CHR o CHR o EOT 1 CCL bitset REF 1 END
194 * matches: foo1foo foo2foo foo3foo
196 * pattern: \(fo.*\)-\1
197 * compile: BOT 1 CHR f CHR o CLO ANY END EOT 1 CHR - REF 1 END
198 * matches: foo-foo fo-fo fob-fob foobar-foobar ...
203 #include "CharClassify.h"
204 #include "RESearch.h"
206 // Shut up annoying Visual C++ warnings:
208 #pragma warning(disable: 4514)
212 using namespace Scintilla
;
233 * The following defines are not meant to be changeable.
234 * They are for readability only.
239 const char bitarr
[] = { 1, 2, 4, 8, 16, 32, 64, '\200' };
241 #define badpat(x) (*nfa = END, x)
244 * Character classification table for word boundary operators BOW
245 * and EOW is passed in by the creator of this object (Scintilla
246 * Document). The Document default state is that word chars are:
247 * 0-9, a-z, A-Z and _
250 RESearch::RESearch(CharClassify
*charClassTable
) {
251 charClass
= charClassTable
;
255 RESearch::~RESearch() {
259 void RESearch::Init() {
260 sta
= NOP
; /* status of lastpat */
262 for (int i
= 0; i
< MAXTAG
; i
++)
264 for (int j
= 0; j
< BITBLK
; j
++)
268 void RESearch::Clear() {
269 for (int i
= 0; i
< MAXTAG
; i
++) {
277 bool RESearch::GrabMatches(CharacterIndexer
&ci
) {
279 for (unsigned int i
= 0; i
< MAXTAG
; i
++) {
280 if ((bopat
[i
] != NOTFOUND
) && (eopat
[i
] != NOTFOUND
)) {
281 unsigned int len
= eopat
[i
] - bopat
[i
];
282 pat
[i
] = new char[len
+ 1];
284 for (unsigned int j
= 0; j
< len
; j
++)
285 pat
[i
][j
] = ci
.CharAt(bopat
[i
] + j
);
295 void RESearch::ChSet(unsigned char c
) {
296 bittab
[((c
) & BLKIND
) >> 3] |= bitarr
[(c
) & BITIND
];
299 void RESearch::ChSetWithCase(unsigned char c
, bool caseSensitive
) {
303 if ((c
>= 'a') && (c
<= 'z')) {
305 ChSet(static_cast<unsigned char>(c
- 'a' + 'A'));
306 } else if ((c
>= 'A') && (c
<= 'Z')) {
308 ChSet(static_cast<unsigned char>(c
- 'A' + 'a'));
315 const unsigned char escapeValue(unsigned char ch
) {
317 case 'a': return '\a';
318 case 'b': return '\b';
319 case 'f': return '\f';
320 case 'n': return '\n';
321 case 'r': return '\r';
322 case 't': return '\t';
323 case 'v': return '\v';
328 static int GetHexaChar(unsigned char hd1
, unsigned char hd2
) {
330 if (hd1
>= '0' && hd1
<= '9') {
331 hexValue
+= 16 * (hd1
- '0');
332 } else if (hd1
>= 'A' && hd1
<= 'F') {
333 hexValue
+= 16 * (hd1
- 'A' + 10);
334 } else if (hd1
>= 'a' && hd1
<= 'f') {
335 hexValue
+= 16 * (hd1
- 'a' + 10);
338 if (hd2
>= '0' && hd2
<= '9') {
339 hexValue
+= hd2
- '0';
340 } else if (hd2
>= 'A' && hd2
<= 'F') {
341 hexValue
+= hd2
- 'A' + 10;
342 } else if (hd2
>= 'a' && hd2
<= 'f') {
343 hexValue
+= hd2
- 'a' + 10;
350 * Called when the parser finds a backslash not followed
351 * by a valid expression (like \( in non-Posix mode).
352 * @param pattern: pointer on the char after the backslash.
353 * @param incr: (out) number of chars to skip after expression evaluation.
354 * @return the char if it resolves to a simple char,
355 * or -1 for a char class. In this case, bittab is changed.
357 int RESearch::GetBackslashExpression(
360 // Since error reporting is primitive and messages are not used anyway,
361 // I choose to interpret unexpected syntax in a logical way instead
362 // of reporting errors. Otherwise, we can stick on, eg., PCRE behavior.
363 incr
= 0; // Most of the time, will skip the char "naturally".
366 unsigned char bsc
= *pattern
;
369 result
= '\\'; // \ at end of pattern, take it literally
381 result
= escapeValue(bsc
);
384 unsigned char hd1
= *(pattern
+ 1);
385 unsigned char hd2
= *(pattern
+ 2);
386 int hexValue
= GetHexaChar(hd1
, hd2
);
389 incr
= 2; // Must skip the digits
391 result
= 'x'; // \x without 2 digits: see it as 'x'
396 for (c
= '0'; c
<= '9'; c
++) {
397 ChSet(static_cast<unsigned char>(c
));
401 for (c
= 0; c
< MAXCHR
; c
++) {
402 if (c
< '0' || c
> '9') {
403 ChSet(static_cast<unsigned char>(c
));
416 for (c
= 0; c
< MAXCHR
; c
++) {
417 if (c
!= ' ' && !(c
>= 0x09 && c
<= 0x0D)) {
418 ChSet(static_cast<unsigned char>(c
));
423 for (c
= 0; c
< MAXCHR
; c
++) {
424 if (iswordc(static_cast<unsigned char>(c
))) {
425 ChSet(static_cast<unsigned char>(c
));
430 for (c
= 0; c
< MAXCHR
; c
++) {
431 if (!iswordc(static_cast<unsigned char>(c
))) {
432 ChSet(static_cast<unsigned char>(c
));
442 const char *RESearch::Compile(const char *pattern
, int length
, bool caseSensitive
, bool posix
) {
443 char *mp
=nfa
; /* nfa pointer */
444 char *lp
; /* saved pointer */
445 char *sp
=nfa
; /* another one */
446 char *mpMax
= mp
+ MAXNFA
- BITBLK
- 10;
448 int tagi
= 0; /* tag stack index */
449 int tagc
= 1; /* actual tag count */
452 char mask
; /* xor mask -CCL/NCL */
453 int c1
, c2
, prevChar
;
455 if (!pattern
|| !length
) {
459 return badpat("No previous regular expression");
463 const char *p
=pattern
; /* pattern pointer */
464 for (int i
=0; i
<length
; i
++, p
++) {
466 return badpat("Pattern too long");
470 case '.': /* match any char */
474 case '^': /* match beginning */
483 case '$': /* match endofline */
492 case '[': /* match char class */
504 if (*p
== '-') { /* real dash */
509 if (*p
== ']') { /* real brace */
514 while (*p
&& *p
!= ']') {
517 // Previous def. was a char class like \d, take dash literally
526 if (!*(p
+1)) // End of RE
527 return badpat("Missing ]");
532 c2
= GetBackslashExpression(p
, incr
);
536 // Convention: \c (c is any char) is case sensitive, whatever the option
537 ChSet(static_cast<unsigned char>(c2
));
540 // bittab is already changed
546 // Char after dash is char class like \d, take dash literally
550 // Put all chars between c1 and c2 included in the char set
552 ChSetWithCase(static_cast<unsigned char>(c1
++), caseSensitive
);
556 // Dash before the ], take it literally
561 return badpat("Missing ]");
563 } else if (*p
== '\\' && *(p
+1)) {
567 int c
= GetBackslashExpression(p
, incr
);
571 // Convention: \c (c is any char) is case sensitive, whatever the option
572 ChSet(static_cast<unsigned char>(c
));
575 // bittab is already changed
580 ChSetWithCase(*p
, caseSensitive
);
586 return badpat("Missing ]");
588 for (n
= 0; n
< BITBLK
; bittab
[n
++] = 0)
589 *mp
++ = static_cast<char>(mask
^ bittab
[n
]);
593 case '*': /* match 0 or more... */
594 case '+': /* match 1 or more... */
596 return badpat("Empty closure");
597 lp
= sp
; /* previous opcode */
598 if (*lp
== CLO
) /* equivalence... */
608 return badpat("Illegal closure");
614 for (sp
= mp
; lp
< sp
; lp
++)
626 case '\\': /* tags, backrefs... */
634 return badpat("Null pattern inside \\<\\>");
647 if (tagi
> 0 && tagstk
[tagi
] == n
)
648 return badpat("Cyclical reference");
650 *mp
++ = static_cast<char>(REF
);
651 *mp
++ = static_cast<char>(n
);
653 return badpat("Undetermined reference");
656 if (!posix
&& *p
== '(') {
658 tagstk
[++tagi
] = tagc
;
660 *mp
++ = static_cast<char>(tagc
++);
662 return badpat("Too many \\(\\) pairs");
663 } else if (!posix
&& *p
== ')') {
665 return badpat("Null pattern inside \\(\\)");
667 *mp
++ = static_cast<char>(EOT
);
668 *mp
++ = static_cast<char>(tagstk
[tagi
--]);
670 return badpat("Unmatched \\)");
673 int c
= GetBackslashExpression(p
, incr
);
678 *mp
++ = static_cast<unsigned char>(c
);
682 for (n
= 0; n
< BITBLK
; bittab
[n
++] = 0)
683 *mp
++ = static_cast<char>(mask
^ bittab
[n
]);
689 default : /* an ordinary char */
690 if (posix
&& *p
== '(') {
692 tagstk
[++tagi
] = tagc
;
694 *mp
++ = static_cast<char>(tagc
++);
696 return badpat("Too many () pairs");
697 } else if (posix
&& *p
== ')') {
699 return badpat("Null pattern inside ()");
701 *mp
++ = static_cast<char>(EOT
);
702 *mp
++ = static_cast<char>(tagstk
[tagi
--]);
704 return badpat("Unmatched )");
706 unsigned char c
= *p
;
708 c
= '\\'; // We take it as raw backslash
709 if (caseSensitive
|| !iswordc(c
)) {
715 ChSetWithCase(c
, false);
716 for (n
= 0; n
< BITBLK
; bittab
[n
++] = 0)
717 *mp
++ = static_cast<char>(mask
^ bittab
[n
]);
725 return badpat((posix
? "Unmatched (" : "Unmatched \\("));
733 * execute nfa to find a match.
735 * special cases: (nfa[0])
737 * Match only once, starting from the
740 * First locate the character without
741 * calling PMatch, and if found, call
742 * PMatch for the remaining string.
744 * RESearch::Compile failed, poor luser did not
745 * check for it. Fail fast.
747 * If a match is found, bopat[0] and eopat[0] are set
748 * to the beginning and the end of the matched fragment,
752 int RESearch::Execute(CharacterIndexer
&ci
, int lp
, int endp
) {
764 case BOL
: /* anchored: match from BOL only */
765 ep
= PMatch(ci
, lp
, endp
, ap
);
767 case EOL
: /* just searching for end of line normal path doesn't work */
768 if (*(ap
+1) == END
) {
775 case CHR
: /* ordinary char: locate it fast */
777 while ((lp
< endp
) && (ci
.CharAt(lp
) != c
))
779 if (lp
>= endp
) /* if EOS, fail, else fall thru. */
781 default: /* regular matching all the way. */
783 ep
= PMatch(ci
, lp
, endp
, ap
);
789 case END
: /* munged automaton. fail always */
801 * PMatch: internal routine for the hard part
803 * This code is partly snarfed from an early grep written by
804 * David Conroy. The backref and tag stuff, and various other
805 * innovations are by oz.
807 * special case optimizations: (nfa[n], nfa[n+1])
809 * We KNOW .* will match everything upto the
810 * end of line. Thus, directly go to the end of
811 * line, without recursive PMatch calls. As in
812 * the other closure cases, the remaining pattern
813 * must be matched by moving backwards on the
814 * string recursively, to find a match for xy
815 * (x is ".*" and y is the remaining pattern)
816 * where the match satisfies the LONGEST match for
817 * x followed by a match for y.
819 * We can again scan the string forward for the
820 * single char and at the point of failure, we
821 * execute the remaining nfa recursively, same as
824 * At the end of a successful match, bopat[n] and eopat[n]
825 * are set to the beginning and end of subpatterns matched
826 * by tagged expressions (n = 1 to 9).
829 extern void re_fail(char *,char);
831 #define isinset(x,y) ((x)[((y)&BLKIND)>>3] & bitarr[(y)&BITIND])
834 * skip values for CLO XXX to skip past the closure
837 #define ANYSKIP 2 /* [CLO] ANY END */
838 #define CHRSKIP 3 /* [CLO] CHR chr END */
839 #define CCLSKIP 34 /* [CLO] CCL 32 bytes END */
841 int RESearch::PMatch(CharacterIndexer
&ci
, int lp
, int endp
, char *ap
) {
843 int e
; /* extra pointer for CLO */
844 int bp
; /* beginning of subpat... */
845 int ep
; /* ending of subpat... */
846 int are
; /* to save the line ptr. */
848 while ((op
= *ap
++) != END
)
852 if (ci
.CharAt(lp
++) != *ap
++)
882 if ((lp
!=bol
&& iswordc(ci
.CharAt(lp
-1))) || !iswordc(ci
.CharAt(lp
)))
886 if (lp
==bol
|| !iswordc(ci
.CharAt(lp
-1)) || iswordc(ci
.CharAt(lp
)))
894 if (ci
.CharAt(bp
++) != ci
.CharAt(lp
++))
908 while ((lp
< endp
) && (c
== ci
.CharAt(lp
)))
913 while ((lp
< endp
) && isinset(ap
+1,ci
.CharAt(lp
)))
919 //re_fail("closure: bad nfa.", *ap);
926 if ((e
= PMatch(ci
, lp
, endp
, ap
)) != NOTFOUND
)
932 //re_fail("RESearch::Execute: bad nfa.", static_cast<char>(op));
939 * RESearch::Substitute:
940 * substitute the matched portions of the src in dst.
942 * & substitute the entire matched pattern.
944 * \digit substitute a subpattern, with the given tag number.
945 * Tags are numbered from 1 to 9. If the particular
946 * tagged subpattern does not exist, null is substituted.
948 int RESearch::Substitute(CharacterIndexer
&ci
, char *src
, char *dst
) {
954 if (!*src
|| !bopat
[0])
957 while ((c
= *src
++) != 0) {
966 if (c
>= '0' && c
<= '9') {
976 if ((bp
= bopat
[pin
]) != 0 && (ep
= eopat
[pin
]) != 0) {
977 while (ci
.CharAt(bp
) && bp
< ep
)
978 *dst
++ = ci
.CharAt(bp
++);