Note: see the link below for the Vietnamese version of this article.

https://duongnt.com/nullable-value-tuple-vie/

A bug

Recently when refactoring a caching solution with MemoryCache, I encountered this bug. This was my original code with the sensitive parts omitted.

private readonly IMemoryCache _cache;

// Code to initialize _cache with MemoryCache

public async Task<MyObject> GetObjectByUuIdAsync(Guid parentUuid, Guid objectUuid)
{
    return await _cache.GetOrCreateAsync(
        objectUuid, async _ =>
        {
            await RefreshCacheByParentUuid(parentUuid);
            // code to retrieve and return MyObject from cache, or return null if still not found
        });
}

private async Task RefreshCacheByParentUuid(Guid parentUuid)
{
    // GetObjectUnderParent retrieves all objects which belong to the same parent.
    var objects = await GetObjectUnderParent(parentUuid);
    foreach (var object in objects)
    {
        // Store all objects belong to this parent into the cache in case we need them later.
        _cache.Set(object.Uuid, object);
    }
}

I changed it to.

public async Task<MyObject> GetObjectByUuIdAsync(Guid parentUuid, Guid objectUuid)
{
    var key = (objectUuid, "some other information I need"); // <-- NOTICE THIS
    return await _cache.GetOrCreateAsync(
        key, async _ =>
        {
            await RefreshCacheByParentUuid(parentUuid);
            // code to retrieve and return MyObject from cache, or return null if still not found
        });
}

private async Task RefreshCacheByParentUuid(Guid parentUuid)
{
    // GetObjectUnderParent retrieves all objects which belong to the same parent
    var objects = await GetObjectUnderParent(parentUuid);
    foreach (var object in objects)
    {
        // Store all objects belong to this parent into the cache in case we need them later.
        var key = (object.Uuid, "some information I need"); // <-- NOTICE THIS
        _cache.Set(key, object);
    }
}

After that, my unit tests started to fail (which reminded me that unit testing is a good thing, but this is a story for another day). The error messages for those tests all pointed to the same cause, for some reason I was getting cache miss when it should be cache hit.

Further investigation revealed that objectUuid passed into GetObjectByUuIdAsync is of type Guid but object.Uuid retrieved from GetObjectUnderParent is of type Guid?. Because in this use case object.Uuid is guaranteed to have a value, I was able to fix this bug relatively easily by changing just one line.

var key = (object.Uuid, "some information I need");
// to
var key = (object.Uuid.Value, "some information I need");

After fixing it, I try to find out why the bug only appeared after I started to use tuple as cache key, even though the mismatch was there from the start. And it is because of the way nullable, value tuple and MemoryCache works.

Inner working of MemoryCache

Under the hood, MemoryCache uses a ConcurrentDictionary to store data. Because we can pretty much use any type as key, MemoryCache uses ConcurrentDictionary<object, CacheEntry> (note that key is of type object). I also use an extension method called GetOrCreateAsync when checking the cache. This method will try to use the provided key to get the entry, and if that entry is not found it will call the provided delegate to create a new entry for that key. The code for GetOrCreateAsync is here.

public static async Task<TItem> GetOrCreateAsync<TItem>(this IMemoryCache cache, object key, Func<ICacheEntry, Task<TItem>> factory)
{
    if (!cache.TryGetValue(key, out object result))
    {
        var entry = cache.CreateEntry(key);
        result = await factory(entry);
        entry.SetValue(result);
        // need to manually call dispose instead of having a using
        // in case the factory passed in throws, in which case we
        // do not want to add the entry to the cache
        entry.Dispose();
    }

    return (TItem)result;
}

We can see that it calls TryGetValue on MemoryCache, and MemoryCache in turn calls TryGetValue on ConcurrentDictionary as can be seen here.

Now let’s look at the implementation of ConcurrentDictionary next, its TryGetValue method can be found here. Because the key is of type object which is a reference type and MemoryCache does not pass a comparer when initializing the dictionary, this code path will be entered.

for (Node? n = Volatile.Read(ref tables.GetBucket(hashcode)); n != null; n = n._next)
{
    if (hashcode == n._hashcode && _defaultComparer.Equals(n._key, key))
    {
        value = n._value;
        return true;
    }
}

The hash code of the key is checked, then _defaultComparer is used to compare keys. That comparer is below, where TKey is object.

