Bidirectional associations using value types in Swift

Just not possible

Trump chicken?

Bidirectional associations. Two way relationships between entities. E.g. a president and a country, a director and his movies, etc. It doesn’t matter if the relationship is one-to-one, one-to-many or many-to-many. It is not possible to fully represent them using value types. There will always be inconsistencies due to value type semantics.

I will try to explain why, using simple examples.

One-to-One

Let’s consider a scenario in which countries are managed by presidents.

//COMPILE ERROR: error: value type 'Country' cannot have a stored property that references itself

This example does not compile. It has nothing to do with the fact that presidents are incompetent or corrupt. The compiler is telling us that a a struct value type cannot have a stored property that references itself. You might ask yourself why?

To explain this, let’s make the example even simpler. Presidents cannot be friends with each-other. A struct cannot have a stored property that references a value of that same type. A President cannot hold a copy of another President value.

//COMPILE ERROR: error: value type 'President' cannot have a stored property that references itself

The reason for this compile error is memory allocation: Value types are fixed structures and they occupy a fixed space in memory, in registers and the stack, depending on its size. That space is pre-determined by the type and must be known at compile time.

So, the compiler needs to know how much space to reserve for a given struct value. But, how could that space be calculated if the value could contain another value of the same type, and that value could contain another one, and so on, and so on, and so on…(recursion)?

It is impossible to calculate the space needed, so the compiler simply says N0!

Before the next example, here is an interesting short article about different types of memory allocation in Swift.

One-to-Many

Movies are more entertaining than presidents, lets use movies and directors as an example case. Movies are directed by only one Director and a Director can direct many movies.

This compiles just fine. Why? Why don’t we have the same compile error we saw before?

The Movie has a Director. That is, the Director value is copied inside the Movie struct. The question is, what happens with the array of movies inside the Director? Don’t we end up with the same issue explained with the presidents example?

Collections have value type semantics in Swift. A swift Array appears as a struct on the outside. But on the inside, it is something else. This excellent post explains how Arrays might be implemented in Swift. Basically, it says that arrays are value types that inside use a reference to actual array objects. To achieve value semantics, each time the array struct needs to mutate (i.e. overwrite itself) the internal array reference is replaced by a new copy and the copy is mutated.

So, in our case, the Director struct needs space for its name and the array of movies. The array of movies (also a struct) needs space for the reference to the array object and other particulars of its implementation. This means the compiler can calculate the necessary space needed (name space + array space). There is no recursion as in the first example. The compiler can do the calculation. That is why the code compiles

Now, the code compiles, but is there anything wrong with it?

It lacks Consistency. We want a director to know its movies and each movie to know its director. Because values are immutable. It is impossible to assign a movie to a director, and then that same director to the same. movie.movie.director != director or director.movie != movie. To achieve consistency, we need the objects to mutate, but since they are values, they are immutable.

If you have a value type which contains another value type, this effectively just makes the value bigger. The inner value is part of the outer value. If you put the outer value into some new storage, it all gets copied, including the inner value. If you put the inner value into some new storage, it gets copied….from When to Use Swift Structs and Classes. mikeash.com

Think of structs as boxes. A struct holds a value of another struct, that means it has another box inside. It would be physically impossible to put box A inside box B and box B inside box A at the same time. We need to make a copy of the box we are inserting. But, when we make a copy of it, whatever happens in the future, it will happen to either the original or the copy, not both.

Consider this example. Spielberg directs E.T.

So, let’s set Spielberg as et’s director:

The cycle goes on and on… Each time you make a change, values are copied terminating all posibilites to have a consistent relationship graph.

Final words

Due to immutability, it is impossible to represent 2 way relationships using solely structs. Some times it is necessary to fall back on reference types, i.e. classes.

I leave you with a quote from the Swift Programming Manual:

….This means that most custom data constructs should be classes, not structures… Swift Programming Manual

Update: That line from Swift Programming Manual has been replaced by this one:

“The additional capabilities that classes support come at the cost of increased complexity. As a general guideline, prefer structures because they’re easier to reason about, and use classes when they’re appropriate or necessary. In practice, this means most of the custom data types you define will be structures and enumerations.”