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.)

[zoechi]

Can't this be solved with https://api.dartlang.org/stable/1.20.1/dart-collection/UnmodifiableListView-class.html ?

[lrhn]

I'm not sure I entirely understand the problem setting.

If you have a list that you can modify, and you pass it to someone else, and then they can modify it, but you can't, then it can't be the same object. You need some kind of protocol to ensure that, and it can't just be using plain modifiable lists that you store and pass around.
That is, you can't talk about an "owner" of an object as anything but who has a reference to it.
If you need to switch owners, you need more than one object, and you need to create the new object at the correct time.

We don't have a way to "seal" any List, especially the standard list, and I don't think we want it.
Likewise, we don't want any notification on normal lists (or objects in general). That kind of overhead you have to opt in to.

For copy-on-write, you still need a new instance for each domain, so you need to wrap at the pass-over point, and you probably want to wrap it immediately the list is created, otherwise you can still modify the original without anybody knowing. You need complete life-time control of the objects in question.

You can easily make a SealableList that wraps a list and adds a seal() method. Then you can modify until you are ready and then seal it. Then nobody can change the list again.

class SealableList<E> extends DelegatingList<E> {
  bool _sealed = false;
  SealableList() : super(<E>[]);
  void checkSealed { if (_sealed) throw new StateError("List has been sealed"); }
  void seal() { _sealed = true; }
  E oprator[](int index) => super[index];
  void operator[]=(int index, E value) {
    _checkSealed();
    super[index] = value;
  }
  // etc.
}

That gives you the option of creating a list that can be sealed, but it's opt-in. It's not something you can do to somebody else's list - if they have a reference to a normal mutable list, nothing can take that away from them again.

Ditto for a notify/intercept-on-change list, and a copy-on-write list, e.g.:

class _CopyOnWriteListShare {
  // Number of other CopyOnWriteList instances sharing the same base list.
  int count = 0;
}

class CopyOnWriteList<E> extends ListBase<E> {
  List<E> _base;
  _CopyOnWriteListShare _share = null;
  CopyOnWriteList() : _base = <E>[];
  CopyOnWriteList.from(List<E> elements) : _base = elements.toList();
  CopyOnWriteList._(this._base, this._share);
  List<E> toList({growable: true}) {
    if (!growable) return _base.toList(growable: false);
    if (_share == null) _share = new _CopyOnWriteListShare();
    _share.count++;
    return new CopyOnWriteList<E>._(_base, _share);
  }
  void _copyOnWrite() {
    if (_share != null) _unshare();
  }

  void _unshare() {
    if (_share.count > 0) {
      var copy = _base.toList();
      _share.count--;
      _base = copy;
    }
    _share = null;
  }
  E operator[](int index) => _base[index];
  void operator[]=(int index, E value) {
    _copyOnWrite();
    _base[index] = value;
  }
  // etc.
}

[Hixie]

Flutter's framework wants you to write code like this:

        ...
        new Row(
          children: <Widget>[
            new Flexible(child: new Text('Everything is awesome')),
            new Checkbox(
              value: config.configuration.stockMode == StockMode.optimistic,
              onChanged: (bool value) => _confirmOptimismChange(),
            ),
          ],
        ),
        ...

The Row object uses the list passed into its children argument directly. We can't afford to copy it.

This means people can instead do things like this:

         List<Widget> list = <Widget>[
            new Flexible(child: new Text('Everything is awesome')),
            new Checkbox(
              value: config.configuration.stockMode == StockMode.optimistic,
              onChanged: (bool value) => _confirmOptimismChange(),
            ),
          ];
        ...
        new Row(
          children: list,
        ),
        ...
        list.add(new Text('Hello?'));

...which will cause all kinds of problems.

We'd like to either make it so it doesn't cause these problems (e.g. copy-on-write lists), or make it so we can catch these cases either at analyzer time, compile time, or runtime (e.g. sealing lists), to help authors avoid them. We have gotten confused questions from customers who end up in situations like this and don't understand why it's not doing what they want.

[Hixie]

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

[lrhn]

I see the problem. It's not a problem that can be solved easily. Adding features that allow you to seal an existing object that someone else has created isn't really feasible - list or otherwise (and a feature that only works for List seems like a kludge).

In general, if someone passes you an object, you don't get to decide anything about that object. Either you make your own copy of it, or you live with what the creator of the object has chosen for you.

If you have a policy that says that you shouldn't change the list, your clients should follow that, just as they should follow all the other policies (like not implementing the Flexible interface in a way that's incompatible with general Widget behavior).

