const parameters / type parameters

[mraleph]

Background

dart:ffi has a number of APIs which require arguments or type arguments to be compile time constants to facilitate static analysis and tree-shaking. For example, funcPtr.asFunction<DF>() requires DF to be a compile time constant, so that compiler could generate appropriate specialised trampoline which handles Dart->C calls. Similar restriction (for the very same reason) applies to the dual API Pointer.fromFunction(dartFunc), where dartFunc is expected a compile-time constant (static function tear-off).

Currently these restrictions are enforced using custom dart:ffi specific CFE/analyzer passes. These passes have two problems:

• They are dart:ffi specific and can't be reused when a similar need arises in some other API. One example of an API which could benefit from this is PluginUtilities.getCallbackHandle in dart:ui (see also PluginUtilities.getCallbackHandle and tree-shaking flutter/flutter#118608)
• They prevent users from hiding restricted APIs inside their code as an implementation detail:

  void doSomethingAndCall(void Function() callback) {
    c_library.doSomethingAndCall(Pointer.fromFunction(callback));  // error: callback is not a constant
  }
  
  void doSomethingAndCall(Pointer<...> callback) {  // FFI type leaks into API
    c_library.doSomethingAndCall(callback);
  }

We have previously experimented with building a feature like this in the linter: see internal @mustBeConst proposal.

Proposal

Allow const modifier on parameter and type parameter declarations:

class X {
  const X();
}

class A<const T> {
  void foo<const U>(const U u);
  void bar(const X x, {const int v});
}

Adding const to a parameter or type parameter declaration introduces the following restrictions:

1. At a call site any parameter which has const on it must have either a constant argument value or an argument which refers to another const parameter. Other arguments are invalid.

   void Function(const X x) bar;
   void Function(const int y) baz;
   
   void foo(const X x, const int y) {
     bar(const X()); // ok
     bar(x);         // ok
     bar(new X());   // error
   
     int v = 10;
     baz(1); // ok
     baz(y); // ok
     baz(v); // error
   }

2. Similarly, at a call site any type parameter which has const on it must have either a constant fully instantiated type argument value or refer to another const type parameter. Other type arguments are invalid.

   void Function<const T>() bar;
   
   void foo<const T>() {
     bar<int>(); // ok
     bar<T>(); // ok
     bar<List<T>>(); // error
   }

3. Similar restrictions apply to type literals, e.g. A<int> is a valid instantiation of A<const T> and so is A<T> if T is a const-type-parameter, but A<List<T>> is incorrect.
4. Rules for subtyping (and consequenty for valid overrides) respect const on parameters and type parameters in an obvious way: given function types A = R Function(const B) and B = R Function(B) B is a subtype of A, but not the other way around. Consequently overriding a function might remove requirement for parameter to be constant, but can't add it.
5. dynamic calls to function which contains const parameters or const type parameters will result in an exception.

/cc @lrhn @leafpetersen @eernstg @munificent @dcharkes @mkustermann

[dcharkes]

Small note for an implementation:

The FFI requires to know all constants that are flowing in to a constant parameter (error value for FFI callbacks) and constant type parameter (C types for a FFI calls and callbacks). Currently, the implementation (FFI transform) does a sort of inlining of the bodies so that the the constants are immediately in place. And the current implementation only inlines one call deep (and prohibits the rest).

This feature will enable transitive const values. (As Slava mentions to enable users of dart:ffi to build abstractions around lookupFunction etc.) Using inlining as a general implementation strategy could blow up code size a lot.

As an alternative implementation strategy we could consider doing some const-flow-analysis that propagates possible tuples of const values and const types that flow into such functions. (Doing it on a per parameter and per type parameter fashion will lose too much information: for FFI callbacks we need to know the const error-return-value together with the const type argument for the C signature.) [Though, maybe we should implement by inlining first, and optimize later.]

cc @johnniwinther for CFE, @alexmarkov for TFA-like design, and @sstrickl for const-propagation logic.

[mraleph]

