Open Bug 1031692 Opened 10 years ago Updated 1 month ago

Consider making the TreeWidget use the AbstractTree mechanism introduced in bug 879008

Categories

(DevTools :: General, defect, P3)

defect

Tracking

(Not tracked)

People

(Reporter: vporof, Unassigned)

References

Details

Attachments

(1 obsolete file)

The tree widget implemented in bug 993014 has a rigid set of assumptions that made it unreasonable to adapt and use for for new profiler UI. As a purely pragmatic solution, an AbstractTree was created in bug 879008. In the interest of code unification and re-use, the AbstractTree may be used as a foundation for a general-purpose TreeWidget, due to it's intrinsic highly generic nature, the reasons for which I'll try to explain below.

The existing TreeWidget assumptions (as a comprehensive list, including things that may or may not be "easy to fix") that made it unsuitable for bug 879008 are:
1. items deeper than level 6 will not be indented anymore
2. only strings can be inserted in the tree, no support for custom nodes
3. odd|even rows in the tree can't be colored differently
4. expando-arrow placement is rigid and can't be custom-positioned 
5. indentation placement is rigid and can't be customized
6. the tree can not be lazily populated based on a provided data source

The new AbstractTree class has a very different (flat) internal DOM structure that automatically fixes all of the above problems. Customized nodes are the foundation of each item. In the DOM, all items are children of the same parent, so odd|even selectors can be used in CSS. Arrows and indentation may be set up anywhere inside an item etc. etc.

This even makes it possible to have a tree that looks like this:

<tree container node>:
  item 1: ... | <node> | ... | ▼ (root)                      | <node> | ...
  item 2: ... | <node> | ... |   ▼ foo                       | <node> | ...
  item 3: ... | <node> | ... |     ▼ bar                     | <node> | ...
  item 4: ... | <node> | ... |       ▶ node_with_children    | <node> | ...
  item 5: ... | <node> | ... |         node_without_children | <node> | ...

As a data structure, every item in the tree knows its root, ancestors and children; however, the DOM structure is flat.

As far as the alternative goes, fixing some of the above issues would be quite hard in the TreeWidget due to its internal DOM (and data) structure. If a solution is found, it would be more inefficient as well (e.g. for having odd|even items with different backgrounds and different heights), while the new AbstractTree fixed all of the above problems for free.

As it stands, the following concerns were detailed in bug 993014 about the the new AbstractTree's API, specifically lacking some of the operations that are present in the current TreeWidget. I'll address each one individually:

1. "[No way to] select a particular node given its unique id / reference."
-- Can be easily implemented as constant time operation, due to the flat DOM structure and the fact that selected tree items === focused nodes in the DOM.
-- Expanding the parent nodes would be as simple as walking upwards to the root.

2. "[No way to] know if a particular node is selected."
-- Again, since focused nodes in the DOM === selected items in the tree structure, this can be found out in constant time as well.

3. "[No way to] get notified when a node is selected."
-- This is incorrect, "focus" events are already emitted from the tree (with the corresponding target item as a parameter) whenever an item is selected, so this requirement is already met.

4. "To expand or focusing a node etc. you need to first get hold of that node, there is no method to simply say `tree.select(<path to the node / unique id of the node>)`"
-- This is incorrect as well, since the DOM tree structure is flat, expanding a node would simply mean knowing it's id, from where I'll defer to point 1.
-- This operation will always be constant for finding the node, and linear time to make sure all nodes are expanded to the root.

Implementing the missing APIs (which are just points 1., 2. and 4. in the above list) is a breeze. Regarding all other operations, the new AbstracTree's internal structure makes it so that everything can be done extremely efficiently.

Pragmatically, from a customization POV and extendability capabilities, the AbstractTree is superior. If a consensus is reached, my (friendly) opinion is that it'd be better in the long run (and in the interest of having a single completely generic tree implementation) to build a TreeWidget based on the newly introduced AbstractTree from bug 879008.

