Precompute full hyphenation layout

am: 43a52c5ee6

Change-Id: Ieca1c79bbe374f7a9be215420864c0d96d158637

10 files changed, 233 insertions, 219 deletions

diff --git a/include/minikin/Layout.h b/include/minikin/Layout.h
index 0d72317..0676c8c 100644
--- a/include/minikin/Layout.h
+++ b/include/minikin/Layout.h
@@ -22,6 +22,7 @@
 #include <vector>
 
 #include <gtest/gtest_prod.h>
+#include <utils/JenkinsHash.h>
 
 #include "minikin/FontCollection.h"
 #include "minikin/Range.h"
@@ -87,12 +88,15 @@ public:
     void doLayout(const U16StringPiece& str, const Range& range, Bidi bidiFlags,
                   const MinikinPaint& paint, StartHyphenEdit startHyphen, EndHyphenEdit endHyphen);
 
-    static void addToLayoutPieces(const U16StringPiece& textBuf, const Range& range, Bidi bidiFlag,
-                                  const MinikinPaint& paint, LayoutPieces* out);
+    void doLayoutWithPrecomputedPieces(const U16StringPiece& str, const Range& range,
+                                       Bidi bidiFlags, const MinikinPaint& paint,
+                                       StartHyphenEdit startHyphen, EndHyphenEdit endHyphen,
+                                       const LayoutPieces& pieces);
 
     static float measureText(const U16StringPiece& str, const Range& range, Bidi bidiFlags,
                              const MinikinPaint& paint, StartHyphenEdit startHyphen,
-                             EndHyphenEdit endHyphen, float* advances, MinikinExtent* extents);
+                             EndHyphenEdit endHyphen, float* advances, MinikinExtent* extents,
+                             LayoutPieces* pieces);
 
     inline const std::vector<float>& advances() const { return mAdvances; }
 
@@ -139,11 +143,7 @@ private:
     friend class LayoutCacheKey;
     friend class LayoutCache;
 
-    // TODO: Remove friend class with decoupling building logic from Layout.
-    friend class LayoutCompositer;
-
-    // TODO: Remove friend test by doing text layout in unit test.
-    FRIEND_TEST(MeasuredTextTest, buildLayoutTest);
+    FRIEND_TEST(LayoutTest, doLayoutWithPrecomputedPiecesTest);
 
     // Find a face in the mFaces vector. If not found, push back the entry to mFaces.
     uint8_t findOrPushBackFace(const FakedFont& face);
@@ -157,14 +157,15 @@ private:
     static float doLayoutRunCached(const U16StringPiece& textBuf, const Range& range, bool isRtl,
                                    const MinikinPaint& paint, size_t dstStart,
                                    StartHyphenEdit startHyphen, EndHyphenEdit endHyphen,
-                                   Layout* layout, float* advances, MinikinExtent* extents,
-                                   LayoutPieces* lpOut);
+                                   const LayoutPieces* lpIn, Layout* layout, float* advances,
+                                   MinikinExtent* extents, LayoutPieces* lpOut);
 
     // Lay out a single word
     static float 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, MinikinExtent* extents, LayoutPieces* lpOut);
