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