Bug 40775 – Table Cell Layering

• Status: RESOLVED
• Resolution: FIXED
• Component: Layout and Rendering

[Fady Samuel]

Layering of table cells is not implemented correctly in WebKit which means there will occasionally be rendering issues when cells overlap in tables. Currently the RenderTableSection object does not keep track of more than one cell for any given grid slot in a table. Through the use of colspan and rowspan attribute, multiple cells may overlap in a single cell slot. 

<TABLE border="1">
<TR><TD>1 <TD>2 <TD>3
<TR><TD>4 <TD rowspan="2">5 <TD>6
<TR><TD colspan="2">7 <TD>9
</TABLE>

The issue of layering is most evident when you assign background colors to overlapping cells. In the patch, I've included two tests that demonstrate the inconsistent/incorrect behavior of Webkit relative to other browsers. 

Technically (according to the spec, http://www.w3.org/TR/html401/struct/tables.html) cell overlap is an 'error' but it is supported on all the major browsers and the behavior is consistent on all the major browsers (with the exception of a few subtle inconsistencies in webkit). WebKit starts messing up painting if dirty paint rects are small. 

The patch here fixes the issue by keeping track of all cells that lie on each grid slot of the table. Cells are assigned a layer number on layout (in RenderTableSection::addCell). A cell that does not overlap with any other cells is assigned a layer number 0. Otherwise, a cell's layer is defined to be 1 + the greatest overlapped cell layer.

On paint, the RenderTableSection object iterates over all the cells that lie on the dirty grid slots. It paints all layer 0 cells directly as they do not overlap with any other cells. It then takes all non-layer 0 cells in the dirty rect, sorts them by layer number, and then paints the layers from 1 onward. In the simplest (and most common) case where there is no overlap, the performance impact on table rendering should be negligible.

Subtle hit testing bugs also exist when doing cell layering as well. These are not fixed in this first patch but will be fixed in a subsequent patch

This is the first of several patches that will be coming to tweak table layout and rendering for performance and compatibility (to better match the behavior of other browsers in edge cases). 

I've split up my work into several patches to smooth out the review process. In the next few patches, I will be doing the following :

1. Issue hit testing on a grid slot in the order of cells layered on that slot (i.e. the topmost cells receives the hit test first and then the one underneath it and so on).
2. Use binary search on both hit testing and painting of dirty rects to identify which cells need to be repainted (current patch uses a linear scan). This should provide a nice perf boost when updating small parts of a very large table. Use counting sort (instead of qsort) when painting dirty rects.
3. Update table layout to better match IE, firefox, and opera in edge cases (e.g. how other browsers treat empty cells and rows that have column counts that don't match). 
4. Possibly opacity/translucency of overlapping cell backgrounds? (This might allow for neat effects although, again, outside the spec).

[Fady Samuel]

Created attachment 59003 [details]
Patch attached that fixes table cell layering

[Fady Samuel]

Created attachment 59036 [details]
Added binaries and updated changelog

[Fady Samuel]

Created attachment 59037 [details]
Table Cell Layering Patch

Fixed flags

[Fady Samuel]

Let me be a bit clearer on what the expected behavior is:

Cells are layered according to DOM order. What that means is if two cells occupy a given slot on the table grid, the cell that was defined later lies above the cell that was defined earlier. This behavior seems to be consistent across IE, Firefox, and Opera. 

On repaint, it was possible for WebKit to draw an earlier cell above a later cell prior to this patch. The added tests check for this case.

[Fady Samuel]

On line 995 of RenderTableSection::paintCell, it says:

RenderObject* col = table()->colElement(cell->col());

This is a bug that I didn't catch before posting the patch. 

That should've been 

RenderObject* col = table()->colElement(c);

Thanks.

I will fix this in the next patch after I get some feedback.

[James Robinson]

I can't tell whether the pixel results are passing or failing from looking at just the test and associated test.  Please make it clearer from the test whether it is passing or not (preferably without having to read any text).  A typical pattern with repaint tests is to arrange the test so that a passing result shows only green and repaint bugs are caught by showing some regions as red.  Also, I would really like to see many more simple tests in addition to more complex tests.  When something breaks down the road it should be as easy as possible to tell exactly where the problem is by looking at which tests break.

The ChangeLog entries have garbage in them.

I see you've made some changes just to fix style issues.  The logic changes will be easier to review if those style-only changes are split into their own patch.

[Fady Samuel]

(In reply to comment #6)
> I can't tell whether the pixel results are passing or failing from looking at just the test and associated test.  Please make it clearer from the test whether it is passing or not (preferably without having to read any text).  A typical pattern with repaint tests is to arrange the test so that a passing result shows only green and repaint bugs are caught by showing some regions as red.  Also, I would really like to see many more simple tests in addition to more complex tests.  When something breaks down the road it should be as easy as possible to tell exactly where the problem is by looking at which tests break.
> 
> The ChangeLog entries have garbage in them.
> 
> I see you've made some changes just to fix style issues.  The logic changes will be easier to review if those style-only changes are split into their own patch.

James, I'll try to simplify the tests. As for other tests, should they all be tests that show WebKit failing right now, or can I add some simple tests that output correctly?

I will fix the changelog and get rid of style fixes in this patch.

[Dave Hyatt]

Comment on attachment 59037 [details]
Table Cell Layering Patch

Some initial feedback:

(1) I don't think CellNode is necessary. You can just make CellStruct have a Vector<RenderTableCell, 1>.  I'd give CellStruct a cell() accessor to get the "primary" RenderTableCell for the code that is using that.
(2) m_layer is not a good name for a variable added to RenderTableCell, since it shadows the m_layer in one of RenderTableCell's base classes.  Let's not overload "layer" if we can help it, since that has a pretty clear meaning in WebCore rendering code.  Something more like m_overlapLevel would be better.
(3) I'm not convinced that the overlap level member variable is needed.  Adding 4 bytes to all RenderTableCells for this seems problematic (same with the extra boolean that was added).  Can't paint order be inferred from ordering in the CellStruct? Maybe the answer is no, but think about it.  I'd consider using hashes in the .cpp file though rather than bloating RenderTableCell for a rare case (e.g., like we do with column members in RenderBlock).
(4) I don't like the name renderCellAtTop.  Someone reading that is going to think "top" means "top of the table."  If we're talking about the notion of a principal/primary cell that occupies that slot, then maybe primaryCell is good enough.

[Fady Samuel]

(In reply to comment #8)
> (From update of attachment 59037 [details])
> Some initial feedback:
> 
> (3) I'm not convinced that the overlap level member variable is needed.  Adding 4 bytes to all RenderTableCells for this seems problematic (same with the extra boolean that was added).  Can't paint order be inferred from ordering in the CellStruct? Maybe the answer is no, but think about it.  I'd consider using hashes in the .cpp file though rather than bloating RenderTableCell for a rare case (e.g., like we do with column members in RenderBlock).

Everything else you said was pretty straightforward. Inferring paint order will definitely be a bit tricky but first instinct is it's possible. I'll spend a bit of time thinking of potential corner cases where this might not be possible. If it is possible, it will also be a bit tricky to do this efficiently. It's an interesting thought, and I agree, it would be nice to avoid those extra 4 bytes.

[Fady Samuel]

Created attachment 60566 [details]
Table Cell Layering Patch -- Updated

Includes dhyatt's suggestions, but not jamesr suggestion about the red/green color scheme for the new layout tests. I'm generating those now but I'd like to get feedback in the meantime if possible.

[WebKit Review Bot]

Attachment 60566 [details] did not pass style-queue:

Failed to run "['WebKitTools/Scripts/check-webkit-style', '--no-squash']" exit_code: 1
WebCore/rendering/RenderTableSection.cpp:1092:  One line control clauses should not use braces.  [whitespace/braces] [4]
WebCore/rendering/RenderTableSection.h:70:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
WebCore/rendering/RenderTableSection.h:71:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
WebCore/rendering/RenderTableSection.h:73:  One line control clauses should not use braces.  [whitespace/braces] [4]
WebCore/rendering/RenderTableSection.h:77:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
WebCore/rendering/RenderTableSection.h:78:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
WebCore/rendering/RenderTableSection.h:80:  One line control clauses should not use braces.  [whitespace/braces] [4]
WebCore/rendering/RenderTableSection.h:84:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 8 in 16 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Fady Samuel]

Created attachment 60567 [details]
Table Cell Layering Patch -- Updated

Fixed style issue.

[Fady Samuel]

Created attachment 60643 [details]
Table Cell Layering Patch -- Updated According to Suggestions by dhyatt and jamesr

[WebKit Review Bot]

Attachment 60643 [details] did not pass style-queue:

Failed to run "['WebKitTools/Scripts/check-webkit-style', '--no-squash']" exit_code: 1
WebCore/rendering/RenderTableSection.cpp:1091:  One line control clauses should not use braces.  [whitespace/braces] [4]
WebCore/rendering/RenderTableSection.h:70:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
WebCore/rendering/RenderTableSection.h:71:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
WebCore/rendering/RenderTableSection.h:73:  One line control clauses should not use braces.  [whitespace/braces] [4]
WebCore/rendering/RenderTableSection.h:77:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
WebCore/rendering/RenderTableSection.h:78:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
WebCore/rendering/RenderTableSection.h:80:  One line control clauses should not use braces.  [whitespace/braces] [4]
WebCore/rendering/RenderTableSection.h:84:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 8 in 16 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Fady Samuel]

Created attachment 60645 [details]
Table Cell Layering Patch - Updated with style fix

[WebKit Review Bot]

Attachment 60645 [details] did not pass style-queue:

Failed to run "['WebKitTools/Scripts/check-webkit-style', '--no-squash']" exit_code: 1
WebCore/rendering/RenderTableSection.h:70:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
WebCore/rendering/RenderTableSection.h:71:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
WebCore/rendering/RenderTableSection.h:73:  One line control clauses should not use braces.  [whitespace/braces] [4]
WebCore/rendering/RenderTableSection.h:77:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
WebCore/rendering/RenderTableSection.h:78:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
WebCore/rendering/RenderTableSection.h:80:  One line control clauses should not use braces.  [whitespace/braces] [4]
WebCore/rendering/RenderTableSection.h:84:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 7 in 16 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Fady Samuel]

Created attachment 60647 [details]
Table Cell Layering Patch

[James Robinson]

I think this looks pretty good.  You shouldn't use qsort() to sort the Vector contents, instead just use the sorting routines from stl's algorithms section.  See RenderLayer::updateZOrderLists() for an example of how this is done.

[Dave Hyatt]

Comment on attachment 60647 [details]
Table Cell Layering Patch

We tend to avoid "get" in method names in the render tree, so instead of getPrimaryCellAt, just make the method primaryCellAt. This is more consistent with primaryCell() anyway.

Please revert your changes to RenderTableCell.cpp.  It looks like you just messed with whitespace there without making any real changes.

RenderTableSection::comparelayers... function names are always intercaps, so that should be compareLayers.  I still think you need to avoid using the term "layer" though, since that's very confusing.  Just rename to compareCellPositions.

I think the implementation of primaryCell is a little weird duplicated.  Maybe you could at least compact it to:

return hasCells() ? cells[cells.size() - 1] : 0;

That's one line instead of three and doesn't look so bad used twice. :)

