Cache glyphs (using display lists) when painting at high frequency
[WebKit-https.git] / Source / WebCore / rendering / SimpleLineLayout.cpp
1 /*
2  * Copyright (C) 2013 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 "SimpleLineLayout.h"
28
29 #include "FontCache.h"
30 #include "Frame.h"
31 #include "GraphicsContext.h"
32 #include "HTMLTextFormControlElement.h"
33 #include "HitTestLocation.h"
34 #include "HitTestRequest.h"
35 #include "HitTestResult.h"
36 #include "Hyphenation.h"
37 #include "InlineTextBox.h"
38 #include "LineWidth.h"
39 #include "Logging.h"
40 #include "PaintInfo.h"
41 #include "RenderBlockFlow.h"
42 #include "RenderChildIterator.h"
43 #include "RenderFragmentedFlow.h"
44 #include "RenderLineBreak.h"
45 #include "RenderMultiColumnFlow.h"
46 #include "RenderStyle.h"
47 #include "RenderText.h"
48 #include "RenderTextControl.h"
49 #include "RenderView.h"
50 #include "Settings.h"
51 #include "SimpleLineLayoutFlowContents.h"
52 #include "SimpleLineLayoutFunctions.h"
53 #include "SimpleLineLayoutTextFragmentIterator.h"
54 #include "Text.h"
55 #include "TextPaintStyle.h"
56 #include <pal/Logging.h>
57
58 namespace WebCore {
59 namespace SimpleLineLayout {
60
61 #ifndef NDEBUG
62 #define SET_REASON_AND_RETURN_IF_NEEDED(reason, reasons, includeReasons) { \
63         reasons |= reason; \
64         if (includeReasons == IncludeReasons::First) \
65             return reasons; \
66     }
67 #else
68 #define SET_REASON_AND_RETURN_IF_NEEDED(reason, reasons, includeReasons) { \
69         ASSERT_UNUSED(includeReasons, includeReasons == IncludeReasons::First); \
70         reasons |= reason; \
71         return reasons; \
72     }
73 #endif
74
75
76 template <typename CharacterType> AvoidanceReasonFlags canUseForCharacter(CharacterType, bool textIsJustified, IncludeReasons);
77
78 template<> AvoidanceReasonFlags canUseForCharacter(UChar character, bool textIsJustified, IncludeReasons includeReasons)
79 {
80     AvoidanceReasonFlags reasons = { };
81     if (textIsJustified) {
82         // Include characters up to Latin Extended-B and some punctuation range when text is justified.
83         bool isLatinIncludingExtendedB = character <= 0x01FF;
84         bool isPunctuationRange = character >= 0x2010 && character <= 0x2027;
85         if (!(isLatinIncludingExtendedB || isPunctuationRange))
86             SET_REASON_AND_RETURN_IF_NEEDED(FlowHasJustifiedNonLatinText, reasons, includeReasons);
87     }
88
89     if (U16_IS_SURROGATE(character))
90         SET_REASON_AND_RETURN_IF_NEEDED(FlowTextHasSurrogatePair, reasons, includeReasons);
91     
92     UCharDirection direction = u_charDirection(character);
93     if (direction == U_RIGHT_TO_LEFT || direction == U_RIGHT_TO_LEFT_ARABIC
94         || direction == U_RIGHT_TO_LEFT_EMBEDDING || direction == U_RIGHT_TO_LEFT_OVERRIDE
95         || direction == U_LEFT_TO_RIGHT_EMBEDDING || direction == U_LEFT_TO_RIGHT_OVERRIDE
96         || direction == U_POP_DIRECTIONAL_FORMAT || direction == U_BOUNDARY_NEUTRAL)
97         SET_REASON_AND_RETURN_IF_NEEDED(FlowTextHasDirectionCharacter, reasons, includeReasons);
98
99     return reasons;
100 }
101
102 template<> AvoidanceReasonFlags canUseForCharacter(LChar, bool, IncludeReasons)
103 {
104     return { };
105 }
106
107 template <typename CharacterType>
108 static AvoidanceReasonFlags canUseForText(const CharacterType* text, unsigned length, const FontCascade& fontCascade, std::optional<float> lineHeightConstraint,
109     bool textIsJustified, IncludeReasons includeReasons)
110 {
111     AvoidanceReasonFlags reasons = { };
112     auto& primaryFont = fontCascade.primaryFont();
113     auto& fontMetrics = primaryFont.fontMetrics();
114     auto availableSpaceForGlyphAscent = fontMetrics.ascent();
115     auto availableSpaceForGlyphDescent = fontMetrics.descent();
116     if (lineHeightConstraint) {
117         auto lineHeightPadding = *lineHeightConstraint - fontMetrics.height();
118         availableSpaceForGlyphAscent += lineHeightPadding / 2;
119         availableSpaceForGlyphDescent += lineHeightPadding / 2;
120     }
121
122     for (unsigned i = 0; i < length; ++i) {
123         auto character = text[i];
124         if (FontCascade::treatAsSpace(character))
125             continue;
126
127         if (character == softHyphen)
128             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextHasSoftHyphen, reasons, includeReasons);
129
130         auto characterReasons = canUseForCharacter(character, textIsJustified, includeReasons);
131         if (characterReasons != NoReason)
132             SET_REASON_AND_RETURN_IF_NEEDED(characterReasons, reasons, includeReasons);
133
134         auto glyphData = fontCascade.glyphDataForCharacter(character, false);
135         if (!glyphData.isValid() || glyphData.font != &primaryFont)
136             SET_REASON_AND_RETURN_IF_NEEDED(FlowPrimaryFontIsInsufficient, reasons, includeReasons);
137
138         if (lineHeightConstraint) {
139             auto bounds = primaryFont.boundsForGlyph(glyphData.glyph);
140             if (ceilf(-bounds.y()) > availableSpaceForGlyphAscent || ceilf(bounds.maxY()) > availableSpaceForGlyphDescent)
141                 SET_REASON_AND_RETURN_IF_NEEDED(FlowFontHasOverflowGlyph, reasons, includeReasons);
142         }
143     }
144     return reasons;
145 }
146
147 static AvoidanceReasonFlags canUseForText(StringView text, const FontCascade& fontCascade, std::optional<float> lineHeightConstraint, bool textIsJustified, IncludeReasons includeReasons)
148 {
149     if (text.is8Bit())
150         return canUseForText(text.characters8(), text.length(), fontCascade, lineHeightConstraint, textIsJustified, includeReasons);
151     return canUseForText(text.characters16(), text.length(), fontCascade, lineHeightConstraint, textIsJustified, includeReasons);
152 }
153
154 static AvoidanceReasonFlags canUseForFontAndText(const RenderBlockFlow& flow, IncludeReasons includeReasons)
155 {
156     AvoidanceReasonFlags reasons = { };
157     // We assume that all lines have metrics based purely on the primary font.
158     const auto& style = flow.style();
159     auto& fontCascade = style.fontCascade();
160     if (fontCascade.primaryFont().isInterstitial())
161         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsMissingPrimaryFont, reasons, includeReasons);
162     std::optional<float> lineHeightConstraint;
163     if (style.lineBoxContain() & LineBoxContainGlyphs)
164         lineHeightConstraint = lineHeightFromFlow(flow).toFloat();
165     bool flowIsJustified = style.textAlign() == JUSTIFY;
166     for (const auto& textRenderer : childrenOfType<RenderText>(flow)) {
167         // FIXME: Do not return until after checking all children.
168         if (textRenderer.text().isEmpty())
169             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsEmpty, reasons, includeReasons);
170         if (textRenderer.isCombineText())
171             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsCombineText, reasons, includeReasons);
172         if (textRenderer.isCounter())
173             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsRenderCounter, reasons, includeReasons);
174         if (textRenderer.isQuote())
175             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsRenderQuote, reasons, includeReasons);
176         if (textRenderer.isTextFragment())
177             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsTextFragment, reasons, includeReasons);
178         if (textRenderer.isSVGInlineText())
179             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsSVGInlineText, reasons, includeReasons);
180         if (!textRenderer.canUseSimpleFontCodePath()) {
181             // No need to check the code path at this point. We already know it can't be simple.
182             SET_REASON_AND_RETURN_IF_NEEDED(FlowHasComplexFontCodePath, reasons, includeReasons);
183         } else {
184             TextRun run(String(textRenderer.text()));
185             run.setCharacterScanForCodePath(false);
186             if (style.fontCascade().codePath(run) != FontCascade::Simple)
187                 SET_REASON_AND_RETURN_IF_NEEDED(FlowHasComplexFontCodePath, reasons, includeReasons);
188         }
189
190         auto textReasons = canUseForText(textRenderer.stringView(), fontCascade, lineHeightConstraint, flowIsJustified, includeReasons);
191         if (textReasons != NoReason)
192             SET_REASON_AND_RETURN_IF_NEEDED(textReasons, reasons, includeReasons);
193     }
194     return reasons;
195 }
196
197 static AvoidanceReasonFlags canUseForStyle(const RenderStyle& style, IncludeReasons includeReasons)
198 {
199     AvoidanceReasonFlags reasons = { };
200     if (style.textOverflow())
201         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextOverflow, reasons, includeReasons);
202     if ((style.textDecorationsInEffect() & TextDecorationUnderline) && style.textUnderlinePosition() == TextUnderlinePositionUnder)
203         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasUnsupportedUnderlineDecoration, reasons, includeReasons);
204     // Non-visible overflow should be pretty easy to support.
205     if (style.overflowX() != OVISIBLE || style.overflowY() != OVISIBLE)
206         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasOverflowNotVisible, reasons, includeReasons);
207     if (!style.isLeftToRightDirection())
208         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsNotLTR, reasons, includeReasons);
209     if (!(style.lineBoxContain() & LineBoxContainBlock))
210         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasLineBoxContainProperty, reasons, includeReasons);
211     if (style.writingMode() != TopToBottomWritingMode)
212         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsNotTopToBottom, reasons, includeReasons);
213     if (style.lineBreak() != LineBreakAuto)
214         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasLineBreak, reasons, includeReasons);
215     if (style.unicodeBidi() != UBNormal)
216         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasNonNormalUnicodeBiDi, reasons, includeReasons);
217     if (style.rtlOrdering() != LogicalOrder)
218         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasRTLOrdering, reasons, includeReasons);
219     if (style.lineAlign() != LineAlignNone)
220         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasLineAlignEdges, reasons, includeReasons);
221     if (style.lineSnap() != LineSnapNone)
222         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasLineSnap, reasons, includeReasons);
223     if (style.textEmphasisFill() != TextEmphasisFillFilled || style.textEmphasisMark() != TextEmphasisMarkNone)
224         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextEmphasisFillOrMark, reasons, includeReasons);
225     if (style.textShadow())
226         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextShadow, reasons, includeReasons);
227     if (style.hasPseudoStyle(FIRST_LINE))
228         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasPseudoFirstLine, reasons, includeReasons);
229     if (style.hasPseudoStyle(FIRST_LETTER))
230         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasPseudoFirstLetter, reasons, includeReasons);
231     if (style.hasTextCombine())
232         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextCombine, reasons, includeReasons);
233     if (style.backgroundClip() == TextFillBox)
234         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextFillBox, reasons, includeReasons);
235     if (style.borderFit() == BorderFitLines)
236         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasBorderFitLines, reasons, includeReasons);
237     if (style.lineBreak() != LineBreakAuto)
238         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasNonAutoLineBreak, reasons, includeReasons);
239     if (style.nbspMode() != NBNORMAL)
240         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasWebKitNBSPMode, reasons, includeReasons);
241 #if ENABLE(CSS_TRAILING_WORD)
242     if (style.trailingWord() != TrailingWord::Auto)
243         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasNonAutoTrailingWord, reasons, includeReasons);
244 #endif
245     if (style.hyphens() == HyphensAuto) {
246         auto textReasons = canUseForText(style.hyphenString(), style.fontCascade(), std::nullopt, false, includeReasons);
247         if (textReasons != NoReason)
248             SET_REASON_AND_RETURN_IF_NEEDED(textReasons, reasons, includeReasons);
249     }
250     return reasons;
251 }
252
253 AvoidanceReasonFlags canUseForWithReason(const RenderBlockFlow& flow, IncludeReasons includeReasons)
254 {
255 #ifndef NDEBUG
256     static std::once_flag onceFlag;
257     std::call_once(onceFlag, [] {
258         PAL::registerNotifyCallback("com.apple.WebKit.showSimpleLineLayoutCoverage", WTF::Function<void()> { printSimpleLineLayoutCoverage });
259         PAL::registerNotifyCallback("com.apple.WebKit.showSimpleLineLayoutReasons", WTF::Function<void()> { printSimpleLineLayoutBlockList });
260         PAL::registerNotifyCallback("com.apple.WebKit.toggleSimpleLineLayout", WTF::Function<void()> { toggleSimpleLineLayout });
261     });
262 #endif
263     AvoidanceReasonFlags reasons = { };
264     if (!flow.settings().simpleLineLayoutEnabled())
265         SET_REASON_AND_RETURN_IF_NEEDED(FeatureIsDisabled, reasons, includeReasons);
266     if (!flow.parent())
267         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasNoParent, reasons, includeReasons);
268     if (!flow.firstChild())
269         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasNoChild, reasons, includeReasons);
270     if (flow.fragmentedFlowState() != RenderObject::NotInsideFragmentedFlow) {
271         auto* fragmentedFlow = flow.enclosingFragmentedFlow();
272         if (!is<RenderMultiColumnFlow>(fragmentedFlow))
273             SET_REASON_AND_RETURN_IF_NEEDED(FlowIsInsideANonMultiColumnThread, reasons, includeReasons);
274         auto& columnThread = downcast<RenderMultiColumnFlow>(*fragmentedFlow);
275         if (columnThread.parent() != &flow.view())
276             SET_REASON_AND_RETURN_IF_NEEDED(MultiColumnFlowIsNotTopLevel, reasons, includeReasons);
277         if (columnThread.hasColumnSpanner())
278             SET_REASON_AND_RETURN_IF_NEEDED(MultiColumnFlowHasColumnSpanner, reasons, includeReasons);
279         auto& style = flow.style();
280         if (style.verticalAlign() != BASELINE)
281             SET_REASON_AND_RETURN_IF_NEEDED(MultiColumnFlowVerticalAlign, reasons, includeReasons);
282         if (style.isFloating())
283             SET_REASON_AND_RETURN_IF_NEEDED(MultiColumnFlowIsFloating, reasons, includeReasons);
284     }
285     if (!flow.isHorizontalWritingMode())
286         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasHorizonalWritingMode, reasons, includeReasons);
287     if (flow.hasOutline())
288         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasOutline, reasons, includeReasons);
289     if (flow.isRubyText() || flow.isRubyBase())
290         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsRuby, reasons, includeReasons);
291     if (flow.style().hangingPunctuation() != NoHangingPunctuation)
292         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasHangingPunctuation, reasons, includeReasons);
293     
294     // Printing does pagination without a flow thread.
295     if (flow.document().paginated())
296         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsPaginated, reasons, includeReasons);
297     if (flow.firstLineBlock())
298         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasPseudoFirstLine, reasons, includeReasons);
299     if (flow.isAnonymousBlock() && flow.parent()->style().textOverflow())
300         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextOverflow, reasons, includeReasons);
301     if (flow.parent()->isDeprecatedFlexibleBox())
302         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsDepricatedFlexBox, reasons, includeReasons);
303     // FIXME: Placeholders do something strange.
304     if (is<RenderTextControl>(*flow.parent()) && downcast<RenderTextControl>(*flow.parent()).textFormControlElement().placeholderElement())
305         SET_REASON_AND_RETURN_IF_NEEDED(FlowParentIsPlaceholderElement, reasons, includeReasons);
306     // FIXME: Implementation of wrap=hard looks into lineboxes.
307     if (flow.parent()->isTextArea() && flow.parent()->element()->hasAttributeWithoutSynchronization(HTMLNames::wrapAttr))
308         SET_REASON_AND_RETURN_IF_NEEDED(FlowParentIsTextAreaWithWrapping, reasons, includeReasons);
309     // This currently covers <blockflow>#text</blockflow>, <blockflow>#text<br></blockflow> and mutiple (sibling) RenderText cases.
310     // The <blockflow><inline>#text</inline></blockflow> case is also popular and should be relatively easy to cover.
311     for (const auto* child = flow.firstChild(); child;) {
312         if (child->selectionState() != RenderObject::SelectionNone)
313             SET_REASON_AND_RETURN_IF_NEEDED(FlowChildIsSelected, reasons, includeReasons);
314         if (is<RenderText>(*child)) {
315             child = child->nextSibling();
316             continue;
317         }
318         if (is<RenderLineBreak>(child) && !downcast<RenderLineBreak>(*child).isWBR() && child->style().clear() == CNONE) {
319             child = child->nextSibling();
320             continue;
321         }
322         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasNonSupportedChild, reasons, includeReasons);
323         break;
324     }
325     auto styleReasons = canUseForStyle(flow.style(), includeReasons);
326     if (styleReasons != NoReason)
327         SET_REASON_AND_RETURN_IF_NEEDED(styleReasons, reasons, includeReasons);
328     // We can't use the code path if any lines would need to be shifted below floats. This is because we don't keep per-line y coordinates.
329     if (flow.containsFloats()) {
330         float minimumWidthNeeded = std::numeric_limits<float>::max();
331         for (const auto& textRenderer : childrenOfType<RenderText>(flow)) {
332             minimumWidthNeeded = std::min(minimumWidthNeeded, textRenderer.minLogicalWidth());
333
334             for (auto& floatingObject : *flow.floatingObjectSet()) {
335                 ASSERT(floatingObject);
336                 // if a float has a shape, we cannot tell if content will need to be shifted until after we lay it out,
337                 // since the amount of space is not uniform for the height of the float.
338                 if (floatingObject->renderer().shapeOutsideInfo())
339                     SET_REASON_AND_RETURN_IF_NEEDED(FlowHasUnsupportedFloat, reasons, includeReasons);
340                 float availableWidth = flow.availableLogicalWidthForLine(floatingObject->y(), DoNotIndentText);
341                 if (availableWidth < minimumWidthNeeded)
342                     SET_REASON_AND_RETURN_IF_NEEDED(FlowHasUnsupportedFloat, reasons, includeReasons);
343             }
344         }
345     }
346     auto fontAndTextReasons = canUseForFontAndText(flow, includeReasons);
347     if (fontAndTextReasons != NoReason)
348         SET_REASON_AND_RETURN_IF_NEEDED(fontAndTextReasons, reasons, includeReasons);
349     return reasons;
350 }
351
352 bool canUseFor(const RenderBlockFlow& flow)
353 {
354     return canUseForWithReason(flow, IncludeReasons::First) == NoReason;
355 }
356
357 static float computeLineLeft(ETextAlign textAlign, float availableWidth, float committedWidth, float logicalLeftOffset)
358 {
359     float remainingWidth = availableWidth - committedWidth;
360     float left = logicalLeftOffset;
361     switch (textAlign) {
362     case LEFT:
363     case WEBKIT_LEFT:
364     case TASTART:
365         return left;
366     case RIGHT:
367     case WEBKIT_RIGHT:
368     case TAEND:
369         return left + std::max<float>(remainingWidth, 0);
370     case CENTER:
371     case WEBKIT_CENTER:
372         return left + std::max<float>(remainingWidth / 2, 0);
373     case JUSTIFY:
374         ASSERT_NOT_REACHED();
375         break;
376     }
377     ASSERT_NOT_REACHED();
378     return 0;
379 }
380
381 static void revertAllRunsOnCurrentLine(Layout::RunVector& runs)
382 {
383     while (!runs.isEmpty() && !runs.last().isEndOfLine)
384         runs.removeLast();
385 }
386
387 static void revertRuns(Layout::RunVector& runs, unsigned positionToRevertTo, float width)
388 {
389     while (runs.size()) {
390         auto& lastRun = runs.last();
391         if (lastRun.end <= positionToRevertTo)
392             break;
393         if (lastRun.start >= positionToRevertTo) {
394             // Revert this run completely.
395             width -= (lastRun.logicalRight - lastRun.logicalLeft);
396             runs.removeLast();
397         } else {
398             lastRun.logicalRight -= width;
399             width = 0;
400             lastRun.end = positionToRevertTo;
401             // Partial removal.
402             break;
403         }
404     }
405 }
406
407 class LineState {
408 public:
409     void setAvailableWidth(float width) { m_availableWidth = width; }
410     void setCollapedWhitespaceWidth(float width) { m_collapsedWhitespaceWidth = width; }
411     void setLogicalLeftOffset(float offset) { m_logicalLeftOffset = offset; }
412     void setOverflowedFragment(const TextFragmentIterator::TextFragment& fragment) { m_overflowedFragment = fragment; }
413     void setNeedsAllFragments()
414     {
415         ASSERT(!m_fragments);
416         m_fragments.emplace();
417     }
418     void setHyphenationDisabled() { m_hyphenationDisabled = true; }
419     bool isHyphenationDisabled() const { return m_hyphenationDisabled; }
420
421     float availableWidth() const { return m_availableWidth; }
422     float logicalLeftOffset() const { return m_logicalLeftOffset; }
423     const TextFragmentIterator::TextFragment& overflowedFragment() const { return m_overflowedFragment; }
424     bool hasTrailingWhitespace() const { return m_lastFragment.type() == TextFragmentIterator::TextFragment::Whitespace; }
425     TextFragmentIterator::TextFragment lastFragment() const { return m_lastFragment; }
426     bool isWhitespaceOnly() const { return m_trailingWhitespaceWidth && m_runsWidth == m_trailingWhitespaceWidth; }
427     bool fits(float extra) const { return m_availableWidth >= m_runsWidth + extra; }
428     bool firstCharacterFits() const { return m_firstCharacterFits; }
429     float width() const { return m_runsWidth; }
430     std::pair<unsigned, bool> expansionOpportunityCount(unsigned from, unsigned to) const
431     {
432         ASSERT(m_fragments);
433         // linebreak runs are special.
434         if (from == to)
435             return std::make_pair(0, false);
436         unsigned expansionOpportunityCount = 0;
437         auto previousFragmentType = TextFragmentIterator::TextFragment::ContentEnd;
438         for (const auto& fragment : *m_fragments) {
439             if (fragment.end() <= from)
440                 continue;
441             auto currentFragmentType = fragment.type();
442             auto expansionOpportunity = this->expansionOpportunity(currentFragmentType, previousFragmentType);
443             if (expansionOpportunity)
444                 ++expansionOpportunityCount;
445             previousFragmentType = currentFragmentType;
446             if (fragment.end() >= to)
447                 return std::make_pair(expansionOpportunityCount, expansionOpportunity);
448         }
449         ASSERT_NOT_REACHED();
450         return std::make_pair(expansionOpportunityCount, false);
451     }
452
453     bool isEmpty() const
454     {
455         if (!m_lastFragment.isValid())
456             return true;
457         if (!m_lastCompleteFragment.isEmpty())
458             return false;
459         return m_lastFragment.overlapsToNextRenderer();
460     }
461
462     static inline unsigned endPositionForCollapsedFragment(const TextFragmentIterator::TextFragment& fragment)
463     {
464         return fragment.isCollapsed() ? fragment.start() + 1 : fragment.end();
465     }
466
467     void appendFragmentAndCreateRunIfNeeded(const TextFragmentIterator::TextFragment& fragment, Layout::RunVector& runs)
468     {
469         // Adjust end position while collapsing.
470         unsigned endPosition = endPositionForCollapsedFragment(fragment);
471         // New line needs new run.
472         if (!m_runsWidth) {
473             ASSERT(!m_uncompletedWidth);
474             runs.append(Run(fragment.start(), endPosition, m_runsWidth, m_runsWidth + fragment.width(), false, fragment.hasHyphen()));
475         } else {
476             // Advance last completed fragment when the previous fragment is all set (including multiple parts across renderers)
477             if ((m_lastFragment.type() != fragment.type()) || !m_lastFragment.overlapsToNextRenderer()) {
478                 m_lastCompleteFragment = m_lastFragment;
479                 m_uncompletedWidth = fragment.width();
480             } else
481                 m_uncompletedWidth += fragment.width();
482             // Collapse neighbouring whitespace, if they are across multiple renderers and are not collapsed yet.
483             if (m_lastFragment.isCollapsible() && fragment.isCollapsible()) {
484                 ASSERT(m_lastFragment.isLastInRenderer());
485                 if (!m_lastFragment.isCollapsed()) {
486                     // Line width needs to be adjusted so that now it takes collapsing into consideration.
487                     m_runsWidth -= (m_lastFragment.width() - m_collapsedWhitespaceWidth);
488                 }
489                 // This fragment is collapsed completely. No run is needed.
490                 return;
491             }
492             if (m_lastFragment.isLastInRenderer() || m_lastFragment.isCollapsed())
493                 runs.append(Run(fragment.start(), endPosition, m_runsWidth, m_runsWidth + fragment.width(), false, fragment.hasHyphen()));
494             else {
495                 Run& lastRun = runs.last();
496                 lastRun.end = endPosition;
497                 lastRun.logicalRight += fragment.width();
498                 ASSERT(!lastRun.hasHyphen);
499                 lastRun.hasHyphen = fragment.hasHyphen();
500             }
501         }
502         m_runsWidth += fragment.width();
503         m_lastFragment = fragment;
504         if (m_fragments)
505             (*m_fragments).append(fragment);
506
507         if (fragment.type() == TextFragmentIterator::TextFragment::Whitespace)
508             m_trailingWhitespaceWidth += fragment.width();
509         else {
510             m_trailingWhitespaceWidth = 0;
511             m_lastNonWhitespaceFragment = fragment;
512         }
513
514         if (!m_firstCharacterFits)
515             m_firstCharacterFits = fragment.start() + 1 > endPosition || m_runsWidth <= m_availableWidth;
516     }
517
518     TextFragmentIterator::TextFragment revertToLastCompleteFragment(Layout::RunVector& runs)
519     {
520         if (!m_uncompletedWidth) {
521             ASSERT(m_lastFragment == m_lastCompleteFragment);
522             return m_lastFragment;
523         }
524         ASSERT(m_lastFragment.isValid());
525         m_runsWidth -= m_uncompletedWidth;
526         revertRuns(runs, endPositionForCollapsedFragment(m_lastCompleteFragment), m_uncompletedWidth);
527         m_uncompletedWidth = 0;
528         ASSERT(m_lastCompleteFragment.isValid());
529         return m_lastCompleteFragment;
530     }
531
532     void removeTrailingWhitespace(Layout::RunVector& runs)
533     {
534         if (m_lastFragment.type() != TextFragmentIterator::TextFragment::Whitespace)
535             return;
536         if (m_lastNonWhitespaceFragment) {
537             auto needsReverting = m_lastNonWhitespaceFragment->end() != m_lastFragment.end();
538             // Trailing whitespace fragment might actually have zero length.
539             ASSERT(needsReverting || !m_trailingWhitespaceWidth);
540             if (needsReverting) {
541                 revertRuns(runs, m_lastNonWhitespaceFragment->end(), m_trailingWhitespaceWidth);
542                 m_runsWidth -= m_trailingWhitespaceWidth;
543             }
544             m_trailingWhitespaceWidth = 0;
545             m_lastFragment = *m_lastNonWhitespaceFragment;
546             return;
547         }
548         // This line is all whitespace.
549         revertAllRunsOnCurrentLine(runs);
550         m_runsWidth = 0;
551         m_trailingWhitespaceWidth = 0;
552         // FIXME: Make m_lastFragment optional.
553         m_lastFragment = TextFragmentIterator::TextFragment();
554     }
555
556 private:
557     bool expansionOpportunity(TextFragmentIterator::TextFragment::Type currentFragmentType, TextFragmentIterator::TextFragment::Type previousFragmentType) const
558     {
559         return (currentFragmentType == TextFragmentIterator::TextFragment::Whitespace
560             || (currentFragmentType == TextFragmentIterator::TextFragment::NonWhitespace && previousFragmentType == TextFragmentIterator::TextFragment::NonWhitespace));
561     }
562
563     float m_availableWidth { 0 };
564     float m_logicalLeftOffset { 0 };
565     float m_runsWidth { 0 };
566     TextFragmentIterator::TextFragment m_overflowedFragment;
567     TextFragmentIterator::TextFragment m_lastFragment;
568     std::optional<TextFragmentIterator::TextFragment> m_lastNonWhitespaceFragment;
569     TextFragmentIterator::TextFragment m_lastCompleteFragment;
570     float m_uncompletedWidth { 0 };
571     float m_trailingWhitespaceWidth { 0 }; // Use this to remove trailing whitespace without re-mesuring the text.
572     float m_collapsedWhitespaceWidth { 0 };
573     // Having one character on the line does not necessarily mean it actually fits.
574     // First character of the first fragment might be forced on to the current line even if it does not fit.
575     bool m_firstCharacterFits { false };
576     bool m_hyphenationDisabled { false };
577     std::optional<Vector<TextFragmentIterator::TextFragment, 30>> m_fragments;
578 };
579
580 static bool preWrap(const TextFragmentIterator::Style& style)
581 {
582     return style.wrapLines && !style.collapseWhitespace;
583 }
584     
585 static void removeTrailingWhitespace(LineState& lineState, Layout::RunVector& runs, const TextFragmentIterator& textFragmentIterator)
586 {
587     if (!lineState.hasTrailingWhitespace())
588         return;
589     // Remove collapsed whitespace, or non-collapsed pre-wrap whitespace, unless it's the only content on the line -so removing the whitesapce
590     // would produce an empty line.
591     const auto& style = textFragmentIterator.style();
592     bool collapseWhitespace = style.collapseWhitespace | preWrap(style);
593     if (!collapseWhitespace)
594         return;
595     if (preWrap(style) && lineState.isWhitespaceOnly())
596         return;
597     lineState.removeTrailingWhitespace(runs);
598 }
599
600 static void updateLineConstrains(const RenderBlockFlow& flow, LineState& line, const LineState& previousLine, unsigned& numberOfPrecedingLinesWithHyphen, const TextFragmentIterator::Style& style, bool isFirstLine)
601 {
602     bool shouldApplyTextIndent = !flow.isAnonymous() || flow.parent()->firstChild() == &flow;
603     LayoutUnit height = flow.logicalHeight();
604     LayoutUnit logicalHeight = flow.minLineHeightForReplacedRenderer(false, 0);
605     line.setLogicalLeftOffset(flow.logicalLeftOffsetForLine(height, DoNotIndentText, logicalHeight) + (shouldApplyTextIndent && isFirstLine ? flow.textIndentOffset() : LayoutUnit(0)));
606     float logicalRightOffset = flow.logicalRightOffsetForLine(height, DoNotIndentText, logicalHeight);
607     line.setAvailableWidth(std::max<float>(0, logicalRightOffset - line.logicalLeftOffset()));
608     if (style.textAlign == JUSTIFY)
609         line.setNeedsAllFragments();
610     numberOfPrecedingLinesWithHyphen = (previousLine.isEmpty() || !previousLine.lastFragment().hasHyphen()) ? 0 : numberOfPrecedingLinesWithHyphen + 1;
611     if (style.hyphenLimitLines && numberOfPrecedingLinesWithHyphen >= *style.hyphenLimitLines)
612         line.setHyphenationDisabled();
613     line.setCollapedWhitespaceWidth(style.font.spaceWidth() + style.wordSpacing);
614 }
615
616 struct SplitFragmentData {
617     unsigned position;
618     float width;
619 };
620 static std::optional<unsigned> hyphenPositionForFragment(SplitFragmentData splitData, const TextFragmentIterator::TextFragment& fragmentToSplit,
621     const LineState& line, const TextFragmentIterator& textFragmentIterator, float availableWidth)
622 {
623     auto& style = textFragmentIterator.style();
624     if (!style.shouldHyphenate || line.isHyphenationDisabled())
625         return std::nullopt;
626
627     // FIXME: This is a workaround for webkit.org/b/169613. See maxPrefixWidth computation in tryHyphenating().
628     // It does not work properly with non-collapsed leading tabs when font is enlarged.
629     auto adjustedAvailableWidth = availableWidth - style.hyphenStringWidth;
630     if (!line.isEmpty())
631         adjustedAvailableWidth += style.font.spaceWidth();
632     if (!enoughWidthForHyphenation(adjustedAvailableWidth, style.font.pixelSize()))
633         return std::nullopt;
634
635     // We might be able to fit the hyphen at the split position.
636     auto splitPositionWithHyphen = splitData.position;
637     // Find a splitting position where hyphen surely fits.
638     unsigned start = fragmentToSplit.start();
639     auto leftSideWidth = splitData.width;
640     while (leftSideWidth + style.hyphenStringWidth > availableWidth) {
641         if (--splitPositionWithHyphen <= start)
642             return std::nullopt; // No space for hyphen.
643         leftSideWidth -= textFragmentIterator.textWidth(splitPositionWithHyphen, splitPositionWithHyphen + 1, 0);
644     }
645     ASSERT(splitPositionWithHyphen > start);
646     return textFragmentIterator.lastHyphenPosition(fragmentToSplit, splitPositionWithHyphen + 1);
647 }
648
649 static SplitFragmentData split(const TextFragmentIterator::TextFragment& fragment, float availableWidth,
650     const TextFragmentIterator& textFragmentIterator)
651 {
652     ASSERT(availableWidth >= 0);
653     auto left = fragment.start();
654     // Pathological case of (extremely)long string and narrow lines.
655     // Adjust the range so that we can pick a reasonable midpoint.
656     auto averageCharacterWidth = fragment.width() / fragment.length();
657     auto right = std::min<unsigned>(left + (2 * availableWidth / averageCharacterWidth), fragment.end() - 1);
658     // Preserve the left width for the final split position so that we don't need to remeasure the left side again.
659     float leftSideWidth = 0;
660     while (left < right) {
661         auto middle = (left + right) / 2;
662         auto width = textFragmentIterator.textWidth(fragment.start(), middle + 1, 0);
663         if (width < availableWidth) {
664             left = middle + 1;
665             leftSideWidth = width;
666         } else if (width > availableWidth)
667             right = middle;
668         else {
669             right = middle + 1;
670             leftSideWidth = width;
671             break;
672         }
673     }
674     return { right, leftSideWidth };
675 }
676
677 static TextFragmentIterator::TextFragment splitFragmentToFitLine(TextFragmentIterator::TextFragment& fragmentToSplit,
678     const LineState& line, const TextFragmentIterator& textFragmentIterator)
679 {
680     auto availableWidth = line.availableWidth() - line.width();
681     auto splitFragmentData = split(fragmentToSplit, availableWidth, textFragmentIterator);
682     std::optional<unsigned> hyphenPosition = std::nullopt;
683     // Does first character fit this line?
684     if (splitFragmentData.position == fragmentToSplit.start()) {
685         // Keep at least one character on empty lines.
686         if (line.isEmpty())
687             splitFragmentData.width = textFragmentIterator.textWidth(fragmentToSplit.start(), ++splitFragmentData.position, 0);
688     } else {
689         hyphenPosition = hyphenPositionForFragment(splitFragmentData, fragmentToSplit, line, textFragmentIterator, availableWidth);
690         if (hyphenPosition) {
691             splitFragmentData.position = *hyphenPosition;
692             splitFragmentData.width = textFragmentIterator.textWidth(fragmentToSplit.start(), splitFragmentData.position, 0);
693         }
694     }
695     // If the right side surely does not fit the (next)line, we don't need the width to be kerning/ligature adjusted.
696     // Part of it gets re-measured as the left side during next split.
697     // This saves measuring long chunk of text repeatedly (see pathological case at ::split).
698     auto rightSideWidth = fragmentToSplit.width() - splitFragmentData.width;
699     if (rightSideWidth < 2 * availableWidth)
700         rightSideWidth = textFragmentIterator.textWidth(splitFragmentData.position, fragmentToSplit.end(), 0);
701     return hyphenPosition ? fragmentToSplit.splitWithHyphen(splitFragmentData.position, textFragmentIterator.style().hyphenStringWidth,
702         splitFragmentData.width, rightSideWidth) : fragmentToSplit.split(splitFragmentData.position, splitFragmentData.width, rightSideWidth);
703 }
704
705 enum PreWrapLineBreakRule { Preserve, Ignore };
706
707 static TextFragmentIterator::TextFragment consumeLineBreakIfNeeded(const TextFragmentIterator::TextFragment& fragment, TextFragmentIterator& textFragmentIterator, LineState& line, Layout::RunVector& runs,
708     PreWrapLineBreakRule preWrapLineBreakRule = PreWrapLineBreakRule::Preserve)
709 {
710     if (!fragment.isLineBreak())
711         return fragment;
712
713     bool isHardLinebreak = fragment.type() == TextFragmentIterator::TextFragment::HardLineBreak;
714     // <br> always produces a run. (required by testing output)
715     if (isHardLinebreak)
716         line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
717
718     auto& style = textFragmentIterator.style();
719     if (style.preserveNewline && preWrapLineBreakRule == PreWrapLineBreakRule::Preserve) {
720         if (!isHardLinebreak)
721             return fragment;
722     }
723     return textFragmentIterator.nextTextFragment();
724 }
725
726 static TextFragmentIterator::TextFragment skipWhitespaceIfNeeded(const TextFragmentIterator::TextFragment& fragment, TextFragmentIterator& textFragmentIterator)
727 {
728     if (!textFragmentIterator.style().collapseWhitespace)
729         return fragment;
730
731     TextFragmentIterator::TextFragment firstNonWhitespaceFragment = fragment;
732     while (firstNonWhitespaceFragment.type() == TextFragmentIterator::TextFragment::Whitespace)
733         firstNonWhitespaceFragment = textFragmentIterator.nextTextFragment();
734     return firstNonWhitespaceFragment;
735 }
736
737 static TextFragmentIterator::TextFragment firstFragment(TextFragmentIterator& textFragmentIterator, LineState& currentLine, const LineState& previousLine, Layout::RunVector& runs)
738 {
739     // Handle overflow fragment from previous line.
740     auto overflowedFragment = previousLine.overflowedFragment();
741     if (overflowedFragment.isEmpty())
742         return skipWhitespaceIfNeeded(textFragmentIterator.nextTextFragment(), textFragmentIterator);
743
744     if (overflowedFragment.type() != TextFragmentIterator::TextFragment::Whitespace)
745         return overflowedFragment;
746
747     // Leading whitespace handling.
748     auto& style = textFragmentIterator.style();
749     // Special overflow pre-wrap whitespace handling: skip the overflowed whitespace (even when style says not-collapsible)
750     // if we manage to fit at least one character on the previous line.
751     auto preWrapIsOn = preWrap(style);
752     if ((style.collapseWhitespace || preWrapIsOn) && previousLine.firstCharacterFits()) {
753         // If skipping the whitespace puts us on a newline, skip the newline too as we already wrapped the line.
754         auto firstFragmentCandidate = consumeLineBreakIfNeeded(textFragmentIterator.nextTextFragment(), textFragmentIterator, currentLine, runs,
755             preWrapIsOn ? PreWrapLineBreakRule::Ignore : PreWrapLineBreakRule::Preserve);
756         return skipWhitespaceIfNeeded(firstFragmentCandidate, textFragmentIterator);
757     }
758     return skipWhitespaceIfNeeded(overflowedFragment, textFragmentIterator);
759 }
760
761 static void forceFragmentToLine(LineState& line, TextFragmentIterator& textFragmentIterator, Layout::RunVector& runs, const TextFragmentIterator::TextFragment& fragment)
762 {
763     line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
764     // Check if there are more fragments to add to the current line.
765     auto nextFragment = textFragmentIterator.nextTextFragment();
766     if (fragment.overlapsToNextRenderer()) {
767         while (true) {
768             if (nextFragment.type() != fragment.type())
769                 break;
770             line.appendFragmentAndCreateRunIfNeeded(nextFragment, runs);
771             // Does it overlap to the next segment?
772             if (!nextFragment.overlapsToNextRenderer())
773                 return;
774             nextFragment = textFragmentIterator.nextTextFragment();
775         }
776     }
777     // When the forced fragment is followed by either whitespace and/or line break, consume them too, otherwise we end up with an extra whitespace and/or line break.
778     nextFragment = skipWhitespaceIfNeeded(nextFragment, textFragmentIterator);
779     nextFragment = consumeLineBreakIfNeeded(nextFragment, textFragmentIterator, line, runs);
780     line.setOverflowedFragment(nextFragment);
781 }
782
783 static bool createLineRuns(LineState& line, const LineState& previousLine, Layout::RunVector& runs, TextFragmentIterator& textFragmentIterator)
784 {
785     const auto& style = textFragmentIterator.style();
786     bool lineCanBeWrapped = style.wrapLines || style.breakFirstWordOnOverflow || style.breakAnyWordOnOverflow;
787     auto fragment = firstFragment(textFragmentIterator, line, previousLine, runs);
788     while (fragment.type() != TextFragmentIterator::TextFragment::ContentEnd) {
789         // Hard and soft linebreaks.
790         if (fragment.isLineBreak()) {
791             // Add the new line fragment only if there's nothing on the line. (otherwise the extra new line character would show up at the end of the content.)
792             if (line.isEmpty() || fragment.type() == TextFragmentIterator::TextFragment::HardLineBreak) {
793                 if (style.textAlign == RIGHT || style.textAlign == WEBKIT_RIGHT)
794                     line.removeTrailingWhitespace(runs);
795                 line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
796             }
797             break;
798         }
799         if (lineCanBeWrapped && !line.fits(fragment.width())) {
800             // Overflow wrapping behaviour:
801             // 1. Whitesapce collapse on: whitespace is skipped. Jump to next line.
802             // 2. Whitespace collapse off: whitespace is wrapped.
803             // 3. First, non-whitespace fragment is either wrapped or kept on the line. (depends on overflow-wrap)
804             // 5. Non-whitespace fragment when there's already another fragment on the line either gets wrapped (word-break: break-all)
805             // or gets pushed to the next line.
806             bool emptyLine = line.isEmpty();
807             // Whitespace fragment.
808             if (fragment.type() == TextFragmentIterator::TextFragment::Whitespace) {
809                 if (style.collapseWhitespace) {
810                     // Push collapased whitespace to the next line.
811                     line.setOverflowedFragment(fragment);
812                     break;
813                 }
814                 // Split the whitespace; left part stays on this line, right is pushed to next line.
815                 line.setOverflowedFragment(splitFragmentToFitLine(fragment, line, textFragmentIterator));
816                 line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
817                 break;
818             }
819             // Non-whitespace fragment. (!style.wrapLines: bug138102(preserve existing behavior)
820             if (((emptyLine && style.breakFirstWordOnOverflow) || style.breakAnyWordOnOverflow) || !style.wrapLines) {
821                 // Split the fragment; (modified)fragment stays on this line, overflowedFragment is pushed to next line.
822                 line.setOverflowedFragment(splitFragmentToFitLine(fragment, line, textFragmentIterator));
823                 line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
824                 break;
825             }
826             ASSERT(fragment.type() == TextFragmentIterator::TextFragment::NonWhitespace);
827             // Find out if this non-whitespace fragment has a hyphen where we can break.
828             if (style.shouldHyphenate) {
829                 auto fragmentToSplit = fragment;
830                 // Split and check if we actually ended up with a hyphen.
831                 auto overflowFragment = splitFragmentToFitLine(fragmentToSplit, line, textFragmentIterator);
832                 if (fragmentToSplit.hasHyphen()) {
833                     line.setOverflowedFragment(overflowFragment);
834                     line.appendFragmentAndCreateRunIfNeeded(fragmentToSplit, runs);
835                     break;
836                 }
837                 // No hyphen, no split.
838             }
839             // Non-breakable non-whitespace first fragment. Add it to the current line. -it overflows though.
840             if (emptyLine) {
841                 forceFragmentToLine(line, textFragmentIterator, runs, fragment);
842                 break;
843             }
844             // Non-breakable non-whitespace fragment when there's already content on the line. Push it to the next line.
845             ASSERT(line.lastFragment().isValid());
846             if (line.lastFragment().overlapsToNextRenderer()) {
847                 // Check if this fragment is a continuation of a previous segment. In such cases, we need to remove them all.
848                 textFragmentIterator.revertToEndOfFragment(line.revertToLastCompleteFragment(runs));
849                 break;
850             }
851             line.setOverflowedFragment(fragment);
852             break;
853         }
854         line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
855         // Find the next text fragment.
856         fragment = textFragmentIterator.nextTextFragment(line.width());
857     }
858     return (fragment.type() == TextFragmentIterator::TextFragment::ContentEnd && line.overflowedFragment().isEmpty()) || line.overflowedFragment().type() == TextFragmentIterator::TextFragment::ContentEnd;
859 }
860
861 static ExpansionBehavior expansionBehavior(bool isAfterExpansion, bool lastRunOnLine)
862 {
863     ExpansionBehavior expansionBehavior;
864     expansionBehavior = isAfterExpansion ? ForbidLeadingExpansion : AllowLeadingExpansion;
865     expansionBehavior |= lastRunOnLine ? ForbidTrailingExpansion : AllowTrailingExpansion;
866     return expansionBehavior;
867 }
868
869 static void justifyRuns(const LineState& line, Layout::RunVector& runs, unsigned firstRunIndex)
870 {
871     ASSERT(runs.size());
872     auto widthToDistribute = line.availableWidth() - line.width();
873     if (widthToDistribute <= 0)
874         return;
875
876     auto lastRunIndex = runs.size() - 1;
877     ASSERT(firstRunIndex <= lastRunIndex);
878     Vector<std::pair<unsigned, ExpansionBehavior>> expansionOpportunityList;
879     unsigned expansionOpportunityCountOnThisLine = 0;
880     auto isAfterExpansion = true;
881     for (auto i = firstRunIndex; i <= lastRunIndex; ++i) {
882         const auto& run = runs.at(i);
883         unsigned opportunityCountInRun = 0;
884         std::tie(opportunityCountInRun, isAfterExpansion) = line.expansionOpportunityCount(run.start, run.end);
885         expansionOpportunityList.append(std::make_pair(opportunityCountInRun, expansionBehavior(isAfterExpansion, i == lastRunIndex)));
886         expansionOpportunityCountOnThisLine += opportunityCountInRun;
887     }
888     if (!expansionOpportunityCountOnThisLine)
889         return;
890
891     ASSERT(expansionOpportunityList.size() == lastRunIndex - firstRunIndex + 1);
892     auto expansion = widthToDistribute / expansionOpportunityCountOnThisLine;
893     float accumulatedExpansion = 0;
894     for (auto i = firstRunIndex; i <= lastRunIndex; ++i) {
895         auto& run = runs.at(i);
896         unsigned opportunityCountInRun;
897         std::tie(opportunityCountInRun, run.expansionBehavior) = expansionOpportunityList.at(i - firstRunIndex);
898         run.expansion = opportunityCountInRun * expansion;
899         run.logicalLeft += accumulatedExpansion;
900         run.logicalRight += (accumulatedExpansion + run.expansion);
901         accumulatedExpansion += run.expansion;
902     }
903 }
904
905 static ETextAlign textAlignForLine(const TextFragmentIterator::Style& style, bool lastLine)
906 {
907     // Fallback to LEFT (START) alignment for non-collapsable content and for the last line before a forced break or the end of the block.
908     auto textAlign = style.textAlign;
909     if (textAlign == JUSTIFY && (!style.collapseWhitespace || lastLine))
910         textAlign = LEFT;
911     return textAlign;
912 }
913
914 static void closeLineEndingAndAdjustRuns(LineState& line, Layout::RunVector& runs, std::optional<unsigned> lastRunIndexOfPreviousLine, unsigned& lineCount,
915     const TextFragmentIterator& textFragmentIterator, bool lastLineInFlow)
916 {
917     if (!runs.size() || (lastRunIndexOfPreviousLine && runs.size() - 1 == lastRunIndexOfPreviousLine.value()))
918         return;
919     removeTrailingWhitespace(line, runs, textFragmentIterator);
920     if (!runs.size())
921         return;
922     // Adjust runs' position by taking line's alignment into account.
923     const auto& style = textFragmentIterator.style();
924     auto firstRunIndex = lastRunIndexOfPreviousLine ? lastRunIndexOfPreviousLine.value() + 1 : 0;
925     auto lineLogicalLeft = line.logicalLeftOffset();
926     auto textAlign = textAlignForLine(style, lastLineInFlow || (line.lastFragment().isValid() && line.lastFragment().type() == TextFragmentIterator::TextFragment::HardLineBreak));
927     if (textAlign == JUSTIFY)
928         justifyRuns(line, runs, firstRunIndex);
929     else
930         lineLogicalLeft = computeLineLeft(textAlign, line.availableWidth(), line.width(), line.logicalLeftOffset());
931     for (auto i = firstRunIndex; i < runs.size(); ++i) {
932         runs[i].logicalLeft += lineLogicalLeft;
933         runs[i].logicalRight += lineLogicalLeft;
934     }
935     runs.last().isEndOfLine = true;
936     ++lineCount;
937 }
938
939 static void createTextRuns(Layout::RunVector& runs, RenderBlockFlow& flow, unsigned& lineCount)
940 {
941     LayoutUnit borderAndPaddingBefore = flow.borderAndPaddingBefore();
942     LayoutUnit lineHeight = lineHeightFromFlow(flow);
943     LineState line;
944     unsigned numberOfPrecedingLinesWithHyphen = 0;
945     bool isEndOfContent = false;
946     TextFragmentIterator textFragmentIterator = TextFragmentIterator(flow);
947     std::optional<unsigned> lastRunIndexOfPreviousLine;
948     do {
949         flow.setLogicalHeight(lineHeight * lineCount + borderAndPaddingBefore);
950         LineState previousLine = line;
951         line = LineState();
952         updateLineConstrains(flow, line, previousLine, numberOfPrecedingLinesWithHyphen, textFragmentIterator.style(), !lineCount);
953         isEndOfContent = createLineRuns(line, previousLine, runs, textFragmentIterator);
954         closeLineEndingAndAdjustRuns(line, runs, lastRunIndexOfPreviousLine, lineCount, textFragmentIterator, isEndOfContent);
955         if (runs.size())
956             lastRunIndexOfPreviousLine = runs.size() - 1;
957     } while (!isEndOfContent);
958 }
959
960 std::unique_ptr<Layout> create(RenderBlockFlow& flow)
961 {
962     unsigned lineCount = 0;
963     Layout::RunVector runs;
964     createTextRuns(runs, flow, lineCount);
965     return Layout::create(runs, lineCount);
966 }
967
968 std::unique_ptr<Layout> Layout::create(const RunVector& runVector, unsigned lineCount)
969 {
970     void* slot = WTF::fastMalloc(sizeof(Layout) + sizeof(Run) * runVector.size());
971     return std::unique_ptr<Layout>(new (NotNull, slot) Layout(runVector, lineCount));
972 }
973
974 Layout::Layout(const RunVector& runVector, unsigned lineCount)
975     : m_lineCount(lineCount)
976     , m_runCount(runVector.size())
977 {
978     memcpy(m_runs, runVector.data(), m_runCount * sizeof(Run));
979 }
980
981 Layout::~Layout()
982 {
983     simpleLineLayoutWillBeDeleted(*this);
984 }
985
986 }
987 }