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