1127044 - Make nsTArray support reverse iterating with STL sematics

Status: RESOLVED FIXED

(Core :: MFBT, defect)

Description

[Xidorn Quan [:xidorn] UTC+11]

Add mozilla::Reversed and mozilla::ReverseIterator to MFBT, and add rbegin() and rend() to nsTArray.

Comment 1

[Xidorn Quan [:xidorn] UTC+11]

Probably we can use std::reverse_iterator directly, can we?

Comment 2

[Xidorn Quan [:xidorn] UTC+11]

Attachment: patch 1 - Add IteratorTraits

Comment 3

[Xidorn Quan [:xidorn] UTC+11]

Attachment: patch 2 - Add ReverseIterator

Comment 4

[Xidorn Quan [:xidorn] UTC+11]

Attachment: patch 3 - Add reverse iterator to nsTArray

Comment 5

[Xidorn Quan [:xidorn] UTC+11]

Attachment: patch 4 - Add helper class & functions for reversing

Comment 6

[Xidorn Quan [:xidorn] UTC+11]

Attachment: usage example

Comment 7

[Xidorn Quan [:xidorn] UTC+11]

Attachment: patch 2 - Add ReverseIterator

Submitted the wrong one...

Comment 8

[Nathan Froyd [:froydnj]]

Comment on attachment 8557746 [details] [diff] [review]
patch 3 - Add reverse iterator to nsTArray

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

::: xpcom/glue/nsTArray.h
@@ +1011,5 @@
> +    return const_reverse_iterator(end() - 1);
> +  }
> +  reverse_iterator rend()
> +  {
> +    return reverse_iterator(begin() - 1);

I think this is technically undefined behavior; see [expr.add]p5 in the C++ standard.  The result here doesn't point into the "array object" of |elem_type*|.  (I realize it points at valid memory belonging to the nsTArray, but still...)

The reverse_iterator() implementation needs to be improved; see [reverse.iterators]p1 in the C++ standard.

Comment 9

[Xidorn Quan [:xidorn] UTC+11]

Attachment: patch 2 - Add ReverseIterator

Comment 10

[Xidorn Quan [:xidorn] UTC+11]

Attachment: patch 3 - Add reverse iterator to nsTArray

Comment 11

[Xidorn Quan [:xidorn] UTC+11]

Attachment: patch 4 - Add helper class & functions for reversing

Comment 12

[Xidorn Quan [:xidorn] UTC+11]

try: https://treeherder.mozilla.org/#/jobs?repo=try&revision=a7e5f52141c5

Comment 13

[Nathan Froyd [:froydnj]]

Comment on attachment 8558137 [details] [diff] [review]
patch 3 - Add reverse iterator to nsTArray

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

This looks better, thank you!

Comment 14

[Jeff Walden [:Waldo]]

Comment on attachment 8557743 [details] [diff] [review]
patch 1 - Add IteratorTraits

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

::: mfbt/IteratorTraits.h
@@ +3,5 @@
> +/* This Source Code Form is subject to the terms of the Mozilla Public
> + * License, v. 2.0. If a copy of the MPL was not distributed with this
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> +
> +/* Template-based metaprogramming facilities for iterators */

/* Iterator traits to expose a value type and a difference type. */

@@ +8,5 @@
> +
> +#ifndef mozilla_IteratorTraits_h
> +#define mozilla_IteratorTraits_h
> +
> +#include "mozilla/Types.h"

Use <stddef.h> directly, not this header.

@@ +16,5 @@
> +template<typename Iterator>
> +struct IteratorTraits
> +{
> +  typedef typename Iterator::ValueType      ValueType;
> +  typedef typename Iterator::DifferenceType DifferenceType;

Please get rid of the attempted vertical alignment here and elsewhere.  Such things become misaligned over time, and it ends up just being a nuisance.  Better not to bother.

Comment 15

[Jeff Walden [:Waldo]]

Comment on attachment 8558135 [details] [diff] [review]
patch 2 - Add ReverseIterator

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

::: mfbt/ReverseIterator.h
@@ +3,5 @@
> +/* This Source Code Form is subject to the terms of the Mozilla Public
> + * License, v. 2.0. If a copy of the MPL was not distributed with this
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> +
> +/* An iterator which reverse the direction of another iterator. */

Slight wording adjustment:

An iterator that acts like another iterator, but iterating in the negative direction.  (Note that not all iterators can iterate in the negative direction.)

(And for what it's worth, "which reverse the direction" isn't correct English, just to note.  :-) )

@@ +24,5 @@
> +  explicit ReverseIterator(Iterator aIter)
> +    : mCurrent(aIter) { }
> +
> +  template<typename Iterator>
> +  ReverseIterator(const ReverseIterator<Iterator>& aOther)

You're going to need a MOZ_IMPLICIT on this for it to compile on static-analysis builds.  Same for the previous patches of yours I've reviewed today, if I forgot to say it.  Or can they just be explicit?

@@ +33,5 @@
> +    IteratorT tmp = mCurrent;
> +    return *--tmp;
> +  }
> +
> +  /* Increments and descrements operators */

