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
20 * '?' extensions by Michael Mullin masmullin@gmail.com
22 * These routines are the PUBLIC DOMAIN equivalents of regex
23 * routines as found in 4.nBSD UN*X, with minor extensions.
25 * These routines are derived from various implementations found
26 * in software tools books, and Conroy's grep. They are NOT derived
27 * from licensed/restricted software.
28 * For more interesting/academic/complicated implementations,
29 * see Henry Spencer's regexp routines, or GNU Emacs pattern
32 * Modification history removed.
35 * RESearch::Compile: compile a regular expression into a NFA.
37 * const char *RESearch::Compile(const char *pattern, int length,
38 * bool caseSensitive, bool posix)
40 * Returns a short error string if they fail.
42 * RESearch::Execute: execute the NFA to match a pattern.
44 * int RESearch::Execute(characterIndexer &ci, int lp, int endp)
46 * re_fail: failure routine for RESearch::Execute. (no longer used)
48 * void re_fail(char *msg, char op)
50 * Regular Expressions:
52 * [1] char matches itself, unless it is a special
53 * character (metachar): . \ [ ] * + ? ^ $
54 * and ( ) if posix option.
56 * [2] . matches any character.
58 * [3] \ matches the character following it, except:
59 * - \a, \b, \f, \n, \r, \t, \v match the corresponding C
60 * escape char, respectively BEL, BS, FF, LF, CR, TAB and VT;
61 * Note that \r and \n are never matched because Scintilla
62 * regex searches are made line per line
63 * (stripped of end-of-line chars).
64 * - if not in posix mode, when followed by a
65 * left or right round bracket (see [8]);
66 * - when followed by a digit 1 to 9 (see [9]);
67 * - when followed by a left or right angle bracket
69 * - when followed by d, D, s, S, w or W (see [11]);
70 * - when followed by x and two hexa digits (see [12].
71 * Backslash is used as an escape character for all
72 * other meta-characters, and itself.
74 * [4] [set] matches one of the characters in the set.
75 * If the first character in the set is "^",
76 * it matches the characters NOT in the set, i.e.
77 * complements the set. A shorthand S-E (start dash end)
78 * is used to specify a set of characters S up to
79 * E, inclusive. S and E must be characters, otherwise
80 * the dash is taken literally (eg. in expression [\d-a]).
81 * The special characters "]" and "-" have no special
82 * meaning if they appear as the first chars in the set.
83 * To include both, put - first: [-]A-Z]
84 * (or just backslash them).
87 * [-]|] matches these 3 chars,
89 * []-|] matches from ] to | chars
91 * [a-z] any lowercase alpha
93 * [^-]] any char except - and ]
95 * [^A-Z] any char except uppercase
100 * [5] * any regular expression form [1] to [4]
101 * (except [8], [9] and [10] forms of [3]),
102 * followed by closure char (*)
103 * matches zero or more matches of that form.
105 * [6] + same as [5], except it matches one or more.
107 * [5-6] Both [5] and [6] are greedy (they match as much as possible).
108 * Unless they are followed by the 'lazy' quantifier (?)
109 * In which case both [5] and [6] try to match as little as possible
111 * [7] ? same as [5] except it matches zero or one.
113 * [8] a regular expression in the form [1] to [13], enclosed
114 * as \(form\) (or (form) with posix flag) matches what
115 * form matches. The enclosure creates a set of tags,
116 * used for [9] and for pattern substitution.
117 * The tagged forms are numbered starting from 1.
119 * [9] a \ followed by a digit 1 to 9 matches whatever a
120 * previously tagged regular expression ([8]) matched.
122 * [10] \< a regular expression starting with a \< construct
123 * \> and/or ending with a \> construct, restricts the
124 * pattern matching to the beginning of a word, and/or
125 * the end of a word. A word is defined to be a character
126 * string beginning and/or ending with the characters
127 * A-Z a-z 0-9 and _. Scintilla extends this definition
128 * by user setting. The word must also be preceded and/or
129 * followed by any character outside those mentioned.
131 * [11] \l a backslash followed by d, D, s, S, w or W,
132 * becomes a character class (both inside and
135 * D: any char except decimal digits
136 * s: whitespace (space, \t \n \r \f \v)
137 * S: any char except whitespace (see above)
138 * w: alphanumeric & underscore (changed by user setting)
139 * W: any char except alphanumeric & underscore (see above)
141 * [12] \xHH a backslash followed by x and two hexa digits,
142 * becomes the character whose ASCII code is equal
143 * to these digits. If not followed by two digits,
144 * it is 'x' char itself.
146 * [13] a composite regular expression xy where x and y
147 * are in the form [1] to [12] matches the longest
148 * match of x followed by a match for y.
150 * [14] ^ a regular expression starting with a ^ character
151 * $ and/or ending with a $ character, restricts the
152 * pattern matching to the beginning of the line,
153 * or the end of line. [anchors] Elsewhere in the
154 * pattern, ^ and $ are treated as ordinary characters.
159 * HCR's Hugh Redelmeier has been most helpful in various
160 * stages of development. He convinced me to include BOW
161 * and EOW constructs, originally invented by Rob Pike at
162 * the University of Toronto.
165 * Software tools Kernighan & Plauger
166 * Software tools in Pascal Kernighan & Plauger
167 * Grep [rsx-11 C dist] David Conroy
168 * ed - text editor Un*x Programmer's Manual
169 * Advanced editing on Un*x B. W. Kernighan
170 * RegExp routines Henry Spencer
174 * This implementation uses a bit-set representation for character
175 * classes for speed and compactness. Each character is represented
176 * by one bit in a 256-bit block. Thus, CCL always takes a
177 * constant 32 bytes in the internal nfa, and RESearch::Execute does a single
178 * bit comparison to locate the character in the set.
183 * compile: CHR f CHR o CLO CHR o END CLO ANY END END
184 * matches: fo foo fooo foobar fobar foxx ...
186 * pattern: fo[ob]a[rz]
187 * compile: CHR f CHR o CCL bitset CHR a CCL bitset END
188 * matches: fobar fooar fobaz fooaz
191 * compile: CHR f CHR o CHR o CHR \ CLO CHR \ END END
192 * matches: foo\ foo\\ foo\\\ ...
194 * pattern: \(foo\)[1-3]\1 (same as foo[1-3]foo)
195 * compile: BOT 1 CHR f CHR o CHR o EOT 1 CCL bitset REF 1 END
196 * matches: foo1foo foo2foo foo3foo
198 * pattern: \(fo.*\)-\1
199 * compile: BOT 1 CHR f CHR o CLO ANY END EOT 1 CHR - REF 1 END
200 * matches: foo-foo fo-fo fob-fob foobar-foobar ...
212 #include "Position.h"
213 #include "CharClassify.h"
214 #include "RESearch.h"
216 using namespace Scintilla::Internal
;
232 #define CLQ 12 /* 0 to 1 closure */
233 #define LCLO 13 /* lazy closure */
238 * The following defines are not meant to be changeable.
239 * They are for readability only.
243 #define badpat(x) (*nfa = END, x)
246 * Character classification table for word boundary operators BOW
247 * and EOW is passed in by the creator of this object (Scintilla
248 * Document). The Document default state is that word chars are:
249 * 0-9, a-z, A-Z and _
252 RESearch::RESearch(CharClassify
*charClassTable
) {
254 charClass
= charClassTable
;
255 sta
= NOP
; /* status of lastpat */
262 void RESearch::Clear() {
263 bopat
.fill(NOTFOUND
);
264 eopat
.fill(NOTFOUND
);
267 void RESearch::ChSet(unsigned char c
) noexcept
{
268 bittab
[c
>> 3] |= 1 << (c
& BITIND
);
271 void RESearch::ChSetWithCase(unsigned char c
, bool caseSensitive
) noexcept
{
273 if (!caseSensitive
) {
274 if ((c
>= 'a') && (c
<= 'z')) {
275 ChSet(c
- 'a' + 'A');
276 } else if ((c
>= 'A') && (c
<= 'Z')) {
277 ChSet(c
- 'A' + 'a');
284 constexpr unsigned char escapeValue(unsigned char ch
) noexcept
{
286 case 'a': return '\a';
287 case 'b': return '\b';
288 case 'f': return '\f';
289 case 'n': return '\n';
290 case 'r': return '\r';
291 case 't': return '\t';
292 case 'v': return '\v';
298 constexpr int GetHexaChar(unsigned char hd1
, unsigned char hd2
) noexcept
{
300 if (hd1
>= '0' && hd1
<= '9') {
301 hexValue
+= 16 * (hd1
- '0');
302 } else if (hd1
>= 'A' && hd1
<= 'F') {
303 hexValue
+= 16 * (hd1
- 'A' + 10);
304 } else if (hd1
>= 'a' && hd1
<= 'f') {
305 hexValue
+= 16 * (hd1
- 'a' + 10);
309 if (hd2
>= '0' && hd2
<= '9') {
310 hexValue
+= hd2
- '0';
311 } else if (hd2
>= 'A' && hd2
<= 'F') {
312 hexValue
+= hd2
- 'A' + 10;
313 } else if (hd2
>= 'a' && hd2
<= 'f') {
314 hexValue
+= hd2
- 'a' + 10;
321 constexpr int isinset(const char *ap
, unsigned char c
) noexcept
{
322 return ap
[c
>> 3] & (1 << (c
& BITIND
));
328 * Called when the parser finds a backslash not followed
329 * by a valid expression (like \( in non-Posix mode).
330 * @param pattern : pointer on the char after the backslash.
331 * @param incr : (out) number of chars to skip after expression evaluation.
332 * @return the char if it resolves to a simple char,
333 * or -1 for a char class. In this case, bittab is changed.
335 int RESearch::GetBackslashExpression(const char *pattern
, int &incr
) noexcept
{
336 // Since error reporting is primitive and messages are not used anyway,
337 // I choose to interpret unexpected syntax in a logical way instead
338 // of reporting errors. Otherwise, we can stick on, eg., PCRE behaviour.
339 incr
= 0; // Most of the time, will skip the char "naturally".
341 const unsigned char bsc
= *pattern
;
344 result
= '\\'; // \ at end of pattern, take it literally
356 result
= escapeValue(bsc
);
359 const unsigned char hd1
= *(pattern
+ 1);
360 const unsigned char hd2
= *(pattern
+ 2);
361 const int hexValue
= GetHexaChar(hd1
, hd2
);
364 incr
= 2; // Must skip the digits
366 result
= 'x'; // \x without 2 digits: see it as 'x'
371 for (int c
= '0'; c
<= '9'; c
++) {
372 ChSet(static_cast<unsigned char>(c
));
376 for (int c
= 0; c
< MAXCHR
; c
++) {
377 if (c
< '0' || c
> '9') {
378 ChSet(static_cast<unsigned char>(c
));
391 for (int c
= 0; c
< MAXCHR
; c
++) {
392 if (c
!= ' ' && !(c
>= 0x09 && c
<= 0x0D)) {
393 ChSet(static_cast<unsigned char>(c
));
398 for (int c
= 0; c
< MAXCHR
; c
++) {
399 if (iswordc(static_cast<unsigned char>(c
))) {
400 ChSet(static_cast<unsigned char>(c
));
405 for (int c
= 0; c
< MAXCHR
; c
++) {
406 if (!iswordc(static_cast<unsigned char>(c
))) {
407 ChSet(static_cast<unsigned char>(c
));
417 const char *RESearch::Compile(const char *pattern
, Sci::Position length
, bool caseSensitive
, bool posix
) {
418 if (!pattern
|| !length
) {
422 return badpat("No previous regular expression");
428 char *mp
=nfa
; /* nfa pointer */
429 char *sp
=nfa
; /* another saved pointer */
430 const char * const mpMax
= mp
+ MAXNFA
- BITBLK
- 10;
432 int tagstk
[MAXTAG
]{}; /* subpat tag stack */
433 int tagi
= 0; /* tag stack index */
434 int tagc
= 1; /* actual tag count */
438 const char *p
=pattern
; /* pattern pointer */
439 for (int i
=0; i
<length
; i
++, p
++) {
441 return badpat("Pattern too long");
442 char *lp
= mp
; /* saved pointer */
445 case '.': /* match any char */
449 case '^': /* match beginning */
458 case '$': /* match endofline */
467 case '[': { /* match char class */
469 char mask
= 0; /* xor mask -CCL/NCL */
478 if (*p
== '-') { /* real dash */
483 if (*p
== ']') { /* real brace */
488 while (*p
&& *p
!= ']') {
491 // Previous def. was a char class like \d, take dash literally
496 int c1
= prevChar
+ 1;
498 int c2
= static_cast<unsigned char>(*++p
);
500 if (!p
[1]) { // End of RE
501 return badpat("Missing ]");
506 c2
= GetBackslashExpression(p
, incr
);
510 // Convention: \c (c is any char) is case sensitive, whatever the option
511 ChSet(static_cast<unsigned char>(c2
));
514 // bittab is already changed
520 // Char after dash is char class like \d, take dash literally
524 // Put all chars between c1 and c2 included in the char set
526 ChSetWithCase(static_cast<unsigned char>(c1
++), caseSensitive
);
530 // Dash before the ], take it literally
535 return badpat("Missing ]");
537 } else if (*p
== '\\' && p
[1]) {
541 const int c
= GetBackslashExpression(p
, incr
);
545 // Convention: \c (c is any char) is case sensitive, whatever the option
546 ChSet(static_cast<unsigned char>(c
));
549 // bittab is already changed
553 prevChar
= static_cast<unsigned char>(*p
);
554 ChSetWithCase(*p
, caseSensitive
);
560 return badpat("Missing ]");
563 for (const unsigned char byte
: bittab
) {
569 case '*': /* match 0 or more... */
570 case '+': /* match 1 or more... */
573 return badpat("Empty closure");
574 lp
= sp
; /* previous opcode */
575 if (*lp
== CLO
|| *lp
== LCLO
) /* equivalence... */
585 return badpat("Illegal closure");
591 for (sp
= mp
; lp
< sp
; lp
++)
600 if (*p
== '?') *mp
= CLQ
;
601 else if (p
[1] == '?') *mp
= LCLO
;
607 case '\\': /* tags, backrefs... */
615 return badpat("Null pattern inside \\<\\>");
627 const int n
= *p
-'0';
628 if (tagi
> 0 && tagstk
[tagi
] == n
)
629 return badpat("Cyclical reference");
632 *mp
++ = static_cast<char>(n
);
634 return badpat("Undetermined reference");
638 if (!posix
&& *p
== '(') {
640 tagstk
[++tagi
] = tagc
;
642 *mp
++ = static_cast<char>(tagc
++);
644 return badpat("Too many \\(\\) pairs");
646 } else if (!posix
&& *p
== ')') {
648 return badpat("Null pattern inside \\(\\)");
651 *mp
++ = static_cast<char>(tagstk
[tagi
--]);
653 return badpat("Unmatched \\)");
657 const int c
= GetBackslashExpression(p
, incr
);
662 *mp
++ = static_cast<unsigned char>(c
);
665 for (const unsigned char byte
: bittab
) {
674 default : /* an ordinary char */
675 if (posix
&& *p
== '(') {
677 tagstk
[++tagi
] = tagc
;
679 *mp
++ = static_cast<char>(tagc
++);
681 return badpat("Too many () pairs");
683 } else if (posix
&& *p
== ')') {
685 return badpat("Null pattern inside ()");
688 *mp
++ = static_cast<char>(tagstk
[tagi
--]);
690 return badpat("Unmatched )");
693 unsigned char c
= *p
;
695 c
= '\\'; // We take it as raw backslash
696 if (caseSensitive
|| !iswordc(c
)) {
700 ChSetWithCase(c
, false);
702 for (const unsigned char byte
: bittab
) {
713 return badpat((posix
? "Unmatched (" : "Unmatched \\("));
721 * execute nfa to find a match.
723 * special cases: (nfa[0])
725 * Match only once, starting from the
728 * First locate the character without
729 * calling PMatch, and if found, call
730 * PMatch for the remaining string.
732 * RESearch::Compile failed, poor luser did not
733 * check for it. Fail fast.
735 * If a match is found, bopat[0] and eopat[0] are set
736 * to the beginning and the end of the matched fragment,
740 int RESearch::Execute(const CharacterIndexer
&ci
, Sci::Position lp
, Sci::Position endp
) {
741 Sci::Position ep
= NOTFOUND
;
742 const char * const ap
= nfa
;
750 case BOL
: /* anchored: match from BOL only */
751 ep
= PMatch(ci
, lp
, endp
, ap
);
753 case EOL
: /* just searching for end of line normal path doesn't work */
754 if (endp
== lineEndPos
&& ap
[1] == END
) {
761 case CHR
: { /* ordinary char: locate it fast */
762 const unsigned char c
= ap
[1];
763 while ((lp
< endp
) && (static_cast<unsigned char>(ci
.CharAt(lp
)) != c
))
765 if (lp
>= endp
) /* if EOS, fail, else fall through. */
769 default: /* regular matching all the way. */
771 ep
= PMatch(ci
, lp
, endp
, ap
);
772 if (ep
!= NOTFOUND
) {
773 // fix match started from middle of character like DBCS trailing ASCII byte
774 const Sci::Position pos
= ci
.MovePositionOutsideChar(lp
, -1);
784 case END
: /* munged automaton. fail always */
787 if (ep
== NOTFOUND
) {
788 /* similar to EOL, match EOW at line end */
789 if (endp
== lineEndPos
&& *ap
== EOW
) {
790 if ((ap
[1] == END
|| ((ap
[1] == EOL
&& ap
[2] == END
))) && iswordc(ci
.CharAt(lp
- 1))) {
801 ep
= ci
.MovePositionOutsideChar(ep
, 1);
808 * PMatch: internal routine for the hard part
810 * This code is partly snarfed from an early grep written by
811 * David Conroy. The backref and tag stuff, and various other
812 * innovations are by oz.
814 * special case optimizations: (nfa[n], nfa[n+1])
816 * We KNOW .* will match everything up to the
817 * end of line. Thus, directly go to the end of
818 * line, without recursive PMatch calls. As in
819 * the other closure cases, the remaining pattern
820 * must be matched by moving backwards on the
821 * string recursively, to find a match for xy
822 * (x is ".*" and y is the remaining pattern)
823 * where the match satisfies the LONGEST match for
824 * x followed by a match for y.
826 * We can again scan the string forward for the
827 * single char and at the point of failure, we
828 * execute the remaining nfa recursively, same as
831 * At the end of a successful match, bopat[n] and eopat[n]
832 * are set to the beginning and end of subpatterns matched
833 * by tagged expressions (n = 1 to 9).
836 //extern void re_fail(char *,char);
839 * skip values for CLO XXX to skip past the closure
842 #define ANYSKIP 2 /* [CLO] ANY END */
843 #define CHRSKIP 3 /* [CLO] CHR chr END */
844 #define CCLSKIP 34 /* [CLO] CCL 32 bytes END */
846 Sci::Position
RESearch::PMatch(const CharacterIndexer
&ci
, Sci::Position lp
, Sci::Position endp
, const char *ap
) {
847 unsigned char op
= 0;
849 while ((op
= *ap
++) != END
)
853 if (ci
.CharAt(lp
++) != *ap
++)
863 if (!isinset(ap
, ci
.CharAt(lp
++)))
868 if (lp
!= lineStartPos
)
876 if (lp
!= ci
.MovePositionOutsideChar(lp
, -1)) {
879 bopat
[static_cast<unsigned char>(*ap
++)] = lp
;
882 lp
= ci
.MovePositionOutsideChar(lp
, 1);
883 eopat
[static_cast<unsigned char>(*ap
++)] = lp
;
886 if ((lp
!=lineStartPos
&& iswordc(ci
.CharAt(lp
-1))) || !iswordc(ci
.CharAt(lp
)))
890 if (lp
==lineStartPos
|| !iswordc(ci
.CharAt(lp
-1)) || iswordc(ci
.CharAt(lp
)))
894 const int n
= static_cast<unsigned char>(*ap
++);
895 Sci::Position bp
= bopat
[n
]; /* beginning of subpat... */
896 const Sci::Position ep
= eopat
[n
]; /* ending of subpat... */
898 if (ci
.CharAt(bp
++) != ci
.CharAt(lp
++))
905 const Sci::Position are
= lp
; /* to save the line ptr. */
909 if (op
== CLO
|| op
== LCLO
)
918 const char c
= ap
[1];
919 if (op
== CLO
|| op
== LCLO
)
920 while ((lp
< endp
) && (c
== ci
.CharAt(lp
)))
922 else if ((lp
< endp
) && (c
== ci
.CharAt(lp
)))
927 while ((lp
< endp
) && isinset(ap
+1, ci
.CharAt(lp
)))
933 //re_fail("closure: bad nfa.", *ap);
938 Sci::Position llp
= lp
; /* lazy lp for LCLO */
939 Sci::Position e
= NOTFOUND
; /* extra pointer for CLO */
941 const Sci::Position q
= PMatch(ci
, llp
, endp
, ap
);
945 if (op
!= LCLO
) return e
;
947 if (*ap
== END
) return e
;
951 PMatch(ci
, lp
, endp
, ap
);
955 //re_fail("RESearch::Execute: bad nfa.", static_cast<char>(op));