A failed attempt at priority collection with inheritance by Mark Seemann

An instructive dead end.

This article is part of a short series on encapsulation and immutability. As the introductory article claims, object mutation makes it difficult to maintain invariants. In order to demonstrate the problem, I deliberately set out to do it wrong, and report on the result.

In subsequent articles in this series I will then show one way you can maintain the invariants in the face of mutation, as well as how much easier everything becomes if you choose an immutable design.

For now, however, I'll pretend to be naive and see how far I can get with that.

In the first article, I described the example problem in more details, but in short, the exercise is to develop a class that holds a collection of prioritized items, with the invariant that the priorities must always sum to 100. It should be impossible to leave the object in a state where that's not true. It's quite an illuminating exercise, so if you have the time, you should try it for yourself before reading on.

Initialization #

In object-oriented design it's common to inherit from a base class. Since I'll try to implement a collection of prioritized items, it seems natural to inherit from Collection<T>:

public sealed class PriorityCollection<T> : Collection<Prioritized<T>>

Of course, I also had to define Prioritized<T>:

public sealed class Prioritized<T>
{
    public Prioritized(T item, byte priority)
    {
        Item = item;
        Priority = priority;
    }
 
    public T Item { get; set; }
    public byte Priority { get; set; }
}

Since Prioritized<T> is generic, it can be used to prioritize any kind of object. In the tests I wrote, however, I exclusively used strings.

A priority is a number between 0 and 100, so I chose to represent that with a byte. Not that this strongly protects invariants, because values can still exceed 100, but on the other hand, there's no reason to use a 32-bit integer to model a number between 0 and 100.

Now that I write this text, I realize that I could have added a Guard Clause to the Prioritized<T> constructor to enforce that precondition, but as you can tell, I didn't think of doing that. This omission, however, doesn't change the conclusion, because the problems that we'll run into stems from another source.

In any case, just inheriting from Collection<Prioritized<T>> isn't enough to guarantee the invariant that the sum of priorities must be 100. An invariant must always hold, even for a newly initialized object. Thus, we need something like this ensure that this is the case:

public sealed class PriorityCollection<T> : Collection<Prioritized<T>>
{
    public PriorityCollection(params Prioritized<T>[] priorities)
        : base(priorities)
    {
        AssertSumIsOneHundred();
    }
 
    private void AssertSumIsOneHundred()
    {
        if (this.Sum(p => p.Priority) != 100)
            throw new InvalidOperationException(
                "The sum of all priorities must be 100.");
    }
}

So far, there's no real need to have a separate AssertSumIsOneHundred helper method; I could have kept that check in the constructor, and that would have been simpler. I did, however, anticipate that I'd need the helper method in other parts of the code base. As it turned out, I did, but not without having to change it.

Protecting overrides #

The Collection<T> base class offers normal collection methods like Add, Insert, Remove and so on. The default implementation allows client code to make arbitrary changes to the collection, including clearing it. The PriorityCollection<T> class can't allow that, because such edits could easily violate the invariants.

Collection<T> is explicitly designed to be a base class, so it offers various virtual methods that inheritors can override to change the behaviour. In this case, this is necessary.

As it turned out, I quickly realized that I had to change my assertion helper method to check the invariant in various cases:

private static void AssertSumIsOneHundred(IEnumerable<Prioritized<T>> priorities)
{
    if (priorities.Sum(p => p.Priority) != 100)
        throw new InvalidOperationException(
            "The sum of all priorities must be 100.");
}

By taking the sequence of priorities as an input argument, this enables me to simulate what would happen if I make a change to the actual collection, for example when adding an item to the collection:

protected override void InsertItem(int index, Prioritized<T> item)
{
    AssertSumIsOneHundred(this.Append(item));
    base.InsertItem(index, item);
}

By using Append, the InsertItem method creates a sequence of values that simulates what the collection would look like if we add the candidate item. The Append function returns a new collection, so this operation doesn't change the actual PriorityCollection<T>. This only happens if we get past the assertion and call InsertItem.

Likewise, I can protect the invariant in the other overrides:

protected override void RemoveItem(int index)
{
    var l = this.ToList();
    l.RemoveAt(index);
    AssertSumIsOneHundred(l);
    base.RemoveItem(index);
}
 
protected override void SetItem(int index, Prioritized<T> item)
{
    var l = this.ToList();
    l[index] = item;
    AssertSumIsOneHundred(l);
    base.SetItem(index, item);
}

I can even use it in the implementation of ClearItems, although that may seem a tad redundant:

protected override void ClearItems()
{
    AssertSumIsOneHundred([]);
}

I could also just have thrown an exception directly from this method, since it's never okay to clear the collection. This would violate the invariant, because the sum of an empty collection of priorities is zero.

As far as I recall, the entire API of Collection<T> is (transitively) based on those four virtual methods, so now that I've protected the invariant in all four, the PriorityCollection<T> class maintains the invariant, right?

Not yet. See if you can spot the problem.

