Simple line layout: Extend coverage for justified content.
[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 "InlineTextBox.h"
37 #include "LineWidth.h"
38 #include "Logging.h"
39 #include "PaintInfo.h"
40 #include "RenderBlockFlow.h"
41 #include "RenderChildIterator.h"
42 #include "RenderLineBreak.h"
43 #include "RenderStyle.h"
44 #include "RenderText.h"
45 #include "RenderTextControl.h"
46 #include "RenderView.h"
47 #include "Settings.h"
48 #include "SimpleLineLayoutFlowContents.h"
49 #include "SimpleLineLayoutFunctions.h"
50 #include "SimpleLineLayoutTextFragmentIterator.h"
51 #include "Text.h"
52 #include "TextPaintStyle.h"
53 #include "TextStream.h"
54
55 namespace WebCore {
56 namespace SimpleLineLayout {
57
58 #ifndef NDEBUG
59 void printSimpleLineLayoutCoverage();
60 void printSimpleLineLayoutBlockList();
61 void toggleSimpleLineLayout();
62 #endif
63
64 enum AvoidanceReason_ : uint64_t {
65     FlowIsInsideRegion                    = 1LLU  << 0,
66     FlowHasHorizonalWritingMode           = 1LLU  << 1,
67     FlowHasOutline                        = 1LLU  << 2,
68     FlowIsRuby                            = 1LLU  << 3,
69     FlowIsPaginated                       = 1LLU  << 4,
70     FlowHasTextOverflow                   = 1LLU  << 5,
71     FlowIsDepricatedFlexBox               = 1LLU  << 6,
72     FlowParentIsPlaceholderElement        = 1LLU  << 7,
73     FlowParentIsTextAreaWithWrapping      = 1LLU  << 8,
74     FlowHasNonSupportedChild              = 1LLU  << 9,
75     FlowHasUnsupportedFloat               = 1LLU  << 10,
76     FlowHasUnsupportedUnderlineDecoration = 1LLU  << 11,
77     FlowHasJustifiedNonLatinText          = 1LLU  << 12,
78     FlowHasOverflowVisible                = 1LLU  << 13,
79     FlowIsNotLTR                          = 1LLU  << 14,
80     FlowHasLineBoxContainProperty         = 1LLU  << 15,
81     FlowIsNotTopToBottom                  = 1LLU  << 16,
82     FlowHasLineBreak                      = 1LLU  << 17,
83     FlowHasNonNormalUnicodeBiDi           = 1LLU  << 18,
84     FlowHasRTLOrdering                    = 1LLU  << 19,
85     FlowHasLineAlignEdges                 = 1LLU  << 20,
86     FlowHasLineSnap                       = 1LLU  << 21,
87     FlowHasHypensAuto                     = 1LLU  << 22,
88     FlowHasTextEmphasisFillOrMark         = 1LLU  << 23,
89     FlowHasTextShadow                     = 1LLU  << 24,
90     FlowHasPseudoFirstLine                = 1LLU  << 25,
91     FlowHasPseudoFirstLetter              = 1LLU  << 26,
92     FlowHasTextCombine                    = 1LLU  << 27,
93     FlowHasTextFillBox                    = 1LLU  << 28,
94     FlowHasBorderFitLines                 = 1LLU  << 29,
95     FlowHasNonAutoLineBreak               = 1LLU  << 30,
96     FlowHasNonAutoTrailingWord            = 1LLU  << 31,
97     FlowHasSVGFont                        = 1LLU  << 32,
98     FlowTextIsEmpty                       = 1LLU  << 33,
99     FlowTextHasNoBreakSpace               = 1LLU  << 34,
100     FlowTextHasSoftHyphen                 = 1LLU  << 35,
101     FlowTextHasDirectionCharacter         = 1LLU  << 36,
102     FlowIsMissingPrimaryFont              = 1LLU  << 37,
103     FlowFontIsMissingGlyph                = 1LLU  << 38,
104     FlowTextIsCombineText                 = 1LLU  << 39,
105     FlowTextIsRenderCounter               = 1LLU  << 40,
106     FlowTextIsRenderQuote                 = 1LLU  << 41,
107     FlowTextIsTextFragment                = 1LLU  << 42,
108     FlowTextIsSVGInlineText               = 1LLU  << 43,
109     FlowFontIsNotSimple                   = 1LLU  << 44,
110     FeatureIsDisabled                     = 1LLU  << 45,
111     FlowHasNoParent                       = 1LLU  << 46,
112     FlowHasNoChild                        = 1LLU  << 47,
113     FlowChildIsSelected                   = 1LLU  << 48,
114     FlowHasHangingPunctuation             = 1LLU  << 49,
115     EndOfReasons                          = 1LLU  << 50
116 };
117 const unsigned NoReason = 0;
118
119 typedef uint64_t AvoidanceReason;
120 typedef uint64_t AvoidanceReasonFlags;
121
122 enum class IncludeReasons { First , All };
123
124 #ifndef NDEBUG
125 #define SET_REASON_AND_RETURN_IF_NEEDED(reason, reasons, includeReasons) { \
126         reasons |= reason; \
127         if (includeReasons == IncludeReasons::First) \
128             return reasons; \
129     }
130 #else
131 #define SET_REASON_AND_RETURN_IF_NEEDED(reason, reasons, includeReasons) { \
132         ASSERT_UNUSED(includeReasons, includeReasons == IncludeReasons::First); \
133         reasons |= reason; \
134         return reasons; \
135     }
136 #endif
137
138 template <typename CharacterType>
139 static AvoidanceReasonFlags canUseForText(const CharacterType* text, unsigned length, const Font& font, bool textIsJustified, IncludeReasons includeReasons)
140 {
141     AvoidanceReasonFlags reasons = { };
142     // FIXME: <textarea maxlength=0> generates empty text node.
143     if (!length)
144         SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsEmpty, reasons, includeReasons);
145
146     for (unsigned i = 0; i < length; ++i) {
147         UChar character = text[i];
148         if (character == ' ')
149             continue;
150
151         if (textIsJustified) {
152             // Include characters up to Latin Extended-B and some punctuation range when text is justified.
153             bool isLatinIncludingExtendedB = character <= 0x01FF;
154             bool isPunctuationRange = character >= 0x2010 && character <= 0x2027;
155             if (!(isLatinIncludingExtendedB || isPunctuationRange))
156                 SET_REASON_AND_RETURN_IF_NEEDED(FlowHasJustifiedNonLatinText, reasons, includeReasons);
157         }
158
159         // These would be easy to support.
160         if (character == noBreakSpace)
161             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextHasNoBreakSpace, reasons, includeReasons);
162         if (character == softHyphen)
163             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextHasSoftHyphen, reasons, includeReasons);
164
165         UCharDirection direction = u_charDirection(character);
166         if (direction == U_RIGHT_TO_LEFT || direction == U_RIGHT_TO_LEFT_ARABIC
167             || direction == U_RIGHT_TO_LEFT_EMBEDDING || direction == U_RIGHT_TO_LEFT_OVERRIDE
168             || direction == U_LEFT_TO_RIGHT_EMBEDDING || direction == U_LEFT_TO_RIGHT_OVERRIDE
169             || direction == U_POP_DIRECTIONAL_FORMAT || direction == U_BOUNDARY_NEUTRAL)
170             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextHasDirectionCharacter, reasons, includeReasons);
171
172         if (!font.glyphForCharacter(character))
173             SET_REASON_AND_RETURN_IF_NEEDED(FlowFontIsMissingGlyph, reasons, includeReasons);
174     }
175     return reasons;
176 }
177
178 static AvoidanceReasonFlags canUseForText(const RenderText& textRenderer, const Font& font, bool textIsJustified, IncludeReasons includeReasons)
179 {
180     if (textRenderer.is8Bit())
181         return canUseForText(textRenderer.characters8(), textRenderer.textLength(), font, false, includeReasons);
182     return canUseForText(textRenderer.characters16(), textRenderer.textLength(), font, textIsJustified, includeReasons);
183 }
184
185 static AvoidanceReasonFlags canUseForFontAndText(const RenderBlockFlow& flow, IncludeReasons includeReasons)
186 {
187     AvoidanceReasonFlags reasons = { };
188     // We assume that all lines have metrics based purely on the primary font.
189     const auto& style = flow.style();
190     auto& primaryFont = style.fontCascade().primaryFont();
191     if (primaryFont.isLoading())
192         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsMissingPrimaryFont, reasons, includeReasons);
193
194     bool flowIsJustified = style.textAlign() == JUSTIFY;
195     for (const auto& textRenderer : childrenOfType<RenderText>(flow)) {
196         if (textRenderer.isCombineText())
197             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsCombineText, reasons, includeReasons);
198         if (textRenderer.isCounter())
199             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsRenderCounter, reasons, includeReasons);
200         if (textRenderer.isQuote())
201             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsRenderQuote, reasons, includeReasons);
202         if (textRenderer.isTextFragment())
203             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsTextFragment, reasons, includeReasons);
204         if (textRenderer.isSVGInlineText())
205             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsSVGInlineText, reasons, includeReasons);
206         if (style.fontCascade().codePath(TextRun(textRenderer.text())) != FontCascade::Simple)
207             SET_REASON_AND_RETURN_IF_NEEDED(FlowFontIsNotSimple, reasons, includeReasons);
208
209         auto textReasons = canUseForText(textRenderer, primaryFont, flowIsJustified, includeReasons);
210         if (textReasons != NoReason)
211             SET_REASON_AND_RETURN_IF_NEEDED(textReasons, reasons, includeReasons);
212     }
213     return reasons;
214 }
215
216 static AvoidanceReasonFlags canUseForStyle(const RenderStyle& style, IncludeReasons includeReasons)
217 {
218     AvoidanceReasonFlags reasons = { };
219     if (style.textOverflow())
220         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextOverflow, reasons, includeReasons);
221     if ((style.textDecorationsInEffect() & TextDecorationUnderline) && style.textUnderlinePosition() == TextUnderlinePositionUnder)
222         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasUnsupportedUnderlineDecoration, reasons, includeReasons);
223     // Non-visible overflow should be pretty easy to support.
224     if (style.overflowX() != OVISIBLE || style.overflowY() != OVISIBLE)
225         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasOverflowVisible, reasons, includeReasons);
226     if (!style.isLeftToRightDirection())
227         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsNotLTR, reasons, includeReasons);
228     if (style.lineBoxContain() != RenderStyle::initialLineBoxContain())
229         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasLineBoxContainProperty, reasons, includeReasons);
230     if (style.writingMode() != TopToBottomWritingMode)
231         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsNotTopToBottom, reasons, includeReasons);
232     if (style.lineBreak() != LineBreakAuto)
233         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasLineBreak, reasons, includeReasons);
234     if (style.unicodeBidi() != UBNormal)
235         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasNonNormalUnicodeBiDi, reasons, includeReasons);
236     if (style.rtlOrdering() != LogicalOrder)
237         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasRTLOrdering, reasons, includeReasons);
238     if (style.lineAlign() != LineAlignNone)
239         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasLineAlignEdges, reasons, includeReasons);
240     if (style.lineSnap() != LineSnapNone)
241         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasLineSnap, reasons, includeReasons);
242     if (style.hyphens() == HyphensAuto)
243         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasHypensAuto, reasons, includeReasons);
244     if (style.textEmphasisFill() != TextEmphasisFillFilled || style.textEmphasisMark() != TextEmphasisMarkNone)
245         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextEmphasisFillOrMark, reasons, includeReasons);
246     if (style.textShadow())
247         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextShadow, reasons, includeReasons);
248     if (style.hasPseudoStyle(FIRST_LINE))
249         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasPseudoFirstLine, reasons, includeReasons);
250     if (style.hasPseudoStyle(FIRST_LETTER))
251         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasPseudoFirstLetter, reasons, includeReasons);
252     if (style.hasTextCombine())
253         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextCombine, reasons, includeReasons);
254     if (style.backgroundClip() == TextFillBox)
255         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextFillBox, reasons, includeReasons);
256     if (style.borderFit() == BorderFitLines)
257         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasBorderFitLines, reasons, includeReasons);
258     if (style.lineBreak() != LineBreakAuto)
259         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasNonAutoLineBreak, 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));
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));
475             else {
476                 Run& lastRun = runs.last();
477                 lastRun.end = endPosition;
478                 lastRun.logicalRight += fragment.width();
479             }
480         }
481         m_fragments.append(fragment);
482         m_runsWidth += fragment.width();
483
484         if (fragment.type() == TextFragmentIterator::TextFragment::Whitespace) {
485             m_trailingWhitespaceLength += endPosition - fragment.start();
486             m_trailingWhitespaceWidth += fragment.width();
487         } else {
488             m_trailingWhitespaceLength = 0;
489             m_trailingWhitespaceWidth = 0;
490         }
491
492         if (!m_firstCharacterFits)
493             m_firstCharacterFits = fragment.start() + 1 > endPosition || m_runsWidth <= m_availableWidth;
494     }
495
496     TextFragmentIterator::TextFragment revertToLastCompleteFragment(Layout::RunVector& runs)
497     {
498         ASSERT(m_fragments.size());
499         unsigned revertLength = 0;
500         float revertWidth = 0;
501         while (m_fragments.size()) {
502             const auto& current = m_fragments.last();
503             if (current == m_lastCompleteFragment)
504                 break;
505             revertLength += current.end() - current.start();
506             revertWidth += current.width();
507             m_fragments.removeLast();
508         }
509         m_runsWidth -= revertWidth;
510         if (revertLength)
511             revertRuns(runs, revertLength, revertWidth);
512         return m_lastCompleteFragment;
513     }
514
515     void removeTrailingWhitespace(Layout::RunVector& runs)
516     {
517         if (!m_trailingWhitespaceLength)
518             return;
519         revertRuns(runs, m_trailingWhitespaceLength, m_trailingWhitespaceWidth);
520         m_runsWidth -= m_trailingWhitespaceWidth;
521         ASSERT(m_fragments.last().type() == TextFragmentIterator::TextFragment::Whitespace);
522         while (m_fragments.size()) {
523             const auto& current = m_fragments.last();
524             if (current.type() != TextFragmentIterator::TextFragment::Whitespace)
525                 break;
526 #if !ASSERT_DISABLED
527             m_trailingWhitespaceLength -= (current.isCollapsed() ? 1 : current.end() - current.start());
528             m_trailingWhitespaceWidth -= current.width();
529 #endif
530             m_fragments.removeLast();
531         }
532 #if !ASSERT_DISABLED
533         ASSERT(!m_trailingWhitespaceLength);
534         ASSERT(!m_trailingWhitespaceWidth);
535 #endif
536         m_trailingWhitespaceLength = 0;
537         m_trailingWhitespaceWidth = 0;
538     }
539
540 private:
541     bool expansionOpportunity(TextFragmentIterator::TextFragment::Type currentFragmentType, TextFragmentIterator::TextFragment::Type previousFragmentType) const
542     {
543         return (currentFragmentType == TextFragmentIterator::TextFragment::Whitespace
544             || (currentFragmentType == TextFragmentIterator::TextFragment::NonWhitespace && previousFragmentType == TextFragmentIterator::TextFragment::NonWhitespace));
545     }
546
547     float m_availableWidth { 0 };
548     float m_logicalLeftOffset { 0 };
549     TextFragmentIterator::TextFragment m_overflowedFragment;
550     float m_runsWidth { 0 };
551     TextFragmentIterator::TextFragment m_lastCompleteFragment;
552     float m_trailingWhitespaceWidth { 0 }; // Use this to remove trailing whitespace without re-mesuring the text.
553     unsigned m_trailingWhitespaceLength { 0 };
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     Vector<TextFragmentIterator::TextFragment> 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
595     // 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.
596     const auto& style = textFragmentIterator.style();
597     bool collapseWhitespace = style.collapseWhitespace | preWrap(style);
598     if (!collapseWhitespace)
599         return;
600
601     if (preWrap(style) && lineState.isWhitespaceOnly())
602         return;
603
604     lineState.removeTrailingWhitespace(runs);
605 }
606
607 static void updateLineConstrains(const RenderBlockFlow& flow, LineState& line, bool isFirstLine)
608 {
609     bool shouldApplyTextIndent = !flow.isAnonymous() || flow.parent()->firstChild() == &flow;
610     LayoutUnit height = flow.logicalHeight();
611     LayoutUnit logicalHeight = flow.minLineHeightForReplacedRenderer(false, 0);
612     float logicalRightOffset = flow.logicalRightOffsetForLine(height, DoNotIndentText, logicalHeight);
613     line.setLogicalLeftOffset(flow.logicalLeftOffsetForLine(height, DoNotIndentText, logicalHeight) +
614         (shouldApplyTextIndent && isFirstLine ? flow.textIndentOffset() : LayoutUnit(0)));
615     line.setAvailableWidth(std::max<float>(0, logicalRightOffset - line.logicalLeftOffset()));
616 }
617
618 static TextFragmentIterator::TextFragment splitFragmentToFitLine(TextFragmentIterator::TextFragment& fragmentToSplit, float availableWidth, bool keepAtLeastOneCharacter, const TextFragmentIterator& textFragmentIterator)
619 {
620     // FIXME: add surrogate pair support.
621     unsigned start = fragmentToSplit.start();
622     auto it = std::upper_bound(begin(fragmentToSplit), end(fragmentToSplit), availableWidth, [&textFragmentIterator, start](float availableWidth, unsigned index) {
623         // FIXME: use the actual left position of the line (instead of 0) to calculated width. It might give false width for tab characters.
624         return availableWidth < textFragmentIterator.textWidth(start, index + 1, 0);
625     });
626     unsigned splitPosition = (*it);
627     if (keepAtLeastOneCharacter && splitPosition == fragmentToSplit.start())
628         ++splitPosition;
629     return fragmentToSplit.split(splitPosition, textFragmentIterator);
630 }
631
632 enum PreWrapLineBreakRule { Preserve, Ignore };
633
634 static TextFragmentIterator::TextFragment consumeLineBreakIfNeeded(const TextFragmentIterator::TextFragment& fragment, TextFragmentIterator& textFragmentIterator, LineState& line, Layout::RunVector& runs,
635     PreWrapLineBreakRule preWrapLineBreakRule = PreWrapLineBreakRule::Preserve)
636 {
637     if (!fragment.isLineBreak())
638         return fragment;
639
640     if (preWrap(textFragmentIterator.style()) && preWrapLineBreakRule != PreWrapLineBreakRule::Ignore)
641         return fragment;
642
643     // <br> always produces a run. (required by testing output)
644     if (fragment.type() == TextFragmentIterator::TextFragment::HardLineBreak)
645         line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
646     return textFragmentIterator.nextTextFragment();
647 }
648
649 static TextFragmentIterator::TextFragment skipWhitespaceIfNeeded(const TextFragmentIterator::TextFragment& fragment, TextFragmentIterator& textFragmentIterator)
650 {
651     if (!textFragmentIterator.style().collapseWhitespace)
652         return fragment;
653
654     TextFragmentIterator::TextFragment firstNonWhitespaceFragment = fragment;
655     while (firstNonWhitespaceFragment.type() == TextFragmentIterator::TextFragment::Whitespace)
656         firstNonWhitespaceFragment = textFragmentIterator.nextTextFragment();
657     return firstNonWhitespaceFragment;
658 }
659
660 static TextFragmentIterator::TextFragment firstFragment(TextFragmentIterator& textFragmentIterator, LineState& currentLine, const LineState& previousLine, Layout::RunVector& runs)
661 {
662     // Handle overflowed fragment from previous line.
663     TextFragmentIterator::TextFragment firstFragment(previousLine.overflowedFragment());
664
665     if (firstFragment.isEmpty())
666         firstFragment = textFragmentIterator.nextTextFragment();
667     else if (firstFragment.type() == TextFragmentIterator::TextFragment::Whitespace && preWrap(textFragmentIterator.style()) && previousLine.firstCharacterFits()) {
668         // 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.
669         firstFragment = textFragmentIterator.nextTextFragment();
670         // If skipping the whitespace puts us on a newline, skip the newline too as we already wrapped the line.
671         firstFragment = consumeLineBreakIfNeeded(firstFragment, textFragmentIterator, currentLine, runs, PreWrapLineBreakRule::Ignore);
672     }
673     return skipWhitespaceIfNeeded(firstFragment, textFragmentIterator);
674 }
675
676 static void forceFragmentToLine(LineState& line, TextFragmentIterator& textFragmentIterator, Layout::RunVector& runs, const TextFragmentIterator::TextFragment& fragment)
677 {
678     line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
679     // Check if there are more fragments to add to the current line.
680     auto nextFragment = textFragmentIterator.nextTextFragment();
681     if (fragment.overlapsToNextRenderer()) {
682         while (true) {
683             if (nextFragment.type() != fragment.type())
684                 break;
685             line.appendFragmentAndCreateRunIfNeeded(nextFragment, runs);
686             // Does it overlap to the next segment?
687             if (!nextFragment.overlapsToNextRenderer())
688                 return;
689             nextFragment = textFragmentIterator.nextTextFragment();
690         }
691     }
692     // 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.
693     nextFragment = skipWhitespaceIfNeeded(nextFragment, textFragmentIterator);
694     nextFragment = consumeLineBreakIfNeeded(nextFragment, textFragmentIterator, line, runs);
695     line.setOverflowedFragment(nextFragment);
696 }
697
698 static bool createLineRuns(LineState& line, const LineState& previousLine, Layout::RunVector& runs, TextFragmentIterator& textFragmentIterator)
699 {
700     const auto& style = textFragmentIterator.style();
701     line.setCollapedWhitespaceWidth(style.spaceWidth + style.wordSpacing);
702     bool lineCanBeWrapped = style.wrapLines || style.breakFirstWordOnOverflow || style.breakAnyWordOnOverflow;
703     auto fragment = firstFragment(textFragmentIterator, line, previousLine, runs);
704     while (fragment.type() != TextFragmentIterator::TextFragment::ContentEnd) {
705         // Hard linebreak.
706         if (fragment.isLineBreak()) {
707             // 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.)
708             if (line.isEmpty() || fragment.type() == TextFragmentIterator::TextFragment::HardLineBreak) {
709                 if (style.textAlign == RIGHT || style.textAlign == WEBKIT_RIGHT)
710                     line.removeTrailingWhitespace(runs);
711                 line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
712             }
713             break;
714         }
715         if (lineCanBeWrapped && !line.fits(fragment.width())) {
716             // Overflow wrapping behaviour:
717             // 1. Whitesapce collapse on: whitespace is skipped. Jump to next line.
718             // 2. Whitespace collapse off: whitespace is wrapped.
719             // 3. First, non-whitespace fragment is either wrapped or kept on the line. (depends on overflow-wrap)
720             // 5. Non-whitespace fragment when there's already another fragment on the line either gets wrapped (word-break: break-all)
721             // or gets pushed to the next line.
722             bool emptyLine = line.isEmpty();
723             // Whitespace fragment.
724             if (fragment.type() == TextFragmentIterator::TextFragment::Whitespace) {
725                 if (!style.collapseWhitespace) {
726                     // Split the fragment; (modified)fragment stays on this line, overflowedFragment is pushed to next line.
727                     line.setOverflowedFragment(splitFragmentToFitLine(fragment, line.availableWidth() - line.width(), emptyLine, textFragmentIterator));
728                     line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
729                 }
730                 // When whitespace collapse is on, whitespace that doesn't fit is simply skipped.
731                 break;
732             }
733             // Non-whitespace fragment. (!style.wrapLines: bug138102(preserve existing behavior)
734             if (((emptyLine && style.breakFirstWordOnOverflow) || style.breakAnyWordOnOverflow) || !style.wrapLines) {
735                 // Split the fragment; (modified)fragment stays on this line, overflowedFragment is pushed to next line.
736                 line.setOverflowedFragment(splitFragmentToFitLine(fragment, line.availableWidth() - line.width(), emptyLine, textFragmentIterator));
737                 line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
738                 break;
739             }
740             // Non-breakable non-whitespace first fragment. Add it to the current line. -it overflows though.
741             ASSERT(fragment.type() == TextFragmentIterator::TextFragment::NonWhitespace);
742             if (emptyLine) {
743                 forceFragmentToLine(line, textFragmentIterator, runs, fragment);
744                 break;
745             }
746             // Non-breakable non-whitespace fragment when there's already content on the line. Push it to the next line.
747             ASSERT(line.lastFragment());
748             if (line.lastFragment().value().overlapsToNextRenderer()) {
749                 // Check if this fragment is a continuation of a previous segment. In such cases, we need to remove them all.
750                 const auto& lastCompleteFragment = line.revertToLastCompleteFragment(runs);
751                 textFragmentIterator.revertToEndOfFragment(lastCompleteFragment);
752                 break;
753             }
754             line.setOverflowedFragment(fragment);
755             break;
756         }
757         line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
758         // Find the next text fragment.
759         fragment = textFragmentIterator.nextTextFragment(line.width());
760     }
761     return (fragment.type() == TextFragmentIterator::TextFragment::ContentEnd && line.overflowedFragment().isEmpty()) || line.overflowedFragment().type() == TextFragmentIterator::TextFragment::ContentEnd;
762 }
763
764 static ExpansionBehavior expansionBehavior(bool isAfterExpansion, bool lastRunOnLine)
765 {
766     ExpansionBehavior expansionBehavior;
767     expansionBehavior = isAfterExpansion ? ForbidLeadingExpansion : AllowLeadingExpansion;
768     expansionBehavior |= lastRunOnLine ? ForbidTrailingExpansion : AllowTrailingExpansion;
769     return expansionBehavior;
770 }
771
772 static void justifyRuns(const LineState& line, Layout::RunVector& runs, unsigned firstRunIndex)
773 {
774     ASSERT(runs.size());
775     auto widthToDistribute = line.availableWidth() - line.width();
776     if (widthToDistribute <= 0)
777         return;
778
779     auto lastRunIndex = runs.size() - 1;
780     ASSERT(firstRunIndex <= lastRunIndex);
781     Vector<std::pair<unsigned, ExpansionBehavior>> expansionOpportunityList;
782     unsigned expansionOpportunityCountOnThisLine = 0;
783     auto isAfterExpansion = true;
784     for (auto i = firstRunIndex; i <= lastRunIndex; ++i) {
785         const auto& run = runs.at(i);
786         unsigned opportunityCountInRun = 0;
787         std::tie(opportunityCountInRun, isAfterExpansion) = line.expansionOpportunityCount(run.start, run.end);
788         expansionOpportunityList.append(std::make_pair(opportunityCountInRun, expansionBehavior(isAfterExpansion, i == lastRunIndex)));
789         expansionOpportunityCountOnThisLine += opportunityCountInRun;
790     }
791     if (!expansionOpportunityCountOnThisLine)
792         return;
793
794     ASSERT(expansionOpportunityList.size() == lastRunIndex - firstRunIndex + 1);
795     auto expansion = widthToDistribute / expansionOpportunityCountOnThisLine;
796     float accumulatedExpansion = 0;
797     for (auto i = firstRunIndex; i <= lastRunIndex; ++i) {
798         auto& run = runs.at(i);
799         unsigned opportunityCountInRun;
800         std::tie(opportunityCountInRun, run.expansionBehavior) = expansionOpportunityList.at(i - firstRunIndex);
801         run.expansion = opportunityCountInRun * expansion;
802         run.logicalLeft += accumulatedExpansion;
803         run.logicalRight += (accumulatedExpansion + run.expansion);
804         accumulatedExpansion += run.expansion;
805     }
806 }
807
808 static ETextAlign textAlignForLine(const TextFragmentIterator::Style& style, bool lastLine)
809 {
810     // Fallback to LEFT (START) alignment for non-collapsable content and for the last line before a forced break or the end of the block.
811     auto textAlign = style.textAlign;
812     if (textAlign == JUSTIFY && (!style.collapseWhitespace || lastLine))
813         textAlign = LEFT;
814     return textAlign;
815 }
816
817 static void closeLineEndingAndAdjustRuns(LineState& line, Layout::RunVector& runs, std::optional<unsigned> lastRunIndexOfPreviousLine, unsigned& lineCount,
818     const TextFragmentIterator& textFragmentIterator, bool lastLineInFlow)
819 {
820     if (!runs.size() || (lastRunIndexOfPreviousLine && runs.size() - 1 == lastRunIndexOfPreviousLine.value()))
821         return;
822     removeTrailingWhitespace(line, runs, textFragmentIterator);
823     if (!runs.size())
824         return;
825     // Adjust runs' position by taking line's alignment into account.
826     const auto& style = textFragmentIterator.style();
827     auto firstRunIndex = lastRunIndexOfPreviousLine ? lastRunIndexOfPreviousLine.value() + 1 : 0;
828     auto lineLogicalLeft = line.logicalLeftOffset();
829     auto textAlign = textAlignForLine(style, lastLineInFlow || (line.lastFragment() && line.lastFragment().value().type() == TextFragmentIterator::TextFragment::HardLineBreak));
830     if (textAlign == JUSTIFY)
831         justifyRuns(line, runs, firstRunIndex);
832     else
833         lineLogicalLeft = computeLineLeft(textAlign, line.availableWidth(), line.width(), line.logicalLeftOffset());
834     for (auto i = firstRunIndex; i < runs.size(); ++i) {
835         runs[i].logicalLeft += lineLogicalLeft;
836         runs[i].logicalRight += lineLogicalLeft;
837     }
838     runs.last().isEndOfLine = true;
839     ++lineCount;
840 }
841
842 static void createTextRuns(Layout::RunVector& runs, RenderBlockFlow& flow, unsigned& lineCount)
843 {
844     LayoutUnit borderAndPaddingBefore = flow.borderAndPaddingBefore();
845     LayoutUnit lineHeight = lineHeightFromFlow(flow);
846     LineState line;
847     bool isEndOfContent = false;
848     TextFragmentIterator textFragmentIterator = TextFragmentIterator(flow);
849     std::optional<unsigned> lastRunIndexOfPreviousLine;
850     do {
851         flow.setLogicalHeight(lineHeight * lineCount + borderAndPaddingBefore);
852         LineState previousLine = line;
853         line = LineState();
854         updateLineConstrains(flow, line, !lineCount);
855         isEndOfContent = createLineRuns(line, previousLine, runs, textFragmentIterator);
856         closeLineEndingAndAdjustRuns(line, runs, lastRunIndexOfPreviousLine, lineCount, textFragmentIterator, isEndOfContent);
857         if (runs.size())
858             lastRunIndexOfPreviousLine = runs.size() - 1;
859     } while (!isEndOfContent);
860 }
861
862 std::unique_ptr<Layout> create(RenderBlockFlow& flow)
863 {
864     unsigned lineCount = 0;
865     Layout::RunVector runs;
866
867     createTextRuns(runs, flow, lineCount);
868     return Layout::create(runs, lineCount);
869 }
870
871 std::unique_ptr<Layout> Layout::create(const RunVector& runVector, unsigned lineCount)
872 {
873     void* slot = WTF::fastMalloc(sizeof(Layout) + sizeof(Run) * runVector.size());
874     return std::unique_ptr<Layout>(new (NotNull, slot) Layout(runVector, lineCount));
875 }
876
877 Layout::Layout(const RunVector& runVector, unsigned lineCount)
878     : m_lineCount(lineCount)
879     , m_runCount(runVector.size())
880 {
881     memcpy(m_runs, runVector.data(), m_runCount * sizeof(Run));
882 }
883
884 #ifndef NDEBUG
885 static void printReason(AvoidanceReason reason, TextStream& stream)
886 {
887     switch (reason) {
888     case FlowIsInsideRegion:
889         stream << "flow is inside region";
890         break;
891     case FlowHasHorizonalWritingMode:
892         stream << "horizontal writing mode";
893         break;
894     case FlowHasOutline:
895         stream << "outline";
896         break;
897     case FlowIsRuby:
898         stream << "ruby";
899         break;
900     case FlowHasHangingPunctuation:
901         stream << "hanging punctuation";
902         break;
903     case FlowIsPaginated:
904         stream << "paginated";
905         break;
906     case FlowHasTextOverflow:
907         stream << "text-overflow";
908         break;
909     case FlowIsDepricatedFlexBox:
910         stream << "depricatedFlexBox";
911         break;
912     case FlowParentIsPlaceholderElement:
913         stream << "placeholder element";
914         break;
915     case FlowParentIsTextAreaWithWrapping:
916         stream << "wrapping textarea";
917         break;
918     case FlowHasNonSupportedChild:
919         stream << "nested renderers";
920         break;
921     case FlowHasUnsupportedFloat:
922         stream << "complicated float";
923         break;
924     case FlowHasUnsupportedUnderlineDecoration:
925         stream << "text-underline-position: under";
926         break;
927     case FlowHasJustifiedNonLatinText:
928         stream << "text-align: justify with non-latin text";
929         break;
930     case FlowHasOverflowVisible:
931         stream << "overflow: visible";
932         break;
933     case FlowIsNotLTR:
934         stream << "dir is not LTR";
935         break;
936     case FlowHasLineBoxContainProperty:
937         stream << "line-box-contain property";
938         break;
939     case FlowIsNotTopToBottom:
940         stream << "non top-to-bottom flow";
941         break;
942     case FlowHasLineBreak:
943         stream << "line-break property";
944         break;
945     case FlowHasNonNormalUnicodeBiDi:
946         stream << "non-normal Unicode bidi";
947         break;
948     case FlowHasRTLOrdering:
949         stream << "-webkit-rtl-ordering";
950         break;
951     case FlowHasLineAlignEdges:
952         stream << "-webkit-line-align edges";
953         break;
954     case FlowHasLineSnap:
955         stream << "-webkit-line-snap property";
956         break;
957     case FlowHasHypensAuto:
958         stream << "hyphen: auto";
959         break;
960     case FlowHasTextEmphasisFillOrMark:
961         stream << "text-emphasis (fill/mark)";
962         break;
963     case FlowHasPseudoFirstLine:
964         stream << "first-line";
965         break;
966     case FlowHasPseudoFirstLetter:
967         stream << "first-letter";
968         break;
969     case FlowHasTextCombine:
970         stream << "text combine";
971         break;
972     case FlowHasTextFillBox:
973         stream << "background-color (text-fill)";
974         break;
975     case FlowHasBorderFitLines:
976         stream << "-webkit-border-fit";
977         break;
978     case FlowHasNonAutoLineBreak:
979         stream << "line-break is not auto";
980         break;
981     case FlowHasNonAutoTrailingWord:
982         stream << "-apple-trailing-word is not auto";
983         break;
984     case FlowHasSVGFont:
985         stream << "SVG font";
986         break;
987     case FlowTextHasNoBreakSpace:
988         stream << "No-break-space character";
989         break;
990     case FlowTextHasSoftHyphen:
991         stream << "soft hyphen character";
992         break;
993     case FlowTextHasDirectionCharacter:
994         stream << "direction character";
995         break;
996     case FlowIsMissingPrimaryFont:
997         stream << "missing primary font";
998         break;
999     case FlowFontIsMissingGlyph:
1000         stream << "missing glyph";
1001         break;
1002     case FlowTextIsCombineText:
1003         stream << "text is combine";
1004         break;
1005     case FlowTextIsRenderCounter:
1006         stream << "unsupported RenderCounter";
1007         break;
1008     case FlowTextIsRenderQuote:
1009         stream << "unsupported RenderQuote";
1010         break;
1011     case FlowTextIsTextFragment:
1012         stream << "unsupported TextFragment";
1013         break;
1014     case FlowTextIsSVGInlineText:
1015         stream << "unsupported SVGInlineText";
1016         break;
1017     case FlowFontIsNotSimple:
1018         stream << "complext font";
1019         break;
1020     case FlowHasTextShadow:
1021         stream << "text-shadow";
1022         break;
1023     case FlowChildIsSelected:
1024         stream << "selected content";
1025         break;
1026     case FlowTextIsEmpty:
1027     case FlowHasNoChild:
1028     case FlowHasNoParent:
1029     case FeatureIsDisabled:
1030     default:
1031         break;
1032     }
1033 }
1034
1035 static void printReasons(AvoidanceReasonFlags reasons, TextStream& stream)
1036 {
1037     bool first = true;
1038     for (auto reasonItem = EndOfReasons >> 1; reasonItem != NoReason; reasonItem >>= 1) {
1039         if (!(reasons & reasonItem))
1040             continue;
1041         stream << (first ? " " : ", ");
1042         first = false;
1043         printReason(reasonItem, stream);
1044     }
1045 }
1046
1047 static void printTextForSubtree(const RenderObject& renderer, unsigned& charactersLeft, TextStream& stream)
1048 {
1049     if (!charactersLeft)
1050         return;
1051     if (is<RenderText>(renderer)) {
1052         String text = downcast<RenderText>(renderer).text();
1053         text = text.stripWhiteSpace();
1054         unsigned len = std::min(charactersLeft, text.length());
1055         stream << text.left(len);
1056         charactersLeft -= len;
1057         return;
1058     }
1059     if (!is<RenderElement>(renderer))
1060         return;
1061     for (const auto* child = downcast<RenderElement>(renderer).firstChild(); child; child = child->nextSibling())
1062         printTextForSubtree(*child, charactersLeft, stream);
1063 }
1064
1065 static unsigned textLengthForSubtree(const RenderObject& renderer)
1066 {
1067     if (is<RenderText>(renderer))
1068         return downcast<RenderText>(renderer).textLength();
1069     if (!is<RenderElement>(renderer))
1070         return 0;
1071     unsigned textLength = 0;
1072     for (const auto* child = downcast<RenderElement>(renderer).firstChild(); child; child = child->nextSibling())
1073         textLength += textLengthForSubtree(*child);
1074     return textLength;
1075 }
1076
1077 static void collectNonEmptyLeafRenderBlockFlows(const RenderObject& renderer, HashSet<const RenderBlockFlow*>& leafRenderers)
1078 {
1079     if (is<RenderText>(renderer)) {
1080         if (!downcast<RenderText>(renderer).textLength())
1081             return;
1082         // Find RenderBlockFlow ancestor.
1083         for (const auto* current = renderer.parent(); current; current = current->parent()) {
1084             if (!is<RenderBlockFlow>(current))
1085                 continue;
1086             leafRenderers.add(downcast<RenderBlockFlow>(current));
1087             break;
1088         }
1089         return;
1090     }
1091     if (!is<RenderElement>(renderer))
1092         return;
1093     for (const auto* child = downcast<RenderElement>(renderer).firstChild(); child; child = child->nextSibling())
1094         collectNonEmptyLeafRenderBlockFlows(*child, leafRenderers);
1095 }
1096
1097 static void collectNonEmptyLeafRenderBlockFlowsForCurrentPage(HashSet<const RenderBlockFlow*>& leafRenderers)
1098 {
1099     for (const auto* document : Document::allDocuments()) {
1100         if (!document->renderView() || document->pageCacheState() != Document::NotInPageCache)
1101             continue;
1102         if (!document->isHTMLDocument() && !document->isXHTMLDocument())
1103             continue;
1104         collectNonEmptyLeafRenderBlockFlows(*document->renderView(), leafRenderers);
1105     }
1106 }
1107
1108 void toggleSimpleLineLayout()
1109 {
1110     for (const auto* document : Document::allDocuments()) {
1111         auto* settings = document->settings();
1112         if (!settings)
1113             continue;
1114         settings->setSimpleLineLayoutEnabled(!settings->simpleLineLayoutEnabled());
1115     }
1116 }
1117
1118 void printSimpleLineLayoutBlockList()
1119 {
1120     HashSet<const RenderBlockFlow*> leafRenderers;
1121     collectNonEmptyLeafRenderBlockFlowsForCurrentPage(leafRenderers);
1122     if (!leafRenderers.size()) {
1123         WTFLogAlways("No text found in this document\n");
1124         return;
1125     }
1126     TextStream stream;
1127     stream << "---------------------------------------------------\n";
1128     for (const auto* flow : leafRenderers) {
1129         auto reason = canUseForWithReason(*flow, IncludeReasons::All);
1130         if (reason == NoReason)
1131             continue;
1132         unsigned printedLength = 30;
1133         stream << "\"";
1134         printTextForSubtree(*flow, printedLength, stream);
1135         for (;printedLength > 0; --printedLength)
1136             stream << " ";
1137         stream << "\"(" << textLengthForSubtree(*flow) << "):";
1138         printReasons(reason, stream);
1139         stream << "\n";
1140     }
1141     stream << "---------------------------------------------------\n";
1142     WTFLogAlways("%s", stream.release().utf8().data());
1143 }
1144
1145 void printSimpleLineLayoutCoverage()
1146 {
1147     HashSet<const RenderBlockFlow*> leafRenderers;
1148     collectNonEmptyLeafRenderBlockFlowsForCurrentPage(leafRenderers);
1149     if (!leafRenderers.size()) {
1150         WTFLogAlways("No text found in this document\n");
1151         return;
1152     }
1153     TextStream stream;
1154     HashMap<AvoidanceReason, unsigned> flowStatistics;
1155     unsigned textLength = 0;
1156     unsigned unsupportedTextLength = 0;
1157     unsigned numberOfUnsupportedLeafBlocks = 0;
1158     for (const auto* flow : leafRenderers) {
1159         auto flowLength = textLengthForSubtree(*flow);
1160         textLength += flowLength;
1161         auto reasons = canUseForWithReason(*flow, IncludeReasons::All);
1162         if (reasons == NoReason)
1163             continue;
1164         ++numberOfUnsupportedLeafBlocks;
1165         unsupportedTextLength += flowLength;
1166         for (auto reasonItem = EndOfReasons >> 1; reasonItem != NoReason; reasonItem >>= 1) {
1167             if (!(reasons & reasonItem))
1168                 continue;
1169             auto result = flowStatistics.add(reasonItem, flowLength);
1170             if (!result.isNewEntry)
1171                 result.iterator->value += flowLength;
1172         }
1173     }
1174     stream << "---------------------------------------------------\n";
1175     stream << "Number of text blocks: total(" <<  leafRenderers.size() << ") non-simple(" << numberOfUnsupportedLeafBlocks << ")\nText length: total(" <<
1176         textLength << ") non-simple(" << unsupportedTextLength << ")\n";
1177     for (const auto reasonEntry : flowStatistics) {
1178         printReason(reasonEntry.key, stream);
1179         stream << ": " << (float)reasonEntry.value / (float)textLength * 100 << "%\n";
1180     }
1181     stream << "simple line layout coverage: " << (float)(textLength - unsupportedTextLength) / (float)textLength * 100 << "%\n";
1182     stream << "---------------------------------------------------\n";
1183     WTFLogAlways("%s", stream.release().utf8().data());
1184 }
1185 #endif
1186 }
1187 }