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