381599 - Inverse relations cache

Status: RESOLVED FIXED

(Core :: Disability Access APIs, defect)

Description

[Aaron Leventhal]

Many accessible relations are expensive to calculate, because we're looking for any node in the DOM which points to the node being asked about.

For example, the labelledby relation needs to look for a <label for="[id]"> element in the dom where the for attribute's value is the same as the current element's id.

This problem is exacerbated by the fact that accessibility APIs tend to get all the relations as a set. When the AT wants a single relation it needs to get them all.

The potential solution is to look at nodes when they're added (onload or later), and seek out relation properties. Whenever an element points to another, insert the expensive reverse relation into a relation cache. Be sure to invalidate the appropriate entries in the cache when either the pointer or "pointee" node goes away.

The problem with this solution is mostly complexity. I'm concerned that it is late in the game for Firefox 3. On the other hand, if we don't do this, then relations may be too expensive to use. Relations are especially important because of ARIA.

Comment 1

[Aaron Leventhal]

One thing to be careful of is:
Node A -> Node B

Node B goes away

Node C is added with same ID that Node B had, so:
Node A -> Node C

Also, what about cases that should not occur but could, such as an ID being set dynamically or multiple items with the same ID, etc.

We may not handle weird edge cases but we can't crash.

Comment 2

[Aaron Leventhal]

One concern is that this could affect page load time on Linux, when a11y is turned on (which is becoming the case more and more often).

We already slow down page load time by about 10%, which I found out once when I accidentally turned off a11y on Linux and the tinderbox numbers came in 10% faster.

One way to alleviate that might be to not create any root accessibles on Linux unless they're really asked for. Just create the app accessible. Might need to file another perf bug on that.

Comment 3

[Aaron Leventhal]

Hmm, we can't get the old attribute value in the attribute changed notification. There's nsIDocument::AttributeWillChange(), but there's no way to register for it.

This makes it more difficult to invalidate the inverse relation cache when someone changes an attribute, such as the for attribute.

Comment 4

[Aaron Leventhal]

To solve the problem in comment #3, we can listen to real DOMAttrModified mutation events to get the event.prevValue. That would be instead of nsIDocumentObserver::AttributeChanged().

Comment 5

[Aaron Leventhal]

There is some old code in bug 290352 we can look at for nsIDOMMutationListener and ::AttrModified() code.

Comment 6

[Aaron Leventhal]

The following relations are affected by this:
<label for=IDREF>
<xul:label control=IDREF>
<xul:description control=IDREF>
aaa:labelledby=IDREFS
aaa:describedby=IDREFS
aaa:controls=IDREFS
aaa:flowto=IDREFS
aaa:owns=IDREFS

More may come in the future. ARIA 2.0 may provide the capability to create custom relations.

Comment 7

[alexander :surkov (:asurkov)]

I tried to do this as part of the bug 345780, iirc there are listed problems I faced when I tried to do this.

Comment 8

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

Mass un-assigning bugs assigned to Aaron.

Comment 9

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

Note the CPU killing is happening nsAccessibilityService::GetAccessible where we check HasRelatedContent.

Comment 10

[alexander :surkov (:asurkov)]

requesting a blocking: it's not about relation computation cost, it's also about name computation cost what's perhaps more serious issue for existing ATs.

The bug 573469 is going to fix the issue for ARIA relations attributes. Here we need to deal with:

<label for=IDREF>
<xul:label control=IDREF>
<xul:description control=IDREF>

Comment 11

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

Marking blocking for now because we should try to get this into FF4. We'll need to get perf numbers for when accessibility is simply invoked and when it is invoked and used by a screen reader. As we discussed, if the speed of our name calculation is noticeably improved it may be worth it but otherwise landing this because AT 'might' want to use it is not enough of a reason.

Comment 12

[alexander :surkov (:asurkov)]

Attachment: patch

Comment 13

[alexander :surkov (:asurkov)]

Attachment: patch2

mochitest changes

Comment 14

[alexander :surkov (:asurkov)]

Before the patch HTML name testcase from bug a11yperf_fx4 takes 87 seconds, after the patch it takes 5 seconds.

Comment 15

[alexander :surkov (:asurkov)]

try server build containing this patch and patches from bug 573469 http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/[e-mail]-3df8d150ad4e

Comment 16

[Marco Zehe (:MarcoZ)]

Comment on attachment 489993 [details] [diff] [review]
patch2

I'll give the try-server build a go before I r+, but so far things look good from this end. Nice to see all these methods be so nicely folded into these iterators!

Comment 17

[Marco Zehe (:MarcoZ)]

Comment on attachment 489993 [details] [diff] [review]
patch2

r=me after running the try-server build and throwing it at the test cases for bug 570500. All looks good from this end.

Comment 18

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

Comment on attachment 489993 [details] [diff] [review]
patch2

r=me "with bells on"!

Hmmm, again, I didn't catch any errors (tests help).

>diff --git a/accessible/src/base/AccIterator.cpp b/accessible/src/base/AccIterator.cpp

