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