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