Simple line layout: Skip 16bit specific checks on 8bit content.
[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 "RenderLineBreak.h"
44 #include "RenderStyle.h"
45 #include "RenderText.h"
46 #include "RenderTextControl.h"
47 #include "RenderView.h"
48 #include "Settings.h"
49 #include "SimpleLineLayoutFlowContents.h"
50 #include "SimpleLineLayoutFunctions.h"
51 #include "SimpleLineLayoutTextFragmentIterator.h"
52 #include "Text.h"
53 #include "TextPaintStyle.h"
54 #include "TextStream.h"
55
56 namespace WebCore {
57 namespace SimpleLineLayout {
58
59 #ifndef NDEBUG
60 void printSimpleLineLayoutCoverage();
61 void printSimpleLineLayoutBlockList();
62 void toggleSimpleLineLayout();
63 #endif
64
65 enum AvoidanceReason_ : uint64_t {
66     FlowIsInsideRegion                    = 1LLU  << 0,
67     FlowHasHorizonalWritingMode           = 1LLU  << 1,
68     FlowHasOutline                        = 1LLU  << 2,
69     FlowIsRuby                            = 1LLU  << 3,
70     FlowIsPaginated                       = 1LLU  << 4,
71     FlowHasTextOverflow                   = 1LLU  << 5,
72     FlowIsDepricatedFlexBox               = 1LLU  << 6,
73     FlowParentIsPlaceholderElement        = 1LLU  << 7,
74     FlowParentIsTextAreaWithWrapping      = 1LLU  << 8,
75     FlowHasNonSupportedChild              = 1LLU  << 9,
76     FlowHasUnsupportedFloat               = 1LLU  << 10,
77     FlowHasUnsupportedUnderlineDecoration = 1LLU  << 11,
78     FlowHasJustifiedNonLatinText          = 1LLU  << 12,
79     FlowHasOverflowVisible                = 1LLU  << 13,
80     FlowHasWebKitNBSPMode                 = 1LLU  << 14,
81     FlowIsNotLTR                          = 1LLU  << 15,
82     FlowHasLineBoxContainProperty         = 1LLU  << 16,
83     FlowIsNotTopToBottom                  = 1LLU  << 17,
84     FlowHasLineBreak                      = 1LLU  << 18,
85     FlowHasNonNormalUnicodeBiDi           = 1LLU  << 19,
86     FlowHasRTLOrdering                    = 1LLU  << 20,
87     FlowHasLineAlignEdges                 = 1LLU  << 21,
88     FlowHasLineSnap                       = 1LLU  << 22,
89     FlowHasTextEmphasisFillOrMark         = 1LLU  << 23,
90     FlowHasTextShadow                     = 1LLU  << 24,
91     FlowHasPseudoFirstLine                = 1LLU  << 25,
92     FlowHasPseudoFirstLetter              = 1LLU  << 26,
93     FlowHasTextCombine                    = 1LLU  << 27,
94     FlowHasTextFillBox                    = 1LLU  << 28,
95     FlowHasBorderFitLines                 = 1LLU  << 29,
96     FlowHasNonAutoLineBreak               = 1LLU  << 30,
97     FlowHasNonAutoTrailingWord            = 1LLU  << 31,
98     FlowHasSVGFont                        = 1LLU  << 32,
99     FlowTextIsEmpty                       = 1LLU  << 33,
100     FlowTextHasSoftHyphen                 = 1LLU  << 34,
101     FlowTextHasDirectionCharacter         = 1LLU  << 35,
102     FlowIsMissingPrimaryFont              = 1LLU  << 36,
103     FlowPrimaryFontIsInsufficient         = 1LLU  << 37,
104     FlowTextIsCombineText                 = 1LLU  << 38,
105     FlowTextIsRenderCounter               = 1LLU  << 39,
106     FlowTextIsRenderQuote                 = 1LLU  << 40,
107     FlowTextIsTextFragment                = 1LLU  << 41,
108     FlowTextIsSVGInlineText               = 1LLU  << 42,
109     FlowHasComplexFontCodePath            = 1LLU  << 43,
110     FeatureIsDisabled                     = 1LLU  << 44,
111     FlowHasNoParent                       = 1LLU  << 45,
112     FlowHasNoChild                        = 1LLU  << 46,
113     FlowChildIsSelected                   = 1LLU  << 47,
114     FlowHasHangingPunctuation             = 1LLU  << 48,
115     FlowFontHasOverflowGlyph              = 1LLU  << 49,
116     EndOfReasons                          = 1LLU  << 50
117 };
118 const unsigned NoReason = 0;
119
120 typedef uint64_t AvoidanceReason;
121 typedef uint64_t AvoidanceReasonFlags;
122
123 enum class IncludeReasons { First , All };
124
125 #ifndef NDEBUG
126 #define SET_REASON_AND_RETURN_IF_NEEDED(reason, reasons, includeReasons) { \
127         reasons |= reason; \
128         if (includeReasons == IncludeReasons::First) \
129             return reasons; \
130     }
131 #else
132 #define SET_REASON_AND_RETURN_IF_NEEDED(reason, reasons, includeReasons) { \
133         ASSERT_UNUSED(includeReasons, includeReasons == IncludeReasons::First); \
134         reasons |= reason; \
135         return reasons; \
136     }
137 #endif
138
139
140 template <typename CharacterType> AvoidanceReasonFlags canUseForCharacter(CharacterType, bool textIsJustified, IncludeReasons);
141
142 template<> AvoidanceReasonFlags canUseForCharacter(UChar character, bool textIsJustified, IncludeReasons includeReasons)
143 {
144     AvoidanceReasonFlags reasons = { };
145     if (textIsJustified) {
146         // Include characters up to Latin Extended-B and some punctuation range when text is justified.
147         bool isLatinIncludingExtendedB = character <= 0x01FF;
148         bool isPunctuationRange = character >= 0x2010 && character <= 0x2027;
149         if (!(isLatinIncludingExtendedB || isPunctuationRange))
150             SET_REASON_AND_RETURN_IF_NEEDED(FlowHasJustifiedNonLatinText, reasons, includeReasons);
151     }
152
153     UCharDirection direction = u_charDirection(character);
154     if (direction == U_RIGHT_TO_LEFT || direction == U_RIGHT_TO_LEFT_ARABIC
155         || direction == U_RIGHT_TO_LEFT_EMBEDDING || direction == U_RIGHT_TO_LEFT_OVERRIDE
156         || direction == U_LEFT_TO_RIGHT_EMBEDDING || direction == U_LEFT_TO_RIGHT_OVERRIDE
157         || direction == U_POP_DIRECTIONAL_FORMAT || direction == U_BOUNDARY_NEUTRAL)
158         SET_REASON_AND_RETURN_IF_NEEDED(FlowTextHasDirectionCharacter, reasons, includeReasons);
159
160     return reasons;
161 }
162
163 template<> AvoidanceReasonFlags canUseForCharacter(LChar, bool, IncludeReasons)
164 {
165     return { };
166 }
167
168 template <typename CharacterType>
169 static AvoidanceReasonFlags canUseForText(const CharacterType* text, unsigned length, const FontCascade& fontCascade, std::optional<float> lineHeightConstraint,
170     bool textIsJustified, IncludeReasons includeReasons)
171 {
172     AvoidanceReasonFlags reasons = { };
173     auto& primaryFont = fontCascade.primaryFont();
174     for (unsigned i = 0; i < length; ++i) {
175         auto character = text[i];
176         if (FontCascade::treatAsSpace(character))
177             continue;
178
179         if (character == softHyphen)
180             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextHasSoftHyphen, reasons, includeReasons);
181
182         auto glyphData = fontCascade.glyphDataForCharacter(character, false);
183         if (!glyphData.isValid() || glyphData.font != &primaryFont)
184             SET_REASON_AND_RETURN_IF_NEEDED(FlowPrimaryFontIsInsufficient, reasons, includeReasons);
185
186         if (lineHeightConstraint && primaryFont.boundsForGlyph(glyphData.glyph).height() > *lineHeightConstraint)
187             SET_REASON_AND_RETURN_IF_NEEDED(FlowFontHasOverflowGlyph, reasons, includeReasons);
188
189         auto characterReasons = canUseForCharacter(character, textIsJustified, includeReasons);
190         if (characterReasons != NoReason)
191             SET_REASON_AND_RETURN_IF_NEEDED(characterReasons, reasons, includeReasons);
192     }
193     return reasons;
194 }
195
196 static AvoidanceReasonFlags canUseForText(StringView text, const FontCascade& fontCascade, std::optional<float> lineHeightConstraint, bool textIsJustified, IncludeReasons includeReasons)
197 {
198     if (text.is8Bit())
199         return canUseForText(text.characters8(), text.length(), fontCascade, lineHeightConstraint, textIsJustified, includeReasons);
200     return canUseForText(text.characters16(), text.length(), fontCascade, lineHeightConstraint, textIsJustified, includeReasons);
201 }
202
203 static AvoidanceReasonFlags canUseForFontAndText(const RenderBlockFlow& flow, IncludeReasons includeReasons)
204 {
205     AvoidanceReasonFlags reasons = { };
206     // We assume that all lines have metrics based purely on the primary font.
207     const auto& style = flow.style();
208     auto& fontCascade = style.fontCascade();
209     if (fontCascade.primaryFont().isLoading())
210         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsMissingPrimaryFont, reasons, includeReasons);
211     std::optional<float> lineHeightConstraint;
212     if (style.lineBoxContain() & LineBoxContainGlyphs)
213         lineHeightConstraint = lineHeightFromFlow(flow).toFloat();
214     bool flowIsJustified = style.textAlign() == JUSTIFY;
215     for (const auto& textRenderer : childrenOfType<RenderText>(flow)) {
216         // FIXME: Do not return until after checking all children.
217         if (!textRenderer.textLength())
218             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsEmpty, reasons, includeReasons);
219         if (textRenderer.isCombineText())
220             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsCombineText, reasons, includeReasons);
221         if (textRenderer.isCounter())
222             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsRenderCounter, reasons, includeReasons);
223         if (textRenderer.isQuote())
224             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsRenderQuote, reasons, includeReasons);
225         if (textRenderer.isTextFragment())
226             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsTextFragment, reasons, includeReasons);
227         if (textRenderer.isSVGInlineText())
228             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsSVGInlineText, reasons, includeReasons);
229         if (!textRenderer.canUseSimpleFontCodePath())
230             SET_REASON_AND_RETURN_IF_NEEDED(FlowHasComplexFontCodePath, reasons, includeReasons);
231
232         auto textReasons = canUseForText(textRenderer.stringView(), fontCascade, lineHeightConstraint, flowIsJustified, includeReasons);
233         if (textReasons != NoReason)
234             SET_REASON_AND_RETURN_IF_NEEDED(textReasons, reasons, includeReasons);
235     }
236     return reasons;
237 }
238
239 static AvoidanceReasonFlags canUseForStyle(const RenderStyle& style, IncludeReasons includeReasons)
240 {
241     AvoidanceReasonFlags reasons = { };
242     if (style.textOverflow())
243         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextOverflow, reasons, includeReasons);
244     if ((style.textDecorationsInEffect() & TextDecorationUnderline) && style.textUnderlinePosition() == TextUnderlinePositionUnder)
245         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasUnsupportedUnderlineDecoration, reasons, includeReasons);
246     // Non-visible overflow should be pretty easy to support.
247     if (style.overflowX() != OVISIBLE || style.overflowY() != OVISIBLE)
248         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasOverflowVisible, reasons, includeReasons);
249     if (!style.isLeftToRightDirection())
250         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsNotLTR, reasons, includeReasons);
251     if (!(style.lineBoxContain() & LineBoxContainBlock))
252         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasLineBoxContainProperty, reasons, includeReasons);
253     if (style.writingMode() != TopToBottomWritingMode)
254         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsNotTopToBottom, reasons, includeReasons);
255     if (style.lineBreak() != LineBreakAuto)
256         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasLineBreak, reasons, includeReasons);
257     if (style.unicodeBidi() != UBNormal)
258         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasNonNormalUnicodeBiDi, reasons, includeReasons);
259     if (style.rtlOrdering() != LogicalOrder)
260         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasRTLOrdering, reasons, includeReasons);
261     if (style.lineAlign() != LineAlignNone)
262         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasLineAlignEdges, reasons, includeReasons);
263     if (style.lineSnap() != LineSnapNone)
264         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasLineSnap, reasons, includeReasons);
265     if (style.textEmphasisFill() != TextEmphasisFillFilled || style.textEmphasisMark() != TextEmphasisMarkNone)
266         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextEmphasisFillOrMark, reasons, includeReasons);
267     if (style.textShadow())
268         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextShadow, reasons, includeReasons);
269     if (style.hasPseudoStyle(FIRST_LINE))
270         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasPseudoFirstLine, reasons, includeReasons);
271     if (style.hasPseudoStyle(FIRST_LETTER))
272         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasPseudoFirstLetter, reasons, includeReasons);
273     if (style.hasTextCombine())
274         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextCombine, reasons, includeReasons);
275     if (style.backgroundClip() == TextFillBox)
276         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextFillBox, reasons, includeReasons);
277     if (style.borderFit() == BorderFitLines)
278         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasBorderFitLines, reasons, includeReasons);
279     if (style.lineBreak() != LineBreakAuto)
280         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasNonAutoLineBreak, reasons, includeReasons);
281     if (style.nbspMode() != NBNORMAL)
282         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasWebKitNBSPMode, reasons, includeReasons);
283 #if ENABLE(CSS_TRAILING_WORD)
284     if (style.trailingWord() != TrailingWord::Auto)
285         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasNonAutoTrailingWord, reasons, includeReasons);
286 #endif
287     return reasons;
288 }
289
290 static AvoidanceReasonFlags canUseForWithReason(const RenderBlockFlow& flow, IncludeReasons includeReasons)
291 {
292 #ifndef NDEBUG
293     static std::once_flag onceFlag;
294     std::call_once(onceFlag, [] {
295         registerNotifyCallback("com.apple.WebKit.showSimpleLineLayoutCoverage", printSimpleLineLayoutCoverage);
296         registerNotifyCallback("com.apple.WebKit.showSimpleLineLayoutReasons", printSimpleLineLayoutBlockList);
297         registerNotifyCallback("com.apple.WebKit.toggleSimpleLineLayout", toggleSimpleLineLayout);
298     });
299 #endif
300     AvoidanceReasonFlags reasons = { };
301     if (!flow.settings().simpleLineLayoutEnabled())
302         SET_REASON_AND_RETURN_IF_NEEDED(FeatureIsDisabled, reasons, includeReasons);
303     if (!flow.parent())
304         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasNoParent, reasons, includeReasons);
305     if (!flow.firstChild())
306         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasNoChild, reasons, includeReasons);
307     if (flow.flowThreadState() != RenderObject::NotInsideFlowThread)
308         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsInsideRegion, reasons, includeReasons);
309     if (!flow.isHorizontalWritingMode())
310         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasHorizonalWritingMode, reasons, includeReasons);
311     if (flow.hasOutline())
312         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasOutline, reasons, includeReasons);
313     if (flow.isRubyText() || flow.isRubyBase())
314         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsRuby, reasons, includeReasons);
315     if (flow.style().hangingPunctuation() != NoHangingPunctuation)
316         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasHangingPunctuation, reasons, includeReasons);
317     
318     // Printing does pagination without a flow thread.
319     if (flow.document().paginated())
320         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsPaginated, reasons, includeReasons);
321     if (flow.firstLineBlock())
322         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasPseudoFirstLine, reasons, includeReasons);
323     if (flow.isAnonymousBlock() && flow.parent()->style().textOverflow())
324         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextOverflow, reasons, includeReasons);
325     if (flow.parent()->isDeprecatedFlexibleBox())
326         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsDepricatedFlexBox, reasons, includeReasons);
327     // FIXME: Placeholders do something strange.
328     if (is<RenderTextControl>(*flow.parent()) && downcast<RenderTextControl>(*flow.parent()).textFormControlElement().placeholderElement())
329         SET_REASON_AND_RETURN_IF_NEEDED(FlowParentIsPlaceholderElement, reasons, includeReasons);
330     // FIXME: Implementation of wrap=hard looks into lineboxes.
331     if (flow.parent()->isTextArea() && flow.parent()->element()->hasAttributeWithoutSynchronization(HTMLNames::wrapAttr))
332         SET_REASON_AND_RETURN_IF_NEEDED(FlowParentIsTextAreaWithWrapping, reasons, includeReasons);
333     // This currently covers <blockflow>#text</blockflow>, <blockflow>#text<br></blockflow> and mutiple (sibling) RenderText cases.
334     // The <blockflow><inline>#text</inline></blockflow> case is also popular and should be relatively easy to cover.
335     for (const auto* child = flow.firstChild(); child;) {
336         if (child->selectionState() != RenderObject::SelectionNone)
337             SET_REASON_AND_RETURN_IF_NEEDED(FlowChildIsSelected, reasons, includeReasons);
338         if (is<RenderText>(*child)) {
339             child = child->nextSibling();
340             continue;
341         }
342         if (is<RenderLineBreak>(child) && !downcast<RenderLineBreak>(*child).isWBR() && child->style().clear() == CNONE) {
343             child = child->nextSibling();
344             continue;
345         }
346         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasNonSupportedChild, reasons, includeReasons);
347         break;
348     }
349     auto styleReasons = canUseForStyle(flow.style(), includeReasons);
350     if (styleReasons != NoReason)
351         SET_REASON_AND_RETURN_IF_NEEDED(styleReasons, reasons, includeReasons);
352     // 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.
353     if (flow.containsFloats()) {
354         float minimumWidthNeeded = std::numeric_limits<float>::max();
355         for (const auto& textRenderer : childrenOfType<RenderText>(flow)) {
356             minimumWidthNeeded = std::min(minimumWidthNeeded, textRenderer.minLogicalWidth());
357
358             for (auto& floatingObject : *flow.floatingObjectSet()) {
359                 ASSERT(floatingObject);
360                 // if a float has a shape, we cannot tell if content will need to be shifted until after we lay it out,
361                 // since the amount of space is not uniform for the height of the float.
362                 if (floatingObject->renderer().shapeOutsideInfo())
363                     SET_REASON_AND_RETURN_IF_NEEDED(FlowHasUnsupportedFloat, reasons, includeReasons);
364                 float availableWidth = flow.availableLogicalWidthForLine(floatingObject->y(), DoNotIndentText);
365                 if (availableWidth < minimumWidthNeeded)
366                     SET_REASON_AND_RETURN_IF_NEEDED(FlowHasUnsupportedFloat, reasons, includeReasons);
367             }
368         }
369     }
370     auto fontAndTextReasons = canUseForFontAndText(flow, includeReasons);
371     if (fontAndTextReasons != NoReason)
372         SET_REASON_AND_RETURN_IF_NEEDED(fontAndTextReasons, reasons, includeReasons);
373     return reasons;
374 }
375
376 bool canUseFor(const RenderBlockFlow& flow)
377 {
378     return canUseForWithReason(flow, IncludeReasons::First) == NoReason;
379 }
380
381 static float computeLineLeft(ETextAlign textAlign, float availableWidth, float committedWidth, float logicalLeftOffset)
382 {
383     float remainingWidth = availableWidth - committedWidth;
384     float left = logicalLeftOffset;
385     switch (textAlign) {
386     case LEFT:
387     case WEBKIT_LEFT:
388     case TASTART:
389         return left;
390     case RIGHT:
391     case WEBKIT_RIGHT:
392     case TAEND:
393         return left + std::max<float>(remainingWidth, 0);
394     case CENTER:
395     case WEBKIT_CENTER:
396         return left + std::max<float>(remainingWidth / 2, 0);
397     case JUSTIFY:
398         ASSERT_NOT_REACHED();
399         break;
400     }
401     ASSERT_NOT_REACHED();
402     return 0;
403 }
404
405 static void revertRuns(Layout::RunVector& runs, unsigned positionToRevertTo, float width)
406 {
407     while (runs.size()) {
408         auto& lastRun = runs.last();
409         if (lastRun.end <= positionToRevertTo)
410             break;
411         if (lastRun.start >= positionToRevertTo) {
412             // Revert this run completely.
413             width -= (lastRun.logicalRight - lastRun.logicalLeft);
414             runs.removeLast();
415         } else {
416             lastRun.logicalRight -= width;
417             width = 0;
418             lastRun.end = positionToRevertTo;
419             // Partial removal.
420             break;
421         }
422     }
423 }
424
425 class LineState {
426 public:
427     void setAvailableWidth(float width) { m_availableWidth = width; }
428     void setCollapedWhitespaceWidth(float width) { m_collapsedWhitespaceWidth = width; }
429     void setLogicalLeftOffset(float offset) { m_logicalLeftOffset = offset; }
430     void setOverflowedFragment(const TextFragmentIterator::TextFragment& fragment) { m_overflowedFragment = fragment; }
431     void setNeedsAllFragments()
432     {
433         ASSERT(!m_fragments);
434         m_fragments.emplace();
435     }
436
437     float availableWidth() const { return m_availableWidth; }
438     float logicalLeftOffset() const { return m_logicalLeftOffset; }
439     const TextFragmentIterator::TextFragment& overflowedFragment() const { return m_overflowedFragment; }
440     bool hasTrailingWhitespace() const { return m_lastFragment.type() == TextFragmentIterator::TextFragment::Whitespace; }
441     TextFragmentIterator::TextFragment lastFragment() const { return m_lastFragment; }
442     bool isWhitespaceOnly() const { return m_trailingWhitespaceWidth && m_runsWidth == m_trailingWhitespaceWidth; }
443     bool fits(float extra) const { return m_availableWidth >= m_runsWidth + extra; }
444     bool firstCharacterFits() const { return m_firstCharacterFits; }
445     float width() const { return m_runsWidth; }
446     std::pair<unsigned, bool> expansionOpportunityCount(unsigned from, unsigned to) const
447     {
448         ASSERT(m_fragments);
449         // linebreak runs are special.
450         if (from == to)
451             return std::make_pair(0, false);
452         unsigned expansionOpportunityCount = 0;
453         auto previousFragmentType = TextFragmentIterator::TextFragment::ContentEnd;
454         for (const auto& fragment : *m_fragments) {
455             if (fragment.end() <= from)
456                 continue;
457             auto currentFragmentType = fragment.type();
458             auto expansionOpportunity = this->expansionOpportunity(currentFragmentType, previousFragmentType);
459             if (expansionOpportunity)
460                 ++expansionOpportunityCount;
461             previousFragmentType = currentFragmentType;
462             if (fragment.end() >= to)
463                 return std::make_pair(expansionOpportunityCount, expansionOpportunity);
464         }
465         ASSERT_NOT_REACHED();
466         return std::make_pair(expansionOpportunityCount, false);
467     }
468
469     bool isEmpty() const
470     {
471         if (!m_lastFragment.isValid())
472             return true;
473         if (!m_lastCompleteFragment.isEmpty())
474             return false;
475         return m_lastFragment.overlapsToNextRenderer();
476     }
477
478     static inline unsigned endPositionForCollapsedFragment(const TextFragmentIterator::TextFragment& fragment)
479     {
480         return fragment.isCollapsed() ? fragment.start() + 1 : fragment.end();
481     }
482
483     void appendFragmentAndCreateRunIfNeeded(const TextFragmentIterator::TextFragment& fragment, Layout::RunVector& runs)
484     {
485         // Adjust end position while collapsing.
486         unsigned endPosition = endPositionForCollapsedFragment(fragment);
487         // New line needs new run.
488         if (!m_runsWidth) {
489             ASSERT(!m_uncompletedWidth);
490             runs.append(Run(fragment.start(), endPosition, m_runsWidth, m_runsWidth + fragment.width(), false, fragment.hasHyphen()));
491         } else {
492             // Advance last completed fragment when the previous fragment is all set (including multiple parts across renderers)
493             if ((m_lastFragment.type() != fragment.type()) || !m_lastFragment.overlapsToNextRenderer()) {
494                 m_lastCompleteFragment = m_lastFragment;
495                 m_uncompletedWidth = fragment.width();
496             } else
497                 m_uncompletedWidth += fragment.width();
498             // Collapse neighbouring whitespace, if they are across multiple renderers and are not collapsed yet.
499             if (m_lastFragment.isCollapsible() && fragment.isCollapsible()) {
500                 ASSERT(m_lastFragment.isLastInRenderer());
501                 if (!m_lastFragment.isCollapsed()) {
502                     // Line width needs to be adjusted so that now it takes collapsing into consideration.
503                     m_runsWidth -= (m_lastFragment.width() - m_collapsedWhitespaceWidth);
504                 }
505                 // This fragment is collapsed completely. No run is needed.
506                 return;
507             }
508             if (m_lastFragment.isLastInRenderer() || m_lastFragment.isCollapsed())
509                 runs.append(Run(fragment.start(), endPosition, m_runsWidth, m_runsWidth + fragment.width(), false, fragment.hasHyphen()));
510             else {
511                 Run& lastRun = runs.last();
512                 lastRun.end = endPosition;
513                 lastRun.logicalRight += fragment.width();
514                 ASSERT(!lastRun.hasHyphen);
515                 lastRun.hasHyphen = fragment.hasHyphen();
516             }
517         }
518         m_runsWidth += fragment.width();
519         m_lastFragment = fragment;
520         if (m_fragments)
521             (*m_fragments).append(fragment);
522
523         if (fragment.type() == TextFragmentIterator::TextFragment::Whitespace)
524             m_trailingWhitespaceWidth += fragment.width();
525         else {
526             m_trailingWhitespaceWidth = 0;
527             m_lastNonWhitespaceFragment = fragment;
528         }
529
530         if (!m_firstCharacterFits)
531             m_firstCharacterFits = fragment.start() + 1 > endPosition || m_runsWidth <= m_availableWidth;
532     }
533
534     TextFragmentIterator::TextFragment revertToLastCompleteFragment(Layout::RunVector& runs)
535     {
536         if (!m_uncompletedWidth) {
537             ASSERT(m_lastFragment == m_lastCompleteFragment);
538             return m_lastFragment;
539         }
540         ASSERT(m_lastFragment.isValid());
541         m_runsWidth -= m_uncompletedWidth;
542         revertRuns(runs, endPositionForCollapsedFragment(m_lastCompleteFragment), m_uncompletedWidth);
543         m_uncompletedWidth = 0;
544         ASSERT(m_lastCompleteFragment.isValid());
545         return m_lastCompleteFragment;
546     }
547
548     void removeTrailingWhitespace(Layout::RunVector& runs)
549     {
550         if (m_lastFragment.type() != TextFragmentIterator::TextFragment::Whitespace || m_lastFragment.end() == m_lastNonWhitespaceFragment.end())
551             return;
552         revertRuns(runs, m_lastNonWhitespaceFragment.end(), m_trailingWhitespaceWidth);
553         m_runsWidth -= m_trailingWhitespaceWidth;
554         m_lastFragment = m_lastNonWhitespaceFragment;
555     }
556
557 private:
558     bool expansionOpportunity(TextFragmentIterator::TextFragment::Type currentFragmentType, TextFragmentIterator::TextFragment::Type previousFragmentType) const
559     {
560         return (currentFragmentType == TextFragmentIterator::TextFragment::Whitespace
561             || (currentFragmentType == TextFragmentIterator::TextFragment::NonWhitespace && previousFragmentType == TextFragmentIterator::TextFragment::NonWhitespace));
562     }
563
564     float m_availableWidth { 0 };
565     float m_logicalLeftOffset { 0 };
566     float m_runsWidth { 0 };
567     TextFragmentIterator::TextFragment m_overflowedFragment;
568     TextFragmentIterator::TextFragment m_lastFragment;
569     TextFragmentIterator::TextFragment m_lastNonWhitespaceFragment;
570     TextFragmentIterator::TextFragment m_lastCompleteFragment;
571     float m_uncompletedWidth { 0 };
572     float m_trailingWhitespaceWidth { 0 }; // Use this to remove trailing whitespace without re-mesuring the text.
573     float m_collapsedWhitespaceWidth { 0 };
574     // Having one character on the line does not necessarily mean it actually fits.
575     // First character of the first fragment might be forced on to the current line even if it does not fit.
576     bool m_firstCharacterFits { false };
577     std::optional<Vector<TextFragmentIterator::TextFragment, 30>> m_fragments;
578 };
579
580 class FragmentForwardIterator : public std::iterator<std::forward_iterator_tag, unsigned> {
581 public:
582     FragmentForwardIterator(unsigned fragmentIndex)
583         : m_fragmentIndex(fragmentIndex)
584     {
585     }
586
587     FragmentForwardIterator& operator++()
588     {
589         ++m_fragmentIndex;
590         return *this;
591     }
592
593     bool operator!=(const FragmentForwardIterator& other) const { return m_fragmentIndex != other.m_fragmentIndex; }
594     bool operator==(const FragmentForwardIterator& other) const { return m_fragmentIndex == other.m_fragmentIndex; }
595     unsigned operator*() const { return m_fragmentIndex; }
596
597 private:
598     unsigned m_fragmentIndex { 0 };
599 };
600
601 static FragmentForwardIterator begin(const TextFragmentIterator::TextFragment& fragment)  { return FragmentForwardIterator(fragment.start()); }
602 static FragmentForwardIterator end(const TextFragmentIterator::TextFragment& fragment)  { return FragmentForwardIterator(fragment.end()); }
603
604 static bool preWrap(const TextFragmentIterator::Style& style)
605 {
606     return style.wrapLines && !style.collapseWhitespace;
607 }
608     
609 static void removeTrailingWhitespace(LineState& lineState, Layout::RunVector& runs, const TextFragmentIterator& textFragmentIterator)
610 {
611     if (!lineState.hasTrailingWhitespace())
612         return;
613     // Remove collapsed whitespace, or non-collapsed pre-wrap whitespace, unless it's the only content on the line -so removing the whitesapce
614     // would produce an empty line.
615     const auto& style = textFragmentIterator.style();
616     bool collapseWhitespace = style.collapseWhitespace | preWrap(style);
617     if (!collapseWhitespace)
618         return;
619     if (preWrap(style) && lineState.isWhitespaceOnly())
620         return;
621     lineState.removeTrailingWhitespace(runs);
622 }
623
624 static void updateLineConstrains(const RenderBlockFlow& flow, LineState& line, const TextFragmentIterator::Style& style, bool isFirstLine)
625 {
626     bool shouldApplyTextIndent = !flow.isAnonymous() || flow.parent()->firstChild() == &flow;
627     LayoutUnit height = flow.logicalHeight();
628     line.setLogicalLeftOffset(flow.logicalLeftOffsetForLine(height, DoNotIndentText) + (shouldApplyTextIndent && isFirstLine ? flow.textIndentOffset() : LayoutUnit(0)));
629     float logicalRightOffset = flow.logicalRightOffsetForLine(height, DoNotIndentText);
630     line.setAvailableWidth(std::max<float>(0, logicalRightOffset - line.logicalLeftOffset()));
631     if (style.textAlign == JUSTIFY)
632         line.setNeedsAllFragments();
633 }
634
635 static std::optional<unsigned> hyphenPositionForFragment(unsigned splitPosition, TextFragmentIterator::TextFragment& fragmentToSplit,
636     const TextFragmentIterator& textFragmentIterator, float availableWidth)
637 {
638     auto& style = textFragmentIterator.style();
639     bool shouldHyphenate = style.shouldHyphenate && (!style.hyphenLimitLines || fragmentToSplit.wrappingWithHyphenCounter() < *style.hyphenLimitLines);
640     if (!shouldHyphenate)
641         return std::nullopt;
642
643     if (!enoughWidthForHyphenation(availableWidth, style.font.pixelSize()))
644         return std::nullopt;
645
646     // We might be able to fit the hyphen at the split position.
647     auto splitPositionWithHyphen = splitPosition;
648     // Find a splitting position where hyphen surely fits.
649     unsigned start = fragmentToSplit.start();
650     auto leftSideWidth = textFragmentIterator.textWidth(start, splitPosition, 0);
651     while (leftSideWidth + style.hyphenStringWidth > availableWidth) {
652         if (--splitPositionWithHyphen <= start)
653             return std::nullopt; // No space for hyphen.
654         leftSideWidth -= textFragmentIterator.textWidth(splitPositionWithHyphen, splitPositionWithHyphen + 1, 0);
655     }
656     ASSERT(splitPositionWithHyphen > start);
657     return textFragmentIterator.lastHyphenPosition(fragmentToSplit, splitPositionWithHyphen + 1);
658 }
659
660 static TextFragmentIterator::TextFragment splitFragmentToFitLine(TextFragmentIterator::TextFragment& fragmentToSplit, float availableWidth, bool keepAtLeastOneCharacter, const TextFragmentIterator& textFragmentIterator)
661 {
662     // FIXME: add surrogate pair support.
663     unsigned start = fragmentToSplit.start();
664     auto it = std::upper_bound(begin(fragmentToSplit), end(fragmentToSplit), availableWidth, [&textFragmentIterator, start](float availableWidth, unsigned index) {
665         // FIXME: use the actual left position of the line (instead of 0) to calculated width. It might give false width for tab characters.
666         return availableWidth < textFragmentIterator.textWidth(start, index + 1, 0);
667     });
668     unsigned splitPosition = (*it);
669     // Does first character fit this line?
670     if (splitPosition == start) {
671         if (keepAtLeastOneCharacter)
672             ++splitPosition;
673     } else if (auto hyphenPosition = hyphenPositionForFragment(splitPosition, fragmentToSplit, textFragmentIterator, availableWidth))
674         return fragmentToSplit.splitWithHyphen(*hyphenPosition, textFragmentIterator);
675     return fragmentToSplit.split(splitPosition, textFragmentIterator);
676 }
677
678 enum PreWrapLineBreakRule { Preserve, Ignore };
679
680 static TextFragmentIterator::TextFragment consumeLineBreakIfNeeded(const TextFragmentIterator::TextFragment& fragment, TextFragmentIterator& textFragmentIterator, LineState& line, Layout::RunVector& runs,
681     PreWrapLineBreakRule preWrapLineBreakRule = PreWrapLineBreakRule::Preserve)
682 {
683     if (!fragment.isLineBreak())
684         return fragment;
685
686     if (preWrap(textFragmentIterator.style()) && preWrapLineBreakRule != PreWrapLineBreakRule::Ignore)
687         return fragment;
688
689     // <br> always produces a run. (required by testing output)
690     if (fragment.type() == TextFragmentIterator::TextFragment::HardLineBreak)
691         line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
692     return textFragmentIterator.nextTextFragment();
693 }
694
695 static TextFragmentIterator::TextFragment skipWhitespaceIfNeeded(const TextFragmentIterator::TextFragment& fragment, TextFragmentIterator& textFragmentIterator)
696 {
697     if (!textFragmentIterator.style().collapseWhitespace)
698         return fragment;
699
700     TextFragmentIterator::TextFragment firstNonWhitespaceFragment = fragment;
701     while (firstNonWhitespaceFragment.type() == TextFragmentIterator::TextFragment::Whitespace)
702         firstNonWhitespaceFragment = textFragmentIterator.nextTextFragment();
703     return firstNonWhitespaceFragment;
704 }
705
706 static TextFragmentIterator::TextFragment firstFragment(TextFragmentIterator& textFragmentIterator, LineState& currentLine, const LineState& previousLine, Layout::RunVector& runs)
707 {
708     // Handle overflowed fragment from previous line.
709     TextFragmentIterator::TextFragment firstFragment(previousLine.overflowedFragment());
710
711     if (firstFragment.isEmpty())
712         firstFragment = textFragmentIterator.nextTextFragment();
713     else if (firstFragment.type() == TextFragmentIterator::TextFragment::Whitespace && preWrap(textFragmentIterator.style()) && previousLine.firstCharacterFits()) {
714         // 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.
715         firstFragment = textFragmentIterator.nextTextFragment();
716         // If skipping the whitespace puts us on a newline, skip the newline too as we already wrapped the line.
717         firstFragment = consumeLineBreakIfNeeded(firstFragment, textFragmentIterator, currentLine, runs, PreWrapLineBreakRule::Ignore);
718     }
719     return skipWhitespaceIfNeeded(firstFragment, textFragmentIterator);
720 }
721
722 static void forceFragmentToLine(LineState& line, TextFragmentIterator& textFragmentIterator, Layout::RunVector& runs, const TextFragmentIterator::TextFragment& fragment)
723 {
724     line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
725     // Check if there are more fragments to add to the current line.
726     auto nextFragment = textFragmentIterator.nextTextFragment();
727     if (fragment.overlapsToNextRenderer()) {
728         while (true) {
729             if (nextFragment.type() != fragment.type())
730                 break;
731             line.appendFragmentAndCreateRunIfNeeded(nextFragment, runs);
732             // Does it overlap to the next segment?
733             if (!nextFragment.overlapsToNextRenderer())
734                 return;
735             nextFragment = textFragmentIterator.nextTextFragment();
736         }
737     }
738     // 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.
739     nextFragment = skipWhitespaceIfNeeded(nextFragment, textFragmentIterator);
740     nextFragment = consumeLineBreakIfNeeded(nextFragment, textFragmentIterator, line, runs);
741     line.setOverflowedFragment(nextFragment);
742 }
743
744 static bool createLineRuns(LineState& line, const LineState& previousLine, Layout::RunVector& runs, TextFragmentIterator& textFragmentIterator)
745 {
746     const auto& style = textFragmentIterator.style();
747     line.setCollapedWhitespaceWidth(style.spaceWidth + style.wordSpacing);
748     bool lineCanBeWrapped = style.wrapLines || style.breakFirstWordOnOverflow || style.breakAnyWordOnOverflow;
749     auto fragment = firstFragment(textFragmentIterator, line, previousLine, runs);
750     while (fragment.type() != TextFragmentIterator::TextFragment::ContentEnd) {
751         // Hard linebreak.
752         if (fragment.isLineBreak()) {
753             // 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.)
754             if (line.isEmpty() || fragment.type() == TextFragmentIterator::TextFragment::HardLineBreak) {
755                 if (style.textAlign == RIGHT || style.textAlign == WEBKIT_RIGHT)
756                     line.removeTrailingWhitespace(runs);
757                 line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
758             }
759             break;
760         }
761         if (lineCanBeWrapped && !line.fits(fragment.width())) {
762             // Overflow wrapping behaviour:
763             // 1. Whitesapce collapse on: whitespace is skipped. Jump to next line.
764             // 2. Whitespace collapse off: whitespace is wrapped.
765             // 3. First, non-whitespace fragment is either wrapped or kept on the line. (depends on overflow-wrap)
766             // 5. Non-whitespace fragment when there's already another fragment on the line either gets wrapped (word-break: break-all)
767             // or gets pushed to the next line.
768             bool emptyLine = line.isEmpty();
769             // Whitespace fragment.
770             if (fragment.type() == TextFragmentIterator::TextFragment::Whitespace) {
771                 if (!style.collapseWhitespace) {
772                     // Split the fragment; (modified)fragment stays on this line, overflowedFragment is pushed to next line.
773                     line.setOverflowedFragment(splitFragmentToFitLine(fragment, line.availableWidth() - line.width(), emptyLine, textFragmentIterator));
774                     line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
775                 }
776                 // When whitespace collapse is on, whitespace that doesn't fit is simply skipped.
777                 break;
778             }
779             // Non-whitespace fragment. (!style.wrapLines: bug138102(preserve existing behavior)
780             if (((emptyLine && style.breakFirstWordOnOverflow) || style.breakAnyWordOnOverflow) || !style.wrapLines) {
781                 // Split the fragment; (modified)fragment stays on this line, overflowedFragment is pushed to next line.
782                 line.setOverflowedFragment(splitFragmentToFitLine(fragment, line.availableWidth() - line.width(), emptyLine, textFragmentIterator));
783                 line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
784                 break;
785             }
786             ASSERT(fragment.type() == TextFragmentIterator::TextFragment::NonWhitespace);
787             // Find out if this non-whitespace fragment has a hyphen where we can break.
788             if (style.shouldHyphenate) {
789                 auto fragmentToSplit = fragment;
790                 // Split and check if we actually ended up with a hyphen.
791                 auto overflowFragment = splitFragmentToFitLine(fragmentToSplit, line.availableWidth() - line.width(), emptyLine, textFragmentIterator);
792                 if (fragmentToSplit.hasHyphen()) {
793                     line.setOverflowedFragment(overflowFragment);
794                     line.appendFragmentAndCreateRunIfNeeded(fragmentToSplit, runs);
795                     break;
796                 }
797                 // No hyphen, no split.
798             }
799             // Non-breakable non-whitespace first fragment. Add it to the current line. -it overflows though.
800             if (emptyLine) {
801                 forceFragmentToLine(line, textFragmentIterator, runs, fragment);
802                 break;
803             }
804             // Non-breakable non-whitespace fragment when there's already content on the line. Push it to the next line.
805             ASSERT(line.lastFragment().isValid());
806             if (line.lastFragment().overlapsToNextRenderer()) {
807                 // Check if this fragment is a continuation of a previous segment. In such cases, we need to remove them all.
808                 textFragmentIterator.revertToEndOfFragment(line.revertToLastCompleteFragment(runs));
809                 break;
810             }
811             line.setOverflowedFragment(fragment);
812             break;
813         }
814         line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
815         // Find the next text fragment.
816         fragment = textFragmentIterator.nextTextFragment(line.width());
817     }
818     return (fragment.type() == TextFragmentIterator::TextFragment::ContentEnd && line.overflowedFragment().isEmpty()) || line.overflowedFragment().type() == TextFragmentIterator::TextFragment::ContentEnd;
819 }
820
821 static ExpansionBehavior expansionBehavior(bool isAfterExpansion, bool lastRunOnLine)
822 {
823     ExpansionBehavior expansionBehavior;
824     expansionBehavior = isAfterExpansion ? ForbidLeadingExpansion : AllowLeadingExpansion;
825     expansionBehavior |= lastRunOnLine ? ForbidTrailingExpansion : AllowTrailingExpansion;
826     return expansionBehavior;
827 }
828
829 static void justifyRuns(const LineState& line, Layout::RunVector& runs, unsigned firstRunIndex)
830 {
831     ASSERT(runs.size());
832     auto widthToDistribute = line.availableWidth() - line.width();
833     if (widthToDistribute <= 0)
834         return;
835
836     auto lastRunIndex = runs.size() - 1;
837     ASSERT(firstRunIndex <= lastRunIndex);
838     Vector<std::pair<unsigned, ExpansionBehavior>> expansionOpportunityList;
839     unsigned expansionOpportunityCountOnThisLine = 0;
840     auto isAfterExpansion = true;
841     for (auto i = firstRunIndex; i <= lastRunIndex; ++i) {
842         const auto& run = runs.at(i);
843         unsigned opportunityCountInRun = 0;
844         std::tie(opportunityCountInRun, isAfterExpansion) = line.expansionOpportunityCount(run.start, run.end);
845         expansionOpportunityList.append(std::make_pair(opportunityCountInRun, expansionBehavior(isAfterExpansion, i == lastRunIndex)));
846         expansionOpportunityCountOnThisLine += opportunityCountInRun;
847     }
848     if (!expansionOpportunityCountOnThisLine)
849         return;
850
851     ASSERT(expansionOpportunityList.size() == lastRunIndex - firstRunIndex + 1);
852     auto expansion = widthToDistribute / expansionOpportunityCountOnThisLine;
853     float accumulatedExpansion = 0;
854     for (auto i = firstRunIndex; i <= lastRunIndex; ++i) {
855         auto& run = runs.at(i);
856         unsigned opportunityCountInRun;
857         std::tie(opportunityCountInRun, run.expansionBehavior) = expansionOpportunityList.at(i - firstRunIndex);
858         run.expansion = opportunityCountInRun * expansion;
859         run.logicalLeft += accumulatedExpansion;
860         run.logicalRight += (accumulatedExpansion + run.expansion);
861         accumulatedExpansion += run.expansion;
862     }
863 }
864
865 static ETextAlign textAlignForLine(const TextFragmentIterator::Style& style, bool lastLine)
866 {
867     // Fallback to LEFT (START) alignment for non-collapsable content and for the last line before a forced break or the end of the block.
868     auto textAlign = style.textAlign;
869     if (textAlign == JUSTIFY && (!style.collapseWhitespace || lastLine))
870         textAlign = LEFT;
871     return textAlign;
872 }
873
874 static void closeLineEndingAndAdjustRuns(LineState& line, Layout::RunVector& runs, std::optional<unsigned> lastRunIndexOfPreviousLine, unsigned& lineCount,
875     const TextFragmentIterator& textFragmentIterator, bool lastLineInFlow)
876 {
877     if (!runs.size() || (lastRunIndexOfPreviousLine && runs.size() - 1 == lastRunIndexOfPreviousLine.value()))
878         return;
879     removeTrailingWhitespace(line, runs, textFragmentIterator);
880     if (!runs.size())
881         return;
882     // Adjust runs' position by taking line's alignment into account.
883     const auto& style = textFragmentIterator.style();
884     auto firstRunIndex = lastRunIndexOfPreviousLine ? lastRunIndexOfPreviousLine.value() + 1 : 0;
885     auto lineLogicalLeft = line.logicalLeftOffset();
886     auto textAlign = textAlignForLine(style, lastLineInFlow || (line.lastFragment().isValid() && line.lastFragment().type() == TextFragmentIterator::TextFragment::HardLineBreak));
887     if (textAlign == JUSTIFY)
888         justifyRuns(line, runs, firstRunIndex);
889     else
890         lineLogicalLeft = computeLineLeft(textAlign, line.availableWidth(), line.width(), line.logicalLeftOffset());
891     for (auto i = firstRunIndex; i < runs.size(); ++i) {
892         runs[i].logicalLeft += lineLogicalLeft;
893         runs[i].logicalRight += lineLogicalLeft;
894     }
895     runs.last().isEndOfLine = true;
896     ++lineCount;
897 }
898
899 static void createTextRuns(Layout::RunVector& runs, RenderBlockFlow& flow, unsigned& lineCount)
900 {
901     LayoutUnit borderAndPaddingBefore = flow.borderAndPaddingBefore();
902     LayoutUnit lineHeight = lineHeightFromFlow(flow);
903     LineState line;
904     bool isEndOfContent = false;
905     TextFragmentIterator textFragmentIterator = TextFragmentIterator(flow);
906     std::optional<unsigned> lastRunIndexOfPreviousLine;
907     do {
908         flow.setLogicalHeight(lineHeight * lineCount + borderAndPaddingBefore);
909         LineState previousLine = line;
910         line = LineState();
911         updateLineConstrains(flow, line, textFragmentIterator.style(), !lineCount);
912         isEndOfContent = createLineRuns(line, previousLine, runs, textFragmentIterator);
913         closeLineEndingAndAdjustRuns(line, runs, lastRunIndexOfPreviousLine, lineCount, textFragmentIterator, isEndOfContent);
914         if (runs.size())
915             lastRunIndexOfPreviousLine = runs.size() - 1;
916     } while (!isEndOfContent);
917 }
918
919 std::unique_ptr<Layout> create(RenderBlockFlow& flow)
920 {
921     unsigned lineCount = 0;
922     Layout::RunVector runs;
923
924     createTextRuns(runs, flow, lineCount);
925     return Layout::create(runs, lineCount);
926 }
927
928 std::unique_ptr<Layout> Layout::create(const RunVector& runVector, unsigned lineCount)
929 {
930     void* slot = WTF::fastMalloc(sizeof(Layout) + sizeof(Run) * runVector.size());
931     return std::unique_ptr<Layout>(new (NotNull, slot) Layout(runVector, lineCount));
932 }
933
934 Layout::Layout(const RunVector& runVector, unsigned lineCount)
935     : m_lineCount(lineCount)
936     , m_runCount(runVector.size())
937 {
938     memcpy(m_runs, runVector.data(), m_runCount * sizeof(Run));
939 }
940
941 #ifndef NDEBUG
942 static void printReason(AvoidanceReason reason, TextStream& stream)
943 {
944     switch (reason) {
945     case FlowIsInsideRegion:
946         stream << "flow is inside region";
947         break;
948     case FlowHasHorizonalWritingMode:
949         stream << "horizontal writing mode";
950         break;
951     case FlowHasOutline:
952         stream << "outline";
953         break;
954     case FlowIsRuby:
955         stream << "ruby";
956         break;
957     case FlowHasHangingPunctuation:
958         stream << "hanging punctuation";
959         break;
960     case FlowIsPaginated:
961         stream << "paginated";
962         break;
963     case FlowHasTextOverflow:
964         stream << "text-overflow";
965         break;
966     case FlowIsDepricatedFlexBox:
967         stream << "depricatedFlexBox";
968         break;
969     case FlowParentIsPlaceholderElement:
970         stream << "placeholder element";
971         break;
972     case FlowParentIsTextAreaWithWrapping:
973         stream << "wrapping textarea";
974         break;
975     case FlowHasNonSupportedChild:
976         stream << "nested renderers";
977         break;
978     case FlowHasUnsupportedFloat:
979         stream << "complicated float";
980         break;
981     case FlowHasUnsupportedUnderlineDecoration:
982         stream << "text-underline-position: under";
983         break;
984     case FlowHasJustifiedNonLatinText:
985         stream << "text-align: justify with non-latin text";
986         break;
987     case FlowHasOverflowVisible:
988         stream << "overflow: visible";
989         break;
990     case FlowHasWebKitNBSPMode:
991         stream << "-webkit-nbsp-mode: space";
992         break;
993     case FlowIsNotLTR:
994         stream << "dir is not LTR";
995         break;
996     case FlowHasLineBoxContainProperty:
997         stream << "line-box-contain value indicates variable line height";
998         break;
999     case FlowIsNotTopToBottom:
1000         stream << "non top-to-bottom flow";
1001         break;
1002     case FlowHasLineBreak:
1003         stream << "line-break property";
1004         break;
1005     case FlowHasNonNormalUnicodeBiDi:
1006         stream << "non-normal Unicode bidi";
1007         break;
1008     case FlowHasRTLOrdering:
1009         stream << "-webkit-rtl-ordering";
1010         break;
1011     case FlowHasLineAlignEdges:
1012         stream << "-webkit-line-align edges";
1013         break;
1014     case FlowHasLineSnap:
1015         stream << "-webkit-line-snap property";
1016         break;
1017     case FlowHasTextEmphasisFillOrMark:
1018         stream << "text-emphasis (fill/mark)";
1019         break;
1020     case FlowHasPseudoFirstLine:
1021         stream << "first-line";
1022         break;
1023     case FlowHasPseudoFirstLetter:
1024         stream << "first-letter";
1025         break;
1026     case FlowHasTextCombine:
1027         stream << "text combine";
1028         break;
1029     case FlowHasTextFillBox:
1030         stream << "background-color (text-fill)";
1031         break;
1032     case FlowHasBorderFitLines:
1033         stream << "-webkit-border-fit";
1034         break;
1035     case FlowHasNonAutoLineBreak:
1036         stream << "line-break is not auto";
1037         break;
1038     case FlowHasNonAutoTrailingWord:
1039         stream << "-apple-trailing-word is not auto";
1040         break;
1041     case FlowHasSVGFont:
1042         stream << "SVG font";
1043         break;
1044     case FlowTextHasSoftHyphen:
1045         stream << "soft hyphen character";
1046         break;
1047     case FlowTextHasDirectionCharacter:
1048         stream << "direction character";
1049         break;
1050     case FlowIsMissingPrimaryFont:
1051         stream << "missing primary font";
1052         break;
1053     case FlowPrimaryFontIsInsufficient:
1054         stream << "missing glyph or glyph needs another font";
1055         break;
1056     case FlowTextIsCombineText:
1057         stream << "text is combine";
1058         break;
1059     case FlowTextIsRenderCounter:
1060         stream << "unsupported RenderCounter";
1061         break;
1062     case FlowTextIsRenderQuote:
1063         stream << "unsupported RenderQuote";
1064         break;
1065     case FlowTextIsTextFragment:
1066         stream << "unsupported TextFragment";
1067         break;
1068     case FlowTextIsSVGInlineText:
1069         stream << "unsupported SVGInlineText";
1070         break;
1071     case FlowHasComplexFontCodePath:
1072         stream << "text with complex font codepath";
1073         break;
1074     case FlowHasTextShadow:
1075         stream << "text-shadow";
1076         break;
1077     case FlowChildIsSelected:
1078         stream << "selected content";
1079         break;
1080     case FlowFontHasOverflowGlyph:
1081         stream << "-webkit-line-box-contain: glyphs with overflowing text.";
1082         break;
1083     case FlowTextIsEmpty:
1084     case FlowHasNoChild:
1085     case FlowHasNoParent:
1086     case FeatureIsDisabled:
1087     default:
1088         break;
1089     }
1090 }
1091
1092 static void printReasons(AvoidanceReasonFlags reasons, TextStream& stream)
1093 {
1094     bool first = true;
1095     for (auto reasonItem = EndOfReasons >> 1; reasonItem != NoReason; reasonItem >>= 1) {
1096         if (!(reasons & reasonItem))
1097             continue;
1098         stream << (first ? " " : ", ");
1099         first = false;
1100         printReason(reasonItem, stream);
1101     }
1102 }
1103
1104 static void printTextForSubtree(const RenderObject& renderer, unsigned& charactersLeft, TextStream& stream)
1105 {
1106     if (!charactersLeft)
1107         return;
1108     if (is<RenderText>(renderer)) {
1109         String text = downcast<RenderText>(renderer).text();
1110         text = text.stripWhiteSpace();
1111         unsigned len = std::min(charactersLeft, text.length());
1112         stream << text.left(len);
1113         charactersLeft -= len;
1114         return;
1115     }
1116     if (!is<RenderElement>(renderer))
1117         return;
1118     for (const auto* child = downcast<RenderElement>(renderer).firstChild(); child; child = child->nextSibling())
1119         printTextForSubtree(*child, charactersLeft, stream);
1120 }
1121
1122 static unsigned textLengthForSubtree(const RenderObject& renderer)
1123 {
1124     if (is<RenderText>(renderer))
1125         return downcast<RenderText>(renderer).textLength();
1126     if (!is<RenderElement>(renderer))
1127         return 0;
1128     unsigned textLength = 0;
1129     for (const auto* child = downcast<RenderElement>(renderer).firstChild(); child; child = child->nextSibling())
1130         textLength += textLengthForSubtree(*child);
1131     return textLength;
1132 }
1133
1134 static void collectNonEmptyLeafRenderBlockFlows(const RenderObject& renderer, HashSet<const RenderBlockFlow*>& leafRenderers)
1135 {
1136     if (is<RenderText>(renderer)) {
1137         if (!downcast<RenderText>(renderer).textLength())
1138             return;
1139         // Find RenderBlockFlow ancestor.
1140         for (const auto* current = renderer.parent(); current; current = current->parent()) {
1141             if (!is<RenderBlockFlow>(current))
1142                 continue;
1143             leafRenderers.add(downcast<RenderBlockFlow>(current));
1144             break;
1145         }
1146         return;
1147     }
1148     if (!is<RenderElement>(renderer))
1149         return;
1150     for (const auto* child = downcast<RenderElement>(renderer).firstChild(); child; child = child->nextSibling())
1151         collectNonEmptyLeafRenderBlockFlows(*child, leafRenderers);
1152 }
1153
1154 static void collectNonEmptyLeafRenderBlockFlowsForCurrentPage(HashSet<const RenderBlockFlow*>& leafRenderers)
1155 {
1156     for (const auto* document : Document::allDocuments()) {
1157         if (!document->renderView() || document->pageCacheState() != Document::NotInPageCache)
1158             continue;
1159         if (!document->isHTMLDocument() && !document->isXHTMLDocument())
1160             continue;
1161         collectNonEmptyLeafRenderBlockFlows(*document->renderView(), leafRenderers);
1162     }
1163 }
1164
1165 void toggleSimpleLineLayout()
1166 {
1167     for (const auto* document : Document::allDocuments()) {
1168         auto* settings = document->settings();
1169         if (!settings)
1170             continue;
1171         settings->setSimpleLineLayoutEnabled(!settings->simpleLineLayoutEnabled());
1172     }
1173 }
1174
1175 void printSimpleLineLayoutBlockList()
1176 {
1177     HashSet<const RenderBlockFlow*> leafRenderers;
1178     collectNonEmptyLeafRenderBlockFlowsForCurrentPage(leafRenderers);
1179     if (!leafRenderers.size()) {
1180         WTFLogAlways("No text found in this document\n");
1181         return;
1182     }
1183     TextStream stream;
1184     stream << "---------------------------------------------------\n";
1185     for (const auto* flow : leafRenderers) {
1186         auto reason = canUseForWithReason(*flow, IncludeReasons::All);
1187         if (reason == NoReason)
1188             continue;
1189         unsigned printedLength = 30;
1190         stream << "\"";
1191         printTextForSubtree(*flow, printedLength, stream);
1192         for (;printedLength > 0; --printedLength)
1193             stream << " ";
1194         stream << "\"(" << textLengthForSubtree(*flow) << "):";
1195         printReasons(reason, stream);
1196         stream << "\n";
1197     }
1198     stream << "---------------------------------------------------\n";
1199     WTFLogAlways("%s", stream.release().utf8().data());
1200 }
1201
1202 void printSimpleLineLayoutCoverage()
1203 {
1204     HashSet<const RenderBlockFlow*> leafRenderers;
1205     collectNonEmptyLeafRenderBlockFlowsForCurrentPage(leafRenderers);
1206     if (!leafRenderers.size()) {
1207         WTFLogAlways("No text found in this document\n");
1208         return;
1209     }
1210     TextStream stream;
1211     HashMap<AvoidanceReason, unsigned> flowStatistics;
1212     unsigned textLength = 0;
1213     unsigned unsupportedTextLength = 0;
1214     unsigned numberOfUnsupportedLeafBlocks = 0;
1215     for (const auto* flow : leafRenderers) {
1216         auto flowLength = textLengthForSubtree(*flow);
1217         textLength += flowLength;
1218         auto reasons = canUseForWithReason(*flow, IncludeReasons::All);
1219         if (reasons == NoReason)
1220             continue;
1221         ++numberOfUnsupportedLeafBlocks;
1222         unsupportedTextLength += flowLength;
1223         for (auto reasonItem = EndOfReasons >> 1; reasonItem != NoReason; reasonItem >>= 1) {
1224             if (!(reasons & reasonItem))
1225                 continue;
1226             auto result = flowStatistics.add(reasonItem, flowLength);
1227             if (!result.isNewEntry)
1228                 result.iterator->value += flowLength;
1229         }
1230     }
1231     stream << "---------------------------------------------------\n";
1232     stream << "Number of text blocks: total(" <<  leafRenderers.size() << ") non-simple(" << numberOfUnsupportedLeafBlocks << ")\nText length: total(" <<
1233         textLength << ") non-simple(" << unsupportedTextLength << ")\n";
1234     for (const auto reasonEntry : flowStatistics) {
1235         printReason(reasonEntry.key, stream);
1236         stream << ": " << (float)reasonEntry.value / (float)textLength * 100 << "%\n";
1237     }
1238     stream << "simple line layout coverage: " << (float)(textLength - unsupportedTextLength) / (float)textLength * 100 << "%\n";
1239     stream << "---------------------------------------------------\n";
1240     WTFLogAlways("%s", stream.release().utf8().data());
1241 }
1242 #endif
1243 }
1244 }