I wanted to see why my local build of Firefox was locking up so frequently so I broke in with the debugger whenever it froze. Here are some of the issues I discovered. Issue #1: In `DocAccessible::CacheChildren`, we add a whole tree worth of nodes to a cache tree. We do this one by one using the `AppendChild` method, which in turn calls `InsertChildAt`. This calls `InvalidateChildrenGroupInfo` to mark all the children of the parent as dirty. The problem is that `InvalidateChildrenGroupInfo` is going to be called once per insertion and it processes every single child node, making this an n-squared operation. It seems like we only need to call `InvalidateChildrenGroupInfo` once, after performing all of our insertions. Issue #2: Same issue but for `HyperTextAccessible::CacheChildren` Issue #3: In `DocAccessible::ShutdownChildrenInSubtree` we loop through every child node and call `DocAccessible::UnbindFromDocument` which calls `Accessible::Shutdown()` which then calls `Accessible::RemoveChild`. That last method loops through every child with a higher index than the specified child and decreases its index. We could eliminate a lot of cpu churn by simply making `DocAccessible::ShutdownChildrenInSubtree` start from the last child and move toward the first instead of starting at the first child and moving toward the last. The attached patch tries to fix each of these issues and from my limited testing seemed to alleviate them without causing other problems. Please feel free to take it and run with it; I'm not super familiar with this area of the codebase or its conventions so I'm happy for someone else to pick it up.

> I wanted to see why my local build of Firefox was locking up so frequently > so I broke in with the debugger whenever it froze. Here are some of the > issues I discovered. would you happen to have a test case? > Issue #1: > In `DocAccessible::CacheChildren`, we add a whole tree worth of nodes to a > cache tree. We do this one by one using the `AppendChild` method, which in > turn calls `InsertChildAt`. This calls `InvalidateChildrenGroupInfo` to mark > all the children of the parent as dirty. The problem is that > `InvalidateChildrenGroupInfo` is going to be called once per insertion and > it processes every single child node, making this an n-squared operation. It > seems like we only need to call `InvalidateChildrenGroupInfo` once, after > performing all of our insertions. > > Issue #2: > Same issue but for `HyperTextAccessible::CacheChildren` > > Issue #3: > In `DocAccessible::ShutdownChildrenInSubtree` we loop through every child > node and call `DocAccessible::UnbindFromDocument` which calls > `Accessible::Shutdown()` which then calls `Accessible::RemoveChild`. That > last method loops through every child with a higher index than the specified > child and decreases its index. We could eliminate a lot of cpu churn by > simply making `DocAccessible::ShutdownChildrenInSubtree` start from the last > child and move toward the first instead of starting at the first child and > moving toward the last. > > The attached patch tries to fix each of these issues and from my limited > testing seemed to alleviate them without causing other problems. Please feel > free to take it and run with it; I'm not super familiar with this area of > the codebase or its conventions so I'm happy for someone else to pick it up. On first thought that seems correct though I don't think I've ever seen this show up high in profiles.

The pages that I noticed my browser freezing were: https://mxr.mozilla.org/mozilla-central/source/widget/windows/nsWindow.cpp http://dxr.mozilla.org/mozilla-central/source/widget/windows/nsWindow.cpp More often than not, if I broke into the process while the browser was unresponsive, I found that I was in one of the places mentioned in comment 0. Let me know if there's more info I can provide or if you'd like me to keep running with the patch.

