320393 - Tree list items should have accessible RELATION_NODE_OF relation

Status: RESOLVED FIXED

(Firefox :: Disability Access, defect)

Description

[Willie Walker]

User-Agent:       Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9a1) Gecko/20051214 Firefox/1.6a1
Build Identifier: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9a1) Gecko/20051214 Firefox/1.6a1

Tree list items should have an accesisble RELATION_NODE_OF relation set.  The ones in the history pane do not have this relation. 

Reproducible: Always

Steps to Reproduce:
1) Run the attached test case in an xterm
2) Give focus to an element in the history pane
3) Observe the output in the xterm

Actual Results:  
1) Run this tool in an xterm
2) Give focus to an element in the history pane
3) Observe the output in the xterm


Expected Results:  
The list items in the history pane should have the
RELATION_NODE_CHILD_OF relation set properly.

Comment 1

[Willie Walker]

Attachment: Standalone test case

Comment 2

[Nian Liu(n/a in a long time)]

Attachment: patch

Comment 3

[Nian Liu(n/a in a long time)]

Attachment: patch with cvs -u

Comment 4

[Aaron Leventhal]

One question -- why is this needed? Isn't there an implicit relationship of parent/children in a tree of objects?

-    PRUint32 relationType[2] = {nsIAccessible::RELATION_LABELLED_BY,
-                                nsIAccessible::RELATION_LABEL_FOR};
+    PRUint32 relationType[3] = {nsIAccessible::RELATION_LABELLED_BY,
+                                nsIAccessible::RELATION_LABEL_FOR,
+                                nsIAccessible::RELATION_NODE_CHILD_OF};
 
-    for (PRUint32 i = 0; i <= 1; i++) { 
+    for (PRUint32 i = 0; i <= 2; i++) { 

Can you fix this to something like:
+    PRUint32 relationType[] = {nsIAccessible::RELATION_LABELLED_BY,
+                               nsIAccessible::RELATION_LABEL_FOR,
+                               nsIAccessible::RELATION_NODE_CHILD_OF,
                                0}; // Magic value to indicate end of list

and then change the loop so that the number doesn't have to be updated each time the code changes.

Also, let's get rid of the extra whitespace change.

Comment 5

[Nian Liu(n/a in a long time)]

Attachment: patchv2

1)0 is used by RELATION_NUL, so I use 0xff as magic value^_^
2)remove extra space
3)in my understanding, relationType is the only place to define element relationship. that's the reason why I add nsIAccessible::RELATION_NODE_CHILD_OF there. correct me if I'm wrong.

Comment 6

[Aaron Leventhal]

> 3)in my understanding, relationType is the only place to define element
> relationship. that's the reason why I add nsIAccessible::RELATION_NODE_CHILD_OF
> there. correct me if I'm wrong.
There is an implicent set of relationships in the object tree
for example, a groupbox with a button inside it -- the button may be a first child of the groupbox, and thus the groupbox is the parent of the button
I don't think this relation is ever necessary.

Comment 7

[Peter Korn]

Aaron - this relation came about because in GNOME/GTK+ Treeviews, there was no heirarchy discernable, so you couldn't figure out at what level in the tree a particular node was (you can see this with at-poke and a GTK+ tree).  If the situation is the same in Mozilla - all nodes have the same parent but different levels, then we need this relation.  If not, we don't.  We don't use this relation in Java's JTree because there is a full parent/child heirarchy for those nodes.

Comment 8

[Aaron Leventhal]

Comment on attachment 209667 [details] [diff] [review]
patchv2

Okay, good. Mozilla has tree views that show hierarchy but are a flat list of objects as well. However, that's not what this patch seems to fix. It's going to the DOM parent.

Comment 9

[Willie Walker]

From an AT point of view, can you provide an algorithm that will allow the AT to reliably determine the node level depth in the face of these two models?  

