1142999 - Add an EnumeratedRange class to iterate EnumeratedArrays

Status: RESOLVED FIXED

(Core :: MFBT, defect)

Description

[Emanuel Hoogeveen [:ehoogeveen]]

In bug 1139552 I switched the AllocKind-related arrays in ArenaList over to mozilla::EnumeratedArray, to work more smoothly with AllocKind as an enum class and get some additional type safety (not to mention mozilla::Array's runtime checks). However, since these arrays can only be indexed with members of AllocKind, I had to add some macros to clean up iteration:

#define ALL_ALLOC_KINDS(i) AllocKind i = AllocKind::FIRST;\
    i < AllocKind::LIMIT; i = AllocKind(uint8_t(i) + 1)

for (ALL_ALLOC_KINDS(kind))
    backgroundFinalizeState[kind] = BFS_DONE;

It would be nice to be able to do this with range-based for loops instead:

for (auto &&kind : AllAllocKinds())
    backgroundFinalizeState[kind] = BFS_DONE;

However, mozilla::IntegerRange cannot handle enum classes - it would have to work with the underlying type instead, and wouldn't produce AllocKind values (unless I'm missing something!). So in this bug I propose adding EnumeratedRange, which does produce values of the right type.

Comment 1

[Emanuel Hoogeveen [:ehoogeveen]]

Attachment: Add an EnumeratedRange class to iterate EnumeratedArrays.

This is very nearly a copy of mozilla::IntegerRange, but I couldn't come up with a way to share more code (I guess they could use a common base class, perhaps, but I didn't really want to complicate things further). Since MSVC doesn't have std::underlying_type as far as I know, I added it as a template parameter to MakeEnumeratedRange. With this class, AllAllocKinds() would look something like this:

inline decltype(mozilla::MakeEnumeratedRange<uint8_t>(AllocKind::FIRST, AllocKind::LIMIT))
AllAllocKinds()
{
    return mozilla::MakeEnumeratedRange<uint8_t>(AllocKind::FIRST, AllocKind::LIMIT);
}

Comment 2

[Emanuel Hoogeveen [:ehoogeveen]]