>+HTMLLabelIterator::

>+  // Go up tree get name of ancestor label if there is one (an ancestor <label>
>+  // implicitly points to us). Don't go up farther than form element.

"form or body element" (body is important for subdocuments case right?)

>+  nsIContent* walkUpContent = mElement;
>+  while ((walkUpContent = walkUpContent->GetParent()) &&
>+         walkUpContent->Tag() != nsAccessibilityAtoms::form &&
>+         walkUpContent->Tag() != nsAccessibilityAtoms::body) {
>+    if (walkUpContent->Tag()== nsAccessibilityAtoms::label) {

nit: space before ==

>+      // Prevent infinite loop.

I'm all for that! (How does it happen?)

>+nsAccessible*
>+HTMLOutputIterator::Next()
>+{
>+  nsAccessible* output = nsnull;
>+  while ((output = mRelIter.Next())) {
>+    if (output->GetContent()->Tag() == nsAccessibilityAtoms::output)
>+      return output;
>+  }

I would call output something else like relAcc but that's just a style issue. Actually I won't make you change this pattern since you do it throughout :)

>+nsAccessible*
>+XULLabelIterator::Next()
>+{
>+  nsAccessible* label = nsnull;
>+  while ((label = mRelIter.Next())) {
>+    if (label->GetContent()->Tag() == nsAccessibilityAtoms::label)
>+      return label;
>+  }
>+
>+  return nsnull;
>+}

Note an alternative style would be:
{
  nsAccessible* label = nsnull;
  while ((label = mRelIter.Next())) {
    if (label->GetContent()->Tag() == nsAccessibilityAtoms::label)
      break;
  }

  return label;
}

I don't mind... but use this if you like it.

>+
>+/**
>+ * Used to iterate through HTML labels associated with given element.

nit: "with the given element" (same for all Iterator comments)

>@@ -388,21 +384,33 @@ nsAccessible::GetKeyboardShortcut(nsAStr

>+    // Copy access key from label node.
>+    if (mContent->IsHTML()) {
>+      // Unless it is labeled via an ancestor <label>, in which case that would

nit: I would put "// ... unless it is"

>diff --git a/accessible/src/base/nsCoreUtils.cpp b/accessible/src/base/nsCoreUtils.cpp

Yes!
Good bye
nsCoreUtils::FindNeighbourPointingToNode
nsCoreUtils::FindDescendantPointingToID


>diff --git a/accessible/src/base/nsDocAccessible.cpp b/accessible/src/base/nsDocAccessible.cpp

> nsDocAccessible::AttributeWillChange(nsIDocument *aDocument,

>-  // XXX TODO: bugs 381599 (partially fixed by 573469), 467143, 472142, 472143.
>+  // XXX TODO: bugs 467143, 472142, 472143.

:)

>+		test_keys.html \

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

Nice :)

In final summary: Woohoo!

Comment 19

[alexander :surkov (:asurkov)]

(In reply to comment #18)

> >+  // Go up tree get name of ancestor label if there is one (an ancestor <label>
> >+  // implicitly points to us). Don't go up farther than form element.
> 
> "form or body element" (body is important for subdocuments case right?)

ok. No, it doesn't important at all.

> >+      // Prevent infinite loop.
> 
> I'm all for that! (How does it happen?)

it happens in while((elm = iter.Next());

> >+  nsAccessible* output = nsnull;
> >+  while ((output = mRelIter.Next())) {
> >+    if (output->GetContent()->Tag() == nsAccessibilityAtoms::output)
> >+      return output;
> >+  }
> 
> I would call output something else like relAcc but that's just a style issue.
> Actually I won't make you change this pattern since you do it throughout :)

I tend to miss accessible word in names because we deal with accesibles in most cases. We look for output accessible here, so neither rel nor acc makes good sense here.

> Note an alternative style would be:
> {
>   nsAccessible* label = nsnull;
>   while ((label = mRelIter.Next())) {
>     if (label->GetContent()->Tag() == nsAccessibilityAtoms::label)
>       break;
>   }
> 
>   return label;
> }

right, I don't have preferences here. Though perhaps I would stay with my version.

> >+    // Copy access key from label node.
> >+    if (mContent->IsHTML()) {
> >+      // Unless it is labeled via an ancestor <label>, in which case that would
> 
> nit: I would put "// ... unless it is"

not sure. Then we should remove '.' from comment above but then we should add something for XUL part. I don't see how to make this nice. Perhaps leave it as is?

> Yes!
> Good bye
> nsCoreUtils::FindNeighbourPointingToNode
> nsCoreUtils::FindDescendantPointingToID

right, that kept me happy as well :)

> >+		test_keys.html \
> 
> >+++ b/accessible/tests/mochitest/test_keys.html
> 
> Nice :)

the cool thing is it fails prior this patch :) No accesskey from label.

Comment 20

[alexander :surkov (:asurkov)]

landed on 2.0 - http://hg.mozilla.org/mozilla-central/rev/1c82a99070c2