[LFC] Layout::Box::containingBlock should return a const ContainerBox&
[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 "FormattingContext.h"
35 #include "LayoutBox.h"
36 #include "LayoutContainerBox.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 FloatPair {
66 public:
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::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
84 private:
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
93 class Iterator {
94 public:
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
102 private:
103     void set(PositionInContextRoot verticalPosition);
104
105     const FloatingState::FloatList& m_floats;
106     FloatPair m_current;
107 };
108
109 static 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
115 static Iterator end(const FloatingState::FloatList& floats)
116 {
117     return Iterator(floats, { });
118 }
119
120 #if ASSERT_ENABLED
121 static 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
152 struct FloatingContext::AbsoluteCoordinateValuesForFloatAvoider {
153     Display::Box displayBox;
154     LayoutPoint containingBlockTopLeft;
155     HorizontalEdges containingBlockContentBox;
156 };
157
158 FloatingContext::FloatingContext(const ContainerBox& floatingContextRoot, const FormattingContext& formattingContext, FloatingState& floatingState)
159     : m_root(makeWeakPtr(floatingContextRoot))
160     , m_formattingContext(formattingContext)
161     , m_floatingState(floatingState)
162 {
163 }
164
165 Point FloatingContext::positionForFloat(const Box& layoutBox, const HorizontalConstraints& horizontalConstraints) const
166 {
167     ASSERT(layoutBox.isFloatingPositioned());
168     ASSERT(areFloatsHorizontallySorted(m_floatingState));
169
170     if (isEmpty()) {
171         auto& boxGeometry = formattingContext().geometryForBox(layoutBox);
172
173         auto alignWithContainingBlock = [&]() -> Position {
174             // If there is no floating to align with, push the box to the left/right edge of its containing block's content box.
175             if (layoutBox.isLeftFloatingPositioned())
176                 return { horizontalConstraints.logicalLeft + boxGeometry.marginStart() };
177
178             return { horizontalConstraints.logicalRight() - boxGeometry.marginEnd() - boxGeometry.width() };
179         };
180
181         // No float box on the context yet -> align it with the containing block's left/right edge.
182         return { alignWithContainingBlock(), boxGeometry.top() };
183     }
184
185     // Find the top most position where the float box fits.
186     auto absoluteDisplayBoxCoordinates = this->absoluteDisplayBoxCoordinates(layoutBox);
187     ASSERT(!isEmpty());
188     auto previousFloatAbsoluteTop = floatingState().floats().last().rectWithMargin().top();
189     auto floatBox = FloatBox { layoutBox, absoluteDisplayBoxCoordinates.displayBox, absoluteDisplayBoxCoordinates.containingBlockTopLeft, absoluteDisplayBoxCoordinates.containingBlockContentBox, previousFloatAbsoluteTop };
190     findPositionForFloatBox(floatBox);
191     return floatBox.rectInContainingBlock().topLeft();
192 }
193
194 Optional<Point> FloatingContext::positionForFormattingContextRoot(const Box& layoutBox) const
195 {
196     ASSERT(layoutBox.establishesBlockFormattingContext());
197     ASSERT(!layoutBox.isFloatingPositioned());
198     ASSERT(!layoutBox.hasFloatClear());
199     ASSERT(areFloatsHorizontallySorted(m_floatingState));
200
201     if (isEmpty())
202         return { };
203
204     auto absoluteDisplayBoxCoordinates = this->absoluteDisplayBoxCoordinates(layoutBox);
205     auto floatAvoider = FloatAvoider { layoutBox, absoluteDisplayBoxCoordinates.displayBox, absoluteDisplayBoxCoordinates.containingBlockTopLeft, absoluteDisplayBoxCoordinates.containingBlockContentBox };
206     findPositionForFormattingContextRoot(floatAvoider);
207     return { floatAvoider.rectInContainingBlock().topLeft() };
208 }
209
210 FloatingContext::ClearancePosition FloatingContext::verticalPositionWithClearance(const Box& layoutBox) const
211 {
212     ASSERT(layoutBox.hasFloatClear());
213     ASSERT(layoutBox.isBlockLevelBox());
214     ASSERT(areFloatsHorizontallySorted(m_floatingState));
215
216     if (isEmpty())
217         return { };
218
219     auto bottom = [&](Optional<PositionInContextRoot> floatBottom) -> ClearancePosition {
220         // 'bottom' is in the formatting root's coordinate system.
221         if (!floatBottom)
222             return { };
223
224         // 9.5.2 Controlling flow next to floats: the 'clear' property
225         // Then the amount of clearance is set to the greater of:
226         //
227         // 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.
228         // 2. The amount necessary to place the top border edge of the block at its hypothetical position.
229         auto rootRelativeTop = mapTopToFloatingStateRoot(layoutBox);
230         auto clearance = *floatBottom - rootRelativeTop;
231         if (clearance <= 0)
232             return { };
233
234         // Clearance inhibits margin collapsing.
235         if (auto* previousInFlowSibling = layoutBox.previousInFlowSibling()) {
236             // Does this box with clearance actually collapse its margin before with the previous inflow box's margin after? 
237             auto verticalMargin = formattingContext().geometryForBox(layoutBox).verticalMargin();
238             if (verticalMargin.hasCollapsedValues() && verticalMargin.collapsedValues().before) {
239                 auto previousVerticalMargin = formattingContext().geometryForBox(*previousInFlowSibling).verticalMargin();
240                 auto collapsedMargin = *verticalMargin.collapsedValues().before;
241                 auto nonCollapsedMargin = previousVerticalMargin.after() + verticalMargin.before();
242                 auto marginDifference = nonCollapsedMargin - collapsedMargin;
243                 // Move the box to the position where it would be with non-collapsed margins.
244                 rootRelativeTop += marginDifference;
245                 // 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.
246                 clearance -= marginDifference;
247             }
248         }
249         // Now adjust the box's position with the clearance.
250         rootRelativeTop += clearance;
251         ASSERT(*floatBottom == rootRelativeTop);
252
253         // The return vertical position is in the containing block's coordinate system. Convert it to the formatting root's coordinate system if needed.
254         if (&layoutBox.containingBlock() == &m_floatingState.root())
255             return { Position { rootRelativeTop }, clearance };
256
257         auto containingBlockRootRelativeTop = mapTopToFloatingStateRoot(layoutBox.containingBlock());
258         return { Position { rootRelativeTop - containingBlockRootRelativeTop }, clearance };
259     };
260
261     auto clear = layoutBox.style().clear();
262     if (clear == Clear::Left)
263         return bottom(m_floatingState.leftBottom(root()));
264
265     if (clear == Clear::Right)
266         return bottom(m_floatingState.rightBottom(root()));
267
268     if (clear == Clear::Both)
269         return bottom(m_floatingState.bottom(root()));
270
271     ASSERT_NOT_REACHED();
272     return { };
273 }
274
275 FloatingContext::Constraints FloatingContext::constraints(LayoutUnit candidateTop, LayoutUnit candidateBottom) const
276 {
277     if (isEmpty())
278         return { };
279     // 1. Convert vertical position if this floating context is inherited.
280     // 2. Find the inner left/right floats at candidateTop/candidateBottom.
281     // 3. Convert left/right positions back to formattingContextRoot's cooridnate system.
282     auto coordinateMappingIsRequired = &floatingState().root() != &root();
283     auto adjustedCandidateTop = candidateTop;
284     LayoutSize adjustingDelta;
285     if (coordinateMappingIsRequired) {
286         auto adjustedCandidatePosition = mapPointFromFormattingContextRootToFloatingStateRoot({ 0, candidateTop });
287         adjustedCandidateTop = adjustedCandidatePosition.y;
288         adjustingDelta = { adjustedCandidatePosition.x, adjustedCandidateTop - candidateTop };
289     }
290     auto adjustedCandidateBottom = adjustedCandidateTop + (candidateBottom - candidateTop);
291     auto isCandidateEmpty = adjustedCandidateTop == adjustedCandidateBottom;
292
293     Constraints constraints;
294     auto& floats = floatingState().floats();
295     for (auto index = floats.size(); index--;) {
296         auto& floatItem = floats[index];
297
298         if (constraints.left && floatItem.isLeftPositioned())
299             continue;
300
301         if (constraints.right && !floatItem.isLeftPositioned())
302             continue;
303
304         auto floatBoxRect = floatItem.rectWithMargin();
305         auto contains = [&] {
306             if (isCandidateEmpty)
307                 return floatBoxRect.top() <= adjustedCandidateTop && floatBoxRect.bottom() > adjustedCandidateTop;
308             return floatBoxRect.top() < adjustedCandidateBottom && floatBoxRect.bottom() > adjustedCandidateTop;
309         };
310         if (!contains())
311             continue;
312
313         if (floatItem.isLeftPositioned())
314             constraints.left = PointInContextRoot { floatBoxRect.right(), floatBoxRect.bottom() };
315         else
316             constraints.right = PointInContextRoot { floatBoxRect.left(), floatBoxRect.bottom() };
317
318         if (constraints.left && constraints.right)
319             break;
320     }
321
322     if (coordinateMappingIsRequired) {
323         if (constraints.left)
324             constraints.left->move(-adjustingDelta);
325
326         if (constraints.right)
327             constraints.right->move(-adjustingDelta);
328     }
329     return constraints;
330 }
331
332 void FloatingContext::append(const Box& floatBox)
333 {
334     floatingState().append(FloatingState::FloatItem { floatBox, mapToFloatingStateRoot(floatBox) });
335 }
336
337 static FloatPair::LeftRightIndex findAvailablePosition(FloatAvoider& floatAvoider, const FloatingState::FloatList& floats)
338 {
339     Optional<PositionInContextRoot> bottomMost;
340     Optional<FloatPair::LeftRightIndex> innerMostLeftAndRight;
341     auto end = Layout::end(floats);
342     for (auto iterator = begin(floats, { floatAvoider.rect().top() }); iterator != end; ++iterator) {
343         ASSERT(!(*iterator).isEmpty());
344         auto leftRightFloatPair = *iterator;
345         innerMostLeftAndRight = innerMostLeftAndRight.valueOr(*leftRightFloatPair);
346
347         // Move the box horizontally so that it either
348         // 1. aligns with the current floating pair
349         // 2. or with the containing block's content box if there's no float to align with at this vertical position.
350         floatAvoider.setHorizontalConstraints(leftRightFloatPair.horizontalConstraints());
351         floatAvoider.setVerticalConstraint(leftRightFloatPair.verticalConstraint());
352
353         // Ensure that the float avoider
354         // 1. does not "overflow" its containing block with the current horiztonal constraints. It simply means that the float avoider's
355         // containing block could push the candidate position beyond the current float horizontally (too far to the left/right)
356         // 2. avoids floats on both sides.
357         if (!floatAvoider.overflowsContainingBlock() && !leftRightFloatPair.intersects(floatAvoider.rect()))
358             return *innerMostLeftAndRight;
359
360         bottomMost = leftRightFloatPair.bottom();
361         // Move to the next floating pair.
362     }
363
364     // The candidate box is already below of all the floats.
365     if (!bottomMost)
366         return { };
367
368     // Passed all the floats and still does not fit? Push it below the last float.
369     floatAvoider.setVerticalConstraint(*bottomMost);
370     floatAvoider.setHorizontalConstraints({ });
371     ASSERT(innerMostLeftAndRight);
372     return *innerMostLeftAndRight;
373 }
374
375 void FloatingContext::findPositionForFloatBox(FloatBox& floatBox) const
376 {
377     findAvailablePosition(floatBox, m_floatingState.floats());
378 }
379
380 void FloatingContext::findPositionForFormattingContextRoot(FloatAvoider& floatAvoider) const
381 {
382     // A non-floating formatting root's initial vertical position is its static position.
383     // It means that such boxes can end up vertically placed in-between existing floats (which is
384     // never the case for floats, since they cannot be placed above existing floats).
385     //  ____  ____
386     // |    || F1 |
387     // | L1 | ----
388     // |    |  ________
389     //  ----  |   R1   |
390     //         --------
391     // Document order: 1. float: left (L1) 2. float: right (R1) 3. formatting root (F1)
392     //
393     // 1. Probe for available placement at initial position (note it runs a backward probing algorithm at a specific vertical position)
394     // 2. Check if there's any intersecing float below (forward seaching)
395     // 3. Align the box with the intersected float and probe for placement again (#1). 
396     auto& floats = m_floatingState.floats();
397     while (true) {
398         auto innerMostLeftAndRight = findAvailablePosition(floatAvoider, floats);
399         if (innerMostLeftAndRight.isEmpty())
400             return;
401
402         auto overlappingFloatBox = [&floats](auto startFloatIndex, auto floatAvoiderRect) -> const FloatingState::FloatItem* {
403             for (auto i = startFloatIndex; i < floats.size(); ++i) {
404                 auto& floatBox = floats[i];
405                 if (floatBox.rectWithMargin().intersects(floatAvoiderRect))
406                     return &floatBox;
407             }
408             return nullptr;
409         };
410
411         auto startIndex = std::max(innerMostLeftAndRight.left.valueOr(0), innerMostLeftAndRight.right.valueOr(0)) + 1;
412         auto* intersectedFloatBox = overlappingFloatBox(startIndex, floatAvoider.rect());
413         if (!intersectedFloatBox)
414             return;
415         floatAvoider.setVerticalConstraint({ intersectedFloatBox->rectWithMargin().top() });
416     }
417 }
418
419 FloatingContext::AbsoluteCoordinateValuesForFloatAvoider FloatingContext::absoluteDisplayBoxCoordinates(const Box& floatAvoider) const
420 {
421     auto& containingBlock = floatAvoider.containingBlock();
422     auto displayBox = mapToFloatingStateRoot(floatAvoider);
423
424     if (&containingBlock == &floatingState().root()) {
425         auto containingBlockGeometry = formattingContext().geometryForBox(containingBlock, FormattingContext::EscapeReason::FloatBoxNeedsToBeInAbsoluteCoordinates);
426         return { displayBox, { }, {  containingBlockGeometry.contentBoxLeft(), containingBlockGeometry.contentBoxRight() } };
427     }
428     auto containingBlockAbsoluteDisplayBox = mapToFloatingStateRoot(containingBlock);
429     auto containingBlockLeft = containingBlockAbsoluteDisplayBox.left();
430     return { displayBox, containingBlockAbsoluteDisplayBox.topLeft(), { containingBlockLeft + containingBlockAbsoluteDisplayBox.contentBoxLeft(), containingBlockLeft + containingBlockAbsoluteDisplayBox.contentBoxRight() } };
431 }
432
433 Display::Box FloatingContext::mapToFloatingStateRoot(const Box& floatBox) const
434 {
435     auto& floatingStateRoot = floatingState().root();
436     auto& boxGeometry = formattingContext().geometryForBox(floatBox, FormattingContext::EscapeReason::FloatBoxNeedsToBeInAbsoluteCoordinates);
437     auto topLeft = boxGeometry.topLeft();
438     for (auto* containingBlock = &floatBox.containingBlock(); containingBlock != &floatingStateRoot; containingBlock = &containingBlock->containingBlock())
439         topLeft.moveBy(formattingContext().geometryForBox(*containingBlock, FormattingContext::EscapeReason::FloatBoxNeedsToBeInAbsoluteCoordinates).topLeft());
440
441     auto mappedDisplayBox = Display::Box(boxGeometry);
442     mappedDisplayBox.setTopLeft(topLeft);
443     return mappedDisplayBox;
444 }
445
446 LayoutUnit FloatingContext::mapTopToFloatingStateRoot(const Box& floatBox) const
447 {
448     auto& floatingStateRoot = floatingState().root();
449     auto top = formattingContext().geometryForBox(floatBox, FormattingContext::EscapeReason::FloatBoxNeedsToBeInAbsoluteCoordinates).top();
450     for (auto* containingBlock = &floatBox.containingBlock(); containingBlock != &floatingStateRoot; containingBlock = &containingBlock->containingBlock())
451         top += formattingContext().geometryForBox(*containingBlock, FormattingContext::EscapeReason::FloatBoxNeedsToBeInAbsoluteCoordinates).top();
452     return top;
453 }
454
455 Point FloatingContext::mapPointFromFormattingContextRootToFloatingStateRoot(Point position) const
456 {
457     auto& from = root();
458     auto& to = floatingState().root();
459     if (&from == &to)
460         return position;
461     auto mappedPosition = position;
462     for (auto* containingBlock = &from; containingBlock != &to; containingBlock = &containingBlock->containingBlock())
463         mappedPosition.moveBy(formattingContext().geometryForBox(*containingBlock, FormattingContext::EscapeReason::FloatBoxNeedsToBeInAbsoluteCoordinates).topLeft());
464     return mappedPosition;
465 }
466
467 FloatPair::FloatPair(const FloatingState::FloatList& floats)
468     : m_floats(floats)
469 {
470 }
471
472 const FloatingState::FloatItem* FloatPair::left() const
473 {
474     if (!m_floatPair.left)
475         return nullptr;
476
477     ASSERT(m_floats[*m_floatPair.left].isLeftPositioned());
478     return &m_floats[*m_floatPair.left];
479 }
480
481 const FloatingState::FloatItem* FloatPair::right() const
482 {
483     if (!m_floatPair.right)
484         return nullptr;
485
486     ASSERT(!m_floats[*m_floatPair.right].isLeftPositioned());
487     return &m_floats[*m_floatPair.right];
488 }
489
490 bool FloatPair::intersects(const Display::Rect& floatAvoiderRect) const
491 {
492     auto intersects = [&](auto* floating) {
493         return floating && floating->rectWithMargin().intersects(floatAvoiderRect);
494     };
495
496     ASSERT(!m_floatPair.isEmpty());
497     return intersects(left()) || intersects(right());
498 }
499
500 bool FloatPair::operator ==(const FloatPair& other) const
501 {
502     return m_floatPair.left == other.m_floatPair.left && m_floatPair.right == other.m_floatPair.right;
503 }
504
505 FloatAvoider::HorizontalConstraints FloatPair::horizontalConstraints() const
506 {
507     Optional<PositionInContextRoot> leftEdge;
508     Optional<PositionInContextRoot> rightEdge;
509
510     if (left())
511         leftEdge = PositionInContextRoot { left()->rectWithMargin().right() };
512
513     if (right())
514         rightEdge = PositionInContextRoot { right()->rectWithMargin().left() };
515
516     return { leftEdge, rightEdge };
517 }
518
519 PositionInContextRoot FloatPair::bottom() const
520 {
521     auto* left = this->left();
522     auto* right = this->right();
523     ASSERT(left || right);
524
525     auto leftBottom = left ? Optional<PositionInContextRoot>(PositionInContextRoot { left->rectWithMargin().bottom() }) : WTF::nullopt;
526     auto rightBottom = right ? Optional<PositionInContextRoot>(PositionInContextRoot { right->rectWithMargin().bottom() }) : WTF::nullopt;
527
528     if (leftBottom && rightBottom)
529         return std::max(*leftBottom, *rightBottom);
530
531     if (leftBottom)
532         return *leftBottom;
533
534     return *rightBottom;
535 }
536
537 Iterator::Iterator(const FloatingState::FloatList& floats, Optional<PositionInContextRoot> verticalPosition)
538     : m_floats(floats)
539     , m_current(floats)
540 {
541     if (verticalPosition)
542         set(*verticalPosition);
543 }
544
545 inline static Optional<unsigned> previousFloatingIndex(Float floatingType, const FloatingState::FloatList& floats, unsigned currentIndex)
546 {
547     RELEASE_ASSERT(currentIndex <= floats.size());
548
549     while (currentIndex) {
550         auto& floating = floats[--currentIndex];
551         if ((floatingType == Float::Left && floating.isLeftPositioned()) || (floatingType == Float::Right && !floating.isLeftPositioned()))
552             return currentIndex;
553     }
554
555     return { };
556 }
557
558 Iterator& Iterator::operator++()
559 {
560     if (m_current.isEmpty()) {
561         ASSERT_NOT_REACHED();
562         return *this;
563     }
564
565     auto findPreviousFloatingWithLowerBottom = [&](Float floatingType, unsigned currentIndex) -> Optional<unsigned> {
566
567         RELEASE_ASSERT(currentIndex < m_floats.size());
568
569         // Last floating? There's certainly no previous floating at this point.
570         if (!currentIndex)
571             return { };
572
573         auto currentBottom = m_floats[currentIndex].rectWithMargin().bottom();
574
575         Optional<unsigned> index = currentIndex;
576         while (true) {
577             index = previousFloatingIndex(floatingType, m_floats, *index);
578             if (!index)
579                 return { };
580
581             if (m_floats[*index].rectWithMargin().bottom() > currentBottom)
582                 return index;
583         }
584
585         ASSERT_NOT_REACHED();
586         return { };
587     };
588
589     // 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).
590     // The current floats from left and right are considered the inner-most pair for the current vertical position.
591     // 2. Move away from inner-most pair by picking one of the previous floats in the list(#1)
592     // 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).
593     // 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.
594     // As the result we have more horizontal space on the current vertical position.
595     auto leftBottom = m_current.left() ? Optional<PositionInContextRoot>(m_current.left()->bottom()) : WTF::nullopt;
596     auto rightBottom = m_current.right() ? Optional<PositionInContextRoot>(m_current.right()->bottom()) : WTF::nullopt;
597
598     auto updateLeft = (leftBottom == rightBottom) || (!rightBottom || (leftBottom && leftBottom < rightBottom)); 
599     auto updateRight = (leftBottom == rightBottom) || (!leftBottom || (rightBottom && leftBottom > rightBottom)); 
600
601     if (updateLeft) {
602         ASSERT(m_current.m_floatPair.left);
603         m_current.m_verticalPosition = *leftBottom;
604         m_current.m_floatPair.left = findPreviousFloatingWithLowerBottom(Float::Left, *m_current.m_floatPair.left);
605     }
606     
607     if (updateRight) {
608         ASSERT(m_current.m_floatPair.right);
609         m_current.m_verticalPosition = *rightBottom;
610         m_current.m_floatPair.right = findPreviousFloatingWithLowerBottom(Float::Right, *m_current.m_floatPair.right);
611     }
612
613     return *this;
614 }
615
616 void Iterator::set(PositionInContextRoot verticalPosition)
617 {
618     // Move the iterator to the initial vertical position by starting at the inner-most floating pair (last floats on left/right).
619     // 1. Check if the inner-most pair covers the vertical position.
620     // 2. Move outwards from the inner-most pair until the vertical postion intersects.
621     m_current.m_verticalPosition = verticalPosition;
622     // No floats at all?
623     if (m_floats.isEmpty()) {
624         ASSERT_NOT_REACHED();
625         m_current.m_floatPair = { };
626         return;
627     }
628
629     auto findFloatingBelow = [&](Float floatingType) -> Optional<unsigned> {
630
631         ASSERT(!m_floats.isEmpty());
632
633         auto index = floatingType == Float::Left ? m_current.m_floatPair.left : m_current.m_floatPair.right;
634         // Start from the end if we don't have current yet.
635         index = index.valueOr(m_floats.size());
636         while (true) {
637             index = previousFloatingIndex(floatingType, m_floats, *index);
638             if (!index)
639                 return { };
640
641             // Is this floating intrusive on this position?
642             auto rect = m_floats[*index].rectWithMargin();
643             if (rect.top() <= verticalPosition && rect.bottom() > verticalPosition)
644                 return index;
645         }
646
647         return { };
648     };
649
650     m_current.m_floatPair.left = findFloatingBelow(Float::Left);
651     m_current.m_floatPair.right = findFloatingBelow(Float::Right);
652
653     ASSERT(!m_current.m_floatPair.left || (*m_current.m_floatPair.left < m_floats.size() && m_floats[*m_current.m_floatPair.left].isLeftPositioned()));
654     ASSERT(!m_current.m_floatPair.right || (*m_current.m_floatPair.right < m_floats.size() && !m_floats[*m_current.m_floatPair.right].isLeftPositioned()));
655 }
656
657 bool Iterator::operator==(const Iterator& other) const
658 {
659     return m_current == other.m_current;
660 }
661
662 bool Iterator::operator!=(const Iterator& other) const
663 {
664     return !(*this == other);
665 }
666
667 }
668 }
669 #endif