#define _invlist_intersection_complement_2nd(a, b, output) \
_invlist_intersection_maybe_complement_2nd(a, b, TRUE, output)
-STATIC void
-S_ssc_flags_and(regnode_ssc *ssc, const U8 and_with)
-{
- /* Take the flags 'and_with' and accumulate them anded into the flags for
- * the SSC 'ssc'. The non-SSC related flags in 'and_with' are ignored. */
-
- const U8 ssc_only_flags = ANYOF_FLAGS(ssc) & ~ANYOF_LOCALE_FLAGS;
-
- PERL_ARGS_ASSERT_SSC_FLAGS_AND;
-
- /* Use just the SSC-related flags from 'and_with' */
- ANYOF_FLAGS(ssc) &= (and_with & ANYOF_LOCALE_FLAGS);
- ANYOF_FLAGS(ssc) |= ssc_only_flags;
-}
-
-STATIC int
-S_ssc_is_cp_posixl_init(pTHX_ const RExC_state_t *pRExC_state,
- const regnode_ssc *ssc)
-{
- /* Returns TRUE if the SSC 'ssc' is in its initial state with regard only
- * to the list of code points matched, and locale posix classes; hence does
- * not check its flags) */
-
- UV start, end;
- bool ret;
-
- PERL_ARGS_ASSERT_SSC_IS_CP_POSIXL_INIT;
-
- assert(OP(ssc) == ANYOF_SYNTHETIC);
-
- invlist_iterinit(ssc->invlist);
- ret = invlist_iternext(ssc->invlist, &start, &end)
- && start == 0
- && end == UV_MAX;
-
- invlist_iterfinish(ssc->invlist);
-
- if (! ret) {
- return FALSE;
- }
-
- if (RExC_contains_locale) {
- if (! (ANYOF_FLAGS(ssc) & ANYOF_LOCALE)
- || ! (ANYOF_FLAGS(ssc) & ANYOF_POSIXL)
- || ! ANYOF_POSIXL_TEST_ALL_SET(ssc))
- {
- return FALSE;
- }
- }
-
- return TRUE;
-}
-
-STATIC SV*
-S_get_ANYOF_cp_list_for_ssc(pTHX_ const RExC_state_t *pRExC_state,
- const regnode_charclass_posixl* const node)
-{
- /* Returns a mortal inversion list defining which code points are matched
- * by 'node', which is of type ANYOF. Handles complementing the result if
- * appropriate. If some code points aren't knowable at this time, the
- * returned list must, and will, contain every possible code point. */
-
- SV* invlist = sv_2mortal(_new_invlist(0));
- unsigned int i;
- const U32 n = ARG(node);
-
- PERL_ARGS_ASSERT_GET_ANYOF_CP_LIST_FOR_SSC;
-
- /* Look at the data structure created by S_set_ANYOF_arg() */
- if (n != ANYOF_NONBITMAP_EMPTY) {
- SV * const rv = MUTABLE_SV(RExC_rxi->data->data[n]);
- AV * const av = MUTABLE_AV(SvRV(rv));
- SV **const ary = AvARRAY(av);
- assert(RExC_rxi->data->what[n] == 's');
-
- if (ary[1] && ary[1] != &PL_sv_undef) { /* Has compile-time swash */
- invlist = sv_2mortal(invlist_clone(_get_swash_invlist(ary[1])));
- }
- else if (ary[0] && ary[0] != &PL_sv_undef) {
-
- /* Here, no compile-time swash, and there are things that won't be
- * known until runtime -- we have to assume it could be anything */
- return _add_range_to_invlist(invlist, 0, UV_MAX);
- }
- else {
-
- /* Here no compile-time swash, and no run-time only data. Use the
- * node's inversion list */
- invlist = sv_2mortal(invlist_clone(ary[2]));
- }
- }
-
- /* An ANYOF node contains a bitmap for the first 256 code points, and an
- * inversion list for the others, but if there are code points that should
- * match only conditionally on the target string being UTF-8, those are
- * placed in the inversion list, and not the bitmap. Since there are
- * circumstances under which they could match, they are included in the
- * SSC. But if the ANYOF node is to be inverted, we have to exclude them
- * here, so that when we invert below, the end result actually does include
- * them. (Think about "\xe0" =~ /[^\xc0]/di;). We have to do this here
- * before we add the unconditionally matched code points */
- if (ANYOF_FLAGS(node) & ANYOF_INVERT) {
- _invlist_intersection_complement_2nd(invlist,
- PL_UpperLatin1,
- &invlist);
- }
-
- /* Add in the points from the bit map */
- for (i = 0; i < 256; i++) {
- if (ANYOF_BITMAP_TEST(node, i)) {
- invlist = add_cp_to_invlist(invlist, i);
- }
- }
-
- /* If this can match all upper Latin1 code points, have to add them
- * as well */
- if (ANYOF_FLAGS(node) & ANYOF_NON_UTF8_LATIN1_ALL) {
- _invlist_union(invlist, PL_UpperLatin1, &invlist);
- }
-
- /* Similarly for these */
- if (ANYOF_FLAGS(node) & ANYOF_ABOVE_LATIN1_ALL) {
- invlist = _add_range_to_invlist(invlist, 256, UV_MAX);
- }
-
- if (ANYOF_FLAGS(node) & ANYOF_INVERT) {
- _invlist_invert(invlist);
- }
-
- return invlist;
-}
-
-PERL_STATIC_INLINE void
-S_ssc_union(pTHX_ regnode_ssc *ssc, SV* const invlist, const bool invert2nd)
-{
- PERL_ARGS_ASSERT_SSC_UNION;
-
- assert(OP(ssc) == ANYOF_SYNTHETIC);
-
- _invlist_union_maybe_complement_2nd(ssc->invlist,
- invlist,
- invert2nd,
- &ssc->invlist);
-}
-
-PERL_STATIC_INLINE void
-S_ssc_intersection(pTHX_ regnode_ssc *ssc,
- SV* const invlist,
- const bool invert2nd)
-{
- PERL_ARGS_ASSERT_SSC_INTERSECTION;
-
- assert(OP(ssc) == ANYOF_SYNTHETIC);
-
- _invlist_intersection_maybe_complement_2nd(ssc->invlist,
- invlist,
- invert2nd,
- &ssc->invlist);
-}
-
-PERL_STATIC_INLINE void
-S_ssc_add_range(pTHX_ regnode_ssc *ssc, const UV start, const UV end)
-{
- PERL_ARGS_ASSERT_SSC_ADD_RANGE;
-
- assert(OP(ssc) == ANYOF_SYNTHETIC);
-
- ssc->invlist = _add_range_to_invlist(ssc->invlist, start, end);
-}
-
-PERL_STATIC_INLINE void
-S_ssc_cp_and(pTHX_ regnode_ssc *ssc, const UV cp)
-{
- /* AND just the single code point 'cp' into the SSC 'ssc' */
-
- SV* cp_list = _new_invlist(2);
-
- PERL_ARGS_ASSERT_SSC_CP_AND;
-
- assert(OP(ssc) == ANYOF_SYNTHETIC);
-
- cp_list = add_cp_to_invlist(cp_list, cp);
- ssc_intersection(ssc, cp_list,
- FALSE /* Not inverted */
- );
- SvREFCNT_dec_NN(cp_list);
-}
-
-PERL_STATIC_INLINE void
-S_ssc_clear_locale(pTHX_ regnode_ssc *ssc)
-{
- /* Set the SSC 'ssc' to not match any locale things */
-
- PERL_ARGS_ASSERT_SSC_CLEAR_LOCALE;
-
- assert(OP(ssc) == ANYOF_SYNTHETIC);
-
- ANYOF_POSIXL_ZERO(ssc);
- ANYOF_FLAGS(ssc) &= ~ANYOF_LOCALE_FLAGS;
-}
-
-STATIC void
-S_ssc_finalize(pTHX_ RExC_state_t *pRExC_state, regnode_ssc *ssc)
-{
- /* The inversion list in the SSC is marked mortal; now we need a more
- * permanent copy, which is stored the same way that is done in a regular
- * ANYOF node, with the first 256 code points in a bit map */
-
- SV* invlist = invlist_clone(ssc->invlist);
-
- PERL_ARGS_ASSERT_SSC_FINALIZE;
-
- assert(OP(ssc) == ANYOF_SYNTHETIC);
-
- populate_ANYOF_from_invlist( (regnode *) ssc, &invlist);
-
- set_ANYOF_arg(pRExC_state, (regnode *) ssc, invlist, NULL, NULL, FALSE);
-
- assert(! (ANYOF_FLAGS(ssc) & ANYOF_LOCALE) || RExC_contains_locale);
-}
-
/* About scan_data_t.
During optimisation we recurse through the regexp program performing
DEBUG_STUDYDATA("commit: ",data,0);
}
-/* These macros set, clear and test whether the synthetic start class ('ssc',
- * given by the parameter) matches an empty string (EOS). This uses the
- * 'next_off' field in the node, to save a bit in the flags field. The ssc
- * stands alone, so there is never a next_off, so this field is otherwise
- * unused. The EOS information is used only for compilation, but theoretically
- * it could be passed on to the execution code. This could be used to store
- * more than one bit of information, but only this one is currently used. This
- * flag could be moved back to the bitmap instead, shared with INVERT, as no
- * SSC is ever inverted */
-#define SET_SSC_EOS(node) STMT_START { (node)->next_off = TRUE; } STMT_END
-#define CLEAR_SSC_EOS(node) STMT_START { (node)->next_off = FALSE; } STMT_END
-#define TEST_SSC_EOS(node) cBOOL((node)->next_off)
-
/* An SSC is just a regnode_charclass_posix with an extra field: the inversion
* list that describes which code points it matches */
ssc->invlist = sv_2mortal(_new_invlist(2)); /* mortalize so won't leak */
_append_range_to_invlist(ssc->invlist, 0, UV_MAX);
- SET_SSC_EOS(ssc); /* Plus match empty string */
+ ANYOF_FLAGS(ssc) |= ANYOF_EMPTY_STRING; /* Plus match empty string */
}
STATIC int
assert(OP(ssc) == ANYOF_SYNTHETIC);
- if (! TEST_SSC_EOS(ssc)) {
+ if (! ANYOF_FLAGS(ssc) & ANYOF_EMPTY_STRING) {
return FALSE;
}
}
}
+STATIC int
+S_ssc_is_cp_posixl_init(pTHX_ const RExC_state_t *pRExC_state,
+ const regnode_ssc *ssc)
+{
+ /* Returns TRUE if the SSC 'ssc' is in its initial state with regard only
+ * to the list of code points matched, and locale posix classes; hence does
+ * not check its flags) */
+
+ UV start, end;
+ bool ret;
+
+ PERL_ARGS_ASSERT_SSC_IS_CP_POSIXL_INIT;
+
+ assert(OP(ssc) == ANYOF_SYNTHETIC);
+
+ invlist_iterinit(ssc->invlist);
+ ret = invlist_iternext(ssc->invlist, &start, &end)
+ && start == 0
+ && end == UV_MAX;
+
+ invlist_iterfinish(ssc->invlist);
+
+ if (! ret) {
+ return FALSE;
+ }
+
+ if (RExC_contains_locale) {
+ if (! (ANYOF_FLAGS(ssc) & ANYOF_LOCALE)
+ || ! (ANYOF_FLAGS(ssc) & ANYOF_POSIXL)
+ || ! ANYOF_POSIXL_TEST_ALL_SET(ssc))
+ {
+ return FALSE;
+ }
+ if (RExC_contains_i && ! (ANYOF_FLAGS(ssc) & ANYOF_LOC_FOLD)) {
+ return FALSE;
+ }
+ }
+
+ return TRUE;
+}
+
+STATIC SV*
+S_get_ANYOF_cp_list_for_ssc(pTHX_ const RExC_state_t *pRExC_state,
+ const regnode_charclass_posixl* const node)
+{
+ /* Returns a mortal inversion list defining which code points are matched
+ * by 'node', which is of type ANYOF. Handles complementing the result if
+ * appropriate. If some code points aren't knowable at this time, the
+ * returned list must, and will, contain every possible code point. */
+
+ SV* invlist = sv_2mortal(_new_invlist(0));
+ unsigned int i;
+ const U32 n = ARG(node);
+
+ PERL_ARGS_ASSERT_GET_ANYOF_CP_LIST_FOR_SSC;
+
+ /* Look at the data structure created by S_set_ANYOF_arg() */
+ if (n != ANYOF_NONBITMAP_EMPTY) {
+ SV * const rv = MUTABLE_SV(RExC_rxi->data->data[n]);
+ AV * const av = MUTABLE_AV(SvRV(rv));
+ SV **const ary = AvARRAY(av);
+ assert(RExC_rxi->data->what[n] == 's');
+
+ if (ary[1] && ary[1] != &PL_sv_undef) { /* Has compile-time swash */
+ invlist = sv_2mortal(invlist_clone(_get_swash_invlist(ary[1])));
+ }
+ else if (ary[0] && ary[0] != &PL_sv_undef) {
+
+ /* Here, no compile-time swash, and there are things that won't be
+ * known until runtime -- we have to assume it could be anything */
+ return _add_range_to_invlist(invlist, 0, UV_MAX);
+ }
+ else {
+
+ /* Here no compile-time swash, and no run-time only data. Use the
+ * node's inversion list */
+ invlist = sv_2mortal(invlist_clone(ary[2]));
+ }
+ }
+
+ /* An ANYOF node contains a bitmap for the first 256 code points, and an
+ * inversion list for the others, but if there are code points that should
+ * match only conditionally on the target string being UTF-8, those are
+ * placed in the inversion list, and not the bitmap. Since there are
+ * circumstances under which they could match, they are included in the
+ * SSC. But if the ANYOF node is to be inverted, we have to exclude them
+ * here, so that when we invert below, the end result actually does include
+ * them. (Think about "\xe0" =~ /[^\xc0]/di;). We have to do this here
+ * before we add the unconditionally matched code points */
+ if (ANYOF_FLAGS(node) & ANYOF_INVERT) {
+ _invlist_intersection_complement_2nd(invlist,
+ PL_UpperLatin1,
+ &invlist);
+ }
+
+ /* Add in the points from the bit map */
+ for (i = 0; i < 256; i++) {
+ if (ANYOF_BITMAP_TEST(node, i)) {
+ invlist = add_cp_to_invlist(invlist, i);
+ }
+ }
+
+ /* If this can match all upper Latin1 code points, have to add them
+ * as well */
+ if (ANYOF_FLAGS(node) & ANYOF_NON_UTF8_LATIN1_ALL) {
+ _invlist_union(invlist, PL_UpperLatin1, &invlist);
+ }
+
+ /* Similarly for these */
+ if (ANYOF_FLAGS(node) & ANYOF_ABOVE_LATIN1_ALL) {
+ invlist = _add_range_to_invlist(invlist, 256, UV_MAX);
+ }
+
+ if (ANYOF_FLAGS(node) & ANYOF_INVERT) {
+ _invlist_invert(invlist);
+ }
+
+ return invlist;
+}
+
/* These two functions currently do the exact same thing */
#define ssc_init_zero ssc_init
#define ssc_add_cp(ssc, cp) ssc_add_range((ssc), (cp), (cp))
#define ssc_match_all_cp(ssc) ssc_add_range(ssc, 0, UV_MAX)
+STATIC void
+S_ssc_flags_and(regnode_ssc *ssc, const U8 and_with)
+{
+ /* Take the flags 'and_with' and accumulate them anded into the flags for
+ * the SSC 'ssc'. The non-SSC related flags in 'and_with' are ignored.
+ * The flags 'and_with' should not come from another SSC (otherwise the
+ * EMPTY_STRING flag won't work) */
+
+ const U8 ssc_only_flags = ANYOF_FLAGS(ssc) & ~ANYOF_LOCALE_FLAGS;
+
+ PERL_ARGS_ASSERT_SSC_FLAGS_AND;
+
+ /* Use just the SSC-related flags from 'and_with' */
+ ANYOF_FLAGS(ssc) &= (and_with & ANYOF_LOCALE_FLAGS);
+ ANYOF_FLAGS(ssc) |= ssc_only_flags;
+}
+
/* 'AND' a given class with another one. Can create false positives. 'ssc'
* should not be inverted. 'and_with->flags & ANYOF_POSIXL' should be 0 if
* 'and_with' is a regnode_charclass instead of a regnode_ssc. */
STATIC void
-S_ssc_and(pTHX_ const RExC_state_t *pRExC_state, regnode_ssc *ssc, const regnode_ssc *and_with)
+S_ssc_and(pTHX_ const RExC_state_t *pRExC_state, regnode_ssc *ssc,
+ const regnode_ssc *and_with)
{
/* Accumulate into SSC 'ssc' its 'AND' with 'and_with', which is either
* another SSC or a regular ANYOF class. Can create false positives. */
- /* If 'and_with' is an SSC, we already have its inversion list; otherwise
- * have to calculate it */
- SV* anded_cp_list = (OP(and_with) == ANYOF_SYNTHETIC)
- ? and_with->invlist
- : get_ANYOF_cp_list_for_ssc(pRExC_state,
- (regnode_charclass_posixl*) and_with);
+ SV* anded_cp_list;
+ U8 anded_flags;
PERL_ARGS_ASSERT_SSC_AND;
assert(OP(ssc) == ANYOF_SYNTHETIC);
- assert(! (ANYOF_FLAGS(ssc) & ANYOF_INVERT)); /* SSCs are never inverted */
+
+ /* 'and_with' is used as-is if it too is an SSC; otherwise have to extract
+ * the code point inversion list and just the relevant flags */
+ if (OP(and_with) == ANYOF_SYNTHETIC) {
+ anded_cp_list = and_with->invlist;
+ anded_flags = ANYOF_FLAGS(and_with);
+ }
+ else {
+ anded_cp_list = get_ANYOF_cp_list_for_ssc(pRExC_state,
+ (regnode_charclass_posixl*) and_with);
+ anded_flags = ANYOF_FLAGS(and_with) & ANYOF_LOCALE_FLAGS;
+ }
+
+ ANYOF_FLAGS(ssc) &= anded_flags;
/* Below, C1 is the list of code points in 'ssc'; P1, its posix classes.
* C2 is the list of code points in 'and-with'; P2, its posix classes.
* <= (C1 & ~C2) | (P1 & ~P2)
* */
- if (ANYOF_FLAGS(and_with) & ANYOF_INVERT) {
+ if ((ANYOF_FLAGS(and_with) & ANYOF_INVERT)
+ && OP(and_with) != ANYOF_SYNTHETIC)
+ {
unsigned int i;
- assert(OP(and_with) != ANYOF_SYNTHETIC);
-
ssc_intersection(ssc,
anded_cp_list,
FALSE /* Has already been inverted */
ssc_intersection(ssc, anded_cp_list, FALSE);
}
}
-
- ssc_flags_and(ssc, ANYOF_FLAGS(and_with));
}
STATIC void
* another SSC or a regular ANYOF class. Can create false positives if
* 'or_with' is to be inverted. */
- /* If 'or_with' is an SSC, we already have its inversion list; otherwise
- * have to calculate it */
- SV* ored_cp_list = (OP(or_with) == ANYOF_SYNTHETIC)
- ? or_with->invlist
- : get_ANYOF_cp_list_for_ssc(pRExC_state,
- (regnode_charclass_posixl*) or_with);
+ SV* ored_cp_list;
+ U8 ored_flags;
PERL_ARGS_ASSERT_SSC_OR;
assert(OP(ssc) == ANYOF_SYNTHETIC);
- assert(! (ANYOF_FLAGS(ssc) & ANYOF_INVERT));
+
+ /* 'or_with' is used as-is if it too is an SSC; otherwise have to extract
+ * the code point inversion list and just the relevant flags */
+ if (OP(or_with) == ANYOF_SYNTHETIC) {
+ ored_cp_list = or_with->invlist;
+ ored_flags = ANYOF_FLAGS(or_with);
+ }
+ else {
+ ored_cp_list = get_ANYOF_cp_list_for_ssc(pRExC_state,
+ (regnode_charclass_posixl*) or_with);
+ ored_flags = ANYOF_FLAGS(or_with) & ANYOF_LOCALE_FLAGS;
+ }
+
+ ANYOF_FLAGS(ssc) |= ored_flags;
/* Below, C1 is the list of code points in 'ssc'; P1, its posix classes.
* C2 is the list of code points in 'or-with'; P2, its posix classes.
* (which results in actually simpler code than the non-inverted case)
* */
- /* Use just the SSC-related flags from 'or_with' */
- ANYOF_FLAGS(ssc) |= (ANYOF_FLAGS(or_with) & ANYOF_LOCALE_FLAGS);
-
- if (ANYOF_FLAGS(or_with) & ANYOF_INVERT) {
- assert(OP(or_with) != ANYOF_SYNTHETIC);
+ if ((ANYOF_FLAGS(or_with) & ANYOF_INVERT)
+ && OP(or_with) != ANYOF_SYNTHETIC)
+ {
/* We ignore P2, leaving P1 going forward */
}
else { /* Not inverted */
);
}
+PERL_STATIC_INLINE void
+S_ssc_union(pTHX_ regnode_ssc *ssc, SV* const invlist, const bool invert2nd)
+{
+ PERL_ARGS_ASSERT_SSC_UNION;
+
+ assert(OP(ssc) == ANYOF_SYNTHETIC);
+
+ _invlist_union_maybe_complement_2nd(ssc->invlist,
+ invlist,
+ invert2nd,
+ &ssc->invlist);
+}
+
+PERL_STATIC_INLINE void
+S_ssc_intersection(pTHX_ regnode_ssc *ssc,
+ SV* const invlist,
+ const bool invert2nd)
+{
+ PERL_ARGS_ASSERT_SSC_INTERSECTION;
+
+ assert(OP(ssc) == ANYOF_SYNTHETIC);
+
+ _invlist_intersection_maybe_complement_2nd(ssc->invlist,
+ invlist,
+ invert2nd,
+ &ssc->invlist);
+}
+
+PERL_STATIC_INLINE void
+S_ssc_add_range(pTHX_ regnode_ssc *ssc, const UV start, const UV end)
+{
+ PERL_ARGS_ASSERT_SSC_ADD_RANGE;
+
+ assert(OP(ssc) == ANYOF_SYNTHETIC);
+
+ ssc->invlist = _add_range_to_invlist(ssc->invlist, start, end);
+}
+
+PERL_STATIC_INLINE void
+S_ssc_cp_and(pTHX_ regnode_ssc *ssc, const UV cp)
+{
+ /* AND just the single code point 'cp' into the SSC 'ssc' */
+
+ SV* cp_list = _new_invlist(2);
+
+ PERL_ARGS_ASSERT_SSC_CP_AND;
+
+ assert(OP(ssc) == ANYOF_SYNTHETIC);
+
+ cp_list = add_cp_to_invlist(cp_list, cp);
+ ssc_intersection(ssc, cp_list,
+ FALSE /* Not inverted */
+ );
+ SvREFCNT_dec_NN(cp_list);
+}
+
+PERL_STATIC_INLINE void
+S_ssc_clear_locale(pTHX_ regnode_ssc *ssc)
+{
+ /* Set the SSC 'ssc' to not match any locale things */
+
+ PERL_ARGS_ASSERT_SSC_CLEAR_LOCALE;
+
+ assert(OP(ssc) == ANYOF_SYNTHETIC);
+
+ ANYOF_POSIXL_ZERO(ssc);
+ ANYOF_FLAGS(ssc) &= ~ANYOF_LOCALE_FLAGS;
+}
+
+STATIC void
+S_ssc_finalize(pTHX_ RExC_state_t *pRExC_state, regnode_ssc *ssc)
+{
+ /* The inversion list in the SSC is marked mortal; now we need a more
+ * permanent copy, which is stored the same way that is done in a regular
+ * ANYOF node, with the first 256 code points in a bit map */
+
+ SV* invlist = invlist_clone(ssc->invlist);
+
+ PERL_ARGS_ASSERT_SSC_FINALIZE;
+
+ assert(OP(ssc) == ANYOF_SYNTHETIC);
+
+ /* The code in this file assumes that all but these flags aren't relevant
+ * to the SSC, except ANYOF_EMPTY_STRING, which should be cleared by the
+ * time we reach here */
+ assert(! (ANYOF_FLAGS(ssc) & ~ANYOF_LOCALE_FLAGS));
+
+ populate_ANYOF_from_invlist( (regnode *) ssc, &invlist);
+
+ set_ANYOF_arg(pRExC_state, (regnode *) ssc, invlist, NULL, NULL, FALSE);
+
+ assert(! (ANYOF_FLAGS(ssc) & ANYOF_LOCALE) || RExC_contains_locale);
+}
+
#define TRIE_LIST_ITEM(state,idx) (trie->states[state].trans.list)[ idx ]
#define TRIE_LIST_CUR(state) ( TRIE_LIST_ITEM( state, 0 ).forid )
#define TRIE_LIST_LEN(state) ( TRIE_LIST_ITEM( state, 0 ).newstate )
/*
Second Pass -- Flat Table Representation.
- we dont use the 0 slot of either trans[] or states[] so we add 1 to each.
- We know that we will need Charcount+1 trans at most to store the data
- (one row per char at worst case) So we preallocate both structures
- assuming worst case.
+ we dont use the 0 slot of either trans[] or states[] so we add 1 to
+ each. We know that we will need Charcount+1 trans at most to store
+ the data (one row per char at worst case) So we preallocate both
+ structures assuming worst case.
We then construct the trie using only the .next slots of the entry
structs.
- We use the .check field of the first entry of the node temporarily to
- make compression both faster and easier by keeping track of how many non
- zero fields are in the node.
+ We use the .check field of the first entry of the node temporarily
+ to make compression both faster and easier by keeping track of how
+ many non zero fields are in the node.
Since trans are numbered from 1 any 0 pointer in the table is a FAIL
transition.
- There are two terms at use here: state as a TRIE_NODEIDX() which is a
- number representing the first entry of the node, and state as a
- TRIE_NODENUM() which is the trans number. state 1 is TRIE_NODEIDX(1) and
- TRIE_NODENUM(1), state 2 is TRIE_NODEIDX(2) and TRIE_NODENUM(3) if there
- are 2 entrys per node. eg:
+ There are two terms at use here: state as a TRIE_NODEIDX() which is
+ a number representing the first entry of the node, and state as a
+ TRIE_NODENUM() which is the trans number. state 1 is TRIE_NODEIDX(1)
+ and TRIE_NODENUM(1), state 2 is TRIE_NODEIDX(2) and TRIE_NODENUM(3)
+ if there are 2 entrys per node. eg:
A B A B
1. 2 4 1. 3 7
3. 0 0 5. 0 0
4. 0 0 7. 0 0
- The table is internally in the right hand, idx form. However as we also
- have to deal with the states array which is indexed by nodenum we have to
- use TRIE_NODENUM() to convert.
+ The table is internally in the right hand, idx form. However as we
+ also have to deal with the states array which is indexed by nodenum
+ we have to use TRIE_NODENUM() to convert.
*/
DEBUG_TRIE_COMPILE_MORE_r( PerlIO_printf( Perl_debug_log,
STATIC void
S_make_trie_failtable(pTHX_ RExC_state_t *pRExC_state, regnode *source, regnode *stclass, U32 depth)
{
-/* The Trie is constructed and compressed now so we can build a fail array if it's needed
+/* The Trie is constructed and compressed now so we can build a fail array if
+ * it's needed
- This is basically the Aho-Corasick algorithm. Its from exercise 3.31 and 3.32 in the
- "Red Dragon" -- Compilers, principles, techniques, and tools. Aho, Sethi, Ullman 1985/88
+ This is basically the Aho-Corasick algorithm. Its from exercise 3.31 and
+ 3.32 in the
+ "Red Dragon" -- Compilers, principles, techniques, and tools. Aho, Sethi,
+ Ullman 1985/88
ISBN 0-201-10088-6
- We find the fail state for each state in the trie, this state is the longest proper
- suffix of the current state's 'word' that is also a proper prefix of another word in our
- trie. State 1 represents the word '' and is thus the default fail state. This allows
- the DFA not to have to restart after its tried and failed a word at a given point, it
- simply continues as though it had been matching the other word in the first place.
+ We find the fail state for each state in the trie, this state is the longest
+ proper suffix of the current state's 'word' that is also a proper prefix of
+ another word in our trie. State 1 represents the word '' and is thus the
+ default fail state. This allows the DFA not to have to restart after its
+ tried and failed a word at a given point, it simply continues as though it
+ had been matching the other word in the first place.
Consider
'abcdgu'=~/abcdefg|cdgu/
- When we get to 'd' we are still matching the first word, we would encounter 'g' which would
- fail, which would bring us to the state representing 'd' in the second word where we would
- try 'g' and succeed, proceeding to match 'cdgu'.
+ When we get to 'd' we are still matching the first word, we would encounter
+ 'g' which would fail, which would bring us to the state representing 'd' in
+ the second word where we would try 'g' and succeed, proceeding to match
+ 'cdgu'.
*/
/* add a fail transition */
const U32 trie_offset = ARG(source);
/* demq: the op(next)==code check is to see if we have "branch-branch" AFAICT */
if (OP(next) == code || code == IFTHEN) {
- /* NOTE - There is similar code to this block below for handling
- TRIE nodes on a re-study. If you change stuff here check there
- too. */
+ /* NOTE - There is similar code to this block below for
+ * handling TRIE nodes on a re-study. If you change stuff here
+ * check there too. */
SSize_t max1 = 0, min1 = SSize_t_MAX, num = 0;
regnode_ssc accum;
regnode * const startbranch=scan;
flags &= ~SCF_DO_STCLASS_AND;
StructCopy(&accum, data->start_class, regnode_ssc);
flags |= SCF_DO_STCLASS_OR;
- SET_SSC_EOS(data->start_class);
}
}
if (PERL_ENABLE_TRIE_OPTIMISATION && OP( startbranch ) == BRANCH ) {
/* demq.
- Assuming this was/is a branch we are dealing with: 'scan' now
- points at the item that follows the branch sequence, whatever
- it is. We now start at the beginning of the sequence and look
- for subsequences of
+ Assuming this was/is a branch we are dealing with: 'scan'
+ now points at the item that follows the branch sequence,
+ whatever it is. We now start at the beginning of the
+ sequence and look for subsequences of
BRANCH->EXACT=>x1
BRANCH->EXACT=>x2
tail
- which would be constructed from a pattern like /A|LIST|OF|WORDS/
+ which would be constructed from a pattern like
+ /A|LIST|OF|WORDS/
If we can find such a subsequence we need to turn the first
element into a trie and then add the subsequent branch exact
We have two cases
- 1. patterns where the whole set of branches can be converted.
+ 1. patterns where the whole set of branches can be
+ converted.
2. patterns where only a subset can be converted.
Step through the branches
cur represents each branch,
- noper is the first thing to be matched as part of that branch
+ noper is the first thing to be matched as part
+ of that branch
noper_next is the regnext() of that node.
- We normally handle a case like this /FOO[xyz]|BAR[pqr]/
- via a "jump trie" but we also support building with NOJUMPTRIE,
- which restricts the trie logic to structures like /FOO|BAR/.
-
- If noper is a trieable nodetype then the branch is a possible optimization
- target. If we are building under NOJUMPTRIE then we require that noper_next
- is the same as scan (our current position in the regex program).
-
- Once we have two or more consecutive such branches we can create a
- trie of the EXACT's contents and stitch it in place into the program.
-
- If the sequence represents all of the branches in the alternation we
- replace the entire thing with a single TRIE node.
-
- Otherwise when it is a subsequence we need to stitch it in place and
- replace only the relevant branches. This means the first branch has
- to remain as it is used by the alternation logic, and its next pointer,
- and needs to be repointed at the item on the branch chain following
- the last branch we have optimized away.
-
- This could be either a BRANCH, in which case the subsequence is internal,
- or it could be the item following the branch sequence in which case the
- subsequence is at the end (which does not necessarily mean the first node
- is the start of the alternation).
-
- TRIE_TYPE(X) is a define which maps the optype to a trietype.
+ We normally handle a case like this
+ /FOO[xyz]|BAR[pqr]/ via a "jump trie" but we also
+ support building with NOJUMPTRIE, which restricts
+ the trie logic to structures like /FOO|BAR/.
+
+ If noper is a trieable nodetype then the branch is
+ a possible optimization target. If we are building
+ under NOJUMPTRIE then we require that noper_next is
+ the same as scan (our current position in the regex
+ program).
+
+ Once we have two or more consecutive such branches
+ we can create a trie of the EXACT's contents and
+ stitch it in place into the program.
+
+ If the sequence represents all of the branches in
+ the alternation we replace the entire thing with a
+ single TRIE node.
+
+ Otherwise when it is a subsequence we need to
+ stitch it in place and replace only the relevant
+ branches. This means the first branch has to remain
+ as it is used by the alternation logic, and its
+ next pointer, and needs to be repointed at the item
+ on the branch chain following the last branch we
+ have optimized away.
+
+ This could be either a BRANCH, in which case the
+ subsequence is internal, or it could be the item
+ following the branch sequence in which case the
+ subsequence is at the end (which does not
+ necessarily mean the first node is the start of the
+ alternation).
+
+ TRIE_TYPE(X) is a define which maps the optype to a
+ trietype.
optype | trietype
----------------+-----------
);
});
- /* Is noper a trieable nodetype that can be merged with the
- * current trie (if there is one)? */
+ /* Is noper a trieable nodetype that can be merged
+ * with the current trie (if there is one)? */
if ( noper_trietype
&&
(
#endif
&& count < U16_MAX)
{
- /* Handle mergable triable node
- * Either we are the first node in a new trieable sequence,
- * in which case we do some bookkeeping, otherwise we update
- * the end pointer. */
+ /* Handle mergable triable node Either we are
+ * the first node in a new trieable sequence,
+ * in which case we do some bookkeeping,
+ * otherwise we update the end pointer. */
if ( !first ) {
first = cur;
if ( noper_trietype == NOTHING ) {
if ( noper_next_trietype ) {
trietype = noper_next_trietype;
} else if (noper_next_type) {
- /* a NOTHING regop is 1 regop wide. We need at least two
- * for a trie so we can't merge this in */
+ /* a NOTHING regop is 1 regop wide.
+ * We need at least two for a trie
+ * so we can't merge this in */
first = NULL;
}
} else {
} /* end handle mergable triable node */
else {
/* handle unmergable node -
- * noper may either be a triable node which can not be tried
- * together with the current trie, or a non triable node */
+ * noper may either be a triable node which can
+ * not be tried together with the current trie,
+ * or a non triable node */
if ( last ) {
- /* If last is set and trietype is not NOTHING then we have found
- * at least two triable branch sequences in a row of a similar
- * trietype so we can turn them into a trie. If/when we
- * allow NOTHING to start a trie sequence this condition will be
- * required, and it isn't expensive so we leave it in for now. */
+ /* If last is set and trietype is not
+ * NOTHING then we have found at least two
+ * triable branch sequences in a row of a
+ * similar trietype so we can turn them
+ * into a trie. If/when we allow NOTHING to
+ * start a trie sequence this condition
+ * will be required, and it isn't expensive
+ * so we leave it in for now. */
if ( trietype && trietype != NOTHING )
make_trie( pRExC_state,
startbranch, first, cur, tail, count,
trietype, depth+1 );
- last = NULL; /* note: we clear/update first, trietype etc below, so we dont do it here */
+ last = NULL; /* note: we clear/update
+ first, trietype etc below,
+ so we dont do it here */
}
if ( noper_trietype
#ifdef NOJUMPTRIE
&& noper_next == tail
#endif
){
- /* noper is triable, so we can start a new trie sequence */
+ /* noper is triable, so we can start a new
+ * trie sequence */
count = 1;
first = cur;
trietype = noper_trietype;
} else if (first) {
- /* if we already saw a first but the current node is not triable then we have
+ /* if we already saw a first but the
+ * current node is not triable then we have
* to reset the first information. */
count = 0;
first = NULL;
});
if ( last && trietype ) {
if ( trietype != NOTHING ) {
- /* the last branch of the sequence was part of a trie,
- * so we have to construct it here outside of the loop
- */
+ /* the last branch of the sequence was part of
+ * a trie, so we have to construct it here
+ * outside of the loop */
made= make_trie( pRExC_state, startbranch, first, scan, tail, count, trietype, depth+1 );
#ifdef TRIE_STUDY_OPT
if ( ((made == MADE_EXACT_TRIE &&
}
#endif
} else {
- /* at this point we know whatever we have is a NOTHING sequence/branch
- * AND if 'startbranch' is 'first' then we can turn the whole thing into a NOTHING
+ /* at this point we know whatever we have is a
+ * NOTHING sequence/branch AND if 'startbranch'
+ * is 'first' then we can turn the whole thing
+ * into a NOTHING
*/
if ( startbranch == first ) {
regnode *opt;
- /* the entire thing is a NOTHING sequence, something like this:
- * (?:|) So we can turn it into a plain NOTHING op. */
+ /* the entire thing is a NOTHING sequence,
+ * something like this: (?:|) So we can
+ * turn it into a plain NOTHING op. */
DEBUG_TRIE_COMPILE_r({
regprop(RExC_rx, mysv, cur);
PerlIO_printf( Perl_debug_log,
* can't match null string */
if (flags & SCF_DO_STCLASS_AND) {
ssc_cp_and(data->start_class, uc);
- CLEAR_SSC_EOS(data->start_class);
+ ANYOF_FLAGS(data->start_class) &= ~ANYOF_EMPTY_STRING;
ssc_clear_locale(data->start_class);
}
else if (flags & SCF_DO_STCLASS_OR) {
- CLEAR_SSC_EOS(data->start_class);
ssc_add_cp(data->start_class, uc);
ssc_and(pRExC_state, data->start_class, and_withp);
}
}
}
if (flags & SCF_DO_STCLASS_AND) {
- CLEAR_SSC_EOS(data->start_class);
- ANYOF_POSIXL_ZERO(data->start_class);
- ssc_intersection(data->start_class, EXACTF_invlist, FALSE);
+ ANYOF_FLAGS(data->start_class) &= ~ANYOF_EMPTY_STRING;
+ ANYOF_POSIXL_ZERO(data->start_class);
+ ssc_intersection(data->start_class, EXACTF_invlist, FALSE);
}
else if (flags & SCF_DO_STCLASS_OR) {
- CLEAR_SSC_EOS(data->start_class);
ssc_union(data->start_class, EXACTF_invlist, FALSE);
ssc_and(pRExC_state, data->start_class, and_withp);
}
flags &= ~SCF_DO_STCLASS_AND;
StructCopy(&this_class, data->start_class, regnode_ssc);
flags |= SCF_DO_STCLASS_OR;
- SET_SSC_EOS(data->start_class);
}
} else { /* Non-zero len */
if (flags & SCF_DO_STCLASS_OR) {
ssc_intersection(data->start_class,
PL_XPosix_ptrs[_CC_VERTSPACE], FALSE);
ssc_clear_locale(data->start_class);
- CLEAR_SSC_EOS(data->start_class); /* No match on empty */
+ ANYOF_FLAGS(data->start_class) &= ~ANYOF_EMPTY_STRING;
}
else if (flags & SCF_DO_STCLASS_OR) {
ssc_union(data->start_class,
PL_XPosix_ptrs[_CC_VERTSPACE],
FALSE);
ssc_and(pRExC_state, data->start_class, and_withp);
- CLEAR_SSC_EOS(data->start_class); /* No match on empty */
}
flags &= ~SCF_DO_STCLASS;
}
U8 classnum;
U8 namedclass;
- CLEAR_SSC_EOS(data->start_class); /* No match on empty */
+ if (flags & SCF_DO_STCLASS_AND) {
+ ANYOF_FLAGS(data->start_class) &= ~ANYOF_EMPTY_STRING;
+ }
/* Some of the logic below assumes that switching
locale on will only add false positives. */
ssc_init(pRExC_state, data->start_class);
} else {
/* AND before and after: combine and continue */
- const int was = TEST_SSC_EOS(data->start_class);
-
ssc_and(pRExC_state, data->start_class, &intrnl);
- if (was)
- SET_SSC_EOS(data->start_class);
}
}
}
*minnextp += min;
if (f & SCF_DO_STCLASS_AND) {
- const int was = TEST_SSC_EOS(data->start_class);
-
ssc_and(pRExC_state, data->start_class, &intrnl);
- if (was)
- SET_SSC_EOS(data->start_class);
}
if (data) {
if (data_fake.flags & (SF_HAS_PAR|SF_IN_PAR))
flags &= ~SCF_DO_STCLASS_AND;
StructCopy(&accum, data->start_class, regnode_ssc);
flags |= SCF_DO_STCLASS_OR;
- SET_SSC_EOS(data->start_class);
}
}
scan= tail;
if ((!(r->anchored_substr || r->anchored_utf8) || r->anchored_offset)
&& stclass_flag
- && ! TEST_SSC_EOS(data.start_class)
+ && ! ANYOF_FLAGS(data.start_class) & ANYOF_EMPTY_STRING
&& !ssc_is_anything(data.start_class))
{
const U32 n = add_data(pRExC_state, STR_WITH_LEN("f"));
r->check_substr = r->check_utf8 = r->anchored_substr = r->anchored_utf8
= r->float_substr = r->float_utf8 = NULL;
- if (! TEST_SSC_EOS(data.start_class)
+ if (! ANYOF_FLAGS(data.start_class) & ANYOF_EMPTY_STRING
&& !ssc_is_anything(data.start_class))
{
const U32 n = add_data(pRExC_state, STR_WITH_LEN("f"));
/*
- regprop - printable representation of opcode
*/
-#define EMIT_ANYOF_TEST_SEPARATOR(do_sep,sv,flags) \
-STMT_START { \
- if (do_sep) { \
- Perl_sv_catpvf(aTHX_ sv,"%s][%s",PL_colors[1],PL_colors[0]); \
- if (flags & ANYOF_INVERT) \
- /*make sure the invert info is in each */ \
- sv_catpvs(sv, "^"); \
- do_sep = 0; \
- } \
-} STMT_END
void
Perl_regprop(pTHX_ const regexp *prog, SV *sv, const regnode *o)
|| _CC_VERTSPACE != 16
#error Need to adjust order of anyofs[]
#endif
- "[\\w]",
- "[\\W]",
- "[\\d]",
- "[\\D]",
+ "\\w",
+ "\\W",
+ "\\d",
+ "\\D",
"[:alpha:]",
"[:^alpha:]",
"[:lower:]",
"[:^graph:]",
"[:cased:]",
"[:^cased:]",
- "[\\s]",
- "[\\S]",
+ "\\s",
+ "\\S",
"[:blank:]",
"[:^blank:]",
"[:xdigit:]",
"[:^cntrl:]",
"[:ascii:]",
"[:^ascii:]",
- "[\\v]",
- "[\\V]"
+ "\\v",
+ "\\V"
};
RXi_GET_DECL(prog,progi);
GET_RE_DEBUG_FLAGS_DECL;
/* output what the standard cp 0-255 bitmap matches */
do_sep = put_latin1_charclass_innards(sv, ANYOF_BITMAP(o));
- EMIT_ANYOF_TEST_SEPARATOR(do_sep,sv,flags);
- /* output any special charclass tests (used entirely under use locale) */
+ /* output any special charclass tests (used entirely under use
+ * locale) * */
if (ANYOF_POSIXL_TEST_ANY_SET(o)) {
int i;
- for (i = 0; i < (int)(sizeof(anyofs)/sizeof(char*)); i++) {
+ for (i = 0; i < ANYOF_POSIXL_MAX; i++) {
if (ANYOF_POSIXL_TEST(o,i)) {
sv_catpv(sv, anyofs[i]);
do_sep = 1;
}
}
- EMIT_ANYOF_TEST_SEPARATOR(do_sep,sv,flags);
+ if (flags & (ANYOF_ABOVE_LATIN1_ALL|ANYOF_ABOVE_LATIN1_ALL)
+ || ANYOF_NONBITMAP(o))
+ {
+ if (do_sep) {
+ Perl_sv_catpvf(aTHX_ sv,"%s][%s",PL_colors[1],PL_colors[0]);
+ if (flags & ANYOF_INVERT)
+ /*make sure the invert info is in each */
+ sv_catpvs(sv, "^");
+ }
if (flags & ANYOF_NON_UTF8_LATIN1_ALL) {
sv_catpvs(sv, "{non-utf8-latin1-all}");
SvREFCNT_dec_NN(lv);
}
}
+ }
Perl_sv_catpvf(aTHX_ sv, "%s]", PL_colors[1]);
}
Perl_sv_catpvf(aTHX_ sv, "[illegal type=%d])", index);
}
else {
+ if (*anyofs[index] != '[') {
+ sv_catpv(sv, "[");
+ }
sv_catpv(sv, anyofs[index]);
+ if (*anyofs[index] != '[') {
+ sv_catpv(sv, "]");
+ }
}
}
else if (k == BRANCHJ && (OP(o) == UNLESSM || OP(o) == IFMATCH))
https://perl5.git.perl.org / perl5.git / blobdiff