Compile-Time Ephemerons

[goderbauer]

It would be cool if Dart supports compile-time Ephemerons (also known as "Weak Properties"). Among other things, this would enable Flutter to restore the state of anonymous Routes during State Restoration (see http://flutter.dev/go/restoring-anonymous-routes for details of that use case).

Functionality

A compile-time ephemeron is a const object that stores a key and a value. It can be instantiated from code only via a const constructor that takes the key and the value as arguments. The ephemeron gets special treatment from the compiler: If the key of a given ephemeron is not reachable from the app (outside of the instantiation of the ephemeron itself), the compiler may null out the key and value field of the given ephemeron. Otherwise, the key and value are left as-is.
When the key and value fields are nulled out, the tree-shaker can potentially eliminate more stuff from the final binary.
Essentially, the ephemeron keeps a weak reference to its key and only keeps its value around if the associated key is reachable from other places in the app. This will allow library authors to create dynamic invocations of methods only if they are retained by the tree shaker.

Interface

/**
 * Instances of this class are ephemerons, also known as weak properties, that
 * participate in determining which const objects will be retained at compile time.
 *
 * A const object is compile-time reachable if it is used in some function
 * transitively callable from main, or as the field of some other compile-time
 * reachable const object.
 *
 * If the key of a CompileTimeEphemeron is compile-time reachable, then its value
 * is compile-time reachable. If the key is not compile-time reachable, the key and
 * value are both replaced with null.
 *
 * All CompileTimeEphemerons created with any compile-time unreachable key are equal.
 * (That is, canonicalization happens after reachability is determined.)
 *
 * This extends the concept of weak reachability from runtime garbage collection to
 * compile-time tree-shaking. Ephemerons were first described in
 * https://doi.org/10.1145/263698.263733
 *
 * Note that a weak reference is a special case of an ephemeron where the value is
 * not used. In this case, we recommend setting the value to null.
 */
class CompileTimeEphemeron<K, V> {
  final K? key;
  final V? value;

  /**
   * This constructor must be invoked via `const`; it is a compile-time error to invoke
   * this constructor via `new`.
   *
   * (Because it is not currently possible to implement a runtime ephemeron in JavaScript.)
   */
  const CompileTimeEphemeron(this.key, this.value);
}

Implementation

The dart:core library would expose a CompileTimeEphemeron class that can only be instantiated via a const constructor. The const constructor takes a key and a value of any type and instances of the class have fields to retrieve both values again.

Tree-shaking compilers typically have a work queue of functions to be compiled. This queue starts with ‘main’ (and other entry points) inserted. The compiler takes a function from the work queue, compiles it, then inserts all functions that could be called from it; and repeats until the queue is empty. Any function that remains uncompiled is dead code and removed. To implement CompileTimeEphemerons, a few changes are made to this loop. When a CompileTimeEphemeron is encountered, it is added to a list of pending ephemerons, instead of being visited immediately like other const objects. After the work queue is drained, each CompileTimeEphemeron in the pending list is examined. If its key is compile-time reachable, then its value is visited and the ephemeron is removed from the pending ephemerons list. Visiting the value can insert into the work queue. After the whole list has been examined, the compiler again drains the work queue and revisits the ephemeron list. This repeats until visiting the ephermon list does not add to the work queue. Then all remaining ephemerons on the pending list have their keys and values set to null.

Use Case

State Serialisation and Deserialisation in Flutter: In order to deserialize a class from serialized data, we need to maintain a Map with serializable class ids as keys and deserialisation functions as values. However, when a certain class is unused in the app and tree-shaken out, we do not want to retain the deserialisation function (see "Restoring anonymous Routes" for details of this use case and how ephemerons can be used to solve it).

Further Reading

• Wikipedia article on Ephemerons
• The original paper by Barry Hayes introducing the concept of ephemerons: Ephemerons: a new finalization mechanism

Related Issues

• Link time sets and maps (Link time sets and maps language#371): Flutter's use-case could also be solved with a link-time map and the condition contributing functionality described in the linked proposal.

Special thanks to @dnfield and @rmacnak-google for their help in creating this proposal.

[goderbauer]

/cc @leafpetersen @Hixie @a-siva

[dnfield]

@lrhn @eernstg as well

[goderbauer]

Closing here since it got moved to dart-lang/language#895.