Optimize FloatIntervalSearchAdapter::collectIfNeeded
authorbjonesbe@adobe.com <bjonesbe@adobe.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 26 Aug 2013 21:35:35 +0000 (21:35 +0000)
committerbjonesbe@adobe.com <bjonesbe@adobe.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 26 Aug 2013 21:35:35 +0000 (21:35 +0000)
https://bugs.webkit.org/show_bug.cgi?id=120237

Reviewed by David Hyatt.

Source/WebCore:

This is a port of 3 Blink patches:
https://codereview.chromium.org/22463002 (By shatch@chromium.org)
https://chromiumcodereview.appspot.com/22909005 (By me)
https://chromiumcodereview.appspot.com/23084002 (By me)

shatch optimized FloatIntervalSearchAdapter by having it store the
outermost float instead of making a bunch of calls to
logical(Left/Right/Bottom)ForFloat, and then only making that call
once when heightRemaining needs to be computed.

I noticed that now we were storing both the last float encountered and
the outermost float, and that the behavior for shape-outside wasn't
significantly changed by using the outermost float instead of the last
float encountered (and in most cases, using the outermost float gives
more reasonable behavior). Since this isn't covered in the spec yet, I
changed shape-outside to use the outermost float, making it so that we
only need to store one float pointer when walking the placed floats
tree, and keeping the performance win.

Also while changing updateOffsetIfNeeded, removed const, since that is
a lie. Nothing about that method is const.

Test: fast/shapes/shape-outside-floats/shape-outside-floats-outermost.html

* rendering/RenderBlock.cpp:
(WebCore::::updateOffsetIfNeeded):
(WebCore::::collectIfNeeded):
(WebCore::::getHeightRemaining):
(WebCore::RenderBlock::logicalLeftFloatOffsetForLine):
(WebCore::RenderBlock::logicalRightFloatOffsetForLine):
* rendering/RenderBlock.h:
(WebCore::RenderBlock::FloatIntervalSearchAdapter::FloatIntervalSearchAdapter):
(WebCore::RenderBlock::FloatIntervalSearchAdapter::outermostFloat):

LayoutTests:

Test shape-outside behavior when there is more than one float on a
given line.

* fast/shapes/shape-outside-floats/shape-outside-floats-outermost-expected.html: Added.
* fast/shapes/shape-outside-floats/shape-outside-floats-outermost.html: Added.

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

LayoutTests/ChangeLog
LayoutTests/fast/shapes/shape-outside-floats/shape-outside-floats-outermost-expected.html [new file with mode: 0644]
LayoutTests/fast/shapes/shape-outside-floats/shape-outside-floats-outermost.html [new file with mode: 0644]
Source/WebCore/ChangeLog
Source/WebCore/rendering/RenderBlock.cpp
Source/WebCore/rendering/RenderBlock.h

index c5232ec..25a5bdc 100644 (file)
@@ -1,3 +1,16 @@
+2013-08-26  Bem Jones-Bey  <bjonesbe@adobe.com>
+
+        Optimize FloatIntervalSearchAdapter::collectIfNeeded
+        https://bugs.webkit.org/show_bug.cgi?id=120237
+
+        Reviewed by David Hyatt.
+
+        Test shape-outside behavior when there is more than one float on a
+        given line.
+
+        * fast/shapes/shape-outside-floats/shape-outside-floats-outermost-expected.html: Added.
+        * fast/shapes/shape-outside-floats/shape-outside-floats-outermost.html: Added.
+
 2013-08-26  Mark Hahnenberg  <mhahnenberg@apple.com>
 
         JSObject::putDirectIndexBeyondVectorLengthWithArrayStorage does a check on the length of the ArrayStorage after possible reallocing it
