How Never Works Internally in Swift

Uninhabited Types / Never Patterns

Expecting to find complex pieces of code, the implementation of Never in the Standard Library shows us something else - the type is nothing but an empty enum:

public enum Never {}

Although that certainly looks weird, it is correct in its theory. When Never got implemented, Swift also added the concept of uninhabited types to its lingo - a type with no value, often used to represent the nonexistent result of something that will never happen. Because an enum with no cases can't be instantiated in any way, it becomes perfect to represent this concept. But if the type itself doesn't do anything, where is the magic done?

A quick search for "never typecheck" in the Swift repo reveals a method called isNoReturnFunction(), which searches for the presence of an uninhabited type return:

bool SILFunctionType::isNoReturnFunction() const {
    for (unsigned i = 0, e = getNumResults(); i < e; ++i) {
        if (getResults()[i].getType()->isUninhabited())
            return true;
    }
    return false;
}

The implementation of the mentioned isUninhabited() itself just checks if we're dealing with an empty enum:

bool TypeBase::isUninhabited() {
    // Empty enum declarations are uninhabited
    if (auto nominalDecl = getAnyNominal())
        if (auto enumDecl = dyn_cast<EnumDecl>(nominalDecl))
            if (enumDecl->getAllElements().empty())
                return true;
    return false;
}

Because Never has no actual code, I expected the compiler to directly identify and change it somehow, but what this shows is that Never really is just an empty enum - the behavior we see has nothing to do with the type itself, but with the concept of an uninhabited type. This means that you don't need Never at all to ignore return statements:

enum Crash {}

func logAndCrash() -> Crash {
    print("Oops!")
    fatalError()
}

func doSomething() -> Int {
    logAndCrash() //Compiles!
}

In fact, because the compiler doesn't know the difference, my Crash type will even throw the same errors as Never:

func logAndCrash() -> Crash {
    //Function with uninhabited return type 'Crash'
    //is missing call to another never-returning function on all paths
}

For context, the very first commit of Never was indeed using the type itself to generate this behavior, but it was later changed to work with all uninhabited types due to multiple bugs that a Never-only solution was causing.

That's a great start, but I still have two major questions:

• First, where are these methods used?
• Second, if all never-returning methods need to return another never-returning method, don't we have an infinite recursion? Because the app is guaranteed to crash, someone down the line will have to not return something. Who makes this decision?

SIL generation of Never-returning methods

The first question can be answered by inspecting what Swift does to your code during the compilation process. To make it straightforward, the secrets of Never are hidden in a source file's SIL representation.

Swift Intermediate Language

In short, SIL is the middle-ground between your .swift files and the LLVM IR, basically acting as your Swift files translated to a "language" that contains high-level semantic information about what's happening behind the scenes. This allows the compiler to diagnose compilation errors and perform early optimizations while still allowing it to seamlessly generate the final LLVM IR necessary to let LLVM handle the rest of the compilation.

Inspecting the SIL version of a method that returns Never should reveal to us an optimized version of it, with hopefully an indicator of how the type works behind the scenes. I'm going to compile the following snippet - with an explicit return statement just to see how the SIL version reacts to it:

@inline(never) func crash() -> Never {
    fatalError()
}

func doSomething() -> Int {
    crash()
    let number = 1+1
    let otherNumber = number * 2
    return otherNumber
}

swiftc -emit-sil never.swift

After running the command above, the output will contain the following reference to doSomething():

// doSomething()
sil hidden @$S5never11doSomethingSiyF : $@convention(thin) () -> Int {
bb0:
  // function_ref crash()
  %0 = function_ref @$S5never5crashs5NeverOyF : $@convention(thin) () -> Never // user: %1
  %1 = apply %0() : $@convention(thin) () -> Never
  unreachable // id: %2
} // end sil function '$S5never11doSomethingSiyF'

SIL is not very easy to read, but it thankfully comes with a few comments that help us understand what's going on. The first thing we can notice here is the beauty of optimizations: all the unreachable number code I added there is completely gone!

Besides that, we can see that an unreachable statement was added right after the call to crash(). Normal methods would show a return statement, so this was clearly added by whatever logic handles Never.

A quick search into the Swift repo revealed that unreachable relates to UnreachableInst, a type that is injected and later used when the compiler needs to make decisions when it comes to code that will never succeed, or even be executed in this case.

TERMINATOR(UnreachableInst, unreachable,
           TermInst, None, DoesNotRelease)

However, this type is not exclusively used by Never, so more investigation is needed: After attaching lldb to the command used above and creating a breakpoint for UnreachableInst's init, a call inside simplifyBlocksWithCallsToNoReturn() is revealed: a method defined inside DiagnoseUnreachable.cpp, whose's backtrace revealed it to be one of the mandatory optimization passes before attempting to generate the final LLVM IR. (take a look at my CaseIterable article for details on how to manually use lldb!)

The actual method is quite large, so I've pseudo-coded it:

