WebCore:
[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
153     // ### we need to add col elements as well
154 }
155
156 void AutoTableLayout::fullRecalc()
157 {
158     m_percentagesDirty = true;
159     m_hasPercent = false;
160     m_effWidthDirty = true;
161
162     int nEffCols = m_table->numEffCols();
163     m_layoutStruct.resize(nEffCols);
164     m_layoutStruct.fill(Layout());
165     m_spanCells.fill(0);
166
167     RenderObject *child = m_table->firstChild();
168     Length grpWidth;
169     int cCol = 0;
170     while (child) {
171         if (child->isTableCol()) {
172             RenderTableCol *col = static_cast<RenderTableCol*>(child);
173             int span = col->span();
174             if (col->firstChild()) {
175                 grpWidth = col->style()->width();
176             } else {
177                 Length w = col->style()->width();
178                 if (w.isAuto())
179                     w = grpWidth;
180                 if ((w.isFixed() || w.isPercent()) && w.isZero())
181                     w = Length();
182                 int cEffCol = m_table->colToEffCol(cCol);
183                 if (!w.isAuto() && span == 1 && cEffCol < nEffCols) {
184                     if (m_table->spanOfEffCol(cEffCol) == 1) {
185                         m_layoutStruct[cEffCol].width = w;
186                         if (w.isFixed() && m_layoutStruct[cEffCol].maxWidth < w.value())
187                             m_layoutStruct[cEffCol].maxWidth = w.value();
188                     }
189                 }
190                 cCol += span;
191             }
192         } else {
193             break;
194         }
195
196         RenderObject *next = child->firstChild();
197         if (!next)
198             next = child->nextSibling();
199         if (!next && child->parent()->isTableCol()) {
200             next = child->parent()->nextSibling();
201             grpWidth = Length();
202         }
203         child = next;
204     }
205
206
207     for (int i = 0; i < nEffCols; i++)
208         recalcColumn(i);
209 }
210
211 static bool shouldScaleColumns(RenderTable* table)
212 {
213     // A special case.  If this table is not fixed width and contained inside
214     // a cell, then don't bloat the maxwidth by examining percentage growth.
215     bool scale = true;
216     while (table) {
217         Length tw = table->style()->width();
218         if ((tw.isAuto() || tw.isPercent()) && !table->isPositioned()) {
219             RenderBlock* cb = table->containingBlock();
220             while (cb && !cb->isRenderView() && !cb->isTableCell() &&
221                 cb->style()->width().isAuto() && !cb->isPositioned())
222                 cb = cb->containingBlock();
223
224             table = 0;
225             if (cb && cb->isTableCell() &&
226                 (cb->style()->width().isAuto() || cb->style()->width().isPercent())) {
227                 if (tw.isPercent())
228                     scale = false;
229                 else {
230                     RenderTableCell* cell = static_cast<RenderTableCell*>(cb);
231                     if (cell->colSpan() > 1 || cell->table()->style()->width().isAuto())
232                         scale = false;
233                     else
234                         table = cell->table();
235                 }
236             }
237         }
238         else
239             table = 0;
240     }
241     return scale;
242 }
243
244 void AutoTableLayout::calcPrefWidths(int& minWidth, int& maxWidth)
245 {
246     fullRecalc();
247
248     int spanMaxWidth = calcEffectiveWidth();
249     minWidth = 0;
250     maxWidth = 0;
251     float maxPercent = 0;
252     float maxNonPercent = 0;
253     bool scaleColumns = shouldScaleColumns(m_table);
254
255     // We substitute 0 percent by (epsilon / percentScaleFactor) percent in two places below to avoid division by zero.
256     // FIXME: Handle the 0% cases properly.
257     const int epsilon = 1;
258
259     int remainingPercent = 100 * percentScaleFactor;
260     for (unsigned int i = 0; i < m_layoutStruct.size(); i++) {
261         minWidth += m_layoutStruct[i].effMinWidth;
262         maxWidth += m_layoutStruct[i].effMaxWidth;
263         if (scaleColumns) {
264             if (m_layoutStruct[i].effWidth.isPercent()) {
265                 int percent = min(m_layoutStruct[i].effWidth.rawValue(), remainingPercent);
266                 float pw = static_cast<float>(m_layoutStruct[i].effMaxWidth) * 100 * percentScaleFactor / max(percent, epsilon);
267                 maxPercent = max(pw,  maxPercent);
268                 remainingPercent -= percent;
269             } else
270                 maxNonPercent += m_layoutStruct[i].effMaxWidth;
271         }
272     }
273
274     if (scaleColumns) {
275         maxNonPercent = maxNonPercent * 100 * percentScaleFactor / max(remainingPercent, epsilon);
276         maxWidth = max(maxWidth, static_cast<int>(min(maxNonPercent, INT_MAX / 2.0f)));
277         maxWidth = max(maxWidth, static_cast<int>(min(maxPercent, INT_MAX / 2.0f)));
278     }
279
280     maxWidth = max(maxWidth, spanMaxWidth);
281     
282     int bs = m_table->bordersPaddingAndSpacing();
283     minWidth += bs;
284     maxWidth += bs;
285
286     Length tw = m_table->style()->width();
287     if (tw.isFixed() && tw.value() > 0) {
288         minWidth = max(minWidth, tw.value());
289         maxWidth = minWidth;
290     }
291 }
292
293 /*
294   This method takes care of colspans.
295   effWidth is the same as width for cells without colspans. If we have colspans, they get modified.
296  */
297 int AutoTableLayout::calcEffectiveWidth()
298 {
299     float tMaxWidth = 0;
300
301     unsigned int nEffCols = m_layoutStruct.size();
302     int hspacing = m_table->hBorderSpacing();
303
304     for (unsigned int i = 0; i < nEffCols; i++) {
305         m_layoutStruct[i].effWidth = m_layoutStruct[i].width;
306         m_layoutStruct[i].effMinWidth = m_layoutStruct[i].minWidth;
307         m_layoutStruct[i].effMaxWidth = m_layoutStruct[i].maxWidth;
308     }
309
310     for (unsigned int i = 0; i < m_spanCells.size(); i++) {
311         RenderTableCell *cell = m_spanCells[i];
312         if (!cell)
313             break;
314         int span = cell->colSpan();
315
316         Length w = cell->styleOrColWidth();
317         if (!w.isRelative() && w.isZero())
318             w = Length(); // make it Auto
319
320         int col = m_table->colToEffCol(cell->col());
321         unsigned int lastCol = col;
322         int cMinWidth = cell->minPrefWidth() + hspacing;
323         float cMaxWidth = cell->maxPrefWidth() + hspacing;
324         int totalPercent = 0;
325         int minWidth = 0;
326         float maxWidth = 0;
327         bool allColsArePercent = true;
328         bool allColsAreFixed = true;
329         bool haveAuto = false;
330         bool spanHasEmptyCellsOnly = true;
331         int fixedWidth = 0;
332         while (lastCol < nEffCols && span > 0) {
333             switch (m_layoutStruct[lastCol].width.type()) {
334             case Percent:
335                 totalPercent += m_layoutStruct[lastCol].width.rawValue();
336                 allColsAreFixed = false;
337                 break;
338             case Fixed:
339                 if (m_layoutStruct[lastCol].width.value() > 0) {
340                     fixedWidth += m_layoutStruct[lastCol].width.value();
341                     allColsArePercent = false;
342                     // IE resets effWidth to Auto here, but this breaks the konqueror about page and seems to be some bad
343                     // legacy behaviour anyway. mozilla doesn't do this so I decided we don't neither.
344                     break;
345                 }
346                 // fall through
347             case Auto:
348                 haveAuto = true;
349                 // fall through
350             default:
351                 // If the column is a percentage width, do not let the spanning cell overwrite the
352                 // width value.  This caused a mis-rendering on amazon.com.
353                 // Sample snippet:
354                 // <table border=2 width=100%><
355                 //   <tr><td>1</td><td colspan=2>2-3</tr>
356                 //   <tr><td>1</td><td colspan=2 width=100%>2-3</td></tr>
357                 // </table>
358                 if (!m_layoutStruct[lastCol].effWidth.isPercent()) {
359                     m_layoutStruct[lastCol].effWidth = Length();
360                     allColsArePercent = false;
361                 }
362                 else
363                     totalPercent += m_layoutStruct[lastCol].effWidth.rawValue();
364                 allColsAreFixed = false;
365             }
366             if (!m_layoutStruct[lastCol].emptyCellsOnly)
367                 spanHasEmptyCellsOnly = false;
368             span -= m_table->spanOfEffCol(lastCol);
369             minWidth += m_layoutStruct[lastCol].effMinWidth;
370             maxWidth += m_layoutStruct[lastCol].effMaxWidth;
371             lastCol++;
372             cMinWidth -= hspacing;
373             cMaxWidth -= hspacing;
374         }
375
376         // adjust table max width if needed
377         if (w.isPercent()) {
378             if (totalPercent > w.rawValue() || allColsArePercent) {
379                 // can't satify this condition, treat as variable
380                 w = Length();
381             } else {
382                 float spanMax = max(maxWidth, cMaxWidth);
383                 tMaxWidth = max(tMaxWidth, spanMax * 100 * percentScaleFactor / w.rawValue());
384
385                 // all non percent columns in the span get percent vlaues to sum up correctly.
386                 int percentMissing = w.rawValue() - totalPercent;
387                 float totalWidth = 0;
388                 for (unsigned int pos = col; pos < lastCol; pos++) {
389                     if (!(m_layoutStruct[pos].effWidth.isPercent()))
390                         totalWidth += m_layoutStruct[pos].effMaxWidth;
391                 }
392
393                 for (unsigned int pos = col; pos < lastCol && totalWidth > 0; pos++) {
394                     if (!(m_layoutStruct[pos].effWidth.isPercent())) {
395                         int percent = static_cast<int>(percentMissing * static_cast<float>(m_layoutStruct[pos].effMaxWidth) / totalWidth);
396                         totalWidth -= m_layoutStruct[pos].effMaxWidth;
397                         percentMissing -= percent;
398                         if (percent > 0)
399                             m_layoutStruct[pos].effWidth.setRawValue(Percent, percent);
400                         else
401                             m_layoutStruct[pos].effWidth = Length();
402                     }
403                 }
404
405             }
406         }
407
408         // make sure minWidth and maxWidth of the spanning cell are honoured
409         if (cMinWidth > minWidth) {
410             if (allColsAreFixed) {
411                 for (unsigned int pos = col; fixedWidth > 0 && pos < lastCol; pos++) {
412                     int w = max(m_layoutStruct[pos].effMinWidth, cMinWidth * m_layoutStruct[pos].width.value() / fixedWidth);
413                     fixedWidth -= m_layoutStruct[pos].width.value();
414                     cMinWidth -= w;
415                     m_layoutStruct[pos].effMinWidth = w;
416                 }
417
418             } else {
419                 float maxw = maxWidth;
420                 int minw = minWidth;
421                 
422                 // Give min to variable first, to fixed second, and to others third.
423                 for (unsigned int pos = col; maxw >= 0 && pos < lastCol; pos++) {
424                     if (m_layoutStruct[pos].width.isFixed() && haveAuto && fixedWidth <= cMinWidth) {
425                         int w = max(m_layoutStruct[pos].effMinWidth, m_layoutStruct[pos].width.value());
426                         fixedWidth -= m_layoutStruct[pos].width.value();
427                         minw -= m_layoutStruct[pos].effMinWidth;
428                         maxw -= m_layoutStruct[pos].effMaxWidth;
429                         cMinWidth -= w;
430                         m_layoutStruct[pos].effMinWidth = w;
431                     }
432                 }
433
434                 for (unsigned int pos = col; maxw >= 0 && pos < lastCol && minw < cMinWidth; pos++) {
435                     if (!(m_layoutStruct[pos].width.isFixed() && haveAuto && fixedWidth <= cMinWidth)) {
436                         int w = max(m_layoutStruct[pos].effMinWidth, static_cast<int>(maxw ? cMinWidth * static_cast<float>(m_layoutStruct[pos].effMaxWidth) / maxw : cMinWidth));
437                         w = min(m_layoutStruct[pos].effMinWidth+(cMinWidth-minw), w);
438                                                 
439                         maxw -= m_layoutStruct[pos].effMaxWidth;
440                         minw -= m_layoutStruct[pos].effMinWidth;
441                         cMinWidth -= w;
442                         m_layoutStruct[pos].effMinWidth = w;
443                     }
444                 }
445             }
446         }
447         if (!(w.isPercent())) {
448             if (cMaxWidth > maxWidth) {
449                 for (unsigned int pos = col; maxWidth >= 0 && pos < lastCol; pos++) {
450                     int w = max(m_layoutStruct[pos].effMaxWidth, static_cast<int>(maxWidth ? cMaxWidth * static_cast<float>(m_layoutStruct[pos].effMaxWidth) / maxWidth : cMaxWidth));
451                     maxWidth -= m_layoutStruct[pos].effMaxWidth;
452                     cMaxWidth -= w;
453                     m_layoutStruct[pos].effMaxWidth = w;
454                 }
455             }
456         } else {
457             for (unsigned int pos = col; pos < lastCol; pos++)
458                 m_layoutStruct[pos].maxWidth = max(m_layoutStruct[pos].maxWidth, m_layoutStruct[pos].minWidth);
459         }
460         // treat span ranges consisting of empty cells only as if they had content
461         if (spanHasEmptyCellsOnly)
462             for (unsigned int pos = col; pos < lastCol; pos++)
463                 m_layoutStruct[pos].emptyCellsOnly = false;
464     }
465     m_effWidthDirty = false;
466
467     return static_cast<int>(min(tMaxWidth, INT_MAX / 2.0f));
468 }
469
470 /* gets all cells that originate in a column and have a cellspan > 1
471    Sorts them by increasing cellspan
472 */
473 void AutoTableLayout::insertSpanCell(RenderTableCell *cell)
474 {
475     if (!cell || cell->colSpan() == 1)
476         return;
477
478     int size = m_spanCells.size();
479     if (!size || m_spanCells[size-1] != 0) {
480         m_spanCells.resize(size + 10);
481         for (int i = 0; i < 10; i++)
482             m_spanCells[size+i] = 0;
483         size += 10;
484     }
485
486     // add them in sort. This is a slow algorithm, and a binary search or a fast sorting after collection would be better
487     unsigned int pos = 0;
488     int span = cell->colSpan();
489     while (pos < m_spanCells.size() && m_spanCells[pos] && span > m_spanCells[pos]->colSpan())
490         pos++;
491     memmove(m_spanCells.data()+pos+1, m_spanCells.data()+pos, (size-pos-1)*sizeof(RenderTableCell *));
492     m_spanCells[pos] = cell;
493 }
494
495
496 void AutoTableLayout::layout()
497 {
498     // table layout based on the values collected in the layout structure.
499     int tableWidth = m_table->width() - m_table->bordersPaddingAndSpacing();
500     int available = tableWidth;
501     int nEffCols = m_table->numEffCols();
502
503     if (nEffCols != (int)m_layoutStruct.size()) {
504         fullRecalc();
505         nEffCols = m_table->numEffCols();
506     }
507
508     if (m_effWidthDirty)
509         calcEffectiveWidth();
510
511     bool havePercent = false;
512     bool haveRelative = false;
513     int totalRelative = 0;
514     int numAuto = 0;
515     int numFixed = 0;
516     float totalAuto = 0;
517     float totalFixed = 0;
518     int totalPercent = 0;
519     int allocAuto = 0;
520     int numAutoEmptyCellsOnly = 0;
521
522     // fill up every cell with its minWidth
523     for (int i = 0; i < nEffCols; i++) {
524         int w = m_layoutStruct[i].effMinWidth;
525         m_layoutStruct[i].calcWidth = w;
526         available -= w;
527         Length& width = m_layoutStruct[i].effWidth;
528         switch (width.type()) {
529         case Percent:
530             havePercent = true;
531             totalPercent += width.rawValue();
532             break;
533         case Relative:
534             haveRelative = true;
535             totalRelative += width.value();
536             break;
537         case Fixed:
538             numFixed++;
539             totalFixed += m_layoutStruct[i].effMaxWidth;
540             // fall through
541             break;
542         case Auto:
543         case Static:
544             if (m_layoutStruct[i].emptyCellsOnly) 
545                 numAutoEmptyCellsOnly++;            
546             else {
547                 numAuto++;
548                 totalAuto += m_layoutStruct[i].effMaxWidth;
549                 allocAuto += w;
550             }
551             break;
552         default:
553             break;
554         }
555     }
556
557     // allocate width to percent cols
558     if (available > 0 && havePercent) {
559         for (int i = 0; i < nEffCols; i++) {
560             Length &width = m_layoutStruct[i].effWidth;
561             if (width.isPercent()) {
562                 int w = max(int(m_layoutStruct[i].effMinWidth), width.calcMinValue(tableWidth));
563                 available += m_layoutStruct[i].calcWidth - w;
564                 m_layoutStruct[i].calcWidth = w;
565             }
566         }
567         if (totalPercent > 100 * percentScaleFactor) {
568             // remove overallocated space from the last columns
569             int excess = tableWidth*(totalPercent - 100 * percentScaleFactor) / (100 * percentScaleFactor);
570             for (int i = nEffCols-1; i >= 0; i--) {
571                 if (m_layoutStruct[i].effWidth.isPercent()) {
572                     int w = m_layoutStruct[i].calcWidth;
573                     int reduction = min(w,  excess);
574                     // the lines below might look inconsistent, but that's the way it's handled in mozilla
575                     excess -= reduction;
576                     int newWidth = max(int (m_layoutStruct[i].effMinWidth), w - reduction);
577                     available += w - newWidth;
578                     m_layoutStruct[i].calcWidth = newWidth;
579                 }
580             }
581         }
582     }
583     
584     // then allocate width to fixed cols
585     if (available > 0) {
586         for (int i = 0; i < nEffCols; ++i) {
587             Length &width = m_layoutStruct[i].effWidth;
588             if (width.isFixed() && width.value() > m_layoutStruct[i].calcWidth) {
589                 available += m_layoutStruct[i].calcWidth - width.value();
590                 m_layoutStruct[i].calcWidth = width.value();
591             }
592         }
593     }
594
595     // now satisfy relative
596     if (available > 0) {
597         for (int i = 0; i < nEffCols; i++) {
598             Length &width = m_layoutStruct[i].effWidth;
599             if (width.isRelative() && width.value() != 0) {
600                 // width=0* gets effMinWidth.
601                 int w = width.value() * tableWidth / totalRelative;
602                 available += m_layoutStruct[i].calcWidth - w;
603                 m_layoutStruct[i].calcWidth = w;
604             }
605         }
606     }
607
608     // now satisfy variable
609     if (available > 0 && numAuto) {
610         available += allocAuto; // this gets redistributed
611         for (int i = 0; i < nEffCols; i++) {
612             Length &width = m_layoutStruct[i].effWidth;
613             if (width.isAuto() && totalAuto != 0 && !m_layoutStruct[i].emptyCellsOnly) {
614                 int w = max(m_layoutStruct[i].calcWidth, static_cast<int>(available * static_cast<float>(m_layoutStruct[i].effMaxWidth) / totalAuto));
615                 available -= w;
616                 totalAuto -= m_layoutStruct[i].effMaxWidth;
617                 m_layoutStruct[i].calcWidth = w;
618             }
619         }
620     }
621
622     // spread over fixed columns
623     if (available > 0 && numFixed) {
624         // still have some width to spread, distribute to fixed columns
625         for (int i = 0; i < nEffCols; i++) {
626             Length &width = m_layoutStruct[i].effWidth;
627             if (width.isFixed()) {
628                 int w = static_cast<int>(available * static_cast<float>(m_layoutStruct[i].effMaxWidth) / totalFixed);
629                 available -= w;
630                 totalFixed -= m_layoutStruct[i].effMaxWidth;
631                 m_layoutStruct[i].calcWidth += w;
632             }
633         }
634     }
635
636     // spread over percent colums
637     if (available > 0 && m_hasPercent && totalPercent < 100 * percentScaleFactor) {
638         // still have some width to spread, distribute weighted to percent columns
639         for (int i = 0; i < nEffCols; i++) {
640             Length &width = m_layoutStruct[i].effWidth;
641             if (width.isPercent()) {
642                 int w = available * width.rawValue() / totalPercent;
643                 available -= w;
644                 totalPercent -= width.rawValue();
645                 m_layoutStruct[i].calcWidth += w;
646                 if (!available || !totalPercent) break;
647             }
648         }
649     }
650
651     // spread over the rest
652     if (available > 0 && nEffCols > numAutoEmptyCellsOnly) {
653         int total = nEffCols - numAutoEmptyCellsOnly;
654         // still have some width to spread
655         int i = nEffCols;
656         while (i--) {
657             // variable columns with empty cells only don't get any width
658             if (m_layoutStruct[i].effWidth.isAuto() && m_layoutStruct[i].emptyCellsOnly)
659                 continue;
660             int w = available / total;
661             available -= w;
662             total--;
663             m_layoutStruct[i].calcWidth += w;
664         }
665     }
666
667     // if we have overallocated, reduce every cell according to the difference between desired width and minwidth
668     // this seems to produce to the pixel exaxt results with IE. Wonder is some of this also holds for width distributing.
669     if (available < 0) {
670         // Need to reduce cells with the following prioritization:
671         // (1) Auto
672         // (2) Relative
673         // (3) Fixed
674         // (4) Percent
675         // This is basically the reverse of how we grew the cells.
676         if (available < 0) {
677             int mw = 0;
678             for (int i = nEffCols-1; i >= 0; i--) {
679                 Length &width = m_layoutStruct[i].effWidth;
680                 if (width.isAuto())
681                     mw += m_layoutStruct[i].calcWidth - m_layoutStruct[i].effMinWidth;
682             }
683             
684             for (int i = nEffCols-1; i >= 0 && mw > 0; i--) {
685                 Length &width = m_layoutStruct[i].effWidth;
686                 if (width.isAuto()) {
687                     int minMaxDiff = m_layoutStruct[i].calcWidth-m_layoutStruct[i].effMinWidth;
688                     int reduce = available * minMaxDiff / mw;
689                     m_layoutStruct[i].calcWidth += reduce;
690                     available -= reduce;
691                     mw -= minMaxDiff;
692                     if (available >= 0)
693                         break;
694                 }
695             }
696         }
697
698         if (available < 0) {
699             int mw = 0;
700             for (int i = nEffCols-1; i >= 0; i--) {
701                 Length& width = m_layoutStruct[i].effWidth;
702                 if (width.isRelative())
703                     mw += m_layoutStruct[i].calcWidth - m_layoutStruct[i].effMinWidth;
704             }
705             
706             for (int i = nEffCols-1; i >= 0 && mw > 0; i--) {
707                 Length& width = m_layoutStruct[i].effWidth;
708                 if (width.isRelative()) {
709                     int minMaxDiff = m_layoutStruct[i].calcWidth-m_layoutStruct[i].effMinWidth;
710                     int reduce = available * minMaxDiff / mw;
711                     m_layoutStruct[i].calcWidth += reduce;
712                     available -= reduce;
713                     mw -= minMaxDiff;
714                     if (available >= 0)
715                         break;
716                 }
717             }
718         }
719
720         if (available < 0) {
721             int mw = 0;
722             for (int i = nEffCols-1; i >= 0; i--) {
723                 Length& width = m_layoutStruct[i].effWidth;
724                 if (width.isFixed())
725                     mw += m_layoutStruct[i].calcWidth - m_layoutStruct[i].effMinWidth;
726             }
727             
728             for (int i = nEffCols-1; i >= 0 && mw > 0; i--) {
729                 Length& width = m_layoutStruct[i].effWidth;
730                 if (width.isFixed()) {
731                     int minMaxDiff = m_layoutStruct[i].calcWidth-m_layoutStruct[i].effMinWidth;
732                     int reduce = available * minMaxDiff / mw;
733                     m_layoutStruct[i].calcWidth += reduce;
734                     available -= reduce;
735                     mw -= minMaxDiff;
736                     if (available >= 0)
737                         break;
738                 }
739             }
740         }
741
742         if (available < 0) {
743             int mw = 0;
744             for (int i = nEffCols-1; i >= 0; i--) {
745                 Length& width = m_layoutStruct[i].effWidth;
746                 if (width.isPercent())
747                     mw += m_layoutStruct[i].calcWidth - m_layoutStruct[i].effMinWidth;
748             }
749             
750             for (int i = nEffCols-1; i >= 0 && mw > 0; i--) {
751                 Length& width = m_layoutStruct[i].effWidth;
752                 if (width.isPercent()) {
753                     int minMaxDiff = m_layoutStruct[i].calcWidth-m_layoutStruct[i].effMinWidth;
754                     int reduce = available * minMaxDiff / mw;
755                     m_layoutStruct[i].calcWidth += reduce;
756                     available -= reduce;
757                     mw -= minMaxDiff;
758                     if (available >= 0)
759                         break;
760                 }
761             }
762         }
763     }
764
765     int pos = 0;
766     for (int i = 0; i < nEffCols; i++) {
767         m_table->columnPositions()[i] = pos;
768         pos += m_layoutStruct[i].calcWidth + m_table->hBorderSpacing();
769     }
770     m_table->columnPositions()[m_table->columnPositions().size() - 1] = pos;
771 }
772
773
774 void AutoTableLayout::calcPercentages() const
775 {
776     unsigned totalPercent = 0;
777     for (unsigned i = 0; i < m_layoutStruct.size(); i++) {
778         if (m_layoutStruct[i].width.isPercent())
779             totalPercent += m_layoutStruct[i].width.rawValue();
780     }
781     m_totalPercent = totalPercent / percentScaleFactor;
782     m_percentagesDirty = false;
783 }
784
785 #undef DEBUG_LAYOUT
786
787 }