Never Type in compiler

Development Compiler
21

Can you detail which tests are you talking about? So I can debug exactly the test and see if the Never and Error type are available.

22

We have tests in the test suite that use the Never and Error types for example. You’ll have to do a search to find them. Here’s one which uses Never: swift/associated_type_inference_fixed_type.swift at main · apple/swift · GitHub

23

Perhaps it's worthwhile to re-think the approach being taken? Instead of concretely storing a Never even when it is not written in the source code, canonicalize throws Never to "non-throwing" (if you saw a throws Never in the source, that means Never is likely already in scope or there's a type error). Parts of the pipeline that deal with canonical types do not have to worry about handling a Never value in throws position (maybe if not all of it, hopefully most of it).

This means you no longer need to materialize Never for function types synthesized when compiling tests that don't use the stdlib; they should just continue to work as if nothing changed.

24

The major issue is not reading a throws (Never) statement. The issue is reading for example a non-throwing function, which is virtually treated as a throws (Never). So we have serialized the Type ThrowsType. We have to set some value at any moment that a FuncType is instantiated.

25

What if you model the type as an optional, instead of storing Never if the type is missing?

26

None is not really well appreciated by the compiler when checking Types

27

Hmm, another option might be to just store a null type and clients can check for that after asking for the type. It’s not great though.

28

Any Type in the system is checked to be a non null pointer at some point in the process. We haven't found neither a way to represent that nor examples of similar behavior in expressions... Do you have something in mind?

29

Given the idea of “throws type” doesn’t already exist, I think it means that it would only be checked in places where you explicitly request for it (in your implementation). Maybe you can store a null type but the getThrowsType method can return an Optional<Type>.

30

That we use Never there, is an important part of the typed throws concept. Not only does it enable () -> () === () throws (Never) -> (), which could probably be modelled using an optional, but also

func foo<E>(_ bar: () throws (E) -> ()) throws (E) {
    try bar()
}

try foo { throw SomeError() } // E is SomeError

foo {} // E is Never, foo doesn’t throw
31

Right, but this is just about how it’s represented in the compiler. It would still be possible to do what you wrote (we’d just assume the lack of a type is the same as the type being Never).

I do think that setting it as Never would be better as it would simplify a lot of implementation code. If that’s not possible, then options such as using a bit (to mark whether a type was specified or not), an optional throws type or even a new ThrowsType type (optionally backed by the actual type) could serve as alternatives.

It might be good to first throughly investigate the feasibility of using Never before looking at other options. As I mentioned above, it should be possible to do so and if the standard library is not available, then just throw an error.

32

I think there are two slightly different things here. One is the choice of representation in FunctionTypeRepr. The other is the choice of representation in *FunctionType. I was (incorrectly) assuming the question was about *FunctionType; I realized this after looking at your PR. In any case, that is something that you'll probably need to handle right after you finish working on FunctionTypeRepr. I'm not super familiar with the *TypeRepr types, so I'm not going to comment on that. I've written my thoughts below on changes to *FunctionType.

