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
36namespace blink {
37
38RenderMultiColumnSet::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
47RenderMultiColumnSet* 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
56RenderMultiColumnSet* 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
65RenderMultiColumnSet* 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
74LayoutSize 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
84LayoutUnit 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
102LayoutUnit RenderMultiColumnSet::pageLogicalTopForOffset(LayoutUnit offset) const
103{
104    unsigned columnIndex = columnIndexAtOffset(offset, AssumeNewColumns);
105    return logicalTopInFlowThread() + columnIndex * pageLogicalHeight();
106}
107
108void 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
116unsigned 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
135void 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
161LayoutUnit 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
195void 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
207bool RenderMultiColumnSet::recalculateColumnHeight(BalancedHeightCalculation calculationMode)
208{
209    ASSERT(multiColumnFlowThread()->heightIsAuto());
210
211    LayoutUnit oldColumnHeight = m_columnHeight;
212    if (calculationMode == GuessFromFlowThreadPortion) {
213        // Post-process the content runs and find out where the implicit breaks will occur.
214        distributeImplicitBreaks();
215    }
216    LayoutUnit newColumnHeight = calculateColumnHeight(calculationMode);
217    setAndConstrainColumnHeight(newColumnHeight);
218
219    // After having calculated an initial column height, the multicol container typically needs at
220    // least one more layout pass with a new column height, but if a height was specified, we only
221    // need to do this if we think that we need less space than specified. Conversely, if we
222    // determined that the columns need to be as tall as the specified height of the container, we
223    // have already laid it out correctly, and there's no need for another pass.
224
225    // We can get rid of the content runs now, if we haven't already done so. They are only needed
226    // to calculate the initial balanced column height. In fact, we have to get rid of them before
227    // the next layout pass, since each pass will rebuild this.
228    m_contentRuns.clear();
229
230    if (m_columnHeight == oldColumnHeight)
231        return false; // No change. We're done.
232
233    m_minSpaceShortage = RenderFlowThread::maxLogicalHeight();
234    return true; // Need another pass.
235}
236
237void RenderMultiColumnSet::recordSpaceShortage(LayoutUnit spaceShortage)
238{
239    if (spaceShortage >= m_minSpaceShortage)
240        return;
241
242    // The space shortage is what we use as our stretch amount. We need a positive number here in
243    // order to get anywhere.
244    ASSERT(spaceShortage > 0);
245
246    m_minSpaceShortage = spaceShortage;
247}
248
249void RenderMultiColumnSet::resetColumnHeight()
250{
251    // Nuke previously stored minimum column height. Contents may have changed for all we know.
252    m_minimumColumnHeight = 0;
253
254    m_maxColumnHeight = calculateMaxColumnHeight();
255
256    LayoutUnit oldColumnHeight = pageLogicalHeight();
257
258    if (multiColumnFlowThread()->heightIsAuto())
259        m_columnHeight = 0;
260    else
261        setAndConstrainColumnHeight(heightAdjustedForSetOffset(multiColumnFlowThread()->columnHeightAvailable()));
262
263    if (pageLogicalHeight() != oldColumnHeight)
264        setChildNeedsLayout(MarkOnlyThis);
265
266    // Content runs are only needed in the initial layout pass, in order to find an initial column
267    // height, and should have been deleted afterwards. We're about to rebuild the content runs, so
268    // the list needs to be empty.
269    ASSERT(m_contentRuns.isEmpty());
270}
271
272void RenderMultiColumnSet::expandToEncompassFlowThreadContentsIfNeeded()
273{
274    ASSERT(multiColumnFlowThread()->lastMultiColumnSet() == this);
275    LayoutRect rect(flowThreadPortionRect());
276
277    // Get the offset within the flow thread in its block progression direction. Then get the
278    // flow thread's remaining logical height including its overflow and expand our rect
279    // to encompass that remaining height and overflow. The idea is that we will generate
280    // additional columns and pages to hold that overflow, since people do write bad
281    // content like <body style="height:0px"> in multi-column layouts.
282    bool isHorizontal = flowThread()->isHorizontalWritingMode();
283    LayoutUnit logicalTopOffset = isHorizontal ? rect.y() : rect.x();
284    LayoutRect layoutRect = flowThread()->layoutOverflowRect();
285    LayoutUnit logicalHeightWithOverflow = (isHorizontal ? layoutRect.maxY() : layoutRect.maxX()) - logicalTopOffset;
286    setFlowThreadPortionRect(LayoutRect(rect.x(), rect.y(), isHorizontal ? rect.width() : logicalHeightWithOverflow, isHorizontal ? logicalHeightWithOverflow : rect.height()));
287}
288
289void RenderMultiColumnSet::computeLogicalHeight(LayoutUnit, LayoutUnit logicalTop, LogicalExtentComputedValues& computedValues) const
290{
291    computedValues.m_extent = m_columnHeight;
292    computedValues.m_position = logicalTop;
293}
294
295LayoutUnit RenderMultiColumnSet::calculateMaxColumnHeight() const
296{
297    RenderBlockFlow* multicolBlock = multiColumnBlockFlow();
298    RenderStyle* multicolStyle = multicolBlock->style();
299    LayoutUnit availableHeight = multiColumnFlowThread()->columnHeightAvailable();
300    LayoutUnit maxColumnHeight = availableHeight ? availableHeight : RenderFlowThread::maxLogicalHeight();
301    if (!multicolStyle->logicalMaxHeight().isMaxSizeNone()) {
302        LayoutUnit logicalMaxHeight = multicolBlock->computeContentLogicalHeight(multicolStyle->logicalMaxHeight(), -1);
303        if (logicalMaxHeight != -1 && maxColumnHeight > logicalMaxHeight)
304            maxColumnHeight = logicalMaxHeight;
305    }
306    return heightAdjustedForSetOffset(maxColumnHeight);
307}
308
309LayoutUnit RenderMultiColumnSet::columnGap() const
310{
311    RenderBlockFlow* parentBlock = multiColumnBlockFlow();
312    if (parentBlock->style()->hasNormalColumnGap())
313        return parentBlock->style()->fontDescription().computedPixelSize(); // "1em" is recommended as the normal gap setting. Matches <p> margins.
314    return parentBlock->style()->columnGap();
315}
316
317unsigned RenderMultiColumnSet::actualColumnCount() const
318{
319    // We must always return a value of 1 or greater. Column count = 0 is a meaningless situation,
320    // and will confuse and cause problems in other parts of the code.
321    if (!pageLogicalHeight())
322        return 1;
323
324    // Our portion rect determines our column count. We have as many columns as needed to fit all the content.
325    LayoutUnit logicalHeightInColumns = flowThread()->isHorizontalWritingMode() ? flowThreadPortionRect().height() : flowThreadPortionRect().width();
326    if (!logicalHeightInColumns)
327        return 1;
328
329    unsigned count = ceil(logicalHeightInColumns.toFloat() / pageLogicalHeight().toFloat());
330    ASSERT(count >= 1);
331    return count;
332}
333
334LayoutRect RenderMultiColumnSet::columnRectAt(unsigned index) const
335{
336    LayoutUnit colLogicalWidth = pageLogicalWidth();
337    LayoutUnit colLogicalHeight = pageLogicalHeight();
338    LayoutUnit colLogicalTop = borderBefore() + paddingBefore();
339    LayoutUnit colLogicalLeft = borderAndPaddingLogicalLeft();
340    LayoutUnit colGap = columnGap();
341
342    if (multiColumnFlowThread()->progressionIsInline()) {
343        if (style()->isLeftToRightDirection())
344            colLogicalLeft += index * (colLogicalWidth + colGap);
345        else
346            colLogicalLeft += contentLogicalWidth() - colLogicalWidth - index * (colLogicalWidth + colGap);
347    } else {
348        colLogicalTop += index * (colLogicalHeight + colGap);
349    }
350
351    if (isHorizontalWritingMode())
352        return LayoutRect(colLogicalLeft, colLogicalTop, colLogicalWidth, colLogicalHeight);
353    return LayoutRect(colLogicalTop, colLogicalLeft, colLogicalHeight, colLogicalWidth);
354}
355
356unsigned RenderMultiColumnSet::columnIndexAtOffset(LayoutUnit offset, ColumnIndexCalculationMode mode) const
357{
358    LayoutRect portionRect(flowThreadPortionRect());
359
360    // Handle the offset being out of range.
361    LayoutUnit flowThreadLogicalTop = isHorizontalWritingMode() ? portionRect.y() : portionRect.x();
362    if (offset < flowThreadLogicalTop)
363        return 0;
364    // If we're laying out right now, we cannot constrain against some logical bottom, since it
365    // isn't known yet. Otherwise, just return the last column if we're past the logical bottom.
366    if (mode == ClampToExistingColumns) {
367        LayoutUnit flowThreadLogicalBottom = isHorizontalWritingMode() ? portionRect.maxY() : portionRect.maxX();
368        if (offset >= flowThreadLogicalBottom)
369            return actualColumnCount() - 1;
370    }
371
372    // Just divide by the column height to determine the correct column.
373    return (offset - flowThreadLogicalTop).toFloat() / pageLogicalHeight().toFloat();
374}
375
376LayoutRect RenderMultiColumnSet::flowThreadPortionRectAt(unsigned index) const
377{
378    LayoutRect portionRect = flowThreadPortionRect();
379    if (isHorizontalWritingMode())
380        portionRect = LayoutRect(portionRect.x(), portionRect.y() + index * pageLogicalHeight(), portionRect.width(), pageLogicalHeight());
381    else
382        portionRect = LayoutRect(portionRect.x() + index * pageLogicalHeight(), portionRect.y(), pageLogicalHeight(), portionRect.height());
383    return portionRect;
384}
385
386LayoutRect RenderMultiColumnSet::flowThreadPortionOverflowRect(const LayoutRect& portionRect, unsigned index, unsigned colCount, LayoutUnit colGap) const
387{
388    // This function determines the portion of the flow thread that paints for the column. Along the inline axis, columns are
389    // unclipped at outside edges (i.e., the first and last column in the set), and they clip to half the column
390    // gap along interior edges.
391    //
392    // In the block direction, we will not clip overflow out of the top of the first column, or out of the bottom of
393    // the last column. This applies only to the true first column and last column across all column sets.
394    //
395    // FIXME: Eventually we will know overflow on a per-column basis, but we can't do this until we have a painting
396    // mode that understands not to paint contents from a previous column in the overflow area of a following column.
397    // This problem applies to regions and pages as well and is not unique to columns.
398    bool isFirstColumn = !index;
399    bool isLastColumn = index == colCount - 1;
400    bool isLeftmostColumn = style()->isLeftToRightDirection() ? isFirstColumn : isLastColumn;
401    bool isRightmostColumn = style()->isLeftToRightDirection() ? isLastColumn : isFirstColumn;
402
403    // Calculate the overflow rectangle, based on the flow thread's, clipped at column logical
404    // top/bottom unless it's the first/last column.
405    LayoutRect overflowRect = overflowRectForFlowThreadPortion(portionRect, isFirstColumn && isFirstRegion(), isLastColumn && isLastRegion());
406
407    // Avoid overflowing into neighboring columns, by clipping in the middle of adjacent column
408    // gaps. Also make sure that we avoid rounding errors.
409    if (isHorizontalWritingMode()) {
410        if (!isLeftmostColumn)
411            overflowRect.shiftXEdgeTo(portionRect.x() - colGap / 2);
412        if (!isRightmostColumn)
413            overflowRect.shiftMaxXEdgeTo(portionRect.maxX() + colGap - colGap / 2);
414    } else {
415        if (!isLeftmostColumn)
416            overflowRect.shiftYEdgeTo(portionRect.y() - colGap / 2);
417        if (!isRightmostColumn)
418            overflowRect.shiftMaxYEdgeTo(portionRect.maxY() + colGap - colGap / 2);
419    }
420    return overflowRect;
421}
422
423void RenderMultiColumnSet::paintObject(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
424{
425    MultiColumnSetPainter(*this).paintObject(paintInfo, paintOffset);
426}
427
428void RenderMultiColumnSet::paintInvalidationForFlowThreadContent(const LayoutRect& paintInvalidationRect) const
429{
430    // Figure out the start and end columns and only check within that range so that we don't walk the
431    // entire column set. Put the paint invalidation rect into flow thread coordinates by flipping it first.
432    LayoutRect flowThreadPaintInvalidationRect(paintInvalidationRect);
433    flowThread()->flipForWritingMode(flowThreadPaintInvalidationRect);
434
435    // Now we can compare this rect with the flow thread portions owned by each column. First let's
436    // just see if the paint invalidation rect intersects our flow thread portion at all.
437    LayoutRect clippedRect(flowThreadPaintInvalidationRect);
438    clippedRect.intersect(RenderRegion::flowThreadPortionOverflowRect());
439    if (clippedRect.isEmpty())
440        return;
441
442    // Now we know we intersect at least one column. Let's figure out the logical top and logical
443    // bottom of the area in which we're issuing paint invalidations.
444    LayoutUnit paintInvalidationLogicalTop = isHorizontalWritingMode() ? flowThreadPaintInvalidationRect.y() : flowThreadPaintInvalidationRect.x();
445    LayoutUnit paintInvalidationLogicalBottom = (isHorizontalWritingMode() ? flowThreadPaintInvalidationRect.maxY() : flowThreadPaintInvalidationRect.maxX()) - 1;
446
447    unsigned startColumn = columnIndexAtOffset(paintInvalidationLogicalTop);
448    unsigned endColumn = columnIndexAtOffset(paintInvalidationLogicalBottom);
449
450    LayoutUnit colGap = columnGap();
451    unsigned colCount = actualColumnCount();
452    for (unsigned i = startColumn; i <= endColumn; i++) {
453        LayoutRect colRect = columnRectAt(i);
454
455        // Get the portion of the flow thread that corresponds to this column.
456        LayoutRect flowThreadPortion = flowThreadPortionRectAt(i);
457
458        // Now get the overflow rect that corresponds to the column.
459        LayoutRect flowThreadOverflowPortion = flowThreadPortionOverflowRect(flowThreadPortion, i, colCount, colGap);
460
461        // Do a paint invalidation for this specific column.
462        paintInvalidationOfFlowThreadContentRectangle(paintInvalidationRect, flowThreadPortion, flowThreadOverflowPortion, colRect.location());
463    }
464}
465
466void RenderMultiColumnSet::collectLayerFragments(LayerFragments& fragments, const LayoutRect& layerBoundingBox, const LayoutRect& dirtyRect)
467{
468    // The two rectangles passed to this method are physical, except that we pretend that there's
469    // only one long column (that's how a flow thread works).
470    //
471    // Then there's the output from this method - the stuff we put into the list of fragments. The
472    // fragment.paginationOffset point is the actual physical translation required to get from a
473    // location in the flow thread to a location in a given column. The fragment.paginationClip
474    // rectangle, on the other hand, is in the same coordinate system as the two rectangles passed
475    // to this method (flow thread coordinates).
476    //
477    // All other rectangles in this method are sized physically, and the inline direction coordinate
478    // is physical too, but the block direction coordinate is "logical top". This is the same as
479    // e.g. RenderBox::frameRect(). These rectangles also pretend that there's only one long column,
480    // i.e. they are for the flow thread.
481
482    // Put the layer bounds into flow thread-local coordinates by flipping it first. Since we're in
483    // a renderer, most rectangles are represented this way.
484    LayoutRect layerBoundsInFlowThread(layerBoundingBox);
485    flowThread()->flipForWritingMode(layerBoundsInFlowThread);
486
487    // Now we can compare with the flow thread portions owned by each column. First let's
488    // see if the rect intersects our flow thread portion at all.
489    LayoutRect clippedRect(layerBoundsInFlowThread);
490    clippedRect.intersect(RenderRegion::flowThreadPortionOverflowRect());
491    if (clippedRect.isEmpty())
492        return;
493
494    // Now we know we intersect at least one column. Let's figure out the logical top and logical
495    // bottom of the area we're checking.
496    LayoutUnit layerLogicalTop = isHorizontalWritingMode() ? layerBoundsInFlowThread.y() : layerBoundsInFlowThread.x();
497    LayoutUnit layerLogicalBottom = (isHorizontalWritingMode() ? layerBoundsInFlowThread.maxY() : layerBoundsInFlowThread.maxX()) - 1;
498
499    // Figure out the start and end columns and only check within that range so that we don't walk the
500    // entire column set.
501    unsigned startColumn = columnIndexAtOffset(layerLogicalTop);
502    unsigned endColumn = columnIndexAtOffset(layerLogicalBottom);
503
504    LayoutUnit colLogicalWidth = pageLogicalWidth();
505    LayoutUnit colGap = columnGap();
506    unsigned colCount = actualColumnCount();
507
508    RenderMultiColumnFlowThread* flowThread = multiColumnFlowThread();
509    bool progressionIsInline = flowThread->progressionIsInline();
510    bool leftToRight = style()->isLeftToRightDirection();
511
512    LayoutUnit initialBlockOffset = logicalTop() - flowThread->logicalTop();
513
514    for (unsigned i = startColumn; i <= endColumn; i++) {
515        // Get the portion of the flow thread that corresponds to this column.
516        LayoutRect flowThreadPortion = flowThreadPortionRectAt(i);
517
518        // Now get the overflow rect that corresponds to the column.
519        LayoutRect flowThreadOverflowPortion = flowThreadPortionOverflowRect(flowThreadPortion, i, colCount, colGap);
520
521        // In order to create a fragment we must intersect the portion painted by this column.
522        LayoutRect clippedRect(layerBoundsInFlowThread);
523        clippedRect.intersect(flowThreadOverflowPortion);
524        if (clippedRect.isEmpty())
525            continue;
526
527        // We also need to intersect the dirty rect. We have to apply a translation and shift based off
528        // our column index.
529        LayoutPoint translationOffset;
530        LayoutUnit inlineOffset = progressionIsInline ? i * (colLogicalWidth + colGap) : LayoutUnit();
531        if (!leftToRight)
532            inlineOffset = -inlineOffset;
533        translationOffset.setX(inlineOffset);
534        LayoutUnit blockOffset;
535        if (progressionIsInline) {
536            blockOffset = initialBlockOffset + (isHorizontalWritingMode() ? -flowThreadPortion.y() : -flowThreadPortion.x());
537        } else {
538            // Column gap can apply in the block direction for page fragmentainers.
539            // There is currently no spec which calls for column-gap to apply
540            // for page fragmentainers at all, but it's applied here for compatibility
541            // with the old multicolumn implementation.
542            blockOffset = i * colGap;
543        }
544        if (isFlippedBlocksWritingMode(style()->writingMode()))
545            blockOffset = -blockOffset;
546        translationOffset.setY(blockOffset);
547        if (!isHorizontalWritingMode())
548            translationOffset = translationOffset.transposedPoint();
549        // FIXME: The translation needs to include the multicolumn set's content offset within the
550        // multicolumn block as well. This won't be an issue until we start creating multiple multicolumn sets.
551
552        // Shift the dirty rect to be in flow thread coordinates with this translation applied.
553        LayoutRect translatedDirtyRect(dirtyRect);
554        translatedDirtyRect.moveBy(-translationOffset);
555
556        // See if we intersect the dirty rect.
557        clippedRect = layerBoundingBox;
558        clippedRect.intersect(translatedDirtyRect);
559        if (clippedRect.isEmpty())
560            continue;
561
562        // Something does need to paint in this column. Make a fragment now and supply the physical translation
563        // offset and the clip rect for the column with that offset applied.
564        LayerFragment fragment;
565        fragment.paginationOffset = translationOffset;
566
567        LayoutRect flippedFlowThreadOverflowPortion(flowThreadOverflowPortion);
568        // Flip it into more a physical (RenderLayer-style) rectangle.
569        flowThread->flipForWritingMode(flippedFlowThreadOverflowPortion);
570        fragment.paginationClip = flippedFlowThreadOverflowPortion;
571        fragments.append(fragment);
572    }
573}
574
575void RenderMultiColumnSet::addOverflowFromChildren()
576{
577    unsigned colCount = actualColumnCount();
578    if (!colCount)
579        return;
580
581    LayoutRect lastRect = columnRectAt(colCount - 1);
582    addLayoutOverflow(lastRect);
583    if (!hasOverflowClip())
584        addVisualOverflow(lastRect);
585}
586
587const char* RenderMultiColumnSet::renderName() const
588{
589    return "RenderMultiColumnSet";
590}
591
592void RenderMultiColumnSet::insertedIntoTree()
593{
594    RenderRegion::insertedIntoTree();
595
596    attachRegion();
597}
598
599void RenderMultiColumnSet::willBeRemovedFromTree()
600{
601    RenderRegion::willBeRemovedFromTree();
602
603    detachRegion();
604}
605
606void RenderMultiColumnSet::attachRegion()
607{
608    if (documentBeingDestroyed())
609        return;
610
611    // A region starts off invalid.
612    setIsValid(false);
613
614    if (!m_flowThread)
615        return;
616
617    // Only after adding the region to the thread, the region is marked to be valid.
618    m_flowThread->addRegionToThread(this);
619}
620
621void RenderMultiColumnSet::detachRegion()
622{
623    if (m_flowThread) {
624        m_flowThread->removeRegionFromThread(this);
625        m_flowThread = 0;
626    }
627}
628
629}
630