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
39namespace WebCore {
40namespace Layout {
41
42WTF_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
63class Iterator;
64
65class FloatPair {
66public:
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(); }
75 const FloatingState::FloatItem* left() const;
76 const FloatingState::FloatItem* right() const;
77 bool intersects(const Display::Box::Rect&) const;
78 PositionInContextRoot verticalConstraint() const { return m_verticalPosition; }
79 FloatAvoider::HorizontalConstraints horizontalConstraints() const;
80 PositionInContextRoot bottom() const;
81 LeftRightIndex operator*() const { return m_floatPair; };
82 bool operator==(const FloatPair&) const;
83
84private:
85 friend class Iterator;
86 FloatPair(const FloatingState::FloatList&);
87
88 const FloatingState::FloatList& m_floats;
89 LeftRightIndex m_floatPair;
90 PositionInContextRoot m_verticalPosition;
91};
92
93class Iterator {
94public:
95 Iterator(const FloatingState::FloatList&, Optional<PositionInContextRoot> verticalPosition);
96
97 const FloatPair& operator*() const { return m_current; }
98 Iterator& operator++();
99 bool operator==(const Iterator&) const;
100 bool operator!=(const Iterator&) const;
101
102private:
103 void set(PositionInContextRoot verticalPosition);
104
105 const FloatingState::FloatList& m_floats;
106 FloatPair m_current;
107};
108
109static Iterator begin(const FloatingState::FloatList& floats, PositionInContextRoot initialVerticalPosition)
110{
111 // Start with the inner-most floating pair for the initial vertical position.
112 return Iterator(floats, initialVerticalPosition);
113}
114
115static Iterator end(const FloatingState::FloatList& floats)
116{
117 return Iterator(floats, { });
118}
119
120#ifndef NDEBUG
121static bool areFloatsHorizontallySorted(const FloatingState& floatingState)
122{
123 auto& floats = floatingState.floats();
124 auto rightEdgeOfLeftFloats = LayoutUnit::min();
125 auto leftEdgeOfRightFloats = LayoutUnit::max();
126 WTF::Optional<LayoutUnit> leftBottom;
127 WTF::Optional<LayoutUnit> rightBottom;
128
129 for (auto& floatItem : floats) {
130 if (floatItem.isLeftPositioned()) {
131 auto rightEdge = floatItem.rectWithMargin().right();
132 if (rightEdge < rightEdgeOfLeftFloats) {
133 if (leftBottom && floatItem.rectWithMargin().top() < *leftBottom)
134 return false;
135 }
136 leftBottom = floatItem.rectWithMargin().bottom();
137 rightEdgeOfLeftFloats = rightEdge;
138 } else {
139 auto leftEdge = floatItem.rectWithMargin().left();
140 if (leftEdge > leftEdgeOfRightFloats) {
141 if (rightBottom && floatItem.rectWithMargin().top() < *rightBottom)
142 return false;
143 }
144 rightBottom = floatItem.rectWithMargin().bottom();
145 leftEdgeOfRightFloats = leftEdge;
146 }
147 }
148 return true;
149}
150#endif
151
152FloatingContext::FloatingContext(FloatingState& floatingState)
153 : m_floatingState(floatingState)
154{
155}
156
157Point FloatingContext::positionForFloat(const Box& layoutBox) const
158{
159 ASSERT(layoutBox.isFloatingPositioned());
160 ASSERT(areFloatsHorizontallySorted(m_floatingState));
161
162 if (m_floatingState.isEmpty()) {
163 auto& displayBox = layoutState().displayBoxForLayoutBox(layoutBox);
164
165 auto alignWithContainingBlock = [&]() -> Position {
166 // If there is no floating to align with, push the box to the left/right edge of its containing block's content box.
167 auto& containingBlockDisplayBox = layoutState().displayBoxForLayoutBox(*layoutBox.containingBlock());
168
169 if (layoutBox.isLeftFloatingPositioned())
170 return Position { containingBlockDisplayBox.contentBoxLeft() + displayBox.marginStart() };
171
172 return Position { containingBlockDisplayBox.contentBoxRight() - displayBox.marginEnd() - displayBox.width() };
173 };
174
175 // No float box on the context yet -> align it with the containing block's left/right edge.
176 return { alignWithContainingBlock(), displayBox.top() };
177 }
178
179 // Find the top most position where the float box fits.
180 FloatBox floatBox = { layoutBox, m_floatingState, layoutState() };
181 findPositionForFloatBox(floatBox);
182 return floatBox.rectInContainingBlock().topLeft();
183}
184
185Optional<Point> FloatingContext::positionForFormattingContextRoot(const Box& layoutBox) const
186{
187 ASSERT(layoutBox.establishesBlockFormattingContext());
188 ASSERT(!layoutBox.isFloatingPositioned());
189 ASSERT(!layoutBox.hasFloatClear());
190 ASSERT(areFloatsHorizontallySorted(m_floatingState));
191
192 if (m_floatingState.isEmpty())
193 return { };
194
195 FloatAvoider floatAvoider = { layoutBox, m_floatingState, layoutState() };
196 findPositionForFormattingContextRoot(floatAvoider);
197 return { floatAvoider.rectInContainingBlock().topLeft() };
198}
199
200FloatingContext::ClearancePosition FloatingContext::verticalPositionWithClearance(const Box& layoutBox) const
201{
202 ASSERT(layoutBox.hasFloatClear());
203 ASSERT(layoutBox.isBlockLevelBox());
204 ASSERT(areFloatsHorizontallySorted(m_floatingState));
205
206 if (m_floatingState.isEmpty())
207 return { };
208
209 auto bottom = [&](Optional<PositionInContextRoot> floatBottom) -> ClearancePosition {
210 // 'bottom' is in the formatting root's coordinate system.
211 if (!floatBottom)
212 return { };
213
214 // 9.5.2 Controlling flow next to floats: the 'clear' property
215 // Then the amount of clearance is set to the greater of:
216 //
217 // 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.
218 // 2. The amount necessary to place the top border edge of the block at its hypothetical position.
219 auto& layoutState = this->layoutState();
220 auto rootRelativeTop = FormattingContext::mapTopToAncestor(layoutState, layoutBox, downcast<Container>(m_floatingState.root()));
221 auto clearance = *floatBottom - rootRelativeTop;
222 if (clearance <= 0)
223 return { };
224
225 // Clearance inhibits margin collapsing.
226 if (auto* previousInFlowSibling = layoutBox.previousInFlowSibling()) {
227 // Does this box with clearance actually collapse its margin before with the previous inflow box's margin after?
228 auto verticalMargin = layoutState.displayBoxForLayoutBox(layoutBox).verticalMargin();
229 if (verticalMargin.hasCollapsedValues() && verticalMargin.collapsedValues().before) {
230 auto previousVerticalMargin = layoutState.displayBoxForLayoutBox(*previousInFlowSibling).verticalMargin();
231 auto collapsedMargin = *verticalMargin.collapsedValues().before;
232 auto nonCollapsedMargin = previousVerticalMargin.after() + verticalMargin.before();
233 auto marginDifference = nonCollapsedMargin - collapsedMargin;
234 // Move the box to the position where it would be with non-collapsed margins.
235 rootRelativeTop += marginDifference;
236 // 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.
237 clearance -= marginDifference;
238 }
239 }
240 // Now adjust the box's position with the clearance.
241 rootRelativeTop += clearance;
242 ASSERT(*floatBottom == rootRelativeTop);
243
244 // The return vertical position is in the containing block's coordinate system. Convert it to the formatting root's coordinate system if needed.
245 if (layoutBox.containingBlock() == &m_floatingState.root())
246 return { Position { rootRelativeTop }, clearance };
247
248 auto containingBlockRootRelativeTop = FormattingContext::mapTopToAncestor(layoutState, *layoutBox.containingBlock(), downcast<Container>(m_floatingState.root()));
249 return { Position { rootRelativeTop - containingBlockRootRelativeTop }, clearance };
250 };
251
252 auto clear = layoutBox.style().clear();
253 auto& formattingContextRoot = layoutBox.formattingContextRoot();
254
255 if (clear == Clear::Left)
256 return bottom(m_floatingState.leftBottom(formattingContextRoot));
257
258 if (clear == Clear::Right)
259 return bottom(m_floatingState.rightBottom(formattingContextRoot));
260
261 if (clear == Clear::Both)
262 return bottom(m_floatingState.bottom(formattingContextRoot));
263
264 ASSERT_NOT_REACHED();
265 return { };
266}
267
268static FloatPair::LeftRightIndex findAvailablePosition(FloatAvoider& floatAvoider, const FloatingState::FloatList& floats)
269{
270 Optional<PositionInContextRoot> bottomMost;
271 Optional<FloatPair::LeftRightIndex> innerMostLeftAndRight;
272 auto end = Layout::end(floats);
273 for (auto iterator = begin(floats, { floatAvoider.rect().top() }); iterator != end; ++iterator) {
274 ASSERT(!(*iterator).isEmpty());
275 auto leftRightFloatPair = *iterator;
276 innerMostLeftAndRight = innerMostLeftAndRight.valueOr(*leftRightFloatPair);
277
278 // Move the box horizontally so that it either
279 // 1. aligns with the current floating pair
280 // 2. or with the containing block's content box if there's no float to align with at this vertical position.
281 floatAvoider.setHorizontalConstraints(leftRightFloatPair.horizontalConstraints());
282 floatAvoider.setVerticalConstraint(leftRightFloatPair.verticalConstraint());
283
284 // Ensure that the float avoider
285 // 1. does not "overflow" its containing block with the current horiztonal constraints. It simply means that the float avoider's
286 // containing block could push the candidate position beyond the current float horizontally (too far to the left/right)
287 // 2. avoids floats on both sides.
288 if (!floatAvoider.overflowsContainingBlock() && !leftRightFloatPair.intersects(floatAvoider.rect()))
289 return *innerMostLeftAndRight;
290
291 bottomMost = leftRightFloatPair.bottom();
292 // Move to the next floating pair.
293 }
294
295 // The candidate box is already below of all the floats.
296 if (!bottomMost)
297 return { };
298
299 // Passed all the floats and still does not fit? Push it below the last float.
300 floatAvoider.setVerticalConstraint(*bottomMost);
301 floatAvoider.setHorizontalConstraints({ });
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)
351 : m_floats(floats)
352{
353}
354
355const FloatingState::FloatItem* FloatPair::left() const
356{
357 if (!m_floatPair.left)
358 return nullptr;
359
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)
367 return nullptr;
368
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
374{
375 auto intersects = [&](auto* floating) {
376 return floating && floating->rectWithMargin().intersects(floatAvoiderRect);
377 };
378
379 ASSERT(!m_floatPair.isEmpty());
380 return intersects(left()) || intersects(right());
381}
382
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
389{
390 Optional<PositionInContextRoot> leftEdge;
391 Optional<PositionInContextRoot> rightEdge;
392
393 if (left())
394 leftEdge = PositionInContextRoot { left()->rectWithMargin().right() };
395
396 if (right())
397 rightEdge = PositionInContextRoot { right()->rectWithMargin().left() };
398
399 return { leftEdge, rightEdge };
400}
401
402PositionInContextRoot FloatPair::bottom() const
403{
404 auto* left = this->left();
405 auto* right = this->right();
406 ASSERT(left || right);
407
408 auto leftBottom = left ? Optional<PositionInContextRoot>(PositionInContextRoot { left->rectWithMargin().bottom() }) : WTF::nullopt;
409 auto rightBottom = right ? Optional<PositionInContextRoot>(PositionInContextRoot { right->rectWithMargin().bottom() }) : WTF::nullopt;
410
411 if (leftBottom && rightBottom)
412 return std::max(*leftBottom, *rightBottom);
413
414 if (leftBottom)
415 return *leftBottom;
416
417 return *rightBottom;
418}
419
420Iterator::Iterator(const FloatingState::FloatList& floats, Optional<PositionInContextRoot> verticalPosition)
421 : m_floats(floats)
422 , m_current(floats)
423{
424 if (verticalPosition)
425 set(*verticalPosition);
426}
427
428inline static Optional<unsigned> previousFloatingIndex(Float floatingType, const FloatingState::FloatList& floats, unsigned currentIndex)
429{
430 RELEASE_ASSERT(currentIndex <= floats.size());
431
432 while (currentIndex) {
433 auto& floating = floats[--currentIndex];
434 if ((floatingType == Float::Left && floating.isLeftPositioned()) || (floatingType == Float::Right && !floating.isLeftPositioned()))
435 return currentIndex;
436 }
437
438 return { };
439}
440
441Iterator& Iterator::operator++()
442{
443 if (m_current.isEmpty()) {
444 ASSERT_NOT_REACHED();
445 return *this;
446 }
447
448 auto findPreviousFloatingWithLowerBottom = [&](Float floatingType, unsigned currentIndex) -> Optional<unsigned> {
449
450 RELEASE_ASSERT(currentIndex < m_floats.size());
451
452 // Last floating? There's certainly no previous floating at this point.
453 if (!currentIndex)
454 return { };
455
456 auto currentBottom = m_floats[currentIndex].rectWithMargin().bottom();
457
458 Optional<unsigned> index = currentIndex;
459 while (true) {
460 index = previousFloatingIndex(floatingType, m_floats, *index);
461 if (!index)
462 return { };
463
464 if (m_floats[*index].rectWithMargin().bottom() > currentBottom)
465 return index;
466 }
467
468 ASSERT_NOT_REACHED();
469 return { };
470 };
471
472 // 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).
473 // The current floats from left and right are considered the inner-most pair for the current vertical position.
474 // 2. Move away from inner-most pair by picking one of the previous floats in the list(#1)
475 // 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).
476 // 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.
477 // As the result we have more horizontal space on the current vertical position.
478 auto leftBottom = m_current.left() ? Optional<PositionInContextRoot>(m_current.left()->bottom()) : WTF::nullopt;
479 auto rightBottom = m_current.right() ? Optional<PositionInContextRoot>(m_current.right()->bottom()) : WTF::nullopt;
480
481 auto updateLeft = (leftBottom == rightBottom) || (!rightBottom || (leftBottom && leftBottom < rightBottom));
482 auto updateRight = (leftBottom == rightBottom) || (!leftBottom || (rightBottom && leftBottom > rightBottom));
483
484 if (updateLeft) {
485 ASSERT(m_current.m_floatPair.left);
486 m_current.m_verticalPosition = *leftBottom;
487 m_current.m_floatPair.left = findPreviousFloatingWithLowerBottom(Float::Left, *m_current.m_floatPair.left);
488 }
489
490 if (updateRight) {
491 ASSERT(m_current.m_floatPair.right);
492 m_current.m_verticalPosition = *rightBottom;
493 m_current.m_floatPair.right = findPreviousFloatingWithLowerBottom(Float::Right, *m_current.m_floatPair.right);
494 }
495
496 return *this;
497}
498
499void Iterator::set(PositionInContextRoot verticalPosition)
500{
501 // Move the iterator to the initial vertical position by starting at the inner-most floating pair (last floats on left/right).
502 // 1. Check if the inner-most pair covers the vertical position.
503 // 2. Move outwards from the inner-most pair until the vertical postion intersects.
504 m_current.m_verticalPosition = verticalPosition;
505 // No floats at all?
506 if (m_floats.isEmpty()) {
507 ASSERT_NOT_REACHED();
508 m_current.m_floatPair = { };
509 return;
510 }
511
512 auto findFloatingBelow = [&](Float floatingType) -> Optional<unsigned> {
513
514 ASSERT(!m_floats.isEmpty());
515
516 auto index = floatingType == Float::Left ? m_current.m_floatPair.left : m_current.m_floatPair.right;
517 // Start from the end if we don't have current yet.
518 index = index.valueOr(m_floats.size());
519 while (true) {
520 index = previousFloatingIndex(floatingType, m_floats, *index);
521 if (!index)
522 return { };
523
524 // Is this floating intrusive on this position?
525 auto rect = m_floats[*index].rectWithMargin();
526 if (rect.top() <= verticalPosition && rect.bottom() > verticalPosition)
527 return index;
528 }
529
530 return { };
531 };
532
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()));
538}
539
540bool Iterator::operator==(const Iterator& other) const
541{
542 return m_current == other.m_current;
543}
544
545bool Iterator::operator!=(const Iterator& other) const
546{
547 return !(*this == other);
548}
549
550}
551}
552#endif
553