Inverse relations cache

RESOLVED FIXED in mozilla2.0b8

Status

()

--
major
RESOLVED FIXED
12 years ago
8 years ago

People

(Reporter: aaronlev, Assigned: surkov)

Tracking

(Blocks: 2 bugs, {access, perf})

Trunk
mozilla2.0b8
access, perf
Points:
---
Dependency tree / graph
Bug Flags:
in-testsuite +

Firefox Tracking Flags

(blocking2.0 final+)

Details

Attachments

(1 attachment, 1 obsolete attachment)

(Reporter)

Description

12 years ago
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.
(Reporter)

Comment 1

12 years ago
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.
(Reporter)

Updated

12 years ago
Severity: normal → enhancement
(Reporter)

Comment 2

12 years ago
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.
(Reporter)

Comment 3

12 years ago
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.
(Reporter)

Comment 4

12 years ago
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().
(Reporter)

Comment 5

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

Comment 6

12 years ago
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.
(Reporter)

Updated

11 years ago
Blocks: 395699
(Assignee)

Comment 7

10 years ago
I tried to do this as part of the bug 345780, iirc there are listed problems I faced when I tried to do this.
(Assignee)

Updated

10 years ago
Blocks: 475297
Mass un-assigning bugs assigned to Aaron.
Assignee: aaronleventhal → nobody
Note the CPU killing is happening nsAccessibilityService::GetAccessible where we check HasRelatedContent.
(Assignee)

Updated

9 years ago
Depends on: 573469
(Assignee)

Comment 10

8 years ago
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>
Assignee: nobody → surkov.alexander
blocking2.0: --- → ?
(Assignee)

Updated

8 years ago
Blocks: 570500
(Assignee)

Updated

8 years ago
Severity: enhancement → major
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.
blocking2.0: ? → final+
(Assignee)

Comment 12

8 years ago
Created attachment 489979 [details] [diff] [review]
patch
Attachment #489979 - Flags: review?(marco.zehe)
Attachment #489979 - Flags: review?(bolterbugz)
(Assignee)

Updated

8 years ago
Status: NEW → ASSIGNED
(Assignee)

Comment 13

8 years ago
Created attachment 489993 [details] [diff] [review]
patch2

mochitest changes
Attachment #489979 - Attachment is obsolete: true
Attachment #489993 - Flags: review?(marco.zehe)
Attachment #489993 - Flags: review?(bolterbugz)
Attachment #489979 - Flags: review?(marco.zehe)
Attachment #489979 - Flags: review?(bolterbugz)
(Assignee)

Comment 14

8 years ago
Before the patch HTML name testcase from bug a11yperf_fx4 takes 87 seconds, after the patch it takes 5 seconds.
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 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.
Attachment #489993 - Flags: review?(marco.zehe) → review+
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!
Attachment #489993 - Flags: review?(bolterbugz) → review+
(Assignee)

Comment 19

8 years ago
(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.
(Assignee)

Comment 20

8 years ago
landed on 2.0 - http://hg.mozilla.org/mozilla-central/rev/1c82a99070c2
Status: ASSIGNED → RESOLVED
Last Resolved: 8 years ago
Flags: in-testsuite+
Resolution: --- → FIXED
Target Milestone: --- → mozilla2.0b8
You need to log in before you can comment on or make changes to this bug.