libfoundation: Add MCStringCopyReversed()

peter-b · peter-b · commit bfb6d786e47d · 2017-03-31T11:10:13.000+01:00
Strings cannot be reversed in-place in the general case.  There is no
upper limit on the number of codeunits in a grapheme, which means that
a temporary buffer of at the same length of the string is required for
general correctness.

This patch adds a "reversed copy" function which performs a deep copy
of the source string, and then constructs the reversed form in the
copy by re-reading from the source string via a grapheme break
iterator.

In practice, the "trivial" flag is not getting set for trivial
strings, so all strings that use UTF-16 internal representatino go
through the slow grapheme break iterator path.
diff --git a/libfoundation/include/foundation.h b/libfoundation/include/foundation.h
@@ -2144,6 +2144,11 @@ MC_DLLEXPORT bool MCStringMutableCopySubstringAndRelease(MCStringRef string, MCR
 
 /////////
 
+// Copy a string, reversing its contents
+MC_DLLEXPORT bool MCStringCopyReversed(MCStringRef string, MCStringRef& r_reversed);
+
+/////////
+
 // Returns true if the string is mutable
 MC_DLLEXPORT bool MCStringIsMutable(const MCStringRef string);
 
diff --git a/libfoundation/src/foundation-string.cpp b/libfoundation/src/foundation-string.cpp
@@ -1475,6 +1475,75 @@ bool MCStringMutableCopySubstringAndRelease(MCStringRef self, MCRange p_range, M
 
 ////////////////////////////////////////////////////////////////////////////////
 
+MC_DLLEXPORT_DEF
+bool MCStringCopyReversed(MCStringRef self, MCStringRef& r_new_string)
+{
+    __MCAssertIsString(self);
+
+    if (MCStringGetLength(self) < 2)
+        return MCStringCopy(self, r_new_string);
+
+    /* Make a deep copy of the input string. */
+    /* TODO[2017-03-29] This could be optimised by _not_ copying the
+     * actual string buffer contents during the deep copy, but
+     * reversing directly from the input string's internal buffer to
+     * the result string's buffer. */
+    MCAutoStringRef t_result;
+    if (!MCStringMutableCopy(self, &t_result))
+        return false;
+    if (__MCStringIsIndirect(*t_result))
+        if (!__MCStringResolveIndirect(*t_result))
+            return false;
+
+    if (__MCStringIsNative(*t_result))
+    {
+        /* Native strings have one char_t per grapheme, so they can be
+         * reversed in-place. */
+        MCInplaceReverse(t_result->native_chars, t_result->char_count);
+    }
+    else if (__MCStringIsTrivial(*t_result))
+    {
+        /* Trivial strings have one unichar_t per grapheme, so they
+         * can be reversed in-place. */
+        MCInplaceReverse(t_result->chars, t_result->char_count);
+    }
+    else
+    {
+        /* These strings have some potentially-unbounded number of
+         * unichar_t codeunits items per grapheme.  In this case, we
+         * reverse by iterating over the contents of the original
+         * string, copying the graphemes into the new string. */
+        MCStringRef t_original = __MCStringIsIndirect(self) ? self->string : self;
+
+        /* Start of the next grapheme to copy, in the input string */
+        uindex_t t_from = 0;
+        uindex_t t_length = t_original->char_count;
+
+        while (t_from < t_length)
+        {
+            /* Find the end of the current grapheme */
+            uindex_t t_grapheme_end =
+                MCStringGraphemeBreakIteratorAdvance(t_original, t_from);
+
+            if (t_grapheme_end == kMCLocaleBreakIteratorDone)
+                t_grapheme_end = t_length;
+
+            MCAssert(t_grapheme_end <= t_length);
+
+            MCMemoryCopy(t_result->chars + t_length - t_grapheme_end,
+                         t_original->chars + t_from,
+                         (t_grapheme_end - t_from) * sizeof(*t_result->chars));
+
+            t_from = t_grapheme_end;
+        }
+    }
+
+    r_new_string = t_result.Take();
+    return true;
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
 MC_DLLEXPORT_DEF
 bool MCStringIsMutable(const MCStringRef self)
 {
