Proposed Language Rules for Expiring Values

[mppf]

I see 3 areas that are possible related

• rules for when deinit is called rules for when deinit is called #11534 I/O and Destroying temporaries at the end of the block vs end of statement #11492
• eliding copies from expiring values issues with eliding copies from expiring values #9490 How can we optimize initialization of arrays with explicit runtime type from expiring values? #9421
• ownership transfer from non-nil owned values https://github.com/Cray/chapel-private/issues/125, see also Missing nil checking upon ownership transfer #13600

In all of these cases, I think the language could benefit from a concept for an expiring value / dead value. This issue shows some examples for each case, discusses two proposals for language rules, and investigates these proposals using examples.

As of 10/1/2019, there is some support for Option 2 in preference to Option 1 because it solves more of the current problems.

---

Motivating Examples

Motivating examples for placement of deinit on records

I/O deinit example

In the following example (from #11492), one would like the channel created by tmp.writer() to be closed before the channel created by tmp.reader() is created. Otherwise, the reader cannot access data written by the writer. However the current behavior is to destroy all local variable records at the end of the block in which they are declared. The result is that tmp.reader().read(B) does not find any written data in the file.

proc main() {
  var tmp = opentmp();

  var A = [1,2,3,4];
  var B:[A.domain] int;

  tmp.writer().write(A);
  tmp.reader().read(B);
}

Slice deinit example

In contrast, the situation with array slices is the opposite, where the temporary needs to be destroyed at the end of the block and not before:

proc makeArray() {
  var A:[1..100] int;
  return A;
}
proc main() {
  ref slice = makeArray()[1..10];
  // point 1
  writeln(slice);
  writeln();
  // point 2
}

In this example, there is a reference to a call-expression temporary storing the slice, which in turn refers to a call-expression temporary storing the whole array. As a result, the compiler may not deinitialize either the array or the slice array-view of it at point 1. It must perform this deinitialization after these are no longer used, at point 2.

Owned deinit example

proc main() {
  var instance: borrowed C = (new owned C(1)).borrow();
  // point 1
  writeln(instance);
  writeln();
  // point 2
}

Here, if the new owned value were deleted after that statement, instance would refer to freed memory.

#11534 contains more examples.

Motivating examples for eliding copies from expiring values

Desire for this has come up in user code with a pattern like

proc f() {
  var a: [1..n] int;
  forall i in a.domain {
    a[i] = i;
  }
  return new MyClass(a);
}

Here MyClass is storing an array and we would like its initializer to accept that array with in intent. In that event, we would like the array already constructed to "move" into the class field, rather than copying. The copy can be expensive if it is a distributed array.

Already, the compiler can eliminate copies in certain cases, such as var x = g().

Related issues are #9421 and #9490.

Motivating example for ownership transfer from non-nil owned values

Because of the role of type inference, it is easy to create variables that are non-nil owned. Simple patterns using these variables will lead to error if we cannot allow a variable of type owned MyClass to store nil, which is the current plan (per #12614). Such patterns are currently simply not checked, which is totally not type-safe and I expect to change.

class MyClass { var x: int; }
proc test() {
  var x = new owned MyClass(1);
  var y = x; // ownership transfer to y
  // end of statement mentioning x
}

class MyClass { var x: int; }
proc test() {
  var x = new owned MyClass(1);
  if something {
    passWithInIntent(x); // ownership transfer to formal argument
  }
}

Language Design Options

Option 1

From
#11534 (comment)

A local value is dead at the end of the block if it was created in a var/ref/const/const ref variable declaration and dead at the end of the statement otherwise. Globals continue to be destroyed at the end of the program's execution).

Pros:

• very easy to implement - the compiler could simply wrap each line in its own small BlockStmt.
• Similar to C++ and D (although C++ has explicit "move" semantics to work around the issue)

Cons:

• Does not help with eliding copies from expiring values
• Does not actually help with the ownership transfer from non-nil case
• Leads to more distinguishing between compiler temporaries and user variables that is ideal (one might expect f(g()) to work the same as var x = g(); f(x); ).
• Might require something like C++ std::move
• Certain programs that work now to be compilation errors (see store(x, makeOwnedC().borrow()); example below).

Option 2

In option 2, the compiler would consider the appearances of a local variable in the source code.

• If any of its uses are potentially capturing aliases according to the rule below, it would make the variable dead at the end of the block.
• Otherwise, it would be dead at the end of the last statement that mentioned that variable. Note that for an if conditional or a loop that contained a mention of the variable in its body, the variable would be dead after that if or the loop. Globals continue to be destroyed at the end of the program's execution.

A function call f(..., a, ...) is potentially capturing an alias to an argument a if the lifetime constraint or inferred lifetime constraint would allow:

• storing something with lifetime of a into another formal argument
• storing something with lifetime of a into an outer / global variable
• initializing a new user variable that refers to / borrows from a (e.g. ref x = a).

A function call g(..., b, ...) is potentially creating an alias to an argument b if the lifetime constraint or inferred lifetime constraint would allow:

• returning something with lifetime b

To determine if a variable v is potentially capture, the analysis would develop a set of potential aliases. Initially, the set consists the variable v only. The analysis would expand this set to include the results of any calls that create an alias, and proceed until this set does not change. Then it would consider calls mentioning members of this set to determine if any of them are potentially capturing.

Pros:

• Does not distinguish between user variables and expression temporaries (f(g()) works the same as var x = g(); f(x); ).
• Allows for eliding copies from expiring (user) values
• Helps with the ownership transfer from non-nil case
• Avoids the need for an idea like C++ std::move

Cons:

• More complex than Option 1
• May confuse C++ developers
• RAII lock pattern is more complex

Further Discussion and Examples Evaluating Each Option

Considering the Motivating Examples

I/O deinit example

proc main() {
  var tmp = opentmp();

  var A = [1,2,3,4];
  var B:[A.domain] int;

  tmp.writer().write(A);
  // point 1
  tmp.reader().read(B);
  // point 2
}

Under option 1 and option 2, the channel that results from tmp.writer() would be deinited (and flushed) at point 1, rather than at point 2 as it is today.

In Option 1, it is deinited at point 1 because the temporary was not in a variable declaration.

In Option 2, it s deinited at point 2 because channel.write() does not have the potential to save an alias (returns a bool, so can't save it that way; can't store the alias in other arguments or globals because there is no lifetime clause).

Slice deinit example

proc makeArray() {
  var A:[1..100] int;
  return A;
}
proc main() {
  ref slice = makeArray()[1..10];
  // point 1
  writeln(slice);
  writeln();
  // point 2
}

Option 1 would deinit the temporaries at point 1 because they are declared in a variable declaration statement. Option 2 would deinit the temporaries at point 2 because:

• the temporary storing makeArray() as captured by a slice (the slice borrows from the original array)
• the temporary storing the reference is captured by ref slice = ___.

Owned deinit example

proc main() {
  var instance: borrowed C = (new owned C(1)).borrow();
  // point 1
  writeln(instance);
  writeln();
  // point 2
}

Here Option 1 would destroy the temporary storing new owned C(1) at the end of the block (point 2) because it was in a variable declaration statement. Option 2 would also destroy it there because an alias to that temporary is created (and stored in instance).

Motivating examples for eliding copies from expiring values

class MyClass {
  var a;
  proc init(in a) {
    this.a = a;
  }
}
proc f() {
  var a: [1..n] int;
  forall i in a.domain {
    a[i] = i;
  }
  return new MyClass(a);
}

Option 1 does not allow for eliding the copy in this case. Option 2 can elide the copy. Even though the compiler might change the loop into something that includes references referring to particular elements, the analysis will see that none of these are potentially capturing. As a result, it could consider the array a dead at the time the new MyClass is constructed and then it could remove a copy.

Motivating example for ownership transfer from non-nil owned values

class MyClass { var x: int; }
proc test() {
  var x = new owned MyClass(1);
  var y = x; // ownership transfer to y
  // end of statement mentioning x
}

Option 1 does not help this case and so it would be a compilation error, since x: owned MyClass is non-nilable but it stores nil after the ownership transfer.

Option 2 would allow for it because init= for owned is not considered to capture an alias.

class MyClass { var x: int; }
proc test() {
  var x = new owned MyClass(1);
  if something {
    passWithInIntent(x); // ownership transfer to formal argument
  }
}

This is similar to the above case.

Further Interesting Examples

RAII Lock

Chapel doesn't have a C++-style RAII lock type and it's unclear if we will add that in the future. What would a C++-style RAII lock look like in Chapel? E.g.

{
   var lock = takeLock();
   // lock deinit function releases lock, so lock released at the end of this block
}

I personally do not like the way that the un-lock is hidden and would prefer something more explicit. Python with contexts and Java synchronized blocks come to mind as a good precedents. See #12306 for the general direction I prefer.

In any case an RAII lock can be directly supported by Option 1. For Option 2 we would need to either use a different lock strategy or use an attribute (see #7355) to communicate to the compiler that deinit for that type should not be moved.

store(x, makeOwnedC().borrow()

This example is more challenging for these analyses and comes from #11534 (comment)

class C {
  var x : int;

  proc deinit() {
    writeln("destroy: ", x);
  }
}

proc makeOwnedC() {
  return new owned C(5);
}

proc store(ref lhs : borrowed C, rhs : borrowed C) lifetime lhs = rhs {
  lhs = rhs;
}

proc main() {
  var x : borrowed C;
  writeln("---- before ----");
  store(x, makeOwnedC().borrow());
  // point 1
  writeln("---- after ----");
  writeln(x);
  // point 2
}

Should the temporary storing the result of makeOwnedC() be destroyed at point 1 or point 2?

In Option 1, it would be destroyed at point 1. This program would fail to compile due to lifetime checking errors.

In Option 2, it would be destroyed at point 2, because store is capturing a potential alias to it.

Option 2 Further Examples

This example shows how the lifetime clause interacts with the checking. Missing a lifetime clause on a function capturing into a global variable would lead to a compilation error. Once that lifetime clause is present, capturing is detected.

// What if R borrows?

record R {
  var x: borrowed object;
  proc init(arg: object) {
    this.x = arg;
  }
  proc init=(arg: R) {
    writeln("in init=");
    this.x = arg.x;
    // case 1: copy constructor copies pointer
    //         -> borrowed
    // case 2: copy constructor creates its own initialized memory
    //         -> pragma "owned" or literally use owned/shared
    //
    // (lifetime checker won't do anything for x: unmanaged object) 
  }
}

proc makeR(arg: object) {
  return new R(arg);
}

var global: borrowed object = new borrowed object();

proc capture(arg: R) {
  global = arg.x; // lifetime error
                  // to fix, i'd need a lifetime clause that says
                  // that lifetime arg >= global,
                  // which would cause Option 2 analysis to decide end-of-block
}

proc acceptRin(in arg: R) {
}

proc test() {
  var obj = new borrowed object();
  var tmp = makeR(obj);

  capture(tmp); // <- does it identify this capture?

  acceptRin(tmp); // copy

  writeln("The End");
  // tmp destroyed here
}
test();

One might ask - what happens if R stores unmanaged C ?

// What if R uses unmanaged?

class C {
  var x: int;
}
record R {
  var x: unmanaged C;
  proc init(arg: int) {
    this.x = new unmanaged C(arg);
  }
  // Supposing this type sometimes aliases other R
  // Normally such a type would need an isOwned flag or reference counts or something.
  proc init(arg: unmanaged C) {
    this.x = arg;
  }
  proc init=(arg: R) {
    writeln("in init=");
    this.x = new unmanaged C(arg.x.x);
  }
  proc deinit() {
    writeln("deleting");
    delete x; 
  }
}

proc makeR() {
  return new R(1);
}

var global: unmanaged C = new unmanaged C(1);

proc captureA(arg: R) {
  global = arg.x;  // unmanaged, so no lifetime error
}

proc captureB(ref lhs: unmanaged C?, rhs: R) {
  lhs = rhs.x; // unmanaged, so no lifetime error
}

proc test1() {
  var u: unmanaged C?;

  var tmp = makeR();
  captureA(tmp);
  captureB(u, tmp);
  // point 1 - tmp deleted here?

  writeln("The End ", u, global);

  // adding the following line would keep tmp from being deinited at point 1
  //   tmp;

  // point 2
}
test1();

The above code could communicate to the compiler that tmp needs to be deinited at point 2 by:

1. adding a later statement referring to tmp e.g. tmp; just before point 2
2. adding a lifetime clause to captureA or captureB to communicate to the compiler that tmp should have global scope

Note that such a type is also able to be misused even with Option 1:

proc test2() {
  var u: unmanaged C?;
  {
    var tmp = makeR();
    captureA(tmp);
    captureB(u, tmp);
    // tmp deleted here even with Option 1
  }

  writeln("The End ", u, global); // use after free
}
test2();

The situation might come up in the standard library with string.localize() and string.c_str(). Both of these return things that alias the original string. However it would be nice for the lifetime checker to find misuses of these, so 2. above would be a preferred. We would want to do that even if we chose Option 1, so I don't think it's asking a lot to do it to support Option 2.

What do other languages do?

• In C++, user variables are destroyed at the end of their block, and not before. A C++ programmer would probably say that doing otherwise would interfere with RAII.
• In Rust, user variables are destroyed when they are dropd explicitly or when they reach the end of their block. Note that the Rust compiler actually reasons about drops at runtime because a variable could be conditionally initialized. There was some discussion about eager drops based only upon compile-time information in Allow Eager Drops rust-lang/rfcs#239 but this approach was not chosen. The reasons were that it interferes with RAII and that it can make writing unsafe code harder. These tradeoffs were not seen as "worth it" when the only benefit described was removing the need for some stack-allocated drop flags.

[mppf]

See PRs #14691 and #14817 for further refinements of the analysis based upon implementation experience. PR #14691 in particular defines "last mention point" to be a statement in the same block as the declaration (at least for now - but see #14749).

[mppf]

PR #15041 implements a simpler rule for deinit points that enables this program to behave as originally expected.

A variable is dead:

• after copy elision if it occurred (after the last mention is
  used to copy-initialize a variable or in intent argument)
• for the results of nested call expressions not involved in initializing
  a user variable or reference after the end of the statement
• otherwise, at the end of the scope in which it is declared