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