+                              StartHyphenEdit startHyphen, EndHyphenEdit endHyphen,
+                              const LayoutPieces* lpIn, Layout* layout, float* advances,
+                              MinikinExtent* extents, LayoutPieces* lpOut);
 
     // Lay out a single bidi run
     void doLayoutRun(const uint16_t* buf, size_t start, size_t count, size_t bufSize, bool isRtl,
@@ -184,34 +185,70 @@ private:
 };
 
 struct LayoutPieces {
-    // TODO: Sorted vector of pairs may be faster?
-    std::unordered_map<uint32_t, Layout> offsetMap;  // start offset to layout index map.
+    struct Key {
+        Key(const U16StringPiece& textBuf, const Range& range, HyphenEdit edit)
+                : text(textBuf.data()), length(textBuf.length()), range(range), hyphenEdit(edit) {}
+
+        void makePersistent() {
+            uint16_t* copied = new uint16_t[length];
+            std::copy(text, text + length, copied);
+            text = copied;
+        }
 
-    uint32_t getMemoryUsage() const {
-        uint32_t result = 0;
-        for (const auto& i : offsetMap) {
-            result += i.second.getMemoryUsage();
+        inline bool operator==(const Key& o) const {
+            return length == o.length && hyphenEdit == o.hyphenEdit && range == o.range &&
+                   (text == o.text || memcmp(text, o.text, sizeof(uint16_t) * length) == 0);
         }
-        return result;
-    }
-};
 
-class LayoutCompositer {
-public:
-    LayoutCompositer(uint32_t size) {
-        mLayout.reset();
-        mLayout.mAdvances.resize(size, 0);
-        mLayout.mExtents.resize(size);
+        const uint16_t* text;
+        const uint32_t length;
+        Range range;
+        HyphenEdit hyphenEdit;
+    };
+
+    struct KeyHasher {
+        std::size_t operator()(const Key& key) const {
+            uint32_t hash = android::JenkinsHashMix(0, static_cast<uint8_t>(key.hyphenEdit));
+            hash = android::JenkinsHashMix(hash, key.range.getStart());
+            hash = android::JenkinsHashMix(hash, key.range.getEnd());
+            hash = android::JenkinsHashMixShorts(hash, key.text, key.length);
+            return android::JenkinsHashWhiten(hash);
+        }
+    };
+
+    LayoutPieces() {}
+
+    ~LayoutPieces() {
+        for (const auto it : offsetMap) {
+            delete[] it.first.text;
+        }
     }
 
-    void append(const Layout& layout, uint32_t start, float extraAdvance) {
-        mLayout.appendLayout(layout, start, extraAdvance);
+    std::unordered_map<Key, Layout, KeyHasher> offsetMap;
+
+    void insert(const U16StringPiece& textBuf, const Range& range, HyphenEdit edit,
+                const Layout& layout) {
+        Key key(textBuf, range, edit);
+        key.makePersistent();
+        offsetMap.insert(std::make_pair(key, layout));
     }
 
-    Layout build() { return std::move(mLayout); }
+    const Layout* get(const U16StringPiece& textBuf, const Range& range, HyphenEdit edit) const {
+        auto it = offsetMap.find(Key(textBuf, range, edit));
+        if (it == offsetMap.end()) {
+            return nullptr;
+        }
+        return &it->second;
+    }
 
-private:
-    Layout mLayout;
+    uint32_t getMemoryUsage() const {
+        uint32_t result = 0;
+        for (const auto& i : offsetMap) {
+            result += sizeof(Key) + sizeof(uint16_t) * i.first.length;
+            result += i.second.getMemoryUsage();
+        }
+        return result;
+    }
 };
 
 }  // namespace minikin
diff --git a/include/minikin/MeasuredText.h b/include/minikin/MeasuredText.h
index 83b774f..474cdf3 100644
--- a/include/minikin/MeasuredText.h
+++ b/include/minikin/MeasuredText.h
@@ -44,8 +44,8 @@ public:
     virtual uint32_t getLocaleListId() const = 0;
 
     // Fills the each character's advances, extents and overhangs.
-    virtual void getMetrics(const U16StringPiece& text, float* advances,
-                            MinikinExtent* extents) const = 0;
+    virtual void getMetrics(const U16StringPiece& text, float* advances, MinikinExtent* extents,
+                            LayoutPieces* piece) const = 0;
 
     // Following two methods are only called when the implementation returns true for
     // canHyphenate method.
@@ -54,13 +54,12 @@ public:
     // Returns null if canHyphenate has not returned true.
     virtual const MinikinPaint* getPaint() const { return nullptr; }
 
-    virtual void addToLayoutPieces(const U16StringPiece&, LayoutPieces*) const {}
-
     // Measures the hyphenation piece and fills each character's advances and overhangs.
     virtual float measureHyphenPiece(const U16StringPiece& /* text */,
                                      const Range& /* hyphenPieceRange */,
                                      StartHyphenEdit /* startHyphen */,
-                                     EndHyphenEdit /* endHyphen */, float* /* advances */) const {
+                                     EndHyphenEdit /* endHyphen */, float* /* advances */,
+                                     LayoutPieces* /* pieces */) const {
         return 0.0;
     }
 
@@ -79,26 +78,21 @@ public:
     uint32_t getLocaleListId() const override { return mPaint.localeListId; }
     bool isRtl() const override { return mIsRtl; }
 
-    void getMetrics(const U16StringPiece& text, float* advances,
-                    MinikinExtent* extents) const override {
+    void getMetrics(const U16StringPiece& text, float* advances, MinikinExtent* extents,
+                    LayoutPieces* pieces) const override {
         Bidi bidiFlag = mIsRtl ? Bidi::FORCE_RTL : Bidi::FORCE_LTR;
         Layout::measureText(text, mRange, bidiFlag, mPaint, StartHyphenEdit::NO_EDIT,
-                            EndHyphenEdit::NO_EDIT, advances, extents);
+                            EndHyphenEdit::NO_EDIT, advances, extents, pieces);
     }
 
     const MinikinPaint* getPaint() const override { return &mPaint; }
 
-    virtual void addToLayoutPieces(const U16StringPiece& textBuf, LayoutPieces* out) const {
-        Bidi bidiFlag = mIsRtl ? Bidi::FORCE_RTL : Bidi::FORCE_LTR;
-        Layout::addToLayoutPieces(textBuf, mRange, bidiFlag, mPaint, out);
-    }
-
     float measureHyphenPiece(const U16StringPiece& text, const Range& range,
-                             StartHyphenEdit startHyphen, EndHyphenEdit endHyphen,
-                             float* advances) const override {
+                             StartHyphenEdit startHyphen, EndHyphenEdit endHyphen, float* advances,
+                             LayoutPieces* pieces) const override {
         Bidi bidiFlag = mIsRtl ? Bidi::FORCE_RTL : Bidi::FORCE_LTR;
         return Layout::measureText(text, range, bidiFlag, mPaint, startHyphen, endHyphen, advances,
-                                   nullptr /* extent */);
+                                   nullptr /* extent */, pieces);
     }
 
 private:
@@ -116,7 +110,7 @@ public:
     uint32_t getLocaleListId() const { return mLocaleListId; }
 
     void getMetrics(const U16StringPiece& /* unused */, float* advances,
-                    MinikinExtent* /* unused */) const override {
+                    MinikinExtent* /* unused */, LayoutPieces* /* pieces */) const override {
         advances[0] = mWidth;
         // TODO: Get the extents information from the caller.
     }
@@ -168,9 +162,9 @@ public:
                sizeof(HyphenBreak) * hyphenBreaks.size() + layoutPieces.getMemoryUsage();
     }
 