@dcharkes inlining does not work as general implementation strategy because invocations might be recursive:

void foo(int level, const int token) {
  if (level != 0) {
    foo(level - 1, token);
  }
}

So we would need some form of TFA support to propagate this information across call-graph edges.

[eernstg]

Just wondering, how would the ability to know that a particular int is obtained as the result of a constant expression evaluation be helpful?

In general, it sounds like you want to perform partial evaluation of invocations of specific methods/functions, because the Dart language abstracts over distinctions that FFI needs to treat explicitly (for instance, FFI needs to generate code separately for each actual value of a given type argument, but Dart is happy to cover all those actual arguments by a single declaration of a type parameter whose actual value isn't restricted by anything other than the bound).

But you do actually need to know the actual value arguments at compile time, not just the actual type arguments, in terms of their precise identity?

[dcharkes]

Just wondering, how would the ability to know that a particular int is obtained as the result of a constant expression evaluation be helpful?

I was just wondering the same. If we start allowing that, we could do:

List<Pointer> foo(const int level) {
  return [
     Pointer.fromFunction<SimpleAdditionType>(simpleAddition, /*errorValue=*/level)),
     if (level != 0)
       ... foo(level - 1),
  ];
}

typedef SimpleAdditionType = Int32 Function(Int32, Int32);
int simpleAddition(int x, int y) {
  print("simpleAddition($x, $y)");
  return x + y;
}

Which would require us to compile many FFI callback trampolines, for every possible value of level once.

But you do actually need to know the actual value arguments at compile time, not just the actual type arguments, in terms of their precise identity?

Yes, the error values are compiled into the code. Even if we would store the error value somewhere else, we would still need a different callback-id and different entry-point in memory to distinguish the callbacks from native.

[mraleph]

Just wondering, how would the ability to know that a particular int is obtained as the result of a constant expression evaluation be helpful?

Imposed restrictions help to perform global propagation of these values and establish which values (or which combination of values) can flow through to a particular interesting call-site.

Knowing possible inputs is good enough for the described purposes.

But you do actually need to know the actual value arguments at compile time, not just the actual type arguments, in terms of their precise identity?

I am not sure I understand the question - this proposal allows you to know the set of possible constant values that flow into a specific function.

[eernstg]

Discussed this with @mraleph IRL, I think I've got a better understanding of the needs now.

So here's a possible interpretation of the feature. My starting point is that it is intended to establish a guarantee that a specific kind of partial evaluation can be performed:

Every method m that has a const parameter p can be replaced by a set of methods m$$1 .. m$$k where each m$$j is specialized to receive one specific actual argument for p, and that actual argument is known at compile time. A trivial example:

class A {
  void m(const int i, int j) => j > 0 ? m(i, j - 1) : n(i);
  void n(const int i) { print(i); }
}

void main() {
  A().m(1, 10);
  A().m(2, -1);
}

// Partial evaluation of the above program yields the following:

class A {
  void m$$1(int j) => j > 0 ? m$$1(j - 1) : n$$1(i);
  void m$$2(int j) => j > 0 ? m$$2(j - 1) : n$$2(i);
  void n$$1() { print(1); }
  void n$$2() { print(2); }
}

void main() {
  A().m$$1(10);
  A().m$$2(-1);
}

It is possible, and it may be useful (in order to save space), to avoid creating specialized variants of all the functions/methods all the way down to the call site, but there would then be a need to create some kind of dispatcher when A.m, say, calls A.n$$1 or A.n$$2, depending on whether A.m is called with the first argument 1 or 2.

A method accepting a const parameter can be overridden, but the overriding method must also make that parameter const.

An actual argument which is passed to a formal parameter p whose statically known declaration is const must be (1) a constant expression, or (2) a formal parameter q whose declaration is itself const.

I don't think we need to generalize this such that const on a parameter is considered to be part of a function type, it's just a thing which is associated with declarations of top-level/static/local functions, and with statically known instance method signatures. A dynamic invocation of a function or a method that accepts a const parameter will throw.