For example, assume some object just got focus.  I guess I would assume that, in the event an object does not have a RELATION_NODE_CHILD_OF relation, the AT will typically have to do some roundtripping and look upwards in the hierarchy to see if it ultimately has an ancestor that is a tree.  I think the main reason for this is that Accessibles cannot have multiple roles, thus giving us a clue that something is *both* a tree node and a {label,checkbox,etc.}.  If the rule were that all tree items would have a RELATION_NODE_CHILD_OF, we have this clue and the AT logic could be greatly simplified.

Comment 10

[Bill Haneman]

The issue/reason for this in gtk+ is not a limitation of the gtk+ implementation, as Peter suggests in comment #7, but rather the fact that for table-like trees (i.e trees whose nodes have multiple columns of info presented to the user, or whose nodes are otherwise composite), there is an inherent conflict between "containership" in the sense of being composite, and "containership" in the sense of being a parent node of a treelike structure.

For trees whose leaf nodes are discrete objects, a pure hierarchy works fine, and no NODE_CHILD_OF relation is needed.  However, for more tabular objects (sometimes referred to as "tree-tables"), the pure hierarchical model breaks down, and we must use the Table interface instead.  The "cells" within a Table are not normally explicitly exposed in a hierarchical view, which is why they need the NODE_CHILD_OF relation to link them bidirectionally back to the hosting Table instance.  This also explains why there is no reciprocal NODE_PARENT_OF relationship needed, since all NODE_CHILD_OF objects are normally obtained via an interface query on the containing Table instance.

Comment 11

[Nian Liu(n/a in a long time)]

is it possible to build the parent-child relationship among tree, treecol and treeitem as shown in DOM inspector?

Comment 12

[Aaron Leventhal]

(In reply to comment #10)
> For trees whose leaf nodes are discrete objects, a pure hierarchy works fine,
> and no NODE_CHILD_OF relation is needed.  However, for more tabular objects
> (sometimes referred to as "tree-tables"), the pure hierarchical model breaks
> down, and we must use the Table interface instead.  

Does the RELATION_NODE_OF point the table cells to a tree item or to the tree itself?
In that case how do we expose the hierarchy for the tree items?
If there are no cells and each tree item is just a single item, should we use parent/child to expose that instead of RELATION_NODE_OF?
Is there an example of all of this working -- does the GTK tree view do all of this correctly?

Comment 13

[Aaron Leventhal]

Screenshot for discussion:
http://xkr47.outerspace.dyndns.org/tools/thunderbird.png

I'm not sure where the RELATION_NODE_OF relations are supposed to point from and to.

Comment 14

[parente]

Following the gtk way of doing things...

The first column having a selectable accessible in the selected row should have a RELATION_NODE_OF target pointing to the first column having a selectable accessible in the row immediately above the selected row (the one with the subject [ANNOUNCE] patch2pom conversion script v1). That accessible should have a RELATION_NODE_OF target pointing to the tree table accessible.

Clarification: By first column having a selectable accessible I mean in gtk trees, columns that have icons and text aren't always individually selectable. In that case, the two accessibles (one for icon and one for text) are subchildren of a node that is selectable. That node has the NODE_OF_RELATION.

Very hard to describe this in words...

Comment 15

[parente]

In addition to having the accessible relation to determine the parent accesible, what about using atk/at-spi object attributes to expose simple information often used by ATs? For instance, in MSAA, the description field was used to say "L3, 5 of 7 with 12". We can use object attribute name/value pairs to say:

tree_level=3
tree_peer_index=5
tree_peer_count=7
tree_children=12

This would save the AT a massive number of cross process calls to determine all these counts (i.e. instead of following relations up to the tree root to get the level count, counting table rows between one item and the next one at the same level to get number of children, etc.)

Comment 16

[Aaron Leventhal]

And to clarify how RELATION_NODE_CHILD_OF should be used:

The first ROLE_TREE_ITEM or ROLE_CELL in every row should point to either:
1) the first item in the parent row 
or
2) the tree itself.

Correct?

Because tree items and cells are all siblings of each other in the accessible tree, right now the proposed patch appears only to do #2. This is because the GetParent() call should always return the ROLE_TREE.

Nian, I think you'll need to write some code on the nsXULTreeAccessible class to resolve the relation. That's where that code belongs.

Comment 17

[Nian Liu(n/a in a long time)]

