17f431a75d49bf9942bf704d0320a4af6bfa6b33
[WebKit-https.git] / Source / WebCore / rendering / RenderBlockLineLayout.cpp
1 /*
2  * Copyright (C) 2000 Lars Knoll (knoll@kde.org)
3  * Copyright (C) 2003, 2004, 2006, 2007, 2008, 2009, 2010, 2011 Apple Inc. All right reserved.
4  * Copyright (C) 2010 Google Inc. All rights reserved.
5  * Copyright (C) 2013 ChangSeok Oh <shivamidow@gmail.com>
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Library General Public
9  * License as published by the Free Software Foundation; either
10  * version 2 of the License, or (at your option) any later version.
11  *
12  * This library is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * Library General Public License for more details.
16  *
17  * You should have received a copy of the GNU Library General Public License
18  * along with this library; see the file COPYING.LIB.  If not, write to
19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
20  * Boston, MA 02110-1301, USA.
21  *
22  */
23
24 #include "config.h"
25
26 #include "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 "ExclusionShapeInsideInfo.h"
52 #endif
53
54 #if ENABLE(SVG)
55 #include "RenderSVGInlineText.h"
56 #include "SVGRootInlineBox.h"
57 #endif
58
59 using namespace std;
60 using namespace WTF;
61 using namespace Unicode;
62
63 namespace WebCore {
64
65 // We don't let our line box tree for a single line get any deeper than this.
66 const unsigned cMaxLineDepth = 200;
67
68 static 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)
80 ExclusionShapeInsideInfo* RenderBlock::layoutExclusionShapeInsideInfo() const
81 {
82     ExclusionShapeInsideInfo* shapeInsideInfo = view()->layoutState()->exclusionShapeInsideInfo();
83
84     if (!shapeInsideInfo && flowThreadContainingBlock() && allowsExclusionShapeInsideInfoSharing()) {
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->exclusionShapeInsideInfo();
90     }
91
92     return shapeInsideInfo;
93 }
94 #endif
95
96 enum IndentTextOrNot { DoNotIndentText, IndentText };
97
98 class LineWidth {
99 public:
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_left(0)
107         , m_right(0)
108         , m_availableWidth(0)
109 #if ENABLE(CSS_SHAPES)
110         , m_segment(0)
111 #endif
112         , m_isFirstLine(isFirstLine)
113         , m_shouldIndentText(shouldIndentText)
114     {
115         ASSERT(block);
116 #if ENABLE(CSS_SHAPES)
117         ExclusionShapeInsideInfo* exclusionShapeInsideInfo = m_block->layoutExclusionShapeInsideInfo();
118         if (exclusionShapeInsideInfo)
119             m_segment = exclusionShapeInsideInfo->currentSegment();
120 #endif
121         updateAvailableWidth();
122     }
123     bool fitsOnLine() const { return currentWidth() <= m_availableWidth; }
124     bool fitsOnLine(float extra) const { return currentWidth() + extra <= m_availableWidth; }
125     bool fitsOnLine(float extra, bool excludeWhitespace) const { return currentWidth() - (excludeWhitespace ? trailingWhitespaceWidth() : 0) + 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     float trailingWhitespaceWidth() const { return m_trailingWhitespaceWidth; }
133
134     void updateAvailableWidth(LayoutUnit minimumHeight = 0);
135     void shrinkAvailableWidthForNewFloatIfNeeded(RenderBlock::FloatingObject*);
136     void addUncommittedWidth(float delta) { m_uncommittedWidth += delta; }
137     void commit()
138     {
139         m_committedWidth += m_uncommittedWidth;
140         m_uncommittedWidth = 0;
141     }
142     void applyOverhang(RenderRubyRun*, RenderObject* startRenderer, RenderObject* endRenderer);
143     void fitBelowFloats();
144     void setTrailingWhitespaceWidth(float width) { m_trailingWhitespaceWidth = width; }
145
146     bool shouldIndentText() { return m_shouldIndentText == IndentText; }
147
148 private:
149     void computeAvailableWidthFromLeftAndRight()
150     {
151         m_availableWidth = max(0.0f, m_right - m_left) + m_overhangWidth;
152     }
153
154 private:
155     RenderBlock* m_block;
156     float m_uncommittedWidth;
157     float m_committedWidth;
158     float m_overhangWidth; // The amount by which |m_availableWidth| has been inflated to account for possible contraction due to ruby overhang.
159     float m_trailingWhitespaceWidth;
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
170 inline 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
187 inline 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     ExclusionShapeOutsideInfo* 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()->exclusionShapeOutsideInfo();
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     ExclusionShapeOutsideInfo* shapeOutsideInfo = newFloat->renderer()->exclusionShapeOutsideInfo();
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
247 void 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
261 void 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
292 class LineInfo {
293 public:
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
329 private:
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
338 static inline LayoutUnit borderPaddingMarginStart(RenderInline* child)
339 {
340     return child->marginStart() + child->paddingStart() + child->borderStart();
341 }
342
343 static inline LayoutUnit borderPaddingMarginEnd(RenderInline* child)
344 {
345     return child->marginEnd() + child->paddingEnd() + child->borderEnd();
346 }
347
348 static 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
354 static RenderObject* previousInFlowSibling(RenderObject* child)
355 {
356     child = child->previousSibling();
357     while (child && child->isOutOfFlowPositioned())
358         child = child->previousSibling();
359     return child;
360 }
361
362 static 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
385 static 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
405 static 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())
421                 endpoint.m_pos--;
422         }
423     }
424 }
425
426 // Don't call this directly. Use one of the descriptive helper functions below.
427 static 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
436 static inline void startIgnoringSpaces(LineMidpointState& lineMidpointState, const InlineIterator& midpoint)
437 {
438     ASSERT(!(lineMidpointState.numMidpoints % 2));
439     deprecatedAddMidpoint(lineMidpointState, midpoint);
440 }
441
442 static 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.
450 static 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.
458 static 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
465 static 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
470 void 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
511 static 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.
533 static inline void updateCounterIfNeeded(RenderText* o)
534 {
535     if (!o->preferredLogicalWidthsDirty() || !o->isCounter())
536         return;
537     toRenderCounter(o)->updateCounter();
538 }
539
540 static 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
550 static 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
560 InlineFlowBox* 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
623 template <typename CharacterType>
624 static 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
634 static 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
653 RootInlineBox* 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
732 ETextAlign 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
741 static 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
757 static 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
779 static 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
793 void 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
809 static inline float measureHyphenWidth(RenderText* renderer, const Font& font)
810 {
811     RenderStyle* style = renderer->style();
812     return font.width(RenderBlock::constructTextRun(renderer, font, style->hyphenString().string(), style));
813 }
814
815 class WordMeasurement {
816 public:
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
832 static 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);
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             const 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                 measuredWidth += renderer->width(wordMeasurement.startOffset, wordLength, xPos + measuredWidth, lineInfo.isFirstLine());
879                 UChar c = renderer->characterAt(wordMeasurement.startOffset);
880                 if (i > 0 && wordLength == 1 && (c == ' ' || c == '\t'))
881                     measuredWidth += renderer->style()->wordSpacing();
882             } else
883                 measuredWidth += wordMeasurement.width;
884             if (!wordMeasurement.fallbackFonts.isEmpty()) {
885                 HashSet<const SimpleFontData*>::const_iterator end = wordMeasurement.fallbackFonts.end();
886                 for (HashSet<const SimpleFontData*>::const_iterator it = wordMeasurement.fallbackFonts.begin(); it != end; ++it)
887                     fallbackFonts.add(*it);
888             }
889         }
890         if (measuredWidth && lastEndOffset != run->m_stop) {
891             // If we don't have enough cached data, we'll measure the run again.
892             measuredWidth = 0;
893             fallbackFonts.clear();
894         }
895     }
896
897     if (!measuredWidth)
898         measuredWidth = renderer->width(run->m_start, run->m_stop - run->m_start, xPos, lineInfo.isFirstLine(), &fallbackFonts, &glyphOverflow);
899
900     run->m_box->setLogicalWidth(measuredWidth + hyphenWidth);
901     if (!fallbackFonts.isEmpty()) {
902         ASSERT(run->m_box->isText());
903         GlyphOverflowAndFallbackFontsMap::iterator it = textBoxDataMap.add(toInlineTextBox(run->m_box), make_pair(Vector<const SimpleFontData*>(), GlyphOverflow())).iterator;
904         ASSERT(it->value.first.isEmpty());
905         copyToVector(fallbackFonts, it->value.first);
906         run->m_box->parent()->clearDescendantsHaveSameLineHeightAndBaseline();
907     }
908     if ((glyphOverflow.top || glyphOverflow.bottom || glyphOverflow.left || glyphOverflow.right)) {
909         ASSERT(run->m_box->isText());
910         GlyphOverflowAndFallbackFontsMap::iterator it = textBoxDataMap.add(toInlineTextBox(run->m_box), make_pair(Vector<const SimpleFontData*>(), GlyphOverflow())).iterator;
911         it->value.second = glyphOverflow;
912         run->m_box->clearKnownToHaveNoOverflow();
913     }
914 }
915
916 static inline void computeExpansionForJustifiedText(BidiRun* firstRun, BidiRun* trailingSpaceRun, Vector<unsigned, 16>& expansionOpportunities, unsigned expansionOpportunityCount, float& totalLogicalWidth, float availableLogicalWidth)
917 {
918     if (!expansionOpportunityCount || availableLogicalWidth <= totalLogicalWidth)
919         return;
920
921     size_t i = 0;
922     for (BidiRun* r = firstRun; r; r = r->next()) {
923 #if ENABLE(CSS_SHAPES)
924         // This method is called once per segment, do not move past the current segment.
925         if (r->m_startsSegment)
926             break;
927 #endif
928         if (!r->m_box || r == trailingSpaceRun)
929             continue;
930         
931         if (r->m_object->isText()) {
932             unsigned opportunitiesInRun = expansionOpportunities[i++];
933             
934             ASSERT(opportunitiesInRun <= expansionOpportunityCount);
935             
936             // Only justify text if whitespace is collapsed.
937             if (r->m_object->style()->collapseWhiteSpace()) {
938                 InlineTextBox* textBox = toInlineTextBox(r->m_box);
939                 int expansion = (availableLogicalWidth - totalLogicalWidth) * opportunitiesInRun / expansionOpportunityCount;
940                 textBox->setExpansion(expansion);
941                 totalLogicalWidth += expansion;
942             }
943             expansionOpportunityCount -= opportunitiesInRun;
944             if (!expansionOpportunityCount)
945                 break;
946         }
947     }
948 }
949
950 void RenderBlock::updateLogicalWidthForAlignment(const ETextAlign& textAlign, BidiRun* trailingSpaceRun, float& logicalLeft, float& totalLogicalWidth, float& availableLogicalWidth, int expansionOpportunityCount)
951 {
952     // Armed with the total width of the line (without justification),
953     // we now examine our text-align property in order to determine where to position the
954     // objects horizontally. The total width of the line can be increased if we end up
955     // justifying text.
956     switch (textAlign) {
957     case LEFT:
958     case WEBKIT_LEFT:
959         updateLogicalWidthForLeftAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
960         break;
961     case RIGHT:
962     case WEBKIT_RIGHT:
963         updateLogicalWidthForRightAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
964         break;
965     case CENTER:
966     case WEBKIT_CENTER:
967         updateLogicalWidthForCenterAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
968         break;
969     case JUSTIFY:
970         adjustInlineDirectionLineBounds(expansionOpportunityCount, logicalLeft, availableLogicalWidth);
971         if (expansionOpportunityCount) {
972             if (trailingSpaceRun) {
973                 totalLogicalWidth -= trailingSpaceRun->m_box->logicalWidth();
974                 trailingSpaceRun->m_box->setLogicalWidth(0);
975             }
976             break;
977         }
978         // Fall through
979     case TASTART:
980         if (style()->isLeftToRightDirection())
981             updateLogicalWidthForLeftAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
982         else
983             updateLogicalWidthForRightAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
984         break;
985     case TAEND:
986         if (style()->isLeftToRightDirection())
987             updateLogicalWidthForRightAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
988         else
989             updateLogicalWidthForLeftAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
990         break;
991     }
992 }
993
994 static IndentTextOrNot requiresIndent(bool isFirstLine, bool isAfterHardLineBreak, RenderStyle* style)
995 {
996     IndentTextOrNot shouldIndentText = DoNotIndentText;
997     if (isFirstLine)
998         shouldIndentText = IndentText;
999 #if ENABLE(CSS3_TEXT)
1000     else if (isAfterHardLineBreak && style->textIndentLine() == TextIndentEachLine) 
1001         shouldIndentText = IndentText;
1002
1003     if (style->textIndentType() == TextIndentHanging)
1004         shouldIndentText = shouldIndentText == IndentText ? DoNotIndentText : IndentText;
1005 #else
1006     UNUSED_PARAM(isAfterHardLineBreak);
1007     UNUSED_PARAM(style);
1008 #endif
1009     return shouldIndentText;
1010 }
1011
1012 static void updateLogicalInlinePositions(RenderBlock* block, float& lineLogicalLeft, float& lineLogicalRight, float& availableLogicalWidth, bool firstLine, IndentTextOrNot shouldIndentText, LayoutUnit boxLogicalHeight)
1013 {
1014     LayoutUnit lineLogicalHeight = logicalHeightForLine(block, firstLine, boxLogicalHeight);
1015     lineLogicalLeft = block->pixelSnappedLogicalLeftOffsetForLine(block->logicalHeight(), shouldIndentText == IndentText, lineLogicalHeight);
1016     lineLogicalRight = block->pixelSnappedLogicalRightOffsetForLine(block->logicalHeight(), shouldIndentText == IndentText, lineLogicalHeight);
1017     availableLogicalWidth = lineLogicalRight - lineLogicalLeft;
1018 }
1019
1020 void RenderBlock::computeInlineDirectionPositionsForLine(RootInlineBox* lineBox, const LineInfo& lineInfo, BidiRun* firstRun, BidiRun* trailingSpaceRun, bool reachedEnd,
1021                                                          GlyphOverflowAndFallbackFontsMap& textBoxDataMap, VerticalPositionCache& verticalPositionCache, WordMeasurements& wordMeasurements)
1022 {
1023     ETextAlign textAlign = textAlignmentForLine(!reachedEnd && !lineBox->endsWithBreak());
1024     
1025     // 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 
1026     // box is only affected if it is the first child of its parent element."
1027     // CSS3 "text-indent", "-webkit-each-line" affects the first line of the block container as well as each line after a forced line break,
1028     // but does not affect lines after a soft wrap break.
1029     bool isFirstLine = lineInfo.isFirstLine() && !(isAnonymousBlock() && parent()->firstChild() != this);
1030     bool isAfterHardLineBreak = lineBox->prevRootBox() && lineBox->prevRootBox()->endsWithBreak();
1031     IndentTextOrNot shouldIndentText = requiresIndent(isFirstLine, isAfterHardLineBreak, style());
1032     float lineLogicalLeft;
1033     float lineLogicalRight;
1034     float availableLogicalWidth;
1035     updateLogicalInlinePositions(this, lineLogicalLeft, lineLogicalRight, availableLogicalWidth, isFirstLine, shouldIndentText, 0);
1036     bool needsWordSpacing;
1037 #if ENABLE(CSS_SHAPES)
1038     ExclusionShapeInsideInfo* exclusionShapeInsideInfo = layoutExclusionShapeInsideInfo();
1039     if (exclusionShapeInsideInfo && exclusionShapeInsideInfo->hasSegments()) {
1040         BidiRun* segmentStart = firstRun;
1041         const SegmentList& segments = exclusionShapeInsideInfo->segments();
1042         float logicalLeft = max<float>(roundToInt(segments[0].logicalLeft), lineLogicalLeft);
1043         float logicalRight = min<float>(floorToInt(segments[0].logicalRight), lineLogicalRight);
1044         float startLogicalLeft = logicalLeft;
1045         float endLogicalRight = logicalLeft;
1046         float minLogicalLeft = logicalLeft;
1047         float maxLogicalRight = logicalLeft;
1048         lineBox->beginPlacingBoxRangesInInlineDirection(logicalLeft);
1049         for (size_t i = 0; i < segments.size(); i++) {
1050             if (i) {
1051                 logicalLeft = max<float>(roundToInt(segments[i].logicalLeft), lineLogicalLeft);
1052                 logicalRight = min<float>(floorToInt(segments[i].logicalRight), lineLogicalRight);
1053             }
1054             availableLogicalWidth = logicalRight - logicalLeft;
1055             BidiRun* newSegmentStart = computeInlineDirectionPositionsForSegment(lineBox, lineInfo, textAlign, logicalLeft, availableLogicalWidth, segmentStart, trailingSpaceRun, textBoxDataMap, verticalPositionCache, wordMeasurements);
1056             needsWordSpacing = false;
1057             endLogicalRight = lineBox->placeBoxRangeInInlineDirection(segmentStart->m_box, newSegmentStart ? newSegmentStart->m_box : 0, logicalLeft, minLogicalLeft, maxLogicalRight, needsWordSpacing, textBoxDataMap);
1058             if (!newSegmentStart || !newSegmentStart->next())
1059                 break;
1060             ASSERT(newSegmentStart->m_startsSegment);
1061             // Discard the empty segment start marker bidi runs
1062             segmentStart = newSegmentStart->next();
1063         }
1064         lineBox->endPlacingBoxRangesInInlineDirection(startLogicalLeft, endLogicalRight, minLogicalLeft, maxLogicalRight);
1065         return;
1066     }
1067 #endif
1068
1069     if (firstRun && firstRun->m_object->isReplaced()) {
1070         RenderBox* renderBox = toRenderBox(firstRun->m_object);
1071         updateLogicalInlinePositions(this, lineLogicalLeft, lineLogicalRight, availableLogicalWidth, isFirstLine, shouldIndentText, renderBox->logicalHeight());
1072     }
1073
1074     computeInlineDirectionPositionsForSegment(lineBox, lineInfo, textAlign, lineLogicalLeft, availableLogicalWidth, firstRun, trailingSpaceRun, textBoxDataMap, verticalPositionCache, wordMeasurements);
1075     // The widths of all runs are now known. We can now place every inline box (and
1076     // compute accurate widths for the inline flow boxes).
1077     needsWordSpacing = false;
1078     lineBox->placeBoxesInInlineDirection(lineLogicalLeft, needsWordSpacing, textBoxDataMap);
1079 }
1080
1081 BidiRun* RenderBlock::computeInlineDirectionPositionsForSegment(RootInlineBox* lineBox, const LineInfo& lineInfo, ETextAlign textAlign, float& logicalLeft, 
1082     float& availableLogicalWidth, BidiRun* firstRun, BidiRun* trailingSpaceRun, GlyphOverflowAndFallbackFontsMap& textBoxDataMap, VerticalPositionCache& verticalPositionCache,
1083     WordMeasurements& wordMeasurements)
1084 {
1085     bool needsWordSpacing = false;
1086     float totalLogicalWidth = lineBox->getFlowSpacingLogicalWidth();
1087     unsigned expansionOpportunityCount = 0;
1088     bool isAfterExpansion = true;
1089     Vector<unsigned, 16> expansionOpportunities;
1090     RenderObject* previousObject = 0;
1091
1092     BidiRun* r = firstRun;
1093     for (; r; r = r->next()) {
1094 #if ENABLE(CSS_SHAPES)
1095         // Once we have reached the start of the next segment, we have finished
1096         // computing the positions for this segment's contents.
1097         if (r->m_startsSegment)
1098             break;
1099 #endif
1100         if (!r->m_box || r->m_object->isOutOfFlowPositioned() || r->m_box->isLineBreak())
1101             continue; // Positioned objects are only participating to figure out their
1102                       // correct static x position.  They have no effect on the width.
1103                       // Similarly, line break boxes have no effect on the width.
1104         if (r->m_object->isText()) {
1105             RenderText* rt = toRenderText(r->m_object);
1106             if (textAlign == JUSTIFY && r != trailingSpaceRun) {
1107                 if (!isAfterExpansion)
1108                     toInlineTextBox(r->m_box)->setCanHaveLeadingExpansion(true);
1109                 unsigned opportunitiesInRun;
1110                 if (rt->is8Bit())
1111                     opportunitiesInRun = Font::expansionOpportunityCount(rt->characters8() + r->m_start, r->m_stop - r->m_start, r->m_box->direction(), isAfterExpansion);
1112                 else
1113                     opportunitiesInRun = Font::expansionOpportunityCount(rt->characters16() + r->m_start, r->m_stop - r->m_start, r->m_box->direction(), isAfterExpansion);
1114                 expansionOpportunities.append(opportunitiesInRun);
1115                 expansionOpportunityCount += opportunitiesInRun;
1116             }
1117
1118             if (int length = rt->textLength()) {
1119                 if (!r->m_start && needsWordSpacing && isSpaceOrNewline(rt->characterAt(r->m_start)))
1120                     totalLogicalWidth += rt->style(lineInfo.isFirstLine())->font().wordSpacing();
1121                 needsWordSpacing = !isSpaceOrNewline(rt->characterAt(r->m_stop - 1)) && r->m_stop == length;
1122             }
1123
1124             setLogicalWidthForTextRun(lineBox, r, rt, totalLogicalWidth, lineInfo, textBoxDataMap, verticalPositionCache, wordMeasurements);
1125         } else {
1126             isAfterExpansion = false;
1127             if (!r->m_object->isRenderInline()) {
1128                 RenderBox* renderBox = toRenderBox(r->m_object);
1129                 if (renderBox->isRubyRun())
1130                     setMarginsForRubyRun(r, toRenderRubyRun(renderBox), previousObject, lineInfo);
1131                 r->m_box->setLogicalWidth(logicalWidthForChild(renderBox));
1132                 totalLogicalWidth += marginStartForChild(renderBox) + marginEndForChild(renderBox);
1133             }
1134         }
1135
1136         totalLogicalWidth += r->m_box->logicalWidth();
1137         previousObject = r->m_object;
1138     }
1139
1140     if (isAfterExpansion && !expansionOpportunities.isEmpty()) {
1141         expansionOpportunities.last()--;
1142         expansionOpportunityCount--;
1143     }
1144
1145     updateLogicalWidthForAlignment(textAlign, trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth, expansionOpportunityCount);
1146
1147     computeExpansionForJustifiedText(firstRun, trailingSpaceRun, expansionOpportunities, expansionOpportunityCount, totalLogicalWidth, availableLogicalWidth);
1148
1149     return r;
1150 }
1151
1152 void RenderBlock::computeBlockDirectionPositionsForLine(RootInlineBox* lineBox, BidiRun* firstRun, GlyphOverflowAndFallbackFontsMap& textBoxDataMap,
1153                                                         VerticalPositionCache& verticalPositionCache)
1154 {
1155     setLogicalHeight(lineBox->alignBoxesInBlockDirection(logicalHeight(), textBoxDataMap, verticalPositionCache));
1156
1157     // Now make sure we place replaced render objects correctly.
1158     for (BidiRun* r = firstRun; r; r = r->next()) {
1159         ASSERT(r->m_box);
1160         if (!r->m_box)
1161             continue; // Skip runs with no line boxes.
1162
1163         // Align positioned boxes with the top of the line box.  This is
1164         // a reasonable approximation of an appropriate y position.
1165         if (r->m_object->isOutOfFlowPositioned())
1166             r->m_box->setLogicalTop(logicalHeight());
1167
1168         // Position is used to properly position both replaced elements and
1169         // to update the static normal flow x/y of positioned elements.
1170         if (r->m_object->isText())
1171             toRenderText(r->m_object)->positionLineBox(r->m_box);
1172         else if (r->m_object->isBox())
1173             toRenderBox(r->m_object)->positionLineBox(r->m_box);
1174     }
1175     // Positioned objects and zero-length text nodes destroy their boxes in
1176     // position(), which unnecessarily dirties the line.
1177     lineBox->markDirty(false);
1178 }
1179
1180 static inline bool isCollapsibleSpace(UChar character, RenderText* renderer)
1181 {
1182     if (character == ' ' || character == '\t' || character == softHyphen)
1183         return true;
1184     if (character == '\n')
1185         return !renderer->style()->preserveNewline();
1186     if (character == noBreakSpace)
1187         return renderer->style()->nbspMode() == SPACE;
1188     return false;
1189 }
1190
1191
1192 static void setStaticPositions(RenderBlock* block, RenderBox* child)
1193 {
1194     // FIXME: The math here is actually not really right. It's a best-guess approximation that
1195     // will work for the common cases
1196     RenderObject* containerBlock = child->container();
1197     LayoutUnit blockHeight = block->logicalHeight();
1198     if (containerBlock->isRenderInline()) {
1199         // A relative positioned inline encloses us. In this case, we also have to determine our
1200         // position as though we were an inline. Set |staticInlinePosition| and |staticBlockPosition| on the relative positioned
1201         // inline so that we can obtain the value later.
1202         toRenderInline(containerBlock)->layer()->setStaticInlinePosition(block->startAlignedOffsetForLine(blockHeight, false));
1203         toRenderInline(containerBlock)->layer()->setStaticBlockPosition(blockHeight);
1204     }
1205     block->updateStaticInlinePositionForChild(child, blockHeight);
1206     child->layer()->setStaticBlockPosition(blockHeight);
1207 }
1208
1209 template <typename CharacterType>
1210 static inline int findFirstTrailingSpace(RenderText* lastText, const CharacterType* characters, int start, int stop)
1211 {
1212     int firstSpace = stop;
1213     while (firstSpace > start) {
1214         UChar current = characters[firstSpace - 1];
1215         if (!isCollapsibleSpace(current, lastText))
1216             break;
1217         firstSpace--;
1218     }
1219
1220     return firstSpace;
1221 }
1222
1223 inline BidiRun* RenderBlock::handleTrailingSpaces(BidiRunList<BidiRun>& bidiRuns, BidiContext* currentContext)
1224 {
1225     if (!bidiRuns.runCount()
1226         || !bidiRuns.logicallyLastRun()->m_object->style()->breakOnlyAfterWhiteSpace()
1227         || !bidiRuns.logicallyLastRun()->m_object->style()->autoWrap())
1228         return 0;
1229
1230     BidiRun* trailingSpaceRun = bidiRuns.logicallyLastRun();
1231     RenderObject* lastObject = trailingSpaceRun->m_object;
1232     if (!lastObject->isText())
1233         return 0;
1234
1235     RenderText* lastText = toRenderText(lastObject);
1236     int firstSpace;
1237     if (lastText->is8Bit())
1238         firstSpace = findFirstTrailingSpace(lastText, lastText->characters8(), trailingSpaceRun->start(), trailingSpaceRun->stop());
1239     else
1240         firstSpace = findFirstTrailingSpace(lastText, lastText->characters16(), trailingSpaceRun->start(), trailingSpaceRun->stop());
1241
1242     if (firstSpace == trailingSpaceRun->stop())
1243         return 0;
1244
1245     TextDirection direction = style()->direction();
1246     bool shouldReorder = trailingSpaceRun != (direction == LTR ? bidiRuns.lastRun() : bidiRuns.firstRun());
1247     if (firstSpace != trailingSpaceRun->start()) {
1248         BidiContext* baseContext = currentContext;
1249         while (BidiContext* parent = baseContext->parent())
1250             baseContext = parent;
1251
1252         BidiRun* newTrailingRun = new (renderArena()) BidiRun(firstSpace, trailingSpaceRun->m_stop, trailingSpaceRun->m_object, baseContext, OtherNeutral);
1253         trailingSpaceRun->m_stop = firstSpace;
1254         if (direction == LTR)
1255             bidiRuns.addRun(newTrailingRun);
1256         else
1257             bidiRuns.prependRun(newTrailingRun);
1258         trailingSpaceRun = newTrailingRun;
1259         return trailingSpaceRun;
1260     }
1261     if (!shouldReorder)
1262         return trailingSpaceRun;
1263
1264     if (direction == LTR) {
1265         bidiRuns.moveRunToEnd(trailingSpaceRun);
1266         trailingSpaceRun->m_level = 0;
1267     } else {
1268         bidiRuns.moveRunToBeginning(trailingSpaceRun);
1269         trailingSpaceRun->m_level = 1;
1270     }
1271     return trailingSpaceRun;
1272 }
1273
1274 void RenderBlock::appendFloatingObjectToLastLine(FloatingObject* floatingObject)
1275 {
1276     ASSERT(!floatingObject->m_originatingLine);
1277     floatingObject->m_originatingLine = lastRootBox();
1278     lastRootBox()->appendFloat(floatingObject->renderer());
1279 }
1280
1281 // FIXME: This should be a BidiStatus constructor or create method.
1282 static inline BidiStatus statusWithDirection(TextDirection textDirection, bool isOverride)
1283 {
1284     WTF::Unicode::Direction direction = textDirection == LTR ? LeftToRight : RightToLeft;
1285     RefPtr<BidiContext> context = BidiContext::create(textDirection == LTR ? 0 : 1, direction, isOverride, FromStyleOrDOM);
1286
1287     // This copies BidiStatus and may churn the ref on BidiContext. I doubt it matters.
1288     return BidiStatus(direction, direction, direction, context.release());
1289 }
1290
1291 // FIXME: BidiResolver should have this logic.
1292 static inline void constructBidiRunsForSegment(InlineBidiResolver& topResolver, BidiRunList<BidiRun>& bidiRuns, const InlineIterator& endOfRuns, VisualDirectionOverride override, bool previousLineBrokeCleanly)
1293 {
1294     // FIXME: We should pass a BidiRunList into createBidiRunsForLine instead
1295     // of the resolver owning the runs.
1296     ASSERT(&topResolver.runs() == &bidiRuns);
1297     ASSERT(topResolver.position() != endOfRuns);
1298     RenderObject* currentRoot = topResolver.position().root();
1299     topResolver.createBidiRunsForLine(endOfRuns, override, previousLineBrokeCleanly);
1300
1301     while (!topResolver.isolatedRuns().isEmpty()) {
1302         // It does not matter which order we resolve the runs as long as we resolve them all.
1303         BidiRun* isolatedRun = topResolver.isolatedRuns().last();
1304         topResolver.isolatedRuns().removeLast();
1305
1306         RenderObject* startObj = isolatedRun->object();
1307
1308         // Only inlines make sense with unicode-bidi: isolate (blocks are already isolated).
1309         // FIXME: Because enterIsolate is not passed a RenderObject, we have to crawl up the
1310         // tree to see which parent inline is the isolate. We could change enterIsolate
1311         // to take a RenderObject and do this logic there, but that would be a layering
1312         // violation for BidiResolver (which knows nothing about RenderObject).
1313         RenderInline* isolatedInline = toRenderInline(containingIsolate(startObj, currentRoot));
1314         InlineBidiResolver isolatedResolver;
1315         EUnicodeBidi unicodeBidi = isolatedInline->style()->unicodeBidi();
1316         TextDirection direction;
1317         if (unicodeBidi == Plaintext)
1318             determineDirectionality(direction, InlineIterator(isolatedInline, isolatedRun->object(), 0));
1319         else {
1320             ASSERT(unicodeBidi == Isolate || unicodeBidi == IsolateOverride);
1321             direction = isolatedInline->style()->direction();
1322         }
1323         isolatedResolver.setStatus(statusWithDirection(direction, isOverride(unicodeBidi)));
1324
1325         // FIXME: The fact that we have to construct an Iterator here
1326         // currently prevents this code from moving into BidiResolver.
1327         if (!bidiFirstSkippingEmptyInlines(isolatedInline, &isolatedResolver))
1328             continue;
1329
1330         // The starting position is the beginning of the first run within the isolate that was identified
1331         // during the earlier call to createBidiRunsForLine. This can be but is not necessarily the
1332         // first run within the isolate.
1333         InlineIterator iter = InlineIterator(isolatedInline, startObj, isolatedRun->m_start);
1334         isolatedResolver.setPositionIgnoringNestedIsolates(iter);
1335
1336         // We stop at the next end of line; we may re-enter this isolate in the next call to constructBidiRuns().
1337         // FIXME: What should end and previousLineBrokeCleanly be?
1338         // rniwa says previousLineBrokeCleanly is just a WinIE hack and could always be false here?
1339         isolatedResolver.createBidiRunsForLine(endOfRuns, NoVisualOverride, previousLineBrokeCleanly);
1340         // Note that we do not delete the runs from the resolver.
1341         // We're not guaranteed to get any BidiRuns in the previous step. If we don't, we allow the placeholder
1342         // itself to be turned into an InlineBox. We can't remove it here without potentially losing track of
1343         // the logically last run.
1344         if (isolatedResolver.runs().runCount())
1345             bidiRuns.replaceRunWithRuns(isolatedRun, isolatedResolver.runs());
1346
1347         // If we encountered any nested isolate runs, just move them
1348         // to the top resolver's list for later processing.
1349         if (!isolatedResolver.isolatedRuns().isEmpty()) {
1350             topResolver.isolatedRuns().appendVector(isolatedResolver.isolatedRuns());
1351             isolatedResolver.isolatedRuns().clear();
1352         }
1353     }
1354 }
1355
1356 static inline void constructBidiRunsForLine(const RenderBlock* block, InlineBidiResolver& topResolver, BidiRunList<BidiRun>& bidiRuns, const InlineIterator& endOfLine, VisualDirectionOverride override, bool previousLineBrokeCleanly)
1357 {
1358 #if !ENABLE(CSS_SHAPES)
1359     UNUSED_PARAM(block);
1360     constructBidiRunsForSegment(topResolver, bidiRuns, endOfLine, override, previousLineBrokeCleanly);
1361 #else
1362     ExclusionShapeInsideInfo* exclusionShapeInsideInfo = block->layoutExclusionShapeInsideInfo();
1363     if (!exclusionShapeInsideInfo || !exclusionShapeInsideInfo->hasSegments()) {
1364         constructBidiRunsForSegment(topResolver, bidiRuns, endOfLine, override, previousLineBrokeCleanly);
1365         return;
1366     }
1367
1368     const SegmentRangeList& segmentRanges = exclusionShapeInsideInfo->segmentRanges();
1369     ASSERT(segmentRanges.size());
1370
1371     for (size_t i = 0; i < segmentRanges.size(); i++) {
1372         LineSegmentIterator iterator = segmentRanges[i].start;
1373         InlineIterator segmentStart(iterator.root, iterator.object, iterator.offset);
1374         iterator = segmentRanges[i].end;
1375         InlineIterator segmentEnd(iterator.root, iterator.object, iterator.offset);
1376         if (i) {
1377             ASSERT(segmentStart.m_obj);
1378             BidiRun* segmentMarker = createRun(segmentStart.m_pos, segmentStart.m_pos, segmentStart.m_obj, topResolver);
1379             segmentMarker->m_startsSegment = true;
1380             bidiRuns.addRun(segmentMarker);
1381             // Do not collapse midpoints between segments
1382             topResolver.midpointState().betweenMidpoints = false;
1383         }
1384         if (segmentStart == segmentEnd)
1385             continue;
1386         topResolver.setPosition(segmentStart, numberOfIsolateAncestors(segmentStart));
1387         constructBidiRunsForSegment(topResolver, bidiRuns, segmentEnd, override, previousLineBrokeCleanly);
1388     }
1389 #endif
1390 }
1391
1392 // This function constructs line boxes for all of the text runs in the resolver and computes their position.
1393 RootInlineBox* RenderBlock::createLineBoxesFromBidiRuns(BidiRunList<BidiRun>& bidiRuns, const InlineIterator& end, LineInfo& lineInfo, VerticalPositionCache& verticalPositionCache, BidiRun* trailingSpaceRun, WordMeasurements& wordMeasurements)
1394 {
1395     if (!bidiRuns.runCount())
1396         return 0;
1397
1398     // FIXME: Why is this only done when we had runs?
1399     lineInfo.setLastLine(!end.m_obj);
1400
1401     RootInlineBox* lineBox = constructLine(bidiRuns, lineInfo);
1402     if (!lineBox)
1403         return 0;
1404
1405     lineBox->setEndsWithBreak(lineInfo.previousLineBrokeCleanly());
1406     
1407 #if ENABLE(SVG)
1408     bool isSVGRootInlineBox = lineBox->isSVGRootInlineBox();
1409 #else
1410     bool isSVGRootInlineBox = false;
1411 #endif
1412     
1413     GlyphOverflowAndFallbackFontsMap textBoxDataMap;
1414     
1415     // Now we position all of our text runs horizontally.
1416     if (!isSVGRootInlineBox)
1417         computeInlineDirectionPositionsForLine(lineBox, lineInfo, bidiRuns.firstRun(), trailingSpaceRun, end.atEnd(), textBoxDataMap, verticalPositionCache, wordMeasurements);
1418     
1419     // Now position our text runs vertically.
1420     computeBlockDirectionPositionsForLine(lineBox, bidiRuns.firstRun(), textBoxDataMap, verticalPositionCache);
1421     
1422 #if ENABLE(SVG)
1423     // SVG text layout code computes vertical & horizontal positions on its own.
1424     // Note that we still need to execute computeVerticalPositionsForLine() as
1425     // it calls InlineTextBox::positionLineBox(), which tracks whether the box
1426     // contains reversed text or not. If we wouldn't do that editing and thus
1427     // text selection in RTL boxes would not work as expected.
1428     if (isSVGRootInlineBox) {
1429         ASSERT(isSVGText());
1430         static_cast<SVGRootInlineBox*>(lineBox)->computePerCharacterLayoutInformation();
1431     }
1432 #endif
1433     
1434     // Compute our overflow now.
1435     lineBox->computeOverflow(lineBox->lineTop(), lineBox->lineBottom(), textBoxDataMap);
1436     
1437 #if PLATFORM(MAC)
1438     // Highlight acts as an overflow inflation.
1439     if (style()->highlight() != nullAtom)
1440         lineBox->addHighlightOverflow();
1441 #endif
1442     return lineBox;
1443 }
1444
1445 // Like LayoutState for layout(), LineLayoutState keeps track of global information
1446 // during an entire linebox tree layout pass (aka layoutInlineChildren).
1447 class LineLayoutState {
1448 public:
1449     LineLayoutState(bool fullLayout, LayoutUnit& repaintLogicalTop, LayoutUnit& repaintLogicalBottom, RenderFlowThread* flowThread)
1450         : m_lastFloat(0)
1451         , m_endLine(0)
1452         , m_floatIndex(0)
1453         , m_endLineLogicalTop(0)
1454         , m_endLineMatched(false)
1455         , m_checkForFloatsFromLastLine(false)
1456         , m_isFullLayout(fullLayout)
1457         , m_repaintLogicalTop(repaintLogicalTop)
1458         , m_repaintLogicalBottom(repaintLogicalBottom)
1459         , m_usesRepaintBounds(false)
1460         , m_flowThread(flowThread)
1461     { }
1462
1463     void markForFullLayout() { m_isFullLayout = true; }
1464     bool isFullLayout() const { return m_isFullLayout; }
1465
1466     bool usesRepaintBounds() const { return m_usesRepaintBounds; }
1467
1468     void setRepaintRange(LayoutUnit logicalHeight)
1469     { 
1470         m_usesRepaintBounds = true;
1471         m_repaintLogicalTop = m_repaintLogicalBottom = logicalHeight; 
1472     }
1473     
1474     void updateRepaintRangeFromBox(RootInlineBox* box, LayoutUnit paginationDelta = 0)
1475     {
1476         m_usesRepaintBounds = true;
1477         m_repaintLogicalTop = min(m_repaintLogicalTop, box->logicalTopVisualOverflow() + min<LayoutUnit>(paginationDelta, 0));
1478         m_repaintLogicalBottom = max(m_repaintLogicalBottom, box->logicalBottomVisualOverflow() + max<LayoutUnit>(paginationDelta, 0));
1479     }
1480     
1481     bool endLineMatched() const { return m_endLineMatched; }
1482     void setEndLineMatched(bool endLineMatched) { m_endLineMatched = endLineMatched; }
1483
1484     bool checkForFloatsFromLastLine() const { return m_checkForFloatsFromLastLine; }
1485     void setCheckForFloatsFromLastLine(bool check) { m_checkForFloatsFromLastLine = check; }
1486
1487     LineInfo& lineInfo() { return m_lineInfo; }
1488     const LineInfo& lineInfo() const { return m_lineInfo; }
1489
1490     LayoutUnit endLineLogicalTop() const { return m_endLineLogicalTop; }
1491     void setEndLineLogicalTop(LayoutUnit logicalTop) { m_endLineLogicalTop = logicalTop; }
1492
1493     RootInlineBox* endLine() const { return m_endLine; }
1494     void setEndLine(RootInlineBox* line) { m_endLine = line; }
1495
1496     RenderBlock::FloatingObject* lastFloat() const { return m_lastFloat; }
1497     void setLastFloat(RenderBlock::FloatingObject* lastFloat) { m_lastFloat = lastFloat; }
1498
1499     Vector<RenderBlock::FloatWithRect>& floats() { return m_floats; }
1500     
1501     unsigned floatIndex() const { return m_floatIndex; }
1502     void setFloatIndex(unsigned floatIndex) { m_floatIndex = floatIndex; }
1503     
1504     RenderFlowThread* flowThread() const { return m_flowThread; }
1505     void setFlowThread(RenderFlowThread* thread) { m_flowThread = thread; }
1506
1507 private:
1508     Vector<RenderBlock::FloatWithRect> m_floats;
1509     RenderBlock::FloatingObject* m_lastFloat;
1510     RootInlineBox* m_endLine;
1511     LineInfo m_lineInfo;
1512     unsigned m_floatIndex;
1513     LayoutUnit m_endLineLogicalTop;
1514     bool m_endLineMatched;
1515     bool m_checkForFloatsFromLastLine;
1516     
1517     bool m_isFullLayout;
1518
1519     // FIXME: Should this be a range object instead of two ints?
1520     LayoutUnit& m_repaintLogicalTop;
1521     LayoutUnit& m_repaintLogicalBottom;
1522
1523     bool m_usesRepaintBounds;
1524     
1525     RenderFlowThread* m_flowThread;
1526 };
1527
1528 static void deleteLineRange(LineLayoutState& layoutState, RenderArena* arena, RootInlineBox* startLine, RootInlineBox* stopLine = 0)
1529 {
1530     RootInlineBox* boxToDelete = startLine;
1531     while (boxToDelete && boxToDelete != stopLine) {
1532         layoutState.updateRepaintRangeFromBox(boxToDelete);
1533         // Note: deleteLineRange(renderArena(), firstRootBox()) is not identical to deleteLineBoxTree().
1534         // deleteLineBoxTree uses nextLineBox() instead of nextRootBox() when traversing.
1535         RootInlineBox* next = boxToDelete->nextRootBox();
1536         boxToDelete->deleteLine(arena);
1537         boxToDelete = next;
1538     }
1539 }
1540
1541 void RenderBlock::layoutRunsAndFloats(LineLayoutState& layoutState, bool hasInlineChild)
1542 {
1543     // We want to skip ahead to the first dirty line
1544     InlineBidiResolver resolver;
1545     RootInlineBox* startLine = determineStartPosition(layoutState, resolver);
1546
1547     unsigned consecutiveHyphenatedLines = 0;
1548     if (startLine) {
1549         for (RootInlineBox* line = startLine->prevRootBox(); line && line->isHyphenated(); line = line->prevRootBox())
1550             consecutiveHyphenatedLines++;
1551     }
1552
1553     // FIXME: This would make more sense outside of this function, but since
1554     // determineStartPosition can change the fullLayout flag we have to do this here. Failure to call
1555     // determineStartPosition first will break fast/repaint/line-flow-with-floats-9.html.
1556     if (layoutState.isFullLayout() && hasInlineChild && !selfNeedsLayout()) {
1557         setNeedsLayout(true, MarkOnlyThis); // Mark as needing a full layout to force us to repaint.
1558         RenderView* v = view();
1559         if (v && !v->doingFullRepaint() && hasLayer()) {
1560             // Because we waited until we were already inside layout to discover
1561             // that the block really needed a full layout, we missed our chance to repaint the layer
1562             // before layout started.  Luckily the layer has cached the repaint rect for its original
1563             // position and size, and so we can use that to make a repaint happen now.
1564             repaintUsingContainer(containerForRepaint(), pixelSnappedIntRect(layer()->repaintRect()));
1565         }
1566     }
1567
1568     if (containsFloats())
1569         layoutState.setLastFloat(m_floatingObjects->set().last());
1570
1571     // We also find the first clean line and extract these lines.  We will add them back
1572     // if we determine that we're able to synchronize after handling all our dirty lines.
1573     InlineIterator cleanLineStart;
1574     BidiStatus cleanLineBidiStatus;
1575     if (!layoutState.isFullLayout() && startLine)
1576         determineEndPosition(layoutState, startLine, cleanLineStart, cleanLineBidiStatus);
1577
1578     if (startLine) {
1579         if (!layoutState.usesRepaintBounds())
1580             layoutState.setRepaintRange(logicalHeight());
1581         deleteLineRange(layoutState, renderArena(), startLine);
1582     }
1583
1584     if (!layoutState.isFullLayout() && lastRootBox() && lastRootBox()->endsWithBreak()) {
1585         // If the last line before the start line ends with a line break that clear floats,
1586         // adjust the height accordingly.
1587         // A line break can be either the first or the last object on a line, depending on its direction.
1588         if (InlineBox* lastLeafChild = lastRootBox()->lastLeafChild()) {
1589             RenderObject* lastObject = lastLeafChild->renderer();
1590             if (!lastObject->isBR())
1591                 lastObject = lastRootBox()->firstLeafChild()->renderer();
1592             if (lastObject->isBR()) {
1593                 EClear clear = lastObject->style()->clear();
1594                 if (clear != CNONE)
1595                     newLine(clear);
1596             }
1597         }
1598     }
1599
1600     layoutRunsAndFloatsInRange(layoutState, resolver, cleanLineStart, cleanLineBidiStatus, consecutiveHyphenatedLines);
1601     linkToEndLineIfNeeded(layoutState);
1602     repaintDirtyFloats(layoutState.floats());
1603 }
1604
1605 RenderBlock::RenderTextInfo::RenderTextInfo()
1606     : m_text(0)
1607     , m_font(0)
1608 {
1609 }
1610
1611 RenderBlock::RenderTextInfo::~RenderTextInfo()
1612 {
1613 }
1614
1615 // Before restarting the layout loop with a new logicalHeight, remove all floats that were added and reset the resolver.
1616 inline const InlineIterator& RenderBlock::restartLayoutRunsAndFloatsInRange(LayoutUnit oldLogicalHeight, LayoutUnit newLogicalHeight,  FloatingObject* lastFloatFromPreviousLine, InlineBidiResolver& resolver,  const InlineIterator& oldEnd)
1617 {
1618     removeFloatingObjectsBelow(lastFloatFromPreviousLine, oldLogicalHeight);
1619     setLogicalHeight(newLogicalHeight);
1620     resolver.setPositionIgnoringNestedIsolates(oldEnd);
1621     return oldEnd;
1622 }
1623
1624 #if ENABLE(CSS_SHAPES)
1625 static inline float firstPositiveWidth(const WordMeasurements& wordMeasurements)
1626 {
1627     for (size_t i = 0; i < wordMeasurements.size(); ++i) {
1628         if (wordMeasurements[i].width > 0)
1629             return wordMeasurements[i].width;
1630     }
1631     return 0;
1632 }
1633
1634 static inline LayoutUnit adjustLogicalLineTop(ExclusionShapeInsideInfo* exclusionShapeInsideInfo, InlineIterator start, InlineIterator end, const WordMeasurements& wordMeasurements)
1635 {
1636     if (!exclusionShapeInsideInfo || end != start)
1637         return 0;
1638
1639     float minWidth = firstPositiveWidth(wordMeasurements);
1640     ASSERT(minWidth || wordMeasurements.isEmpty());
1641     if (minWidth > 0 && exclusionShapeInsideInfo->adjustLogicalLineTop(minWidth))
1642         return exclusionShapeInsideInfo->logicalLineTop();
1643
1644     return exclusionShapeInsideInfo->shapeLogicalBottom();
1645 }
1646
1647 void RenderBlock::updateShapeAndSegmentsForCurrentLine(ExclusionShapeInsideInfo* exclusionShapeInsideInfo, LayoutUnit& absoluteLogicalTop, LineLayoutState& layoutState, bool& lineOverflowsFromShapeInside)
1648 {
1649     LayoutUnit logicalHeight = this->logicalHeight();
1650     RenderRegion* currentRegion = regionAtBlockOffset(logicalHeight);
1651     if (currentRegion)
1652         exclusionShapeInsideInfo = layoutExclusionShapeInsideInfo();
1653     if (!exclusionShapeInsideInfo)
1654         return;
1655
1656     LayoutUnit lineTop = logicalHeight + absoluteLogicalTop;
1657     LayoutUnit lineHeight = this->lineHeight(layoutState.lineInfo().isFirstLine(), isHorizontalWritingMode() ? HorizontalLine : VerticalLine, PositionOfInteriorLineBoxes);
1658
1659     if (layoutState.flowThread()) {
1660         RenderRegion* nextRegion = regionAtBlockOffset(logicalHeight + lineHeight - LayoutUnit(1));
1661         lineTop += exclusionShapeInsideInfo->owner()->borderAndPaddingBefore();
1662         // Content in a flow thread is relative to the beginning of the thread, but the shape calculation should be relative to the current region.
1663         if (currentRegion == nextRegion)
1664             lineTop -= currentRegion->logicalTopForFlowThreadContent();
1665     }
1666
1667     // FIXME: Bug 95361: It is possible for a line to grow beyond lineHeight, in which case these segments may be incorrect.
1668     exclusionShapeInsideInfo->computeSegmentsForLine(lineTop, lineHeight);
1669
1670     // The overflow should be pushed below the content box
1671     LayoutUnit shapeContainingBlockHeight = exclusionShapeInsideInfo->shapeContainingBlockHeight();
1672     if (!exclusionShapeInsideInfo->lineWithinShapeBounds() && !lineOverflowsFromShapeInside && shapeContainingBlockHeight) {
1673         lineOverflowsFromShapeInside = true;
1674         LayoutUnit newLogicalHeight = shapeContainingBlockHeight;
1675
1676         if (layoutState.flowThread()) {
1677             // If block contents flown across multiple regions and the shape-inside was applied on the second region we can end up with negative lineTop
1678             if (lineTop < 0)
1679                 return;
1680
1681             newLogicalHeight = logicalHeight + shapeContainingBlockHeight - lineTop - currentRegion->borderAndPaddingBefore();
1682
1683             RenderRegion* nextRegion = regionAtBlockOffset(newLogicalHeight);
1684             ExclusionShapeInsideInfo* nextShapeInfo = 0;
1685             if (nextRegion)
1686                 nextShapeInfo = nextRegion->exclusionShapeInsideInfo();
1687
1688             // The overflow flows into another region with shape-inside
1689             if (currentRegion != nextRegion && nextShapeInfo) {
1690                 newLogicalHeight += nextShapeInfo->shapeLogicalTop() - nextRegion->borderAndPaddingBefore();
1691
1692                 LayoutUnit offset = nextShapeInfo->shapeLogicalTop() - nextRegion->borderAndPaddingBefore();
1693                 nextShapeInfo->computeSegmentsForLine(offset, lineHeight);
1694
1695                 exclusionShapeInsideInfo = nextShapeInfo;
1696                 lineOverflowsFromShapeInside = false;
1697             }
1698         }
1699         setLogicalHeight(newLogicalHeight);
1700     }
1701 }
1702
1703 bool RenderBlock::adjustLogicalLineTopAndLogicalHeightIfNeeded(ExclusionShapeInsideInfo* exclusionShapeInsideInfo, LayoutUnit absoluteLogicalTop, LineLayoutState& layoutState, InlineBidiResolver& resolver, FloatingObject* lastFloatFromPreviousLine, InlineIterator& end, WordMeasurements& wordMeasurements)
1704 {
1705     LayoutUnit adjustedLogicalLineTop = adjustLogicalLineTop(exclusionShapeInsideInfo, resolver.position(), end, wordMeasurements);
1706     if (!adjustedLogicalLineTop)
1707         return false;
1708
1709     LayoutUnit newLogicalHeight = adjustedLogicalLineTop - absoluteLogicalTop;
1710     if (layoutState.flowThread())
1711         newLogicalHeight = logicalHeight();
1712
1713     end = restartLayoutRunsAndFloatsInRange(logicalHeight(), newLogicalHeight, lastFloatFromPreviousLine, resolver, end);
1714     return true;
1715 }
1716 #endif
1717
1718 void RenderBlock::layoutRunsAndFloatsInRange(LineLayoutState& layoutState, InlineBidiResolver& resolver, const InlineIterator& cleanLineStart, const BidiStatus& cleanLineBidiStatus, unsigned consecutiveHyphenatedLines)
1719 {
1720     RenderStyle* styleToUse = style();
1721     bool paginated = view()->layoutState() && view()->layoutState()->isPaginated();
1722     LineMidpointState& lineMidpointState = resolver.midpointState();
1723     InlineIterator end = resolver.position();
1724     bool checkForEndLineMatch = layoutState.endLine();
1725     RenderTextInfo renderTextInfo;
1726     VerticalPositionCache verticalPositionCache;
1727
1728     LineBreaker lineBreaker(this);
1729
1730 #if ENABLE(CSS_SHAPES)
1731     LayoutUnit absoluteLogicalTop;
1732     ExclusionShapeInsideInfo* exclusionShapeInsideInfo = layoutExclusionShapeInsideInfo();
1733     if (exclusionShapeInsideInfo) {
1734         ASSERT(exclusionShapeInsideInfo->owner() == this || allowsExclusionShapeInsideInfoSharing());
1735         if (exclusionShapeInsideInfo != this->exclusionShapeInsideInfo()) {
1736             // FIXME Bug 100284: If subsequent LayoutStates are pushed, we will have to add
1737             // their offsets from the original shape-inside container.
1738             absoluteLogicalTop = logicalTop();
1739         }
1740         // Begin layout at the logical top of our shape inside.
1741         if (logicalHeight() + absoluteLogicalTop < exclusionShapeInsideInfo->shapeLogicalTop()) {
1742             LayoutUnit logicalHeight = exclusionShapeInsideInfo->shapeLogicalTop() - absoluteLogicalTop;
1743             if (layoutState.flowThread())
1744                 logicalHeight -= exclusionShapeInsideInfo->owner()->borderAndPaddingBefore();
1745             setLogicalHeight(logicalHeight);
1746         }
1747     }
1748
1749     bool lineOverflowsFromShapeInside = false;
1750 #endif
1751
1752     while (!end.atEnd()) {
1753         // FIXME: Is this check necessary before the first iteration or can it be moved to the end?
1754         if (checkForEndLineMatch) {
1755             layoutState.setEndLineMatched(matchedEndLine(layoutState, resolver, cleanLineStart, cleanLineBidiStatus));
1756             if (layoutState.endLineMatched()) {
1757                 resolver.setPosition(InlineIterator(resolver.position().root(), 0, 0), 0);
1758                 break;
1759             }
1760         }
1761
1762         lineMidpointState.reset();
1763
1764         layoutState.lineInfo().setEmpty(true);
1765         layoutState.lineInfo().resetRunsFromLeadingWhitespace();
1766
1767         const InlineIterator oldEnd = end;
1768         bool isNewUBAParagraph = layoutState.lineInfo().previousLineBrokeCleanly();
1769         FloatingObject* lastFloatFromPreviousLine = (containsFloats()) ? m_floatingObjects->set().last() : 0;
1770
1771 #if ENABLE(CSS_SHAPES)
1772         updateShapeAndSegmentsForCurrentLine(exclusionShapeInsideInfo, absoluteLogicalTop, layoutState, lineOverflowsFromShapeInside);
1773 #endif
1774         WordMeasurements wordMeasurements;
1775         end = lineBreaker.nextLineBreak(resolver, layoutState.lineInfo(), renderTextInfo, lastFloatFromPreviousLine, consecutiveHyphenatedLines, wordMeasurements);
1776         renderTextInfo.m_lineBreakIterator.resetPriorContext();
1777         if (resolver.position().atEnd()) {
1778             // FIXME: We shouldn't be creating any runs in nextLineBreak to begin with!
1779             // Once BidiRunList is separated from BidiResolver this will not be needed.
1780             resolver.runs().deleteRuns();
1781             resolver.markCurrentRunEmpty(); // FIXME: This can probably be replaced by an ASSERT (or just removed).
1782             layoutState.setCheckForFloatsFromLastLine(true);
1783             resolver.setPosition(InlineIterator(resolver.position().root(), 0, 0), 0);
1784             break;
1785         }
1786
1787 #if ENABLE(CSS_SHAPES)
1788         if (adjustLogicalLineTopAndLogicalHeightIfNeeded(exclusionShapeInsideInfo, absoluteLogicalTop, layoutState, resolver, lastFloatFromPreviousLine, end, wordMeasurements))
1789             continue;
1790 #endif
1791         ASSERT(end != resolver.position());
1792
1793         // This is a short-cut for empty lines.
1794         if (layoutState.lineInfo().isEmpty()) {
1795             if (lastRootBox())
1796                 lastRootBox()->setLineBreakInfo(end.m_obj, end.m_pos, resolver.status());
1797         } else {
1798             VisualDirectionOverride override = (styleToUse->rtlOrdering() == VisualOrder ? (styleToUse->direction() == LTR ? VisualLeftToRightOverride : VisualRightToLeftOverride) : NoVisualOverride);
1799
1800             if (isNewUBAParagraph && styleToUse->unicodeBidi() == Plaintext && !resolver.context()->parent()) {
1801                 TextDirection direction = styleToUse->direction();
1802                 determineDirectionality(direction, resolver.position());
1803                 resolver.setStatus(BidiStatus(direction, isOverride(styleToUse->unicodeBidi())));
1804             }
1805             // FIXME: This ownership is reversed. We should own the BidiRunList and pass it to createBidiRunsForLine.
1806             BidiRunList<BidiRun>& bidiRuns = resolver.runs();
1807             constructBidiRunsForLine(this, resolver, bidiRuns, end, override, layoutState.lineInfo().previousLineBrokeCleanly());
1808             ASSERT(resolver.position() == end);
1809
1810             BidiRun* trailingSpaceRun = !layoutState.lineInfo().previousLineBrokeCleanly() ? handleTrailingSpaces(bidiRuns, resolver.context()) : 0;
1811
1812             if (bidiRuns.runCount() && lineBreaker.lineWasHyphenated()) {
1813                 bidiRuns.logicallyLastRun()->m_hasHyphen = true;
1814                 consecutiveHyphenatedLines++;
1815             } else
1816                 consecutiveHyphenatedLines = 0;
1817
1818             // Now that the runs have been ordered, we create the line boxes.
1819             // At the same time we figure out where border/padding/margin should be applied for
1820             // inline flow boxes.
1821
1822             LayoutUnit oldLogicalHeight = logicalHeight();
1823             RootInlineBox* lineBox = createLineBoxesFromBidiRuns(bidiRuns, end, layoutState.lineInfo(), verticalPositionCache, trailingSpaceRun, wordMeasurements);
1824
1825             bidiRuns.deleteRuns();
1826             resolver.markCurrentRunEmpty(); // FIXME: This can probably be replaced by an ASSERT (or just removed).
1827
1828             if (lineBox) {
1829                 lineBox->setLineBreakInfo(end.m_obj, end.m_pos, resolver.status());
1830                 if (layoutState.usesRepaintBounds())
1831                     layoutState.updateRepaintRangeFromBox(lineBox);
1832
1833                 if (paginated) {
1834                     LayoutUnit adjustment = 0;
1835                     adjustLinePositionForPagination(lineBox, adjustment, layoutState.flowThread());
1836                     if (adjustment) {
1837                         LayoutUnit oldLineWidth = availableLogicalWidthForLine(oldLogicalHeight, layoutState.lineInfo().isFirstLine());
1838                         lineBox->adjustBlockDirectionPosition(adjustment);
1839                         if (layoutState.usesRepaintBounds())
1840                             layoutState.updateRepaintRangeFromBox(lineBox);
1841
1842                         if (availableLogicalWidthForLine(oldLogicalHeight + adjustment, layoutState.lineInfo().isFirstLine()) != oldLineWidth) {
1843                             // We have to delete this line, remove all floats that got added, and let line layout re-run.
1844                             lineBox->deleteLine(renderArena());
1845                             end = restartLayoutRunsAndFloatsInRange(oldLogicalHeight, oldLogicalHeight + adjustment, lastFloatFromPreviousLine, resolver, oldEnd);
1846                             continue;
1847                         }
1848
1849                         setLogicalHeight(lineBox->lineBottomWithLeading());
1850                     }
1851
1852                     if (layoutState.flowThread())
1853                         lineBox->setContainingRegion(regionAtBlockOffset(lineBox->lineTopWithLeading()));
1854                 }
1855             }
1856         }
1857
1858         for (size_t i = 0; i < lineBreaker.positionedObjects().size(); ++i)
1859             setStaticPositions(this, lineBreaker.positionedObjects()[i]);
1860
1861         if (!layoutState.lineInfo().isEmpty()) {
1862             layoutState.lineInfo().setFirstLine(false);
1863             newLine(lineBreaker.clear());
1864         }
1865
1866         if (m_floatingObjects && lastRootBox()) {
1867             const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1868             FloatingObjectSetIterator it = floatingObjectSet.begin();
1869             FloatingObjectSetIterator end = floatingObjectSet.end();
1870             if (layoutState.lastFloat()) {
1871                 FloatingObjectSetIterator lastFloatIterator = floatingObjectSet.find(layoutState.lastFloat());
1872                 ASSERT(lastFloatIterator != end);
1873                 ++lastFloatIterator;
1874                 it = lastFloatIterator;
1875             }
1876             for (; it != end; ++it) {
1877                 FloatingObject* f = *it;
1878                 appendFloatingObjectToLastLine(f);
1879                 ASSERT(f->m_renderer == layoutState.floats()[layoutState.floatIndex()].object);
1880                 // If a float's geometry has changed, give up on syncing with clean lines.
1881                 if (layoutState.floats()[layoutState.floatIndex()].rect != f->frameRect())
1882                     checkForEndLineMatch = false;
1883                 layoutState.setFloatIndex(layoutState.floatIndex() + 1);
1884             }
1885             layoutState.setLastFloat(!floatingObjectSet.isEmpty() ? floatingObjectSet.last() : 0);
1886         }
1887
1888         lineMidpointState.reset();
1889         resolver.setPosition(end, numberOfIsolateAncestors(end));
1890     }
1891
1892     if (paginated && !style()->hasAutoWidows()) {
1893         // Check the line boxes to make sure we didn't create unacceptable widows.
1894         // However, we'll prioritize orphans - so nothing we do here should create
1895         // a new orphan.
1896
1897         RootInlineBox* lineBox = lastRootBox();
1898
1899         // Count from the end of the block backwards, to see how many hanging
1900         // lines we have.
1901         RootInlineBox* firstLineInBlock = firstRootBox();
1902         int numLinesHanging = 1;
1903         while (lineBox && lineBox != firstLineInBlock && !lineBox->isFirstAfterPageBreak()) {
1904             ++numLinesHanging;
1905             lineBox = lineBox->prevRootBox();
1906         }
1907
1908         // If there were no breaks in the block, we didn't create any widows.
1909         if (!lineBox || !lineBox->isFirstAfterPageBreak() || lineBox == firstLineInBlock)
1910             return;
1911
1912         if (numLinesHanging < style()->widows()) {
1913             // We have detected a widow. Now we need to work out how many
1914             // lines there are on the previous page, and how many we need
1915             // to steal.
1916             int numLinesNeeded = style()->widows() - numLinesHanging;
1917             RootInlineBox* currentFirstLineOfNewPage = lineBox;
1918
1919             // Count the number of lines in the previous page.
1920             lineBox = lineBox->prevRootBox();
1921             int numLinesInPreviousPage = 1;
1922             while (lineBox && lineBox != firstLineInBlock && !lineBox->isFirstAfterPageBreak()) {
1923                 ++numLinesInPreviousPage;
1924                 lineBox = lineBox->prevRootBox();
1925             }
1926
1927             // If there was an explicit value for orphans, respect that. If not, we still
1928             // shouldn't create a situation where we make an orphan bigger than the initial value.
1929             // This means that setting widows implies we also care about orphans, but given
1930             // the specification says the initial orphan value is non-zero, this is ok. The
1931             // author is always free to set orphans explicitly as well.
1932             int orphans = style()->hasAutoOrphans() ? style()->initialOrphans() : style()->orphans();
1933             int numLinesAvailable = numLinesInPreviousPage - orphans;
1934             if (numLinesAvailable <= 0)
1935                 return;
1936
1937             int numLinesToTake = min(numLinesAvailable, numLinesNeeded);
1938             // Wind back from our first widowed line.
1939             lineBox = currentFirstLineOfNewPage;
1940             for (int i = 0; i < numLinesToTake; ++i)
1941                 lineBox = lineBox->prevRootBox();
1942
1943             // We now want to break at this line. Remember for next layout and trigger relayout.
1944             setBreakAtLineToAvoidWidow(lineBox);
1945             markLinesDirtyInBlockRange(lastRootBox()->lineBottomWithLeading(), lineBox->lineBottomWithLeading(), lineBox);
1946         }
1947     }
1948 }
1949
1950 void RenderBlock::linkToEndLineIfNeeded(LineLayoutState& layoutState)
1951 {
1952     if (layoutState.endLine()) {
1953         if (layoutState.endLineMatched()) {
1954             bool paginated = view()->layoutState() && view()->layoutState()->isPaginated();
1955             // Attach all the remaining lines, and then adjust their y-positions as needed.
1956             LayoutUnit delta = logicalHeight() - layoutState.endLineLogicalTop();
1957             for (RootInlineBox* line = layoutState.endLine(); line; line = line->nextRootBox()) {
1958                 line->attachLine();
1959                 if (paginated) {
1960                     delta -= line->paginationStrut();
1961                     adjustLinePositionForPagination(line, delta, layoutState.flowThread());
1962                 }
1963                 if (delta) {
1964                     layoutState.updateRepaintRangeFromBox(line, delta);
1965                     line->adjustBlockDirectionPosition(delta);
1966                 }
1967                 if (layoutState.flowThread())
1968                     line->setContainingRegion(regionAtBlockOffset(line->lineTopWithLeading()));
1969                 if (Vector<RenderBox*>* cleanLineFloats = line->floatsPtr()) {
1970                     Vector<RenderBox*>::iterator end = cleanLineFloats->end();
1971                     for (Vector<RenderBox*>::iterator f = cleanLineFloats->begin(); f != end; ++f) {
1972                         FloatingObject* floatingObject = insertFloatingObject(*f);
1973                         ASSERT(!floatingObject->m_originatingLine);
1974                         floatingObject->m_originatingLine = line;
1975                         setLogicalHeight(logicalTopForChild(*f) - marginBeforeForChild(*f) + delta);
1976                         positionNewFloats();
1977                     }
1978                 }
1979             }
1980             setLogicalHeight(lastRootBox()->lineBottomWithLeading());
1981         } else {
1982             // Delete all the remaining lines.
1983             deleteLineRange(layoutState, renderArena(), layoutState.endLine());
1984         }
1985     }
1986     
1987     if (m_floatingObjects && (layoutState.checkForFloatsFromLastLine() || positionNewFloats()) && lastRootBox()) {
1988         // In case we have a float on the last line, it might not be positioned up to now.
1989         // This has to be done before adding in the bottom border/padding, or the float will
1990         // include the padding incorrectly. -dwh
1991         if (layoutState.checkForFloatsFromLastLine()) {
1992             LayoutUnit bottomVisualOverflow = lastRootBox()->logicalBottomVisualOverflow();
1993             LayoutUnit bottomLayoutOverflow = lastRootBox()->logicalBottomLayoutOverflow();
1994             TrailingFloatsRootInlineBox* trailingFloatsLineBox = new (renderArena()) TrailingFloatsRootInlineBox(this);
1995             m_lineBoxes.appendLineBox(trailingFloatsLineBox);
1996             trailingFloatsLineBox->setConstructed();
1997             GlyphOverflowAndFallbackFontsMap textBoxDataMap;
1998             VerticalPositionCache verticalPositionCache;
1999             LayoutUnit blockLogicalHeight = logicalHeight();
2000             trailingFloatsLineBox->alignBoxesInBlockDirection(blockLogicalHeight, textBoxDataMap, verticalPositionCache);
2001             trailingFloatsLineBox->setLineTopBottomPositions(blockLogicalHeight, blockLogicalHeight, blockLogicalHeight, blockLogicalHeight);
2002             trailingFloatsLineBox->setPaginatedLineWidth(availableLogicalWidthForContent(blockLogicalHeight));
2003             LayoutRect logicalLayoutOverflow(0, blockLogicalHeight, 1, bottomLayoutOverflow - blockLogicalHeight);
2004             LayoutRect logicalVisualOverflow(0, blockLogicalHeight, 1, bottomVisualOverflow - blockLogicalHeight);
2005             trailingFloatsLineBox->setOverflowFromLogicalRects(logicalLayoutOverflow, logicalVisualOverflow, trailingFloatsLineBox->lineTop(), trailingFloatsLineBox->lineBottom());
2006             if (layoutState.flowThread())
2007                 trailingFloatsLineBox->setContainingRegion(regionAtBlockOffset(trailingFloatsLineBox->lineTopWithLeading()));
2008         }
2009
2010         const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2011         FloatingObjectSetIterator it = floatingObjectSet.begin();
2012         FloatingObjectSetIterator end = floatingObjectSet.end();
2013         if (layoutState.lastFloat()) {
2014             FloatingObjectSetIterator lastFloatIterator = floatingObjectSet.find(layoutState.lastFloat());
2015             ASSERT(lastFloatIterator != end);
2016             ++lastFloatIterator;
2017             it = lastFloatIterator;
2018         }
2019         for (; it != end; ++it)
2020             appendFloatingObjectToLastLine(*it);
2021         layoutState.setLastFloat(!floatingObjectSet.isEmpty() ? floatingObjectSet.last() : 0);
2022     }
2023 }
2024
2025 void RenderBlock::repaintDirtyFloats(Vector<FloatWithRect>& floats)
2026 {
2027     size_t floatCount = floats.size();
2028     // Floats that did not have layout did not repaint when we laid them out. They would have
2029     // painted by now if they had moved, but if they stayed at (0, 0), they still need to be
2030     // painted.
2031     for (size_t i = 0; i < floatCount; ++i) {
2032         if (!floats[i].everHadLayout) {
2033             RenderBox* f = floats[i].object;
2034             if (!f->x() && !f->y() && f->checkForRepaintDuringLayout())
2035                 f->repaint();
2036         }
2037     }
2038 }
2039
2040 void RenderBlock::layoutInlineChildren(bool relayoutChildren, LayoutUnit& repaintLogicalTop, LayoutUnit& repaintLogicalBottom)
2041 {
2042     setLogicalHeight(borderBefore() + paddingBefore());
2043     
2044     // Lay out our hypothetical grid line as though it occurs at the top of the block.
2045     if (view()->layoutState() && view()->layoutState()->lineGrid() == this)
2046         layoutLineGridBox();
2047
2048     RenderFlowThread* flowThread = flowThreadContainingBlock();
2049     bool clearLinesForPagination = firstLineBox() && flowThread && !flowThread->hasRegions();
2050
2051     // Figure out if we should clear out our line boxes.
2052     // FIXME: Handle resize eventually!
2053     bool isFullLayout = !firstLineBox() || selfNeedsLayout() || relayoutChildren || clearLinesForPagination;
2054     LineLayoutState layoutState(isFullLayout, repaintLogicalTop, repaintLogicalBottom, flowThread);
2055
2056     if (isFullLayout)
2057         lineBoxes()->deleteLineBoxes(renderArena());
2058
2059     // Text truncation kicks in in two cases:
2060     //     1) If your overflow isn't visible and your text-overflow-mode isn't clip.
2061     //     2) If you're an anonymous block with a block parent that satisfies #1.
2062     // FIXME: CSS3 says that descendants that are clipped must also know how to truncate.  This is insanely
2063     // difficult to figure out in general (especially in the middle of doing layout), so we only handle the
2064     // simple case of an anonymous block truncating when it's parent is clipped.
2065     bool hasTextOverflow = (style()->textOverflow() && hasOverflowClip())
2066         || (isAnonymousBlock() && parent() && parent()->isRenderBlock() && parent()->style()->textOverflow() && parent()->hasOverflowClip());
2067
2068     // Walk all the lines and delete our ellipsis line boxes if they exist.
2069     if (hasTextOverflow)
2070          deleteEllipsisLineBoxes();
2071
2072     if (firstChild()) {
2073         // In full layout mode, clear the line boxes of children upfront. Otherwise,
2074         // siblings can run into stale root lineboxes during layout. Then layout
2075         // the replaced elements later. In partial layout mode, line boxes are not
2076         // deleted and only dirtied. In that case, we can layout the replaced
2077         // elements at the same time.
2078         bool hasInlineChild = false;
2079         Vector<RenderBox*> replacedChildren;
2080         for (InlineWalker walker(this); !walker.atEnd(); walker.advance()) {
2081             RenderObject* o = walker.current();
2082             if (!hasInlineChild && o->isInline())
2083                 hasInlineChild = true;
2084
2085             if (o->isReplaced() || o->isFloating() || o->isOutOfFlowPositioned()) {
2086                 RenderBox* box = toRenderBox(o);
2087
2088                 if (relayoutChildren || box->hasRelativeDimensions())
2089                     o->setChildNeedsLayout(true, MarkOnlyThis);
2090
2091                 // If relayoutChildren is set and the child has percentage padding or an embedded content box, we also need to invalidate the childs pref widths.
2092                 if (relayoutChildren && box->needsPreferredWidthsRecalculation())
2093                     o->setPreferredLogicalWidthsDirty(true, MarkOnlyThis);
2094
2095                 if (o->isOutOfFlowPositioned())
2096                     o->containingBlock()->insertPositionedObject(box);
2097                 else if (o->isFloating())
2098                     layoutState.floats().append(FloatWithRect(box));
2099                 else if (isFullLayout || o->needsLayout()) {
2100                     // Replaced element.
2101                     box->dirtyLineBoxes(isFullLayout);
2102                     if (isFullLayout)
2103                         replacedChildren.append(box);
2104                     else
2105                         o->layoutIfNeeded();
2106                 }
2107             } else if (o->isText() || (o->isRenderInline() && !walker.atEndOfInline())) {
2108                 if (!o->isText())
2109                     toRenderInline(o)->updateAlwaysCreateLineBoxes(layoutState.isFullLayout());
2110                 if (layoutState.isFullLayout() || o->selfNeedsLayout())
2111                     dirtyLineBoxesForRenderer(o, layoutState.isFullLayout());
2112                 o->setNeedsLayout(false);
2113             }
2114         }
2115
2116         for (size_t i = 0; i < replacedChildren.size(); i++)
2117              replacedChildren[i]->layoutIfNeeded();
2118
2119         layoutRunsAndFloats(layoutState, hasInlineChild);
2120     }
2121
2122     // Expand the last line to accommodate Ruby and emphasis marks.
2123     int lastLineAnnotationsAdjustment = 0;
2124     if (lastRootBox()) {
2125         LayoutUnit lowestAllowedPosition = max(lastRootBox()->lineBottom(), logicalHeight() + paddingAfter());
2126         if (!style()->isFlippedLinesWritingMode())
2127             lastLineAnnotationsAdjustment = lastRootBox()->computeUnderAnnotationAdjustment(lowestAllowedPosition);
2128         else
2129             lastLineAnnotationsAdjustment = lastRootBox()->computeOverAnnotationAdjustment(lowestAllowedPosition);
2130     }
2131
2132     // Now add in the bottom border/padding.
2133     setLogicalHeight(logicalHeight() + lastLineAnnotationsAdjustment + borderAfter() + paddingAfter() + scrollbarLogicalHeight());
2134
2135     if (!firstLineBox() && hasLineIfEmpty())
2136         setLogicalHeight(logicalHeight() + lineHeight(true, isHorizontalWritingMode() ? HorizontalLine : VerticalLine, PositionOfInteriorLineBoxes));
2137
2138     // See if we have any lines that spill out of our block.  If we do, then we will possibly need to
2139     // truncate text.
2140     if (hasTextOverflow)
2141         checkLinesForTextOverflow();
2142 }
2143
2144 void RenderBlock::checkFloatsInCleanLine(RootInlineBox* line, Vector<FloatWithRect>& floats, size_t& floatIndex, bool& encounteredNewFloat, bool& dirtiedByFloat)
2145 {
2146     Vector<RenderBox*>* cleanLineFloats = line->floatsPtr();
2147     if (!cleanLineFloats)
2148         return;
2149
2150     Vector<RenderBox*>::iterator end = cleanLineFloats->end();
2151     for (Vector<RenderBox*>::iterator it = cleanLineFloats->begin(); it != end; ++it) {
2152         RenderBox* floatingBox = *it;
2153         floatingBox->layoutIfNeeded();
2154         LayoutSize newSize(floatingBox->width() + floatingBox->marginWidth(), floatingBox->height() + floatingBox->marginHeight());
2155         ASSERT_WITH_SECURITY_IMPLICATION(floatIndex < floats.size());
2156         if (floats[floatIndex].object != floatingBox) {
2157             encounteredNewFloat = true;
2158             return;
2159         }
2160
2161         if (floats[floatIndex].rect.size() != newSize) {
2162             LayoutUnit floatTop = isHorizontalWritingMode() ? floats[floatIndex].rect.y() : floats[floatIndex].rect.x();
2163             LayoutUnit floatHeight = isHorizontalWritingMode() ? max(floats[floatIndex].rect.height(), newSize.height())
2164                                                                  : max(floats[floatIndex].rect.width(), newSize.width());
2165             floatHeight = min(floatHeight, LayoutUnit::max() - floatTop);
2166             line->markDirty();
2167             markLinesDirtyInBlockRange(line->lineBottomWithLeading(), floatTop + floatHeight, line);
2168             floats[floatIndex].rect.setSize(newSize);
2169             dirtiedByFloat = true;
2170         }
2171         floatIndex++;
2172     }
2173 }
2174
2175 RootInlineBox* RenderBlock::determineStartPosition(LineLayoutState& layoutState, InlineBidiResolver& resolver)
2176 {
2177     RootInlineBox* curr = 0;
2178     RootInlineBox* last = 0;
2179
2180     // FIXME: This entire float-checking block needs to be broken into a new function.
2181     bool dirtiedByFloat = false;
2182     if (!layoutState.isFullLayout()) {
2183         // Paginate all of the clean lines.
2184         bool paginated = view()->layoutState() && view()->layoutState()->isPaginated();
2185         LayoutUnit paginationDelta = 0;
2186         size_t floatIndex = 0;
2187         for (curr = firstRootBox(); curr && !curr->isDirty(); curr = curr->nextRootBox()) {
2188             if (paginated) {
2189                 if (lineWidthForPaginatedLineChanged(curr, 0, layoutState.flowThread())) {
2190                     curr->markDirty();
2191                     break;
2192                 }
2193                 paginationDelta -= curr->paginationStrut();
2194                 adjustLinePositionForPagination(curr, paginationDelta, layoutState.flowThread());
2195                 if (paginationDelta) {
2196                     if (containsFloats() || !layoutState.floats().isEmpty()) {
2197                         // FIXME: Do better eventually.  For now if we ever shift because of pagination and floats are present just go to a full layout.
2198                         layoutState.markForFullLayout();
2199                         break;
2200                     }
2201
2202                     layoutState.updateRepaintRangeFromBox(curr, paginationDelta);
2203                     curr->adjustBlockDirectionPosition(paginationDelta);
2204                 }
2205                 if (layoutState.flowThread())
2206                     curr->setContainingRegion(regionAtBlockOffset(curr->lineTopWithLeading()));
2207             }
2208
2209             // If a new float has been inserted before this line or before its last known float, just do a full layout.
2210             bool encounteredNewFloat = false;
2211             checkFloatsInCleanLine(curr, layoutState.floats(), floatIndex, encounteredNewFloat, dirtiedByFloat);
2212             if (encounteredNewFloat)
2213                 layoutState.markForFullLayout();
2214
2215             if (dirtiedByFloat || layoutState.isFullLayout())
2216                 break;
2217         }
2218         // Check if a new float has been inserted after the last known float.
2219         if (!curr && floatIndex < layoutState.floats().size())
2220             layoutState.markForFullLayout();
2221     }
2222
2223     if (layoutState.isFullLayout()) {
2224         m_lineBoxes.deleteLineBoxTree(renderArena());
2225         curr = 0;
2226
2227         ASSERT(!firstLineBox() && !lastLineBox());
2228     } else {
2229         if (curr) {
2230             // We have a dirty line.
2231             if (RootInlineBox* prevRootBox = curr->prevRootBox()) {
2232                 // We have a previous line.
2233                 if (!dirtiedByFloat && (!prevRootBox->endsWithBreak() || !prevRootBox->lineBreakObj() || (prevRootBox->lineBreakObj()->isText() && prevRootBox->lineBreakPos() >= toRenderText(prevRootBox->lineBreakObj())->textLength())))
2234                     // The previous line didn't break cleanly or broke at a newline
2235                     // that has been deleted, so treat it as dirty too.
2236                     curr = prevRootBox;
2237             }
2238         } else {
2239             // No dirty lines were found.
2240             // If the last line didn't break cleanly, treat it as dirty.
2241             if (lastRootBox() && !lastRootBox()->endsWithBreak())
2242                 curr = lastRootBox();
2243         }
2244
2245         // If we have no dirty lines, then last is just the last root box.
2246         last = curr ? curr->prevRootBox() : lastRootBox();
2247     }
2248
2249     unsigned numCleanFloats = 0;
2250     if (!layoutState.floats().isEmpty()) {
2251         LayoutUnit savedLogicalHeight = logicalHeight();
2252         // Restore floats from clean lines.
2253         RootInlineBox* line = firstRootBox();
2254         while (line != curr) {
2255             if (Vector<RenderBox*>* cleanLineFloats = line->floatsPtr()) {
2256                 Vector<RenderBox*>::iterator end = cleanLineFloats->end();
2257                 for (Vector<RenderBox*>::iterator f = cleanLineFloats->begin(); f != end; ++f) {
2258                     FloatingObject* floatingObject = insertFloatingObject(*f);
2259                     ASSERT(!floatingObject->m_originatingLine);
2260                     floatingObject->m_originatingLine = line;
2261                     setLogicalHeight(logicalTopForChild(*f) - marginBeforeForChild(*f));
2262                     positionNewFloats();
2263                     ASSERT(layoutState.floats()[numCleanFloats].object == *f);
2264                     numCleanFloats++;
2265                 }
2266             }
2267             line = line->nextRootBox();
2268         }
2269         setLogicalHeight(savedLogicalHeight);
2270     }
2271     layoutState.setFloatIndex(numCleanFloats);
2272
2273     layoutState.lineInfo().setFirstLine(!last);
2274     layoutState.lineInfo().setPreviousLineBrokeCleanly(!last || last->endsWithBreak());
2275
2276     if (last) {
2277         setLogicalHeight(last->lineBottomWithLeading());
2278         InlineIterator iter = InlineIterator(this, last->lineBreakObj(), last->lineBreakPos());
2279         resolver.setPosition(iter, numberOfIsolateAncestors(iter));
2280         resolver.setStatus(last->lineBreakBidiStatus());
2281     } else {
2282         TextDirection direction = style()->direction();
2283         if (style()->unicodeBidi() == Plaintext)
2284             determineDirectionality(direction, InlineIterator(this, bidiFirstSkippingEmptyInlines(this), 0));
2285         resolver.setStatus(BidiStatus(direction, isOverride(style()->unicodeBidi())));
2286         InlineIterator iter = InlineIterator(this, bidiFirstSkippingEmptyInlines(this, &resolver), 0);
2287         resolver.setPosition(iter, numberOfIsolateAncestors(iter));
2288     }
2289     return curr;
2290 }
2291
2292 void RenderBlock::determineEndPosition(LineLayoutState& layoutState, RootInlineBox* startLine, InlineIterator& cleanLineStart, BidiStatus& cleanLineBidiStatus)
2293 {
2294     ASSERT(!layoutState.endLine());
2295     size_t floatIndex = layoutState.floatIndex();
2296     RootInlineBox* last = 0;
2297     for (RootInlineBox* curr = startLine->nextRootBox(); curr; curr = curr->nextRootBox()) {
2298         if (!curr->isDirty()) {
2299             bool encounteredNewFloat = false;
2300             bool dirtiedByFloat = false;
2301             checkFloatsInCleanLine(curr, layoutState.floats(), floatIndex, encounteredNewFloat, dirtiedByFloat);
2302             if (encounteredNewFloat)
2303                 return;
2304         }
2305         if (curr->isDirty())
2306             last = 0;
2307         else if (!last)
2308             last = curr;
2309     }
2310
2311     if (!last)
2312         return;
2313
2314     // At this point, |last| is the first line in a run of clean lines that ends with the last line
2315     // in the block.
2316
2317     RootInlineBox* prev = last->prevRootBox();
2318     cleanLineStart = InlineIterator(this, prev->lineBreakObj(), prev->lineBreakPos());
2319     cleanLineBidiStatus = prev->lineBreakBidiStatus();
2320     layoutState.setEndLineLogicalTop(prev->lineBottomWithLeading());
2321
2322     for (RootInlineBox* line = last; line; line = line->nextRootBox())
2323         line->extractLine(); // Disconnect all line boxes from their render objects while preserving
2324                              // their connections to one another.
2325
2326     layoutState.setEndLine(last);
2327 }
2328
2329 bool RenderBlock::checkPaginationAndFloatsAtEndLine(LineLayoutState& layoutState)
2330 {
2331     LayoutUnit lineDelta = logicalHeight() - layoutState.endLineLogicalTop();
2332
2333     bool paginated = view()->layoutState() && view()->layoutState()->isPaginated();
2334     if (paginated && layoutState.flowThread()) {
2335         // Check all lines from here to the end, and see if the hypothetical new position for the lines will result
2336         // in a different available line width.
2337         for (RootInlineBox* lineBox = layoutState.endLine(); lineBox; lineBox = lineBox->nextRootBox()) {
2338             if (paginated) {
2339                 // This isn't the real move we're going to do, so don't update the line box's pagination
2340                 // strut yet.
2341                 LayoutUnit oldPaginationStrut = lineBox->paginationStrut();
2342                 lineDelta -= oldPaginationStrut;
2343                 adjustLinePositionForPagination(lineBox, lineDelta, layoutState.flowThread());
2344                 lineBox->setPaginationStrut(oldPaginationStrut);
2345             }
2346             if (lineWidthForPaginatedLineChanged(lineBox, lineDelta, layoutState.flowThread()))
2347                 return false;
2348         }
2349     }
2350     
2351     if (!lineDelta || !m_floatingObjects)
2352         return true;
2353     
2354     // See if any floats end in the range along which we want to shift the lines vertically.
2355     LayoutUnit logicalTop = min(logicalHeight(), layoutState.endLineLogicalTop());
2356
2357     RootInlineBox* lastLine = layoutState.endLine();
2358     while (RootInlineBox* nextLine = lastLine->nextRootBox())
2359         lastLine = nextLine;
2360
2361     LayoutUnit logicalBottom = lastLine->lineBottomWithLeading() + absoluteValue(lineDelta);
2362
2363     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2364     FloatingObjectSetIterator end = floatingObjectSet.end();
2365     for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
2366         FloatingObject* f = *it;
2367         if (logicalBottomForFloat(f) >= logicalTop && logicalBottomForFloat(f) < logicalBottom)
2368             return false;
2369     }
2370
2371     return true;
2372 }
2373
2374 bool RenderBlock::matchedEndLine(LineLayoutState& layoutState, const InlineBidiResolver& resolver, const InlineIterator& endLineStart, const BidiStatus& endLineStatus)
2375 {
2376     if (resolver.position() == endLineStart) {
2377         if (resolver.status() != endLineStatus)
2378             return false;
2379         return checkPaginationAndFloatsAtEndLine(layoutState);
2380     }
2381
2382     // The first clean line doesn't match, but we can check a handful of following lines to try
2383     // to match back up.
2384     static int numLines = 8; // The # of lines we're willing to match against.
2385     RootInlineBox* originalEndLine = layoutState.endLine();
2386     RootInlineBox* line = originalEndLine;
2387     for (int i = 0; i < numLines && line; i++, line = line->nextRootBox()) {
2388         if (line->lineBreakObj() == resolver.position().m_obj && line->lineBreakPos() == resolver.position().m_pos) {
2389             // We have a match.
2390             if (line->lineBreakBidiStatus() != resolver.status())
2391                 return false; // ...but the bidi state doesn't match.
2392             
2393             bool matched = false;
2394             RootInlineBox* result = line->nextRootBox();
2395             layoutState.setEndLine(result);
2396             if (result) {
2397                 layoutState.setEndLineLogicalTop(line->lineBottomWithLeading());
2398                 matched = checkPaginationAndFloatsAtEndLine(layoutState);
2399             }
2400
2401             // Now delete the lines that we failed to sync.
2402             deleteLineRange(layoutState, renderArena(), originalEndLine, result);
2403             return matched;
2404         }
2405     }
2406
2407     return false;
2408 }
2409
2410 static inline bool skipNonBreakingSpace(const InlineIterator& it, const LineInfo& lineInfo)
2411 {
2412     if (it.m_obj->style()->nbspMode() != SPACE || it.current() != noBreakSpace)
2413         return false;
2414
2415     // FIXME: This is bad.  It makes nbsp inconsistent with space and won't work correctly
2416     // with m_minWidth/m_maxWidth.
2417     // Do not skip a non-breaking space if it is the first character
2418     // on a line after a clean line break (or on the first line, since previousLineBrokeCleanly starts off
2419     // |true|).
2420     if (lineInfo.isEmpty() && lineInfo.previousLineBrokeCleanly())
2421         return false;
2422
2423     return true;
2424 }
2425
2426 enum WhitespacePosition { LeadingWhitespace, TrailingWhitespace };
2427 static inline bool shouldCollapseWhiteSpace(const RenderStyle* style, const LineInfo& lineInfo, WhitespacePosition whitespacePosition)
2428 {
2429     // CSS2 16.6.1
2430     // If a space (U+0020) at the beginning of a line has 'white-space' set to 'normal', 'nowrap', or 'pre-line', it is removed.
2431     // 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.
2432     // 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.
2433     return style->collapseWhiteSpace()
2434         || (whitespacePosition == TrailingWhitespace && style->whiteSpace() == PRE_WRAP && (!lineInfo.isEmpty() || !lineInfo.previousLineBrokeCleanly()));
2435 }
2436
2437 static bool requiresLineBoxForContent(RenderInline* flow, const LineInfo& lineInfo)
2438 {
2439     RenderObject* parent = flow->parent();
2440     if (flow->document()->inNoQuirksMode() 
2441         && (flow->style(lineInfo.isFirstLine())->lineHeight() != parent->style(lineInfo.isFirstLine())->lineHeight()
2442         || flow->style()->verticalAlign() != parent->style()->verticalAlign()
2443         || !parent->style()->font().fontMetrics().hasIdenticalAscentDescentAndLineGap(flow->style()->font().fontMetrics())))
2444         return true;
2445     return false;
2446 }
2447
2448 static bool hasInlineDirectionBordersPaddingOrMargin(RenderInline* flow)
2449 {
2450     // Where an empty inline is split across anonymous blocks we should only give lineboxes to the 'sides' of the
2451     // inline that have borders, padding or margin.
2452     bool shouldApplyStartBorderPaddingOrMargin = !flow->parent()->isAnonymousBlock() || !flow->isInlineElementContinuation();
2453     if (shouldApplyStartBorderPaddingOrMargin && (flow->borderStart() || flow->marginStart() || flow->paddingStart()))
2454         return true;
2455
2456     bool shouldApplyEndBorderPaddingOrMargin = !flow->parent()->isAnonymousBlock() || flow->isInlineElementContinuation() || !flow->inlineElementContinuation();
2457     return shouldApplyEndBorderPaddingOrMargin && (flow->borderEnd() || flow->marginEnd() || flow->paddingEnd());
2458 }
2459
2460 static bool alwaysRequiresLineBox(RenderObject* flow)
2461 {
2462     // FIXME: Right now, we only allow line boxes for inlines that are truly empty.
2463     // We need to fix this, though, because at the very least, inlines containing only
2464     // ignorable whitespace should should also have line boxes.
2465     return isEmptyInline(flow) && hasInlineDirectionBordersPaddingOrMargin(toRenderInline(flow));
2466 }
2467
2468 static bool requiresLineBox(const InlineIterator& it, const LineInfo& lineInfo = LineInfo(), WhitespacePosition whitespacePosition = LeadingWhitespace)
2469 {
2470     if (it.m_obj->isFloatingOrOutOfFlowPositioned())
2471         return false;
2472
2473     if (it.m_obj->isRenderInline() && !alwaysRequiresLineBox(it.m_obj) && !requiresLineBoxForContent(toRenderInline(it.m_obj), lineInfo))
2474         return false;
2475
2476     if (!shouldCollapseWhiteSpace(it.m_obj->style(), lineInfo, whitespacePosition) || it.m_obj->isBR())
2477         return true;
2478
2479     UChar current = it.current();
2480     bool notJustWhitespace = current != ' ' && current != '\t' && current != softHyphen && (current != '\n' || it.m_obj->preservesNewline()) && !skipNonBreakingSpace(it, lineInfo);
2481     return notJustWhitespace || isEmptyInline(it.m_obj);
2482 }
2483
2484 bool RenderBlock::generatesLineBoxesForInlineChild(RenderObject* inlineObj)
2485 {
2486     ASSERT(inlineObj->parent() == this);
2487
2488     InlineIterator it(this, inlineObj, 0);
2489     // FIXME: We should pass correct value for WhitespacePosition.
2490     while (!it.atEnd() && !requiresLineBox(it))
2491         it.increment();
2492
2493     return !it.atEnd();
2494 }
2495
2496 // FIXME: The entire concept of the skipTrailingWhitespace function is flawed, since we really need to be building
2497 // line boxes even for containers that may ultimately collapse away. Otherwise we'll never get positioned
2498 // elements quite right. In other words, we need to build this function's work into the normal line
2499 // object iteration process.
2500 // NB. this function will insert any floating elements that would otherwise
2501 // be skipped but it will not position them.
2502 void RenderBlock::LineBreaker::skipTrailingWhitespace(InlineIterator& iterator, const LineInfo& lineInfo)
2503 {
2504     while (!iterator.atEnd() && !requiresLineBox(iterator, lineInfo, TrailingWhitespace)) {
2505         RenderObject* object = iterator.m_obj;
2506         if (object->isOutOfFlowPositioned())
2507             setStaticPositions(m_block, toRenderBox(object));
2508         else if (object->isFloating())
2509             m_block->insertFloatingObject(toRenderBox(object));
2510         iterator.increment();
2511     }
2512 }
2513
2514 void RenderBlock::LineBreaker::skipLeadingWhitespace(InlineBidiResolver& resolver, LineInfo& lineInfo,
2515                                                      FloatingObject* lastFloatFromPreviousLine, LineWidth& width)
2516 {
2517     while (!resolver.position().atEnd() && !requiresLineBox(resolver.position(), lineInfo, LeadingWhitespace)) {
2518         RenderObject* object = resolver.position().m_obj;
2519         if (object->isOutOfFlowPositioned()) {
2520             setStaticPositions(m_block, toRenderBox(object));
2521             if (object->style()->isOriginalDisplayInlineType()) {
2522                 resolver.runs().addRun(createRun(0, 1, object, resolver));
2523                 lineInfo.incrementRunsFromLeadingWhitespace();
2524             }
2525         } else if (object->isFloating()) {
2526             // The top margin edge of a self-collapsing block that clears a float intrudes up into it by the height of the margin,
2527             // 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.
2528             LayoutUnit marginOffset = (!object->previousSibling() && m_block->isSelfCollapsingBlock() && m_block->style()->clear() && m_block->getClearDelta(m_block, LayoutUnit())) ? m_block->collapsedMarginBeforeForChild(m_block) : LayoutUnit();
2529             LayoutUnit oldLogicalHeight = m_block->logicalHeight();
2530             m_block->setLogicalHeight(oldLogicalHeight + marginOffset);
2531             m_block->positionNewFloatOnLine(m_block->insertFloatingObject(toRenderBox(object)), lastFloatFromPreviousLine, lineInfo, width);
2532             m_block->setLogicalHeight(oldLogicalHeight);
2533         } else if (object->isText() && object->style()->hasTextCombine() && object->isCombineText() && !toRenderCombineText(object)->isCombined()) {
2534             toRenderCombineText(object)->combineText();
2535             if (toRenderCombineText(object)->isCombined())
2536                 continue;
2537         }
2538         resolver.increment();
2539     }
2540     resolver.commitExplicitEmbedding();
2541 }
2542
2543 // This is currently just used for list markers and inline flows that have line boxes. Neither should
2544 // have an effect on whitespace at the start of the line.
2545 static bool shouldSkipWhitespaceAfterStartObject(RenderBlock* block, RenderObject* o, LineMidpointState& lineMidpointState)
2546 {
2547     RenderObject* next = bidiNextSkippingEmptyInlines(block, o);
2548     while (next && next->isFloatingOrOutOfFlowPositioned())
2549         next = bidiNextSkippingEmptyInlines(block, next);
2550
2551     if (next && !next->isBR() && next->isText() && toRenderText(next)->textLength() > 0) {
2552         RenderText* nextText = toRenderText(next);
2553         UChar nextChar = nextText->characterAt(0);
2554         if (nextText->style()->isCollapsibleWhiteSpace(nextChar)) {
2555             startIgnoringSpaces(lineMidpointState, InlineIterator(0, o, 0));
2556             return true;
2557         }
2558     }
2559
2560     return false;
2561 }
2562
2563 static ALWAYS_INLINE float textWidth(RenderText* text, unsigned from, unsigned len, const Font& font, float xPos, bool isFixedPitch, bool collapseWhiteSpace, HashSet<const SimpleFontData*>* fallbackFonts = 0, TextLayout* layout = 0)
2564 {
2565     GlyphOverflow glyphOverflow;
2566     if (isFixedPitch || (!from && len == text->textLength()) || text->style()->hasTextCombine())
2567         return text->width(from, len, font, xPos, fallbackFonts, &glyphOverflow);
2568
2569     if (layout)
2570         return Font::width(*layout, from, len, fallbackFonts);
2571
2572     TextRun run = RenderBlock::constructTextRun(text, font, text, from, len, text->style());
2573     run.setCharactersLength(text->textLength() - from);
2574     ASSERT(run.charactersLength() >= run.length());
2575
2576     run.setCharacterScanForCodePath(!text->canUseSimpleFontCodePath());
2577     run.setTabSize(!collapseWhiteSpace, text->style()->tabSize());
2578     run.setXPos(xPos);
2579     return font.width(run, fallbackFonts, &glyphOverflow);
2580 }
2581
2582 static void tryHyphenating(RenderText* text, const Font& font, const AtomicString& localeIdentifier, unsigned consecutiveHyphenatedLines, int consecutiveHyphenatedLinesLimit, int minimumPrefixLimit, int minimumSuffixLimit, unsigned lastSpace, unsigned pos, float xPos, int availableWidth, bool isFixedPitch, bool collapseWhiteSpace, int lastSpaceWordSpacing, InlineIterator& lineBreak, int nextBreakable, bool& hyphenated)
2583 {
2584     // Map 'hyphenate-limit-{before,after}: auto;' to 2.
2585     unsigned minimumPrefixLength;
2586     unsigned minimumSuffixLength;
2587
2588     if (minimumPrefixLimit < 0)
2589         minimumPrefixLength = 2;
2590     else
2591         minimumPrefixLength = static_cast<unsigned>(minimumPrefixLimit);
2592
2593     if (minimumSuffixLimit < 0)
2594         minimumSuffixLength = 2;
2595     else
2596         minimumSuffixLength = static_cast<unsigned>(minimumSuffixLimit);
2597
2598     if (pos - lastSpace <= minimumSuffixLength)
2599         return;
2600
2601     if (consecutiveHyphenatedLinesLimit >= 0 && consecutiveHyphenatedLines >= static_cast<unsigned>(consecutiveHyphenatedLinesLimit))
2602         return;
2603
2604     int hyphenWidth = measureHyphenWidth(text, font);
2605
2606     float maxPrefixWidth = availableWidth - xPos - hyphenWidth - lastSpaceWordSpacing;
2607     // If the maximum width available for the prefix before the hyphen is small, then it is very unlikely
2608     // that an hyphenation opportunity exists, so do not bother to look for it.
2609     if (maxPrefixWidth <= font.pixelSize() * 5 / 4)
2610         return;
2611
2612     TextRun run = RenderBlock::constructTextRun(text, font, text, lastSpace, pos - lastSpace, text->style());
2613     run.setCharactersLength(text->textLength() - lastSpace);
2614     ASSERT(run.charactersLength() >= run.length());
2615
2616     run.setTabSize(!collapseWhiteSpace, text->style()->tabSize());
2617     run.setXPos(xPos + lastSpaceWordSpacing);
2618
2619     unsigned prefixLength = font.offsetForPosition(run, maxPrefixWidth, false);
2620     if (prefixLength < minimumPrefixLength)
2621         return;
2622
2623     prefixLength = lastHyphenLocation(text->characters() + lastSpace, pos - lastSpace, min(prefixLength, pos - lastSpace - minimumSuffixLength) + 1, localeIdentifier);
2624     if (!prefixLength || prefixLength < minimumPrefixLength)
2625         return;
2626
2627     // When lastSapce is a space, which it always is except sometimes at the beginning of a line or after collapsed
2628     // space, it should not count towards hyphenate-limit-before.
2629     if (prefixLength == minimumPrefixLength) {
2630         UChar characterAtLastSpace = text->characterAt(lastSpace);
2631         if (characterAtLastSpace == ' ' || characterAtLastSpace == '\n' || characterAtLastSpace == '\t' || characterAtLastSpace == noBreakSpace)
2632             return;
2633     }
2634
2635     ASSERT(pos - lastSpace - prefixLength >= minimumSuffixLength);
2636
2637 #if !ASSERT_DISABLED
2638     float prefixWidth = hyphenWidth + textWidth(text, lastSpace, prefixLength, font, xPos, isFixedPitch, collapseWhiteSpace) + lastSpaceWordSpacing;
2639     ASSERT(xPos + prefixWidth <= availableWidth);
2640 #else
2641     UNUSED_PARAM(isFixedPitch);
2642 #endif
2643
2644     lineBreak.moveTo(text, lastSpace + prefixLength, nextBreakable);
2645     hyphenated = true;
2646 }
2647
2648 class TrailingObjects {
2649 public:
2650     TrailingObjects();
2651     void setTrailingWhitespace(RenderText*);
2652     void clear();
2653     void appendBoxIfNeeded(RenderBoxModelObject*);
2654
2655     enum CollapseFirstSpaceOrNot { DoNotCollapseFirstSpace, CollapseFirstSpace };
2656
2657     void updateMidpointsForTrailingBoxes(LineMidpointState&, const InlineIterator& lBreak, CollapseFirstSpaceOrNot);
2658
2659 private:
2660     RenderText* m_whitespace;
2661     Vector<RenderBoxModelObject*, 4> m_boxes;
2662 };
2663
2664 TrailingObjects::TrailingObjects()
2665     : m_whitespace(0)
2666 {
2667 }
2668
2669 inline void TrailingObjects::setTrailingWhitespace(RenderText* whitespace)
2670 {
2671     ASSERT(whitespace);
2672     m_whitespace = whitespace;
2673 }
2674
2675 inline void TrailingObjects::clear()
2676 {
2677     m_whitespace = 0;
2678     m_boxes.clear();
2679 }
2680
2681 inline void TrailingObjects::appendBoxIfNeeded(RenderBoxModelObject* box)
2682 {
2683     if (m_whitespace)
2684         m_boxes.append(box);
2685 }
2686
2687 void TrailingObjects::updateMidpointsForTrailingBoxes(LineMidpointState& lineMidpointState, const InlineIterator& lBreak, CollapseFirstSpaceOrNot collapseFirstSpace)
2688 {
2689     if (!m_whitespace)
2690         return;
2691
2692     // This object is either going to be part of the last midpoint, or it is going to be the actual endpoint.
2693     // In both cases we just decrease our pos by 1 level to exclude the space, allowing it to - in effect - collapse into the newline.
2694     if (lineMidpointState.numMidpoints % 2) {
2695         // Find the trailing space object's midpoint.
2696         int trailingSpaceMidpoint = lineMidpointState.numMidpoints - 1;
2697         for ( ; trailingSpaceMidpoint > 0 && lineMidpointState.midpoints[trailingSpaceMidpoint].m_obj != m_whitespace; --trailingSpaceMidpoint) { }
2698         ASSERT(trailingSpaceMidpoint >= 0);
2699         if (collapseFirstSpace == CollapseFirstSpace)
2700             lineMidpointState.midpoints[trailingSpaceMidpoint].m_pos--;
2701
2702         // Now make sure every single trailingPositionedBox following the trailingSpaceMidpoint properly stops and starts
2703         // ignoring spaces.
2704         size_t currentMidpoint = trailingSpaceMidpoint + 1;
2705         for (size_t i = 0; i < m_boxes.size(); ++i) {
2706             if (currentMidpoint >= lineMidpointState.numMidpoints) {
2707                 // We don't have a midpoint for this box yet.
2708                 ensureLineBoxInsideIgnoredSpaces(lineMidpointState, m_boxes[i]);
2709             } else {
2710                 ASSERT(lineMidpointState.midpoints[currentMidpoint].m_obj == m_boxes[i]);
2711                 ASSERT(lineMidpointState.midpoints[currentMidpoint + 1].m_obj == m_boxes[i]);
2712             }
2713             currentMidpoint += 2;
2714         }
2715     } else if (!lBreak.m_obj) {
2716         ASSERT(m_whitespace->isText());
2717         ASSERT(collapseFirstSpace == CollapseFirstSpace);
2718         // Add a new end midpoint that stops right at the very end.
2719         unsigned length = m_whitespace->textLength();
2720         unsigned pos = length >= 2 ? length - 2 : UINT_MAX;
2721         InlineIterator endMid(0, m_whitespace, pos);
2722         startIgnoringSpaces(lineMidpointState, endMid);
2723         for (size_t i = 0; i < m_boxes.size(); ++i) {
2724             ensureLineBoxInsideIgnoredSpaces(lineMidpointState, m_boxes[i]);
2725         }
2726     }
2727 }
2728
2729 void RenderBlock::LineBreaker::reset()
2730 {
2731     m_positionedObjects.clear();
2732     m_hyphenated = false;
2733     m_clear = CNONE;
2734 }
2735
2736 InlineIterator RenderBlock::LineBreaker::nextLineBreak(InlineBidiResolver& resolver, LineInfo& lineInfo, RenderTextInfo& renderTextInfo, FloatingObject* lastFloatFromPreviousLine, unsigned consecutiveHyphenatedLines, WordMeasurements& wordMeasurements)
2737 {
2738 #if !ENABLE(CSS_SHAPES)
2739     return nextSegmentBreak(resolver, lineInfo, renderTextInfo, lastFloatFromPreviousLine, consecutiveHyphenatedLines, wordMeasurements);
2740 #else
2741     ExclusionShapeInsideInfo* exclusionShapeInsideInfo = m_block->layoutExclusionShapeInsideInfo();
2742
2743     if (!exclusionShapeInsideInfo || !exclusionShapeInsideInfo->lineOverlapsShapeBounds())
2744         return nextSegmentBreak(resolver, lineInfo, renderTextInfo, lastFloatFromPreviousLine, consecutiveHyphenatedLines, wordMeasurements);
2745
2746     // 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,
2747     // 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.
2748     if (!m_block->flowThreadContainingBlock() && !exclusionShapeInsideInfo->lineWithinShapeBounds()) {
2749         exclusionShapeInsideInfo->clearSegments();
2750         return nextSegmentBreak(resolver, lineInfo, renderTextInfo, lastFloatFromPreviousLine, consecutiveHyphenatedLines, wordMeasurements);
2751     }
2752
2753     InlineIterator end = resolver.position();
2754     InlineIterator oldEnd = end;
2755
2756     if (!exclusionShapeInsideInfo->hasSegments()) {
2757         end = nextSegmentBreak(resolver, lineInfo, renderTextInfo, lastFloatFromPreviousLine, consecutiveHyphenatedLines, wordMeasurements);
2758         resolver.setPositionIgnoringNestedIsolates(oldEnd);
2759         return oldEnd;
2760     }
2761
2762     const SegmentList& segments = exclusionShapeInsideInfo->segments();
2763     SegmentRangeList& segmentRanges = exclusionShapeInsideInfo->segmentRanges();
2764
2765     for (unsigned i = 0; i < segments.size() && !end.atEnd(); i++) {
2766         InlineIterator segmentStart = resolver.position();
2767         end = nextSegmentBreak(resolver, lineInfo, renderTextInfo, lastFloatFromPreviousLine, consecutiveHyphenatedLines, wordMeasurements);
2768
2769         ASSERT(segmentRanges.size() == i);
2770         if (resolver.position().atEnd()) {
2771             segmentRanges.append(LineSegmentRange(segmentStart, end));
2772             break;
2773         }
2774         if (resolver.position() == end) {
2775             // Nothing fit this segment
2776             end = segmentStart;
2777             segmentRanges.append(LineSegmentRange(segmentStart, segmentStart));
2778             resolver.setPositionIgnoringNestedIsolates(segmentStart);
2779         } else {
2780             // Note that resolver.position is already skipping some of the white space at the beginning of the line,
2781             // so that's why segmentStart might be different than resolver.position().
2782             LineSegmentRange range(resolver.position(), end);
2783             segmentRanges.append(range);
2784             resolver.setPosition(end, numberOfIsolateAncestors(end));
2785
2786             if (lineInfo.previousLineBrokeCleanly()) {
2787                 // If we hit a new line break, just stop adding anything to this line.
2788                 break;
2789             }
2790         }
2791     }
2792     resolver.setPositionIgnoringNestedIsolates(oldEnd);
2793     return end;
2794 #endif
2795 }
2796
2797 static inline bool iteratorIsBeyondEndOfRenderCombineText(const InlineIterator& iter, RenderCombineText* renderer)
2798 {
2799     return iter.m_obj == renderer && iter.m_pos >= renderer->textLength();
2800 }
2801
2802 InlineIterator RenderBlock::LineBreaker::nextSegmentBreak(InlineBidiResolver& resolver, LineInfo& lineInfo, RenderTextInfo& renderTextInfo, FloatingObject* lastFloatFromPreviousLine, unsigned consecutiveHyphenatedLines, WordMeasurements& wordMeasurements)
2803 {
2804     reset();
2805
2806     ASSERT(resolver.position().root() == m_block);
2807
2808     bool appliedStartWidth = resolver.position().m_pos > 0;
2809     bool includeEndWidth = true;
2810     LineMidpointState& lineMidpointState = resolver.midpointState();
2811
2812     LineWidth width(m_block, lineInfo.isFirstLine(), requiresIndent(lineInfo.isFirstLine(), lineInfo.previousLineBrokeCleanly(), m_block->style()));
2813
2814     skipLeadingWhitespace(resolver, lineInfo, lastFloatFromPreviousLine, width);
2815
2816     if (resolver.position().atEnd())
2817         return resolver.position();
2818
2819     // This variable is used only if whitespace isn't set to PRE, and it tells us whether
2820     // or not we are currently ignoring whitespace.
2821     bool ignoringSpaces = false;
2822     InlineIterator ignoreStart;
2823
2824     // This variable tracks whether the very last character we saw was a space.  We use
2825     // this to detect when we encounter a second space so we know we have to terminate
2826     // a run.
2827     bool currentCharacterIsSpace = false;
2828     bool currentCharacterIsWS = false;
2829     TrailingObjects trailingObjects;
2830
2831     InlineIterator lBreak = resolver.position();
2832
2833     // FIXME: It is error-prone to split the position object out like this.
2834     // Teach this code to work with objects instead of this split tuple.
2835     InlineIterator current = resolver.position();
2836     RenderObject* last = current.m_obj;
2837     bool atStart = true;
2838
2839     bool startingNewParagraph = lineInfo.previousLineBrokeCleanly();
2840     lineInfo.setPreviousLineBrokeCleanly(false);
2841
2842     bool autoWrapWasEverTrueOnLine = false;
2843     bool floatsFitOnLine = true;
2844
2845     // Firefox and Opera will allow a table cell to grow to fit an image inside it under
2846     // very specific circumstances (in order to match common WinIE renderings).
2847     // Not supporting the quirk has caused us to mis-render some real sites. (See Bugzilla 10517.)
2848     RenderStyle* blockStyle = m_block->style();
2849     bool allowImagesToBreak = !m_block->document()->inQuirksMode() || !m_block->isTableCell() || !blockStyle->logicalWidth().isIntrinsicOrAuto();
2850
2851     EWhiteSpace currWS = blockStyle->whiteSpace();
2852     EWhiteSpace lastWS = currWS;
2853     while (current.m_obj) {
2854         RenderStyle* currentStyle = current.m_obj->style();
2855         RenderObject* next = bidiNextSkippingEmptyInlines(m_block, current.m_obj);
2856         if (next && next->parent() && !next->parent()->isDescendantOf(current.m_obj->parent()))
2857             includeEndWidth = true;
2858
2859         currWS = current.m_obj->isReplaced() ? current.m_obj->parent()->style()->whiteSpace() : currentStyle->whiteSpace();
2860         lastWS = last->isReplaced() ? last->parent()->style()->whiteSpace() : last->style()->whiteSpace();
2861
2862         bool autoWrap = RenderStyle::autoWrap(currWS);
2863         autoWrapWasEverTrueOnLine = autoWrapWasEverTrueOnLine || autoWrap;
2864
2865 #if ENABLE(SVG)
2866         bool preserveNewline = current.m_obj->isSVGInlineText() ? false : RenderStyle::preserveNewline(currWS);
2867 #else
2868         bool preserveNewline = RenderStyle::preserveNewline(currWS);
2869 #endif
2870
2871         bool collapseWhiteSpace = RenderStyle::collapseWhiteSpace(currWS);
2872
2873         if (current.m_obj->isBR()) {
2874             if (width.fitsOnLine()) {
2875                 lBreak.moveToStartOf(current.m_obj);
2876                 lBreak.increment();
2877
2878                 // A <br> always breaks a line, so don't let the line be collapsed
2879                 // away. Also, the space at the end of a line with a <br> does not
2880                 // get collapsed away.  It only does this if the previous line broke
2881                 // cleanly.  Otherwise the <br> has no effect on whether the line is
2882                 // empty or not.
2883                 if (startingNewParagraph)
2884                     lineInfo.setEmpty(false, m_block, &width);
2885                 trailingObjects.clear();
2886                 lineInfo.setPreviousLineBrokeCleanly(true);
2887
2888                 // A <br> with clearance always needs a linebox in case the lines below it get dirtied later and 
2889                 // need to check for floats to clear - so if we're ignoring spaces, stop ignoring them and add a
2890                 // run for this object.
2891                 if (ignoringSpaces && currentStyle->clear() != CNONE)
2892                     ensureLineBoxInsideIgnoredSpaces(lineMidpointState, current.m_obj);
2893
2894                 if (!lineInfo.isEmpty())
2895                     m_clear = currentStyle->clear();
2896             }
2897             goto end;
2898         }
2899
2900         if (current.m_obj->isOutOfFlowPositioned()) {
2901             // If our original display wasn't an inline type, then we can
2902             // go ahead and determine our static inline position now.
2903             RenderBox* box = toRenderBox(current.m_obj);
2904             bool isInlineType = box->style()->isOriginalDisplayInlineType();
2905             if (!isInlineType)
2906                 m_block->setStaticInlinePositionForChild(box, m_block->logicalHeight(), m_block->startOffsetForContent(m_block->logicalHeight()));
2907             else  {
2908                 // If our original display was an INLINE type, then we can go ahead
2909                 // and determine our static y position now.
2910                 box->layer()->setStaticBlockPosition(m_block->logicalHeight());
2911             }
2912
2913             // If we're ignoring spaces, we have to stop and include this object and
2914             // then start ignoring spaces again.
2915             if (isInlineType || current.m_obj->container()->isRenderInline()) {
2916                 if (ignoringSpaces)
2917                     ensureLineBoxInsideIgnoredSpaces(lineMidpointState, current.m_obj);
2918                 trailingObjects.appendBoxIfNeeded(box);
2919             } else
2920                 m_positionedObjects.append(box);
2921             width.addUncommittedWidth(inlineLogicalWidth(current.m_obj));
2922             // Reset prior line break context characters.
2923             renderTextInfo.m_lineBreakIterator.resetPriorContext();
2924         } else if (current.m_obj->isFloating()) {
2925             RenderBox* floatBox = toRenderBox(current.m_obj);
2926             FloatingObject* f = m_block->insertFloatingObject(floatBox);
2927             // check if it fits in the current line.
2928             // If it does, position it now, otherwise, position
2929             // it after moving to next line (in newLine() func)
2930             // FIXME: Bug 110372: Properly position multiple stacked floats with non-rectangular shape outside.
2931             if (floatsFitOnLine && width.fitsOnLine(m_block->logicalWidthForFloat(f), true)) {
2932                 m_block->positionNewFloatOnLine(f, lastFloatFromPreviousLine, lineInfo, width);
2933                 if (lBreak.m_obj == current.m_obj) {
2934                     ASSERT(!lBreak.m_pos);
2935                     lBreak.increment();
2936                 }
2937             } else
2938                 floatsFitOnLine = false;
2939             // Update prior line break context characters, using U+FFFD (OBJECT REPLACEMENT CHARACTER) for floating element.
2940             renderTextInfo.m_lineBreakIterator.updatePriorContext(replacementCharacter);
2941         } else if (current.m_obj->isRenderInline()) {
2942             // Right now, we should only encounter empty inlines here.
2943             ASSERT(isEmptyInline(current.m_obj));
2944
2945             RenderInline* flowBox = toRenderInline(current.m_obj);
2946
2947             // Now that some inline flows have line boxes, if we are already ignoring spaces, we need
2948             // to make sure that we stop to include this object and then start ignoring spaces again.
2949             // If this object is at the start of the line, we need to behave like list markers and
2950             // start ignoring spaces.
2951             bool requiresLineBox = alwaysRequiresLineBox(current.m_obj);
2952             if (requiresLineBox || requiresLineBoxForContent(flowBox, lineInfo)) {
2953                 // An empty inline that only has line-height, vertical-align or font-metrics will only get a
2954                 // line box to affect the height of the line if the rest of the line is not empty.
2955                 if (requiresLineBox)
2956                     lineInfo.setEmpty(false, m_block, &width);
2957                 if (ignoringSpaces) {
2958                     trailingObjects.clear();
2959                     ensureLineBoxInsideIgnoredSpaces(lineMidpointState, current.m_obj);
2960                 } else if (blockStyle->collapseWhiteSpace() && resolver.position().m_obj == current.m_obj
2961                     && shouldSkipWhitespaceAfterStartObject(m_block, current.m_obj, lineMidpointState)) {
2962                     // Like with list markers, we start ignoring spaces to make sure that any
2963                     // additional spaces we see will be discarded.
2964                     currentCharacterIsSpace = true;
2965                     currentCharacterIsWS = true;
2966                     ignoringSpaces = true;
2967                 } else {
2968                     trailingObjects.appendBoxIfNeeded(flowBox);
2969                 }
2970             }
2971
2972             width.addUncommittedWidth(inlineLogicalWidth(current.m_obj) + borderPaddingMarginStart(flowBox) + borderPaddingMarginEnd(flowBox));
2973         } else if (current.m_obj->isReplaced()) {
2974             RenderBox* replacedBox = toRenderBox(current.m_obj);
2975
2976             if (atStart)
2977                 width.updateAvailableWidth(replacedBox->logicalHeight());
2978
2979             // Break on replaced elements if either has normal white-space.
2980             if ((autoWrap || RenderStyle::autoWrap(lastWS)) && (!current.m_obj->isImage() || allowImagesToBreak)) {
2981                 width.commit();
2982                 lBreak.moveToStartOf(current.m_obj);
2983             }
2984
2985             if (ignoringSpaces)
2986                 stopIgnoringSpaces(lineMidpointState, InlineIterator(0, current.m_obj, 0));
2987
2988             lineInfo.setEmpty(false, m_block, &width);
2989             ignoringSpaces = false;
2990             currentCharacterIsSpace = false;
2991             currentCharacterIsWS = false;
2992             trailingObjects.clear();
2993
2994             // Optimize for a common case. If we can't find whitespace after the list
2995             // item, then this is all moot.
2996             LayoutUnit replacedLogicalWidth = m_block->logicalWidthForChild(replacedBox) + m_block->marginStartForChild(replacedBox) + m_block->marginEndForChild(replacedBox) + inlineLogicalWidth(current.m_obj);
2997             if (current.m_obj->isListMarker()) {
2998                 if (blockStyle->collapseWhiteSpace() && shouldSkipWhitespaceAfterStartObject(m_block, current.m_obj, lineMidpointState)) {
2999                     // Like with inline flows, we start ignoring spaces to make sure that any
3000                     // additional spaces we see will be discarded.
3001                     currentCharacterIsSpace = true;
3002                     currentCharacterIsWS = true;
3003                     ignoringSpaces = true;
3004                 }
3005                 if (toRenderListMarker(current.m_obj)->isInside())
3006                     width.addUncommittedWidth(replacedLogicalWidth);
3007             } else
3008                 width.addUncommittedWidth(replacedLogicalWidth);
3009             if (current.m_obj->isRubyRun())
3010                 width.applyOverhang(toRenderRubyRun(current.m_obj), last, next);
3011             // Update prior line break context characters, using U+FFFD (OBJECT REPLACEMENT CHARACTER) for replaced element.
3012             renderTextInfo.m_lineBreakIterator.updatePriorContext(replacementCharacter);
3013         } else if (current.m_obj->isText()) {
3014             if (!current.m_pos)
3015                 appliedStartWidth = false;
3016
3017             RenderText* t = toRenderText(current.m_obj);
3018
3019 #if ENABLE(SVG)
3020             bool isSVGText = t->isSVGInlineText();
3021 #endif
3022
3023             if (t->style()->hasTextCombine() && current.m_obj->isCombineText() && !toRenderCombineText(current.m_obj)->isCombined()) {
3024                 RenderCombineText* combineRenderer = toRenderCombineText(current.m_obj);
3025                 combineRenderer->combineText();
3026                 // The length of the renderer's text may have changed. Increment stale iterator positions
3027                 if (iteratorIsBeyondEndOfRenderCombineText(lBreak, combineRenderer)) {
3028                     ASSERT(iteratorIsBeyondEndOfRenderCombineText(resolver.position(), combineRenderer));
3029                     lBreak.increment();
3030                     resolver.increment();
3031                 }
3032             }
3033
3034             RenderStyle* style = t->style(lineInfo.isFirstLine());
3035             const Font& f = style->font();
3036             bool isFixedPitch = f.isFixedPitch();
3037             bool canHyphenate = style->hyphens() == HyphensAuto && WebCore::canHyphenate(style->locale());
3038
3039             unsigned lastSpace = current.m_pos;
3040             float wordSpacing = currentStyle->wordSpacing();
3041             float lastSpaceWordSpacing = 0;
3042             float wordSpacingForWordMeasurement = 0;
3043
3044             float wrapW = width.uncommittedWidth() + inlineLogicalWidth(current.m_obj, !appliedStartWidth, true);
3045             float charWidth = 0;
3046             bool breakNBSP = autoWrap && currentStyle->nbspMode() == SPACE;
3047             // Auto-wrapping text should wrap in the middle of a word only if it could not wrap before the word,
3048             // which is only possible if the word is the first thing on the line, that is, if |w| is zero.
3049             bool breakWords = currentStyle->breakWords() && ((autoWrap && !width.committedWidth()) || currWS == PRE);
3050             bool midWordBreak = false;
3051             bool breakAll = currentStyle->wordBreak() == BreakAllWordBreak && autoWrap;
3052             float hyphenWidth = 0;
3053 #if ENABLE(SVG)
3054             if (isSVGText) {
3055                 breakWords = false;
3056                 breakAll = false;
3057             }
3058 #endif
3059
3060             if (t->isWordBreak()) {
3061                 width.commit();
3062                 lBreak.moveToStartOf(current.m_obj);
3063                 ASSERT(current.m_pos == t->textLength());
3064             }
3065
3066             if (renderTextInfo.m_text != t) {
3067                 updateCounterIfNeeded(t);
3068                 renderTextInfo.m_text = t;
3069                 renderTextInfo.m_font = &f;
3070                 renderTextInfo.m_layout = f.createLayout(t, width.currentWidth(), collapseWhiteSpace);
3071                 renderTextInfo.m_lineBreakIterator.resetStringAndReleaseIterator(t->text(), style->locale());
3072             } else if (renderTextInfo.m_layout && renderTextInfo.m_font != &f) {
3073                 renderTextInfo.m_font = &f;
3074                 renderTextInfo.m_layout = f.createLayout(t, width.currentWidth(), collapseWhiteSpace);
3075             }
3076
3077             TextLayout* textLayout = renderTextInfo.m_layout.get();
3078
3079             // Non-zero only when kerning is enabled and TextLayout isn't used, in which case we measure
3080             // words with their trailing space, then subtract its width.
3081             float wordTrailingSpaceWidth = (f.typesettingFeatures() & Kerning) && !textLayout ? f.width(constructTextRun(t, f, &space, 1, style)) + wordSpacing : 0;
3082
3083             UChar lastCharacter = renderTextInfo.m_lineBreakIterator.lastCharacter();
3084             UChar secondToLastCharacter = renderTextInfo.m_lineBreakIterator.secondToLastCharacter();
3085             for (; current.m_pos < t->textLength(); current.fastIncrementInTextNode()) {
3086                 bool previousCharacterIsSpace = currentCharacterIsSpace;
3087                 bool previousCharacterIsWS = currentCharacterIsWS;
3088                 UChar c = current.current();
3089                 currentCharacterIsSpace = c == ' ' || c == '\t' || (!preserveNewline && (c == '\n'));
3090
3091                 if (!collapseWhiteSpace || !currentCharacterIsSpace)
3092                     lineInfo.setEmpty(false, m_block, &width);
3093
3094                 if (c == softHyphen && autoWrap && !hyphenWidth && style->hyphens() != HyphensNone) {
3095                     hyphenWidth = measureHyphenWidth(t, f);
3096                     width.addUncommittedWidth(hyphenWidth);
3097                 }
3098
3099                 bool applyWordSpacing = false;
3100
3101                 currentCharacterIsWS = currentCharacterIsSpace || (breakNBSP && c == noBreakSpace);
3102
3103                 if ((breakAll || breakWords) && !midWordBreak) {
3104                     wrapW += charWidth;
3105                     bool midWordBreakIsBeforeSurrogatePair = U16_IS_LEAD(c) && current.m_pos + 1 < t->textLength() && U16_IS_TRAIL(t->characters()[current.m_pos + 1]);
3106                     charWidth = textWidth(t, current.m_pos, midWordBreakIsBeforeSurrogatePair ? 2 : 1, f, width.committedWidth() + wrapW, isFixedPitch, collapseWhiteSpace, 0, textLayout);
3107                     midWordBreak = width.committedWidth() + wrapW + charWidth > width.availableWidth();
3108                 }
3109
3110                 bool betweenWords = c == '\n' || (currWS != PRE && !atStart && isBreakable(renderTextInfo.m_lineBreakIterator, current.m_pos, current.m_nextBreakablePosition, breakNBSP)
3111                     && (style->hyphens() != HyphensNone || (current.previousInSameNode() != softHyphen)));
3112
3113                 if (betweenWords || midWordBreak) {
3114                     bool stoppedIgnoringSpaces = false;
3115                     if (ignoringSpaces) {
3116                         lastSpaceWordSpacing = 0;
3117                         if (!currentCharacterIsSpace) {
3118                             // Stop ignoring spaces and begin at this
3119                             // new point.
3120                             ignoringSpaces = false;
3121                             wordSpacingForWordMeasurement = 0;
3122                             lastSpace = current.m_pos; // e.g., "Foo    goo", don't add in any of the ignored spaces.
3123                             stopIgnoringSpaces(lineMidpointState, InlineIterator(0, current.m_obj, current.m_pos));
3124                             stoppedIgnoringSpaces = true;
3125                         } else {
3126                             // Just keep ignoring these spaces.
3127                             goto nextCharacter;
3128                         }
3129                     }
3130
3131                     wordMeasurements.grow(wordMeasurements.size() + 1);
3132                     WordMeasurement& wordMeasurement = wordMeasurements.last();
3133                     
3134                     wordMeasurement.renderer = t;
3135                     wordMeasurement.endOffset = current.m_pos;
3136                     wordMeasurement.startOffset = lastSpace;
3137                     
3138                     float additionalTempWidth;
3139                     if (wordTrailingSpaceWidth && c == ' ')
3140                         additionalTempWidth = textWidth(t, lastSpace, current.m_pos + 1 - lastSpace, f, width.currentWidth(), isFixedPitch, collapseWhiteSpace, &wordMeasurement.fallbackFonts, textLayout) - wordTrailingSpaceWidth;
3141                     else
3142                         additionalTempWidth = textWidth(t, lastSpace, current.m_pos - lastSpace, f, width.currentWidth(), isFixedPitch, collapseWhiteSpace, &wordMeasurement.fallbackFonts, textLayout);
3143
3144                     wordMeasurement.width = additionalTempWidth + wordSpacingForWordMeasurement;
3145                     additionalTempWidth += lastSpaceWordSpacing;
3146                     width.addUncommittedWidth(additionalTempWidth);
3147
3148                     if (collapseWhiteSpace && previousCharacterIsSpace && currentCharacterIsSpace && additionalTempWidth)
3149                         width.setTrailingWhitespaceWidth(additionalTempWidth);
3150
3151                     if (!appliedStartWidth) {
3152                         width.addUncommittedWidth(inlineLogicalWidth(current.m_obj, true, false));
3153                         appliedStartWidth = true;
3154                     }
3155
3156                     applyWordSpacing = wordSpacing && currentCharacterIsSpace;
3157
3158                     if (!width.committedWidth() && autoWrap && !width.fitsOnLine())
3159                         width.fitBelowFloats();
3160
3161                     if (autoWrap || breakWords) {
3162                         // If we break only after white-space, consider the current character
3163                         // as candidate width for this line.
3164                         bool lineWasTooWide = false;
3165                         if (width.fitsOnLine() && currentCharacterIsWS && currentStyle->breakOnlyAfterWhiteSpace() && !midWordBreak) {
3166                             float charWidth = textWidth(t, current.m_pos, 1, f, width.currentWidth(), isFixedPitch, collapseWhiteSpace, &wordMeasurement.fallbackFonts, textLayout) + (applyWordSpacing ? wordSpacing : 0);
3167                             // Check if line is too big even without the extra space
3168                             // at the end of the line. If it is not, do nothing.
3169                             // If the line needs the extra whitespace to be too long,
3170                             // then move the line break to the space and skip all
3171                             // additional whitespace.
3172                             if (!width.fitsOnLine(charWidth)) {
3173                                 lineWasTooWide = true;
3174                                 lBreak.moveTo(current.m_obj, current.m_pos, current.m_nextBreakablePosition);
3175                                 skipTrailingWhitespace(lBreak, lineInfo);
3176                             }
3177                         }
3178                         if (lineWasTooWide || !width.fitsOnLine()) {
3179                             if (canHyphenate && !width.fitsOnLine()) {
3180                                 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);
3181                                 if (m_hyphenated)
3182                                     goto end;
3183                             }
3184                             if (lBreak.atTextParagraphSeparator()) {
3185                                 if (!stoppedIgnoringSpaces && current.m_pos > 0)
3186                                     ensureCharacterGetsLineBox(lineMidpointState, current);
3187                                 lBreak.increment();
3188                                 lineInfo.setPreviousLineBrokeCleanly(true);
3189                                 wordMeasurement.endOffset = lBreak.m_pos;
3190                             }
3191                             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)
3192                                 m_hyphenated = true;
3193                             if (lBreak.m_pos && lBreak.m_pos != (unsigned)wordMeasurement.endOffset && !wordMeasurement.width) {
3194                                 if (charWidth) {
3195                                     wordMeasurement.endOffset = lBreak.m_pos;
3196                                     wordMeasurement.width = charWidth;
3197                                 }
3198                             }
3199                             // Didn't fit. Jump to the end unless there's still an opportunity to collapse whitespace.
3200                             if (ignoringSpaces || !collapseWhiteSpace || !currentCharacterIsSpace || !previousCharacterIsSpace)
3201                                 goto end;
3202                         } else {
3203                             if (!betweenWords || (midWordBreak && !autoWrap))
3204                                 width.addUncommittedWidth(-additionalTempWidth);
3205                             if (hyphenWidth) {
3206                                 // Subtract the width of the soft hyphen out since we fit on a line.
3207                                 width.addUncommittedWidth(-hyphenWidth);
3208                                 hyphenWidth = 0;
3209                             }
3210                         }
3211                     }
3212
3213                     if (c == '\n' && preserveNewline) {
3214                         if (!stoppedIgnoringSpaces && current.m_pos > 0)
3215                             ensureCharacterGetsLineBox(lineMidpointState, current);
3216                         lBreak.moveTo(current.m_obj, current.m_pos, current.m_nextBreakablePosition);
3217                         lBreak.increment();
3218                         lineInfo.setPreviousLineBrokeCleanly(true);
3219                         return lBreak;
3220                     }
3221
3222                     if (autoWrap && betweenWords) {
3223                         width.commit();
3224                         wrapW = 0;
3225                         lBreak.moveTo(current.m_obj, current.m_pos, current.m_nextBreakablePosition);
3226                         // Auto-wrapping text should not wrap in the middle of a word once it has had an
3227                         // opportunity to break after a word.
3228                         breakWords = false;
3229                     }
3230
3231                     if (midWordBreak && !U16_IS_TRAIL(c) && !(category(c) & (Mark_NonSpacing | Mark_Enclosing | Mark_SpacingCombining))) {
3232                         // Remember this as a breakable position in case
3233                         // adding the end width forces a break.
3234                         lBreak.moveTo(current.m_obj, current.m_pos, current.m_nextBreakablePosition);
3235                         midWordBreak &= (breakWords || breakAll);
3236                     }
3237
3238                     if (betweenWords) {
3239                         lastSpaceWordSpacing = applyWordSpacing ? wordSpacing : 0;
3240                         wordSpacingForWordMeasurement = (applyWordSpacing && wordMeasurement.width) ? wordSpacing : 0;
3241                         lastSpace = current.m_pos;
3242                     }
3243
3244                     if (!ignoringSpaces && currentStyle->collapseWhiteSpace()) {
3245                         // If we encounter a newline, or if we encounter a
3246                         // second space, we need to go ahead and break up this
3247                         // run and enter a mode where we start collapsing spaces.
3248                         if (currentCharacterIsSpace && previousCharacterIsSpace) {
3249                             ignoringSpaces = true;
3250
3251                             // We just entered a mode where we are ignoring
3252                             // spaces. Create a midpoint to terminate the run
3253                             // before the second space.
3254                             startIgnoringSpaces(lineMidpointState, ignoreStart);
3255                             trailingObjects.updateMidpointsForTrailingBoxes(lineMidpointState, InlineIterator(), TrailingObjects::DoNotCollapseFirstSpace);
3256                         }
3257                     }
3258                 } else if (ignoringSpaces) {
3259                     // Stop ignoring spaces and begin at this
3260                     // new point.
3261                     ignoringSpaces = false;
3262                     lastSpaceWordSpacing = applyWordSpacing ? wordSpacing : 0;
3263                     wordSpacingForWordMeasurement = (applyWordSpacing && wordMeasurements.last().width) ? wordSpacing : 0;
3264                     lastSpace = current.m_pos; // e.g., "Foo    goo", don't add in any of the ignored spaces.
3265                     stopIgnoringSpaces(lineMidpointState, InlineIterator(0, current.m_obj, current.m_pos));
3266                 }
3267
3268 #if ENABLE(SVG)
3269                 if (isSVGText && current.m_pos > 0) {
3270                     // Force creation of new InlineBoxes for each absolute positioned character (those that start new text chunks).
3271                     if (toRenderSVGInlineText(t)->characterStartsNewTextChunk(current.m_pos))
3272                         ensureCharacterGetsLineBox(lineMidpointState, current);
3273                 }
3274 #endif
3275
3276                 if (currentCharacterIsSpace && !previousCharacterIsSpace) {
3277                     ignoreStart.m_obj = current.m_obj;
3278                     ignoreStart.m_pos = current.m_pos;
3279                 }
3280
3281                 if (!currentCharacterIsWS && previousCharacterIsWS) {
3282                     if (autoWrap && currentStyle->breakOnlyAfterWhiteSpace())
3283                         lBreak.moveTo(current.m_obj, current.m_pos, current.m_nextBreakablePosition);
3284                 }
3285
3286                 if (collapseWhiteSpace && currentCharacterIsSpace && !ignoringSpaces)
3287                     trailingObjects.setTrailingWhitespace(toRenderText(current.m_obj));
3288                 else if (!currentStyle->collapseWhiteSpace() || !currentCharacterIsSpace)
3289                     trailingObjects.clear();
3290
3291                 atStart = false;
3292             nextCharacter:
3293                 secondToLastCharacter = lastCharacter;
3294                 lastCharacter = c;
3295             }
3296
3297             renderTextInfo.m_lineBreakIterator.setPriorContext(lastCharacter, secondToLastCharacter);
3298
3299             wordMeasurements.grow(wordMeasurements.size() + 1);
3300             WordMeasurement& wordMeasurement = wordMeasurements.last();
3301             wordMeasurement.renderer = t;
3302
3303             // IMPORTANT: current.m_pos is > length here!
3304             float additionalTempWidth = ignoringSpaces ? 0 : textWidth(t, lastSpace, current.m_pos - lastSpace, f, width.currentWidth(), isFixedPitch, collapseWhiteSpace, &wordMeasurement.fallbackFonts, textLayout);
3305             wordMeasurement.startOffset = lastSpace;
3306             wordMeasurement.endOffset = current.m_pos;
3307             wordMeasurement.width = ignoringSpaces ? 0 : additionalTempWidth + wordSpacingForWordMeasurement;
3308             additionalTempWidth += lastSpaceWordSpacing;
3309
3310             float inlineLogicalTempWidth = inlineLogicalWidth(current.m_obj, !appliedStartWidth, includeEndWidth);
3311             width.addUncommittedWidth(additionalTempWidth + inlineLogicalTempWidth);
3312
3313             if (collapseWhiteSpace && currentCharacterIsSpace && additionalTempWidth)
3314                 width.setTrailingWhitespaceWidth(additionalTempWidth + inlineLogicalTempWidth);
3315
3316             includeEndWidth = false;
3317
3318             if (!width.fitsOnLine()) {
3319                 if (canHyphenate)
3320                     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);
3321
3322                 if (!m_hyphenated && lBreak.previousInSameNode() == softHyphen && style->hyphens() != HyphensNone)
3323                     m_hyphenated = true;
3324
3325                 if (m_hyphenated)
3326                     goto end;
3327             }
3328         } else
3329             ASSERT_NOT_REACHED();
3330
3331         bool checkForBreak = autoWrap;
3332         if (width.committedWidth() && !width.fitsOnLine() && lBreak.m_obj && currWS == NOWRAP)
3333             checkForBreak = true;
3334         else if (next && current.m_obj->isText() && next->isText() && !next->isBR() && (autoWrap || next->style()->autoWrap())) {
3335             if (autoWrap && currentCharacterIsSpace)
3336                 checkForBreak = true;
3337             else {
3338                 RenderText* nextText = toRenderText(next);
3339                 if (nextText->textLength()) {
3340                     UChar c = nextText->characterAt(0);
3341                     // If we allow whitespace collapsing, 'word  ' and 'word' are equivalent before a whitespace
3342                     // character, so treat both as a potential linebreak.
3343                     checkForBreak = (ignoringSpaces || !currentCharacterIsSpace) && (c == ' ' || c == '\t' || (c == '\n' && !next->preservesNewline()));
3344                 } else if (nextText->isWordBreak())
3345                     checkForBreak = true;
3346
3347                 if (!width.fitsOnLine() && !width.committedWidth())
3348                     width.fitBelowFloats();
3349
3350                 bool canPlaceOnLine = width.fitsOnLine() || !autoWrapWasEverTrueOnLine;
3351                 if (canPlaceOnLine && checkForBreak) {
3352                     width.commit();
3353                     lBreak.moveToStartOf(next);
3354                 }
3355             }
3356         }
3357
3358         if (checkForBreak && !width.fitsOnLine()) {
3359             // if we have floats, try to get below them.
3360             if (currentCharacterIsSpace && !ignoringSpaces && currentStyle->collapseWhiteSpace())
3361                 trailingObjects.clear();
3362
3363             if (width.committedWidth())
3364                 goto end;
3365
3366             width.fitBelowFloats();
3367
3368             // |width| may have been adjusted because we got shoved down past a float (thus
3369             // giving us more room), so we need to retest, and only jump to
3370             // the end label if we still don't fit on the line. -dwh
3371             if (!width.fitsOnLine())
3372                 goto end;
3373         } else if (blockStyle->autoWrap() && !width.fitsOnLine() && !width.committedWidth()) {
3374             // If the container autowraps but the current child does not then we still need to ensure that it
3375             // wraps and moves below any floats.
3376             width.fitBelowFloats();
3377         }
3378
3379         if (!current.m_obj->isFloatingOrOutOfFlowPositioned()) {
3380             last = current.m_obj;
3381             if (last->isReplaced() && autoWrap && (!last->isImage() || allowImagesToBreak) && (!last->isListMarker() || toRenderListMarker(last)->isInside())) {
3382                 width.commit();
3383                 lBreak.moveToStartOf(next);
3384             }
3385         }
3386
3387         // Clear out our character space bool, since inline <pre>s don't collapse whitespace
3388         // with adjacent inline normal/nowrap spans.
3389         if (!collapseWhiteSpace)
3390             currentCharacterIsSpace = false;
3391
3392         current.moveToStartOf(next);
3393         atStart = false;
3394     }
3395
3396     if (width.fitsOnLine() || lastWS == NOWRAP)
3397         lBreak.clear();
3398
3399  end:
3400 #if ENABLE(CSS_SHAPES)
3401     ExclusionShapeInsideInfo* shapeInfo = m_block->layoutExclusionShapeInsideInfo();
3402     bool segmentAllowsOverflow = !shapeInfo || !shapeInfo->hasSegments();
3403 #else
3404     bool segmentAllowsOverflow = true;
3405 #endif
3406
3407     if (lBreak == resolver.position() && (!lBreak.m_obj || !lBreak.m_obj->isBR()) && segmentAllowsOverflow) {
3408         // we just add as much as possible
3409         if (blockStyle->whiteSpace() == PRE && !current.m_pos) {
3410             lBreak.moveTo(last, last->isText() ? last->length() : 0);
3411         } else if (lBreak.m_obj) {
3412             // Don't ever break in the middle of a word if we can help it.
3413             // There's no room at all. We just have to be on this line,
3414             // even though we'll spill out.
3415             lBreak.moveTo(current.m_obj, current.m_pos);
3416         }
3417     }
3418
3419     // make sure we consume at least one char/object.
3420     if (lBreak == resolver.position() && segmentAllowsOverflow)
3421         lBreak.increment();
3422
3423     // Sanity check our midpoints.
3424     checkMidpoints(lineMidpointState, lBreak);
3425
3426     trailingObjects.updateMidpointsForTrailingBoxes(lineMidpointState, lBreak, TrailingObjects::CollapseFirstSpace);
3427
3428     // We might have made lBreak an iterator that points past the end
3429     // of the object. Do this adjustment to make it point to the start
3430     // of the next object instead to avoid confusing the rest of the
3431     // code.
3432     if (lBreak.m_pos > 0) {
3433         lBreak.m_pos--;
3434         lBreak.increment();
3435     }
3436
3437     return lBreak;
3438 }
3439
3440 void RenderBlock::addOverflowFromInlineChildren()
3441 {
3442     LayoutUnit endPadding = hasOverflowClip() ? paddingEnd() : LayoutUnit();
3443     // FIXME: Need to find another way to do this, since scrollbars could show when we don't want them to.
3444     if (hasOverflowClip() && !endPadding && node() && node()->isRootEditableElement() && style()->isLeftToRightDirection())
3445         endPadding = 1;
3446     for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
3447         addLayoutOverflow(curr->paddedLayoutOverflowRect(endPadding));
3448         if (!hasOverflowClip())
3449             addVisualOverflow(curr->visualOverflowRect(curr->lineTop(), curr->lineBottom()));
3450     }
3451 }
3452
3453 void RenderBlock::deleteEllipsisLineBoxes()
3454 {
3455     ETextAlign textAlign = style()->textAlign();
3456     bool ltr = style()->isLeftToRightDirection();
3457     bool firstLine = true;
3458     for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
3459         if (curr->hasEllipsisBox()) {
3460             curr->clearTruncation();
3461
3462             // Shift the line back where it belongs if we cannot accomodate an ellipsis.
3463             float logicalLeft = pixelSnappedLogicalLeftOffsetForLine(curr->lineTop(), firstLine);
3464             float availableLogicalWidth = logicalRightOffsetForLine(curr->lineTop(), false) - logicalLeft;
3465             float totalLogicalWidth = curr->logicalWidth();
3466             updateLogicalWidthForAlignment(textAlign, 0, logicalLeft, totalLogicalWidth, availableLogicalWidth, 0);
3467
3468             if (ltr)
3469                 curr->adjustLogicalPosition((logicalLeft - curr->logicalLeft()), 0);
3470             else
3471                 curr->adjustLogicalPosition(-(curr->logicalLeft() - logicalLeft), 0);
3472         }
3473         firstLine = false;
3474     }
3475 }
3476
3477 void RenderBlock::checkLinesForTextOverflow()