(For instance, we could call an unspecialized variant of the function/method, and it would have parameter type Never for each const parameter; every statically checked invocation would call one of the specialized variants of the function/method.)

Types have a similar distinction: Some terms derived from <type> are constant type expressions (e.g., int and List<int>), but others are not (e.g., Y and List<Y>, where Y is a type parameter).

Considering an invocation of a generic function or method f where a formal type parameter X is marked const, the actual type argument must then be a constant type expression or a type variable Y of the enclosing function/method declaration whose declaration is itself const (in particular, f<List<Y>>(...) is an error).

This sounds like we might have a space explosion, but it also sounds like approximately what's needed. ;-)

@mraleph, @dcharkes, WDYT?

[dcharkes]

This sounds like we might have a space explosion,

This is exactly what I tried to say earlier.

but it also sounds like approximately what's needed

Exactly. :-)

In order to make the language spec more precise, we would need to give examples with the combinations of const type params and const parameters instead of just a single parameter. Because if we lose the relation between possible values of the different parameters the dispatch becomes multiplicative.

class A {
  List<T> n<const T>(const int i, const int j) { print(i+j); return <T>[]; }
}

void main() {
  A().n<int>(10, 20);
  A().n<double>(11, 22);
}

// Partial evaluation of the above program yields the following:

class A {
  // Only the 2 combinations of const type parameters and parameters.
  List<int> n$$1() { print(30); }
  List<double> n$$2() { print(33); }
  // And not 8 combinations with [int,double] x [10,11] x [20,22].
}

void main() {
  A().m$$1();
  A().m$$2();
}

I believe we're on the same page. 👍

[eernstg]

Right, we need to consider distinct tuples containing every const element of the entire function signature, not all possible combinations of values that exist at each position.

[lrhn]

At a call site any parameter which has const on it must have either a constant argument value or an argument
which refers to another const parameter.

That sounds like the definition of "potentially constant", except that we allow potentially constant expressions to do compile-time-computable computations. Should this do the same?

That is, if we invoke a function with a constant argument, and it invokes another function with a constant argument, should that argument be allowed to be any potentially constant expression which refers only to constant parameters?

That suggests that we're going to do compile-time evaluation of the arguments, but we need to do that anyway to ensure they are constant, so it's probably about the same.

But if we do that, then we can also allow const int as a return type of static const int increment(const int x) => x;.
Which would be nice, but probably a step too far. But without that, it's also a very low-benefit feature for the general user.

A larger issue is that potentially constant expressions work both with constants and with non-constants. The latter case just cannot create new constants.
I'd expect the increment method above to be callable with a non-constant argument too, but just that if I call it with a constant, the result is also constant.

That is, the const modifier here works differently from how const works everywhere else in Dart: It requires a constant rather than allowing it.
I'd prefer to not use const in a way which prevents us from later creating const getters and methods with the other behavior, ones which can be used in constant evaluation and then creating constant results, but which can also be used in normal evaluation.
That alone makes me prefer to not add this feature as described, and ask you to use an annotation instead.

Requiring a value to be constant is at odds with how Dart treats constant values - they are just like normal values, except that they can be created eagerly and are canonicalized. After that, there doesn't need to be any way to distinguish const Object() from new Object().
That is, requiring an argument to be a constant value is not useful in plain Dart, it's very use-case dependent for you creating what is effectively a sub-language of Dart where some operations can only be used with constants, even if the computation itself cannot tell the difference. You're implementing your own macros, and asking for language support for it.
I'd prefer that you wait and just use macro annotations for that, or normal annotations now that your own tools recognize. That won't allow you to have function types with const requirements, but it's also a type-system complication that I don't think will be able to pay for itself. It's just a complication that 99% of users won't need.

---

Anyway, the proposal itself:

Are parameters and type parameters the only place this would apply?

Those are typical API boundaries, so it makes sense that this is where you'd put a restriction that apply to other people (if you want only constants yourself, you can just do it).

