51684 - Revisiting nsIFrame

Status: NEW

(Core :: Layout, defect)

Description

[rbs]

[An item for the record in bugzilla]

Since the general feeling is that there are going to be some core redesign
efforts in Gecko 1.x, I am filing this bug in an attempt to get some thinking
going on in the back of the minds about potential changes in the nsIFrame API in
particular. Given that nsIFrame is central to the layout engine, it is a good
idea to ruminate about the fundamental changes over a sufficient time, even if
the actual implementation can wait a while before becoming a reality -- assuming
the changes are deemed necessary.

1/ A suggestion that has been around for some time is to remove the specific
text related methods, and create a separate nsITextFrame interface.

Cons:
* Creating nsITextFrame will mean that nsTextFrame incurs the additional storage
of a vtable.

Pros:
* TrimTrailingWhiteSpace() and friends stick like sore thumbs in the nsIFrame
API, and it has always seemed that they were added temporary. Removing them is
a step in the right direction to keep the geometric frame model pure.
* If properly done, there could be cleaner derivatives (e.g, bidi, MathML) of
nsTextFrame, in a way aimed at not cluttering the optimized implementation for
typical rendering of HTML text.

Balance:
The number of non-nsTextFrames certainly outweigh, by far, the number of
nsTextFrames. So the savings from removing TrimTrailingWhiteSpace() and friends
in these frames' vtables may balance the space of the vtable in nsTextFrames.

2/ Move from mRect to mArea. This is a change that I have been considering 
because the basic rectangular metrics stored in the frames are too limited, and
this has been the source of undue complications when aligning frames.

So the suggestion is simply to extend nsRect into a nsArea defined as:
struct nsArea { x, y, width [, height], ascent, descent }

(Although height = ascent + descent, the 'height' may be added to the struct
for convenience. Indeed, as we shall we see below, storing the extra ascent,
descent information can bring savings to the overall system...)

Pros of nsRect:
* It is there in the tree and it works...

Cons of nsRect:
* Nearly all frames (XUL/CSS/Table/MathML) cache their ascent and/or descent
information from reflow.  Because of the memory taken by the separate cache and
methods, it is a if the ascent/descent were in nsIFrame itself, with separate 
getter and/or setter methods in addition to GetRect/SetRect.
* Each frame is doing its little own thing (with separate getter/setter methods)
to get around the problem, and this business is probably a mis-use of developer 
time and effort.

Pros of nsArea:
* nsRect is a proper subset of nsArea (descent=0), meaning a direct mapping to
the present code is possible.
* Since (with hindsight) we now see that almost all frames need their
ascent/descent information long after the life time of aDesiredSize from reflow,
nsArea will provide a unified way to store/retrieve the information, thus
leading to leaner/cleaner code, and saving time to developers who would not
need to devise work-around to the problem.
* Since the ascent/descent are cached in the frames, the line layout code
will allocate less memory for its data structure in reflow. Also, removing the
(work-around) getter/setter methods in the frames will bring additional savings.

Cons of nsArea:
* Necessary to setup nsArea.h/nsArea.cpp like nsRect.h/nsRect.cpp
* Migrating from nsRect to nsArea is large. Although many of the changes are
simple, the number of changes in the entire tree would be large.

Balance:
Like string changes that have been made, there could be gradual passes over
the tree. Supporting both GetRect/SetRect and GetArea/SetArea in layout, and 
removing the rect variants (and related work-around) when the changes are over.

Comment 1

[rbs]

> non-nsTextFrames certainly outweigh, by far, the number of nsTextFrames.
"by far"... To be more accurate, on documents with long texts, there could be
several instances of (splittable) text frames that deny this. (Although from a
MathML standpoint, a little text/character is surrounded by a lot of tags).
However, keeping the fundamental frame model clean can be viewed as an
architectural necessity. 

Comment 2

[Chris Waterson]

With respect to (1), there will be no additional vtable overhead if nsITextFrame 
derives from nsIFrame, and nsTextFrame *only* derives from nsITextFrame.

The claim that "the savings from removing TrimTrailingWhiteSpace() and friends 
in these frames' vtables may balance the space of the vtable in nsTextFrames" 
isn't really right. The vtable is only stored once per class, no matter how many 
instances you make of it. Therefore, overhead of a additional *methods* in a 
vtable is shared among all instances. In short, you'll save four bytes per 
method (say, 40 bytes total), not four bytes per method per instance.

Another issue we should consider here is:

3. Refactoring logic so that extenders (XUL, MathML et. al.) don't need to 
*inherit* from nsFrame. (This causes the "monster layout DLL" problem we have 
now, or alternatively a DLL dependency problem if we mandate that extenders must 
link to gkhtml.dll). Can we move logic out to a generic "frame helper service"?

