Changeset 241869 in webkit


Ignore:
Timestamp:
Feb 21, 2019 9:58:15 AM (5 years ago)
Author:
Alan Bujtas
Message:

[LFC][Floats] Add support for placing formatting roots in-between floats.
​https://bugs.webkit.org/show_bug.cgi?id=194902

Reviewed by Antti Koivisto.

Source/WebCore:

This patch add support for placing a formatting root box in-between existing floats.
The initial vertical position of a formatting root is its static position which can make the box
placed above exsiting floats (whereas we can never place a regular float above existing floats.)

Test: fast/block/block-only/floats-and-block-formatting-roots.html

  • layout/blockformatting/BlockFormattingContext.cpp:

(WebCore::Layout::BlockFormattingContext::computePositionToAvoidFloats const):

  • layout/floats/FloatingContext.cpp:

(WebCore::Layout::FloatPair::LeftRightIndex::isEmpty const):
(WebCore::Layout::FloatPair::isEmpty const):
(WebCore::Layout::FloatPair::operator* const):
(WebCore::Layout::Iterator::operator* const):
(WebCore::Layout::begin):
(WebCore::Layout::end):
(WebCore::Layout::FloatingContext::positionForFloat const):
(WebCore::Layout::FloatingContext::positionForFormattingContextRoot const):
(WebCore::Layout::findAvailablePosition):
(WebCore::Layout::FloatingContext::findPositionForFloatBox const):
(WebCore::Layout::FloatingContext::findPositionForFormattingContextRoot const):
(WebCore::Layout::FloatPair::FloatPair):
(WebCore::Layout::FloatPair::left const):
(WebCore::Layout::FloatPair::right const):
(WebCore::Layout::FloatPair::intersects const):
(WebCore::Layout::FloatPair::operator == const):
(WebCore::Layout::FloatPair::horizontalConstraints const):
(WebCore::Layout::FloatPair::bottom const):
(WebCore::Layout::Iterator::operator++):
(WebCore::Layout::Iterator::set):
(WebCore::Layout::FloatingPair::isEmpty const): Deleted.
(WebCore::Layout::FloatingPair::verticalConstraint const): Deleted.
(WebCore::Layout::FloatingContext::positionForFloatAvoiding const): Deleted.
(WebCore::Layout::FloatingContext::floatingPosition const): Deleted.
(WebCore::Layout::FloatingPair::FloatingPair): Deleted.
(WebCore::Layout::FloatingPair::left const): Deleted.
(WebCore::Layout::FloatingPair::right const): Deleted.
(WebCore::Layout::FloatingPair::intersects const): Deleted.
(WebCore::Layout::FloatingPair::operator == const): Deleted.
(WebCore::Layout::FloatingPair::horizontalConstraints const): Deleted.
(WebCore::Layout::FloatingPair::bottom const): Deleted.

  • layout/floats/FloatingContext.h:

Tools:

  • LayoutReloaded/misc/LFC-passing-tests.txt:

LayoutTests:

  • fast/block/block-only/floats-and-block-formatting-roots-expected.html: Added.
  • fast/block/block-only/floats-and-block-formatting-roots.html: Added.
Location:
trunk
Files:
2 added
7 edited

Legend:

Unmodified
Added
Removed

  • trunk/LayoutTests/ChangeLog

    r241864 r241869  
     12019-02-21  Zalan Bujtas  <zalan@apple.com>
     2
     3        [LFC][Floats] Add support for placing formatting roots in-between floats.
     4        https://bugs.webkit.org/show_bug.cgi?id=194902
     5
     6        Reviewed by Antti Koivisto.
     7
     8        * fast/block/block-only/floats-and-block-formatting-roots-expected.html: Added.
     9        * fast/block/block-only/floats-and-block-formatting-roots.html: Added.
     10
    1112019-02-21  Diego Pino Garcia  <dpino@igalia.com>
    212

  • trunk/Source/WebCore/ChangeLog

    r241863 r241869  
     12019-02-21  Zalan Bujtas  <zalan@apple.com>
     2
     3        [LFC][Floats] Add support for placing formatting roots in-between floats.
     4        https://bugs.webkit.org/show_bug.cgi?id=194902
     5
     6        Reviewed by Antti Koivisto.
     7
     8        This patch add support for placing a formatting root box in-between existing floats.
     9        The initial vertical position of a formatting root is its static position which can make the box
     10        placed above exsiting floats (whereas we can never place a regular float above existing floats.)
     11
     12        Test: fast/block/block-only/floats-and-block-formatting-roots.html
     13
     14        * layout/blockformatting/BlockFormattingContext.cpp:
     15        (WebCore::Layout::BlockFormattingContext::computePositionToAvoidFloats const):
     16        * layout/floats/FloatingContext.cpp:
     17        (WebCore::Layout::FloatPair::LeftRightIndex::isEmpty const):
     18        (WebCore::Layout::FloatPair::isEmpty const):
     19        (WebCore::Layout::FloatPair::operator* const):
     20        (WebCore::Layout::Iterator::operator* const):
     21        (WebCore::Layout::begin):
     22        (WebCore::Layout::end):
     23        (WebCore::Layout::FloatingContext::positionForFloat const):
     24        (WebCore::Layout::FloatingContext::positionForFormattingContextRoot const):
     25        (WebCore::Layout::findAvailablePosition):
     26        (WebCore::Layout::FloatingContext::findPositionForFloatBox const):
     27        (WebCore::Layout::FloatingContext::findPositionForFormattingContextRoot const):
     28        (WebCore::Layout::FloatPair::FloatPair):
     29        (WebCore::Layout::FloatPair::left const):
     30        (WebCore::Layout::FloatPair::right const):
     31        (WebCore::Layout::FloatPair::intersects const):
     32        (WebCore::Layout::FloatPair::operator == const):
     33        (WebCore::Layout::FloatPair::horizontalConstraints const):
     34        (WebCore::Layout::FloatPair::bottom const):
     35        (WebCore::Layout::Iterator::operator++):
     36        (WebCore::Layout::Iterator::set):
     37        (WebCore::Layout::FloatingPair::isEmpty const): Deleted.
     38        (WebCore::Layout::FloatingPair::verticalConstraint const): Deleted.
     39        (WebCore::Layout::FloatingContext::positionForFloatAvoiding const): Deleted.
     40        (WebCore::Layout::FloatingContext::floatingPosition const): Deleted.
     41        (WebCore::Layout::FloatingPair::FloatingPair): Deleted.
     42        (WebCore::Layout::FloatingPair::left const): Deleted.
     43        (WebCore::Layout::FloatingPair::right const): Deleted.
     44        (WebCore::Layout::FloatingPair::intersects const): Deleted.
     45        (WebCore::Layout::FloatingPair::operator == const): Deleted.
     46        (WebCore::Layout::FloatingPair::horizontalConstraints const): Deleted.
     47        (WebCore::Layout::FloatingPair::bottom const): Deleted.
     48        * layout/floats/FloatingContext.h:
     49
    1502019-02-21  Rob Buis  <rbuis@igalia.com>
    251

  • trunk/Source/WebCore/layout/blockformatting/BlockFormattingContext.cpp

    r241264 r241869  
    292292        return;
    293293
    294     if (auto adjustedPosition = floatingContext.positionForFloatAvoiding(layoutBox))
     294    if (auto adjustedPosition = floatingContext.positionForFormattingContextRoot(layoutBox))
    295295        layoutState.displayBoxForLayoutBox(layoutBox).setTopLeft(*adjustedPosition);
    296296}

  • trunk/Source/WebCore/layout/floats/FloatingContext.cpp

    r241822 r241869  
    6363class Iterator;
    6464
    65 class FloatingPair {
     65class FloatPair {
    6666public:
    67     bool isEmpty() const { return !m_leftIndex && !m_rightIndex; }
     67    struct LeftRightIndex {
     68        bool isEmpty() const { return !left && !right;}
     69
     70        Optional<unsigned> left;
     71        Optional<unsigned> right;
     72    };
     73
     74    bool isEmpty() const { return m_floatPair.isEmpty(); }
    6875    const FloatingState::FloatItem* left() const;
    6976    const FloatingState::FloatItem* right() const;
    … …  
    7279    FloatAvoider::HorizontalConstraints horizontalConstraints() const;
    7380    PositionInContextRoot bottom() const;
    74     bool operator==(const FloatingPair&) const;
     81    LeftRightIndex operator*() const { return m_floatPair; };
     82    bool operator==(const FloatPair&) const;
    7583
    7684private:
    7785    friend class Iterator;
    78     FloatingPair(const FloatingState::FloatList&);
     86    FloatPair(const FloatingState::FloatList&);
    7987
    8088    const FloatingState::FloatList& m_floats;
    81 
    82     Optional<unsigned> m_leftIndex;
    83     Optional<unsigned> m_rightIndex;
     89    LeftRightIndex m_floatPair;
    8490    PositionInContextRoot m_verticalPosition;
    8591};
    … …  
    8995    Iterator(const FloatingState::FloatList&, Optional<PositionInContextRoot> verticalPosition);
    9096
    91     const FloatingPair& operator*() const { return m_current; }
     97    const FloatPair& operator*() const { return m_current; }
    9298    Iterator& operator++();
    9399    bool operator==(const Iterator&) const;
    … …  
    98104
    99105    const FloatingState::FloatList& m_floats;
    100     FloatingPair m_current;
     106    FloatPair m_current;
    101107};
    102108
    103 static Iterator begin(const FloatingState& floatingState, PositionInContextRoot initialVerticalPosition)
     109static Iterator begin(const FloatingState::FloatList& floats, PositionInContextRoot initialVerticalPosition)
    104110{
    105111    // Start with the inner-most floating pair for the initial vertical position.
    106     return Iterator(floatingState.floats(), initialVerticalPosition);
    107 }
    108 
    109 static Iterator end(const FloatingState& floatingState)
    110 {
    111     return Iterator(floatingState.floats(), WTF::nullopt);
     112    return Iterator(floats, initialVerticalPosition);
     113}
     114
     115static Iterator end(const FloatingState::FloatList& floats)
     116{
     117    return Iterator(floats, { });
    112118}
    113119
    … …  
    173179    // Find the top most position where the float box fits.
    174180    FloatBox floatBox = { layoutBox, m_floatingState, layoutState() };
    175     floatingPosition(floatBox);
     181    findPositionForFloatBox(floatBox);
    176182    return floatBox.rectInContainingBlock().topLeft();
    177183}
    178184
    179 Optional<Point> FloatingContext::positionForFloatAvoiding(const Box& layoutBox) const
     185Optional<Point> FloatingContext::positionForFormattingContextRoot(const Box& layoutBox) const
    180186{
    181187    ASSERT(layoutBox.establishesBlockFormattingContext());
    … …  
    188194
    189195    FloatAvoider floatAvoider = { layoutBox, m_floatingState, layoutState() };
    190     floatingPosition(floatAvoider);
     196    findPositionForFormattingContextRoot(floatAvoider);
    191197    return { floatAvoider.rectInContainingBlock().topLeft() };
    192198}
    … …  
    260266}
    261267
    262 void FloatingContext::floatingPosition(FloatAvoider& floatAvoider) const
     268static FloatPair::LeftRightIndex findAvailablePosition(FloatAvoider& floatAvoider, const FloatingState::FloatList& floats)
    263269{
    264270    Optional<PositionInContextRoot> bottomMost;
    265     auto end = Layout::end(m_floatingState);
    266     for (auto iterator = begin(m_floatingState, { floatAvoider.rect().top() }); iterator != end; ++iterator) {
     271    Optional<FloatPair::LeftRightIndex> innerMostLeftAndRight;
     272    auto end = Layout::end(floats);
     273    for (auto iterator = begin(floats, { floatAvoider.rect().top() }); iterator != end; ++iterator) {
    267274        ASSERT(!(*iterator).isEmpty());
    268         auto floats = *iterator;
     275        auto leftRightFloatPair = *iterator;
     276        innerMostLeftAndRight = innerMostLeftAndRight.valueOr(*leftRightFloatPair);
    269277
    270278        // Move the box horizontally so that it either
    271279        // 1. aligns with the current floating pair
    272280        // 2. or with the containing block's content box if there's no float to align with at this vertical position.
    273         floatAvoider.setHorizontalConstraints(floats.horizontalConstraints());
    274         floatAvoider.setVerticalConstraint(floats.verticalConstraint());
     281        floatAvoider.setHorizontalConstraints(leftRightFloatPair.horizontalConstraints());
     282        floatAvoider.setVerticalConstraint(leftRightFloatPair.verticalConstraint());
    275283
    276284        // Ensure that the float avoider
    … …  
    278286        // containing block could push the candidate position beyond the current float horizontally (too far to the left/right)
    279287        // 2. avoids floats on both sides.
    280         if (!floatAvoider.overflowsContainingBlock() && !floats.intersects(floatAvoider.rect()))
    281             return;
    282 
    283         bottomMost = floats.bottom();
     288        if (!floatAvoider.overflowsContainingBlock() && !leftRightFloatPair.intersects(floatAvoider.rect()))
     289            return *innerMostLeftAndRight;
     290
     291        bottomMost = leftRightFloatPair.bottom();
    284292        // Move to the next floating pair.
    285293    }
    … …  
    287295    // The candidate box is already below of all the floats.
    288296    if (!bottomMost)
    289         return;
     297        return { };
    290298
    291299    // Passed all the floats and still does not fit? Push it below the last float.
    292300    floatAvoider.setVerticalConstraint(*bottomMost);
    293301    floatAvoider.setHorizontalConstraints({ });
    294 }
    295 
    296 FloatingPair::FloatingPair(const FloatingState::FloatList& floats)
     302    ASSERT(innerMostLeftAndRight);
     303    return *innerMostLeftAndRight;
     304}
     305
     306void FloatingContext::findPositionForFloatBox(FloatBox& floatBox) const
     307{
     308    findAvailablePosition(floatBox, m_floatingState.floats());
     309}
     310
     311void FloatingContext::findPositionForFormattingContextRoot(FloatAvoider& floatAvoider) const
     312{
     313    // A non-floating formatting root's initial vertical position is its static position.
     314    // It means that such boxes can end up vertically placed in-between existing floats (which is
     315    // never the case for floats, since they cannot be placed above existing floats).
     316    //  ____  ____
     317    // |    || F1 |
     318    // | L1 | ----
     319    // |    |  ________
     320    //  ----  |   R1   |
     321    //         --------
     322    // Document order: 1. float: left (L1) 2. float: right (R1) 3. formatting root (F1)
     323    //
     324    // 1. Probe for available placement at initial position (note it runs a backward probing algorithm at a specific vertical position)
     325    // 2. Check if there's any intersecing float below (forward seaching)
     326    // 3. Align the box with the intersected float and probe for placement again (#1).
     327    auto& floats = m_floatingState.floats();
     328    while (true) {
     329        auto innerMostLeftAndRight = findAvailablePosition(floatAvoider, floats);
     330        if (innerMostLeftAndRight.isEmpty())
     331            return;
     332
     333        auto overlappingFloatBox = [&floats](auto startFloatIndex, auto floatAvoiderRect) -> const FloatingState::FloatItem* {
     334            for (auto i = startFloatIndex; i < floats.size(); ++i) {
     335                auto& floatBox = floats[i];
     336                if (floatBox.rectWithMargin().intersects(floatAvoiderRect))
     337                    return &floatBox;
     338            }
     339            return nullptr;
     340        };
     341
     342        auto startIndex = std::max(innerMostLeftAndRight.left.valueOr(0), innerMostLeftAndRight.right.valueOr(0)) + 1;
     343        auto* intersectedFloatBox = overlappingFloatBox(startIndex, floatAvoider.rect());
     344        if (!intersectedFloatBox)
     345            return;
     346        floatAvoider.setVerticalConstraint({ intersectedFloatBox->rectWithMargin().top() });
     347    }
     348}
     349
     350FloatPair::FloatPair(const FloatingState::FloatList& floats)
    297351    : m_floats(floats)
    298352{
    299353}
    300354
    301 const FloatingState::FloatItem* FloatingPair::left() const
    302 {
    303     if (!m_leftIndex)
     355const FloatingState::FloatItem* FloatPair::left() const
     356{
     357    if (!m_floatPair.left)
    304358        return nullptr;
    305359
    306     ASSERT(m_floats[*m_leftIndex].isLeftPositioned());
    307     return &m_floats[*m_leftIndex];
    308 }
    309 
    310 const FloatingState::FloatItem* FloatingPair::right() const
    311 {
    312     if (!m_rightIndex)
     360    ASSERT(m_floats[*m_floatPair.left].isLeftPositioned());
     361    return &m_floats[*m_floatPair.left];
     362}
     363
     364const FloatingState::FloatItem* FloatPair::right() const
     365{
     366    if (!m_floatPair.right)
    313367        return nullptr;
    314368
    315     ASSERT(!m_floats[*m_rightIndex].isLeftPositioned());
    316     return &m_floats[*m_rightIndex];
    317 }
    318 
    319 bool FloatingPair::intersects(const Display::Box::Rect& floatAvoiderRect) const
     369    ASSERT(!m_floats[*m_floatPair.right].isLeftPositioned());
     370    return &m_floats[*m_floatPair.right];
     371}
     372
     373bool FloatPair::intersects(const Display::Box::Rect& floatAvoiderRect) const
    320374{
    321375    auto intersects = [&](auto* floating) {
    … …  
    323377    };
    324378
    325     ASSERT(m_leftIndex || m_rightIndex);
     379    ASSERT(!m_floatPair.isEmpty());
    326380    return intersects(left()) || intersects(right());
    327381}
    328382
    329 bool FloatingPair::operator ==(const FloatingPair& other) const
    330 {
    331     return m_leftIndex == other.m_leftIndex && m_rightIndex == other.m_rightIndex;
    332 }
    333 
    334 FloatAvoider::HorizontalConstraints FloatingPair::horizontalConstraints() const
     383bool FloatPair::operator ==(const FloatPair& other) const
     384{
     385    return m_floatPair.left == other.m_floatPair.left && m_floatPair.right == other.m_floatPair.right;
     386}
     387
     388FloatAvoider::HorizontalConstraints FloatPair::horizontalConstraints() const
    335389{
    336390    Optional<PositionInContextRoot> leftEdge;
    … …  
    346400}
    347401
    348 PositionInContextRoot FloatingPair::bottom() const
     402PositionInContextRoot FloatPair::bottom() const
    349403{
    350404    auto* left = this->left();
    … …  
    429483
    430484    if (updateLeft) {
    431         ASSERT(m_current.m_leftIndex);
     485        ASSERT(m_current.m_floatPair.left);
    432486        m_current.m_verticalPosition = *leftBottom;
    433         m_current.m_leftIndex = findPreviousFloatingWithLowerBottom(Float::Left, *m_current.m_leftIndex);
     487        m_current.m_floatPair.left = findPreviousFloatingWithLowerBottom(Float::Left, *m_current.m_floatPair.left);
    434488    }
    435489   
    436490    if (updateRight) {
    437         ASSERT(m_current.m_rightIndex);
     491        ASSERT(m_current.m_floatPair.right);
    438492        m_current.m_verticalPosition = *rightBottom;
    439         m_current.m_rightIndex = findPreviousFloatingWithLowerBottom(Float::Right, *m_current.m_rightIndex);
     493        m_current.m_floatPair.right = findPreviousFloatingWithLowerBottom(Float::Right, *m_current.m_floatPair.right);
    440494    }
    441495
    … …  
    448502    // 1. Check if the inner-most pair covers the vertical position.
    449503    // 2. Move outwards from the inner-most pair until the vertical postion intersects.
    450     // (Note that verticalPosition has already been adjusted with the top of the last float.)
    451 
    452504    m_current.m_verticalPosition = verticalPosition;
    453505    // No floats at all?
    454506    if (m_floats.isEmpty()) {
    455507        ASSERT_NOT_REACHED();
    456 
    457         m_current.m_leftIndex = { };
    458         m_current.m_rightIndex = { };
     508        m_current.m_floatPair = { };
    459509        return;
    460510    }
    … …  
    464514        ASSERT(!m_floats.isEmpty());
    465515
    466         auto index = floatingType == Float::Left ? m_current.m_leftIndex : m_current.m_rightIndex;
     516        auto index = floatingType == Float::Left ? m_current.m_floatPair.left : m_current.m_floatPair.right;
    467517        // Start from the end if we don't have current yet.
    468518        index = index.valueOr(m_floats.size());
    … …  
    472522                return { };
    473523
    474             auto bottom = m_floats[*index].rectWithMargin().bottom();
    475524            // Is this floating intrusive on this position?
    476             if (bottom > verticalPosition)
     525            auto rect = m_floats[*index].rectWithMargin();
     526            if (rect.top() <= verticalPosition && rect.bottom() > verticalPosition)
    477527                return index;
    478528        }
    … …  
    481531    };
    482532
    483     m_current.m_leftIndex = findFloatingBelow(Float::Left);
    484     m_current.m_rightIndex = findFloatingBelow(Float::Right);
    485 
    486     ASSERT(!m_current.m_leftIndex || (*m_current.m_leftIndex < m_floats.size() && m_floats[*m_current.m_leftIndex].isLeftPositioned()));
    487     ASSERT(!m_current.m_rightIndex || (*m_current.m_rightIndex < m_floats.size() && !m_floats[*m_current.m_rightIndex].isLeftPositioned()));
     533    m_current.m_floatPair.left = findFloatingBelow(Float::Left);
     534    m_current.m_floatPair.right = findFloatingBelow(Float::Right);
     535
     536    ASSERT(!m_current.m_floatPair.left || (*m_current.m_floatPair.left < m_floats.size() && m_floats[*m_current.m_floatPair.left].isLeftPositioned()));
     537    ASSERT(!m_current.m_floatPair.right || (*m_current.m_floatPair.right < m_floats.size() && !m_floats[*m_current.m_floatPair.right].isLeftPositioned()));
    488538}
    489539

  • trunk/Source/WebCore/layout/floats/FloatingContext.h

    r240253 r241869  
    5252
    5353    Point positionForFloat(const Box&) const;
    54     Optional<Point> positionForFloatAvoiding(const Box&) const;
     54    Optional<Point> positionForFormattingContextRoot(const Box&) const;
    5555
    5656    struct ClearancePosition {
    … …  
    6363    LayoutState& layoutState() const { return m_floatingState.layoutState(); }
    6464
    65     void floatingPosition(FloatAvoider&) const;
     65    void findPositionForFloatBox(FloatBox&) const;
     66    void findPositionForFormattingContextRoot(FloatAvoider&) const;
    6667
    6768    FloatingState& m_floatingState;

  • trunk/Tools/ChangeLog

    r241866 r241869  
     12019-02-21  Zalan Bujtas  <zalan@apple.com>
     2
     3        [LFC][Floats] Add support for placing formatting roots in-between floats.
     4        https://bugs.webkit.org/show_bug.cgi?id=194902
     5
     6        Reviewed by Antti Koivisto.
     7
     8        * LayoutReloaded/misc/LFC-passing-tests.txt:
     9
    1102019-02-21  Adrian Perez de Castro  <aperez@igalia.com>
    211

  • trunk/Tools/LayoutReloaded/misc/LFC-passing-tests.txt

    r241774 r241869  
    8282fast/block/block-only/floating-multiple-lefts.html
    8383fast/block/block-only/floating-with-new-block-formatting-context.html
     84fast/block/block-only/floats-and-block-formatting-roots.html
    8485fast/block/block-only/inflow-min-max-height.html
    8586fast/block/block-only/inflow-min-max-width.html
    … …  
    844845css2.1/20110323/float-replaced-width-006.htm
    845846css2.1/20110323/float-replaced-width-011.htm
    846 css2.1/20110323/floats-wrap-top-below-bfc-002l.htm
    847847css2.1/20110323/floats-001.html
    848848css2.1/20110323/floats-102.html
     849css2.1/20110323/floats-wrap-top-below-bfc-002l.htm
     850css2.1/20110323/floats-wrap-top-below-bfc-002r.htm
    849851css2.1/20110323/inline-block-non-replaced-width-001.htm
    850852css2.1/20110323/inline-block-non-replaced-width-002.htm
Note: See TracChangeset for help on using the changeset viewer.