Move EnumSet to std?

[brson]

It's wanted for #6085, and generally OR-ing flags together is a common pattern for which we don't otherwise have a typesafe solution. Does EnumSet meet the high bar for inclusion in std? If so, then it's API probably needs careful consideration.

[sfackler]

It should be updated to implement std::container::MutableSet at the very least.

[martindemello]

I'm interested in taking this one on (assuming @nikomatsakis would not rather do it himself, of course)

[nikomatsakis]

@martindemello be my guest. :) The main reason I did not move it to std in the first place was that I didn't want to invest a lot of energy in making it have a nice interface -- but also because we didn't have the deriving modes that would make it usable with unsafe::transmute. I think that last part is no longer true, not sure if it's been properly integrated with those modes and so forth yet (not even sure what those traits are called). I think it's useful enough to warrant inclusion though if done right.

[martindemello]

okay, great :) i'll start figuring out a nice interface for it.

[sfackler]

The relevant traits are ToPrimitive and FromPrimitive.

[martindemello]

@sfackler Why ToPrimitive and FromPrimitive? They seem overly general to me; I think it would make more sense to implement CLike, provide a transparent to_uint that simply returns the underlying uint, and a somewhat more problematic from_uint that could either silently zero out any bit that does not correspond to an enum value, or raise a runtime error if one exist. In the unlikely case that someone wants the value as something other than a uint, they can call to_uint and then cast it themselves.

[sfackler]

They are more general than needed, but they can be automatically derived and CLike (I think?) can't.

[martindemello]

oh, i see. yeah, that's a good point. it looks like FromPrimitive is derivable but ToPrimitive is not, though, and furthermore that FromPrimitive cannot be derived for structs (though that might be worth changing in the special case of a struct holding a single primitive field).

i am unconvinced that there is a sufficient use case for this anyway, versus just calling to_uint when you hit the boundary with C code - at least, the way i am envisioning this being used is to maintain a set of flags in a typesafe way in rust code, and "emit" a uint when needed to pass to a C function. i guess the C function could theoretically want a mutable flagset that the caller is expected to preserve changes to, but i would still do that via an explicit to_uint and from_uint personally. is there some good case for this i'm missing?

[nikomatsakis]

I personally have come to the conclusion that FromPrimitive and ToPrimitive are the wrong basis for EnumSet. The right basis is a trait that guarantees it converts from each enum variant into an integer between 0 and n-1 and which can tell you what n is. One way of doing that -- and the way the deriving mode should use -- is to return the index of the variant in the list, which is often but not always the same as the discriminant. If you need a more stable version that doesn't change as the enum variants are reshuffled than you can implement the trait yourself, though I personally think that in that event you are doing it wrong (that basically implies you are serializing a bit set as an integer, which I think you should not do if you want the data to be forwards compatible).

Here is a (slightly modified) excerpt from an e-mail that I wrote to @martindemello:

I think we really need to decide what we are optimizing for. My
original intention with EnumSet was to handle the following use case:

#[deriving(CLike)]
enum MyFlag { Flag1, Flag2, Flag3 }

type MyFlags = EnumSet<MyFlag>;    

That is, a user who wants to declare an enum indicating a set of
flags, and then work with a set of those flags. I wasn't really
thinking about C compatibility and I'm not overly concerned with binary
compatibility of EnumSets or anything else. I'm not even sure if the
API should expose a way to get the underlying bits, since by keeping
them private you make the matter of whether we use the index or some
other discriminant inobservable.

However, I do think that trying to make it nicer to work with C
code that uses flags is a legitimate use case, naturally. It might
be that we need a different type for it (CEnumSet or something).
Note though that there are multiple ways of encoding bits into
discriminants. One way is to write C code like the following:

enum Flags {
    Flag1 = 1 << 0,
    Flag2 = 1 << 1,
    Flag3 = 1 << 2,
};
bool hasFlag(unsigned u, Flags f) {
     return !!(u & f);
}

Though it is not unheard of to do something like this as well:

enum Flags { Flag1, Flag2, Flag3 };
#define TO_BIT(F) (1 << (F))
bool hasFlag(unsigned u, Flags f) {
     return !!(u & TO_BIT(f));
}

The latter is convenient because you do not need to label
every individual enum with a bit, and it makes it easier
to shuffle the order around and so forth. Note that the
same EnumSet class cannot work with both approaches, because
in one case it must shift the discriminants and in one case
it doesn't have to.

• Using indices:
  • Guarantees tightly packed indices from 0..n-1
    with no duplicates.
  • Makes it easy to know the maximum number of bits,
    permitting EnumSet::<T>::all().
  • Works invisibly with ANY enum, regardless of discriminants
    or other flags.
• Using the discriminant:
  • Potentially gives compatibility with C (modulo the usual
    concerns about the unpredictability of the representation
    of enums in the C ABI)
  • Allows users to convert an EnumSet into a uint and back again
    in a backwards compatible way:
    • i.e., if they change the order of things in the enum, they
      can theoretically update the discriminants to maintain
      the same bits

Note though that using explicit discriminants in place of indices
carries some real disadvantages, particularly if those indices
are bits:

• Users must label every variant, and if they forget to do
  so the EnumSet breaks in horrible ways
• Matching against such an enum is inefficient
• You cannot use the discriminant to index into a table

In my opinion the tradeoff is clear. Using indices makes EnumSet
convenient for Rust code and much more bullet proof. C users can just
a uint, or we could possibly make a second type specialized to that
use case. This does imply though a new trait and deriving mode for it.

[martindemello]

Agreed. I think the correct progression, then, is

1. Define a derivable trait, Ordinal
2. Have EnumSet take an Ordinal rather than a CLike
3. Have a separate CLike trait, not necessarily derivable, and possibly a separate CFlagSet analogue of EnumSet meant to convert to/from C uints stored as ored collections of flags.

[nikomatsakis]

That sounds correct.

[SimonSapin]

If EnumSet is being redesigned, #13756 is kinda related. My use case in Servo is unrelated to C. I just want a bunch of named bits, and I don’t care about the underlying enum (it only exists for EnumSet.)

[aturon]

To make some progress on this issue (and the related #6085 which is blocked on it), I'm thinking of doing the following:

• Introduce CFlagSet with CLike trait that uses the discriminants directly (rather than indices), and allows conversion to uint (unlike EnumSet); use the current EnumSet implementation as a basis
• Rename CLike to Ordinal in EnumSet
• Reimplement EnumSet as a wrapper around CFlagSet by transforming indices from Ordinal to discriminants for CLike (just as the bit function in EnumSet currently does)
• Add MutableSet implementations for both
• Put this all in libstd

This would unblock #6085 by giving us C-compatible flag sets, without duplicating the EnumSet implementation -- but would also give us the freedom to change the representation/implementation of EnumSet later on if desired.

[aturon]

Update on this issue: the bitflags! macro has been merged, as part of libstd, so that is now the preferred way to construct C-compatible, type-safe APIs.

As per @nikomatsakis above, there is still a potential role for EnumSet. We are evaluating a few possibilities, in part by moving existing uses of C-style enums to use bitflags! (and thereby perhaps enabling a language simplification).

[Gankra]

Any developments on this? What is the fate of EnumSet?

[Gankra]

EnumSet is no longer part of the public API. It is currently hosted in libcollections but not re-exported, so that the compiler can use it. It may reasonably be removed if the compiler stops using it.