/* regcomp.h
*
* Copyright (C) 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
- * 2000, 2001, 2002, 2003, 2005 by Larry Wall and others
+ * 2000, 2001, 2002, 2003, 2005, 2006, 2007, by Larry Wall and others
*
* You may distribute under the terms of either the GNU General Public
* License or the Artistic License, as specified in the README file.
*
*/
+#include "regcharclass.h"
-typedef OP OP_4tree; /* Will be redefined later. */
-
-
+/* Convert branch sequences to more efficient trie ops? */
#define PERL_ENABLE_TRIE_OPTIMISATION 1
+
+/* Be really aggressive about optimising patterns with trie sequences? */
#define PERL_ENABLE_EXTENDED_TRIE_OPTIMISATION 1
+
+/* Should the optimiser take positive assertions into account? */
+#define PERL_ENABLE_POSITIVE_ASSERTION_STUDY 0
+
+/* Not for production use: */
#define PERL_ENABLE_EXPERIMENTAL_REGEX_OPTIMISATIONS 0
+/* Activate offsets code - set to if 1 to enable */
+#ifdef DEBUGGING
+#define RE_TRACK_PATTERN_OFFSETS
+#endif
+
/*
* The "internal use only" fields in regexp.h are present to pass info from
* compile to execute that permits the execute phase to run lots faster on
* stored negative.]
*/
+/* This is the stuff that used to live in regexp.h that was truly
+ private to the engine itself. It now lives here. */
+
+
+
+ typedef struct regexp_internal {
+ int name_list_idx; /* Optional data index of an array of paren names */
+ union {
+ U32 *offsets; /* offset annotations 20001228 MJD
+ data about mapping the program to the
+ string -
+ offsets[0] is proglen when this is used
+ */
+ U32 proglen;
+ } u;
+
+ regnode *regstclass; /* Optional startclass as identified or constructed
+ by the optimiser */
+ struct reg_data *data; /* Additional miscellaneous data used by the program.
+ Used to make it easier to clone and free arbitrary
+ data that the regops need. Often the ARG field of
+ a regop is an index into this structure */
+ struct reg_code_block *code_blocks;/* positions of literal (?{}) */
+ int num_code_blocks; /* size of code_blocks[] */
+ regnode program[1]; /* Unwarranted chumminess with compiler. */
+} regexp_internal;
+
+#define RXi_SET(x,y) (x)->pprivate = (void*)(y)
+#define RXi_GET(x) ((regexp_internal *)((x)->pprivate))
+#define RXi_GET_DECL(r,ri) regexp_internal *ri = RXi_GET(r)
+/*
+ * Flags stored in regexp->intflags
+ * These are used only internally to the regexp engine
+ *
+ * See regexp.h for flags used externally to the regexp engine
+ */
+#define RXp_INTFLAGS(rx) ((rx)->intflags)
+#define RX_INTFLAGS(prog) RXp_INTFLAGS(ReANY(prog))
+
+#define PREGf_SKIP 0x00000001
+#define PREGf_IMPLICIT 0x00000002 /* Converted .* to ^.* */
+#define PREGf_NAUGHTY 0x00000004 /* how exponential is this pattern? */
+#define PREGf_VERBARG_SEEN 0x00000008
+#define PREGf_CUTGROUP_SEEN 0x00000010
+#define PREGf_USE_RE_EVAL 0x00000020 /* compiled with "use re 'eval'" */
+/* these used to be extflags, but are now intflags */
+#define PREGf_NOSCAN 0x00000040
+#define PREGf_CANY_SEEN 0x00000080
+#define PREGf_GPOS_SEEN 0x00000100
+#define PREGf_GPOS_FLOAT 0x00000200
+
+#define PREGf_ANCH_BOL 0x00000400
+#define PREGf_ANCH_MBOL 0x00000800
+#define PREGf_ANCH_SBOL 0x00001000
+#define PREGf_ANCH_GPOS 0x00002000
+
+#define PREGf_ANCH (PREGf_ANCH_SBOL | PREGf_ANCH_GPOS | \
+ PREGf_ANCH_MBOL | PREGf_ANCH_BOL )
+
+/* this is where the old regcomp.h started */
+
struct regnode_string {
U8 str_len;
U8 type;
char string[1];
};
+/* Argument bearing node - workhorse,
+ arg1 is often for the data field */
struct regnode_1 {
U8 flags;
U8 type;
U32 arg1;
};
+/* Similar to a regnode_1 but with an extra signed argument */
+struct regnode_2L {
+ U8 flags;
+ U8 type;
+ U16 next_off;
+ U32 arg1;
+ I32 arg2;
+};
+
+/* 'Two field' -- Two 16 bit unsigned args */
struct regnode_2 {
U8 flags;
U8 type;
U16 arg2;
};
-#define ANYOF_BITMAP_SIZE 32 /* 256 b/(8 b/B) */
-#define ANYOF_CLASSBITMAP_SIZE 4 /* up to 32 (8*4) named classes */
-
+/* This give the number of code points that can be in the bitmap of an ANYOF
+ * node. The shift number must currently be one of: 8..12. It can't be less
+ * than 8 (256) because some code relies on it being at least that. Above 12
+ * (4096), and you start running into warnings that some data structure widths
+ * have been exceeded, though the test suite as of this writing still passes
+ * for up through 16, which is as high as anyone would ever want to go,
+ * encompassing all of the Unicode BMP, and thus including all the economically
+ * important world scripts. At 12 most of them are: including Arabic,
+ * Cyrillic, Greek, Hebrew, Indian subcontinent, Latin, and Thai; but not Han,
+ * Japanese, nor Korean. (The regarglen structure in regnodes.h is a U8, and
+ * the trie types TRIEC and AHOCORASICKC are larger than U8 for shift values
+ * below above 12.) Be sure to benchmark before changing, as larger sizes do
+ * significantly slow down the test suite */
+#define NUM_ANYOF_CODE_POINTS (1 << 8)
+
+#define ANYOF_BITMAP_SIZE (NUM_ANYOF_CODE_POINTS / 8) /* 8 bits/Byte */
+
+/* Note that these form structs which are supersets of the next smaller one, by
+ * appending fields. Alignment problems can occur if one of those optional
+ * fields requires stricter alignment than the base struct. And formal
+ * parameters that can really be two or more of the structs should be
+ * declared as the smallest one it could be. See commit message for
+ * 7dcac5f6a5195002b55c935ee1d67f67e1df280b. Regnode allocation is done
+ * without regard to alignment, and changing it to would also require changing
+ * the code that inserts and deletes regnodes. The basic single-argument
+ * regnode has a U32, which is what reganode() allocates as a unit. Therefore
+ * no field can require stricter alignment than U32. */
+
+/* also used by trie */
struct regnode_charclass {
U8 flags;
U8 type;
char bitmap[ANYOF_BITMAP_SIZE]; /* only compile-time */
};
-struct regnode_charclass_class { /* has [[:blah:]] classes */
- U8 flags; /* should have ANYOF_CLASS here */
+/* has runtime (locale) \d, \w, ..., [:posix:] classes */
+struct regnode_charclass_class {
+ U8 flags; /* ANYOF_MATCHES_POSIXL bit must go here */
+ U8 type;
+ U16 next_off;
+ U32 arg1;
+ char bitmap[ANYOF_BITMAP_SIZE]; /* both compile-time ... */
+ U32 classflags; /* and run-time */
+};
+
+/* A synthetic start class (SSC); is a regnode_charclass_posixl_fold, plus an
+ * extra SV*, used only during its construction and which is not used by
+ * regexec.c. Note that the 'next_off' field is unused, as the SSC stands
+ * alone, so there is never a next node. Also, there is no alignment issue,
+ * becase these are declared or allocated as a complete unit so the compiler
+ * takes care of alignment. This is unlike the other regnodes which are
+ * allocated in terms of multiples of a single-argument regnode. SSC nodes can
+ * have a pointer field because there is no alignment issue, and because it is
+ * set to NULL after construction, before any cloning of the pattern */
+struct regnode_ssc {
+ U8 flags; /* ANYOF_MATCHES_POSIXL bit must go here */
U8 type;
U16 next_off;
U32 arg1;
- char bitmap[ANYOF_BITMAP_SIZE]; /* both compile-time */
- char classflags[ANYOF_CLASSBITMAP_SIZE]; /* and run-time */
+ char bitmap[ANYOF_BITMAP_SIZE]; /* both compile-time ... */
+ U32 classflags; /* and run-time */
+
+ /* Auxiliary, only used during construction; NULL afterwards: list of code
+ * points matched */
+ SV* invlist;
};
+/* We take advantage of 'next_off' not otherwise being used in the SSC by
+ * actually using it: by setting it to 1. This allows us to test and
+ * distinguish between an SSC and other ANYOF node types, as 'next_off' cannot
+ * otherwise be 1, because it is the offset to the next regnode expressed in
+ * units of regnodes. Since an ANYOF node contains extra fields, it adds up
+ * to 12 regnode units on 32-bit systems, (hence the minimum this can be (if
+ * not 0) is 11 there. Even if things get tightly packed on a 64-bit system,
+ * it still would be more than 1. */
+#define set_ANYOF_SYNTHETIC(n) STMT_START{ OP(n) = ANYOF; \
+ NEXT_OFF(n) = 1; \
+ } STMT_END
+#define is_ANYOF_SYNTHETIC(n) (OP(n) == ANYOF && NEXT_OFF(n) == 1)
+
/* XXX fix this description.
Impose a limit of REG_INFTY on various pattern matching operations
to limit stack growth and to avoid "infinite" recursions.
#define ARG(p) ARG_VALUE(ARG_LOC(p))
#define ARG1(p) ARG_VALUE(ARG1_LOC(p))
#define ARG2(p) ARG_VALUE(ARG2_LOC(p))
+#define ARG2L(p) ARG_VALUE(ARG2L_LOC(p))
+
#define ARG_SET(p, val) ARG__SET(ARG_LOC(p), (val))
#define ARG1_SET(p, val) ARG__SET(ARG1_LOC(p), (val))
#define ARG2_SET(p, val) ARG__SET(ARG2_LOC(p), (val))
+#define ARG2L_SET(p, val) ARG__SET(ARG2L_LOC(p), (val))
#undef NEXT_OFF
#undef NODE_ALIGN
#undef STRING
#define OP(p) ((p)->type)
+#define FLAGS(p) ((p)->flags) /* Caution: Doesn't apply to all \
+ regnode types. For some, it's the \
+ character set of the regnode */
#define OPERAND(p) (((struct regnode_string *)p)->string)
#define MASK(p) ((char*)OPERAND(p))
#define STR_LEN(p) (((struct regnode_string *)p)->str_len)
#define ARG_LOC(p) (((struct regnode_1 *)p)->arg1)
#define ARG1_LOC(p) (((struct regnode_2 *)p)->arg1)
#define ARG2_LOC(p) (((struct regnode_2 *)p)->arg2)
+#define ARG2L_LOC(p) (((struct regnode_2L *)p)->arg2)
+
#define NODE_STEP_REGNODE 1 /* sizeof(regnode)/sizeof(regnode) */
#define EXTRA_STEP_2ARGS EXTRA_SIZE(struct regnode_2)
#define REG_MAGIC 0234
-#define SIZE_ONLY (RExC_emit == &PL_regdummy)
-
-/* Flags for node->flags of ANYOF */
-
-#define ANYOF_CLASS 0x08 /* has [[:blah:]] classes */
-#define ANYOF_INVERT 0x04
-#define ANYOF_FOLD 0x02
-#define ANYOF_LOCALE 0x01
+#define SIZE_ONLY (RExC_emit == (regnode *) & RExC_emit_dummy)
+#define PASS1 SIZE_ONLY
+#define PASS2 (! SIZE_ONLY)
+
+/* If the bitmap fully represents what this ANYOF node can match, the
+ * ARG is set to this special value (since 0, 1, ... are legal, but will never
+ * reach this high). */
+#define ANYOF_ONLY_HAS_BITMAP ((U32) -1)
+
+/* Flags for node->flags of ANYOF. These are in short supply, with none
+ * currently available. The ABOVE_BITMAP_ALL bit could be freed up
+ * by resorting to creating a swash containing everything above 255. This
+ * introduces a performance penalty. An option that wouldn't slow things down
+ * would be to split one of the two LOC flags out into a separate
+ * node, like what was done with ANYOF_NON_UTF8_NON_ASCII_ALL in commit
+ * 34fdef848b1687b91892ba55e9e0c3430e0770f6 (but which was reverted because it
+ * wasn't the best option available at the time), and using a LOC flag is
+ * probably better than that commit anyway. But it could be reinstated if we
+ * need a bit. The LOC flags are only for /l nodes; the reverted commit was
+ * only for /d, so there are no combinatorial issues. The LOC flag to use is
+ * probably the POSIXL one.
+ * Several flags are not used in synthetic start class (SSC) nodes, so could be
+ * shared should new flags be needed for SSCs, like SSC_MATCHES_EMPTY_STRING
+ * now. */
+
+/* regexec.c is expecting this to be in the low bit */
+#define ANYOF_INVERT 0x01
+
+/* For the SSC node only, which cannot be inverted, so is shared with that bit.
+ * This is used only during regex compilation. */
+#define SSC_MATCHES_EMPTY_STRING ANYOF_INVERT
+
+/* Are there things outside the bitmap that will match only if the target
+ * string is encoded in UTF-8? (This is not set if ANYOF_ABOVE_BITMAP_ALL is
+ * set) */
+#define ANYOF_HAS_UTF8_NONBITMAP_MATCHES 0x02
+
+/* The fold is calculated and stored in the bitmap where possible at compile
+ * time. However under locale, the actual folding varies depending on
+ * what the locale is at the time of execution, so it has to be deferred until
+ * then */
+#define ANYOF_LOC_FOLD 0x04
+
+/* Set if this is a regnode_charclass_posixl vs a regnode_charclass. This
+ * is used for runtime \d, \w, [:posix:], ..., which are used only in locale
+ * and the optimizer's synthetic start class. Non-locale \d, etc are resolved
+ * at compile-time */
+#define ANYOF_MATCHES_POSIXL 0x08
+
+/* Should we raise a warning if matching against an above-Unicode code point?
+ * */
+#define ANYOF_WARN_SUPER 0x10
+
+/* Can match something outside the bitmap that isn't in utf8 */
+#define ANYOF_HAS_NONBITMAP_NON_UTF8_MATCHES 0x20
+
+/* Matches every code point NUM_ANYOF_CODE_POINTS and above*/
+#define ANYOF_MATCHES_ALL_ABOVE_BITMAP 0x40
+
+/* Match all Latin1 characters that aren't ASCII when the target string is not
+ * in utf8. */
+#define ANYOF_MATCHES_ALL_NON_UTF8_NON_ASCII 0x80
+
+#define ANYOF_FLAGS_ALL (0xff)
+
+#define ANYOF_LOCALE_FLAGS (ANYOF_LOC_FOLD | ANYOF_MATCHES_POSIXL)
+
+/* These are the flags that apply to both regular ANYOF nodes and synthetic
+ * start class nodes during construction of the SSC. During finalization of
+ * the SSC, other of the flags could be added to it */
+#define ANYOF_COMMON_FLAGS (ANYOF_WARN_SUPER|ANYOF_HAS_UTF8_NONBITMAP_MATCHES)
-/* Used for regstclass only */
-#define ANYOF_EOS 0x10 /* Can match an empty string too */
-
-/* There is a character or a range past 0xff */
-#define ANYOF_UNICODE 0x20
-#define ANYOF_UNICODE_ALL 0x40 /* Can match any char past 0xff */
+/* Character classes for node->classflags of ANYOF */
+/* Should be synchronized with a table in regprop() */
+/* 2n should be the normal one, paired with its complement at 2n+1 */
+
+#define ANYOF_ALPHA ((_CC_ALPHA) * 2)
+#define ANYOF_NALPHA ((ANYOF_ALPHA) + 1)
+#define ANYOF_ALPHANUMERIC ((_CC_ALPHANUMERIC) * 2) /* [[:alnum:]] isalnum(3), utf8::IsAlnum */
+#define ANYOF_NALPHANUMERIC ((ANYOF_ALPHANUMERIC) + 1)
+#define ANYOF_ASCII ((_CC_ASCII) * 2)
+#define ANYOF_NASCII ((ANYOF_ASCII) + 1)
+#define ANYOF_BLANK ((_CC_BLANK) * 2) /* GNU extension: space and tab: non-vertical space */
+#define ANYOF_NBLANK ((ANYOF_BLANK) + 1)
+#define ANYOF_CASED ((_CC_CASED) * 2) /* Pseudo class for [:lower:] or
+ [:upper:] under /i */
+#define ANYOF_NCASED ((ANYOF_CASED) + 1)
+#define ANYOF_CNTRL ((_CC_CNTRL) * 2)
+#define ANYOF_NCNTRL ((ANYOF_CNTRL) + 1)
+#define ANYOF_DIGIT ((_CC_DIGIT) * 2) /* \d */
+#define ANYOF_NDIGIT ((ANYOF_DIGIT) + 1)
+#define ANYOF_GRAPH ((_CC_GRAPH) * 2)
+#define ANYOF_NGRAPH ((ANYOF_GRAPH) + 1)
+#define ANYOF_LOWER ((_CC_LOWER) * 2)
+#define ANYOF_NLOWER ((ANYOF_LOWER) + 1)
+#define ANYOF_PRINT ((_CC_PRINT) * 2)
+#define ANYOF_NPRINT ((ANYOF_PRINT) + 1)
+#define ANYOF_PSXSPC ((_CC_PSXSPC) * 2) /* POSIX space: \s plus the vertical tab */
+#define ANYOF_NPSXSPC ((ANYOF_PSXSPC) + 1)
+#define ANYOF_PUNCT ((_CC_PUNCT) * 2)
+#define ANYOF_NPUNCT ((ANYOF_PUNCT) + 1)
+#define ANYOF_SPACE ((_CC_SPACE) * 2) /* \s */
+#define ANYOF_NSPACE ((ANYOF_SPACE) + 1)
+#define ANYOF_UPPER ((_CC_UPPER) * 2)
+#define ANYOF_NUPPER ((ANYOF_UPPER) + 1)
+#define ANYOF_WORDCHAR ((_CC_WORDCHAR) * 2) /* \w, PL_utf8_alnum, utf8::IsWord, ALNUM */
+#define ANYOF_NWORDCHAR ((ANYOF_WORDCHAR) + 1)
+#define ANYOF_XDIGIT ((_CC_XDIGIT) * 2)
+#define ANYOF_NXDIGIT ((ANYOF_XDIGIT) + 1)
+
+/* pseudo classes below this, not stored in the class bitmap, but used as flags
+ during compilation of char classes */
+
+#define ANYOF_VERTWS ((_CC_VERTSPACE) * 2)
+#define ANYOF_NVERTWS ((ANYOF_VERTWS)+1)
+
+/* It is best if this is the last one, as all above it are stored as bits in a
+ * bitmap, and it isn't part of that bitmap */
+#if _CC_VERTSPACE != _HIGHEST_REGCOMP_DOT_H_SYNC
+# error Problem with handy.h _HIGHEST_REGCOMP_DOT_H_SYNC #define
+#endif
-/* size of node is large (includes class pointer) */
-#define ANYOF_LARGE 0x80
+#define ANYOF_POSIXL_MAX (ANYOF_VERTWS) /* So upper loop limit is written:
+ * '< ANYOF_MAX'
+ * Hence doesn't include VERTWS, as that
+ * is a pseudo class */
+#define ANYOF_MAX ANYOF_POSIXL_MAX
-/* Are there any runtime flags on in this node? */
-#define ANYOF_RUNTIME(s) (ANYOF_FLAGS(s) & 0x0f)
+#if (ANYOF_POSIXL_MAX > 32) /* Must fit in 32-bit word */
+# error Problem with handy.h _CC_foo #defines
+#endif
-#define ANYOF_FLAGS_ALL 0xff
+#define ANYOF_HORIZWS ((ANYOF_POSIXL_MAX)+2) /* = (ANYOF_NVERTWS + 1) */
+#define ANYOF_NHORIZWS ((ANYOF_POSIXL_MAX)+3)
-/* Character classes for node->classflags of ANYOF */
-/* Should be synchronized with a table in regprop() */
-/* 2n should pair with 2n+1 */
-
-#define ANYOF_ALNUM 0 /* \w, PL_utf8_alnum, utf8::IsWord, ALNUM */
-#define ANYOF_NALNUM 1
-#define ANYOF_SPACE 2 /* \s */
-#define ANYOF_NSPACE 3
-#define ANYOF_DIGIT 4
-#define ANYOF_NDIGIT 5
-#define ANYOF_ALNUMC 6 /* isalnum(3), utf8::IsAlnum, ALNUMC */
-#define ANYOF_NALNUMC 7
-#define ANYOF_ALPHA 8
-#define ANYOF_NALPHA 9
-#define ANYOF_ASCII 10
-#define ANYOF_NASCII 11
-#define ANYOF_CNTRL 12
-#define ANYOF_NCNTRL 13
-#define ANYOF_GRAPH 14
-#define ANYOF_NGRAPH 15
-#define ANYOF_LOWER 16
-#define ANYOF_NLOWER 17
-#define ANYOF_PRINT 18
-#define ANYOF_NPRINT 19
-#define ANYOF_PUNCT 20
-#define ANYOF_NPUNCT 21
-#define ANYOF_UPPER 22
-#define ANYOF_NUPPER 23
-#define ANYOF_XDIGIT 24
-#define ANYOF_NXDIGIT 25
-#define ANYOF_PSXSPC 26 /* POSIX space: \s plus the vertical tab */
-#define ANYOF_NPSXSPC 27
-#define ANYOF_BLANK 28 /* GNU extension: space and tab: non-vertical space */
-#define ANYOF_NBLANK 29
-
-#define ANYOF_MAX 32
+#define ANYOF_UNIPROP ((ANYOF_POSIXL_MAX)+4) /* Used to indicate a Unicode
+ property: \p{} or \P{} */
/* Backward source code compatibility. */
#define ANYOF_NALNUML ANYOF_NALNUM
#define ANYOF_SPACEL ANYOF_SPACE
#define ANYOF_NSPACEL ANYOF_NSPACE
+#define ANYOF_ALNUM ANYOF_WORDCHAR
+#define ANYOF_NALNUM ANYOF_NWORDCHAR
/* Utility macros for the bitmap and classes of ANYOF */
#define ANYOF_SIZE (sizeof(struct regnode_charclass))
-#define ANYOF_CLASS_SIZE (sizeof(struct regnode_charclass_class))
+#define ANYOF_POSIXL_SIZE (sizeof(regnode_charclass_posixl))
+#define ANYOF_CLASS_SIZE ANYOF_POSIXL_SIZE
#define ANYOF_FLAGS(p) ((p)->flags)
-#define ANYOF_BIT(c) (1 << ((c) & 7))
+#define ANYOF_BIT(c) (1U << ((c) & 7))
-#define ANYOF_CLASS_BYTE(p, c) (((struct regnode_charclass_class*)(p))->classflags[((c) >> 3) & 3])
-#define ANYOF_CLASS_SET(p, c) (ANYOF_CLASS_BYTE(p, c) |= ANYOF_BIT(c))
-#define ANYOF_CLASS_CLEAR(p, c) (ANYOF_CLASS_BYTE(p, c) &= ~ANYOF_BIT(c))
-#define ANYOF_CLASS_TEST(p, c) (ANYOF_CLASS_BYTE(p, c) & ANYOF_BIT(c))
+#define ANYOF_POSIXL_SET(p, c) (((regnode_charclass_posixl*) (p))->classflags |= (1U << (c)))
+#define ANYOF_CLASS_SET(p, c) ANYOF_POSIXL_SET((p), (c))
-#define ANYOF_CLASS_ZERO(ret) Zero(((struct regnode_charclass_class*)(ret))->classflags, ANYOF_CLASSBITMAP_SIZE, char)
-#define ANYOF_BITMAP_ZERO(ret) Zero(((struct regnode_charclass*)(ret))->bitmap, ANYOF_BITMAP_SIZE, char)
+#define ANYOF_POSIXL_CLEAR(p, c) (((regnode_charclass_posixl*) (p))->classflags &= ~ (1U <<(c)))
+#define ANYOF_CLASS_CLEAR(p, c) ANYOF_POSIXL_CLEAR((p), (c))
+
+#define ANYOF_POSIXL_TEST(p, c) (((regnode_charclass_posixl*) (p))->classflags & (1U << (c)))
+#define ANYOF_CLASS_TEST(p, c) ANYOF_POSIXL_TEST((p), (c))
+
+#define ANYOF_POSIXL_ZERO(ret) STMT_START { ((regnode_charclass_posixl*) (ret))->classflags = 0; } STMT_END
+#define ANYOF_CLASS_ZERO(ret) ANYOF_POSIXL_ZERO(ret)
+
+/* Shifts a bit to get, eg. 0x4000_0000, then subtracts 1 to get 0x3FFF_FFFF */
+#define ANYOF_POSIXL_SETALL(ret) STMT_START { ((regnode_charclass_posixl*) (ret))->classflags = ((1U << ((ANYOF_POSIXL_MAX) - 1))) - 1; } STMT_END
+#define ANYOF_CLASS_SETALL(ret) ANYOF_POSIXL_SETALL(ret)
+
+#define ANYOF_POSIXL_TEST_ANY_SET(p) \
+ ((ANYOF_FLAGS(p) & ANYOF_MATCHES_POSIXL) \
+ && (((regnode_charclass_posixl*)(p))->classflags))
+#define ANYOF_CLASS_TEST_ANY_SET(p) ANYOF_POSIXL_TEST_ANY_SET(p)
+/* Since an SSC always has this field, we don't have to test for that; nor do
+ * we want to because the bit isn't set for SSC during its construction */
+#define ANYOF_POSIXL_SSC_TEST_ANY_SET(p) \
+ cBOOL(((regnode_ssc*)(p))->classflags)
+#define ANYOF_POSIXL_SSC_TEST_ALL_SET(p) /* Are all bits set? */ \
+ (((regnode_ssc*) (p))->classflags \
+ == ((1U << ((ANYOF_POSIXL_MAX) - 1))) - 1)
+
+#define ANYOF_POSIXL_TEST_ALL_SET(p) \
+ ((ANYOF_FLAGS(p) & ANYOF_MATCHES_POSIXL) \
+ && ((regnode_charclass_posixl*) (p))->classflags \
+ == ((1U << ((ANYOF_POSIXL_MAX) - 1))) - 1)
+
+#define ANYOF_POSIXL_OR(source, dest) STMT_START { (dest)->classflags |= (source)->classflags ; } STMT_END
+#define ANYOF_CLASS_OR(source, dest) ANYOF_POSIXL_OR((source), (dest))
+
+#define ANYOF_POSIXL_AND(source, dest) STMT_START { (dest)->classflags &= (source)->classflags ; } STMT_END
+
+#define ANYOF_BITMAP_ZERO(ret) Zero(((struct regnode_charclass*)(ret))->bitmap, ANYOF_BITMAP_SIZE, char)
#define ANYOF_BITMAP(p) (((struct regnode_charclass*)(p))->bitmap)
-#define ANYOF_BITMAP_BYTE(p, c) (ANYOF_BITMAP(p)[((c) >> 3) & 31])
+#define ANYOF_BITMAP_BYTE(p, c) (ANYOF_BITMAP(p)[(((U8)(c)) >> 3) & 31])
#define ANYOF_BITMAP_SET(p, c) (ANYOF_BITMAP_BYTE(p, c) |= ANYOF_BIT(c))
#define ANYOF_BITMAP_CLEAR(p,c) (ANYOF_BITMAP_BYTE(p, c) &= ~ANYOF_BIT(c))
-#define ANYOF_BITMAP_TEST(p, c) (ANYOF_BITMAP_BYTE(p, c) & ANYOF_BIT(c))
+#define ANYOF_BITMAP_TEST(p, c) cBOOL(ANYOF_BITMAP_BYTE(p, c) & ANYOF_BIT(c))
#define ANYOF_BITMAP_SETALL(p) \
memset (ANYOF_BITMAP(p), 255, ANYOF_BITMAP_SIZE)
#define ANYOF_BITMAP_CLEARALL(p) \
Zero (ANYOF_BITMAP(p), ANYOF_BITMAP_SIZE)
-/* Check that all 256 bits are all set. Used in S_cl_is_anything() */
-#define ANYOF_BITMAP_TESTALLSET(p) \
- memEQ (ANYOF_BITMAP(p), "\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377", ANYOF_BITMAP_SIZE)
#define ANYOF_SKIP ((ANYOF_SIZE - 1)/sizeof(regnode))
-#define ANYOF_CLASS_SKIP ((ANYOF_CLASS_SIZE - 1)/sizeof(regnode))
-#define ANYOF_CLASS_ADD_SKIP (ANYOF_CLASS_SKIP - ANYOF_SKIP)
+#define ANYOF_POSIXL_SKIP ((ANYOF_POSIXL_SIZE - 1)/sizeof(regnode))
+#define ANYOF_CLASS_SKIP ANYOF_POSIXL_SKIP
/*
* Utility definitions.
#define EXTRA_SIZE(guy) ((sizeof(guy)-1)/sizeof(struct regnode))
-#define REG_SEEN_ZERO_LEN 0x00000001
-#define REG_SEEN_LOOKBEHIND 0x00000002
-#define REG_SEEN_GPOS 0x00000004
-#define REG_SEEN_EVAL 0x00000008
-#define REG_SEEN_CANY 0x00000010
-#define REG_SEEN_SANY REG_SEEN_CANY /* src bckwrd cmpt */
+#define REG_ZERO_LEN_SEEN 0x00000001
+#define REG_LOOKBEHIND_SEEN 0x00000002
+#define REG_GPOS_SEEN 0x00000004
+/* spare */
+#define REG_CANY_SEEN 0x00000010
+#define REG_RECURSE_SEEN 0x00000020
+#define REG_TOP_LEVEL_BRANCHES_SEEN 0x00000040
+#define REG_VERBARG_SEEN 0x00000080
+#define REG_CUTGROUP_SEEN 0x00000100
+#define REG_RUN_ON_COMMENT_SEEN 0x00000200
+#define REG_UNFOLDED_MULTI_SEEN 0x00000400
+#define REG_GOSTART_SEEN 0x00000800
+#define REG_UNBOUNDED_QUANTIFIER_SEEN 0x00001000
+
START_EXTERN_C
#include "regnodes.h"
#endif
-/* The following have no fixed length. U8 so we can do strchr() on it. */
+#ifndef PLUGGABLE_RE_EXTENSION
#ifndef DOINIT
-EXTCONST U8 PL_varies[];
-#else
-EXTCONST U8 PL_varies[] = {
- BRANCH, BACK, STAR, PLUS, CURLY, CURLYX, REF, REFF, REFFL,
- WHILEM, CURLYM, CURLYN, BRANCHJ, IFTHEN, SUSPEND, CLUMP, 0
+EXTCONST regexp_engine PL_core_reg_engine;
+#else /* DOINIT */
+EXTCONST regexp_engine PL_core_reg_engine = {
+ Perl_re_compile,
+ Perl_regexec_flags,
+ Perl_re_intuit_start,
+ Perl_re_intuit_string,
+ Perl_regfree_internal,
+ Perl_reg_numbered_buff_fetch,
+ Perl_reg_numbered_buff_store,
+ Perl_reg_numbered_buff_length,
+ Perl_reg_named_buff,
+ Perl_reg_named_buff_iter,
+ Perl_reg_qr_package,
+#if defined(USE_ITHREADS)
+ Perl_regdupe_internal,
+#endif
+ Perl_re_op_compile
};
-#endif
+#endif /* DOINIT */
+#endif /* PLUGGABLE_RE_EXTENSION */
-/* The following always have a length of 1. U8 we can do strchr() on it. */
-/* (Note that length 1 means "one character" under UTF8, not "one octet".) */
-#ifndef DOINIT
-EXTCONST U8 PL_simple[];
-#else
-EXTCONST U8 PL_simple[] = {
- REG_ANY, SANY, CANY,
- ANYOF,
- ALNUM, ALNUML,
- NALNUM, NALNUML,
- SPACE, SPACEL,
- NSPACE, NSPACEL,
- DIGIT, NDIGIT,
- 0
-};
-#endif
END_EXTERN_C
-typedef struct re_scream_pos_data_s
-{
- char **scream_olds; /* match pos */
- I32 *scream_pos; /* Internal iterator of scream. */
-} re_scream_pos_data;
/* .what is a character array with one character for each member of .data
* The character describes the function of the corresponding .data item:
+ * a - AV for paren_name_list under DEBUGGING
* f - start-class data for regstclass optimization
- * n - Root of op tree for (?{EVAL}) item
- * o - Start op for (?{EVAL}) item
- * p - Pad for (?{EVAL}) item
- * s - swash for unicode-style character class, and the multicharacter
+ * l - start op for literal (?{EVAL}) item
+ * L - start op for literal (?{EVAL}) item, with separate CV (qr//)
+ * r - pointer to an embedded code-containing qr, e.g. /ab$qr/
+ * s - swash for Unicode-style character class, and the multicharacter
* strings resulting from casefolding the single-character entries
* in the character class
* t - trie struct
+ * u - trie struct's widecharmap (a HV, so can't share, must dup)
+ * also used for revcharmap and words under DEBUGGING
* T - aho-trie struct
+ * S - sv for named capture lookup
* 20010712 mjd@plover.com
* (Remember to update re_dup() and pregfree() if you add any items.)
*/
void* data[1];
};
-struct reg_substr_datum {
- I32 min_offset;
- I32 max_offset;
- SV *substr; /* non-utf8 variant */
- SV *utf8_substr; /* utf8 variant */
-};
-
-struct reg_substr_data {
- struct reg_substr_datum data[3]; /* Actual array */
-};
-
+/* Code in S_to_utf8_substr() and S_to_byte_substr() in regexec.c accesses
+ anchored* and float* via array indexes 0 and 1. */
#define anchored_substr substrs->data[0].substr
#define anchored_utf8 substrs->data[0].utf8_substr
#define anchored_offset substrs->data[0].min_offset
+#define anchored_end_shift substrs->data[0].end_shift
+
#define float_substr substrs->data[1].substr
#define float_utf8 substrs->data[1].utf8_substr
#define float_min_offset substrs->data[1].min_offset
#define float_max_offset substrs->data[1].max_offset
+#define float_end_shift substrs->data[1].end_shift
+
#define check_substr substrs->data[2].substr
#define check_utf8 substrs->data[2].utf8_substr
#define check_offset_min substrs->data[2].min_offset
#define check_offset_max substrs->data[2].max_offset
+#define check_end_shift substrs->data[2].end_shift
-
+#define RX_ANCHORED_SUBSTR(rx) (ReANY(rx)->anchored_substr)
+#define RX_ANCHORED_UTF8(rx) (ReANY(rx)->anchored_utf8)
+#define RX_FLOAT_SUBSTR(rx) (ReANY(rx)->float_substr)
+#define RX_FLOAT_UTF8(rx) (ReANY(rx)->float_utf8)
/* trie related stuff */
} trans;
};
+/* info per word; indexed by wordnum */
+typedef struct {
+ U16 prev; /* previous word in acceptance chain; eg in
+ * zzz|abc|ab/ after matching the chars abc, the
+ * accepted word is #2, and the previous accepted
+ * word is #3 */
+ U32 len; /* how many chars long is this word? */
+ U32 accept; /* accept state for this word */
+} reg_trie_wordinfo;
typedef struct _reg_trie_state reg_trie_state;
/* anything in here that needs to be freed later
- should be dealt with in pregfree */
+ should be dealt with in pregfree.
+ refcount is first in both this and _reg_ac_data to allow a space
+ optimisation in Perl_regdupe. */
struct _reg_trie_data {
- U16 uniquecharcount;
- U32 lasttrans;
- U16 *charmap;
- HV *widecharmap;
- reg_trie_state *states;
- reg_trie_trans *trans;
- char *bitmap;
- U32 refcount;
- U32 startstate;
- STRLEN minlen;
- STRLEN maxlen;
- U32 *wordlen;
- U32 laststate; /* Build only */
+ U32 refcount; /* number of times this trie is referenced */
+ U32 lasttrans; /* last valid transition element */
+ U16 *charmap; /* byte to charid lookup array */
+ reg_trie_state *states; /* state data */
+ reg_trie_trans *trans; /* array of transition elements */
+ char *bitmap; /* stclass bitmap */
+ U16 *jump; /* optional 1 indexed array of offsets before tail
+ for the node following a given word. */
+ reg_trie_wordinfo *wordinfo; /* array of info per word */
+ U16 uniquecharcount; /* unique chars in trie (width of trans table) */
+ U32 startstate; /* initial state - used for common prefix optimisation */
+ STRLEN minlen; /* minimum length of words in trie - build/opt only? */
+ STRLEN maxlen; /* maximum length of words in trie - build/opt only? */
+ U32 prefixlen; /* #chars in common prefix */
+ U32 statecount; /* Build only - number of states in the states array
+ (including the unused zero state) */
+ U32 wordcount; /* Build only */
#ifdef DEBUGGING
- U16 wordcount; /* Build only */
- STRLEN charcount; /* Build only */
- AV *words;
- AV *revcharmap;
+ STRLEN charcount; /* Build only */
#endif
};
+/* There is one (3 under DEBUGGING) pointers that logically belong in this
+ structure, but are held outside as they need duplication on thread cloning,
+ whereas the rest of the structure can be read only:
+ HV *widecharmap; code points > 255 to charid
+#ifdef DEBUGGING
+ AV *words; Array of words contained in trie, for dumping
+ AV *revcharmap; Map of each charid back to its character representation
+#endif
+*/
+
+#define TRIE_WORDS_OFFSET 2
+
typedef struct _reg_trie_data reg_trie_data;
+/* refcount is first in both this and _reg_trie_data to allow a space
+ optimisation in Perl_regdupe. */
struct _reg_ac_data {
+ U32 refcount;
+ U32 trie;
U32 *fail;
reg_trie_state *states;
- reg_trie_data *trie;
- U32 refcount;
};
typedef struct _reg_ac_data reg_ac_data;
-/* ANY_BIT doesnt use the structure, so we can borrow it here.
+/* ANY_BIT doesn't use the structure, so we can borrow it here.
This is simpler than refactoring all of it as wed end up with
three different sets... */
#define TRIE_BITMAP(p) (((reg_trie_data *)(p))->bitmap)
-#define TRIE_BITMAP_BYTE(p, c) (TRIE_BITMAP(p)[((c) >> 3) & 31])
-#define TRIE_BITMAP_SET(p, c) (TRIE_BITMAP_BYTE(p, c) |= ANYOF_BIT(c))
-#define TRIE_BITMAP_CLEAR(p,c) (TRIE_BITMAP_BYTE(p, c) &= ~ANYOF_BIT(c))
-#define TRIE_BITMAP_TEST(p, c) (TRIE_BITMAP_BYTE(p, c) & ANYOF_BIT(c))
+#define TRIE_BITMAP_BYTE(p, c) (TRIE_BITMAP(p)[(((U8)(c)) >> 3) & 31])
+#define TRIE_BITMAP_SET(p, c) (TRIE_BITMAP_BYTE(p, c) |= ANYOF_BIT((U8)c))
+#define TRIE_BITMAP_CLEAR(p,c) (TRIE_BITMAP_BYTE(p, c) &= ~ANYOF_BIT((U8)c))
+#define TRIE_BITMAP_TEST(p, c) (TRIE_BITMAP_BYTE(p, c) & ANYOF_BIT((U8)c))
+
+#define IS_ANYOF_TRIE(op) ((op)==TRIEC || (op)==AHOCORASICKC)
+#define IS_TRIE_AC(op) ((op)>=AHOCORASICK)
+
+#define BITMAP_BYTE(p, c) (((U8*)p)[(((U8)(c)) >> 3) & 31])
+#define BITMAP_TEST(p, c) (BITMAP_BYTE(p, c) & ANYOF_BIT((U8)c))
/* these defines assume uniquecharcount is the correct variable, and state may be evaluated twice */
#define TRIE_NODENUM(state) (((state)-1)/(trie->uniquecharcount)+1)
#define TRIE_NODEIDX(state) ((state) ? (((state)-1)*(trie->uniquecharcount)+1) : (state))
#ifdef DEBUGGING
-#define TRIE_WORDCOUNT(trie) ((trie)->wordcount)
#define TRIE_CHARCOUNT(trie) ((trie)->charcount)
-#define TRIE_LASTSTATE(trie) ((trie)->laststate)
-#define TRIE_REVCHARMAP(trie) ((trie)->revcharmap)
#else
-#define TRIE_WORDCOUNT(trie) (trie_wordcount)
#define TRIE_CHARCOUNT(trie) (trie_charcount)
-/*#define TRIE_LASTSTATE(trie) (trie_laststate)*/
-#define TRIE_LASTSTATE(trie) ((trie)->laststate)
-#define TRIE_REVCHARMAP(trie) (trie_revcharmap)
#endif
#define RE_TRIE_MAXBUF_INIT 65536
#define RE_DEBUG_COMPILE_OPTIMISE 0x000002
#define RE_DEBUG_COMPILE_TRIE 0x000004
#define RE_DEBUG_COMPILE_DUMP 0x000008
-#define RE_DEBUG_COMPILE_OFFSETS 0x000010
+#define RE_DEBUG_COMPILE_FLAGS 0x000010
/* Execute */
#define RE_DEBUG_EXECUTE_MASK 0x00FF00
#define RE_DEBUG_EXTRA_MASK 0xFF0000
#define RE_DEBUG_EXTRA_TRIE 0x010000
#define RE_DEBUG_EXTRA_OFFSETS 0x020000
+#define RE_DEBUG_EXTRA_OFFDEBUG 0x040000
+#define RE_DEBUG_EXTRA_STATE 0x080000
+#define RE_DEBUG_EXTRA_OPTIMISE 0x100000
+#define RE_DEBUG_EXTRA_BUFFERS 0x400000
+#define RE_DEBUG_EXTRA_GPOS 0x800000
+/* combined */
+#define RE_DEBUG_EXTRA_STACK 0x280000
#define RE_DEBUG_FLAG(x) (re_debug_flags & x)
/* Compile */
if (re_debug_flags & RE_DEBUG_COMPILE_PARSE) x )
#define DEBUG_DUMP_r(x) DEBUG_r( \
if (re_debug_flags & RE_DEBUG_COMPILE_DUMP) x )
-#define DEBUG_OFFSETS_r(x) DEBUG_r( \
- if (re_debug_flags & RE_DEBUG_COMPILE_OFFSETS) x )
#define DEBUG_TRIE_COMPILE_r(x) DEBUG_r( \
if (re_debug_flags & RE_DEBUG_COMPILE_TRIE) x )
-
+#define DEBUG_FLAGS_r(x) DEBUG_r( \
+ if (re_debug_flags & RE_DEBUG_COMPILE_FLAGS) x )
/* Execute */
#define DEBUG_EXECUTE_r(x) DEBUG_r( \
if (re_debug_flags & RE_DEBUG_EXECUTE_MASK) x )
/* Extra */
#define DEBUG_EXTRA_r(x) DEBUG_r( \
if (re_debug_flags & RE_DEBUG_EXTRA_MASK) x )
+#define DEBUG_OFFSETS_r(x) DEBUG_r( \
+ if (re_debug_flags & RE_DEBUG_EXTRA_OFFSETS) x )
+#define DEBUG_STATE_r(x) DEBUG_r( \
+ if (re_debug_flags & RE_DEBUG_EXTRA_STATE) x )
+#define DEBUG_STACK_r(x) DEBUG_r( \
+ if (re_debug_flags & RE_DEBUG_EXTRA_STACK) x )
+#define DEBUG_BUFFERS_r(x) DEBUG_r( \
+ if (re_debug_flags & RE_DEBUG_EXTRA_BUFFERS) x )
+
+#define DEBUG_OPTIMISE_MORE_r(x) DEBUG_r( \
+ if ((RE_DEBUG_EXTRA_OPTIMISE|RE_DEBUG_COMPILE_OPTIMISE) == \
+ (re_debug_flags & (RE_DEBUG_EXTRA_OPTIMISE|RE_DEBUG_COMPILE_OPTIMISE)) ) x )
#define MJD_OFFSET_DEBUG(x) DEBUG_r( \
- if (re_debug_flags & RE_DEBUG_EXTRA_OFFSETS) \
+ if (re_debug_flags & RE_DEBUG_EXTRA_OFFDEBUG) \
Perl_warn_nocontext x )
#define DEBUG_TRIE_COMPILE_MORE_r(x) DEBUG_TRIE_COMPILE_r( \
if (re_debug_flags & RE_DEBUG_EXTRA_TRIE) x )
#define DEBUG_TRIE_r(x) DEBUG_r( \
if (re_debug_flags & (RE_DEBUG_COMPILE_TRIE \
| RE_DEBUG_EXECUTE_TRIE )) x )
+#define DEBUG_GPOS_r(x) DEBUG_r( \
+ if (re_debug_flags & RE_DEBUG_EXTRA_GPOS) x )
/* initialization */
/* get_sv() can return NULL during global destruction. */
})
#ifdef DEBUGGING
-#define GET_RE_DEBUG_FLAGS_DECL IV re_debug_flags = 0; GET_RE_DEBUG_FLAGS;
-#else
+
+#define GET_RE_DEBUG_FLAGS_DECL VOL IV re_debug_flags = 0; \
+ PERL_UNUSED_VAR(re_debug_flags); GET_RE_DEBUG_FLAGS;
+
+#define RE_PV_COLOR_DECL(rpv,rlen,isuni,dsv,pv,l,m,c1,c2) \
+ const char * const rpv = \
+ pv_pretty((dsv), (pv), (l), (m), \
+ PL_colors[(c1)],PL_colors[(c2)], \
+ PERL_PV_ESCAPE_RE|PERL_PV_ESCAPE_NONASCII |((isuni) ? PERL_PV_ESCAPE_UNI : 0) ); \
+ const int rlen = SvCUR(dsv)
+
+#define RE_SV_ESCAPE(rpv,isuni,dsv,sv,m) \
+ const char * const rpv = \
+ pv_pretty((dsv), (SvPV_nolen_const(sv)), (SvCUR(sv)), (m), \
+ PL_colors[(c1)],PL_colors[(c2)], \
+ PERL_PV_ESCAPE_RE|PERL_PV_ESCAPE_NONASCII |((isuni) ? PERL_PV_ESCAPE_UNI : 0) )
+
+#define RE_PV_QUOTED_DECL(rpv,isuni,dsv,pv,l,m) \
+ const char * const rpv = \
+ pv_pretty((dsv), (pv), (l), (m), \
+ PL_colors[0], PL_colors[1], \
+ ( PERL_PV_PRETTY_QUOTE | PERL_PV_ESCAPE_RE | PERL_PV_ESCAPE_NONASCII | PERL_PV_PRETTY_ELLIPSES | \
+ ((isuni) ? PERL_PV_ESCAPE_UNI : 0)) \
+ )
+
+#define RE_SV_DUMPLEN(ItEm) (SvCUR(ItEm) - (SvTAIL(ItEm)!=0))
+#define RE_SV_TAIL(ItEm) (SvTAIL(ItEm) ? "$" : "")
+
+#else /* if not DEBUGGING */
+
#define GET_RE_DEBUG_FLAGS_DECL
-#endif
+#define RE_PV_COLOR_DECL(rpv,rlen,isuni,dsv,pv,l,m,c1,c2)
+#define RE_SV_ESCAPE(rpv,isuni,dsv,sv,m)
+#define RE_PV_QUOTED_DECL(rpv,isuni,dsv,pv,l,m)
+#define RE_SV_DUMPLEN(ItEm)
+#define RE_SV_TAIL(ItEm)
+
+#endif /* DEBUG RELATED DEFINES */
+/*
+ * Local variables:
+ * c-indentation-style: bsd
+ * c-basic-offset: 4
+ * indent-tabs-mode: nil
+ * End:
+ *
+ * ex: set ts=8 sts=4 sw=4 et:
+ */
https://perl5.git.perl.org / perl5.git / blobdiff