71530 - implement RDF outliner

Status: RESOLVED FIXED

(Core :: XUL, defect, P2)

Description

[Chris Waterson]

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

Comment 1

[Chris Waterson]

Attachment: work-in-progress; factor nsXULTemplateBuilder into content & outliner

Comment 2

[Chris Waterson]

Attachment: work-in-progress; get sample RDF outliner to come up

Comment 3

[Chris Waterson]

Attachment: work-in-progress, flat data models working

Comment 4

[Chris Waterson]

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

Comment 5

[Chris Waterson]

Attachment: add property support, hierarchy (crudely), toggle open/close, persist open state

Comment 6

[Chris Waterson]

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

Comment 7

[Chris Waterson]

Attachment: argh! diff -uN this time

Comment 8

[Chris Waterson]

Attachment: good enough to eat, diff -uN

Comment 9

[Chris Waterson]

Attachment: xpfe/components/directory/directory.xul as <outliner>

Comment 10

[Chris Waterson]

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

Comment 11

[Bradley Baetz]

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.

Comment 12

[(not reading, please use [e-mail] instead)]

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

Comment 13

[Chris Waterson]

Attachment: implement sorting

Comment 14

[Chris Waterson]

Attachment: pretty much done diffs

Comment 15

[Chris Waterson]

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

Comment 16

[Chris Waterson]

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

Comment 17

[Chris Waterson]

Attachment: half-baked changes to directory.xul that I've been using to test

Comment 18

[Chris Waterson]

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

Comment 19

[Chris Waterson]

Attachment: first crack at natural order

Comment 20

[Chris Waterson]

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

Comment 21

[Chris Waterson]

Attachment: same as above, but get the comparison order right

Comment 22

[Ben Goodger (use ben at mozilla dot org for email)]

r=ben for the sorting changes. 

Comment 23

[David Hyatt]

sr=hyatt

Comment 24

[Chris Waterson]

Natural order sorting is in, modulo bug 73851.

Comment 25

[Chris Waterson]

Marking fixed.