src/third_party/WebKit/Source/core/rendering/RenderBlockLineLayout.cpp

   1 /*
   2  * Copyright (C) 2000 Lars Knoll (knoll@kde.org)
   3  * Copyright (C) 2003, 2004, 2006, 2007, 2008, 2009, 2010, 2011 Apple Inc. All right reserved.
   4  * Copyright (C) 2010 Google Inc. All rights reserved.
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Library General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Library General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Library General Public License
  17  * along with this library; see the file COPYING.LIB.  If not, write to
  18  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  19  * Boston, MA 02110-1301, USA.
  20  *
  21  */
  22
  23 #include "config.h"
  24
  25 #include "core/accessibility/AXObjectCache.h"
  26 #include "core/rendering/BidiRunForLine.h"
  27 #include "core/rendering/RenderCounter.h"
  28 #include "core/rendering/RenderFlowThread.h"
  29 #include "core/rendering/RenderLayer.h"
  30 #include "core/rendering/RenderListMarker.h"
  31 #include "core/rendering/RenderObjectInlines.h"
  32 #include "core/rendering/RenderRegion.h"
  33 #include "core/rendering/RenderRubyRun.h"
  34 #include "core/rendering/RenderView.h"
  35 #include "core/rendering/TextRunConstructor.h"
  36 #include "core/rendering/TrailingFloatsRootInlineBox.h"
  37 #include "core/rendering/VerticalPositionCache.h"
  38 #include "core/rendering/line/BreakingContextInlineHeaders.h"
  39 #include "core/rendering/line/LineLayoutState.h"
  40 #include "core/rendering/line/LineWidth.h"
  41 #include "core/rendering/line/RenderTextInfo.h"
  42 #include "core/rendering/line/WordMeasurement.h"
  43 #include "core/rendering/svg/SVGRootInlineBox.h"
  44 #include "platform/fonts/Character.h"
  45 #include "platform/text/BidiResolver.h"
  46 #include "wtf/RefCountedLeakCounter.h"
  47 #include "wtf/StdLibExtras.h"
  48 #include "wtf/Vector.h"
  49 #include "wtf/unicode/CharacterNames.h"
  50
  51 namespace blink {
  52
  53 using namespace WTF::Unicode;
  54
  55 static inline InlineBox* createInlineBoxForRenderer(RenderObject* obj, bool isRootLineBox, bool isOnlyRun = false)
  56 {
  57     if (isRootLineBox)
  58         return toRenderBlockFlow(obj)->createAndAppendRootInlineBox();
  59
  60     if (obj->isText()) {
  61         InlineTextBox* textBox = toRenderText(obj)->createInlineTextBox();
  62         // We only treat a box as text for a <br> if we are on a line by ourself or in strict mode
  63         // (Note the use of strict mode.  In "almost strict" mode, we don't treat the box for <br> as text.)
  64         if (obj->isBR())
  65             textBox->setIsText(isOnlyRun || obj->document().inNoQuirksMode());
  66         return textBox;
  67     }
  68
  69     if (obj->isBox())
  70         return toRenderBox(obj)->createInlineBox();
  71
  72     return toRenderInline(obj)->createAndAppendInlineFlowBox();
  73 }
  74
  75 static inline void dirtyLineBoxesForRenderer(RenderObject* o, bool fullLayout)
  76 {
  77     if (o->isText()) {
  78         RenderText* renderText = toRenderText(o);
  79         renderText->dirtyLineBoxes(fullLayout);
  80     } else
  81         toRenderInline(o)->dirtyLineBoxes(fullLayout);
  82 }
  83
  84 static bool parentIsConstructedOrHaveNext(InlineFlowBox* parentBox)
  85 {
  86     do {
  87         if (parentBox->isConstructed() || parentBox->nextOnLine())
  88             return true;
  89         parentBox = parentBox->parent();
  90     } while (parentBox);
  91     return false;
  92 }
  93
  94 InlineFlowBox* RenderBlockFlow::createLineBoxes(RenderObject* obj, const LineInfo& lineInfo, InlineBox* childBox)
  95 {
  96     // See if we have an unconstructed line box for this object that is also
  97     // the last item on the line.
  98     unsigned lineDepth = 1;
  99     InlineFlowBox* parentBox = 0;
 100     InlineFlowBox* result = 0;
 101     bool hasDefaultLineBoxContain = style()->lineBoxContain() == RenderStyle::initialLineBoxContain();
 102     do {
 103         ASSERT_WITH_SECURITY_IMPLICATION(obj->isRenderInline() || obj == this);
 104
 105         RenderInline* inlineFlow = (obj != this) ? toRenderInline(obj) : 0;
 106
 107         // Get the last box we made for this render object.
 108         parentBox = inlineFlow ? inlineFlow->lastLineBox() : toRenderBlock(obj)->lastLineBox();
 109
 110         // If this box or its ancestor is constructed then it is from a previous line, and we need
 111         // to make a new box for our line.  If this box or its ancestor is unconstructed but it has
 112         // something following it on the line, then we know we have to make a new box
 113         // as well.  In this situation our inline has actually been split in two on
 114         // the same line (this can happen with very fancy language mixtures).
 115         bool constructedNewBox = false;
 116         bool allowedToConstructNewBox = !hasDefaultLineBoxContain || !inlineFlow || inlineFlow->alwaysCreateLineBoxes();
 117         bool canUseExistingParentBox = parentBox && !parentIsConstructedOrHaveNext(parentBox);
 118         if (allowedToConstructNewBox && !canUseExistingParentBox) {
 119             // We need to make a new box for this render object.  Once
 120             // made, we need to place it at the end of the current line.
 121             InlineBox* newBox = createInlineBoxForRenderer(obj, obj == this);
 122             ASSERT_WITH_SECURITY_IMPLICATION(newBox->isInlineFlowBox());
 123             parentBox = toInlineFlowBox(newBox);
 124             parentBox->setFirstLineStyleBit(lineInfo.isFirstLine());
 125             parentBox->setIsHorizontal(isHorizontalWritingMode());
 126             if (!hasDefaultLineBoxContain)
 127                 parentBox->clearDescendantsHaveSameLineHeightAndBaseline();
 128             constructedNewBox = true;
 129         }
 130
 131         if (constructedNewBox || canUseExistingParentBox) {
 132             if (!result)
 133                 result = parentBox;
 134
 135             // If we have hit the block itself, then |box| represents the root
 136             // inline box for the line, and it doesn't have to be appended to any parent
 137             // inline.
 138             if (childBox)
 139                 parentBox->addToLine(childBox);
 140
 141             if (!constructedNewBox || obj == this)
 142                 break;
 143
 144             childBox = parentBox;
 145         }
 146
 147         // If we've exceeded our line depth, then jump straight to the root and skip all the remaining
 148         // intermediate inline flows.
 149         obj = (++lineDepth >= cMaxLineDepth) ? this : obj->parent();
 150
 151     } while (true);
 152
 153     return result;
 154 }
 155
 156 template <typename CharacterType>
 157 static inline bool endsWithASCIISpaces(const CharacterType* characters, unsigned pos, unsigned end)
 158 {
 159     while (isASCIISpace(characters[pos])) {
 160         pos++;
 161         if (pos >= end)
 162             return true;
 163     }
 164     return false;
 165 }
 166
 167 static bool reachedEndOfTextRenderer(const BidiRunList<BidiRun>& bidiRuns)
 168 {
 169     BidiRun* run = bidiRuns.logicallyLastRun();
 170     if (!run)
 171         return true;
 172     unsigned pos = run->stop();
 173     RenderObject* r = run->m_object;
 174     if (!r->isText() || r->isBR())
 175         return false;
 176     RenderText* renderText = toRenderText(r);
 177     unsigned length = renderText->textLength();
 178     if (pos >= length)
 179         return true;
 180
 181     if (renderText->is8Bit())
 182         return endsWithASCIISpaces(renderText->characters8(), pos, length);
 183     return endsWithASCIISpaces(renderText->characters16(), pos, length);
 184 }
 185
 186 RootInlineBox* RenderBlockFlow::constructLine(BidiRunList<BidiRun>& bidiRuns, const LineInfo& lineInfo)
 187 {
 188     ASSERT(bidiRuns.firstRun());
 189
 190     bool rootHasSelectedChildren = false;
 191     InlineFlowBox* parentBox = 0;
 192     int runCount = bidiRuns.runCount() - lineInfo.runsFromLeadingWhitespace();
 193     for (BidiRun* r = bidiRuns.firstRun(); r; r = r->next()) {
 194         // Create a box for our object.
 195         bool isOnlyRun = (runCount == 1);
 196         if (runCount == 2 && !r->m_object->isListMarker())
 197             isOnlyRun = (!style()->isLeftToRightDirection() ? bidiRuns.lastRun() : bidiRuns.firstRun())->m_object->isListMarker();
 198
 199         if (lineInfo.isEmpty())
 200             continue;
 201
 202         InlineBox* box = createInlineBoxForRenderer(r->m_object, false, isOnlyRun);
 203         r->m_box = box;
 204
 205         ASSERT(box);
 206         if (!box)
 207             continue;
 208
 209         if (!rootHasSelectedChildren && box->renderer().selectionState() != RenderObject::SelectionNone)
 210             rootHasSelectedChildren = true;
 211
 212         // If we have no parent box yet, or if the run is not simply a sibling,
 213         // then we need to construct inline boxes as necessary to properly enclose the
 214         // run's inline box. Segments can only be siblings at the root level, as
 215         // they are positioned separately.
 216         if (!parentBox || parentBox->renderer() != r->m_object->parent()) {
 217             // Create new inline boxes all the way back to the appropriate insertion point.
 218             parentBox = createLineBoxes(r->m_object->parent(), lineInfo, box);
 219         } else {
 220             // Append the inline box to this line.
 221             parentBox->addToLine(box);
 222         }
 223
 224         bool visuallyOrdered = r->m_object->style()->rtlOrdering() == VisualOrder;
 225         box->setBidiLevel(r->level());
 226
 227         if (box->isInlineTextBox()) {
 228             InlineTextBox* text = toInlineTextBox(box);
 229             text->setStart(r->m_start);
 230             text->setLen(r->m_stop - r->m_start);
 231             text->setDirOverride(r->dirOverride(visuallyOrdered));
 232             if (r->m_hasHyphen)
 233                 text->setHasHyphen(true);
 234
 235             if (AXObjectCache* cache = document().existingAXObjectCache())
 236                 cache->inlineTextBoxesUpdated(r->m_object);
 237         }
 238     }
 239
 240     // We should have a root inline box.  It should be unconstructed and
 241     // be the last continuation of our line list.
 242     ASSERT(lastLineBox() && !lastLineBox()->isConstructed());
 243
 244     // Set the m_selectedChildren flag on the root inline box if one of the leaf inline box
 245     // from the bidi runs walk above has a selection state.
 246     if (rootHasSelectedChildren)
 247         lastLineBox()->root().setHasSelectedChildren(true);
 248
 249     // Set bits on our inline flow boxes that indicate which sides should
 250     // paint borders/margins/padding.  This knowledge will ultimately be used when
 251     // we determine the horizontal positions and widths of all the inline boxes on
 252     // the line.
 253     bool isLogicallyLastRunWrapped = bidiRuns.logicallyLastRun()->m_object && bidiRuns.logicallyLastRun()->m_object->isText() ? !reachedEndOfTextRenderer(bidiRuns) : true;
 254     lastLineBox()->determineSpacingForFlowBoxes(lineInfo.isLastLine(), isLogicallyLastRunWrapped, bidiRuns.logicallyLastRun()->m_object);
 255
 256     // Now mark the line boxes as being constructed.
 257     lastLineBox()->setConstructed();
 258
 259     // Return the last line.
 260     return lastRootBox();
 261 }
 262
 263 ETextAlign RenderBlockFlow::textAlignmentForLine(bool endsWithSoftBreak) const
 264 {
 265     ETextAlign alignment = style()->textAlign();
 266     if (endsWithSoftBreak)
 267         return alignment;
 268
 269     if (!RuntimeEnabledFeatures::css3TextEnabled())
 270         return (alignment == JUSTIFY) ? TASTART : alignment;
 271
 272     if (alignment != JUSTIFY)
 273         return alignment;
 274
 275     TextAlignLast alignmentLast = style()->textAlignLast();
 276     switch (alignmentLast) {
 277     case TextAlignLastStart:
 278         return TASTART;
 279     case TextAlignLastEnd:
 280         return TAEND;
 281     case TextAlignLastLeft:
 282         return LEFT;
 283     case TextAlignLastRight:
 284         return RIGHT;
 285     case TextAlignLastCenter:
 286         return CENTER;
 287     case TextAlignLastJustify:
 288         return JUSTIFY;
 289     case TextAlignLastAuto:
 290         if (style()->textJustify() == TextJustifyDistribute)
 291             return JUSTIFY;
 292         return TASTART;
 293     }
 294
 295     return alignment;
 296 }
 297
 298 static void updateLogicalWidthForLeftAlignedBlock(bool isLeftToRightDirection, BidiRun* trailingSpaceRun, float& logicalLeft, float& totalLogicalWidth, float availableLogicalWidth)
 299 {
 300     // The direction of the block should determine what happens with wide lines.
 301     // In particular with RTL blocks, wide lines should still spill out to the left.
 302     if (isLeftToRightDirection) {
 303         if (totalLogicalWidth > availableLogicalWidth && trailingSpaceRun)
 304             trailingSpaceRun->m_box->setLogicalWidth(std::max<float>(0, trailingSpaceRun->m_box->logicalWidth() - totalLogicalWidth + availableLogicalWidth));
 305         return;
 306     }
 307
 308     if (trailingSpaceRun)
 309         trailingSpaceRun->m_box->setLogicalWidth(0);
 310     else if (totalLogicalWidth > availableLogicalWidth)
 311         logicalLeft -= (totalLogicalWidth - availableLogicalWidth);
 312 }
 313
 314 static void updateLogicalWidthForRightAlignedBlock(bool isLeftToRightDirection, BidiRun* trailingSpaceRun, float& logicalLeft, float& totalLogicalWidth, float availableLogicalWidth)
 315 {
 316     // Wide lines spill out of the block based off direction.
 317     // So even if text-align is right, if direction is LTR, wide lines should overflow out of the right
 318     // side of the block.
 319     if (isLeftToRightDirection) {
 320         if (trailingSpaceRun) {
 321             totalLogicalWidth -= trailingSpaceRun->m_box->logicalWidth();
 322             trailingSpaceRun->m_box->setLogicalWidth(0);
 323         }
 324         if (totalLogicalWidth < availableLogicalWidth)
 325             logicalLeft += availableLogicalWidth - totalLogicalWidth;
 326         return;
 327     }
 328
 329     if (totalLogicalWidth > availableLogicalWidth && trailingSpaceRun) {
 330         trailingSpaceRun->m_box->setLogicalWidth(std::max<float>(0, trailingSpaceRun->m_box->logicalWidth() - totalLogicalWidth + availableLogicalWidth));
 331         totalLogicalWidth -= trailingSpaceRun->m_box->logicalWidth();
 332     } else
 333         logicalLeft += availableLogicalWidth - totalLogicalWidth;
 334 }
 335
 336 static void updateLogicalWidthForCenterAlignedBlock(bool isLeftToRightDirection, BidiRun* trailingSpaceRun, float& logicalLeft, float& totalLogicalWidth, float availableLogicalWidth)
 337 {
 338     float trailingSpaceWidth = 0;
 339     if (trailingSpaceRun) {
 340         totalLogicalWidth -= trailingSpaceRun->m_box->logicalWidth();
 341         trailingSpaceWidth = std::min(trailingSpaceRun->m_box->logicalWidth(), (availableLogicalWidth - totalLogicalWidth + 1) / 2);
 342         trailingSpaceRun->m_box->setLogicalWidth(std::max<float>(0, trailingSpaceWidth));
 343     }
 344     if (isLeftToRightDirection)
 345         logicalLeft += std::max<float>((availableLogicalWidth - totalLogicalWidth) / 2, 0);
 346     else
 347         logicalLeft += totalLogicalWidth > availableLogicalWidth ? (availableLogicalWidth - totalLogicalWidth) : (availableLogicalWidth - totalLogicalWidth) / 2 - trailingSpaceWidth;
 348 }
 349
 350 void RenderBlockFlow::setMarginsForRubyRun(BidiRun* run, RenderRubyRun* renderer, RenderObject* previousObject, const LineInfo& lineInfo)
 351 {
 352     int startOverhang;
 353     int endOverhang;
 354     RenderObject* nextObject = 0;
 355     for (BidiRun* runWithNextObject = run->next(); runWithNextObject; runWithNextObject = runWithNextObject->next()) {
 356         if (!runWithNextObject->m_object->isOutOfFlowPositioned() && !runWithNextObject->m_box->isLineBreak()) {
 357             nextObject = runWithNextObject->m_object;
 358             break;
 359         }
 360     }
 361     renderer->getOverhang(lineInfo.isFirstLine(), renderer->style()->isLeftToRightDirection() ? previousObject : nextObject, renderer->style()->isLeftToRightDirection() ? nextObject : previousObject, startOverhang, endOverhang);
 362     setMarginStartForChild(renderer, -startOverhang);
 363     setMarginEndForChild(renderer, -endOverhang);
 364 }
 365
 366 static inline void setLogicalWidthForTextRun(RootInlineBox* lineBox, BidiRun* run, RenderText* renderer, float xPos, const LineInfo& lineInfo,
 367                                              GlyphOverflowAndFallbackFontsMap& textBoxDataMap, VerticalPositionCache& verticalPositionCache, WordMeasurements& wordMeasurements)
 368 {
 369     HashSet<const SimpleFontData*> fallbackFonts;
 370     GlyphOverflow glyphOverflow;
 371
 372     const Font& font = renderer->style(lineInfo.isFirstLine())->font();
 373     // Always compute glyph overflow if the block's line-box-contain value is "glyphs".
 374     if (lineBox->fitsToGlyphs()) {
 375         // If we don't stick out of the root line's font box, then don't bother computing our glyph overflow. This optimization
 376         // will keep us from computing glyph bounds in nearly all cases.
 377         bool includeRootLine = lineBox->includesRootLineBoxFontOrLeading();
 378         int baselineShift = lineBox->verticalPositionForBox(run->m_box, verticalPositionCache);
 379         int rootDescent = includeRootLine ? font.fontMetrics().descent() : 0;
 380         int rootAscent = includeRootLine ? font.fontMetrics().ascent() : 0;
 381         int boxAscent = font.fontMetrics().ascent() - baselineShift;
 382         int boxDescent = font.fontMetrics().descent() + baselineShift;
 383         if (boxAscent > rootDescent ||  boxDescent > rootAscent)
 384             glyphOverflow.computeBounds = true;
 385     }
 386
 387     LayoutUnit hyphenWidth = 0;
 388     if (toInlineTextBox(run->m_box)->hasHyphen()) {
 389         const Font& font = renderer->style(lineInfo.isFirstLine())->font();
 390         hyphenWidth = measureHyphenWidth(renderer, font, run->direction());
 391     }
 392     float measuredWidth = 0;
 393
 394     bool kerningIsEnabled = font.fontDescription().typesettingFeatures() & Kerning;
 395
 396 #if OS(MACOSX)
 397     // FIXME: Having any font feature settings enabled can lead to selection gaps on
 398     // Chromium-mac. https://bugs.webkit.org/show_bug.cgi?id=113418
 399     bool canUseSimpleFontCodePath = renderer->canUseSimpleFontCodePath() && !font.fontDescription().featureSettings();
 400 #else
 401     bool canUseSimpleFontCodePath = renderer->canUseSimpleFontCodePath();
 402 #endif
 403
 404     // Since we don't cache glyph overflows, we need to re-measure the run if
 405     // the style is linebox-contain: glyph.
 406
 407     if (!lineBox->fitsToGlyphs() && canUseSimpleFontCodePath) {
 408         int lastEndOffset = run->m_start;
 409         for (size_t i = 0, size = wordMeasurements.size(); i < size && lastEndOffset < run->m_stop; ++i) {
 410             const WordMeasurement& wordMeasurement = wordMeasurements[i];
 411             if (wordMeasurement.width <=0 || wordMeasurement.startOffset == wordMeasurement.endOffset)
 412                 continue;
 413             if (wordMeasurement.renderer != renderer || wordMeasurement.startOffset != lastEndOffset || wordMeasurement.endOffset > run->m_stop)
 414                 continue;
 415
 416             lastEndOffset = wordMeasurement.endOffset;
 417             if (kerningIsEnabled && lastEndOffset == run->m_stop) {
 418                 int wordLength = lastEndOffset - wordMeasurement.startOffset;
 419                 measuredWidth += renderer->width(wordMeasurement.startOffset, wordLength, xPos, run->direction(), lineInfo.isFirstLine());
 420                 if (i > 0 && wordLength == 1 && renderer->characterAt(wordMeasurement.startOffset) == ' ')
 421                     measuredWidth += renderer->style()->wordSpacing();
 422             } else
 423                 measuredWidth += wordMeasurement.width;
 424             if (!wordMeasurement.fallbackFonts.isEmpty()) {
 425                 HashSet<const SimpleFontData*>::const_iterator end = wordMeasurement.fallbackFonts.end();
 426                 for (HashSet<const SimpleFontData*>::const_iterator it = wordMeasurement.fallbackFonts.begin(); it != end; ++it)
 427                     fallbackFonts.add(*it);
 428             }
 429         }
 430         if (measuredWidth && lastEndOffset != run->m_stop) {
 431             // If we don't have enough cached data, we'll measure the run again.
 432             measuredWidth = 0;
 433             fallbackFonts.clear();
 434         }
 435     }
 436
 437     if (!measuredWidth)
 438         measuredWidth = renderer->width(run->m_start, run->m_stop - run->m_start, xPos, run->direction(), lineInfo.isFirstLine(), &fallbackFonts, &glyphOverflow);
 439
 440     run->m_box->setLogicalWidth(measuredWidth + hyphenWidth);
 441     if (!fallbackFonts.isEmpty()) {
 442         ASSERT(run->m_box->isText());
 443         GlyphOverflowAndFallbackFontsMap::ValueType* it = textBoxDataMap.add(toInlineTextBox(run->m_box), std::make_pair(Vector<const SimpleFontData*>(), GlyphOverflow())).storedValue;
 444         ASSERT(it->value.first.isEmpty());
 445         copyToVector(fallbackFonts, it->value.first);
 446         run->m_box->parent()->clearDescendantsHaveSameLineHeightAndBaseline();
 447     }
 448     if (!glyphOverflow.isZero()) {
 449         ASSERT(run->m_box->isText());
 450         GlyphOverflowAndFallbackFontsMap::ValueType* it = textBoxDataMap.add(toInlineTextBox(run->m_box), std::make_pair(Vector<const SimpleFontData*>(), GlyphOverflow())).storedValue;
 451         it->value.second = glyphOverflow;
 452         run->m_box->clearKnownToHaveNoOverflow();
 453     }
 454 }
 455
 456 static inline void computeExpansionForJustifiedText(BidiRun* firstRun, BidiRun* trailingSpaceRun, Vector<unsigned, 16>& expansionOpportunities, unsigned expansionOpportunityCount, float& totalLogicalWidth, float availableLogicalWidth)
 457 {
 458     if (!expansionOpportunityCount || availableLogicalWidth <= totalLogicalWidth)
 459         return;
 460
 461     size_t i = 0;
 462     for (BidiRun* r = firstRun; r; r = r->next()) {
 463         if (!r->m_box || r == trailingSpaceRun)
 464             continue;
 465
 466         if (r->m_object->isText()) {
 467             unsigned opportunitiesInRun = expansionOpportunities[i++];
 468
 469             ASSERT(opportunitiesInRun <= expansionOpportunityCount);
 470
 471             // Don't justify for white-space: pre.
 472             if (r->m_object->style()->whiteSpace() != PRE) {
 473                 InlineTextBox* textBox = toInlineTextBox(r->m_box);
 474                 int expansion = (availableLogicalWidth - totalLogicalWidth) * opportunitiesInRun / expansionOpportunityCount;
 475                 textBox->setExpansion(expansion);
 476                 totalLogicalWidth += expansion;
 477             }
 478             expansionOpportunityCount -= opportunitiesInRun;
 479             if (!expansionOpportunityCount)
 480                 break;
 481         }
 482     }
 483 }
 484
 485 void RenderBlockFlow::updateLogicalWidthForAlignment(const ETextAlign& textAlign, const RootInlineBox* rootInlineBox, BidiRun* trailingSpaceRun, float& logicalLeft, float& totalLogicalWidth, float& availableLogicalWidth, unsigned expansionOpportunityCount)
 486 {
 487     TextDirection direction;
 488     if (rootInlineBox && rootInlineBox->renderer().style()->unicodeBidi() == Plaintext)
 489         direction = rootInlineBox->direction();
 490     else
 491         direction = style()->direction();
 492
 493     // Armed with the total width of the line (without justification),
 494     // we now examine our text-align property in order to determine where to position the
 495     // objects horizontally. The total width of the line can be increased if we end up
 496     // justifying text.
 497     switch (textAlign) {
 498     case LEFT:
 499     case WEBKIT_LEFT:
 500         updateLogicalWidthForLeftAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
 501         break;
 502     case RIGHT:
 503     case WEBKIT_RIGHT:
 504         updateLogicalWidthForRightAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
 505         break;
 506     case CENTER:
 507     case WEBKIT_CENTER:
 508         updateLogicalWidthForCenterAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
 509         break;
 510     case JUSTIFY:
 511         adjustInlineDirectionLineBounds(expansionOpportunityCount, logicalLeft, availableLogicalWidth);
 512         if (expansionOpportunityCount) {
 513             if (trailingSpaceRun) {
 514                 totalLogicalWidth -= trailingSpaceRun->m_box->logicalWidth();
 515                 trailingSpaceRun->m_box->setLogicalWidth(0);
 516             }
 517             break;
 518         }
 519         // Fall through
 520     case TASTART:
 521         if (direction == LTR)
 522             updateLogicalWidthForLeftAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
 523         else
 524             updateLogicalWidthForRightAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
 525         break;
 526     case TAEND:
 527         if (direction == LTR)
 528             updateLogicalWidthForRightAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
 529         else
 530             updateLogicalWidthForLeftAlignedBlock(style()->isLeftToRightDirection(), trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth);
 531         break;
 532     }
 533     if (style()->shouldPlaceBlockDirectionScrollbarOnLogicalLeft())
 534         logicalLeft += verticalScrollbarWidth();
 535 }
 536
 537 static void updateLogicalInlinePositions(RenderBlockFlow* block, float& lineLogicalLeft, float& lineLogicalRight, float& availableLogicalWidth, bool firstLine, IndentTextOrNot shouldIndentText, LayoutUnit boxLogicalHeight)
 538 {
 539     LayoutUnit lineLogicalHeight = block->minLineHeightForReplacedRenderer(firstLine, boxLogicalHeight);
 540     lineLogicalLeft = block->logicalLeftOffsetForLine(block->logicalHeight(), shouldIndentText == IndentText, lineLogicalHeight).toFloat();
 541     lineLogicalRight = block->logicalRightOffsetForLine(block->logicalHeight(), shouldIndentText == IndentText, lineLogicalHeight).toFloat();
 542     availableLogicalWidth = lineLogicalRight - lineLogicalLeft;
 543 }
 544
 545 void RenderBlockFlow::computeInlineDirectionPositionsForLine(RootInlineBox* lineBox, const LineInfo& lineInfo, BidiRun* firstRun, BidiRun* trailingSpaceRun, bool reachedEnd,
 546                                                          GlyphOverflowAndFallbackFontsMap& textBoxDataMap, VerticalPositionCache& verticalPositionCache, WordMeasurements& wordMeasurements)
 547 {
 548     ETextAlign textAlign = textAlignmentForLine(!reachedEnd && !lineBox->endsWithBreak());
 549
 550     // 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
 551     // box is only affected if it is the first child of its parent element."
 552     // CSS3 "text-indent", "each-line" affects the first line of the block container as well as each line after a forced line break,
 553     // but does not affect lines after a soft wrap break.
 554     bool isFirstLine = lineInfo.isFirstLine() && !(isAnonymousBlock() && parent()->slowFirstChild() != this);
 555     bool isAfterHardLineBreak = lineBox->prevRootBox() && lineBox->prevRootBox()->endsWithBreak();
 556     IndentTextOrNot shouldIndentText = requiresIndent(isFirstLine, isAfterHardLineBreak, style());
 557     float lineLogicalLeft;
 558     float lineLogicalRight;
 559     float availableLogicalWidth;
 560     updateLogicalInlinePositions(this, lineLogicalLeft, lineLogicalRight, availableLogicalWidth, isFirstLine, shouldIndentText, 0);
 561     bool needsWordSpacing;
 562
 563     if (firstRun && firstRun->m_object->isReplaced()) {
 564         RenderBox* renderBox = toRenderBox(firstRun->m_object);
 565         updateLogicalInlinePositions(this, lineLogicalLeft, lineLogicalRight, availableLogicalWidth, isFirstLine, shouldIndentText, renderBox->logicalHeight());
 566     }
 567
 568     computeInlineDirectionPositionsForSegment(lineBox, lineInfo, textAlign, lineLogicalLeft, availableLogicalWidth, firstRun, trailingSpaceRun, textBoxDataMap, verticalPositionCache, wordMeasurements);
 569     // The widths of all runs are now known. We can now place every inline box (and
 570     // compute accurate widths for the inline flow boxes).
 571     needsWordSpacing = lineBox->isLeftToRightDirection() ? false: true;
 572     lineBox->placeBoxesInInlineDirection(lineLogicalLeft, needsWordSpacing);
 573 }
 574
 575 BidiRun* RenderBlockFlow::computeInlineDirectionPositionsForSegment(RootInlineBox* lineBox, const LineInfo& lineInfo, ETextAlign textAlign, float& logicalLeft,
 576     float& availableLogicalWidth, BidiRun* firstRun, BidiRun* trailingSpaceRun, GlyphOverflowAndFallbackFontsMap& textBoxDataMap, VerticalPositionCache& verticalPositionCache,
 577     WordMeasurements& wordMeasurements)
 578 {
 579     bool needsWordSpacing = true;
 580     float totalLogicalWidth = lineBox->getFlowSpacingLogicalWidth().toFloat();
 581     unsigned expansionOpportunityCount = 0;
 582     bool isAfterExpansion = true;
 583     Vector<unsigned, 16> expansionOpportunities;
 584     RenderObject* previousObject = 0;
 585     TextJustify textJustify = style()->textJustify();
 586
 587     BidiRun* r = firstRun;
 588     for (; r; r = r->next()) {
 589         if (!r->m_box || r->m_object->isOutOfFlowPositioned() || r->m_box->isLineBreak())
 590             continue; // Positioned objects are only participating to figure out their
 591                       // correct static x position.  They have no effect on the width.
 592                       // Similarly, line break boxes have no effect on the width.
 593         if (r->m_object->isText()) {
 594             RenderText* rt = toRenderText(r->m_object);
 595             if (textAlign == JUSTIFY && r != trailingSpaceRun && textJustify != TextJustifyNone) {
 596                 if (!isAfterExpansion)
 597                     toInlineTextBox(r->m_box)->setCanHaveLeadingExpansion(true);
 598                 unsigned opportunitiesInRun;
 599                 if (rt->is8Bit())
 600                     opportunitiesInRun = Character::expansionOpportunityCount(rt->characters8() + r->m_start, r->m_stop - r->m_start, r->m_box->direction(), isAfterExpansion);
 601                 else
 602                     opportunitiesInRun = Character::expansionOpportunityCount(rt->characters16() + r->m_start, r->m_stop - r->m_start, r->m_box->direction(), isAfterExpansion);
 603                 expansionOpportunities.append(opportunitiesInRun);
 604                 expansionOpportunityCount += opportunitiesInRun;
 605             }
 606
 607             if (rt->textLength()) {
 608                 if (!r->m_start && needsWordSpacing && isSpaceOrNewline(rt->characterAt(r->m_start)))
 609                     totalLogicalWidth += rt->style(lineInfo.isFirstLine())->font().fontDescription().wordSpacing();
 610                 needsWordSpacing = !isSpaceOrNewline(rt->characterAt(r->m_stop - 1));
 611             }
 612
 613             setLogicalWidthForTextRun(lineBox, r, rt, totalLogicalWidth, lineInfo, textBoxDataMap, verticalPositionCache, wordMeasurements);
 614         } else {
 615             isAfterExpansion = false;
 616             if (!r->m_object->isRenderInline()) {
 617                 RenderBox* renderBox = toRenderBox(r->m_object);
 618                 if (renderBox->isRubyRun())
 619                     setMarginsForRubyRun(r, toRenderRubyRun(renderBox), previousObject, lineInfo);
 620                 r->m_box->setLogicalWidth(logicalWidthForChild(renderBox).toFloat());
 621                 totalLogicalWidth += marginStartForChild(renderBox) + marginEndForChild(renderBox);
 622             }
 623         }
 624
 625         totalLogicalWidth += r->m_box->logicalWidth();
 626         previousObject = r->m_object;
 627     }
 628
 629     if (isAfterExpansion && !expansionOpportunities.isEmpty()) {
 630         expansionOpportunities.last()--;
 631         expansionOpportunityCount--;
 632     }
 633
 634     updateLogicalWidthForAlignment(textAlign, lineBox, trailingSpaceRun, logicalLeft, totalLogicalWidth, availableLogicalWidth, expansionOpportunityCount);
 635
 636     computeExpansionForJustifiedText(firstRun, trailingSpaceRun, expansionOpportunities, expansionOpportunityCount, totalLogicalWidth, availableLogicalWidth);
 637
 638     return r;
 639 }
 640
 641 void RenderBlockFlow::computeBlockDirectionPositionsForLine(RootInlineBox* lineBox, BidiRun* firstRun, GlyphOverflowAndFallbackFontsMap& textBoxDataMap,
 642                                                         VerticalPositionCache& verticalPositionCache)
 643 {
 644     setLogicalHeight(lineBox->alignBoxesInBlockDirection(logicalHeight(), textBoxDataMap, verticalPositionCache));
 645
 646     // Now make sure we place replaced render objects correctly.
 647     for (BidiRun* r = firstRun; r; r = r->next()) {
 648         ASSERT(r->m_box);
 649         if (!r->m_box)
 650             continue; // Skip runs with no line boxes.
 651
 652         // Align positioned boxes with the top of the line box.  This is
 653         // a reasonable approximation of an appropriate y position.
 654         if (r->m_object->isOutOfFlowPositioned())
 655             r->m_box->setLogicalTop(logicalHeight().toFloat());
 656
 657         // Position is used to properly position both replaced elements and
 658         // to update the static normal flow x/y of positioned elements.
 659         if (r->m_object->isText())
 660             toRenderText(r->m_object)->positionLineBox(r->m_box);
 661         else if (r->m_object->isBox())
 662             toRenderBox(r->m_object)->positionLineBox(r->m_box);
 663     }
 664 }
 665
 666 void RenderBlockFlow::appendFloatingObjectToLastLine(FloatingObject* floatingObject)
 667 {
 668     ASSERT(!floatingObject->originatingLine());
 669     floatingObject->setOriginatingLine(lastRootBox());
 670     lastRootBox()->appendFloat(floatingObject->renderer());
 671 }
 672
 673 // This function constructs line boxes for all of the text runs in the resolver and computes their position.
 674 RootInlineBox* RenderBlockFlow::createLineBoxesFromBidiRuns(unsigned bidiLevel, BidiRunList<BidiRun>& bidiRuns, const InlineIterator& end, LineInfo& lineInfo, VerticalPositionCache& verticalPositionCache, BidiRun* trailingSpaceRun, WordMeasurements& wordMeasurements)
 675 {
 676     if (!bidiRuns.runCount())
 677         return 0;
 678
 679     // FIXME: Why is this only done when we had runs?
 680     lineInfo.setLastLine(!end.object());
 681
 682     RootInlineBox* lineBox = constructLine(bidiRuns, lineInfo);
 683     if (!lineBox)
 684         return 0;
 685
 686     lineBox->setBidiLevel(bidiLevel);
 687     lineBox->setEndsWithBreak(lineInfo.previousLineBrokeCleanly());
 688
 689     bool isSVGRootInlineBox = lineBox->isSVGRootInlineBox();
 690
 691     GlyphOverflowAndFallbackFontsMap textBoxDataMap;
 692
 693     // Now we position all of our text runs horizontally.
 694     if (!isSVGRootInlineBox)
 695         computeInlineDirectionPositionsForLine(lineBox, lineInfo, bidiRuns.firstRun(), trailingSpaceRun, end.atEnd(), textBoxDataMap, verticalPositionCache, wordMeasurements);
 696
 697     // Now position our text runs vertically.
 698     computeBlockDirectionPositionsForLine(lineBox, bidiRuns.firstRun(), textBoxDataMap, verticalPositionCache);
 699
 700     // SVG text layout code computes vertical & horizontal positions on its own.
 701     // Note that we still need to execute computeVerticalPositionsForLine() as
 702     // it calls InlineTextBox::positionLineBox(), which tracks whether the box
 703     // contains reversed text or not. If we wouldn't do that editing and thus
 704     // text selection in RTL boxes would not work as expected.
 705     if (isSVGRootInlineBox) {
 706         ASSERT(isSVGText());
 707         toSVGRootInlineBox(lineBox)->computePerCharacterLayoutInformation();
 708     }
 709
 710     // Compute our overflow now.
 711     lineBox->computeOverflow(lineBox->lineTop(), lineBox->lineBottom(), textBoxDataMap);
 712
 713     return lineBox;
 714 }
 715
 716 static void deleteLineRange(LineLayoutState& layoutState, RootInlineBox* startLine, RootInlineBox* stopLine = 0)
 717 {
 718     RootInlineBox* boxToDelete = startLine;
 719     while (boxToDelete && boxToDelete != stopLine) {
 720         layoutState.updatePaintInvalidationRangeFromBox(boxToDelete);
 721         // Note: deleteLineRange(firstRootBox()) is not identical to deleteLineBoxTree().
 722         // deleteLineBoxTree uses nextLineBox() instead of nextRootBox() when traversing.
 723         RootInlineBox* next = boxToDelete->nextRootBox();
 724         boxToDelete->deleteLine();
 725         boxToDelete = next;
 726     }
 727 }
 728
 729 void RenderBlockFlow::layoutRunsAndFloats(LineLayoutState& layoutState)
 730 {
 731     // We want to skip ahead to the first dirty line
 732     InlineBidiResolver resolver;
 733     RootInlineBox* startLine = determineStartPosition(layoutState, resolver);
 734
 735     if (containsFloats())
 736         layoutState.setLastFloat(m_floatingObjects->set().last().get());
 737
 738     // We also find the first clean line and extract these lines.  We will add them back
 739     // if we determine that we're able to synchronize after handling all our dirty lines.
 740     InlineIterator cleanLineStart;
 741     BidiStatus cleanLineBidiStatus;
 742     if (!layoutState.isFullLayout() && startLine)
 743         determineEndPosition(layoutState, startLine, cleanLineStart, cleanLineBidiStatus);
 744
 745     if (startLine) {
 746         if (!layoutState.usesPaintInvalidationBounds())
 747             layoutState.setPaintInvalidationRange(logicalHeight());
 748         deleteLineRange(layoutState, startLine);
 749     }
 750
 751     if (!layoutState.isFullLayout() && lastRootBox() && lastRootBox()->endsWithBreak()) {
 752         // If the last line before the start line ends with a line break that clear floats,
 753         // adjust the height accordingly.
 754         // A line break can be either the first or the last object on a line, depending on its direction.
 755         if (InlineBox* lastLeafChild = lastRootBox()->lastLeafChild()) {
 756             RenderObject* lastObject = &lastLeafChild->renderer();
 757             if (!lastObject->isBR())
 758                 lastObject = &lastRootBox()->firstLeafChild()->renderer();
 759             if (lastObject->isBR()) {
 760                 EClear clear = lastObject->style()->clear();
 761                 if (clear != CNONE)
 762                     clearFloats(clear);
 763             }
 764         }
 765     }
 766
 767     layoutRunsAndFloatsInRange(layoutState, resolver, cleanLineStart, cleanLineBidiStatus);
 768     linkToEndLineIfNeeded(layoutState);
 769     markDirtyFloatsForPaintInvalidation(layoutState.floats());
 770 }
 771
 772 // Before restarting the layout loop with a new logicalHeight, remove all floats that were added and reset the resolver.
 773 inline const InlineIterator& RenderBlockFlow::restartLayoutRunsAndFloatsInRange(LayoutUnit oldLogicalHeight, LayoutUnit newLogicalHeight,  FloatingObject* lastFloatFromPreviousLine, InlineBidiResolver& resolver,  const InlineIterator& oldEnd)
 774 {
 775     removeFloatingObjectsBelow(lastFloatFromPreviousLine, oldLogicalHeight);
 776     setLogicalHeight(newLogicalHeight);
 777     resolver.setPositionIgnoringNestedIsolates(oldEnd);
 778     return oldEnd;
 779 }
 780
 781 void RenderBlockFlow::layoutRunsAndFloatsInRange(LineLayoutState& layoutState,
 782     InlineBidiResolver& resolver, const InlineIterator& cleanLineStart,
 783     const BidiStatus& cleanLineBidiStatus)
 784 {
 785     RenderStyle* styleToUse = style();
 786     bool paginated = view()->layoutState() && view()->layoutState()->isPaginated();
 787     LineMidpointState& lineMidpointState = resolver.midpointState();
 788     InlineIterator endOfLine = resolver.position();
 789     bool checkForEndLineMatch = layoutState.endLine();
 790     RenderTextInfo renderTextInfo;
 791     VerticalPositionCache verticalPositionCache;
 792
 793     LineBreaker lineBreaker(this);
 794
 795     while (!endOfLine.atEnd()) {
 796         // FIXME: Is this check necessary before the first iteration or can it be moved to the end?
 797         if (checkForEndLineMatch) {
 798             layoutState.setEndLineMatched(matchedEndLine(layoutState, resolver, cleanLineStart, cleanLineBidiStatus));
 799             if (layoutState.endLineMatched()) {
 800                 resolver.setPosition(InlineIterator(resolver.position().root(), 0, 0), 0);
 801                 break;
 802             }
 803         }
 804
 805         lineMidpointState.reset();
 806
 807         layoutState.lineInfo().setEmpty(true);
 808         layoutState.lineInfo().resetRunsFromLeadingWhitespace();
 809
 810         const InlineIterator previousEndofLine = endOfLine;
 811         bool isNewUBAParagraph = layoutState.lineInfo().previousLineBrokeCleanly();
 812         FloatingObject* lastFloatFromPreviousLine = (containsFloats()) ? m_floatingObjects->set().last().get() : 0;
 813
 814         WordMeasurements wordMeasurements;
 815         endOfLine = lineBreaker.nextLineBreak(resolver, layoutState.lineInfo(), renderTextInfo,
 816             lastFloatFromPreviousLine, wordMeasurements);
 817         renderTextInfo.m_lineBreakIterator.resetPriorContext();
 818         if (resolver.position().atEnd()) {
 819             // FIXME: We shouldn't be creating any runs in nextLineBreak to begin with!
 820             // Once BidiRunList is separated from BidiResolver this will not be needed.
 821             resolver.runs().deleteRuns();
 822             resolver.markCurrentRunEmpty(); // FIXME: This can probably be replaced by an ASSERT (or just removed).
 823             layoutState.setCheckForFloatsFromLastLine(true);
 824             resolver.setPosition(InlineIterator(resolver.position().root(), 0, 0), 0);
 825             break;
 826         }
 827
 828         ASSERT(endOfLine != resolver.position());
 829
 830         // This is a short-cut for empty lines.
 831         if (layoutState.lineInfo().isEmpty()) {
 832             if (lastRootBox())
 833                 lastRootBox()->setLineBreakInfo(endOfLine.object(), endOfLine.offset(), resolver.status());
 834         } else {
 835             VisualDirectionOverride override = (styleToUse->rtlOrdering() == VisualOrder ? (styleToUse->direction() == LTR ? VisualLeftToRightOverride : VisualRightToLeftOverride) : NoVisualOverride);
 836             if (isNewUBAParagraph && styleToUse->unicodeBidi() == Plaintext && !resolver.context()->parent()) {
 837                 TextDirection direction = determinePlaintextDirectionality(resolver.position().root(), resolver.position().object(), resolver.position().offset());
 838                 resolver.setStatus(BidiStatus(direction, isOverride(styleToUse->unicodeBidi())));
 839             }
 840             // FIXME: This ownership is reversed. We should own the BidiRunList and pass it to createBidiRunsForLine.
 841             BidiRunList<BidiRun>& bidiRuns = resolver.runs();
 842             constructBidiRunsForLine(resolver, bidiRuns, endOfLine, override, layoutState.lineInfo().previousLineBrokeCleanly(), isNewUBAParagraph);
 843             ASSERT(resolver.position() == endOfLine);
 844
 845             BidiRun* trailingSpaceRun = resolver.trailingSpaceRun();
 846
 847             if (bidiRuns.runCount() && lineBreaker.lineWasHyphenated())
 848                 bidiRuns.logicallyLastRun()->m_hasHyphen = true;
 849
 850             // Now that the runs have been ordered, we create the line boxes.
 851             // At the same time we figure out where border/padding/margin should be applied for
 852             // inline flow boxes.
 853
 854             LayoutUnit oldLogicalHeight = logicalHeight();
 855             RootInlineBox* lineBox = createLineBoxesFromBidiRuns(resolver.status().context->level(), bidiRuns, endOfLine, layoutState.lineInfo(), verticalPositionCache, trailingSpaceRun, wordMeasurements);
 856
 857             bidiRuns.deleteRuns();
 858             resolver.markCurrentRunEmpty(); // FIXME: This can probably be replaced by an ASSERT (or just removed).
 859
 860             if (lineBox) {
 861                 lineBox->setLineBreakInfo(endOfLine.object(), endOfLine.offset(), resolver.status());
 862                 if (layoutState.usesPaintInvalidationBounds())
 863                     layoutState.updatePaintInvalidationRangeFromBox(lineBox);
 864
 865                 if (paginated) {
 866                     LayoutUnit adjustment = 0;
 867                     adjustLinePositionForPagination(lineBox, adjustment, layoutState.flowThread());
 868                     if (adjustment) {
 869                         LayoutUnit oldLineWidth = availableLogicalWidthForLine(oldLogicalHeight, layoutState.lineInfo().isFirstLine());
 870                         lineBox->adjustBlockDirectionPosition(adjustment.toFloat());
 871                         if (layoutState.usesPaintInvalidationBounds())
 872                             layoutState.updatePaintInvalidationRangeFromBox(lineBox);
 873
 874                         if (availableLogicalWidthForLine(oldLogicalHeight + adjustment, layoutState.lineInfo().isFirstLine()) != oldLineWidth) {
 875                             // We have to delete this line, remove all floats that got added, and let line layout re-run.
 876                             lineBox->deleteLine();
 877                             endOfLine = restartLayoutRunsAndFloatsInRange(oldLogicalHeight, oldLogicalHeight + adjustment, lastFloatFromPreviousLine, resolver, previousEndofLine);
 878                             continue;
 879                         }
 880
 881                         setLogicalHeight(lineBox->lineBottomWithLeading());
 882                     }
 883                 }
 884             }
 885         }
 886
 887         for (size_t i = 0; i < lineBreaker.positionedObjects().size(); ++i)
 888             setStaticPositions(this, lineBreaker.positionedObjects()[i]);
 889
 890         if (!layoutState.lineInfo().isEmpty()) {
 891             layoutState.lineInfo().setFirstLine(false);
 892             clearFloats(lineBreaker.clear());
 893         }
 894
 895         if (m_floatingObjects && lastRootBox()) {
 896             const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
 897             FloatingObjectSetIterator it = floatingObjectSet.begin();
 898             FloatingObjectSetIterator end = floatingObjectSet.end();
 899             if (layoutState.lastFloat()) {
 900                 FloatingObjectSetIterator lastFloatIterator = floatingObjectSet.find(layoutState.lastFloat());
 901                 ASSERT(lastFloatIterator != end);
 902                 ++lastFloatIterator;
 903                 it = lastFloatIterator;
 904             }
 905             for (; it != end; ++it) {
 906                 FloatingObject* f = it->get();
 907                 appendFloatingObjectToLastLine(f);
 908                 ASSERT(f->renderer() == layoutState.floats()[layoutState.floatIndex()].object);
 909                 // If a float's geometry has changed, give up on syncing with clean lines.
 910                 if (layoutState.floats()[layoutState.floatIndex()].rect != f->frameRect())
 911                     checkForEndLineMatch = false;
 912                 layoutState.setFloatIndex(layoutState.floatIndex() + 1);
 913             }
 914             layoutState.setLastFloat(!floatingObjectSet.isEmpty() ? floatingObjectSet.last().get() : 0);
 915         }
 916
 917         lineMidpointState.reset();
 918         resolver.setPosition(endOfLine, numberOfIsolateAncestors(endOfLine));
 919     }
 920
 921     // In case we already adjusted the line positions during this layout to avoid widows
 922     // then we need to ignore the possibility of having a new widows situation.
 923     // Otherwise, we risk leaving empty containers which is against the block fragmentation principles.
 924     if (paginated && !style()->hasAutoWidows() && !didBreakAtLineToAvoidWidow()) {
 925         // Check the line boxes to make sure we didn't create unacceptable widows.
 926         // However, we'll prioritize orphans - so nothing we do here should create
 927         // a new orphan.
 928
 929         RootInlineBox* lineBox = lastRootBox();
 930
 931         // Count from the end of the block backwards, to see how many hanging
 932         // lines we have.
 933         RootInlineBox* firstLineInBlock = firstRootBox();
 934         int numLinesHanging = 1;
 935         while (lineBox && lineBox != firstLineInBlock && !lineBox->isFirstAfterPageBreak()) {
 936             ++numLinesHanging;
 937             lineBox = lineBox->prevRootBox();
 938         }
 939
 940         // If there were no breaks in the block, we didn't create any widows.
 941         if (!lineBox || !lineBox->isFirstAfterPageBreak() || lineBox == firstLineInBlock)
 942             return;
 943
 944         if (numLinesHanging < style()->widows()) {
 945             // We have detected a widow. Now we need to work out how many
 946             // lines there are on the previous page, and how many we need
 947             // to steal.
 948             int numLinesNeeded = style()->widows() - numLinesHanging;
 949             RootInlineBox* currentFirstLineOfNewPage = lineBox;
 950
 951             // Count the number of lines in the previous page.
 952             lineBox = lineBox->prevRootBox();
 953             int numLinesInPreviousPage = 1;
 954             while (lineBox && lineBox != firstLineInBlock && !lineBox->isFirstAfterPageBreak()) {
 955                 ++numLinesInPreviousPage;
 956                 lineBox = lineBox->prevRootBox();
 957             }
 958
 959             // If there was an explicit value for orphans, respect that. If not, we still
 960             // shouldn't create a situation where we make an orphan bigger than the initial value.
 961             // This means that setting widows implies we also care about orphans, but given
 962             // the specification says the initial orphan value is non-zero, this is ok. The
 963             // author is always free to set orphans explicitly as well.
 964             int orphans = style()->hasAutoOrphans() ? style()->initialOrphans() : style()->orphans();
 965             int numLinesAvailable = numLinesInPreviousPage - orphans;
 966             if (numLinesAvailable <= 0)
 967                 return;
 968
 969             int numLinesToTake = std::min(numLinesAvailable, numLinesNeeded);
 970             // Wind back from our first widowed line.
 971             lineBox = currentFirstLineOfNewPage;
 972             for (int i = 0; i < numLinesToTake; ++i)
 973                 lineBox = lineBox->prevRootBox();
 974
 975             // We now want to break at this line. Remember for next layout and trigger relayout.
 976             setBreakAtLineToAvoidWidow(lineCount(lineBox));
 977             markLinesDirtyInBlockRange(lastRootBox()->lineBottomWithLeading(), lineBox->lineBottomWithLeading(), lineBox);
 978         }
 979     }
 980
 981     clearDidBreakAtLineToAvoidWidow();
 982 }
 983
 984 void RenderBlockFlow::linkToEndLineIfNeeded(LineLayoutState& layoutState)
 985 {
 986     if (layoutState.endLine()) {
 987         if (layoutState.endLineMatched()) {
 988             bool paginated = view()->layoutState() && view()->layoutState()->isPaginated();
 989             // Attach all the remaining lines, and then adjust their y-positions as needed.
 990             LayoutUnit delta = logicalHeight() - layoutState.endLineLogicalTop();
 991             for (RootInlineBox* line = layoutState.endLine(); line; line = line->nextRootBox()) {
 992                 line->attachLine();
 993                 if (paginated) {
 994                     delta -= line->paginationStrut();
 995                     adjustLinePositionForPagination(line, delta, layoutState.flowThread());
 996                 }
 997                 if (delta) {
 998                     layoutState.updatePaintInvalidationRangeFromBox(line, delta);
 999                     line->adjustBlockDirectionPosition(delta.toFloat());
1000                 }
1001                 if (Vector<RenderBox*>* cleanLineFloats = line->floatsPtr()) {
1002                     Vector<RenderBox*>::iterator end = cleanLineFloats->end();
1003                     for (Vector<RenderBox*>::iterator f = cleanLineFloats->begin(); f != end; ++f) {
1004                         FloatingObject* floatingObject = insertFloatingObject(*f);
1005                         ASSERT(!floatingObject->originatingLine());
1006                         floatingObject->setOriginatingLine(line);
1007                         setLogicalHeight(logicalTopForChild(*f) - marginBeforeForChild(*f) + delta);
1008                         positionNewFloats();
1009                     }
1010                 }
1011             }
1012             setLogicalHeight(lastRootBox()->lineBottomWithLeading());
1013         } else {
1014             // Delete all the remaining lines.
1015             deleteLineRange(layoutState, layoutState.endLine());
1016         }
1017     }
1018
1019     if (m_floatingObjects && (layoutState.checkForFloatsFromLastLine() || positionNewFloats()) && lastRootBox()) {
1020         // In case we have a float on the last line, it might not be positioned up to now.
1021         // This has to be done before adding in the bottom border/padding, or the float will
1022         // include the padding incorrectly. -dwh
1023         const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1024         FloatingObjectSetIterator it = floatingObjectSet.begin();
1025         FloatingObjectSetIterator end = floatingObjectSet.end();
1026         if (layoutState.lastFloat()) {
1027             FloatingObjectSetIterator lastFloatIterator = floatingObjectSet.find(layoutState.lastFloat());
1028             ASSERT(lastFloatIterator != end);
1029             ++lastFloatIterator;
1030             it = lastFloatIterator;
1031         }
1032         layoutState.setLastFloat(!floatingObjectSet.isEmpty() ? floatingObjectSet.last().get() : 0);
1033
1034         if (it == end)
1035             return;
1036
1037         if (layoutState.checkForFloatsFromLastLine()) {
1038             LayoutUnit bottomVisualOverflow = lastRootBox()->logicalBottomVisualOverflow();
1039             LayoutUnit bottomLayoutOverflow = lastRootBox()->logicalBottomLayoutOverflow();
1040             TrailingFloatsRootInlineBox* trailingFloatsLineBox = new TrailingFloatsRootInlineBox(*this);
1041             m_lineBoxes.appendLineBox(trailingFloatsLineBox);
1042             trailingFloatsLineBox->setConstructed();
1043             GlyphOverflowAndFallbackFontsMap textBoxDataMap;
1044             VerticalPositionCache verticalPositionCache;
1045             LayoutUnit blockLogicalHeight = logicalHeight();
1046             trailingFloatsLineBox->alignBoxesInBlockDirection(blockLogicalHeight, textBoxDataMap, verticalPositionCache);
1047             trailingFloatsLineBox->setLineTopBottomPositions(blockLogicalHeight, blockLogicalHeight, blockLogicalHeight, blockLogicalHeight);
1048             trailingFloatsLineBox->setPaginatedLineWidth(availableLogicalWidthForContent());
1049             LayoutRect logicalLayoutOverflow(0, blockLogicalHeight, 1, bottomLayoutOverflow - blockLogicalHeight);
1050             LayoutRect logicalVisualOverflow(0, blockLogicalHeight, 1, bottomVisualOverflow - blockLogicalHeight);
1051             trailingFloatsLineBox->setOverflowFromLogicalRects(logicalLayoutOverflow, logicalVisualOverflow, trailingFloatsLineBox->lineTop(), trailingFloatsLineBox->lineBottom());
1052         }
1053
1054         for (; it != end; ++it)
1055             appendFloatingObjectToLastLine(it->get());
1056     }
1057 }
1058
1059 void RenderBlockFlow::markDirtyFloatsForPaintInvalidation(Vector<FloatWithRect>& floats)
1060 {
1061     size_t floatCount = floats.size();
1062     // Floats that did not have layout did not paint invalidations when we laid them out. They would have
1063     // painted by now if they had moved, but if they stayed at (0, 0), they still need to be
1064     // painted.
1065     for (size_t i = 0; i < floatCount; ++i) {
1066         if (!floats[i].everHadLayout) {
1067             RenderBox* f = floats[i].object;
1068             if (!f->x() && !f->y() && f->checkForPaintInvalidation()) {
1069                 f->setShouldDoFullPaintInvalidation(true);
1070             }
1071         }
1072     }
1073 }
1074
1075 struct InlineMinMaxIterator {
1076 /* InlineMinMaxIterator is a class that will iterate over all render objects that contribute to
1077    inline min/max width calculations.  Note the following about the way it walks:
1078    (1) Positioned content is skipped (since it does not contribute to min/max width of a block)
1079    (2) We do not drill into the children of floats or replaced elements, since you can't break
1080        in the middle of such an element.
1081    (3) Inline flows (e.g., <a>, <span>, <i>) are walked twice, since each side can have
1082        distinct borders/margin/padding that contribute to the min/max width.
1083 */
1084     RenderObject* parent;
1085     RenderObject* current;
1086     bool endOfInline;
1087
1088     InlineMinMaxIterator(RenderObject* p, bool end = false)
1089         : parent(p), current(p), endOfInline(end)
1090     {
1091
1092     }
1093
1094     RenderObject* next();
1095 };
1096
1097 RenderObject* InlineMinMaxIterator::next()
1098 {
1099     RenderObject* result = 0;
1100     bool oldEndOfInline = endOfInline;
1101     endOfInline = false;
1102     while (current || current == parent) {
1103         if (!oldEndOfInline && (current == parent || (!current->isFloating() && !current->isReplaced() && !current->isOutOfFlowPositioned())))
1104             result = current->slowFirstChild();
1105
1106         if (!result) {
1107             // We hit the end of our inline. (It was empty, e.g., <span></span>.)
1108             if (!oldEndOfInline && current->isRenderInline()) {
1109                 result = current;
1110                 endOfInline = true;
1111                 break;
1112             }
1113
1114             while (current && current != parent) {
1115                 result = current->nextSibling();
1116                 if (result)
1117                     break;
1118                 current = current->parent();
1119                 if (current && current != parent && current->isRenderInline()) {
1120                     result = current;
1121                     endOfInline = true;
1122                     break;
1123                 }
1124             }
1125         }
1126
1127         if (!result)
1128             break;
1129
1130         if (!result->isOutOfFlowPositioned() && (result->isText() || result->isFloating() || result->isReplaced() || result->isRenderInline()))
1131             break;
1132
1133         current = result;
1134         result = 0;
1135     }
1136
1137     // Update our position.
1138     current = result;
1139     return current;
1140 }
1141
1142 static LayoutUnit getBPMWidth(LayoutUnit childValue, Length cssUnit)
1143 {
1144     if (cssUnit.type() != Auto)
1145         return (cssUnit.isFixed() ? static_cast<LayoutUnit>(cssUnit.value()) : childValue);
1146     return 0;
1147 }
1148
1149 static LayoutUnit getBorderPaddingMargin(RenderBoxModelObject* child, bool endOfInline)
1150 {
1151     RenderStyle* childStyle = child->style();
1152     if (endOfInline) {
1153         return getBPMWidth(child->marginEnd(), childStyle->marginEnd()) +
1154             getBPMWidth(child->paddingEnd(), childStyle->paddingEnd()) +
1155             child->borderEnd();
1156     }
1157     return getBPMWidth(child->marginStart(), childStyle->marginStart()) +
1158         getBPMWidth(child->paddingStart(), childStyle->paddingStart()) +
1159         child->borderStart();
1160 }
1161
1162 static inline void stripTrailingSpace(float& inlineMax, float& inlineMin, RenderObject* trailingSpaceChild)
1163 {
1164     if (trailingSpaceChild && trailingSpaceChild->isText()) {
1165         // Collapse away the trailing space at the end of a block.
1166         RenderText* t = toRenderText(trailingSpaceChild);
1167         const UChar space = ' ';
1168         const Font& font = t->style()->font(); // FIXME: This ignores first-line.
1169         float spaceWidth = font.width(constructTextRun(t, font, &space, 1, t->style(), LTR));
1170         inlineMax -= spaceWidth + font.fontDescription().wordSpacing();
1171         if (inlineMin > inlineMax)
1172             inlineMin = inlineMax;
1173     }
1174 }
1175
1176 static inline void updatePreferredWidth(LayoutUnit& preferredWidth, float& result)
1177 {
1178     LayoutUnit snappedResult = LayoutUnit::fromFloatCeil(result);
1179     preferredWidth = std::max(snappedResult, preferredWidth);
1180 }
1181
1182 // When converting between floating point and LayoutUnits we risk losing precision
1183 // with each conversion. When this occurs while accumulating our preferred widths,
1184 // we can wind up with a line width that's larger than our maxPreferredWidth due to
1185 // pure float accumulation.
1186 static inline LayoutUnit adjustFloatForSubPixelLayout(float value)
1187 {
1188     return LayoutUnit::fromFloatCeil(value);
1189 }
1190
1191 // FIXME: This function should be broken into something less monolithic.
1192 // FIXME: The main loop here is very similar to LineBreaker::nextSegmentBreak. They can probably reuse code.
1193 void RenderBlockFlow::computeInlinePreferredLogicalWidths(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth)
1194 {
1195     float inlineMax = 0;
1196     float inlineMin = 0;
1197
1198     RenderStyle* styleToUse = style();
1199     RenderBlock* containingBlock = this->containingBlock();
1200     LayoutUnit cw = containingBlock ? containingBlock->contentLogicalWidth() : LayoutUnit();
1201
1202     // If we are at the start of a line, we want to ignore all white-space.
1203     // Also strip spaces if we previously had text that ended in a trailing space.
1204     bool stripFrontSpaces = true;
1205     RenderObject* trailingSpaceChild = 0;
1206
1207     // Firefox and Opera will allow a table cell to grow to fit an image inside it under
1208     // very specific cirucumstances (in order to match common WinIE renderings).
1209     // Not supporting the quirk has caused us to mis-render some real sites. (See Bugzilla 10517.)
1210     bool allowImagesToBreak = !document().inQuirksMode() || !isTableCell() || !styleToUse->logicalWidth().isIntrinsicOrAuto();
1211
1212     bool autoWrap, oldAutoWrap;
1213     autoWrap = oldAutoWrap = styleToUse->autoWrap();
1214
1215     InlineMinMaxIterator childIterator(this);
1216
1217     // Only gets added to the max preffered width once.
1218     bool addedTextIndent = false;
1219     // Signals the text indent was more negative than the min preferred width
1220     bool hasRemainingNegativeTextIndent = false;
1221
1222     LayoutUnit textIndent = minimumValueForLength(styleToUse->textIndent(), cw);
1223     RenderObject* prevFloat = 0;
1224     bool isPrevChildInlineFlow = false;
1225     bool shouldBreakLineAfterText = false;
1226     while (RenderObject* child = childIterator.next()) {
1227         autoWrap = child->isReplaced() ? child->parent()->style()->autoWrap() :
1228             child->style()->autoWrap();
1229
1230         if (!child->isBR()) {
1231             // Step One: determine whether or not we need to go ahead and
1232             // terminate our current line. Each discrete chunk can become
1233             // the new min-width, if it is the widest chunk seen so far, and
1234             // it can also become the max-width.
1235
1236             // Children fall into three categories:
1237             // (1) An inline flow object. These objects always have a min/max of 0,
1238             // and are included in the iteration solely so that their margins can
1239             // be added in.
1240             //
1241             // (2) An inline non-text non-flow object, e.g., an inline replaced element.
1242             // These objects can always be on a line by themselves, so in this situation
1243             // we need to go ahead and break the current line, and then add in our own
1244             // margins and min/max width on its own line, and then terminate the line.
1245             //
1246             // (3) A text object. Text runs can have breakable characters at the start,
1247             // the middle or the end. They may also lose whitespace off the front if
1248             // we're already ignoring whitespace. In order to compute accurate min-width
1249             // information, we need three pieces of information.
1250             // (a) the min-width of the first non-breakable run. Should be 0 if the text string
1251             // starts with whitespace.
1252             // (b) the min-width of the last non-breakable run. Should be 0 if the text string
1253             // ends with whitespace.
1254             // (c) the min/max width of the string (trimmed for whitespace).
1255             //
1256             // If the text string starts with whitespace, then we need to go ahead and
1257             // terminate our current line (unless we're already in a whitespace stripping
1258             // mode.
1259             //
1260             // If the text string has a breakable character in the middle, but didn't start
1261             // with whitespace, then we add the width of the first non-breakable run and
1262             // then end the current line. We then need to use the intermediate min/max width
1263             // values (if any of them are larger than our current min/max). We then look at
1264             // the width of the last non-breakable run and use that to start a new line
1265             // (unless we end in whitespace).
1266             RenderStyle* childStyle = child->style();
1267             float childMin = 0;
1268             float childMax = 0;
1269
1270             if (!child->isText()) {
1271                 // Case (1) and (2). Inline replaced and inline flow elements.
1272                 if (child->isRenderInline()) {
1273                     // Add in padding/border/margin from the appropriate side of
1274                     // the element.
1275                     float bpm = getBorderPaddingMargin(toRenderInline(child), childIterator.endOfInline).toFloat();
1276                     childMin += bpm;
1277                     childMax += bpm;
1278
1279                     inlineMin += childMin;
1280                     inlineMax += childMax;
1281
1282                     child->clearPreferredLogicalWidthsDirty();
1283                 } else {
1284                     // Inline replaced elts add in their margins to their min/max values.
1285                     LayoutUnit margins = 0;
1286                     Length startMargin = childStyle->marginStart();
1287                     Length endMargin = childStyle->marginEnd();
1288                     if (startMargin.isFixed())
1289                         margins += adjustFloatForSubPixelLayout(startMargin.value());
1290                     if (endMargin.isFixed())
1291                         margins += adjustFloatForSubPixelLayout(endMargin.value());
1292                     childMin += margins.ceilToFloat();
1293                     childMax += margins.ceilToFloat();
1294                 }
1295             }
1296
1297             if (!child->isRenderInline() && !child->isText()) {
1298                 // Case (2). Inline replaced elements and floats.
1299                 // Go ahead and terminate the current line as far as
1300                 // minwidth is concerned.
1301                 LayoutUnit childMinPreferredLogicalWidth, childMaxPreferredLogicalWidth;
1302                 if (child->isBox() && child->isHorizontalWritingMode() != isHorizontalWritingMode()) {
1303                     RenderBox* childBox = toRenderBox(child);
1304                     LogicalExtentComputedValues computedValues;
1305                     childBox->computeLogicalHeight(childBox->borderAndPaddingLogicalHeight(), 0, computedValues);
1306                     childMinPreferredLogicalWidth = childMaxPreferredLogicalWidth = computedValues.m_extent;
1307                 } else {
1308                     childMinPreferredLogicalWidth = child->minPreferredLogicalWidth();
1309                     childMaxPreferredLogicalWidth = child->maxPreferredLogicalWidth();
1310                 }
1311                 childMin += childMinPreferredLogicalWidth.ceilToFloat();
1312                 childMax += childMaxPreferredLogicalWidth.ceilToFloat();
1313
1314                 bool clearPreviousFloat;
1315                 if (child->isFloating()) {
1316                     clearPreviousFloat = (prevFloat
1317                         && ((prevFloat->style()->floating() == LeftFloat && (childStyle->clear() & CLEFT))
1318                             || (prevFloat->style()->floating() == RightFloat && (childStyle->clear() & CRIGHT))));
1319                     prevFloat = child;
1320                 } else {
1321                     clearPreviousFloat = false;
1322                 }
1323
1324                 bool canBreakReplacedElement = !child->isImage() || allowImagesToBreak;
1325                 if ((canBreakReplacedElement && (autoWrap || oldAutoWrap) && (!isPrevChildInlineFlow || shouldBreakLineAfterText)) || clearPreviousFloat) {
1326                     updatePreferredWidth(minLogicalWidth, inlineMin);
1327                     inlineMin = 0;
1328                 }
1329
1330                 // If we're supposed to clear the previous float, then terminate maxwidth as well.
1331                 if (clearPreviousFloat) {
1332                     updatePreferredWidth(maxLogicalWidth, inlineMax);
1333                     inlineMax = 0;
1334                 }
1335
1336                 // Add in text-indent. This is added in only once.
1337                 if (!addedTextIndent && !child->isFloating()) {
1338                     float ceiledTextIndent = textIndent.ceilToFloat();
1339                     childMin += ceiledTextIndent;
1340                     childMax += ceiledTextIndent;
1341
1342                     if (childMin < 0)
1343                         textIndent = adjustFloatForSubPixelLayout(childMin);
1344                     else
1345                         addedTextIndent = true;
1346                 }
1347
1348                 // Add our width to the max.
1349                 inlineMax += std::max<float>(0, childMax);
1350
1351                 if (!autoWrap || !canBreakReplacedElement || (isPrevChildInlineFlow && !shouldBreakLineAfterText)) {
1352                     if (child->isFloating())
1353                         updatePreferredWidth(minLogicalWidth, childMin);
1354                     else
1355                         inlineMin += childMin;
1356                 } else {
1357                     // Now check our line.
1358                     updatePreferredWidth(minLogicalWidth, childMin);
1359
1360                     // Now start a new line.
1361                     inlineMin = 0;
1362                 }
1363
1364                 if (autoWrap && canBreakReplacedElement && isPrevChildInlineFlow) {
1365                     updatePreferredWidth(minLogicalWidth, inlineMin);
1366                     inlineMin = 0;
1367                 }
1368
1369                 // We are no longer stripping whitespace at the start of
1370                 // a line.
1371                 if (!child->isFloating()) {
1372                     stripFrontSpaces = false;
1373                     trailingSpaceChild = 0;
1374                 }
1375             } else if (child->isText()) {
1376                 // Case (3). Text.
1377                 RenderText* t = toRenderText(child);
1378
1379                 if (t->isWordBreak()) {
1380                     updatePreferredWidth(minLogicalWidth, inlineMin);
1381                     inlineMin = 0;
1382                     continue;
1383                 }
1384
1385                 if (t->style()->hasTextCombine() && t->isCombineText())
1386                     toRenderCombineText(t)->combineText();
1387
1388                 // Determine if we have a breakable character. Pass in
1389                 // whether or not we should ignore any spaces at the front
1390                 // of the string. If those are going to be stripped out,
1391                 // then they shouldn't be considered in the breakable char
1392                 // check.
1393                 bool hasBreakableChar, hasBreak;
1394                 float firstLineMinWidth, lastLineMinWidth;
1395                 bool hasBreakableStart, hasBreakableEnd;
1396                 float firstLineMaxWidth, lastLineMaxWidth;
1397                 t->trimmedPrefWidths(inlineMax,
1398                     firstLineMinWidth, hasBreakableStart, lastLineMinWidth, hasBreakableEnd,
1399                     hasBreakableChar, hasBreak, firstLineMaxWidth, lastLineMaxWidth,
1400                     childMin, childMax, stripFrontSpaces, styleToUse->direction());
1401
1402                 // This text object will not be rendered, but it may still provide a breaking opportunity.
1403                 if (!hasBreak && !childMax) {
1404                     if (autoWrap && (hasBreakableStart || hasBreakableEnd)) {
1405                         updatePreferredWidth(minLogicalWidth, inlineMin);
1406                         inlineMin = 0;
1407                     }
1408                     continue;
1409                 }
1410
1411                 if (stripFrontSpaces)
1412                     trailingSpaceChild = child;
1413                 else
1414                     trailingSpaceChild = 0;
1415
1416                 // Add in text-indent. This is added in only once.
1417                 float ti = 0;
1418                 if (!addedTextIndent || hasRemainingNegativeTextIndent) {
1419                     ti = textIndent.ceilToFloat();
1420                     childMin += ti;
1421                     firstLineMinWidth += ti;
1422
1423                     // It the text indent negative and larger than the child minimum, we re-use the remainder
1424                     // in future minimum calculations, but using the negative value again on the maximum
1425                     // will lead to under-counting the max pref width.
1426                     if (!addedTextIndent) {
1427                         childMax += ti;
1428                         firstLineMaxWidth += ti;
1429                         addedTextIndent = true;
1430                     }
1431
1432                     if (childMin < 0) {
1433                         textIndent = childMin;
1434                         hasRemainingNegativeTextIndent = true;
1435                     }
1436                 }
1437
1438                 // If we have no breakable characters at all,
1439                 // then this is the easy case. We add ourselves to the current
1440                 // min and max and continue.
1441                 if (!hasBreakableChar) {
1442                     inlineMin += childMin;
1443                 } else {
1444                     if (hasBreakableStart) {
1445                         updatePreferredWidth(minLogicalWidth, inlineMin);
1446                     } else {
1447                         inlineMin += firstLineMinWidth;
1448                         updatePreferredWidth(minLogicalWidth, inlineMin);
1449                         childMin -= ti;
1450                     }
1451
1452                     inlineMin = childMin;
1453
1454                     if (hasBreakableEnd) {
1455                         updatePreferredWidth(minLogicalWidth, inlineMin);
1456                         inlineMin = 0;
1457                         shouldBreakLineAfterText = false;
1458                     } else {
1459                         updatePreferredWidth(minLogicalWidth, inlineMin);
1460                         inlineMin = lastLineMinWidth;
1461                         shouldBreakLineAfterText = true;
1462                     }
1463                 }
1464
1465                 if (hasBreak) {
1466                     inlineMax += firstLineMaxWidth;
1467                     updatePreferredWidth(maxLogicalWidth, inlineMax);
1468                     updatePreferredWidth(maxLogicalWidth, childMax);
1469                     inlineMax = lastLineMaxWidth;
1470                     addedTextIndent = true;
1471                 } else {
1472                     inlineMax += std::max<float>(0, childMax);
1473                 }
1474             }
1475
1476             // Ignore spaces after a list marker.
1477             if (child->isListMarker())
1478                 stripFrontSpaces = true;
1479         } else {
1480             updatePreferredWidth(minLogicalWidth, inlineMin);
1481             updatePreferredWidth(maxLogicalWidth, inlineMax);
1482             inlineMin = inlineMax = 0;
1483             stripFrontSpaces = true;
1484             trailingSpaceChild = 0;
1485             addedTextIndent = true;
1486         }
1487
1488         if (!child->isText() && child->isRenderInline())
1489             isPrevChildInlineFlow = true;
1490         else
1491             isPrevChildInlineFlow = false;
1492
1493         oldAutoWrap = autoWrap;
1494     }
1495
1496     if (styleToUse->collapseWhiteSpace())
1497         stripTrailingSpace(inlineMax, inlineMin, trailingSpaceChild);
1498
1499     updatePreferredWidth(minLogicalWidth, inlineMin);
1500     updatePreferredWidth(maxLogicalWidth, inlineMax);
1501 }
1502
1503 void RenderBlockFlow::layoutInlineChildren(bool relayoutChildren, LayoutUnit& paintInvalidationLogicalTop, LayoutUnit& paintInvalidationLogicalBottom, LayoutUnit afterEdge)
1504 {
1505     RenderFlowThread* flowThread = flowThreadContainingBlock();
1506     bool clearLinesForPagination = firstLineBox() && flowThread && !flowThread->hasRegions();
1507
1508     // Figure out if we should clear out our line boxes.
1509     // FIXME: Handle resize eventually!
1510     bool isFullLayout = !firstLineBox() || selfNeedsLayout() || relayoutChildren || clearLinesForPagination;
1511     LineLayoutState layoutState(isFullLayout, paintInvalidationLogicalTop, paintInvalidationLogicalBottom, flowThread);
1512
1513     if (isFullLayout) {
1514         // Ensure the old line boxes will be erased.
1515         if (firstLineBox())
1516             setShouldDoFullPaintInvalidation(true);
1517         lineBoxes()->deleteLineBoxes();
1518     }
1519
1520     // Text truncation kicks in in two cases:
1521     //     1) If your overflow isn't visible and your text-overflow-mode isn't clip.
1522     //     2) If you're an anonymous block with a block parent that satisfies #1 that was created
1523     //        to accomodate a block that has inline and block children. This excludes parents where
1524     //        canCollapseAnonymousBlockChild is false, notabley flex items and grid items.
1525     // FIXME: CSS3 says that descendants that are clipped must also know how to truncate.  This is insanely
1526     // difficult to figure out in general (especially in the middle of doing layout), so we only handle the
1527     // simple case of an anonymous block truncating when it's parent is clipped.
1528     bool hasTextOverflow = (style()->textOverflow() && hasOverflowClip())
1529         || (isAnonymousBlock() && parent() && parent()->isRenderBlock() && toRenderBlock(parent())->canCollapseAnonymousBlockChild()
1530             && parent()->style()->textOverflow() && parent()->hasOverflowClip());
1531
1532     // Walk all the lines and delete our ellipsis line boxes if they exist.
1533     if (hasTextOverflow)
1534          deleteEllipsisLineBoxes();
1535
1536     if (firstChild()) {
1537         // In full layout mode, clear the line boxes of children upfront. Otherwise,
1538         // siblings can run into stale root lineboxes during layout. Then layout
1539         // the replaced elements later. In partial layout mode, line boxes are not
1540         // deleted and only dirtied. In that case, we can layout the replaced
1541         // elements at the same time.
1542         Vector<RenderBox*> replacedChildren;
1543         for (InlineWalker walker(this); !walker.atEnd(); walker.advance()) {
1544             RenderObject* o = walker.current();
1545
1546             if (!layoutState.hasInlineChild() && o->isInline())
1547                 layoutState.setHasInlineChild(true);
1548
1549             if (o->isReplaced() || o->isFloating() || o->isOutOfFlowPositioned()) {
1550                 RenderBox* box = toRenderBox(o);
1551
1552                 updateBlockChildDirtyBitsBeforeLayout(relayoutChildren, box);
1553
1554                 if (o->isOutOfFlowPositioned())
1555                     o->containingBlock()->insertPositionedObject(box);
1556                 else if (o->isFloating())
1557                     layoutState.floats().append(FloatWithRect(box));
1558                 else if (isFullLayout || o->needsLayout()) {
1559                     // Replaced element.
1560                     box->dirtyLineBoxes(isFullLayout);
1561                     if (isFullLayout)
1562                         replacedChildren.append(box);
1563                     else
1564                         o->layoutIfNeeded();
1565                 }
1566             } else if (o->isText() || (o->isRenderInline() && !walker.atEndOfInline())) {
1567                 if (!o->isText())
1568                     toRenderInline(o)->updateAlwaysCreateLineBoxes(layoutState.isFullLayout());
1569                 if (layoutState.isFullLayout() || o->selfNeedsLayout())
1570                     dirtyLineBoxesForRenderer(o, layoutState.isFullLayout());
1571                 o->clearNeedsLayout();
1572             }
1573         }
1574
1575         for (size_t i = 0; i < replacedChildren.size(); i++)
1576             replacedChildren[i]->layoutIfNeeded();
1577
1578         layoutRunsAndFloats(layoutState);
1579     }
1580
1581     // Expand the last line to accommodate Ruby and emphasis marks.
1582     int lastLineAnnotationsAdjustment = 0;
1583     if (lastRootBox()) {
1584         LayoutUnit lowestAllowedPosition = std::max(lastRootBox()->lineBottom(), logicalHeight() + paddingAfter());
1585         if (!style()->isFlippedLinesWritingMode())
1586             lastLineAnnotationsAdjustment = lastRootBox()->computeUnderAnnotationAdjustment(lowestAllowedPosition);
1587         else
1588             lastLineAnnotationsAdjustment = lastRootBox()->computeOverAnnotationAdjustment(lowestAllowedPosition);
1589     }
1590
1591     // Now add in the bottom border/padding.
1592     setLogicalHeight(logicalHeight() + lastLineAnnotationsAdjustment + afterEdge);
1593
1594     if (!firstLineBox() && hasLineIfEmpty())
1595         setLogicalHeight(logicalHeight() + lineHeight(true, isHorizontalWritingMode() ? HorizontalLine : VerticalLine, PositionOfInteriorLineBoxes));
1596
1597     // See if we have any lines that spill out of our block.  If we do, then we will possibly need to
1598     // truncate text.
1599     if (hasTextOverflow)
1600         checkLinesForTextOverflow();
1601
1602     // Ensure the new line boxes will be painted.
1603     if (isFullLayout && firstLineBox())
1604         setShouldDoFullPaintInvalidation(true);
1605 }
1606
1607 void RenderBlockFlow::checkFloatsInCleanLine(RootInlineBox* line, Vector<FloatWithRect>& floats, size_t& floatIndex, bool& encounteredNewFloat, bool& dirtiedByFloat)
1608 {
1609     Vector<RenderBox*>* cleanLineFloats = line->floatsPtr();
1610     if (!cleanLineFloats)
1611         return;
1612
1613     Vector<RenderBox*>::iterator end = cleanLineFloats->end();
1614     for (Vector<RenderBox*>::iterator it = cleanLineFloats->begin(); it != end; ++it) {
1615         RenderBox* floatingBox = *it;
1616         floatingBox->layoutIfNeeded();
1617         LayoutSize newSize(floatingBox->width() + floatingBox->marginWidth(), floatingBox->height() + floatingBox->marginHeight());
1618         if (floats[floatIndex].object != floatingBox) {
1619             encounteredNewFloat = true;
1620             return;
1621         }
1622
1623         if (floats[floatIndex].rect.size() != newSize) {
1624             LayoutUnit floatTop = isHorizontalWritingMode() ? floats[floatIndex].rect.y() : floats[floatIndex].rect.x();
1625             LayoutUnit floatHeight = isHorizontalWritingMode() ? std::max(floats[floatIndex].rect.height(), newSize.height())
1626                 : std::max(floats[floatIndex].rect.width(), newSize.width());
1627             floatHeight = std::min(floatHeight, LayoutUnit::max() - floatTop);
1628             line->markDirty();
1629             markLinesDirtyInBlockRange(line->lineBottomWithLeading(), floatTop + floatHeight, line);
1630             floats[floatIndex].rect.setSize(newSize);
1631             dirtiedByFloat = true;
1632         }
1633         floatIndex++;
1634     }
1635 }
1636
1637 RootInlineBox* RenderBlockFlow::determineStartPosition(LineLayoutState& layoutState, InlineBidiResolver& resolver)
1638 {
1639     RootInlineBox* curr = 0;
1640     RootInlineBox* last = 0;
1641
1642     // FIXME: This entire float-checking block needs to be broken into a new function.
1643     bool dirtiedByFloat = false;
1644     if (!layoutState.isFullLayout()) {
1645         // Paginate all of the clean lines.
1646         bool paginated = view()->layoutState() && view()->layoutState()->isPaginated();
1647         LayoutUnit paginationDelta = 0;
1648         size_t floatIndex = 0;
1649         for (curr = firstRootBox(); curr && !curr->isDirty(); curr = curr->nextRootBox()) {
1650             if (paginated) {
1651                 paginationDelta -= curr->paginationStrut();
1652                 adjustLinePositionForPagination(curr, paginationDelta, layoutState.flowThread());
1653                 if (paginationDelta) {
1654                     if (containsFloats() || !layoutState.floats().isEmpty()) {
1655                         // FIXME: Do better eventually.  For now if we ever shift because of pagination and floats are present just go to a full layout.
1656                         layoutState.markForFullLayout();
1657                         break;
1658                     }
1659
1660                     layoutState.updatePaintInvalidationRangeFromBox(curr, paginationDelta);
1661                     curr->adjustBlockDirectionPosition(paginationDelta.toFloat());
1662                 }
1663             }
1664
1665             // If a new float has been inserted before this line or before its last known float, just do a full layout.
1666             bool encounteredNewFloat = false;
1667             checkFloatsInCleanLine(curr, layoutState.floats(), floatIndex, encounteredNewFloat, dirtiedByFloat);
1668             if (encounteredNewFloat)
1669                 layoutState.markForFullLayout();
1670
1671             if (dirtiedByFloat || layoutState.isFullLayout())
1672                 break;
1673         }
1674         // Check if a new float has been inserted after the last known float.
1675         if (!curr && floatIndex < layoutState.floats().size())
1676             layoutState.markForFullLayout();
1677     }
1678
1679     if (layoutState.isFullLayout()) {
1680         // If we encountered a new float and have inline children, mark ourself to force us to issue paint invalidations.
1681         if (layoutState.hasInlineChild() && !selfNeedsLayout()) {
1682             setNeedsLayoutAndFullPaintInvalidation(MarkOnlyThis);
1683             setShouldDoFullPaintInvalidation(true);
1684         }
1685
1686         // FIXME: This should just call deleteLineBoxTree, but that causes
1687         // crashes for fast/repaint tests.
1688         curr = firstRootBox();
1689         while (curr) {
1690             // Note: This uses nextRootBox() insted of nextLineBox() like deleteLineBoxTree does.
1691             RootInlineBox* next = curr->nextRootBox();
1692             curr->deleteLine();
1693             curr = next;
1694         }
1695         ASSERT(!firstLineBox() && !lastLineBox());
1696     } else {
1697         if (curr) {
1698             // We have a dirty line.
1699             if (RootInlineBox* prevRootBox = curr->prevRootBox()) {
1700                 // We have a previous line.
1701                 if (!dirtiedByFloat && (!prevRootBox->endsWithBreak() || !prevRootBox->lineBreakObj() || (prevRootBox->lineBreakObj()->isText() && prevRootBox->lineBreakPos() >= toRenderText(prevRootBox->lineBreakObj())->textLength())))
1702                     // The previous line didn't break cleanly or broke at a newline
1703                     // that has been deleted, so treat it as dirty too.
1704                     curr = prevRootBox;
1705             }
1706         } else {
1707             // No dirty lines were found.
1708             // If the last line didn't break cleanly, treat it as dirty.
1709             if (lastRootBox() && !lastRootBox()->endsWithBreak())
1710                 curr = lastRootBox();
1711         }
1712
1713         // If we have no dirty lines, then last is just the last root box.
1714         last = curr ? curr->prevRootBox() : lastRootBox();
1715     }
1716
1717     unsigned numCleanFloats = 0;
1718     if (!layoutState.floats().isEmpty()) {
1719         LayoutUnit savedLogicalHeight = logicalHeight();
1720         // Restore floats from clean lines.
1721         RootInlineBox* line = firstRootBox();
1722         while (line != curr) {
1723             if (Vector<RenderBox*>* cleanLineFloats = line->floatsPtr()) {
1724                 Vector<RenderBox*>::iterator end = cleanLineFloats->end();
1725                 for (Vector<RenderBox*>::iterator f = cleanLineFloats->begin(); f != end; ++f) {
1726                     FloatingObject* floatingObject = insertFloatingObject(*f);
1727                     ASSERT(!floatingObject->originatingLine());
1728                     floatingObject->setOriginatingLine(line);
1729                     setLogicalHeight(logicalTopForChild(*f) - marginBeforeForChild(*f));
1730                     positionNewFloats();
1731                     ASSERT(layoutState.floats()[numCleanFloats].object == *f);
1732                     numCleanFloats++;
1733                 }
1734             }
1735             line = line->nextRootBox();
1736         }
1737         setLogicalHeight(savedLogicalHeight);
1738     }
1739     layoutState.setFloatIndex(numCleanFloats);
1740
1741     layoutState.lineInfo().setFirstLine(!last);
1742     layoutState.lineInfo().setPreviousLineBrokeCleanly(!last || last->endsWithBreak());
1743
1744     if (last) {
1745         setLogicalHeight(last->lineBottomWithLeading());
1746         InlineIterator iter = InlineIterator(this, last->lineBreakObj(), last->lineBreakPos());
1747         resolver.setPosition(iter, numberOfIsolateAncestors(iter));
1748         resolver.setStatus(last->lineBreakBidiStatus());
1749     } else {
1750         TextDirection direction = style()->direction();
1751         if (style()->unicodeBidi() == Plaintext)
1752             direction = determinePlaintextDirectionality(this);
1753         resolver.setStatus(BidiStatus(direction, isOverride(style()->unicodeBidi())));
1754         InlineIterator iter = InlineIterator(this, bidiFirstSkippingEmptyInlines(this, resolver.runs(), &resolver), 0);
1755         resolver.setPosition(iter, numberOfIsolateAncestors(iter));
1756     }
1757     return curr;
1758 }
1759
1760 void RenderBlockFlow::determineEndPosition(LineLayoutState& layoutState, RootInlineBox* startLine, InlineIterator& cleanLineStart, BidiStatus& cleanLineBidiStatus)
1761 {
1762     ASSERT(!layoutState.endLine());
1763     size_t floatIndex = layoutState.floatIndex();
1764     RootInlineBox* last = 0;
1765     for (RootInlineBox* curr = startLine->nextRootBox(); curr; curr = curr->nextRootBox()) {
1766         if (!curr->isDirty()) {
1767             bool encounteredNewFloat = false;
1768             bool dirtiedByFloat = false;
1769             checkFloatsInCleanLine(curr, layoutState.floats(), floatIndex, encounteredNewFloat, dirtiedByFloat);
1770             if (encounteredNewFloat)
1771                 return;
1772         }
1773         if (curr->isDirty())
1774             last = 0;
1775         else if (!last)
1776             last = curr;
1777     }
1778
1779     if (!last)
1780         return;
1781
1782     // At this point, |last| is the first line in a run of clean lines that ends with the last line
1783     // in the block.
1784
1785     RootInlineBox* prev = last->prevRootBox();
1786     cleanLineStart = InlineIterator(this, prev->lineBreakObj(), prev->lineBreakPos());
1787     cleanLineBidiStatus = prev->lineBreakBidiStatus();
1788     layoutState.setEndLineLogicalTop(prev->lineBottomWithLeading());
1789
1790     for (RootInlineBox* line = last; line; line = line->nextRootBox())
1791         line->extractLine(); // Disconnect all line boxes from their render objects while preserving
1792                              // their connections to one another.
1793
1794     layoutState.setEndLine(last);
1795 }
1796
1797 bool RenderBlockFlow::checkPaginationAndFloatsAtEndLine(LineLayoutState& layoutState)
1798 {
1799     LayoutUnit lineDelta = logicalHeight() - layoutState.endLineLogicalTop();
1800
1801     bool paginated = view()->layoutState() && view()->layoutState()->isPaginated();
1802     if (paginated && layoutState.flowThread()) {
1803         // Check all lines from here to the end, and see if the hypothetical new position for the lines will result
1804         // in a different available line width.
1805         for (RootInlineBox* lineBox = layoutState.endLine(); lineBox; lineBox = lineBox->nextRootBox()) {
1806             if (paginated) {
1807                 // This isn't the real move we're going to do, so don't update the line box's pagination
1808                 // strut yet.
1809                 LayoutUnit oldPaginationStrut = lineBox->paginationStrut();
1810                 lineDelta -= oldPaginationStrut;
1811                 adjustLinePositionForPagination(lineBox, lineDelta, layoutState.flowThread());
1812                 lineBox->setPaginationStrut(oldPaginationStrut);
1813             }
1814         }
1815     }
1816
1817     if (!lineDelta || !m_floatingObjects)
1818         return true;
1819
1820     // See if any floats end in the range along which we want to shift the lines vertically.
1821     LayoutUnit logicalTop = std::min(logicalHeight(), layoutState.endLineLogicalTop());
1822
1823     RootInlineBox* lastLine = layoutState.endLine();
1824     while (RootInlineBox* nextLine = lastLine->nextRootBox())
1825         lastLine = nextLine;
1826
1827     LayoutUnit logicalBottom = lastLine->lineBottomWithLeading() + absoluteValue(lineDelta);
1828
1829     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1830     FloatingObjectSetIterator end = floatingObjectSet.end();
1831     for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
1832         FloatingObject* floatingObject = it->get();
1833         if (logicalBottomForFloat(floatingObject) >= logicalTop && logicalBottomForFloat(floatingObject) < logicalBottom)
1834             return false;
1835     }
1836
1837     return true;
1838 }
1839
1840 bool RenderBlockFlow::matchedEndLine(LineLayoutState& layoutState, const InlineBidiResolver& resolver, const InlineIterator& endLineStart, const BidiStatus& endLineStatus)
1841 {
1842     if (resolver.position() == endLineStart) {
1843         if (resolver.status() != endLineStatus)
1844             return false;
1845         return checkPaginationAndFloatsAtEndLine(layoutState);
1846     }
1847
1848     // The first clean line doesn't match, but we can check a handful of following lines to try
1849     // to match back up.
1850     static int numLines = 8; // The # of lines we're willing to match against.
1851     RootInlineBox* originalEndLine = layoutState.endLine();
1852     RootInlineBox* line = originalEndLine;
1853     for (int i = 0; i < numLines && line; i++, line = line->nextRootBox()) {
1854         if (line->lineBreakObj() == resolver.position().object() && line->lineBreakPos() == resolver.position().offset()) {
1855             // We have a match.
1856             if (line->lineBreakBidiStatus() != resolver.status())
1857                 return false; // ...but the bidi state doesn't match.
1858
1859             bool matched = false;
1860             RootInlineBox* result = line->nextRootBox();
1861             layoutState.setEndLine(result);
1862             if (result) {
1863                 layoutState.setEndLineLogicalTop(line->lineBottomWithLeading());
1864                 matched = checkPaginationAndFloatsAtEndLine(layoutState);
1865             }
1866
1867             // Now delete the lines that we failed to sync.
1868             deleteLineRange(layoutState, originalEndLine, result);
1869             return matched;
1870         }
1871     }
1872
1873     return false;
1874 }
1875
1876 bool RenderBlockFlow::generatesLineBoxesForInlineChild(RenderObject* inlineObj)
1877
1878 {
1879     ASSERT(inlineObj->parent() == this);
1880
1881     InlineIterator it(this, inlineObj, 0);
1882     // FIXME: We should pass correct value for WhitespacePosition.
1883     while (!it.atEnd() && !requiresLineBox(it))
1884         it.increment();
1885
1886     return !it.atEnd();
1887 }
1888
1889
1890 void RenderBlockFlow::addOverflowFromInlineChildren()
1891 {
1892     LayoutUnit endPadding = hasOverflowClip() ? paddingEnd() : LayoutUnit();
1893     // FIXME: Need to find another way to do this, since scrollbars could show when we don't want them to.
1894     if (hasOverflowClip() && !endPadding && node() && node()->isRootEditableElement() && style()->isLeftToRightDirection())
1895         endPadding = 1;
1896     for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
1897         addLayoutOverflow(curr->paddedLayoutOverflowRect(endPadding));
1898         LayoutRect visualOverflow = curr->visualOverflowRect(curr->lineTop(), curr->lineBottom());
1899         addContentsVisualOverflow(visualOverflow);
1900     }
1901 }
1902
1903 void RenderBlockFlow::deleteEllipsisLineBoxes()
1904 {
1905     ETextAlign textAlign = style()->textAlign();
1906     bool ltr = style()->isLeftToRightDirection();
1907     bool firstLine = true;
1908     for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
1909         if (curr->hasEllipsisBox()) {
1910             curr->clearTruncation();
1911
1912             // Shift the line back where it belongs if we cannot accomodate an ellipsis.
1913             float logicalLeft = logicalLeftOffsetForLine(curr->lineTop(), firstLine).toFloat();
1914             float availableLogicalWidth = logicalRightOffsetForLine(curr->lineTop(), false) - logicalLeft;
1915             float totalLogicalWidth = curr->logicalWidth();
1916             updateLogicalWidthForAlignment(textAlign, curr, 0, logicalLeft, totalLogicalWidth, availableLogicalWidth, 0);
1917
1918             if (ltr)
1919                 curr->adjustLogicalPosition((logicalLeft - curr->logicalLeft()), 0);
1920             else
1921                 curr->adjustLogicalPosition(-(curr->logicalLeft() - logicalLeft), 0);
1922         }
1923         firstLine = false;
1924     }
1925 }
1926
1927 void RenderBlockFlow::checkLinesForTextOverflow()
1928 {
1929     // Determine the width of the ellipsis using the current font.
1930     // FIXME: CSS3 says this is configurable, also need to use 0x002E (FULL STOP) if horizontal ellipsis is "not renderable"
1931     const Font& font = style()->font();
1932     DEFINE_STATIC_LOCAL(AtomicString, ellipsisStr, (&horizontalEllipsis, 1));
1933     const Font& firstLineFont = firstLineStyle()->font();
1934     // FIXME: We should probably not hard-code the direction here. https://crbug.com/333004
1935     TextDirection ellipsisDirection = LTR;
1936     float firstLineEllipsisWidth = firstLineFont.width(constructTextRun(this, firstLineFont, &horizontalEllipsis, 1, firstLineStyle(), ellipsisDirection));
1937     float ellipsisWidth = (font == firstLineFont) ? firstLineEllipsisWidth : font.width(constructTextRun(this, font, &horizontalEllipsis, 1, style(), ellipsisDirection));
1938
1939     // For LTR text truncation, we want to get the right edge of our padding box, and then we want to see
1940     // if the right edge of a line box exceeds that.  For RTL, we use the left edge of the padding box and
1941     // check the left edge of the line box to see if it is less
1942     // Include the scrollbar for overflow blocks, which means we want to use "contentWidth()"
1943     bool ltr = style()->isLeftToRightDirection();
1944     ETextAlign textAlign = style()->textAlign();
1945     bool firstLine = true;
1946     for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
1947         float currLogicalLeft = curr->logicalLeft();
1948         LayoutUnit blockRightEdge = logicalRightOffsetForLine(curr->lineTop(), firstLine);
1949         LayoutUnit blockLeftEdge = logicalLeftOffsetForLine(curr->lineTop(), firstLine);
1950         LayoutUnit lineBoxEdge = ltr ? currLogicalLeft + curr->logicalWidth() : currLogicalLeft;
1951         if ((ltr && lineBoxEdge > blockRightEdge) || (!ltr && lineBoxEdge < blockLeftEdge)) {
1952             // This line spills out of our box in the appropriate direction.  Now we need to see if the line
1953             // can be truncated.  In order for truncation to be possible, the line must have sufficient space to
1954             // accommodate our truncation string, and no replaced elements (images, tables) can overlap the ellipsis
1955             // space.
1956
1957             LayoutUnit width = firstLine ? firstLineEllipsisWidth : ellipsisWidth;
1958             LayoutUnit blockEdge = ltr ? blockRightEdge : blockLeftEdge;
1959             if (curr->lineCanAccommodateEllipsis(ltr, blockEdge, lineBoxEdge, width)) {
1960                 float totalLogicalWidth = curr->placeEllipsis(ellipsisStr, ltr, blockLeftEdge.toFloat(), blockRightEdge.toFloat(), width.toFloat());
1961
1962                 float logicalLeft = 0; // We are only intersted in the delta from the base position.
1963                 float availableLogicalWidth = (blockRightEdge - blockLeftEdge).toFloat();
1964                 updateLogicalWidthForAlignment(textAlign, curr, 0, logicalLeft, totalLogicalWidth, availableLogicalWidth, 0);
1965                 if (ltr)
1966                     curr->adjustLogicalPosition(logicalLeft, 0);
1967                 else
1968                     curr->adjustLogicalPosition(logicalLeft - (availableLogicalWidth - totalLogicalWidth), 0);
1969             }
1970         }
1971         firstLine = false;
1972     }
1973 }
1974
1975 bool RenderBlockFlow::positionNewFloatOnLine(FloatingObject* newFloat, FloatingObject* lastFloatFromPreviousLine, LineInfo& lineInfo, LineWidth& width)
1976 {
1977     if (!positionNewFloats())
1978         return false;
1979
1980     width.shrinkAvailableWidthForNewFloatIfNeeded(newFloat);
1981
1982     // We only connect floats to lines for pagination purposes if the floats occur at the start of
1983     // the line and the previous line had a hard break (so this line is either the first in the block
1984     // or follows a <br>).
1985     if (!newFloat->paginationStrut() || !lineInfo.previousLineBrokeCleanly() || !lineInfo.isEmpty())
1986         return true;
1987
1988     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1989     ASSERT(floatingObjectSet.last() == newFloat);
1990
1991     LayoutUnit floatLogicalTop = logicalTopForFloat(newFloat);
1992     int paginationStrut = newFloat->paginationStrut();
1993
1994     if (floatLogicalTop - paginationStrut != logicalHeight() + lineInfo.floatPaginationStrut())
1995         return true;
1996
1997     FloatingObjectSetIterator it = floatingObjectSet.end();
1998     --it; // Last float is newFloat, skip that one.
1999     FloatingObjectSetIterator begin = floatingObjectSet.begin();
2000     while (it != begin) {
2001         --it;
2002         FloatingObject* floatingObject = it->get();
2003         if (floatingObject == lastFloatFromPreviousLine)
2004             break;
2005         if (logicalTopForFloat(floatingObject) == logicalHeight() + lineInfo.floatPaginationStrut()) {
2006             floatingObject->setPaginationStrut(paginationStrut + floatingObject->paginationStrut());
2007             RenderBox* floatBox = floatingObject->renderer();
2008             setLogicalTopForChild(floatBox, logicalTopForChild(floatBox) + marginBeforeForChild(floatBox) + paginationStrut);
2009             if (floatBox->isRenderBlock())
2010                 floatBox->forceChildLayout();
2011             else
2012                 floatBox->layoutIfNeeded();
2013             // Save the old logical top before calling removePlacedObject which will set
2014             // isPlaced to false. Otherwise it will trigger an assert in logicalTopForFloat.
2015             LayoutUnit oldLogicalTop = logicalTopForFloat(floatingObject);
2016             m_floatingObjects->removePlacedObject(floatingObject);
2017             setLogicalTopForFloat(floatingObject, oldLogicalTop + paginationStrut);
2018             m_floatingObjects->addPlacedObject(floatingObject);
2019         }
2020     }
2021
2022     // Just update the line info's pagination strut without altering our logical height yet. If the line ends up containing
2023     // no content, then we don't want to improperly grow the height of the block.
2024     lineInfo.setFloatPaginationStrut(lineInfo.floatPaginationStrut() + paginationStrut);
2025     return true;
2026 }
2027
2028 LayoutUnit RenderBlockFlow::startAlignedOffsetForLine(LayoutUnit position, bool firstLine)
2029 {
2030     ETextAlign textAlign = style()->textAlign();
2031
2032     if (textAlign == TASTART) // FIXME: Handle TAEND here
2033         return startOffsetForLine(position, firstLine);
2034
2035     // updateLogicalWidthForAlignment() handles the direction of the block so no need to consider it here
2036     float totalLogicalWidth = 0;
2037     float logicalLeft = logicalLeftOffsetForLine(logicalHeight(), false).toFloat();
2038     float availableLogicalWidth = logicalRightOffsetForLine(logicalHeight(), false) - logicalLeft;
2039     updateLogicalWidthForAlignment(textAlign, 0, 0, logicalLeft, totalLogicalWidth, availableLogicalWidth, 0);
2040
2041     if (!style()->isLeftToRightDirection())
2042         return logicalWidth() - logicalLeft;
2043     return logicalLeft;
2044 }
2045
2046 }