Synthesized Conformance to Equatable

Investigating compiler magic for automatically synthesizing Equatable conformance.

31 July 2018 ∙ Swift Internals ∙ written by Greg Heo ∙ Swift 4.1

Equatable is a simple protocol that became even simpler to use in Swift 4.1 with automatically synthesized conformance. That means you don’t need to write the == function yourself in many cases, as it gets generated for you automatically.

How does the compiler determine whether to synthesize or not? What are the requirements? How does synthesis work, and what does the generated implementation look like?

Read on to get the answers to these questions!

For a refresher on the basics, check out the article on the Equatable protocol.

Synthesized SIL

Given this example struct:

struct Puppy: Equatable {
  let name: String
  let age: Int
}

Both property types conform to Equatable so there should be an == function generated automatically.

If you compile this with the -dump-ast or -emit-sil options, you’ll see an automatically-synthesized function with a name like derived_struct_equals for your type.

Here’s what a bit of the comparison SIL code looks like:

%15 = struct_extract %0 : $Puppy, #Puppy.age
%16 = struct_extract %1 : $Puppy, #Puppy.age
%17 = struct_extract %15 : $Int, #Int._value
%18 = struct_extract %16 : $Int, #Int._value
%19 = builtin "cmp_eq_Int64"(%17 : $Builtin.Int64, %18 : $Builtin.Int64) : $Builtin.Int1
%20 = struct $Bool (%19 : $Builtin.Int1)

The first two lines access the age property for the two Puppy instances to compare; the next two lines extract the age values, which are Int values in this case.

Next, we use a built-in function cmp_eq_Int64 to compare the two integers. The final line here creates a Bool with the result of the comparison, either true or false.

Curious to see the entire implementation? See the AST and SIL for the generated == function in full.

You can always implement the == function yourself and dump out the AST and SIL to compare; you should see very similar results.

Equatable Code Generation

So how and where is the code for == actually generated?

One way to do it might be for the compiler to generate Swift code and combine it with your own code. That’s basically what’s happening except since we’re already in the compiler and the compiler’s job is to generate lower-level stuff from Swift code, why not go right to that lower-level stuff?

During compilation your Swift code gets turned into a tree structure, with nodes for each little bit of syntax: braces, literals, function calls, etc. So the Equatable synthesis adds these nodes directly to the tree.

Tree structures in the compiler may not be particularly human-readable, and it’s C++ code to handle it all, but we’re brave and curious, right? 💪

Conformance Check

The first step to auto-synthesis is to determine whether it’s even possible.

Let’s have a look at the canDeriveConformance helper function:

