18ff50c33e75eb84a435d14450badd5087b9c5e2
[WebKit-https.git] / WebCore / khtml / rendering / render_table.cpp
1 /**
2  * This file is part of the DOM implementation for KDE.
3  *
4  * Copyright (C) 1997 Martin Jones (mjones@kde.org)
5  *           (C) 1997 Torben Weis (weis@kde.org)
6  *           (C) 1998 Waldo Bastian (bastian@kde.org)
7  *           (C) 1999 Lars Knoll (knoll@kde.org)
8  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
9  * Copyright (C) 2003 Apple Computer, Inc.
10  *
11  * This library is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU Library General Public
13  * License as published by the Free Software Foundation; either
14  * version 2 of the License, or (at your option) any later version.
15  *
16  * This library is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
19  * Library General Public License for more details.
20  *
21  * You should have received a copy of the GNU Library General Public License
22  * along with this library; see the file COPYING.LIB.  If not, write to
23  * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
24  * Boston, MA 02111-1307, USA.
25  */
26
27 //#define TABLE_DEBUG
28 //#define TABLE_PRINT
29 //#define DEBUG_LAYOUT
30 //#define BOX_DEBUG
31 #include "rendering/render_table.h"
32 #include "rendering/table_layout.h"
33 #include "html/html_tableimpl.h"
34 #include "misc/htmltags.h"
35 #include "misc/htmlattrs.h"
36 #include "xml/dom_docimpl.h"
37
38 #include <kglobal.h>
39
40 #include <qapplication.h>
41 #include <qstyle.h>
42
43 #include <kdebug.h>
44 #include <assert.h>
45
46 #include "khtmlview.h"
47
48 using namespace khtml;
49 using namespace DOM;
50
51 RenderTable::RenderTable(DOM::NodeImpl* node)
52     : RenderBlock(node)
53 {
54
55     tCaption = 0;
56     head = foot = firstBody = 0;
57     tableLayout = 0;
58     m_currentBorder = 0;
59     
60     rules = None;
61     frame = Void;
62     has_col_elems = false;
63     hspacing = 0;
64     vspacing = 0;
65     padding = 0;
66     needSectionRecalc = false;
67     padding = 0;
68
69     columnPos.resize( 2 );
70     columnPos.fill( 0 );
71     columns.resize( 1 );
72     columns.fill( ColumnStruct() );
73
74     columnPos[0] = 0;
75 }
76
77 RenderTable::~RenderTable()
78 {
79     delete tableLayout;
80 }
81
82 void RenderTable::setStyle(RenderStyle *_style)
83 {
84     ETableLayout oldTableLayout = style() ? style()->tableLayout() : TAUTO;
85     RenderBlock::setStyle(_style);
86
87     // In the collapsed border model, there is no cell spacing.
88     hspacing = collapseBorders() ? 0 : style()->horizontalBorderSpacing();
89     vspacing = collapseBorders() ? 0 : style()->verticalBorderSpacing();
90     columnPos[0] = hspacing;
91
92     if ( !tableLayout || style()->tableLayout() != oldTableLayout ) {
93         delete tableLayout;
94
95         // According to the CSS2 spec, you only use fixed table layout if an
96         // explicit width is specified on the table.  Auto width implies auto table layout.
97         if (style()->tableLayout() == TFIXED && !style()->width().isVariable()) {
98             tableLayout = new FixedTableLayout(this);
99 #ifdef DEBUG_LAYOUT
100             kdDebug( 6040 ) << "using fixed table layout" << endl;
101 #endif
102         } else
103             tableLayout = new AutoTableLayout(this);
104     }
105 }
106
107 void RenderTable::addChild(RenderObject *child, RenderObject *beforeChild)
108 {
109 #ifdef DEBUG_LAYOUT
110     kdDebug( 6040 ) << renderName() << "(Table)::addChild( " << child->renderName() << ", " <<
111                        (beforeChild ? beforeChild->renderName() : "0") << " )" << endl;
112 #endif
113     RenderObject *o = child;
114
115     if (child->element() && child->element()->id() == ID_FORM) {
116         RenderContainer::addChild(child,beforeChild);
117         return;
118     }
119
120     switch(child->style()->display())
121     {
122     case TABLE_CAPTION:
123         tCaption = static_cast<RenderBlock *>(child);
124         break;
125     case TABLE_COLUMN:
126     case TABLE_COLUMN_GROUP:
127         has_col_elems = true;
128         break;
129     case TABLE_HEADER_GROUP:
130         if ( !head )
131             head = static_cast<RenderTableSection *>(child);
132         else if ( !firstBody )
133             firstBody = static_cast<RenderTableSection *>(child);
134         break;
135     case TABLE_FOOTER_GROUP:
136         if ( !foot ) {
137             foot = static_cast<RenderTableSection *>(child);
138             break;
139         }
140         // fall through
141     case TABLE_ROW_GROUP:
142         if(!firstBody)
143             firstBody = static_cast<RenderTableSection *>(child);
144         break;
145     default:
146         if ( !beforeChild && lastChild() &&
147              lastChild()->isTableSection() && lastChild()->isAnonymous() ) {
148             o = lastChild();
149         } else {
150             RenderObject *lastBox = beforeChild;
151             while ( lastBox && lastBox->parent()->isAnonymous() &&
152                     !lastBox->isTableSection() && lastBox->style()->display() != TABLE_CAPTION )
153                 lastBox = lastBox->parent();
154             if ( lastBox && lastBox->isAnonymous() ) {
155                 lastBox->addChild( child, beforeChild );
156                 return;
157             } else {
158                 if ( beforeChild && !beforeChild->isTableSection() )
159                     beforeChild = 0;
160                 //kdDebug( 6040 ) << this <<" creating anonymous table section beforeChild="<< beforeChild << endl;
161                 o = new (renderArena()) RenderTableSection(document() /* anonymous */);
162                 RenderStyle *newStyle = new (renderArena()) RenderStyle();
163                 newStyle->inheritFrom(style());
164                 newStyle->setDisplay(TABLE_ROW_GROUP);
165                 o->setStyle(newStyle);
166                 addChild(o, beforeChild);
167             }
168         }
169         o->addChild(child);
170         child->setNeedsLayoutAndMinMaxRecalc();
171         return;
172     }
173     RenderContainer::addChild(child,beforeChild);
174 }
175
176
177
178 void RenderTable::calcWidth()
179 {
180     if ( isPositioned() ) {
181         calcAbsoluteHorizontal();
182     }
183
184     RenderBlock *cb = containingBlock();
185     int availableWidth = cb->contentWidth();
186
187     LengthType widthType = style()->width().type;
188     if (widthType > Relative && style()->width().value > 0) {
189         // Percent or fixed table
190         m_width = style()->width().minWidth( availableWidth );
191         if(m_minWidth > m_width) m_width = m_minWidth;
192     }
193     else {
194         // An auto width table should shrink to fit within the line width if necessary in order to 
195         // avoid overlapping floats.
196         availableWidth = cb->lineWidth( m_y );
197         
198         // Subtract out any fixed margins from our available width for auto width tables.
199         int marginTotal = 0;
200         if (style()->marginLeft().type != Variable)
201             marginTotal += style()->marginLeft().width(availableWidth);
202         if (style()->marginRight().type != Variable)
203             marginTotal += style()->marginRight().width(availableWidth);
204             
205         // Subtract out our margins to get the available content width.
206         int availContentWidth = kMax(0, availableWidth - marginTotal);
207         
208         // Ensure we aren't bigger than our max width or smaller than our min width.
209         m_width = kMin(availContentWidth, m_maxWidth);
210     }
211     
212     m_width = kMax(m_width, m_minWidth);
213
214     // Finally, with our true width determined, compute our margins for real.
215     m_marginRight = 0;
216     m_marginLeft = 0;
217     calcHorizontalMargins(style()->marginLeft(),style()->marginRight(),availableWidth);
218 }
219
220 void RenderTable::layout()
221 {
222     KHTMLAssert( needsLayout() );
223     KHTMLAssert( minMaxKnown() );
224     KHTMLAssert( !needSectionRecalc );
225
226     if (posChildNeedsLayout() && !normalChildNeedsLayout() && !selfNeedsLayout()) {
227         // All we have to is lay out our positioned objects.
228         layoutPositionedObjects(true);
229         setNeedsLayout(false);
230         return;
231     }
232
233     QRect oldBounds, oldFullBounds;
234     bool checkForRepaint = checkForRepaintDuringLayout();
235     if (checkForRepaint)
236         getAbsoluteRepaintRectIncludingFloats(oldBounds, oldFullBounds);
237     
238     //kdDebug( 6040 ) << renderName() << "(Table)"<< this << " ::layout0() width=" << width() << ", needsLayout=" << needsLayout() << endl;
239     
240     m_height = m_overflowHeight = 0;
241     initMaxMarginValues();
242     
243     //int oldWidth = m_width;
244     calcWidth();
245     m_overflowWidth = m_width;
246
247     // the optimisation below doesn't work since the internal table
248     // layout could have changed.  we need to add a flag to the table
249     // layout that tells us if something has changed in the min max
250     // calculations to do it correctly.
251 //     if ( oldWidth != m_width || columns.size() + 1 != columnPos.size() )
252     tableLayout->layout();
253
254 #ifdef DEBUG_LAYOUT
255     kdDebug( 6040 ) << renderName() << "(Table)::layout1() width=" << width() << ", marginLeft=" << marginLeft() << " marginRight=" << marginRight() << endl;
256 #endif
257
258     setCellWidths();
259
260     // layout child objects
261     int calculatedHeight = 0;
262
263     RenderObject *child = firstChild();
264     while( child ) {
265         if ( child->needsLayout() && !(child->element() && child->element()->id() == ID_FORM))
266             child->layout();
267         if ( child->isTableSection() ) {
268             static_cast<RenderTableSection *>(child)->calcRowHeight();
269             calculatedHeight += static_cast<RenderTableSection *>(child)->layoutRows( 0 );
270         }
271         child = child->nextSibling();
272     }
273
274     // ### collapse caption margin
275     if(tCaption && tCaption->style()->captionSide() != CAPBOTTOM) {
276         tCaption->setPos(tCaption->marginLeft(), m_height);
277         m_height += tCaption->height() + tCaption->marginTop() + tCaption->marginBottom();
278     }
279
280     int bpTop = borderTop() + (collapseBorders() ? 0 : paddingTop());
281     int bpBottom = borderBottom() + (collapseBorders() ? 0 : paddingBottom());
282     
283     m_height += bpTop;
284
285     int oldHeight = m_height;
286     calcHeight();
287     int newHeight = m_height;
288     m_height = oldHeight;
289
290     Length h = style()->height();
291     int th = 0;
292     if (isPositioned())
293         th = newHeight; // FIXME: Leave this alone for now but investigate later.
294     else if (h.isFixed())
295         th = h.value - (bpTop + bpBottom);  // Tables size as though CSS height includes border/padding.
296     else if (h.isPercent())
297         th = calcPercentageHeight(h);
298     th = kMax(0, th);
299
300     // layout rows
301     if ( th > calculatedHeight ) {
302         // we have to redistribute that height to get the constraint correctly
303         // just force the first body to the height needed
304         // ### FIXME This should take height constraints on all table sections into account and distribute
305         // accordingly. For now this should be good enough
306         if (firstBody) {
307             firstBody->calcRowHeight();
308             firstBody->layoutRows( th - calculatedHeight );
309         }
310     }
311     
312     int bl = borderLeft();
313     if (!collapseBorders())
314         bl += paddingLeft();
315
316     // position the table sections
317     if ( head ) {
318         head->setPos(bl, m_height);
319         m_height += head->height();
320     }
321     RenderObject *body = firstBody;
322     while ( body ) {
323         if ( body != head && body != foot && body->isTableSection() ) {
324             body->setPos(bl, m_height);
325             m_height += body->height();
326         }
327         body = body->nextSibling();
328     }
329     if ( foot ) {
330         foot->setPos(bl, m_height);
331         m_height += foot->height();
332     }
333
334     m_height += bpBottom;
335                
336     if(tCaption && tCaption->style()->captionSide()==CAPBOTTOM) {
337         tCaption->setPos(tCaption->marginLeft(), m_height);
338         m_height += tCaption->height() + tCaption->marginTop() + tCaption->marginBottom();
339     }
340
341     //kdDebug(0) << "table height: " << m_height << endl;
342
343     // table can be containing block of positioned elements.
344     // ### only pass true if width or height changed.
345     layoutPositionedObjects( true );
346
347     // Repaint with our new bounds if they are different from our old bounds.
348     if (checkForRepaint)
349         repaintAfterLayoutIfNeeded(oldBounds, oldFullBounds);
350     
351     m_overflowHeight = kMax(m_overflowHeight, m_height);
352     m_overflowWidth = kMax(m_overflowWidth, m_width);
353
354     setNeedsLayout(false);
355 }
356
357 void RenderTable::setCellWidths()
358 {
359 #ifdef DEBUG_LAYOUT
360     kdDebug( 6040 ) << renderName() << "(Table, this=0x" << this << ")::setCellWidths()" << endl;
361 #endif
362
363     RenderObject *child = firstChild();
364     while( child ) {
365         if ( child->isTableSection() )
366             static_cast<RenderTableSection *>(child)->setCellWidths();
367         child = child->nextSibling();
368     }
369 }
370
371 void RenderTable::paint(PaintInfo& i, int _tx, int _ty)
372 {
373     _tx += xPos();
374     _ty += yPos();
375
376     PaintAction paintAction = i.phase;
377     
378 #ifdef TABLE_PRINT
379     kdDebug( 6040 ) << "RenderTable::paint() w/h = (" << width() << "/" << height() << ")" << endl;
380 #endif
381     
382     int os = 2*maximalOutlineSize(paintAction);
383     if ((_ty >= i.r.y() + i.r.height() + os) || (_ty + height() <= i.r.y() - os)) return;
384     if ((_tx >= i.r.x() + i.r.width() + os) || (_tx + width() <= i.r.x() - os)) return;
385
386 #ifdef TABLE_PRINT
387     kdDebug( 6040 ) << "RenderTable::paint(2) " << _tx << "/" << _ty << " (" << _y << "/" << _h << ")" << endl;
388 #endif
389
390     if ((paintAction == PaintActionBlockBackground || paintAction == PaintActionChildBlockBackground)
391         && shouldPaintBackgroundOrBorder() && style()->visibility() == VISIBLE)
392         paintBoxDecorations(i, _tx, _ty);
393
394     // We're done.  We don't bother painting any children.
395     if (paintAction == PaintActionBlockBackground)
396         return;
397     // We don't paint our own background, but we do let the kids paint their backgrounds.
398     if (paintAction == PaintActionChildBlockBackgrounds)
399         paintAction = PaintActionChildBlockBackground;
400     PaintInfo paintInfo(i.p, i.r, paintAction, paintingRootForChildren(i));
401     
402     for (RenderObject *child = firstChild(); child; child = child->nextSibling())
403         if (child->isTableSection() || child == tCaption)
404             child->paint(paintInfo, _tx, _ty);
405
406     if (collapseBorders() && paintAction == PaintActionChildBlockBackground && style()->visibility() == VISIBLE) {
407         // Collect all the unique border styles that we want to paint in a sorted list.  Once we
408         // have all the styles sorted, we then do individual passes, painting each style of border
409         // from lowest precedence to highest precedence.
410         paintInfo.phase = PaintActionCollapsedTableBorders;
411         QValueList<CollapsedBorderValue> borderStyles;
412         collectBorders(borderStyles);
413         QValueListIterator<CollapsedBorderValue> it = borderStyles.begin();
414         QValueListIterator<CollapsedBorderValue> end = borderStyles.end();
415         for (; it != end; ++it) {
416             m_currentBorder = &(*it);
417             for (RenderObject* child = firstChild(); child; child = child->nextSibling())
418                 if (child->isTableSection())
419                     child->paint(paintInfo, _tx, _ty);
420         }
421     }
422         
423 #ifdef BOX_DEBUG
424     outlineBox(i.p, _tx, _ty, "blue");
425 #endif
426 }
427
428 void RenderTable::paintBoxDecorations(PaintInfo& i, int _tx, int _ty)
429 {
430     int w = width();
431     int h = height();
432     
433     // Account for the caption.
434     if (tCaption) {
435         int captionHeight = (tCaption->height() + tCaption->marginBottom() +  tCaption->marginTop());
436         h -= captionHeight;
437         if (tCaption->style()->captionSide() != CAPBOTTOM)
438             _ty += captionHeight;
439     }
440
441     int my = kMax(_ty, i.r.y());
442     int mh;
443     if (_ty < i.r.y())
444         mh= kMax(0, h - (i.r.y() - _ty));
445     else
446         mh = kMin(i.r.height(), h);
447     
448     paintBackground(i.p, style()->backgroundColor(), style()->backgroundLayers(), my, mh, _tx, _ty, w, h);
449     
450     if (style()->hasBorder() && !collapseBorders())
451         paintBorder(i.p, _tx, _ty, w, h, style());
452 }
453
454 void RenderTable::calcMinMaxWidth()
455 {
456     KHTMLAssert( !minMaxKnown() );
457
458     if ( needSectionRecalc )
459         recalcSections();
460
461 #ifdef DEBUG_LAYOUT
462     kdDebug( 6040 ) << renderName() << "(Table " << this << ")::calcMinMaxWidth()" <<  endl;
463 #endif
464
465     tableLayout->calcMinMaxWidth();
466
467     if (tCaption && tCaption->minWidth() > m_minWidth)
468         m_minWidth = tCaption->minWidth();
469
470     setMinMaxKnown();
471 #ifdef DEBUG_LAYOUT
472     kdDebug( 6040 ) << renderName() << " END: (Table " << this << ")::calcMinMaxWidth() min = " << m_minWidth << " max = " << m_maxWidth <<  endl;
473 #endif
474 }
475
476 void RenderTable::splitColumn( int pos, int firstSpan )
477 {
478     // we need to add a new columnStruct
479     int oldSize = columns.size();
480     columns.resize( oldSize + 1 );
481     int oldSpan = columns[pos].span;
482 //     qDebug("splitColumn( %d,%d ), oldSize=%d, oldSpan=%d", pos, firstSpan, oldSize, oldSpan );
483     KHTMLAssert( oldSpan > firstSpan );
484     columns[pos].span = firstSpan;
485     memmove( columns.data()+pos+1, columns.data()+pos, (oldSize-pos)*sizeof(ColumnStruct) );
486     columns[pos+1].span = oldSpan - firstSpan;
487
488     // change width of all rows.
489     RenderObject *child = firstChild();
490     while ( child ) {
491         if ( child->isTableSection() ) {
492             RenderTableSection *section = static_cast<RenderTableSection *>(child);
493             int size = section->numRows();
494             int row = 0;
495             if ( section->cCol > pos )
496                 section->cCol++;
497             while ( row < size ) {
498                 section->grid[row].row->resize( oldSize+1 );
499                 RenderTableSection::Row &r = *section->grid[row].row;
500                 memmove( r.data()+pos+1, r.data()+pos, (oldSize-pos)*sizeof( RenderTableCell * ) );
501 //              qDebug("moving from %d to %d, num=%d", pos, pos+1, (oldSize-pos-1) );
502                 r[pos+1] = r[pos] ? (RenderTableCell *)-1 : 0;
503                 row++;
504             }
505         }
506         child = child->nextSibling();
507     }
508     columnPos.resize( numEffCols()+1 );
509     setNeedsLayoutAndMinMaxRecalc();
510 }
511
512 void RenderTable::appendColumn( int span )
513 {
514     // easy case.
515     int pos = columns.size();
516 //     qDebug("appendColumn( %d ), size=%d", span, pos );
517     int newSize = pos + 1;
518     columns.resize( newSize );
519     columns[pos].span = span;
520     //qDebug("appending column at %d, span %d", pos,  span );
521
522     // change width of all rows.
523     RenderObject *child = firstChild();
524     while ( child ) {
525         if ( child->isTableSection() ) {
526             RenderTableSection *section = static_cast<RenderTableSection *>(child);
527             int size = section->numRows();
528             int row = 0;
529             while ( row < size ) {
530                 section->grid[row].row->resize( newSize );
531                 section->cellAt( row, pos ) = 0;
532                 row++;
533             }
534
535         }
536         child = child->nextSibling();
537     }
538     columnPos.resize( numEffCols()+1 );
539     setNeedsLayoutAndMinMaxRecalc();
540 }
541
542 RenderTableCol *RenderTable::colElement( int col ) {
543     if ( !has_col_elems )
544         return 0;
545     RenderObject *child = firstChild();
546     int cCol = 0;
547     while ( child ) {
548         if ( child->isTableCol() ) {
549             RenderTableCol *colElem = static_cast<RenderTableCol *>(child);
550             int span = colElem->span();
551             if ( !colElem->firstChild() ) {
552                 cCol += span;
553                 if ( cCol > col )
554                     return colElem;
555             }
556
557             RenderObject *next = child->firstChild();
558             if ( !next )
559                 next = child->nextSibling();
560             if ( !next && child->parent()->isTableCol() )
561                 next = child->parent()->nextSibling();
562             child = next;
563         } else
564             break;
565     }
566     return 0;
567 }
568
569 void RenderTable::recalcSections()
570 {
571     tCaption = 0;
572     head = foot = firstBody = 0;
573     has_col_elems = false;
574
575     RenderObject *child = firstChild();
576     // We need to get valid pointers to caption, head, foot and firstbody again
577     while (child) {
578         switch (child->style()->display()) {
579         case TABLE_CAPTION:
580             if (!tCaption) {
581                 tCaption = static_cast<RenderBlock*>(child);
582                 tCaption->setNeedsLayout(true);
583             }
584             break;
585         case TABLE_COLUMN:
586         case TABLE_COLUMN_GROUP:
587             has_col_elems = true;
588             break;
589         case TABLE_HEADER_GROUP: {
590             RenderTableSection *section = static_cast<RenderTableSection *>(child);
591             if ( !head )
592                 head = section;
593             else if ( !firstBody )
594                 firstBody = section;
595             if ( section->needCellRecalc )
596                 section->recalcCells();
597             break;
598         }
599         case TABLE_FOOTER_GROUP: {
600             RenderTableSection *section = static_cast<RenderTableSection *>(child);
601             if ( !foot )
602                 foot = section;
603             else if ( !firstBody )
604                 firstBody = section;
605             if ( section->needCellRecalc )
606                 section->recalcCells();
607             break;
608         }
609         case TABLE_ROW_GROUP: {
610             RenderTableSection *section = static_cast<RenderTableSection *>(child);
611             if ( !firstBody )
612                 firstBody = section;
613             if ( section->needCellRecalc )
614                 section->recalcCells();
615         }
616         default:
617             break;
618         }
619         child = child->nextSibling();
620     }
621     needSectionRecalc = false;
622     setNeedsLayout(true);
623 }
624
625 RenderObject* RenderTable::removeChildNode(RenderObject* child)
626 {
627     setNeedSectionRecalc();
628     return RenderContainer::removeChildNode( child );
629 }
630
631 int RenderTable::borderLeft() const
632 {
633     if (collapseBorders()) {
634         // FIXME: For strict mode, returning 0 is correct, since the table border half spills into the margin,
635         // but I'm working to get this changed.  For now, follow the spec.
636         return 0;
637     }
638     return RenderBlock::borderLeft();
639 }
640     
641 int RenderTable::borderRight() const
642 {
643     if (collapseBorders()) {
644         // FIXME: For strict mode, returning 0 is correct, since the table border half spills into the margin,
645         // but I'm working to get this changed.  For now, follow the spec.
646         return 0;
647     }
648     return RenderBlock::borderRight();
649 }
650
651 int RenderTable::borderTop() const
652 {
653     if (collapseBorders()) {
654         // FIXME: For strict mode, returning 0 is correct, since the table border half spills into the margin,
655         // but I'm working to get this changed.  For now, follow the spec.
656         return 0;
657     }
658     return RenderBlock::borderTop();
659 }
660
661 int RenderTable::borderBottom() const
662 {
663     if (collapseBorders()) {
664         // FIXME: For strict mode, returning 0 is correct, since the table border half spills into the margin,
665         // but I'm working to get this changed.  For now, follow the spec.
666         return 0;
667     }
668     return RenderBlock::borderBottom();
669 }
670
671 RenderTableCell* RenderTable::cellAbove(const RenderTableCell* cell) const
672 {
673     // Find the section and row to look in
674     int r = cell->row();
675     RenderTableSection* section = 0;
676     int rAbove = -1;
677     if (r > 0) {
678         // cell is not in the first row, so use the above row in its own section
679         section = cell->section();
680         rAbove = r-1;
681     } else {
682         // cell is at top of a section, use last row in previous section
683         for (RenderObject *prevSection = cell->section()->previousSibling();
684              prevSection && rAbove < 0;
685              prevSection = prevSection->previousSibling()) {
686             if (prevSection->isTableSection()) {
687                 section = static_cast<RenderTableSection *>(prevSection);
688                 if (section->numRows() > 0)
689                     rAbove = section->numRows()-1;
690             }
691         }
692     }
693
694     // Look up the cell in the section's grid, which requires effective col index
695     if (section && rAbove >= 0) {
696         int effCol = colToEffCol(cell->col());
697         RenderTableCell* aboveCell;
698         // If we hit a span back up to a real cell.
699         do {
700             aboveCell = section->cellAt(rAbove, effCol);
701             effCol--;
702         } while (aboveCell == (RenderTableCell *)-1 && effCol >=0);
703         return (aboveCell == (RenderTableCell *)-1) ? 0 : aboveCell;
704     } else {
705         return 0;
706     }
707 }
708
709 RenderTableCell* RenderTable::cellBelow(const RenderTableCell* cell) const
710 {
711     // Find the section and row to look in
712     int r = cell->row() + cell->rowSpan() - 1;
713     RenderTableSection* section = 0;
714     int rBelow = -1;
715     if (r < cell->section()->numRows()-1) {
716         // The cell is not in the last row, so use the next row in the section.
717         section = cell->section();
718         rBelow= r+1;
719     } else {
720         // The cell is at the bottom of a section. Use the first row in the next section.
721         for (RenderObject* nextSection = cell->section()->nextSibling();
722              nextSection && rBelow < 0;
723              nextSection = nextSection->nextSibling()) 
724         {
725             if (nextSection->isTableSection()) {
726                 section = static_cast<RenderTableSection *>(nextSection);
727                 if (section->numRows() > 0)
728                     rBelow = 0;
729             }
730         }
731     }
732     
733     // Look up the cell in the section's grid, which requires effective col index
734     if (section && rBelow >= 0) {
735         int effCol = colToEffCol(cell->col());
736         RenderTableCell* belowCell;
737         // If we hit a colspan back up to a real cell.
738         do {
739             belowCell = section->cellAt(rBelow, effCol);
740             effCol--;
741         } while (belowCell == (RenderTableCell *)-1 && effCol >=0);
742         return (belowCell == (RenderTableCell *)-1) ? 0 : belowCell;
743     } else {
744         return 0;
745     }    
746 }
747
748 RenderTableCell* RenderTable::cellLeft(const RenderTableCell* cell) const
749 {
750     RenderTableSection* section = cell->section();
751     int effCol = colToEffCol(cell->col());
752     if (effCol == 0)
753         return 0;
754     
755     // If we hit a colspan back up to a real cell.
756     RenderTableCell* prevCell;
757     do {
758         prevCell = section->cellAt(cell->row(), effCol-1);
759         effCol--;
760     } while (prevCell == (RenderTableCell *)-1 && effCol >=0);
761     return (prevCell == (RenderTableCell *)-1) ? 0 : prevCell;
762 }
763
764 RenderTableCell* RenderTable::cellRight(const RenderTableCell* cell) const
765 {
766     int effCol = colToEffCol(cell->col()+cell->colSpan());
767     if (effCol >= numEffCols())
768         return 0;
769     RenderTableCell* result = cell->section()->cellAt(cell->row(), effCol);
770     return (result == (RenderTableCell*)-1) ? 0 : result;
771 }
772
773 RenderBlock* RenderTable::firstLineBlock() const
774 {
775     return 0;
776 }
777
778 void RenderTable::updateFirstLetter()
779 {}
780
781 #ifndef NDEBUG
782 void RenderTable::dump(QTextStream *stream, QString ind) const
783 {
784     if (tCaption)
785         *stream << " tCaption";
786     if (head)
787         *stream << " head";
788     if (foot)
789         *stream << " foot";
790
791     *stream << endl << ind << "cspans:";
792     for ( unsigned int i = 0; i < columns.size(); i++ )
793         *stream << " " << columns[i].span;
794     *stream << endl << ind;
795
796     RenderBlock::dump(stream,ind);
797 }
798 #endif
799
800 // --------------------------------------------------------------------------
801
802 RenderTableSection::RenderTableSection(DOM::NodeImpl* node)
803     : RenderContainer(node)
804 {
805     // init RenderObject attributes
806     setInline(false);   // our object is not Inline
807     gridRows = 0;
808     cCol = 0;
809     cRow = -1;
810     needCellRecalc = false;
811 }
812
813 RenderTableSection::~RenderTableSection()
814 {
815     clearGrid();
816 }
817
818 void RenderTableSection::detach()
819 {
820     // recalc cell info because RenderTable has unguarded pointers
821     // stored that point to this RenderTableSection.
822     if (table())
823         table()->setNeedSectionRecalc();
824
825     RenderContainer::detach();
826 }
827
828 void RenderTableSection::setStyle(RenderStyle* _style)
829 {
830     // we don't allow changing this one
831     if (style())
832         _style->setDisplay(style()->display());
833     else if (_style->display() != TABLE_FOOTER_GROUP && _style->display() != TABLE_HEADER_GROUP)
834         _style->setDisplay(TABLE_ROW_GROUP);
835
836     RenderContainer::setStyle(_style);
837 }
838
839 void RenderTableSection::addChild(RenderObject *child, RenderObject *beforeChild)
840 {
841 #ifdef DEBUG_LAYOUT
842     kdDebug( 6040 ) << renderName() << "(TableSection)::addChild( " << child->renderName()  << ", beforeChild=" <<
843                        (beforeChild ? beforeChild->renderName() : "0") << " )" << endl;
844 #endif
845     RenderObject *row = child;
846
847     if (child->element() && child->element()->id() == ID_FORM) {
848         RenderContainer::addChild(child,beforeChild);
849         return;
850     }
851     
852     if ( !child->isTableRow() ) {
853
854         if( !beforeChild )
855             beforeChild = lastChild();
856
857         if( beforeChild && beforeChild->isAnonymous() )
858             row = beforeChild;
859         else {
860             RenderObject *lastBox = beforeChild;
861             while ( lastBox && lastBox->parent()->isAnonymous() && !lastBox->isTableRow() )
862                 lastBox = lastBox->parent();
863             if ( lastBox && lastBox->isAnonymous() ) {
864                 lastBox->addChild( child, beforeChild );
865                 return;
866             } else {
867                 //kdDebug( 6040 ) << "creating anonymous table row" << endl;
868                 row = new (renderArena()) RenderTableRow(document() /* anonymous table */);
869                 RenderStyle *newStyle = new (renderArena()) RenderStyle();
870                 newStyle->inheritFrom(style());
871                 newStyle->setDisplay( TABLE_ROW );
872                 row->setStyle(newStyle);
873                 addChild(row, beforeChild);
874             }
875         }
876         row->addChild(child);
877         child->setNeedsLayoutAndMinMaxRecalc();
878         return;
879     }
880
881     if (beforeChild)
882         setNeedCellRecalc();
883
884     cRow++;
885     cCol = 0;
886
887     ensureRows( cRow+1 );
888
889     if (!beforeChild) {
890         grid[cRow].height = child->style()->height();
891         if ( grid[cRow].height.type == Relative )
892             grid[cRow].height = Length();
893     }
894
895
896     RenderContainer::addChild(child,beforeChild);
897 }
898
899 void RenderTableSection::ensureRows(int numRows)
900 {
901     int nRows = gridRows;
902     if (numRows > nRows) {
903         if (numRows > static_cast<int>(grid.size()))
904             grid.resize(numRows*2+1);
905
906         gridRows = numRows;
907         int nCols = table()->numEffCols();
908         for (int r = nRows; r < numRows; r++ ) {
909             grid[r].row = new Row(nCols);
910             grid[r].row->fill(0);
911             grid[r].baseLine = 0;
912             grid[r].height = Length();
913         }
914     }
915
916 }
917
918 void RenderTableSection::addCell( RenderTableCell *cell )
919 {
920     int rSpan = cell->rowSpan();
921     int cSpan = cell->colSpan();
922     QMemArray<RenderTable::ColumnStruct> &columns = table()->columns;
923     int nCols = columns.size();
924
925     // ### mozilla still seems to do the old HTML way, even for strict DTD
926     // (see the annotation on table cell layouting in the CSS specs and the testcase below:
927     // <TABLE border>
928     // <TR><TD>1 <TD rowspan="2">2 <TD>3 <TD>4
929     // <TR><TD colspan="2">5
930     // </TABLE>
931 #if 0
932     // find empty space for the cell
933     bool found = false;
934     while ( !found ) {
935         found = true;
936         while ( cCol < nCols && cellAt( cRow, cCol ) )
937             cCol++;
938         int pos = cCol;
939         int span = 0;
940         while ( pos < nCols && span < cSpan ) {
941             if ( cellAt( cRow, pos ) ) {
942                 found = false;
943                 cCol = pos;
944                 break;
945             }
946             span += columns[pos].span;
947             pos++;
948         }
949     }
950 #else
951     while ( cCol < nCols && cellAt( cRow, cCol ) )
952         cCol++;
953 #endif
954
955 //       qDebug("adding cell at %d/%d span=(%d/%d)",  cRow, cCol, rSpan, cSpan );
956
957     if ( rSpan == 1 ) {
958         // we ignore height settings on rowspan cells
959         Length height = cell->style()->height();
960         if ( height.value > 0 || (height.type == Relative && height.value >= 0) ) {
961             Length cRowHeight = grid[cRow].height;
962             switch( height.type ) {
963             case Percent:
964                 if ( !(cRowHeight.type == Percent) ||
965                      ( cRowHeight.type == Percent && cRowHeight.value < height.value ) )
966                     grid[cRow].height = height;
967                      break;
968             case Fixed:
969                 if ( cRowHeight.type < Percent ||
970                      ( cRowHeight.type == Fixed && cRowHeight.value < height.value ) )
971                     grid[cRow].height = height;
972                 break;
973             case Relative:
974 #if 0
975                 // we treat this as variable. This is correct according to HTML4, as it only specifies length for the height.
976                 if ( cRowHeight.type == Variable ||
977                      ( cRowHeight.type == Relative && cRowHeight.value < height.value ) )
978                      grid[cRow].height = height;
979                      break;
980 #endif
981             default:
982                 break;
983             }
984         }
985     }
986
987     // make sure we have enough rows
988     ensureRows( cRow + rSpan );
989
990     int col = cCol;
991     // tell the cell where it is
992     RenderTableCell *set = cell;
993     while ( cSpan ) {
994         int currentSpan;
995         if ( cCol >= nCols ) {
996             table()->appendColumn( cSpan );
997             currentSpan = cSpan;
998         } else {
999             if ( cSpan < columns[cCol].span )
1000                 table()->splitColumn( cCol, cSpan );
1001             currentSpan = columns[cCol].span;
1002         }
1003         int r = 0;
1004         while ( r < rSpan ) {
1005             if ( !cellAt( cRow + r, cCol ) ) {
1006 //              qDebug("    adding cell at %d, %d",  cRow + r, cCol );
1007                 cellAt( cRow + r, cCol ) = set;
1008             }
1009             r++;
1010         }
1011         cCol++;
1012         cSpan -= currentSpan;
1013         set = (RenderTableCell *)-1;
1014     }
1015     if ( cell ) {
1016         cell->setRow( cRow );
1017         cell->setCol( table()->effColToCol( col ) );
1018     }
1019 }
1020
1021
1022
1023 void RenderTableSection::setCellWidths()
1024 {
1025 #ifdef DEBUG_LAYOUT
1026     kdDebug( 6040 ) << renderName() << "(Table, this=0x" << this << ")::setCellWidths()" << endl;
1027 #endif
1028     QMemArray<int> &columnPos = table()->columnPos;
1029
1030     int rows = gridRows;
1031     for ( int i = 0; i < rows; i++ ) {
1032         Row &row = *grid[i].row;
1033         int cols = row.size();
1034         for ( int j = 0; j < cols; j++ ) {
1035             RenderTableCell *cell = row[j];
1036 //          qDebug("cell[%d,%d] = %p", i, j, cell );
1037             if ( !cell || cell == (RenderTableCell *)-1 )
1038                 continue;
1039             int endCol = j;
1040             int cspan = cell->colSpan();
1041             while ( cspan && endCol < cols ) {
1042                 cspan -= table()->columns[endCol].span;
1043                 endCol++;
1044             }
1045             int w = columnPos[endCol] - columnPos[j] - table()->hBorderSpacing();
1046 #ifdef DEBUG_LAYOUT
1047             kdDebug( 6040 ) << "setting width of cell " << cell << " " << cell->row() << "/" << cell->col() << " to " << w << " colspan=" << cell->colSpan() << " start=" << j << " end=" << endCol << endl;
1048 #endif
1049             int oldWidth = cell->width();
1050             if ( w != oldWidth ) {
1051                 cell->setNeedsLayout(true);
1052                 cell->setWidth( w );
1053             }
1054         }
1055     }
1056 }
1057
1058
1059 void RenderTableSection::calcRowHeight()
1060 {
1061     int indx;
1062     RenderTableCell *cell;
1063
1064     int totalRows = gridRows;
1065     int spacing = table()->vBorderSpacing();
1066
1067     rowPos.resize( totalRows + 1 );
1068     rowPos[0] = spacing;
1069
1070     for ( int r = 0; r < totalRows; r++ ) {
1071         rowPos[r+1] = 0;
1072
1073         int baseline=0;
1074         int bdesc = 0;
1075 //      qDebug("height of row %d is %d/%d", r, grid[r].height.value, grid[r].height.type );
1076         int ch = grid[r].height.minWidth( 0 );
1077         int pos = rowPos[ r+1 ] + ch + spacing;
1078
1079         if ( pos > rowPos[r+1] )
1080             rowPos[r+1] = pos;
1081
1082         Row *row = grid[r].row;
1083         int totalCols = row->size();
1084         int totalRows = gridRows;
1085
1086         for ( int c = 0; c < totalCols; c++ ) {
1087             cell = cellAt(r, c);
1088             if ( !cell || cell == (RenderTableCell *)-1 )
1089                 continue;
1090             if ( r < totalRows - 1 && cellAt(r+1, c) == cell )
1091                 continue;
1092
1093             if ( ( indx = r - cell->rowSpan() + 1 ) < 0 )
1094                 indx = 0;
1095
1096             if (cell->overrideSize() != -1) {
1097                 cell->setOverrideSize(-1);
1098                 cell->setChildNeedsLayout(true, false);
1099                 cell->layoutIfNeeded();
1100             }
1101             
1102             // Explicit heights use the border box in quirks mode.  In strict mode do the right
1103             // thing and actually add in the border and padding.
1104             ch = cell->style()->height().width(0) + 
1105                 (cell->style()->htmlHacks() ? 0 : (cell->paddingTop() + cell->paddingBottom() +
1106                                                    cell->borderTop() + cell->borderBottom()));
1107             if (cell->height() > ch)
1108                 ch = cell->height();
1109
1110             pos = rowPos[ indx ] + ch + spacing;
1111
1112             if ( pos > rowPos[r+1] )
1113                 rowPos[r+1] = pos;
1114
1115             // find out the baseline
1116             EVerticalAlign va = cell->style()->verticalAlign();
1117             if (va == BASELINE || va == TEXT_BOTTOM || va == TEXT_TOP
1118                 || va == SUPER || va == SUB)
1119             {
1120                 int b=cell->baselinePosition();
1121
1122                 if (b>baseline)
1123                     baseline=b;
1124
1125                 int td = rowPos[ indx ] + ch - b;
1126                 if (td>bdesc)
1127                     bdesc = td;
1128             }
1129         }
1130
1131         //do we have baseline aligned elements?
1132         if (baseline) {
1133             // increase rowheight if baseline requires
1134             int bRowPos = baseline + bdesc  + spacing ; // + 2*padding
1135             if (rowPos[r+1]<bRowPos)
1136                 rowPos[r+1]=bRowPos;
1137
1138             grid[r].baseLine = baseline;
1139         }
1140
1141         if ( rowPos[r+1] < rowPos[r] )
1142             rowPos[r+1] = rowPos[r];
1143 //      qDebug("rowpos(%d)=%d",  r, rowPos[r] );
1144     }
1145 }
1146
1147 int RenderTableSection::layoutRows( int toAdd )
1148 {
1149     int rHeight;
1150     int rindx;
1151     int totalRows = gridRows;
1152     int hspacing = table()->hBorderSpacing();
1153     int vspacing = table()->vBorderSpacing();
1154     
1155     if (toAdd && totalRows && (rowPos[totalRows] || !nextSibling())) {
1156
1157         int totalHeight = rowPos[totalRows] + toAdd;
1158 //      qDebug("layoutRows: totalHeight = %d",  totalHeight );
1159
1160         int dh = toAdd;
1161         int totalPercent = 0;
1162         int numVariable = 0;
1163         for ( int r = 0; r < totalRows; r++ ) {
1164             if ( grid[r].height.type == Variable )
1165                 numVariable++;
1166             else if ( grid[r].height.type == Percent )
1167                 totalPercent += grid[r].height.value;
1168         }
1169         if ( totalPercent ) {
1170 //          qDebug("distributing %d over percent rows totalPercent=%d", dh,  totalPercent );
1171             // try to satisfy percent
1172             int add = 0;
1173             if ( totalPercent > 100 )
1174                 totalPercent = 100;
1175             int rh = rowPos[1]-rowPos[0];
1176             for ( int r = 0; r < totalRows; r++ ) {
1177                 if ( totalPercent > 0 && grid[r].height.type == Percent ) {
1178                     int toAdd = kMin(dh, (totalHeight * grid[r].height.value / 100)-rh);
1179                     // If toAdd is negative, then we don't want to shrink the row (this bug
1180                     // affected Outlook Web Access).
1181                     toAdd = QMAX(0, toAdd);
1182                     add += toAdd;
1183                     dh -= toAdd;
1184                     totalPercent -= grid[r].height.value;
1185 //                  qDebug( "adding %d to row %d", toAdd, r );
1186                 }
1187                 if ( r < totalRows-1 )
1188                     rh = rowPos[r+2] - rowPos[r+1];
1189                 rowPos[r+1] += add;
1190             }
1191         }
1192         if ( numVariable ) {
1193             // distribute over variable cols
1194 //          qDebug("distributing %d over variable rows numVariable=%d", dh,  numVariable );
1195             int add = 0;
1196             for ( int r = 0; r < totalRows; r++ ) {
1197                 if ( numVariable > 0 && grid[r].height.type == Variable ) {
1198                     int toAdd = dh/numVariable;
1199                     add += toAdd;
1200                     dh -= toAdd;
1201                     numVariable--;
1202                 }
1203                 rowPos[r+1] += add;
1204             }
1205         }
1206         if (dh>0 && rowPos[totalRows]) {
1207             // if some left overs, distribute equally.
1208             int tot=rowPos[totalRows];
1209             int add=0;
1210             int prev=rowPos[0];
1211             for ( int r = 0; r < totalRows; r++ ) {
1212                 //weight with the original height
1213                 add+=dh*(rowPos[r+1]-prev)/tot;
1214                 prev=rowPos[r+1];
1215                 rowPos[r+1]+=add;
1216             }
1217         }
1218     }
1219
1220     int leftOffset = hspacing;
1221
1222     int nEffCols = table()->numEffCols();
1223     for ( int r = 0; r < totalRows; r++ )
1224     {
1225         Row *row = grid[r].row;
1226         int totalCols = row->size();
1227         for ( int c = 0; c < nEffCols; c++ )
1228         {
1229             RenderTableCell *cell = cellAt(r, c);
1230             if (!cell || cell == (RenderTableCell *)-1 )
1231                 continue;
1232             if ( r < totalRows - 1 && cell == cellAt(r+1, c) )
1233                 continue;
1234
1235             if ( ( rindx = r-cell->rowSpan()+1 ) < 0 )
1236                 rindx = 0;
1237
1238             rHeight = rowPos[r+1] - rowPos[rindx] - vspacing;
1239             
1240             // Force percent height children to lay themselves out again.
1241             // This will cause these children to grow to fill the cell.
1242             // FIXME: There is still more work to do here to fully match WinIE (should
1243             // it become necessary to do so).  In quirks mode, WinIE behaves like we
1244             // do, but it will clip the cells that spill out of the table section.  In
1245             // strict mode, Mozilla and WinIE both regrow the table to accommodate the
1246             // new height of the cell (thus letting the percentages cause growth one
1247             // time only).  We may also not be handling row-spanning cells correctly.
1248             //
1249             // Note also the oddity where replaced elements always flex, and yet blocks/tables do
1250             // not necessarily flex.  WinIE is crazy and inconsistent, and we can't hope to
1251             // match the behavior perfectly, but we'll continue to refine it as we discover new
1252             // bugs. :)
1253             bool cellChildrenFlex = false;
1254             bool flexAllChildren = cell->style()->height().isFixed() || 
1255                 (!table()->style()->height().isVariable() && rHeight != cell->height());
1256             RenderObject* o = cell->firstChild();
1257             while (o) {
1258                 if (!o->isText() && o->style()->height().isPercent() && (o->isReplaced() || o->scrollsOverflow() || flexAllChildren)) {
1259                     // Tables with no sections do not flex.
1260                     if (!o->isTable() || static_cast<RenderTable*>(o)->hasSections()) {
1261                         o->setNeedsLayout(true, false);
1262                         cell->setChildNeedsLayout(true, false);
1263                         cellChildrenFlex = true;
1264                     }
1265                 }
1266                 o = o->nextSibling();
1267             }
1268             if (cellChildrenFlex) {
1269                 cell->setOverrideSize(kMax(0, 
1270                                            rHeight - cell->borderTop() - cell->paddingTop() - 
1271                                                      cell->borderBottom() - cell->paddingBottom()));
1272                 cell->layoutIfNeeded();
1273
1274                 // Alignment within a cell is based off the calculated
1275                 // height, which becomes irrelevant once the cell has
1276                 // been resized based off its percentage. -dwh
1277                 cell->setCellTopExtra(0);
1278                 cell->setCellBottomExtra(0);
1279             }
1280             else {
1281 #ifdef DEBUG_LAYOUT
1282             kdDebug( 6040 ) << "setting position " << r << "/" << c << ": "
1283                             << table()->columnPos[c] /*+ padding */ << "/" << rowPos[rindx] << " height=" << rHeight<< endl;
1284 #endif
1285
1286             EVerticalAlign va = cell->style()->verticalAlign();
1287             int te=0;
1288             switch (va)
1289             {
1290             case SUB:
1291             case SUPER:
1292             case TEXT_TOP:
1293             case TEXT_BOTTOM:
1294             case BASELINE:
1295                 te = getBaseline(r) - cell->baselinePosition() ;
1296                 break;
1297             case TOP:
1298                 te = 0;
1299                 break;
1300             case MIDDLE:
1301                 te = (rHeight - cell->height())/2;
1302                 break;
1303             case BOTTOM:
1304                 te = rHeight - cell->height();
1305                 break;
1306             default:
1307                 break;
1308             }
1309 #ifdef DEBUG_LAYOUT
1310             //            kdDebug( 6040 ) << "CELL " << cell << " te=" << te << ", be=" << rHeight - cell->height() - te << ", rHeight=" << rHeight << ", valign=" << va << endl;
1311 #endif
1312             cell->setCellTopExtra( te );
1313             cell->setCellBottomExtra( rHeight - cell->height() - te);
1314             }
1315             
1316             int oldCellX = cell->xPos();
1317             int oldCellY = cell->yPos();
1318         
1319             if (style()->direction()==RTL) {
1320                 cell->setPos(
1321                     table()->columnPos[(int)totalCols] -
1322                     table()->columnPos[table()->colToEffCol(cell->col()+cell->colSpan())] +
1323                     leftOffset,
1324                     rowPos[rindx] );
1325             } else {
1326                 cell->setPos( table()->columnPos[c] + leftOffset, rowPos[rindx] );
1327             }
1328
1329             // If the cell moved, we have to repaint it as well as any floating/positioned
1330             // descendants.  An exception is if we need a layout.  In this case, we know we're going to
1331             // repaint ourselves (and the cell) anyway.
1332             if (!table()->selfNeedsLayout() && cell->checkForRepaintDuringLayout())
1333                 cell->repaintDuringLayoutIfMoved(oldCellX, oldCellY);
1334         }
1335     }
1336
1337     m_height = rowPos[totalRows];
1338     return m_height;
1339 }
1340
1341
1342 void RenderTableSection::paint(PaintInfo& i, int tx, int ty)
1343 {
1344     unsigned int totalRows = gridRows;
1345     unsigned int totalCols = table()->columns.size();
1346
1347     tx += m_x;
1348     ty += m_y;
1349
1350     // check which rows and cols are visible and only paint these
1351     // ### fixme: could use a binary search here
1352     PaintAction paintAction = i.phase;
1353     int x = i.r.x(); int y = i.r.y(); int w = i.r.width(); int h = i.r.height();
1354
1355     int os = 2*maximalOutlineSize(paintAction);
1356     unsigned int startrow = 0;
1357     unsigned int endrow = totalRows;
1358     for ( ; startrow < totalRows; startrow++ ) {
1359         if ( ty + rowPos[startrow+1] >= y - os)
1360             break;
1361     }
1362     for ( ; endrow > 0; endrow-- ) {
1363         if ( ty + rowPos[endrow-1] <= y + h + os)
1364             break;
1365     }
1366     unsigned int startcol = 0;
1367     unsigned int endcol = totalCols;
1368     if ( style()->direction() == LTR ) {
1369         for ( ; startcol < totalCols; startcol++ ) {
1370             if ( tx + table()->columnPos[startcol+1] >= x - os)
1371                 break;
1372         }
1373         for ( ; endcol > 0; endcol-- ) {
1374             if ( tx + table()->columnPos[endcol-1] <= x + w + os)
1375                 break;
1376         }
1377     }
1378     
1379     if ( startcol < endcol ) {
1380         // draw the cells
1381         for ( unsigned int r = startrow; r < endrow; r++ ) {
1382             unsigned int c = startcol;
1383             // since a cell can be -1 (indicating a colspan) we might have to search backwards to include it
1384             while ( c && cellAt( r, c ) == (RenderTableCell *)-1 )
1385                 c--;
1386             for ( ; c < endcol; c++ ) {
1387                 RenderTableCell *cell = cellAt(r, c);
1388                 if (!cell || cell == (RenderTableCell *)-1 )
1389                     continue;
1390                 
1391                 // Cells must always paint in the order in which they appear taking into account
1392                 // their upper left originating row/column.  For cells with rowspans, avoid repainting
1393                 // if we've already seen the cell.
1394                 if (r > startrow && (cellAt(r-1, c) == cell))
1395                     continue;
1396
1397 #ifdef TABLE_PRINT
1398                 kdDebug( 6040 ) << "painting cell " << r << "/" << c << endl;
1399 #endif
1400                 cell->paint(i, tx, ty);
1401             }
1402         }
1403     }
1404 }
1405
1406 void RenderTableSection::recalcCells()
1407 {
1408     cCol = 0;
1409     cRow = -1;
1410     clearGrid();
1411     gridRows = 0;
1412
1413     RenderObject *row = firstChild();
1414     while ( row ) {
1415         cRow++;
1416         cCol = 0;
1417         ensureRows( cRow+1 );
1418         RenderObject *cell = row->firstChild();
1419         while ( cell ) {
1420             if ( cell->isTableCell() )
1421                 addCell( static_cast<RenderTableCell *>(cell) );
1422             cell = cell->nextSibling();
1423         }
1424         row = row->nextSibling();
1425     }
1426     needCellRecalc = false;
1427     setNeedsLayout(true);
1428 }
1429
1430 void RenderTableSection::clearGrid()
1431 {
1432     int rows = gridRows;
1433     while ( rows-- ) {
1434         delete grid[rows].row;
1435     }
1436 }
1437
1438 RenderObject* RenderTableSection::removeChildNode(RenderObject* child)
1439 {
1440     setNeedCellRecalc();
1441     return RenderContainer::removeChildNode( child );
1442 }
1443
1444 #ifndef NDEBUG
1445 void RenderTableSection::dump(QTextStream *stream, QString ind) const
1446 {
1447     *stream << endl << ind << "grid=(" << grid.size() << "," << table()->numEffCols() << ")" << endl << ind;
1448     for ( unsigned int r = 0; r < grid.size(); r++ ) {
1449         for ( int c = 0; c < table()->numEffCols(); c++ ) {
1450             if ( cellAt( r,  c ) && cellAt( r, c ) != (RenderTableCell *)-1 )
1451                 *stream << "(" << cellAt( r, c )->row() << "," << cellAt( r, c )->col() << ","
1452                         << cellAt(r, c)->rowSpan() << "," << cellAt(r, c)->colSpan() << ") ";
1453             else
1454                 *stream << cellAt( r, c ) << "null cell ";
1455         }
1456         *stream << endl << ind;
1457     }
1458     RenderContainer::dump(stream,ind);
1459 }
1460 #endif
1461
1462 // -------------------------------------------------------------------------
1463
1464 RenderTableRow::RenderTableRow(DOM::NodeImpl* node)
1465     : RenderContainer(node)
1466 {
1467     // init RenderObject attributes
1468     setInline(false);   // our object is not Inline
1469 }
1470
1471 void RenderTableRow::detach()
1472 {
1473     RenderTableSection *s = section();
1474     if (s) {
1475         s->setNeedCellRecalc();
1476     }
1477     RenderContainer::detach();
1478 }
1479
1480 void RenderTableRow::setStyle(RenderStyle* style)
1481 {
1482     style->setDisplay(TABLE_ROW);
1483     RenderContainer::setStyle(style);
1484 }
1485
1486 void RenderTableRow::addChild(RenderObject *child, RenderObject *beforeChild)
1487 {
1488 #ifdef DEBUG_LAYOUT
1489     kdDebug( 6040 ) << renderName() << "(TableRow)::addChild( " << child->renderName() << " )"  << ", " <<
1490                        (beforeChild ? beforeChild->renderName() : "0") << " )" << endl;
1491 #endif
1492     if (child->element() && child->element()->id() == ID_FORM) {
1493         RenderContainer::addChild(child,beforeChild);
1494         return;
1495     }
1496
1497     RenderTableCell *cell;
1498
1499     if ( !child->isTableCell() ) {
1500         RenderObject *last = beforeChild;
1501         if ( !last )
1502             last = lastChild();
1503         RenderTableCell *cell = 0;
1504         if( last && last->isAnonymous() && last->isTableCell() )
1505             cell = static_cast<RenderTableCell *>(last);
1506         else {
1507             cell = new (renderArena()) RenderTableCell(document() /* anonymous object */);
1508             RenderStyle *newStyle = new (renderArena()) RenderStyle();
1509             newStyle->inheritFrom(style());
1510             newStyle->setDisplay( TABLE_CELL );
1511             cell->setStyle(newStyle);
1512             addChild(cell, beforeChild);
1513         }
1514         cell->addChild(child);
1515         child->setNeedsLayoutAndMinMaxRecalc();
1516         return;
1517     } else
1518         cell = static_cast<RenderTableCell *>(child);
1519
1520     static_cast<RenderTableSection *>(parent())->addCell( cell );
1521
1522     RenderContainer::addChild(cell,beforeChild);
1523
1524     if ( ( beforeChild || nextSibling()) && section() )
1525         section()->setNeedCellRecalc();
1526 }
1527
1528 RenderObject* RenderTableRow::removeChildNode(RenderObject* child)
1529 {
1530 // RenderTableCell detach should do it
1531 //     if ( section() )
1532 //      section()->setNeedCellRecalc();
1533     return RenderContainer::removeChildNode( child );
1534 }
1535
1536 #ifndef NDEBUG
1537 void RenderTableRow::dump(QTextStream *stream, QString ind) const
1538 {
1539     RenderContainer::dump(stream,ind);
1540 }
1541 #endif
1542
1543 void RenderTableRow::layout()
1544 {
1545     KHTMLAssert( needsLayout() );
1546     KHTMLAssert( minMaxKnown() );
1547
1548     RenderObject *child = firstChild();
1549     while( child ) {
1550         if (child->isTableCell()) {
1551             RenderTableCell *cell = static_cast<RenderTableCell *>(child);
1552             if (child->needsLayout()) {
1553                 cell->calcVerticalMargins();
1554                 cell->layout();
1555                 cell->setCellTopExtra(0);
1556                 cell->setCellBottomExtra(0);
1557             }
1558         }
1559         child = child->nextSibling();
1560     }
1561     setNeedsLayout(false);
1562 }
1563
1564 QRect RenderTableRow::getAbsoluteRepaintRect()
1565 {
1566     // For now, just repaint the whole table.
1567     // FIXME: Find a better way to do this.
1568     RenderTable* parentTable = table();
1569     if (parentTable)
1570         return parentTable->getAbsoluteRepaintRect();
1571     else
1572         return QRect();
1573 }
1574
1575 // -------------------------------------------------------------------------
1576
1577 RenderTableCell::RenderTableCell(DOM::NodeImpl* _node)
1578   : RenderBlock(_node)
1579 {
1580   _col = -1;
1581   _row = -1;
1582   cSpan = rSpan = 1;
1583   updateFromElement();
1584   setShouldPaintBackgroundOrBorder(true);
1585   _topExtra = 0;
1586   _bottomExtra = 0;
1587   m_percentageHeight = 0;
1588 }
1589
1590 void RenderTableCell::detach()
1591 {
1592     if (parent() && section())
1593         section()->setNeedCellRecalc();
1594
1595     RenderBlock::detach();
1596 }
1597
1598 void RenderTableCell::updateFromElement()
1599 {
1600     int oldRSpan = rSpan;
1601     int oldCSpan = cSpan;
1602     DOM::NodeImpl* node = element();
1603     if (node && (node->id() == ID_TD || node->id() == ID_TH)) {
1604         DOM::HTMLTableCellElementImpl *tc = static_cast<DOM::HTMLTableCellElementImpl *>(node);
1605         cSpan = tc->colSpan();
1606         rSpan = tc->rowSpan();
1607     }
1608     if ((oldRSpan != rSpan || oldCSpan != cSpan) && style() && parent())
1609         setNeedsLayoutAndMinMaxRecalc();
1610 }
1611     
1612 void RenderTableCell::calcMinMaxWidth()
1613 {
1614     RenderBlock::calcMinMaxWidth();
1615     if (element() && style()->whiteSpace() == NORMAL) {
1616         // See if nowrap was set.
1617         DOMString nowrap = static_cast<ElementImpl*>(element())->getAttribute(ATTR_NOWRAP);
1618         if (!nowrap.isNull() && style()->width().isFixed())
1619             // Nowrap is set, but we didn't actually use it because of the
1620             // fixed width set on the cell.  Even so, it is a WinIE/Moz trait
1621             // to make the minwidth of the cell into the fixed width.  They do this
1622             // even in strict mode, so do not make this a quirk.  Affected the top
1623             // of hiptop.com.
1624             if (m_minWidth < style()->width().value)
1625                 m_minWidth = style()->width().value;
1626     }
1627 }
1628
1629 void RenderTableCell::calcWidth()
1630 {
1631 }
1632
1633 void RenderTableCell::setWidth( int width )
1634 {
1635     if ( width != m_width ) {
1636         m_width = width;
1637         m_widthChanged = true;
1638     }
1639 }
1640
1641 void RenderTableCell::layout()
1642 {
1643     layoutBlock(m_widthChanged);
1644     m_widthChanged = false;
1645 }
1646
1647 void RenderTableCell::computeAbsoluteRepaintRect(QRect& r, bool f)
1648 {
1649     r.setY(r.y() + _topExtra);
1650     RenderBlock::computeAbsoluteRepaintRect(r, f);
1651 }
1652
1653 bool RenderTableCell::absolutePosition(int &xPos, int &yPos, bool f)
1654 {
1655     bool ret = RenderBlock::absolutePosition(xPos, yPos, f);
1656     if (ret)
1657       yPos += _topExtra;
1658     return ret;
1659 }
1660
1661 short RenderTableCell::baselinePosition( bool ) const
1662 {
1663     RenderObject *o = firstChild();
1664     int offset = paddingTop() + borderTop();
1665     if ( !o ) return offset;
1666     while ( o->firstChild() ) {
1667         if ( !o->isInline() )
1668             offset += o->paddingTop() + o->borderTop();
1669         o = o->firstChild();
1670     }
1671     offset += o->baselinePosition( true );
1672     return offset;
1673 }
1674
1675
1676 void RenderTableCell::setStyle( RenderStyle *style )
1677 {
1678     style->setDisplay(TABLE_CELL);
1679
1680     if (style->whiteSpace() == KHTML_NOWRAP) {
1681         // Figure out if we are really nowrapping or if we should just
1682         // use normal instead.  If the width of the cell is fixed, then
1683         // we don't actually use NOWRAP. 
1684         if (style->width().isFixed())
1685             style->setWhiteSpace(NORMAL);
1686         else
1687             style->setWhiteSpace(NOWRAP);
1688     }
1689
1690     RenderBlock::setStyle( style );
1691     setShouldPaintBackgroundOrBorder(true);
1692 }
1693
1694 bool RenderTableCell::requiresLayer() {
1695     // FIXME: This is only here until we figure out how to position
1696     // table cells properly when they have layers.
1697     return false;
1698 }
1699
1700 // The following rules apply for resolving conflicts and figuring out which border
1701 // to use.
1702 // (1) Borders with the 'border-style' of 'hidden' take precedence over all other conflicting 
1703 // borders. Any border with this value suppresses all borders at this location.
1704 // (2) Borders with a style of 'none' have the lowest priority. Only if the border properties of all 
1705 // the elements meeting at this edge are 'none' will the border be omitted (but note that 'none' is 
1706 // the default value for the border style.)
1707 // (3) If none of the styles are 'hidden' and at least one of them is not 'none', then narrow borders 
1708 // are discarded in favor of wider ones. If several have the same 'border-width' then styles are preferred 
1709 // in this order: 'double', 'solid', 'dashed', 'dotted', 'ridge', 'outset', 'groove', and the lowest: 'inset'.
1710 // (4) If border styles differ only in color, then a style set on a cell wins over one on a row, 
1711 // which wins over a row group, column, column group and, lastly, table. It is undefined which color 
1712 // is used when two elements of the same type disagree.
1713 static CollapsedBorderValue compareBorders(const CollapsedBorderValue& border1, 
1714                                            const CollapsedBorderValue& border2)
1715 {
1716     // Sanity check the values passed in.  If either is null, return the other.
1717     if (!border2.exists()) return border1;
1718     if (!border1.exists()) return border2;
1719     
1720     // Rule #1 above.
1721     if (border1.style() == BHIDDEN || border2.style() == BHIDDEN)
1722         return CollapsedBorderValue(); // No border should exist at this location.
1723     
1724     // Rule #2 above.  A style of 'none' has lowest priority and always loses to any other border.
1725     if (border2.style() == BNONE) return border1;
1726     if (border1.style() == BNONE) return border2;
1727     
1728     // The first part of rule #3 above. Wider borders win.
1729     if (border1.width() != border2.width())
1730         return border1.width() > border2.width() ? border1 : border2;
1731     
1732     // The borders have equal width.  Sort by border style.
1733     if (border1.style() != border2.style())
1734         return border1.style() > border2.style() ? border1 : border2;
1735     
1736     // The border have the same width and style.  Rely on precedence (cell over row over row group, etc.)
1737     return border1.precedence >= border2.precedence ? border1 : border2;
1738 }
1739
1740 CollapsedBorderValue RenderTableCell::collapsedLeftBorder() const
1741 {
1742     // For border left, we need to check, in order of precedence:
1743     // (1) Our left border.
1744     CollapsedBorderValue result(&style()->borderLeft(), BCELL);
1745     
1746     // (2) The previous cell's right border.
1747     RenderTableCell* prevCell = table()->cellLeft(this);
1748     if (prevCell) {
1749         result = compareBorders(result, CollapsedBorderValue(&prevCell->style()->borderRight(), BCELL));
1750         if (!result.exists()) return result;
1751     }
1752     else if (col() == 0) {
1753         // (3) Our row's left border.
1754         result = compareBorders(result, CollapsedBorderValue(&parent()->style()->borderLeft(), BROW));
1755         if (!result.exists()) return result;
1756         
1757         // (4) Our row group's left border.
1758         result = compareBorders(result, CollapsedBorderValue(&section()->style()->borderLeft(), BROWGROUP));
1759         if (!result.exists()) return result;
1760     }
1761     
1762     // (5) Our column's left border.
1763     RenderTableCol* colElt = table()->colElement(col());
1764     if (colElt) {
1765         result = compareBorders(result, CollapsedBorderValue(&colElt->style()->borderLeft(), BCOL));
1766         if (!result.exists()) return result;
1767     }
1768     
1769     // (6) The previous column's right border.
1770     if (col() > 0) {
1771         colElt = table()->colElement(col()-1);
1772         if (colElt) {
1773             result = compareBorders(result, CollapsedBorderValue(&colElt->style()->borderRight(), BCOL));
1774             if (!result.exists()) return result;
1775         }
1776     }
1777     
1778     if (col() == 0) {
1779         // (7) The table's left border.
1780         result = compareBorders(result, CollapsedBorderValue(&table()->style()->borderLeft(), BTABLE));
1781         if (!result.exists()) return result;
1782     }
1783     
1784     return result;
1785 }
1786
1787 CollapsedBorderValue RenderTableCell::collapsedRightBorder() const
1788 {
1789     RenderTable* tableElt = table();
1790     bool inLastColumn = false;
1791     int effCol = tableElt->colToEffCol(col()+colSpan()-1);
1792     if (effCol == tableElt->numEffCols()-1)
1793         inLastColumn = true;
1794     
1795     // For border right, we need to check, in order of precedence:
1796     // (1) Our right border.
1797     CollapsedBorderValue result = CollapsedBorderValue(&style()->borderRight(), BCELL);
1798     
1799     // (2) The next cell's left border.
1800     if (!inLastColumn) {
1801         RenderTableCell* nextCell = tableElt->cellRight(this);
1802         if (nextCell && nextCell->style()) {
1803             result = compareBorders(result, CollapsedBorderValue(&nextCell->style()->borderLeft(), BCELL));
1804             if (!result.exists()) return result;
1805         }
1806     }
1807     else {
1808         // (3) Our row's right border.
1809         result = compareBorders(result, CollapsedBorderValue(&parent()->style()->borderRight(), BROW));
1810         if (!result.exists()) return result;
1811         
1812         // (4) Our row group's right border.
1813         result = compareBorders(result, CollapsedBorderValue(&section()->style()->borderRight(), BROWGROUP));
1814         if (!result.exists()) return result;
1815     }
1816     
1817     // (5) Our column's right border.
1818     RenderTableCol* colElt = table()->colElement(col()+colSpan()-1);
1819     if (colElt) {
1820         result = compareBorders(result, CollapsedBorderValue(&colElt->style()->borderRight(), BCOL));
1821         if (!result.exists()) return result;
1822     }
1823     
1824     // (6) The next column's left border.
1825     if (!inLastColumn) {
1826         colElt = tableElt->colElement(col()+colSpan());
1827         if (colElt) {
1828             result = compareBorders(result, CollapsedBorderValue(&colElt->style()->borderLeft(), BCOL));
1829             if (!result.exists()) return result;
1830         }
1831     }
1832     else {
1833         // (7) The table's right border.
1834         result = compareBorders(result, CollapsedBorderValue(&tableElt->style()->borderRight(), BTABLE));
1835         if (!result.exists()) return result;
1836     }
1837     
1838     return result;
1839 }
1840
1841 CollapsedBorderValue RenderTableCell::collapsedTopBorder() const
1842 {
1843     // For border top, we need to check, in order of precedence:
1844     // (1) Our top border.
1845     CollapsedBorderValue result = CollapsedBorderValue(&style()->borderTop(), BCELL);
1846     
1847     RenderTableCell* prevCell = table()->cellAbove(this);
1848     if (prevCell) {
1849         // (2) A previous cell's bottom border.
1850         result = compareBorders(result, CollapsedBorderValue(&prevCell->style()->borderBottom(), BCELL));
1851         if (!result.exists()) return result;
1852     }
1853     
1854     // (3) Our row's top border.
1855     result = compareBorders(result, CollapsedBorderValue(&parent()->style()->borderTop(), BROW));
1856     if (!result.exists()) return result;
1857     
1858     // (4) The previous row's bottom border.
1859     if (prevCell) {
1860         RenderObject* prevRow = 0;
1861         if (prevCell->section() == section())
1862             prevRow = parent()->previousSibling();
1863         else
1864             prevRow = prevCell->section()->lastChild();
1865     
1866         if (prevRow) {
1867             result = compareBorders(result, CollapsedBorderValue(&prevRow->style()->borderBottom(), BROW));
1868             if (!result.exists()) return result;
1869         }
1870     }
1871     
1872     // Now check row groups.
1873     RenderObject* currSection = parent()->parent();
1874     if (row() == 0) {
1875         // (5) Our row group's top border.
1876         result = compareBorders(result, CollapsedBorderValue(&currSection->style()->borderTop(), BROWGROUP));
1877         if (!result.exists()) return result;
1878         
1879         // (6) Previous row group's bottom border.
1880         for (currSection = currSection->previousSibling(); currSection;
1881              currSection = currSection->previousSibling()) {
1882             if (currSection->isTableSection()) {
1883                 RenderTableSection* section = static_cast<RenderTableSection*>(currSection);
1884                 result = compareBorders(result, CollapsedBorderValue(&section->style()->borderBottom(), BROWGROUP));
1885                 if (!result.exists()) return result;
1886             }
1887         }
1888     }
1889     
1890     if (!currSection) {
1891         // (8) Our column's top border.
1892         RenderTableCol* colElt = table()->colElement(col());
1893         if (colElt) {
1894             result = compareBorders(result, CollapsedBorderValue(&colElt->style()->borderTop(), BCOL));
1895             if (!result.exists()) return result;
1896         }
1897         
1898         // (9) The table's top border.
1899         result = compareBorders(result, CollapsedBorderValue(&table()->style()->borderTop(), BTABLE));
1900         if (!result.exists()) return result;
1901     }
1902     
1903     return result;
1904 }
1905
1906 CollapsedBorderValue RenderTableCell::collapsedBottomBorder() const
1907 {
1908     // For border top, we need to check, in order of precedence:
1909     // (1) Our bottom border.
1910     CollapsedBorderValue result = CollapsedBorderValue(&style()->borderBottom(), BCELL);
1911     
1912     RenderTableCell* nextCell = table()->cellBelow(this);
1913     if (nextCell) {
1914         // (2) A following cell's top border.
1915         result = compareBorders(result, CollapsedBorderValue(&nextCell->style()->borderTop(), BCELL));
1916         if (!result.exists()) return result;
1917     }
1918     
1919     // (3) Our row's bottom border. (FIXME: Deal with rowspan!)
1920     result = compareBorders(result, CollapsedBorderValue(&parent()->style()->borderBottom(), BROW));
1921     if (!result.exists()) return result;
1922     
1923     // (4) The next row's top border.
1924     if (nextCell) {
1925         result = compareBorders(result, CollapsedBorderValue(&nextCell->parent()->style()->borderTop(), BROW));
1926         if (!result.exists()) return result;
1927     }
1928     
1929     // Now check row groups.
1930     RenderObject* currSection = parent()->parent();
1931     if (row() + rowSpan() >= static_cast<RenderTableSection*>(currSection)->numRows()) {
1932         // (5) Our row group's bottom border.
1933         result = compareBorders(result, CollapsedBorderValue(&currSection->style()->borderBottom(), BROWGROUP));
1934         if (!result.exists()) return result;
1935         
1936         // (6) Following row group's top border.
1937         for (currSection = currSection->nextSibling(); currSection;
1938              currSection = currSection->nextSibling()) {
1939             if (currSection->isTableSection()) {
1940                 RenderTableSection* section = static_cast<RenderTableSection*>(currSection);
1941                 result = compareBorders(result, CollapsedBorderValue(&section->style()->borderTop(), BROWGROUP));
1942                 if (!result.exists()) return result;
1943             }
1944         }
1945     }
1946     
1947     if (!currSection) {
1948         // (8) Our column's bottom border.
1949         RenderTableCol* colElt = table()->colElement(col());
1950         if (colElt) {
1951             result = compareBorders(result, CollapsedBorderValue(&colElt->style()->borderBottom(), BCOL));
1952             if (!result.exists()) return result;
1953         }
1954         
1955         // (9) The table's bottom border.
1956         result = compareBorders(result, CollapsedBorderValue(&table()->style()->borderBottom(), BTABLE));
1957         if (!result.exists()) return result;
1958     }
1959     
1960     return result;    
1961 }
1962
1963 int RenderTableCell::borderLeft() const
1964 {
1965     if (table()->collapseBorders()) {
1966         CollapsedBorderValue border = collapsedLeftBorder();
1967         if (border.exists())
1968             return int(border.width()/2.0+0.5); // Give the extra pixel to top and left.
1969         return 0;
1970     }
1971     return RenderBlock::borderLeft();
1972 }
1973     
1974 int RenderTableCell::borderRight() const
1975 {
1976     if (table()->collapseBorders()) {
1977         CollapsedBorderValue border = collapsedRightBorder();
1978         if (border.exists())
1979             return border.width()/2;
1980         return 0;
1981     }
1982     return RenderBlock::borderRight();
1983 }
1984
1985 int RenderTableCell::borderTop() const
1986 {
1987     if (table()->collapseBorders()) {
1988         CollapsedBorderValue border = collapsedTopBorder();
1989         if (border.exists())
1990             return int(border.width()/2.0+0.5); // Give the extra pixel to top and left.
1991         return 0;
1992     }
1993     return RenderBlock::borderTop();
1994 }
1995
1996 int RenderTableCell::borderBottom() const
1997 {
1998     if (table()->collapseBorders()) {
1999         CollapsedBorderValue border = collapsedBottomBorder();
2000         if (border.exists())
2001             return border.width()/2;
2002         return 0;
2003     }
2004     return RenderBlock::borderBottom();
2005 }
2006
2007 #ifdef BOX_DEBUG
2008 #include <qpainter.h>
2009
2010 static void outlineBox(QPainter *p, int _tx, int _ty, int w, int h)
2011 {
2012     p->setPen(QPen(QColor("yellow"), 3, Qt::DotLine));
2013     p->setBrush( Qt::NoBrush );
2014     p->drawRect(_tx, _ty, w, h );
2015 }
2016 #endif
2017
2018 void RenderTableCell::paint(PaintInfo& i, int _tx, int _ty)
2019 {
2020
2021 #ifdef TABLE_PRINT
2022     kdDebug( 6040 ) << renderName() << "(RenderTableCell)::paint() w/h = (" << width() << "/" << height() << ")" << " _y/_h=" << _y << "/" << _h << endl;
2023 #endif
2024
2025     _tx += m_x;
2026     _ty += m_y;
2027
2028     // check if we need to do anything at all...
2029     int os = 2*maximalOutlineSize(i.phase);
2030     if ((_ty >= i.r.y() + i.r.height() + os) || (_ty + _topExtra + m_height + _bottomExtra <= i.r.y() - os))
2031         return;
2032     
2033     if (i.phase == PaintActionCollapsedTableBorders && style()->visibility() == VISIBLE) {
2034         int w = width();
2035         int h = height() + borderTopExtra() + borderBottomExtra();
2036         paintCollapsedBorder(i.p, _tx, _ty, w, h);
2037     }
2038     else
2039         RenderBlock::paintObject(i, _tx, _ty + _topExtra);
2040
2041 #ifdef BOX_DEBUG
2042     ::outlineBox( i.p, _tx, _ty, width(), height() + borderTopExtra() + borderBottomExtra());
2043 #endif
2044 }
2045
2046 static EBorderStyle collapsedBorderStyle(EBorderStyle style)
2047 {
2048     if (style == OUTSET)
2049         style = GROOVE;
2050     else if (style == INSET)
2051         style = RIDGE;
2052     return style;
2053 }
2054
2055 struct CollapsedBorder {
2056     CollapsedBorder(){}
2057     
2058     CollapsedBorderValue border;
2059     RenderObject::BorderSide side;
2060     bool shouldPaint;
2061     int x1;
2062     int y1;
2063     int x2;
2064     int y2;
2065     EBorderStyle style;
2066 };
2067
2068 class CollapsedBorders
2069 {
2070 public:
2071     CollapsedBorders(int i) :count(0) {}
2072     
2073     void addBorder(const CollapsedBorderValue& b, RenderObject::BorderSide s, bool paint, 
2074                    int _x1, int _y1, int _x2, int _y2,
2075                    EBorderStyle _style)
2076     {
2077         if (b.exists() && paint) {
2078             borders[count].border = b;
2079             borders[count].side = s;
2080             borders[count].shouldPaint = paint;
2081             borders[count].x1 = _x1;
2082             borders[count].x2 = _x2;
2083             borders[count].y1 = _y1;
2084             borders[count].y2 = _y2;
2085             borders[count].style = _style;
2086             count++;
2087         }
2088     }
2089
2090     CollapsedBorder* nextBorder() {
2091         for (int i = 0; i < count; i++) {
2092             if (borders[i].border.exists() && borders[i].shouldPaint) {
2093                 borders[i].shouldPaint = false;
2094                 return &borders[i];
2095             }
2096         }
2097         
2098         return 0;
2099     }
2100     
2101     CollapsedBorder borders[4];
2102     int count;
2103 };
2104
2105 static void addBorderStyle(QValueList<CollapsedBorderValue>& borderStyles, CollapsedBorderValue borderValue)
2106 {
2107     if (!borderValue.exists() || borderStyles.contains(borderValue))
2108         return;
2109     
2110     QValueListIterator<CollapsedBorderValue> it = borderStyles.begin();
2111     QValueListIterator<CollapsedBorderValue> end = borderStyles.end();
2112     for (; it != end; ++it) {
2113         CollapsedBorderValue result = compareBorders(*it, borderValue);
2114         if (result == *it) {
2115             borderStyles.insert(it, borderValue);
2116             return;
2117         }
2118     }
2119
2120     borderStyles.append(borderValue);
2121 }
2122
2123 void RenderTableCell::collectBorders(QValueList<CollapsedBorderValue>& borderStyles)
2124 {
2125     addBorderStyle(borderStyles, collapsedLeftBorder());
2126     addBorderStyle(borderStyles, collapsedRightBorder());
2127     addBorderStyle(borderStyles, collapsedTopBorder());
2128     addBorderStyle(borderStyles, collapsedBottomBorder());
2129 }
2130
2131 void RenderTableCell::paintCollapsedBorder(QPainter* p, int _tx, int _ty, int w, int h)
2132 {
2133     if (!table()->currentBorderStyle())
2134         return;
2135     
2136     CollapsedBorderValue leftVal = collapsedLeftBorder();
2137     CollapsedBorderValue rightVal = collapsedRightBorder();
2138     CollapsedBorderValue topVal = collapsedTopBorder();
2139     CollapsedBorderValue bottomVal = collapsedBottomBorder();
2140      
2141     // Adjust our x/y/width/height so that we paint the collapsed borders at the correct location.
2142     int topWidth = topVal.width();
2143     int bottomWidth = bottomVal.width();
2144     int leftWidth = leftVal.width();
2145     int rightWidth = rightVal.width();
2146     
2147     _tx -= leftWidth/2;
2148     _ty -= topWidth/2;
2149     w += leftWidth/2 + int(rightWidth/2.0+0.5);
2150     h += topWidth/2 + int(bottomWidth/2.0+0.5);
2151     
2152     bool tt = topVal.isTransparent();
2153     bool bt = bottomVal.isTransparent();
2154     bool rt = rightVal.isTransparent();
2155     bool lt = leftVal.isTransparent();
2156     
2157     EBorderStyle ts = collapsedBorderStyle(topVal.style());
2158     EBorderStyle bs = collapsedBorderStyle(bottomVal.style());
2159     EBorderStyle ls = collapsedBorderStyle(leftVal.style());
2160     EBorderStyle rs = collapsedBorderStyle(rightVal.style());
2161     
2162     bool render_t = ts > BHIDDEN && !tt;
2163     bool render_l = ls > BHIDDEN && !lt;
2164     bool render_r = rs > BHIDDEN && !rt;
2165     bool render_b = bs > BHIDDEN && !bt;
2166
2167     // We never paint diagonals at the joins.  We simply let the border with the highest
2168     // precedence paint on top of borders with lower precedence.  
2169     CollapsedBorders borders(4);
2170     borders.addBorder(topVal, BSTop, render_t, _tx, _ty, _tx + w, _ty + topWidth, ts);
2171     borders.addBorder(bottomVal, BSBottom, render_b, _tx, _ty + h - bottomWidth, _tx + w, _ty + h, bs);
2172     borders.addBorder(leftVal, BSLeft, render_l, _tx, _ty, _tx + leftWidth, _ty + h, ls);
2173     borders.addBorder(rightVal, BSRight, render_r, _tx + w - rightWidth, _ty, _tx + w, _ty + h, rs);
2174     
2175     for (CollapsedBorder* border = borders.nextBorder(); border; border = borders.nextBorder()) {
2176         if (border->border == *table()->currentBorderStyle())
2177             drawBorder(p, border->x1, border->y1, border->x2, border->y2, border->side, 
2178                        border->border.color(), style()->color(), border->style, 0, 0);
2179     }
2180 }
2181
2182 QRect RenderTableCell::getAbsoluteRepaintRect()
2183 {
2184     int ow = style() ? style()->outlineSize() : 0;
2185     QRect r(-ow, -ow - borderTopExtra(), 
2186             overflowWidth(false)+ow*2, overflowHeight(false)+borderTopExtra()+borderBottomExtra()+ow*2);
2187     computeAbsoluteRepaintRect(r);
2188     return r;
2189 }
2190
2191 void RenderTableCell::paintBoxDecorations(PaintInfo& i, int _tx, int _ty)
2192 {
2193     RenderTable* tableElt = table();
2194     if (!tableElt->collapseBorders() && style()->emptyCells() == HIDE && !firstChild())
2195         return;
2196     
2197     int w = width();
2198     int h = height() + borderTopExtra() + borderBottomExtra();
2199     _ty -= borderTopExtra();
2200
2201     QColor c = style()->backgroundColor();
2202     if ( !c.isValid() && parent() ) // take from row
2203         c = parent()->style()->backgroundColor();
2204     if ( !c.isValid() && parent() && parent()->parent() ) // take from rowgroup
2205         c = parent()->parent()->style()->backgroundColor();
2206     if ( !c.isValid() ) {
2207         // see if we have a col or colgroup for this
2208         RenderTableCol *col = table()->colElement( _col );
2209         if ( col ) {
2210             c = col->style()->backgroundColor();
2211             if ( !c.isValid() ) {
2212                 // try column group
2213                 RenderStyle *style = col->parent()->style();
2214                 if ( style->display() == TABLE_COLUMN_GROUP )
2215                     c = style->backgroundColor();
2216             }
2217         }
2218     }
2219
2220     // FIXME: This code is just plain wrong.  Rows and columns should paint their backgrounds
2221     // independent from the cell.
2222     // ### get offsets right in case the bgimage is inherited.
2223     const BackgroundLayer* bgLayer = style()->backgroundLayers();
2224     if (!bgLayer->hasImage() && parent())
2225         bgLayer = parent()->style()->backgroundLayers();
2226     if (!bgLayer->hasImage() && parent() && parent()->parent())
2227         bgLayer = parent()->parent()->style()->backgroundLayers();
2228     if (!bgLayer->hasImage()) {
2229         // see if we have a col or colgroup for this
2230         RenderTableCol* col = table()->colElement(_col);
2231         if (col) {
2232             bgLayer = col->style()->backgroundLayers();
2233             if (!bgLayer->hasImage()) {
2234                 // try column group
2235                 RenderStyle *style = col->parent()->style();
2236                 if (style->display() == TABLE_COLUMN_GROUP)
2237                     bgLayer = style->backgroundLayers();
2238             }
2239         }
2240     }
2241
2242     int my = kMax(_ty, i.r.y());
2243     int end = kMin(i.r.y() + i.r.height(), _ty + h);
2244     int mh = end - my;
2245
2246     if (bgLayer->hasImage() || c.isValid())
2247         paintBackground(i.p, c, bgLayer, my, mh, _tx, _ty, w, h);
2248
2249     if (style()->hasBorder() && !tableElt->collapseBorders())
2250         paintBorder(i.p, _tx, _ty, w, h, style());
2251 }
2252
2253
2254 #ifndef NDEBUG
2255 void RenderTableCell::dump(QTextStream *stream, QString ind) const
2256 {
2257     *stream << " row=" << _row;
2258     *stream << " col=" << _col;
2259     *stream << " rSpan=" << rSpan;
2260     *stream << " cSpan=" << cSpan;
2261 //    *stream << " nWrap=" << nWrap;
2262
2263     RenderBlock::dump(stream,ind);
2264 }
2265 #endif
2266
2267 // -------------------------------------------------------------------------
2268
2269 RenderTableCol::RenderTableCol(DOM::NodeImpl* node)
2270     : RenderContainer(node)
2271 {
2272     // init RenderObject attributes
2273     setInline(true);   // our object is not Inline
2274
2275     _span = 1;
2276     updateFromElement();
2277 }
2278
2279 void RenderTableCol::updateFromElement()
2280 {
2281     int oldSpan = _span;
2282     DOM::NodeImpl *node = element();
2283     if (node && (node->id() == ID_COL || node->id() == ID_COLGROUP)) {
2284         DOM::HTMLTableColElementImpl *tc = static_cast<DOM::HTMLTableColElementImpl *>(node);
2285         _span = tc->span();
2286     } 
2287     else
2288       _span = !(style() && style()->display() == TABLE_COLUMN_GROUP);
2289     if (_span != oldSpan && style() && parent())
2290         setNeedsLayoutAndMinMaxRecalc();
2291 }
2292
2293 bool RenderTableCol::canHaveChildren() const
2294 {
2295     // cols cannot have children.  This is actually necessary to fix a bug
2296     // with libraries.uc.edu, which makes a <p> be a table-column.
2297     return style()->display() == TABLE_COLUMN_GROUP;
2298 }
2299
2300 void RenderTableCol::addChild(RenderObject *child, RenderObject *beforeChild)
2301 {
2302 #ifdef DEBUG_LAYOUT
2303     //kdDebug( 6040 ) << renderName() << "(Table)::addChild( " << child->renderName() << " )"  << ", " <<
2304     //                   (beforeChild ? beforeChild->renderName() : 0) << " )" << endl;
2305 #endif
2306
2307     KHTMLAssert(child->style()->display() == TABLE_COLUMN);
2308
2309     // these have to come before the table definition!
2310     RenderContainer::addChild(child,beforeChild);
2311 }
2312
2313 #ifndef NDEBUG
2314 void RenderTableCol::dump(QTextStream *stream, QString ind) const
2315 {
2316     *stream << " _span=" << _span;
2317     RenderContainer::dump(stream,ind);
2318 }
2319 #endif
2320
2321 #undef TABLE_DEBUG
2322 #undef DEBUG_LAYOUT
2323 #undef BOX_DEBUG