Would we want to apply it to sub-components of a larger value? It's not easy to make usable, since extracting the value is not going to be a constant expression, but with patterns and the inevitable pattern parameters, we might want to allow something like:

class C {
  final int x, y;
  C(const this.x, this.y);
  C.fromPair((const this.x, this.y));
}

The fromPair constructor can only work if we can distinguish a (const int, int) record from an (int, int) record, and records are similar to argument lists where we do make that distinction.

It'll get harder to track which values flow where if they can go through other objects, but records are really close to just being juxtapositions of individual values, not values of their own, so it might just work.

The subtyping suggests that a const value is a subtype of a non-const value, which makes sense, you can always forget that a value was constant.
But const T is not a general type, its just a marker on parameters and type parameters. It won't be possible to do:

typedef F2<R, T> = R Function(T);
....
  F2<int, const int> f = ...;

Is that a problem? So far, every time we've had a "type" that we couldn't abstract over, we've ended up allowing it. (Well, we did it for void, and for generic function types, and otherwise we haven't even tried to prevent types from being type arguments.)

[dcharkes]

TL;DR: @lrhn has a good point. We should probably explore Dart macros and see what the user experience for this use case is.

Detailed reply:

I'd expect the increment method above to be callable with a non-constant argument too, but just that if I call it with a constant, the result is also constant.

That would not solve the dart:ffi use cases. We require constant arguments and constant type arguments.

That is, the const modifier here works differently from how const works everywhere else in Dart: It requires a constant rather than allowing it.

In the dart:ffi use cases we require it. (Having an allowing feature might be useful as well, but that is a separate discussion from our dart:ffi use cases.)

That is, requiring an argument to be a constant value is not useful in plain Dart, it's very use-case dependent for you creating what is effectively a sub-language of Dart where some operations can only be used with constants, even if the computation itself cannot tell the difference.

Wouldn't the result values be also automatically be canonicalized, isn't that observable?

