Unreviewed, rolling out r167478.
[WebKit-https.git] / Source / WebCore / 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 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 "RenderMultiColumnSet.h"
28
29 #include "PaintInfo.h"
30 #include "RenderLayer.h"
31 #include "RenderMultiColumnFlowThread.h"
32 #include "RenderMultiColumnSpannerPlaceholder.h"
33
34 namespace WebCore {
35
36 RenderMultiColumnSet::RenderMultiColumnSet(RenderFlowThread& flowThread, PassRef<RenderStyle> style)
37     : RenderRegionSet(flowThread.document(), std::move(style), flowThread)
38     , m_computedColumnCount(1)
39     , m_computedColumnWidth(0)
40     , m_computedColumnHeight(0)
41     , m_maxColumnHeight(RenderFlowThread::maxLogicalHeight())
42     , m_minSpaceShortage(RenderFlowThread::maxLogicalHeight())
43     , m_minimumColumnHeight(0)
44 {
45 }
46
47 RenderMultiColumnSet* RenderMultiColumnSet::nextSiblingMultiColumnSet() const
48 {
49     for (RenderObject* sibling = nextSibling(); sibling; sibling = sibling->nextSibling()) {
50         if (sibling->isRenderMultiColumnSet())
51             return toRenderMultiColumnSet(sibling);
52     }
53     return nullptr;
54 }
55
56 RenderMultiColumnSet* RenderMultiColumnSet::previousSiblingMultiColumnSet() const
57 {
58     for (RenderObject* sibling = previousSibling(); sibling; sibling = sibling->previousSibling()) {
59         if (sibling->isRenderMultiColumnSet())
60             return toRenderMultiColumnSet(sibling);
61     }
62     return nullptr;
63 }
64
65 RenderObject* RenderMultiColumnSet::firstRendererInFlowThread() const
66 {
67     if (RenderBox* sibling = RenderMultiColumnFlowThread::previousColumnSetOrSpannerSiblingOf(this)) {
68         // Adjacent sets should not occur. Currently we would have no way of figuring out what each
69         // of them contains then.
70         ASSERT(!sibling->isRenderMultiColumnSet());
71         RenderMultiColumnSpannerPlaceholder* placeholder = multiColumnFlowThread()->findColumnSpannerPlaceholder(sibling);
72         return placeholder->nextInPreOrderAfterChildren();
73     }
74     return flowThread()->firstChild();
75 }
76
77 RenderObject* RenderMultiColumnSet::lastRendererInFlowThread() const
78 {
79     if (RenderBox* sibling = RenderMultiColumnFlowThread::nextColumnSetOrSpannerSiblingOf(this)) {
80         // Adjacent sets should not occur. Currently we would have no way of figuring out what each
81         // of them contains then.
82         ASSERT(!sibling->isRenderMultiColumnSet());
83         RenderMultiColumnSpannerPlaceholder* placeholder = multiColumnFlowThread()->findColumnSpannerPlaceholder(sibling);
84         return placeholder->previousInPreOrder();
85     }
86     return flowThread()->lastLeafChild();
87 }
88
89 static bool precedesRenderer(RenderObject* renderer, RenderObject* boundary)
90 {
91     for (; renderer; renderer = renderer->nextInPreOrder()) {
92         if (renderer == boundary)
93             return true;
94     }
95     return false;
96 }
97
98 bool RenderMultiColumnSet::containsRendererInFlowThread(RenderObject* renderer) const
99 {
100     if (!previousSiblingMultiColumnSet() && !nextSiblingMultiColumnSet()) {
101         // There is only one set. This is easy, then.
102         return renderer->isDescendantOf(m_flowThread);
103     }
104
105     RenderObject* firstRenderer = firstRendererInFlowThread();
106     RenderObject* lastRenderer = lastRendererInFlowThread();
107     ASSERT(firstRenderer);
108     ASSERT(lastRenderer);
109
110     // This is SLOW! But luckily very uncommon.
111     return precedesRenderer(firstRenderer, renderer) && precedesRenderer(renderer, lastRenderer);
112 }
113
114 void RenderMultiColumnSet::setLogicalTopInFlowThread(LayoutUnit logicalTop)
115 {
116     LayoutRect rect = flowThreadPortionRect();
117     if (isHorizontalWritingMode())
118         rect.setY(logicalTop);
119     else
120         rect.setX(logicalTop);
121     setFlowThreadPortionRect(rect);
122 }
123
124 void RenderMultiColumnSet::setLogicalBottomInFlowThread(LayoutUnit logicalBottom)
125 {
126     LayoutRect rect = flowThreadPortionRect();
127     if (isHorizontalWritingMode())
128         rect.shiftMaxYEdgeTo(logicalBottom);
129     else
130         rect.shiftMaxXEdgeTo(logicalBottom);
131     setFlowThreadPortionRect(rect);
132 }
133
134 LayoutUnit RenderMultiColumnSet::heightAdjustedForSetOffset(LayoutUnit height) const
135 {
136     RenderBlockFlow* multicolBlock = toRenderBlockFlow(parent());
137     LayoutUnit contentLogicalTop = logicalTop() - multicolBlock->borderAndPaddingBefore();
138
139     height -= contentLogicalTop;
140     return std::max(height, LayoutUnit::fromPixel(1)); // Let's avoid zero height, as that would probably cause an infinite amount of columns to be created.
141 }
142
143 LayoutUnit RenderMultiColumnSet::pageLogicalTopForOffset(LayoutUnit offset) const
144 {
145     unsigned columnIndex = columnIndexAtOffset(offset, AssumeNewColumns);
146     return logicalTopInFlowThread() + columnIndex * computedColumnHeight();
147 }
148
149 void RenderMultiColumnSet::setAndConstrainColumnHeight(LayoutUnit newHeight)
150 {
151     m_computedColumnHeight = newHeight;
152     if (m_computedColumnHeight > m_maxColumnHeight)
153         m_computedColumnHeight = m_maxColumnHeight;
154     // FIXME: the height may also be affected by the enclosing pagination context, if any.
155 }
156
157 unsigned RenderMultiColumnSet::findRunWithTallestColumns() const
158 {
159     unsigned indexWithLargestHeight = 0;
160     LayoutUnit largestHeight;
161     LayoutUnit previousOffset;
162     size_t runCount = m_contentRuns.size();
163     ASSERT(runCount);
164     for (size_t i = 0; i < runCount; i++) {
165         const ContentRun& run = m_contentRuns[i];
166         LayoutUnit height = run.columnLogicalHeight(previousOffset);
167         if (largestHeight < height) {
168             largestHeight = height;
169             indexWithLargestHeight = i;
170         }
171         previousOffset = run.breakOffset();
172     }
173     return indexWithLargestHeight;
174 }
175
176 void RenderMultiColumnSet::distributeImplicitBreaks()
177 {
178     unsigned breakCount = forcedBreaksCount();
179
180 #ifndef NDEBUG
181     // There should be no implicit breaks assumed at this point.
182     for (unsigned i = 0; i < breakCount; i++)
183         ASSERT(!m_contentRuns[i].assumedImplicitBreaks());
184 #endif // NDEBUG
185
186     if (!breakCount) {
187         // The flow thread would normally insert a forced break at end of content, but if this set
188         // isn't last in the multicol container, we have to do it ourselves.
189         addForcedBreak(logicalBottomInFlowThread());
190         breakCount = 1;
191     }
192
193     // If there is room for more breaks (to reach the used value of column-count), imagine that we
194     // insert implicit breaks at suitable locations. At any given time, the content run with the
195     // currently tallest columns will get another implicit break "inserted", which will increase its
196     // column count by one and shrink its columns' height. Repeat until we have the desired total
197     // number of breaks. The largest column height among the runs will then be the initial column
198     // height for the balancer to use.
199     while (breakCount < m_computedColumnCount) {
200         unsigned index = findRunWithTallestColumns();
201         m_contentRuns[index].assumeAnotherImplicitBreak();
202         breakCount++;
203     }
204 }
205
206 LayoutUnit RenderMultiColumnSet::calculateBalancedHeight(bool initial) const
207 {
208     if (initial) {
209         // Start with the lowest imaginable column height.
210         unsigned index = findRunWithTallestColumns();
211         LayoutUnit startOffset = index > 0 ? m_contentRuns[index - 1].breakOffset() : logicalTopInFlowThread();
212         return std::max<LayoutUnit>(m_contentRuns[index].columnLogicalHeight(startOffset), m_minimumColumnHeight);
213     }
214
215     if (columnCount() <= computedColumnCount()) {
216         // With the current column height, the content fits without creating overflowing columns. We're done.
217         return m_computedColumnHeight;
218     }
219
220     if (forcedBreaksCount() > 1 && forcedBreaksCount() >= computedColumnCount()) {
221         // Too many forced breaks to allow any implicit breaks. Initial balancing should already
222         // have set a good height. There's nothing more we should do.
223         return m_computedColumnHeight;
224     }
225
226     // If the initial guessed column height wasn't enough, stretch it now. Stretch by the lowest
227     // amount of space shortage found during layout.
228
229     ASSERT(m_minSpaceShortage > 0); // We should never _shrink_ the height!
230     ASSERT(m_minSpaceShortage != RenderFlowThread::maxLogicalHeight()); // If this happens, we probably have a bug.
231     if (m_minSpaceShortage == RenderFlowThread::maxLogicalHeight())
232         return m_computedColumnHeight; // So bail out rather than looping infinitely.
233
234     return m_computedColumnHeight + m_minSpaceShortage;
235 }
236
237 void RenderMultiColumnSet::clearForcedBreaks()
238 {
239     m_contentRuns.clear();
240 }
241
242 void RenderMultiColumnSet::addForcedBreak(LayoutUnit offsetFromFirstPage)
243 {
244     if (!requiresBalancing())
245         return;
246     if (!m_contentRuns.isEmpty() && offsetFromFirstPage <= m_contentRuns.last().breakOffset())
247         return;
248     // Append another item as long as we haven't exceeded used column count. What ends up in the
249     // overflow area shouldn't affect column balancing.
250     if (m_contentRuns.size() < m_computedColumnCount)
251         m_contentRuns.append(ContentRun(offsetFromFirstPage));
252 }
253
254 bool RenderMultiColumnSet::recalculateColumnHeight(bool initial)
255 {
256     LayoutUnit oldColumnHeight = m_computedColumnHeight;
257     if (requiresBalancing()) {
258         if (initial)
259             distributeImplicitBreaks();
260         LayoutUnit newColumnHeight = calculateBalancedHeight(initial);
261         setAndConstrainColumnHeight(newColumnHeight);
262         // After having calculated an initial column height, the multicol container typically needs at
263         // least one more layout pass with a new column height, but if a height was specified, we only
264         // need to do this if we think that we need less space than specified. Conversely, if we
265         // determined that the columns need to be as tall as the specified height of the container, we
266         // have already laid it out correctly, and there's no need for another pass.
267     } else {
268         // The position of the column set may have changed, in which case height available for
269         // columns may have changed as well.
270         setAndConstrainColumnHeight(m_computedColumnHeight);
271     }
272     if (m_computedColumnHeight == oldColumnHeight)
273         return false; // No change. We're done.
274
275     m_minSpaceShortage = RenderFlowThread::maxLogicalHeight();
276     return true; // Need another pass.
277 }
278
279 void RenderMultiColumnSet::recordSpaceShortage(LayoutUnit spaceShortage)
280 {
281     if (spaceShortage >= m_minSpaceShortage)
282         return;
283
284     // The space shortage is what we use as our stretch amount. We need a positive number here in
285     // order to get anywhere. Some lines actually have zero height. Ignore them.
286     if (spaceShortage > 0)
287         m_minSpaceShortage = spaceShortage;
288
289     m_minSpaceShortage = spaceShortage;
290 }
291
292 void RenderMultiColumnSet::updateLogicalWidth()
293 {
294     setComputedColumnWidthAndCount(multiColumnFlowThread()->columnWidth(), multiColumnFlowThread()->columnCount()); // FIXME: This will eventually vary if we are contained inside regions.
295     
296     // FIXME: When we add regions support, we'll start it off at the width of the multi-column
297     // block in that particular region.
298     setLogicalWidth(parentBox()->contentLogicalWidth());
299 }
300
301 bool RenderMultiColumnSet::requiresBalancing() const
302 {
303     if (!multiColumnFlowThread()->progressionIsInline())
304         return false;
305
306     if (RenderBox* next = RenderMultiColumnFlowThread::nextColumnSetOrSpannerSiblingOf(this)) {
307         if (!next->isRenderMultiColumnSet()) {
308             // If we're followed by a spanner, we need to balance.
309             ASSERT(multiColumnFlowThread()->findColumnSpannerPlaceholder(next));
310             return true;
311         }
312     }
313     RenderBlockFlow* container = multiColumnBlockFlow();
314     if (container->style().columnFill() == ColumnFillBalance)
315         return true;
316     return !multiColumnFlowThread()->columnHeightAvailable();
317 }
318
319 void RenderMultiColumnSet::prepareForLayout(bool initial)
320 {
321     // Guess box logical top. This might eliminate the need for another layout pass.
322     if (RenderBox* previous = RenderMultiColumnFlowThread::previousColumnSetOrSpannerSiblingOf(this))
323         setLogicalTop(previous->logicalBottom() + previous->marginAfter());
324     else
325         setLogicalTop(multiColumnBlockFlow()->borderAndPaddingBefore());
326
327     if (initial)
328         m_maxColumnHeight = calculateMaxColumnHeight();
329     if (requiresBalancing()) {
330         if (initial)
331             m_computedColumnHeight = 0;
332     } else
333         setAndConstrainColumnHeight(heightAdjustedForSetOffset(multiColumnFlowThread()->columnHeightAvailable()));
334
335     // Set box width.
336     updateLogicalWidth();
337
338     // Any breaks will be re-inserted during layout, so get rid of what we already have.
339     clearForcedBreaks();
340
341     // Nuke previously stored minimum column height. Contents may have changed for all we know.
342     m_minimumColumnHeight = 0;
343
344     // Start with "infinite" flow thread portion height until height is known.
345     setLogicalBottomInFlowThread(RenderFlowThread::maxLogicalHeight());
346
347     setNeedsLayout();
348 }
349
350 void RenderMultiColumnSet::beginFlow(RenderBlock* container)
351 {
352     RenderMultiColumnFlowThread* flowThread = multiColumnFlowThread();
353
354     // At this point layout is exactly at the beginning of this set. Store block offset from flow
355     // thread start.
356     LayoutUnit logicalTopInFlowThread = flowThread->offsetFromLogicalTopOfFirstRegion(container) + container->logicalHeight();
357     setLogicalTopInFlowThread(logicalTopInFlowThread);
358 }
359
360 void RenderMultiColumnSet::endFlow(RenderBlock* container, LayoutUnit bottomInContainer)
361 {
362     RenderMultiColumnFlowThread* flowThread = multiColumnFlowThread();
363
364     // At this point layout is exactly at the end of this set. Store block offset from flow thread
365     // start. Also note that a new column height may have affected the height used in the flow
366     // thread (because of struts), which may affect the number of columns. So we also need to update
367     // the flow thread portion height in order to be able to calculate actual column-count.
368     LayoutUnit logicalBottomInFlowThread = flowThread->offsetFromLogicalTopOfFirstRegion(container) + bottomInContainer;
369     setLogicalBottomInFlowThread(logicalBottomInFlowThread);
370     container->setLogicalHeight(bottomInContainer);
371     unsigned colCount = columnCount();
372     if (colCount > 1) {
373         LayoutUnit paddedLogicalBottomInFlowThread = logicalTopInFlowThread() + computedColumnHeight() * colCount;
374         if (logicalBottomInFlowThread != paddedLogicalBottomInFlowThread) {
375             // Stretch the container to fully contain all columns, so that later content doesn't
376             // start at the wrong position and end up bleeding into the columns of this set.
377             container->setLogicalHeight(container->logicalHeight() + paddedLogicalBottomInFlowThread - logicalBottomInFlowThread);
378             setLogicalBottomInFlowThread(paddedLogicalBottomInFlowThread);
379         }
380     }
381 }
382
383 void RenderMultiColumnSet::layout()
384 {
385     RenderBlockFlow::layout();
386
387     // At this point the logical top and bottom of the column set are known. Update maximum column
388     // height (multicol height may be constrained).
389     m_maxColumnHeight = calculateMaxColumnHeight();
390
391     if (!nextSiblingMultiColumnSet()) {
392         // This is the last set, i.e. the last region. Seize the opportunity to validate them.
393         multiColumnFlowThread()->validateRegions();
394     }
395 }
396
397 void RenderMultiColumnSet::computeLogicalHeight(LayoutUnit, LayoutUnit logicalTop, LogicalExtentComputedValues& computedValues) const
398 {
399     computedValues.m_extent = m_computedColumnHeight;
400     computedValues.m_position = logicalTop;
401 }
402
403 LayoutUnit RenderMultiColumnSet::calculateMaxColumnHeight() const
404 {
405     RenderBlockFlow* multicolBlock = multiColumnBlockFlow();
406     const RenderStyle& multicolStyle = multicolBlock->style();
407     LayoutUnit availableHeight = multiColumnFlowThread()->columnHeightAvailable();
408     LayoutUnit maxColumnHeight = availableHeight ? availableHeight : RenderFlowThread::maxLogicalHeight();
409     if (!multicolStyle.logicalMaxHeight().isUndefined()) {
410         LayoutUnit logicalMaxHeight = multicolBlock->computeContentLogicalHeight(multicolStyle.logicalMaxHeight());
411         if (logicalMaxHeight != -1 && maxColumnHeight > logicalMaxHeight)
412             maxColumnHeight = logicalMaxHeight;
413     }
414     return heightAdjustedForSetOffset(maxColumnHeight);
415 }
416
417 LayoutUnit RenderMultiColumnSet::columnGap() const
418 {
419     // FIXME: Eventually we will cache the column gap when the widths of columns start varying, but for now we just
420     // go to the parent block to get the gap.
421     RenderBlockFlow* parentBlock = toRenderBlockFlow(parent());
422     if (parentBlock->style().hasNormalColumnGap())
423         return parentBlock->style().fontDescription().computedPixelSize(); // "1em" is recommended as the normal gap setting. Matches <p> margins.
424     return parentBlock->style().columnGap();
425 }
426
427 unsigned RenderMultiColumnSet::columnCount() const
428 {
429     // We must always return a value of 1 or greater. Column count = 0 is a meaningless situation,
430     // and will confuse and cause problems in other parts of the code.
431     if (!computedColumnHeight())
432         return 1;
433
434     // Our portion rect determines our column count. We have as many columns as needed to fit all the content.
435     LayoutUnit logicalHeightInColumns = flowThread()->isHorizontalWritingMode() ? flowThreadPortionRect().height() : flowThreadPortionRect().width();
436     if (!logicalHeightInColumns)
437         return 1;
438     
439     unsigned count = ceil(static_cast<float>(logicalHeightInColumns) / computedColumnHeight());
440     ASSERT(count >= 1);
441     return count;
442 }
443
444 LayoutRect RenderMultiColumnSet::columnRectAt(unsigned index) const
445 {
446     LayoutUnit colLogicalWidth = computedColumnWidth();
447     LayoutUnit colLogicalHeight = computedColumnHeight();
448     LayoutUnit colLogicalTop = borderAndPaddingBefore();
449     LayoutUnit colLogicalLeft = borderAndPaddingLogicalLeft();
450     LayoutUnit colGap = columnGap();
451     
452     bool progressionReversed = multiColumnFlowThread()->progressionIsReversed();
453     bool progressionInline = multiColumnFlowThread()->progressionIsInline();
454     
455     if (progressionInline) {
456         if (style().isLeftToRightDirection() ^ progressionReversed)
457             colLogicalLeft += index * (colLogicalWidth + colGap);
458         else
459             colLogicalLeft += contentLogicalWidth() - colLogicalWidth - index * (colLogicalWidth + colGap);
460     } else {
461         if (!progressionReversed)
462             colLogicalTop += index * (colLogicalHeight + colGap);
463         else
464             colLogicalTop += contentLogicalHeight() - colLogicalHeight - index * (colLogicalHeight + colGap);
465     }
466     
467     if (isHorizontalWritingMode())
468         return LayoutRect(colLogicalLeft, colLogicalTop, colLogicalWidth, colLogicalHeight);
469     return LayoutRect(colLogicalTop, colLogicalLeft, colLogicalHeight, colLogicalWidth);
470 }
471
472 unsigned RenderMultiColumnSet::columnIndexAtOffset(LayoutUnit offset, ColumnIndexCalculationMode mode) const
473 {
474     LayoutRect portionRect(flowThreadPortionRect());
475
476     // Handle the offset being out of range.
477     LayoutUnit flowThreadLogicalTop = isHorizontalWritingMode() ? portionRect.y() : portionRect.x();
478     if (offset < flowThreadLogicalTop)
479         return 0;
480     // If we're laying out right now, we cannot constrain against some logical bottom, since it
481     // isn't known yet. Otherwise, just return the last column if we're past the logical bottom.
482     if (mode == ClampToExistingColumns) {
483         LayoutUnit flowThreadLogicalBottom = isHorizontalWritingMode() ? portionRect.maxY() : portionRect.maxX();
484         if (offset >= flowThreadLogicalBottom)
485             return columnCount() - 1;
486     }
487
488     // Just divide by the column height to determine the correct column.
489     return static_cast<float>(offset - flowThreadLogicalTop) / computedColumnHeight();
490 }
491
492 LayoutRect RenderMultiColumnSet::flowThreadPortionRectAt(unsigned index) const
493 {
494     LayoutRect portionRect = flowThreadPortionRect();
495     if (isHorizontalWritingMode())
496         portionRect = LayoutRect(portionRect.x(), portionRect.y() + index * computedColumnHeight(), portionRect.width(), computedColumnHeight());
497     else
498         portionRect = LayoutRect(portionRect.x() + index * computedColumnHeight(), portionRect.y(), computedColumnHeight(), portionRect.height());
499     return portionRect;
500 }
501
502 LayoutRect RenderMultiColumnSet::flowThreadPortionOverflowRect(const LayoutRect& portionRect, unsigned index, unsigned colCount, LayoutUnit colGap)
503 {
504     // This function determines the portion of the flow thread that paints for the column. Along the inline axis, columns are
505     // unclipped at outside edges (i.e., the first and last column in the set), and they clip to half the column
506     // gap along interior edges.
507     //
508     // In the block direction, we will not clip overflow out of the top of the first column, or out of the bottom of
509     // the last column. This applies only to the true first column and last column across all column sets.
510     //
511     // FIXME: Eventually we will know overflow on a per-column basis, but we can't do this until we have a painting
512     // mode that understands not to paint contents from a previous column in the overflow area of a following column.
513     // This problem applies to regions and pages as well and is not unique to columns.
514
515     bool progressionReversed = multiColumnFlowThread()->progressionIsReversed();
516
517     bool isFirstColumn = !index;
518     bool isLastColumn = index == colCount - 1;
519     bool isLeftmostColumn = style().isLeftToRightDirection() ^ progressionReversed ? isFirstColumn : isLastColumn;
520     bool isRightmostColumn = style().isLeftToRightDirection() ^ progressionReversed ? isLastColumn : isFirstColumn;
521
522     // Calculate the overflow rectangle, based on the flow thread's, clipped at column logical
523     // top/bottom unless it's the first/last column.
524     LayoutRect overflowRect = overflowRectForFlowThreadPortion(portionRect, isFirstColumn && isFirstRegion(), isLastColumn && isLastRegion(), VisualOverflow);
525
526     // Avoid overflowing into neighboring columns, by clipping in the middle of adjacent column
527     // gaps. Also make sure that we avoid rounding errors.
528     if (isHorizontalWritingMode()) {
529         if (!isLeftmostColumn)
530             overflowRect.shiftXEdgeTo(portionRect.x() - colGap / 2);
531         if (!isRightmostColumn)
532             overflowRect.shiftMaxXEdgeTo(portionRect.maxX() + colGap - colGap / 2);
533     } else {
534         if (!isLeftmostColumn)
535             overflowRect.shiftYEdgeTo(portionRect.y() - colGap / 2);
536         if (!isRightmostColumn)
537             overflowRect.shiftMaxYEdgeTo(portionRect.maxY() + colGap - colGap / 2);
538     }
539     return overflowRect;
540 }
541
542 void RenderMultiColumnSet::paintColumnRules(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
543 {
544     if (paintInfo.context->paintingDisabled())
545         return;
546
547     RenderMultiColumnFlowThread* flowThread = multiColumnFlowThread();
548     const RenderStyle& blockStyle = parent()->style();
549     const Color& ruleColor = blockStyle.visitedDependentColor(CSSPropertyWebkitColumnRuleColor);
550     bool ruleTransparent = blockStyle.columnRuleIsTransparent();
551     EBorderStyle ruleStyle = blockStyle.columnRuleStyle();
552     LayoutUnit ruleThickness = blockStyle.columnRuleWidth();
553     LayoutUnit colGap = columnGap();
554     bool renderRule = ruleStyle > BHIDDEN && !ruleTransparent;
555     if (!renderRule)
556         return;
557
558     unsigned colCount = columnCount();
559     if (colCount <= 1)
560         return;
561
562     bool antialias = shouldAntialiasLines(paintInfo.context);
563
564     if (flowThread->progressionIsInline()) {
565         bool leftToRight = style().isLeftToRightDirection() ^ flowThread->progressionIsReversed();
566         LayoutUnit currLogicalLeftOffset = leftToRight ? LayoutUnit() : contentLogicalWidth();
567         LayoutUnit ruleAdd = logicalLeftOffsetForContent();
568         LayoutUnit ruleLogicalLeft = leftToRight ? LayoutUnit() : contentLogicalWidth();
569         LayoutUnit inlineDirectionSize = computedColumnWidth();
570         BoxSide boxSide = isHorizontalWritingMode()
571             ? leftToRight ? BSLeft : BSRight
572             : leftToRight ? BSTop : BSBottom;
573
574         for (unsigned i = 0; i < colCount; i++) {
575             // Move to the next position.
576             if (leftToRight) {
577                 ruleLogicalLeft += inlineDirectionSize + colGap / 2;
578                 currLogicalLeftOffset += inlineDirectionSize + colGap;
579             } else {
580                 ruleLogicalLeft -= (inlineDirectionSize + colGap / 2);
581                 currLogicalLeftOffset -= (inlineDirectionSize + colGap);
582             }
583
584             // Now paint the column rule.
585             if (i < colCount - 1) {
586                 LayoutUnit ruleLeft = isHorizontalWritingMode() ? paintOffset.x() + ruleLogicalLeft - ruleThickness / 2 + ruleAdd : paintOffset.x() + borderLeft() + paddingLeft();
587                 LayoutUnit ruleRight = isHorizontalWritingMode() ? ruleLeft + ruleThickness : ruleLeft + contentWidth();
588                 LayoutUnit ruleTop = isHorizontalWritingMode() ? paintOffset.y() + borderTop() + paddingTop() : paintOffset.y() + ruleLogicalLeft - ruleThickness / 2 + ruleAdd;
589                 LayoutUnit ruleBottom = isHorizontalWritingMode() ? ruleTop + contentHeight() : ruleTop + ruleThickness;
590                 IntRect pixelSnappedRuleRect = pixelSnappedIntRectFromEdges(ruleLeft, ruleTop, ruleRight, ruleBottom);
591                 drawLineForBoxSide(paintInfo.context, pixelSnappedRuleRect.x(), pixelSnappedRuleRect.y(), pixelSnappedRuleRect.maxX(), pixelSnappedRuleRect.maxY(), boxSide, ruleColor, ruleStyle, 0, 0, antialias);
592             }
593             
594             ruleLogicalLeft = currLogicalLeftOffset;
595         }
596     } else {
597         bool topToBottom = !style().isFlippedBlocksWritingMode() ^ flowThread->progressionIsReversed();
598         LayoutUnit ruleLeft = isHorizontalWritingMode() ? LayoutUnit() : colGap / 2 - colGap - ruleThickness / 2;
599         LayoutUnit ruleWidth = isHorizontalWritingMode() ? contentWidth() : ruleThickness;
600         LayoutUnit ruleTop = isHorizontalWritingMode() ? colGap / 2 - colGap - ruleThickness / 2 : LayoutUnit();
601         LayoutUnit ruleHeight = isHorizontalWritingMode() ? ruleThickness : contentHeight();
602         LayoutRect ruleRect(ruleLeft, ruleTop, ruleWidth, ruleHeight);
603
604         if (!topToBottom) {
605             if (isHorizontalWritingMode())
606                 ruleRect.setY(height() - ruleRect.maxY());
607             else
608                 ruleRect.setX(width() - ruleRect.maxX());
609         }
610
611         ruleRect.moveBy(paintOffset);
612
613         BoxSide boxSide = isHorizontalWritingMode() ? topToBottom ? BSTop : BSBottom : topToBottom ? BSLeft : BSRight;
614
615         LayoutSize step(0, topToBottom ? computedColumnHeight() + colGap : -(computedColumnHeight() + colGap));
616         if (!isHorizontalWritingMode())
617             step = step.transposedSize();
618
619         for (unsigned i = 1; i < colCount; i++) {
620             ruleRect.move(step);
621             IntRect pixelSnappedRuleRect = pixelSnappedIntRect(ruleRect);
622             drawLineForBoxSide(paintInfo.context, pixelSnappedRuleRect.x(), pixelSnappedRuleRect.y(), pixelSnappedRuleRect.maxX(), pixelSnappedRuleRect.maxY(), boxSide, ruleColor, ruleStyle, 0, 0, antialias);
623         }
624     }
625 }
626
627 void RenderMultiColumnSet::repaintFlowThreadContent(const LayoutRect& repaintRect)
628 {
629     // Figure out the start and end columns and only check within that range so that we don't walk the
630     // entire column set. Put the repaint rect into flow thread coordinates by flipping it first.
631     LayoutRect flowThreadRepaintRect(repaintRect);
632     flowThread()->flipForWritingMode(flowThreadRepaintRect);
633     
634     // Now we can compare this rect with the flow thread portions owned by each column. First let's
635     // just see if the repaint rect intersects our flow thread portion at all.
636     LayoutRect clippedRect(flowThreadRepaintRect);
637     clippedRect.intersect(RenderRegion::flowThreadPortionOverflowRect());
638     if (clippedRect.isEmpty())
639         return;
640     
641     // Now we know we intersect at least one column. Let's figure out the logical top and logical
642     // bottom of the area we're repainting.
643     LayoutUnit repaintLogicalTop = isHorizontalWritingMode() ? flowThreadRepaintRect.y() : flowThreadRepaintRect.x();
644     LayoutUnit repaintLogicalBottom = (isHorizontalWritingMode() ? flowThreadRepaintRect.maxY() : flowThreadRepaintRect.maxX()) - 1;
645     
646     unsigned startColumn = columnIndexAtOffset(repaintLogicalTop);
647     unsigned endColumn = columnIndexAtOffset(repaintLogicalBottom);
648     
649     LayoutUnit colGap = columnGap();
650     unsigned colCount = columnCount();
651     for (unsigned i = startColumn; i <= endColumn; i++) {
652         LayoutRect colRect = columnRectAt(i);
653         
654         // Get the portion of the flow thread that corresponds to this column.
655         LayoutRect flowThreadPortion = flowThreadPortionRectAt(i);
656
657         // Now get the overflow rect that corresponds to the column.
658         LayoutRect flowThreadOverflowPortion = flowThreadPortionOverflowRect(flowThreadPortion, i, colCount, colGap);
659
660         // Do a repaint for this specific column.
661         repaintFlowThreadContentRectangle(repaintRect, flowThreadPortion, colRect.location(), &flowThreadOverflowPortion);
662     }
663 }
664
665 LayoutUnit RenderMultiColumnSet::initialBlockOffsetForPainting() const
666 {
667     bool progressionReversed = multiColumnFlowThread()->progressionIsReversed();
668     bool progressionIsInline = multiColumnFlowThread()->progressionIsInline();
669     
670     LayoutUnit result = 0;
671     if (!progressionIsInline && progressionReversed) {
672         LayoutRect colRect = columnRectAt(0);
673         result = isHorizontalWritingMode() ? colRect.y() : colRect.x();
674         if (style().isFlippedBlocksWritingMode())
675             result = -result;
676     }
677     return result;
678 }
679
680 void RenderMultiColumnSet::collectLayerFragments(LayerFragments& fragments, const LayoutRect& layerBoundingBox, const LayoutRect& dirtyRect)
681 {
682     // Let's start by introducing the different coordinate systems involved here. They are different
683     // in how they deal with writing modes and columns. RenderLayer rectangles tend to be more
684     // physical than the rectangles used in RenderObject & co.
685     //
686     // The two rectangles passed to this method are physical, except that we pretend that there's
687     // only one long column (that's the flow thread). They are relative to the top left corner of
688     // the flow thread. All rectangles being compared to the dirty rect also need to be in this
689     // coordinate system.
690     //
691     // Then there's the output from this method - the stuff we put into the list of fragments. The
692     // translationOffset point is the actual physical translation required to get from a location in
693     // the flow thread to a location in some column. The paginationClip rectangle is in the same
694     // coordinate system as the two rectangles passed to this method (i.e. physical, in flow thread
695     // coordinates, pretending that there's only one long column).
696     //
697     // All other rectangles in this method are slightly less physical, when it comes to how they are
698     // used with different writing modes, but they aren't really logical either. They are just like
699     // RenderBox::frameRect(). More precisely, the sizes are physical, and the inline direction
700     // coordinate is too, but the block direction coordinate is always "logical top". These
701     // rectangles also pretend that there's only one long column, i.e. they are for the flow thread.
702     //
703     // To sum up: input and output from this method are "physical" RenderLayer-style rectangles and
704     // points, while inside this method we mostly use the RenderObject-style rectangles (with the
705     // block direction coordinate always being logical top).
706
707     // Put the layer bounds into flow thread-local coordinates by flipping it first. Since we're in
708     // a renderer, most rectangles are represented this way.
709     LayoutRect layerBoundsInFlowThread(layerBoundingBox);
710     flowThread()->flipForWritingMode(layerBoundsInFlowThread);
711
712     // Now we can compare with the flow thread portions owned by each column. First let's
713     // see if the rect intersects our flow thread portion at all.
714     LayoutRect clippedRect(layerBoundsInFlowThread);
715     clippedRect.intersect(RenderRegion::flowThreadPortionOverflowRect());
716     if (clippedRect.isEmpty())
717         return;
718     
719     // Now we know we intersect at least one column. Let's figure out the logical top and logical
720     // bottom of the area we're checking.
721     LayoutUnit layerLogicalTop = isHorizontalWritingMode() ? layerBoundsInFlowThread.y() : layerBoundsInFlowThread.x();
722     LayoutUnit layerLogicalBottom = (isHorizontalWritingMode() ? layerBoundsInFlowThread.maxY() : layerBoundsInFlowThread.maxX()) - 1;
723     
724     // Figure out the start and end columns and only check within that range so that we don't walk the
725     // entire column set.
726     unsigned startColumn = columnIndexAtOffset(layerLogicalTop);
727     unsigned endColumn = columnIndexAtOffset(layerLogicalBottom);
728     
729     LayoutUnit colLogicalWidth = computedColumnWidth();
730     LayoutUnit colGap = columnGap();
731     unsigned colCount = columnCount();
732
733     bool progressionReversed = multiColumnFlowThread()->progressionIsReversed();
734     bool progressionIsInline = multiColumnFlowThread()->progressionIsInline();
735
736     LayoutUnit initialBlockOffset = initialBlockOffsetForPainting();
737     
738     for (unsigned i = startColumn; i <= endColumn; i++) {
739         // Get the portion of the flow thread that corresponds to this column.
740         LayoutRect flowThreadPortion = flowThreadPortionRectAt(i);
741         
742         // Now get the overflow rect that corresponds to the column.
743         LayoutRect flowThreadOverflowPortion = flowThreadPortionOverflowRect(flowThreadPortion, i, colCount, colGap);
744
745         // In order to create a fragment we must intersect the portion painted by this column.
746         LayoutRect clippedRect(layerBoundsInFlowThread);
747         clippedRect.intersect(flowThreadOverflowPortion);
748         if (clippedRect.isEmpty())
749             continue;
750         
751         // We also need to intersect the dirty rect. We have to apply a translation and shift based off
752         // our column index.
753         LayoutPoint translationOffset;
754         LayoutUnit inlineOffset = progressionIsInline ? i * (colLogicalWidth + colGap) : LayoutUnit();
755         
756         bool leftToRight = style().isLeftToRightDirection() ^ progressionReversed;
757         if (!leftToRight) {
758             inlineOffset = -inlineOffset;
759             if (progressionReversed)
760                 inlineOffset += contentLogicalWidth() - colLogicalWidth;
761         }
762         translationOffset.setX(inlineOffset);
763         LayoutUnit blockOffset = initialBlockOffset + logicalTop() - flowThread()->logicalTop() + (isHorizontalWritingMode() ? -flowThreadPortion.y() : -flowThreadPortion.x());
764         if (!progressionIsInline) {
765             if (!progressionReversed)
766                 blockOffset = i * colGap;
767             else
768                 blockOffset -= i * (computedColumnHeight() + colGap);
769         }
770         if (isFlippedBlocksWritingMode(style().writingMode()))
771             blockOffset = -blockOffset;
772         translationOffset.setY(blockOffset);
773         if (!isHorizontalWritingMode())
774             translationOffset = translationOffset.transposedPoint();
775         // FIXME: The translation needs to include the multicolumn set's content offset within the
776         // multicolumn block as well. This won't be an issue until we start creating multiple multicolumn sets.
777
778         // Shift the dirty rect to be in flow thread coordinates with this translation applied.
779         LayoutRect translatedDirtyRect(dirtyRect);
780         translatedDirtyRect.moveBy(-translationOffset);
781         
782         // See if we intersect the dirty rect.
783         clippedRect = layerBoundingBox;
784         clippedRect.intersect(translatedDirtyRect);
785         if (clippedRect.isEmpty())
786             continue;
787         
788         // Something does need to paint in this column. Make a fragment now and supply the physical translation
789         // offset and the clip rect for the column with that offset applied.
790         LayerFragment fragment;
791         fragment.paginationOffset = translationOffset;
792
793         LayoutRect flippedFlowThreadOverflowPortion(flowThreadOverflowPortion);
794         // Flip it into more a physical (RenderLayer-style) rectangle.
795         flowThread()->flipForWritingMode(flippedFlowThreadOverflowPortion);
796         fragment.paginationClip = flippedFlowThreadOverflowPortion;
797         fragments.append(fragment);
798     }
799 }
800
801 LayoutPoint RenderMultiColumnSet::columnTranslationForOffset(const LayoutUnit& offset) const
802 {
803     unsigned startColumn = columnIndexAtOffset(offset);
804     
805     LayoutUnit colGap = columnGap();
806     LayoutUnit colLogicalWidth = computedColumnWidth();
807     
808     LayoutRect flowThreadPortion = flowThreadPortionRectAt(startColumn);
809     LayoutPoint translationOffset;
810
811     bool progressionReversed = multiColumnFlowThread()->progressionIsReversed();
812     bool progressionIsInline = multiColumnFlowThread()->progressionIsInline();
813
814     LayoutUnit initialBlockOffset = initialBlockOffsetForPainting();
815     
816     LayoutUnit inlineOffset = progressionIsInline ? startColumn * (colLogicalWidth + colGap) : LayoutUnit();
817     
818     bool leftToRight = style().isLeftToRightDirection() ^ progressionReversed;
819     if (!leftToRight) {
820         inlineOffset = -inlineOffset;
821         if (progressionReversed)
822             inlineOffset += contentLogicalWidth() - colLogicalWidth;
823     }
824     translationOffset.setX(inlineOffset);
825     LayoutUnit blockOffset = initialBlockOffset + (isHorizontalWritingMode() ? -flowThreadPortion.y() : -flowThreadPortion.x());
826     if (!progressionIsInline) {
827         if (!progressionReversed)
828             blockOffset = startColumn * colGap;
829         else
830             blockOffset -= startColumn * (computedColumnHeight() + colGap);
831     }
832     if (isFlippedBlocksWritingMode(style().writingMode()))
833         blockOffset = -blockOffset;
834     translationOffset.setY(blockOffset);
835     
836     if (!isHorizontalWritingMode())
837         translationOffset = translationOffset.transposedPoint();
838     
839     // FIXME: The translation needs to include the multicolumn set's content offset within the
840     // multicolumn block as well. This won't be an issue until we start creating multiple multicolumn sets.
841     return translationOffset;
842 }
843
844 void RenderMultiColumnSet::adjustRegionBoundsFromFlowThreadPortionRect(const LayoutPoint& layerOffset, LayoutRect& regionBounds)
845 {
846     regionBounds.moveBy(roundedIntPoint(-columnTranslationForOffset(isHorizontalWritingMode() ? layerOffset.y() : layerOffset.x())));
847 }
848
849 void RenderMultiColumnSet::addOverflowFromChildren()
850 {
851     // FIXME: Need to do much better here.
852     unsigned colCount = columnCount();
853     if (!colCount)
854         return;
855     
856     LayoutRect lastRect = columnRectAt(colCount - 1);
857     addLayoutOverflow(lastRect);
858     if (!hasOverflowClip())
859         addVisualOverflow(lastRect);
860 }
861
862 VisiblePosition RenderMultiColumnSet::positionForPoint(const LayoutPoint& physicalPoint)
863 {
864     // Determine which columns we intersect.
865     LayoutUnit colGap = columnGap();
866     LayoutUnit halfColGap = colGap / 2;
867     LayoutPoint columnPoint(columnRectAt(0).location());
868     LayoutUnit logicalOffset = 0;
869     
870     bool progressionIsInline = multiColumnFlowThread()->progressionIsInline();
871
872     LayoutPoint point = physicalPoint;
873     
874     for (unsigned i = 0; i < columnCount(); i++) {
875         // Add in half the column gap to the left and right of the rect.
876         LayoutRect colRect = columnRectAt(i);
877         flipForWritingMode(colRect);
878         if (isHorizontalWritingMode() == progressionIsInline) {
879             LayoutRect gapAndColumnRect(colRect.x() - halfColGap, colRect.y(), colRect.width() + colGap, colRect.height());
880             if (point.x() >= gapAndColumnRect.x() && point.x() < gapAndColumnRect.maxX()) {
881                 if (progressionIsInline) {
882                     // FIXME: The clamping that follows is not completely right for right-to-left
883                     // content.
884                     // Clamp everything above the column to its top left.
885                     if (point.y() < gapAndColumnRect.y())
886                         point = gapAndColumnRect.location();
887                     // Clamp everything below the column to the next column's top left. If there is
888                     // no next column, this still maps to just after this column.
889                     else if (point.y() >= gapAndColumnRect.maxY()) {
890                         point = gapAndColumnRect.location();
891                         point.move(0, gapAndColumnRect.height());
892                     }
893                 } else {
894                     if (point.x() < colRect.x())
895                         point.setX(colRect.x());
896                     else if (point.x() >= colRect.maxX())
897                         point.setX(colRect.maxX() - 1);
898                 }
899
900                 // We're inside the column. Translate the x and y into our column coordinate space.
901                 if (progressionIsInline)
902                     point.move(columnPoint.x() - colRect.x(), (!style().isFlippedBlocksWritingMode() ? logicalOffset : -logicalOffset));
903                 else
904                     point.move((!style().isFlippedBlocksWritingMode() ? logicalOffset : -logicalOffset) - colRect.x() + borderLeft() + paddingLeft(), 0);
905                 
906                 LayoutRect portion = flowThreadPortionRect();
907                 flipForWritingMode(portion);
908                 point.move(isHorizontalWritingMode() ? LayoutUnit() : portion.x(), isHorizontalWritingMode() ? portion.y() : LayoutUnit());
909                 return multiColumnFlowThread()->positionForPoint(point);
910             }
911
912             // Move to the next position.
913             logicalOffset += progressionIsInline ? colRect.height() : colRect.width();
914         } else {
915             LayoutRect gapAndColumnRect(colRect.x(), colRect.y() - halfColGap, colRect.width(), colRect.height() + colGap);
916             if (point.y() >= gapAndColumnRect.y() && point.y() < gapAndColumnRect.maxY()) {
917                 if (progressionIsInline) {
918                     // FIXME: The clamping that follows is not completely right for right-to-left
919                     // content.
920                     // Clamp everything above the column to its top left.
921                     if (point.x() < gapAndColumnRect.x())
922                         point = gapAndColumnRect.location();
923                     // Clamp everything below the column to the next column's top left. If there is
924                     // no next column, this still maps to just after this column.
925                     else if (point.x() >= gapAndColumnRect.maxX()) {
926                         point = gapAndColumnRect.location();
927                         point.move(gapAndColumnRect.width(), 0);
928                     }
929                 } else {
930                     if (point.y() < colRect.y())
931                         point.setY(colRect.y());
932                     else if (point.y() >= colRect.maxY())
933                         point.setY(colRect.maxY() - 1);
934                 }
935
936                 // We're inside the column. Translate the x and y into our column coordinate space.
937                 if (progressionIsInline)
938                     point.move((!style().isFlippedBlocksWritingMode() ? logicalOffset : -logicalOffset), columnPoint.y() - colRect.y());
939                 else
940                     point.move(0, (!style().isFlippedBlocksWritingMode() ? logicalOffset : -logicalOffset) - colRect.y() + borderTop() + paddingTop());
941                 
942                 LayoutRect portion = flowThreadPortionRect();
943                 flipForWritingMode(portion);
944                 point.move(isHorizontalWritingMode() ? LayoutUnit() : portion.x(), isHorizontalWritingMode() ? portion.y() : LayoutUnit());
945                 
946                 return multiColumnFlowThread()->positionForPoint(point);
947             }
948
949             // Move to the next position.
950             logicalOffset += progressionIsInline ? colRect.width() : colRect.height();
951         }
952     }
953
954     return VisiblePosition();
955 }
956
957 const char* RenderMultiColumnSet::renderName() const
958 {    
959     return "RenderMultiColumnSet";
960 }
961
962 }