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