Open Bug 203686 Opened 21 years ago Updated 2 years ago

[BC] border collapse code how to proceed?

Categories

(Core :: Layout: Tables, defect, P3)

Product:
Core
Component:
Layout: Tables
Type:
defect

Tracking

()

Milestone:
Future

People

(Reporter: bernd_mozilla, Unassigned)

References

(Blocks 4 open bugs,
URL
)

Details

Attachments

(1 file)

status
2.53 KB, text/html
Details
Attached file status — 
any comments hints etc are wellcome
Do we have any evidence that optimizing collapsed borders is/was important?

It seems to me that moving collapsed border painting to cells would simplify the
code and make it possible for us to solve a lot of problems.
I don't have that kind of evidence, even more while horking the border drawing
in nsCSSRendering (sorry Robert for this) I got the impression that the drawing
of borders in the separate mode is less efficient and I did not yet hear a
complaint about beeing unefficient. More than this I believe that we can
preserve the idea of drawing only the top and left border for every table cell
and to only draw the right and bottom border only at the table edge. The cost
would be that for every table cell we need to wind up to the border owner to get
the style information. Another way would be to store for every border segment
the owner as a nsIFrame* in the cellmap  but this means 2 * 4 bytes per cellmap
entry. 
To make it explicit I would like to move the code to the table cell as I dont
see any other way to get the scrolling working. 

Robert what do you mean with a lot of problems, are they behind the scope that I
mentioned in the attachment? 
Painting only the top left borders of each table cell won't work for the case
when a table cell is "position:relative".

What I meant was that cell-based painting would fix "position:relative", fix
scrolling, fix any case where the table cell has a view (e.g., cells with
'-moz-opacity'), and probably fix other problems.
Priority: -- → P3
Target Milestone: --- → Future
If we store for each cell which table element owns each border segment, we can
probably use the painter framework set up in 4510 to optimize painting. (It lets
you cache style info for rows/cols as it loops over the table cells.)
OS: Windows 98 → All
Hardware: PC → All
Linking in dependencies. The dependent-blocking relationship might not be quite
correct for all of them, but they're all relevant afaict.
Blocks: 126540, 135236, 142998, 174470, 190593, 192031, 221952, 224309, 229712
Depends on: 195772, 229883, 237530
Cell-based painting will also (barring any unfortune screw-ups) fix 174470 - the
RTL issue.

Answering question no. 1 from the 'status' attachment: to realize just how
crucial the RTL border-collapse issue is, imagine for a second what would happen
if Mozilla did not at all support border-collapse. Disastrous, outrageous,
inconceivable, right? Well, for websites in Hebrew, this is the case. Even
worse, not only is it not supported (in which case Mozilla could use
non-collapsed borders, which is by the way not a bad idea for a temporary fix
for 174470 until the border-collapse code is rewritten), it is drawn wrong,
creating a visual mess of such tables. So the answer is yes, these problems must
be fixed, they are not at all esoteric.

PS - ok, only ~0.5% of web users use websites written in Hebrew so one could
claim statistic esotery.
Blocks: 242997
Blocks: 248374
Blocks: 257086
Summary: border collapse code how to proceed? → [BC] border collapse code how to proceed?
Blocks: 262709
Blocks: 296938
Blocks: 256749
Some questions that need to be solved (probably by the W3C, but AFAIK we're still waiting for the CSS3 table module) :

In BC model, when a cell is taken out of flow with position: absolute/fixed, does it take its borders with it ? More precisely, which of the propositions below is the Right Way ?
a) The cell moves, but borders stay unchanged in the table
b) The border in the table stay unchanged, but the cell paints its own copy of the borders
c) The borders come along with the cell, and are not drawn in the table
d) The borders drawn by the cell are what would be drawn in border separate model (but perhaps half outside the cell), and in the table the borders of the cell are considered as border:none, thus having no longer any influence on the rest of the table
?) Take two of the above, shake a bit, and get a new combination
> still waiting for the CSS3 table module