Comment 3

[rbs]

With the reformulated XHTML way of doing things, there seems to be all sort of 
W3C modules everyday (*ML, X*, etc.). So yes, point (3) is a vital point for the 
scalability of Gecko. Amongst other benefits, each add-on could have its
own release schedule depending on the revision of the associated standards and 
the availability of an implementation. Moreover, it will mean that the add-on 
is really kept *optional* and, if available, could be auto-downloaded from 
mozilla.org when the corresponding namespace is detected (or be hand-picked by 
the user at custom installation). Without these possibilities, maintaining Gecko
would quickly become an unsustainable nightmare.

Speaking of the extenders, I will quickly take this opportunity to mention
another thing that may also help to consolidate the strength of Gecko in the
future. We may need a new generation of XML-aware plug-ins to which we
pass the containing fragment <tag>...</tag> (e.g., <svg>...</svg>, or the DOM 
representation?) and the surrounding style context, i.e., the single resolved
nsStyleContext that hit the <tag>. This way, there could be *proprietary* 
implementation(s) of <tag xmlns=".">...</tag> that cascade their own styles,
respond to niceties such as style changes through JavaScript, and still blend
gracefully with the rest of the layout (in this respect, nsArea would help for 
proper alignments). The benefit is that we don't have to *built-in* everything 
ourselves... This was a disgression that I thought I should mention in passing
since I am sure other people have been thinking along similar lines.

Cc:ing style people for inputs about 4) the alterations needed for (huge!) style
optimizations (bug 39618, nsIFrame::GetStyleData() is implicitly deprecated and
GetStyle() will be taking over I think. This is another large change).

Comment 4

[rbs]

More about nsIFrame... In order to fix bug 45210, Marc was compelled to recently
add the new method nsIFrame::GetParentStyleContextProvider(). Unfortunately,
this function has the side-effect that a misuse (or abuse) can turn the style 
"tree" into a kinda graph with possible cycles (c.f. Marc's post on
n.p.m.layout.checkins for details/ramifications). Since the tree representation
(the DOM and the resulting cascading CSSOM) is well accepted to be
"sufficient/complete" for web rendering purposes, it looks like the root problem
in bug 45210 would later need a further investigation which should remove the
need for the function.

Comment 5

[Robert O'Callahan (:roc) (email my personal email if necessary)]

nsIFrame is a huge and beastly interface. I feel scared making it the basis of 
modularity in Gecko. Also, a lot of the functionality of Gecko is really 
organised around sets of style properties (e.g. borders, backgrounds, padding, 
positioning) rather than frame types; so we duplicate code for these things all 
over the place, leading to hosage and generally inconsistent behavior. So I for 
one would like to see this common logic moved out of the frames and into some 
set of frame helper modules. When possible, we could move the actual interface 
methods to helpers too, to cut down the size of nsIFrame and the need for 
delegation by frame implementations.

BTW, is XSL-FO on our radar? Because if so, then we have to talk :-).

Comment 6

[vidur (gone)]

Moving frame functionality out to helper classes makes sense. Currently, all 
implementations of nsIFrame inherit from nsFrame to avoid the copious amounts of 
redundancy that would result from implementing the interface from scratch. As a 
result, we make it impossible to have nsIFrame implementations in other 
DLLs.

I think XSL-FOs are in our future, but I believe that translating an FO tree 
into a nsIFrame tree is the way to go. The FO tree should just be considered the 
result tree of a tranformation. I think it's unrealistic to think of it as the 
actual formatting model of an existing layout/rendering engine.

Comment 7

[rbs]

