Feedback on Sealed Types

[Alan Malloy]

Hello again, amber-spec-experts. I have another report from the Google
codebase, this time focusing on sealed types. It is viewable in full
Technicolor HTML at
http://cr.openjdk.java.net/~cushon/amalloy/sealed-types-report.html (thanks
again to Liam for hosting), and included below as plain text:

Author: Alan Malloy (amalloy at google.com)
Published: 2019-04-29

Feedback on Sealed Types

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.

Summary and Recommendations

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.

Sealed Types As a Vehicle For Sum Types

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:

* Developers might more often realize that a sealed/sum type is a good
model for their domain. Currently it’s a “pattern” external to the language
instead of a “feature”, and many don’t realize it could be applied to their
domain. Putting it in the language raises its profile, addressing the
problem that people don’t realize they want it.
* The compiler could provide help for defining simple sums-of-products,
while making it possible to opt into more complicated subclasses, in much
the way that enums do: the typical enum just has bare constants like EAST,
but you can add constructor arguments or override methods when necessary.
* The ability to more easily model data in this way may result in
developers writing more classes that are amenable to sealing/sums, as they
do in other languages with explicit sum types (Haskell, Kotlin, Scala).
Then, the exhaustiveness-checking feature that sealed types provide would
pull more weight.

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.

Evidence in Google’s Codebase

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:

1. Its declared type
2. The set of subtypes it was checked for with instanceof
3. The common supertype of those subtypes.

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.

Bad sealed types found looking at instanceof checks

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.

Plausible sealed types found looking at instanceof checks

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;
  }
}

Visitors

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 Visiting Object

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.

The Enumerated Node

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.

Colocated interface implementations

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.java.net/pipermail/amber-spec-experts/attachments/20190429/40ea9753/attachment-0001.html>