Don't hold your breath. :)

When the cell is absolute/fixed positioned, it's pulled out of the flow and the table behaves as if it didn't exist. The more interesting question is what to do with relatively-positioned cells.
(In reply to comment #8)
My intuition says (b).
Continuing questions :

First, another possibility in the list above :
e) The out-of flow cell only takes with it its inner half of the border, leaving the other half in the table

Second, do we want to use the same behaviour for "position: relative;" cells ? Since they aren't exactly taken out of flow, it would be sensible to make their borders influence the resolution of border conflicts, for example.

Third, do we want to have a rendering algorithm for BC tables that will flawlessly work with borders that aren't locally invariant ? That is if a row border is, say, a gradient (e.g. with "border-image"-like facilities), drawing this border in chunks belonging to the table shouldn't appear as several gradients end-to-end...

Finally, if the cells draw their part of the border (which IMHO is the way to go, I blindly follow roc and bernd on this) and draw not only their inner half but the whole border, how to handle overlapps ? Some borders could be drawn twice, and some corners four times... This leads to slow rendering, and also to gliches (e.g. antialiased dots drawn on top of each other).
If I understand well, the good news is that then each cell-painted border would be in a separate display item in the display list (at least one display item for each cell, but probably the 4 borders of the cell in a single item)... Perhaps there could then be a simplification to only draw each border once ?

(Nota: If my wanderings are stupid/irrelevant/already known by everyone, or do not belong to this bug, let me know so that I do not pollute any longer.)
(In reply to comment #11)
> e) The out-of flow cell only takes with it its inner half of the border,
> leaving the other half in the table

It seems to me that implies the borders have not really been collapsed but rather halved... YMMV on that notion though.

> twice, and some corners four times... This leads to slow rendering,

Not necessarily. Maybe determining ownership slows rendering more than double rendering? Or maybe the contribution of this to the entirety of the rendering is not that significant?

Note that all of this has already been discussed in the past by fantasai, roc, dbaron, and bernd.  Might be worth finding the bug that happened in...
(In reply to comment #13)
> Note that all of this has already been discussed in the past by fantasai, roc,
> dbaron, and bernd.  Might be worth finding the bug that happened in...
> 

I read all I could of the layout:tables bugs in which fantasai and bernd spoke, and couldn't find the discussion you talk about. Maybe in a wiki page ?
That makes me think that a wiki page discussing of the way to paint borders by cells could be utterly useful (if not already existent).
probably on IRC, but boris remembers the outcome correctly.

The problem with determining the ownership during paint is that it makes scrolling slow. So it should be done when the properties change and currently we use reflow for this.
Assignee: layout.tables → nobody
QA Contact: madhur → layout.tables
Bug 191567 has the discussion I was thinking about.

And yes, getting it all wiki-ed in a coherent way would be great.
I began a wiki page on http://wiki.mozilla.org/Gecko:Border_collapse

I need to sleep so can't do more now, but I hope that helps. Feel free to change the wording/organisation/ideas, etc... and if I wrote blunders and/or shocking/unpleasant things, please forgive me, I swear I didn't notice.
Blocks: 444000
I've decided to try to tackle this. We'll see if that finishes well.

I've created bug 452319 to discuss actual code and patches when the time comes;
here can be used for preliminary discussion.

Here is what I have in mind:

Currently Gecko uses a TableBackgroundPainter to paint the
colgroups/cols/rowgroups/rows backgrounds under the cells, for performance
reasons, and I don't plan to change that. Backgrounds of cells themselves are
not included (1).
IIUC, all those backgrounds can be gathered in the same display item, since I
don't think we support applying z-indexes to those (what about
rows/rowgroups??).

Then the cells paint their backgrounds themselves, with a display list for each
cell, IIUC, so it's not difficult to get those in tree order (if not already).
The code as it is currently is thus correct and wouldn't be changed.