And maybe code size (canonicalized values), and performance (compile-time evaluation vs runtime evaluation) is important. (Otherwise, we'd drop const from Dart all together and make everything just final?)

You're implementing your own macros, and asking for language support for it.

Aren't partial evaluation and macro evaluation different? Partial evaluation requires that the source code has the same semantics as the partially evaluated code, macros are more free-form. Our macro-proposals can add things to the outline, and create expressions and statements with arbitrary semantics. On the flip side, maybe macros are harder to reason about than partial evaluation.

I'd prefer that you wait and just use macro annotations for that

Agreed, we should try and see if any of our macro prototype implementations would help here.

or normal annotations now that your own tools recognize.

We could generalize the logic we have now with those type of annotations, but if we would want to enable users to build abstractions, they should be able to use the annotations as well. So that feature will likely leak into code directly involved with dart:ffi. If we do implement such generalized thing in the CFE, TFA, and analyzer, I'd rather have it specced out rather good (as good as a language feature). Then it would be a language feature with annotation syntax instead of keyword syntax. (We should probably first explore a macro feature before we go down that road.)

[lrhn]

Wouldn't the result values be also automatically be canonicalized, isn't that observable?

That's a philosophical rathole. 😁
Can you detect canonicalization in a vacuum, or only if you already have the canonicalized value available?

I posit that you can't generally, in plain Dart, write code that takes an instance of a known class with a const constructor, and determines whether the instance was originally created by a const constructor.
(Not unless the class has only a limited number of possible states total, so you can compare to your own const created and canonicalized constants, in which case it's basically an enum. If it has an int field, that becomes impossible.)

There is nothing in the object itself which distinguishes a const created object from a new created object, which is also why the same constructor can be used to create both. A valid implementation strategy for constants would be to just change every canonicalized constant into a reference to a lazy variable initialized with a new invocation of the same constructor and arguments as one of the original canonicalized expressions.
(Collection literals are not the same, they create different collection types when const.)

What you want is not for the run-time values to be "constants", you want the expression values to be available at compile-time, because you are doing things to them at compile-time that you cannot do at run-time.
Which is why I'm saying that you're really doing macros, which is computation at compile-time.

Partial evaluation is basically what Dart constant evaluation does today.
It's possible with today's const rules.
Requiring an expression to be constant isn't necessary for that. Being constant enables partial evaluation, but requiring constants is more like introducing a full two-level language, which is what macros are.

[ds84182]

That is, the const modifier here works differently from how const works everywhere else in Dart: It requires a constant rather than allowing it.

@lrhn I disagree, actually it is quite consistent. It makes sense.

Parameter lists can be interpreted as specialized variable declarations. As a consequence, final is already allowed in parameter lists. This means const is intuitive. The input is a known constant expression. It can be used anywhere a known constant expression can be utilized.

Widget myConstCanonicalizedWidget(const String text) => const MyWidget(..., child: Text(text), ...);

Calling the above would partially evaluate the body at compile time. Doing so would create independent widget constants for each invocation's constant shape.

Furthermore, by introducing a const function modifier (as discussed above) would also allow the usage of the function as a const. However this has restrictions associated to massively reduce scope. The body must be a return statement, or an expression return statement. Other than const variable declarations and nested const function declarations, no other statements are allowed. Note that this can still live in a world with macros and potentially-const functions (like C++ constexpr), but is a stronger version of the latter.

const Widget myConstCanonicalizedWidget(const String text) => const ...(..., child: Text(text), ...);

const helloWidget = myConstCanonicalizedWidget('Hello, World!');

---

As a quick aside, it could also lead to intuitive metaprogramming.

Described here, to avoid gunking up this issue: https://gist.github.com/ds84182/12e12cbf69f2627b462a1308600f9da1

Something like FFI could be implemented on top of this, instead of having to integrate deeply with CFE. But it is complicated, so it is definitely a tool meant to be used by package authors.

[lrhn]

Parameter lists can be interpreted as specialized variable declarations. As a consequence, final is already allowed in parameter lists. This means const is intuitive. The input is a known constant expression. It can be used anywhere a known constant expression can be utilized.

I don't think the analogy works.

A parameter list declares local variables that are initialized at runtime. It's not the same thing - a parameter list declares both a parameter (which becomes part of the function type) and a local variable of the same name (which becomes available in the body scope).

The caller doesn't know whether a parameter variable is final or not, because that's a property of the corresponding local variable, not of the parameter.

Introducing const variables suggest that the local variable will be const. It cannot possibly be so, because a const variable must have the same value each time it's read, and a function parameter can differ per invocation.

So the local variable is not a const variable. What is it then? It is, as described here, more like a potentially constant variable, like the parameter of a const constructor, in that it can be used in other expressions that are required to be potentially constant (arguments to const parameters).

But potentially constant expressions only work for constructors because we can distinguish const invocations, where we do the computation at compile-time, from non-const invocations where we just do everything at runtime. We can find all the const constructors invocations at compile-time, and fully evaluate the entire invocation.

We don't have const invocations of normal functions. If a function has a const argument, we don't know what it will be called with at runtime, or when, or how many times. Not unless we disallow closurizing such functions, because that completely prevents predicting calls. Maybe also prevent the functions from being instance methods.

If we do that, basically making every invocation that requires a const argument into a necessarily static call, then we can statically know all the invocations. We may also be able to partially evaluate const arguments occurring inside each invocation at compile-time, to know the arguments that goes into further const-parameter calls.

But that's not what's described here. I'm not sure what's described here actually makes sense as a general feature, it only works for things where the compiler can interpret the arguments to special compiler-recognized functions.
Everything else breaks down when you try to pass a function value with a const-required parameter around as value, and combine it with a const parameter variable's value later. There is nothing useful the program can gain from that restriction, other than possibly ensuring that an argument will be immutable. (And it will be used for that. Badly.)

Widget myConstCanonicalizedWidget(const String text) => const MyWidget(..., child: Text(text), ...);

Calling the above would partially evaluate the body at compile time.

How, if I do:

Widget myApply(bool choose, Widget Function(const String) factory, const String trueText,  const String falseText) =>
   choose ? factory(trueText) : factory(falseText);

Notice that the factory constructor is not const. I may call myApply with any number of functions in differently places in the program, and with different constant texts.

And what does it even mean to partially evaluate a function call that is not entirely constant. Will you evaluate both branches here? What will you actually do inside the body of myConstantCanonicalizedWidget, if you can even figure out that that's the function being called?

Partial evaluation is something you usually do bottom-up. When all the leaves of an expression are constants, and the operation can be performed at compile-time, then do the operation at compile-time.
A parameter is never known at compile-time unless the entire call-chain from main is known at compile-time.

[rubenferreira97]

@lrhn Some time ago I had some implementation problems because I couldn't declare a parameter as const.
Consider the following example:

extension EnvironmentString on String {
  // Get environment variable, if not set throw `EnvironmentVariableError`.
  static String fromEnvironmentOrThrow(/*const*/ String name) => bool.hasEnvironment(name)
      ? const String.fromEnvironment(name) // compile error here, name must be const
      : throw EnvironmentVariableError('Environment variable $name not set.');
}

Note: C.fromEnvironment can only work with const

This constructor is only guaranteed to work when invoked as const.

Would this be a good example for this issue? It does not have nothing to do with FFI, since it's a user usecase. Another solution was to implement a external const factory that would throw, but users don't have that control.

[lrhn]

Yes, this is a good example of a function which can only work if the function itself can be invoked as part of constant evaluation. If it isn't then const String.fromEnvironment(name) cannot know that value of name at compile-time.
Even if the argument is known to be a constant, the invocation is not. There can be hundreds of invocations of that function, spread across the program, with different constant values for name. It's not possible to compiler const String.fromEnvironment(name) at compile-time, because name is not bound until runtime.

If we allowed such a feature, then the compiler could inline the function at each call point.
That's easy when it's a small static function, but not something which generalizes to large functions (then it could be refactored to compute the constant subexpressions at each call point and pass them to the function, but there cannot be any runtime guards which are needed to prevent errors), and it won't work for instance methods at all.

[ds84182]

And what does it even mean to partially evaluate a function call that is not entirely constant. Will you evaluate both branches here? What will you actually do inside the body of myConstantCanonicalizedWidget, if you can even figure out that that's the function being called?

@lrhn Partial evaluation is not supported. Lambdas can act as an escape hatch for partial evaluation, but it has to be opted into.

In the myConstantCanonicalizedWidget example, the entire expression is a constant value. It can be interpreted as a shorthand for inlining that returned value into the callsite. There is no partial evaluation here, the const on Text was omitted due to it being a const context.

An example of partial evaluation would be const void Function() makePrinter(String text) => () => print(text);. It's rather contrived, but it has some usefulness when used with the dart:meta strawman.

Anyways, this is an entirely separate feature. But it is an extension of const parameters as it relies on it.

Const parameters create specialized versions of a function with those parameters inlined. Like a more limited form of templating in C++, or generics in Rust. It introduces the concept of const (type) parameters to the language. Const functions go a step further, utilizing the same precedent to allow for less code duplication. With the const decoration, you can communicate what methods are usable in a const context. This leads to less magic around List.length, String.length, int.operator+, etc. as there would be an explanation as to why they're usable in const contexts. But this discussion should be moved to #2222, my apologies.

---

As for another example where const type parameters are useful, it allows writing generic code over typed data without sacrificing performance. Here's a strawman example:

// Hypothetically, lets say typedef TypedList<T> = List<T> + TypedData;
int sum<const T: TypedList<int>>>(T typedData) {
  var acc = 0;
  for (var x in typedData) acc += x;
  return acc;
}

sum<Uint8List>(...) // Calls specialized version of sum for Uint8List
sum<Int64List>(...) // Calls specialized version of sum for Int64List