784e11fe9b13f6493e790f382cc00e34ced929ab
[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 "FloatingState.h"
32 #include "InlineFormattingState.h"
33 #include "InlineLineBreaker.h"
34 #include "InlineRunProvider.h"
35 #include "LayoutBox.h"
36 #include "LayoutContainer.h"
37 #include "LayoutFormattingState.h"
38 #include "LayoutInlineBox.h"
39 #include "LayoutInlineContainer.h"
40 #include "Logging.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, FormattingState& formattingState)
50     : FormattingContext(formattingContextRoot, formattingState)
51 {
52 }
53
54 void InlineFormattingContext::layout() const
55 {
56     if (!is<Container>(root()))
57         return;
58
59     LOG_WITH_STREAM(FormattingContextLayout, stream << "[Start] -> inline formatting context -> formatting root(" << &root() << ")");
60
61     InlineRunProvider inlineRunProvider(inlineFormattingState());
62     collectInlineContent(inlineRunProvider);
63     // Compute width/height for non-text content.
64     for (auto& inlineRun : inlineRunProvider.runs()) {
65         if (inlineRun.isText())
66             continue;
67
68         auto& layoutBox = inlineRun.inlineItem().layoutBox();
69         if (layoutBox.establishesFormattingContext()) {
70             layoutFormattingContextRoot(layoutBox);
71             continue;
72         }
73         computeWidthAndHeightForReplacedInlineBox(layoutBox);
74     }
75
76     layoutInlineContent(inlineRunProvider);
77     LOG_WITH_STREAM(FormattingContextLayout, stream << "[End] -> inline formatting context -> formatting root(" << &root() << ")");
78 }
79
80 static bool isTrimmableContent(const InlineLineBreaker::Run& run)
81 {
82     return run.content.isWhitespace() && run.content.style().collapseWhiteSpace();
83 }
84
85 void InlineFormattingContext::initializeNewLine(Line& line) const
86 {
87     auto& formattingRoot = downcast<Container>(root());
88     auto& formattingRootDisplayBox = layoutState().displayBoxForLayoutBox(formattingRoot);
89
90     auto lineLogicalLeft = formattingRootDisplayBox.contentBoxLeft();
91     auto lineLogicalTop = line.isFirstLine() ? formattingRootDisplayBox.contentBoxTop() : line.logicalBottom();
92     auto availableWidth = formattingRootDisplayBox.contentBoxWidth();
93
94     // Check for intruding floats and adjust logical left/available width for this line accordingly.
95     auto& floatingState = formattingState().floatingState();
96     if (!floatingState.isEmpty()) {
97         auto floatConstraints = floatingState.constraints(lineLogicalTop, formattingRoot);
98         // Check if these constraints actually put limitation on the line.
99         if (floatConstraints.left && *floatConstraints.left <= formattingRootDisplayBox.contentBoxLeft())
100             floatConstraints.left = { };
101
102         if (floatConstraints.right && *floatConstraints.right >= formattingRootDisplayBox.contentBoxRight())
103             floatConstraints.right = { };
104
105         if (floatConstraints.left && floatConstraints.right) {
106             ASSERT(*floatConstraints.left < *floatConstraints.right);
107             availableWidth = *floatConstraints.right - *floatConstraints.left;
108             lineLogicalLeft = *floatConstraints.left;
109         } else if (floatConstraints.left) {
110             ASSERT(*floatConstraints.left > lineLogicalLeft);
111             availableWidth -= (*floatConstraints.left - lineLogicalLeft);
112             lineLogicalLeft = *floatConstraints.left;
113         } else if (floatConstraints.right) {
114             ASSERT(*floatConstraints.right > lineLogicalLeft);
115             availableWidth = *floatConstraints.right - lineLogicalLeft;
116         }
117     }
118
119     Display::Box::Rect logicalRect;
120     logicalRect.setTop(lineLogicalTop);
121     logicalRect.setLeft(lineLogicalLeft);
122     logicalRect.setWidth(availableWidth);
123     logicalRect.setHeight(formattingRoot.style().computedLineHeight());
124
125     line.init(logicalRect);
126 }
127
128 bool InlineFormattingContext::contentRequiresSeparateRun(const InlineItem& inlineItem) const
129 {
130     // FIXME: This is way too inefficient. We should pre-mark the runs instead while flattening the inline formatting context.
131     for (auto* inlineContainer = inlineItem.layoutBox().parent(); inlineContainer != &root(); inlineContainer = inlineContainer->parent()) {
132         if (inlineContainer->isPositioned())
133             return true;
134     }
135     return false;
136 }
137
138 void InlineFormattingContext::splitInlineRunIfNeeded(const InlineRun& inlineRun, InlineRuns& splitRuns) const
139 {
140     if (!inlineRun.overlapsMultipleInlineItems())
141         return;
142
143     ASSERT(inlineRun.textContext());
144     // In certain cases, a run can overlap multiple inline elements like this:
145     // <span>normal text content</span><span style="position: relative; left: 10px;">but this one needs a dedicated run</span><span>end of text</span>
146     // The content above generates one long run <normal text contentbut this one needs dedicated runend of text>
147     // However, since the middle run is positioned, it needs to be moved independently from the rest of the content, hence it needs a dedicated inline run.
148
149     // 1. Start with the first inline item (element) and travers the list until
150     // 2. either find an inline item that needs a dedicated run or we reach the end of the run
151     // 3. Shrink the original inline run and create a new one.
152     auto& inlineContent = inlineFormattingState().inlineContent();
153     auto textUtil = TextUtil { inlineContent };
154
155     auto split=[&](const auto& inlineItem, auto startPosition, auto length, auto contentStart) {
156         auto width = textUtil.width(inlineItem, startPosition, length, contentStart);
157
158         auto run = InlineRun { { inlineRun.logicalTop(), contentStart, width, inlineRun.height() }, inlineItem };
159         run.setTextContext({ startPosition, length });
160         splitRuns.append(run);
161         return contentStart + width;
162     };
163
164     auto contentStart = inlineRun.logicalLeft();
165     auto startPosition = inlineRun.textContext()->start();
166     auto remaningLength = inlineRun.textContext()->length();
167
168     unsigned uncommittedLength = 0;
169     InlineItem* firstUncommittedInlineItem = nullptr;
170     for (auto iterator = inlineContent.find<const InlineItem&, InlineItemHashTranslator>(inlineRun.inlineItem()); iterator != inlineContent.end() && remaningLength > 0; ++iterator) {
171         auto& inlineItem = **iterator;
172
173         if (!contentRequiresSeparateRun(inlineItem)) {
174             uncommittedLength += std::min(remaningLength, inlineItem.textContent().length() - startPosition);
175             firstUncommittedInlineItem = !firstUncommittedInlineItem ? &inlineItem : firstUncommittedInlineItem;
176             continue;
177         }
178
179         // Commit the items that don't need dedicated run.
180         if (firstUncommittedInlineItem) {
181             contentStart = split(*firstUncommittedInlineItem, startPosition, uncommittedLength, contentStart);
182
183             remaningLength -= uncommittedLength;
184             startPosition = 0;
185             uncommittedLength = 0;
186         }
187
188         // Create a dedicated run for this inline item.
189         auto length = std::min(remaningLength, inlineItem.textContent().length() - startPosition);
190         contentStart = split(inlineItem, startPosition, length, contentStart);
191
192         startPosition = 0;
193         remaningLength -= length;
194         firstUncommittedInlineItem = nullptr;
195     }
196
197     // Either all inline elements needed dedicated runs or neither of them.
198     if (!remaningLength || remaningLength == inlineRun.textContext()->length())
199         return;
200
201     ASSERT(remaningLength == uncommittedLength);
202     split(*firstUncommittedInlineItem, startPosition, uncommittedLength, contentStart);
203 }
204
205 void InlineFormattingContext::postProcessInlineRuns(Line& line, IsLastLine isLastLine, Line::RunRange runRange) const
206 {
207     auto& inlineFormattingState = this->inlineFormattingState();
208     Geometry::alignRuns(inlineFormattingState, root().style().textAlign(), line, runRange, isLastLine);
209
210     auto& inlineRuns = inlineFormattingState.inlineRuns();
211     ASSERT(*runRange.lastRunIndex < inlineRuns.size());
212
213     auto runIndex = *runRange.firstRunIndex;
214     auto& lastInlineRun = inlineRuns[*runRange.lastRunIndex];
215     while (runIndex < inlineRuns.size()) {
216         auto& inlineRun = inlineRuns[runIndex];
217         auto isLastRunInRange = &inlineRun == &lastInlineRun;
218
219         InlineRuns splitRuns;
220         splitInlineRunIfNeeded(inlineRun, splitRuns);
221         if (!splitRuns.isEmpty()) {
222             ASSERT(splitRuns.size() > 1);
223             // Replace the continous run with new ones.
224             // Reuse the original one.
225             auto& firstRun = splitRuns.first();
226             inlineRun.setWidth(firstRun.width());
227             inlineRun.textContext()->setLength(firstRun.textContext()->length());
228             splitRuns.remove(0);
229             // Insert the rest.
230             for (auto& splitRun : splitRuns)
231                 inlineRuns.insert(++runIndex, splitRun);
232         }
233
234         if (isLastRunInRange)
235             break;
236
237         ++runIndex;
238     }
239 }
240
241 void InlineFormattingContext::closeLine(Line& line, IsLastLine isLastLine) const
242 {
243     auto runRange = line.close();
244     ASSERT(!runRange.firstRunIndex || runRange.lastRunIndex);
245
246     if (!runRange.firstRunIndex)
247         return;
248
249     postProcessInlineRuns(line, isLastLine, runRange);
250 }
251
252 void InlineFormattingContext::appendContentToLine(Line& line, const InlineLineBreaker::Run& run) const
253 {
254     auto lastRunType = line.lastRunType();
255     line.appendContent(run);
256
257     if (root().style().textAlign() == TextAlignMode::Justify)
258         Geometry::computeExpansionOpportunities(inlineFormattingState(), run.content, lastRunType.value_or(InlineRunProvider::Run::Type::NonWhitespace));
259 }
260
261 void InlineFormattingContext::layoutInlineContent(const InlineRunProvider& inlineRunProvider) const
262 {
263     auto& layoutState = this->layoutState();
264     auto& inlineFormattingState = this->inlineFormattingState();
265     auto floatingContext = FloatingContext { inlineFormattingState.floatingState() };
266
267     Line line(inlineFormattingState);
268     initializeNewLine(line);
269
270     InlineLineBreaker lineBreaker(layoutState, inlineFormattingState.inlineContent(), inlineRunProvider.runs());
271     while (auto run = lineBreaker.nextRun(line.contentLogicalRight(), line.availableWidth(), !line.hasContent())) {
272         auto isFirstRun = run->position == InlineLineBreaker::Run::Position::LineBegin;
273         auto isLastRun = run->position == InlineLineBreaker::Run::Position::LineEnd;
274         auto generatesInlineRun = true;
275
276         // Position float and adjust the runs on line.
277         if (run->content.isFloat()) {
278             auto& floatBox = run->content.inlineItem().layoutBox();
279             computeFloatPosition(floatingContext, line, floatBox);
280             inlineFormattingState.floatingState().append(floatBox);
281
282             auto floatBoxWidth = layoutState.displayBoxForLayoutBox(floatBox).width();
283             // Shrink availble space for current line and move existing inline runs.
284             floatBox.isLeftFloatingPositioned() ? line.adjustLogicalLeft(floatBoxWidth) : line.adjustLogicalRight(floatBoxWidth);
285
286             generatesInlineRun = false;
287         }
288
289         // 1. Initialize new line if needed.
290         // 2. Append inline run unless it is skipped.
291         // 3. Close current line if needed.
292         if (isFirstRun) {
293             // When the first run does not generate an actual inline run, the next run comes in first-run as well.
294             // No need to spend time on closing/initializing.
295             // Skip leading whitespace.
296             if (!generatesInlineRun || isTrimmableContent(*run))
297                 continue;
298
299             if (line.hasContent()) {
300                 // Previous run ended up being at the line end. Adjust the line accordingly.
301                 if (!line.isClosed())
302                     closeLine(line, IsLastLine::No);
303                 initializeNewLine(line);
304             }
305          }
306
307         if (generatesInlineRun)
308             appendContentToLine(line, *run);
309
310         if (isLastRun)
311             closeLine(line, IsLastLine::No);
312     }
313
314     closeLine(line, IsLastLine::Yes);
315 }
316
317 void InlineFormattingContext::computeWidthAndMargin(const Box& layoutBox) const
318 {
319     auto& layoutState = this->layoutState();
320
321     WidthAndMargin widthAndMargin;
322     if (layoutBox.isFloatingPositioned())
323         widthAndMargin = Geometry::floatingWidthAndMargin(layoutState, layoutBox);
324     else if (layoutBox.isInlineBlockBox())
325         widthAndMargin = Geometry::inlineBlockWidthAndMargin(layoutState, layoutBox);
326     else if (layoutBox.replaced())
327         widthAndMargin = Geometry::inlineReplacedWidthAndMargin(layoutState, layoutBox);
328     else
329         ASSERT_NOT_REACHED();
330
331     auto& displayBox = layoutState.displayBoxForLayoutBox(layoutBox);
332     displayBox.setContentBoxWidth(widthAndMargin.width);
333     displayBox.setHorizontalMargin(widthAndMargin.margin);
334     displayBox.setHorizontalNonComputedMargin(widthAndMargin.nonComputedMargin);
335 }
336
337 void InlineFormattingContext::computeHeightAndMargin(const Box& layoutBox) const
338 {
339     auto& layoutState = this->layoutState();
340
341     HeightAndMargin heightAndMargin;
342     if (layoutBox.isFloatingPositioned())
343         heightAndMargin = Geometry::floatingHeightAndMargin(layoutState, layoutBox);
344     else if (layoutBox.isInlineBlockBox())
345         heightAndMargin = Geometry::inlineBlockHeightAndMargin(layoutState, layoutBox);
346     else if (layoutBox.replaced())
347         heightAndMargin = Geometry::inlineReplacedHeightAndMargin(layoutState, layoutBox);
348     else
349         ASSERT_NOT_REACHED();
350
351     auto& displayBox = layoutState.displayBoxForLayoutBox(layoutBox);
352     displayBox.setContentBoxHeight(heightAndMargin.height);
353     displayBox.setVerticalNonCollapsedMargin(heightAndMargin.margin);
354     displayBox.setVerticalMargin(heightAndMargin.collapsedMargin.value_or(heightAndMargin.margin));
355 }
356
357 void InlineFormattingContext::layoutFormattingContextRoot(const Box& layoutBox) const
358 {
359     ASSERT(layoutBox.isFloatingPositioned() || layoutBox.isInlineBlockBox());
360
361     auto& layoutState = this->layoutState();
362     auto& formattingState = layoutState.createFormattingStateForFormattingRootIfNeeded(layoutBox);
363     computeBorderAndPadding(layoutBox);
364     computeWidthAndMargin(layoutBox);
365     // Swich over to the new formatting context (the one that the root creates).
366     formattingState.formattingContext(layoutBox)->layout();
367     // Come back and finalize the root's height and margin.
368     computeHeightAndMargin(layoutBox);
369 }
370
371 void InlineFormattingContext::computeWidthAndHeightForReplacedInlineBox(const Box& layoutBox) const
372 {
373     ASSERT(!layoutBox.isContainer());
374     ASSERT(!layoutBox.establishesFormattingContext());
375     ASSERT(layoutBox.replaced());
376
377     computeBorderAndPadding(layoutBox);
378     computeWidthAndMargin(layoutBox);
379     computeHeightAndMargin(layoutBox);
380 }
381
382 void InlineFormattingContext::computeFloatPosition(const FloatingContext& floatingContext, Line& line, const Box& floatBox) const
383 {
384     auto& layoutState = this->layoutState();
385     ASSERT(layoutState.hasDisplayBox(floatBox));
386     auto& displayBox = layoutState.displayBoxForLayoutBox(floatBox);
387
388     // Set static position first.
389     displayBox.setTopLeft({ line.contentLogicalRight(), line.logicalTop() });
390     // Float it.
391     displayBox.setTopLeft(floatingContext.positionForFloat(floatBox));
392 }
393
394 void InlineFormattingContext::computeStaticPosition(const Box&) const
395 {
396 }
397
398 void InlineFormattingContext::collectInlineContent(InlineRunProvider& inlineRunProvider) const
399 {
400     if (!is<Container>(root()))
401         return;
402
403     auto& formattingRoot = downcast<Container>(root());
404     auto* layoutBox = formattingRoot.firstInFlowOrFloatingChild();
405
406     while (layoutBox) {
407         ASSERT(layoutBox->isDescendantOf(formattingRoot));
408
409         if (layoutBox->establishesFormattingContext()) {
410             inlineRunProvider.append(*layoutBox);
411             layoutBox = layoutBox->nextInFlowOrFloatingSibling();
412             continue;
413         }
414
415         if (is<Container>(layoutBox)) {
416             layoutBox = downcast<Container>(*layoutBox).firstInFlowOrFloatingChild();
417             continue;
418         }
419
420         inlineRunProvider.append(*layoutBox);
421
422         while (true) {
423             if (auto* nextSibling = layoutBox->nextInFlowOrFloatingSibling()) {
424                 layoutBox = nextSibling;
425                 break;
426             }
427
428             layoutBox = layoutBox->parent();
429
430             if (layoutBox == &formattingRoot)
431                 return;
432         }
433     }
434 }
435
436 FormattingContext::InstrinsicWidthConstraints InlineFormattingContext::instrinsicWidthConstraints() const
437 {
438     auto& formattingStateForRoot = layoutState().formattingStateForBox(root());
439     if (auto instrinsicWidthConstraints = formattingStateForRoot.instrinsicWidthConstraints(root()))
440         return *instrinsicWidthConstraints;
441
442     auto& inlineFormattingState = this->inlineFormattingState();
443     InlineRunProvider inlineRunProvider(inlineFormattingState);
444     collectInlineContent(inlineRunProvider);
445
446     // Compute width for non-text content.
447     for (auto& inlineRun : inlineRunProvider.runs()) {
448         if (inlineRun.isText())
449             continue;
450
451         computeWidthAndMargin(inlineRun.inlineItem().layoutBox());
452     }
453
454     auto maximumLineWidth = [&](auto availableWidth) {
455         LayoutUnit maxContentLogicalRight;
456         InlineLineBreaker lineBreaker(layoutState(), inlineFormattingState.inlineContent(), inlineRunProvider.runs());
457         LayoutUnit lineLogicalRight;
458         while (auto run = lineBreaker.nextRun(lineLogicalRight, availableWidth, !lineLogicalRight)) {
459             if (run->position == InlineLineBreaker::Run::Position::LineBegin)
460                 lineLogicalRight = 0;
461             lineLogicalRight += run->width;
462
463             maxContentLogicalRight = std::max(maxContentLogicalRight, lineLogicalRight);
464         }
465         return maxContentLogicalRight;
466     };
467
468     auto instrinsicWidthConstraints = FormattingContext::InstrinsicWidthConstraints { maximumLineWidth(0), maximumLineWidth(LayoutUnit::max()) };
469     formattingStateForRoot.setInstrinsicWidthConstraints(root(), instrinsicWidthConstraints);
470     return instrinsicWidthConstraints;
471 }
472
473 }
474 }
475
476 #endif