State of Valhalla

Section 2: Language Model

Brian Goetz, Feb 2020

This document describes the language model for incorporating inline types. Separate documents will describe the JVM model for inline types, and the translation strategy from Java source code to Java classfiles. (In this document, we use “currently” to describe the language as it stands today, without inline types.)

Where we are today

Types are currently divided into primitive and reference types. There are eight built-in primitive types (void is not a type); reference types are those that are not primitive types, which includes types declared as classes or interfaces, as well as non-declared types such as arrays types (String[], int[]) and parameterizations of reference types (List<String>, List<?>).

Reference and primitive types differ in almost every conceivable way. Reference types have members (methods and fields) and supertypes (superclasses and interfaces), and all (directly or indirectly) extend Object; primitive types have no members and are “islands” in the type system, with no supertypes or subtypes. To connect primitive types to reference types, each primitive type is associated with a wrapper type (Integer is the wrapper type for int). Wrapper types are reference types, and so can have members and can participate in subtyping. There are boxing and unboxing conversions between a primitive type and its corresponding wrapper type.

Types, current world
Types, current world

Value sets

Every type has a value set; this is the set of values that can be stored in a variable of that type. (For example, the value set of a primitive such as int is the set of 32 bit integers.) We write Vals(T) to describe the value set of type T. If type T is a subtype of type U, then Vals(T) ⊆ Vals(U).

An object is an instance of a class; currently, all objects have a unique object identity. The value set for a reference type consists not of objects, but of references to objects; the possible values of a variable of type String are not the String objects themselves, but references to those String objects. (It may come as a surprise to even experienced Java developers that it is not possible to store, manipulate, or access objects directly; we’re so used to dealing with object references that we don’t even notice the difference. Indeed, it is a common “gotcha” question about whether Java objects are passed by value or by reference, and the answer is “neither”: object references are passed by value.)

The value set of primitive types consists of primitive values (and never contains null); the value set of reference types consists of references to object instances, or null.

Both of the key facts in the previous paragraph – that all objects have a unique identity, and that the only way to manipulate objects is via their references – will change when we bring in inline types.

To highlight the values that we can store in variables in Java programs, the following diagram shows representable values as red boxes:

Values, current world
Values, current world

The universe of values in the current world consists of primitive values and references to objects.

To summarize the current world:

Inline classes

Having set the stage, we can now address how we will accommodate inline classes in the language type system. The motto for inline classes is: codes like a class, works like an int; the latter part of this motto means that inline types should align with the runtime behaviors of primitive types outlined so far. (Indeed, we would like to subsume primitive types under the umbrella of inline types; dividing our already bipartite type system into more categories would not be desirable.)

An inline class codes like a class, and so can have most of the things classes can have: fields, methods, constructors, superinterfaces, type variables, etc:

inline class Point {
    private int x;
    private int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int x() { return x; }
    public int y() { return y; }
}

The first big difference Valhalla brings is that instances of inline classes (call these inline objects) do not have identity; this means that certain identity-sensitive operations (e.g., synchronization) are not permitted on inline objects. To avoid confusion, we’ll refer to traditional classes as identity classes, and their instances as identity objects.

Instances of inline classes are objects, but do not have identity.

Object identity serves, among other things, to enable mutability and layout polymorphism; by giving up identity, inline classes must give up these things. Accordingly, inline classes are implicitly final, their fields are implicitly final, and there are restrictions on their supertypes (they can implement interfaces and extend some abstract classes.) Further, the representation of an inline class V may not contain, directly or indirectly, fields of type V. (Additionally, inline classes may not override the clone() or finalize() methods.)

Instead of dividing types into primitive and reference types, Valhalla divides them into inline and reference types – where inline types will subsume the primitives. The meaning of “reference type” remains anchored: reference types are those that are not inline types (this includes declared identity classes, declared interfaces, array types, etc.) We can update our types diagram to include inline types:

Types, Valhalla
Types, Valhalla

Value sets

Unlike identity classes, whose value set consists of references to object instances (or null), the value set of an inline class type is the set of possible instances of that class. (Like primitives, inline classes are non-nullable.) Inline objects are represented directly, as primitives are today; we can reflect this in our value set diagram:

Values, Valhalla
Values, Valhalla

Like primitives, the value set of an inline class is the set of instances of that class, not object references.

Every type has a default value. For primitive types, the default value is some sort of zero (0, 0.0, false, etc); for reference types, the default value is null. For inline classes, the default value is the instance of that type where all fields take on the default value for their type. For any class type C, the default value of C may be denoted as C.default. (In generic code, we may refer to T.default. For erased generics, T is always a reference type and therefore this evaluates to null; when generics are specialized, T.default will be specialized as well.)

New top interfaces

To distinguish between inline and identity classes at compile time and runtime, we introduce a pair of restricted interfaces: IdentityObject and InlineObject. Inline classes implicitly implement InlineObject; identity classes implicitly implement IdentityObject. (It is an error to attempt to implement both.) This enables us to write code that dynamically tests for object identity before performing identity-sensitive operations:

if (x instanceof IdentityObject)) {
    synchronized(x) { ... }
}

as well as statically reflecting the requirement for identity in variable types (and generic type bounds):

static void runWithLock(IdentityObject lock, Runnable r) {
    synchronized (lock) {
        r.run();
    }
}

Equality

In the current world, == is defined for each primitive type, and for reference types two values are == if they are both null or if they are references to the same object. And because currently all references are to objects with identity, we can use object identity to define “same object.”

We can extend == to inline objects by composition: two inline objects are == if they are of the same type, and each of their fields are pairwise equal according to == for the static type of that field (except for float and double, which compare according to the semantics of Float::equals and Double::equals). This definition says that two inline objects are equal if and only they are substitutable – we can discern no difference between them.

Arrays

For any class X (inline or identity) that implements interface I, the following subtyping relationship holds for arrays of X:

X[] <: I[] <: Object[]

Identity-sensitive operations

Certain operations are currently defined in terms of object identity. Some of these can be sensibly extended to cover all object instances; others will become partial. These include:

Inline and reference types

So far, we’ve constructed inline types to be very much like “programmable primitives”. But the biggest disadvantage of primitives has been the sharp divide – both statically and dynamically – between primitives and objects. The “programmable” part narrows the gap some, in that it allows inline types to have members and supertypes. But we would like to narrow this gap further.

In the current world, we convert from primitive to reference types via a boxing conversion. This is useful as it allows us to write more polymorphic code – any value can be represented by Object, either through subtyping or boxing. But, boxing has a number of serious downsides. The box types are bespoke, hand-crafted classes, with limited linguistic connection to the primitive types – this surely would not scale to inline classes. Worse, the resulting box has an “accidental” object identity, which interferes with many VM optimizations. The belief that “boxing is slow” derives in no small part from this accidental identity.

What we would like to do is connect the world of inline types to the world of reference types in a way that is less ad-hoc and lighter weight at runtime.

Boxing is dead, long live inline widening

The value set of an inline class consists of object instances, but the value set of an identity class consists of references to object instances. This difference in representation is one of the key sources of differences between primitives and objects in the current world.

We want to connect inline classes to the rest of the type system, where they can implement interfaces and extend Object. But suppose we have an interface I, an identity class C that implements I, and an inline class V that implements I – what is the value set of I? Clearly, we want it to include the value sets of both C and V – but these sets are structurally quite different – one contains objects, and the other contains references to objects. This is the object-primitive divide that needs to be bridged. The current world bridges this, clunkily, with boxing; we want to bridge it in a more uniform and lighter-weight manner.

Interfaces (and Object) are reference types, which means their value sets should consists of object references. Which brings us to the next big difference in Valhalla – that, while we can only manipulate identity objects via references, we can manipulate and store inline objects either directly or via object references.

The universe of values in Valhalla consists of primitive values, inline objects, and references to both identity and inline objects.

In Valhalla, we convert from inline to reference types via an inline widening conversion. This is similar to boxing, but it has a significant difference: the result of the conversion is not an identity object (as a box would be), but a reference to an inline object. (If you call Object::getClass on the resulting Object, it will report back the class of the original inline object, not a box type.) This gets us the interoperation we want between inline and reference types, without undermining the VM’s ability to optimize.

