icuSources/i18n/regeximp.h

   1 //
   2 //   Copyright (C) 2002-2004 International Business Machines Corporation
   3 //   and others. All rights reserved.
   4 //
   5 //   file:  regeximp.h
   6 //
   7 //           ICU Regular Expressions,
   8 //               Definitions of constant values used in the compiled form of
   9 //               a regular expression pattern.
  10 //
  11
  12 #ifndef _REGEXIMP_H
  13 #define _REGEXIMP_H
  14
  15 #include "cmemory.h"
  16
  17 U_NAMESPACE_BEGIN
  18
  19 #ifdef REGEX_DEBUG   /* For debugging, define REGEX_DEBUG in regex.h, not here in this file. */
  20 //
  21 //  debugging options.  Enable one or more of the three #defines immediately following
  22 //
  23
  24 //#define REGEX_SCAN_DEBUG
  25 #define REGEX_DUMP_DEBUG
  26 #define REGEX_RUN_DEBUG
  27
  28 //  End of #defines inteded to be directly set.
  29
  30 #include <stdio.h>
  31 #endif
  32
  33 #ifdef REGEX_SCAN_DEBUG
  34 #define REGEX_SCAN_DEBUG_PRINTF(a) printf a
  35 #else
  36 #define REGEX_SCAN_DEBUG_PRINTF(a)
  37 #endif
  38
  39 #ifdef REGEX_DUMP_DEBUG
  40 #define REGEX_DUMP_DEBUG_PRINTF(a) printf a
  41 #else
  42 #define REGEX_DUMP_DEBUG_PRINTF(a)
  43 #endif
  44
  45 #ifdef REGEX_RUN_DEBUG
  46 #define REGEX_RUN_DEBUG_PRINTF(a) printf a
  47 #define REGEX_DUMP_DEBUG_PRINTF(a) printf a
  48 #else
  49 #define REGEX_RUN_DEBUG_PRINTF(a)
  50 #endif
  51
  52
  53 //
  54 //  Opcode types     In the compiled form of the regexp, these are the type, or opcodes,
  55 //                   of the entries.
  56 //
  57 enum {
  58      URX_RESERVED_OP   = 0,    // For multi-operand ops, most non-first words.
  59      URX_RESERVED_OP_N = 255,  // For multi-operand ops, negative operand values.
  60      URX_BACKTRACK     = 1,
  61      URX_END           = 2,
  62      URX_ONECHAR       = 3,    // Value field is the 21 bit unicode char to match
  63      URX_STRING        = 4,    // Value field is index of string start
  64      URX_STRING_LEN    = 5,    // Value field is string length (code units)
  65      URX_STATE_SAVE    = 6,    // Value field is pattern position to push
  66      URX_NOP           = 7,
  67      URX_START_CAPTURE = 8,    // Value field is capture group number.
  68      URX_END_CAPTURE   = 9,    // Value field is capture group number
  69      URX_STATIC_SETREF = 10,   // Value field is index of set in array of sets.
  70      URX_SETREF        = 11,   // Value field is index of set in array of sets.
  71      URX_DOTANY        = 12,
  72      URX_JMP           = 13,   // Value field is destination position in
  73                                                     //   the pattern.
  74      URX_FAIL          = 14,   // Stop match operation,  No match.
  75
  76      URX_JMP_SAV       = 15,   // Operand:  JMP destination location
  77      URX_BACKSLASH_B   = 16,   // Value field:  0:  \b    1:  \B
  78      URX_BACKSLASH_G   = 17,
  79      URX_JMP_SAV_X     = 18,   // Conditional JMP_SAV,
  80                                //    Used in (x)+, breaks loop on zero length match.
  81                                //    Operand:  Jmp destination.
  82      URX_BACKSLASH_X   = 19,
  83      URX_BACKSLASH_Z   = 20,   // \z   Unconditional end of line.
  84
  85      URX_DOTANY_ALL    = 21,   // ., in the . matches any mode.
  86      URX_BACKSLASH_D   = 22,   // Value field:  0:  \d    1:  \D
  87      URX_CARET         = 23,   // Value field:  1:  multi-line mode.
  88      URX_DOLLAR        = 24,  // Also for \Z
  89
  90      URX_CTR_INIT      = 25,   // Counter Inits for {Interval} loops.
  91      URX_CTR_INIT_NG   = 26,   //   3 kinds, normal, non-greedy, and possessive.
  92                                //   These are 4 word opcodes.  See description.
  93                                //    First Operand:  Data loc of counter variable
  94                                //    2nd   Operand:  Pat loc of the URX_CTR_LOOPx
  95                                //                    at the end of the loop.
  96                                //    3rd   Operand:  Minimum count.
  97                                //    4th   Operand:  Max count, -1 for unbounded.
  98
  99      URX_DOTANY_PL     = 27,   // .+, match rest of the line.  Fail already at end.
 100
 101      URX_CTR_LOOP      = 28,   // Loop Ops for {interval} loops.
 102      URX_CTR_LOOP_NG   = 29,   //   Also in three flavors.
 103                                //   Operand is loc of corresponding CTR_INIT.
 104
 105      URX_DOTANY_ALL_PL = 30,   // .+, match rest of the Input.  Fail if already at end
 106
 107      URX_RELOC_OPRND   = 31,   // Operand value in multi-operand ops that refers
 108                                //   back into compiled pattern code, and thus must
 109                                //   be relocated when inserting/deleting ops in code.
 110
 111      URX_STO_SP        = 32,   // Store the stack ptr.  Operand is location within
 112                                //   matcher data (not stack data) to store it.
 113      URX_LD_SP         = 33,   // Load the stack pointer.  Operand is location
 114                                //   to load from.
 115      URX_BACKREF       = 34,   // Back Reference.  Parameter is the index of the
 116                                //   capture group variables in the state stack frame.
 117      URX_STO_INP_LOC   = 35,   // Store the input location.  Operand is location
 118                                //   within the matcher stack frame.
 119      URX_JMPX          = 36,  // Conditional JMP.
 120                                //   First Operand:  JMP target location.
 121                                //   Second Operand:  Data location containing an
 122                                //     input position.  If current input position ==
 123                                //     saved input position, FAIL rather than taking
 124                                //     the JMP
 125      URX_LA_START      = 37,   // Starting a LookAround expression.
 126                                //   Save InputPos and SP in static data.
 127                                //   Operand:  Static data offset for the save
 128      URX_LA_END        = 38,   // Ending a Lookaround expression.
 129                                //   Restore InputPos and Stack to saved values.
 130                                //   Operand:  Static data offset for saved data.
 131      URX_ONECHAR_I     = 39,   // Test for case-insensitive match of a literal character.
 132                                //   Operand:  the literal char.
 133      URX_STRING_I      = 40,   // Case insensitive string compare.
 134                                //   First Operand:  Index of start of string in string literals
 135                                //   Second Operand (next word in compiled code):
 136                                //     the length of the string.
 137      URX_BACKREF_I     = 41,   // Case insensitive back reference.
 138                                //   Parameter is the index of the
 139                                //   capture group variables in the state stack frame.
 140      URX_DOLLAR_M      = 42,   // $ in multi-line mode.
 141      URX_CARET_M       = 43,   // ^ in multi-line mode.
 142      URX_LB_START      = 44,   // LookBehind Start.
 143                                //   Paramater is data location
 144      URX_LB_CONT       = 45,   // LookBehind Continue.
 145                                //   Param 0:  the data location
 146                                //   Param 1:  The minimum length of the look-behind match
 147                                //   Param 2:  The max length of the look-behind match
 148      URX_LB_END        = 46,   // LookBehind End.
 149                                //   Parameter is the data location.
 150                                //     Check that match ended at the right spot,
 151                                //     Restore original input string len.
 152      URX_LBN_CONT      = 47,   // Negative LookBehind Continue
 153                                //   Param 0:  the data location
 154                                //   Param 1:  The minimum length of the look-behind match
 155                                //   Param 2:  The max     length of the look-behind match
 156                                //   Param 3:  The pattern loc following the look-behind block.
 157      URX_LBN_END       = 48,   // Negative LookBehind end
 158                                //   Parameter is the data location.
 159                                //   Check that the match ended at the right spot.
 160      URX_STAT_SETREF_N = 49,   // Reference to a prebuilt set (e.g. \w), negated
 161                                //   Operand is index of set in array of sets.
 162      URX_LOOP_SR_I     = 50,   // Init a [set]* loop.
 163                                //   Operand is the sets index in array of user sets.
 164      URX_LOOP_C        = 51,   // Continue a [set]* or OneChar* loop.
 165                                //   Operand is a matcher static data location.
 166                                //   Must always immediately follow  LOOP_x_I instruction.
 167      URX_LOOP_DOT_I    = 52,   // .*, initialization of the optimized loop.
 168                                //   Operand value:
 169                                //      0:  Normal (. doesn't match new-line) mode.
 170                                //      1:  . matches new-line mode.
 171      URX_BACKSLASH_BU  = 53    // \b or \B in UREGEX_UWORD mode, using Unicode style
 172                                //   word boundaries.
 173
 174 };
 175
 176 // Keep this list of opcode names in sync with the above enum
 177 //   Used for debug printing only.
 178 #define URX_OPCODE_NAMES       \
 179         "               ",     \
 180         "BACKTRACK",           \
 181         "END",                 \
 182         "ONECHAR",             \
 183         "STRING",              \
 184         "STRING_LEN",          \
 185         "STATE_SAVE",          \
 186         "NOP",                 \
 187         "START_CAPTURE",       \
 188         "END_CAPTURE",         \
 189         "URX_STATIC_SETREF",   \
 190         "SETREF",              \
 191         "DOTANY",              \
 192         "JMP",                 \
 193         "FAIL",                \
 194         "JMP_SAV",             \
 195         "BACKSLASH_B",         \
 196         "BACKSLASH_G",         \
 197         "JMP_SAV_X",           \
 198         "BACKSLASH_X",         \
 199         "BACKSLASH_Z",         \
 200         "DOTANY_ALL",          \
 201         "BACKSLASH_D",         \
 202         "CARET",               \
 203         "DOLLAR",              \
 204         "CTR_INIT",            \
 205         "CTR_INIT_NG",         \
 206         "DOTANY_PL",           \
 207         "CTR_LOOP",            \
 208         "CTR_LOOP_NG",         \
 209         "DOTANY_ALL_PL",       \
 210         "RELOC_OPRND",         \
 211         "STO_SP",              \
 212         "LD_SP",               \
 213         "BACKREF",             \
 214         "STO_INP_LOC",         \
 215         "JMPX",                \
 216         "LA_START",            \
 217         "LA_END",              \
 218         "ONECHAR_I",           \
 219         "STRING_I",            \
 220         "BACKREF_I",           \
 221         "DOLLAR_M",            \
 222         "CARET_M",             \
 223         "LB_START",            \
 224         "LB_CONT",             \
 225         "LB_END",              \
 226         "LBN_CONT",            \
 227         "LBN_END",             \
 228         "STAT_SETREF_N",       \
 229         "LOOP_SR_I",           \
 230         "LOOP_C",              \
 231         "LOOP_DOT_I",          \
 232         "BACKSLASH_BU"
 233
 234
 235 //
 236 //  Convenience macros for assembling and disassembling a compiled operation.
 237 //
 238 #define URX_BUILD(type, val) (int32_t)((type << 24) | (val))
 239 #define URX_TYPE(x)          ((uint32_t)(x) >> 24)
 240 #define URX_VAL(x)           ((x) & 0xffffff)
 241
 242
 243 //
 244 //  Access to Unicode Sets composite character properties
 245 //     The sets are accessed by the match engine for things like \w (word boundary)
 246 //
 247 enum {
 248      URX_ISWORD_SET  = 1,
 249      URX_ISALNUM_SET = 2,
 250      URX_ISALPHA_SET = 3,
 251      URX_ISSPACE_SET = 4,
 252
 253      URX_GC_NORMAL,          // Sets for finding grapheme cluster boundaries.
 254      URX_GC_EXTEND,
 255      URX_GC_CONTROL,
 256      URX_GC_L,
 257      URX_GC_LV,
 258      URX_GC_LVT,
 259      URX_GC_V,
 260      URX_GC_T,
 261
 262      URX_LAST_SET,
 263
 264      URX_NEG_SET     = 0x800000          // Flag bit to reverse sense of set
 265                                          //   membership test.
 266 };
 267
 268
 269 //
 270 //  Match Engine State Stack Frame Layout.
 271 //
 272 struct REStackFrame {
 273     int32_t            fInputIdx;        // Position of next character in the input string
 274     int32_t            fPatIdx;          // Position of next Op in the compiled pattern
 275     int32_t            fExtra[2];        // Extra state, for capture group start/ends
 276                                          //   atomic parentheses, repeat counts, etc.
 277                                          //   Locations assigned at pattern compile time.
 278 };
 279
 280 //
 281 //  Start-Of-Match type.  Used by find() to quickly scan to positions where a
 282 //                        match might start before firing up the full match engine.
 283 //
 284 enum StartOfMatch {
 285     START_NO_INFO,             // No hint available.
 286     START_CHAR,                // Match starts with a literal code point.
 287     START_SET,                 // Match starts with something matching a set.
 288     START_START,               // Match starts at start of buffer only (^ or \A)
 289     START_LINE,                // Match starts with ^ in multi-line mode.
 290     START_STRING               // Match starts with a literal string.
 291 };
 292
 293 #define START_OF_MATCH_STR(v) ((v)==START_NO_INFO? "START_NO_INFO" : \
 294                                (v)==START_CHAR?    "START_CHAR"    : \
 295                                (v)==START_SET?     "START_SET"     : \
 296                                (v)==START_START?   "START_START"   : \
 297                                (v)==START_LINE?    "START_LINE"    : \
 298                                (v)==START_STRING?  "START_STRING"  : \
 299                                                    "ILLEGAL")
 300
 301
 302 //
 303 //  8 bit set, to fast-path latin-1 set membership tests.
 304 //
 305 struct Regex8BitSet : public UMemory {
 306     inline Regex8BitSet();
 307     inline void operator = (const Regex8BitSet &s);
 308     inline void init(const UnicodeSet *src);
 309     inline UBool contains(UChar32 c);
 310     inline void  add(UChar32 c);
 311     int8_t d[32];
 312 };
 313
 314 inline Regex8BitSet::Regex8BitSet() {
 315     uprv_memset(d, 0, sizeof(d));
 316 }
 317
 318 inline UBool Regex8BitSet::contains(UChar32 c) {
 319     // No bounds checking!  This is deliberate.
 320     return ((d[c>>3] & 1 <<(c&7)) != 0);
 321 };
 322
 323 inline void  Regex8BitSet::add(UChar32 c) {
 324     d[c>>3] |= 1 << (c&7);
 325 };
 326
 327 inline void Regex8BitSet::init(const UnicodeSet *s) {
 328     if (s != NULL) {
 329         for (int i=0; i<=255; i++) {
 330             if (s->contains(i)) {
 331                 this->add(i);
 332             }
 333         }
 334     }
 335 }
 336
 337 inline void Regex8BitSet::operator = (const Regex8BitSet &s) {
 338    uprv_memcpy(d, s.d, sizeof(d));
 339 }
 340
 341
 342 U_NAMESPACE_END
 343 #endif
 344