/*
 * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
 *           (C) 1999 Antti Koivisto (koivisto@kde.org)
 *           (C) 2007 David Smith (catfish.man@gmail.com)
 * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 Apple Inc. All rights reserved.
 * Copyright (C) Research In Motion Limited 2010. All rights reserved.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public License
 * along with this library; see the file COPYING.LIB.  If not, write to
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
 */

#include "core/layout/FloatingObjects.h"

#include "core/layout/LayoutBlockFlow.h"
#include "core/layout/LayoutBox.h"
#include "core/layout/LayoutView.h"
#include "core/layout/api/LineLayoutBlockFlow.h"
#include "core/layout/shapes/ShapeOutsideInfo.h"
#include "core/paint/PaintLayer.h"
#include "platform/RuntimeEnabledFeatures.h"
#include "wtf/PtrUtil.h"
#include <algorithm>
#include <memory>

using namespace WTF;

namespace blink {

struct SameSizeAsFloatingObject {
    void* pointers[2];
    LayoutRect rect;
    uint32_t bitfields : 8;
};

static_assert(sizeof(FloatingObject) == sizeof(SameSizeAsFloatingObject), "FloatingObject should stay small");

FloatingObject::FloatingObject(LayoutBox* layoutObject)
    : m_layoutObject(layoutObject)
    , m_originatingLine(nullptr)
    , m_shouldPaint(true)
    , m_isDescendant(false)
    , m_isPlaced(false)
    , m_isLowestNonOverhangingFloatInChild(false)
#if ENABLE(ASSERT)
    , m_isInPlacedTree(false)
#endif
{
    EFloat type = layoutObject->style()->floating();
    DCHECK_NE(type, EFloat::None);
    if (type == EFloat::Left)
        m_type = FloatLeft;
    else if (type == EFloat::Right)
        m_type = FloatRight;
}

FloatingObject::FloatingObject(LayoutBox* layoutObject, Type type, const LayoutRect& frameRect, bool shouldPaint, bool isDescendant, bool isLowestNonOverhangingFloatInChild, bool performingUnsafeClone)
    : m_layoutObject(layoutObject)
    , m_originatingLine(nullptr)
    , m_frameRect(frameRect)
    , m_type(type)
    , m_isDescendant(isDescendant)
    , m_isPlaced(true)
    , m_isLowestNonOverhangingFloatInChild(isLowestNonOverhangingFloatInChild)
#if ENABLE(ASSERT)
    , m_isInPlacedTree(false)
#endif
{
    m_shouldPaint = shouldPaint;
    // TODO(chrishtr): Avoid the following hack when performing an unsafe clone.
    // This avoids a use-after-free bug due to the fact that we sometimes fail to remove
    // floats from their container when detaching (crbug.com/619380). This is actually a bug in the
    // floats detach machinery, which needs to be fixed, in which case this workaround can be removed.
    // In any case, it should be safe because moving floats from one owner to another should cause layout,
    // which will in turn update the m_shouldPaint property.
    if (!performingUnsafeClone)
        m_shouldPaint = m_shouldPaint || shouldPaintForCompositedLayoutPart();
}

bool FloatingObject::shouldPaintForCompositedLayoutPart()
{
    // HACK: only non-self-painting floats should paint. However, due to the fundamental compositing bug, some LayoutPart objects
    // may become self-painting due to being composited. This leads to a chicken-egg issue because layout may not depend on compositing.
    // If this is the case, set shouldPaint() to true even if the layer is technically self-painting. This lets the float which contains
    // a LayoutPart start painting as soon as it stops being composited, without having to re-layout the float.
    // This hack can be removed after SPv2.
    return m_layoutObject->layer() && m_layoutObject->layer()->isSelfPaintingOnlyBecauseIsCompositedPart() && !RuntimeEnabledFeatures::slimmingPaintV2Enabled();
}

std::unique_ptr<FloatingObject> FloatingObject::create(LayoutBox* layoutObject)
{
    std::unique_ptr<FloatingObject> newObj = wrapUnique(new FloatingObject(layoutObject));

    // If a layer exists, the float will paint itself. Otherwise someone else will.
    newObj->setShouldPaint(!layoutObject->hasSelfPaintingLayer() || newObj->shouldPaintForCompositedLayoutPart());

    newObj->setIsDescendant(true);

    return newObj;
}

bool FloatingObject::shouldPaint() const
{
    return m_shouldPaint && !m_layoutObject->hasSelfPaintingLayer();
}

std::unique_ptr<FloatingObject> FloatingObject::copyToNewContainer(LayoutSize offset, bool shouldPaint, bool isDescendant) const
{
    return wrapUnique(new FloatingObject(layoutObject(), getType(), LayoutRect(frameRect().location() - offset, frameRect().size()), shouldPaint, isDescendant, isLowestNonOverhangingFloatInChild()));
}

std::unique_ptr<FloatingObject> FloatingObject::unsafeClone() const
{
    std::unique_ptr<FloatingObject> cloneObject = wrapUnique(new FloatingObject(layoutObject(), getType(), m_frameRect, m_shouldPaint, m_isDescendant, false, true));
    cloneObject->m_isPlaced = m_isPlaced;
    return cloneObject;
}

template <FloatingObject::Type FloatTypeValue>
class ComputeFloatOffsetAdapter {
public:
    typedef FloatingObjectInterval IntervalType;

