Web Inspector: Native Memory Instrumentation: instrument not instrumented members.
[WebKit-https.git] / Source / WebCore / rendering / RenderTableSection.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, 2008, 2009, 2010 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 "RenderTableSection.h"
28 #include "CachedImage.h"
29 #include "Document.h"
30 #include "HitTestResult.h"
31 #include "HTMLNames.h"
32 #include "PaintInfo.h"
33 #include "RenderTableCell.h"
34 #include "RenderTableCol.h"
35 #include "RenderTableRow.h"
36 #include "RenderView.h"
37 #include "StyleInheritedData.h"
38 #include "WebCoreMemoryInstrumentation.h"
39 #include <limits>
40 #include <wtf/HashSet.h>
41 #include <wtf/MemoryInstrumentationHashMap.h>
42 #include <wtf/MemoryInstrumentationHashSet.h>
43 #include <wtf/MemoryInstrumentationVector.h>
44 #include <wtf/Vector.h>
45
46 using namespace std;
47
48 namespace WebCore {
49
50 using namespace HTMLNames;
51
52 // Those 2 variables are used to balance the memory consumption vs the repaint time on big tables.
53 static unsigned gMinTableSizeToUseFastPaintPathWithOverflowingCell = 75 * 75;
54 static float gMaxAllowedOverflowingCellRatioForFastPaintPath = 0.1f;
55
56 static inline void setRowLogicalHeightToRowStyleLogicalHeightIfNotRelative(RenderTableSection::RowStruct& row)
57 {
58     ASSERT(row.rowRenderer);
59     row.logicalHeight = row.rowRenderer->style()->logicalHeight();
60     if (row.logicalHeight.isRelative())
61         row.logicalHeight = Length();
62 }
63
64 static inline void updateLogicalHeightForCell(RenderTableSection::RowStruct& row, const RenderTableCell* cell)
65 {
66     // We ignore height settings on rowspan cells.
67     if (cell->rowSpan() != 1)
68         return;
69
70     Length logicalHeight = cell->style()->logicalHeight();
71     if (logicalHeight.isPositive() || (logicalHeight.isRelative() && logicalHeight.value() >= 0)) {
72         Length cRowLogicalHeight = row.logicalHeight;
73         switch (logicalHeight.type()) {
74         case Percent:
75             if (!(cRowLogicalHeight.isPercent())
76                 || (cRowLogicalHeight.isPercent() && cRowLogicalHeight.percent() < logicalHeight.percent()))
77                 row.logicalHeight = logicalHeight;
78             break;
79         case Fixed:
80             if (cRowLogicalHeight.type() < Percent
81                 || (cRowLogicalHeight.isFixed() && cRowLogicalHeight.value() < logicalHeight.value()))
82                 row.logicalHeight = logicalHeight;
83             break;
84         case Relative:
85         default:
86             break;
87         }
88     }
89 }
90
91
92 RenderTableSection::RenderTableSection(Node* node)
93     : RenderBox(node)
94     , m_cCol(0)
95     , m_cRow(0)
96     , m_outerBorderStart(0)
97     , m_outerBorderEnd(0)
98     , m_outerBorderBefore(0)
99     , m_outerBorderAfter(0)
100     , m_needsCellRecalc(false)
101     , m_hasMultipleCellLevels(false)
102 {
103     // init RenderObject attributes
104     setInline(false); // our object is not Inline
105 }
106
107 RenderTableSection::~RenderTableSection()
108 {
109 }
110
111 void RenderTableSection::styleDidChange(StyleDifference diff, const RenderStyle* oldStyle)
112 {
113     RenderBox::styleDidChange(diff, oldStyle);
114     propagateStyleToAnonymousChildren();
115
116     // If border was changed, notify table.
117     RenderTable* table = this->table();
118     if (table && !table->selfNeedsLayout() && !table->normalChildNeedsLayout() && oldStyle && oldStyle->border() != style()->border())
119         table->invalidateCollapsedBorders();
120 }
121
122 void RenderTableSection::willBeRemovedFromTree()
123 {
124     RenderBox::willBeRemovedFromTree();
125
126     // Preventively invalidate our cells as we may be re-inserted into
127     // a new table which would require us to rebuild our structure.
128     setNeedsCellRecalc();
129 }
130
131 void RenderTableSection::addChild(RenderObject* child, RenderObject* beforeChild)
132 {
133     // Make sure we don't append things after :after-generated content if we have it.
134     if (!beforeChild)
135         beforeChild = afterPseudoElementRenderer();
136
137     if (!child->isTableRow()) {
138         RenderObject* last = beforeChild;
139         if (!last)
140             last = lastChild();
141         if (last && last->isAnonymous() && !last->isBeforeOrAfterContent()) {
142             if (beforeChild == last)
143                 beforeChild = last->firstChild();
144             last->addChild(child, beforeChild);
145             return;
146         }
147
148         if (beforeChild && !beforeChild->isAnonymous() && beforeChild->parent() == this) {
149             RenderObject* row = beforeChild->previousSibling();
150             if (row && row->isTableRow() && row->isAnonymous()) {
151                 row->addChild(child);
152                 return;
153             }
154         }
155
156         // If beforeChild is inside an anonymous cell/row, insert into the cell or into
157         // the anonymous row containing it, if there is one.
158         RenderObject* lastBox = last;
159         while (lastBox && lastBox->parent()->isAnonymous() && !lastBox->isTableRow())
160             lastBox = lastBox->parent();
161         if (lastBox && lastBox->isAnonymous() && !lastBox->isBeforeOrAfterContent()) {
162             lastBox->addChild(child, beforeChild);
163             return;
164         }
165
166         RenderObject* row = RenderTableRow::createAnonymousWithParentRenderer(this);
167         addChild(row, beforeChild);
168         row->addChild(child);
169         return;
170     }
171
172     if (beforeChild)
173         setNeedsCellRecalc();
174
175     unsigned insertionRow = m_cRow;
176     ++m_cRow;
177     m_cCol = 0;
178
179     ensureRows(m_cRow);
180
181     RenderTableRow* row = toRenderTableRow(child);
182     m_grid[insertionRow].rowRenderer = row;
183     row->setRowIndex(insertionRow);
184
185     if (!beforeChild)
186         setRowLogicalHeightToRowStyleLogicalHeightIfNotRelative(m_grid[insertionRow]);
187
188     if (beforeChild && beforeChild->parent() != this)
189         beforeChild = splitAnonymousBoxesAroundChild(beforeChild);
190
191     ASSERT(!beforeChild || beforeChild->isTableRow());
192     RenderBox::addChild(child, beforeChild);
193 }
194
195 void RenderTableSection::ensureRows(unsigned numRows)
196 {
197     if (numRows <= m_grid.size())
198         return;
199
200     unsigned oldSize = m_grid.size();
201     m_grid.grow(numRows);
202
203     unsigned effectiveColumnCount = max(1u, table()->numEffCols());
204     for (unsigned row = oldSize; row < m_grid.size(); ++row)
205         m_grid[row].row.grow(effectiveColumnCount);
206 }
207
208 void RenderTableSection::addCell(RenderTableCell* cell, RenderTableRow* row)
209 {
210     // We don't insert the cell if we need cell recalc as our internal columns' representation
211     // will have drifted from the table's representation. Also recalcCells will call addCell
212     // at a later time after sync'ing our columns' with the table's.
213     if (needsCellRecalc())
214         return;
215
216     unsigned rSpan = cell->rowSpan();
217     unsigned cSpan = cell->colSpan();
218     const Vector<RenderTable::ColumnStruct>& columns = table()->columns();
219     unsigned nCols = columns.size();
220     unsigned insertionRow = row->rowIndex();
221
222     // ### mozilla still seems to do the old HTML way, even for strict DTD
223     // (see the annotation on table cell layouting in the CSS specs and the testcase below:
224     // <TABLE border>
225     // <TR><TD>1 <TD rowspan="2">2 <TD>3 <TD>4
226     // <TR><TD colspan="2">5
227     // </TABLE>
228     while (m_cCol < nCols && (cellAt(insertionRow, m_cCol).hasCells() || cellAt(insertionRow, m_cCol).inColSpan))
229         m_cCol++;
230
231     updateLogicalHeightForCell(m_grid[insertionRow], cell);
232
233     ensureRows(insertionRow + rSpan);
234
235     m_grid[insertionRow].rowRenderer = row;
236
237     unsigned col = m_cCol;
238     // tell the cell where it is
239     bool inColSpan = false;
240     while (cSpan) {
241         unsigned currentSpan;
242         if (m_cCol >= nCols) {
243             table()->appendColumn(cSpan);
244             currentSpan = cSpan;
245         } else {
246             if (cSpan < columns[m_cCol].span)
247                 table()->splitColumn(m_cCol, cSpan);
248             currentSpan = columns[m_cCol].span;
249         }
250         for (unsigned r = 0; r < rSpan; r++) {
251             CellStruct& c = cellAt(insertionRow + r, m_cCol);
252             ASSERT(cell);
253             c.cells.append(cell);
254             // If cells overlap then we take the slow path for painting.
255             if (c.cells.size() > 1)
256                 m_hasMultipleCellLevels = true;
257             if (inColSpan)
258                 c.inColSpan = true;
259         }
260         m_cCol++;
261         cSpan -= currentSpan;
262         inColSpan = true;
263     }
264     cell->setCol(table()->effColToCol(col));
265 }
266
267 int RenderTableSection::calcRowLogicalHeight()
268 {
269 #ifndef NDEBUG
270     setNeedsLayoutIsForbidden(true);
271 #endif
272
273     ASSERT(!needsLayout());
274
275     RenderTableCell* cell;
276
277     int spacing = table()->vBorderSpacing();
278     
279     RenderView* viewRenderer = view();
280     LayoutStateMaintainer statePusher(viewRenderer);
281
282     m_rowPos.resize(m_grid.size() + 1);
283     m_rowPos[0] = spacing;
284
285     for (unsigned r = 0; r < m_grid.size(); r++) {
286         m_grid[r].baseline = 0;
287         LayoutUnit baselineDescent = 0;
288
289         // Our base size is the biggest logical height from our cells' styles (excluding row spanning cells).
290         m_rowPos[r + 1] = max(m_rowPos[r] + minimumValueForLength(m_grid[r].logicalHeight, 0, viewRenderer).round(), 0);
291
292         Row& row = m_grid[r].row;
293         unsigned totalCols = row.size();
294
295         for (unsigned c = 0; c < totalCols; c++) {
296             CellStruct& current = cellAt(r, c);
297             for (unsigned i = 0; i < current.cells.size(); i++) {
298                 cell = current.cells[i];
299                 if (current.inColSpan && cell->rowSpan() == 1)
300                     continue;
301
302                 // FIXME: We are always adding the height of a rowspan to the last rows which doesn't match
303                 // other browsers. See webkit.org/b/52185 for example.
304                 if ((cell->rowIndex() + cell->rowSpan() - 1) != r)
305                     continue;
306
307                 // For row spanning cells, |r| is the last row in the span.
308                 unsigned cellStartRow = cell->rowIndex();
309
310                 if (cell->hasOverrideHeight()) {
311                     if (!statePusher.didPush()) {
312                         // Technically, we should also push state for the row, but since
313                         // rows don't push a coordinate transform, that's not necessary.
314                         statePusher.push(this, locationOffset());
315                     }
316                     cell->clearIntrinsicPadding();
317                     cell->clearOverrideSize();
318                     cell->setChildNeedsLayout(true, MarkOnlyThis);
319                     cell->layoutIfNeeded();
320                 }
321
322                 int cellLogicalHeight = cell->logicalHeightForRowSizing();
323                 m_rowPos[r + 1] = max(m_rowPos[r + 1], m_rowPos[cellStartRow] + cellLogicalHeight);
324
325                 // find out the baseline
326                 EVerticalAlign va = cell->style()->verticalAlign();
327                 if (va == BASELINE || va == TEXT_BOTTOM || va == TEXT_TOP || va == SUPER || va == SUB || va == LENGTH) {
328                     LayoutUnit baselinePosition = cell->cellBaselinePosition();
329                     if (baselinePosition > cell->borderBefore() + cell->paddingBefore()) {
330                         m_grid[cellStartRow].baseline = max(m_grid[cellStartRow].baseline, baselinePosition - cell->intrinsicPaddingBefore());
331                         baselineDescent = max(baselineDescent, m_rowPos[cellStartRow] + cellLogicalHeight - (baselinePosition - cell->intrinsicPaddingBefore()));
332                     }
333                 }
334             }
335         }
336
337         // do we have baseline aligned elements?
338         if (m_grid[r].baseline)
339             // increase rowheight if baseline requires
340             m_rowPos[r + 1] = max<int>(m_rowPos[r + 1], m_grid[r].baseline + baselineDescent);
341
342         // Add the border-spacing to our final position.
343         m_rowPos[r + 1] += m_grid[r].rowRenderer ? spacing : 0;
344         m_rowPos[r + 1] = max(m_rowPos[r + 1], m_rowPos[r]);
345     }
346
347 #ifndef NDEBUG
348     setNeedsLayoutIsForbidden(false);
349 #endif
350
351     ASSERT(!needsLayout());
352
353     statePusher.pop();
354
355     return m_rowPos[m_grid.size()];
356 }
357
358 void RenderTableSection::layout()
359 {
360     StackStats::LayoutCheckPoint layoutCheckPoint;
361     ASSERT(needsLayout());
362     ASSERT(!needsCellRecalc());
363     ASSERT(!table()->needsSectionRecalc());
364
365     // addChild may over-grow m_grid but we don't want to throw away the memory too early as addChild
366     // can be called in a loop (e.g during parsing). Doing it now ensures we have a stable-enough structure.
367     m_grid.shrinkToFit();
368
369     LayoutStateMaintainer statePusher(view(), this, locationOffset(), style()->isFlippedBlocksWritingMode());
370
371     const Vector<int>& columnPos = table()->columnPositions();
372
373     for (unsigned r = 0; r < m_grid.size(); ++r) {
374         Row& row = m_grid[r].row;
375         unsigned cols = row.size();
376         // First, propagate our table layout's information to the cells. This will mark the row as needing layout
377         // if there was a column logical width change.
378         for (unsigned startColumn = 0; startColumn < cols; ++startColumn) {
379             CellStruct& current = row[startColumn];
380             RenderTableCell* cell = current.primaryCell();
381             if (!cell || current.inColSpan)
382                 continue;
383
384             unsigned endCol = startColumn;
385             unsigned cspan = cell->colSpan();
386             while (cspan && endCol < cols) {
387                 ASSERT(endCol < table()->columns().size());
388                 cspan -= table()->columns()[endCol].span;
389                 endCol++;
390             }
391             int tableLayoutLogicalWidth = columnPos[endCol] - columnPos[startColumn] - table()->hBorderSpacing();
392             cell->setCellLogicalWidth(tableLayoutLogicalWidth);
393         }
394
395         if (RenderTableRow* rowRenderer = m_grid[r].rowRenderer)
396             rowRenderer->layoutIfNeeded();
397     }
398
399     statePusher.pop();
400     setNeedsLayout(false);
401 }
402
403 void RenderTableSection::distributeExtraLogicalHeightToPercentRows(int& extraLogicalHeight, int totalPercent)
404 {
405     if (!totalPercent)
406         return;
407
408     unsigned totalRows = m_grid.size();
409     int totalHeight = m_rowPos[totalRows] + extraLogicalHeight;
410     int totalLogicalHeightAdded = 0;
411     totalPercent = min(totalPercent, 100);
412     int rowHeight = m_rowPos[1] - m_rowPos[0];
413     for (unsigned r = 0; r < totalRows; ++r) {
414         if (totalPercent > 0 && m_grid[r].logicalHeight.isPercent()) {
415             int toAdd = min<int>(extraLogicalHeight, (totalHeight * m_grid[r].logicalHeight.percent() / 100) - rowHeight);
416             // If toAdd is negative, then we don't want to shrink the row (this bug
417             // affected Outlook Web Access).
418             toAdd = max(0, toAdd);
419             totalLogicalHeightAdded += toAdd;
420             extraLogicalHeight -= toAdd;
421             totalPercent -= m_grid[r].logicalHeight.percent();
422         }
423         ASSERT(totalRows >= 1);
424         if (r < totalRows - 1)
425             rowHeight = m_rowPos[r + 2] - m_rowPos[r + 1];
426         m_rowPos[r + 1] += totalLogicalHeightAdded;
427     }
428 }
429
430 void RenderTableSection::distributeExtraLogicalHeightToAutoRows(int& extraLogicalHeight, unsigned autoRowsCount)
431 {
432     if (!autoRowsCount)
433         return;
434
435     int totalLogicalHeightAdded = 0;
436     for (unsigned r = 0; r < m_grid.size(); ++r) {
437         if (autoRowsCount > 0 && m_grid[r].logicalHeight.isAuto()) {
438             // Recomputing |extraLogicalHeightForRow| guarantees that we properly ditribute round |extraLogicalHeight|.
439             int extraLogicalHeightForRow = extraLogicalHeight / autoRowsCount;
440             totalLogicalHeightAdded += extraLogicalHeightForRow;
441             extraLogicalHeight -= extraLogicalHeightForRow;
442             --autoRowsCount;
443         }
444         m_rowPos[r + 1] += totalLogicalHeightAdded;
445     }
446 }
447
448 void RenderTableSection::distributeRemainingExtraLogicalHeight(int& extraLogicalHeight)
449 {
450     unsigned totalRows = m_grid.size();
451
452     if (extraLogicalHeight <= 0 || !m_rowPos[totalRows])
453         return;
454
455     // FIXME: m_rowPos[totalRows] - m_rowPos[0] is the total rows' size.
456     int totalRowSize = m_rowPos[totalRows];
457     int totalLogicalHeightAdded = 0;
458     int previousRowPosition = m_rowPos[0];
459     for (unsigned r = 0; r < totalRows; r++) {
460         // weight with the original height
461         totalLogicalHeightAdded += extraLogicalHeight * (m_rowPos[r + 1] - previousRowPosition) / totalRowSize;
462         previousRowPosition = m_rowPos[r + 1];
463         m_rowPos[r + 1] += totalLogicalHeightAdded;
464     }
465
466     extraLogicalHeight -= totalLogicalHeightAdded;
467 }
468
469 int RenderTableSection::distributeExtraLogicalHeightToRows(int extraLogicalHeight)
470 {
471     if (!extraLogicalHeight)
472         return extraLogicalHeight;
473
474     unsigned totalRows = m_grid.size();
475     if (!totalRows)
476         return extraLogicalHeight;
477
478     if (!m_rowPos[totalRows] && nextSibling())
479         return extraLogicalHeight;
480
481     unsigned autoRowsCount = 0;
482     int totalPercent = 0;
483     for (unsigned r = 0; r < totalRows; r++) {
484         if (m_grid[r].logicalHeight.isAuto())
485             ++autoRowsCount;
486         else if (m_grid[r].logicalHeight.isPercent())
487             totalPercent += m_grid[r].logicalHeight.percent();
488     }
489
490     int remainingExtraLogicalHeight = extraLogicalHeight;
491     distributeExtraLogicalHeightToPercentRows(remainingExtraLogicalHeight, totalPercent);
492     distributeExtraLogicalHeightToAutoRows(remainingExtraLogicalHeight, autoRowsCount);
493     distributeRemainingExtraLogicalHeight(remainingExtraLogicalHeight);
494     return extraLogicalHeight - remainingExtraLogicalHeight;
495 }
496
497 void RenderTableSection::layoutRows()
498 {
499 #ifndef NDEBUG
500     setNeedsLayoutIsForbidden(true);
501 #endif
502
503     ASSERT(!needsLayout());
504
505     unsigned totalRows = m_grid.size();
506
507     // Set the width of our section now.  The rows will also be this width.
508     setLogicalWidth(table()->contentLogicalWidth());
509     m_overflow.clear();
510     m_overflowingCells.clear();
511     m_forceSlowPaintPathWithOverflowingCell = false;
512
513     int vspacing = table()->vBorderSpacing();
514     unsigned nEffCols = table()->numEffCols();
515
516     LayoutStateMaintainer statePusher(view(), this, locationOffset(), style()->isFlippedBlocksWritingMode());
517
518     for (unsigned r = 0; r < totalRows; r++) {
519         // Set the row's x/y position and width/height.
520         if (RenderTableRow* rowRenderer = m_grid[r].rowRenderer) {
521             rowRenderer->setLocation(LayoutPoint(0, m_rowPos[r]));
522             rowRenderer->setLogicalWidth(logicalWidth());
523             rowRenderer->setLogicalHeight(m_rowPos[r + 1] - m_rowPos[r] - vspacing);
524             rowRenderer->updateLayerTransform();
525         }
526
527         int rowHeightIncreaseForPagination = 0;
528
529         for (unsigned c = 0; c < nEffCols; c++) {
530             CellStruct& cs = cellAt(r, c);
531             RenderTableCell* cell = cs.primaryCell();
532
533             if (!cell || cs.inColSpan)
534                 continue;
535
536             int rowIndex = cell->rowIndex();
537             int rHeight = m_rowPos[rowIndex + cell->rowSpan()] - m_rowPos[rowIndex] - vspacing;
538
539             // Force percent height children to lay themselves out again.
540             // This will cause these children to grow to fill the cell.
541             // FIXME: There is still more work to do here to fully match WinIE (should
542             // it become necessary to do so).  In quirks mode, WinIE behaves like we
543             // do, but it will clip the cells that spill out of the table section.  In
544             // strict mode, Mozilla and WinIE both regrow the table to accommodate the
545             // new height of the cell (thus letting the percentages cause growth one
546             // time only).  We may also not be handling row-spanning cells correctly.
547             //
548             // Note also the oddity where replaced elements always flex, and yet blocks/tables do
549             // not necessarily flex.  WinIE is crazy and inconsistent, and we can't hope to
550             // match the behavior perfectly, but we'll continue to refine it as we discover new
551             // bugs. :)
552             bool cellChildrenFlex = false;
553             bool flexAllChildren = cell->style()->logicalHeight().isFixed()
554                 || (!table()->style()->logicalHeight().isAuto() && rHeight != cell->logicalHeight());
555
556             for (RenderObject* o = cell->firstChild(); o; o = o->nextSibling()) {
557                 if (!o->isText() && o->style()->logicalHeight().isPercent() && (flexAllChildren || o->isReplaced() || (o->isBox() && toRenderBox(o)->scrollsOverflow()))) {
558                     // Tables with no sections do not flex.
559                     if (!o->isTable() || toRenderTable(o)->hasSections()) {
560                         o->setNeedsLayout(true, MarkOnlyThis);
561                         cellChildrenFlex = true;
562                     }
563                 }
564             }
565
566             if (TrackedRendererListHashSet* percentHeightDescendants = cell->percentHeightDescendants()) {
567                 TrackedRendererListHashSet::iterator end = percentHeightDescendants->end();
568                 for (TrackedRendererListHashSet::iterator it = percentHeightDescendants->begin(); it != end; ++it) {
569                     RenderBox* box = *it;
570                     if (!box->isReplaced() && !box->scrollsOverflow() && !flexAllChildren)
571                         continue;
572
573                     while (box != cell) {
574                         if (box->normalChildNeedsLayout())
575                             break;
576                         box->setChildNeedsLayout(true, MarkOnlyThis);
577                         box = box->containingBlock();
578                         ASSERT(box);
579                         if (!box)
580                             break;
581                     }
582                     cellChildrenFlex = true;
583                 }
584             }
585
586             if (cellChildrenFlex) {
587                 cell->setChildNeedsLayout(true, MarkOnlyThis);
588                 // Alignment within a cell is based off the calculated
589                 // height, which becomes irrelevant once the cell has
590                 // been resized based off its percentage.
591                 cell->setOverrideLogicalContentHeightFromRowHeight(rHeight);
592                 cell->layoutIfNeeded();
593
594                 // If the baseline moved, we may have to update the data for our row. Find out the new baseline.
595                 EVerticalAlign va = cell->style()->verticalAlign();
596                 if (va == BASELINE || va == TEXT_BOTTOM || va == TEXT_TOP || va == SUPER || va == SUB || va == LENGTH) {
597                     LayoutUnit baseline = cell->cellBaselinePosition();
598                     if (baseline > cell->borderBefore() + cell->paddingBefore())
599                         m_grid[r].baseline = max(m_grid[r].baseline, baseline);
600                 }
601             }
602
603             cell->computeIntrinsicPadding(rHeight);
604
605             LayoutRect oldCellRect = cell->frameRect();
606
607             setLogicalPositionForCell(cell, c);
608
609             if (!cell->needsLayout() && view()->layoutState()->pageLogicalHeight() && view()->layoutState()->pageLogicalOffset(cell, cell->logicalTop()) != cell->pageLogicalOffset())
610                 cell->setChildNeedsLayout(true, MarkOnlyThis);
611
612             cell->layoutIfNeeded();
613
614             // FIXME: Make pagination work with vertical tables.
615             if (view()->layoutState()->pageLogicalHeight() && cell->logicalHeight() != rHeight) {
616                 // FIXME: Pagination might have made us change size. For now just shrink or grow the cell to fit without doing a relayout.
617                 // We'll also do a basic increase of the row height to accommodate the cell if it's bigger, but this isn't quite right
618                 // either. It's at least stable though and won't result in an infinite # of relayouts that may never stabilize.
619                 if (cell->logicalHeight() > rHeight)
620                     rowHeightIncreaseForPagination = max<int>(rowHeightIncreaseForPagination, cell->logicalHeight() - rHeight);
621                 cell->setLogicalHeight(rHeight);
622             }
623
624             LayoutSize childOffset(cell->location() - oldCellRect.location());
625             if (childOffset.width() || childOffset.height()) {
626                 view()->addLayoutDelta(childOffset);
627
628                 // If the child moved, we have to repaint it as well as any floating/positioned
629                 // descendants.  An exception is if we need a layout.  In this case, we know we're going to
630                 // repaint ourselves (and the child) anyway.
631                 if (!table()->selfNeedsLayout() && cell->checkForRepaintDuringLayout())
632                     cell->repaintDuringLayoutIfMoved(oldCellRect);
633             }
634         }
635         if (rowHeightIncreaseForPagination) {
636             for (unsigned rowIndex = r + 1; rowIndex <= totalRows; rowIndex++)
637                 m_rowPos[rowIndex] += rowHeightIncreaseForPagination;
638             for (unsigned c = 0; c < nEffCols; ++c) {
639                 Vector<RenderTableCell*, 1>& cells = cellAt(r, c).cells;
640                 for (size_t i = 0; i < cells.size(); ++i)
641                     cells[i]->setLogicalHeight(cells[i]->logicalHeight() + rowHeightIncreaseForPagination);
642             }
643         }
644     }
645
646 #ifndef NDEBUG
647     setNeedsLayoutIsForbidden(false);
648 #endif
649
650     ASSERT(!needsLayout());
651
652     setLogicalHeight(m_rowPos[totalRows]);
653
654     unsigned totalCellsCount = nEffCols * totalRows;
655     int maxAllowedOverflowingCellsCount = totalCellsCount < gMinTableSizeToUseFastPaintPathWithOverflowingCell ? 0 : gMaxAllowedOverflowingCellRatioForFastPaintPath * totalCellsCount;
656
657 #ifndef NDEBUG
658     bool hasOverflowingCell = false;
659 #endif
660     // Now that our height has been determined, add in overflow from cells.
661     for (unsigned r = 0; r < totalRows; r++) {
662         for (unsigned c = 0; c < nEffCols; c++) {
663             CellStruct& cs = cellAt(r, c);
664             RenderTableCell* cell = cs.primaryCell();
665             if (!cell || cs.inColSpan)
666                 continue;
667             if (r < totalRows - 1 && cell == primaryCellAt(r + 1, c))
668                 continue;
669             addOverflowFromChild(cell);
670 #ifndef NDEBUG
671             hasOverflowingCell |= cell->hasVisualOverflow();
672 #endif
673             if (cell->hasVisualOverflow() && !m_forceSlowPaintPathWithOverflowingCell) {
674                 m_overflowingCells.add(cell);
675                 if (m_overflowingCells.size() > maxAllowedOverflowingCellsCount) {
676                     // We need to set m_forcesSlowPaintPath only if there is a least one overflowing cells as the hit testing code rely on this information.
677                     m_forceSlowPaintPathWithOverflowingCell = true;
678                     // The slow path does not make any use of the overflowing cells info, don't hold on to the memory.
679                     m_overflowingCells.clear();
680                 }
681             }
682         }
683     }
684
685     ASSERT(hasOverflowingCell == this->hasOverflowingCell());
686
687     statePusher.pop();
688 }
689
690 int RenderTableSection::calcOuterBorderBefore() const
691 {
692     unsigned totalCols = table()->numEffCols();
693     if (!m_grid.size() || !totalCols)
694         return 0;
695
696     unsigned borderWidth = 0;
697
698     const BorderValue& sb = style()->borderBefore();
699     if (sb.style() == BHIDDEN)
700         return -1;
701     if (sb.style() > BHIDDEN)
702         borderWidth = sb.width();
703
704     const BorderValue& rb = firstChild()->style()->borderBefore();
705     if (rb.style() == BHIDDEN)
706         return -1;
707     if (rb.style() > BHIDDEN && rb.width() > borderWidth)
708         borderWidth = rb.width();
709
710     bool allHidden = true;
711     for (unsigned c = 0; c < totalCols; c++) {
712         const CellStruct& current = cellAt(0, c);
713         if (current.inColSpan || !current.hasCells())
714             continue;
715         const BorderValue& cb = current.primaryCell()->style()->borderBefore(); // FIXME: Make this work with perpendicular and flipped cells.
716         // FIXME: Don't repeat for the same col group
717         RenderTableCol* colGroup = table()->colElement(c);
718         if (colGroup) {
719             const BorderValue& gb = colGroup->style()->borderBefore();
720             if (gb.style() == BHIDDEN || cb.style() == BHIDDEN)
721                 continue;
722             allHidden = false;
723             if (gb.style() > BHIDDEN && gb.width() > borderWidth)
724                 borderWidth = gb.width();
725             if (cb.style() > BHIDDEN && cb.width() > borderWidth)
726                 borderWidth = cb.width();
727         } else {
728             if (cb.style() == BHIDDEN)
729                 continue;
730             allHidden = false;
731             if (cb.style() > BHIDDEN && cb.width() > borderWidth)
732                 borderWidth = cb.width();
733         }
734     }
735     if (allHidden)
736         return -1;
737
738     return borderWidth / 2;
739 }
740
741 int RenderTableSection::calcOuterBorderAfter() const
742 {
743     unsigned totalCols = table()->numEffCols();
744     if (!m_grid.size() || !totalCols)
745         return 0;
746
747     unsigned borderWidth = 0;
748
749     const BorderValue& sb = style()->borderAfter();
750     if (sb.style() == BHIDDEN)
751         return -1;
752     if (sb.style() > BHIDDEN)
753         borderWidth = sb.width();
754
755     const BorderValue& rb = lastChild()->style()->borderAfter();
756     if (rb.style() == BHIDDEN)
757         return -1;
758     if (rb.style() > BHIDDEN && rb.width() > borderWidth)
759         borderWidth = rb.width();
760
761     bool allHidden = true;
762     for (unsigned c = 0; c < totalCols; c++) {
763         const CellStruct& current = cellAt(m_grid.size() - 1, c);
764         if (current.inColSpan || !current.hasCells())
765             continue;
766         const BorderValue& cb = current.primaryCell()->style()->borderAfter(); // FIXME: Make this work with perpendicular and flipped cells.
767         // FIXME: Don't repeat for the same col group
768         RenderTableCol* colGroup = table()->colElement(c);
769         if (colGroup) {
770             const BorderValue& gb = colGroup->style()->borderAfter();
771             if (gb.style() == BHIDDEN || cb.style() == BHIDDEN)
772                 continue;
773             allHidden = false;
774             if (gb.style() > BHIDDEN && gb.width() > borderWidth)
775                 borderWidth = gb.width();
776             if (cb.style() > BHIDDEN && cb.width() > borderWidth)
777                 borderWidth = cb.width();
778         } else {
779             if (cb.style() == BHIDDEN)
780                 continue;
781             allHidden = false;
782             if (cb.style() > BHIDDEN && cb.width() > borderWidth)
783                 borderWidth = cb.width();
784         }
785     }
786     if (allHidden)
787         return -1;
788
789     return (borderWidth + 1) / 2;
790 }
791
792 int RenderTableSection::calcOuterBorderStart() const
793 {
794     unsigned totalCols = table()->numEffCols();
795     if (!m_grid.size() || !totalCols)
796         return 0;
797
798     unsigned borderWidth = 0;
799
800     const BorderValue& sb = style()->borderStart();
801     if (sb.style() == BHIDDEN)
802         return -1;
803     if (sb.style() > BHIDDEN)
804         borderWidth = sb.width();
805
806     if (RenderTableCol* colGroup = table()->colElement(0)) {
807         const BorderValue& gb = colGroup->style()->borderStart();
808         if (gb.style() == BHIDDEN)
809             return -1;
810         if (gb.style() > BHIDDEN && gb.width() > borderWidth)
811             borderWidth = gb.width();
812     }
813
814     bool allHidden = true;
815     for (unsigned r = 0; r < m_grid.size(); r++) {
816         const CellStruct& current = cellAt(r, 0);
817         if (!current.hasCells())
818             continue;
819         // FIXME: Don't repeat for the same cell
820         const BorderValue& cb = current.primaryCell()->style()->borderStart(); // FIXME: Make this work with perpendicular and flipped cells.
821         const BorderValue& rb = current.primaryCell()->parent()->style()->borderStart();
822         if (cb.style() == BHIDDEN || rb.style() == BHIDDEN)
823             continue;
824         allHidden = false;
825         if (cb.style() > BHIDDEN && cb.width() > borderWidth)
826             borderWidth = cb.width();
827         if (rb.style() > BHIDDEN && rb.width() > borderWidth)
828             borderWidth = rb.width();
829     }
830     if (allHidden)
831         return -1;
832
833     return (borderWidth + (table()->style()->isLeftToRightDirection() ? 0 : 1)) / 2;
834 }
835
836 int RenderTableSection::calcOuterBorderEnd() const
837 {
838     unsigned totalCols = table()->numEffCols();
839     if (!m_grid.size() || !totalCols)
840         return 0;
841
842     unsigned borderWidth = 0;
843
844     const BorderValue& sb = style()->borderEnd();
845     if (sb.style() == BHIDDEN)
846         return -1;
847     if (sb.style() > BHIDDEN)
848         borderWidth = sb.width();
849
850     if (RenderTableCol* colGroup = table()->colElement(totalCols - 1)) {
851         const BorderValue& gb = colGroup->style()->borderEnd();
852         if (gb.style() == BHIDDEN)
853             return -1;
854         if (gb.style() > BHIDDEN && gb.width() > borderWidth)
855             borderWidth = gb.width();
856     }
857
858     bool allHidden = true;
859     for (unsigned r = 0; r < m_grid.size(); r++) {
860         const CellStruct& current = cellAt(r, totalCols - 1);
861         if (!current.hasCells())
862             continue;
863         // FIXME: Don't repeat for the same cell
864         const BorderValue& cb = current.primaryCell()->style()->borderEnd(); // FIXME: Make this work with perpendicular and flipped cells.
865         const BorderValue& rb = current.primaryCell()->parent()->style()->borderEnd();
866         if (cb.style() == BHIDDEN || rb.style() == BHIDDEN)
867             continue;
868         allHidden = false;
869         if (cb.style() > BHIDDEN && cb.width() > borderWidth)
870             borderWidth = cb.width();
871         if (rb.style() > BHIDDEN && rb.width() > borderWidth)
872             borderWidth = rb.width();
873     }
874     if (allHidden)
875         return -1;
876
877     return (borderWidth + (table()->style()->isLeftToRightDirection() ? 1 : 0)) / 2;
878 }
879
880 void RenderTableSection::recalcOuterBorder()
881 {
882     m_outerBorderBefore = calcOuterBorderBefore();
883     m_outerBorderAfter = calcOuterBorderAfter();
884     m_outerBorderStart = calcOuterBorderStart();
885     m_outerBorderEnd = calcOuterBorderEnd();
886 }
887
888 int RenderTableSection::firstLineBoxBaseline() const
889 {
890     if (!m_grid.size())
891         return -1;
892
893     int firstLineBaseline = m_grid[0].baseline;
894     if (firstLineBaseline)
895         return firstLineBaseline + m_rowPos[0];
896
897     firstLineBaseline = -1;
898     const Row& firstRow = m_grid[0].row;
899     for (size_t i = 0; i < firstRow.size(); ++i) {
900         const CellStruct& cs = firstRow.at(i);
901         const RenderTableCell* cell = cs.primaryCell();
902         // Only cells with content have a baseline
903         if (cell && cell->contentLogicalHeight())
904             firstLineBaseline = max<int>(firstLineBaseline, cell->logicalTop() + cell->paddingBefore() + cell->borderBefore() + cell->contentLogicalHeight());
905     }
906
907     return firstLineBaseline;
908 }
909
910 void RenderTableSection::paint(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
911 {
912     // put this back in when all layout tests can handle it
913     // ASSERT(!needsLayout());
914     // avoid crashing on bugs that cause us to paint with dirty layout
915     if (needsLayout())
916         return;
917     
918     unsigned totalRows = m_grid.size();
919     unsigned totalCols = table()->columns().size();
920
921     if (!totalRows || !totalCols)
922         return;
923
924     LayoutPoint adjustedPaintOffset = paintOffset + location();
925
926     PaintPhase phase = paintInfo.phase;
927     bool pushedClip = pushContentsClip(paintInfo, adjustedPaintOffset);
928     paintObject(paintInfo, adjustedPaintOffset);
929     if (pushedClip)
930         popContentsClip(paintInfo, phase, adjustedPaintOffset);
931
932     if ((phase == PaintPhaseOutline || phase == PaintPhaseSelfOutline) && style()->visibility() == VISIBLE)
933         paintOutline(paintInfo.context, LayoutRect(adjustedPaintOffset, size()));
934 }
935
936 static inline bool compareCellPositions(RenderTableCell* elem1, RenderTableCell* elem2)
937 {
938     return elem1->rowIndex() < elem2->rowIndex();
939 }
940
941 // This comparison is used only when we have overflowing cells as we have an unsorted array to sort. We thus need
942 // to sort both on rows and columns to properly repaint.
943 static inline bool compareCellPositionsWithOverflowingCells(RenderTableCell* elem1, RenderTableCell* elem2)
944 {
945     if (elem1->rowIndex() != elem2->rowIndex())
946         return elem1->rowIndex() < elem2->rowIndex();
947
948     return elem1->col() < elem2->col();
949 }
950
951 void RenderTableSection::paintCell(RenderTableCell* cell, PaintInfo& paintInfo, const LayoutPoint& paintOffset)
952 {
953     LayoutPoint cellPoint = flipForWritingModeForChild(cell, paintOffset);
954     PaintPhase paintPhase = paintInfo.phase;
955     RenderTableRow* row = toRenderTableRow(cell->parent());
956
957     if (paintPhase == PaintPhaseBlockBackground || paintPhase == PaintPhaseChildBlockBackground) {
958         // We need to handle painting a stack of backgrounds.  This stack (from bottom to top) consists of
959         // the column group, column, row group, row, and then the cell.
960         RenderTableCol* column = table()->colElement(cell->col());
961         RenderTableCol* columnGroup = column ? column->enclosingColumnGroup() : 0;
962
963         // Column groups and columns first.
964         // FIXME: Columns and column groups do not currently support opacity, and they are being painted "too late" in
965         // the stack, since we have already opened a transparency layer (potentially) for the table row group.
966         // Note that we deliberately ignore whether or not the cell has a layer, since these backgrounds paint "behind" the
967         // cell.
968         cell->paintBackgroundsBehindCell(paintInfo, cellPoint, columnGroup);
969         cell->paintBackgroundsBehindCell(paintInfo, cellPoint, column);
970
971         // Paint the row group next.
972         cell->paintBackgroundsBehindCell(paintInfo, cellPoint, this);
973
974         // Paint the row next, but only if it doesn't have a layer.  If a row has a layer, it will be responsible for
975         // painting the row background for the cell.
976         if (!row->hasSelfPaintingLayer())
977             cell->paintBackgroundsBehindCell(paintInfo, cellPoint, row);
978     }
979     if ((!cell->hasSelfPaintingLayer() && !row->hasSelfPaintingLayer()))
980         cell->paint(paintInfo, cellPoint);
981 }
982
983 LayoutRect RenderTableSection::logicalRectForWritingModeAndDirection(const LayoutRect& rect) const
984 {
985     LayoutRect tableAlignedRect(rect);
986
987     flipForWritingMode(tableAlignedRect);
988
989     if (!style()->isHorizontalWritingMode())
990         tableAlignedRect = tableAlignedRect.transposedRect();
991
992     const Vector<int>& columnPos = table()->columnPositions();
993     // FIXME: The table's direction should determine our row's direction, not the section's (see bug 96691).
994     if (!style()->isLeftToRightDirection())
995         tableAlignedRect.setX(columnPos[columnPos.size() - 1] - tableAlignedRect.maxX());
996
997     return tableAlignedRect;
998 }
999
1000 CellSpan RenderTableSection::dirtiedRows(const LayoutRect& damageRect) const
1001 {
1002     if (m_forceSlowPaintPathWithOverflowingCell) 
1003         return fullTableRowSpan();
1004
1005     CellSpan coveredRows = spannedRows(damageRect);
1006
1007     // To repaint the border we might need to repaint first or last row even if they are not spanned themselves.
1008     if (coveredRows.start() >= m_rowPos.size() - 1 && m_rowPos[m_rowPos.size() - 1] + table()->outerBorderAfter() >= damageRect.y())
1009         --coveredRows.start();
1010
1011     if (!coveredRows.end() && m_rowPos[0] - table()->outerBorderBefore() <= damageRect.maxY())
1012         ++coveredRows.end();
1013
1014     return coveredRows;
1015 }
1016
1017 CellSpan RenderTableSection::dirtiedColumns(const LayoutRect& damageRect) const
1018 {
1019     if (m_forceSlowPaintPathWithOverflowingCell) 
1020         return fullTableColumnSpan();
1021
1022     CellSpan coveredColumns = spannedColumns(damageRect);
1023
1024     const Vector<int>& columnPos = table()->columnPositions();
1025     // To repaint the border we might need to repaint first or last column even if they are not spanned themselves.
1026     if (coveredColumns.start() >= columnPos.size() - 1 && columnPos[columnPos.size() - 1] + table()->outerBorderEnd() >= damageRect.x())
1027         --coveredColumns.start();
1028
1029     if (!coveredColumns.end() && columnPos[0] - table()->outerBorderStart() <= damageRect.maxX())
1030         ++coveredColumns.end();
1031
1032     return coveredColumns;
1033 }
1034
1035 CellSpan RenderTableSection::spannedRows(const LayoutRect& flippedRect) const
1036 {
1037     // Find the first row that starts after rect top.
1038     unsigned nextRow = std::upper_bound(m_rowPos.begin(), m_rowPos.end(), flippedRect.y()) - m_rowPos.begin();
1039
1040     if (nextRow == m_rowPos.size())
1041         return CellSpan(m_rowPos.size() - 1, m_rowPos.size() - 1); // After all rows.
1042
1043     unsigned startRow = nextRow > 0 ? nextRow - 1 : 0;
1044
1045     // Find the first row that starts after rect bottom.
1046     unsigned endRow;
1047     if (m_rowPos[nextRow] >= flippedRect.maxY())
1048         endRow = nextRow;
1049     else {
1050         endRow = std::upper_bound(m_rowPos.begin() + nextRow, m_rowPos.end(), flippedRect.maxY()) - m_rowPos.begin();
1051         if (endRow == m_rowPos.size())
1052             endRow = m_rowPos.size() - 1;
1053     }
1054
1055     return CellSpan(startRow, endRow);
1056 }
1057
1058 CellSpan RenderTableSection::spannedColumns(const LayoutRect& flippedRect) const
1059 {
1060     const Vector<int>& columnPos = table()->columnPositions();
1061
1062     // Find the first column that starts after rect left.
1063     // lower_bound doesn't handle the edge between two cells properly as it would wrongly return the
1064     // cell on the logical top/left.
1065     // upper_bound on the other hand properly returns the cell on the logical bottom/right, which also
1066     // matches the behavior of other browsers.
1067     unsigned nextColumn = std::upper_bound(columnPos.begin(), columnPos.end(), flippedRect.x()) - columnPos.begin();
1068
1069     if (nextColumn == columnPos.size())
1070         return CellSpan(columnPos.size() - 1, columnPos.size() - 1); // After all columns.
1071
1072     unsigned startColumn = nextColumn > 0 ? nextColumn - 1 : 0;
1073
1074     // Find the first column that starts after rect right.
1075     unsigned endColumn;
1076     if (columnPos[nextColumn] >= flippedRect.maxX())
1077         endColumn = nextColumn;
1078     else {
1079         endColumn = std::upper_bound(columnPos.begin() + nextColumn, columnPos.end(), flippedRect.maxX()) - columnPos.begin();
1080         if (endColumn == columnPos.size())
1081             endColumn = columnPos.size() - 1;
1082     }
1083
1084     return CellSpan(startColumn, endColumn);
1085 }
1086
1087
1088 void RenderTableSection::paintObject(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
1089 {
1090     PaintPhase paintPhase = paintInfo.phase;
1091
1092     LayoutRect localRepaintRect = paintInfo.rect;
1093     localRepaintRect.moveBy(-paintOffset);
1094     localRepaintRect.inflate(maximalOutlineSize(paintPhase));
1095
1096     LayoutRect tableAlignedRect = logicalRectForWritingModeAndDirection(localRepaintRect);
1097
1098     CellSpan dirtiedRows = this->dirtiedRows(tableAlignedRect);
1099     CellSpan dirtiedColumns = this->dirtiedColumns(tableAlignedRect);
1100
1101     if (dirtiedColumns.start() < dirtiedColumns.end()) {
1102         if (!m_hasMultipleCellLevels && !m_overflowingCells.size()) {
1103             if (paintInfo.phase == PaintPhaseCollapsedTableBorders) {
1104                 // Collapsed borders are painted from the bottom right to the top left so that precedence
1105                 // due to cell position is respected.
1106                 for (unsigned r = dirtiedRows.end(); r > dirtiedRows.start(); r--) {
1107                     unsigned row = r - 1;
1108                     for (unsigned c = dirtiedColumns.end(); c > dirtiedColumns.start(); c--) {
1109                         unsigned col = c - 1;
1110                         CellStruct& current = cellAt(row, col);
1111                         RenderTableCell* cell = current.primaryCell();
1112                         if (!cell || (row > dirtiedRows.start() && primaryCellAt(row - 1, col) == cell) || (col > dirtiedColumns.start() && primaryCellAt(row, col - 1) == cell))
1113                             continue;
1114                         LayoutPoint cellPoint = flipForWritingModeForChild(cell, paintOffset);
1115                         cell->paintCollapsedBorders(paintInfo, cellPoint);
1116                     }
1117                 }
1118             } else {
1119                 // Draw the dirty cells in the order that they appear.
1120                 for (unsigned r = dirtiedRows.start(); r < dirtiedRows.end(); r++) {
1121                     RenderTableRow* row = m_grid[r].rowRenderer;
1122                     if (row && !row->hasSelfPaintingLayer())
1123                         row->paintOutlineForRowIfNeeded(paintInfo, paintOffset);
1124                     for (unsigned c = dirtiedColumns.start(); c < dirtiedColumns.end(); c++) {
1125                         CellStruct& current = cellAt(r, c);
1126                         RenderTableCell* cell = current.primaryCell();
1127                         if (!cell || (r > dirtiedRows.start() && primaryCellAt(r - 1, c) == cell) || (c > dirtiedColumns.start() && primaryCellAt(r, c - 1) == cell))
1128                             continue;
1129                         paintCell(cell, paintInfo, paintOffset);
1130                     }
1131                 }
1132             }
1133         } else {
1134             // The overflowing cells should be scarce to avoid adding a lot of cells to the HashSet.
1135 #ifndef NDEBUG
1136             unsigned totalRows = m_grid.size();
1137             unsigned totalCols = table()->columns().size();
1138             ASSERT(m_overflowingCells.size() < totalRows * totalCols * gMaxAllowedOverflowingCellRatioForFastPaintPath);
1139 #endif
1140
1141             // To make sure we properly repaint the section, we repaint all the overflowing cells that we collected.
1142             Vector<RenderTableCell*> cells;
1143             copyToVector(m_overflowingCells, cells);
1144
1145             HashSet<RenderTableCell*> spanningCells;
1146
1147             for (unsigned r = dirtiedRows.start(); r < dirtiedRows.end(); r++) {
1148                 RenderTableRow* row = m_grid[r].rowRenderer;
1149                 if (row && !row->hasSelfPaintingLayer())
1150                     row->paintOutlineForRowIfNeeded(paintInfo, paintOffset);
1151                 for (unsigned c = dirtiedColumns.start(); c < dirtiedColumns.end(); c++) {
1152                     CellStruct& current = cellAt(r, c);
1153                     if (!current.hasCells())
1154                         continue;
1155                     for (unsigned i = 0; i < current.cells.size(); ++i) {
1156                         if (m_overflowingCells.contains(current.cells[i]))
1157                             continue;
1158
1159                         if (current.cells[i]->rowSpan() > 1 || current.cells[i]->colSpan() > 1) {
1160                             if (spanningCells.contains(current.cells[i]))
1161                                 continue;
1162                             spanningCells.add(current.cells[i]);
1163                         }
1164
1165                         cells.append(current.cells[i]);
1166                     }
1167                 }
1168             }
1169
1170             // Sort the dirty cells by paint order.
1171             if (!m_overflowingCells.size())
1172                 std::stable_sort(cells.begin(), cells.end(), compareCellPositions);
1173             else
1174                 std::sort(cells.begin(), cells.end(), compareCellPositionsWithOverflowingCells);
1175
1176             if (paintInfo.phase == PaintPhaseCollapsedTableBorders) {
1177                 for (unsigned i = cells.size(); i > 0; --i) {
1178                     LayoutPoint cellPoint = flipForWritingModeForChild(cells[i - 1], paintOffset);
1179                     cells[i - 1]->paintCollapsedBorders(paintInfo, cellPoint);
1180                 }
1181             } else {
1182                 for (unsigned i = 0; i < cells.size(); ++i)
1183                     paintCell(cells[i], paintInfo, paintOffset);
1184             }
1185         }
1186     }
1187 }
1188
1189 void RenderTableSection::imageChanged(WrappedImagePtr, const IntRect*)
1190 {
1191     // FIXME: Examine cells and repaint only the rect the image paints in.
1192     repaint();
1193 }
1194
1195 void RenderTableSection::recalcCells()
1196 {
1197     ASSERT(m_needsCellRecalc);
1198     // We reset the flag here to ensure that |addCell| works. This is safe to do as
1199     // fillRowsWithDefaultStartingAtPosition makes sure we match the table's columns
1200     // representation.
1201     m_needsCellRecalc = false;
1202
1203     m_cCol = 0;
1204     m_cRow = 0;
1205     m_grid.clear();
1206
1207     for (RenderObject* row = firstChild(); row; row = row->nextSibling()) {
1208         if (row->isTableRow()) {
1209             unsigned insertionRow = m_cRow;
1210             m_cRow++;
1211             m_cCol = 0;
1212             ensureRows(m_cRow);
1213
1214             RenderTableRow* tableRow = toRenderTableRow(row);
1215             m_grid[insertionRow].rowRenderer = tableRow;
1216             tableRow->setRowIndex(insertionRow);
1217             setRowLogicalHeightToRowStyleLogicalHeightIfNotRelative(m_grid[insertionRow]);
1218
1219             for (RenderObject* cell = row->firstChild(); cell; cell = cell->nextSibling()) {
1220                 if (!cell->isTableCell())
1221                     continue;
1222
1223                 RenderTableCell* tableCell = toRenderTableCell(cell);
1224                 addCell(tableCell, tableRow);
1225             }
1226         }
1227     }
1228
1229     m_grid.shrinkToFit();
1230     setNeedsLayout(true);
1231 }
1232
1233 // FIXME: This function could be made O(1) in certain cases (like for the non-most-constrainive cells' case).
1234 void RenderTableSection::rowLogicalHeightChanged(unsigned rowIndex)
1235 {
1236     if (needsCellRecalc())
1237         return;
1238
1239     setRowLogicalHeightToRowStyleLogicalHeightIfNotRelative(m_grid[rowIndex]);
1240
1241     for (RenderObject* cell = m_grid[rowIndex].rowRenderer->firstChild(); cell; cell = cell->nextSibling()) {
1242         if (!cell->isTableCell())
1243             continue;
1244
1245         updateLogicalHeightForCell(m_grid[rowIndex], toRenderTableCell(cell));
1246     }
1247 }
1248
1249 void RenderTableSection::setNeedsCellRecalc()
1250 {
1251     m_needsCellRecalc = true;
1252     if (RenderTable* t = table())
1253         t->setNeedsSectionRecalc();
1254 }
1255
1256 unsigned RenderTableSection::numColumns() const
1257 {
1258     unsigned result = 0;
1259     
1260     for (unsigned r = 0; r < m_grid.size(); ++r) {
1261         for (unsigned c = result; c < table()->numEffCols(); ++c) {
1262             const CellStruct& cell = cellAt(r, c);
1263             if (cell.hasCells() || cell.inColSpan)
1264                 result = c;
1265         }
1266     }
1267     
1268     return result + 1;
1269 }
1270
1271 const BorderValue& RenderTableSection::borderAdjoiningStartCell(const RenderTableCell* cell) const
1272 {
1273     ASSERT(cell->isFirstOrLastCellInRow());
1274     return hasSameDirectionAs(cell) ? style()->borderStart() : style()->borderEnd();
1275 }
1276
1277 const BorderValue& RenderTableSection::borderAdjoiningEndCell(const RenderTableCell* cell) const
1278 {
1279     ASSERT(cell->isFirstOrLastCellInRow());
1280     return hasSameDirectionAs(cell) ? style()->borderEnd() : style()->borderStart();
1281 }
1282
1283 const RenderTableCell* RenderTableSection::firstRowCellAdjoiningTableStart() const
1284 {
1285     unsigned adjoiningStartCellColumnIndex = hasSameDirectionAs(table()) ? 0 : table()->lastColumnIndex();
1286     return cellAt(0, adjoiningStartCellColumnIndex).primaryCell();
1287 }
1288
1289 const RenderTableCell* RenderTableSection::firstRowCellAdjoiningTableEnd() const
1290 {
1291     unsigned adjoiningEndCellColumnIndex = hasSameDirectionAs(table()) ? table()->lastColumnIndex() : 0;
1292     return cellAt(0, adjoiningEndCellColumnIndex).primaryCell();
1293 }
1294
1295 void RenderTableSection::appendColumn(unsigned pos)
1296 {
1297     ASSERT(!m_needsCellRecalc);
1298
1299     for (unsigned row = 0; row < m_grid.size(); ++row)
1300         m_grid[row].row.resize(pos + 1);
1301 }
1302
1303 void RenderTableSection::splitColumn(unsigned pos, unsigned first)
1304 {
1305     ASSERT(!m_needsCellRecalc);
1306
1307     if (m_cCol > pos)
1308         m_cCol++;
1309     for (unsigned row = 0; row < m_grid.size(); ++row) {
1310         Row& r = m_grid[row].row;
1311         r.insert(pos + 1, CellStruct());
1312         if (r[pos].hasCells()) {
1313             r[pos + 1].cells.append(r[pos].cells);
1314             RenderTableCell* cell = r[pos].primaryCell();
1315             ASSERT(cell);
1316             ASSERT(cell->colSpan() >= (r[pos].inColSpan ? 1u : 0));
1317             unsigned colleft = cell->colSpan() - r[pos].inColSpan;
1318             if (first > colleft)
1319               r[pos + 1].inColSpan = 0;
1320             else
1321               r[pos + 1].inColSpan = first + r[pos].inColSpan;
1322         } else {
1323             r[pos + 1].inColSpan = 0;
1324         }
1325     }
1326 }
1327
1328 // Hit Testing
1329 bool RenderTableSection::nodeAtPoint(const HitTestRequest& request, HitTestResult& result, const HitTestLocation& locationInContainer, const LayoutPoint& accumulatedOffset, HitTestAction action)
1330 {
1331     // If we have no children then we have nothing to do.
1332     if (!firstChild())
1333         return false;
1334
1335     // Table sections cannot ever be hit tested.  Effectively they do not exist.
1336     // Just forward to our children always.
1337     LayoutPoint adjustedLocation = accumulatedOffset + location();
1338
1339     if (hasOverflowClip() && !locationInContainer.intersects(overflowClipRect(adjustedLocation, locationInContainer.region())))
1340         return false;
1341
1342     if (hasOverflowingCell()) {
1343         for (RenderObject* child = lastChild(); child; child = child->previousSibling()) {
1344             // FIXME: We have to skip over inline flows, since they can show up inside table rows
1345             // at the moment (a demoted inline <form> for example). If we ever implement a
1346             // table-specific hit-test method (which we should do for performance reasons anyway),
1347             // then we can remove this check.
1348             if (child->isBox() && !toRenderBox(child)->hasSelfPaintingLayer()) {
1349                 LayoutPoint childPoint = flipForWritingModeForChild(toRenderBox(child), adjustedLocation);
1350                 if (child->nodeAtPoint(request, result, locationInContainer, childPoint, action)) {
1351                     updateHitTestResult(result, toLayoutPoint(locationInContainer.point() - childPoint));
1352                     return true;
1353                 }
1354             }
1355         }
1356         return false;
1357     }
1358
1359     recalcCellsIfNeeded();
1360
1361     LayoutRect hitTestRect = locationInContainer.boundingBox();
1362     hitTestRect.moveBy(-adjustedLocation);
1363
1364     LayoutRect tableAlignedRect = logicalRectForWritingModeAndDirection(hitTestRect);
1365     CellSpan rowSpan = spannedRows(tableAlignedRect);
1366     CellSpan columnSpan = spannedColumns(tableAlignedRect);
1367
1368     // Now iterate over the spanned rows and columns.
1369     for (unsigned hitRow = rowSpan.start(); hitRow < rowSpan.end(); ++hitRow) {
1370         for (unsigned hitColumn = columnSpan.start(); hitColumn < columnSpan.end(); ++hitColumn) {
1371             CellStruct& current = cellAt(hitRow, hitColumn);
1372
1373             // If the cell is empty, there's nothing to do
1374             if (!current.hasCells())
1375                 continue;
1376
1377             for (unsigned i = current.cells.size() ; i; ) {
1378                 --i;
1379                 RenderTableCell* cell = current.cells[i];
1380                 LayoutPoint cellPoint = flipForWritingModeForChild(cell, adjustedLocation);
1381                 if (static_cast<RenderObject*>(cell)->nodeAtPoint(request, result, locationInContainer, cellPoint, action)) {
1382                     updateHitTestResult(result, locationInContainer.point() - toLayoutSize(cellPoint));
1383                     return true;
1384                 }
1385             }
1386             if (!result.isRectBasedTest())
1387                 break;
1388         }
1389         if (!result.isRectBasedTest())
1390             break;
1391     }
1392
1393     return false;
1394 }
1395
1396 void RenderTableSection::removeCachedCollapsedBorders(const RenderTableCell* cell)
1397 {
1398     if (!table()->collapseBorders())
1399         return;
1400     
1401     for (int side = CBSBefore; side <= CBSEnd; ++side)
1402         m_cellsCollapsedBorders.remove(make_pair(cell, side));
1403 }
1404
1405 void RenderTableSection::setCachedCollapsedBorder(const RenderTableCell* cell, CollapsedBorderSide side, CollapsedBorderValue border)
1406 {
1407     ASSERT(table()->collapseBorders());
1408     m_cellsCollapsedBorders.set(make_pair(cell, side), border);
1409 }
1410
1411 CollapsedBorderValue& RenderTableSection::cachedCollapsedBorder(const RenderTableCell* cell, CollapsedBorderSide side)
1412 {
1413     ASSERT(table()->collapseBorders());
1414     HashMap<pair<const RenderTableCell*, int>, CollapsedBorderValue>::iterator it = m_cellsCollapsedBorders.find(make_pair(cell, side));
1415     ASSERT(it != m_cellsCollapsedBorders.end());
1416     return it->value;
1417 }
1418
1419 RenderTableSection* RenderTableSection::createAnonymousWithParentRenderer(const RenderObject* parent)
1420 {
1421     RefPtr<RenderStyle> newStyle = RenderStyle::createAnonymousStyleWithDisplay(parent->style(), TABLE_ROW_GROUP);
1422     RenderTableSection* newSection = new (parent->renderArena()) RenderTableSection(parent->document() /* is anonymous */);
1423     newSection->setStyle(newStyle.release());
1424     return newSection;
1425 }
1426
1427 void RenderTableSection::setLogicalPositionForCell(RenderTableCell* cell, unsigned effectiveColumn) const
1428 {
1429     LayoutPoint oldCellLocation = cell->location();
1430
1431     LayoutPoint cellLocation(0, m_rowPos[cell->rowIndex()]);
1432     int horizontalBorderSpacing = table()->hBorderSpacing();
1433
1434     // FIXME: The table's direction should determine our row's direction, not the section's (see bug 96691).
1435     if (!style()->isLeftToRightDirection())
1436         cellLocation.setX(table()->columnPositions()[table()->numEffCols()] - table()->columnPositions()[table()->colToEffCol(cell->col() + cell->colSpan())] + horizontalBorderSpacing);
1437     else
1438         cellLocation.setX(table()->columnPositions()[effectiveColumn] + horizontalBorderSpacing);
1439
1440     cell->setLogicalLocation(cellLocation);
1441     view()->addLayoutDelta(oldCellLocation - cell->location());
1442 }
1443
1444 void RenderTableSection::reportMemoryUsage(MemoryObjectInfo* memoryObjectInfo) const
1445 {
1446     MemoryClassInfo info(memoryObjectInfo, this, PlatformMemoryTypes::Rendering);
1447     RenderBox::reportMemoryUsage(memoryObjectInfo);
1448     info.addMember(m_children);
1449     info.addMember(m_grid);
1450     info.addMember(m_rowPos);
1451     info.addMember(m_overflowingCells);
1452     info.addMember(m_cellsCollapsedBorders);
1453 }
1454
1455 void RenderTableSection::RowStruct::reportMemoryUsage(MemoryObjectInfo* memoryObjectInfo) const
1456 {
1457     MemoryClassInfo info(memoryObjectInfo, this, PlatformMemoryTypes::Rendering);
1458     info.addMember(row);
1459     info.addMember(rowRenderer);
1460     info.addMember(logicalHeight);
1461 }
1462
1463 void RenderTableSection::CellStruct::reportMemoryUsage(MemoryObjectInfo* memoryObjectInfo) const
1464 {
1465     MemoryClassInfo info(memoryObjectInfo, this, PlatformMemoryTypes::Rendering);
1466     info.addMember(cells);
1467 }
1468
1469 } // namespace WebCore