Closed Bug 1052122 Opened 10 years ago Closed 10 years ago

derecursify TreeWalker::NextChild

Categories

(Core :: Disability Access APIs, defect)

x86_64
Linux
defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla34

People

(Reporter: tbsaunde, Assigned: tbsaunde)

Details

Attachments

(2 files, 2 obsolete files)

      No description provided.
Attachment #8471090 - Flags: review?(surkov.alexander)
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?
> ::: 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.
Attachment #8471090 - Attachment is obsolete: true
Attachment #8471090 - Flags: review?(surkov.alexander)
Attachment #8472981 - Flags: review?(surkov.alexander)
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+
> ::: 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.
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();
}
Attachment #8472981 - Attachment is obsolete: true
Attachment #8473057 - Flags: review?(surkov.alexander)
Attachment #8473057 - Flags: review?(surkov.alexander) → review+
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
https://hg.mozilla.org/mozilla-central/rev/a7840102579b
Status: ASSIGNED → RESOLVED
Closed: 10 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla34
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 → ---
(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.
(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.
(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.
Attached patch fixupSplinter Review
Attachment #8484347 - Flags: review?(surkov.alexander)
Attachment #8484347 - Flags: review?(surkov.alexander) → review+
https://hg.mozilla.org/mozilla-central/rev/25a373fa9dbf
Status: REOPENED → RESOLVED
Closed: 10 years ago10 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: