Non-Nullable Types vs C#: Fixing the Billion Dollar Mistake

posted by Craig Gidney on September 24, 2012

One of the top suggestions (currently #15 on uservoice) for improving C# is the addition of non-nullable reference types. This is not surprising, considering the number of functions that start with a block of ‘if (x == null) throw new ArgumentNullException(“x”)’ lines. Not to mention the head-slapping bugs null pointers cause. There’s a reason Tony Hoare calls the null pointer his billion dollar mistake.

In this post I will talk about the obstacles that make adding non-nullable types to C# difficult, and propose a way forward.

Obstacles

Adding non-nullable types to C# seems, on the surface, easy. Put a “!” at the end of the type to mean non-nullable, add some nullable/non-nullable conversation operators, implement a few compiler checks and you’re done… right? Oops, we just broke the cohesiveness of the language. The compiler keeps refusing to compile “new object![10]” (it can’t figure out what to fill the array with initially). Naturally, all of the generic classes that happen to use arrays also refuse to work for the same reason (goodbye List<T>) but some generic class that don’t use arrays like TaskCompletionSource<T> also fail. Bleh.

I should note at this point that C# is a mature language with mountains of already-written code that we aren’t allowed to break. If adding non-null types to the language breaks existing code, then non-null types won’t get added. We have to work within the constraints of backwards compatibility, which is tricky when removing widely-used assumptions. To give an idea of the sorts of code we can’t break, I’ve put together a list of the cases I think are important. Before reading on, you may want to spend a minute imagining how you would add non-nullability to C#. See if your idea meshes with each case in an elegant way:

Existing generic code allocates arrays:

public T[] ToArray(IReadOnlyCollection<T> items) {
    var r = new T[items.Count];
    ...
    return r;
}

Existing generic code uses default(T):

public T FirstOrDefault(IEnumerable<T> items) {
    using (var e = items.GetEnumerator()) {
        return e.MoveNext() ? e.Current : default(T);
    }
}

Existing generic code propagates generic parameters:

default(KeyValuePair<K, V>) // if K or V has no default value...

Existing generic classes that intuitively should accept non-nullable types (a.k.a. are “non-null safe”) may use constructs that assume a default value exists:
```
public class List<T> {
    ...
        _items = new T[capacity];
    ...
}
```

Classes that are intuitively non-null safe may not always initialize fields, implicitly assuming a default value is used (and you may be able to access that value via reflection):

public struct Maybe<T> {
    private readonly T _value;
    public readonly bool HasValue;
    public T Value { 
        get { 
            if (!HasValue) throw new InvalidOperationException();
            return _value;
        }
    }
    // default constructor creates a 'no value' instance where _value = default(T)
    public Maybe(T value) { HasValue = true; _value = value; }
}

A common pattern, ‘bool TryX(out T result)’, assumes a default value to assign to ‘result’ when failing:

bool TryParseValue(out T value) {
    if (...) {
        ...
        value = ...
        return true;
    }
    value = default(T);
    return false;
}

Some interfaces are intuitively non-null safe, but use the TryX pattern:

public interface IReadOnlyDictionary<TKey, TValue> : IReadOnlyCollection<KeyValuePair<TKey, TValue>> {
    ...
    bool TryGetValue(TKey key, out TValue value);
    ...
}

Most interfaces happen to be (somewhat) naively non-null safe (although implementations may not be), but it’s possible to create ones that aren’t:
```
public interface IMustHaveDefault<T> {
    void DoIt(T value = default(T)); 
}
```
Analogously, most delegates happen to be non-null safe, but it’s not guaranteed:
```
delegate void MustHaveDefault<T>(T value = default(T))
```

Existing code may extend legacy code that won’t be updated for non-nullability:

interface IBloomFilter<T> : SomeOldUnmaintainedLibrary.IHeuristicSet<T> {
    ...
}

How did your impromptu idea do?

The fundamental problem here is an assumption deeply ingrained into C#: the assumption that every type has a default value. Consider: if T doesn’t (or might not have) a default value then the compiler has nothing to use when evaluating default(T), initializing a field of type T, or initializing the items in a new array of T. This is a problem when it comes to non-null reference types because, although some reference types have a decent non-null default value (e.g. the default non-null String could be the empty string), most do not. Consider: what is the default non-null value of IEnumerator<int>? IObservable<bool>? UserControl? NetworkStream? The simple answer is that they don’t have one. The “best” you can do is give a mock instance that fails if you try to use it… but we already have that and it’s called null.

Note that there may be important cases I’ve missed here. C# is a very large language and I don’t have experience with all of its parts, particularly native interop things like unsafe and pinned. There are surely plenty of complications with respect to type inference and lambdas that I’m not exploring. I’m also going to gloss over the implications on reflection, other than to note that the result of GetType will be unable to indicate non-nullability and that this may be counter-intuitive to users. (Hopefully whatever I’ve overlooked won’t make what I propose in the next section utterly useless.)

Proposed Solution

All the obstacles I’ve mentioned can be overcome. The way I’ve approached the problem is by adding three bits of syntax to C#: an ‘is non-null’ type modifier, a ‘may be non-null’ type parameter modifier, and a ‘withdefault’ keyword to undo making a type non-nullable. The basic idea for making code non-null safe it to wrap T! into withdefault(T!) on the way in and cast back to T! on the way out.

I find it difficult to succinctly explain what I mean in prose, so I’m just going to go with a list. These are the semantic changes I would make to C# to allow non-nullable types:

Appending “!” to a (nullable) reference type means “is non-nullable”. A variable of type “object!” can reference an object, but may not be a null reference.
Appending “!” to a generic type parameter means “is potentially non-nullable”. The type parameter T in “class C<T>” can’t be “object!”, but it could be if the declaration was “class C<T!>”.
Invoking “withdefault” on a non-nullable reference type returns the associated nullable reference type but otherwise returns the same type. withdefault(object!) = object = withdefault(object), withdefault(int) = int, withdefault(int?) = int?.
For any (nullable) reference type T there is an explicit cast operator from T to T! that throws when given null.
A T! “is a” T. Consequently, for example, an IEnumerable<T!> is an IEnumerable<T> by covariance.
The expression “default(T)” is a compile error when T is potentially non-nullable.
The expression “new T[n]” is a compile error when T is potentially non-nullable and n is not a constant zero. Note that new T[] { … } may still work.
Using a potentially non-nullable type as the argument to a generic type parameter that is not marked as potentially non-nullable is a compile error.
A struct or class containing a field with a potentially non-nullable type is not given a default empty constructor by the compiler.
In a constructor, all fields with a potentially non-nullable type must be initialized before ‘this’ can be used.
The type of a constructor invocation expression is now non-null when the constructed type is a reference type. For example, “new object()” has type “object!”.
A few existing compiler errors, like disallowing constraining a generic parameter by a sealed type, need to be removed or rethought (because T! is a T, even if T is sealed).

Additionally, the following things should not be breaking changes, when done by the user:

Changing usage of a type T to withdefault(T) or vice versa, unless T is potentially non-nullable. This allows tweaking the return types of generic methods to make sense when T is non-nullable, without breaking existing code.
Changing a type argument from withdefault(T) to T when the type parameter is covariant, or vice versa when the type parameter is contra-variant. This is useful for interop with legacy code because we can expose non-nullability right away without painting ourselves into a corner. For example, suppose IEnumerable<T> has not been marked non-null safe. A non-null safe class can implement IEnumerable<withdefault(T)> in the interim and, once IEnumerable is made non-null safe, implementing IEnumerable<T> instead will not break existing code because a T! is a T.

Finally, some useful additions to the .Net base class library that I would recommend, although they aren’t necessary:

A special method to create an array of a non-null type from an IReadOnlyCollection<T!>.
A non-null safe array type that can be initialized incrementally (perhaps a better name would be CappedList<T!>).
A standard maybe/option type that is non-null safe.

Given these language changes, it is relatively simple to update/implement code with non-null safety. As I’ve already mentioned, you just abuse withdefault(T!) and casting from T to T! to assert to the compiler that you’ve done things right (if you haven’t, you’ll get an exception during the cast at runtime). I’ll go over some examples in a moment. As more code is made non-null safe, the amount of casting and withdefault-ing you need should go down.

The changes to make code non-null safe are so simple that you might expect the conversion to be automatable. Unfortunately, human judgement is necessary in a some cases. For example, the return type of FirstOrDefault<T!> is withdefault(T!) but the return type of First<T!> is just T!. Doing the conversion automatically would require analyzing the implementations of those methods to figure out that default(T) might flow out of FirstOrDefault<T> but not First<T>. But even with a magical halt-problem-avoiding analysis, we’d find it impossible to infer the non-nullability of interfaces and abstract classes, because their implementing code may not even be in the same assembly! We must update the code by hand.

Examples

In order to give you a more concrete taste of how non-nullable types would work in practice, given that this proposal were implemented, I’ve prepared two examples. The first is a simple maybe/option type that is non-null safe:

///May contain a value or no value. Non-null safe.
public struct Maybe<T!> {
    private readonly withdefault(T) _value;
    public readonly bool HasValue;
    public T Value { 
        get { 
            if (!HasValue) throw new InvalidOperationException();
            return (T)_value;
        }
    }
    // note: has default constructor for 'no value'
    public Maybe(T value) { HasValue = true; _value = value; }
}

As you can see, the _value field is of type “withdefault(T)” but exposed as type T by using a cast inside the Value property. Note that if you tried to change the field to type T, the compiler would omit the default constructor. As a result, you would need to implement it explicitly (otherwise you can’t create the No Value instance) and, in doing so, would discover it to be impossible to satisfy the requirement that _value be initialized before ‘this’ can be accessed. Most classes would be updated in the same way: withdefault in, cast out.

The second example I have is more involved, because it uses a real existing class. I call it “how to make System.Collections.Generic.Dictionary non-null safe (in spirit)”. I used reflector to get source code for Dictionary (and cleaned it up a bit with ReSharper). However, to keep the example short, I am only including the notable changes necessary to upgrade the important public methods (Add, Remove, this[]) and the implementation of the IReadOnlyDictionary interface. Additions are highlighted in green, deletions are struck-through and highlighted in red:

public interface IEnumerable<out T!> : IEnumerable {
...
public interface IReadOnlyCollection<out T!> : IEnumerable<T> {
...
public interface IReadOnlyDictionary<TKey!, TValue!> : IReadOnlyCollection<KeyValuePair<TKey, TValue>> {
    bool ContainsKey(TKey key);
    bool TryGetValue(TKey key, out withdefault(TValue) value);
    TValue this[TKey key] { get; }
...
public class Dictionary<TKey!, TValue!> : IReadOnlyDictionary<TKey, TValue> {
    private int[] _buckets;
    private int _count;
    private Entry[] _entries;
    private int _freeCount;
    ...
            for (var j = 0; j < _count; j++) {
                if ((_entries[j].HashCode >= 0) && comparer.Equals((TValue)_entries[j].Value, value))
                    return true;
            }
    ...
            for (var i = _buckets[num%_buckets.Length]; i >= 0; i = _entries[i].Next) {
                if (_entries[i].HashCode == num && Comparer.Equals((TKey)_entries[i].Key, key))
                    return i;
            }
    ...
    internal withdefault(TValue) GetValueOrDefault(TKey key) {
        var index = FindEntry(key);
        if (index >= 0) return _entries[index].Value;
        return default(withdefault(TValue));
    }
    ...
        for (var i = _buckets[index]; i >= 0; i = _entries[i].Next) {
            if ((_entries[i].HashCode == num) && Comparer.Equals((TKey)_entries[i].Key, key)) {
                if (add)
	...
            for (var i = _buckets[index]; i >= 0; i = _entries[i].Next) {
                if ((_entries[i].HashCode == num) && Comparer.Equals((TKey)_entries[i].Key, key)) {
                    ...
                    _entries[i].HashCode = -1;
                    _entries[i].Next = _freeList;
                    _entries[i].Key = default(withdefault(TKey));
                    _entries[i].Value = default(withdefault(TValue));
                    _freeList = i;
                    _freeCount++;
                    _version++;
                    return true;
    ...
            for (var k = 0; k < _count; k++) {
                if (destArray[k].HashCode != -1)
                    destArray[k].HashCode = Comparer.GetHashCode((TKey)destArray[k].Key) & 0x7fffffff;
            }
    ...
    public bool TryGetValue(TKey key, out withdefault(TValue) value) {
        var index = FindEntry(key);
        if (index >= 0) {
            value = _entries[index].Value;
            return true;
        }
        value = default(withdefault(TValue));
        return false;
    }
    ... 
    public TValue this[TKey key] {
        ...
                return (TValue)_entries[index].Value;
	...
    private struct Entry {
        public int HashCode;
        public int Next;
        public withdefault(TKey) Key;
        public withdefault(TValue) Value;
    }
    ... 
    public struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue>> {
        ...
        private withdefault(KeyValuePair<TKey, TValue>) _current;
        ...
        public bool MoveNext() {
            while (_index < _dictionary._count) {
                if (_dictionary._entries[_index].HashCode >= 0) {
                    _current = new KeyValuePair<TKey, TValue>(
                        (TKey)_dictionary._entries[_index].Key,
                        (TValue)_dictionary._entries[_index].Value);
                    _index++;
                    return true;
                }
                this._index++;
            }
            this._index = this._dictionary._count + 1;
            this._current = default(withdefault(KeyValuePair<TKey, TValue>))new KeyValuePair<TKey, TValue>();
            return false;
        }
    ...

Once again you can see the “write withdefault(T), read T by casting” technique, except it is used in several places. Otherwise the only notable change is to the signature of TryGetValue: the out parameter now has type withdefault(TValue). You might expect this to break existing code, because we’re changing the signature, but it works out that we only change the signature in new cases. TValue couldn’t be a non-nullable reference type before, and withdefault(T) = T in that case.

Summary

Adding non-null types to C# is do-able, but not simple and not cheap. I’m sure it overcomes the features start at -100 points threshold, but that’s before considering the implementation costs. Even if the feature was already implemented in the language, there are mountains of existing classes that need to be updated.

We may never see non-null types in C#, but I hope we do.

View comments on reddit

8 Responses to “Non-Nullable Types vs C#: Fixing the Billion Dollar Mistake”

Keith Hill says:

February 27, 2014 at 1:32 pm

I agree this would be a very worthy addition to C#. Heck, I liked this idea back when MSR was toying with non-nullable reference types in Spec#. http://research.microsoft.com/en-us/projects/specsharp/

Zahir Tezcan says:

February 27, 2014 at 5:27 pm

how do you tackle with the problem of calling virtual methods from constructors or destructors? because unlike c++ standard current C# compiler on visual studio calls the most overloaded function from the base class constructor. Output of this C++ program (http://cppquiz.org/quiz/question/29) is “121” but in C# such pattern starts with a “2”. Now with non-nullable types as members we need to initialize them first before calling member methods right? What if base class is calling?

CraigGidney says:

February 27, 2014 at 7:40 pm

This is probably the hairiest bit of what has to change, and the most likely reason the change wouldn’t be made. Either non-nullable fields need to be initialized *before* the base constructor runs, with something like C++ initialization syntax, or it needs to be illegal to modify or read non-nullable fields in virtual methods, or some other terrible tradeoff.

Then you get to the really nasty cases, like aborting during construction and the finalizer seeing a null non-nullable… see Eric Lippert’s blog post about it: http://blog.coverity.com/2013/11/20/c-non-nullable-reference-types/#.Uw_MhPldUmE

kbiel says:

September 5, 2014 at 6:08 pm

It seems to me that you have merely swapped NullReferenceException for InvalidOperationException. The consumer will still need an if statement to check HasValue before invoking the Value property getter.

Then you might propose having a GetValueOrDefault method that will be entirely safe. This can already be done with extension methods though. C# will readily invoke an extension method on a null object passing null into the first (this) parameter. For example:

public static class ExtMethods
{
public static string GetEmptyIfNull(this string value)
{
return value == null ? string.Empty : value;
}
}
…
string test = null;
Console.WriteLine(test.GetEmptyIfNull());

Note that the compiler will refuse to compile if “test” is not assigned a null (or some other value) even though the result would be the same.

CraigGidney says:

September 6, 2014 at 4:05 pm

All the checks proposed either happen at compile time or require explicit casts. Additionally, the explicit checks can be encapsulated inside classes like lists so callers don’t have to do them.

This significantly reduces the number of places where mistakes can be made. The remaining ones do essentially replace one type of exception with another, but they are fewer and easier to spot.

kbiel says:

September 8, 2014 at 2:06 pm

“The remaining ones do essentially replace one type of exception with another, but they are fewer and easier to spot.”

The remaining ones are the original problem domain. We’re trying to avoid this:

public string Foo(object a)
{
return a.ToString(); //Oops. Forgot to guard with if (a != null)
}

But I fail to see how this is easier to spot or avoid:

public string Foo(object! a)
{
return a.Value.ToString(); //Oops. Forgot to guard with if (a.HasValue)
}

The difference between a non-null reference type and a nullable value type is that the nullable container adds information to the value type. The non-null container takes information that could already be carried in the variable (null) and recasts it as a boolean property. The “no value” singleton might have some value in providing default behavior, but you can do that without a non-null container by providing a singleton default type to be used like this:

public string Foo(RefType a)
{
return (a ?? RefType.Default).ToString(); //This is looking pretty lazy, but still requires a conscious effort to remember to coalesce.
}

Using static methods we can target certain behaviors that we think should have a default but it becomes implicit (by lack of implementation) which would not have a default behavior without throwing a bunch of InvalidOperationException exceptions:

public string Foo(RefType a)

{
return RefType.ToStringOrDefault(a); //This method checks for null for me.
}

That can be recast to an extension method if you want to make it fully lazy:

public string Foo(RefType a)
{
return a.ToStringOrDefault(); //Is ‘a’ null? Who cares, the extension method will take it and check for me.
}

Note: I am not advocating for this as a good pattern. I think a bunch of extension methods designed to check tens or hundreds or thousands of types for null for me, while cool and easy, actually makes code harder to follow as it might hide nulls to someone debugging your code for the first time.

CraigGidney says:

September 8, 2014 at 8:11 pm

I think you misunderstood what the post is suggesting. There is not a value getter on Object!. An Object! is an Object, just statically guaranteed to not be null. It is impossible to have an Object! that is null or absent or invalid or uninitialized.

For example, there is no default(Object!). Which means you need special rules for fields and arrays and generics, as is elaborated on in the post.

Jim Balter says:

January 31, 2015 at 1:45 am

Please see https://github.com/dotnet/roslyn/issues/98 [NULL] … it seems that they read Eric Lippert’s blog post without bothering to read any of the comments.

Twisted Oak Studios offers consulting and development on high-tech interactive projects. Check out our portfolio, or Give us a shout if you have anything you think some really rad engineers should help you with.

Non-Nullable Types vs C#: Fixing the Billion Dollar Mistake