(In reply to Tim Abraldes [:TimAbraldes] [:tabraldes] from comment #0) > Issue #1: agree, it's reasonable (In reply to Trevor Saunders (:tbsaunde) from comment #1) > On first thought that seems correct though I don't think I've ever seen > this show up high in profiles. probably because it's more or less recent change (In reply to Tim Abraldes [:TimAbraldes] [:tabraldes] from comment #2) > if you'd like me to keep > running with the patch. please alternative approaches can be considered 1) make InvalidateChildrenGroupInfo smarter to avoid running through children with dirty flag 2) make InsertChildAt/AppendChild protected and require a caller to call UpdateChildrenGroupInfo() after batch of changes (mostly what you did but having no _NoDirty methods)

just fyi, there's another problem (bug 1040735) related with InvalidateChildrenGroupInfo that might affect on solution design taken here.

Comment on attachment 8459050 [details] [diff] [review] Patch v1 > > if you'd like me to keep > > running with the patch. > > please > > alternative approaches can be considered > 1) make InvalidateChildrenGroupInfo smarter to avoid running through > children with dirty flag > 2) make InsertChildAt/AppendChild protected and require a caller to call > UpdateChildrenGroupInfo() after batch of changes (mostly what you did but > having no _NoDirty methods) I don't think 1 is possible: You would have to either check every child for a dirty flag (which is just as algorithmically slow as setting the flag) or you would have to maintain separate structures of dirty and clean (which would complicate the logic and increase memory usage). Let me know if 2 is preferred over the approach taken in this patch or if there is another alternative that would be preferable.

(In reply to Tim Abraldes [:TimAbraldes] [:tabraldes] from comment #5) > Comment on attachment 8459050 [details] [diff] [review] > Patch v1 > > > > if you'd like me to keep > > > running with the patch. > > > > please > > > > alternative approaches can be considered > > 1) make InvalidateChildrenGroupInfo smarter to avoid running through > > children with dirty flag > > 2) make InsertChildAt/AppendChild protected and require a caller to call > > UpdateChildrenGroupInfo() after batch of changes (mostly what you did but > > having no _NoDirty methods) > > I don't think 1 is possible: You would have to either check every child for > a dirty flag (which is just as algorithmically slow as setting the flag) or > you would have to maintain separate structures of dirty and clean (which > would complicate the logic and increase memory usage). could it look like // move backward for (int i = mIndexInParent - 1; i >= 0 && !mChildren[i]->HasDirtyGroupInfo(); i--) mChildren[i]->SetDirtyGroupInfo(true); // move forward so if you do while (hasKids) { AppendChild(kid); } then each subsequent call shouldn't traverse all children again. > Let me know if 2 is preferred over the approach taken in this patch or if > there is another alternative that would be preferable. Trev, do you have preferences on each way? NoDirty approach is nice but feels a bit heavy.

(In reply to alexander :surkov from comment #6) > (In reply to Tim Abraldes [:TimAbraldes] [:tabraldes] from comment #5) > > Comment on attachment 8459050 [details] [diff] [review] > > Patch v1 > > > > > > if you'd like me to keep > > > > running with the patch. > > > > > > please > > > > > > alternative approaches can be considered > > > 1) make InvalidateChildrenGroupInfo smarter to avoid running through > > > children with dirty flag > > > 2) make InsertChildAt/AppendChild protected and require a caller to call > > > UpdateChildrenGroupInfo() after batch of changes (mostly what you did but > > > having no _NoDirty methods) > > > > I don't think 1 is possible: You would have to either check every child for > > a dirty flag (which is just as algorithmically slow as setting the flag) or > > you would have to maintain separate structures of dirty and clean (which > > would complicate the logic and increase memory usage). > > could it look like > > // move backward > for (int i = mIndexInParent - 1; i >= 0 && > !mChildren[i]->HasDirtyGroupInfo(); i--) > mChildren[i]->SetDirtyGroupInfo(true); > // move forward > > so if you do > while (hasKids) { > AppendChild(kid); > } > > then each subsequent call shouldn't traverse all children again. but you have to do something else if you insert children in the middle. > > Let me know if 2 is preferred over the approach taken in this patch or if > > there is another alternative that would be preferable. I think I like 2 somewhat better, but its not really great. > Trev, do you have preferences on each way? NoDirty approach is nice but > feels a bit heavy. short of "rewrite everything so we call AppendChild much less"?

(In reply to Trevor Saunders (:tbsaunde) from comment #7) > > then each subsequent call shouldn't traverse all children again. > > but you have to do something else if you insert children in the middle. you run back and forward as suggested, the point is you don't need traverse the array twice if insert twice > > > Let me know if 2 is preferred over the approach taken in this patch or if > > > there is another alternative that would be preferable. > > I think I like 2 somewhat better, but its not really great. > > > Trev, do you have preferences on each way? NoDirty approach is nice but > > feels a bit heavy. > > short of "rewrite everything so we call AppendChild much less"? that shouldn't be so bad, just move them into protected section and make sure each caller updates group info after. Alternative is to have a guard object like struct TreeMutationGuard(Accessible* aMutated) { TreeMutationGuard() { mAcc->SetFlag(eSubtreeMutating) }; ~TreeMutationGuard() { mAcc->RemoveFlag(eSubtreeMutating); mAcc->UpdateGroupInfo(); } Accessible* mAcc; }; Accessible::AppnedChild(Accessible* aChild) { NS_ASSERITON(HasFlag(eSubtreeMutating), "Illegal tree update!"); } TreeMuationGuard guard(this); while (haveKids) AppendChild(kid);

(In reply to alexander :surkov from comment #8) > (In reply to Trevor Saunders (:tbsaunde) from comment #7) > > > > then each subsequent call shouldn't traverse all children again. > > > > but you have to do something else if you insert children in the middle. > > you run back and forward as suggested, the point is you don't need traverse > the array twice if insert twice seems slower than the alternative though. > > > > Let me know if 2 is preferred over the approach taken in this patch or if > > > > there is another alternative that would be preferable. > > > > I think I like 2 somewhat better, but its not really great. > > > > > Trev, do you have preferences on each way? NoDirty approach is nice but > > > feels a bit heavy. > > > > short of "rewrite everything so we call AppendChild much less"? > > that shouldn't be so bad, just move them into protected section and make > sure each caller updates group info after. Alternative is to have a guard > object like > > struct TreeMutationGuard(Accessible* aMutated) > { > TreeMutationGuard() { mAcc->SetFlag(eSubtreeMutating) }; > ~TreeMutationGuard() > { > mAcc->RemoveFlag(eSubtreeMutating); > mAcc->UpdateGroupInfo(); > } > Accessible* mAcc; > }; > > Accessible::AppnedChild(Accessible* aChild) > { > NS_ASSERITON(HasFlag(eSubtreeMutating), "Illegal tree update!"); > } > > TreeMuationGuard guard(this); > while (haveKids) > AppendChild(kid); guard seems weird name, maybe use AutoTreeMutation? but otherwise seems fine.

(In reply to Trevor Saunders (:tbsaunde) from comment #9) > > you run back and forward as suggested, the point is you don't need traverse > > the array twice if insert twice > > seems slower than the alternative though yeah, something like 3 times slower, much better than o^2 though, a positive thing no extra moves like AutoTreeMutation objects > > TreeMuationGuard guard(this); > > while (haveKids) > > AppendChild(kid); > > guard seems weird name, maybe use AutoTreeMutation? but otherwise seems fine. fine with me Tim, what do you think?

(In reply to alexander :surkov from comment #10) > (In reply to Trevor Saunders (:tbsaunde) from comment #9) > > > you run back and forward as suggested, the point is you don't need traverse > > > the array twice if insert twice > > > > seems slower than the alternative though > > yeah, something like 3 times slower, much better than o^2 though, a positive > thing no extra moves like AutoTreeMutation objects so make setting a mutating state ifdef debug.

So something like this?

Comment on attachment 8465090 [details] [diff] [review] Patch v2 Review of attachment 8465090 [details] [diff] [review]: ----------------------------------------------------------------- it's something in the middle between comment #6 and comment #8, it looks more complicated than comment #6 and should have nearly same performance.

Comment on attachment 8465090 [details] [diff] [review] Patch v2 > Accessible::BindToParent(Accessible* aParent, uint32_t aIndexInParent) > { > NS_PRECONDITION(aParent, "This method isn't used to set null parent!"); > > if (mParent) { > if (mParent != aParent) {> NS_ERROR("Adopting child!"); >- mParent->RemoveChild(this); >- mParent->InvalidateChildrenGroupInfo(); >+ { >+ AutoChildTreeMutation mut(mParent); should be unnecessary, we should already be within a mutation at this point. >+ mParent->RemoveChild(this); >+ } > } else { > NS_ERROR("Binding to the same parent!"); > return; > } > } > > mParent = aParent; > mIndexInParent = aIndexInParent; > >- mParent->InvalidateChildrenGroupInfo(); >+ if (mParent) { >+ AutoChildTreeMutation mut(mParent); >+ } same > void > Accessible::UnbindFromParent() > { >- mParent->InvalidateChildrenGroupInfo(); >+ if (mParent) { >+ AutoChildTreeMutation mut(mParent); >+ } same, and pretty silly since the scope of the object is just constructing it. > Accessible::InvalidateChildren() > { >+ AutoChildTreeMutation mut(this); if this is called we should per the API be just about to finish mutatingthe tree so I don't think there's a point. So just assert that we're in a tree that's being mutated and do the same for Insert / Remove Child. >+ class AutoChildTreeMutation { >+ public: >+ AutoChildTreeMutation(Accessible* acc) >+ : mAccessible(acc) { >+ mAccessible->mCurrentMutations++; I'm pretty sure just having a bit for mutating or not is enough. >+ } >+ void Cancel() { >+ --mAccessible->mCurrentMutations; >+ mAccessible = nullptr; >+ } afaik the only places this is used is when there's no children, in which case there's not much point >@@ -1493,31 +1493,39 @@ void > DocAccessible::CacheChildren() > { > // Search for accessible children starting from the document element since > // some web pages tend to insert elements under it rather than document body. > dom::Element* rootElm = mDocumentNode->GetRootElement(); > if (!rootElm) > return; > >- // Ignore last HTML:br, copied from HyperTextAccessible. >+ // Trailing HTML br element don't play any difference. We don't need to expose >+ // it to AT (see bug https://bugzilla.mozilla.org/show_bug.cgi?id=899433#c16 >+ // for details). why are you changing this? >+ >+ AutoChildTreeMutation mut(this); > TreeWalker walker(this, rootElm); >- Accessible* lastChild = nullptr; >- while (Accessible* child = walker.NextChild()) { >- if (lastChild) >- AppendChild(lastChild); >- >- lastChild = child; >+ Accessible* child = walker.NextChild(); >+ Accessible* nextChild = child ? walker.NextChild() : nullptr; >+ while (nextChild) { >+ InsertChildAt(mChildren.Length(), child); >+ child = nextChild; >+ nextChild = walker.NextChild(); > } > >- if (lastChild) { >- if (lastChild->IsHTMLBr()) >- Document()->UnbindFromDocument(lastChild); >- else >- AppendChild(lastChild); >+ if (!child) { >+ mut.Cancel(); no point, if that happens there's no kids so we don't really save much by not calling InvalidateChildrenGroupInfo() >+ } else { >+ if (child->IsHTMLBr()) { >+ Document()->UnbindFromDocument(child); >+ mut.Cancel(); that's wrong, there could have been a mutation adding children before the br we're ignoring. > DocAccessible::ShutdownChildrenInSubtree(Accessible* aAccessible) > { > // Traverse through children and shutdown them before this accessible. When > // child gets shutdown then it removes itself from children array of its >- //parent. Use jdx index to process the cases if child is not attached to the >- // parent and as result doesn't remove itself from its children. >- uint32_t count = aAccessible->ContentChildCount(); >- for (uint32_t idx = 0, jdx = 0; idx < count; idx++) { >- Accessible* child = aAccessible->ContentChildAt(jdx); >+ //parent. >+ for (uint32_t count = aAccessible->ContentChildCount(); count > 0; count--) { >+ Accessible* child = aAccessible->ContentChildAt(count-1); I think the typical way to write that is uint32_t childCount = ContentChildCount(); for (uint32_t i = length - 1; i < length; i--) > void > HyperTextAccessible::CacheChildren() same comments as for DocAccessible::CacheChildren

(In reply to Trevor Saunders (:tbsaunde) from comment #14) > Comment on attachment 8465090 [details] [diff] [review] > Patch v2 > > > Accessible::BindToParent(Accessible* aParent, uint32_t aIndexInParent) > > { > > NS_PRECONDITION(aParent, "This method isn't used to set null parent!"); > > > > if (mParent) { > > if (mParent != aParent) {> NS_ERROR("Adopting child!"); > >- mParent->RemoveChild(this); > >- mParent->InvalidateChildrenGroupInfo(); > >+ { > >+ AutoChildTreeMutation mut(mParent); > > > should be unnecessary, we should already be within a mutation at this point. We have no guarantee of being in a mutation at this point, and we especially don't have any guarantee of being in a mutation for `mParent` (we're more likely to be in a mutation for `aParent`. You're right that this is unnecessary; it is unnecessary because the call to `RemoveChild` will invoke `UnbindFromParent` which will itself ensure that `InvalidateChildGroupInfo` will be called. Removed this change in the current patch. > >+ mParent->RemoveChild(this); > >+ } > > } else { > > NS_ERROR("Binding to the same parent!"); > > return; > > } > > } > > > > mParent = aParent; > > mIndexInParent = aIndexInParent; > > > >- mParent->InvalidateChildrenGroupInfo(); > >+ if (mParent) { > >+ AutoChildTreeMutation mut(mParent); > >+ } > > same We're not guaranteed to have entered a mutation by the time we call `BindToParent`. I've modified certain locations to enter mutations before calling `BindToParent` (or `InsertChildAt` or `AppendChild` which call `BindToParent`) but we call `AppendChild` all over the place and making every one of those call sites enter a mutation would, I think, be a much larger change than the current patch. > > void > > Accessible::UnbindFromParent() > > { > >- mParent->InvalidateChildrenGroupInfo(); > >+ if (mParent) { > >+ AutoChildTreeMutation mut(mParent); > >+ } > > same, and pretty silly since the scope of the object is just constructing it. I've removed the scope but I've kept the `AutoChildTreeMutation` object. See other reply comments. > > Accessible::InvalidateChildren() > > { > >+ AutoChildTreeMutation mut(this); > > if this is called we should per the API be just about to finish mutatingthe > tree so I don't think there's a point. So just assert that we're in a tree > that's being mutated and do the same for Insert / Remove Child. Changed. > >+ class AutoChildTreeMutation { > >+ public: > >+ AutoChildTreeMutation(Accessible* acc) > >+ : mAccessible(acc) { > >+ mAccessible->mCurrentMutations++; > > I'm pretty sure just having a bit for mutating or not is enough. I've written this patch in a way that allows all existing `BindToParent`/`InsertChildAt`/`AppendChild` calls to be unmodified at their call sites. In cases where we know we are going to call one of those functions multiple times we can create an `AutoChildTreeMutation` object so that `InvalidateChildrenGroupInfo` will not be called until all of the mutations are over. Having a single bit for mutating or not requires modifying all the call sites for `BindToParent` and/or `InsertChildAt` and/or `AppendChild` to know that they need to enter a mutation, and makes recursive calls to those call sites more complicated. Perhaps `mCurrentMutations` is a misleading name; I've renamed it to `mMutationRecursionLevel` in the current patch. Please let me know if you can think of a better name. > >+ } > >+ void Cancel() { > >+ --mAccessible->mCurrentMutations; > >+ mAccessible = nullptr; > >+ } > > afaik the only places this is used is when there's no children, in which > case there's not much point Removed. > >@@ -1493,31 +1493,39 @@ void > > DocAccessible::CacheChildren() > > { > > // Search for accessible children starting from the document element since > > // some web pages tend to insert elements under it rather than document body. > > dom::Element* rootElm = mDocumentNode->GetRootElement(); > > if (!rootElm) > > return; > > > >- // Ignore last HTML:br, copied from HyperTextAccessible. > >+ // Trailing HTML br element don't play any difference. We don't need to expose > >+ // it to AT (see bug https://bugzilla.mozilla.org/show_bug.cgi?id=899433#c16 > >+ // for details). > > why are you changing this? Reverted. > >+ > >+ AutoChildTreeMutation mut(this); > > TreeWalker walker(this, rootElm); > >- Accessible* lastChild = nullptr; > >- while (Accessible* child = walker.NextChild()) { > >- if (lastChild) > >- AppendChild(lastChild); > >- > >- lastChild = child; > >+ Accessible* child = walker.NextChild(); > >+ Accessible* nextChild = child ? walker.NextChild() : nullptr; > >+ while (nextChild) { > >+ InsertChildAt(mChildren.Length(), child); > >+ child = nextChild; > >+ nextChild = walker.NextChild(); > > } > > > >- if (lastChild) { > >- if (lastChild->IsHTMLBr()) > >- Document()->UnbindFromDocument(lastChild); > >- else > >- AppendChild(lastChild); > >+ if (!child) { > >+ mut.Cancel(); > > no point, if that happens there's no kids so we don't really save much by > not calling InvalidateChildrenGroupInfo() Removed. > >+ } else { > >+ if (child->IsHTMLBr()) { > >+ Document()->UnbindFromDocument(child); > >+ mut.Cancel(); > > that's wrong, there could have been a mutation adding children before the br > we're ignoring. Fixed. > > DocAccessible::ShutdownChildrenInSubtree(Accessible* aAccessible) > > { > > // Traverse through children and shutdown them before this accessible. When > > // child gets shutdown then it removes itself from children array of its > >- //parent. Use jdx index to process the cases if child is not attached to the > >- // parent and as result doesn't remove itself from its children. > >- uint32_t count = aAccessible->ContentChildCount(); > >- for (uint32_t idx = 0, jdx = 0; idx < count; idx++) { > >- Accessible* child = aAccessible->ContentChildAt(jdx); > >+ //parent. > >+ for (uint32_t count = aAccessible->ContentChildCount(); count > 0; count--) { > >+ Accessible* child = aAccessible->ContentChildAt(count-1); > > I think the typical way to write that is Changed. > uint32_t childCount = ContentChildCount(); > for (uint32_t i = length - 1; i < length; i--) > > > void > > HyperTextAccessible::CacheChildren() > > same comments as for DocAccessible::CacheChildren Changed.

(In reply to Tim Abraldes [:TimAbraldes] [:tabraldes] from comment #15) > Created attachment 8466385 [details] [diff] [review] > Patch v3 > > (In reply to Trevor Saunders (:tbsaunde) from comment #14) > > Comment on attachment 8465090 [details] [diff] [review] > > Patch v2 > > > > > Accessible::BindToParent(Accessible* aParent, uint32_t aIndexInParent) > > > { > > > NS_PRECONDITION(aParent, "This method isn't used to set null parent!"); > > > > > > if (mParent) { > > > if (mParent != aParent) {> NS_ERROR("Adopting child!"); > > >- mParent->RemoveChild(this); > > >- mParent->InvalidateChildrenGroupInfo(); > > >+ { > > >+ AutoChildTreeMutation mut(mParent); > > > > > > should be unnecessary, we should already be within a mutation at this point. > > We have no guarantee of being in a mutation at this point, and we especially > don't have any guarantee of being in a mutation for `mParent` (we're more > likely to be in a mutation for `aParent`. You're right that this is > unnecessary; it is unnecessary because the call to `RemoveChild` will invoke > `UnbindFromParent` which will itself ensure that `InvalidateChildGroupInfo` > will be called. Removed this change in the current patch. I guess I was unclear, I was saying callers of AppendChild / InsertChild / RemoveChild should be required to first put a auto mutation on the stack. > We're not guaranteed to have entered a mutation by the time we call > `BindToParent`. I've modified certain locations to enter mutations before > calling `BindToParent` (or `InsertChildAt` or `AppendChild` which call > `BindToParent`) but we call `AppendChild` all over the place and making > every one of those call sites enter a mutation would, I think, be a much > larger change than the current patch. there isn't really that many of them, and while it might be larger textually I think its a better design.

Tim, do you have time to finish this one? It looks like bug 1058423 dependent on it.

(In reply to alexander :surkov from comment #17) > Tim, do you have time to finish this one? It looks like bug 1058423 > dependent on it. I've been working on this in my spare time so I can't guarantee anything, but I'm working on it now. I do have something that needs to be resolved before I can continue working on this: From comment 14, it sounds like we want to require callers of `BindToParent`, `UnbindFromParent`, `AppendChild`, `InsertChildAt`, and `RemoveChild` to enter a mutation before calling those functions, and we explicitly DON'T want those functions to enter mutations themselves. One way to implement the above would be to change the signatures of `BindToParent, `UnbindFromParent`, `AppendChild`, `InsertChildAt`, and `RemoveChild` to take as an argument an `AutoChildTreeMutation` reference. That way we have a compile-time requirement that consumers are entering a mutation before calling our functions. There is of course the possibility that the consumer has passed in an `AutoChildTreeMutation` for a different `Accessible`, in which case we would have some kind of runtime failure. If we're not OK with changing the `Accessible` interface, then the best we can do is enforce at runtime that callers of `BindToParent`, `UnbindFromParent`, `AppendChild`, `InsertChildAt`, and `RemoveChild` have entered mutations. We can accomplish this by adding an `NS_PRECONDITION` to the beginning of those functions that checks whether the `Accessible` being modified is currently in a mutation. If we somehow overlook a call site, we will have failures at runtime due to not being in a mutation. I really prefer the approach taken in attachment 8466385 [details] [diff] [review]. It does not require changing the interface of `Accessible`, there is no chance that existing or future code will accidentally cause runtime failures by failing to properly create `AutoChildTreeMutation`s, and it doesn't require finding and modifying every single call site of the functions mentioned above. Additionally, it allows for more complicated usage patterns: Consider `HTMLLIAccessible::CacheChildren`, which calls `AppendChild` and then calls `AccessibleWrap::CacheChildren`. If we use the approach suggested in comment 14, we would have to create an `AutoChildTreeMutation` before calling `AppendChild`, and then we would have to destroy the `AutoChildTreeMutation` before calling `AccessibleWrap::CacheChildren`, which means that `InvalidateChildGroupInfo` will be called twice. If we use the approach taken in attachment 8466385 [details] [diff] [review], we can create a single `AutoChildTreeMutation` before the call to `AppendChild` and we can allow it to survive through the call to `AccessibleWrap::CacheChildren` and on to the end of the function.

(In reply to Tim Abraldes [:TimAbraldes] [:tabraldes] from comment #18) > (In reply to alexander :surkov from comment #17) > > Tim, do you have time to finish this one? It looks like bug 1058423 > > dependent on it. > > I've been working on this in my spare time so I can't guarantee anything, > but I'm working on it now. If you don't mind I think I'm just going to steal it, I think that'll be easier.

(In reply to Trevor Saunders (:tbsaunde) from comment #19) > (In reply to Tim Abraldes [:TimAbraldes] [:tabraldes] from comment #18) > > (In reply to alexander :surkov from comment #17) > > > Tim, do you have time to finish this one? It looks like bug 1058423 > > > dependent on it. > > > > I've been working on this in my spare time so I can't guarantee anything, > > but I'm working on it now. > > > If you don't mind I think I'm just going to steal it, I think that'll be > easier. Feel free!

Still need to give a good think about if the loop is necessary in AssertInMutatingSubtree, but this is the direction I want to go and I think is fairly close.

Comment on attachment 8483697 [details] [diff] [review] wip Review of attachment 8483697 [details] [diff] [review]: ----------------------------------------------------------------- it's nice that we invalidate children only when it's needed, however assertion part may be not faster (what depends on tree deep) than what we do now, especially it looks worse in document shutdown part. At least assertion part must be under debug.

Comment on attachment 8487416 [details] [diff] [review] patch I don't see how you expect to fix anything when you don't remove any calls to InvalidateGroupInfo. Also this is really complicated, I think we need some kind of asserts of correctness. I suspect you need to hand full subtrees not just direct children, but I'm not absolutely sure of that.

(In reply to Trevor Saunders (:tbsaunde) from comment #24) > I don't see how you expect to fix anything when you don't remove any calls > to InvalidateGroupInfo. yeah, forgot to remove them. If you want new patch having this fixed pls let me know. > Also this is really complicated, I think we need > some kind of asserts of correctness. It is nice to have but I do not see good way to implement assertions. We have options 1) have heavy assertion checks 2) aggravate the difference between debug and release 3) just catch bugs 4) something else for example special build config running on test suite If we don't have good ideas for 4 then I think I prefer to do 3. > I suspect you need to hand full subtrees not just direct children, but I'm > not absolutely sure of that. I don't follow that.

(In reply to alexander :surkov from comment #25) > (In reply to Trevor Saunders (:tbsaunde) from comment #24) > > I don't see how you expect to fix anything when you don't remove any calls > > to InvalidateGroupInfo. > > yeah, forgot to remove them. If you want new patch having this fixed pls let > me know. Trev, what about to get landed short version and then file follow up bug? The issue is serious enough to keep the bug unaddressed for long time.

(In reply to alexander :surkov from comment #25) > (In reply to Trevor Saunders (:tbsaunde) from comment #24) > > I don't see how you expect to fix anything when you don't remove any calls > > to InvalidateGroupInfo. > > yeah, forgot to remove them. If you want new patch having this fixed pls let > me know. yes, that'd be useful > > Also this is really complicated, I think we need > > some kind of asserts of correctness. > > It is nice to have but I do not see good way to implement assertions. We > have options > 1) have heavy assertion checks > 2) aggravate the difference between debug and release > 3) just catch bugs > 4) something else for example special build config running on test suite > > If we don't have good ideas for 4 then I think I prefer to do 3. I'd really rather have somewhat slow asserts unless you want to write tests checking correctness for as many crazy edge cases as you can think of. > > I suspect you need to hand full subtrees not just direct children, but I'm > > not absolutely sure of that. > > I don't follow that. I'm suspecting that if you have accessible with children and you insert new child then you need to mark the children's children as having dirty group info too

(In reply to Trevor Saunders (:tbsaunde) from comment #27) > I'm suspecting that if you have accessible with children and you insert new > child then you need to mark the children's children as having dirty group > info too isn't it covered by UpdateTree() part?

I'm not sure what you want from me, you you aren't exactly giving me any more reason to think this is ok. (In reply to alexander :surkov from comment #29) > (In reply to Trevor Saunders (:tbsaunde) from comment #27) > > > I'm suspecting that if you have accessible with children and you insert new > > child then you need to mark the children's children as having dirty group > > info too > > isn't it covered by UpdateTree() part? maybe, I'm not really sure

(In reply to Trevor Saunders (:tbsaunde) from comment #30) > I'm not sure what you want from me, you you aren't exactly giving me any > more reason to think this is ok. I believe we need to get this bug fixed asap, it gets too long. I can see two options for that: 1) get you to review the light patch I proposed 2) get you back to working on the bug to fishing your approach I'm not sure what option we are currently on. What concerns to me either way is fine.

(In reply to alexander :surkov from comment #31) > (In reply to Trevor Saunders (:tbsaunde) from comment #30) > > I'm not sure what you want from me, you you aren't exactly giving me any > > more reason to think this is ok. > > I believe we need to get this bug fixed asap, it gets too long. I can see > two options for that: > 1) get you to review the light patch I proposed > 2) get you back to working on the bug to fishing your approach 3 you can write a patch I like

May this bug be related to Bug 1066165 ?

(In reply to Trevor Saunders (:tbsaunde) from comment #30) > I'm not sure what you want from me, you you aren't exactly giving me any > more reason to think this is ok. > > (In reply to alexander :surkov from comment #29) > > (In reply to Trevor Saunders (:tbsaunde) from comment #27) > > > > > I'm suspecting that if you have accessible with children and you insert new > > > child then you need to mark the children's children as having dirty group > > > info too > > > > isn't it covered by UpdateTree() part? > > maybe, I'm not really sure Alexander can you provide the details here? (It would help me too)

basically child insertion is implemented by UpdateTree() (except some special classes like XUL trees), UpdateTree() takes care to set dirty bits.

(In reply to Trevor Saunders (:tbsaunde) from comment #21) > Created attachment 8483697 [details] [diff] [review] > wip > > Still need to give a good think about if the loop is necessary in > AssertInMutatingSubtree, If nothing else the loop is good future proofing coverage.

(In reply to alexander :surkov from comment #35) > basically child insertion is implemented by UpdateTree() (except some > special classes like XUL trees), UpdateTree() takes care to set dirty bits. actually no, see bug 895082 where CacheChildrenInSubtree does tree creation. so imho its kind of unreasonable to argue that anyone can prove the correctness of this stuff, and given that I think we need either tests or asserts and the latter seem much easier.

Comment on attachment 8493966 [details] [diff] [review] fix O(N^2) runtime of tree update Review of attachment 8493966 [details] [diff] [review]: ----------------------------------------------------------------- ::: accessible/generic/Accessible-inl.h @@ +59,5 @@ > return mRoleMapEntry && mRoleMapEntry->valueRule != eNoValue; > } > > + inline bool > + Accessible::UpdateChildren() nit: wrong indentation ::: accessible/generic/Accessible.h @@ +370,5 @@ > > /** > * Update the children cache. > */ > + inline bool UpdateChildren(); nit: you don't really need inline here? @@ +1022,5 @@ > uint32_t mType : kTypeBits; > uint32_t mGenericTypes : kGenericTypesBits; > > void StaticAsserts() const; > + void AssertInMutatingSubtree() const; are there benefits to keep it under #DEBUG too? @@ +1109,5 @@ > uint32_t mKey; > uint32_t mModifierMask; > }; > > +class AutoTreeMutation please comment it, something like The class is for assertion proposes only to make sure group position is invalidated by every tree update code path. It should be replaced by few direct calls of invalidate group methods when these code paths are covered by automated testing (see also a light version patch of bug 1041070). @@ +1111,5 @@ > }; > > +class AutoTreeMutation > +{ > + public: nit: fix indentation @@ +1127,5 @@ > + MOZ_ASSERT(mRoot->mStateFlags & Accessible::eSubtreeMutating); > + mRoot->mStateFlags &= ~Accessible::eSubtreeMutating; > + } > + > + private: wrong indentation ::: accessible/generic/DocAccessible.cpp @@ +628,5 @@ > mDependentIDsHash.Clear(); > mNodeToAccessibleMap.Clear(); > + > + { > + AutoTreeMutation mut(this); no invalidation required @@ +1476,5 @@ > } > > // Make sure the subtree is created. > + if (accessible) { > + AutoTreeMutation mut(accessible); it's invalidated twice, as part of UpdateChildren() call and here in general this code should be replaced by UpdateTree() routine, we need to file a bug on this @@ +1584,5 @@ > mContent = contentElm; > SetRoleMapEntry(aria::GetRoleMap(mContent)); > } > > + // Build initial tree. Since its the initial tree there's no group info to nit: two spaces before 'Since' @@ +1820,5 @@ > // children because there's no good way to find insertion point of new child > // accessibles into accessible tree. We need to invalidate children even > // there's no inserted accessibles in the end because accessible children > // are created while parent recaches child accessibles. > + AutoTreeMutation mut(this); has to container, not document but it's duped by UpdateTree, right? ::: accessible/html/HTMLImageMapAccessible.cpp @@ +85,5 @@ > if (!imageMapObj) > return; > > bool doReorderEvent = false; > + AutoTreeMutation mut(this); no group position invalidation required, HTML areas don't expose native group position

> @@ +1022,5 @@ > > uint32_t mType : kTypeBits; > > uint32_t mGenericTypes : kGenericTypesBits; > > > > void StaticAsserts() const; > > + void AssertInMutatingSubtree() const; > > are there benefits to keep it under #DEBUG too? don't think so > @@ +1109,5 @@ > > uint32_t mKey; > > uint32_t mModifierMask; > > }; > > > > +class AutoTreeMutation > > please comment it, something like > > The class is for assertion proposes only to make sure group position is > invalidated by every tree update code path. It should be replaced by few > direct calls of invalidate group methods when these code paths are covered > by automated testing (see also a light version patch of bug 1041070). [disagreement box] > ::: accessible/generic/DocAccessible.cpp > @@ +628,5 @@ > > mDependentIDsHash.Clear(); > > mNodeToAccessibleMap.Clear(); > > + > > + { > > + AutoTreeMutation mut(this); > > no invalidation required it sort of is, ClearCache will change the tree, and istr external things being able to poke at things somehow. > @@ +1476,5 @@ > > } > > > > // Make sure the subtree is created. > > + if (accessible) { > > + AutoTreeMutation mut(accessible); > > it's invalidated twice, as part of UpdateChildren() call and here maybe, though I don't think its particularly safe to assume CacheChildrenInSubtee won't create stuff that wasn't there before. > in general this code should be replaced by UpdateTree() routine, we need to > file a bug on this patches welcome I guess. > @@ +1820,5 @@ > > // children because there's no good way to find insertion point of new child > > // accessibles into accessible tree. We need to invalidate children even > > // there's no inserted accessibles in the end because accessible children > > // are created while parent recaches child accessibles. > > + AutoTreeMutation mut(this); > > has to container, not document but it's duped by UpdateTree, right? If I have to bet I'd bet there's a case where its not duplicate. > ::: accessible/html/HTMLImageMapAccessible.cpp > @@ +85,5 @@ > > if (!imageMapObj) > > return; > > > > bool doReorderEvent = false; > > + AutoTreeMutation mut(this); > > no group position invalidation required, HTML areas don't expose native > group position I don't think native matters, GroupInfo works for things like <map role="tree"> <div role="treeitem"> ... I expect (as utterly insane as that is)

(In reply to Trevor Saunders (:tbsaunde) from comment #40) > > > +class AutoTreeMutation > > > > please comment it, something like > > > > The class is for assertion proposes only to make sure group position is > > invalidated by every tree update code path. It should be replaced by few > > direct calls of invalidate group methods when these code paths are covered > > by automated testing (see also a light version patch of bug 1041070). > > [disagreement box] more explanation is on the way I guess? > > ::: accessible/generic/DocAccessible.cpp > > @@ +628,5 @@ > > > mDependentIDsHash.Clear(); > > > mNodeToAccessibleMap.Clear(); > > > + > > > + { > > > + AutoTreeMutation mut(this); > > > > no invalidation required > > it sort of is, ClearCache will change the tree, and istr external things > being able to poke at things somehow. are you saying we need to invalidate group position for shutting down document? > > @@ +1476,5 @@ > > > } > > > > > > // Make sure the subtree is created. > > > + if (accessible) { > > > + AutoTreeMutation mut(accessible); > > > > it's invalidated twice, as part of UpdateChildren() call and here > > maybe, though I don't think its particularly safe to assume > CacheChildrenInSubtee won't create stuff that wasn't there before. it's sort of strange we call CacheChildrenInSubtee on existing accessible because it has to have created subtree but ok it can be dealt as followup. > > @@ +1820,5 @@ > > > // children because there's no good way to find insertion point of new child > > > // accessibles into accessible tree. We need to invalidate children even > > > // there's no inserted accessibles in the end because accessible children > > > // are created while parent recaches child accessibles. > > > + AutoTreeMutation mut(this); > > > > has to container, not document but it's duped by UpdateTree, right? > > If I have to bet I'd bet there's a case where its not duplicate. do you agree that you were supposed to invalidate container rather than document, if so can you provide code path where UpdateTree() doesn't dupe the logic please? > > no group position invalidation required, HTML areas don't expose native > > group position > > I don't think native matters, GroupInfo works for things like > <map role="tree"> > <div role="treeitem"> > ... > > I expect (as utterly insane as that is) ok, I guess web authors could use ARIA on HTML area elements. Anyway, it makes sense to invalidate depending on doReorderEvent.

> > > ::: accessible/generic/DocAccessible.cpp > > > @@ +628,5 @@ > > > > mDependentIDsHash.Clear(); > > > > mNodeToAccessibleMap.Clear(); > > > > + > > > > + { > > > > + AutoTreeMutation mut(this); > > > > > > no invalidation required > > > > it sort of is, ClearCache will change the tree, and istr external things > > being able to poke at things somehow. > > are you saying we need to invalidate group position for shutting down > document? Technically I think so > > > @@ +1476,5 @@ > > > > } > > > > > > > > // Make sure the subtree is created. > > > > + if (accessible) { > > > > + AutoTreeMutation mut(accessible); > > > > > > it's invalidated twice, as part of UpdateChildren() call and here > > > > maybe, though I don't think its particularly safe to assume > > CacheChildrenInSubtee won't create stuff that wasn't there before. > > it's sort of strange we call CacheChildrenInSubtee on existing accessible > because it has to have created subtree but ok it can be dealt as followup. Sure, most of this code is crazy, but that's a preexisting condition. > > > @@ +1820,5 @@ > > > > // children because there's no good way to find insertion point of new child > > > > // accessibles into accessible tree. We need to invalidate children even > > > > // there's no inserted accessibles in the end because accessible children > > > > // are created while parent recaches child accessibles. > > > > + AutoTreeMutation mut(this); > > > > > > has to container, not document but it's duped by UpdateTree, right? > > > > If I have to bet I'd bet there's a case where its not duplicate. > > do you agree that you were supposed to invalidate container rather than > document, if so can you provide code path where UpdateTree() doesn't dupe > the logic please? I think if you assume you don't need to invalidate whole subtree (which I'm not particularly convinced is true) then maybe its always a dup? > > > no group position invalidation required, HTML areas don't expose native > > > group position > > > > I don't think native matters, GroupInfo works for things like > > <map role="tree"> > > <div role="treeitem"> > > ... > > > > I expect (as utterly insane as that is) > > ok, I guess web authors could use ARIA on HTML area elements. Anyway, it > makes sense to invalidate depending on doReorderEvent. I guess, though that's more work.

(In reply to Trevor Saunders (:tbsaunde) from comment #42) > > > it sort of is, ClearCache will change the tree, and istr external things > > > being able to poke at things somehow. > > > > are you saying we need to invalidate group position for shutting down > > document? > > Technically I think so what is a reason to update anything for something we are about to destroy? > > > > @@ +1820,5 @@ > > > > > // children because there's no good way to find insertion point of new child > > > > > // accessibles into accessible tree. We need to invalidate children even > > > > > // there's no inserted accessibles in the end because accessible children > > > > > // are created while parent recaches child accessibles. > > > > > + AutoTreeMutation mut(this); > > > > > > > > has to container, not document but it's duped by UpdateTree, right? > > > > > > If I have to bet I'd bet there's a case where its not duplicate. > > > > do you agree that you were supposed to invalidate container rather than > > document, if so can you provide code path where UpdateTree() doesn't dupe > > the logic please? > > I think if you assume you don't need to invalidate whole subtree (which I'm > not particularly convinced is true) then maybe its always a dup? I'm not sure I follow you. There are two issues here 1) you update group position of the document while the code invalidates children of container accessible. I think this is mistake and you were supposed to invalidate group position on container 2) if that's true then this group position invalidation seems to be covered by group invalidation in UpdateTree() > > > > no group position invalidation required, HTML areas don't expose native > > > > group position > > > > > > I don't think native matters, GroupInfo works for things like > > > <map role="tree"> > > > <div role="treeitem"> > > > ... > > > > > > I expect (as utterly insane as that is) > > > > ok, I guess web authors could use ARIA on HTML area elements. Anyway, it > > makes sense to invalidate depending on doReorderEvent. > > I guess, though that's more work. you can add something like SetInvalidationRequired(bool) method to AutoTreeMutation to override mInvalidationRequired. That adds complexity but AutoTreeMutation approach is complicated already by itself and being a bit faster should be worth of it.

(In reply to alexander :surkov from comment #43) > (In reply to Trevor Saunders (:tbsaunde) from comment #42) > > > > > it sort of is, ClearCache will change the tree, and istr external things > > > > being able to poke at things somehow. > > > > > > are you saying we need to invalidate group position for shutting down > > > document? > > > > Technically I think so > > what is a reason to update anything for something we are about to destroy? people get to look at it before you destroy it, and if they can look at it they may see wrong thing. > > > > > @@ +1820,5 @@ > > > > > > // children because there's no good way to find insertion point of new child > > > > > > // accessibles into accessible tree. We need to invalidate children even > > > > > > // there's no inserted accessibles in the end because accessible children > > > > > > // are created while parent recaches child accessibles. > > > > > > + AutoTreeMutation mut(this); > > > > > > > > > > has to container, not document but it's duped by UpdateTree, right? > > > > > > > > If I have to bet I'd bet there's a case where its not duplicate. > > > > > > do you agree that you were supposed to invalidate container rather than > > > document, if so can you provide code path where UpdateTree() doesn't dupe > > > the logic please? > > > > I think if you assume you don't need to invalidate whole subtree (which I'm > > not particularly convinced is true) then maybe its always a dup? > > I'm not sure I follow you. There are two issues here > 1) you update group position of the document while the code invalidates > children of container accessible. I think this is mistake and you were > supposed to invalidate group position on container yes > 2) if that's true then this group position invalidation seems to be covered > by group invalidation in UpdateTree() I agree it seems to, but it seems better to be safe and make sure. > > > > > no group position invalidation required, HTML areas don't expose native > > > > > group position > > > > > > > > I don't think native matters, GroupInfo works for things like > > > > <map role="tree"> > > > > <div role="treeitem"> > > > > ... > > > > > > > > I expect (as utterly insane as that is) > > > > > > ok, I guess web authors could use ARIA on HTML area elements. Anyway, it > > > makes sense to invalidate depending on doReorderEvent. > > > > I guess, though that's more work. > > you can add something like SetInvalidationRequired(bool) method to > AutoTreeMutation to override mInvalidationRequired. That adds complexity but > AutoTreeMutation approach is complicated already by itself and being a bit > faster should be worth of it. I guess.

(In reply to Trevor Saunders (:tbsaunde) from comment #44) > (In reply to alexander :surkov from comment #43) > > (In reply to Trevor Saunders (:tbsaunde) from comment #42) > > > > > > > it sort of is, ClearCache will change the tree, and istr external things > > > > > being able to poke at things somehow. > > > > > > > > are you saying we need to invalidate group position for shutting down > > > > document? > > > > > > Technically I think so > > > > what is a reason to update anything for something we are about to destroy? > > people get to look at it before you destroy it, and if they can look at it > they may see wrong thing. honestly I can't think of any path how AT can call into us while we shutdown the document. Iirc we had something on ATK side in the past but it was not related that they were needed valid information about shutting down document. > > 2) if that's true then this group position invalidation seems to be covered > > by group invalidation in UpdateTree() > > I agree it seems to, but it seems better to be safe and make sure. after all AutoTreeMutation is supposed to assert if we missed something, I don't see theoretical possibility of missing invalidation thus we should be on a safe side. Actually your patch should assert if we set eSubtreeMutating bit twice so as long as you replace 'this' to container you will get assertion on mochitest run.

(In reply to alexander :surkov from comment #45) > (In reply to Trevor Saunders (:tbsaunde) from comment #44) > > (In reply to alexander :surkov from comment #43) > > > (In reply to Trevor Saunders (:tbsaunde) from comment #42) > > > > > > > > > it sort of is, ClearCache will change the tree, and istr external things > > > > > > being able to poke at things somehow. > > > > > > > > > > are you saying we need to invalidate group position for shutting down > > > > > document? > > > > > > > > Technically I think so > > > > > > what is a reason to update anything for something we are about to destroy? > > > > people get to look at it before you destroy it, and if they can look at it > > they may see wrong thing. > > honestly I can't think of any path how AT can call into us while we shutdown > the document. Iirc we had something on ATK side in the past but it was not > related that they were needed valid information about shutting down document. Well, that proves that they *can*, and if its possible I think we need to handle it correctly. > > > 2) if that's true then this group position invalidation seems to be covered > > > by group invalidation in UpdateTree() > > > > I agree it seems to, but it seems better to be safe and make sure. > > after all AutoTreeMutation is supposed to assert if we missed something, I > don't see theoretical possibility of missing invalidation thus we should be I'm of the opinion this stuff is far too complex to believe you can reason about it correctly. > on a safe side. Actually your patch should assert if we set eSubtreeMutating > bit twice so as long as you replace 'this' to container you will get > assertion on mochitest run. you don't because the scopes are different.

(In reply to Trevor Saunders (:tbsaunde) from comment #46) > (In reply to alexander :surkov from comment #45) > > (In reply to Trevor Saunders (:tbsaunde) from comment #44) > > > (In reply to alexander :surkov from comment #43) > > > > (In reply to Trevor Saunders (:tbsaunde) from comment #42) > > > > > > > > > > > it sort of is, ClearCache will change the tree, and istr external things > > > > > > > being able to poke at things somehow. > > > > > > > > > > > > are you saying we need to invalidate group position for shutting down > > > > > > document? > > > > > > > > > > Technically I think so > > > > > > > > what is a reason to update anything for something we are about to destroy? > > > > > > people get to look at it before you destroy it, and if they can look at it > > > they may see wrong thing. > > > > honestly I can't think of any path how AT can call into us while we shutdown > > the document. Iirc we had something on ATK side in the past but it was not > > related that they were needed valid information about shutting down document. > > Well, that proves that they *can*, and if its possible I think we need to > handle it correctly. > > > > > 2) if that's true then this group position invalidation seems to be covered > > > > by group invalidation in UpdateTree() > > > > > > I agree it seems to, but it seems better to be safe and make sure. > > > > after all AutoTreeMutation is supposed to assert if we missed something, I > > don't see theoretical possibility of missing invalidation thus we should be > > I'm of the opinion this stuff is far too complex to believe you can reason > about it correctly. and since Group info stuff is far from the top of the profile with this patch I don't seem much reason to care if these are absolutely necessary or not. The top 20 - 30% seems to all be calling LinkState() in LinkableAccessible::BindToParent().

(In reply to Trevor Saunders (:tbsaunde) from comment #46) > > honestly I can't think of any path how AT can call into us while we shutdown > > the document. Iirc we had something on ATK side in the past but it was not > > related that they were needed valid information about shutting down document. > > Well, that proves that they *can*, and if its possible I think we need to > handle it correctly. it doesn't prove anything. it's inpractical to update destroying stuff. > > on a safe side. Actually your patch should assert if we set eSubtreeMutating > > bit twice so as long as you replace 'this' to container you will get > > assertion on mochitest run. > > you don't because the scopes are different. I might miss something, maybe you elaborate it? (In reply to Trevor Saunders (:tbsaunde) from comment #47) > > > after all AutoTreeMutation is supposed to assert if we missed something, I > > > don't see theoretical possibility of missing invalidation thus we should be > > > > I'm of the opinion this stuff is far too complex to believe you can reason > > about it correctly. > > and since Group info stuff is far from the top of the profile with this > patch I don't seem much reason to care if these are absolutely necessary or > not. we'll get an assertion if I'm wrong and it's fine.

Comment on attachment 8493966 [details] [diff] [review] fix O(N^2) runtime of tree update canceling review, it'd be good to get a look at next patch when we agreed on issues

Comment on attachment 8488795 [details] [diff] [review] light patch v2 canceling review as we're currently on assertion approach

(In reply to alexander :surkov from comment #48) > (In reply to Trevor Saunders (:tbsaunde) from comment #46) > > > > honestly I can't think of any path how AT can call into us while we shutdown > > > the document. Iirc we had something on ATK side in the past but it was not > > > related that they were needed valid information about shutting down document. > > > > Well, that proves that they *can*, and if its possible I think we need to > > handle it correctly. > > it doesn't prove anything. it's inpractical to update destroying stuff. huh?? If we ever call into external code then they are free to poke at whatever stuff we haven't marked as defunct in any way they choose. > > > on a safe side. Actually your patch should assert if we set eSubtreeMutating > > > bit twice so as long as you replace 'this' to container you will get > > > assertion on mochitest run. > > > > you don't because the scopes are different. > > I might miss something, maybe you elaborate it? Read the code and think about when dtors run, there really isn't more to say. > (In reply to Trevor Saunders (:tbsaunde) from comment #47) > > > > > after all AutoTreeMutation is supposed to assert if we missed something, I > > > > don't see theoretical possibility of missing invalidation thus we should be > > > > > > I'm of the opinion this stuff is far too complex to believe you can reason > > > about it correctly. > > > > and since Group info stuff is far from the top of the profile with this > > patch I don't seem much reason to care if these are absolutely necessary or > > not. > > we'll get an assertion if I'm wrong and it's fine. We don't have any assertion getting Group info has same result as using cache (though may be we should). So I don't see why you believe we'll necessarily get an assert.

(In reply to Trevor Saunders (:tbsaunde) from comment #51) > huh?? If we ever call into external code then they are free to poke at > whatever stuff we haven't marked as defunct in any way they choose. they are free but they don't have a reason to do that. Either way I don't see the way how that could affect on the user. It's not worth spending cycles. > > we'll get an assertion if I'm wrong and it's fine. > > We don't have any assertion getting Group info has same result as using > cache (though may be we should). So I don't see why you believe we'll > necessarily get an assert. you assert whenever you change the tree having no eSubtreeMutating bit set, right? So if you missed AutoTreeMutation somewhere then you should see the assertion.

(In reply to alexander :surkov from comment #52) > (In reply to Trevor Saunders (:tbsaunde) from comment #51) > > > huh?? If we ever call into external code then they are free to poke at > > whatever stuff we haven't marked as defunct in any way they choose. > > they are free but they don't have a reason to do that. Either way I don't > see the way how that could affect on the user. It's not worth spending > cycles. The fact we can't immediately think of a reason someone would do that doesn't mean we can assume they won't. > > > we'll get an assertion if I'm wrong and it's fine. > > > > We don't have any assertion getting Group info has same result as using > > cache (though may be we should). So I don't see why you believe we'll > > necessarily get an assert. > > you assert whenever you change the tree having no eSubtreeMutating bit set, > right? So if you missed AutoTreeMutation somewhere then you should see the > assertion. and I'm pretty sure I did see asserts without both AutoTreeMutation things. For the most part its probably just InvalidateChildren nonsense, but the only way to get around it I see is setting mInvalidate to false in which case we get no asserts.

(In reply to Trevor Saunders (:tbsaunde) from comment #53) > (In reply to alexander :surkov from comment #52) > > (In reply to Trevor Saunders (:tbsaunde) from comment #51) > > > > > huh?? If we ever call into external code then they are free to poke at > > > whatever stuff we haven't marked as defunct in any way they choose. > > > > they are free but they don't have a reason to do that. Either way I don't > > see the way how that could affect on the user. It's not worth spending > > cycles. > > The fact we can't immediately think of a reason someone would do that > doesn't mean we can assume they won't. that's just insane and if there's somebody seeing some practical reason of doing that then I prefer to know it. On the other hand the document is empty when you invalidate group position, so that's just useless piece of code. > > you assert whenever you change the tree having no eSubtreeMutating bit set, > > right? So if you missed AutoTreeMutation somewhere then you should see the > > assertion. > > and I'm pretty sure I did see asserts without both AutoTreeMutation things. could you please attach stacks? I don't see code path, DocAccessible::ProcessContentInserted() simply calls UpdateTree() and they both do AutoTreeMutation

(In reply to alexander :surkov from comment #54) > (In reply to Trevor Saunders (:tbsaunde) from comment #53) > > (In reply to alexander :surkov from comment #52) > > > (In reply to Trevor Saunders (:tbsaunde) from comment #51) > > > > > > > huh?? If we ever call into external code then they are free to poke at > > > > whatever stuff we haven't marked as defunct in any way they choose. > > > > > > they are free but they don't have a reason to do that. Either way I don't > > > see the way how that could affect on the user. It's not worth spending > > > cycles. > > > > The fact we can't immediately think of a reason someone would do that > > doesn't mean we can assume they won't. > > that's just insane and if there's somebody seeing some practical reason of > doing that then I prefer to know it. On the other I really don't want to have to debug why it doesn't work if someone ever files a bug because of it. hand the document is empty > when you invalidate group position, so that's just useless piece of code. yeah, I guess that is true, so I guess technically we should invalidate before calling ClearCache, but I don't really want to bother with that. > > > > you assert whenever you change the tree having no eSubtreeMutating bit set, > > > right? So if you missed AutoTreeMutation somewhere then you should see the > > > assertion. > > > > and I'm pretty sure I did see asserts without both AutoTreeMutation things. > > could you please attach stacks? I don't see code path, > DocAccessible::ProcessContentInserted() simply calls UpdateTree() and they > both do AutoTreeMutation InvalidateChildren calls UnbindFromParent so you need a mutation on the stack when you call that.

(In reply to Trevor Saunders (:tbsaunde) from comment #55) > (In reply to alexander :surkov from comment #54) > > > The fact we can't immediately think of a reason someone would do that > > > doesn't mean we can assume they won't. > > > > that's just insane and if there's somebody seeing some practical reason of > > doing that then I prefer to know it. On the other > > I really don't want to have to debug why it doesn't work if someone ever > files a bug because of it. I believe you won't. > hand the document is empty > > when you invalidate group position, so that's just useless piece of code. > > yeah, I guess that is true, so I guess technically we should invalidate > before calling ClearCache, but I don't really want to bother with that. so you don't need to even try to invalidate > > could you please attach stacks? I don't see code path, > > DocAccessible::ProcessContentInserted() simply calls UpdateTree() and they > > both do AutoTreeMutation > > InvalidateChildren calls UnbindFromParent so you need a mutation on the > stack when you call that. ok, that's one more downside of assertion approach, having to invalidate things twice. So what left: 1) proper comment for the class and style fixes 2) no invalidation for destroying document since it's quite confusing 3) no invalidation for image map when no change what do you think?

> > > could you please attach stacks? I don't see code path, > > > DocAccessible::ProcessContentInserted() simply calls UpdateTree() and they > > > both do AutoTreeMutation > > > > InvalidateChildren calls UnbindFromParent so you need a mutation on the > > stack when you call that. > > ok, that's one more downside of assertion approach, having to invalidate > things twice. your assuming its not necessary, which I'm not convinced is true.

(In reply to Trevor Saunders (:tbsaunde) from comment #57) > > > InvalidateChildren calls UnbindFromParent so you need a mutation on the > > > stack when you call that. > > > > ok, that's one more downside of assertion approach, having to invalidate > > things twice. > > your assuming its not necessary, which I'm not convinced is true. how could it be otherwise? ProcessContentInserted calls UpdateTree which has AutoTreeMutation, there's no return on the path. It looks pretty straight forward. Did I miss something?

Comment on attachment 8496258 [details] [diff] [review] fix O(N^2) runtime of tree update Review of attachment 8496258 [details] [diff] [review]: ----------------------------------------------------------------- ::: accessible/generic/Accessible.h @@ +1110,5 @@ > uint32_t mModifierMask; > }; > > +/** > + * This class makes sure Required tasks are done before and after tree lowecase "required" @@ +1111,5 @@ > }; > > +/** > + * This class makes sure Required tasks are done before and after tree > + * mutations. Currently this only includes group info invalidation. YOu must extra space after both sentences. lowercase o in You. @@ +1113,5 @@ > +/** > + * This class makes sure Required tasks are done before and after tree > + * mutations. Currently this only includes group info invalidation. YOu must > + * have an object of this class on the stack when calling methods that mutate > + * the accessible tree. I'm not sure why you insist that we need to use this class over test coverage since this approach has bunch of noticeable disadvantages so I suggest to extend the comment to address this. I personally fine with wording I gave in comment #39. ::: accessible/generic/DocAccessible.cpp @@ +1822,5 @@ > // children because there's no good way to find insertion point of new child > // accessibles into accessible tree. We need to invalidate children even > // there's no inserted accessibles in the end because accessible children > // are created while parent recaches child accessibles. > + AutoTreeMutation mut(aContainer); per comment #58 (if it's valid) it'd be good to comment here that this AutoTreeMutation is to avoid assertion, no group invalidation is required. ::: accessible/html/HTMLImageMapAccessible.cpp @@ +135,4 @@ > mDoc->FireDelayedEvent(reorderEvent); > + > + if (!treeChanged) > + mut.mInvalidationRequired = false; thinking more on this, it sounds like we trick here ourselves, i.e if we think we don't mutate the tree then we should not have AutoTreeMutation object on the stack. Otherwise AutoTreeMutation won't assert when tree is changed but group info is not invalidated.

(In reply to Sandor from comment #33) > May this bug be related to Bug 1066165 ? I've tried the bug-1066165-problem with FF31.2.0 published on the 7th of October but it still exist :( Trevor, does FF31.2.0 contain your 2014-10-07-changeset?

It will be landed in Firefox 35. I think it can be backported to 34 but that's likely all we can do.

I am interested in only the esr-versions. Do you mean, following FF31esr-subversions not but the FF38esr will this fix contain?

[Tracking Requested - why for this release]: if 38 is next esr then yes, I'm not sure about backporting to existing esr, that must be something quite serious, perhaps this bug is, need somebody to comment about criteria

Could you send me a setup exe (or a link) with this changeset in order to try if it fixes my problem? So we could tell our customers the status of the Bug 1066165.

it's not landed on trunk yet, but I think it will be available in few days in nightlies (https://nightly.mozilla.org/).

(In reply to alexander :surkov from comment #65) > [Tracking Requested - why for this release]: > > if 38 is next esr then yes, I'm not sure about backporting to existing esr, > that must be something quite serious, perhaps this bug is, need somebody to > comment about criteria Correct, this will have to be in the next ESR (38) as it doesn't fit the criteria for backports during the time of ESR31.

(In reply to alexander :surkov from comment #67) > it's not landed on trunk yet, but I think it will be available in few days > in nightlies (https://nightly.mozilla.org/). Can we get this soon? It will also help greatly with Thunderbird performance issue bug 939462

it has been landed a while ago http://hg.mozilla.org/mozilla-central/rev/6525c7ee1f50

(In reply to alexander :surkov from comment #70) > it has been landed a while ago > http://hg.mozilla.org/mozilla-central/rev/6525c7ee1f50 So this should be available in current beta. Thanks. But I'm feeling dense - this landed between comment 20 and comment 21, so what is everything through comment 62 about?

that's interesting question :) maybe there's something wrong with dates.

(In reply to alexander :surkov from comment #3) > (In reply to Tim Abraldes [:TimAbraldes] [:tabraldes] from comment #0) > > > Issue #1: > > agree, it's reasonable > > (In reply to Trevor Saunders (:tbsaunde) from comment #1) > > > On first thought that seems correct though I don't think I've ever seen > > this show up high in profiles. > > probably because it's more or less recent change Do we know, was the regression in disability code? Or other code? Do we know which bug or patch made the change? Why is the checkin date bogus (Tue, 02 Sep 2014) for https://hg.mozilla.org/integration/mozilla-inbound/rev/6525c7ee1f50

(In reply to Wayne Mery (:wsmwk, use Needinfo for questions) from comment #73) > (In reply to alexander :surkov from comment #3) > > (In reply to Tim Abraldes [:TimAbraldes] [:tabraldes] from comment #0) > > > > > Issue #1: > > > > agree, it's reasonable > > > > (In reply to Trevor Saunders (:tbsaunde) from comment #1) > > > > > On first thought that seems correct though I don't think I've ever seen > > > this show up high in profiles. > > > > probably because it's more or less recent change > > Do we know, was the regression in disability code? Or other code? > Do we know which bug or patch made the change? I think it was bug 844023 > Why is the checkin date bogus (Tue, 02 Sep 2014) for > https://hg.mozilla.org/integration/mozilla-inbound/rev/6525c7ee1f50 dates in commits are *not* checkin dates so its not bogus it just doesn't tell you when it first showed up in any particular public repo.