[LFC][IFC] Move line layout code to a dedicated file
[WebKit-https.git] / Source / WebCore / layout / inlineformatting / InlineFormattingContext.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 "InlineFormattingContext.h"
28
29 #if ENABLE(LAYOUT_FORMATTING_CONTEXT)
30
31 #include "InlineFormattingState.h"
32 #include "InlineLineBreaker.h"
33 #include "InlineRunProvider.h"
34 #include "LayoutBox.h"
35 #include "LayoutContainer.h"
36 #include "LayoutInlineBox.h"
37 #include "LayoutInlineContainer.h"
38 #include "LayoutState.h"
39 #include "Logging.h"
40 #include "Textutil.h"
41 #include <wtf/IsoMallocInlines.h>
42 #include <wtf/text/TextStream.h>
43
44 namespace WebCore {
45 namespace Layout {
46
47 WTF_MAKE_ISO_ALLOCATED_IMPL(InlineFormattingContext);
48
49 InlineFormattingContext::InlineFormattingContext(const Box& formattingContextRoot, InlineFormattingState& formattingState)
50     : FormattingContext(formattingContextRoot, formattingState)
51 {
52 }
53
54 static inline const Box* nextInPreOrder(const Box& layoutBox, const Container& root)
55 {
56     const Box* nextInPreOrder = nullptr;
57     if (!layoutBox.establishesFormattingContext() && is<Container>(layoutBox) && downcast<Container>(layoutBox).hasInFlowOrFloatingChild())
58         return downcast<Container>(layoutBox).firstInFlowOrFloatingChild();
59
60     for (nextInPreOrder = &layoutBox; nextInPreOrder && nextInPreOrder != &root; nextInPreOrder = nextInPreOrder->parent()) {
61         if (auto* nextSibling = nextInPreOrder->nextInFlowOrFloatingSibling())
62             return nextSibling;
63     }
64     return nullptr;
65 }
66
67 void InlineFormattingContext::layout() const
68 {
69     if (!is<Container>(root()))
70         return;
71
72     LOG_WITH_STREAM(FormattingContextLayout, stream << "[Start] -> inline formatting context -> formatting root(" << &root() << ")");
73     auto& root = downcast<Container>(this->root());
74     auto* layoutBox = root.firstInFlowOrFloatingChild();
75     // Compute width/height for non-text content and margin/border/padding for inline containers.
76     while (layoutBox) {
77         if (layoutBox->establishesFormattingContext())
78             layoutFormattingContextRoot(*layoutBox);
79         else if (is<Container>(*layoutBox))
80             computeMarginBorderAndPadding(downcast<InlineContainer>(*layoutBox));
81         else if (layoutBox->isReplaced())
82             computeWidthAndHeightForReplacedInlineBox(*layoutBox);
83         layoutBox = nextInPreOrder(*layoutBox, root);
84     }
85
86     InlineRunProvider inlineRunProvider;
87     collectInlineContent(inlineRunProvider);
88     LineLayout(*this).layout(inlineRunProvider);
89     LOG_WITH_STREAM(FormattingContextLayout, stream << "[End] -> inline formatting context -> formatting root(" << &root << ")");
90 }
91
92 void InlineFormattingContext::computeMarginBorderAndPadding(const InlineContainer& inlineContainer) const
93 {
94     // Non-replaced, non-formatting root containers (<span></span>) don't have width property -> non width computation. 
95     ASSERT(!inlineContainer.replaced());
96     ASSERT(!inlineContainer.establishesFormattingContext());
97
98     computeBorderAndPadding(inlineContainer);
99     auto& displayBox = layoutState().displayBoxForLayoutBox(inlineContainer);
100     auto computedHorizontalMargin = Geometry::computedHorizontalMargin(layoutState(), inlineContainer);
101     displayBox.setHorizontalComputedMargin(computedHorizontalMargin);
102     displayBox.setHorizontalMargin({ computedHorizontalMargin.start.valueOr(0), computedHorizontalMargin.end.valueOr(0) });
103 }
104
105 void InlineFormattingContext::computeWidthAndMargin(const Box& layoutBox) const
106 {
107     auto& layoutState = this->layoutState();
108
109     WidthAndMargin widthAndMargin;
110     if (layoutBox.isFloatingPositioned())
111         widthAndMargin = Geometry::floatingWidthAndMargin(layoutState, layoutBox);
112     else if (layoutBox.isInlineBlockBox())
113         widthAndMargin = Geometry::inlineBlockWidthAndMargin(layoutState, layoutBox);
114     else if (layoutBox.replaced())
115         widthAndMargin = Geometry::inlineReplacedWidthAndMargin(layoutState, layoutBox);
116     else
117         ASSERT_NOT_REACHED();
118
119     auto& displayBox = layoutState.displayBoxForLayoutBox(layoutBox);
120     displayBox.setContentBoxWidth(widthAndMargin.width);
121     displayBox.setHorizontalMargin(widthAndMargin.usedMargin);
122     displayBox.setHorizontalComputedMargin(widthAndMargin.computedMargin);
123 }
124
125 void InlineFormattingContext::computeHeightAndMargin(const Box& layoutBox) const
126 {
127     auto& layoutState = this->layoutState();
128
129     HeightAndMargin heightAndMargin;
130     if (layoutBox.isFloatingPositioned())
131         heightAndMargin = Geometry::floatingHeightAndMargin(layoutState, layoutBox);
132     else if (layoutBox.isInlineBlockBox())
133         heightAndMargin = Geometry::inlineBlockHeightAndMargin(layoutState, layoutBox);
134     else if (layoutBox.replaced())
135         heightAndMargin = Geometry::inlineReplacedHeightAndMargin(layoutState, layoutBox);
136     else
137         ASSERT_NOT_REACHED();
138
139     auto& displayBox = layoutState.displayBoxForLayoutBox(layoutBox);
140     displayBox.setContentBoxHeight(heightAndMargin.height);
141     displayBox.setVerticalMargin({ heightAndMargin.nonCollapsedMargin, { } });
142 }
143
144 void InlineFormattingContext::layoutFormattingContextRoot(const Box& root) const
145 {
146     ASSERT(root.isFloatingPositioned() || root.isInlineBlockBox());
147
148     computeBorderAndPadding(root);
149     computeWidthAndMargin(root);
150     // Swich over to the new formatting context (the one that the root creates).
151     auto formattingContext = layoutState().createFormattingContext(root);
152     formattingContext->layout();
153     // Come back and finalize the root's height and margin.
154     computeHeightAndMargin(root);
155     // Now that we computed the root's height, we can go back and layout the out-of-flow descedants (if any).
156     formattingContext->layoutOutOfFlowDescendants(root);
157 }
158
159 void InlineFormattingContext::computeWidthAndHeightForReplacedInlineBox(const Box& layoutBox) const
160 {
161     ASSERT(!layoutBox.isContainer());
162     ASSERT(!layoutBox.establishesFormattingContext());
163     ASSERT(layoutBox.replaced());
164
165     computeBorderAndPadding(layoutBox);
166     computeWidthAndMargin(layoutBox);
167     computeHeightAndMargin(layoutBox);
168 }
169
170 static void addDetachingRules(InlineItem& inlineItem, Optional<LayoutUnit> nonBreakableStartWidth, Optional<LayoutUnit> nonBreakableEndWidth)
171 {
172     OptionSet<InlineItem::DetachingRule> detachingRules;
173     if (nonBreakableStartWidth) {
174         detachingRules.add(InlineItem::DetachingRule::BreakAtStart);
175         inlineItem.addNonBreakableStart(*nonBreakableStartWidth);
176     }
177     if (nonBreakableEndWidth) {
178         detachingRules.add(InlineItem::DetachingRule::BreakAtEnd);
179         inlineItem.addNonBreakableEnd(*nonBreakableEndWidth);
180     }
181     inlineItem.addDetachingRule(detachingRules);
182 }
183
184 static InlineItem& createAndAppendInlineItem(InlineRunProvider& inlineRunProvider, InlineContent& inlineContent, const Box& layoutBox)
185 {
186     ASSERT(layoutBox.isInlineLevelBox() || layoutBox.isFloatingPositioned());
187     auto inlineItem = std::make_unique<InlineItem>(layoutBox);
188     auto* inlineItemPtr = inlineItem.get();
189     inlineContent.add(WTFMove(inlineItem));
190     inlineRunProvider.append(*inlineItemPtr);
191     return *inlineItemPtr;
192 }
193
194 void InlineFormattingContext::collectInlineContent(InlineRunProvider& inlineRunProvider) const
195 {
196     if (!is<Container>(root()))
197         return;
198     auto& root = downcast<Container>(this->root());
199     if (!root.hasInFlowOrFloatingChild())
200         return;
201     // The logic here is very similar to BFC layout.
202     // 1. Travers down the layout tree and collect "start" unbreakable widths (margin-left, border-left, padding-left)
203     // 2. Create InlineItem per leaf inline box (text nodes, inline-blocks, floats) and set "start" unbreakable width on them. 
204     // 3. Climb back and collect "end" unbreakable width and set it on the last InlineItem.
205     auto& layoutState = this->layoutState();
206     auto& inlineContent = formattingState().inlineContent();
207
208     enum class NonBreakableWidthType { Start, End };
209     auto nonBreakableWidth = [&](auto& container, auto type) {
210         auto& displayBox = layoutState.displayBoxForLayoutBox(container);
211         if (type == NonBreakableWidthType::Start)
212             return displayBox.marginStart() + displayBox.borderLeft() + displayBox.paddingLeft().valueOr(0);
213         return displayBox.marginEnd() + displayBox.borderRight() + displayBox.paddingRight().valueOr(0);
214     };
215
216     LayoutQueue layoutQueue;
217     layoutQueue.append(root.firstInFlowOrFloatingChild());
218
219     Optional<LayoutUnit> nonBreakableStartWidth;
220     Optional<LayoutUnit> nonBreakableEndWidth;
221     InlineItem* lastInlineItem = nullptr;
222     while (!layoutQueue.isEmpty()) {
223         while (true) {
224             auto& layoutBox = *layoutQueue.last();
225             if (!is<Container>(layoutBox))
226                 break;
227             auto& container = downcast<Container>(layoutBox);
228
229             if (container.establishesFormattingContext()) {
230                 // Formatting contexts are treated as leaf nodes.
231                 auto& inlineItem = createAndAppendInlineItem(inlineRunProvider, inlineContent, container);
232                 auto& displayBox = layoutState.displayBoxForLayoutBox(container);
233                 auto currentNonBreakableStartWidth = nonBreakableStartWidth.valueOr(0) + displayBox.marginStart() + nonBreakableEndWidth.valueOr(0);
234                 addDetachingRules(inlineItem, currentNonBreakableStartWidth, displayBox.marginEnd());
235                 nonBreakableStartWidth = { };
236                 nonBreakableEndWidth = { };
237
238                 // Formatting context roots take care of their subtrees. Continue with next sibling if exists.
239                 layoutQueue.removeLast();
240                 if (!container.nextInFlowOrFloatingSibling())
241                     break;
242                 layoutQueue.append(container.nextInFlowOrFloatingSibling());
243                 continue;
244             }
245
246             // Check if this non-formatting context container has any non-breakable start properties (margin-left, border-left, padding-left)
247             // <span style="padding-left: 5px"><span style="padding-left: 5px">foobar</span></span> -> 5px + 5px
248             auto currentNonBreakableStartWidth = nonBreakableWidth(layoutBox, NonBreakableWidthType::Start);
249             if (currentNonBreakableStartWidth || layoutBox.isPositioned())
250                 nonBreakableStartWidth = nonBreakableStartWidth.valueOr(0) + currentNonBreakableStartWidth;
251
252             if (!container.hasInFlowOrFloatingChild())
253                 break;
254             layoutQueue.append(container.firstInFlowOrFloatingChild());
255         }
256
257         while (!layoutQueue.isEmpty()) {
258             auto& layoutBox = *layoutQueue.takeLast();
259             if (is<Container>(layoutBox)) {
260                 // This is the end of an inline container. Compute the non-breakable end width and add it to the last inline box.
261                 // <span style="padding-right: 5px">foobar</span> -> 5px; last inline item -> "foobar"
262                 auto currentNonBreakableEndWidth = nonBreakableWidth(layoutBox, NonBreakableWidthType::End);
263                 if (currentNonBreakableEndWidth || layoutBox.isPositioned())
264                     nonBreakableEndWidth = nonBreakableEndWidth.valueOr(0) + currentNonBreakableEndWidth;
265                 // Add it to the last inline box
266                 if (lastInlineItem) {
267                     addDetachingRules(*lastInlineItem, { }, nonBreakableEndWidth);
268                     nonBreakableEndWidth = { };
269                 }
270             } else {
271                 // Leaf inline box
272                 auto& inlineItem = createAndAppendInlineItem(inlineRunProvider, inlineContent, layoutBox);
273                 // Add start and the (through empty containers) accumulated end width.
274                 // <span style="padding-left: 1px">foobar</span> -> nonBreakableStartWidth: 1px;
275                 // <span style="padding: 5px"></span>foobar -> nonBreakableStartWidth: 5px; nonBreakableEndWidth: 5px
276                 if (nonBreakableStartWidth || nonBreakableEndWidth) {
277                     addDetachingRules(inlineItem, nonBreakableStartWidth.valueOr(0) + nonBreakableEndWidth.valueOr(0), { });
278                     nonBreakableStartWidth = { };
279                     nonBreakableEndWidth = { };
280                 }
281                 lastInlineItem = &inlineItem;
282             }
283
284             if (auto* nextSibling = layoutBox.nextInFlowOrFloatingSibling()) {
285                 layoutQueue.append(nextSibling);
286                 break;
287             }
288         }
289     }
290 }
291
292 FormattingContext::InstrinsicWidthConstraints InlineFormattingContext::instrinsicWidthConstraints() const
293 {
294     auto& formattingStateForRoot = layoutState().formattingStateForBox(root());
295     if (auto instrinsicWidthConstraints = formattingStateForRoot.instrinsicWidthConstraints(root()))
296         return *instrinsicWidthConstraints;
297
298     auto& inlineFormattingState = formattingState();
299     InlineRunProvider inlineRunProvider;
300     collectInlineContent(inlineRunProvider);
301
302     // Compute width for non-text content.
303     for (auto& inlineRun : inlineRunProvider.runs()) {
304         if (inlineRun.isText())
305             continue;
306
307         computeWidthAndMargin(inlineRun.inlineItem().layoutBox());
308     }
309
310     auto maximumLineWidth = [&](auto availableWidth) {
311         LayoutUnit maxContentLogicalRight;
312         InlineLineBreaker lineBreaker(layoutState(), inlineFormattingState.inlineContent(), inlineRunProvider.runs());
313         LayoutUnit lineLogicalRight;
314         while (auto run = lineBreaker.nextRun(lineLogicalRight, availableWidth, !lineLogicalRight)) {
315             if (run->position == InlineLineBreaker::Run::Position::LineBegin)
316                 lineLogicalRight = 0;
317             lineLogicalRight += run->width;
318
319             maxContentLogicalRight = std::max(maxContentLogicalRight, lineLogicalRight);
320         }
321         return maxContentLogicalRight;
322     };
323
324     return FormattingContext::InstrinsicWidthConstraints { maximumLineWidth(0), maximumLineWidth(LayoutUnit::max()) };
325 }
326
327 }
328 }
329
330 #endif