Following your comments about XSL-FO, I followed the W3C link and was interested
to see that they use the generic "area" terminology which really hints at what
Gecko's nsIFrames are capable of. That's another pro for the move to nsArea I
would say, with the view that it might unite with the XSL-FO when there are
more insights into what is needed for such support. Looking at the XSL-FO 
spec (http://www.w3.org/TR/xsl/) from an implementor frame of mind, I tend to
agree with the initial thinking of vidur that nsIFrames could aptly do the job.
I was also struck by the large amount of overlap with CSS (so that's why some
people really feel XSL-FO can just be folded in CSS, right?). There is so much
overlap between the two models (CSS and XSL-FO) that it would seem someone can
copy mozilla/layout to mozilla/layoutfo as a starting point to support XSL-FO...

roc: could you be more explicit about your concern(s). Since Gecko is okay with
any frame tree, there have been some other bugs asking to recast the mighty
nsCSSFrameConstructor into a pluggable system of frames (bug 39965). This way of
doing so will not affect mixing all kinds of frames (which is a great benefit of
this low granularity, and which provides a basis for special effects). If the
recast is done and common frame functionalities are pushed down to helper
classes, would there be any other option(s) to ponder at? 

The other direction of extensibility to look at is in the Style System--mindful
of the CSS3 modules. However, it is hard to think of some pluggable CSS engine!
But we may live with the current system since W3C has guaranteed to retain the
CSS syntax and prevent clashes of semantics between modules. Where the problem
lies seems to be that, as more types of rules are added in the style contexts
and the style data, they are just going to grow bigger and bigger (that's
another motivation for bug 39618).

Comment 8

[Robert O'Callahan (:roc) (email my personal email if necessary)]

The following are just some ideas. Please do not take them too seriously.

Yes, Gecko frames can represent FO areas. That is not the concern. My concern is 
that it appears possible to create an XSL-FO document where, for example, the 
width of an element depends on some arbitrary function of its parent's computed 
height. (I don't know WHY FO wants to allow this, but it seems possible; I'd be 
overjoyed to find out I'm mistaken.) Gecko currently hardcodes assumptions about 
the kinds of dependencies that can exist, for performance reasons. The 
hardcoding of all those assumptions is also making things fragile and 
complicating the code; whenever we use a computed layout value, we also have to 
arrange for things to be reflowed when that value changes. And of course, 
changing these assumptions breaks stuff everywhere. I've been thinking about 
what it would be like to explicitly track dependencies instead, so that reading 
a layout-computed value automatically records a dependency and ensures that 
incremental updates will occur correctly. This would obviously be a huge change 
and could not be done soon.

BTW, an interesting change of similar magnitude: allow the frame model to be 
partial, by discarding (or even better, never creating) frames that you don't 
need, e.g. for content that's scrolled out of the viewport (like you do for 
trees now). Obviously you need to pull tricks with caching, precomputation, 
memory balancing and whatnot to make it work optimally depending on the 
resources available.

Roger, I agree with what you say about the style system. Clearly a major 
dimension of extensibility in the style system is adding new properties. So I 
think the style system interface should be independent of the list of 
properties; we should get properties using property name atoms rather than as 
hardcoded object fields. This would also allow us to tune the style system by 
using different storage techniques for frequently and infrequently used 
properties. If it turns out to be too slow to fetch properties one at a time by 
name atom, there are ways to speed things up without compromising the interface.

Would it be possible to separate content and style (XBL) from actual layout, 
with real XPCOM interfaces between them? Right now things are sort-of separated 
internally but I think that having a separate module for "really just layout" 
would really help. We could then rip out other pieces of functionality from 
layout without committing to nsIFrame as a public interface. There's a lot of 
text-related code that could be moved out into a separate "text services" 
module. It would also be great if we could get rid of widgets ... can we just do 
them in XBL :-)?

Comment 9

[buster]

Ok, the NS RTM push is behind us, so it's time to get serious about this issue.
 I think a bug is the wrong place for this discussion.  Let's move it to the
layout newsgroup.  Also, this discussion has gotten too big for a single thread,
I think.  I'll start a thread on along the lines of "improve nsIFrame and make
layout extensible"  Somebody else please pick up the pieces that I leave out as
separate threads (XSL-FO, style system changes, etc.)

I think doing *something* in this area is critical for the embedding effort.
There are real oppurtunities for size and performance improvements.

Comment 10

[buster]

moving to mozilla0.9

Comment 11

[buster]

moving to mozilla0.9

Comment 12

[buster]

Edward Kandrot wrote:
Here's an exchange from some private email.....

=====================================================================

I have been profiling some code that adds a large number of objects to doc (it
creates around 10,000 divs).  By doing this, I have been able to find some nlogn
algorithms in our code base.  Tracking through the code, I found that the code
does a lot of appending of items to a FrameList.  The main problem with append,
in our current implementation, is that it calls nsFrameList::LastChild(), which
walks the list every time a child is added.  How hard would it be to modify this
code to maintain mLastChild, which would then make this function a virtual nop
(except for the xpcom overhead, which it and GetNextSibling incur in great
quantity)?

Thanks for your time.

-Edward

=============================================================

I cannot believe that you had the unbridled audacity to ask this question. (Just
kidding!)

Edward Kandrot wrote:


I have been profiling some code that adds a large number of objects to doc (it
creates around 10,000 divs).  By doing this, I have been able to find some nlogn
algorithms in our code base.  Tracking through the code, I found that the code
does a lot of appending of items to a FrameList.  The main problem with append,
in our current implementation, is that it calls nsFrameList::LastChild(), which
walks the list every time a child is added.  How hard would it be to modify this
code to maintain mLastChild, which would then make this function a virtual nop

Not hard, right? Looks like the logic is self-contained within the nsFrameList
class. The only downside I can see is you'd add an extra word of storage to
nsContainerFrame, which itself can be constructed in great quantity. But I think
nsContainerFrame is already ~15 words big, including vtable, so the incremental
cost isn't bad.

How many nsContainerFrame (and nsContainerFrame-derived) objects are created on
typical web pages? I think nsBoxFrame is derived from nsContainerFrame, so
this'd affect chrome, too...

The other places nsFrameList is used AFAIK is on the stack, so "who cares" (heh,
heh...)

(except for the xpcom overhead, which it and GetNextSibling incur in great
quantity)?

Search bugzilla for bugs with nsIFrame in the summary. There's one called
"rethink nsIFrame" or some such. You might be interested in that.

chris

=====================================================================

Sorry for taking so long to respond.  RTM, and all that...

Chris' answer is correct, in that it wouldn't be hard at all.

But we do create a ton of nsContainerFrame instances. And the case where a
parent frame contains thousands of children is pretty rare.  So I'm reluctant to
add the extra 4 bytes.

Maybe there's some other way to maintain that information.  Or, maybe there's a
way to make the overhead smaller.  For example, currently, all frames derive
from nsFrame.  It is possible for methods like nsFrameList::LastChild() to treat
XPCOM objects of type nsIFrame as concrete objects of type nsFrame.  Then the
method would become:

nsIFrame*
nsFrameList::LastChild() const
{
 nsFrame* frame = (nsFrame *)mFirstChild;
 while (frame->mNextSibling; frame=frame->mNextSibling) {
 return (nsIFrame *)frame;  // notice that nsIFrame objects are not ref-counted
}

tighter code, no xpcom overhead.  I've oversimplified the casting, but basically
it should work.  It'd be interesting to get some quantify numbers from your test
and see if this is a significant improvement or not.

Does this sort of thing makes third party frames tougher to do?  Maybe, but
maybe we do third party frames as extensions of an existing frame type that
derives from our concrete base classes.  For example, off the top of my head:

nsExtensionFrame : public nsFrame {
 nsISupports *mDelegate;
}

nsExtensionContainerFrame : public nsContainerFrame {
 nsISupports *mDelegate;
}

So a third party frame is just a (container) frame, with a delegate that gets
called for all nsIFrame-y sorts of calls.

Anyway, my point is that it should be possible to reduce the xpcom overhead by
knowing actual concrete classes at critical points, while still offering an
extension mechanism.

I will add this thought to the "nsIFrame must die, long live nsIFrame" bug if
someone hasn't already beaten me to it.

Comment 13

[karnaze (gone)]

Marking future and reassigning to attinasi.

Comment 14

[Marc Attinasi]

--> p3

Comment 15

[Jon Smirl]

Any chance that this is going to happen? Now that work has started on SVG I'm 
concerned about how big gkcontent/layout could become; they are already big 
enough to cause problems building and debugging. The Adobe SVG implementation 
is over 3MB.

Also, it would also be much easier to work on the SVG code as a separate module 
instead of a CVS branch which is continuously getting out of sync.

This would also be a good competitive edge for Mozilla. External groups could 
build things like support for Chemical ML, Cell ML, Music ML, SVG, XSL-FO, 3D 
ML without the need to tightly integrate into the very complex gkcontent/layout 
code.

Comment 16

[rbs]

[Hixie-PF] - it might be worth documenting your reasons somewhere to enligthen
other interested people. I have myself come to the conclusions that the
requirements of MathML (linebreaking, superior handling of fonts, Text Services
like selection, copy-paste, find, etc, Dynamic DOM + JavaScript, etc) need a
close integration. Trying to do these separately can be pretty hard and might
discourage from thinking of a less ambitious extensible framework. But MathML is
text formatted differently anyway. Close integration is not necessarily true for
other modules. I have seen the demo of the IE guys where they have extended
their engine to allow pluggable COM layout components a-la <object> and that's
how their MathML support is working over there -- using a COM component
developed by Design Science (the maker of MathType). Although the area allocated
for that piece of concent is foreign (e.g., no DOM related functions there),
it showed that the IE people now have an extensible infrastructure to add other
things (if they wished) without cluttering the internals of their engine.

Comment 17

[Hixie (not reading bugmail)]

PF = I wouldn't consider this for 1.0. The reason being that it is high risk.

Frankly I should probably revisit the bugs marked PF now. This is more like a P2
on the big scale of things. (The big scale including things like SVG and MathML.)

Comment 18

[Markus Hübner]

Is this something to take into consideration for Gecko2 ?