The inline widening conversion gives us the desirable semantics of boxing without most of the performance downsides of boxing.

It will be useful to define the operator ref v to be a reference to v when v is an inline object, and v itself if it is already an object reference. Then ref is total on all representable values, and always returns a reference. (The opposite operator, unref, is partial, and applies only on references to inline objects, and the two form a projection-embedding pair.)

The inline widening conversion exists from an inline type to any interface it implements and to Object, and is defined to be the application of the ref operator. This allows us to answer our question about the value set of I: it includes references to all the instances of C, and references to all the instances of V.

The value sets of interfaces (and of Object) consists of the value null, plus references to objects, which may be either identity or inline objects. Performing identity-sensitive operations on instances of interfaces or Object may fail at runtime.

Isn’t this just boxing with a fancy new name?

At this point, readers may be wondering whether we’ve merely played a trick of nomenclature, replacing the loaded term “boxing” with the not-yet loaded term “inline widening.” And if all we’d done is changed the name, it would indeed be a trick. The reason that inline widening is not just boxing renamed is that in the Valhalla JVM, inline widening and narrowing conversions are far lighter than the corresponding boxing and unboxing conversions. The problem with boxing is that it is as-hoc, and expensive; we seek to address both of these concerns.

Supertypes

Inline classes can implement interfaces. They cannot extend arbitrary classes, but they can extend a limited category of abstract classes – those with no fields, empty no-arg constructor bodies, no other constructors, no instance initializers, no synchronized methods, and whose superclasses all meet this same set of conditions (Object is an example of such a class.)

Reference and value projections

It is often useful to be able to describe the set of references to objects of a given inline class, plus null. Given an inline type V, we would like a reference type R whose value set is given by:


ValSet(R) = {null} ∪ {ref v : v ∈ ValSet(V)}

We call such a type R a reference projection of V. (A reference type is its own reference projection.)

A reference projection plays the role that a wrapper class plays in the current world. But, we don’t want every inline class to have a hand-written, ad-hoc wrapper; we would like to be able to mechanically derive a reference projection from an inline class, and have a uniform way to refer to it – that way we don’t have to maintain a mental dictionary mapping inline classes to their reference projections. For any type T, we would like for T.ref to denote the reference projection of T.

For inline classes, we automatically create both the reference and value projections. For an inline class V, V.ref is a type that describes the reference projection for V (the set of references to instances of V, plus null), V.val refers to the value projection for V (the set of instances of V), and (absent special pleading, see below) V is an alias for V.val. (The reference projection is a sealed abstract class that permits only V.val as a subtype.) So for an inline class V, we effectively get:

sealed abstract class V.ref permits V.val { }
inline class V.val extends V.ref { }

and we make V an alias for V.val. We automatically get an inline widening conversion from V.val to V.ref (and hence from V to V.ref). Additionally, we define an inline narrowing conversion from V.ref to V.val (and hence from V.ref to V) which applies the unref operator, throwing NullPointerException on null.

With this pair of conversions, inline classes have the same relationship with their reference projections as primitives historically did with their wrapper types. Existing rules that are defined in terms of boxing conversions (autoboxing, typing of conditionals, overload selection) can be trivially extended to incorporate inline widening and narrowing conversions too. The result is that existing user intuition about these conversions carries forward unchanged in the new world – but without the runtime costs of boxing, because inline widening does not create a new object with accidental identity as boxing currently does.

A reference type R already meets all the requirements to be its own reference projection, so for a reference type R, we make R.ref an alias for R itself. Now we’ve ensured that every type T has a reference projection that is denoted T.ref.

Class mirrors

An inline class V gives rise to two types (V.ref and V.val, plus the type alias V), and so it also gives rise to two class mirrors. However, since the reference projection is an abstract class, no instance will ever report that it is an instance of the reference projection – a non-null reference to a value of V will still report that it is an instance of V.val. (The class mirror for the reference projection serves the same purpose as the synthetic class mirrors for the primitive types – so that reflection can distinguish between the value and reference projections when used as field types or method parameters.)

Interfaces

Historically, for a class to implement an interface meant several things:

We need to refine this last bullet, subtyping, in a small way to support inline classes; we say that the reference projection of the class type is a subtype of the interface type. (Identity class types are their own reference projection, so this statement holds for all classes.) Similarly, if an inline class extends an abstract class, this means that the reference projection is a subtype of the abstract class.

Object

Because of its role as the root type for all classes, inline and identity, Object shares many characteristics with interfaces. As noted already, there is an inline widening conversion from all inline types to Object.

However, because Object is a concrete class, it is unfortunately possible to instantiate Object directly through its constructor. And because interfaces are inherited, Object can implement neither InlineObject nor IdentityObject – but the result of instantiating new Object() must be an instance of an identity type (since there is no point instantiating Object for any other reason.)

Wriggling out of this trap will require some fancy moves. We can start by creating a static factory Object::newIdentity that returns IdentityObject, and then attempt to migrate existing source and binary usages of new Object() towards this using various tools (compiler warnings, JIT magic) – and ultimately “deprecating” the Object constructor for direct instantiation (by making it protected).

Equality, again

We haven’t finished extending == for inline objects. We’ve defined it for the inline objects themselves, but not yet to reference types that may have references to inline objects in their value sets. We do this by saying that two object references are equal if they are both null, or are both references to the same identity object, or are both references to inline objects that are ==. This extends the substitutability semantics of == to all values – two values are == only if it is not possible to distinguish between them in any way – excepting the legacy behavior of NaN.

This gives us the following useful invariants about == (all modulo the legacy behavior of NaN):

The base implementation of Object::equals is to delegate to ==; for an inline class that does not explicitly override Object::equals, this is the default we want. (Similarly, the base implementation of Object::hashCode delegates to System::identityHashCode; this is also the default we want.)

Why reference projections?

The definitions given for reference projections make sense and comport with existing intuitions about the relationship with reference types, but we have not yet fully motivated why these types are so important.

There are several circumstances when we cannot use inline types, such as:

In all of these situations, we can use a reference type instead of an inline type. But, if we were to use a broad reference type such as Object, we lose a lot – we lose type safety, and clients then have to insert unchecked casts into their code to get back to the inline domain. By using the reference projection for an inline type, with its inline widening and narrowing conversions, we have a reference type whose value set is tightly tied to that of a specific inline class, which can be freely converted back to that inline class without the use of explicit conversions – which rescues the type safety and convenience we want.

As an example, consider the problem of migrating the Map interface to support specialized instantiation. The Map::get method returns null when the requested key is not present in the map, but if the V parameter of the Map is an inline type, null is not a member of the value set. We can capture this by declaring the get() method as follows:

public V.ref get(K key);

which captures the notion that the return type of Map::get will either be a reference to a V, or the null reference.

Migration

The techniques discussed so far suffice for new code, but there are several migration scenarios that we want to plan for.

Migrating value-based classes to inline classes

There are many existing value based classes, which meet a set of restrictions designed to enable a smooth migration to inline classes. One such example is java.util.Optional, which could have been declared an inline class if we had inline classes in Java 8. We would like to migrate Optional to be an inline class, to take advantage of the runtime benefits of inline classes. (The classes in the java.util.time package are in a similar situation.)

Existing clients are full of uses of the type Optional, including as variable types, method parameter or return types, and type parameters. All of these clients assume Optional to be a reference type, and reference types are nullable. So we cannot migrate Optional directly to be an inline type.

The next best thing would be to define Optional to be the reference projection of some inline class. This means we will migrate Optional to be an abstract class, and arrange for it to be sealed to permit exactly one inline class – the value projection Optional.val.

Following this migration, instances of Optional will be of an inline class rather than an identity class, but existing code will still store and pass Optional values via references. Where it really makes a difference that we represent them directly is where they meet the heap: fields and array elements. And here, we can freely and gradually migrate these specific uses of Optional to Optional.val. Because of the inline widening and narrowing conversions, changing a field or array from Optional to Optional.val is a source-compatible change.) Existing APIs would likely continue to use the reference projection Optional.

To accomplish this trick, we want to declare an inline class for Optional, yielding a reference projection Optional.ref and a value projection Optional.val, but we want to reverse the alias Optional to refer to the the reference projection instead of the value projection. We can accomplish this by modifying the declaration to say that it is ref-default inline class:

ref-default inline class Optional<T> {
    // current implementation of Optional
}

The only effect that the ref-default modifier has is to determine which of the two projections the unadorned type name refers to.

There is one possible incompatibility mode from such a migration – if the client compares the getClass() result with Optional.class. Pre-migration, an instance of Optional has class Optional.class; once Optional is migrated to an abstract class, instances of Optional will report that they are instances of the value projection Optional.val.

This incompatibility surrounding use of M.class is the major compatibility cost of the migration approach outlined here. This can be mitigated somewhat by issuing compiling warnings when comparing the getClass() result with == against the class literal for an interface or abstract class, since this will be known to fail at runtime.

Migration: primitives

We’ve cast inline types as an abstraction of primitives, but there is more work to do to ensure that we can actually subsume primitives into inline types.

We start by migrating the wrapper types Integer and friends to be sealed abstract classes, using the same techniques as with migrating Optional. These interfaces will become the reference projection for the primitives. To do this, we’ll first have to wean users off of dependence on identity of primitive wrappers. We can do this by deprecating for removal the public constructors (they would become private rather than actually removing them), and making instances of Integer “permanently locked” for some transition period (see JEP 169 for an approach here.)

This move risks breaking code that depends on the identity of primitive wrappers. Comparisons with == will likely not be problematic, given the substitutibility definition of ==, but code that locks on wrappers will fail at runtime.

We then can explicitly declare the primitive types as inline classes:

inline class int { /* implementation */ }

Obviously some fudging has to be done over self-reference, and some additional fudging to mate up the primitives with the names of their legacy wrappers, but we are now free to add superinterfaces and instance methods to int, and generally treat it like a class. The reference projection int.ref becomes an alias for Integer, and Integer.val becomes an alias for int, and the relationship between the two types is the same as for a migrated value-based class. If primitives are true inline types, then we also have the following subtyping relationship between arrays:

int[] <: Integer[] <: Object[]

We now have to reconcile the two sets of conversions defined between int and Integer; the existing boxing conversions, and the new inline narrowing and widening conversions. But conveniently, we’ve defined these to have the same semantics, with the exception of the accidental identity of the wrapper classes (which is being deprecated anyway.) Boxing becomes simpler for the runtime to routinely optimize away, while keeping all the existing rules surrounding conversion, overload selection, and inference. Similarly, because we can generalize the role of boxing in overload selection to use inline widening and narrowing instead, overload selection decisions will be unchanged under this migration.

Migration: specialized generics

Generics are currently erased to a single reference. We would like to eventually permit generics to specialize their representation, so that generic types like ArrayList<Point> can get the flattening and density benefits that Point[] gets. Doing so will take additional time, and brings with it an additional set of migration-compatibility issues – when ArrayList is migrated to be a specializable type, existing classfiles will still be full of erased references to ArrayList, and these have to continue to work.

We are trying to preserve room for specialized generics as a future feature. It seems likely that present-day erased generics will continue to work only on reference types. We wish to reserve a natural notation in the future for specialized types, such as List<int> or Optional<Point>. To do this, we require that in erased generics, only reference types are valid as type arguments. Today, people write List<Integer>; this generalizes to List<int.ref> and List<Point.ref>.

Summary

The approach we’ve taken is one of keeping the structure of the existing primitive-reference divide, but making it more regular and more performant. Boxing gets way cheaper and recedes farther into the shadows, “inline” is the new word for “primitive”, and the set of primitives is expandable. We’ve gone from “refs and primitives with heavy boxing” to “refs and inlines with lighter boxing”, but the two worlds remain largely isomorphic:

Current World Valhalla
references and primitives references and inlines (primitives are inlines)
primitives have boxes inlines have reference projections
boxes have identity, are visible as getClass() reference projection not visible at runtime
boxing and unboxing conversions inline narrowing and widening conversions, but same rules
primitives are built in and magic primitives are mostly just inline classes with extra VM support
primitives don’t have methods, supertypes primitives are inline classes, have methods & supers
primitive arrays are monomorphic inline arrays are polymorphic