regexp.h

   1 /*    regexp.h
   2  *
   3  *    Copyright (C) 1993, 1994, 1996, 1997, 1999, 2000, 2001, 2003,
   4  *    2005, 2006, 2007, 2008 by Larry Wall and others
   5  *
   6  *    You may distribute under the terms of either the GNU General Public
   7  *    License or the Artistic License, as specified in the README file.
   8  *
   9  */
  10
  11 /*
  12  * Definitions etc. for regexp(3) routines.
  13  *
  14  * Caveat:  this is V8 regexp(3) [actually, a reimplementation thereof],
  15  * not the System V one.
  16  */
  17 #ifndef PLUGGABLE_RE_EXTENSION
  18 /* we don't want to include this stuff if we are inside of
  19    an external regex engine based on the core one - like re 'debug'*/
  20
  21 #  include "utf8.h"
  22
  23 typedef SSize_t regnode_offset;
  24
  25 struct regnode_meta {
  26     U8 type;
  27     U8 arg_len;
  28     U8 arg_len_varies;
  29     U8 off_by_arg;
  30 };
  31
  32 /* this ensures that on alignment sensitive platforms
  33  * this struct is aligned on 32 bit boundaries */
  34 union regnode_head {
  35     struct {
  36         union {
  37             U8 flags;
  38             U8 str_len_u8;
  39             U8 first_byte;
  40         } u_8;
  41         U8  type;
  42         U16 next_off;
  43     } data;
  44     U32 data_u32;
  45 };
  46
  47 struct regnode {
  48     union regnode_head head;
  49 };
  50
  51 typedef struct regnode regnode;
  52
  53 struct reg_substr_data;
  54
  55 struct reg_data;
  56
  57 struct regexp_engine;
  58 struct regexp;
  59
  60 struct reg_substr_datum {
  61     SSize_t min_offset; /* min pos (in chars) that substr must appear */
  62     SSize_t max_offset; /* max pos (in chars) that substr must appear */
  63     SV *substr;         /* non-utf8 variant */
  64     SV *utf8_substr;    /* utf8 variant */
  65     SSize_t end_shift;  /* how many fixed chars must end the string */
  66 };
  67 struct reg_substr_data {
  68     U8      check_ix;   /* index into data[] of check substr */
  69     struct reg_substr_datum data[3];    /* Actual array */
  70 };
  71
  72 #  ifdef PERL_ANY_COW
  73 #    define SV_SAVED_COPY   SV *saved_copy; /* If non-NULL, SV which is COW from original */
  74 #  else
  75 #    define SV_SAVED_COPY
  76 #  endif
  77
  78 /* offsets within a string of a particular /(.)/ capture
  79  * if you change this by adding new non-temporary fields
  80  * then be sure to update Perl_rxres_save() in pp_ctl.c */
  81 typedef struct regexp_paren_pair {
  82     SSize_t start;
  83     SSize_t end;
  84
  85     /* 'start_tmp' records a new opening position before the matching end
  86      * has been found, so that the old start and end values are still
  87      * valid, e.g.
  88      *    "abc" =~ /(.(?{print "[$1]"}))+/
  89      *outputs [][a][b]
  90      * This field is not part of the API.  */
  91     SSize_t start_tmp;
  92 } regexp_paren_pair;
  93
  94 #  if defined(PERL_IN_REGCOMP_ANY) || defined(PERL_IN_UTF8_C)
  95 #    define _invlist_union(a, b, output) _invlist_union_maybe_complement_2nd(a, b, FALSE, output)
  96 #    define _invlist_intersection(a, b, output) _invlist_intersection_maybe_complement_2nd(a, b, FALSE, output)
  97
  98 /* Subtracting b from a leaves in a everything that was there that isn't in b,
  99  * that is the intersection of a with b's complement */
 100 #    define _invlist_subtract(a, b, output) _invlist_intersection_maybe_complement_2nd(a, b, TRUE, output)
 101 #  endif
 102
 103 /* record the position of a (?{...}) within a pattern */
 104
 105 struct reg_code_block {
 106     STRLEN start;
 107     STRLEN end;
 108     OP     *block;
 109     REGEXP *src_regex;
 110 };
 111
 112 /* array of reg_code_block's plus header info */
 113
 114 struct reg_code_blocks {
 115     int refcnt; /* we may be pointed to from a regex and from the savestack */
 116     int  count; /* how many code block slots currently in use */
 117     int  size;  /* how many slots allocated in code_block[]  */
 118     struct reg_code_block *cb; /* array of reg_code_block's */
 119 };
 120
 121
 122 /*
 123 =for apidoc AyT||regexp
 124 The regexp/REGEXP struct, see L<perlreapi> for further documentation
 125 on the individual fields. The struct is ordered so that the most
 126 commonly used fields are placed at the start.
 127
 128 Any patch that adds items to this struct will need to include
 129 changes to F<sv.c> (C<Perl_re_dup()>) and F<regcomp.c>
 130 (C<pregfree()>). This involves freeing or cloning items in the
 131 regexp's data array based on the data item's type.
 132 =cut
 133 */
 134
 135 /* NOTE: There is a copy of this struct in the documentation in perlreapi.pod
 136  *       if you make ANY changes please make sure they are ALSO made there.
 137  */
 138 typedef struct regexp {
 139     /*----------------------------------------------------------------------
 140      * Fields required for compatibility with SV types
 141      */
 142     _XPV_HEAD;
 143
 144     /*----------------------------------------------------------------------
 145      * Operational fields
 146      */
 147
 148     const struct regexp_engine* engine; /* what engine created this regexp? */
 149     REGEXP *mother_re; /* what re is this a lightweight copy of? */
 150     HV *paren_names;   /* Optional hash of paren names */
 151
 152     /*----------------------------------------------------------------------
 153      * Information about the match that the perl core uses to manage things
 154      */
 155
 156     /* see comment in regcomp_internal.h about branch reset to understand
 157        the distinction between physical and logical capture buffers */
 158     U32 nparens;                    /* physical number of capture buffers */
 159     U32 logical_nparens;            /* logical_number of capture buffers */
 160     I32 *logical_to_parno;          /* map logical parno to first physcial */
 161     I32 *parno_to_logical;          /* map every physical parno to logical */
 162     I32 *parno_to_logical_next;     /* map every physical parno to the next
 163                                        physical with the same logical id */
 164
 165     SSize_t maxlen;    /* maximum possible number of chars in string to match */
 166     SSize_t minlen;    /* minimum possible number of chars in string to match */
 167     SSize_t minlenret; /* minimum possible number of chars in $& */
 168     STRLEN gofs;       /* chars left of pos that we search from */
 169                        /* substring data about strings that must appear in
 170                         * the final match, used for optimisations */
 171
 172     struct reg_substr_data *substrs;
 173
 174     /* private engine specific data */
 175
 176     void *pprivate;    /* Data private to the regex engine which
 177                         * created this object. */
 178
 179     U32 extflags;      /* Flags used both externally and internally */
 180     U32 intflags;      /* Engine Specific Internal flags */
 181
 182     /*----------------------------------------------------------------------
 183      * Data about the last/current match. These are modified during matching
 184      */
 185
 186     U32 lastparen;           /* highest close paren matched ($+) */
 187     U32 lastcloseparen;      /* last close paren matched ($^N) */
 188     regexp_paren_pair *offs; /* Array of offsets for (@-) and (@+) */
 189     char **recurse_locinput; /* used to detect infinite recursion, XXX: move to internal */
 190
 191     /*---------------------------------------------------------------------- */
 192
 193     /* offset from wrapped to the start of precomp */
 194     PERL_BITFIELD32 pre_prefix:4;
 195
 196     /* original flags used to compile the pattern, may differ from
 197      * extflags in various ways */
 198     PERL_BITFIELD32 compflags:9;
 199
 200     /*---------------------------------------------------------------------- */
 201
 202     char *subbeg;       /* saved or original string so \digit works forever. */
 203     SV_SAVED_COPY       /* If non-NULL, SV which is COW from original */
 204     SSize_t sublen;     /* Length of string pointed by subbeg */
 205     SSize_t suboffset;  /* byte offset of subbeg from logical start of str */
 206     SSize_t subcoffset; /* suboffset equiv, but in chars (for @-/@+) */
 207
 208     /*----------------------------------------------------------------------
 209      * More Operational fields
 210      */
 211
 212     CV *qr_anoncv;      /* the anon sub wrapped round qr/(?{..})/ */
 213 } regexp;
 214
 215
 216 #define RXp_PAREN_NAMES(rx) ((rx)->paren_names)
 217
 218 #define RXp_OFFS_START(rx,n) \
 219      RXp_OFFSp(rx)[(n)].start
 220
 221 #define RXp_OFFS_END(rx,n) \
 222      RXp_OFFSp(rx)[(n)].end
 223
 224 #define RXp_OFFS_VALID(rx,n) \
 225      (RXp_OFFSp(rx)[(n)].end != -1 && RXp_OFFSp(rx)[(n)].start != -1 )
 226
 227
 228 #define RX_OFFS_START(rx_sv,n)  RXp_OFFS_START(ReANY(rx_sv),n)
 229 #define RX_OFFS_END(rx_sv,n)    RXp_OFFS_END(ReANY(rx_sv),n)
 230 #define RX_OFFS_VALID(rx_sv,n)  RXp_OFFS_VALID(ReANY(rx_sv),n)
 231
 232 /*
 233
 234 =for apidoc mh||RX_OFFSp|const REGEXP * rx_sv
 235 Returns the RX_OFFS structure as a pointer.  This should NOT be used
 236 directly, and the structure it returns may change in future versions of
 237 perl.  Use one of the other RX_OFFS_xxx macros instead, which should be
 238 stable as Perl evolves. The 'p' suffix on the macro is meant to indicate
 239 both that the macro is "private" to the internals, and that it returns
 240 a pointer.
 241
 242 =for apidoc Amh||RX_OFFS_START|const REGEXP * rx_sv|U32 n
 243 Returns the start offset of the C<n>'th capture buffer, when
 244 C<n> is 0 it refers to the overall match as a whole. A value of
 245 -1 is returned if the C<n>'th capture buffer did not match.
 246
 247 =for apidoc Amh||RXp_OFFS_START|const regexp * rx|U32 n
 248 Same as RX_OFFS_START() but operates on a C<struct regexp *> instead of
 249 an C<SV *>.
 250
 251 =for apidoc Amh||RX_OFFS_END|const REGEXP * rx_sv|U32 n
 252 Returns the end offset of the C<n>'th capture buffer, when C<n> is 0 it
 253 refers to the overall match as a whole. A value of
 254 -1 is returned if the C<n>'th capture buffer did not match.
 255
 256 =for apidoc Amh||RXp_OFFS_END|const regexp * rx|U32 n
 257 Same as RX_OFFS_END() but operates on a C<struct regexp *> instead of
 258 an C<SV *>.
 259
 260 =for apidoc Amh||RX_OFFS_VALID|const REGEXP * rx_sv|U32 n
 261 Returns true if the C<n>'th offset buffer matched, false otherwise, when
 262 C<n> is 0 it refers to the overall match as a whole which should always
 263 return true.
 264
 265 =for apidoc Amh||RXp_OFFS_VALID|const regexp * rx|U32 n
 266 Same as RX_OFFS_VLAID() but operates on a C<struct regexp *> instead of
 267 an C<SV *>.
 268
 269 =cut
 270
 271 */
 272
 273 /* used for high speed searches */
 274 typedef struct re_scream_pos_data_s
 275 {
 276     char **scream_olds;         /* match pos */
 277     SSize_t *scream_pos;        /* Internal iterator of scream. */
 278 } re_scream_pos_data;
 279
 280 /* regexp_engine structure. This is the dispatch table for regexes.
 281  * Any regex engine implementation must be able to build one of these.
 282  */
 283 typedef struct regexp_engine {
 284     REGEXP* (*comp) (pTHX_ SV * const pattern, U32 flags);
 285     I32     (*exec) (pTHX_ REGEXP * const rx, char* stringarg, char* strend,
 286                      char* strbeg, SSize_t minend, SV* sv,
 287                      void* data, U32 flags);
 288     char*   (*intuit) (pTHX_
 289                         REGEXP * const rx,
 290                         SV *sv,
 291                         const char * const strbeg,
 292                         char *strpos,
 293                         char *strend,
 294                         const U32 flags,
 295                        re_scream_pos_data *data);
 296     SV*     (*checkstr) (pTHX_ REGEXP * const rx);
 297     void    (*rxfree) (pTHX_ REGEXP * const rx);
 298     void    (*numbered_buff_FETCH) (pTHX_ REGEXP * const rx, const I32 paren,
 299                                     SV * const sv);
 300     void    (*numbered_buff_STORE) (pTHX_ REGEXP * const rx, const I32 paren,
 301                                    SV const * const value);
 302     I32     (*numbered_buff_LENGTH) (pTHX_ REGEXP * const rx, const SV * const sv,
 303                                     const I32 paren);
 304     SV*     (*named_buff) (pTHX_ REGEXP * const rx, SV * const key,
 305                            SV * const value, const U32 flags);
 306     SV*     (*named_buff_iter) (pTHX_ REGEXP * const rx, const SV * const lastkey,
 307                                 const U32 flags);
 308     SV*     (*qr_package)(pTHX_ REGEXP * const rx);
 309 #  ifdef USE_ITHREADS
 310     void*   (*dupe) (pTHX_ REGEXP * const rx, CLONE_PARAMS *param);
 311 #  endif
 312     REGEXP* (*op_comp) (pTHX_ SV ** const patternp, int pat_count,
 313                     OP *expr, const struct regexp_engine* eng,
 314                     REGEXP *old_re,
 315                     bool *is_bare_re, U32 orig_rx_flags, U32 pm_flags);
 316 } regexp_engine;
 317
 318 /*
 319   These are passed to the numbered capture variable callbacks as the
 320   paren name. >= 1 is reserved for actual numbered captures, i.e. $1,
 321   $2 etc.
 322 */
 323 #  define RX_BUFF_IDX_CARET_PREMATCH  -5 /* ${^PREMATCH}  */
 324 #  define RX_BUFF_IDX_CARET_POSTMATCH -4 /* ${^POSTMATCH} */
 325 #  define RX_BUFF_IDX_CARET_FULLMATCH -3 /* ${^MATCH}     */
 326 #  define RX_BUFF_IDX_PREMATCH        -2 /* $` */
 327 #  define RX_BUFF_IDX_POSTMATCH       -1 /* $' */
 328 #  define RX_BUFF_IDX_FULLMATCH        0 /* $& */
 329
 330 /*
 331   Flags that are passed to the named_buff and named_buff_iter
 332   callbacks above. Those routines are called from universal.c via the
 333   Tie::Hash::NamedCapture interface for %+ and %- and the re::
 334   functions in the same file.
 335 */
 336
 337 /* The Tie::Hash::NamedCapture operation this is part of, if any */
 338 #  define RXapif_FETCH     0x0001
 339 #  define RXapif_STORE     0x0002
 340 #  define RXapif_DELETE    0x0004
 341 #  define RXapif_CLEAR     0x0008
 342 #  define RXapif_EXISTS    0x0010
 343 #  define RXapif_SCALAR    0x0020
 344 #  define RXapif_FIRSTKEY  0x0040
 345 #  define RXapif_NEXTKEY   0x0080
 346
 347 /* Whether %+ or %- is being operated on */
 348 #  define RXapif_ONE       0x0100 /* %+ */
 349 #  define RXapif_ALL       0x0200 /* %- */
 350
 351 /* Whether this is being called from a re:: function */
 352 #  define RXapif_REGNAME         0x0400
 353 #  define RXapif_REGNAMES        0x0800
 354 #  define RXapif_REGNAMES_COUNT  0x1000
 355
 356 /*
 357 =for apidoc Am|REGEXP *|SvRX|SV *sv
 358
 359 Convenience macro to get the REGEXP from a SV.  This is approximately
 360 equivalent to the following snippet:
 361
 362     if (SvMAGICAL(sv))
 363         mg_get(sv);
 364     if (SvROK(sv))
 365         sv = MUTABLE_SV(SvRV(sv));
 366     if (SvTYPE(sv) == SVt_REGEXP)
 367         return (REGEXP*) sv;
 368
 369 C<NULL> will be returned if a REGEXP* is not found.
 370
 371 =for apidoc Am|bool|SvRXOK|SV* sv
 372
 373 Returns a boolean indicating whether the SV (or the one it references)
 374 is a REGEXP.
 375
 376 If you want to do something with the REGEXP* later use SvRX instead
 377 and check for NULL.
 378
 379 =cut
 380 */
 381
 382 #  define SvRX(sv)   (Perl_get_re_arg(aTHX_ sv))
 383 #  define SvRXOK(sv) cBOOL(Perl_get_re_arg(aTHX_ sv))
 384
 385
 386 /* Flags stored in regexp->extflags
 387  * These are used by code external to the regexp engine
 388  *
 389  * Note that the flags whose names start with RXf_PMf_ are defined in
 390  * op_reg_common.h, being copied from the parallel flags of op_pmflags
 391  *
 392  * NOTE: if you modify any RXf flags you should run regen.pl or
 393  * regen/regcomp.pl so that regnodes.h is updated with the changes.
 394  *
 395  */
 396
 397 #  include "op_reg_common.h"
 398
 399 #  define RXf_PMf_STD_PMMOD     (RXf_PMf_MULTILINE|RXf_PMf_SINGLELINE|RXf_PMf_FOLD|RXf_PMf_EXTENDED|RXf_PMf_EXTENDED_MORE|RXf_PMf_NOCAPTURE)
 400
 401 #  define CASE_STD_PMMOD_FLAGS_PARSE_SET(pmfl, x_count)                       \
 402     case IGNORE_PAT_MOD:    *(pmfl) |= RXf_PMf_FOLD;       break;           \
 403     case MULTILINE_PAT_MOD: *(pmfl) |= RXf_PMf_MULTILINE;  break;           \
 404     case SINGLE_PAT_MOD:    *(pmfl) |= RXf_PMf_SINGLELINE; break;           \
 405     case XTENDED_PAT_MOD:   if (x_count == 0) {                             \
 406                                 *(pmfl) |= RXf_PMf_EXTENDED;                \
 407                                 *(pmfl) &= ~RXf_PMf_EXTENDED_MORE;          \
 408                             }                                               \
 409                             else {                                          \
 410                                 *(pmfl) |= RXf_PMf_EXTENDED                 \
 411                                           |RXf_PMf_EXTENDED_MORE;           \
 412                             }                                               \
 413                             (x_count)++; break;                             \
 414     case NOCAPTURE_PAT_MOD: *(pmfl) |= RXf_PMf_NOCAPTURE; break;
 415
 416 /* Note, includes charset ones, assumes 0 is the default for them */
 417 #  define STD_PMMOD_FLAGS_CLEAR(pmfl)                        \
 418     *(pmfl) &= ~(RXf_PMf_FOLD|RXf_PMf_MULTILINE|RXf_PMf_SINGLELINE|RXf_PMf_EXTENDED|RXf_PMf_EXTENDED_MORE|RXf_PMf_CHARSET|RXf_PMf_NOCAPTURE)
 419
 420 /* chars and strings used as regex pattern modifiers
 421  * Singular is a 'c'har, plural is a "string"
 422  *
 423  * NOTE, KEEPCOPY was originally 'k', but was changed to 'p' for preserve
 424  * for compatibility reasons with Regexp::Common which highjacked (?k:...)
 425  * for its own uses. So 'k' is out as well.
 426  */
 427 #  define DEFAULT_PAT_MOD      '^'    /* Short for all the default modifiers */
 428 #  define EXEC_PAT_MOD         'e'
 429 #  define KEEPCOPY_PAT_MOD     'p'
 430 #  define NOCAPTURE_PAT_MOD    'n'
 431 #  define ONCE_PAT_MOD         'o'
 432 #  define GLOBAL_PAT_MOD       'g'
 433 #  define CONTINUE_PAT_MOD     'c'
 434 #  define MULTILINE_PAT_MOD    'm'
 435 #  define SINGLE_PAT_MOD       's'
 436 #  define IGNORE_PAT_MOD       'i'
 437 #  define XTENDED_PAT_MOD      'x'
 438 #  define NONDESTRUCT_PAT_MOD  'r'
 439 #  define LOCALE_PAT_MOD       'l'
 440 #  define UNICODE_PAT_MOD      'u'
 441 #  define DEPENDS_PAT_MOD      'd'
 442 #  define ASCII_RESTRICT_PAT_MOD 'a'
 443
 444 #  define ONCE_PAT_MODS        "o"
 445 #  define KEEPCOPY_PAT_MODS    "p"
 446 #  define NOCAPTURE_PAT_MODS   "n"
 447 #  define EXEC_PAT_MODS        "e"
 448 #  define LOOP_PAT_MODS        "gc"
 449 #  define NONDESTRUCT_PAT_MODS "r"
 450 #  define LOCALE_PAT_MODS      "l"
 451 #  define UNICODE_PAT_MODS     "u"
 452 #  define DEPENDS_PAT_MODS     "d"
 453 #  define ASCII_RESTRICT_PAT_MODS "a"
 454 #  define ASCII_MORE_RESTRICT_PAT_MODS "aa"
 455
 456 /* This string is expected by regcomp.c to be ordered so that the first
 457  * character is the flag in bit RXf_PMf_STD_PMMOD_SHIFT of extflags; the next
 458  * character is bit +1, etc. */
 459 #  define STD_PAT_MODS        "msixxn"
 460
 461 #  define CHARSET_PAT_MODS    ASCII_RESTRICT_PAT_MODS DEPENDS_PAT_MODS LOCALE_PAT_MODS UNICODE_PAT_MODS
 462
 463 /* This string is expected by XS_re_regexp_pattern() in universal.c to be ordered
 464  * so that the first character is the flag in bit RXf_PMf_STD_PMMOD_SHIFT of
 465  * extflags; the next character is in bit +1, etc. */
 466 #  define INT_PAT_MODS    STD_PAT_MODS    KEEPCOPY_PAT_MODS
 467
 468 #  define EXT_PAT_MODS    ONCE_PAT_MODS   KEEPCOPY_PAT_MODS  NOCAPTURE_PAT_MODS
 469 #  define QR_PAT_MODS     STD_PAT_MODS    EXT_PAT_MODS     CHARSET_PAT_MODS
 470 #  define M_PAT_MODS      QR_PAT_MODS     LOOP_PAT_MODS
 471 #  define S_PAT_MODS      M_PAT_MODS      EXEC_PAT_MODS      NONDESTRUCT_PAT_MODS
 472
 473 /*
 474  * NOTE: if you modify any RXf flags you should run regen.pl or
 475  * regen/regcomp.pl so that regnodes.h is updated with the changes.
 476  *
 477  */
 478
 479 /*
 480   Set in Perl_pmruntime for a split. Will be used by regex engines to
 481   check whether they should set RXf_SKIPWHITE
 482 */
 483 #  define RXf_SPLIT   RXf_PMf_SPLIT
 484
 485 /* Currently the regex flags occupy a single 32-bit word.  Not all bits are
 486  * currently used.  The lower bits are shared with their corresponding PMf flag
 487  * bits, up to but not including _RXf_PMf_SHIFT_NEXT.  The unused bits
 488  * immediately follow; finally the used RXf-only (unshared) bits, so that the
 489  * highest bit in the word is used.  This gathers all the unused bits as a pool
 490  * in the middle, like so: 11111111111111110000001111111111
 491  * where the '1's represent used bits, and the '0's unused.  This design allows
 492  * us to allocate off one end of the pool if we need to add a shared bit, and
 493  * off the other end if we need a non-shared bit, without disturbing the other
 494  * bits.  This maximizes the likelihood of being able to change things without
 495  * breaking binary compatibility.
 496  *
 497  * To add shared bits, do so in op_reg_common.h.  This should change
 498  * _RXf_PMf_SHIFT_NEXT so that things won't compile.  Then come to regexp.h and
 499  * op.h and adjust the constant adders in the definitions of RXf_BASE_SHIFT and
 500  * Pmf_BASE_SHIFT down by the number of shared bits you added.  That's it.
 501  * Things should be binary compatible.  But if either of these gets to having
 502  * to subtract rather than add, leave at 0 and instead adjust all the entries
 503  * that are in terms of it.  But if the first one of those is already
 504  * RXf_BASE_SHIFT+0, there are no bits left, and a redesign is in order.
 505  *
 506  * To remove unshared bits, just delete its entry.  If you're where breaking
 507  * binary compatibility is ok to do, you might want to adjust things to move
 508  * the newly opened space so that it gets absorbed into the common pool.
 509  *
 510  * To add unshared bits, first use up any gaps in the middle.  Otherwise,
 511  * allocate off the low end until you get to RXf_BASE_SHIFT+0.  If that isn't
 512  * enough, move RXf_BASE_SHIFT down (if possible) and add the new bit at the
 513  * other end instead; this preserves binary compatibility.
 514  *
 515  * For the regexp bits, PL_reg_extflags_name[] in regnodes.h has a comment
 516  * giving which bits are used/unused */
 517
 518 #  define RXf_BASE_SHIFT (_RXf_PMf_SHIFT_NEXT + 2)
 519
 520 /* What we have seen */
 521 #  define RXf_NO_INPLACE_SUBST  (1U<<(RXf_BASE_SHIFT+2))
 522 #  define RXf_EVAL_SEEN         (1U<<(RXf_BASE_SHIFT+3))
 523
 524 /* Special */
 525 #  define RXf_UNBOUNDED_QUANTIFIER_SEEN   (1U<<(RXf_BASE_SHIFT+4))
 526 #  define RXf_CHECK_ALL         (1U<<(RXf_BASE_SHIFT+5))
 527
 528 /* UTF8 related */
 529 #  define RXf_MATCH_UTF8        (1U<<(RXf_BASE_SHIFT+6)) /* $1 etc are utf8 */
 530
 531 /* Intuit related */
 532 #  define RXf_USE_INTUIT_NOML   (1U<<(RXf_BASE_SHIFT+7))
 533 #  define RXf_USE_INTUIT_ML     (1U<<(RXf_BASE_SHIFT+8))
 534 #  define RXf_INTUIT_TAIL       (1U<<(RXf_BASE_SHIFT+9))
 535 #  define RXf_USE_INTUIT        (RXf_USE_INTUIT_NOML|RXf_USE_INTUIT_ML)
 536
 537 /* Do we have some sort of anchor? */
 538 #  define RXf_IS_ANCHORED       (1U<<(RXf_BASE_SHIFT+10))
 539
 540 /* Copy and tainted info */
 541 #  define RXf_COPY_DONE         (1U<<(RXf_BASE_SHIFT+11))
 542
 543 /* post-execution: $1 et al are tainted */
 544 #  define RXf_TAINTED_SEEN      (1U<<(RXf_BASE_SHIFT+12))
 545 /* this pattern was tainted during compilation */
 546 #  define RXf_TAINTED           (1U<<(RXf_BASE_SHIFT+13))
 547
 548 /* Flags indicating special patterns */
 549 #  define RXf_START_ONLY        (1U<<(RXf_BASE_SHIFT+14)) /* Pattern is /^/ */
 550 #  define RXf_SKIPWHITE         (1U<<(RXf_BASE_SHIFT+15)) /* Pattern is for a */
 551                                                           /* split " " */
 552 #  define RXf_WHITE             (1U<<(RXf_BASE_SHIFT+16)) /* Pattern is /\s+/ */
 553 #  define RXf_NULL              (1U<<(RXf_BASE_SHIFT+17)) /* Pattern is // */
 554
 555 /* See comments at the beginning of these defines about adding bits.  The
 556  * highest bit position should be used, so that if RXf_BASE_SHIFT gets
 557  * increased, the #error below will be triggered so that you will be reminded
 558  * to adjust things at the other end to keep the bit positions unchanged */
 559 #  if RXf_BASE_SHIFT+17 > 31
 560 #     error Too many RXf_PMf bits used.  See comments at beginning of these for what to do
 561 #  endif
 562
 563 /*
 564  * NOTE: if you modify any RXf flags you should run regen.pl or
 565  * regen/regcomp.pl so that regnodes.h is updated with the changes.
 566  *
 567  */
 568
 569 #  ifdef NO_TAINT_SUPPORT
 570 #    define RX_ISTAINTED(rx_sv)           0
 571 #    define RXp_ISTAINTED(prog)           0
 572 #    define RX_TAINT_on(rx_sv)            NOOP
 573 #    define RXp_MATCH_TAINTED(prog)       0
 574 #    define RX_MATCH_TAINTED(rx_sv)       0
 575 #    define RXp_MATCH_TAINTED_on(prog)    NOOP
 576 #    define RX_MATCH_TAINTED_on(rx_sv)    NOOP
 577 #    define RXp_MATCH_TAINTED_off(prog)   NOOP
 578 #    define RX_MATCH_TAINTED_off(rx_sv)   NOOP
 579 #  else
 580 #    define RX_ISTAINTED(rx_sv)           (RX_EXTFLAGS(rx_sv) & RXf_TAINTED)
 581 #    define RXp_ISTAINTED(prog)           (RXp_EXTFLAGS(prog) & RXf_TAINTED)
 582 #    define RX_TAINT_on(rx_sv)            (RX_EXTFLAGS(rx_sv) |= RXf_TAINTED)
 583 #    define RXp_MATCH_TAINTED(prog)       (RXp_EXTFLAGS(prog) & RXf_TAINTED_SEEN)
 584 #    define RX_MATCH_TAINTED(rx_sv)       (RX_EXTFLAGS(rx_sv) & RXf_TAINTED_SEEN)
 585 #    define RXp_MATCH_TAINTED_on(prog)    (RXp_EXTFLAGS(prog) |= RXf_TAINTED_SEEN)
 586 #    define RX_MATCH_TAINTED_on(rx_sv)    (RX_EXTFLAGS(rx_sv) |= RXf_TAINTED_SEEN)
 587 #    define RXp_MATCH_TAINTED_off(prog)   (RXp_EXTFLAGS(prog) &= ~RXf_TAINTED_SEEN)
 588 #    define RX_MATCH_TAINTED_off(rx_sv)   (RX_EXTFLAGS(rx_sv) &= ~RXf_TAINTED_SEEN)
 589 #  endif
 590
 591 #  define RXp_HAS_CUTGROUP(prog)          ((prog)->intflags & PREGf_CUTGROUP_SEEN)
 592
 593 #  define RX_MATCH_TAINTED_set(rx_sv, t)  ((t) \
 594                                         ? RX_MATCH_TAINTED_on(rx_sv) \
 595                                         : RX_MATCH_TAINTED_off(rx_sv))
 596
 597 #  define RXp_MATCH_COPIED(prog)          (RXp_EXTFLAGS(prog) & RXf_COPY_DONE)
 598 #  define RX_MATCH_COPIED(rx_sv)          (RX_EXTFLAGS(rx_sv) & RXf_COPY_DONE)
 599 #  define RXp_MATCH_COPIED_on(prog)       (RXp_EXTFLAGS(prog) |= RXf_COPY_DONE)
 600 #  define RX_MATCH_COPIED_on(rx_sv)       (RX_EXTFLAGS(rx_sv) |= RXf_COPY_DONE)
 601 #  define RXp_MATCH_COPIED_off(prog)      (RXp_EXTFLAGS(prog) &= ~RXf_COPY_DONE)
 602 #  define RX_MATCH_COPIED_off(rx_sv)      (RX_EXTFLAGS(rx_sv) &= ~RXf_COPY_DONE)
 603 #  define RX_MATCH_COPIED_set(rx_sv,t)    ((t) \
 604                                          ? RX_MATCH_COPIED_on(rx_sv) \
 605                                          : RX_MATCH_COPIED_off(rx_sv))
 606
 607 #  define RXp_EXTFLAGS(rx)                ((rx)->extflags)
 608 #  define RXp_COMPFLAGS(rx)               ((rx)->compflags)
 609
 610 /* For source compatibility. We used to store these explicitly.  */
 611 #  define RX_PRECOMP(rx_sv)              (RX_WRAPPED(rx_sv) \
 612                                             + ReANY(rx_sv)->pre_prefix)
 613 #  define RX_PRECOMP_const(rx_sv)        (RX_WRAPPED_const(rx_sv) \
 614                                             + ReANY(rx_sv)->pre_prefix)
 615 /* FIXME? Are we hardcoding too much here and constraining plugin extension
 616    writers? Specifically, the value 1 assumes that the wrapped version always
 617    has exactly one character at the end, a ')'. Will that always be true?  */
 618 #  define RX_PRELEN(rx_sv)                (RX_WRAPLEN(rx_sv) \
 619                                             - ReANY(rx_sv)->pre_prefix - 1)
 620
 621 #  define RX_WRAPPED(rx_sv)               SvPVX(rx_sv)
 622 #  define RX_WRAPPED_const(rx_sv)         SvPVX_const(rx_sv)
 623 #  define RX_WRAPLEN(rx_sv)               SvCUR(rx_sv)
 624 #  define RX_CHECK_SUBSTR(rx_sv)          (ReANY(rx_sv)->check_substr)
 625 #  define RX_REFCNT(rx_sv)                SvREFCNT(rx_sv)
 626 #  define RX_EXTFLAGS(rx_sv)              RXp_EXTFLAGS(ReANY(rx_sv))
 627 #  define RX_COMPFLAGS(rx_sv)             RXp_COMPFLAGS(ReANY(rx_sv))
 628 #  define RXp_ENGINE(prog)                ((prog)->engine)
 629 #  define RX_ENGINE(rx_sv)                (RXp_ENGINE(ReANY(rx_sv)))
 630 #  define RXp_SUBBEG(prog)                ((prog)->subbeg)
 631 #  define RX_SUBBEG(rx_sv)                (RXp_SUBBEG(ReANY(rx_sv)))
 632 #  define RXp_SUBOFFSET(prog)             ((prog)->suboffset)
 633 #  define RX_SUBOFFSET(rx_sv)             (RXp_SUBOFFSET(ReANY(rx_sv)))
 634 #  define RXp_SUBCOFFSET(prog)            ((prog)->subcoffset)
 635 #  define RX_SUBCOFFSET(rx_sv)            (RXp_SUBCOFFSET(ReANY(rx_sv)))
 636 #  define RXp_OFFSp(prog)                 ((prog)->offs)
 637 #  define RX_OFFSp(rx_sv)                 (RXp_OFFSp(ReANY(rx_sv)))
 638 #  define RXp_LOGICAL_NPARENS(prog)       ((prog)->logical_nparens)
 639 #  define RX_LOGICAL_NPARENS(rx_sv)       (RXp_LOGICAL_NPARENS(ReANY(rx_sv)))
 640 #  define RXp_LOGICAL_TO_PARNO(prog)      ((prog)->logical_to_parno)
 641 #  define RX_LOGICAL_TO_PARNO(rx_sv)      (RXp_LOGICAL_TO_PARNO(ReANY(rx_sv)))
 642 #  define RXp_PARNO_TO_LOGICAL(prog)      ((prog)->parno_to_logical)
 643 #  define RX_PARNO_TO_LOGICAL(rx_sv)      (RXp_PARNO_TO_LOGICAL(ReANY(rx_sv)))
 644 #  define RXp_PARNO_TO_LOGICAL_NEXT(prog) ((prog)->parno_to_logical_next)
 645 #  define RX_PARNO_TO_LOGICAL_NEXT(rx_sv) (RXp_PARNO_TO_LOGICAL_NEXT(ReANY(rx_sv)))
 646 #  define RXp_NPARENS(prog)               ((prog)->nparens)
 647 #  define RX_NPARENS(rx_sv)               (RXp_NPARENS(ReANY(rx_sv)))
 648 #  define RXp_SUBLEN(prog)                ((prog)->sublen)
 649 #  define RX_SUBLEN(rx_sv)                (RXp_SUBLEN(ReANY(rx_sv)))
 650 #  define RXp_MINLEN(prog)                ((prog)->minlen)
 651 #  define RX_MINLEN(rx_sv)                (RXp_MINLEN(ReANY(rx_sv)))
 652 #  define RXp_MINLENRET(prog)             ((prog)->minlenret)
 653 #  define RX_MINLENRET(rx_sv)             (RXp_MINLENRET(ReANY(rx_sv)))
 654 #  define RXp_GOFS(prog)                  ((prog)->gofs)
 655 #  define RX_GOFS(rx_sv)                  (RXp_GOFS(ReANY(rx_sv)))
 656 #  define RXp_LASTPAREN(prog)             ((prog)->lastparen)
 657 #  define RX_LASTPAREN(rx_sv)             (RXp_LASTPAREN(ReANY(rx_sv)))
 658 #  define RXp_LASTCLOSEPAREN(prog)        ((prog)->lastcloseparen)
 659 #  define RX_LASTCLOSEPAREN(rx_sv)        (RXp_LASTCLOSEPAREN(ReANY(rx_sv)))
 660 #  define RXp_SAVED_COPY(prog)            ((prog)->saved_copy)
 661 #  define RX_SAVED_COPY(rx_sv)            (RXp_SAVED_COPY(ReANY(rx_sv)))
 662 #  define RXp_SUBSTRS(prog)               ((prog)->substrs)
 663 #  define RX_SUBSTRS(rx_sv)               (RXp_SUBSTRS(ReANY(rx_sv)))
 664 #  define RXp_PPRIVATE(prog)              ((prog)->pprivate)
 665 #  define RX_PPRIVATE(rx_sv)              (RXp_PPRIVATE(ReANY(rx_sv)))
 666 #  define RXp_QR_ANONCV(prog)             ((prog)->qr_anoncv)
 667 #  define RX_QR_ANONCV(rx_sv)             (RXp_QR_ANONCV(ReANY(rx_sv)))
 668 #  define RXp_MOTHER_RE(prog)             ((prog)->mother_re)
 669 #  define RX_MOTHER_RE(rx_sv)             (RXp_MOTHER_RE(ReANY(rx_sv)))
 670 #  define RXp_PRE_PREFIX(prog)            ((prog)->pre_prefix)
 671 #  define RX_PRE_PREFIX(rx_sv)            (RXp_PRE_PREFIX(ReANY(rx_sv)))
 672
 673 /* last match was zero-length */
 674 #  define RXp_ZERO_LEN(prog) \
 675         (RXp_OFFS_START(prog,0) + (SSize_t)RXp_GOFS(prog) \
 676           == RXp_OFFS_END(prog,0))
 677 #  define RX_ZERO_LEN(rx_sv)              (RXp_ZERO_LEN(ReANY(rx_sv)))
 678
 679 #endif /* PLUGGABLE_RE_EXTENSION */
 680
 681 /* Stuff that needs to be included in the pluggable extension goes below here */
 682
 683 #include "regexp_constants.h"
 684
 685 #ifdef PERL_ANY_COW
 686 #  define RXp_MATCH_COPY_FREE(prog)                                 \
 687     STMT_START {                                                    \
 688         if (RXp_SAVED_COPY(prog)) {                                 \
 689             SV_CHECK_THINKFIRST_COW_DROP(RXp_SAVED_COPY(prog));     \
 690         }                                                           \
 691         if (RXp_MATCH_COPIED(prog)) {                               \
 692             Safefree(RXp_SUBBEG(prog));                             \
 693             RXp_MATCH_COPIED_off(prog);                             \
 694         }                                                           \
 695     } STMT_END
 696 #else
 697 #  define RXp_MATCH_COPY_FREE(prog)                     \
 698     STMT_START {                                        \
 699         if (RXp_MATCH_COPIED(prog)) {                   \
 700             Safefree(RXp_SUBBEG(prog));                 \
 701             RXp_MATCH_COPIED_off(prog);                 \
 702         }                                               \
 703     } STMT_END
 704 #endif
 705 #define RX_MATCH_COPY_FREE(rx_sv)       RXp_MATCH_COPY_FREE(ReANY(rx_sv))
 706
 707 #define RXp_MATCH_UTF8(prog)            (RXp_EXTFLAGS(prog) & RXf_MATCH_UTF8)
 708 #define RX_MATCH_UTF8(rx_sv)            (RX_EXTFLAGS(rx_sv) & RXf_MATCH_UTF8)
 709 #define RXp_MATCH_UTF8_on(prog)         (RXp_EXTFLAGS(prog) |= RXf_MATCH_UTF8)
 710 #define RX_MATCH_UTF8_on(rx_sv)         (RXp_MATCH_UTF8_on(ReANY(rx_sv)))
 711 #define RXp_MATCH_UTF8_off(prog)        (RXp_EXTFLAGS(prog) &= ~RXf_MATCH_UTF8)
 712 #define RX_MATCH_UTF8_off(rx_sv)        (RXp_MATCH_UTF8_off(ReANY(rx_sv))
 713 #define RXp_MATCH_UTF8_set(prog, t)     ((t) \
 714                                         ? RXp_MATCH_UTF8_on(prog) \
 715                                         : RXp_MATCH_UTF8_off(prog))
 716 #define RX_MATCH_UTF8_set(rx_sv, t)     (RXp_MATCH_UTF8_set(ReANY(rx_sv), t))
 717
 718 /* Whether the pattern stored at RX_WRAPPED is in UTF-8  */
 719 #define RX_UTF8(rx_sv)                  SvUTF8(rx_sv)
 720
 721
 722 /* bits in flags arg of Perl_regexec_flags() */
 723
 724 #define REXEC_COPY_STR  0x01    /* Need to copy the string for captures. */
 725 #define REXEC_CHECKED   0x02    /* re_intuit_start() already called. */
 726 #define REXEC_SCREAM    0x04    /* currently unused. */
 727 #define REXEC_IGNOREPOS 0x08    /* use stringarg, not pos(), for \G match */
 728 #define REXEC_NOT_FIRST 0x10    /* This is another iteration of //g:
 729                                    no need to copy string again */
 730
 731                                      /* under REXEC_COPY_STR, it's ok for the
 732                                         engine (modulo PL_sawamperand etc)
 733                                         to skip copying: ... */
 734 #define REXEC_COPY_SKIP_PRE  0x20    /* ...the $` part of the string, or */
 735 #define REXEC_COPY_SKIP_POST 0x40    /* ...the $' part of the string */
 736 #define REXEC_FAIL_ON_UNDERFLOW 0x80 /* fail the match if $& would start before
 737                                         the start pos (so s/.\G// would fail
 738                                         on second iteration */
 739
 740 #if defined(PERL_USE_GCC_BRACE_GROUPS)
 741 #  define ReREFCNT_inc(re)                                              \
 742     ({                                                                  \
 743         /* This is here to generate a casting warning if incorrect.  */ \
 744         REGEXP *const _rerefcnt_inc = (re);                             \
 745         assert(SvTYPE(_rerefcnt_inc) == SVt_REGEXP);                    \
 746         SvREFCNT_inc(_rerefcnt_inc);                                    \
 747         _rerefcnt_inc;                                                  \
 748     })
 749 #  define ReREFCNT_dec(re)                                              \
 750     ({                                                                  \
 751         /* This is here to generate a casting warning if incorrect.  */ \
 752         REGEXP *const _rerefcnt_dec = (re);                             \
 753         SvREFCNT_dec(_rerefcnt_dec);                                    \
 754     })
 755 #else
 756 #  define ReREFCNT_dec(re)      SvREFCNT_dec(re)
 757 #  define ReREFCNT_inc(re)      ((REGEXP *) SvREFCNT_inc(re))
 758 #endif
 759 #define ReANY(re)               Perl_ReANY((const REGEXP *)(re))
 760
 761 /* FIXME for plugins. */
 762
 763 #define FBMcf_TAIL_DOLLAR       1
 764 #define FBMcf_TAIL_DOLLARM      2
 765 #define FBMcf_TAIL_Z            4
 766 #define FBMcf_TAIL_z            8
 767 #define FBMcf_TAIL              (FBMcf_TAIL_DOLLAR|FBMcf_TAIL_DOLLARM|FBMcf_TAIL_Z|FBMcf_TAIL_z)
 768
 769 #define FBMrf_MULTILINE 1
 770
 771 struct regmatch_state;
 772 struct regmatch_slab;
 773
 774 /* like regmatch_info_aux, but contains extra fields only needed if the
 775  * pattern contains (?{}). If used, is snuck into the second slot in the
 776  * regmatch_state stack at the start of execution */
 777
 778 typedef struct {
 779     REGEXP *rx;
 780     PMOP   *old_op;           /* saved value of PL_op and ... */
 781     REGEXP *old_op_val;       /* ... saved value of PM_GETRE(PL_op) if any */
 782     REGEXP *old_regcurpm_val; /* saved value of PM_GETRE(PL_reg_curpm) */
 783     PMOP    *curpm;     /* saved PL_curpm */
 784 #ifdef PERL_ANY_COW
 785     SV      *saved_copy; /* saved saved_copy field from rex */
 786 #endif
 787     char    *subbeg;    /* saved subbeg     field from rex */
 788     STRLEN  sublen;     /* saved sublen     field from rex */
 789     STRLEN  suboffset;  /* saved suboffset  field from rex */
 790     STRLEN  subcoffset; /* saved subcoffset field from rex */
 791     SV      *sv;        /* $_  during (?{}) */
 792     MAGIC   *pos_magic; /* pos() magic attached to $_ */
 793     SSize_t pos;        /* the original value of pos() in pos_magic */
 794     U8      pos_flags;  /* flags to be restored; currently only MGf_BYTES*/
 795 } regmatch_info_aux_eval;
 796
 797
 798 /* fields that logically  live in regmatch_info, but which need cleaning
 799  * up on croak(), and so are instead are snuck into the first slot in
 800  * the regmatch_state stack at the start of execution */
 801
 802 typedef struct {
 803     regmatch_info_aux_eval *info_aux_eval;
 804     struct regmatch_state *old_regmatch_state; /* saved PL_regmatch_state */
 805     struct regmatch_slab  *old_regmatch_slab;  /* saved PL_regmatch_slab */
 806     char *poscache;     /* S-L cache of fail positions of WHILEMs */
 807 } regmatch_info_aux;
 808
 809
 810 /*
 811 =for apidoc Ay||regmatch_info
 812 Some basic information about the current match that is created by
 813 Perl_regexec_flags and then passed to regtry(), regmatch() etc.
 814 It is allocated as a local var on the stack, so nothing should be
 815 stored in it that needs preserving or clearing up on croak().
 816 For that, see the aux_info and aux_info_eval members of the
 817 regmatch_state union.
 818
 819 =cut
 820 */
 821
 822 typedef struct {
 823     REGEXP *prog;        /* the regex being executed */
 824     const char * strbeg; /* real start of string */
 825     char *strend;        /* one byte beyond last char of match string */
 826     char *till;          /* matches shorter than this fail (see minlen arg) */
 827     SV *sv;              /* the SV string currently being matched */
 828     char *ganch;         /* position of \G anchor */
 829     char *cutpoint;      /* (*COMMIT) position (if any) */
 830     regmatch_info_aux      *info_aux; /* extra fields that need cleanup */
 831     regmatch_info_aux_eval *info_aux_eval; /* extra saved state for (?{}) */
 832     I32  poscache_maxiter; /* how many whilems todo before S-L cache kicks in */
 833     I32  poscache_iter;    /* current countdown from _maxiter to zero */
 834     STRLEN poscache_size;  /* size of regmatch_info_aux.poscache */
 835     bool intuit;    /* re_intuit_start() is the top-level caller */
 836     bool is_utf8_pat;    /* regex is utf8 */
 837     bool is_utf8_target; /* string being matched is utf8 */
 838     bool warned; /* we have issued a recursion warning; no need for more */
 839 } regmatch_info;
 840
 841
 842 /* structures for holding and saving the state maintained by regmatch() */
 843
 844 #ifndef MAX_RECURSE_EVAL_NOCHANGE_DEPTH
 845 #  define MAX_RECURSE_EVAL_NOCHANGE_DEPTH 10
 846 #endif
 847
 848 /* The +1 is because everything matches itself, which isn't included in
 849  * MAX_FOLD_FROMS; the +2 is based on the current Unicode standards needs, and
 850  * is unlikely to change.  An assertion should fail in regexec.c if it is too
 851  * low.  It is needed for certain edge cases involving multi-character folds
 852  * when the first component also participates in a fold individually. */
 853 #define MAX_MATCHES (MAX_FOLD_FROMS + 1 + 2)
 854
 855 struct next_matchable_info {
 856     U8     first_byte_mask;
 857     U8     first_byte_anded;
 858     U32    mask32;
 859     U32    anded32;
 860     PERL_INT_FAST8_T count; /* Negative means not initialized */
 861     PERL_UINT_FAST8_T min_length;
 862     PERL_UINT_FAST8_T max_length;
 863     PERL_UINT_FAST8_T initial_definitive;
 864     PERL_UINT_FAST8_T initial_exact;
 865     PERL_UINT_FAST8_T lengths[MAX_MATCHES];
 866
 867     /* The size is from trial and error, and could change with new Unicode
 868      * standards, in which case there is an assertion that should start
 869      * failing.  This size could be calculated in one of the regen scripts
 870      * dealing with Unicode, but khw thinks the likelihood of it changing is
 871      * low enough that it isn't worth the effort. */
 872     U8 matches[18];
 873 };
 874
 875 typedef I32 CHECKPOINT;
 876
 877 typedef struct regmatch_state {
 878     int resume_state;           /* where to jump to on return */
 879     char *locinput;             /* where to backtrack in string on failure */
 880     char *loceol;
 881     U8 *sr0;                    /* position of start of script run, or NULL */
 882
 883     union {
 884
 885         /* the 'info_aux' and 'info_aux_eval' union members are cuckoos in
 886          * the nest. They aren't saved backtrack state; rather they
 887          * represent one or two extra chunks of data that need allocating
 888          * at the start of a match. These fields would logically live in
 889          * the regmatch_info struct, except that is allocated on the
 890          * C stack, and these fields are all things that require cleanup
 891          * after a croak(), when the stack is lost.
 892          * As a convenience, we just use the first 1 or 2 regmatch_state
 893          * slots to store this info, as we will be allocating a slab of
 894          * these anyway. Otherwise we'd have to malloc and then free them,
 895          * or allocate them on the save stack (where they will get
 896          * realloced if the save stack grows).
 897          * info_aux contains the extra fields that are always needed;
 898          * info_aux_eval contains extra fields that only needed if
 899          * the pattern contains code blocks
 900          * We split them into two separate structs to avoid increasing
 901          * the size of the union.
 902          */
 903
 904         regmatch_info_aux info_aux;
 905
 906         regmatch_info_aux_eval info_aux_eval;
 907
 908         /* this is a fake union member that matches the first element
 909          * of each member that needs to store positive backtrack
 910          * information */
 911         struct {
 912             struct regmatch_state *prev_yes_state;
 913         } yes;
 914
 915
 916         /* NOTE: Regarding 'cp' and 'lastcp' in the following structs...
 917          *
 918          * In the majority of cases we use 'cp' for the "normal"
 919          * checkpoint for paren saves, and 'lastcp' for the addtional
 920          * paren saves that are done only under RE_PESSIMISTIC_PARENS.
 921          *
 922          * There may be a few cases where both are used always.
 923          * Regardless they tend be used something like this:
 924          *
 925          *   ST.cp = regcppush(rex, 0, maxopenparen);
 926          *   REGCP_SET(ST.lastcp);
 927          *
 928          * thus ST.cp holds the checkpoint from before we push parens,
 929          * and ST.lastcp holds the checkpoint from afterwards.
 930          */
 931
 932         /* branchlike members */
 933         /* this is a fake union member that matches the first elements
 934          * of each member that needs to behave like a branch */
 935         struct {
 936             /* this first element must match u.yes */
 937             struct regmatch_state *prev_yes_state;
 938             U32         lastparen;
 939             U32         lastcloseparen;
 940             CHECKPOINT  cp;         /* see note above "struct branchlike" */
 941             CHECKPOINT  lastcp;     /* see note above "struct branchlike" */
 942             U16         before_paren;
 943             U16         after_paren;
 944
 945         } branchlike;
 946
 947         struct {
 948             /* the first elements must match u.branchlike */
 949             struct regmatch_state *prev_yes_state;
 950             U32         lastparen;
 951             U32         lastcloseparen;
 952             CHECKPOINT  cp;         /* see note above "struct branchlike" */
 953             CHECKPOINT  lastcp;     /* see note above "struct branchlike" */
 954             U16         before_paren;
 955             U16         after_paren;
 956
 957             regnode *next_branch;   /* next branch node */
 958         } branch;
 959
 960         struct {
 961             /* the first elements must match u.branchlike */
 962             struct regmatch_state *prev_yes_state;
 963             U32         lastparen;
 964             U32         lastcloseparen;
 965             CHECKPOINT  cp;         /* see note above "struct branchlike" */
 966             CHECKPOINT  lastcp;     /* see note above "struct branchlike" */
 967             U16         before_paren;
 968             U16         after_paren;
 969
 970             U32         accepted;   /* how many accepting states left */
 971             bool        longfold;   /* saw a fold with a 1->n char mapping */
 972             U16         *jump;      /* positive offsets from me */
 973             U16         *j_before_paren;
 974             U16         *j_after_paren;
 975             regnode     *me;        /* Which node am I - needed for jump tries*/
 976             U8          *firstpos;  /* pos in string of first trie match */
 977             U32         firstchars; /* len in chars of firstpos from start */
 978             U16         nextword;   /* next word to try */
 979             U16         topword;    /* longest accepted word */
 980         } trie;
 981
 982         /* special types - these members are used to store state for special
 983            regops like eval, if/then, lookaround and the markpoint state */
 984         struct {
 985             /* this first element must match u.yes */
 986             struct regmatch_state *prev_yes_state;
 987             struct regmatch_state *prev_curlyx;
 988             struct regmatch_state *prev_eval;
 989             REGEXP      *prev_rex;
 990             CHECKPOINT  cp;             /* see note above "struct branchlike" */
 991             CHECKPOINT  lastcp;         /* see note above "struct branchlike" */
 992             U32         close_paren;    /* which close bracket is our end (+1) */
 993             regnode     *B;             /* the node following us  */
 994             char        *prev_recurse_locinput;
 995         } eval;
 996
 997         struct {
 998             /* this first element must match u.yes */
 999             struct regmatch_state *prev_yes_state;
1000             I32     wanted;
1001             I32     logical;    /* saved copy of 'logical' var */
1002             U8      count;      /* number of beginning positions */
1003             char    *start;
1004             char    *end;
1005             regnode *me;        /* the IFMATCH/SUSPEND/UNLESSM node  */
1006             char    *prev_match_end;
1007         } ifmatch;              /* and SUSPEND/UNLESSM */
1008
1009         struct {
1010             /* this first element must match u.yes */
1011             struct regmatch_state *prev_yes_state;
1012             struct regmatch_state *prev_mark;
1013             SV      *mark_name;
1014             char    *mark_loc;
1015         } mark;
1016
1017         struct {
1018             int val;
1019         } keeper;
1020
1021         /* quantifiers - these members are used for storing state for
1022            the regops used to implement quantifiers */
1023         struct {
1024             /* this first element must match u.yes */
1025             struct regmatch_state *prev_yes_state;
1026             struct regmatch_state *prev_curlyx; /* previous cur_curlyx */
1027             regnode     *me;        /* the CURLYX node  */
1028             regnode     *B;         /* the B node in /A*B/  */
1029             CHECKPOINT  cp;         /* see note above "struct branchlike" */
1030             CHECKPOINT  lastcp;     /* see note above "struct branchlike" */
1031             bool        minmod;
1032             int         parenfloor; /* how far back to strip paren data */
1033
1034             /* these two are modified by WHILEM */
1035             int         count;      /* how many instances of A we've matched */
1036             char        *lastloc;   /* where previous A matched (0-len detect) */
1037         } curlyx;
1038
1039         struct {
1040             /* this first element must match u.yes */
1041             struct regmatch_state *prev_yes_state;
1042             struct regmatch_state *save_curlyx;
1043             CHECKPOINT  cp;             /* see note above "struct branchlike" */
1044             CHECKPOINT  lastcp;         /* see note above "struct branchlike" */
1045             char        *save_lastloc;  /* previous curlyx.lastloc */
1046             I32         cache_offset;
1047             I32         cache_mask;
1048         } whilem;
1049
1050         struct {
1051             /* this first element must match u.yes */
1052             struct regmatch_state *prev_yes_state;
1053             U32         lastparen;
1054             U32         lastcloseparen;
1055             CHECKPOINT  cp;         /* see note above "struct branchlike" */
1056             CHECKPOINT  lastcp;     /* see note above "struct branchlike" */
1057             I32         alen;       /* length of first-matched A string */
1058             I32         count;
1059             bool        minmod;
1060             regnode     *A, *B;     /* the nodes corresponding to /A*B/  */
1061             regnode     *me;        /* the curlym node */
1062             struct next_matchable_info Binfo;
1063         } curlym;
1064
1065         struct {
1066             U32         paren;
1067             U32         lastparen;
1068             U32         lastcloseparen;
1069             CHECKPOINT  cp;         /* see note above "struct branchlike" */
1070             CHECKPOINT  lastcp;     /* see note above "struct branchlike" */
1071             char        *maxpos;    /* highest possible point in string to match */
1072             char        *oldloc;    /* the previous locinput */
1073             int         count;
1074             int         min, max;   /* {m,n} */
1075             regnode     *A, *B;     /* the nodes corresponding to /A*B/  */
1076             struct next_matchable_info Binfo;
1077         } curly; /* and CURLYN/PLUS/STAR */
1078
1079         struct {
1080             CHECKPOINT  cp;
1081             CHECKPOINT  lastcp;
1082         } backref; /* REF and friends */
1083     } u;
1084 } regmatch_state;
1085
1086
1087
1088 /* how many regmatch_state structs to allocate as a single slab.
1089  * We do it in 4K blocks for efficiency. The "3" is 2 for the next/prev
1090  * pointers, plus 1 for any mythical malloc overhead. */
1091
1092 #define PERL_REGMATCH_SLAB_SLOTS \
1093     ((4096 - 3 * sizeof (void*)) / sizeof(regmatch_state))
1094
1095 typedef struct regmatch_slab {
1096     regmatch_state states[PERL_REGMATCH_SLAB_SLOTS];
1097     struct regmatch_slab *prev, *next;
1098 } regmatch_slab;
1099
1100
1101 #define REG_FETCH_ABSOLUTE 1
1102
1103 /*
1104  * ex: set ts=8 sts=4 sw=4 et:
1105  */