Entry 4: Derive Equatable & Hashable for Uninhabited Types

14 July 2018

After attempting a few failed improvements, I needed another win. I looked through a few tickets, but then I remembered a limitation of Swift that has bothered me: Swift won’t synthesize Equatable and Hashable implementations for uninhabited types.

An uninhabited type is one that can’t be initialized. Never, which is included in the standard library, is one such type:

public enum Never {}

A type like this can easily be made Equatable and Hashable:

extension Never: Equatable {
  public static func == (lhs: Never, rhs: Never) -> Bool {
    // This is actually valid Swift. No `case`s are needed because
    // every _possible_ value has been included.
    switch (lhs, rhs) {
    }
  }
}

extension Never: Hashable {
  public var hashValue: Int {
    switch (lhs, rhs) {
    }
  }
}

But Swift won’t do this for you, even though it’ll do it if you include one or more cases:

// Swift complains that you haven't implemented the required methods
enum NoCases: Hashable {
}

// But this is okay
enum OneCase: Hashable {
  case one
}

So I set out to fix this.

The first task was to find the code for synthesized implementations. I don’t remember how (it was a couple weeks ago due to some personal reasons), but I found this code in DerivedConformanceEquatableHashable.cpp:

/// Common preconditions for Equatable and Hashable.
static bool canDeriveConformance(TypeChecker &tc, DeclContext *DC,
                                 NominalTypeDecl *target,
                                 ProtocolDecl *protocol) {
  // The type must be an enum or a struct.
  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, DC, enumDecl, protocol);
  }

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

  return false;
}

This method was returning false for any enums that didn’t have any cases. It couldn’t be as easy as removing that check, could it? 🤔

No, it couldn’t. I got this strange warning after removing that check:

<unknown>:0: warning: will never be executed

But that was definitely the right first step.

Next, I hunted down the source of that warning. It was in the SIL (Swift Intermediate Language) generation, so it didn’t turn up anything useful.

So, instead, I backed up, set a breakpoint in the canDeriveConformance method that I mentioned above, and walked through the code. Just by stepping over, I ended up in resolveWitnessViaDerivation, which had this line:

// Attempt to derive the witness.
auto derived = TC.deriveProtocolRequirement(DC, derivingTypeDecl, requirement);

Stepping into that led me to the code where the Equatable implementation is derived:

ValueDecl *DerivedConformance::deriveEquatable(ValueDecl *requirement) {
  if (checkAndDiagnoseDisallowedContext(requirement))
    return nullptr;

  // Build the necessary decl.
  if (requirement->getBaseName() == "==") {
    if (auto ED = dyn_cast<EnumDecl>(Nominal)) {
      auto bodySynthesizer =
          ED->hasOnlyCasesWithoutAssociatedValues()
              ? &deriveBodyEquatable_enum_noAssociatedValues_eq
              : &deriveBodyEquatable_enum_hasAssociatedValues_eq;
      return deriveEquatable_eq(*this, TC.Context.Id_derived_enum_equals,
                                bodySynthesizer);
    } else if (isa<StructDecl>(Nominal))
      return deriveEquatable_eq(*this, TC.Context.Id_derived_struct_equals,
                                &deriveBodyEquatable_struct_eq);
    else
      llvm_unreachable("todo");
  }
  TC.diagnose(requirement->getLoc(), diag::broken_equatable_requirement);
  return nullptr;

This was what I was looking for. If the requirement is to add ==, then Swift looks to see if it’s an enum or a struct and synthesizes an appropriate implementation. Interestingly, the enum version has a check: the synthesized implementation is different depending on whether the enum has any associated values.

An enum without any cases has only cases without associated values, so that’s the implementation the compiler would be using.

/// Derive the body for an '==' operator for an enum that has no associated
/// values. This generates code that converts each value to its integer ordinal
/// and compares them, which produces an optimal single icmp instruction.
static void
deriveBodyEquatable_enum_noAssociatedValues_eq(AbstractFunctionDecl *eqDecl) {
  auto parentDC = eqDecl->getDeclContext();
  ASTContext &C = parentDC->getASTContext();

  auto args = eqDecl->getParameterLists().back();
  auto aParam = args->get(0);
  auto bParam = args->get(1);

  auto enumDecl = cast<EnumDecl>(aParam->getType()->getAnyNominal());

  // Generate the conversion from the enums to integer indices.
  SmallVector<ASTNode, 6> statements;
  DeclRefExpr *aIndex = convertEnumToIndex(statements, parentDC, enumDecl,
                                           aParam, eqDecl, "index_a");
  DeclRefExpr *bIndex = convertEnumToIndex(statements, parentDC, enumDecl,
                                           bParam, eqDecl, "index_b");

  // Generate the compare of the indices.
  FuncDecl *cmpFunc = C.getEqualIntDecl();
  assert(cmpFunc && "should have a == for int as we already checked for it");

  auto fnType = cmpFunc->getInterfaceType()->castTo<FunctionType>();

  // Leaving out some uninteresting code for brevity
  Expr *cmpFuncExpr = …

  TupleExpr *abTuple = TupleExpr::create(C, SourceLoc(), { aIndex, bIndex },
                                         { }, { }, SourceLoc(),
                                         /*HasTrailingClosure*/ false,
                                         /*Implicit*/ true);

  auto *cmpExpr = new (C) BinaryExpr(cmpFuncExpr, abTuple, /*implicit*/ true);
  statements.push_back(new (C) ReturnStmt(SourceLoc(), cmpExpr));

  BraceStmt *body = BraceStmt::create(C, SourceLoc(), statements, SourceLoc());
  eqDecl->setBody(body);
}

The included documentation comment describes it well. Swift is generating an AST for the code it’s synthesizing. This leads to the error we were seeing:

The compiler detects that some of the generated code will never be executed since the type is uninhabited
The source location is unknown because there isn’t one: it’s synthesized

The other case, where an enum does have associated values, looks similar but actually generates a switch:

// switch (a, b) { <case statements> }
auto aRef = new (C) DeclRefExpr(aParam, DeclNameLoc(), /*implicit*/true);
auto bRef = new (C) DeclRefExpr(bParam, DeclNameLoc(), /*implicit*/true);
auto abExpr = TupleExpr::create(C, SourceLoc(), { aRef, bRef }, {}, {},
                                SourceLoc(), /*HasTrailingClosure*/ false,
                                /*implicit*/ true);
auto switchStmt = SwitchStmt::create(LabeledStmtInfo(), SourceLoc(), abExpr,
                                     SourceLoc(), cases, SourceLoc(), C);
statements.push_back(switchStmt);

auto body = BraceStmt::create(C, SourceLoc(), statements, SourceLoc());
eqDecl->setBody(body);

Using these two versions, I was able to write a new version that works for uninhabited types. It takes advantage of the implementations I gave above: a switch can be empty of the enum has no cases. (I basically copied the associated values variant and neutered it.)

static void
deriveBodyEquatable_enum_uninhabited_eq(AbstractFunctionDecl *eqDecl) {
  auto parentDC = eqDecl->getDeclContext();
  ASTContext &C = parentDC->getASTContext();

  auto args = eqDecl->getParameterLists().back();
  auto aParam = args->get(0);
  auto bParam = args->get(1);

  assert(!cast<EnumDecl>(aParam->getType()->getAnyNominal())->hasCases());

  SmallVector<ASTNode, 1> statements;
  SmallVector<ASTNode, 0> cases;

  // switch (a, b) { }
  auto aRef = new (C) DeclRefExpr(aParam, DeclNameLoc(), /*implicit*/ true);
  auto bRef = new (C) DeclRefExpr(bParam, DeclNameLoc(), /*implicit*/ true);
  auto abExpr = TupleExpr::create(C, SourceLoc(), {aRef, bRef}, {}, {},
                                  SourceLoc(), /*HasTrailingClosure*/ false,
                                  /*implicit*/ true);
  auto switchStmt = SwitchStmt::create(LabeledStmtInfo(), SourceLoc(), abExpr,
                                       SourceLoc(), cases, SourceLoc(), C);
  statements.push_back(switchStmt);

  auto body = BraceStmt::create(C, SourceLoc(), statements, SourceLoc());
  eqDecl->setBody(body);
}

Now I had to tell the compiler to use this variant for enums with no cases. Luckily, I know that the EnumDecl had a hasCases() method from the check I removed above. So I just had to plug that in:

auto bodySynthesizer =
    !ed->hasCases()
        ? &deriveBodyEquatable_enum_uninhabited_eq
        : ed->hasOnlyCasesWithoutAssociatedValues()
              ? &deriveBodyEquatable_enum_noAssociatedValues_eq
              : &deriveBodyEquatable_enum_hasAssociatedValues_eq;
return deriveEquatable_eq(*this, TC.Context.Id_derived_enum_equals,
                          bodySynthesizer);

Compiling and running my test file showed that it worked!

From there, I just had to write a test. Luckily, I found an existing test that tested that an enum with no cases wouldn’t derive conformance. I inverted the expectations from that test and had completed my task!

You can see all of this in my PR.