icuSources/i18n/regeximp.h

   1 //
   2 //   Copyright (C) 2002-2010 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,    // Force a backtrack, as if a match test had failed.
  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,   //   2 kinds, normal and non-greedy.
  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_UNIX   = 27,   // '.' operator in UNIX_LINES mode, only \n marks end of line.
 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_CARET_M_UNIX  = 30,   // '^' operator, test for start of line in multi-line
 106                                //      plus UNIX_LINES mode.
 107
 108      URX_RELOC_OPRND   = 31,   // Operand value in multi-operand ops that refers
 109                                //   back into compiled pattern code, and thus must
 110                                //   be relocated when inserting/deleting ops in code.
 111
 112      URX_STO_SP        = 32,   // Store the stack ptr.  Operand is location within
 113                                //   matcher data (not stack data) to store it.
 114      URX_LD_SP         = 33,   // Load the stack pointer.  Operand is location
 115                                //   to load from.
 116      URX_BACKREF       = 34,   // Back Reference.  Parameter is the index of the
 117                                //   capture group variables in the state stack frame.
 118      URX_STO_INP_LOC   = 35,   // Store the input location.  Operand is location
 119                                //   within the matcher stack frame.
 120      URX_JMPX          = 36,  // Conditional JMP.
 121                                //   First Operand:  JMP target location.
 122                                //   Second Operand:  Data location containing an
 123                                //     input position.  If current input position ==
 124                                //     saved input position, FAIL rather than taking
 125                                //     the JMP
 126      URX_LA_START      = 37,   // Starting a LookAround expression.
 127                                //   Save InputPos and SP in static data.
 128                                //   Operand:  Static data offset for the save
 129      URX_LA_END        = 38,   // Ending a Lookaround expression.
 130                                //   Restore InputPos and Stack to saved values.
 131                                //   Operand:  Static data offset for saved data.
 132      URX_ONECHAR_I     = 39,   // Test for case-insensitive match of a literal character.
 133                                //   Operand:  the literal char.
 134      URX_STRING_I      = 40,   // Case insensitive string compare.
 135                                //   First Operand:  Index of start of string in string literals
 136                                //   Second Operand (next word in compiled code):
 137                                //     the length of the string.
 138      URX_BACKREF_I     = 41,   // Case insensitive back reference.
 139                                //   Parameter is the index of the
 140                                //   capture group variables in the state stack frame.
 141      URX_DOLLAR_M      = 42,   // $ in multi-line mode.
 142      URX_CARET_M       = 43,   // ^ in multi-line mode.
 143      URX_LB_START      = 44,   // LookBehind Start.
 144                                //   Paramater is data location
 145      URX_LB_CONT       = 45,   // LookBehind Continue.
 146                                //   Param 0:  the data location
 147                                //   Param 1:  The minimum length of the look-behind match
 148                                //   Param 2:  The max length of the look-behind match
 149      URX_LB_END        = 46,   // LookBehind End.
 150                                //   Parameter is the data location.
 151                                //     Check that match ended at the right spot,
 152                                //     Restore original input string len.
 153      URX_LBN_CONT      = 47,   // Negative LookBehind Continue
 154                                //   Param 0:  the data location
 155                                //   Param 1:  The minimum length of the look-behind match
 156                                //   Param 2:  The max     length of the look-behind match
 157                                //   Param 3:  The pattern loc following the look-behind block.
 158      URX_LBN_END       = 48,   // Negative LookBehind end
 159                                //   Parameter is the data location.
 160                                //   Check that the match ended at the right spot.
 161      URX_STAT_SETREF_N = 49,   // Reference to a prebuilt set (e.g. \w), negated
 162                                //   Operand is index of set in array of sets.
 163      URX_LOOP_SR_I     = 50,   // Init a [set]* loop.
 164                                //   Operand is the sets index in array of user sets.
 165      URX_LOOP_C        = 51,   // Continue a [set]* or OneChar* loop.
 166                                //   Operand is a matcher static data location.
 167                                //   Must always immediately follow  LOOP_x_I instruction.
 168      URX_LOOP_DOT_I    = 52,   // .*, initialization of the optimized loop.
 169                                //   Operand value:
 170                                //      bit 0:
 171                                //         0:  Normal (. doesn't match new-line) mode.
 172                                //         1:  . matches new-line mode.
 173                                //      bit 1:  controls what new-lines are recognized by this operation.
 174                                //         0:  All Unicode New-lines
 175                                //         1:  UNIX_LINES, \u000a only.
 176      URX_BACKSLASH_BU  = 53,   // \b or \B in UREGEX_UWORD mode, using Unicode style
 177                                //   word boundaries.
 178      URX_DOLLAR_D      = 54,   // $ end of input test, in UNIX_LINES mode.
 179      URX_DOLLAR_MD     = 55    // $ end of input test, in MULTI_LINE and UNIX_LINES mode.
 180
 181 };
 182
 183 // Keep this list of opcode names in sync with the above enum
 184 //   Used for debug printing only.
 185 #define URX_OPCODE_NAMES       \
 186         "               ",     \
 187         "BACKTRACK",           \
 188         "END",                 \
 189         "ONECHAR",             \
 190         "STRING",              \
 191         "STRING_LEN",          \
 192         "STATE_SAVE",          \
 193         "NOP",                 \
 194         "START_CAPTURE",       \
 195         "END_CAPTURE",         \
 196         "URX_STATIC_SETREF",   \
 197         "SETREF",              \
 198         "DOTANY",              \
 199         "JMP",                 \
 200         "FAIL",                \
 201         "JMP_SAV",             \
 202         "BACKSLASH_B",         \
 203         "BACKSLASH_G",         \
 204         "JMP_SAV_X",           \
 205         "BACKSLASH_X",         \
 206         "BACKSLASH_Z",         \
 207         "DOTANY_ALL",          \
 208         "BACKSLASH_D",         \
 209         "CARET",               \
 210         "DOLLAR",              \
 211         "CTR_INIT",            \
 212         "CTR_INIT_NG",         \
 213         "DOTANY_UNIX",         \
 214         "CTR_LOOP",            \
 215         "CTR_LOOP_NG",         \
 216         "URX_CARET_M_UNIX",    \
 217         "RELOC_OPRND",         \
 218         "STO_SP",              \
 219         "LD_SP",               \
 220         "BACKREF",             \
 221         "STO_INP_LOC",         \
 222         "JMPX",                \
 223         "LA_START",            \
 224         "LA_END",              \
 225         "ONECHAR_I",           \
 226         "STRING_I",            \
 227         "BACKREF_I",           \
 228         "DOLLAR_M",            \
 229         "CARET_M",             \
 230         "LB_START",            \
 231         "LB_CONT",             \
 232         "LB_END",              \
 233         "LBN_CONT",            \
 234         "LBN_END",             \
 235         "STAT_SETREF_N",       \
 236         "LOOP_SR_I",           \
 237         "LOOP_C",              \
 238         "LOOP_DOT_I",          \
 239         "BACKSLASH_BU",        \
 240         "DOLLAR_D",            \
 241         "DOLLAR_MD"
 242
 243
 244 //
 245 //  Convenience macros for assembling and disassembling a compiled operation.
 246 //
 247 #define URX_BUILD(type, val) (int32_t)((type << 24) | (val))
 248 #define URX_TYPE(x)          ((uint32_t)(x) >> 24)
 249 #define URX_VAL(x)           ((x) & 0xffffff)
 250
 251
 252 //
 253 //  Access to Unicode Sets composite character properties
 254 //     The sets are accessed by the match engine for things like \w (word boundary)
 255 //
 256 enum {
 257      URX_ISWORD_SET  = 1,
 258      URX_ISALNUM_SET = 2,
 259      URX_ISALPHA_SET = 3,
 260      URX_ISSPACE_SET = 4,
 261
 262      URX_GC_NORMAL,          // Sets for finding grapheme cluster boundaries.
 263      URX_GC_EXTEND,
 264      URX_GC_CONTROL,
 265      URX_GC_L,
 266      URX_GC_LV,
 267      URX_GC_LVT,
 268      URX_GC_V,
 269      URX_GC_T,
 270
 271      URX_LAST_SET,
 272
 273      URX_NEG_SET     = 0x800000          // Flag bit to reverse sense of set
 274                                          //   membership test.
 275 };
 276
 277
 278 //
 279 //  Match Engine State Stack Frame Layout.
 280 //
 281 struct REStackFrame {
 282     // Header
 283     int64_t            fInputIdx;        // Position of next character in the input string
 284     int64_t            fPatIdx;          // Position of next Op in the compiled pattern
 285                                          // (int64_t for UVector64, values fit in an int32_t)
 286     // Remainder
 287     int64_t            fExtra[1];        // Extra state, for capture group start/ends
 288                                          //   atomic parentheses, repeat counts, etc.
 289                                          //   Locations assigned at pattern compile time.
 290                                          //   Variable-length array.
 291 };
 292 // number of UVector elements in the header
 293 #define RESTACKFRAME_HDRCOUNT 2
 294
 295 //
 296 //  Start-Of-Match type.  Used by find() to quickly scan to positions where a
 297 //                        match might start before firing up the full match engine.
 298 //
 299 enum StartOfMatch {
 300     START_NO_INFO,             // No hint available.
 301     START_CHAR,                // Match starts with a literal code point.
 302     START_SET,                 // Match starts with something matching a set.
 303     START_START,               // Match starts at start of buffer only (^ or \A)
 304     START_LINE,                // Match starts with ^ in multi-line mode.
 305     START_STRING               // Match starts with a literal string.
 306 };
 307
 308 #define START_OF_MATCH_STR(v) ((v)==START_NO_INFO? "START_NO_INFO" : \
 309                                (v)==START_CHAR?    "START_CHAR"    : \
 310                                (v)==START_SET?     "START_SET"     : \
 311                                (v)==START_START?   "START_START"   : \
 312                                (v)==START_LINE?    "START_LINE"    : \
 313                                (v)==START_STRING?  "START_STRING"  : \
 314                                                    "ILLEGAL")
 315
 316 //
 317 //  8 bit set, to fast-path latin-1 set membership tests.
 318 //
 319 struct Regex8BitSet : public UMemory {
 320     inline Regex8BitSet();
 321     inline void operator = (const Regex8BitSet &s);
 322     inline void init(const UnicodeSet *src);
 323     inline UBool contains(UChar32 c);
 324     inline void  add(UChar32 c);
 325     int8_t d[32];
 326 };
 327
 328 inline Regex8BitSet::Regex8BitSet() {
 329     uprv_memset(d, 0, sizeof(d));
 330 }
 331
 332 inline UBool Regex8BitSet::contains(UChar32 c) {
 333     // No bounds checking!  This is deliberate.
 334     return ((d[c>>3] & 1 <<(c&7)) != 0);
 335 }
 336
 337 inline void  Regex8BitSet::add(UChar32 c) {
 338     d[c>>3] |= 1 << (c&7);
 339 }
 340
 341 inline void Regex8BitSet::init(const UnicodeSet *s) {
 342     if (s != NULL) {
 343         for (int32_t i=0; i<=255; i++) {
 344             if (s->contains(i)) {
 345                 this->add(i);
 346             }
 347         }
 348     }
 349 }
 350
 351 inline void Regex8BitSet::operator = (const Regex8BitSet &s) {
 352    uprv_memcpy(d, s.d, sizeof(d));
 353 }
 354
 355 U_NAMESPACE_END
 356 #endif
 357