decrements

@@ +85,5 @@
> +  IteratorT mCurrent;
> +};
> +
> +template<typename Iterator1, typename Iterator2>
> +bool operator==(const ReverseIterator<Iterator1>& aIter1,

Hmm, forgot to say it on the other patches.  Use this formatting:

template<typename Iterator1, typename Iterator2>
bool
operator==(...,
           ...)
{
  ...
}

Comment 16

[Xidorn Quan [:xidorn] UTC+11]

(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #15)
> Comment on attachment 8558135 [details] [diff] [review]
> patch 2 - Add ReverseIterator
> 
> Review of attachment 8558135 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: mfbt/ReverseIterator.h
> @@ +24,5 @@
> > +  explicit ReverseIterator(Iterator aIter)
> > +    : mCurrent(aIter) { }
> > +
> > +  template<typename Iterator>
> > +  ReverseIterator(const ReverseIterator<Iterator>& aOther)
> 
> You're going to need a MOZ_IMPLICIT on this for it to compile on
> static-analysis builds.  Same for the previous patches of yours I've
> reviewed today, if I forgot to say it.  Or can they just be explicit?

Do we generally mark copy constructor |explicit|? I guess adding MOZ_IMPLICIT here is enough. STL containers don't add |explicit| to their copy constructors, either.

Comment 17

[Nathan Froyd [:froydnj]]

(In reply to Xidorn Quan [:xidorn] (UTC+11) from comment #16)
> (In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #15)
> > Comment on attachment 8558135 [details] [diff] [review]
> > patch 2 - Add ReverseIterator
> > 
> > Review of attachment 8558135 [details] [diff] [review]:
> > -----------------------------------------------------------------
> > 
> > ::: mfbt/ReverseIterator.h
> > @@ +24,5 @@
> > > +  explicit ReverseIterator(Iterator aIter)
> > > +    : mCurrent(aIter) { }
> > > +
> > > +  template<typename Iterator>
> > > +  ReverseIterator(const ReverseIterator<Iterator>& aOther)
> > 
> > You're going to need a MOZ_IMPLICIT on this for it to compile on
> > static-analysis builds.  Same for the previous patches of yours I've
> > reviewed today, if I forgot to say it.  Or can they just be explicit?
> 
> Do we generally mark copy constructor |explicit|? I guess adding
> MOZ_IMPLICIT here is enough. STL containers don't add |explicit| to their
> copy constructors, either.

Depends on the class.  |explicit| would be better than MOZ_IMPLICIT.

STL constructors don't add it because they don't compile with static analyses that require it.  Also, they have to follow what the standard specifies.

Comment 18

[Jeff Walden [:Waldo]]

Comment on attachment 8558138 [details] [diff] [review]
patch 4 - Add helper class & functions for reversing

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

::: mfbt/IteratorRange.h
@@ +13,5 @@
> +
> +namespace mozilla {
> +
> +template<typename IteratorT>
> +class IteratorRange

This can be detail, right?

Is there a reason this can't just live in the other header?  Generally helper things don't live in their own headers unless there's a good reason for it.  And given this is only used in one file right now, I must be missing it.

@@ +34,5 @@
> +  iterator end() const { return mIterEnd; }
> +  reverse_iterator rbegin() const { return reverse_iterator(mIterEnd); }
> +  reverse_iterator rend() const { return reverse_iterator(mIterBegin); }
> +
> +protected:

private again, because not meant for exposure via inheritance.

::: mfbt/IteratorRangeUtils.h
@@ +3,5 @@
> +/* This Source Code Form is subject to the terms of the Mozilla Public
> + * License, v. 2.0. If a copy of the MPL was not distributed with this
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> +
> +/* Utils for iterator range */

/* Utility methods to produce a reversed range. */

Is there a reason this file shouldn't be named ReverseIterator.h?  Because it's just exposing reversing of an iterator.

@@ +13,5 @@
> +
> +namespace mozilla {
> +
> +template<typename Range>
> +IteratorRange<typename Range::reverse_iterator>

I really thought this needed a typename, but I guess my understanding of what is/isn't a dependent type is a bit off.

@@ +14,5 @@
> +namespace mozilla {
> +
> +template<typename Range>
> +IteratorRange<typename Range::reverse_iterator>
> +Reverse(Range& aRange)

What would you think about using the name Reversed for these, instead?  Reverse suggests the argument is mutated, but that's not actually the case.  Reversed suggests the correct sense of a new copy being made.

Comment 19

[Xidorn Quan [:xidorn] UTC+11]

(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #18)
> Comment on attachment 8558138 [details] [diff] [review]
> patch 4 - Add helper class & functions for reversing
> 
> Review of attachment 8558138 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: mfbt/IteratorRange.h
> @@ +13,5 @@
> > +
> > +namespace mozilla {
> > +
> > +template<typename IteratorT>
> > +class IteratorRange
> 
> This can be detail, right?
> 
> Is there a reason this can't just live in the other header?  Generally
> helper things don't live in their own headers unless there's a good reason
> for it.  And given this is only used in one file right now, I must be
> missing it.

I thought it could be a general purpose template class. But given that we don't have any other usage yet, I guess it is probably better to put it in detail.

> ::: mfbt/IteratorRangeUtils.h
> @@ +3,5 @@
> > +/* This Source Code Form is subject to the terms of the Mozilla Public
> > + * License, v. 2.0. If a copy of the MPL was not distributed with this
> > + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> > +
> > +/* Utils for iterator range */
> 
> /* Utility methods to produce a reversed range. */
> 
> Is there a reason this file shouldn't be named ReverseIterator.h?  Because
> it's just exposing reversing of an iterator.

So merge the two extra files to ReverseIterator.h? I'm fine with this if you think it's better.

> @@ +14,5 @@
> > +namespace mozilla {
> > +
> > +template<typename Range>
> > +IteratorRange<typename Range::reverse_iterator>
> > +Reverse(Range& aRange)
> 
> What would you think about using the name Reversed for these, instead? 
> Reverse suggests the argument is mutated, but that's not actually the case. 
> Reversed suggests the correct sense of a new copy being made.

I think it's reasonable. I'll rename it.

I guess what I thought was that the name of function should be a verb, but it seems that it is not a requirement.

Comment 20

[Xidorn Quan [:xidorn] UTC+11]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=c987e8202892

Comment 21

[Xidorn Quan [:xidorn] UTC+11]

https://hg.mozilla.org/integration/mozilla-inbound/rev/56219858c1e1
https://hg.mozilla.org/integration/mozilla-inbound/rev/8b2716be2d71
https://hg.mozilla.org/integration/mozilla-inbound/rev/e57cd9c7c07c

Comment 22

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/56219858c1e1
https://hg.mozilla.org/mozilla-central/rev/8b2716be2d71

Comment 23

[Xidorn Quan [:xidorn] UTC+11]

https://hg.mozilla.org/mozilla-central/rev/e57cd9c7c07c

This commit belongs to here as well. I don't understand why I changed the bug number in the commit message...