Improve line breaking performance for complex text
authormitz@apple.com <mitz@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 27 Aug 2012 15:31:56 +0000 (15:31 +0000)
committermitz@apple.com <mitz@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 27 Aug 2012 15:31:56 +0000 (15:31 +0000)
https://bugs.webkit.org/show_bug.cgi?id=83045

Patch by Ned Holbrook <nholbrook@apple.com> on 2012-08-27
Reviewed by Darin Adler.

Currently RenderBlock::LineBreaker::nextLineBreak assumes that measuring individual words is as cheap
as free. This is not the case when dealing with complex text, which benefits from laying out as much
text as possible and by reusing that layout when feasible: by doing so this patch improves line
breaking by 25% as measured with a simple test app.

The bulk of this change is modifying ComplexTextController::advance, which previously required the
text offset to be strictly increasing and assumed unidirectional text; now it supports random seeking
in a naive fashion (by restarting to the beginning) and traverses glyphs in logical order. In the
latter case, the presence of any non-LTR runs triggers the population of a mapping from logical to
visual run indices. Finally, a new flag has been added which inhibits glyph advances from being split
across ligatures (thus causing spurious line breaks).

A ComplexTextController and its associated TextRun and Font are encapsulated in a TextLayout object,
which is instantiated as an opaque object via functions that are no-ops unless building for Mac. A
static member function (isNeeded) checks to see whether a TextRun is complex, in order to avoid
needless instantiation. It also bails if tabs would be enabled since positional effects are not yet
handled in this mode.

No behavioral changes are expected due to this change, so no new tests.

* platform/graphics/Font.cpp:
(WTF): Define deleteOwnedPtr for TextLayout as calling through destroyLayout; relying on operator delete is not workable as the class does not exist on all platforms.
(WTF::WebCore::TextLayout):
(WebCore): Implement no-op TextLayout wrappers for non-Mac platforms.
(WebCore::Font::createLayout):
(WebCore::Font::deleteLayout):
(WebCore::Font::width):
* platform/graphics/Font.h:
(WebCore): Add forward declarations for RenderText and TextLayout.
(Font): Add functions for dealing with pointer to TextLayout implementation.
(WTF): Declare deleteOwnedPtr for TextLayout.
* platform/graphics/mac/ComplexTextController.cpp:
(TextLayout): An instance of this class corresponds to a ComplexTextController for a particular TextRun.
(WebCore::TextLayout::isNeeded): Used by wrapper to avoid instantiation when complex layout is not required.
(WebCore::TextLayout::TextLayout):
(WebCore::TextLayout::width):
(WebCore::TextLayout::fontWithNoWordSpacing): Helper function to allow initialization of member variable.
(WebCore::TextLayout::constructTextRun): Ditto.
(WebCore): Implement real TextLayout wrappers for Mac.
(WebCore::Font::createLayout):
(WebCore::Font::deleteLayout):
(WebCore::Font::width):
(WebCore::ComplexTextController::ComplexTextController): Initialize m_ltrOnly and reserve initial capacity for m_runIndices.
(WebCore::ComplexTextController::indexOfCurrentRun): Return (visual) m_complexTextRuns index corresponding to (logical) m_currentRun, lazily constructing m_runIndices if needed.
(WebCore::ComplexTextController::incrementCurrentRun): Return next m_complexTextRuns index in logical order.
(WebCore::ComplexTextController::advance): Allow restarting, support for bidi reordering, and option to measure only whole glyphs rather than dividing advances.
(WebCore::ComplexTextController::adjustGlyphsAndAdvances): Clear m_ltrOnly on detecting a RTL run.
* platform/graphics/mac/ComplexTextController.h:
(ComplexTextController): Add m_ltrOnly indicating no bidi reordering, and m_runIndices mapping from runs (logical order) to m_complexTextRuns (visual order).
(WebCore::ComplexTextController::ComplexTextRun::indexBegin):
(WebCore::ComplexTextController::ComplexTextRun::isLTR):
(ComplexTextRun): Add helper functions returning values pertinent to individual runs as opposed to the entire containing line.
(WebCore::ComplexTextController::stringBegin): Return first string index.
(WebCore::ComplexTextController::stringEnd): Return one past last string index.
* platform/graphics/mac/ComplexTextControllerCoreText.mm: Initialize m_indexBegin and m_ltr.
(WebCore::ComplexTextController::ComplexTextRun::ComplexTextRun): Initialize m_indexBegin and m_ltr.
* rendering/RenderBlock.h:
(RenderTextInfo): Add single mapping from RenderText to LazyLineBreakIterator and (possibly null) TextLayout since they are recreated under the same circumstances.
* rendering/RenderBlockLineLayout.cpp:
(WebCore::RenderBlock::RenderTextInfo::RenderTextInfo): Make non-inline to avoid compilation errors.
(WebCore::RenderBlock::RenderTextInfo::~RenderTextInfo): Ditto.
(WebCore::RenderBlock::layoutRunsAndFloatsInRange): Allow RenderTextInfo to be reused across calls to nextLineBreak.
(WebCore::textWidth): Use TextLayout when supplied for measuring.
(WebCore::RenderBlock::LineBreaker::nextLineBreak):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@126763 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WebCore/ChangeLog
Source/WebCore/platform/graphics/Font.cpp
Source/WebCore/platform/graphics/Font.h
Source/WebCore/platform/graphics/mac/ComplexTextController.cpp
Source/WebCore/platform/graphics/mac/ComplexTextController.h
Source/WebCore/platform/graphics/mac/ComplexTextControllerCoreText.mm
Source/WebCore/rendering/RenderBlock.h
Source/WebCore/rendering/RenderBlockLineLayout.cpp

