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