Simple line layout: use std::upper_bound in splitFragmentToFitLine()
authorzalan@apple.com <zalan@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 2 Feb 2015 23:53:26 +0000 (23:53 +0000)
committerzalan@apple.com <zalan@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 2 Feb 2015 23:53:26 +0000 (23:53 +0000)
https://bugs.webkit.org/show_bug.cgi?id=141146

Reviewed by Antti Koivisto.

Replace the custom binary search implementation with std::upper_bound and
move splitting functionality to TextFragment.

No change in functionality.

* rendering/SimpleLineLayout.cpp:
(WebCore::SimpleLineLayout::FragmentForwardIterator::FragmentForwardIterator):
(WebCore::SimpleLineLayout::FragmentForwardIterator::operator++):
(WebCore::SimpleLineLayout::FragmentForwardIterator::operator!=):
(WebCore::SimpleLineLayout::FragmentForwardIterator::operator*):
(WebCore::SimpleLineLayout::begin):
(WebCore::SimpleLineLayout::end):
(WebCore::SimpleLineLayout::splitFragmentToFitLine):
* rendering/SimpleLineLayoutFlowContentsIterator.cpp:
(WebCore::SimpleLineLayout::FlowContentsIterator::runWidth):
* rendering/SimpleLineLayoutFlowContentsIterator.h:
(WebCore::SimpleLineLayout::FlowContentsIterator::TextFragment::split):

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

Source/WebCore/ChangeLog
Source/WebCore/rendering/SimpleLineLayout.cpp
Source/WebCore/rendering/SimpleLineLayoutFlowContentsIterator.cpp
Source/WebCore/rendering/SimpleLineLayoutFlowContentsIterator.h

index 052ca56..39daf89 100644 (file)
@@ -1,3 +1,28 @@
+2015-02-02  Zalan Bujtas  <zalan@apple.com>
+
+        Simple line layout: use std::upper_bound in splitFragmentToFitLine()
+        https://bugs.webkit.org/show_bug.cgi?id=141146
+
+        Reviewed by Antti Koivisto.
+
+        Replace the custom binary search implementation with std::upper_bound and
+        move splitting functionality to TextFragment.
+
+        No change in functionality.
+
+        * rendering/SimpleLineLayout.cpp:
+        (WebCore::SimpleLineLayout::FragmentForwardIterator::FragmentForwardIterator):
+        (WebCore::SimpleLineLayout::FragmentForwardIterator::operator++):
+        (WebCore::SimpleLineLayout::FragmentForwardIterator::operator!=):
+        (WebCore::SimpleLineLayout::FragmentForwardIterator::operator*):
+        (WebCore::SimpleLineLayout::begin):
+        (WebCore::SimpleLineLayout::end):
+        (WebCore::SimpleLineLayout::splitFragmentToFitLine):
+        * rendering/SimpleLineLayoutFlowContentsIterator.cpp:
+        (WebCore::SimpleLineLayout::FlowContentsIterator::runWidth):
+        * rendering/SimpleLineLayoutFlowContentsIterator.h:
+        (WebCore::SimpleLineLayout::FlowContentsIterator::TextFragment::split):
+
 2015-02-02  Geoffrey Garen  <ggaren@apple.com>
 
         Use FastMalloc (bmalloc) instead of BlockAllocator for GC pages
index b9312b6..aba48b6 100644 (file)
@@ -297,6 +297,29 @@ private:
     bool m_firstCharacterFits { false };
 };
 
