[Inline Classes] Phantom Type support?

[modulovalue]

This issue is a question about whether the Inline Classes proposal is able to support Phantom Type use cases.

I will first introduce the idea of Phantom Types in the context of Dart and provide a small motivating example for them.

Phantom Types

Consider the following:

abstract class Foo<T> {}

The type parameter T is unused. I will refer to type parameters that are not used anywhere inside of the body of the associated declaration as Phantom Types.

State model

Consider the following interface hierarchy:

abstract class Listcontent {}

abstract class Empty implements Listcontent {}

abstract class Nonempty implements Listcontent {}

abstract class One implements Nonempty {}

abstract class Many implements Nonempty {}

This models the state of the contents of a List i.e. a list can be empty, it can have one element or many. If it has one or many elements, it is considered to be nonempty.

I will use of the Listcontent hierarchy below.

Proving and carrying around facts about the contents of a List

Here is an example of proving, encoding and carrying around a proof that a list is not empty using Phantom Types and the hierarchy from above. (Note: This is a simplified example that is meant to present the key idea and does not represent a safe implementation.)

/// A wrapper for Dart Lists that is able to carry a Phantom Type P.
class List2<T, P> {
  final List<T> list;

  const List2(this.list);
}

/// A function that maps a list to either Null or to a
/// list that is annotated to be not empty.
List2<T, Nonempty>? prove_list_nonempty<T>(
  final List<T> list,
) {
  if (list.length == 0) {
    return null;
  } else if (list.length == 1) {
    return List2<T, One>(list);
  } else {
    return List2<T, Many>(list);
  }
}

void main() {
  final a = prove_list_nonempty([]);
  final b = prove_list_nonempty([0]);
  final c = prove_list_nonempty([0, 1]);
  if (a != null) {
    // Prints nothing. This branch is never reached
    // because a is null because [] is empty.
    take_only_nonempty_lists(a);
  }
  if (b != null) {
    // Prints something because [0] has one element which makes it not empty.
    take_only_nonempty_lists(b);
  }
  if (c != null) {
    // Prints something because [0, 1] has many elements which makes is not empty.
    take_only_nonempty_lists(c);
  }
}

// An example of a function that depends on a list that is not empty.
void take_only_nonempty_lists<T>(
  final List2<T, Nonempty> list,
) {
  // We know that 'list' is not empty.
  // We could make use of this fact and e.g. map the list
  // to a new list while maintaining the proof that the 
  // new mapped list is also not empty.
  print(list.list);
}

Notice how take_only_nonempty_lists expects us to give it a nonempty List. Its requirements have been encoded as a Type. This allows us to provide greater safety guarantees.

I hope this shows that Phantom Types are a useful idea as they allow us to maintain properties through Types. Without them, in the example above, we'd have to write down our expectations as comments and hope that no user violates any of our expectations. Or alternatively, we would have to re-check whether our assumptions about any given list are true which is not free (and can be expensive for some properties such as maintaining whether a list is sorted.).

Inline Classes support for Phantom Types

If we want to use phantom types to add more safety to our programs today, we have to pay for a wrapper type. We are forced to make a trade-off between performance and safety. I'm very excited about inline classes because I hope that they could make annotating values with Phantom Types cheaper i.e. remove the costs of the wrapper type (List2 in the example above).

