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