Row spanning cell content is flowing out of the cell border if this row spanning cell comes under t…

Row spanning cell content is flowing out of the cell border if this row spanning cell comes under the boundries of other row spanning cell.

Inner row spanning cell height was not considered in table layout So Height
of the row spanning cell was not proper. Overlapping row spanning cells was
not handles.

Inner row spanning cell should handle first in the table. So we are rearranging
the list of row spanning cells so that inner row spanning cell will handled first
for spredding remaining logical height in the rows than outer row spanning cell.

List of row spanning cells is already sorted in ascending order by their
rowIndexs.
We are rearranging the row spanning cell's list and pushing inner cell before
its outer cell. Also if 2 or more row spanning cells are same but their heights
are different then pushing height-est row spanning cell before the lower height row
spanning cells.
After rearranging them, we apply the process of spreading remaining logical
height into rows.

R=jchaffraix@chromium.org
BUG=252120
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=155337

[Julien - ping for review, 2013-07-29 16:52:55]

https://codereview.chromium.org/19635004/diff/29001/Source/core/rendering/Ren...
File Source/core/rendering/RenderTableSection.cpp (right):

https://codereview.chromium.org/19635004/diff/29001/Source/core/rendering/Ren...
Source/core/rendering/RenderTableSection.cpp:372: // Arrange row spanning cell
in the oder in which we need to process first.
This comment should be embedded into the method name:
sortRowSpanCellsInProcessingOrder (or something similar, we could probably find
a better naming based on how we sort but not sure if it would make it more
readable).

Outlining how you sort (remember the 'why' comments) would be a very good
comment to add at the top of the function.

https://codereview.chromium.org/19635004/diff/29001/Source/core/rendering/Ren...
Source/core/rendering/RenderTableSection.cpp:377: // 'rowSpanCelss' list is
already sorted based on the cells rowIndex in ascending order
typo: rowSpanCelss

