186ca870ed10913d58b8549eb96de336e3455359
[WebKit-https.git] / Source / WebCore / rendering / RenderTable.cpp
1 /*
2  * Copyright (C) 1997 Martin Jones (mjones@kde.org)
3  *           (C) 1997 Torben Weis (weis@kde.org)
4  *           (C) 1998 Waldo Bastian (bastian@kde.org)
5  *           (C) 1999 Lars Knoll (knoll@kde.org)
6  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
7  * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2014 Apple Inc. All rights reserved.
8  * Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)
9  *
10  * This library is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU Library General Public
12  * License as published by the Free Software Foundation; either
13  * version 2 of the License, or (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18  * Library General Public License for more details.
19  *
20  * You should have received a copy of the GNU Library General Public License
21  * along with this library; see the file COPYING.LIB.  If not, write to
22  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
23  * Boston, MA 02110-1301, USA.
24  */
25
26 #include "config.h"
27 #include "RenderTable.h"
28
29 #include "AutoTableLayout.h"
30 #include "CollapsedBorderValue.h"
31 #include "Document.h"
32 #include "FixedTableLayout.h"
33 #include "FrameView.h"
34 #include "HitTestResult.h"
35 #include "HTMLNames.h"
36 #include "HTMLTableElement.h"
37 #include "LayoutRepainter.h"
38 #include "RenderBlockFlow.h"
39 #include "RenderChildIterator.h"
40 #include "RenderDescendantIterator.h"
41 #include "RenderIterator.h"
42 #include "RenderLayer.h"
43 #include "RenderLayoutState.h"
44 #include "RenderTableCaption.h"
45 #include "RenderTableCell.h"
46 #include "RenderTableCol.h"
47 #include "RenderTableSection.h"
48 #include "RenderTreeBuilder.h"
49 #include "RenderView.h"
50 #include "StyleInheritedData.h"
51 #include <wtf/IsoMallocInlines.h>
52 #include <wtf/SetForScope.h>
53 #include <wtf/StackStats.h>
54
55 namespace WebCore {
56
57 using namespace HTMLNames;
58
59 WTF_MAKE_ISO_ALLOCATED_IMPL(RenderTable);
60
61 RenderTable::RenderTable(Element& element, RenderStyle&& style)
62     : RenderBlock(element, WTFMove(style), 0)
63     , m_currentBorder(nullptr)
64     , m_collapsedBordersValid(false)
65     , m_collapsedEmptyBorderIsPresent(false)
66     , m_hasColElements(false)
67     , m_needsSectionRecalc(false)
68     , m_columnLogicalWidthChanged(false)
69     , m_columnRenderersValid(false)
70     , m_hasCellColspanThatDeterminesTableWidth(false)
71     , m_borderStart(0)
72     , m_borderEnd(0)
73     , m_columnOffsetTop(-1)
74     , m_columnOffsetHeight(-1)
75 {
76     setChildrenInline(false);
77     m_columnPos.fill(0, 1);
78 }
79
80 RenderTable::RenderTable(Document& document, RenderStyle&& style)
81     : RenderBlock(document, WTFMove(style), 0)
82     , m_currentBorder(nullptr)
83     , m_collapsedBordersValid(false)
84     , m_collapsedEmptyBorderIsPresent(false)
85     , m_hasColElements(false)
86     , m_needsSectionRecalc(false)
87     , m_columnLogicalWidthChanged(false)
88     , m_columnRenderersValid(false)
89     , m_hasCellColspanThatDeterminesTableWidth(false)
90     , m_borderStart(0)
91     , m_borderEnd(0)
92 {
93     setChildrenInline(false);
94     m_columnPos.fill(0, 1);
95 }
96
97 RenderTable::~RenderTable() = default;
98
99 RenderTableSection* RenderTable::header() const
100 {
101     return m_head.get();
102 }
103
104 RenderTableSection* RenderTable::footer() const
105 {
106     return m_foot.get();
107 }
108
109 RenderTableSection* RenderTable::firstBody() const
110 {
111     return m_firstBody.get();
112 }
113
114 RenderTableSection* RenderTable::topSection() const
115 {
116     ASSERT(!needsSectionRecalc());
117     if (m_head)
118         return m_head.get();
119     if (m_firstBody)
120         return m_firstBody.get();
121     return m_foot.get();
122 }
123
124 void RenderTable::styleDidChange(StyleDifference diff, const RenderStyle* oldStyle)
125 {
126     RenderBlock::styleDidChange(diff, oldStyle);
127     propagateStyleToAnonymousChildren(PropagateToAllChildren);
128
129     auto oldTableLayout = oldStyle ? oldStyle->tableLayout() : TableLayoutType::Auto;
130
131     // In the collapsed border model, there is no cell spacing.
132     m_hSpacing = collapseBorders() ? 0 : style().horizontalBorderSpacing();
133     m_vSpacing = collapseBorders() ? 0 : style().verticalBorderSpacing();
134     m_columnPos[0] = m_hSpacing;
135
136     if (!m_tableLayout || style().tableLayout() != oldTableLayout) {
137         // According to the CSS2 spec, you only use fixed table layout if an
138         // explicit width is specified on the table.  Auto width implies auto table layout.
139         if (style().tableLayout() == TableLayoutType::Fixed && !style().logicalWidth().isAuto())
140             m_tableLayout = std::make_unique<FixedTableLayout>(this);
141         else
142             m_tableLayout = std::make_unique<AutoTableLayout>(this);
143     }
144
145     // If border was changed, invalidate collapsed borders cache.
146     if (oldStyle && oldStyle->border() != style().border())
147         invalidateCollapsedBorders();
148 }
149
150 static inline void resetSectionPointerIfNotBefore(WeakPtr<RenderTableSection>& section, RenderObject* before)
151 {
152     if (!before || !section)
153         return;
154     auto* previousSibling = before->previousSibling();
155     while (previousSibling && previousSibling != section)
156         previousSibling = previousSibling->previousSibling();
157     if (!previousSibling)
158         section.clear();
159 }
160
161 void RenderTable::willInsertTableColumn(RenderTableCol&, RenderObject*)
162 {
163     m_hasColElements = true;
164 }
165
166 void RenderTable::willInsertTableSection(RenderTableSection& child, RenderObject* beforeChild)
167 {
168     switch (child.style().display()) {
169     case DisplayType::TableHeaderGroup:
170         resetSectionPointerIfNotBefore(m_head, beforeChild);
171         if (!m_head)
172             m_head = makeWeakPtr(child);
173         else {
174             resetSectionPointerIfNotBefore(m_firstBody, beforeChild);
175             if (!m_firstBody)
176                 m_firstBody = makeWeakPtr(child);
177         }
178         break;
179     case DisplayType::TableFooterGroup:
180         resetSectionPointerIfNotBefore(m_foot, beforeChild);
181         if (!m_foot) {
182             m_foot = makeWeakPtr(child);
183             break;
184         }
185         FALLTHROUGH;
186     case DisplayType::TableRowGroup:
187         resetSectionPointerIfNotBefore(m_firstBody, beforeChild);
188         if (!m_firstBody)
189             m_firstBody = makeWeakPtr(child);
190         break;
191     default:
192         ASSERT_NOT_REACHED();
193     }
194
195     setNeedsSectionRecalc();
196 }
197
198 void RenderTable::addCaption(RenderTableCaption& caption)
199 {
200     ASSERT(m_captions.find(&caption) == notFound);
201     m_captions.append(makeWeakPtr(caption));
202 }
203
204 void RenderTable::removeCaption(RenderTableCaption& oldCaption)
205 {
206     bool removed = m_captions.removeFirst(&oldCaption);
207     ASSERT_UNUSED(removed, removed);
208 }
209
210 void RenderTable::invalidateCachedColumns()
211 {
212     m_columnRenderersValid = false;
213     m_columnRenderers.shrink(0);
214     m_effectiveColumnIndexMap.clear();
215 }
216
217 void RenderTable::invalidateCachedColumnOffsets()
218 {
219     m_columnOffsetTop = -1;
220     m_columnOffsetHeight = -1;
221 }
222
223 void RenderTable::addColumn(const RenderTableCol*)
224 {
225     invalidateCachedColumns();
226 }
227
228 void RenderTable::removeColumn(const RenderTableCol*)
229 {
230     invalidateCachedColumns();
231     // We don't really need to recompute our sections, but we need to update our
232     // column count and whether we have a column. Currently, we only have one
233     // size-fit-all flag but we may have to consider splitting it.
234     setNeedsSectionRecalc();
235 }
236
237 void RenderTable::updateLogicalWidth()
238 {
239     recalcSectionsIfNeeded();
240
241     if (isOutOfFlowPositioned()) {
242         LogicalExtentComputedValues computedValues;
243         computePositionedLogicalWidth(computedValues);
244         setLogicalWidth(computedValues.m_extent);
245         setLogicalLeft(computedValues.m_position);
246         setMarginStart(computedValues.m_margins.m_start);
247         setMarginEnd(computedValues.m_margins.m_end);
248     }
249
250     RenderBlock& cb = *containingBlock();
251
252     LayoutUnit availableLogicalWidth = containingBlockLogicalWidthForContent();
253     bool hasPerpendicularContainingBlock = cb.style().isHorizontalWritingMode() != style().isHorizontalWritingMode();
254     LayoutUnit containerWidthInInlineDirection = hasPerpendicularContainingBlock ? perpendicularContainingBlockLogicalHeight() : availableLogicalWidth;
255
256     Length styleLogicalWidth = style().logicalWidth();
257     if ((styleLogicalWidth.isSpecified() && styleLogicalWidth.isPositive()) || styleLogicalWidth.isIntrinsic())
258         setLogicalWidth(convertStyleLogicalWidthToComputedWidth(styleLogicalWidth, containerWidthInInlineDirection));
259     else {
260         // Subtract out any fixed margins from our available width for auto width tables.
261         LayoutUnit marginStart = minimumValueForLength(style().marginStart(), availableLogicalWidth);
262         LayoutUnit marginEnd = minimumValueForLength(style().marginEnd(), availableLogicalWidth);
263         LayoutUnit marginTotal = marginStart + marginEnd;
264
265         // Subtract out our margins to get the available content width.
266         LayoutUnit availableContentLogicalWidth = std::max<LayoutUnit>(0, containerWidthInInlineDirection - marginTotal);
267         if (shrinkToAvoidFloats() && cb.containsFloats() && !hasPerpendicularContainingBlock) {
268             // FIXME: Work with regions someday.
269             availableContentLogicalWidth = shrinkLogicalWidthToAvoidFloats(marginStart, marginEnd, cb, 0);
270         }
271
272         // Ensure we aren't bigger than our available width.
273         setLogicalWidth(std::min(availableContentLogicalWidth, maxPreferredLogicalWidth()));
274         LayoutUnit maxWidth = maxPreferredLogicalWidth();
275         // scaledWidthFromPercentColumns depends on m_layoutStruct in TableLayoutAlgorithmAuto, which
276         // maxPreferredLogicalWidth fills in. So scaledWidthFromPercentColumns has to be called after
277         // maxPreferredLogicalWidth.
278         LayoutUnit scaledWidth = m_tableLayout->scaledWidthFromPercentColumns() + bordersPaddingAndSpacingInRowDirection();
279         maxWidth = std::max(scaledWidth, maxWidth);
280         setLogicalWidth(std::min(availableContentLogicalWidth, maxWidth));
281     }
282
283     // Ensure we aren't smaller than our min preferred width.
284     setLogicalWidth(std::max(logicalWidth(), minPreferredLogicalWidth()));
285
286     
287     // Ensure we aren't bigger than our max-width style.
288     Length styleMaxLogicalWidth = style().logicalMaxWidth();
289     if ((styleMaxLogicalWidth.isSpecified() && !styleMaxLogicalWidth.isNegative()) || styleMaxLogicalWidth.isIntrinsic()) {
290         LayoutUnit computedMaxLogicalWidth = convertStyleLogicalWidthToComputedWidth(styleMaxLogicalWidth, availableLogicalWidth);
291         setLogicalWidth(std::min(logicalWidth(), computedMaxLogicalWidth));
292     }
293
294     // Ensure we aren't smaller than our min-width style.
295     Length styleMinLogicalWidth = style().logicalMinWidth();
296     if ((styleMinLogicalWidth.isSpecified() && !styleMinLogicalWidth.isNegative()) || styleMinLogicalWidth.isIntrinsic()) {
297         LayoutUnit computedMinLogicalWidth = convertStyleLogicalWidthToComputedWidth(styleMinLogicalWidth, availableLogicalWidth);
298         setLogicalWidth(std::max(logicalWidth(), computedMinLogicalWidth));
299     }
300
301     // Finally, with our true width determined, compute our margins for real.
302     setMarginStart(0);
303     setMarginEnd(0);
304     if (!hasPerpendicularContainingBlock) {
305         LayoutUnit containerLogicalWidthForAutoMargins = availableLogicalWidth;
306         if (avoidsFloats() && cb.containsFloats())
307             containerLogicalWidthForAutoMargins = containingBlockAvailableLineWidthInFragment(0); // FIXME: Work with regions someday.
308         ComputedMarginValues marginValues;
309         bool hasInvertedDirection =  cb.style().isLeftToRightDirection() == style().isLeftToRightDirection();
310         computeInlineDirectionMargins(cb, containerLogicalWidthForAutoMargins, logicalWidth(),
311             hasInvertedDirection ? marginValues.m_start : marginValues.m_end,
312             hasInvertedDirection ? marginValues.m_end : marginValues.m_start);
313         setMarginStart(marginValues.m_start);
314         setMarginEnd(marginValues.m_end);
315     } else {
316         setMarginStart(minimumValueForLength(style().marginStart(), availableLogicalWidth));
317         setMarginEnd(minimumValueForLength(style().marginEnd(), availableLogicalWidth));
318     }
319 }
320
321 // This method takes a RenderStyle's logical width, min-width, or max-width length and computes its actual value.
322 LayoutUnit RenderTable::convertStyleLogicalWidthToComputedWidth(const Length& styleLogicalWidth, LayoutUnit availableWidth)
323 {
324     if (styleLogicalWidth.isIntrinsic())
325         return computeIntrinsicLogicalWidthUsing(styleLogicalWidth, availableWidth, bordersPaddingAndSpacingInRowDirection());
326
327     // HTML tables' width styles already include borders and paddings, but CSS tables' width styles do not.
328     LayoutUnit borders;
329     bool isCSSTable = !is<HTMLTableElement>(element());
330     if (isCSSTable && styleLogicalWidth.isSpecified() && styleLogicalWidth.isPositive() && style().boxSizing() == BoxSizing::ContentBox)
331         borders = borderStart() + borderEnd() + (collapseBorders() ? 0_lu : paddingStart() + paddingEnd());
332
333     return minimumValueForLength(styleLogicalWidth, availableWidth) + borders;
334 }
335
336 LayoutUnit RenderTable::convertStyleLogicalHeightToComputedHeight(const Length& styleLogicalHeight)
337 {
338     LayoutUnit borderAndPaddingBefore = borderBefore() + (collapseBorders() ? 0_lu : paddingBefore());
339     LayoutUnit borderAndPaddingAfter = borderAfter() + (collapseBorders() ? 0_lu : paddingAfter());
340     LayoutUnit borderAndPadding = borderAndPaddingBefore + borderAndPaddingAfter;
341     if (styleLogicalHeight.isFixed()) {
342         // HTML tables size as though CSS height includes border/padding, CSS tables do not.
343         LayoutUnit borders;
344         // FIXME: We cannot apply box-sizing: content-box on <table> which other browsers allow.
345         if (is<HTMLTableElement>(element()) || style().boxSizing() == BoxSizing::BorderBox) {
346             borders = borderAndPadding;
347         }
348         return LayoutUnit(styleLogicalHeight.value() - borders);
349     } else if (styleLogicalHeight.isPercentOrCalculated())
350         return computePercentageLogicalHeight(styleLogicalHeight).valueOr(0);
351     else if (styleLogicalHeight.isIntrinsic())
352         return computeIntrinsicLogicalContentHeightUsing(styleLogicalHeight, logicalHeight() - borderAndPadding, borderAndPadding).valueOr(0);
353     else
354         ASSERT_NOT_REACHED();
355     return 0_lu;
356 }
357
358 void RenderTable::layoutCaption(RenderTableCaption& caption)
359 {
360     LayoutRect captionRect(caption.frameRect());
361
362     if (caption.needsLayout()) {
363         // The margins may not be available but ensure the caption is at least located beneath any previous sibling caption
364         // so that it does not mistakenly think any floats in the previous caption intrude into it.
365         caption.setLogicalLocation(LayoutPoint(caption.marginStart(), caption.marginBefore() + logicalHeight()));
366         // If RenderTableCaption ever gets a layout() function, use it here.
367         caption.layoutIfNeeded();
368     }
369     // Apply the margins to the location now that they are definitely available from layout
370     caption.setLogicalLocation(LayoutPoint(caption.marginStart(), caption.marginBefore() + logicalHeight()));
371
372     if (!selfNeedsLayout() && caption.checkForRepaintDuringLayout())
373         caption.repaintDuringLayoutIfMoved(captionRect);
374
375     setLogicalHeight(logicalHeight() + caption.logicalHeight() + caption.marginBefore() + caption.marginAfter());
376 }
377
378 void RenderTable::layoutCaptions(BottomCaptionLayoutPhase bottomCaptionLayoutPhase)
379 {
380     if (m_captions.isEmpty())
381         return;
382     // FIXME: Collapse caption margin.
383     for (unsigned i = 0; i < m_captions.size(); ++i) {
384         if ((bottomCaptionLayoutPhase == BottomCaptionLayoutPhase::Yes && m_captions[i]->style().captionSide() != CaptionSide::Bottom)
385             || (bottomCaptionLayoutPhase == BottomCaptionLayoutPhase::No && m_captions[i]->style().captionSide() == CaptionSide::Bottom))
386             continue;
387         layoutCaption(*m_captions[i]);
388     }
389 }
390
391 void RenderTable::distributeExtraLogicalHeight(LayoutUnit extraLogicalHeight)
392 {
393     if (extraLogicalHeight <= 0)
394         return;
395
396     // FIXME: Distribute the extra logical height between all table sections instead of giving it all to the first one.
397     if (RenderTableSection* section = firstBody())
398         extraLogicalHeight -= section->distributeExtraLogicalHeightToRows(extraLogicalHeight);
399
400     // FIXME: We really would like to enable this ASSERT to ensure that all the extra space has been distributed.
401     // However our current distribution algorithm does not round properly and thus we can have some remaining height.
402     // ASSERT(!topSection() || !extraLogicalHeight);
403 }
404
405 void RenderTable::simplifiedNormalFlowLayout()
406 {
407     layoutCaptions();
408     for (RenderTableSection* section = topSection(); section; section = sectionBelow(section)) {
409         section->layoutIfNeeded();
410         section->computeOverflowFromCells();
411     }
412     layoutCaptions(BottomCaptionLayoutPhase::Yes);
413 }
414
415 void RenderTable::layout()
416 {
417     StackStats::LayoutCheckPoint layoutCheckPoint;
418     ASSERT(needsLayout());
419
420     if (simplifiedLayout())
421         return;
422
423     recalcSectionsIfNeeded();
424     // FIXME: We should do this recalc lazily in borderStart/borderEnd so that we don't have to make sure
425     // to call this before we call borderStart/borderEnd to avoid getting a stale value.
426     recalcBordersInRowDirection();
427     bool sectionMoved = false;
428     LayoutUnit movedSectionLogicalTop;
429
430     LayoutRepainter repainter(*this, checkForRepaintDuringLayout());
431     {
432         LayoutStateMaintainer statePusher(*this, locationOffset(), hasTransform() || hasReflection() || style().isFlippedBlocksWritingMode());
433
434         LayoutUnit oldLogicalWidth = logicalWidth();
435         LayoutUnit oldLogicalHeight = logicalHeight();
436         setLogicalHeight(0);
437         updateLogicalWidth();
438
439         if (logicalWidth() != oldLogicalWidth) {
440             for (unsigned i = 0; i < m_captions.size(); i++)
441                 m_captions[i]->setNeedsLayout(MarkOnlyThis);
442         }
443         // FIXME: The optimisation below doesn't work since the internal table
444         // layout could have changed. We need to add a flag to the table
445         // layout that tells us if something has changed in the min max
446         // calculations to do it correctly.
447         //     if ( oldWidth != width() || columns.size() + 1 != columnPos.size() )
448         m_tableLayout->layout();
449
450         LayoutUnit totalSectionLogicalHeight;
451         LayoutUnit oldTableLogicalTop;
452         for (unsigned i = 0; i < m_captions.size(); i++) {
453             if (m_captions[i]->style().captionSide() == CaptionSide::Bottom)
454                 continue;
455             oldTableLogicalTop += m_captions[i]->logicalHeight() + m_captions[i]->marginBefore() + m_captions[i]->marginAfter();
456         }
457
458         bool collapsing = collapseBorders();
459
460         for (auto& child : childrenOfType<RenderElement>(*this)) {
461             if (is<RenderTableSection>(child)) {
462                 RenderTableSection& section = downcast<RenderTableSection>(child);
463                 if (m_columnLogicalWidthChanged)
464                     section.setChildNeedsLayout(MarkOnlyThis);
465                 section.layoutIfNeeded();
466                 totalSectionLogicalHeight += section.calcRowLogicalHeight();
467                 if (collapsing)
468                     section.recalcOuterBorder();
469                 ASSERT(!section.needsLayout());
470             } else if (is<RenderTableCol>(child)) {
471                 downcast<RenderTableCol>(child).layoutIfNeeded();
472                 ASSERT(!child.needsLayout());
473             }
474         }
475
476         // If any table section moved vertically, we will just repaint everything from that
477         // section down (it is quite unlikely that any of the following sections
478         // did not shift).
479         layoutCaptions();
480         if (!m_captions.isEmpty() && logicalHeight() != oldTableLogicalTop) {
481             sectionMoved = true;
482             movedSectionLogicalTop = std::min(logicalHeight(), oldTableLogicalTop);
483         }
484
485         LayoutUnit borderAndPaddingBefore = borderBefore() + (collapsing ? 0_lu : paddingBefore());
486         LayoutUnit borderAndPaddingAfter = borderAfter() + (collapsing ? 0_lu : paddingAfter());
487
488         setLogicalHeight(logicalHeight() + borderAndPaddingBefore);
489
490         if (!isOutOfFlowPositioned())
491             updateLogicalHeight();
492
493         LayoutUnit computedLogicalHeight;
494     
495         Length logicalHeightLength = style().logicalHeight();
496         if (logicalHeightLength.isIntrinsic() || (logicalHeightLength.isSpecified() && logicalHeightLength.isPositive()))
497             computedLogicalHeight = convertStyleLogicalHeightToComputedHeight(logicalHeightLength);
498
499         Length logicalMaxHeightLength = style().logicalMaxHeight();
500         if (logicalMaxHeightLength.isIntrinsic() || (logicalMaxHeightLength.isSpecified() && !logicalMaxHeightLength.isNegative())) {
501             LayoutUnit computedMaxLogicalHeight = convertStyleLogicalHeightToComputedHeight(logicalMaxHeightLength);
502             computedLogicalHeight = std::min(computedLogicalHeight, computedMaxLogicalHeight);
503         }
504
505         Length logicalMinHeightLength = style().logicalMinHeight();
506         if (logicalMinHeightLength.isIntrinsic() || (logicalMinHeightLength.isSpecified() && !logicalMinHeightLength.isNegative())) {
507             LayoutUnit computedMinLogicalHeight = convertStyleLogicalHeightToComputedHeight(logicalMinHeightLength);
508             computedLogicalHeight = std::max(computedLogicalHeight, computedMinLogicalHeight);
509         }
510
511         distributeExtraLogicalHeight(computedLogicalHeight - totalSectionLogicalHeight);
512
513         for (RenderTableSection* section = topSection(); section; section = sectionBelow(section))
514             section->layoutRows();
515
516         if (!topSection() && computedLogicalHeight > totalSectionLogicalHeight && !document().inQuirksMode()) {
517             // Completely empty tables (with no sections or anything) should at least honor specified height
518             // in strict mode.
519             setLogicalHeight(logicalHeight() + computedLogicalHeight);
520         }
521
522         LayoutUnit sectionLogicalLeft = style().isLeftToRightDirection() ? borderStart() : borderEnd();
523         if (!collapsing)
524             sectionLogicalLeft += style().isLeftToRightDirection() ? paddingStart() : paddingEnd();
525
526         // position the table sections
527         RenderTableSection* section = topSection();
528         while (section) {
529             if (!sectionMoved && section->logicalTop() != logicalHeight()) {
530                 sectionMoved = true;
531                 movedSectionLogicalTop = std::min(logicalHeight(), section->logicalTop()) + (style().isHorizontalWritingMode() ? section->visualOverflowRect().y() : section->visualOverflowRect().x());
532             }
533             section->setLogicalLocation(LayoutPoint(sectionLogicalLeft, logicalHeight()));
534
535             setLogicalHeight(logicalHeight() + section->logicalHeight());
536             section = sectionBelow(section);
537         }
538
539         setLogicalHeight(logicalHeight() + borderAndPaddingAfter);
540
541         layoutCaptions(BottomCaptionLayoutPhase::Yes);
542
543         if (isOutOfFlowPositioned())
544             updateLogicalHeight();
545
546         // table can be containing block of positioned elements.
547         bool dimensionChanged = oldLogicalWidth != logicalWidth() || oldLogicalHeight != logicalHeight();
548         layoutPositionedObjects(dimensionChanged);
549
550         updateLayerTransform();
551
552         // Layout was changed, so probably borders too.
553         invalidateCollapsedBorders();
554
555         // The location or height of one or more sections may have changed.
556         invalidateCachedColumnOffsets();
557
558         computeOverflow(clientLogicalBottom());
559     }
560
561     auto* layoutState = view().frameView().layoutContext().layoutState();
562     if (layoutState->pageLogicalHeight())
563         setPageLogicalOffset(layoutState->pageLogicalOffset(this, logicalTop()));
564
565     bool didFullRepaint = repainter.repaintAfterLayout();
566     // Repaint with our new bounds if they are different from our old bounds.
567     if (!didFullRepaint && sectionMoved) {
568         if (style().isHorizontalWritingMode())
569             repaintRectangle(LayoutRect(visualOverflowRect().x(), movedSectionLogicalTop, visualOverflowRect().width(), visualOverflowRect().maxY() - movedSectionLogicalTop));
570         else
571             repaintRectangle(LayoutRect(movedSectionLogicalTop, visualOverflowRect().y(), visualOverflowRect().maxX() - movedSectionLogicalTop, visualOverflowRect().height()));
572     }
573
574     bool paginated = layoutState && layoutState->isPaginated();
575     if (sectionMoved && paginated) {
576         // FIXME: Table layout should always stabilize even when section moves (see webkit.org/b/174412).
577         if (!m_inRecursiveSectionMovedWithPagination) {
578             SetForScope<bool> paginatedSectionMoved(m_inRecursiveSectionMovedWithPagination, true);
579             markForPaginationRelayoutIfNeeded();
580             layoutIfNeeded();
581         } else
582             ASSERT_NOT_REACHED();
583     }
584     
585     // FIXME: This value isn't the intrinsic content logical height, but we need
586     // to update the value as its used by flexbox layout. crbug.com/367324
587     cacheIntrinsicContentLogicalHeightForFlexItem(contentLogicalHeight());
588     
589     m_columnLogicalWidthChanged = false;
590     clearNeedsLayout();
591 }
592
593 void RenderTable::invalidateCollapsedBorders(RenderTableCell* cellWithStyleChange)
594 {
595     m_collapsedBordersValid = false;
596     m_collapsedBorders.clear();
597
598     for (auto& section : childrenOfType<RenderTableSection>(*this))
599         section.clearCachedCollapsedBorders();
600
601     if (!m_collapsedEmptyBorderIsPresent)
602         return;
603
604     if (cellWithStyleChange) {
605         // It is enough to invalidate just the surrounding cells when cell border style changes.
606         cellWithStyleChange->invalidateHasEmptyCollapsedBorders();
607         if (auto* below = cellBelow(cellWithStyleChange))
608             below->invalidateHasEmptyCollapsedBorders();
609         if (auto* above = cellAbove(cellWithStyleChange))
610             above->invalidateHasEmptyCollapsedBorders();
611         if (auto* before = cellBefore(cellWithStyleChange))
612             before->invalidateHasEmptyCollapsedBorders();
613         if (auto* after = cellAfter(cellWithStyleChange))
614             after->invalidateHasEmptyCollapsedBorders();
615         return;
616     }
617
618     for (auto& section : childrenOfType<RenderTableSection>(*this)) {
619         for (auto* row = section.firstRow(); row; row = row->nextRow()) {
620             for (auto* cell = row->firstCell(); cell; cell = cell->nextCell()) {
621                 ASSERT(cell->table() == this);
622                 cell->invalidateHasEmptyCollapsedBorders();
623             }
624         }
625     }
626     m_collapsedEmptyBorderIsPresent = false;
627 }
628
629 // Collect all the unique border values that we want to paint in a sorted list.
630 void RenderTable::recalcCollapsedBorders()
631 {
632     if (m_collapsedBordersValid)
633         return;
634     m_collapsedBorders.clear();
635     for (auto& section : childrenOfType<RenderTableSection>(*this)) {
636         for (RenderTableRow* row = section.firstRow(); row; row = row->nextRow()) {
637             for (RenderTableCell* cell = row->firstCell(); cell; cell = cell->nextCell()) {
638                 ASSERT(cell->table() == this);
639                 cell->collectBorderValues(m_collapsedBorders);
640             }
641         }
642     }
643     RenderTableCell::sortBorderValues(m_collapsedBorders);
644     m_collapsedBordersValid = true;
645 }
646
647 void RenderTable::addOverflowFromChildren()
648 {
649     // Add overflow from borders.
650     // Technically it's odd that we are incorporating the borders into layout overflow, which is only supposed to be about overflow from our
651     // descendant objects, but since tables don't support overflow:auto, this works out fine.
652     if (collapseBorders()) {
653         LayoutUnit rightBorderOverflow = width() + outerBorderRight() - borderRight();
654         LayoutUnit leftBorderOverflow = borderLeft() - outerBorderLeft();
655         LayoutUnit bottomBorderOverflow = height() + outerBorderBottom() - borderBottom();
656         LayoutUnit topBorderOverflow = borderTop() - outerBorderTop();
657         LayoutRect borderOverflowRect(leftBorderOverflow, topBorderOverflow, rightBorderOverflow - leftBorderOverflow, bottomBorderOverflow - topBorderOverflow);
658         if (borderOverflowRect != borderBoxRect()) {
659             addLayoutOverflow(borderOverflowRect);
660             addVisualOverflow(borderOverflowRect);
661         }
662     }
663
664     // Add overflow from our caption.
665     for (unsigned i = 0; i < m_captions.size(); i++) 
666         addOverflowFromChild(m_captions[i].get());
667
668     // Add overflow from our sections.
669     for (RenderTableSection* section = topSection(); section; section = sectionBelow(section))
670         addOverflowFromChild(section);
671 }
672
673 void RenderTable::paint(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
674 {
675     LayoutPoint adjustedPaintOffset = paintOffset + location();
676
677     PaintPhase paintPhase = paintInfo.phase;
678
679     if (!isDocumentElementRenderer()) {
680         LayoutRect overflowBox = visualOverflowRect();
681         flipForWritingMode(overflowBox);
682         overflowBox.moveBy(adjustedPaintOffset);
683         if (!overflowBox.intersects(paintInfo.rect))
684             return;
685     }
686
687     bool pushedClip = pushContentsClip(paintInfo, adjustedPaintOffset);
688     paintObject(paintInfo, adjustedPaintOffset);
689     if (pushedClip)
690         popContentsClip(paintInfo, paintPhase, adjustedPaintOffset);
691 }
692
693 void RenderTable::paintObject(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
694 {
695     PaintPhase paintPhase = paintInfo.phase;
696     if ((paintPhase == PaintPhase::BlockBackground || paintPhase == PaintPhase::ChildBlockBackground) && hasVisibleBoxDecorations() && style().visibility() == Visibility::Visible)
697         paintBoxDecorations(paintInfo, paintOffset);
698
699     if (paintPhase == PaintPhase::Mask) {
700         paintMask(paintInfo, paintOffset);
701         return;
702     }
703
704     // We're done.  We don't bother painting any children.
705     if (paintPhase == PaintPhase::BlockBackground)
706         return;
707     
708     // We don't paint our own background, but we do let the kids paint their backgrounds.
709     if (paintPhase == PaintPhase::ChildBlockBackgrounds)
710         paintPhase = PaintPhase::ChildBlockBackground;
711
712     PaintInfo info(paintInfo);
713     info.phase = paintPhase;
714     info.updateSubtreePaintRootForChildren(this);
715
716     for (auto& box : childrenOfType<RenderBox>(*this)) {
717         if (!box.hasSelfPaintingLayer() && (box.isTableSection() || box.isTableCaption())) {
718             LayoutPoint childPoint = flipForWritingModeForChild(&box, paintOffset);
719             box.paint(info, childPoint);
720         }
721     }
722     
723     if (collapseBorders() && paintPhase == PaintPhase::ChildBlockBackground && style().visibility() == Visibility::Visible) {
724         recalcCollapsedBorders();
725         // Using our cached sorted styles, we then do individual passes,
726         // painting each style of border from lowest precedence to highest precedence.
727         info.phase = PaintPhase::CollapsedTableBorders;
728         size_t count = m_collapsedBorders.size();
729         for (size_t i = 0; i < count; ++i) {
730             m_currentBorder = &m_collapsedBorders[i];
731             for (RenderTableSection* section = bottomSection(); section; section = sectionAbove(section)) {
732                 LayoutPoint childPoint = flipForWritingModeForChild(section, paintOffset);
733                 section->paint(info, childPoint);
734             }
735         }
736         m_currentBorder = 0;
737     }
738
739     // Paint outline.
740     if ((paintPhase == PaintPhase::Outline || paintPhase == PaintPhase::SelfOutline) && hasOutline() && style().visibility() == Visibility::Visible)
741         paintOutline(paintInfo, LayoutRect(paintOffset, size()));
742 }
743
744 void RenderTable::adjustBorderBoxRectForPainting(LayoutRect& rect)
745 {
746     for (unsigned i = 0; i < m_captions.size(); i++) {
747         LayoutUnit captionLogicalHeight = m_captions[i]->logicalHeight() + m_captions[i]->marginBefore() + m_captions[i]->marginAfter();
748         bool captionIsBefore = (m_captions[i]->style().captionSide() != CaptionSide::Bottom) ^ style().isFlippedBlocksWritingMode();
749         if (style().isHorizontalWritingMode()) {
750             rect.setHeight(rect.height() - captionLogicalHeight);
751             if (captionIsBefore)
752                 rect.move(0_lu, captionLogicalHeight);
753         } else {
754             rect.setWidth(rect.width() - captionLogicalHeight);
755             if (captionIsBefore)
756                 rect.move(captionLogicalHeight, 0_lu);
757         }
758     }
759     
760     RenderBlock::adjustBorderBoxRectForPainting(rect);
761 }
762
763 void RenderTable::paintBoxDecorations(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
764 {
765     if (!paintInfo.shouldPaintWithinRoot(*this))
766         return;
767
768     LayoutRect rect(paintOffset, size());
769     adjustBorderBoxRectForPainting(rect);
770     
771     BackgroundBleedAvoidance bleedAvoidance = determineBackgroundBleedAvoidance(paintInfo.context());
772     if (!boxShadowShouldBeAppliedToBackground(rect.location(), bleedAvoidance))
773         paintBoxShadow(paintInfo, rect, style(), Normal);
774     paintBackground(paintInfo, rect, bleedAvoidance);
775     paintBoxShadow(paintInfo, rect, style(), Inset);
776
777     if (style().hasVisibleBorderDecoration() && !collapseBorders())
778         paintBorder(paintInfo, rect, style());
779 }
780
781 void RenderTable::paintMask(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
782 {
783     if (style().visibility() != Visibility::Visible || paintInfo.phase != PaintPhase::Mask)
784         return;
785
786     LayoutRect rect(paintOffset, size());
787     adjustBorderBoxRectForPainting(rect);
788
789     paintMaskImages(paintInfo, rect);
790 }
791
792 void RenderTable::computeIntrinsicLogicalWidths(LayoutUnit& minWidth, LayoutUnit& maxWidth) const
793 {
794     recalcSectionsIfNeeded();
795     // FIXME: Do the recalc in borderStart/borderEnd and make those const_cast this call.
796     // Then m_borderStart/m_borderEnd will be transparent a cache and it removes the possibility
797     // of reading out stale values.
798     const_cast<RenderTable*>(this)->recalcBordersInRowDirection();
799     // FIXME: Restructure the table layout code so that we can make this method const.
800     const_cast<RenderTable*>(this)->m_tableLayout->computeIntrinsicLogicalWidths(minWidth, maxWidth);
801
802     // FIXME: We should include captions widths here like we do in computePreferredLogicalWidths.
803 }
804
805 void RenderTable::computePreferredLogicalWidths()
806 {
807     ASSERT(preferredLogicalWidthsDirty());
808
809     computeIntrinsicLogicalWidths(m_minPreferredLogicalWidth, m_maxPreferredLogicalWidth);
810
811     LayoutUnit bordersPaddingAndSpacing = bordersPaddingAndSpacingInRowDirection();
812     m_minPreferredLogicalWidth += bordersPaddingAndSpacing;
813     m_maxPreferredLogicalWidth += bordersPaddingAndSpacing;
814
815     m_tableLayout->applyPreferredLogicalWidthQuirks(m_minPreferredLogicalWidth, m_maxPreferredLogicalWidth);
816
817     for (unsigned i = 0; i < m_captions.size(); i++)
818         m_minPreferredLogicalWidth = std::max(m_minPreferredLogicalWidth, m_captions[i]->minPreferredLogicalWidth());
819
820     auto& styleToUse = style();
821     // FIXME: This should probably be checking for isSpecified since you should be able to use percentage or calc values for min-width.
822     if (styleToUse.logicalMinWidth().isFixed() && styleToUse.logicalMinWidth().value() > 0) {
823         m_maxPreferredLogicalWidth = std::max(m_maxPreferredLogicalWidth, adjustContentBoxLogicalWidthForBoxSizing(styleToUse.logicalMinWidth().value()));
824         m_minPreferredLogicalWidth = std::max(m_minPreferredLogicalWidth, adjustContentBoxLogicalWidthForBoxSizing(styleToUse.logicalMinWidth().value()));
825     }
826
827     // FIXME: This should probably be checking for isSpecified since you should be able to use percentage or calc values for maxWidth.
828     if (styleToUse.logicalMaxWidth().isFixed()) {
829         m_maxPreferredLogicalWidth = std::min(m_maxPreferredLogicalWidth, adjustContentBoxLogicalWidthForBoxSizing(styleToUse.logicalMaxWidth().value()));
830         m_minPreferredLogicalWidth = std::min(m_minPreferredLogicalWidth, adjustContentBoxLogicalWidthForBoxSizing(styleToUse.logicalMaxWidth().value()));
831     }
832
833     // FIXME: We should be adding borderAndPaddingLogicalWidth here, but m_tableLayout->computePreferredLogicalWidths already does,
834     // so a bunch of tests break doing this naively.
835     setPreferredLogicalWidthsDirty(false);
836 }
837
838 RenderTableSection* RenderTable::topNonEmptySection() const
839 {
840     RenderTableSection* section = topSection();
841     if (section && !section->numRows())
842         section = sectionBelow(section, SkipEmptySections);
843     return section;
844 }
845
846 void RenderTable::splitColumn(unsigned position, unsigned firstSpan)
847 {
848     // We split the column at "position", taking "firstSpan" cells from the span.
849     ASSERT(m_columns[position].span > firstSpan);
850     m_columns.insert(position, ColumnStruct(firstSpan));
851     m_columns[position + 1].span -= firstSpan;
852
853     // Propagate the change in our columns representation to the sections that don't need
854     // cell recalc. If they do, they will be synced up directly with m_columns later.
855     for (auto& section : childrenOfType<RenderTableSection>(*this)) {
856         if (section.needsCellRecalc())
857             continue;
858
859         section.splitColumn(position, firstSpan);
860     }
861
862     m_columnPos.grow(numEffCols() + 1);
863 }
864
865 void RenderTable::appendColumn(unsigned span)
866 {
867     unsigned newColumnIndex = m_columns.size();
868     m_columns.append(ColumnStruct(span));
869
870     // Unless the table has cell(s) with colspan that exceed the number of columns afforded
871     // by the other rows in the table we can use the fast path when mapping columns to effective columns.
872     m_hasCellColspanThatDeterminesTableWidth = m_hasCellColspanThatDeterminesTableWidth || span > 1;
873
874     // Propagate the change in our columns representation to the sections that don't need
875     // cell recalc. If they do, they will be synced up directly with m_columns later.
876     for (auto& section : childrenOfType<RenderTableSection>(*this)) {
877         if (section.needsCellRecalc())
878             continue;
879
880         section.appendColumn(newColumnIndex);
881     }
882
883     m_columnPos.grow(numEffCols() + 1);
884 }
885
886 RenderTableCol* RenderTable::firstColumn() const
887 {
888     for (auto& child : childrenOfType<RenderObject>(*this)) {
889         if (is<RenderTableCol>(child))
890             return &const_cast<RenderTableCol&>(downcast<RenderTableCol>(child));
891
892         // We allow only table-captions before columns or column-groups.
893         if (!is<RenderTableCaption>(child))
894             return nullptr;
895     }
896
897     return nullptr;
898 }
899
900 void RenderTable::updateColumnCache() const
901 {
902     ASSERT(m_hasColElements);
903     ASSERT(m_columnRenderers.isEmpty());
904     ASSERT(m_effectiveColumnIndexMap.isEmpty());
905     ASSERT(!m_columnRenderersValid);
906
907     unsigned columnIndex = 0;
908     for (RenderTableCol* columnRenderer = firstColumn(); columnRenderer; columnRenderer = columnRenderer->nextColumn()) {
909         if (columnRenderer->isTableColumnGroupWithColumnChildren())
910             continue;
911         m_columnRenderers.append(makeWeakPtr(columnRenderer));
912         // FIXME: We should look to compute the effective column index successively from previous values instead of
913         // calling colToEffCol(), which is in O(numEffCols()). Although it's unlikely that this is a hot function.
914         m_effectiveColumnIndexMap.add(columnRenderer, colToEffCol(columnIndex));
915         columnIndex += columnRenderer->span();
916     }
917     m_columnRenderersValid = true;
918 }
919
920 unsigned RenderTable::effectiveIndexOfColumn(const RenderTableCol& column) const
921 {
922     if (!m_columnRenderersValid)
923         updateColumnCache();
924     const RenderTableCol* columnToUse = &column;
925     if (columnToUse->isTableColumnGroupWithColumnChildren())
926         columnToUse = columnToUse->nextColumn(); // First column in column-group
927     auto it = m_effectiveColumnIndexMap.find(columnToUse);
928     ASSERT(it != m_effectiveColumnIndexMap.end());
929     if (it == m_effectiveColumnIndexMap.end())
930         return std::numeric_limits<unsigned>::max();
931     return it->value;
932 }
933
934 LayoutUnit RenderTable::offsetTopForColumn(const RenderTableCol& column) const
935 {
936     if (effectiveIndexOfColumn(column) >= numEffCols())
937         return 0;
938     if (m_columnOffsetTop >= 0) {
939         ASSERT(!needsLayout());
940         return m_columnOffsetTop;
941     }
942     RenderTableSection* section = topNonEmptySection();
943     return m_columnOffsetTop = section ? section->offsetTop() : 0_lu;
944 }
945
946 LayoutUnit RenderTable::offsetLeftForColumn(const RenderTableCol& column) const
947 {
948     unsigned columnIndex = effectiveIndexOfColumn(column);
949     if (columnIndex >= numEffCols())
950         return 0;
951     return m_columnPos[columnIndex] + m_hSpacing + borderLeft();
952 }
953
954 LayoutUnit RenderTable::offsetWidthForColumn(const RenderTableCol& column) const
955 {
956     const RenderTableCol* currentColumn = &column;
957     bool hasColumnChildren;
958     if ((hasColumnChildren = currentColumn->isTableColumnGroupWithColumnChildren()))
959         currentColumn = currentColumn->nextColumn(); // First column in column-group
960     unsigned numberOfEffectiveColumns = numEffCols();
961     ASSERT_WITH_SECURITY_IMPLICATION(m_columnPos.size() >= numberOfEffectiveColumns + 1);
962     LayoutUnit width;
963     LayoutUnit spacing = m_hSpacing;
964     while (currentColumn) {
965         unsigned columnIndex = effectiveIndexOfColumn(*currentColumn);
966         unsigned span = currentColumn->span();
967         while (span && columnIndex < numberOfEffectiveColumns) {
968             width += m_columnPos[columnIndex + 1] - m_columnPos[columnIndex] - spacing;
969             span -= m_columns[columnIndex].span;
970             ++columnIndex;
971             if (span)
972                 width += spacing;
973         }
974         if (!hasColumnChildren)
975             break;
976         currentColumn = currentColumn->nextColumn();
977         if (!currentColumn || currentColumn->isTableColumnGroup())
978             break;
979         width += spacing;
980     }
981     return width;
982 }
983
984 LayoutUnit RenderTable::offsetHeightForColumn(const RenderTableCol& column) const
985 {
986     if (effectiveIndexOfColumn(column) >= numEffCols())
987         return 0;
988     if (m_columnOffsetHeight >= 0) {
989         ASSERT(!needsLayout());
990         return m_columnOffsetHeight;
991     }
992     LayoutUnit height;
993     for (RenderTableSection* section = topSection(); section; section = sectionBelow(section))
994         height += section->offsetHeight();
995     m_columnOffsetHeight = height;
996     return m_columnOffsetHeight;
997 }
998
999 RenderTableCol* RenderTable::slowColElement(unsigned col, bool* startEdge, bool* endEdge) const
1000 {
1001     ASSERT(m_hasColElements);
1002
1003     if (!m_columnRenderersValid)
1004         updateColumnCache();
1005
1006     unsigned columnCount = 0;
1007     for (auto& columnRenderer : m_columnRenderers) {
1008         if (!columnRenderer)
1009             continue;
1010         unsigned span = columnRenderer->span();
1011         unsigned startCol = columnCount;
1012         ASSERT(span >= 1);
1013         unsigned endCol = columnCount + span - 1;
1014         columnCount += span;
1015         if (columnCount > col) {
1016             if (startEdge)
1017                 *startEdge = startCol == col;
1018             if (endEdge)
1019                 *endEdge = endCol == col;
1020             return columnRenderer.get();
1021         }
1022     }
1023     return nullptr;
1024 }
1025
1026 void RenderTable::recalcSections() const
1027 {
1028     ASSERT(m_needsSectionRecalc);
1029
1030     m_head.clear();
1031     m_foot.clear();
1032     m_firstBody.clear();
1033     m_hasColElements = false;
1034     m_hasCellColspanThatDeterminesTableWidth = hasCellColspanThatDeterminesTableWidth();
1035
1036     // We need to get valid pointers to caption, head, foot and first body again
1037     RenderObject* nextSibling;
1038     for (RenderObject* child = firstChild(); child; child = nextSibling) {
1039         nextSibling = child->nextSibling();
1040         switch (child->style().display()) {
1041         case DisplayType::TableColumn:
1042         case DisplayType::TableColumnGroup:
1043             m_hasColElements = true;
1044             break;
1045         case DisplayType::TableHeaderGroup:
1046             if (is<RenderTableSection>(*child)) {
1047                 RenderTableSection& section = downcast<RenderTableSection>(*child);
1048                 if (!m_head)
1049                     m_head = makeWeakPtr(section);
1050                 else if (!m_firstBody)
1051                     m_firstBody = makeWeakPtr(section);
1052                 section.recalcCellsIfNeeded();
1053             }
1054             break;
1055         case DisplayType::TableFooterGroup:
1056             if (is<RenderTableSection>(*child)) {
1057                 RenderTableSection& section = downcast<RenderTableSection>(*child);
1058                 if (!m_foot)
1059                     m_foot = makeWeakPtr(section);
1060                 else if (!m_firstBody)
1061                     m_firstBody = makeWeakPtr(section);
1062                 section.recalcCellsIfNeeded();
1063             }
1064             break;
1065         case DisplayType::TableRowGroup:
1066             if (is<RenderTableSection>(*child)) {
1067                 RenderTableSection& section = downcast<RenderTableSection>(*child);
1068                 if (!m_firstBody)
1069                     m_firstBody = makeWeakPtr(section);
1070                 section.recalcCellsIfNeeded();
1071             }
1072             break;
1073         default:
1074             break;
1075         }
1076     }
1077
1078     // repair column count (addChild can grow it too much, because it always adds elements to the last row of a section)
1079     unsigned maxCols = 0;
1080     for (auto& section : childrenOfType<RenderTableSection>(*this)) {
1081         unsigned sectionCols = section.numColumns();
1082         if (sectionCols > maxCols)
1083             maxCols = sectionCols;
1084     }
1085     
1086     m_columns.resize(maxCols);
1087     m_columnPos.resize(maxCols + 1);
1088
1089     // Now that we know the number of maximum number of columns, let's shrink the sections grids if needed.
1090     for (auto& section : childrenOfType<RenderTableSection>(const_cast<RenderTable&>(*this)))
1091         section.removeRedundantColumns();
1092
1093     ASSERT(selfNeedsLayout());
1094
1095     m_needsSectionRecalc = false;
1096 }
1097
1098 LayoutUnit RenderTable::calcBorderStart() const
1099 {
1100     if (!collapseBorders())
1101         return RenderBlock::borderStart();
1102
1103     // Determined by the first cell of the first row. See the CSS 2.1 spec, section 17.6.2.
1104     if (!numEffCols())
1105         return 0;
1106
1107     float borderWidth = 0;
1108
1109     const BorderValue& tableStartBorder = style().borderStart();
1110     if (tableStartBorder.style() == BorderStyle::Hidden)
1111         return 0;
1112     if (tableStartBorder.style() > BorderStyle::Hidden)
1113         borderWidth = tableStartBorder.width();
1114
1115     if (RenderTableCol* column = colElement(0)) {
1116         // FIXME: We don't account for direction on columns and column groups.
1117         const BorderValue& columnAdjoiningBorder = column->style().borderStart();
1118         if (columnAdjoiningBorder.style() == BorderStyle::Hidden)
1119             return 0;
1120         if (columnAdjoiningBorder.style() > BorderStyle::Hidden)
1121             borderWidth = std::max(borderWidth, columnAdjoiningBorder.width());
1122         // FIXME: This logic doesn't properly account for the first column in the first column-group case.
1123     }
1124
1125     if (const RenderTableSection* topNonEmptySection = this->topNonEmptySection()) {
1126         const BorderValue& sectionAdjoiningBorder = topNonEmptySection->borderAdjoiningTableStart();
1127         if (sectionAdjoiningBorder.style() == BorderStyle::Hidden)
1128             return 0;
1129
1130         if (sectionAdjoiningBorder.style() > BorderStyle::Hidden)
1131             borderWidth = std::max(borderWidth, sectionAdjoiningBorder.width());
1132
1133         if (const RenderTableCell* adjoiningStartCell = topNonEmptySection->firstRowCellAdjoiningTableStart()) {
1134             // FIXME: Make this work with perpendicular and flipped cells.
1135             const BorderValue& startCellAdjoiningBorder = adjoiningStartCell->borderAdjoiningTableStart();
1136             if (startCellAdjoiningBorder.style() == BorderStyle::Hidden)
1137                 return 0;
1138
1139             const BorderValue& firstRowAdjoiningBorder = adjoiningStartCell->row()->borderAdjoiningTableStart();
1140             if (firstRowAdjoiningBorder.style() == BorderStyle::Hidden)
1141                 return 0;
1142
1143             if (startCellAdjoiningBorder.style() > BorderStyle::Hidden)
1144                 borderWidth = std::max(borderWidth, startCellAdjoiningBorder.width());
1145             if (firstRowAdjoiningBorder.style() > BorderStyle::Hidden)
1146                 borderWidth = std::max(borderWidth, firstRowAdjoiningBorder.width());
1147         }
1148     }
1149     return CollapsedBorderValue::adjustedCollapsedBorderWidth(borderWidth, document().deviceScaleFactor(), !style().isLeftToRightDirection());
1150 }
1151
1152 LayoutUnit RenderTable::calcBorderEnd() const
1153 {
1154     if (!collapseBorders())
1155         return RenderBlock::borderEnd();
1156
1157     // Determined by the last cell of the first row. See the CSS 2.1 spec, section 17.6.2.
1158     if (!numEffCols())
1159         return 0;
1160
1161     float borderWidth = 0;
1162
1163     const BorderValue& tableEndBorder = style().borderEnd();
1164     if (tableEndBorder.style() == BorderStyle::Hidden)
1165         return 0;
1166     if (tableEndBorder.style() > BorderStyle::Hidden)
1167         borderWidth = tableEndBorder.width();
1168
1169     unsigned endColumn = numEffCols() - 1;
1170     if (RenderTableCol* column = colElement(endColumn)) {
1171         // FIXME: We don't account for direction on columns and column groups.
1172         const BorderValue& columnAdjoiningBorder = column->style().borderEnd();
1173         if (columnAdjoiningBorder.style() == BorderStyle::Hidden)
1174             return 0;
1175         if (columnAdjoiningBorder.style() > BorderStyle::Hidden)
1176             borderWidth = std::max(borderWidth, columnAdjoiningBorder.width());
1177         // FIXME: This logic doesn't properly account for the last column in the last column-group case.
1178     }
1179
1180     if (const RenderTableSection* topNonEmptySection = this->topNonEmptySection()) {
1181         const BorderValue& sectionAdjoiningBorder = topNonEmptySection->borderAdjoiningTableEnd();
1182         if (sectionAdjoiningBorder.style() == BorderStyle::Hidden)
1183             return 0;
1184
1185         if (sectionAdjoiningBorder.style() > BorderStyle::Hidden)
1186             borderWidth = std::max(borderWidth, sectionAdjoiningBorder.width());
1187
1188         if (const RenderTableCell* adjoiningEndCell = topNonEmptySection->firstRowCellAdjoiningTableEnd()) {
1189             // FIXME: Make this work with perpendicular and flipped cells.
1190             const BorderValue& endCellAdjoiningBorder = adjoiningEndCell->borderAdjoiningTableEnd();
1191             if (endCellAdjoiningBorder.style() == BorderStyle::Hidden)
1192                 return 0;
1193
1194             const BorderValue& firstRowAdjoiningBorder = adjoiningEndCell->row()->borderAdjoiningTableEnd();
1195             if (firstRowAdjoiningBorder.style() == BorderStyle::Hidden)
1196                 return 0;
1197
1198             if (endCellAdjoiningBorder.style() > BorderStyle::Hidden)
1199                 borderWidth = std::max(borderWidth, endCellAdjoiningBorder.width());
1200             if (firstRowAdjoiningBorder.style() > BorderStyle::Hidden)
1201                 borderWidth = std::max(borderWidth, firstRowAdjoiningBorder.width());
1202         }
1203     }
1204     return CollapsedBorderValue::adjustedCollapsedBorderWidth(borderWidth, document().deviceScaleFactor(), style().isLeftToRightDirection());
1205 }
1206
1207 void RenderTable::recalcBordersInRowDirection()
1208 {
1209     // FIXME: We need to compute the collapsed before / after borders in the same fashion.
1210     m_borderStart = calcBorderStart();
1211     m_borderEnd = calcBorderEnd();
1212 }
1213
1214 LayoutUnit RenderTable::borderBefore() const
1215 {
1216     if (collapseBorders()) {
1217         recalcSectionsIfNeeded();
1218         return outerBorderBefore();
1219     }
1220     return RenderBlock::borderBefore();
1221 }
1222
1223 LayoutUnit RenderTable::borderAfter() const
1224 {
1225     if (collapseBorders()) {
1226         recalcSectionsIfNeeded();
1227         return outerBorderAfter();
1228     }
1229     return RenderBlock::borderAfter();
1230 }
1231
1232 LayoutUnit RenderTable::outerBorderBefore() const
1233 {
1234     if (!collapseBorders())
1235         return 0;
1236     LayoutUnit borderWidth;
1237     if (RenderTableSection* topSection = this->topSection()) {
1238         borderWidth = topSection->outerBorderBefore();
1239         if (borderWidth < 0)
1240             return 0;   // Overridden by hidden
1241     }
1242     const BorderValue& tb = style().borderBefore();
1243     if (tb.style() == BorderStyle::Hidden)
1244         return 0;
1245     if (tb.style() > BorderStyle::Hidden) {
1246         LayoutUnit collapsedBorderWidth = std::max(borderWidth, LayoutUnit(tb.width() / 2));
1247         borderWidth = floorToDevicePixel(collapsedBorderWidth, document().deviceScaleFactor());
1248     }
1249     return borderWidth;
1250 }
1251
1252 LayoutUnit RenderTable::outerBorderAfter() const
1253 {
1254     if (!collapseBorders())
1255         return 0;
1256     LayoutUnit borderWidth;
1257
1258     if (RenderTableSection* section = bottomSection()) {
1259         borderWidth = section->outerBorderAfter();
1260         if (borderWidth < 0)
1261             return 0; // Overridden by hidden
1262     }
1263     const BorderValue& tb = style().borderAfter();
1264     if (tb.style() == BorderStyle::Hidden)
1265         return 0;
1266     if (tb.style() > BorderStyle::Hidden) {
1267         float deviceScaleFactor = document().deviceScaleFactor();
1268         LayoutUnit collapsedBorderWidth = std::max(borderWidth, LayoutUnit((tb.width() + (1 / deviceScaleFactor)) / 2));
1269         borderWidth = floorToDevicePixel(collapsedBorderWidth, deviceScaleFactor);
1270     }
1271     return borderWidth;
1272 }
1273
1274 LayoutUnit RenderTable::outerBorderStart() const
1275 {
1276     if (!collapseBorders())
1277         return 0;
1278
1279     LayoutUnit borderWidth;
1280
1281     const BorderValue& tb = style().borderStart();
1282     if (tb.style() == BorderStyle::Hidden)
1283         return 0;
1284     if (tb.style() > BorderStyle::Hidden)
1285         return CollapsedBorderValue::adjustedCollapsedBorderWidth(tb.width(), document().deviceScaleFactor(), !style().isLeftToRightDirection());
1286
1287     bool allHidden = true;
1288     for (RenderTableSection* section = topSection(); section; section = sectionBelow(section)) {
1289         LayoutUnit sw = section->outerBorderStart();
1290         if (sw < 0)
1291             continue;
1292         allHidden = false;
1293         borderWidth = std::max(borderWidth, sw);
1294     }
1295     if (allHidden)
1296         return 0;
1297
1298     return borderWidth;
1299 }
1300
1301 LayoutUnit RenderTable::outerBorderEnd() const
1302 {
1303     if (!collapseBorders())
1304         return 0;
1305
1306     LayoutUnit borderWidth;
1307
1308     const BorderValue& tb = style().borderEnd();
1309     if (tb.style() == BorderStyle::Hidden)
1310         return 0;
1311     if (tb.style() > BorderStyle::Hidden)
1312         return CollapsedBorderValue::adjustedCollapsedBorderWidth(tb.width(), document().deviceScaleFactor(), style().isLeftToRightDirection());
1313
1314     bool allHidden = true;
1315     for (RenderTableSection* section = topSection(); section; section = sectionBelow(section)) {
1316         LayoutUnit sw = section->outerBorderEnd();
1317         if (sw < 0)
1318             continue;
1319         allHidden = false;
1320         borderWidth = std::max(borderWidth, sw);
1321     }
1322     if (allHidden)
1323         return 0;
1324
1325     return borderWidth;
1326 }
1327
1328 RenderTableSection* RenderTable::sectionAbove(const RenderTableSection* section, SkipEmptySectionsValue skipEmptySections) const
1329 {
1330     recalcSectionsIfNeeded();
1331
1332     if (section == m_head)
1333         return nullptr;
1334
1335     RenderObject* prevSection = section == m_foot ? lastChild() : section->previousSibling();
1336     while (prevSection) {
1337         if (is<RenderTableSection>(*prevSection) && prevSection != m_head && prevSection != m_foot && (skipEmptySections == DoNotSkipEmptySections || downcast<RenderTableSection>(*prevSection).numRows()))
1338             break;
1339         prevSection = prevSection->previousSibling();
1340     }
1341     if (!prevSection && m_head && (skipEmptySections == DoNotSkipEmptySections || m_head->numRows()))
1342         prevSection = m_head.get();
1343     return downcast<RenderTableSection>(prevSection);
1344 }
1345
1346 RenderTableSection* RenderTable::sectionBelow(const RenderTableSection* section, SkipEmptySectionsValue skipEmptySections) const
1347 {
1348     recalcSectionsIfNeeded();
1349
1350     if (section == m_foot)
1351         return nullptr;
1352
1353     RenderObject* nextSection = section == m_head ? firstChild() : section->nextSibling();
1354     while (nextSection) {
1355         if (is<RenderTableSection>(*nextSection) && nextSection != m_head && nextSection != m_foot && (skipEmptySections  == DoNotSkipEmptySections || downcast<RenderTableSection>(*nextSection).numRows()))
1356             break;
1357         nextSection = nextSection->nextSibling();
1358     }
1359     if (!nextSection && m_foot && (skipEmptySections == DoNotSkipEmptySections || m_foot->numRows()))
1360         nextSection = m_foot.get();
1361     return downcast<RenderTableSection>(nextSection);
1362 }
1363
1364 RenderTableSection* RenderTable::bottomSection() const
1365 {
1366     recalcSectionsIfNeeded();
1367     if (m_foot)
1368         return m_foot.get();
1369     for (RenderObject* child = lastChild(); child; child = child->previousSibling()) {
1370         if (is<RenderTableSection>(*child))
1371             return downcast<RenderTableSection>(child);
1372     }
1373     return nullptr;
1374 }
1375
1376 RenderTableCell* RenderTable::cellAbove(const RenderTableCell* cell) const
1377 {
1378     recalcSectionsIfNeeded();
1379
1380     // Find the section and row to look in
1381     unsigned r = cell->rowIndex();
1382     RenderTableSection* section = nullptr;
1383     unsigned rAbove = 0;
1384     if (r > 0) {
1385         // cell is not in the first row, so use the above row in its own section
1386         section = cell->section();
1387         rAbove = r - 1;
1388     } else {
1389         section = sectionAbove(cell->section(), SkipEmptySections);
1390         if (section) {
1391             ASSERT(section->numRows());
1392             rAbove = section->numRows() - 1;
1393         }
1394     }
1395
1396     // Look up the cell in the section's grid, which requires effective col index
1397     if (section) {
1398         unsigned effCol = colToEffCol(cell->col());
1399         RenderTableSection::CellStruct& aboveCell = section->cellAt(rAbove, effCol);
1400         return aboveCell.primaryCell();
1401     } else
1402         return nullptr;
1403 }
1404
1405 RenderTableCell* RenderTable::cellBelow(const RenderTableCell* cell) const
1406 {
1407     recalcSectionsIfNeeded();
1408
1409     // Find the section and row to look in
1410     unsigned r = cell->rowIndex() + cell->rowSpan() - 1;
1411     RenderTableSection* section = nullptr;
1412     unsigned rBelow = 0;
1413     if (r < cell->section()->numRows() - 1) {
1414         // The cell is not in the last row, so use the next row in the section.
1415         section = cell->section();
1416         rBelow = r + 1;
1417     } else {
1418         section = sectionBelow(cell->section(), SkipEmptySections);
1419         if (section)
1420             rBelow = 0;
1421     }
1422
1423     // Look up the cell in the section's grid, which requires effective col index
1424     if (section) {
1425         unsigned effCol = colToEffCol(cell->col());
1426         RenderTableSection::CellStruct& belowCell = section->cellAt(rBelow, effCol);
1427         return belowCell.primaryCell();
1428     } else
1429         return nullptr;
1430 }
1431
1432 RenderTableCell* RenderTable::cellBefore(const RenderTableCell* cell) const
1433 {
1434     recalcSectionsIfNeeded();
1435
1436     RenderTableSection* section = cell->section();
1437     unsigned effCol = colToEffCol(cell->col());
1438     if (!effCol)
1439         return nullptr;
1440     
1441     // If we hit a colspan back up to a real cell.
1442     RenderTableSection::CellStruct& prevCell = section->cellAt(cell->rowIndex(), effCol - 1);
1443     return prevCell.primaryCell();
1444 }
1445
1446 RenderTableCell* RenderTable::cellAfter(const RenderTableCell* cell) const
1447 {
1448     recalcSectionsIfNeeded();
1449
1450     unsigned effCol = colToEffCol(cell->col() + cell->colSpan());
1451     if (effCol >= numEffCols())
1452         return nullptr;
1453     return cell->section()->primaryCellAt(cell->rowIndex(), effCol);
1454 }
1455
1456 RenderBlock* RenderTable::firstLineBlock() const
1457 {
1458     return nullptr;
1459 }
1460
1461 int RenderTable::baselinePosition(FontBaseline baselineType, bool firstLine, LineDirectionMode direction, LinePositionMode linePositionMode) const
1462 {
1463     return valueOrCompute(firstLineBaseline(), [&] {
1464         return RenderBox::baselinePosition(baselineType, firstLine, direction, linePositionMode);
1465     });
1466 }
1467
1468 Optional<int> RenderTable::inlineBlockBaseline(LineDirectionMode) const
1469 {
1470     // Tables are skipped when computing an inline-block's baseline.
1471     return Optional<int>();
1472 }
1473
1474 Optional<int> RenderTable::firstLineBaseline() const
1475 {
1476     // The baseline of a 'table' is the same as the 'inline-table' baseline per CSS 3 Flexbox (CSS 2.1
1477     // doesn't define the baseline of a 'table' only an 'inline-table').
1478     // This is also needed to properly determine the baseline of a cell if it has a table child.
1479
1480     if (isWritingModeRoot())
1481         return Optional<int>();
1482
1483     recalcSectionsIfNeeded();
1484
1485     const RenderTableSection* topNonEmptySection = this->topNonEmptySection();
1486     if (!topNonEmptySection)
1487         return Optional<int>();
1488
1489     if (Optional<int> baseline = topNonEmptySection->firstLineBaseline())
1490         return Optional<int>(topNonEmptySection->logicalTop() + baseline.value());
1491
1492     // FIXME: A table row always has a baseline per CSS 2.1. Will this return the right value?
1493     return Optional<int>();
1494 }
1495
1496 LayoutRect RenderTable::overflowClipRect(const LayoutPoint& location, RenderFragmentContainer* fragment, OverlayScrollbarSizeRelevancy relevancy, PaintPhase phase)
1497 {
1498     LayoutRect rect;
1499     // Don't clip out the table's side of the collapsed borders if we're in the paint phase that will ask the sections to paint them.
1500     // Likewise, if we're self-painting we avoid clipping them out as the clip rect that will be passed down to child layers from RenderLayer will do that instead.
1501     if (phase == PaintPhase::ChildBlockBackgrounds || layer()->isSelfPaintingLayer()) {
1502         rect = borderBoxRectInFragment(fragment);
1503         rect.setLocation(location + rect.location());
1504     } else
1505         rect = RenderBox::overflowClipRect(location, fragment, relevancy);
1506
1507     // If we have a caption, expand the clip to include the caption.
1508     // FIXME: Technically this is wrong, but it's virtually impossible to fix this
1509     // for real until captions have been re-written.
1510     // FIXME: This code assumes (like all our other caption code) that only top/bottom are
1511     // supported.  When we actually support left/right and stop mapping them to top/bottom,
1512     // we might have to hack this code first (depending on what order we do these bug fixes in).
1513     if (!m_captions.isEmpty()) {
1514         if (style().isHorizontalWritingMode()) {
1515             rect.setHeight(height());
1516             rect.setY(location.y());
1517         } else {
1518             rect.setWidth(width());
1519             rect.setX(location.x());
1520         }
1521     }
1522
1523     return rect;
1524 }
1525
1526 bool RenderTable::nodeAtPoint(const HitTestRequest& request, HitTestResult& result, const HitTestLocation& locationInContainer, const LayoutPoint& accumulatedOffset, HitTestAction action)
1527 {
1528     LayoutPoint adjustedLocation = accumulatedOffset + location();
1529
1530     // Check kids first.
1531     if (!hasOverflowClip() || locationInContainer.intersects(overflowClipRect(adjustedLocation, nullptr))) {
1532         for (RenderObject* child = lastChild(); child; child = child->previousSibling()) {
1533             if (is<RenderBox>(*child) && !downcast<RenderBox>(*child).hasSelfPaintingLayer() && (child->isTableSection() || child->isTableCaption())) {
1534                 LayoutPoint childPoint = flipForWritingModeForChild(downcast<RenderBox>(child), adjustedLocation);
1535                 if (child->nodeAtPoint(request, result, locationInContainer, childPoint, action)) {
1536                     updateHitTestResult(result, toLayoutPoint(locationInContainer.point() - childPoint));
1537                     return true;
1538                 }
1539             }
1540         }
1541     }
1542
1543     // Check our bounds next.
1544     LayoutRect boundsRect(adjustedLocation, size());
1545     if (visibleToHitTesting() && (action == HitTestBlockBackground || action == HitTestChildBlockBackground) && locationInContainer.intersects(boundsRect)) {
1546         updateHitTestResult(result, flipForWritingMode(locationInContainer.point() - toLayoutSize(adjustedLocation)));
1547         if (result.addNodeToListBasedTestResult(element(), request, locationInContainer, boundsRect) == HitTestProgress::Stop)
1548             return true;
1549     }
1550
1551     return false;
1552 }
1553
1554 RenderPtr<RenderTable> RenderTable::createTableWithStyle(Document& document, const RenderStyle& style)
1555 {
1556     auto table = createRenderer<RenderTable>(document, RenderStyle::createAnonymousStyleWithDisplay(style, style.display() == DisplayType::Inline ? DisplayType::InlineTable : DisplayType::Table));
1557     table->initializeStyle();
1558     return table;
1559 }
1560
1561 RenderPtr<RenderTable> RenderTable::createAnonymousWithParentRenderer(const RenderElement& parent)
1562 {
1563     return RenderTable::createTableWithStyle(parent.document(), parent.style());
1564 }
1565
1566 const BorderValue& RenderTable::tableStartBorderAdjoiningCell(const RenderTableCell& cell) const
1567 {
1568     ASSERT(cell.isFirstOrLastCellInRow());
1569     if (isDirectionSame(this, cell.row()))
1570         return style().borderStart();
1571
1572     return style().borderEnd();
1573 }
1574
1575 const BorderValue& RenderTable::tableEndBorderAdjoiningCell(const RenderTableCell& cell) const
1576 {
1577     ASSERT(cell.isFirstOrLastCellInRow());
1578     if (isDirectionSame(this, cell.row()))
1579         return style().borderEnd();
1580
1581     return style().borderStart();
1582 }
1583
1584 void RenderTable::markForPaginationRelayoutIfNeeded()
1585 {
1586     auto* layoutState = view().frameView().layoutContext().layoutState();
1587     if (!layoutState->isPaginated() || (!layoutState->pageLogicalHeightChanged() && (!layoutState->pageLogicalHeight() || layoutState->pageLogicalOffset(this, logicalTop()) == pageLogicalOffset())))
1588         return;
1589     
1590     // When a table moves, we have to dirty all of the sections too.
1591     if (!needsLayout())
1592         setChildNeedsLayout(MarkOnlyThis);
1593     for (auto& child : childrenOfType<RenderTableSection>(*this)) {
1594         if (!child.needsLayout())
1595             child.setChildNeedsLayout(MarkOnlyThis);
1596     }
1597 }
1598
1599 }