-    bool buildLayout(const U16StringPiece& textBuf, const Range& range, const MinikinPaint& paint,
-                     Bidi bidiFlag, int mtOffset, StartHyphenEdit startHyphen,
-                     EndHyphenEdit endHyphen, Layout* layout);
+    void buildLayout(const U16StringPiece& textBuf, const Range& range, const MinikinPaint& paint,
+                     Bidi bidiFlag, StartHyphenEdit startHyphen, EndHyphenEdit endHyphen,
+                     Layout* layout);
 
     MeasuredText(MeasuredText&&) = default;
     MeasuredText& operator=(MeasuredText&&) = default;
diff --git a/include/minikin/U16StringPiece.h b/include/minikin/U16StringPiece.h
index 9b28111..fe92635 100644
--- a/include/minikin/U16StringPiece.h
+++ b/include/minikin/U16StringPiece.h
@@ -54,7 +54,7 @@ public:
 
 private:
     const uint16_t* mData;
-    const uint32_t mLength;
+    uint32_t mLength;
 };
 
 }  // namespace minikin
diff --git a/libs/minikin/GreedyLineBreaker.cpp b/libs/minikin/GreedyLineBreaker.cpp
index f20e5c4..661a42e 100644
--- a/libs/minikin/GreedyLineBreaker.cpp
+++ b/libs/minikin/GreedyLineBreaker.cpp
@@ -195,7 +195,7 @@ bool GreedyLineBreaker::tryLineBreakWithHyphenation(const Range& range, WordBrea
 
         const float width = targetRun->measureHyphenPiece(mTextBuf, contextRange.split(i).first,
                                                           mStartHyphenEdit, editForThisLine(hyph),
-                                                          nullptr /* advances */);
+                                                          nullptr /* advances */, nullptr);
 
         if (width <= mLineWidthLimit) {
             // There are still space, remember current offset and look up next hyphenation point.
@@ -214,7 +214,7 @@ bool GreedyLineBreaker::tryLineBreakWithHyphenation(const Range& range, WordBrea
             const StartHyphenEdit nextLineStartHyphenEdit = editForNextLine(hyph);
             const float remainingCharWidths = targetRun->measureHyphenPiece(
                     mTextBuf, contextRange.split(prevOffset).second, nextLineStartHyphenEdit,
-                    EndHyphenEdit::NO_EDIT, nullptr /* advances */);
+                    EndHyphenEdit::NO_EDIT, nullptr /* advances */, nullptr);
             breakLineAt(prevOffset, prevWidth,
                         remainingCharWidths - (mSumOfCharWidths - mLineWidth), remainingCharWidths,
                         editForThisLine(hyph), nextLineStartHyphenEdit);
@@ -243,7 +243,7 @@ bool GreedyLineBreaker::tryLineBreakWithHyphenation(const Range& range, WordBrea
         const StartHyphenEdit nextLineStartHyphenEdit = editForNextLine(hyph);
         const float remainingCharWidths = targetRun->measureHyphenPiece(
                 mTextBuf, contextRange.split(prevOffset).second, nextLineStartHyphenEdit,
-                EndHyphenEdit::NO_EDIT, nullptr /* advances */);
+                EndHyphenEdit::NO_EDIT, nullptr /* advances */, nullptr);
 
         breakLineAt(prevOffset, prevWidth, remainingCharWidths - (mSumOfCharWidths - mLineWidth),
                     remainingCharWidths, editForThisLine(hyph), nextLineStartHyphenEdit);
diff --git a/libs/minikin/Layout.cpp b/libs/minikin/Layout.cpp
index 717ffcd..4383d60 100644
--- a/libs/minikin/Layout.cpp
+++ b/libs/minikin/Layout.cpp
@@ -234,37 +234,37 @@ void Layout::doLayout(const U16StringPiece& textBuf, const Range& range, Bidi bi
 
     for (const BidiText::RunInfo& runInfo : BidiText(textBuf, range, bidiFlags)) {
         doLayoutRunCached(textBuf, runInfo.range, runInfo.isRtl, paint, range.getStart(),
-                          startHyphen, endHyphen, this, nullptr, nullptr, nullptr);
+                          startHyphen, endHyphen, nullptr, this, nullptr, nullptr, nullptr);
     }
 }
 
