libabigail
On-the-fly Canonicalization

This optimization is also known as "canonical type propagation".

This optimization is also known as "canonical type propagation".

During the canonicalization of a type T (which doesn't yet have a canonical type), T is compared structurally (member-wise) against a type C which already has a canonical type. The comparison expression is C == T.

During that structural comparison, if a subtype of C (which also already has a canonical type) is structurally compared to a subtype of T (which doesn't yet have a canonical type) and if they are equal, then we can deduce that the canonical type of the subtype of C is the canonical type of the subtype of C.

Thus, we can canonicalize the sub-type of the T, during the canonicalization of T itself. That canonicalization of the sub-type of T is what we call the "on-the-fly canonicalization". It's on the fly because it happens during a comparison – which itself happens during the canonicalization of T.

For now this on-the-fly canonicalization only happens when comparing class_decl and function_type.

Note however that there is a case when a type is *NOT* eligible to this canonical type propagation optimization.

The reason why a type is deemed NON-eligible to the canonical type propagation optimization is that it "depends" on recursively present type. Let me explain.

Suppose we have a type T that has sub-types named ST0 and ST1. Suppose ST1 itself has a sub-type that is T itself. In this case, we say that T is a recursive type, because it has T (itself) as one of its sub-types:

```   T
+-- ST0
|
+-- ST1
|    +
|    |
|    +-- T
|
+-- ST2
```

ST1 is said to "depend" on T because it has T as a sub-type. But because T is recursive, then ST1 is said to depend on a recursive type. Notice however that ST0 does not depend on any recursive type.

Now suppose we are comparing T to a type T' that has the same structure with sub-types ST0', ST1' and ST2'. During the comparison of ST1 against ST1', their sub-type T is compared against T'. Because T (resp. T') is a recursive type that is already being compared, the comparison of T against T' (as a subtypes of ST1 and ST1') returns true, meaning they are considered equal. This is done so that we don't enter an infinite recursion.

That means ST1 is also deemed equal to ST1'. If we are in the course of the canonicalization of T' and thus if T (as well as as all of its sub-types) is already canonicalized, then the canonical type propagation optimization will make us propagate the canonical type of ST1 onto ST1'. So the canonical type of ST1' will be equal to the canonical type of ST1 as a result of that optmization.

But then, later down the road, when ST2 is compared against ST2', let's suppose that we find out that they are different. Meaning that ST2 != ST2'. This means that T != T', i.e, the canonicalization of T' failed for now. But most importantly, it means that the propagation of the canonical type of ST1 to ST1' must now be invalidated. Meaning, ST1' must now be considered as not having any canonical type.

In other words, during type canonicalization, if ST1' depends on a recursive type T', its propagated canonical type must be invalidated (set to nullptr) if T' appears to be different from T, a.k.a, the canonicalization of T' temporarily failed.

This means that any sub-type that depends on recursive types and that has been the target of the canonical type propagation optimization must be tracked. If the dependant recursive type fails its canonicalization, then the sub-type being compared must have its propagated canonical type cleared. In other words, its propagated canonical type must be cancelled.