Simple line layout: Removing adjacent trailing whitespace runs should not crash.
[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 positionToRevertTo, float width)
387 {
388     while (runs.size()) {
389         auto& lastRun = runs.last();
390         if (lastRun.end <= positionToRevertTo)
391             break;
392         if (lastRun.start >= positionToRevertTo) {
393             // Revert this run completely.
394             width -= (lastRun.logicalRight - lastRun.logicalLeft);
395             runs.removeLast();
396         } else {
397             lastRun.logicalRight -= width;
398             width = 0;
399             lastRun.end = positionToRevertTo;
400             // Partial removal.
401             break;
402         }
403     }
404 }
405
406 class LineState {
407 public:
408     void setAvailableWidth(float width) { m_availableWidth = width; }
409     void setCollapedWhitespaceWidth(float width) { m_collapsedWhitespaceWidth = width; }
410     void setLogicalLeftOffset(float offset) { m_logicalLeftOffset = offset; }
411     void setOverflowedFragment(const TextFragmentIterator::TextFragment& fragment) { m_overflowedFragment = fragment; }
412     void setNeedsAllFragments()
413     {
414         ASSERT(!m_fragments);
415         m_fragments.emplace();
416     }
417
418     float availableWidth() const { return m_availableWidth; }
419     float logicalLeftOffset() const { return m_logicalLeftOffset; }
420     const TextFragmentIterator::TextFragment& overflowedFragment() const { return m_overflowedFragment; }
421     bool hasTrailingWhitespace() const { return m_lastFragment.type() == TextFragmentIterator::TextFragment::Whitespace; }
422     TextFragmentIterator::TextFragment lastFragment() const { return m_lastFragment; }
423     bool isWhitespaceOnly() const { return m_trailingWhitespaceWidth && m_runsWidth == m_trailingWhitespaceWidth; }
424     bool fits(float extra) const { return m_availableWidth >= m_runsWidth + extra; }
425     bool firstCharacterFits() const { return m_firstCharacterFits; }
426     float width() const { return m_runsWidth; }
427     std::pair<unsigned, bool> expansionOpportunityCount(unsigned from, unsigned to) const
428     {
429         ASSERT(m_fragments);
430         // linebreak runs are special.
431         if (from == to)
432             return std::make_pair(0, false);
433         unsigned expansionOpportunityCount = 0;
434         auto previousFragmentType = TextFragmentIterator::TextFragment::ContentEnd;
435         for (const auto& fragment : *m_fragments) {
436             if (fragment.end() <= from)
437                 continue;
438             auto currentFragmentType = fragment.type();
439             auto expansionOpportunity = this->expansionOpportunity(currentFragmentType, previousFragmentType);
440             if (expansionOpportunity)
441                 ++expansionOpportunityCount;
442             previousFragmentType = currentFragmentType;
443             if (fragment.end() >= to)
444                 return std::make_pair(expansionOpportunityCount, expansionOpportunity);
445         }
446         ASSERT_NOT_REACHED();
447         return std::make_pair(expansionOpportunityCount, false);
448     }
449
450     bool isEmpty() const
451     {
452         if (!m_lastFragment.isValid())
453             return true;
454         if (!m_lastCompleteFragment.isEmpty())
455             return false;
456         return m_lastFragment.overlapsToNextRenderer();
457     }
458
459     static inline unsigned endPositionForCollapsedFragment(const TextFragmentIterator::TextFragment& fragment)
460     {
461         return fragment.isCollapsed() ? fragment.start() + 1 : fragment.end();
462     }
463
464     void appendFragmentAndCreateRunIfNeeded(const TextFragmentIterator::TextFragment& fragment, Layout::RunVector& runs)
465     {
466         // Adjust end position while collapsing.
467         unsigned endPosition = endPositionForCollapsedFragment(fragment);
468         // New line needs new run.
469         if (!m_runsWidth) {
470             ASSERT(!m_uncompletedWidth);
471             runs.append(Run(fragment.start(), endPosition, m_runsWidth, m_runsWidth + fragment.width(), false, fragment.hasHyphen()));
472         } else {
473             // Advance last completed fragment when the previous fragment is all set (including multiple parts across renderers)
474             if ((m_lastFragment.type() != fragment.type()) || !m_lastFragment.overlapsToNextRenderer()) {
475                 m_lastCompleteFragment = m_lastFragment;
476                 m_uncompletedWidth = fragment.width();
477             } else
478                 m_uncompletedWidth += fragment.width();
479             // Collapse neighbouring whitespace, if they are across multiple renderers and are not collapsed yet.
480             if (m_lastFragment.isCollapsible() && fragment.isCollapsible()) {
481                 ASSERT(m_lastFragment.isLastInRenderer());
482                 if (!m_lastFragment.isCollapsed()) {
483                     // Line width needs to be adjusted so that now it takes collapsing into consideration.
484                     m_runsWidth -= (m_lastFragment.width() - m_collapsedWhitespaceWidth);
485                 }
486                 // This fragment is collapsed completely. No run is needed.
487                 return;
488             }
489             if (m_lastFragment.isLastInRenderer() || m_lastFragment.isCollapsed())
490                 runs.append(Run(fragment.start(), endPosition, m_runsWidth, m_runsWidth + fragment.width(), false, fragment.hasHyphen()));
491             else {
492                 Run& lastRun = runs.last();
493                 lastRun.end = endPosition;
494                 lastRun.logicalRight += fragment.width();
495                 ASSERT(!lastRun.hasHyphen);
496                 lastRun.hasHyphen = fragment.hasHyphen();
497             }
498         }
499         m_runsWidth += fragment.width();
500         m_lastFragment = fragment;
501         if (m_fragments)
502             (*m_fragments).append(fragment);
503
504         if (fragment.type() == TextFragmentIterator::TextFragment::Whitespace)
505             m_trailingWhitespaceWidth += fragment.width();
506         else {
507             m_trailingWhitespaceWidth = 0;
508             m_lastNonWhitespaceFragment = fragment;
509         }
510
511         if (!m_firstCharacterFits)
512             m_firstCharacterFits = fragment.start() + 1 > endPosition || m_runsWidth <= m_availableWidth;
513     }
514
515     TextFragmentIterator::TextFragment revertToLastCompleteFragment(Layout::RunVector& runs)
516     {
517         if (!m_uncompletedWidth) {
518             ASSERT(m_lastFragment == m_lastCompleteFragment);
519             return m_lastFragment;
520         }
521         ASSERT(m_lastFragment.isValid());
522         m_runsWidth -= m_uncompletedWidth;
523         revertRuns(runs, endPositionForCollapsedFragment(m_lastCompleteFragment), m_uncompletedWidth);
524         m_uncompletedWidth = 0;
525         ASSERT(m_lastCompleteFragment.isValid());
526         return m_lastCompleteFragment;
527     }
528
529     void removeTrailingWhitespace(Layout::RunVector& runs)
530     {
531         if (m_lastFragment.type() != TextFragmentIterator::TextFragment::Whitespace || m_lastFragment.end() == m_lastNonWhitespaceFragment.end())
532             return;
533         revertRuns(runs, m_lastNonWhitespaceFragment.end(), m_trailingWhitespaceWidth);
534         m_runsWidth -= m_trailingWhitespaceWidth;
535         m_lastFragment = m_lastNonWhitespaceFragment;
536     }
537
538 private:
539     bool expansionOpportunity(TextFragmentIterator::TextFragment::Type currentFragmentType, TextFragmentIterator::TextFragment::Type previousFragmentType) const
540     {
541         return (currentFragmentType == TextFragmentIterator::TextFragment::Whitespace
542             || (currentFragmentType == TextFragmentIterator::TextFragment::NonWhitespace && previousFragmentType == TextFragmentIterator::TextFragment::NonWhitespace));
543     }
544
545     float m_availableWidth { 0 };
546     float m_logicalLeftOffset { 0 };
547     float m_runsWidth { 0 };
548     TextFragmentIterator::TextFragment m_overflowedFragment;
549     TextFragmentIterator::TextFragment m_lastFragment;
550     TextFragmentIterator::TextFragment m_lastNonWhitespaceFragment;
551     TextFragmentIterator::TextFragment m_lastCompleteFragment;
552     float m_uncompletedWidth { 0 };
553     float m_trailingWhitespaceWidth { 0 }; // Use this to remove trailing whitespace without re-mesuring the text.
554     float m_collapsedWhitespaceWidth { 0 };
555     // Having one character on the line does not necessarily mean it actually fits.
556     // First character of the first fragment might be forced on to the current line even if it does not fit.
557     bool m_firstCharacterFits { false };
558     std::optional<Vector<TextFragmentIterator::TextFragment, 30>> m_fragments;
559 };
560
561 class FragmentForwardIterator : public std::iterator<std::forward_iterator_tag, unsigned> {
562 public:
563     FragmentForwardIterator(unsigned fragmentIndex)
564         : m_fragmentIndex(fragmentIndex)
565     {
566     }
567
568     FragmentForwardIterator& operator++()
569     {
570         ++m_fragmentIndex;
571         return *this;
572     }
573
574     bool operator!=(const FragmentForwardIterator& other) const { return m_fragmentIndex != other.m_fragmentIndex; }
575     bool operator==(const FragmentForwardIterator& other) const { return m_fragmentIndex == other.m_fragmentIndex; }
576     unsigned operator*() const { return m_fragmentIndex; }
577
578 private:
579     unsigned m_fragmentIndex { 0 };
580 };
581
582 static FragmentForwardIterator begin(const TextFragmentIterator::TextFragment& fragment)  { return FragmentForwardIterator(fragment.start()); }
583 static FragmentForwardIterator end(const TextFragmentIterator::TextFragment& fragment)  { return FragmentForwardIterator(fragment.end()); }
584
585 static bool preWrap(const TextFragmentIterator::Style& style)
586 {
587     return style.wrapLines && !style.collapseWhitespace;
588 }
589     
590 static void removeTrailingWhitespace(LineState& lineState, Layout::RunVector& runs, const TextFragmentIterator& textFragmentIterator)
591 {
592     if (!lineState.hasTrailingWhitespace())
593         return;
594     // Remove collapsed whitespace, or non-collapsed pre-wrap whitespace, unless it's the only content on the line -so removing the whitesapce
595     // would produce an empty line.
596     const auto& style = textFragmentIterator.style();
597     bool collapseWhitespace = style.collapseWhitespace | preWrap(style);
598     if (!collapseWhitespace)
599         return;
600     if (preWrap(style) && lineState.isWhitespaceOnly())
601         return;
602     lineState.removeTrailingWhitespace(runs);
603 }
604
605 static void updateLineConstrains(const RenderBlockFlow& flow, LineState& line, const TextFragmentIterator::Style& style, bool isFirstLine)
606 {
607     bool shouldApplyTextIndent = !flow.isAnonymous() || flow.parent()->firstChild() == &flow;
608     LayoutUnit height = flow.logicalHeight();
609     line.setLogicalLeftOffset(flow.logicalLeftOffsetForLine(height, DoNotIndentText) + (shouldApplyTextIndent && isFirstLine ? flow.textIndentOffset() : LayoutUnit(0)));
610     float logicalRightOffset = flow.logicalRightOffsetForLine(height, DoNotIndentText);
611     line.setAvailableWidth(std::max<float>(0, logicalRightOffset - line.logicalLeftOffset()));
612     if (style.textAlign == JUSTIFY)
613         line.setNeedsAllFragments();
614 }
615
616 static std::optional<unsigned> hyphenPositionForFragment(unsigned splitPosition, TextFragmentIterator::TextFragment& fragmentToSplit,
617     const TextFragmentIterator& textFragmentIterator, float availableWidth)
618 {
619     auto& style = textFragmentIterator.style();
620     bool shouldHyphenate = style.shouldHyphenate && (!style.hyphenLimitLines || fragmentToSplit.wrappingWithHyphenCounter() < *style.hyphenLimitLines);
621     if (!shouldHyphenate)
622         return std::nullopt;
623
624     if (!enoughWidthForHyphenation(availableWidth, style.font.pixelSize()))
625         return std::nullopt;
626
627     // We might be able to fit the hyphen at the split position.
628     auto splitPositionWithHyphen = splitPosition;
629     // Find a splitting position where hyphen surely fits.
630     unsigned start = fragmentToSplit.start();
631     auto leftSideWidth = textFragmentIterator.textWidth(start, splitPosition, 0);
632     while (leftSideWidth + style.hyphenStringWidth > availableWidth) {
633         if (--splitPositionWithHyphen <= start)
634             return std::nullopt; // No space for hyphen.
635         leftSideWidth -= textFragmentIterator.textWidth(splitPositionWithHyphen, splitPositionWithHyphen + 1, 0);
636     }
637     ASSERT(splitPositionWithHyphen > start);
638     return textFragmentIterator.lastHyphenPosition(fragmentToSplit, splitPositionWithHyphen + 1);
639 }
640
641 static TextFragmentIterator::TextFragment splitFragmentToFitLine(TextFragmentIterator::TextFragment& fragmentToSplit, float availableWidth, bool keepAtLeastOneCharacter, const TextFragmentIterator& textFragmentIterator)
642 {
643     // FIXME: add surrogate pair support.
644     unsigned start = fragmentToSplit.start();
645     auto it = std::upper_bound(begin(fragmentToSplit), end(fragmentToSplit), availableWidth, [&textFragmentIterator, start](float availableWidth, unsigned index) {
646         // FIXME: use the actual left position of the line (instead of 0) to calculated width. It might give false width for tab characters.
647         return availableWidth < textFragmentIterator.textWidth(start, index + 1, 0);
648     });
649     unsigned splitPosition = (*it);
650     // Does first character fit this line?
651     if (splitPosition == start) {
652         if (keepAtLeastOneCharacter)
653             ++splitPosition;
654     } else if (auto hyphenPosition = hyphenPositionForFragment(splitPosition, fragmentToSplit, textFragmentIterator, availableWidth))
655         return fragmentToSplit.splitWithHyphen(*hyphenPosition, textFragmentIterator);
656     return fragmentToSplit.split(splitPosition, textFragmentIterator);
657 }
658
659 enum PreWrapLineBreakRule { Preserve, Ignore };
660
661 static TextFragmentIterator::TextFragment consumeLineBreakIfNeeded(const TextFragmentIterator::TextFragment& fragment, TextFragmentIterator& textFragmentIterator, LineState& line, Layout::RunVector& runs,
662     PreWrapLineBreakRule preWrapLineBreakRule = PreWrapLineBreakRule::Preserve)
663 {
664     if (!fragment.isLineBreak())
665         return fragment;
666
667     if (preWrap(textFragmentIterator.style()) && preWrapLineBreakRule != PreWrapLineBreakRule::Ignore)
668         return fragment;
669
670     // <br> always produces a run. (required by testing output)
671     if (fragment.type() == TextFragmentIterator::TextFragment::HardLineBreak)
672         line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
673     return textFragmentIterator.nextTextFragment();
674 }
675
676 static TextFragmentIterator::TextFragment skipWhitespaceIfNeeded(const TextFragmentIterator::TextFragment& fragment, TextFragmentIterator& textFragmentIterator)
677 {
678     if (!textFragmentIterator.style().collapseWhitespace)
679         return fragment;
680
681     TextFragmentIterator::TextFragment firstNonWhitespaceFragment = fragment;
682     while (firstNonWhitespaceFragment.type() == TextFragmentIterator::TextFragment::Whitespace)
683         firstNonWhitespaceFragment = textFragmentIterator.nextTextFragment();
684     return firstNonWhitespaceFragment;
685 }
686
687 static TextFragmentIterator::TextFragment firstFragment(TextFragmentIterator& textFragmentIterator, LineState& currentLine, const LineState& previousLine, Layout::RunVector& runs)
688 {
689     // Handle overflowed fragment from previous line.
690     TextFragmentIterator::TextFragment firstFragment(previousLine.overflowedFragment());
691
692     if (firstFragment.isEmpty())
693         firstFragment = textFragmentIterator.nextTextFragment();
694     else if (firstFragment.type() == TextFragmentIterator::TextFragment::Whitespace && preWrap(textFragmentIterator.style()) && previousLine.firstCharacterFits()) {
695         // 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.
696         firstFragment = textFragmentIterator.nextTextFragment();
697         // If skipping the whitespace puts us on a newline, skip the newline too as we already wrapped the line.
698         firstFragment = consumeLineBreakIfNeeded(firstFragment, textFragmentIterator, currentLine, runs, PreWrapLineBreakRule::Ignore);
699     }
700     return skipWhitespaceIfNeeded(firstFragment, textFragmentIterator);
701 }
702
703 static void forceFragmentToLine(LineState& line, TextFragmentIterator& textFragmentIterator, Layout::RunVector& runs, const TextFragmentIterator::TextFragment& fragment)
704 {
705     line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
706     // Check if there are more fragments to add to the current line.
707     auto nextFragment = textFragmentIterator.nextTextFragment();
708     if (fragment.overlapsToNextRenderer()) {
709         while (true) {
710             if (nextFragment.type() != fragment.type())
711                 break;
712             line.appendFragmentAndCreateRunIfNeeded(nextFragment, runs);
713             // Does it overlap to the next segment?
714             if (!nextFragment.overlapsToNextRenderer())
715                 return;
716             nextFragment = textFragmentIterator.nextTextFragment();
717         }
718     }
719     // 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.
720     nextFragment = skipWhitespaceIfNeeded(nextFragment, textFragmentIterator);
721     nextFragment = consumeLineBreakIfNeeded(nextFragment, textFragmentIterator, line, runs);
722     line.setOverflowedFragment(nextFragment);
723 }
724
725 static bool createLineRuns(LineState& line, const LineState& previousLine, Layout::RunVector& runs, TextFragmentIterator& textFragmentIterator)
726 {
727     const auto& style = textFragmentIterator.style();
728     line.setCollapedWhitespaceWidth(style.spaceWidth + style.wordSpacing);
729     bool lineCanBeWrapped = style.wrapLines || style.breakFirstWordOnOverflow || style.breakAnyWordOnOverflow;
730     auto fragment = firstFragment(textFragmentIterator, line, previousLine, runs);
731     while (fragment.type() != TextFragmentIterator::TextFragment::ContentEnd) {
732         // Hard linebreak.
733         if (fragment.isLineBreak()) {
734             // 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.)
735             if (line.isEmpty() || fragment.type() == TextFragmentIterator::TextFragment::HardLineBreak) {
736                 if (style.textAlign == RIGHT || style.textAlign == WEBKIT_RIGHT)
737                     line.removeTrailingWhitespace(runs);
738                 line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
739             }
740             break;
741         }
742         if (lineCanBeWrapped && !line.fits(fragment.width())) {
743             // Overflow wrapping behaviour:
744             // 1. Whitesapce collapse on: whitespace is skipped. Jump to next line.
745             // 2. Whitespace collapse off: whitespace is wrapped.
746             // 3. First, non-whitespace fragment is either wrapped or kept on the line. (depends on overflow-wrap)
747             // 5. Non-whitespace fragment when there's already another fragment on the line either gets wrapped (word-break: break-all)
748             // or gets pushed to the next line.
749             bool emptyLine = line.isEmpty();
750             // Whitespace fragment.
751             if (fragment.type() == TextFragmentIterator::TextFragment::Whitespace) {
752                 if (!style.collapseWhitespace) {
753                     // Split the fragment; (modified)fragment stays on this line, overflowedFragment is pushed to next line.
754                     line.setOverflowedFragment(splitFragmentToFitLine(fragment, line.availableWidth() - line.width(), emptyLine, textFragmentIterator));
755                     line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
756                 }
757                 // When whitespace collapse is on, whitespace that doesn't fit is simply skipped.
758                 break;
759             }
760             // Non-whitespace fragment. (!style.wrapLines: bug138102(preserve existing behavior)
761             if (((emptyLine && style.breakFirstWordOnOverflow) || style.breakAnyWordOnOverflow) || !style.wrapLines) {
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                 break;
766             }
767             ASSERT(fragment.type() == TextFragmentIterator::TextFragment::NonWhitespace);
768             // Find out if this non-whitespace fragment has a hyphen where we can break.
769             if (style.shouldHyphenate) {
770                 auto fragmentToSplit = fragment;
771                 // Split and check if we actually ended up with a hyphen.
772                 auto overflowFragment = splitFragmentToFitLine(fragmentToSplit, line.availableWidth() - line.width(), emptyLine, textFragmentIterator);
773                 if (fragmentToSplit.hasHyphen()) {
774                     line.setOverflowedFragment(overflowFragment);
775                     line.appendFragmentAndCreateRunIfNeeded(fragmentToSplit, runs);
776                     break;
777                 }
778                 // No hyphen, no split.
779             }
780             // Non-breakable non-whitespace first fragment. Add it to the current line. -it overflows though.
781             if (emptyLine) {
782                 forceFragmentToLine(line, textFragmentIterator, runs, fragment);
783                 break;
784             }
785             // Non-breakable non-whitespace fragment when there's already content on the line. Push it to the next line.
786             ASSERT(line.lastFragment().isValid());
787             if (line.lastFragment().overlapsToNextRenderer()) {
788                 // Check if this fragment is a continuation of a previous segment. In such cases, we need to remove them all.
789                 textFragmentIterator.revertToEndOfFragment(line.revertToLastCompleteFragment(runs));
790                 break;
791             }
792             line.setOverflowedFragment(fragment);
793             break;
794         }
795         line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
796         // Find the next text fragment.
797         fragment = textFragmentIterator.nextTextFragment(line.width());
798     }
799     return (fragment.type() == TextFragmentIterator::TextFragment::ContentEnd && line.overflowedFragment().isEmpty()) || line.overflowedFragment().type() == TextFragmentIterator::TextFragment::ContentEnd;
800 }
801
802 static ExpansionBehavior expansionBehavior(bool isAfterExpansion, bool lastRunOnLine)
803 {
804     ExpansionBehavior expansionBehavior;
805     expansionBehavior = isAfterExpansion ? ForbidLeadingExpansion : AllowLeadingExpansion;
806     expansionBehavior |= lastRunOnLine ? ForbidTrailingExpansion : AllowTrailingExpansion;
807     return expansionBehavior;
808 }
809
810 static void justifyRuns(const LineState& line, Layout::RunVector& runs, unsigned firstRunIndex)
811 {
812     ASSERT(runs.size());
813     auto widthToDistribute = line.availableWidth() - line.width();
814     if (widthToDistribute <= 0)
815         return;
816
817     auto lastRunIndex = runs.size() - 1;
818     ASSERT(firstRunIndex <= lastRunIndex);
819     Vector<std::pair<unsigned, ExpansionBehavior>> expansionOpportunityList;
820     unsigned expansionOpportunityCountOnThisLine = 0;
821     auto isAfterExpansion = true;
822     for (auto i = firstRunIndex; i <= lastRunIndex; ++i) {
823         const auto& run = runs.at(i);
824         unsigned opportunityCountInRun = 0;
825         std::tie(opportunityCountInRun, isAfterExpansion) = line.expansionOpportunityCount(run.start, run.end);
826         expansionOpportunityList.append(std::make_pair(opportunityCountInRun, expansionBehavior(isAfterExpansion, i == lastRunIndex)));
827         expansionOpportunityCountOnThisLine += opportunityCountInRun;
828     }
829     if (!expansionOpportunityCountOnThisLine)
830         return;
831
832     ASSERT(expansionOpportunityList.size() == lastRunIndex - firstRunIndex + 1);
833     auto expansion = widthToDistribute / expansionOpportunityCountOnThisLine;
834     float accumulatedExpansion = 0;
835     for (auto i = firstRunIndex; i <= lastRunIndex; ++i) {
836         auto& run = runs.at(i);
837         unsigned opportunityCountInRun;
838         std::tie(opportunityCountInRun, run.expansionBehavior) = expansionOpportunityList.at(i - firstRunIndex);
839         run.expansion = opportunityCountInRun * expansion;
840         run.logicalLeft += accumulatedExpansion;
841         run.logicalRight += (accumulatedExpansion + run.expansion);
842         accumulatedExpansion += run.expansion;
843     }
844 }
845
846 static ETextAlign textAlignForLine(const TextFragmentIterator::Style& style, bool lastLine)
847 {
848     // Fallback to LEFT (START) alignment for non-collapsable content and for the last line before a forced break or the end of the block.
849     auto textAlign = style.textAlign;
850     if (textAlign == JUSTIFY && (!style.collapseWhitespace || lastLine))
851         textAlign = LEFT;
852     return textAlign;
853 }
854
855 static void closeLineEndingAndAdjustRuns(LineState& line, Layout::RunVector& runs, std::optional<unsigned> lastRunIndexOfPreviousLine, unsigned& lineCount,
856     const TextFragmentIterator& textFragmentIterator, bool lastLineInFlow)
857 {
858     if (!runs.size() || (lastRunIndexOfPreviousLine && runs.size() - 1 == lastRunIndexOfPreviousLine.value()))
859         return;
860     removeTrailingWhitespace(line, runs, textFragmentIterator);
861     if (!runs.size())
862         return;
863     // Adjust runs' position by taking line's alignment into account.
864     const auto& style = textFragmentIterator.style();
865     auto firstRunIndex = lastRunIndexOfPreviousLine ? lastRunIndexOfPreviousLine.value() + 1 : 0;
866     auto lineLogicalLeft = line.logicalLeftOffset();
867     auto textAlign = textAlignForLine(style, lastLineInFlow || (line.lastFragment().isValid() && line.lastFragment().type() == TextFragmentIterator::TextFragment::HardLineBreak));
868     if (textAlign == JUSTIFY)
869         justifyRuns(line, runs, firstRunIndex);
870     else
871         lineLogicalLeft = computeLineLeft(textAlign, line.availableWidth(), line.width(), line.logicalLeftOffset());
872     for (auto i = firstRunIndex; i < runs.size(); ++i) {
873         runs[i].logicalLeft += lineLogicalLeft;
874         runs[i].logicalRight += lineLogicalLeft;
875     }
876     runs.last().isEndOfLine = true;
877     ++lineCount;
878 }
879
880 static void createTextRuns(Layout::RunVector& runs, RenderBlockFlow& flow, unsigned& lineCount)
881 {
882     LayoutUnit borderAndPaddingBefore = flow.borderAndPaddingBefore();
883     LayoutUnit lineHeight = lineHeightFromFlow(flow);
884     LineState line;
885     bool isEndOfContent = false;
886     TextFragmentIterator textFragmentIterator = TextFragmentIterator(flow);
887     std::optional<unsigned> lastRunIndexOfPreviousLine;
888     do {
889         flow.setLogicalHeight(lineHeight * lineCount + borderAndPaddingBefore);
890         LineState previousLine = line;
891         line = LineState();
892         updateLineConstrains(flow, line, textFragmentIterator.style(), !lineCount);
893         isEndOfContent = createLineRuns(line, previousLine, runs, textFragmentIterator);
894         closeLineEndingAndAdjustRuns(line, runs, lastRunIndexOfPreviousLine, lineCount, textFragmentIterator, isEndOfContent);
895         if (runs.size())
896             lastRunIndexOfPreviousLine = runs.size() - 1;
897     } while (!isEndOfContent);
898 }
899
900 std::unique_ptr<Layout> create(RenderBlockFlow& flow)
901 {
902     unsigned lineCount = 0;
903     Layout::RunVector runs;
904
905     createTextRuns(runs, flow, lineCount);
906     return Layout::create(runs, lineCount);
907 }
908
909 std::unique_ptr<Layout> Layout::create(const RunVector& runVector, unsigned lineCount)
910 {
911     void* slot = WTF::fastMalloc(sizeof(Layout) + sizeof(Run) * runVector.size());
912     return std::unique_ptr<Layout>(new (NotNull, slot) Layout(runVector, lineCount));
913 }
914
915 Layout::Layout(const RunVector& runVector, unsigned lineCount)
916     : m_lineCount(lineCount)
917     , m_runCount(runVector.size())
918 {
919     memcpy(m_runs, runVector.data(), m_runCount * sizeof(Run));
920 }
921
922 #ifndef NDEBUG
923 static void printReason(AvoidanceReason reason, TextStream& stream)
924 {
925     switch (reason) {
926     case FlowIsInsideRegion:
927         stream << "flow is inside region";
928         break;
929     case FlowHasHorizonalWritingMode:
930         stream << "horizontal writing mode";
931         break;
932     case FlowHasOutline:
933         stream << "outline";
934         break;
935     case FlowIsRuby:
936         stream << "ruby";
937         break;
938     case FlowHasHangingPunctuation:
939         stream << "hanging punctuation";
940         break;
941     case FlowIsPaginated:
942         stream << "paginated";
943         break;
944     case FlowHasTextOverflow:
945         stream << "text-overflow";
946         break;
947     case FlowIsDepricatedFlexBox:
948         stream << "depricatedFlexBox";
949         break;
950     case FlowParentIsPlaceholderElement:
951         stream << "placeholder element";
952         break;
953     case FlowParentIsTextAreaWithWrapping:
954         stream << "wrapping textarea";
955         break;
956     case FlowHasNonSupportedChild:
957         stream << "nested renderers";
958         break;
959     case FlowHasUnsupportedFloat:
960         stream << "complicated float";
961         break;
962     case FlowHasUnsupportedUnderlineDecoration:
963         stream << "text-underline-position: under";
964         break;
965     case FlowHasJustifiedNonLatinText:
966         stream << "text-align: justify with non-latin text";
967         break;
968     case FlowHasOverflowVisible:
969         stream << "overflow: visible";
970         break;
971     case FlowHasWebKitNBSPMode:
972         stream << "-webkit-nbsp-mode: space";
973         break;
974     case FlowIsNotLTR:
975         stream << "dir is not LTR";
976         break;
977     case FlowHasLineBoxContainProperty:
978         stream << "line-box-contain value indicates variable line height";
979         break;
980     case FlowIsNotTopToBottom:
981         stream << "non top-to-bottom flow";
982         break;
983     case FlowHasLineBreak:
984         stream << "line-break property";
985         break;
986     case FlowHasNonNormalUnicodeBiDi:
987         stream << "non-normal Unicode bidi";
988         break;
989     case FlowHasRTLOrdering:
990         stream << "-webkit-rtl-ordering";
991         break;
992     case FlowHasLineAlignEdges:
993         stream << "-webkit-line-align edges";
994         break;
995     case FlowHasLineSnap:
996         stream << "-webkit-line-snap property";
997         break;
998     case FlowHasTextEmphasisFillOrMark:
999         stream << "text-emphasis (fill/mark)";
1000         break;
1001     case FlowHasPseudoFirstLine:
1002         stream << "first-line";
1003         break;
1004     case FlowHasPseudoFirstLetter:
1005         stream << "first-letter";
1006         break;
1007     case FlowHasTextCombine:
1008         stream << "text combine";
1009         break;
1010     case FlowHasTextFillBox:
1011         stream << "background-color (text-fill)";
1012         break;
1013     case FlowHasBorderFitLines:
1014         stream << "-webkit-border-fit";
1015         break;
1016     case FlowHasNonAutoLineBreak:
1017         stream << "line-break is not auto";
1018         break;
1019     case FlowHasNonAutoTrailingWord:
1020         stream << "-apple-trailing-word is not auto";
1021         break;
1022     case FlowHasSVGFont:
1023         stream << "SVG font";
1024         break;
1025     case FlowTextHasSoftHyphen:
1026         stream << "soft hyphen character";
1027         break;
1028     case FlowTextHasDirectionCharacter:
1029         stream << "direction character";
1030         break;
1031     case FlowIsMissingPrimaryFont:
1032         stream << "missing primary font";
1033         break;
1034     case FlowFontIsMissingGlyph:
1035         stream << "missing glyph";
1036         break;
1037     case FlowTextIsCombineText:
1038         stream << "text is combine";
1039         break;
1040     case FlowTextIsRenderCounter:
1041         stream << "unsupported RenderCounter";
1042         break;
1043     case FlowTextIsRenderQuote:
1044         stream << "unsupported RenderQuote";
1045         break;
1046     case FlowTextIsTextFragment:
1047         stream << "unsupported TextFragment";
1048         break;
1049     case FlowTextIsSVGInlineText:
1050         stream << "unsupported SVGInlineText";
1051         break;
1052     case FlowFontIsNotSimple:
1053         stream << "complext font";
1054         break;
1055     case FlowHasTextShadow:
1056         stream << "text-shadow";
1057         break;
1058     case FlowChildIsSelected:
1059         stream << "selected content";
1060         break;
1061     case FlowFontHasOverflowGlyph:
1062         stream << "-webkit-line-box-contain: glyphs with overflowing text.";
1063         break;
1064     case FlowTextIsEmpty:
1065     case FlowHasNoChild:
1066     case FlowHasNoParent:
1067     case FeatureIsDisabled:
1068     default:
1069         break;
1070     }
1071 }
1072
1073 static void printReasons(AvoidanceReasonFlags reasons, TextStream& stream)
1074 {
1075     bool first = true;
1076     for (auto reasonItem = EndOfReasons >> 1; reasonItem != NoReason; reasonItem >>= 1) {
1077         if (!(reasons & reasonItem))
1078             continue;
1079         stream << (first ? " " : ", ");
1080         first = false;
1081         printReason(reasonItem, stream);
1082     }
1083 }
1084
1085 static void printTextForSubtree(const RenderObject& renderer, unsigned& charactersLeft, TextStream& stream)
1086 {
1087     if (!charactersLeft)
1088         return;
1089     if (is<RenderText>(renderer)) {
1090         String text = downcast<RenderText>(renderer).text();
1091         text = text.stripWhiteSpace();
1092         unsigned len = std::min(charactersLeft, text.length());
1093         stream << text.left(len);
1094         charactersLeft -= len;
1095         return;
1096     }
1097     if (!is<RenderElement>(renderer))
1098         return;
1099     for (const auto* child = downcast<RenderElement>(renderer).firstChild(); child; child = child->nextSibling())
1100         printTextForSubtree(*child, charactersLeft, stream);
1101 }
1102
1103 static unsigned textLengthForSubtree(const RenderObject& renderer)
1104 {
1105     if (is<RenderText>(renderer))
1106         return downcast<RenderText>(renderer).textLength();
1107     if (!is<RenderElement>(renderer))
1108         return 0;
1109     unsigned textLength = 0;
1110     for (const auto* child = downcast<RenderElement>(renderer).firstChild(); child; child = child->nextSibling())
1111         textLength += textLengthForSubtree(*child);
1112     return textLength;
1113 }
1114
1115 static void collectNonEmptyLeafRenderBlockFlows(const RenderObject& renderer, HashSet<const RenderBlockFlow*>& leafRenderers)
1116 {
1117     if (is<RenderText>(renderer)) {
1118         if (!downcast<RenderText>(renderer).textLength())
1119             return;
1120         // Find RenderBlockFlow ancestor.
1121         for (const auto* current = renderer.parent(); current; current = current->parent()) {
1122             if (!is<RenderBlockFlow>(current))
1123                 continue;
1124             leafRenderers.add(downcast<RenderBlockFlow>(current));
1125             break;
1126         }
1127         return;
1128     }
1129     if (!is<RenderElement>(renderer))
1130         return;
1131     for (const auto* child = downcast<RenderElement>(renderer).firstChild(); child; child = child->nextSibling())
1132         collectNonEmptyLeafRenderBlockFlows(*child, leafRenderers);
1133 }
1134
1135 static void collectNonEmptyLeafRenderBlockFlowsForCurrentPage(HashSet<const RenderBlockFlow*>& leafRenderers)
1136 {
1137     for (const auto* document : Document::allDocuments()) {
1138         if (!document->renderView() || document->pageCacheState() != Document::NotInPageCache)
1139             continue;
1140         if (!document->isHTMLDocument() && !document->isXHTMLDocument())
1141             continue;
1142         collectNonEmptyLeafRenderBlockFlows(*document->renderView(), leafRenderers);
1143     }
1144 }
1145
1146 void toggleSimpleLineLayout()
1147 {
1148     for (const auto* document : Document::allDocuments()) {
1149         auto* settings = document->settings();
1150         if (!settings)
1151             continue;
1152         settings->setSimpleLineLayoutEnabled(!settings->simpleLineLayoutEnabled());
1153     }
1154 }
1155
1156 void printSimpleLineLayoutBlockList()
1157 {
1158     HashSet<const RenderBlockFlow*> leafRenderers;
1159     collectNonEmptyLeafRenderBlockFlowsForCurrentPage(leafRenderers);
1160     if (!leafRenderers.size()) {
1161         WTFLogAlways("No text found in this document\n");
1162         return;
1163     }
1164     TextStream stream;
1165     stream << "---------------------------------------------------\n";
1166     for (const auto* flow : leafRenderers) {
1167         auto reason = canUseForWithReason(*flow, IncludeReasons::All);
1168         if (reason == NoReason)
1169             continue;
1170         unsigned printedLength = 30;
1171         stream << "\"";
1172         printTextForSubtree(*flow, printedLength, stream);
1173         for (;printedLength > 0; --printedLength)
1174             stream << " ";
1175         stream << "\"(" << textLengthForSubtree(*flow) << "):";
1176         printReasons(reason, stream);
1177         stream << "\n";
1178     }
1179     stream << "---------------------------------------------------\n";
1180     WTFLogAlways("%s", stream.release().utf8().data());
1181 }
1182
1183 void printSimpleLineLayoutCoverage()
1184 {
1185     HashSet<const RenderBlockFlow*> leafRenderers;
1186     collectNonEmptyLeafRenderBlockFlowsForCurrentPage(leafRenderers);
1187     if (!leafRenderers.size()) {
1188         WTFLogAlways("No text found in this document\n");
1189         return;
1190     }
1191     TextStream stream;
1192     HashMap<AvoidanceReason, unsigned> flowStatistics;
1193     unsigned textLength = 0;
1194     unsigned unsupportedTextLength = 0;
1195     unsigned numberOfUnsupportedLeafBlocks = 0;
1196     for (const auto* flow : leafRenderers) {
1197         auto flowLength = textLengthForSubtree(*flow);
1198         textLength += flowLength;
1199         auto reasons = canUseForWithReason(*flow, IncludeReasons::All);
1200         if (reasons == NoReason)
1201             continue;
1202         ++numberOfUnsupportedLeafBlocks;
1203         unsupportedTextLength += flowLength;
1204         for (auto reasonItem = EndOfReasons >> 1; reasonItem != NoReason; reasonItem >>= 1) {
1205             if (!(reasons & reasonItem))
1206                 continue;
1207             auto result = flowStatistics.add(reasonItem, flowLength);
1208             if (!result.isNewEntry)
1209                 result.iterator->value += flowLength;
1210         }
1211     }
1212     stream << "---------------------------------------------------\n";
1213     stream << "Number of text blocks: total(" <<  leafRenderers.size() << ") non-simple(" << numberOfUnsupportedLeafBlocks << ")\nText length: total(" <<
1214         textLength << ") non-simple(" << unsupportedTextLength << ")\n";
1215     for (const auto reasonEntry : flowStatistics) {
1216         printReason(reasonEntry.key, stream);
1217         stream << ": " << (float)reasonEntry.value / (float)textLength * 100 << "%\n";
1218     }
1219     stream << "simple line layout coverage: " << (float)(textLength - unsupportedTextLength) / (float)textLength * 100 << "%\n";
1220     stream << "---------------------------------------------------\n";
1221     WTFLogAlways("%s", stream.release().utf8().data());
1222 }
1223 #endif
1224 }
1225 }