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