-// static
-void Layout::addToLayoutPieces(const U16StringPiece& textBuf, const Range& range, Bidi bidiFlag,
-                               const MinikinPaint& paint,
-                               LayoutPieces* out) {
-    float advance = 0;
-    for (const BidiText::RunInfo& runInfo : BidiText(textBuf, range, bidiFlag)) {
-        advance += doLayoutRunCached(textBuf, runInfo.range, runInfo.isRtl, paint,
-                                     0,                         // Destination start. Not used.
-                                     StartHyphenEdit::NO_EDIT,  // Hyphen edit, not used.
-                                     EndHyphenEdit::NO_EDIT,    // Hyphen edit, not used.
-                                     nullptr,                   // output layout. Not used
-                                     nullptr,                   // advances. Not used
-                                     nullptr,                   // extents. Not used.
-                                     out);
+void Layout::doLayoutWithPrecomputedPieces(const U16StringPiece& textBuf, const Range& range,
+                                           Bidi bidiFlags, const MinikinPaint& paint,
+                                           StartHyphenEdit startHyphen, EndHyphenEdit endHyphen,
+                                           const LayoutPieces& lpIn) {
+    const uint32_t count = range.getLength();
+    reset();
+    mAdvances.resize(count, 0);
+    mExtents.resize(count);
+
+    for (const BidiText::RunInfo& runInfo : BidiText(textBuf, range, bidiFlags)) {
+        doLayoutRunCached(textBuf, runInfo.range, runInfo.isRtl, paint, range.getStart(),
+                          startHyphen, endHyphen, &lpIn, this, nullptr, nullptr, nullptr);
     }
 }
 
 float Layout::measureText(const U16StringPiece& textBuf, const Range& range, Bidi bidiFlags,
                           const MinikinPaint& paint, StartHyphenEdit startHyphen,
-                          EndHyphenEdit endHyphen, float* advances, MinikinExtent* extents) {
+                          EndHyphenEdit endHyphen, float* advances, MinikinExtent* extents,
+                          LayoutPieces* pieces) {
     float advance = 0;
     for (const BidiText::RunInfo& runInfo : BidiText(textBuf, range, bidiFlags)) {
         const size_t offset = range.toRangeOffset(runInfo.range.getStart());
         float* advancesForRun = advances ? advances + offset : nullptr;
         MinikinExtent* extentsForRun = extents ? extents + offset : nullptr;
         advance += doLayoutRunCached(textBuf, runInfo.range, runInfo.isRtl, paint, 0, startHyphen,
-                                     endHyphen, NULL, advancesForRun, extentsForRun, nullptr);
+                                     endHyphen, nullptr, nullptr, advancesForRun, extentsForRun,
+                                     pieces);
     }
     return advance;
 }
@@ -272,8 +272,8 @@ 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, MinikinExtent* extents,
-                                LayoutPieces* lpOut) {
+                                const LayoutPieces* lpIn, Layout* layout, float* advances,
+                                MinikinExtent* extents, LayoutPieces* lpOut) {
     if (!range.isValid()) {
         return 0.0f;  // ICU failed to retrieve the bidi run?
     }
@@ -295,8 +295,8 @@ float Layout::doLayoutRunCached(const U16StringPiece& textBuf, const Range& rang
                                     wordend - wordstart, isRtl, paint, iter - dstStart,
                                     // Only apply hyphen to the first or last word in the string.
                                     iter == start ? startHyphen : StartHyphenEdit::NO_EDIT,
-                                    wordend >= end ? endHyphen : EndHyphenEdit::NO_EDIT, layout,
-                                    advances ? advances + offset : nullptr,
+                                    wordend >= end ? endHyphen : EndHyphenEdit::NO_EDIT, lpIn,
+                                    layout, advances ? advances + offset : nullptr,
                                     extents ? extents + offset : nullptr, lpOut);
             wordstart = wordend;
         }
@@ -313,7 +313,7 @@ float Layout::doLayoutRunCached(const U16StringPiece& textBuf, const Range& rang
                                     // Only apply hyphen to the first (rightmost) or last (leftmost)
                                     // word in the string.
                                     wordstart <= start ? startHyphen : StartHyphenEdit::NO_EDIT,
-                                    iter == end ? endHyphen : EndHyphenEdit::NO_EDIT, layout,
+                                    iter == end ? endHyphen : EndHyphenEdit::NO_EDIT, lpIn, layout,
                                     advances ? advances + offset : nullptr,
                                     extents ? extents + offset : nullptr, lpOut);
             wordend = wordstart;