The RenderTableSection member, Vector<RenderTableCell*> m_Cells, does not appear to be used unless I'm missing something.

[Fady Samuel]

Created attachment 61109 [details]
Table Cell Layering Patch

Updated with even more suggestions from jamesr and dhyatt! Thanks! :D

[Fady Samuel]

Created attachment 61427 [details]
Table Cell Layering Patch

Updated according to IRC chat with dhyatt.

[Dave Hyatt]

Comment on attachment 61427 [details]
Table Cell Layering Patch

r=me

[WebKit Commit Bot]

Comment on attachment 61427 [details]
Table Cell Layering Patch

Rejecting patch 61427 from commit-queue.

Unexpected failure when processing patch!  Please file a bug against webkit-patch.
Failed to run "['./WebKitTools/Scripts/webkit-patch', '--status-host=queues.webkit.org', 'land-attachment', '--force-clean', '--build', '--non-interactive', '--ignore-builders', '--build-style=both', '--quiet', 61427, '--test', '--parent-command=commit-queue', '--no-update']" exit_code: 1
Logging in as [e-mail]...
Fetching: https://bugs.webkit.org/attachment.cgi?id=61427&action=edit
Fetching: https://bugs.webkit.org/show_bug.cgi?id=40775&ctype=xml
Processing 1 patch from 1 bug.
Cleaning working directory
Processing patch 61427 from bug 40775.
ERROR: /Users/eseidel/Projects/CommitQueue/LayoutTests/ChangeLog neither lists a valid reviewer nor contains the string "Unreviewed" or "Rubber stamp" (case insensitive).