For borders, the current plan is to morph the TableBackgroundPainter into a
TablePainter which would be able to tackle BG painting *and* border painting,
because a lot of the needed information is the same.
We absolutely need to have the BC borders in another display item than the
previous non-cell backgrounds, because said borders need to be at least atop
non positionned cells (or below in z-index). That means I would make the
aforementionned TablePainter live (as a nsTableFrame member, for instance)
trough the whole painting process, to avoid recomputing at BC border painting
information I already calculated to paint backgrounds.

There I'm not completely sure of what to do: the simplest would be to put all
borders into the same display item, which would mean that borders don't follow
(z-index-wise) the cells if the cells are positionned with z-index. I don't
think it's outrageous to do like that. I don't plan to make the borders move
with the cells either, just to make the table paint the borders itself all at
once at the best vertical position possible in the display list.

I still need to understand what is the "flagged TABLE_BG_PAINT ::Paint call"
used for (intuitively it sounds like something that the display lists were made
to replace, but I didn't look at that part of the code yet, so I'm probably
just speaking nonsense).

(1) Firefox 3 (as in my debian package) seems to paint the cell backgrounds
also with the table painter, but it's not the case anymore with the trunk. I'm
bisecting to find where it changed.

The IRC discussion referenced in comment 15 might've been
  http://fantasai.inkedblade.net/mozilla/irc/border-collapse-css
It's bug 423823 that removed the drawing of cells by the table painter when they are in a scrolled tbody.
Some remarks/questions:

a) I think that tables like this:

|---------|-------------------|
|         |                   |
|         |                   |
|         |                   |
|---------|---------|---------|
|                   |         |
|                   |         |
|                   |         |
|-------------------|---------|

make really difficult to do a rendering per cell, or with loops over the cells.
I'd rather make a loop over corners/cellmap coordinates. The first consequence is that I won't be able to use a solution like in bug 423823 to get correct clipping/scrolling. Since I'd have to write code to handle partial/clipped painting for borders, I could revert bug 423823 and handle that with the same machinery, which would give back the tablepainter performance to scrolled rowgroups. What do you think ? 

b) IIUC, Part of this rewrite is to rewrite CalcBCBorders, because we want to store less information in the cell map (namely, not *what* won the border fight, but *which one* won), and CalcBCBorders is too big a beast anyway, calculating border chunks which we want to get rid of. What is exactly the goal here ? Do you have some advice ?

My idea was that we could remove every optimisation like merging of borders etc... and paint each border separately, each corner separately (because corners may need painting on an offscreen surface to avoid seems), even if everybody is opaque and the same color; and see what performance we loose. Then when we are sure we have correct rendering, we can focus on special cases if needed.
I am sure that I follow the idea of storing less in the cellmap.
>  What is exactly the goal here ? Do you have some advice ?
It does exactly the opposite what you propose, it computes as much as possible to do as few as possible computations during painting to prevent slow scrolling. And IMHO we should keep this. 

I would prefer a approach that creates test cases first and then makes sure that the changes do not regress the rendering. A good start would be http://mxr.mozilla.org/seamonkey/source/layout/reftests/table-background/ and to convert it into real test cases (currently they are only crashtests)

and there a few more test cases once bug 43178 gets reviewed, which will remove one of the reasons why CalcBCBorder is so complicated.
> I am sure that I follow the idea of storing less in the cellmap.
> >  What is exactly the goal here ? Do you have some advice ?
> It does exactly the opposite what you propose, it computes as much as possible
> to do as few as possible computations during painting to prevent slow
> scrolling. And IMHO we should keep this.