    ComputeFloatOffsetAdapter(const LayoutBlockFlow* layoutObject, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
        : m_layoutObject(layoutObject)
        , m_lineTop(lineTop)
        , m_lineBottom(lineBottom)
        , m_offset(offset)
        , m_outermostFloat(nullptr)
    {
    }

    virtual ~ComputeFloatOffsetAdapter() { }

    LayoutUnit lowValue() const { return m_lineTop; }
    LayoutUnit highValue() const { return m_lineBottom; }
    void collectIfNeeded(const IntervalType&);

    LayoutUnit offset() const { return m_offset; }

protected:
    virtual bool updateOffsetIfNeeded(const FloatingObject&) = 0;

    const LayoutBlockFlow* m_layoutObject;
    LayoutUnit m_lineTop;
    LayoutUnit m_lineBottom;
    LayoutUnit m_offset;
    const FloatingObject* m_outermostFloat;
};

template <FloatingObject::Type FloatTypeValue>
class ComputeFloatOffsetForFloatLayoutAdapter : public ComputeFloatOffsetAdapter<FloatTypeValue> {
public:
    ComputeFloatOffsetForFloatLayoutAdapter(const LayoutBlockFlow* layoutObject, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
        : ComputeFloatOffsetAdapter<FloatTypeValue>(layoutObject, lineTop, lineBottom, offset)
    {
    }

    ~ComputeFloatOffsetForFloatLayoutAdapter() override { }

    LayoutUnit heightRemaining() const;

protected:
    bool updateOffsetIfNeeded(const FloatingObject&) final;
};

template <FloatingObject::Type FloatTypeValue>
class ComputeFloatOffsetForLineLayoutAdapter : public ComputeFloatOffsetAdapter<FloatTypeValue> {
public:
    ComputeFloatOffsetForLineLayoutAdapter(const LayoutBlockFlow* layoutObject, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
        : ComputeFloatOffsetAdapter<FloatTypeValue>(layoutObject, lineTop, lineBottom, offset)
    {
    }

    ~ComputeFloatOffsetForLineLayoutAdapter() override { }

protected:
    bool updateOffsetIfNeeded(const FloatingObject&) final;
};

class FindNextFloatLogicalBottomAdapter {
public:
    typedef FloatingObjectInterval IntervalType;

    FindNextFloatLogicalBottomAdapter(const LayoutBlockFlow& renderer, LayoutUnit belowLogicalHeight)
        : m_layoutObject(renderer)
        , m_belowLogicalHeight(belowLogicalHeight)
        , m_aboveLogicalHeight(LayoutUnit::max())
        , m_nextLogicalBottom()
        , m_nextShapeLogicalBottom()
    {
    }

    LayoutUnit lowValue() const { return m_belowLogicalHeight; }
    LayoutUnit highValue() const { return m_aboveLogicalHeight; }
    void collectIfNeeded(const IntervalType&);

