741 lines
32 KiB
C++
741 lines
32 KiB
C++
/*
|
|
* Copyright (C) 2018 Apple Inc. All rights reserved.
|
|
*
|
|
* Redistribution and use in source and binary forms, with or without
|
|
* modification, are permitted provided that the following conditions
|
|
* are met:
|
|
* 1. Redistributions of source code must retain the above copyright
|
|
* notice, this list of conditions and the following disclaimer.
|
|
* 2. Redistributions in binary form must reproduce the above copyright
|
|
* notice, this list of conditions and the following disclaimer in the
|
|
* documentation and/or other materials provided with the distribution.
|
|
*
|
|
* THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
|
|
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
|
|
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
|
|
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
|
|
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
|
|
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
|
|
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
|
|
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
|
|
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
|
|
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
|
|
* THE POSSIBILITY OF SUCH DAMAGE.
|
|
*/
|
|
|
|
#include "config.h"
|
|
#include "FloatingContext.h"
|
|
|
|
#if ENABLE(LAYOUT_FORMATTING_CONTEXT)
|
|
|
|
#include "BlockFormattingState.h"
|
|
#include "FloatAvoider.h"
|
|
#include "LayoutBox.h"
|
|
#include "LayoutBoxGeometry.h"
|
|
#include "LayoutContainerBox.h"
|
|
#include "LayoutContainingBlockChainIterator.h"
|
|
#include <wtf/IsoMallocInlines.h>
|
|
|
|
namespace WebCore {
|
|
namespace Layout {
|
|
|
|
WTF_MAKE_ISO_ALLOCATED_IMPL(FloatingContext);
|
|
|
|
// Finding the top/left position for a new floating(F)
|
|
// ____ ____ _____ _______
|
|
// | || L2 || | <-----1---->| |
|
|
// | ||____|| L3 | | R1 |
|
|
// | L1 | |_____| | |
|
|
// |____| <-------------2--------->| |
|
|
// | |
|
|
// |_______|
|
|
//
|
|
// 1. Compute the initial vertical position for (F) -> (1)
|
|
// 2. Find the corresponding floating pair (L3-R1)
|
|
// 3. Align (F) horizontally with (L3-R1) depending whether (F) is left/right positioned
|
|
// 4. Intersect (F) with (L3-R1)
|
|
// 5. If (F) does not fit, find the next floating pair (L1-R1)
|
|
// 6. Repeat until either (F) fits/no more floats.
|
|
// Note that all coordinates are in the coordinate system of the formatting root.
|
|
// The formatting root here is always the one that establishes the floating context (see inherited floating context).
|
|
// (It simply means that the float box's formatting root is not necessarily the same as the FormattingContext's root.)
|
|
|
|
class Iterator;
|
|
|
|
class FloatPair {
|
|
public:
|
|
struct LeftRightIndex {
|
|
bool isEmpty() const { return !left && !right;}
|
|
|
|
std::optional<unsigned> left;
|
|
std::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 {
|
|
std::optional<PositionInContextRoot> left;
|
|
std::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&, std::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)
|
|
{
|
|
// Start with the inner-most floating pair for the initial vertical position.
|
|
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();
|
|
std::optional<LayoutUnit> leftBottom;
|
|
std::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)
|
|
{
|
|
std::optional<PositionInContextRoot> bottomMost;
|
|
std::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.value_or(*leftRightFloatPair);
|
|
|
|
// Move the box horizontally so that it either
|
|
// 1. aligns with the current floating pair
|
|
// 2. or with the containing block's content box if there's no float to align with at this vertical position.
|
|
auto leftRightEdge = leftRightFloatPair.horizontalConstraints();
|
|
if (auto horizontalConstraint = floatAvoider.isLeftAligned() ? leftRightEdge.left : leftRightEdge.right)
|
|
floatAvoider.setHorizontalPosition(*horizontalConstraint);
|
|
else
|
|
floatAvoider.resetHorizontalPosition();
|
|
floatAvoider.setVerticalPosition(leftRightFloatPair.verticalConstraint());
|
|
|
|
// Ensure that the float avoider
|
|
// 1. does not "overflow" its containing block with the current horiztonal constraints. It simply means that the float avoider's
|
|
// containing block could push the candidate position beyond the current float horizontally (too far to the left/right)
|
|
// 2. avoids floats on both sides.
|
|
if (!floatAvoider.overflowsContainingBlock() && !leftRightFloatPair.intersects(floatAvoider))
|
|
return *innerMostLeftAndRight;
|
|
|
|
bottomMost = leftRightFloatPair.bottom();
|
|
// Move to the next floating pair.
|
|
}
|
|
|
|
// The candidate box is already below of all the floats.
|
|
if (!bottomMost)
|
|
return { };
|
|
|
|
// Passed all the floats and still does not fit? Push it below the last float.
|
|
floatAvoider.setVerticalPosition(*bottomMost);
|
|
floatAvoider.resetHorizontalPosition();
|
|
ASSERT(innerMostLeftAndRight);
|
|
return *innerMostLeftAndRight;
|
|
}
|
|
|
|
struct FloatingContext::AbsoluteCoordinateValuesForFloatAvoider {
|
|
LayoutPoint topLeft;
|
|
LayoutPoint containingBlockTopLeft;
|
|
HorizontalEdges containingBlockContentBox;
|
|
};
|
|
|
|
FloatingContext::FloatingContext(const FormattingContext& formattingContext, const FloatingState& floatingState)
|
|
: 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 there is no floating to align with, push the box to the left/right edge of its containing block's content box.
|
|
if (layoutBox.isLeftFloatingPositioned())
|
|
return { horizontalConstraints.logicalLeft + boxGeometry.marginStart() };
|
|
return { horizontalConstraints.logicalRight() - boxGeometry.marginEnd() - boxGeometry.borderBoxWidth() };
|
|
};
|
|
// No float box on the context yet -> align it with the containing block's left/right edge.
|
|
return { alignWithContainingBlock(), BoxGeometry::borderBoxTop(boxGeometry) };
|
|
}
|
|
|
|
// Find the top most position where the float box fits.
|
|
ASSERT(!isEmpty());
|
|
auto absoluteCoordinates = this->absoluteCoordinates(layoutBox);
|
|
auto absoluteTopLeft = absoluteCoordinates.topLeft;
|
|
auto verticalPositionCandidate = absoluteTopLeft.y();
|
|
|
|
auto& boxGeometry = formattingContext().geometryForBox(layoutBox);
|
|
if (layoutBox.hasFloatClear()) {
|
|
// The vertical position candidate needs to clear the existing floats in this context.
|
|
auto floatBottom = [&]() -> std::optional<LayoutUnit> {
|
|
switch (layoutBox.style().clear()) {
|
|
case Clear::Left:
|
|
return leftBottom();
|
|
case Clear::Right:
|
|
return rightBottom();
|
|
case Clear::Both:
|
|
return bottom();
|
|
default:
|
|
ASSERT_NOT_REACHED();
|
|
}
|
|
return { };
|
|
};
|
|
if (auto bottomWithClear = floatBottom())
|
|
verticalPositionCandidate = *bottomWithClear + boxGeometry.marginBefore();
|
|
} else {
|
|
// Incoming float cannot be placed higher than existing floats (margin box of the last float).
|
|
// Take the static position (where the box would go if it wasn't floating) and adjust it with the last float.
|
|
auto previousFloatAbsoluteTop = floatingState().floats().last().rectWithMargin().top();
|
|
if (verticalPositionCandidate - boxGeometry.marginBefore() < previousFloatAbsoluteTop)
|
|
verticalPositionCandidate = previousFloatAbsoluteTop + boxGeometry.marginBefore();
|
|
}
|
|
absoluteTopLeft.setY(verticalPositionCandidate);
|
|
auto horizontalMargin = computedHorizontalMargin(layoutBox, horizontalConstraints.logicalWidth);
|
|
auto margins = Edges { { *horizontalMargin.start, *horizontalMargin.end }, { boxGeometry.marginBefore(), boxGeometry.marginAfter() } };
|
|
auto isLeftAligned = layoutBox.isFloatingPositioned() ? layoutBox.isLeftFloatingPositioned() : layoutBox.style().isLeftToRightDirection();
|
|
auto floatBox = FloatAvoider { absoluteTopLeft, boxGeometry.borderBoxWidth(), margins, absoluteCoordinates.containingBlockContentBox, layoutBox.isFloatingPositioned(), isLeftAligned };
|
|
findAvailablePosition(floatBox, m_floatingState.floats());
|
|
// Convert box coordinates from formatting root back to containing block.
|
|
auto containingBlockTopLeft = absoluteCoordinates.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 BoxGeometry::borderBoxTopLeft(formattingContext().geometryForBox(layoutBox));
|
|
|
|
auto absoluteCoordinates = this->absoluteCoordinates(layoutBox);
|
|
auto& boxGeometry = formattingContext().geometryForBox(layoutBox);
|
|
auto horizontalMargin = computedHorizontalMargin(layoutBox, horizontalConstraints.logicalWidth);
|
|
auto margins = Edges { { *horizontalMargin.start, *horizontalMargin.end }, { boxGeometry.marginBefore(), boxGeometry.marginAfter() } };
|
|
auto isLeftAligned = layoutBox.isFloatingPositioned() ? layoutBox.isLeftFloatingPositioned() : layoutBox.style().isLeftToRightDirection();
|
|
auto floatAvoider = FloatAvoider { absoluteCoordinates.topLeft, boxGeometry.borderBoxWidth(), margins, absoluteCoordinates.containingBlockContentBox, layoutBox.isFloatingPositioned(), isLeftAligned };
|
|
findPositionForFormattingContextRoot(floatAvoider);
|
|
auto containingBlockTopLeft = absoluteCoordinates.containingBlockTopLeft;
|
|
return { floatAvoider.left() - containingBlockTopLeft.x(), floatAvoider.top() - containingBlockTopLeft.y() };
|
|
}
|
|
|
|
std::optional<FloatingContext::PositionWithClearance> FloatingContext::verticalPositionWithClearance(const Box& layoutBox) const
|
|
{
|
|
ASSERT(layoutBox.hasFloatClear());
|
|
ASSERT(areFloatsHorizontallySorted(m_floatingState));
|
|
|
|
if (isEmpty())
|
|
return { };
|
|
|
|
auto bottom = [&](auto floatBottom) -> std::optional<PositionWithClearance> {
|
|
if (!floatBottom)
|
|
return { };
|
|
// 9.5.2 Controlling flow next to floats: the 'clear' property
|
|
// Then the amount of clearance is set to the greater of:
|
|
//
|
|
// 1. The amount necessary to place the border edge of the block even with the bottom outer edge of the lowest float that is to be cleared.
|
|
// 2. The amount necessary to place the top border edge of the block at its hypothetical position.
|
|
auto logicalTopRelativeToFloatingStateRoot = mapTopLeftToFloatingStateRoot(layoutBox).y();
|
|
auto clearance = *floatBottom - logicalTopRelativeToFloatingStateRoot;
|
|
if (clearance <= 0)
|
|
return { };
|
|
|
|
if (layoutBox.isBlockLevelBox()) {
|
|
// Clearance inhibits margin collapsing in block formatting context.
|
|
if (auto* previousInFlowSibling = layoutBox.previousInFlowSibling()) {
|
|
// Does this box with clearance actually collapse its margin before with the previous inflow box's margin after?
|
|
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;
|
|
// Move the box to the position where it would be with non-collapsed margins.
|
|
logicalTopRelativeToFloatingStateRoot += marginDifference;
|
|
// Having negative clearance is also normal. It just means that the box with the non-collapsed margins is now lower than it needs to be.
|
|
clearance -= marginDifference;
|
|
}
|
|
}
|
|
}
|
|
// Now adjust the box's position with the clearance.
|
|
logicalTopRelativeToFloatingStateRoot += clearance;
|
|
ASSERT(*floatBottom == logicalTopRelativeToFloatingStateRoot);
|
|
|
|
// The return vertical position needs to be in the containing block's coordinate system.
|
|
if (&layoutBox.containingBlock() == &m_floatingState.root())
|
|
return PositionWithClearance { logicalTopRelativeToFloatingStateRoot, clearance };
|
|
|
|
auto containingBlockRootRelativeTop = mapTopLeftToFloatingStateRoot(layoutBox.containingBlock()).y();
|
|
return PositionWithClearance { logicalTopRelativeToFloatingStateRoot - containingBlockRootRelativeTop, clearance };
|
|
};
|
|
|
|
auto clear = layoutBox.style().clear();
|
|
if (clear == Clear::Left)
|
|
return bottom(leftBottom());
|
|
|
|
if (clear == Clear::Right)
|
|
return bottom(rightBottom());
|
|
|
|
if (clear == Clear::Both)
|
|
return bottom(this->bottom());
|
|
|
|
ASSERT_NOT_REACHED();
|
|
return { };
|
|
}
|
|
|
|
std::optional<LayoutUnit> FloatingContext::bottom(Clear type) const
|
|
{
|
|
// TODO: Currently this is only called once for each formatting context root with floats per layout.
|
|
// Cache the value if we end up calling it more frequently (and update it at append/remove).
|
|
auto bottom = std::optional<LayoutUnit> { };
|
|
for (auto& floatItem : floatingState().floats()) {
|
|
if ((type == Clear::Left && !floatItem.isLeftPositioned())
|
|
|| (type == Clear::Right && floatItem.isLeftPositioned()))
|
|
continue;
|
|
bottom = !bottom ? floatItem.rectWithMargin().bottom() : std::max(*bottom, floatItem.rectWithMargin().bottom());
|
|
}
|
|
return bottom;
|
|
}
|
|
|
|
std::optional<LayoutUnit> FloatingContext::top() const
|
|
{
|
|
auto top = std::optional<LayoutUnit> { };
|
|
for (auto& floatItem : floatingState().floats())
|
|
top = !top ? floatItem.rectWithMargin().top() : std::min(*top, floatItem.rectWithMargin().top());
|
|
return top;
|
|
}
|
|
|
|
FloatingContext::Constraints FloatingContext::constraints(LayoutUnit candidateTop, LayoutUnit candidateBottom) const
|
|
{
|
|
if (isEmpty())
|
|
return { };
|
|
// 1. Convert vertical position if this floating context is inherited.
|
|
// 2. Find the inner left/right floats at candidateTop/candidateBottom.
|
|
// 3. Convert left/right positions back to formattingContextRoot's cooridnate system.
|
|
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;
|
|
}
|
|
|
|
FloatingState::FloatItem FloatingContext::toFloatItem(const Box& floatBox) const
|
|
{
|
|
auto absoluteBoxGeometry = BoxGeometry(formattingContext().geometryForBox(floatBox));
|
|
absoluteBoxGeometry.setLogicalTopLeft(mapTopLeftToFloatingStateRoot(floatBox));
|
|
return { floatBox, absoluteBoxGeometry };
|
|
}
|
|
|
|
void FloatingContext::findPositionForFormattingContextRoot(FloatAvoider& floatAvoider) const
|
|
{
|
|
// A non-floating formatting root's initial vertical position is its static position.
|
|
// It means that such boxes can end up vertically placed in-between existing floats (which is
|
|
// never the case for floats, since they cannot be placed above existing floats).
|
|
// ____ ____
|
|
// | || F1 |
|
|
// | L1 | ----
|
|
// | | ________
|
|
// ---- | R1 |
|
|
// --------
|
|
// Document order: 1. float: left (L1) 2. float: right (R1) 3. formatting root (F1)
|
|
//
|
|
// 1. Probe for available placement at initial position (note it runs a backward probing algorithm at a specific vertical position)
|
|
// 2. Check if there's any intersecing float below (forward seaching)
|
|
// 3. Align the box with the intersected float and probe for placement again (#1).
|
|
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.value_or(0), innerMostLeftAndRight.right.value_or(0)) + 1;
|
|
auto* intersectedFloatBox = overlappingFloatBox(startIndex, floatAvoider);
|
|
if (!intersectedFloatBox)
|
|
return;
|
|
floatAvoider.setVerticalPosition({ intersectedFloatBox->rectWithMargin().top() });
|
|
}
|
|
}
|
|
|
|
FloatingContext::AbsoluteCoordinateValuesForFloatAvoider FloatingContext::absoluteCoordinates(const Box& floatAvoider) const
|
|
{
|
|
auto& containingBlock = floatAvoider.containingBlock();
|
|
auto& containingBlockGeometry = formattingContext().geometryForBox(containingBlock, FormattingContext::EscapeReason::FloatBoxIsAlwaysRelativeToFloatStateRoot);
|
|
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 = BoxGeometry::borderBoxTopLeft(formattingContext().geometryForBox(floatBox, FormattingContext::EscapeReason::FloatBoxIsAlwaysRelativeToFloatStateRoot));
|
|
for (auto& containingBlock : containingBlockChain(floatBox, floatingStateRoot))
|
|
topLeft.moveBy(BoxGeometry::borderBoxTopLeft(formattingContext().geometryForBox(containingBlock, FormattingContext::EscapeReason::FloatBoxIsAlwaysRelativeToFloatStateRoot)));
|
|
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(BoxGeometry::borderBoxTopLeft(formattingContext().geometryForBox(*containingBlock, FormattingContext::EscapeReason::FloatBoxIsAlwaysRelativeToFloatStateRoot)));
|
|
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
|
|
{
|
|
std::optional<PositionInContextRoot> leftEdge;
|
|
std::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 ? std::optional<PositionInContextRoot>(PositionInContextRoot { left->rectWithMargin().bottom() }) : std::nullopt;
|
|
auto rightBottom = right ? std::optional<PositionInContextRoot>(PositionInContextRoot { right->rectWithMargin().bottom() }) : std::nullopt;
|
|
|
|
if (leftBottom && rightBottom)
|
|
return std::max(*leftBottom, *rightBottom);
|
|
|
|
if (leftBottom)
|
|
return *leftBottom;
|
|
|
|
return *rightBottom;
|
|
}
|
|
|
|
Iterator::Iterator(const FloatingState::FloatList& floats, std::optional<PositionInContextRoot> verticalPosition)
|
|
: m_floats(floats)
|
|
, m_current(floats)
|
|
{
|
|
if (verticalPosition)
|
|
set(*verticalPosition);
|
|
}
|
|
|
|
inline static std::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) -> std::optional<unsigned> {
|
|
|
|
RELEASE_ASSERT(currentIndex < m_floats.size());
|
|
|
|
// Last floating? There's certainly no previous floating at this point.
|
|
if (!currentIndex)
|
|
return { };
|
|
|
|
auto currentBottom = m_floats[currentIndex].rectWithMargin().bottom();
|
|
|
|
std::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 { };
|
|
};
|
|
|
|
// 1. Take the current floating from left and right and check which one's bottom edge is positioned higher (they could be on the same vertical position too).
|
|
// The current floats from left and right are considered the inner-most pair for the current vertical position.
|
|
// 2. Move away from inner-most pair by picking one of the previous floats in the list(#1)
|
|
// Ensure that the new floating's bottom edge is positioned lower than the current one -which essentially means skipping in-between floats that are positioned higher).
|
|
// 3. Reset the vertical position and align it with the new left-right pair. These floats are now the inner-most boxes for the current vertical position.
|
|
// As the result we have more horizontal space on the current vertical position.
|
|
auto leftBottom = m_current.left() ? std::optional<PositionInContextRoot>(m_current.left()->bottom()) : std::nullopt;
|
|
auto rightBottom = m_current.right() ? std::optional<PositionInContextRoot>(m_current.right()->bottom()) : std::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)
|
|
{
|
|
// Move the iterator to the initial vertical position by starting at the inner-most floating pair (last floats on left/right).
|
|
// 1. Check if the inner-most pair covers the vertical position.
|
|
// 2. Move outwards from the inner-most pair until the vertical postion intersects.
|
|
m_current.m_verticalPosition = verticalPosition;
|
|
// No floats at all?
|
|
if (m_floats.isEmpty()) {
|
|
ASSERT_NOT_REACHED();
|
|
m_current.m_floatPair = { };
|
|
return;
|
|
}
|
|
|
|
auto findFloatingBelow = [&](Float floatingType) -> std::optional<unsigned> {
|
|
|
|
ASSERT(!m_floats.isEmpty());
|
|
|
|
auto index = floatingType == Float::Left ? m_current.m_floatPair.left : m_current.m_floatPair.right;
|
|
// Start from the end if we don't have current yet.
|
|
index = index.value_or(m_floats.size());
|
|
while (true) {
|
|
index = previousFloatingIndex(floatingType, m_floats, *index);
|
|
if (!index)
|
|
return { };
|
|
|
|
// Is this floating intrusive on this position?
|
|
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
|