Sealing or watching List objects, or copy-on-write List objects

[Hixie]

In Flutter, we pass lists around but it is a convention that once you have passed a list to an object, you no longer "own" the list and are not allowed to modify it.

Unfortunately, nothing in the language, API, or tooling actually support this, and so it's very easy for our customers to think they are keeping ownership of the list and for them to then run into trouble when either the changes have no effect, or the changes unexpectedly have an effect, depending on what they were trying to do.

---

Possible ways we could address this:

• having a way to "seal" a List object and thus prevent people who have references to it from ever modifying the list again.
• having a way to be notified when a List object created from a literal is changed, so that we could then throw with a message that says "you can't modify the list"
• have a way to very cheaply "copy" a List object created from a literal, using techniques such as "copy on write", so that we can say that later modifying the list is fine but doesn't affect the widgets that used the original copy. (Ideally such a solution would be compatible with passing const lists to const constructors but having those same constructors usable with new and getting this copy-on-write behaviour.)

[yjbanov]

I think C++ const does the opposite of what you want

Agreed. I updated my comment, added unique_ptr and std:move. That said C++ const is still a good demo of a zero-cost purely type system-based way to solving similar problems. Now that Dart is going strong mode, I think the language should lean on similar sound type-based solutions rather than dynamic checks and (costly) object wrappers.

[leafpetersen]

Haskell also tackles this through the type system. It's a pretty dense interface, but gives you both safe an unsafe ways of dealing with these things. The nice version uses a monadic interface to allow a mutable vector to be created, initialized by user code, and then in place frozen in a way that guarantees that no aliasing happens. See the docs on create or modify in the links below.

It's obviously a pretty heavy type system though, and the vector API is... less than approachable.

https://hackage.haskell.org/package/vector-0.12.0.1/docs/Data-Vector.html https://www.schoolofhaskell.com/user/commercial/content/vector

I don't see any path for Dart to get anything like a Rust or Haskell type system for enforcing these sorts of things - they are very far afield from the core ideas of Dart.

[davidmorgan]

We seem to have gotten away from the idea of a unmodifiable list literal -- I think this is simple and would offer real value.

Is this something that could happen, please? I'd like to see unmodifiable map literals, too; both would need to be cheaply detectable from the modifiable literals, so things like flutter can enforce their use.

What syntax to use is a hard problem, but I'm sure we can come up with something ;)

Thanks!

[munificent]

We seem to have gotten away from the idea of a unmodifiable list literal -- I think this is simple and would offer real value.

That isn't the original request actually. Note this comment: https://github.com/dart-lang/sdk/issues/27755#issuecomment-292009273

The request is for a mutable list that can be imperatively sealed after the fact.

[matanlurey]

I'm taking this thread offline with relevant folks.

[yjbanov]

I think the thread should continue for openness sake, but I'd be totally happy to meet in person too.

[yjbanov]

The request is for a mutable list that can be imperatively sealed after the fact.

We should have @Hixie confirm this, but I don't think that's the request, but only a statement of what we do currently that causes the issue of losing write-ownership to the list. Alternatives suggested thus far seem too syntactically/conceptually/performance taxing for adoption.

unmodifiable list literal

This may actually be one possible solution if it also supported inline conditionals that would remove the need for most of mutations in the first place. Let's say we used the final keyword for the unmodifiable list literal: final [1, 2, 3]. Then instead of:

  final list = [1];
  if (condition) {
    list.add(2);
  }
  list.add[3];

One could do:

final list = final [
  1,
  if (condition) 2,
  3,
];

No mutations, immutable result.

[leafpetersen]

Several languages have copy-on-write arrays, e.g. PHP or ObjectPascal. These would solve the problem, albeit not with the most help to the developer.

Is this really true for ObjectPascal? The only references I can find on a quick search suggest that some of the string types implement copying using copy-on-write, but that arrays are aliased as usual.

[leafpetersen]

unmodifiable list literal This may actually be one possible solution if it also supported inline conditionals that would remove the need for most of mutations in the first place.

I'd be surprised if this really addressed all of the original request. @Hixie can you address this?

Is the intent that unmodifiable lists would be proper subtypes of regular lists (implementing all of the modification operations by throwing), or supertypes of regular lists? And what is the type on the receiver?

