1b63ea57df21802b1031df9b317fc83eea3d7435
[WebKit-https.git] / WebCore / rendering / RenderTable.cpp
1 /**
2  * Copyright (C) 1997 Martin Jones (mjones@kde.org)
3  *           (C) 1997 Torben Weis (weis@kde.org)
4  *           (C) 1998 Waldo Bastian (bastian@kde.org)
5  *           (C) 1999 Lars Knoll (knoll@kde.org)
6  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
7  * Copyright (C) 2003, 2004, 2005, 2006, 2007 Apple Inc. All rights reserved.
8  * Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)
9  *
10  * This library is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU Library General Public
12  * License as published by the Free Software Foundation; either
13  * version 2 of the License, or (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18  * Library General Public License for more details.
19  *
20  * You should have received a copy of the GNU Library General Public License
21  * along with this library; see the file COPYING.LIB.  If not, write to
22  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
23  * Boston, MA 02110-1301, USA.
24  */
25
26 #include "config.h"
27 #include "RenderTable.h"
28
29 #include "AutoTableLayout.h"
30 #include "DeleteButtonController.h"
31 #include "Document.h"
32 #include "FixedTableLayout.h"
33 #include "FrameView.h"
34 #include "HTMLNames.h"
35 #include "RenderLayer.h"
36 #include "RenderTableCell.h"
37 #include "RenderTableCol.h"
38 #include "RenderTableSection.h"
39 #include "RenderView.h"
40 #include "TextStream.h"
41
42 using namespace std;
43
44 namespace WebCore {
45
46 using namespace HTMLNames;
47
48 RenderTable::RenderTable(Node* node)
49     : RenderBlock(node)
50     , m_caption(0)
51     , m_head(0)
52     , m_foot(0)
53     , m_firstBody(0)
54     , m_tableLayout(0)
55     , m_currentBorder(0)
56     , m_frame(Void)
57     , m_rules(None)
58     , m_hasColElements(false)
59     , m_padding(0)
60     , m_needsSectionRecalc(0)
61     , m_hSpacing(0)
62     , m_vSpacing(0)
63     , m_borderLeft(0)
64     , m_borderRight(0)
65 {
66     m_columnPos.fill(0, 2);
67     m_columns.fill(ColumnStruct(), 1);
68 }
69
70 RenderTable::~RenderTable()
71 {
72     delete m_tableLayout;
73 }
74
75 void RenderTable::setStyle(RenderStyle* newStyle)
76 {
77     ETableLayout oldTableLayout = style() ? style()->tableLayout() : TAUTO;
78     RenderBlock::setStyle(newStyle);
79
80     // In the collapsed border model, there is no cell spacing.
81     m_hSpacing = collapseBorders() ? 0 : style()->horizontalBorderSpacing();
82     m_vSpacing = collapseBorders() ? 0 : style()->verticalBorderSpacing();
83     m_columnPos[0] = m_hSpacing;
84
85     if (!m_tableLayout || style()->tableLayout() != oldTableLayout) {
86         delete m_tableLayout;
87
88         // According to the CSS2 spec, you only use fixed table layout if an
89         // explicit width is specified on the table.  Auto width implies auto table layout.
90         if (style()->tableLayout() == TFIXED && !style()->width().isAuto())
91             m_tableLayout = new FixedTableLayout(this);
92         else
93             m_tableLayout = new AutoTableLayout(this);
94     }
95 }
96
97 static inline void resetSectionPointerIfNotBefore(RenderTableSection*& ptr, RenderObject* before)
98 {
99     if (!before || !ptr)
100         return;
101     RenderObject* o = before->previousSibling();
102     while (o && o != ptr)
103         o = o->previousSibling();
104     if (!o)
105         ptr = 0;
106 }
107
108 void RenderTable::addChild(RenderObject* child, RenderObject* beforeChild)
109 {
110     // Make sure we don't append things after :after-generated content if we have it.
111     if (!beforeChild && isAfterContent(lastChild()))
112         beforeChild = lastChild();
113
114     bool wrapInAnonymousSection = true;
115     bool isTableElement = element() && element()->hasTagName(tableTag);
116
117     if (child->isRenderBlock() && child->style()->display() == TABLE_CAPTION) {
118         // First caption wins.
119         if (beforeChild && m_caption) {
120             RenderObject* o = beforeChild->previousSibling();
121             while (o && o != m_caption)
122                 o = o->previousSibling();
123             if (!o)
124                 m_caption = 0;
125         }
126         if (!m_caption)
127             m_caption = static_cast<RenderBlock*>(child);
128         wrapInAnonymousSection = false;
129     } else if (child->isTableCol()) {
130         m_hasColElements = true;
131         wrapInAnonymousSection = false;
132     } else if (child->isTableSection()) {
133         switch (child->style()->display()) {
134             case TABLE_HEADER_GROUP:
135                 if (child->isTableSection()) {
136                     resetSectionPointerIfNotBefore(m_head, beforeChild);
137                     if (!m_head) {
138                         m_head = static_cast<RenderTableSection*>(child);
139                     } else {
140                         resetSectionPointerIfNotBefore(m_firstBody, beforeChild);
141                         if (!m_firstBody) 
142                             m_firstBody = static_cast<RenderTableSection*>(child);
143                     }
144                 }
145                 wrapInAnonymousSection = false;
146                 break;
147             case TABLE_FOOTER_GROUP:
148                 if (child->isTableSection()) {
149                     resetSectionPointerIfNotBefore(m_foot, beforeChild);
150                     if (!m_foot) {
151                         m_foot = static_cast<RenderTableSection*>(child);
152                         wrapInAnonymousSection = false;
153                         break;
154                     }
155                 }
156                 // Fall through.
157             case TABLE_ROW_GROUP:
158                 if (child->isTableSection()) {
159                     resetSectionPointerIfNotBefore(m_firstBody, beforeChild);
160                     if (!m_firstBody)
161                         m_firstBody = static_cast<RenderTableSection*>(child);
162                 }
163                 wrapInAnonymousSection = false;
164                 break;
165             default:
166                 ASSERT_NOT_REACHED();
167         }
168     } else if (child->isTableCell() || child->isTableRow()) {
169         wrapInAnonymousSection = true;
170     } else {
171         // Allow a form to just sit at the top level.
172         wrapInAnonymousSection = !isTableElement || !child->element() || !(child->element()->hasTagName(formTag) && document()->isHTMLDocument());
173
174         // FIXME: Allow the delete button container element to sit at the top level. This is needed until http://bugs.webkit.org/show_bug.cgi?id=11363 is fixed.
175         if (wrapInAnonymousSection && child->element() && child->element()->isHTMLElement() && static_cast<HTMLElement*>(child->element())->id() == DeleteButtonController::containerElementIdentifier)
176             wrapInAnonymousSection = false;
177     }
178
179     if (!wrapInAnonymousSection) {
180         // If the next renderer is actually wrapped in an anonymous table section, we need to go up and find that.
181         while (beforeChild && !beforeChild->isTableSection() && !beforeChild->isTableCol() && beforeChild->style()->display() != TABLE_CAPTION)
182             beforeChild = beforeChild->parent();
183
184         RenderContainer::addChild(child, beforeChild);
185         return;
186     }
187
188     if (!beforeChild && lastChild() && lastChild()->isTableSection() && lastChild()->isAnonymous()) {
189         lastChild()->addChild(child);
190         return;
191     }
192
193     RenderObject* lastBox = beforeChild;
194     RenderObject* nextToLastBox = beforeChild;
195     while (lastBox && lastBox->parent()->isAnonymous() && !lastBox->isTableSection() && lastBox->style()->display() != TABLE_CAPTION) {
196         nextToLastBox = lastBox;
197         lastBox = lastBox->parent();
198     }
199     if (lastBox && lastBox->isAnonymous() && !isAfterContent(lastBox)) {
200         lastBox->addChild(child, nextToLastBox);
201         return;
202     }
203
204     if (beforeChild && !beforeChild->isTableSection() && beforeChild->style()->display() != TABLE_CAPTION)
205         beforeChild = 0;
206     RenderTableSection* section = new (renderArena()) RenderTableSection(document() /* anonymous */);
207     RenderStyle* newStyle = new (renderArena()) RenderStyle();
208     newStyle->inheritFrom(style());
209     newStyle->setDisplay(TABLE_ROW_GROUP);
210     section->setStyle(newStyle);
211     addChild(section, beforeChild);
212     section->addChild(child);
213 }
214
215 void RenderTable::calcWidth()
216 {
217     if (isPositioned())
218         calcAbsoluteHorizontal();
219
220     RenderBlock* cb = containingBlock();
221     int availableWidth = cb->availableWidth();
222
223     LengthType widthType = style()->width().type();
224     if (widthType > Relative && style()->width().isPositive()) {
225         // Percent or fixed table
226         m_width = style()->width().calcMinValue(availableWidth);
227         m_width = max(minPrefWidth(), m_width);
228     } else {
229         // An auto width table should shrink to fit within the line width if necessary in order to 
230         // avoid overlapping floats.
231         availableWidth = cb->lineWidth(m_y);
232         
233         // Subtract out any fixed margins from our available width for auto width tables.
234         int marginTotal = 0;
235         if (!style()->marginLeft().isAuto())
236             marginTotal += style()->marginLeft().calcValue(availableWidth);
237         if (!style()->marginRight().isAuto())
238             marginTotal += style()->marginRight().calcValue(availableWidth);
239             
240         // Subtract out our margins to get the available content width.
241         int availContentWidth = max(0, availableWidth - marginTotal);
242         
243         // Ensure we aren't bigger than our max width or smaller than our min width.
244         m_width = min(availContentWidth, maxPrefWidth());
245     }
246     
247     m_width = max(m_width, minPrefWidth());
248
249     // Finally, with our true width determined, compute our margins for real.
250     m_marginRight = 0;
251     m_marginLeft = 0;
252     calcHorizontalMargins(style()->marginLeft(), style()->marginRight(), availableWidth);
253 }
254
255 void RenderTable::layout()
256 {
257     ASSERT(needsLayout());
258
259     if (layoutOnlyPositionedObjects())
260         return;
261
262     recalcSectionsIfNeeded();
263         
264     IntRect oldBounds;
265     IntRect oldOutlineBox;
266     bool checkForRepaint = checkForRepaintDuringLayout();
267     if (checkForRepaint) {
268         oldBounds = absoluteClippedOverflowRect();
269         oldOutlineBox = absoluteOutlineBox();
270     }
271     
272     view()->pushLayoutState(this, IntSize(m_x, m_y));
273
274     m_height = 0;
275     m_overflowHeight = 0;
276     m_overflowTop = 0;
277     initMaxMarginValues();
278     
279     int oldWidth = m_width;
280     calcWidth();
281
282     if (m_caption && m_width != oldWidth)
283         m_caption->setNeedsLayout(true, false);
284
285     // FIXME: The optimisation below doesn't work since the internal table
286     // layout could have changed.  we need to add a flag to the table
287     // layout that tells us if something has changed in the min max
288     // calculations to do it correctly.
289 //     if ( oldWidth != m_width || columns.size() + 1 != columnPos.size() )
290     m_tableLayout->layout();
291
292     setCellWidths();
293
294     // layout child objects
295     int calculatedHeight = 0;
296     int oldTableTop = m_caption ? m_caption->height() + m_caption->marginTop() + m_caption->marginBottom() : 0;
297
298     RenderObject* child = firstChild();
299     while (child) {
300         // FIXME: What about a form that has a display value that makes it a table section?
301         if (child->needsLayout() && !(child->element() && child->element()->hasTagName(formTag)))
302             child->layout();
303         if (child->isTableSection()) {
304             static_cast<RenderTableSection*>(child)->calcRowHeight();
305             calculatedHeight += static_cast<RenderTableSection*>(child)->layoutRows(0);
306         }
307         child = child->nextSibling();
308     }
309
310     m_overflowWidth = m_width + (collapseBorders() ? outerBorderRight() - borderRight() : 0);
311     m_overflowLeft = collapseBorders() ? borderLeft() - outerBorderLeft() : 0;
312
313     // If any table section moved vertically, we will just repaint everything from that
314     // section down (it is quite unlikely that any of the following sections
315     // did not shift).
316     bool sectionMoved = false;
317     int movedSectionTop = 0;
318
319     // FIXME: Collapse caption margin.
320     if (m_caption && m_caption->style()->captionSide() != CAPBOTTOM) {
321         IntRect captionRect(m_caption->xPos(), m_caption->yPos(), m_caption->width(), m_caption->height());
322
323         m_caption->setPos(m_caption->marginLeft(), m_height);
324         if (!selfNeedsLayout() && m_caption->checkForRepaintDuringLayout())
325             m_caption->repaintDuringLayoutIfMoved(captionRect);
326
327         m_height += m_caption->height() + m_caption->marginTop() + m_caption->marginBottom();
328         m_overflowLeft = min(m_overflowLeft, m_caption->xPos() + m_caption->overflowLeft(false));
329         m_overflowWidth = max(m_overflowWidth, m_caption->xPos() + m_caption->overflowWidth(false));
330         m_overflowTop = min(m_overflowTop, m_caption->yPos() + m_caption->overflowTop(false));
331         m_overflowHeight = max(m_overflowHeight, m_caption->yPos() + m_caption->overflowHeight(false));
332
333         if (m_height != oldTableTop) {
334             sectionMoved = true;
335             movedSectionTop = min(m_height, oldTableTop);
336         }
337     }
338
339     int bpTop = borderTop() + (collapseBorders() ? 0 : paddingTop());
340     int bpBottom = borderBottom() + (collapseBorders() ? 0 : paddingBottom());
341     
342     m_height += bpTop;
343
344     int oldHeight = m_height;
345     if (!isPositioned())
346         calcHeight();
347     m_height = oldHeight;
348
349     Length h = style()->height();
350     int th = 0;
351     if (h.isFixed())
352         // Tables size as though CSS height includes border/padding.
353         th = h.value() - (bpTop + bpBottom);
354     else if (h.isPercent())
355         th = calcPercentageHeight(h);
356     th = max(0, th);
357
358     // layout rows
359     if (th > calculatedHeight) {
360         // we have to redistribute that height to get the constraint correctly
361         // just force the first body to the height needed
362         // FIXME: This should take height constraints on all table sections into account and distribute
363         // accordingly. For now this should be good enough.
364         if (m_firstBody) {
365             m_firstBody->calcRowHeight();
366             m_firstBody->layoutRows(th - calculatedHeight);
367         } else if (!style()->htmlHacks())
368             // Completely empty tables (with no sections or anything) should at least honor specified height
369             // in strict mode.
370             m_height += th;
371     }
372     
373     int bl = borderLeft();
374     if (!collapseBorders())
375         bl += paddingLeft();
376
377     // position the table sections
378     RenderTableSection* section = m_head ? m_head : (m_firstBody ? m_firstBody : m_foot);
379     while (section) {
380         if (!sectionMoved && section->yPos() != m_height) {
381             sectionMoved = true;
382             movedSectionTop = min(m_height, section->yPos()) + section->overflowTop(false);
383         }
384         section->setPos(bl, m_height);
385
386         m_height += section->height();
387         m_overflowLeft = min(m_overflowLeft, section->xPos() + section->overflowLeft(false));
388         m_overflowWidth = max(m_overflowWidth, section->xPos() + section->overflowWidth(false));
389         m_overflowTop = min(m_overflowTop, section->yPos() + section->overflowTop(false));
390         m_overflowHeight = max(m_overflowHeight, section->yPos() + section->overflowHeight(false));
391         section = sectionBelow(section);
392     }
393
394     m_height += bpBottom;
395
396     if (m_caption && m_caption->style()->captionSide() == CAPBOTTOM) {
397         IntRect captionRect(m_caption->xPos(), m_caption->yPos(), m_caption->width(), m_caption->height());
398
399         m_caption->setPos(m_caption->marginLeft(), m_height);
400         if (!selfNeedsLayout() && m_caption->checkForRepaintDuringLayout())
401             m_caption->repaintDuringLayoutIfMoved(captionRect);
402
403         m_height += m_caption->height() + m_caption->marginTop() + m_caption->marginBottom();
404         m_overflowLeft = min(m_overflowLeft, m_caption->xPos() + m_caption->overflowLeft(false));
405         m_overflowWidth = max(m_overflowWidth, m_caption->xPos() + m_caption->overflowWidth(false));
406     }
407
408     if (isPositioned())
409         calcHeight();
410
411     m_overflowHeight = max(m_overflowHeight, m_height);
412
413     // table can be containing block of positioned elements.
414     // FIXME: Only pass true if width or height changed.
415     layoutPositionedObjects(true);
416
417     if (!hasOverflowClip()) {
418         if (ShadowData* boxShadow = style()->boxShadow()) {
419             m_overflowLeft = min(m_overflowLeft, boxShadow->x - boxShadow->blur);
420             m_overflowWidth = max(m_overflowWidth, m_width + boxShadow->x + boxShadow->blur);
421             m_overflowTop = min(m_overflowTop, boxShadow->y - boxShadow->blur);
422             m_overflowHeight = max(m_overflowHeight, m_height + boxShadow->y + boxShadow->blur);
423         }
424     }
425
426     view()->popLayoutState();
427
428     bool didFullRepaint = true;
429     // Repaint with our new bounds if they are different from our old bounds.
430     if (checkForRepaint)
431         didFullRepaint = repaintAfterLayoutIfNeeded(oldBounds, oldOutlineBox);
432     if (!didFullRepaint && sectionMoved) {
433         IntRect repaintRect(m_overflowLeft, movedSectionTop, m_overflowWidth - m_overflowLeft, m_overflowHeight - movedSectionTop);
434         if (FrameView* frameView = view()->frameView())
435             frameView->addRepaintInfo(this, repaintRect);
436     }
437     
438     setNeedsLayout(false);
439 }
440
441 void RenderTable::setCellWidths()
442 {
443     for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
444         if (child->isTableSection())
445             static_cast<RenderTableSection*>(child)->setCellWidths();
446     }
447 }
448
449 void RenderTable::paint(PaintInfo& paintInfo, int tx, int ty)
450 {
451     tx += xPos();
452     ty += yPos();
453
454     PaintPhase paintPhase = paintInfo.phase;
455
456     int os = 2 * maximalOutlineSize(paintPhase);
457     if (ty + overflowTop(false) >= paintInfo.rect.bottom() + os || ty + overflowHeight(false) <= paintInfo.rect.y() - os)
458         return;
459     if (tx + overflowLeft(false) >= paintInfo.rect.right() + os || tx + overflowWidth(false) <= paintInfo.rect.x() - os)
460         return;
461
462     if ((paintPhase == PaintPhaseBlockBackground || paintPhase == PaintPhaseChildBlockBackground) && hasBoxDecorations() && style()->visibility() == VISIBLE)
463         paintBoxDecorations(paintInfo, tx, ty);
464
465     // We're done.  We don't bother painting any children.
466     if (paintPhase == PaintPhaseBlockBackground)
467         return;
468
469     // We don't paint our own background, but we do let the kids paint their backgrounds.
470     if (paintPhase == PaintPhaseChildBlockBackgrounds)
471         paintPhase = PaintPhaseChildBlockBackground;
472     PaintInfo info(paintInfo);
473     info.phase = paintPhase;
474     info.paintingRoot = paintingRootForChildren(paintInfo);
475
476     for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
477         if (!child->hasLayer() && (child->isTableSection() || child == m_caption))
478             child->paint(info, tx, ty);
479     }
480
481     if (collapseBorders() && paintPhase == PaintPhaseChildBlockBackground && style()->visibility() == VISIBLE) {
482         // Collect all the unique border styles that we want to paint in a sorted list.  Once we
483         // have all the styles sorted, we then do individual passes, painting each style of border
484         // from lowest precedence to highest precedence.
485         info.phase = PaintPhaseCollapsedTableBorders;
486         RenderTableCell::CollapsedBorderStyles borderStyles;
487         RenderObject* stop = nextInPreOrderAfterChildren();
488         for (RenderObject* o = firstChild(); o && o != stop; o = o->nextInPreOrder())
489             if (o->isTableCell())
490                 static_cast<RenderTableCell*>(o)->collectBorderStyles(borderStyles);
491         RenderTableCell::sortBorderStyles(borderStyles);
492         size_t count = borderStyles.size();
493         for (size_t i = 0; i < count; ++i) {
494             m_currentBorder = &borderStyles[i];
495             for (RenderObject* child = firstChild(); child; child = child->nextSibling())
496                 if (child->isTableSection())
497                     child->paint(info, tx, ty);
498         }
499         m_currentBorder = 0;
500     }
501 }
502
503 void RenderTable::paintBoxDecorations(PaintInfo& paintInfo, int tx, int ty)
504 {
505     int w = width();
506     int h = height();
507
508     // Account for the caption.
509     if (m_caption) {
510         int captionHeight = (m_caption->height() + m_caption->marginBottom() +  m_caption->marginTop());
511         h -= captionHeight;
512         if (m_caption->style()->captionSide() != CAPBOTTOM)
513             ty += captionHeight;
514     }
515
516     int my = max(ty, paintInfo.rect.y());
517     int mh;
518     if (ty < paintInfo.rect.y())
519         mh = max(0, h - (paintInfo.rect.y() - ty));
520     else
521         mh = min(paintInfo.rect.height(), h);
522
523     paintBoxShadow(paintInfo.context, tx, ty, w, h, style());
524     
525     paintBackground(paintInfo.context, style()->backgroundColor(), style()->backgroundLayers(), my, mh, tx, ty, w, h);
526
527     if (style()->hasBorder() && !collapseBorders())
528         paintBorder(paintInfo.context, tx, ty, w, h, style());
529 }
530
531 void RenderTable::calcPrefWidths()
532 {
533     ASSERT(prefWidthsDirty());
534
535     recalcSectionsIfNeeded();
536     recalcHorizontalBorders();
537
538     m_tableLayout->calcPrefWidths(m_minPrefWidth, m_maxPrefWidth);
539
540     if (m_caption)
541         m_minPrefWidth = max(m_minPrefWidth, m_caption->minPrefWidth());
542
543     setPrefWidthsDirty(false);
544 }
545
546 void RenderTable::splitColumn(int pos, int firstSpan)
547 {
548     // we need to add a new columnStruct
549     int oldSize = m_columns.size();
550     m_columns.resize(oldSize + 1);
551     int oldSpan = m_columns[pos].span;
552     ASSERT(oldSpan > firstSpan);
553     m_columns[pos].span = firstSpan;
554     memmove(m_columns.data() + pos + 1, m_columns.data() + pos, (oldSize - pos) * sizeof(ColumnStruct));
555     m_columns[pos + 1].span = oldSpan - firstSpan;
556
557     // change width of all rows.
558     for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
559         if (child->isTableSection())
560             static_cast<RenderTableSection*>(child)->splitColumn(pos, oldSize + 1);
561     }
562
563     m_columnPos.resize(numEffCols() + 1);
564     setNeedsLayoutAndPrefWidthsRecalc();
565 }
566
567 void RenderTable::appendColumn(int span)
568 {
569     // easy case.
570     int pos = m_columns.size();
571     int newSize = pos + 1;
572     m_columns.resize(newSize);
573     m_columns[pos].span = span;
574
575     // change width of all rows.
576     for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
577         if (child->isTableSection())
578             static_cast<RenderTableSection*>(child)->appendColumn(pos);
579     }
580
581     m_columnPos.resize(numEffCols() + 1);
582     setNeedsLayoutAndPrefWidthsRecalc();
583 }
584
585 RenderTableCol* RenderTable::colElement(int col, bool* startEdge, bool* endEdge) const
586 {
587     if (!m_hasColElements)
588         return 0;
589     RenderObject* child = firstChild();
590     int cCol = 0;
591
592     while (child) {
593         if (child->isTableCol()) {
594             RenderTableCol* colElem = static_cast<RenderTableCol*>(child);
595             int span = colElem->span();
596             if (!colElem->firstChild()) {
597                 int startCol = cCol;
598                 int endCol = cCol + span - 1;
599                 cCol += span;
600                 if (cCol > col) {
601                     if (startEdge)
602                         *startEdge = startCol == col;
603                     if (endEdge)
604                         *endEdge = endCol == col;
605                     return colElem;
606                 }
607             }
608
609             RenderObject* next = child->firstChild();
610             if (!next)
611                 next = child->nextSibling();
612             if (!next && child->parent()->isTableCol())
613                 next = child->parent()->nextSibling();
614             child = next;
615         } else if (child == m_caption)
616             child = child->nextSibling();
617         else
618             break;
619     }
620
621     return 0;
622 }
623
624 void RenderTable::recalcSections() const
625 {
626     m_caption = 0;
627     m_head = 0;
628     m_foot = 0;
629     m_firstBody = 0;
630     m_hasColElements = false;
631
632     // We need to get valid pointers to caption, head, foot and first body again
633     for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
634         switch (child->style()->display()) {
635             case TABLE_CAPTION:
636                 if (!m_caption && child->isRenderBlock()) {
637                     m_caption = static_cast<RenderBlock*>(child);
638                     m_caption->setNeedsLayout(true);
639                 }
640                 break;
641             case TABLE_COLUMN:
642             case TABLE_COLUMN_GROUP:
643                 m_hasColElements = true;
644                 break;
645             case TABLE_HEADER_GROUP:
646                 if (child->isTableSection()) {
647                     RenderTableSection* section = static_cast<RenderTableSection*>(child);
648                     if (!m_head)
649                         m_head = section;
650                     else if (!m_firstBody)
651                         m_firstBody = section;
652                     section->recalcCellsIfNeeded();
653                 }
654                 break;
655             case TABLE_FOOTER_GROUP:
656                 if (child->isTableSection()) {
657                     RenderTableSection* section = static_cast<RenderTableSection*>(child);
658                     if (!m_foot)
659                         m_foot = section;
660                     else if (!m_firstBody)
661                         m_firstBody = section;
662                     section->recalcCellsIfNeeded();
663                 }
664                 break;
665             case TABLE_ROW_GROUP:
666                 if (child->isTableSection()) {
667                     RenderTableSection* section = static_cast<RenderTableSection*>(child);
668                     if (!m_firstBody)
669                         m_firstBody = section;
670                     section->recalcCellsIfNeeded();
671                 }
672                 break;
673             default:
674                 break;
675         }
676     }
677
678     // repair column count (addChild can grow it too much, because it always adds elements to the last row of a section)
679     int maxCols = 0;
680     for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
681         if (child->isTableSection()) {
682             RenderTableSection* section = static_cast<RenderTableSection*>(child);
683             int sectionCols = section->numColumns();
684             if (sectionCols > maxCols)
685                 maxCols = sectionCols;
686         }
687     }
688     
689     m_columns.resize(maxCols);
690     m_columnPos.resize(maxCols + 1);
691
692     ASSERT(selfNeedsLayout());
693
694     m_needsSectionRecalc = false;
695 }
696
697 RenderObject* RenderTable::removeChildNode(RenderObject* child, bool fullRemove)
698 {
699     setNeedsSectionRecalc();
700     return RenderContainer::removeChildNode(child, fullRemove);
701 }
702
703 int RenderTable::calcBorderLeft() const
704 {
705     if (collapseBorders()) {
706         // Determined by the first cell of the first row. See the CSS 2.1 spec, section 17.6.2.
707         if (!numEffCols())
708             return 0;
709
710         unsigned borderWidth = 0;
711
712         const BorderValue& tb = style()->borderLeft();
713         if (tb.style() == BHIDDEN)
714             return 0;
715         if (tb.style() > BHIDDEN)
716             borderWidth = tb.width;
717
718         int leftmostColumn = style()->direction() == RTL ? numEffCols() - 1 : 0;
719         RenderTableCol* colGroup = colElement(leftmostColumn);
720         if (colGroup) {
721             const BorderValue& gb = style()->borderLeft();
722             if (gb.style() == BHIDDEN)
723                 return 0;
724             if (gb.style() > BHIDDEN)
725                 borderWidth = max(borderWidth, static_cast<unsigned>(gb.width));
726         }
727         
728         RenderTableSection* firstNonEmptySection = m_head ? m_head : (m_firstBody ? m_firstBody : m_foot);
729         if (firstNonEmptySection && !firstNonEmptySection->numRows())
730             firstNonEmptySection = sectionBelow(firstNonEmptySection, true);
731         
732         if (firstNonEmptySection) {
733             const BorderValue& sb = firstNonEmptySection->style()->borderLeft();
734             if (sb.style() == BHIDDEN)
735                 return 0;
736
737             if (sb.style() > BHIDDEN)
738                 borderWidth = max(borderWidth, static_cast<unsigned>(sb.width));
739
740             const RenderTableSection::CellStruct& cs = firstNonEmptySection->cellAt(0, leftmostColumn);
741             
742             if (cs.cell) {
743                 const BorderValue& cb = cs.cell->style()->borderLeft();
744                 if (cb.style() == BHIDDEN)
745                     return 0;
746
747                 const BorderValue& rb = cs.cell->parent()->style()->borderLeft();
748                 if (rb.style() == BHIDDEN)
749                     return 0;
750
751                 if (cb.style() > BHIDDEN)
752                     borderWidth = max(borderWidth, static_cast<unsigned>(cb.width));
753                 if (rb.style() > BHIDDEN)
754                     borderWidth = max(borderWidth, static_cast<unsigned>(rb.width));
755             }
756         }
757         return borderWidth / 2;
758     }
759     return RenderBlock::borderLeft();
760 }
761     
762 int RenderTable::calcBorderRight() const
763 {
764     if (collapseBorders()) {
765         // Determined by the last cell of the first row. See the CSS 2.1 spec, section 17.6.2.
766         if (!numEffCols())
767             return 0;
768
769         unsigned borderWidth = 0;
770
771         const BorderValue& tb = style()->borderRight();
772         if (tb.style() == BHIDDEN)
773             return 0;
774         if (tb.style() > BHIDDEN)
775             borderWidth = tb.width;
776
777         int rightmostColumn = style()->direction() == RTL ? 0 : numEffCols() - 1;
778         RenderTableCol* colGroup = colElement(rightmostColumn);
779         if (colGroup) {
780             const BorderValue& gb = style()->borderRight();
781             if (gb.style() == BHIDDEN)
782                 return 0;
783             if (gb.style() > BHIDDEN)
784                 borderWidth = max(borderWidth, static_cast<unsigned>(gb.width));
785         }
786         
787         RenderTableSection* firstNonEmptySection = m_head ? m_head : (m_firstBody ? m_firstBody : m_foot);
788         if (firstNonEmptySection && !firstNonEmptySection->numRows())
789             firstNonEmptySection = sectionBelow(firstNonEmptySection, true);
790         
791         if (firstNonEmptySection) {
792             const BorderValue& sb = firstNonEmptySection->style()->borderRight();
793             if (sb.style() == BHIDDEN)
794                 return 0;
795
796             if (sb.style() > BHIDDEN)
797                 borderWidth = max(borderWidth, static_cast<unsigned>(sb.width));
798
799             const RenderTableSection::CellStruct& cs = firstNonEmptySection->cellAt(0, rightmostColumn);
800             
801             if (cs.cell) {
802                 const BorderValue& cb = cs.cell->style()->borderRight();
803                 if (cb.style() == BHIDDEN)
804                     return 0;
805
806                 const BorderValue& rb = cs.cell->parent()->style()->borderRight();
807                 if (rb.style() == BHIDDEN)
808                     return 0;
809
810                 if (cb.style() > BHIDDEN)
811                     borderWidth = max(borderWidth, static_cast<unsigned>(cb.width));
812                 if (rb.style() > BHIDDEN)
813                     borderWidth = max(borderWidth, static_cast<unsigned>(rb.width));
814             }
815         }
816         return (borderWidth + 1) / 2;
817     }
818     return RenderBlock::borderRight();
819 }
820
821 void RenderTable::recalcHorizontalBorders()
822 {
823     m_borderLeft = calcBorderLeft();
824     m_borderRight = calcBorderRight();
825 }
826
827 int RenderTable::borderTop() const
828 {
829     if (collapseBorders())
830         return outerBorderTop();
831     return RenderBlock::borderTop();
832 }
833
834 int RenderTable::borderBottom() const
835 {
836     if (collapseBorders())
837         return outerBorderBottom();
838     return RenderBlock::borderBottom();
839 }
840
841 int RenderTable::outerBorderTop() const
842 {
843     if (!collapseBorders())
844         return 0;
845     int borderWidth = 0;
846     RenderTableSection* topSection;
847     if (m_head)
848         topSection = m_head;
849     else if (m_firstBody)
850         topSection = m_firstBody;
851     else if (m_foot)
852         topSection = m_foot;
853     else
854         topSection = 0;
855     if (topSection) {
856         borderWidth = topSection->outerBorderTop();
857         if (borderWidth == -1)
858             return 0;   // Overridden by hidden
859     }
860     const BorderValue& tb = style()->borderTop();
861     if (tb.style() == BHIDDEN)
862         return 0;
863     if (tb.style() > BHIDDEN)
864         borderWidth = max(borderWidth, static_cast<int>(tb.width / 2));
865     return borderWidth;
866 }
867
868 int RenderTable::outerBorderBottom() const
869 {
870     if (!collapseBorders())
871         return 0;
872     int borderWidth = 0;
873     RenderTableSection* bottomSection;
874     if (m_foot)
875         bottomSection = m_foot;
876     else {
877         RenderObject* child;
878         for (child = lastChild(); child && !child->isTableSection(); child = child->previousSibling())
879             ;
880         bottomSection = child ? static_cast<RenderTableSection*>(child) : 0;
881     }
882     if (bottomSection) {
883         borderWidth = bottomSection->outerBorderBottom();
884         if (borderWidth == -1)
885             return 0;   // Overridden by hidden
886     }
887     const BorderValue& tb = style()->borderBottom();
888     if (tb.style() == BHIDDEN)
889         return 0;
890     if (tb.style() > BHIDDEN)
891         borderWidth = max(borderWidth, static_cast<int>((tb.width + 1) / 2));
892     return borderWidth;
893 }
894
895 int RenderTable::outerBorderLeft() const
896 {
897     if (!collapseBorders())
898         return 0;
899
900     int borderWidth = 0;
901
902     const BorderValue& tb = style()->borderLeft();
903     if (tb.style() == BHIDDEN)
904         return 0;
905     if (tb.style() > BHIDDEN)
906         borderWidth = tb.width / 2;
907
908     bool allHidden = true;
909     for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
910         if (!child->isTableSection())
911             continue;
912         int sw = static_cast<RenderTableSection*>(child)->outerBorderLeft();
913         if (sw == -1)
914             continue;
915         else
916             allHidden = false;
917         borderWidth = max(borderWidth, sw);
918     }
919     if (allHidden)
920         return 0;
921
922     return borderWidth;
923 }
924
925 int RenderTable::outerBorderRight() const
926 {
927     if (!collapseBorders())
928         return 0;
929
930     int borderWidth = 0;
931
932     const BorderValue& tb = style()->borderRight();
933     if (tb.style() == BHIDDEN)
934         return 0;
935     if (tb.style() > BHIDDEN)
936         borderWidth = (tb.width + 1) / 2;
937
938     bool allHidden = true;
939     for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
940         if (!child->isTableSection())
941             continue;
942         int sw = static_cast<RenderTableSection*>(child)->outerBorderRight();
943         if (sw == -1)
944             continue;
945         else
946             allHidden = false;
947         borderWidth = max(borderWidth, sw);
948     }
949     if (allHidden)
950         return 0;
951
952     return borderWidth;
953 }
954
955 RenderTableSection* RenderTable::sectionAbove(const RenderTableSection* section, bool skipEmptySections) const
956 {
957     recalcSectionsIfNeeded();
958
959     if (section == m_head)
960         return 0;
961
962     RenderObject* prevSection = section == m_foot ? lastChild() : section->previousSibling();
963     while (prevSection) {
964         if (prevSection->isTableSection() && prevSection != m_head && prevSection != m_foot && (!skipEmptySections || static_cast<RenderTableSection*>(prevSection)->numRows()))
965             break;
966         prevSection = prevSection->previousSibling();
967     }
968     if (!prevSection && m_head && (!skipEmptySections || m_head->numRows()))
969         prevSection = m_head;
970     return static_cast<RenderTableSection*>(prevSection);
971 }
972
973 RenderTableSection* RenderTable::sectionBelow(const RenderTableSection* section, bool skipEmptySections) const
974 {
975     recalcSectionsIfNeeded();
976
977     if (section == m_foot)
978         return 0;
979
980     RenderObject* nextSection = section == m_head ? firstChild() : section->nextSibling();
981     while (nextSection) {
982         if (nextSection->isTableSection() && nextSection != m_head && nextSection != m_foot && (!skipEmptySections || static_cast<RenderTableSection*>(nextSection)->numRows()))
983             break;
984         nextSection = nextSection->nextSibling();
985     }
986     if (!nextSection && m_foot && (!skipEmptySections || m_foot->numRows()))
987         nextSection = m_foot;
988     return static_cast<RenderTableSection*>(nextSection);
989 }
990
991 RenderTableCell* RenderTable::cellAbove(const RenderTableCell* cell) const
992 {
993     recalcSectionsIfNeeded();
994
995     // Find the section and row to look in
996     int r = cell->row();
997     RenderTableSection* section = 0;
998     int rAbove = 0;
999     if (r > 0) {
1000         // cell is not in the first row, so use the above row in its own section
1001         section = cell->section();
1002         rAbove = r - 1;
1003     } else {
1004         section = sectionAbove(cell->section(), true);
1005         if (section)
1006             rAbove = section->numRows() - 1;
1007     }
1008
1009     // Look up the cell in the section's grid, which requires effective col index
1010     if (section) {
1011         int effCol = colToEffCol(cell->col());
1012         RenderTableSection::CellStruct aboveCell;
1013         // If we hit a span back up to a real cell.
1014         do {
1015             aboveCell = section->cellAt(rAbove, effCol);
1016             effCol--;
1017         } while (!aboveCell.cell && aboveCell.inColSpan && effCol >= 0);
1018         return aboveCell.cell;
1019     } else
1020         return 0;
1021 }
1022
1023 RenderTableCell* RenderTable::cellBelow(const RenderTableCell* cell) const
1024 {
1025     recalcSectionsIfNeeded();
1026
1027     // Find the section and row to look in
1028     int r = cell->row() + cell->rowSpan() - 1;
1029     RenderTableSection* section = 0;
1030     int rBelow = 0;
1031     if (r < cell->section()->numRows() - 1) {
1032         // The cell is not in the last row, so use the next row in the section.
1033         section = cell->section();
1034         rBelow = r + 1;
1035     } else {
1036         section = sectionBelow(cell->section(), true);
1037         if (section)
1038             rBelow = 0;
1039     }
1040
1041     // Look up the cell in the section's grid, which requires effective col index
1042     if (section) {
1043         int effCol = colToEffCol(cell->col());
1044         RenderTableSection::CellStruct belowCell;
1045         // If we hit a colspan back up to a real cell.
1046         do {
1047             belowCell = section->cellAt(rBelow, effCol);
1048             effCol--;
1049         } while (!belowCell.cell && belowCell.inColSpan && effCol >= 0);
1050         return belowCell.cell;
1051     } else
1052         return 0;
1053 }
1054
1055 RenderTableCell* RenderTable::cellBefore(const RenderTableCell* cell) const
1056 {
1057     recalcSectionsIfNeeded();
1058
1059     RenderTableSection* section = cell->section();
1060     int effCol = colToEffCol(cell->col());
1061     if (!effCol)
1062         return 0;
1063     
1064     // If we hit a colspan back up to a real cell.
1065     RenderTableSection::CellStruct prevCell;
1066     do {
1067         prevCell = section->cellAt(cell->row(), effCol - 1);
1068         effCol--;
1069     } while (!prevCell.cell && prevCell.inColSpan && effCol >= 0);
1070     return prevCell.cell;
1071 }
1072
1073 RenderTableCell* RenderTable::cellAfter(const RenderTableCell* cell) const
1074 {
1075     recalcSectionsIfNeeded();
1076
1077     int effCol = colToEffCol(cell->col() + cell->colSpan());
1078     if (effCol >= numEffCols())
1079         return 0;
1080     return cell->section()->cellAt(cell->row(), effCol).cell;
1081 }
1082
1083 RenderBlock* RenderTable::firstLineBlock() const
1084 {
1085     return 0;
1086 }
1087
1088 void RenderTable::updateFirstLetter()
1089 {
1090 }
1091
1092 IntRect RenderTable::getOverflowClipRect(int tx, int ty)
1093 {
1094     IntRect rect = RenderBlock::getOverflowClipRect(tx, ty);
1095     
1096     // If we have a caption, expand the clip to include the caption.
1097     // FIXME: Technically this is wrong, but it's virtually impossible to fix this
1098     // for real until captions have been re-written.
1099     // FIXME: This code assumes (like all our other caption code) that only top/bottom are
1100     // supported.  When we actually support left/right and stop mapping them to top/bottom,
1101     // we might have to hack this code first (depending on what order we do these bug fixes in).
1102     if (m_caption) {
1103         rect.setHeight(height());
1104         rect.setY(ty);
1105     }
1106
1107     return rect;
1108 }
1109
1110 #ifndef NDEBUG
1111 void RenderTable::dump(TextStream* stream, DeprecatedString ind) const
1112 {
1113     if (m_caption)
1114         *stream << " tCaption";
1115     if (m_head)
1116         *stream << " head";
1117     if (m_foot)
1118         *stream << " foot";
1119
1120     *stream << endl << ind << "cspans:";
1121     for (unsigned i = 0; i < m_columns.size(); i++)
1122         *stream << " " << m_columns[i].span;
1123     *stream << endl << ind;
1124
1125     RenderBlock::dump(stream, ind);
1126 }
1127 #endif
1128
1129 }