Jaa

Why is covariance of value-typed arrays inconsistent?

  • Artikkeli

Another interesting question from StackOverflow:

uint[] foo = new uint[10];
object bar = foo;
Console.WriteLine("{0} {1} {2} {3}",       
  foo is uint[], // True
  foo is int[],  // False
  bar is uint[], // True
  bar is int[]); // True

What the heck is going on here?

This program fragment illustrates an interesting and unfortunate inconsistency between the CLI type system and the C# type system.

The CLI has the concept of "assignment compatibility". If a value x of known data type S is "assignment compatible" with a particular storage location y of known data type T, then you can store x in y. If not, then doing so is not verifiable code and the verifier will disallow it.

The CLI type system says, for instance, that subtypes of reference type are assignment compatible with supertypes of reference type. If you have a string, you can store it in a variable of type object, because both are reference types and string is a subtype of object. But the opposite is not true; supertypes are not assignment compatible with subtypes. You can't stick something only known to be object into a variable of type string without first casting it.

Basically "assignment compatible" means "it makes sense to stick these exact bits into this variable". The assignment from source value to target variable has to be "representation preserving".

One of the rules of the CLI is "if X is assignment compatible with Y then X[] is assignment compatible with Y[] ".

That is, arrays are covariant with respect to assignment compatibility. As I've discussed already, this is actually a broken kind of covariance.

That is not a rule of C#. C#'s array covariance rule is "if X is a reference type implicitly convertible to reference type Y (via a reference or identity conversion) then X[] is implicitly convertible to Y[] ". That is a subtly different rule!

In the CLI, uint and int are assignment compatible; therefore uint[] and int[] are too. But in C#, the conversion between int and uint is explicit, not implicit, and these are value types, not reference types. So in C# it is not legal to convert an int[] to a uint[]. But it is legal in the CLI. So now we are faced with a choice.

1) Implement "is" so that when the compiler cannot determine the answer statically, it actually calls a method which checks all the C# rules for identity-preserving convertibility. This is slow, and 99.9% of the time matches what the CLR rules are. But we take the performance hit so as to be 100% compliant with the rules of C#.

2) Implement "is" so that when the compiler cannot determine the answer statically, it does the incredibly fast CLR assignment compatibility check, and live with the fact that this says that a uint[] is an int[], even though that would not actually be legal in C#.

We chose the latter. It is unfortunate that C# and the CLI specifications disagree on this minor point but we are willing to live with the inconsistency.

So what's going on here is that in the "foo" cases, the compiler can determine statically what the answer is going to be according to the rules of C#, and generates code to produce "True" and "False". But in the "bar" case, the compiler no longer knows what exact type is in bar, so it generates code to make the CLR answer the question, and the CLR gives a different opinion.