static bool canDeriveConformance(TypeChecker &tc, NominalTypeDecl *target,
                                 ProtocolDecl *protocol) {

Given a type (target) and a protocol, the function returns a bool on whether we can derive conformance.

First up is enumerations:

if (auto enumDecl = dyn_cast<EnumDecl>(target)) {
  // The enum must have cases.
  if (!enumDecl->hasCases())
    return false;

  // The cases must not have associated values, or all associated values must
  // conform to the protocol.
  return allAssociatedValuesConformToProtocol(tc, enumDecl, protocol);
}

A dyn_cast is a dynamic cast, like when you use as? in Swift to see if an instance matches some type.

In this case, we’re checking if our given type target can be cast to EnumDecl; that is, is it an enumeration?

If so, there are two further checks:

1. The enumeration must have some cases^*
2. Each case must either have no associated values, or all associated values must conform to Equatable

Note that requirement 1 will be going away in the future, and “uninhabited” enums will get synthesized conformance.

If you’re curious, check out the allAssociatedValuesConformToProtocol helper function for more details.

Next up is structs:

if (auto structDecl = dyn_cast<StructDecl>(target)) {
  // All stored properties of the struct must conform to the protocol.
  return allStoredPropertiesConformToProtocol(tc, structDecl, protocol);
}

Again, we use a dynamic cast to check if we’re dealing with a struct type. If so, the well-named helper function allStoredPropertiesConformToProtocol checks whether all stored properties conform to Equatable.

Finally, one more thing:

return false;

In all other cases we return false, meaning no, we cannot conform to Equatable. That means only structs and enumerations that pass the above conditions can get synthesized conformance; it’s not at all possible for classes!

Why not for classes? Inheritance, basically. You can read all about it in the Swift Evolution proposal.

Here’s the grand summary of the conformance check:

Once we’ve determined conformance is possible, it’s time to make the implementation! 🛠

Implementation

If we peek ahead a bit, we’ll see that the generated == implementation would look something like this in Swift:

guard lhs.name == rhs.name else { return false }
guard lhs.age == rhs.age else { return false }
return true

I would write it as a single return statement but remember, this is a computer writing the code as a series of nodes. You get one guard per property, which probably leads to simpler code generation.

Let’s look at generating the guard statements in more detail next.

Guard Statements

Looking at the guard line again, we can think of it in three parts:

guard lhs.name == rhs.name else { return false }

1. The guard keyword itself
2. The condition
3. The else statement body

There’s a helper function returnIfNotEqualGuard that does the work of generating guard statements for == synthesis. Let’s have a look at how it works and build up our syntax nodes into a tree.

Statement Body

For the statement body, we want return false. That means we’ll need a false value and a return statement that returns it:

auto falseExpr = new (C) BooleanLiteralExpr(false, SourceLoc(), true);
auto returnStmt = new (C) ReturnStmt(SourceLoc(), falseExpr);

Although our else has a single statement here, there could be many more so it should be modeled as some kind of array of statements:

SmallVector<ASTNode, 1> statements;

statements.emplace_back(ASTNode(returnStmt));

Wait, we forgot the braces { and } surrounding the body statements!

auto body = BraceStmt::create(C, SourceLoc(), statements, SourceLoc());

That wraps up our statement body; we’ll see it again when constructing the full guard statement.

Condition

Next is the condition lhs == rhs. Although == uses infix notation you can still think of it like a regular function call, which means we can start by getting a reference to the == function:

auto cmpFuncExpr = new (C) UnresolvedDeclRefExpr(
  DeclName(C.getIdentifier("==")), DeclRefKind::BinaryOperator,
  DeclNameLoc());

And then we need the arguments, as a tuple:

auto cmpArgsTuple = TupleExpr::create(C, SourceLoc(),
                                      { lhsExpr, rhsExpr },
                                      { }, { }, SourceLoc(),
                                      /*HasTrailingClosure*/false,
                                      /*Implicit*/true);

The tuple contains our two arguments: the left- and right-hand side expressions surrounding the ==.

And finally, we can build the comparison expression from the function and its arguments:

auto cmpExpr = new (C) BinaryExpr(cmpFuncExpr, cmpArgsTuple, true);

Just as with the body, there could be multiple conditions although we have just one here. Still, we should put our single comparison expression into an array of conditions since that’s what guard is expecting:

SmallVector<StmtConditionElement, 1> conditions;

conditions.emplace_back(cmpExpr);

Guard

We built up the conditions and the else statement body; all that’s left is to tie them together into a guard statement!

return GuardStmt(SourceLoc(), C.AllocateCopy(conditions), body);

That’s the helper function to generate guard statements in tree form. Now you can imagine some kind of for loop: for each stored property in the struct, call the helper to generate a guard statement.

If we pass all the guard statements, the two instances must be equal. In that case, we need to return true. You’ve already seen code above on how to return false so use your imagination on what this might look like. 😉

Curious to see it all in action? See the full source for deriveBodyEquatable_struct_eq.

Synthesizing Equatable

That’s automatic Equatable synthesis for structs, built up with guard statements.

There’s a parallel code path for enumerations too that you can investigate if you’re curious. All the C++ code above is from DerivedConformanceEquatableHashable.cpp, where you’ll find lots of interesting code for both Equatable and Hashable.

If you want to trace the function calls all the way through for structs, it looks something like this:

You can browse through DerivedConformanceEquatableHashable.cpp and look for these names to help you along.

The Closing Brace

Not having to write == functions manually is a great convenience and time saver. But the curious part of me always wanted to know: how is it done?

I hope you have a better sense of how it works and what the implementation looks like, and have a bit more insight into syntax trees and everyone’s favorite language C++. 🤭

Equatable is a simple protocol but there’s a lot going on under the hood thanks to automatic conformance. There might be a lot of code needed in the compiler to synthesize conformance, but it saves us from having to write code in our applications: that’s my favorite kind of compiler feature. 👍

}