tr///; simplify $utf8 =~ tr/nonutf8/nonutf8/

The run-time code to handle a non-utf8 tr/// against a utf8 string
is complex, with many variants of similar code repeated depending on the
presence of the /s and /c flags.

Simplify them all into a single code block by changing how the translation
table is stored. Formerly, the tr struct contained possibly two tables:
the basic 0-255 slot one, plus in the presence of /c, a second one
to map the implicit search range (\x{100}...) against any residual
replacement chars not consumed by the first table.

This commit merges the two tables into a single unified whole. For example

    tr/\x00-\xfe/abcd/c

is equivalent to

    tr/xff-\x{7fffffff}/abcd/

which generates a 259-entry translation table consisting of:

    0x00  => -1
    0x01  => -1
    ...
    0xfe  => -1
    0xff  =>  a
    0x100 =>  b
    0x101 =>  c
    0x102 =>  d

In addition we store:
    1) the size of the translation table (0x103 in the example above);
    2) an extra 'wildcard' entry stored 1 slot beyond the main table,
       which specifies the action for any codepoints outside the range of
       the table (i.e. chars 0x103..0x7fffffff). This can be either:
        a) a character, when the last replacement char is repeated;
        b) -1 when /c isn't in effect;
        c) -2 when /d is in effect;
        c) -3 identity: when the replacement list is empty but not /d.

       In the example above, this would be
            0x103 =>  d

The addition of -3 as a valid slot value is new.

This makes the main runtime code for the utf8 string with non-utf8 tr//
case look like, at its core:

    size = tbl->size;
    mapped_ch = tbl->map[ch >= size ? size : ch];

which then processes mapped_ch based on whether its >=0, or -1/-2/-3.

This is a lot simpler than the old scheme, and should generally be faster
too.

1 files changed, 20 insertions, 94 deletions

diff --git a/doop.c b/doop.c
index edc403838c..22431ef7f0 100644
--- a/doop.c
+++ b/doop.c
@@ -166,11 +166,11 @@ S_do_trans_complex(pTHX_ SV * const sv)
     U8 *s = (U8*)SvPV_nomg(sv, len);
     U8 * const send = s+len;
     I32 matches = 0;
-    const OPtrans_map_ex * const extbl = (OPtrans_map_ex*)cPVOP->op_pv;
+    const OPtrans_map * const tbl = (OPtrans_map*)cPVOP->op_pv;
 
     PERL_ARGS_ASSERT_DO_TRANS_COMPLEX;
 
