Author: Alan Malloy (amalloy@google.com)
Published: 2019-04-29
Feedback on Sealed Types
Sealed Types As a Vehicle For Sum Types
Bad sealed types found looking at instanceof checks
Plausible sealed types found looking at instanceof checks
Colocated interface implementations
Hello again, amber-spec-experts. I’m back with a second Google codebase research project. I’m looking again at the Records & Sealed Types proposal (which has now become JDK-8222777), but this time I’m focusing on sealed types instead of records, as promised in my RFC of a few weeks ago. My goal was to investigate Google’s codebase to guess what developers might have done differently if they had access to sealed types. This could help us understand what works in the current proposal and what to consider changing.
Unlike my previous report, this one contains more anecdotes than statistics. It wound up being difficult to build static analysis to categorize the interesting cases, so I mostly examined promising candidates by hand.
For those who don’t care to read through all my anecdotes, I first provide a summary of my findings, and one suggested addition.
Sealed types, as proposed so far, are a good idea in theory: Java already has product types and open polymorphism, and sealed types give us closed polymorphism. However, I could not find many cases of code being written today that would be greatly enhanced if sealed types were available. The main selling point of sealed types for application authors is getting help from the compiler with exhaustiveness checking, but in practice developers almost always have a default case, because they are only interested in a subset of the possible subclasses, and want to ignore cases they don’t understand. This means that exhaustiveness-checking for pattern matches would mostly go unused if developers rewrote their existing code using sealed types.
Pattern matching is great, and can replace visitors in many cases, but this does not depend on sealed types except for exhaustiveness checks (which, again, would go mostly unused in code written today). The class hierarchies for which people define visitors today are just too large to write an exhaustive pattern match, and so a default case would be very common.
The other audience for sealed types is library authors. While in practice most developers have no great need to forbid subclasses, perhaps it would be a boon for authors of particularly popular libraries, who need to expose a non-final class as an implementation detail but don’t intend for consumers to create their own subclasses. Those authors can already include documentation saying “you really should not extend this”, but there is always some weirdo out there who will ignore your warnings and then write an angry letter when the next version of your library breaks his program (see: sun.misc.Unsafe). Authors of such libraries would welcome the opportunity to make it truly impossible to create undesirable subclasses.
So, sealed types as-is would be an improvement, but a niche one, used by few. I think we can get substantially more mileage out of them if we also include a more cohesive way to explicitly define a sum type and all its subtypes in one place with minimal ceremony. Such a sum type could be sealed, implicitly or explicitly. A tool like this takes what I see as the “theoretical” advantage of sum types (closed polymorphism), and makes it “practical” by putting it front and center. Making sums an actual language element instead of something “implied” by sealing a type and putting its subclasses nearby could help in a lot of ways:
Since enum types are “degenerate sum types”, the syntax for defining sums can borrow heavily from enums. A sketch of the syntax I imagine for such things (of course, I am not married to it):
public type-enum interface BinaryTree<T> {
Leaf {
@Override public Stream<T> elements() {return Stream.empty();}
},
Node(T data, BinaryTree<T> left, BinaryTree<T> right) {
@Override public Stream<T> elements() {
return Stream.concat(left.elements(),
Stream.concat(Stream.of(data), right.elements()));
}
};
public Stream<T> elements();
}
Like enums, you can use a bare identifier for simple types that exist only to be pattern-matched against, but you can add fields and/or override blocks as necessary. The advantage over declaring a sealed type separately from its elements is both concision (the compiler infers visible records, superclass, and all type parameters) and clarity: you state your intention firmly. I think a convenient syntax like this will encourage developers to use the powerful tool of sealed types to model their data.
If you are just interested in recommendations, you can stop reading now: they are all included in the summary. What follows is a number of anecdotes, or case studies if you prefer, that led me to the conclusions above. Each shows a type that might have been written as a sealed type, and hopefully highlights a different facet of the question of how sealed types can be useful.
The first thing I looked for was classes which are often involved in instanceof checks. As language authors, we imagine people writing stuff like this[1] all the time:
interface Expr {int eval(Scope s);}
record Var(String name) implements Expr {
public int eval(Scope s) {return s.get(name);}
}
record Sum(Expr left, Expr right) implements Expr {
public int eval(Scope s) {return left.eval(s) + right.eval(s);}
}
class Analyzer {
Stream<String> variablesUsed(Expr e) {
if (e instanceof Var) return Stream.of(((Var)e).name);
if (e instanceof Sum) {
return variablesUsed(((Sum)e).left)
.concat(variablesUsed(((Sum)e).right));
}
throw new IllegalArgumentException();
}
}
Here, the Expr interface captures some of the functionality shared by all expressions, but later a client (Analyzer) came along and invented some other polymorphic operations to perform on an Expr, which Expr did not support. So Analyzer needed to do instanceof checks instead, externalizing the polymorphism. The principled approach would have been for Expr to export a visitor to begin with, but perhaps it wasn’t seen as worth the trouble at the time.
To try to find this pattern in the wild, I searched for method bodies which perform multiple instanceof checks against the same variable. Notably, this excludes the typical equals(Object) method, which only performs a single check. For each such variable, I noted:
I guessed that (3) would usually be the same as (1), but in practice 55% of the time they were different. Often, the declared type was Object, or some generic type variable which erases to Object, while the common supertype being tested was something like Number, Event, or Node. For example, a Container<T> knows it will be used in some context where NaN is unsuitable, so it checks whether its contents are Float or Double, and if so ensures NaN is not stored. As a second example, a serialize(Object) method checks whether its input is String or ByteString, and throws an exception otherwise.
I looked through the most popular declared types of these candidates, to investigate which types are often involved in such checks. Most of them are not good candidates for a sealed type. Object was the most common type, followed by Exception and Throwabe.
Next up is an internal DOMObject class, which sounds promising until I tell you it has thousands of direct subclasses. Nobody is doing exhaustive switches on this, of course. Instead, many uses iterate over a Collection<DOMObject>, or receive a DOMObject in some way, and just check whether it is of one or two specific subtypes they care about. This turned out to be a very common pattern, not just for DOMObject, but for many candidate sealed types I found: nobody does exhaustive case analysis. They just look for objects they understand in some much larger hierarchy, and ignore the rest.
Some more humorous types that are often involved in instanceof checks: java.net.InetAddress (everyone wants to know if it’s v4 or v6) and com.sun.source.tree.Tree, in our static-analysis tools. Tree is an interesting case: here we do exactly what I mentioned previously for DOMObject. On the surface it seems that Tree would be a good candidate for a sealed interface with record subtypes, but in practice I’m not sure what sealing would buy us. We would effectively opt out of exhaustiveness-checking by having a large default case, or by extending a visitor with default-empty methods. Of course, sometimes we define a new visitor to do some polymorphic operation over a Tree, but more often we just look for one or two subtypes we care about. For example, DataFlow inspects a Tree, but knows from context that it is either a LambdaExpressionTree, MethodTree, or an initializer.
The previous section notwithstanding, I did dig deep enough into the results to find a few classes that could make good sealed types. The most prominent, and most interesting, was another AST. There is an abstract Node class for representing HTML documents. It has just 4 subclasses defined in the same file: Text, Comment, Tag, and EndTag. This spartan definition suggests it’s used for something like SAX parsing, but I didn’t confirm this. It does everything you could hope for from a type like this: it exposes a Visitor, it provides an accept(Visitor) method, and the superclass specifies abstract methods for a couple of the most common things you would want to do, such as a String toHtml() method.
However, recall that I found this class by looking for classes often involved in instanceof checks! Some people use the visitor, but why doesn’t everyone? The first reason I found is one I’ve mentioned several times already: clients only care about one of the 4 cases, and may have felt creating an anonymous visitor is too much ceremony. Would they be happy with a switch and a default clause? Probably, but it’s hard to know for sure. The second reason surprised me a bit: I found clients doing analysis that isn’t really amenable to any one visitor, or a simple pattern-match. They’ve written this:
If (mode1) { if (x instanceof Tag) {...} }
else if (mode2) { if (x instanceof Text) {...}}
The same use site cares about different subclasses at different times, depending on some other flag(s) controlling its behavior. Even if we offered a pattern-match on x, it’s difficult to encode the flags correctly. They would have to match on a tuple of (mode1, mode2, x), with a case for (true, _, Tag name) and another for (false, true, Text text). Technically possible, but not really prettier than what they already have, especially since you would need to use a local record instead of an anonymous tuple.
Even so, I think this would have benefited from being a sealed type. Recall that earlier I carefully said “4 subclasses defined in the same file”. This is because some jokester in a different package altogether has defined their own fifth subclass, Doctype. They have their own sub-interface of Visitor that knows about Doctype nodes. I can’t help but feel that the authors of Node would have preferred to make this illegal, if they had been able to.
The second good sealed type I found is almost an enum, except that one of the instances has per-instance data. This is not exactly a surprise, since an enum is a degenerate sum type, and one way to think of sealed types is as a way to model sums. It looks something like this[2]:
public abstract class DbResult<T> {
public record NoDatabase<T>() extends DbResult<T>;
public record RowNotFound<T>() extends DbResult<T>;
// Four more error types ...
public record EmptySuccess<T>() extends DbResult<T>;
public record SuccessWithData<T>(T data) extends DbResult<T>;
public T getData() {
if (!(this instanceof SuccessWithData))
throw new DbException();
return ((SuccessWithData<T>)this).data;
}
public <U> DbResult<U> transform(Function<T, U> f) {
if (!(this instanceof SuccessWithData)) {
return (DbResult<U>)this;
}
return new SuccessWithData<U>(f.apply(
((SuccessWithData<T>)this).data));
}
Reading this code made me yearn for Haskell: here is someone who surely wanted to write
data DbResult t = NoDatabase | NoRow | EmptySuccess | Success t
but had to spend 120 lines defining their sum-of-products (the extra verbosity is because really they made the subclasses private, and defined private static singletons for each of the error types, with a static getter to get the type parameter right). This seems like a potential win for records and for sealed types. Certainly my snippet was much shorter than the actual source file because the proposed record syntax is quite concise, so that is a real win. But what do we really gain from sealing this type? Still nobody does exhaustive analysis even of this relatively small type: they just use functions like getData and transform to work with the result generically, or spot-check a couple interesting subtypes with instanceof. Forbidding subclassing from other packages hardly matters: nobody was subclassing it anyway, and nor would they be tempted to. Really the improvements DbResult benefits most from are records, and pattern-matching on records. It would be much nicer to replace the instanceof/cast pattern with a pattern-match that extracts the relevant field.
This is the use case that inspired my idea of a type-enum, in the Summary section above. Rewriting it as a type-enum eliminates many of the problems: all the instanceof checks are gone, we don’t need a bunch of extra keywords for each case, and we’re explicit about the subclasses “belonging to” the sealed parent, which means we get stuff like extends and <T> for free. We get improved clarity by letting the definition of the class hierarchy reflect its “nature” as a sum.
public abstract type-enum DbResult<T> {
NoDatabase,
RowNotFound,
EmptySuccess,
SuccessWithData(T data) {
@Override public T getData() {
return data;
}
@Override public <U> DbResult<U> transform(Function<T, U> f) {
return new SuccessWithData<U>(f.apply(data));
}
}
public T getData() {
throw new DbException();
}
public <U> DbResult<U> transform(Function<T, U> f) {
return (DbResult<U>)this;
}
}
Instead of doing a bunch of instanceof checks, the “sophisticated” way to interact with a class having a small, known set of subtypes is with a visitor. I considered doing some complicated analysis to characterize what makes a class a visitor, and trying to automatically cross-reference visitors to the classes they visit...but in practice simply looking for classes with “Visitor” in their name was a strong enough signal that a more complicated approach was not needed. Having identified visitors, I looked at those visitors with the most subclasses, since each distinct subclass corresponds to one “interaction” with the sealed type that it visits, and well-used visitors suggest both popularity and good design.
One common theme I found: developers aren’t good at applying the visitor pattern. Many cases I found had some weird and inexplicable quirk compared to the “standard” visitor. These developers will be relieved to get pattern-matching syntax so they can stop writing visitors.
The first popular visitor I found was a bit odd to me. It’s another tree type, but with a weird amalgam of several visitors, and an unusual approach to its double dispatch. I have to include a relatively lengthy code snippet to show all of its facets:
public static abstract class Node {
public interface Visitor {
boolean process(Node node);
}
public boolean visit(Object v) {
return v instanceof Visitor
&& ((Visitor)v).process(this);
}
// Other methods common to all Nodes ...
}
public static final class RootNode extends Node {
public interface Visitor {
boolean processRoot(RootNode node);
}
@Override
public boolean visit(Object v) {
return v instanceof Visitor
? ((Visitor)v).processRoot(this)
: super.visit(v);
}
// Other stuff about root nodes ...
}
public static abstract class ValueNode extends Node {
public interface Visitor {
boolean processValue(ValueNode node);
}
@Override
public boolean visit(Object v) {
return v instanceof Visitor
? ((Visitor)v).processValue(this)
: super.visit(v);
}
}
public static final class BooleanNode extends ValueNode {
public interface Visitor {
boolean processBool(BooleanNode node);
}
@Override
public boolean visit(Object v) {
return v instanceof Visitor
? ((Visitor)v).processBool(this)
: super.visit(v);
}
// Other stuff about booleans ...
}
public static final class StringNode extends ValueNode {
// Much the same as BooleanNode
}
This goes on for some time: there is a multi-layered hierarchy of dozens of node types, each with a boolean visit(Object) method, and their own distinct Visitor interface, in this file. I should note that this code is actually not written by a human, but rather generated by some process (I didn’t look into how). I still think it is worth mentioning here for two reasons: first, whoever wrote the code generator would probably do something similar if writing it by hand, and second because these visitors are used often by hand-written code.
Speaking of hand-written code, visitor subclasses now get to declare ahead of time exactly which kinds of nodes they care about, by implementing only the appropriate Visitor interfaces:
private class FooVisitor implements StringNode.Visitor,
BooleanNode.Visitor, RootNode.Visitor {
// ...
}
This isn’t how I would have written things, but I can sorta see the appeal, if you don’t have to write it all by hand: a visitor can choose to handle any one subclass of ValueNode, or all ValueNodes, or just RootNode and StringNode, et cetera. They get to pick and choose what sub-trees of the inheritance tree they work with.
Would Node be a good sealed class? Maybe. It clearly intends to enumerate all subclasses, but the benefit it gets from enforcing that is minimal. As in my previous examples, the main advantage for Node implementors would come from records, and the main advantage for clients would come from pattern-matching, obviating their need for this giant visitor.
Another AST, this time for some kind of query language, explicitly declares an enum of all subclasses it can have, and uses this enum instead of using traditional double-dispatch:
public interface Node {
enum Kind {EXPR, QUERY, IMPORT /* and 9 more */}
Kind getKind();
Location getLocation();
}
public abstract record AbstractNode(Location l) implements Node {}
public class Expr extends AbstractNode {
public Kind getKind() {return EXPR;}
// ...
}
// And so on for other Kinds ...
public abstract class Visitor {
// Empty default implementations, not abstract.
public Expr visitExpr(Expr e) {}
public Query visitQuery(Query q) {}
public Import visitImport(Import i) {}
public Node visit(Node n) {
switch (n.getKind()) {
case EXPR: return visitExpr((Expr)n);
case QUERY: return visitQuery((Query)n);
case IMPORT: return visitImport((Import)n);
// ...
}
}
}
It’s not really clear to me why they do it this way, instead of putting an accept(Visitor) method on Node. They gain the ability to return different types for each Node subtype, but are hugely restricted in what visitors can do: they must return a Node, instead of performing an arbitrary computation. It seems like the idea is visitors must specialize to tree rewriting, but I still would have preferred to parameterize the visitor by return type.
Would this be better as a sealed type? I feel sure that if sealed types existed, the authors of this class would have used one. We could certainly do away with the enum, and use an expression-switch instead to pattern-match in the implementation of visit(Node). But I think the Visitor class would still exist, and still have separate methods for each Node subtype, because they developer seemed to care about specializing the return type. The only place where an exhaustiveness check helps would be in the visit(Node) method, inside the visitor class itself. All other dispatch goes through visit(Node), or through one of the specialized visitor methods if the type is known statically. It seems like overall this would be an improvement, but again, the improvement comes primarily from pattern-matching, not sealing.
Finally, I looked for interfaces having all of their implementations defined in the same file. On this I do have some statistical data[3]. A huge majority (98.5%) of public interfaces have at least one implementation in a different source file. Package-private interfaces also tend to have implementations in other files: 85% of them are in this category. For protected interfaces it’s much closer: only 53% have external implementations. Of course, all private interfaces have all implementations in a single file.
Next, I looked at interfaces that share a source file with all their implementations, to see whether they’d make good sealed types. First was this Entry class:
public interface Entry {
enum Status {OK, PENDING, FAILED}
Status getStatus();
int size();
String render();
}
public class UserEntry implements Entry {
private User u;
private Status s;
public UserEntry(User u, Status s) {
this.u = u;
this.s = s;
}
@Override String render() {return u.name();}
@Override int size() {return 1;}
@Override Status getStatus() {return s;}
}
public class AccountEntry implements Entry {
private Account a;
private Status s;
public UserEntry(Account a, Status s) {
this.a = a;
this.s = s;
}
@Override String render() {return a.render();}
@Override int size() {return a.size();}
@Override Status getStatus() {return s;}
}
A huge majority of the clients of this Entry interface treat it polymorphically, just calling its interface methods. In only one case is there an instanceof check made on an Entry, dispatching to different methods depending on which subclass is present.
Is this a good sealed type? I think not, really. There are two implementations now, but perhaps there will be a GroupEntry someday. Existing clients should continue to work in that case: the polymorphic Entry interface provides everything clients are “intended” to know.
Another candidate for sealing:
public interface Request {/* Empty */}
public record RequestById(int id) implements Request;
public record RequestByValue(String owner, boolean historic) implements Request;
public class RequestFetcher {
public List<Item> fetch(Iterable<Request> requests) {
List<RequestById> idReqs = Lists.newArrayList();
List<RequestByValue> valueReqs = Lists.newArrayList();
List<Query> queries = Lists.newArrayList();
for (Request req : requests) {
if (req instanceof RequestById) {
idReqs.add((RequestById)req);
} else if (req instanceof RequestByValue) {
valueReqs.add((RequestByValue)req);
}
}
queries.addAll(prepareIdQueries(idReqs));
queries.addAll(prepareValueQueries(valueReqs));
return runQueries(queries);
}
}
Interestingly, since the Request interface is empty, the only way to do anything with this class is to cast it to one implementation type. In fact, the RequestFetcher I include here is the only usage of either of these classes (plus, of course, helpers like prepareIdQueries).
So, clients need to know about specific subclasses, and want to be sure they’re doing exhaustive pattern-matching. Seems like a great sealed class to me. Except...actually each of the two subclasses has been extended by a decorator adding a source[4]:
public record SourcedRequestById(Source source) extends RequestById;
public record SourcedRequestByValue(Source source) extends RequestByValue;
Does this argue in favor of sealing, or against? I don’t really know. The owners of Request clearly intended for all four of these subclasses to exist (they’re in the same package), so they could include them all in the permitted subtype list, but it seems like a confusing API to expose to clients.
A third candidate for sealing is another simple sum type:
public interface ValueOrAggregatorException<T> {
T get();
public static <T> ValueOrAggregatorException<T>
of(T value) {
return new OfValue<T>(value);
}
public static <T> ValueOrAggregatorException<T>
ofException(AggregatorException err) {
return new OfException<T>(err);
}
private record OfValue<T>(T value)
implements ValueOrAggregatorException<T> {
@Override T get() {return value;}
}
private record OfException<T>(AggregatorException err)
implements ValueOrAggregatorException<T> {
@Override T get() {throw err;}
}
}
It has only two subtypes, and it seems unimaginable there could ever be a third, so why not seal it? However, the subtypes are intentionally hidden: it is undesirable to let people see whether there’s an exception, except by having it thrown at you. In fact AggregatorException is documented as “plugins may throw this, but should never catch it”: there is some higher-level thing responsible for catching all such exceptions. So, this type gains no benefit from exhaustiveness checks in pattern-matching. The type is intended to be used polymorphically, through its interface method, even though its private implementation is amenable to sealing.
[1] Throughout this document I will use record syntax as if it were already in the language. This is merely for brevity, and to avoid making the reader spend a lot of time reading code that boils down to just storing a couple fields. In practice, of course the code in Google’s codebase either defines the records by hand, or uses an @AutoValue.
[2] Recall that @AutoValue, Google’s “record”, allows extending a class, which is semantically okay here: DbResult has no state, only behavior.
[3]This data is imperfect. While the Google codebase strongly discourages having more than one version of a module checked in, there is still some amount of “vendoring” or checking in multiple versions of some package, e.g. for supporting external clients of an old version of an API. As a result, two “different files” which are really copies of each other may implement interfaces with the same fully-qualified name; I did not attempt to control for this case, and so such cases may look like they were in the same file, or not.
[4] Of course in the record proposal it is illegal to extend records like this; in real life these plain data carriers are implemented by hand as ordinary classes, so the subtyping is legal,