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