-    if (!extbl)
+    if (!tbl)
 	Perl_croak(aTHX_ "panic: do_trans_complex line %d",__LINE__);
 
     if (!SvUTF8(sv)) {
@@ -180,7 +180,7 @@ S_do_trans_complex(pTHX_ SV * const sv)
 	if (PL_op->op_private & OPpTRANS_SQUASH) {
 	    const U8* p = send;
 	    while (s < send) {
-		const I32 ch = extbl->map[*s];
+		const I32 ch = tbl->map[*s];
 		if (ch >= 0) {
 		    *d = (U8)ch;
 		    matches++;
@@ -196,7 +196,7 @@ S_do_trans_complex(pTHX_ SV * const sv)
 	}
 	else {
 	    while (s < send) {
-		const I32 ch = extbl->map[*s];
+		const I32 ch = tbl->map[*s];
 		if (ch >= 0) {
 		    matches++;
 		    *d++ = (U8)ch;
@@ -212,25 +212,19 @@ S_do_trans_complex(pTHX_ SV * const sv)
 	SvCUR_set(sv, d - dstart);
     }
     else { /* is utf8 */
-	const I32 complement = PL_op->op_private & OPpTRANS_COMPLEMENT;
+	const bool squash =  cBOOL(PL_op->op_private & OPpTRANS_SQUASH);
 	const I32 grows = PL_op->op_private & OPpTRANS_GROWS;
-	const I32 del = PL_op->op_private & OPpTRANS_DELETE;
 	U8 *d;
 	U8 *dstart;
-	SSize_t excess = 0;
+	Size_t size = tbl->size;
+        UV pch = 0xfeedface;
 
 	if (grows)
 	    Newx(d, len*2+1, U8);
 	else
 	    d = s;
 	dstart = d;
-	if (complement)
-            /* number of replacement chars in excess of any 0x00..0xff
-             * search characters */
-	    excess = extbl->excess_len;
 
-	if (PL_op->op_private & OPpTRANS_SQUASH) {
-	    UV pch = 0xfeedface;
 	    while (s < send) {
 		STRLEN len;
 		const UV comp = utf8n_to_uvchr(s, send - s, &len,
@@ -238,40 +232,13 @@ S_do_trans_complex(pTHX_ SV * const sv)
 		UV     ch;
                 short sch;
 
-		if (comp > 0xff) {
-		    if (!complement) {
-			Move(s, d, len, U8);
-			d += len;
-		    }
-		    else {
-                        /* use the implicit 0x100..0x7fffffff search range */
-                        UV comp100 = comp - 0x100;
-			matches++;
-                        ch = del
-                               /* setting ch to pch forces char to be deleted */
-                             ? ((excess > (IV)comp100)
-                                            ? (UV)extbl->map_ex[comp100]
-                                            : pch           )
-
-			     : (        (excess == -1) ? comp :
-                                 (UV)((  excess ==  0
-                                      || excess <= (IV)comp100)
-                                            ? extbl->repeat_char
-                                            : extbl->map_ex[comp100]
-                                     )
-                               );
-                        if (ch != pch) {
-                            d = uvchr_to_utf8(d, ch);
-                            pch = ch;
-                        }
-                        s += len;
-                        continue;
-		    }
-		}
-		else if ((sch = extbl->map[comp]) >= 0) {
+                sch = tbl->map[comp >= size ? size : comp];
+
+		if (sch >= 0) {
                     ch = (UV)sch;
+                  replace:
 		    matches++;
-		    if (ch != pch) {
+		    if (LIKELY(!squash || ch != pch)) {
 		        d = uvchr_to_utf8(d, ch);
 		        pch = ch;
 		    }
@@ -282,59 +249,18 @@ S_do_trans_complex(pTHX_ SV * const sv)
 		    Move(s, d, len, U8);
 		    d += len;
 		}
-		else if (sch == -2)      /* -2 is delete character */
+		else if (sch == -2)     /* -2 is delete character */
 		    matches++;
+                else {
+                    assert(sch == -3);  /* -3 is empty replacement */
+                    ch = comp;
+                    goto replace;
+                }
+
 		s += len;
 		pch = 0xfeedface;
 	    }
-	}
-	else {
-	    while (s < send) {
-		STRLEN len;
-		const UV comp = utf8n_to_uvchr(s, send - s, &len,
-					       UTF8_ALLOW_DEFAULT);
-		UV     ch;
-		short sch;
-		if (comp > 0xff) {
-		    if (!complement) {
-			Move(s, d, len, U8);
-			d += len;
-		    }
-		    else {
-                        /* use the implicit 0x100..0x7fffffff search range */
-                        UV comp100 = comp - 0x100;
-			matches++;
-                        if (del) {
-                             if (excess > (IV)comp100) {
-                                ch = (UV)extbl->map_ex[comp100];
-                                d = uvchr_to_utf8(d, ch);
-                            }
-                        }
-                        else {
-                            /* tr/...//c should call S_do_trans_count
-                             * instead */
-                            assert(excess != -1);
-			    ch = (   excess ==  0
-                                      || excess <= (IV)comp100)
-                                            ? (UV)extbl->repeat_char
-                                            : (UV)extbl->map_ex[comp100];
-                            d = uvchr_to_utf8(d, ch);
-                        }
-		    }
-		}
-		else if ((sch = extbl->map[comp]) >= 0) {
-		    d = uvchr_to_utf8(d, (UV)sch);
-		    matches++;
-		}
-		else if (sch == -1) {	/* -1 is unmapped character */
-		    Move(s, d, len, U8);
-		    d += len;
-		}
-		else if (sch == -2)      /* -2 is delete character */
-		    matches++;
-		s += len;
-	    }
-	}
+
 	if (grows) {
 	    sv_setpvn(sv, (char*)dstart, d - dstart);
 	    Safefree(dstart);