Reviewed by Dave Hyatt.
[WebKit-https.git] / WebCore / khtml / rendering / table_layout.cpp
1 /*
2  * This file is part of the HTML rendering engine for KDE.
3  *
4  * Copyright (C) 2002 Lars Knoll (knoll@kde.org)
5  *           (C) 2002 Dirk Mueller (mueller@kde.org)
6  * Copyright (C) 2003 Apple Computer, Inc.
7  *
8  * This library is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Library General Public
10  * License as published by the Free Software Foundation; either
11  * version 2 of the License.
12  *
13  * This library is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16  * Library General Public License for more details.
17  *
18  * You should have received a copy of the GNU Library General Public License
19  * along with this library; see the file COPYING.LIB.  If not, write to
20  * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
21  * Boston, MA 02111-1307, USA.
22  *
23  * $Id$
24  */
25 #include "table_layout.h"
26 #include "render_table.h"
27
28 #include <kglobal.h>
29
30 using namespace khtml;
31
32 // #define DEBUG_LAYOUT
33
34 /*
35   The text below is from the CSS 2.1 specs.
36
37   Fixed table layout
38   ------------------
39
40   With this (fast) algorithm, the horizontal layout of the table does
41   not depend on the contents of the cells; it only depends on the
42   table's width, the width of the columns, and borders or cell
43   spacing.
44
45   The table's width may be specified explicitly with the 'width'
46   property. A value of 'auto' (for both 'display: table' and 'display:
47   inline-table') means use the automatic table layout algorithm.
48
49   In the fixed table layout algorithm, the width of each column is
50   determined as follows:
51
52     1. A column element with a value other than 'auto' for the 'width'
53     property sets the width for that column.
54
55     2. Otherwise, a cell in the first row with a value other than
56     'auto' for the 'width' property sets the width for that column. If
57     the cell spans more than one column, the width is divided over the
58     columns.
59
60     3. Any remaining columns equally divide the remaining horizontal
61     table space (minus borders or cell spacing).
62
63   The width of the table is then the greater of the value of the
64   'width' property for the table element and the sum of the column
65   widths (plus cell spacing or borders). If the table is wider than
66   the columns, the extra space should be distributed over the columns.
67
68
69   In this manner, the user agent can begin to lay out the table once
70   the entire first row has been received. Cells in subsequent rows do
71   not affect column widths. Any cell that has content that overflows
72   uses the 'overflow' property to determine whether to clip the
73   overflow content.
74
75 _____________________________________________________
76
77   This is not quite true when comparing to IE. IE always honours
78   table-layout:fixed and treats a variable table width as 100%. Makes
79   a lot of sense, and is implemented here the same way.
80
81 */
82
83 FixedTableLayout::FixedTableLayout( RenderTable *table )
84     : TableLayout ( table )
85 {
86 }
87
88 FixedTableLayout::~FixedTableLayout()
89 {
90 }
91
92 int FixedTableLayout::calcWidthArray(int tableWidth)
93 {
94     int usedWidth = 0;
95
96     // iterate over all <col> elements
97     RenderObject *child = table->firstChild();
98     int cCol = 0;
99     int nEffCols = table->numEffCols();
100     width.resize( nEffCols );
101     width.fill( Length( Variable ) );
102
103 #ifdef DEBUG_LAYOUT
104     qDebug("FixedTableLayout::calcWidthArray( %d )", tableWidth );
105     qDebug("    col elements:");
106 #endif
107
108     Length grpWidth;
109     while ( child ) {
110         if ( child->isTableCol() ) {
111             RenderTableCol *col = static_cast<RenderTableCol *>(child);
112             int span = col->span();
113             if ( col->firstChild() ) {
114                 grpWidth = col->style()->width();
115             } else {
116                 Length w = col->style()->width();
117                 if ( w.isVariable() )
118                     w = grpWidth;
119                 int effWidth = 0;
120                 if ( w.type == Fixed && w.value > 0 )
121                     effWidth = w.value;
122                 
123 #ifdef DEBUG_LAYOUT
124                 qDebug("    col element: effCol=%d, span=%d: %d w=%d type=%d",
125                        cCol, span, effWidth,  w.value, w.type);
126 #endif
127                 int usedSpan = 0;
128                 int i = 0;
129                 while ( usedSpan < span ) {
130                     if( cCol + i >= nEffCols ) {
131                         table->appendColumn( span - usedSpan );
132                         nEffCols++;
133                         width.resize( nEffCols );
134                         width[nEffCols-1] = Length();
135                     }
136                     int eSpan = table->spanOfEffCol( cCol+i );
137                     if ( (w.type == Fixed || w.type == Percent) && w.value > 0 ) {
138                         width[cCol+i] = Length( w.value * eSpan, w.type );
139                         usedWidth += effWidth * eSpan;
140 #ifdef DEBUG_LAYOUT
141                         qDebug("    setting effCol %d (span=%d) to width %d(type=%d)",
142                                cCol+i, eSpan, width[cCol+i].value, width[cCol+i].type );
143 #endif
144                     }
145                     usedSpan += eSpan;
146                     i++;
147                 }
148                 cCol += i;
149             }
150         } else {
151             break;
152         }
153
154         RenderObject *next = child->firstChild();
155         if ( !next )
156             next = child->nextSibling();
157         if ( !next && child->parent()->isTableCol() ) {
158             next = child->parent()->nextSibling();
159             grpWidth = Length();
160         }
161         child = next;
162     }
163
164 #ifdef DEBUG_LAYOUT
165     qDebug("    first row:");
166 #endif
167     // iterate over the first row in case some are unspecified.
168     RenderTableSection *section = table->head;
169     if ( !section )
170         section = table->firstBody;
171     if ( !section )
172         section = table->foot;
173     if ( section ) {
174         cCol = 0;
175         // FIXME: Technically the first row could be in an arbitrary section (e.g., an nth section
176         // if the previous n-1 sections have no rows), so this check isn't good enough.
177         // get the first cell in the first row
178         RenderObject* firstRow = section->firstChild();
179         child = firstRow ? firstRow->firstChild() : 0;
180         while ( child ) {
181             if ( child->isTableCell() ) {
182                 RenderTableCell *cell = static_cast<RenderTableCell *>(child);
183                 Length w = cell->style()->width();
184                 int span = cell->colSpan();
185                 int effWidth = 0;
186                 if ( (w.type == Fixed || w.type == Percent) && w.value > 0 )
187                     effWidth = w.value;
188                 
189 #ifdef DEBUG_LAYOUT
190                 qDebug("    table cell: effCol=%d, span=%d: %d",  cCol, span, effWidth);
191 #endif
192                 int usedSpan = 0;
193                 int i = 0;
194                 while ( usedSpan < span ) {
195                     Q_ASSERT( cCol + i < nEffCols );
196                     int eSpan = table->spanOfEffCol( cCol+i );
197                     // only set if no col element has already set it.
198                     if ( width[cCol+i].type == Variable && w.type != Variable ) {
199                         width[cCol+i] = Length( w.value*eSpan, w.type );
200                         usedWidth += effWidth*eSpan;
201 #ifdef DEBUG_LAYOUT
202                         qDebug("    setting effCol %d (span=%d) to width %d(type=%d)",
203                                cCol+i, eSpan, width[cCol+i].value, width[cCol+i].type );
204 #endif
205                     }
206 #ifdef DEBUG_LAYOUT
207                     else {
208                         qDebug("    width of col %d already defined (span=%d)", cCol, table->spanOfEffCol( cCol ) );
209                     }
210 #endif
211                     usedSpan += eSpan;
212                     i++;
213                 }
214                 cCol += i;
215             } else {
216                 Q_ASSERT( false );
217             }
218             child = child->nextSibling();
219         }
220     }
221
222     return usedWidth;
223
224 }
225
226 void FixedTableLayout::calcMinMaxWidth()
227 {
228     // FIXME: This entire calculation is incorrect for both minwidth and maxwidth.
229     
230     // we might want to wait until we have all of the first row before
231     // layouting for the first time.
232
233     // only need to calculate the minimum width as the sum of the
234     // cols/cells with a fixed width.
235     //
236     // The maximum width is kMax( minWidth, tableWidth ).
237     int bs = table->bordersPaddingAndSpacing();
238     
239     int tableWidth = table->style()->width().type == Fixed ? table->style()->width().value - bs : 0;
240     int mw = calcWidthArray( tableWidth ) + bs;
241
242     table->m_minWidth = kMax( mw, tableWidth );
243     table->m_maxWidth = table->m_minWidth;
244 }
245
246 void FixedTableLayout::layout()
247 {
248     int tableWidth = table->width() - table->bordersPaddingAndSpacing();
249     int available = tableWidth;
250     int nEffCols = table->numEffCols();
251     int totalPercent = 0;
252     
253 #ifdef DEBUG_LAYOUT
254     qDebug("FixedTableLayout::layout: tableWidth=%d, numEffCols=%d",  tableWidth, nEffCols);
255 #endif
256
257
258     QMemArray<int> calcWidth;
259     calcWidth.resize( nEffCols );
260     calcWidth.fill( -1 );
261
262     // assign  percent width
263     if ( available > 0 ) {
264         for ( int i = 0; i < nEffCols; i++ )
265             if ( width[i].type == Percent )
266                 totalPercent += width[i].value;
267
268         // calculate how much to distribute to percent cells.
269         int base = tableWidth * totalPercent / 100;
270         if ( base > available )
271             base = available;
272         else
273             totalPercent = 100;
274
275 #ifdef DEBUG_LAYOUT
276         qDebug("FixedTableLayout::layout: assigning percent width, base=%d, totalPercent=%d", base, totalPercent);
277 #endif
278         for ( int i = 0; available > 0 && i < nEffCols; i++ ) {
279             if ( width[i].type == Percent ) {
280                 int w = base * width[i].value / totalPercent;
281                 available -= w;
282                 calcWidth[i] = w;
283             }
284         }
285     }
286     
287     // next assign fixed width
288     for ( int i = 0; i < nEffCols; i++ ) {
289         if ( width[i].type == Fixed ) {
290             calcWidth[i] = width[i].value;
291             available -= width[i].value;
292         }
293     }
294
295     // assign variable width
296     if ( available > 0 ) {
297         int totalVariable = 0;
298         for ( int i = 0; i < nEffCols; i++ )
299             if ( width[i].type == Variable )
300                 totalVariable++;
301
302         for ( int i = 0; available > 0 && i < nEffCols; i++ ) {
303             if ( width[i].type == Variable ) {
304                 int w = available / totalVariable;
305                 available -= w;
306                 calcWidth[i] = w;
307                 totalVariable--;
308             }
309         }
310     }
311
312     for ( int i = 0; i < nEffCols; i++ )
313         if ( calcWidth[i] <= 0 )
314             calcWidth[i] = 0; // IE gives min 1 px...
315
316     // spread extra space over columns
317     if ( available > 0 ) {
318         int total = nEffCols;
319         // still have some width to spread
320         int i = nEffCols;
321         while (  i-- ) {
322             int w = available / total;
323             available -= w;
324             total--;
325             calcWidth[i] += w;
326         }
327     }
328     
329     int pos = 0;
330     int hspacing = table->hBorderSpacing();
331     for ( int i = 0; i < nEffCols; i++ ) {
332 #ifdef DEBUG_LAYOUT
333         qDebug("col %d: %d (width %d)", i, pos, calcWidth[i] );
334 #endif
335         table->columnPos[i] = pos;
336         pos += calcWidth[i] + hspacing;
337     }
338     table->columnPos[table->columnPos.size()-1] = pos;
339 }
340
341 // -------------------------------------------------------------------------
342 // -------------------------------------------------------------------------
343
344
345 AutoTableLayout::AutoTableLayout( RenderTable* table )
346     : TableLayout( table )
347 {
348     percentagesDirty = true;
349     effWidthDirty = true;
350     total_percent = 0;
351     hasPercent = false;
352 }
353
354 AutoTableLayout::~AutoTableLayout()
355 {
356 }
357
358 /* recalculates the full structure needed to do layouting and minmax calculations.
359    This is usually calculated on the fly, but needs to be done fully when table cells change
360    dynamically
361 */
362 void AutoTableLayout::recalcColumn( int effCol )
363 {
364     Layout &l = layoutStruct[effCol];
365
366     RenderObject *child = table->firstChild();
367     // first we iterate over all rows.
368
369     RenderTableCell *fixedContributor = 0;
370     RenderTableCell *maxContributor = 0;
371
372     while ( child ) {
373         if ( child->isTableSection() ) {
374             RenderTableSection *section = static_cast<RenderTableSection *>(child);
375             int numRows = section->numRows();
376             RenderTableCell *last = 0;
377             for ( int i = 0; i < numRows; i++ ) {
378                 RenderTableCell *cell = section->cellAt( i,  effCol );
379                 if ( cell == (RenderTableCell *)-1 )
380                     continue;
381                 if ( cell && cell->colSpan() == 1 ) {
382                     // A cell originates in this column.  Ensure we have
383                     // a min/max width of at least 1px for this column now.
384                     l.minWidth = kMax(l.minWidth, 1);
385                     l.maxWidth = kMax(l.maxWidth, 1);
386                     if ( !cell->minMaxKnown() )
387                         cell->calcMinMaxWidth();
388                     if ( cell->minWidth() > l.minWidth )
389                         l.minWidth = cell->minWidth();
390                     if ( cell->maxWidth() > l.maxWidth ) {
391                         l.maxWidth = cell->maxWidth();
392                         maxContributor = cell;
393                     }
394
395                     Length w = cell->style()->width();
396                     if ( w.value > 32760 )
397                         w.value = 32760;
398                     if ( w.value < 0 )
399                         w.value = 0;
400                     switch( w.type ) {
401                     case Fixed:
402                         // ignore width=0
403                         if ( w.value > 0 && (int)l.width.type != Percent ) {
404                             int wval = w.value + (cell->paddingLeft()+cell->paddingRight());
405                             if ( l.width.type == Fixed ) {
406                                 // Nav/IE weirdness
407                                 if ((wval > l.width.value) ||
408                                     ((l.width.value == wval) && (maxContributor == cell))) {
409                                     l.width.value = wval;
410                                     fixedContributor = cell;
411                                 }
412                             } else {
413                                 l.width.type = Fixed;
414                                 l.width.value = wval;
415                                 fixedContributor = cell;
416                             }
417                         }
418                         break;
419                     case Percent:
420                         hasPercent = true;
421                         if ( w.value > 0 && (l.width.type != Percent || w.value > l.width.value ) )
422                             l.width = w;
423                         break;
424                     case Relative:
425                         if ( w.type == Variable || (w.type == Relative && w.value > l.width.value ) )
426                                 l.width = w;
427                     default:
428                         break;
429                     }
430                 } else {
431                     if ( cell && (!effCol || section->cellAt( i, effCol-1 ) != cell) ) {
432                         // This spanning cell originates in this column.  Ensure we have
433                         // a min/max width of at least 1px for this column now.
434                         l.minWidth = kMax(l.minWidth, 1);
435                         l.maxWidth = kMax(l.maxWidth, 1);
436                         insertSpanCell( cell );
437                     }
438                     last = cell;
439                 }
440             }
441         }
442         child = child->nextSibling();
443     }
444
445     // Nav/IE weirdness
446     if ( l.width.type == Fixed ) {
447         if ( table->style()->htmlHacks()
448              && (l.maxWidth > l.width.value) && (fixedContributor != maxContributor)) {
449             l.width = Length();
450             fixedContributor = 0;
451         }
452     }
453
454     l.maxWidth = kMax(l.maxWidth, l.minWidth);
455 #ifdef DEBUG_LAYOUT
456     qDebug("col %d, final min=%d, max=%d, width=%d(%d)", effCol, l.minWidth, l.maxWidth, l.width.value,  l.width.type );
457 #endif
458
459     // ### we need to add col elements aswell
460 }
461
462
463 void AutoTableLayout::fullRecalc()
464 {
465     percentagesDirty = true;
466     hasPercent = false;
467     effWidthDirty = true;
468
469     int nEffCols = table->numEffCols();
470     layoutStruct.resize( nEffCols );
471     layoutStruct.fill( Layout() );
472     spanCells.fill( 0 );
473
474     RenderObject *child = table->firstChild();
475     Length grpWidth;
476     int cCol = 0;
477     while ( child ) {
478         if ( child->isTableCol() ) {
479             RenderTableCol *col = static_cast<RenderTableCol *>(child);
480             int span = col->span();
481             if ( col->firstChild() ) {
482                 grpWidth = col->style()->width();
483             } else {
484                 Length w = col->style()->width();
485                 if ( w.isVariable() )
486                     w = grpWidth;
487                 if ( (w.type == Fixed && w.value == 0) ||
488                      (w.type == Percent && w.value == 0) )
489                     w = Length();
490                 int cEffCol = table->colToEffCol( cCol );
491 #ifdef DEBUG_LAYOUT
492                 qDebug("    col element %d (eff=%d): Length=%d(%d), span=%d, effColSpan=%d",  cCol, cEffCol, w.value, w.type, span, table->spanOfEffCol(cEffCol ) );
493 #endif
494                 if ( (int)w.type != Variable && span == 1 && cEffCol < nEffCols ) {
495                     if ( table->spanOfEffCol( cEffCol ) == 1 ) {
496                         layoutStruct[cEffCol].width = w;
497                         if (w.isFixed() && layoutStruct[cEffCol].maxWidth < w.value)
498                             layoutStruct[cEffCol].maxWidth = w.value;
499                     }
500                 }
501                 cCol += span;
502             }
503         } else {
504             break;
505         }
506
507         RenderObject *next = child->firstChild();
508         if ( !next )
509             next = child->nextSibling();
510         if ( !next && child->parent()->isTableCol() ) {
511             next = child->parent()->nextSibling();
512             grpWidth = Length();
513         }
514         child = next;
515     }
516
517
518     for ( int i = 0; i < nEffCols; i++ )
519         recalcColumn( i );
520 }
521
522 static bool shouldScaleColumns(RenderTable* table)
523 {
524     // A special case.  If this table is not fixed width and contained inside
525     // a cell, then don't bloat the maxwidth by examining percentage growth.
526     bool scale = true;
527     while (table) {
528         Length tw = table->style()->width();
529         if ((tw.isVariable() || tw.isPercent()) && !table->isPositioned()) {
530             RenderBlock* cb = table->containingBlock();
531             while (cb && !cb->isCanvas() && !cb->isTableCell() &&
532                 cb->style()->width().isVariable() && !cb->isPositioned())
533                 cb = cb->containingBlock();
534
535             table = 0;
536             if (cb && cb->isTableCell() &&
537                 (cb->style()->width().isVariable() || cb->style()->width().isPercent())) {
538                 if (tw.isPercent())
539                     scale = false;
540                 else {
541                     RenderTableCell* cell = static_cast<RenderTableCell*>(cb);
542                     if (cell->colSpan() > 1 || cell->table()->style()->width().isVariable())
543                         scale = false;
544                     else
545                         table = cell->table();
546                 }
547             }
548         }
549         else
550             table = 0;
551     }
552     return scale;
553 }
554
555 void AutoTableLayout::calcMinMaxWidth()
556 {
557 #ifdef DEBUG_LAYOUT
558     qDebug("AutoTableLayout::calcMinMaxWidth");
559 #endif
560     fullRecalc();
561
562     int spanMaxWidth = calcEffectiveWidth();
563     int minWidth = 0;
564     int maxWidth = 0;
565     int maxPercent = 0;
566     int maxNonPercent = 0;
567
568     int remainingPercent = 100;
569     for ( unsigned int i = 0; i < layoutStruct.size(); i++ ) {
570         minWidth += layoutStruct[i].effMinWidth;
571         maxWidth += layoutStruct[i].effMaxWidth;
572         if ( layoutStruct[i].effWidth.type == Percent ) {
573             int percent = kMin(layoutStruct[i].effWidth.value, remainingPercent);
574             int pw = ( layoutStruct[i].effMaxWidth * 100) / kMax(percent, 1);
575             remainingPercent -= percent;
576             maxPercent = kMax( pw,  maxPercent );
577         } else {
578             maxNonPercent += layoutStruct[i].effMaxWidth;
579         }
580     }
581
582     if (shouldScaleColumns(table)) {
583         maxNonPercent = (maxNonPercent * 100 + 50) / kMax(remainingPercent, 1);
584         maxWidth = kMax( maxNonPercent,  maxWidth );
585         maxWidth = kMax( maxWidth, maxPercent );
586     }
587
588     maxWidth = kMax( maxWidth, spanMaxWidth );
589     
590     int bs = table->bordersPaddingAndSpacing();
591     minWidth += bs;
592     maxWidth += bs;
593
594     Length tw = table->style()->width();
595     if ( tw.isFixed() && tw.value > 0 ) {
596         minWidth = kMax( minWidth, int( tw.value ) );
597         maxWidth = minWidth;
598     }
599
600     table->m_maxWidth = maxWidth;
601     table->m_minWidth = minWidth;
602 #ifdef DEBUG_LAYOUT
603     qDebug("    minWidth=%d, maxWidth=%d", table->m_minWidth, table->m_maxWidth );
604 #endif
605 }
606
607 /*
608   This method takes care of colspans.
609   effWidth is the same as width for cells without colspans. If we have colspans, they get modified.
610  */
611 int AutoTableLayout::calcEffectiveWidth()
612 {
613     int tMaxWidth = 0;
614
615     unsigned int nEffCols = layoutStruct.size();
616     int hspacing = table->hBorderSpacing();
617 #ifdef DEBUG_LAYOUT
618     qDebug("AutoTableLayout::calcEffectiveWidth for %d cols", nEffCols );
619 #endif
620     for ( unsigned int i = 0; i < nEffCols; i++ ) {
621         layoutStruct[i].effWidth = layoutStruct[i].width;
622         layoutStruct[i].effMinWidth = layoutStruct[i].minWidth;
623         layoutStruct[i].effMaxWidth = layoutStruct[i].maxWidth;
624     }
625
626     for ( unsigned int i = 0; i < spanCells.size(); i++ ) {
627         RenderTableCell *cell = spanCells[i];
628         if ( !cell || cell == (RenderTableCell *)-1 )
629             break;
630         int span = cell->colSpan();
631
632         Length w = cell->style()->width();
633         if ( !(w.type == Relative) && w.value == 0 )
634             w = Length(); // make it Variable
635
636         int col = table->colToEffCol( cell->col() );
637         unsigned int lastCol = col;
638         int cMinWidth = cell->minWidth() + hspacing;
639         int cMaxWidth = cell->maxWidth() + hspacing;
640         int totalPercent = 0;
641         int minWidth = 0;
642         int maxWidth = 0;
643         bool allColsArePercent = true;
644         bool allColsAreFixed = true;
645         bool haveVariable = false;
646         int fixedWidth = 0;
647 #ifdef DEBUG_LAYOUT
648         int cSpan = span;
649 #endif
650         while ( lastCol < nEffCols && span > 0 ) {
651             switch( layoutStruct[lastCol].width.type ) {
652             case Percent:
653                 totalPercent += layoutStruct[lastCol].width.value;
654                 allColsAreFixed = false;
655                 break;
656             case Fixed:
657                 if (layoutStruct[lastCol].width.value > 0) {
658                     fixedWidth += layoutStruct[lastCol].width.value;
659                     allColsArePercent = false;
660                     // IE resets effWidth to Variable here, but this breaks the konqueror about page and seems to be some bad
661                     // legacy behaviour anyway. mozilla doesn't do this so I decided we don't neither.
662                     break;
663                 }
664                 // fall through
665             case Variable:
666                 haveVariable = true;
667                 // fall through
668             default:
669                 // If the column is a percentage width, do not let the spanning cell overwrite the
670                 // width value.  This caused a mis-rendering on amazon.com.
671                 // Sample snippet:
672                 // <table border=2 width=100%><
673                 //   <tr><td>1</td><td colspan=2>2-3</tr>
674                 //   <tr><td>1</td><td colspan=2 width=100%>2-3</td></tr>
675                 // </table>
676                 if (layoutStruct[lastCol].effWidth.type != Percent) {
677                     layoutStruct[lastCol].effWidth = Length();
678                     allColsArePercent = false;
679                 }
680                 else
681                     totalPercent += layoutStruct[lastCol].effWidth.value;
682                 allColsAreFixed = false;
683             }
684             span -= table->spanOfEffCol( lastCol );
685             minWidth += layoutStruct[lastCol].effMinWidth;
686             maxWidth += layoutStruct[lastCol].effMaxWidth;
687             lastCol++;
688             cMinWidth -= hspacing;
689             cMaxWidth -= hspacing;
690         }
691 #ifdef DEBUG_LAYOUT
692         qDebug("    colspan cell %p at effCol %d, span %d, type %d, value %d cmin=%d min=%d fixedwidth=%d", cell, col, cSpan, w.type, w.value, cMinWidth, minWidth, fixedWidth );
693 #endif
694
695         // adjust table max width if needed
696         if ( w.type == Percent ) {
697             if ( totalPercent > w.value || allColsArePercent ) {
698                 // can't satify this condition, treat as variable
699                 w = Length();
700             } else {
701                 int spanMax = kMax( maxWidth, cMaxWidth );
702 #ifdef DEBUG_LAYOUT
703                 qDebug("    adjusting tMaxWidth (%d): spanMax=%d, value=%d, totalPercent=%d", tMaxWidth, spanMax, w.value, totalPercent );
704 #endif
705                 tMaxWidth = kMax( tMaxWidth, spanMax * 100 / w.value );
706
707                 // all non percent columns in the span get percent vlaues to sum up correctly.
708                 int percentMissing = w.value - totalPercent;
709                 int totalWidth = 0;
710                 for ( unsigned int pos = col; pos < lastCol; pos++ ) {
711                     if ( !(layoutStruct[pos].width.type == Percent ) )
712                         totalWidth += layoutStruct[pos].effMaxWidth;
713                 }
714
715                 for ( unsigned int pos = col; pos < lastCol && totalWidth > 0; pos++ ) {
716                     if ( !(layoutStruct[pos].width.type == Percent ) ) {
717                         int percent = percentMissing * layoutStruct[pos].effMaxWidth / totalWidth;
718 #ifdef DEBUG_LAYOUT
719                         qDebug("   col %d: setting percent value %d effMaxWidth=%d totalWidth=%d", pos, percent, layoutStruct[pos].effMaxWidth, totalWidth );
720 #endif
721                         totalWidth -= layoutStruct[pos].effMaxWidth;
722                         percentMissing -= percent;
723                         if ( percent > 0 )
724                             layoutStruct[pos].effWidth = Length( percent, Percent );
725                         else
726                             layoutStruct[pos].effWidth = Length();
727                     }
728                 }
729
730             }
731         }
732
733         // make sure minWidth and maxWidth of the spanning cell are honoured
734         if ( cMinWidth > minWidth ) {
735             if ( allColsAreFixed ) {
736 #ifdef DEBUG_LAYOUT
737                 qDebug("extending minWidth of cols %d-%d to %dpx currentMin=%d accroding to fixed sum %d", col, lastCol-1, cMinWidth, minWidth, fixedWidth );
738 #endif
739                 for ( unsigned int pos = col; fixedWidth > 0 && pos < lastCol; pos++ ) {
740                     int w = kMax( layoutStruct[pos].effMinWidth, cMinWidth * layoutStruct[pos].width.value / fixedWidth );
741 #ifdef DEBUG_LAYOUT
742                     qDebug("   col %d: min=%d, effMin=%d, new=%d", pos, layoutStruct[pos].effMinWidth, layoutStruct[pos].effMinWidth, w );
743 #endif
744                     fixedWidth -= layoutStruct[pos].width.value;
745                     cMinWidth -= w;
746                     layoutStruct[pos].effMinWidth = w;
747                 }
748
749             } else {
750 #ifdef DEBUG_LAYOUT
751                 qDebug("extending minWidth of cols %d-%d to %dpx currentMin=%d", col, lastCol-1, cMinWidth, minWidth );
752 #endif
753                 int maxw = maxWidth;
754                 int minw = minWidth;
755                 
756                 // Give min to variable first, to fixed second, and to others third.
757                 for ( unsigned int pos = col; maxw > 0 && pos < lastCol; pos++ ) {
758                     if ( layoutStruct[pos].width.type == Fixed && haveVariable && fixedWidth <= cMinWidth ) {
759                         int w = kMax( layoutStruct[pos].effMinWidth, layoutStruct[pos].width.value );
760                         fixedWidth -= layoutStruct[pos].width.value;
761                         minw -= layoutStruct[pos].effMinWidth;
762 #ifdef DEBUG_LAYOUT
763                         qDebug("   col %d: min=%d, effMin=%d, new=%d", pos, layoutStruct[pos].effMinWidth, layoutStruct[pos].effMinWidth, w );
764 #endif
765                         maxw -= layoutStruct[pos].effMaxWidth;
766                         cMinWidth -= w;
767                         layoutStruct[pos].effMinWidth = w;
768                     }
769                 }
770
771                 for ( unsigned int pos = col; maxw > 0 && pos < lastCol && minw < cMinWidth; pos++ ) {
772                     if ( !(layoutStruct[pos].width.type == Fixed && haveVariable && fixedWidth <= cMinWidth) ) {
773                         int w = kMax( layoutStruct[pos].effMinWidth, cMinWidth * layoutStruct[pos].effMaxWidth / maxw );
774                         w = kMin(layoutStruct[pos].effMinWidth+(cMinWidth-minw), w);
775                                                 
776 #ifdef DEBUG_LAYOUT
777                         qDebug("   col %d: min=%d, effMin=%d, new=%d", pos, layoutStruct[pos].effMinWidth, layoutStruct[pos].effMinWidth, w );
778 #endif
779                         maxw -= layoutStruct[pos].effMaxWidth;
780                         minw -= layoutStruct[pos].effMinWidth;
781                         cMinWidth -= w;
782                         layoutStruct[pos].effMinWidth = w;
783                     }
784                 }
785             }
786         }
787         if ( !(w.type == Percent ) ) {
788             if ( cMaxWidth > maxWidth ) {
789 #ifdef DEBUG_LAYOUT
790                 qDebug("extending maxWidth of cols %d-%d to %dpx", col, lastCol-1, cMaxWidth );
791 #endif
792                 for ( unsigned int pos = col; maxWidth > 0 && pos < lastCol; pos++ ) {
793                     int w = kMax( layoutStruct[pos].effMaxWidth, cMaxWidth * layoutStruct[pos].effMaxWidth / maxWidth );
794 #ifdef DEBUG_LAYOUT
795                     qDebug("   col %d: max=%d, effMax=%d, new=%d", pos, layoutStruct[pos].effMaxWidth, layoutStruct[pos].effMaxWidth, w );
796 #endif
797                     maxWidth -= layoutStruct[pos].effMaxWidth;
798                     cMaxWidth -= w;
799                     layoutStruct[pos].effMaxWidth = w;
800                 }
801             }
802         } else {
803             for ( unsigned int pos = col; pos < lastCol; pos++ )
804                 layoutStruct[pos].maxWidth = kMax(layoutStruct[pos].maxWidth, layoutStruct[pos].minWidth );
805         }
806     }
807     effWidthDirty = false;
808
809 //     qDebug("calcEffectiveWidth: tMaxWidth=%d",  tMaxWidth );
810     return tMaxWidth;
811 }
812
813 /* gets all cells that originate in a column and have a cellspan > 1
814    Sorts them by increasing cellspan
815 */
816 void AutoTableLayout::insertSpanCell( RenderTableCell *cell )
817 {
818     if ( !cell || cell == (RenderTableCell *)-1 || cell->colSpan() == 1 )
819         return;
820
821 //     qDebug("inserting span cell %p with span %d", cell, cell->colSpan() );
822     int size = spanCells.size();
823     if ( !size || spanCells[size-1] != 0 ) {
824         spanCells.resize( size + 10 );
825         for ( int i = 0; i < 10; i++ )
826             spanCells[size+i] = 0;
827         size += 10;
828     }
829
830     // add them in sort. This is a slow algorithm, and a binary search or a fast sorting after collection would be better
831     unsigned int pos = 0;
832     int span = cell->colSpan();
833     while ( pos < spanCells.size() && spanCells[pos] && span > spanCells[pos]->colSpan() )
834         pos++;
835     memmove( spanCells.data()+pos+1, spanCells.data()+pos, (size-pos-1)*sizeof( RenderTableCell * ) );
836     spanCells[pos] = cell;
837 }
838
839
840 void AutoTableLayout::layout()
841 {
842     // table layout based on the values collected in the layout structure.
843     int tableWidth = table->width() - table->bordersPaddingAndSpacing();
844     int available = tableWidth;
845     int nEffCols = table->numEffCols();
846
847     if ( nEffCols != (int)layoutStruct.size() ) {
848         qWarning("WARNING: nEffCols is not equal to layoutstruct!" );
849         fullRecalc();
850         nEffCols = table->numEffCols();
851     }
852 #ifdef DEBUG_LAYOUT
853     qDebug("AutoTableLayout::layout()");
854 #endif
855
856     if ( effWidthDirty )
857         calcEffectiveWidth();
858
859 #ifdef DEBUG_LAYOUT
860     qDebug("    tableWidth=%d,  nEffCols=%d", tableWidth,  nEffCols );
861     for ( int i = 0; i < nEffCols; i++ ) {
862         qDebug("    effcol %d is of type %d value %d, minWidth=%d, maxWidth=%d",
863                i, layoutStruct[i].width.type, layoutStruct[i].width.value,
864                layoutStruct[i].minWidth, layoutStruct[i].maxWidth );
865         qDebug("        effective: type %d value %d, minWidth=%d, maxWidth=%d",
866                layoutStruct[i].effWidth.type, layoutStruct[i].effWidth.value,
867                layoutStruct[i].effMinWidth, layoutStruct[i].effMaxWidth );
868     }
869 #endif
870
871     bool havePercent = false;
872     bool haveRelative = false;
873     int totalRelative = 0;
874     int numVariable = 0;
875     int numFixed = 0;
876     int totalVariable = 0;
877     int totalFixed = 0;
878     int totalPercent = 0;
879     int allocVariable = 0;
880
881     // fill up every cell with its minWidth
882     for ( int i = 0; i < nEffCols; i++ ) {
883         int w = layoutStruct[i].effMinWidth;
884         layoutStruct[i].calcWidth = w;
885         available -= w;
886         Length& width = layoutStruct[i].effWidth;
887         switch( width.type) {
888         case Percent:
889             havePercent = true;
890             totalPercent += width.value;
891             break;
892         case Relative:
893             haveRelative = true;
894             totalRelative += width.value;
895             break;
896         case Fixed:
897             numFixed++;
898             totalFixed += layoutStruct[i].effMaxWidth;
899             // fall through
900             break;
901         case Variable:
902         case Static:
903             numVariable++;
904             totalVariable += layoutStruct[i].effMaxWidth;
905             allocVariable += w;
906         default:
907             break;
908         }
909     }
910
911     // allocate width to percent cols
912     if ( available > 0 && havePercent ) {
913         for ( int i = 0; i < nEffCols; i++ ) {
914             Length &width = layoutStruct[i].effWidth;
915             if ( width.type == Percent ) {
916                 int w = kMax ( int( layoutStruct[i].effMinWidth ), width.minWidth( tableWidth ) );
917                 available += layoutStruct[i].calcWidth - w;
918                 layoutStruct[i].calcWidth = w;
919             }
920         }
921         if ( totalPercent > 100 ) {
922             // remove overallocated space from the last columns
923             int excess = tableWidth*(totalPercent-100)/100;
924             for ( int i = nEffCols-1; i >= 0; i-- ) {
925                 if ( layoutStruct[i].effWidth.type == Percent ) {
926                     int w = layoutStruct[i].calcWidth;
927                     int reduction = kMin( w,  excess );
928                     // the lines below might look inconsistent, but that's the way it's handled in mozilla
929                     excess -= reduction;
930                     int newWidth = kMax( int (layoutStruct[i].effMinWidth), w - reduction );
931                     available += w - newWidth;
932                     layoutStruct[i].calcWidth = newWidth;
933                     //qDebug("col %d: reducing to %d px (reduction=%d)", i, newWidth, reduction );
934                 }
935             }
936         }
937     }
938 #ifdef DEBUG_LAYOUT
939     qDebug("percent satisfied: available is %d", available);
940 #endif
941     
942     // then allocate width to fixed cols
943     if ( available > 0 ) {
944         for ( int i = 0; i < nEffCols; ++i ) {
945             Length &width = layoutStruct[i].effWidth;
946             if ( width.type == Fixed && width.value > layoutStruct[i].calcWidth ) {
947                 available += layoutStruct[i].calcWidth - width.value;
948                 layoutStruct[i].calcWidth = width.value;
949             }
950         }
951     }
952 #ifdef DEBUG_LAYOUT
953     qDebug("fixed satisfied: available is %d", available);
954 #endif
955
956     // now satisfy relative
957     if ( available > 0 ) {
958         for ( int i = 0; i < nEffCols; i++ ) {
959             Length &width = layoutStruct[i].effWidth;
960             if ( width.type == Relative && width.value != 0 ) {
961                 // width=0* gets effMinWidth.
962                 int w = width.value*tableWidth/totalRelative;
963                 available += layoutStruct[i].calcWidth - w;
964                 layoutStruct[i].calcWidth = w;
965             }
966         }
967     }
968
969     // now satisfy variable
970     if ( available > 0 && numVariable ) {
971         available += allocVariable; // this gets redistributed
972         //qDebug("redistributing %dpx to %d variable columns. totalVariable=%d",  available,  numVariable,  totalVariable );
973         for ( int i = 0; i < nEffCols; i++ ) {
974             Length &width = layoutStruct[i].effWidth;
975             if ( width.type == Variable && totalVariable != 0 ) {
976                 int w = kMax( int ( layoutStruct[i].calcWidth ),
977                               available * layoutStruct[i].effMaxWidth / totalVariable );
978                 available -= w;
979                 totalVariable -= layoutStruct[i].effMaxWidth;
980                 layoutStruct[i].calcWidth = w;
981             }
982         }
983     }
984 #ifdef DEBUG_LAYOUT
985     qDebug("variable satisfied: available is %d",  available );
986 #endif
987
988     // spread over fixed columns
989     if (available > 0 && numFixed) {
990         // still have some width to spread, distribute to fixed columns
991         for ( int i = 0; i < nEffCols; i++ ) {
992             Length &width = layoutStruct[i].effWidth;
993             if ( width.isFixed() ) {
994                 int w = available * layoutStruct[i].effMaxWidth / totalFixed;
995                 available -= w;
996                 totalFixed -= layoutStruct[i].effMaxWidth;
997                 layoutStruct[i].calcWidth += w;
998             }
999         }
1000     }
1001     
1002 #ifdef DEBUG_LAYOUT
1003     qDebug("after fixed distribution: available=%d",  available );
1004 #endif
1005     
1006     // spread over percent colums
1007     if (available > 0 && hasPercent && totalPercent < 100) {
1008         // still have some width to spread, distribute weighted to percent columns
1009         for ( int i = 0; i < nEffCols; i++ ) {
1010             Length &width = layoutStruct[i].effWidth;
1011             if ( width.isPercent() ) {
1012                 int w = available * width.value / totalPercent;
1013                 available -= w;
1014                 totalPercent -= width.value;
1015                 layoutStruct[i].calcWidth += w;
1016                 if (!available || !totalPercent) break;
1017             }
1018         }
1019     }
1020
1021 #ifdef DEBUG_LAYOUT
1022     qDebug("after percent distribution: available=%d",  available );
1023 #endif
1024
1025     // spread over the rest
1026     if ( available > 0 ) {
1027         int total = nEffCols;
1028         // still have some width to spread
1029         int i = nEffCols;
1030         while (  i-- ) {
1031             int w = available / total;
1032             available -= w;
1033             total--;
1034             layoutStruct[i].calcWidth += w;
1035         }
1036     }
1037
1038 #ifdef DEBUG_LAYOUT
1039     qDebug("after equal distribution: available=%d",  available );
1040 #endif
1041     // if we have overallocated, reduce every cell according to the difference between desired width and minwidth
1042     // this seems to produce to the pixel exaxt results with IE. Wonder is some of this also holds for width distributing.
1043     if ( available < 0 ) {
1044         // Need to reduce cells with the following prioritization:
1045         // (1) Variable
1046         // (2) Relative
1047         // (3) Fixed
1048         // (4) Percent
1049         // This is basically the reverse of how we grew the cells.
1050         if (available < 0) {
1051             int mw = 0;
1052             for ( int i = nEffCols-1; i >= 0; i-- ) {
1053                 Length &width = layoutStruct[i].effWidth;
1054                 if (width.isVariable())
1055                     mw += layoutStruct[i].calcWidth - layoutStruct[i].effMinWidth;
1056             }
1057             
1058             for ( int i = nEffCols-1; i >= 0 && mw > 0; i-- ) {
1059                 Length &width = layoutStruct[i].effWidth;
1060                 if (width.isVariable()) {
1061                     int minMaxDiff = layoutStruct[i].calcWidth-layoutStruct[i].effMinWidth;
1062                     int reduce = available * minMaxDiff / mw;
1063                     layoutStruct[i].calcWidth += reduce;
1064                     available -= reduce;
1065                     mw -= minMaxDiff;
1066                     if ( available >= 0 )
1067                         break;
1068                 }
1069             }
1070         }
1071
1072         if (available < 0) {
1073             int mw = 0;
1074             for ( int i = nEffCols-1; i >= 0; i-- ) {
1075                 Length &width = layoutStruct[i].effWidth;
1076                 if (width.isRelative())
1077                     mw += layoutStruct[i].calcWidth - layoutStruct[i].effMinWidth;
1078             }
1079             
1080             for ( int i = nEffCols-1; i >= 0 && mw > 0; i-- ) {
1081                 Length &width = layoutStruct[i].effWidth;
1082                 if (width.isRelative()) {
1083                     int minMaxDiff = layoutStruct[i].calcWidth-layoutStruct[i].effMinWidth;
1084                     int reduce = available * minMaxDiff / mw;
1085                     layoutStruct[i].calcWidth += reduce;
1086                     available -= reduce;
1087                     mw -= minMaxDiff;
1088                     if ( available >= 0 )
1089                         break;
1090                 }
1091             }
1092         }
1093
1094         if (available < 0) {
1095             int mw = 0;
1096             for ( int i = nEffCols-1; i >= 0; i-- ) {
1097                 Length &width = layoutStruct[i].effWidth;
1098                 if (width.isFixed())
1099                     mw += layoutStruct[i].calcWidth - layoutStruct[i].effMinWidth;
1100             }
1101             
1102             for ( int i = nEffCols-1; i >= 0 && mw > 0; i-- ) {
1103                 Length &width = layoutStruct[i].effWidth;
1104                 if (width.isFixed()) {
1105                     int minMaxDiff = layoutStruct[i].calcWidth-layoutStruct[i].effMinWidth;
1106                     int reduce = available * minMaxDiff / mw;
1107                     layoutStruct[i].calcWidth += reduce;
1108                     available -= reduce;
1109                     mw -= minMaxDiff;
1110                     if ( available >= 0 )
1111                         break;
1112                 }
1113             }
1114         }
1115
1116         if (available < 0) {
1117             int mw = 0;
1118             for ( int i = nEffCols-1; i >= 0; i-- ) {
1119                 Length &width = layoutStruct[i].effWidth;
1120                 if (width.isPercent())
1121                     mw += layoutStruct[i].calcWidth - layoutStruct[i].effMinWidth;
1122             }
1123             
1124             for ( int i = nEffCols-1; i >= 0 && mw > 0; i-- ) {
1125                 Length &width = layoutStruct[i].effWidth;
1126                 if (width.isPercent()) {
1127                     int minMaxDiff = layoutStruct[i].calcWidth-layoutStruct[i].effMinWidth;
1128                     int reduce = available * minMaxDiff / mw;
1129                     layoutStruct[i].calcWidth += reduce;
1130                     available -= reduce;
1131                     mw -= minMaxDiff;
1132                     if ( available >= 0 )
1133                         break;
1134                 }
1135             }
1136         }
1137     }
1138
1139     //qDebug( "    final available=%d", available );
1140
1141     int pos = 0;
1142     for ( int i = 0; i < nEffCols; i++ ) {
1143 #ifdef DEBUG_LAYOUT
1144         qDebug("col %d: %d (width %d)", i, pos, layoutStruct[i].calcWidth );
1145 #endif
1146         table->columnPos[i] = pos;
1147         pos += layoutStruct[i].calcWidth + table->hBorderSpacing();
1148     }
1149     table->columnPos[table->columnPos.size()-1] = pos;
1150
1151 }
1152
1153
1154 void AutoTableLayout::calcPercentages() const
1155 {
1156     total_percent = 0;
1157     for ( unsigned int i = 0; i < layoutStruct.size(); i++ ) {
1158         if ( layoutStruct[i].width.type == Percent )
1159             total_percent += layoutStruct[i].width.value;
1160     }
1161     percentagesDirty = false;
1162 }
1163
1164 #undef DEBUG_LAYOUT