05d444345c1a09c6d5fb134686f5c87c1edf588d
[WebKit-https.git] / Source / WebCore / layout / floats / FloatingContext.cpp
1 /*
2  * Copyright (C) 2018 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "FloatingContext.h"
28
29 #if ENABLE(LAYOUT_FORMATTING_CONTEXT)
30
31 #include "DisplayBox.h"
32 #include "FloatAvoider.h"
33 #include "FloatBox.h"
34 #include "LayoutBox.h"
35 #include "LayoutContainer.h"
36 #include "LayoutContext.h"
37 #include <wtf/IsoMallocInlines.h>
38
39 namespace WebCore {
40 namespace Layout {
41
42 WTF_MAKE_ISO_ALLOCATED_IMPL(FloatingContext);
43
44 // Finding the top/left position for a new floating(F)
45 //  ____  ____  _____               _______
46 // |    || L2 ||     | <-----1---->|       |
47 // |    ||____||  L3 |             |   R1  |
48 // | L1 |      |_____|             |       |
49 // |____| <-------------2--------->|       |
50 //                                 |       |
51 //                                 |_______|
52 //
53 // 1. Compute the initial vertical position for (F) -> (1)
54 // 2. Find the corresponding floating pair (L3-R1)
55 // 3. Align (F) horizontally with (L3-R1) depending whether (F) is left/right positioned
56 // 4. Intersect (F) with (L3-R1)
57 // 5. If (F) does not fit, find the next floating pair (L1-R1)
58 // 6. Repeat until either (F) fits/no more floats.
59 // Note that all coordinates are in the coordinate system of the formatting root.
60 // The formatting root here is always the one that establishes the floating context (see inherited floating context).
61 // (It simply means that the float box's formatting root is not necessarily the same as the FormattingContext's root.)
62
63 class Iterator;
64
65 class FloatingPair {
66 public:
67     bool isEmpty() const { return !m_leftIndex && !m_rightIndex; }
68     const FloatingState::FloatItem* left() const;
69     const FloatingState::FloatItem* right() const;
70     bool intersects(const Display::Box::Rect&) const;
71     PositionInContextRoot verticalConstraint() const { return m_verticalPosition; }
72     FloatAvoider::HorizontalConstraints horizontalConstraints() const;
73     PositionInContextRoot bottom() const;
74     bool operator==(const FloatingPair&) const;
75
76 private:
77     friend class Iterator;
78     FloatingPair(const FloatingState::FloatList&);
79
80     const FloatingState::FloatList& m_floats;
81
82     std::optional<unsigned> m_leftIndex;
83     std::optional<unsigned> m_rightIndex;
84     PositionInContextRoot m_verticalPosition;
85 };
86
87 class Iterator {
88 public:
89     Iterator(const FloatingState::FloatList&, std::optional<PositionInContextRoot> verticalPosition);
90
91     const FloatingPair& operator*() const { return m_current; }
92     Iterator& operator++();
93     bool operator==(const Iterator&) const;
94     bool operator!=(const Iterator&) const;
95
96 private:
97     void set(PositionInContextRoot verticalPosition);
98
99     const FloatingState::FloatList& m_floats;
100     FloatingPair m_current;
101 };
102
103 static Iterator begin(const FloatingState& floatingState, PositionInContextRoot initialVerticalPosition)
104 {
105     // 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(), std::nullopt);
112 }
113
114 FloatingContext::FloatingContext(FloatingState& floatingState)
115     : m_floatingState(floatingState)
116 {
117 }
118
119 PointInContainingBlock FloatingContext::positionForFloat(const Box& layoutBox) const
120 {
121     ASSERT(layoutBox.isFloatingPositioned());
122
123     if (m_floatingState.isEmpty()) {
124         auto& displayBox = *layoutContext().displayBoxForLayoutBox(layoutBox);
125
126         auto alignWithContainingBlock = [&]() -> PositionInContainingBlock {
127             // If there is no floating to align with, push the box to the left/right edge of its containing block's content box.
128             auto& containingBlockDisplayBox = *layoutContext().displayBoxForLayoutBox(*layoutBox.containingBlock());
129
130             if (layoutBox.isLeftFloatingPositioned())
131                 return containingBlockDisplayBox.contentBoxLeft() + displayBox.marginLeft();
132
133             return containingBlockDisplayBox.contentBoxRight() - displayBox.marginRight() - displayBox.width();
134         };
135
136         // No float box on the context yet -> align it with the containing block's left/right edge.
137         return { alignWithContainingBlock(), displayBox.top() };
138     }
139
140     // Find the top most position where the float box fits.
141     FloatBox floatBox = { layoutBox, m_floatingState, layoutContext() };
142     floatingPosition(floatBox);
143     return floatBox.rectInContainingBlock().topLeft();
144 }
145
146 std::optional<PointInContainingBlock> FloatingContext::positionForFloatAvoiding(const Box& layoutBox) const
147 {
148     ASSERT(layoutBox.establishesBlockFormattingContext());
149     ASSERT(!layoutBox.isFloatingPositioned());
150     ASSERT(!layoutBox.hasFloatClear());
151
152     if (m_floatingState.isEmpty())
153         return { };
154
155     FloatAvoider floatAvoider = { layoutBox, m_floatingState, layoutContext() };
156     floatingPosition(floatAvoider);
157     return { floatAvoider.rectInContainingBlock().topLeft() };
158 }
159
160 std::optional<PositionInContainingBlock> FloatingContext::verticalPositionWithClearance(const Box& layoutBox) const
161 {
162     ASSERT(layoutBox.hasFloatClear());
163     ASSERT(layoutBox.isBlockLevelBox());
164
165     if (m_floatingState.isEmpty())
166         return { };
167
168     auto bottom = [&](std::optional<PositionInContextRoot> floatBottom) -> std::optional<PositionInContainingBlock> {
169         // 'bottom' is in the formatting root's coordinate system.
170         if (!floatBottom)
171             return { };
172
173         // 9.5.2 Controlling flow next to floats: the 'clear' property
174         // Then the amount of clearance is set to the greater of:
175         //
176         // 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.
177         // 2. The amount necessary to place the top border edge of the block at its hypothetical position.
178
179         auto& layoutContext = this->layoutContext();
180         auto& displayBox = *layoutContext.displayBoxForLayoutBox(layoutBox);
181         auto rootRelativeTop = FormattingContext::mapTopLeftToAncestor(layoutContext, layoutBox, downcast<Container>(m_floatingState.root())).y;
182         auto clearance = *floatBottom - rootRelativeTop;
183         if (clearance <= 0)
184             return { };
185
186         // Clearance inhibits margin collapsing. Let's reset the relevant adjoining margins.
187         if (auto* previousInFlowSibling = layoutBox.previousInFlowSibling()) {
188             auto& previousInFlowDisplayBox = *layoutContext.displayBoxForLayoutBox(*previousInFlowSibling);
189
190             // Since the previous inflow sibling has already been laid out, its margin is collapsed by now.
191             ASSERT(!previousInFlowDisplayBox.marginBottom());
192             auto collapsedMargin = displayBox.marginTop();
193
194             // Reset previous bottom and current top margins to non-collapsing.
195             previousInFlowDisplayBox.setVerticalMargin({ previousInFlowDisplayBox.marginTop(), previousInFlowDisplayBox.nonCollapsedMarginBottom() });
196             displayBox.setVerticalMargin({ displayBox.nonCollapsedMarginTop(), displayBox.marginBottom() });
197
198             auto nonCollapsedMargin = previousInFlowDisplayBox.marginBottom() + displayBox.marginTop();
199             auto marginOffset = nonCollapsedMargin - collapsedMargin;
200             // Move the box to the position where it would be with non-collapsed margins.
201             rootRelativeTop += marginOffset;
202
203             // 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.
204             clearance -= marginOffset;
205         }
206         // Now adjust the box's position with the clearance.
207         rootRelativeTop += clearance;
208         ASSERT(*floatBottom == rootRelativeTop);
209
210         // The return vertical position is in the containing block's coordinate system.
211         auto containingBlockRootRelativeTop = FormattingContext::mapTopLeftToAncestor(layoutContext, *layoutBox.containingBlock(), downcast<Container>(m_floatingState.root())).y;
212         return rootRelativeTop - containingBlockRootRelativeTop;
213     };
214
215     auto clear = layoutBox.style().clear();
216     auto& formattingContextRoot = layoutBox.formattingContextRoot();
217
218     if (clear == Clear::Left)
219         return bottom(m_floatingState.leftBottom(formattingContextRoot));
220
221     if (clear == Clear::Right)
222         return bottom(m_floatingState.rightBottom(formattingContextRoot));
223
224     if (clear == Clear::Both)
225         return bottom(m_floatingState.bottom(formattingContextRoot));
226
227     ASSERT_NOT_REACHED();
228     return { };
229 }
230
231 void FloatingContext::floatingPosition(FloatAvoider& floatAvoider) const
232 {
233     // Ensure the float avoider starts with no constraints.
234     floatAvoider.resetPosition();
235
236     std::optional<PositionInContextRoot> bottomMost;
237     auto end = Layout::end(m_floatingState);
238     for (auto iterator = begin(m_floatingState, floatAvoider.rect().top()); iterator != end; ++iterator) {
239         ASSERT(!(*iterator).isEmpty());
240         auto floats = *iterator;
241
242         // Move the box horizontally so that it either
243         // 1. aligns with the current floating pair
244         // 2. or with the containing block's content box if there's no float to align with at this vertical position.
245         floatAvoider.setHorizontalConstraints(floats.horizontalConstraints());
246         floatAvoider.setVerticalConstraint(floats.verticalConstraint());
247
248         // Ensure that the float avoider
249         // 1. does not overflow its containing block with the current horiztonal constraints
250         // 2. avoids floats on both sides.
251         if (!floatAvoider.overflowsContainingBlock() && !floats.intersects(floatAvoider.rect()))
252             return;
253
254         bottomMost = floats.bottom();
255         // Move to the next floating pair.
256     }
257
258     // The candidate box is already below of all the floats.
259     if (!bottomMost)
260         return;
261
262     // Passed all the floats and still does not fit? Push it below the last float.
263     floatAvoider.setVerticalConstraint(*bottomMost);
264     floatAvoider.setHorizontalConstraints({ });
265 }
266
267 FloatingPair::FloatingPair(const FloatingState::FloatList& floats)
268     : m_floats(floats)
269 {
270 }
271
272 const FloatingState::FloatItem* FloatingPair::left() const
273 {
274     if (!m_leftIndex)
275         return nullptr;
276
277     ASSERT(m_floats[*m_leftIndex].isLeftPositioned());
278     return &m_floats[*m_leftIndex];
279 }
280
281 const FloatingState::FloatItem* FloatingPair::right() const
282 {
283     if (!m_rightIndex)
284         return nullptr;
285
286     ASSERT(!m_floats[*m_rightIndex].isLeftPositioned());
287     return &m_floats[*m_rightIndex];
288 }
289
290 bool FloatingPair::intersects(const Display::Box::Rect& candidateRect) const
291 {
292     auto intersects = [&](const FloatingState::FloatItem* floating, Float floatingType) {
293         if (!floating)
294             return false;
295
296         auto marginRect = floating->rectWithMargin();
297         // Before intersecting, check if the candidate position is too far to the left/right.
298         // The new float's containing block could push the candidate position beyond the current float horizontally.
299         if ((floatingType == Float::Left && candidateRect.left() < marginRect.right())
300             || (floatingType == Float::Right && candidateRect.right() > marginRect.left()))
301             return true;
302         return marginRect.intersects(candidateRect);
303     };
304
305     if (!m_leftIndex && !m_rightIndex) {
306         ASSERT_NOT_REACHED();
307         return false;
308     }
309
310     if (intersects(left(), Float::Left))
311         return true;
312
313     if (intersects(right(), Float::Right))
314         return true;
315
316     return false;
317 }
318
319 bool FloatingPair::operator ==(const FloatingPair& other) const
320 {
321     return m_leftIndex == other.m_leftIndex && m_rightIndex == other.m_rightIndex;
322 }
323
324 FloatAvoider::HorizontalConstraints FloatingPair::horizontalConstraints() const
325 {
326     std::optional<PositionInContextRoot> leftEdge;
327     std::optional<PositionInContextRoot> rightEdge;
328
329     if (left())
330         leftEdge = left()->rectWithMargin().right();
331
332     if (right())
333         rightEdge = right()->rectWithMargin().left();
334
335     return { leftEdge, rightEdge };
336 }
337
338 PositionInContextRoot FloatingPair::bottom() const
339 {
340     auto* left = this->left();
341     auto* right = this->right();
342     ASSERT(left || right);
343
344     auto leftBottom = left ? std::optional<PositionInContextRoot>(left->rectWithMargin().bottom()) : std::nullopt;
345     auto rightBottom = right ? std::optional<PositionInContextRoot>(right->rectWithMargin().bottom()) : std::nullopt;
346
347     if (leftBottom && rightBottom)
348         return std::max(*leftBottom, *rightBottom);
349
350     if (leftBottom)
351         return *leftBottom;
352
353     return *rightBottom;
354 }
355
356 Iterator::Iterator(const FloatingState::FloatList& floats, std::optional<PositionInContextRoot> verticalPosition)
357     : m_floats(floats)
358     , m_current(floats)
359 {
360     if (verticalPosition)
361         set(*verticalPosition);
362 }
363
364 inline static std::optional<unsigned> previousFloatingIndex(Float floatingType, const FloatingState::FloatList& floats, unsigned currentIndex)
365 {
366     RELEASE_ASSERT(currentIndex <= floats.size());
367
368     while (currentIndex) {
369         auto& floating = floats[--currentIndex];
370         if ((floatingType == Float::Left && floating.isLeftPositioned()) || (floatingType == Float::Right && !floating.isLeftPositioned()))
371             return currentIndex;
372     }
373
374     return { };
375 }
376
377 Iterator& Iterator::operator++()
378 {
379     if (m_current.isEmpty()) {
380         ASSERT_NOT_REACHED();
381         return *this;
382     }
383
384     auto findPreviousFloatingWithLowerBottom = [&](Float floatingType, unsigned currentIndex) -> std::optional<unsigned> {
385
386         RELEASE_ASSERT(currentIndex < m_floats.size());
387
388         // Last floating? There's certainly no previous floating at this point.
389         if (!currentIndex)
390             return { };
391
392         auto currentBottom = m_floats[currentIndex].rectWithMargin().bottom();
393
394         std::optional<unsigned> index = currentIndex;
395         while (true) {
396             index = previousFloatingIndex(floatingType, m_floats, *index);
397             if (!index)
398                 return { };
399
400             if (m_floats[*index].rectWithMargin().bottom() > currentBottom)
401                 return index;
402         }
403
404         ASSERT_NOT_REACHED();
405         return { };
406     };
407
408     // 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).
409     // The current floats from left and right are considered the inner-most pair for the current vertical position.
410     // 2. Move away from inner-most pair by picking one of the previous floats in the list(#1)
411     // 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).
412     // 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.
413     // As the result we have more horizontal space on the current vertical position.
414     auto leftBottom = m_current.left() ? std::optional<PositionInContextRoot>(m_current.left()->bottom()) : std::nullopt;
415     auto rightBottom = m_current.right() ? std::optional<PositionInContextRoot>(m_current.right()->bottom()) : std::nullopt;
416
417     auto updateLeft = (leftBottom == rightBottom) || (!rightBottom || (leftBottom && leftBottom < rightBottom)); 
418     auto updateRight = (leftBottom == rightBottom) || (!leftBottom || (rightBottom && leftBottom > rightBottom)); 
419
420     if (updateLeft) {
421         ASSERT(m_current.m_leftIndex);
422         m_current.m_verticalPosition = *leftBottom;
423         m_current.m_leftIndex = findPreviousFloatingWithLowerBottom(Float::Left, *m_current.m_leftIndex);
424     }
425     
426     if (updateRight) {
427         ASSERT(m_current.m_rightIndex);
428         m_current.m_verticalPosition = *rightBottom;
429         m_current.m_rightIndex = findPreviousFloatingWithLowerBottom(Float::Right, *m_current.m_rightIndex);
430     }
431
432     return *this;
433 }
434
435 void Iterator::set(PositionInContextRoot verticalPosition)
436 {
437     // Move the iterator to the initial vertical position by starting at the inner-most floating pair (last floats on left/right).
438     // 1. Check if the inner-most pair covers the vertical position.
439     // 2. Move outwards from the inner-most pair until the vertical postion intersects.
440     // (Note that verticalPosition has already been adjusted with the top of the last float.)
441
442     m_current.m_verticalPosition = verticalPosition;
443     // No floats at all?
444     if (m_floats.isEmpty()) {
445         ASSERT_NOT_REACHED();
446
447         m_current.m_leftIndex = { };
448         m_current.m_rightIndex = { };
449         return;
450     }
451
452     auto findFloatingBelow = [&](Float floatingType) -> std::optional<unsigned> {
453
454         ASSERT(!m_floats.isEmpty());
455
456         auto index = floatingType == Float::Left ? m_current.m_leftIndex : m_current.m_rightIndex;
457         // Start from the end if we don't have current yet.
458         index = index.value_or(m_floats.size());
459         while (true) {
460             index = previousFloatingIndex(floatingType, m_floats, *index);
461             if (!index)
462                 return { };
463
464             auto bottom = m_floats[*index].rectWithMargin().bottom();
465             // Is this floating intrusive on this position?
466             if (bottom > verticalPosition)
467                 return index;
468         }
469
470         return { };
471     };
472
473     m_current.m_leftIndex = findFloatingBelow(Float::Left);
474     m_current.m_rightIndex = findFloatingBelow(Float::Right);
475
476     ASSERT(!m_current.m_leftIndex || (*m_current.m_leftIndex < m_floats.size() && m_floats[*m_current.m_leftIndex].isLeftPositioned()));
477     ASSERT(!m_current.m_rightIndex || (*m_current.m_rightIndex < m_floats.size() && !m_floats[*m_current.m_rightIndex].isLeftPositioned()));
478 }
479
480 bool Iterator::operator==(const Iterator& other) const
481 {
482     return m_current == other.m_current;
483 }
484
485 bool Iterator::operator!=(const Iterator& other) const
486 {
487     return !(*this == other);
488 }
489
490 }
491 }
492 #endif