Implement RDF outliner, eventually to be used to replace slow <tree>'s.

Last patch - makes nsXULTemplateBuilder a base class for nsXULContentBuilder (the good old fashioned builder that makes content models) and nsXULOutlinerBuilder (which is the nsIOutlinerView implementation) - fixes template builder, XUL document, XUL element ownership and updating eyesores that have been around for ages. Specifically, a lazy nsXULElement no longer delegates to the document when it needs content built. - explodes template builder related classes into separate files to make maintenance easier. - gets ``flat'' data models limping along in outliner (with async update even!) To do: - get nested data models working - handle open/close - return row and cell properties - somehow I've broken ``delete message'' in messenger. (I suspect that all deletions in the good old fashioned builder are busted, actually.)

With last patch, added: - support for row and cell properties - support for nested data models - toggle open/close Still to do: - sorting - deal with box object fu, depends on hyatt refactoring that - use local store for persistence on ``trusted'' outliners - when opening container, obey persisted open on sub-containers - improve efficiency of GetParentIndex() and HasNextSibling() (currently O(n) and O(n**2), respectively) - figure out why delete-message busted

Last monster patch (``good enough to eat'') fixes gross performance problems, bustage on the old-fashioned template builder, and is pretty much ready to go modulo the outliner box object stuff. (Hyatt, come hold my hand and help me hack around this until you refactor.) Still to do, sorting. I think I'll wait until mailnews lands and then try to make my sorting look like theirs. Anyone care to r=/sr=?

I guess your latest patch probably fixes 69185. How much faster is the dirviewer now? (Although for a fair comparison you'd have to wait for sorting - that was the main slowdown there) Just looking at the directory.xul diff, it looks like you've removed all the event handlers. Or are these added magically by the outliner or something? I haven't applied this yet - its 2am, so I'll try it out when I get up.

adding myself to the cc list. is the plan to convert all trees to use this, and then get rid of the XUL sort service? see nsMsgDBView.cpp to see how mailnews does sorting of string values (by getting and sorting collations keys), PRTime values, and PRUint32 values. it's stolen from how 4.x did it, but it is pretty efficient. there are some easy performance gains to be made in how collation keys are generated. (too much allocating / copying).

Okay, these diffs are pretty much cooked. There are still a few things to finish, namely . Use localstore to remember state if trusted outliner . move sort header state from column to column, rather than letting it ``accumulate'' . indicate sort-active on the column, not just the header . make NS_QuickSort() do stable sort . make natural order work for RDF containers (drag & drop will depend on this). I'll summarize the changes in a sec...

- Made nsXULTemplateBuilder be the base class for nsXULOutlinerBuilder and nsXULContentBuilder. nsXULTemplateBuilder implement nsIRDFObserver and knows how to translate the rule stuff into ``matches''. nsXULOutlinerBuilder implements nsIOutlinerView, and can translate matches into an outliner view. nsXULContentBuilder knows about translating matches into lazy content models. The nsXULTemplateBuilder communicates with subclasses in a couple of ways. 1) When matches are added or removed, it calls the pure virtual ReplaceMatch(). When a match's bindings change, it calls SynchronizeMatch(). 2) When compiling rules, the template builder will also delegate to its subclasses (e.g., the outliner builder doesn't handle rules that process matches that are specific to a parent tag's name). So, there are now some virtual methods that get invoked during rule compilation. - The nsRDFOutlinerBuilder's heart and soul is the nsOutlinerRows class. This is just a n-ary tree with some code that let's you grovel around it. - I exploded all the little helper subclasses that used to be implemented inside nsXULTempalteBuilder into their own files. This should make stuff a bit more maintainable: nsXULTemplateBuilder was pushing 8,200 lines. - Cleaned up the relationship between nsXULContentBuilder and nsXULDocument. It used to be that the document owned the content builders. When a lazy element wanted content to be built for itself, it delegated to the docuemnt. The document would dispatch the request to *every* builder. The builder would then have to figure out if it was responsible for the lazy content node. Now, since lazy content nodes *only* live in builders, a lazy content node just crawls up its own parent chain until it finds the element with a builder attached. This removed a lot of crap from the venerable nsIRDFContentModelBuilder interface. - The nsXULTemplateBuilder is now a first-class document observer, so knowledge about updating a template builder's state (e.g., opening and closing container elements, changing the ``ref'' attribute) has now been removed from the XUL document and placed into the builder itself. This got rid of methods like nsXULDocument::[Open|Close|Rebuild]WidgetItem(). - The XUL document still maintains the content model builders that are active in the document; however, they're now kept in a table, and associated directly with a content element: see [Get|Set]TemplateBuilderFor(). That means that I was able to pull the mDatabase and mBuilder fields out of the XUL element's slots, and the GetDatabase() and GetBuilder() methods delegate to the document. - Got rid of all the static kFooAtoms in nsXULDocument, and moved them into nsXULAtomList.h - nsXULDocument now calls nsIDocumentObserver::DocumentWillBeDestroyed(). It was #if 0'd for some lame late NS6 reason, and I now need it to break cycles. - It used to be the case that each rule would maintain its own private symbol table. Now there is one symbol table per template builder (integrated into the nsRuleNetwork). I used this to implement sorting in the outliner builder (you specify a ``sort'' attribute on the <outlinercol> which corresponds to a symbol in the rule). Eventually, I'd like to get rid of nsXULSortService and use the more efficient sorting mechanism that I've got in the outliner builder. (The rule network has all the information that's needed to sort.) - One minor fix to outlinerBindings.xml. Hackery in nsOutlinerBodyFrame to do hookup on an RDF outliner.

Ok, I landed this. Leaving the bug open until I get a chance to address the other issues.

The above patch is a first crack at ``natrual order'' a la bookmarks. It is sufficient to make bookmarks work, but there are still some problems with the general case (see large XXX comment in nsXULOutlinerBuilder.cpp). Also fixed infinite loop that occurs in nsOutlinerRows::Find().

r=ben for the sorting changes.

sr=hyatt

Natural order sorting is in, modulo bug 73851.

Marking fixed.