Statically tracked shared immutable objects

[leafpetersen]

This is a proposed solution to the problem of communicating data between isolates.

This proposal adds a static notion of immutability which guarantees that once initialized, any immutable object is the root of a fully immutable object graph, which can therefore be shared between isolates with no copying required.

This proposal also incidentally provides at least a partial solution for the following problems:

• Building immutable collections
• Unwanted mutation of lists in Flutter

Initial draft proposal is here

[leafpetersen]

Draft PR up for comment.

[pulyaevskiy]

Would this be somewhat similar to Scala case classes or similar immutable structures?

Also how equality and hashCode would work if I have two instances of immutable class that hold identical values? E.g.

Say:

class User immutable {
  final String id;
  final String name;
  User({this.id, this.name});
}

final a = User(id: '123', name: 'John');
final b = User(id: '123', name: 'John');
print (a == b); // ?

If, it's going to be similar it would be nice to have a convenient way to create a copy of such immutable object, similar to Scala's copy method on case classes.

[leafpetersen]

I think it might be a good idea to have equality and hashCode be automatically derived, and have structural semantics.

What is the motivation for having a copy method? I would think that since they are deeply immutable, you should never copy (just share)?

[munificent]

What is the motivation for having a copy method?

In Scala, the generated copy() method has optional named parameters for each field in the case class, so you can produce a copy while changing one or more of the fields. Sort of like OCaml's functional update syntax.

[pulyaevskiy]

Yes, copy is sort of a magic method with named parameters for every field.

You can actually see this pattern in Flutter copyWith method.

[munificent]

When/if this gets further along I'll have a lot more detailed feedback around stuff like syntax and policy. Overall, I think this is a really interesting proposal. I'm not sold on all aspects, but I think it's a good starting point. Here's a couple of high level things:

• Immutability is a hot topic in general right now. A lot of programmers are realizing that their programs are easier to reason about and maintain when they know which parts of their data is immutable and which isn't. So I expect that if we ship anything around "immutability", users will want to be able to use it for lots and lots of their classes.

  That's a good thing, because it means this feature can provide a lot of value for a lot of users. But it also means we should make sure it's general enough to be a good fit for as many kinds of immutable data as possible. I don't see anything the proposal that gets in the way of that now except that, like Yegor, I think the syntax should be nicer. I think data class Foo { ... } looks pretty good.

