[Manifesto] Ownership

John_McCall · March 7, 2017, 7:48pm

1: Collection Composition

As much as the high-level picture is focused on safety, I’d just like to request a strong focus on making sure the eventual ownership system addresses the common issues like avoiding copies when mutating through optionals, or when nesting collections, and so on.

Avoiding copies is basically the entire core of the proposal. The interaction with safety is that sometimes copies are necessary to avoid memory unsafety, and this proposal recommends an approach that minimizes that.

Thanks for the extend reply and sorry for my own belated reply.

What motivated me to ask for more focus on the common cases was that it was unclear from reading the proposal whether the `inout` binding--as used in `for inout`--could be used with `if`: in other words, we currently have `if let` and `if var`, but will we have `if inout` under this proposal?

I am embarassed to admit I honestly couldn't tell if the proposal didn't contain any examples of `if inout` due to (a) the capability following trivially from the rest of the proposal or (b) the capability falling outside the scope of the proposal.

I just didn't think about it. "if inout" is quite supportable under the basic model.

The technical obstacle to this is just that, so far, we've tried to make language features like for-loops use formal protocols.

An iteration protocol is going to have requirements like this:
  generator iterate() -> Element
  mutating generator iterateMutable() -> inout Element
But there's no valid substitution that makes '(Key, inout Value)' equal either 'Element' or 'inout Element'. So we'd have to do some special to make this work.

That said, no, there's no intrinsic technical reason this can't be made to work.

The explanation of wanting to stick to formal protocols makes perfect sense. I don’t think this should be a show-stopper, but I do think it’ll be a common request for a subsequent enhancement.

Even in the interim it seems quite feasible to emulate the capability in any concrete case with enough willingness to crank out boilerplate; thus e.g. if someone truly needs `for (index, inout value) in collection.enumerated()` or `for (a, inout b) in zip(as,bs)` it isn’t as if they’re entirely stuck.

I actually spent some more time thinking about it after I wrote it, and there are some nice things that come out of abandoning formal protocols here. You could allow generators to be overloaded, not by name, but by the "inout-shape" of their return value, so that something like
  for (a, inout b) in ...
would specifically look for a generator like:
  generator() -> (T, inout U)
etc.

Would it be valid write:
var iter = foo.makeIterator()
inout x = iter.next()
If not, are special case `inout` returns really the right way to model this feature? It seems that a inout-map interface would be better as it doesn't require any special case language features.

Or am I misunderstanding, and `inout` reruns in the general case are supported by this proposal? If so, `inout` seems like a poor name.

inout returns are not supported, for reasons covered at length in the manifesto. The specific sub-proposal for for loops is to base them around co-routines, for which inouts would be supported, and for which the "inout" name is somewhat more appropriate (because, you might say, exclusive access to the value in the variable yielded inout is temporarily passed into the caller of the co-routine and then back out to the co-routine). Co-routine yields are quite different from returns in a number of ways.

John.

···

On Mar 7, 2017, at 1:28 PM, jaden.geller@gmail.com wrote:
On Mar 7, 2017, at 10:02 AM, John McCall via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Mar 7, 2017, at 11:47 AM, plx via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Feb 27, 2017, at 11:08 AM, John McCall <rjmccall@apple.com <mailto:rjmccall@apple.com>> wrote:

On Feb 25, 2017, at 11:41 AM, plx via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

3: Mutable Views

It's not sensible to have a type that conditionally conforms to a protocol based on context.

That did indeed seem like a big ask!

I’ll put in an early request to consider

  @moveonly {
    struct File { }
  }

…(or @scope(moveonly) or @context(moveonly) or @dialect(moveonly), etc.).

It’s confusing that `moveonly` essentially applies “inward”—it flags the code *within* a scope as using different assumptions, etc.—in contrast to most of the modifiers like `open`, `final`, `mutating`, etc., apply “outward” (by e.g. describing how visible the code in the scope is from other scopes, etc.).

An interesting idea.

However, the requirements of MutableCollection are all 'mutating', so you can't actually use them unless you have a mutable value. So the way to fit what you're asking for into the ownership proposal is to make sure that clients of your view type only have a mutable value when the base was mutable, and the easiest way of getting that is to have the view be vended as storage rather than a return value. If you think about it, a mutable view can't be an independent value anyway, because if code like this could work:

  var grid = ... // note that this is mutable
  var view = grid.traversal(from: p, following: m) // should return a mutable view by design, right?
  view.mutate() // reflected in grid, right?

then it completely destroys the value-type properties of 'grid', because 'view' should really be an independent value.

Without belaboring this, the point is indeed to “destroy the value-type properties of `grid`”, while trying to keep things “safe” by quarantining `view`—and the temporary relaxation of value semantics its existence implies—to a specific scope; thus under the status quo the use-site looks like this:

  var grid = // note that this is mutable
  // also note that `mutatingTraversal` is a `mutating` method...
  grid.mutatingTraversal(from: c, following: m) {
    (inout view: MutableGrid2DTraversal<T>) -> Void
    in
    // ^ this is the only public method that vends `MutableGrid2DTraversal<T>`, and
    // `MutableGrid2DTraversal<T>` has no public constructors, thus `view` is
    // “quarantined” to this scope unless we actively attempt to leak `view`...
    view.mutate()
  }

