5f831864660c194fe8e9673d81625b3360751250
[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 floatings.  
57
58 class Iterator;
59
60 class FloatingPair {
61 public:
62     FloatingPair(const LayoutContext&, const FloatingState&);
63
64     bool isEmpty() const { return !m_leftIndex && !m_rightIndex; }
65     const Display::Box* left() const;
66     const Display::Box* right() const;
67     bool intersects(const Display::Box::Rect&) const;
68     LayoutUnit verticalPosition() const { return m_verticalPosition; }
69     LayoutUnit bottom() const;
70     bool operator==(const FloatingPair&) const;
71
72 private:
73     friend class Iterator;
74     const LayoutContext& m_layoutContext;
75     const FloatingState& m_floatingState;
76
77     std::optional<unsigned> m_leftIndex;
78     std::optional<unsigned> m_rightIndex;
79     LayoutUnit m_verticalPosition;
80 };
81
82 class Iterator {
83 public:
84     Iterator(const LayoutContext&, const FloatingState&, std::optional<LayoutUnit> verticalPosition);
85
86     const FloatingPair& operator*() const { return m_current; }
87     Iterator& operator++();
88     bool operator==(const Iterator&) const;
89     bool operator!=(const Iterator&) const;
90
91 private:
92     void set(LayoutUnit verticalPosition);
93
94     const LayoutContext& m_layoutContext;
95     const FloatingState& m_floatingState;
96     FloatingPair m_current;
97 };
98
99 static Iterator begin(const LayoutContext& layoutContext, const FloatingState& floatingState, LayoutUnit initialVerticalPosition)
100 {
101     // Start with the inner-most floating pair for the initial vertical position.
102     return Iterator(layoutContext, floatingState, initialVerticalPosition);
103 }
104
105 static Iterator end(const LayoutContext& layoutContext, const FloatingState& floatingState)
106 {
107     return Iterator(layoutContext, floatingState, std::nullopt);
108 }
109
110 FloatingContext::FloatingContext(const Container& formattingContextRoot, FloatingState& floatingState)
111     : m_formattingContextRoot(formattingContextRoot)
112     , m_floatingState(floatingState)
113 {
114     ASSERT(m_formattingContextRoot.establishesFormattingContext());
115 }
116
117 Position FloatingContext::computePosition(const Box& layoutBox) const
118 {
119     ASSERT(layoutBox.isFloatingPositioned());
120
121     // 1. No floating box on the context yet -> align it with the containing block's left/right edge. 
122     if (m_floatingState.isEmpty())
123         return { alignWithContainingBlock(layoutBox), layoutContext().displayBoxForLayoutBox(layoutBox)->top() };
124
125     // 2. Find the top most position where the floating fits.
126     return floatingPosition(layoutBox); 
127 }
128
129 Position FloatingContext::floatingPosition(const Box& layoutBox) const
130 {
131     auto initialVerticalPosition = this->initialVerticalPosition(layoutBox);
132     auto boxSize = layoutContext().displayBoxForLayoutBox(layoutBox)->marginBox().size();
133
134     auto end = Layout::end(layoutContext(), m_floatingState);
135     auto top = initialVerticalPosition;
136     auto bottomMost = top;
137     for (auto iterator = begin(layoutContext(), m_floatingState, initialVerticalPosition); iterator != end; ++iterator) {
138         ASSERT(!(*iterator).isEmpty());
139
140         auto floatings = *iterator;
141         top = floatings.verticalPosition();
142
143         // Move the box horizontally so that it aligns with the current floating pair.
144         auto left = alignWithFloatings(floatings, layoutBox);
145         // Check if the box fits at this vertical position.
146         if (!floatings.intersects({ top, left, boxSize.width(), boxSize.height() }))
147             return { left, top };
148
149         bottomMost = floatings.bottom();
150         // Move to the next floating pair.
151     }
152
153     // Passed all the floatings and still does not fit? 
154     return { alignWithContainingBlock(layoutBox), bottomMost };
155 }
156
157 LayoutUnit FloatingContext::initialVerticalPosition(const Box& layoutBox) const
158 {
159     // Incoming floating cannot be placed higher than existing floatings.
160     // Take the static position (where the box would go if it wasn't floating) and adjust it with the last floating.
161     auto& displayBox = *layoutContext().displayBoxForLayoutBox(layoutBox);
162
163     if (auto lastFloating = m_floatingState.last())
164         return std::max(displayBox.top(), layoutContext().displayBoxForLayoutBox(*lastFloating)->top());
165
166     return displayBox.top();
167 }
168
169 LayoutUnit FloatingContext::alignWithContainingBlock(const Box& layoutBox) const
170 {
171     // If there is no floating to align with, push the box to the left/right edge of its containing block's content box.
172     // (Either there's no floatings at all or this box does not fit at any vertical positions where the floatings are.)
173     auto& layoutContext = m_floatingState.layoutContext();
174     auto* containingBlock = layoutBox.containingBlock();
175     ASSERT(containingBlock == &m_formattingContextRoot || containingBlock->isDescendantOf(m_formattingContextRoot));
176
177     auto* containgBlockDisplayBox = layoutContext.displayBoxForLayoutBox(*containingBlock);
178
179     if (layoutBox.isLeftFloatingPositioned())
180         return containgBlockDisplayBox->contentBoxLeft();
181
182     auto boxWidth = layoutContext.displayBoxForLayoutBox(layoutBox)->marginBox().width();
183     return containgBlockDisplayBox->contentBoxRight() - boxWidth;
184 }
185
186 LayoutUnit FloatingContext::alignWithFloatings(const FloatingPair& floatingPair, const Box& layoutBox) const
187 {
188     // Compute the horizontal position for the new floating by taking both the contining block and the current left/right floatings into account.
189     auto& containingBlock = *layoutContext().displayBoxForLayoutBox(*layoutBox.containingBlock());
190     auto containingBlockContentLeft = containingBlock.contentBoxLeft();
191     auto containingBlockContentRight = containingBlock.contentBoxRight();
192     auto marginBoxWidth = layoutContext().displayBoxForLayoutBox(layoutBox)->marginBox().width();
193
194     if (floatingPair.isEmpty()) {
195         ASSERT_NOT_REACHED();
196         return layoutBox.isLeftFloatingPositioned() ? containingBlockContentLeft : containingBlockContentRight - marginBoxWidth;
197     }
198
199     if (layoutBox.isLeftFloatingPositioned()) {
200         if (auto* leftDisplayBox = floatingPair.left()) 
201             return std::min(std::max(containingBlockContentLeft, leftDisplayBox->right()), containingBlockContentRight - marginBoxWidth);
202         
203         return containingBlockContentLeft;
204     }
205
206     ASSERT(layoutBox.isRightFloatingPositioned());
207
208     if (auto* rightDisplayBox = floatingPair.right())
209         return std::max(std::min(containingBlockContentRight, rightDisplayBox->left()) - marginBoxWidth, containingBlockContentLeft);
210
211     return containingBlockContentRight - marginBoxWidth;
212 }
213
214 static const Display::Box* floatingDisplayBox(unsigned index, const FloatingState::FloatingList& floatings, const LayoutContext& layoutContext)
215 {
216     RELEASE_ASSERT(index < floatings.size());
217     return layoutContext.displayBoxForLayoutBox(*floatings[index]);
218 }
219
220 FloatingPair::FloatingPair(const LayoutContext& layoutContext, const FloatingState& floatingState)
221     : m_layoutContext(layoutContext)
222     , m_floatingState(floatingState)
223 {
224 }
225
226 const Display::Box* FloatingPair::left() const
227 {
228     if (!m_leftIndex)
229         return nullptr;
230
231     return floatingDisplayBox(*m_leftIndex, m_floatingState.floatings().left, m_layoutContext);
232 }
233
234 const Display::Box* FloatingPair::right() const
235 {
236     if (!m_rightIndex)
237         return nullptr;
238
239     return floatingDisplayBox(*m_rightIndex, m_floatingState.floatings().right, m_layoutContext);
240 }
241
242 bool FloatingPair::intersects(const Display::Box::Rect& rect) const
243 {
244     auto intersects = [&](const Display::Box* floating, const Display::Box::Rect& rect) {
245         if (!floating)
246             return false;
247         // FIXME: use margin box here.
248         return floating->rect().intersects(rect);
249     };
250
251     if (!m_leftIndex && !m_rightIndex) {
252         ASSERT_NOT_REACHED();
253         return false;
254     }
255
256     if (intersects(left(), rect))
257         return true;
258
259     if (intersects(right(), rect))
260         return true;
261
262     return false;
263 }
264
265 bool FloatingPair::operator ==(const FloatingPair& other) const
266 {
267     return m_leftIndex == other.m_leftIndex && m_rightIndex == other.m_rightIndex;
268 }
269
270 LayoutUnit FloatingPair::bottom() const
271 {
272     auto* left = this->left();
273     auto* right = this->right();
274     ASSERT(left || right);
275
276     auto leftBottom = left ? std::optional<LayoutUnit>(left->bottom()) : std::nullopt;
277     auto rightBottom = right ? std::optional<LayoutUnit>(right->bottom()) : std::nullopt;
278
279     if (leftBottom && rightBottom)
280         return std::max(*leftBottom, *rightBottom);
281
282     if (leftBottom)
283         return *leftBottom;
284
285     return *rightBottom;
286 }
287
288 Iterator::Iterator(const LayoutContext& layoutContext, const FloatingState& floatingState, std::optional<LayoutUnit> verticalPosition)
289     : m_layoutContext(layoutContext)
290     , m_floatingState(floatingState)
291     , m_current(layoutContext, floatingState)
292 {
293     if (verticalPosition)
294         set(*verticalPosition);
295 }
296
297 Iterator& Iterator::operator++()
298 {
299     if (m_current.isEmpty()) {
300         ASSERT_NOT_REACHED();
301         return *this;
302     }
303
304     auto previousFloatingIndex = [&](const FloatingState::FloatingList& floatings, unsigned index) -> std::optional<unsigned> {
305
306         RELEASE_ASSERT(index < floatings.size());
307
308         if (!index)
309             return { };
310
311         auto currentBottom = floatingDisplayBox(index--, floatings, m_layoutContext)->bottom();
312         while (true) {
313             if (floatingDisplayBox(index, floatings, m_layoutContext)->bottom() > currentBottom)
314                 return index;
315             if (!index--)
316                 return { };
317         }
318
319         ASSERT_NOT_REACHED();
320         return { };
321     };
322
323     // 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).
324     // The current floatings from left and right are considered the inner-most pair for the current vertical position.
325     // 2. Move away from inner-most pair by picking one of the previous floatings in the list(#1)
326     // 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).
327     // 3. Reset the vertical position and align it with the new left-right pair. These floatings are now the inner-most boxes for the current vertical position.
328     // As the result we have more horizontal space on the current vertical position.
329     auto leftBottom = m_current.left() ? std::optional<LayoutUnit>(m_current.left()->bottom()) : std::nullopt;
330     auto rightBottom = m_current.right() ? std::optional<LayoutUnit>(m_current.right()->bottom()) : std::nullopt;
331
332     auto updateLeft = (leftBottom == rightBottom) || (!rightBottom || (leftBottom && leftBottom < rightBottom)); 
333     auto updateRight = (leftBottom == rightBottom) || (!leftBottom || (rightBottom && leftBottom > rightBottom)); 
334
335     if (updateLeft) {
336         ASSERT(m_current.m_leftIndex);
337         m_current.m_verticalPosition = *leftBottom;
338         m_current.m_leftIndex = previousFloatingIndex(m_floatingState.floatings().left, *m_current.m_leftIndex);
339     }
340     
341     if (updateRight) {
342         ASSERT(m_current.m_rightIndex);
343         m_current.m_verticalPosition = *rightBottom;
344         m_current.m_rightIndex = previousFloatingIndex(m_floatingState.floatings().right, *m_current.m_rightIndex);
345     }
346
347     return *this;
348 }
349
350 void Iterator::set(LayoutUnit verticalPosition)
351 {
352     // Move the iterator to the initial vertical position by starting at the inner-most floating pair (last floats on left/right).
353     // 1. Check if the inner-most pair covers the vertical position.
354     // 2. Move outwards from the inner-most pair until the vertical postion intersects.
355     // (Note that verticalPosition has already been adjusted with the top of the last float.)
356
357     m_current.m_verticalPosition = verticalPosition;
358     // No floatings at all?
359     if (m_floatingState.isEmpty()) {
360         ASSERT_NOT_REACHED();
361
362         m_current.m_leftIndex = { };
363         m_current.m_rightIndex = { };
364         return;
365     }
366
367     auto findFloatingBelow = [&](const FloatingState::FloatingList& list) -> std::optional<unsigned> {
368         
369         auto index = list.size(); 
370         while (index) {
371             auto bottom = floatingDisplayBox(--index, list, m_layoutContext)->bottom();
372             // Is this floating intrusive on this position?
373             if (bottom > verticalPosition)
374                 return index;
375         }
376         return { };
377     };
378
379     auto& floatings = m_floatingState.floatings();
380     m_current.m_leftIndex = findFloatingBelow(floatings.left);
381     m_current.m_rightIndex = findFloatingBelow(floatings.right);
382 }
383
384 bool Iterator::operator==(const Iterator& other) const
385 {
386     return m_current == other.m_current;
387 }
388
389 bool Iterator::operator!=(const Iterator& other) const
390 {
391     return !(*this == other);
392 }
393
394 }
395 }
396 #endif