Implement phrase->non-phrase fallback

Bug: 281970875
Test: atest StaticLayoutLineBreakingVariantsTest
Change-Id: I22fc72e2a7379512466e246daa3a5ae223ad6aec

2 files changed, 106 insertions, 12 deletions

diff --git a/libs/minikin/GreedyLineBreaker.cpp b/libs/minikin/GreedyLineBreaker.cpp
index bb2f91c..192697a 100644
--- a/libs/minikin/GreedyLineBreaker.cpp
+++ b/libs/minikin/GreedyLineBreaker.cpp
@@ -99,6 +99,7 @@ private:
     // This method return true if there is no characters to be processed.
     bool doLineBreakWithGraphemeBounds(const Range& range);
 
+    bool doLineBreakWithFallback(const Range& range);
     // Info about the line currently processing.
     uint32_t mLineNum = 0;
     double mLineWidth = 0;
@@ -282,6 +283,69 @@ bool GreedyLineBreaker::doLineBreakWithGraphemeBounds(const Range& range) {
     return true;
 }
 
+bool GreedyLineBreaker::doLineBreakWithFallback(const Range& range) {
+    Run* targetRun = nullptr;
+    for (const auto& run : mMeasuredText.runs) {
+        if (run->getRange().contains(range)) {
+            targetRun = run.get();
+        }
+    }
+
+    if (targetRun == nullptr) {
+        return false;  // The target range may lay on multiple run. Unable to fallback.
+    }
+
+    if (targetRun->lineBreakWordStyle() == LineBreakWordStyle::None) {
+        return false;  // If the line break word style is already none, nothing can be falled back.
+    }
+
+    WordBreaker wb;
+    wb.setText(mTextBuf.data(), mTextBuf.length());
+    ssize_t next = wb.followingWithLocale(getEffectiveLocale(targetRun->getLocaleListId()),
+                                          targetRun->lineBreakStyle(), LineBreakWordStyle::None,
+                                          range.getStart());
+
+    if (!range.contains(next)) {
+        return false;  // No fallback break points.
+    }
+
+    int32_t prevBreak = -1;
+    float wordWidth = 0;
+    float preBreakWidth = 0;
+    for (uint32_t i = range.getStart(); i < range.getEnd(); ++i) {
+        const float w = mMeasuredText.widths[i];
+        if (w == 0) {
+            continue;  // w == 0 means here is not a grapheme bounds. Don't break here.
+        }
+        if (i == (uint32_t)next) {
+            if (preBreakWidth + wordWidth > mLineWidthLimit) {
+                if (prevBreak == -1) {
+                    return false;  // No candidate before this point. Give up.
+                }
+                breakLineAt(prevBreak, preBreakWidth, mLineWidth - preBreakWidth,
+                            mSumOfCharWidths - preBreakWidth, EndHyphenEdit::NO_EDIT,
+                            StartHyphenEdit::NO_EDIT);
+                return true;
+            }
+            prevBreak = i;
+            next = wb.next();
+            preBreakWidth += wordWidth;
+            wordWidth = w;
+        } else {
+            wordWidth += w;
+        }
+    }
+
+    if (preBreakWidth <= mLineWidthLimit) {
+        breakLineAt(prevBreak, preBreakWidth, mLineWidth - preBreakWidth,
+                    mSumOfCharWidths - preBreakWidth, EndHyphenEdit::NO_EDIT,
+                    StartHyphenEdit::NO_EDIT);
+        return true;
+    }
+
+    return false;
+}
+
 void GreedyLineBreaker::updateLineWidth(uint16_t c, float width) {
     if (c == CHAR_TAB) {
         mSumOfCharWidths = mTabStops.nextTab(mSumOfCharWidths);
@@ -302,6 +366,8 @@ void GreedyLineBreaker::processLineBreak(uint32_t offset, WordBreaker* breaker,
             continue;  // The word in the new line may still be too long for the line limit.
         } else if (doHyphenation && tryLineBreakWithHyphenation(lineRange, breaker)) {
             continue;  // TODO: we may be able to return here.
+        } else if (doLineBreakWithFallback(lineRange)) {
+            continue;
         } else {
             if (doLineBreakWithGraphemeBounds(lineRange)) {
                 return;
diff --git a/libs/minikin/OptimalLineBreaker.cpp b/libs/minikin/OptimalLineBreaker.cpp
index b05a94d..13590c6 100644
--- a/libs/minikin/OptimalLineBreaker.cpp
+++ b/libs/minikin/OptimalLineBreaker.cpp
@@ -41,6 +41,7 @@ namespace {
 constexpr float SCORE_INFTY = std::numeric_limits<float>::max();
 constexpr float SCORE_OVERFULL = 1e12f;
 constexpr float SCORE_DESPERATE = 1e10f;
+constexpr float SCORE_FALLBACK = 1e6f;
 
 // Multiplier for hyphen penalty on last line.
 constexpr float LAST_LINE_PENALTY_MULTIPLIER = 4.0f;
@@ -97,11 +98,10 @@ struct OptimizeContext {
     float spaceWidth = 0.0f;
 
     // Append desperate break point to the candidates.
-    inline void pushDesperate(uint32_t offset, ParaWidth sumOfCharWidths, uint32_t spaceCount,
-                              bool isRtl) {
-        candidates.emplace_back(offset, sumOfCharWidths, sumOfCharWidths, SCORE_DESPERATE,
-                                spaceCount, spaceCount,
-                                HyphenationType::BREAK_AND_DONT_INSERT_HYPHEN, isRtl);
+    inline void pushDesperate(uint32_t offset, ParaWidth sumOfCharWidths, float score,
+                              uint32_t spaceCount, bool isRtl) {
+        candidates.emplace_back(offset, sumOfCharWidths, sumOfCharWidths, score, spaceCount,
+                                spaceCount, HyphenationType::BREAK_AND_DONT_INSERT_HYPHEN, isRtl);
     }
 
     // Append hyphenation break point to the candidates.
@@ -156,23 +156,51 @@ struct DesperateBreak {
     // The sum of the character width from the beginning of the word.
     ParaWidth sumOfChars;
 
-    DesperateBreak(uint32_t offset, ParaWidth sumOfChars)
-            : offset(offset), sumOfChars(sumOfChars){};
+    float score;
+
+    DesperateBreak(uint32_t offset, ParaWidth sumOfChars, float score)
+            : offset(offset), sumOfChars(sumOfChars), score(score){};
 };
 
 // Retrieves desperate break points from a word.
-std::vector<DesperateBreak> populateDesperatePoints(const MeasuredText& measured,
-                                                    const Range& range) {
+std::vector<DesperateBreak> populateDesperatePoints(const U16StringPiece& textBuf,
+                                                    const MeasuredText& measured,
+                                                    const Range& range, const Run& run) {
     std::vector<DesperateBreak> out;
+
+    bool calculateFallback = true;
+    if (run.lineBreakWordStyle() == LineBreakWordStyle::None) {
+        calculateFallback = false;
+    }
+
+    WordBreaker wb;
+    wb.setText(textBuf.data(), textBuf.length());
+    ssize_t next =
+            wb.followingWithLocale(getEffectiveLocale(run.getLocaleListId()), run.lineBreakStyle(),
+                                   LineBreakWordStyle::None, range.getStart());
+
+    if (!range.contains(next)) {
+        calculateFallback = false;
+    }
+
     ParaWidth width = measured.widths[range.getStart()];
     for (uint32_t i = range.getStart() + 1; i < range.getEnd(); ++i) {
         const float w = measured.widths[i];
         if (w == 0) {
             continue;  // w == 0 means here is not a grapheme bounds. Don't break here.
         }
-        out.emplace_back(i, width);
+        if (calculateFallback && i == (uint32_t)next) {
+            out.emplace_back(i, width, SCORE_FALLBACK);
+            next = wb.next();
+            if (!range.contains(next)) {
+                break;
+            }
+        } else {
+            out.emplace_back(i, width, SCORE_DESPERATE);
+        }
         width += w;
     }
+
     return out;
 }
 
@@ -192,7 +220,7 @@ void appendWithMerging(std::vector<HyphenBreak>::const_iterator hyIter,
         // breaks first.
         if (d != desperates.end() && (hyIter == endHyIter || d->offset <= hyIter->offset)) {
             out->pushDesperate(d->offset, proc.sumOfCharWidthsAtPrevWordBreak + d->sumOfChars,
-                               proc.effectiveSpaceCount, isRtl);
+                               d->score, proc.effectiveSpaceCount, isRtl);
             d++;
         } else {
             out->pushHyphenation(hyIter->offset, proc.sumOfCharWidths - hyIter->second,
@@ -252,7 +280,7 @@ OptimizeContext populateCandidates(const U16StringPiece& textBuf, const Measured
                 hyIter++;
             }
             if (proc.widthFromLastWordBreak() > minLineWidth) {
-                desperateBreaks = populateDesperatePoints(measured, contextRange);
+                desperateBreaks = populateDesperatePoints(textBuf, measured, contextRange, *run);
             }
             appendWithMerging(beginHyIter, doHyphenation ? hyIter : beginHyIter, desperateBreaks,
                               proc, hyphenPenalty, isRtl, &result);