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