Merge "Compute bounding box and use it during line break" into main

13 files changed, 307 insertions, 182 deletions

diff --git a/libs/minikin/Android.bp b/libs/minikin/Android.bp
index f5af693..c406015 100644
--- a/libs/minikin/Android.bp
+++ b/libs/minikin/Android.bp
@@ -28,7 +28,6 @@ cc_library {
     host_supported: true,
     srcs: [
         "BidiUtils.cpp",
-        "BoundsCache.cpp",
         "CmapCoverage.cpp",
         "Emoji.cpp",
         "Font.cpp",
diff --git a/libs/minikin/BoundsCache.cpp b/libs/minikin/BoundsCache.cpp
deleted file mode 100644
index 95b453b..0000000
--- a/libs/minikin/BoundsCache.cpp
+++ /dev/null
@@ -1,43 +0,0 @@
-/*
- * Copyright (C) 2020 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#include "minikin/BoundsCache.h"
-
-namespace minikin {
-
-void ValueExtractor::operator()(const LayoutPiece& layoutPiece, const MinikinPaint& paint) {
-    value.reset(new BoundsValue);
-    value->rect = BoundsCache::getBounds(layoutPiece, paint);
-    value->advance = layoutPiece.advance();
-}
-
-// static
-MinikinRect BoundsCache::getBounds(const LayoutPiece& layoutPiece, const MinikinPaint& paint) {
-    MinikinRect pieceBounds;
-    MinikinRect tmpRect;
-    for (uint32_t i = 0; i < layoutPiece.glyphCount(); ++i) {
-        const FakedFont& font = layoutPiece.fontAt(i);
-        const Point& point = layoutPiece.pointAt(i);
-
-        MinikinFont* minikinFont = font.typeface().get();
-        minikinFont->GetBounds(&tmpRect, layoutPiece.glyphIdAt(i), paint, font.fakery);
-        tmpRect.offset(point.x, point.y);
-        pieceBounds.join(tmpRect);
-    }
-    return pieceBounds;
-}
-
-}  // namespace minikin
diff --git a/libs/minikin/Debug.cpp b/libs/minikin/Debug.cpp
index 6c48a39..42d6d8e 100644
--- a/libs/minikin/Debug.cpp
+++ b/libs/minikin/Debug.cpp
@@ -81,7 +81,8 @@ std::string toString(const MinikinExtent& extent) {
 
 std::string toString(const LayoutPiece& layout) {
     std::stringstream ss;
-    ss << "advance=" << layout.advance() << ", extent=" << toString(layout.extent()) << ", glyphs=";
+    ss << "{advance=" << layout.advance() << ", extent=" << toString(layout.extent())
+       << ", glyphs=";
 
     for (uint32_t i = 0; i < layout.glyphCount(); ++i) {
         ss << "{id:" << layout.glyphIdAt(i) << ", pos = " << toString(layout.pointAt(i))
diff --git a/libs/minikin/GreedyLineBreaker.cpp b/libs/minikin/GreedyLineBreaker.cpp
index bb2f91c..ecaf895 100644
--- a/libs/minikin/GreedyLineBreaker.cpp
+++ b/libs/minikin/GreedyLineBreaker.cpp
@@ -40,13 +40,14 @@ public:
     // destructed.
     GreedyLineBreaker(const U16StringPiece& textBuf, const MeasuredText& measured,
                       const LineWidth& lineWidthLimits, const TabStops& tabStops,
-                      bool enableHyphenation)
+                      bool enableHyphenation, bool useBoundsForWidth)
             : mLineWidthLimit(lineWidthLimits.getAt(0)),
               mTextBuf(textBuf),
               mMeasuredText(measured),
               mLineWidthLimits(lineWidthLimits),
               mTabStops(tabStops),
-              mEnableHyphenation(enableHyphenation) {}
+              mEnableHyphenation(enableHyphenation),
+              mUseBoundsForWidth(useBoundsForWidth) {}
 
     void process();
 
@@ -99,6 +100,8 @@ private:
     // This method return true if there is no characters to be processed.
     bool doLineBreakWithGraphemeBounds(const Range& range);
 
+    bool overhangExceedLineLimit(const Range& range);
+
     // Info about the line currently processing.
     uint32_t mLineNum = 0;
     double mLineWidth = 0;
@@ -121,6 +124,7 @@ private:
     const LineWidth& mLineWidthLimits;
     const TabStops& mTabStops;
     bool mEnableHyphenation;
+    bool mUseBoundsForWidth;
 
     // The result of line breaking.
     std::vector<BreakPoint> mBreakPoints;
@@ -263,7 +267,8 @@ bool GreedyLineBreaker::doLineBreakWithGraphemeBounds(const Range& range) {
         if (w == 0) {
             continue;  // w == 0 means here is not a grapheme bounds. Don't break here.
         }
-        if (width + w > mLineWidthLimit) {
+        if (width + w > mLineWidthLimit ||
+            overhangExceedLineLimit(Range(range.getStart(), i + 1))) {
             // Okay, here is the longest position.
             breakLineAt(i, width, mLineWidth - width, mSumOfCharWidths - width,
                         EndHyphenEdit::NO_EDIT, StartHyphenEdit::NO_EDIT);
@@ -294,18 +299,44 @@ void GreedyLineBreaker::updateLineWidth(uint16_t c, float width) {
     }
 }
 
+bool GreedyLineBreaker::overhangExceedLineLimit(const Range& range) {
+    if (!mUseBoundsForWidth) {
+        return false;
+    }
+    if (!mMeasuredText.hasOverhang(range)) {
+        return false;
+    }
+
+    uint32_t i;
+    for (i = 0; i < range.getLength(); ++i) {
+        uint16_t ch = mTextBuf[range.getEnd() - i - 1];
+        if (!isLineEndSpace(ch)) {
+            break;
+        }
+    }
+    if (i == range.getLength()) {
+        return false;
+    }
+
+    return mMeasuredText.getBounds(mTextBuf, Range(range.getStart(), range.getEnd() - i)).width() >
+           mLineWidthLimit;
+}
+
 void GreedyLineBreaker::processLineBreak(uint32_t offset, WordBreaker* breaker,
                                          bool doHyphenation) {
-    while (mLineWidth > mLineWidthLimit) {
-        const Range lineRange(getPrevLineBreakOffset(), offset);  // The range we need to address.
+    while (mLineWidth > mLineWidthLimit ||
+           overhangExceedLineLimit(Range(getPrevLineBreakOffset(), offset))) {
         if (tryLineBreakWithWordBreak()) {
             continue;  // The word in the new line may still be too long for the line limit.
-        } else if (doHyphenation && tryLineBreakWithHyphenation(lineRange, breaker)) {
+        }
+
+        if (doHyphenation &&
+            tryLineBreakWithHyphenation(Range(getPrevLineBreakOffset(), offset), breaker)) {
             continue;  // TODO: we may be able to return here.
-        } else {
-            if (doLineBreakWithGraphemeBounds(lineRange)) {
-                return;
-            }
+        }
+
+        if (doLineBreakWithGraphemeBounds(Range(getPrevLineBreakOffset(), offset))) {
+            return;
         }
     }
 
@@ -371,12 +402,32 @@ LineBreakResult GreedyLineBreaker::getResult() const {
             hasTabChar |= mTextBuf[i] == CHAR_TAB;
         }
 
-        MinikinExtent extent =
-                mMeasuredText.getExtent(mTextBuf, Range(prevBreakOffset, breakPoint.offset));
+        if (mUseBoundsForWidth) {
+            Range range = Range(prevBreakOffset, breakPoint.offset);
+            Range actualRange = trimTrailingLineEndSpaces(mTextBuf, range);
+            if (actualRange.isEmpty()) {
+                // No characters before the line-end-spaces.
+                MinikinExtent extent = mMeasuredText.getExtent(mTextBuf, range);
+                out.ascents.push_back(extent.ascent);
+                out.descents.push_back(extent.descent);
+                out.bounds.emplace_back(0, extent.ascent, breakPoint.lineWidth, extent.descent);
+            } else {
+                LineMetrics metrics = mMeasuredText.getLineMetrics(mTextBuf, actualRange);
+                out.ascents.push_back(metrics.extent.ascent);
+                out.descents.push_back(metrics.extent.descent);
+                out.bounds.emplace_back(metrics.bounds);
+            }
+        } else {
+            MinikinExtent extent =
+                    mMeasuredText.getExtent(mTextBuf, Range(prevBreakOffset, breakPoint.offset));
+            out.ascents.push_back(extent.ascent);
+            out.descents.push_back(extent.descent);
+            // We don't have bounding box if mUseBoundsForWidth is false. Use line ascent/descent
+            // and linew width for the bounding box.
+            out.bounds.emplace_back(0, extent.ascent, breakPoint.lineWidth, extent.descent);
+        }
         out.breakPoints.push_back(breakPoint.offset);
         out.widths.push_back(breakPoint.lineWidth);
-        out.ascents.push_back(extent.ascent);
-        out.descents.push_back(extent.descent);
         out.flags.push_back((hasTabChar ? TAB_BIT : 0) | static_cast<int>(breakPoint.hyphenEdit));
 
         prevBreakOffset = breakPoint.offset;
@@ -388,11 +439,12 @@ LineBreakResult GreedyLineBreaker::getResult() const {
 
 LineBreakResult breakLineGreedy(const U16StringPiece& textBuf, const MeasuredText& measured,
                                 const LineWidth& lineWidthLimits, const TabStops& tabStops,
-                                bool enableHyphenation) {
+                                bool enableHyphenation, bool useBoundsForWidth) {
     if (textBuf.size() == 0) {
         return LineBreakResult();
     }
-    GreedyLineBreaker lineBreaker(textBuf, measured, lineWidthLimits, tabStops, enableHyphenation);
+    GreedyLineBreaker lineBreaker(textBuf, measured, lineWidthLimits, tabStops, enableHyphenation,
+                                  useBoundsForWidth);
     lineBreaker.process();
     return lineBreaker.getResult();
 }
diff --git a/libs/minikin/GreedyLineBreaker.h b/libs/minikin/GreedyLineBreaker.h
index ead93e4..9d17ec2 100644
--- a/libs/minikin/GreedyLineBreaker.h
+++ b/libs/minikin/GreedyLineBreaker.h
@@ -27,7 +27,7 @@ namespace minikin {
 
 LineBreakResult breakLineGreedy(const U16StringPiece& textBuf, const MeasuredText& measured,
                                 const LineWidth& lineWidthLimits, const TabStops& tabStops,
-                                bool enableHyphenation);
+                                bool enableHyphenation, bool useBoundsForWidth);
 
 }  // namespace minikin
 
diff --git a/libs/minikin/Layout.cpp b/libs/minikin/Layout.cpp
index e7d41c8..ad16796 100644
--- a/libs/minikin/Layout.cpp
+++ b/libs/minikin/Layout.cpp
@@ -53,19 +53,27 @@ void Layout::doLayout(const U16StringPiece& textBuf, const Range& range, Bidi bi
     mGlyphs.reserve(count);
     for (const BidiText::RunInfo& runInfo : BidiText(textBuf, range, bidiFlags)) {
         doLayoutRunCached(textBuf, runInfo.range, runInfo.isRtl, paint, range.getStart(),
-                          startHyphen, endHyphen, this, nullptr);
+                          startHyphen, endHyphen, this, nullptr, nullptr);
     }
 }
 
 float Layout::measureText(const U16StringPiece& textBuf, const Range& range, Bidi bidiFlags,
                           const MinikinPaint& paint, StartHyphenEdit startHyphen,
-                          EndHyphenEdit endHyphen, float* advances) {
+                          EndHyphenEdit endHyphen, float* advances, MinikinRect* bounds) {
     float advance = 0;
+
+    MinikinRect tmpBounds;
     for (const BidiText::RunInfo& runInfo : BidiText(textBuf, range, bidiFlags)) {
         const size_t offset = range.toRangeOffset(runInfo.range.getStart());
         float* advancesForRun = advances ? advances + offset : nullptr;
-        advance += doLayoutRunCached(textBuf, runInfo.range, runInfo.isRtl, paint, 0, startHyphen,
-                                     endHyphen, nullptr, advancesForRun);
+        tmpBounds.setEmpty();
+        float run_advance = doLayoutRunCached(textBuf, runInfo.range, runInfo.isRtl, paint, 0,
+                                              startHyphen, endHyphen, nullptr, advancesForRun,
+                                              bounds ? &tmpBounds : nullptr);
+        if (bounds) {
+            bounds->join(tmpBounds, advance, 0);
+        }
+        advance += run_advance;
     }
     return advance;
 }
@@ -73,11 +81,12 @@ float Layout::measureText(const U16StringPiece& textBuf, const Range& range, Bid
 float Layout::doLayoutRunCached(const U16StringPiece& textBuf, const Range& range, bool isRtl,
                                 const MinikinPaint& paint, size_t dstStart,
                                 StartHyphenEdit startHyphen, EndHyphenEdit endHyphen,
-                                Layout* layout, float* advances) {
+                                Layout* layout, float* advances, MinikinRect* bounds) {
     if (!range.isValid()) {
         return 0.0f;  // ICU failed to retrieve the bidi run?
     }
     float advance = 0;
+    MinikinRect tmpBounds;
     for (const auto[context, piece] : LayoutSplitter(textBuf, range, isRtl)) {
         // Hyphenation only applies to the start/end of run.
         const StartHyphenEdit pieceStartHyphen =
@@ -86,25 +95,32 @@ float Layout::doLayoutRunCached(const U16StringPiece& textBuf, const Range& rang
                 (piece.getEnd() == range.getEnd()) ? endHyphen : EndHyphenEdit::NO_EDIT;
         float* advancesForRun =
                 advances ? advances + (piece.getStart() - range.getStart()) : nullptr;
-        advance += doLayoutWord(textBuf.data() + context.getStart(),
-                                piece.getStart() - context.getStart(), piece.getLength(),
-                                context.getLength(), isRtl, paint, piece.getStart() - dstStart,
-                                pieceStartHyphen, pieceEndHyphen, layout, advancesForRun);
+        tmpBounds.setEmpty();
+        float word_advance = doLayoutWord(
+                textBuf.data() + context.getStart(), piece.getStart() - context.getStart(),
+                piece.getLength(), context.getLength(), isRtl, paint, piece.getStart() - dstStart,
+                pieceStartHyphen, pieceEndHyphen, layout, advancesForRun,
+                bounds ? &tmpBounds : nullptr);
+        if (bounds) {
+            bounds->join(tmpBounds, advance, 0);
+        }
+        advance += word_advance;
     }
     return advance;
 }
 
 class LayoutAppendFunctor {
 public:
-    LayoutAppendFunctor(Layout* layout, float* advances, float* totalAdvance, uint32_t outOffset,
-                        float wordSpacing)
+    LayoutAppendFunctor(Layout* layout, float* advances, uint32_t outOffset, float wordSpacing,
+                        MinikinRect* bounds)
             : mLayout(layout),
               mAdvances(advances),
-              mTotalAdvance(totalAdvance),
               mOutOffset(outOffset),
-              mWordSpacing(wordSpacing) {}
+              mWordSpacing(wordSpacing),
+              mBounds(bounds) {}
 
-    void operator()(const LayoutPiece& layoutPiece, const MinikinPaint& /* paint */) {
+    void operator()(const LayoutPiece& layoutPiece, const MinikinPaint& /* paint */,
+                    const MinikinRect& bounds) {
         if (mLayout) {
             mLayout->appendLayout(layoutPiece, mOutOffset, mWordSpacing);
         }
@@ -112,30 +128,37 @@ public:
             const std::vector<float>& advances = layoutPiece.advances();
             std::copy(advances.begin(), advances.end(), mAdvances);
         }
-        if (mTotalAdvance) {
-            *mTotalAdvance = layoutPiece.advance();
+        if (mBounds) {
+            mBounds->join(bounds, mTotalAdvance, 0);
         }
+        mTotalAdvance += layoutPiece.advance();
     }
 
+    float getTotalAdvance() { return mTotalAdvance; }
+
 private:
     Layout* mLayout;
     float* mAdvances;
-    float* mTotalAdvance;
+    float mTotalAdvance;
     const uint32_t mOutOffset;
     const float mWordSpacing;
+    MinikinRect* mBounds;
 };
 
 float Layout::doLayoutWord(const uint16_t* buf, size_t start, size_t count, size_t bufSize,
                            bool isRtl, const MinikinPaint& paint, size_t bufStart,
                            StartHyphenEdit startHyphen, EndHyphenEdit endHyphen, Layout* layout,
-                           float* advances) {
+                           float* advances, MinikinRect* bounds) {
     float wordSpacing = count == 1 && isWordSpace(buf[start]) ? paint.wordSpacing : 0;
     float totalAdvance = 0;
+    const bool boundsCalculation = bounds != nullptr;
 
     const U16StringPiece textBuf(buf, bufSize);
     const Range range(start, start + count);
-    LayoutAppendFunctor f(layout, advances, &totalAdvance, bufStart, wordSpacing);
-    LayoutCache::getInstance().getOrCreate(textBuf, range, paint, isRtl, startHyphen, endHyphen, f);
+    LayoutAppendFunctor f(layout, advances, bufStart, wordSpacing, bounds);
+    LayoutCache::getInstance().getOrCreate(textBuf, range, paint, isRtl, startHyphen, endHyphen,
+                                           boundsCalculation, f);
+    totalAdvance = f.getTotalAdvance();
 
     if (wordSpacing != 0) {
         totalAdvance += wordSpacing;
diff --git a/libs/minikin/LayoutCore.cpp b/libs/minikin/LayoutCore.cpp
index 6ba6491..bc907fd 100644
--- a/libs/minikin/LayoutCore.cpp
+++ b/libs/minikin/LayoutCore.cpp
@@ -332,17 +332,11 @@ LayoutPiece::LayoutPiece(const U16StringPiece& textBuf, const Range& range, bool
     const size_t bufSize = textBuf.size();
 
     mAdvances.resize(count, 0);  // Need zero filling.
-#ifdef FEATURE_HORIZONTAL_CLIPPING
-    mFlags.resize(count, 0);
-#endif  // FEATURE_HORIZONTAL_CLIPPING
 
     // Usually the number of glyphs are less than number of code units.
     mFontIndices.reserve(count);
     mGlyphIds.reserve(count);
     mPoints.reserve(count);
-#ifdef FEATURE_HORIZONTAL_CLIPPING
-    mGlyphBounds.reserve(count);
-#endif  // FEATURE_HORIZONTAL_CLIPPING
 
     HbBufferUniquePtr buffer(hb_buffer_create());
     U16StringPiece substr = textBuf.substr(range);
@@ -481,18 +475,8 @@ LayoutPiece::LayoutPiece(const U16StringPiece& textBuf, const Range& range, bool
                 mPoints.emplace_back(x + xoff, y + yoff);
                 float xAdvance = HBFixedToFloat(positions[i].x_advance);
 
-#ifdef FEATURE_HORIZONTAL_CLIPPING
-                MinikinRect bounds;
-                fakedFont.font->typeface()->GetBounds(&bounds, glyph_ix, paint, fakedFont.fakery);
-                bounds.offset(x + xoff, y + yoff);
-
-                mGlyphBounds.emplace_back(bounds.mLeft, bounds.mTop, bounds.mRight, bounds.mBottom);
-#endif  // FEATURE_HORIZONTAL_CLIPPING
                 if (clusterBaseIndex < count) {
                     mAdvances[clusterBaseIndex] += xAdvance;
-#ifdef FEATURE_HORIZONTAL_CLIPPING
-                    mFlags[clusterBaseIndex] = bounds.mLeft < x || bounds.mRight > x + xAdvance;
-#endif  // FEATURE_HORIZONTAL_CLIPPING
                 } else {
                     ALOGE("cluster %zu (start %zu) out of bounds of count %zu", clusterBaseIndex,
                           start, count);
@@ -508,12 +492,24 @@ LayoutPiece::LayoutPiece(const U16StringPiece& textBuf, const Range& range, bool
     mFontIndices.shrink_to_fit();
     mGlyphIds.shrink_to_fit();
     mPoints.shrink_to_fit();
-#ifdef FEATURE_HORIZONTAL_CLIPPING
-    mGlyphBounds.shrink_to_fit();
-#endif  // FEATURE_HORIZONTAL_CLIPPING
     mAdvance = x;
 }
 
+// static
+MinikinRect LayoutPiece::calculateBounds(const LayoutPiece& layout, const MinikinPaint& paint) {
+    MinikinRect out;
+    for (uint32_t i = 0; i < layout.glyphCount(); ++i) {
+        MinikinRect bounds;
+        uint32_t glyphId = layout.glyphIdAt(i);
+        const FakedFont& fakedFont = layout.fontAt(i);
+        const Point& pos = layout.pointAt(i);
+
+        fakedFont.typeface()->GetBounds(&bounds, glyphId, paint, fakedFont.fakery);
+        out.join(bounds, pos);
+    }
+    return out;
+}
+
 LayoutPiece::~LayoutPiece() {}
 
 }  // namespace minikin
diff --git a/libs/minikin/LineBreaker.cpp b/libs/minikin/LineBreaker.cpp
index 12cf9bd..20a075c 100644
--- a/libs/minikin/LineBreaker.cpp
+++ b/libs/minikin/LineBreaker.cpp
@@ -24,13 +24,13 @@ namespace minikin {
 LineBreakResult breakIntoLines(const U16StringPiece& textBuffer, BreakStrategy strategy,
                                HyphenationFrequency frequency, bool justified,
                                const MeasuredText& measuredText, const LineWidth& lineWidth,
-                               const TabStops& tabStops) {
+                               const TabStops& tabStops, bool useBoundsForWidth) {
     if (strategy == BreakStrategy::Greedy || textBuffer.hasChar(CHAR_TAB)) {
         return breakLineGreedy(textBuffer, measuredText, lineWidth, tabStops,
-                               frequency != HyphenationFrequency::None);
+                               frequency != HyphenationFrequency::None, useBoundsForWidth);
     } else {
-        return breakLineOptimal(textBuffer, measuredText, lineWidth, strategy, frequency,
-                                justified);
+        return breakLineOptimal(textBuffer, measuredText, lineWidth, strategy, frequency, justified,
+                                useBoundsForWidth);
     }
 }
 
diff --git a/libs/minikin/LineBreakerUtil.h b/libs/minikin/LineBreakerUtil.h
index 5764c5e..6e572f1 100644
--- a/libs/minikin/LineBreakerUtil.h
+++ b/libs/minikin/LineBreakerUtil.h
@@ -55,6 +55,15 @@ inline bool isLineEndSpace(uint16_t c) {
            || c == 0x3000;
 }
 
+inline Range trimTrailingLineEndSpaces(const U16StringPiece& textBuf, const Range& range) {
+    for (uint32_t i = 0; i < range.getLength(); i++) {
+        if (!isLineEndSpace(textBuf[range.getEnd() - i - 1])) {
+            return Range(range.getStart(), range.getEnd() - i);
+        }
+    }
+    return Range(range.getStart(), range.getStart());
+}
+
 inline Locale getEffectiveLocale(uint32_t localeListId) {
     const LocaleList& localeList = LocaleListCache::getById(localeListId);
     return localeList.empty() ? Locale() : localeList[0];
diff --git a/libs/minikin/MeasuredText.cpp b/libs/minikin/MeasuredText.cpp
index ad9e622..3ae19a0 100644
--- a/libs/minikin/MeasuredText.cpp
+++ b/libs/minikin/MeasuredText.cpp
@@ -17,32 +17,40 @@
 #define LOG_TAG "Minikin"
 #include "minikin/MeasuredText.h"
 
-#include "minikin/Layout.h"
-
 #include "BidiUtils.h"
 #include "LayoutSplitter.h"
 #include "LayoutUtils.h"
 #include "LineBreakerUtil.h"
+#include "minikin/Characters.h"
+#include "minikin/Layout.h"
 
 namespace minikin {
 
 // Helper class for composing character advances.
 class AdvancesCompositor {
 public:
-    AdvancesCompositor(std::vector<float>* outAdvances, LayoutPieces* outPieces)
-            : mOutAdvances(outAdvances), mOutPieces(outPieces) {}
+    AdvancesCompositor(std::vector<float>* outAdvances, std::vector<uint8_t>* flags,
+                       LayoutPieces* outPieces)
+            : mOutAdvances(outAdvances), mFlags(flags), mOutPieces(outPieces) {}
 
     void setNextRange(const Range& range, bool dir) {
         mRange = range;
         mDir = dir;
     }
 
-    void operator()(const LayoutPiece& layoutPiece, const MinikinPaint& paint) {
+    void operator()(const LayoutPiece& layoutPiece, const MinikinPaint& paint,
+                    const MinikinRect& bounds) {
         const std::vector<float>& advances = layoutPiece.advances();
         std::copy(advances.begin(), advances.end(), mOutAdvances->begin() + mRange.getStart());
 
+        if (bounds.mLeft < 0 || bounds.mRight > layoutPiece.advance()) {
+            for (uint32_t i : mRange) {
+                (*mFlags)[i] |= MeasuredText::MAY_OVERHANG_BIT;
+            }
+        }
+
         if (mOutPieces != nullptr) {
-            mOutPieces->insert(mRange, 0 /* no edit */, layoutPiece, mDir, paint);
+            mOutPieces->insert(mRange, 0 /* no edit */, layoutPiece, mDir, paint, bounds);
         }
     }
 
@@ -50,12 +58,14 @@ private:
     Range mRange;
     bool mDir;
     std::vector<float>* mOutAdvances;
+    std::vector<uint8_t>* mFlags;
     LayoutPieces* mOutPieces;
 };
 
 void StyleRun::getMetrics(const U16StringPiece& textBuf, std::vector<float>* advances,
-                          LayoutPieces* precomputed, LayoutPieces* outPieces) const {
-    AdvancesCompositor compositor(advances, outPieces);
+                          std::vector<uint8_t>* flags, LayoutPieces* precomputed,
+                          bool boundsCalculation, LayoutPieces* outPieces) const {
+    AdvancesCompositor compositor(advances, flags, outPieces);
     const Bidi bidiFlag = mIsRtl ? Bidi::FORCE_RTL : Bidi::FORCE_LTR;
     const uint32_t paintId =
             (precomputed == nullptr) ? LayoutPieces::kNoPaintId : precomputed->findPaintId(mPaint);
@@ -65,11 +75,12 @@ void StyleRun::getMetrics(const U16StringPiece& textBuf, std::vector<float>* adv
             if (paintId == LayoutPieces::kNoPaintId) {
                 LayoutCache::getInstance().getOrCreate(
                         textBuf.substr(context), piece - context.getStart(), mPaint, info.isRtl,
-                        StartHyphenEdit::NO_EDIT, EndHyphenEdit::NO_EDIT, compositor);
+                        StartHyphenEdit::NO_EDIT, EndHyphenEdit::NO_EDIT, boundsCalculation,
+                        compositor);
             } else {
                 precomputed->getOrCreate(textBuf, piece, context, mPaint, info.isRtl,
                                          StartHyphenEdit::NO_EDIT, EndHyphenEdit::NO_EDIT, paintId,
-                                         compositor);
+                                         boundsCalculation, compositor);
             }
         }
     }
@@ -80,7 +91,7 @@ class TotalAdvancesCompositor {
 public:
     TotalAdvancesCompositor() : mOut(0) {}
 
-    void operator()(const LayoutPiece& layoutPiece, const MinikinPaint&) {
+    void operator()(const LayoutPiece& layoutPiece, const MinikinPaint&, const MinikinRect&) {
         for (float w : layoutPiece.advances()) {
             mOut += w;
         }
@@ -100,7 +111,7 @@ float StyleRun::measureText(const U16StringPiece& textBuf) const {
         for (const auto [context, piece] : LayoutSplitter(textBuf, info.range, info.isRtl)) {
             layoutCache.getOrCreate(textBuf.substr(context), piece - context.getStart(), mPaint,
                                     info.isRtl, StartHyphenEdit::NO_EDIT, EndHyphenEdit::NO_EDIT,
-                                    compositor);
+                                    false /* bounds calculation */, compositor);
         }
     }
     return compositor.getTotalAdvance();
@@ -117,10 +128,11 @@ public:
         mDir = dir;
     }
 
-    void operator()(const LayoutPiece& layoutPiece, const MinikinPaint& paint) {
+    void operator()(const LayoutPiece& layoutPiece, const MinikinPaint& paint,
+                    const MinikinRect& bounds) {
         mTotalAdvance += layoutPiece.advance();
         if (mOutPieces != nullptr) {
-            mOutPieces->insert(mRange, mEdit, layoutPiece, mDir, paint);
+            mOutPieces->insert(mRange, mEdit, layoutPiece, mDir, paint, bounds);
         }
     }
 
@@ -147,16 +159,17 @@ float StyleRun::measureHyphenPiece(const U16StringPiece& textBuf, const Range& r
                     piece.getEnd() == range.getEnd() ? endHyphen : EndHyphenEdit::NO_EDIT;
 
             compositor.setNextContext(piece, packHyphenEdit(startEdit, endEdit), info.isRtl);
-            LayoutCache::getInstance().getOrCreate(textBuf.substr(context),
-                                                   piece - context.getStart(), mPaint, info.isRtl,
-                                                   startEdit, endEdit, compositor);
+            LayoutCache::getInstance().getOrCreate(
+                    textBuf.substr(context), piece - context.getStart(), mPaint, info.isRtl,
+                    startEdit, endEdit, false /* bounds calculation */, compositor);
         }
     }
     return compositor.advance();
 }
 
 void MeasuredText::measure(const U16StringPiece& textBuf, bool computeHyphenation,
-                           bool computeLayout, bool ignoreHyphenKerning, MeasuredText* hint) {
+                           bool computeLayout, bool computeBounds, bool ignoreHyphenKerning,
+                           MeasuredText* hint) {
     if (textBuf.size() == 0) {
         return;
     }
@@ -165,7 +178,8 @@ void MeasuredText::measure(const U16StringPiece& textBuf, bool computeHyphenatio
     CharProcessor proc(textBuf);
     for (const auto& run : runs) {
         const Range& range = run->getRange();
-        run->getMetrics(textBuf, &widths, hint ? &hint->layoutPieces : nullptr, piecesOut);
+        run->getMetrics(textBuf, &widths, &flags, hint ? &hint->layoutPieces : nullptr,
+                        computeBounds, piecesOut);
 
         if (!computeHyphenation || !run->canBreak()) {
             continue;
@@ -198,7 +212,8 @@ public:
 
     void setOutOffset(uint32_t outOffset) { mOutOffset = outOffset; }
 
-    void operator()(const LayoutPiece& layoutPiece, const MinikinPaint& /* paint */) {
+    void operator()(const LayoutPiece& layoutPiece, const MinikinPaint& /* paint */,
+                    const MinikinRect&) {
         mOutLayout->appendLayout(layoutPiece, mOutOffset, mExtraAdvance);
     }
 
@@ -212,6 +227,7 @@ void StyleRun::appendLayout(const U16StringPiece& textBuf, const Range& range,
                             const MinikinPaint& paint, uint32_t outOrigin,
                             StartHyphenEdit startHyphen, EndHyphenEdit endHyphen,
                             Layout* outLayout) const {
+    bool boundsCalculation = false;
     float wordSpacing = range.getLength() == 1 && isWordSpace(textBuf[range.getStart()])
                                 ? mPaint.wordSpacing
                                 : 0;
@@ -230,11 +246,11 @@ void StyleRun::appendLayout(const U16StringPiece& textBuf, const Range& range,
 
             if (canUsePrecomputedResult) {
                 pieces.getOrCreate(textBuf, piece, context, mPaint, info.isRtl, startEdit, endEdit,
-                                   paintId, compositor);
+                                   paintId, boundsCalculation, compositor);
             } else {
-                LayoutCache::getInstance().getOrCreate(textBuf.substr(context),
-                                                       piece - context.getStart(), paint,
-                                                       info.isRtl, startEdit, endEdit, compositor);
+                LayoutCache::getInstance().getOrCreate(
+                        textBuf.substr(context), piece - context.getStart(), paint, info.isRtl,
+                        startEdit, endEdit, boundsCalculation, compositor);
             }
         }
     }
@@ -245,20 +261,9 @@ class BoundsCompositor {
 public:
     BoundsCompositor() : mAdvance(0) {}
 
-    void operator()(const LayoutPiece& layoutPiece, const MinikinPaint& paint) {
-        MinikinRect pieceBounds;
-        MinikinRect tmpRect;
-        for (uint32_t i = 0; i < layoutPiece.glyphCount(); ++i) {
-            const FakedFont& font = layoutPiece.fontAt(i);
-            const Point& point = layoutPiece.pointAt(i);
-
-            MinikinFont* minikinFont = font.typeface().get();
-            minikinFont->GetBounds(&tmpRect, layoutPiece.glyphIdAt(i), paint, font.fakery);
-            tmpRect.offset(point.x, point.y);
-            pieceBounds.join(tmpRect);
-        }
-        pieceBounds.offset(mAdvance, 0);
-        mBounds.join(pieceBounds);
+    void operator()(const LayoutPiece& layoutPiece, const MinikinPaint& /* paint */,
+                    const MinikinRect& bounds) {
+        mBounds.join(bounds, mAdvance, 0);
         mAdvance += layoutPiece.advance();
     }
 
@@ -279,7 +284,7 @@ std::pair<float, MinikinRect> StyleRun::getBounds(const U16StringPiece& textBuf,
         for (const auto[context, piece] : LayoutSplitter(textBuf, info.range, info.isRtl)) {
             pieces.getOrCreate(textBuf, piece, context, mPaint, info.isRtl,
                                StartHyphenEdit::NO_EDIT, EndHyphenEdit::NO_EDIT, paintId,
-                               compositor);
+                               true /* bounds calculation */, compositor);
         }
     }
     return std::make_pair(compositor.advance(), compositor.bounds());
@@ -290,7 +295,8 @@ class ExtentCompositor {
 public:
     ExtentCompositor() {}
 
-    void operator()(const LayoutPiece& layoutPiece, const MinikinPaint& /* paint */) {
+    void operator()(const LayoutPiece& layoutPiece, const MinikinPaint& /* paint */,
+                    const MinikinRect&) {
         mExtent.extendBy(layoutPiece.extent());
     }
 
@@ -309,12 +315,42 @@ MinikinExtent StyleRun::getExtent(const U16StringPiece& textBuf, const Range& ra
         for (const auto[context, piece] : LayoutSplitter(textBuf, info.range, info.isRtl)) {
             pieces.getOrCreate(textBuf, piece, context, mPaint, info.isRtl,
                                StartHyphenEdit::NO_EDIT, EndHyphenEdit::NO_EDIT, paintId,
-                               compositor);
+                               false /* bounds calculation */, compositor);
         }
     }
     return compositor.extent();
 }
 
+class LineMetricsCompositor {
+public:
+    LineMetricsCompositor() {}
+
+    void operator()(const LayoutPiece& layoutPiece, const MinikinPaint& /* paint */,
+                    const MinikinRect& bounds) {
+        mMetrics.append(layoutPiece.extent(), bounds, layoutPiece.advance());
+    }
+
+    const LineMetrics& metrics() const { return mMetrics; }
+
+private:
+    LineMetrics mMetrics;
+};
+
+LineMetrics StyleRun::getLineMetrics(const U16StringPiece& textBuf, const Range& range,
+                                     const LayoutPieces& pieces) const {
+    LineMetricsCompositor compositor;
+    Bidi bidiFlag = mIsRtl ? Bidi::FORCE_RTL : Bidi::FORCE_LTR;
+    const uint32_t paintId = pieces.findPaintId(mPaint);
+    for (const BidiText::RunInfo info : BidiText(textBuf, range, bidiFlag)) {
+        for (const auto [context, piece] : LayoutSplitter(textBuf, info.range, info.isRtl)) {
+            pieces.getOrCreate(textBuf, piece, context, mPaint, info.isRtl,
+                               StartHyphenEdit::NO_EDIT, EndHyphenEdit::NO_EDIT, paintId,
+                               true /* bounds calculation */, compositor);
+        }
+    }
+    return compositor.metrics();
+}
+
 Layout MeasuredText::buildLayout(const U16StringPiece& textBuf, const Range& range,
                                  const Range& contextRange, const MinikinPaint& paint,
                                  StartHyphenEdit startHyphen, EndHyphenEdit endHyphen) {
@@ -346,8 +382,7 @@ MinikinRect MeasuredText::getBounds(const U16StringPiece& textBuf, const Range&
         }
         auto[advance, bounds] =
                 run->getBounds(textBuf, Range::intersection(runRange, range), layoutPieces);
-        bounds.offset(totalAdvance, 0);
-        rect.join(bounds);
+        rect.join(bounds, totalAdvance, 0);
         totalAdvance += advance;
     }
     return rect;
@@ -360,11 +395,23 @@ MinikinExtent MeasuredText::getExtent(const U16StringPiece& textBuf, const Range
         if (!Range::intersects(range, runRange)) {
             continue;
         }
-        MinikinExtent runExtent =
-                run->getExtent(textBuf, Range::intersection(runRange, range), layoutPieces);
-        extent.extendBy(runExtent);
+        extent.extendBy(
+                run->getExtent(textBuf, Range::intersection(runRange, range), layoutPieces));
     }
     return extent;
 }
 
+LineMetrics MeasuredText::getLineMetrics(const U16StringPiece& textBuf, const Range& range) const {
+    LineMetrics metrics;
+    for (const auto& run : runs) {
+        const Range& runRange = run->getRange();
+        if (!Range::intersects(range, runRange)) {
+            continue;
+        }
+        metrics.append(
+                run->getLineMetrics(textBuf, Range::intersection(runRange, range), layoutPieces));
+    }
+    return metrics;
+}
+
 }  // namespace minikin
diff --git a/libs/minikin/Measurement.cpp b/libs/minikin/Measurement.cpp
index 968ab6f..7797faa 100644
--- a/libs/minikin/Measurement.cpp
+++ b/libs/minikin/Measurement.cpp
@@ -21,8 +21,8 @@
 
 #include "BidiUtils.h"
 #include "LayoutSplitter.h"
-#include "minikin/BoundsCache.h"
 #include "minikin/GraphemeBreak.h"
+#include "minikin/LayoutCache.h"
 
 namespace {
 bool isAsciiOrBidiControlCharacter(uint16_t c) {
@@ -194,11 +194,10 @@ size_t getOffsetForAdvance(const float* advances, const uint16_t* buf, size_t st
 struct BoundsComposer {
     BoundsComposer() : mAdvance(0) {}
 
-    void operator()(const MinikinRect& rect, float advance) {
-        MinikinRect tmp = rect;
-        tmp.offset(mAdvance, 0);
-        mBounds.join(tmp);
-        mAdvance += advance;
+    void operator()(const LayoutPiece& layoutPiece, const MinikinPaint& /* paint */,
+                    const MinikinRect& bounds) {
+        mBounds.join(bounds, mAdvance, 0);
+        mAdvance += layoutPiece.advance();
     }
 
     float mAdvance;
@@ -215,9 +214,9 @@ void getBounds(const U16StringPiece& str, const Range& range, Bidi bidiFlag,
                     (piece.getStart() == range.getStart()) ? startHyphen : StartHyphenEdit::NO_EDIT;
             const EndHyphenEdit pieceEndHyphen =
                     (piece.getEnd() == range.getEnd()) ? endHyphen : EndHyphenEdit::NO_EDIT;
-            BoundsCache::getInstance().getOrCreate(str.substr(context), piece - context.getStart(),
-                                                   paint, info.isRtl, pieceStartHyphen,
-                                                   pieceEndHyphen, bc);
+            LayoutCache::getInstance().getOrCreate(
+                    str.substr(context), piece - context.getStart(), paint, info.isRtl,
+                    pieceStartHyphen, pieceEndHyphen, true /* bounds calculation */, bc);
             // Increment word spacing for spacer
             if (piece.getLength() == 1 && isWordSpace(str[piece.getStart()])) {
                 bc.mAdvance += paint.wordSpacing;
@@ -230,7 +229,7 @@ void getBounds(const U16StringPiece& str, const Range& range, Bidi bidiFlag,
 struct ExtentComposer {
     ExtentComposer() {}
 
-    void operator()(const LayoutPiece& layoutPiece, const MinikinPaint&) {
+    void operator()(const LayoutPiece& layoutPiece, const MinikinPaint&, const MinikinRect&) {
         extent.extendBy(layoutPiece.extent());
     }
 
@@ -242,9 +241,10 @@ MinikinExtent getFontExtent(const U16StringPiece& textBuf, const Range& range, B
     ExtentComposer composer;
     for (const BidiText::RunInfo info : BidiText(textBuf, range, bidiFlag)) {
         for (const auto [context, piece] : LayoutSplitter(textBuf, info.range, info.isRtl)) {
-            LayoutCache::getInstance().getOrCreate(
-                    textBuf.substr(context), piece - context.getStart(), paint, info.isRtl,
-                    StartHyphenEdit::NO_EDIT, EndHyphenEdit::NO_EDIT, composer);
+            LayoutCache::getInstance().getOrCreate(textBuf.substr(context),
+                                                   piece - context.getStart(), paint, info.isRtl,
+                                                   StartHyphenEdit::NO_EDIT, EndHyphenEdit::NO_EDIT,
+                                                   false /* bounds calculation */, composer);
         }
     }
     return composer.extent;
diff --git a/libs/minikin/OptimalLineBreaker.cpp b/libs/minikin/OptimalLineBreaker.cpp
index b05a94d..adc7b66 100644
--- a/libs/minikin/OptimalLineBreaker.cpp
+++ b/libs/minikin/OptimalLineBreaker.cpp
@@ -19,11 +19,6 @@
 #include <algorithm>
 #include <limits>
 
-#include "minikin/Characters.h"
-#include "minikin/Layout.h"
-#include "minikin/Range.h"
-#include "minikin/U16StringPiece.h"
-
 #include "HyphenatorMap.h"
 #include "LayoutUtils.h"
 #include "LineBreakerUtil.h"
@@ -31,6 +26,10 @@
 #include "LocaleListCache.h"
 #include "MinikinInternal.h"
 #include "WordBreaker.h"
+#include "minikin/Characters.h"
+#include "minikin/Layout.h"
+#include "minikin/Range.h"
+#include "minikin/U16StringPiece.h"
 
 namespace minikin {
 
@@ -276,7 +275,7 @@ public:
 
     LineBreakResult computeBreaks(const OptimizeContext& context, const U16StringPiece& textBuf,
                                   const MeasuredText& measuredText, const LineWidth& lineWidth,
-                                  BreakStrategy strategy, bool justified);
+                                  BreakStrategy strategy, bool justified, bool useBoundsForWidth);
 
 private:
     // Data used to compute optimal line breaks
@@ -287,14 +286,15 @@ private:
     };
     LineBreakResult finishBreaksOptimal(const U16StringPiece& textBuf, const MeasuredText& measured,
                                         const std::vector<OptimalBreaksData>& breaksData,
-                                        const std::vector<Candidate>& candidates);
+                                        const std::vector<Candidate>& candidates,
+                                        bool useBoundsForWidth);
 };
 
 // Follow "prev" links in candidates array, and copy to result arrays.
 LineBreakResult LineBreakOptimizer::finishBreaksOptimal(
         const U16StringPiece& textBuf, const MeasuredText& measured,
-        const std::vector<OptimalBreaksData>& breaksData,
-        const std::vector<Candidate>& candidates) {
+        const std::vector<OptimalBreaksData>& breaksData, const std::vector<Candidate>& candidates,
+        bool useBoundsForWidth) {
     LineBreakResult result;
     const uint32_t nCand = candidates.size();
     uint32_t prevIndex;
@@ -305,9 +305,28 @@ LineBreakResult LineBreakOptimizer::finishBreaksOptimal(
 
         result.breakPoints.push_back(cand.offset);
         result.widths.push_back(cand.postBreak - prev.preBreak);
-        MinikinExtent extent = measured.getExtent(textBuf, Range(prev.offset, cand.offset));
-        result.ascents.push_back(extent.ascent);
-        result.descents.push_back(extent.descent);
+        if (useBoundsForWidth) {
+            Range range = Range(prev.offset, cand.offset);
+            Range actualRange = trimTrailingLineEndSpaces(textBuf, range);
+            if (actualRange.isEmpty()) {
+                MinikinExtent extent = measured.getExtent(textBuf, range);
+                result.ascents.push_back(extent.ascent);
+                result.descents.push_back(extent.descent);
+                result.bounds.emplace_back(0, extent.ascent, cand.postBreak - prev.preBreak,
+                                           extent.descent);
+            } else {
+                LineMetrics metrics = measured.getLineMetrics(textBuf, actualRange);
+                result.ascents.push_back(metrics.extent.ascent);
+                result.descents.push_back(metrics.extent.descent);
+                result.bounds.emplace_back(metrics.bounds);
+            }
+        } else {
+            MinikinExtent extent = measured.getExtent(textBuf, Range(prev.offset, cand.offset));
+            result.ascents.push_back(extent.ascent);
+            result.descents.push_back(extent.descent);
+            result.bounds.emplace_back(0, extent.ascent, cand.postBreak - prev.preBreak,
+                                       extent.descent);
+        }
 
         const HyphenEdit edit =
                 packHyphenEdit(editForNextLine(prev.hyphenType), editForThisLine(cand.hyphenType));
@@ -321,7 +340,8 @@ LineBreakResult LineBreakOptimizer::computeBreaks(const OptimizeContext& context
                                                   const U16StringPiece& textBuf,
                                                   const MeasuredText& measured,
                                                   const LineWidth& lineWidth,
-                                                  BreakStrategy strategy, bool justified) {
+                                                  BreakStrategy strategy, bool justified,
+                                                  bool useBoundsForWidth) {
     const std::vector<Candidate>& candidates = context.candidates;
     uint32_t active = 0;
     const uint32_t nCand = candidates.size();
@@ -357,7 +377,25 @@ LineBreakResult LineBreakOptimizer::computeBreaks(const OptimizeContext& context
             }
             const float jScore = breaksData[j].score;
             if (jScore + bestHope >= best) continue;
-            const float delta = candidates[j].preBreak - leftEdge;
+            float delta = candidates[j].preBreak - leftEdge;
+
+            if (useBoundsForWidth) {
+                // FIXME: Support bounds based line break for hyphenated break point.
+                if (candidates[i].hyphenType == HyphenationType::DONT_BREAK &&
+                    candidates[j].hyphenType == HyphenationType::DONT_BREAK) {
+                    if (delta >= 0) {
+                        Range range = Range(candidates[j].offset, candidates[i].offset);
+                        Range actualRange = trimTrailingLineEndSpaces(textBuf, range);
+                        if (!actualRange.isEmpty() && measured.hasOverhang(range)) {
+                            float boundsDelta =
+                                    width - measured.getBounds(textBuf, actualRange).width();
+                            if (boundsDelta < 0) {
+                                delta = boundsDelta;
+                            }
+                        }
+                    }
+                }
+            }
 
             // compute width score for line
 
@@ -399,21 +437,23 @@ LineBreakResult LineBreakOptimizer::computeBreaks(const OptimizeContext& context
                               bestPrev,                                            // prev
                               breaksData[bestPrev].lineNumber + 1});               // lineNumber
     }
-    return finishBreaksOptimal(textBuf, measured, breaksData, candidates);
+    return finishBreaksOptimal(textBuf, measured, breaksData, candidates, useBoundsForWidth);
 }
 
 }  // namespace
 
 LineBreakResult breakLineOptimal(const U16StringPiece& textBuf, const MeasuredText& measured,
                                  const LineWidth& lineWidth, BreakStrategy strategy,
-                                 HyphenationFrequency frequency, bool justified) {
+                                 HyphenationFrequency frequency, bool justified,
+                                 bool useBoundsForWidth) {
     if (textBuf.size() == 0) {
         return LineBreakResult();
     }
     const OptimizeContext context =
             populateCandidates(textBuf, measured, lineWidth, frequency, justified);
     LineBreakOptimizer optimizer;
-    return optimizer.computeBreaks(context, textBuf, measured, lineWidth, strategy, justified);
+    return optimizer.computeBreaks(context, textBuf, measured, lineWidth, strategy, justified,
+                                   useBoundsForWidth);
 }
 
 }  // namespace minikin
diff --git a/libs/minikin/OptimalLineBreaker.h b/libs/minikin/OptimalLineBreaker.h
index f13e2a8..da7798d 100644
--- a/libs/minikin/OptimalLineBreaker.h
+++ b/libs/minikin/OptimalLineBreaker.h
@@ -25,7 +25,8 @@ namespace minikin {
 
 LineBreakResult breakLineOptimal(const U16StringPiece& textBuf, const MeasuredText& measured,
                                  const LineWidth& lineWidthLimits, BreakStrategy strategy,
-                                 HyphenationFrequency frequency, bool justified);
+                                 HyphenationFrequency frequency, bool justified,
+                                 bool useBoundsForWidth);
 
 }  // namespace minikin