In the September 2003 installment of this column, I began a discussion of generics in the common language runtime (CLR). I introduced the concept of a generic type, covered the flexibility and code reuse that's afforded by generics, discussed performance and type safety, and presented the generics syntax in C# in a simple code sample. This month I'll dig deeper into the internal workings of the CLR with respect to generics. I'll cover type constraints, generic classes, methods, structures, and the upcoming generic class libraries.
How Does the Compiler Handle Generic Types?
Both C++ templates and the proposed generics equivalent in the Java language are features of their respective compilers. These compilers construct code from references to the generic or template type at compile time. This can cause code bloat as well as reduced type equivalence from one construction to another, even when the type arguments are the same. In contrast, CLR generics do not work this way.
Generics in the CLR are a first-class feature of the platform itself. To implement it this way required changes throughout the CLR including new and modified intermediate language instructions, changes to the metadata, type-loader, just-in-time (JIT) compiler, language compilers, and more. There are two significant benefits to the run-time expansion in the CLR.
First, even though each construction of a generic type, such as Node<Form> and Node<String>, has its own distinct type identity, the CLR is able to reuse much of the actual JIT-compiled code between the type instantiations. This drastically reduces code bloat and is possible because the various instantiations of a generic type are expanded at run time. All that exists of a constructed type at compile time is a type reference. When assemblies A and B both reference a generic type defined in a third assembly, their constructed types are expanded at run time. This means that, in addition to sharing CLR type-identities (when appropriate), type instantiations from assemblies A and B also share run-time resources such as native code and expanded metadata.
Type equivalency is the second benefit of run-time expansion of constructed types. Here is an example: referencing code in AssemblyA.dll that constructs Node<Int32> and referencing code in AssemblyB.dll that constructs Node<Int32> will both create objects of the same CLR type at run time. This way, if both assemblies are used by the same application, their constructions of the Node<T> type resolve to the same type and their objects can be exchanged freely. You should note that compile-time expansion would make this logically simple equivalency either problematic or impossible to implement.
There are a few other benefits to implementing generics at the runtime level, rather than at the compiler level. One such benefit is that generic type information is preserved between compilation and execution and is therefore accessible at all points in the code lifecycle. For example, reflection provides full access to generics metadata. Another benefit is rich IntelliSense® support in Visual Studio® .NET as well as a clean debugging experience with generic code. In contrast, Java generics and C++ templates lose their generic identity by run time.
Another benefit, and mainstay of the CLR, is cross-language use—a generic defined using one managed language can be referenced by code written in another managed language. Meanwhile, the likelihood that a language vendor will put generics support in their compilers is increased by the fact that much of the hard work is done in the platform.
Of all the fringe benefits of run-time type expansion, my favorite is a somewhat subtle one. Generic code is limited to operations that are certain to work for any constructed instantiation of the type. The side effect of this restriction is that CLR generics are more understandable and usable than their C++ template counterparts. Let's look at the constraints around generics in the CLR.
Rules and Constraints
One problem that plagues programmers who use C++ templates is the many ways in which a particular attempt at type construction might fail, including the failure of a type argument of a type parameter to implement a method called by the templated code. Meanwhile, the compiler errors in these cases can be confusing and may seem unrelated to the root problem. With run-time expansion of constructed types, similar errors would become JIT-compiler or type-load errors rather than compile-time errors. The CLR architects decided that this would not be an acceptable implementation for generics.
Instead, they decided that a generic type, such as Node<T>, must be verifiable at compile time as a valid type for any possible type instantiation of the generic type, even though type instantiation actually occurs at run time. As such, expansion errors around problematic type constructions become impossible. To achieve this goal, the architects constrained the features of generics with a set of rules and restrictions that make it possible to assure the validity of a generic type before attempting an expansion of one of its instantiations.
There are some rules that constrain the types of code that you can write generically. The essence of these rules can be summed up in a single statement: generic code is only valid if it will work for every possible constructed instance of the generic. Otherwise, the code is invalid and will not compile correctly (or if it does, it won't pass verification at run time).
At first this can seem like a limiting rule. Here is an example:
public class GenericMath {
public T Min<T>(T item1, T item2) {
if (item1 < item2) {
return item1;
}
return item2;
}
}
This code is not valid in CLR generics. The error that you get from the C# compiler reads something like this:
invalid.cs(4,11): error CS0019: Operator '<' cannot be applied to
operands of type 'T' and 'T'
Meanwhile, minor syntax differences aside, this very same code is allowed in C++ templates. Why the limitation with generics? The reason is that the less-than operator in C# only works with certain types. However, the type parameter T in the previous code snippet could expand to any CLR type at run time. Rather than risk having invalid code at run time, the preceding example is found invalid at compile time.
Operators aside, though, the same limitation applies to more manageable uses of types, such as method calls. This modification to the Min<T> method is also invalid generic code:
class GenericMath {
public T Min<T>(T item1, T item2) {
if (item1.CompareTo(item2) < 0) {
return item1;
}
return item2;
}
}
This code is invalid for the same reason as the previous example. The CompareTo method, although implemented by many types in the class library and easily implemented by your custom types, is not guaranteed to exist on every possible type that can be used as an argument to T.
But you've already seen that method calls are not completely disallowed in generic code. In Figure 1 the GetHashCode method is called on the two parameterized arguments, and the Node<T> type in Figure 2 calls the ToString method on its parameterized m_data field. Why are GetHashCode and ToString allowed, when CompareTo is not? The reason is that GetHashCode and ToString are both defined on the System.Object type from which every possible CLR type is derived. This means that every possible expansion of type T has an implementation of the ToString and GetHashCode member functions.
If generics are to be useful for anything beyond collection classes, then generic code needs to be able to call methods other than those defined by System.Object. But remember, generic code is only valid if it will work for every possible constructed instance of the generic. The resolution to these two seemingly incompatible requirements is a feature of CLR generics called constraints.
You should be aware that constraints are an optional component of a generic type or method definition. A generic type may define any number of constraints, and each constraint applies an arbitrary restriction on the types that can be used as an argument to one of the type parameters on the generic code. By restricting the types that can be used in the construction of a generic type, the limitations on the code that references the constrained type parameter are relaxed (see Figure 3).
It is valid for Min<T> and Max<T> to call CompareTo on its items because the constraint is applied to the type parameter T. In the third line of code in Figure 3, you can see the introduction of a where clause that looks like this:
where T : IComparable
This constraint indicates that any construction of the method Min<T> must supply a type argument for parameter T of a type that implements the IComparable interface. This constraint limits the variety of possible instantiations of Min<T> while increasing the flexibility of the code in the method such that it can now call CompareTo on variables of type T.
Constraints make generic algorithms possible by allowing generic code to call arbitrary methods on the expanded types. Although constraints require additional syntax for generic defining code, referencing code syntax is unchanged by constraints. The only difference for referencing code is that the type arguments must respect the constraints on the generic type. For example, the following referencing code to Max<T> is valid:
GenericMath.Min(5, 10);
This is because 5 and 10 are integers and the Int32 type implements the IComparable interface. However, this attempted construction of Max<T> produces a compiler error:
GenericMath.Min(new Object(), new Object());
Here is the error generated by the compiler:
MinMax.cs(32,7): error CS0309: The type 'object' must be convertible
to 'System.IComparable' in order to use it as parameter 'T' in the
generic type or method 'GenericMath.Min<T>(T, T)'
System.Object is an invalid type argument for T because it does not implement the IComparable interface required by the constraint on T. Constraints make it possible for the compiler to provide descriptive errors like the one shown in the preceding example, when the type argument is not compatible with the type parameter on the generic code.
At present, generics support three kinds of constraints: the interface constraint, the base class constraint, and the constructor constraint. An interface constraint specifies an interface with which all type arguments to the parameter must be compatible. Any number of interface constraints can apply to a given type parameter.
The base class constraint is similar to an interface constraint, but each type parameter may only include a single base class constraint. If no constraint is specified for a type parameter, then the implicit base class constraint of Object is applied.
The constructor constraint makes it possible for generic code to create instances of the type specified by a type parameter by constraining type arguments to types that implement a public default constructor. At this time, only default or parameterless constructors are supported with the constructor constraint.
A where clause is used to define a constraint or list of constraints for a given type parameter. Each where clause applies to only a single type parameter. A generic type or method definition may have no where clauses, or it may have as many where clauses as it has type parameters. A given where clause may include a single constraint or list of constraints separated by commas. Figure 4 shows the various syntaxes for applying constraints to generic code.
The fundamental rule of generics—that either all possible instantiations of the generic are valid or the generic type itself is invalid—has a few more interesting side effects. First, there's casting. In generic code a variable of a type-parameter type may only be cast to and from its base class constraint type or bases thereof. This means that if a type parameter T has no constraints, it can only be cast to and from Object references. However, if T is constrained to a more derived type such as FileStream, then the generic definition can include casts to and from T and FileStream, as well as all bases of FileStream, down to Object. The code in Figure 5 shows this cast rule in action.
In this example, T has no constraint and is considered to be unbounded. It has the implicit base class constraint of Object. Casts of T to and from the Object class, as well as casts to and from interface types, are valid at compile time. Casts to other types, such as Int32, for unbounded T are disallowed by the compiler. The casting rule for generics also applies to conversions and therefore disallows the use of casting syntax to make type conversions such as the conversion from an Int32 to an Int64; conversions like this are not supported with generics.
Here's another interesting tidbit. Consider the following code:
void Foo<T>() {
T x = null; // compiler error when T is unbounded
•••
While a null assignment like this one has obvious uses, there is one possible problem. What if T is expanded to a value type? A null assignment to a value variable has no meaning. Fortunately, the C# compiler provides special syntax that provides correct results regardless of the runtime type of T:
void Foo<T>() {
T x = T.default; // OK for any T
}
The expression on the right side of the equals sign is called the default value expression. If T is expanded to a reference type, then T.default resolves to null. If T is expanded to a value type, then T.default is the all-bits-zero value for the variable.
Null assignment to a parameterized variable T is disallowed if T is unbounded, so one might guess that the following would also be invalid, but it is not:
void Foo<T>(T x) {
if (x == null) { // Ok
•••
}
}
If null is allowed here, what happens if T is expanded to a value type? Where T is a value type, the Boolean expression in the preceding example is hardwired to false. Unlike in the null assignment case, null comparison makes sense for any expansion of T.
The premise that generic types are verifiably valid at compile time for any possible instantiation does have an effect on your generic code. However, I have found that the additional structure around generics in the CLR, by comparison to templates in C++, has a clarifying effect. All in all, constraints and their surrounding infrastructure are one of my favorite aspects of CLR generics.
Generic Interfaces and Delegates
Generic classes, structures, and methods are the primary features of CLR generics. Generic interfaces and delegates are really supporting features. A generic interface alone has limited usefulness. But when used with a generic class, struct, or method, generic interfaces (and delegates) have significant impact.
The GenericMath.Min<T> and GenericMath.Max<T> methods in Figure 3 both constrain T to be compatible with the IComparable interface. This allows the methods to call CompareTo on the parameterized arguments to the methods. However, neither of these methods as implemented in Figure 3 enjoy the full benefits of generics. The reason is that calls to non-generic interfaces for value types incur a boxing if the interface takes one or more object parameters, such as the obj parameter of CompareTo.
Each call to GenericMath.Min<T> in Figure 3 causes a boxing of the parameter to the CompareTo method if the instantiation of the method expands T to a value rather than to a reference. This is where generic interfaces can help.
The code in Figure 6 refactors the GenericMath methods to constrain T over a generic interface IComparable<T>. Now if an instantiation of Min<T> or Max<T> uses a value type as an argument to T, the interface call to CompareTo is part of the interface construction, its parameter is the value type, and no boxing occurs.
Generic delegates have similar benefits to generic interfaces, but are oriented to methods rather than types.
Generics in the Class Library
In addition to implementing generics in the CLR, Microsoft is planning to provide new generic library classes as part of the class libraries for the release of the CLR code-named "Whidbey". A preview release of the Whidbey CLR should be available about the time that this column goes to press. (For more details, see the September 2003 installment of this column.) Minimally, generic collection classes for implementing lists, dictionaries, stacks, and queues are expected. Additionally, the class libraries will include supporting interface types such as IList<T>, ICollection<T>, and IComparable<T>, which are generic equivalents of the simple interfaces that shipped in the Microsoft® .NET Framework 1.0 and 1.1 class libraries.
Finally, you will notice that types throughout the class library will be augmented with generic versions of new and existing functionality. For example, the System.Array class will include generic versions of its BinarySearch and Sort methods that take advantage of the generic interfaces IComparer<T> and IComparable<T>. At the time of this writing, Microsoft has not yet decided exactly how much of the existing class library will be reworked to include generic support in the next release of the runtime.
Conclusion
CLR generics are a powerful application and library development feature. Whether you choose to apply generics by using the collection classes or by architecting your app generically throughout, generics can make your code more type-safe, maintainable, and efficient. I have had fun with generics programming in managed code in these two installments of this column, and I look forward to the released product. It's exciting to see the CLR progress with the addition of significant features like generics. There are so many interesting possibilities. Stay tuned.
by ;jason