Closed Bug 1127044 Opened 5 years ago Closed 5 years ago

Make nsTArray support reverse iterating with STL sematics

Categories

(Core :: MFBT, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla38
Tracking Status
firefox38 --- fixed

People

(Reporter: xidorn, Assigned: xidorn)

References

Details

Attachments

(5 files, 4 obsolete files)

Add mozilla::Reversed and mozilla::ReverseIterator to MFBT, and add rbegin() and rend() to nsTArray.
Probably we can use std::reverse_iterator directly, can we?
Assignee: nobody → quanxunzhen
Attachment #8557743 - Flags: review?(jwalden+bmo)
Attached patch patch 2 - Add ReverseIterator (obsolete) — Splinter Review
Attachment #8557745 - Flags: review?(jwalden+bmo)
Attachment #8557746 - Flags: review?(nfroyd)
Attachment #8557747 - Flags: review?(jwalden+bmo)
Attached patch usage exampleSplinter Review
Attachment #8557749 - Attachment description: example → usage example
Attached patch patch 2 - Add ReverseIterator (obsolete) — Splinter Review
Submitted the wrong one...
Attachment #8557745 - Attachment is obsolete: true
Attachment #8557745 - Flags: review?(jwalden+bmo)
Attachment #8557801 - Flags: review?(jwalden+bmo)
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.
Attachment #8557746 - Flags: review?(nfroyd)
Attachment #8557801 - Attachment is obsolete: true
Attachment #8557801 - Flags: review?(jwalden+bmo)
Attachment #8558135 - Flags: review?(jwalden+bmo)
Attachment #8557746 - Attachment is obsolete: true
Attachment #8558137 - Flags: review?(nfroyd)
Attachment #8557747 - Attachment is obsolete: true
Attachment #8557747 - Flags: review?(jwalden+bmo)
Attachment #8558138 - Flags: review?(jwalden+bmo)
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!
Attachment #8558137 - Flags: review?(nfroyd) → review+
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.
Attachment #8557743 - Flags: review?(jwalden+bmo) → review+
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==(...,
           ...)
{
  ...
}
Attachment #8558135 - Flags: review?(jwalden+bmo) → review+
(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.
(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 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.
Attachment #8558138 - Flags: review?(jwalden+bmo) → review+
(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.
https://hg.mozilla.org/mozilla-central/rev/56219858c1e1
https://hg.mozilla.org/mozilla-central/rev/8b2716be2d71
Status: NEW → RESOLVED
Closed: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla38
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...
Blocks: 1175485
You need to log in before you can comment on or make changes to this bug.