@@ -324,10 +324,14 @@ float Layout::doLayoutRunCached(const U16StringPiece& textBuf, const Range& rang
 
 class LayoutAppendFunctor {
 public:
-    LayoutAppendFunctor(Layout* layout, float* advances, MinikinExtent* extents,
+    LayoutAppendFunctor(const U16StringPiece& textBuf, const Range& range, HyphenEdit hyphenEdit,
+                        Layout* layout, float* advances, MinikinExtent* extents,
                         LayoutPieces* pieces, float* totalAdvance, uint32_t outOffset,
                         float wordSpacing)
-            : mLayout(layout),
+            : mTextBuf(textBuf),
+              mRange(range),
+              mHyphenEdit(hyphenEdit),
+              mLayout(layout),
               mAdvances(advances),
               mExtents(extents),
               mPieces(pieces),
@@ -349,11 +353,14 @@ public:
             layout.getExtents(mExtents);
         }
         if (mPieces) {
-            mPieces->offsetMap.insert(std::make_pair(mOutOffset, layout));
+            mPieces->insert(mTextBuf, mRange, mHyphenEdit, layout);
         }
     }
 
 private:
+    const U16StringPiece& mTextBuf;
+    const Range& mRange;
+    HyphenEdit mHyphenEdit;
     Layout* mLayout;
     float* mAdvances;
     MinikinExtent* mExtents;
@@ -365,16 +372,28 @@ private:
 
 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, MinikinExtent* extents, LayoutPieces* lpOut) {
+                           StartHyphenEdit startHyphen, EndHyphenEdit endHyphen,
+                           const LayoutPieces* lpIn, Layout* layout, float* advances,
+                           MinikinExtent* extents, LayoutPieces* lpOut) {
     float wordSpacing = count == 1 && isWordSpace(buf[start]) ? paint.wordSpacing : 0;
     float totalAdvance;
 
-    LayoutAppendFunctor f(layout, advances, extents, lpOut, &totalAdvance, bufStart, wordSpacing);
+    const U16StringPiece textBuf(buf, bufSize);
+    const Range range(start, start + count);
+    HyphenEdit hyphenEdit = packHyphenEdit(startHyphen, endHyphen);
+
+    LayoutAppendFunctor f(textBuf, range, hyphenEdit, layout, advances, extents, lpOut,
+                          &totalAdvance, bufStart, wordSpacing);
 
-    LayoutCache::getInstance().getOrCreate(U16StringPiece(buf, bufSize),
-                                           Range(start, start + count), paint, isRtl, startHyphen,
-                                           endHyphen, f);
+    const Layout* layoutInPieces =
+            lpIn == nullptr ? nullptr : lpIn->get(textBuf, range, hyphenEdit);
+
+    if (layoutInPieces != nullptr) {
+        f(*layoutInPieces);
+    } else {
+        LayoutCache::getInstance().getOrCreate(textBuf, range, paint, isRtl, startHyphen, endHyphen,
+                                               f);
+    }
 
     if (wordSpacing != 0) {
         totalAdvance += wordSpacing;
diff --git a/libs/minikin/LineBreakerUtil.h b/libs/minikin/LineBreakerUtil.h
index feecf50..406de7b 100644
--- a/libs/minikin/LineBreakerUtil.h
+++ b/libs/minikin/LineBreakerUtil.h
@@ -72,7 +72,8 @@ inline void populateHyphenationPoints(
         const Hyphenator& hyphenator,         // A hyphenator to be used for hyphenation.
         const Range& contextRange,            // A context range for measuring hyphenated piece.
         const Range& hyphenationTargetRange,  // An actual range for the hyphenation target.
-        std::vector<HyphenBreak>* out) {      // An output to be appended.
+        std::vector<HyphenBreak>* out,        // An output to be appended.
+        LayoutPieces* pieces) {               // An output of layout pieces. Maybe null.
     if (!run.getRange().contains(contextRange) || !contextRange.contains(hyphenationTargetRange)) {
         return;
     }
@@ -89,11 +90,11 @@ inline void populateHyphenationPoints(
         const float first = run.measureHyphenPiece(
                 textBuf /* text */, hyphenPart.first /* hyphenated piece range */,
                 StartHyphenEdit::NO_EDIT /* start hyphen edit */,
-                editForThisLine(hyph) /* end hyphen edit */, nullptr /* advances */);
+                editForThisLine(hyph) /* end hyphen edit */, nullptr /* advances */, pieces);
         const float second = run.measureHyphenPiece(
                 textBuf /* text */, hyphenPart.second /* hyphenated piece range */,
                 editForNextLine(hyph) /* start hyphen edit */,
-                EndHyphenEdit::NO_EDIT /* end hyphen edit */, nullptr /* advances */);
+                EndHyphenEdit::NO_EDIT /* end hyphen edit */, nullptr /* advances */, pieces);
 
         out->emplace_back(i, hyph, first, second);
     }
diff --git a/libs/minikin/MeasuredText.cpp b/libs/minikin/MeasuredText.cpp
index 1f22f49..7be949b 100644
--- a/libs/minikin/MeasuredText.cpp
+++ b/libs/minikin/MeasuredText.cpp
@@ -19,6 +19,7 @@
 
 #include "minikin/Layout.h"
 
+#include "LayoutUtils.h"
 #include "LineBreakerUtil.h"
 
 namespace minikin {
@@ -28,15 +29,12 @@ void MeasuredText::measure(const U16StringPiece& textBuf, bool computeHyphenatio
     if (textBuf.size() == 0) {
         return;
     }
+    LayoutPieces* piecesOut = computeLayout ? &layoutPieces : nullptr;
     CharProcessor proc(textBuf);
     for (const auto& run : runs) {
         const Range& range = run->getRange();
         const uint32_t runOffset = range.getStart();
-        run->getMetrics(textBuf, widths.data() + runOffset, extents.data() + runOffset);
-
-        if (computeLayout) {
-            run->addToLayoutPieces(textBuf, &layoutPieces);
-        }
+        run->getMetrics(textBuf, widths.data() + runOffset, extents.data() + runOffset, piecesOut);
 
         if (!computeHyphenation || !run->canHyphenate()) {
             continue;
@@ -52,42 +50,17 @@ void MeasuredText::measure(const U16StringPiece& textBuf, bool computeHyphenatio
             }
 
             populateHyphenationPoints(textBuf, *run, *proc.hyphenator, proc.contextRange(),
-                                      proc.wordRange(), &hyphenBreaks);
+                                      proc.wordRange(), &hyphenBreaks, piecesOut);
         }
     }
 }
 
-bool MeasuredText::buildLayout(const U16StringPiece& /*textBuf*/, const Range& range,
-                               const MinikinPaint& paint, Bidi /*bidiFlag*/, int mtOffset,
+void MeasuredText::buildLayout(const U16StringPiece& textBuf, const Range& range,
+                               const MinikinPaint& paint, Bidi bidiFlags,
                                StartHyphenEdit startHyphen, EndHyphenEdit endHyphen,
                                Layout* layout) {
-    if (paint.wordSpacing != 0.0f || startHyphen != StartHyphenEdit::NO_EDIT ||
-        endHyphen != EndHyphenEdit::NO_EDIT) {
-        // TODO: Use layout result as much as possible even if justified lines and hyphenated lines.
-        return false;
-    }
-
-    uint32_t start = range.getStart() + mtOffset;
-    const uint32_t end = range.getEnd() + mtOffset;
-    LayoutCompositer compositer(range.getLength());
-    while (start < end) {
-        auto ite = layoutPieces.offsetMap.find(start);
-        if (ite == layoutPieces.offsetMap.end()) {
-            // The layout result not found, possibly due to hyphenation or desperate breaks.
-            // TODO: Do layout here only for necessary piece and keep composing final layout.
-            return false;
-        }
-        if (start + ite->second.advances().size() > end) {
-            // The width of the layout piece exceeds the end of line, possibly due to hyphenation
-            // or desperate breaks.
-            // TODO: Do layout here only for necessary piece and keep composing final layout.
-            return false;
-        }
-        compositer.append(ite->second, start - mtOffset, 0);
-        start += ite->second.advances().size();
-    }
-    *layout = std::move(compositer.build());
-    return true;
+    layout->doLayoutWithPrecomputedPieces(textBuf, range, bidiFlags, paint, startHyphen, endHyphen,
+                                          layoutPieces);
 }
 
 }  // namespace minikin
diff --git a/tests/unittest/LayoutTest.cpp b/tests/unittest/LayoutTest.cpp
index a87374b..830dc92 100644
--- a/tests/unittest/LayoutTest.cpp
+++ b/tests/unittest/LayoutTest.cpp
@@ -43,6 +43,25 @@ static void resetAdvances(float* advances, size_t length) {
     }
 }
 
