[LFC][Floating] Use margin box consistently while placing a floating.
[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         auto* displayBox = layoutContext().displayBoxForLayoutBox(layoutBox);
124         return { alignWithContainingBlock(layoutBox) + displayBox->marginLeft(), displayBox->top() };
125     }
126
127     // 2. Find the top most position where the floating fits.
128     return floatingPosition(layoutBox); 
129 }
130
131 Position FloatingContext::floatingPosition(const Box& layoutBox) const
132 {
133     auto initialVerticalPosition = this->initialVerticalPosition(layoutBox);
134     auto* displayBox = layoutContext().displayBoxForLayoutBox(layoutBox);
135     auto marginBoxSize = displayBox->marginBox().size();
136
137     auto end = Layout::end(layoutContext(), m_floatingState);
138     auto top = initialVerticalPosition;
139     auto bottomMost = top;
140     for (auto iterator = begin(layoutContext(), m_floatingState, initialVerticalPosition); iterator != end; ++iterator) {
141         ASSERT(!(*iterator).isEmpty());
142
143         auto floatings = *iterator;
144         top = floatings.verticalPosition();
145
146         // Move the box horizontally so that it aligns with the current floating pair.
147         auto left = alignWithFloatings(floatings, layoutBox);
148         // Check if the box fits at this vertical position.
149         if (!floatings.intersects({ top, left, marginBoxSize.width(), marginBoxSize.height() }))
150             return { left + displayBox->marginLeft(), top + displayBox->marginTop() };
151
152         bottomMost = floatings.bottom();
153         // Move to the next floating pair.
154     }
155
156     // Passed all the floatings and still does not fit? 
157     return { alignWithContainingBlock(layoutBox) + displayBox->marginLeft(), bottomMost + displayBox->marginTop() };
158 }
159
160 LayoutUnit FloatingContext::initialVerticalPosition(const Box& layoutBox) const
161 {
162     // Incoming floating cannot be placed higher than existing floatings.
163     // Take the static position (where the box would go if it wasn't floating) and adjust it with the last floating.
164     auto marginBoxTop = layoutContext().displayBoxForLayoutBox(layoutBox)->rectWithMargin().top();
165
166     if (auto lastFloating = m_floatingState.last())
167         return std::max(marginBoxTop, layoutContext().displayBoxForLayoutBox(*lastFloating)->rectWithMargin().top());
168
169     return marginBoxTop;
170 }
171
172 LayoutUnit FloatingContext::alignWithContainingBlock(const Box& layoutBox) const
173 {
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     // (Either there's no floatings at all or this box does not fit at any vertical positions where the floatings are.)
176     auto* displayBox = layoutContext().displayBoxForLayoutBox(layoutBox);
177     auto* containingBlock = layoutBox.containingBlock();
178     ASSERT(containingBlock == &m_formattingContextRoot || containingBlock->isDescendantOf(m_formattingContextRoot));
179
180     auto* containgBlockDisplayBox = layoutContext().displayBoxForLayoutBox(*containingBlock);
181
182     if (layoutBox.isLeftFloatingPositioned())
183         return containgBlockDisplayBox->contentBoxLeft();
184
185     return containgBlockDisplayBox->contentBoxRight() - displayBox->marginBox().width();
186 }
187
188 LayoutUnit FloatingContext::alignWithFloatings(const FloatingPair& floatingPair, const Box& layoutBox) const
189 {
190     // Compute the horizontal position for the new floating by taking both the contining block and the current left/right floatings into account.
191     auto* displayBox = layoutContext().displayBoxForLayoutBox(layoutBox);
192     auto& containingBlock = *layoutContext().displayBoxForLayoutBox(*layoutBox.containingBlock());
193     auto containingBlockContentBoxLeft = containingBlock.contentBoxLeft();
194     auto containingBlockContentBoxRight = containingBlock.contentBoxRight();
195     auto marginBoxWidth = displayBox->marginBox().width();
196
197     auto leftAlignedBoxLeft = containingBlockContentBoxLeft;
198     auto rightAlignedBoxLeft = containingBlockContentBoxRight - displayBox->marginBox().width();
199
200     if (floatingPair.isEmpty()) {
201         ASSERT_NOT_REACHED();
202         return layoutBox.isLeftFloatingPositioned() ? leftAlignedBoxLeft : rightAlignedBoxLeft;
203     }
204
205     if (layoutBox.isLeftFloatingPositioned()) {
206         if (auto* leftDisplayBox = floatingPair.left()) {
207             auto leftFloatingBoxRight = leftDisplayBox->rectWithMargin().right();
208             return std::min(std::max(leftAlignedBoxLeft, leftFloatingBoxRight), rightAlignedBoxLeft);
209         }
210         
211         return leftAlignedBoxLeft;
212     }
213
214     ASSERT(layoutBox.isRightFloatingPositioned());
215
216     if (auto* rightDisplayBox = floatingPair.right()) {
217         auto rightFloatingBoxLeft = rightDisplayBox->rectWithMargin().left();
218         return std::max(std::min(rightAlignedBoxLeft, rightFloatingBoxLeft) - marginBoxWidth, leftAlignedBoxLeft);
219     }
220
221     return rightAlignedBoxLeft;
222 }
223
224 static const Display::Box* floatingDisplayBox(unsigned index, const FloatingState::FloatingList& floatings, const LayoutContext& layoutContext)
225 {
226     RELEASE_ASSERT(index < floatings.size());
227     return layoutContext.displayBoxForLayoutBox(*floatings[index]);
228 }
229
230 FloatingPair::FloatingPair(const LayoutContext& layoutContext, const FloatingState& floatingState)
231     : m_layoutContext(layoutContext)
232     , m_floatingState(floatingState)
233 {
234 }
235
236 const Display::Box* FloatingPair::left() const
237 {
238     if (!m_leftIndex)
239         return nullptr;
240
241     return floatingDisplayBox(*m_leftIndex, m_floatingState.floatings().left, m_layoutContext);
242 }
243
244 const Display::Box* FloatingPair::right() const
245 {
246     if (!m_rightIndex)
247         return nullptr;
248
249     return floatingDisplayBox(*m_rightIndex, m_floatingState.floatings().right, m_layoutContext);
250 }
251
252 bool FloatingPair::intersects(const Display::Box::Rect& rect) const
253 {
254     auto intersects = [&](const Display::Box* floating, const Display::Box::Rect& rect) {
255         if (!floating)
256             return false;
257
258         return floating->rectWithMargin().intersects(rect);
259     };
260
261     if (!m_leftIndex && !m_rightIndex) {
262         ASSERT_NOT_REACHED();
263         return false;
264     }
265
266     if (intersects(left(), rect))
267         return true;
268
269     if (intersects(right(), rect))
270         return true;
271
272     return false;
273 }
274
275 bool FloatingPair::operator ==(const FloatingPair& other) const
276 {
277     return m_leftIndex == other.m_leftIndex && m_rightIndex == other.m_rightIndex;
278 }
279
280 LayoutUnit FloatingPair::bottom() const
281 {
282     auto* left = this->left();
283     auto* right = this->right();
284     ASSERT(left || right);
285
286     auto leftBottom = left ? std::optional<LayoutUnit>(left->bottom()) : std::nullopt;
287     auto rightBottom = right ? std::optional<LayoutUnit>(right->bottom()) : std::nullopt;
288
289     if (leftBottom && rightBottom)
290         return std::max(*leftBottom, *rightBottom);
291
292     if (leftBottom)
293         return *leftBottom;
294
295     return *rightBottom;
296 }
297
298 Iterator::Iterator(const LayoutContext& layoutContext, const FloatingState& floatingState, std::optional<LayoutUnit> verticalPosition)
299     : m_layoutContext(layoutContext)
300     , m_floatingState(floatingState)
301     , m_current(layoutContext, floatingState)
302 {
303     if (verticalPosition)
304         set(*verticalPosition);
305 }
306
307 Iterator& Iterator::operator++()
308 {
309     if (m_current.isEmpty()) {
310         ASSERT_NOT_REACHED();
311         return *this;
312     }
313
314     auto previousFloatingIndex = [&](const FloatingState::FloatingList& floatings, unsigned index) -> std::optional<unsigned> {
315
316         RELEASE_ASSERT(index < floatings.size());
317
318         if (!index)
319             return { };
320
321         auto currentBottom = floatingDisplayBox(index--, floatings, m_layoutContext)->bottom();
322         while (true) {
323             if (floatingDisplayBox(index, floatings, m_layoutContext)->bottom() > currentBottom)
324                 return index;
325             if (!index--)
326                 return { };
327         }
328
329         ASSERT_NOT_REACHED();
330         return { };
331     };
332
333     // 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).
334     // The current floatings from left and right are considered the inner-most pair for the current vertical position.
335     // 2. Move away from inner-most pair by picking one of the previous floatings in the list(#1)
336     // 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).
337     // 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.
338     // As the result we have more horizontal space on the current vertical position.
339     auto leftBottom = m_current.left() ? std::optional<LayoutUnit>(m_current.left()->bottom()) : std::nullopt;
340     auto rightBottom = m_current.right() ? std::optional<LayoutUnit>(m_current.right()->bottom()) : std::nullopt;
341
342     auto updateLeft = (leftBottom == rightBottom) || (!rightBottom || (leftBottom && leftBottom < rightBottom)); 
343     auto updateRight = (leftBottom == rightBottom) || (!leftBottom || (rightBottom && leftBottom > rightBottom)); 
344
345     if (updateLeft) {
346         ASSERT(m_current.m_leftIndex);
347         m_current.m_verticalPosition = *leftBottom;
348         m_current.m_leftIndex = previousFloatingIndex(m_floatingState.floatings().left, *m_current.m_leftIndex);
349     }
350     
351     if (updateRight) {
352         ASSERT(m_current.m_rightIndex);
353         m_current.m_verticalPosition = *rightBottom;
354         m_current.m_rightIndex = previousFloatingIndex(m_floatingState.floatings().right, *m_current.m_rightIndex);
355     }
356
357     return *this;
358 }
359
360 void Iterator::set(LayoutUnit verticalPosition)
361 {
362     // Move the iterator to the initial vertical position by starting at the inner-most floating pair (last floats on left/right).
363     // 1. Check if the inner-most pair covers the vertical position.
364     // 2. Move outwards from the inner-most pair until the vertical postion intersects.
365     // (Note that verticalPosition has already been adjusted with the top of the last float.)
366
367     m_current.m_verticalPosition = verticalPosition;
368     // No floatings at all?
369     if (m_floatingState.isEmpty()) {
370         ASSERT_NOT_REACHED();
371
372         m_current.m_leftIndex = { };
373         m_current.m_rightIndex = { };
374         return;
375     }
376
377     auto findFloatingBelow = [&](const FloatingState::FloatingList& list) -> std::optional<unsigned> {
378         
379         auto index = list.size(); 
380         while (index) {
381             auto bottom = floatingDisplayBox(--index, list, m_layoutContext)->bottom();
382             // Is this floating intrusive on this position?
383             if (bottom > verticalPosition)
384                 return index;
385         }
386         return { };
387     };
388
389     auto& floatings = m_floatingState.floatings();
390     m_current.m_leftIndex = findFloatingBelow(floatings.left);
391     m_current.m_rightIndex = findFloatingBelow(floatings.right);
392 }
393
394 bool Iterator::operator==(const Iterator& other) const
395 {
396     return m_current == other.m_current;
397 }
398
399 bool Iterator::operator!=(const Iterator& other) const
400 {
401     return !(*this == other);
402 }
403
404 }
405 }
406 #endif