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