0c2e6e105df260fdb62653070132f05b34d9b553
[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 "RenderInline.h"
33 #include "RenderLayer.h"
34 #include "RenderListMarker.h"
35 #include "RenderRubyRun.h"
36 #include "RenderView.h"
37 #include "Settings.h"
38 #include "TextBreakIterator.h"
39 #include "TrailingFloatsRootInlineBox.h"
40 #include "VerticalPositionCache.h"
41 #include "break_lines.h"
42 #include <wtf/AlwaysInline.h>
43 #include <wtf/RefCountedLeakCounter.h>
44 #include <wtf/StdLibExtras.h>
45 #include <wtf/Vector.h>
46 #include <wtf/unicode/CharacterNames.h>
47
48 #if ENABLE(SVG)
49 #include "RenderSVGInlineText.h"
50 #include "SVGRootInlineBox.h"
51 #endif
52
53 using namespace std;
54 using namespace WTF;
55 using namespace Unicode;
56
57 namespace WebCore {
58
59 // We don't let our line box tree for a single line get any deeper than this.
60 const unsigned cMaxLineDepth = 200;
61
62 class LineInfo {
63 public:
64     LineInfo()
65         : m_isFirstLine(true)
66         , m_isLastLine(false)
67         , m_isEmpty(true)
68         , m_previousLineBrokeCleanly(true)
69     { }
70
71     bool isFirstLine() const { return m_isFirstLine; }
72     bool isLastLine() const { return m_isLastLine; }
73     bool isEmpty() const { return m_isEmpty; }
74     bool previousLineBrokeCleanly() const { return m_previousLineBrokeCleanly; }
75
76     void setFirstLine(bool firstLine) { m_isFirstLine = firstLine; }
77     void setLastLine(bool lastLine) { m_isLastLine = lastLine; }
78     void setEmpty(bool empty) { m_isEmpty = empty; }
79     void setPreviousLineBrokeCleanly(bool previousLineBrokeCleanly) { m_previousLineBrokeCleanly = previousLineBrokeCleanly; }
80
81 private:
82     bool m_isFirstLine;
83     bool m_isLastLine;
84     bool m_isEmpty;
85     bool m_previousLineBrokeCleanly;
86 };
87
88 static inline int borderPaddingMarginStart(RenderInline* child)
89 {
90     return child->marginStart() + child->paddingStart() + child->borderStart();
91 }
92
93 static inline int borderPaddingMarginEnd(RenderInline* child)
94 {
95     return child->marginEnd() + child->paddingEnd() + child->borderEnd();
96 }
97
98 static int inlineLogicalWidth(RenderObject* child, bool start = true, bool end = true)
99 {
100     unsigned lineDepth = 1;
101     int extraWidth = 0;
102     RenderObject* parent = child->parent();
103     while (parent->isRenderInline() && lineDepth++ < cMaxLineDepth) {
104         RenderInline* parentAsRenderInline = toRenderInline(parent);
105         if (start && !child->previousSibling())
106             extraWidth += borderPaddingMarginStart(parentAsRenderInline);
107         if (end && !child->nextSibling())
108             extraWidth += borderPaddingMarginEnd(parentAsRenderInline);
109         child = parent;
110         parent = child->parent();
111     }
112     return extraWidth;
113 }
114
115 static void determineParagraphDirection(TextDirection& dir, InlineIterator iter)
116 {
117     while (!iter.atEnd()) {
118         if (iter.atParagraphSeparator())
119             return;
120         if (UChar current = iter.current()) {
121             Direction charDirection = direction(current);
122             if (charDirection == LeftToRight) {
123                 dir = LTR;
124                 return;
125             }
126             if (charDirection == RightToLeft || charDirection == RightToLeftArabic) {
127                 dir = RTL;
128                 return;
129             }
130         }
131         iter.increment();
132     }
133 }
134
135 static void checkMidpoints(LineMidpointState& lineMidpointState, InlineIterator& lBreak)
136 {
137     // Check to see if our last midpoint is a start point beyond the line break.  If so,
138     // shave it off the list, and shave off a trailing space if the previous end point doesn't
139     // preserve whitespace.
140     if (lBreak.m_obj && lineMidpointState.numMidpoints && !(lineMidpointState.numMidpoints % 2)) {
141         InlineIterator* midpoints = lineMidpointState.midpoints.data();
142         InlineIterator& endpoint = midpoints[lineMidpointState.numMidpoints - 2];
143         const InlineIterator& startpoint = midpoints[lineMidpointState.numMidpoints - 1];
144         InlineIterator currpoint = endpoint;
145         while (!currpoint.atEnd() && currpoint != startpoint && currpoint != lBreak)
146             currpoint.increment();
147         if (currpoint == lBreak) {
148             // We hit the line break before the start point.  Shave off the start point.
149             lineMidpointState.numMidpoints--;
150             if (endpoint.m_obj->style()->collapseWhiteSpace())
151                 endpoint.m_pos--;
152         }
153     }
154 }
155
156 static void addMidpoint(LineMidpointState& lineMidpointState, const InlineIterator& midpoint)
157 {
158     if (lineMidpointState.midpoints.size() <= lineMidpointState.numMidpoints)
159         lineMidpointState.midpoints.grow(lineMidpointState.numMidpoints + 10);
160
161     InlineIterator* midpoints = lineMidpointState.midpoints.data();
162     midpoints[lineMidpointState.numMidpoints++] = midpoint;
163 }
164
165 static inline BidiRun* createRun(int start, int end, RenderObject* obj, InlineBidiResolver& resolver)
166 {
167     return new (obj->renderArena()) BidiRun(start, end, obj, resolver.context(), resolver.dir());
168 }
169
170 void RenderBlock::appendRunsForObject(BidiRunList<BidiRun>& runs, int start, int end, RenderObject* obj, InlineBidiResolver& resolver)
171 {
172     if (start > end || obj->isFloating() ||
173         (obj->isPositioned() && !obj->style()->isOriginalDisplayInlineType() && !obj->container()->isRenderInline()))
174         return;
175
176     LineMidpointState& lineMidpointState = resolver.midpointState();
177     bool haveNextMidpoint = (lineMidpointState.currentMidpoint < lineMidpointState.numMidpoints);
178     InlineIterator nextMidpoint;
179     if (haveNextMidpoint)
180         nextMidpoint = lineMidpointState.midpoints[lineMidpointState.currentMidpoint];
181     if (lineMidpointState.betweenMidpoints) {
182         if (!(haveNextMidpoint && nextMidpoint.m_obj == obj))
183             return;
184         // This is a new start point. Stop ignoring objects and
185         // adjust our start.
186         lineMidpointState.betweenMidpoints = false;
187         start = nextMidpoint.m_pos;
188         lineMidpointState.currentMidpoint++;
189         if (start < end)
190             return appendRunsForObject(runs, start, end, obj, resolver);
191     } else {
192         if (!haveNextMidpoint || (obj != nextMidpoint.m_obj)) {
193             runs.addRun(createRun(start, end, obj, resolver));
194             return;
195         }
196
197         // An end midpoint has been encountered within our object.  We
198         // need to go ahead and append a run with our endpoint.
199         if (static_cast<int>(nextMidpoint.m_pos + 1) <= end) {
200             lineMidpointState.betweenMidpoints = true;
201             lineMidpointState.currentMidpoint++;
202             if (nextMidpoint.m_pos != UINT_MAX) { // UINT_MAX means stop at the object and don't include any of it.
203                 if (static_cast<int>(nextMidpoint.m_pos + 1) > start)
204                     runs.addRun(createRun(start, nextMidpoint.m_pos + 1, obj, resolver));
205                 return appendRunsForObject(runs, nextMidpoint.m_pos + 1, end, obj, resolver);
206             }
207         } else
208            runs.addRun(createRun(start, end, obj, resolver));
209     }
210 }
211
212 static inline InlineBox* createInlineBoxForRenderer(RenderObject* obj, bool isRootLineBox, bool isOnlyRun = false)
213 {
214     if (isRootLineBox)
215         return toRenderBlock(obj)->createAndAppendRootInlineBox();
216
217     if (obj->isText()) {
218         InlineTextBox* textBox = toRenderText(obj)->createInlineTextBox();
219         // We only treat a box as text for a <br> if we are on a line by ourself or in strict mode
220         // (Note the use of strict mode.  In "almost strict" mode, we don't treat the box for <br> as text.)
221         if (obj->isBR())
222             textBox->setIsText(isOnlyRun || obj->document()->inNoQuirksMode());
223         return textBox;
224     }
225
226     if (obj->isBox())
227         return toRenderBox(obj)->createInlineBox();
228
229     return toRenderInline(obj)->createAndAppendInlineFlowBox();
230 }
231
232 static inline void dirtyLineBoxesForRenderer(RenderObject* o, bool fullLayout)
233 {
234     if (o->isText()) {
235         if (o->preferredLogicalWidthsDirty() && (o->isCounter() || o->isQuote()))
236             toRenderText(o)->computePreferredLogicalWidths(0); // FIXME: Counters depend on this hack. No clue why. Should be investigated and removed.
237         toRenderText(o)->dirtyLineBoxes(fullLayout);
238     } else
239         toRenderInline(o)->dirtyLineBoxes(fullLayout);
240 }
241
242 static bool parentIsConstructedOrHaveNext(InlineFlowBox* parentBox)
243 {
244     do {
245         if (parentBox->isConstructed() || parentBox->nextOnLine())
246             return true;
247         parentBox = parentBox->parent();
248     } while (parentBox);
249     return false;
250 }
251
252 InlineFlowBox* RenderBlock::createLineBoxes(RenderObject* obj, const LineInfo& lineInfo, InlineBox* childBox)
253 {
254     // See if we have an unconstructed line box for this object that is also
255     // the last item on the line.
256     unsigned lineDepth = 1;
257     InlineFlowBox* parentBox = 0;
258     InlineFlowBox* result = 0;
259     bool hasDefaultLineBoxContain = style()->lineBoxContain() == RenderStyle::initialLineBoxContain();
260     do {
261         ASSERT(obj->isRenderInline() || obj == this);
262
263         RenderInline* inlineFlow = (obj != this) ? toRenderInline(obj) : 0;
264
265         // Get the last box we made for this render object.
266         parentBox = inlineFlow ? inlineFlow->lastLineBox() : toRenderBlock(obj)->lastLineBox();
267
268         // If this box or its ancestor is constructed then it is from a previous line, and we need
269         // to make a new box for our line.  If this box or its ancestor is unconstructed but it has
270         // something following it on the line, then we know we have to make a new box
271         // as well.  In this situation our inline has actually been split in two on
272         // the same line (this can happen with very fancy language mixtures).
273         bool constructedNewBox = false;
274         bool allowedToConstructNewBox = !hasDefaultLineBoxContain || !inlineFlow || inlineFlow->alwaysCreateLineBoxes();
275         bool canUseExistingParentBox = parentBox && !parentIsConstructedOrHaveNext(parentBox);
276         if (allowedToConstructNewBox && !canUseExistingParentBox) {
277             // We need to make a new box for this render object.  Once
278             // made, we need to place it at the end of the current line.
279             InlineBox* newBox = createInlineBoxForRenderer(obj, obj == this);
280             ASSERT(newBox->isInlineFlowBox());
281             parentBox = toInlineFlowBox(newBox);
282             parentBox->setFirstLineStyleBit(lineInfo.isFirstLine());
283             parentBox->setIsHorizontal(isHorizontalWritingMode());
284             if (!hasDefaultLineBoxContain)
285                 parentBox->clearDescendantsHaveSameLineHeightAndBaseline();
286             constructedNewBox = true;
287         }
288
289         if (constructedNewBox || canUseExistingParentBox) {
290             if (!result)
291                 result = parentBox;
292
293             // If we have hit the block itself, then |box| represents the root
294             // inline box for the line, and it doesn't have to be appended to any parent
295             // inline.
296             if (childBox)
297                 parentBox->addToLine(childBox);
298
299             if (!constructedNewBox || obj == this)
300                 break;
301
302             childBox = parentBox;
303         }
304
305         // If we've exceeded our line depth, then jump straight to the root and skip all the remaining
306         // intermediate inline flows.
307         obj = (++lineDepth >= cMaxLineDepth) ? this : obj->parent();
308
309     } while (true);
310
311     return result;
312 }
313
314 static bool reachedEndOfTextRenderer(const BidiRunList<BidiRun>& bidiRuns)
315 {
316     BidiRun* run = bidiRuns.logicallyLastRun();
317     if (!run)
318         return true;
319     unsigned int pos = run->stop();
320     RenderObject* r = run->m_object;
321     if (!r->isText() || r->isBR())
322         return false;
323     RenderText* renderText = toRenderText(r);
324     if (pos >= renderText->textLength())
325         return true;
326
327     while (isASCIISpace(renderText->characters()[pos])) {
328         pos++;
329         if (pos >= renderText->textLength())
330             return true;
331     }
332     return false;
333 }
334
335 RootInlineBox* RenderBlock::constructLine(BidiRunList<BidiRun>& bidiRuns, const LineInfo& lineInfo)
336 {
337     ASSERT(bidiRuns.firstRun());
338
339     bool rootHasSelectedChildren = false;
340     InlineFlowBox* parentBox = 0;
341     for (BidiRun* r = bidiRuns.firstRun(); r; r = r->next()) {
342         // Create a box for our object.
343         bool isOnlyRun = (bidiRuns.runCount() == 1);
344         if (bidiRuns.runCount() == 2 && !r->m_object->isListMarker())
345             isOnlyRun = (!style()->isLeftToRightDirection() ? bidiRuns.lastRun() : bidiRuns.firstRun())->m_object->isListMarker();
346
347         InlineBox* box = createInlineBoxForRenderer(r->m_object, false, isOnlyRun);
348         r->m_box = box;
349
350         ASSERT(box);
351         if (!box)
352             continue;
353
354         if (!rootHasSelectedChildren && box->renderer()->selectionState() != RenderObject::SelectionNone)
355             rootHasSelectedChildren = true;
356
357         // If we have no parent box yet, or if the run is not simply a sibling,
358         // then we need to construct inline boxes as necessary to properly enclose the
359         // run's inline box.
360         if (!parentBox || parentBox->renderer() != r->m_object->parent())
361             // Create new inline boxes all the way back to the appropriate insertion point.
362             parentBox = createLineBoxes(r->m_object->parent(), lineInfo, box);
363         else {
364             // Append the inline box to this line.
365             parentBox->addToLine(box);
366         }
367
368         bool visuallyOrdered = r->m_object->style()->rtlOrdering() == VisualOrder;
369         box->setBidiLevel(r->level());
370
371         if (box->isInlineTextBox()) {
372             InlineTextBox* text = toInlineTextBox(box);
373             text->setStart(r->m_start);
374             text->setLen(r->m_stop - r->m_start);
375             text->m_dirOverride = r->dirOverride(visuallyOrdered);
376             if (r->m_hasHyphen)
377                 text->setHasHyphen(true);
378         }
379     }
380
381     // We should have a root inline box.  It should be unconstructed and
382     // be the last continuation of our line list.
383     ASSERT(lastLineBox() && !lastLineBox()->isConstructed());
384
385     // Set the m_selectedChildren flag on the root inline box if one of the leaf inline box
386     // from the bidi runs walk above has a selection state.
387     if (rootHasSelectedChildren)
388         lastLineBox()->root()->setHasSelectedChildren(true);
389
390     // Set bits on our inline flow boxes that indicate which sides should
391     // paint borders/margins/padding.  This knowledge will ultimately be used when
392     // we determine the horizontal positions and widths of all the inline boxes on
393     // the line.
394     bool isLogicallyLastRunWrapped = bidiRuns.logicallyLastRun()->m_object && bidiRuns.logicallyLastRun()->m_object->isText() ? !reachedEndOfTextRenderer(bidiRuns) : true;
395     lastLineBox()->determineSpacingForFlowBoxes(lineInfo.isLastLine(), isLogicallyLastRunWrapped, bidiRuns.logicallyLastRun()->m_object);
396
397     // Now mark the line boxes as being constructed.
398     lastLineBox()->setConstructed();
399
400     // Return the last line.
401     return lastRootBox();
402 }
403
404 ETextAlign RenderBlock::textAlignmentForLine(bool endsWithSoftBreak) const
405 {
406     ETextAlign alignment = style()->textAlign();
407     if (!endsWithSoftBreak && alignment == JUSTIFY)
408         alignment = TAAUTO;
409
410     return alignment;
411 }
412
413 static void updateLogicalWidthForLeftAlignedBlock(bool isLeftToRightDirection, BidiRun* trailingSpaceRun, float& logicalLeft, float& totalLogicalWidth, float availableLogicalWidth)
414 {
415     // The direction of the block should determine what happens with wide lines.
416     // In particular with RTL blocks, wide lines should still spill out to the left.
417     if (isLeftToRightDirection) {
418         if (totalLogicalWidth > availableLogicalWidth && trailingSpaceRun)
419             trailingSpaceRun->m_box->setLogicalWidth(max<float>(0, trailingSpaceRun->m_box->logicalWidth() - totalLogicalWidth + availableLogicalWidth));
420         return;
421     }
422
423     if (trailingSpaceRun)
424         trailingSpaceRun->m_box->setLogicalWidth(0);
425     else if (totalLogicalWidth > availableLogicalWidth)
426         logicalLeft -= (totalLogicalWidth - availableLogicalWidth);
427 }
428
429 static void updateLogicalWidthForRightAlignedBlock(bool isLeftToRightDirection, BidiRun* trailingSpaceRun, float& logicalLeft, float& totalLogicalWidth, float availableLogicalWidth)
430 {
431     // Wide lines spill out of the block based off direction.
432     // So even if text-align is right, if direction is LTR, wide lines should overflow out of the right
433     // side of the block.
434     if (isLeftToRightDirection) {
435         if (trailingSpaceRun) {
436             totalLogicalWidth -= trailingSpaceRun->m_box->logicalWidth();
437             trailingSpaceRun->m_box->setLogicalWidth(0);
438         }
439         if (totalLogicalWidth < availableLogicalWidth)
440             logicalLeft += availableLogicalWidth - totalLogicalWidth;
441         return;
442     }
443
444     if (totalLogicalWidth > availableLogicalWidth && trailingSpaceRun) {
445         trailingSpaceRun->m_box->setLogicalWidth(max<float>(0, trailingSpaceRun->m_box->logicalWidth() - totalLogicalWidth + availableLogicalWidth));
446         totalLogicalWidth -= trailingSpaceRun->m_box->logicalWidth();
447     } else
448         logicalLeft += availableLogicalWidth - totalLogicalWidth;
449 }
450
451 static void updateLogicalWidthForCenterAlignedBlock(bool isLeftToRightDirection, BidiRun* trailingSpaceRun, float& logicalLeft, float& totalLogicalWidth, float availableLogicalWidth)
452 {
453     float trailingSpaceWidth = 0;
454     if (trailingSpaceRun) {
455         totalLogicalWidth -= trailingSpaceRun->m_box->logicalWidth();
456         trailingSpaceWidth = min(trailingSpaceRun->m_box->logicalWidth(), (availableLogicalWidth - totalLogicalWidth + 1) / 2);
457         trailingSpaceRun->m_box->setLogicalWidth(max<float>(0, trailingSpaceWidth));
458     }
459     if (isLeftToRightDirection)
460         logicalLeft += max<float>((availableLogicalWidth - totalLogicalWidth) / 2, 0);
461     else
462         logicalLeft += totalLogicalWidth > availableLogicalWidth ? (availableLogicalWidth - totalLogicalWidth) : (availableLogicalWidth - totalLogicalWidth) / 2 - trailingSpaceWidth;
463 }
464
465 void RenderBlock::setMarginsForRubyRun(BidiRun* run, RenderRubyRun* renderer, RenderObject* previousObject, const LineInfo& lineInfo)
466 {
467     int startOverhang;
468     int endOverhang;
469     RenderObject* nextObject = 0;
470     for (BidiRun* runWithNextObject = run->next(); runWithNextObject; runWithNextObject = runWithNextObject->next()) {
471         if (!runWithNextObject->m_object->isPositioned() && !runWithNextObject->m_box->isLineBreak()) {
472             nextObject = runWithNextObject->m_object;
473             break;
474         }
475     }
476     renderer->getOverhang(lineInfo.isFirstLine(), renderer->style()->isLeftToRightDirection() ? previousObject : nextObject, renderer->style()->isLeftToRightDirection() ? nextObject : previousObject, startOverhang, endOverhang);
477     setMarginStartForChild(renderer, -startOverhang);
478     setMarginEndForChild(renderer, -endOverhang);
479 }
480
481 static inline void setLogicalWidthForTextRun(RootInlineBox* lineBox, BidiRun* run, RenderText* renderer, float xPos, const LineInfo& lineInfo,
482                                    GlyphOverflowAndFallbackFontsMap& textBoxDataMap, VerticalPositionCache& verticalPositionCache)
483 {
484     HashSet<const SimpleFontData*> fallbackFonts;
485     GlyphOverflow glyphOverflow;
486     
487     // Always compute glyph overflow if the block's line-box-contain value is "glyphs".
488     if (lineBox->fitsToGlyphs()) {
489         // If we don't stick out of the root line's font box, then don't bother computing our glyph overflow. This optimization
490         // will keep us from computing glyph bounds in nearly all cases.
491         bool includeRootLine = lineBox->includesRootLineBoxFontOrLeading();
492         int baselineShift = lineBox->verticalPositionForBox(run->m_box, verticalPositionCache);
493         int rootDescent = includeRootLine ? lineBox->renderer()->style(lineInfo.isFirstLine())->font().fontMetrics().descent() : 0;
494         int rootAscent = includeRootLine ? lineBox->renderer()->style(lineInfo.isFirstLine())->font().fontMetrics().ascent() : 0;
495         int boxAscent = renderer->style(lineInfo.isFirstLine())->font().fontMetrics().ascent() - baselineShift;
496         int boxDescent = renderer->style(lineInfo.isFirstLine())->font().fontMetrics().descent() + baselineShift;
497         if (boxAscent > rootDescent ||  boxDescent > rootAscent)
498             glyphOverflow.computeBounds = true; 
499     }
500     
501     int hyphenWidth = 0;
502     if (toInlineTextBox(run->m_box)->hasHyphen()) {
503         const AtomicString& hyphenString = renderer->style()->hyphenString();
504         const Font& font = renderer->style(lineInfo.isFirstLine())->font();
505         hyphenWidth = font.width(RenderBlock::constructTextRun(renderer, font, hyphenString.string(), renderer->style()));
506     }
507     run->m_box->setLogicalWidth(renderer->width(run->m_start, run->m_stop - run->m_start, xPos, lineInfo.isFirstLine(), &fallbackFonts, &glyphOverflow) + hyphenWidth);
508     if (!fallbackFonts.isEmpty()) {
509         ASSERT(run->m_box->isText());
510         GlyphOverflowAndFallbackFontsMap::iterator it = textBoxDataMap.add(toInlineTextBox(run->m_box), make_pair(Vector<const SimpleFontData*>(), GlyphOverflow())).first;
511         ASSERT(it->second.first.isEmpty());
512         copyToVector(fallbackFonts, it->second.first);
513         run->m_box->parent()->clearDescendantsHaveSameLineHeightAndBaseline();
514     }
515     if ((glyphOverflow.top || glyphOverflow.bottom || glyphOverflow.left || glyphOverflow.right)) {
516         ASSERT(run->m_box->isText());
517         GlyphOverflowAndFallbackFontsMap::iterator it = textBoxDataMap.add(toInlineTextBox(run->m_box), make_pair(Vector<const SimpleFontData*>(), GlyphOverflow())).first;
518         it->second.second = glyphOverflow;
519         run->m_box->clearKnownToHaveNoOverflow();
520     }
521 }
522
523 static inline void computeExpansionForJustifiedText(BidiRun* firstRun, BidiRun* trailingSpaceRun, Vector<unsigned, 16>& expansionOpportunities, unsigned expansionOpportunityCount, float& totalLogicalWidth, float availableLogicalWidth)
524 {
525     if (!expansionOpportunityCount || availableLogicalWidth <= totalLogicalWidth)
526         return;
527
528     size_t i = 0;
529     for (BidiRun* r = firstRun; r; r = r->next()) {
530         if (!r->m_box || r == trailingSpaceRun)
531             continue;
532         
533         if (r->m_object->isText()) {
534             unsigned opportunitiesInRun = expansionOpportunities[i++];
535             
536             ASSERT(opportunitiesInRun <= expansionOpportunityCount);
537             
538             // Only justify text if whitespace is collapsed.
539             if (r->m_object->style()->collapseWhiteSpace()) {
540                 InlineTextBox* textBox = toInlineTextBox(r->m_box);
541                 int expansion = (availableLogicalWidth - totalLogicalWidth) * opportunitiesInRun / expansionOpportunityCount;
542                 textBox->setExpansion(expansion);
543                 totalLogicalWidth += expansion;
544             }
545             expansionOpportunityCount -= opportunitiesInRun;
546             if (!expansionOpportunityCount)
547                 break;
548         }
549     }
550 }
551
552 void RenderBlock::computeInlineDirectionPositionsForLine(RootInlineBox* lineBox, const LineInfo& lineInfo, BidiRun* firstRun, BidiRun* trailingSpaceRun, bool reachedEnd,
553                                                          GlyphOverflowAndFallbackFontsMap& textBoxDataMap, VerticalPositionCache& verticalPositionCache)
554 {
555     ETextAlign textAlign = textAlignmentForLine(!reachedEnd && !lineBox->endsWithBreak());
556     float logicalLeft = logicalLeftOffsetForLine(logicalHeight(), lineInfo.isFirstLine());
557     float availableLogicalWidth = logicalRightOffsetForLine(logicalHeight(), lineInfo.isFirstLine()) - logicalLeft;
558
559     bool needsWordSpacing = false;
560     float totalLogicalWidth = lineBox->getFlowSpacingLogicalWidth();
561     unsigned expansionOpportunityCount = 0;
562     bool isAfterExpansion = true;
563     Vector<unsigned, 16> expansionOpportunities;
564     RenderObject* previousObject = 0;
565
566     for (BidiRun* r = firstRun; r; r = r->next()) {
567         if (!r->m_box || r->m_object->isPositioned() || r->m_box->isLineBreak())
568             continue; // Positioned objects are only participating to figure out their
569                       // correct static x position.  They have no effect on the width.
570                       // Similarly, line break boxes have no effect on the width.
571         if (r->m_object->isText()) {
572             RenderText* rt = toRenderText(r->m_object);
573             if (textAlign == JUSTIFY && r != trailingSpaceRun) {
574                 if (!isAfterExpansion)
575                     toInlineTextBox(r->m_box)->setCanHaveLeadingExpansion(true);
576                 unsigned opportunitiesInRun = Font::expansionOpportunityCount(rt->characters() + r->m_start, r->m_stop - r->m_start, r->m_box->direction(), isAfterExpansion);
577                 expansionOpportunities.append(opportunitiesInRun);
578                 expansionOpportunityCount += opportunitiesInRun;
579             }
580
581             if (int length = rt->textLength()) {
582                 if (!r->m_start && needsWordSpacing && isSpaceOrNewline(rt->characters()[r->m_start]))
583                     totalLogicalWidth += rt->style(lineInfo.isFirstLine())->font().wordSpacing();
584                 needsWordSpacing = !isSpaceOrNewline(rt->characters()[r->m_stop - 1]) && r->m_stop == length;
585             }
586
587             setLogicalWidthForTextRun(lineBox, r, rt, totalLogicalWidth, lineInfo, textBoxDataMap, verticalPositionCache);
588         } else {
589             isAfterExpansion = false;
590             if (!r->m_object->isRenderInline()) {
591                 RenderBox* renderBox = toRenderBox(r->m_object);
592                 if (renderBox->isRubyRun())
593                     setMarginsForRubyRun(r, toRenderRubyRun(renderBox), previousObject, lineInfo);
594                 r->m_box->setLogicalWidth(logicalWidthForChild(renderBox));
595                 totalLogicalWidth += marginStartForChild(renderBox) + marginEndForChild(renderBox);
596             }
597         }
598
599         totalLogicalWidth += r->m_box->logicalWidth();
600         previousObject = r->m_object;
601     }
602
603     if (isAfterExpansion && !expansionOpportunities.isEmpty()) {
604         expansionOpportunities.last()--;
605         expansionOpportunityCount--;
606     }
607
608     // Armed with the total width of the line (without justification),
609     // we now examine our text-align property in order to determine where to position the
610     // objects horizontally.  The total width of the line can be increased if we end up
611     // justifying text.
612     switch (textAlign) {
613         case LEFT:
614         case WEBKIT_LEFT:
615             updateLogicalWidthForLeftAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
616             break;
617         case JUSTIFY:
618             adjustInlineDirectionLineBounds(expansionOpportunityCount, logicalLeft, availableLogicalWidth);
619             if (expansionOpportunityCount) {
620                 if (trailingSpaceRun) {
621                     totalLogicalWidth -= trailingSpaceRun->m_box->logicalWidth();
622                     trailingSpaceRun->m_box->setLogicalWidth(0);
623                 }
624                 break;
625             }
626             // fall through
627         case TAAUTO:
628             // for right to left fall through to right aligned
629             if (style()->isLeftToRightDirection()) {
630                 if (totalLogicalWidth > availableLogicalWidth && trailingSpaceRun)
631                     trailingSpaceRun->m_box->setLogicalWidth(max<float>(0, trailingSpaceRun->m_box->logicalWidth() - totalLogicalWidth + availableLogicalWidth));
632                 break;
633             }
634         case RIGHT:
635         case WEBKIT_RIGHT:
636             updateLogicalWidthForRightAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
637             break;
638         case CENTER:
639         case WEBKIT_CENTER:
640             updateLogicalWidthForCenterAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
641             break;
642         case TASTART:
643             if (style()->isLeftToRightDirection())
644                 updateLogicalWidthForLeftAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
645             else
646                 updateLogicalWidthForRightAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
647             break;
648         case TAEND:
649             if (style()->isLeftToRightDirection())
650                 updateLogicalWidthForRightAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
651             else
652                 updateLogicalWidthForLeftAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
653             break;
654     }
655
656     computeExpansionForJustifiedText(firstRun, trailingSpaceRun, expansionOpportunities, expansionOpportunityCount, totalLogicalWidth, availableLogicalWidth);
657
658     // The widths of all runs are now known.  We can now place every inline box (and
659     // compute accurate widths for the inline flow boxes).
660     needsWordSpacing = false;
661     lineBox->placeBoxesInInlineDirection(logicalLeft, needsWordSpacing, textBoxDataMap);
662 }
663
664 void RenderBlock::computeBlockDirectionPositionsForLine(RootInlineBox* lineBox, BidiRun* firstRun, GlyphOverflowAndFallbackFontsMap& textBoxDataMap,
665                                                         VerticalPositionCache& verticalPositionCache)
666 {
667     setLogicalHeight(lineBox->alignBoxesInBlockDirection(logicalHeight(), textBoxDataMap, verticalPositionCache));
668     lineBox->setBlockLogicalHeight(logicalHeight());
669
670     // Now make sure we place replaced render objects correctly.
671     for (BidiRun* r = firstRun; r; r = r->next()) {
672         ASSERT(r->m_box);
673         if (!r->m_box)
674             continue; // Skip runs with no line boxes.
675
676         // Align positioned boxes with the top of the line box.  This is
677         // a reasonable approximation of an appropriate y position.
678         if (r->m_object->isPositioned())
679             r->m_box->setLogicalTop(logicalHeight());
680
681         // Position is used to properly position both replaced elements and
682         // to update the static normal flow x/y of positioned elements.
683         if (r->m_object->isText())
684             toRenderText(r->m_object)->positionLineBox(r->m_box);
685         else if (r->m_object->isBox())
686             toRenderBox(r->m_object)->positionLineBox(r->m_box);
687     }
688     // Positioned objects and zero-length text nodes destroy their boxes in
689     // position(), which unnecessarily dirties the line.
690     lineBox->markDirty(false);
691 }
692
693 static inline bool isCollapsibleSpace(UChar character, RenderText* renderer)
694 {
695     if (character == ' ' || character == '\t' || character == softHyphen)
696         return true;
697     if (character == '\n')
698         return !renderer->style()->preserveNewline();
699     if (character == noBreakSpace)
700         return renderer->style()->nbspMode() == SPACE;
701     return false;
702 }
703
704
705 static void setStaticPositions(RenderBlock* block, RenderBox* child)
706 {
707     // FIXME: The math here is actually not really right. It's a best-guess approximation that
708     // will work for the common cases
709     RenderObject* containerBlock = child->container();
710     int blockHeight = block->logicalHeight();
711     if (containerBlock->isRenderInline()) {
712         // A relative positioned inline encloses us. In this case, we also have to determine our
713         // position as though we were an inline. Set |staticInlinePosition| and |staticBlockPosition| on the relative positioned
714         // inline so that we can obtain the value later.
715         toRenderInline(containerBlock)->layer()->setStaticInlinePosition(block->startOffsetForLine(blockHeight, false));
716         toRenderInline(containerBlock)->layer()->setStaticBlockPosition(blockHeight);
717     }
718
719     if (child->style()->isOriginalDisplayInlineType())
720         child->layer()->setStaticInlinePosition(block->startOffsetForLine(blockHeight, false));
721     else
722         child->layer()->setStaticInlinePosition(block->borderAndPaddingStart());
723     child->layer()->setStaticBlockPosition(blockHeight);
724 }
725
726 inline BidiRun* RenderBlock::handleTrailingSpaces(BidiRunList<BidiRun>& bidiRuns, BidiContext* currentContext)
727 {
728     if (!bidiRuns.runCount()
729         || !bidiRuns.logicallyLastRun()->m_object->style()->breakOnlyAfterWhiteSpace()
730         || !bidiRuns.logicallyLastRun()->m_object->style()->autoWrap())
731         return 0;
732
733     BidiRun* trailingSpaceRun = bidiRuns.logicallyLastRun();
734     RenderObject* lastObject = trailingSpaceRun->m_object;
735     if (!lastObject->isText())
736         return 0;
737
738     RenderText* lastText = toRenderText(lastObject);
739     const UChar* characters = lastText->characters();
740     int firstSpace = trailingSpaceRun->stop();
741     while (firstSpace > trailingSpaceRun->start()) {
742         UChar current = characters[firstSpace - 1];
743         if (!isCollapsibleSpace(current, lastText))
744             break;
745         firstSpace--;
746     }
747     if (firstSpace == trailingSpaceRun->stop())
748         return 0;
749
750     TextDirection direction = style()->direction();
751     bool shouldReorder = trailingSpaceRun != (direction == LTR ? bidiRuns.lastRun() : bidiRuns.firstRun());
752     if (firstSpace != trailingSpaceRun->start()) {
753         BidiContext* baseContext = currentContext;
754         while (BidiContext* parent = baseContext->parent())
755             baseContext = parent;
756
757         BidiRun* newTrailingRun = new (renderArena()) BidiRun(firstSpace, trailingSpaceRun->m_stop, trailingSpaceRun->m_object, baseContext, OtherNeutral);
758         trailingSpaceRun->m_stop = firstSpace;
759         if (direction == LTR)
760             bidiRuns.addRun(newTrailingRun);
761         else
762             bidiRuns.prependRun(newTrailingRun);
763         trailingSpaceRun = newTrailingRun;
764         return trailingSpaceRun;
765     }
766     if (!shouldReorder)
767         return trailingSpaceRun;
768
769     if (direction == LTR) {
770         bidiRuns.moveRunToEnd(trailingSpaceRun);
771         trailingSpaceRun->m_level = 0;
772     } else {
773         bidiRuns.moveRunToBeginning(trailingSpaceRun);
774         trailingSpaceRun->m_level = 1;
775     }
776     return trailingSpaceRun;
777 }
778
779 void RenderBlock::appendFloatingObjectToLastLine(FloatingObject* floatingObject)
780 {
781     ASSERT(!floatingObject->m_originatingLine);
782     floatingObject->m_originatingLine = lastRootBox();
783     lastRootBox()->appendFloat(floatingObject->renderer());
784 }
785
786 // This function constructs line boxes for all of the text runs in the resolver and computes their position.
787 RootInlineBox* RenderBlock::createLineBoxesFromBidiRuns(BidiRunList<BidiRun>& bidiRuns, const InlineIterator& end, LineInfo& lineInfo, VerticalPositionCache& verticalPositionCache, BidiRun* trailingSpaceRun)
788 {
789     if (!bidiRuns.runCount())
790         return 0;
791
792     // FIXME: Why is this only done when we had runs?
793     lineInfo.setLastLine(!end.m_obj);
794
795     RootInlineBox* lineBox = constructLine(bidiRuns, lineInfo);
796     if (!lineBox)
797         return 0;
798
799     lineBox->setEndsWithBreak(lineInfo.previousLineBrokeCleanly());
800     
801 #if ENABLE(SVG)
802     bool isSVGRootInlineBox = lineBox->isSVGRootInlineBox();
803 #else
804     bool isSVGRootInlineBox = false;
805 #endif
806     
807     GlyphOverflowAndFallbackFontsMap textBoxDataMap;
808     
809     // Now we position all of our text runs horizontally.
810     if (!isSVGRootInlineBox)
811         computeInlineDirectionPositionsForLine(lineBox, lineInfo, bidiRuns.firstRun(), trailingSpaceRun, end.atEnd(), textBoxDataMap, verticalPositionCache);
812     
813     // Now position our text runs vertically.
814     computeBlockDirectionPositionsForLine(lineBox, bidiRuns.firstRun(), textBoxDataMap, verticalPositionCache);
815     
816 #if ENABLE(SVG)
817     // SVG text layout code computes vertical & horizontal positions on its own.
818     // Note that we still need to execute computeVerticalPositionsForLine() as
819     // it calls InlineTextBox::positionLineBox(), which tracks whether the box
820     // contains reversed text or not. If we wouldn't do that editing and thus
821     // text selection in RTL boxes would not work as expected.
822     if (isSVGRootInlineBox) {
823         ASSERT(isSVGText());
824         static_cast<SVGRootInlineBox*>(lineBox)->computePerCharacterLayoutInformation();
825     }
826 #endif
827     
828     // Compute our overflow now.
829     lineBox->computeOverflow(lineBox->lineTop(), lineBox->lineBottom(), textBoxDataMap);
830     
831 #if PLATFORM(MAC)
832     // Highlight acts as an overflow inflation.
833     if (style()->highlight() != nullAtom)
834         lineBox->addHighlightOverflow();
835 #endif
836     return lineBox;
837 }
838
839 // Like LayoutState for layout(), LineLayoutState keeps track of global information
840 // during an entire linebox tree layout pass (aka layoutInlineChildren).
841 class LineLayoutState {
842 public:
843     LineLayoutState(bool fullLayout, int& repaintLogicalTop, int& repaintLogicalBottom)
844         : m_lastFloat(0)
845         , m_endLine(0)
846         , m_floatIndex(0)
847         , m_endLineLogicalTop(0)
848         , m_endLineMatched(false)
849         , m_checkForFloatsFromLastLine(false)
850         , m_isFullLayout(fullLayout)
851         , m_repaintLogicalTop(repaintLogicalTop)
852         , m_repaintLogicalBottom(repaintLogicalBottom)
853         , m_usesRepaintBounds(false)
854     { }
855
856     void markForFullLayout() { m_isFullLayout = true; }
857     bool isFullLayout() const { return m_isFullLayout; }
858
859     bool usesRepaintBounds() const { return m_usesRepaintBounds; }
860
861     void setRepaintRange(int logicalHeight)
862     { 
863         m_usesRepaintBounds = true;
864         m_repaintLogicalTop = m_repaintLogicalBottom = logicalHeight; 
865     }
866     
867     void updateRepaintRangeFromBox(RootInlineBox* box, int paginationDelta = 0)
868     {
869         m_usesRepaintBounds = true;
870         m_repaintLogicalTop = min(m_repaintLogicalTop, box->logicalTopVisualOverflow() + min(paginationDelta, 0));
871         m_repaintLogicalBottom = max(m_repaintLogicalBottom, box->logicalBottomVisualOverflow() + max(paginationDelta, 0));
872     }
873     
874     bool endLineMatched() const { return m_endLineMatched; }
875     void setEndLineMatched(bool endLineMatched) { m_endLineMatched = endLineMatched; }
876
877     bool checkForFloatsFromLastLine() const { return m_checkForFloatsFromLastLine; }
878     void setCheckForFloatsFromLastLine(bool check) { m_checkForFloatsFromLastLine = check; }
879
880     LineInfo& lineInfo() { return m_lineInfo; }
881     const LineInfo& lineInfo() const { return m_lineInfo; }
882
883     int endLineLogicalTop() const { return m_endLineLogicalTop; }
884     void setEndLineLogicalTop(int logicalTop) { m_endLineLogicalTop = logicalTop; }
885
886     RootInlineBox* endLine() const { return m_endLine; }
887     void setEndLine(RootInlineBox* line) { m_endLine = line; }
888
889     RenderBlock::FloatingObject* lastFloat() const { return m_lastFloat; }
890     void setLastFloat(RenderBlock::FloatingObject* lastFloat) { m_lastFloat = lastFloat; }
891
892     Vector<RenderBlock::FloatWithRect>& floats() { return m_floats; }
893     
894     unsigned floatIndex() const { return m_floatIndex; }
895     void setFloatIndex(unsigned floatIndex) { m_floatIndex = floatIndex; }
896     
897 private:
898     Vector<RenderBlock::FloatWithRect> m_floats;
899     RenderBlock::FloatingObject* m_lastFloat;
900     RootInlineBox* m_endLine;
901     LineInfo m_lineInfo;
902     unsigned m_floatIndex;
903     int m_endLineLogicalTop;
904     bool m_endLineMatched;
905     bool m_checkForFloatsFromLastLine;
906     
907     bool m_isFullLayout;
908
909     // FIXME: Should this be a range object instead of two ints?
910     int& m_repaintLogicalTop;
911     int& m_repaintLogicalBottom;
912     
913     bool m_usesRepaintBounds;
914 };
915
916 static void deleteLineRange(LineLayoutState& layoutState, RenderArena* arena, RootInlineBox* startLine, RootInlineBox* stopLine = 0)
917 {
918     RootInlineBox* boxToDelete = startLine;
919     while (boxToDelete && boxToDelete != stopLine) {
920         layoutState.updateRepaintRangeFromBox(boxToDelete);
921         // Note: deleteLineRange(renderArena(), firstRootBox()) is not identical to deleteLineBoxTree().
922         // deleteLineBoxTree uses nextLineBox() instead of nextRootBox() when traversing.
923         RootInlineBox* next = boxToDelete->nextRootBox();
924         boxToDelete->deleteLine(arena);
925         boxToDelete = next;
926     }
927 }
928
929 void RenderBlock::layoutRunsAndFloats(LineLayoutState& layoutState, bool hasInlineChild)
930 {
931     // We want to skip ahead to the first dirty line
932     InlineBidiResolver resolver;
933     RootInlineBox* startLine = determineStartPosition(layoutState, resolver);
934
935     // FIXME: This would make more sense outside of this function, but since
936     // determineStartPosition can change the fullLayout flag we have to do this here. Failure to call
937     // determineStartPosition first will break fast/repaint/line-flow-with-floats-9.html.
938     if (layoutState.isFullLayout() && hasInlineChild && !selfNeedsLayout()) {
939         setNeedsLayout(true, false);  // Mark ourselves as needing a full layout. This way we'll repaint like
940         // we're supposed to.
941         RenderView* v = view();
942         if (v && !v->doingFullRepaint() && hasLayer()) {
943             // Because we waited until we were already inside layout to discover
944             // that the block really needed a full layout, we missed our chance to repaint the layer
945             // before layout started.  Luckily the layer has cached the repaint rect for its original
946             // position and size, and so we can use that to make a repaint happen now.
947             repaintUsingContainer(containerForRepaint(), layer()->repaintRect());
948         }
949     }
950
951     if (m_floatingObjects && !m_floatingObjects->set().isEmpty())
952         layoutState.setLastFloat(m_floatingObjects->set().last());
953
954     // We also find the first clean line and extract these lines.  We will add them back
955     // if we determine that we're able to synchronize after handling all our dirty lines.
956     InlineIterator cleanLineStart;
957     BidiStatus cleanLineBidiStatus;
958     if (!layoutState.isFullLayout() && startLine)
959         determineEndPosition(layoutState, startLine, cleanLineStart, cleanLineBidiStatus);
960
961     if (startLine) {
962         if (!layoutState.usesRepaintBounds())
963             layoutState.setRepaintRange(logicalHeight());
964         deleteLineRange(layoutState, renderArena(), startLine);
965     }
966
967     if (!layoutState.isFullLayout() && lastRootBox() && lastRootBox()->endsWithBreak()) {
968         // If the last line before the start line ends with a line break that clear floats,
969         // adjust the height accordingly.
970         // A line break can be either the first or the last object on a line, depending on its direction.
971         if (InlineBox* lastLeafChild = lastRootBox()->lastLeafChild()) {
972             RenderObject* lastObject = lastLeafChild->renderer();
973             if (!lastObject->isBR())
974                 lastObject = lastRootBox()->firstLeafChild()->renderer();
975             if (lastObject->isBR()) {
976                 EClear clear = lastObject->style()->clear();
977                 if (clear != CNONE)
978                     newLine(clear);
979             }
980         }
981     }
982
983     layoutRunsAndFloatsInRange(layoutState, resolver, cleanLineStart, cleanLineBidiStatus);
984     linkToEndLineIfNeeded(layoutState);
985     repaintDirtyFloats(layoutState.floats());
986 }
987
988 void RenderBlock::layoutRunsAndFloatsInRange(LineLayoutState& layoutState, InlineBidiResolver& resolver, const InlineIterator& cleanLineStart, const BidiStatus& cleanLineBidiStatus)
989 {
990     bool paginated = view()->layoutState() && view()->layoutState()->isPaginated();
991     LineMidpointState& lineMidpointState = resolver.midpointState();
992     InlineIterator end = resolver.position();
993     bool checkForEndLineMatch = layoutState.endLine();
994     LineBreakIteratorInfo lineBreakIteratorInfo;
995     VerticalPositionCache verticalPositionCache;
996
997     LineBreaker lineBreaker(this);
998
999     while (!end.atEnd()) {
1000         // FIXME: Is this check necessary before the first iteration or can it be moved to the end?
1001         if (checkForEndLineMatch) {
1002             layoutState.setEndLineMatched(matchedEndLine(layoutState, resolver, cleanLineStart, cleanLineBidiStatus));
1003             if (layoutState.endLineMatched())
1004                 break;
1005         }
1006
1007         lineMidpointState.reset();
1008
1009         layoutState.lineInfo().setEmpty(true);
1010
1011         InlineIterator oldEnd = end;
1012         bool isNewUBAParagraph = layoutState.lineInfo().previousLineBrokeCleanly();
1013         FloatingObject* lastFloatFromPreviousLine = (m_floatingObjects && !m_floatingObjects->set().isEmpty()) ? m_floatingObjects->set().last() : 0;
1014         end = lineBreaker.nextLineBreak(resolver, layoutState.lineInfo(), lineBreakIteratorInfo, lastFloatFromPreviousLine);
1015         if (resolver.position().atEnd()) {
1016             // FIXME: We shouldn't be creating any runs in findNextLineBreak to begin with!
1017             // Once BidiRunList is separated from BidiResolver this will not be needed.
1018             resolver.runs().deleteRuns();
1019             resolver.markCurrentRunEmpty(); // FIXME: This can probably be replaced by an ASSERT (or just removed).
1020             layoutState.setCheckForFloatsFromLastLine(true);
1021             break;
1022         }
1023         ASSERT(end != resolver.position());
1024
1025         // This is a short-cut for empty lines.
1026         if (layoutState.lineInfo().isEmpty()) {
1027             if (lastRootBox())
1028                 lastRootBox()->setLineBreakInfo(end.m_obj, end.m_pos, resolver.status());
1029         } else {
1030             VisualDirectionOverride override = (style()->rtlOrdering() == VisualOrder ? (style()->direction() == LTR ? VisualLeftToRightOverride : VisualRightToLeftOverride) : NoVisualOverride);
1031
1032             if (isNewUBAParagraph && style()->unicodeBidi() == Plaintext && !resolver.context()->parent()) {
1033                 TextDirection direction = style()->direction();
1034                 determineParagraphDirection(direction, resolver.position());
1035                 resolver.setStatus(BidiStatus(direction, style()->unicodeBidi() == Override));
1036             }
1037             // FIXME: This ownership is reversed. We should own the BidiRunList and pass it to createBidiRunsForLine.
1038             BidiRunList<BidiRun>& bidiRuns = resolver.runs();
1039             resolver.createBidiRunsForLine(end, override, layoutState.lineInfo().previousLineBrokeCleanly());
1040             ASSERT(resolver.position() == end);
1041
1042             BidiRun* trailingSpaceRun = !layoutState.lineInfo().previousLineBrokeCleanly() ? handleTrailingSpaces(bidiRuns, resolver.context()) : 0;
1043
1044             if (bidiRuns.runCount() && lineBreaker.lineWasHyphenated())
1045                 bidiRuns.logicallyLastRun()->m_hasHyphen = true;
1046
1047             // Now that the runs have been ordered, we create the line boxes.
1048             // At the same time we figure out where border/padding/margin should be applied for
1049             // inline flow boxes.
1050
1051             int oldLogicalHeight = logicalHeight();
1052             RootInlineBox* lineBox = createLineBoxesFromBidiRuns(bidiRuns, end, layoutState.lineInfo(), verticalPositionCache, trailingSpaceRun);
1053
1054             bidiRuns.deleteRuns();
1055             resolver.markCurrentRunEmpty(); // FIXME: This can probably be replaced by an ASSERT (or just removed).
1056
1057             if (lineBox) {
1058                 lineBox->setLineBreakInfo(end.m_obj, end.m_pos, resolver.status());
1059                 if (layoutState.usesRepaintBounds())
1060                     layoutState.updateRepaintRangeFromBox(lineBox);
1061
1062                 if (paginated) {
1063                     int adjustment = 0;
1064                     adjustLinePositionForPagination(lineBox, adjustment);
1065                     if (adjustment) {
1066                         int oldLineWidth = availableLogicalWidthForLine(oldLogicalHeight, layoutState.lineInfo().isFirstLine());
1067                         lineBox->adjustBlockDirectionPosition(adjustment);
1068                         if (layoutState.usesRepaintBounds())
1069                             layoutState.updateRepaintRangeFromBox(lineBox);
1070
1071                         if (availableLogicalWidthForLine(oldLogicalHeight + adjustment, layoutState.lineInfo().isFirstLine()) != oldLineWidth) {
1072                             // We have to delete this line, remove all floats that got added, and let line layout re-run.
1073                             lineBox->deleteLine(renderArena());
1074                             removeFloatingObjectsBelow(lastFloatFromPreviousLine, oldLogicalHeight);
1075                             setLogicalHeight(oldLogicalHeight + adjustment);
1076                             resolver.setPosition(oldEnd);
1077                             end = oldEnd;
1078                             continue;
1079                         }
1080
1081                         setLogicalHeight(lineBox->blockLogicalHeight());
1082                     }
1083                 }
1084             }
1085
1086             for (size_t i = 0; i < lineBreaker.positionedObjects().size(); ++i)
1087                 setStaticPositions(this, lineBreaker.positionedObjects()[i]);
1088
1089             layoutState.lineInfo().setFirstLine(false);
1090             newLine(lineBreaker.clear());
1091         }
1092
1093         if (m_floatingObjects && lastRootBox()) {
1094             const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1095             FloatingObjectSetIterator it = floatingObjectSet.begin();
1096             FloatingObjectSetIterator end = floatingObjectSet.end();
1097             if (layoutState.lastFloat()) {
1098                 FloatingObjectSetIterator lastFloatIterator = floatingObjectSet.find(layoutState.lastFloat());
1099                 ASSERT(lastFloatIterator != end);
1100                 ++lastFloatIterator;
1101                 it = lastFloatIterator;
1102             }
1103             for (; it != end; ++it) {
1104                 FloatingObject* f = *it;
1105                 appendFloatingObjectToLastLine(f);
1106                 ASSERT(f->m_renderer == layoutState.floats()[layoutState.floatIndex()].object);
1107                 // If a float's geometry has changed, give up on syncing with clean lines.
1108                 if (layoutState.floats()[layoutState.floatIndex()].rect != f->frameRect())
1109                     checkForEndLineMatch = false;
1110                 layoutState.setFloatIndex(layoutState.floatIndex() + 1);
1111             }
1112             layoutState.setLastFloat(!floatingObjectSet.isEmpty() ? floatingObjectSet.last() : 0);
1113         }
1114
1115         lineMidpointState.reset();
1116         resolver.setPosition(end);
1117     }
1118 }
1119
1120 void RenderBlock::linkToEndLineIfNeeded(LineLayoutState& layoutState)
1121 {
1122     if (layoutState.endLine()) {
1123         if (layoutState.endLineMatched()) {
1124             bool paginated = view()->layoutState() && view()->layoutState()->isPaginated();
1125             // Attach all the remaining lines, and then adjust their y-positions as needed.
1126             int delta = logicalHeight() - layoutState.endLineLogicalTop();
1127             for (RootInlineBox* line = layoutState.endLine(); line; line = line->nextRootBox()) {
1128                 line->attachLine();
1129                 if (paginated) {
1130                     delta -= line->paginationStrut();
1131                     adjustLinePositionForPagination(line, delta);
1132                 }
1133                 if (delta) {
1134                     layoutState.updateRepaintRangeFromBox(line, delta);
1135                     line->adjustBlockDirectionPosition(delta);
1136                 }
1137                 if (Vector<RenderBox*>* cleanLineFloats = line->floatsPtr()) {
1138                     Vector<RenderBox*>::iterator end = cleanLineFloats->end();
1139                     for (Vector<RenderBox*>::iterator f = cleanLineFloats->begin(); f != end; ++f) {
1140                         FloatingObject* floatingObject = insertFloatingObject(*f);
1141                         ASSERT(!floatingObject->m_originatingLine);
1142                         floatingObject->m_originatingLine = line;
1143                         setLogicalHeight(logicalTopForChild(*f) - marginBeforeForChild(*f) + delta);
1144                         positionNewFloats();
1145                     }
1146                 }
1147             }
1148             setLogicalHeight(lastRootBox()->blockLogicalHeight());
1149         } else {
1150             // Delete all the remaining lines.
1151             deleteLineRange(layoutState, renderArena(), layoutState.endLine());
1152         }
1153     }
1154     
1155     if (m_floatingObjects && (layoutState.checkForFloatsFromLastLine() || positionNewFloats()) && lastRootBox()) {
1156         // In case we have a float on the last line, it might not be positioned up to now.
1157         // This has to be done before adding in the bottom border/padding, or the float will
1158         // include the padding incorrectly. -dwh
1159         if (layoutState.checkForFloatsFromLastLine()) {
1160             int bottomVisualOverflow = lastRootBox()->logicalBottomVisualOverflow();
1161             int bottomLayoutOverflow = lastRootBox()->logicalBottomLayoutOverflow();
1162             TrailingFloatsRootInlineBox* trailingFloatsLineBox = new (renderArena()) TrailingFloatsRootInlineBox(this);
1163             m_lineBoxes.appendLineBox(trailingFloatsLineBox);
1164             trailingFloatsLineBox->setConstructed();
1165             GlyphOverflowAndFallbackFontsMap textBoxDataMap;
1166             VerticalPositionCache verticalPositionCache;
1167             trailingFloatsLineBox->alignBoxesInBlockDirection(logicalHeight(), textBoxDataMap, verticalPositionCache);
1168             int blockLogicalHeight = logicalHeight();
1169             IntRect logicalLayoutOverflow(0, blockLogicalHeight, 1, bottomLayoutOverflow - blockLogicalHeight);
1170             IntRect logicalVisualOverflow(0, blockLogicalHeight, 1, bottomVisualOverflow - blockLogicalHeight);
1171             trailingFloatsLineBox->setOverflowFromLogicalRects(logicalLayoutOverflow, logicalVisualOverflow, trailingFloatsLineBox->lineTop(), trailingFloatsLineBox->lineBottom());
1172             trailingFloatsLineBox->setBlockLogicalHeight(logicalHeight());
1173         }
1174
1175         const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1176         FloatingObjectSetIterator it = floatingObjectSet.begin();
1177         FloatingObjectSetIterator end = floatingObjectSet.end();
1178         if (layoutState.lastFloat()) {
1179             FloatingObjectSetIterator lastFloatIterator = floatingObjectSet.find(layoutState.lastFloat());
1180             ASSERT(lastFloatIterator != end);
1181             ++lastFloatIterator;
1182             it = lastFloatIterator;
1183         }
1184         for (; it != end; ++it)
1185             appendFloatingObjectToLastLine(*it);
1186         layoutState.setLastFloat(!floatingObjectSet.isEmpty() ? floatingObjectSet.last() : 0);
1187     }
1188 }
1189
1190 void RenderBlock::repaintDirtyFloats(Vector<FloatWithRect>& floats)
1191 {
1192     size_t floatCount = floats.size();
1193     // Floats that did not have layout did not repaint when we laid them out. They would have
1194     // painted by now if they had moved, but if they stayed at (0, 0), they still need to be
1195     // painted.
1196     for (size_t i = 0; i < floatCount; ++i) {
1197         if (!floats[i].everHadLayout) {
1198             RenderBox* f = floats[i].object;
1199             if (!f->x() && !f->y() && f->checkForRepaintDuringLayout())
1200                 f->repaint();
1201         }
1202     }
1203 }
1204
1205 void RenderBlock::layoutInlineChildren(bool relayoutChildren, int& repaintLogicalTop, int& repaintLogicalBottom)
1206 {
1207     m_overflow.clear();
1208
1209     setLogicalHeight(borderBefore() + paddingBefore());
1210
1211     // Figure out if we should clear out our line boxes.
1212     // FIXME: Handle resize eventually!
1213     bool isFullLayout = !firstLineBox() || selfNeedsLayout() || relayoutChildren;
1214     LineLayoutState layoutState(isFullLayout, repaintLogicalTop, repaintLogicalBottom);
1215
1216     if (isFullLayout)
1217         lineBoxes()->deleteLineBoxes(renderArena());
1218
1219     // Text truncation only kicks in if your overflow isn't visible and your text-overflow-mode isn't
1220     // clip.
1221     // FIXME: CSS3 says that descendants that are clipped must also know how to truncate.  This is insanely
1222     // difficult to figure out (especially in the middle of doing layout), and is really an esoteric pile of nonsense
1223     // anyway, so we won't worry about following the draft here.
1224     bool hasTextOverflow = style()->textOverflow() && hasOverflowClip();
1225
1226     // Walk all the lines and delete our ellipsis line boxes if they exist.
1227     if (hasTextOverflow)
1228          deleteEllipsisLineBoxes();
1229
1230     if (firstChild()) {
1231         // layout replaced elements
1232         bool hasInlineChild = false;
1233         for (InlineWalker walker(this); !walker.atEnd(); walker.advance()) {
1234             RenderObject* o = walker.current();
1235             if (!hasInlineChild && o->isInline())
1236                 hasInlineChild = true;
1237
1238             if (o->isReplaced() || o->isFloating() || o->isPositioned()) {
1239                 RenderBox* box = toRenderBox(o);
1240
1241                 if (relayoutChildren || o->style()->width().isPercent() || o->style()->height().isPercent())
1242                     o->setChildNeedsLayout(true, false);
1243
1244                 // If relayoutChildren is set and the child has percentage padding or an embedded content box, we also need to invalidate the childs pref widths.
1245                 if (relayoutChildren && box->needsPreferredWidthsRecalculation())
1246                     o->setPreferredLogicalWidthsDirty(true, false);
1247
1248                 if (o->isPositioned())
1249                     o->containingBlock()->insertPositionedObject(box);
1250                 else if (o->isFloating())
1251                     layoutState.floats().append(FloatWithRect(box));
1252                 else if (layoutState.isFullLayout() || o->needsLayout()) {
1253                     // Replaced elements
1254                     toRenderBox(o)->dirtyLineBoxes(layoutState.isFullLayout());
1255                     o->layoutIfNeeded();
1256                 }
1257             } else if (o->isText() || (o->isRenderInline() && !walker.atEndOfInline())) {
1258                 if (!o->isText())
1259                     toRenderInline(o)->updateAlwaysCreateLineBoxes(layoutState.isFullLayout());
1260                 if (layoutState.isFullLayout() || o->selfNeedsLayout())
1261                     dirtyLineBoxesForRenderer(o, layoutState.isFullLayout());
1262                 o->setNeedsLayout(false);
1263             }
1264         }
1265
1266         layoutRunsAndFloats(layoutState, hasInlineChild);
1267     }
1268
1269     // Expand the last line to accommodate Ruby and emphasis marks.
1270     int lastLineAnnotationsAdjustment = 0;
1271     if (lastRootBox()) {
1272         int lowestAllowedPosition = max(lastRootBox()->lineBottom(), logicalHeight() + paddingAfter());
1273         if (!style()->isFlippedLinesWritingMode())
1274             lastLineAnnotationsAdjustment = lastRootBox()->computeUnderAnnotationAdjustment(lowestAllowedPosition);
1275         else
1276             lastLineAnnotationsAdjustment = lastRootBox()->computeOverAnnotationAdjustment(lowestAllowedPosition);
1277     }
1278
1279     // Now add in the bottom border/padding.
1280     setLogicalHeight(logicalHeight() + lastLineAnnotationsAdjustment + borderAfter() + paddingAfter() + scrollbarLogicalHeight());
1281
1282     if (!firstLineBox() && hasLineIfEmpty())
1283         setLogicalHeight(logicalHeight() + lineHeight(true, isHorizontalWritingMode() ? HorizontalLine : VerticalLine, PositionOfInteriorLineBoxes));
1284
1285     // See if we have any lines that spill out of our block.  If we do, then we will possibly need to
1286     // truncate text.
1287     if (hasTextOverflow)
1288         checkLinesForTextOverflow();
1289 }
1290
1291 void RenderBlock::checkFloatsInCleanLine(RootInlineBox* line, Vector<FloatWithRect>& floats, size_t& floatIndex, bool& encounteredNewFloat, bool& dirtiedByFloat)
1292 {
1293     Vector<RenderBox*>* cleanLineFloats = line->floatsPtr();
1294     if (!cleanLineFloats)
1295         return;
1296
1297     Vector<RenderBox*>::iterator end = cleanLineFloats->end();
1298     for (Vector<RenderBox*>::iterator it = cleanLineFloats->begin(); it != end; ++it) {
1299         RenderBox* floatingBox = *it;
1300         floatingBox->layoutIfNeeded();
1301         IntSize newSize(floatingBox->width() + floatingBox->marginLeft() + floatingBox->marginRight(), floatingBox->height() + floatingBox->marginTop() + floatingBox->marginBottom());
1302         ASSERT(floatIndex < floats.size());
1303         if (floats[floatIndex].object != floatingBox) {
1304             encounteredNewFloat = true;
1305             return;
1306         }
1307
1308         if (floats[floatIndex].rect.size() != newSize) {
1309             int floatTop = isHorizontalWritingMode() ? floats[floatIndex].rect.y() : floats[floatIndex].rect.x();
1310             int floatHeight = isHorizontalWritingMode() ? max(floats[floatIndex].rect.height(), newSize.height())
1311                                                                  : max(floats[floatIndex].rect.width(), newSize.width());
1312             floatHeight = min(floatHeight, numeric_limits<int>::max() - floatTop);
1313             line->markDirty();
1314             markLinesDirtyInBlockRange(line->blockLogicalHeight(), floatTop + floatHeight, line);
1315             floats[floatIndex].rect.setSize(newSize);
1316             dirtiedByFloat = true;
1317         }
1318         floatIndex++;
1319     }
1320 }
1321
1322 RootInlineBox* RenderBlock::determineStartPosition(LineLayoutState& layoutState, InlineBidiResolver& resolver)
1323 {
1324     RootInlineBox* curr = 0;
1325     RootInlineBox* last = 0;
1326
1327     // FIXME: This entire float-checking block needs to be broken into a new function.
1328     bool dirtiedByFloat = false;
1329     if (!layoutState.isFullLayout()) {
1330         // Paginate all of the clean lines.
1331         bool paginated = view()->layoutState() && view()->layoutState()->isPaginated();
1332         int paginationDelta = 0;
1333         size_t floatIndex = 0;
1334         for (curr = firstRootBox(); curr && !curr->isDirty(); curr = curr->nextRootBox()) {
1335             if (paginated) {
1336                 paginationDelta -= curr->paginationStrut();
1337                 adjustLinePositionForPagination(curr, paginationDelta);
1338                 if (paginationDelta) {
1339                     if (containsFloats() || !layoutState.floats().isEmpty()) {
1340                         // FIXME: Do better eventually.  For now if we ever shift because of pagination and floats are present just go to a full layout.
1341                         layoutState.markForFullLayout();
1342                         break;
1343                     }
1344
1345                     layoutState.updateRepaintRangeFromBox(curr, paginationDelta);
1346                     curr->adjustBlockDirectionPosition(paginationDelta);
1347                 }
1348             }
1349
1350             // If a new float has been inserted before this line or before its last known float, just do a full layout.
1351             bool encounteredNewFloat = false;
1352             checkFloatsInCleanLine(curr, layoutState.floats(), floatIndex, encounteredNewFloat, dirtiedByFloat);
1353             if (encounteredNewFloat)
1354                 layoutState.markForFullLayout();
1355
1356             if (dirtiedByFloat || layoutState.isFullLayout())
1357                 break;
1358         }
1359         // Check if a new float has been inserted after the last known float.
1360         if (!curr && floatIndex < layoutState.floats().size())
1361             layoutState.markForFullLayout();
1362     }
1363
1364     if (layoutState.isFullLayout()) {
1365         // FIXME: This should just call deleteLineBoxTree, but that causes
1366         // crashes for fast/repaint tests.
1367         RenderArena* arena = renderArena();
1368         curr = firstRootBox();
1369         while (curr) {
1370             // Note: This uses nextRootBox() insted of nextLineBox() like deleteLineBoxTree does.
1371             RootInlineBox* next = curr->nextRootBox();
1372             curr->deleteLine(arena);
1373             curr = next;
1374         }
1375         ASSERT(!firstLineBox() && !lastLineBox());
1376     } else {
1377         if (curr) {
1378             // We have a dirty line.
1379             if (RootInlineBox* prevRootBox = curr->prevRootBox()) {
1380                 // We have a previous line.
1381                 if (!dirtiedByFloat && (!prevRootBox->endsWithBreak() || (prevRootBox->lineBreakObj()->isText() && prevRootBox->lineBreakPos() >= toRenderText(prevRootBox->lineBreakObj())->textLength())))
1382                     // The previous line didn't break cleanly or broke at a newline
1383                     // that has been deleted, so treat it as dirty too.
1384                     curr = prevRootBox;
1385             }
1386         } else {
1387             // No dirty lines were found.
1388             // If the last line didn't break cleanly, treat it as dirty.
1389             if (lastRootBox() && !lastRootBox()->endsWithBreak())
1390                 curr = lastRootBox();
1391         }
1392
1393         // If we have no dirty lines, then last is just the last root box.
1394         last = curr ? curr->prevRootBox() : lastRootBox();
1395     }
1396
1397     unsigned numCleanFloats = 0;
1398     if (!layoutState.floats().isEmpty()) {
1399         int savedLogicalHeight = logicalHeight();
1400         // Restore floats from clean lines.
1401         RootInlineBox* line = firstRootBox();
1402         while (line != curr) {
1403             if (Vector<RenderBox*>* cleanLineFloats = line->floatsPtr()) {
1404                 Vector<RenderBox*>::iterator end = cleanLineFloats->end();
1405                 for (Vector<RenderBox*>::iterator f = cleanLineFloats->begin(); f != end; ++f) {
1406                     FloatingObject* floatingObject = insertFloatingObject(*f);
1407                     ASSERT(!floatingObject->m_originatingLine);
1408                     floatingObject->m_originatingLine = line;
1409                     setLogicalHeight(logicalTopForChild(*f) - marginBeforeForChild(*f));
1410                     positionNewFloats();
1411                     ASSERT(layoutState.floats()[numCleanFloats].object == *f);
1412                     numCleanFloats++;
1413                 }
1414             }
1415             line = line->nextRootBox();
1416         }
1417         setLogicalHeight(savedLogicalHeight);
1418     }
1419     layoutState.setFloatIndex(numCleanFloats);
1420
1421     layoutState.lineInfo().setFirstLine(!last);
1422     layoutState.lineInfo().setPreviousLineBrokeCleanly(!last || last->endsWithBreak());
1423
1424     if (last) {
1425         setLogicalHeight(last->blockLogicalHeight());
1426         resolver.setPosition(InlineIterator(this, last->lineBreakObj(), last->lineBreakPos()));
1427         resolver.setStatus(last->lineBreakBidiStatus());
1428     } else {
1429         TextDirection direction = style()->direction();
1430         if (style()->unicodeBidi() == Plaintext)
1431             determineParagraphDirection(direction, InlineIterator(this, bidiFirstNotSkippingInlines(this), 0));
1432         resolver.setStatus(BidiStatus(direction, style()->unicodeBidi() == Override));
1433         resolver.setPosition(InlineIterator(this, bidiFirstSkippingInlines(this, &resolver), 0));
1434     }
1435     return curr;
1436 }
1437
1438 void RenderBlock::determineEndPosition(LineLayoutState& layoutState, RootInlineBox* startLine, InlineIterator& cleanLineStart, BidiStatus& cleanLineBidiStatus)
1439 {
1440     ASSERT(!layoutState.endLine());
1441     size_t floatIndex = layoutState.floatIndex();
1442     RootInlineBox* last = 0;
1443     for (RootInlineBox* curr = startLine->nextRootBox(); curr; curr = curr->nextRootBox()) {
1444         if (!curr->isDirty()) {
1445             bool encounteredNewFloat = false;
1446             bool dirtiedByFloat = false;
1447             checkFloatsInCleanLine(curr, layoutState.floats(), floatIndex, encounteredNewFloat, dirtiedByFloat);
1448             if (encounteredNewFloat)
1449                 return;
1450         }
1451         if (curr->isDirty())
1452             last = 0;
1453         else if (!last)
1454             last = curr;
1455     }
1456
1457     if (!last)
1458         return;
1459
1460     // At this point, |last| is the first line in a run of clean lines that ends with the last line
1461     // in the block.
1462
1463     RootInlineBox* prev = last->prevRootBox();
1464     cleanLineStart = InlineIterator(this, prev->lineBreakObj(), prev->lineBreakPos());
1465     cleanLineBidiStatus = prev->lineBreakBidiStatus();
1466     layoutState.setEndLineLogicalTop(prev->blockLogicalHeight());
1467
1468     for (RootInlineBox* line = last; line; line = line->nextRootBox())
1469         line->extractLine(); // Disconnect all line boxes from their render objects while preserving
1470                              // their connections to one another.
1471
1472     layoutState.setEndLine(last);
1473 }
1474
1475 bool RenderBlock::matchedEndLine(LineLayoutState& layoutState, const InlineBidiResolver& resolver, const InlineIterator& endLineStart, const BidiStatus& endLineStatus)
1476 {
1477     if (resolver.position() == endLineStart) {
1478         if (resolver.status() != endLineStatus)
1479             return false;
1480
1481         int delta = logicalHeight() - layoutState.endLineLogicalTop();
1482         if (!delta || !m_floatingObjects)
1483             return true;
1484
1485         // See if any floats end in the range along which we want to shift the lines vertically.
1486         int logicalTop = min(logicalHeight(), layoutState.endLineLogicalTop());
1487
1488         RootInlineBox* lastLine = layoutState.endLine();
1489         while (RootInlineBox* nextLine = lastLine->nextRootBox())
1490             lastLine = nextLine;
1491
1492         int logicalBottom = lastLine->blockLogicalHeight() + abs(delta);
1493
1494         const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1495         FloatingObjectSetIterator end = floatingObjectSet.end();
1496         for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
1497             FloatingObject* f = *it;
1498             if (logicalBottomForFloat(f) >= logicalTop && logicalBottomForFloat(f) < logicalBottom)
1499                 return false;
1500         }
1501
1502         return true;
1503     }
1504
1505     // The first clean line doesn't match, but we can check a handful of following lines to try
1506     // to match back up.
1507     static int numLines = 8; // The # of lines we're willing to match against.
1508     RootInlineBox* line = layoutState.endLine();
1509     for (int i = 0; i < numLines && line; i++, line = line->nextRootBox()) {
1510         if (line->lineBreakObj() == resolver.position().m_obj && line->lineBreakPos() == resolver.position().m_pos) {
1511             // We have a match.
1512             if (line->lineBreakBidiStatus() != resolver.status())
1513                 return false; // ...but the bidi state doesn't match.
1514             RootInlineBox* result = line->nextRootBox();
1515
1516             // Set our logical top to be the block height of endLine.
1517             if (result)
1518                 layoutState.setEndLineLogicalTop(line->blockLogicalHeight());
1519
1520             int delta = logicalHeight() - layoutState.endLineLogicalTop();
1521             if (delta && m_floatingObjects) {
1522                 // See if any floats end in the range along which we want to shift the lines vertically.
1523                 int logicalTop = min(logicalHeight(), layoutState.endLineLogicalTop());
1524
1525                 RootInlineBox* lastLine = layoutState.endLine();
1526                 while (RootInlineBox* nextLine = lastLine->nextRootBox())
1527                     lastLine = nextLine;
1528
1529                 int logicalBottom = lastLine->blockLogicalHeight() + abs(delta);
1530
1531                 const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1532                 FloatingObjectSetIterator end = floatingObjectSet.end();
1533                 for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
1534                     FloatingObject* f = *it;
1535                     if (logicalBottomForFloat(f) >= logicalTop && logicalBottomForFloat(f) < logicalBottom)
1536                         return false;
1537                 }
1538             }
1539
1540             // Now delete the lines that we failed to sync.
1541             deleteLineRange(layoutState, renderArena(), layoutState.endLine(), result);
1542             layoutState.setEndLine(result);
1543             return result;
1544         }
1545     }
1546
1547     return false;
1548 }
1549
1550 static inline bool skipNonBreakingSpace(const InlineIterator& it, const LineInfo& lineInfo)
1551 {
1552     if (it.m_obj->style()->nbspMode() != SPACE || it.current() != noBreakSpace)
1553         return false;
1554
1555     // FIXME: This is bad.  It makes nbsp inconsistent with space and won't work correctly
1556     // with m_minWidth/m_maxWidth.
1557     // Do not skip a non-breaking space if it is the first character
1558     // on a line after a clean line break (or on the first line, since previousLineBrokeCleanly starts off
1559     // |true|).
1560     if (lineInfo.isEmpty() && lineInfo.previousLineBrokeCleanly())
1561         return false;
1562
1563     return true;
1564 }
1565
1566 enum WhitespacePosition { LeadingWhitespace, TrailingWhitespace };
1567 static inline bool shouldCollapseWhiteSpace(const RenderStyle* style, const LineInfo& lineInfo, WhitespacePosition whitespacePosition)
1568 {
1569     // CSS2 16.6.1
1570     // If a space (U+0020) at the beginning of a line has 'white-space' set to 'normal', 'nowrap', or 'pre-line', it is removed.
1571     // 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.
1572     // 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.
1573     return style->collapseWhiteSpace()
1574         || (whitespacePosition == TrailingWhitespace && style->whiteSpace() == PRE_WRAP && (!lineInfo.isEmpty() || !lineInfo.previousLineBrokeCleanly()));
1575 }
1576
1577 static bool inlineFlowRequiresLineBox(RenderInline* flow)
1578 {
1579     // FIXME: Right now, we only allow line boxes for inlines that are truly empty.
1580     // We need to fix this, though, because at the very least, inlines containing only
1581     // ignorable whitespace should should also have line boxes.
1582     return !flow->firstChild() && flow->hasInlineDirectionBordersPaddingOrMargin();
1583 }
1584
1585 static bool requiresLineBox(const InlineIterator& it, const LineInfo& lineInfo = LineInfo(), WhitespacePosition whitespacePosition = LeadingWhitespace)
1586 {
1587     if (it.m_obj->isFloatingOrPositioned())
1588         return false;
1589
1590     if (it.m_obj->isRenderInline() && !inlineFlowRequiresLineBox(toRenderInline(it.m_obj)))
1591         return false;
1592
1593     if (!shouldCollapseWhiteSpace(it.m_obj->style(), lineInfo, whitespacePosition) || it.m_obj->isBR())
1594         return true;
1595
1596     UChar current = it.current();
1597     return current != ' ' && current != '\t' && current != softHyphen && (current != '\n' || it.m_obj->preservesNewline())
1598     && !skipNonBreakingSpace(it, lineInfo);
1599 }
1600
1601 bool RenderBlock::generatesLineBoxesForInlineChild(RenderObject* inlineObj)
1602 {
1603     ASSERT(inlineObj->parent() == this);
1604
1605     InlineIterator it(this, inlineObj, 0);
1606     // FIXME: We should pass correct value for WhitespacePosition.
1607     while (!it.atEnd() && !requiresLineBox(it))
1608         it.increment();
1609
1610     return !it.atEnd();
1611 }
1612
1613 // FIXME: The entire concept of the skipTrailingWhitespace function is flawed, since we really need to be building
1614 // line boxes even for containers that may ultimately collapse away. Otherwise we'll never get positioned
1615 // elements quite right. In other words, we need to build this function's work into the normal line
1616 // object iteration process.
1617 // NB. this function will insert any floating elements that would otherwise
1618 // be skipped but it will not position them.
1619 void RenderBlock::LineBreaker::skipTrailingWhitespace(InlineIterator& iterator, const LineInfo& lineInfo)
1620 {
1621     while (!iterator.atEnd() && !requiresLineBox(iterator, lineInfo, TrailingWhitespace)) {
1622         RenderObject* object = iterator.m_obj;
1623         if (object->isFloating()) {
1624             m_block->insertFloatingObject(toRenderBox(object));
1625         } else if (object->isPositioned())
1626             setStaticPositions(m_block, toRenderBox(object));
1627         iterator.increment();
1628     }
1629 }
1630
1631 void RenderBlock::LineBreaker::skipLeadingWhitespace(InlineBidiResolver& resolver, const LineInfo& lineInfo,
1632                                                      FloatingObject* lastFloatFromPreviousLine, LineWidth& width)
1633 {
1634     while (!resolver.position().atEnd() && !requiresLineBox(resolver.position(), lineInfo, LeadingWhitespace)) {
1635         RenderObject* object = resolver.position().m_obj;
1636         if (object->isFloating())
1637             m_block->positionNewFloatOnLine(m_block->insertFloatingObject(toRenderBox(object)), lastFloatFromPreviousLine, width);
1638         else if (object->isPositioned())
1639             setStaticPositions(m_block, toRenderBox(object));
1640         resolver.increment();
1641     }
1642     resolver.commitExplicitEmbedding();
1643 }
1644
1645 // This is currently just used for list markers and inline flows that have line boxes. Neither should
1646 // have an effect on whitespace at the start of the line.
1647 static bool shouldSkipWhitespaceAfterStartObject(RenderBlock* block, RenderObject* o, LineMidpointState& lineMidpointState)
1648 {
1649     RenderObject* next = bidiNext(block, o);
1650     if (next && !next->isBR() && next->isText() && toRenderText(next)->textLength() > 0) {
1651         RenderText* nextText = toRenderText(next);
1652         UChar nextChar = nextText->characters()[0];
1653         if (nextText->style()->isCollapsibleWhiteSpace(nextChar)) {
1654             addMidpoint(lineMidpointState, InlineIterator(0, o, 0));
1655             return true;
1656         }
1657     }
1658
1659     return false;
1660 }
1661
1662 static inline float textWidth(RenderText* text, unsigned from, unsigned len, const Font& font, float xPos, bool isFixedPitch, bool collapseWhiteSpace)
1663 {
1664     if (isFixedPitch || (!from && len == text->textLength()) || text->style()->hasTextCombine())
1665         return text->width(from, len, font, xPos);
1666
1667     TextRun run = RenderBlock::constructTextRun(text, font, text->characters() + from, len, text->style());
1668     run.setCharactersLength(text->textLength() - from);
1669     ASSERT(run.charactersLength() >= run.length());
1670
1671     run.setAllowTabs(!collapseWhiteSpace);
1672     run.setXPos(xPos);
1673     return font.width(run);
1674 }
1675
1676 static void tryHyphenating(RenderText* text, const Font& font, const AtomicString& localeIdentifier, int minimumPrefixLength, int minimumSuffixLength, int lastSpace, int pos, float xPos, int availableWidth, bool isFixedPitch, bool collapseWhiteSpace, int lastSpaceWordSpacing, InlineIterator& lineBreak, int nextBreakable, bool& hyphenated)
1677 {
1678     // Map 'hyphenate-limit-{before,after}: auto;' to 2.
1679     if (minimumPrefixLength < 0)
1680         minimumPrefixLength = 2;
1681
1682     if (minimumSuffixLength < 0)
1683         minimumSuffixLength = 2;
1684
1685     if (pos - lastSpace <= minimumSuffixLength)
1686         return;
1687
1688     const AtomicString& hyphenString = text->style()->hyphenString();
1689     int hyphenWidth = font.width(RenderBlock::constructTextRun(text, font, hyphenString.string(), text->style()));
1690
1691     float maxPrefixWidth = availableWidth - xPos - hyphenWidth - lastSpaceWordSpacing;
1692     // If the maximum width available for the prefix before the hyphen is small, then it is very unlikely
1693     // that an hyphenation opportunity exists, so do not bother to look for it.
1694     if (maxPrefixWidth <= font.pixelSize() * 5 / 4)
1695         return;
1696
1697     TextRun run = RenderBlock::constructTextRun(text, font, text->characters() + lastSpace, pos - lastSpace, text->style());
1698     run.setCharactersLength(text->textLength() - lastSpace);
1699     ASSERT(run.charactersLength() >= run.length());
1700
1701     run.setAllowTabs(!collapseWhiteSpace);
1702     run.setXPos(xPos + lastSpaceWordSpacing);
1703
1704     unsigned prefixLength = font.offsetForPosition(run, maxPrefixWidth, false);
1705     if (prefixLength < static_cast<unsigned>(minimumPrefixLength))
1706         return;
1707
1708     prefixLength = lastHyphenLocation(text->characters() + lastSpace, pos - lastSpace, min(prefixLength, static_cast<unsigned>(pos - lastSpace - minimumSuffixLength)) + 1, localeIdentifier);
1709     // FIXME: The following assumes that the character at lastSpace is a space (and therefore should not factor
1710     // into hyphenate-limit-before) unless lastSpace is 0. This is wrong in the rare case of hyphenating
1711     // the first word in a text node which has leading whitespace.
1712     if (!prefixLength || prefixLength - (lastSpace ? 1 : 0) < static_cast<unsigned>(minimumPrefixLength))
1713         return;
1714
1715     ASSERT(pos - lastSpace - prefixLength >= static_cast<unsigned>(minimumSuffixLength));
1716
1717 #if !ASSERT_DISABLED
1718     float prefixWidth = hyphenWidth + textWidth(text, lastSpace, prefixLength, font, xPos, isFixedPitch, collapseWhiteSpace) + lastSpaceWordSpacing;
1719     ASSERT(xPos + prefixWidth <= availableWidth);
1720 #else
1721     UNUSED_PARAM(isFixedPitch);
1722 #endif
1723
1724     lineBreak.moveTo(text, lastSpace + prefixLength, nextBreakable);
1725     hyphenated = true;
1726 }
1727
1728 class LineWidth {
1729 public:
1730     LineWidth(RenderBlock* block, bool isFirstLine)
1731         : m_block(block)
1732         , m_uncommittedWidth(0)
1733         , m_committedWidth(0)
1734         , m_overhangWidth(0)
1735         , m_left(0)
1736         , m_right(0)
1737         , m_availableWidth(0)
1738         , m_isFirstLine(isFirstLine)
1739     {
1740         ASSERT(block);
1741         updateAvailableWidth();
1742     }
1743     bool fitsOnLine() const { return currentWidth() <= m_availableWidth; }
1744     bool fitsOnLine(float extra) const { return currentWidth() + extra <= m_availableWidth; }
1745     float currentWidth() const { return m_committedWidth + m_uncommittedWidth; }
1746
1747     // FIXME: We should eventually replace these three functions by ones that work on a higher abstraction.
1748     float uncommittedWidth() const { return m_uncommittedWidth; }
1749     float committedWidth() const { return m_committedWidth; }
1750     float availableWidth() const { return m_availableWidth; }
1751
1752     void updateAvailableWidth();
1753     void shrinkAvailableWidthForNewFloatIfNeeded(RenderBlock::FloatingObject*);
1754     void addUncommittedWidth(float delta) { m_uncommittedWidth += delta; }
1755     void commit()
1756     {
1757         m_committedWidth += m_uncommittedWidth;
1758         m_uncommittedWidth = 0;
1759     }
1760     void applyOverhang(RenderRubyRun*, RenderObject* startRenderer, RenderObject* endRenderer);
1761     void fitBelowFloats();
1762
1763 private:
1764     void computeAvailableWidthFromLeftAndRight()
1765     {
1766         m_availableWidth = max(0, m_right - m_left) + m_overhangWidth;
1767     }
1768
1769 private:
1770     RenderBlock* m_block;
1771     float m_uncommittedWidth;
1772     float m_committedWidth;
1773     float m_overhangWidth; // The amount by which |m_availableWidth| has been inflated to account for possible contraction due to ruby overhang.
1774     int m_left;
1775     int m_right;
1776     float m_availableWidth;
1777     bool m_isFirstLine;
1778 };
1779
1780 inline void LineWidth::updateAvailableWidth()
1781 {
1782     int height = m_block->logicalHeight();
1783     m_left = m_block->logicalLeftOffsetForLine(height, m_isFirstLine);
1784     m_right = m_block->logicalRightOffsetForLine(height, m_isFirstLine);
1785
1786     computeAvailableWidthFromLeftAndRight();
1787 }
1788
1789 inline void LineWidth::shrinkAvailableWidthForNewFloatIfNeeded(RenderBlock::FloatingObject* newFloat)
1790 {
1791     int height = m_block->logicalHeight();
1792     if (height < m_block->logicalTopForFloat(newFloat) || height >= m_block->logicalBottomForFloat(newFloat))
1793         return;
1794
1795     if (newFloat->type() == RenderBlock::FloatingObject::FloatLeft)
1796         m_left = m_block->logicalRightForFloat(newFloat);
1797     else
1798         m_right = m_block->logicalLeftForFloat(newFloat);
1799
1800     computeAvailableWidthFromLeftAndRight();
1801 }
1802
1803 void LineWidth::applyOverhang(RenderRubyRun* rubyRun, RenderObject* startRenderer, RenderObject* endRenderer)
1804 {
1805     int startOverhang;
1806     int endOverhang;
1807     rubyRun->getOverhang(m_isFirstLine, startRenderer, endRenderer, startOverhang, endOverhang);
1808
1809     startOverhang = min<int>(startOverhang, m_committedWidth);
1810     m_availableWidth += startOverhang;
1811
1812     endOverhang = max(min<int>(endOverhang, m_availableWidth - currentWidth()), 0);
1813     m_availableWidth += endOverhang;
1814     m_overhangWidth += startOverhang + endOverhang;
1815 }
1816
1817 void LineWidth::fitBelowFloats()
1818 {
1819     ASSERT(!m_committedWidth);
1820     ASSERT(!fitsOnLine());
1821
1822     int floatLogicalBottom;
1823     int lastFloatLogicalBottom = m_block->logicalHeight();
1824     float newLineWidth = m_availableWidth;
1825     while (true) {
1826         floatLogicalBottom = m_block->nextFloatLogicalBottomBelow(lastFloatLogicalBottom);
1827         if (!floatLogicalBottom)
1828             break;
1829
1830         newLineWidth = m_block->availableLogicalWidthForLine(floatLogicalBottom, m_isFirstLine);
1831         lastFloatLogicalBottom = floatLogicalBottom;
1832         if (newLineWidth >= m_uncommittedWidth)
1833             break;
1834     }
1835
1836     if (newLineWidth > m_availableWidth) {
1837         m_block->setLogicalHeight(lastFloatLogicalBottom);
1838         m_availableWidth = newLineWidth + m_overhangWidth;
1839     }
1840 }
1841
1842 class TrailingObjects {
1843 public:
1844     TrailingObjects();
1845     void setTrailingWhitespace(RenderText*);
1846     void clear();
1847     void appendBoxIfNeeded(RenderBox*);
1848
1849     enum CollapseFirstSpaceOrNot { DoNotCollapseFirstSpace, CollapseFirstSpace };
1850
1851     void updateMidpointsForTrailingBoxes(LineMidpointState&, const InlineIterator& lBreak, CollapseFirstSpaceOrNot);
1852
1853 private:
1854     RenderText* m_whitespace;
1855     Vector<RenderBox*, 4> m_boxes;
1856 };
1857
1858 TrailingObjects::TrailingObjects()
1859     : m_whitespace(0)
1860 {
1861 }
1862
1863 inline void TrailingObjects::setTrailingWhitespace(RenderText* whitespace)
1864 {
1865     ASSERT(whitespace);
1866     m_whitespace = whitespace;
1867 }
1868
1869 inline void TrailingObjects::clear()
1870 {
1871     m_whitespace = 0;
1872     m_boxes.clear();
1873 }
1874
1875 inline void TrailingObjects::appendBoxIfNeeded(RenderBox* box)
1876 {
1877     if (m_whitespace)
1878         m_boxes.append(box);
1879 }
1880
1881 void TrailingObjects::updateMidpointsForTrailingBoxes(LineMidpointState& lineMidpointState, const InlineIterator& lBreak, CollapseFirstSpaceOrNot collapseFirstSpace)
1882 {
1883     if (!m_whitespace)
1884         return;
1885
1886     // This object is either going to be part of the last midpoint, or it is going to be the actual endpoint.
1887     // In both cases we just decrease our pos by 1 level to exclude the space, allowing it to - in effect - collapse into the newline.
1888     if (lineMidpointState.numMidpoints % 2) {
1889         // Find the trailing space object's midpoint.
1890         int trailingSpaceMidpoint = lineMidpointState.numMidpoints - 1;
1891         for ( ; trailingSpaceMidpoint > 0 && lineMidpointState.midpoints[trailingSpaceMidpoint].m_obj != m_whitespace; --trailingSpaceMidpoint) { }
1892         ASSERT(trailingSpaceMidpoint >= 0);
1893         if (collapseFirstSpace == CollapseFirstSpace)
1894             lineMidpointState.midpoints[trailingSpaceMidpoint].m_pos--;
1895
1896         // Now make sure every single trailingPositionedBox following the trailingSpaceMidpoint properly stops and starts
1897         // ignoring spaces.
1898         size_t currentMidpoint = trailingSpaceMidpoint + 1;
1899         for (size_t i = 0; i < m_boxes.size(); ++i) {
1900             if (currentMidpoint >= lineMidpointState.numMidpoints) {
1901                 // We don't have a midpoint for this box yet.
1902                 InlineIterator ignoreStart(0, m_boxes[i], 0);
1903                 addMidpoint(lineMidpointState, ignoreStart); // Stop ignoring.
1904                 addMidpoint(lineMidpointState, ignoreStart); // Start ignoring again.
1905             } else {
1906                 ASSERT(lineMidpointState.midpoints[currentMidpoint].m_obj == m_boxes[i]);
1907                 ASSERT(lineMidpointState.midpoints[currentMidpoint + 1].m_obj == m_boxes[i]);
1908             }
1909             currentMidpoint += 2;
1910         }
1911     } else if (!lBreak.m_obj) {
1912         ASSERT(m_whitespace->isText());
1913         ASSERT(collapseFirstSpace == CollapseFirstSpace);
1914         // Add a new end midpoint that stops right at the very end.
1915         unsigned length = m_whitespace->textLength();
1916         unsigned pos = length >= 2 ? length - 2 : UINT_MAX;
1917         InlineIterator endMid(0, m_whitespace, pos);
1918         addMidpoint(lineMidpointState, endMid);
1919         for (size_t i = 0; i < m_boxes.size(); ++i) {
1920             InlineIterator ignoreStart(0, m_boxes[i], 0);
1921             addMidpoint(lineMidpointState, ignoreStart); // Stop ignoring spaces.
1922             addMidpoint(lineMidpointState, ignoreStart); // Start ignoring again.
1923         }
1924     }
1925 }
1926
1927 void RenderBlock::LineBreaker::reset()
1928 {
1929     m_positionedObjects.clear();
1930     m_hyphenated = false;
1931     m_clear = CNONE;
1932 }
1933
1934 InlineIterator RenderBlock::LineBreaker::nextLineBreak(InlineBidiResolver& resolver, LineInfo& lineInfo,
1935     LineBreakIteratorInfo& lineBreakIteratorInfo, FloatingObject* lastFloatFromPreviousLine)
1936 {
1937     reset();
1938
1939     ASSERT(resolver.position().root() == m_block);
1940
1941     bool appliedStartWidth = resolver.position().m_pos > 0;
1942     bool includeEndWidth = true;
1943     LineMidpointState& lineMidpointState = resolver.midpointState();
1944
1945     LineWidth width(m_block, lineInfo.isFirstLine());
1946
1947     skipLeadingWhitespace(resolver, lineInfo, lastFloatFromPreviousLine, width);
1948
1949     if (resolver.position().atEnd())
1950         return resolver.position();
1951
1952     // This variable is used only if whitespace isn't set to PRE, and it tells us whether
1953     // or not we are currently ignoring whitespace.
1954     bool ignoringSpaces = false;
1955     InlineIterator ignoreStart;
1956
1957     // This variable tracks whether the very last character we saw was a space.  We use
1958     // this to detect when we encounter a second space so we know we have to terminate
1959     // a run.
1960     bool currentCharacterIsSpace = false;
1961     bool currentCharacterIsWS = false;
1962     TrailingObjects trailingObjects;
1963
1964     InlineIterator lBreak = resolver.position();
1965
1966     // FIXME: It is error-prone to split the position object out like this.
1967     // Teach this code to work with objects instead of this split tuple.
1968     InlineIterator current = resolver.position();
1969     RenderObject* last = current.m_obj;
1970     bool atStart = true;
1971
1972     bool startingNewParagraph = lineInfo.previousLineBrokeCleanly();
1973     lineInfo.setPreviousLineBrokeCleanly(false);
1974
1975     bool autoWrapWasEverTrueOnLine = false;
1976     bool floatsFitOnLine = true;
1977
1978     // Firefox and Opera will allow a table cell to grow to fit an image inside it under
1979     // very specific circumstances (in order to match common WinIE renderings).
1980     // Not supporting the quirk has caused us to mis-render some real sites. (See Bugzilla 10517.)
1981     bool allowImagesToBreak = !m_block->document()->inQuirksMode() || !m_block->isTableCell() || !m_block->style()->logicalWidth().isIntrinsicOrAuto();
1982
1983     EWhiteSpace currWS = m_block->style()->whiteSpace();
1984     EWhiteSpace lastWS = currWS;
1985     while (current.m_obj) {
1986         RenderObject* next = bidiNext(m_block, current.m_obj);
1987         if (next && next->parent() && !next->parent()->isDescendantOf(current.m_obj->parent()))
1988             includeEndWidth = true;
1989
1990         currWS = current.m_obj->isReplaced() ? current.m_obj->parent()->style()->whiteSpace() : current.m_obj->style()->whiteSpace();
1991         lastWS = last->isReplaced() ? last->parent()->style()->whiteSpace() : last->style()->whiteSpace();
1992
1993         bool autoWrap = RenderStyle::autoWrap(currWS);
1994         autoWrapWasEverTrueOnLine = autoWrapWasEverTrueOnLine || autoWrap;
1995
1996 #if ENABLE(SVG)
1997         bool preserveNewline = current.m_obj->isSVGInlineText() ? false : RenderStyle::preserveNewline(currWS);
1998 #else
1999         bool preserveNewline = RenderStyle::preserveNewline(currWS);
2000 #endif
2001
2002         bool collapseWhiteSpace = RenderStyle::collapseWhiteSpace(currWS);
2003
2004         if (current.m_obj->isBR()) {
2005             if (width.fitsOnLine()) {
2006                 lBreak.moveToStartOf(current.m_obj);
2007                 lBreak.increment();
2008
2009                 // A <br> always breaks a line, so don't let the line be collapsed
2010                 // away. Also, the space at the end of a line with a <br> does not
2011                 // get collapsed away.  It only does this if the previous line broke
2012                 // cleanly.  Otherwise the <br> has no effect on whether the line is
2013                 // empty or not.
2014                 if (startingNewParagraph)
2015                     lineInfo.setEmpty(false);
2016                 trailingObjects.clear();
2017                 lineInfo.setPreviousLineBrokeCleanly(true);
2018
2019                 if (!lineInfo.isEmpty())
2020                     m_clear = current.m_obj->style()->clear();
2021             }
2022             goto end;
2023         }
2024
2025         if (current.m_obj->isFloating()) {
2026             RenderBox* floatBox = toRenderBox(current.m_obj);
2027             FloatingObject* f = m_block->insertFloatingObject(floatBox);
2028             // check if it fits in the current line.
2029             // If it does, position it now, otherwise, position
2030             // it after moving to next line (in newLine() func)
2031             if (floatsFitOnLine && width.fitsOnLine(m_block->logicalWidthForFloat(f))) {
2032                 m_block->positionNewFloatOnLine(f, lastFloatFromPreviousLine, width);
2033                 if (lBreak.m_obj == current.m_obj) {
2034                     ASSERT(!lBreak.m_pos);
2035                     lBreak.increment();
2036                 }
2037             } else
2038                 floatsFitOnLine = false;
2039         } else if (current.m_obj->isPositioned()) {
2040             // If our original display wasn't an inline type, then we can
2041             // go ahead and determine our static inline position now.
2042             RenderBox* box = toRenderBox(current.m_obj);
2043             bool isInlineType = box->style()->isOriginalDisplayInlineType();
2044             if (!isInlineType)
2045                 box->layer()->setStaticInlinePosition(m_block->borderAndPaddingStart());
2046             else  {
2047                 // If our original display was an INLINE type, then we can go ahead
2048                 // and determine our static y position now.
2049                 box->layer()->setStaticBlockPosition(m_block->logicalHeight());
2050             }
2051
2052             // If we're ignoring spaces, we have to stop and include this object and
2053             // then start ignoring spaces again.
2054             if (isInlineType || current.m_obj->container()->isRenderInline()) {
2055                 if (ignoringSpaces) {
2056                     ignoreStart.m_obj = current.m_obj;
2057                     ignoreStart.m_pos = 0;
2058                     addMidpoint(lineMidpointState, ignoreStart); // Stop ignoring spaces.
2059                     addMidpoint(lineMidpointState, ignoreStart); // Start ignoring again.
2060                 }
2061                 trailingObjects.appendBoxIfNeeded(box);
2062             } else
2063                 m_positionedObjects.append(box);
2064         } else if (current.m_obj->isRenderInline()) {
2065             // Right now, we should only encounter empty inlines here.
2066             ASSERT(!current.m_obj->firstChild());
2067
2068             RenderInline* flowBox = toRenderInline(current.m_obj);
2069
2070             // Now that some inline flows have line boxes, if we are already ignoring spaces, we need
2071             // to make sure that we stop to include this object and then start ignoring spaces again.
2072             // If this object is at the start of the line, we need to behave like list markers and
2073             // start ignoring spaces.
2074             if (inlineFlowRequiresLineBox(flowBox)) {
2075                 lineInfo.setEmpty(false);
2076                 if (ignoringSpaces) {
2077                     trailingObjects.clear();
2078                     addMidpoint(lineMidpointState, InlineIterator(0, current.m_obj, 0)); // Stop ignoring spaces.
2079                     addMidpoint(lineMidpointState, InlineIterator(0, current.m_obj, 0)); // Start ignoring again.
2080                 } else if (m_block->style()->collapseWhiteSpace() && resolver.position().m_obj == current.m_obj
2081                     && shouldSkipWhitespaceAfterStartObject(m_block, current.m_obj, lineMidpointState)) {
2082                     // Like with list markers, we start ignoring spaces to make sure that any
2083                     // additional spaces we see will be discarded.
2084                     currentCharacterIsSpace = true;
2085                     currentCharacterIsWS = true;
2086                     ignoringSpaces = true;
2087                 }
2088             }
2089
2090             width.addUncommittedWidth(borderPaddingMarginStart(flowBox) + borderPaddingMarginEnd(flowBox));
2091         } else if (current.m_obj->isReplaced()) {
2092             RenderBox* replacedBox = toRenderBox(current.m_obj);
2093
2094             // Break on replaced elements if either has normal white-space.
2095             if ((autoWrap || RenderStyle::autoWrap(lastWS)) && (!current.m_obj->isImage() || allowImagesToBreak)) {
2096                 width.commit();
2097                 lBreak.moveToStartOf(current.m_obj);
2098             }
2099
2100             if (ignoringSpaces)
2101                 addMidpoint(lineMidpointState, InlineIterator(0, current.m_obj, 0));
2102
2103             lineInfo.setEmpty(false);
2104             ignoringSpaces = false;
2105             currentCharacterIsSpace = false;
2106             currentCharacterIsWS = false;
2107             trailingObjects.clear();
2108
2109             // Optimize for a common case. If we can't find whitespace after the list
2110             // item, then this is all moot.
2111             int replacedLogicalWidth = m_block->logicalWidthForChild(replacedBox) + m_block->marginStartForChild(replacedBox) + m_block->marginEndForChild(replacedBox) + inlineLogicalWidth(current.m_obj);
2112             if (current.m_obj->isListMarker()) {
2113                 if (m_block->style()->collapseWhiteSpace() && shouldSkipWhitespaceAfterStartObject(m_block, current.m_obj, lineMidpointState)) {
2114                     // Like with inline flows, we start ignoring spaces to make sure that any
2115                     // additional spaces we see will be discarded.
2116                     currentCharacterIsSpace = true;
2117                     currentCharacterIsWS = true;
2118                     ignoringSpaces = true;
2119                 }
2120                 if (toRenderListMarker(current.m_obj)->isInside())
2121                     width.addUncommittedWidth(replacedLogicalWidth);
2122             } else
2123                 width.addUncommittedWidth(replacedLogicalWidth);
2124             if (current.m_obj->isRubyRun())
2125                 width.applyOverhang(toRenderRubyRun(current.m_obj), last, next);
2126         } else if (current.m_obj->isText()) {
2127             if (!current.m_pos)
2128                 appliedStartWidth = false;
2129
2130             RenderText* t = toRenderText(current.m_obj);
2131
2132 #if ENABLE(SVG)
2133             bool isSVGText = t->isSVGInlineText();
2134 #endif
2135
2136             RenderStyle* style = t->style(lineInfo.isFirstLine());
2137             if (style->hasTextCombine() && current.m_obj->isCombineText())
2138                 toRenderCombineText(current.m_obj)->combineText();
2139
2140             const Font& f = style->font();
2141             bool isFixedPitch = f.isFixedPitch();
2142             bool canHyphenate = style->hyphens() == HyphensAuto && WebCore::canHyphenate(style->locale());
2143
2144             int lastSpace = current.m_pos;
2145             float wordSpacing = current.m_obj->style()->wordSpacing();
2146             float lastSpaceWordSpacing = 0;
2147
2148             // Non-zero only when kerning is enabled, in which case we measure words with their trailing
2149             // space, then subtract its width.
2150             float wordTrailingSpaceWidth = f.typesettingFeatures() & Kerning ? f.width(constructTextRun(t, f, &space, 1, style)) + wordSpacing : 0;
2151
2152             float wrapW = width.uncommittedWidth() + inlineLogicalWidth(current.m_obj, !appliedStartWidth, true);
2153             float charWidth = 0;
2154             bool breakNBSP = autoWrap && current.m_obj->style()->nbspMode() == SPACE;
2155             // Auto-wrapping text should wrap in the middle of a word only if it could not wrap before the word,
2156             // which is only possible if the word is the first thing on the line, that is, if |w| is zero.
2157             bool breakWords = current.m_obj->style()->breakWords() && ((autoWrap && !width.committedWidth()) || currWS == PRE);
2158             bool midWordBreak = false;
2159             bool breakAll = current.m_obj->style()->wordBreak() == BreakAllWordBreak && autoWrap;
2160             float hyphenWidth = 0;
2161
2162             if (t->isWordBreak()) {
2163                 width.commit();
2164                 lBreak.moveToStartOf(current.m_obj);
2165                 ASSERT(current.m_pos == t->textLength());
2166             }
2167
2168             for (; current.m_pos < t->textLength(); current.fastIncrementInTextNode()) {
2169                 bool previousCharacterIsSpace = currentCharacterIsSpace;
2170                 bool previousCharacterIsWS = currentCharacterIsWS;
2171                 UChar c = current.current();
2172                 currentCharacterIsSpace = c == ' ' || c == '\t' || (!preserveNewline && (c == '\n'));
2173
2174                 if (!collapseWhiteSpace || !currentCharacterIsSpace)
2175                     lineInfo.setEmpty(false);
2176
2177                 if (c == softHyphen && autoWrap && !hyphenWidth && style->hyphens() != HyphensNone) {
2178                     const AtomicString& hyphenString = style->hyphenString();
2179                     hyphenWidth = f.width(constructTextRun(t, f, hyphenString.string(), current.m_obj->style()));
2180                     width.addUncommittedWidth(hyphenWidth);
2181                 }
2182
2183                 bool applyWordSpacing = false;
2184
2185                 currentCharacterIsWS = currentCharacterIsSpace || (breakNBSP && c == noBreakSpace);
2186
2187                 if ((breakAll || breakWords) && !midWordBreak) {
2188                     wrapW += charWidth;
2189                     bool midWordBreakIsBeforeSurrogatePair = U16_IS_LEAD(c) && current.m_pos + 1 < t->textLength() && U16_IS_TRAIL(t->characters()[current.m_pos + 1]);
2190                     charWidth = textWidth(t, current.m_pos, midWordBreakIsBeforeSurrogatePair ? 2 : 1, f, width.committedWidth() + wrapW, isFixedPitch, collapseWhiteSpace);
2191                     midWordBreak = width.committedWidth() + wrapW + charWidth > width.availableWidth();
2192                 }
2193
2194                 if (lineBreakIteratorInfo.first != t) {
2195                     lineBreakIteratorInfo.first = t;
2196                     lineBreakIteratorInfo.second.reset(t->characters(), t->textLength(), style->locale());
2197                 }
2198
2199                 bool betweenWords = c == '\n' || (currWS != PRE && !atStart && isBreakable(lineBreakIteratorInfo.second, current.m_pos, current.m_nextBreakablePosition, breakNBSP)
2200                     && (style->hyphens() != HyphensNone || (current.previousInSameNode() != softHyphen)));
2201
2202                 if (betweenWords || midWordBreak) {
2203                     bool stoppedIgnoringSpaces = false;
2204                     if (ignoringSpaces) {
2205                         if (!currentCharacterIsSpace) {
2206                             // Stop ignoring spaces and begin at this
2207                             // new point.
2208                             ignoringSpaces = false;
2209                             lastSpaceWordSpacing = 0;
2210                             lastSpace = current.m_pos; // e.g., "Foo    goo", don't add in any of the ignored spaces.
2211                             addMidpoint(lineMidpointState, InlineIterator(0, current.m_obj, current.m_pos));
2212                             stoppedIgnoringSpaces = true;
2213                         } else {
2214                             // Just keep ignoring these spaces.
2215                             continue;
2216                         }
2217                     }
2218
2219                     float additionalTmpW;
2220                     if (wordTrailingSpaceWidth && currentCharacterIsSpace)
2221                         additionalTmpW = textWidth(t, lastSpace, current.m_pos + 1 - lastSpace, f, width.currentWidth(), isFixedPitch, collapseWhiteSpace) - wordTrailingSpaceWidth + lastSpaceWordSpacing;
2222                     else
2223                         additionalTmpW = textWidth(t, lastSpace, current.m_pos - lastSpace, f, width.currentWidth(), isFixedPitch, collapseWhiteSpace) + lastSpaceWordSpacing;
2224                     width.addUncommittedWidth(additionalTmpW);
2225                     if (!appliedStartWidth) {
2226                         width.addUncommittedWidth(inlineLogicalWidth(current.m_obj, true, false));
2227                         appliedStartWidth = true;
2228                     }
2229
2230                     applyWordSpacing =  wordSpacing && currentCharacterIsSpace && !previousCharacterIsSpace;
2231
2232                     if (!width.committedWidth() && autoWrap && !width.fitsOnLine())
2233                         width.fitBelowFloats();
2234
2235                     if (autoWrap || breakWords) {
2236                         // If we break only after white-space, consider the current character
2237                         // as candidate width for this line.
2238                         bool lineWasTooWide = false;
2239                         if (width.fitsOnLine() && currentCharacterIsWS && current.m_obj->style()->breakOnlyAfterWhiteSpace() && !midWordBreak) {
2240                             float charWidth = textWidth(t, current.m_pos, 1, f, width.currentWidth(), isFixedPitch, collapseWhiteSpace) + (applyWordSpacing ? wordSpacing : 0);
2241                             // Check if line is too big even without the extra space
2242                             // at the end of the line. If it is not, do nothing.
2243                             // If the line needs the extra whitespace to be too long,
2244                             // then move the line break to the space and skip all
2245                             // additional whitespace.
2246                             if (!width.fitsOnLine(charWidth)) {
2247                                 lineWasTooWide = true;
2248                                 lBreak.moveTo(current.m_obj, current.m_pos, current.m_nextBreakablePosition);
2249                                 skipTrailingWhitespace(lBreak, lineInfo);
2250                             }
2251                         }
2252                         if (lineWasTooWide || !width.fitsOnLine()) {
2253                             if (canHyphenate && !width.fitsOnLine()) {
2254                                 tryHyphenating(t, f, style->locale(), style->hyphenationLimitBefore(), style->hyphenationLimitAfter(), lastSpace, current.m_pos, width.currentWidth() - additionalTmpW, width.availableWidth(), isFixedPitch, collapseWhiteSpace, lastSpaceWordSpacing, lBreak, current.m_nextBreakablePosition, m_hyphenated);
2255                                 if (m_hyphenated)
2256                                     goto end;
2257                             }
2258                             if (lBreak.atTextParagraphSeparator()) {
2259                                 if (!stoppedIgnoringSpaces && current.m_pos > 0) {
2260                                     // We need to stop right before the newline and then start up again.
2261                                     addMidpoint(lineMidpointState, InlineIterator(0, current.m_obj, current.m_pos - 1)); // Stop
2262                                     addMidpoint(lineMidpointState, InlineIterator(0, current.m_obj, current.m_pos)); // Start
2263                                 }
2264                                 lBreak.increment();
2265                                 lineInfo.setPreviousLineBrokeCleanly(true);
2266                             }
2267                             if (lBreak.m_obj && lBreak.m_pos && lBreak.m_obj->isText() && toRenderText(lBreak.m_obj)->textLength() && toRenderText(lBreak.m_obj)->characters()[lBreak.m_pos - 1] == softHyphen && style->hyphens() != HyphensNone)
2268                                 m_hyphenated = true;
2269                             goto end; // Didn't fit. Jump to the end.
2270                         } else {
2271                             if (!betweenWords || (midWordBreak && !autoWrap))
2272                                 width.addUncommittedWidth(-additionalTmpW);
2273                             if (hyphenWidth) {
2274                                 // Subtract the width of the soft hyphen out since we fit on a line.
2275                                 width.addUncommittedWidth(-hyphenWidth);
2276                                 hyphenWidth = 0;
2277                             }
2278                         }
2279                     }
2280
2281                     if (c == '\n' && preserveNewline) {
2282                         if (!stoppedIgnoringSpaces && current.m_pos > 0) {
2283                             // We need to stop right before the newline and then start up again.
2284                             addMidpoint(lineMidpointState, InlineIterator(0, current.m_obj, current.m_pos - 1)); // Stop
2285                             addMidpoint(lineMidpointState, InlineIterator(0, current.m_obj, current.m_pos)); // Start
2286                         }
2287                         lBreak.moveTo(current.m_obj, current.m_pos, current.m_nextBreakablePosition);
2288                         lBreak.increment();
2289                         lineInfo.setPreviousLineBrokeCleanly(true);
2290                         return lBreak;
2291                     }
2292
2293                     if (autoWrap && betweenWords) {
2294                         width.commit();
2295                         wrapW = 0;
2296                         lBreak.moveTo(current.m_obj, current.m_pos, current.m_nextBreakablePosition);
2297                         // Auto-wrapping text should not wrap in the middle of a word once it has had an
2298                         // opportunity to break after a word.
2299                         breakWords = false;
2300                     }
2301
2302                     if (midWordBreak && !U16_IS_TRAIL(c)) {
2303                         // Remember this as a breakable position in case
2304                         // adding the end width forces a break.
2305                         lBreak.moveTo(current.m_obj, current.m_pos, current.m_nextBreakablePosition);
2306                         midWordBreak &= (breakWords || breakAll);
2307                     }
2308
2309                     if (betweenWords) {
2310                         lastSpaceWordSpacing = applyWordSpacing ? wordSpacing : 0;
2311                         lastSpace = current.m_pos;
2312                     }
2313
2314                     if (!ignoringSpaces && current.m_obj->style()->collapseWhiteSpace()) {
2315                         // If we encounter a newline, or if we encounter a
2316                         // second space, we need to go ahead and break up this
2317                         // run and enter a mode where we start collapsing spaces.
2318                         if (currentCharacterIsSpace && previousCharacterIsSpace) {
2319                             ignoringSpaces = true;
2320
2321                             // We just entered a mode where we are ignoring
2322                             // spaces. Create a midpoint to terminate the run
2323                             // before the second space.
2324                             addMidpoint(lineMidpointState, ignoreStart);
2325                             trailingObjects.updateMidpointsForTrailingBoxes(lineMidpointState, InlineIterator(), TrailingObjects::DoNotCollapseFirstSpace);
2326                         }
2327                     }
2328                 } else if (ignoringSpaces) {
2329                     // Stop ignoring spaces and begin at this
2330                     // new point.
2331                     ignoringSpaces = false;
2332                     lastSpaceWordSpacing = applyWordSpacing ? wordSpacing : 0;
2333                     lastSpace = current.m_pos; // e.g., "Foo    goo", don't add in any of the ignored spaces.
2334                     addMidpoint(lineMidpointState, InlineIterator(0, current.m_obj, current.m_pos));
2335                 }
2336
2337 #if ENABLE(SVG)
2338                 if (isSVGText && current.m_pos > 0) {
2339                     // Force creation of new InlineBoxes for each absolute positioned character (those that start new text chunks).
2340                     if (toRenderSVGInlineText(t)->characterStartsNewTextChunk(current.m_pos)) {
2341                         addMidpoint(lineMidpointState, InlineIterator(0, current.m_obj, current.m_pos - 1));
2342                         addMidpoint(lineMidpointState, InlineIterator(0, current.m_obj, current.m_pos));
2343                     }
2344                 }
2345 #endif
2346
2347                 if (currentCharacterIsSpace && !previousCharacterIsSpace) {
2348                     ignoreStart.m_obj = current.m_obj;
2349                     ignoreStart.m_pos = current.m_pos;
2350                 }
2351
2352                 if (!currentCharacterIsWS && previousCharacterIsWS) {
2353                     if (autoWrap && current.m_obj->style()->breakOnlyAfterWhiteSpace())
2354                         lBreak.moveTo(current.m_obj, current.m_pos, current.m_nextBreakablePosition);
2355                 }
2356
2357                 if (collapseWhiteSpace && currentCharacterIsSpace && !ignoringSpaces)
2358                     trailingObjects.setTrailingWhitespace(toRenderText(current.m_obj));
2359                 else if (!current.m_obj->style()->collapseWhiteSpace() || !currentCharacterIsSpace)
2360                     trailingObjects.clear();
2361
2362                 atStart = false;
2363             }
2364
2365             // IMPORTANT: current.m_pos is > length here!
2366             float additionalTmpW = ignoringSpaces ? 0 : textWidth(t, lastSpace, current.m_pos - lastSpace, f, width.currentWidth(), isFixedPitch, collapseWhiteSpace) + lastSpaceWordSpacing;
2367             width.addUncommittedWidth(additionalTmpW + inlineLogicalWidth(current.m_obj, !appliedStartWidth, includeEndWidth));
2368             includeEndWidth = false;
2369
2370             if (!width.fitsOnLine()) {
2371                 if (canHyphenate)
2372                     tryHyphenating(t, f, style->locale(), style->hyphenationLimitBefore(), style->hyphenationLimitAfter(), lastSpace, current.m_pos, width.currentWidth() - additionalTmpW, width.availableWidth(), isFixedPitch, collapseWhiteSpace, lastSpaceWordSpacing, lBreak, current.m_nextBreakablePosition, m_hyphenated);
2373
2374                 if (!m_hyphenated && lBreak.previousInSameNode() == softHyphen && style->hyphens() != HyphensNone)
2375                     m_hyphenated = true;
2376
2377                 if (m_hyphenated)
2378                     goto end;
2379             }
2380         } else
2381             ASSERT_NOT_REACHED();
2382
2383         bool checkForBreak = autoWrap;
2384         if (width.committedWidth() && !width.fitsOnLine() && lBreak.m_obj && currWS == NOWRAP)
2385             checkForBreak = true;
2386         else if (next && current.m_obj->isText() && next->isText() && !next->isBR() && (autoWrap || (next->style()->autoWrap()))) {
2387             if (currentCharacterIsSpace)
2388                 checkForBreak = true;
2389             else {
2390                 RenderText* nextText = toRenderText(next);
2391                 if (nextText->textLength()) {
2392                     UChar c = nextText->characters()[0];
2393                     checkForBreak = (c == ' ' || c == '\t' || (c == '\n' && !next->preservesNewline()));
2394                     // If the next item on the line is text, and if we did not end with
2395                     // a space, then the next text run continues our word (and so it needs to
2396                     // keep adding to |tmpW|. Just update and continue.
2397                 } else if (nextText->isWordBreak())
2398                     checkForBreak = true;
2399
2400                 if (!width.fitsOnLine() && !width.committedWidth())
2401                     width.fitBelowFloats();
2402
2403                 bool canPlaceOnLine = width.fitsOnLine() || !autoWrapWasEverTrueOnLine;
2404                 if (canPlaceOnLine && checkForBreak) {
2405                     width.commit();
2406                     lBreak.moveToStartOf(next);
2407                 }
2408             }
2409         }
2410
2411         if (checkForBreak && !width.fitsOnLine()) {
2412             // if we have floats, try to get below them.
2413             if (currentCharacterIsSpace && !ignoringSpaces && current.m_obj->style()->collapseWhiteSpace())
2414                 trailingObjects.clear();
2415
2416             if (width.committedWidth())
2417                 goto end;
2418
2419             width.fitBelowFloats();
2420
2421             // |width| may have been adjusted because we got shoved down past a float (thus
2422             // giving us more room), so we need to retest, and only jump to
2423             // the end label if we still don't fit on the line. -dwh
2424             if (!width.fitsOnLine())
2425                 goto end;
2426         }
2427
2428         if (!current.m_obj->isFloatingOrPositioned()) {
2429             last = current.m_obj;
2430             if (last->isReplaced() && autoWrap && (!last->isImage() || allowImagesToBreak) && (!last->isListMarker() || toRenderListMarker(last)->isInside())) {
2431                 width.commit();
2432                 lBreak.moveToStartOf(next);
2433             }
2434         }
2435
2436         // Clear out our character space bool, since inline <pre>s don't collapse whitespace
2437         // with adjacent inline normal/nowrap spans.
2438         if (!collapseWhiteSpace)
2439             currentCharacterIsSpace = false;
2440
2441         current.moveToStartOf(next);
2442         atStart = false;
2443     }
2444
2445     if (width.fitsOnLine() || lastWS == NOWRAP)
2446         lBreak.clear();
2447
2448  end:
2449     if (lBreak == resolver.position() && (!lBreak.m_obj || !lBreak.m_obj->isBR())) {
2450         // we just add as much as possible
2451         if (m_block->style()->whiteSpace() == PRE) {
2452             // FIXME: Don't really understand this case.
2453             if (current.m_pos) {
2454                 // FIXME: This should call moveTo which would clear m_nextBreakablePosition
2455                 // this code as-is is likely wrong.
2456                 lBreak.m_obj = current.m_obj;
2457                 lBreak.m_pos = current.m_pos - 1;
2458             } else
2459                 lBreak.moveTo(last, last->isText() ? last->length() : 0);
2460         } else if (lBreak.m_obj) {
2461             // Don't ever break in the middle of a word if we can help it.
2462             // There's no room at all. We just have to be on this line,
2463             // even though we'll spill out.
2464             lBreak.moveTo(current.m_obj, current.m_pos);
2465         }
2466     }
2467
2468     // make sure we consume at least one char/object.
2469     if (lBreak == resolver.position())
2470         lBreak.increment();
2471
2472     // Sanity check our midpoints.
2473     checkMidpoints(lineMidpointState, lBreak);
2474
2475     trailingObjects.updateMidpointsForTrailingBoxes(lineMidpointState, lBreak, TrailingObjects::CollapseFirstSpace);
2476
2477     // We might have made lBreak an iterator that points past the end
2478     // of the object. Do this adjustment to make it point to the start
2479     // of the next object instead to avoid confusing the rest of the
2480     // code.
2481     if (lBreak.m_pos > 0) {
2482         lBreak.m_pos--;
2483         lBreak.increment();
2484     }
2485
2486     return lBreak;
2487 }
2488
2489 void RenderBlock::addOverflowFromInlineChildren()
2490 {
2491     int endPadding = hasOverflowClip() ? paddingEnd() : 0;
2492     // FIXME: Need to find another way to do this, since scrollbars could show when we don't want them to.
2493     if (hasOverflowClip() && !endPadding && node() && node()->rendererIsEditable() && node() == node()->rootEditableElement() && style()->isLeftToRightDirection())
2494         endPadding = 1;
2495     for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
2496         addLayoutOverflow(curr->paddedLayoutOverflowRect(endPadding));
2497         if (!hasOverflowClip())
2498             addVisualOverflow(curr->visualOverflowRect(curr->lineTop(), curr->lineBottom()));
2499     }
2500 }
2501
2502 void RenderBlock::deleteEllipsisLineBoxes()
2503 {
2504     for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox())
2505         curr->clearTruncation();
2506 }
2507
2508 void RenderBlock::checkLinesForTextOverflow()
2509 {
2510     // Determine the width of the ellipsis using the current font.
2511     // FIXME: CSS3 says this is configurable, also need to use 0x002E (FULL STOP) if horizontal ellipsis is "not renderable"
2512     const Font& font = style()->font();
2513     DEFINE_STATIC_LOCAL(AtomicString, ellipsisStr, (&horizontalEllipsis, 1));
2514     const Font& firstLineFont = firstLineStyle()->font();
2515     int firstLineEllipsisWidth = firstLineFont.width(constructTextRun(this, firstLineFont, &horizontalEllipsis, 1, firstLineStyle()));
2516     int ellipsisWidth = (font == firstLineFont) ? firstLineEllipsisWidth : font.width(constructTextRun(this, font, &horizontalEllipsis, 1, style()));
2517
2518     // For LTR text truncation, we want to get the right edge of our padding box, and then we want to see
2519     // if the right edge of a line box exceeds that.  For RTL, we use the left edge of the padding box and
2520     // check the left edge of the line box to see if it is less
2521     // Include the scrollbar for overflow blocks, which means we want to use "contentWidth()"
2522     bool ltr = style()->isLeftToRightDirection();
2523     for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
2524         int blockRightEdge = logicalRightOffsetForLine(curr->y(), curr == firstRootBox());
2525         int blockLeftEdge = logicalLeftOffsetForLine(curr->y(), curr == firstRootBox());
2526         int lineBoxEdge = ltr ? curr->x() + curr->logicalWidth() : curr->x();
2527         if ((ltr && lineBoxEdge > blockRightEdge) || (!ltr && lineBoxEdge < blockLeftEdge)) {
2528             // This line spills out of our box in the appropriate direction.  Now we need to see if the line
2529             // can be truncated.  In order for truncation to be possible, the line must have sufficient space to
2530             // accommodate our truncation string, and no replaced elements (images, tables) can overlap the ellipsis
2531             // space.
2532             int width = curr == firstRootBox() ? firstLineEllipsisWidth : ellipsisWidth;
2533             int blockEdge = ltr ? blockRightEdge : blockLeftEdge;
2534             if (curr->lineCanAccommodateEllipsis(ltr, blockEdge, lineBoxEdge, width))
2535                 curr->placeEllipsis(ellipsisStr, ltr, blockLeftEdge, blockRightEdge, width);
2536         }
2537     }
2538 }
2539
2540 bool RenderBlock::positionNewFloatOnLine(FloatingObject* newFloat, FloatingObject* lastFloatFromPreviousLine, LineWidth& width)
2541 {
2542     if (!positionNewFloats())
2543         return false;
2544
2545     width.shrinkAvailableWidthForNewFloatIfNeeded(newFloat);
2546
2547     if (!newFloat->m_paginationStrut)
2548         return true;
2549
2550     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2551     ASSERT(floatingObjectSet.last() == newFloat);
2552
2553     int floatLogicalTop = logicalTopForFloat(newFloat);
2554     int paginationStrut = newFloat->m_paginationStrut;
2555
2556     if (floatLogicalTop - paginationStrut != logicalHeight())
2557         return true;
2558
2559     FloatingObjectSetIterator it = floatingObjectSet.end();
2560     --it; // Last float is newFloat, skip that one.
2561     FloatingObjectSetIterator begin = floatingObjectSet.begin();
2562     while (it != begin) {
2563         --it;
2564         FloatingObject* f = *it;
2565         if (f == lastFloatFromPreviousLine)
2566             break;
2567         if (logicalTopForFloat(f) == logicalHeight()) {
2568             ASSERT(!f->m_paginationStrut);
2569             f->m_paginationStrut = paginationStrut;
2570             RenderBox* o = f->m_renderer;
2571             setLogicalTopForChild(o, logicalTopForChild(o) + marginBeforeForChild(o) + paginationStrut);
2572             if (o->isRenderBlock())
2573                 toRenderBlock(o)->setChildNeedsLayout(true, false);
2574             o->layoutIfNeeded();
2575             // Save the old logical top before calling removePlacedObject which will set
2576             // isPlaced to false. Otherwise it will trigger an assert in logicalTopForFloat.
2577             LayoutUnit oldLogicalTop = logicalTopForFloat(f);
2578             m_floatingObjects->removePlacedObject(f);
2579             setLogicalTopForFloat(f, oldLogicalTop + f->m_paginationStrut);
2580             m_floatingObjects->addPlacedObject(f);
2581         }
2582     }
2583
2584     setLogicalHeight(logicalHeight() + paginationStrut);
2585     width.updateAvailableWidth();
2586
2587     return true;
2588 }
2589
2590 }