+class FragmentForwardIterator : public std::iterator<std::forward_iterator_tag, unsigned> {
+public:
+    FragmentForwardIterator(unsigned fragmentIndex)
+        : m_fragmentIndex(fragmentIndex)
+    {
+    }
+
+    FragmentForwardIterator& operator++()
+    {
+        ++m_fragmentIndex;
+        return *this;
+    }
+
+    bool operator!=(const FragmentForwardIterator& other) const { return m_fragmentIndex != other.m_fragmentIndex; }
+    unsigned operator*() const { return m_fragmentIndex; }
+
+private:
+    unsigned m_fragmentIndex { 0 };
+};
+
+static FragmentForwardIterator begin(const FlowContentsIterator::TextFragment& fragment)  { return FragmentForwardIterator(fragment.start()); }
+static FragmentForwardIterator end(const FlowContentsIterator::TextFragment& fragment)  { return FragmentForwardIterator(fragment.end()); }
+
 static bool preWrap(const FlowContentsIterator::Style& style)
 {
     return style.wrapLines && !style.collapseWhitespace;
@@ -330,48 +353,16 @@ static void updateLineConstrains(const RenderBlockFlow& flow, LineState& line)
 
 static FlowContentsIterator::TextFragment splitFragmentToFitLine(FlowContentsIterator::TextFragment& fragmentToSplit, float availableWidth, bool keepAtLeastOneCharacter, const FlowContentsIterator& flowContentsIterator)
 {
-    // Fast path for single char fragments.
-    if (fragmentToSplit.start() + 1 == fragmentToSplit.end()) {
-        if (keepAtLeastOneCharacter)
-            return FlowContentsIterator::TextFragment();
-
-        FlowContentsIterator::TextFragment fragmentForNextLine(fragmentToSplit);
-        // Make it empty fragment.
-        fragmentToSplit = FlowContentsIterator::TextFragment(fragmentToSplit.start(), fragmentToSplit.start(), 0, fragmentToSplit.type());
-        return fragmentForNextLine;
-    }
-    // Simple binary search to find out what fits the current line.
     // FIXME: add surrogate pair support.
-    unsigned left = fragmentToSplit.start();
-    unsigned right = fragmentToSplit.end() - 1; // We can ignore the last character. It surely does not fit.
-    float width = 0;
-    while (left < right) {
-        unsigned middle = (left + right) / 2;
-        width = flowContentsIterator.textWidth(fragmentToSplit.start(), middle + 1, 0);
-        if (availableWidth > width)
-            left = middle + 1;
-        else if (availableWidth < width)
-            right = middle;
-        else {
-            right = middle + 1;
-            break;
-        }
-    }
-
-    if (keepAtLeastOneCharacter && right == fragmentToSplit.start())
-        ++right;
-
-    // Fragment for next line.
-    unsigned nextLineStart = right;
-    unsigned nextLineEnd = fragmentToSplit.end();
-    float nextLineWidth = flowContentsIterator.textWidth(nextLineStart, nextLineEnd, 0);
-
-    unsigned thisLineStart = fragmentToSplit.start();
-    unsigned thisLineEnd = right;
-    ASSERT(thisLineStart <= thisLineEnd);
-    float thisLineWidth = thisLineStart < thisLineEnd ? flowContentsIterator.textWidth(thisLineStart, thisLineEnd, 0) : 0;
-    fragmentToSplit = FlowContentsIterator::TextFragment(thisLineStart, thisLineEnd, thisLineWidth, fragmentToSplit.type(), fragmentToSplit.isCollapsed(), fragmentToSplit.isBreakable());
-    return FlowContentsIterator::TextFragment(nextLineStart, nextLineEnd, nextLineWidth, fragmentToSplit.type(), fragmentToSplit.isCollapsed(), fragmentToSplit.isBreakable());
+    unsigned start = fragmentToSplit.start();
+    auto it = std::upper_bound(begin(fragmentToSplit), end(fragmentToSplit), availableWidth, [&flowContentsIterator, start](float availableWidth, unsigned index) {
+        // FIXME: use the actual left position of the line (instead of 0) to calculated width. It might give false width for tab characters.
+        return availableWidth < flowContentsIterator.textWidth(start, index + 1, 0);
+    });
+    unsigned splitPosition = (*it);
+    if (keepAtLeastOneCharacter && splitPosition == fragmentToSplit.start())
+        ++splitPosition;
+    return fragmentToSplit.split(splitPosition, flowContentsIterator);
 }
 
 static FlowContentsIterator::TextFragment firstFragment(FlowContentsIterator& flowContentsIterator, const LineState& previousLine)
index 0ed6f49..3abd4f8 100644 (file)
@@ -171,7 +171,9 @@ unsigned FlowContentsIterator::findNextNonWhitespacePosition(unsigned position,
 template <typename CharacterType>
 float FlowContentsIterator::runWidth(const String& text, unsigned from, unsigned to, float xPosition) const
 {
-    ASSERT(from < to);
+    ASSERT(from <= to);
+    if (from == to)
+        return 0;
     bool measureWithEndSpace = m_style.collapseWhitespace && to < text.length() && text[to] == ' ';
     if (measureWithEndSpace)
         ++to;
index ec4988f..64e6e21 100644 (file)
@@ -59,7 +59,9 @@ public:
         Type type() const { return m_type; }
         bool isCollapsed() const { return m_isCollapsed; }
         bool isBreakable() const { return m_isBreakable; }
+
         bool isEmpty() const { return start() == end(); }
+        TextFragment split(unsigned splitPosition, const FlowContentsIterator&);
 
     private:
         unsigned m_start { 0 };
@@ -103,6 +105,28 @@ private:
     unsigned m_position { 0 };
 };
 
+inline FlowContentsIterator::TextFragment FlowContentsIterator::TextFragment::split(unsigned splitPosition, const FlowContentsIterator& flowContentsIterator)
+{
+    auto updateFragmentProperties = [&flowContentsIterator] (TextFragment& fragment)
+    {
+        fragment.m_width = 0;
+        if (fragment.start() != fragment.end())
+            fragment.m_width = flowContentsIterator.textWidth(fragment.start(), fragment.end(), 0);
+        if (fragment.start() + 1 > fragment.end())
+            return;
+        fragment.m_isCollapsed = false;
+        fragment.m_isBreakable = false;
+    };
+
+    TextFragment newFragment(*this);
+    m_end = splitPosition;
+    updateFragmentProperties(*this);
+
+    newFragment.m_start = splitPosition;
+    updateFragmentProperties(newFragment);
+    return newFragment;
+}
+
 inline UChar FlowContentsIterator::characterAt(unsigned position) const
 {
     auto& segment = m_flowContents.segmentForPosition(position);