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