- /* and_with's ARG may match things that don't require UTF8.
- * And now cl's will too, in spite of this being an 'and'. See
- * the comments below about the kludge */
- cl->flags |= and_with->flags & ANYOF_NONBITMAP_NON_UTF8;
- }
- }
- else {
- /* Here, both 'and_with' and cl match something outside the
- * bitmap. Currently we do not do the intersection, so just match
- * whatever cl had at the beginning. */
- }
-
-
- /* Take the intersection of the two sets of flags. However, the
- * ANYOF_NONBITMAP_NON_UTF8 flag is treated as an 'or'. This is a
- * kludge around the fact that this flag is not treated like the others
- * which are initialized in cl_anything(). The way the optimizer works
- * is that the synthetic start class (SSC) is initialized to match
- * anything, and then the first time a real node is encountered, its
- * values are AND'd with the SSC's with the result being the values of
- * the real node. However, there are paths through the optimizer where
- * the AND never gets called, so those initialized bits are set
- * inappropriately, which is not usually a big deal, as they just cause
- * false positives in the SSC, which will just mean a probably
- * imperceptible slow down in execution. However this bit has a
- * higher false positive consequence in that it can cause utf8.pm,
- * utf8_heavy.pl ... to be loaded when not necessary, which is a much
- * bigger slowdown and also causes significant extra memory to be used.
- * In order to prevent this, the code now takes a different tack. The
- * bit isn't set unless some part of the regular expression needs it,
- * but once set it won't get cleared. This means that these extra
- * modules won't get loaded unless there was some path through the
- * pattern that would have required them anyway, and so any false
- * positives that occur by not ANDing them out when they could be
- * aren't as severe as they would be if we treated this bit like all
- * the others */
- outside_bitmap_but_not_utf8 = (cl->flags | and_with->flags)
- & ANYOF_NONBITMAP_NON_UTF8;
- cl->flags &= and_with->flags;
- cl->flags |= outside_bitmap_but_not_utf8;
+/* '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)
+{
+ /* Accumulate into SSC 'ssc' its 'AND' with 'and_with', which is either
+ * another SSC or a regular ANYOF class. Can create false positives. */
+
+ SV* anded_cp_list;
+ U8 anded_flags;
+
+ PERL_ARGS_ASSERT_SSC_AND;
+
+ assert(OP(ssc) == ANYOF_SYNTHETIC);
+
+ /* '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.
+ * 'and_with' may be inverted. When not inverted, we have the situation of
+ * computing:
+ * (C1 | P1) & (C2 | P2)
+ * = (C1 & (C2 | P2)) | (P1 & (C2 | P2))
+ * = ((C1 & C2) | (C1 & P2)) | ((P1 & C2) | (P1 & P2))
+ * <= ((C1 & C2) | P2)) | ( P1 | (P1 & P2))
+ * <= ((C1 & C2) | P1 | P2)
+ * Alternatively, the last few steps could be:
+ * = ((C1 & C2) | (C1 & P2)) | ((P1 & C2) | (P1 & P2))
+ * <= ((C1 & C2) | C1 ) | ( C2 | (P1 & P2))
+ * <= (C1 | C2 | (P1 & P2))
+ * We favor the second approach if either P1 or P2 is non-empty. This is
+ * because these components are a barrier to doing optimizations, as what
+ * they match cannot be known until the moment of matching as they are
+ * dependent on the current locale, 'AND"ing them likely will reduce or
+ * eliminate them.
+ * But we can do better if we know that C1,P1 are in their initial state (a
+ * frequent occurrence), each matching everything:
+ * (<everything>) & (C2 | P2) = C2 | P2
+ * Similarly, if C2,P2 are in their initial state (again a frequent
+ * occurrence), the result is a no-op
+ * (C1 | P1) & (<everything>) = C1 | P1
+ *
+ * Inverted, we have
+ * (C1 | P1) & ~(C2 | P2) = (C1 | P1) & (~C2 & ~P2)
+ * = (C1 & (~C2 & ~P2)) | (P1 & (~C2 & ~P2))
+ * <= (C1 & ~C2) | (P1 & ~P2)
+ * */
+
+ if ((ANYOF_FLAGS(and_with) & ANYOF_INVERT)
+ && OP(and_with) != ANYOF_SYNTHETIC)
+ {
+ unsigned int i;
+
+ ssc_intersection(ssc,
+ anded_cp_list,
+ FALSE /* Has already been inverted */
+ );
+
+ /* If either P1 or P2 is empty, the intersection will be also; can skip
+ * the loop */
+ if (! (ANYOF_FLAGS(and_with) & ANYOF_POSIXL)) {
+ ANYOF_POSIXL_ZERO(ssc);
+ }
+ else if (ANYOF_POSIXL_TEST_ANY_SET(ssc)) {
+
+ /* Note that the Posix class component P from 'and_with' actually
+ * looks like:
+ * P = Pa | Pb | ... | Pn
+ * where each component is one posix class, such as in [\w\s].
+ * Thus
+ * ~P = ~(Pa | Pb | ... | Pn)
+ * = ~Pa & ~Pb & ... & ~Pn
+ * <= ~Pa | ~Pb | ... | ~Pn
+ * The last is something we can easily calculate, but unfortunately
+ * is likely to have many false positives. We could do better
+ * in some (but certainly not all) instances if two classes in
+ * P have known relationships. For example
+ * :lower: <= :alpha: <= :alnum: <= \w <= :graph: <= :print:
+ * So
+ * :lower: & :print: = :lower:
+ * And similarly for classes that must be disjoint. For example,
+ * since \s and \w can have no elements in common based on rules in
+ * the POSIX standard,
+ * \w & ^\S = nothing
+ * Unfortunately, some vendor locales do not meet the Posix
+ * standard, in particular almost everything by Microsoft.
+ * The loop below just changes e.g., \w into \W and vice versa */
+
+ regnode_charclass_posixl temp;
+ int add = 1; /* To calculate the index of the complement */
+
+ ANYOF_POSIXL_ZERO(&temp);
+ for (i = 0; i < ANYOF_MAX; i++) {
+ assert(i % 2 != 0
+ || ! ANYOF_POSIXL_TEST(and_with, i)
+ || ! ANYOF_POSIXL_TEST(and_with, i + 1));
+
+ if (ANYOF_POSIXL_TEST(and_with, i)) {
+ ANYOF_POSIXL_SET(&temp, i + add);
+ }
+ add = 0 - add; /* 1 goes to -1; -1 goes to 1 */
+ }
+ ANYOF_POSIXL_AND(&temp, ssc);
+
+ } /* else ssc already has no posixes */
+ } /* else: Not inverted. This routine is a no-op if 'and_with' is an SSC
+ in its initial state */
+ else if (OP(and_with) != ANYOF_SYNTHETIC
+ || ! ssc_is_cp_posixl_init(pRExC_state, and_with))
+ {
+ /* But if 'ssc' is in its initial state, the result is just 'and_with';
+ * copy it over 'ssc' */
+ if (ssc_is_cp_posixl_init(pRExC_state, ssc)) {
+ if (OP(and_with) == ANYOF_SYNTHETIC) {
+ StructCopy(and_with, ssc, regnode_ssc);
+ }
+ else {
+ ssc->invlist = anded_cp_list;
+ ANYOF_POSIXL_ZERO(ssc);
+ if (ANYOF_FLAGS(and_with) & ANYOF_POSIXL) {
+ ANYOF_POSIXL_OR(and_with, ssc);
+ }
+ }
+ }
+ else if ((ANYOF_FLAGS(ssc) & ANYOF_POSIXL)
+ || (ANYOF_FLAGS(and_with) & ANYOF_POSIXL))
+ {
+ /* One or the other of P1, P2 is non-empty. */
+ ANYOF_POSIXL_AND(and_with, ssc);
+ ssc_union(ssc, anded_cp_list, FALSE);
+ }
+ else { /* P1 = P2 = empty */
+ ssc_intersection(ssc, anded_cp_list, FALSE);
+ }
https://perl5.git.perl.org / perl5.git / blobdiff