Reviewed by Darin.
[WebKit-https.git] / WebCore / rendering / AutoTableLayout.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, 2006 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., 51 Franklin Street, Fifth Floor,
21  * Boston, MA 02110-1301, USA.
22  */
23
24 #include "config.h"
25 #include "AutoTableLayout.h"
26
27 #include "RenderTable.h"
28 #include "RenderTableCell.h"
29 #include "RenderTableCol.h"
30 #include "RenderTableSection.h"
31
32 using namespace std;
33
34 namespace WebCore {
35
36 AutoTableLayout::AutoTableLayout(RenderTable* table)
37     : TableLayout(table)
38     , m_hasPercent(false)
39     , m_percentagesDirty(true)
40     , m_effWidthDirty(true)
41     , m_totalPercent(0)
42 {
43 }
44
45 AutoTableLayout::~AutoTableLayout()
46 {
47 }
48
49 /* recalculates the full structure needed to do layouting and minmax calculations.
50    This is usually calculated on the fly, but needs to be done fully when table cells change
51    dynamically
52 */
53 void AutoTableLayout::recalcColumn(int effCol)
54 {
55     Layout &l = m_layoutStruct[effCol];
56
57     RenderObject* child = m_table->firstChild();
58     // first we iterate over all rows.
59
60     RenderTableCell* fixedContributor = 0;
61     RenderTableCell* maxContributor = 0;
62
63     while (child) {
64         if (child->isTableSection()) {
65             RenderTableSection* section = static_cast<RenderTableSection*>(child);
66             int numRows = section->numRows();
67             RenderTableCell* last = 0;
68             for (int i = 0; i < numRows; i++) {
69                 RenderTableSection::CellStruct current = section->cellAt(i, effCol);
70                 RenderTableCell* cell = current.cell;
71                 
72                 bool cellHasContent = cell && (cell->firstChild() || m_table->cellPadding() || cell->style()->hasBorder() || cell->style()->hasPadding());
73                 if (cellHasContent)
74                     l.emptyCellsOnly = false;
75                     
76                 if (current.inColSpan)
77                     continue;
78                 if (cell && cell->colSpan() == 1) {
79                     // A cell originates in this column.  Ensure we have
80                     // a min/max width of at least 1px for this column now.
81                     l.minWidth = max(l.minWidth, cellHasContent ? 1 : 0);
82                     l.maxWidth = max(l.maxWidth, 1);
83                     if (cell->prefWidthsDirty())
84                         cell->calcPrefWidths();
85                     l.minWidth = max(cell->minPrefWidth(), l.minWidth);
86                     if (cell->maxPrefWidth() > l.maxWidth) {
87                         l.maxWidth = cell->maxPrefWidth();
88                         maxContributor = cell;
89                     }
90
91                     Length w = cell->styleOrColWidth();
92                     // FIXME: What is this arbitrary value?
93                     if (w.rawValue() > 32760)
94                         w.setRawValue(32760);
95                     if (w.isNegative())
96                         w.setValue(0);
97                     switch(w.type()) {
98                     case Fixed:
99                         // ignore width=0
100                         if (w.value() > 0 && (int)l.width.type() != Percent) {
101                             int wval = cell->calcBorderBoxWidth(w.value());
102                             if (l.width.isFixed()) {
103                                 // Nav/IE weirdness
104                                 if ((wval > l.width.value()) ||
105                                     ((l.width.value() == wval) && (maxContributor == cell))) {
106                                     l.width.setValue(wval);
107                                     fixedContributor = cell;
108                                 }
109                             } else {
110                                 l.width.setValue(Fixed, wval);
111                                 fixedContributor = cell;
112                             }
113                         }
114                         break;
115                     case Percent:
116                         m_hasPercent = true;
117                         if (w.isPositive() && (!l.width.isPercent() || w.rawValue() > l.width.rawValue()))
118                             l.width = w;
119                         break;
120                     case Relative:
121                         // FIXME: Need to understand this case and whether it makes sense to compare values
122                         // which are not necessarily of the same type.
123                         if (w.isAuto() || (w.isRelative() && w.value() > l.width.rawValue()))
124                             l.width = w;
125                     default:
126                         break;
127                     }
128                 } else {
129                     if (cell && (!effCol || section->cellAt(i, effCol-1).cell != cell)) {
130                         // This spanning cell originates in this column.  Ensure we have
131                         // a min/max width of at least 1px for this column now.
132                         l.minWidth = max(l.minWidth, cellHasContent ? 1 : 0);
133                         l.maxWidth = max(l.maxWidth, 1);
134                         insertSpanCell(cell);
135                     }
136                     last = cell;
137                 }
138             }
139         }
140         child = child->nextSibling();
141     }
142
143     // Nav/IE weirdness
144     if (l.width.isFixed()) {
145         if (m_table->style()->htmlHacks() && l.maxWidth > l.width.value() && fixedContributor != maxContributor) {
146             l.width = Length();
147             fixedContributor = 0;
148         }
149     }
150
151     l.maxWidth = max(l.maxWidth, l.minWidth);
152 #ifdef DEBUG_LAYOUT
153     qDebug("col %d, final min=%d, max=%d, width=%d(%d)", effCol, l.minWidth, l.maxWidth, l.width.value,  l.width.type);
154 #endif
155
156     // ### we need to add col elements as well
157 }
158
159 void AutoTableLayout::fullRecalc()
160 {
161     m_percentagesDirty = true;
162     m_hasPercent = false;
163     m_effWidthDirty = true;
164
165     int nEffCols = m_table->numEffCols();
166     m_layoutStruct.resize(nEffCols);
167     m_layoutStruct.fill(Layout());
168     m_spanCells.fill(0);
169
170     RenderObject *child = m_table->firstChild();
171     Length grpWidth;
172     int cCol = 0;
173     while (child) {
174         if (child->isTableCol()) {
175             RenderTableCol *col = static_cast<RenderTableCol*>(child);
176             int span = col->span();
177             if (col->firstChild()) {
178                 grpWidth = col->style()->width();
179             } else {
180                 Length w = col->style()->width();
181                 if (w.isAuto())
182                     w = grpWidth;
183                 if ((w.isFixed() || w.isPercent()) && w.isZero())
184                     w = Length();
185                 int cEffCol = m_table->colToEffCol(cCol);
186 #ifdef DEBUG_LAYOUT
187                 qDebug("    col element %d (eff=%d): Length=%d(%d), span=%d, effColSpan=%d",  cCol, cEffCol, w.value, w.type, span, m_table->spanOfEffCol(cEffCol));
188 #endif
189                 if (!w.isAuto() && span == 1 && cEffCol < nEffCols) {
190                     if (m_table->spanOfEffCol(cEffCol) == 1) {
191                         m_layoutStruct[cEffCol].width = w;
192                         if (w.isFixed() && m_layoutStruct[cEffCol].maxWidth < w.value())
193                             m_layoutStruct[cEffCol].maxWidth = w.value();
194                     }
195                 }
196                 cCol += span;
197             }
198         } else {
199             break;
200         }
201
202         RenderObject *next = child->firstChild();
203         if (!next)
204             next = child->nextSibling();
205         if (!next && child->parent()->isTableCol()) {
206             next = child->parent()->nextSibling();
207             grpWidth = Length();
208         }
209         child = next;
210     }
211
212
213     for (int i = 0; i < nEffCols; i++)
214         recalcColumn(i);
215 }
216
217 static bool shouldScaleColumns(RenderTable* table)
218 {
219     // A special case.  If this table is not fixed width and contained inside
220     // a cell, then don't bloat the maxwidth by examining percentage growth.
221     bool scale = true;
222     while (table) {
223         Length tw = table->style()->width();
224         if ((tw.isAuto() || tw.isPercent()) && !table->isPositioned()) {
225             RenderBlock* cb = table->containingBlock();
226             while (cb && !cb->isRenderView() && !cb->isTableCell() &&
227                 cb->style()->width().isAuto() && !cb->isPositioned())
228                 cb = cb->containingBlock();
229
230             table = 0;
231             if (cb && cb->isTableCell() &&
232                 (cb->style()->width().isAuto() || cb->style()->width().isPercent())) {
233                 if (tw.isPercent())
234                     scale = false;
235                 else {
236                     RenderTableCell* cell = static_cast<RenderTableCell*>(cb);
237                     if (cell->colSpan() > 1 || cell->table()->style()->width().isAuto())
238                         scale = false;
239                     else
240                         table = cell->table();
241                 }
242             }
243         }
244         else
245             table = 0;
246     }
247     return scale;
248 }
249
250 void AutoTableLayout::calcPrefWidths(int& minWidth, int& maxWidth)
251 {
252     fullRecalc();
253
254     int spanMaxWidth = calcEffectiveWidth();
255     minWidth = 0;
256     maxWidth = 0;
257     float maxPercent = 0;
258     float maxNonPercent = 0;
259     bool scaleColumns = shouldScaleColumns(m_table);
260
261     // We substitute 0 percent by (epsilon / percentScaleFactor) percent in two places below to avoid division by zero.
262     // FIXME: Handle the 0% cases properly.
263     const int epsilon = 1;
264
265     int remainingPercent = 100 * percentScaleFactor;
266     for (unsigned int i = 0; i < m_layoutStruct.size(); i++) {
267         minWidth += m_layoutStruct[i].effMinWidth;
268         maxWidth += m_layoutStruct[i].effMaxWidth;
269         if (scaleColumns) {
270             if (m_layoutStruct[i].effWidth.isPercent()) {
271                 int percent = min(m_layoutStruct[i].effWidth.rawValue(), remainingPercent);
272                 float pw = static_cast<float>(m_layoutStruct[i].effMaxWidth) * 100 * percentScaleFactor / max(percent, epsilon);
273                 maxPercent = max(pw,  maxPercent);
274                 remainingPercent -= percent;
275             } else
276                 maxNonPercent += m_layoutStruct[i].effMaxWidth;
277         }
278     }
279
280     if (scaleColumns) {
281         maxNonPercent = maxNonPercent * 100 * percentScaleFactor / max(remainingPercent, epsilon);
282         maxWidth = max(maxWidth, static_cast<int>(min(maxNonPercent, INT_MAX / 2.0f)));
283         maxWidth = max(maxWidth, static_cast<int>(min(maxPercent, INT_MAX / 2.0f)));
284     }
285
286     maxWidth = max(maxWidth, spanMaxWidth);
287     
288     int bs = m_table->bordersPaddingAndSpacing();
289     minWidth += bs;
290     maxWidth += bs;
291
292     Length tw = m_table->style()->width();
293     if (tw.isFixed() && tw.value() > 0) {
294         minWidth = max(minWidth, tw.value());
295         maxWidth = minWidth;
296     }
297 }
298
299 /*
300   This method takes care of colspans.
301   effWidth is the same as width for cells without colspans. If we have colspans, they get modified.
302  */
303 int AutoTableLayout::calcEffectiveWidth()
304 {
305     float tMaxWidth = 0;
306
307     unsigned int nEffCols = m_layoutStruct.size();
308     int hspacing = m_table->hBorderSpacing();
309 #ifdef DEBUG_LAYOUT
310     qDebug("AutoTableLayout::calcEffectiveWidth for %d cols", nEffCols);
311 #endif
312     for (unsigned int i = 0; i < nEffCols; i++) {
313         m_layoutStruct[i].effWidth = m_layoutStruct[i].width;
314         m_layoutStruct[i].effMinWidth = m_layoutStruct[i].minWidth;
315         m_layoutStruct[i].effMaxWidth = m_layoutStruct[i].maxWidth;
316     }
317
318     for (unsigned int i = 0; i < m_spanCells.size(); i++) {
319         RenderTableCell *cell = m_spanCells[i];
320         if (!cell)
321             break;
322         int span = cell->colSpan();
323
324         Length w = cell->styleOrColWidth();
325         if (!w.isRelative() && w.isZero())
326             w = Length(); // make it Auto
327
328         int col = m_table->colToEffCol(cell->col());
329         unsigned int lastCol = col;
330         int cMinWidth = cell->minPrefWidth() + hspacing;
331         float cMaxWidth = cell->maxPrefWidth() + hspacing;
332         int totalPercent = 0;
333         int minWidth = 0;
334         float maxWidth = 0;
335         bool allColsArePercent = true;
336         bool allColsAreFixed = true;
337         bool haveAuto = false;
338         bool spanHasEmptyCellsOnly = true;
339         int fixedWidth = 0;
340         while (lastCol < nEffCols && span > 0) {
341             switch (m_layoutStruct[lastCol].width.type()) {
342             case Percent:
343                 totalPercent += m_layoutStruct[lastCol].width.rawValue();
344                 allColsAreFixed = false;
345                 break;
346             case Fixed:
347                 if (m_layoutStruct[lastCol].width.value() > 0) {
348                     fixedWidth += m_layoutStruct[lastCol].width.value();
349                     allColsArePercent = false;
350                     // IE resets effWidth to Auto here, but this breaks the konqueror about page and seems to be some bad
351                     // legacy behaviour anyway. mozilla doesn't do this so I decided we don't neither.
352                     break;
353                 }
354                 // fall through
355             case Auto:
356                 haveAuto = true;
357                 // fall through
358             default:
359                 // If the column is a percentage width, do not let the spanning cell overwrite the
360                 // width value.  This caused a mis-rendering on amazon.com.
361                 // Sample snippet:
362                 // <table border=2 width=100%><
363                 //   <tr><td>1</td><td colspan=2>2-3</tr>
364                 //   <tr><td>1</td><td colspan=2 width=100%>2-3</td></tr>
365                 // </table>
366                 if (!m_layoutStruct[lastCol].effWidth.isPercent()) {
367                     m_layoutStruct[lastCol].effWidth = Length();
368                     allColsArePercent = false;
369                 }
370                 else
371                     totalPercent += m_layoutStruct[lastCol].effWidth.rawValue();
372                 allColsAreFixed = false;
373             }
374             if (!m_layoutStruct[lastCol].emptyCellsOnly)
375                 spanHasEmptyCellsOnly = false;
376             span -= m_table->spanOfEffCol(lastCol);
377             minWidth += m_layoutStruct[lastCol].effMinWidth;
378             maxWidth += m_layoutStruct[lastCol].effMaxWidth;
379             lastCol++;
380             cMinWidth -= hspacing;
381             cMaxWidth -= hspacing;
382         }
383
384         // adjust table max width if needed
385         if (w.isPercent()) {
386             if (totalPercent > w.rawValue() || allColsArePercent) {
387                 // can't satify this condition, treat as variable
388                 w = Length();
389             } else {
390                 float spanMax = max(maxWidth, cMaxWidth);
391                 tMaxWidth = max(tMaxWidth, spanMax * 100 * percentScaleFactor / w.rawValue());
392
393                 // all non percent columns in the span get percent vlaues to sum up correctly.
394                 int percentMissing = w.rawValue() - totalPercent;
395                 float totalWidth = 0;
396                 for (unsigned int pos = col; pos < lastCol; pos++) {
397                     if (!(m_layoutStruct[pos].effWidth.isPercent()))
398                         totalWidth += m_layoutStruct[pos].effMaxWidth;
399                 }
400
401                 for (unsigned int pos = col; pos < lastCol && totalWidth > 0; pos++) {
402                     if (!(m_layoutStruct[pos].effWidth.isPercent())) {
403                         int percent = static_cast<int>(percentMissing * static_cast<float>(m_layoutStruct[pos].effMaxWidth) / totalWidth);
404                         totalWidth -= m_layoutStruct[pos].effMaxWidth;
405                         percentMissing -= percent;
406                         if (percent > 0)
407                             m_layoutStruct[pos].effWidth.setRawValue(Percent, percent);
408                         else
409                             m_layoutStruct[pos].effWidth = Length();
410                     }
411                 }
412
413             }
414         }
415
416         // make sure minWidth and maxWidth of the spanning cell are honoured
417         if (cMinWidth > minWidth) {
418             if (allColsAreFixed) {
419                 for (unsigned int pos = col; fixedWidth > 0 && pos < lastCol; pos++) {
420                     int w = max(m_layoutStruct[pos].effMinWidth, cMinWidth * m_layoutStruct[pos].width.value() / fixedWidth);
421                     fixedWidth -= m_layoutStruct[pos].width.value();
422                     cMinWidth -= w;
423                     m_layoutStruct[pos].effMinWidth = w;
424                 }
425
426             } else {
427                 float maxw = maxWidth;
428                 int minw = minWidth;
429                 
430                 // Give min to variable first, to fixed second, and to others third.
431                 for (unsigned int pos = col; maxw >= 0 && pos < lastCol; pos++) {
432                     if (m_layoutStruct[pos].width.isFixed() && haveAuto && fixedWidth <= cMinWidth) {
433                         int w = max(m_layoutStruct[pos].effMinWidth, m_layoutStruct[pos].width.value());
434                         fixedWidth -= m_layoutStruct[pos].width.value();
435                         minw -= m_layoutStruct[pos].effMinWidth;
436                         maxw -= m_layoutStruct[pos].effMaxWidth;
437                         cMinWidth -= w;
438                         m_layoutStruct[pos].effMinWidth = w;
439                     }
440                 }
441
442                 for (unsigned int pos = col; maxw >= 0 && pos < lastCol && minw < cMinWidth; pos++) {
443                     if (!(m_layoutStruct[pos].width.isFixed() && haveAuto && fixedWidth <= cMinWidth)) {
444                         int w = max(m_layoutStruct[pos].effMinWidth, static_cast<int>(maxw ? cMinWidth * static_cast<float>(m_layoutStruct[pos].effMaxWidth) / maxw : cMinWidth));
445                         w = min(m_layoutStruct[pos].effMinWidth+(cMinWidth-minw), w);
446                                                 
447                         maxw -= m_layoutStruct[pos].effMaxWidth;
448                         minw -= m_layoutStruct[pos].effMinWidth;
449                         cMinWidth -= w;
450                         m_layoutStruct[pos].effMinWidth = w;
451                     }
452                 }
453             }
454         }
455         if (!(w.isPercent())) {
456             if (cMaxWidth > maxWidth) {
457                 for (unsigned int pos = col; maxWidth >= 0 && pos < lastCol; pos++) {
458                     int w = max(m_layoutStruct[pos].effMaxWidth, static_cast<int>(maxWidth ? cMaxWidth * static_cast<float>(m_layoutStruct[pos].effMaxWidth) / maxWidth : cMaxWidth));
459                     maxWidth -= m_layoutStruct[pos].effMaxWidth;
460                     cMaxWidth -= w;
461                     m_layoutStruct[pos].effMaxWidth = w;
462                 }
463             }
464         } else {
465             for (unsigned int pos = col; pos < lastCol; pos++)
466                 m_layoutStruct[pos].maxWidth = max(m_layoutStruct[pos].maxWidth, m_layoutStruct[pos].minWidth);
467         }
468         // treat span ranges consisting of empty cells only as if they had content
469         if (spanHasEmptyCellsOnly)
470             for (unsigned int pos = col; pos < lastCol; pos++)
471                 m_layoutStruct[pos].emptyCellsOnly = false;
472     }
473     m_effWidthDirty = false;
474
475     return static_cast<int>(min(tMaxWidth, INT_MAX / 2.0f));
476 }
477
478 /* gets all cells that originate in a column and have a cellspan > 1
479    Sorts them by increasing cellspan
480 */
481 void AutoTableLayout::insertSpanCell(RenderTableCell *cell)
482 {
483     if (!cell || cell->colSpan() == 1)
484         return;
485
486     int size = m_spanCells.size();
487     if (!size || m_spanCells[size-1] != 0) {
488         m_spanCells.resize(size + 10);
489         for (int i = 0; i < 10; i++)
490             m_spanCells[size+i] = 0;
491         size += 10;
492     }
493
494     // add them in sort. This is a slow algorithm, and a binary search or a fast sorting after collection would be better
495     unsigned int pos = 0;
496     int span = cell->colSpan();
497     while (pos < m_spanCells.size() && m_spanCells[pos] && span > m_spanCells[pos]->colSpan())
498         pos++;
499     memmove(m_spanCells.data()+pos+1, m_spanCells.data()+pos, (size-pos-1)*sizeof(RenderTableCell *));
500     m_spanCells[pos] = cell;
501 }
502
503
504 void AutoTableLayout::layout()
505 {
506     // table layout based on the values collected in the layout structure.
507     int tableWidth = m_table->width() - m_table->bordersPaddingAndSpacing();
508     int available = tableWidth;
509     int nEffCols = m_table->numEffCols();
510
511     if (nEffCols != (int)m_layoutStruct.size()) {
512         fullRecalc();
513         nEffCols = m_table->numEffCols();
514     }
515 #ifdef DEBUG_LAYOUT
516     qDebug("AutoTableLayout::layout()");
517 #endif
518
519     if (m_effWidthDirty)
520         calcEffectiveWidth();
521
522 #ifdef DEBUG_LAYOUT
523     qDebug("    tableWidth=%d,  nEffCols=%d", tableWidth,  nEffCols);
524     for (int i = 0; i < nEffCols; i++) {
525         qDebug("    effcol %d is of type %d value %d, minWidth=%d, maxWidth=%d",
526                i, m_layoutStruct[i].width.type, m_layoutStruct[i].width.value,
527                m_layoutStruct[i].minWidth, m_layoutStruct[i].maxWidth);
528         qDebug("        effective: type %d value %d, minWidth=%d, maxWidth=%d",
529                m_layoutStruct[i].effWidth.type, m_layoutStruct[i].effWidth.value,
530                m_layoutStruct[i].effMinWidth, m_layoutStruct[i].effMaxWidth);
531     }
532 #endif
533
534     bool havePercent = false;
535     bool haveRelative = false;
536     int totalRelative = 0;
537     int numAuto = 0;
538     int numFixed = 0;
539     float totalAuto = 0;
540     float totalFixed = 0;
541     int totalPercent = 0;
542     int allocAuto = 0;
543     int numAutoEmptyCellsOnly = 0;
544
545     // fill up every cell with its minWidth
546     for (int i = 0; i < nEffCols; i++) {
547         int w = m_layoutStruct[i].effMinWidth;
548         m_layoutStruct[i].calcWidth = w;
549         available -= w;
550         Length& width = m_layoutStruct[i].effWidth;
551         switch (width.type()) {
552         case Percent:
553             havePercent = true;
554             totalPercent += width.rawValue();
555             break;
556         case Relative:
557             haveRelative = true;
558             totalRelative += width.value();
559             break;
560         case Fixed:
561             numFixed++;
562             totalFixed += m_layoutStruct[i].effMaxWidth;
563             // fall through
564             break;
565         case Auto:
566         case Static:
567             if (m_layoutStruct[i].emptyCellsOnly) 
568                 numAutoEmptyCellsOnly++;            
569             else {
570                 numAuto++;
571                 totalAuto += m_layoutStruct[i].effMaxWidth;
572                 allocAuto += w;
573             }
574             break;
575         default:
576             break;
577         }
578     }
579
580     // allocate width to percent cols
581     if (available > 0 && havePercent) {
582         for (int i = 0; i < nEffCols; i++) {
583             Length &width = m_layoutStruct[i].effWidth;
584             if (width.isPercent()) {
585                 int w = max(int(m_layoutStruct[i].effMinWidth), width.calcMinValue(tableWidth));
586                 available += m_layoutStruct[i].calcWidth - w;
587                 m_layoutStruct[i].calcWidth = w;
588             }
589         }
590         if (totalPercent > 100 * percentScaleFactor) {
591             // remove overallocated space from the last columns
592             int excess = tableWidth*(totalPercent - 100 * percentScaleFactor) / (100 * percentScaleFactor);
593             for (int i = nEffCols-1; i >= 0; i--) {
594                 if (m_layoutStruct[i].effWidth.isPercent()) {
595                     int w = m_layoutStruct[i].calcWidth;
596                     int reduction = min(w,  excess);
597                     // the lines below might look inconsistent, but that's the way it's handled in mozilla
598                     excess -= reduction;
599                     int newWidth = max(int (m_layoutStruct[i].effMinWidth), w - reduction);
600                     available += w - newWidth;
601                     m_layoutStruct[i].calcWidth = newWidth;
602                 }
603             }
604         }
605     }
606 #ifdef DEBUG_LAYOUT
607     qDebug("percent satisfied: available is %d", available);
608 #endif
609     
610     // then allocate width to fixed cols
611     if (available > 0) {
612         for (int i = 0; i < nEffCols; ++i) {
613             Length &width = m_layoutStruct[i].effWidth;
614             if (width.isFixed() && width.value() > m_layoutStruct[i].calcWidth) {
615                 available += m_layoutStruct[i].calcWidth - width.value();
616                 m_layoutStruct[i].calcWidth = width.value();
617             }
618         }
619     }
620 #ifdef DEBUG_LAYOUT
621     qDebug("fixed satisfied: available is %d", available);
622 #endif
623
624     // now satisfy relative
625     if (available > 0) {
626         for (int i = 0; i < nEffCols; i++) {
627             Length &width = m_layoutStruct[i].effWidth;
628             if (width.isRelative() && width.value() != 0) {
629                 // width=0* gets effMinWidth.
630                 int w = width.value() * tableWidth / totalRelative;
631                 available += m_layoutStruct[i].calcWidth - w;
632                 m_layoutStruct[i].calcWidth = w;
633             }
634         }
635     }
636
637     // now satisfy variable
638     if (available > 0 && numAuto) {
639         available += allocAuto; // this gets redistributed
640         for (int i = 0; i < nEffCols; i++) {
641             Length &width = m_layoutStruct[i].effWidth;
642             if (width.isAuto() && totalAuto != 0 && !m_layoutStruct[i].emptyCellsOnly) {
643                 int w = max(m_layoutStruct[i].calcWidth, static_cast<int>(available * static_cast<float>(m_layoutStruct[i].effMaxWidth) / totalAuto));
644                 available -= w;
645                 totalAuto -= m_layoutStruct[i].effMaxWidth;
646                 m_layoutStruct[i].calcWidth = w;
647             }
648         }
649     }
650 #ifdef DEBUG_LAYOUT
651     qDebug("variable satisfied: available is %d",  available);
652 #endif
653
654     // spread over fixed columns
655     if (available > 0 && numFixed) {
656         // still have some width to spread, distribute to fixed columns
657         for (int i = 0; i < nEffCols; i++) {
658             Length &width = m_layoutStruct[i].effWidth;
659             if (width.isFixed()) {
660                 int w = static_cast<int>(available * static_cast<float>(m_layoutStruct[i].effMaxWidth) / totalFixed);
661                 available -= w;
662                 totalFixed -= m_layoutStruct[i].effMaxWidth;
663                 m_layoutStruct[i].calcWidth += w;
664             }
665         }
666     }
667     
668 #ifdef DEBUG_LAYOUT
669     qDebug("after fixed distribution: available=%d",  available);
670 #endif
671     
672     // spread over percent colums
673     if (available > 0 && m_hasPercent && totalPercent < 100 * percentScaleFactor) {
674         // still have some width to spread, distribute weighted to percent columns
675         for (int i = 0; i < nEffCols; i++) {
676             Length &width = m_layoutStruct[i].effWidth;
677             if (width.isPercent()) {
678                 int w = available * width.rawValue() / totalPercent;
679                 available -= w;
680                 totalPercent -= width.rawValue();
681                 m_layoutStruct[i].calcWidth += w;
682                 if (!available || !totalPercent) break;
683             }
684         }
685     }
686
687 #ifdef DEBUG_LAYOUT
688     qDebug("after percent distribution: available=%d",  available);
689 #endif
690
691     // spread over the rest
692     if (available > 0 && nEffCols > numAutoEmptyCellsOnly) {
693         int total = nEffCols - numAutoEmptyCellsOnly;
694         // still have some width to spread
695         int i = nEffCols;
696         while (i--) {
697             // variable columns with empty cells only don't get any width
698             if (m_layoutStruct[i].width.isAuto() && m_layoutStruct[i].emptyCellsOnly)
699                 continue;
700             int w = available / total;
701             available -= w;
702             total--;
703             m_layoutStruct[i].calcWidth += w;
704         }
705     }
706
707 #ifdef DEBUG_LAYOUT
708     qDebug("after equal distribution: available=%d",  available);
709 #endif
710     // if we have overallocated, reduce every cell according to the difference between desired width and minwidth
711     // this seems to produce to the pixel exaxt results with IE. Wonder is some of this also holds for width distributing.
712     if (available < 0) {
713         // Need to reduce cells with the following prioritization:
714         // (1) Auto
715         // (2) Relative
716         // (3) Fixed
717         // (4) Percent
718         // This is basically the reverse of how we grew the cells.
719         if (available < 0) {
720             int mw = 0;
721             for (int i = nEffCols-1; i >= 0; i--) {
722                 Length &width = m_layoutStruct[i].effWidth;
723                 if (width.isAuto())
724                     mw += m_layoutStruct[i].calcWidth - m_layoutStruct[i].effMinWidth;
725             }
726             
727             for (int i = nEffCols-1; i >= 0 && mw > 0; i--) {
728                 Length &width = m_layoutStruct[i].effWidth;
729                 if (width.isAuto()) {
730                     int minMaxDiff = m_layoutStruct[i].calcWidth-m_layoutStruct[i].effMinWidth;
731                     int reduce = available * minMaxDiff / mw;
732                     m_layoutStruct[i].calcWidth += reduce;
733                     available -= reduce;
734                     mw -= minMaxDiff;
735                     if (available >= 0)
736                         break;
737                 }
738             }
739         }
740
741         if (available < 0) {
742             int mw = 0;
743             for (int i = nEffCols-1; i >= 0; i--) {
744                 Length& width = m_layoutStruct[i].effWidth;
745                 if (width.isRelative())
746                     mw += m_layoutStruct[i].calcWidth - m_layoutStruct[i].effMinWidth;
747             }
748             
749             for (int i = nEffCols-1; i >= 0 && mw > 0; i--) {
750                 Length& width = m_layoutStruct[i].effWidth;
751                 if (width.isRelative()) {
752                     int minMaxDiff = m_layoutStruct[i].calcWidth-m_layoutStruct[i].effMinWidth;
753                     int reduce = available * minMaxDiff / mw;
754                     m_layoutStruct[i].calcWidth += reduce;
755                     available -= reduce;
756                     mw -= minMaxDiff;
757                     if (available >= 0)
758                         break;
759                 }
760             }
761         }
762
763         if (available < 0) {
764             int mw = 0;
765             for (int i = nEffCols-1; i >= 0; i--) {
766                 Length& width = m_layoutStruct[i].effWidth;
767                 if (width.isFixed())
768                     mw += m_layoutStruct[i].calcWidth - m_layoutStruct[i].effMinWidth;
769             }
770             
771             for (int i = nEffCols-1; i >= 0 && mw > 0; i--) {
772                 Length& width = m_layoutStruct[i].effWidth;
773                 if (width.isFixed()) {
774                     int minMaxDiff = m_layoutStruct[i].calcWidth-m_layoutStruct[i].effMinWidth;
775                     int reduce = available * minMaxDiff / mw;
776                     m_layoutStruct[i].calcWidth += reduce;
777                     available -= reduce;
778                     mw -= minMaxDiff;
779                     if (available >= 0)
780                         break;
781                 }
782             }
783         }
784
785         if (available < 0) {
786             int mw = 0;
787             for (int i = nEffCols-1; i >= 0; i--) {
788                 Length& width = m_layoutStruct[i].effWidth;
789                 if (width.isPercent())
790                     mw += m_layoutStruct[i].calcWidth - m_layoutStruct[i].effMinWidth;
791             }
792             
793             for (int i = nEffCols-1; i >= 0 && mw > 0; i--) {
794                 Length& width = m_layoutStruct[i].effWidth;
795                 if (width.isPercent()) {
796                     int minMaxDiff = m_layoutStruct[i].calcWidth-m_layoutStruct[i].effMinWidth;
797                     int reduce = available * minMaxDiff / mw;
798                     m_layoutStruct[i].calcWidth += reduce;
799                     available -= reduce;
800                     mw -= minMaxDiff;
801                     if (available >= 0)
802                         break;
803                 }
804             }
805         }
806     }
807
808     int pos = 0;
809     for (int i = 0; i < nEffCols; i++) {
810 #ifdef DEBUG_LAYOUT
811         qDebug("col %d: %d (width %d)", i, pos, m_layoutStruct[i].calcWidth);
812 #endif
813         m_table->columnPositions()[i] = pos;
814         pos += m_layoutStruct[i].calcWidth + m_table->hBorderSpacing();
815     }
816     m_table->columnPositions()[m_table->columnPositions().size() - 1] = pos;
817 }
818
819
820 void AutoTableLayout::calcPercentages() const
821 {
822     unsigned totalPercent = 0;
823     for (unsigned i = 0; i < m_layoutStruct.size(); i++) {
824         if (m_layoutStruct[i].width.isPercent())
825             totalPercent += m_layoutStruct[i].width.rawValue();
826     }
827     m_totalPercent = totalPercent / percentScaleFactor;
828     m_percentagesDirty = false;
829 }
830
831 #undef DEBUG_LAYOUT
832
833 }