_defaultComparer = EqualityComparer<TKey>.Default;

Objects and how to compare them

In an earlier part, we know that the keys of ConcurrentDictionary are compared with EqualityComparer<object>.Default. From the document of EqualityComparer<T>.

The Default property checks whether type T implements the System.IEquatable<T> interface and, if so, returns an EqualityComparer<T> that uses that implementation. Otherwise, it returns an EqualityComparer<T> that uses the overrides of Object.Equals and Object.GetHashCode provided by T.

The object class does not implement IEquatable<object>, that means we must resort to Object.Equals and Object.GetHashCode. Now, even though the key is of type object, we actually pass in a Guid or a tuple, and polymorphism kicks in. Let’s look at each scenario to see how the Equals and GetHashCode method is called.

Guid as key

What happens if we store an entry with a Nullable<Guid> key then try to use Guid to retrieve it? GetHashCode of Nullable<T> is very simple.

The hash code of the object returned by the Value property if the HasValue property is true, or zero if the HasValue property is false.

We can easily see that the hash code of a Nullable<Guid> equals the hash code of a Guid if the value of Nullable<Guid> equals that of Guid.

The same is also true for Equals method of Nullable<T>, true is returned if.

The HasValue property is false, and the other parameter is null (that is, two null values are equal by definition), OR the HasValue property is true, and the value returned by the Value property is equal to the other parameter.

We can then conclude that it is possible to retrieve an entry stored with a Nullable<Guid> key with a Guid key. This is why I didn’t encounter any bug with the original code.

Tuple as key

It’s trickier when a tuple is involved. This is the source code of ValueTuple (because our tuple has arity of 2, we only care about the struct ValueTuple<T1, T2>).

First let’s look at the source code of the GetHashCode method.

public override int GetHashCode()
{
    return HashCode.Combine(Item1?.GetHashCode() ?? 0,
                            Item2?.GetHashCode() ?? 0);
}

Now take a look at our key, we stored the entry with (Guid?, string) key and tried to retrieve it with (Guid, string). Since the string is the same, and we already know from Guid as key that in our case Guid and Guid? should return the same hash code, we can conclude that the hash code of (Guid?, string) and (Guid, string) are equal.

Move on to Equals method, this is the source code.

public override bool Equals([NotNullWhen(true)] object? obj)
{
    return obj is ValueTuple<T1, T2> tuple && Equals(tuple);
}

And this is the cause of our bug, the first check is translated to obj is ValueType<Guid?, string>, but actually the type is ValueType<Guid, string>. Because of that, Equals will return false, ConcurrentDictionary cannot find the entry and we get a cache miss.

When nullable is actually not null

We have finally found the culprit, but tuple still have some interesting tricks. Let’s look at the following code.

Guid id1 = Guid.NewGuid();
Guid? id2 = id1;

Console.WriteLine((id1, "Test").Equals((id1, "Test"))); // False
Console.WriteLine((id1, "Test") == (id2, "Test")); // True!!

Why comparison with == returns true when Equals returns false? It turns out that tuple equality with == or != was added recently in C# 7.3. The implementation roughly translated to this.

Allow expressions t1 == t2 where t1 and t2 are tuple or nullable tuple types of same cardinality, and evaluate them roughly as temp1.Item1 == temp2.Item1 && temp1.Item2 == temp2.Item2 (assuming var temp1 = t1; var temp2 = t2;). Conversely it would allow t1 != t2 and evaluate it as temp1.Item1 != temp2.Item1 || temp1.Item2 != temp2.Item2.

Clearly the 2 strings are equal, but how about Guid and Guid?? When id1 is Guid and id2 is Nullable<Guid>, we have Operator Lifting. More information can be found in the section Nullable Value Types – Operator Lifting of the book C#9.0 in a Nutshell by Joseph Albahari. It works basically like this.

• Nullable<T> struct does not define operators such as <, > or even ==.
• However, the compiler can borrow or lifts the == operator from the underlying value type. Semantically, it translates x == y into this.

  (x.HasValue && y.HasValue) ? (x.Value == y.Value);
  

Thanks to Operator Lifting, comparison of Guid and Guid? using == also returns true. All this results in the difference between comparison with == and comparison with Equals of tuple.

Conclusion

Since you have reached this part, I hope that this article was useful for you. If you have any suggestion please do let me know.