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