98ce2e8ea053034be4b07373a6823c345464c159
[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 "LayoutState.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     Optional<unsigned> m_leftIndex;
83     Optional<unsigned> m_rightIndex;
84     PositionInContextRoot m_verticalPosition;
85 };
86
87 class Iterator {
88 public:
89     Iterator(const FloatingState::FloatList&, 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(), WTF::nullopt);
112 }
113
114 #ifndef NDEBUG
115 static bool areFloatsHorizontallySorted(const FloatingState& floatingState)
116 {
117     auto& floats = floatingState.floats();
118     auto rightEdgeOfLeftFloats = LayoutUnit::min();
119     auto leftEdgeOfRightFloats = LayoutUnit::max();
120     WTF::Optional<LayoutUnit> leftBottom;
121     WTF::Optional<LayoutUnit> rightBottom;
122
123     for (auto& floatItem : floats) {
124         if (floatItem.isLeftPositioned()) {
125             auto rightEdge = floatItem.rectWithMargin().right();
126             if (rightEdge < rightEdgeOfLeftFloats) {
127                 if (leftBottom && floatItem.rectWithMargin().top() < *leftBottom)
128                     return false;
129             }
130             leftBottom = floatItem.rectWithMargin().bottom();
131             rightEdgeOfLeftFloats = rightEdge;
132         } else {
133             auto leftEdge = floatItem.rectWithMargin().left();
134             if (leftEdge > leftEdgeOfRightFloats) {
135                 if (rightBottom && floatItem.rectWithMargin().top() < *rightBottom)
136                     return false;
137             }
138             rightBottom = floatItem.rectWithMargin().bottom();
139             leftEdgeOfRightFloats = leftEdge;
140         }
141     }
142     return true;
143 }
144 #endif
145
146 FloatingContext::FloatingContext(FloatingState& floatingState)
147     : m_floatingState(floatingState)
148 {
149 }
150
151 Point FloatingContext::positionForFloat(const Box& layoutBox) const
152 {
153     ASSERT(layoutBox.isFloatingPositioned());
154     ASSERT(areFloatsHorizontallySorted(m_floatingState));
155
156     if (m_floatingState.isEmpty()) {
157         auto& displayBox = layoutState().displayBoxForLayoutBox(layoutBox);
158
159         auto alignWithContainingBlock = [&]() -> Position {
160             // If there is no floating to align with, push the box to the left/right edge of its containing block's content box.
161             auto& containingBlockDisplayBox = layoutState().displayBoxForLayoutBox(*layoutBox.containingBlock());
162
163             if (layoutBox.isLeftFloatingPositioned())
164                 return Position { containingBlockDisplayBox.contentBoxLeft() + displayBox.marginStart() };
165
166             return Position { containingBlockDisplayBox.contentBoxRight() - displayBox.marginEnd() - displayBox.width() };
167         };
168
169         // No float box on the context yet -> align it with the containing block's left/right edge.
170         return { alignWithContainingBlock(), displayBox.top() };
171     }
172
173     // Find the top most position where the float box fits.
174     FloatBox floatBox = { layoutBox, m_floatingState, layoutState() };
175     floatingPosition(floatBox);
176     return floatBox.rectInContainingBlock().topLeft();
177 }
178
179 Optional<Point> FloatingContext::positionForFloatAvoiding(const Box& layoutBox) const
180 {
181     ASSERT(layoutBox.establishesBlockFormattingContext());
182     ASSERT(!layoutBox.isFloatingPositioned());
183     ASSERT(!layoutBox.hasFloatClear());
184     ASSERT(areFloatsHorizontallySorted(m_floatingState));
185
186     if (m_floatingState.isEmpty())
187         return { };
188
189     FloatAvoider floatAvoider = { layoutBox, m_floatingState, layoutState() };
190     floatingPosition(floatAvoider);
191     return { floatAvoider.rectInContainingBlock().topLeft() };
192 }
193
194 FloatingContext::ClearancePosition FloatingContext::verticalPositionWithClearance(const Box& layoutBox) const
195 {
196     ASSERT(layoutBox.hasFloatClear());
197     ASSERT(layoutBox.isBlockLevelBox());
198     ASSERT(areFloatsHorizontallySorted(m_floatingState));
199
200     if (m_floatingState.isEmpty())
201         return { };
202
203     auto bottom = [&](Optional<PositionInContextRoot> floatBottom) -> ClearancePosition {
204         // 'bottom' is in the formatting root's coordinate system.
205         if (!floatBottom)
206             return { };
207
208         // 9.5.2 Controlling flow next to floats: the 'clear' property
209         // Then the amount of clearance is set to the greater of:
210         //
211         // 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.
212         // 2. The amount necessary to place the top border edge of the block at its hypothetical position.
213         auto& layoutState = this->layoutState();
214         auto rootRelativeTop = FormattingContext::mapTopToAncestor(layoutState, layoutBox, downcast<Container>(m_floatingState.root()));
215         auto clearance = *floatBottom - rootRelativeTop;
216         if (clearance <= 0)
217             return { };
218
219         // Clearance inhibits margin collapsing.
220         if (auto* previousInFlowSibling = layoutBox.previousInFlowSibling()) {
221             // Does this box with clearance actually collapse its margin before with the previous inflow box's margin after? 
222             auto verticalMargin = layoutState.displayBoxForLayoutBox(layoutBox).verticalMargin();
223             if (verticalMargin.hasCollapsedValues() && verticalMargin.collapsedValues().before) {
224                 auto previousVerticalMargin = layoutState.displayBoxForLayoutBox(*previousInFlowSibling).verticalMargin();
225                 auto collapsedMargin = *verticalMargin.collapsedValues().before;
226                 auto nonCollapsedMargin = previousVerticalMargin.after() + verticalMargin.before();
227                 auto marginDifference = nonCollapsedMargin - collapsedMargin;
228                 // Move the box to the position where it would be with non-collapsed margins.
229                 rootRelativeTop += marginDifference;
230                 // 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.
231                 clearance -= marginDifference;
232             }
233         }
234         // Now adjust the box's position with the clearance.
235         rootRelativeTop += clearance;
236         ASSERT(*floatBottom == rootRelativeTop);
237
238         // The return vertical position is in the containing block's coordinate system. Convert it to the formatting root's coordinate system if needed.
239         if (layoutBox.containingBlock() == &m_floatingState.root())
240             return { Position { rootRelativeTop }, clearance };
241
242         auto containingBlockRootRelativeTop = FormattingContext::mapTopToAncestor(layoutState, *layoutBox.containingBlock(), downcast<Container>(m_floatingState.root()));
243         return { Position { rootRelativeTop - containingBlockRootRelativeTop }, clearance };
244     };
245
246     auto clear = layoutBox.style().clear();
247     auto& formattingContextRoot = layoutBox.formattingContextRoot();
248
249     if (clear == Clear::Left)
250         return bottom(m_floatingState.leftBottom(formattingContextRoot));
251
252     if (clear == Clear::Right)
253         return bottom(m_floatingState.rightBottom(formattingContextRoot));
254
255     if (clear == Clear::Both)
256         return bottom(m_floatingState.bottom(formattingContextRoot));
257
258     ASSERT_NOT_REACHED();
259     return { };
260 }
261
262 void FloatingContext::floatingPosition(FloatAvoider& floatAvoider) const
263 {
264     Optional<PositionInContextRoot> bottomMost;
265     auto end = Layout::end(m_floatingState);
266     for (auto iterator = begin(m_floatingState, { floatAvoider.rect().top() }); iterator != end; ++iterator) {
267         ASSERT(!(*iterator).isEmpty());
268         auto floats = *iterator;
269
270         // Move the box horizontally so that it either
271         // 1. aligns with the current floating pair
272         // 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());
275
276         // Ensure that the float avoider
277         // 1. does not "overflow" its containing block with the current horiztonal constraints. It simply means that the float avoider's
278         // containing block could push the candidate position beyond the current float horizontally (too far to the left/right)
279         // 2. avoids floats on both sides.
280         if (!floatAvoider.overflowsContainingBlock() && !floats.intersects(floatAvoider.rect()))
281             return;
282
283         bottomMost = floats.bottom();
284         // Move to the next floating pair.
285     }
286
287     // The candidate box is already below of all the floats.
288     if (!bottomMost)
289         return;
290
291     // Passed all the floats and still does not fit? Push it below the last float.
292     floatAvoider.setVerticalConstraint(*bottomMost);
293     floatAvoider.setHorizontalConstraints({ });
294 }
295
296 FloatingPair::FloatingPair(const FloatingState::FloatList& floats)
297     : m_floats(floats)
298 {
299 }
300
301 const FloatingState::FloatItem* FloatingPair::left() const
302 {
303     if (!m_leftIndex)
304         return nullptr;
305
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)
313         return nullptr;
314
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
320 {
321     auto intersects = [&](auto* floating) {
322         return floating && floating->rectWithMargin().intersects(floatAvoiderRect);
323     };
324
325     ASSERT(m_leftIndex || m_rightIndex);
326     return intersects(left()) || intersects(right());
327 }
328
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
335 {
336     Optional<PositionInContextRoot> leftEdge;
337     Optional<PositionInContextRoot> rightEdge;
338
339     if (left())
340         leftEdge = PositionInContextRoot { left()->rectWithMargin().right() };
341
342     if (right())
343         rightEdge = PositionInContextRoot { right()->rectWithMargin().left() };
344
345     return { leftEdge, rightEdge };
346 }
347
348 PositionInContextRoot FloatingPair::bottom() const
349 {
350     auto* left = this->left();
351     auto* right = this->right();
352     ASSERT(left || right);
353
354     auto leftBottom = left ? Optional<PositionInContextRoot>(PositionInContextRoot { left->rectWithMargin().bottom() }) : WTF::nullopt;
355     auto rightBottom = right ? Optional<PositionInContextRoot>(PositionInContextRoot { right->rectWithMargin().bottom() }) : WTF::nullopt;
356
357     if (leftBottom && rightBottom)
358         return std::max(*leftBottom, *rightBottom);
359
360     if (leftBottom)
361         return *leftBottom;
362
363     return *rightBottom;
364 }
365
366 Iterator::Iterator(const FloatingState::FloatList& floats, Optional<PositionInContextRoot> verticalPosition)
367     : m_floats(floats)
368     , m_current(floats)
369 {
370     if (verticalPosition)
371         set(*verticalPosition);
372 }
373
374 inline static Optional<unsigned> previousFloatingIndex(Float floatingType, const FloatingState::FloatList& floats, unsigned currentIndex)
375 {
376     RELEASE_ASSERT(currentIndex <= floats.size());
377
378     while (currentIndex) {
379         auto& floating = floats[--currentIndex];
380         if ((floatingType == Float::Left && floating.isLeftPositioned()) || (floatingType == Float::Right && !floating.isLeftPositioned()))
381             return currentIndex;
382     }
383
384     return { };
385 }
386
387 Iterator& Iterator::operator++()
388 {
389     if (m_current.isEmpty()) {
390         ASSERT_NOT_REACHED();
391         return *this;
392     }
393
394     auto findPreviousFloatingWithLowerBottom = [&](Float floatingType, unsigned currentIndex) -> Optional<unsigned> {
395
396         RELEASE_ASSERT(currentIndex < m_floats.size());
397
398         // Last floating? There's certainly no previous floating at this point.
399         if (!currentIndex)
400             return { };
401
402         auto currentBottom = m_floats[currentIndex].rectWithMargin().bottom();
403
404         Optional<unsigned> index = currentIndex;
405         while (true) {
406             index = previousFloatingIndex(floatingType, m_floats, *index);
407             if (!index)
408                 return { };
409
410             if (m_floats[*index].rectWithMargin().bottom() > currentBottom)
411                 return index;
412         }
413
414         ASSERT_NOT_REACHED();
415         return { };
416     };
417
418     // 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).
419     // The current floats from left and right are considered the inner-most pair for the current vertical position.
420     // 2. Move away from inner-most pair by picking one of the previous floats in the list(#1)
421     // 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).
422     // 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.
423     // As the result we have more horizontal space on the current vertical position.
424     auto leftBottom = m_current.left() ? Optional<PositionInContextRoot>(m_current.left()->bottom()) : WTF::nullopt;
425     auto rightBottom = m_current.right() ? Optional<PositionInContextRoot>(m_current.right()->bottom()) : WTF::nullopt;
426
427     auto updateLeft = (leftBottom == rightBottom) || (!rightBottom || (leftBottom && leftBottom < rightBottom)); 
428     auto updateRight = (leftBottom == rightBottom) || (!leftBottom || (rightBottom && leftBottom > rightBottom)); 
429
430     if (updateLeft) {
431         ASSERT(m_current.m_leftIndex);
432         m_current.m_verticalPosition = *leftBottom;
433         m_current.m_leftIndex = findPreviousFloatingWithLowerBottom(Float::Left, *m_current.m_leftIndex);
434     }
435     
436     if (updateRight) {
437         ASSERT(m_current.m_rightIndex);
438         m_current.m_verticalPosition = *rightBottom;
439         m_current.m_rightIndex = findPreviousFloatingWithLowerBottom(Float::Right, *m_current.m_rightIndex);
440     }
441
442     return *this;
443 }
444
445 void Iterator::set(PositionInContextRoot verticalPosition)
446 {
447     // Move the iterator to the initial vertical position by starting at the inner-most floating pair (last floats on left/right).
448     // 1. Check if the inner-most pair covers the vertical position.
449     // 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
452     m_current.m_verticalPosition = verticalPosition;
453     // No floats at all?
454     if (m_floats.isEmpty()) {
455         ASSERT_NOT_REACHED();
456
457         m_current.m_leftIndex = { };
458         m_current.m_rightIndex = { };
459         return;
460     }
461
462     auto findFloatingBelow = [&](Float floatingType) -> Optional<unsigned> {
463
464         ASSERT(!m_floats.isEmpty());
465
466         auto index = floatingType == Float::Left ? m_current.m_leftIndex : m_current.m_rightIndex;
467         // Start from the end if we don't have current yet.
468         index = index.valueOr(m_floats.size());
469         while (true) {
470             index = previousFloatingIndex(floatingType, m_floats, *index);
471             if (!index)
472                 return { };
473
474             auto bottom = m_floats[*index].rectWithMargin().bottom();
475             // Is this floating intrusive on this position?
476             if (bottom > verticalPosition)
477                 return index;
478         }
479
480         return { };
481     };
482
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()));
488 }
489
490 bool Iterator::operator==(const Iterator& other) const
491 {
492     return m_current == other.m_current;
493 }
494
495 bool Iterator::operator!=(const Iterator& other) const
496 {
497     return !(*this == other);
498 }
499
500 }
501 }
502 #endif