blob: 0d13c321aa8a24fbddb4dd0fd24bc4cf11ebc06d [file] [log] [blame]
/*
* 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-2019 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 "config.h"
#include "FloatingObjects.h"
#include "PODIntervalTree.h"
#include "RenderBlockFlow.h"
#include "RenderBox.h"
#include "RenderView.h"
#include <wtf/HexNumber.h>
#include <wtf/text/StringConcatenateNumbers.h>
namespace WebCore {
struct SameSizeAsFloatingObject {
WeakPtr<RenderBox> renderer;
WeakPtr<LegacyRootInlineBox> originatingLine;
LayoutRect rect;
int paginationStrut;
LayoutSize size;
uint32_t bitfields : 8;
};
static_assert(sizeof(FloatingObject) == sizeof(SameSizeAsFloatingObject), "FloatingObject should stay small");
#if !ASSERT_ENABLED
static_assert(sizeof(WeakPtr<RenderBox>) == sizeof(void*), "WeakPtr should be same size as raw pointer");
static_assert(sizeof(WeakPtr<LegacyRootInlineBox>) == sizeof(void*), "WeakPtr should be same size as raw pointer");
#endif
FloatingObject::FloatingObject(RenderBox& renderer)
: m_renderer(renderer)
, m_paintsFloat(true)
, m_isDescendant(false)
, m_isPlaced(false)
#if ASSERT_ENABLED
, m_isInPlacedTree(false)
#endif
{
UsedFloat type = RenderStyle::usedFloat(renderer);
ASSERT(type != UsedFloat::None);
if (type == UsedFloat::Left)
m_type = FloatLeft;
else if (type == UsedFloat::Right)
m_type = FloatRight;
}
FloatingObject::FloatingObject(RenderBox& renderer, Type type, const LayoutRect& frameRect, const LayoutSize& marginOffset, bool shouldPaint, bool isDescendant)
: m_renderer(renderer)
, m_frameRect(frameRect)
, m_marginOffset(marginOffset)
, m_type(type)
, m_paintsFloat(shouldPaint)
, m_isDescendant(isDescendant)
, m_isPlaced(true)
#if ASSERT_ENABLED
, m_isInPlacedTree(false)
#endif
{
}
std::unique_ptr<FloatingObject> FloatingObject::create(RenderBox& renderer)
{
auto object = makeUnique<FloatingObject>(renderer);
object->setIsDescendant(true);
return object;
}
std::unique_ptr<FloatingObject> FloatingObject::copyToNewContainer(LayoutSize offset, bool shouldPaint, bool isDescendant) const
{
return makeUnique<FloatingObject>(renderer(), type(), LayoutRect(frameRect().location() - offset, frameRect().size()), marginOffset(), shouldPaint, isDescendant);
}
std::unique_ptr<FloatingObject> FloatingObject::cloneForNewParent() const
{
auto cloneObject = makeUnique<FloatingObject>(renderer(), type(), m_frameRect, m_marginOffset, m_paintsFloat, m_isDescendant);
cloneObject->m_paginationStrut = m_paginationStrut;
cloneObject->m_isPlaced = m_isPlaced;
return cloneObject;
}
bool FloatingObject::shouldPaint() const
{
if (!m_renderer)
return false;
return !m_renderer->hasSelfPaintingLayer() && m_paintsFloat;
}
LayoutSize FloatingObject::translationOffsetToAncestor() const
{
return locationOffsetOfBorderBox() - renderer().locationOffset();
}
#if ENABLE(TREE_DEBUGGING)
TextStream& operator<<(TextStream& stream, const FloatingObject& object)
{
stream << &object << " renderer " << &object.renderer();
if (object.isPlaced())
stream << " " << object.frameRect();
else
stream << " (not placed yet)";
return stream << " paintsFloat " << object.paintsFloat() << " shouldPaint " << object.shouldPaint();
}
#endif
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;
}
template <FloatingObject::Type FloatTypeValue>
class ComputeFloatOffsetAdapter {
public:
typedef FloatingObjectInterval IntervalType;
ComputeFloatOffsetAdapter(const RenderBlockFlow& renderer, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
: m_renderer(renderer)
, m_lineTop(lineTop)
, m_lineBottom(lineBottom)
, m_offset(offset)
, m_outermostFloat(0)
{
}
virtual ~ComputeFloatOffsetAdapter() = default;
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;
WeakPtr<const RenderBlockFlow> m_renderer;
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 RenderBlockFlow& renderer, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
: ComputeFloatOffsetAdapter<FloatTypeValue>(renderer, lineTop, lineBottom, offset)
{
}
virtual ~ComputeFloatOffsetForFloatLayoutAdapter() = default;
LayoutUnit heightRemaining() const;
protected:
bool updateOffsetIfNeeded(const FloatingObject&) final;
};
template <FloatingObject::Type FloatTypeValue>
class ComputeFloatOffsetForLineLayoutAdapter : public ComputeFloatOffsetAdapter<FloatTypeValue> {
public:
ComputeFloatOffsetForLineLayoutAdapter(const RenderBlockFlow& renderer, LayoutUnit lineTop, LayoutUnit lineBottom, LayoutUnit offset)
: ComputeFloatOffsetAdapter<FloatTypeValue>(renderer, lineTop, lineBottom, offset)
{
}
virtual ~ComputeFloatOffsetForLineLayoutAdapter() = default;
protected:
bool updateOffsetIfNeeded(const FloatingObject&) final;
};
class FindNextFloatLogicalBottomAdapter {
public:
typedef FloatingObjectInterval IntervalType;
FindNextFloatLogicalBottomAdapter(const RenderBlockFlow& renderer, LayoutUnit belowLogicalHeight)
: m_renderer(renderer)
, m_belowLogicalHeight(belowLogicalHeight)
{
}
LayoutUnit lowValue() const { return m_belowLogicalHeight; }
LayoutUnit highValue() const { return LayoutUnit::max(); }
void collectIfNeeded(const IntervalType&);
LayoutUnit nextLogicalBottom() const { return m_nextLogicalBottom.value_or(0); }
LayoutUnit nextShapeLogicalBottom() const { return m_nextShapeLogicalBottom.value_or(nextLogicalBottom()); }
private:
WeakPtr<const RenderBlockFlow> m_renderer;
LayoutUnit m_belowLogicalHeight;
std::optional<LayoutUnit> m_nextLogicalBottom;
std::optional<LayoutUnit> m_nextShapeLogicalBottom;
};
inline void FindNextFloatLogicalBottomAdapter::collectIfNeeded(const IntervalType& interval)
{
const auto& floatingObject = *interval.data();
if (!rangesIntersect(interval.low(), interval.high(), m_belowLogicalHeight, LayoutUnit::max()))
return;
// All the objects returned from the tree should be already placed.
ASSERT(floatingObject.isPlaced());
ASSERT(rangesIntersect(m_renderer->logicalTopForFloat(floatingObject), m_renderer->logicalBottomForFloat(floatingObject), m_belowLogicalHeight, LayoutUnit::max()));
LayoutUnit floatBottom = m_renderer->logicalBottomForFloat(floatingObject);
if (m_nextLogicalBottom && m_nextLogicalBottom.value() < floatBottom)
return;
if (ShapeOutsideInfo* shapeOutside = floatingObject.renderer().shapeOutsideInfo()) {
LayoutUnit shapeBottom = m_renderer->logicalTopForFloat(floatingObject) + m_renderer->marginBeforeForChild(floatingObject.renderer()) + shapeOutside->shapeLogicalBottom();
// Use the shapeBottom unless it extends outside of the margin box, in which case it is clipped.
m_nextShapeLogicalBottom = std::min(shapeBottom, floatBottom);
} else
m_nextShapeLogicalBottom = floatBottom;
m_nextLogicalBottom = floatBottom;
}
LayoutUnit FloatingObjects::findNextFloatLogicalBottomBelow(LayoutUnit logicalHeight)
{
FindNextFloatLogicalBottomAdapter adapter(renderer(), logicalHeight);
if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
placedFloatsTree->allOverlapsWithAdapter(adapter);
return adapter.nextShapeLogicalBottom();
}
LayoutUnit FloatingObjects::findNextFloatLogicalBottomBelowForBlock(LayoutUnit logicalHeight)
{
FindNextFloatLogicalBottomAdapter adapter(renderer(), logicalHeight);
if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
placedFloatsTree->allOverlapsWithAdapter(adapter);
return adapter.nextLogicalBottom();
}
FloatingObjects::FloatingObjects(const RenderBlockFlow& renderer)
: m_horizontalWritingMode(renderer.isHorizontalWritingMode())
, m_renderer(renderer)
{
}
FloatingObjects::~FloatingObjects() = default;
void FloatingObjects::clearLineBoxTreePointers()
{
// Clear references to originating lines, since the lines are being deleted
for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
ASSERT(!((*it)->originatingLine()) || &((*it)->originatingLine()->renderer()) == &renderer());
(*it)->clearOriginatingLine();
}
}
void FloatingObjects::clear()
{
m_set.clear();
m_placedFloatsTree = nullptr;
m_leftObjectsCount = 0;
m_rightObjectsCount = 0;
}
void FloatingObjects::moveAllToFloatInfoMap(RendererToFloatInfoMap& map)
{
for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
auto& renderer = it->get()->renderer();
// FIXME: The only reason it is safe to move these out of the set is that
// we are about to clear it. Otherwise it would break the hash table invariant.
// A clean way to do this would be to add a takeAll function to HashSet.
map.add(&renderer, WTFMove(*it));
}
clear();
}
void FloatingObjects::increaseObjectsCount(FloatingObject::Type type)
{
if (type == FloatingObject::FloatLeft)
m_leftObjectsCount++;
else
m_rightObjectsCount++;
}
void FloatingObjects::decreaseObjectsCount(FloatingObject::Type type)
{
if (type == FloatingObject::FloatLeft)
m_leftObjectsCount--;
else
m_rightObjectsCount--;
}
FloatingObjectInterval FloatingObjects::intervalForFloatingObject(FloatingObject* floatingObject)
{
// FIXME The endpoints of the floating object interval shouldn't need to be
// floored. See http://wkb.ug/125831 for more details.
if (m_horizontalWritingMode)
return FloatingObjectInterval(floatingObject->frameRect().y().floor(), floatingObject->frameRect().maxY().floor(), floatingObject);
return FloatingObjectInterval(floatingObject->frameRect().x().floor(), floatingObject->frameRect().maxX().floor(), floatingObject);
}
void FloatingObjects::addPlacedObject(FloatingObject* floatingObject)
{
ASSERT(!floatingObject->isInPlacedTree());
floatingObject->setIsPlaced(true);
if (m_placedFloatsTree)
m_placedFloatsTree->add(intervalForFloatingObject(floatingObject));
#if ASSERT_ENABLED
floatingObject->setIsInPlacedTree(true);
#endif
}
void FloatingObjects::removePlacedObject(FloatingObject* floatingObject)
{
ASSERT(floatingObject->isPlaced() && floatingObject->isInPlacedTree());
if (m_placedFloatsTree) {
bool removed = m_placedFloatsTree->remove(intervalForFloatingObject(floatingObject));
ASSERT_UNUSED(removed, removed);
}
floatingObject->setIsPlaced(false);
#if ASSERT_ENABLED
floatingObject->setIsInPlacedTree(false);
#endif
}
FloatingObject* FloatingObjects::add(std::unique_ptr<FloatingObject> floatingObject)
{
increaseObjectsCount(floatingObject->type());
if (floatingObject->isPlaced())
addPlacedObject(floatingObject.get());
return m_set.add(WTFMove(floatingObject)).iterator->get();
}
void FloatingObjects::remove(FloatingObject* floatingObject)
{
ASSERT((m_set.contains(floatingObject)));
decreaseObjectsCount(floatingObject->type());
ASSERT(floatingObject->isPlaced() || !floatingObject->isInPlacedTree());
if (floatingObject->isPlaced())
removePlacedObject(floatingObject);
ASSERT(!floatingObject->originatingLine());
m_set.remove(floatingObject);
}
void FloatingObjects::computePlacedFloatsTree()
{
ASSERT(!m_placedFloatsTree);
if (m_set.isEmpty())
return;
m_placedFloatsTree = makeUnique<FloatingObjectTree>();
for (auto it = m_set.begin(), end = m_set.end(); it != end; ++it) {
FloatingObject* floatingObject = it->get();
if (floatingObject->isPlaced())
m_placedFloatsTree->add(intervalForFloatingObject(floatingObject));
}
}
inline const FloatingObjectTree* FloatingObjects::placedFloatsTree()
{
if (!m_placedFloatsTree)
computePlacedFloatsTree();
return m_placedFloatsTree.get();
}
LayoutUnit FloatingObjects::logicalLeftOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
{
ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatLeft> adapter(renderer(), logicalTop, logicalTop, fixedOffset);
if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
placedFloatsTree->allOverlapsWithAdapter(adapter);
if (heightRemaining)
*heightRemaining = adapter.heightRemaining();
return adapter.offset();
}
LayoutUnit FloatingObjects::logicalRightOffsetForPositioningFloat(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit *heightRemaining)
{
ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatRight> adapter(renderer(), logicalTop, logicalTop, fixedOffset);
if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
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(renderer(), logicalTop, logicalTop + logicalHeight, fixedOffset);
if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
placedFloatsTree->allOverlapsWithAdapter(adapter);
return adapter.offset();
}
LayoutUnit FloatingObjects::logicalRightOffset(LayoutUnit fixedOffset, LayoutUnit logicalTop, LayoutUnit logicalHeight)
{
ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatRight> adapter(renderer(), logicalTop, logicalTop + logicalHeight, fixedOffset);
if (const FloatingObjectTree* placedFloatsTree = this->placedFloatsTree())
placedFloatsTree->allOverlapsWithAdapter(adapter);
return std::min(fixedOffset, adapter.offset());
}
template<>
inline bool ComputeFloatOffsetForFloatLayoutAdapter<FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
{
LayoutUnit logicalRight = m_renderer->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_renderer->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_renderer->logicalBottomForFloat(*this->m_outermostFloat) - this->m_lineTop : 1_lu;
}
template <FloatingObject::Type FloatTypeValue>
inline void ComputeFloatOffsetAdapter<FloatTypeValue>::collectIfNeeded(const IntervalType& interval)
{
const auto& floatingObject = *interval.data();
if (floatingObject.type() != FloatTypeValue || !rangesIntersect(interval.low(), interval.high(), m_lineTop, m_lineBottom))
return;
// All the objects returned from the tree should be already placed.
ASSERT(floatingObject.isPlaced());
ASSERT(rangesIntersect(m_renderer->logicalTopForFloat(floatingObject), m_renderer->logicalBottomForFloat(floatingObject), m_lineTop, m_lineBottom));
bool floatIsNewExtreme = updateOffsetIfNeeded(floatingObject);
if (floatIsNewExtreme)
m_outermostFloat = &floatingObject;
}
template<>
inline bool ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatLeft>::updateOffsetIfNeeded(const FloatingObject& floatingObject)
{
LayoutUnit logicalRight = m_renderer->logicalRightForFloat(floatingObject);
if (ShapeOutsideInfo* shapeOutside = floatingObject.renderer().shapeOutsideInfo()) {
ShapeOutsideDeltas shapeDeltas = shapeOutside->computeDeltasForContainingBlockLine(*m_renderer, floatingObject, m_lineTop, m_lineBottom - m_lineTop);
if (!shapeDeltas.isValid() || !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_renderer->logicalLeftForFloat(floatingObject);
if (ShapeOutsideInfo* shapeOutside = floatingObject.renderer().shapeOutsideInfo()) {
ShapeOutsideDeltas shapeDeltas = shapeOutside->computeDeltasForContainingBlockLine(*m_renderer, floatingObject, m_lineTop, m_lineBottom - m_lineTop);
if (!shapeDeltas.isValid() || !shapeDeltas.lineOverlapsShape())
return false;
logicalLeft += shapeDeltas.leftMarginBoxDelta();
}
if (logicalLeft < m_offset) {
m_offset = logicalLeft;
return true;
}
return false;
}
} // namespace WebCore