[Fady Samuel]

Created attachment 62228 [details]
Table Cell Layering Patch

Fixed Malformed Changelog.

[Dave Hyatt]

Comment on attachment 62228 [details]
Table Cell Layering Patch

r=me

[WebKit Commit Bot]

Comment on attachment 62228 [details]
Table Cell Layering Patch

Rejecting patch 62228 from commit-queue.

Failed to run "['WebKitTools/Scripts/run-webkit-tests', '--no-launch-safari', '--exit-after-n-failures=1', '--ignore-tests', 'compositing', '--quiet']" exit_code: 1
Running build-dumprendertree
Compiling Java tests
make: Nothing to be done for `default'.
Running tests from /Users/eseidel/Projects/CommitQueue/LayoutTests
Testing 20696 test cases.
fast/table/fixed-granular-cols.html -> failed

Exiting early after 1 failures. 14990 tests run.
259.62s total testing time

14989 test cases (99%) succeeded
1 test case (<1%) had incorrect layout
1 test case (<1%) had stderr output

Full output: http://queues.webkit.org/results/3585355

[Eric Seidel (no email)]

Comment on attachment 61427 [details]
Table Cell Layering Patch

Cleared David Hyatt's review+ from obsolete attachment 61427 [details] so that this bug does not appear in http://webkit.org/pending-commit.

[Fady Samuel]

Created attachment 62427 [details]
Table Cell Layering Patch

Fixed a bug that crept into the later iterations of this patch (was doing a resize of the row on SplitColumn, instead of inserting a new CellStruct at the appropriate position).

Fixed a small layout bug that crept in.

More baselines for more platforms. 

Passing all layout tests as of July 23, 2010.

[Dave Hyatt]

Comment on attachment 62427 [details]
Table Cell Layering Patch

r=me

[WebKit Commit Bot]

Comment on attachment 62427 [details]
Table Cell Layering Patch

Rejecting patch 62427 from commit-queue.

Failed to run "['WebKitTools/Scripts/run-webkit-tests', '--no-launch-safari', '--exit-after-n-failures=1', '--ignore-tests', 'compositing', '--quiet']" exit_code: 1
Running build-dumprendertree
Compiling Java tests
make: Nothing to be done for `default'.
Running tests from /Users/eseidel/Projects/CommitQueue/LayoutTests
Testing 20714 test cases.
animations/play-state.html -> failed

Exiting early after 1 failures. 123 tests run.
13.22s total testing time

122 test cases (99%) succeeded
1 test case (<1%) had incorrect layout

Full output: http://queues.webkit.org/results/3594362

[James Robinson]

Comment on attachment 62427 [details]
Table Cell Layering Patch

Clearing flags on attachment: 62427

Committed r63994: <http://trac.webkit.org/changeset/63994>

[James Robinson]

All reviewed patches have been landed.  Closing bug.

[James Robinson]

The commit queue bounced this due to a flaky test, so I landed it manually.

[Mark Rowe (bdash)]

This appears to have broken the rendering of Bank of America’s website.  See bug 42993.