Llogiq on stuff

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 of a and b equal?
  • In fn bar(a: &T) -> &T, is the type of a 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 of a and b 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.