https://codereview.chromium.org/19635004/diff/29001/Source/core/rendering/Ren...
Source/core/rendering/RenderTableSection.cpp:382: for (unsigned j = totalCells -
1; j > i; j--) {
As mentioned on IRC, reusing std::sort with a custom sorting function is almost
always a better solution to rolling your own sorting function. Especially here,
the implementation would yield to O(n^2) worst case complexity which would be
easily alleviate by std::sort.

[a.suchit, 2013-07-30 08:42:20]

https://codereview.chromium.org/19635004/diff/29001/Source/core/rendering/Ren...
File Source/core/rendering/RenderTableSection.cpp (right):

https://codereview.chromium.org/19635004/diff/29001/Source/core/rendering/Ren...
Source/core/rendering/RenderTableSection.cpp:372: // Arrange row spanning cell
in the oder in which we need to process first.
On 2013/07/29 16:52:55, Julien Chaffraix wrote:
> This comment should be embedded into the method name:
> sortRowSpanCellsInProcessingOrder (or something similar, we could probably
find
> a better naming based on how we sort but not sure if it would make it more
> readable).
> 
> Outlining how you sort (remember the 'why' comments) would be a very good
> comment to add at the top of the function.

Done.

https://codereview.chromium.org/19635004/diff/29001/Source/core/rendering/Ren...
Source/core/rendering/RenderTableSection.cpp:377: // 'rowSpanCelss' list is
already sorted based on the cells rowIndex in ascending order
On 2013/07/29 16:52:55, Julien Chaffraix wrote:
> typo: rowSpanCelss

Done.

https://codereview.chromium.org/19635004/diff/29001/Source/core/rendering/Ren...
Source/core/rendering/RenderTableSection.cpp:382: for (unsigned j = totalCells -
1; j > i; j--) {
On 2013/07/29 16:52:55, Julien Chaffraix wrote:
> As mentioned on IRC, reusing std::sort with a custom sorting function is
almost
> always a better solution to rolling your own sorting function. Especially
here,
> the implementation would yield to O(n^2) worst case complexity which would be
> easily alleviate by std::sort.

Done.

[Julien - ping for review, 2013-07-30 23:43:07]

https://codereview.chromium.org/19635004/diff/36001/Source/core/rendering/Ren...
File Source/core/rendering/RenderTableSection.cpp (right):

https://codereview.chromium.org/19635004/diff/36001/Source/core/rendering/Ren...
Source/core/rendering/RenderTableSection.cpp:375: // specified by user. So
sorting these types of cells in ascending order based on their size.
The comment is OK but I think we could make this comment way clearer:

// To avoid unneeded extra height distributions, we apply the following sorting
algorithm:
// 1. We sort the cells by increasing starting row, then increasing last row (ie
the top-most, longest cells first)
// 2. For cells spanning the same rows, we sort by intrinsic size.

https://codereview.chromium.org/19635004/diff/36001/Source/core/rendering/Ren...
Source/core/rendering/RenderTableSection.cpp:376: static bool
compareRowSpanCellsInHeightDistributionOrder(RenderTableCell* cell2,
RenderTableCell* cell1)
const RenderTableCell*, const RenderTableCell*

https://codereview.chromium.org/19635004/diff/36001/Source/core/rendering/Ren...
Source/core/rendering/RenderTableSection.cpp:379: ASSERT(cell2);
These ASSERTs are unneeded for 2 reasons:
- unless the std is wrong this won't happen (and it should be tested enough that
it's unlikely to happen)
- you would crash below anyway.

https://codereview.chromium.org/19635004/diff/36001/Source/core/rendering/Ren...
Source/core/rendering/RenderTableSection.cpp:389: return (cellRowIndex2 >=
cellRowIndex1 && (cellRowIndex2 + cellRowSpan2) <= (cellRowIndex1 +
cellRowSpan1));
The comparator function passed to std::sort should be a *strict* comparator.
This means that this condition should be changed to be strict or else badness
will happen.

https://codereview.chromium.org/19635004/diff/36001/Source/core/rendering/Ren...
Source/core/rendering/RenderTableSection.cpp:414: if (rowIndex == lastRowIndex
&& rowSpan == lastRowSpan)
Nit: Do we need to compute |originalBeforePosition| above even if we don't use
it by bailing out here?

Also it would be nice to add a comment why it's correct to bail out here.

[a.suchit, 2013-07-31 10:26:13]

https://codereview.chromium.org/19635004/diff/36001/Source/core/rendering/Ren...
File Source/core/rendering/RenderTableSection.cpp (right):

https://codereview.chromium.org/19635004/diff/36001/Source/core/rendering/Ren...
Source/core/rendering/RenderTableSection.cpp:375: // specified by user. So
sorting these types of cells in ascending order based on their size.
On 2013/07/30 23:43:07, Julien Chaffraix wrote:
> The comment is OK but I think we could make this comment way clearer:
> 
> // To avoid unneeded extra height distributions, we apply the following
sorting
> algorithm:
> // 1. We sort the cells by increasing starting row, then increasing last row
(ie
> the top-most, longest cells first)
> // 2. For cells spanning the same rows, we sort by intrinsic size.

Done.

https://codereview.chromium.org/19635004/diff/36001/Source/core/rendering/Ren...
Source/core/rendering/RenderTableSection.cpp:376: static bool
compareRowSpanCellsInHeightDistributionOrder(RenderTableCell* cell2,
RenderTableCell* cell1)
On 2013/07/30 23:43:07, Julien Chaffraix wrote:
> const RenderTableCell*, const RenderTableCell*

Done.

https://codereview.chromium.org/19635004/diff/36001/Source/core/rendering/Ren...
Source/core/rendering/RenderTableSection.cpp:377: {
+----------+----------+----------+
|          |    B     |    C     |
|          +----------+----------+----------+
|          |          |          |     F    |
|          |          |    E     |----------+
|          |          |          |     G    |
|          |    D     |          +----------+
|    A     |          +----------+ E extra height
|          |          |    H     |
|          |          +----------+ D extra height
|          +----------+----------+----------+
|          |    I     |    J     |     K    |
|          +----------+----------+----------+
+----------+----------+----------+ A extra height
|    L     |    M     |    N     |
+----------+----------+----------+ just border space
|          |          +----------+
|          |          |    Q     |
|          |          |----------+
|          |          |    R     |
|          +    P     +----------+
|    O     |          |    S     |
|          +          +----------+
|          +          |    T     |
|          |          +----------+ P extra height
|          +----------+----------+
+----------+ O extra height

A, D, E, O, P list sorted and becomes E, D, A, O, P. Where P does not play any
role.

https://codereview.chromium.org/19635004/diff/36001/Source/core/rendering/Ren...
Source/core/rendering/RenderTableSection.cpp:379: ASSERT(cell2);
On 2013/07/30 23:43:07, Julien Chaffraix wrote:
> These ASSERTs are unneeded for 2 reasons:
> - unless the std is wrong this won't happen (and it should be tested enough
that
> it's unlikely to happen)
> - you would crash below anyway.

Done.

https://codereview.chromium.org/19635004/diff/36001/Source/core/rendering/Ren...
Source/core/rendering/RenderTableSection.cpp:387: return
(cell2->logicalHeightForRowSizing() > cell1->logicalHeightForRowSizing());
This condition covers below case. In below case, A, B, C are 4 rowspan cells and
Only B spanning cell will distribute it's extra height in rows and A, C does not
need to distribute their's extra height because B is highest and A, C's extra
height covers by A's extra height.

+---+---+---+---+
|   |   |   | D |
|   |   |   +---+
|   |   |   | E |
|   |   |   +---+---+
| A | B | C | F | H |
|   |   |   +---+---+
|   |   |   | G | I |
|   |   |   +---+---+
|   |   +---+
+---+   |
    +---+

A, B, C list sorted and becomes B, A, C and A, C will not play any role.

https://codereview.chromium.org/19635004/diff/36001/Source/core/rendering/Ren...
Source/core/rendering/RenderTableSection.cpp:389: return (cellRowIndex2 >=
cellRowIndex1 && (cellRowIndex2 + cellRowSpan2) <= (cellRowIndex1 +
cellRowSpan1));
On 2013/07/30 23:43:07, Julien Chaffraix wrote:
> The comparator function passed to std::sort should be a *strict* comparator.
> This means that this condition should be changed to be strict or else badness
> will happen.

I did not get meaning of strict comparator and not able to find that what to
improve in this condition.

This condition covers below three cases. (A is 4 rowspan cell and B is 2 rowspan
cell.)

+---+---+       +---+---+---+   +---+---+
|   | C |       |   |   | C |   |   | C |
|   +---+       |   |   +---+   |   +---+---+
|   | D |       |   | B | D |   |   |   | D |
|   +---+---+   |   |   +---+   |   |   +---+
| A |   | E |   | A +---+       | A | B | E |
|   |   +---+   |   | E |       |   |   +---+
|   | B | F |   |   +---+       |   +---+
|   |   |---+   |   | F |       |   | F |
|   +---+       |   +---+       |   +---+
+---+           +---+           +---+

A, B list is sorted and becomes B, A.

Below 3 cases are same in different scenario. (B is 4 rowspan cell and A is 2
rowspan cell.)

+---+---+       +---+---+---+   +---+---+
| C |   |       |   |   | C |   | C |   |
+---+   |       | A |   +---+   +---+   +---+
| D |   |       |   |   | D |   |   |   | D |
+---+   +---+   |   |   +---+   |   |   +---+
| A | B | E |   +---+ B |       | A | B | E |
|   |   +---+   | E |   |       |   |   +---+
|   |   | F |   +---+   |       +---+   +
|   |   |---+   | F |   |       | F |   |
|   +---+       +---+   |       +---+   |
+---+               +---+           +---+

B, A list is sorted and becomes A, B.

https://codereview.chromium.org/19635004/diff/36001/Source/core/rendering/Ren...
Source/core/rendering/RenderTableSection.cpp:414: if (rowIndex == lastRowIndex
&& rowSpan == lastRowSpan)
On 2013/07/30 23:43:07, Julien Chaffraix wrote:
> Nit: Do we need to compute |originalBeforePosition| above even if we don't use
> it by bailing out here?
> 
> Also it would be nice to add a comment why it's correct to bail out here.

Done.

[Julien - ping for review, 2013-07-31 18:21:10]

assuming the new test case matches Firefox, lgtm

https://codereview.chromium.org/19635004/diff/45001/Source/core/rendering/Ren...
File Source/core/rendering/RenderTableSection.cpp (right):

https://codereview.chromium.org/19635004/diff/45001/Source/core/rendering/Ren...
Source/core/rendering/RenderTableSection.cpp:373: // 1. We sort the cells by
increasing starting row, then increasing last row (ie the top-most, longest
cells first)
Please don't just copy and paste what I said without double-checking, this
comment is wrong: We sort by increasing start row but *decreasing* last row (ie
top-most, *shortest* cells first).

https://codereview.chromium.org/19635004/diff/45001/Source/core/rendering/Ren...
Source/core/rendering/RenderTableSection.cpp:385: return (cellRowIndex2 >=
cellRowIndex1 && (cellRowIndex2 + cellRowSpan2) <= (cellRowIndex1 +
cellRowSpan1));
By a strict operator I meant an operator that defines a "strict weak ordering"
(per std::sort documentation). The definition of a strict weak ordering:
https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings

Because you allow equality in the line above, I thought it was possible to
create 3 cells for which the "transitivity" property wouldn't apply (ie x < y
and y < z but not(x < z)). I double-checked the logic on paper and I think you
can't construct such a case.

[commit-bot: I haz the power, 2013-08-01 06:34:11]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/a.suchit@samsung.com/19635004/54001

[commit-bot: I haz the power, 2013-08-01 07:09:57]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/a.suchit@samsung.com/19635004/68001

[commit-bot: I haz the power, 2013-08-01 09:11:04]

Failed to apply patch for LayoutTests/TestExpectations:
While running patch -p1 --forward --force --no-backup-if-mismatch;
  patching file LayoutTests/TestExpectations
  Hunk #1 FAILED at 1380.
  1 out of 1 hunk FAILED -- saving rejects to file
LayoutTests/TestExpectations.rej

Patch:       LayoutTests/TestExpectations
Index: LayoutTests/TestExpectations
diff --git a/LayoutTests/TestExpectations b/LayoutTests/TestExpectations
index
bfcda128080e2758dab62b8dc7e3a49c29641201..757666277e466b3ffa9363ff703d3eaaf51d19e5
100644
--- a/LayoutTests/TestExpectations
+++ b/LayoutTests/TestExpectations
@@ -1380,3 +1380,17 @@ crbug.com/264501 [ Debug ] xmlviewer/extensions-api.html
[ Pass Crash ]
 crbug.com/265650 [ SnowLeopard Debug ]
compositing/repaint/transform-style-change.html [ Pass ImageOnlyFailure ]
 
 crbug.com/261998 inspector/profiler/canvas2d/canvas2d-api-changes.html [
Failure ]
+
+# Below test case need to rebaseline after crbug.com/252120
+# Image only
+crbug.com/252120 [ Linux Win ] tables/mozilla/bugs/bug73321.html [
NeedsRebaseline ]
+crbug.com/252120 [ Linux Win Mac ] tables/mozilla/bugs/bug13169.html [
NeedsRebaseline ]
+crbug.com/252120 [ Linux ] tables/mozilla_expected_failures/bugs/bug23847.html
[ NeedsRebaseline ]
+# Text only
+crbug.com/252120 [ Mac ]
fast/table/table-rowspan-height-distribution-in-rows-1.html [ NeedsRebaseline ]
+crbug.com/252120 [ Mac ]
fast/table/table-rowspan-height-distribution-in-rows-2.html [ NeedsRebaseline ]
+crbug.com/252120 [ Mac ]
fast/table/table-all-rowspans-height-distribution-in-rows-except-overlapped.html
[ NeedsRebaseline ]
+crbug.com/252120 [ Mac ]
fast/table/table-all-rowspans-height-distribution-in-rows.html [ NeedsRebaseline
]
+# Text and image both
+crbug.com/252120 [ Mac ] tables/mozilla/bugs/bug73321.html [ NeedsRebaseline ]
+crbug.com/252120 [ Win Mac ]
tables/mozilla_expected_failures/bugs/bug23847.html [ NeedsRebaseline ]

[commit-bot: I haz the power, 2013-08-01 10:58:03]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/a.suchit@samsung.com/19635004/77001

[commit-bot: I haz the power, 2013-08-01 12:23:16]

Failed to apply patch for LayoutTests/TestExpectations:
While running patch -p1 --forward --force --no-backup-if-mismatch;
  patching file LayoutTests/TestExpectations
  Hunk #1 FAILED at 1862.
  Hunk #2 FAILED at 1970.
  2 out of 2 hunks FAILED -- saving rejects to file
LayoutTests/TestExpectations.rej

Patch:       LayoutTests/TestExpectations
Index: LayoutTests/TestExpectations
diff --git a/LayoutTests/TestExpectations b/LayoutTests/TestExpectations
index
230217f3d4e43750b30f1d5e45558853b3494884..9d51f7a606222145d53090605bbb2102e91d0891
100644
--- a/LayoutTests/TestExpectations
+++ b/LayoutTests/TestExpectations
@@ -1862,7 +1862,6 @@ Bug(ccameron) [ Mac ] tables/mozilla/bugs/bug650.html [
NeedsRebaseline ]
 Bug(ccameron) [ Mac ] tables/mozilla/bugs/bug67915-1.html [ NeedsRebaseline ]
 Bug(ccameron) [ Mac ] tables/mozilla/bugs/bug7112-1.html [ NeedsRebaseline ]
 Bug(ccameron) [ Mac ] tables/mozilla/bugs/bug7112-2.html [ NeedsRebaseline ]
-Bug(ccameron) [ Mac ] tables/mozilla/bugs/bug73321.html [ NeedsRebaseline ]
 Bug(ccameron) [ Mac ] tables/mozilla/bugs/bug92143.html [ NeedsRebaseline ]
 Bug(ccameron) [ Mac ] tables/mozilla/bugs/bug96334.html [ NeedsRebaseline ]
 Bug(ccameron) [ Mac ] tables/mozilla/bugs/bug96343.html [ NeedsRebaseline ]
@@ -1970,3 +1969,17 @@ Bug(ccameron) [ Mac ]
virtual/gpu/compositedscrolling/scrollbars/scrollbars-on-p
 Bug(ccameron) [ Mac ]
virtual/gpu/compositedscrolling/scrollbars/short-scrollbar.html [
NeedsRebaseline ]
 Bug(ccameron) [ Mac ] virtual/gpu/fast/canvas/canvas-text-alignment.html [
NeedsRebaseline ]
 Bug(ccameron) [ Mac ] virtual/gpu/fast/canvas/image-object-in-canvas.html [
NeedsRebaseline ]
+
+# Below test case need to rebaseline after crbug.com/252120
+# Image only
+crbug.com/252120 [ Linux Win ] tables/mozilla/bugs/bug73321.html [
NeedsRebaseline ]
+crbug.com/252120 [ Linux Win Mac ] tables/mozilla/bugs/bug13169.html [
NeedsRebaseline ]
+crbug.com/252120 [ Linux ] tables/mozilla_expected_failures/bugs/bug23847.html
[ NeedsRebaseline ]
+# Text only
+crbug.com/252120 [ Mac ]
fast/table/table-rowspan-height-distribution-in-rows-1.html [ NeedsRebaseline ]
+crbug.com/252120 [ Mac ]
fast/table/table-rowspan-height-distribution-in-rows-2.html [ NeedsRebaseline ]
+crbug.com/252120 [ Mac ]
fast/table/table-all-rowspans-height-distribution-in-rows-except-overlapped.html
[ NeedsRebaseline ]
+crbug.com/252120 [ Mac ]
fast/table/table-all-rowspans-height-distribution-in-rows.html [ NeedsRebaseline
]
+# Text and image both
+crbug.com/252120 [ Mac ] tables/mozilla/bugs/bug73321.html [ NeedsRebaseline ]
+crbug.com/252120 [ Win Mac ]
tables/mozilla_expected_failures/bugs/bug23847.html [ NeedsRebaseline ]

[commit-bot: I haz the power, 2013-08-01 12:34:56]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/a.suchit@samsung.com/19635004/89001

[commit-bot: I haz the power, 2013-08-01 14:12:10]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/a.suchit@samsung.com/19635004/63002

[commit-bot: I haz the power, 2013-08-01 15:35:02]

Change committed as 155337