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