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