(I guess I just kind of jumped in on this, but there's no rush)

Comment 3

[Nathan Froyd [:froydnj]]

Comment on attachment 8577253 [details] [diff] [review]
Add an EnumeratedRange class to iterate EnumeratedArrays.

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

r=me, with some documentation added.  I realize IntegerRange doesn't really have any documentation, but enums are sufficiently different that I think a little extra documentation would be good.

::: mfbt/EnumeratedRange.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/. */
> +
> +/* Iterator over a packed enum class */

I assume "packed" here is meant to imply "contiguous enum values".  Can you unpack that definition in a larger comment below, and what can go wrong if you use it on a non-packed enum class?  It looks like single-argument MakeEnumeratedRange also assumes that the enum values start at 0; probably good to make that clear.

Also, there's not really anything here that limits you to enum classes, is there?  Please fix this brief blurb if that's the case, and make it clear in your expanded comment that this works for plain enums and enum classes.

@@ +33,5 @@
> +  // Since operator* is required to return a reference, we return
> +  // the reference of our member here.
> +  const EnumTypeT& operator*() const { return mCurrent; }
> +
> +  /* Increments and descrements operators */

Nit: "decrements", though I think "increments" and "decrements" should really be rendered in the singular form.

Comment 4

[Nathan Froyd [:froydnj]]

Comment on attachment 8577253 [details] [diff] [review]
Add an EnumeratedRange class to iterate EnumeratedArrays.

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

Apologies for the second review, I should have said something about these things in the initial review.  I *think* these are all the extra checks we need.

::: mfbt/EnumeratedRange.h
@@ +182,5 @@
> +detail::EnumeratedRange<IntType, EnumType>
> +MakeEnumeratedRange(EnumType aEnd)
> +{
> +  MOZ_ASSERT(detail::GeqZero<IntType>::check(IntType(aEnd)),
> +             "Should never have negative value here");

We should also verify that aEnd actually fits into the range of IntType.  static_assert(sizeof(IntType) >= sizeof(EnumType)) is almost sufficient, except for signedness issues.

@@ +190,5 @@
> +template<typename IntType, typename EnumType>
> +detail::EnumeratedRange<IntType, EnumType>
> +MakeEnumeratedRange(EnumType aBegin, EnumType aEnd)
> +{
> +  MOZ_ASSERT(aEnd >= aBegin, "End value should be larger than begin value");

Likewise here, for both aBegin and aEnd.

Comment 5

[Emanuel Hoogeveen [:ehoogeveen]]

Attachment: v2 - Add an EnumeratedRange class to iterate EnumeratedArrays.

I added the checks you requested, but I wonder if I went a bit overboard with them. Could you have another quick look?

(In reply to Nathan Froyd [:froydnj] [:nfroyd] from comment #3)
> > +/* Iterator over a packed enum class */
> 
> I assume "packed" here is meant to imply "contiguous enum values".  Can you
> unpack that definition in a larger comment below, and what can go wrong if
> you use it on a non-packed enum class?  It looks like single-argument
> MakeEnumeratedRange also assumes that the enum values start at 0; probably
> good to make that clear.
> 
> Also, there's not really anything here that limits you to enum classes, is
> there?  Please fix this brief blurb if that's the case, and make it clear in
> your expanded comment that this works for plain enums and enum classes.

I expanded the comment and added descriptions above the range generator functions.

> > +  /* Increments and descrements operators */
> 
> Nit: "decrements", though I think "increments" and "decrements" should
> really be rendered in the singular form.

I copy-pasted this from IntegerRange, so I took the liberty of correcting the same error there.

(In reply to Nathan Froyd [:froydnj] [:nfroyd] from comment #4)
> We should also verify that aEnd actually fits into the range of IntType. 
> static_assert(sizeof(IntType) >= sizeof(EnumType)) is almost sufficient,
> except for signedness issues.

I added checks to this effect, though perhaps 4 runtime assertions is a bit overkill. One thing we unfortunately *can't* check, as far as I can tell, is whether EnumType(0) is a valid cast. Even though the enum values should be known at compile time, neither gcc nor clang gives so much as a warning when you do this (even with -Wall -Wextra -pedantic).

I considered writing a checked cast for a while using macros and templates that could wrap an enum definition, but I couldn't think of a way to handle things like |enum { FIRST, SECOND = FIRST + 1, FIRST_AGAIN = FIRST };| without requiring the user to list the unique values a second time.

Comment 6

[Emanuel Hoogeveen [:ehoogeveen]]

Try run with a tweaked version of the patch from bug 1143042 on top (since otherwise this has no uses):
https://treeherder.mozilla.org/#/jobs?repo=try&revision=bf5c056c3cc3

Comment 7

[Emanuel Hoogeveen [:ehoogeveen]]

(In reply to Emanuel Hoogeveen [:ehoogeveen] from comment #5)
> Even though the enum values should be
> known at compile time, neither gcc nor clang gives so much as a warning when
> you do this (even with -Wall -Wextra -pedantic).

I should clarify, I mean this doesn't generate a warning for scoped/unscoped enums that *do not* start at 0:

enum class EnumTest {
  ONE = 1
};

int main()
{
  EnumTest test = EnumTest(0);
  return int(test);
}

This compiles without any complaint. I know it's an explicit cast, but I'd hoped it would be undefined for integer constant expressions that don't map to an enum value, or at least generate a warning.

Comment 8

[Nathan Froyd [:froydnj]]

Comment on attachment 8581169 [details] [diff] [review]
v2 - Add an EnumeratedRange class to iterate EnumeratedArrays.

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

Thanks for the expanded assertions!  Just a few comments on this version.

::: mfbt/EnumeratedRange.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/. */
> +
> +/* 

Nit: trailing whitespace.

Also, for the purposes of mxr (dxr?) directory listings, it's nice to have a single-line summary comment.  So can you put back your previous summary comment with a tweak, something like:

/* Iterator over contiguous enum values */

and then follow with the explanation you have now?

@@ +186,5 @@
> +
> +#ifdef __GNUC__
> +// Enums can have an unsigned underlying type, which makes some of the
> +// comparisons below always true or always false. Temporarily disable
> +// -Wtype-limits to avoid breaking -Werror builds.

Two questions for this:

1) Compilers are supposed to ignore pragmas they don't understand, but IIRC, we also have clang and GCC configured to warn on unknown pragmas.  Does clang quietly ignore these, loudly ignore these, or follow them?  (Since clang also defines __GNUC__.)
2) Does the warning suppression actually apply to the instantiation of the templates, not just the definition?  That's pretty slick if so.

@@ +219,5 @@
> +  MOZ_ASSERT(aBegin < aEnd, "Cannot generate invalid, unbounded range!");
> +
> +  MOZ_ASSERT_IF(aBegin < EnumType(0), IsSigned<IntType>::value);
> +  MOZ_ASSERT_IF(EnumType(0) < aEnd,
> +                UnsignedType(aEnd) <= UnsignedType(MaxValue<IntType>::value));

This is to guard against cases like:

enum Example {
  ...
  VALUE = 0xffffffff;
}

MakeEnumeratedRange<int32_t>(..., VALUE);

yes?

@@ +221,5 @@
> +  MOZ_ASSERT_IF(aBegin < EnumType(0), IsSigned<IntType>::value);
> +  MOZ_ASSERT_IF(EnumType(0) < aEnd,
> +                UnsignedType(aEnd) <= UnsignedType(MaxValue<IntType>::value));
> +  MOZ_ASSERT_IF(aBegin < EnumType(0),
> +                SignedType(MinValue<IntType>::value) >= SignedType(aBegin));

Shouldn't this be <=?  Consider something like:

enum Example {
  START = -2;
  ...
};

MakeEnumeratedRange<int32_t>(START, ...);

The assert as written would say:

  if (-2 < 0) {
    MOZ_ASSERT(INT32_MIN >= -2);

which is always going to assert.

Comment 9

[Emanuel Hoogeveen [:ehoogeveen]]

Attachment: v3 - Add an EnumeratedRange class to iterate EnumeratedArrays.

Carrying forward r=nfroyd. Thanks for the quick reviews!

I decided to make the one-parameter version of MakeEnumeratedRange() call the two-parameter version, since the assertions check the same things.

(In reply to Nathan Froyd [:froydnj] [:nfroyd] from comment #8)
> Nit: trailing whitespace.
> 
> Also, for the purposes of mxr (dxr?) directory listings, it's nice to have a
> single-line summary comment.  So can you put back your previous summary
> comment with a tweak, something like:
> 
> /* Iterator over contiguous enum values */
> 
> and then follow with the explanation you have now?

Done, and stripped trailing whitespace.

> 1) Compilers are supposed to ignore pragmas they don't understand, but IIRC,
> we also have clang and GCC configured to warn on unknown pragmas.  Does
> clang quietly ignore these, loudly ignore these, or follow them?  (Since
> clang also defines __GNUC__.)

Clang supports both -Wtype-limits and the GCC diagnostics pragma (I checked). Not surprising since it's supposed to work as a drop-in replacement.

> 2) Does the warning suppression actually apply to the instantiation of the
> templates, not just the definition?  That's pretty slick if so.

Yep! Try was burning without it (though now that bug 1143966 has landed, my particular use won't require it). I'll send a version to try with that reverted to ensure my changes didn't break this.

> > +  MOZ_ASSERT_IF(EnumType(0) < aEnd,
> > +                UnsignedType(aEnd) <= UnsignedType(MaxValue<IntType>::value));
> 
> This is to guard against cases like:
> 
> enum Example {
>   ...
>   VALUE = 0xffffffff;
> }
> 
> MakeEnumeratedRange<int32_t>(..., VALUE);
> 
> yes?

Right. If both limits are non-negative, we have no way of knowing whether the underlying type of the enum is signed or unsigned, so if IntType is signed we have to check that the maximum value of IntType is less than aEnd if both are interpreted as unsigned numbers.

Thankfully, we can use EnumType(0) < aEnd to sidestep signedness issues *before* we actually know that aEnd is non-negative. Still, the assert as written was a bit confusing. I changed it to the following, which should be somewhat more optimal and clarify the intent:

MOZ_ASSERT_IF(aBegin >= EnumType(0) && IsSigned<IntType>::value, UnsignedType(aEnd) <= UnsignedType(MaxValue<IntType>::value));

> > +  MOZ_ASSERT_IF(aBegin < EnumType(0),
> > +                SignedType(MinValue<IntType>::value) >= SignedType(aBegin));
> 
> Shouldn't this be <=?

Ah, good point. But in fact, the static_assert and the IntType signedness assert should be enough to ensure that this assert (when corrected) always passes anyway, so I just removed it instead. This also let me get rid of the SignedType typedef.

Comment 10

[Emanuel Hoogeveen [:ehoogeveen]]

(In reply to Emanuel Hoogeveen [:ehoogeveen] from comment #9)
> we have to check that the maximum value of IntType is less than aEnd
> if both are interpreted as unsigned numbers.

More than, even. The actual assert does it the other way around :)

Comment 11

[Emanuel Hoogeveen [:ehoogeveen]]

Looks good on try:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=3897dadba6a4

Also with bug 1143966 reverted:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=070737de94bf

And testing the single-argument version (which otherwise has no uses):
https://treeherder.mozilla.org/#/jobs?repo=try&revision=8ee6ccb4d539

Comment 12

[Emanuel Hoogeveen [:ehoogeveen]]

Hang on, I just realized that aBegin == aEnd still gives a valid, albeit empty range. IntegerRange does the right thing here.

Comment 13

[Emanuel Hoogeveen [:ehoogeveen]]

Attachment: v3.1 - Add an EnumeratedRange class to iterate EnumeratedArrays.

Carrying forward r=nfroyd. This just loosens an assertion slightly, so I don't think it needs another try run.

With this change, the behavior will more closely match regular for loops, where you might end up with valid situations where i == n, causing the for loop to never execute. It will still assert on the conceptual equivalent of i > n, since that would never reach the end value.

Comment 14

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/f6850a11e315

Comment 15

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

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

Comment 16

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8582011 [details] [diff] [review]
v3.1 - Add an EnumeratedRange class to iterate EnumeratedArrays.

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

::: mfbt/EnumeratedRange.h
@@ +198,5 @@
> +template<typename IntType, typename EnumType>
> +inline detail::EnumeratedRange<IntType, EnumType>
> +MakeEnumeratedRange(EnumType aBegin, EnumType aEnd)
> +{
> +  typedef typename MakeUnsigned<IntType>::Type UnsignedType;

In optimized builds, GCC 4.8 complains with the following error message:

error: typedef 'UnsignedType' locally defined but not used [-Werror=unused-local-typedefs]
   typedef typename MakeUnsigned<IntType>::Type UnsignedType;

I suggest adding a #ifdef DEBUG around this typedef.

Comment 17

[Nicolas B. Pierron [:nbp]]

Attachment: Remove gcc warning about unused typedef.

Comment 18

[Emanuel Hoogeveen [:ehoogeveen]]

Comment on attachment 8583167 [details] [diff] [review]
Remove gcc warning about unused typedef.

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

Ah, I didn't consider that. Looks fine.

Comment 19

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/7e3c6bc1ade6

Comment 20

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/7e3c6bc1ade6