573719 - IAccessible2 - Recursively finding the object containing the caret is painfully slow.

Status: RESOLVED FIXED

(Core :: Disability Access APIs, defect)

Description

[RaZiel]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2.3) Gecko/20100401 Firefox/3.6.3 (.NET CLR 3.5.30729)
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2.3) Gecko/20100401 Firefox/3.6.3 (.NET CLR 3.5.30729)

http://www.inetword.com/ is probably the worst case scenario.
For complex sites like this one, the accessibility tree is enormous. Makes the effort to find the object containing the caret a resource- and time-consuming operation.
Other sites like; http://ckeditor.com/demo and http://tinymce.moxiecode.com/examples/full.php is less complex, but is still complex enough to make it a time consuming operation.

This relates to: https://bugzilla.mozilla.org/show_bug.cgi?id=573714
Both ways have their problems. I really hope IAccessible2 will change, so it makes it easier to get the object containing the caret.


Reproducible: Always

Steps to Reproduce:
1.Place caret within a paragraph.
2.Get the focused IAccessible object.
3.Traverse it's children to find the IAccessible2 object containing the caret.

Actual Results:  
Time consuming operation.

Expected Results:  
Less time consuming operation.

Comment 1

[alexander :surkov (:asurkov)]

it's sort of o(n^2) crawling through the tree: we get accessible with caret, go up to object the caret was asked for, then caller goes down to child, request caret for it and etc.

Comment 2

[David Bolter [:davidb] (NeedInfo me for attention)]

So the IA2 specification requires the client to drill down to get the most granular IA2 object containing the caret. I'm not very familiar with our caret code, but I wonder if we could just supply this a lot quicker, through some additional (prototype/pioneer) API? A method to get the child with the caret.

Comment 3

[alexander :surkov (:asurkov)]

What do you mean under prototype/pioneer API?

Comment 4

[alexander :surkov (:asurkov)]

There is two ways as I said on irc and ideally we should follow both.
1) Request IA2 change for this. It can be a method defined on IAccessibleText like

[propget] HRESULT accessibleWithCaret (
     [out, retval] IUnknown **accessible);

what returns deepest text accessible containing the caret if the caret in the subtree of the object the method is called on.

The problem is IA2 has big amount of pending changes and obviously all changes should be added at once to avoid frequent interface changes. So this approach should take significant time and I don't think it can be in timeframe of Firefox4.

2. Improve performance. I don't think there's lot of options here. All we can do (and should) is to provide quick text offsets calculation. In this case time is spent for tree traversal from up to down (client side) and from down to up (server side - probably we can do something here as well).

Comment 5

[David Bolter [:davidb] (NeedInfo me for attention)]

(In reply to comment #4)
> 1) Request IA2 change for this. It can be a method defined on IAccessibleText
> like
> 
> [propget] HRESULT accessibleWithCaret (
>      [out, retval] IUnknown **accessible);
> 
> what returns deepest text accessible containing the caret if the caret in the
> subtree of the object the method is called on.

Right. Could we do this performantly?

Comment 6

[alexander :surkov (:asurkov)]

Yes

Comment 7

[alexander :surkov (:asurkov)]

(In reply to comment #6)
> Yes

Client don't need to go from up to down in the tree and we don't need to calculate text offsets. If the method is called on document accessible then this method can be really quick.

Comment 8

[David Bolter [:davidb] (NeedInfo me for attention)]

Great. That's what I wanted to be clear about thanks. Want to start the IA2 thread?

Comment 9

[alexander :surkov (:asurkov)]

(In reply to comment #8)
> Want to start the IA2 thread?

Not this time I think.

Comment 10

[alexander :surkov (:asurkov)]

bug 567553 might be related and help here.

Comment 11

[David Bolter [:davidb] (NeedInfo me for attention)]

Let's try to make this fast for FF4.

Comment 12

[RaZiel]

(In reply to comment #11)
> Let's try to make this fast for FF4.

Oh, I would really really appreciate that :)

Comment 13

[David Bolter [:davidb] (NeedInfo me for attention)]

Alexander if we aren't going to do #1 in comment 4 we should probably close this bug and just make text offsets fast correct?

Comment 14

[alexander :surkov (:asurkov)]

(In reply to David Bolter [:davidb] from comment #13)
> Alexander if we aren't going to do #1 in comment 4 we should probably close
> this bug and just make text offsets fast correct?

if then no/yes

Comment 15

[David Bolter [:davidb] (NeedInfo me for attention)]

Do you have a preference?

Jamie what do you think about #1 in comment 4?

Comment 16

[alexander :surkov (:asurkov)]

(In reply to David Bolter [:davidb] from comment #15)
> Do you have a preference?

both of them should be fixed, it's not about preferences.

Comment 17

[David Bolter [:davidb] (NeedInfo me for attention)]

OK that's clearer thanks!

Comment 18

[James Teh [:Jamie]]

(In reply to David Bolter [:davidb] from comment #15)
> Jamie what do you think about #1 in comment 4?
It does make sense. However, I'm not sure we can make much use of it in NVDA. When a control gets focus, we query for selection, not caret. If the selection is collapsed, there's no selection and it's a caret. If it's not collapsed, we report the selection accordingly. Unfortunately, having a way to retrieve the accessible with caret doesn't really help selection much, so we probably won't end up using it much in NVDA.

Comment 19

[James Teh [:Jamie]]

I think we're done here.