Are you saying that we should keep the border chunks calculation ? Which means that changing the color of one cell border can potentially trigger an update for a big part of the table. This border chunk feast is very rigid and does not cope well with changes.
I'm all for calculating the most we can, but the border chunks system (to be able to paint several cell borders together when they are the same color/width/style and aligned) is complicated (decide when you group, especially when you cannot afford to paint two times a corner due to transparency, etc...), and as a whole looks like a premature optimisation.
I wouldn't like to have to tweak this system to get correct rendering (esp. all the corner difficulties) and to cope with dynamic styling, without any proof that this complex calculus is worth it in terms of painting time gains, not to mention that in its current style nobody wants to touch it even with a barge pole (even super-bz, which means a lot to me)

> I would prefer a approach that creates test cases first and then makes sure
> that the changes do not regress the rendering. A good start would be
> http://mxr.mozilla.org/seamonkey/source/layout/reftests/table-background/ and
> to convert it into real test cases (currently they are only crashtests)

Sure, I'm planning to do that, and I'm planning to do the most incremental rewrite possible to be able to easily track regressions.

> and there a few more test cases once bug 43178 gets reviewed, which will remove
> one of the reasons why CalcBCBorder is so complicated.
You have border segments if you like it or not, the table from comment 21 illustrates this. And typical use cases with one rowspan on the left side of a table will also require this.

However: I have no authority to require any design and this is due to the fact that I am notoriously bad at those decisions. Authority in these questions do have dbaron, bz and roc.

What I can offer is a little bit of experience with this code. And I am little bit scared that I am taking part on sending you on a death march project.
This fear is due to the following things:
1. I did not review a patch from you for a table issue, this makes me wonder how good you know the code that you need (cellmap, style resolution, painting etc)
2. I witnessed the first write of this code because the old design was probably easier but it never really worked as good as the current design (in fact the old design was backed out).
3. A new design should in my eyes meet the following criteria:
a. more correct
b. at least as fast the previous design
c. easier to maintain
All that I read here does only focus on 3c, but for me 3a and 3b are more important.
4. Your dislike of the table painter, I am very happy about this code, it just works and after I kicked all the crash bugs I didn't touch it for ages.

Will it really help if you say in 6 months: it just didn't work, there where too many edge cases, that the easier design did not handle.   This is the point of my pledge for good reftests, even if this happens, there will be something that will last.

We had with this code the procedure, write it and sort out the bugs later, so it would be IMHO much more preferable to have a design that will make damned sure that 3a is met by design and not a afterthought.
Bernd, I believe the cellmap should only be storing who won the collapse, not what won the collapse. I talked about this with Julien and Boris at the Mozilla Summit, which is why we are discussing it here. It will simplify the code, avoid broken and incomplete caching of style data, and save memory. With regards to paint speed, I think using the table painter should take care of performance concerns. This was my plan when I wrote it: it is why it's not called nsTableBackgroundPainter. :)

I suspect all of the borders need to be drawn from cellmap corner to cellmap corner, even long segments (which would then be considered as multiple short segments) to get dotted lines to look right. Julien, you should take a look at bug 19963 and what Zack is planning to do there.

IMO, I think a first pass at rewriting this code should take into consideration but not include all the necessary painting trickery to get border joins looking right in Cairo. I would rather see the wireframe first and the details later than an attempt to tackle everything at once.

Writing tests first is an excellent idea. If they are also valid CSS2.1-format tests, then I will be even happier. :) There are some border-conflict tests already at http://www.w3.org/Style/CSS/Test/CSS2.1/current/xhtml1/ It should be possible to reftest the conflict rules.

However, I don't know if we can reftest how the corner joins are done etc. It's possible to write non-reftest tests for them, of course, but we do need to decide what we want to happen for the tricky cases in order to write tests for them. Wrt Julien's writeup in https://wiki.mozilla.org/Gecko:Border_collapse it is missing a possibility for the positioned cell, which is drawing its own borders but only for the segments that won.
URL: https://wiki.mozilla.org/Gecko:Border...
I think that your 3.a is the first reason to rewrite the code; currently the border chunks as calculated can span a whole table and be across several "corners". My idea was as follows: loop over the corner coordinates, and every time we have a "real" corner (not in the middle of a cell), paint it, and paint the borders parting right and down from it (if they exist).

