[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.

> 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.

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"?

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).

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.

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 :-).

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.

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).

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 :-)?

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.

moving to mozilla0.9

moving to mozilla0.9

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.

Marking future and reassigning to attinasi.

--> p3

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.

[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.

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.)

Is this something to take into consideration for Gecko2 ?