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