Category Archives: Cast operator

Static analysis of "is"

Posted on by
1

Returning now to the subject we started discussing last time on FAIC: sometimes the compiler can know via static analysis1 that an is operator expression is guaranteed to produce a particular result.

But before we get into that, let's briefly review the meaning of is in C#. The expression

x is T

for an expression x and a type T produces a bool. Generally speaking, if there is a reference, boxing or unboxing conversion from the runtime value of x to the type T then the result is true, otherwise the result is false. Note that in particular user-defined conversions are not considered. The intention of the operator is to determine if the runtime value of x is actually a useful value of the type T,2 and therefore we add a few additional caveats:

  • T may not be a pointer type
  • x may not be a lambda or anonymous method
  • if x is classified as a method group or is the null literal3 then the result is false
  • if the runtime type of x is a reference type and its value is a null reference then the result is false
  • if the runtime type of x is a nullable value type and the HasValue property of its value is false then the result is false
  • if the runtime type of x is a nullable value type and the HasValue property of its value is true then the result is computed as though you typed x.Value is T

So, knowing that, try to think of some situations in which you know for certain that x is T is going to always produce true, or always produce false. Here are a few that you and I know are always true:

int i = 123; 
bool b1 = i is int; 
bool b2 = i is IComparable; 
bool b3 = i is object; 
bool b4 = "hello" is string;

Here in every case we know first, that the operand is not null, and second, that the operand will always be of the given type, and therefore the operator will always produce "true".

Before we go on, I want to briefly review our criteria for when to make a warning: the warning in question has got to be (1) thought of, (2) possible to implement cheaply, (3) identify code that is both plausibly written by a real user and almost certainly wrong, but non-obviously wrong (4) be work-around-able should the code actually be correct and (5) not turn huge amounts of existing code into spurious errors.

Of these four lines, only the third strikes me as plausibly written by a real user and almost certainly wrong; the user must not realize that every int always implements IComparable. The other ones are just weird. Interestingly enough, the C# 5 compiler warns about the first three, but not the fourth.

There are a lot more situations where you know that the result will always be false. Can you think of some? Here are just a few off the top of my head:

bool b5 = M is Func<object>; // M is a method group 
bool b6 = null is object; 
bool b7 = b5 is IEnumerable; 
bool b8 = E.Blah is uint; // E is an enum type bool 
b9 = i is double;

The first two follow the rules of the spec. The latter three are cases where we can know via static analysis that the value cannot possibly be converted to the given type by a reference, boxing or unboxing conversion. The compiler produces a warning for all these trivially-analyzed cases. (Though of course again some of these examples -- b6 in particular -- are unlikely to show up in real code.)

That was a whole lot of preamble to the question I actually want to consider today, which is: how far should we go when making these sorts of static analyses for the purpose of warning that an is expression is always false? We could go a lot farther! I started this series off with a puzzle about the cases where there is no compile-time conversion from x to T, but nevertheless x is T can be true; today I want to talk about what we do when there is no compile-time conversion from x to T, and hey, x is T really cannot possibly be true as a result. There are lots of cases where you and I know that a given expression will never be of a given type, but these cases can get quite complex. Let's look at three complex ones:

class C<T> {} 
... 
static bool M10<X>(X x) where X : struct 
{ return x is string; } 
static bool M11<X>(C<X> cx) where X : struct 
{ return cx is C<string>; } 
static bool M12<X>(Dictionary<int, int> d) 
{ return d is List<X>; }

In case M10 we know that X will always be a value type and no value type is convertible to string via a reference, boxing or unboxing conversion. The type check must be false.

In case M11 we know that cx is of type C<some-value-type>, or a type derived from C<some-value-type>. You and I know that there is no way to get the same generic class type into a type hierarchy twice; there is no way to make something derive from both C<some-value-type> and C<string>. So the type check must be false.

In case M12 we know that there is no way to make an object that inherits from both the dictionary and list base classes, no matter what X is. The type check must be false.

In all these cases the compiler could produce a warning, but we are rapidly running up against the "possible to implement cheaply" criterion! The compiler team could spend a lot of expensive time coming up with heuristics which would not make a difference to real users writing real code. They have to draw the line somewhere.

Where is that line? The heuristic the compiler team actually uses to determine whether or not to report a warning when the compiler detects that there is no compile-time conversion from x to T is as follows:

  • If neither the compile time type of x nor the type T is an open type (that is, a type that involves generic type parameters) then we know that the result will always be false. There's no conversion, and nothing to substitute at runtime to make there be a conversion. Give a warning.
  • One of the types is open. If the compile time type of x is a value type and T is a class type then we know that the result will always be false.4 (This is case M10 above.) Give a warning.
  • Otherwise, abandon further analysis and do not produce a warning.