Comments

  • Anonymous
    September 24, 2009
    The really crazy part is it's not just "is" that does it            var x = new int[] { -1 };            uint[] y = (uint[])(object)x;            Console.WriteLine(y[0]); // 4294967295            x[0] = int.MinValue; // prove that x really is the same object as y            Console.WriteLine(y[0]); // 2147483648 At least it's guaranteed to always be twos-complement.

  • Anonymous
    September 24, 2009
    The comment has been removed

  • Anonymous
    September 24, 2009
    The comment has been removed

  • Anonymous
    September 24, 2009
    @DRBlaise, if arbitrary value types were assignment compatible like that, it would provide an easy way to defeat encapsulation. DateTime contains a private field; you're not supposed to mess with it and e.g. break its invariants, but if you could cast a long[] with arbitrary value in it to DateTime[], that's precisely what you could do. In contrast, treating int[] as uint[] is safe in that the types have exact, well-defined 1-to-1 value correspondence, so there's nothing you could possibly gain in terms of circumventing encapsulation or type safety by such a cast. And before you mention reflection, remember that it requires certain CAS permission checks for the calling code, while casting int[] to uint[] does not.

  • Anonymous
    September 24, 2009
    @Pavel - Thanks for the explanations.  The inconsistentancies with enums boxing, unboxing, and IS were particularly mind blowing.

  • Anonymous
    September 24, 2009
    Off-topic (?): I would like to see from Microsoft, within a decade from now, a complete new framework base without these types of incoherent behavior and supporting natively: Co+contra variance at the type system level (not just for delegates and interfaces), tuples, inmmutabiilty, STM, weak events, unloadable app-domains, and whatever needed thinking in tomorrow computing. Stop forcing compatibility with legacy technologies and bring something CONSISTENT. Then for compatibility make special types (like that dynamic of c# 4.0) or virtualize.

  • Anonymous
    September 24, 2009
    Nestor:   I think you miss the point.  Microsoft was doing exactly what you asked: building a new framework that was consistent and easy to use.  They called it .NET and shipped it in 2002.  7 years later we find that a few (and a very few by the way) of the decisions made back in 1998 and 1999 are different than we would have chosen. The problem is that without the benefit of a time machine, there is no reason to believe they would do any better this time than last time.  I'm sure they would have never done anonymous delegates in C# 2,0 if they knew that lambdas were comming in C# 3.0.  The new system would sprout its own warts and  be just as inconsistent as ,NET within a month of release. Furthermore it seems most of what you ask for can (and in many instances is) be implemented without a top to bottom rewrite.  Read Joel's adminition on why you should never start over from scratch: http://www.joelonsoftware.com/articles/fog0000000069.html

  • Anonymous
    September 24, 2009
    Interesting post. Is this going to change, along with the generic co/contravariance changes in C#4.0?

  • Anonymous
    September 24, 2009
    @John The article by Spolsky is a bit drastic. And after the (good) initial assumption that writing a program from scratch will take a long time, it continues with a long list of "what ifs" that really don't demonstrate anything. I will reply to his article with my own questions:

  • what if the old program REALLY is a mess?
  • what if the old program was badly patched/maintained for 10 years?
  • what if the new team DOES have more experience?
  • what if the new team gets better requirements than the old team?
  • what if the old program (service) is still making an astonishing amount of revenue, while we develop the new one?
  • what if I want to switch platform? My company switched platform for it's core business from mainframe to .NET 4 years ago. With a total rewrite. It was long and hard, but it worked. But, obviously, it's not a rule. Recently, we developed a new version of another program, switching from .NET to Java, with a rewrite from zero. The results were... uhm... less brilliant :-)

  • Anonymous
    September 25, 2009
    @Filini: Or perhaps the results were more brillant:  http://thedailywtf.com/articles/the_brillant_paula_bean.aspx

  • Anonymous
    September 25, 2009
    > Stop forcing compatibility with legacy technologies and bring something CONSISTENT. It's funny how .NET is already "legacy", when just 3-4 years ago you could still hear a lot of people moaning about how COM (usually in VB6 context) was perfectly fine, and how evil MS is because it "killed" (eh?) it with .NET.

  • Anonymous
    September 25, 2009
    John: I was not talking about a fully rewrite of everything. I just wanted to put in perspective -within the next decade- that .NET will become of age and there is IMHO a need to sacrifice legacy compatibility toward reaching a consistent multiparadigm coexistence in the same framework. Considering the evolution of such paradigms (functional composability, meta-programming, etc.), plus multicore hardware, the Cloud and so on... I think it is becoming necessary to think ahead like in these 1995-1999 years when .NET was conceived. Let's think about the ".CLOUD" (or ".CORE") framework structural basis ;) I'm sure these kind of things are being discussed at some level on MS, but of course they cannot share these speculative thinkings for the same reasons the USAF doesn't talk so much about Area 51.

  • Anonymous
    September 25, 2009
    It seems like option 3 would have been to use the CLR assignment compatibility check, plus an extra check for the known differences between the C# rules and the CLR rules (which as you said are extremely limited). This would limit the performance impact but still maintain consistency. Broadly speaking, I much prefer consistency over performance shortcuts. Although you describe "a method which checks all the C# rules for identity-preserving convertibility" as "slow", in reality it would be blindingly fast; it would only be slow compared to the even-more-blindingly fast CLR check. We all know the cliche about premature optimization, but frankly it is cliche because it is so often true. I would rather suffer an incredibly tiny performance degradation and avoid these kinds of inconsistencies that lead to subtle bugs, which cost time, money, and user confidence.

  • Anonymous
    September 26, 2009
    I was amazed to know the "C# team" had done a trade-off such as this one. You chose speed over correctness (w.r.t. the C# specification)! Yep. If it helps you get through the grieving process, think of it not as an incorrectness but as a special extra feature. An extension of the language, as it were. -- Eric Had you chosen speed over prettyness, it could be understood, not this. You bended the rules, and thought no one's ever going to use this, so no one's ever going to notice this...but who knows how many hours have been lost debugging such a thing. We'll never know. But considering that I've personally seen a grand total of one user mention this issue in the last four years, my guess would be that the number is small. -- Eric I felt glad that I am so many times lazy, for not using uint or even arrays of ints (I prefer ints and generic ILists for almost anything I do, as long as it doesn't become a performance bottleneck)!

  • Anonymous
    September 27, 2009
    > You bended the rules, and thought no one's ever going to use this, so no one's ever going to notice this...but who knows how many hours have been lost debugging such a thing. Can you come up with a realistic scenario where allowing to treat int[] as uint[] would be harmful and require "hours of debugging"? Actually, can you come up with a realistic scenario where strict array variance semantics, as described by C# spec, is fundamental to the design of the code in question, and would be broken on VC#?

  • Anonymous
    September 28, 2009
    The comment has been removed

  • Anonymous
    September 30, 2009
    @David, I know very well about that particular issue (I upvoted it immediately when it first appeared, and all comments posted under the alias "int19h" there are mine). The problem with it, however, is that it is a breaking change - as in, it quietly changes the behavior of code that was legal on the same implementation (and according to specification) before. It was made more restrictive than it was, which is why it is such a big deal. In addition, it actually affects some very valid use cases for generics. I'm very surprised that someone in MS actually assessed the change as "not significant", because to me it clearly is, even before a customer comes in with a concrete example of broken code. In contrast, array variance has been working the same way on all .NET releases, starting from the very first one. Furthermore, it is more permissive than what the spec allows, rather than more restritive. In practice, this means that it's only a breaking change if a code somewhere relies on either the result of an "is" or "as" check being null, or on a cast throwing InvalidCastException, and not being able to correctly handle an array of different-signedness values received. I simply cannot think of any case where it would matter. Can you? In the end, the fact that there's no bug report for this, even though the inconsistency (or the language extension, whichever is your take on it) has been there for 7 years now, seem to prove the point better than anything else.

  • Anonymous
    September 30, 2009
    @Pavel, I knew that you are int19h. I am not sure if you were aware that I am CommonGenius, and I reported the bug initially :) A "feature" which does not match expectations AND is undocumented has the same affect as a breaking change. You write code that looks like it should work, but it doesn't. Especially on a corner case like this, unless you have exceptionally good test coverage, there is a very good chance that you won't catch it during development. Then one day something unusual happens and your production application starts crashing. And good luck finding the problem, since everything you can see in the code looks correct. Yes, the fact that it is a corner case makes it less likely to show up as a real world problem. But it also means that, when it does show up, it will be vastly more difficult to find and fix. Especially since it is apparently not documented anywhere (except this blog post and the stackoverflow question). I cannot think of a specific case where this bug (and I do consider it a bug, Eric's explanation notwithstanding) would cause problems for me, mostly because I rarely use unsigned types. But absence of proof is not proof of absence. Despite having significant programming experience and a very strong knowledge of .NET, I am certain that I can only imagine a very small percentage of the possible use cases of the platform. Even the .NET team with all of their combined knowledge and experience cannot possibly anticipate every possible use case. That is precisely why general purpose languages exist: to provide a foundation on which specialized functionality can be built, even when that specialized functionality cannot be foreseen. But when the foundation is shaky, the structure is in constant danger of collapsing.

  • Anonymous
    September 30, 2009
    @David, I agree with everything in your post, but I believe that calling .NET "shaky" is a serious overstatement. In the 37+ years I have been developing software I have not encountered a single compiler/platform that was "perfect"; neither have I encountered something as wide reading as the .Net framework and assocuated languages. "Pound for Pound" I do believe it is by far the best I have seen (albiet not perfect) in all these years.

  • Anonymous
    October 01, 2009
    Just another good reason to avoid raw arrays.

  • Anonymous
    October 01, 2009
    @TheCPUWizard I agree with you. I switched to .NET from C++ 6 years ago and have never looked back. My few forays into Java are dark periods of my life that I would rather forget. I have staked my career on the viability of the .NET platform as a way to quickly deliver quality applications that provide value to end users. However, as you said, no platform is perfect, and I think it is perfectly legitimate to describe the way in which those imperfections hurt the platform as a whole, in the hopes that similar mistakes are not made in the future. In this case, it was not my intention to describe the entire .NET framework as "shaky", but rather to point out that any application which is built believing that this particular case works as expected has a shaky foundation that could collapse at any time without warning and without any explanation. Allowing that kind of unseen danger into a general purpose platform for the sake of premature performance optimization was, IMHO, a bad design decision.

  • Anonymous
    July 17, 2011
    The comment has been removed