A TreeWidget would still be necessary because the AbstractTree is completely assumption-free, and doesn't even build it's own DOM nodes, while consumers may not care too much about so much customization (and just want to quickly insert labels in a tree). Therefore, my suggestion is to subclass AbstractTree for a quick&easy tree widget, while keeping the AbstractTree for more complex scenarios.
Depends on: 879008
FWIW, attachment 8447664 [details] [diff] [review] in bug 879008 contains an AbstractTreeView.jsm file in devtools/shared/ with the new implementation described in the above comment, along with a very detailed explanation about how to use it.
(In reply to Victor Porof [:vporof][:vp] from comment #0)
> The tree widget implemented in bug 993014 has a rigid set of assumptions
> that made it unreasonable to adapt and use for for new profiler UI. As a
> purely pragmatic solution, an AbstractTree was created in bug 879008. In the
> interest of code unification and re-use, the AbstractTree may be used as a
> foundation for a general-purpose TreeWidget, due to it's intrinsic highly
> generic nature, the reasons for which I'll try to explain below.
> 
> The existing TreeWidget assumptions (as a comprehensive list, including
> things that may or may not be "easy to fix") that made it unsuitable for bug
> 879008 are:
> 1. items deeper than level 6 will not be indented anymore

Easily fixable by using JS instead of CSS for indentation

> 2. only strings can be inserted in the tree, no support for custom nodes

Wrong, you can easily do tree.add(..,.., {id: "foo", node: domNode}).

See [0] for example

> 3. odd|even rows in the tree can't be colored differently

Yes, they can't be. Trees are not meant to have that functionality to start with. Only in Profiler, where its a tree-table combo, it is needed.

Again, this is an assumption, but a very accurate one, from what I have seen in the gif of Profiler UI, the tree nodes are of equal height and thus CSS can be used to achieve such behavior.

> 4. expando-arrow placement is rigid and can't be custom-positioned 

Since you are (and can) use a custom node instead of string as a tree item, you can place the arrow anywhere you like. The arrow is places using CSS, so its just a matter of overriding it with custom CSS rules.

> 5. indentation placement is rigid and can't be customized

Again, if I take into account that you want to use custom node, you can place the indentation anywhere, you have enough attributes on the node to do so.

> 6. the tree can not be lazily populated based on a provided data source

Agreed, a thing once inserted via tree.add goes and sit in the DOM. But there was no usecase of poppulating it lazily while creating the widget and adding some functionality which will not be used in near future was over engineering. I had to remove the functionality of using the tree with url strings instead of node arrays just for the same reason.

That being said, its not much work to make it insert lazily.

> The new AbstractTree class has a very different (flat) internal DOM
> structure that automatically fixes all of the above problems. Customized
> nodes are the foundation of each item. In the DOM, all items are children of
> the same parent, so odd|even selectors can be used in CSS. Arrows and
> indentation may be set up anywhere inside an item etc. etc.

This sounds good on the top but actually is an overhead when you simply want to use the tree as a source view (which is the majority use case for such a tree)

you have to create your own DOM node add just a string to it and then call the tree's add method.

TreeWidget was built on the foundation that using it as a source tree will be its primary use case and any custom use case can be taken care of by inserting custom node instead of strings.
 
> This even makes it possible to have a tree that looks like this:

This can be done using TreeWidget as well. 
> <tree container node>:
>   item 1: ... | <node> | ... | ▼ (root)                      | <node> | ...
>   item 2: ... | <node> | ... |   ▼ foo                       | <node> | ...
>   item 3: ... | <node> | ... |     ▼ bar                     | <node> | ...
>   item 4: ... | <node> | ... |       ▶ node_with_children    | <node> | ...
>   item 5: ... | <node> | ... |         node_without_children | <node> | ...
> 
> As a data structure, every item in the tree knows its root, ancestors and
> children; however, the DOM structure is flat.
> 
> As far as the alternative goes, fixing some of the above issues would be
> quite hard in the TreeWidget due to its internal DOM (and data) structure.
> If a solution is found, it would be more inefficient as well (e.g. for
> having odd|even items with different backgrounds and different heights),
> while the new AbstractTree fixed all of the above problems for free.
> 
> As it stands, the following concerns were detailed in bug 993014 about the
> the new AbstractTree's API, specifically lacking some of the operations that
> are present in the current TreeWidget. I'll address each one individually:
> 
> 1. "[No way to] select a particular node given its unique id / reference."
> -- Can be easily implemented as constant time operation, due to the flat DOM
> structure and the fact that selected tree items === focused nodes in the DOM.

True, but then if we are talking of performance, ATV's selection is heavier than TW's selection as no extra work to first insert the required DOM elements into the tree is needed in case of TW

> -- Expanding the parent nodes would be as simple as walking upwards to the
> root.

But you still have to insert the DOM nodes which are not inserted. Managing that is a bit of overhead.
 
> 3. "[No way to] get notified when a node is selected."
> -- This is incorrect, "focus" events are already emitted from the tree (with
> the corresponding target item as a parameter) whenever an item is selected,
> so this requirement is already met.

That is being managed by DOM, right ? as in the addEventListener("focus") thingy.

Then to get any meta data associated by the node (see attachment in TW), I will have to query the tree myself (that method also does not exist btw)
 
> 4. "To expand or focusing a node etc. you need to first get hold of that
> node, there is no method to simply say `tree.select(<path to the node /
> unique id of the node>)`"
> -- This is incorrect as well, since the DOM tree structure is flat,
> expanding a node would simply mean knowing it's id, from where I'll defer to
> point 1.
> -- This operation will always be constant for finding the node, and linear
> time to make sure all nodes are expanded to the root.

But still, you will have to add DOM nodes to the document. Which can take quite a while in case when a there are huge number of children to the expanding parent.

It like a tradeoff, do all the DOM insertions at initialization vs do it everytime a node is expanded.

> A TreeWidget would still be necessary because the AbstractTree is completely
> assumption-free, and doesn't even build it's own DOM nodes, while consumers
> may not care too much about so much customization (and just want to quickly
> insert labels in a tree). Therefore, my suggestion is to subclass
> AbstractTree for a quick&easy tree widget, while keeping the AbstractTree
> for more complex scenarios.

I am fine with this, if all the functionality is retained. For instance, I don't care about creating my own DOM nodes and just want to insert strings or urls into the tree, etc.

[0] http://dxr.mozilla.org/mozilla-central/source/browser/devtools/shared/test/browser_treeWidget_basic.js#104
(In reply to Girish Sharma [:Optimizer] from comment #2)
> 
> > The new AbstractTree class has a very different (flat) internal DOM
> > structure that automatically fixes all of the above problems. Customized
> > nodes are the foundation of each item. In the DOM, all items are children of
> > the same parent, so odd|even selectors can be used in CSS. Arrows and
> > indentation may be set up anywhere inside an item etc. etc.
> 
> This sounds good on the top but actually is an overhead when you simply want
> to use the tree as a source view (which is the majority use case for such a
> tree)
> 
> you have to create your own DOM node add just a string to it and then call
> the tree's add method.

I've said this a million times. You don't use the AbstractTree alone. You subclass your own TreeWidget with it, which does this for you. It's in the bug title, the documentation, and the last two paragraphs of the comment you're replying to ;)

> 
> True, but then if we are talking of performance, ATV's selection is heavier
> than TW's selection as no extra work to first insert the required DOM
> elements into the tree is needed in case of TW
> 

Agreed. But I fixed this last night, so this point is moot now. DOM nodes are inserted just once in the tree, which I assume the TreeWidget needs to do anyway for there to be a node to be selected in the first place! :) Also, now expanding/collapsing a node doesn't re-create the children every time.

