1 // Scintilla source code edit control
2 /** @file RESearch.cxx
3 ** Regular expression search library.
4 **/
5
6 /*
7 * regex - Regular expression pattern matching and replacement
8 *
9 * By: Ozan S. Yigit (oz)
10 * Dept. of Computer Science
11 * York University
12 *
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
21 *
22 * These routines are the PUBLIC DOMAIN equivalents of regex
23 * routines as found in 4.nBSD UN*X, with minor extensions.
24 *
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
30 * matching module.
31 *
32 * Modification history removed.
33 *
34 * Interfaces:
35 * RESearch::Compile: compile a regular expression into a NFA.
36 *
37 * const char *RESearch::Compile(const char *pattern, int length,
38 * bool caseSensitive, bool posix)
39 *
40 * Returns a short error string if they fail.
41 *
42 * RESearch::Execute: execute the NFA to match a pattern.
43 *
44 * int RESearch::Execute(characterIndexer &ci, int lp, int endp)
45 *
46 * re_fail: failure routine for RESearch::Execute. (no longer used)
47 *
48 * void re_fail(char *msg, char op)
49 *
50 * Regular Expressions:
51 *
52 * [1] char matches itself, unless it is a special
53 * character (metachar): . \ [ ] * + ? ^ $
54 * and ( ) if posix option.
55 *
56 * [2] . matches any character.
57 *
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
68 * (see [10]);
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.
73 *
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).
85 * examples: match:
86 *
87 * [-]|] matches these 3 chars,
88 *
89 * []-|] matches from ] to | chars
90 *
91 * [a-z] any lowercase alpha
92 *
93 * [^-]] any char except - and ]
94 *
95 * [^A-Z] any char except uppercase
96 * alpha
97 *
98 * [a-zA-Z] any alpha
99 *
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.
104 *
105 * [6] + same as [5], except it matches one or more.
106 *
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
110 *
111 * [7] ? same as [5] except it matches zero or one.
112 *
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.
118 *
119 * [9] a \ followed by a digit 1 to 9 matches whatever a
120 * previously tagged regular expression ([8]) matched.
121 *
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.
130 *
131 * [11] \l a backslash followed by d, D, s, S, w or W,
132 * becomes a character class (both inside and
133 * outside sets []).
134 * d: decimal digits
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)
140 *
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.
145 *
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.
149 *
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.
155 *
156 *
157 * Acknowledgements:
158 *
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.
163 *
164 * References:
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
171 *
172 * Notes:
173 *
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.
179 *
180 * Examples:
181 *
182 * pattern: foo*.*
183 * compile: CHR f CHR o CLO CHR o END CLO ANY END END
184 * matches: fo foo fooo foobar fobar foxx ...
185 *
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
189 *
190 * pattern: foo\\+
191 * compile: CHR f CHR o CHR o CHR \ CLO CHR \ END END
192 * matches: foo\ foo\\ foo\\\ ...
193 *
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
197 *
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 ...
201 */
202
203 #include <stdlib.h>
204
205 #include <string>
206 #include <algorithm>
207
208 #include "CharClassify.h"
209 #include "RESearch.h"
210
211 #ifdef SCI_NAMESPACE
212 using namespace Scintilla;
213 #endif
214
215 #define OKP 1
216 #define NOP 0
217
218 #define CHR 1
219 #define ANY 2
220 #define CCL 3
221 #define BOL 4
222 #define EOL 5
223 #define BOT 6
224 #define EOT 7
225 #define BOW 8
226 #define EOW 9
227 #define REF 10
228 #define CLO 11
229 #define CLQ 12 /* 0 to 1 closure */
230 #define LCLO 13 /* lazy closure */
231
232 #define END 0
233
234 /*
235 * The following defines are not meant to be changeable.
236 * They are for readability only.
237 */
238 #define BLKIND 0370
239 #define BITIND 07
240
241 const char bitarr[] = { 1, 2, 4, 8, 16, 32, 64, '\200' };
242
243 #define badpat(x) (*nfa = END, x)
244
245 /*
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 _
250 */
251
RESearch(CharClassify * charClassTable)252 RESearch::RESearch(CharClassify *charClassTable) {
253 failure = 0;
254 charClass = charClassTable;
255 sta = NOP; /* status of lastpat */
256 bol = 0;
257 std::fill(bittab, bittab + BITBLK, 0);
258 std::fill(tagstk, tagstk + MAXTAG, 0);
259 std::fill(nfa, nfa + MAXNFA, 0);
260 Clear();
261 }
262
~RESearch()263 RESearch::~RESearch() {
264 Clear();
265 }
266
Clear()267 void RESearch::Clear() {
268 for (int i = 0; i < MAXTAG; i++) {
269 pat[i].clear();
270 bopat[i] = NOTFOUND;
271 eopat[i] = NOTFOUND;
272 }
273 }
274
GrabMatches(CharacterIndexer & ci)275 void RESearch::GrabMatches(CharacterIndexer &ci) {
276 for (unsigned int i = 0; i < MAXTAG; i++) {
277 if ((bopat[i] != NOTFOUND) && (eopat[i] != NOTFOUND)) {
278 unsigned int len = eopat[i] - bopat[i];
279 pat[i] = std::string(len+1, '\0');
280 for (unsigned int j = 0; j < len; j++)
281 pat[i][j] = ci.CharAt(bopat[i] + j);
282 pat[i][len] = '\0';
283 }
284 }
285 }
286
ChSet(unsigned char c)287 void RESearch::ChSet(unsigned char c) {
288 bittab[((c) & BLKIND) >> 3] |= bitarr[(c) & BITIND];
289 }
290
ChSetWithCase(unsigned char c,bool caseSensitive)291 void RESearch::ChSetWithCase(unsigned char c, bool caseSensitive) {
292 if (caseSensitive) {
293 ChSet(c);
294 } else {
295 if ((c >= 'a') && (c <= 'z')) {
296 ChSet(c);
297 ChSet(static_cast<unsigned char>(c - 'a' + 'A'));
298 } else if ((c >= 'A') && (c <= 'Z')) {
299 ChSet(c);
300 ChSet(static_cast<unsigned char>(c - 'A' + 'a'));
301 } else {
302 ChSet(c);
303 }
304 }
305 }
306
escapeValue(unsigned char ch)307 unsigned char escapeValue(unsigned char ch) {
308 switch (ch) {
309 case 'a': return '\a';
310 case 'b': return '\b';
311 case 'f': return '\f';
312 case 'n': return '\n';
313 case 'r': return '\r';
314 case 't': return '\t';
315 case 'v': return '\v';
316 }
317 return 0;
318 }
319
GetHexaChar(unsigned char hd1,unsigned char hd2)320 static int GetHexaChar(unsigned char hd1, unsigned char hd2) {
321 int hexValue = 0;
322 if (hd1 >= '0' && hd1 <= '9') {
323 hexValue += 16 * (hd1 - '0');
324 } else if (hd1 >= 'A' && hd1 <= 'F') {
325 hexValue += 16 * (hd1 - 'A' + 10);
326 } else if (hd1 >= 'a' && hd1 <= 'f') {
327 hexValue += 16 * (hd1 - 'a' + 10);
328 } else {
329 return -1;
330 }
331 if (hd2 >= '0' && hd2 <= '9') {
332 hexValue += hd2 - '0';
333 } else if (hd2 >= 'A' && hd2 <= 'F') {
334 hexValue += hd2 - 'A' + 10;
335 } else if (hd2 >= 'a' && hd2 <= 'f') {
336 hexValue += hd2 - 'a' + 10;
337 } else {
338 return -1;
339 }
340 return hexValue;
341 }
342
343 /**
344 * Called when the parser finds a backslash not followed
345 * by a valid expression (like \( in non-Posix mode).
346 * @param pattern: pointer on the char after the backslash.
347 * @param incr: (out) number of chars to skip after expression evaluation.
348 * @return the char if it resolves to a simple char,
349 * or -1 for a char class. In this case, bittab is changed.
350 */
GetBackslashExpression(const char * pattern,int & incr)351 int RESearch::GetBackslashExpression(
352 const char *pattern,
353 int &incr) {
354 // Since error reporting is primitive and messages are not used anyway,
355 // I choose to interpret unexpected syntax in a logical way instead
356 // of reporting errors. Otherwise, we can stick on, eg., PCRE behavior.
357 incr = 0; // Most of the time, will skip the char "naturally".
358 int c;
359 int result = -1;
360 unsigned char bsc = *pattern;
361 if (!bsc) {
362 // Avoid overrun
363 result = '\\'; // \ at end of pattern, take it literally
364 return result;
365 }
366
367 switch (bsc) {
368 case 'a':
369 case 'b':
370 case 'n':
371 case 'f':
372 case 'r':
373 case 't':
374 case 'v':
375 result = escapeValue(bsc);
376 break;
377 case 'x': {
378 unsigned char hd1 = *(pattern + 1);
379 unsigned char hd2 = *(pattern + 2);
380 int hexValue = GetHexaChar(hd1, hd2);
381 if (hexValue >= 0) {
382 result = hexValue;
383 incr = 2; // Must skip the digits
384 } else {
385 result = 'x'; // \x without 2 digits: see it as 'x'
386 }
387 }
388 break;
389 case 'd':
390 for (c = '0'; c <= '9'; c++) {
391 ChSet(static_cast<unsigned char>(c));
392 }
393 break;
394 case 'D':
395 for (c = 0; c < MAXCHR; c++) {
396 if (c < '0' || c > '9') {
397 ChSet(static_cast<unsigned char>(c));
398 }
399 }
400 break;
401 case 's':
402 ChSet(' ');
403 ChSet('\t');
404 ChSet('\n');
405 ChSet('\r');
406 ChSet('\f');
407 ChSet('\v');
408 break;
409 case 'S':
410 for (c = 0; c < MAXCHR; c++) {
411 if (c != ' ' && !(c >= 0x09 && c <= 0x0D)) {
412 ChSet(static_cast<unsigned char>(c));
413 }
414 }
415 break;
416 case 'w':
417 for (c = 0; c < MAXCHR; c++) {
418 if (iswordc(static_cast<unsigned char>(c))) {
419 ChSet(static_cast<unsigned char>(c));
420 }
421 }
422 break;
423 case 'W':
424 for (c = 0; c < MAXCHR; c++) {
425 if (!iswordc(static_cast<unsigned char>(c))) {
426 ChSet(static_cast<unsigned char>(c));
427 }
428 }
429 break;
430 default:
431 result = bsc;
432 }
433 return result;
434 }
435
Compile(const char * pattern,int length,bool caseSensitive,bool posix)436 const char *RESearch::Compile(const char *pattern, int length, bool caseSensitive, bool posix) {
437 char *mp=nfa; /* nfa pointer */
438 char *lp; /* saved pointer */
439 char *sp=nfa; /* another one */
440 char *mpMax = mp + MAXNFA - BITBLK - 10;
441
442 int tagi = 0; /* tag stack index */
443 int tagc = 1; /* actual tag count */
444
445 int n;
446 char mask; /* xor mask -CCL/NCL */
447 int c1, c2, prevChar;
448
449 if (!pattern || !length) {
450 if (sta)
451 return 0;
452 else
453 return badpat("No previous regular expression");
454 }
455 sta = NOP;
456
457 const char *p=pattern; /* pattern pointer */
458 for (int i=0; i<length; i++, p++) {
459 if (mp > mpMax)
460 return badpat("Pattern too long");
461 lp = mp;
462 switch (*p) {
463
464 case '.': /* match any char */
465 *mp++ = ANY;
466 break;
467
468 case '^': /* match beginning */
469 if (p == pattern) {
470 *mp++ = BOL;
471 } else {
472 *mp++ = CHR;
473 *mp++ = *p;
474 }
475 break;
476
477 case '$': /* match endofline */
478 if (!*(p+1)) {
479 *mp++ = EOL;
480 } else {
481 *mp++ = CHR;
482 *mp++ = *p;
483 }
484 break;
485
486 case '[': /* match char class */
487 *mp++ = CCL;
488 prevChar = 0;
489
490 i++;
491 if (*++p == '^') {
492 mask = '\377';
493 i++;
494 p++;
495 } else {
496 mask = 0;
497 }
498
499 if (*p == '-') { /* real dash */
500 i++;
501 prevChar = *p;
502 ChSet(*p++);
503 }
504 if (*p == ']') { /* real brace */
505 i++;
506 prevChar = *p;
507 ChSet(*p++);
508 }
509 while (*p && *p != ']') {
510 if (*p == '-') {
511 if (prevChar < 0) {
512 // Previous def. was a char class like \d, take dash literally
513 prevChar = *p;
514 ChSet(*p);
515 } else if (*(p+1)) {
516 if (*(p+1) != ']') {
517 c1 = prevChar + 1;
518 i++;
519 c2 = static_cast<unsigned char>(*++p);
520 if (c2 == '\\') {
521 if (!*(p+1)) { // End of RE
522 return badpat("Missing ]");
523 } else {
524 i++;
525 p++;
526 int incr;
527 c2 = GetBackslashExpression(p, incr);
528 i += incr;
529 p += incr;
530 if (c2 >= 0) {
531 // Convention: \c (c is any char) is case sensitive, whatever the option
532 ChSet(static_cast<unsigned char>(c2));
533 prevChar = c2;
534 } else {
535 // bittab is already changed
536 prevChar = -1;
537 }
538 }
539 }
540 if (prevChar < 0) {
541 // Char after dash is char class like \d, take dash literally
542 prevChar = '-';
543 ChSet('-');
544 } else {
545 // Put all chars between c1 and c2 included in the char set
546 while (c1 <= c2) {
547 ChSetWithCase(static_cast<unsigned char>(c1++), caseSensitive);
548 }
549 }
550 } else {
551 // Dash before the ], take it literally
552 prevChar = *p;
553 ChSet(*p);
554 }
555 } else {
556 return badpat("Missing ]");
557 }
558 } else if (*p == '\\' && *(p+1)) {
559 i++;
560 p++;
561 int incr;
562 int c = GetBackslashExpression(p, incr);
563 i += incr;
564 p += incr;
565 if (c >= 0) {
566 // Convention: \c (c is any char) is case sensitive, whatever the option
567 ChSet(static_cast<unsigned char>(c));
568 prevChar = c;
569 } else {
570 // bittab is already changed
571 prevChar = -1;
572 }
573 } else {
574 prevChar = static_cast<unsigned char>(*p);
575 ChSetWithCase(*p, caseSensitive);
576 }
577 i++;
578 p++;
579 }
580 if (!*p)
581 return badpat("Missing ]");
582
583 for (n = 0; n < BITBLK; bittab[n++] = 0)
584 *mp++ = static_cast<char>(mask ^ bittab[n]);
585
586 break;
587
588 case '*': /* match 0 or more... */
589 case '+': /* match 1 or more... */
590 case '?':
591 if (p == pattern)
592 return badpat("Empty closure");
593 lp = sp; /* previous opcode */
594 if (*lp == CLO || *lp == LCLO) /* equivalence... */
595 break;
596 switch (*lp) {
597
598 case BOL:
599 case BOT:
600 case EOT:
601 case BOW:
602 case EOW:
603 case REF:
604 return badpat("Illegal closure");
605 default:
606 break;
607 }
608
609 if (*p == '+')
610 for (sp = mp; lp < sp; lp++)
611 *mp++ = *lp;
612
613 *mp++ = END;
614 *mp++ = END;
615 sp = mp;
616
617 while (--mp > lp)
618 *mp = mp[-1];
619 if (*p == '?') *mp = CLQ;
620 else if (*(p+1) == '?') *mp = LCLO;
621 else *mp = CLO;
622
623 mp = sp;
624 break;
625
626 case '\\': /* tags, backrefs... */
627 i++;
628 switch (*++p) {
629 case '<':
630 *mp++ = BOW;
631 break;
632 case '>':
633 if (*sp == BOW)
634 return badpat("Null pattern inside \\<\\>");
635 *mp++ = EOW;
636 break;
637 case '1':
638 case '2':
639 case '3':
640 case '4':
641 case '5':
642 case '6':
643 case '7':
644 case '8':
645 case '9':
646 n = *p-'0';
647 if (tagi > 0 && tagstk[tagi] == n)
648 return badpat("Cyclical reference");
649 if (tagc > n) {
650 *mp++ = static_cast<char>(REF);
651 *mp++ = static_cast<char>(n);
652 } else {
653 return badpat("Undetermined reference");
654 }
655 break;
656 default:
657 if (!posix && *p == '(') {
658 if (tagc < MAXTAG) {
659 tagstk[++tagi] = tagc;
660 *mp++ = BOT;
661 *mp++ = static_cast<char>(tagc++);
662 } else {
663 return badpat("Too many \\(\\) pairs");
664 }
665 } else if (!posix && *p == ')') {
666 if (*sp == BOT)
667 return badpat("Null pattern inside \\(\\)");
668 if (tagi > 0) {
669 *mp++ = static_cast<char>(EOT);
670 *mp++ = static_cast<char>(tagstk[tagi--]);
671 } else {
672 return badpat("Unmatched \\)");
673 }
674 } else {
675 int incr;
676 int c = GetBackslashExpression(p, incr);
677 i += incr;
678 p += incr;
679 if (c >= 0) {
680 *mp++ = CHR;
681 *mp++ = static_cast<unsigned char>(c);
682 } else {
683 *mp++ = CCL;
684 mask = 0;
685 for (n = 0; n < BITBLK; bittab[n++] = 0)
686 *mp++ = static_cast<char>(mask ^ bittab[n]);
687 }
688 }
689 }
690 break;
691
692 default : /* an ordinary char */
693 if (posix && *p == '(') {
694 if (tagc < MAXTAG) {
695 tagstk[++tagi] = tagc;
696 *mp++ = BOT;
697 *mp++ = static_cast<char>(tagc++);
698 } else {
699 return badpat("Too many () pairs");
700 }
701 } else if (posix && *p == ')') {
702 if (*sp == BOT)
703 return badpat("Null pattern inside ()");
704 if (tagi > 0) {
705 *mp++ = static_cast<char>(EOT);
706 *mp++ = static_cast<char>(tagstk[tagi--]);
707 } else {
708 return badpat("Unmatched )");
709 }
710 } else {
711 unsigned char c = *p;
712 if (!c) // End of RE
713 c = '\\'; // We take it as raw backslash
714 if (caseSensitive || !iswordc(c)) {
715 *mp++ = CHR;
716 *mp++ = c;
717 } else {
718 *mp++ = CCL;
719 mask = 0;
720 ChSetWithCase(c, false);
721 for (n = 0; n < BITBLK; bittab[n++] = 0)
722 *mp++ = static_cast<char>(mask ^ bittab[n]);
723 }
724 }
725 break;
726 }
727 sp = lp;
728 }
729 if (tagi > 0)
730 return badpat((posix ? "Unmatched (" : "Unmatched \\("));
731 *mp = END;
732 sta = OKP;
733 return 0;
734 }
735
736 /*
737 * RESearch::Execute:
738 * execute nfa to find a match.
739 *
740 * special cases: (nfa[0])
741 * BOL
742 * Match only once, starting from the
743 * beginning.
744 * CHR
745 * First locate the character without
746 * calling PMatch, and if found, call
747 * PMatch for the remaining string.
748 * END
749 * RESearch::Compile failed, poor luser did not
750 * check for it. Fail fast.
751 *
752 * If a match is found, bopat[0] and eopat[0] are set
753 * to the beginning and the end of the matched fragment,
754 * respectively.
755 *
756 */
Execute(CharacterIndexer & ci,int lp,int endp)757 int RESearch::Execute(CharacterIndexer &ci, int lp, int endp) {
758 unsigned char c;
759 int ep = NOTFOUND;
760 char *ap = nfa;
761
762 bol = lp;
763 failure = 0;
764
765 Clear();
766
767 switch (*ap) {
768
769 case BOL: /* anchored: match from BOL only */
770 ep = PMatch(ci, lp, endp, ap);
771 break;
772 case EOL: /* just searching for end of line normal path doesn't work */
773 if (*(ap+1) == END) {
774 lp = endp;
775 ep = lp;
776 break;
777 } else {
778 return 0;
779 }
780 case CHR: /* ordinary char: locate it fast */
781 c = *(ap+1);
782 while ((lp < endp) && (static_cast<unsigned char>(ci.CharAt(lp)) != c))
783 lp++;
784 if (lp >= endp) /* if EOS, fail, else fall through. */
785 return 0;
786 default: /* regular matching all the way. */
787 while (lp < endp) {
788 ep = PMatch(ci, lp, endp, ap);
789 if (ep != NOTFOUND)
790 break;
791 lp++;
792 }
793 break;
794 case END: /* munged automaton. fail always */
795 return 0;
796 }
797 if (ep == NOTFOUND)
798 return 0;
799
800 bopat[0] = lp;
801 eopat[0] = ep;
802 return 1;
803 }
804
805 /*
806 * PMatch: internal routine for the hard part
807 *
808 * This code is partly snarfed from an early grep written by
809 * David Conroy. The backref and tag stuff, and various other
810 * innovations are by oz.
811 *
812 * special case optimizations: (nfa[n], nfa[n+1])
813 * CLO ANY
814 * We KNOW .* will match everything up to the
815 * end of line. Thus, directly go to the end of
816 * line, without recursive PMatch calls. As in
817 * the other closure cases, the remaining pattern
818 * must be matched by moving backwards on the
819 * string recursively, to find a match for xy
820 * (x is ".*" and y is the remaining pattern)
821 * where the match satisfies the LONGEST match for
822 * x followed by a match for y.
823 * CLO CHR
824 * We can again scan the string forward for the
825 * single char and at the point of failure, we
826 * execute the remaining nfa recursively, same as
827 * above.
828 *
829 * At the end of a successful match, bopat[n] and eopat[n]
830 * are set to the beginning and end of subpatterns matched
831 * by tagged expressions (n = 1 to 9).
832 */
833
834 extern void re_fail(char *,char);
835
836 #define isinset(x,y) ((x)[((y)&BLKIND)>>3] & bitarr[(y)&BITIND])
837
838 /*
839 * skip values for CLO XXX to skip past the closure
840 */
841
842 #define ANYSKIP 2 /* [CLO] ANY END */
843 #define CHRSKIP 3 /* [CLO] CHR chr END */
844 #define CCLSKIP 34 /* [CLO] CCL 32 bytes END */
845
PMatch(CharacterIndexer & ci,int lp,int endp,char * ap)846 int RESearch::PMatch(CharacterIndexer &ci, int lp, int endp, char *ap) {
847 int op, c, n;
848 int e; /* extra pointer for CLO */
849 int bp; /* beginning of subpat... */
850 int ep; /* ending of subpat... */
851 int are; /* to save the line ptr. */
852 int llp; /* lazy lp for LCLO */
853
854 while ((op = *ap++) != END)
855 switch (op) {
856
857 case CHR:
858 if (ci.CharAt(lp++) != *ap++)
859 return NOTFOUND;
860 break;
861 case ANY:
862 if (lp++ >= endp)
863 return NOTFOUND;
864 break;
865 case CCL:
866 if (lp >= endp)
867 return NOTFOUND;
868 c = ci.CharAt(lp++);
869 if (!isinset(ap,c))
870 return NOTFOUND;
871 ap += BITBLK;
872 break;
873 case BOL:
874 if (lp != bol)
875 return NOTFOUND;
876 break;
877 case EOL:
878 if (lp < endp)
879 return NOTFOUND;
880 break;
881 case BOT:
882 bopat[static_cast<int>(*ap++)] = lp;
883 break;
884 case EOT:
885 eopat[static_cast<int>(*ap++)] = lp;
886 break;
887 case BOW:
888 if ((lp!=bol && iswordc(ci.CharAt(lp-1))) || !iswordc(ci.CharAt(lp)))
889 return NOTFOUND;
890 break;
891 case EOW:
892 if (lp==bol || !iswordc(ci.CharAt(lp-1)) || iswordc(ci.CharAt(lp)))
893 return NOTFOUND;
894 break;
895 case REF:
896 n = *ap++;
897 bp = bopat[n];
898 ep = eopat[n];
899 while (bp < ep)
900 if (ci.CharAt(bp++) != ci.CharAt(lp++))
901 return NOTFOUND;
902 break;
903 case LCLO:
904 case CLQ:
905 case CLO:
906 are = lp;
907 switch (*ap) {
908
909 case ANY:
910 if (op == CLO || op == LCLO)
911 while (lp < endp)
912 lp++;
913 else if (lp < endp)
914 lp++;
915
916 n = ANYSKIP;
917 break;
918 case CHR:
919 c = *(ap+1);
920 if (op == CLO || op == LCLO)
921 while ((lp < endp) && (c == ci.CharAt(lp)))
922 lp++;
923 else if ((lp < endp) && (c == ci.CharAt(lp)))
924 lp++;
925 n = CHRSKIP;
926 break;
927 case CCL:
928 while ((lp < endp) && isinset(ap+1,ci.CharAt(lp)))
929 lp++;
930 n = CCLSKIP;
931 break;
932 default:
933 failure = true;
934 //re_fail("closure: bad nfa.", *ap);
935 return NOTFOUND;
936 }
937 ap += n;
938
939 llp = lp;
940 e = NOTFOUND;
941 while (llp >= are) {
942 int q;
943 if ((q = PMatch(ci, llp, endp, ap)) != NOTFOUND) {
944 e = q;
945 lp = llp;
946 if (op != LCLO) return e;
947 }
948 if (*ap == END) return e;
949 --llp;
950 }
951 if (*ap == EOT)
952 PMatch(ci, lp, endp, ap);
953 return e;
954 default:
955 //re_fail("RESearch::Execute: bad nfa.", static_cast<char>(op));
956 return NOTFOUND;
957 }
958 return lp;
959 }
960
961
962