[LFC][IFC] Construct dedicated runs when the inline element requires it (part 2)
[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 void InlineFormattingContext::splitInlineRunIfNeeded(const InlineRun& inlineRun, InlineRuns& splitRuns) const
129 {
130     if (!inlineRun.overlapsMultipleInlineItems())
131         return;
132
133     ASSERT(inlineRun.textContext());
134     // In certain cases, a run can overlap multiple inline elements like this:
135     // <span>normal text content</span><span style="position: relative; left: 10px;">but this one needs a dedicated run</span><span>end of text</span>
136     // The content above generates one long run <normal text contentbut this one needs dedicated runend of text>
137     // 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.
138
139     // 1. Start with the first inline item (element) and travers the list until
140     // 2. either find an inline item that needs a dedicated run or we reach the end of the run
141     // 3. Create dedicate inline runs.
142     auto& inlineContent = inlineFormattingState().inlineContent();
143     auto textUtil = TextUtil { inlineContent };
144
145     auto split=[&](const auto& inlineItem, auto startPosition, auto length, auto contentStart) {
146         auto width = textUtil.width(inlineItem, startPosition, length, contentStart);
147
148         auto run = InlineRun { { inlineRun.logicalTop(), contentStart, width, inlineRun.height() }, inlineItem };
149         run.setTextContext({ startPosition, length });
150         splitRuns.append(run);
151         return contentStart + width;
152     };
153
154     auto contentStart = inlineRun.logicalLeft();
155     auto startPosition = inlineRun.textContext()->start();
156     auto remaningLength = inlineRun.textContext()->length();
157
158     unsigned uncommittedLength = 0;
159     InlineItem* firstUncommittedInlineItem = nullptr;
160     for (auto iterator = inlineContent.find<const InlineItem&, InlineItemHashTranslator>(inlineRun.inlineItem()); iterator != inlineContent.end() && remaningLength > 0; ++iterator) {
161         auto& inlineItem = **iterator;
162
163         auto currentLength = [&] {
164             return std::min(remaningLength, inlineItem.textContent().length() - startPosition);
165         };
166
167         // 1. Inline element does not require run breaking -> add current inline element to uncommitted. Jump to the next element.
168         // 2. Break at the beginning of the inline element -> commit what we've got so far. Current element becomes the first uncommitted.
169         // 3. Break at the end of the inline element -> commit what we've got so far including the current element.
170         // 4. Break before/after -> requires dedicated run -> commit what we've got so far and also commit the current inline element as a separate inline run.
171         auto detachingRules = inlineFormattingState().detachingRules(inlineItem.layoutBox());
172
173         // #1
174         if (!detachingRules) {
175             uncommittedLength += currentLength();
176             firstUncommittedInlineItem = !firstUncommittedInlineItem ? &inlineItem : firstUncommittedInlineItem;
177             continue;
178         }
179
180         auto commit = [&] {
181             if (!firstUncommittedInlineItem)
182                 return;
183
184             contentStart = split(*firstUncommittedInlineItem, startPosition, uncommittedLength, contentStart);
185
186             remaningLength -= uncommittedLength;
187             startPosition = 0;
188             uncommittedLength = 0;
189             firstUncommittedInlineItem = nullptr;
190         };
191
192         // #2
193         if (*detachingRules == InlineFormattingState::DetachingRule::BreakAtStart) {
194             commit();
195             firstUncommittedInlineItem = &inlineItem;
196             uncommittedLength = currentLength();
197             continue;
198         }
199
200         // #3
201         if (*detachingRules == InlineFormattingState::DetachingRule::BreakAtEnd) {
202             ASSERT(firstUncommittedInlineItem);
203             uncommittedLength += currentLength();
204             commit();
205             continue;
206         }
207
208         // #4
209         commit();
210         firstUncommittedInlineItem = &inlineItem;
211         uncommittedLength = currentLength();
212         commit();
213     }
214
215     // Either all inline elements needed dedicated runs or neither of them.
216     if (!remaningLength || remaningLength == inlineRun.textContext()->length())
217         return;
218
219     ASSERT(remaningLength == uncommittedLength);
220     split(*firstUncommittedInlineItem, startPosition, uncommittedLength, contentStart);
221 }
222
223 void InlineFormattingContext::postProcessInlineRuns(Line& line, IsLastLine isLastLine, Line::RunRange runRange) const
224 {
225     auto& inlineFormattingState = this->inlineFormattingState();
226     Geometry::alignRuns(inlineFormattingState, root().style().textAlign(), line, runRange, isLastLine);
227
228     auto& inlineRuns = inlineFormattingState.inlineRuns();
229     ASSERT(*runRange.lastRunIndex < inlineRuns.size());
230
231     auto runIndex = *runRange.firstRunIndex;
232     auto& lastInlineRun = inlineRuns[*runRange.lastRunIndex];
233     while (runIndex < inlineRuns.size()) {
234         auto& inlineRun = inlineRuns[runIndex];
235         auto isLastRunInRange = &inlineRun == &lastInlineRun;
236
237         InlineRuns splitRuns;
238         splitInlineRunIfNeeded(inlineRun, splitRuns);
239         if (!splitRuns.isEmpty()) {
240             ASSERT(splitRuns.size() > 1);
241             // Replace the continous run with new ones.
242             // Reuse the original one.
243             auto& firstRun = splitRuns.first();
244             inlineRun.setWidth(firstRun.width());
245             inlineRun.textContext()->setLength(firstRun.textContext()->length());
246             splitRuns.remove(0);
247             // Insert the rest.
248             for (auto& splitRun : splitRuns)
249                 inlineRuns.insert(++runIndex, splitRun);
250         }
251
252         if (isLastRunInRange)
253             break;
254
255         ++runIndex;
256     }
257 }
258
259 void InlineFormattingContext::closeLine(Line& line, IsLastLine isLastLine) const
260 {
261     auto runRange = line.close();
262     ASSERT(!runRange.firstRunIndex || runRange.lastRunIndex);
263
264     if (!runRange.firstRunIndex)
265         return;
266
267     postProcessInlineRuns(line, isLastLine, runRange);
268 }
269
270 void InlineFormattingContext::appendContentToLine(Line& line, const InlineLineBreaker::Run& run) const
271 {
272     auto lastRunType = line.lastRunType();
273     line.appendContent(run);
274
275     if (root().style().textAlign() == TextAlignMode::Justify)
276         Geometry::computeExpansionOpportunities(inlineFormattingState(), run.content, lastRunType.value_or(InlineRunProvider::Run::Type::NonWhitespace));
277 }
278
279 void InlineFormattingContext::layoutInlineContent(const InlineRunProvider& inlineRunProvider) const
280 {
281     auto& layoutState = this->layoutState();
282     auto& inlineFormattingState = this->inlineFormattingState();
283     auto floatingContext = FloatingContext { inlineFormattingState.floatingState() };
284
285     Line line(inlineFormattingState);
286     initializeNewLine(line);
287
288     InlineLineBreaker lineBreaker(layoutState, inlineFormattingState.inlineContent(), inlineRunProvider.runs());
289     while (auto run = lineBreaker.nextRun(line.contentLogicalRight(), line.availableWidth(), !line.hasContent())) {
290         auto isFirstRun = run->position == InlineLineBreaker::Run::Position::LineBegin;
291         auto isLastRun = run->position == InlineLineBreaker::Run::Position::LineEnd;
292         auto generatesInlineRun = true;
293
294         // Position float and adjust the runs on line.
295         if (run->content.isFloat()) {
296             auto& floatBox = run->content.inlineItem().layoutBox();
297             computeFloatPosition(floatingContext, line, floatBox);
298             inlineFormattingState.floatingState().append(floatBox);
299
300             auto floatBoxWidth = layoutState.displayBoxForLayoutBox(floatBox).width();
301             // Shrink availble space for current line and move existing inline runs.
302             floatBox.isLeftFloatingPositioned() ? line.adjustLogicalLeft(floatBoxWidth) : line.adjustLogicalRight(floatBoxWidth);
303
304             generatesInlineRun = false;
305         }
306
307         // 1. Initialize new line if needed.
308         // 2. Append inline run unless it is skipped.
309         // 3. Close current line if needed.
310         if (isFirstRun) {
311             // When the first run does not generate an actual inline run, the next run comes in first-run as well.
312             // No need to spend time on closing/initializing.
313             // Skip leading whitespace.
314             if (!generatesInlineRun || isTrimmableContent(*run))
315                 continue;
316
317             if (line.hasContent()) {
318                 // Previous run ended up being at the line end. Adjust the line accordingly.
319                 if (!line.isClosed())
320                     closeLine(line, IsLastLine::No);
321                 initializeNewLine(line);
322             }
323          }
324
325         if (generatesInlineRun)
326             appendContentToLine(line, *run);
327
328         if (isLastRun)
329             closeLine(line, IsLastLine::No);
330     }
331
332     closeLine(line, IsLastLine::Yes);
333 }
334
335 void InlineFormattingContext::computeWidthAndMargin(const Box& layoutBox) const
336 {
337     auto& layoutState = this->layoutState();
338
339     WidthAndMargin widthAndMargin;
340     if (layoutBox.isFloatingPositioned())
341         widthAndMargin = Geometry::floatingWidthAndMargin(layoutState, layoutBox);
342     else if (layoutBox.isInlineBlockBox())
343         widthAndMargin = Geometry::inlineBlockWidthAndMargin(layoutState, layoutBox);
344     else if (layoutBox.replaced())
345         widthAndMargin = Geometry::inlineReplacedWidthAndMargin(layoutState, layoutBox);
346     else
347         ASSERT_NOT_REACHED();
348
349     auto& displayBox = layoutState.displayBoxForLayoutBox(layoutBox);
350     displayBox.setContentBoxWidth(widthAndMargin.width);
351     displayBox.setHorizontalMargin(widthAndMargin.margin);
352     displayBox.setHorizontalNonComputedMargin(widthAndMargin.nonComputedMargin);
353 }
354
355 void InlineFormattingContext::computeHeightAndMargin(const Box& layoutBox) const
356 {
357     auto& layoutState = this->layoutState();
358
359     HeightAndMargin heightAndMargin;
360     if (layoutBox.isFloatingPositioned())
361         heightAndMargin = Geometry::floatingHeightAndMargin(layoutState, layoutBox);
362     else if (layoutBox.isInlineBlockBox())
363         heightAndMargin = Geometry::inlineBlockHeightAndMargin(layoutState, layoutBox);
364     else if (layoutBox.replaced())
365         heightAndMargin = Geometry::inlineReplacedHeightAndMargin(layoutState, layoutBox);
366     else
367         ASSERT_NOT_REACHED();
368
369     auto& displayBox = layoutState.displayBoxForLayoutBox(layoutBox);
370     displayBox.setContentBoxHeight(heightAndMargin.height);
371     displayBox.setVerticalNonCollapsedMargin(heightAndMargin.margin);
372     displayBox.setVerticalMargin(heightAndMargin.collapsedMargin.value_or(heightAndMargin.margin));
373 }
374
375 void InlineFormattingContext::layoutFormattingContextRoot(const Box& layoutBox) const
376 {
377     ASSERT(layoutBox.isFloatingPositioned() || layoutBox.isInlineBlockBox());
378
379     auto& layoutState = this->layoutState();
380     auto& formattingState = layoutState.createFormattingStateForFormattingRootIfNeeded(layoutBox);
381     computeBorderAndPadding(layoutBox);
382     computeWidthAndMargin(layoutBox);
383     // Swich over to the new formatting context (the one that the root creates).
384     formattingState.formattingContext(layoutBox)->layout();
385     // Come back and finalize the root's height and margin.
386     computeHeightAndMargin(layoutBox);
387 }
388
389 void InlineFormattingContext::computeWidthAndHeightForReplacedInlineBox(const Box& layoutBox) const
390 {
391     ASSERT(!layoutBox.isContainer());
392     ASSERT(!layoutBox.establishesFormattingContext());
393     ASSERT(layoutBox.replaced());
394
395     computeBorderAndPadding(layoutBox);
396     computeWidthAndMargin(layoutBox);
397     computeHeightAndMargin(layoutBox);
398 }
399
400 void InlineFormattingContext::computeFloatPosition(const FloatingContext& floatingContext, Line& line, const Box& floatBox) const
401 {
402     auto& layoutState = this->layoutState();
403     ASSERT(layoutState.hasDisplayBox(floatBox));
404     auto& displayBox = layoutState.displayBoxForLayoutBox(floatBox);
405
406     // Set static position first.
407     displayBox.setTopLeft({ line.contentLogicalRight(), line.logicalTop() });
408     // Float it.
409     displayBox.setTopLeft(floatingContext.positionForFloat(floatBox));
410 }
411
412 void InlineFormattingContext::computeStaticPosition(const Box&) const
413 {
414 }
415
416 void InlineFormattingContext::collectInlineContentForSubtree(const Box& root, InlineRunProvider& inlineRunProvider) const
417 {
418     // Collect inline content recursively and set breaking rules for the inline elements (for paddings, margins, positioned element etc).
419     auto& inlineFormattingState = this->inlineFormattingState();
420
421     if (root.establishesFormattingContext() && &root != &(this->root())) {
422         // Skip formatting root subtree. They are not part of this inline formatting context.
423         inlineRunProvider.append(root);
424         inlineFormattingState.addDetachingRule(root, { InlineFormattingState::DetachingRule::BreakAtStart, InlineFormattingState::DetachingRule::BreakAtEnd });
425         return;
426     }
427
428     if (!is<Container>(root)) {
429         inlineRunProvider.append(root);
430         return;
431     }
432
433     auto* lastInlineBoxBeforeContainer = inlineFormattingState.lastInlineItem();
434     auto* child = downcast<Container>(root).firstInFlowOrFloatingChild();
435     while (child) {
436         collectInlineContentForSubtree(*child, inlineRunProvider);
437         child = child->nextInFlowOrFloatingSibling();
438     }
439
440     // Setup breaking boundaries for this subtree.
441     auto* lastDescendantInlineBox = inlineFormattingState.lastInlineItem();
442     // Empty container?
443     if (lastInlineBoxBeforeContainer == lastDescendantInlineBox)
444         return;
445
446     auto rootBreaksAtStart = [&] {
447         // FIXME: add padding-inline-start, margin-inline-start etc.
448         return false;
449     };
450
451     auto rootBreaksAtEnd = [&] {
452         // FIXME: add padding-inline-end, margin-inline-end etc.
453         return false;
454     };
455
456     if (rootBreaksAtStart()) {
457         InlineItem* firstDescendantInlineBox = nullptr;
458         auto& inlineContent = inlineFormattingState.inlineContent();
459
460         if (lastInlineBoxBeforeContainer) {
461             auto iterator = inlineContent.find<const InlineItem&, InlineItemHashTranslator>(*lastInlineBoxBeforeContainer);
462             firstDescendantInlineBox = (*++iterator).get();
463         } else
464             firstDescendantInlineBox = inlineContent.first().get();
465
466         ASSERT(firstDescendantInlineBox);
467         inlineFormattingState.addDetachingRule(firstDescendantInlineBox->layoutBox(), InlineFormattingState::DetachingRule::BreakAtStart);
468     }
469
470     if (rootBreaksAtEnd())
471         inlineFormattingState.addDetachingRule(lastDescendantInlineBox->layoutBox(), InlineFormattingState::DetachingRule::BreakAtEnd);
472 }
473
474 void InlineFormattingContext::collectInlineContent(InlineRunProvider& inlineRunProvider) const
475 {
476     collectInlineContentForSubtree(root(), inlineRunProvider);
477 }
478
479 FormattingContext::InstrinsicWidthConstraints InlineFormattingContext::instrinsicWidthConstraints() const
480 {
481     auto& formattingStateForRoot = layoutState().formattingStateForBox(root());
482     if (auto instrinsicWidthConstraints = formattingStateForRoot.instrinsicWidthConstraints(root()))
483         return *instrinsicWidthConstraints;
484
485     auto& inlineFormattingState = this->inlineFormattingState();
486     InlineRunProvider inlineRunProvider(inlineFormattingState);
487     collectInlineContent(inlineRunProvider);
488
489     // Compute width for non-text content.
490     for (auto& inlineRun : inlineRunProvider.runs()) {
491         if (inlineRun.isText())
492             continue;
493
494         computeWidthAndMargin(inlineRun.inlineItem().layoutBox());
495     }
496
497     auto maximumLineWidth = [&](auto availableWidth) {
498         LayoutUnit maxContentLogicalRight;
499         InlineLineBreaker lineBreaker(layoutState(), inlineFormattingState.inlineContent(), inlineRunProvider.runs());
500         LayoutUnit lineLogicalRight;
501         while (auto run = lineBreaker.nextRun(lineLogicalRight, availableWidth, !lineLogicalRight)) {
502             if (run->position == InlineLineBreaker::Run::Position::LineBegin)
503                 lineLogicalRight = 0;
504             lineLogicalRight += run->width;
505
506             maxContentLogicalRight = std::max(maxContentLogicalRight, lineLogicalRight);
507         }
508         return maxContentLogicalRight;
509     };
510
511     auto instrinsicWidthConstraints = FormattingContext::InstrinsicWidthConstraints { maximumLineWidth(0), maximumLineWidth(LayoutUnit::max()) };
512     formattingStateForRoot.setInstrinsicWidthConstraints(root(), instrinsicWidthConstraints);
513     return instrinsicWidthConstraints;
514 }
515
516 }
517 }
518
519 #endif