> 
> But you still have to insert the DOM nodes which are not inserted. Managing
> that is a bit of overhead.
>  

Not anymore ;)

> That is being managed by DOM, right ? as in the addEventListener("focus")
> thingy.
> 
> Then to get any meta data associated by the node (see attachment in TW), I
> will have to query the tree myself (that method also does not exist btw)

Again, we're not talking about a finalized class here. The API is minimal now, and to fix the issue here is as simple as adding a one-line method to the prototype. Not sure why you're bringing up such trivialities like doing a

> get focusedItem() { return this.document.commandDispatcher.focusedElement.id };

> But still, you will have to add DOM nodes to the document. Which can take
> quite a while in case when a there are huge number of children to the
> expanding parent. 

Not really, since you're dealing with data sources directly in the tree before creating any nodes, you can simply walk the data source instead of the DOM if the nodes weren't created yet. That's the niceness of the current approach, you supply a data source (of whatever format you want) and a TreeView subclass implementation simply walks it however it wants.

> It like a tradeoff, do all the DOM insertions at initialization vs do it
> everytime a node is expanded.

Like I said, I fixed this last night, so this point is moot. DOM nodes are only inserted once.

As of right now, all operations in the AbstractTree are lighter and faster than the current TreeWidget implementation.
So let me get this straight. Now that ATV also inserts all the DOM elements once, (as compared to inserting them while expanding any parent node) the amount of DOM operations are almost similar for TW and ATV.

If I recall correctly, this was your main concern wrt Profiler UI where call stack can be huge.

So while the discussion continues, you keep on improving ATV (and friends) and TW's implementation being stagnant, there is no point comparing the two as you'll keep on fixing the missing things in ATV :).

(I am sad that this much development could have been done on top of TW instead)

Just a fun fact : Currently, feature wise, the only benefit ATV gives is odd|even background colors :)