    LayoutUnit nextLogicalBottom() { return m_nextLogicalBottom; }
    LayoutUnit nextShapeLogicalBottom() { return m_nextShapeLogicalBottom; }

private:
    const LayoutBlockFlow& m_layoutObject;
    LayoutUnit m_belowLogicalHeight;
    LayoutUnit m_aboveLogicalHeight;
    LayoutUnit m_nextLogicalBottom;
    LayoutUnit m_nextShapeLogicalBottom;
};

inline static bool rangesIntersect(LayoutUnit floatTop, LayoutUnit floatBottom, LayoutUnit objectTop, LayoutUnit 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;
}

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.logicalTopForFloat(floatingObject), m_layoutObject.logicalBottomForFloat(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()
{
}
void FloatingObjects::clearLineBoxTreePointers()
{
    // Clear references to originating lines, since the lines are being deleted
    FloatingObjectSetIterator end = m_set.end();
    for (FloatingObjectSetIterator it = m_set.begin(); it != end; ++it) {
        ASSERT(!((*it)->originatingLine()) || (*it)->originatingLine()->getLineLayoutItem().isEqual(m_layoutObject));
        (*it)->setOriginatingLine(nullptr);
    }
}

FloatingObjects::FloatingObjects(const LayoutBlockFlow* layoutObject, bool horizontalWritingMode)
    : m_placedFloatsTree(UninitializedTree)
    , m_leftObjectsCount(0)
    , m_rightObjectsCount(0)
    , m_horizontalWritingMode(horizontalWritingMode)
    , m_layoutObject(layoutObject)
    , m_cachedHorizontalWritingMode(false)
{
}

void FloatingObjects::clear()
{
    m_set.clear();
    m_placedFloatsTree.clear();
    m_leftObjectsCount = 0;
    m_rightObjectsCount = 0;
    markLowestFloatLogicalBottomCacheAsDirty();
}

LayoutUnit FloatingObjects::lowestFloatLogicalBottom(FloatingObject::Type floatType)
{
    bool isInHorizontalWritingMode = m_horizontalWritingMode;
    if (floatType != FloatingObject::FloatLeftRight) {
        if (hasLowestFloatLogicalBottomCached(isInHorizontalWritingMode, floatType))
            return getCachedlowestFloatLogicalBottom(floatType);
    } else {
        if (hasLowestFloatLogicalBottomCached(isInHorizontalWritingMode, FloatingObject::FloatLeft) && hasLowestFloatLogicalBottomCached(isInHorizontalWritingMode, FloatingObject::FloatRight)) {
            return std::max(getCachedlowestFloatLogicalBottom(FloatingObject::FloatLeft),
                getCachedlowestFloatLogicalBottom(FloatingObject::FloatRight));
        }
    }

    LayoutUnit lowestFloatBottom;
    const FloatingObjectSet& floatingObjectSet = set();
    FloatingObjectSetIterator end = floatingObjectSet.end();
    if (floatType == FloatingObject::FloatLeftRight) {
        FloatingObject* lowestFloatingObjectLeft = nullptr;
        FloatingObject* lowestFloatingObjectRight = nullptr;
        LayoutUnit lowestFloatBottomLeft;
        LayoutUnit lowestFloatBottomRight;
        for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
            FloatingObject& floatingObject = *it->get();
            if (floatingObject.isPlaced()) {
                FloatingObject::Type curType = floatingObject.getType();
                LayoutUnit curFloatLogicalBottom = m_layoutObject->logicalBottomForFloat(floatingObject);
                if (curType & FloatingObject::FloatLeft && curFloatLogicalBottom > lowestFloatBottomLeft) {
                    lowestFloatBottomLeft = curFloatLogicalBottom;
                    lowestFloatingObjectLeft = &floatingObject;
                }
                if (curType & FloatingObject::FloatRight && curFloatLogicalBottom > lowestFloatBottomRight) {
                    lowestFloatBottomRight = curFloatLogicalBottom;
                    lowestFloatingObjectRight = &floatingObject;
                }
            }
        }
        lowestFloatBottom = std::max(lowestFloatBottomLeft, lowestFloatBottomRight);
        setCachedLowestFloatLogicalBottom(isInHorizontalWritingMode, FloatingObject::FloatLeft, lowestFloatingObjectLeft);
        setCachedLowestFloatLogicalBottom(isInHorizontalWritingMode, FloatingObject::FloatRight, lowestFloatingObjectRight);
    } else {
        FloatingObject* lowestFloatingObject = nullptr;
        for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
            FloatingObject& floatingObject = *it->get();
            if (floatingObject.isPlaced() && floatingObject.getType() == floatType) {
                if (m_layoutObject->logicalBottomForFloat(floatingObject) > lowestFloatBottom) {
                    lowestFloatingObject = &floatingObject;
                    lowestFloatBottom = m_layoutObject->logicalBottomForFloat(floatingObject);
                }
            }
        }
        setCachedLowestFloatLogicalBottom(isInHorizontalWritingMode, floatType, lowestFloatingObject);
    }

