Deciding if two types are equal
mutagen until recently suffered a bug that rendered both the return input and the interchange arguments mutation inapplicable.
To explain, the former mutation compares each input type with the return type and allows code to return inputs of the same type, if any, while the latter compares input arguments’ types and exchanges two equally-typed inputs.
Now the astute reader may get the impression that type equality is the root of the problem, and indeed, it is. This is how we used to check if two types are equal:
t1 == t2
Yay for expressing intent, nay for being wrong.
The reason is that syntax::ast::Ty
not only contains the actual type
information (if any), but also a unique NodeId
and the Span
which tells us
where in the code this type was written. And PartialEq
is just derived for
Ty
, which means those get compared, too. Oops.
(I should have known this, for I have implemented a very similar check for clippy about two years ago – how time flies)
Anyway, so we now check equality by walking the syntax tree of the type and comparing stuff along the way. But this leaves us with a number of interesting edge cases:
Quoth the Raven: “Never…more”
The ‘Never’ type (!
in Rust parlance) is always good for a surprise. Since it
represents a computation that will never return, it can be equal to anything.
So should !
be equal to Foo
? At the moment, the never type is used
sparingly in any real-world code, and equating it with itself seems a safe
bet. I’ll have to gain confidence that the compiler will actually allow us to
interchange those values before I’ll allow otherwise.
Array-, Inferred and Function Types
Arrays have one thing that no other type has: A length (which is actually
numeric). This length gets stored as an expression, which in theory can be just
about anything. To avoid having to build walkers for the whole AST (as we did
for clippy), we just extracted literal values and compared them. However in the
first version of the code our extracting function returned an Option<usize>
,
which is acceptable for this specific use case, but comparing two of them with
==
means that the following function would have its input and output equated.
const ONE: usize = 1;
const TWO: usize = 2;
fn foo([u8; ONE]) -> [u8; TWO] { .. }
Inferred types are not used in function interfaces, or else we’d have them here. Equating two distinct inferred types would likely lead to the wrong solution. Same with function types – in Rust, each function has its own type, so equating them could be problematic (function type pointers are a different thing, though, but for now we take the conservative view).
Lifetimes
At their heart, lifetimes are just identifiers that have an apostrophe
prepended. Comparing them for equality is literally just a.identifier ==
b.identifier
. However, one interesting edge case is when they aren’t there.
To explain the problem, I’ll give you two examples, each with a question about
the types:
- in
fn foo(a: &T, b: &T)
, are the types ofa
andb
equal? - In
fn bar(a: &T) -> &T
, is the type ofa
equal to the returned type?
If you answered “No” and “Yes”, respectively, good for you! You know Rust’s lifetime elision rules. Now let’s make it a bit harder:
- In
fn ouch(a: Foo, b: Foo)
, are the types ofa
andb
equal?
I’ll admit that this is something of a trick question. The answer is: It
depends. If Foo
is generic over a lifetime, elision rules state that the
types are not equal, otherwise they are equal. Since we must be careful not to
equate unequal things and cannot know if Foo
is indeed lifetime-less (we
could, if we annotated it to have mutagen see the code, but that’s for a future
version), we must answer “No” here (unless we know the type will never contain
a lifetime, e.g. u8
– a whitelist as with Default
would be useful).
This mey be surprising, but recall the first question above: Lifetime elision
assignes distinct lifetimes to multiple input arguments. So we could equally
write fn ouch(a: Foo<'a>, b: Foo<'b>)
, and that is of course not equal.
Actually my first version of my code to handle this made the mistake of equating all path types without lifetimes, no matter if the actual type had one or not or if it was eligible for equality by elision. So if you got it wrong, don’t fret, welcome to the club.