23296c6d2fd3354df3f172fbf7240ac76399d69c
[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  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Library General Public
9  * License as published by the Free Software Foundation; either
10  * version 2 of the License, or (at your option) any later version.
11  *
12  * This library is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * Library General Public License for more details.
16  *
17  * You should have received a copy of the GNU Library General Public License
18  * along with this library; see the file COPYING.LIB.  If not, write to
19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
20  * Boston, MA 02110-1301, USA.
21  *
22  */
23
24 #include "config.h"
25
26 #include "AXObjectCache.h"
27 #include "BidiResolver.h"
28 #include "FloatingObjects.h"
29 #include "Hyphenation.h"
30 #include "InlineIterator.h"
31 #include "InlineTextBox.h"
32 #include "LineInfo.h"
33 #include "LineLayoutState.h"
34 #include "Logging.h"
35 #include "RenderArena.h"
36 #include "RenderBlockFlow.h"
37 #include "RenderCombineText.h"
38 #include "RenderCounter.h"
39 #include "RenderFlowThread.h"
40 #include "RenderInline.h"
41 #include "RenderLayer.h"
42 #include "RenderLineBreak.h"
43 #include "RenderListMarker.h"
44 #include "RenderRegion.h"
45 #include "RenderRubyRun.h"
46 #include "RenderView.h"
47 #include "Settings.h"
48 #include "SimpleLineLayoutFunctions.h"
49 #include "TrailingFloatsRootInlineBox.h"
50 #include "VerticalPositionCache.h"
51 #include "break_lines.h"
52 #include <wtf/RefCountedLeakCounter.h>
53 #include <wtf/StdLibExtras.h>
54 #include <wtf/Vector.h>
55 #include <wtf/unicode/CharacterNames.h>
56
57 #if ENABLE(CSS_SHAPES)
58 #include "ShapeInsideInfo.h"
59 #endif
60
61 #if ENABLE(SVG)
62 #include "RenderSVGInlineText.h"
63 #include "SVGRootInlineBox.h"
64 #endif
65
66 using namespace std;
67 using namespace WTF;
68 using namespace Unicode;
69
70 namespace WebCore {
71
72 // We don't let our line box tree for a single line get any deeper than this.
73 const unsigned cMaxLineDepth = 200;
74
75 struct RenderTextInfo {
76     // Destruction of m_layout requires TextLayout to be a complete type, so the constructor and destructor are made non-inline to avoid compilation errors.
77     RenderTextInfo();
78     ~RenderTextInfo();
79
80     RenderText* m_text;
81     OwnPtr<TextLayout> m_layout;
82     LazyLineBreakIterator m_lineBreakIterator;
83     const Font* m_font;
84 };
85
86 class LineBreaker {
87 public:
88     friend class BreakingContext;
89     LineBreaker(RenderBlockFlow& block)
90         : m_block(block)
91     {
92         reset();
93     }
94
95     InlineIterator nextLineBreak(InlineBidiResolver&, LineInfo&, RenderTextInfo&, FloatingObject* lastFloatFromPreviousLine, unsigned consecutiveHyphenatedLines, WordMeasurements&);
96
97     bool lineWasHyphenated() { return m_hyphenated; }
98     const Vector<RenderBox*>& positionedObjects() { return m_positionedObjects; }
99     EClear clear() { return m_clear; }
100
101 private:
102     void reset();
103
104     InlineIterator nextSegmentBreak(InlineBidiResolver&, LineInfo&, RenderTextInfo&, FloatingObject* lastFloatFromPreviousLine, unsigned consecutiveHyphenatedLines, WordMeasurements&);
105     void skipTrailingWhitespace(InlineIterator&, const LineInfo&);
106     void skipLeadingWhitespace(InlineBidiResolver&, LineInfo&, FloatingObject* lastFloatFromPreviousLine, LineWidth&);
107
108     RenderBlockFlow& m_block;
109     bool m_hyphenated;
110     EClear m_clear;
111     Vector<RenderBox*> m_positionedObjects;
112 };
113
114 static inline LayoutUnit borderPaddingMarginStart(const RenderInline& child)
115 {
116     return child.marginStart() + child.paddingStart() + child.borderStart();
117 }
118
119 static inline LayoutUnit borderPaddingMarginEnd(const RenderInline& child)
120 {
121     return child.marginEnd() + child.paddingEnd() + child.borderEnd();
122 }
123
124 static inline bool shouldAddBorderPaddingMargin(RenderObject* child)
125 {
126     // When deciding whether we're at the edge of an inline, adjacent collapsed whitespace is the same as no sibling at all.
127     return !child || (child->isText() && !toRenderText(child)->textLength());
128 }
129
130 static RenderObject* previousInFlowSibling(RenderObject* child)
131 {
132     child = child->previousSibling();
133     while (child && child->isOutOfFlowPositioned())
134         child = child->previousSibling();
135     return child;
136 }
137
138 static LayoutUnit inlineLogicalWidth(RenderObject* child, bool checkStartEdge = true, bool checkEndEdge = true)
139 {
140     unsigned lineDepth = 1;
141     LayoutUnit extraWidth = 0;
142     RenderElement* parent = child->parent();
143     while (parent->isRenderInline() && lineDepth++ < cMaxLineDepth) {
144         const RenderInline& parentAsRenderInline = toRenderInline(*parent);
145         if (!isEmptyInline(parentAsRenderInline)) {
146             checkStartEdge = checkStartEdge && shouldAddBorderPaddingMargin(previousInFlowSibling(child));
147             if (checkStartEdge)
148                 extraWidth += borderPaddingMarginStart(parentAsRenderInline);
149             checkEndEdge = checkEndEdge && shouldAddBorderPaddingMargin(child->nextSibling());
150             if (checkEndEdge)
151                 extraWidth += borderPaddingMarginEnd(parentAsRenderInline);
152             if (!checkStartEdge && !checkEndEdge)
153                 return extraWidth;
154         }
155         child = parent;
156         parent = child->parent();
157     }
158     return extraWidth;
159 }
160
161 static void determineDirectionality(TextDirection& dir, InlineIterator iter)
162 {
163     while (!iter.atEnd()) {
164         if (iter.atParagraphSeparator())
165             return;
166         if (UChar current = iter.current()) {
167             UCharDirection charDirection = u_charDirection(current);
168             if (charDirection == U_LEFT_TO_RIGHT) {
169                 dir = LTR;
170                 return;
171             }
172             if (charDirection == U_RIGHT_TO_LEFT || charDirection == U_RIGHT_TO_LEFT_ARABIC) {
173                 dir = RTL;
174                 return;
175             }
176         }
177         iter.increment();
178     }
179 }
180
181 static void checkMidpoints(LineMidpointState& lineMidpointState, InlineIterator& lBreak)
182 {
183     // Check to see if our last midpoint is a start point beyond the line break.  If so,
184     // shave it off the list, and shave off a trailing space if the previous end point doesn't
185     // preserve whitespace.
186     if (lBreak.m_obj && lineMidpointState.numMidpoints && !(lineMidpointState.numMidpoints % 2)) {
187         InlineIterator* midpoints = lineMidpointState.midpoints.data();
188         InlineIterator& endpoint = midpoints[lineMidpointState.numMidpoints - 2];
189         const InlineIterator& startpoint = midpoints[lineMidpointState.numMidpoints - 1];
190         InlineIterator currpoint = endpoint;
191         while (!currpoint.atEnd() && currpoint != startpoint && currpoint != lBreak)
192             currpoint.increment();
193         if (currpoint == lBreak) {
194             // We hit the line break before the start point.  Shave off the start point.
195             lineMidpointState.numMidpoints--;
196             if (endpoint.m_obj->style()->collapseWhiteSpace() && endpoint.m_obj->isText())
197                 endpoint.m_pos--;
198         }
199     }
200 }
201
202 // Don't call this directly. Use one of the descriptive helper functions below.
203 static void deprecatedAddMidpoint(LineMidpointState& lineMidpointState, const InlineIterator& midpoint)
204 {
205     if (lineMidpointState.midpoints.size() <= lineMidpointState.numMidpoints)
206         lineMidpointState.midpoints.grow(lineMidpointState.numMidpoints + 10);
207
208     InlineIterator* midpoints = lineMidpointState.midpoints.data();
209     midpoints[lineMidpointState.numMidpoints++] = midpoint;
210 }
211
212 static inline void startIgnoringSpaces(LineMidpointState& lineMidpointState, const InlineIterator& midpoint)
213 {
214     ASSERT(!(lineMidpointState.numMidpoints % 2));
215     deprecatedAddMidpoint(lineMidpointState, midpoint);
216 }
217
218 static inline void stopIgnoringSpaces(LineMidpointState& lineMidpointState, const InlineIterator& midpoint)
219 {
220     ASSERT(lineMidpointState.numMidpoints % 2);
221     deprecatedAddMidpoint(lineMidpointState, midpoint);
222 }
223
224 // When ignoring spaces, this needs to be called for objects that need line boxes such as RenderInlines or
225 // hard line breaks to ensure that they're not ignored.
226 static inline void ensureLineBoxInsideIgnoredSpaces(LineMidpointState& lineMidpointState, RenderObject* renderer)
227 {
228     InlineIterator midpoint(0, renderer, 0);
229     stopIgnoringSpaces(lineMidpointState, midpoint);
230     startIgnoringSpaces(lineMidpointState, midpoint);
231 }
232
233 // Adding a pair of midpoints before a character will split it out into a new line box.
234 static inline void ensureCharacterGetsLineBox(LineMidpointState& lineMidpointState, InlineIterator& textParagraphSeparator)
235 {
236     InlineIterator midpoint(0, textParagraphSeparator.m_obj, textParagraphSeparator.m_pos);
237     startIgnoringSpaces(lineMidpointState, InlineIterator(0, textParagraphSeparator.m_obj, textParagraphSeparator.m_pos - 1));
238     stopIgnoringSpaces(lineMidpointState, InlineIterator(0, textParagraphSeparator.m_obj, textParagraphSeparator.m_pos));
239 }
240
241 static inline BidiRun* createRun(int start, int end, RenderObject* obj, InlineBidiResolver& resolver)
242 {
243     return new (obj->renderArena()) BidiRun(start, end, obj, resolver.context(), resolver.dir());
244 }
245
246 void RenderBlockFlow::appendRunsForObject(BidiRunList<BidiRun>& runs, int start, int end, RenderObject* obj, InlineBidiResolver& resolver)
247 {
248     if (start > end || shouldSkipCreatingRunsForObject(obj))
249         return;
250
251     LineMidpointState& lineMidpointState = resolver.midpointState();
252     bool haveNextMidpoint = (lineMidpointState.currentMidpoint < lineMidpointState.numMidpoints);
253     InlineIterator nextMidpoint;
254     if (haveNextMidpoint)
255         nextMidpoint = lineMidpointState.midpoints[lineMidpointState.currentMidpoint];
256     if (lineMidpointState.betweenMidpoints) {
257         if (!(haveNextMidpoint && nextMidpoint.m_obj == obj))
258             return;
259         // This is a new start point. Stop ignoring objects and
260         // adjust our start.
261         lineMidpointState.betweenMidpoints = false;
262         start = nextMidpoint.m_pos;
263         lineMidpointState.currentMidpoint++;
264         if (start < end)
265             return appendRunsForObject(runs, start, end, obj, resolver);
266     } else {
267         if (!haveNextMidpoint || (obj != nextMidpoint.m_obj)) {
268             runs.addRun(createRun(start, end, obj, resolver));
269             return;
270         }
271
272         // An end midpoint has been encountered within our object.  We
273         // need to go ahead and append a run with our endpoint.
274         if (static_cast<int>(nextMidpoint.m_pos + 1) <= end) {
275             lineMidpointState.betweenMidpoints = true;
276             lineMidpointState.currentMidpoint++;
277             if (nextMidpoint.m_pos != UINT_MAX) { // UINT_MAX means stop at the object and don't include any of it.
278                 if (static_cast<int>(nextMidpoint.m_pos + 1) > start)
279                     runs.addRun(createRun(start, nextMidpoint.m_pos + 1, obj, resolver));
280                 return appendRunsForObject(runs, nextMidpoint.m_pos + 1, end, obj, resolver);
281             }
282         } else
283            runs.addRun(createRun(start, end, obj, resolver));
284     }
285 }
286
287 RootInlineBox* RenderBlockFlow::createRootInlineBox()
288 {
289     return new (renderArena()) RootInlineBox(*this);
290 }
291
292 RootInlineBox* RenderBlockFlow::createAndAppendRootInlineBox()
293 {
294     RootInlineBox* rootBox = createRootInlineBox();
295     m_lineBoxes.appendLineBox(rootBox);
296
297     if (UNLIKELY(AXObjectCache::accessibilityEnabled()) && m_lineBoxes.firstLineBox() == rootBox) {
298         if (AXObjectCache* cache = document().existingAXObjectCache())
299             cache->recomputeIsIgnored(this);
300     }
301
302     return rootBox;
303 }
304
305
306 static inline InlineBox* createInlineBoxForRenderer(RenderObject* obj, bool isRootLineBox, bool isOnlyRun = false)
307 {
308     if (isRootLineBox)
309         return toRenderBlockFlow(obj)->createAndAppendRootInlineBox();
310
311     if (obj->isText())
312         return toRenderText(obj)->createInlineTextBox();
313
314     if (obj->isBox())
315         return toRenderBox(obj)->createInlineBox();
316
317     if (obj->isLineBreak()) {
318         InlineBox* inlineBox = toRenderLineBreak(obj)->createInlineBox();
319         // We only treat a box as text for a <br> if we are on a line by ourself or in strict mode
320         // (Note the use of strict mode. In "almost strict" mode, we don't treat the box for <br> as text.)
321         inlineBox->setBehavesLikeText(isOnlyRun || obj->document().inNoQuirksMode() || obj->isLineBreakOpportunity());
322         return inlineBox;
323     }
324
325     return toRenderInline(obj)->createAndAppendInlineFlowBox();
326 }
327
328 // FIXME: Don't let counters mark themselves as needing pref width recalcs during layout
329 // so we don't need this hack.
330 static inline void updateCounterIfNeeded(RenderText& renderText)
331 {
332     if (!renderText.preferredLogicalWidthsDirty() || !renderText.isCounter())
333         return;
334     toRenderCounter(renderText).updateCounter();
335 }
336
337 static inline void dirtyLineBoxesForRenderer(RenderObject& renderer, bool fullLayout)
338 {
339     if (renderer.isText()) {
340         RenderText& renderText = toRenderText(renderer);
341         updateCounterIfNeeded(renderText);
342         renderText.dirtyLineBoxes(fullLayout);
343     } else if (renderer.isLineBreak())
344         toRenderLineBreak(renderer).dirtyLineBoxes(fullLayout);
345     else
346         toRenderInline(renderer).dirtyLineBoxes(fullLayout);
347 }
348
349 static bool parentIsConstructedOrHaveNext(InlineFlowBox* parentBox)
350 {
351     do {
352         if (parentBox->isConstructed() || parentBox->nextOnLine())
353             return true;
354         parentBox = parentBox->parent();
355     } while (parentBox);
356     return false;
357 }
358
359 InlineFlowBox* RenderBlockFlow::createLineBoxes(RenderObject* obj, const LineInfo& lineInfo, InlineBox* childBox, bool startNewSegment)
360 {
361     // See if we have an unconstructed line box for this object that is also
362     // the last item on the line.
363     unsigned lineDepth = 1;
364     InlineFlowBox* parentBox = 0;
365     InlineFlowBox* result = 0;
366     bool hasDefaultLineBoxContain = style()->lineBoxContain() == RenderStyle::initialLineBoxContain();
367     do {
368         ASSERT_WITH_SECURITY_IMPLICATION(obj->isRenderInline() || obj == this);
369
370         RenderInline* inlineFlow = (obj != this) ? toRenderInline(obj) : 0;
371
372         // Get the last box we made for this render object.
373         parentBox = inlineFlow ? inlineFlow->lastLineBox() : toRenderBlockFlow(obj)->lastLineBox();
374
375         // If this box or its ancestor is constructed then it is from a previous line, and we need
376         // to make a new box for our line.  If this box or its ancestor is unconstructed but it has
377         // something following it on the line, then we know we have to make a new box
378         // as well.  In this situation our inline has actually been split in two on
379         // the same line (this can happen with very fancy language mixtures).
380         bool constructedNewBox = false;
381         bool allowedToConstructNewBox = !hasDefaultLineBoxContain || !inlineFlow || inlineFlow->alwaysCreateLineBoxes();
382         bool mustCreateBoxesToRoot = startNewSegment && !(parentBox && parentBox->isRootInlineBox());
383         bool canUseExistingParentBox = parentBox && !parentIsConstructedOrHaveNext(parentBox) && !mustCreateBoxesToRoot;
384         if (allowedToConstructNewBox && !canUseExistingParentBox) {
385             // We need to make a new box for this render object.  Once
386             // made, we need to place it at the end of the current line.
387             InlineBox* newBox = createInlineBoxForRenderer(obj, obj == this);
388             ASSERT_WITH_SECURITY_IMPLICATION(newBox->isInlineFlowBox());
389             parentBox = toInlineFlowBox(newBox);
390             parentBox->setIsFirstLine(lineInfo.isFirstLine());
391             parentBox->setIsHorizontal(isHorizontalWritingMode());
392             if (!hasDefaultLineBoxContain)
393                 parentBox->clearDescendantsHaveSameLineHeightAndBaseline();
394             constructedNewBox = true;
395         }
396
397         if (constructedNewBox || canUseExistingParentBox) {
398             if (!result)
399                 result = parentBox;
400
401             // If we have hit the block itself, then |box| represents the root
402             // inline box for the line, and it doesn't have to be appended to any parent
403             // inline.
404             if (childBox)
405                 parentBox->addToLine(childBox);
406
407             if (!constructedNewBox || obj == this)
408                 break;
409
410             childBox = parentBox;
411         }
412
413         // If we've exceeded our line depth, then jump straight to the root and skip all the remaining
414         // intermediate inline flows.
415         obj = (++lineDepth >= cMaxLineDepth) ? this : obj->parent();
416
417     } while (true);
418
419     return result;
420 }
421
422 template <typename CharacterType>
423 static inline bool endsWithASCIISpaces(const CharacterType* characters, unsigned pos, unsigned end)
424 {
425     while (isASCIISpace(characters[pos])) {
426         pos++;
427         if (pos >= end)
428             return true;
429     }
430     return false;
431 }
432
433 static bool reachedEndOfTextRenderer(const BidiRunList<BidiRun>& bidiRuns)
434 {
435     BidiRun* run = bidiRuns.logicallyLastRun();
436     if (!run)
437         return true;
438     unsigned pos = run->stop();
439     RenderObject* r = run->m_object;
440     if (!r->isText())
441         return false;
442     RenderText* renderText = toRenderText(r);
443     unsigned length = renderText->textLength();
444     if (pos >= length)
445         return true;
446
447     if (renderText->is8Bit())
448         return endsWithASCIISpaces(renderText->characters8(), pos, length);
449     return endsWithASCIISpaces(renderText->characters16(), pos, length);
450 }
451
452 RootInlineBox* RenderBlockFlow::constructLine(BidiRunList<BidiRun>& bidiRuns, const LineInfo& lineInfo)
453 {
454     ASSERT(bidiRuns.firstRun());
455
456     bool rootHasSelectedChildren = false;
457     InlineFlowBox* parentBox = 0;
458     int runCount = bidiRuns.runCount() - lineInfo.runsFromLeadingWhitespace();
459     for (BidiRun* r = bidiRuns.firstRun(); r; r = r->next()) {
460         // Create a box for our object.
461         bool isOnlyRun = (runCount == 1);
462         if (runCount == 2 && !r->m_object->isListMarker())
463             isOnlyRun = (!style()->isLeftToRightDirection() ? bidiRuns.lastRun() : bidiRuns.firstRun())->m_object->isListMarker();
464
465         if (lineInfo.isEmpty())
466             continue;
467
468         InlineBox* box = createInlineBoxForRenderer(r->m_object, false, isOnlyRun);
469         r->m_box = box;
470
471         ASSERT(box);
472         if (!box)
473             continue;
474
475         if (!rootHasSelectedChildren && box->renderer().selectionState() != RenderObject::SelectionNone)
476             rootHasSelectedChildren = true;
477
478         // If we have no parent box yet, or if the run is not simply a sibling,
479         // then we need to construct inline boxes as necessary to properly enclose the
480         // run's inline box. Segments can only be siblings at the root level, as
481         // they are positioned separately.
482 #if ENABLE(CSS_SHAPES)
483         bool runStartsSegment = r->m_startsSegment;
484 #else
485         bool runStartsSegment = false;
486 #endif
487         if (!parentBox || &parentBox->renderer() != r->m_object->parent() || runStartsSegment)
488             // Create new inline boxes all the way back to the appropriate insertion point.
489             parentBox = createLineBoxes(r->m_object->parent(), lineInfo, box, runStartsSegment);
490         else {
491             // Append the inline box to this line.
492             parentBox->addToLine(box);
493         }
494
495         bool visuallyOrdered = r->m_object->style()->rtlOrdering() == VisualOrder;
496         box->setBidiLevel(r->level());
497
498         if (box->isInlineTextBox()) {
499             InlineTextBox* text = toInlineTextBox(box);
500             text->setStart(r->m_start);
501             text->setLen(r->m_stop - r->m_start);
502             text->setDirOverride(r->dirOverride(visuallyOrdered));
503             if (r->m_hasHyphen)
504                 text->setHasHyphen(true);
505         }
506     }
507
508     // We should have a root inline box.  It should be unconstructed and
509     // be the last continuation of our line list.
510     ASSERT(lastLineBox() && !lastLineBox()->isConstructed());
511
512     // Set the m_selectedChildren flag on the root inline box if one of the leaf inline box
513     // from the bidi runs walk above has a selection state.
514     if (rootHasSelectedChildren)
515         lastLineBox()->root().setHasSelectedChildren(true);
516
517     // Set bits on our inline flow boxes that indicate which sides should
518     // paint borders/margins/padding.  This knowledge will ultimately be used when
519     // we determine the horizontal positions and widths of all the inline boxes on
520     // the line.
521     bool isLogicallyLastRunWrapped = bidiRuns.logicallyLastRun()->m_object && bidiRuns.logicallyLastRun()->m_object->isText() ? !reachedEndOfTextRenderer(bidiRuns) : true;
522     lastLineBox()->determineSpacingForFlowBoxes(lineInfo.isLastLine(), isLogicallyLastRunWrapped, bidiRuns.logicallyLastRun()->m_object);
523
524     // Now mark the line boxes as being constructed.
525     lastLineBox()->setConstructed();
526
527     // Return the last line.
528     return lastRootBox();
529 }
530
531 ETextAlign RenderBlock::textAlignmentForLine(bool endsWithSoftBreak) const
532 {
533     ETextAlign alignment = style()->textAlign();
534     if (!endsWithSoftBreak && alignment == JUSTIFY)
535         alignment = TASTART;
536
537     return alignment;
538 }
539
540 static void updateLogicalWidthForLeftAlignedBlock(bool isLeftToRightDirection, BidiRun* trailingSpaceRun, float& logicalLeft, float& totalLogicalWidth, float availableLogicalWidth)
541 {
542     // The direction of the block should determine what happens with wide lines.
543     // In particular with RTL blocks, wide lines should still spill out to the left.
544     if (isLeftToRightDirection) {
545         if (totalLogicalWidth > availableLogicalWidth && trailingSpaceRun)
546             trailingSpaceRun->m_box->setLogicalWidth(max<float>(0, trailingSpaceRun->m_box->logicalWidth() - totalLogicalWidth + availableLogicalWidth));
547         return;
548     }
549
550     if (trailingSpaceRun)
551         trailingSpaceRun->m_box->setLogicalWidth(0);
552     else if (totalLogicalWidth > availableLogicalWidth)
553         logicalLeft -= (totalLogicalWidth - availableLogicalWidth);
554 }
555
556 static void updateLogicalWidthForRightAlignedBlock(bool isLeftToRightDirection, BidiRun* trailingSpaceRun, float& logicalLeft, float& totalLogicalWidth, float availableLogicalWidth)
557 {
558     // Wide lines spill out of the block based off direction.
559     // So even if text-align is right, if direction is LTR, wide lines should overflow out of the right
560     // side of the block.
561     if (isLeftToRightDirection) {
562         if (trailingSpaceRun) {
563             totalLogicalWidth -= trailingSpaceRun->m_box->logicalWidth();
564             trailingSpaceRun->m_box->setLogicalWidth(0);
565         }
566         if (totalLogicalWidth < availableLogicalWidth)
567             logicalLeft += availableLogicalWidth - totalLogicalWidth;
568         return;
569     }
570
571     if (totalLogicalWidth > availableLogicalWidth && trailingSpaceRun) {
572         trailingSpaceRun->m_box->setLogicalWidth(max<float>(0, trailingSpaceRun->m_box->logicalWidth() - totalLogicalWidth + availableLogicalWidth));
573         totalLogicalWidth -= trailingSpaceRun->m_box->logicalWidth();
574     } else
575         logicalLeft += availableLogicalWidth - totalLogicalWidth;
576 }
577
578 static void updateLogicalWidthForCenterAlignedBlock(bool isLeftToRightDirection, BidiRun* trailingSpaceRun, float& logicalLeft, float& totalLogicalWidth, float availableLogicalWidth)
579 {
580     float trailingSpaceWidth = 0;
581     if (trailingSpaceRun) {
582         totalLogicalWidth -= trailingSpaceRun->m_box->logicalWidth();
583         trailingSpaceWidth = min(trailingSpaceRun->m_box->logicalWidth(), (availableLogicalWidth - totalLogicalWidth + 1) / 2);
584         trailingSpaceRun->m_box->setLogicalWidth(max<float>(0, trailingSpaceWidth));
585     }
586     if (isLeftToRightDirection)
587         logicalLeft += max<float>((availableLogicalWidth - totalLogicalWidth) / 2, 0);
588     else
589         logicalLeft += totalLogicalWidth > availableLogicalWidth ? (availableLogicalWidth - totalLogicalWidth) : (availableLogicalWidth - totalLogicalWidth) / 2 - trailingSpaceWidth;
590 }
591
592 void RenderBlockFlow::setMarginsForRubyRun(BidiRun* run, RenderRubyRun& renderer, RenderObject* previousObject, const LineInfo& lineInfo)
593 {
594     int startOverhang;
595     int endOverhang;
596     RenderObject* nextObject = 0;
597     for (BidiRun* runWithNextObject = run->next(); runWithNextObject; runWithNextObject = runWithNextObject->next()) {
598         if (!runWithNextObject->m_object->isOutOfFlowPositioned() && !runWithNextObject->m_box->isLineBreak()) {
599             nextObject = runWithNextObject->m_object;
600             break;
601         }
602     }
603     renderer.getOverhang(lineInfo.isFirstLine(), renderer.style()->isLeftToRightDirection() ? previousObject : nextObject, renderer.style()->isLeftToRightDirection() ? nextObject : previousObject, startOverhang, endOverhang);
604     setMarginStartForChild(renderer, -startOverhang);
605     setMarginEndForChild(renderer, -endOverhang);
606 }
607
608 static inline float measureHyphenWidth(RenderText* renderer, const Font& font, HashSet<const SimpleFontData*>* fallbackFonts = 0)
609 {
610     const RenderStyle& style = *renderer->style();
611     return font.width(RenderBlock::constructTextRun(renderer, font, style.hyphenString().string(), style), fallbackFonts);
612 }
613
614 class WordMeasurement {
615 public:
616     WordMeasurement()
617         : renderer(0)
618         , width(0)
619         , startOffset(0)
620         , endOffset(0)
621     {
622     }
623     
624     RenderText* renderer;
625     float width;
626     int startOffset;
627     int endOffset;
628     HashSet<const SimpleFontData*> fallbackFonts;
629 };
630
631 static inline const RenderStyle& lineStyle(const RenderElement& renderer, const LineInfo& lineInfo)
632 {
633     return lineInfo.isFirstLine() ? *renderer.firstLineStyle() : *renderer.style();
634 }
635
636 static inline void setLogicalWidthForTextRun(RootInlineBox* lineBox, BidiRun* run, RenderText* renderer, float xPos, const LineInfo& lineInfo,
637     GlyphOverflowAndFallbackFontsMap& textBoxDataMap, VerticalPositionCache& verticalPositionCache, WordMeasurements& wordMeasurements)
638 {
639     HashSet<const SimpleFontData*> fallbackFonts;
640     GlyphOverflow glyphOverflow;
641
642     const Font& font = lineStyle(*renderer->parent(), lineInfo).font();
643     // Always compute glyph overflow if the block's line-box-contain value is "glyphs".
644     if (lineBox->fitsToGlyphs()) {
645         // If we don't stick out of the root line's font box, then don't bother computing our glyph overflow. This optimization
646         // will keep us from computing glyph bounds in nearly all cases.
647         bool includeRootLine = lineBox->includesRootLineBoxFontOrLeading();
648         int baselineShift = lineBox->verticalPositionForBox(run->m_box, verticalPositionCache);
649         int rootDescent = includeRootLine ? font.fontMetrics().descent() : 0;
650         int rootAscent = includeRootLine ? font.fontMetrics().ascent() : 0;
651         int boxAscent = font.fontMetrics().ascent() - baselineShift;
652         int boxDescent = font.fontMetrics().descent() + baselineShift;
653         if (boxAscent > rootDescent ||  boxDescent > rootAscent)
654             glyphOverflow.computeBounds = true; 
655     }
656     
657     LayoutUnit hyphenWidth = 0;
658     if (toInlineTextBox(run->m_box)->hasHyphen())
659         hyphenWidth = measureHyphenWidth(renderer, font, &fallbackFonts);
660
661     float measuredWidth = 0;
662
663     bool kerningIsEnabled = font.typesettingFeatures() & Kerning;
664     bool canUseSimpleFontCodePath = renderer->canUseSimpleFontCodePath();
665     
666     // Since we don't cache glyph overflows, we need to re-measure the run if
667     // the style is linebox-contain: glyph.
668     
669     if (!lineBox->fitsToGlyphs() && canUseSimpleFontCodePath) {
670         int lastEndOffset = run->m_start;
671         for (size_t i = 0, size = wordMeasurements.size(); i < size && lastEndOffset < run->m_stop; ++i) {
672             WordMeasurement& wordMeasurement = wordMeasurements[i];
673             if (wordMeasurement.width <= 0 || wordMeasurement.startOffset == wordMeasurement.endOffset)
674                 continue;
675             if (wordMeasurement.renderer != renderer || wordMeasurement.startOffset != lastEndOffset || wordMeasurement.endOffset > run->m_stop)
676                 continue;
677
678             lastEndOffset = wordMeasurement.endOffset;
679             if (kerningIsEnabled && lastEndOffset == run->m_stop) {
680                 int wordLength = lastEndOffset - wordMeasurement.startOffset;
681                 GlyphOverflow overflow;
682                 measuredWidth += renderer->width(wordMeasurement.startOffset, wordLength, xPos + measuredWidth, lineInfo.isFirstLine(),
683                     &wordMeasurement.fallbackFonts, &overflow);
684                 UChar c = renderer->characterAt(wordMeasurement.startOffset);
685                 if (i > 0 && wordLength == 1 && (c == ' ' || c == '\t'))
686                     measuredWidth += renderer->style()->wordSpacing();
687             } else
688                 measuredWidth += wordMeasurement.width;
689             if (!wordMeasurement.fallbackFonts.isEmpty()) {
690                 HashSet<const SimpleFontData*>::const_iterator end = wordMeasurement.fallbackFonts.end();
691                 for (HashSet<const SimpleFontData*>::const_iterator it = wordMeasurement.fallbackFonts.begin(); it != end; ++it)
692                     fallbackFonts.add(*it);
693             }
694         }
695         if (measuredWidth && lastEndOffset != run->m_stop) {
696             // If we don't have enough cached data, we'll measure the run again.
697             measuredWidth = 0;
698             fallbackFonts.clear();
699         }
700     }
701
702     if (!measuredWidth)
703         measuredWidth = renderer->width(run->m_start, run->m_stop - run->m_start, xPos, lineInfo.isFirstLine(), &fallbackFonts, &glyphOverflow);
704
705     run->m_box->setLogicalWidth(measuredWidth + hyphenWidth);
706     if (!fallbackFonts.isEmpty()) {
707         ASSERT(run->m_box->behavesLikeText());
708         GlyphOverflowAndFallbackFontsMap::iterator it = textBoxDataMap.add(toInlineTextBox(run->m_box), make_pair(Vector<const SimpleFontData*>(), GlyphOverflow())).iterator;
709         ASSERT(it->value.first.isEmpty());
710         copyToVector(fallbackFonts, it->value.first);
711         run->m_box->parent()->clearDescendantsHaveSameLineHeightAndBaseline();
712     }
713     if ((glyphOverflow.top || glyphOverflow.bottom || glyphOverflow.left || glyphOverflow.right)) {
714         ASSERT(run->m_box->behavesLikeText());
715         GlyphOverflowAndFallbackFontsMap::iterator it = textBoxDataMap.add(toInlineTextBox(run->m_box), make_pair(Vector<const SimpleFontData*>(), GlyphOverflow())).iterator;
716         it->value.second = glyphOverflow;
717         run->m_box->clearKnownToHaveNoOverflow();
718     }
719 }
720
721 static inline void computeExpansionForJustifiedText(BidiRun* firstRun, BidiRun* trailingSpaceRun, Vector<unsigned, 16>& expansionOpportunities, unsigned expansionOpportunityCount, float& totalLogicalWidth, float availableLogicalWidth)
722 {
723     if (!expansionOpportunityCount || availableLogicalWidth <= totalLogicalWidth)
724         return;
725
726     size_t i = 0;
727     for (BidiRun* r = firstRun; r; r = r->next()) {
728 #if ENABLE(CSS_SHAPES)
729         // This method is called once per segment, do not move past the current segment.
730         if (r->m_startsSegment)
731             break;
732 #endif
733         if (!r->m_box || r == trailingSpaceRun)
734             continue;
735         
736         if (r->m_object->isText()) {
737             unsigned opportunitiesInRun = expansionOpportunities[i++];
738             
739             ASSERT(opportunitiesInRun <= expansionOpportunityCount);
740             
741             // Only justify text if whitespace is collapsed.
742             if (r->m_object->style()->collapseWhiteSpace()) {
743                 InlineTextBox* textBox = toInlineTextBox(r->m_box);
744                 int expansion = (availableLogicalWidth - totalLogicalWidth) * opportunitiesInRun / expansionOpportunityCount;
745                 textBox->setExpansion(expansion);
746                 totalLogicalWidth += expansion;
747             }
748             expansionOpportunityCount -= opportunitiesInRun;
749             if (!expansionOpportunityCount)
750                 break;
751         }
752     }
753 }
754
755 void RenderBlock::updateLogicalWidthForAlignment(const ETextAlign& textAlign, BidiRun* trailingSpaceRun, float& logicalLeft, float& totalLogicalWidth, float& availableLogicalWidth, int expansionOpportunityCount)
756 {
757     // Armed with the total width of the line (without justification),
758     // we now examine our text-align property in order to determine where to position the
759     // objects horizontally. The total width of the line can be increased if we end up
760     // justifying text.
761     switch (textAlign) {
762     case LEFT:
763     case WEBKIT_LEFT:
764         updateLogicalWidthForLeftAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
765         break;
766     case RIGHT:
767     case WEBKIT_RIGHT:
768         updateLogicalWidthForRightAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
769         break;
770     case CENTER:
771     case WEBKIT_CENTER:
772         updateLogicalWidthForCenterAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
773         break;
774     case JUSTIFY:
775         adjustInlineDirectionLineBounds(expansionOpportunityCount, logicalLeft, availableLogicalWidth);
776         if (expansionOpportunityCount) {
777             if (trailingSpaceRun) {
778                 totalLogicalWidth -= trailingSpaceRun->m_box->logicalWidth();
779                 trailingSpaceRun->m_box->setLogicalWidth(0);
780             }
781             break;
782         }
783         // Fall through
784     case TASTART:
785         if (style()->isLeftToRightDirection())
786             updateLogicalWidthForLeftAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
787         else
788             updateLogicalWidthForRightAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
789         break;
790     case TAEND:
791         if (style()->isLeftToRightDirection())
792             updateLogicalWidthForRightAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
793         else
794             updateLogicalWidthForLeftAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
795         break;
796     }
797 }
798
799 static IndentTextOrNot requiresIndent(bool isFirstLine, bool isAfterHardLineBreak, const RenderStyle& style)
800 {
801     IndentTextOrNot shouldIndentText = DoNotIndentText;
802     if (isFirstLine)
803         shouldIndentText = IndentText;
804 #if ENABLE(CSS3_TEXT)
805     else if (isAfterHardLineBreak && style.textIndentLine() == TextIndentEachLine)
806         shouldIndentText = IndentText;
807
808     if (style.textIndentType() == TextIndentHanging)
809         shouldIndentText = shouldIndentText == IndentText ? DoNotIndentText : IndentText;
810 #else
811     UNUSED_PARAM(isAfterHardLineBreak);
812     UNUSED_PARAM(style);
813 #endif
814     return shouldIndentText;
815 }
816
817 static void updateLogicalInlinePositions(RenderBlockFlow* block, float& lineLogicalLeft, float& lineLogicalRight, float& availableLogicalWidth, bool firstLine, IndentTextOrNot shouldIndentText, LayoutUnit boxLogicalHeight)
818 {
819     LayoutUnit lineLogicalHeight = block->minLineHeightForReplacedRenderer(firstLine, boxLogicalHeight);
820     lineLogicalLeft = block->pixelSnappedLogicalLeftOffsetForLine(block->logicalHeight(), shouldIndentText == IndentText, lineLogicalHeight);
821     lineLogicalRight = block->pixelSnappedLogicalRightOffsetForLine(block->logicalHeight(), shouldIndentText == IndentText, lineLogicalHeight);
822     availableLogicalWidth = lineLogicalRight - lineLogicalLeft;
823 }
824
825 void RenderBlockFlow::computeInlineDirectionPositionsForLine(RootInlineBox* lineBox, const LineInfo& lineInfo, BidiRun* firstRun, BidiRun* trailingSpaceRun, bool reachedEnd,
826                                                          GlyphOverflowAndFallbackFontsMap& textBoxDataMap, VerticalPositionCache& verticalPositionCache, WordMeasurements& wordMeasurements)
827 {
828     ETextAlign textAlign = textAlignmentForLine(!reachedEnd && !lineBox->endsWithBreak());
829     
830     // 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 
831     // box is only affected if it is the first child of its parent element."
832     // CSS3 "text-indent", "-webkit-each-line" affects the first line of the block container as well as each line after a forced line break,
833     // but does not affect lines after a soft wrap break.
834     bool isFirstLine = lineInfo.isFirstLine() && !(isAnonymousBlock() && parent()->firstChild() != this);
835     bool isAfterHardLineBreak = lineBox->prevRootBox() && lineBox->prevRootBox()->endsWithBreak();
836     IndentTextOrNot shouldIndentText = requiresIndent(isFirstLine, isAfterHardLineBreak, *style());
837     float lineLogicalLeft;
838     float lineLogicalRight;
839     float availableLogicalWidth;
840     updateLogicalInlinePositions(this, lineLogicalLeft, lineLogicalRight, availableLogicalWidth, isFirstLine, shouldIndentText, 0);
841     bool needsWordSpacing;
842 #if ENABLE(CSS_SHAPES)
843     ShapeInsideInfo* shapeInsideInfo = layoutShapeInsideInfo();
844     if (shapeInsideInfo && shapeInsideInfo->hasSegments()) {
845         BidiRun* segmentStart = firstRun;
846         const SegmentList& segments = shapeInsideInfo->segments();
847         float logicalLeft = max<float>(roundToInt(segments[0].logicalLeft), lineLogicalLeft);
848         float logicalRight = min<float>(floorToInt(segments[0].logicalRight), lineLogicalRight);
849         float startLogicalLeft = logicalLeft;
850         float endLogicalRight = logicalLeft;
851         float minLogicalLeft = logicalLeft;
852         float maxLogicalRight = logicalLeft;
853         lineBox->beginPlacingBoxRangesInInlineDirection(logicalLeft);
854         for (size_t i = 0; i < segments.size(); i++) {
855             if (i) {
856                 logicalLeft = max<float>(roundToInt(segments[i].logicalLeft), lineLogicalLeft);
857                 logicalRight = min<float>(floorToInt(segments[i].logicalRight), lineLogicalRight);
858             }
859             availableLogicalWidth = logicalRight - logicalLeft;
860             BidiRun* newSegmentStart = computeInlineDirectionPositionsForSegment(lineBox, lineInfo, textAlign, logicalLeft, availableLogicalWidth, segmentStart, trailingSpaceRun, textBoxDataMap, verticalPositionCache, wordMeasurements);
861             needsWordSpacing = false;
862             endLogicalRight = lineBox->placeBoxRangeInInlineDirection(segmentStart->m_box, newSegmentStart ? newSegmentStart->m_box : 0, logicalLeft, minLogicalLeft, maxLogicalRight, needsWordSpacing, textBoxDataMap);
863             if (!newSegmentStart || !newSegmentStart->next())
864                 break;
865             ASSERT(newSegmentStart->m_startsSegment);
866             // Discard the empty segment start marker bidi runs
867             segmentStart = newSegmentStart->next();
868         }
869         lineBox->endPlacingBoxRangesInInlineDirection(startLogicalLeft, endLogicalRight, minLogicalLeft, maxLogicalRight);
870         return;
871     }
872 #endif
873
874     if (firstRun && firstRun->m_object->isReplaced()) {
875         RenderBox* renderBox = toRenderBox(firstRun->m_object);
876         updateLogicalInlinePositions(this, lineLogicalLeft, lineLogicalRight, availableLogicalWidth, isFirstLine, shouldIndentText, renderBox->logicalHeight());
877     }
878
879     computeInlineDirectionPositionsForSegment(lineBox, lineInfo, textAlign, lineLogicalLeft, availableLogicalWidth, firstRun, trailingSpaceRun, textBoxDataMap, verticalPositionCache, wordMeasurements);
880     // The widths of all runs are now known. We can now place every inline box (and
881     // compute accurate widths for the inline flow boxes).
882     needsWordSpacing = false;
883     lineBox->placeBoxesInInlineDirection(lineLogicalLeft, needsWordSpacing, textBoxDataMap);
884 }
885
886 BidiRun* RenderBlockFlow::computeInlineDirectionPositionsForSegment(RootInlineBox* lineBox, const LineInfo& lineInfo, ETextAlign textAlign, float& logicalLeft, 
887     float& availableLogicalWidth, BidiRun* firstRun, BidiRun* trailingSpaceRun, GlyphOverflowAndFallbackFontsMap& textBoxDataMap, VerticalPositionCache& verticalPositionCache,
888     WordMeasurements& wordMeasurements)
889 {
890     bool needsWordSpacing = false;
891     float totalLogicalWidth = lineBox->getFlowSpacingLogicalWidth();
892     unsigned expansionOpportunityCount = 0;
893     bool isAfterExpansion = true;
894     Vector<unsigned, 16> expansionOpportunities;
895     RenderObject* previousObject = 0;
896
897     BidiRun* r = firstRun;
898     for (; r; r = r->next()) {
899 #if ENABLE(CSS_SHAPES)
900         // Once we have reached the start of the next segment, we have finished
901         // computing the positions for this segment's contents.
902         if (r->m_startsSegment)
903             break;
904 #endif
905         if (!r->m_box || r->m_object->isOutOfFlowPositioned() || r->m_box->isLineBreak())
906             continue; // Positioned objects are only participating to figure out their
907                       // correct static x position.  They have no effect on the width.
908                       // Similarly, line break boxes have no effect on the width.
909         if (r->m_object->isText()) {
910             RenderText* rt = toRenderText(r->m_object);
911             if (textAlign == JUSTIFY && r != trailingSpaceRun) {
912                 if (!isAfterExpansion)
913                     toInlineTextBox(r->m_box)->setCanHaveLeadingExpansion(true);
914                 unsigned opportunitiesInRun;
915                 if (rt->is8Bit())
916                     opportunitiesInRun = Font::expansionOpportunityCount(rt->characters8() + r->m_start, r->m_stop - r->m_start, r->m_box->direction(), isAfterExpansion);
917                 else
918                     opportunitiesInRun = Font::expansionOpportunityCount(rt->characters16() + r->m_start, r->m_stop - r->m_start, r->m_box->direction(), isAfterExpansion);
919                 expansionOpportunities.append(opportunitiesInRun);
920                 expansionOpportunityCount += opportunitiesInRun;
921             }
922
923             if (int length = rt->textLength()) {
924                 if (!r->m_start && needsWordSpacing && isSpaceOrNewline(rt->characterAt(r->m_start)))
925                     totalLogicalWidth += lineStyle(*rt->parent(), lineInfo).font().wordSpacing();
926                 needsWordSpacing = !isSpaceOrNewline(rt->characterAt(r->m_stop - 1)) && r->m_stop == length;
927             }
928
929             setLogicalWidthForTextRun(lineBox, r, rt, totalLogicalWidth, lineInfo, textBoxDataMap, verticalPositionCache, wordMeasurements);
930         } else {
931             isAfterExpansion = false;
932             if (!r->m_object->isRenderInline()) {
933                 RenderBox& renderBox = toRenderBox(*r->m_object);
934                 if (renderBox.isRubyRun())
935                     setMarginsForRubyRun(r, toRenderRubyRun(renderBox), previousObject, lineInfo);
936                 r->m_box->setLogicalWidth(logicalWidthForChild(renderBox));
937                 totalLogicalWidth += marginStartForChild(renderBox) + marginEndForChild(renderBox);
938             }
939         }
940
941         totalLogicalWidth += r->m_box->logicalWidth();
942         previousObject = r->m_object;
943     }
944
945     if (isAfterExpansion && !expansionOpportunities.isEmpty()) {
946         expansionOpportunities.last()--;
947         expansionOpportunityCount--;
948     }
949
950     updateLogicalWidthForAlignment(textAlign, trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth, expansionOpportunityCount);
951
952     computeExpansionForJustifiedText(firstRun, trailingSpaceRun, expansionOpportunities, expansionOpportunityCount, totalLogicalWidth, availableLogicalWidth);
953
954     return r;
955 }
956
957 void RenderBlockFlow::computeBlockDirectionPositionsForLine(RootInlineBox* lineBox, BidiRun* firstRun, GlyphOverflowAndFallbackFontsMap& textBoxDataMap,
958                                                         VerticalPositionCache& verticalPositionCache)
959 {
960     setLogicalHeight(lineBox->alignBoxesInBlockDirection(logicalHeight(), textBoxDataMap, verticalPositionCache));
961
962     // Now make sure we place replaced render objects correctly.
963     for (BidiRun* r = firstRun; r; r = r->next()) {
964         ASSERT(r->m_box);
965         if (!r->m_box)
966             continue; // Skip runs with no line boxes.
967
968         // Align positioned boxes with the top of the line box.  This is
969         // a reasonable approximation of an appropriate y position.
970         if (r->m_object->isOutOfFlowPositioned())
971             r->m_box->setLogicalTop(logicalHeight());
972
973         // Position is used to properly position both replaced elements and
974         // to update the static normal flow x/y of positioned elements.
975         if (r->m_object->isText())
976             toRenderText(r->m_object)->positionLineBox(r->m_box);
977         else if (r->m_object->isBox())
978             toRenderBox(r->m_object)->positionLineBox(r->m_box);
979         else if (r->m_object->isLineBreak())
980             toRenderLineBreak(r->m_object)->replaceInlineBoxWrapper(r->m_box);
981     }
982     // Positioned objects and zero-length text nodes destroy their boxes in
983     // position(), which unnecessarily dirties the line.
984     lineBox->markDirty(false);
985 }
986
987 static inline bool isCollapsibleSpace(UChar character, RenderText* renderer)
988 {
989     if (character == ' ' || character == '\t' || character == softHyphen)
990         return true;
991     if (character == '\n')
992         return !renderer->style()->preserveNewline();
993     if (character == noBreakSpace)
994         return renderer->style()->nbspMode() == SPACE;
995     return false;
996 }
997
998
999 static void setStaticPositions(RenderBlockFlow& block, RenderBox& child)
1000 {
1001     // FIXME: The math here is actually not really right. It's a best-guess approximation that
1002     // will work for the common cases
1003     RenderElement* containerBlock = child.container();
1004     LayoutUnit blockHeight = block.logicalHeight();
1005     if (containerBlock->isRenderInline()) {
1006         // A relative positioned inline encloses us. In this case, we also have to determine our
1007         // position as though we were an inline. Set |staticInlinePosition| and |staticBlockPosition| on the relative positioned
1008         // inline so that we can obtain the value later.
1009         toRenderInline(containerBlock)->layer()->setStaticInlinePosition(block.startAlignedOffsetForLine(blockHeight, false));
1010         toRenderInline(containerBlock)->layer()->setStaticBlockPosition(blockHeight);
1011     }
1012     block.updateStaticInlinePositionForChild(child, blockHeight);
1013     child.layer()->setStaticBlockPosition(blockHeight);
1014 }
1015
1016 template <typename CharacterType>
1017 static inline int findFirstTrailingSpace(RenderText* lastText, const CharacterType* characters, int start, int stop)
1018 {
1019     int firstSpace = stop;
1020     while (firstSpace > start) {
1021         UChar current = characters[firstSpace - 1];
1022         if (!isCollapsibleSpace(current, lastText))
1023             break;
1024         firstSpace--;
1025     }
1026
1027     return firstSpace;
1028 }
1029
1030 inline BidiRun* RenderBlockFlow::handleTrailingSpaces(BidiRunList<BidiRun>& bidiRuns, BidiContext* currentContext)
1031 {
1032     if (!bidiRuns.runCount()
1033         || !bidiRuns.logicallyLastRun()->m_object->style()->breakOnlyAfterWhiteSpace()
1034         || !bidiRuns.logicallyLastRun()->m_object->style()->autoWrap())
1035         return 0;
1036
1037     BidiRun* trailingSpaceRun = bidiRuns.logicallyLastRun();
1038     RenderObject* lastObject = trailingSpaceRun->m_object;
1039     if (!lastObject->isText())
1040         return 0;
1041
1042     RenderText* lastText = toRenderText(lastObject);
1043     int firstSpace;
1044     if (lastText->is8Bit())
1045         firstSpace = findFirstTrailingSpace(lastText, lastText->characters8(), trailingSpaceRun->start(), trailingSpaceRun->stop());
1046     else
1047         firstSpace = findFirstTrailingSpace(lastText, lastText->characters16(), trailingSpaceRun->start(), trailingSpaceRun->stop());
1048
1049     if (firstSpace == trailingSpaceRun->stop())
1050         return 0;
1051
1052     TextDirection direction = style()->direction();
1053     bool shouldReorder = trailingSpaceRun != (direction == LTR ? bidiRuns.lastRun() : bidiRuns.firstRun());
1054     if (firstSpace != trailingSpaceRun->start()) {
1055         BidiContext* baseContext = currentContext;
1056         while (BidiContext* parent = baseContext->parent())
1057             baseContext = parent;
1058
1059         BidiRun* newTrailingRun = new (renderArena()) BidiRun(firstSpace, trailingSpaceRun->m_stop, trailingSpaceRun->m_object, baseContext, U_OTHER_NEUTRAL);
1060         trailingSpaceRun->m_stop = firstSpace;
1061         if (direction == LTR)
1062             bidiRuns.addRun(newTrailingRun);
1063         else
1064             bidiRuns.prependRun(newTrailingRun);
1065         trailingSpaceRun = newTrailingRun;
1066         return trailingSpaceRun;
1067     }
1068     if (!shouldReorder)
1069         return trailingSpaceRun;
1070
1071     if (direction == LTR) {
1072         bidiRuns.moveRunToEnd(trailingSpaceRun);
1073         trailingSpaceRun->m_level = 0;
1074     } else {
1075         bidiRuns.moveRunToBeginning(trailingSpaceRun);
1076         trailingSpaceRun->m_level = 1;
1077     }
1078     return trailingSpaceRun;
1079 }
1080
1081 void RenderBlockFlow::appendFloatingObjectToLastLine(FloatingObject* floatingObject)
1082 {
1083     ASSERT(!floatingObject->originatingLine());
1084     floatingObject->setOriginatingLine(lastRootBox());
1085     lastRootBox()->appendFloat(floatingObject->renderer());
1086 }
1087
1088 // FIXME: This should be a BidiStatus constructor or create method.
1089 static inline BidiStatus statusWithDirection(TextDirection textDirection, bool isOverride)
1090 {
1091     UCharDirection direction = textDirection == LTR ? U_LEFT_TO_RIGHT : U_RIGHT_TO_LEFT;
1092     RefPtr<BidiContext> context = BidiContext::create(textDirection == LTR ? 0 : 1, direction, isOverride, FromStyleOrDOM);
1093
1094     // This copies BidiStatus and may churn the ref on BidiContext. I doubt it matters.
1095     return BidiStatus(direction, direction, direction, context.release());
1096 }
1097
1098 // FIXME: BidiResolver should have this logic.
1099 static inline void constructBidiRunsForSegment(InlineBidiResolver& topResolver, BidiRunList<BidiRun>& bidiRuns, const InlineIterator& endOfRuns, VisualDirectionOverride override, bool previousLineBrokeCleanly)
1100 {
1101     // FIXME: We should pass a BidiRunList into createBidiRunsForLine instead
1102     // of the resolver owning the runs.
1103     ASSERT(&topResolver.runs() == &bidiRuns);
1104     ASSERT(topResolver.position() != endOfRuns);
1105     RenderObject* currentRoot = topResolver.position().root();
1106     topResolver.createBidiRunsForLine(endOfRuns, override, previousLineBrokeCleanly);
1107
1108     while (!topResolver.isolatedRuns().isEmpty()) {
1109         // It does not matter which order we resolve the runs as long as we resolve them all.
1110         BidiRun* isolatedRun = topResolver.isolatedRuns().last();
1111         topResolver.isolatedRuns().removeLast();
1112
1113         RenderObject* startObj = isolatedRun->object();
1114
1115         // Only inlines make sense with unicode-bidi: isolate (blocks are already isolated).
1116         // FIXME: Because enterIsolate is not passed a RenderObject, we have to crawl up the
1117         // tree to see which parent inline is the isolate. We could change enterIsolate
1118         // to take a RenderObject and do this logic there, but that would be a layering
1119         // violation for BidiResolver (which knows nothing about RenderObject).
1120         RenderInline* isolatedInline = toRenderInline(containingIsolate(startObj, currentRoot));
1121         InlineBidiResolver isolatedResolver;
1122         EUnicodeBidi unicodeBidi = isolatedInline->style()->unicodeBidi();
1123         TextDirection direction;
1124         if (unicodeBidi == Plaintext)
1125             determineDirectionality(direction, InlineIterator(isolatedInline, isolatedRun->object(), 0));
1126         else {
1127             ASSERT(unicodeBidi == Isolate || unicodeBidi == IsolateOverride);
1128             direction = isolatedInline->style()->direction();
1129         }
1130         isolatedResolver.setStatus(statusWithDirection(direction, isOverride(unicodeBidi)));
1131
1132         // FIXME: The fact that we have to construct an Iterator here
1133         // currently prevents this code from moving into BidiResolver.
1134         if (!bidiFirstSkippingEmptyInlines(*isolatedInline, &isolatedResolver))
1135             continue;
1136
1137         // The starting position is the beginning of the first run within the isolate that was identified
1138         // during the earlier call to createBidiRunsForLine. This can be but is not necessarily the
1139         // first run within the isolate.
1140         InlineIterator iter = InlineIterator(isolatedInline, startObj, isolatedRun->m_start);
1141         isolatedResolver.setPositionIgnoringNestedIsolates(iter);
1142
1143         // We stop at the next end of line; we may re-enter this isolate in the next call to constructBidiRuns().
1144         // FIXME: What should end and previousLineBrokeCleanly be?
1145         // rniwa says previousLineBrokeCleanly is just a WinIE hack and could always be false here?
1146         isolatedResolver.createBidiRunsForLine(endOfRuns, NoVisualOverride, previousLineBrokeCleanly);
1147         // Note that we do not delete the runs from the resolver.
1148         // We're not guaranteed to get any BidiRuns in the previous step. If we don't, we allow the placeholder
1149         // itself to be turned into an InlineBox. We can't remove it here without potentially losing track of
1150         // the logically last run.
1151         if (isolatedResolver.runs().runCount())
1152             bidiRuns.replaceRunWithRuns(isolatedRun, isolatedResolver.runs());
1153
1154         // If we encountered any nested isolate runs, just move them
1155         // to the top resolver's list for later processing.
1156         if (!isolatedResolver.isolatedRuns().isEmpty()) {
1157             topResolver.isolatedRuns().appendVector(isolatedResolver.isolatedRuns());
1158             isolatedResolver.isolatedRuns().clear();
1159             currentRoot = isolatedInline;
1160         }
1161     }
1162 }
1163
1164 static inline void constructBidiRunsForLine(const RenderBlockFlow* block, InlineBidiResolver& topResolver, BidiRunList<BidiRun>& bidiRuns, const InlineIterator& endOfLine, VisualDirectionOverride override, bool previousLineBrokeCleanly)
1165 {
1166 #if !ENABLE(CSS_SHAPES)
1167     UNUSED_PARAM(block);
1168     constructBidiRunsForSegment(topResolver, bidiRuns, endOfLine, override, previousLineBrokeCleanly);
1169 #else
1170     ShapeInsideInfo* shapeInsideInfo = block->layoutShapeInsideInfo();
1171     if (!shapeInsideInfo || !shapeInsideInfo->hasSegments()) {
1172         constructBidiRunsForSegment(topResolver, bidiRuns, endOfLine, override, previousLineBrokeCleanly);
1173         return;
1174     }
1175
1176     const SegmentRangeList& segmentRanges = shapeInsideInfo->segmentRanges();
1177     ASSERT(segmentRanges.size());
1178
1179     for (size_t i = 0; i < segmentRanges.size(); i++) {
1180         LineSegmentIterator iterator = segmentRanges[i].start;
1181         InlineIterator segmentStart(iterator.root, iterator.object, iterator.offset);
1182         iterator = segmentRanges[i].end;
1183         InlineIterator segmentEnd(iterator.root, iterator.object, iterator.offset);
1184         if (i) {
1185             ASSERT(segmentStart.m_obj);
1186             BidiRun* segmentMarker = createRun(segmentStart.m_pos, segmentStart.m_pos, segmentStart.m_obj, topResolver);
1187             segmentMarker->m_startsSegment = true;
1188             bidiRuns.addRun(segmentMarker);
1189             // Do not collapse midpoints between segments
1190             topResolver.midpointState().betweenMidpoints = false;
1191         }
1192         if (segmentStart == segmentEnd)
1193             continue;
1194         topResolver.setPosition(segmentStart, numberOfIsolateAncestors(segmentStart));
1195         constructBidiRunsForSegment(topResolver, bidiRuns, segmentEnd, override, previousLineBrokeCleanly);
1196     }
1197 #endif
1198 }
1199
1200 // This function constructs line boxes for all of the text runs in the resolver and computes their position.
1201 RootInlineBox* RenderBlockFlow::createLineBoxesFromBidiRuns(BidiRunList<BidiRun>& bidiRuns, const InlineIterator& end, LineInfo& lineInfo, VerticalPositionCache& verticalPositionCache, BidiRun* trailingSpaceRun, WordMeasurements& wordMeasurements)
1202 {
1203     if (!bidiRuns.runCount())
1204         return 0;
1205
1206     // FIXME: Why is this only done when we had runs?
1207     lineInfo.setLastLine(!end.m_obj);
1208
1209     RootInlineBox* lineBox = constructLine(bidiRuns, lineInfo);
1210     if (!lineBox)
1211         return 0;
1212
1213     lineBox->setEndsWithBreak(lineInfo.previousLineBrokeCleanly());
1214     
1215 #if ENABLE(SVG)
1216     bool isSVGRootInlineBox = lineBox->isSVGRootInlineBox();
1217 #else
1218     bool isSVGRootInlineBox = false;
1219 #endif
1220     
1221     GlyphOverflowAndFallbackFontsMap textBoxDataMap;
1222     
1223     // Now we position all of our text runs horizontally.
1224     if (!isSVGRootInlineBox)
1225         computeInlineDirectionPositionsForLine(lineBox, lineInfo, bidiRuns.firstRun(), trailingSpaceRun, end.atEnd(), textBoxDataMap, verticalPositionCache, wordMeasurements);
1226     
1227     // Now position our text runs vertically.
1228     computeBlockDirectionPositionsForLine(lineBox, bidiRuns.firstRun(), textBoxDataMap, verticalPositionCache);
1229     
1230 #if ENABLE(SVG)
1231     // SVG text layout code computes vertical & horizontal positions on its own.
1232     // Note that we still need to execute computeVerticalPositionsForLine() as
1233     // it calls InlineTextBox::positionLineBox(), which tracks whether the box
1234     // contains reversed text or not. If we wouldn't do that editing and thus
1235     // text selection in RTL boxes would not work as expected.
1236     if (isSVGRootInlineBox) {
1237         ASSERT_WITH_SECURITY_IMPLICATION(isSVGText());
1238         static_cast<SVGRootInlineBox*>(lineBox)->computePerCharacterLayoutInformation();
1239     }
1240 #endif
1241     
1242     // Compute our overflow now.
1243     lineBox->computeOverflow(lineBox->lineTop(), lineBox->lineBottom(), textBoxDataMap);
1244     
1245 #if PLATFORM(MAC)
1246     // Highlight acts as an overflow inflation.
1247     if (style()->highlight() != nullAtom)
1248         lineBox->addHighlightOverflow();
1249 #endif
1250     return lineBox;
1251 }
1252
1253 static void deleteLineRange(LineLayoutState& layoutState, RenderArena& arena, RootInlineBox* startLine, RootInlineBox* stopLine = 0)
1254 {
1255     RootInlineBox* boxToDelete = startLine;
1256     while (boxToDelete && boxToDelete != stopLine) {
1257         layoutState.updateRepaintRangeFromBox(boxToDelete);
1258         // Note: deleteLineRange(renderArena(), firstRootBox()) is not identical to deleteLineBoxTree().
1259         // deleteLineBoxTree uses nextLineBox() instead of nextRootBox() when traversing.
1260         RootInlineBox* next = boxToDelete->nextRootBox();
1261         boxToDelete->deleteLine(arena);
1262         boxToDelete = next;
1263     }
1264 }
1265
1266 void RenderBlockFlow::layoutRunsAndFloats(LineLayoutState& layoutState, bool hasInlineChild)
1267 {
1268     // We want to skip ahead to the first dirty line
1269     InlineBidiResolver resolver;
1270     RootInlineBox* startLine = determineStartPosition(layoutState, resolver);
1271
1272     unsigned consecutiveHyphenatedLines = 0;
1273     if (startLine) {
1274         for (RootInlineBox* line = startLine->prevRootBox(); line && line->isHyphenated(); line = line->prevRootBox())
1275             consecutiveHyphenatedLines++;
1276     }
1277
1278     // FIXME: This would make more sense outside of this function, but since
1279     // determineStartPosition can change the fullLayout flag we have to do this here. Failure to call
1280     // determineStartPosition first will break fast/repaint/line-flow-with-floats-9.html.
1281     if (layoutState.isFullLayout() && hasInlineChild && !selfNeedsLayout()) {
1282         setNeedsLayout(MarkOnlyThis); // Mark as needing a full layout to force us to repaint.
1283         if (!view().doingFullRepaint() && hasLayer()) {
1284             // Because we waited until we were already inside layout to discover
1285             // that the block really needed a full layout, we missed our chance to repaint the layer
1286             // before layout started.  Luckily the layer has cached the repaint rect for its original
1287             // position and size, and so we can use that to make a repaint happen now.
1288             repaintUsingContainer(containerForRepaint(), pixelSnappedIntRect(layer()->repaintRect()));
1289         }
1290     }
1291
1292     if (containsFloats())
1293         layoutState.setLastFloat(m_floatingObjects->set().last().get());
1294
1295     // We also find the first clean line and extract these lines.  We will add them back
1296     // if we determine that we're able to synchronize after handling all our dirty lines.
1297     InlineIterator cleanLineStart;
1298     BidiStatus cleanLineBidiStatus;
1299     if (!layoutState.isFullLayout() && startLine)
1300         determineEndPosition(layoutState, startLine, cleanLineStart, cleanLineBidiStatus);
1301
1302     if (startLine) {
1303         if (!layoutState.usesRepaintBounds())
1304             layoutState.setRepaintRange(logicalHeight());
1305         deleteLineRange(layoutState, renderArena(), startLine);
1306     }
1307
1308     if (!layoutState.isFullLayout() && lastRootBox() && lastRootBox()->endsWithBreak()) {
1309         // If the last line before the start line ends with a line break that clear floats,
1310         // adjust the height accordingly.
1311         // A line break can be either the first or the last object on a line, depending on its direction.
1312         if (InlineBox* lastLeafChild = lastRootBox()->lastLeafChild()) {
1313             RenderObject* lastObject = &lastLeafChild->renderer();
1314             if (!lastObject->isBR())
1315                 lastObject = &lastRootBox()->firstLeafChild()->renderer();
1316             if (lastObject->isBR()) {
1317                 EClear clear = lastObject->style()->clear();
1318                 if (clear != CNONE)
1319                     newLine(clear);
1320             }
1321         }
1322     }
1323
1324     layoutRunsAndFloatsInRange(layoutState, resolver, cleanLineStart, cleanLineBidiStatus, consecutiveHyphenatedLines);
1325     linkToEndLineIfNeeded(layoutState);
1326     repaintDirtyFloats(layoutState.floats());
1327 }
1328
1329 RenderTextInfo::RenderTextInfo()
1330     : m_text(0)
1331     , m_font(0)
1332 {
1333 }
1334
1335 RenderTextInfo::~RenderTextInfo()
1336 {
1337 }
1338
1339 // Before restarting the layout loop with a new logicalHeight, remove all floats that were added and reset the resolver.
1340 inline const InlineIterator& RenderBlockFlow::restartLayoutRunsAndFloatsInRange(LayoutUnit oldLogicalHeight, LayoutUnit newLogicalHeight,  FloatingObject* lastFloatFromPreviousLine, InlineBidiResolver& resolver,  const InlineIterator& oldEnd)
1341 {
1342     removeFloatingObjectsBelow(lastFloatFromPreviousLine, oldLogicalHeight);
1343     setLogicalHeight(newLogicalHeight);
1344     resolver.setPositionIgnoringNestedIsolates(oldEnd);
1345     return oldEnd;
1346 }
1347
1348 #if ENABLE(CSS_SHAPES)
1349 static inline void pushShapeContentOverflowBelowTheContentBox(RenderBlockFlow* block, ShapeInsideInfo* shapeInsideInfo, LayoutUnit lineTop, LayoutUnit lineHeight)
1350 {
1351     ASSERT(shapeInsideInfo);
1352
1353     LayoutUnit logicalLineBottom = lineTop + lineHeight;
1354     LayoutUnit shapeLogicalBottom = shapeInsideInfo->shapeLogicalBottom();
1355     LayoutUnit shapeContainingBlockLogicalHeight = shapeInsideInfo->shapeContainingBlockLogicalHeight();
1356
1357     bool isOverflowPositionedAlready = (shapeContainingBlockLogicalHeight - shapeInsideInfo->owner()->borderAndPaddingAfter() + lineHeight) <= lineTop;
1358
1359     // If the last line overlaps with the shape, we don't need the segments anymore
1360     if (lineTop < shapeLogicalBottom && shapeLogicalBottom < logicalLineBottom)
1361         shapeInsideInfo->clearSegments();
1362
1363     if (logicalLineBottom <= shapeLogicalBottom || !shapeContainingBlockLogicalHeight || isOverflowPositionedAlready)
1364         return;
1365
1366     LayoutUnit newLogicalHeight = block->logicalHeight() + (shapeContainingBlockLogicalHeight - (lineTop + shapeInsideInfo->owner()->borderAndPaddingAfter()));
1367     block->setLogicalHeight(newLogicalHeight);
1368 }
1369
1370 void RenderBlockFlow::updateShapeAndSegmentsForCurrentLine(ShapeInsideInfo*& shapeInsideInfo, const LayoutSize& logicalOffsetFromShapeContainer, LineLayoutState& layoutState)
1371 {
1372     if (layoutState.flowThread())
1373         return updateShapeAndSegmentsForCurrentLineInFlowThread(shapeInsideInfo, layoutState);
1374
1375     if (!shapeInsideInfo)
1376         return;
1377
1378     LayoutUnit lineTop = logicalHeight() + logicalOffsetFromShapeContainer.height();
1379     LayoutUnit lineLeft = logicalOffsetFromShapeContainer.width();
1380     LayoutUnit lineHeight = this->lineHeight(layoutState.lineInfo().isFirstLine(), isHorizontalWritingMode() ? HorizontalLine : VerticalLine, PositionOfInteriorLineBoxes);
1381
1382     // FIXME: Bug 95361: It is possible for a line to grow beyond lineHeight, in which case these segments may be incorrect.
1383     shapeInsideInfo->updateSegmentsForLine(LayoutSize(lineLeft, lineTop), lineHeight);
1384
1385     pushShapeContentOverflowBelowTheContentBox(this, shapeInsideInfo, lineTop, lineHeight);
1386 }
1387
1388 void RenderBlockFlow::updateShapeAndSegmentsForCurrentLineInFlowThread(ShapeInsideInfo*& shapeInsideInfo, LineLayoutState& layoutState)
1389 {
1390     ASSERT(layoutState.flowThread());
1391
1392     LayoutUnit lineHeight = this->lineHeight(layoutState.lineInfo().isFirstLine(), isHorizontalWritingMode() ? HorizontalLine : VerticalLine, PositionOfInteriorLineBoxes);
1393
1394     RenderRegion* currentRegion = regionAtBlockOffset(logicalHeight());
1395     if (!currentRegion || !currentRegion->logicalHeight())
1396         return;
1397
1398     shapeInsideInfo = currentRegion->shapeInsideInfo();
1399
1400     LayoutUnit logicalLineTopInFlowThread = logicalHeight() + offsetFromLogicalTopOfFirstPage();
1401     LayoutUnit logicalLineBottomInFlowThread = logicalLineTopInFlowThread + lineHeight;
1402     LayoutUnit logicalRegionTopInFlowThread = currentRegion->logicalTopForFlowThreadContent();
1403     LayoutUnit logicalRegionBottomInFlowThread = logicalRegionTopInFlowThread + currentRegion->logicalHeight() - currentRegion->borderAndPaddingBefore() - currentRegion->borderAndPaddingAfter();
1404
1405     // We only want to deal regions with shapes, so we look up for the next region whether it has a shape
1406     if (!shapeInsideInfo && !currentRegion->isLastRegion()) {
1407         LayoutUnit deltaToNextRegion = logicalHeight() + logicalRegionBottomInFlowThread - logicalLineTopInFlowThread;
1408         RenderRegion* lookupForNextRegion = regionAtBlockOffset(logicalHeight() + deltaToNextRegion);
1409         if (!lookupForNextRegion->shapeInsideInfo())
1410             return;
1411     }
1412
1413     LayoutUnit shapeBottomInFlowThread = LayoutUnit::max();
1414     if (shapeInsideInfo)
1415         shapeBottomInFlowThread = shapeInsideInfo->shapeLogicalBottom() + currentRegion->logicalTopForFlowThreadContent();
1416
1417     // If the line is between two shapes/regions we position the line to the top of the next shape/region
1418     RenderRegion* nextRegion = regionAtBlockOffset(logicalHeight() + lineHeight);
1419     if ((currentRegion != nextRegion && (logicalLineBottomInFlowThread > logicalRegionBottomInFlowThread)) || (!currentRegion->isLastRegion() && shapeBottomInFlowThread < logicalLineBottomInFlowThread)) {
1420         LayoutUnit deltaToNextRegion = logicalRegionBottomInFlowThread - logicalLineTopInFlowThread;
1421         nextRegion = regionAtBlockOffset(logicalHeight() + deltaToNextRegion);
1422
1423         ASSERT(currentRegion != nextRegion);
1424
1425         shapeInsideInfo = nextRegion->shapeInsideInfo();
1426         setLogicalHeight(logicalHeight() + deltaToNextRegion);
1427
1428         currentRegion = nextRegion;
1429
1430         logicalLineTopInFlowThread = logicalHeight() + offsetFromLogicalTopOfFirstPage();
1431         logicalLineBottomInFlowThread = logicalLineTopInFlowThread + lineHeight;
1432         logicalRegionTopInFlowThread = currentRegion->logicalTopForFlowThreadContent();
1433         logicalRegionBottomInFlowThread = logicalRegionTopInFlowThread + currentRegion->logicalHeight() - currentRegion->borderAndPaddingBefore() - currentRegion->borderAndPaddingAfter();
1434     }
1435
1436     if (!shapeInsideInfo)
1437         return;
1438
1439     // We position the first line to the top of the shape in the region or to the previously adjusted position in the shape
1440     if (logicalLineBottomInFlowThread <= (logicalRegionTopInFlowThread + lineHeight) || (logicalLineTopInFlowThread - logicalRegionTopInFlowThread) < (layoutState.adjustedLogicalLineTop() - currentRegion->borderAndPaddingBefore())) {
1441         LayoutUnit shapeTopOffset = layoutState.adjustedLogicalLineTop();
1442         if (!shapeTopOffset)
1443             shapeTopOffset = shapeInsideInfo->shapeLogicalTop();
1444
1445         LayoutUnit shapePositionInFlowThread = currentRegion->logicalTopForFlowThreadContent() + shapeTopOffset;
1446         LayoutUnit shapeTopLineTopDelta = shapePositionInFlowThread - logicalLineTopInFlowThread - currentRegion->borderAndPaddingBefore();
1447
1448         setLogicalHeight(logicalHeight() + shapeTopLineTopDelta);
1449         logicalLineTopInFlowThread += shapeTopLineTopDelta;
1450         layoutState.setAdjustedLogicalLineTop(0);
1451     }
1452
1453     LayoutUnit lineTop = logicalLineTopInFlowThread - currentRegion->logicalTopForFlowThreadContent() + currentRegion->borderAndPaddingBefore();
1454
1455     // FIXME: 118571 - Shape inside on a region does not yet take into account its padding for nested flow blocks
1456     shapeInsideInfo->updateSegmentsForLine(LayoutSize(0, lineTop), lineHeight);
1457
1458     if (currentRegion->isLastRegion())
1459         pushShapeContentOverflowBelowTheContentBox(this, shapeInsideInfo, lineTop, lineHeight);
1460 }
1461
1462 static inline float firstPositiveWidth(const WordMeasurements& wordMeasurements)
1463 {
1464     for (size_t i = 0; i < wordMeasurements.size(); ++i) {
1465         if (wordMeasurements[i].width > 0)
1466             return wordMeasurements[i].width;
1467     }
1468     return 0;
1469 }
1470
1471 static inline LayoutUnit adjustLogicalLineTop(ShapeInsideInfo* shapeInsideInfo, InlineIterator start, InlineIterator end, const WordMeasurements& wordMeasurements)
1472 {
1473     if (!shapeInsideInfo || end != start)
1474         return 0;
1475
1476     float minWidth = firstPositiveWidth(wordMeasurements);
1477     ASSERT(minWidth || wordMeasurements.isEmpty());
1478     if (minWidth > 0 && shapeInsideInfo->adjustLogicalLineTop(minWidth))
1479         return shapeInsideInfo->logicalLineTop();
1480
1481     return shapeInsideInfo->shapeLogicalBottom();
1482 }
1483
1484 bool RenderBlockFlow::adjustLogicalLineTopAndLogicalHeightIfNeeded(ShapeInsideInfo* shapeInsideInfo, LayoutUnit absoluteLogicalTop, LineLayoutState& layoutState, InlineBidiResolver& resolver, FloatingObject* lastFloatFromPreviousLine, InlineIterator& end, WordMeasurements& wordMeasurements)
1485 {
1486     LayoutUnit adjustedLogicalLineTop = adjustLogicalLineTop(shapeInsideInfo, resolver.position(), end, wordMeasurements);
1487
1488     if (shapeInsideInfo && containsFloats()) {
1489         lastFloatFromPreviousLine = m_floatingObjects->set().last().get();
1490         if (!wordMeasurements.size()) {
1491             LayoutUnit floatLogicalTopOffset = shapeInsideInfo->computeFirstFitPositionForFloat(logicalSizeForFloat(lastFloatFromPreviousLine));
1492             if (logicalHeight() < floatLogicalTopOffset)
1493                 adjustedLogicalLineTop = floatLogicalTopOffset;
1494         }
1495     }
1496
1497     if (!adjustedLogicalLineTop)
1498         return false;
1499
1500     LayoutUnit newLogicalHeight = adjustedLogicalLineTop - absoluteLogicalTop;
1501
1502     if (layoutState.flowThread()) {
1503         layoutState.setAdjustedLogicalLineTop(adjustedLogicalLineTop);
1504         newLogicalHeight = logicalHeight();
1505     }
1506
1507     end = restartLayoutRunsAndFloatsInRange(logicalHeight(), newLogicalHeight, lastFloatFromPreviousLine, resolver, end);
1508     return true;
1509 }
1510 #endif
1511
1512 void RenderBlockFlow::layoutRunsAndFloatsInRange(LineLayoutState& layoutState, InlineBidiResolver& resolver, const InlineIterator& cleanLineStart, const BidiStatus& cleanLineBidiStatus, unsigned consecutiveHyphenatedLines)
1513 {
1514     RenderStyle* styleToUse = style();
1515     bool paginated = view().layoutState() && view().layoutState()->isPaginated();
1516     LineMidpointState& lineMidpointState = resolver.midpointState();
1517     InlineIterator end = resolver.position();
1518     bool checkForEndLineMatch = layoutState.endLine();
1519     RenderTextInfo renderTextInfo;
1520     VerticalPositionCache verticalPositionCache;
1521
1522     LineBreaker lineBreaker(*this);
1523
1524 #if ENABLE(CSS_SHAPES)
1525     LayoutSize logicalOffsetFromShapeContainer;
1526     ShapeInsideInfo* shapeInsideInfo = layoutShapeInsideInfo();
1527     if (shapeInsideInfo) {
1528         ASSERT(shapeInsideInfo->owner() == this || allowsShapeInsideInfoSharing());
1529         if (shapeInsideInfo != this->shapeInsideInfo()) {
1530             // FIXME Bug 100284: If subsequent LayoutStates are pushed, we will have to add
1531             // their offsets from the original shape-inside container.
1532             logicalOffsetFromShapeContainer = logicalOffsetFromShapeAncestorContainer(shapeInsideInfo->owner());
1533         }
1534         // Begin layout at the logical top of our shape inside.
1535         if (logicalHeight() + logicalOffsetFromShapeContainer.height() < shapeInsideInfo->shapeLogicalTop()) {
1536             LayoutUnit logicalHeight = shapeInsideInfo->shapeLogicalTop() - logicalOffsetFromShapeContainer.height();
1537             if (layoutState.flowThread())
1538                 logicalHeight -= shapeInsideInfo->owner()->borderAndPaddingBefore();
1539             setLogicalHeight(logicalHeight);
1540         }
1541     }
1542 #endif
1543
1544     while (!end.atEnd()) {
1545         // FIXME: Is this check necessary before the first iteration or can it be moved to the end?
1546         if (checkForEndLineMatch) {
1547             layoutState.setEndLineMatched(matchedEndLine(layoutState, resolver, cleanLineStart, cleanLineBidiStatus));
1548             if (layoutState.endLineMatched()) {
1549                 resolver.setPosition(InlineIterator(resolver.position().root(), 0, 0), 0);
1550                 break;
1551             }
1552         }
1553
1554         lineMidpointState.reset();
1555
1556         layoutState.lineInfo().setEmpty(true);
1557         layoutState.lineInfo().resetRunsFromLeadingWhitespace();
1558
1559         const InlineIterator oldEnd = end;
1560         bool isNewUBAParagraph = layoutState.lineInfo().previousLineBrokeCleanly();
1561         FloatingObject* lastFloatFromPreviousLine = (containsFloats()) ? m_floatingObjects->set().last().get() : 0;
1562
1563 #if ENABLE(CSS_SHAPES)
1564         updateShapeAndSegmentsForCurrentLine(shapeInsideInfo, logicalOffsetFromShapeContainer, layoutState);
1565 #endif
1566         WordMeasurements wordMeasurements;
1567         end = lineBreaker.nextLineBreak(resolver, layoutState.lineInfo(), renderTextInfo, lastFloatFromPreviousLine, consecutiveHyphenatedLines, wordMeasurements);
1568         renderTextInfo.m_lineBreakIterator.resetPriorContext();
1569         if (resolver.position().atEnd()) {
1570             // FIXME: We shouldn't be creating any runs in nextLineBreak to begin with!
1571             // Once BidiRunList is separated from BidiResolver this will not be needed.
1572             resolver.runs().deleteRuns();
1573             resolver.markCurrentRunEmpty(); // FIXME: This can probably be replaced by an ASSERT (or just removed).
1574             layoutState.setCheckForFloatsFromLastLine(true);
1575             resolver.setPosition(InlineIterator(resolver.position().root(), 0, 0), 0);
1576             break;
1577         }
1578
1579 #if ENABLE(CSS_SHAPES)
1580         if (adjustLogicalLineTopAndLogicalHeightIfNeeded(shapeInsideInfo, logicalOffsetFromShapeContainer.height(), layoutState, resolver, lastFloatFromPreviousLine, end, wordMeasurements))
1581             continue;
1582 #endif
1583         ASSERT(end != resolver.position());
1584
1585         // This is a short-cut for empty lines.
1586         if (layoutState.lineInfo().isEmpty()) {
1587             if (lastRootBox())
1588                 lastRootBox()->setLineBreakInfo(end.m_obj, end.m_pos, resolver.status());
1589         } else {
1590             VisualDirectionOverride override = (styleToUse->rtlOrdering() == VisualOrder ? (styleToUse->direction() == LTR ? VisualLeftToRightOverride : VisualRightToLeftOverride) : NoVisualOverride);
1591
1592             if (isNewUBAParagraph && styleToUse->unicodeBidi() == Plaintext && !resolver.context()->parent()) {
1593                 TextDirection direction = styleToUse->direction();
1594                 determineDirectionality(direction, resolver.position());
1595                 resolver.setStatus(BidiStatus(direction, isOverride(styleToUse->unicodeBidi())));
1596             }
1597             // FIXME: This ownership is reversed. We should own the BidiRunList and pass it to createBidiRunsForLine.
1598             BidiRunList<BidiRun>& bidiRuns = resolver.runs();
1599             constructBidiRunsForLine(this, resolver, bidiRuns, end, override, layoutState.lineInfo().previousLineBrokeCleanly());
1600             ASSERT(resolver.position() == end);
1601
1602             BidiRun* trailingSpaceRun = !layoutState.lineInfo().previousLineBrokeCleanly() ? handleTrailingSpaces(bidiRuns, resolver.context()) : 0;
1603
1604             if (bidiRuns.runCount() && lineBreaker.lineWasHyphenated()) {
1605                 bidiRuns.logicallyLastRun()->m_hasHyphen = true;
1606                 consecutiveHyphenatedLines++;
1607             } else
1608                 consecutiveHyphenatedLines = 0;
1609
1610             // Now that the runs have been ordered, we create the line boxes.
1611             // At the same time we figure out where border/padding/margin should be applied for
1612             // inline flow boxes.
1613
1614             LayoutUnit oldLogicalHeight = logicalHeight();
1615             RootInlineBox* lineBox = createLineBoxesFromBidiRuns(bidiRuns, end, layoutState.lineInfo(), verticalPositionCache, trailingSpaceRun, wordMeasurements);
1616
1617             bidiRuns.deleteRuns();
1618             resolver.markCurrentRunEmpty(); // FIXME: This can probably be replaced by an ASSERT (or just removed).
1619
1620             if (lineBox) {
1621                 lineBox->setLineBreakInfo(end.m_obj, end.m_pos, resolver.status());
1622                 if (layoutState.usesRepaintBounds())
1623                     layoutState.updateRepaintRangeFromBox(lineBox);
1624
1625                 if (paginated) {
1626                     LayoutUnit adjustment = 0;
1627                     adjustLinePositionForPagination(lineBox, adjustment, layoutState.flowThread());
1628                     if (adjustment) {
1629                         LayoutUnit oldLineWidth = availableLogicalWidthForLine(oldLogicalHeight, layoutState.lineInfo().isFirstLine());
1630                         lineBox->adjustBlockDirectionPosition(adjustment);
1631                         if (layoutState.usesRepaintBounds())
1632                             layoutState.updateRepaintRangeFromBox(lineBox);
1633
1634                         if (availableLogicalWidthForLine(oldLogicalHeight + adjustment, layoutState.lineInfo().isFirstLine()) != oldLineWidth) {
1635                             // We have to delete this line, remove all floats that got added, and let line layout re-run.
1636                             lineBox->deleteLine(renderArena());
1637                             end = restartLayoutRunsAndFloatsInRange(oldLogicalHeight, oldLogicalHeight + adjustment, lastFloatFromPreviousLine, resolver, oldEnd);
1638                             continue;
1639                         }
1640
1641                         setLogicalHeight(lineBox->lineBottomWithLeading());
1642                     }
1643
1644                     if (layoutState.flowThread())
1645                         updateRegionForLine(lineBox);
1646                 }
1647             }
1648         }
1649
1650         for (size_t i = 0; i < lineBreaker.positionedObjects().size(); ++i)
1651             setStaticPositions(*this, *lineBreaker.positionedObjects()[i]);
1652
1653         if (!layoutState.lineInfo().isEmpty()) {
1654             layoutState.lineInfo().setFirstLine(false);
1655             newLine(lineBreaker.clear());
1656         }
1657
1658         if (m_floatingObjects && lastRootBox()) {
1659             const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1660             auto it = floatingObjectSet.begin();
1661             auto end = floatingObjectSet.end();
1662             if (layoutState.lastFloat()) {
1663                 auto lastFloatIterator = floatingObjectSet.find<FloatingObject&, FloatingObjectHashTranslator>(*layoutState.lastFloat());
1664                 ASSERT(lastFloatIterator != end);
1665                 ++lastFloatIterator;
1666                 it = lastFloatIterator;
1667             }
1668             for (; it != end; ++it) {
1669                 FloatingObject* f = it->get();
1670                 appendFloatingObjectToLastLine(f);
1671                 ASSERT(&f->renderer() == &layoutState.floats()[layoutState.floatIndex()].object);
1672                 // If a float's geometry has changed, give up on syncing with clean lines.
1673                 if (layoutState.floats()[layoutState.floatIndex()].rect != f->frameRect())
1674                     checkForEndLineMatch = false;
1675                 layoutState.setFloatIndex(layoutState.floatIndex() + 1);
1676             }
1677             layoutState.setLastFloat(!floatingObjectSet.isEmpty() ? floatingObjectSet.last().get() : nullptr);
1678         }
1679
1680         lineMidpointState.reset();
1681         resolver.setPosition(end, numberOfIsolateAncestors(end));
1682     }
1683
1684     // In case we already adjusted the line positions during this layout to avoid widows
1685     // then we need to ignore the possibility of having a new widows situation.
1686     // Otherwise, we risk leaving empty containers which is against the block fragmentation principles.
1687     if (paginated && !style()->hasAutoWidows() && !didBreakAtLineToAvoidWidow()) {
1688         // Check the line boxes to make sure we didn't create unacceptable widows.
1689         // However, we'll prioritize orphans - so nothing we do here should create
1690         // a new orphan.
1691
1692         RootInlineBox* lineBox = lastRootBox();
1693
1694         // Count from the end of the block backwards, to see how many hanging
1695         // lines we have.
1696         RootInlineBox* firstLineInBlock = firstRootBox();
1697         int numLinesHanging = 1;
1698         while (lineBox && lineBox != firstLineInBlock && !lineBox->isFirstAfterPageBreak()) {
1699             ++numLinesHanging;
1700             lineBox = lineBox->prevRootBox();
1701         }
1702
1703         // If there were no breaks in the block, we didn't create any widows.
1704         if (!lineBox || !lineBox->isFirstAfterPageBreak() || lineBox == firstLineInBlock)
1705             return;
1706
1707         if (numLinesHanging < style()->widows()) {
1708             // We have detected a widow. Now we need to work out how many
1709             // lines there are on the previous page, and how many we need
1710             // to steal.
1711             int numLinesNeeded = style()->widows() - numLinesHanging;
1712             RootInlineBox* currentFirstLineOfNewPage = lineBox;
1713
1714             // Count the number of lines in the previous page.
1715             lineBox = lineBox->prevRootBox();
1716             int numLinesInPreviousPage = 1;
1717             while (lineBox && lineBox != firstLineInBlock && !lineBox->isFirstAfterPageBreak()) {
1718                 ++numLinesInPreviousPage;
1719                 lineBox = lineBox->prevRootBox();
1720             }
1721
1722             // If there was an explicit value for orphans, respect that. If not, we still
1723             // shouldn't create a situation where we make an orphan bigger than the initial value.
1724             // This means that setting widows implies we also care about orphans, but given
1725             // the specification says the initial orphan value is non-zero, this is ok. The
1726             // author is always free to set orphans explicitly as well.
1727             int orphans = style()->hasAutoOrphans() ? style()->initialOrphans() : style()->orphans();
1728             int numLinesAvailable = numLinesInPreviousPage - orphans;
1729             if (numLinesAvailable <= 0)
1730                 return;
1731
1732             int numLinesToTake = min(numLinesAvailable, numLinesNeeded);
1733             // Wind back from our first widowed line.
1734             lineBox = currentFirstLineOfNewPage;
1735             for (int i = 0; i < numLinesToTake; ++i)
1736                 lineBox = lineBox->prevRootBox();
1737
1738             // We now want to break at this line. Remember for next layout and trigger relayout.
1739             setBreakAtLineToAvoidWidow(lineCount(lineBox));
1740             markLinesDirtyInBlockRange(lastRootBox()->lineBottomWithLeading(), lineBox->lineBottomWithLeading(), lineBox);
1741         }
1742     }
1743
1744     clearDidBreakAtLineToAvoidWidow();
1745 }
1746
1747 void RenderBlockFlow::linkToEndLineIfNeeded(LineLayoutState& layoutState)
1748 {
1749     if (layoutState.endLine()) {
1750         if (layoutState.endLineMatched()) {
1751             bool paginated = view().layoutState() && view().layoutState()->isPaginated();
1752             // Attach all the remaining lines, and then adjust their y-positions as needed.
1753             LayoutUnit delta = logicalHeight() - layoutState.endLineLogicalTop();
1754             for (RootInlineBox* line = layoutState.endLine(); line; line = line->nextRootBox()) {
1755                 line->attachLine();
1756                 if (paginated) {
1757                     delta -= line->paginationStrut();
1758                     adjustLinePositionForPagination(line, delta, layoutState.flowThread());
1759                 }
1760                 if (delta) {
1761                     layoutState.updateRepaintRangeFromBox(line, delta);
1762                     line->adjustBlockDirectionPosition(delta);
1763                 }
1764                 if (layoutState.flowThread())
1765                     updateRegionForLine(line);
1766                 if (Vector<RenderBox*>* cleanLineFloats = line->floatsPtr()) {
1767                     for (auto it = cleanLineFloats->begin(), end = cleanLineFloats->end(); it != end; ++it) {
1768                         RenderBox* floatingBox = *it;
1769                         FloatingObject* floatingObject = insertFloatingObject(*floatingBox);
1770                         ASSERT(!floatingObject->originatingLine());
1771                         floatingObject->setOriginatingLine(line);
1772                         setLogicalHeight(logicalTopForChild(*floatingBox) - marginBeforeForChild(*floatingBox) + delta);
1773                         positionNewFloats();
1774                     }
1775                 }
1776             }
1777             setLogicalHeight(lastRootBox()->lineBottomWithLeading());
1778         } else {
1779             // Delete all the remaining lines.
1780             deleteLineRange(layoutState, renderArena(), layoutState.endLine());
1781         }
1782     }
1783     
1784     if (m_floatingObjects && (layoutState.checkForFloatsFromLastLine() || positionNewFloats()) && lastRootBox()) {
1785         // In case we have a float on the last line, it might not be positioned up to now.
1786         // This has to be done before adding in the bottom border/padding, or the float will
1787         // include the padding incorrectly. -dwh
1788         if (layoutState.checkForFloatsFromLastLine()) {
1789             LayoutUnit bottomVisualOverflow = lastRootBox()->logicalBottomVisualOverflow();
1790             LayoutUnit bottomLayoutOverflow = lastRootBox()->logicalBottomLayoutOverflow();
1791             TrailingFloatsRootInlineBox* trailingFloatsLineBox = new (renderArena()) TrailingFloatsRootInlineBox(*this);
1792             m_lineBoxes.appendLineBox(trailingFloatsLineBox);
1793             trailingFloatsLineBox->setConstructed();
1794             GlyphOverflowAndFallbackFontsMap textBoxDataMap;
1795             VerticalPositionCache verticalPositionCache;
1796             LayoutUnit blockLogicalHeight = logicalHeight();
1797             trailingFloatsLineBox->alignBoxesInBlockDirection(blockLogicalHeight, textBoxDataMap, verticalPositionCache);
1798             trailingFloatsLineBox->setLineTopBottomPositions(blockLogicalHeight, blockLogicalHeight, blockLogicalHeight, blockLogicalHeight);
1799             trailingFloatsLineBox->setPaginatedLineWidth(availableLogicalWidthForContent(blockLogicalHeight));
1800             LayoutRect logicalLayoutOverflow(0, blockLogicalHeight, 1, bottomLayoutOverflow - blockLogicalHeight);
1801             LayoutRect logicalVisualOverflow(0, blockLogicalHeight, 1, bottomVisualOverflow - blockLogicalHeight);
1802             trailingFloatsLineBox->setOverflowFromLogicalRects(logicalLayoutOverflow, logicalVisualOverflow, trailingFloatsLineBox->lineTop(), trailingFloatsLineBox->lineBottom());
1803             if (layoutState.flowThread())
1804                 updateRegionForLine(trailingFloatsLineBox);
1805         }
1806
1807         const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1808         auto it = floatingObjectSet.begin();
1809         auto end = floatingObjectSet.end();
1810         if (layoutState.lastFloat()) {
1811             auto lastFloatIterator = floatingObjectSet.find<FloatingObject&, FloatingObjectHashTranslator>(*layoutState.lastFloat());
1812             ASSERT(lastFloatIterator != end);
1813             ++lastFloatIterator;
1814             it = lastFloatIterator;
1815         }
1816         for (; it != end; ++it)
1817             appendFloatingObjectToLastLine(it->get());
1818         layoutState.setLastFloat(!floatingObjectSet.isEmpty() ? floatingObjectSet.last().get() : nullptr);
1819     }
1820 }
1821
1822 void RenderBlockFlow::repaintDirtyFloats(Vector<FloatWithRect>& floats)
1823 {
1824     size_t floatCount = floats.size();
1825     // Floats that did not have layout did not repaint when we laid them out. They would have
1826     // painted by now if they had moved, but if they stayed at (0, 0), they still need to be
1827     // painted.
1828     for (size_t i = 0; i < floatCount; ++i) {
1829         if (!floats[i].everHadLayout) {
1830             RenderBox& box = floats[i].object;
1831             if (!box.x() && !box.y() && box.checkForRepaintDuringLayout())
1832                 box.repaint();
1833         }
1834     }
1835 }
1836
1837 void RenderBlockFlow::layoutLineBoxes(bool relayoutChildren, LayoutUnit& repaintLogicalTop, LayoutUnit& repaintLogicalBottom)
1838 {
1839     ASSERT(!m_simpleLines);
1840
1841     setLogicalHeight(borderAndPaddingBefore());
1842     
1843     // Lay out our hypothetical grid line as though it occurs at the top of the block.
1844     if (view().layoutState() && view().layoutState()->lineGrid() == this)
1845         layoutLineGridBox();
1846
1847     RenderFlowThread* flowThread = flowThreadContainingBlock();
1848     bool clearLinesForPagination = firstLineBox() && flowThread && !flowThread->hasRegions();
1849
1850     // Figure out if we should clear out our line boxes.
1851     // FIXME: Handle resize eventually!
1852     bool isFullLayout = !firstLineBox() || selfNeedsLayout() || relayoutChildren || clearLinesForPagination;
1853     LineLayoutState layoutState(isFullLayout, repaintLogicalTop, repaintLogicalBottom, flowThread);
1854
1855     if (isFullLayout)
1856         lineBoxes().deleteLineBoxes(renderArena());
1857
1858     // Text truncation kicks in in two cases:
1859     //     1) If your overflow isn't visible and your text-overflow-mode isn't clip.
1860     //     2) If you're an anonymous block with a block parent that satisfies #1.
1861     // FIXME: CSS3 says that descendants that are clipped must also know how to truncate.  This is insanely
1862     // difficult to figure out in general (especially in the middle of doing layout), so we only handle the
1863     // simple case of an anonymous block truncating when it's parent is clipped.
1864     bool hasTextOverflow = (style()->textOverflow() && hasOverflowClip())
1865         || (isAnonymousBlock() && parent() && parent()->isRenderBlock() && parent()->style()->textOverflow() && parent()->hasOverflowClip());
1866
1867     // Walk all the lines and delete our ellipsis line boxes if they exist.
1868     if (hasTextOverflow)
1869          deleteEllipsisLineBoxes();
1870
1871     if (firstChild()) {
1872         // In full layout mode, clear the line boxes of children upfront. Otherwise,
1873         // siblings can run into stale root lineboxes during layout. Then layout
1874         // the replaced elements later. In partial layout mode, line boxes are not
1875         // deleted and only dirtied. In that case, we can layout the replaced
1876         // elements at the same time.
1877         bool hasInlineChild = false;
1878         Vector<RenderBox*> replacedChildren;
1879         for (InlineWalker walker(*this); !walker.atEnd(); walker.advance()) {
1880             RenderObject& o = *walker.current();
1881
1882             if (!hasInlineChild && o.isInline())
1883                 hasInlineChild = true;
1884
1885             if (o.isReplaced() || o.isFloating() || o.isOutOfFlowPositioned()) {
1886                 RenderBox& box = toRenderBox(o);
1887
1888                 if (relayoutChildren || box.hasRelativeDimensions())
1889                     box.setChildNeedsLayout(MarkOnlyThis);
1890
1891                 // If relayoutChildren is set and the child has percentage padding or an embedded content box, we also need to invalidate the childs pref widths.
1892                 if (relayoutChildren && box.needsPreferredWidthsRecalculation())
1893                     box.setPreferredLogicalWidthsDirty(true, MarkOnlyThis);
1894
1895                 if (box.isOutOfFlowPositioned())
1896                     box.containingBlock()->insertPositionedObject(box);
1897                 else if (box.isFloating())
1898                     layoutState.floats().append(FloatWithRect(box));
1899                 else if (isFullLayout || box.needsLayout()) {
1900                     // Replaced element.
1901                     box.dirtyLineBoxes(isFullLayout);
1902                     if (isFullLayout)
1903                         replacedChildren.append(&box);
1904                     else
1905                         box.layoutIfNeeded();
1906                 }
1907             } else if (o.isTextOrLineBreak() || (o.isRenderInline() && !walker.atEndOfInline())) {
1908                 if (o.isRenderInline())
1909                     toRenderInline(o).updateAlwaysCreateLineBoxes(layoutState.isFullLayout());
1910                 if (layoutState.isFullLayout() || o.selfNeedsLayout())
1911                     dirtyLineBoxesForRenderer(o, layoutState.isFullLayout());
1912                 o.clearNeedsLayout();
1913             }
1914         }
1915
1916         for (size_t i = 0; i < replacedChildren.size(); i++)
1917              replacedChildren[i]->layoutIfNeeded();
1918
1919         layoutRunsAndFloats(layoutState, hasInlineChild);
1920     }
1921
1922     // Expand the last line to accommodate Ruby and emphasis marks.
1923     int lastLineAnnotationsAdjustment = 0;
1924     if (lastRootBox()) {
1925         LayoutUnit lowestAllowedPosition = max(lastRootBox()->lineBottom(), logicalHeight() + paddingAfter());
1926         if (!style()->isFlippedLinesWritingMode())
1927             lastLineAnnotationsAdjustment = lastRootBox()->computeUnderAnnotationAdjustment(lowestAllowedPosition);
1928         else
1929             lastLineAnnotationsAdjustment = lastRootBox()->computeOverAnnotationAdjustment(lowestAllowedPosition);
1930     }
1931
1932     // Now add in the bottom border/padding.
1933     setLogicalHeight(logicalHeight() + lastLineAnnotationsAdjustment + borderAndPaddingAfter() + scrollbarLogicalHeight());
1934
1935     if (!firstLineBox() && hasLineIfEmpty())
1936         setLogicalHeight(logicalHeight() + lineHeight(true, isHorizontalWritingMode() ? HorizontalLine : VerticalLine, PositionOfInteriorLineBoxes));
1937
1938     // See if we have any lines that spill out of our block.  If we do, then we will possibly need to
1939     // truncate text.
1940     if (hasTextOverflow)
1941         checkLinesForTextOverflow();
1942 }
1943
1944 void RenderBlockFlow::checkFloatsInCleanLine(RootInlineBox* line, Vector<FloatWithRect>& floats, size_t& floatIndex, bool& encounteredNewFloat, bool& dirtiedByFloat)
1945 {
1946     Vector<RenderBox*>* cleanLineFloats = line->floatsPtr();
1947     if (!cleanLineFloats)
1948         return;
1949
1950     for (auto it = cleanLineFloats->begin(), end = cleanLineFloats->end(); it != end; ++it) {
1951         RenderBox* floatingBox = *it;
1952         floatingBox->layoutIfNeeded();
1953         LayoutSize newSize(floatingBox->width() + floatingBox->marginWidth(), floatingBox->height() + floatingBox->marginHeight());
1954         ASSERT_WITH_SECURITY_IMPLICATION(floatIndex < floats.size());
1955         if (&floats[floatIndex].object != floatingBox) {
1956             encounteredNewFloat = true;
1957             return;
1958         }
1959
1960         if (floats[floatIndex].rect.size() != newSize) {
1961             LayoutUnit floatTop = isHorizontalWritingMode() ? floats[floatIndex].rect.y() : floats[floatIndex].rect.x();
1962             LayoutUnit floatHeight = isHorizontalWritingMode() ? max(floats[floatIndex].rect.height(), newSize.height()) : max(floats[floatIndex].rect.width(), newSize.width());
1963             floatHeight = min(floatHeight, LayoutUnit::max() - floatTop);
1964             line->markDirty();
1965             markLinesDirtyInBlockRange(line->lineBottomWithLeading(), floatTop + floatHeight, line);
1966             floats[floatIndex].rect.setSize(newSize);
1967             dirtiedByFloat = true;
1968         }
1969         floatIndex++;
1970     }
1971 }
1972
1973 RootInlineBox* RenderBlockFlow::determineStartPosition(LineLayoutState& layoutState, InlineBidiResolver& resolver)
1974 {
1975     RootInlineBox* curr = 0;
1976     RootInlineBox* last = 0;
1977
1978     // FIXME: This entire float-checking block needs to be broken into a new function.
1979     bool dirtiedByFloat = false;
1980     if (!layoutState.isFullLayout()) {
1981         // Paginate all of the clean lines.
1982         bool paginated = view().layoutState() && view().layoutState()->isPaginated();
1983         LayoutUnit paginationDelta = 0;
1984         size_t floatIndex = 0;
1985         for (curr = firstRootBox(); curr && !curr->isDirty(); curr = curr->nextRootBox()) {
1986             if (paginated) {
1987                 if (lineWidthForPaginatedLineChanged(curr, 0, layoutState.flowThread())) {
1988                     curr->markDirty();
1989                     break;
1990                 }
1991                 paginationDelta -= curr->paginationStrut();
1992                 adjustLinePositionForPagination(curr, paginationDelta, layoutState.flowThread());
1993                 if (paginationDelta) {
1994                     if (containsFloats() || !layoutState.floats().isEmpty()) {
1995                         // FIXME: Do better eventually.  For now if we ever shift because of pagination and floats are present just go to a full layout.
1996                         layoutState.markForFullLayout();
1997                         break;
1998                     }
1999
2000                     layoutState.updateRepaintRangeFromBox(curr, paginationDelta);
2001                     curr->adjustBlockDirectionPosition(paginationDelta);
2002                 }
2003                 if (layoutState.flowThread())
2004                     updateRegionForLine(curr);
2005             }
2006
2007             // If a new float has been inserted before this line or before its last known float, just do a full layout.
2008             bool encounteredNewFloat = false;
2009             checkFloatsInCleanLine(curr, layoutState.floats(), floatIndex, encounteredNewFloat, dirtiedByFloat);
2010             if (encounteredNewFloat)
2011                 layoutState.markForFullLayout();
2012
2013             if (dirtiedByFloat || layoutState.isFullLayout())
2014                 break;
2015         }
2016         // Check if a new float has been inserted after the last known float.
2017         if (!curr && floatIndex < layoutState.floats().size())
2018             layoutState.markForFullLayout();
2019     }
2020
2021     if (layoutState.isFullLayout()) {
2022         m_lineBoxes.deleteLineBoxTree(renderArena());
2023         curr = 0;
2024
2025         ASSERT(!firstLineBox() && !lastLineBox());
2026     } else {
2027         if (curr) {
2028             // We have a dirty line.
2029             if (RootInlineBox* prevRootBox = curr->prevRootBox()) {
2030                 // We have a previous line.
2031                 if (!dirtiedByFloat && (!prevRootBox->endsWithBreak() || !prevRootBox->lineBreakObj() || (prevRootBox->lineBreakObj()->isText() && prevRootBox->lineBreakPos() >= toRenderText(prevRootBox->lineBreakObj())->textLength())))
2032                     // The previous line didn't break cleanly or broke at a newline
2033                     // that has been deleted, so treat it as dirty too.
2034                     curr = prevRootBox;
2035             }
2036         } else {
2037             // No dirty lines were found.
2038             // If the last line didn't break cleanly, treat it as dirty.
2039             if (lastRootBox() && !lastRootBox()->endsWithBreak())
2040                 curr = lastRootBox();
2041         }
2042
2043         // If we have no dirty lines, then last is just the last root box.
2044         last = curr ? curr->prevRootBox() : lastRootBox();
2045     }
2046
2047     unsigned numCleanFloats = 0;
2048     if (!layoutState.floats().isEmpty()) {
2049         LayoutUnit savedLogicalHeight = logicalHeight();
2050         // Restore floats from clean lines.
2051         RootInlineBox* line = firstRootBox();
2052         while (line != curr) {
2053             if (Vector<RenderBox*>* cleanLineFloats = line->floatsPtr()) {
2054                 for (auto it = cleanLineFloats->begin(), end = cleanLineFloats->end(); it != end; ++it) {
2055                     RenderBox* floatingBox = *it;
2056                     FloatingObject* floatingObject = insertFloatingObject(*floatingBox);
2057                     ASSERT(!floatingObject->originatingLine());
2058                     floatingObject->setOriginatingLine(line);
2059                     setLogicalHeight(logicalTopForChild(*floatingBox) - marginBeforeForChild(*floatingBox));
2060                     positionNewFloats();
2061                     ASSERT(&layoutState.floats()[numCleanFloats].object == floatingBox);
2062                     numCleanFloats++;
2063                 }
2064             }
2065             line = line->nextRootBox();
2066         }
2067         setLogicalHeight(savedLogicalHeight);
2068     }
2069     layoutState.setFloatIndex(numCleanFloats);
2070
2071     layoutState.lineInfo().setFirstLine(!last);
2072     layoutState.lineInfo().setPreviousLineBrokeCleanly(!last || last->endsWithBreak());
2073
2074     if (last) {
2075         setLogicalHeight(last->lineBottomWithLeading());
2076         InlineIterator iter = InlineIterator(this, last->lineBreakObj(), last->lineBreakPos());
2077         resolver.setPosition(iter, numberOfIsolateAncestors(iter));
2078         resolver.setStatus(last->lineBreakBidiStatus());
2079     } else {
2080         TextDirection direction = style()->direction();
2081         if (style()->unicodeBidi() == Plaintext)
2082             determineDirectionality(direction, InlineIterator(this, bidiFirstSkippingEmptyInlines(*this), 0));
2083         resolver.setStatus(BidiStatus(direction, isOverride(style()->unicodeBidi())));
2084         InlineIterator iter = InlineIterator(this, bidiFirstSkippingEmptyInlines(*this, &resolver), 0);
2085         resolver.setPosition(iter, numberOfIsolateAncestors(iter));
2086     }
2087     return curr;
2088 }
2089
2090 void RenderBlockFlow::determineEndPosition(LineLayoutState& layoutState, RootInlineBox* startLine, InlineIterator& cleanLineStart, BidiStatus& cleanLineBidiStatus)
2091 {
2092     ASSERT(!layoutState.endLine());
2093     size_t floatIndex = layoutState.floatIndex();
2094     RootInlineBox* last = 0;
2095     for (RootInlineBox* curr = startLine->nextRootBox(); curr; curr = curr->nextRootBox()) {
2096         if (!curr->isDirty()) {
2097             bool encounteredNewFloat = false;
2098             bool dirtiedByFloat = false;
2099             checkFloatsInCleanLine(curr, layoutState.floats(), floatIndex, encounteredNewFloat, dirtiedByFloat);
2100             if (encounteredNewFloat)
2101                 return;
2102         }
2103         if (curr->isDirty())
2104             last = 0;
2105         else if (!last)
2106             last = curr;
2107     }
2108
2109     if (!last)
2110         return;
2111
2112     // At this point, |last| is the first line in a run of clean lines that ends with the last line
2113     // in the block.
2114
2115     RootInlineBox* prev = last->prevRootBox();
2116     cleanLineStart = InlineIterator(this, prev->lineBreakObj(), prev->lineBreakPos());
2117     cleanLineBidiStatus = prev->lineBreakBidiStatus();
2118     layoutState.setEndLineLogicalTop(prev->lineBottomWithLeading());
2119
2120     for (RootInlineBox* line = last; line; line = line->nextRootBox())
2121         line->extractLine(); // Disconnect all line boxes from their render objects while preserving
2122                              // their connections to one another.
2123
2124     layoutState.setEndLine(last);
2125 }
2126
2127 bool RenderBlockFlow::checkPaginationAndFloatsAtEndLine(LineLayoutState& layoutState)
2128 {
2129     LayoutUnit lineDelta = logicalHeight() - layoutState.endLineLogicalTop();
2130
2131     bool paginated = view().layoutState() && view().layoutState()->isPaginated();
2132     if (paginated && layoutState.flowThread()) {
2133         // Check all lines from here to the end, and see if the hypothetical new position for the lines will result
2134         // in a different available line width.
2135         for (RootInlineBox* lineBox = layoutState.endLine(); lineBox; lineBox = lineBox->nextRootBox()) {
2136             if (paginated) {
2137                 // This isn't the real move we're going to do, so don't update the line box's pagination
2138                 // strut yet.
2139                 LayoutUnit oldPaginationStrut = lineBox->paginationStrut();
2140                 lineDelta -= oldPaginationStrut;
2141                 adjustLinePositionForPagination(lineBox, lineDelta, layoutState.flowThread());
2142                 lineBox->setPaginationStrut(oldPaginationStrut);
2143             }
2144             if (lineWidthForPaginatedLineChanged(lineBox, lineDelta, layoutState.flowThread()))
2145                 return false;
2146         }
2147     }
2148     
2149     if (!lineDelta || !m_floatingObjects)
2150         return true;
2151     
2152     // See if any floats end in the range along which we want to shift the lines vertically.
2153     LayoutUnit logicalTop = min(logicalHeight(), layoutState.endLineLogicalTop());
2154
2155     RootInlineBox* lastLine = layoutState.endLine();
2156     while (RootInlineBox* nextLine = lastLine->nextRootBox())
2157         lastLine = nextLine;
2158
2159     LayoutUnit logicalBottom = lastLine->lineBottomWithLeading() + absoluteValue(lineDelta);
2160
2161     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2162     auto end = floatingObjectSet.end();
2163     for (auto it = floatingObjectSet.begin(); it != end; ++it) {
2164         FloatingObject* floatingObject = it->get();
2165         if (logicalBottomForFloat(floatingObject) >= logicalTop && logicalBottomForFloat(floatingObject) < logicalBottom)
2166             return false;
2167     }
2168
2169     return true;
2170 }
2171
2172 bool RenderBlockFlow::matchedEndLine(LineLayoutState& layoutState, const InlineBidiResolver& resolver, const InlineIterator& endLineStart, const BidiStatus& endLineStatus)
2173 {
2174     if (resolver.position() == endLineStart) {
2175         if (resolver.status() != endLineStatus)
2176             return false;
2177         return checkPaginationAndFloatsAtEndLine(layoutState);
2178     }
2179
2180     // The first clean line doesn't match, but we can check a handful of following lines to try
2181     // to match back up.
2182     static int numLines = 8; // The # of lines we're willing to match against.
2183     RootInlineBox* originalEndLine = layoutState.endLine();
2184     RootInlineBox* line = originalEndLine;
2185     for (int i = 0; i < numLines && line; i++, line = line->nextRootBox()) {
2186         if (line->lineBreakObj() == resolver.position().m_obj && line->lineBreakPos() == resolver.position().m_pos) {
2187             // We have a match.
2188             if (line->lineBreakBidiStatus() != resolver.status())
2189                 return false; // ...but the bidi state doesn't match.
2190             
2191             bool matched = false;
2192             RootInlineBox* result = line->nextRootBox();
2193             layoutState.setEndLine(result);
2194             if (result) {
2195                 layoutState.setEndLineLogicalTop(line->lineBottomWithLeading());
2196                 matched = checkPaginationAndFloatsAtEndLine(layoutState);
2197             }
2198
2199             // Now delete the lines that we failed to sync.
2200             deleteLineRange(layoutState, renderArena(), originalEndLine, result);
2201             return matched;
2202         }
2203     }
2204
2205     return false;
2206 }
2207
2208 static inline bool skipNonBreakingSpace(const InlineIterator& it, const LineInfo& lineInfo)
2209 {
2210     if (it.m_obj->style()->nbspMode() != SPACE || it.current() != noBreakSpace)
2211         return false;
2212
2213     // FIXME: This is bad.  It makes nbsp inconsistent with space and won't work correctly
2214     // with m_minWidth/m_maxWidth.
2215     // Do not skip a non-breaking space if it is the first character
2216     // on a line after a clean line break (or on the first line, since previousLineBrokeCleanly starts off
2217     // |true|).
2218     if (lineInfo.isEmpty() && lineInfo.previousLineBrokeCleanly())
2219         return false;
2220
2221     return true;
2222 }
2223
2224 enum WhitespacePosition { LeadingWhitespace, TrailingWhitespace };
2225 static inline bool shouldCollapseWhiteSpace(const RenderStyle* style, const LineInfo& lineInfo, WhitespacePosition whitespacePosition)
2226 {
2227     // CSS2 16.6.1
2228     // If a space (U+0020) at the beginning of a line has 'white-space' set to 'normal', 'nowrap', or 'pre-line', it is removed.
2229     // If a space (U+0020) at the end of a line has 'white-space' set to 'normal', 'nowrap', or 'pre-line', it is also removed.
2230     // If spaces (U+0020) or tabs (U+0009) at the end of a line have 'white-space' set to 'pre-wrap', UAs may visually collapse them.
2231     return style->collapseWhiteSpace()
2232         || (whitespacePosition == TrailingWhitespace && style->whiteSpace() == PRE_WRAP && (!lineInfo.isEmpty() || !lineInfo.previousLineBrokeCleanly()));
2233 }
2234
2235 static bool requiresLineBoxForContent(const RenderInline& flow, const LineInfo& lineInfo)
2236 {
2237     RenderElement* parent = flow.parent();
2238     if (flow.document().inNoQuirksMode()) {
2239         const RenderStyle& flowStyle = lineStyle(flow, lineInfo);
2240         const RenderStyle& parentStyle = lineStyle(*parent, lineInfo);
2241         if (flowStyle.lineHeight() != parentStyle.lineHeight()
2242             || flowStyle.verticalAlign() != parentStyle.verticalAlign()
2243             || !parentStyle.font().fontMetrics().hasIdenticalAscentDescentAndLineGap(flowStyle.font().fontMetrics()))
2244         return true;
2245     }
2246     return false;
2247 }
2248
2249 static bool hasInlineDirectionBordersPaddingOrMargin(const RenderInline& flow)
2250 {
2251     // Where an empty inline is split across anonymous blocks we should only give lineboxes to the 'sides' of the
2252     // inline that have borders, padding or margin.
2253     bool shouldApplyStartBorderPaddingOrMargin = !flow.parent()->isAnonymousBlock() || !flow.isInlineElementContinuation();
2254     if (shouldApplyStartBorderPaddingOrMargin && (flow.borderStart() || flow.marginStart() || flow.paddingStart()))
2255         return true;
2256
2257     bool shouldApplyEndBorderPaddingOrMargin = !flow.parent()->isAnonymousBlock() || flow.isInlineElementContinuation() || !flow.inlineElementContinuation();
2258     return shouldApplyEndBorderPaddingOrMargin && (flow.borderEnd() || flow.marginEnd() || flow.paddingEnd());
2259 }
2260
2261 static bool alwaysRequiresLineBox(const RenderInline& flow)
2262 {
2263     // FIXME: Right now, we only allow line boxes for inlines that are truly empty.
2264     // We need to fix this, though, because at the very least, inlines containing only
2265     // ignorable whitespace should should also have line boxes.
2266     return isEmptyInline(flow) && hasInlineDirectionBordersPaddingOrMargin(flow);
2267 }
2268
2269 static bool requiresLineBox(const InlineIterator& it, const LineInfo& lineInfo = LineInfo(), WhitespacePosition whitespacePosition = LeadingWhitespace)
2270 {
2271     if (it.m_obj->isFloatingOrOutOfFlowPositioned())
2272         return false;
2273
2274     if (it.m_obj->isBR())
2275         return true;
2276
2277     bool rendererIsEmptyInline = false;
2278     if (it.m_obj->isRenderInline()) {
2279         const RenderInline& inlineRenderer = toRenderInline(*it.m_obj);
2280         if (!alwaysRequiresLineBox(inlineRenderer) && !requiresLineBoxForContent(inlineRenderer, lineInfo))
2281             return false;
2282         rendererIsEmptyInline = isEmptyInline(inlineRenderer);
2283     }
2284
2285     if (!shouldCollapseWhiteSpace(it.m_obj->style(), lineInfo, whitespacePosition))
2286         return true;
2287
2288     UChar current = it.current();
2289     bool notJustWhitespace = current != ' ' && current != '\t' && current != softHyphen && (current != '\n' || it.m_obj->preservesNewline()) && !skipNonBreakingSpace(it, lineInfo);
2290     return notJustWhitespace || rendererIsEmptyInline;
2291 }
2292
2293 bool RenderBlock::generatesLineBoxesForInlineChild(RenderObject* inlineObj)
2294 {
2295     ASSERT(inlineObj->parent() == this);
2296
2297     InlineIterator it(this, inlineObj, 0);
2298     // FIXME: We should pass correct value for WhitespacePosition.
2299     while (!it.atEnd() && !requiresLineBox(it))
2300         it.increment();
2301
2302     return !it.atEnd();
2303 }
2304
2305 // FIXME: The entire concept of the skipTrailingWhitespace function is flawed, since we really need to be building
2306 // line boxes even for containers that may ultimately collapse away. Otherwise we'll never get positioned
2307 // elements quite right. In other words, we need to build this function's work into the normal line
2308 // object iteration process.
2309 // NB. this function will insert any floating elements that would otherwise
2310 // be skipped but it will not position them.
2311 void LineBreaker::skipTrailingWhitespace(InlineIterator& iterator, const LineInfo& lineInfo)
2312 {
2313     while (!iterator.atEnd() && !requiresLineBox(iterator, lineInfo, TrailingWhitespace)) {
2314         RenderObject& object = *iterator.m_obj;
2315         if (object.isOutOfFlowPositioned())
2316             setStaticPositions(m_block, toRenderBox(object));
2317         else if (object.isFloating())
2318             m_block.insertFloatingObject(toRenderBox(object));
2319         iterator.increment();
2320     }
2321 }
2322
2323 void LineBreaker::skipLeadingWhitespace(InlineBidiResolver& resolver, LineInfo& lineInfo, FloatingObject* lastFloatFromPreviousLine, LineWidth& width)
2324 {
2325     while (!resolver.position().atEnd() && !requiresLineBox(resolver.position(), lineInfo, LeadingWhitespace)) {
2326         RenderObject& object = *resolver.position().m_obj;
2327         if (object.isOutOfFlowPositioned()) {
2328             setStaticPositions(m_block, toRenderBox(object));
2329             if (object.style()->isOriginalDisplayInlineType()) {
2330                 resolver.runs().addRun(createRun(0, 1, &object, resolver));
2331                 lineInfo.incrementRunsFromLeadingWhitespace();
2332             }
2333         } else if (object.isFloating()) {
2334             // The top margin edge of a self-collapsing block that clears a float intrudes up into it by the height of the margin,
2335             // so in order to place this first child float at the top content edge of the self-collapsing block add the margin back in before placement.
2336             LayoutUnit marginOffset = (!object.previousSibling() && m_block.isSelfCollapsingBlock() && m_block.style()->clear() && m_block.getClearDelta(m_block, LayoutUnit())) ? m_block.collapsedMarginBeforeForChild(m_block) : LayoutUnit();
2337             LayoutUnit oldLogicalHeight = m_block.logicalHeight();
2338             m_block.setLogicalHeight(oldLogicalHeight + marginOffset);
2339             m_block.positionNewFloatOnLine(m_block.insertFloatingObject(toRenderBox(object)), lastFloatFromPreviousLine, lineInfo, width);
2340             m_block.setLogicalHeight(oldLogicalHeight);
2341         } else if (object.isText() && object.style()->hasTextCombine() && object.isCombineText() && !toRenderCombineText(object).isCombined()) {
2342             toRenderCombineText(object).combineText();
2343             if (toRenderCombineText(object).isCombined())
2344                 continue;
2345         }
2346         resolver.increment();
2347     }
2348     resolver.commitExplicitEmbedding();
2349 }
2350
2351 // This is currently just used for list markers and inline flows that have line boxes. Neither should
2352 // have an effect on whitespace at the start of the line.
2353 static bool shouldSkipWhitespaceAfterStartObject(RenderBlockFlow& block, RenderObject* o, LineMidpointState& lineMidpointState)
2354 {
2355     RenderObject* next = bidiNextSkippingEmptyInlines(block, o);
2356     while (next && next->isFloatingOrOutOfFlowPositioned())
2357         next = bidiNextSkippingEmptyInlines(block, next);
2358
2359     if (next && next->isText() && toRenderText(next)->textLength() > 0) {
2360         RenderText* nextText = toRenderText(next);
2361         UChar nextChar = nextText->characterAt(0);
2362         if (nextText->style()->isCollapsibleWhiteSpace(nextChar)) {
2363             startIgnoringSpaces(lineMidpointState, InlineIterator(0, o, 0));
2364             return true;
2365         }
2366     }
2367
2368     return false;
2369 }
2370
2371 static ALWAYS_INLINE float textWidth(RenderText* text, unsigned from, unsigned len, const Font& font, float xPos, bool isFixedPitch, bool collapseWhiteSpace, HashSet<const SimpleFontData*>& fallbackFonts, TextLayout* layout = 0)
2372 {
2373     const RenderStyle& style = *text->style();
2374
2375     GlyphOverflow glyphOverflow;
2376     if (isFixedPitch || (!from && len == text->textLength()) || style.hasTextCombine())
2377         return text->width(from, len, font, xPos, &fallbackFonts, &glyphOverflow);
2378
2379     if (layout)
2380         return Font::width(*layout, from, len, &fallbackFonts);
2381
2382     TextRun run = RenderBlock::constructTextRun(text, font, text, from, len, style);
2383     run.setCharactersLength(text->textLength() - from);
2384     ASSERT(run.charactersLength() >= run.length());
2385
2386     run.setCharacterScanForCodePath(!text->canUseSimpleFontCodePath());
2387     run.setTabSize(!collapseWhiteSpace, text->style()->tabSize());
2388     run.setXPos(xPos);
2389     return font.width(run, &fallbackFonts, &glyphOverflow);
2390 }
2391
2392 static void tryHyphenating(RenderText* text, const Font& font, const AtomicString& localeIdentifier, unsigned consecutiveHyphenatedLines, int consecutiveHyphenatedLinesLimit, int minimumPrefixLimit, int minimumSuffixLimit, unsigned lastSpace, unsigned pos, float xPos, int availableWidth, bool isFixedPitch, bool collapseWhiteSpace, int lastSpaceWordSpacing, InlineIterator& lineBreak, int nextBreakable, bool& hyphenated)
2393 {
2394     // Map 'hyphenate-limit-{before,after}: auto;' to 2.
2395     unsigned minimumPrefixLength;
2396     unsigned minimumSuffixLength;
2397
2398     if (minimumPrefixLimit < 0)
2399         minimumPrefixLength = 2;
2400     else
2401         minimumPrefixLength = static_cast<unsigned>(minimumPrefixLimit);
2402
2403     if (minimumSuffixLimit < 0)
2404         minimumSuffixLength = 2;
2405     else
2406         minimumSuffixLength = static_cast<unsigned>(minimumSuffixLimit);
2407
2408     if (pos - lastSpace <= minimumSuffixLength)
2409         return;
2410
2411     if (consecutiveHyphenatedLinesLimit >= 0 && consecutiveHyphenatedLines >= static_cast<unsigned>(consecutiveHyphenatedLinesLimit))
2412         return;
2413
2414     int hyphenWidth = measureHyphenWidth(text, font);
2415
2416     float maxPrefixWidth = availableWidth - xPos - hyphenWidth - lastSpaceWordSpacing;
2417     // If the maximum width available for the prefix before the hyphen is small, then it is very unlikely
2418     // that an hyphenation opportunity exists, so do not bother to look for it.
2419     if (maxPrefixWidth <= font.pixelSize() * 5 / 4)
2420         return;
2421
2422     const RenderStyle& style = *text->style();
2423     TextRun run = RenderBlock::constructTextRun(text, font, text, lastSpace, pos - lastSpace, style);
2424     run.setCharactersLength(text->textLength() - lastSpace);
2425     ASSERT(run.charactersLength() >= run.length());
2426
2427     run.setTabSize(!collapseWhiteSpace, style.tabSize());
2428     run.setXPos(xPos + lastSpaceWordSpacing);
2429
2430     unsigned prefixLength = font.offsetForPosition(run, maxPrefixWidth, false);
2431     if (prefixLength < minimumPrefixLength)
2432         return;
2433
2434     prefixLength = lastHyphenLocation(text->characters() + lastSpace, pos - lastSpace, min(prefixLength, pos - lastSpace - minimumSuffixLength) + 1, localeIdentifier);
2435     if (!prefixLength || prefixLength < minimumPrefixLength)
2436         return;
2437
2438     // When lastSapce is a space, which it always is except sometimes at the beginning of a line or after collapsed
2439     // space, it should not count towards hyphenate-limit-before.
2440     if (prefixLength == minimumPrefixLength) {
2441         UChar characterAtLastSpace = text->characterAt(lastSpace);
2442         if (characterAtLastSpace == ' ' || characterAtLastSpace == '\n' || characterAtLastSpace == '\t' || characterAtLastSpace == noBreakSpace)
2443             return;
2444     }
2445
2446     ASSERT(pos - lastSpace - prefixLength >= minimumSuffixLength);
2447
2448 #if !ASSERT_DISABLED
2449     HashSet<const SimpleFontData*> fallbackFonts;
2450     float prefixWidth = hyphenWidth + textWidth(text, lastSpace, prefixLength, font, xPos, isFixedPitch, collapseWhiteSpace, fallbackFonts) + lastSpaceWordSpacing;
2451     ASSERT(xPos + prefixWidth <= availableWidth);
2452 #else
2453     UNUSED_PARAM(isFixedPitch);
2454 #endif
2455
2456     lineBreak.moveTo(text, lastSpace + prefixLength, nextBreakable);
2457     hyphenated = true;
2458 }
2459
2460 class TrailingObjects {
2461 public:
2462     TrailingObjects();
2463     void setTrailingWhitespace(RenderText*);
2464     void clear();
2465     void appendBoxIfNeeded(RenderBoxModelObject*);
2466
2467     enum CollapseFirstSpaceOrNot { DoNotCollapseFirstSpace, CollapseFirstSpace };
2468
2469     void updateMidpointsForTrailingBoxes(LineMidpointState&, const InlineIterator& lBreak, CollapseFirstSpaceOrNot);
2470
2471 private:
2472     RenderText* m_whitespace;
2473     Vector<RenderBoxModelObject*, 4> m_boxes;
2474 };
2475
2476 TrailingObjects::TrailingObjects()
2477     : m_whitespace(0)
2478 {
2479 }
2480
2481 inline void TrailingObjects::setTrailingWhitespace(RenderText* whitespace)
2482 {
2483     ASSERT(whitespace);
2484     m_whitespace = whitespace;
2485 }
2486
2487 inline void TrailingObjects::clear()
2488 {
2489     m_whitespace = 0;
2490     m_boxes.shrink(0); // Use shrink(0) instead of clear() to retain our capacity.
2491 }
2492
2493 inline void TrailingObjects::appendBoxIfNeeded(RenderBoxModelObject* box)
2494 {
2495     if (m_whitespace)
2496         m_boxes.append(box);
2497 }
2498
2499 void TrailingObjects::updateMidpointsForTrailingBoxes(LineMidpointState& lineMidpointState, const InlineIterator& lBreak, CollapseFirstSpaceOrNot collapseFirstSpace)
2500 {
2501     if (!m_whitespace)
2502         return;
2503
2504     // This object is either going to be part of the last midpoint, or it is going to be the actual endpoint.
2505     // In both cases we just decrease our pos by 1 level to exclude the space, allowing it to - in effect - collapse into the newline.
2506     if (lineMidpointState.numMidpoints % 2) {
2507         // Find the trailing space object's midpoint.
2508         int trailingSpaceMidpoint = lineMidpointState.numMidpoints - 1;
2509         for ( ; trailingSpaceMidpoint > 0 && lineMidpointState.midpoints[trailingSpaceMidpoint].m_obj != m_whitespace; --trailingSpaceMidpoint) { }
2510         ASSERT(trailingSpaceMidpoint >= 0);
2511         if (collapseFirstSpace == CollapseFirstSpace)
2512             lineMidpointState.midpoints[trailingSpaceMidpoint].m_pos--;
2513
2514         // Now make sure every single trailingPositionedBox following the trailingSpaceMidpoint properly stops and starts
2515         // ignoring spaces.
2516         size_t currentMidpoint = trailingSpaceMidpoint + 1;
2517         for (size_t i = 0; i < m_boxes.size(); ++i) {
2518             if (currentMidpoint >= lineMidpointState.numMidpoints) {
2519                 // We don't have a midpoint for this box yet.
2520                 ensureLineBoxInsideIgnoredSpaces(lineMidpointState, m_boxes[i]);
2521             } else {
2522                 ASSERT(lineMidpointState.midpoints[currentMidpoint].m_obj == m_boxes[i]);
2523                 ASSERT(lineMidpointState.midpoints[currentMidpoint + 1].m_obj == m_boxes[i]);
2524             }
2525             currentMidpoint += 2;
2526         }
2527     } else if (!lBreak.m_obj) {
2528         ASSERT(m_whitespace->isText());
2529         ASSERT(collapseFirstSpace == CollapseFirstSpace);
2530         // Add a new end midpoint that stops right at the very end.
2531         unsigned length = m_whitespace->textLength();
2532         unsigned pos = length >= 2 ? length - 2 : UINT_MAX;
2533         InlineIterator endMid(0, m_whitespace, pos);
2534         startIgnoringSpaces(lineMidpointState, endMid);
2535         for (size_t i = 0; i < m_boxes.size(); ++i) {
2536             ensureLineBoxInsideIgnoredSpaces(lineMidpointState, m_boxes[i]);
2537         }
2538     }
2539 }
2540
2541 void LineBreaker::reset()
2542 {
2543     m_positionedObjects.clear();
2544     m_hyphenated = false;
2545     m_clear = CNONE;
2546 }
2547
2548 InlineIterator LineBreaker::nextLineBreak(InlineBidiResolver& resolver, LineInfo& lineInfo, RenderTextInfo& renderTextInfo, FloatingObject* lastFloatFromPreviousLine, unsigned consecutiveHyphenatedLines, WordMeasurements& wordMeasurements)
2549 {
2550 #if !ENABLE(CSS_SHAPES)
2551     return nextSegmentBreak(resolver, lineInfo, renderTextInfo, lastFloatFromPreviousLine, consecutiveHyphenatedLines, wordMeasurements);
2552 #else
2553     ShapeInsideInfo* shapeInsideInfo = m_block.layoutShapeInsideInfo();
2554
2555     if (!shapeInsideInfo || !shapeInsideInfo->lineOverlapsShapeBounds())
2556         return nextSegmentBreak(resolver, lineInfo, renderTextInfo, lastFloatFromPreviousLine, consecutiveHyphenatedLines, wordMeasurements);
2557
2558     InlineIterator end = resolver.position();
2559     InlineIterator oldEnd = end;
2560
2561     if (!shapeInsideInfo->hasSegments()) {
2562         end = nextSegmentBreak(resolver, lineInfo, renderTextInfo, lastFloatFromPreviousLine, consecutiveHyphenatedLines, wordMeasurements);
2563         resolver.setPositionIgnoringNestedIsolates(oldEnd);
2564         return oldEnd;
2565     }
2566
2567     const SegmentList& segments = shapeInsideInfo->segments();
2568     SegmentRangeList& segmentRanges = shapeInsideInfo->segmentRanges();
2569
2570     for (unsigned i = 0; i < segments.size() && !end.atEnd(); i++) {
2571         InlineIterator segmentStart = resolver.position();
2572         end = nextSegmentBreak(resolver, lineInfo, renderTextInfo, lastFloatFromPreviousLine, consecutiveHyphenatedLines, wordMeasurements);
2573
2574         ASSERT(segmentRanges.size() == i);
2575         if (resolver.position().atEnd()) {
2576             segmentRanges.append(LineSegmentRange(segmentStart, end));
2577             break;
2578         }
2579         if (resolver.position() == end) {
2580             // Nothing fit this segment
2581             end = segmentStart;
2582             segmentRanges.append(LineSegmentRange(segmentStart, segmentStart));
2583             resolver.setPositionIgnoringNestedIsolates(segmentStart);
2584         } else {
2585             // Note that resolver.position is already skipping some of the white space at the beginning of the line,
2586             // so that's why segmentStart might be different than resolver.position().
2587             LineSegmentRange range(resolver.position(), end);
2588             segmentRanges.append(range);
2589             resolver.setPosition(end, numberOfIsolateAncestors(end));
2590
2591             if (lineInfo.previousLineBrokeCleanly()) {
2592                 // If we hit a new line break, just stop adding anything to this line.
2593                 break;
2594             }
2595         }
2596     }
2597     resolver.setPositionIgnoringNestedIsolates(oldEnd);
2598     return end;
2599 #endif
2600 }
2601
2602 static inline bool iteratorIsBeyondEndOfRenderCombineText(const InlineIterator& iter, RenderCombineText& renderer)
2603 {
2604     return iter.m_obj == &renderer && iter.m_pos >= renderer.textLength();
2605 }
2606
2607 #if ENABLE(CSS_SHAPES)
2608 static void updateSegmentsForShapes(RenderBlockFlow& block, const FloatingObject* lastFloatFromPreviousLine, const WordMeasurements& wordMeasurements, LineWidth& width, bool isFirstLine)
2609 {
2610     ASSERT(lastFloatFromPreviousLine);
2611
2612     ShapeInsideInfo* shapeInsideInfo = block.layoutShapeInsideInfo();
2613     if (!lastFloatFromPreviousLine->isPlaced() || !shapeInsideInfo)
2614         return;
2615
2616     bool isHorizontalWritingMode = block.isHorizontalWritingMode();
2617     LayoutUnit logicalOffsetFromShapeContainer = block.logicalOffsetFromShapeAncestorContainer(shapeInsideInfo->owner()).height();
2618
2619     LayoutUnit lineLogicalTop = block.logicalHeight() + logicalOffsetFromShapeContainer;
2620     LayoutUnit lineLogicalHeight = block.lineHeight(isFirstLine, isHorizontalWritingMode ? HorizontalLine : VerticalLine, PositionOfInteriorLineBoxes);
2621     LayoutUnit lineLogicalBottom = lineLogicalTop + lineLogicalHeight;
2622
2623     LayoutUnit floatLogicalTop = block.logicalTopForFloat(lastFloatFromPreviousLine);
2624     LayoutUnit floatLogicalBottom = block.logicalBottomForFloat(lastFloatFromPreviousLine);
2625
2626     bool lineOverlapsWithFloat = (floatLogicalTop < lineLogicalBottom) && (lineLogicalTop < floatLogicalBottom);
2627     if (!lineOverlapsWithFloat)
2628         return;
2629
2630     float minSegmentWidth = firstPositiveWidth(wordMeasurements);
2631
2632     LayoutUnit floatLogicalWidth = block.logicalWidthForFloat(lastFloatFromPreviousLine);
2633     LayoutUnit availableLogicalWidth = block.logicalWidth() - block.logicalRightForFloat(lastFloatFromPreviousLine);
2634     if (availableLogicalWidth < minSegmentWidth)
2635         block.setLogicalHeight(floatLogicalBottom);
2636
2637     if (block.logicalHeight() < floatLogicalTop) {
2638         shapeInsideInfo->adjustLogicalLineTop(minSegmentWidth + floatLogicalWidth);
2639         block.setLogicalHeight(shapeInsideInfo->logicalLineTop() - logicalOffsetFromShapeContainer);
2640     }
2641
2642     lineLogicalTop = block.logicalHeight() + logicalOffsetFromShapeContainer;
2643
2644     shapeInsideInfo->updateSegmentsForLine(lineLogicalTop, lineLogicalHeight);
2645     width.updateCurrentShapeSegment();
2646     width.updateAvailableWidth();
2647 }
2648 #endif
2649
2650 class BreakingContext {
2651 public:
2652     BreakingContext(LineBreaker& lineBreaker, InlineBidiResolver& resolver, LineInfo& inLineInfo, LineWidth& lineWidth, RenderTextInfo& inRenderTextInfo, FloatingObject* inLastFloatFromPreviousLine, bool appliedStartWidth, RenderBlockFlow& block)
2653         : m_lineBreaker(lineBreaker)
2654         , m_resolver(resolver)
2655         , m_current(resolver.position())
2656         , m_lineBreak(resolver.position())
2657         , m_block(block)
2658         , m_lastObject(m_current.m_obj)
2659         , m_nextObject(0)
2660         , m_currentStyle(0)
2661         , m_blockStyle(*(block.style()))
2662         , m_lineInfo(inLineInfo)
2663         , m_renderTextInfo(inRenderTextInfo)
2664         , m_lastFloatFromPreviousLine(inLastFloatFromPreviousLine)
2665         , m_width(lineWidth)
2666         , m_currWS(NORMAL)
2667         , m_lastWS(NORMAL)
2668         , m_preservesNewline(false)
2669         , m_atStart(true)
2670         , m_ignoringSpaces(false)
2671         , m_currentCharacterIsSpace(false)
2672         , m_currentCharacterIsWS(false)
2673         , m_appliedStartWidth(appliedStartWidth)
2674         , m_includeEndWidth(true)
2675         , m_autoWrap(false)
2676         , m_autoWrapWasEverTrueOnLine(false)
2677         , m_floatsFitOnLine(true)
2678         , m_collapseWhiteSpace(false)
2679         , m_startingNewParagraph(m_lineInfo.previousLineBrokeCleanly())
2680         , m_allowImagesToBreak(!block.document().inQuirksMode() || !block.isTableCell() || !m_blockStyle.logicalWidth().isIntrinsicOrAuto())
2681         , m_atEnd(false)
2682         , m_hadUncommittedWidthBeforeCurrent(false)
2683         , m_lineMidpointState(resolver.midpointState())
2684     {
2685         m_lineInfo.setPreviousLineBrokeCleanly(false);
2686     }
2687
2688     RenderObject* currentObject() { return m_current.m_obj; }
2689     InlineIterator lineBreak() { return m_lineBreak; }
2690     InlineIterator& lineBreakRef() {return m_lineBreak; }
2691     LineWidth& lineWidth() { return m_width; }
2692     bool atEnd() { return m_atEnd; }
2693
2694     void initializeForCurrentObject();
2695
2696     void increment();
2697
2698     void handleBR(EClear&);
2699     void handleOutOfFlowPositioned(Vector<RenderBox*>& positionedObjects);
2700     void handleFloat();
2701     void handleEmptyInline();
2702     void handleReplaced();
2703     bool handleText(WordMeasurements&, bool& hyphenated, unsigned& consecutiveHyphenatedLines);
2704     bool canBreakAtThisPosition();
2705     void commitAndUpdateLineBreakIfNeeded();
2706     InlineIterator handleEndOfLine();
2707
2708     void clearLineBreakIfFitsOnLine(bool ignoringTrailingSpace = false)
2709     {
2710         if (m_width.fitsOnLine(ignoringTrailingSpace) || m_lastWS == NOWRAP)
2711             m_lineBreak.clear();
2712     }
2713
2714     void commitLineBreakAtCurrentWidth(RenderObject* object, unsigned offset = 0, int nextBreak = -1)
2715     {
2716         m_width.commit();
2717         m_lineBreak.moveTo(object, offset, nextBreak);
2718     }
2719
2720 private:
2721     LineBreaker& m_lineBreaker;
2722     InlineBidiResolver& m_resolver;
2723
2724     InlineIterator m_current;
2725     InlineIterator m_lineBreak;
2726     InlineIterator m_startOfIgnoredSpaces;
2727
2728     RenderBlockFlow& m_block;
2729     RenderObject* m_lastObject;
2730     RenderObject* m_nextObject;
2731
2732     RenderStyle* m_currentStyle;
2733
2734     // Firefox and Opera will allow a table cell to grow to fit an image inside it under
2735     // very specific circumstances (in order to match common WinIE renderings).
2736     // Not supporting the quirk has caused us to mis-render some real sites. (See Bugzilla 10517.)
2737     RenderStyle& m_blockStyle;
2738
2739     LineInfo& m_lineInfo;
2740
2741     RenderTextInfo& m_renderTextInfo;
2742
2743     FloatingObject* m_lastFloatFromPreviousLine;
2744
2745     LineWidth m_width;
2746
2747     EWhiteSpace m_currWS;
2748     EWhiteSpace m_lastWS;
2749
2750     bool m_preservesNewline;
2751     bool m_atStart;
2752
2753     // This variable is used only if whitespace isn't set to PRE, and it tells us whether
2754     // or not we are currently ignoring whitespace.
2755     bool m_ignoringSpaces;
2756
2757     // This variable tracks whether the very last character we saw was a space.  We use
2758     // this to detect when we encounter a second space so we know we have to terminate
2759     // a run.
2760     bool m_currentCharacterIsSpace;
2761     bool m_currentCharacterIsWS;
2762     bool m_appliedStartWidth;
2763     bool m_includeEndWidth;
2764     bool m_autoWrap;
2765     bool m_autoWrapWasEverTrueOnLine;
2766     bool m_floatsFitOnLine;
2767     bool m_collapseWhiteSpace;
2768     bool m_startingNewParagraph;
2769     bool m_allowImagesToBreak;
2770     bool m_atEnd;
2771     bool m_hadUncommittedWidthBeforeCurrent;
2772
2773     LineMidpointState& m_lineMidpointState;
2774
2775     TrailingObjects m_trailingObjects;
2776 };
2777
2778 inline void BreakingContext::initializeForCurrentObject()
2779 {
2780     m_hadUncommittedWidthBeforeCurrent = !!m_width.uncommittedWidth();
2781
2782     m_currentStyle = m_current.m_obj->style();
2783
2784     ASSERT(m_currentStyle);
2785
2786     m_nextObject = bidiNextSkippingEmptyInlines(m_block, m_current.m_obj);
2787     if (m_nextObject && m_nextObject->parent() && !m_nextObject->parent()->isDescendantOf(m_current.m_obj->parent()))
2788         m_includeEndWidth = true;
2789
2790     m_currWS = m_current.m_obj->isReplaced() ? m_current.m_obj->parent()->style()->whiteSpace() : m_currentStyle->whiteSpace();
2791     m_lastWS = m_lastObject->isReplaced() ? m_lastObject->parent()->style()->whiteSpace() : m_lastObject->style()->whiteSpace();
2792
2793     m_autoWrap = RenderStyle::autoWrap(m_currWS);
2794     m_autoWrapWasEverTrueOnLine = m_autoWrapWasEverTrueOnLine || m_autoWrap;
2795
2796 #if ENABLE(SVG)
2797     m_preservesNewline = m_current.m_obj->isSVGInlineText() ? false : RenderStyle::preserveNewline(m_currWS);
2798 #else
2799     m_preservesNewline = RenderStyle::preserveNewline(m_currWS);
2800 #endif
2801
2802     m_collapseWhiteSpace = RenderStyle::collapseWhiteSpace(m_currWS);
2803 }
2804
2805 inline void BreakingContext::increment()
2806 {
2807     // Clear out our character space bool, since inline <pre>s don't collapse whitespace
2808     // with adjacent inline normal/nowrap spans.
2809     if (!m_collapseWhiteSpace)
2810         m_currentCharacterIsSpace = false;
2811
2812     m_current.moveToStartOf(m_nextObject);
2813     m_atStart = false;
2814 }
2815
2816 inline void BreakingContext::handleBR(EClear& clear)
2817 {
2818     if (m_width.fitsOnLine()) {
2819         RenderObject* br = m_current.m_obj;
2820         m_lineBreak.moveToStartOf(br);
2821         m_lineBreak.increment();
2822
2823         // A <br> always breaks a line, so don't let the line be collapsed
2824         // away. Also, the space at the end of a line with a <br> does not
2825         // get collapsed away. It only does this if the previous line broke
2826         // cleanly. Otherwise the <br> has no effect on whether the line is
2827         // empty or not.
2828         if (m_startingNewParagraph)
2829             m_lineInfo.setEmpty(false, &m_block, &m_width);
2830         m_trailingObjects.clear();
2831         m_lineInfo.setPreviousLineBrokeCleanly(true);
2832
2833         // A <br> with clearance always needs a linebox in case the lines below it get dirtied later and
2834         // need to check for floats to clear - so if we're ignoring spaces, stop ignoring them and add a
2835         // run for this object.
2836         if (m_ignoringSpaces && m_currentStyle->clear() != CNONE)
2837             ensureLineBoxInsideIgnoredSpaces(m_lineMidpointState, br);
2838         // If we were preceded by collapsing space and are in a right-aligned container we need to ensure the space gets
2839         // collapsed away so that it doesn't push the text out from the container's right-hand edge.
2840         // FIXME: Do this regardless of the container's alignment - will require rebaselining a lot of test results.
2841         else if (m_ignoringSpaces && (m_blockStyle.textAlign() == RIGHT || m_blockStyle.textAlign() == WEBKIT_RIGHT))
2842             stopIgnoringSpaces(m_lineMidpointState, InlineIterator(0, m_current.m_obj, m_current.m_pos));
2843
2844         if (!m_lineInfo.isEmpty())
2845             clear = m_currentStyle->clear();
2846     }
2847     m_atEnd = true;
2848 }
2849
2850 inline void BreakingContext::handleOutOfFlowPositioned(Vector<RenderBox*>& positionedObjects)
2851 {
2852     // If our original display wasn't an inline type, then we can
2853     // go ahead and determine our static inline position now.
2854     RenderBox* box = toRenderBox(m_current.m_obj);
2855     bool isInlineType = box->style()->isOriginalDisplayInlineType();
2856     if (!isInlineType)
2857         m_block.setStaticInlinePositionForChild(*box, m_block.logicalHeight(), m_block.startOffsetForContent(m_block.logicalHeight()));
2858     else {
2859         // If our original display was an INLINE type, then we can go ahead
2860         // and determine our static y position now.
2861         box->layer()->setStaticBlockPosition(m_block.logicalHeight());
2862     }
2863
2864     // If we're ignoring spaces, we have to stop and include this object and
2865     // then start ignoring spaces again.
2866     if (isInlineType || box->container()->isRenderInline()) {
2867         if (m_ignoringSpaces)
2868             ensureLineBoxInsideIgnoredSpaces(m_lineMidpointState, box);
2869         m_trailingObjects.appendBoxIfNeeded(box);
2870     } else
2871         positionedObjects.append(box);
2872
2873     m_width.addUncommittedWidth(inlineLogicalWidth(box));
2874     // Reset prior line break context characters.
2875     m_renderTextInfo.m_lineBreakIterator.resetPriorContext();
2876 }
2877
2878 inline void BreakingContext::handleFloat()
2879 {
2880     RenderBox& floatBox = toRenderBox(*m_current.m_obj);
2881     FloatingObject* floatingObject = m_block.insertFloatingObject(floatBox);
2882     // check if it fits in the current line.
2883     // If it does, position it now, otherwise, position
2884     // it after moving to next line (in newLine() func)
2885     // FIXME: Bug 110372: Properly position multiple stacked floats with non-rectangular shape outside.
2886     if (m_floatsFitOnLine && m_width.fitsOnLineExcludingTrailingWhitespace(m_block.logicalWidthForFloat(floatingObject))) {
2887         m_block.positionNewFloatOnLine(floatingObject, m_lastFloatFromPreviousLine, m_lineInfo, m_width);
2888         if (m_lineBreak.m_obj == m_current.m_obj) {
2889             ASSERT(!m_lineBreak.m_pos);
2890             m_lineBreak.increment();
2891         }
2892     } else
2893         m_floatsFitOnLine = false;
2894     // Update prior line break context characters, using U+FFFD (OBJECT REPLACEMENT CHARACTER) for floating element.
2895     m_renderTextInfo.m_lineBreakIterator.updatePriorContext(replacementCharacter);
2896 }
2897
2898 inline void BreakingContext::handleEmptyInline()
2899 {
2900     RenderInline& flowBox = toRenderInline(*m_current.m_obj);
2901
2902     // This should only end up being called on empty inlines
2903     ASSERT(isEmptyInline(flowBox));
2904
2905     // Now that some inline flows have line boxes, if we are already ignoring spaces, we need
2906     // to make sure that we stop to include this object and then start ignoring spaces again.
2907     // If this object is at the start of the line, we need to behave like list markers and
2908     // start ignoring spaces.
2909     bool requiresLineBox = alwaysRequiresLineBox(flowBox);
2910     if (requiresLineBox || requiresLineBoxForContent(flowBox, m_lineInfo)) {
2911         // An empty inline that only has line-height, vertical-align or font-metrics will only get a
2912         // line box to affect the height of the line if the rest of the line is not empty.
2913         if (requiresLineBox)
2914             m_lineInfo.setEmpty(false, &m_block, &m_width);
2915         if (m_ignoringSpaces) {
2916             m_trailingObjects.clear();
2917             ensureLineBoxInsideIgnoredSpaces(m_lineMidpointState, m_current.m_obj);
2918         } else if (m_blockStyle.collapseWhiteSpace() && m_resolver.position().m_obj == m_current.m_obj
2919             && shouldSkipWhitespaceAfterStartObject(m_block, m_current.m_obj, m_lineMidpointState)) {
2920             // Like with list markers, we start ignoring spaces to make sure that any
2921             // additional spaces we see will be discarded.
2922             m_currentCharacterIsSpace = true;
2923             m_currentCharacterIsWS = true;
2924             m_ignoringSpaces = true;
2925         } else
2926             m_trailingObjects.appendBoxIfNeeded(&flowBox);
2927     }
2928
2929     m_width.addUncommittedWidth(inlineLogicalWidth(m_current.m_obj) + borderPaddingMarginStart(flowBox) + borderPaddingMarginEnd(flowBox));
2930 }
2931
2932 inline void BreakingContext::handleReplaced()
2933 {
2934     RenderBox& replacedBox = toRenderBox(*m_current.m_obj);
2935
2936     if (m_atStart)
2937         m_width.updateAvailableWidth(replacedBox.logicalHeight());
2938
2939     // Break on replaced elements if either has normal white-space.
2940     if ((m_autoWrap || RenderStyle::autoWrap(m_lastWS)) && (!m_current.m_obj->isImage() || m_allowImagesToBreak)) {
2941         m_width.commit();
2942         m_lineBreak.moveToStartOf(m_current.m_obj);
2943     }
2944
2945     if (m_ignoringSpaces)
2946         stopIgnoringSpaces(m_lineMidpointState, InlineIterator(0, m_current.m_obj, 0));
2947
2948     m_lineInfo.setEmpty(false, &m_block, &m_width);
2949     m_ignoringSpaces = false;
2950     m_currentCharacterIsSpace = false;
2951     m_currentCharacterIsWS = false;
2952     m_trailingObjects.clear();
2953
2954     // Optimize for a common case. If we can't find whitespace after the list
2955     // item, then this is all moot.
2956     LayoutUnit replacedLogicalWidth = m_block.logicalWidthForChild(replacedBox) + m_block.marginStartForChild(replacedBox) + m_block.marginEndForChild(replacedBox) + inlineLogicalWidth(m_current.m_obj);
2957     if (m_current.m_obj->isListMarker()) {
2958         if (m_blockStyle.collapseWhiteSpace() && shouldSkipWhitespaceAfterStartObject(m_block, m_current.m_obj, m_lineMidpointState)) {
2959             // Like with inline flows, we start ignoring spaces to make sure that any
2960             // additional spaces we see will be discarded.
2961             m_currentCharacterIsSpace = true;
2962             m_currentCharacterIsWS = false;
2963             m_ignoringSpaces = true;
2964         }
2965         if (toRenderListMarker(*m_current.m_obj).isInside())
2966             m_width.addUncommittedWidth(replacedLogicalWidth);
2967     } else
2968         m_width.addUncommittedWidth(replacedLogicalWidth);
2969     if (m_current.m_obj->isRubyRun())
2970         m_width.applyOverhang(toRenderRubyRun(m_current.m_obj), m_lastObject, m_nextObject);
2971     // Update prior line break context characters, using U+FFFD (OBJECT REPLACEMENT CHARACTER) for replaced element.
2972     m_renderTextInfo.m_lineBreakIterator.updatePriorContext(replacementCharacter);
2973 }
2974
2975
2976 static inline void nextCharacter(UChar& currentCharacter, UChar& lastCharacter, UChar& secondToLastCharacter)
2977 {
2978     secondToLastCharacter = lastCharacter;
2979     lastCharacter = currentCharacter;
2980 }
2981
2982 inline bool BreakingContext::handleText(WordMeasurements& wordMeasurements, bool& hyphenated,  unsigned& consecutiveHyphenatedLines)
2983 {
2984     if (!m_current.m_pos)
2985         m_appliedStartWidth = false;
2986
2987     RenderText* renderText = toRenderText(m_current.m_obj);
2988
2989 #if ENABLE(SVG)
2990     bool isSVGText = renderText->isSVGInlineText();
2991 #endif
2992
2993     // If we have left a no-wrap inline and entered an autowrap inline while ignoring spaces
2994     // then we need to mark the start of the autowrap inline as a potential linebreak now.
2995     if (m_autoWrap && !RenderStyle::autoWrap(m_lastWS) && m_ignoringSpaces)
2996         commitLineBreakAtCurrentWidth(m_current.m_obj);
2997
2998     if (renderText->style()->hasTextCombine() && m_current.m_obj->isCombineText() && !toRenderCombineText(*m_current.m_obj).isCombined()) {
2999         RenderCombineText& combineRenderer = toRenderCombineText(*m_current.m_obj);
3000         combineRenderer.combineText();
3001         // The length of the renderer's text may have changed. Increment stale iterator positions
3002         if (iteratorIsBeyondEndOfRenderCombineText(m_lineBreak, combineRenderer)) {
3003             ASSERT(iteratorIsBeyondEndOfRenderCombineText(m_resolver.position(), combineRenderer));
3004             m_lineBreak.increment();
3005             m_resolver.increment();
3006         }
3007     }
3008
3009     const RenderStyle& style = lineStyle(*renderText->parent(), m_lineInfo);
3010     const Font& font = style.font();
3011     bool isFixedPitch = font.isFixedPitch();
3012     bool canHyphenate = style.hyphens() == HyphensAuto && WebCore::canHyphenate(style.locale());
3013
3014     unsigned lastSpace = m_current.m_pos;
3015     float wordSpacing = m_currentStyle->wordSpacing();
3016     float lastSpaceWordSpacing = 0;
3017     float wordSpacingForWordMeasurement = 0;
3018
3019     float wrapW = m_width.uncommittedWidth() + inlineLogicalWidth(m_current.m_obj, !m_appliedStartWidth, true);
3020     float charWidth = 0;
3021     bool breakNBSP = m_autoWrap && m_currentStyle->nbspMode() == SPACE;
3022     // Auto-wrapping text should wrap in the middle of a word only if it could not wrap before the word,
3023     // which is only possible if the word is the first thing on the line, that is, if |w| is zero.
3024     bool breakWords = m_currentStyle->breakWords() && ((m_autoWrap && !m_width.committedWidth()) || m_currWS == PRE);
3025     bool midWordBreak = false;
3026     bool breakAll = m_currentStyle->wordBreak() == BreakAllWordBreak && m_autoWrap;
3027     float hyphenWidth = 0;
3028 #if ENABLE(SVG)
3029     if (isSVGText) {
3030         breakWords = false;
3031         breakAll = false;
3032     }
3033 #endif
3034
3035     if (m_renderTextInfo.m_text != renderText) {
3036         updateCounterIfNeeded(*renderText);
3037         m_renderTextInfo.m_text = renderText;
3038         m_renderTextInfo.m_font = &font;
3039         m_renderTextInfo.m_layout = font.createLayout(renderText, m_width.currentWidth(), m_collapseWhiteSpace);
3040         m_renderTextInfo.m_lineBreakIterator.resetStringAndReleaseIterator(renderText->text(), style.locale());
3041     } else if (m_renderTextInfo.m_layout && m_renderTextInfo.m_font != &font) {
3042         m_renderTextInfo.m_font = &font;
3043         m_renderTextInfo.m_layout = font.createLayout(renderText, m_width.currentWidth(), m_collapseWhiteSpace);
3044     }
3045
3046     TextLayout* textLayout = m_renderTextInfo.m_layout.get();
3047
3048     // Non-zero only when kerning is enabled and TextLayout isn't used, in which case we measure
3049     // words with their trailing space, then subtract its width.
3050     HashSet<const SimpleFontData*> fallbackFonts;
3051     float wordTrailingSpaceWidth = (font.typesettingFeatures() & Kerning) && !textLayout ? font.width(RenderBlock::constructTextRun(renderText, font, &space, 1, style), &fallbackFonts) + wordSpacing : 0;
3052
3053     UChar lastCharacter = m_renderTextInfo.m_lineBreakIterator.lastCharacter();
3054     UChar secondToLastCharacter = m_renderTextInfo.m_lineBreakIterator.secondToLastCharacter();
3055     for (; m_current.m_pos < renderText->textLength(); m_current.fastIncrementInTextNode()) {
3056         bool previousCharacterIsSpace = m_currentCharacterIsSpace;
3057         bool previousCharacterIsWS = m_currentCharacterIsWS;
3058         UChar c = m_current.current();
3059         m_currentCharacterIsSpace = c == ' ' || c == '\t' || (!m_preservesNewline && (c == '\n'));
3060
3061         if (!m_collapseWhiteSpace || !m_currentCharacterIsSpace)
3062             m_lineInfo.setEmpty(false, &m_block, &m_width);
3063
3064         if (c == softHyphen && m_autoWrap && !hyphenWidth && style.hyphens() != HyphensNone) {
3065             hyphenWidth = measureHyphenWidth(renderText, font, &fallbackFonts);
3066             m_width.addUncommittedWidth(hyphenWidth);
3067         }
3068
3069         bool applyWordSpacing = false;
3070
3071         m_currentCharacterIsWS = m_currentCharacterIsSpace || (breakNBSP && c == noBreakSpace);
3072
3073         if ((breakAll || breakWords) && !midWordBreak) {
3074             wrapW += charWidth;
3075             bool midWordBreakIsBeforeSurrogatePair = U16_IS_LEAD(c) && m_current.m_pos + 1 < renderText->textLength() && U16_IS_TRAIL((*renderText)[m_current.m_pos + 1]);
3076             charWidth = textWidth(renderText, m_current.m_pos, midWordBreakIsBeforeSurrogatePair ? 2 : 1, font, m_width.committedWidth() + wrapW, isFixedPitch, m_collapseWhiteSpace, fallbackFonts, textLayout);
3077             midWordBreak = m_width.committedWidth() + wrapW + charWidth > m_width.availableWidth();
3078         }
3079
3080         bool betweenWords = c == '\n' || (m_currWS != PRE && !m_atStart && isBreakable(m_renderTextInfo.m_lineBreakIterator, m_current.m_pos, m_current.m_nextBreakablePosition, breakNBSP)
3081             && (style.hyphens() != HyphensNone || (m_current.previousInSameNode() != softHyphen)));
3082
3083         if (betweenWords || midWordBreak) {
3084             bool stoppedIgnoringSpaces = false;
3085             if (m_ignoringSpaces) {
3086                 lastSpaceWordSpacing = 0;
3087                 if (!m_currentCharacterIsSpace) {
3088                     // Stop ignoring spaces and begin at this
3089                     // new point.
3090                     m_ignoringSpaces = false;
3091                     wordSpacingForWordMeasurement = 0;
3092                     lastSpace = m_current.m_pos; // e.g., "Foo    goo", don't add in any of the ignored spaces.
3093                     stopIgnoringSpaces(m_lineMidpointState, InlineIterator(0, m_current.m_obj, m_current.m_pos));
3094                     stoppedIgnoringSpaces = true;
3095                 } else {
3096                     // Just keep ignoring these spaces.
3097                     nextCharacter(c, lastCharacter, secondToLastCharacter);
3098                     continue;
3099                 }
3100             }
3101
3102             wordMeasurements.grow(wordMeasurements.size() + 1);
3103             WordMeasurement& wordMeasurement = wordMeasurements.last();
3104
3105             wordMeasurement.renderer = renderText;
3106             wordMeasurement.endOffset = m_current.m_pos;
3107             wordMeasurement.startOffset = lastSpace;
3108
3109             float additionalTempWidth;
3110             if (wordTrailingSpaceWidth && c == ' ')
3111                 additionalTempWidth = textWidth(renderText, lastSpace, m_current.m_pos + 1 - lastSpace, font, m_width.currentWidth(), isFixedPitch, m_collapseWhiteSpace, wordMeasurement.fallbackFonts, textLayout) - wordTrailingSpaceWidth;
3112             else
3113                 additionalTempWidth = textWidth(renderText, lastSpace, m_current.m_pos - lastSpace, font, m_width.currentWidth(), isFixedPitch, m_collapseWhiteSpace, wordMeasurement.fallbackFonts, textLayout);
3114
3115             if (wordMeasurement.fallbackFonts.isEmpty() && !fallbackFonts.isEmpty())
3116                 wordMeasurement.fallbackFonts.swap(fallbackFonts);
3117             fallbackFonts.clear();
3118
3119             wordMeasurement.width = additionalTempWidth + wordSpacingForWordMeasurement;
3120             additionalTempWidth += lastSpaceWordSpacing;
3121             m_width.addUncommittedWidth(additionalTempWidth);
3122
3123             if (m_collapseWhiteSpace && previousCharacterIsSpace && m_currentCharacterIsSpace && additionalTempWidth)
3124                 m_width.setTrailingWhitespaceWidth(additionalTempWidth);
3125
3126             if (!m_appliedStartWidth) {
3127                 m_width.addUncommittedWidth(inlineLogicalWidth(m_current.m_obj, true, false));
3128                 m_appliedStartWidth = true;
3129             }
3130
3131 #if ENABLE(CSS_SHAPES)
3132             if (m_lastFloatFromPreviousLine)
3133                 updateSegmentsForShapes(m_block, m_lastFloatFromPreviousLine, wordMeasurements, m_width, m_lineInfo.isFirstLine());
3134 #endif
3135             applyWordSpacing = wordSpacing && m_currentCharacterIsSpace;
3136
3137             if (!m_width.committedWidth() && m_autoWrap && !m_width.fitsOnLine())
3138                 m_width.fitBelowFloats();
3139
3140             if (m_autoWrap || breakWords) {
3141                 // If we break only after white-space, consider the current character
3142                 // as candidate width for this line.
3143                 bool lineWasTooWide = false;
3144                 if (m_width.fitsOnLine() && m_currentCharacterIsSpace && m_currentStyle->breakOnlyAfterWhiteSpace() && !midWordBreak) {
3145                     float charWidth = textWidth(renderText, m_current.m_pos, 1, font, m_width.currentWidth(), isFixedPitch, m_collapseWhiteSpace, wordMeasurement.fallbackFonts, textLayout) + (applyWordSpacing ? wordSpacing : 0);
3146                     // Check if line is too big even without the extra space
3147                     // at the end of the line. If it is not, do nothing.
3148                     // If the line needs the extra whitespace to be too long,
3149                     // then move the line break to the space and skip all
3150                     // additional whitespace.
3151                     if (!m_width.fitsOnLineIncludingExtraWidth(charWidth)) {
3152                         lineWasTooWide = true;
3153                         m_lineBreak.moveTo(m_current.m_obj, m_current.m_pos, m_current.m_nextBreakablePosition);
3154                         m_lineBreaker.skipTrailingWhitespace(m_lineBreak, m_lineInfo);
3155                     }
3156                 }
3157                 if (lineWasTooWide || !m_width.fitsOnLine()) {
3158                     if (canHyphenate && !m_width.fitsOnLine()) {
3159                         tryHyphenating(renderText, font, style.locale(), consecutiveHyphenatedLines, m_blockStyle.hyphenationLimitLines(), style.hyphenationLimitBefore(), style.hyphenationLimitAfter(), lastSpace, m_current.m_pos, m_width.currentWidth() - additionalTempWidth, m_width.availableWidth(), isFixedPitch, m_collapseWhiteSpace, lastSpaceWordSpacing, m_lineBreak, m_current.m_nextBreakablePosition, m_lineBreaker.m_hyphenated);
3160                         if (m_lineBreaker.m_hyphenated) {
3161                             m_atEnd = true;
3162                             return false;
3163                         }
3164                     }
3165                     if (m_lineBreak.atTextParagraphSeparator()) {
3166                         if (!stoppedIgnoringSpaces && m_current.m_pos > 0)
3167                             ensureCharacterGetsLineBox(m_lineMidpointState, m_current);
3168                         m_lineBreak.increment();
3169                         m_lineInfo.setPreviousLineBrokeCleanly(true);
3170                         wordMeasurement.endOffset = m_lineBreak.m_pos;
3171                     }
3172                     if (m_lineBreak.m_obj && m_lineBreak.m_pos && m_lineBreak.m_obj->isText() && toRenderText(m_lineBreak.m_obj)->textLength() && toRenderText(m_lineBreak.m_obj)->characterAt(m_lineBreak.m_pos - 1) == softHyphen && style.hyphens() != HyphensNone)
3173                         hyphenated = true;
3174                     if (m_lineBreak.m_pos && m_lineBreak.m_pos != (unsigned)wordMeasurement.endOffset && !wordMeasurement.width) {
3175                         if (charWidth) {
3176                             wordMeasurement.endOffset = m_lineBreak.m_pos;
3177                             wordMeasurement.width = charWidth;
3178                         }
3179                     }
3180                     // Didn't fit. Jump to the end unless there's still an opportunity to collapse whitespace.
3181                     if (m_ignoringSpaces || !m_collapseWhiteSpace || !m_currentCharacterIsSpace || !previousCharacterIsSpace) {
3182                         m_atEnd = true;
3183                         return false;
3184                     }
3185                 } else {
3186                     if (!betweenWords || (midWordBreak && !m_autoWrap))
3187                         m_width.addUncommittedWidth(-additionalTempWidth);
3188                     if (hyphenWidth) {
3189                         // Subtract the width of the soft hyphen out since we fit on a line.
3190                         m_width.addUncommittedWidth(-hyphenWidth);
3191                         hyphenWidth = 0;
3192                     }
3193                 }
3194             }
3195
3196             if (c == '\n' && m_preservesNewline) {
3197                 if (!stoppedIgnoringSpaces && m_current.m_pos > 0)
3198                     ensureCharacterGetsLineBox(m_lineMidpointState, m_current);
3199                 m_lineBreak.moveTo(m_current.m_obj, m_current.m_pos, m_current.m_nextBreakablePosition);
3200                 m_lineBreak.increment();
3201                 m_lineInfo.setPreviousLineBrokeCleanly(true);
3202                 return true;
3203             }
3204
3205             if (m_autoWrap && betweenWords) {
3206                 m_width.commit();
3207                 wrapW = 0;
3208                 m_lineBreak.moveTo(m_current.m_obj, m_current.m_pos, m_current.m_nextBreakablePosition);
3209                 // Auto-wrapping text should not wrap in the middle of a word once it has had an
3210                 // opportunity to break after a word.
3211                 breakWords = false;
3212             }
3213
3214             if (midWordBreak && !U16_IS_TRAIL(c) && !(U_GET_GC_MASK(c) & U_GC_M_MASK)) {
3215                 // Remember this as a breakable position in case
3216                 // adding the end width forces a break.
3217                 m_lineBreak.moveTo(m_current.m_obj, m_current.m_pos, m_current.m_nextBreakablePosition);
3218                 midWordBreak &= (breakWords || breakAll);
3219             }
3220
3221             if (betweenWords) {
3222                 lastSpaceWordSpacing = applyWordSpacing ? wordSpacing : 0;
3223                 wordSpacingForWordMeasurement = (applyWordSpacing && wordMeasurement.width) ? wordSpacing : 0;
3224                 lastSpace = m_current.m_pos;
3225             }
3226
3227             if (!m_ignoringSpaces && m_currentStyle->collapseWhiteSpace()) {
3228                 // If we encounter a newline, or if we encounter a
3229                 // second space, we need to go ahead and break up this
3230                 // run and enter a mode where we start collapsing spaces.
3231                 if (m_currentCharacterIsSpace && previousCharacterIsSpace) {
3232                     m_ignoringSpaces = true;
3233
3234                     // We just entered a mode where we are ignoring
3235                     // spaces. Create a midpoint to terminate the run
3236                     // before the second space.
3237                     startIgnoringSpaces(m_lineMidpointState, m_startOfIgnoredSpaces);
3238                     m_trailingObjects.updateMidpointsForTrailingBoxes(m_lineMidpointState, InlineIterator(), TrailingObjects::DoNotCollapseFirstSpace);
3239                 }
3240             }
3241         } else if (m_ignoringSpaces) {
3242             // Stop ignoring spaces and begin at this
3243             // new point.
3244             m_ignoringSpaces = false;
3245             lastSpaceWordSpacing = applyWordSpacing ? wordSpacing : 0;
3246             wordSpacingForWordMeasurement = (applyWordSpacing && wordMeasurements.last().width) ? wordSpacing : 0;
3247             lastSpace = m_current.m_pos; // e.g., "Foo    goo", don't add in any of the ignored spaces.
3248             stopIgnoringSpaces(m_lineMidpointState, InlineIterator(0, m_current.m_obj, m_current.m_pos));
3249         }
3250 #if ENABLE(SVG)
3251         if (isSVGText && m_current.m_pos > 0) {
3252             // Force creation of new InlineBoxes for each absolute positioned character (those that start new text chunks).
3253             if (toRenderSVGInlineText(renderText)->characterStartsNewTextChunk(m_current.m_pos))
3254                 ensureCharacterGetsLineBox(m_lineMidpointState, m_current);
3255         }
3256 #endif
3257
3258         if (m_currentCharacterIsSpace && !previousCharacterIsSpace) {
3259             m_startOfIgnoredSpaces.m_obj = m_current.m_obj;
3260             m_startOfIgnoredSpaces.m_pos = m_current.m_pos;
3261             // Spaces after right-aligned text and before a line-break get collapsed away completely so that the trailing
3262             // space doesn't seem to push the text out from the right-hand edge.
3263             // FIXME: Do this regardless of the container's alignment - will require rebaselining a lot of test results.
3264             if (m_nextObject && m_nextObject->isBR() && (m_blockStyle.textAlign() == RIGHT || m_blockStyle.textAlign() == WEBKIT_RIGHT)) {
3265                 m_startOfIgnoredSpaces.m_pos--;
3266                 // If there's just a single trailing space start ignoring it now so it collapses away.
3267                 if (m_current.m_pos == renderText->textLength() - 1)
3268                     startIgnoringSpaces(m_lineMidpointState, m_startOfIgnoredSpaces);
3269             }
3270         }
3271
3272         if (!m_currentCharacterIsSpace && previousCharacterIsWS) {
3273             if (m_autoWrap && m_currentStyle->breakOnlyAfterWhiteSpace())
3274                 m_lineBreak.moveTo(m_current.m_obj, m_current.m_pos, m_current.m_nextBreakablePosition);
3275         }
3276
3277         if (m_collapseWhiteSpace && m_currentCharacterIsSpace && !m_ignoringSpaces)
3278             m_trailingObjects.setTrailingWhitespace(toRenderText(m_current.m_obj));
3279         else if (!m_currentStyle->collapseWhiteSpace() || !m_currentCharacterIsSpace)
3280             m_trailingObjects.clear();
3281
3282         m_atStart = false;
3283         nextCharacter(c, lastCharacter, secondToLastCharacter);
3284     }
3285
3286     m_renderTextInfo.m_lineBreakIterator.setPriorContext(lastCharacter, secondToLastCharacter);
3287
3288     wordMeasurements.grow(wordMeasurements.size() + 1);
3289     WordMeasurement& wordMeasurement = wordMeasurements.last();
3290     wordMeasurement.renderer = renderText;
3291
3292     // IMPORTANT: current.m_pos is > length here!
3293     float additionalTempWidth = m_ignoringSpaces ? 0 : textWidth(renderText, lastSpace, m_current.m_pos - lastSpace, font, m_width.currentWidth(), isFixedPitch, m_collapseWhiteSpace, wordMeasurement.fallbackFonts, textLayout);
3294     wordMeasurement.startOffset = lastSpace;
3295     wordMeasurement.endOffset = m_current.m_pos;
3296     wordMeasurement.width = m_ignoringSpaces ? 0 : additionalTempWidth + wordSpacingForWordMeasurement;
3297     additionalTempWidth += lastSpaceWordSpacing;
3298
3299     float inlineLogicalTempWidth = inlineLogicalWidth(m_current.m_obj, !m_appliedStartWidth, m_includeEndWidth);
3300     m_width.addUncommittedWidth(additionalTempWidth + inlineLogicalTempWidth);
3301
3302     if (wordMeasurement.fallbackFonts.isEmpty() && !fallbackFonts.isEmpty())
3303         wordMeasurement.fallbackFonts.swap(fallbackFonts);
3304     fallbackFonts.clear();
3305
3306     if (m_collapseWhiteSpace && m_currentCharacterIsSpace && additionalTempWidth)
3307         m_width.setTrailingWhitespaceWidth(additionalTempWidth, inlineLogicalTempWidth);
3308
3309     m_includeEndWidth = false;
3310
3311     if (!m_width.fitsOnLine()) {
3312         if (canHyphenate)
3313             tryHyphenating(renderText, font, style.locale(), consecutiveHyphenatedLines, m_blockStyle.hyphenationLimitLines(), style.hyphenationLimitBefore(), style.hyphenationLimitAfter(), lastSpace, m_current.m_pos, m_width.currentWidth() - additionalTempWidth, m_width.availableWidth(), isFixedPitch, m_collapseWhiteSpace, lastSpaceWordSpacing, m_lineBreak, m_current.m_nextBreakablePosition, m_lineBreaker.m_hyphenated);
3314
3315         if (!hyphenated && m_lineBreak.previousInSameNode() == softHyphen && style.hyphens() != HyphensNone) {
3316             hyphenated = true;
3317             m_atEnd = true;
3318         }
3319     }
3320     return false;
3321 }
3322
3323 static bool textBeginsWithBreakablePosition(RenderObject* next)
3324 {
3325     ASSERT(next->isText());
3326     RenderText* nextText = toRenderText(next);
3327     if (!nextText->textLength())
3328         return false;
3329     UChar c = nextText->characterAt(0);
3330     return c == ' ' || c == '\t' || (c == '\n' && !nextText->preservesNewline());
3331 }
3332
3333 inline bool BreakingContext::canBreakAtThisPosition()
3334 {
3335     // If we are no-wrap and have found a line-breaking opportunity already then we should take it.
3336     if (m_width.committedWidth() && !m_width.fitsOnLine(m_currentCharacterIsSpace) && m_currWS == NOWRAP)
3337         return true;
3338
3339     // Avoid breaking before empty inlines.
3340     if (m_nextObject && m_nextObject->isRenderInline() && isEmptyInline(toRenderInline(*m_nextObject)))
3341         return false;
3342
3343     // Return early if we autowrap and the current character is a space as we will always want to break at such a position.
3344     if (m_autoWrap && m_currentCharacterIsSpace)
3345         return true;
3346
3347     if (m_nextObject && m_nextObject->isLineBreakOpportunity())
3348         return m_autoWrap;
3349
3350     bool nextIsAutoWrappingText = (m_nextObject && m_nextObject->isText() && (m_autoWrap || m_nextObject->style()->autoWrap()));
3351     if (!nextIsAutoWrappingText)
3352         return m_autoWrap;
3353     bool currentIsTextOrEmptyInline = m_current.m_obj->isText() || (m_current.m_obj->isRenderInline() && isEmptyInline(toRenderInline(*m_current.m_obj)));
3354     if (!currentIsTextOrEmptyInline)
3355         return m_autoWrap;
3356
3357     bool canBreakHere = !m_currentCharacterIsSpace && textBeginsWithBreakablePosition(m_nextObject);
3358
3359     // See if attempting to fit below floats creates more available width on the line.
3360     if (!m_width.fitsOnLine() && !m_width.committedWidth())
3361         m_width.fitBelowFloats();
3362
3363     bool canPlaceOnLine = m_width.fitsOnLine() || !m_autoWrapWasEverTrueOnLine;
3364
3365     if (canPlaceOnLine && canBreakHere)
3366         commitLineBreakAtCurrentWidth(m_nextObject);
3367
3368     return canBreakHere;
3369 }
3370
3371 inline void BreakingContext::commitAndUpdateLineBreakIfNeeded()
3372 {
3373     bool checkForBreak = canBreakAtThisPosition();
3374
3375     if (checkForBreak && !m_width.fitsOnLine(m_ignoringSpaces)) {
3376         // if we have floats, try to get below them.
3377         if (m_currentCharacterIsSpace && !m_ignoringSpaces && m_currentStyle->collapseWhiteSpace())
3378             m_trailingObjects.clear();
3379
3380         if (m_width.committedWidth()) {
3381             m_atEnd = true;
3382             return;
3383         }
3384
3385         m_width.fitBelowFloats();
3386
3387         // |width| may have been adjusted because we got shoved down past a float (thus
3388         // giving us more room), so we need to retest, and only jump to
3389         // the end label if we still don't fit on the line. -dwh
3390         if (!m_width.fitsOnLine(m_ignoringSpaces)) {
3391             m_atEnd = true;
3392             return;
3393         }
3394     } else if (m_blockStyle.autoWrap() && !m_width.fitsOnLine() && !m_width.committedWidth()) {
3395         // If the container autowraps but the current child does not then we still need to ensure that it
3396         // wraps and moves below any floats.
3397         m_width.fitBelowFloats();
3398     }
3399
3400     if (!m_current.m_obj->isFloatingOrOutOfFlowPositioned()) {
3401         m_lastObject = m_current.m_obj;
3402         if (m_lastObject->isReplaced() && m_autoWrap && (!m_lastObject->isImage() || m_allowImagesToBreak) && (!m_lastObject->isListMarker() || toRenderListMarker(*m_lastObject).isInside())) {
3403             m_width.commit();
3404             m_lineBreak.moveToStartOf(m_nextObject);
3405         }
3406     }
3407 }
3408
3409 InlineIterator BreakingContext::handleEndOfLine()
3410 {
3411 #if ENABLE(CSS_SHAPES)
3412     ShapeInsideInfo* shapeInfo = m_block.layoutShapeInsideInfo();
3413     bool segmentAllowsOverflow = !shapeInfo || !shapeInfo->hasSegments();
3414 #else
3415     bool segmentAllowsOverflow = true;
3416 #endif
3417     if (segmentAllowsOverflow) {
3418         if (m_lineBreak == m_resolver.position()) {
3419             if (!m_lineBreak.m_obj || !m_lineBreak.m_obj->isBR()) {
3420                 // we just add as much as possible
3421                 if (m_blockStyle.whiteSpace() == PRE && !m_current.m_pos) {
3422                     m_lineBreak.moveTo(m_lastObject, m_lastObject->isText() ? m_lastObject->length() : 0);
3423                 } else if (m_lineBreak.m_obj) {
3424                     // Don't ever break in the middle of a word if we can help it.
3425                     // There's no room at all. We just have to be on this line,
3426                     // even though we'll spill out.
3427                     m_lineBreak.moveTo(m_current.m_obj, m_current.m_pos);
3428                 }
3429             }
3430             // make sure we consume at least one char/object.
3431             if (m_lineBreak == m_resolver.position())
3432                 m_lineBreak.increment();
3433         } else if (!m_current.m_pos && !m_width.committedWidth() && m_width.uncommittedWidth() && !m_hadUncommittedWidthBeforeCurrent) {
3434             // Do not push the current object to the next line, when this line has some content, but it is still considered empty.
3435             // Empty inline elements like <span></span> can produce such lines and now we just ignore these break opportunities
3436             // at the start of a line, if no width has been committed yet.
3437             // Behave as if it was actually empty and consume at least one object.
3438             m_lineBreak.increment();
3439         }
3440     }
3441
3442     // Sanity check our midpoints.
3443     checkMidpoints(m_lineMidpointState, m_lineBreak);
3444
3445     m_trailingObjects.updateMidpointsForTrailingBoxes(m_lineMidpointState, m_lineBreak, TrailingObjects::CollapseFirstSpace);
3446
3447     // We might have made lineBreak an iterator that points past the end
3448     // of the object. Do this adjustment to make it point to the start
3449     // of the next object instead to avoid confusing the rest of the
3450     // code.
3451     if (m_lineBreak.m_pos > 0) {
3452         m_lineBreak.m_pos--;
3453         m_lineBreak.increment();
3454     }
3455
3456     return m_lineBreak;
3457 }
3458
3459 InlineIterator LineBreaker::nextSegmentBreak(InlineBidiResolver& resolver, LineInfo& lineInfo, RenderTextInfo& renderTextInfo, FloatingObject* lastFloatFromPreviousLine, unsigned consecutiveHyphenatedLines, WordMeasurements& wordMeasurements)
3460 {
3461     reset();
3462
3463     ASSERT(resolver.position().root() == &m_block);
3464
3465     bool appliedStartWidth = resolver.position().m_pos > 0;
3466
3467     LineWidth width(m_block, lineInfo.isFirstLine(), requiresIndent(lineInfo.isFirstLine(), lineInfo.previousLineBrokeCleanly(), *m_block.style()));
3468
3469     skipLeadingWhitespace(resolver, lineInfo, lastFloatFromPreviousLine, width);
3470
3471     if (resolver.position().atEnd())
3472         return resolver.position();
3473
3474     BreakingContext context(*this, resolver, lineInfo, width, renderTextInfo, lastFloatFromPreviousLine, appliedStartWidth, m_block);
3475
3476     while (context.currentObject()) {
3477         context.initializeForCurrentObject();
3478         if (context.currentObject()->isBR()) {
3479             context.handleBR(m_clear);
3480         } else if (context.currentObject()->isOutOfFlowPositioned()) {
3481             context.handleOutOfFlowPositioned(m_positionedObjects);
3482         } else if (context.currentObject()->isFloating()) {
3483             context.handleFloat();
3484         } else if (context.currentObject()->isRenderInline()) {
3485             context.handleEmptyInline();
3486         } else if (context.currentObject()->isReplaced()) {
3487             context.handleReplaced();
3488         } else if (context.currentObject()->isText()) {
3489             if (context.handleText(wordMeasurements, m_hyphenated, consecutiveHyphenatedLines)) {
3490                 // We've hit a hard text line break. Our line break iterator is updated, so go ahead and early return.
3491                 return context.lineBreak();
3492             }
3493         } else if (context.currentObject()->isLineBreakOpportunity())
3494             context.commitLineBreakAtCurrentWidth(context.currentObject());
3495         else
3496             ASSERT_NOT_REACHED();
3497
3498         if (context.atEnd())
3499             return context.handleEndOfLine();
3500
3501         context.commitAndUpdateLineBreakIfNeeded();
3502
3503         if (context.atEnd())
3504             return context.handleEndOfLine();
3505
3506         context.increment();
3507     }
3508
3509     context.clearLineBreakIfFitsOnLine(true);
3510
3511     return context.handleEndOfLine();
3512 }
3513
3514 void RenderBlockFlow::addOverflowFromInlineChildren()
3515 {
3516     if (auto lines = simpleLines()) {
3517         ASSERT(!hasOverflowClip());
3518         SimpleLineLayout::collectFlowOverflow(*this, *lines);
3519         return;
3520     }
3521     LayoutUnit endPadding = hasOverflowClip() ? paddingEnd() : LayoutUnit();
3522     // FIXME: Need to find another way to do this, since scrollbars could show when we don't want them to.
3523     if (hasOverflowClip() && !endPadding && element() && element()->isRootEditableElement() && style()->isLeftToRightDirection())
3524         endPadding = 1;
3525     for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
3526         addLayoutOverflow(curr->paddedLayoutOverflowRect(endPadding));
3527         RenderRegion* region = curr->containingRegion();
3528         if (region)
3529             region->addLayoutOverflowForBox(this, curr->paddedLayoutOverflowRect(endPadding));
3530         if (!hasOverflowClip()) {
3531             addVisualOverflow(curr->visualOverflowRect(curr->lineTop(), curr->lineBottom()));
3532             if (region)
3533                 region->addVisualOverflowForBox(this, curr->visualOverflowRect(curr->lineTop(), curr->lineBottom()));
3534         }
3535     }
3536 }
3537
3538 void RenderBlockFlow::deleteEllipsisLineBoxes()
3539 {
3540     ETextAlign textAlign = style()->textAlign();
3541     bool ltr = style()->isLeftToRightDirection();
3542     bool firstLine = true;
3543     for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
3544         if (curr->hasEllipsisBox()) {
3545             curr->clearTruncation();
3546
3547             // Shift the line back where it belongs if we cannot accomodate an ellipsis.
3548             float logicalLeft = pixelSnappedLogicalLeftOffsetForLine(curr->lineTop(), firstLine);
3549             float availableLogicalWidth = logicalRightOffsetForLine(curr->lineTop(), false) - logicalLeft;
3550             float totalLogicalWidth = curr->logicalWidth();
3551             updateLogicalWidthForAlignment(textAlign, 0, logicalLeft, totalLogicalWidth, availableLogicalWidth, 0);
3552
3553             if (ltr)
3554                 curr->adjustLogicalPosition((logicalLeft - curr->logicalLeft()), 0);
3555             else