604bb273ceeec9ac9ed245e4d5c8a31688220999
[WebKit-https.git] / Source / WebCore / layout / FloatingContext.cpp
1 /*
2  * Copyright (C) 2018 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "FloatingContext.h"
28
29 #if ENABLE(LAYOUT_FORMATTING_CONTEXT)
30
31 #include "DisplayBox.h"
32 #include "LayoutBox.h"
33 #include "LayoutContainer.h"
34 #include "LayoutContext.h"
35 #include <wtf/IsoMallocInlines.h>
36
37 namespace WebCore {
38 namespace Layout {
39
40 WTF_MAKE_ISO_ALLOCATED_IMPL(FloatingContext);
41
42 // Finding the top/left position for a new floating(F)
43 //  ____  ____  _____               _______
44 // |    || L2 ||     | <-----1---->|       |
45 // |    ||____||  L3 |             |   R1  |
46 // | L1 |      |_____|             |       |
47 // |____| <-------------2--------->|       |
48 //                                 |       |
49 //                                 |_______|
50 //
51 // 1. Compute the initial vertical position for (F) -> (1)
52 // 2. Find the corresponding floating pair (L3-R1)
53 // 3. Align (F) horizontally with (L3-R1) depending whether (F) is left/right positioned
54 // 4. Intersect (F) with (L3-R1)
55 // 5. If (F) does not fit, find the next floating pair (L1-R1)
56 // 6. Repeat until either (F) fits/no more floats.
57 // Note that all coordinates are in the coordinate system of the formatting root.
58 // The formatting root here is always the one that establishes the floating context (see inherited floating context).
59 // (It simply means that the float box's formatting root is not necessarily the same as the FormattingContext's root.)
60
61 class Iterator;
62
63 class FloatingPair {
64 public:
65     bool isEmpty() const { return !m_leftIndex && !m_rightIndex; }
66     const Display::Box* left() const;
67     const Display::Box* right() const;
68     bool intersects(const Display::Box::Rect&) const;
69     LayoutUnit verticalPosition() const { return m_verticalPosition; }
70     LayoutUnit bottom() const;
71     bool operator==(const FloatingPair&) const;
72
73 private:
74     friend class Iterator;
75     FloatingPair(const LayoutContext&, const FloatingState::FloatList&);
76
77     const LayoutContext& m_layoutContext;
78     const FloatingState::FloatList& m_floats;
79
80     std::optional<unsigned> m_leftIndex;
81     std::optional<unsigned> m_rightIndex;
82     LayoutUnit m_verticalPosition;
83 };
84
85 class Iterator {
86 public:
87     Iterator(const LayoutContext&, const FloatingState::FloatList&, std::optional<LayoutUnit> verticalPosition);
88
89     const FloatingPair& operator*() const { return m_current; }
90     Iterator& operator++();
91     bool operator==(const Iterator&) const;
92     bool operator!=(const Iterator&) const;
93
94 private:
95     void set(LayoutUnit verticalPosition);
96
97     const LayoutContext& m_layoutContext;
98     const FloatingState::FloatList& m_floats;
99     FloatingPair m_current;
100 };
101
102 static Iterator begin(const LayoutContext& layoutContext, const FloatingState& floatingState, LayoutUnit initialVerticalPosition)
103 {
104     // Start with the inner-most floating pair for the initial vertical position.
105     return Iterator(layoutContext, floatingState.floats(), initialVerticalPosition);
106 }
107
108 static Iterator end(const LayoutContext& layoutContext, const FloatingState& floatingState)
109 {
110     return Iterator(layoutContext, floatingState.floats(), std::nullopt);
111 }
112
113 FloatingContext::FloatingContext(FloatingState& floatingState)
114     : m_floatingState(floatingState)
115 {
116 }
117
118 Position FloatingContext::computePosition(const Box& layoutBox) const
119 {
120     ASSERT(layoutBox.isFloatingPositioned());
121     FloatingState::FloatItem floatItem = { layoutBox, m_floatingState };
122
123     Position floatPosition;
124     if (m_floatingState.isEmpty()) {
125         // No float box on the context yet -> align it with the containing block's left/right edge.
126         auto& displayBox = floatItem.displayBox();
127         floatPosition = { alignWithContainingBlock(floatItem) + displayBox.marginLeft(), displayBox.top() };
128     } else {
129         // Find the top most position where the float box fits.
130         floatPosition = floatingPosition(floatItem);
131     }
132
133     return toContainingBlock(floatItem, floatPosition);
134 }
135
136 Position FloatingContext::floatingPosition(const FloatingState::FloatItem& floatItem) const
137 {
138     auto initialVerticalPosition = this->initialVerticalPosition(floatItem);
139     auto& displayBox = floatItem.displayBox();
140     auto marginBoxSize = displayBox.marginBox().size();
141
142     auto end = Layout::end(layoutContext(), m_floatingState);
143     auto top = initialVerticalPosition;
144     auto bottomMost = top;
145     for (auto iterator = begin(layoutContext(), m_floatingState, initialVerticalPosition); iterator != end; ++iterator) {
146         ASSERT(!(*iterator).isEmpty());
147
148         auto floats = *iterator;
149         top = floats.verticalPosition();
150
151         // Move the box horizontally so that it aligns with the current floating pair.
152         auto left = alignWithFloatings(floats, floatItem);
153         // Check if the box fits at this vertical position.
154         if (!floats.intersects({ top, left, marginBoxSize.width(), marginBoxSize.height() }))
155             return { left + displayBox.marginLeft(), top + displayBox.marginTop() };
156
157         bottomMost = floats.bottom();
158         // Move to the next floating pair.
159     }
160
161     // Passed all the floats and still does not fit?
162     return { alignWithContainingBlock(floatItem) + displayBox.marginLeft(), bottomMost + displayBox.marginTop() };
163 }
164
165 LayoutUnit FloatingContext::initialVerticalPosition(const FloatingState::FloatItem& floatItem) const
166 {
167     // Incoming floating cannot be placed higher than existing floats.
168     // Take the static position (where the box would go if it wasn't floating) and adjust it with the last floating.
169     auto marginBoxTop = floatItem.displayBox().rectWithMargin().top();
170
171     if (auto lastFloat = m_floatingState.last())
172         return std::max(marginBoxTop, lastFloat->displayBox().rectWithMargin().top());
173
174     return marginBoxTop;
175 }
176
177 LayoutUnit FloatingContext::alignWithContainingBlock(const FloatingState::FloatItem& floatItem) const
178 {
179     // If there is no floating to align with, push the box to the left/right edge of its containing block's content box.
180     // (Either there's no floats at all or this box does not fit at any vertical positions where the floats are.)
181     auto& containgBlockDisplayBox = floatItem.containingBlockDisplayBox();
182     auto containingBlockContentBoxLeft = containgBlockDisplayBox.left() + containgBlockDisplayBox.contentBoxLeft();
183
184     if (floatItem.layoutBox().isLeftFloatingPositioned())
185         return containingBlockContentBoxLeft;
186
187     return containingBlockContentBoxLeft + containgBlockDisplayBox.contentBoxWidth() - floatItem.displayBox().marginBox().width();
188 }
189
190 LayoutUnit FloatingContext::alignWithFloatings(const FloatingPair& floatingPair, const FloatingState::FloatItem& floatItem) const
191 {
192     // Compute the horizontal position for the new floating by taking both the contining block and the current left/right floats into account.
193     auto& containingBlockDisplayBox = floatItem.containingBlockDisplayBox();
194     auto containingBlockContentBoxLeft = containingBlockDisplayBox.left() + containingBlockDisplayBox.contentBoxLeft();
195     auto containingBlockContentBoxRight = containingBlockDisplayBox.left() + containingBlockDisplayBox.contentBoxRight();
196     auto marginBoxWidth = floatItem.displayBox().marginBox().width();
197
198     auto leftAlignedBoxLeft = containingBlockContentBoxLeft;
199     auto rightAlignedBoxLeft = containingBlockContentBoxRight - marginBoxWidth;
200
201     if (floatingPair.isEmpty()) {
202         ASSERT_NOT_REACHED();
203         return floatItem.layoutBox().isLeftFloatingPositioned() ? leftAlignedBoxLeft : rightAlignedBoxLeft;
204     }
205
206     if (floatItem.layoutBox().isLeftFloatingPositioned()) {
207         if (auto* leftDisplayBox = floatingPair.left()) {
208             auto leftFloatingBoxRight = leftDisplayBox->rectWithMargin().right();
209             return std::min(std::max(leftAlignedBoxLeft, leftFloatingBoxRight), rightAlignedBoxLeft);
210         }
211         
212         return leftAlignedBoxLeft;
213     }
214
215     ASSERT(floatItem.layoutBox().isRightFloatingPositioned());
216
217     if (auto* rightDisplayBox = floatingPair.right()) {
218         auto rightFloatingBoxLeft = rightDisplayBox->rectWithMargin().left();
219         return std::max(std::min(rightAlignedBoxLeft, rightFloatingBoxLeft - marginBoxWidth), leftAlignedBoxLeft);
220     }
221
222     return rightAlignedBoxLeft;
223 }
224
225 // FIXME: find a better place for this.
226 Position FloatingContext::toContainingBlock(const FloatingState::FloatItem& floatItem, Position position) const
227 {
228     // From formatting root coordinate system back to containing block's.
229     if (&floatItem.containingBlock() == &m_floatingState.root())
230         return position;
231
232     auto& containgBlockDisplayBox = floatItem.containingBlockDisplayBox();
233     return { position.x - containgBlockDisplayBox.left(), position.y - containgBlockDisplayBox.top() };
234 }
235
236 FloatingPair::FloatingPair(const LayoutContext& layoutContext, const FloatingState::FloatList& floats)
237     : m_layoutContext(layoutContext)
238     , m_floats(floats)
239 {
240 }
241
242 const Display::Box* FloatingPair::left() const
243 {
244     if (!m_leftIndex)
245         return nullptr;
246
247     ASSERT(m_floats[*m_leftIndex].layoutBox().isLeftFloatingPositioned());
248     return &m_floats[*m_leftIndex].displayBox();
249 }
250
251 const Display::Box* FloatingPair::right() const
252 {
253     if (!m_rightIndex)
254         return nullptr;
255
256     ASSERT(m_floats[*m_rightIndex].layoutBox().isRightFloatingPositioned());
257     return &m_floats[*m_rightIndex].displayBox();
258 }
259
260 bool FloatingPair::intersects(const Display::Box::Rect& candidateRect) const
261 {
262     auto intersects = [&](const Display::Box* floating, Float floatingType) {
263         if (!floating)
264             return false;
265
266         auto marginRect = floating->rectWithMargin();
267         // Before intersecting, check if the candidate position is too far to the left/right.
268         // The new float's containing block could push the candidate position beyond the current float horizontally.
269         if ((floatingType == Float::Left && candidateRect.left() < marginRect.right())
270             || (floatingType == Float::Right && candidateRect.right() > marginRect.left()))
271             return true;
272         return marginRect.intersects(candidateRect);
273     };
274
275     if (!m_leftIndex && !m_rightIndex) {
276         ASSERT_NOT_REACHED();
277         return false;
278     }
279
280     if (intersects(left(), Float::Left))
281         return true;
282
283     if (intersects(right(), Float::Right))
284         return true;
285
286     return false;
287 }
288
289 bool FloatingPair::operator ==(const FloatingPair& other) const
290 {
291     return m_leftIndex == other.m_leftIndex && m_rightIndex == other.m_rightIndex;
292 }
293
294 LayoutUnit FloatingPair::bottom() const
295 {
296     auto* left = this->left();
297     auto* right = this->right();
298     ASSERT(left || right);
299
300     auto leftBottom = left ? std::optional<LayoutUnit>(left->rectWithMargin().bottom()) : std::nullopt;
301     auto rightBottom = right ? std::optional<LayoutUnit>(right->rectWithMargin().bottom()) : std::nullopt;
302
303     if (leftBottom && rightBottom)
304         return std::max(*leftBottom, *rightBottom);
305
306     if (leftBottom)
307         return *leftBottom;
308
309     return *rightBottom;
310 }
311
312 Iterator::Iterator(const LayoutContext& layoutContext, const FloatingState::FloatList& floats, std::optional<LayoutUnit> verticalPosition)
313     : m_layoutContext(layoutContext)
314     , m_floats(floats)
315     , m_current(layoutContext, floats)
316 {
317     if (verticalPosition)
318         set(*verticalPosition);
319 }
320
321 inline static std::optional<unsigned> previousFloatingIndex(Float floatingType, const FloatingState::FloatList& floats, unsigned currentIndex)
322 {
323     RELEASE_ASSERT(currentIndex <= floats.size());
324
325     while (currentIndex) {
326         auto& floating = floats[--currentIndex].layoutBox();
327         if ((floatingType == Float::Left && floating.isLeftFloatingPositioned()) || (floatingType == Float::Right && floating.isRightFloatingPositioned()))
328             return currentIndex;
329     }
330
331     return { };
332 }
333
334 Iterator& Iterator::operator++()
335 {
336     if (m_current.isEmpty()) {
337         ASSERT_NOT_REACHED();
338         return *this;
339     }
340
341     auto findPreviousFloatingWithLowerBottom = [&](Float floatingType, unsigned currentIndex) -> std::optional<unsigned> {
342
343         RELEASE_ASSERT(currentIndex < m_floats.size());
344
345         // Last floating? There's certainly no previous floating at this point.
346         if (!currentIndex)
347             return { };
348
349         auto currentBottom = m_floats[currentIndex].displayBox().rectWithMargin().bottom();
350
351         std::optional<unsigned> index = currentIndex;
352         while (true) {
353             index = previousFloatingIndex(floatingType, m_floats, *index);
354             if (!index)
355                 return { };
356
357             if (m_floats[*index].displayBox().rectWithMargin().bottom() > currentBottom)
358                 return index;
359         }
360
361         ASSERT_NOT_REACHED();
362         return { };
363     };
364
365     // 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).
366     // The current floats from left and right are considered the inner-most pair for the current vertical position.
367     // 2. Move away from inner-most pair by picking one of the previous floats in the list(#1)
368     // 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).
369     // 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.
370     // As the result we have more horizontal space on the current vertical position.
371     auto leftBottom = m_current.left() ? std::optional<LayoutUnit>(m_current.left()->bottom()) : std::nullopt;
372     auto rightBottom = m_current.right() ? std::optional<LayoutUnit>(m_current.right()->bottom()) : std::nullopt;
373
374     auto updateLeft = (leftBottom == rightBottom) || (!rightBottom || (leftBottom && leftBottom < rightBottom)); 
375     auto updateRight = (leftBottom == rightBottom) || (!leftBottom || (rightBottom && leftBottom > rightBottom)); 
376
377     if (updateLeft) {
378         ASSERT(m_current.m_leftIndex);
379         m_current.m_verticalPosition = *leftBottom;
380         m_current.m_leftIndex = findPreviousFloatingWithLowerBottom(Float::Left, *m_current.m_leftIndex);
381     }
382     
383     if (updateRight) {
384         ASSERT(m_current.m_rightIndex);
385         m_current.m_verticalPosition = *rightBottom;
386         m_current.m_rightIndex = findPreviousFloatingWithLowerBottom(Float::Right, *m_current.m_rightIndex);
387     }
388
389     return *this;
390 }
391
392 void Iterator::set(LayoutUnit verticalPosition)
393 {
394     // Move the iterator to the initial vertical position by starting at the inner-most floating pair (last floats on left/right).
395     // 1. Check if the inner-most pair covers the vertical position.
396     // 2. Move outwards from the inner-most pair until the vertical postion intersects.
397     // (Note that verticalPosition has already been adjusted with the top of the last float.)
398
399     m_current.m_verticalPosition = verticalPosition;
400     // No floats at all?
401     if (m_floats.isEmpty()) {
402         ASSERT_NOT_REACHED();
403
404         m_current.m_leftIndex = { };
405         m_current.m_rightIndex = { };
406         return;
407     }
408
409     auto findFloatingBelow = [&](Float floatingType) -> std::optional<unsigned> {
410
411         ASSERT(!m_floats.isEmpty());
412
413         auto index = floatingType == Float::Left ? m_current.m_leftIndex : m_current.m_rightIndex;
414         // Start from the end if we don't have current yet.
415         index = index.value_or(m_floats.size());
416         while (true) {
417             index = previousFloatingIndex(floatingType, m_floats, *index);
418             if (!index)
419                 return { };
420
421             auto bottom = m_floats[*index].displayBox().rectWithMargin().bottom();
422             // Is this floating intrusive on this position?
423             if (bottom > verticalPosition)
424                 return index;
425         }
426
427         return { };
428     };
429
430     m_current.m_leftIndex = findFloatingBelow(Float::Left);
431     m_current.m_rightIndex = findFloatingBelow(Float::Right);
432
433     ASSERT(!m_current.m_leftIndex || (*m_current.m_leftIndex < m_floats.size() && m_floats[*m_current.m_leftIndex].layoutBox().isLeftFloatingPositioned()));
434     ASSERT(!m_current.m_rightIndex || (*m_current.m_rightIndex < m_floats.size() && m_floats[*m_current.m_rightIndex].layoutBox().isRightFloatingPositioned()));
435 }
436
437 bool Iterator::operator==(const Iterator& other) const
438 {
439     return m_current == other.m_current;
440 }
441
442 bool Iterator::operator!=(const Iterator& other) const
443 {
444     return !(*this == other);
445 }
446
447 }
448 }
449 #endif