Wave That Flag

Sunday, October 8, 2006

Have a look at the FlagSet8 struct in Gregor.Core, which is supposed to compact boolean flags into a more memory-efficient structure. It works like a flags enum, but it's got a more convenient interface, one that can safely be exposed to clients, too.

FlagSet8 supports up to eight flags and provides convenience methods for common flag operations:

FlagSet8 flags = new FlagSet8(Flags8.Flag2 | Flags8.Flag4);
Console.WriteLine(flags[Flags8.Flag4 | Flags8.Flag6]);
flags[Flags8.Flag6] = true;
Console.WriteLine(flags[Flags8.Flag4 | Flags8.Flag6]);

Details

The FlagSet8 struct works in conjunction with the Flags8 enum, which defines the eight possible flag values (its underlying type is byte). This way, objects that have a large number of boolean properties can work with less overhead; also consider that derived classes may define additional boolean properties. Using a value type is also more effient than using a BitArray (System.Collections).

I have resisted the temptation of overloading operators, because that always becomes a bottomless pit. Just think about all the consistency requirements - boolean conversion and definite true/false, equality and those various methods defined in System.Object and System.IEquatable, and perhaps I could have gone really crazy so as to define comparison operators that - how intuitive - compare the count of bits set in each operand. And sure enough, logical operators are overloadable as well.

As mentioned, the FlagSet8 struct works with the Flags8 enum. By only accepting that enum, the structure wraps bit flags in a type-safe manner.

Another design choice is that all methods that either take or return instances of type FlagSet8 are static members. These include logical operations (And, Or, Xor, Not), as well as obtaining a default instance (Empty). FlagSet8 instance members work with the Flags8 enum and booleans. This way, it's easier to remember when a method does not actually change the struct - static methods with value parameters cannot alter the arguments passed.

As I see it, mutators should never return anything. Not a value of the object's type - you'll never know whether the instance returned is a copy of the object in the "old" state, a copy of the object in the "new" state, or whether the method even does change the object and changes are applied to the new instance returned only. Likewise, a mutator should not return a value of any parameter's type - again, you'll never know which convention applies - is the "old" value returned, or the new one?

Generics Blues

So why are there no FlagSet16, FlagSet32, and FlagSet64 structs? For one, I think I'll get by with eight possible flags in my classes for now.

But more importantly, I'm hesitant to duplicate the code of FlagSet8, because - can you guess what's bugging me? - it would be so damn easy to define a generic struct that accepts a type parameter that is constrained to an enumerated type decorated with the System.Flags attribute, if it only worked.

// doesn't work
struct FlagSet<FlagType> where FlagType : enum {}

Of couse, I could accept any type parameter constrained to value types and IConvertible, and fall back on conversion, and sometimes reflection, for manipulation the bits. But I'm not trading size for speed in that manner in this case!

Identifying the Bits

Speaking of the type system, I'd like to be able to define alias types for enums, so that client code can use more appropriate enumerator names for flag access:

// doesn't work
[Flags()]
enum DiningOptions : Flags8 {
    AirConditioning = Flags8.Flag1,
    CellPhoneBan    = Flags8.Flag2,
    ToplessWaitress = Flags8.Flag3,
}

Again, if we could reasonably constrain a generic parameter type to an enum, client code could just construct a generic FlagSet type with any suitable flags enum (the enum wouldn't need to be an alias, then):

// air code
class Dinner {

    private FlagSet<DiningOptions> m_Options;

}

New Helpers

There are some new helper routines in the Gregor.Core.Bytes module:

• BitsToString creates a binary-format [sic?] string representation of integers or flags enums, either in big-endian or little-endian order.
• IterateFlags returns a generic IEnumerator (for integer and flags enum types) that walks all bits that are set. Think of it as the equivalent to Bytes.WalkFlags (which uses a callback), supporting the more convenient foreach-style of iteration.

In both cases, the generic version (intended for flags-enums) suffers from the limitations of the type constraints model.

Bytes.IterateFlags is implemented using C# iterator constructs (yield return). Since the generic IEnumerator<T> interface is returned, there has to be a separate implementation for every integer type supported (compatibility among generic parameter types does not imply compatibility of constructed types). Again, if it was possible to constrain generic type parameters to integral numbers, one generic routine would have been enough.

On Iterating a FlagSet

Note that FlagSet8 implements IEnumerable<Flags8> with a C# iterator as well. For performance and type system reasons, the implementation does not delegate to Bytes.IterateFlags. Notice that bit shifting is not supported for enums:

public IEnumerator<Flags8>GetEnumerator(){
    // return Bytes.IterateFlags<Flags8>(m_Value);
    Flags8 flag = Flags8.Flag1;
    Flags8 value = m_Value;
    for(int i = 0; i < sizeof(Flags8) * 8; i++){
        if((value & flag) == flag){
            yield return flag;
        }
        byte tmp = (byte) flag;
        tmp <<= 1;
        flag = (Flags8)tmp;
    }
}

Usage:

FlagSet8 set = new FlagSet8(Flags8.Flag1 | Flags8.Flag3);
foreach(Flags8 flag in set){
    Console.WriteLine(flag);
}
// Flag1
// Flag3