Note that unless you arrange the types in such away that the user can't pass a regular list, then you're not really addressing the original request. This probably means that you want UList <: List and to type your API to take UList (hence you can't pass a regular list).

[Hixie]

The problem descriptions from the November 3rd and 4th comments are my best attempt to describe the problem. I'm not sure how else to explain it. tl;dr, there's no language or library support to catch violations of the Flutter framework ownership model (that once you pass the list to a widget, the widget owns the list and you can't modify it anymore).

@leafpetersen You are right, my bad. I was mixing AnsiString and dynamic arrays. The new management operators in FPC make it possible to implement this in general, though, I believe, for any custom type.

[leafpetersen]

The problem descriptions from the November 3rd and 4th comments are my best attempt to describe the problem. I'm not sure how else to explain it

I think my specific question boils down to this:

Would you be ok with making all of your APIs for which you wanted to enforce this contract use the UnmodifiableList type for their parameters instead of the List type, with the understanding that regular lists could not be passed where an UnmodifiableList was expected?

If the answer is yes, then I agree that unmodifiable list literals + @yjbanov's proposal could solve some large fraction of the problem.

If the answer is no, then I think unmodifiable list literals are a red herring.

[Hixie]

If we can port existing code to this model without introducing new copies or making the code less ergonomic, then sure, though if that's the solution then we should do this soon because that's a really invasive breaking change to the API which would surely affect many of our customers.

FWIW, some of the existing code doesn't use list literals at all. For example, it uses Iterable's API to filter some list owned by the parent, then calls toList on the result to get a copy and passes that to the widget. Some of the existing code uses const list literals (ideally a lot more would, but we are blocked by https://github.com/dart-lang/sdk/issues/29276). Some builds the list imperatively, sometimes in logic that spans multiple functions before the list is passed to the widget.

[davidmorgan]

Does UnmodifiableList vs List need to be detectable statically? I was envisaging this:

Widget createWidget(List list) {
  // can make this debug only, add based on version, etc, to migrate.
  if (list is! UnmodifiableList) throw 'Unmodifiable only';
  ...create widget...
}

Then it becomes an enforced convention that people have to pass an UnmodifiableList literal.

A different static type seems better, but the runtime check seems much easier to land -- if it's good enough?

[lrhn]

If you can usefully do list is UnmodifiableList then UnmodifiableList is a subtype of List and you can also write createWidget(UnmodifiableList list).

I'm not sure we want that. We have deliberately avoided having multiple List types that users need to pick between. That was a design choice made early in the Dart library design process, and we have kept it so far. It would also require all unmodifiable list implementations to implement that type, otherwise it wouldn't always work. For example, a const list would then probably also have to implement UnmodifiableList.

Instead, we could have List<T> Iterable.toList({growable: true, unmodifiable: false}), and if you call toList(unmodifiable: true) on an unmodifiable list, it returns itself. That would allow you to copy only when necessary, and with a way to express unmodifiable List literals, uses can create those directly. It still allows users to avoid extra copying, but it also allows them to use a normal list if that is what they have.

As for conditionally included list literal elements, the if syntax is probably a little too tricky, and it doesn't generalize well to more than one element. Other options is an "elided" expression result (I'm trying not to say "value") that gets removed from literals, so [1, 2, x ? 3 : elide, 4] (with a much better syntax, obviously) would become [1, 2, 4] if x is false. Another, probably more general, approach would be to allow a spread operator in a list literal: [1, 2, ...list, 3] would include the elements of list in the new list. It's like a string-interpolation for lists, and it can be used to include or omit single values as [1, 2, ... x?[3]:[], 4].

(Just speculating, no promises about any of this!).

[davidmorgan]

toList(unmodifiable: true) would be really nice to have, and, yes, I think it fits the use case. If we want we can do:

var unmodifiable = list.toList(unmodifiable: true);
if (debugMode && !identical(list, unmodifiable))
  throw 'Performance hit: please pass unmodifiable list';

But I'll let @Hixie comment as it's his issue :)

[lrhn]

I'm not sure we would promise that toList(unmodifiable: true) returns the same list. Maybe it will return a new list with the same backing store, which will still avoid copying the elements, but not necessarily avoid allocation completely. I prefer not to restrict the implementation too much. If some other List implementation decides to handle its unmodifiable list versions differently, it should be allowed to.

[yjbanov]

@leafpetersen

Would you be ok with making all of your APIs for which you wanted to enforce this contract use the UnmodifiableList type for their parameters instead of the List type, with the understanding that regular lists could not be passed where an UnmodifiableList was expected?

The semantics LGTM. I think UnmodifiableList and List not being cross-assignable but easily cross-convertible would be sufficient, as long as both still implement Iterable for compatibility with many existing utilities. The name UnmodifiableList is a mouthful. People will be typing it a lot. Also it implies compatibility with the List type, which is not the case. I'd look for alternative names that are both shorter and do not cause confusion. A couple of ideas: Array, Seq (a la F# and Scala).

@lrhn

I'm not sure we want that. We have deliberately avoided having multiple List types that users need to pick between. That was a design choice made early in the Dart library design process, and we have kept it so far.

True, and probably made sense in 2011, when Dart's only framework was dart:html. It also made the [] list literal very convenient as you only need one syntax to express all lists. However, it's 2017, and the world is moving to a new style of programming, one that favors immutability. Today the most convenient, the most idiomatic syntax gives you a plain mutable List :( Dart punishes you for using immutability, with extra/longer keywords (see final, @immutable), circumventible type system (BuiltList is all nice but I can go ahead and implement BuiltList and make it mutable), and expensive copying (e.g. List.unmodifiable). I think we need considerable improvements in this area.

a const list would then probably also have to implement UnmodifiableList

Would this be problematic?

toList(unmodifiable: true)

Where in code would this appear? If it's everywhere a list is constructed, then I doubt Flutter users would be happy to use it.

"elided" expression result

If it doesn't generalize to multiple elements better than inline if, then meh...

spread operator in a list literal: [1, 2, ...list, 3]

:+1: Ooh, this looks nice!

[Hixie]

But I'll let @Hixie comment as it's his issue :)

My recommendation would be to try to convert some of the more esoteric build functions to the proposed API and see if they remain intuitive. Hopefully most would remain unchanged with no loss of performance.

[dave26199]

I don't know if this came up before -- I seem to recall it did but coudn't find it -- what about varargs as a way to let people write their own "literals"?

https://github.com/dart-lang/sdk/issues/16253

--> Varargs would need to be implemented such that it guarantees the resulting list is owned by the receiving method, i.e. nobody else can have a reference to it. --> We can then wrap the list immediately to ensure nobody else ever gets a reference to it.

e.g.

static ImmutableList<T> immutableListLiteral(T... varargs)
    => new ImmutableList._withoutCopying(varargs);

void main() {
  new Widget(subwidgets: immutableListLiteral(widget1, widget2, widget3));
}

It effectively gives a way to write your own list-based literals. (It would be nice to have a "varmap" equivalent to let people write their own map-based literals, too).

[srawlins]

@bwilkerson I am really curious about the typestate analysis that @rakudrama mentions above:

This problem could be detected by static analysis tools, specifically typestate analysis, although this is more advanced than the tools we currently have which are very lint-like.

A typestate analysis could track the modifiablility of the list, assigning the state 'unmodifiable' from the point of being passed to the constructor, validating that the list does not flow to operations that would modify it. In effect, this is simulating the 'read-only' bit in the analysis.

Does the analyzer feature any APIs that would allow writing such an analysis?

[MichaelRFairhurst]

Regarding the breaking change of requiring all children list literals to be changed to final list literals, we could explore inferring mutability like we infer Sets vs Maps and Ints vs Doubles.

ImmutableList x = []; // inferred immutable
List y = []; // inferred mutable
[]; // backwards compatability, inferred mutable
final []; // we can keep Yegor's syntax too for the remaining cases :)

// less breaking of a change:
children: [ // inferred as immutable when children is typed as immutable
  ...
]

Doesn't handle the places people do .toList() though.

Just in general, https://medium.com/flutter-community/kt-dart-better-collections-for-your-flutter-business-logic-41886ab7883 raises some valid complaints about current lists in Dart and can be read as some suggestions to consider.

[Hixie]

The case where people pass a literal is fine. The case where people call toList() and pass the result is fine too. It's the case where people pass a local variable that they then subsequently mutate that's the problem.

[eernstg]

@lrhn, why is it that we can't just introduce something like this into dart:core?:

abstract class ImmutableList<E> extends ListIterable<E> {
  List<R> cast<R>();
  E operator [](int index);
  int get length;
  Iterable<E> get reversed;
  int indexWhere(bool test(E element), [int start = 0]);
  int lastIndexWhere(bool test(E element), [int start]);
  List<E> sublist(int start, [int end]);
  Iterable<E> getRange(int start, int end);
  Map<int, E> asMap();

  // Maybe include these: Methods where `E` is used contravariantly.
  int indexOf(E element, [int start = 0]);
  int lastIndexOf(E element, [int start]);
  List<E> operator +(List<E> other);
}

// And then:
abstract class List<E> implements ImmutableList<E> { ... }

OK, maybe ListIterable should be kept 'secret', but surely those things can be sorted out.

Client code could then immediately start using the type ImmutableList<E> for lists that are intended to be immutable (thus helping developers to avoid the unwanted usages of mutation related members), and certain expressions, say, const <T>[..], could have static type ImmutableList<T>. Of course, that would be breaking for workflows using --no-implicit-casts, so we'd need to do the usual breaking-change dance and get those changes introduced in a way that everybody can live with (ok, almost everybody ;-).

It would be much more of a breaking change to start creating instances whose type is ImmutableList<T> and not List<T> (say, const <T>[...] could start yielding such objects), but we can do that in a 2nd phase, or omit that step entirely if it is considered too breaking. In any case, it would certainly be possible to allow for such "typed immutable lists" to be created using new syntax (or even by existing constructors like List.unmodifiable(Iterable elements)).

[lrhn]

1. Naming. If List implements ImmutableList then a mutable list is-an ImmutableList. That's ... highly confusing.

2. Every API should now start worrying whether to accept ImmutableList or List as argument type. Unless everybody does that correctly, you will have cases where you have an ImmutableList and want to pass it to someone who expects a List (because you know it won't mutate it anyway), but you can't. Should an API return an ImmutableList or a List? Should JSON parsing return an ImmutableList? (Maybe yes, but that breaks the use-case of receiving a list and then mutating it). Should we have guide-lines to always return a full list, and always accept an ImmutableList unless you need to mutate it?

3. Is the cast deliberately returning List (which will still throw if you try to mutate it)? Or should it have returned ImmutableList? Should sublist have returned an immutable list too? Should operator+ create immutable lists from immutable lists? Why/why not? Every API which mentions List needs this discussion. There is no clear and simple answer that is always correct.

So users will need to choose. Every time they write List, they now need to decide whether they mean List or ImmutableList (and why not just Iterable?) and that extra mental overhead is one of the reasons we have avoided creating such classes (we tried, it was called Sequence, it was removed again almost immediately because it encouraged behavior that we didn't want. And this was back when we had Collection as an interface above List and Set, instead of just Iterable).

We definitely can introduce something like that in the platform libraries. We don't want to. The mental and programmatic overhead that the distinction introduces is not worth whatever benefit you would get from it.

[lrhn]

However, coming back to the original problem: If we had a way to create an unmodifiable list literal, without requiring it to be constant, then users can use that. With spreads and control-flow operations in list literals, there shouldn't be a need to build the list imperatively, so a read-only list literal would actually be read-only.

(There would still not be a way to recognize it as such, and no way for an API to require list arguments to be unmodifiable).

[davidmorgan]

That doesn't solve the original problem, which is about transferring ownership of the list.

To solve ownership you either need to be able to require the list is unmodifiable or check and efficiently handle the case where it isn't.

[eernstg]

@lrhn wrote:

a mutable list is-an ImmutableList. That's ... highly confusing.

Nope, that's exactly the way it should be.

Every API should now start worrying whether to accept ImmutableList or List as argument type

Granted, but that would be a useful addition to the indications about how those lists are going to be used behind that API.

Taking an ImmutableList where a List used to be accepted is generally a non-problem: A List is still accepted. For return types and other covariant usages it would make a difference. This may or may not be a problem (esp. when using --no-implicit-casts), but if there is a static problem here then maybe it would be a good opportunity to adjust the type annotations concerned with the reception of such an object.

So, lots of breakage here because List is used everywhere, but it seems to be a rather relevant and useful kind of breakage, and we could provide some tool support for changing a lot of type annotations from List<T> to ImmutableList<T>, immediately covering the cases where there is no mutation anyway..

Is the cast deliberately returning List (which will still throw if you try to mutate it)?

No, it sounds quite plausible that cast should return an ImmutableList<R>, such that it could be immutable (and it could be a return this in some rather common cases), and similarly for the other examples. The override in List would then (probably) covariantly specialize the return type. So there's more work to do before that API will work really well, but I'm sure we can sort that out.

don't want to.

Maybe.

[eernstg]

@davidmorgan wrote:

That doesn't solve the original problem, which is about transferring ownership of the list.

Right, in order to get a type based guarantee that a given list will not be mutated (and hence it can be shared freely) we'd need a proper subtype of ImmutableList<T> which is not a supertype of List<T>.

@lrhn just suggested a name like ReadableList, which makes sense for a list which can be used for reading (and we just don't know whether it supports writing), and then ImmutableList would be a subtype of ReadableList for which it is intended to be guaranteed that this is a list which is not mutable and hence can be shared. So List would be a subtype of ReadableList, but not ImmutableList.

Of course, the type system cannot establish any firm guarantees of this kind anyway (unless we consider typing properties which are directly concerned with absence of mutations, cf. https://github.com/dart-lang/language/issues/125), because any class type could have a member like clear() which would mutate the receiver even though it does not have any contravariant occurrences of the type argument in its signature. But it would probably be sufficient in practice to have a ReadableList and ImmutableList type (and letting the type of const literal lists be the latter), in return for being somewhat compatible with the huge amount of usages of types like Iterable and List.

[yjbanov]

@eernstg wrote:

@lrhn wrote:

a mutable list is-an ImmutableList. That's ... highly confusing.

Nope, that's exactly the way it should be.

Then it wouldn't solve the original problem. If List is-an ImmutableList, then I can pass a mutable List to a widget and continue mutating it while the widget assumes no further mutations.

@davidmorgan wrote:

That doesn't solve the original problem, which is about transferring ownership of the list.

The problem is not exactly about transferring ownership. It is about users passing a list to a widget then mutating the list. Transferring write-ownership is one possible solution to the problem, but it's not the problem. Other solutions are possible, such as immutable lists (i.e. nobody has write-ownership), sealing, and copy-on-write.

@eernstg wrote:

unless we consider typing properties which are directly concerned with absence of mutations, cf. dart-lang/language#125

Yes, I think it would be more practical to move this discussion to that thread. Immutability can solve many problems, including this one, and if we find the right semantics for @leafpetersen's immutability proposal we can solve a lot with one language feature.

[eernstg]

@yjbanov wrote:

Then it wouldn't solve the original problem.

Using Lasse's proposal to call it ReadableList<E> and making ImmutableList<E> a subtype of ReadableList<E> which is not a supertype of List<E> would enable a discipline whereby an ImmutableList<...> is guaranteed to be shareable. (Of course, we would need something like dart-lang/language#125 in order to get a language-level guarantee against mutation, but anyone who writes a mutable class which is a subtype of ImmutableList where the mutation goes beyond caching would be taken out at dawn and frowned at ;-). The reason why this could make sense is that our literal forms and existing code uses List; otherwise we could just start from scratch with a fresh, 'statically tracked shared immutable' list class.

is one possible solution

OK, I thought sharing based on immutability was already considered the desired solution. But ownership (and whatever else might come up) is of course a completely different notion.

[pauldemarco]

Something I really like about Dart is the simplicity of the core data types. It would be a real shame if this leads to any sort of ambiguity to List or the literal [].

I would also aim for a solution that avoids requiring the user to know about different List subclasses. I really don't want to spend cognitive resources trying to decide which List I should make when I need a collection of elements. "I want a collection of elements? Oh I use the List." --nice and simple.

This might be a solution:

final list = [1,2,3];
/// Somebody else seals the list
list.seal();

list.add(4); // throws UnsupportedError

As the creator of the list, I should have a good idea what might have sealed the list. Alternatively, I could force the error to be thrown upon the non-creator of the list:

final list = List([1,2,3], allowSeal: false);

list.seal(); // throws UnsupportedError

[MichaelRFairhurst]

a mutable list is-an ImmutableList. That's ... highly confusing. Nope, that's exactly the way it should be.

It's OK for a mutable list to implement an immutable interface, but a mutable list is not immutable.

A lot of people get this backwards, but the liskov substitution principle says that mutability is a supertype of immutability, not the reverse:

A violation of this constraint can be exemplified by defining a mutable point as a subtype of an immutable point. This is a violation of the history constraint, because in the history of the immutable point, the state is always the same after creation, so it cannot include the history of a mutable point in general. Fields added to the subtype may however be safely modified because they are not observable through the supertype methods.

Source: https://en.wikipedia.org/wiki/Liskov_substitution_principle

Essentially this is the problem:

double distance = dist(coordOne, coordTwo);
callerPassedFunction(); // do potentially anything, out of your control.
return distance; // is this still the correct distance or did it mutate?

I'm not sure how often this subtlety of LSP comes up in real life, but that's what we're facing here.

Not having setters on Coord doesn't mean the above code should be fine. But docs saying "Coord is immutable" does, and users should not pass in a mutable coordinate without expecting problems.

The same applies to ImmutableList. That isn't just an interface, that's an express contract, and users should not be able to break that contract so easily as List being assignable to ImmutableList.

There's a close equivalence here:

class SomeWidget {
  ImmutableList<Widget> children;
  int childrenCount;
  SomeWidget(this.children) {
    this.childrenCount = children.length;
  }
  build() {
    // childrenCount *must* still match chlildren.length!
  }
}

Obviously the type system can only help solve this problem so much. But making List a subtype of ImmutableList would be using the type system to actively perpetuate this problem.

This is all, really, though, all best summarized like so:

ImmutableList immutableList = new MutableList(); // blatantly false

[MichaelRFairhurst]

@pauldemarco

That would be potentially a step forward, but I'm hoping we can do better. The right usage of immutable lists could in theory make programs run faster, and let the type system catch errors where people mutate lists they weren't supposed to (like const lists).

Dynamically sealing lists is cool but introduces a performance penalty because now writing to lists requires a dynamic check to see if that's legal first.

Not sure if we can come up with something better though, there's definitely no clear consensus yet in this thread.

[eernstg]

@MichaelRFairhurst wrote:

ImmutableList immutableList = new MutableList(); // blatantly false

That is a compile-time error, assuming the subtype relationships that I mentioned:

abstract class ReadableList<E> extends ListIterable<E> {...}
abstract class List<E> implements ReadableList<E> {...}
abstract class ImmutableList<E> implements ReadableList<E> {}

Note that ImmutableList is neither a supertype nor a subtype of List. So a ReadableList will let you invoke non-mutating operations on a list (including mutable ones), and ImmutableList is used for lists that are actually immutable (and it offers the same interface as ReadableList).

As I also mentioned, unless we add mutation related static checks like those of dart-lang/language#125, we don't have language level support for immutability enforcement in a type. (You can always create a new subclass, add a new mutable field int someFreshName; and a mutator void someFreshMethodName() => someFreshName++;, and that new method could also be an override of any existing method, such that code could mutate the object without knowing the new class).

Without those checks it would still be possible to create a new class which is a subtype of ImmutableList whose instances are mutable in some way; but that could be done in order to improve performance (caching), or it would be a blatant bug. So, even without mutation related static checks we would be able to trust such objects to be freely shareable.

[eernstg]

@MichaelRFairhurst wrote:

A lot of people get this backwards, but the liskov substitution principle says that mutability is a supertype of immutability, not the reverse:

And the referred wiki page says:

History constraint .. Objects are regarded as being modifiable only through their methods

The Liskov substitution principle is irrelevant to object-oriented programming in that respect. Maybe that will be a surprise ;-), but think about it:

Such a history constraint will make sense for the relationship between abstract data types and their implementations: An implementation of an ADT must implement that abstract data structure, period, and you should actually, without any danger of introducing a bug, be able to edit your program such that it stops using one implementation I₁ of the ADT and starts using I₂ instead. So each (correct) implementation is a completely transparent replacement of any other (correct) implementation.

But the history constraint isn't a useful concept if you try to enforce it for object-oriented subtype structures. For instance, you wouldn't want to insist that with Point p1 = new ColorPoint(3, 4, "red"); and Point p2 = new ColorPoint(3, 4, "blue");, p1 == p2 must return true, based on (1) if we have Point p1 = new Point(3, 4); and Point p2 = new Point(3, 4); then p1 == p2 it must return true, and (2) ColorPoint <: Point, so it shouldn't make a difference that we're operating on color points. So we can only fulfill the history constraint if we implement == on color points such that it ignores the color.

It is not just an == thing, any method override would be seriously constrained if it were to guarantee that no future behavior will differ from that of the behavior of an instance of a supertype. Just think about how useful toString() would be if it could never be overridden in such a way that it would reveal anything about the receiver beyond the fact that it is an Object.. ;-)

Hence, a history constraint is far too rigid in an OO setting where we have subtype relations that are used to model conceptual relationships. It only makes sense in a strict ADT setting where we only have the types (abstract data types) and the implementations, and each implementation implements exactly one ADT.

So the useful way to think about this is that we'd want a considerably weaker notion of substitutability, but if a subtype has more operations than a supertype, then we can expect to be able to do things with the subtype than the supertype will not faithfully emulate (so the histories of behavior will be different). In particular, if a supertype has no operations for mutation then we can't just conclude that every subtype thereof also has no mutation operations. (Note again that Object has no member that supports mutation. ;-)

This is the reason why we would want to be able to specify explicitly that a given type T and all its subtypes satisfy some extra constraints, in this case: Every instance of type T (and that includes instances of subtypes of T) is immutable. If we add such a mechanism then we can trust the property of being immutable (hence, of being freely shareable) to be enforced by the language for all subtypes.

But, as I mentioned, we can currently make the choice to rely on that property being maintained by convention, and it should be a requirement that we as developers can maintain correctly, that every subtype of ImmutableList must be implemented in such a way that its instances have no observable mutation.

[davidmorgan]

Creating separate immutable interfaces doesn't require an SDK change; we already have e.g. BuiltList. We use Iterable for ReadableList; in practice they seem to be close enough.

I think there are two things preventing BuiltList from satisfying this issue:

1) There's no way for it to avoid copying list literals for safety, so it's too slow (TODO: verify? Maybe it's fast enough in practice). Discussion around solving this: https://github.com/dart-lang/language/issues/187

2) Adopting BuiltList would require changes to all the Widget APIs, which would require changes to all users of those APIs. I don't see any obvious way around this. We could look at ways of making it possible for literals to automatically instantiate to the type required in the context when it has a constructor that accepts the literal ... C++ style ... that's a big can of worms to open. And, it wouldn't help when the values from from a local variable--those would have to be explicitly created in the new type.

• Updating the widgets to take Iterable instead of List (or, think ReadableList, if the detail of Iterable offend you) would allow but not require people to pass immutable lists, which is insufficient.
• Updating the widgets to take Iterable and immediately construct BuiltList from that Iterable would work in all cases, but only be fast if a BuiltList is passed in: when a List is passed in it would have to copy.

[eernstg]

@davidmorgan wrote:

There's no way for it to avoid copying list literals

The intention behind adding types like ReadableList and ImmutableList to the Dart core libraries would be that we would then be able to give the value of a const list literal like const <int>[2, 3] a suitable type.

A soft model (that is, an approach where we give it a high priority to minimize breakage) would be to give such an expression the static type ReadableList<int>, and the dynamic type would be a subtype of ImmutableList<int>, such that an assignment to a variable of type ImmutableList<int> would succeed. We should also have an ImmutableList.unmodifiable(Iterable elements) constructor that would allow us to get an immutable list from other sources than a constant expression.

This would enable developers to safely use the type ImmutableList and safely share such instances.

We might not be able to remove List from the type of constant lists (which means that the type List would continue to be unsafe, in the sense that it could throw if we try to add an element, and the list turns out to be immutable), but we could of course remove that subtype relationship from all sources of immutable lists that involve new syntax (for instance, ImmutableList<int>.unmodifiable([1]) could return an instance o such that o is List would be false). We might also want to make const [] is List false, at the end of a long transition period.

But the main point is that the desired safety property could be achieved: You can share an ImmutableList, because it is actually immutable. And we wouldn't have to copy list literals (both the constant and the non-constant list literals can be immutable if we are willing to use ImmutableList.unmodifiable; and ImmutableList.unmodifiable on a list literal could use compiler magic to avoid copying anything, it would directly proceed to create an immutable list with the elements specified in the dynamic list literal).

Adopting BuiltList would require changes to all the Widget APIs

Some level of breakage would still be present, but we could introduce these immutable lists (or maps, etc.) in more than one way:

The most static approach goes as follows: An API that used to accept an argument of type List is changed to use ImmutableList. All callers would then be forced to to pass an object which is actually an immutable list, and the framework would have the static guarantee that it is only working on immutable lists. It would also break subtypes, because they would need to change their overriding method declarations to accept ImmutableList. An API that used to accept an Iterable could stay unchanged (and it would accept arguments of type ImmutableList, no problem, also when the actual instances stop implementing List).

An intermediary approach could go as follows: The API accepting List could be changed to accept ReadableList, which would allow both immutable and mutable lists to be passed. It would serve as a reminder for the implementation of the API that said argument has no mutator methods (and a downcast to List would be needed to get to them), but it wouldn't help enforcing the constraint that those lists cannot be modified. Nevertheless, clients might conspire to pass lists that are actually immutable, in which case the desired safety property is achieved in practice, even though the type checker did not help us getting there.

Finally, the API could be left unchanged, accepting List. This could still be safer than it is today, given that we could have the situation where all the lists we actually encounter are immutable. But it would stop working at the point where it gets impossible to obtain an immutable list which has type List. (So, at the end of that long transition period, when const [] is List yields false, we wouldn't be able to pass such a list as an actual argument to that API). This means that the code must be refactored to some other model (e.g., the intermediary model) at that point.

A similar set of considerations apply for the case where the API is a method signature that returns a list. That could again be changed from List to ReadableList or ImmutableList, or it could stay unchanged if it is currently Iterable, and these changes could introduce downcasts or type errors ('side casts') at call sites.

Updating the widgets to take Iterable instead of List (or, think ReadableList, if the detail of Iterable offend you) would allow but not require people to pass immutable lists, which is insufficient.

We do have the choice here, as described above, and I believe that the available choices carry some reasonable trade-offs in terms of changes needed and guarantees achieved:

I think it does make sense from the API point of view to require ImmutableList, in order to have the guarantee that there is a fast index access operation (operator []), and we have immutability (Iterator doesn't promise any of those things).

With ReadableList we only constrain the framework itself to stay away from mutating the given list (which may or may not allow for mutation; and, of course, the framework can always try to downcast to List and mutate it anyway), so that won't help clients to get it right, but they can pass immutable lists, and that will continue to work (also if we change the API to require ImmutableList at some point).

If we keep the API at List then we (1) won't help clients, and (2) it will break if/when we change instances obtained from constant list literals such that they don't implement List any more. At that point the API would then have to change in order to get any of the benefits of immutability, i.e., we would then switch to one of the other approaches.

The associated breakage corresponds to this: More guarantees, more breakage.

[Hixie]

Early in this centithread I posted some comments with the requirements we have for solving the Flutter problem that led to this bug being filed. I obviously have no problem with solutions to other problems being discussed, but for the record, solutions that don't fulfill the requirements described in those comments would not solve the problem that Flutter has. The specific requirements aren't necessarily obvious; in particular, most variants of "immutable lists" don't generally solve the problem at hand.

[davidmorgan]

Thanks @Hixie. Did I correctly identify that the problems with immutable lists as a solution are 1) arranging that there is no additional runtime cost, and 2) that a migration of API+clients would be required? Is there anything else?

[eernstg]

@Hixie, that would be this?:

(Our requirements are that it not make using the framework any more awkward syntactically or any slower in release builds.)

I think we can get there with the ideas that we have on the table.

With the hierarchy I mentioned here, it would not require copying or extra syntax on const list literals.

I mentioned that ImmutableList<...>.unmodifiable(...) could be used to create immutable lists in general, and that a compiler could compile ImmutableList.unmodifiable<...>.unmodifiable([1, 2]); to an immutable list without creating the mutable one otherwise denoted by the argument.

Also, @kevmoo suggested that something like ^[...] could be used to specify an immutable list literal which is not constant (https://github.com/dart-lang/language/issues/187#issuecomment-457449728). We could also use the context type to infer that any given list literal should be made immutable.

I think this would in fact deliver on your requirements.

[lrhn]

The type hierarchy you refer to would make constant lists not implement List. That would be very breaking.

Without that, it would only work if the code can test the argument for being an ImmutableList, which brings us back to the problem of placing ImmutableList in the type hierarchy (which we'd prefer to avoid).

We could add List.isUnmodifiable and List.isFixedLength as properties on lists (well, we can't because it will break every implementation of List), then the code could see that an argument is unmodifiable, independently of whether it implements any particular type.

One option is the marker interface (which is usually considered an anti-pattern). If we introduce abstract class UnmodifiableList<E> implements List<E>{} and make all our unmodifiable list classes implement that, then code can test whether an incoming list is unmodifiable by doing is UnmodifiableList. Nothing prevents malicious code from having a mutable list implementing UnmodifiableList, but if you compile malicious code into your program, you're doomed anyway.

The problem, which we want to avoid, is that you can then write a method that will only accept UnmodifiableList. We are back to every usage of List now having to consider which list to expect or return, which complicates APIs significantly (and doesn't actually do anything for code safety, since any List might be unmodifiable).

Or we use ModifiableList as marker for lists that are modifable, and then you can check if a list is unmodifiable as list is! ModifiableList. User created lists will likely forget to add that interface, so you might get modifiable lists that are not marked as such. And again, any List might be modifiable or not, and we don't want functions to require ModifiableList (it's an implementation detail, so the static type of a list literal will not be ModifiableList).

I don't think the type system is where we want to fix this problem.

[eernstg]

would make constant lists not implement List

I proposed that they should have static type ReadableList and a dynamic type that implements ImmutableList as well as List. This would allow assignments to List as well as ImmutableList for these constant lists, and for any instance of type ImmutableList it would actually be guaranteed that it is immutable.

And then, after a long transition period, we might get away with a more strict approach where constant lists do not implement List. We would then have the extra guarantee that there won't be any dynamic errors based on attempts to modify such a list.

marker interface

We could use a marker interface, but we would then have an interface for immutable lists which seems to promise that they can be modified. I think it's useful to give immutable lists a type which reflects what they can actually do.

The problem, which we want to avoid, is that you can then write a method that will only accept UnmodifiableList.

But this is exactly the kind of guarantee that we are looking for: It should be possible to freely share certain objects. That won't work if they are mutable. So we want to know, by way of the static type, that we are currently dealing with an object which is immutable.

I don't think the type system is where we want to fix this problem.

Not even in order to ensure that the statically known type of such objects faithfully reflects which operations they support? I'd say that is a task which is very well suited for a type system.

[lrhn]

@tatumizer That straightforward solution sounds like C++ const.

First of all, that won't solve the current problem. You can pass a mutable object to a const parameter in C++. The request here is for a way to ensure (or check) that a incoming list is not modifiable by someone else. Marking your own reference as non-modifying won't do anything for that.

There are various arguments for and against C++'s const feature,

• https://google.github.io/styleguide/cppguide.html#Use_of_const
• http://wiki.c2.com/?AvoidConstCompletely
• https://en.wikipedia.org/wiki/Const_(computer_programming)#Problems

It will likely work for Dart, the question is whether it's worth the complexity that it adds. Adding C++ const to the Dart language is a breaking change (and it would have to be called something else, let's say unmod). If anyone adds unmod to a parameter, nobody else would be able to call it, so introduction would need some way to gradually migrate the code (probably pretty similar to nun-nullable types). We then have a situation where you can, and must, choose everywhere whether to require an unmodifiable argument. The viral propagation of const dependencies (if one const method needs to call another method, that other method needs to be const) causes modelling complexity, similarly to how async functions force other functions to be async (that's just the other direction: If a function needs to call another async function, the first function then needs to be async).

I'm not particularly convinced that C++ const is worth it. It doesn't introduce any new functionality (like async does), it just restricts you from doing some things at the type level without introducing a separate "readable-only" super-type. Java goes a long towards that with their Foo<? extends C> type, where you can only use the methods where C occurs covariantly, not contravariantly.

[Hixie]

Let me try to explain the constraints using examples. These are part of State objects that define the behaviour of a stateful widget.

I want this code to work as it does today:

  Widget build(BuildContext context) {
    return Row(children: [Placeholder(), Placeholder()]);
  }

I want this code to work as it does today:

  final List children = [Placeholder(), Placeholder()];
  Widget build(BuildContext context) {
    return Row(children: children);
  }

I want this code to work as it does today:

  List children;
  void initState() {
    super.initState();
    children = [Placeholder(), Placeholder()];
  }
  Widget build(BuildContext context) {
    return Row(children: children);
  }

I want this code to work as it does today:

  List children = [];
  void initState() {
    super.initState();
    children.addAll([Placeholder(), Placeholder()]);
  }
  Widget build(BuildContext context) {
    return Row(children: children);
  }

I want this code to show a useful error message when addChild() is called (ideally), or, alternatively, to update the UI with no errors. Today it would get the framework into a broken state, either not updating the UI or throwing in an unhelpful place deep in the framework.

  List children = [];
  void initState() {
    super.initState();
    children.addAll([Placeholder(), Placeholder()]);
  }
  void addChild() {
    setState(() { children.add(Placeholder()); });
  }
  Widget build(BuildContext context) {
    return Row(children: children);
  }

I don't want the solution to make existing code measurably slower or bigger.

[eernstg]

@tatumizer wrote:

Because it doesn't matter how you syntactically express immutability

As @lrhn already mentioned, constraints on executable code ("this code can't modify the object which is reached via a specific parameter or variable") does nothing to ensure immutability of any particular object, because you're free to modify the very same object if you can get some other reference to it (which isn't const, or whatever that property is called).

So it certainly matters whether it's immutability via a specific reference (like C++ const) or immutability as a property of an instance (as proposed in dart-lang/language#125, where it's a property of a type and hence a property of all instances of that type and all its subtypes).

But there's no realistic hope that we can enforce the total absence of apparent state changes in a language where mutability is present at all. For instance, you could always have an immutable "box" which uses access to a global entity to make it look like it has a final field that changes over time:

class ImmutableBox<X> {
  final X value;
  ImmutableBox(this.value);
}

Map<Cheater, Object> _cheaterData = {};

class Cheater<X> implements ImmutableBox<X> {
  X get value => _cheaterData[this];
  Cheater(X x) {
    _cheaterData[this] = x;
  }
}

Now, some code somewhere could change _cheaterData (doesn't have to be in Cheater, if your immutability rules are strong enough to prevent side-effects on global data in an immutable class), and your ImmutableBox instance (which turns out to be an instance of Cheater) will change state.

The class Cheater would satisfy the constraints that we have considered for declaring shallow immutability, and it is actually never mutated, but the fact that it is able to refer to state outside the object (possibly through any number of function calls), or, e.g., it gets the current time, or lots of other things that aren't "pure" if you think about it, we can't rely on the type system to enforce that any given object behaves consistently with the expectations based on having immutable state. I'm not convinced that we can realistically give Dart any rules concerning immutability which are strong enough to actually prevent apparent mutation of instances of "immutable types". So we will presumably need to rely on an incomplete guarantee plus some developer discipline: "If you write a class implementing ImmutableBox, you must make its instances behave like an immutable object!"

[rakudrama]

Nearly two years ago I suggested a static analysis tool using typestate analysis could find a large proportion of errors where the list should not be modified after it is captured.

Now that we have transitioned to a front-end that generates the Kernel representation, we have a good foundation for writing such tools. Are there other problems that would yield to typestate analysis to amortize the cost of producing such a tool?

[davidmorgan]

So we will presumably need to rely on an incomplete guarantee plus some developer discipline: "If you write a class implementing ImmutableBox, you must make its instances behave like an immutable object!"

That seems fine; I don't think it is significantly different from allowing subclassing in the first place. If people write a subclass ignoring the intent of the author of the base class, it will cause problems :)

@Hixie thanks for the examples. I think this is an important problem ... unfortunately we do not seem to be a great deal closer to a good solution :/

[Hixie]

IMHO the simplest solution is just to add a method called debugSeal() to the List interface, which has the following contract:

• In release and profile mode, it's a no-op, compiled entirely out of the app.
• In debug builds, if any mutation to the underlying list is attempted after the list has had debugSeal() called on it, then the mutation may throw an exception saying that the list has been sealed and cannot be further modified.
• For extra credit, debugSeal could take a String which is included in the exception when it throws.

This solves the problem described in this bug and meets all the requirements.

[Hixie]

I think it's fine if it's only implemented for the kind of list you get from [], the kind of list you get from new List(), and the kind of list you get from calling toList on most Iterables. That should hit the vast majority of lists.

Making it efficient isn't especially critical since it only has to work in debug builds; in release builds this code can all be entirely compiled out.

[eernstg]

@tatumizer wrote:

.. there's not much contradiction .. The main objection against C++-style const .. is its viral nature. Same will be present in type-based solution

There's one huge difference: With a C++ style const mechanism there is zero resistance from the compiler against creating a mutable list, passing it on with a const modifier on the receiving parameter declaration, and then modifying it. So we're going to help the Flutter framework avoid changing certain objects, but there will be no help against the actual problem: The client doesn't really know that the list should never be changed after passing it to Flutter, so they go ahead and change it. In contrast, an ImmutableList like the one I proposed would offer static and dynamic protection against changes.

About the guarantees:

runtime checks give 100% guarantee

With the current approach, a list obtained from evaluation of a constant list literal will throw if you try to modify it. Obviously, you would have both static and dynamic checks with a straightforward implementation of ImmutableList (because it simply doesn't have any of those mutator methods that we'd otherwise implement as throw ..., so you couldn't even try to call them except with a dynamic invocation), and even with an implementation that also implements List, we would obviously still have the same throwing method implementations for all mutator methods. So you don't get to call operator []= on such a list except when it has type dynamic, and even then it'll throw.

The fact that you can write a class like Cheater is not a problem in real life: Unless you're actively trying to cheat, instances of any class that implements ImmutableList will actually be immutable. Still, cf. dart-lang/language#125, it would be very easy to add compile-time checks on all subtypes of a type marked as immutable such that developers writing such classes would get an error if they declare a mutable instance variable or make similar basic mistakes.