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