index e042425..9a5a20e 100644 (file)
@@ -1,3 +1,75 @@
+2012-08-27  Ned Holbrook  <nholbrook@apple.com>
+
+        Improve line breaking performance for complex text
+        https://bugs.webkit.org/show_bug.cgi?id=83045
+
+        Reviewed by Darin Adler.
+
+        Currently RenderBlock::LineBreaker::nextLineBreak assumes that measuring individual words is as cheap
+        as free. This is not the case when dealing with complex text, which benefits from laying out as much
+        text as possible and by reusing that layout when feasible: by doing so this patch improves line
+        breaking by 25% as measured with a simple test app.
+
+        The bulk of this change is modifying ComplexTextController::advance, which previously required the
+        text offset to be strictly increasing and assumed unidirectional text; now it supports random seeking
+        in a naive fashion (by restarting to the beginning) and traverses glyphs in logical order. In the
+        latter case, the presence of any non-LTR runs triggers the population of a mapping from logical to
+        visual run indices. Finally, a new flag has been added which inhibits glyph advances from being split
+        across ligatures (thus causing spurious line breaks).
+
+        A ComplexTextController and its associated TextRun and Font are encapsulated in a TextLayout object,
+        which is instantiated as an opaque object via functions that are no-ops unless building for Mac. A
+        static member function (isNeeded) checks to see whether a TextRun is complex, in order to avoid
+        needless instantiation. It also bails if tabs would be enabled since positional effects are not yet
+        handled in this mode.
+
+        No behavioral changes are expected due to this change, so no new tests.
+
+        * platform/graphics/Font.cpp:
+        (WTF): Define deleteOwnedPtr for TextLayout as calling through destroyLayout; relying on operator delete is not workable as the class does not exist on all platforms.
+        (WTF::WebCore::TextLayout):
+        (WebCore): Implement no-op TextLayout wrappers for non-Mac platforms.
+        (WebCore::Font::createLayout):
+        (WebCore::Font::deleteLayout):
+        (WebCore::Font::width):
+        * platform/graphics/Font.h:
+        (WebCore): Add forward declarations for RenderText and TextLayout.
+        (Font): Add functions for dealing with pointer to TextLayout implementation.
+        (WTF): Declare deleteOwnedPtr for TextLayout.
+        * platform/graphics/mac/ComplexTextController.cpp:
+        (TextLayout): An instance of this class corresponds to a ComplexTextController for a particular TextRun.
+        (WebCore::TextLayout::isNeeded): Used by wrapper to avoid instantiation when complex layout is not required.
+        (WebCore::TextLayout::TextLayout):
+        (WebCore::TextLayout::width):
+        (WebCore::TextLayout::fontWithNoWordSpacing): Helper function to allow initialization of member variable.
+        (WebCore::TextLayout::constructTextRun): Ditto.
+        (WebCore): Implement real TextLayout wrappers for Mac.
+        (WebCore::Font::createLayout):
+        (WebCore::Font::deleteLayout):
+        (WebCore::Font::width):
+        (WebCore::ComplexTextController::ComplexTextController): Initialize m_ltrOnly and reserve initial capacity for m_runIndices.
+        (WebCore::ComplexTextController::indexOfCurrentRun): Return (visual) m_complexTextRuns index corresponding to (logical) m_currentRun, lazily constructing m_runIndices if needed.
+        (WebCore::ComplexTextController::incrementCurrentRun): Return next m_complexTextRuns index in logical order.
+        (WebCore::ComplexTextController::advance): Allow restarting, support for bidi reordering, and option to measure only whole glyphs rather than dividing advances.
+        (WebCore::ComplexTextController::adjustGlyphsAndAdvances): Clear m_ltrOnly on detecting a RTL run.
+        * platform/graphics/mac/ComplexTextController.h:
+        (ComplexTextController): Add m_ltrOnly indicating no bidi reordering, and m_runIndices mapping from runs (logical order) to m_complexTextRuns (visual order).
+        (WebCore::ComplexTextController::ComplexTextRun::indexBegin):
+        (WebCore::ComplexTextController::ComplexTextRun::isLTR):
+        (ComplexTextRun): Add helper functions returning values pertinent to individual runs as opposed to the entire containing line.
+        (WebCore::ComplexTextController::stringBegin): Return first string index.
+        (WebCore::ComplexTextController::stringEnd): Return one past last string index.
+        * platform/graphics/mac/ComplexTextControllerCoreText.mm: Initialize m_indexBegin and m_ltr.
+        (WebCore::ComplexTextController::ComplexTextRun::ComplexTextRun): Initialize m_indexBegin and m_ltr.
+        * rendering/RenderBlock.h:
+        (RenderTextInfo): Add single mapping from RenderText to LazyLineBreakIterator and (possibly null) TextLayout since they are recreated under the same circumstances.
+        * rendering/RenderBlockLineLayout.cpp:
+        (WebCore::RenderBlock::RenderTextInfo::RenderTextInfo): Make non-inline to avoid compilation errors.
+        (WebCore::RenderBlock::RenderTextInfo::~RenderTextInfo): Ditto.
+        (WebCore::RenderBlock::layoutRunsAndFloatsInRange): Allow RenderTextInfo to be reused across calls to nextLineBreak.
+        (WebCore::textWidth): Use TextLayout when supplied for measuring.
+        (WebCore::RenderBlock::LineBreaker::nextLineBreak):
+
 2012-08-27  Nico Weber  <thakis@chromium.org>
 
         Add two missing variable initializers to RenderFlowThread