One thing you could do is to remember the original length of the list, and check occasionally whether it has changed. That would at least catch the "add extra element to list" bug, but won't catch if someone replaces an element.

I can see that copying everything is an overhead, especially if there are many small lists.
Copying a list shouldn't be that slow. If you copy to a non-growable list, it should be one new-space allocation, two writes (header and length) and a mem-copy of the contents of the source list, but all copying costs, and all allocation increases memory churn, even one as simple as this.

All in all, I don't see the requests here as viable. Especially if you don't want anything to be slower.

Now, if we had positional rest-parameters, your clients could pass parameters without creating a list, and you would receive them as a list that nobody else has a reference to. That might solve the problem without giving anyone a way to mess with other people's Lists.

Or a way to transfer elements from one list to another, leaving the original list empty.
But that only works for growable lists - you can't empty a fixed-length list, so you would need to handle a fixed-length list differently.

[Hixie]

This doesn't have to be solved with something that affects release-mode runtime semantics. For example, we could have an API that is only enabled in checked mode, like "debugSeal()", which sets a flag which add/remove/etc assert is false. (One could imagine even that you would pass a string to debugSeal and the assertion would use that string if it throws, to make debugging this viable.)

If you have a policy that says that you shouldn't change the list, your clients should follow that, just as they should follow all the other policies

Well, yes, but the problem is how to help them when they don't realise that that is the policy.

[Hixie]

To give an example of how this can just be a debug-mode or analyzer-level feature:

like not implementing the Flexible interface in a way that's incompatible with general Widget behavior

We plan on addressing that particular issue with an analyzer lint.

[Hixie]

Here's an example of a customer being tripped up by this: flutter/flutter#8952

[zoechi]

@Hixie did you consider https://github.com/google/built_value.dart and https://github.com/google/built_collection.dart (I assume you did - just to be sure ;-) )

[Hixie]

@zoechi I don't see how those help. The class we have to use is whatever [] literals give us, and we want to avoid any copies.

[lrhn]

I can see only one solution that is at all plausible, and that is to "lazy-clone" a list with copy-on-write semantics.
That would allow the original owner of the list to keep a reference to it and modify it, without it costing you anything if they don't do it.
It does mean that each List must be at least two objects. It already is for growable lists, but fixed-length and const lists are just single objects. Const lists are "easy" because you can't write anyway, so you can give the same reference to all users, and "lazyClone" would just return itself.
Fixed length lists has to fail cloning, which is annoying.

Also, this is just VM semantics, dart2js should also support the operation, and there is no good way to share list structures when you use native JS lists. So, not really viable as a JS strategy.

So, maybe, just maybe, it could be implemented as an optimization strategy for the VM's implementation of List.toList(). It only triggers when you use a growable list as base and result, and it would just replace the class pointer for the list objects with a CopyOnWrite class.

It is not something we can handle at the library level, and probably not even at the language level, so I'm reassigning this as a VM feature.

[rakudrama]

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. The analysis also has to track backwards to see if there are other access paths to the list, since all pointers to the list become unmodifiable. Imprecise aliasing (both forwards and backwards) is a source of false positives (spurious reports) in such an analysis, but often, like flutter/flutter#8952, the aliasing relationship is precise. If you are happy detecting most, or just many, design pattern violations, the noise from false positives can be tuned out.

[Hixie]

That would be wonderful.

[leafpetersen]

Do you actually ever need the list to be modifiable in the first place (and only subsequently sealed)? In the code snippet you gave, it seems like a literal form for an unmodifiable (from creation) list would suffice?

[Hixie]

We commonly build the list incrementally, e.g.:
https://github.com/flutter/flutter/blob/master/packages/flutter/lib/src/material/scaffold.dart#L235
https://github.com/flutter/flutter/blob/master/packages/flutter/lib/src/material/app_bar.dart#L349

[eseidelGoogle]

