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 }