index db07f0a..cd8ea63 100644 (file)
 using namespace WTF;
 using namespace Unicode;
 
+namespace WTF {
+
+// allow compilation of OwnPtr<TextLayout> in source files that don't have access to the TextLayout class definition
+template <> void deleteOwnedPtr<WebCore::TextLayout>(WebCore::TextLayout* ptr)
+{
+    WebCore::Font::deleteLayout(ptr);
+}
+
+}
+
 namespace WebCore {
 
 const uint8_t Font::s_roundingHackCharacterTable[256] = {
@@ -197,6 +207,25 @@ float Font::width(const TextRun& run, int& charsConsumed, String& glyphName) con
     return floatWidthForComplexText(run);
 }
 
+#if !PLATFORM(MAC)
+
+PassOwnPtr<TextLayout> Font::createLayout(RenderText*, float, bool) const
+{
+    return nullptr;
+}
+
+void Font::deleteLayout(TextLayout*)
+{
+}
+
+float Font::width(TextLayout&, unsigned, unsigned)
+{
+    ASSERT_NOT_REACHED();
+    return 0;
+}
+
+#endif
+
 FloatRect Font::selectionRectForText(const TextRun& run, const FloatPoint& point, int h, int from, int to) const
 {
     to = (to == -1 ? run.length() : to);
index 5e38a96..2ec2605 100644 (file)
@@ -53,6 +53,8 @@ class FontSelector;
 class GlyphBuffer;
 class GlyphPageTreeNode;
 class GraphicsContext;
+class RenderText;
+class TextLayout;
 class TextRun;
 
 struct GlyphData;
@@ -102,6 +104,10 @@ public:
     float width(const TextRun&, HashSet<const SimpleFontData*>* fallbackFonts = 0, GlyphOverflow* = 0) const;
     float width(const TextRun&, int& charsConsumed, String& glyphName) const;
 
+    PassOwnPtr<TextLayout> createLayout(RenderText*, float xPos, bool collapseWhiteSpace) const;
+    static void deleteLayout(TextLayout*);
+    static float width(TextLayout&, unsigned from, unsigned len);
+
     int offsetForPosition(const TextRun&, float position, bool includePartialGlyphs) const;
     FloatRect selectionRectForText(const TextRun&, const FloatPoint&, int h, int from = 0, int to = -1) const;
 
@@ -310,4 +316,10 @@ inline float Font::tabWidth(const SimpleFontData& fontData, unsigned tabSize, fl
 
 }
 
+namespace WTF {
+
+template <> void deleteOwnedPtr<WebCore::TextLayout>(WebCore::TextLayout*);
+
+}
+
 #endif
index 83d6ee4..29b77a1 100644 (file)
@@ -27,6 +27,8 @@
 
 #include "FloatSize.h"
 #include "Font.h"
+#include "RenderBlock.h"
+#include "RenderText.h"
 #include "TextBreakIterator.h"
 #include "TextRun.h"
 #include <ApplicationServices/ApplicationServices.h>
@@ -37,6 +39,71 @@ using namespace std;
 
 namespace WebCore {
 
+class TextLayout {
+public:
+    static bool isNeeded(RenderText* text, const Font& font)
+    {
+        TextRun run = RenderBlock::constructTextRun(text, font, text->characters(), text->textLength(), text->style());
+        return font.codePath(run) == Font::Complex;
+    }
+
+    TextLayout(RenderText* text, const Font& font, float xPos)
+        : m_font(fontWithNoWordSpacing(font))
+        , m_run(constructTextRun(text, font, xPos))
+        , m_controller(adoptPtr(new ComplexTextController(&m_font, m_run, true)))
+    {
+    }
+
+    float width(unsigned from, unsigned len)
+    {
+        m_controller->advance(from, 0, ByWholeGlyphs);
+        float beforeWidth = m_controller->runWidthSoFar();
+        m_controller->advance(from + len, 0, ByWholeGlyphs);
+        float afterWidth = m_controller->runWidthSoFar();
+        return afterWidth - beforeWidth;
+    }
+
+private:
+    static Font fontWithNoWordSpacing(const Font& originalFont)
+    {
+        Font font(originalFont);
+        font.setWordSpacing(0);
+        return font;
+    }
+
+    static TextRun constructTextRun(RenderText* text, const Font& font, float xPos)
+    {
+        TextRun run = RenderBlock::constructTextRun(text, font, text->characters(), text->textLength(), text->style());
+        run.setCharactersLength(text->textLength());
+        ASSERT(run.charactersLength() >= run.length());
+
+        run.setXPos(xPos);
+        return run;
+    }
+
+    // ComplexTextController has only references to its Font and TextRun so they must be kept alive here.
+    Font m_font;
+    TextRun m_run;
+    OwnPtr<ComplexTextController> m_controller;
+};
+
+PassOwnPtr<TextLayout> Font::createLayout(RenderText* text, float xPos, bool collapseWhiteSpace) const
+{
+    if (!collapseWhiteSpace || !TextLayout::isNeeded(text, *this))
+        return nullptr;
+    return adoptPtr(new TextLayout(text, *this, xPos));
+}
+
+void Font::deleteLayout(TextLayout* layout)
+{
+    delete layout;
+}
+
+float Font::width(TextLayout& layout, unsigned from, unsigned len)
+{
+    return layout.width(from, len);
+}
+
 static inline CGFloat roundCGFloat(CGFloat f)
 {
     if (sizeof(CGFloat) == sizeof(float))
@@ -54,6 +121,7 @@ static inline CGFloat ceilCGFloat(CGFloat f)
 ComplexTextController::ComplexTextController(const Font* font, const TextRun& run, bool mayUseNaturalWritingDirection, HashSet<const SimpleFontData*>* fallbackFonts, bool forTextEmphasis)
     : m_font(*font)
     , m_run(run)
+    , m_isLTROnly(true)
     , m_mayUseNaturalWritingDirection(mayUseNaturalWritingDirection)
     , m_forTextEmphasis(forTextEmphasis)
     , m_currentCharacter(0)
@@ -92,6 +160,9 @@ ComplexTextController::ComplexTextController(const Font* font, const TextRun& ru
     collectComplexTextRuns();
     adjustGlyphsAndAdvances();
 
+    if (!m_isLTROnly)
+        m_runIndices.reserveInitialCapacity(m_complexTextRuns.size());
+
     m_runWidthSoFar = m_leadingExpansion;
 }
 
@@ -340,25 +411,75 @@ void ComplexTextController::ComplexTextRun::setIsNonMonotonic()
     }
 }
 
-void ComplexTextController::advance(unsigned offset, GlyphBuffer* glyphBuffer)
+unsigned ComplexTextController::indexOfCurrentRun(unsigned& leftmostGlyph)
+{
+    leftmostGlyph = 0;
+    
+    size_t runCount = m_complexTextRuns.size();
+    if (m_currentRun >= runCount)
+        return runCount;
+
+    if (m_isLTROnly) {
+        for (unsigned i = 0; i < m_currentRun; ++i)
+            leftmostGlyph += m_complexTextRuns[i]->glyphCount();
+        return m_currentRun;
+    }
+
+    while (m_runIndices.size() <= m_currentRun) {
+        unsigned offset = m_runIndices.isEmpty() ? 0 : stringEnd(*m_complexTextRuns[m_runIndices.last()]);
+
+        for (unsigned i = 0; i < runCount; ++i) {
+            if (offset == stringBegin(*m_complexTextRuns[i])) {
+                m_runIndices.uncheckedAppend(i);
+                break;
+            }
+        }
+    }
+
+    unsigned currentRunIndex = m_runIndices[m_currentRun];
+    for (unsigned i = 0; i < currentRunIndex; ++i)
+        leftmostGlyph += m_complexTextRuns[i]->glyphCount();
+    return currentRunIndex;
+}
+
+unsigned ComplexTextController::incrementCurrentRun(unsigned& leftmostGlyph)
+{
+    if (m_isLTROnly) {
+        leftmostGlyph += m_complexTextRuns[m_currentRun++]->glyphCount();
+        return m_currentRun;
+    }
+
+    m_currentRun++;
+    leftmostGlyph = 0;
+    return indexOfCurrentRun(leftmostGlyph);
+}
+
+void ComplexTextController::advance(unsigned offset, GlyphBuffer* glyphBuffer, GlyphIterationStyle iterationStyle)
 {
     if (static_cast<int>(offset) > m_end)
         offset = m_end;
 
-    if (offset <= m_currentCharacter)
-        return;
+    if (offset <= m_currentCharacter) {
+        m_runWidthSoFar = m_leadingExpansion;
+        m_numGlyphsSoFar = 0;
+        m_currentRun = 0;
+        m_glyphInCurrentRun = 0;
+        m_characterInCurrentGlyph = 0;
+    }
 
     m_currentCharacter = offset;
 
     size_t runCount = m_complexTextRuns.size();
 
-    bool ltr = m_run.ltr();
-
-    unsigned k = ltr ? m_numGlyphsSoFar : m_adjustedGlyphs.size() - 1 - m_numGlyphsSoFar;
+    unsigned leftmostGlyph = 0;
+    unsigned currentRunIndex = indexOfCurrentRun(leftmostGlyph);
     while (m_currentRun < runCount) {
-        const ComplexTextRun& complexTextRun = *m_complexTextRuns[ltr ? m_currentRun : runCount - 1 - m_currentRun];
+        const ComplexTextRun& complexTextRun = *m_complexTextRuns[currentRunIndex];
+        bool ltr = complexTextRun.isLTR();
         size_t glyphCount = complexTextRun.glyphCount();
         unsigned g = ltr ? m_glyphInCurrentRun : glyphCount - 1 - m_glyphInCurrentRun;
+        unsigned k = leftmostGlyph + g;
+
         while (m_glyphInCurrentRun < glyphCount) {
             unsigned glyphStartOffset = complexTextRun.indexAt(g);
             unsigned glyphEndOffset;
@@ -387,6 +508,9 @@ void ComplexTextController::advance(unsigned offset, GlyphBuffer* glyphBuffer)
                 // When there are multiple glyphs per character we need to advance by the full width of the glyph.
                 ASSERT(m_characterInCurrentGlyph == oldCharacterInCurrentGlyph);
                 m_runWidthSoFar += adjustedAdvance.width;
+            } else if (iterationStyle == ByWholeGlyphs) {
+                if (!oldCharacterInCurrentGlyph)
+                    m_runWidthSoFar += adjustedAdvance.width;
             } else
                 m_runWidthSoFar += adjustedAdvance.width * (m_characterInCurrentGlyph - oldCharacterInCurrentGlyph) / (glyphEndOffset - glyphStartOffset);
 
@@ -404,10 +528,10 @@ void ComplexTextController::advance(unsigned offset, GlyphBuffer* glyphBuffer)
                 k--;
             }
         }
-        m_currentRun++;
+        currentRunIndex = incrementCurrentRun(leftmostGlyph);
         m_glyphInCurrentRun = 0;
     }
-    if (!ltr && m_numGlyphsSoFar == m_adjustedAdvances.size())
+    if (!m_run.ltr() && m_numGlyphsSoFar == m_adjustedAdvances.size())
         m_runWidthSoFar += m_finalRoundingWidth;
 }
 
