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