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

   1 /*
   2  * Copyright (C) 2012 Apple Inc.  All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "core/rendering/RenderMultiColumnSet.h"
  28
  29 #include "core/paint/BoxPainter.h"
  30 #include "core/paint/MultiColumnSetPainter.h"
  31 #include "core/paint/ObjectPainter.h"
  32 #include "core/rendering/PaintInfo.h"
  33 #include "core/rendering/RenderLayer.h"
  34 #include "core/rendering/RenderMultiColumnFlowThread.h"
  35
  36 namespace blink {
  37
  38 RenderMultiColumnSet::RenderMultiColumnSet(RenderFlowThread* flowThread)
  39     : RenderRegion(0, flowThread)
  40     , m_columnHeight(0)
  41     , m_maxColumnHeight(RenderFlowThread::maxLogicalHeight())
  42     , m_minSpaceShortage(RenderFlowThread::maxLogicalHeight())
  43     , m_minimumColumnHeight(0)
  44 {
  45 }
  46
  47 RenderMultiColumnSet* RenderMultiColumnSet::createAnonymous(RenderFlowThread* flowThread, RenderStyle* parentStyle)
  48 {
  49     Document& document = flowThread->document();
  50     RenderMultiColumnSet* renderer = new RenderMultiColumnSet(flowThread);
  51     renderer->setDocumentForAnonymous(&document);
  52     renderer->setStyle(RenderStyle::createAnonymousStyleWithDisplay(parentStyle, BLOCK));
  53     return renderer;
  54 }
  55
  56 RenderMultiColumnSet* RenderMultiColumnSet::nextSiblingMultiColumnSet() const
  57 {
  58     for (RenderObject* sibling = nextSibling(); sibling; sibling = sibling->nextSibling()) {
  59         if (sibling->isRenderMultiColumnSet())
  60             return toRenderMultiColumnSet(sibling);
  61     }
  62     return 0;
  63 }
  64
  65 RenderMultiColumnSet* RenderMultiColumnSet::previousSiblingMultiColumnSet() const
  66 {
  67     for (RenderObject* sibling = previousSibling(); sibling; sibling = sibling->previousSibling()) {
  68         if (sibling->isRenderMultiColumnSet())
  69             return toRenderMultiColumnSet(sibling);
  70     }
  71     return 0;
  72 }
  73
  74 LayoutSize RenderMultiColumnSet::flowThreadTranslationAtOffset(LayoutUnit blockOffset) const
  75 {
  76     unsigned columnIndex = columnIndexAtOffset(blockOffset);
  77     LayoutRect portionRect(flowThreadPortionRectAt(columnIndex));
  78     flipForWritingMode(portionRect);
  79     LayoutRect columnRect(columnRectAt(columnIndex));
  80     flipForWritingMode(columnRect);
  81     return contentBoxRect().location() + columnRect.location() - portionRect.location();
  82 }
  83
  84 LayoutUnit RenderMultiColumnSet::heightAdjustedForSetOffset(LayoutUnit height) const
  85 {
  86     // Adjust for the top offset within the content box of the multicol container (containing
  87     // block), unless this is the first set. We know that the top offset for the first set will be
  88     // zero, but if the multicol container has non-zero top border or padding, the set's top offset
  89     // (initially being 0 and relative to the border box) will be negative until it has been laid
  90     // out. Had we used this bogus offset, we would calculate the wrong height, and risk performing
  91     // a wasted layout iteration. Of course all other sets (if any) have this problem in the first
  92     // layout pass too, but there's really nothing we can do there until the flow thread has been
  93     // laid out anyway.
  94     if (previousSiblingMultiColumnSet()) {
  95         RenderBlockFlow* multicolBlock = multiColumnBlockFlow();
  96         LayoutUnit contentLogicalTop = logicalTop() - multicolBlock->borderAndPaddingBefore();
  97         height -= contentLogicalTop;
  98     }
  99     return max(height, LayoutUnit(1)); // Let's avoid zero height, as that would probably cause an infinite amount of columns to be created.
 100 }
 101
 102 LayoutUnit RenderMultiColumnSet::pageLogicalTopForOffset(LayoutUnit offset) const
 103 {
 104     unsigned columnIndex = columnIndexAtOffset(offset, AssumeNewColumns);
 105     return logicalTopInFlowThread() + columnIndex * pageLogicalHeight();
 106 }
 107
 108 void RenderMultiColumnSet::setAndConstrainColumnHeight(LayoutUnit newHeight)
 109 {
 110     m_columnHeight = newHeight;
 111     if (m_columnHeight > m_maxColumnHeight)
 112         m_columnHeight = m_maxColumnHeight;
 113     // FIXME: the height may also be affected by the enclosing pagination context, if any.
 114 }
 115
 116 unsigned RenderMultiColumnSet::findRunWithTallestColumns() const
 117 {
 118     unsigned indexWithLargestHeight = 0;
 119     LayoutUnit largestHeight;
 120     LayoutUnit previousOffset = logicalTopInFlowThread();
 121     size_t runCount = m_contentRuns.size();
 122     ASSERT(runCount);
 123     for (size_t i = 0; i < runCount; i++) {
 124         const ContentRun& run = m_contentRuns[i];
 125         LayoutUnit height = run.columnLogicalHeight(previousOffset);
 126         if (largestHeight < height) {
 127             largestHeight = height;
 128             indexWithLargestHeight = i;
 129         }
 130         previousOffset = run.breakOffset();
 131     }
 132     return indexWithLargestHeight;
 133 }
 134
 135 void RenderMultiColumnSet::distributeImplicitBreaks()
 136 {
 137 #if ENABLE(ASSERT)
 138     // There should be no implicit breaks assumed at this point.
 139     for (unsigned i = 0; i < m_contentRuns.size(); i++)
 140         ASSERT(!m_contentRuns[i].assumedImplicitBreaks());
 141 #endif // ENABLE(ASSERT)
 142
 143     // Insert a final content run to encompass all content. This will include overflow if this is
 144     // the last set.
 145     addContentRun(logicalBottomInFlowThread());
 146     unsigned columnCount = m_contentRuns.size();
 147
 148     // If there is room for more breaks (to reach the used value of column-count), imagine that we
 149     // insert implicit breaks at suitable locations. At any given time, the content run with the
 150     // currently tallest columns will get another implicit break "inserted", which will increase its
 151     // column count by one and shrink its columns' height. Repeat until we have the desired total
 152     // number of breaks. The largest column height among the runs will then be the initial column
 153     // height for the balancer to use.
 154     while (columnCount < usedColumnCount()) {
 155         unsigned index = findRunWithTallestColumns();
 156         m_contentRuns[index].assumeAnotherImplicitBreak();
 157         columnCount++;
 158     }
 159 }
 160
 161 LayoutUnit RenderMultiColumnSet::calculateColumnHeight(BalancedHeightCalculation calculationMode) const
 162 {
 163     if (calculationMode == GuessFromFlowThreadPortion) {
 164         // Initial balancing. Start with the lowest imaginable column height. We use the tallest
 165         // content run (after having "inserted" implicit breaks), and find its start offset (by
 166         // looking at the previous run's end offset, or, if there's no previous run, the set's start
 167         // offset in the flow thread).
 168         unsigned index = findRunWithTallestColumns();
 169         LayoutUnit startOffset = index > 0 ? m_contentRuns[index - 1].breakOffset() : logicalTopInFlowThread();
 170         return std::max<LayoutUnit>(m_contentRuns[index].columnLogicalHeight(startOffset), m_minimumColumnHeight);
 171     }
 172
 173     if (actualColumnCount() <= usedColumnCount()) {
 174         // With the current column height, the content fits without creating overflowing columns. We're done.
 175         return m_columnHeight;
 176     }
 177
 178     if (m_contentRuns.size() >= usedColumnCount()) {
 179         // Too many forced breaks to allow any implicit breaks. Initial balancing should already
 180         // have set a good height. There's nothing more we should do.
 181         return m_columnHeight;
 182     }
 183
 184     // If the initial guessed column height wasn't enough, stretch it now. Stretch by the lowest
 185     // amount of space shortage found during layout.
 186
 187     ASSERT(m_minSpaceShortage > 0); // We should never _shrink_ the height!
 188     ASSERT(m_minSpaceShortage != RenderFlowThread::maxLogicalHeight()); // If this happens, we probably have a bug.
 189     if (m_minSpaceShortage == RenderFlowThread::maxLogicalHeight())
 190         return m_columnHeight; // So bail out rather than looping infinitely.
 191
 192     return m_columnHeight + m_minSpaceShortage;
 193 }
 194
 195 void RenderMultiColumnSet::addContentRun(LayoutUnit endOffsetFromFirstPage)
 196 {
 197     if (!multiColumnFlowThread()->heightIsAuto())
 198         return;
 199     if (!m_contentRuns.isEmpty() && endOffsetFromFirstPage <= m_contentRuns.last().breakOffset())
 200         return;
 201     // Append another item as long as we haven't exceeded used column count. What ends up in the
 202     // overflow area shouldn't affect column balancing.
 203     if (m_contentRuns.size() < usedColumnCount())
 204         m_contentRuns.append(ContentRun(endOffsetFromFirstPage));
 205 }
 206
 207 bool RenderMultiColumnSet::recalculateColumnHeight(BalancedHeightCalculation calculationMode)
 208 {
 209     if (previousSiblingMultiColumnSet()) {
 210         // FIXME: column spanner layout is not yet implemented. Until it's in place, we only operate
 211         // on the first set during layout. We need to ignore the others here, or assertions will
 212         // fail.
 213         return false;
 214     }
 215     ASSERT(multiColumnFlowThread()->heightIsAuto());
 216
 217     LayoutUnit oldColumnHeight = m_columnHeight;
 218     if (calculationMode == GuessFromFlowThreadPortion) {
 219         // Post-process the content runs and find out where the implicit breaks will occur.
 220         distributeImplicitBreaks();
 221     }
 222     LayoutUnit newColumnHeight = calculateColumnHeight(calculationMode);
 223     setAndConstrainColumnHeight(newColumnHeight);
 224
 225     // After having calculated an initial column height, the multicol container typically needs at
 226     // least one more layout pass with a new column height, but if a height was specified, we only
 227     // need to do this if we think that we need less space than specified. Conversely, if we
 228     // determined that the columns need to be as tall as the specified height of the container, we
 229     // have already laid it out correctly, and there's no need for another pass.
 230
 231     // We can get rid of the content runs now, if we haven't already done so. They are only needed
 232     // to calculate the initial balanced column height. In fact, we have to get rid of them before
 233     // the next layout pass, since each pass will rebuild this.
 234     m_contentRuns.clear();
 235
 236     if (m_columnHeight == oldColumnHeight)
 237         return false; // No change. We're done.
 238
 239     m_minSpaceShortage = RenderFlowThread::maxLogicalHeight();
 240     return true; // Need another pass.
 241 }
 242
 243 void RenderMultiColumnSet::recordSpaceShortage(LayoutUnit spaceShortage)
 244 {
 245     if (spaceShortage >= m_minSpaceShortage)
 246         return;
 247
 248     // The space shortage is what we use as our stretch amount. We need a positive number here in
 249     // order to get anywhere.
 250     ASSERT(spaceShortage > 0);
 251
 252     m_minSpaceShortage = spaceShortage;
 253 }
 254
 255 void RenderMultiColumnSet::resetColumnHeight()
 256 {
 257     // Nuke previously stored minimum column height. Contents may have changed for all we know.
 258     m_minimumColumnHeight = 0;
 259
 260     m_maxColumnHeight = calculateMaxColumnHeight();
 261
 262     LayoutUnit oldColumnHeight = pageLogicalHeight();
 263
 264     if (multiColumnFlowThread()->heightIsAuto())
 265         m_columnHeight = 0;
 266     else
 267         setAndConstrainColumnHeight(heightAdjustedForSetOffset(multiColumnFlowThread()->columnHeightAvailable()));
 268
 269     if (pageLogicalHeight() != oldColumnHeight)
 270         setChildNeedsLayout(MarkOnlyThis);
 271
 272     // Content runs are only needed in the initial layout pass, in order to find an initial column
 273     // height, and should have been deleted afterwards. We're about to rebuild the content runs, so
 274     // the list needs to be empty.
 275     ASSERT(m_contentRuns.isEmpty());
 276 }
 277
 278 void RenderMultiColumnSet::expandToEncompassFlowThreadContentsIfNeeded()
 279 {
 280     ASSERT(multiColumnFlowThread()->lastMultiColumnSet() == this);
 281     LayoutRect rect(flowThreadPortionRect());
 282
 283     // Get the offset within the flow thread in its block progression direction. Then get the
 284     // flow thread's remaining logical height including its overflow and expand our rect
 285     // to encompass that remaining height and overflow. The idea is that we will generate
 286     // additional columns and pages to hold that overflow, since people do write bad
 287     // content like <body style="height:0px"> in multi-column layouts.
 288     bool isHorizontal = flowThread()->isHorizontalWritingMode();
 289     LayoutUnit logicalTopOffset = isHorizontal ? rect.y() : rect.x();
 290     LayoutRect layoutRect = flowThread()->layoutOverflowRect();
 291     LayoutUnit logicalHeightWithOverflow = (isHorizontal ? layoutRect.maxY() : layoutRect.maxX()) - logicalTopOffset;
 292     setFlowThreadPortionRect(LayoutRect(rect.x(), rect.y(), isHorizontal ? rect.width() : logicalHeightWithOverflow, isHorizontal ? logicalHeightWithOverflow : rect.height()));
 293 }
 294
 295 void RenderMultiColumnSet::computeLogicalHeight(LayoutUnit, LayoutUnit logicalTop, LogicalExtentComputedValues& computedValues) const
 296 {
 297     computedValues.m_extent = m_columnHeight;
 298     computedValues.m_position = logicalTop;
 299 }
 300
 301 LayoutUnit RenderMultiColumnSet::calculateMaxColumnHeight() const
 302 {
 303     RenderBlockFlow* multicolBlock = multiColumnBlockFlow();
 304     RenderStyle* multicolStyle = multicolBlock->style();
 305     LayoutUnit availableHeight = multiColumnFlowThread()->columnHeightAvailable();
 306     LayoutUnit maxColumnHeight = availableHeight ? availableHeight : RenderFlowThread::maxLogicalHeight();
 307     if (!multicolStyle->logicalMaxHeight().isMaxSizeNone()) {
 308         LayoutUnit logicalMaxHeight = multicolBlock->computeContentLogicalHeight(multicolStyle->logicalMaxHeight(), -1);
 309         if (logicalMaxHeight != -1 && maxColumnHeight > logicalMaxHeight)
 310             maxColumnHeight = logicalMaxHeight;
 311     }
 312     return heightAdjustedForSetOffset(maxColumnHeight);
 313 }
 314
 315 LayoutUnit RenderMultiColumnSet::columnGap() const
 316 {
 317     RenderBlockFlow* parentBlock = multiColumnBlockFlow();
 318     if (parentBlock->style()->hasNormalColumnGap())
 319         return parentBlock->style()->fontDescription().computedPixelSize(); // "1em" is recommended as the normal gap setting. Matches <p> margins.
 320     return parentBlock->style()->columnGap();
 321 }
 322
 323 unsigned RenderMultiColumnSet::actualColumnCount() const
 324 {
 325     // We must always return a value of 1 or greater. Column count = 0 is a meaningless situation,
 326     // and will confuse and cause problems in other parts of the code.
 327     if (!pageLogicalHeight())
 328         return 1;
 329
 330     // Our portion rect determines our column count. We have as many columns as needed to fit all the content.
 331     LayoutUnit logicalHeightInColumns = flowThread()->isHorizontalWritingMode() ? flowThreadPortionRect().height() : flowThreadPortionRect().width();
 332     if (!logicalHeightInColumns)
 333         return 1;
 334
 335     unsigned count = ceil(logicalHeightInColumns.toFloat() / pageLogicalHeight().toFloat());
 336     ASSERT(count >= 1);
 337     return count;
 338 }
 339
 340 LayoutRect RenderMultiColumnSet::columnRectAt(unsigned index) const
 341 {
 342     LayoutUnit colLogicalWidth = pageLogicalWidth();
 343     LayoutUnit colLogicalHeight = pageLogicalHeight();
 344     LayoutUnit colLogicalTop = borderBefore() + paddingBefore();
 345     LayoutUnit colLogicalLeft = borderAndPaddingLogicalLeft();
 346     LayoutUnit colGap = columnGap();
 347
 348     if (multiColumnFlowThread()->progressionIsInline()) {
 349         if (style()->isLeftToRightDirection())
 350             colLogicalLeft += index * (colLogicalWidth + colGap);
 351         else
 352             colLogicalLeft += contentLogicalWidth() - colLogicalWidth - index * (colLogicalWidth + colGap);
 353     } else {
 354         colLogicalTop += index * (colLogicalHeight + colGap);
 355     }
 356
 357     if (isHorizontalWritingMode())
 358         return LayoutRect(colLogicalLeft, colLogicalTop, colLogicalWidth, colLogicalHeight);
 359     return LayoutRect(colLogicalTop, colLogicalLeft, colLogicalHeight, colLogicalWidth);
 360 }
 361
 362 unsigned RenderMultiColumnSet::columnIndexAtOffset(LayoutUnit offset, ColumnIndexCalculationMode mode) const
 363 {
 364     LayoutRect portionRect(flowThreadPortionRect());
 365
 366     // Handle the offset being out of range.
 367     LayoutUnit flowThreadLogicalTop = isHorizontalWritingMode() ? portionRect.y() : portionRect.x();
 368     if (offset < flowThreadLogicalTop)
 369         return 0;
 370     // If we're laying out right now, we cannot constrain against some logical bottom, since it
 371     // isn't known yet. Otherwise, just return the last column if we're past the logical bottom.
 372     if (mode == ClampToExistingColumns) {
 373         LayoutUnit flowThreadLogicalBottom = isHorizontalWritingMode() ? portionRect.maxY() : portionRect.maxX();
 374         if (offset >= flowThreadLogicalBottom)
 375             return actualColumnCount() - 1;
 376     }
 377
 378     // Just divide by the column height to determine the correct column.
 379     return (offset - flowThreadLogicalTop).toFloat() / pageLogicalHeight().toFloat();
 380 }
 381
 382 LayoutRect RenderMultiColumnSet::flowThreadPortionRectAt(unsigned index) const
 383 {
 384     LayoutRect portionRect = flowThreadPortionRect();
 385     if (isHorizontalWritingMode())
 386         portionRect = LayoutRect(portionRect.x(), portionRect.y() + index * pageLogicalHeight(), portionRect.width(), pageLogicalHeight());
 387     else
 388         portionRect = LayoutRect(portionRect.x() + index * pageLogicalHeight(), portionRect.y(), pageLogicalHeight(), portionRect.height());
 389     return portionRect;
 390 }
 391
 392 LayoutRect RenderMultiColumnSet::flowThreadPortionOverflowRect(const LayoutRect& portionRect, unsigned index, unsigned colCount, LayoutUnit colGap) const
 393 {
 394     // This function determines the portion of the flow thread that paints for the column. Along the inline axis, columns are
 395     // unclipped at outside edges (i.e., the first and last column in the set), and they clip to half the column
 396     // gap along interior edges.
 397     //
 398     // In the block direction, we will not clip overflow out of the top of the first column, or out of the bottom of
 399     // the last column. This applies only to the true first column and last column across all column sets.
 400     //
 401     // FIXME: Eventually we will know overflow on a per-column basis, but we can't do this until we have a painting
 402     // mode that understands not to paint contents from a previous column in the overflow area of a following column.
 403     // This problem applies to regions and pages as well and is not unique to columns.
 404     bool isFirstColumn = !index;
 405     bool isLastColumn = index == colCount - 1;
 406     bool isLeftmostColumn = style()->isLeftToRightDirection() ? isFirstColumn : isLastColumn;
 407     bool isRightmostColumn = style()->isLeftToRightDirection() ? isLastColumn : isFirstColumn;
 408
 409     // Calculate the overflow rectangle, based on the flow thread's, clipped at column logical
 410     // top/bottom unless it's the first/last column.
 411     LayoutRect overflowRect = overflowRectForFlowThreadPortion(portionRect, isFirstColumn && isFirstRegion(), isLastColumn && isLastRegion());
 412
 413     // Avoid overflowing into neighboring columns, by clipping in the middle of adjacent column
 414     // gaps. Also make sure that we avoid rounding errors.
 415     if (isHorizontalWritingMode()) {
 416         if (!isLeftmostColumn)
 417             overflowRect.shiftXEdgeTo(portionRect.x() - colGap / 2);
 418         if (!isRightmostColumn)
 419             overflowRect.shiftMaxXEdgeTo(portionRect.maxX() + colGap - colGap / 2);
 420     } else {
 421         if (!isLeftmostColumn)
 422             overflowRect.shiftYEdgeTo(portionRect.y() - colGap / 2);
 423         if (!isRightmostColumn)
 424             overflowRect.shiftMaxYEdgeTo(portionRect.maxY() + colGap - colGap / 2);
 425     }
 426     return overflowRect;
 427 }
 428
 429 void RenderMultiColumnSet::paintObject(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
 430 {
 431     MultiColumnSetPainter(*this).paintObject(paintInfo, paintOffset);
 432 }
 433
 434 void RenderMultiColumnSet::paintInvalidationForFlowThreadContent(const LayoutRect& paintInvalidationRect) const
 435 {
 436     // Figure out the start and end columns and only check within that range so that we don't walk the
 437     // entire column set. Put the paint invalidation rect into flow thread coordinates by flipping it first.
 438     LayoutRect flowThreadPaintInvalidationRect(paintInvalidationRect);
 439     flowThread()->flipForWritingMode(flowThreadPaintInvalidationRect);
 440
 441     // Now we can compare this rect with the flow thread portions owned by each column. First let's
 442     // just see if the paint invalidation rect intersects our flow thread portion at all.
 443     LayoutRect clippedRect(flowThreadPaintInvalidationRect);
 444     clippedRect.intersect(RenderRegion::flowThreadPortionOverflowRect());
 445     if (clippedRect.isEmpty())
 446         return;
 447
 448     // Now we know we intersect at least one column. Let's figure out the logical top and logical
 449     // bottom of the area in which we're issuing paint invalidations.
 450     LayoutUnit paintInvalidationLogicalTop = isHorizontalWritingMode() ? flowThreadPaintInvalidationRect.y() : flowThreadPaintInvalidationRect.x();
 451     LayoutUnit paintInvalidationLogicalBottom = (isHorizontalWritingMode() ? flowThreadPaintInvalidationRect.maxY() : flowThreadPaintInvalidationRect.maxX()) - 1;
 452
 453     unsigned startColumn = columnIndexAtOffset(paintInvalidationLogicalTop);
 454     unsigned endColumn = columnIndexAtOffset(paintInvalidationLogicalBottom);
 455
 456     LayoutUnit colGap = columnGap();
 457     unsigned colCount = actualColumnCount();
 458     for (unsigned i = startColumn; i <= endColumn; i++) {
 459         LayoutRect colRect = columnRectAt(i);
 460
 461         // Get the portion of the flow thread that corresponds to this column.
 462         LayoutRect flowThreadPortion = flowThreadPortionRectAt(i);
 463
 464         // Now get the overflow rect that corresponds to the column.
 465         LayoutRect flowThreadOverflowPortion = flowThreadPortionOverflowRect(flowThreadPortion, i, colCount, colGap);
 466
 467         // Do a paint invalidation for this specific column.
 468         paintInvalidationOfFlowThreadContentRectangle(paintInvalidationRect, flowThreadPortion, flowThreadOverflowPortion, colRect.location());
 469     }
 470 }
 471
 472 void RenderMultiColumnSet::collectLayerFragments(LayerFragments& fragments, const LayoutRect& layerBoundingBox, const LayoutRect& dirtyRect)
 473 {
 474     // |layerBoundingBox| is in the flow thread coordinate space, relative to the top/left edge of
 475     // the flow thread, but note that it has been converted with respect to writing mode (so that
 476     // it's visual/physical in that sense).
 477     //
 478     // |dirtyRect| is visual, relative to the multicol container.
 479     //
 480     // Then there's the output from this method - the stuff we put into the list of fragments. The
 481     // fragment.paginationOffset point is the actual visual translation required to get from a
 482     // location in the flow thread to a location in a given column. The fragment.paginationClip
 483     // rectangle, on the other hand, is in flow thread coordinates.
 484     //
 485     // All other rectangles in this method are sized physically, and the inline direction coordinate
 486     // is physical too, but the block direction coordinate is "logical top". This is the same as
 487     // e.g. RenderBox::frameRect(). These rectangles also pretend that there's only one long column,
 488     // i.e. they are for the flow thread.
 489
 490     // Put the layer bounds into flow thread-local coordinates by flipping it first. Since we're in
 491     // a renderer, most rectangles are represented this way.
 492     LayoutRect layerBoundsInFlowThread(layerBoundingBox);
 493     flowThread()->flipForWritingMode(layerBoundsInFlowThread);
 494
 495     // Now we can compare with the flow thread portions owned by each column. First let's
 496     // see if the rect intersects our flow thread portion at all.
 497     LayoutRect clippedRect(layerBoundsInFlowThread);
 498     clippedRect.intersect(RenderRegion::flowThreadPortionOverflowRect());
 499     if (clippedRect.isEmpty())
 500         return;
 501
 502     // Now we know we intersect at least one column. Let's figure out the logical top and logical
 503     // bottom of the area we're checking.
 504     LayoutUnit layerLogicalTop = isHorizontalWritingMode() ? layerBoundsInFlowThread.y() : layerBoundsInFlowThread.x();
 505     LayoutUnit layerLogicalBottom = (isHorizontalWritingMode() ? layerBoundsInFlowThread.maxY() : layerBoundsInFlowThread.maxX()) - 1;
 506
 507     // Figure out the start and end columns and only check within that range so that we don't walk the
 508     // entire column set.
 509     unsigned startColumn = columnIndexAtOffset(layerLogicalTop);
 510     unsigned endColumn = columnIndexAtOffset(layerLogicalBottom);
 511
 512     LayoutUnit colLogicalWidth = pageLogicalWidth();
 513     LayoutUnit colGap = columnGap();
 514     unsigned colCount = actualColumnCount();
 515
 516     RenderMultiColumnFlowThread* flowThread = multiColumnFlowThread();
 517     bool progressionIsInline = flowThread->progressionIsInline();
 518     bool leftToRight = style()->isLeftToRightDirection();
 519
 520     LayoutUnit initialBlockOffset = logicalTop() - flowThread->logicalTop();
 521
 522     for (unsigned i = startColumn; i <= endColumn; i++) {
 523         // Get the portion of the flow thread that corresponds to this column.
 524         LayoutRect flowThreadPortion = flowThreadPortionRectAt(i);
 525
 526         // Now get the overflow rect that corresponds to the column.
 527         LayoutRect flowThreadOverflowPortion = flowThreadPortionOverflowRect(flowThreadPortion, i, colCount, colGap);
 528
 529         // In order to create a fragment we must intersect the portion painted by this column.
 530         LayoutRect clippedRect(layerBoundsInFlowThread);
 531         clippedRect.intersect(flowThreadOverflowPortion);
 532         if (clippedRect.isEmpty())
 533             continue;
 534
 535         // We also need to intersect the dirty rect. We have to apply a translation and shift based off
 536         // our column index.
 537         LayoutPoint translationOffset;
 538         LayoutUnit inlineOffset = progressionIsInline ? i * (colLogicalWidth + colGap) : LayoutUnit();
 539         if (!leftToRight)
 540             inlineOffset = -inlineOffset;
 541         translationOffset.setX(inlineOffset);
 542         LayoutUnit blockOffset;
 543         if (progressionIsInline) {
 544             blockOffset = initialBlockOffset + (isHorizontalWritingMode() ? -flowThreadPortion.y() : -flowThreadPortion.x());
 545         } else {
 546             // Column gap can apply in the block direction for page fragmentainers.
 547             // There is currently no spec which calls for column-gap to apply
 548             // for page fragmentainers at all, but it's applied here for compatibility
 549             // with the old multicolumn implementation.
 550             blockOffset = i * colGap;
 551         }
 552         if (isFlippedBlocksWritingMode(style()->writingMode()))
 553             blockOffset = -blockOffset;
 554         translationOffset.setY(blockOffset);
 555         if (!isHorizontalWritingMode())
 556             translationOffset = translationOffset.transposedPoint();
 557         // FIXME: The translation needs to include the multicolumn set's content offset within the
 558         // multicolumn block as well. This won't be an issue until we start creating multiple multicolumn sets.
 559
 560         // Shift the dirty rect to be in flow thread coordinates with this translation applied.
 561         LayoutRect translatedDirtyRect(dirtyRect);
 562         translatedDirtyRect.moveBy(-translationOffset);
 563
 564         // See if we intersect the dirty rect.
 565         clippedRect = layerBoundingBox;
 566         clippedRect.intersect(translatedDirtyRect);
 567         if (clippedRect.isEmpty())
 568             continue;
 569
 570         // Something does need to paint in this column. Make a fragment now and supply the physical translation
 571         // offset and the clip rect for the column with that offset applied.
 572         LayerFragment fragment;
 573         fragment.paginationOffset = translationOffset;
 574
 575         LayoutRect flippedFlowThreadOverflowPortion(flowThreadOverflowPortion);
 576         // Flip it into more a physical (RenderLayer-style) rectangle.
 577         flowThread->flipForWritingMode(flippedFlowThreadOverflowPortion);
 578         fragment.paginationClip = flippedFlowThreadOverflowPortion;
 579         fragments.append(fragment);
 580     }
 581 }
 582
 583 void RenderMultiColumnSet::addOverflowFromChildren()
 584 {
 585     unsigned colCount = actualColumnCount();
 586     if (!colCount)
 587         return;
 588
 589     LayoutRect lastRect = columnRectAt(colCount - 1);
 590     addLayoutOverflow(lastRect);
 591     if (!hasOverflowClip())
 592         addVisualOverflow(lastRect);
 593 }
 594
 595 const char* RenderMultiColumnSet::renderName() const
 596 {
 597     return "RenderMultiColumnSet";
 598 }
 599
 600 void RenderMultiColumnSet::insertedIntoTree()
 601 {
 602     RenderRegion::insertedIntoTree();
 603
 604     attachRegion();
 605 }
 606
 607 void RenderMultiColumnSet::willBeRemovedFromTree()
 608 {
 609     RenderRegion::willBeRemovedFromTree();
 610
 611     detachRegion();
 612 }
 613
 614 void RenderMultiColumnSet::attachRegion()
 615 {
 616     if (documentBeingDestroyed())
 617         return;
 618
 619     // A region starts off invalid.
 620     setIsValid(false);
 621
 622     if (!m_flowThread)
 623         return;
 624
 625     // Only after adding the region to the thread, the region is marked to be valid.
 626     m_flowThread->addRegionToThread(this);
 627 }
 628
 629 void RenderMultiColumnSet::detachRegion()
 630 {
 631     if (m_flowThread) {
 632         m_flowThread->removeRegionFromThread(this);
 633         m_flowThread = 0;
 634     }
 635 }
 636
 637 }