considered a tree structure as below

A1 A2
   A11 A12
B1 B2

and we have a flat structure which all cells are sibilings as A1, A2, A11, A12, B1, B2

we only set RELATION_NODE_CHILD_OF to A1 as tree, A11 as A1, B1 as tree. Is that enough for AT to build the right hierarchical model?
(In reply to comment #16)
> And to clarify how RELATION_NODE_CHILD_OF should be used:
> 
> The first ROLE_TREE_ITEM or ROLE_CELL in every row should point to either:
> 1) the first item in the parent row 
> or
> 2) the tree itself.
> 
> Correct?
> 
> Because tree items and cells are all siblings of each other in the accessible
> tree, right now the proposed patch appears only to do #2. This is because the
> GetParent() call should always return the ROLE_TREE.
> 
> Nian, I think you'll need to write some code on the nsXULTreeAccessible class
> to resolve the relation. That's where that code belongs.
> 

Comment 18

[Nian Liu(n/a in a long time)]

(In reply to comment #16)
Aaron,

I think we only need to build RELATION_NODE_CHILD_OF for 
  treeitem ROLE_OUTLINEITEM which columns > 1 and
  treeitem ROLE_CELL which columns =1
as you described below. 
> And to clarify how RELATION_NODE_CHILD_OF should be used:
> 
> The first ROLE_TREE_ITEM or ROLE_CELL in every row should point to either:
> 1) the first item in the parent row 
> or
> 2) the tree itself.
> 
> Correct?
> 
> Because tree items and cells are all siblings of each other in the accessible
> tree, right now the proposed patch appears only to do #2. This is because the
> GetParent() call should always return the ROLE_TREE.
> 
> Nian, I think you'll need to write some code on the nsXULTreeAccessible class
> to resolve the relation. That's where that code belongs.
> 

Comment 19

[Aaron Leventhal]