This is far from perfect, but it is definitely in the "good enough" bucket. And "good enough" is, by definition, good enough. Of course, this heuristic is subject to change without notice, should the compiler team discover that some real user-impacting scenario motivates changing it.

Next time on FAIC: How does the compiler ensure that the method type inference algorithm terminates?

  1. That is, analysis done knowing only the compile-time types of expressions, rather than knowing their possibly more specific run-time types ↩
  2. It is not to determine "is there any way to associate a value of type T with this value?" or "can the value x be legally assigned to a variable of type T?" ↩
  3. There are some small spec holes here and around these holes are minor inconsistencies between the C# 5 compiler and Roslyn. The spec does not say what to do if the expression x is a namespace or a type; those are of course valid expressions. The compiler produces an error stating that an expression with a value is expected. Similarly for write-only properties and write-only indexers. The original-recipe C# 5 compiler produces an error if the expression is a void-returning call, which technically is a spec violation; Roslyn produces a warning, though frankly, I'd be more inclined to change the spec in this case. The specification does say that x is T is an error if T is a static type; the C# 5 compiler erroneously allows this and produces false whereas the Roslyn compiler produces an error. ↩
  4. This is a lie; there is one case where the compile time type of x is an open value type and T is a class type, and there is no compile-time conversion from x to T, and x is T can be true, and therefore the warning must be suppressed. Can you write a program that demonstrates this scenario? I'll put the answer in the comments. ↩

An "is" operator puzzle, part two

Posted on by
1

As I said last time, that was a pretty easy puzzle. The solution is: either FooBar or the type of local variable x can be a type parameter. That is:

void M<FooBar>()
{
  int x = 0;
  bool b = x is FooBar;  // legal, true if FooBar is int.
  FooBar fb = (FooBar)x; // illegal
}

or

struct FooBar { /* ... */ }
void M<X>()
{
  X x = default(X);
  bool b = x is FooBar; // legal, true if X is FooBar
  FooBar fb = (FooBar)x; // illegal
}

This not only illustrates an interesting fact about is -- that an is expression can result in true even if the corresponding cast would be illegal -- but also an interesting fact about casts. Generally speaking, a cast is allowed if the conversion either is know at compile time to always succeed, or possibly succeed. But in these cases we have a situation where the cast could possibly succeed but is still illegal. What's up with that?

There are two main factors that come to mind, based on the dual nature of casts that I've mentioned before: a cast can mean "I know that this value is of the given type, even though the compiler does not know that, the compiler should allow it", and a cast can mean "I know that this value is not of the given type; generate special-purpose, type-specific code to convert a value of one type to a value of a different type."

But neither of these things are logical when type parameters are involved. In the context of the first meaning, a cast between a type parameter and a regular type essentially means "I know that the type parameter supplied is of the given type." But in that case, why do you have a type parameter in the first place? It's like having an integer formal parameter and then asserting that it is always twelve. Why did you have the parameter at all if you know ahead of time what the argument will be?

And in the context of the second meaning, in generic code we have no way to generate the special-purpose conversion logic. Let's take our first example code, above. If FooBar is double then we have to generate different code for int-to-double than if FooBar is long. We don't have a cheap and easy way to generate that code, and if user-defined conversions are involved then we need to do overload resolution at runtime. We added that feature to C# 4; if you want to generate fresh code at runtime that can do arbitrary conversions, use dynamic.

Next time on FAIC we'll explore the question "under what circumstances will the is operator give a warning at compile time stating that the operation is unnecessary?"

When is a cast not a cast?

Posted on by
Reply

I'm asked a lot of questions about conversion logic in C#, which is not that surprising. Conversions are common, and the rules are pretty complicated. Here's some code I was asked about recently; I've stripped it down to its essence for clarity:

class C<T> {} 
class D 
{
  public static C<U> M<U>(C<bool> c)   
  { return =something=; } 
} 
public static class X 
{ 
  public static V Cast<V>(object obj) 
  { return (V)obj; } 
}

where there are three possible texts for "=something=":

  1. (C<U>)c
  2. X.Cast<C<U>>(c);
  3. (C<U>)(object)c

Version 1 fails at compile time. Versions 2 and 3 succeed at compile time, and then fail at runtime if U is not bool.

Question: Why does the first version fail at compile time?

Because the compiler knows that the only way this conversion could possibly succeed is if U is bool, but U can be anything! The compiler assumes that most of the time U is not going to be constructed with bool, and therefore this code is almost certainly an error, and the compiler is bringing that fact to your attention.

Question: Then why does the second version succeed at compile time?

Because the compiler has no idea that a method named X.Cast<V> is going to perform a cast to V! All the compiler sees is a call to a method that takes an object, and you've given it an object, so the compiler's work is done. The method is a "black box" from the caller's perspective; the compiler does not look inside that box to see whether the mechanisms in that box are likely to fail given the input. This "cast" is not really a cast from the compiler's perspective, it's a method call.