    return lowestFloatBottom;
}

bool FloatingObjects::hasLowestFloatLogicalBottomCached(bool isHorizontal, FloatingObject::Type type) const
{
    int floatIndex = static_cast<int>(type) - 1;
    ASSERT(floatIndex < static_cast<int>(sizeof(m_lowestFloatBottomCache) / sizeof(FloatBottomCachedValue)));
    ASSERT(floatIndex >= 0);
    return (m_cachedHorizontalWritingMode == isHorizontal && !m_lowestFloatBottomCache[floatIndex].dirty);
}

LayoutUnit FloatingObjects::getCachedlowestFloatLogicalBottom(FloatingObject::Type type) const
{
    int floatIndex = static_cast<int>(type) - 1;
    ASSERT(floatIndex < static_cast<int>(sizeof(m_lowestFloatBottomCache) / sizeof(FloatBottomCachedValue)));
    ASSERT(floatIndex >= 0);
    if (!m_lowestFloatBottomCache[floatIndex].floatingObject)
        return LayoutUnit();
    return m_layoutObject->logicalBottomForFloat(*m_lowestFloatBottomCache[floatIndex].floatingObject);
}

void FloatingObjects::setCachedLowestFloatLogicalBottom(bool isHorizontal, FloatingObject::Type type, FloatingObject* floatingObject)
{
    int floatIndex = static_cast<int>(type) - 1;
    ASSERT(floatIndex < static_cast<int>(sizeof(m_lowestFloatBottomCache) / sizeof(FloatBottomCachedValue)));
    ASSERT(floatIndex >= 0);
    m_cachedHorizontalWritingMode = isHorizontal;
    m_lowestFloatBottomCache[floatIndex].floatingObject = floatingObject;
    m_lowestFloatBottomCache[floatIndex].dirty = false;
}

FloatingObject* FloatingObjects::lowestFloatingObject() const
{
    bool isInHorizontalWritingMode = m_horizontalWritingMode;
    if (!hasLowestFloatLogicalBottomCached(isInHorizontalWritingMode, FloatingObject::FloatLeft) && !hasLowestFloatLogicalBottomCached(isInHorizontalWritingMode, FloatingObject::FloatRight))
        return nullptr;
    FloatingObject* lowestLeftObject = m_lowestFloatBottomCache[0].floatingObject;
    FloatingObject* lowestRightObject = m_lowestFloatBottomCache[1].floatingObject;
    LayoutUnit lowestFloatBottomLeft = lowestLeftObject ? m_layoutObject->logicalBottomForFloat(*lowestLeftObject) : LayoutUnit();
    LayoutUnit lowestFloatBottomRight = lowestRightObject ? m_layoutObject->logicalBottomForFloat(*lowestRightObject) : LayoutUnit();

    if (lowestFloatBottomLeft > lowestFloatBottomRight)
        return lowestLeftObject;
    return lowestRightObject;
}

void FloatingObjects::markLowestFloatLogicalBottomCacheAsDirty()
{
    for (size_t i = 0; i < sizeof(m_lowestFloatBottomCache) / sizeof(FloatBottomCachedValue); ++i)
        m_lowestFloatBottomCache[i].dirty = true;
}

void FloatingObjects::moveAllToFloatInfoMap(LayoutBoxToFloatInfoMap& map)
{
    while (!m_set.isEmpty()) {
        std::unique_ptr<FloatingObject> floatingObject = m_set.takeFirst();
        LayoutBox* layoutObject = floatingObject->layoutObject();
        map.add(layoutObject, std::move(floatingObject));
    }
    clear();
}

inline void FloatingObjects::increaseObjectsCount(FloatingObject::Type type)
{
    if (type == FloatingObject::FloatLeft)
        m_leftObjectsCount++;
    else
        m_rightObjectsCount++;
}

inline void FloatingObjects::decreaseObjectsCount(FloatingObject::Type type)
{
    if (type == FloatingObject::FloatLeft)
        m_leftObjectsCount--;
    else
        m_rightObjectsCount--;
}

inline FloatingObjectInterval FloatingObjects::intervalForFloatingObject(FloatingObject& floatingObject)
{
    if (m_horizontalWritingMode)
        return FloatingObjectInterval(floatingObject.frameRect().y(), floatingObject.frameRect().maxY(), &floatingObject);
    return FloatingObjectInterval(floatingObject.frameRect().x(), floatingObject.frameRect().maxX(), &floatingObject);
}

void FloatingObjects::addPlacedObject(FloatingObject& floatingObject)
{
    ASSERT(!floatingObject.isInPlacedTree());

    floatingObject.setIsPlaced(true);
    if (m_placedFloatsTree.isInitialized())
        m_placedFloatsTree.add(intervalForFloatingObject(floatingObject));

#if ENABLE(ASSERT)
    floatingObject.setIsInPlacedTree(true);
#endif
    markLowestFloatLogicalBottomCacheAsDirty();
}

void FloatingObjects::removePlacedObject(FloatingObject& floatingObject)
{
    ASSERT(floatingObject.isPlaced() && floatingObject.isInPlacedTree());

    if (m_placedFloatsTree.isInitialized()) {
        bool removed = m_placedFloatsTree.remove(intervalForFloatingObject(floatingObject));
        ASSERT_UNUSED(removed, removed);
    }

    floatingObject.setIsPlaced(false);
#if ENABLE(ASSERT)
    floatingObject.setIsInPlacedTree(false);
#endif
    markLowestFloatLogicalBottomCacheAsDirty();
}

FloatingObject* FloatingObjects::add(std::unique_ptr<FloatingObject> floatingObject)
{
    FloatingObject* newObject = floatingObject.release();
    increaseObjectsCount(newObject->getType());
    m_set.add(wrapUnique(newObject));
    if (newObject->isPlaced())
        addPlacedObject(*newObject);
    markLowestFloatLogicalBottomCacheAsDirty();
    return newObject;
}

void FloatingObjects::remove(FloatingObject* toBeRemoved)
{
    decreaseObjectsCount(toBeRemoved->getType());
    std::unique_ptr<FloatingObject> floatingObject = m_set.take(toBeRemoved);
    ASSERT(floatingObject->isPlaced() || !floatingObject->isInPlacedTree());
    if (floatingObject->isPlaced())
        removePlacedObject(*floatingObject);
    markLowestFloatLogicalBottomCacheAsDirty();
    ASSERT(!floatingObject->originatingLine());
}

void FloatingObjects::computePlacedFloatsTree()
{
    ASSERT(!m_placedFloatsTree.isInitialized());
    if (m_set.isEmpty())
        return;
    m_placedFloatsTree.initIfNeeded(m_layoutObject->view()->intervalArena());
    FloatingObjectSetIterator it = m_set.begin();
    FloatingObjectSetIterator end = m_set.end();
    for (; it != end; ++it) {
        FloatingObject& floatingObject = *it->get();
        if (floatingObject.isPlaced())
            m_placedFloatsTree.add(intervalForFloatingObject(floatingObject));
    }
}

LayoutUnit FloatingObjects::logicalLeftOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
{
    ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatLeft> adapter(m_layoutObject, logicalTop, logicalTop, fixedOffset);
    placedFloatsTree().allOverlapsWithAdapter(adapter);

    if (heightRemaining)
        *heightRemaining = adapter.heightRemaining();

    return adapter.offset();
}

LayoutUnit FloatingObjects::logicalRightOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
{
    ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatRight> adapter(m_layoutObject, logicalTop, logicalTop, fixedOffset);
    placedFloatsTree().allOverlapsWithAdapter(adapter);

    if (heightRemaining)
        *heightRemaining = adapter.heightRemaining();

    return std::min(fixedOffset, adapter.offset());
}

LayoutUnit FloatingObjects::logicalLeftOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
{
    ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatLeft> adapter(m_layoutObject, logicalTop, logicalTop + logicalHeight, fixedOffset);
    placedFloatsTree().allOverlapsWithAdapter(adapter);

    return adapter.offset();
}

LayoutUnit FloatingObjects::logicalRightOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
{
    ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatRight> adapter(m_layoutObject, logicalTop, logicalTop + logicalHeight, fixedOffset);
    placedFloatsTree().allOverlapsWithAdapter(adapter);

    return std::min(fixedOffset, adapter.offset());
}

FloatingObjects::FloatBottomCachedValue::FloatBottomCachedValue()
    : floatingObject(nullptr)
    , dirty(true)
{
}

template<>
inline bool ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
{
    LayoutUnit logicalRight = m_layoutObject->logicalRightForFloat(floatingObject);
    if (logicalRight > m_offset) {
        m_offset = logicalRight;
        return true;
    }
    return false;
}

template<>
inline bool ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatRight>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
{
    LayoutUnit logicalLeft = m_layoutObject->logicalLeftForFloat(floatingObject);
    if (logicalLeft < m_offset) {
        m_offset = logicalLeft;
        return true;
    }
    return false;
}

template <FloatingObject::Type FloatTypeValue>
LayoutUnit ComputeFloatOffsetForFloatLayoutAdapter<FloatTypeValue>::heightRemaining() const
{
    return this->m_outermostFloat ? this->m_layoutObject->logicalBottomForFloat(*this->m_outermostFloat) - this->m_lineTop : LayoutUnit(1);
}

template <FloatingObject::Type FloatTypeValue>
DISABLE_CFI_PERF
inline void ComputeFloatOffsetAdapter<FloatTypeValue>::collectIfNeeded(const IntervalType& interval)
{
    const FloatingObject& floatingObject = *(interval.data());
    if (floatingObject.getType() != FloatTypeValue || !rangesIntersect(interval.low(), interval.high(), m_lineTop, m_lineBottom))
        return;

    // Make sure the float hasn't changed since it was added to the placed floats tree.
    ASSERT(floatingObject.isPlaced());
    ASSERT(interval.low() == m_layoutObject->logicalTopForFloat(floatingObject));
    ASSERT(interval.high() == m_layoutObject->logicalBottomForFloat(floatingObject));

    bool floatIsNewExtreme = updateOffsetIfNeeded(floatingObject);
    if (floatIsNewExtreme)
        m_outermostFloat = &floatingObject;
}

template<>
inline bool ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
{
    LayoutUnit logicalRight = m_layoutObject->logicalRightForFloat(floatingObject);
    if (ShapeOutsideInfo* shapeOutside = floatingObject.layoutObject()->shapeOutsideInfo()) {
        ShapeOutsideDeltas shapeDeltas = shapeOutside->computeDeltasForContainingBlockLine(LineLayoutBlockFlow(const_cast<LayoutBlockFlow*>(m_layoutObject)), floatingObject, m_lineTop, m_lineBottom - m_lineTop);
        if (!shapeDeltas.lineOverlapsShape())
            return false;

        logicalRight += shapeDeltas.rightMarginBoxDelta();
    }
    if (logicalRight > m_offset) {
        m_offset = logicalRight;
        return true;
    }

    return false;
}

template<>
inline bool ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatRight>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
{
    LayoutUnit logicalLeft = m_layoutObject->logicalLeftForFloat(floatingObject);
    if (ShapeOutsideInfo* shapeOutside = floatingObject.layoutObject()->shapeOutsideInfo()) {
        ShapeOutsideDeltas shapeDeltas = shapeOutside->computeDeltasForContainingBlockLine(LineLayoutBlockFlow(const_cast<LayoutBlockFlow*>(m_layoutObject)), floatingObject, m_lineTop, m_lineBottom - m_lineTop);
        if (!shapeDeltas.lineOverlapsShape())
            return false;

        logicalLeft += shapeDeltas.leftMarginBoxDelta();
    }
    if (logicalLeft < m_offset) {
        m_offset = logicalLeft;
        return true;
    }

    return false;
}

#ifndef NDEBUG
// These helpers are only used by the PODIntervalTree for debugging purposes.
String ValueToString<LayoutUnit>::toString(const LayoutUnit value)
{
    return String::number(value.toFloat());
}

String ValueToString<FloatingObject*>::toString(const FloatingObject* floatingObject)
{
    return String::format("%p (%gx%g %gx%g)", floatingObject, floatingObject->frameRect().x().toFloat(), floatingObject->frameRect().y().toFloat(), floatingObject->frameRect().maxX().toFloat(), floatingObject->frameRect().maxY().toFloat());
}
#endif


} // namespace blink