diff --git a/LayoutTests/fast/shapes/shape-outside-floats/shape-outside-floats-outermost-expected.html b/LayoutTests/fast/shapes/shape-outside-floats/shape-outside-floats-outermost-expected.html
new file mode 100644 (file)
index 0000000..c95e346
--- /dev/null
@@ -0,0 +1,24 @@
+<!DOCTYPE html>
+<style>
+    .container {
+        line-height: 100px;
+        font: 100px/1 Ahem;
+    }
+    .short {
+        float: left;
+        width: 50px;
+        height: 20px;
+        clear: left;
+        margin-bottom: 10px;
+        background-color: black;
+    }
+</style>
+<body>
+    <div class="container">
+        <div class="short"></div>
+        <div class="short"></div>
+        <div class="short"></div>
+        XXXX
+    </div>
+</body>
+
diff --git a/LayoutTests/fast/shapes/shape-outside-floats/shape-outside-floats-outermost.html b/LayoutTests/fast/shapes/shape-outside-floats/shape-outside-floats-outermost.html
new file mode 100644 (file)
index 0000000..db05c34
--- /dev/null
@@ -0,0 +1,32 @@
+<!DOCTYPE html>
+<style>
+    .container {
+        line-height: 100px;
+        font: 100px/1 Ahem;
+    }
+    .long {
+        float: left;
+        width: 100px;
+        height: 20px;
+        margin-bottom: 10px;
+        background-color: black;
+        -webkit-shape-outside: rectangle(0, 0, 50%, 100%);
+    }
+    .short {
+        float: left;
+        width: 50px;
+        height: 20px;
+        clear: left;
+        margin-bottom: 10px;
+        background-color: black;
+    }
+</style>
+<body>
+    <div class="container">
+        <div class="long"></div>
+        <div class="short"></div>
+        <div class="short"></div>
+        XXXX
+    </div>
+</body>
+
index b80d9c5..2ac17c2 100644 (file)
@@ -1,3 +1,44 @@
+2013-08-26  Bem Jones-Bey  <bjonesbe@adobe.com>
+
+        Optimize FloatIntervalSearchAdapter::collectIfNeeded
+        https://bugs.webkit.org/show_bug.cgi?id=120237
+
+        Reviewed by David Hyatt.
+
+        This is a port of 3 Blink patches:
+        https://codereview.chromium.org/22463002 (By shatch@chromium.org)
+        https://chromiumcodereview.appspot.com/22909005 (By me)
+        https://chromiumcodereview.appspot.com/23084002 (By me)
+
+        shatch optimized FloatIntervalSearchAdapter by having it store the
+        outermost float instead of making a bunch of calls to
+        logical(Left/Right/Bottom)ForFloat, and then only making that call
+        once when heightRemaining needs to be computed.
+
+        I noticed that now we were storing both the last float encountered and
+        the outermost float, and that the behavior for shape-outside wasn't
+        significantly changed by using the outermost float instead of the last
+        float encountered (and in most cases, using the outermost float gives
+        more reasonable behavior). Since this isn't covered in the spec yet, I
+        changed shape-outside to use the outermost float, making it so that we
+        only need to store one float pointer when walking the placed floats
+        tree, and keeping the performance win.
+
+        Also while changing updateOffsetIfNeeded, removed const, since that is
+        a lie. Nothing about that method is const.
+
+        Test: fast/shapes/shape-outside-floats/shape-outside-floats-outermost.html
+
+        * rendering/RenderBlock.cpp:
+        (WebCore::::updateOffsetIfNeeded):
+        (WebCore::::collectIfNeeded):
+        (WebCore::::getHeightRemaining):
+        (WebCore::RenderBlock::logicalLeftFloatOffsetForLine):
+        (WebCore::RenderBlock::logicalRightFloatOffsetForLine):
+        * rendering/RenderBlock.h:
+        (WebCore::RenderBlock::FloatIntervalSearchAdapter::FloatIntervalSearchAdapter):
+        (WebCore::RenderBlock::FloatIntervalSearchAdapter::outermostFloat):
+
 2013-08-26  Alexey Proskuryakov  <ap@apple.com>
 
         [Mac] can-read-in-dragstart-event.html and can-read-in-copy-and-cut-events.html fail
index 69139a3..f7b4a11 100644 (file)
@@ -4439,27 +4439,29 @@ inline static bool rangesIntersect(int floatTop, int floatBottom, int objectTop,
 }
 
 template<>
