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