// Scintilla source code edit control /** @file RESearch.cxx ** Regular expression search library. **/ /* * regex - Regular expression pattern matching and replacement * * By: Ozan S. Yigit (oz) * Dept. of Computer Science * York University * * Original code available from http://www.cs.yorku.ca/~oz/ * Translation to C++ by Neil Hodgson neilh@scintilla.org * Removed all use of register. * Converted to modern function prototypes. * Put all global/static variables into an object so this code can be * used from multiple threads, etc. * Some extensions by Philippe Lhoste PhiLho(a)GMX.net * '?' extensions by Michael Mullin masmullin@gmail.com * * These routines are the PUBLIC DOMAIN equivalents of regex * routines as found in 4.nBSD UN*X, with minor extensions. * * These routines are derived from various implementations found * in software tools books, and Conroy's grep. They are NOT derived * from licensed/restricted software. * For more interesting/academic/complicated implementations, * see Henry Spencer's regexp routines, or GNU Emacs pattern * matching module. * * Modification history removed. * * Interfaces: * RESearch::Compile: compile a regular expression into a NFA. * * const char *RESearch::Compile(const char *pattern, int length, * bool caseSensitive, bool posix) * * Returns a short error string if they fail. * * RESearch::Execute: execute the NFA to match a pattern. * * int RESearch::Execute(characterIndexer &ci, int lp, int endp) * * re_fail: failure routine for RESearch::Execute. (no longer used) * * void re_fail(char *msg, char op) * * Regular Expressions: * * [1] char matches itself, unless it is a special * character (metachar): . \ [ ] * + ? ^ $ * and ( ) if posix option. * * [2] . matches any character. * * [3] \ matches the character following it, except: * - \a, \b, \f, \n, \r, \t, \v match the corresponding C * escape char, respectively BEL, BS, FF, LF, CR, TAB and VT; * Note that \r and \n are never matched because Scintilla * regex searches are made line per line * (stripped of end-of-line chars). * - if not in posix mode, when followed by a * left or right round bracket (see [8]); * - when followed by a digit 1 to 9 (see [9]); * - when followed by a left or right angle bracket * (see [10]); * - when followed by d, D, s, S, w or W (see [11]); * - when followed by x and two hexa digits (see [12]. * Backslash is used as an escape character for all * other meta-characters, and itself. * * [4] [set] matches one of the characters in the set. * If the first character in the set is "^", * it matches the characters NOT in the set, i.e. * complements the set. A shorthand S-E (start dash end) * is used to specify a set of characters S up to * E, inclusive. S and E must be characters, otherwise * the dash is taken literally (eg. in expression [\d-a]). * The special characters "]" and "-" have no special * meaning if they appear as the first chars in the set. * To include both, put - first: [-]A-Z] * (or just backslash them). * examples: match: * * [-]|] matches these 3 chars, * * []-|] matches from ] to | chars * * [a-z] any lowercase alpha * * [^-]] any char except - and ] * * [^A-Z] any char except uppercase * alpha * * [a-zA-Z] any alpha * * [5] * any regular expression form [1] to [4] * (except [8], [9] and [10] forms of [3]), * followed by closure char (*) * matches zero or more matches of that form. * * [6] + same as [5], except it matches one or more. * * [5-6] Both [5] and [6] are greedy (they match as much as possible). * Unless they are followed by the 'lazy' quantifier (?) * In which case both [5] and [6] try to match as little as possible * * [7] ? same as [5] except it matches zero or one. * * [8] a regular expression in the form [1] to [13], enclosed * as \(form\) (or (form) with posix flag) matches what * form matches. The enclosure creates a set of tags, * used for [9] and for pattern substitution. * The tagged forms are numbered starting from 1. * * [9] a \ followed by a digit 1 to 9 matches whatever a * previously tagged regular expression ([8]) matched. * * [10] \< a regular expression starting with a \< construct * \> and/or ending with a \> construct, restricts the * pattern matching to the beginning of a word, and/or * the end of a word. A word is defined to be a character * string beginning and/or ending with the characters * A-Z a-z 0-9 and _. Scintilla extends this definition * by user setting. The word must also be preceded and/or * followed by any character outside those mentioned. * * [11] \l a backslash followed by d, D, s, S, w or W, * becomes a character class (both inside and * outside sets []). * d: decimal digits * D: any char except decimal digits * s: whitespace (space, \t \n \r \f \v) * S: any char except whitespace (see above) * w: alphanumeric & underscore (changed by user setting) * W: any char except alphanumeric & underscore (see above) * * [12] \xHH a backslash followed by x and two hexa digits, * becomes the character whose Ascii code is equal * to these digits. If not followed by two digits, * it is 'x' char itself. * * [13] a composite regular expression xy where x and y * are in the form [1] to [12] matches the longest * match of x followed by a match for y. * * [14] ^ a regular expression starting with a ^ character * $ and/or ending with a $ character, restricts the * pattern matching to the beginning of the line, * or the end of line. [anchors] Elsewhere in the * pattern, ^ and $ are treated as ordinary characters. * * * Acknowledgements: * * HCR's Hugh Redelmeier has been most helpful in various * stages of development. He convinced me to include BOW * and EOW constructs, originally invented by Rob Pike at * the University of Toronto. * * References: * Software tools Kernighan & Plauger * Software tools in Pascal Kernighan & Plauger * Grep [rsx-11 C dist] David Conroy * ed - text editor Un*x Programmer's Manual * Advanced editing on Un*x B. W. Kernighan * RegExp routines Henry Spencer * * Notes: * * This implementation uses a bit-set representation for cHTTP/1.1 200 OK Connection: keep-alive Connection: keep-alive Content-Disposition: inline; filename="RESearch.cxx" Content-Disposition: inline; filename="RESearch.cxx" Content-Length: 26508 Content-Length: 26508 Content-Security-Policy: default-src 'none' Content-Security-Policy: default-src 'none' Content-Type: text/plain; charset=UTF-8 Content-Type: text/plain; charset=UTF-8 Date: Wed, 31 Dec 2025 11:27:59 UTC ETag: "81eddf0131a3bbf949e82da19c5bb27a55cea943" ETag: "81eddf0131a3bbf949e82da19c5bb27a55cea943" Expires: Sat, 29 Dec 2035 11:27:59 GMT Expires: Sat, 29 Dec 2035 11:27:59 GMT Last-Modified: Wed, 31 Dec 2025 11:27:59 GMT Last-Modified: Wed, 31 Dec 2025 11:27:59 GMT Server: OpenBSD httpd Server: OpenBSD httpd X-Content-Type-Options: nosniff X-Content-Type-Options: nosniff // Scintilla source code edit control /** @file RESearch.cxx ** Regular expression search library. **/ /* * regex - Regular expression pattern matching and replacement * * By: Ozan S. Yigit (oz) * Dept. of Computer Science * York University * * Original code available from http://www.cs.yorku.ca/~oz/ * Translation to C++ by Neil Hodgson neilh@scintilla.org * Removed all use of register. * Converted to modern function prototypes. * Put all global/static variables into an object so this code can be * used from multiple threads, etc. * Some extensions by Philippe Lhoste PhiLho(a)GMX.net * '?' extensions by Michael Mullin masmullin@gmail.com * * These routines are the PUBLIC DOMAIN equivalents of regex * routines as found in 4.nBSD UN*X, with minor extensions. * * These routines are derived from various implementations found * in software tools books, and Conroy's grep. They are NOT derived * from licensed/restricted software. * For more interesting/academic/complicated implementations, * see Henry Spencer's regexp routines, or GNU Emacs pattern * matching module. * * Modification history removed. * * Interfaces: * RESearch::Compile: compile a regular expression into a NFA. * * const char *RESearch::Compile(const char *pattern, int length, * bool caseSensitive, bool posix) * * Returns a short error string if they fail. * * RESearch::Execute: execute the NFA to match a pattern. * * int RESearch::Execute(characterIndexer &ci, int lp, int endp) * * re_fail: failure routine for RESearch::Execute. (no longer used) * * void re_fail(char *msg, char op) * * Regular Expressions: * * [1] char matches itself, unless it is a special * character (metachar): . \ [ ] * + ? ^ $ * and ( ) if posix option. * * [2] . matches any character. * * [3] \ matches the character following it, except: * - \a, \b, \f, \n, \r, \t, \v match the corresponding C * escape char, respectively BEL, BS, FF, LF, CR, TAB and VT; * Note that \r and \n are never matched because Scintilla * regex searches are made line per line * (stripped of end-of-line chars). * - if not in posix mode, when followed by a * left or right round bracket (see [8]); * - when followed by a digit 1 to 9 (see [9]); * - when followed by a left or right angle bracket * (see [10]); * - when followed by d, D, s, S, w or W (see [11]); * - when followed by x and two hexa digits (see [12]. * Backslash is used as an escape character for all * other meta-characters, and itself. * * [4] [set] matches one of the characters in the set. * If the first character in the set is "^", * it matches the characters NOT in the set, i.e. * complements the set. A shorthand S-E (start dash end) * is used to specify a set of characters S up to * E, inclusive. S and E must be characters, otherwise * the dash is taken literally (eg. in expression [\d-a]). * The special characters "]" and "-" have no special * meaning if they appear as the first chars in the set. * To include both, put - first: [-]A-Z] * (or just backslash them). * examples: match: * * [-]|] matches these 3 chars, * * []-|] matches from ] to | chars * * [a-z] any lowercase alpha * * [^-]] any char except - and ] * * [^A-Z] any char except uppercase * alpha * * [a-zA-Z] any alpha * * [5] * any regular expression form [1] to [4] * (except [8], [9] and [10] forms of [3]), * followed by closure char (*) * matches zero or more matches of that form. * * [6] + same as [5], except it matches one or more. * * [5-6] Both [5] and [6] are greedy (they match as much as possible). * Unless they are followed by the 'lazy' quantifier (?) * In which case both [5] and [6] try to match as little as possible * * [7] ? same as [5] except it matches zero or one. * * [8] a regular expression in the form [1] to [13], enclosed * as \(form\) (or (form) with posix flag) matches what * form matches. The enclosure creates a set of tags, * used for [9] and for pattern substitution. * The tagged forms are numbered starting from 1. * * [9] a \ followed by a digit 1 to 9 matches whatever a * previously tagged regular expression ([8]) matched. * * [10] \< a regular expression starting with a \< construct * \> and/or ending with a \> construct, restricts the * pattern matching to the beginning of a word, and/or * the end of a word. A word is defined to be a character * string beginning and/or ending with the characters * A-Z a-z 0-9 and _. Scintilla extends this definition * by user setting. The word must also be preceded and/or * followed by any character outside those mentioned. * * [11] \l a backslash followed by d, D, s, S, w or W, * becomes a character class (both inside and * outside sets []). * d: decimal digits * D: any char except decimal digits * s: whitespace (space, \t \n \r \f \v) * S: any char except whitespace (see above) * w: alphanumeric & underscore (changed by user setting) * W: any char except alphanumeric & underscore (see above) * * [12] \xHH a backslash followed by x and two hexa digits, * becomes the character whose Ascii code is equal * to these digits. If not followed by two digits, * it is 'x' char itself. * * [13] a composite regular expression xy where x and y * are in the form [1] to [12] matches the longest * match of x followed by a match for y. * * [14] ^ a regular expression starting with a ^ character * $ and/or ending with a $ character, restricts the * pattern matching to the beginning of the line, * or the end of line. [anchors] Elsewhere in the * pattern, ^ and $ are treated as ordinary characters. * * * Acknowledgements: * * HCR's Hugh Redelmeier has been most helpful in various * stages of development. He convinced me to include BOW * and EOW constructs, originally invented by Rob Pike at * the University of Toronto. * * References: * Software tools Kernighan & Plauger * Software tools in Pascal Kernighan & Plauger * Grep [rsx-11 C dist] David Conroy * ed - text editor Un*x Programmer's Manual * Advanced editing on Un*x B. W. Kernighan * RegExp routines Henry Spencer * * Notes: * * This implementation uses a bit-set representation for character * classes for speed and compactness. Each character is represented * by one bit in a 256-bit block. Thus, CCL always takes a * constant 32 bytes in the internal nfa, and RESearch::Execute does a single * bit comparison to locate the character in the set. * * Examples: * * pattern: foo*.* * compile: CHR f CHR o CLO CHR o END CLO ANY END END * matches: fo foo fooo foobar fobar foxx ... * * pattern: fo[ob]a[rz] * compile: CHR f CHR o CCL bitset CHR a CCL bitset END * matches: fobar fooar fobaz fooaz * * pattern: foo\\+ * compile: CHR f CHR o CHR o CHR \ CLO CHR \ END END * matches: foo\ foo\\ foo\\\ ... * * pattern: \(foo\)[1-3]\1 (same as foo[1-3]foo) * compile: BOT 1 CHR f CHR o CHR o EOT 1 CCL bitset REF 1 END * matches: foo1foo foo2foo foo3foo * * pattern: \(fo.*\)-\1 * compile: BOT 1 CHR f CHR o CLO ANY END EOT 1 CHR - REF 1 END * matches: foo-foo fo-fo fob-fob foobar-foobar ... */ #include #include #include "CharClassify.h" #include "RESearch.h" // Shut up annoying Visual C++ warnings: #ifdef _MSC_VER #pragma warning(disable: 4514) #endif #ifdef SCI_NAMESPACE using namespace Scintilla; #endif #define OKP 1 #define NOP 0 #define CHR 1 #define ANY 2 #define CCL 3 #define BOL 4 #define EOL 5 #define BOT 6 #define EOT 7 #define BOW 8 #define EOW 9 #define REF 10 #define CLO 11 #define CLQ 12 /* 0 to 1 closure */ #define LCLO 13 /* lazy closure */ #define END 0 /* * The following defines are not meant to be changeable. * They are for readability only. */ #define BLKIND 0370 #define BITIND 07 const char bitarr[] = { 1, 2, 4, 8, 16, 32, 64, '\200' }; #define badpat(x) (*nfa = END, x) /* * Character classification table for word boundary operators BOW * and EOW is passed in by the creator of this object (Scintilla * Document). The Document default state is that word chars are: * 0-9, a-z, A-Z and _ */ RESearch::RESearch(CharClassify *charClassTable) { failure = 0; charClass = charClassTable; Init(); } RESearch::~RESearch() { Clear(); } void RESearch::Init() { sta = NOP; /* status of lastpat */ bol = 0; for (int i = 0; i < MAXTAG; i++) pat[i].clear(); for (int j = 0; j < BITBLK; j++) bittab[j] = 0; } void RESearch::Clear() { for (int i = 0; i < MAXTAG; i++) { pat[i].clear(); bopat[i] = NOTFOUND; eopat[i] = NOTFOUND; } } void RESearch::GrabMatches(CharacterIndexer &ci) { for (unsigned int i = 0; i < MAXTAG; i++) { if ((bopat[i] != NOTFOUND) && (eopat[i] != NOTFOUND)) { unsigned int len = eopat[i] - bopat[i]; pat[i] = std::string(len+1, '\0'); for (unsigned int j = 0; j < len; j++) pat[i][j] = ci.CharAt(bopat[i] + j); pat[i][len] = '\0'; } } } void RESearch::ChSet(unsigned char c) { bittab[((c) & BLKIND) >> 3] |= bitarr[(c) & BITIND]; } void RESearch::ChSetWithCase(unsigned char c, bool caseSensitive) { if (caseSensitive) { ChSet(c); } else { if ((c >= 'a') && (c <= 'z')) { ChSet(c); ChSet(static_cast(c - 'a' + 'A')); } else if ((c >= 'A') && (c <= 'Z')) { ChSet(c); ChSet(static_cast(c - 'A' + 'a')); } else { ChSet(c); } } } unsigned char escapeValue(unsigned char ch) { switch (ch) { case 'a': return '\a'; case 'b': return '\b'; case 'f': return '\f'; case 'n': return '\n'; case 'r': return '\r'; case 't': return '\t'; case 'v': return '\v'; } return 0; } static int GetHexaChar(unsigned char hd1, unsigned char hd2) { int hexValue = 0; if (hd1 >= '0' && hd1 <= '9') { hexValue += 16 * (hd1 - '0'); } else if (hd1 >= 'A' && hd1 <= 'F') { hexValue += 16 * (hd1 - 'A' + 10); } else if (hd1 >= 'a' && hd1 <= 'f') { hexValue += 16 * (hd1 - 'a' + 10); } else { return -1; } if (hd2 >= '0' && hd2 <= '9') { hexValue += hd2 - '0'; } else if (hd2 >= 'A' && hd2 <= 'F') { hexValue += hd2 - 'A' + 10; } else if (hd2 >= 'a' && hd2 <= 'f') { hexValue += hd2 - 'a' + 10; } else { return -1; } return hexValue; } /** * Called when the parser finds a backslash not followed * by a valid expression (like \( in non-Posix mode). * @param pattern: pointer on the char after the backslash. * @param incr: (out) number of chars to skip after expression evaluation. * @return the char if it resolves to a simple char, * or -1 for a char class. In this case, bittab is changed. */ int RESearch::GetBackslashExpression( const char *pattern, int &incr) { // Since error reporting is primitive and messages are not used anyway, // I choose to interpret unexpected syntax in a logical way instead // of reporting errors. Otherwise, we can stick on, eg., PCRE behavior. incr = 0; // Most of the time, will skip the char "naturally". int c; int result = -1; unsigned char bsc = *pattern; if (!bsc) { // Avoid overrun result = '\\'; // \ at end of pattern, take it literally return result; } switch (bsc) { case 'a': case 'b': case 'n': case 'f': case 'r': case 't': case 'v': result = escapeValue(bsc); break; case 'x': { unsigned char hd1 = *(pattern + 1); unsigned char hd2 = *(pattern + 2); int hexValue = GetHexaChar(hd1, hd2); if (hexValue >= 0) { result = hexValue; incr = 2; // Must skip the digits } else { result = 'x'; // \x without 2 digits: see it as 'x' } } break; case 'd': for (c = '0'; c <= '9'; c++) { ChSet(static_cast(c)); } break; case 'D': for (c = 0; c < MAXCHR; c++) { if (c < '0' || c > '9') { ChSet(static_cast(c)); } } break; case 's': ChSet(' '); ChSet('\t'); ChSet('\n'); ChSet('\r'); ChSet('\f'); ChSet('\v'); break; case 'S': for (c = 0; c < MAXCHR; c++) { if (c != ' ' && !(c >= 0x09 && c <= 0x0D)) { ChSet(static_cast(c)); } } break; case 'w': for (c = 0; c < MAXCHR; c++) { if (iswordc(static_cast(c))) { ChSet(static_cast(c)); } } break; case 'W': for (c = 0; c < MAXCHR; c++) { if (!iswordc(static_cast(c))) { ChSet(static_cast(c)); } } break; default: result = bsc; } return result; } const char *RESearch::Compile(const char *pattern, int length, bool caseSensitive, bool posix) { char *mp=nfa; /* nfa pointer */ char *lp; /* saved pointer */ char *sp=nfa; /* another one */ char *mpMax = mp + MAXNFA - BITBLK - 10; int tagi = 0; /* tag stack index */ int tagc = 1; /* actual tag count */ int n; char mask; /* xor mask -CCL/NCL */ int c1, c2, prevChar; if (!pattern || !length) { if (sta) return 0; else return badpat("No previous regular expression"); } sta = NOP; const char *p=pattern; /* pattern pointer */ for (int i=0; i mpMax) return badpat("Pattern too long"); lp = mp; switch (*p) { case '.': /* match any char */ *mp++ = ANY; break; case '^': /* match beginning */ if (p == pattern) { *mp++ = BOL; } else { *mp++ = CHR; *mp++ = *p; } break; case '$': /* match endofline */ if (!*(p+1)) { *mp++ = EOL; } else { *mp++ = CHR; *mp++ = *p; } break; case '[': /* match char class */ *mp++ = CCL; prevChar = 0; i++; if (*++p == '^') { mask = '\377'; i++; p++; } else { mask = 0; } if (*p == '-') { /* real dash */ i++; prevChar = *p; ChSet(*p++); } if (*p == ']') { /* real brace */ i++; prevChar = *p; ChSet(*p++); } while (*p && *p != ']') { if (*p == '-') { if (prevChar < 0) { // Previous def. was a char class like \d, take dash literally prevChar = *p; ChSet(*p); } else if (*(p+1)) { if (*(p+1) != ']') { c1 = prevChar + 1; i++; c2 = static_cast(*++p); if (c2 == '\\') { if (!*(p+1)) { // End of RE return badpat("Missing ]"); } else { i++; p++; int incr; c2 = GetBackslashExpression(p, incr); i += incr; p += incr; if (c2 >= 0) { // Convention: \c (c is any char) is case sensitive, whatever the option ChSet(static_cast(c2)); prevChar = c2; } else { // bittab is already changed prevChar = -1; } } } if (prevChar < 0) { // Char after dash is char class like \d, take dash literally prevChar = '-'; ChSet('-'); } else { // Put all chars between c1 and c2 included in the char set while (c1 <= c2) { ChSetWithCase(static_cast(c1++), caseSensitive); } } } else { // Dash before the ], take it literally prevChar = *p; ChSet(*p); } } else { return badpat("Missing ]"); } } else if (*p == '\\' && *(p+1)) { i++; p++; int incr; int c = GetBackslashExpression(p, incr); i += incr; p += incr; if