+static Layout doLayout(const std::string& text, const MinikinPaint& paint) {
+    Layout layout;
+    auto utf16 = utf8ToUtf16(text);
+    Range range(0, utf16.size());
+    layout.doLayout(utf16, range, Bidi::FORCE_LTR, paint, StartHyphenEdit::NO_EDIT,
+                    EndHyphenEdit::NO_EDIT);
+    return layout;
+}
+
+static Layout doLayoutWithPrecomputedPieces(const std::string& text, const MinikinPaint& paint,
+                                            const LayoutPieces& pieces) {
+    Layout layout;
+    auto utf16 = utf8ToUtf16(text);
+    Range range(0, utf16.size());
+    layout.doLayoutWithPrecomputedPieces(utf16, range, Bidi::FORCE_LTR, paint,
+                                         StartHyphenEdit::NO_EDIT, EndHyphenEdit::NO_EDIT, pieces);
+    return layout;
+}
+
 class LayoutTest : public testing::Test {
 protected:
     LayoutTest() : mCollection(nullptr) {}
@@ -498,8 +517,9 @@ TEST_F(LayoutTest, measuredTextTest) {
         std::vector<uint16_t> text = utf8ToUtf16("I");
         std::vector<float> advances(text.size());
         Range range(0, text.size());
-        EXPECT_EQ(1.0f, Layout::measureText(text, range, Bidi::LTR, paint, StartHyphenEdit::NO_EDIT,
-                                            EndHyphenEdit::NO_EDIT, advances.data(), nullptr));
+        EXPECT_EQ(1.0f,
+                  Layout::measureText(text, range, Bidi::LTR, paint, StartHyphenEdit::NO_EDIT,
+                                      EndHyphenEdit::NO_EDIT, advances.data(), nullptr, nullptr));
         ASSERT_EQ(1u, advances.size());
         EXPECT_EQ(1.0f, advances[0]);
     }
@@ -508,8 +528,9 @@ TEST_F(LayoutTest, measuredTextTest) {
         std::vector<uint16_t> text = utf8ToUtf16("IV");
         std::vector<float> advances(text.size());
         Range range(0, text.size());
-        EXPECT_EQ(6.0f, Layout::measureText(text, range, Bidi::LTR, paint, StartHyphenEdit::NO_EDIT,
-                                            EndHyphenEdit::NO_EDIT, advances.data(), nullptr));
+        EXPECT_EQ(6.0f,
+                  Layout::measureText(text, range, Bidi::LTR, paint, StartHyphenEdit::NO_EDIT,
+                                      EndHyphenEdit::NO_EDIT, advances.data(), nullptr, nullptr));
         ASSERT_EQ(2u, advances.size());
         EXPECT_EQ(1.0f, advances[0]);
         EXPECT_EQ(5.0f, advances[1]);
@@ -521,7 +542,7 @@ TEST_F(LayoutTest, measuredTextTest) {
         Range range(0, text.size());
         EXPECT_EQ(16.0f,
                   Layout::measureText(text, range, Bidi::LTR, paint, StartHyphenEdit::NO_EDIT,
-                                      EndHyphenEdit::NO_EDIT, advances.data(), nullptr));
+                                      EndHyphenEdit::NO_EDIT, advances.data(), nullptr, nullptr));
         ASSERT_EQ(3u, advances.size());
         EXPECT_EQ(1.0f, advances[0]);
         EXPECT_EQ(5.0f, advances[1]);
@@ -529,6 +550,60 @@ TEST_F(LayoutTest, measuredTextTest) {
     }
 }
 