There are, in fact, at least two remaining problems. One that we can recover from, and one that is insurmountable with this design. I'll get back to the serious problem later, but see if you can spot it already.

Leaf mutation #

In the introductory article I wrote:

"If the mutation happens on a leaf node in an object graph, the leaf may have to notify its parent, so that the parent can recheck the invariants."

I realize that this may sound abstract, but the current code presents a simple example. What happens if you change the Priority of an item after you've initialized the collection?

Consider the following example. For various reasons, I wrote the examples (that is, the unit tests) for this exercise in F#, but even if you're not an F# developer, you can probably understand what's going on. First, we create a Prioritized<string> object and use it to initialize a PriorityCollection<string> object named sut:

let item = Prioritized<string> ("foo", 40uy)
let sut = PriorityCollection<string> (item, Prioritized<string> ("bar", 60uy))

The item has a priority of 40 (the uy suffix is the F# way of stating that the literal is a byte), and the other unnamed value has a priority of 60, so all is good so far; the sum is 100.

Since, however, item is a mutable object, we can now change its Priority:

item.Priority <- 50uy

This changes item.Priority to 50, but since none of the four virtual base class methods of Collection<T> are involved, the sut never notices, the assertion never runs, and the object is now in an invalid state.

That's what I meant when I discussed mutations in leaf nodes. You can think of a collection as a rather flat and boring tree. The collection object itself is the root, and each of the items are leaves, and no further nesting is allowed.

When you edit a leaf, the root isn't automatically aware of such an event. You explicitly have to wire the object graph up so that this happens.

Event propagation #

One possible way to address this issue is to take advantage of .NET's event system. If you're reading along, but you normally write in another language, you can also use the Observer pattern, or even ReactiveX.

We need to have Prioritized<T> raise events, and one option is to let it implement INotifyPropertyChanging:

public sealed class Prioritized<T> : INotifyPropertyChanging

A Prioritized<T> object can now raise its PropertyChanging event before accepting an edit:

public byte Priority
{
    get => priority;
    set
    {
        if (PropertyChanging is { })
            PropertyChanging(
                this,
                new PriorityChangingEventArgs(value));
        priority = value;
    }
}

where PriorityChangingEventArgs is a little helper class that carries the proposed value around:

public class PriorityChangingEventArgs(byte proposal)
    : PropertyChangingEventArgs(nameof(Priority))
{
    public byte Proposal { get; } = proposal;
}

A PriorityCollection<T> object can now subscribe to that event on each of the values it keeps track of, so that it can protect the invariant against leaf node mutations.

private void Priority_PropertyChanging(object? sender, PropertyChangingEventArgs e)
{
    if (sender is Prioritized<T> p &&
        e is Prioritized<T>.PriorityChangingEventArgs pcea)
    {
        var l = this.ToList();
        l[l.IndexOf(p)] = new Prioritized<T>(p.Item, pcea.Proposal);
        AssertSumIsOneHundred(l);
    }
}

Such a solution comes with its own built-in complexity, because the PriorityCollection<T> class must be careful to subscribe to the PropertyChanging event in various different places. A new Prioritized<T> object may be added to the collection during initialization, or via the InsertItem or SetItem methods. Furthermore, the collection should make sure to unsubscribe from the event if an item is removed from the collection.

To be honest, I didn't bother to implement these extra checks, because the point is moot anyway.

Fatal flaw #

The design shown here comes with a fatal flaw. Can you tell what it is?

Since the invariant is that the priorities must always sum to exactly 100, it's impossible to add, remove, or change any items after initialization.

Or, rather, you can add new Prioritized<T> objects as long as their Priority is 0. Any other value breaks the invariant.

Likewise, the only item you can remove is one with a Priority of 0. Again, if you remove an item with any other Priority, you'd be violating the invariant.

A similar situation arises with editing an existing item. While you can change the Priority of an item, you can only 'change' it to the same value. So you can change 0 to 0, 42 to 42, or 100 to 100, but that's it.

But, I can hear you say, I'll only change 60 to 40 because I intend to add a new item with a 20 priority! In the end, the sum will be 100!

Yes, but this design doesn't know that, and you have no way of telling it.

While we may be able to rectify the situation, I consider this design so compromised that I think it better to start afresh with this realization. Thus, I'll abandon this version of PriorityCollection<T> in favour of a fresh start in the next article.

Conclusion #

While I've titled this article "A failed attempt", the actual purpose was to demonstrate how 'aggregate' requirements make it difficult to maintain class invariants.

I've seen many code bases with poor encapsulation. As far as I can tell, a major reason for that is that the usual 'small-scale' object-oriented design techniques like Guard Clauses fall short when an invariant involves the interplay of multiple objects. And in real business logic, that's the rule rather than the exception.

Not all is lost, however. In the next article, I'll develop an alternative object-oriented solution to the priority collection problem.

Next: A mutable priority collection.

---

Comments

• ← Previous
• Archive
• Next →