static bool simplifyBlocksWithCallsToNoReturn(SILBasicBlock &BB,
                                 UnreachableUserCodeReportingState *State) {
    if method_returns_never
        delete_everything_after_call
        inject_fake_unreachable_instruction
}

This does exactly what we've seen in the snippet, but still doesn't answer the first question! Why is this enough to stop requiring return values?

The answer is another mandatory optimization pass file named DataflowDiagnostics.cpp: the responsible for throwing unreachable-related compilation errors such as "missing return", "guard body missing return" and the "never method must call another never-method" from the previous examples.

One of the methods inside this file is called diagnoseMissingReturn(), which throws the "missing return" error: (note the call to isNoReturnFunction() to throw the different Never error!)

static void diagnoseMissingReturn(const UnreachableInst *UI,
                                  ASTContext &Context) {
    //Removed: Retrieving type data
    auto diagID = F->isNoReturnFunction() ? diag::missing_never_call
                                          : diag::missing_return;

    //"diagnose" throws the compilation error
    diagnose(Context,
             L.getEndSourceLoc(),
             diagID, ResTy,
             FLoc.isASTNode&ClosureExpr>() ? 1 : 0);
}

The decision to call diagnoseMissingReturn() is handled by diagnoseUnreachable(), which checks if the relevant UnreachableInst points to an actual position in the code (when you're really missing a return, so throw an error) or was injected by the compiler (like returning Never, so do nothing), which is exactly our case. Remember that the previous optimization removed everything after the Never call, so we only have the injected one at this point:

static void diagnoseUnreachable(const SILInstruction *I,
                                ASTContext &Context) {
  if (auto *UI = dyn_cast<UnreachableInst>(I)) {
    SILLocation L = UI->getLoc();

    // Invalid location means that the instruction has been generated by SIL
    // passes, such as DCE. FIXME: we might want to just introduce a separate
    // instruction kind, instead of keeping this invariant.
    //
    // We also do not want to emit diagnostics for code that was
    // transparently inlined. We should have already emitted these
    // diagnostics when we process the callee function prior to
    // inlining it.
    if (!L || L.is<MandatoryInlinedLocation>())
      return;

    // The most common case of getting an unreachable instruction is a
    // missing return statement. In this case, we know that the instruction
    // location will be the enclosing function.
    if (L.isASTNode<AbstractFunctionDecl>() || L.isASTNode<ClosureExpr>()) {
      diagnoseMissingReturn(UI, Context);
      return;
    }

    if (auto *Guard = L.getAsASTNode<GuardStmt>()) {
      diagnose(Context, Guard->getBody()->getEndLoc(),
               diag::guard_body_must_not_fallthrough);
      return;
    }
  }
}

In short, Never's behavior is defined in the optimization passes - after DiagnoseUnreachable.cpp detects and marks the instruction after a never call as unreachable, DataflowDiagnostics.cpp sees that this specific unreachable statement was injected by the compiler itself, avoids throwing a "missing return" compilation error, and lets the compilation continue.

Internals of fatalError()

Although the main functionality is now uncovered, something still bugs me; We've seen that creating a Never returning method will result in a compilation error if it doesn't call another Never method. Isn't this an infinite loop? Where is this loop broken?

To get the answer to that, we can inspect the contents of fatalError() and start going up its backtrace. Here's how fatalError() is defined:

public func fatalError(
  _ message: @autoclosure () -> String = String(),
  file: StaticString = #file, line: UInt = #line
) -> Never {
  _assertionFailure("Fatal error", message(), file: file, line: line,
    flags: _fatalErrorFlags())
}

This will compile correctly, since _assertionFailure also returns Never. Going up the backtrace, we'll see that it has the following implementation:

internal func _assertionFailure(
  _ prefix: StaticString, _ message: StaticString,
  file: StaticString, line: UInt,
  flags: UInt32
) -> Never {
  //Removed: Write to file
  Builtin.int_trap()
}

Now, Builtin.int_trap() also returns Never, so this too will compile correctly. Going up the backtrace, we'll see that int_trap() is defined as... uhhh....

Actually, there's no definition for this method! Builtin is not a normal framework - it seems to be generated inside the compiler as a way to allow Swift code to directly access LLVM functions. It appears to be all done in Builtins.cpp by parsing a table all the way from the swift-llvm repository and generating "pre-compiled" Swift methods from them. In this case, int_trap() is parsed as a Never returning method that calls llvm.trap(), a function that adds an instruction to blow up your app.

So how does the infinite loop stops? The answer seems to be that it simply does not. Because the final call of the chain is inside a "pre-compiled framework" in a sense, diagnostics do not seem to affect it, allowing the app to compile correctly.

Conclusion

Compilers are scary monsters, but knowing the internals of a language can really help you write efficient code. In this case, spelunking Never was interesting to see how each optimization pass complements each other when it comes to finding problems or changing the behaviour of a piece of code.

References and Good reads