606924 - create complete accessible tree

Status: RESOLVED FIXED

(Core :: Disability Access APIs, defect)

Description

[alexander :surkov (:asurkov)]

We should create accessible tree when notified that new content has been inserted. That allows us to not traverse up the DOM tree looking for cached accessibles and then go down and cache children. So getting slower on content insertion notification handling, we get faster with accessible tree operations in general.

On the another hand it allows us to process the tree and cache necessary information about accessible tree. As side node this allows us to fix bug 573469.

Comment 1

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

Note to self: one issue with computing the tree lazily (on demand), is that we can miss important relations. Talking with Alexander yesterday, we are thinking that AT tend to walk the whole tree anyways (thereby forcing us to create it).

Comment 2

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

Note to self: we might have to use AT sniffing here if the upfront perf cost is too high.

Comment 3

[alexander :surkov (:asurkov)]

I think we need to fix it since this may cause the accessible tree creation at wrong time. We could lie to AT and do not return children (pend their creation and fire mutation events after that) but it sounds tricky and should be expensive.

Comment 4

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

Why should this block?

Comment 5

[alexander :surkov (:asurkov)]

(In reply to comment #4)
> Why should this block?

Doesn't the comment #3 make things clear?

Comment 6

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

As per our discussion, this bug is another one of our bugs related to the accessible tree being incorrect.

Comment 7

[alexander :surkov (:asurkov)]

Attachment: part1v1: create tree on content insertion

Comment 8

[alexander :surkov (:asurkov)]

(In reply to comment #7)
> Created attachment 502714 [details] [diff] [review]
> patch1v1: create tree on content insertion

try server build - http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/[e-mail]-1122c6f1b869

Comment 9

[alexander :surkov (:asurkov)]

Attachment: part1v2: create tree on content insertion [landed 2011-01-20]

Comment 10

[alexander :surkov (:asurkov)]

Attachment: part2v1: create initial tree

Comment 11

[alexander :surkov (:asurkov)]

Comment on attachment 503406 [details] [diff] [review]
part2v1: create initial tree

that's not exactly what we need

Comment 12

[alexander :surkov (:asurkov)]

Comment on attachment 503406 [details] [diff] [review]
part2v1: create initial tree

though that's not exactly what we want but we want this, we need to create initial accessible tree for documents that were loaded before a11y was started. We can do that at safe time only, so that if accessible creation is safe when document is created then anyways it doesn't make sense to do that because we can't rely on this behavior.

Comment 13

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

Could you rephrase comment 12?

Comment 14

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

Comment on attachment 503103 [details] [diff] [review]
part1v2: create tree on content insertion [landed 2011-01-20]

r=me conditional on Fer's review and:

>@@ -1949,17 +1949,21 @@ nsDocAccessible::UpdateTreeInternal(nsAc

>-    if (!aIsInsert) {
>+    if (aIsInsert) {
>+      // Create accessible tree for shown accessible.
>+      CacheChildrenInSubtree(accessible);

This is going to end up calling ensure children for every ContentRangeInserted. I hope it doesn't bite our perf badly?


>+++ b/accessible/tests/mochitest/test_nsIAccessibleHyperText.html

Nit: forgot to reference this bug?

Comment 15

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

Comment on attachment 503406 [details] [diff] [review]
part2v1: create initial tree

> NotificationController::NotificationController(nsDocAccessible* aDocument,
>                                                nsIPresShell* aPresShell) :
>   mObservingState(eNotObservingRefresh), mDocument(aDocument),
>-  mPresShell(aPresShell)
>+  mPresShell(aPresShell), mTreeConstructedState(eTreeConstructionPending)
> {
>+  // Schedule initial accessible tree construction.
>+  ScheduleProcessing();

I've lost track of where this method gets introduced (not in mxr).
 
>+  // Initial accessible tree construction.
>+  if (mTreeConstructedState == eTreeConstructionPending) {
>+    mTreeConstructedState = eTreeConstructed;
>+    mDocument->CacheChildrenInSubtree(mDocument);
>+
>+    // Prune any pending content insertions.
>+    mContentInsertions.Clear();
>+  }

This looks correct.

Comment 16

[alexander :surkov (:asurkov)]

(In reply to comment #13)
> Could you rephrase comment 12?

1) We need to create an accessible tree for document that was created before a11y is started
2) It's ok to do via refresh observer (sometimes we could do it early but we can't be guaranteed we can do that always, that adds ambiguity and I want to avoid it).

Comment 17

[alexander :surkov (:asurkov)]

(In reply to comment #14)

> This is going to end up calling ensure children for every ContentRangeInserted.
> I hope it doesn't bite our perf badly?

It doesn't when screen reader is running. When this bug is finished then we should get good perf improvement. It's hard to test in not screen reader case. That depends entirely on the page. It shouldn't regress us on dynamic pages or pages having lot of form controls that require the user be active. It may regress on static pages that contains readable content only but I don't think it'll be noticeable regression even on War and Peace of Lev Tolstoy since I don't think the page will have large hierarchy.

> >+++ b/accessible/tests/mochitest/test_nsIAccessibleHyperText.html
> 
> Nit: forgot to reference this bug?

sounds so, thx.

Comment 18

[alexander :surkov (:asurkov)]

(In reply to comment #15)

> >+  // Schedule initial accessible tree construction.
> >+  ScheduleProcessing();
> 
> I've lost track of where this method gets introduced (not in mxr).

bug 498015

Comment 19

[alexander :surkov (:asurkov)]

Attachment: part3v1: hanging document concept

when the child document is created before parent document (for example, when a11y is started after parent DOM document is created) then binding the child document to tree triggers early tree creation for parent document, it may happen at unsafe time for tree creation.

Comment 20

[alexander :surkov (:asurkov)]

(In reply to comment #19)
> Created attachment 503784 [details] [diff] [review]
> patch1v3: hanging document concept

try server build - http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/[e-mail]-c0d1b34ee26c

Marco, please run with this build for a while when it's ready.

Comment 21

[alexander :surkov (:asurkov)]

Comment on attachment 503784 [details] [diff] [review]
part3v1: hanging document concept

random failures (http://stage.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/[e-mail]-c0d1b34ee26c/try-lnx/tryserver_fedora_test-mochitest-other-build846.txt.gz): can't get a document accessible, needs further investigations

Comment 22

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

Comment on attachment 503406 [details] [diff] [review]
part2v1: create initial tree

r=me thanks.

(In reply to comment #18)
> (In reply to comment #15)
> 
> > >+  // Schedule initial accessible tree construction.
> > >+  ScheduleProcessing();
> > 
> > I've lost track of where this method gets introduced (not in mxr).
> 
> bug 498015

Ah right, it basically sets up the refresh observer.

Comment 23

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

(In reply to comment #17)
> (In reply to comment #14)
> 
> > This is going to end up calling ensure children for every ContentRangeInserted.
> > I hope it doesn't bite our perf badly?
> 
> It doesn't when screen reader is running. When this bug is finished then we
> should get good perf improvement. It's hard to test in not screen reader case.
> That depends entirely on the page. It shouldn't regress us on dynamic pages or
> pages having lot of form controls that require the user be active. It may
> regress on static pages that contains readable content only but I don't think
> it'll be noticeable regression even on War and Peace of Lev Tolstoy since I
> don't think the page will have large hierarchy.

OK, and we can optimize later if necessary,.

Comment 24

[alexander :surkov (:asurkov)]

Attachment: part3v2: hanging document concept

Comment 25

[alexander :surkov (:asurkov)]

(In reply to comment #24)
> Created attachment 504106 [details] [diff] [review]
> part3v2: hanging document concept

try server build - http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/[e-mail]-eefbb9468729

Comment 26

[alexander :surkov (:asurkov)]

Attachment: part4v1: deal with cached accessible tree only

Comment 27

[alexander :surkov (:asurkov)]

Attachment: part5v1: rename GetCachedAccessible

Comment 28

[alexander :surkov (:asurkov)]

Attachment: part6v1: move GetAccessibleOrContainer

move GetAccessibleOrContainer to document accessible making it optimal

Comment 29

[alexander :surkov (:asurkov)]

Attachment: part3v3: hanging document concept [landed 2011-01-25]

fix intermittent mochitest failures

Comment 30

[Marco Zehe (:MarcoZ)]

I ran with the latest try-server from this bug over the weekend and found absolutely nothing wrong with it. On the contrary, this adds more stability to the document loading and others, in my subjective view, compared to the try-server build from bug 498015.

Comment 31

[alexander :surkov (:asurkov)]

Thanks, Marco! 

Here will be a build that contains all patches - http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/[e-mail]-41a9659498b3

Comment 32

[alexander :surkov (:asurkov)]

(In reply to comment #31)

> Here will be a build that contains all patches -
> http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/[e-mail]-41a9659498b3

intermittent mochitest failures

Comment 33

[alexander :surkov (:asurkov)]

Attachment: part4v2: deal with cached accessible tree only [landed 2011-01-26]

get back null check to GetContainerAccessible

Comment 34

[alexander :surkov (:asurkov)]

(In reply to comment #32)
> (In reply to comment #31)
> 
> > Here will be a build that contains all patches -
> > http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/[e-mail]-41a9659498b3
> 
> intermittent mochitest failures

new try server build, should be ok - http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/[e-mail]-a5951167079a

Comment 35

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

Comment on attachment 504373 [details] [diff] [review]
part3v3: hanging document concept [landed 2011-01-25]

r=me. I like this idea.

>+  // Bind hanging child documents.
>+  PRUint32 childDocCount = mHangingChildDocuments.Length();
>+  for (PRUint32 idx = 0; idx < childDocCount; idx++) {
>+    nsDocAccessible* childDoc = mHangingChildDocuments[idx];
>+
>+    nsIContent* ownerContent = mDocument->GetDocumentNode()->
>+      FindContentForSubDocument(childDoc->GetDocumentNode());

Note mDocument->GetDocumentNode === mDocument right? (If you want to leave it in for readability that's fine since the compiler should fix it).

Comment 36

[alexander :surkov (:asurkov)]

(In reply to comment #35)

> >+    nsIContent* ownerContent = mDocument->GetDocumentNode()->
> >+      FindContentForSubDocument(childDoc->GetDocumentNode());
> 
> Note mDocument->GetDocumentNode === mDocument right?

no

Comment 37

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

(In reply to comment #36)
> (In reply to comment #35)
> 
> > >+    nsIContent* ownerContent = mDocument->GetDocumentNode()->
> > >+      FindContentForSubDocument(childDoc->GetDocumentNode());
> > 
> > Note mDocument->GetDocumentNode === mDocument right?
> 
> no

Did you change GetDocumentNode somewhere?

Comment 38

[alexander :surkov (:asurkov)]

I don't get a question. GetDocumentNode is nsIDocument, mDocument is nsDocAccessible.

Comment 39

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

(In reply to comment #38)
> I don't get a question. GetDocumentNode is nsIDocument, mDocument is
> nsDocAccessible.

Thank you.

Comment 40

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

(In reply to comment #34)
> new try server build, should be ok -
> http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/[e-mail]-a5951167079a

Using NVDA 2010.2:
* When I launch this build while NVDA is running, things work well - nice!
* I still encounter problems when first visiting a page. Arrowing actually scrolls the document. Tabbing away and back (as per Marco) helps, as does reloading the virtual buffer (ins+f5).

Comment 41

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

Sigh sorry, for the second bullet I meant to add "When launching NVDA after FF".

Comment 42

[alexander :surkov (:asurkov)]

Attachment: part2v2: create initial tree [landed 2011-01-23]

ignore content inserted notifications when they happen rather than coalesce them to ignore them later

Comment 43

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

Comment on attachment 504659 [details] [diff] [review]
part2v2: create initial tree [landed 2011-01-23]

r=me. Comment nits:

> NotificationController::ScheduleContentInsertion(nsAccessible* aContainer,
>                                                  nsIContent* aStartChildNode,
>                                                  nsIContent* aEndChildNode)
> {
>+  // Ignore content insertions until we constructed accessible tree.

Nit: ... until we have constructed ...

>+  if (mTreeConstructedState == eTreeConstructionPending)
>+    return;

Good.


>   /**
>+   * Indicate whether initial construction of the document's accessible tree
>+   * performed or pending. When the document accessible is created then
>+   * we construct its initial accessible tree.
>+   */

Nit: has been performed, or is pending.

Comment 44

[Fernando Herrera]

Comment on attachment 503103 [details] [diff] [review]
part1v2: create tree on content insertion [landed 2011-01-20]

r=me

Comment 45

[Marco Zehe (:MarcoZ)]

(In reply to comment #34)
> new try server build, should be ok -
> http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/[e-mail]-a5951167079a

This one crashes for me reproducibly on pages like http://www.amazon.de. Other pages like http://www.google.com are OK.

Comment 46

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

(In reply to comment #45)
> (In reply to comment #34)
> > new try server build, should be ok -
> > http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/[e-mail]-a5951167079a
> 
> This one crashes for me reproducibly on pages like http://www.amazon.de. Other
> pages like http://www.google.com are OK.

Is it crashing at Role()?

Comment 47

[Marco Zehe (:MarcoZ)]

I don't know. It crashes with NVDA loaded, and the release build, not the debug one, can't use that. But should be easily reproducible.

Comment 48

[alexander :surkov (:asurkov)]

That build is out of date a bit. I'll provide a new one.

Comment 49

[alexander :surkov (:asurkov)]

"part1: create tree on content insertion" is landed on 2.0 beta10 - http://hg.mozilla.org/mozilla-central/rev/d5e9eddf4acd

Comment 50

[alexander :surkov (:asurkov)]

try server build for all patches based on trunk will be here - http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/[e-mail]-9514d591be92

Comment 51

[Marco Zehe (:MarcoZ)]

(In reply to comment #46)
> Is it crashing at Role()?

No, the current nightly build doesn't crash for me, so this does not appear to be bug 626841. I'll give the newest try-server build a go as soon as it's ready and report back if it still crashes for me.

Comment 52

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

(In reply to comment #49)
> "part1: create tree on content insertion" is landed on 2.0 beta10 -
> http://hg.mozilla.org/mozilla-central/rev/d5e9eddf4acd

Unfortunately this looks to have regressed talos quite a bit.
http://groups.google.com/group/mozilla.dev.tree-management/browse_thread/thread/e1d95e20f33779f9#

I can profile this tomorrow. Alexander, I'll try to catch you as I've promised the thread a response soon.

Comment 53

[Marco Zehe (:MarcoZ)]

I can confirm that this latest try-server build and also Thursday's nightly build feel a little less responsive than Wednesday's build over-all. Also, the test cases from bug 570500 all show some higher values in the post-processing bit.

In addition, jumping to an anchor on page load still doesn't work as reliably again as it did in 3.6. I've seen it working once but failing 4 times.

Comment 54

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

Confirmed with Marco that it is most evident on initial load.

Comment 55

[alexander :surkov (:asurkov)]

"part2: create initial tree" is landed on 2.0 http://hg.mozilla.org/mozilla-central/rev/26e88d430849

Comment 56

[alexander :surkov (:asurkov)]

(In reply to comment #53)

> In addition, jumping to an anchor on page load still doesn't work as reliably
> again as it did in 3.6. I've seen it working once but failing 4 times.

Do we have a bug on this?

Comment 57

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

Comment on attachment 504108 [details] [diff] [review]
part5v1: rename GetCachedAccessible

>+nsDocAccessible::GetAccessible(nsINode* aNode) const

>-    accessible = this;
>+    accessible = const_cast<nsDocAccessible*>(this);

Why is this necessary?

Comment 58

[alexander :surkov (:asurkov)]

(In reply to comment #57)

> >+nsDocAccessible::GetAccessible(nsINode* aNode) const
> 
> >-    accessible = this;
> >+    accessible = const_cast<nsDocAccessible*>(this);
> 
> Why is this necessary?

not necessary, just making a method a const since it doesn't change the document accessible.

Comment 59

[Fernando Herrera]

Comment on attachment 504108 [details] [diff] [review]
part5v1: rename GetCachedAccessible

Everything looks ok. r=me

Comment 60

[alexander :surkov (:asurkov)]

part3: handing document concept is landed - http://hg.mozilla.org/mozilla-central/rev/e0fc18b3bc41

Comment 61

[alexander :surkov (:asurkov)]

part4: deal with cached tree only is landed - http://hg.mozilla.org/mozilla-central/rev/f0f5638a8f51

Comment 62

[alexander :surkov (:asurkov)]

Attachment: patch5v2: rename GetCachedAccessible [landed 2011-01-27]

updated to trunk

Comment 63

[alexander :surkov (:asurkov)]

Attachment: part6v2: move GetAccessibleOrContainer to nsDocAccessible [landed 2011-01-27]

updated to trunk

Comment 64

[Fernando Herrera]

Comment on attachment 507415 [details] [diff] [review]
part6v2: move GetAccessibleOrContainer to nsDocAccessible [landed 2011-01-27]

r=me

Comment 65

[alexander :surkov (:asurkov)]

part5 - rename GetCachedAccessible is landed - http://hg.mozilla.org/mozilla-central/rev/635864984350

part6 - move GetAccessibleOrContainer to nsDocAccessible is landed - http://hg.mozilla.org/mozilla-central/rev/0b39828124f9

Comment 66

[alexander :surkov (:asurkov)]

RecreateAccessible leaves a hole for incomplete accessible tree, when the hide event is handled then we destroy the subtree and new one is not created. For now RecreateAccessible tree can be processed as ContentRemoved/ContentInserted pair leaving the optimization for the future. Reopen the bug.

Comment 67

[alexander :surkov (:asurkov)]

Attachment: patch7v1: recreate subtree when root is recreated

Comment 68

[chris hofmann]

possible crash regression from this in bug 629912

Comment 69

[chris hofmann]

this is marked "blocking final" but does it really need beta coverage.  number of comments and dependency bugs might be an indicator of complexity, and complex changes really should get beta coverage.

Comment 70

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

Agreed, marking blocking betaN+.

Comment 71

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

I don't think this caused the regression. Closing.

Comment 72

[Fernando Herrera]

Comment on attachment 507818 [details] [diff] [review]
patch7v1: recreate subtree when root is recreated


> 
>-  nsAccessible* parent = nsnull;
>+  // Check if the node is in DOM still.
>+  nsIContent* parentContent = aContent->GetParent();
>+  if (parentContent && parentContent->IsInDoc()) {
>+    nsAccessible* container = parentContent ?
>+      GetAccessibleOrContainer(parentContent) : this;

If we are inside the if branch, if because parentContent is not null, so I don't understand the "parentContent ? X : Y".

Comment 73

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

Alexander, does this latest patch fix bug 628668?

Comment 74

[alexander :surkov (:asurkov)]

(In reply to comment #73)
> Alexander, does this latest patch fix bug 628668?

I don't know. I've never seen this bug.

Comment 75

[alexander :surkov (:asurkov)]

(In reply to comment #72)

> >+  if (parentContent && parentContent->IsInDoc()) {
> >+    nsAccessible* container = parentContent ?
> >+      GetAccessibleOrContainer(parentContent) : this;
> 
> If we are inside the if branch, if because parentContent is not null, so I
> don't understand the "parentContent ? X : Y".

copy/paste issue I guess, I'll remove it.

Comment 76

[Fernando Herrera]

Comment on attachment 507818 [details] [diff] [review]
patch7v1: recreate subtree when root is recreated

r=me with the previous comment addressed

Comment 77

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

Comment on attachment 507818 [details] [diff] [review]
patch7v1: recreate subtree when root is recreated

r=me with Fer's catch. What about a Marco f+?

Comment 78

[alexander :surkov (:asurkov)]

(In reply to comment #77)
> Comment on attachment 507818 [details] [diff] [review]
> patch7v1: recreate subtree when root is recreated
> 
> r=me with Fer's catch. What about a Marco f+?

he did this implicitly by testing try server build from bug 626660.

Comment 79

[alexander :surkov (:asurkov)]

patch7v1: recreate subtree when root is recreated - landed on 2.0 beta 11 - http://hg.mozilla.org/mozilla-central/rev/ae887246ba34