-inline bool RenderBlock::FloatIntervalSearchAdapter<RenderBlock::FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject* floatingObject) const
+inline bool RenderBlock::FloatIntervalSearchAdapter<RenderBlock::FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject* floatingObject)
 {
-    if (m_renderer->logicalRightForFloat(floatingObject) > m_offset) {
-        m_offset = m_renderer->logicalRightForFloat(floatingObject);
+    LayoutUnit logicalRight = m_renderer->logicalRightForFloat(floatingObject);
+    if (logicalRight > m_offset) {
+        m_offset = logicalRight;
         return true;
     }
     return false;
 }
 
 template<>
-inline bool RenderBlock::FloatIntervalSearchAdapter<RenderBlock::FloatingObject::FloatRight>::updateOffsetIfNeeded(const FloatingObject* floatingObject) const
+inline bool RenderBlock::FloatIntervalSearchAdapter<RenderBlock::FloatingObject::FloatRight>::updateOffsetIfNeeded(const FloatingObject* floatingObject)
 {
-    if (m_renderer->logicalLeftForFloat(floatingObject) < m_offset) {
-        m_offset = m_renderer->logicalLeftForFloat(floatingObject);
+    LayoutUnit logicalLeft = m_renderer->logicalLeftForFloat(floatingObject);
+    if (logicalLeft < m_offset) {
+        m_offset = logicalLeft;
         return true;
     }
     return false;
 }
 
 template <RenderBlock::FloatingObject::Type FloatTypeValue>
-inline void RenderBlock::FloatIntervalSearchAdapter<FloatTypeValue>::collectIfNeeded(const IntervalType& interval) const
+inline void RenderBlock::FloatIntervalSearchAdapter<FloatTypeValue>::collectIfNeeded(const IntervalType& interval)
 {
     const FloatingObject* floatingObject = interval.data();
     if (floatingObject->type() != FloatTypeValue || !rangesIntersect(interval.low(), interval.high(), m_lowValue, m_highValue))
@@ -4470,12 +4472,14 @@ inline void RenderBlock::FloatIntervalSearchAdapter<FloatTypeValue>::collectIfNe
     ASSERT(rangesIntersect(m_renderer->pixelSnappedLogicalTopForFloat(floatingObject), m_renderer->pixelSnappedLogicalBottomForFloat(floatingObject), m_lowValue, m_highValue));
 
     bool floatIsNewExtreme = updateOffsetIfNeeded(floatingObject);
-    if (floatIsNewExtreme && m_heightRemaining)
-        *m_heightRemaining = m_renderer->logicalBottomForFloat(floatingObject) - m_lowValue;
+    if (floatIsNewExtreme)
+        m_outermostFloat = floatingObject;
+}
 
-#if ENABLE(CSS_SHAPES)
-    m_last = floatingObject;
-#endif
+template <RenderBlock::FloatingObject::Type FloatTypeValue>
+LayoutUnit RenderBlock::FloatIntervalSearchAdapter<FloatTypeValue>::getHeightRemaining() const
+{
+    return m_outermostFloat ? m_renderer->logicalBottomForFloat(m_outermostFloat) - m_lowValue : LayoutUnit(1);
 }
 
 LayoutUnit RenderBlock::textIndentOffset() const
@@ -4515,17 +4519,17 @@ LayoutUnit RenderBlock::logicalLeftFloatOffsetForLine(LayoutUnit logicalTop, Lay
 #endif
     LayoutUnit left = fixedOffset;
     if (m_floatingObjects && m_floatingObjects->hasLeftObjects()) {
-        if (heightRemaining)
-            *heightRemaining = 1;
-
-        FloatIntervalSearchAdapter<FloatingObject::FloatLeft> adapter(this, roundToInt(logicalTop), roundToInt(logicalTop + logicalHeight), left, heightRemaining);
+        FloatIntervalSearchAdapter<FloatingObject::FloatLeft> adapter(this, roundToInt(logicalTop), roundToInt(logicalTop + logicalHeight), left);
         m_floatingObjects->placedFloatsTree().allOverlapsWithAdapter(adapter);
 
+        if (heightRemaining)
+            *heightRemaining = adapter.getHeightRemaining();
+
 #if ENABLE(CSS_SHAPES)
-        const FloatingObject* lastFloat = adapter.lastFloat();
-        if (offsetMode == ShapeOutsideFloatShapeOffset && lastFloat) {
-            if (ShapeOutsideInfo* shapeOutside = lastFloat->renderer()->shapeOutsideInfo()) {
-                shapeOutside->computeSegmentsForContainingBlockLine(logicalTop, logicalTopForFloat(lastFloat), logicalHeight);
+        const FloatingObject* outermostFloat = adapter.outermostFloat();
+        if (offsetMode == ShapeOutsideFloatShapeOffset && outermostFloat) {
+            if (ShapeOutsideInfo* shapeOutside = outermostFloat->renderer()->shapeOutsideInfo()) {
+                shapeOutside->computeSegmentsForContainingBlockLine(logicalTop, logicalTopForFloat(outermostFloat), logicalHeight);
                 left += shapeOutside->rightSegmentMarginBoxDelta();
             }
         }
@@ -4582,18 +4586,18 @@ LayoutUnit RenderBlock::logicalRightFloatOffsetForLine(LayoutUnit logicalTop, La
 #endif
     LayoutUnit right = fixedOffset;
     if (m_floatingObjects && m_floatingObjects->hasRightObjects()) {
-        if (heightRemaining)
-            *heightRemaining = 1;
-
         LayoutUnit rightFloatOffset = fixedOffset;
-        FloatIntervalSearchAdapter<FloatingObject::FloatRight> adapter(this, roundToInt(logicalTop), roundToInt(logicalTop + logicalHeight), rightFloatOffset, heightRemaining);
+        FloatIntervalSearchAdapter<FloatingObject::FloatRight> adapter(this, roundToInt(logicalTop), roundToInt(logicalTop + logicalHeight), rightFloatOffset);
         m_floatingObjects->placedFloatsTree().allOverlapsWithAdapter(adapter);
 
+        if (heightRemaining)
+            *heightRemaining = adapter.getHeightRemaining();
+
 #if ENABLE(CSS_SHAPES)
-        const FloatingObject* lastFloat = adapter.lastFloat();
-        if (offsetMode == ShapeOutsideFloatShapeOffset && lastFloat) {
-            if (ShapeOutsideInfo* shapeOutside = lastFloat->renderer()->shapeOutsideInfo()) {
-                shapeOutside->computeSegmentsForContainingBlockLine(logicalTop, logicalTopForFloat(lastFloat), logicalHeight);
+        const FloatingObject* outermostFloat = adapter.outermostFloat();
+        if (offsetMode == ShapeOutsideFloatShapeOffset && outermostFloat) {
+            if (ShapeOutsideInfo* shapeOutside = outermostFloat->renderer()->shapeOutsideInfo()) {
+                shapeOutside->computeSegmentsForContainingBlockLine(logicalTop, logicalTopForFloat(outermostFloat), logicalHeight);
                 rightFloatOffset += shapeOutside->leftSegmentMarginBoxDelta();
             }
         }
index 242cce4..03e07a0 100644 (file)
@@ -1208,48 +1208,37 @@ protected:
     public:
         typedef FloatingObjectInterval IntervalType;
         
-        FloatIntervalSearchAdapter(const RenderBlock* renderer, int lowValue, int highValue, LayoutUnit& offset, LayoutUnit* heightRemaining)
+        FloatIntervalSearchAdapter(const RenderBlock* renderer, int lowValue, int highValue, LayoutUnit& offset)
             : m_renderer(renderer)
             , m_lowValue(lowValue)
             , m_highValue(highValue)
             , m_offset(offset)
-            , m_heightRemaining(heightRemaining)
-#if ENABLE(CSS_SHAPES)
-            , m_last(0)
-#endif
+            , m_outermostFloat(0)
         {
         }
         
         inline int lowValue() const { return m_lowValue; }
         inline int highValue() const { return m_highValue; }
-        void collectIfNeeded(const IntervalType&) const;
+        void collectIfNeeded(const IntervalType&);
 
 #if ENABLE(CSS_SHAPES)
         // When computing the offset caused by the floats on a given line, if
         // the outermost float on that line has a shape-outside, the inline
         // content that butts up against that float must be positioned using
         // the contours of the shape, not the margin box of the float.
-        // We save the last float encountered so that the offset can be
-        // computed correctly by the code using this adapter.
-        const FloatingObject* lastFloat() const { return m_last; }
+        const FloatingObject* outermostFloat() const { return m_outermostFloat; }
 #endif
 
+        LayoutUnit getHeightRemaining() const;
+
     private:
-        bool updateOffsetIfNeeded(const FloatingObject*) const;
+        bool updateOffsetIfNeeded(const FloatingObject*);
 
         const RenderBlock* m_renderer;
         int m_lowValue;
         int m_highValue;
         LayoutUnit& m_offset;
-        LayoutUnit* m_heightRemaining;
-#if ENABLE(CSS_SHAPES)
-        // This member variable is mutable because the collectIfNeeded method
-        // is declared as const, even though it doesn't actually respect that
-        // contract. It modifies other member variables via loopholes in the
-        // const behavior. Instead of using loopholes, I decided it was better
-        // to make the fact that this is modified in a const method explicit.
-        mutable const FloatingObject* m_last;
-#endif
+        const FloatingObject* m_outermostFloat;
     };
 
     void createFloatingObjects();