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