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