ebf64fb17fd4b8ea10cf108736bffd39e0bccb3e
[WebKit-https.git] / Source / WebCore / layout / inlineformatting / InlineFormattingContextLineLayout.cpp
1 /*
2  * Copyright (C) 2019 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 "FloatingContext.h"
32 #include "FloatingState.h"
33 #include "InlineFormattingState.h"
34 #include "InlineLine.h"
35 #include "InlineLineBreaker.h"
36 #include "LayoutBox.h"
37 #include "LayoutContainer.h"
38 #include "LayoutState.h"
39 #include "TextUtil.h"
40
41 namespace WebCore {
42 namespace Layout {
43
44 struct UncommittedContent {
45     struct Run {
46         const InlineItem& inlineItem;
47         LayoutUnit logicalWidth;
48         // FIXME: add optional breaking context (start and end position) for split text content.
49     };
50     void add(const InlineItem&, LayoutUnit logicalWidth);
51     void reset();
52
53     Vector<Run> runs() { return m_uncommittedRuns; }
54     bool isEmpty() const { return m_uncommittedRuns.isEmpty(); }
55     unsigned size() const { return m_uncommittedRuns.size(); }
56     LayoutUnit width() const { return m_width; }
57
58 private:
59     Vector<Run> m_uncommittedRuns;
60     LayoutUnit m_width;
61 };
62
63 void UncommittedContent::add(const InlineItem& inlineItem, LayoutUnit logicalWidth)
64 {
65     m_uncommittedRuns.append({ inlineItem, logicalWidth });
66     m_width += logicalWidth;
67 }
68
69 void UncommittedContent::reset()
70 {
71     m_uncommittedRuns.clear();
72     m_width = 0;
73 }
74
75 InlineFormattingContext::LineLayout::LineInput::HorizontalConstraint::HorizontalConstraint(LayoutPoint logicalTopLeft, LayoutUnit availableLogicalWidth)
76     : logicalTopLeft(logicalTopLeft)
77     , availableLogicalWidth(availableLogicalWidth)
78 {
79 }
80
81 InlineFormattingContext::LineLayout::LineInput::LineInput(LayoutPoint logicalTopLeft, LayoutUnit availableLogicalWidth, SkipVerticalAligment skipVerticalAligment, unsigned firstInlineItemIndex, const InlineItems& inlineItems)
82     : horizontalConstraint(logicalTopLeft, availableLogicalWidth)
83     , skipVerticalAligment(skipVerticalAligment)
84     , firstInlineItemIndex(firstInlineItemIndex)
85     , inlineItems(inlineItems)
86 {
87 }
88
89 InlineFormattingContext::LineLayout::LineLayout(const InlineFormattingContext& inlineFormattingContext)
90     : m_formattingContext(inlineFormattingContext)
91     , m_formattingState(m_formattingContext.formattingState())
92     , m_floatingState(m_formattingState.floatingState())
93     , m_formattingRoot(downcast<Container>(m_formattingContext.root()))
94 {
95 }
96
97 static LayoutUnit inlineItemWidth(const LayoutState& layoutState, const InlineItem& inlineItem, LayoutUnit contentLogicalLeft)
98 {
99     if (inlineItem.isLineBreak())
100         return 0;
101
102     if (is<InlineTextItem>(inlineItem)) {
103         auto& inlineTextItem = downcast<InlineTextItem>(inlineItem);
104         auto end = inlineTextItem.isCollapsed() ? inlineTextItem.start() + 1 : inlineTextItem.end();
105         return TextUtil::width(downcast<InlineBox>(inlineTextItem.layoutBox()), inlineTextItem.start(), end, contentLogicalLeft);
106     }
107
108     auto& layoutBox = inlineItem.layoutBox();
109     ASSERT(layoutState.hasDisplayBox(layoutBox));
110     auto& displayBox = layoutState.displayBoxForLayoutBox(layoutBox);
111
112     if (layoutBox.isFloatingPositioned())
113         return displayBox.marginBoxWidth();
114
115     if (layoutBox.isReplaced())
116         return displayBox.width();
117
118     if (inlineItem.isContainerStart())
119         return displayBox.marginStart() + displayBox.borderLeft() + displayBox.paddingLeft().valueOr(0);
120
121     if (inlineItem.isContainerEnd())
122         return displayBox.marginEnd() + displayBox.borderRight() + displayBox.paddingRight().valueOr(0);
123
124     // Non-replaced inline box (e.g. inline-block)
125     return displayBox.width();
126 }
127
128 InlineFormattingContext::LineLayout::LineContent InlineFormattingContext::LineLayout::placeInlineItems(const LineInput& lineInput) const
129 {
130     std::unique_ptr<Line> line;
131     if (lineInput.skipVerticalAligment == LineInput::SkipVerticalAligment::No) {
132         auto mimimumLineHeight = m_formattingRoot.style().computedLineHeight();
133         auto initialBaselineOffset = Line::halfLeadingMetrics(m_formattingRoot.style().fontMetrics(), mimimumLineHeight).ascent;
134         line = std::make_unique<Line>(layoutState(), lineInput.horizontalConstraint.logicalTopLeft, lineInput.horizontalConstraint.availableLogicalWidth, mimimumLineHeight, initialBaselineOffset);
135     } else
136         line = std::make_unique<Line>(layoutState(), lineInput.horizontalConstraint.logicalTopLeft.x(), lineInput.horizontalConstraint.availableLogicalWidth);
137
138     Vector<WeakPtr<InlineItem>> floats;
139     unsigned committedInlineItemCount = 0;
140
141     UncommittedContent uncommittedContent;
142     auto commitPendingContent = [&] {
143         if (uncommittedContent.isEmpty())
144             return;
145         committedInlineItemCount += uncommittedContent.size();
146         for (auto& uncommittedRun : uncommittedContent.runs()) {
147             auto& inlineItem = uncommittedRun.inlineItem;
148             if (inlineItem.isHardLineBreak())
149                 line->appendHardLineBreak(inlineItem);
150             else if (is<InlineTextItem>(inlineItem))
151                 line->appendTextContent(downcast<InlineTextItem>(inlineItem), uncommittedRun.logicalWidth);
152             else if (inlineItem.isContainerStart())
153                 line->appendInlineContainerStart(inlineItem, uncommittedRun.logicalWidth);
154             else if (inlineItem.isContainerEnd())
155                 line->appendInlineContainerEnd(inlineItem, uncommittedRun.logicalWidth);
156             else if (inlineItem.layoutBox().isReplaced())
157                 line->appendReplacedInlineBox(inlineItem, uncommittedRun.logicalWidth);
158             else
159                 line->appendNonReplacedInlineBox(inlineItem, uncommittedRun.logicalWidth);
160         }
161         uncommittedContent.reset();
162     };
163
164     auto lineHasFloatBox = lineInput.floatMinimumLogicalBottom.hasValue();
165     auto closeLine = [&] {
166         ASSERT(committedInlineItemCount || lineHasFloatBox);
167         auto lastCommittedIndex = committedInlineItemCount ? Optional<unsigned> { lineInput.firstInlineItemIndex + (committedInlineItemCount - 1) } : WTF::nullopt;
168         return LineContent { lastCommittedIndex, WTFMove(floats), line->close() };
169     };
170     LineBreaker lineBreaker;
171     // Iterate through the inline content and place the inline boxes on the current line.
172     for (auto inlineItemIndex = lineInput.firstInlineItemIndex; inlineItemIndex < lineInput.inlineItems.size(); ++inlineItemIndex) {
173         auto availableWidth = line->availableWidth() - uncommittedContent.width();
174         auto currentLogicalRight = line->contentLogicalRight() + uncommittedContent.width();
175         auto& inlineItem = lineInput.inlineItems[inlineItemIndex];
176         auto itemLogicalWidth = inlineItemWidth(layoutState(), *inlineItem, currentLogicalRight);
177
178         // FIXME: Ensure LineContext::trimmableWidth includes uncommitted content if needed.
179         auto lineIsConsideredEmpty = !line->hasContent() && !lineHasFloatBox;
180         auto breakingContext = lineBreaker.breakingContext(*inlineItem, itemLogicalWidth, { availableWidth, currentLogicalRight, line->trailingTrimmableWidth(), lineIsConsideredEmpty });
181         if (breakingContext.isAtBreakingOpportunity)
182             commitPendingContent();
183
184         // Content does not fit the current line.
185         if (breakingContext.breakingBehavior == LineBreaker::BreakingBehavior::Wrap)
186             return closeLine();
187
188         // Partial content stays on the current line. 
189         if (breakingContext.breakingBehavior == LineBreaker::BreakingBehavior::Split) {
190             ASSERT(inlineItem->isText());
191
192             ASSERT_NOT_IMPLEMENTED_YET();
193             return closeLine();
194         }
195
196         ASSERT(breakingContext.breakingBehavior == LineBreaker::BreakingBehavior::Keep);
197         if (inlineItem->isFloat()) {
198             auto& floatBox = inlineItem->layoutBox();
199             ASSERT(layoutState().hasDisplayBox(floatBox));
200             // Shrink availble space for current line and move existing inline runs.
201             auto floatBoxWidth = layoutState().displayBoxForLayoutBox(floatBox).marginBoxWidth();
202             floatBox.isLeftFloatingPositioned() ? line->moveLogicalLeft(floatBoxWidth) : line->moveLogicalRight(floatBoxWidth);
203             floats.append(makeWeakPtr(*inlineItem));
204             ++committedInlineItemCount;
205             lineHasFloatBox = true;
206             continue;
207         }
208
209         uncommittedContent.add(*inlineItem, itemLogicalWidth);
210         if (breakingContext.isAtBreakingOpportunity)
211             commitPendingContent();
212
213         if (inlineItem->isHardLineBreak())
214             return closeLine();
215     }
216     commitPendingContent();
217     return closeLine();
218 }
219
220 void InlineFormattingContext::LineLayout::layout(LayoutUnit widthConstraint) const
221 {
222     ASSERT(!m_formattingState.inlineItems().isEmpty());
223
224     auto& formattingRootDisplayBox = layoutState().displayBoxForLayoutBox(m_formattingRoot);
225     auto lineLogicalTop = formattingRootDisplayBox.contentBoxTop();
226     auto lineLogicalLeft = formattingRootDisplayBox.contentBoxLeft();
227
228     auto applyFloatConstraint = [&](auto& lineInput) {
229         // Check for intruding floats and adjust logical left/available width for this line accordingly.
230         if (m_floatingState.isEmpty())
231             return;
232         auto availableWidth = lineInput.horizontalConstraint.availableLogicalWidth;
233         auto lineLogicalLeft = lineInput.horizontalConstraint.logicalTopLeft.x();
234         auto floatConstraints = m_floatingState.constraints({ lineLogicalTop }, m_formattingRoot);
235         // Check if these constraints actually put limitation on the line.
236         if (floatConstraints.left && floatConstraints.left->x <= formattingRootDisplayBox.contentBoxLeft())
237             floatConstraints.left = { };
238
239         if (floatConstraints.right && floatConstraints.right->x >= formattingRootDisplayBox.contentBoxRight())
240             floatConstraints.right = { };
241
242         // Set the minimum float bottom value as a hint for the next line if needed.
243         static auto inifitePoint = PointInContextRoot::max();
244         auto floatMinimumLogicalBottom = std::min(floatConstraints.left.valueOr(inifitePoint).y, floatConstraints.right.valueOr(inifitePoint).y);
245         if (floatMinimumLogicalBottom != inifitePoint.y)
246             lineInput.floatMinimumLogicalBottom = floatMinimumLogicalBottom;
247
248         if (floatConstraints.left && floatConstraints.right) {
249             ASSERT(floatConstraints.left->x <= floatConstraints.right->x);
250             availableWidth = floatConstraints.right->x - floatConstraints.left->x;
251             lineLogicalLeft = floatConstraints.left->x;
252         } else if (floatConstraints.left) {
253             ASSERT(floatConstraints.left->x >= lineLogicalLeft);
254             availableWidth -= (floatConstraints.left->x - lineLogicalLeft);
255             lineLogicalLeft = floatConstraints.left->x;
256         } else if (floatConstraints.right) {
257             ASSERT(floatConstraints.right->x >= lineLogicalLeft);
258             availableWidth = floatConstraints.right->x - lineLogicalLeft;
259         }
260         lineInput.horizontalConstraint.availableLogicalWidth = availableWidth;
261         lineInput.horizontalConstraint.logicalTopLeft.setX(lineLogicalLeft);
262     };
263
264     auto& inlineItems = m_formattingState.inlineItems();
265     unsigned currentInlineItemIndex = 0;
266     while (currentInlineItemIndex < inlineItems.size()) {
267         auto lineInput = LineInput { { lineLogicalLeft, lineLogicalTop }, widthConstraint, LineInput::SkipVerticalAligment::No, currentInlineItemIndex, inlineItems };
268         applyFloatConstraint(lineInput);
269         auto lineContent = placeInlineItems(lineInput);
270         createDisplayRuns(*lineContent.runs, lineContent.floats, widthConstraint);
271         if (!lineContent.lastInlineItemIndex) {
272             // Floats prevented us putting any content on the line.
273             ASSERT(lineInput.floatMinimumLogicalBottom);
274             ASSERT(lineContent.runs->isEmpty());
275             lineLogicalTop = *lineInput.floatMinimumLogicalBottom;
276         } else {
277             currentInlineItemIndex = *lineContent.lastInlineItemIndex + 1;
278             lineLogicalTop = lineContent.runs->logicalBottom();
279         }
280     }
281 }
282
283 LayoutUnit InlineFormattingContext::LineLayout::computedIntrinsicWidth(LayoutUnit widthConstraint) const
284 {
285     LayoutUnit maximumLineWidth;
286     auto& inlineItems = m_formattingState.inlineItems();
287     unsigned currentInlineItemIndex = 0;
288     while (currentInlineItemIndex < inlineItems.size()) {
289         auto lineContent = placeInlineItems({ { }, widthConstraint, LineInput::SkipVerticalAligment::Yes, currentInlineItemIndex, inlineItems });
290         currentInlineItemIndex = *lineContent.lastInlineItemIndex + 1;
291         LayoutUnit floatsWidth;
292         for (auto& floatItem : lineContent.floats)
293             floatsWidth += layoutState().displayBoxForLayoutBox(floatItem->layoutBox()).marginBoxWidth();
294         maximumLineWidth = std::max(maximumLineWidth, floatsWidth + lineContent.runs->logicalWidth());
295     }
296     return maximumLineWidth;
297 }
298
299 void InlineFormattingContext::LineLayout::createDisplayRuns(const Line::Content& lineContent, const Vector<WeakPtr<InlineItem>>& floats, LayoutUnit widthConstraint) const
300 {
301     auto floatingContext = FloatingContext { m_floatingState };
302
303     // Move floats to their final position.
304     for (auto floatItem : floats) {
305         auto& floatBox = floatItem->layoutBox();
306         ASSERT(layoutState().hasDisplayBox(floatBox));
307         auto& displayBox = layoutState().displayBoxForLayoutBox(floatBox);
308         // Set static position first.
309         displayBox.setTopLeft({ lineContent.logicalLeft(), lineContent.logicalTop() });
310         // Float it.
311         displayBox.setTopLeft(floatingContext.positionForFloat(floatBox));
312         m_floatingState.append(floatBox);
313     }
314
315     if (lineContent.isEmpty()) {
316         // Spec tells us to create a zero height, empty line box.
317         auto lineBox = Display::Rect { lineContent.logicalTop(), lineContent.logicalLeft(), 0 , 0 };
318         m_formattingState.addLineBox({ lineBox, lineContent.baseline(), lineContent.baselineOffset() });
319         return;
320     }
321
322     auto& inlineDisplayRuns = m_formattingState.inlineRuns(); 
323     Optional<unsigned> previousLineLastRunIndex = inlineDisplayRuns.isEmpty() ? Optional<unsigned>() : inlineDisplayRuns.size() - 1;
324     // 9.4.2 Inline formatting contexts
325     // A line box is always tall enough for all of the boxes it contains.
326
327     // Ignore the initial strut.
328     auto lineBox = Display::Rect { lineContent.logicalTop(), lineContent.logicalLeft(), 0, lineContent.logicalHeight()};
329     // Create final display runs.
330     auto& lineRuns = lineContent.runs();
331     for (unsigned index = 0; index < lineRuns.size(); ++index) {
332         auto& lineRun = lineRuns.at(index);
333
334         auto& inlineItem = lineRun->inlineItem;
335         auto& logicalRect = lineRun->logicalRect;
336         auto& layoutBox = inlineItem.layoutBox();
337         auto& displayBox = layoutState().displayBoxForLayoutBox(layoutBox);
338
339         if (inlineItem.isHardLineBreak()) {
340             displayBox.setTopLeft(logicalRect.topLeft());
341             displayBox.setContentBoxWidth(logicalRect.width());
342             displayBox.setContentBoxHeight(logicalRect.height());
343             m_formattingState.addInlineRun(std::make_unique<Display::Run>(logicalRect));
344             continue;
345         }
346
347         // Inline level box (replaced or inline-block)
348         if (inlineItem.isBox()) {
349             auto topLeft = logicalRect.topLeft();
350             if (layoutBox.isInFlowPositioned())
351                 topLeft += Geometry::inFlowPositionedPositionOffset(layoutState(), layoutBox);
352             displayBox.setTopLeft(topLeft);
353             lineBox.expandHorizontally(logicalRect.width());
354             m_formattingState.addInlineRun(std::make_unique<Display::Run>(logicalRect));
355             continue;
356         }
357
358         // Inline level container start (<span>)
359         if (inlineItem.isContainerStart()) {
360             displayBox.setTopLeft(logicalRect.topLeft());
361             lineBox.expandHorizontally(logicalRect.width());
362             continue;
363         }
364
365         // Inline level container end (</span>)
366         if (inlineItem.isContainerEnd()) {
367             if (layoutBox.isInFlowPositioned()) {
368                 auto inflowOffset = Geometry::inFlowPositionedPositionOffset(layoutState(), layoutBox);
369                 displayBox.moveHorizontally(inflowOffset.width());
370                 displayBox.moveVertically(inflowOffset.height());
371             }
372             auto marginBoxWidth = logicalRect.left() - displayBox.left();
373             auto contentBoxWidth = marginBoxWidth - (displayBox.marginStart() + displayBox.borderLeft() + displayBox.paddingLeft().valueOr(0));
374             // FIXME fix it for multiline.
375             displayBox.setContentBoxWidth(contentBoxWidth);
376             displayBox.setContentBoxHeight(logicalRect.height());
377             lineBox.expandHorizontally(logicalRect.width());
378             continue;
379         }
380
381         // Text content. Try to join multiple text runs when possible.
382         ASSERT(lineRun->textContext);        
383         const Line::Content::Run* previousLineRun = !index ? nullptr : lineRuns[index - 1].get();
384         if (!lineRun->isCollapsed) {
385             auto previousRunCanBeExtended = previousLineRun ? previousLineRun->canBeExtended : false;
386             auto requiresNewRun = !index || !previousRunCanBeExtended || &layoutBox != &previousLineRun->inlineItem.layoutBox();
387             if (requiresNewRun)
388                 m_formattingState.addInlineRun(std::make_unique<Display::Run>(logicalRect, Display::Run::TextContext { lineRun->textContext->start, lineRun->textContext->length }));
389             else {
390                 auto& lastDisplayRun = m_formattingState.inlineRuns().last();
391                 lastDisplayRun->expandHorizontally(logicalRect.width());
392                 lastDisplayRun->textContext()->expand(lineRun->textContext->length);
393             }
394             lineBox.expandHorizontally(logicalRect.width());
395         }
396         // FIXME take content breaking into account when part of the layout box is on the previous line.
397         auto firstInlineRunForLayoutBox = !previousLineRun || &previousLineRun->inlineItem.layoutBox() != &layoutBox;
398         if (firstInlineRunForLayoutBox) {
399             // Setup display box for the associated layout box.
400             displayBox.setTopLeft(logicalRect.topLeft());
401             displayBox.setContentBoxWidth(lineRun->isCollapsed ? LayoutUnit() : logicalRect.width());
402             displayBox.setContentBoxHeight(logicalRect.height());
403         } else if (!lineRun->isCollapsed) {
404             // FIXME fix it for multirun/multiline.
405             displayBox.setContentBoxWidth(displayBox.contentBoxWidth() + logicalRect.width());
406         }
407     }
408     // FIXME linebox needs to be ajusted after content alignment.
409     m_formattingState.addLineBox({ lineBox, lineContent.baseline(), lineContent.baselineOffset() });
410     alignRuns(m_formattingRoot.style().textAlign(), previousLineLastRunIndex.valueOr(-1) + 1, widthConstraint - lineContent.logicalWidth());
411 }
412
413 static Optional<LayoutUnit> horizontalAdjustmentForAlignment(TextAlignMode align, LayoutUnit remainingWidth)
414 {
415     switch (align) {
416     case TextAlignMode::Left:
417     case TextAlignMode::WebKitLeft:
418     case TextAlignMode::Start:
419         return { };
420     case TextAlignMode::Right:
421     case TextAlignMode::WebKitRight:
422     case TextAlignMode::End:
423         return std::max(remainingWidth, 0_lu);
424     case TextAlignMode::Center:
425     case TextAlignMode::WebKitCenter:
426         return std::max(remainingWidth / 2, 0_lu);
427     case TextAlignMode::Justify:
428         ASSERT_NOT_REACHED();
429         break;
430     }
431     ASSERT_NOT_REACHED();
432     return { };
433 }
434
435 void InlineFormattingContext::LineLayout::alignRuns(TextAlignMode textAlign, unsigned firstRunIndex, LayoutUnit availableWidth) const
436 {
437     auto adjustment = horizontalAdjustmentForAlignment(textAlign, availableWidth);
438     if (!adjustment)
439         return;
440
441     auto& inlineDisplayRuns = m_formattingState.inlineRuns(); 
442     for (unsigned index = firstRunIndex; index < inlineDisplayRuns.size(); ++index)
443         inlineDisplayRuns[index]->moveHorizontally(*adjustment);
444 }
445
446 }
447 }
448
449 #endif