Refactor the treatment of shape-outside objects in float overlapping checks

Source/core/layout/FloatingObjects.cpp

Index: Source/core/layout/FloatingObjects.cpp
diff --git a/Source/core/layout/FloatingObjects.cpp b/Source/core/layout/FloatingObjects.cpp
index 8a256450277ada037dfc732736a7d44c29299003..0bcfb5f6d75175d4111948b84e65000f137baf44 100644
--- a/Source/core/layout/FloatingObjects.cpp
+++ b/Source/core/layout/FloatingObjects.cpp
@@ -29,6 +29,8 @@
 #include "core/layout/LayoutView.h"
 #include "core/layout/shapes/ShapeOutsideInfo.h"
 
+#include <algorithm>
+
 using namespace WTF;
 
 namespace blink {
@@ -100,15 +102,35 @@ PassOwnPtr<FloatingObject> FloatingObject::unsafeClone() const
     return cloneObject.release();
 }
 
+inline static bool rangesIntersect(int floatTop, int floatBottom, int objectTop, int objectBottom)
+{
+    if (objectTop >= floatBottom || objectBottom < floatTop)
+        return false;
+
+    // The top of the object overlaps the float
+    if (objectTop >= floatTop)
+        return true;
+
+    // The object encloses the float
+    if (objectTop < floatTop && objectBottom > floatBottom)
+        return true;
+
+    // The bottom of the object overlaps the float
+    if (objectBottom > objectTop && objectBottom > floatTop && objectBottom <= floatBottom)
+        return true;
+
+    return false;
+}
+
 template <FloatingObject::Type FloatTypeValue>
 class ComputeFloatOffsetAdapter {
 public:
     typedef FloatingObjectInterval IntervalType;
 
-    ComputeFloatOffsetAdapter(const LayoutBlockFlow* layoutObject, int lineTop, int lineBottom, LayoutUnit offset)
+    ComputeFloatOffsetAdapter(const LayoutBlockFlow* layoutObject, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
         : m_layoutObject(layoutObject)
-        , m_lineTop(lineTop)
-        , m_lineBottom(lineBottom)
+        , m_lineTop(roundToInt(lineTop))
+        , m_lineBottom(roundToInt(lineBottom))
         , m_offset(offset)
         , m_outermostFloat(nullptr)
     {
@@ -162,6 +184,72 @@ protected:
     bool updateOffsetIfNeeded(const FloatingObject&) final;
 };
 
+class FindNextFloatLogicalBottomAdapter {
+public:
+    typedef FloatingObjectInterval IntervalType;
+
+    FindNextFloatLogicalBottomAdapter(const LayoutBlockFlow& renderer, LayoutUnit belowLogicalHeight)
+        : m_layoutObject(renderer)
+        , m_belowLogicalHeight(floorToInt(belowLogicalHeight))
+        , m_aboveLogicalHeight(roundToInt(LayoutUnit::max()))
+        , m_nextLogicalBottom()
+        , m_nextShapeLogicalBottom()
+    {
+    }
+
+    int lowValue() const { return m_belowLogicalHeight; }
+    int highValue() const { return m_aboveLogicalHeight; }
+    void collectIfNeeded(const IntervalType&);
+
+    LayoutUnit nextLogicalBottom() { return m_nextLogicalBottom; }
+    LayoutUnit nextShapeLogicalBottom() { return m_nextShapeLogicalBottom; }
+
+private:
+    const LayoutBlockFlow& m_layoutObject;
+    int m_belowLogicalHeight;
+    int m_aboveLogicalHeight;
+    LayoutUnit m_nextLogicalBottom;
+    LayoutUnit m_nextShapeLogicalBottom;
+};
+
+inline void FindNextFloatLogicalBottomAdapter::collectIfNeeded(const IntervalType& interval)
+{
+    const FloatingObject& floatingObject = *(interval.data());
+    if (!rangesIntersect(interval.low(), interval.high(), m_belowLogicalHeight, m_aboveLogicalHeight))
+        return;
+
+    // All the objects returned from the tree should be already placed.
+    ASSERT(floatingObject.isPlaced());
+    ASSERT(rangesIntersect(m_layoutObject.pixelSnappedLogicalTopForFloat(floatingObject), m_layoutObject.pixelSnappedLogicalBottomForFloat(floatingObject), m_belowLogicalHeight, m_aboveLogicalHeight));
+
+    LayoutUnit floatBottom = m_layoutObject.logicalBottomForFloat(floatingObject);
+
+    if (ShapeOutsideInfo* shapeOutside = floatingObject.layoutObject()->shapeOutsideInfo()) {
+        LayoutUnit shapeBottom = m_layoutObject.logicalTopForFloat(floatingObject) + m_layoutObject.marginBeforeForChild(*floatingObject.layoutObject()) + shapeOutside->shapeLogicalBottom();
+        // Use the shapeBottom unless it extends outside of the margin box, in which case it is clipped.
+        m_nextShapeLogicalBottom = m_nextShapeLogicalBottom ? std::min(shapeBottom, floatBottom) : shapeBottom;
+    } else {
+        m_nextShapeLogicalBottom = m_nextShapeLogicalBottom ? std::min(m_nextShapeLogicalBottom, floatBottom) : floatBottom;
+    }
+
+    m_nextLogicalBottom = m_nextLogicalBottom ? std::min(m_nextLogicalBottom, floatBottom) : floatBottom;
+}
+
+LayoutUnit FloatingObjects::findNextFloatLogicalBottomBelow(LayoutUnit logicalHeight)
+{
+    FindNextFloatLogicalBottomAdapter adapter(*m_layoutObject, logicalHeight);
+    placedFloatsTree().allOverlapsWithAdapter(adapter);
+
+    return adapter.nextShapeLogicalBottom();
+}
+
+LayoutUnit FloatingObjects::findNextFloatLogicalBottomBelowForBlock(LayoutUnit logicalHeight)
+{
+    FindNextFloatLogicalBottomAdapter adapter(*m_layoutObject, logicalHeight);
+    placedFloatsTree().allOverlapsWithAdapter(adapter);
+
+    return adapter.nextLogicalBottom();
+}
 
 FloatingObjects::~FloatingObjects()
 {
@@ -402,8 +490,7 @@ void FloatingObjects::computePlacedFloatsTree()
 
 LayoutUnit FloatingObjects::logicalLeftOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
 {
-    int logicalTopAsInt = roundToInt(logicalTop);
-    ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatLeft> adapter(m_layoutObject, logicalTopAsInt, logicalTopAsInt, fixedOffset);
+    ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatLeft> adapter(m_layoutObject, logicalTop, logicalTop, fixedOffset);
     placedFloatsTree().allOverlapsWithAdapter(adapter);
 
     if (heightRemaining)
@@ -414,8 +501,7 @@ LayoutUnit FloatingObjects::logicalLeftOffsetForPositioningFloat(LayoutUnit fixe
 
 LayoutUnit FloatingObjects::logicalRightOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
 {
-    int logicalTopAsInt = roundToInt(logicalTop);
-    ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatRight> adapter(m_layoutObject, logicalTopAsInt, logicalTopAsInt, fixedOffset);
+    ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatRight> adapter(m_layoutObject, logicalTop, logicalTop, fixedOffset);
     placedFloatsTree().allOverlapsWithAdapter(adapter);
 
     if (heightRemaining)
@@ -426,7 +512,7 @@ LayoutUnit FloatingObjects::logicalRightOffsetForPositioningFloat(LayoutUnit fix
 
 LayoutUnit FloatingObjects::logicalLeftOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
 {
-    ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatLeft> adapter(m_layoutObject, roundToInt(logicalTop), roundToInt(logicalTop + logicalHeight), fixedOffset);
+    ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatLeft> adapter(m_layoutObject, logicalTop, logicalTop + logicalHeight, fixedOffset);
     placedFloatsTree().allOverlapsWithAdapter(adapter);
 
     return adapter.offset();
@@ -434,7 +520,7 @@ LayoutUnit FloatingObjects::logicalLeftOffset(LayoutUnit fixedOffset, LayoutUnit
 
 LayoutUnit FloatingObjects::logicalRightOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
 {
-    ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatRight> adapter(m_layoutObject, roundToInt(logicalTop), roundToInt(logicalTop + logicalHeight), fixedOffset);
+    ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatRight> adapter(m_layoutObject, logicalTop, logicalTop + logicalHeight, fixedOffset);
     placedFloatsTree().allOverlapsWithAdapter(adapter);
 
     return std::min(fixedOffset, adapter.offset());
@@ -446,26 +532,6 @@ FloatingObjects::FloatBottomCachedValue::FloatBottomCachedValue()
 {
 }
 
-inline static bool rangesIntersect(int floatTop, int floatBottom, int objectTop, int objectBottom)
-{
-    if (objectTop >= floatBottom || objectBottom < floatTop)
-        return false;
-
-    // The top of the object overlaps the float
-    if (objectTop >= floatTop)
-        return true;
-
-    // The object encloses the float
-    if (objectTop < floatTop && objectBottom > floatBottom)
-        return true;
-
-    // The bottom of the object overlaps the float
-    if (objectBottom > objectTop && objectBottom > floatTop && objectBottom <= floatBottom)
-        return true;
-
-    return false;
-}
-
 template<>
 inline bool ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
 {