Add helper template classes for iterating index with range-based loop

RESOLVED FIXED in Firefox 38

Status

()

Core
MFBT
RESOLVED FIXED
3 years ago
3 years ago

People

(Reporter: xidorn, Assigned: xidorn)

Tracking

Trunk
mozilla38
Points:
---

Firefox Tracking Flags

(firefox38 fixed)

Details

Attachments

(2 attachments, 2 obsolete attachments)

(Assignee)

Description

3 years ago
As we have supported range-based for loop in our code base, it would be good to have classes which iterate index with this kind of loop. There are two motivations for having them:

1. Reverse iterating. Because length is usually unsigned, it is hard to write reverse iterating in an elegant way with tranditional for loop. However, we could encapsulate this logic into a class and make the caller code elegant.

2. Integer type dedution. With tranditional for loop, we always have to specify the type of loop variable, because we usually initialize it with an integer literal, which does not dedution to the type we actually want. With range-based for loop, we can benefit from type dedution.

For these cases, I purpose the name Range and ReverseRange. But it seems mozilla::Range is currently used as a pointer range. I guess we probably could rename it to something like PointerRange.

Comment 1

3 years ago
Maybe IterateForward/IterateBackward?  PointerRange isn't suggestive, to me, of a thing to iterate over.
(Assignee)

Comment 2

3 years ago
(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #1)
> Maybe IterateForward/IterateBackward?  PointerRange isn't suggestive, to me,
> of a thing to iterate over.

I meant, renaming the current Range to PointerRange, and then use Range as the name of the purposed template class here.
(Assignee)

Comment 3

3 years ago
I think Range is a good name for this purpose, because this kind of loop is called "range-based loop", and we know the for loop in Python usually uses the "range()" function.

Though, we will still need a MakeRange and MakeReverseRange helper function so that we don't need to specify the template parameter of the classes.
(Assignee)

Comment 4

3 years ago
Created attachment 8557750 [details] [diff] [review]
patch
Assignee: nobody → quanxunzhen
Attachment #8557750 - Flags: review?(jwalden+bmo)
(Assignee)

Comment 5

3 years ago
Created attachment 8557751 [details] [diff] [review]
usage example
(Assignee)

Comment 6

3 years ago
Created attachment 8558139 [details] [diff] [review]
patch
Attachment #8557750 - Attachment is obsolete: true
Attachment #8557750 - Flags: review?(jwalden+bmo)
Attachment #8558139 - Flags: review?(jwalden+bmo)
(Assignee)

Comment 7

3 years ago
Comment on attachment 8558139 [details] [diff] [review]
patch

Cause busted in try build.
Attachment #8558139 - Flags: review?(jwalden+bmo)
(Assignee)

Comment 8

3 years ago
Created attachment 8558332 [details] [diff] [review]
patch

Add workaround for GCC < 4.8
Attachment #8558139 - Attachment is obsolete: true
Attachment #8558332 - Flags: review?(jwalden+bmo)
Comment on attachment 8558332 [details] [diff] [review]
patch

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

::: mfbt/IntegerRange.h
@@ +146,5 @@
> +
> +  iterator begin() const { return iterator(mBegin); }
> +  iterator end() const { return iterator(mEnd); }
> +  reverse_iterator rbegin() const { return reverse_iterator(mEnd); }
> +  reverse_iterator rend() const { return reverse_iterator(mBegin); }

The naming is horrendous, but you can add const versions of these named like crbegin and crend, and cbegin/cend.

@@ +148,5 @@
> +  iterator end() const { return iterator(mEnd); }
> +  reverse_iterator rbegin() const { return reverse_iterator(mEnd); }
> +  reverse_iterator rend() const { return reverse_iterator(mBegin); }
> +
> +protected:

private, please.  I don't think we want people subclassing these and using the internal fields directly.

@@ +154,5 @@
> +  IntTypeT mEnd;
> +};
> +
> +template<typename IntType>
> +IntegerRange<IntType> MakeRange(IntType aEnd)

template<typename IntType>
IntegerRange<IntType>
MakeRange(IntType aEnd)
{
...
}

Also, I am fairly sure that you need a |typename| in front of that return type.

@@ +161,5 @@
> +  // which applies unsigned comparison warning on template parameters.
> +  // See https://gcc.gnu.org/bugzilla/show_bug.cgi?id=11856
> +  MOZ_ASSERT(IsUnsigned<IntType>::value ||
> +             static_cast<typename MakeSigned<IntType>::Type>(aEnd) >= 0,
> +             "Should never have negative value here");

I'd prefer:

namespace detail {

template<typename T, bool = IsUnsigned<T>::value>
struct GeqZero
{
  static bool check(T t) {
    return t >= 0;
  }
};

template<typename T>
struct GeqZero<T, true>
{
  static bool check(T) {
    return true;
  }
};

MOZ_ASSERT(GeqZero<IntType>::check(aEnd));

and so on.  The gcc warning is not quite really a bug, because if the template is only used on unsigned types, it really is a vacuous comparison.

@@ +166,5 @@
> +  return IntegerRange<IntType>(aEnd);
> +}
> +
> +template<typename IntType1, typename IntType2>
> +IntegerRange<IntType2> MakeRange(IntType1 aBegin, IntType2 aEnd)

Same formatting/typename thing.
Attachment #8558332 - Flags: review?(jwalden+bmo) → review+
Comment on attachment 8558332 [details] [diff] [review]
patch

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

::: mfbt/IntegerRange.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/. */
> +
> +/* Classes for iterating integers */

Better phrasing, actually:

/* Iterators over ranges of integers. */

@@ +15,5 @@
> +
> +namespace mozilla {
> +
> +template<typename IntTypeT>
> +class IntegerIterator

So it belatedly occurs to me, we have no good reason to expose IntegerIterator directly, as a class people should use.  Right?  So could you enclose both it and IntegerRange in namespace detail {}?  The only things this should expose are mozilla::MakeRange that produces instances of these classes.  Or am I missing something about the API?  Certainly your demo uses only use MakeRange.
(Assignee)

Comment 12

3 years ago
(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #10)
> Comment on attachment 8558332 [details] [diff] [review]
> patch
> 
> Review of attachment 8558332 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: mfbt/IntegerRange.h
> @@ +146,5 @@
> > +
> > +  iterator begin() const { return iterator(mBegin); }
> > +  iterator end() const { return iterator(mEnd); }
> > +  reverse_iterator rbegin() const { return reverse_iterator(mEnd); }
> > +  reverse_iterator rend() const { return reverse_iterator(mBegin); }
> 
> The naming is horrendous, but you can add const versions of these named like
> crbegin and crend, and cbegin/cend.

I didn't know the reason STL added those methods, so I didn't add them. But it seems they are mostly for the type deduction, which sounds like a reasonable usage. I guess we probably should also add those methods in nsTArray (which should have happended in bug 1126552) and IteratorRange in bug 1127044.

May I open another bug for those methods, and leave this bug as-is?

> @@ +154,5 @@
> > +  IntTypeT mEnd;
> > +};
> > +
> > +template<typename IntType>
> > +IntegerRange<IntType> MakeRange(IntType aEnd)
> 
> template<typename IntType>
> IntegerRange<IntType>
> MakeRange(IntType aEnd)
> {
> ...
> }
> 
> Also, I am fairly sure that you need a |typename| in front of that return
> type.

Why do we need a |typename| there? The current code has passed all compilers we use. See comment 9.

> @@ +161,5 @@
> > +  // which applies unsigned comparison warning on template parameters.
> > +  // See https://gcc.gnu.org/bugzilla/show_bug.cgi?id=11856
> > +  MOZ_ASSERT(IsUnsigned<IntType>::value ||
> > +             static_cast<typename MakeSigned<IntType>::Type>(aEnd) >= 0,
> > +             "Should never have negative value here");
> 
> I'd prefer:
> 
> namespace detail {
> 
> template<typename T, bool = IsUnsigned<T>::value>
> struct GeqZero
> {
>   static bool check(T t) {
>     return t >= 0;
>   }
> };
> 
> template<typename T>
> struct GeqZero<T, true>
> {
>   static bool check(T) {
>     return true;
>   }
> };
> 
> MOZ_ASSERT(GeqZero<IntType>::check(aEnd));
> 
> and so on.  The gcc warning is not quite really a bug, because if the
> template is only used on unsigned types, it really is a vacuous comparison.

This template probably should be in some other file I suppose? I guess it would be useful for other templates as well.
(Assignee)

Comment 13

3 years ago
(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #11)
> Comment on attachment 8558332 [details] [diff] [review]
> patch
> 
> Review of attachment 8558332 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: mfbt/IntegerRange.h
> @@ +15,5 @@
> > +
> > +namespace mozilla {
> > +
> > +template<typename IntTypeT>
> > +class IntegerIterator
> 
> So it belatedly occurs to me, we have no good reason to expose
> IntegerIterator directly, as a class people should use.  Right?  So could
> you enclose both it and IntegerRange in namespace detail {}?  The only
> things this should expose are mozilla::MakeRange that produces instances of
> these classes.  Or am I missing something about the API?  Certainly your
> demo uses only use MakeRange.

You understand this API correctly. We don't need to expose those classes. I'll enclose them.
https://hg.mozilla.org/mozilla-central/rev/47aa743dcd1b
Status: NEW → RESOLVED
Last Resolved: 3 years ago
status-firefox38: --- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla38
(Assignee)

Updated

3 years ago
Blocks: 1175485
You need to log in before you can comment on or make changes to this bug.