Closed Bug 1336215 Opened 7 years ago Closed 7 years ago

nsDeque's range-for should accommodate deque size changes, like ForEach

Categories

(Core :: XPCOM, defect)

49 Branch
defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla54
Tracking Status
firefox54 --- fixed

People

(Reporter: mozbugz, Assigned: mozbugz)

References

Details

Attachments

(3 files)

nsDeque's iterator (introduced in bug 1322700 to enable range-for) creates the end-iterator as a fixed point based on the deque size at that time, meaning that if the size changes during the loop, we would still iterate over the initial size -- which is worse than ForEach or even a hand-crafted `for(int i = 0; i < deque.GetSize(); ++i)` loop!

Instead the end-iterator should work in such a way that it will somehow track the current deque size.
Assignee: nobody → gsquelart
FYI, existing typo in part 1, first hunk:
via an interator class
--------^

New typo in part 1: "needee" (twice)

I suspect that "@param   item to store in deque" should really be
"@param aItem  item to store in deque".
Thank you Mats, fixed & improved doc again.
(Funnily enough, the mentioned "interator" was never implemented!)
Comment on attachment 8833129 [details]
Bug 1336215 - More complete and consistent nsDeque doc, deleted special copy members -

https://reviewboard.mozilla.org/r/109352/#review111196
Attachment #8833129 - Flags: review?(nfroyd) → review+
Comment on attachment 8833130 [details]
Bug 1336215 - Make nsDeque::ConstIterator resistant to size changes -

https://reviewboard.mozilla.org/r/109354/#review111200

Looks good, I think.  I kind of want `EffectiveIndex` to return a `Maybe<size_t`, but that would make the comparison functions quite ugly.

::: xpcom/ds/nsDeque.h:205
(Diff revision 3)
> +    // Effective index (0 <= index <= deque.GetSize()), for comparisons.
> +    size_t EffectiveIndex() const

Perhaps this method should be private.

::: xpcom/ds/nsDeque.h:205
(Diff revision 3)
> +      // End-iterator shouldn't be modified.
> +      MOZ_ASSERT(mIndex != EndIteratorIndex);
> +      ++mIndex;
> +      return *this;
> +    }
> +    // Effective index (0 <= index <= deque.GetSize()), for comparisons.

This comment should have `0 <= index < deque.GetSize()`, right?

::: xpcom/ds/nsDeque.h:221
(Diff revision 3)
> +      return EffectiveIndex() != aOther.EffectiveIndex();
> +    }
> +    void* operator*() const
> +    {
> +      // Don't allow out-of-deque dereferences.
> +      MOZ_ASSERT(mIndex < mDeque.GetSize());

I'm inclined to make this `MOZ_RELEASE_ASSERT`.
Attachment #8833130 - Flags: review?(nfroyd) → review+
Comment on attachment 8833131 [details]
Bug 1336215 - Optimize iterator if nsDeque is const -

https://reviewboard.mozilla.org/r/109356/#review111208

::: xpcom/ds/nsDeque.h:210
(Diff revision 4)
> +      return mIndex != aOther.mIndex;
> +    }
> +    void* operator*() const
> +    {
> +      // Don't allow out-of-deque dereferences.
> +      MOZ_ASSERT(mIndex < mDeque.GetSize());

`MOZ_RELEASE_ASSERT`, please.
Attachment #8833131 - Flags: review?(nfroyd) → review+
Comment on attachment 8833130 [details]
Bug 1336215 - Make nsDeque::ConstIterator resistant to size changes -

https://reviewboard.mozilla.org/r/109354/#review111200

I'm using deque.GetSize() as the "outside" value, and it's only used internally in the comparison functions.

> Perhaps this method should be private.

Indeed. Also the code didn't match the documentation, so I'll fix that (by returning at most deque.GetSize()).

> This comment should have `0 <= index < deque.GetSize()`, right?

No, deque.GetSize() is the 1-past-the-end value that identifies any index outside of the deque.
As noted, this is only used for index comparisons, not to actually access elements.
I'll clarify all this in the comment.

> I'm inclined to make this `MOZ_RELEASE_ASSERT`.

When used in a range-for, it should never happen! But then nsDeque's begin&end are public, so this iterator could be abused.
Since this check is a tiny cost, but with big benefits in case of trouble, I'll go ahead with it. Thank you for the suggestion.
Pushed by gsquelart@mozilla.com:
https://hg.mozilla.org/integration/autoland/rev/f321cc0af904
More complete and consistent nsDeque doc, deleted special copy members - r=froydnj
https://hg.mozilla.org/integration/autoland/rev/d969e512cd1d
Make nsDeque::ConstIterator resistant to size changes - r=froydnj
https://hg.mozilla.org/integration/autoland/rev/f24e0917fd60
Optimize iterator if nsDeque is const - r=froydnj
You need to log in before you can comment on or make changes to this bug.