FloatingContext.cpp [plain text]
#include "config.h"
#include "FloatingContext.h"
#if ENABLE(LAYOUT_FORMATTING_CONTEXT)
#include "BlockFormattingState.h"
#include "DisplayBox.h"
#include "FloatAvoider.h"
#include "FormattingContext.h"
#include "LayoutBox.h"
#include "LayoutContainerBox.h"
#include <wtf/IsoMallocInlines.h>
namespace WebCore {
namespace Layout {
WTF_MAKE_ISO_ALLOCATED_IMPL(FloatingContext);
class Iterator;
class FloatPair {
public:
struct LeftRightIndex {
bool isEmpty() const { return !left && !right;}
Optional<unsigned> left;
Optional<unsigned> right;
};
bool isEmpty() const { return m_floatPair.isEmpty(); }
const FloatingState::FloatItem* left() const;
const FloatingState::FloatItem* right() const;
bool intersects(const FloatAvoider&) const;
PositionInContextRoot verticalConstraint() const { return m_verticalPosition; }
struct HorizontalConstraints {
Optional<PositionInContextRoot> left;
Optional<PositionInContextRoot> right;
};
HorizontalConstraints horizontalConstraints() const;
PositionInContextRoot bottom() const;
LeftRightIndex operator*() const { return m_floatPair; };
bool operator==(const FloatPair&) const;
private:
friend class Iterator;
FloatPair(const FloatingState::FloatList&);
const FloatingState::FloatList& m_floats;
LeftRightIndex m_floatPair;
PositionInContextRoot m_verticalPosition;
};
class Iterator {
public:
Iterator(const FloatingState::FloatList&, Optional<PositionInContextRoot> verticalPosition);
const FloatPair& operator*() const { return m_current; }
Iterator& operator++();
bool operator==(const Iterator&) const;
bool operator!=(const Iterator&) const;
private:
void set(PositionInContextRoot verticalPosition);
const FloatingState::FloatList& m_floats;
FloatPair m_current;
};
static Iterator begin(const FloatingState::FloatList& floats, PositionInContextRoot initialVerticalPosition)
{
return Iterator(floats, initialVerticalPosition);
}
static Iterator end(const FloatingState::FloatList& floats)
{
return Iterator(floats, { });
}
#if ASSERT_ENABLED
static bool areFloatsHorizontallySorted(const FloatingState& floatingState)
{
auto& floats = floatingState.floats();
auto rightEdgeOfLeftFloats = LayoutUnit::min();
auto leftEdgeOfRightFloats = LayoutUnit::max();
WTF::Optional<LayoutUnit> leftBottom;
WTF::Optional<LayoutUnit> rightBottom;
for (auto& floatItem : floats) {
if (floatItem.isLeftPositioned()) {
auto rightEdge = floatItem.rectWithMargin().right();
if (rightEdge < rightEdgeOfLeftFloats) {
if (leftBottom && floatItem.rectWithMargin().top() < *leftBottom)
return false;
}
leftBottom = floatItem.rectWithMargin().bottom();
rightEdgeOfLeftFloats = rightEdge;
} else {
auto leftEdge = floatItem.rectWithMargin().left();
if (leftEdge > leftEdgeOfRightFloats) {
if (rightBottom && floatItem.rectWithMargin().top() < *rightBottom)
return false;
}
rightBottom = floatItem.rectWithMargin().bottom();
leftEdgeOfRightFloats = leftEdge;
}
}
return true;
}
#endif
static ComputedHorizontalMargin computedHorizontalMargin(const Box& layoutBox, LayoutUnit horizontalConstraint)
{
auto& style = layoutBox.style();
auto computedValue = [&] (const auto& margin) {
if (margin.isFixed() || margin.isPercent() || margin.isCalculated())
return valueForLength(margin, horizontalConstraint);
return 0_lu;
};
return { computedValue(style.marginStart()), computedValue(style.marginEnd()) };
}
static FloatPair::LeftRightIndex findAvailablePosition(FloatAvoider& floatAvoider, const FloatingState::FloatList& floats)
{
Optional<PositionInContextRoot> bottomMost;
Optional<FloatPair::LeftRightIndex> innerMostLeftAndRight;
auto end = Layout::end(floats);
for (auto iterator = begin(floats, { floatAvoider.top() }); iterator != end; ++iterator) {
ASSERT(!(*iterator).isEmpty());
auto leftRightFloatPair = *iterator;
innerMostLeftAndRight = innerMostLeftAndRight.valueOr(*leftRightFloatPair);
auto leftRightEdge = leftRightFloatPair.horizontalConstraints();
if (auto horizontalConstraint = floatAvoider.isLeftAligned() ? leftRightEdge.left : leftRightEdge.right)
floatAvoider.setHorizontalPosition(*horizontalConstraint);
else
floatAvoider.resetHorizontalPosition();
floatAvoider.setVerticalPosition(leftRightFloatPair.verticalConstraint());
if (!floatAvoider.overflowsContainingBlock() && !leftRightFloatPair.intersects(floatAvoider))
return *innerMostLeftAndRight;
bottomMost = leftRightFloatPair.bottom();
}
if (!bottomMost)
return { };
floatAvoider.setVerticalPosition(*bottomMost);
floatAvoider.resetHorizontalPosition();
ASSERT(innerMostLeftAndRight);
return *innerMostLeftAndRight;
}
struct FloatingContext::AbsoluteCoordinateValuesForFloatAvoider {
LayoutPoint topLeft;
LayoutPoint containingBlockTopLeft;
HorizontalEdges containingBlockContentBox;
};
FloatingContext::FloatingContext(const ContainerBox& floatingContextRoot, const FormattingContext& formattingContext, FloatingState& floatingState)
: m_root(makeWeakPtr(floatingContextRoot))
, m_formattingContext(formattingContext)
, m_floatingState(floatingState)
{
}
LayoutPoint FloatingContext::positionForFloat(const Box& layoutBox, const HorizontalConstraints& horizontalConstraints) const
{
ASSERT(layoutBox.isFloatingPositioned());
ASSERT(areFloatsHorizontallySorted(m_floatingState));
if (isEmpty()) {
auto& boxGeometry = formattingContext().geometryForBox(layoutBox);
auto alignWithContainingBlock = [&]() -> Position {
if (layoutBox.isLeftFloatingPositioned())
return { horizontalConstraints.logicalLeft + boxGeometry.marginStart() };
return { horizontalConstraints.logicalRight() - boxGeometry.marginEnd() - boxGeometry.width() };
};
return { alignWithContainingBlock(), boxGeometry.top() };
}
ASSERT(!isEmpty());
auto previousFloatAbsoluteTop = floatingState().floats().last().rectWithMargin().top();
auto absoluteDisplayBoxCoordinates = this->absoluteDisplayBoxCoordinates(layoutBox);
auto absoluteTopLeft = absoluteDisplayBoxCoordinates.topLeft;
auto& displayBox = formattingContext().geometryForBox(layoutBox);
if (absoluteTopLeft.y() - displayBox.marginBefore() < previousFloatAbsoluteTop)
absoluteTopLeft.setY(previousFloatAbsoluteTop + displayBox.marginBefore());
auto horizontalMargin = computedHorizontalMargin(layoutBox, horizontalConstraints.logicalWidth);
auto margins = Edges { { *horizontalMargin.start, *horizontalMargin.end }, { displayBox.marginBefore(), displayBox.marginAfter() } };
auto floatBox = FloatAvoider { layoutBox, absoluteTopLeft, displayBox.width(), margins, absoluteDisplayBoxCoordinates.containingBlockContentBox };
findAvailablePosition(floatBox, m_floatingState.floats());
auto containingBlockTopLeft = absoluteDisplayBoxCoordinates.containingBlockTopLeft;
return { floatBox.left() + margins.horizontal.left - containingBlockTopLeft.x(), floatBox.top() + margins.vertical.top - containingBlockTopLeft.y() };
}
LayoutPoint FloatingContext::positionForNonFloatingFloatAvoider(const Box& layoutBox, const HorizontalConstraints& horizontalConstraints) const
{
ASSERT(layoutBox.establishesBlockFormattingContext());
ASSERT(!layoutBox.isFloatingPositioned());
ASSERT(!layoutBox.hasFloatClear());
ASSERT(areFloatsHorizontallySorted(m_floatingState));
if (isEmpty())
return formattingContext().geometryForBox(layoutBox).topLeft();
auto absoluteDisplayBoxCoordinates = this->absoluteDisplayBoxCoordinates(layoutBox);
auto& displayBox = formattingContext().geometryForBox(layoutBox);
auto horizontalMargin = computedHorizontalMargin(layoutBox, horizontalConstraints.logicalWidth);
auto margins = Edges { { *horizontalMargin.start, *horizontalMargin.end }, { displayBox.marginBefore(), displayBox.marginAfter() } };
auto floatAvoider = FloatAvoider { layoutBox, absoluteDisplayBoxCoordinates.topLeft, displayBox.width(), margins, absoluteDisplayBoxCoordinates.containingBlockContentBox };
findPositionForFormattingContextRoot(floatAvoider);
auto containingBlockTopLeft = absoluteDisplayBoxCoordinates.containingBlockTopLeft;
return { floatAvoider.left() - containingBlockTopLeft.x(), floatAvoider.top() - containingBlockTopLeft.y() };
}
FloatingContext::ClearancePosition FloatingContext::verticalPositionWithClearance(const Box& layoutBox) const
{
ASSERT(layoutBox.hasFloatClear());
ASSERT(layoutBox.isBlockLevelBox());
ASSERT(areFloatsHorizontallySorted(m_floatingState));
if (isEmpty())
return { };
auto bottom = [&](Optional<PositionInContextRoot> floatBottom) -> ClearancePosition {
if (!floatBottom)
return { };
auto rootRelativeTop = mapTopLeftToFloatingStateRoot(layoutBox).y();
auto clearance = *floatBottom - rootRelativeTop;
if (clearance <= 0)
return { };
if (auto* previousInFlowSibling = layoutBox.previousInFlowSibling()) {
auto& formattingState = downcast<BlockFormattingState>(layoutState().formattingStateForBox(layoutBox));
auto verticalMargin = formattingState.usedVerticalMargin(layoutBox);
if (verticalMargin.collapsedValues.before) {
auto previousVerticalMarginAfter = formattingContext().geometryForBox(*previousInFlowSibling).marginAfter();
auto collapsedMargin = *verticalMargin.collapsedValues.before;
auto nonCollapsedMargin = previousVerticalMarginAfter + marginBefore(verticalMargin);
auto marginDifference = nonCollapsedMargin - collapsedMargin;
rootRelativeTop += marginDifference;
clearance -= marginDifference;
}
}
rootRelativeTop += clearance;
ASSERT(*floatBottom == rootRelativeTop);
if (&layoutBox.containingBlock() == &m_floatingState.root())
return { Position { rootRelativeTop }, clearance };
auto containingBlockRootRelativeTop = mapTopLeftToFloatingStateRoot(layoutBox.containingBlock()).y();
return { Position { rootRelativeTop - containingBlockRootRelativeTop }, clearance };
};
auto clear = layoutBox.style().clear();
if (clear == Clear::Left)
return bottom(m_floatingState.leftBottom(root()));
if (clear == Clear::Right)
return bottom(m_floatingState.rightBottom(root()));
if (clear == Clear::Both)
return bottom(m_floatingState.bottom(root()));
ASSERT_NOT_REACHED();
return { };
}
FloatingContext::Constraints FloatingContext::constraints(LayoutUnit candidateTop, LayoutUnit candidateBottom) const
{
if (isEmpty())
return { };
auto coordinateMappingIsRequired = &floatingState().root() != &root();
auto adjustedCandidateTop = candidateTop;
LayoutSize adjustingDelta;
if (coordinateMappingIsRequired) {
auto adjustedCandidatePosition = mapPointFromFormattingContextRootToFloatingStateRoot({ 0, candidateTop });
adjustedCandidateTop = adjustedCandidatePosition.y;
adjustingDelta = { adjustedCandidatePosition.x, adjustedCandidateTop - candidateTop };
}
auto adjustedCandidateBottom = adjustedCandidateTop + (candidateBottom - candidateTop);
auto isCandidateEmpty = adjustedCandidateTop == adjustedCandidateBottom;
Constraints constraints;
auto& floats = floatingState().floats();
for (auto index = floats.size(); index--;) {
auto& floatItem = floats[index];
if (constraints.left && floatItem.isLeftPositioned())
continue;
if (constraints.right && !floatItem.isLeftPositioned())
continue;
auto floatBoxRect = floatItem.rectWithMargin();
auto contains = [&] {
if (isCandidateEmpty)
return floatBoxRect.top() <= adjustedCandidateTop && floatBoxRect.bottom() > adjustedCandidateTop;
return floatBoxRect.top() < adjustedCandidateBottom && floatBoxRect.bottom() > adjustedCandidateTop;
};
if (!contains())
continue;
if (floatItem.isLeftPositioned())
constraints.left = PointInContextRoot { floatBoxRect.right(), floatBoxRect.bottom() };
else
constraints.right = PointInContextRoot { floatBoxRect.left(), floatBoxRect.bottom() };
if (constraints.left && constraints.right)
break;
}
if (coordinateMappingIsRequired) {
if (constraints.left)
constraints.left->move(-adjustingDelta);
if (constraints.right)
constraints.right->move(-adjustingDelta);
}
return constraints;
}
void FloatingContext::append(const Box& floatBox)
{
auto absoluteDisplayBox = Display::Box(formattingContext().geometryForBox(floatBox));
absoluteDisplayBox.setTopLeft(mapTopLeftToFloatingStateRoot(floatBox));
floatingState().append(FloatingState::FloatItem { floatBox, absoluteDisplayBox });
}
void FloatingContext::findPositionForFormattingContextRoot(FloatAvoider& floatAvoider) const
{
auto& floats = m_floatingState.floats();
while (true) {
auto innerMostLeftAndRight = findAvailablePosition(floatAvoider, floats);
if (innerMostLeftAndRight.isEmpty())
return;
auto overlappingFloatBox = [&floats](auto startFloatIndex, auto& floatAvoider) -> const FloatingState::FloatItem* {
for (auto i = startFloatIndex; i < floats.size(); ++i) {
auto& floatBox = floats[i];
auto intersects = [&] {
auto floatingRect = floatBox.rectWithMargin();
if (floatAvoider.left() >= floatingRect.right() || floatAvoider.right() <= floatingRect.left())
return false;
return floatAvoider.top() >= floatingRect.top() && floatAvoider.top() < floatingRect.bottom();
}();
if (intersects)
return &floatBox;
}
return nullptr;
};
auto startIndex = std::max(innerMostLeftAndRight.left.valueOr(0), innerMostLeftAndRight.right.valueOr(0)) + 1;
auto* intersectedFloatBox = overlappingFloatBox(startIndex, floatAvoider);
if (!intersectedFloatBox)
return;
floatAvoider.setVerticalPosition({ intersectedFloatBox->rectWithMargin().top() });
}
}
FloatingContext::AbsoluteCoordinateValuesForFloatAvoider FloatingContext::absoluteDisplayBoxCoordinates(const Box& floatAvoider) const
{
auto& containingBlock = floatAvoider.containingBlock();
auto& containingBlockGeometry = formattingContext().geometryForBox(containingBlock, FormattingContext::EscapeReason::FloatBoxNeedsToBeInAbsoluteCoordinates);
auto absoluteTopLeft = mapTopLeftToFloatingStateRoot(floatAvoider);
if (&containingBlock == &floatingState().root())
return { absoluteTopLeft, { }, { containingBlockGeometry.contentBoxLeft(), containingBlockGeometry.contentBoxRight() } };
auto containingBlockAbsoluteTopLeft = mapTopLeftToFloatingStateRoot(containingBlock);
return { absoluteTopLeft, containingBlockAbsoluteTopLeft, { containingBlockAbsoluteTopLeft.x() + containingBlockGeometry.contentBoxLeft(), containingBlockAbsoluteTopLeft.x() + containingBlockGeometry.contentBoxRight() } };
}
LayoutPoint FloatingContext::mapTopLeftToFloatingStateRoot(const Box& floatBox) const
{
auto& floatingStateRoot = floatingState().root();
auto topLeft = formattingContext().geometryForBox(floatBox, FormattingContext::EscapeReason::FloatBoxNeedsToBeInAbsoluteCoordinates).topLeft();
for (auto* containingBlock = &floatBox.containingBlock(); containingBlock != &floatingStateRoot; containingBlock = &containingBlock->containingBlock())
topLeft.moveBy(formattingContext().geometryForBox(*containingBlock, FormattingContext::EscapeReason::FloatBoxNeedsToBeInAbsoluteCoordinates).topLeft());
return topLeft;
}
Point FloatingContext::mapPointFromFormattingContextRootToFloatingStateRoot(Point position) const
{
auto& from = root();
auto& to = floatingState().root();
if (&from == &to)
return position;
auto mappedPosition = position;
for (auto* containingBlock = &from; containingBlock != &to; containingBlock = &containingBlock->containingBlock())
mappedPosition.moveBy(formattingContext().geometryForBox(*containingBlock, FormattingContext::EscapeReason::FloatBoxNeedsToBeInAbsoluteCoordinates).topLeft());
return mappedPosition;
}
FloatPair::FloatPair(const FloatingState::FloatList& floats)
: m_floats(floats)
{
}
const FloatingState::FloatItem* FloatPair::left() const
{
if (!m_floatPair.left)
return nullptr;
ASSERT(m_floats[*m_floatPair.left].isLeftPositioned());
return &m_floats[*m_floatPair.left];
}
const FloatingState::FloatItem* FloatPair::right() const
{
if (!m_floatPair.right)
return nullptr;
ASSERT(!m_floats[*m_floatPair.right].isLeftPositioned());
return &m_floats[*m_floatPair.right];
}
bool FloatPair::intersects(const FloatAvoider& floatAvoider) const
{
auto intersects = [&](auto* floating) {
if (!floating)
return false;
auto floatingRect = floating->rectWithMargin();
if (floatAvoider.left() >= floatingRect.right() || floatAvoider.right() <= floatingRect.left())
return false;
return floatAvoider.top() >= floatingRect.top() && floatAvoider.top() < floatingRect.bottom();
};
ASSERT(!m_floatPair.isEmpty());
return intersects(left()) || intersects(right());
}
bool FloatPair::operator ==(const FloatPair& other) const
{
return m_floatPair.left == other.m_floatPair.left && m_floatPair.right == other.m_floatPair.right;
}
FloatPair::HorizontalConstraints FloatPair::horizontalConstraints() const
{
Optional<PositionInContextRoot> leftEdge;
Optional<PositionInContextRoot> rightEdge;
if (left())
leftEdge = PositionInContextRoot { left()->rectWithMargin().right() };
if (right())
rightEdge = PositionInContextRoot { right()->rectWithMargin().left() };
return { leftEdge, rightEdge };
}
PositionInContextRoot FloatPair::bottom() const
{
auto* left = this->left();
auto* right = this->right();
ASSERT(left || right);
auto leftBottom = left ? Optional<PositionInContextRoot>(PositionInContextRoot { left->rectWithMargin().bottom() }) : WTF::nullopt;
auto rightBottom = right ? Optional<PositionInContextRoot>(PositionInContextRoot { right->rectWithMargin().bottom() }) : WTF::nullopt;
if (leftBottom && rightBottom)
return std::max(*leftBottom, *rightBottom);
if (leftBottom)
return *leftBottom;
return *rightBottom;
}
Iterator::Iterator(const FloatingState::FloatList& floats, Optional<PositionInContextRoot> verticalPosition)
: m_floats(floats)
, m_current(floats)
{
if (verticalPosition)
set(*verticalPosition);
}
inline static Optional<unsigned> previousFloatingIndex(Float floatingType, const FloatingState::FloatList& floats, unsigned currentIndex)
{
RELEASE_ASSERT(currentIndex <= floats.size());
while (currentIndex) {
auto& floating = floats[--currentIndex];
if ((floatingType == Float::Left && floating.isLeftPositioned()) || (floatingType == Float::Right && !floating.isLeftPositioned()))
return currentIndex;
}
return { };
}
Iterator& Iterator::operator++()
{
if (m_current.isEmpty()) {
ASSERT_NOT_REACHED();
return *this;
}
auto findPreviousFloatingWithLowerBottom = [&](Float floatingType, unsigned currentIndex) -> Optional<unsigned> {
RELEASE_ASSERT(currentIndex < m_floats.size());
if (!currentIndex)
return { };
auto currentBottom = m_floats[currentIndex].rectWithMargin().bottom();
Optional<unsigned> index = currentIndex;
while (true) {
index = previousFloatingIndex(floatingType, m_floats, *index);
if (!index)
return { };
if (m_floats[*index].rectWithMargin().bottom() > currentBottom)
return index;
}
ASSERT_NOT_REACHED();
return { };
};
auto leftBottom = m_current.left() ? Optional<PositionInContextRoot>(m_current.left()->bottom()) : WTF::nullopt;
auto rightBottom = m_current.right() ? Optional<PositionInContextRoot>(m_current.right()->bottom()) : WTF::nullopt;
auto updateLeft = (leftBottom == rightBottom) || (!rightBottom || (leftBottom && *leftBottom < *rightBottom));
auto updateRight = (leftBottom == rightBottom) || (!leftBottom || (rightBottom && *leftBottom > *rightBottom));
if (updateLeft) {
ASSERT(m_current.m_floatPair.left);
m_current.m_verticalPosition = *leftBottom;
m_current.m_floatPair.left = findPreviousFloatingWithLowerBottom(Float::Left, *m_current.m_floatPair.left);
}
if (updateRight) {
ASSERT(m_current.m_floatPair.right);
m_current.m_verticalPosition = *rightBottom;
m_current.m_floatPair.right = findPreviousFloatingWithLowerBottom(Float::Right, *m_current.m_floatPair.right);
}
return *this;
}
void Iterator::set(PositionInContextRoot verticalPosition)
{
m_current.m_verticalPosition = verticalPosition;
if (m_floats.isEmpty()) {
ASSERT_NOT_REACHED();
m_current.m_floatPair = { };
return;
}
auto findFloatingBelow = [&](Float floatingType) -> Optional<unsigned> {
ASSERT(!m_floats.isEmpty());
auto index = floatingType == Float::Left ? m_current.m_floatPair.left : m_current.m_floatPair.right;
index = index.valueOr(m_floats.size());
while (true) {
index = previousFloatingIndex(floatingType, m_floats, *index);
if (!index)
return { };
auto rect = m_floats[*index].rectWithMargin();
if (rect.top() <= verticalPosition && rect.bottom() > verticalPosition)
return index;
}
return { };
};
m_current.m_floatPair.left = findFloatingBelow(Float::Left);
m_current.m_floatPair.right = findFloatingBelow(Float::Right);
ASSERT(!m_current.m_floatPair.left || (*m_current.m_floatPair.left < m_floats.size() && m_floats[*m_current.m_floatPair.left].isLeftPositioned()));
ASSERT(!m_current.m_floatPair.right || (*m_current.m_floatPair.right < m_floats.size() && !m_floats[*m_current.m_floatPair.right].isLeftPositioned()));
}
bool Iterator::operator==(const Iterator& other) const
{
return m_current == other.m_current;
}
bool Iterator::operator!=(const Iterator& other) const
{
return !(*this == other);
}
}
}
#endif