@@ -421,6 +545,9 @@ void ComplexTextController::adjustGlyphsAndAdvances()
         unsigned glyphCount = complexTextRun.glyphCount();
         const SimpleFontData* fontData = complexTextRun.fontData();
 
+        if (!complexTextRun.isLTR())
+            m_isLTROnly = false;
+
         const CGGlyph* glyphs = complexTextRun.glyphs();
         const CGSize* advances = complexTextRun.advances();
 
index 7c00dcb..b3165c2 100644 (file)
@@ -44,6 +44,8 @@ class Font;
 class SimpleFontData;
 class TextRun;
 
+enum GlyphIterationStyle { IncludePartialGlyphs, ByWholeGlyphs };
+
 // ComplexTextController is responsible for rendering and measuring glyphs for
 // complex scripts on OS X.
 class ComplexTextController {
@@ -51,7 +53,7 @@ public:
     ComplexTextController(const Font*, const TextRun&, bool mayUseNaturalWritingDirection = false, HashSet<const SimpleFontData*>* fallbackFonts = 0, bool forTextEmphasis = false);
 
     // Advance and emit glyphs up to the specified character.
-    void advance(unsigned to, GlyphBuffer* = 0);
+    void advance(unsigned to, GlyphBuffer* = 0, GlyphIterationStyle = IncludePartialGlyphs);
 
     // Compute the character offset for a given x coordinate.
     int offsetForPosition(float x, bool includePartialGlyphs);
@@ -89,10 +91,12 @@ private:
         unsigned stringLocation() const { return m_stringLocation; }
         size_t stringLength() const { return m_stringLength; }
         ALWAYS_INLINE CFIndex indexAt(size_t i) const;
+        CFIndex indexBegin() const { return m_indexBegin; }
         CFIndex indexEnd() const { return m_indexEnd; }
         CFIndex endOffsetAt(size_t i) const { ASSERT(!m_isMonotonic); return m_glyphEndOffsets[i]; }
         const CGGlyph* glyphs() const { return m_glyphs; }
         const CGSize* advances() const { return m_advances; }
+        bool isLTR() const { return m_isLTR; }
         bool isMonotonic() const { return m_isMonotonic; }
         void setIsNonMonotonic();
 
@@ -107,22 +111,35 @@ private:
         size_t m_stringLength;
         Vector<CFIndex, 64> m_coreTextIndicesVector;
         const CFIndex* m_coreTextIndices;
+        CFIndex m_indexBegin;
         CFIndex m_indexEnd;
         Vector<CFIndex, 64> m_glyphEndOffsets;
         Vector<CGGlyph, 64> m_glyphsVector;
         const CGGlyph* m_glyphs;
         Vector<CGSize, 64> m_advancesVector;
         const CGSize* m_advances;
+        bool m_isLTR;
         bool m_isMonotonic;
     };
