4feaea27be180c5c10f4ed9258b0abf42c38a77a
[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 "LayoutBox.h"
33 #include "LayoutContainer.h"
34 #include "LayoutContext.h"
35 #include <wtf/IsoMallocInlines.h>
36
37 namespace WebCore {
38 namespace Layout {
39
40 WTF_MAKE_ISO_ALLOCATED_IMPL(FloatingContext);
41
42 // Finding the top/left position for a new floating(F)
43 //  ____  ____  _____               _______
44 // |    || L2 ||     | <-----1---->|       |
45 // |    ||____||  L3 |             |   R1  |
46 // | L1 |      |_____|             |       |
47 // |____| <-------------2--------->|       |
48 //                                 |       |
49 //                                 |_______|
50 //
51 // 1. Compute the initial vertical position for (F) -> (1)
52 // 2. Find the corresponding floating pair (L3-R1)
53 // 3. Align (F) horizontally with (L3-R1) depending whether (F) is left/right positioned
54 // 4. Intersect (F) with (L3-R1)
55 // 5. If (F) does not fit, find the next floating pair (L1-R1)
56 // 6. Repeat until either (F) fits/no more floats.
57 // Note that all coordinates are in the coordinate system of the formatting root.
58 // The formatting root here is always the one that establishes the floating context (see inherited floating context).
59 // (It simply means that the float box's formatting root is not necessarily the same as the FormattingContext's root.)
60
61 class Iterator;
62
63 class FloatingPair {
64 public:
65     bool isEmpty() const { return !m_leftIndex && !m_rightIndex; }
66     const Display::Box* left() const;
67     const Display::Box* right() const;
68     bool intersects(const Display::Box::Rect&) const;
69     LayoutUnit verticalPosition() const { return m_verticalPosition; }
70     LayoutUnit bottom() const;
71     bool operator==(const FloatingPair&) const;
72
73 private:
74     friend class Iterator;
75     FloatingPair(const FloatingState::FloatList&);
76
77     const FloatingState::FloatList& m_floats;
78
79     std::optional<unsigned> m_leftIndex;
80     std::optional<unsigned> m_rightIndex;
81     LayoutUnit m_verticalPosition;
82 };
83
84 class Iterator {
85 public:
86     Iterator(const FloatingState::FloatList&, std::optional<LayoutUnit> verticalPosition);
87
88     const FloatingPair& operator*() const { return m_current; }
89     Iterator& operator++();
90     bool operator==(const Iterator&) const;
91     bool operator!=(const Iterator&) const;
92
93 private:
94     void set(LayoutUnit verticalPosition);
95
96     const FloatingState::FloatList& m_floats;
97     FloatingPair m_current;
98 };
99
100 static Iterator begin(const FloatingState& floatingState, LayoutUnit initialVerticalPosition)
101 {
102     // Start with the inner-most floating pair for the initial vertical position.
103     return Iterator(floatingState.floats(), initialVerticalPosition);
104 }
105
106 static Iterator end(const FloatingState& floatingState)
107 {
108     return Iterator(floatingState.floats(), std::nullopt);
109 }
110
111 FloatingContext::FloatingContext(FloatingState& floatingState)
112     : m_floatingState(floatingState)
113 {
114 }
115
116 Position FloatingContext::positionForFloat(const Box& layoutBox) const
117 {
118     ASSERT(layoutBox.isFloatingPositioned());
119     FloatingState::FloatItem floatItem = { layoutBox, m_floatingState };
120
121     Position floatPosition;
122     if (m_floatingState.isEmpty()) {
123         // No float box on the context yet -> align it with the containing block's left/right edge.
124         auto& displayBox = floatItem.displayBox();
125         floatPosition = { alignWithContainingBlock(floatItem) + displayBox.marginLeft(), displayBox.top() };
126     } else {
127         // Find the top most position where the float box fits.
128         floatPosition = floatingPosition(floatItem);
129     }
130
131     return toContainingBlock(floatItem, floatPosition);
132 }
133
134 std::optional<LayoutUnit> FloatingContext::verticalPositionWithClearance(const Box& layoutBox) const
135 {
136     ASSERT(layoutBox.hasFloatClear());
137     ASSERT(layoutBox.isBlockLevelBox());
138
139     if (m_floatingState.isEmpty())
140         return { };
141
142     auto bottom = [&](std::optional<LayoutUnit> floatBottom) -> std::optional<LayoutUnit> {
143         // 'bottom' is in the formatting root's coordinate system.
144         if (!floatBottom)
145             return { };
146
147         // 9.5.2 Controlling flow next to floats: the 'clear' property
148         // Then the amount of clearance is set to the greater of:
149         //
150         // 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.
151         // 2. The amount necessary to place the top border edge of the block at its hypothetical position.
152
153         auto& layoutContext = this->layoutContext();
154         auto& displayBox = *layoutContext.displayBoxForLayoutBox(layoutBox);
155         auto rootRelativeTop = FormattingContext::mapTopLeftToAncestor(layoutContext, layoutBox, downcast<Container>(m_floatingState.root())).y;
156         auto clearance = *floatBottom - rootRelativeTop;
157         if (clearance <= 0)
158             return { };
159
160         // Clearance inhibits margin collapsing. Let's reset the relevant adjoining margins.
161         if (auto* previousInFlowSibling = layoutBox.previousInFlowSibling()) {
162             auto& previousInFlowDisplayBox = *layoutContext.displayBoxForLayoutBox(*previousInFlowSibling);
163
164             // Since the previous inflow sibling has already been laid out, its margin is collapsed by now.
165             ASSERT(!previousInFlowDisplayBox.marginBottom());
166             auto collapsedMargin = displayBox.marginTop();
167
168             // Reset previous bottom and current top margins to non-collapsing.
169             previousInFlowDisplayBox.setVerticalMargin({ previousInFlowDisplayBox.marginTop(), previousInFlowDisplayBox.nonCollapsedMarginBottom() });
170             displayBox.setVerticalMargin({ displayBox.nonCollapsedMarginTop(), displayBox.marginBottom() });
171
172             auto nonCollapsedMargin = previousInFlowDisplayBox.marginBottom() + displayBox.marginTop();
173             auto marginOffset = nonCollapsedMargin - collapsedMargin;
174             // Move the box to the position where it would be with non-collapsed margins.
175             rootRelativeTop += marginOffset;
176
177             // 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.
178             clearance -= marginOffset;
179         }
180         // Now adjust the box's position with the clearance.
181         rootRelativeTop += clearance;
182         ASSERT(*floatBottom == rootRelativeTop);
183
184         // The return vertical position is in the containing block's coordinate system.
185         auto containingBlockRootRelativeTop = FormattingContext::mapTopLeftToAncestor(layoutContext, *layoutBox.containingBlock(), downcast<Container>(m_floatingState.root())).y;
186         return rootRelativeTop - containingBlockRootRelativeTop;
187     };
188
189     auto clear = layoutBox.style().clear();
190     auto& formattingContextRoot = layoutBox.formattingContextRoot();
191
192     if (clear == Clear::Left)
193         return bottom(m_floatingState.leftBottom(formattingContextRoot));
194
195     if (clear == Clear::Right)
196         return bottom(m_floatingState.rightBottom(formattingContextRoot));
197
198     if (clear == Clear::Both)
199         return bottom(m_floatingState.bottom(formattingContextRoot));
200
201     ASSERT_NOT_REACHED();
202     return { };
203 }
204
205 Position FloatingContext::floatingPosition(const FloatingState::FloatItem& floatItem) const
206 {
207     auto initialVerticalPosition = this->initialVerticalPosition(floatItem);
208     auto& displayBox = floatItem.displayBox();
209     auto marginBoxSize = displayBox.marginBox().size();
210
211     auto end = Layout::end(m_floatingState);
212     auto top = initialVerticalPosition;
213     auto bottomMost = top;
214     for (auto iterator = begin(m_floatingState, initialVerticalPosition); iterator != end; ++iterator) {
215         ASSERT(!(*iterator).isEmpty());
216
217         auto floats = *iterator;
218         top = floats.verticalPosition();
219
220         // Move the box horizontally so that it aligns with the current floating pair.
221         auto left = alignWithFloatings(floats, floatItem);
222         // Check if the box fits at this vertical position.
223         if (!floats.intersects({ top, left, marginBoxSize.width(), marginBoxSize.height() }))
224             return { left + displayBox.marginLeft(), top + displayBox.marginTop() };
225
226         bottomMost = floats.bottom();
227         // Move to the next floating pair.
228     }
229
230     // Passed all the floats and still does not fit?
231     return { alignWithContainingBlock(floatItem) + displayBox.marginLeft(), bottomMost + displayBox.marginTop() };
232 }
233
234 LayoutUnit FloatingContext::initialVerticalPosition(const FloatingState::FloatItem& floatItem) const
235 {
236     // Incoming floating cannot be placed higher than existing floats.
237     // Take the static position (where the box would go if it wasn't floating) and adjust it with the last floating.
238     auto marginBoxTop = floatItem.displayBox().rectWithMargin().top();
239
240     if (auto lastFloat = m_floatingState.last())
241         return std::max(marginBoxTop, lastFloat->displayBox().rectWithMargin().top());
242
243     return marginBoxTop;
244 }
245
246 LayoutUnit FloatingContext::alignWithContainingBlock(const FloatingState::FloatItem& floatItem) const
247 {
248     // If there is no floating to align with, push the box to the left/right edge of its containing block's content box.
249     // (Either there's no floats at all or this box does not fit at any vertical positions where the floats are.)
250     auto& containingBlockDisplayBox = floatItem.containingBlockDisplayBox();
251     auto containingBlockContentBoxLeft = containingBlockDisplayBox.left() + containingBlockDisplayBox.contentBoxLeft();
252
253     if (floatItem.layoutBox().isLeftFloatingPositioned())
254         return containingBlockContentBoxLeft;
255
256     return containingBlockContentBoxLeft + containingBlockDisplayBox.contentBoxWidth() - floatItem.displayBox().marginBox().width();
257 }
258
259 LayoutUnit FloatingContext::alignWithFloatings(const FloatingPair& floatingPair, const FloatingState::FloatItem& floatItem) const
260 {
261     // Compute the horizontal position for the new floating by taking both the contining block and the current left/right floats into account.
262     auto& containingBlockDisplayBox = floatItem.containingBlockDisplayBox();
263     auto containingBlockContentBoxLeft = containingBlockDisplayBox.left() + containingBlockDisplayBox.contentBoxLeft();
264     auto containingBlockContentBoxRight = containingBlockDisplayBox.left() + containingBlockDisplayBox.contentBoxRight();
265     auto marginBoxWidth = floatItem.displayBox().marginBox().width();
266
267     auto leftAlignedBoxLeft = containingBlockContentBoxLeft;
268     auto rightAlignedBoxLeft = containingBlockContentBoxRight - marginBoxWidth;
269
270     if (floatingPair.isEmpty()) {
271         ASSERT_NOT_REACHED();
272         return floatItem.layoutBox().isLeftFloatingPositioned() ? leftAlignedBoxLeft : rightAlignedBoxLeft;
273     }
274
275     if (floatItem.layoutBox().isLeftFloatingPositioned()) {
276         if (auto* leftDisplayBox = floatingPair.left()) {
277             auto leftFloatingBoxRight = leftDisplayBox->rectWithMargin().right();
278             return std::min(std::max(leftAlignedBoxLeft, leftFloatingBoxRight), rightAlignedBoxLeft);
279         }
280         
281         return leftAlignedBoxLeft;
282     }
283
284     ASSERT(floatItem.layoutBox().isRightFloatingPositioned());
285
286     if (auto* rightDisplayBox = floatingPair.right()) {
287         auto rightFloatingBoxLeft = rightDisplayBox->rectWithMargin().left();
288         return std::max(std::min(rightAlignedBoxLeft, rightFloatingBoxLeft - marginBoxWidth), leftAlignedBoxLeft);
289     }
290
291     return rightAlignedBoxLeft;
292 }
293
294 // FIXME: find a better place for this.
295 Position FloatingContext::toContainingBlock(const FloatingState::FloatItem& floatItem, Position position) const
296 {
297     // From formatting root coordinate system back to containing block's.
298     if (&floatItem.containingBlock() == &m_floatingState.root())
299         return position;
300
301     auto& containingBlockDisplayBox = floatItem.containingBlockDisplayBox();
302     return { position.x - containingBlockDisplayBox.left(), position.y - containingBlockDisplayBox.top() };
303 }
304
305 FloatingPair::FloatingPair(const FloatingState::FloatList& floats)
306     : m_floats(floats)
307 {
308 }
309
310 const Display::Box* FloatingPair::left() const
311 {
312     if (!m_leftIndex)
313         return nullptr;
314
315     ASSERT(m_floats[*m_leftIndex].layoutBox().isLeftFloatingPositioned());
316     return &m_floats[*m_leftIndex].displayBox();
317 }
318
319 const Display::Box* FloatingPair::right() const
320 {
321     if (!m_rightIndex)
322         return nullptr;
323
324     ASSERT(m_floats[*m_rightIndex].layoutBox().isRightFloatingPositioned());
325     return &m_floats[*m_rightIndex].displayBox();
326 }
327
328 bool FloatingPair::intersects(const Display::Box::Rect& candidateRect) const
329 {
330     auto intersects = [&](const Display::Box* floating, Float floatingType) {
331         if (!floating)
332             return false;
333
334         auto marginRect = floating->rectWithMargin();
335         // Before intersecting, check if the candidate position is too far to the left/right.
336         // The new float's containing block could push the candidate position beyond the current float horizontally.
337         if ((floatingType == Float::Left && candidateRect.left() < marginRect.right())
338             || (floatingType == Float::Right && candidateRect.right() > marginRect.left()))
339             return true;
340         return marginRect.intersects(candidateRect);
341     };
342
343     if (!m_leftIndex && !m_rightIndex) {
344         ASSERT_NOT_REACHED();
345         return false;
346     }
347
348     if (intersects(left(), Float::Left))
349         return true;
350
351     if (intersects(right(), Float::Right))
352         return true;
353
354     return false;
355 }
356
357 bool FloatingPair::operator ==(const FloatingPair& other) const
358 {
359     return m_leftIndex == other.m_leftIndex && m_rightIndex == other.m_rightIndex;
360 }
361
362 LayoutUnit FloatingPair::bottom() const
363 {
364     auto* left = this->left();
365     auto* right = this->right();
366     ASSERT(left || right);
367
368     auto leftBottom = left ? std::optional<LayoutUnit>(left->rectWithMargin().bottom()) : std::nullopt;
369     auto rightBottom = right ? std::optional<LayoutUnit>(right->rectWithMargin().bottom()) : std::nullopt;
370
371     if (leftBottom && rightBottom)
372         return std::max(*leftBottom, *rightBottom);
373
374     if (leftBottom)
375         return *leftBottom;
376
377     return *rightBottom;
378 }
379
380 Iterator::Iterator(const FloatingState::FloatList& floats, std::optional<LayoutUnit> verticalPosition)
381     : m_floats(floats)
382     , m_current(floats)
383 {
384     if (verticalPosition)
385         set(*verticalPosition);
386 }
387
388 inline static std::optional<unsigned> previousFloatingIndex(Float floatingType, const FloatingState::FloatList& floats, unsigned currentIndex)
389 {
390     RELEASE_ASSERT(currentIndex <= floats.size());
391
392     while (currentIndex) {
393         auto& floating = floats[--currentIndex].layoutBox();
394         if ((floatingType == Float::Left && floating.isLeftFloatingPositioned()) || (floatingType == Float::Right && floating.isRightFloatingPositioned()))
395             return currentIndex;
396     }
397
398     return { };
399 }
400
401 Iterator& Iterator::operator++()
402 {
403     if (m_current.isEmpty()) {
404         ASSERT_NOT_REACHED();
405         return *this;
406     }
407
408     auto findPreviousFloatingWithLowerBottom = [&](Float floatingType, unsigned currentIndex) -> std::optional<unsigned> {
409
410         RELEASE_ASSERT(currentIndex < m_floats.size());
411
412         // Last floating? There's certainly no previous floating at this point.
413         if (!currentIndex)
414             return { };
415
416         auto currentBottom = m_floats[currentIndex].displayBox().rectWithMargin().bottom();
417
418         std::optional<unsigned> index = currentIndex;
419         while (true) {
420             index = previousFloatingIndex(floatingType, m_floats, *index);
421             if (!index)
422                 return { };
423
424             if (m_floats[*index].displayBox().rectWithMargin().bottom() > currentBottom)
425                 return index;
426         }
427
428         ASSERT_NOT_REACHED();
429         return { };
430     };
431
432     // 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).
433     // The current floats from left and right are considered the inner-most pair for the current vertical position.
434     // 2. Move away from inner-most pair by picking one of the previous floats in the list(#1)
435     // 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).
436     // 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.
437     // As the result we have more horizontal space on the current vertical position.
438     auto leftBottom = m_current.left() ? std::optional<LayoutUnit>(m_current.left()->bottom()) : std::nullopt;
439     auto rightBottom = m_current.right() ? std::optional<LayoutUnit>(m_current.right()->bottom()) : std::nullopt;
440
441     auto updateLeft = (leftBottom == rightBottom) || (!rightBottom || (leftBottom && leftBottom < rightBottom)); 
442     auto updateRight = (leftBottom == rightBottom) || (!leftBottom || (rightBottom && leftBottom > rightBottom)); 
443
444     if (updateLeft) {
445         ASSERT(m_current.m_leftIndex);
446         m_current.m_verticalPosition = *leftBottom;
447         m_current.m_leftIndex = findPreviousFloatingWithLowerBottom(Float::Left, *m_current.m_leftIndex);
448     }
449     
450     if (updateRight) {
451         ASSERT(m_current.m_rightIndex);
452         m_current.m_verticalPosition = *rightBottom;
453         m_current.m_rightIndex = findPreviousFloatingWithLowerBottom(Float::Right, *m_current.m_rightIndex);
454     }
455
456     return *this;
457 }
458
459 void Iterator::set(LayoutUnit verticalPosition)
460 {
461     // Move the iterator to the initial vertical position by starting at the inner-most floating pair (last floats on left/right).
462     // 1. Check if the inner-most pair covers the vertical position.
463     // 2. Move outwards from the inner-most pair until the vertical postion intersects.
464     // (Note that verticalPosition has already been adjusted with the top of the last float.)
465
466     m_current.m_verticalPosition = verticalPosition;
467     // No floats at all?
468     if (m_floats.isEmpty()) {
469         ASSERT_NOT_REACHED();
470
471         m_current.m_leftIndex = { };
472         m_current.m_rightIndex = { };
473         return;
474     }
475
476     auto findFloatingBelow = [&](Float floatingType) -> std::optional<unsigned> {
477
478         ASSERT(!m_floats.isEmpty());
479
480         auto index = floatingType == Float::Left ? m_current.m_leftIndex : m_current.m_rightIndex;
481         // Start from the end if we don't have current yet.
482         index = index.value_or(m_floats.size());
483         while (true) {
484             index = previousFloatingIndex(floatingType, m_floats, *index);
485             if (!index)
486                 return { };
487
488             auto bottom = m_floats[*index].displayBox().rectWithMargin().bottom();
489             // Is this floating intrusive on this position?
490             if (bottom > verticalPosition)
491                 return index;
492         }
493
494         return { };
495     };
496
497     m_current.m_leftIndex = findFloatingBelow(Float::Left);
498     m_current.m_rightIndex = findFloatingBelow(Float::Right);
499
500     ASSERT(!m_current.m_leftIndex || (*m_current.m_leftIndex < m_floats.size() && m_floats[*m_current.m_leftIndex].layoutBox().isLeftFloatingPositioned()));
501     ASSERT(!m_current.m_rightIndex || (*m_current.m_rightIndex < m_floats.size() && m_floats[*m_current.m_rightIndex].layoutBox().isRightFloatingPositioned()));
502 }
503
504 bool Iterator::operator==(const Iterator& other) const
505 {
506     return m_current == other.m_current;
507 }
508
509 bool Iterator::operator!=(const Iterator& other) const
510 {
511     return !(*this == other);
512 }
513
514 }
515 }
516 #endif