The borders can be painted directly on canvas, but as was done for divs border rendering rewrite, we possibly need to do more complicated things with the corners; and since 4 borders can come there, there is less room for optimisation like "draw all borders in one pass".

I really think that 3.b is less of an issue, because what I propose would make the code essentially as few optimised as the non collapsed model, which is not that bad.

For the corners rendering, the more I think about it, the more I think we need to do something more like "never share the border between more than two borders", and decide which ones "by majority, then size". I'll write a "spec" for it before implementing it, but it's less important to get it right at first, my first pass can afford not to render corners at all; the corner problem is well self-contained.

As for the dislike of the table painter, it's just because initially I had in mind to make the rendering fully cell-based; but it was a red-herring, and I'm perfectly happy to use the table painter now. Note that recently I even proposed to revert scrolled rowgroups painting to the table painter, since I'll have to implement clipping for the borders, and as such will have a (better ?) fix to bug 423823. So in effect I'm willing to use *more* table painter.

All in all, I'm not planning to dive into coding before thinking, specing, reftesting and all, because the worst that could happen is a full opaque rewriting and then we have a huge impossible to review patch which does some things better and some things worse than before.
URL: https://wiki.mozilla.org/Gecko:Border...
And last but not least, this is the first thing I wanted to correct in gecko, and what led me to invest my time into Mozilla; but since it was too hard to begin with, I retreated to widget which was easier to handle because you don't have to know that much of the inner workings of Gecko. Now I want to crawl my way back to layout, but I can still retreat to widget if things go wrong.

The good thing about this bug is that nobody is really relying on me to fix it, and nobody would have the time to do this rewrite. bz may need only 3 weeks to write it, but he doesn't have spare 3 weeks, and the same goes for a lot of the people more capable than me. I may take 6 months to understand all, but I don't hurt anybody, and with luck you will have gained a new layout dev. Without luck I will have lost some time, which I probably wouldn't have devoted to Mozilla if not for that bug ;)
My main difficulty is that making the table paint the borders means the code has to handle a lot of cases (visibility: collapse, scrolling, etc...), but making the cells paint the borders means that a cell may be responsible for a lot of borders (and that doesn't tell us how to handle some constructs, what of borders at a boundary between rowgroups, one scrolling, the other not, etc...).

Either way this code will be complicated, so I'd rather go with the best performer (which almost certainly is the table painter approach).

Also, what do we do when a cell has opacity, and it is its border that won ? Do we apply the opacity on the border, or not ? etc... There are a lot of spec issues to solve before anything else.
Julien and I talked on IRC. It seems a promising way to go could be to have table-painter-like code that runs at BuildDisplayList time, generating display list items for the various background and border parts. This lets us reorder those items and take advantage of display list optimizations like skipping content under other opaque content.

(In reply to comment #28)
> Also, what do we do when a cell has opacity, and it is its border that won ? Do
> we apply the opacity on the border, or not ? etc... There are a lot of spec
> issues to solve before anything else.

In general I think we should cut the border in half and give half to each cell on either side.
The idea between doing the TablePainter logic at display list creation time is that currently we loop over the cells two times: once to create the display list, and once with the table painter. The table painter is really efficient for the loop, because it caches a lot; the display list logic is good because it tracks damage areas/dirty rects.
Apart from the advantages given by Robert, it would remove the need for things like in bug 423823, perhaps even remove altogether the need for passing...
Depends on: 452319
Severity: normal → S3

The severity field for this bug is relatively low, S3. However, the bug has 11 votes.
:dholbert, could you consider increasing the bug severity?

For more information, please visit auto_nag documentation.

Flags: needinfo?(dholbert)

The last needinfo from me was triggered in error by recent activity on the bug. I'm clearing the needinfo since this is a very old bug and I don't know if it's still relevant.

Flags: needinfo?(dholbert)
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: