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