Rename InlineBox::nextLeafChild to nextLeafOnLine
[WebKit-https.git] / Source / WebCore / rendering / ComplexLineLayout.cpp
1 /*
2  * Copyright (C) 2000 Lars Knoll (knoll@kde.org)
3  * Copyright (C) 2003-2019 Apple Inc. All right reserved.
4  * Copyright (C) 2010 Google Inc. All rights reserved.
5  * Copyright (C) 2013 ChangSeok Oh <shivamidow@gmail.com>
6  * Copyright (C) 2013 Adobe Systems Inc. All right reserved.
7  *
8  * This library is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Library General Public
10  * License as published by the Free Software Foundation; either
11  * version 2 of the License, or (at your option) any later version.
12  *
13  * This library is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16  * Library General Public License for more details.
17  *
18  * You should have received a copy of the GNU Library General Public License
19  * along with this library; see the file COPYING.LIB.  If not, write to
20  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
21  * Boston, MA 02110-1301, USA.
22  *
23  */
24
25 #include "config.h"
26 #include "ComplexLineLayout.h"
27
28 #include "AXObjectCache.h"
29 #include "BidiResolver.h"
30 #include "BreakingContext.h"
31 #include "FloatingObjects.h"
32 #include "HTMLParserIdioms.h"
33 #include "InlineElementBox.h"
34 #include "InlineIterator.h"
35 #include "InlineTextBox.h"
36 #include "InlineTextBoxStyle.h"
37 #include "LineLayoutState.h"
38 #include "Logging.h"
39 #include "RenderBlockFlow.h"
40 #include "RenderFragmentContainer.h"
41 #include "RenderFragmentedFlow.h"
42 #include "RenderLayoutState.h"
43 #include "RenderLineBreak.h"
44 #include "RenderRubyBase.h"
45 #include "RenderRubyText.h"
46 #include "RenderSVGText.h"
47 #include "RenderView.h"
48 #include "SVGRootInlineBox.h"
49 #include "Settings.h"
50 #include "TrailingFloatsRootInlineBox.h"
51 #include "VerticalPositionCache.h"
52 #include <wtf/StdLibExtras.h>
53
54 namespace WebCore {
55
56 ComplexLineLayout::ComplexLineLayout(RenderBlockFlow& flow)
57     : m_flow(flow)
58 {
59 }
60
61 ComplexLineLayout::~ComplexLineLayout() = default;
62
63 static void determineDirectionality(TextDirection& dir, InlineIterator iter)
64 {
65     while (!iter.atEnd()) {
66         if (iter.atParagraphSeparator())
67             return;
68         if (UChar current = iter.current()) {
69             UCharDirection charDirection = u_charDirection(current);
70             if (charDirection == U_LEFT_TO_RIGHT) {
71                 dir = TextDirection::LTR;
72                 return;
73             }
74             if (charDirection == U_RIGHT_TO_LEFT || charDirection == U_RIGHT_TO_LEFT_ARABIC) {
75                 dir = TextDirection::RTL;
76                 return;
77             }
78         }
79         iter.increment();
80     }
81 }
82
83 inline std::unique_ptr<BidiRun> createRun(int start, int end, RenderObject& obj, InlineBidiResolver& resolver)
84 {
85     return makeUnique<BidiRun>(start, end, obj, resolver.context(), resolver.dir());
86 }
87
88 void ComplexLineLayout::appendRunsForObject(BidiRunList<BidiRun>* runs, int start, int end, RenderObject& obj, InlineBidiResolver& resolver)
89 {
90     if (start > end || RenderBlock::shouldSkipCreatingRunsForObject(obj))
91         return;
92
93     LineWhitespaceCollapsingState& lineWhitespaceCollapsingState = resolver.whitespaceCollapsingState();
94     bool haveNextTransition = (lineWhitespaceCollapsingState.currentTransition() < lineWhitespaceCollapsingState.numTransitions());
95     InlineIterator nextTransition;
96     if (haveNextTransition)
97         nextTransition = lineWhitespaceCollapsingState.transitions()[lineWhitespaceCollapsingState.currentTransition()];
98     if (lineWhitespaceCollapsingState.betweenTransitions()) {
99         if (!haveNextTransition || (&obj != nextTransition.renderer()))
100             return;
101         // This is a new start point. Stop ignoring objects and
102         // adjust our start.
103         start = nextTransition.offset();
104         lineWhitespaceCollapsingState.incrementCurrentTransition();
105         if (start < end) {
106             appendRunsForObject(runs, start, end, obj, resolver);
107             return;
108         }
109     } else {
110         if (!haveNextTransition || (&obj != nextTransition.renderer())) {
111             if (runs)
112                 runs->appendRun(createRun(start, end, obj, resolver));
113             return;
114         }
115
116         // An end transition has been encountered within our object. We need to append a run with our endpoint.
117         if (static_cast<int>(nextTransition.offset() + 1) <= end) {
118             lineWhitespaceCollapsingState.incrementCurrentTransition();
119             // The end of the line is before the object we're inspecting. Skip everything and return
120             if (nextTransition.refersToEndOfPreviousNode())
121                 return;
122             if (static_cast<int>(nextTransition.offset() + 1) > start && runs)
123                 runs->appendRun(createRun(start, nextTransition.offset() + 1, obj, resolver));
124             appendRunsForObject(runs, nextTransition.offset() + 1, end, obj, resolver);
125         } else if (runs)
126             runs->appendRun(createRun(start, end, obj, resolver));
127     }
128 }
129
130 std::unique_ptr<RootInlineBox> ComplexLineLayout::createRootInlineBox()
131 {
132     if (is<RenderSVGText>(m_flow)) {
133         auto box = makeUnique<SVGRootInlineBox>(downcast<RenderSVGText>(m_flow));
134         box->setHasVirtualLogicalHeight();
135         return box;
136     }
137         
138     return makeUnique<RootInlineBox>(m_flow);
139 }
140
141 RootInlineBox* ComplexLineLayout::createAndAppendRootInlineBox()
142 {
143     auto newRootBox = createRootInlineBox();
144     RootInlineBox* rootBox = newRootBox.get();
145     m_lineBoxes.appendLineBox(WTFMove(newRootBox));
146
147     if (UNLIKELY(AXObjectCache::accessibilityEnabled()) && firstRootBox() == rootBox) {
148         if (AXObjectCache* cache = m_flow.document().existingAXObjectCache())
149             cache->deferRecomputeIsIgnored(m_flow.element());
150     }
151
152     return rootBox;
153 }
154
155 InlineBox* ComplexLineLayout::createInlineBoxForRenderer(RenderObject* renderer, bool isOnlyRun)
156 {
157     if (renderer == &m_flow)
158         return createAndAppendRootInlineBox();
159
160     if (is<RenderText>(*renderer))
161         return downcast<RenderText>(*renderer).createInlineTextBox();
162
163     if (is<RenderBox>(*renderer)) {
164         // FIXME: This is terrible. This branch returns an *owned* pointer!
165         return downcast<RenderBox>(*renderer).createInlineBox().release();
166     }
167
168     if (is<RenderLineBreak>(*renderer)) {
169         // FIXME: This is terrible. This branch returns an *owned* pointer!
170         auto inlineBox = downcast<RenderLineBreak>(*renderer).createInlineBox().release();
171         // We only treat a box as text for a <br> if we are on a line by ourself or in strict mode
172         // (Note the use of strict mode. In "almost strict" mode, we don't treat the box for <br> as text.)
173         inlineBox->setBehavesLikeText(isOnlyRun || renderer->document().inNoQuirksMode() || renderer->isLineBreakOpportunity());
174         return inlineBox;
175     }
176
177     return downcast<RenderInline>(*renderer).createAndAppendInlineFlowBox();
178 }
179
180 static inline void dirtyLineBoxesForRenderer(RenderObject& renderer, bool fullLayout)
181 {
182     if (is<RenderText>(renderer)) {
183         RenderText& renderText = downcast<RenderText>(renderer);
184         updateCounterIfNeeded(renderText);
185         renderText.dirtyLineBoxes(fullLayout);
186     } else if (is<RenderLineBreak>(renderer))
187         downcast<RenderLineBreak>(renderer).dirtyLineBoxes(fullLayout);
188     else
189         downcast<RenderInline>(renderer).dirtyLineBoxes(fullLayout);
190 }
191
192 static bool parentIsConstructedOrHaveNext(InlineFlowBox* parentBox)
193 {
194     do {
195         if (parentBox->isConstructed() || parentBox->nextOnLine())
196             return true;
197         parentBox = parentBox->parent();
198     } while (parentBox);
199     return false;
200 }
201
202 InlineFlowBox* ComplexLineLayout::createLineBoxes(RenderObject* obj, const LineInfo& lineInfo, InlineBox* childBox)
203 {
204     // See if we have an unconstructed line box for this object that is also
205     // the last item on the line.
206     unsigned lineDepth = 1;
207     InlineFlowBox* parentBox = nullptr;
208     InlineFlowBox* result = nullptr;
209     bool hasDefaultLineBoxContain = style().lineBoxContain() == RenderStyle::initialLineBoxContain();
210     do {
211         RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(is<RenderInline>(*obj) || obj == &m_flow);
212
213         RenderInline* inlineFlow = obj != &m_flow ? downcast<RenderInline>(obj) : nullptr;
214
215         // Get the last box we made for this render object.
216         parentBox = inlineFlow ? inlineFlow->lastLineBox() : downcast<RenderBlockFlow>(*obj).lastRootBox();
217
218         // If this box or its ancestor is constructed then it is from a previous line, and we need
219         // to make a new box for our line. If this box or its ancestor is unconstructed but it has
220         // something following it on the line, then we know we have to make a new box
221         // as well. In this situation our inline has actually been split in two on
222         // the same line (this can happen with very fancy language mixtures).
223         bool constructedNewBox = false;
224         bool allowedToConstructNewBox = !hasDefaultLineBoxContain || !inlineFlow || inlineFlow->alwaysCreateLineBoxes();
225         bool canUseExistingParentBox = parentBox && !parentIsConstructedOrHaveNext(parentBox);
226         if (allowedToConstructNewBox && !canUseExistingParentBox) {
227             // We need to make a new box for this render object. Once
228             // made, we need to place it at the end of the current line.
229             InlineBox* newBox = createInlineBoxForRenderer(obj);
230             parentBox = downcast<InlineFlowBox>(newBox);
231             parentBox->setIsFirstLine(lineInfo.isFirstLine());
232             parentBox->setIsHorizontal(m_flow.isHorizontalWritingMode());
233             if (!hasDefaultLineBoxContain)
234                 parentBox->clearDescendantsHaveSameLineHeightAndBaseline();
235             constructedNewBox = true;
236         }
237
238         if (constructedNewBox || canUseExistingParentBox) {
239             if (!result)
240                 result = parentBox;
241
242             // If we have hit the block itself, then |box| represents the root
243             // inline box for the line, and it doesn't have to be appended to any parent
244             // inline.
245             if (childBox)
246                 parentBox->addToLine(childBox);
247
248             if (!constructedNewBox || obj == &m_flow)
249                 break;
250
251             childBox = parentBox;
252         }
253
254         // If we've exceeded our line depth, then jump straight to the root and skip all the remaining
255         // intermediate inline flows.
256         obj = (++lineDepth >= cMaxLineDepth) ? &m_flow : obj->parent();
257
258     } while (true);
259
260     return result;
261 }
262
263 template<typename CharacterType> static inline bool endsWithHTMLSpaces(const CharacterType* characters, unsigned position, unsigned end)
264 {
265     for (unsigned i = position; i < end; ++i) {
266         if (!isHTMLSpace(characters[i]))
267             return false;
268     }
269     return true;
270 }
271
272 static bool reachedEndOfTextRenderer(const BidiRunList<BidiRun>& bidiRuns)
273 {
274     BidiRun* run = bidiRuns.logicallyLastRun();
275     if (!run)
276         return true;
277     if (!is<RenderText>(run->renderer()))
278         return false;
279     auto& text = downcast<RenderText>(run->renderer()).text();
280     unsigned position = run->stop();
281     unsigned length = text.length();
282     if (text.is8Bit())
283         return endsWithHTMLSpaces(text.characters8(), position, length);
284     return endsWithHTMLSpaces(text.characters16(), position, length);
285 }
286
287 RootInlineBox* ComplexLineLayout::constructLine(BidiRunList<BidiRun>& bidiRuns, const LineInfo& lineInfo)
288 {
289     ASSERT(bidiRuns.firstRun());
290
291     bool rootHasSelectedChildren = false;
292     InlineFlowBox* parentBox = 0;
293     int runCount = bidiRuns.runCount() - lineInfo.runsFromLeadingWhitespace();
294     
295     for (BidiRun* r = bidiRuns.firstRun(); r; r = r->next()) {
296         // Create a box for our object.
297         bool isOnlyRun = (runCount == 1);
298         if (runCount == 2 && !r->renderer().isListMarker())
299             isOnlyRun = (!style().isLeftToRightDirection() ? bidiRuns.lastRun() : bidiRuns.firstRun())->renderer().isListMarker();
300
301         if (lineInfo.isEmpty())
302             continue;
303
304         InlineBox* box = createInlineBoxForRenderer(&r->renderer(), isOnlyRun);
305         r->setBox(box);
306
307         if (!rootHasSelectedChildren && box->renderer().selectionState() != RenderObject::SelectionNone)
308             rootHasSelectedChildren = true;
309         
310         // If we have no parent box yet, or if the run is not simply a sibling,
311         // then we need to construct inline boxes as necessary to properly enclose the
312         // run's inline box. Segments can only be siblings at the root level, as
313         // they are positioned separately.
314         if (!parentBox || &parentBox->renderer() != r->renderer().parent()) {
315             // Create new inline boxes all the way back to the appropriate insertion point.
316             RenderObject* parentToUse = r->renderer().parent();
317             parentBox = createLineBoxes(parentToUse, lineInfo, box);
318         } else {
319             // Append the inline box to this line.
320             parentBox->addToLine(box);
321         }
322
323         bool visuallyOrdered = r->renderer().style().rtlOrdering() == Order::Visual;
324         box->setBidiLevel(r->level());
325
326         if (is<InlineTextBox>(*box)) {
327             auto& textBox = downcast<InlineTextBox>(*box);
328             textBox.setStart(r->m_start);
329             textBox.setLen(r->m_stop - r->m_start);
330             textBox.setDirOverride(r->dirOverride(visuallyOrdered));
331             if (r->m_hasHyphen)
332                 textBox.setHasHyphen(true);
333         }
334     }
335
336     // We should have a root inline box. It should be unconstructed and
337     // be the last continuation of our line list.
338     ASSERT(lastRootBox() && !lastRootBox()->isConstructed());
339
340     // Set the m_selectedChildren flag on the root inline box if one of the leaf inline box
341     // from the bidi runs walk above has a selection state.
342     if (rootHasSelectedChildren)
343         lastRootBox()->root().setHasSelectedChildren(true);
344
345     // Set bits on our inline flow boxes that indicate which sides should
346     // paint borders/margins/padding. This knowledge will ultimately be used when
347     // we determine the horizontal positions and widths of all the inline boxes on
348     // the line.
349     bool isLogicallyLastRunWrapped = bidiRuns.logicallyLastRun()->renderer().isText() ? !reachedEndOfTextRenderer(bidiRuns) : !is<RenderInline>(bidiRuns.logicallyLastRun()->renderer());
350     lastRootBox()->determineSpacingForFlowBoxes(lineInfo.isLastLine(), isLogicallyLastRunWrapped, &bidiRuns.logicallyLastRun()->renderer());
351
352     // Now mark the line boxes as being constructed.
353     lastRootBox()->setConstructed();
354
355     // Return the last line.
356     return lastRootBox();
357 }
358
359 TextAlignMode ComplexLineLayout::textAlignmentForLine(bool endsWithSoftBreak) const
360 {
361     if (auto overrideAlignment = m_flow.overrideTextAlignmentForLine(endsWithSoftBreak))
362         return *overrideAlignment;
363
364     TextAlignMode alignment = style().textAlign();
365 #if ENABLE(CSS3_TEXT)
366     TextJustify textJustify = style().textJustify();
367     if (alignment == TextAlignMode::Justify && textJustify == TextJustify::None)
368         return style().direction() == TextDirection::LTR ? TextAlignMode::Left : TextAlignMode::Right;
369 #endif
370
371     if (endsWithSoftBreak)
372         return alignment;
373
374 #if !ENABLE(CSS3_TEXT)
375     return (alignment == TextAlignMode::Justify) ? TextAlignMode::Start : alignment;
376 #else
377     if (alignment != TextAlignMode::Justify)
378         return alignment;
379
380     TextAlignLast alignmentLast = style().textAlignLast();
381     switch (alignmentLast) {
382     case TextAlignLast::Start:
383         return TextAlignMode::Start;
384     case TextAlignLast::End:
385         return TextAlignMode::End;
386     case TextAlignLast::Left:
387         return TextAlignMode::Left;
388     case TextAlignLast::Right:
389         return TextAlignMode::Right;
390     case TextAlignLast::Center:
391         return TextAlignMode::Center;
392     case TextAlignLast::Justify:
393         return TextAlignMode::Justify;
394     case TextAlignLast::Auto:
395         if (textJustify == TextJustify::Distribute)
396             return TextAlignMode::Justify;
397         return TextAlignMode::Start;
398     }
399     return alignment;
400 #endif
401 }
402
403 static void updateLogicalWidthForLeftAlignedBlock(bool isLeftToRightDirection, BidiRun* trailingSpaceRun, float& logicalLeft, float& totalLogicalWidth, float availableLogicalWidth)
404 {
405     // The direction of the block should determine what happens with wide lines.
406     // In particular with RTL blocks, wide lines should still spill out to the left.
407     if (isLeftToRightDirection) {
408         if (totalLogicalWidth > availableLogicalWidth && trailingSpaceRun)
409             trailingSpaceRun->box()->setLogicalWidth(std::max<float>(0, trailingSpaceRun->box()->logicalWidth() - totalLogicalWidth + availableLogicalWidth));
410         return;
411     }
412
413     if (trailingSpaceRun)
414         trailingSpaceRun->box()->setLogicalWidth(0);
415     else if (totalLogicalWidth > availableLogicalWidth)
416         logicalLeft -= (totalLogicalWidth - availableLogicalWidth);
417 }
418
419 static void updateLogicalWidthForRightAlignedBlock(bool isLeftToRightDirection, BidiRun* trailingSpaceRun, float& logicalLeft, float& totalLogicalWidth, float availableLogicalWidth)
420 {
421     // Wide lines spill out of the block based off direction.
422     // So even if text-align is right, if direction is LTR, wide lines should overflow out of the right
423     // side of the block.
424     if (isLeftToRightDirection) {
425         if (trailingSpaceRun) {
426             totalLogicalWidth -= trailingSpaceRun->box()->logicalWidth();
427             trailingSpaceRun->box()->setLogicalWidth(0);
428         }
429         logicalLeft += std::max(0.f, availableLogicalWidth - totalLogicalWidth);
430         return;
431     }
432
433     if (totalLogicalWidth > availableLogicalWidth && trailingSpaceRun) {
434         trailingSpaceRun->box()->setLogicalWidth(std::max<float>(0, trailingSpaceRun->box()->logicalWidth() - totalLogicalWidth + availableLogicalWidth));
435         totalLogicalWidth -= trailingSpaceRun->box()->logicalWidth();
436     } else
437         logicalLeft += availableLogicalWidth - totalLogicalWidth;
438 }
439
440 static void updateLogicalWidthForCenterAlignedBlock(bool isLeftToRightDirection, BidiRun* trailingSpaceRun, float& logicalLeft, float& totalLogicalWidth, float availableLogicalWidth)
441 {
442     float trailingSpaceWidth = 0;
443     if (trailingSpaceRun) {
444         totalLogicalWidth -= trailingSpaceRun->box()->logicalWidth();
445         trailingSpaceWidth = std::min(trailingSpaceRun->box()->logicalWidth(), (availableLogicalWidth - totalLogicalWidth + 1) / 2);
446         trailingSpaceRun->box()->setLogicalWidth(std::max<float>(0, trailingSpaceWidth));
447     }
448     if (isLeftToRightDirection)
449         logicalLeft += std::max<float>((availableLogicalWidth - totalLogicalWidth) / 2, 0);
450     else
451         logicalLeft += totalLogicalWidth > availableLogicalWidth ? (availableLogicalWidth - totalLogicalWidth) : (availableLogicalWidth - totalLogicalWidth) / 2 - trailingSpaceWidth;
452 }
453
454 void ComplexLineLayout::setMarginsForRubyRun(BidiRun* run, RenderRubyRun& renderer, RenderObject* previousObject, const LineInfo& lineInfo)
455 {
456     float startOverhang;
457     float endOverhang;
458     RenderObject* nextObject = 0;
459     for (BidiRun* runWithNextObject = run->next(); runWithNextObject; runWithNextObject = runWithNextObject->next()) {
460         if (!runWithNextObject->renderer().isOutOfFlowPositioned() && !runWithNextObject->box()->isLineBreak()) {
461             nextObject = &runWithNextObject->renderer();
462             break;
463         }
464     }
465     renderer.getOverhang(lineInfo.isFirstLine(), renderer.style().isLeftToRightDirection() ? previousObject : nextObject, renderer.style().isLeftToRightDirection() ? nextObject : previousObject, startOverhang, endOverhang);
466     m_flow.setMarginStartForChild(renderer, LayoutUnit(-startOverhang));
467     m_flow.setMarginEndForChild(renderer, LayoutUnit(-endOverhang));
468 }
469
470 static inline void setLogicalWidthForTextRun(RootInlineBox* lineBox, BidiRun* run, RenderText& renderer, float xPos, const LineInfo& lineInfo,
471     GlyphOverflowAndFallbackFontsMap& textBoxDataMap, VerticalPositionCache& verticalPositionCache, WordMeasurements& wordMeasurements)
472 {
473     HashSet<const Font*> fallbackFonts;
474     GlyphOverflow glyphOverflow;
475
476     const FontCascade& font = lineStyle(*renderer.parent(), lineInfo).fontCascade();
477     // Always compute glyph overflow if the block's line-box-contain value is "glyphs".
478     if (lineBox->fitsToGlyphs()) {
479         // If we don't stick out of the root line's font box, then don't bother computing our glyph overflow. This optimization
480         // will keep us from computing glyph bounds in nearly all cases.
481         bool includeRootLine = lineBox->includesRootLineBoxFontOrLeading();
482         int baselineShift = lineBox->verticalPositionForBox(run->box(), verticalPositionCache);
483         int rootDescent = includeRootLine ? font.fontMetrics().descent() : 0;
484         int rootAscent = includeRootLine ? font.fontMetrics().ascent() : 0;
485         int boxAscent = font.fontMetrics().ascent() - baselineShift;
486         int boxDescent = font.fontMetrics().descent() + baselineShift;
487         if (boxAscent > rootDescent ||  boxDescent > rootAscent)
488             glyphOverflow.computeBounds = true; 
489     }
490     
491     LayoutUnit hyphenWidth;
492     if (downcast<InlineTextBox>(*run->box()).hasHyphen())
493         hyphenWidth = measureHyphenWidth(renderer, font, &fallbackFonts);
494
495     float measuredWidth = 0;
496
497     bool kerningIsEnabled = font.enableKerning();
498     bool canUseSimpleFontCodePath = renderer.canUseSimpleFontCodePath();
499     
500     // Since we don't cache glyph overflows, we need to re-measure the run if
501     // the style is linebox-contain: glyph.
502     if (!lineBox->fitsToGlyphs() && canUseSimpleFontCodePath) {
503         unsigned lastEndOffset = run->m_start;
504         bool atFirstWordMeasurement = true;
505         for (size_t i = 0, size = wordMeasurements.size(); i < size && lastEndOffset < run->m_stop; ++i) {
506             WordMeasurement& wordMeasurement = wordMeasurements[i];
507             if (wordMeasurement.width <= 0 || wordMeasurement.startOffset == wordMeasurement.endOffset)
508                 continue;
509             if (wordMeasurement.renderer != &renderer || wordMeasurement.startOffset != lastEndOffset || wordMeasurement.endOffset > run->m_stop)
510                 continue;
511
512             lastEndOffset = wordMeasurement.endOffset;
513             if (kerningIsEnabled && lastEndOffset == run->m_stop) {
514                 int wordLength = lastEndOffset - wordMeasurement.startOffset;
515                 GlyphOverflow overflow;
516                 measuredWidth += renderer.width(wordMeasurement.startOffset, wordLength, xPos + measuredWidth, lineInfo.isFirstLine(),
517                     &wordMeasurement.fallbackFonts, &overflow);
518                 UChar c = renderer.characterAt(wordMeasurement.startOffset);
519                 // renderer.width() omits word-spacing value for leading whitespace, so let's just add it back here.
520                 if (!atFirstWordMeasurement && FontCascade::treatAsSpace(c))
521                     measuredWidth += renderer.style().fontCascade().wordSpacing();
522             } else
523                 measuredWidth += wordMeasurement.width;
524             atFirstWordMeasurement = false;
525
526             if (!wordMeasurement.fallbackFonts.isEmpty()) {
527                 HashSet<const Font*>::const_iterator end = wordMeasurement.fallbackFonts.end();
528                 for (HashSet<const Font*>::const_iterator it = wordMeasurement.fallbackFonts.begin(); it != end; ++it)
529                     fallbackFonts.add(*it);
530             }
531         }
532         if (measuredWidth && lastEndOffset != run->m_stop) {
533             // If we don't have enough cached data, we'll measure the run again.
534             measuredWidth = 0;
535             fallbackFonts.clear();
536         }
537     }
538
539     if (!measuredWidth)
540         measuredWidth = renderer.width(run->m_start, run->m_stop - run->m_start, xPos, lineInfo.isFirstLine(), &fallbackFonts, &glyphOverflow);
541
542     run->box()->setLogicalWidth(measuredWidth + hyphenWidth);
543     if (!fallbackFonts.isEmpty()) {
544         ASSERT(run->box()->behavesLikeText());
545         GlyphOverflowAndFallbackFontsMap::iterator it = textBoxDataMap.add(downcast<InlineTextBox>(run->box()), std::make_pair(Vector<const Font*>(), GlyphOverflow())).iterator;
546         ASSERT(it->value.first.isEmpty());
547         it->value.first = copyToVector(fallbackFonts);
548         run->box()->parent()->clearDescendantsHaveSameLineHeightAndBaseline();
549     }
550
551     // Include text decoration visual overflow as part of the glyph overflow.
552     if (!renderer.style().textDecorationsInEffect().isEmpty())
553         glyphOverflow.extendTo(visualOverflowForDecorations(run->box()->lineStyle(), downcast<InlineTextBox>(run->box())));
554
555     if (!glyphOverflow.isEmpty()) {
556         ASSERT(run->box()->behavesLikeText());
557         GlyphOverflowAndFallbackFontsMap::iterator it = textBoxDataMap.add(downcast<InlineTextBox>(run->box()), std::make_pair(Vector<const Font*>(), GlyphOverflow())).iterator;
558         it->value.second = glyphOverflow;
559         run->box()->clearKnownToHaveNoOverflow();
560     }
561 }
562
563 void ComplexLineLayout::updateRubyForJustifiedText(RenderRubyRun& rubyRun, BidiRun& r, const Vector<unsigned, 16>& expansionOpportunities, unsigned& expansionOpportunityCount, float& totalLogicalWidth, float availableLogicalWidth, size_t& i)
564 {
565     if (!rubyRun.rubyBase() || !rubyRun.rubyBase()->firstRootBox() || rubyRun.rubyBase()->firstRootBox()->nextRootBox() || !r.renderer().style().collapseWhiteSpace())
566         return;
567
568     auto& rubyBase = *rubyRun.rubyBase();
569     auto& rootBox = *rubyBase.firstRootBox();
570
571     float totalExpansion = 0;
572     unsigned totalOpportunitiesInRun = 0;
573     for (auto* leafChild = rootBox.firstLeafDescendant(); leafChild; leafChild = leafChild->nextLeafOnLine()) {
574         if (!leafChild->isInlineTextBox())
575             continue;
576
577         unsigned opportunitiesInRun = expansionOpportunities[i++];
578         ASSERT(opportunitiesInRun <= expansionOpportunityCount);
579         auto expansion = (availableLogicalWidth - totalLogicalWidth) * opportunitiesInRun / expansionOpportunityCount;
580         totalExpansion += expansion;
581         totalOpportunitiesInRun += opportunitiesInRun;
582     }
583
584     ASSERT(!rubyRun.hasOverrideContentLogicalWidth());
585     float newBaseWidth = rubyRun.logicalWidth() + totalExpansion + m_flow.marginStartForChild(rubyRun) + m_flow.marginEndForChild(rubyRun);
586     float newRubyRunWidth = rubyRun.logicalWidth() + totalExpansion;
587     rubyBase.setInitialOffset((newRubyRunWidth - newBaseWidth) / 2);
588     rubyRun.setOverrideContentLogicalWidth(LayoutUnit(newRubyRunWidth));
589     rubyRun.setNeedsLayout(MarkOnlyThis);
590     rootBox.markDirty();
591     if (RenderRubyText* rubyText = rubyRun.rubyText()) {
592         if (RootInlineBox* textRootBox = rubyText->firstRootBox())
593             textRootBox->markDirty();
594     }
595     rubyRun.layoutBlock(true);
596     rubyRun.clearOverrideContentLogicalWidth();
597     r.box()->setExpansion(newRubyRunWidth - r.box()->logicalWidth());
598
599     totalLogicalWidth += totalExpansion;
600     expansionOpportunityCount -= totalOpportunitiesInRun;
601 }
602
603 void ComplexLineLayout::computeExpansionForJustifiedText(BidiRun* firstRun, BidiRun* trailingSpaceRun, const Vector<unsigned, 16>& expansionOpportunities, unsigned expansionOpportunityCount, float totalLogicalWidth, float availableLogicalWidth)
604 {
605     if (!expansionOpportunityCount || availableLogicalWidth <= totalLogicalWidth)
606         return;
607
608     size_t i = 0;
609     for (BidiRun* run = firstRun; run; run = run->next()) {
610         if (!run->box() || run == trailingSpaceRun)
611             continue;
612         
613         if (is<RenderText>(run->renderer())) {
614             unsigned opportunitiesInRun = expansionOpportunities[i++];
615             
616             ASSERT(opportunitiesInRun <= expansionOpportunityCount);
617             
618             // Only justify text if whitespace is collapsed.
619             if (run->renderer().style().collapseWhiteSpace()) {
620                 InlineTextBox& textBox = downcast<InlineTextBox>(*run->box());
621                 float expansion = (availableLogicalWidth - totalLogicalWidth) * opportunitiesInRun / expansionOpportunityCount;
622                 textBox.setExpansion(expansion);
623                 totalLogicalWidth += expansion;
624             }
625             expansionOpportunityCount -= opportunitiesInRun;
626         } else if (is<RenderRubyRun>(run->renderer()))
627             updateRubyForJustifiedText(downcast<RenderRubyRun>(run->renderer()), *run, expansionOpportunities, expansionOpportunityCount, totalLogicalWidth, availableLogicalWidth, i);
628
629         if (!expansionOpportunityCount)
630             break;
631     }
632 }
633
634 void ComplexLineLayout::updateLogicalWidthForAlignment(RenderBlockFlow& flow, const TextAlignMode& textAlign, const RootInlineBox* rootInlineBox, BidiRun* trailingSpaceRun, float& logicalLeft, float& totalLogicalWidth, float& availableLogicalWidth, int expansionOpportunityCount)
635 {
636     TextDirection direction;
637     if (rootInlineBox && flow.style().unicodeBidi() == Plaintext)
638         direction = rootInlineBox->direction();
639     else
640         direction = flow.style().direction();
641
642     bool isLeftToRightDirection = flow.style().isLeftToRightDirection();
643
644     // Armed with the total width of the line (without justification),
645     // we now examine our text-align property in order to determine where to position the
646     // objects horizontally. The total width of the line can be increased if we end up
647     // justifying text.
648     switch (textAlign) {
649     case TextAlignMode::Left:
650     case TextAlignMode::WebKitLeft:
651         updateLogicalWidthForLeftAlignedBlock(isLeftToRightDirection, trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
652         break;
653     case TextAlignMode::Right:
654     case TextAlignMode::WebKitRight:
655         updateLogicalWidthForRightAlignedBlock(isLeftToRightDirection, trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
656         break;
657     case TextAlignMode::Center:
658     case TextAlignMode::WebKitCenter:
659         updateLogicalWidthForCenterAlignedBlock(isLeftToRightDirection, trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
660         break;
661     case TextAlignMode::Justify:
662         flow.adjustInlineDirectionLineBounds(expansionOpportunityCount, logicalLeft, availableLogicalWidth);
663         if (expansionOpportunityCount) {
664             if (trailingSpaceRun) {
665                 totalLogicalWidth -= trailingSpaceRun->box()->logicalWidth();
666                 trailingSpaceRun->box()->setLogicalWidth(0);
667             }
668             break;
669         }
670         FALLTHROUGH;
671     case TextAlignMode::Start:
672         if (direction == TextDirection::LTR)
673             updateLogicalWidthForLeftAlignedBlock(isLeftToRightDirection, trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
674         else
675             updateLogicalWidthForRightAlignedBlock(isLeftToRightDirection, trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
676         break;
677     case TextAlignMode::End:
678         if (direction == TextDirection::LTR)
679             updateLogicalWidthForRightAlignedBlock(isLeftToRightDirection, trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
680         else
681             updateLogicalWidthForLeftAlignedBlock(isLeftToRightDirection, trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
682         break;
683     }
684 }
685
686 static void updateLogicalInlinePositions(RenderBlockFlow& block, float& lineLogicalLeft, float& lineLogicalRight, float& availableLogicalWidth, bool firstLine,
687     IndentTextOrNot shouldIndentText, LayoutUnit boxLogicalHeight)
688 {
689     LayoutUnit lineLogicalHeight = block.minLineHeightForReplacedRenderer(firstLine, boxLogicalHeight);
690     lineLogicalLeft = block.logicalLeftOffsetForLine(block.logicalHeight(), shouldIndentText, lineLogicalHeight);
691     lineLogicalRight = block.logicalRightOffsetForLine(block.logicalHeight(), shouldIndentText, lineLogicalHeight);
692     availableLogicalWidth = lineLogicalRight - lineLogicalLeft;
693 }
694
695 void ComplexLineLayout::computeInlineDirectionPositionsForLine(RootInlineBox* lineBox, const LineInfo& lineInfo, BidiRun* firstRun, BidiRun* trailingSpaceRun, bool reachedEnd, GlyphOverflowAndFallbackFontsMap& textBoxDataMap, VerticalPositionCache& verticalPositionCache, WordMeasurements& wordMeasurements)
696 {
697     TextAlignMode textAlign = textAlignmentForLine(!reachedEnd && !lineBox->endsWithBreak());
698     
699     // CSS 2.1: "'Text-indent' only affects a line if it is the first formatted line of an element. For example, the first line of an anonymous block 
700     // box is only affected if it is the first child of its parent element."
701     // CSS3 "text-indent", "-webkit-each-line" affects the first line of the block container as well as each line after a forced line break,
702     // but does not affect lines after a soft wrap break.
703     bool isFirstLine = lineInfo.isFirstLine() && !(m_flow.isAnonymousBlock() && m_flow.parent()->firstChild() != &m_flow);
704     bool isAfterHardLineBreak = lineBox->prevRootBox() && lineBox->prevRootBox()->endsWithBreak();
705     IndentTextOrNot shouldIndentText = requiresIndent(isFirstLine, isAfterHardLineBreak, style());
706     float lineLogicalLeft;
707     float lineLogicalRight;
708     float availableLogicalWidth;
709     updateLogicalInlinePositions(m_flow, lineLogicalLeft, lineLogicalRight, availableLogicalWidth, isFirstLine, shouldIndentText, 0);
710     bool needsWordSpacing;
711
712     if (firstRun && firstRun->renderer().isReplaced()) {
713         RenderBox& renderBox = downcast<RenderBox>(firstRun->renderer());
714         updateLogicalInlinePositions(m_flow, lineLogicalLeft, lineLogicalRight, availableLogicalWidth, isFirstLine, shouldIndentText, renderBox.logicalHeight());
715     }
716
717     computeInlineDirectionPositionsForSegment(lineBox, lineInfo, textAlign, lineLogicalLeft, availableLogicalWidth, firstRun, trailingSpaceRun, textBoxDataMap, verticalPositionCache, wordMeasurements);
718     // The widths of all runs are now known. We can now place every inline box (and
719     // compute accurate widths for the inline flow boxes).
720     needsWordSpacing = false;
721     lineBox->placeBoxesInInlineDirection(lineLogicalLeft, needsWordSpacing);
722 }
723
724 static inline ExpansionBehavior expansionBehaviorForInlineTextBox(RenderBlockFlow& block, InlineTextBox& textBox, BidiRun* previousRun, BidiRun* nextRun, TextAlignMode textAlign, bool isAfterExpansion)
725 {
726     // Tatechuyoko is modeled as the Object Replacement Character (U+FFFC), which can never have expansion opportunities inside nor intrinsically adjacent to it.
727     if (textBox.renderer().style().textCombine() == TextCombine::Horizontal)
728         return ForbidLeadingExpansion | ForbidTrailingExpansion;
729
730     ExpansionBehavior result = 0;
731     bool setLeadingExpansion = false;
732     bool setTrailingExpansion = false;
733     if (textAlign == TextAlignMode::Justify) {
734         // If the next box is ruby, and we're justifying, and the first box in the ruby base has a leading expansion, and we are a text box, then force a trailing expansion.
735         if (nextRun && is<RenderRubyRun>(nextRun->renderer()) && downcast<RenderRubyRun>(nextRun->renderer()).rubyBase() && nextRun->renderer().style().collapseWhiteSpace()) {
736             auto& rubyBase = *downcast<RenderRubyRun>(nextRun->renderer()).rubyBase();
737             if (rubyBase.firstRootBox() && !rubyBase.firstRootBox()->nextRootBox()) {
738                 if (auto* leafChild = rubyBase.firstRootBox()->firstLeafDescendant()) {
739                     if (is<InlineTextBox>(*leafChild)) {
740                         // FIXME: This leadingExpansionOpportunity doesn't actually work because it doesn't perform the UBA
741                         if (FontCascade::leadingExpansionOpportunity(downcast<RenderText>(leafChild->renderer()).stringView(), leafChild->direction())) {
742                             setTrailingExpansion = true;
743                             result |= ForceTrailingExpansion;
744                         }
745                     }
746                 }
747             }
748         }
749         // Same thing, except if we're following a ruby
750         if (previousRun && is<RenderRubyRun>(previousRun->renderer()) && downcast<RenderRubyRun>(previousRun->renderer()).rubyBase() && previousRun->renderer().style().collapseWhiteSpace()) {
751             auto& rubyBase = *downcast<RenderRubyRun>(previousRun->renderer()).rubyBase();
752             if (rubyBase.firstRootBox() && !rubyBase.firstRootBox()->nextRootBox()) {
753                 if (auto* leafChild = rubyBase.firstRootBox()->lastLeafDescendant()) {
754                     if (is<InlineTextBox>(*leafChild)) {
755                         // FIXME: This leadingExpansionOpportunity doesn't actually work because it doesn't perform the UBA
756                         if (FontCascade::trailingExpansionOpportunity(downcast<RenderText>(leafChild->renderer()).stringView(), leafChild->direction())) {
757                             setLeadingExpansion = true;
758                             result |= ForceLeadingExpansion;
759                         }
760                     }
761                 }
762             }
763         }
764         // If we're the first box inside a ruby base, forbid a leading expansion, and vice-versa
765         if (is<RenderRubyBase>(block)) {
766             RenderRubyBase& rubyBase = downcast<RenderRubyBase>(block);
767             if (&textBox == rubyBase.firstRootBox()->firstLeafDescendant()) {
768                 setLeadingExpansion = true;
769                 result |= ForbidLeadingExpansion;
770             } if (&textBox == rubyBase.firstRootBox()->lastLeafDescendant()) {
771                 setTrailingExpansion = true;
772                 result |= ForbidTrailingExpansion;
773             }
774         }
775     }
776     if (!setLeadingExpansion)
777         result |= isAfterExpansion ? ForbidLeadingExpansion : AllowLeadingExpansion;
778     if (!setTrailingExpansion)
779         result |= AllowTrailingExpansion;
780     return result;
781 }
782
783 static inline void applyExpansionBehavior(InlineTextBox& textBox, ExpansionBehavior expansionBehavior)
784 {
785     switch (expansionBehavior & LeadingExpansionMask) {
786     case ForceLeadingExpansion:
787         textBox.setForceLeadingExpansion();
788         break;
789     case ForbidLeadingExpansion:
790         textBox.setCanHaveLeadingExpansion(false);
791         break;
792     case AllowLeadingExpansion:
793         textBox.setCanHaveLeadingExpansion(true);
794         break;
795     default:
796         ASSERT_NOT_REACHED();
797         break;
798     }
799     switch (expansionBehavior & TrailingExpansionMask) {
800     case ForceTrailingExpansion:
801         textBox.setForceTrailingExpansion();
802         break;
803     case ForbidTrailingExpansion:
804         textBox.setCanHaveTrailingExpansion(false);
805         break;
806     case AllowTrailingExpansion:
807         textBox.setCanHaveTrailingExpansion(true);
808         break;
809     default:
810         ASSERT_NOT_REACHED();
811         break;
812     }
813 }
814
815 static bool inlineAncestorHasStartBorderPaddingOrMargin(const RenderBlockFlow& block, const InlineBox& box)
816 {
817     bool isLTR = block.style().isLeftToRightDirection();
818     for (auto* currentBox = box.parent(); currentBox; currentBox = currentBox->parent()) {
819         if ((isLTR && currentBox->marginBorderPaddingLogicalLeft() > 0)
820             || (!isLTR && currentBox->marginBorderPaddingLogicalRight() > 0))
821             return true;
822     }
823     return false;
824 }
825
826 static bool inlineAncestorHasEndBorderPaddingOrMargin(const RenderBlockFlow& block, const InlineBox& box)
827 {
828     bool isLTR = block.style().isLeftToRightDirection();
829     for (auto* currentBox = box.parent(); currentBox; currentBox = currentBox->parent()) {
830         if ((isLTR && currentBox->marginBorderPaddingLogicalRight() > 0)
831             || (!isLTR && currentBox->marginBorderPaddingLogicalLeft() > 0))
832             return true;
833     }
834     return false;
835 }
836     
837 static bool isLastInFlowRun(BidiRun& runToCheck)
838 {
839     for (auto* run = runToCheck.next(); run; run = run->next()) {
840         if (!run->box() || run->renderer().isOutOfFlowPositioned() || run->box()->isLineBreak())
841             continue;
842         return false;
843     }
844     return true;
845 }
846     
847 BidiRun* ComplexLineLayout::computeInlineDirectionPositionsForSegment(RootInlineBox* lineBox, const LineInfo& lineInfo, TextAlignMode textAlign, float& logicalLeft,
848     float& availableLogicalWidth, BidiRun* firstRun, BidiRun* trailingSpaceRun, GlyphOverflowAndFallbackFontsMap& textBoxDataMap, VerticalPositionCache& verticalPositionCache,
849     WordMeasurements& wordMeasurements)
850 {
851     bool needsWordSpacing = false;
852     bool canHangPunctuationAtStart = style().hangingPunctuation().contains(HangingPunctuation::First);
853     bool canHangPunctuationAtEnd = style().hangingPunctuation().contains(HangingPunctuation::Last);
854     bool isLTR = style().isLeftToRightDirection();
855     float totalLogicalWidth = lineBox->getFlowSpacingLogicalWidth();
856     unsigned expansionOpportunityCount = 0;
857     bool isAfterExpansion = is<RenderRubyBase>(m_flow) ? downcast<RenderRubyBase>(m_flow).isAfterExpansion() : true;
858     Vector<unsigned, 16> expansionOpportunities;
859
860     BidiRun* run = firstRun;
861     BidiRun* previousRun = nullptr;
862     for (; run; run = run->next()) {
863         auto computeExpansionOpportunities = [&expansionOpportunities, &expansionOpportunityCount, textAlign, &isAfterExpansion] (RenderBlockFlow& block,
864             InlineTextBox& textBox, BidiRun* previousRun, BidiRun* nextRun, const StringView& stringView, TextDirection direction)
865         {
866             if (stringView.isEmpty()) {
867                 // Empty runs should still produce an entry in expansionOpportunities list so that the number of items matches the number of runs.
868                 expansionOpportunities.append(0);
869                 return;
870             }
871             ExpansionBehavior expansionBehavior = expansionBehaviorForInlineTextBox(block, textBox, previousRun, nextRun, textAlign, isAfterExpansion);
872             applyExpansionBehavior(textBox, expansionBehavior);
873             unsigned opportunitiesInRun;
874             std::tie(opportunitiesInRun, isAfterExpansion) = FontCascade::expansionOpportunityCount(stringView, direction, expansionBehavior);
875             expansionOpportunities.append(opportunitiesInRun);
876             expansionOpportunityCount += opportunitiesInRun;
877         };
878         if (!run->box() || run->renderer().isOutOfFlowPositioned() || run->box()->isLineBreak()) {
879             // Positioned objects are only participating to figure out their correct static x position.
880             // They have no effect on the width. Similarly, line break boxes have no effect on the width.
881             continue;
882         }
883         if (is<RenderText>(run->renderer())) {
884             auto& renderText = downcast<RenderText>(run->renderer());
885             auto& textBox = downcast<InlineTextBox>(*run->box());
886             if (canHangPunctuationAtStart && lineInfo.isFirstLine() && (isLTR || isLastInFlowRun(*run))
887                 && !inlineAncestorHasStartBorderPaddingOrMargin(m_flow, *run->box())) {
888                 float hangStartWidth = renderText.hangablePunctuationStartWidth(run->m_start);
889                 availableLogicalWidth += hangStartWidth;
890                 if (style().isLeftToRightDirection())
891                     logicalLeft -= hangStartWidth;
892                 canHangPunctuationAtStart = false;
893             }
894             
895             if (canHangPunctuationAtEnd && lineInfo.isLastLine() && run->m_stop > 0 && (!isLTR || isLastInFlowRun(*run))
896                 && !inlineAncestorHasEndBorderPaddingOrMargin(m_flow, *run->box())) {
897                 float hangEndWidth = renderText.hangablePunctuationEndWidth(run->m_stop - 1);
898                 availableLogicalWidth += hangEndWidth;
899                 if (!style().isLeftToRightDirection())
900                     logicalLeft -= hangEndWidth;
901                 canHangPunctuationAtEnd = false;
902             }
903             
904             if (textAlign == TextAlignMode::Justify && run != trailingSpaceRun)
905                 computeExpansionOpportunities(m_flow, textBox, previousRun, run->next(), renderText.stringView(run->m_start, run->m_stop), run->box()->direction());
906
907             if (unsigned length = renderText.text().length()) {
908                 if (!run->m_start && needsWordSpacing && isSpaceOrNewline(renderText.characterAt(run->m_start)))
909                     totalLogicalWidth += lineStyle(*renderText.parent(), lineInfo).fontCascade().wordSpacing();
910                 // run->m_start == run->m_stop should only be true iff the run is a replaced run for bidi: isolate.
911                 ASSERT(run->m_stop > 0 || run->m_start == run->m_stop);
912                 needsWordSpacing = run->m_stop == length && !isSpaceOrNewline(renderText.characterAt(run->m_stop - 1));
913             }
914
915             setLogicalWidthForTextRun(lineBox, run, renderText, totalLogicalWidth, lineInfo, textBoxDataMap, verticalPositionCache, wordMeasurements);
916         } else {
917             canHangPunctuationAtStart = false;
918             bool encounteredJustifiedRuby = false;
919             if (is<RenderRubyRun>(run->renderer()) && textAlign == TextAlignMode::Justify && run != trailingSpaceRun && downcast<RenderRubyRun>(run->renderer()).rubyBase()) {
920                 auto* rubyBase = downcast<RenderRubyRun>(run->renderer()).rubyBase();
921                 if (rubyBase->firstRootBox() && !rubyBase->firstRootBox()->nextRootBox() && run->renderer().style().collapseWhiteSpace()) {
922                     rubyBase->setIsAfterExpansion(isAfterExpansion);
923                     for (auto* leafChild = rubyBase->firstRootBox()->firstLeafDescendant(); leafChild; leafChild = leafChild->nextLeafOnLine()) {
924                         if (!is<InlineTextBox>(*leafChild))
925                             continue;
926                         encounteredJustifiedRuby = true;
927                         computeExpansionOpportunities(*rubyBase, downcast<InlineTextBox>(*leafChild), nullptr, nullptr,
928                             downcast<RenderText>(leafChild->renderer()).stringView(), leafChild->direction());
929                     }
930                 }
931             }
932
933             if (!encounteredJustifiedRuby)
934                 isAfterExpansion = false;
935
936             if (!is<RenderInline>(run->renderer())) {
937                 auto& renderBox = downcast<RenderBox>(run->renderer());
938                 if (is<RenderRubyRun>(renderBox))
939                     setMarginsForRubyRun(run, downcast<RenderRubyRun>(renderBox), previousRun ? &previousRun->renderer() : nullptr, lineInfo);
940                 run->box()->setLogicalWidth(m_flow.logicalWidthForChild(renderBox));
941                 totalLogicalWidth += m_flow.marginStartForChild(renderBox) + m_flow.marginEndForChild(renderBox);
942             }
943         }
944
945         totalLogicalWidth += run->box()->logicalWidth();
946         previousRun = run;
947     }
948
949     if (isAfterExpansion && !expansionOpportunities.isEmpty()) {
950         // FIXME: see <webkit.org/b/139393#c11>
951         int lastValidExpansionOpportunitiesIndex = expansionOpportunities.size() - 1;
952         while (lastValidExpansionOpportunitiesIndex >= 0 && !expansionOpportunities.at(lastValidExpansionOpportunitiesIndex))
953             --lastValidExpansionOpportunitiesIndex;
954         if (lastValidExpansionOpportunitiesIndex >= 0) {
955             ASSERT(expansionOpportunities.at(lastValidExpansionOpportunitiesIndex));
956             expansionOpportunities.at(lastValidExpansionOpportunitiesIndex)--;
957             expansionOpportunityCount--;
958         }
959     }
960
961     if (is<RenderRubyBase>(m_flow) && !expansionOpportunityCount)
962         textAlign = TextAlignMode::Center;
963
964     updateLogicalWidthForAlignment(m_flow, textAlign, lineBox, trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth, expansionOpportunityCount);
965
966     computeExpansionForJustifiedText(firstRun, trailingSpaceRun, expansionOpportunities, expansionOpportunityCount, totalLogicalWidth, availableLogicalWidth);
967
968     return run;
969 }
970
971 void ComplexLineLayout::removeInlineBox(BidiRun& run, const RootInlineBox& rootLineBox) const
972 {
973     auto* inlineBox = run.box();
974 #if !ASSERT_DISABLED
975     auto* inlineParent = inlineBox->parent();
976     while (inlineParent && inlineParent != &rootLineBox) {
977         ASSERT(!inlineParent->isDirty());
978         inlineParent = inlineParent->parent();
979     }
980     ASSERT(!rootLineBox.isDirty());
981 #endif
982     auto* parent = inlineBox->parent();
983     inlineBox->removeFromParent();
984
985     auto& renderer = run.renderer();
986     if (is<RenderText>(renderer))
987         downcast<RenderText>(renderer).removeTextBox(downcast<InlineTextBox>(*inlineBox));
988     delete inlineBox;
989     run.setBox(nullptr);
990     // removeFromParent() unnecessarily dirties the ancestor subtree.
991     auto* ancestor = parent;
992     while (ancestor) {
993         ancestor->markDirty(false);
994         if (ancestor == &rootLineBox)
995             break;
996         ancestor = ancestor->parent();
997     }
998 }
999
1000 void ComplexLineLayout::computeBlockDirectionPositionsForLine(RootInlineBox* lineBox, BidiRun* firstRun, GlyphOverflowAndFallbackFontsMap& textBoxDataMap, VerticalPositionCache& verticalPositionCache)
1001 {
1002     m_flow.setLogicalHeight(lineBox->alignBoxesInBlockDirection(m_flow.logicalHeight(), textBoxDataMap, verticalPositionCache));
1003
1004     // Now make sure we place replaced render objects correctly.
1005     for (auto* run = firstRun; run; run = run->next()) {
1006         ASSERT(run->box());
1007         if (!run->box())
1008             continue; // Skip runs with no line boxes.
1009
1010         // Align positioned boxes with the top of the line box. This is
1011         // a reasonable approximation of an appropriate y position.
1012         auto& renderer = run->renderer();
1013         if (renderer.isOutOfFlowPositioned())
1014             run->box()->setLogicalTop(m_flow.logicalHeight());
1015
1016         // Position is used to properly position both replaced elements and
1017         // to update the static normal flow x/y of positioned elements.
1018         bool inlineBoxIsRedundant = false;
1019         if (is<RenderText>(renderer)) {
1020             auto& inlineTextBox = downcast<InlineTextBox>(*run->box());
1021             downcast<RenderText>(renderer).positionLineBox(inlineTextBox);
1022             inlineBoxIsRedundant = !inlineTextBox.hasTextContent();
1023         } else if (is<RenderBox>(renderer)) {
1024             downcast<RenderBox>(renderer).positionLineBox(downcast<InlineElementBox>(*run->box()));
1025             inlineBoxIsRedundant = renderer.isOutOfFlowPositioned();
1026         } else if (is<RenderLineBreak>(renderer))
1027             downcast<RenderLineBreak>(renderer).replaceInlineBoxWrapper(downcast<InlineElementBox>(*run->box()));
1028         // Check if we need to keep this box on the line at all.
1029         if (inlineBoxIsRedundant)
1030             removeInlineBox(*run, *lineBox);
1031     }
1032 }
1033
1034 static inline bool isCollapsibleSpace(UChar character, const RenderText& renderer)
1035 {
1036     if (character == ' ' || character == '\t' || character == softHyphen)
1037         return true;
1038     if (character == '\n')
1039         return !renderer.style().preserveNewline();
1040     if (character == noBreakSpace)
1041         return renderer.style().nbspMode() == NBSPMode::Space;
1042     return false;
1043 }
1044
1045 template <typename CharacterType>
1046 static inline unsigned findFirstTrailingSpace(const RenderText& lastText, const CharacterType* characters, unsigned start, unsigned stop)
1047 {
1048     unsigned firstSpace = stop;
1049     while (firstSpace > start) {
1050         UChar current = characters[firstSpace - 1];
1051         if (!isCollapsibleSpace(current, lastText))
1052             break;
1053         firstSpace--;
1054     }
1055
1056     return firstSpace;
1057 }
1058
1059 inline BidiRun* ComplexLineLayout::handleTrailingSpaces(BidiRunList<BidiRun>& bidiRuns, BidiContext* currentContext)
1060 {
1061     if (!bidiRuns.runCount()
1062         || !bidiRuns.logicallyLastRun()->renderer().style().breakOnlyAfterWhiteSpace()
1063         || !bidiRuns.logicallyLastRun()->renderer().style().autoWrap())
1064         return nullptr;
1065
1066     BidiRun* trailingSpaceRun = bidiRuns.logicallyLastRun();
1067     const RenderObject& lastObject = trailingSpaceRun->renderer();
1068     if (!is<RenderText>(lastObject))
1069         return nullptr;
1070
1071     const RenderText& lastText = downcast<RenderText>(lastObject);
1072     unsigned firstSpace;
1073     if (lastText.text().is8Bit())
1074         firstSpace = findFirstTrailingSpace(lastText, lastText.text().characters8(), trailingSpaceRun->start(), trailingSpaceRun->stop());
1075     else
1076         firstSpace = findFirstTrailingSpace(lastText, lastText.text().characters16(), trailingSpaceRun->start(), trailingSpaceRun->stop());
1077
1078     if (firstSpace == trailingSpaceRun->stop())
1079         return nullptr;
1080
1081     TextDirection direction = style().direction();
1082     bool shouldReorder = trailingSpaceRun != (direction == TextDirection::LTR ? bidiRuns.lastRun() : bidiRuns.firstRun());
1083     if (firstSpace != trailingSpaceRun->start()) {
1084         BidiContext* baseContext = currentContext;
1085         while (BidiContext* parent = baseContext->parent())
1086             baseContext = parent;
1087
1088         std::unique_ptr<BidiRun> newTrailingRun = makeUnique<BidiRun>(firstSpace, trailingSpaceRun->m_stop, trailingSpaceRun->renderer(), baseContext, U_OTHER_NEUTRAL);
1089         trailingSpaceRun->m_stop = firstSpace;
1090         trailingSpaceRun = newTrailingRun.get();
1091         if (direction == TextDirection::LTR)
1092             bidiRuns.appendRun(WTFMove(newTrailingRun));
1093         else
1094             bidiRuns.prependRun(WTFMove(newTrailingRun));
1095         return trailingSpaceRun;
1096     }
1097     if (!shouldReorder)
1098         return trailingSpaceRun;
1099
1100     if (direction == TextDirection::LTR) {
1101         bidiRuns.moveRunToEnd(trailingSpaceRun);
1102         trailingSpaceRun->m_level = 0;
1103     } else {
1104         bidiRuns.moveRunToBeginning(trailingSpaceRun);
1105         trailingSpaceRun->m_level = 1;
1106     }
1107     return trailingSpaceRun;
1108 }
1109
1110 void ComplexLineLayout::appendFloatingObjectToLastLine(FloatingObject& floatingObject)
1111 {
1112     ASSERT_WITH_SECURITY_IMPLICATION(!floatingObject.originatingLine());
1113     ASSERT(lastRootBox());
1114     floatingObject.setOriginatingLine(*lastRootBox());
1115     lastRootBox()->appendFloat(floatingObject.renderer());
1116 }
1117
1118 static inline void notifyResolverToResumeInIsolate(InlineBidiResolver& resolver, RenderObject* root, RenderObject* startObject)
1119 {
1120     if (root != startObject) {
1121         RenderObject* parent = startObject->parent();
1122         notifyResolverToResumeInIsolate(resolver, root, parent);
1123         notifyObserverEnteredObject(&resolver, startObject);
1124     }
1125 }
1126
1127 static inline void setUpResolverToResumeInIsolate(InlineBidiResolver& resolver, InlineBidiResolver& topResolver, BidiRun& isolatedRun, RenderObject* root, RenderObject* startObject)
1128 {
1129     // Set up m_whitespaceCollapsingState
1130     resolver.whitespaceCollapsingState() = topResolver.whitespaceCollapsingState();
1131     resolver.whitespaceCollapsingState().setCurrentTransition(topResolver.whitespaceCollapsingTransitionForIsolatedRun(isolatedRun));
1132
1133     // Set up m_nestedIsolateCount
1134     notifyResolverToResumeInIsolate(resolver, root, startObject);
1135 }
1136
1137 // FIXME: BidiResolver should have this logic.
1138 static inline void constructBidiRunsForSegment(InlineBidiResolver& topResolver, BidiRunList<BidiRun>& bidiRuns, const InlineIterator& endOfRuns, VisualDirectionOverride override, bool previousLineBrokeCleanly)
1139 {
1140     // FIXME: We should pass a BidiRunList into createBidiRunsForLine instead
1141     // of the resolver owning the runs.
1142     ASSERT(&topResolver.runs() == &bidiRuns);
1143     ASSERT(topResolver.position() != endOfRuns);
1144     RenderObject* currentRoot = topResolver.position().root();
1145     topResolver.createBidiRunsForLine(endOfRuns, override, previousLineBrokeCleanly);
1146
1147     while (!topResolver.isolatedRuns().isEmpty()) {
1148         // It does not matter which order we resolve the runs as long as we resolve them all.
1149         auto isolatedRun = WTFMove(topResolver.isolatedRuns().last());
1150         topResolver.isolatedRuns().removeLast();
1151         currentRoot = &isolatedRun.root;
1152
1153         RenderObject& startObject = isolatedRun.object;
1154
1155         // Only inlines make sense with unicode-bidi: isolate (blocks are already isolated).
1156         // FIXME: Because enterIsolate is not passed a RenderObject, we have to crawl up the
1157         // tree to see which parent inline is the isolate. We could change enterIsolate
1158         // to take a RenderObject and do this logic there, but that would be a layering
1159         // violation for BidiResolver (which knows nothing about RenderObject).
1160         RenderInline* isolatedInline = downcast<RenderInline>(highestContainingIsolateWithinRoot(startObject, currentRoot));
1161         ASSERT(isolatedInline);
1162
1163         InlineBidiResolver isolatedResolver;
1164         EUnicodeBidi unicodeBidi = isolatedInline->style().unicodeBidi();
1165         TextDirection direction;
1166         if (unicodeBidi == Plaintext)
1167             determineDirectionality(direction, InlineIterator(isolatedInline, &isolatedRun.object, 0));
1168         else {
1169             ASSERT(unicodeBidi == Isolate || unicodeBidi == IsolateOverride);
1170             direction = isolatedInline->style().direction();
1171         }
1172         isolatedResolver.setStatus(BidiStatus(direction, isOverride(unicodeBidi)));
1173
1174         setUpResolverToResumeInIsolate(isolatedResolver, topResolver, isolatedRun.runToReplace, isolatedInline, &startObject);
1175
1176         // The starting position is the beginning of the first run within the isolate that was identified
1177         // during the earlier call to createBidiRunsForLine. This can be but is not necessarily the
1178         // first run within the isolate.
1179         InlineIterator iter = InlineIterator(isolatedInline, &startObject, isolatedRun.position);
1180         isolatedResolver.setPositionIgnoringNestedIsolates(iter);
1181
1182         // We stop at the next end of line; we may re-enter this isolate in the next call to constructBidiRuns().
1183         // FIXME: What should end and previousLineBrokeCleanly be?
1184         // rniwa says previousLineBrokeCleanly is just a WinIE hack and could always be false here?
1185         isolatedResolver.createBidiRunsForLine(endOfRuns, NoVisualOverride, previousLineBrokeCleanly);
1186         // Note that we do not delete the runs from the resolver.
1187         // We're not guaranteed to get any BidiRuns in the previous step. If we don't, we allow the placeholder
1188         // itself to be turned into an InlineBox. We can't remove it here without potentially losing track of
1189         // the logically last run.
1190         if (isolatedResolver.runs().runCount())
1191             bidiRuns.replaceRunWithRuns(&isolatedRun.runToReplace, isolatedResolver.runs());
1192
1193         // If we encountered any nested isolate runs, just move them
1194         // to the top resolver's list for later processing.
1195         while (!isolatedResolver.isolatedRuns().isEmpty()) {
1196             auto runWithContext = WTFMove(isolatedResolver.isolatedRuns().last());
1197             isolatedResolver.isolatedRuns().removeLast();
1198             topResolver.setWhitespaceCollapsingTransitionForIsolatedRun(runWithContext.runToReplace, isolatedResolver.whitespaceCollapsingTransitionForIsolatedRun(runWithContext.runToReplace));
1199             topResolver.isolatedRuns().append(WTFMove(runWithContext));
1200         }
1201     }
1202 }
1203
1204 // This function constructs line boxes for all of the text runs in the resolver and computes their position.
1205 RootInlineBox* ComplexLineLayout::createLineBoxesFromBidiRuns(unsigned bidiLevel, BidiRunList<BidiRun>& bidiRuns, const InlineIterator& end, LineInfo& lineInfo, VerticalPositionCache& verticalPositionCache, BidiRun* trailingSpaceRun, WordMeasurements& wordMeasurements)
1206 {
1207     if (!bidiRuns.runCount())
1208         return nullptr;
1209
1210     // FIXME: Why is this only done when we had runs?
1211     lineInfo.setLastLine(!end.renderer());
1212
1213     RootInlineBox* lineBox = constructLine(bidiRuns, lineInfo);
1214     if (!lineBox)
1215         return nullptr;
1216
1217     lineBox->setBidiLevel(bidiLevel);
1218     lineBox->setEndsWithBreak(lineInfo.previousLineBrokeCleanly());
1219     
1220     bool isSVGRootInlineBox = is<SVGRootInlineBox>(*lineBox);
1221     
1222     GlyphOverflowAndFallbackFontsMap textBoxDataMap;
1223     
1224     // Now we position all of our text runs horizontally.
1225     if (!isSVGRootInlineBox)
1226         computeInlineDirectionPositionsForLine(lineBox, lineInfo, bidiRuns.firstRun(), trailingSpaceRun, end.atEnd(), textBoxDataMap, verticalPositionCache, wordMeasurements);
1227     
1228     // Now position our text runs vertically.
1229     computeBlockDirectionPositionsForLine(lineBox, bidiRuns.firstRun(), textBoxDataMap, verticalPositionCache);
1230     
1231     // SVG text layout code computes vertical & horizontal positions on its own.
1232     // Note that we still need to execute computeVerticalPositionsForLine() as
1233     // it calls InlineTextBox::positionLineBox(), which tracks whether the box
1234     // contains reversed text or not. If we wouldn't do that editing and thus
1235     // text selection in RTL boxes would not work as expected.
1236     if (isSVGRootInlineBox) {
1237         RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(m_flow.isSVGText());
1238         downcast<SVGRootInlineBox>(*lineBox).computePerCharacterLayoutInformation();
1239     }
1240     
1241     // Compute our overflow now.
1242     lineBox->computeOverflow(lineBox->lineTop(), lineBox->lineBottom(), textBoxDataMap);
1243     
1244     return lineBox;
1245 }
1246
1247 static void deleteLineRange(LineLayoutState& layoutState, RootInlineBox* startLine, RootInlineBox* stopLine = 0)
1248 {
1249     RootInlineBox* boxToDelete = startLine;
1250     while (boxToDelete && boxToDelete != stopLine) {
1251         layoutState.updateRepaintRangeFromBox(boxToDelete);
1252         // Note: deleteLineRange(firstRootBox()) is not identical to deleteLineBoxTree().
1253         // deleteLineBoxTree uses nextLineBox() instead of nextRootBox() when traversing.
1254         RootInlineBox* next = boxToDelete->nextRootBox();
1255         boxToDelete->deleteLine();
1256         boxToDelete = next;
1257     }
1258 }
1259
1260 static void repaintDirtyFloats(LineLayoutState::FloatList& floats)
1261 {
1262     // Floats that did not have layout did not repaint when we laid them out. They would have
1263     // painted by now if they had moved, but if they stayed at (0, 0), they still need to be
1264     // painted.
1265     for (auto& floatBox : floats) {
1266         if (floatBox->everHadLayout())
1267             continue;
1268         auto& box = floatBox->renderer();
1269         if (!box.x() && !box.y() && box.checkForRepaintDuringLayout())
1270             box.repaint();
1271     }
1272 }
1273
1274 void ComplexLineLayout::layoutRunsAndFloats(LineLayoutState& layoutState, bool hasInlineChild)
1275 {
1276     // We want to skip ahead to the first dirty line
1277     InlineBidiResolver resolver;
1278     RootInlineBox* startLine = determineStartPosition(layoutState, resolver);
1279     
1280     unsigned consecutiveHyphenatedLines = 0;
1281     if (startLine) {
1282         for (RootInlineBox* line = startLine->prevRootBox(); line && line->isHyphenated(); line = line->prevRootBox())
1283             consecutiveHyphenatedLines++;
1284     }
1285
1286     // FIXME: This would make more sense outside of this function, but since
1287     // determineStartPosition can change the fullLayout flag we have to do this here. Failure to call
1288     // determineStartPosition first will break fast/repaint/line-flow-with-floats-9.html.
1289     if (layoutState.isFullLayout() && hasInlineChild && !m_flow.selfNeedsLayout()) {
1290         m_flow.setNeedsLayout(MarkOnlyThis); // Mark as needing a full layout to force us to repaint.
1291         if (!layoutContext().needsFullRepaint() && m_flow.hasSelfPaintingLayer() && m_flow.hasRepaintLayoutRects()) {
1292             // Because we waited until we were already inside layout to discover
1293             // that the block really needed a full layout, we missed our chance to repaint the layer
1294             // before layout started. Luckily the layer has cached the repaint rect for its original
1295             // position and size, and so we can use that to make a repaint happen now.
1296             m_flow.repaintUsingContainer(m_flow.containerForRepaint(), m_flow.repaintLayoutRects().m_repaintRect);
1297         }
1298     }
1299
1300     if (m_flow.containsFloats())
1301         layoutState.floatList().setLastFloat(m_flow.floatingObjects()->set().last().get());
1302
1303     // We also find the first clean line and extract these lines. We will add them back
1304     // if we determine that we're able to synchronize after handling all our dirty lines.
1305     InlineIterator cleanLineStart;
1306     BidiStatus cleanLineBidiStatus;
1307     if (!layoutState.isFullLayout() && startLine)
1308         determineEndPosition(layoutState, startLine, cleanLineStart, cleanLineBidiStatus);
1309
1310     if (startLine) {
1311         if (!layoutState.usesRepaintBounds())
1312             layoutState.setRepaintRange(m_flow.logicalHeight());
1313         deleteLineRange(layoutState, startLine);
1314     }
1315
1316     if (!layoutState.isFullLayout() && lastRootBox() && lastRootBox()->endsWithBreak()) {
1317         // If the last line before the start line ends with a line break that clear floats,
1318         // adjust the height accordingly.
1319         // A line break can be either the first or the last object on a line, depending on its direction.
1320         if (InlineBox* lastLeafDescendant = lastRootBox()->lastLeafDescendant()) {
1321             RenderObject* lastObject = &lastLeafDescendant->renderer();
1322             if (!lastObject->isBR())
1323                 lastObject = &lastRootBox()->firstLeafDescendant()->renderer();
1324             if (lastObject->isBR()) {
1325                 Clear clear = lastObject->style().clear();
1326                 if (clear != Clear::None)
1327                     m_flow.clearFloats(clear);
1328             }
1329         }
1330     }
1331
1332     layoutRunsAndFloatsInRange(layoutState, resolver, cleanLineStart, cleanLineBidiStatus, consecutiveHyphenatedLines);
1333     linkToEndLineIfNeeded(layoutState);
1334     repaintDirtyFloats(layoutState.floatList());
1335 }
1336
1337 // Before restarting the layout loop with a new logicalHeight, remove all floats that were added and reset the resolver.
1338 inline const InlineIterator& ComplexLineLayout::restartLayoutRunsAndFloatsInRange(LayoutUnit oldLogicalHeight, LayoutUnit newLogicalHeight,  FloatingObject* lastFloatFromPreviousLine, InlineBidiResolver& resolver,  const InlineIterator& oldEnd)
1339 {
1340     m_flow.removeFloatingObjectsBelow(lastFloatFromPreviousLine, oldLogicalHeight);
1341     m_flow.setLogicalHeight(newLogicalHeight);
1342     resolver.setPositionIgnoringNestedIsolates(oldEnd);
1343     return oldEnd;
1344 }
1345
1346 void ComplexLineLayout::layoutRunsAndFloatsInRange(LineLayoutState& layoutState, InlineBidiResolver& resolver, const InlineIterator& cleanLineStart, const BidiStatus& cleanLineBidiStatus, unsigned consecutiveHyphenatedLines)
1347 {
1348     const RenderStyle& styleToUse = style();
1349     bool paginated = layoutContext().layoutState() && layoutContext().layoutState()->isPaginated();
1350     LineWhitespaceCollapsingState& lineWhitespaceCollapsingState = resolver.whitespaceCollapsingState();
1351     InlineIterator end = resolver.position();
1352     bool checkForEndLineMatch = layoutState.endLine();
1353     RenderTextInfo renderTextInfo;
1354     VerticalPositionCache verticalPositionCache;
1355
1356     LineBreaker lineBreaker(m_flow);
1357
1358     while (!end.atEnd()) {
1359         // FIXME: Is this check necessary before the first iteration or can it be moved to the end?
1360         if (checkForEndLineMatch) {
1361             layoutState.setEndLineMatched(matchedEndLine(layoutState, resolver, cleanLineStart, cleanLineBidiStatus));
1362             if (layoutState.endLineMatched()) {
1363                 resolver.setPosition(InlineIterator(resolver.position().root(), 0, 0), 0);
1364                 layoutState.marginInfo().clearMargin();
1365                 break;
1366             }
1367         }
1368
1369         lineWhitespaceCollapsingState.reset();
1370
1371         layoutState.lineInfo().setEmpty(true);
1372         layoutState.lineInfo().resetRunsFromLeadingWhitespace();
1373
1374         const InlineIterator oldEnd = end;
1375         bool isNewUBAParagraph = layoutState.lineInfo().previousLineBrokeCleanly();
1376         FloatingObject* lastFloatFromPreviousLine = (m_flow.containsFloats()) ? m_flow.floatingObjects()->set().last().get() : nullptr;
1377
1378         WordMeasurements wordMeasurements;
1379         end = lineBreaker.nextLineBreak(resolver, layoutState.lineInfo(), renderTextInfo, lastFloatFromPreviousLine, consecutiveHyphenatedLines, wordMeasurements);
1380         m_flow.cachePriorCharactersIfNeeded(renderTextInfo.lineBreakIterator);
1381         renderTextInfo.lineBreakIterator.resetPriorContext();
1382         if (resolver.position().atEnd()) {
1383             // FIXME: We shouldn't be creating any runs in nextLineBreak to begin with!
1384             // Once BidiRunList is separated from BidiResolver this will not be needed.
1385             resolver.runs().clear();
1386             resolver.markCurrentRunEmpty(); // FIXME: This can probably be replaced by an ASSERT (or just removed).
1387             layoutState.setCheckForFloatsFromLastLine(true);
1388             resolver.setPosition(InlineIterator(resolver.position().root(), 0, 0), 0);
1389             break;
1390         }
1391
1392         ASSERT(end != resolver.position());
1393
1394         // This is a short-cut for empty lines.
1395         if (layoutState.lineInfo().isEmpty()) {
1396             if (lastRootBox())
1397                 lastRootBox()->setLineBreakInfo(end.renderer(), end.offset(), resolver.status());
1398         } else {
1399             VisualDirectionOverride override = (styleToUse.rtlOrdering() == Order::Visual ? (styleToUse.direction() == TextDirection::LTR ? VisualLeftToRightOverride : VisualRightToLeftOverride) : NoVisualOverride);
1400
1401             if (isNewUBAParagraph && styleToUse.unicodeBidi() == Plaintext && !resolver.context()->parent()) {
1402                 TextDirection direction = styleToUse.direction();
1403                 determineDirectionality(direction, resolver.position());
1404                 resolver.setStatus(BidiStatus(direction, isOverride(styleToUse.unicodeBidi())));
1405             }
1406             // FIXME: This ownership is reversed. We should own the BidiRunList and pass it to createBidiRunsForLine.
1407             BidiRunList<BidiRun>& bidiRuns = resolver.runs();
1408             constructBidiRunsForSegment(resolver, bidiRuns, end, override, layoutState.lineInfo().previousLineBrokeCleanly());
1409             ASSERT(resolver.position() == end);
1410
1411             BidiRun* trailingSpaceRun = !layoutState.lineInfo().previousLineBrokeCleanly() ? handleTrailingSpaces(bidiRuns, resolver.context()) : nullptr;
1412
1413             if (bidiRuns.runCount() && lineBreaker.lineWasHyphenated()) {
1414                 bidiRuns.logicallyLastRun()->m_hasHyphen = true;
1415                 consecutiveHyphenatedLines++;
1416             } else
1417                 consecutiveHyphenatedLines = 0;
1418
1419             // Now that the runs have been ordered, we create the line boxes.
1420             // At the same time we figure out where border/padding/margin should be applied for
1421             // inline flow boxes.
1422
1423             LayoutUnit oldLogicalHeight = m_flow.logicalHeight();
1424             RootInlineBox* lineBox = createLineBoxesFromBidiRuns(resolver.status().context->level(), bidiRuns, end, layoutState.lineInfo(), verticalPositionCache, trailingSpaceRun, wordMeasurements);
1425
1426             bidiRuns.clear();
1427             resolver.markCurrentRunEmpty(); // FIXME: This can probably be replaced by an ASSERT (or just removed).
1428
1429             if (lineBox) {
1430                 lineBox->setLineBreakInfo(end.renderer(), end.offset(), resolver.status());
1431                 if (layoutState.usesRepaintBounds())
1432                     layoutState.updateRepaintRangeFromBox(lineBox);
1433                 
1434                 LayoutUnit adjustment;
1435                 bool overflowsFragment = false;
1436                 
1437                 layoutState.marginInfo().setAtBeforeSideOfBlock(false);
1438
1439                 if (paginated)
1440                     m_flow.adjustLinePositionForPagination(lineBox, adjustment, overflowsFragment, layoutState.fragmentedFlow());
1441                 if (adjustment) {
1442                     IndentTextOrNot shouldIndentText = layoutState.lineInfo().isFirstLine() ? IndentText : DoNotIndentText;
1443                     LayoutUnit oldLineWidth = m_flow.availableLogicalWidthForLine(oldLogicalHeight, shouldIndentText);
1444                     lineBox->adjustBlockDirectionPosition(adjustment);
1445                     if (layoutState.usesRepaintBounds())
1446                         layoutState.updateRepaintRangeFromBox(lineBox);
1447
1448                     if (m_flow.availableLogicalWidthForLine(oldLogicalHeight + adjustment, shouldIndentText) != oldLineWidth) {
1449                         // We have to delete this line, remove all floats that got added, and let line layout re-run.
1450                         lineBox->deleteLine();
1451                         end = restartLayoutRunsAndFloatsInRange(oldLogicalHeight, oldLogicalHeight + adjustment, lastFloatFromPreviousLine, resolver, oldEnd);
1452                         continue;
1453                     }
1454
1455                     m_flow.setLogicalHeight(lineBox->lineBottomWithLeading());
1456                 }
1457                     
1458                 if (paginated) {
1459                     if (layoutState.fragmentedFlow())
1460                         updateFragmentForLine(lineBox);
1461                 }
1462             }
1463         }
1464
1465         for (size_t i = 0; i < lineBreaker.positionedObjects().size(); ++i)
1466             setStaticPositions(m_flow, *lineBreaker.positionedObjects()[i], DoNotIndentText);
1467
1468         if (!layoutState.lineInfo().isEmpty()) {
1469             layoutState.lineInfo().setFirstLine(false);
1470             m_flow.clearFloats(lineBreaker.clear());
1471         }
1472
1473         if (m_flow.floatingObjects() && lastRootBox()) {
1474             const FloatingObjectSet& floatingObjectSet = m_flow.floatingObjects()->set();
1475             auto it = floatingObjectSet.begin();
1476             auto end = floatingObjectSet.end();
1477             if (auto* lastFloat = layoutState.floatList().lastFloat()) {
1478                 auto lastFloatIterator = floatingObjectSet.find(lastFloat);
1479                 ASSERT(lastFloatIterator != end);
1480                 ++lastFloatIterator;
1481                 it = lastFloatIterator;
1482             }
1483             for (; it != end; ++it) {
1484                 auto& floatingObject = *it;
1485                 appendFloatingObjectToLastLine(*floatingObject);
1486                 // If a float's geometry has changed, give up on syncing with clean lines.
1487                 auto* floatWithRect = layoutState.floatList().floatWithRect(floatingObject->renderer());
1488                 if (!floatWithRect || floatWithRect->rect() != floatingObject->frameRect())
1489                     checkForEndLineMatch = false;
1490             }
1491             layoutState.floatList().setLastFloat(!floatingObjectSet.isEmpty() ? floatingObjectSet.last().get() : nullptr);
1492         }
1493
1494         lineWhitespaceCollapsingState.reset();
1495         resolver.setPosition(end, numberOfIsolateAncestors(end));
1496     }
1497
1498     // In case we already adjusted the line positions during this layout to avoid widows
1499     // then we need to ignore the possibility of having a new widows situation.
1500     // Otherwise, we risk leaving empty containers which is against the block fragmentation principles.
1501     if (paginated && !style().hasAutoWidows() && !m_flow.didBreakAtLineToAvoidWidow()) {
1502         // Check the line boxes to make sure we didn't create unacceptable widows.
1503         // However, we'll prioritize orphans - so nothing we do here should create
1504         // a new orphan.
1505
1506         RootInlineBox* lineBox = lastRootBox();
1507
1508         // Count from the end of the block backwards, to see how many hanging
1509         // lines we have.
1510         RootInlineBox* firstLineInBlock = firstRootBox();
1511         int numLinesHanging = 1;
1512         while (lineBox && lineBox != firstLineInBlock && !lineBox->isFirstAfterPageBreak()) {
1513             ++numLinesHanging;
1514             lineBox = lineBox->prevRootBox();
1515         }
1516
1517         // If there were no breaks in the block, we didn't create any widows.
1518         if (!lineBox || !lineBox->isFirstAfterPageBreak() || lineBox == firstLineInBlock)
1519             return;
1520
1521         if (numLinesHanging < style().widows()) {
1522             // We have detected a widow. Now we need to work out how many
1523             // lines there are on the previous page, and how many we need
1524             // to steal.
1525             int numLinesNeeded = style().widows() - numLinesHanging;
1526             RootInlineBox* currentFirstLineOfNewPage = lineBox;
1527
1528             // Count the number of lines in the previous page.
1529             lineBox = lineBox->prevRootBox();
1530             int numLinesInPreviousPage = 1;
1531             while (lineBox && lineBox != firstLineInBlock && !lineBox->isFirstAfterPageBreak()) {
1532                 ++numLinesInPreviousPage;
1533                 lineBox = lineBox->prevRootBox();
1534             }
1535
1536             // If there was an explicit value for orphans, respect that. If not, we still
1537             // shouldn't create a situation where we make an orphan bigger than the initial value.
1538             // This means that setting widows implies we also care about orphans, but given
1539             // the specification says the initial orphan value is non-zero, this is ok. The
1540             // author is always free to set orphans explicitly as well.
1541             int orphans = style().hasAutoOrphans() ? style().initialOrphans() : style().orphans();
1542             int numLinesAvailable = numLinesInPreviousPage - orphans;
1543             if (numLinesAvailable <= 0)
1544                 return;
1545
1546             int numLinesToTake = std::min(numLinesAvailable, numLinesNeeded);
1547             // Wind back from our first widowed line.
1548             lineBox = currentFirstLineOfNewPage;
1549             for (int i = 0; i < numLinesToTake; ++i)
1550                 lineBox = lineBox->prevRootBox();
1551
1552             // We now want to break at this line. Remember for next layout and trigger relayout.
1553             m_flow.setBreakAtLineToAvoidWidow(m_flow.lineCount(lineBox));
1554             m_flow.markLinesDirtyInBlockRange(lastRootBox()->lineBottomWithLeading(), lineBox->lineBottomWithLeading(), lineBox);
1555         }
1556     }
1557     m_flow.clearDidBreakAtLineToAvoidWidow();
1558 }
1559
1560 void ComplexLineLayout::reattachCleanLineFloats(RootInlineBox& cleanLine, LayoutUnit delta, bool isFirstCleanLine)
1561 {
1562     auto* cleanLineFloats = cleanLine.floatsPtr();
1563     if (!cleanLineFloats)
1564         return;
1565
1566     for (auto& floatingBox : *cleanLineFloats) {
1567         if (!floatingBox)
1568             continue;
1569         auto* floatingObject = m_flow.insertFloatingObject(*floatingBox);
1570         if (isFirstCleanLine && floatingObject->originatingLine()) {
1571             // Float box does not belong to this line anymore.
1572             ASSERT_WITH_SECURITY_IMPLICATION(cleanLine.prevRootBox() == floatingObject->originatingLine());
1573             cleanLine.removeFloat(*floatingBox);
1574             continue;
1575         }
1576         ASSERT_WITH_SECURITY_IMPLICATION(!floatingObject->originatingLine());
1577         floatingObject->setOriginatingLine(cleanLine);
1578         m_flow.setLogicalHeight(m_flow.logicalTopForChild(*floatingBox) - m_flow.marginBeforeForChild(*floatingBox) + delta);
1579         m_flow.positionNewFloats();
1580     }
1581 }
1582
1583 void ComplexLineLayout::linkToEndLineIfNeeded(LineLayoutState& layoutState)
1584 {
1585     auto* firstCleanLine = layoutState.endLine();
1586     if (firstCleanLine) {
1587         if (layoutState.endLineMatched()) {
1588             bool paginated = layoutContext().layoutState() && layoutContext().layoutState()->isPaginated();
1589             // Attach all the remaining lines, and then adjust their y-positions as needed.
1590             LayoutUnit delta = m_flow.logicalHeight() - layoutState.endLineLogicalTop();
1591             for (auto* line = firstCleanLine; line; line = line->nextRootBox()) {
1592                 line->attachLine();
1593                 if (paginated) {
1594                     delta -= line->paginationStrut();
1595                     bool overflowsFragment;
1596                     m_flow.adjustLinePositionForPagination(line, delta, overflowsFragment, layoutState.fragmentedFlow());
1597                 }
1598                 if (delta) {
1599                     layoutState.updateRepaintRangeFromBox(line, delta);
1600                     line->adjustBlockDirectionPosition(delta);
1601                 }
1602                 if (layoutState.fragmentedFlow())
1603                     updateFragmentForLine(line);
1604                 reattachCleanLineFloats(*line, delta, line == firstCleanLine);
1605             }
1606             m_flow.setLogicalHeight(lastRootBox()->lineBottomWithLeading());
1607         } else {
1608             // Delete all the remaining lines.
1609             deleteLineRange(layoutState, layoutState.endLine());
1610         }
1611     }
1612     
1613     if (m_flow.floatingObjects() && (layoutState.checkForFloatsFromLastLine() || m_flow.positionNewFloats()) && lastRootBox()) {
1614         // In case we have a float on the last line, it might not be positioned up to now.
1615         // This has to be done before adding in the bottom border/padding, or the float will
1616         // include the padding incorrectly. -dwh
1617         if (layoutState.checkForFloatsFromLastLine()) {
1618             LayoutUnit bottomVisualOverflow = lastRootBox()->logicalBottomVisualOverflow();
1619             LayoutUnit bottomLayoutOverflow = lastRootBox()->logicalBottomLayoutOverflow();
1620             auto newLineBox = makeUnique<TrailingFloatsRootInlineBox>(m_flow);
1621             auto trailingFloatsLineBox = newLineBox.get();
1622             m_lineBoxes.appendLineBox(WTFMove(newLineBox));
1623             trailingFloatsLineBox->setConstructed();
1624             GlyphOverflowAndFallbackFontsMap textBoxDataMap;
1625             VerticalPositionCache verticalPositionCache;
1626             LayoutUnit blockLogicalHeight = m_flow.logicalHeight();
1627             trailingFloatsLineBox->alignBoxesInBlockDirection(blockLogicalHeight, textBoxDataMap, verticalPositionCache);
1628             trailingFloatsLineBox->setLineTopBottomPositions(blockLogicalHeight, blockLogicalHeight, blockLogicalHeight, blockLogicalHeight);
1629             trailingFloatsLineBox->setPaginatedLineWidth(m_flow.availableLogicalWidthForContent(blockLogicalHeight));
1630             LayoutRect logicalLayoutOverflow(0_lu, blockLogicalHeight, 1_lu, bottomLayoutOverflow - blockLogicalHeight);
1631             LayoutRect logicalVisualOverflow(0_lu, blockLogicalHeight, 1_lu, bottomVisualOverflow - blockLogicalHeight);
1632             trailingFloatsLineBox->setOverflowFromLogicalRects(logicalLayoutOverflow, logicalVisualOverflow, trailingFloatsLineBox->lineTop(), trailingFloatsLineBox->lineBottom());
1633             if (layoutState.fragmentedFlow())
1634                 updateFragmentForLine(trailingFloatsLineBox);
1635         }
1636
1637         const FloatingObjectSet& floatingObjectSet = m_flow.floatingObjects()->set();
1638         auto it = floatingObjectSet.begin();
1639         auto end = floatingObjectSet.end();
1640         if (auto* lastFloat = layoutState.floatList().lastFloat()) {
1641             auto lastFloatIterator = floatingObjectSet.find(lastFloat);
1642             ASSERT(lastFloatIterator != end);
1643             ++lastFloatIterator;
1644             it = lastFloatIterator;
1645         }
1646         for (; it != end; ++it)
1647             appendFloatingObjectToLastLine(**it);
1648         layoutState.floatList().setLastFloat(!floatingObjectSet.isEmpty() ? floatingObjectSet.last().get() : nullptr);
1649     }
1650 }
1651
1652 void ComplexLineLayout::layoutLineBoxes(bool relayoutChildren, LayoutUnit& repaintLogicalTop, LayoutUnit& repaintLogicalBottom)
1653 {
1654     ASSERT(!m_flow.simpleLineLayout());
1655
1656     m_flow.setLogicalHeight(m_flow.borderAndPaddingBefore());
1657     
1658     // Lay out our hypothetical grid line as though it occurs at the top of the block.
1659     if (layoutContext().layoutState() && layoutContext().layoutState()->lineGrid() == &m_flow)
1660         m_flow.layoutLineGridBox();
1661
1662     RenderFragmentedFlow* fragmentedFlow = m_flow.enclosingFragmentedFlow();
1663     bool clearLinesForPagination = firstRootBox() && fragmentedFlow && !fragmentedFlow->hasFragments();
1664
1665     // Figure out if we should clear out our line boxes.
1666     // FIXME: Handle resize eventually!
1667     bool isFullLayout = !firstRootBox() || m_flow.selfNeedsLayout() || relayoutChildren || clearLinesForPagination;
1668     LineLayoutState layoutState(m_flow, isFullLayout, repaintLogicalTop, repaintLogicalBottom, fragmentedFlow);
1669
1670     if (isFullLayout)
1671         lineBoxes().deleteLineBoxes();
1672
1673     // Text truncation kicks in in two cases:
1674     //     1) If your overflow isn't visible and your text-overflow-mode isn't clip.
1675     //     2) If you're an anonymous block with a block parent that satisfies #1.
1676     // FIXME: CSS3 says that descendants that are clipped must also know how to truncate. This is insanely
1677     // difficult to figure out in general (especially in the middle of doing layout), so we only handle the
1678     // simple case of an anonymous block truncating when it's parent is clipped.
1679     auto* parent = m_flow.parent();
1680     bool hasTextOverflow = (style().textOverflow() == TextOverflow::Ellipsis && m_flow.hasOverflowClip())
1681         || (m_flow.isAnonymousBlock() && parent && parent->isRenderBlock() && parent->style().textOverflow() == TextOverflow::Ellipsis && parent->hasOverflowClip());
1682
1683     // Walk all the lines and delete our ellipsis line boxes if they exist.
1684     if (hasTextOverflow)
1685         deleteEllipsisLineBoxes();
1686
1687     if (m_flow.firstChild()) {
1688         // In full layout mode, clear the line boxes of children upfront. Otherwise,
1689         // siblings can run into stale root lineboxes during layout. Then layout
1690         // the replaced elements later. In partial layout mode, line boxes are not
1691         // deleted and only dirtied. In that case, we can layout the replaced
1692         // elements at the same time.
1693         bool hasInlineChild = false;
1694         Vector<RenderBox*> replacedChildren;
1695         for (InlineWalker walker(m_flow); !walker.atEnd(); walker.advance()) {
1696             RenderObject& o = *walker.current();
1697
1698             if (!hasInlineChild && o.isInline())
1699                 hasInlineChild = true;
1700
1701             if (o.isReplaced() || o.isFloating() || o.isOutOfFlowPositioned()) {
1702                 RenderBox& box = downcast<RenderBox>(o);
1703
1704                 if (relayoutChildren || box.hasRelativeDimensions())
1705                     box.setChildNeedsLayout(MarkOnlyThis);
1706
1707                 // If relayoutChildren is set and the child has percentage padding or an embedded content box, we also need to invalidate the childs pref widths.
1708                 if (relayoutChildren && box.needsPreferredWidthsRecalculation())
1709                     box.setPreferredLogicalWidthsDirty(true, MarkOnlyThis);
1710
1711                 if (box.isOutOfFlowPositioned())
1712                     box.containingBlock()->insertPositionedObject(box);
1713                 else if (box.isFloating())
1714                     layoutState.floatList().append(FloatWithRect::create(box));
1715                 else if (isFullLayout || box.needsLayout()) {
1716                     // Replaced element.
1717                     if (isFullLayout && is<RenderRubyRun>(box)) {
1718                         // FIXME: This resets the overhanging margins that we set during line layout (see computeInlineDirectionPositionsForSegment)
1719                         // Find a more suitable place for this.
1720                         m_flow.setMarginStartForChild(box, 0);
1721                         m_flow.setMarginEndForChild(box, 0);
1722                     }
1723                     box.dirtyLineBoxes(isFullLayout);
1724                     if (isFullLayout)
1725                         replacedChildren.append(&box);
1726                     else
1727                         box.layoutIfNeeded();
1728                 }
1729             } else if (o.isTextOrLineBreak() || (is<RenderInline>(o) && !walker.atEndOfInline())) {
1730                 if (is<RenderInline>(o))
1731                     downcast<RenderInline>(o).updateAlwaysCreateLineBoxes(layoutState.isFullLayout());
1732                 if (layoutState.isFullLayout() || o.selfNeedsLayout())
1733                     dirtyLineBoxesForRenderer(o, layoutState.isFullLayout());
1734                 o.clearNeedsLayout();
1735             }
1736         }
1737
1738         for (size_t i = 0; i < replacedChildren.size(); i++)
1739             replacedChildren[i]->layoutIfNeeded();
1740
1741         layoutRunsAndFloats(layoutState, hasInlineChild);
1742     }
1743
1744     // Expand the last line to accommodate Ruby and emphasis marks.
1745     int lastLineAnnotationsAdjustment = 0;
1746     if (lastRootBox()) {
1747         LayoutUnit lowestAllowedPosition = std::max(lastRootBox()->lineBottom(), m_flow.logicalHeight() + m_flow.paddingAfter());
1748         if (!style().isFlippedLinesWritingMode())
1749             lastLineAnnotationsAdjustment = lastRootBox()->computeUnderAnnotationAdjustment(lowestAllowedPosition);
1750         else
1751             lastLineAnnotationsAdjustment = lastRootBox()->computeOverAnnotationAdjustment(lowestAllowedPosition);
1752     }
1753     
1754     // Now do the handling of the bottom of the block, adding in our bottom border/padding and
1755     // determining the correct collapsed bottom margin information. This collapse is only necessary
1756     // if our last child was an anonymous inline block that might need to propagate margin information out to
1757     // us.
1758     LayoutUnit afterEdge = m_flow.borderAndPaddingAfter() + m_flow.scrollbarLogicalHeight() + lastLineAnnotationsAdjustment;
1759     m_flow.setLogicalHeight(m_flow.logicalHeight() + afterEdge);
1760
1761     if (!firstRootBox() && m_flow.hasLineIfEmpty())
1762         m_flow.setLogicalHeight(m_flow.logicalHeight() + m_flow.lineHeight(true, m_flow.isHorizontalWritingMode() ? HorizontalLine : VerticalLine, PositionOfInteriorLineBoxes));
1763
1764     // See if we have any lines that spill out of our block. If we do, then we will possibly need to
1765     // truncate text.
1766     if (hasTextOverflow)
1767         checkLinesForTextOverflow();
1768 }
1769
1770 void ComplexLineLayout::checkFloatInCleanLine(RootInlineBox& cleanLine, RenderBox& floatBoxOnCleanLine, FloatWithRect& matchingFloatWithRect,
1771     bool& encounteredNewFloat, bool& dirtiedByFloat)
1772 {
1773     ASSERT_WITH_SECURITY_IMPLICATION(!floatBoxOnCleanLine.style().deletionHasBegun());
1774     if (&matchingFloatWithRect.renderer() != &floatBoxOnCleanLine) {
1775         encounteredNewFloat = true;
1776         return;
1777     }
1778     floatBoxOnCleanLine.layoutIfNeeded();
1779     LayoutRect originalFloatRect = matchingFloatWithRect.rect();
1780     LayoutSize newSize(
1781         floatBoxOnCleanLine.width() + floatBoxOnCleanLine.horizontalMarginExtent(),
1782         floatBoxOnCleanLine.height() + floatBoxOnCleanLine.verticalMarginExtent());
1783     
1784     // We have to reset the cap-height alignment done by the first-letter floats when initial-letter is set, so just always treat first-letter floats as dirty.
1785     if (originalFloatRect.size() == newSize && (floatBoxOnCleanLine.style().styleType() != PseudoId::FirstLetter || !floatBoxOnCleanLine.style().initialLetterDrop()))
1786         return;
1787
1788     LayoutUnit floatTop = m_flow.isHorizontalWritingMode() ? originalFloatRect.y() : originalFloatRect.x();
1789     LayoutUnit floatHeight = m_flow.isHorizontalWritingMode() ? std::max(originalFloatRect.height(), newSize.height())
1790         : std::max(originalFloatRect.width(), newSize.width());
1791     floatHeight = std::min(floatHeight, LayoutUnit::max() - floatTop);
1792     cleanLine.markDirty();
1793     m_flow.markLinesDirtyInBlockRange(cleanLine.lineBottomWithLeading(), floatTop + floatHeight, &cleanLine);
1794     LayoutRect newFloatRect = originalFloatRect;
1795     newFloatRect.setSize(newSize);
1796     matchingFloatWithRect.adjustRect(newFloatRect);
1797     dirtiedByFloat = true;
1798 }
1799
1800 RootInlineBox* ComplexLineLayout::determineStartPosition(LineLayoutState& layoutState, InlineBidiResolver& resolver)
1801 {
1802     RootInlineBox* currentLine = nullptr;
1803     RootInlineBox* lastLine = nullptr;
1804
1805     // FIXME: This entire float-checking block needs to be broken into a new function.
1806     auto& floats = layoutState.floatList();
1807     bool dirtiedByFloat = false;
1808     if (!layoutState.isFullLayout()) {
1809         // Paginate all of the clean lines.
1810         bool paginated = layoutContext().layoutState() && layoutContext().layoutState()->isPaginated();
1811         LayoutUnit paginationDelta;
1812         auto floatsIterator = floats.begin();
1813         auto end = floats.end();
1814         for (currentLine = firstRootBox(); currentLine && !currentLine->isDirty(); currentLine = currentLine->nextRootBox()) {
1815             if (paginated) {
1816                 if (lineWidthForPaginatedLineChanged(currentLine, 0, layoutState.fragmentedFlow())) {
1817                     currentLine->markDirty();
1818                     break;
1819                 }
1820                 paginationDelta -= currentLine->paginationStrut();
1821                 bool overflowsFragment;
1822                 m_flow.adjustLinePositionForPagination(currentLine, paginationDelta, overflowsFragment, layoutState.fragmentedFlow());
1823                 if (paginationDelta) {
1824                     if (m_flow.containsFloats() || !floats.isEmpty()) {
1825                         // FIXME: Do better eventually. For now if we ever shift because of pagination and floats are present just go to a full layout.
1826                         layoutState.markForFullLayout();
1827                         break;
1828                     }
1829
1830                     layoutState.updateRepaintRangeFromBox(currentLine, paginationDelta);
1831                     currentLine->adjustBlockDirectionPosition(paginationDelta);
1832                 }
1833                 if (layoutState.fragmentedFlow())
1834                     updateFragmentForLine(currentLine);
1835             }
1836
1837             if (auto* cleanLineFloats = currentLine->floatsPtr()) {
1838                 // If a new float has been inserted before this line or before its last known float, just do a full layout.
1839                 bool encounteredNewFloat = false;
1840                 for (auto& floatBoxOnCleanLine : *cleanLineFloats) {
1841                     ASSERT(floatsIterator != end);
1842                     if (!floatBoxOnCleanLine)
1843                         continue;
1844                     checkFloatInCleanLine(*currentLine, *floatBoxOnCleanLine, *floatsIterator, encounteredNewFloat, dirtiedByFloat);
1845                     ++floatsIterator;
1846                     if (floatsIterator == end || encounteredNewFloat) {
1847                         layoutState.markForFullLayout();
1848                         break;
1849                     }
1850                 }
1851                 if (dirtiedByFloat || encounteredNewFloat)
1852                     break;
1853             }
1854         }
1855         // Check if a new float has been inserted after the last known float.
1856         if (floatsIterator != end) {
1857             if (!currentLine)
1858                 layoutState.markForFullLayout();
1859             else {
1860                 for (; floatsIterator != end; ++floatsIterator) {
1861                     auto& floatWithRect = *floatsIterator;
1862                     if (!floatWithRect->renderer().needsLayout())
1863                         continue;
1864                     layoutState.markForFullLayout();
1865                     break;
1866                 }
1867             }
1868         }
1869     }
1870
1871     if (layoutState.isFullLayout()) {
1872         m_lineBoxes.deleteLineBoxTree();
1873         currentLine = nullptr;
1874         ASSERT(!firstRootBox() && !lastRootBox());
1875     } else {
1876         if (currentLine) {
1877             // We have a dirty line.
1878             if (RootInlineBox* prevRootBox = currentLine->prevRootBox()) {
1879                 // We have a previous line.
1880                 if (!dirtiedByFloat && (!prevRootBox->endsWithBreak()
1881                     || !prevRootBox->lineBreakObj()
1882                     || (is<RenderText>(*prevRootBox->lineBreakObj())
1883                     && prevRootBox->lineBreakPos() >= downcast<RenderText>(*prevRootBox->lineBreakObj()).text().length()))) {
1884                     // The previous line didn't break cleanly or broke at a newline
1885                     // that has been deleted, so treat it as dirty too.
1886                     currentLine = prevRootBox;
1887                 }
1888             }
1889         }
1890         // If we have no dirty lines, then last is just the last root box.
1891         lastLine = currentLine ? currentLine->prevRootBox() : lastRootBox();
1892     }
1893
1894     if (!floats.isEmpty()) {
1895         LayoutUnit savedLogicalHeight = m_flow.logicalHeight();
1896         // Restore floats from clean lines.
1897         RootInlineBox* line = firstRootBox();
1898         while (line != currentLine) {
1899             if (auto* cleanLineFloats = line->floatsPtr()) {
1900                 for (auto& floatingBox : *cleanLineFloats) {
1901                     if (!floatingBox)
1902                         continue;
1903                     auto* floatingObject = m_flow.insertFloatingObject(*floatingBox);
1904                     ASSERT_WITH_SECURITY_IMPLICATION(!floatingObject->originatingLine());
1905                     floatingObject->setOriginatingLine(*line);
1906                     m_flow.setLogicalHeight(m_flow.logicalTopForChild(*floatingBox) - m_flow.marginBeforeForChild(*floatingBox));
1907                     m_flow.positionNewFloats();
1908                     floats.setLastCleanFloat(*floatingBox);
1909                 }
1910             }
1911             line = line->nextRootBox();
1912         }
1913         m_flow.setLogicalHeight(savedLogicalHeight);
1914     }
1915
1916     layoutState.lineInfo().setFirstLine(!lastLine);
1917     layoutState.lineInfo().setPreviousLineBrokeCleanly(!lastLine || lastLine->endsWithBreak());
1918
1919     if (lastLine) {
1920         m_flow.setLogicalHeight(lastLine->lineBottomWithLeading());
1921         InlineIterator iter = InlineIterator(&m_flow, lastLine->lineBreakObj(), lastLine->lineBreakPos());
1922         resolver.setPosition(iter, numberOfIsolateAncestors(iter));
1923         resolver.setStatus(lastLine->lineBreakBidiStatus());
1924     } else {
1925         TextDirection direction = style().direction();
1926         if (style().unicodeBidi() == Plaintext)
1927             determineDirectionality(direction, InlineIterator(&m_flow, bidiFirstSkippingEmptyInlines(m_flow), 0));
1928         resolver.setStatus(BidiStatus(direction, isOverride(style().unicodeBidi())));
1929         InlineIterator iter = InlineIterator(&m_flow, bidiFirstSkippingEmptyInlines(m_flow, &resolver), 0);
1930         resolver.setPosition(iter, numberOfIsolateAncestors(iter));
1931     }
1932     return currentLine;
1933 }
1934
1935 void ComplexLineLayout::determineEndPosition(LineLayoutState& layoutState, RootInlineBox* startLine, InlineIterator& cleanLineStart, BidiStatus& cleanLineBidiStatus)
1936 {
1937     auto iteratorForFirstDirtyFloat = [](LineLayoutState::FloatList& floats) {
1938         auto lastCleanFloat = floats.lastCleanFloat();
1939         if (!lastCleanFloat)
1940             return floats.begin();
1941         auto* lastCleanFloatWithRect = floats.floatWithRect(*lastCleanFloat);
1942         ASSERT(lastCleanFloatWithRect);
1943         return ++floats.find(*lastCleanFloatWithRect);
1944     };
1945
1946     ASSERT(!layoutState.endLine());
1947     auto floatsIterator = iteratorForFirstDirtyFloat(layoutState.floatList());
1948     auto end = layoutState.floatList().end();
1949     RootInlineBox* lastLine = nullptr;
1950     for (RootInlineBox* currentLine = startLine->nextRootBox(); currentLine; currentLine = currentLine->nextRootBox()) {
1951         if (!currentLine->isDirty()) {
1952             if (auto* cleanLineFloats = currentLine->floatsPtr()) {
1953                 bool encounteredNewFloat = false;
1954                 bool dirtiedByFloat = false;
1955                 for (auto& floatBoxOnCleanLine : *cleanLineFloats) {
1956                     if (!floatBoxOnCleanLine)
1957                         continue;
1958                     ASSERT(floatsIterator != end);
1959                     checkFloatInCleanLine(*currentLine, *floatBoxOnCleanLine, *floatsIterator, encounteredNewFloat, dirtiedByFloat);
1960                     ++floatsIterator;
1961                     if (floatsIterator == end || encounteredNewFloat)
1962                         return;
1963                 }
1964             }
1965         }
1966         if (currentLine->isDirty())
1967             lastLine = nullptr;
1968         else if (!lastLine)
1969             lastLine = currentLine;
1970     }
1971
1972     if (!lastLine)
1973         return;
1974
1975     // At this point, |last| is the first line in a run of clean lines that ends with the last line
1976     // in the block.
1977     RootInlineBox* previousLine = lastLine->prevRootBox();
1978     cleanLineStart = InlineIterator(&m_flow, previousLine->lineBreakObj(), previousLine->lineBreakPos());
1979     cleanLineBidiStatus = previousLine->lineBreakBidiStatus();
1980     layoutState.setEndLineLogicalTop(previousLine->lineBottomWithLeading());
1981
1982     for (RootInlineBox* line = lastLine; line; line = line->nextRootBox()) {
1983         // Disconnect all line boxes from their render objects while preserving their connections to one another.
1984         line->extractLine();
1985     }
1986     layoutState.setEndLine(lastLine);
1987 }
1988
1989 bool ComplexLineLayout::checkPaginationAndFloatsAtEndLine(LineLayoutState& layoutState)
1990 {
1991     LayoutUnit lineDelta = m_flow.logicalHeight() - layoutState.endLineLogicalTop();
1992
1993     bool paginated = layoutContext().layoutState() && layoutContext().layoutState()->isPaginated();
1994     if (paginated && layoutState.fragmentedFlow()) {
1995         // Check all lines from here to the end, and see if the hypothetical new position for the lines will result
1996         // in a different available line width.
1997         for (RootInlineBox* lineBox = layoutState.endLine(); lineBox; lineBox = lineBox->nextRootBox()) {
1998             if (paginated) {
1999                 // This isn't the real move we're going to do, so don't update the line box's pagination
2000                 // strut yet.
2001                 LayoutUnit oldPaginationStrut = lineBox->paginationStrut();
2002                 bool overflowsFragment;
2003                 lineDelta -= oldPaginationStrut;
2004                 m_flow.adjustLinePositionForPagination(lineBox, lineDelta, overflowsFragment, layoutState.fragmentedFlow());
2005                 lineBox->setPaginationStrut(oldPaginationStrut);
2006             }
2007             if (lineWidthForPaginatedLineChanged(lineBox, lineDelta, layoutState.fragmentedFlow()))
2008                 return false;
2009         }
2010     }
2011     
2012     if (!lineDelta || !m_flow.floatingObjects())
2013         return true;
2014     
2015     // See if any floats end in the range along which we want to shift the lines vertically.
2016     LayoutUnit logicalTop = std::min(m_flow.logicalHeight(), layoutState.endLineLogicalTop());
2017
2018     RootInlineBox* lastLine = layoutState.endLine();
2019     while (RootInlineBox* nextLine = lastLine->nextRootBox())
2020         lastLine = nextLine;
2021
2022     LayoutUnit logicalBottom = lastLine->lineBottomWithLeading() + absoluteValue(lineDelta);
2023
2024     const FloatingObjectSet& floatingObjectSet = m_flow.floatingObjects()->set();
2025     auto end = floatingObjectSet.end();
2026     for (auto it = floatingObjectSet.begin(); it != end; ++it) {
2027         const auto& floatingObject = *it->get();
2028         if (m_flow.logicalBottomForFloat(floatingObject) >= logicalTop && m_flow.logicalBottomForFloat(floatingObject) < logicalBottom)
2029             return false;
2030     }
2031
2032     return true;
2033 }
2034
2035 bool ComplexLineLayout::lineWidthForPaginatedLineChanged(RootInlineBox* rootBox, LayoutUnit lineDelta, RenderFragmentedFlow* fragmentedFlow) const
2036 {
2037     if (!fragmentedFlow)
2038         return false;
2039
2040     RenderFragmentContainer* currentFragment = m_flow.fragmentAtBlockOffset(rootBox->lineTopWithLeading() + lineDelta);
2041     // Just bail if the fragment didn't change.
2042     if (rootBox->containingFragment() == currentFragment)
2043         return false;
2044     return rootBox->paginatedLineWidth() != m_flow.availableLogicalWidthForContent(currentFragment);
2045 }
2046
2047 bool ComplexLineLayout::matchedEndLine(LineLayoutState& layoutState, const InlineBidiResolver& resolver, const InlineIterator& endLineStart, const BidiStatus& endLineStatus)
2048 {
2049     if (resolver.position() == endLineStart) {
2050         if (resolver.status() != endLineStatus)
2051             return false;
2052         return checkPaginationAndFloatsAtEndLine(layoutState);
2053     }
2054
2055     // The first clean line doesn't match, but we can check a handful of following lines to try
2056     // to match back up.
2057     static const int numLines = 8; // The # of lines we're willing to match against.
2058     RootInlineBox* originalEndLine = layoutState.endLine();
2059     RootInlineBox* line = originalEndLine;
2060     for (int i = 0; i < numLines && line; i++, line = line->nextRootBox()) {
2061         if (line->lineBreakObj() == resolver.position().renderer() && line->lineBreakPos() == resolver.position().offset()) {
2062             // We have a match.
2063             if (line->lineBreakBidiStatus() != resolver.status())
2064                 return false; // ...but the bidi state doesn't match.
2065             
2066             bool matched = false;
2067             RootInlineBox* result = line->nextRootBox();
2068             layoutState.setEndLine(result);
2069             if (result) {
2070                 layoutState.setEndLineLogicalTop(line->lineBottomWithLeading());
2071                 matched = checkPaginationAndFloatsAtEndLine(layoutState);
2072             }
2073
2074             // Now delete the lines that we failed to sync.
2075             deleteLineRange(layoutState, originalEndLine, result);
2076             return matched;
2077         }
2078     }
2079
2080     return false;
2081 }
2082
2083 void ComplexLineLayout::addOverflowFromInlineChildren()
2084 {
2085     ASSERT(!m_flow.simpleLineLayout());
2086
2087     LayoutUnit endPadding = m_flow.hasOverflowClip() ? m_flow.paddingEnd() : 0_lu;
2088     // FIXME: Need to find another way to do this, since scrollbars could show when we don't want them to.
2089     if (m_flow.hasOverflowClip() && !endPadding && m_flow.element() && m_flow.element()->isRootEditableElement() && style().isLeftToRightDirection())
2090         endPadding = 1;
2091     for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
2092         m_flow.addLayoutOverflow(curr->paddedLayoutOverflowRect(endPadding));
2093         RenderFragmentContainer* fragment = m_flow.enclosingFragmentedFlow() ? curr->containingFragment() : nullptr;
2094         if (fragment)
2095             fragment->addLayoutOverflowForBox(&m_flow, curr->paddedLayoutOverflowRect(endPadding));
2096         if (!m_flow.hasOverflowClip()) {
2097             LayoutRect childVisualOverflowRect = curr->visualOverflowRect(curr->lineTop(), curr->lineBottom());
2098             m_flow.addVisualOverflow(childVisualOverflowRect);
2099             if (fragment)
2100                 fragment->addVisualOverflowForBox(&m_flow, childVisualOverflowRect);
2101         }
2102     }
2103 }
2104
2105 void ComplexLineLayout::deleteEllipsisLineBoxes()
2106 {
2107     TextAlignMode textAlign = style().textAlign();
2108     bool ltr = style().isLeftToRightDirection();
2109     IndentTextOrNot shouldIndentText = IndentText;
2110     for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
2111         if (curr->hasEllipsisBox()) {
2112             curr->clearTruncation();
2113
2114             // Shift the line back where it belongs if we cannot accomodate an ellipsis.
2115             float logicalLeft = m_flow.logicalLeftOffsetForLine(curr->lineTop(), shouldIndentText);
2116             float availableLogicalWidth = m_flow.logicalRightOffsetForLine(curr->lineTop(), DoNotIndentText) - logicalLeft;
2117             float totalLogicalWidth = curr->logicalWidth();
2118             updateLogicalWidthForAlignment(m_flow, textAlign, curr, 0, logicalLeft, totalLogicalWidth, availableLogicalWidth, 0);
2119
2120             if (ltr)
2121                 curr->adjustLogicalPosition((logicalLeft - curr->logicalLeft()), 0);
2122             else
2123                 curr->adjustLogicalPosition(-(curr->logicalLeft() - logicalLeft), 0);
2124         }
2125         shouldIndentText = DoNotIndentText;
2126     }
2127 }
2128
2129 void ComplexLineLayout::checkLinesForTextOverflow()
2130 {
2131     // Determine the width of the ellipsis using the current font.
2132     // FIXME: CSS3 says this is configurable, also need to use 0x002E (FULL STOP) if horizontal ellipsis is "not renderable"
2133     const FontCascade& font = style().fontCascade();
2134     static NeverDestroyed<AtomString> ellipsisStr(&horizontalEllipsis, 1);
2135     const FontCascade& firstLineFont = m_flow.firstLineStyle().fontCascade();
2136     float firstLineEllipsisWidth = firstLineFont.width(m_flow.constructTextRun(&horizontalEllipsis, 1, m_flow.firstLineStyle()));
2137     float ellipsisWidth = (font == firstLineFont) ? firstLineEllipsisWidth : font.width(m_flow.constructTextRun(&horizontalEllipsis, 1, style()));
2138
2139     // For LTR text truncation, we want to get the right edge of our padding box, and then we want to see
2140     // if the right edge of a line box exceeds that. For RTL, we use the left edge of the padding box and
2141     // check the left edge of the line box to see if it is less
2142     // Include the scrollbar for overflow blocks, which means we want to use "contentWidth()"
2143     bool ltr = style().isLeftToRightDirection();
2144     TextAlignMode textAlign = style().textAlign();
2145     bool firstLine = true;
2146     for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
2147         IndentTextOrNot shouldIndentText = firstLine ? IndentText : DoNotIndentText;
2148         LayoutUnit blockRightEdge = m_flow.logicalRightOffsetForLine(curr->lineTop(), shouldIndentText);
2149         LayoutUnit blockLeftEdge = m_flow.logicalLeftOffsetForLine(curr->lineTop(), shouldIndentText);
2150         LayoutUnit lineBoxEdge { ltr ? curr->x() + curr->logicalWidth() : curr->x() };
2151         if ((ltr && lineBoxEdge > blockRightEdge) || (!ltr && lineBoxEdge < blockLeftEdge)) {
2152             // This line spills out of our box in the appropriate direction. Now we need to see if the line
2153             // can be truncated. In order for truncation to be possible, the line must have sufficient space to
2154             // accommodate our truncation string, and no replaced elements (images, tables) can overlap the ellipsis
2155             // space.
2156             LayoutUnit width { firstLine ? firstLineEllipsisWidth : ellipsisWidth };
2157             LayoutUnit blockEdge { ltr ? blockRightEdge : blockLeftEdge };
2158             if (curr->lineCanAccommodateEllipsis(ltr, blockEdge, lineBoxEdge, width)) {
2159                 float totalLogicalWidth = curr->placeEllipsis(ellipsisStr, ltr, blockLeftEdge, blockRightEdge, width);
2160
2161                 float logicalLeft = 0; // We are only interested in the delta from the base position.
2162                 float truncatedWidth = m_flow.availableLogicalWidthForLine(curr->lineTop(), shouldIndentText);
2163                 updateLogicalWidthForAlignment(m_flow, textAlign, curr, nullptr, logicalLeft, totalLogicalWidth, truncatedWidth, 0);
2164                 if (ltr)
2165                     curr->adjustLogicalPosition(logicalLeft, 0);
2166                 else
2167                     curr->adjustLogicalPosition(-(truncatedWidth - (logicalLeft + totalLogicalWidth)), 0);
2168             }
2169         }
2170         firstLine = false;
2171     }
2172 }
2173
2174 bool ComplexLineLayout::positionNewFloatOnLine(const FloatingObject& newFloat, FloatingObject* lastFloatFromPreviousLine, LineInfo& lineInfo, LineWidth& width)
2175 {
2176     if (!m_flow.positionNewFloats())
2177         return false;
2178
2179     width.shrinkAvailableWidthForNewFloatIfNeeded(newFloat);
2180
2181     // We only connect floats to lines for pagination purposes if the floats occur at the start of
2182     // the line and the previous line had a hard break (so this line is either the first in the block
2183     // or follows a <br>).
2184     if (!newFloat.paginationStrut() || !lineInfo.previousLineBrokeCleanly() || !lineInfo.isEmpty())
2185         return true;
2186
2187     const FloatingObjectSet& floatingObjectSet = m_flow.floatingObjects()->set();
2188     ASSERT(floatingObjectSet.last().get() == &newFloat);
2189
2190     LayoutUnit floatLogicalTop = m_flow.logicalTopForFloat(newFloat);
2191     LayoutUnit paginationStrut = newFloat.paginationStrut();
2192
2193     if (floatLogicalTop - paginationStrut != m_flow.logicalHeight() + lineInfo.floatPaginationStrut())
2194         return true;
2195
2196     auto it = floatingObjectSet.end();
2197     --it; // Last float is newFloat, skip that one.
2198     auto begin = floatingObjectSet.begin();
2199     while (it != begin) {
2200         --it;
2201         auto& floatingObject = *it->get();
2202         if (&floatingObject == lastFloatFromPreviousLine)
2203             break;
2204         if (m_flow.logicalTopForFloat(floatingObject) == m_flow.logicalHeight() + lineInfo.floatPaginationStrut()) {
2205             floatingObject.setPaginationStrut(paginationStrut + floatingObject.paginationStrut());
2206             RenderBox& floatBox = floatingObject.renderer();
2207             m_flow.setLogicalTopForChild(floatBox, m_flow.logicalTopForChild(floatBox) + m_flow.marginBeforeForChild(floatBox) + paginationStrut);
2208
2209             if (m_flow.updateFragmentRangeForBoxChild(floatBox))
2210                 floatBox.setNeedsLayout(MarkOnlyThis);
2211             else if (is<RenderBlock>(floatBox))
2212                 downcast<RenderBlock>(floatBox).setChildNeedsLayout(MarkOnlyThis);
2213             floatBox.layoutIfNeeded();
2214
2215             // Save the old logical top before calling removePlacedObject which will set
2216             // isPlaced to false. Otherwise it will trigger an assert in logicalTopForFloat.
2217             LayoutUnit oldLogicalTop = m_flow.logicalTopForFloat(floatingObject);
2218             m_flow.floatingObjects()->removePlacedObject(&floatingObject);
2219             m_flow.setLogicalTopForFloat(floatingObject, oldLogicalTop + paginationStrut);
2220             m_flow.floatingObjects()->addPlacedObject(&floatingObject);
2221         }
2222     }
2223
2224     // Just update the line info's pagination strut without altering our logical height yet. If the line ends up containing
2225     // no content, then we don't want to improperly grow the height of the block.
2226     lineInfo.setFloatPaginationStrut(lineInfo.floatPaginationStrut() + paginationStrut);
2227     return true;
2228 }
2229
2230 void ComplexLineLayout::updateFragmentForLine(RootInlineBox* lineBox) const
2231 {
2232     ASSERT(lineBox);
2233
2234     if (!m_flow.hasFragmentRangeInFragmentedFlow())
2235         lineBox->clearContainingFragment();
2236     else {
2237         if (auto containingFragment = m_flow.fragmentAtBlockOffset(lineBox->lineTopWithLeading()))
2238             lineBox->setContainingFragment(*containingFragment);
2239         else
2240             lineBox->clearContainingFragment();
2241     }
2242
2243     RootInlineBox* prevLineBox = lineBox->prevRootBox();
2244     if (!prevLineBox)
2245         return;
2246
2247     // This check is more accurate than the one in |adjustLinePositionForPagination| because it takes into
2248     // account just the container changes between lines. The before mentioned function doesn't set the flag
2249     // correctly if the line is positioned at the top of the last fragment container.
2250     if (lineBox->containingFragment() != prevLineBox->containingFragment())
2251         lineBox->setIsFirstAfterPageBreak(true);
2252 }
2253
2254 const RenderStyle& ComplexLineLayout::style() const
2255 {
2256     return m_flow.style();
2257 }
2258
2259 const FrameViewLayoutContext& ComplexLineLayout::layoutContext() const
2260 {
2261     return m_flow.view().frameView().layoutContext();
2262 }
2263
2264
2265 }