…which currently has two major drawbacks:

- (a) lots of code duplication: the immutable `Grid2DTraversal<T>` and the mutable `Mutable2DTraversal<T>`
- (b) the “quarantine” isn’t airtight, in that there are at least these three ways a `view` could escape:

  var grid = // …
  var leakedView: MutatingGrid2DTraversal<T>? = nil
  var otherLeakedView = grid.mutatingTraversal(from: c, following: m) {
    (inout view: MutableGrid2DTraversal<T>) -> MutableGrid2DTraversal<T>
    in
    view.mutate()
    // leak #1:
    leakedView = view
    // leak #2:
    self.liveDangerously(leaking: view)
    // leak #3:
    return view
  }

…which imho makes it fair to say “the above approach *encourages* ‘safe’ usage, but can’t *prevent* unsafe usage”.

Under the ownership proposal nothing changes for drawback (a): to stick with the design and behavior sketched above requires distinct types and thus a lot of duplicate or near-duplicate boilerplate.

Only if you insist that you want a traversal to behave like a linked value even when everything about the traversing code makes it look independent. You're trying to shoe-horn in a kind of reference semantics where it doesn't belong.

Look, your goals are an exact match for the basic ownership design here. You have a type (the grid), it has a thing you can get from it (the traversal), that thing has both mutating and non-mutating operations, you want the mutating operations to be usable if and only if the original value was mutable, you don't want to allow simultaneous accesses to the original value while you have the thing, etc. These are exactly the properties you get by default if starting a traversal is just protecting a component of the value via a property/subscript access. Just accept that a let or var containing a traversal is an independent value.

Drawback (b) seems to fare better under the ownership proposal, provided that I make `MutatingGrid2DTraversal` a non-Copyable type; at least AIUI making `MutatingGrid2DTraversal` non-Copyable would effectively close leaks #1, #2, and #3, b/c:

- I would explicitly have to write e.g. `leakedView = move(view)` (a *very* unlikely accident)
- I would also have to supply a "replacement value” for `view` by the end of the scope (impossible due to lack of public constructors)

…at least if I understand correctly. Is this accurate? If accurate, how likely would it be that “failed to provide replacement value for `view` after move” would get caught at compile time?

It would be guaranteed to get caught at compile time.

This leaking issue is something I didn't get into in the manifesto, but we've actually thought a fair amount about it. Generalized accessors come up a lot in the context of array slices, which share a lot of similar properties with your scenario. With array slices, we have some additional problems:
  - arrays are copy-on-write values, and the original array does need to keep its buffer alive while a slice is being accessed
  - slices need to be usable as independent (and copyable) value types; thus at least sometimes they need to have a strong reference to the buffer
  - forming a mutable slice really shouldn't form a second strong reference to the buffer because then mutations of the slice will trigger a buffer copy
The current line of thinking is that maybe we can have explicit copy and move hooks so that e.g. a projected slice could hold an unowned reference to the buffer which would be promoted to a strong reference on move/copy. But that's a lot of complexity, and I don't think it helps you that much.

Your analysis is correct: making the type move-only solves many of these problems, but not all of them because of the ability to move values aside. Rust has a concept of types that can't even be moved, I think; maybe we need to explore that.

John.

Thanks again for providing such detailed clarifications about this proposal.

The proposal suggests doing this instead with storage, so that the view is logically a (mutable) component of the grid. So on the use side:

  var grid = ...
  inout view = &grid[traversingFrom: p, following: m]
  view.mutate()

and on the declaration side:

  struct Grid2D<T> {
    subscript(traversingFrom corner: Grid2DCorner, following motion: Grid2DMotion) -> Grid2DTraversal<T> {
      read {
        yield Grid2DTraversal(...)
      }
      modify {
        var traversal = Grid2DTraversal(...)
        yield &traversal
        // ensure changes were applied here
      }
    }
  }

If you feel that the aesthetics of this leave something to be desired, that's a totally reasonable thing to discuss.

John.

Anyways, it’s not clear to me, personally, whether or not the above is within the scope of any likely, concrete ownership system that’d follow from the manifesto or not…but if at all possible I’d prefer the eventual ownership system make it reasonable—and reasonably safe—to implement “small-c ‘collection’s that can safely-and-efficiently expose various *mutable* views as big-C `Collection`s”.

Apologies if all of the above considerations have answers that follow trivially from the manifesto; it’s just unclear personally whether the features described in the manifesto would work together to allow something like the above to be implemented more-reasonably than currently the case.

On Feb 17, 2017, at 11:08 AM, John McCall via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Feb 17, 2017, at 4:50 AM, Adrian Zubarev <adrian.zubarev@devandartist.com <mailto:adrian.zubarev@devandartist.com>> wrote:
Hi John, would you mind creating a markdown document for this manifesto in https://github.com/apple/swift/tree/master/docs? :)

Yes, it should go in the repository. That commit is pending, but the in meantime, you can see the document properly rendered at:
  https://github.com/rjmccall/swift/blob/4c67c1d45b6f9649cc39bbb296d63663c1ef841f/docs/OwnershipManifesto.md

John.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution