Taking ownership of value captured by a lambda env is unsafe

[TimDeve]

The following example will result in a double free:

(defn main []
  (let [s @"String"
        f (fn [] s)]
    (ignore (f))))

The reason is that returning the value s means the consumer of the lambda will take ownership of it, so when it is done with the value it will call delete on it, but the value is still captured in the env of the lambda so when the env gets deleted it tries to free something already free-ed.

For the same reason calling a function that take ownership in the lambda will result in the same problem:

(defn main []
  (let [s @"String"
        f (fn [] (ignore s))]
    (f)))

[TimDeve]

Two solutions come to mind: the simplest is to disallow taking ownership of env values in lambdas. Alternatively we could remove the value from the env when it's consumed and only allow to call these lambda once, but it seems that would be quite complex to implement.

[scolsen]

Two solutions come to mind: the simplest is to disallow taking ownership of env values in lambdas. Alternatively we could remove the value from the env when it's consumed and only allow to call these lambda once, but it seems that would be quite complex to implement.

The second solution would be "linear (or affine if we permit 0 usages) lambdas" and would probably be more robust. As mentioned in some other issues, I think this would mostly entail tracking linearity dependencies across values lexically referenced in multiple scopes. You could conceive as linearity/ownership as a transitive property, for things that take ownership of a reference via closure e.g. lambdas that capture some linear value can only be used once, structs that capture some linear value can only have that field referenced once, etc. and the lifetime of the captured thing should be incremented

another way to talk about this is that the lambda in this case "leaks" s by providing a means of accessing it beyond its assigned scope/lifetime. The most intuitive behavior would be for the linearity to be "transferred" to the lambda in the first case, (you can only call it once).

as a rough sketch, we could analyze this as:

[s @"String"<lt=1>
  f (fn [] s <lt=2>) <lt=1>

where a reference capture occurs iff the same value e.g. s is assigned a higher lifetime in a subscope, capture wouldn't occur, for example when:

[s @"String"<lt=1>
  t s <lt=1> <lt=1>

since the lifetime assignments for all instances of s are equal.

In the case of a capture, where some lifetime assignment greater than another lifetime assignment exists, we do not perform a deletion, but instead only add the dependency; e.g.

START_SCOPE_1
s @"String" ;; assign s.lifetime = 1
f (fn [] s <lt=2>) ;; assign f.lifetime = 1; s.lifetime++; f.dependent = s
END_SCOPE_1
;; check lifetimes:
;;     s.lifetime--; s.lifetime = 1; do nothing.
;;     f.lifetime--; -- delete f; s.lifetime--; delete s.

[TimDeve]

Yes, affine FnOnce-like lambdas is what I had in mind.

[scolsen]

Been thinking about this a bit more.

In the current implementation we store the env as a struct ty, so its deleter is the same as that of a struct (it'll just call delete on all members unless they are not isManaged). The issue here is: we can't just remove the capture from the env, because then the lambda doesn't have access to it. Unfortunately, since we only determine deletions by types, we'll always wind up calling a deletion on the capture when we delete the lambda's env (also necessary).

The most robust solution would probably be to introduce a proper linear type that, similar to refs, includes a lifetime. A more adhoc solution is to just tag the captured variables with an additional flag that indicates whether or not they should be deleted, which effectively "overrides" the default behavior we currently use for finding deleters for types.

We could also introduce a separate lambda type, like FnOnce that behaves a bit differently.

In terms of the current implementation, simply disallowing returning captured memory would have the least impact. We could restrict lambda captures to references only.

[scolsen]

I think only allowing reference captures might be the best approach w.r.t the current implementation. We already correctly track reference lifetimes:

(defn foo [] 
  (let [s @"foo"
          f (fn [] &s)])) ; error

(defn foo [] 
  (let [s @"foo"
          f (fn [] @&s)])) ; OK

Is there any use case that we'd have to permit ownership taking captures for?

EDIT: We also correctly catch the case:

(defn foo [] (let [s @"foo" f (fn [] &s)] f))
(defn bar [] ((foo)))
The reference '(defn bar [] ((foo)))' (depending on the variable '_5') isn't alive at line 6, column 2 in 'REPL'. at REPL:6:2.

Allowing for a "move and capture" in a robust way would require introducing a proper Linear Type kind that includes lifetime analysis for the linear values as we do with Refs currently, so it'd take some work. The current system is also simpler. I guess adding this restriction means you can't write a lambda that has a an allocation-free non-ref capture, but it's not impossible. You'd only have to convert a value to a pointer and then manually manage the memory. Since this is maybe an advanced use case anyway, perhaps that's OK?