If you think a bug might affect users in the 57 release, please set the correct tracking and status flags for Release Management.

derecursify TreeWalker::NextChild

RESOLVED FIXED in mozilla34

Status

()

Core
Disability Access APIs
RESOLVED FIXED
3 years ago
3 years ago

People

(Reporter: tbsaunde, Assigned: tbsaunde)

Tracking

unspecified
mozilla34
x86_64
Linux
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(2 attachments, 2 obsolete attachments)

Comment hidden (empty)
(Assignee)

Comment 1

3 years ago
Created attachment 8471090 [details] [diff] [review]
derecursify TreeWalker::NextChild
Attachment #8471090 - Flags: review?(surkov.alexander)

Comment 2

3 years ago
Comment on attachment 8471090 [details] [diff] [review]
derecursify TreeWalker::NextChild

Review of attachment 8471090 [details] [diff] [review]:
-----------------------------------------------------------------

::: accessible/base/TreeWalker.cpp
@@ +51,5 @@
>      return nullptr;
>  
> +  dom::AllChildrenIterator* top = &mStateStack[mStateStack.Length() - 1];
> +  while (top) {
> +  while (nsIContent* childNode = top->GetNextChild()) {

nit: please indent it properly
doesn't it warn about assignment inside while()?

@@ +74,5 @@
>    // relative anchor node within the context subtree if possible.
>    if (mFlags != eWalkContextTree)
>      return nullptr;
>  
> +  mFlags &= ~eWalkContextTree;

so you get here one time only which means you will ignore next after next elements like

<context>
  <div>anchored</div><div>next</div><div>next after next(ignored)</div>
</context>

@@ +85,5 @@
>  
> +    nsIContent* parent = parentNode->AsElement();
> +    top =
> +      mStateStack.InsertElementAt(0, dom::AllChildrenIterator(parent,
> +                                                              mChildFilter));

do you really need to have parent on stack even if it doesn't have children

@@ +102,3 @@
>  TreeWalker::PopState()
>  {
> +  size_t length = mStateStack.Length();

it looks like you don't need local variable for length

@@ +102,4 @@
>  TreeWalker::PopState()
>  {
> +  size_t length = mStateStack.Length();
> +  mStateStack.RemoveElementAt(length - 1);

it doesn't reallocate the array, correct?

@@ +107,3 @@
>  }
>  
> +  dom::AllChildrenIterator*

nit: wrong indent

@@ +110,4 @@
>  TreeWalker::PushState(nsIContent* aContent)
>  {
> +  return mStateStack.AppendElement(dom::AllChildrenIterator(aContent,
> +                                                            mChildFilter));

shouldn't it be inline thing?

::: accessible/base/TreeWalker.h
@@ +16,5 @@
>  namespace mozilla {
>  namespace a11y {
>  
>  class Accessible;
>  class DocAccessible;

you didn't remove class WalkState, right?
(Assignee)

Comment 3

3 years ago
> ::: accessible/base/TreeWalker.cpp
> @@ +51,5 @@
> >      return nullptr;
> >  
> > +  dom::AllChildrenIterator* top = &mStateStack[mStateStack.Length() - 1];
> > +  while (top) {
> > +  while (nsIContent* childNode = top->GetNextChild()) {
> 
> nit: please indent it properly
> doesn't it warn about assignment inside while()?

apparently not, I guess because the variable being assigned to is also being declared there.

> @@ +74,5 @@
> >    // relative anchor node within the context subtree if possible.
> >    if (mFlags != eWalkContextTree)
> >      return nullptr;
> >  
> > +  mFlags &= ~eWalkContextTree;
> 
> so you get here one time only which means you will ignore next after next
> elements like
> 
> <context>
>   <div>anchored</div><div>next</div><div>next after next(ignored)</div>
> </context>

running the following code only once is intended.  The basic idea is that we build up a context stack the same as if accessible for mNode was mContext, and we had already iterated to end of children of actual mContext.

> @@ +85,5 @@
> >  
> > +    nsIContent* parent = parentNode->AsElement();
> > +    top =
> > +      mStateStack.InsertElementAt(0, dom::AllChildrenIterator(parent,
> > +                                                              mChildFilter));
> 
> do you really need to have parent on stack even if it doesn't have children

its not absolutely necessary, but its much simpler and I doubt it would be any cheaper to remove it when you find your already on the last child.

> @@ +102,3 @@
> >  TreeWalker::PopState()
> >  {
> > +  size_t length = mStateStack.Length();
> 
> it looks like you don't need local variable for length

its used twice, seems simpler to keep it.

> @@ +102,4 @@
> >  TreeWalker::PopState()
> >  {
> > +  size_t length = mStateStack.Length();
> > +  mStateStack.RemoveElementAt(length - 1);
> 
> it doesn't reallocate the array, correct?

not that I'm aware of though if it does I believe that's fine.
(Assignee)

Comment 4

3 years ago
Created attachment 8472981 [details] [diff] [review]
derecursify TreeWalker::NextChild
Attachment #8471090 - Attachment is obsolete: true
Attachment #8471090 - Flags: review?(surkov.alexander)
Attachment #8472981 - Flags: review?(surkov.alexander)

Comment 5

3 years ago
Comment on attachment 8472981 [details] [diff] [review]
derecursify TreeWalker::NextChild

Review of attachment 8472981 [details] [diff] [review]:
-----------------------------------------------------------------

r=me

::: accessible/base/TreeWalker.cpp
@@ -113,5 @@
>  
> -    PushState(parentNode->AsElement());
> -    while (nsIContent* childNode = mState->iter.GetNextChild()) {
> -      if (childNode == anchorNode)
> -        return NextChildInternal(false);

still not sure if getting rid of much of recursion here is worth to do. It seems like we could keep the approach of this part of code unchanged.

@@ +88,5 @@
> +      mStateStack.InsertElementAt(0, dom::AllChildrenIterator(parent,
> +                                                              mChildFilter));
> +    while (nsIContent* childNode = top->GetNextChild()) {
> +      if (childNode == anchorNode) {
> +    anchorNode = parent;

nit: wrong indentation

::: accessible/base/TreeWalker.h
@@ +76,4 @@
>  
>    DocAccessible* mDoc;
>    Accessible* mContext;
> +  nsIContent* mNode;

maybe rename it to mAnchorNode? mNode is too generic
Attachment #8472981 - Flags: review?(surkov.alexander) → review+
(Assignee)

Comment 6

3 years ago
> ::: accessible/base/TreeWalker.cpp
> @@ -113,5 @@
> >  
> > -    PushState(parentNode->AsElement());
> > -    while (nsIContent* childNode = mState->iter.GetNextChild()) {
> > -      if (childNode == anchorNode)
> > -        return NextChildInternal(false);
> 
> still not sure if getting rid of much of recursion here is worth to do. It
> seems like we could keep the approach of this part of code unchanged.

I'm not sure I see a nice way to leave it the way it is, and I don't think new approach is really worse than old one.

Comment 7

3 years ago
shoudln't something like work?

if (mFlags != eWalkContextTree)
  return nullptr;

if (anchorNode == mContext->GetNode())
  return nullptr;

nsINode* parentNode = anchorNode->GetFlattenedTreeParent();
if (!parentNode || !parentNode->IsElement())
  return nullptr;

dom::AllChildrenIterator* it = PushState(parentNode->AsElement());
while (nsIContent* childNode = it->GetNextChild()) {
if (childNode == anchorNode) {
  mAnchorNode = parentNode;
  return NextChild();
}
(Assignee)

Comment 8

3 years ago
Created attachment 8473057 [details] [diff] [review]
derecursify TreeWalker::NextChild
Attachment #8472981 - Attachment is obsolete: true
Attachment #8473057 - Flags: review?(surkov.alexander)

Updated

3 years ago
Attachment #8473057 - Flags: review?(surkov.alexander) → review+
(Assignee)

Comment 9

3 years ago
https://hg.mozilla.org/integration/mozilla-inbound/rev/891c2e1b0e93
Reverted for build failures on several platforms: "error: no matching constructor for initialization of 'mozilla::dom::AllChildrenIterator'".

Logs:
https://tbpl.mozilla.org/php/getParsedLog.php?id=45953292&tree=Mozilla-Inbound
https://tbpl.mozilla.org/php/getParsedLog.php?id=45953481&tree=Mozilla-Inbound

Log excerpt:
{
In file included from build/obj-firefox/i386/accessible/base/Unified_cpp_accessible_base1.cpp:2:
In file included from build/accessible/base/TextRange.cpp:7:
In file included from build/accessible/base/TextRange.h:14:
../../dist/include/nsTArray.h:483:34: error: no matching constructor for initialization of 'mozilla::dom::AllChildrenIterator'
    new (static_cast<void*>(aE)) E(mozilla::Forward<A>(aArg));
                                 ^ ~~~~~~~~~~~~~~~~~~~~~~~~~
../../dist/include/nsTArray.h:1290:39: note: in instantiation of function template specialization 'nsTArrayElementTraits<mozilla::dom::AllChildrenIterator>::Construct<mozilla::dom::AllChildrenIterator>' requested here
    nsTArrayElementTraits<elem_type>::Construct(iter, mozilla::Forward<elem_type>(aItem));
                                      ^
/builds/slave/m-in-osx64-0000000000000000000/build/accessible/base/TreeWalker.h:68:24: note: in instantiation of member function 'nsTArray_Impl<mozilla::dom::AllChildrenIterator, nsTArrayInfallibleAllocator>::AppendElement' requested here
    return mStateStack.AppendElement(dom::AllChildrenIterator(aContent,
                       ^
../../dist/include/mozilla/dom/ChildIterator.h:144:7: note: candidate constructor (the implicit copy constructor) not viable: expects an l-value for 1st argument
class AllChildrenIterator : private FlattenedChildIterator
      ^
../../dist/include/mozilla/dom/ChildIterator.h:147:3: note: candidate constructor not viable: requires 2 arguments, but 1 was provided
  AllChildrenIterator(nsIContent* aNode, uint32_t aFlags) :
  ^
1 error generated.
make[6]: *** [Unified_cpp_accessible_base1.o] Error 1
}

Backout commit:
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/86954c95768d
Assignee: nobody → trev.saunders
Status: NEW → ASSIGNED
(Assignee)

Comment 11

3 years ago
https://hg.mozilla.org/integration/mozilla-inbound/rev/a7840102579b
https://hg.mozilla.org/mozilla-central/rev/a7840102579b
Status: ASSIGNED → RESOLVED
Last Resolved: 3 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla34

Comment 13

3 years ago
This patch is causing the following regression:
Str:
1. Focus the location bar.
2. Type foo bar.
3. Get the word offsets for offset 4.
Result: Application stops responding and CPU usage spikes. Seems like an infinite loop.
I've no idea how this change is causing this, but backing out changeset a7840102579b fixes the problem.
Thanks fot the catch, jamie! Given that there's a U.S. and Canada holiday today, and that there is an uplift tomorrow, I'm requesting from sheriffs that this be backed out and reopened.
backed out in remote:   https://hg.mozilla.org/mozilla-central/rev/532b5fb77ba on request by marcoz for causing regressions
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
(Assignee)

Comment 16

3 years ago
(In reply to Marco Zehe (:MarcoZ) from comment #14)
> Thanks fot the catch, jamie! Given that there's a U.S. and Canada holiday
> today, and that there is an uplift tomorrow, I'm requesting from sheriffs
> that this be backed out and reopened.

arg, I really wish you hadn't, there was no good reason fixing that couldn't wait a day or two.

Comment 17

3 years ago
(In reply to Trevor Saunders (:tbsaunde) from comment #16)
> arg, I really wish you hadn't, there was no good reason fixing that couldn't
> wait a day or two.
FWIW, it's actually a pretty serious issue. The str I gave is just one demonstration. It happens in a lot of other cases too, some which are easy to reproduce (e.g. simply press f12) and some which I haven't figured out exactly how to reproduce.
(Assignee)

Comment 18

3 years ago
(In reply to James Teh [:Jamie] from comment #17)
> (In reply to Trevor Saunders (:tbsaunde) from comment #16)
> > arg, I really wish you hadn't, there was no good reason fixing that couldn't
> > wait a day or two.
> FWIW, it's actually a pretty serious issue. The str I gave is just one
> demonstration. It happens in a lot of other cases too, some which are easy
> to reproduce (e.g. simply press f12) and some which I haven't figured out
> exactly how to reproduce.

Sure its important, but nobody was going to die if it took another day or two, running trunk is signing up for some pain ;)
(In reply to Trevor Saunders (:tbsaunde) from comment #18)
> Sure its important, but nobody was going to die if it took another day or
> two, running trunk is signing up for some pain ;)

It was a holiday in the U.S. and Canada, and the merge to Aurora was going to happen the next day, which meant that this regression would have uplifted to that channel. I had seen some strange behavior like Jamie described myself, so I decided it was less painful to back it out and not uplift this to Aurora, than to let it ride the train and then back it out from there etc if a fix hadn't been created in time. Now, we have time to properly implement this bug without regressions.
(Assignee)

Comment 20

3 years ago
Created attachment 8484347 [details] [diff] [review]
fixup
Attachment #8484347 - Flags: review?(surkov.alexander)

Updated

3 years ago
Attachment #8484347 - Flags: review?(surkov.alexander) → review+
(Assignee)

Comment 21

3 years ago
https://hg.mozilla.org/integration/mozilla-inbound/rev/25a373fa9dbf
https://hg.mozilla.org/mozilla-central/rev/25a373fa9dbf
Status: REOPENED → RESOLVED
Last Resolved: 3 years ago3 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.