Question: So what about the third version? Why does it not fail like the first version?

This one is actually the same thing as the second version; all we've done is inlined the body of the call to X.Cast<V>, including the intermediate conversion to object! That conversion is relevant.

Question: In both the second and third cases, the conversion succeeds at compile time because there is a conversion to object in the middle?

That's right. The rule is: if there is a conversion from a type S to object, then there is an explicit conversion from object to S.1

By making a conversion to object before doing the "offensive" conversion, you are basically telling the compiler "please throw away the compile-time information you have about the type of the thing I am converting". In the third version we do so explicitly; in the second version we do so sneakily, by making an implicit conversion to object when the argument is converted to the parameter type.

Question: So this explains why compile-time type checking doesn't seem to work quite right on LINQ expressions?

Yes! You would think that the compiler would disallow nonsense like:

from bool b in new int[] { 123, 345 } select b.ToString()

because obviously there is no conversion from int to bool, so how can range variable b take on the values in the array? Nevertheless, this succeeds because the compiler translates this to

(new int[] { 123, 345 }).Cast<bool>().Select(b=>b.ToString())

and the compiler has no idea that passing a sequence of integers to the extension method Cast<bool> is going to fail at runtime. That method is a black box. You and I know that it is going to perform a cast, and that the cast is going to fail, but the compiler does not know that.

And maybe we do not actually know it either; perhaps we are using some library other than the default LINQ-to-objects query provider that does know how to make conversions between types that the C# language would not normally allow. This is actually an extensibility feature masquerading as a compiler deficiency: it's not a bug, it's a feature! 2

Next time on FAIC: Should C# warn on null dereferences known to the compiler?

  1. Of course it is not the case that there is a conversion from every type to object. There is no conversion from any pointer type to object, from the void return type to object, and there are also some special "typed reference" helper types that cannot be converted to object. Maybe I'll discuss those in another episode of FAIC. ↩
  2. My glib statement here conveniently ignores that this method had quite a nasty bug in its initial release, a bug that was mostly my fault. Late in the game before the release one of the developers changed the implementation of the extension method so that it allowed more conversions than were specified, as a convenience to users. I reviewed the change while under the incorrect impression that the implemented behaviour was the specified behaviour. It was not, and the implementation was quite slow in a common code path. We took a breaking change in a service pack as a result. The cost of breaking a few people who might have been relying on the unintended behaviour was considered to be low compared to the cost to everyone of the slow implementation. This was a tough, controversial call but I think we did the right thing in the end. I regret the error. ↩

Representation and identity

Posted on by
Reply

(Note: not to be confused with Inheritance and Representation.)

I get a fair number of questions about the C# cast operator. The most frequent question I get is:

short sss = 123;
object ooo = sss;            // Box the short.
int iii = (int) sss;         // Perfectly legal.
int jjj = (int) (short) ooo; // Perfectly legal
int kkk = (int) ooo;         // Invalid cast exception?! Why?

Why? Because a boxed T can only be unboxed to T.1 Once it is unboxed, it’s just a value that can be cast as usual, so the double cast works just fine.

Many people find this restriction grating; they expect to be able to cast a boxed thing to anything that the unboxed thing could have been cast to. There are ways to do that, as we’ll see, but there are good reasons why the cast operator does what it does.

To understand why this design works this way it’s necessary to first wrap your head around the contradiction that is the cast operator. There are two2 basic usages of the cast operator in C#:

  • My code has an expression of type B, but I happen to have more information than the compiler does. I claim to know for certain that at runtime, this object of type B will actually always be of derived type D. I will inform the compiler of this claim by inserting a cast to D on the expression. Since the compiler probably cannot verify my claim, the compiler might ensure its veracity by inserting a run-time check at the point where I make the claim. If my claim turns out to be inaccurate, the CLR will throw an exception.
  • I have an expression of some type T which I know for certain is not of type U. However, I have a well-known way of associating some or all values of T with an “equivalent” value of U. I will instruct the compiler to generate code that implements this operation by inserting a cast to U. (And if at runtime there turns out to be no equivalent value of U for the particular T I’ve got, again we throw an exception.)

The attentive reader will have noticed that these are opposites. A neat trick, to have an operator which means two contradictory things, don’t you think?

This dichotomy motivates yet another classification scheme for conversions.3 We can divide conversions intorepresentation-preserving conversions (B to D) and representation-changing conversions (T to U).4 We can think of representation-preserving conversions on reference types as those conversions which preserve the identity of the object. When you cast a B to a D, you’re not doing anything to the existing object; you’re merely verifying that it is actually the type you say it is, and moving on. The identity of the object and the bits which represent the reference stay the same. But when you cast an int to a double, the resulting bits are very different.

