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