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