Source/WebCore/rendering/RenderBlockLineLayout.cpp

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