Source/WebCore/rendering/RenderBlockLineLayout.cpp

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