(In reply to comment #17)
> considered a tree structure as below
> A1 A2
>    A11 A12
> B1 B2
...
> we only set RELATION_NODE_CHILD_OF to A1 as tree, A11 as A1, B1 as tree.
Looks right to me.

(In reply to comment #18)
> I think we only need to build RELATION_NODE_CHILD_OF for 
>   treeitem ROLE_OUTLINEITEM which columns > 1 and
>   treeitem ROLE_CELL which columns =1
> as you described below. 
The ROLE_CELL part looks correct. However, for ROLE_OUTLINEITEM I thought that meant that there is only 1 column.

Comment 20

[Nian Liu(n/a in a long time)]

right. ROLE_CELL for multiple column, and ROLE_OUTLINEITEM for one column. sorry for the wrong typing
(In reply to comment #19)
> (In reply to comment #17)
> > considered a tree structure as below
> > A1 A2
> >    A11 A12
> > B1 B2
> ...
> > we only set RELATION_NODE_CHILD_OF to A1 as tree, A11 as A1, B1 as tree.
> Looks right to me.
> 
> (In reply to comment #18)
> > I think we only need to build RELATION_NODE_CHILD_OF for 
> >   treeitem ROLE_OUTLINEITEM which columns > 1 and
> >   treeitem ROLE_CELL which columns =1
> > as you described below. 
> The ROLE_CELL part looks correct. However, for ROLE_OUTLINEITEM I thought that
> meant that there is only 1 column.
> 

Comment 21

[Nian Liu(n/a in a long time)]

Attachment: patch to show rough idea

patch to show the rough solution.

if that way is acceptable, i'll refine it.

things makes me feel not good:
1)NS_STATIC_CAST. to make it QIable, we need add new api. maybe in nsIAccessible?
2)atk only way. is that possible that we sync MSAA and new atk in the future?

Comment 22

[Nian Liu(n/a in a long time)]

oops,
treeitemAccessible->SetRelationNode should use node get from
GetCacheEntry(*mAccessNodeCache, (void*)(parentIndex * kMaxTreeColumns), getter_AddRefs(accessNode))
(In reply to comment #21)
> Created an attachment (id=222016) [edit]
> patch to show rough idea
> 
> patch to show the rough solution.
> 
> if that way is acceptable, i'll refine it.
> 
> things makes me feel not good:
> 1)NS_STATIC_CAST. to make it QIable, we need add new api. maybe in
> nsIAccessible?
> 2)atk only way. is that possible that we sync MSAA and new atk in the future?
> 

Comment 23

[Aaron Leventhal]

Comment on attachment 222016 [details] [diff] [review]
patch to show rough idea

* Create nsXULTreeitemAccessible::GetAccessibleRelated to override nsAccessible::GetAccessibleRelated. Then just call up to the nsAccessible version of the method if RELATION_NODE_CHILD_OF is not the relation being asked for.

* Make sure you use COM/interfaces, not static_cast. I'm not even sure you'll need all that stuff if you use the method overriding recommended above. If you really need to add a new interface, that is okay just try to make it generic/abstract so we can use it for other things later.

* It's okay to keep the code in the cross platform area -- eventually the MSAA and ATK tree implementations should become the same.

* Minor not: in your loop don't use the 0xff magic value for the end of the array, but use NS_ARRAY_LENGTH instead.

Comment 24

[Nian Liu(n/a in a long time)]

Attachment: patch

Comment 25

[Aaron Leventhal]

Comment on attachment 222141 [details] [diff] [review]
patch

Getting closer.

Rather than cache the related node via SetRelatedNode I would rather you put that logic in GetAccessibleRelated(). Just recalculate the parent each time that is called. The reason is that the tree changes so fast and we don't invalidate the cache every time it does. That would be really expensive. 

Also, there is one extra whitespace change that you can remove.

Comment 26

[Nian Liu(n/a in a long time)]

Attachment: patch

Comment 27

[Aaron Leventhal]

Comment on attachment 222307 [details] [diff] [review]
patch

Make sure to start out GetAccessibleRelated with *aRelated = nsnull. It's good practice to initially set the out paramaters on the first line. If anyone ever changes the method there is no risk of dangling pointers.

It is legal to do this, but it is your choice:
NS_IF_ADDREF(*aRelated = mParent);

Comment 28

[Nian Liu(n/a in a long time)]

Attachment: patch addressing aaron's comments

Comment 29

[Nian Liu(n/a in a long time)]

roc, please^_^

Comment 30

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

Comment on attachment 222445 [details] [diff] [review]
patch addressing aaron's comments

+  *aRelated == nsnull;

I think you want "= nsnull;", please fix.

Comment 31

[Ginn Chen]

Checking in nsXULTreeAccessible.cpp;
/cvsroot/mozilla/accessible/src/xul/nsXULTreeAccessible.cpp,v  <--  nsXULTreeAccessible.cpp
new revision: 1.37; previous revision: 1.36
done
Checking in nsXULTreeAccessible.h;
/cvsroot/mozilla/accessible/src/xul/nsXULTreeAccessible.h,v  <--  nsXULTreeAccessible.h
new revision: 1.18; previous revision: 1.17
done

Comment 32

[Ginn Chen]

Checking in src/atk/nsAccessibleWrap.cpp;
/cvsroot/mozilla/accessible/src/atk/nsAccessibleWrap.cpp,v  <--  nsAccessibleWrap.cpp
new revision: 1.34; previous revision: 1.33
done

Comment 33

[Ginn Chen]

Checking in src/atk/nsAccessibleWrap.cpp;
/cvsroot/mozilla/accessible/src/atk/nsAccessibleWrap.cpp,v  <--  nsAccessibleWrap.cpp
new revision: 1.25.4.4; previous revision: 1.25.4.3
done
Checking in src/xul/nsXULTreeAccessible.cpp;
/cvsroot/mozilla/accessible/src/xul/nsXULTreeAccessible.cpp,v  <--  nsXULTreeAccessible.cpp
new revision: 1.33.2.2; previous revision: 1.33.2.1
done
Checking in src/xul/nsXULTreeAccessible.h;
/cvsroot/mozilla/accessible/src/xul/nsXULTreeAccessible.h,v  <--  nsXULTreeAccessible.h
new revision: 1.17.2.1; previous revision: 1.17
done