Truly Immutable Dictionary in .NET

Question

Good morning, afternoon or night,

Still building on my question about immutable dictionaries in .NET, I came up with the following question: while if then TKey and TValue are value types you can make a dictionary truly immutable, in the sense that neither its inner structure nor the values themselves can change, if those parameters are reference types keys and values can easily be changed, thus changing the dictionary itself. Am I right?

Thank you very much.

Answer 1

if then TKey and TValue are value types you can make a dictionary truly immutable, in the sense that neither its inner structure nor the values themselves can change, if those parameters are reference types keys and values can easily be changed, thus changing the dictionary itself. Am I right?

Not exactly. You've identified a real problem but your characterization of it is not fully thought through.

First off, I note that yes, a value type stuck in an immutable dictionary is immutable, even if it is a mutable value type. Why? Because value types are only mutated by mutating the variable which contains them. If your dictionary does not expose the variables it uses to store the value types then there is no way for those variables to be changed.

However, even if a value type is itself immutable an immutable value type can contain a reference to a mutable reference type, and now we've got the same problem. Restricting the dictionary to value types only pushes the problem off a level, it does not solve it! What you really need to guarantee "deep" immutability is a dictionary of blittable value types. By "blittable", I mean a value type with no fields of reference type. (So-called because you can serialize one of these to storage by "blitting" the bits straight out to disk.)

Unfortunately there is no constraint in the generic type system to constrain to blittable value types.

Let's now consider the general problem of mutable reference types in an immutable dictionary, whether those reference types are there directly or via a field of a value type. What can go wrong if a reference type is mutated out-of-band while it is in an immutable dictionary?

Well, the first thing that comes to mind is that an immutable dictionary should give the same answer twice to the same question twice, and now this is no longer the case. If you say "customers[name].Address" you'd expect to get the same answer twice, but if the customer is a reference type that can mutate, you'll get a potentially different answer. That might or might not be desirable. (And note that the dictionary is giving the same answer twice: it's giving the same reference to the customer object. It is actually the customer object that is not giving the same answer twice.)

Assuming you don't try to memoize answers to questions that can change, this is usually not a big problem.

A bigger problem is when an object that is in a hash table as a key mutates, thereby changing its hash value and "losing" the object in the table.

If that happens then someone is not keeping inside the guidelines. The guidelines are (1) reference types should if possible not base their hash codes (and equality) upon data that can mutate, and (2) an object being used as a key in a hash table should not be mutated.

Answer 2

Structs are value types and are not necessarily immutable - so the answer is no. You can design immutable types (make all fields and properties readonly). However there is no type constraint available (like where TKey : class) which would allow you to enforce it.

Update: An example:

class Bar { public int I; }
struct Foo { public Bar B; }

var b = new Bar();
var f = new Foo { B = b; }

dict[key] = f;
b.I++;

A bit constructed I admit.