+ /* Must be NUL-terminated */
+ assert(*(input_string + len) == '\0');
+
+ /* If this locale has defective collation, skip */
+ if (PL_collxfrm_base == 0 && PL_collxfrm_mult == 0) {
+ DEBUG_L(PerlIO_printf(Perl_debug_log,
+ "_mem_collxfrm: locale's collation is defective\n"));
+ goto bad;
+ }
+
+ /* Replace any embedded NULs with the control that sorts before any others.
+ * This will give as good as possible results on strings that don't
+ * otherwise contain that character, but otherwise there may be
+ * less-than-perfect results with that character and NUL. This is
+ * unavoidable unless we replace strxfrm with our own implementation. */
+ if (s_strlen < len) { /* Only execute if there is an embedded NUL */
+ char * e = s + len;
+ char * sans_nuls;
+ STRLEN sans_nuls_len;
+ STRLEN sans_nuls_pos;
+ int try_non_controls;
+ char this_replacement_char[] = "?\0"; /* Room for a two-byte string,
+ making sure 2nd byte is NUL.
+ */
+ STRLEN this_replacement_len;
+
+ /* If we don't know what non-NUL control character sorts lowest for
+ * this locale, find it */
+ if (PL_strxfrm_NUL_replacement == '\0') {
+ int j;
+ char * cur_min_x = NULL; /* The min_char's xfrm, (except it also
+ includes the collation index
+ prefixed. */
+
+ DEBUG_Lv(PerlIO_printf(Perl_debug_log, "Looking to replace NUL\n"));
+
+ /* Unlikely, but it may be that no control will work to replace
+ * NUL, in which case we instead look for any character. Controls
+ * are preferred because collation order is, in general, context
+ * sensitive, with adjoining characters affecting the order, and
+ * controls are less likely to have such interactions, allowing the
+ * NUL-replacement to stand on its own. (Another way to look at it
+ * is to imagine what would happen if the NUL were replaced by a
+ * combining character; it wouldn't work out all that well.) */
+ for (try_non_controls = 0;
+ try_non_controls < 2;
+ try_non_controls++)
+ {
+ /* Look through all legal code points (NUL isn't) */
+ for (j = 1; j < 256; j++) {
+ char * x; /* j's xfrm plus collation index */
+ STRLEN x_len; /* length of 'x' */
+ STRLEN trial_len = 1;
+
+ /* Create a 1 byte string of the current code point */
+ char cur_source[] = { (char) j, '\0' };
+
+ if (! try_non_controls && (PL_in_utf8_COLLATE_locale)
+ ? ! isCNTRL_L1(j)
+ : ! isCNTRL_LC(j))
+ {
+ continue;
+ }
+
+ /* Then transform it */
+ x = _mem_collxfrm(cur_source, trial_len, &x_len,
+ 0 /* The string is not in UTF-8 */);
+
+ /* Ignore any character that didn't successfully transform.
+ * */
+ if (! x) {
+ continue;
+ }
+
+ /* If this character's transformation is lower than
+ * the current lowest, this one becomes the lowest */
+ if ( cur_min_x == NULL
+ || strLT(x + COLLXFRM_HDR_LEN,
+ cur_min_x + COLLXFRM_HDR_LEN))
+ {
+ PL_strxfrm_NUL_replacement = j;
+ cur_min_x = x;
+ }
+ else {
+ Safefree(x);
+ }
+ } /* end of loop through all 255 characters */
+
+ /* Stop looking if found */
+ if (cur_min_x) {
+ break;
+ }
+
+ /* Unlikely, but possible, if there aren't any controls that
+ * work in the locale, repeat the loop, looking for any
+ * character that works */
+ DEBUG_L(PerlIO_printf(Perl_debug_log,
+ "_mem_collxfrm: No control worked. Trying non-controls\n"));
+ } /* End of loop to try first the controls, then any char */
+
+ if (! cur_min_x) {
+ DEBUG_L(PerlIO_printf(Perl_debug_log,
+ "_mem_collxfrm: Couldn't find any character to replace"
+ " embedded NULs in locale %s with", PL_collation_name));
+ goto bad;
+ }
+
+ DEBUG_L(PerlIO_printf(Perl_debug_log,
+ "_mem_collxfrm: Replacing embedded NULs in locale %s with "
+ "0x%02X\n", PL_collation_name, PL_strxfrm_NUL_replacement));
+
+ Safefree(cur_min_x);
+ } /* End of determining the character that is to replace NULs */
+
+ /* If the replacement is variant under UTF-8, it must match the
+ * UTF8-ness as the original */
+ if ( ! UVCHR_IS_INVARIANT(PL_strxfrm_NUL_replacement) && utf8) {
+ this_replacement_char[0] =
+ UTF8_EIGHT_BIT_HI(PL_strxfrm_NUL_replacement);
+ this_replacement_char[1] =
+ UTF8_EIGHT_BIT_LO(PL_strxfrm_NUL_replacement);
+ this_replacement_len = 2;
+ }
+ else {
+ this_replacement_char[0] = PL_strxfrm_NUL_replacement;
+ /* this_replacement_char[1] = '\0' was done at initialization */
+ this_replacement_len = 1;
+ }
+
+ /* The worst case length for the replaced string would be if every
+ * character in it is NUL. Multiply that by the length of each
+ * replacement, and allow for a trailing NUL */
+ sans_nuls_len = (len * this_replacement_len) + 1;
+ Newx(sans_nuls, sans_nuls_len, char);
+ *sans_nuls = '\0';
+ sans_nuls_pos = 0;
+
+ /* Replace each NUL with the lowest collating control. Loop until have
+ * exhausted all the NULs */
+ while (s + s_strlen < e) {
+ sans_nuls_pos = my_strlcat(sans_nuls + sans_nuls_pos,
+ s,
+ sans_nuls_len);
+
+ /* Do the actual replacement */
+ sans_nuls_pos = my_strlcat(sans_nuls + sans_nuls_pos,
+ this_replacement_char,
+ sans_nuls_len);
+
+ /* Move past the input NUL */
+ s += s_strlen + 1;
+ s_strlen = strlen(s);
+ }
+
+ /* And add anything that trails the final NUL */
+ my_strlcat(sans_nuls + sans_nuls_pos, s, sans_nuls_len);
+
+ /* Switch so below we transform this modified string */
+ s = sans_nuls;
+ len = strlen(s);
+ } /* End of replacing NULs */
+
+ /* Make sure the UTF8ness of the string and locale match */
+ if (utf8 != PL_in_utf8_COLLATE_locale) {
+ const char * const t = s; /* Temporary so we can later find where the
+ input was */
+
+ /* Here they don't match. Change the string's to be what the locale is
+ * expecting */
+
+ if (! utf8) { /* locale is UTF-8, but input isn't; upgrade the input */
+ s = (char *) bytes_to_utf8((const U8 *) s, &len);
+ utf8 = TRUE;
+ }
+ else { /* locale is not UTF-8; but input is; downgrade the input */
+
+ s = (char *) bytes_from_utf8((const U8 *) s, &len, &utf8);
+
+ /* If the downgrade was successful we are done, but if the input
+ * contains things that require UTF-8 to represent, have to do
+ * damage control ... */
+ if (UNLIKELY(utf8)) {
+
+ /* What we do is construct a non-UTF-8 string with
+ * 1) the characters representable by a single byte converted
+ * to be so (if necessary);
+ * 2) and the rest converted to collate the same as the
+ * highest collating representable character. That makes
+ * them collate at the end. This is similar to how we
+ * handle embedded NULs, but we use the highest collating
+ * code point instead of the smallest. Like the NUL case,
+ * this isn't perfect, but is the best we can reasonably
+ * do. Every above-255 code point will sort the same as
+ * the highest-sorting 0-255 code point. If that code
+ * point can combine in a sequence with some other code
+ * points for weight calculations, us changing something to
+ * be it can adversely affect the results. But in most
+ * cases, it should work reasonably. And note that this is
+ * really an illegal situation: using code points above 255
+ * on a locale where only 0-255 are valid. If two strings
+ * sort entirely equal, then the sort order for the
+ * above-255 code points will be in code point order. */
+
+ utf8 = FALSE;
+
+ /* If we haven't calculated the code point with the maximum
+ * collating order for this locale, do so now */
+ if (! PL_strxfrm_max_cp) {
+ int j;
+
+ /* The current transformed string that collates the
+ * highest (except it also includes the prefixed collation
+ * index. */
+ char * cur_max_x = NULL;
+
+ /* Look through all legal code points (NUL isn't) */
+ for (j = 1; j < 256; j++) {
+ char * x;
+ STRLEN x_len;
+
+ /* Create a 1-char string of the current code point. */
+ char cur_source[] = { (char) j, '\0' };
+
+ /* Then transform it */
+ x = _mem_collxfrm(cur_source, 1, &x_len, FALSE);
+
+ /* If something went wrong (which it shouldn't), just
+ * ignore this code point */
+ if (! x) {
+ continue;
+ }
+
+ /* If this character's transformation is higher than
+ * the current highest, this one becomes the highest */
+ if ( cur_max_x == NULL
+ || strGT(x + COLLXFRM_HDR_LEN,
+ cur_max_x + COLLXFRM_HDR_LEN))
+ {
+ PL_strxfrm_max_cp = j;
+ cur_max_x = x;
+ }
+ else {
+ Safefree(x);
+ }
+ }
+
+ if (! cur_max_x) {
+ DEBUG_L(PerlIO_printf(Perl_debug_log,
+ "_mem_collxfrm: Couldn't find any character to"
+ " replace above-Latin1 chars in locale %s with",
+ PL_collation_name));
+ goto bad;
+ }
+
+ DEBUG_L(PerlIO_printf(Perl_debug_log,
+ "_mem_collxfrm: highest 1-byte collating character"
+ " in locale %s is 0x%02X\n",
+ PL_collation_name,
+ PL_strxfrm_max_cp));
+
+ Safefree(cur_max_x);
+ }
+
+ /* Here we know which legal code point collates the highest.
+ * We are ready to construct the non-UTF-8 string. The length
+ * will be at least 1 byte smaller than the input string
+ * (because we changed at least one 2-byte character into a
+ * single byte), but that is eaten up by the trailing NUL */
+ Newx(s, len, char);
+
+ {
+ STRLEN i;
+ STRLEN d= 0;
+ char * e = (char *) t + len;
+
+ for (i = 0; i < len; i+= UTF8SKIP(t + i)) {
+ U8 cur_char = t[i];
+ if (UTF8_IS_INVARIANT(cur_char)) {
+ s[d++] = cur_char;
+ }
+ else if (UTF8_IS_NEXT_CHAR_DOWNGRADEABLE(t + i, e)) {
+ s[d++] = EIGHT_BIT_UTF8_TO_NATIVE(cur_char, t[i+1]);
+ }
+ else { /* Replace illegal cp with highest collating
+ one */
+ s[d++] = PL_strxfrm_max_cp;
+ }
+ }
+ s[d++] = '\0';
+ Renew(s, d, char); /* Free up unused space */
+ }
+ }
+ }
+
+ /* Here, we have constructed a modified version of the input. It could
+ * be that we already had a modified copy before we did this version.
+ * If so, that copy is no longer needed */
+ if (t != input_string) {
+ Safefree(t);
+ }
+ }
+
+ length_in_chars = (utf8)
+ ? utf8_length((U8 *) s, (U8 *) s + len)
+ : len;
+
+ /* The first element in the output is the collation id, used by
+ * sv_collxfrm(); then comes the space for the transformed string. The
+ * equation should give us a good estimate as to how much is needed */
+ xAlloc = COLLXFRM_HDR_LEN
+ + PL_collxfrm_base
+ + (PL_collxfrm_mult * length_in_chars);