All the built-in reference conversions are identity-preserving.5 Obviously trivial “conversions” such as converting from int to int are also representation-preserving conversions. All user-defined conversions6 and non-trivial value type conversions (such as converting from int to double) are representation-changing conversions. Boxing and unboxing conversions are all representation-changing conversions.

The representation-preserving conversions that are known to never fail often result in no codegen at all.7 If a representation-preserving conversion could fail then a castclass instruction is emitted, which does a runtime check and throws if the check fails.

But each representation-changing conversion is handled in its own special way. User-defined conversions are resolved using a special version of the overload resolution algorithm, and generated as a call to the appropriate static method. Boxing and unboxing conversions are generated as box and unbox instructions. All the other built-in conversions (int to double, and so on) are generated as custom sequences of instructions that do the right conversion.

So now that you know that, consider what the compiler would have to do to make this work the way some people expect:

int kkk = (int) ooo;

All that the compiler knows is that ooo is of type object. It could be anything. Suppose it is a boxed int – then the compiler should generate an unboxing instruction. Suppose it is a boxed short. Then the compiler should unbox the short and then generate the custom sequence of instructions that convert a short to an int. Suppose it is a boxed double – same thing, but different instructions. And so on, for all the built-in conversions that go to int.

This would be a huge amount of code to generate, and it would be very slow. The code is of course so large that you would want to put it in its own method and just generate a call to it. Rather than do that by default, and always generate code that is slow, large and fragile, instead we’ve decided that unboxing can only unbox to the exact type. If you want to call the slow method that does all that goo, it’s available – you can always call Convert.ToInt32, which does all that analysis at runtime for you. We give you the choice between “fast and precise” or “slow and lax”, and the sensible default is the former. If you want the latter then call the method.

That’s just the built-in conversions. Let’s continue imagining what would have to happen if we wanted all possible conversions to int to just work out correctly at runtime, instead of just bailing out early if the boxed thing is not an int.

Suppose the object is a Foo where there is a user-defined conversion from Foo (or one of its base classes) to int (or a type that int is explicitly convertible from, like, say, Nullable<int>). Then the compiler would need to generate a call to that conversion method, just as it would if the type had been known at compile time, and then possibly also generate the conversion from the return type of the method to int.

Remember, there could be arbitrarily many such conversion methods on arbitrarily many types. The type Foo and its conversion method might not even be defined in the assembly currently being compiled or any assembly referenced. Therefore the compiler would have to generate code to interrogate Foo at runtime, do the overload resolution analysis, and then dynamically spit the code to do the call.

Which is exactly what the compiler does in C# 4.0 if the argument to the cast is of type dynamic instead of object. The compiler actually generates code which starts a mini version of the compiler up again at runtime, does all that analysis, and spits fresh code. This is not fast, but it is accurate, if that’s what you really need. (And the spit code is then cached so that the next time this call site is hit, it is much faster.)

I don’t think people really expect the compiler to start up again at runtime every time they cast an object to int; I think they just haven’t thought through carefully exactly how much analysis solving the problem would take. Rather a lot, it turns out.

  1. Or Nullable<T>. ↩
  2. There are others that are not germane to this discussion. For example, a third usage is “Everyone knows that this D is also of base type B; I want the compiler to treat this expression of type D as a B for overload resolution purposes.” That would clearly be an identity-preserving conversion. ↩
  3. There are many ways to classify conversions; we already divide conversions into implicit/explicit, built-in/user-defined, and so on. For the purposes of this discussion we’ll gloss over the details of those other classifications. ↩
  4. I’m glossing over here that certain conversions that the C# compiler thinks of as representation-changing are actually seen by the CLR verifier as representation-preserving. For example, the conversion from int to uint is seen by the CLR as representation-preserving because the 32 bits of a signed integer can be reinterpreted as an unsigned integer without changing the bits. These cases can be subtle and complex, and often have an impact on covariance-related issues; see next footnote. I’m also ignoring conversions involving generic type parameters which are not known at compile time to be reference or value types. There are special rules for classifying those which would be major digressions to get into. ↩
  5. This is why covariant and contravariant conversions of interface and delegate types require that all varying type arguments be of reference types. To ensure that a variant reference conversion is always identity-preserving, all of the conversions involving type arguments must also be identity-preserving. The easiest way to ensure that all the non-trivial conversions on type arguments are identity-preserving is to restrict them to be reference conversions. ↩
  6. The rules of C# prohibit all user-defined conversions that could possibly be identity-preserving coercions. More generally, all user-defined conversions that could possibly be any "standard" conversion are illegal. ↩
  7. Again, I’m ignoring irksome generic issues here. There are situations where humans can prove mathematically that two generic type parameters must be identical at runtime, but the verifier is not smart enough to make those same deductions and requires the compiler to emit type checks. ↩