About Hierarchy Validation in Mixins

Do I have to remind you by now that mixins aren't classes? Hopefully not. However since from a purely mechanical standpoint mixins are compiled using javac just like ordinary java classes, there are certain things you need to be aware of when writing them, many of which I have already covered in previous sections.

One place where mixins get tricky to work with is when you have mixins being applied to multiple classes which form a class hierarchy. Inter-mixin operability can be a nuisance without helper interfaces allowing you to access mixin-provided fields and methods in superclasses.

As we saw in the earlier sections, in general a mixin is expected to extend either the direct superclass of its target class or a superclass within the the target class's hierarchy (up to and including java.lang.Object).

This section covers one of the more technical aspects of mixin implementation, that of validating that a mixin extends from a valid superclass.

Mixins and the parallel pseudo-hierarchy

For a typical class hierarchy, we can easily end up with a scenario which looks something like the following, with each mixin inheriting from its target's parent class:

We can easily see from this diagram that the mixins themselves form what appears at first glance to be a hierarchy which mirrors the hierarchy of their targets, however it is important to realise that the mixins themselves do not, in fact, form a hierarchy and are not directly related to one another in any way that transcends the purely conceptual.

One benefit of this scenario is that it is extremely easy to validate, we can easily check that a mixin's superclass is valid by simply looking for its superclass in the hierarchy of each target class.

Let's take a look at how we would validate MixinEntityPlayer. This mixin targets EntityPlayer and extends EntityLiving. To perform validation we simply walk up EntityPlayer's superclass hierarchy until we find (or don't find) EntityLiving.

We can express our naïve validation algorithm in a recursive fashion as follows:

1. If I am the superclass, stop and return true.
2. If I am Object, stop and return false.
3. Walk up to my superclass, then repeat from step 1 and return the result.

Visually, our validation process looks like this:

As we can see, validation for this scenario using this algorithm takes only two steps:

1. First we traverse to the mixin target class EntityPlayer
2. Next we walk up the hierarchy 1 position to EntityPlayer's superclass, at which point validation succeeds because the superclass was found.

However this efficiency comes at a price: because our mixins don't actually extend from one another, it is not immediately possible to access a field or method in a superclass which is added by a mixin.

For example, let's imagine that MixinEntityLiving adds a new protected field into its target class. Now because MixinEntityPlayer extends EntityLiving, in practice the field foo will be accessible from EntityPlayer, however mixins for EntityPlayer have no awareness of this new field and are thus unable to reference it at compile time:

Mixin "inheritance"

We can address this problem by allowing mixins to extend not just from classes in the target's hierarchy, but also from other mixins, this allows us to conceptually create a structure like this:

However whilst a structure like this is easy for a human being to design and understand, it is quite difficult for the mixin subsystem to verify, this is because an individual mixin has no way of knowing if it's (declared) superclass will eventually appear in the superclass hierarchy of its target.

It may be tempting to assume - looking at the diagram above - that validation is easy or even unnecessary, but since it's true that mixins can have multiple targets and multiple mixins can target a single class, validation gets very complicated very quickly when the hierarchy of mixins and targets is less straightforward:

Superclass validation is important because it's the only way to verify before application of a mixin that statically-bound invocations in the mixin are sane and will resolve correctly at application time, thus it is not safe to simply skip validation and hope for the best. However we need validation to be as efficient as possible because it must be run for every mixin at load time.

It's important to realise that every mixin has to be validated in the context of every one of its targets, since as already shown mixin targets may have wildly different hierarchies. This means it's not safe to assume that because one target's hierarchy can be sanely resolved that all other targets are sane, validation still has to take place for each target.

When we apply our naïve validation scheme from before, and simply look for the mixin's superclass in the hierarchy of the target, we run into a problem, validation fails:

Now we could solve this problem by walking up the mixin hierarchy, and for each super mixin, look for each of its targets in the superclass hierarchy of the mixin target in question. However this approach gets very expensive very quickly when dealing with multi-target mixins because for every supermixin target we have to search the superclass hierarchy of every target of the derived mixin to find a match. This could result in a lot of lookups for an ostensibly quite simple validation task.

The solution turns out to be quite simple: we simply separate mixin loading into two distinct passes. In the first pass we generate some additional metadata which can be used to fill the gaps in our knowledge of the hierarchy. In particular, we have each loaded mixin "tag" its target classes with a pointer to itself. This means that the target class now knows which mixins are targetting it:

With this new information available, we can perform validation in a second pass, knowing that our hierarchy information is complete, and modify our recursive algorithm to take advantage of the new data as follows:

1. If I am the superclass, stop and return true.
2. If I am Object, stop and return false.
3. Walk up to my superclass, then repeat from step 1 and note the result.
4. If the result of step 3 is false check each tagged mixin:

• If any mixins are the superclass we're looking for, return true
• If no mixins are the superclass we're looking for, return false

As you can see, validation is still a depth-first search. However we now have a secondary strategy to employ when the search fails, in that we check tagged mixins on our way back up the tree. This ultimately means that the complexity of our search is linear and only marginally more expensive than before, in as much as a full traversal of the target's superclass hierarchy is still required, but a maximum of one time per target, which is far more acceptable.