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.