← Back to branch summary

~efargaspro/+junk/codeblocks-16.01-release

« back to all changes in this revision

Viewing changes to src/sdk/wxscintilla/src/scintilla/src/RESearch.cxx

  • Committer: damienlmoore at gmail
  • Date: 2016-02-02 02:43:22 UTC
  • Revision ID: damienlmoore@gmail.com-20160202024322-yql5qmtbwdyamdwd
Code::Blocks 16.01

Show diffs side-by-side

added added

removed removed

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