(In reply to Victor Porof [:vporof][:vp] from comment #3) 

> > get focusedItem() { return this.document.commandDispatcher.focusedElement.id };

I was referring to the JS object meta data, not the id of the selected node. For instance, I want to attach a Set with a tree item and when that item is selected, I want to use that Set. With a DOM event listener for focus, I do get the id, but then I (or the implementation on top of ATV) will have to chain that logic itself.

> > But still, you will have to add DOM nodes to the document. Which can take
> > quite a while in case when a there are huge number of children to the
> > expanding parent. 
> 
> Not really, since you're dealing with data sources directly in the tree
> before creating any nodes, you can simply walk the data source instead of
> the DOM if the nodes weren't created yet. That's the niceness of the current
> approach, you supply a data source (of whatever format you want) and a
> TreeView subclass implementation simply walks it however it wants.
> 

What I actually meant here was with reference to the following (now moot) behavior

Construct following tree :
A - B - C
A - B - D
A - B - E
A - F - G
A - F - H
A - F - I
A - F - I - J

Visually select A - F - I - J node in the tree

Now here, if A was not expanded, you would have had to first insert J in the DOM tree, then I, H, G , then F and B

> As of right now, all operations in the AbstractTree are lighter and faster
> than the current TreeWidget implementation.

I still don't think that comparing the code implementations will give a(n) ( anywhere near ) correct performance difference.

Again, keeping the comparison discussion asides I have no objection in using whatever implementation.
I just don't have time to (almost) rewrite the TW on top of ATV right now.
(In reply to Girish Sharma [:Optimizer] from comment #4)
> So let me get this straight. Now that ATV also inserts all the DOM elements
> once, (as compared to inserting them while expanding any parent node) the
> amount of DOM operations are almost similar for TW and ATV.
> 

You misread me. I said 'once' to mean 'one time', on expansion. Nothing else changes from the previous implementation, nodes are still inserted lazily, except the fact that nodes are now hidden instead of removed on collapse.

> If I recall correctly, this was your main concern wrt Profiler UI where call
> stack can be huge.
> 

It still is.

> So while the discussion continues, you keep on improving ATV (and friends)
> and TW's implementation being stagnant, there is no point comparing the two
> as you'll keep on fixing the missing things in ATV :).
> 

Not really what's going on here.

> (I am sad that this much development could have been done on top of TW
> instead)
> 

It couldn't have. Do you not think I tried? :)

> Just a fun fact : Currently, feature wise, the only benefit ATV gives is
> odd|even background colors :)
> 

That's quite an understatement.

> 
> Now here, if A was not expanded, you would have had to first insert J in the
> DOM tree, then I, H, G , then F and B
> 

You don't seem to understand that you're dealing with data sources in this case, not dom nodes. You just need to find J in an array (or object, or Map, or Set, or whatever you like), and then build the tree upwards.

> I just don't have time to (almost) rewrite the TW on top of ATV right now.

This bug doesn't seem to be assigned to you, and I've never implied that it's you who should be doing this. If you want to, by all means!, but if not, then that's perfectly ok.
(In reply to Girish Sharma [:Optimizer] from comment #4)
> 
> I was referring to the JS object meta data, not the id of the selected node.
> For instance, I want to attach a Set with a tree item and when that item is
> selected, I want to use that Set. With a DOM event listener for focus, I do
> get the id, but then I (or the implementation on top of ATV) will have to
> chain that logic itself.

Big deal, just add a WeakMap of nodes-to-metadata.
(In reply to Victor Porof [:vporof][:vp] from comment #5)
> 
> That's quite an understatement.
>

I said feature wise :)
 
> > 
> > Now here, if A was not expanded, you would have had to first insert J in the
> > DOM tree, then I, H, G , then F and B
> > 
> 
> You don't seem to understand that you're dealing with data sources in this
> case, not dom nodes. You just need to find J in an array (or object, or Map,
> or Set, or whatever you like), and then build the tree upwards.

Please hear me out . I actually was demoing the exact same thing. You get hold of J using whatever data structure you have (BTW, that data structure is still a tree so a similar search algorithm to TW is needed). And then build the tree upwards to the first expanded parent node. This building of the graph includes addition of DOM nodes which are not present in the tree, right ?
So I still stand corrected that nodes corresponding to J, I, H, G, F and B have to be added just to visually select A - F - I - J node.

Now here, for a 4th level node in the tree, 6 nodes were inserted. For a profiler call stack, and a 8th level node with much more branching of nodes can easily lead to 50+ node insertion just to show that node.

This use case will quite often come up when a person is hovering the histogram on the top and you need to show the call associated to that histogram entry. Now, that call node can be sitting very deeply inside the tree and thus the use would possibly see a jank caused by insertion and expansion of DOM nodes.

Now, if there is no visual jank , even in super highly branched call stacks and deep level node selections, then it simply means that the browser is super fast wrt DOM interactions and our whole discussion of tree interaction performance based on the code implementation was irrelevant :)
Product: Firefox → DevTools
Severity: normal → S3
Attachment #9384416 - Attachment is obsolete: true
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: