[core] Bidi support for styled text.

Remove use of QString from non-ICU Qt stub bidi implementation since we weren't making use of it.

3 files changed, 127 insertions, 22 deletions

diff --git a/platform/default/bidi.cpp b/platform/default/bidi.cpp
index d475c387b3..f972e43cc1 100644
--- a/platform/default/bidi.cpp
+++ b/platform/default/bidi.cpp
@@ -100,6 +100,108 @@ std::vector<std::u16string> BiDi::processText(const std::u16string& input,
 
     return applyLineBreaking(lineBreakPoints);
 }
+    
+std::vector<StyledText> BiDi::processStyledText(const StyledText& input, std::set<std::size_t> lineBreakPoints) {
+    std::vector<StyledText> lines;
+    const auto& inputText = input.first;
+    const auto& styleIndices = input.second;
+    
+    UErrorCode errorCode = U_ZERO_ERROR;
+    
+    ubidi_setPara(impl->bidiText, mbgl::utf16char_cast<const UChar*>(inputText.c_str()), static_cast<int32_t>(inputText.size()),
+                  UBIDI_DEFAULT_LTR, nullptr, &errorCode);
+    
+    if (U_FAILURE(errorCode)) {
+        throw std::runtime_error(std::string("BiDi::processStyledText: ") + u_errorName(errorCode));
+    }
+    
+    mergeParagraphLineBreaks(lineBreakPoints);
+    
+    std::size_t lineStartIndex = 0;
+    
+    for (std::size_t lineBreakPoint : lineBreakPoints) {
+        StyledText line;
+        line.second.reserve(lineBreakPoint - lineStartIndex);
+
+        errorCode = U_ZERO_ERROR;
+        ubidi_setLine(impl->bidiText, static_cast<int32_t>(lineStartIndex), static_cast<int32_t>(lineBreakPoint), impl->bidiLine, &errorCode);
+        if (U_FAILURE(errorCode)) {
+            throw std::runtime_error(std::string("BiDi::processStyledText (setLine): ") + u_errorName(errorCode));
+        }
+        
+        errorCode = U_ZERO_ERROR;
+        uint32_t runCount = ubidi_countRuns(impl->bidiLine, &errorCode);
+        if (U_FAILURE(errorCode)) {
+            throw std::runtime_error(std::string("BiDi::processStyledText (countRuns): ") + u_errorName(errorCode));
+        }
+        
+        for (uint32_t runIndex = 0; runIndex < runCount; runIndex++) {
+            int32_t runLogicalStart;
+            int32_t runLength;
+            UBiDiDirection direction = ubidi_getVisualRun(impl->bidiLine, runIndex, &runLogicalStart, &runLength);
+            const bool isReversed = direction == UBIDI_RTL;
+            
+            std::size_t logicalStart = lineStartIndex + runLogicalStart;
+            std::size_t logicalEnd = logicalStart + runLength;
+            if (isReversed) {
+                // Within this reversed section, iterate logically backwards
+                // Each time we see a change in style, render a reversed chunk
+                // of everything since the last change
+                std::size_t styleRunStart = logicalEnd;
+                uint8_t currentStyleIndex = styleIndices.at(styleRunStart - 1);
+                for (std::size_t i = logicalEnd - 1; i >= logicalStart; i--) {
+                    if (currentStyleIndex != styleIndices.at(i) || i == logicalStart) {
+                        std::size_t styleRunEnd = i == logicalStart ? i : i + 1;
+                        std::u16string reversed = writeReverse(inputText, styleRunEnd, styleRunStart);
+                        line.first += reversed;
+                        for (std::size_t j = 0; j < reversed.size(); j++) {
+                            line.second.push_back(currentStyleIndex);
+                        }
+                        currentStyleIndex = styleIndices.at(i);
+                        styleRunStart = styleRunEnd;
+                    }
+                    if (i == 0) {
+                        break;
+                    }
+                }
+                
+            } else {
+                line.first += input.first.substr(logicalStart, runLength);
+                line.second.insert(line.second.end(), styleIndices.begin() + logicalStart, styleIndices.begin() + logicalStart + runLength);
+            }
+        }
+
+        lines.push_back(line);
+        lineStartIndex = lineBreakPoint;
+    }
+
+    return lines;
+}
+    
+std::u16string BiDi::writeReverse(const std::u16string& input, std::size_t logicalStart, std::size_t logicalEnd) {
+    UErrorCode errorCode = U_ZERO_ERROR;
+    int32_t logicalLength = static_cast<int32_t>(logicalEnd - logicalStart);
+    std::u16string outputText(logicalLength + 1, 0);
+    
+    // UBIDI_DO_MIRRORING: Apply unicode mirroring of characters like parentheses
+    // UBIDI_REMOVE_BIDI_CONTROLS: Now that all the lines are set, remove control characters so that
+    // they don't show up on screen (some fonts have glyphs representing them)
+    int32_t outputLength =
+        ubidi_writeReverse(mbgl::utf16char_cast<const UChar*>(&input[logicalStart]),
+                           logicalLength,
+                           mbgl::utf16char_cast<UChar*>(&outputText[0]),
+                           logicalLength + 1, // Extra room for null terminator, although we don't really need to have ICU write it for us
+                           UBIDI_DO_MIRRORING | UBIDI_REMOVE_BIDI_CONTROLS,
+                           &errorCode);
+    
+    if (U_FAILURE(errorCode)) {
+        throw std::runtime_error(std::string("BiDi::writeReverse: ") + u_errorName(errorCode));
+    }
+    
+    outputText.resize(outputLength); // REMOVE_BIDI_CONTROLS may have shrunk the string
+
+    return outputText;
+}
 
 std::u16string BiDi::getLine(std::size_t start, std::size_t end) {
     UErrorCode errorCode = U_ZERO_ERROR;
diff --git a/platform/qt/src/bidi.cpp b/platform/qt/src/bidi.cpp
index b75d038d6b..6b680a9769 100644
--- a/platform/qt/src/bidi.cpp
+++ b/platform/qt/src/bidi.cpp
@@ -2,51 +2,50 @@
 
 #include <mbgl/text/bidi.hpp>
 
-#include <QString>
-
 namespace mbgl {
 
+// This stub implementation is stateless and doesn't implement the private
+// methods used by the ICU BiDi
 class BiDiImpl {
-public:
-    QString string;
+    // Used by the ICU implementation to hold onto internal BiDi state
 };
 
 std::u16string applyArabicShaping(const std::u16string& input) {
     return input;
 }
 
-void BiDi::mergeParagraphLineBreaks(std::set<std::size_t>& lineBreakPoints) {
-    lineBreakPoints.insert(static_cast<std::size_t>(impl->string.length()));
+BiDi::BiDi() : impl(std::make_unique<BiDiImpl>())
+{
 }
 
-std::vector<std::u16string>
-BiDi::applyLineBreaking(std::set<std::size_t> lineBreakPoints) {
-    mergeParagraphLineBreaks(lineBreakPoints);
+BiDi::~BiDi() = default;
+
+std::vector<std::u16string> BiDi::processText(const std::u16string& input, std::set<std::size_t> lineBreakPoints) {
+    lineBreakPoints.insert(input.length());
 
     std::vector<std::u16string> transformedLines;
     std::size_t start = 0;
     for (std::size_t lineBreakPoint : lineBreakPoints) {
-        transformedLines.push_back(getLine(start, lineBreakPoint));
+        transformedLines.push_back(input.substr(start, lineBreakPoint - start));
         start = lineBreakPoint;
     }
 
     return transformedLines;
 }
 
-BiDi::BiDi() : impl(std::make_unique<BiDiImpl>())
-{
-}
-
-BiDi::~BiDi() = default;
+std::vector<StyledText> BiDi::processStyledText(const StyledText& input, std::set<std::size_t> lineBreakPoints) {
+    lineBreakPoints.insert(input.first.length());
 
-std::vector<std::u16string> BiDi::processText(const std::u16string& input, std::set<std::size_t> lineBreakPoints) {
-    impl->string = QString::fromUtf16(reinterpret_cast<const ushort*>(input.data()), int(input.size()));
-    return applyLineBreaking(lineBreakPoints);
-}
+    std::vector<StyledText> transformedLines;
+    std::size_t start = 0;
+    for (std::size_t lineBreakPoint : lineBreakPoints) {
+        transformedLines.emplace_back(
+            input.first.substr(start, lineBreakPoint - start),
+            std::vector<uint8_t>(input.second.begin() + start, input.second.begin() + lineBreakPoint));
+        start = lineBreakPoint;
+    }
 
-std::u16string BiDi::getLine(std::size_t start, std::size_t end) {
-    auto utf16 = impl->string.mid(static_cast<int32_t>(start), static_cast<int32_t>(end - start));
-    return std::u16string(reinterpret_cast<const char16_t*>(utf16.utf16()), utf16.length());
+    return transformedLines;
 }
 
 } // end namespace mbgl
diff --git a/src/mbgl/text/bidi.hpp b/src/mbgl/text/bidi.hpp
index 59d306489c..d90f3e5d1b 100644
--- a/src/mbgl/text/bidi.hpp
+++ b/src/mbgl/text/bidi.hpp
@@ -14,17 +14,21 @@ class BiDiImpl;
 
 std::u16string applyArabicShaping(const std::u16string&);
 
+using StyledText = std::pair<std::u16string, std::vector<uint8_t>>;
+    
 class BiDi : private util::noncopyable {
 public:
     BiDi();
     ~BiDi();
 
     std::vector<std::u16string> processText(const std::u16string&, std::set<std::size_t>);
+    std::vector<StyledText> processStyledText(const StyledText&, std::set<std::size_t>);
 
 private:
     void mergeParagraphLineBreaks(std::set<std::size_t>&);
     std::vector<std::u16string> applyLineBreaking(std::set<std::size_t>);
     std::u16string getLine(std::size_t start, std::size_t end);
+    std::u16string writeReverse(const std::u16string&, std::size_t, std::size_t);
 
     std::unique_ptr<BiDiImpl> impl;
 };