+    
+    static unsigned stringBegin(const ComplexTextRun& run) { return run.stringLocation() + run.indexBegin(); }
+    static unsigned stringEnd(const ComplexTextRun& run) { return run.stringLocation() + run.indexEnd(); }
 
     void collectComplexTextRuns();
 
     void collectComplexTextRunsForCharacters(const UChar*, unsigned length, unsigned stringLocation, const SimpleFontData*);
     void adjustGlyphsAndAdvances();
 
+    unsigned indexOfCurrentRun(unsigned& leftmostGlyph);
+    unsigned incrementCurrentRun(unsigned& leftmostGlyph);
+
+    // The default size of this vector was selected as being the smallest power of two greater than
+    // the average (3.5) plus one standard deviation (7.5) of nonzero sizes used on Arabic Wikipedia.
+    Vector<unsigned, 16> m_runIndices;
+
     const Font& m_font;
     const TextRun& m_run;
+    bool m_isLTROnly;
     bool m_mayUseNaturalWritingDirection;
     bool m_forTextEmphasis;
 
index a993b77..2440fd4 100644 (file)
@@ -105,7 +105,9 @@ ComplexTextController::ComplexTextRun::ComplexTextRun(CTRunRef ctRun, const Simp
     , m_characters(characters)
     , m_stringLocation(stringLocation)
     , m_stringLength(stringLength)
+    , m_indexBegin(runRange.location)
     , m_indexEnd(runRange.location + runRange.length)
+    , m_isLTR(!(CTRunGetStatus(ctRun) & kCTRunStatusRightToLeft))
     , m_isMonotonic(true)
 {
     m_glyphCount = CTRunGetGlyphCount(ctRun);
@@ -138,7 +140,9 @@ ComplexTextController::ComplexTextRun::ComplexTextRun(const SimpleFontData* font
     , m_characters(characters)
     , m_stringLocation(stringLocation)
     , m_stringLength(stringLength)
+    , m_indexBegin(0)
     , m_indexEnd(stringLength)
+    , m_isLTR(ltr)
     , m_isMonotonic(true)
 {
     m_coreTextIndicesVector.reserveInitialCapacity(m_stringLength);
index 1a7eba1..2f84b08 100644 (file)
@@ -29,6 +29,7 @@
 #include "RenderBox.h"
 #include "RenderLineBoxList.h"
 #include "RootInlineBox.h"
+#include "TextBreakIterator.h"
 #include "TextRun.h"
 #include <wtf/OwnPtr.h>
 #include <wtf/ListHashSet.h>
@@ -42,7 +43,6 @@ namespace WebCore {
 class BidiContext;
 class InlineIterator;
 class LayoutStateMaintainer;
-class LazyLineBreakIterator;
 class LineLayoutState;
 class LineWidth;
 class RenderInline;
@@ -52,6 +52,7 @@ struct BidiRun;
 struct PaintInfo;
 class LineInfo;
 class RenderRubyRun;
+class TextLayout;
 
 template <class Iterator, class Run> class BidiResolver;
 template <class Run> class BidiRunList;
@@ -706,7 +707,16 @@ private:
     LayoutPoint computeLogicalLocationForFloat(const FloatingObject*, LayoutUnit logicalTopOffset) const;
 
     // The following functions' implementations are in RenderBlockLineLayout.cpp.
-    typedef std::pair<RenderText*, LazyLineBreakIterator> LineBreakIteratorInfo;
+    struct RenderTextInfo {
+        // Destruction of m_layout requires TextLayout to be a complete type, so the constructor and destructor are made non-inline to avoid compilation errors.
+        RenderTextInfo();
+        ~RenderTextInfo();
+
+        RenderText* m_text;
+        OwnPtr<TextLayout> m_layout;
+        LazyLineBreakIterator m_lineBreakIterator;
+    };
+
     class LineBreaker {
     public:
         LineBreaker(RenderBlock* block)
@@ -715,7 +725,7 @@ private:
             reset();
         }
 
-        InlineIterator nextLineBreak(InlineBidiResolver&, LineInfo&, LineBreakIteratorInfo&, FloatingObject* lastFloatFromPreviousLine, unsigned consecutiveHyphenatedLines);
+        InlineIterator nextLineBreak(InlineBidiResolver&, LineInfo&, RenderTextInfo&, FloatingObject* lastFloatFromPreviousLine, unsigned consecutiveHyphenatedLines);
 
         bool lineWasHyphenated() { return m_hyphenated; }
         const Vector<RenderBox*>& positionedObjects() { return m_positionedObjects; }
index 734e5e6..b64c1d3 100755 (executable)
@@ -36,7 +36,6 @@
 #include "RenderRubyRun.h"
 #include "RenderView.h"
 #include "Settings.h"
-#include "TextBreakIterator.h"
 #include "TrailingFloatsRootInlineBox.h"
 #include "VerticalPositionCache.h"
 #include "break_lines.h"
@@ -1274,6 +1273,15 @@ void RenderBlock::layoutRunsAndFloats(LineLayoutState& layoutState, bool hasInli
     repaintDirtyFloats(layoutState.floats());
 }
 
+RenderBlock::RenderTextInfo::RenderTextInfo()
+    : m_text(0)
+{
+}
+
+RenderBlock::RenderTextInfo::~RenderTextInfo()
+{
+}
+
 void RenderBlock::layoutRunsAndFloatsInRange(LineLayoutState& layoutState, InlineBidiResolver& resolver, const InlineIterator& cleanLineStart, const BidiStatus& cleanLineBidiStatus, unsigned consecutiveHyphenatedLines)
 {
     RenderStyle* styleToUse = style();
@@ -1281,7 +1289,7 @@ void RenderBlock::layoutRunsAndFloatsInRange(LineLayoutState& layoutState, Inlin
     LineMidpointState& lineMidpointState = resolver.midpointState();
     InlineIterator end = resolver.position();
     bool checkForEndLineMatch = layoutState.endLine();
-    LineBreakIteratorInfo lineBreakIteratorInfo;
+    RenderTextInfo renderTextInfo;
     VerticalPositionCache verticalPositionCache;
 
     LineBreaker lineBreaker(this);
@@ -1317,7 +1325,7 @@ void RenderBlock::layoutRunsAndFloatsInRange(LineLayoutState& layoutState, Inlin
         if (wrapShapeInfo)
             wrapShapeInfo->computeSegmentsForLine(logicalHeight());
 #endif
-        end = lineBreaker.nextLineBreak(resolver, layoutState.lineInfo(), lineBreakIteratorInfo, lastFloatFromPreviousLine, consecutiveHyphenatedLines);
+        end = lineBreaker.nextLineBreak(resolver, layoutState.lineInfo(), renderTextInfo, lastFloatFromPreviousLine, consecutiveHyphenatedLines);
         if (resolver.position().atEnd()) {
             // FIXME: We shouldn't be creating any runs in nextLineBreak to begin with!
             // Once BidiRunList is separated from BidiResolver this will not be needed.
@@ -2017,11 +2025,14 @@ static bool shouldSkipWhitespaceAfterStartObject(RenderBlock* block, RenderObjec
     return false;
 }
 
-static inline float textWidth(RenderText* text, unsigned from, unsigned len, const Font& font, float xPos, bool isFixedPitch, bool collapseWhiteSpace)
+static inline float textWidth(RenderText* text, unsigned from, unsigned len, const Font& font, float xPos, bool isFixedPitch, bool collapseWhiteSpace, TextLayout* layout = 0)
 {
     if (isFixedPitch || (!from && len == text->textLength()) || text->style()->hasTextCombine())
         return text->width(from, len, font, xPos);
 
+    if (layout)
+        return Font::width(*layout, from, len);
+
     TextRun run = RenderBlock::constructTextRun(text, font, text->characters() + from, len, text->style());
     run.setCharactersLength(text->textLength() - from);
     ASSERT(run.charactersLength() >= run.length());
@@ -2183,8 +2194,7 @@ void RenderBlock::LineBreaker::reset()
     m_clear = CNONE;
 }
 
-InlineIterator RenderBlock::LineBreaker::nextLineBreak(InlineBidiResolver& resolver, LineInfo& lineInfo,
-    LineBreakIteratorInfo& lineBreakIteratorInfo, FloatingObject* lastFloatFromPreviousLine, unsigned consecutiveHyphenatedLines)
+InlineIterator RenderBlock::LineBreaker::nextLineBreak(InlineBidiResolver& resolver, LineInfo& lineInfo, RenderTextInfo& renderTextInfo, FloatingObject* lastFloatFromPreviousLine, unsigned consecutiveHyphenatedLines)
 {
     reset();
 
@@ -2423,6 +2433,13 @@ InlineIterator RenderBlock::LineBreaker::nextLineBreak(InlineBidiResolver& resol
                 ASSERT(current.m_pos == t->textLength());
             }
 
+            if (renderTextInfo.m_text != t || renderTextInfo.m_lineBreakIterator.string() != t->characters()) {
+                renderTextInfo.m_text = t;
+                renderTextInfo.m_layout = f.createLayout(t, width.currentWidth(), collapseWhiteSpace);
+                renderTextInfo.m_lineBreakIterator.reset(t->characters(), t->textLength(), style->locale());
+            }
+            TextLayout* textLayout = renderTextInfo.m_layout.get();
+
             for (; current.m_pos < t->textLength(); current.fastIncrementInTextNode()) {
                 bool previousCharacterIsSpace = currentCharacterIsSpace;
                 bool previousCharacterIsWS = currentCharacterIsWS;
@@ -2444,16 +2461,11 @@ InlineIterator RenderBlock::LineBreaker::nextLineBreak(InlineBidiResolver& resol
                 if ((breakAll || breakWords) && !midWordBreak) {
                     wrapW += charWidth;
                     bool midWordBreakIsBeforeSurrogatePair = U16_IS_LEAD(c) && current.m_pos + 1 < t->textLength() && U16_IS_TRAIL(t->characters()[current.m_pos + 1]);
-                    charWidth = textWidth(t, current.m_pos, midWordBreakIsBeforeSurrogatePair ? 2 : 1, f, width.committedWidth() + wrapW, isFixedPitch, collapseWhiteSpace);
+                    charWidth = textWidth(t, current.m_pos, midWordBreakIsBeforeSurrogatePair ? 2 : 1, f, width.committedWidth() + wrapW, isFixedPitch, collapseWhiteSpace, textLayout);
                     midWordBreak = width.committedWidth() + wrapW + charWidth > width.availableWidth();
                 }
 
-                if ((lineBreakIteratorInfo.first != t) || (lineBreakIteratorInfo.second.string() != t->characters())) {
-                    lineBreakIteratorInfo.first = t;
-                    lineBreakIteratorInfo.second.reset(t->characters(), t->textLength(), style->locale());
-                }
-
-                bool betweenWords = c == '\n' || (currWS != PRE && !atStart && isBreakable(lineBreakIteratorInfo.second, current.m_pos, current.m_nextBreakablePosition, breakNBSP)
+                bool betweenWords = c == '\n' || (currWS != PRE && !atStart && isBreakable(renderTextInfo.m_lineBreakIterator, current.m_pos, current.m_nextBreakablePosition, breakNBSP)
                     && (style->hyphens() != HyphensNone || (current.previousInSameNode() != softHyphen)));
 
                 if (betweenWords || midWordBreak) {
@@ -2475,9 +2487,9 @@ InlineIterator RenderBlock::LineBreaker::nextLineBreak(InlineBidiResolver& resol
 
                     float additionalTmpW;
                     if (wordTrailingSpaceWidth && currentCharacterIsSpace)
-                        additionalTmpW = textWidth(t, lastSpace, current.m_pos + 1 - lastSpace, f, width.currentWidth(), isFixedPitch, collapseWhiteSpace) - wordTrailingSpaceWidth + lastSpaceWordSpacing;
+                        additionalTmpW = textWidth(t, lastSpace, current.m_pos + 1 - lastSpace, f, width.currentWidth(), isFixedPitch, collapseWhiteSpace, textLayout) - wordTrailingSpaceWidth + lastSpaceWordSpacing;
                     else
-                        additionalTmpW = textWidth(t, lastSpace, current.m_pos - lastSpace, f, width.currentWidth(), isFixedPitch, collapseWhiteSpace) + lastSpaceWordSpacing;
+                        additionalTmpW = textWidth(t, lastSpace, current.m_pos - lastSpace, f, width.currentWidth(), isFixedPitch, collapseWhiteSpace, textLayout) + lastSpaceWordSpacing;
                     width.addUncommittedWidth(additionalTmpW);
                     if (!appliedStartWidth) {
                         width.addUncommittedWidth(inlineLogicalWidth(current.m_obj, true, false));
@@ -2494,7 +2506,7 @@ InlineIterator RenderBlock::LineBreaker::nextLineBreak(InlineBidiResolver& resol
                         // as candidate width for this line.
                         bool lineWasTooWide = false;
                         if (width.fitsOnLine() && currentCharacterIsWS && currentStyle->breakOnlyAfterWhiteSpace() && !midWordBreak) {
-                            float charWidth = textWidth(t, current.m_pos, 1, f, width.currentWidth(), isFixedPitch, collapseWhiteSpace) + (applyWordSpacing ? wordSpacing : 0);
+                            float charWidth = textWidth(t, current.m_pos, 1, f, width.currentWidth(), isFixedPitch, collapseWhiteSpace, textLayout) + (applyWordSpacing ? wordSpacing : 0);
                             // Check if line is too big even without the extra space
                             // at the end of the line. If it is not, do nothing.
                             // If the line needs the extra whitespace to be too long,
@@ -2620,7 +2632,7 @@ InlineIterator RenderBlock::LineBreaker::nextLineBreak(InlineBidiResolver& resol
             }
 
             // IMPORTANT: current.m_pos is > length here!
-            float additionalTmpW = ignoringSpaces ? 0 : textWidth(t, lastSpace, current.m_pos - lastSpace, f, width.currentWidth(), isFixedPitch, collapseWhiteSpace) + lastSpaceWordSpacing;
+            float additionalTmpW = ignoringSpaces ? 0 : textWidth(t, lastSpace, current.m_pos - lastSpace, f, width.currentWidth(), isFixedPitch, collapseWhiteSpace, textLayout) + lastSpaceWordSpacing;
             width.addUncommittedWidth(additionalTmpW + inlineLogicalWidth(current.m_obj, !appliedStartWidth, includeEndWidth));
             includeEndWidth = false;