Would the inline classes proposal allow for wrapper types to be zero-cost (i.e. the wrapper object would be free, we'd have to only pay for the phantom type and the wrapped value) or would that not be possible because List2 declares a type parameter that is not being used in the wrapped value?

[lrhn]

I'd say "yes", it you can live with the phantom types only existing at compile-time.
And then you don't have to pay for the phantom type either, you can make those inline class types too.

inline class ListContent { final Never _; }
inline class Empty implements ListContent { final Never _; }
inline class NonEmpty implements ListContent { final Never _; }
inline class One implements NonEmpty { final Never _; }
inline class Many implements NonEmpty { final Never _; }

and

inline class List2<T, Restriction extends ListContent> {
  final List<T> elements;
  
  static List2<T, Empty> empty<T>() => <T>[] as List2<T, Empty>;
  static List2<T, One> single<T>(T value => <T>[] as List2<T, One>;
  static List2<T, Many> all<T>(Iterable<T> elements) {
    var values = elements.toList();
    if (values.length < 2) throw ArgumentError("Not many elements", "elements");
    return values as List2<T, Many>();
  }
}

If you want the phantom types to be reified at runtime, so you can do if (myList2 is List2<T, Many>) and make it mean something, then both List2 and Many need to be non-inline types.

[modulovalue]

If you want the phantom types to be reified at runtime, so you can do if (myList2 is List2<T, Many>) and make it mean something, then both List2 and Many need to be non-inline types.

How will this be enforced? (i.e. the then both List2 and Many need to be non-inline types. part). It seems like inline classes are meant to support arbitrary type parameter declarations. So what prevents anyone from using non inline classes as concrete type arguments for the phantom type type parameters?

inline class List2<T, Unrestricted /* can be anything? */> {
  List2<T> list;
}

In case my description was a little unclear, I'm mostly interesting in using inline classes to remove the overhead of the wrapper and support unrestricted phantom types at the same type (not necessarily in getting rid of any costs that are intrinsic to phantom types, although that would be nice)

[eernstg]

This should just work. However, the implementation of inline classes doesn't yet handle all kinds of type inference (so we need to write a couple of extra type arguments explicitly until that has been fixed).

I don't see any reason to make the phantom type hierarchy an inline class hierarchy (it's a fancy idea, but I don't think it brings any benefits ;-). The effect would simply be that we reserve the same amount of space to store the value of a type variable, but that type variable would always have the value Never (based on the declaration final Never _;, except that we can't actually do that—but anyway, it doesn't save any space or any time to make those classes inline).

So here we go (--enable-experiment=inline-class,class-modifiers):

// ----------------------------------------------------------------------
// Lists with phantom classification.

abstract final class ListContents {}
abstract final class Empty implements ListContents {}
abstract final class NonEmpty implements ListContents {}
abstract final class One implements NonEmpty {}
abstract final class Many implements NonEmpty {}

inline class ListPhantom<T, State extends ListContents> {
  final List<T> elements;
  ListPhantom._(this.elements);
  
  ListPhantom<T, NonEmpty>? get asNonEmptyOrNull =>
      <State>[] is List<NonEmpty> ? this as dynamic : null;

  static ListPhantom<T, Empty> empty<T>() =>
      ListPhantom<T, Empty>._([]);
  static ListPhantom<T, One> single<T>(T value) =>
      ListPhantom<T, One>._([value]);
  static ListPhantom<T, Many> all<T>(Iterable<T> elements) {
    var values = elements.toList();
    if (values.length < 2) {
      throw ArgumentError("Not many elements", "elements");
    }
    return ListPhantom<T, Many>._(values);
  }
}

// ----------------------------------------------------------------------
// Example usage.

void main() {
  final a = ListPhantom.empty<int>();
  final b = ListPhantom.single(0);
  final c = ListPhantom.all([1, 2]);

  // takeOnlyNonemptyLists(a); // Compile-time error.
  takeOnlyNonemptyLists(b); // OK.
  takeOnlyNonemptyLists(c); // OK.

  void f<T, State extends ListContents>(ListPhantom<T, State> list) {
    var maybeList = list.asNonEmptyOrNull;
    if (maybeList != null) takeOnlyNonemptyLists(maybeList);
  }

  // Type arguments will be inferred (when that has been fixed).
  f<int, Empty>(a); // No output.
  f<int, One>(b); // Prints '0'. 
  f<int, Many>(c); // Prints '0'.
}

void takeOnlyNonemptyLists<T>(ListPhantom<T, NonEmpty> list) {
  print(list.elements.first);
}

The most interesting part is probably the treatment of phantom type arguments at run time: We can't communicate to the type system that a given type variable has a value which is a subtype of anything specific (here: State <: NonEmpty) and hence certain variables have more informative types (in particular, list is ListPhantom<T, NonEmpty>), so we need to perform a forced re-typing (here: a type cast). We do that in the getter asNonEmptyOrNull.

[modulovalue]

Thank you for the hint that the experiment is ready to be tested.

There are some other things related to phantom types that I need to try, I will report any issues that I encounter.

(I've tried to hide the inline class behind an interface which did not work for me: dart-lang/sdk#51564)

[eernstg]

I've tried to hide the inline class behind an interface ...

That's inherently impossible: The word 'inline' indicates that there is no wrapper object, so there's no representation of MyInlineClass(o) at run time which is different from the representation of o. This means that we would never be able to run two different method implementations in a scenario like the following:

abstract class Foo { void bar(); }

inline class I1 implements Foo { // Let's just pretend that we can implement `Foo`.
  final int i;
  I1(this.i);
  void bar() => print('1-bar');
}

inline class I2 implements Foo { // Ditto.
  final int i;
  I2(this.i);
  void bar() => print('2-bar');
}

bool b = true;

void main() {
  Foo = b ? I1(42) : I2(42);
  b.bar(); // `identical(b, 42)` is true, and so is `b is int`. There's no trace of the inline classes.
}

We can't distinguish I1.bar from I2.bar, and we can't even start to determine that the relevant choice is from the set {I1.bar, I2.bar} because there could be some other location in code where that same int was used in an inline class constructor invocation like I3(b). In other words, we simply can't allow a reference of type Foo to refer to 42, and it doesn't make any difference that we're wrapping this object in an inline class "instance", because they don't exist.

We can actually allow implements Foo in an inline class (several earlier proposals had a feature like that), but we can't make it mean anything which is similar to implements Foo in a class declaration. In particular, we can't have run-time subsumption such that an expression of type Foo "really is an I1 or really is an I2", because it is really an int.

[eernstg]

Anyway, it looks like there are no actionable issues here, so I'll close the issue. @modulovalue, please open new ones as needed if anything is still unresolved.