We have another customer get confused by the gotcha in Flutter for which this is a possible workaround just now (modifying a list, repeatedly passing the same list to a new Widget, and being confused that his UI didn't change).

[Hixie]

cc @floitschG this is the bug we were talking about the other day

[rakudrama]

We are spending a lot of energy to avoid copying one small list.
So, why not copy the list inside the framework?
This seems to be what the users expect, and no doing so is causing them pain.

The copy can be unmodifiable, which will be approx half the size (one object instead of two, no internal fragmentation). If you have lots of such lists, it will be beneficial to have the more compact copy and have larger growable lists GC-ed.

Is copying really too slow? Most of the ideas are adding various kinds of code to the system which is not free, and might end up being more expensive than copying the list.

If copying the list is too slow, find out why. The VM could have special knowledge of new List<Widget>.unmodifiable(list) in order to make the copying as fast as possible, possibly using hand-written code for the common case of copying from standard corelib lists.

[Hixie]

It's not one small list, it's hundreds of lists, every 16ms. We have a budget of about 8ms for the entire frame. We already frequently go over budget. We really can't afford to be doing any extra work that we don't need to be doing, especially memory copies. It would be much cheaper to not do any work in release mode at all, and do a couple of extra branches of work in debug mode.

[rakudrama]

It is not clear that avoiding a copy is necessarily the fastest way.
You might avoid extra work by copying.

Consider an app that uses

children: <Widget>[new ...]

and

var list = new List<Widget>(5);
...
children: list

and

children: const <Widget>[]   // perhaps via a default value

These three lists are different types. The code that iterates the children will slower because each access now is an if-then-else on the type of the list. If the code walking the children list is one piece of code that is used by all widgets in the app, each additional list type it could slow down the whole app. By copying you could force a single type and avoid this if-then-else tax (except in the copying :-). If you create the lists once and walk them many times you might come out ahead by copying.

You can hunt for this kind of problem (multiple kinds of list) in observatory.

You alluded to doing more in debug mode. You could in debug mode copy the list to a shadow _children list and periodically check that the contents are identical to the copy.

[leafpetersen]

I'm also pretty skeptical about this being an overall win. Unless it's purely a debug option, you're trading off making everything everywhere a little bit slower against a possible win at one point. And if it's purely debug, then doing the defensive checks in the framework seems at least worth exploring.

I don't know what parameters the VM uses for allocating growable lists, but it is pretty much inevitably either over-allocating them for your use case, or else already copying when it grows them. Either way, I have to wonder whether you wouldn't be better served both performance and correctness wise to have the APIs take an immutable list. The copy that happens when you cross the API and you did in fact start with a mutable list has a cost, but you will be shrinking the object in the process (getting rid of over-allocated space and moving to a more compact representation) which means that the GC will do less copying. And if it is a reasonably common pattern to pass in a list literal, then the intermediate literal could/should be optimized away, and the immutable form generated in place.

Some concrete data here might be useful.

[Hixie]

We'd love the API to take only immutable lists. Unfortunately the common case is passing in a non-const list literal, and those are mutable.

[Hixie]

@floitschG @munificent @leafpetersen Friendly ping. We're finding a lot of new users end up tripping over this. Just being able to seal lists in debug mode and assert would be super helpful (especially if we could provide a custom message for the assert!). I'd be happy to try to do this entirely on the framework side but I don't really know how to do that.

[Hixie]

The widgets don't take a copy of the list, they take a reference to the list. So when you mutate the list, you're mutating the list inside the widget, and then when you call setState and it rebuilds, the widget looks at the "old" list and the "new" list and sees that they are identical.

[icatalud]

Updated

If they take the reference, then mutating list and calling setState is not a problem.

Case 1 (works fine problem):

final foo = List(...)
// .. children: foo
foo.add(1);
setState((){})  // problem, does not rebuild

Case 2 (problem works fine):

var foo = List(...)
// .. children: foo
foo = List(...);
setState((){})  // ok

But there is no way around that, unless the var itself was special and it had some kind of hook that alerted when there reference has changed, something very unorthodox.

That is a mistake from the developer side.

[Hixie]

Case 1 is the case that doesn't work today (it creates broken results), case 2 works fine. Case 1 would be solved by the suggestions in this bug, either copy-on-write (which would allow the widgets to cheaply copy the lists they get), or sealing (which would cause the snippet in case 1 to throw an exception on the add).

[icatalud]

If Case 1 does not update correctly, then this is currently a bug in Flutter. Programs should be consistent first, optimized secondly. This is not consistent, because it's a hidden unsuspected behavior of the framework. If this is documented and users can predict it, its still not correct because it's non intuitive (people don't read all the documentation).

The framework should be currently working as expected under all circumstances, and this feature should be a request for an optimization, but no the other way around.

[Hixie]

I disagree, but I think this is mostly a matter of philosophy, so I doubt there is a compelling case to be made in either direction.

[icatalud]

I disagree, but I think this is mostly a matter of philosophy, so I doubt there is a compelling case to be made in either direction.

You disagree with:

1. Consistency first, optimization second.
2. That this is hidden non intuitive behavior of the framework.
3. The framework should be currently working as expected under all circumstances.

Be precise so that anyone can understand and discuss the ideas behind both sides of the disagreement. It's not just a matter of philosophy, because by defining standards these decisions can be objectivized. The only situation where this is not a bug is if the rules of rebuilding were very well explained. But then it is questionable that the rules have such kind of complexity (APIs should be simple).

About (2) I can ensure you it's non intuitive to some people and it could be very costly. I certainly never expected that and I'm lucky I didn't find this bug (because of the style and library I use). I had a similar discussion with some Dart team member in #24206 about an inconsistency in the hashCode field which costed me at least three weekends.
A good way to leverage the importance of reliability is putting yourself in the feet of the developer and imagine how they might think and use the framework. Then the possibility that some will use it in that way becomes a border case that should be addressed (because they will be clueless).
These bugs are the most difficult ones to revert because they imply a performance cost (perhaps it's negligible in this case) and most applications are working fine because they do not deal with these edge cases.

[Hixie]

I disagree that the contract required by the framework is not consistent (it's well-defined and clearly-stated, it's just a contract we can't currently enforce in the language) and I disagree that optimisation should come second (API design must balance performance, usability, and various other constraints together).

I agree that it's not intuitive to everyone, that's why this bug was filed in the first place, to resolve that issue.

[icatalud]

See feature request #225 which asks for freezable objects which could disambiguate this. But I must insist that it is far better from the user perspective that in the mean time some performance is sacrificed until the right feature has been developed. If the type of the list is checked, the users can still have optimal performance if they pass immutable lists.
I think API simplicity is really important to make the framework welcoming and friendly to the users. This edge cases can scare some people away, because it's too technical, think from the perspective of people that are far less knowledgeable in programming.

[davidmorgan]

I think companies shipping apps in Flutter might disagree with you about a performance hit being okay :)

Anyway, I'm afraid what you ask is impossible.

There is no immutable list type that is compatible with List and can be checked for at runtime. For example, although const [1, 2, 3] is a different type to [1, 2, 3], the implementation type is private to the SDK and can't be used for checks.

"Immutable" list views do not solve the problem, because the underlying list can still be mutated.

If there was a way within the current SDK to make this work I would be using it as a performance optimization for built_collection constructors to avoid copying unnecessarily. There isn't :) ... the only way to get immutability from List right now is to always copy, which is too expensive for this use case.

[davidmorgan]

"If the user passes an ImmutableList on the first place".

Please read my post again. It is not possible to check whether what is passed is an immutable list. Dart does not have an accessible type called ImmutableList, or any other immutable list type.

What you are suggesting is not currently possible. I don't mean that we don't want to do it. I mean it cannot be done as you describe. It would require a core SDK change and/or a language change to introduce immutable collections.

[icatalud]

Dart does not have an accessible type called ImmutableList, or any other immutable list type.

It would require a core SDK change and/or a language change to introduce immutable collections.

const [1, 2, 3] is a different type to [1, 2, 3], the implementation type is private to the SDK

Finally I understand that part. I have assumed all this time the existence of ImmutableList. But then if Flutter required it, it should have been created by Flutter. Users just had to do FlutterList(otherList), which is as inconvenient as defining ImmutableList, unless Dart provided some kind of shortcut for the creation of ImmutableList (if it existed).

Please read my post again.
There is no immutable list type that is compatible with List and can be checked for at runtime.

I did read that part, apologize for not understanding, but I got confused by some terms (fixation with the idea that Immutable existed lead me to believe there was a confusion). Now I understood.

Summarizing the problem
The options to deal with the mutability of List are:

• Rebuild every time when there are lists of children (rebuild stops at the children)
• Copy the list the first and then perform list comparison by values
• Accept only FlutterList (immutable) type
• Accept both own list and default list, and treat the cases separetely (the best imo)
• Add complexity to the API explanation

It was opted for the last one, which is ok, but what I was saying is that it should be justified with numbers that at least the first second and fourth options (which accept default List) are nonviable in performance terms (what is the actual cost in a real app?).

I can imagine some apps where they have List with thousands of widgets and therefore iterating them becomes an important part of the build time. I had no idea that that optimization was being done, many times I plainly place the children like children: [w1, w2, ...bigList, w3] and assumed that Flutter would rebuild all that tree anyways. I have only created small example apps though (no more than 2k lines). But the cases of huge lists are limited within apps, users could take special care on those cases and pass a FlutterList as an optimization.

Currently the documentation is not clear about the reference comparison, that could be updated until this is resolved, it would help users determine why their app is not behaving as they expect.

[dave26199]

Thanks. The final part of the problem is this: there is no way to create an immutable FlutterList that is fast. It always requires copying all the elements to create it so it's guarded against mutations.

I created BuiltList which is I think the most popular immutable list class for Dart :) ... whenever you create one from a List or Iterable it copies all the elements.

This is okay for BuiltList--okay, not great--because in most usage collections stick around for a while, and have a tendency to get defensively copied, which can be automatically avoided if they're immutable. So in most usage this is fast enough.

But in the Flutter usage it is intended that you frequently recreate the widget tree--on every frame. It's how Flutter uses Dart in place of a domain specific language for defining UIs. So, that extra copy is unusually expensive.

Which is why we keep coming back to needing language and/or SDK support to solve this. And why as soon as there is a solution I hope it also makes BuiltList faster :)

[lrhn]

The one case where you don't need to copy is where the user creates a list once, passes it to the widget, and never touches it again.
Let's assume that that is a common case. Avoiding copying just in those cases will still have a measurable impact on performance.

Now, the current platform has no way to distinguish this case from a case where the list is modified again, so it either has to defensively copy the list every time, or not copy it and document that the user should not modify the list.

The Flutter designers also want it to be easy for users to write the code, so they do not want to force users to write something convoluted. A plain list literal is the preferred syntax for providing a list of values.

There is no efficient way to copy a list cheaply. There is no cheap way to make an existing list unmodifiable without copying it. On the VM, there are ways around that, but it's not something we can port to JavaScript easily.

[lrhn]

@tatumizer
The problem with copying a list cheaply is that there is no solution that works both on the VM and in the browser. Well, except introducing a freeze to the VM, which I'm solidly against—it's not good for encapsulation if someone somewhere else can make your list immutable. There is no way to protect against that except ... well, copying the list before giving it away. It's a foot-cannon to allow freezing of arbitrary lists that the original creator did not opt in to making freezable.

Any other approach is limited by the JS lists being implemented directly by JS arrays, so anyone with access to the list has a reference directly to the array. We can't make that copy-on-write because JS doesn't have that functionality. The VM growable lists can be made copy-on-write (CoW) because they have a nested (and accessible to the VM) backing array that can be shared between different CoW-list objects. But fixed-length lists cannot, because they have no backing array.

So, all in all, every approach to avoid copying has a bad interaction with at least one of the VM lists types or JS lists. That's what I mean when I say there is no efficient way to cheaply copy a list: There isn't one which has a good API and works across platforms.

[Hixie]

@lrhn The debugSeal proposal is not "freeze someone else's list", it's "add a debug-only flag (aka assert) to indicate when you mutate a list that you have previously passed to an API that has a contract that says that you transfer ownership of the list". By passing the list to a Widget you are opting in to transferring its ownership, it's no longer "your" list. That is the case today. All that is being asked for is a way to detect contract violations in debug mode. It doesn't have to work in Web at all, even.

@tatumizer By "cheaply" we mean "O(1)".

[hpoul]

maybe a bit far fetched, but how about a completely separate unmodifiable (builtin) type like pythons tuple? For Flutter's children pattern it could be a Tuple<Widget> children and list literals being tuples depending on context, similar to number literals becoming double in the right context? although modifiable Lists would still need to be copied 🤷‍♂️️

(btw. is this related to #36097 "Introducing support for transitively freezing an object graph (i.e. making it immutable)")

[Hixie]

FWIW, I continue to design APIs that take lists and cannot afford to copy them, and assume that the caller has relinquished ownership of those lists. I still think it would be a huge improvement to the language if there was some way to cheaply copy a list (even if it was only cheap for built-in lists), or a way to mark a list such that any future mutations threw an exception.

[rakudrama]

@Hixie FWIW it is already relatively cheap to copy system Lists. List.of on the VM ends up in one of 10 inner loops depending on the source Iterable. Six of the 10 inner loops are are copying from growable, fixed-length or immutable/const system List implementations (x2 for whether the result is growable for fixed length). This happened late last year: 6b6ecce

In addition to being faster, this change also protects basic list copying from the polymorphism performance disease that I mentioned over in the sister issue.

[davidmorgan]

Thanks @rakudrama. That change again highlights the gap in what the SDK currently offers: immutable collections currently have to be provided as third party packages, but there's no way to make them fast because the SDK implementation only recognizes its own types for the optimized paths.

[Hixie]

@rakudrama There would be literally thousands of these to copy every 4ms in some Flutter apps, I don't think it's practical (and certainly would use a lot more CPU than not copying them, which is what we do now, and which works except for the problems discussed above).