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