• Related to the above, I think many users will expect these to have value-like semantics, (for some definition of "value"), so implementing hashCode and operator ==()` is probably worth considering.

• I do think users will need some kind of runtime checking for whether or not an object is immutable, for code like:

  takeList(List stuff) {
    // Defensive copy, only if needed.
    if (stuff is! Immutable) stuff = stuff.toList();
    _field = stuff;
  }

  A marker interface works fine, I think.

• The flow analysis feels pretty complex for the amount of value it provides.
  For user-defined classes, shallow immutable objects (i.e. all fields final) require every bit of state to be initialized before the constructor body exits, and that doesn't seem to be too painful of a restriction for users.

  Lists and maps do tend to be imperatively built more than classes, so I can see why they might be special. But, even so, I think most intended-to-be-immutable lists and maps probably aren't mutated after their initial literal expression ends. With the stuff we're talking about adding to collection for UI as code (spread, if, for), that goes even farther. The latter in particular means you can do a lot of interesting imperative work right inside the literal before the object is ever observed.

  I'm also worried about brittleness. Hoisting a chunk of initialization code out into a helper function will either break the flow analysis, or require us to add interprocedural analysis. The former feels annoying, and the latter feels like a lot of mechanism to add for what we get in return.

  So, if it's possible, I think it's worth seeing if we can get by without the flow analysis stuff at all.

• Taking that out would mean there's no way to statically prevent you from calling things like add() on an ImmutableList since it does statically implement List. I wonder if we should consider either something like C#'s explicit interface implementation or have ImmutableList not implement List but support an "implicit conversion" to List that's a no-op at runtime but hides the mutating List methods statically.

I really hope we can make progress on this.

[leafpetersen]

• With the stuff we're talking about adding to collection for UI as code (spread, if, for), that goes even farther.

I think the UI as code collection features would help a lot. The things they don't cover are:

• The cases where you need random access initialization (rather than just sequential initialization)
• The cases where you want to refer to other elements of the array during the initialization process

Maybe these are rare enough that it's ok to do this in two steps: first fill in a mutable list, then copy it to an immutable list?

It would be good to look at some real code to see if it fits these patterns. @aam do you have any concrete examples you have been working from?

[munificent]

I could be wrong, but my hunch is that both of those cases are rare enough that building a separate mutable list and copying is sufficient. I'd definitely like to see motivating examples too. I don't have a good feel for what kind of code is driving the feature.

[aam]

It would be good to look at some real code to see if it fits these patterns. @aam do you have any concrete examples you have been working from?

I was looking at transferrables, rather than immutables, so the use-case I've been looking at is image loading in https://github.com/flutter/flutter/blob/master/packages/flutter/lib/src/painting/image_provider.dart where if you move image downloading off to a separate isolate(good thing), then you have to copy all downloaded bytes back to main isolate(bad thing). "Simple" solution for this "simple" problem(transfer of unstructured typed data) that I'm using to jump start more vigorous analysis of this area is to introduce another constructor for Uint8List that would create "transferrable" list, a list that can be 0-cost moved (transferred) from one isolate to another.

[yjbanov]

I'd like to link some of the properties of immutable objects that have been mentioned in this thread to specific Flutter issues that they could potentially solve (@Hixie for sanity-checking):

• Immutability: solves this issue Sealing or watching List objects, or copy-on-write List objects sdk#27755
• Fast cross-isolate sharing: solves the issue of transferring big chunks of structured data between isolates. One example is parse a big piece of JSON or protobufs in an isolate, then share the data with the main isolate for rendering.
• operator==/hashCode: this could make UI rebuilds more efficient because the framework relies on operator== to decide whether a widget needs to be rebuilt (source). In practice few users implement hashCode and == so that equality check can only pass when two widgets are identical, which is rarely the case when you call setState. I only works when you cache widget object or use const.
• Regular classes extending immutable classes: this was discussed in the proposal PR. This property would allow us to make the Widget class immutable as a non-breaking change. Also, not all widgets need to be deeply immutable. Some widgets could carry references to stateful service objects. Instances of such widgets would not be shareable with other isolates. However, having operator== and == would still be useful.
• Implicit conversion between List and ImmutableList: discussed in the proposal PR. this would allow us to convert final List children to ImmutableList children as a non-breaking change.
• Canonicalization: discussed in the proposal PR. This would make tree comparison cheap (practically free). For example, if a widget near the top of the widget tree calls setState but only affects one branch in the UI, the framework can push the state change down the tree automatically without developer's involvement. However, this would potentially make allocation of such objects more expensive. This needs to be measured.
• Non-nullability: this property would produce fewer objects on the heap, particularly non-nullable ints, doubles, bools, Strings.

I have more thoughts on this here. The tl;dr version:

• Would love to see a lightweight syntax for this, e.g. data Foo to declare an immutable class, <data T> to put a constraint on a generic parameter, and DataList instead of ImmutableList. (value instead of data would also be fine).
• Consider providing better defaults, such as implicit final and non-nullability by default.
• Consider providing operator== and hashCode; they would be so so useful in a lot of code.

[leafpetersen]

@yjbanov Thanks for the summary. I'm don't want to promise that we can cover all of those points, but that's a great list to aim for.

Question in light of the example from @aam above. Do you see sharing data between isolates being valuable (as opposed to just being able to transfer data from one isolate to the other). For example, I can imagine an architecture in which one isolate does a functional update on the render tree (that is, treats it like a persistent data structure, allocating new objects for the changed part), and then passes off the pointer to the "updated" tree to another isolate for rendering, and then repeats.

Would you expect to take advantage of something like that? Or is one-time transfer of data (assuming near zero-cost transfer) the sweet spot?

[davidmorgan]

Very excited about where this leads :)

Re: immutable collections. Please note that https://github.com/google/built_collection.dart is already heavily used--e.g. it is referenced in google3 4.4x more than package:collection. (I won't share absolute numbers here, they are easy enough to get).

So I think this proposal needs to contain a plan for built_collection; they should either be the same thing, or they should be compatible, or there should be a very easy migration path. Any disruption to this space risks causing a lot of churn.

I think compatible means at least that there's a way for a built_collection instance to count as Immutable. The provision of hashCode is going to cause issues here, see below.

Thoughts based on what we've seen with built_collection, and some comments on compatibility:

• ImmutableList implements List is a scary thing as it causes failures at runtime. built_collection chose to skip implementing List and implement just Iterable, and this has worked well. One related thought, if we ever get a way to declare generic covariance/contravariance, at that point having a separate immutable interface will allow us to treat the generics correctly--we can't do that if we reuse List.
• Immutable collections should forbid null values. It's simpler, it's more efficient, and it's extremely rare that people want them.
• Comparison+hashing works well. It makes sense to cache the hash code which I think will be the biggest issue for compatibility with this proposal. If ImmutableList manages to solve this efficiently and still remain immutable then we can presumably just delegate to it. Otherwise we're going to hit problems.
• Switching BuiltList to wrap ImmutableList without making it slower--causing twice as much copying--is not possible with the current proposal. Currently, BuiltList copies when it turns into ListBuilder but does not copy when it turns back into BuiltList; if any further modifications are made to the builder then at that point an additional copy is made. This is what the proposal is trying to make efficient with the part about the instance escaping--but what is currently in the proposal is not sufficient. We would need something more explicit.
• It might be worth calling out in the proposal if the intention is that they should replace mutable collections whenever collections are passed around, or whether they are for specialist use. To be used everywhere they should be as easy to "update" as possible. If they need to be as convenient as the mutable collections, then the builder pattern works well; if this doesn't make it into the core then hopefully it's possible for a library like built_collection to provide it in a reasonably friction-free way.

Re: immutable value types. Similar story here: https://github.com/google/built_value.dart is already in this space and heavily used. Inside google3 it accounts for just over half of the classes that define hashCode (ignoring the SDK).

Again, we're going to need a plan for what happens to built_value. I think the right outcome is that it's possible to create built_value instances that count as immutable.

The biggest part of this will be making it so built_collection instances can count as immutable.

Beyond that, the only awkward point I see is that built_value has a feature which allows you to mark getters as @memorized, causing them to be cached on first use. We wouldn't be able to support that and be immutable at the same time. This sounds like a feature request for the proposal, or maybe a followup--it makes your immutable types significantly more powerful. It could also be considered a more general form of the request to have collections cache their hash codes.

Finally some general thoughts on immutable classes:

• +1 for operator== and hashCode. FWIW, built_value does not usually cache these; but it has been requested as a feature, it would be nice to be able to support it.
• +1 for more focus on non-nullability, although people still want a way to make null be allowed, including primitives; search our code for @nullable, which is how built_value marks this, to see this in action.
• on updates, again, I like the builder pattern; see use of the rebuild method in our code for examples; and in particular built_value uses nested builders to give a very concise way to write updates to something deeply nested in your object structure; it also makes it efficient (only rebuilds along the path to the root); as far as I can see, though, all this can live happily outside the core language support. I might even argue for not adding something like a copy method ... it's not as good as what built_value provides, but it does cover some of the use cases, so it will reduce built_value use :)

Those are my initial thoughts--thanks for listening :)

Please reach out to me if you need anything specific on how this proposal interacts with existing code, I'll be happy to explore options, write docs, point to examples. I'll anyway keep an eye on the issue and try to volunteer anything that seems relevant.