Add SPI to access a WebsiteDataStore without instantiating it, and its configuration
[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 "DocumentMarkerController.h"
30 #include "FontCache.h"
31 #include "Frame.h"
32 #include "GraphicsContext.h"
33 #include "HTMLTextFormControlElement.h"
34 #include "HitTestLocation.h"
35 #include "HitTestRequest.h"
36 #include "HitTestResult.h"
37 #include "Hyphenation.h"
38 #include "InlineTextBox.h"
39 #include "LineWidth.h"
40 #include "Logging.h"
41 #include "PaintInfo.h"
42 #include "RenderBlockFlow.h"
43 #include "RenderChildIterator.h"
44 #include "RenderFragmentedFlow.h"
45 #include "RenderLineBreak.h"
46 #include "RenderMultiColumnFlow.h"
47 #include "RenderStyle.h"
48 #include "RenderText.h"
49 #include "RenderTextControl.h"
50 #include "RenderView.h"
51 #include "Settings.h"
52 #include "SimpleLineLayoutFlowContents.h"
53 #include "SimpleLineLayoutFunctions.h"
54 #include "SimpleLineLayoutResolver.h"
55 #include "SimpleLineLayoutTextFragmentIterator.h"
56 #include "Text.h"
57 #include "TextPaintStyle.h"
58 #include <pal/Logging.h>
59
60 namespace WebCore {
61 namespace SimpleLineLayout {
62
63 #ifndef NDEBUG
64 #define SET_REASON_AND_RETURN_IF_NEEDED(reason, reasons, includeReasons) { \
65         reasons |= reason; \
66         if (includeReasons == IncludeReasons::First) \
67             return reasons; \
68     }
69 #else
70 #define SET_REASON_AND_RETURN_IF_NEEDED(reason, reasons, includeReasons) { \
71         ASSERT_UNUSED(includeReasons, includeReasons == IncludeReasons::First); \
72         reasons |= reason; \
73         return reasons; \
74     }
75 #endif
76
77
78 template <typename CharacterType> AvoidanceReasonFlags canUseForCharacter(CharacterType, bool textIsJustified, IncludeReasons);
79
80 template<> AvoidanceReasonFlags canUseForCharacter(UChar character, bool textIsJustified, IncludeReasons includeReasons)
81 {
82     AvoidanceReasonFlags reasons = { };
83     if (textIsJustified) {
84         // Include characters up to Latin Extended-B and some punctuation range when text is justified.
85         bool isLatinIncludingExtendedB = character <= 0x01FF;
86         bool isPunctuationRange = character >= 0x2010 && character <= 0x2027;
87         if (!(isLatinIncludingExtendedB || isPunctuationRange))
88             SET_REASON_AND_RETURN_IF_NEEDED(FlowHasJustifiedNonLatinText, reasons, includeReasons);
89     }
90
91     if (U16_IS_SURROGATE(character))
92         SET_REASON_AND_RETURN_IF_NEEDED(FlowTextHasSurrogatePair, reasons, includeReasons);
93     
94     UCharDirection direction = u_charDirection(character);
95     if (direction == U_RIGHT_TO_LEFT || direction == U_RIGHT_TO_LEFT_ARABIC
96         || direction == U_RIGHT_TO_LEFT_EMBEDDING || direction == U_RIGHT_TO_LEFT_OVERRIDE
97         || direction == U_LEFT_TO_RIGHT_EMBEDDING || direction == U_LEFT_TO_RIGHT_OVERRIDE
98         || direction == U_POP_DIRECTIONAL_FORMAT || direction == U_BOUNDARY_NEUTRAL)
99         SET_REASON_AND_RETURN_IF_NEEDED(FlowTextHasDirectionCharacter, reasons, includeReasons);
100
101     return reasons;
102 }
103
104 template<> AvoidanceReasonFlags canUseForCharacter(LChar, bool, IncludeReasons)
105 {
106     return { };
107 }
108
109 template <typename CharacterType>
110 static AvoidanceReasonFlags canUseForText(const CharacterType* text, unsigned length, const FontCascade& fontCascade, Optional<float> lineHeightConstraint,
111     bool textIsJustified, IncludeReasons includeReasons)
112 {
113     AvoidanceReasonFlags reasons = { };
114     auto& primaryFont = fontCascade.primaryFont();
115     auto& fontMetrics = primaryFont.fontMetrics();
116     auto availableSpaceForGlyphAscent = fontMetrics.ascent();
117     auto availableSpaceForGlyphDescent = fontMetrics.descent();
118     if (lineHeightConstraint) {
119         auto lineHeightPadding = *lineHeightConstraint - fontMetrics.height();
120         availableSpaceForGlyphAscent += lineHeightPadding / 2;
121         availableSpaceForGlyphDescent += lineHeightPadding / 2;
122     }
123
124     for (unsigned i = 0; i < length; ++i) {
125         auto character = text[i];
126         if (FontCascade::treatAsSpace(character))
127             continue;
128
129         if (character == softHyphen)
130             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextHasSoftHyphen, reasons, includeReasons);
131
132         auto characterReasons = canUseForCharacter(character, textIsJustified, includeReasons);
133         if (characterReasons != NoReason)
134             SET_REASON_AND_RETURN_IF_NEEDED(characterReasons, reasons, includeReasons);
135
136         auto glyphData = fontCascade.glyphDataForCharacter(character, false);
137         if (!glyphData.isValid() || glyphData.font != &primaryFont)
138             SET_REASON_AND_RETURN_IF_NEEDED(FlowPrimaryFontIsInsufficient, reasons, includeReasons);
139
140         if (lineHeightConstraint) {
141             auto bounds = primaryFont.boundsForGlyph(glyphData.glyph);
142             if (ceilf(-bounds.y()) > availableSpaceForGlyphAscent || ceilf(bounds.maxY()) > availableSpaceForGlyphDescent)
143                 SET_REASON_AND_RETURN_IF_NEEDED(FlowFontHasOverflowGlyph, reasons, includeReasons);
144         }
145     }
146     return reasons;
147 }
148
149 static AvoidanceReasonFlags canUseForText(StringView text, const FontCascade& fontCascade, Optional<float> lineHeightConstraint, bool textIsJustified, IncludeReasons includeReasons)
150 {
151     if (text.is8Bit())
152         return canUseForText(text.characters8(), text.length(), fontCascade, lineHeightConstraint, textIsJustified, includeReasons);
153     return canUseForText(text.characters16(), text.length(), fontCascade, lineHeightConstraint, textIsJustified, includeReasons);
154 }
155
156 static AvoidanceReasonFlags canUseForFontAndText(const RenderBlockFlow& flow, IncludeReasons includeReasons)
157 {
158     AvoidanceReasonFlags reasons = { };
159     // We assume that all lines have metrics based purely on the primary font.
160     const auto& style = flow.style();
161     auto& fontCascade = style.fontCascade();
162     if (fontCascade.primaryFont().isInterstitial())
163         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsMissingPrimaryFont, reasons, includeReasons);
164     Optional<float> lineHeightConstraint;
165     if (style.lineBoxContain().contains(LineBoxContain::Glyphs))
166         lineHeightConstraint = lineHeightFromFlow(flow).toFloat();
167     bool flowIsJustified = style.textAlign() == TextAlignMode::Justify;
168     for (const auto& textRenderer : childrenOfType<RenderText>(flow)) {
169         // FIXME: Do not return until after checking all children.
170         if (textRenderer.text().isEmpty())
171             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsEmpty, reasons, includeReasons);
172         if (textRenderer.isCombineText())
173             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsCombineText, reasons, includeReasons);
174         if (textRenderer.isCounter())
175             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsRenderCounter, reasons, includeReasons);
176         if (textRenderer.isQuote())
177             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsRenderQuote, reasons, includeReasons);
178         if (textRenderer.isTextFragment())
179             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsTextFragment, reasons, includeReasons);
180         if (textRenderer.isSVGInlineText())
181             SET_REASON_AND_RETURN_IF_NEEDED(FlowTextIsSVGInlineText, reasons, includeReasons);
182         if (!textRenderer.canUseSimpleFontCodePath()) {
183             // No need to check the code path at this point. We already know it can't be simple.
184             SET_REASON_AND_RETURN_IF_NEEDED(FlowHasComplexFontCodePath, reasons, includeReasons);
185         } else {
186             TextRun run(String(textRenderer.text()));
187             run.setCharacterScanForCodePath(false);
188             if (style.fontCascade().codePath(run) != FontCascade::Simple)
189                 SET_REASON_AND_RETURN_IF_NEEDED(FlowHasComplexFontCodePath, reasons, includeReasons);
190         }
191
192         auto textReasons = canUseForText(textRenderer.stringView(), fontCascade, lineHeightConstraint, flowIsJustified, includeReasons);
193         if (textReasons != NoReason)
194             SET_REASON_AND_RETURN_IF_NEEDED(textReasons, reasons, includeReasons);
195     }
196     return reasons;
197 }
198
199 static AvoidanceReasonFlags canUseForStyle(const RenderStyle& style, IncludeReasons includeReasons)
200 {
201     AvoidanceReasonFlags reasons = { };
202     if (style.textOverflow() == TextOverflow::Ellipsis)
203         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextOverflow, reasons, includeReasons);
204     if (style.textUnderlinePosition() != TextUnderlinePosition::Auto || !style.textUnderlineOffset().isAuto() || !style.textDecorationThickness().isAuto())
205         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasUnsupportedUnderlineDecoration, reasons, includeReasons);
206     // Non-visible overflow should be pretty easy to support.
207     if (style.overflowX() != Overflow::Visible || style.overflowY() != Overflow::Visible)
208         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasOverflowNotVisible, reasons, includeReasons);
209     if (!style.isLeftToRightDirection())
210         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsNotLTR, reasons, includeReasons);
211     if (!(style.lineBoxContain().contains(LineBoxContain::Block)))
212         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasLineBoxContainProperty, reasons, includeReasons);
213     if (style.writingMode() != TopToBottomWritingMode)
214         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsNotTopToBottom, reasons, includeReasons);
215     if (style.lineBreak() != LineBreak::Auto)
216         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasLineBreak, reasons, includeReasons);
217     if (style.unicodeBidi() != UBNormal)
218         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasNonNormalUnicodeBiDi, reasons, includeReasons);
219     if (style.rtlOrdering() != Order::Logical)
220         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasRTLOrdering, reasons, includeReasons);
221     if (style.lineAlign() != LineAlign::None)
222         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasLineAlignEdges, reasons, includeReasons);
223     if (style.lineSnap() != LineSnap::None)
224         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasLineSnap, reasons, includeReasons);
225     if (style.textEmphasisFill() != TextEmphasisFill::Filled || style.textEmphasisMark() != TextEmphasisMark::None)
226         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextEmphasisFillOrMark, reasons, includeReasons);
227     if (style.textShadow())
228         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextShadow, reasons, includeReasons);
229     if (style.hasPseudoStyle(PseudoId::FirstLine))
230         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasPseudoFirstLine, reasons, includeReasons);
231     if (style.hasPseudoStyle(PseudoId::FirstLetter))
232         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasPseudoFirstLetter, reasons, includeReasons);
233     if (style.hasTextCombine())
234         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextCombine, reasons, includeReasons);
235     if (style.backgroundClip() == FillBox::Text)
236         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextFillBox, reasons, includeReasons);
237     if (style.borderFit() == BorderFit::Lines)
238         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasBorderFitLines, reasons, includeReasons);
239     if (style.lineBreak() != LineBreak::Auto)
240         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasNonAutoLineBreak, reasons, includeReasons);
241     if (style.nbspMode() != NBSPMode::Normal)
242         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasWebKitNBSPMode, reasons, includeReasons);
243     if (style.hyphens() == Hyphens::Auto) {
244         auto textReasons = canUseForText(style.hyphenString(), style.fontCascade(), WTF::nullopt, false, includeReasons);
245         if (textReasons != NoReason)
246             SET_REASON_AND_RETURN_IF_NEEDED(textReasons, reasons, includeReasons);
247     }
248     return reasons;
249 }
250
251 AvoidanceReasonFlags canUseForWithReason(const RenderBlockFlow& flow, IncludeReasons includeReasons)
252 {
253 #ifndef NDEBUG
254     static std::once_flag onceFlag;
255     std::call_once(onceFlag, [] {
256         PAL::registerNotifyCallback("com.apple.WebKit.showSimpleLineLayoutCoverage", WTF::Function<void()> { printSimpleLineLayoutCoverage });
257         PAL::registerNotifyCallback("com.apple.WebKit.showSimpleLineLayoutReasons", WTF::Function<void()> { printSimpleLineLayoutBlockList });
258         PAL::registerNotifyCallback("com.apple.WebKit.toggleSimpleLineLayout", WTF::Function<void()> { toggleSimpleLineLayout });
259     });
260 #endif
261     AvoidanceReasonFlags reasons = { };
262     if (!flow.settings().simpleLineLayoutEnabled())
263         SET_REASON_AND_RETURN_IF_NEEDED(FeatureIsDisabled, reasons, includeReasons);
264     if (!flow.parent())
265         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasNoParent, reasons, includeReasons);
266     if (!flow.firstChild())
267         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasNoChild, reasons, includeReasons);
268     if (flow.fragmentedFlowState() != RenderObject::NotInsideFragmentedFlow) {
269         auto* fragmentedFlow = flow.enclosingFragmentedFlow();
270         if (!is<RenderMultiColumnFlow>(fragmentedFlow))
271             SET_REASON_AND_RETURN_IF_NEEDED(FlowIsInsideANonMultiColumnThread, reasons, includeReasons);
272         auto& columnThread = downcast<RenderMultiColumnFlow>(*fragmentedFlow);
273         if (columnThread.parent() != &flow.view())
274             SET_REASON_AND_RETURN_IF_NEEDED(MultiColumnFlowIsNotTopLevel, reasons, includeReasons);
275         if (columnThread.hasColumnSpanner())
276             SET_REASON_AND_RETURN_IF_NEEDED(MultiColumnFlowHasColumnSpanner, reasons, includeReasons);
277         auto& style = flow.style();
278         if (style.verticalAlign() != VerticalAlign::Baseline)
279             SET_REASON_AND_RETURN_IF_NEEDED(MultiColumnFlowVerticalAlign, reasons, includeReasons);
280         if (style.isFloating())
281             SET_REASON_AND_RETURN_IF_NEEDED(MultiColumnFlowIsFloating, reasons, includeReasons);
282     }
283     if (!flow.isHorizontalWritingMode())
284         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasHorizonalWritingMode, reasons, includeReasons);
285     if (flow.hasOutline())
286         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasOutline, reasons, includeReasons);
287     if (flow.isRubyText() || flow.isRubyBase())
288         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsRuby, reasons, includeReasons);
289     if (!flow.style().hangingPunctuation().isEmpty())
290         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasHangingPunctuation, reasons, includeReasons);
291     
292     // Printing does pagination without a flow thread.
293     if (flow.document().paginated())
294         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsPaginated, reasons, includeReasons);
295     if (flow.firstLineBlock())
296         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasPseudoFirstLine, reasons, includeReasons);
297     if (flow.isAnonymousBlock() && flow.parent()->style().textOverflow() == TextOverflow::Ellipsis)
298         SET_REASON_AND_RETURN_IF_NEEDED(FlowHasTextOverflow, reasons, includeReasons);
299     if (flow.parent()->isDeprecatedFlexibleBox())
300         SET_REASON_AND_RETURN_IF_NEEDED(FlowIsDepricatedFlexBox, reasons, includeReasons);
301     // FIXME: Placeholders do something strange.
302     if (is<RenderTextControl>(*flow.parent()) && downcast<RenderTextControl>(*flow.parent()).textFormControlElement().placeholderElement())
303         SET_REASON_AND_RETURN_IF_NEEDED(FlowParentIsPlaceholderElement, reasons, includeReasons);
304     // FIXME: Implementation of wrap=hard looks into lineboxes.
305     if (flow.parent()->isTextArea() && flow.parent()->element()->hasAttributeWithoutSynchronization(HTMLNames::wrapAttr))
306         SET_REASON_AND_RETURN_IF_NEEDED(FlowParentIsTextAreaWithWrapping, reasons, includeReasons);
307     // This currently covers <blockflow>#text</blockflow>, <blockflow>#text<br></blockflow> and mutiple (sibling) RenderText cases.
308     // The <blockflow><inline>#text</inline></blockflow> case is also popular and should be relatively easy to cover.
309     for (const auto* child = flow.firstChild(); child;) {
310         if (child->selectionState() != RenderObject::SelectionNone)
311             SET_REASON_AND_RETURN_IF_NEEDED(FlowChildIsSelected, reasons, includeReasons);
312         if (is<RenderText>(*child)) {
313             const auto& renderText = downcast<RenderText>(*child);
314             if (renderText.textNode() && !renderText.document().markers().markersFor(*renderText.textNode()).isEmpty())
315                 SET_REASON_AND_RETURN_IF_NEEDED(FlowIncludesDocumentMarkers, reasons, includeReasons);
316             child = child->nextSibling();
317             continue;
318         }
319         if (is<RenderLineBreak>(child) && !downcast<RenderLineBreak>(*child).isWBR() && child->style().clear() == Clear::None) {
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 void revertAllRunsOnCurrentLine(Layout::RunVector& runs)
359 {
360     while (!runs.isEmpty() && !runs.last().isEndOfLine)
361         runs.removeLast();
362 }
363
364 static void revertRuns(Layout::RunVector& runs, unsigned positionToRevertTo, float width)
365 {
366     while (runs.size()) {
367         auto& lastRun = runs.last();
368         if (lastRun.end <= positionToRevertTo)
369             break;
370         if (lastRun.start >= positionToRevertTo) {
371             // Revert this run completely.
372             width -= (lastRun.logicalRight - lastRun.logicalLeft);
373             runs.removeLast();
374         } else {
375             lastRun.logicalRight -= width;
376             width = 0;
377             lastRun.end = positionToRevertTo;
378             // Partial removal.
379             break;
380         }
381     }
382 }
383
384 class LineState {
385 public:
386     void setAvailableWidth(float width) { m_availableWidth = width; }
387     void setCollapedWhitespaceWidth(float width) { m_collapsedWhitespaceWidth = width; }
388     void setLogicalLeftOffset(float offset) { m_logicalLeftOffset = offset; }
389     void setOverflowedFragment(const TextFragmentIterator::TextFragment& fragment) { m_overflowedFragment = fragment; }
390     void setNeedsAllFragments()
391     {
392         ASSERT(!m_fragments);
393         m_fragments.emplace();
394     }
395     void setHyphenationDisabled() { m_hyphenationDisabled = true; }
396     bool isHyphenationDisabled() const { return m_hyphenationDisabled; }
397
398     float availableWidth() const { return m_availableWidth; }
399     float logicalLeftOffset() const { return m_logicalLeftOffset; }
400     const TextFragmentIterator::TextFragment& overflowedFragment() const { return m_overflowedFragment; }
401     bool hasTrailingWhitespace() const { return m_lastFragment.type() == TextFragmentIterator::TextFragment::Whitespace && m_lastFragment.length() > 0; }
402     bool hasWhitespaceFragments() const { return m_lastWhitespaceFragment != WTF::nullopt; }
403     TextFragmentIterator::TextFragment lastFragment() const { return m_lastFragment; }
404     bool isWhitespaceOnly() const { return m_trailingWhitespaceWidth && m_runsWidth == m_trailingWhitespaceWidth; }
405     bool fits(float extra) const { return m_availableWidth >= m_runsWidth + extra; }
406     bool firstCharacterFits() const { return m_firstCharacterFits; }
407     float width() const { return m_runsWidth; }
408     std::pair<unsigned, bool> expansionOpportunityCount(unsigned from, unsigned to) const
409     {
410         ASSERT(m_fragments);
411         // linebreak runs are special.
412         if (from == to)
413             return std::make_pair(0, false);
414         unsigned expansionOpportunityCount = 0;
415         auto previousFragmentType = TextFragmentIterator::TextFragment::ContentEnd;
416         for (const auto& fragment : *m_fragments) {
417             if (fragment.end() <= from)
418                 continue;
419             auto currentFragmentType = fragment.type();
420             auto expansionOpportunity = this->expansionOpportunity(currentFragmentType, previousFragmentType);
421             if (expansionOpportunity)
422                 ++expansionOpportunityCount;
423             previousFragmentType = currentFragmentType;
424             if (fragment.end() >= to)
425                 return std::make_pair(expansionOpportunityCount, expansionOpportunity);
426         }
427         ASSERT_NOT_REACHED();
428         return std::make_pair(expansionOpportunityCount, false);
429     }
430
431     bool isEmpty() const
432     {
433         if (!m_lastFragment.isValid())
434             return true;
435         if (!m_lastCompleteFragment.isEmpty())
436             return false;
437         return m_lastFragment.overlapsToNextRenderer();
438     }
439
440     static inline unsigned endPositionForCollapsedFragment(const TextFragmentIterator::TextFragment& fragment)
441     {
442         return fragment.isCollapsed() ? fragment.start() + 1 : fragment.end();
443     }
444
445     void appendFragmentAndCreateRunIfNeeded(const TextFragmentIterator::TextFragment& fragment, Layout::RunVector& runs)
446     {
447         // Adjust end position while collapsing.
448         unsigned endPosition = endPositionForCollapsedFragment(fragment);
449         // New line needs new run.
450         if (!m_runsWidth) {
451             ASSERT(!m_uncompletedWidth);
452             runs.append(Run(fragment.start(), endPosition, m_runsWidth, m_runsWidth + fragment.width(), false, fragment.hasHyphen(), fragment.isLineBreak()));
453         } else {
454             // Advance last completed fragment when the previous fragment is all set (including multiple parts across renderers)
455             if ((m_lastFragment.type() != fragment.type()) || !m_lastFragment.overlapsToNextRenderer()) {
456                 m_lastCompleteFragment = m_lastFragment;
457                 m_uncompletedWidth = fragment.width();
458             } else
459                 m_uncompletedWidth += fragment.width();
460             // Collapse neighbouring whitespace, if they are across multiple renderers and are not collapsed yet.
461             if (m_lastFragment.isCollapsible() && fragment.isCollapsible()) {
462                 ASSERT(m_lastFragment.isLastInRenderer());
463                 if (!m_lastFragment.isCollapsed()) {
464                     // Line width needs to be adjusted so that now it takes collapsing into consideration.
465                     m_runsWidth -= (m_lastFragment.width() - m_collapsedWhitespaceWidth);
466                 }
467                 // This fragment is collapsed completely. No run is needed.
468                 return;
469             }
470             Run& lastRun = runs.last();
471             if (m_lastFragment.isLastInRenderer() || m_lastFragment.isCollapsed() || fragment.isLineBreak() || lastRun.isLineBreak)
472                 runs.append(Run(fragment.start(), endPosition, m_runsWidth, m_runsWidth + fragment.width(), false, fragment.hasHyphen(), fragment.isLineBreak()));
473             else {
474                 lastRun.end = endPosition;
475                 lastRun.logicalRight += fragment.width();
476                 ASSERT(!lastRun.hasHyphen);
477                 lastRun.hasHyphen = fragment.hasHyphen();
478             }
479         }
480         m_runsWidth += fragment.width();
481         m_lastFragment = fragment;
482         if (m_fragments)
483             (*m_fragments).append(fragment);
484
485         if (fragment.type() == TextFragmentIterator::TextFragment::Whitespace) {
486             m_trailingWhitespaceWidth += fragment.width();
487             m_lastWhitespaceFragment = fragment;
488         } else {
489             m_trailingWhitespaceWidth = 0;
490             m_lastNonWhitespaceFragment = fragment;
491         }
492
493         if (!m_firstCharacterFits)
494             m_firstCharacterFits = fragment.start() + 1 > endPosition || m_runsWidth <= m_availableWidth;
495     }
496
497     TextFragmentIterator::TextFragment revertToLastCompleteFragment(Layout::RunVector& runs)
498     {
499         if (!m_uncompletedWidth) {
500             ASSERT(m_lastFragment == m_lastCompleteFragment);
501             return m_lastFragment;
502         }
503         ASSERT(m_lastFragment.isValid());
504         m_runsWidth -= m_uncompletedWidth;
505         revertRuns(runs, endPositionForCollapsedFragment(m_lastCompleteFragment), m_uncompletedWidth);
506         m_uncompletedWidth = 0;
507         ASSERT(m_lastCompleteFragment.isValid());
508         return m_lastCompleteFragment;
509     }
510
511     void removeTrailingWhitespace(Layout::RunVector& runs)
512     {
513         if (!hasTrailingWhitespace())
514             return;
515         if (m_lastNonWhitespaceFragment) {
516             auto needsReverting = m_lastNonWhitespaceFragment->end() != m_lastFragment.end();
517             // Trailing whitespace fragment might actually have zero length.
518             ASSERT(needsReverting || !m_trailingWhitespaceWidth);
519             if (needsReverting) {
520                 revertRuns(runs, m_lastNonWhitespaceFragment->end(), m_trailingWhitespaceWidth);
521                 m_runsWidth -= m_trailingWhitespaceWidth;
522             }
523             m_trailingWhitespaceWidth = 0;
524             m_lastFragment = *m_lastNonWhitespaceFragment;
525             return;
526         }
527         // This line is all whitespace.
528         revertAllRunsOnCurrentLine(runs);
529         m_runsWidth = 0;
530         m_trailingWhitespaceWidth = 0;
531         // FIXME: Make m_lastFragment optional.
532         m_lastFragment = TextFragmentIterator::TextFragment();
533     }
534
535     float trailingWhitespaceWidth() const { return m_trailingWhitespaceWidth; }
536
537 private:
538     bool expansionOpportunity(TextFragmentIterator::TextFragment::Type currentFragmentType, TextFragmentIterator::TextFragment::Type previousFragmentType) const
539     {
540         return (currentFragmentType == TextFragmentIterator::TextFragment::Whitespace
541             || (currentFragmentType == TextFragmentIterator::TextFragment::NonWhitespace && previousFragmentType == TextFragmentIterator::TextFragment::NonWhitespace));
542     }
543
544     float m_availableWidth { 0 };
545     float m_logicalLeftOffset { 0 };
546     float m_runsWidth { 0 };
547     TextFragmentIterator::TextFragment m_overflowedFragment;
548     TextFragmentIterator::TextFragment m_lastFragment;
549     Optional<TextFragmentIterator::TextFragment> m_lastNonWhitespaceFragment;
550     Optional<TextFragmentIterator::TextFragment> m_lastWhitespaceFragment;
551     TextFragmentIterator::TextFragment m_lastCompleteFragment;
552     float m_uncompletedWidth { 0 };
553     float m_trailingWhitespaceWidth { 0 }; // Use this to remove trailing whitespace without re-mesuring the text.
554     float m_collapsedWhitespaceWidth { 0 };
555     // Having one character on the line does not necessarily mean it actually fits.
556     // First character of the first fragment might be forced on to the current line even if it does not fit.
557     bool m_firstCharacterFits { false };
558     bool m_hyphenationDisabled { false };
559     Optional<Vector<TextFragmentIterator::TextFragment, 30>> m_fragments;
560 };
561
562 static float computeLineLeft(const LineState& line, TextAlignMode textAlign, float& hangingWhitespaceWidth)
563 {
564     float totalWidth = line.width() - hangingWhitespaceWidth;
565     float remainingWidth = line.availableWidth() - totalWidth;
566     float left = line.logicalLeftOffset();
567     switch (textAlign) {
568     case TextAlignMode::Left:
569     case TextAlignMode::WebKitLeft:
570     case TextAlignMode::Start:
571         hangingWhitespaceWidth = std::max(0.f, std::min(hangingWhitespaceWidth, remainingWidth));
572         return left;
573     case TextAlignMode::Right:
574     case TextAlignMode::WebKitRight:
575     case TextAlignMode::End:
576         hangingWhitespaceWidth = 0;
577         return left + std::max<float>(remainingWidth, 0);
578     case TextAlignMode::Center:
579     case TextAlignMode::WebKitCenter:
580         hangingWhitespaceWidth = std::max(0.f, std::min(hangingWhitespaceWidth, (remainingWidth + 1) / 2));
581         return left + std::max<float>(remainingWidth / 2, 0);
582     case TextAlignMode::Justify:
583         ASSERT_NOT_REACHED();
584         break;
585     }
586     ASSERT_NOT_REACHED();
587     return 0;
588 }
589
590 static bool preWrap(const TextFragmentIterator::Style& style)
591 {
592     return style.wrapLines && !style.collapseWhitespace && !style.breakSpaces;
593 }
594
595 static void updateLineConstrains(const RenderBlockFlow& flow, LineState& line, const LineState& previousLine, unsigned& numberOfPrecedingLinesWithHyphen, const TextFragmentIterator::Style& style, bool isFirstLine)
596 {
597     bool shouldApplyTextIndent = !flow.isAnonymous() || flow.parent()->firstChild() == &flow;
598     LayoutUnit height = flow.logicalHeight();
599     LayoutUnit logicalHeight = flow.minLineHeightForReplacedRenderer(false, 0);
600     line.setLogicalLeftOffset(flow.logicalLeftOffsetForLine(height, DoNotIndentText, logicalHeight) + (shouldApplyTextIndent && isFirstLine ? flow.textIndentOffset() : 0_lu));
601     float logicalRightOffset = flow.logicalRightOffsetForLine(height, DoNotIndentText, logicalHeight);
602     line.setAvailableWidth(std::max<float>(0, logicalRightOffset - line.logicalLeftOffset()));
603     if (style.textAlign == TextAlignMode::Justify)
604         line.setNeedsAllFragments();
605     numberOfPrecedingLinesWithHyphen = (previousLine.isEmpty() || !previousLine.lastFragment().hasHyphen()) ? 0 : numberOfPrecedingLinesWithHyphen + 1;
606     if (style.hyphenLimitLines && numberOfPrecedingLinesWithHyphen >= *style.hyphenLimitLines)
607         line.setHyphenationDisabled();
608     line.setCollapedWhitespaceWidth(style.font.spaceWidth() + style.wordSpacing);
609 }
610
611 struct SplitFragmentData {
612     unsigned position;
613     float width;
614 };
615 static Optional<unsigned> hyphenPositionForFragment(SplitFragmentData splitData, const TextFragmentIterator::TextFragment& fragmentToSplit,
616     const LineState& line, const TextFragmentIterator& textFragmentIterator, float availableWidth)
617 {
618     auto& style = textFragmentIterator.style();
619     if (!style.shouldHyphenate || line.isHyphenationDisabled())
620         return WTF::nullopt;
621
622     // FIXME: This is a workaround for webkit.org/b/169613. See maxPrefixWidth computation in tryHyphenating().
623     // It does not work properly with non-collapsed leading tabs when font is enlarged.
624     auto adjustedAvailableWidth = availableWidth - style.hyphenStringWidth;
625     if (!line.isEmpty())
626         adjustedAvailableWidth += style.font.spaceWidth();
627     if (!enoughWidthForHyphenation(adjustedAvailableWidth, style.font.pixelSize()))
628         return WTF::nullopt;
629
630     // We might be able to fit the hyphen at the split position.
631     auto splitPositionWithHyphen = splitData.position;
632     // Find a splitting position where hyphen surely fits.
633     unsigned start = fragmentToSplit.start();
634     auto leftSideWidth = splitData.width;
635     while (leftSideWidth + style.hyphenStringWidth > availableWidth) {
636         if (--splitPositionWithHyphen <= start)
637             return WTF::nullopt; // No space for hyphen.
638         leftSideWidth -= textFragmentIterator.textWidth(splitPositionWithHyphen, splitPositionWithHyphen + 1, 0);
639     }
640     ASSERT(splitPositionWithHyphen > start);
641     return textFragmentIterator.lastHyphenPosition(fragmentToSplit, splitPositionWithHyphen + 1);
642 }
643
644 static SplitFragmentData split(const TextFragmentIterator::TextFragment& fragment, float availableWidth,
645     const TextFragmentIterator& textFragmentIterator)
646 {
647     ASSERT(availableWidth >= 0);
648     auto left = fragment.start();
649     // Pathological case of (extremely)long string and narrow lines.
650     // Adjust the range so that we can pick a reasonable midpoint.
651     auto averageCharacterWidth = fragment.width() / fragment.length();
652     auto right = std::min<unsigned>(left + (2 * availableWidth / averageCharacterWidth), fragment.end() - 1);
653     // Preserve the left width for the final split position so that we don't need to remeasure the left side again.
654     float leftSideWidth = 0;
655     while (left < right) {
656         auto middle = (left + right) / 2;
657         auto width = textFragmentIterator.textWidth(fragment.start(), middle + 1, 0);
658         if (width < availableWidth) {
659             left = middle + 1;
660             leftSideWidth = width;
661         } else if (width > availableWidth)
662             right = middle;
663         else {
664             right = middle + 1;
665             leftSideWidth = width;
666             break;
667         }
668     }
669     return { right, leftSideWidth };
670 }
671
672 static TextFragmentIterator::TextFragment splitFragmentToFitLine(TextFragmentIterator::TextFragment& fragmentToSplit,
673     const LineState& line, const TextFragmentIterator& textFragmentIterator)
674 {
675     auto availableWidth = line.availableWidth() - line.width();
676     auto splitFragmentData = split(fragmentToSplit, availableWidth, textFragmentIterator);
677     Optional<unsigned> hyphenPosition = WTF::nullopt;
678     // Does first character fit this line?
679     if (splitFragmentData.position == fragmentToSplit.start()) {
680         // Keep at least one character on empty lines.
681         if (line.isEmpty())
682             splitFragmentData.width = textFragmentIterator.textWidth(fragmentToSplit.start(), ++splitFragmentData.position, 0);
683     } else {
684         hyphenPosition = hyphenPositionForFragment(splitFragmentData, fragmentToSplit, line, textFragmentIterator, availableWidth);
685         if (hyphenPosition) {
686             splitFragmentData.position = *hyphenPosition;
687             splitFragmentData.width = textFragmentIterator.textWidth(fragmentToSplit.start(), splitFragmentData.position, 0);
688         }
689     }
690     // If the right side surely does not fit the (next)line, we don't need the width to be kerning/ligature adjusted.
691     // Part of it gets re-measured as the left side during next split.
692     // This saves measuring long chunk of text repeatedly (see pathological case at ::split).
693     auto rightSideWidth = fragmentToSplit.width() - splitFragmentData.width;
694     if (rightSideWidth < 2 * availableWidth)
695         rightSideWidth = textFragmentIterator.textWidth(splitFragmentData.position, fragmentToSplit.end(), 0);
696     return hyphenPosition ? fragmentToSplit.splitWithHyphen(splitFragmentData.position, textFragmentIterator.style().hyphenStringWidth,
697         splitFragmentData.width, rightSideWidth) : fragmentToSplit.split(splitFragmentData.position, splitFragmentData.width, rightSideWidth);
698 }
699
700 enum PreWrapLineBreakRule { Preserve, Ignore };
701
702 static TextFragmentIterator::TextFragment consumeLineBreakIfNeeded(const TextFragmentIterator::TextFragment& fragment, TextFragmentIterator& textFragmentIterator, LineState& line, Layout::RunVector& runs,
703     PreWrapLineBreakRule preWrapLineBreakRule = PreWrapLineBreakRule::Preserve)
704 {
705     if (!fragment.isLineBreak())
706         return fragment;
707
708     bool isHardLinebreak = fragment.type() == TextFragmentIterator::TextFragment::HardLineBreak;
709     // <br> always produces a run. (required by testing output)
710     if (isHardLinebreak)
711         line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
712
713     auto& style = textFragmentIterator.style();
714     if (style.preserveNewline && preWrapLineBreakRule == PreWrapLineBreakRule::Preserve) {
715         if (!isHardLinebreak)
716             return fragment;
717     }
718     return textFragmentIterator.nextTextFragment();
719 }
720
721 static TextFragmentIterator::TextFragment skipWhitespaceIfNeeded(const TextFragmentIterator::TextFragment& fragment, TextFragmentIterator& textFragmentIterator)
722 {
723     if (!textFragmentIterator.style().collapseWhitespace)
724         return fragment;
725
726     TextFragmentIterator::TextFragment firstNonWhitespaceFragment = fragment;
727     while (firstNonWhitespaceFragment.type() == TextFragmentIterator::TextFragment::Whitespace)
728         firstNonWhitespaceFragment = textFragmentIterator.nextTextFragment();
729     return firstNonWhitespaceFragment;
730 }
731
732 static TextFragmentIterator::TextFragment firstFragment(TextFragmentIterator& textFragmentIterator, LineState& currentLine, const LineState& previousLine, Layout::RunVector& runs)
733 {
734     // Handle overflow fragment from previous line.
735     auto overflowedFragment = previousLine.overflowedFragment();
736     if (overflowedFragment.isEmpty())
737         return skipWhitespaceIfNeeded(textFragmentIterator.nextTextFragment(), textFragmentIterator);
738
739     if (overflowedFragment.type() != TextFragmentIterator::TextFragment::Whitespace)
740         return overflowedFragment;
741
742     // Leading whitespace handling.
743     auto& style = textFragmentIterator.style();
744     if (style.breakSpaces) {
745         // Leading whitespace created after breaking the previous line.
746         // Breaking before the first space after a word is only allowed in combination with break-all or break-word.
747         if (style.breakFirstWordOnOverflow || previousLine.hasTrailingWhitespace())
748             return overflowedFragment;
749     }
750     // Special overflow pre-wrap whitespace handling: skip the overflowed whitespace (even when style says not-collapsible)
751     // if we manage to fit at least one character on the previous line.
752     if ((style.collapseWhitespace || style.wrapLines) && previousLine.firstCharacterFits()) {
753         // If skipping the whitespace puts us on a newline, skip the newline too as we already wrapped the line.
754         auto firstFragmentCandidate = consumeLineBreakIfNeeded(textFragmentIterator.nextTextFragment(), textFragmentIterator, currentLine, runs,
755             preWrap(style) ? PreWrapLineBreakRule::Ignore : PreWrapLineBreakRule::Preserve);
756         return skipWhitespaceIfNeeded(firstFragmentCandidate, textFragmentIterator);
757     }
758     return skipWhitespaceIfNeeded(overflowedFragment, textFragmentIterator);
759 }
760
761 static void forceFragmentToLine(LineState& line, TextFragmentIterator& textFragmentIterator, Layout::RunVector& runs, const TextFragmentIterator::TextFragment& fragment)
762 {
763     line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
764     // Check if there are more fragments to add to the current line.
765     auto nextFragment = textFragmentIterator.nextTextFragment();
766     if (fragment.overlapsToNextRenderer()) {
767         while (true) {
768             if (nextFragment.type() != fragment.type())
769                 break;
770             line.appendFragmentAndCreateRunIfNeeded(nextFragment, runs);
771             // Does it overlap to the next segment?
772             if (!nextFragment.overlapsToNextRenderer())
773                 return;
774             nextFragment = textFragmentIterator.nextTextFragment();
775         }
776     }
777     // 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.
778     nextFragment = skipWhitespaceIfNeeded(nextFragment, textFragmentIterator);
779     nextFragment = consumeLineBreakIfNeeded(nextFragment, textFragmentIterator, line, runs);
780     line.setOverflowedFragment(nextFragment);
781 }
782
783 static bool createLineRuns(LineState& line, const LineState& previousLine, Layout::RunVector& runs, TextFragmentIterator& textFragmentIterator)
784 {
785     const auto& style = textFragmentIterator.style();
786     bool lineCanBeWrapped = style.wrapLines || style.breakFirstWordOnOverflow || style.breakAnyWordOnOverflow;
787     auto fragment = firstFragment(textFragmentIterator, line, previousLine, runs);
788     while (fragment.type() != TextFragmentIterator::TextFragment::ContentEnd) {
789         // Hard and soft linebreaks.
790         if (fragment.isLineBreak()) {
791             // 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.)
792             if (line.isEmpty() || fragment.type() == TextFragmentIterator::TextFragment::HardLineBreak || preWrap(style)) {
793                 if (style.textAlign == TextAlignMode::Right || style.textAlign == TextAlignMode::WebKitRight)
794                     line.removeTrailingWhitespace(runs);
795                 line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
796             }
797             break;
798         }
799         if (lineCanBeWrapped && !line.fits(fragment.width())) {
800             // Overflow wrapping behaviour:
801             // 1. Whitesapce collapse on: whitespace is skipped. Jump to next line.
802             // 2. Whitespace collapse off: whitespace is wrapped.
803             // 3. First, non-whitespace fragment is either wrapped or kept on the line. (depends on overflow-wrap)
804             // 5. Non-whitespace fragment when there's already another fragment on the line either gets wrapped (word-break: break-all)
805             // or gets pushed to the next line.
806             bool emptyLine = line.isEmpty();
807             // Whitespace fragment.
808             if (fragment.type() == TextFragmentIterator::TextFragment::Whitespace) {
809                 if (style.collapseWhitespace) {
810                     // Push collapased whitespace to the next line.
811                     line.setOverflowedFragment(fragment);
812                     break;
813                 }
814                 if (style.breakSpaces && line.hasWhitespaceFragments() && fragment.length() == 1) {
815                     // Breaking before the first space after a word is not allowed if there are previous breaking opportunities in the line.
816                     textFragmentIterator.revertToEndOfFragment(line.revertToLastCompleteFragment(runs));
817                     break;
818                 }
819                 if (preWrap(style)) {
820                     line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
821                     fragment = textFragmentIterator.nextTextFragment(line.width());
822                     if (fragment.isLineBreak())
823                         continue;
824                     line.setOverflowedFragment(fragment);
825                     break;
826                 }
827                 // Split the whitespace; left part stays on this line, right is pushed to next line.
828                 line.setOverflowedFragment(splitFragmentToFitLine(fragment, line, textFragmentIterator));
829                 line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
830                 break;
831             }
832             // Non-whitespace fragment. (!style.wrapLines: bug138102(preserve existing behavior)
833             if (((emptyLine && style.breakFirstWordOnOverflow) || style.breakAnyWordOnOverflow) || !style.wrapLines) {
834                 // Split the fragment; (modified)fragment stays on this line, overflowedFragment is pushed to next line.
835                 line.setOverflowedFragment(splitFragmentToFitLine(fragment, line, textFragmentIterator));
836                 line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
837                 break;
838             }
839             ASSERT(fragment.type() == TextFragmentIterator::TextFragment::NonWhitespace);
840             // Find out if this non-whitespace fragment has a hyphen where we can break.
841             if (style.shouldHyphenate) {
842                 auto fragmentToSplit = fragment;
843                 // Split and check if we actually ended up with a hyphen.
844                 auto overflowFragment = splitFragmentToFitLine(fragmentToSplit, line, textFragmentIterator);
845                 if (fragmentToSplit.hasHyphen()) {
846                     line.setOverflowedFragment(overflowFragment);
847                     line.appendFragmentAndCreateRunIfNeeded(fragmentToSplit, runs);
848                     break;
849                 }
850                 // No hyphen, no split.
851             }
852             // Non-breakable non-whitespace first fragment. Add it to the current line. -it overflows though.
853             if (emptyLine) {
854                 forceFragmentToLine(line, textFragmentIterator, runs, fragment);
855                 break;
856             }
857             // Non-breakable non-whitespace fragment when there's already content on the line. Push it to the next line.
858             ASSERT(line.lastFragment().isValid());
859             if (line.lastFragment().overlapsToNextRenderer()) {
860                 // Check if this fragment is a continuation of a previous segment. In such cases, we need to remove them all.
861                 textFragmentIterator.revertToEndOfFragment(line.revertToLastCompleteFragment(runs));
862                 break;
863             }
864             line.setOverflowedFragment(fragment);
865             break;
866         }
867         line.appendFragmentAndCreateRunIfNeeded(fragment, runs);
868         // Find the next text fragment.
869         fragment = textFragmentIterator.nextTextFragment(line.width());
870     }
871     return (fragment.type() == TextFragmentIterator::TextFragment::ContentEnd && line.overflowedFragment().isEmpty()) || line.overflowedFragment().type() == TextFragmentIterator::TextFragment::ContentEnd;
872 }
873
874 static ExpansionBehavior expansionBehavior(bool isAfterExpansion, bool lastRunOnLine)
875 {
876     ExpansionBehavior expansionBehavior;
877     expansionBehavior = isAfterExpansion ? ForbidLeadingExpansion : AllowLeadingExpansion;
878     expansionBehavior |= lastRunOnLine ? ForbidTrailingExpansion : AllowTrailingExpansion;
879     return expansionBehavior;
880 }
881
882 static void justifyRuns(const LineState& line, Layout::RunVector& runs, unsigned firstRunIndex)
883 {
884     ASSERT(runs.size());
885     auto widthToDistribute = line.availableWidth() - line.width();
886     if (widthToDistribute <= 0)
887         return;
888
889     auto lastRunIndex = runs.size() - 1;
890     ASSERT(firstRunIndex <= lastRunIndex);
891     Vector<std::pair<unsigned, ExpansionBehavior>> expansionOpportunityList;
892     unsigned expansionOpportunityCountOnThisLine = 0;
893     auto isAfterExpansion = true;
894     for (auto i = firstRunIndex; i <= lastRunIndex; ++i) {
895         const auto& run = runs.at(i);
896         unsigned opportunityCountInRun = 0;
897         std::tie(opportunityCountInRun, isAfterExpansion) = line.expansionOpportunityCount(run.start, run.end);
898         expansionOpportunityList.append(std::make_pair(opportunityCountInRun, expansionBehavior(isAfterExpansion, i == lastRunIndex)));
899         expansionOpportunityCountOnThisLine += opportunityCountInRun;
900     }
901     if (!expansionOpportunityCountOnThisLine)
902         return;
903
904     ASSERT(expansionOpportunityList.size() == lastRunIndex - firstRunIndex + 1);
905     auto expansion = widthToDistribute / expansionOpportunityCountOnThisLine;
906     float accumulatedExpansion = 0;
907     for (auto i = firstRunIndex; i <= lastRunIndex; ++i) {
908         auto& run = runs.at(i);
909         unsigned opportunityCountInRun;
910         std::tie(opportunityCountInRun, run.expansionBehavior) = expansionOpportunityList.at(i - firstRunIndex);
911         run.expansion = opportunityCountInRun * expansion;
912         run.logicalLeft += accumulatedExpansion;
913         run.logicalRight += (accumulatedExpansion + run.expansion);
914         accumulatedExpansion += run.expansion;
915     }
916 }
917
918 static TextAlignMode textAlignForLine(const TextFragmentIterator::Style& style, bool lastLine)
919 {
920     // Fallback to TextAlignMode::Left (START) alignment for non-collapsable content and for the last line before a forced break or the end of the block.
921     auto textAlign = style.textAlign;
922     if (textAlign == TextAlignMode::Justify && (!style.collapseWhitespace || lastLine))
923         textAlign = TextAlignMode::Left;
924     return textAlign;
925 }
926
927 static void closeLineEndingAndAdjustRuns(LineState& line, Layout::RunVector& runs, Optional<unsigned> lastRunIndexOfPreviousLine, unsigned& lineCount,
928     const TextFragmentIterator& textFragmentIterator, bool lastLineInFlow)
929 {
930     if (!runs.size() || (lastRunIndexOfPreviousLine && runs.size() - 1 == lastRunIndexOfPreviousLine.value()))
931         return;
932
933     const auto& style = textFragmentIterator.style();
934
935     if (style.collapseWhitespace)
936         line.removeTrailingWhitespace(runs);
937
938     if (!runs.size())
939         return;
940
941     // Adjust runs' position by taking line's alignment into account.
942     auto firstRunIndex = lastRunIndexOfPreviousLine ? lastRunIndexOfPreviousLine.value() + 1 : 0;
943     auto lineLogicalLeft = line.logicalLeftOffset();
944     auto textAlign = textAlignForLine(style, lastLineInFlow || (line.lastFragment().isValid() && line.lastFragment().type() == TextFragmentIterator::TextFragment::HardLineBreak));
945
946     // https://www.w3.org/TR/css-text-3/#white-space-phase-2
947     bool shouldHangTrailingWhitespace = style.wrapLines && line.trailingWhitespaceWidth();
948     auto hangingWhitespaceWidth = shouldHangTrailingWhitespace ? line.trailingWhitespaceWidth() : 0;
949
950     if (textAlign == TextAlignMode::Justify) {
951         justifyRuns(line, runs, firstRunIndex);
952         hangingWhitespaceWidth = 0;
953     } else
954         lineLogicalLeft = computeLineLeft(line, textAlign, hangingWhitespaceWidth);
955
956     for (auto i = firstRunIndex; i < runs.size(); ++i) {
957         runs[i].logicalLeft += lineLogicalLeft;
958         runs[i].logicalRight += lineLogicalLeft;
959     }
960
961     if (shouldHangTrailingWhitespace && hangingWhitespaceWidth < line.trailingWhitespaceWidth())
962         runs.last().logicalRight = runs.last().logicalRight - (line.trailingWhitespaceWidth() - hangingWhitespaceWidth);
963
964     runs.last().isEndOfLine = true;
965     ++lineCount;
966 }
967
968 static void createTextRuns(Layout::RunVector& runs, RenderBlockFlow& flow, unsigned& lineCount)
969 {
970     LayoutUnit borderAndPaddingBefore = flow.borderAndPaddingBefore();
971     LayoutUnit lineHeight = lineHeightFromFlow(flow);
972     LineState line;
973     unsigned numberOfPrecedingLinesWithHyphen = 0;
974     bool isEndOfContent = false;
975     TextFragmentIterator textFragmentIterator = TextFragmentIterator(flow);
976     Optional<unsigned> lastRunIndexOfPreviousLine;
977     do {
978         flow.setLogicalHeight(lineHeight * lineCount + borderAndPaddingBefore);
979         LineState previousLine = line;
980         line = LineState();
981         updateLineConstrains(flow, line, previousLine, numberOfPrecedingLinesWithHyphen, textFragmentIterator.style(), !lineCount);
982         isEndOfContent = createLineRuns(line, previousLine, runs, textFragmentIterator);
983         closeLineEndingAndAdjustRuns(line, runs, lastRunIndexOfPreviousLine, lineCount, textFragmentIterator, isEndOfContent);
984         if (runs.size())
985             lastRunIndexOfPreviousLine = runs.size() - 1;
986     } while (!isEndOfContent);
987 }
988
989 Ref<Layout> create(RenderBlockFlow& flow)
990 {
991     unsigned lineCount = 0;
992     Layout::RunVector runs;
993     createTextRuns(runs, flow, lineCount);
994     return Layout::create(runs, lineCount, flow);
995 }
996
997 Ref<Layout> Layout::create(const RunVector& runVector, unsigned lineCount, const RenderBlockFlow& blockFlow)
998 {
999     void* slot = WTF::fastMalloc(sizeof(Layout) + sizeof(Run) * runVector.size());
1000     return adoptRef(*new (NotNull, slot) Layout(runVector, lineCount, blockFlow));
1001 }
1002
1003 Layout::Layout(const RunVector& runVector, unsigned lineCount, const RenderBlockFlow& blockFlow)
1004     : m_lineCount(lineCount)
1005     , m_runCount(runVector.size())
1006     , m_blockFlowRenderer(blockFlow)
1007 {
1008     memcpy(m_runs, runVector.data(), m_runCount * sizeof(Run));
1009 }
1010
1011 const RunResolver& Layout::runResolver() const
1012 {
1013     if (!m_runResolver)
1014         m_runResolver = makeUnique<RunResolver>(m_blockFlowRenderer, *this);
1015     return *m_runResolver;
1016 }
1017
1018 Layout::~Layout()
1019 {
1020     simpleLineLayoutWillBeDeleted(*this);
1021 }
1022
1023 }
1024 }