(Disclaimer: I'm very much biased towards using (exhaustive) switch statements instead of if-else chains.)

Today, we don't store an extra reference to Error per throwing instance of *FunctionType, because it's understood that throwing functions today throw Error. We could follow the same pattern for Never.

00 -> non-throwing == throws Never, no extra storage
01 -> untyped throw == throws Error, no extra storage
10 -> typed throw == throws T, T != Never,
      where T is stored in *FunctionType's trailing storage
11 -> unused/illegal

Call-sites which use this can get a "view struct" out of a *FunctionType, like ThrowInfo or something, which reads off the bits and the trailing storage (if necessary) and creating a C++ equivalent of the following Swift enum:

// Swift
enum ThrowInfo {
  case nonThrowing
  case untypedThrow
  case typedThrow(SwiftType)
}

// C++
class ThrowInfo {
  enum class Kind : uint8_t {
    Nonthrowing,
    Untyped,
    Typed,
  };
  Kind kind;
  // invariant: thrownType is non-null iff kind == Kind::Typed
  Type thrownType;
}

Type ThrowInfo::getThrownType(); // assert if kind != Typed

struct ASTExtInfoBuilder {
  // throwing -> extended to 2 bits instead of 1
  unsigned bits;

  // clangTypeInfo elided...

  // new field, may potentially be null
  Type thrownType;
}

// Update methods
ASTExtInfoBuilder ASTExtInfoBuilder::withThrowInfo(ThrowInfo info);
ASTExtInfo ASTExtInfo::withThrowInfo(ThrowInfo info);

// materialize ThrowInfo on-demand from various types
ThrowInfo ASTExtInfoBuilder::getThrowInfo();
ThrowInfo ASTExtInfo::getThrowInfo();
ThrowInfo AnyFunctionType::getThrowInfo() { return getExtInfo().getThrowInfo(); }

Now clients can exhaustively switch on a ThrowInfo::Kind (because we have to roll our own ADTs in C++ :grimacing:) and possibly call getThrownType under case ThrowInfo::Kind::Typed.

If instead you just add an extra field of type swift::Type to AnyFunctionType's trailing storage, now clients need to use if-else chains to (a) check Never, then (b) check Error then (c) check the last case, I think that's a less ergonomic API. Also, you need to manually audit places call-sites of ASTExtInfo::isThrowing(); either removing that bit altogether to avoid two sources of truth going out of sync, or make sure that the bit on ASTExtInfo stays in sync with what you stored in the trailing storage.

Lastly, one problem I suspect you're going to encounter is that the thrown type will get dropped in places when new function types are creating by slightly tweaking existing types. (I'm saying this from painful experience working with this recently :sob:) By storing it always, I suspect that you'll probably have to do more plumbing to propagate the thrown type correctly. If you materialize it on-demand (and maybe even bundle it with ExtInfo as above), it might require more LoC overall but it the complexity would be largely contained within the *FunctionType/*ExtInfo/ThrowInfo types, with small updates to:

  • type-checking (to make sure you get the right subtyping relation)
  • call sites for ASTExtInfo::withThrows
  • whatever implements substitutions

(EDIT: Sorry, replied to the wrong comment. This was meant for @minuscorp )

3 Likes
33

This is a curious approach that we haven't thought of, will think about it. Mostly because it is starting almost from scratch (the only thing it can be preserved is all the parsing methodology we have now. It'd be from serialization to beyond.

Thank you very much!

34

There could be a problem with this approach. How and when do we check, if a generic throws type is Never and convert it to a Nonthrowing function?

What I mean is this:
when we have a function like

func foo<E>(_ bar: () throws (E) -> ()) throws (E) {
    try bar()
}

it would get the state ThrowInfo::Kind::Typed . When we call it later on we could supply a non-throwing function for bar, so that E is Never , which should mean, that foo is non-throwing too, but we already gave it the kind Typed.

The same also applies to the following case (although it is probably easier to solve):

func foo() throws (Never) {}

Again this function should be semantically the same as writing just

func foo() {}

but we somehow have to convert a function whose kind is ThrowInfo::Kind::Typed and whose type is Swift.Never to a function with the kind ThrowInfo::Kind::Nonthrowing.

35

when we have a function like

it would get the state ThrowInfo::Kind::Typed . When we call it later on we could supply a non-throwing function for bar , so that E is Never , which should mean, that foo is non-throwing too, but we already gave it the kind Typed .

That's why I included "whatever implements substitutions" in the list of things that would need to be updated. When you substituted the generic argument, the throw type needs to be adjusted anyways, regardless of whether the substitution is E := Never or E := Error or E := MyLibraryError or something else. The substitution logic needs to make sure that it doesn't set the configuration to Kind::Typed + storing a Never, possibly by using a constructor ThrowInfo(Kind k, Type t) which makes sure the invariant is upheld.

but we somehow have to convert a function whose kind is ThrowInfo::Kind::Typed and whose type is Swift.Never to a function with the kind ThrowInfo::Kind::Nonthrowing .

So there are two places where this could be done.

  1. When a FunctionType is created. The FunctionTypeRepr (which represents user-written code) can still continue to store the Never explicitly; my understanding (possibly incorrect) is that we consistently use *TypeReprs to present types in diagnostics, so this still avoids the problem of presenting something different than what the user wrote. This seems like the easier option to me and allows us to have a stronger invariant (no FunctionType's ThrowInfo has Kind::Typed and thrownType = Never).
  2. When a FunctionType is canonicalized. This would have a weaker invariant, namely that a non-canonical FunctionType can have Kind::Typed and thrownType = Never but that's not possible for canonical FunctionTypes (and at a later stage SILFunctionTypes because all SILFunctionTypes are canonical).
36

One more thing I forgot to add; if you do end up going this route, make sure to update the equality and hashing functions for *ExtInfo(Builder)? and *ExtInfo.

1 Like