+TEST_F(LayoutTest, doLayoutWithPrecomputedPiecesTest) {
+    float MARKER1 = 1e+16;
+    float MARKER2 = 1e+17;
+    auto fc = buildFontCollection("LayoutTestFont.ttf");
+    {
+        LayoutPieces pieces;
+
+        Layout inLayout = doLayout("I", MinikinPaint(fc));
+        inLayout.mAdvances[0] = MARKER1;  // Modify the advance to make sure this layout is used.
+        pieces.insert(utf8ToUtf16("I"), Range(0, 1), 0 /* hyphen edit */, inLayout);
+
+        Layout outLayout = doLayoutWithPrecomputedPieces("I", MinikinPaint(fc), pieces);
+        EXPECT_EQ(MARKER1, outLayout.mAdvances[0]);
+    }
+    {
+        LayoutPieces pieces;
+
+        Layout inLayout = doLayout("I", MinikinPaint(fc));
+        inLayout.mAdvances[0] = MARKER1;
+        pieces.insert(utf8ToUtf16("I"), Range(0, 1), 0 /* hyphen edit */, inLayout);
+
+        Layout outLayout = doLayoutWithPrecomputedPieces("II", MinikinPaint(fc), pieces);
+        // The layout pieces are used in word units. Should not be used "I" for "II".
+        EXPECT_NE(MARKER1, outLayout.mAdvances[0]);
+        EXPECT_NE(MARKER1, outLayout.mAdvances[1]);
+    }
+    {
+        LayoutPieces pieces;
+
+        Layout inLayout = doLayout("I", MinikinPaint(fc));
+        inLayout.mAdvances[0] = MARKER1;
+        pieces.insert(utf8ToUtf16("I"), Range(0, 1), 0 /* hyphen edit */, inLayout);
+
+        Layout outLayout = doLayoutWithPrecomputedPieces("I I", MinikinPaint(fc), pieces);
+        EXPECT_EQ(MARKER1, outLayout.mAdvances[0]);
+        EXPECT_EQ(MARKER1, outLayout.mAdvances[2]);
+    }
+    {
+        LayoutPieces pieces;
+
+        Layout inLayout = doLayout("I", MinikinPaint(fc));
+        inLayout.mAdvances[0] = MARKER1;  // Modify the advance to make sure this layout is used.
+        pieces.insert(utf8ToUtf16("I"), Range(0, 1), 0 /* hyphen edit */, inLayout);
+
+        inLayout = doLayout("V", MinikinPaint(fc));
+        inLayout.mAdvances[0] = MARKER2;  // Modify the advance to make sure this layout is used.
+        pieces.insert(utf8ToUtf16("V"), Range(0, 1), 0 /* hyphen edit */, inLayout);
+
+        Layout outLayout = doLayoutWithPrecomputedPieces("I V", MinikinPaint(fc), pieces);
+        EXPECT_EQ(MARKER1, outLayout.mAdvances[0]);
+        EXPECT_EQ(MARKER2, outLayout.mAdvances[2]);
+    }
+}
+
 // TODO: Add more test cases, e.g. measure text, letter spacing.
 
 }  // namespace minikin
diff --git a/tests/unittest/LineBreakerTestHelper.h b/tests/unittest/LineBreakerTestHelper.h
index 9eb73af..d6ab740 100644
--- a/tests/unittest/LineBreakerTestHelper.h
+++ b/tests/unittest/LineBreakerTestHelper.h
@@ -52,14 +52,16 @@ public:
     virtual bool canHyphenate() const override { return true; }
     virtual uint32_t getLocaleListId() const { return mLocaleListId; }
 
