ARIA attributes (like aria-labelledby, aria-describedby and etc) are used to create accessible relations for accessibles, for example, <span id="label">it's a description</span> <input aria-describedby="label"> We need to get related accessibles each by other, i.e. in the example above we need to get span by input and input by span. As side effect of relation computation we make sure that node that is related with another one is accessible what leads perf problems since we inspect the subtree around the node to see if it has ARIA attribute. For example, mozilla mxr pages may be loading significant time. We could cache either accessible relations or DOM structures that allows us to find related nodes. We need to create relations when DOM document is loading. Also we need to use nsIMutationObserver to keep relation updated. The problem is if the document was loaded before a11y started then we need to either traverse the whole DOM document before accessible tree creation and cache relations or make sure we create whole accessible tree and remember elements with ID since they can be referred by ARIA attributes somewhere in the tree and then insert their accessibles into tree.

this bug is part of bug 381599

This bug is critical for performance improvement of accessible tree creation. This bug is cause of very slow firefox on certain webpages when a11y is enabled.

Alexander, I'm going to unrequest blocking on this bug and make bug 563331 block since we need to resolve that bug via this bug, or some other way. This bug will be a dependency of bug 563331 and so will automatically inherit blocking status (as per Tuesday's platform meeting decision). Make sense?

(In reply to comment #2) > This bug is critical for performance improvement of accessible tree creation. > This bug is cause of very slow firefox on certain webpages when a11y is > enabled. Alexander, can you please provide example web pages where this bites us?

(In reply to comment #3) > Alexander, I'm going to unrequest blocking on this bug and make bug 563331 > block since we need to resolve that bug via this bug, or some other way. This > bug will be a dependency of bug 563331 and so will automatically inherit > blocking status (as per Tuesday's platform meeting decision). > > Make sense? I'm fine with this. (In reply to comment #4) > (In reply to comment #2) > > This bug is critical for performance improvement of accessible tree creation. > > This bug is cause of very slow firefox on certain webpages when a11y is > > enabled. > > Alexander, can you please provide example web pages where this bites us? I saw it on mxr pages, look for a big one like nsCSSFrameConstructor.cpp

(In reply to comment #4) > (In reply to comment #2) > > This bug is critical for performance improvement of accessible tree creation. > > This bug is cause of very slow firefox on certain webpages when a11y is > > enabled. > > Alexander, can you please provide example web pages where this bites us? I don't really want to look for web pages. I filed simple testcase (no any weird or contrived cases, just spans having @id attribute) in meta bug 570500 which shows that results in 100 times slower with this bug unfixed. This should be definitely blocking.

I need a nice way to iterate through IDs or elements pointed by IDRefs attribute.

Just for curiosity: why are you checking for repeated whitespace in every iteration instead of doing the CompressWhitespace() when storing the attrs?

(In reply to comment #8) > Just for curiosity: why are you checking for repeated whitespace in every > iteration instead of doing the CompressWhitespace() when storing the attrs? I want to avoid excess string traversal and its modification. All I need is to search IDs.

Comment on attachment 488636 [details] [diff] [review] part1_patch1: add iterator through IDRefs elements >+ PRInt32 idStartIdx = -1; >+ >+ for (; mCurrIdx < mIDs.Length(); mCurrIdx++) { >+ if (idStartIdx != -1) { >+ if (NS_IsAsciiWhitespace(mIDs[mCurrIdx])) { >+ aID = Substring(mIDs, idStartIdx, mCurrIdx - idStartIdx); >+ mCurrIdx++; >+ return true; >+ } >+ } else { >+ if (!NS_IsAsciiWhitespace(mIDs[mCurrIdx])) >+ idStartIdx = mCurrIdx; >+ } >+ } This is confusing. It might be better as two loops, one to find idStartIdx and one to find the "new" mCurrIdx. Doing that might even make the code simpler. >+ nsAutoString id; >+ while (NextID(id)) { [This ends up copying the id into the string, but I can't think of a good way of getting around that.]

(In reply to comment #10) > >+ nsAutoString id; > >+ while (NextID(id)) { > [This ends up copying the id into the string, but I can't think of a good way > of getting around that.] Would it help if I start to use const nsDependentSubstring instead of nsAutoString and nsAString in argument?

I don't think that would even compile.

ARIA relation test (bug 570500) results: 6 secs without relation getting, 30 seconds with it and 10 secs with patch. About 6 times improvement.

Neil's comments are addressed

Comment on attachment 489297 [details] [diff] [review] part2_patch2 r=me for the tests. So this one is strictly for ARIA? Will we get something similar for non-ARIA stuff too, for example when label/input relations are being created/changed dynamically?

(In reply to comment #16) > Comment on attachment 489297 [details] [diff] [review] > part2_patch2 > > r=me for the tests. So this one is strictly for ARIA? Will we get something > similar for non-ARIA stuff too, for example when label/input relations are > being created/changed dynamically? right, for others I want to deal in bug 381599.

Comment on attachment 489296 [details] [diff] [review] part1_patch2 >+const nsDependentSubstring >+IDRefsIterator::NextID() >+{ >+ PRInt32 idStartIdx = -1; >+ >+ for (; mCurrIdx < mIDs.Length(); mCurrIdx++) { >+ if (!NS_IsAsciiWhitespace(mIDs[mCurrIdx])) { >+ idStartIdx = mCurrIdx; >+ break; >+ } >+ } >+ >+ if (idStartIdx == -1) >+ return nsDependentSubstring(); >+ >+ for (++mCurrIdx; mCurrIdx < mIDs.Length(); mCurrIdx++) { >+ if (NS_IsAsciiWhitespace(mIDs[mCurrIdx])) { >+ return Substring(mIDs, idStartIdx, mCurrIdx++ - idStartIdx); >+ } >+ } >+ >+ return Substring(mIDs, idStartIdx, mCurrIdx - idStartIdx); >+} I like this, but you might also like this tweak: for (; mCurrIdx < mIDs.Length(); mCurrIdx++) { if (!NS_IsAsciiWhitespace(mIDs[mCurrIdx])) { break; } } nsAString::index_type idStartIdx = mCurrIdx; for (; mCurrIdx < mIDs.Length(); mCurrIdx++) { if (NS_IsAsciiWhitespace(mIDs[mCurrIdx])) { break; } } return Substring(mIDs, idStartIdx, mCurrIdx - idStartIdx); This version has the disadvantage that it checks some characters twice. >+ while (true) { [Some people prefer for (;;) but I guess that was in the days before bool.]

Comment on attachment 489297 [details] [diff] [review] part2_patch2 >+ nsIContent* providerContent = aRelProvider->GetContent(); >+ nsAutoString IDRefs; >+ if (providerContent->GetAttr(kNameSpaceID_None, aRelAttr, IDRefs)) { >+ IDRefsIterator iter(providerContent, IDRefs); Why can't you write this as IDRefsIterator iter(aRelProvider->GetContent(), aRelAttr); ?

the "Create Accessible Tree" test from bug 570500 takes about 3 sec to insert spans, before these patches it took 44 sec.

Comment on attachment 489297 [details] [diff] [review] part2_patch2 >+IDRefsIterator::IDRefsIterator(nsIContent* aContent, >+ const nsAString& aIDRefsAttrValue) : >+ } else{ nit: space after else. >--- a/accessible/src/base/nsDocAccessible.cpp >+++ b/accessible/src/base/nsDocAccessible.cpp >+static PRUint32 kRelationAttrsLen = NS_ARRAY_LENGTH(kRelationAttrs); nit: This could be const though I have no idea if that matters. >@@ -926,26 +939,56 @@ nsDocAccessible::AttributeWillChange(nsI > dom::Element* aElement, > PRInt32 aNameSpaceID, > nsIAtom* aAttribute, PRInt32 aModType) > { > // XXX TODO: bugs 381599 467143 472142 472143 Maybe you could say something about 381599 being partially implemented now :) >+ // Update dependent IDs cache. Note there might be ways to optimize this if necessary (on a follow up). >@@ -1341,27 +1384,31 @@ nsDocAccessible::BindToDocument(nsAccess (I'll probably want a renaming of BindTo and UnbindFrom (on dependent bug 545465)) Note to self: left off at AppendDependentIDsFor; go review bug 545465 soon and come back here.

something in the middle between Neil's suggestion and last version.

(In reply to comment #18) > >+ while (true) { > [Some people prefer for (;;) but I guess that was in the days before bool.] I'm fine with for (;;) but I think I like while(true) more. Hope that's ok. (In reply to comment #19) > Why can't you write this as > IDRefsIterator iter(aRelProvider->GetContent(), aRelAttr); ? I could but most of elements don't have these attributes, I just avoid to create object when I don't need. Does it make sense?

(In reply to comment #23) > (In reply to comment #19) > > Why can't you write this as > > IDRefsIterator iter(aRelProvider->GetContent(), aRelAttr); ? > I could but most of elements don't have these attributes, I just avoid to > create object when I don't need. Does it make sense? Well, you early return in the constructor anyway.

(In reply to comment #24) > (In reply to comment #23) > > (In reply to comment #19) > > > Why can't you write this as > > > IDRefsIterator iter(aRelProvider->GetContent(), aRelAttr); ? > > I could but most of elements don't have these attributes, I just avoid to > > create object when I don't need. Does it make sense? > Well, you early return in the constructor anyway. Right, perhaps it's too paranoiac to avoid create an object to avoid excess memory allocation while code can be more nicer if you do that. Should I do more nicer code?

make RelAccIterator work properly for XBL anon content

ignore non HTML for HasRelatedContent. I don't have any example where non accessible by default element is pointed by relation attribute in XUL and since XBL is primary used for XUL then IsDependentID() should safe for elements inside of different XBL bindings having the same anonid. As well I'm not aware of other markups used in web that would be inaccessible by default and be referred by relation attributes (mostly anything else than HTML and XUL hasn't good accessibility).

Comment on attachment 489625 [details] [diff] [review] part1_patch3 >+ for (++mCurrIdx; mCurrIdx < mIDs.Length(); mCurrIdx++) { I think you could also write this as: while (++mCurrIdx < mIDs.Length()) {

Comment on attachment 489971 [details] [diff] [review] part2_patch4 r=me with nits. Nice. >+ /** >+ * Append dependent IDs pointed by accessible element by relation attribute to >+ * cache. If the relation attribute is missed then all relation attributes >+ * are checked. >+ * >+ * @param aRelProvider [in] accessible that element has relation attribute >+ * @param aRelAttr [in, optional] relation attribute >+ */ >+ void AppendDependentIDsFor(nsAccessible* aRelProvider, >+ nsIAtom* aRelAttr = nsnull); I'm not sure "Append" is right here. I realize that is one kind of usage, but sometimes this is just about caching all the dependent IDs. How about: "AddDependentIDsFor"? For the comment how about: Store all relations or specifically those referred to by the optional relation attribute. Specifying the relation attribute does not remove existing stored relations. >+ >+ /** >+ * Remove dependent IDs pointed by accessible element by relation attribute >+ * from cache. If the relation attribute is missed then all relation >+ * attributes are checked. I think "absent" is more common than "missed" here. >+ /** >+ * The pair of relation attribute and the content providing this attribute. >+ */ Maybe "A storage class for pairing content with one of its relation attributes" >+ test_update.html \ >+++ b/accessible/tests/mochitest/relations/test_update.html >@@ -0,0 +1,162 @@ >+<html> >+ >+<head> >+ <title>Accessible relation tests in dynamic</title> "Test updating of accessible relations"

Comment on attachment 489971 [details] [diff] [review] part2_patch4 Alexander, can you please add a test case for something that is aria-labelledby an element with role="presentation"? It might be good for us to include these elements in the tree (even if this is an author error).

Comment on attachment 489977 [details] [diff] [review] part3_patch2 > static PRBool HasRelatedContent(nsIContent *aContent) >+ if (aContent->IsHTML() && >+ nsAccUtils::GetDocAccessibleFor(aContent)->IsDependentID(id)) I know we check for a valid doc accessible in our caller but no null check here still makes me nervous. Please add a null check if it makes you nervous too :) >+ /** >+ * Return the element by the given ID. Maybe: Return element with the given ID. [Note to self: left off at ::NotifyOfCachingEnd]

Comment on attachment 489625 [details] [diff] [review] part1_patch3 >+ for (++mCurrIdx; mCurrIdx < mIDs.Length(); mCurrIdx++) { >+ if (NS_IsAsciiWhitespace(mIDs[mCurrIdx])) >+ break; >+ } >+ >+ return Substring(mIDs, idStartIdx, mCurrIdx++ - idStartIdx); I also prefer here: while (++mCurrIdx < mIDs.Length()) { instead of pre-increment+post-increment at for loop init and step. Maybe also for consistency it would be nice to do the previous loop also as a while, but I don't have any preference on this. Beside that everything looks ok.

Comment on attachment 489977 [details] [diff] [review] part3_patch2 r=me. OK! Sorry for delay. >+nsDocAccessible::NotifyOfCachingEnd(nsAccessible* aAccessible) >+{ >+ if (mCacheRoot == aAccessible && !mIsPostCacheProcessing) { >+ // Allow invalidation list insertions while container children are recached. Hmm, OK. >+ // Make sure we keep children updated, it may be wrong to not reinitialize >+ // container children while while we're inside of caching loop. >+ container->EnsureChildren(); I found this comment slightly confusing/ambiguous. Are you saying that we shouldn't reinitialize the children prior to this method (in CacheChildren)? > void > nsDocAccessible::AppendDependentIDsFor(nsAccessible* aRelProvider, > nsIAtom* aRelAttr) >+ // We've got here during the children caching. If the referenced >+ // content is not accessible then store it to pend its container >+ // children invalidation (what happens immediately after the caching >+ // is finished). nit: "this" or "which" probably is better than "what" here. >+ nsIContent* dependentContent = iter.GetElem(id); >+ if (dependentContent && !GetCachedAccessible(dependentContent)) >+ mInvalidationList.AppendElement(dependentContent); >+ } Good. Definitely prefer {}'s here ;) (because of lonely parent block } looks ambiguous to my eye) >+++ b/accessible/src/base/nsDocAccessible.h >+ * Return true if the given ID is referred by relation attribute. >+ * >+ * @note Different elements may share the same ID if they are hosted inside >+ * XBL bindings. >+ */ >+ PRBool IsDependentID(const nsAString& aID) const Nice to have the @note, can you add something about how we (don't) handle this case? >+ /** >+ * Root of caching and list of nodes that container accessibles should be >+ * invalidated. Maybe: "Used for our caching algorithm. We store the root of the tree that needs caching, the list of nodes that should be invalidated, and whether we are processing the invalidation list." >+ * >+ * @see NotifyOfCaching This doesn't exist right? Maybe "@see NotifyOfCachingStart and NotifyOfCachingEnd"? >+ */ >+ nsAccessible* mCacheRoot; >+ nsTArray<nsIContent*> mInvalidationList; >+ PRBool mIsPostCacheProcessing;

Comment on attachment 489971 [details] [diff] [review] part2_patch4 >+ nsDocAccessible::AttrRelProvider* provider = (*mProviders)[mIndex]; >+ mIndex++; [Nit: could merge the ++ into the previous line.] >+ if (!mDependentIDsHash.Put(id, providers)) >+ delete providers; [Does this set providers back to null, for the if below it? I can't remember.] >+ if (providers->Length() == 0) >+ mDependentIDsHash.Remove(id); [Does providers need to be deleted?]

(In reply to comment #35) >(From update of attachment 489971 [details] [diff] [review]) >>+ if (!mDependentIDsHash.Put(id, providers)) >>+ delete providers; >[Does this set providers back to null, for the if below it? I can't remember.] It apparently doesn't, so the if will succeed and you will crash.

Comment on attachment 489977 [details] [diff] [review] part3_patch2 Didn't see anything interesting here.

(In reply to comment #35) > Comment on attachment 489971 [details] [diff] [review] > part2_patch4 > >+ if (providers->Length() == 0) > >+ mDependentIDsHash.Remove(id); > [Does providers need to be deleted?] Hmm I missed that (darn it I need to get better at this).

(In reply to comment #30) > Comment on attachment 489971 [details] [diff] [review] > part2_patch4 > I'm not sure "Append" is right here. I realize that is one kind of usage, but > sometimes this is just about caching all the dependent IDs. How about: > "AddDependentIDsFor"? ok > For the comment how about: > Store all relations or specifically those referred to by the optional relation > attribute. Specifying the relation attribute does not remove existing stored > relations. it sounds unclear for me because it's not clear what is relation making hard to understand what this method is going to do. (In reply to comment #31) > Comment on attachment 489971 [details] [diff] [review] > part2_patch4 > > Alexander, can you please add a test case for something that is aria-labelledby > an element with role="presentation"? > > It might be good for us to include these elements in the tree (even if this is > an author error). Perhaps the bug should be open for that and add mochitest there. I'm not sure what is right behavior and therefor adding mochitest now doesn't make lot of sense. Are you fine with that? (In reply to comment #35) > Comment on attachment 489971 [details] [diff] [review] > part2_patch4 > > >+ if (providers->Length() == 0) > >+ mDependentIDsHash.Remove(id); > [Does providers need to be deleted?] providers is nsTArray, so I shouldn't care about that, right? (In reply to comment #36) > (In reply to comment #35) > >(From update of attachment 489971 [details] [diff] [review]) > >>+ if (!mDependentIDsHash.Put(id, providers)) > >>+ delete providers; > >[Does this set providers back to null, for the if below it? I can't remember.] > It apparently doesn't, so the if will succeed and you will crash. right, thanks for the catch.

(In reply to comment #32) > Comment on attachment 489977 [details] [diff] [review] > part3_patch2 > > > static PRBool HasRelatedContent(nsIContent *aContent) > I know we check for a valid doc accessible in our caller but no null check here > still makes me nervous. Please add a null check if it makes you nervous too :) It doesn't while our caller does this. (In reply to comment #34) > Comment on attachment 489977 [details] [diff] [review] > part3_patch2 > >+ // Make sure we keep children updated, it may be wrong to not reinitialize > >+ // container children while while we're inside of caching loop. > >+ container->EnsureChildren(); > > I found this comment slightly confusing/ambiguous. Are you saying that we > shouldn't reinitialize the children prior to this method (in CacheChildren)? No I think. Is it better? // Make sure we keep children updated. While we're inside of caching loop // then we must exist it with cached children. > >+ PRBool IsDependentID(const nsAString& aID) const > > Nice to have the @note, can you add something about how we (don't) handle this > case? Perhaps it's not right place since caller should take care of this. Would it be nicer if I add "Be careful the result of this method may be senseless while it's called for XUL elements (where XBL is used widely)".

(In reply to comment #33) > Comment on attachment 489625 [details] [diff] [review] > part1_patch3 > Maybe also for consistency it would be nice to do the previous loop also as a > while, but I don't have any preference on this. I don't have any clue how to transform the first for into while.

part1 landed with Neil's comment addressed - http://hg.mozilla.org/mozilla-central/rev/384f1f7127df

(In reply to comment #39) > (In reply to comment #30) > > For the comment how about: > > Store all relations or specifically those referred to by the optional relation > > attribute. Specifying the relation attribute does not remove existing stored > > relations. > > it sounds unclear for me because it's not clear what is relation making hard to > understand what this method is going to do. OK. I just wanted it to be clear that this is not a destructive method but no big deal. > (In reply to comment #31) > > Comment on attachment 489971 [details] [diff] [review] [details] > > part2_patch4 > > > > Alexander, can you please add a test case for something that is aria-labelledby > > an element with role="presentation"? > > > > It might be good for us to include these elements in the tree (even if this is > > an author error). > > Perhaps the bug should be open for that and add mochitest there. I'm not sure > what is right behavior and therefor adding mochitest now doesn't make lot of > sense. Are you fine with that? Sure. Filed bug 612920.

part2 landed on 2.0 with comments addressed - http://hg.mozilla.org/mozilla-central/rev/c3c229aaf531

(In reply to comment #39) > (In reply to comment #35) > > (From update of attachment 489971 [details] [diff] [review]) > > >+ if (providers->Length() == 0) > > >+ mDependentIDsHash.Remove(id); > > [Does providers need to be deleted?] > providers is nsTArray, so I shouldn't care about that, right? Actually it makes things worse, since not are you leaking *providers, but you're leaking its contents too, since it's not being destroyed.

(In reply to comment #45) > (In reply to comment #39) > > (In reply to comment #35) > > > (From update of attachment 489971 [details] [diff] [review]) > > > >+ if (providers->Length() == 0) > > > >+ mDependentIDsHash.Remove(id); > > > [Does providers need to be deleted?] > > providers is nsTArray, so I shouldn't care about that, right? > Actually it makes things worse, since not are you leaking *providers, but > you're leaking its contents too, since it's not being destroyed. This is nsClassHashtable, so nsTArray is kept by nsAutoPtr, it should be ok, I guess. Sounds correct?

(In reply to comment #46) > (In reply to comment #45) > > (In reply to comment #39) > > > (In reply to comment #35) > > > > (From update of attachment 489971 [details] [diff] [review] [details]) > > > > >+ if (providers->Length() == 0) > > > > >+ mDependentIDsHash.Remove(id); > > > > [Does providers need to be deleted?] > > > providers is nsTArray, so I shouldn't care about that, right? > > Actually it makes things worse, since not are you leaking *providers, but > > you're leaking its contents too, since it's not being destroyed. > This is nsClassHashtable, so nsTArray is kept by nsAutoPtr, it should be ok, I > guess. Sounds correct? Yes, that makes sense now. Sorry I didn't realise that nsClassHashtable automatically deletes its entries.

part3 landed on 2.0 - http://hg.mozilla.org/mozilla-central/rev/e3d3bcffefa7