Exploring inference for sealed types

[Gavin Bierman]

Dear experts:

We have been discussing some tweaks to the sealed types design. I thought it
would be useful to elucidate the ideas, and also to explain some of the
wrinkles. As always, we're interested to hear any thoughts you may have.

As Brian mentioned in an earlier email, sealed types address two related, but
distinct, issues: (1) declaring a sum type, whereby the compiler can exploit
exhaustiveness in various places (e.g. in a switch); and (2) defining a type
that for clients behaves as if it is final (it cannot be extended), but for
the class author actually has a fixed, known collection of implementations. 

The second use dictates a subtle design constraint: a type that directly
extends/implements a `sealed` type must be either `sealed`, `final` or
`non-sealed`. If not, it will be too easy to create a security hole where the
class author intended a class hierarchy to be closed, but by forgetting a
modifier at a leaf type, inadvertently renders the hierarchy open. 

One valid design point is to stop here. All `sealed`/`non-sealed`/`final`
modifiers and `permits` clauses have to be given explicitly. The compiler then
just checks that what has been declared is correct.

We have been exploring some alternative design points, all supporting some
sort of inference. The idea is that if all the type declarations are in the
same compilation unit (this is important, we don't infer anything outside a
compilation unit) then we might like to spare users writing all the `sealed`
modifiers and `permits` clauses. More concretely, if we write:

```
sealed class B 
class C extends B
class D extends C
class E extends D
// EOF
```

(in other words, we just declared the root class to be sealed) then the compiler
infers: 

```
sealed class B permits C
sealed class C extends B permits D
sealed class D extends C permits E
final class E extends D
// EOF
```

We want a cascading inference behavior: If you put `sealed` at the top of a
hierarchy that resides in the same compilation unit, then the compiler works
its way down the hierarchy inferring `sealed` until we get to leaf classes
where we infer `final`. Perfect! (At the bottom of this email, I include a
draft spec that covers this inference process.)

But there are wrinkles with this design. 

1. Obviously we will rule out the explicit declaration of an empty `permits`
clause, but what if we _infer_ one? To be concrete where we have the 
compilation unit:

```
sealed class Foo { } 
//EOF
```

What's the right thing here? Is this an compile-time error? A `sealed` class
with an empty `permits` clause is morally `final`, so should we infer the
class to be `final`? Or do we need to keep the two - `final` and
`sealed`-with-empty-`permits`) and make sure we treat them identically?

2. Consider the following:

```
class Outer {
    sealed class SuperSealed {}

    sealed interface SealedI {}

    class SubFinal1 extends SuperSealed {}

    class SubFinal2 implements SealedI {}

    non-sealed SubNonSealed extends SuperSealed implements SealedI {}

    class WhatAboutMe extends SubNonSealed implements SealedI {}
}
```

The issue is around class WhatAboutMe. It redundantly implements SealedI. But
with the cascading behavior this is significant. *With* the `implements` clause
we infer that WhatAboutMe should be `final`. *Without* it we would not. 

As is common with other inference systems, our inference may not be invariant
under semantically equivalent declarations. Is that going to be too
confusing for users?

3. This cascading inference puts strain on the compiler. It works by analyzing
which types extend/implement the `sealed` type in question. Whilst such
hierarchies are probably going to be small, one could imagine people
exploiting this inference feature and building extensive and complicated
sealed hierarchies within a single compilation unit. Do we want to commit
compilers to navigating these graphs? Would we be encouraging people to defining
auxiliary classes when we have been recommending *not* to do so?


Thoughts welcome!
Gavin

SPEC DETAILS
------------

To deal with modifiers; first for classes:

---

If a class _C_ extends a `sealed` class ([8.1.4]) that is declared in the same
compilation unit ([7.3]), or implements a `sealed` interface ([9.1.1.3]) that
is declared in the same compilation unit, one of the following applies:

- The class is explicitly declared `final` or `sealed`.

- The class is explicitly declared `non-sealed`, meaning that there are no
restrictions on the subclasses of _C_.

- The class is not declared `final`, `sealed`, nor `non-sealed`. In this case,
if _C_ is the direct superclass ([8.1.4]) of another class declared in the
same compilation unit, then class _C_ is implicitly declared `sealed`;
otherwise class _C_ is implicitly declared `final`.

Otherwise, if a class _C_ extends a `sealed` class or implements a `sealed`
interface, one of the following applies:

- The class is explicitly declared `final` or `sealed`.

- The class is explicitly declared `non-sealed`, meaning that there are no
restrictions on the subclasses of _C_.

- The class is not declared `final`, `sealed`, nor `non-sealed`, and a
compile-time error occurs.

---

And for interfaces:

---

If an interface _I_ extends a `sealed` interface ([9.1.3]) that is declared in
the same compilation unit ([7.3]), one of the following applies:

- The interface _I_ is explicitly declared `sealed`.

- The interface _I_ is explicitly declared `non-sealed`, meaning that there are
no restrictions on the subtypes of _I_.

- The interface _I_ is not declared `sealed` or `non-sealed`. In this case, if
_I_ is the superinterface ([8.1.5], [9.1.3]) of another class or interface 
declared in the same compilation unit, then interface _I_ is implicitly
declared `sealed`; otherwise a compile-time error occurs. 

---

To deal with `permits` clauses; first for classes:

---

A `sealed` class _C_ without an explicitly declared `permits`
clause, has an implicitly declared `permits` clause that lists as permitted
subclasses all the classes in the same compilation unit ([7.3]) as _C_ that
declare _C_ as their direct superclass.

---

and for interfaces:

---

If a `sealed` interface _I_ does not have an explicit `permits` clause, then
it has an implicitly declared `permits` clause that lists as permitted
subtypes all the classes and interfaces in the same compilation unit ([7.3])
as _I_ that declare _I_ as their direct superinterface.

---