-    virtual void getMetrics(const U16StringPiece&, float* advances, MinikinExtent*) const {
+    virtual void getMetrics(const U16StringPiece&, float* advances, MinikinExtent*,
+                            LayoutPieces*) const {
         std::fill(advances, advances + mRange.getLength(), mWidth);
     }
 
     virtual const MinikinPaint* getPaint() const { return &mPaint; }
 
     virtual float measureHyphenPiece(const U16StringPiece&, const Range& range,
-                                     StartHyphenEdit start, EndHyphenEdit end, float*) const {
+                                     StartHyphenEdit start, EndHyphenEdit end, float*,
+                                     LayoutPieces*) const {
         uint32_t extraCharForHyphen = 0;
         if (isInsertion(start)) {
             extraCharForHyphen++;
diff --git a/tests/unittest/MeasuredTextTest.cpp b/tests/unittest/MeasuredTextTest.cpp
index 2cda52a..e8ed408 100644
--- a/tests/unittest/MeasuredTextTest.cpp
+++ b/tests/unittest/MeasuredTextTest.cpp
@@ -56,91 +56,4 @@ TEST(MeasuredTextTest, RunTests) {
     EXPECT_EQ(expectedWidths, measuredText->widths);
 }
 
-TEST(MeasuredTextTest, buildLayoutTest) {
-    std::vector<uint16_t> text = utf8ToUtf16("Hello, world.");
-    Range range(0, text.size());
-    auto font = buildFontCollection("Ascii.ttf");
-    MinikinPaint paint(font);
-    Bidi bidi = Bidi::FORCE_LTR;
-
-    MeasuredTextBuilder builder;
-    builder.addStyleRun(0, text.size(), MinikinPaint(font), false /* is RTL */);
-    std::unique_ptr<MeasuredText> mt = builder.build(
-            text, true /* compute hyphenation */,
-            false /* compute full layout. Fill manually later for testing purposes */);
-
-    auto& offsetMap = mt->layoutPieces.offsetMap;
-    {
-        // If there is no pre-computed layouts, do not touch layout and return false.
-        Layout layout;
-        offsetMap.clear();
-        EXPECT_FALSE(mt->buildLayout(text, range, paint, bidi, 0, StartHyphenEdit::NO_EDIT,
-                                     EndHyphenEdit::NO_EDIT, &layout));
-        EXPECT_EQ(0U, layout.nGlyphs());
-    }
-    {
-        // If layout result size is different, do not touch layout and return false.
-        Layout outLayout;
-        Layout inLayout;
-        inLayout.mAdvances.resize(text.size() + 1);
-        offsetMap.clear();
-        offsetMap[0] = inLayout;
-        EXPECT_FALSE(mt->buildLayout(text, range, paint, bidi, 0, StartHyphenEdit::NO_EDIT,
-                                     EndHyphenEdit::NO_EDIT, &outLayout));
-        EXPECT_EQ(0U, outLayout.nGlyphs());
-    }
-    {
-        // If requested layout starts from unknown position, do not touch layout and return false.
-        Layout outLayout;
-        Layout inLayout;
-        inLayout.mAdvances.resize(text.size());
-        offsetMap.clear();
-        offsetMap[0] = inLayout;
-        EXPECT_FALSE(mt->buildLayout(text, Range(range.getStart() + 1, range.getEnd()), paint, bidi,
-                                     0, StartHyphenEdit::NO_EDIT, EndHyphenEdit::NO_EDIT,
-                                     &outLayout));
-        EXPECT_EQ(0U, outLayout.nGlyphs());
-    }
-    {
-        // If requested layout starts from unknown position, do not touch layout and return false.
-        // (MeasuredText offset moves forward.)
-        Layout outLayout;
-        Layout inLayout;
-        inLayout.mAdvances.resize(text.size());
-        offsetMap.clear();
-        offsetMap[0] = inLayout;
-        EXPECT_FALSE(mt->buildLayout(text, range, paint, bidi, 1, StartHyphenEdit::NO_EDIT,
-                                     EndHyphenEdit::NO_EDIT, &outLayout));
-        EXPECT_EQ(0U, outLayout.nGlyphs());
-    }
-    {
-        // Currently justification is not supported.
-        Layout outLayout;
-        Layout inLayout;
-        inLayout.mAdvances.resize(text.size());
-        offsetMap.clear();
-        offsetMap[0] = inLayout;
-        MinikinPaint justifiedPaint(font);
-        justifiedPaint.wordSpacing = 1.0;
-        EXPECT_FALSE(mt->buildLayout(text, range, justifiedPaint, bidi, 0, StartHyphenEdit::NO_EDIT,
-                                     EndHyphenEdit::NO_EDIT, &outLayout));
-        EXPECT_EQ(0U, outLayout.nGlyphs());
-    }
-    {
-        // Currently hyphenation is not supported.
-        Layout outLayout;
-        Layout inLayout;
-        inLayout.mAdvances.resize(text.size());
-        offsetMap.clear();
-        offsetMap[0] = inLayout;
-        MinikinPaint hyphenatedPaint(font);
-        EXPECT_FALSE(mt->buildLayout(text, range, hyphenatedPaint, bidi, 0,
-                                     StartHyphenEdit::NO_EDIT, EndHyphenEdit::INSERT_HYPHEN,
-                                     &outLayout));
-        EXPECT_EQ(0U, outLayout.nGlyphs());
-    }
-
-    // TODO: Add positive test case. This requires Layout refactoring or real text layout in test.
-}
-
 }  // namespace minikin