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 ...
201
#include "CharClassify.h"
202
#include "RESearch.h"
204
// Shut up annoying Visual C++ warnings:
206
#pragma warning(disable: 4514)
210
using namespace Scintilla;
231
* The following defines are not meant to be changeable.
232
* They are for readability only.
237
const char bitarr[] = { 1, 2, 4, 8, 16, 32, 64, '\200' };
239
#define badpat(x) (*nfa = END, x)
242
* Character classification table for word boundary operators BOW
243
* and EOW is passed in by the creator of this object (Scintilla
244
* Document). The Document default state is that word chars are:
245
* 0-9, a-z, A-Z and _
248
RESearch::RESearch(CharClassify *charClassTable) {
249
charClass = charClassTable;
253
RESearch::~RESearch() {
257
void RESearch::Init() {
258
sta = NOP; /* status of lastpat */
260
for (int i = 0; i < MAXTAG; i++)
262
for (int j = 0; j < BITBLK; j++)
266
void RESearch::Clear() {
267
for (int i = 0; i < MAXTAG; i++) {
275
bool RESearch::GrabMatches(CharacterIndexer &ci) {
277
for (unsigned int i = 0; i < MAXTAG; i++) {
278
if ((bopat[i] != NOTFOUND) && (eopat[i] != NOTFOUND)) {
279
unsigned int len = eopat[i] - bopat[i];
280
pat[i] = new char[len + 1];
282
for (unsigned int j = 0; j < len; j++)
283
pat[i][j] = ci.CharAt(bopat[i] + j);
293
void RESearch::ChSet(unsigned char c) {
294
bittab[((c) & BLKIND) >> 3] |= bitarr[(c) & BITIND];
297
void RESearch::ChSetWithCase(unsigned char c, bool caseSensitive) {
301
if ((c >= 'a') && (c <= 'z')) {
303
ChSet(static_cast<unsigned char>(c - 'a' + 'A'));
304
} else if ((c >= 'A') && (c <= 'Z')) {
306
ChSet(static_cast<unsigned char>(c - 'A' + 'a'));
313
const unsigned char escapeValue(unsigned char ch) {
315
case 'a': return '\a';
316
case 'b': return '\b';
317
case 'f': return '\f';
318
case 'n': return '\n';
319
case 'r': return '\r';
320
case 't': return '\t';
321
case 'v': return '\v';
326
static int GetHexaChar(unsigned char hd1, unsigned char hd2) {
328
if (hd1 >= '0' && hd1 <= '9') {
329
hexValue += 16 * (hd1 - '0');
330
} else if (hd1 >= 'A' && hd1 <= 'F') {
331
hexValue += 16 * (hd1 - 'A' + 10);
332
} else if (hd1 >= 'a' && hd1 <= 'f') {
333
hexValue += 16 * (hd1 - 'a' + 10);
336
if (hd2 >= '0' && hd2 <= '9') {
337
hexValue += hd2 - '0';
338
} else if (hd2 >= 'A' && hd2 <= 'F') {
339
hexValue += hd2 - 'A' + 10;
340
} else if (hd2 >= 'a' && hd2 <= 'f') {
341
hexValue += hd2 - 'a' + 10;
348
* Called when the parser finds a backslash not followed
349
* by a valid expression (like \( in non-Posix mode).
350
* @param pattern: pointer on the char after the backslash.
351
* @param incr: (out) number of chars to skip after expression evaluation.
352
* @return the char if it resolves to a simple char,
353
* or -1 for a char class. In this case, bittab is changed.
355
int RESearch::GetBackslashExpression(
358
// Since error reporting is primitive and messages are not used anyway,
359
// I choose to interpret unexpected syntax in a logical way instead
360
// of reporting errors. Otherwise, we can stick on, eg., PCRE behavior.
361
incr = 0; // Most of the time, will skip the char "naturally".
364
unsigned char bsc = *pattern;
367
result = '\\'; // \ at end of pattern, take it literally
379
result = escapeValue(bsc);
382
unsigned char hd1 = *(pattern + 1);
383
unsigned char hd2 = *(pattern + 2);
384
int hexValue = GetHexaChar(hd1, hd2);
387
incr = 2; // Must skip the digits
389
result = 'x'; // \x without 2 digits: see it as 'x'
394
for (c = '0'; c <= '9'; c++) {
395
ChSet(static_cast<unsigned char>(c));
399
for (c = 0; c < MAXCHR; c++) {
400
if (c < '0' || c > '9') {
401
ChSet(static_cast<unsigned char>(c));
414
for (c = 0; c < MAXCHR; c++) {
415
if (c != ' ' && !(c >= 0x09 && c <= 0x0D)) {
416
ChSet(static_cast<unsigned char>(c));
420
for (c = 0; c < MAXCHR; c++) {
421
if (iswordc(static_cast<unsigned char>(c))) {
422
ChSet(static_cast<unsigned char>(c));
427
for (c = 0; c < MAXCHR; c++) {
428
if (!iswordc(static_cast<unsigned char>(c))) {
429
ChSet(static_cast<unsigned char>(c));
439
const char *RESearch::Compile(const char *pattern, int length, bool caseSensitive, bool posix) {
440
char *mp=nfa; /* nfa pointer */
441
char *lp; /* saved pointer */
442
char *sp=nfa; /* another one */
443
char *mpMax = mp + MAXNFA - BITBLK - 10;
445
int tagi = 0; /* tag stack index */
446
int tagc = 1; /* actual tag count */
449
char mask; /* xor mask -CCL/NCL */
450
int c1, c2, prevChar;
452
if (!pattern || !length)
456
return badpat("No previous regular expression");
459
const char *p=pattern; /* pattern pointer */
460
for (int i=0; i<length; i++, p++) {
462
return badpat("Pattern too long");
466
case '.': /* match any char */
470
case '^': /* match beginning */
479
case '$': /* match endofline */
488
case '[': /* match char class */
500
if (*p == '-') { /* real dash */
505
if (*p == ']') { /* real brace */
510
while (*p && *p != ']') {
513
// Previous def. was a char class like \d, take dash literally
522
if (!*(p+1)) // End of RE
523
return badpat("Missing ]");
528
c2 = GetBackslashExpression(p, incr);
532
// Convention: \c (c is any char) is case sensitive, whatever the option
533
ChSet(static_cast<unsigned char>(c2));
536
// bittab is already changed
542
// Char after dash is char class like \d, take dash literally
546
// Put all chars between c1 and c2 included in the char set
548
ChSetWithCase(static_cast<unsigned char>(c1++), caseSensitive);
552
// Dash before the ], take it literally
557
return badpat("Missing ]");
559
} else if (*p == '\\' && *(p+1)) {
563
int c = GetBackslashExpression(p, incr);
567
// Convention: \c (c is any char) is case sensitive, whatever the option
568
ChSet(static_cast<unsigned char>(c));
571
// bittab is already changed
576
ChSetWithCase(*p, caseSensitive);
582
return badpat("Missing ]");
584
for (n = 0; n < BITBLK; bittab[n++] = 0)
585
*mp++ = static_cast<char>(mask ^ bittab[n]);
589
case '*': /* match 0 or more... */
590
case '+': /* match 1 or more... */
592
return badpat("Empty closure");
593
lp = sp; /* previous opcode */
594
if (*lp == CLO) /* equivalence... */
604
return badpat("Illegal closure");
610
for (sp = mp; lp < sp; lp++)
622
case '\\': /* tags, backrefs... */
630
return badpat("Null pattern inside \\<\\>");
643
if (tagi > 0 && tagstk[tagi] == n)
644
return badpat("Cyclical reference");
646
*mp++ = static_cast<char>(REF);
647
*mp++ = static_cast<char>(n);
649
return badpat("Undetermined reference");
652
if (!posix && *p == '(') {
654
tagstk[++tagi] = tagc;
656
*mp++ = static_cast<char>(tagc++);
658
return badpat("Too many \\(\\) pairs");
659
} else if (!posix && *p == ')') {
661
return badpat("Null pattern inside \\(\\)");
663
*mp++ = static_cast<char>(EOT);
664
*mp++ = static_cast<char>(tagstk[tagi--]);
666
return badpat("Unmatched \\)");
669
int c = GetBackslashExpression(p, incr);
674
*mp++ = static_cast<unsigned char>(c);
678
for (n = 0; n < BITBLK; bittab[n++] = 0)
679
*mp++ = static_cast<char>(mask ^ bittab[n]);
685
default : /* an ordinary char */
686
if (posix && *p == '(') {
688
tagstk[++tagi] = tagc;
690
*mp++ = static_cast<char>(tagc++);
692
return badpat("Too many () pairs");
693
} else if (posix && *p == ')') {
695
return badpat("Null pattern inside ()");
697
*mp++ = static_cast<char>(EOT);
698
*mp++ = static_cast<char>(tagstk[tagi--]);
700
return badpat("Unmatched )");
702
unsigned char c = *p;
704
c = '\\'; // We take it as raw backslash
705
if (caseSensitive || !iswordc(c)) {
711
ChSetWithCase(c, false);
712
for (n = 0; n < BITBLK; bittab[n++] = 0)
713
*mp++ = static_cast<char>(mask ^ bittab[n]);
721
return badpat((posix ? "Unmatched (" : "Unmatched \\("));
729
* execute nfa to find a match.
731
* special cases: (nfa[0])
733
* Match only once, starting from the
736
* First locate the character without
737
* calling PMatch, and if found, call
738
* PMatch for the remaining string.
740
* RESearch::Compile failed, poor luser did not
741
* check for it. Fail fast.
743
* If a match is found, bopat[0] and eopat[0] are set
744
* to the beginning and the end of the matched fragment,
748
int RESearch::Execute(CharacterIndexer &ci, int lp, int endp) {
760
case BOL: /* anchored: match from BOL only */
761
ep = PMatch(ci, lp, endp, ap);
763
case EOL: /* just searching for end of line normal path doesn't work */
764
if (*(ap+1) == END) {
771
case CHR: /* ordinary char: locate it fast */
773
while ((lp < endp) && (ci.CharAt(lp) != c))
775
if (lp >= endp) /* if EOS, fail, else fall thru. */
777
default: /* regular matching all the way. */
779
ep = PMatch(ci, lp, endp, ap);
785
case END: /* munged automaton. fail always */
797
* PMatch: internal routine for the hard part
799
* This code is partly snarfed from an early grep written by
800
* David Conroy. The backref and tag stuff, and various other
801
* innovations are by oz.
803
* special case optimizations: (nfa[n], nfa[n+1])
805
* We KNOW .* will match everything upto the
806
* end of line. Thus, directly go to the end of
807
* line, without recursive PMatch calls. As in
808
* the other closure cases, the remaining pattern
809
* must be matched by moving backwards on the
810
* string recursively, to find a match for xy
811
* (x is ".*" and y is the remaining pattern)
812
* where the match satisfies the LONGEST match for
813
* x followed by a match for y.
815
* We can again scan the string forward for the
816
* single char and at the point of failure, we
817
* execute the remaining nfa recursively, same as
820
* At the end of a successful match, bopat[n] and eopat[n]
821
* are set to the beginning and end of subpatterns matched
822
* by tagged expressions (n = 1 to 9).
825
extern void re_fail(char *,char);
827
#define isinset(x,y) ((x)[((y)&BLKIND)>>3] & bitarr[(y)&BITIND])
830
* skip values for CLO XXX to skip past the closure
833
#define ANYSKIP 2 /* [CLO] ANY END */
834
#define CHRSKIP 3 /* [CLO] CHR chr END */
835
#define CCLSKIP 34 /* [CLO] CCL 32 bytes END */
837
int RESearch::PMatch(CharacterIndexer &ci, int lp, int endp, char *ap) {
839
int e; /* extra pointer for CLO */
840
int bp; /* beginning of subpat... */
841
int ep; /* ending of subpat... */
842
int are; /* to save the line ptr. */
844
while ((op = *ap++) != END)
848
if (ci.CharAt(lp++) != *ap++)
878
if (lp!=bol && iswordc(ci.CharAt(lp-1)) || !iswordc(ci.CharAt(lp)))
882
if (lp==bol || !iswordc(ci.CharAt(lp-1)) || iswordc(ci.CharAt(lp)))
890
if (ci.CharAt(bp++) != ci.CharAt(lp++))
904
while ((lp < endp) && (c == ci.CharAt(lp)))
909
while ((lp < endp) && isinset(ap+1,ci.CharAt(lp)))
915
//re_fail("closure: bad nfa.", *ap);
922
if ((e = PMatch(ci, lp, endp, ap)) != NOTFOUND)
928
//re_fail("RESearch::Execute: bad nfa.", static_cast<char>(op));
935
* RESearch::Substitute:
936
* substitute the matched portions of the src in dst.
938
* & substitute the entire matched pattern.
940
* \digit substitute a subpattern, with the given tag number.
941
* Tags are numbered from 1 to 9. If the particular
942
* tagged subpattern does not exist, null is substituted.
944
int RESearch::Substitute(CharacterIndexer &ci, char *src, char *dst) {
950
if (!*src || !bopat[0])
953
while ((c = *src++) != 0) {
962
if (c >= '0' && c <= '9') {
972
if ((bp = bopat[pin]) != 0 && (ep = eopat[pin]) != 0) {
973
while (ci.CharAt(bp) && bp < ep)
974
*dst++ = ci.CharAt(bp++);
added
removed
src/qscintilla2/src/RESearch.cpp
