fb982b3d1e68cd2f0127d2ca05f0c550ba256d38
[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 usedValues = UsedHorizontalValues { layoutState().displayBoxForLayoutBox(root).contentBoxWidth() };
75     auto* layoutBox = root.firstInFlowOrFloatingChild();
76     // Compute width/height for non-text content and margin/border/padding for inline containers.
77     while (layoutBox) {
78         if (layoutBox->establishesFormattingContext())
79             layoutFormattingContextRoot(*layoutBox, usedValues);
80         else if (is<Container>(*layoutBox)) {
81             auto& inlineContainer = downcast<InlineContainer>(*layoutBox);
82             computeMargin(inlineContainer, usedValues);
83             computeBorderAndPadding(inlineContainer, usedValues);
84         } else if (layoutBox->isReplaced())
85             computeWidthAndHeightForReplacedInlineBox(*layoutBox, usedValues);
86         layoutBox = nextInPreOrder(*layoutBox, root);
87     }
88
89     InlineRunProvider inlineRunProvider;
90     collectInlineContent(inlineRunProvider);
91     LineLayout(*this).layout(inlineRunProvider);
92     LOG_WITH_STREAM(FormattingContextLayout, stream << "[End] -> inline formatting context -> formatting root(" << &root << ")");
93 }
94
95 void InlineFormattingContext::computeIntrinsicWidthConstraints() const
96 {
97     ASSERT(is<Container>(root()));
98
99     auto& layoutState = this->layoutState();
100     auto& root = downcast<Container>(this->root());
101     ASSERT(!layoutState.formattingStateForBox(root).intrinsicWidthConstraints(root));
102
103     Vector<const Box*> formattingContextRootList;
104     auto usedValues = UsedHorizontalValues { };
105     auto* layoutBox = root.firstInFlowOrFloatingChild();
106     while (layoutBox) {
107         if (layoutBox->establishesFormattingContext()) {
108             formattingContextRootList.append(layoutBox);
109             if (layoutBox->isFloatingPositioned())
110                 computeIntrinsicWidthForFloatBox(*layoutBox);
111             else if (layoutBox->isInlineBlockBox())
112                 computeIntrinsicWidthForInlineBlock(*layoutBox);
113             else
114                 ASSERT_NOT_REACHED();
115         } else if (layoutBox->isReplaced() || is<Container>(*layoutBox)) {
116             computeBorderAndPadding(*layoutBox, usedValues);
117             // inline-block and replaced.
118             auto needsWidthComputation = layoutBox->isReplaced() || layoutBox->establishesFormattingContext();
119             if (needsWidthComputation)
120                 computeWidthAndMargin(*layoutBox, usedValues);
121             else {
122                 // Simple inline container with no intrinsic width <span>.
123                 computeMargin(*layoutBox, usedValues);
124             }
125         }
126         layoutBox = nextInPreOrder(*layoutBox, root);
127     }
128
129     InlineRunProvider inlineRunProvider;
130     collectInlineContent(inlineRunProvider);
131
132     auto maximumLineWidth = [&](auto availableWidth) {
133         LayoutUnit maxContentLogicalRight;
134         auto lineBreaker = InlineLineBreaker { layoutState, formattingState().inlineContent(), inlineRunProvider.runs() };
135         LayoutUnit lineLogicalRight;
136
137         // Switch to the min/max formatting root width values before formatting the lines.
138         for (auto* formattingRoot : formattingContextRootList) {
139             auto intrinsicWidths = layoutState.formattingStateForBox(*formattingRoot).intrinsicWidthConstraints(*formattingRoot);
140             layoutState.displayBoxForLayoutBox(*formattingRoot).setContentBoxWidth(availableWidth ? intrinsicWidths->maximum : intrinsicWidths->minimum);
141         }
142
143         while (auto run = lineBreaker.nextRun(lineLogicalRight, availableWidth, !lineLogicalRight)) {
144             if (run->position == InlineLineBreaker::Run::Position::LineBegin)
145                 lineLogicalRight = 0;
146             lineLogicalRight += run->width;
147
148             maxContentLogicalRight = std::max(maxContentLogicalRight, lineLogicalRight);
149         }
150         return maxContentLogicalRight;
151     };
152
153     auto intrinsicWidthConstraints = FormattingContext::IntrinsicWidthConstraints { maximumLineWidth(0), maximumLineWidth(LayoutUnit::max()) };
154     layoutState.formattingStateForBox(root).setIntrinsicWidthConstraints(root, intrinsicWidthConstraints);
155 }
156
157 void InlineFormattingContext::computeIntrinsicWidthForFloatBox(const Box& layoutBox) const
158 {
159     ASSERT(layoutBox.isFloatingPositioned());
160     auto& layoutState = this->layoutState();
161
162     auto usedHorizontalValues = UsedHorizontalValues { };
163     computeBorderAndPadding(layoutBox, usedHorizontalValues);
164     computeMargin(layoutBox, usedHorizontalValues);
165     layoutState.createFormattingContext(layoutBox)->computeIntrinsicWidthConstraints();
166
167     auto usedVerticalValues = UsedVerticalValues { };
168     auto heightAndMargin = Geometry::floatingHeightAndMargin(layoutState, layoutBox, usedVerticalValues, usedHorizontalValues);
169
170     auto& displayBox = layoutState.displayBoxForLayoutBox(layoutBox);
171     displayBox.setContentBoxHeight(heightAndMargin.height);
172     displayBox.setVerticalMargin({ heightAndMargin.nonCollapsedMargin, { } });
173 }
174
175 void InlineFormattingContext::computeIntrinsicWidthForInlineBlock(const Box& layoutBox) const
176 {
177     ASSERT(layoutBox.isInlineBlockBox());
178
179     auto usedValues = UsedHorizontalValues { };
180     computeBorderAndPadding(layoutBox, usedValues);
181     computeMargin(layoutBox, usedValues);
182     layoutState().createFormattingContext(layoutBox)->computeIntrinsicWidthConstraints();
183 }
184
185 void InlineFormattingContext::computeMargin(const Box& layoutBox, UsedHorizontalValues usedValues) const
186 {
187     auto computedHorizontalMargin = Geometry::computedHorizontalMargin(layoutBox, usedValues);
188     auto& displayBox = layoutState().displayBoxForLayoutBox(layoutBox);
189     displayBox.setHorizontalComputedMargin(computedHorizontalMargin);
190     displayBox.setHorizontalMargin({ computedHorizontalMargin.start.valueOr(0), computedHorizontalMargin.end.valueOr(0) });
191 }
192
193 void InlineFormattingContext::computeWidthAndMargin(const Box& layoutBox, UsedHorizontalValues usedValues) const
194 {
195     auto& layoutState = this->layoutState();
196     WidthAndMargin widthAndMargin;
197     if (layoutBox.isFloatingPositioned())
198         widthAndMargin = Geometry::floatingWidthAndMargin(layoutState, layoutBox, usedValues);
199     else if (layoutBox.isInlineBlockBox())
200         widthAndMargin = Geometry::inlineBlockWidthAndMargin(layoutState, layoutBox, usedValues);
201     else if (layoutBox.replaced())
202         widthAndMargin = Geometry::inlineReplacedWidthAndMargin(layoutState, layoutBox, usedValues);
203     else
204         ASSERT_NOT_REACHED();
205
206     auto& displayBox = layoutState.displayBoxForLayoutBox(layoutBox);
207     displayBox.setContentBoxWidth(widthAndMargin.width);
208     displayBox.setHorizontalMargin(widthAndMargin.usedMargin);
209     displayBox.setHorizontalComputedMargin(widthAndMargin.computedMargin);
210 }
211
212 void InlineFormattingContext::computeHeightAndMargin(const Box& layoutBox) const
213 {
214     auto& layoutState = this->layoutState();
215
216     HeightAndMargin heightAndMargin;
217     if (layoutBox.isFloatingPositioned())
218         heightAndMargin = Geometry::floatingHeightAndMargin(layoutState, layoutBox, { }, UsedHorizontalValues { layoutState.displayBoxForLayoutBox(*layoutBox.containingBlock()).contentBoxWidth() });
219     else if (layoutBox.isInlineBlockBox())
220         heightAndMargin = Geometry::inlineBlockHeightAndMargin(layoutState, layoutBox);
221     else if (layoutBox.replaced())
222         heightAndMargin = Geometry::inlineReplacedHeightAndMargin(layoutState, layoutBox, { });
223     else
224         ASSERT_NOT_REACHED();
225
226     auto& displayBox = layoutState.displayBoxForLayoutBox(layoutBox);
227     displayBox.setContentBoxHeight(heightAndMargin.height);
228     displayBox.setVerticalMargin({ heightAndMargin.nonCollapsedMargin, { } });
229 }
230
231 void InlineFormattingContext::layoutFormattingContextRoot(const Box& root, UsedHorizontalValues usedValues) const
232 {
233     ASSERT(root.isFloatingPositioned() || root.isInlineBlockBox());
234     ASSERT(usedValues.containingBlockWidth);
235
236     computeBorderAndPadding(root, usedValues);
237     computeWidthAndMargin(root, usedValues);
238     // Swich over to the new formatting context (the one that the root creates).
239     auto formattingContext = layoutState().createFormattingContext(root);
240     formattingContext->layout();
241     // Come back and finalize the root's height and margin.
242     computeHeightAndMargin(root);
243     // Now that we computed the root's height, we can go back and layout the out-of-flow descedants (if any).
244     formattingContext->layoutOutOfFlowDescendants(root);
245 }
246
247 void InlineFormattingContext::computeWidthAndHeightForReplacedInlineBox(const Box& layoutBox, UsedHorizontalValues usedValues) const
248 {
249     ASSERT(!layoutBox.isContainer());
250     ASSERT(!layoutBox.establishesFormattingContext());
251     ASSERT(layoutBox.replaced());
252     ASSERT(usedValues.containingBlockWidth);
253
254     computeBorderAndPadding(layoutBox, usedValues);
255     computeWidthAndMargin(layoutBox, usedValues);
256     computeHeightAndMargin(layoutBox);
257 }
258
259 static void addDetachingRules(InlineItem& inlineItem, Optional<LayoutUnit> nonBreakableStartWidth, Optional<LayoutUnit> nonBreakableEndWidth)
260 {
261     OptionSet<InlineItem::DetachingRule> detachingRules;
262     if (nonBreakableStartWidth) {
263         detachingRules.add(InlineItem::DetachingRule::BreakAtStart);
264         inlineItem.addNonBreakableStart(*nonBreakableStartWidth);
265     }
266     if (nonBreakableEndWidth) {
267         detachingRules.add(InlineItem::DetachingRule::BreakAtEnd);
268         inlineItem.addNonBreakableEnd(*nonBreakableEndWidth);
269     }
270     inlineItem.addDetachingRule(detachingRules);
271 }
272
273 static InlineItem& createAndAppendInlineItem(InlineRunProvider& inlineRunProvider, InlineContent& inlineContent, const Box& layoutBox)
274 {
275     ASSERT(layoutBox.isInlineLevelBox() || layoutBox.isFloatingPositioned());
276     auto inlineItem = std::make_unique<InlineItem>(layoutBox);
277     auto* inlineItemPtr = inlineItem.get();
278     inlineContent.add(WTFMove(inlineItem));
279     inlineRunProvider.append(*inlineItemPtr);
280     return *inlineItemPtr;
281 }
282
283 void InlineFormattingContext::collectInlineContent(InlineRunProvider& inlineRunProvider) const
284 {
285     if (!is<Container>(root()))
286         return;
287     auto& root = downcast<Container>(this->root());
288     if (!root.hasInFlowOrFloatingChild())
289         return;
290     // The logic here is very similar to BFC layout.
291     // 1. Travers down the layout tree and collect "start" unbreakable widths (margin-left, border-left, padding-left)
292     // 2. Create InlineItem per leaf inline box (text nodes, inline-blocks, floats) and set "start" unbreakable width on them. 
293     // 3. Climb back and collect "end" unbreakable width and set it on the last InlineItem.
294     auto& layoutState = this->layoutState();
295     auto& inlineContent = formattingState().inlineContent();
296
297     enum class NonBreakableWidthType { Start, End };
298     auto nonBreakableWidth = [&](auto& container, auto type) {
299         auto& displayBox = layoutState.displayBoxForLayoutBox(container);
300         if (type == NonBreakableWidthType::Start)
301             return displayBox.marginStart() + displayBox.borderLeft() + displayBox.paddingLeft().valueOr(0);
302         return displayBox.marginEnd() + displayBox.borderRight() + displayBox.paddingRight().valueOr(0);
303     };
304
305     LayoutQueue layoutQueue;
306     layoutQueue.append(root.firstInFlowOrFloatingChild());
307
308     Optional<LayoutUnit> nonBreakableStartWidth;
309     Optional<LayoutUnit> nonBreakableEndWidth;
310     InlineItem* lastInlineItem = nullptr;
311     while (!layoutQueue.isEmpty()) {
312         while (true) {
313             auto& layoutBox = *layoutQueue.last();
314             if (!is<Container>(layoutBox))
315                 break;
316             auto& container = downcast<Container>(layoutBox);
317
318             if (container.establishesFormattingContext()) {
319                 // Formatting contexts are treated as leaf nodes.
320                 auto& inlineItem = createAndAppendInlineItem(inlineRunProvider, inlineContent, container);
321                 auto& displayBox = layoutState.displayBoxForLayoutBox(container);
322                 auto currentNonBreakableStartWidth = nonBreakableStartWidth.valueOr(0) + displayBox.marginStart() + nonBreakableEndWidth.valueOr(0);
323                 addDetachingRules(inlineItem, currentNonBreakableStartWidth, displayBox.marginEnd());
324                 nonBreakableStartWidth = { };
325                 nonBreakableEndWidth = { };
326
327                 // Formatting context roots take care of their subtrees. Continue with next sibling if exists.
328                 layoutQueue.removeLast();
329                 if (!container.nextInFlowOrFloatingSibling())
330                     break;
331                 layoutQueue.append(container.nextInFlowOrFloatingSibling());
332                 continue;
333             }
334
335             // Check if this non-formatting context container has any non-breakable start properties (margin-left, border-left, padding-left)
336             // <span style="padding-left: 5px"><span style="padding-left: 5px">foobar</span></span> -> 5px + 5px
337             auto currentNonBreakableStartWidth = nonBreakableWidth(layoutBox, NonBreakableWidthType::Start);
338             if (currentNonBreakableStartWidth || layoutBox.isPositioned())
339                 nonBreakableStartWidth = nonBreakableStartWidth.valueOr(0) + currentNonBreakableStartWidth;
340
341             if (!container.hasInFlowOrFloatingChild())
342                 break;
343             layoutQueue.append(container.firstInFlowOrFloatingChild());
344         }
345
346         while (!layoutQueue.isEmpty()) {
347             auto& layoutBox = *layoutQueue.takeLast();
348             if (is<Container>(layoutBox)) {
349                 // This is the end of an inline container. Compute the non-breakable end width and add it to the last inline box.
350                 // <span style="padding-right: 5px">foobar</span> -> 5px; last inline item -> "foobar"
351                 auto currentNonBreakableEndWidth = nonBreakableWidth(layoutBox, NonBreakableWidthType::End);
352                 if (currentNonBreakableEndWidth || layoutBox.isPositioned())
353                     nonBreakableEndWidth = nonBreakableEndWidth.valueOr(0) + currentNonBreakableEndWidth;
354                 // Add it to the last inline box
355                 if (lastInlineItem) {
356                     addDetachingRules(*lastInlineItem, { }, nonBreakableEndWidth);
357                     nonBreakableEndWidth = { };
358                 }
359             } else {
360                 // Leaf inline box
361                 auto& inlineItem = createAndAppendInlineItem(inlineRunProvider, inlineContent, layoutBox);
362                 // Add start and the (through empty containers) accumulated end width.
363                 // <span style="padding-left: 1px">foobar</span> -> nonBreakableStartWidth: 1px;
364                 // <span style="padding: 5px"></span>foobar -> nonBreakableStartWidth: 5px; nonBreakableEndWidth: 5px
365                 if (nonBreakableStartWidth || nonBreakableEndWidth) {
366                     addDetachingRules(inlineItem, nonBreakableStartWidth.valueOr(0) + nonBreakableEndWidth.valueOr(0), { });
367                     nonBreakableStartWidth = { };
368                     nonBreakableEndWidth = { };
369                 }
370                 lastInlineItem = &inlineItem;
371             }
372
373             if (auto* nextSibling = layoutBox.nextInFlowOrFloatingSibling()) {
374                 layoutQueue.append(nextSibling);
375                 break;
376             }
377         }
378     }
379 }
380
381 }
382 }
383
384 #endif