f9c8b5e93d
This PR fixes theoretical leaks in the handling of `Array.get!Internal`
in the code generator.
Currently, the code generator assumes that the value returned by
`get!Internal` is derived from the
`Array` argument. However, this does not generally hold up as we might
also return the `Inhabited`
value in case of an out of bounds access (recall that we continue
execution after panics by
default). This means that we sometimes convert an `Array.get!Internal`
to
`Array.get!InternalBorrowed` when we are not allowed to do so because in
the panic case the
`Inhabited` instance can be returned and if it is an owned value it is
going to leak.
The fix consists of adapting several components to this change:
1. `PropagateBorrow` will only mark the derived value as forcibly
borrowed if both the `Inhabited`
and `Array` argument are forcibly borrowed.
2. `InferBorrow` will do the same for its data flow analysis
3. The derived value analysis of `ExplicitRC` is extended from a derived
value tree to a derived
value graph where a value may have more than one parent. We only
consider a value borrowed if all
of its parents are still accessible. Then `get!Internal` is equipped
with both its `Inhabited`
and its `Array` parent.
These changes are sufficient for correctness on their own. However, they
are going to break
`get!Internal` to `get!InternalBorrowed` conversion in most places. This
happens because almost all
`Inhabited` instances are going to be constants. Currently reads from
constants yield semantically
owned values and thus block the `get!InternalBorrowed` conversion. We
would thus prefer for these
constants to be treated as borrows instead.
The owned return is implemented in two ways at the moment:
1. In the C code emitter we do not need to do anything as constants are
marked persistent to begin
with
2. In the interpreter whenever a constant is pulled from the constant
cache it is `inc`-ed and then
later `dec`-ed somewhere (potentially using a `dec[persistent]` which is
a no-op in C)
This PR changes the semantics of constant reads to instead be borrows
from the constant (they can be
cutely interpreted as "being borrowed from the world"). This enables
many `get!Internal` to have
both their arguments be marked as borrowed and thus still converted to
`get!InternalBorrowed`. Note
that this PR does not yet change the semantics of the interpreter to
account for this
(it will be done in a part 2) and thus introduces (very minor) leaks
temporarily.
Furthermore, we observed code with signatures such as the following:
```lean
@[specialize]
def foo {a : Type} [inst : Inhabited a] (xs : Array a) (f : a -> a -> Bool) ... :=
...
let x := Array.get!Internal inst xs i
...
```
being instantiated with `a := UInt32`. This poses a challenge because
`Inhabited` is currently
marked as `nospecialize`, meaning that we are sometimes going to end up
with code such as:
```
def foo._spec (inst : UInt32) (xs : @&Array UInt32) ... :=
...
let inst := box inst
let x := Array.get!Internal inst xs i
dec inst
...
```
Here `xs` itself was inferred as borrowed, however, the `UInt32`
`Inhabited` instance was not
specialized for (as `Inhabited` is marked `nospecialize`) and thus needs
to be boxed. This causes
the `inst` parameter to `get!Internal` to be owned and thus
`get!InternalBorrowed` conversion fails.
This PR marks `Inhabited` as `weak_specialize` which will make it get
specialized for in this case,
yielding code such as:
```
def foo._spec (xs : @&Array UInt32) ... :=
...
let inst := instInhabitedUInt32
let inst := box inst
let x := Array.get!Internal inst xs i
dec inst
...
```
Fortunately the closed term extractor has support for precisely this
feature and thus produces:
```
def inst.boxed_const :=
let inst := instInhabitedUInt32
let inst := box inst
return inst
def foo._spec (xs : @&Array UInt32) ... :=
...
let inst := inst.boxed_const
let x := Array.get!Internal inst xs i
...
```
As described above reads from constants are now interpreted as borrows
and thus the conversion to
`get!InternalBorrowed` becomes legal again.
177 lines
5 KiB
Text
177 lines
5 KiB
Text
module
|
||
|
||
public section
|
||
|
||
|
||
|
||
/--
|
||
trace: [Compiler.explicitRc] size: 1
|
||
def test1._closed_0 : obj :=
|
||
let _x.1 := "";
|
||
return _x.1
|
||
[Compiler.explicitRc] size: 7
|
||
def test1 @&xs : obj :=
|
||
let _x.1 := test1._closed_0;
|
||
let _x.2 := 0;
|
||
let _x.3 := Array.get!InternalBorrowed ◾ _x.1 xs _x.2;
|
||
let _x.4 := 1;
|
||
let _x.5 := Array.get!InternalBorrowed ◾ _x.1 xs _x.4;
|
||
inc _x.3;
|
||
let _x.6 := String.append _x.3 _x.5;
|
||
return _x.6
|
||
[Compiler.explicitRc] size: 2
|
||
def test1._boxed xs : obj :=
|
||
let res := test1 xs;
|
||
dec[ref] xs;
|
||
return res
|
||
-/
|
||
#guard_msgs in
|
||
set_option trace.Compiler.explicitRc true in
|
||
def test1 (xs : Array String) := xs[0]! ++ xs[1]!
|
||
|
||
/--
|
||
trace: [Compiler.explicitRc] size: 7
|
||
def test2._redArg @&inst.1 @&xs f : tobj :=
|
||
let _x.2 := 0;
|
||
let _x.3 := Array.get!InternalBorrowed ◾ inst.1 xs _x.2;
|
||
let _x.4 := 1;
|
||
let _x.5 := Array.get!InternalBorrowed ◾ inst.1 xs _x.4;
|
||
inc _x.5;
|
||
inc _x.3;
|
||
let _x.6 := f _x.3 _x.5;
|
||
return _x.6
|
||
[Compiler.explicitRc] size: 3
|
||
def test2._redArg._boxed inst.1 xs f : tobj :=
|
||
let res := test2._redArg inst.1 xs f;
|
||
dec[ref] xs;
|
||
dec inst.1;
|
||
return res
|
||
[Compiler.explicitRc] size: 1
|
||
def test2 α @&inst.1 @&xs f : tobj :=
|
||
let _x.2 := test2._redArg inst.1 xs f;
|
||
return _x.2
|
||
[Compiler.explicitRc] size: 3
|
||
def test2._boxed α inst.1 xs f : tobj :=
|
||
let res := test2 α inst.1 xs f;
|
||
dec[ref] xs;
|
||
dec inst.1;
|
||
return res
|
||
-/
|
||
#guard_msgs in
|
||
set_option trace.Compiler.explicitRc true in
|
||
def test2 [Inhabited α] (xs : Array α) (f : α → α → α) := f xs[0]! xs[1]!
|
||
|
||
/--
|
||
trace: [Compiler.explicitRc] size: 4
|
||
def test3._lam_0 @&xs i : UInt8 :=
|
||
let _x.1 := USize.toNat i;
|
||
let _x.2 := Array.size ◾ xs;
|
||
let _x.3 := Nat.decLt _x.1 _x.2;
|
||
dec _x.1;
|
||
return _x.3
|
||
[Compiler.explicitRc] size: 5
|
||
def test3._lam_0._boxed xs i : tagged :=
|
||
let i.boxed := unbox i;
|
||
dec i;
|
||
let res := test3._lam_0 xs i.boxed;
|
||
dec[ref] xs;
|
||
let r := box res;
|
||
return r
|
||
[Compiler.explicitRc] size: 21
|
||
def test3 @&xs : obj :=
|
||
let _x.1 := test1._closed_0;
|
||
jp _jp.2 _y.3 : obj :=
|
||
let _x.4 := 1;
|
||
let _x.5 := test3._lam_0 xs _x.4;
|
||
cases _x.5 : obj
|
||
| Bool.false =>
|
||
let _x.6 := outOfBounds._redArg _x.1;
|
||
let _x.7 := String.append _y.3 _x.6;
|
||
dec _x.6;
|
||
return _x.7
|
||
| Bool.true =>
|
||
let _x.8 := Array.ugetBorrowed ◾ xs _x.4 ◾;
|
||
let _x.9 := String.append _y.3 _x.8;
|
||
return _x.9;
|
||
let _x.10 := 0;
|
||
let _x.11 := test3._lam_0 xs _x.10;
|
||
cases _x.11 : obj
|
||
| Bool.false =>
|
||
let _x.12 := outOfBounds._redArg _x.1;
|
||
goto _jp.2 _x.12
|
||
| Bool.true =>
|
||
let _x.13 := Array.ugetBorrowed ◾ xs _x.10 ◾;
|
||
inc _x.13;
|
||
goto _jp.2 _x.13
|
||
[Compiler.explicitRc] size: 2
|
||
def test3._boxed xs : obj :=
|
||
let res := test3 xs;
|
||
dec[ref] xs;
|
||
return res
|
||
-/
|
||
#guard_msgs in
|
||
set_option trace.Compiler.explicitRc true in
|
||
def test3 (xs : Array String) := xs[(0 : USize)]! ++ xs[(1 : USize)]!
|
||
|
||
|
||
/--
|
||
trace: [Compiler.explicitRc] size: 4
|
||
def test4._redArg._lam_0 @&xs i : UInt8 :=
|
||
let _x.1 := USize.toNat i;
|
||
let _x.2 := Array.size ◾ xs;
|
||
let _x.3 := Nat.decLt _x.1 _x.2;
|
||
dec _x.1;
|
||
return _x.3
|
||
[Compiler.explicitRc] size: 5
|
||
def test4._redArg._lam_0._boxed xs i : tagged :=
|
||
let i.boxed := unbox i;
|
||
dec i;
|
||
let res := test4._redArg._lam_0 xs i.boxed;
|
||
dec[ref] xs;
|
||
let r := box res;
|
||
return r
|
||
[Compiler.explicitRc] size: 20
|
||
def test4._redArg @&inst.1 @&xs f : tobj :=
|
||
jp _jp.2 _y.3 : tobj :=
|
||
let _x.4 := 1;
|
||
let _x.5 := test4._redArg._lam_0 xs _x.4;
|
||
cases _x.5 : tobj
|
||
| Bool.false =>
|
||
let _x.6 := outOfBounds._redArg inst.1;
|
||
let _x.7 := f _y.3 _x.6;
|
||
return _x.7
|
||
| Bool.true =>
|
||
let _x.8 := Array.ugetBorrowed ◾ xs _x.4 ◾;
|
||
inc _x.8;
|
||
let _x.9 := f _y.3 _x.8;
|
||
return _x.9;
|
||
let _x.10 := 0;
|
||
let _x.11 := test4._redArg._lam_0 xs _x.10;
|
||
cases _x.11 : tobj
|
||
| Bool.false =>
|
||
let _x.12 := outOfBounds._redArg inst.1;
|
||
goto _jp.2 _x.12
|
||
| Bool.true =>
|
||
let _x.13 := Array.ugetBorrowed ◾ xs _x.10 ◾;
|
||
inc _x.13;
|
||
goto _jp.2 _x.13
|
||
[Compiler.explicitRc] size: 3
|
||
def test4._redArg._boxed inst.1 xs f : tobj :=
|
||
let res := test4._redArg inst.1 xs f;
|
||
dec[ref] xs;
|
||
dec inst.1;
|
||
return res
|
||
[Compiler.explicitRc] size: 1
|
||
def test4 α @&inst.1 @&xs f : tobj :=
|
||
let _x.2 := test4._redArg inst.1 xs f;
|
||
return _x.2
|
||
[Compiler.explicitRc] size: 3
|
||
def test4._boxed α inst.1 xs f : tobj :=
|
||
let res := test4 α inst.1 xs f;
|
||
dec[ref] xs;
|
||
dec inst.1;
|
||
return res
|
||
-/
|
||
#guard_msgs in
|
||
set_option trace.Compiler.explicitRc true in
|
||
def test4 [Inhabited α] (xs : Array α) (f : α → α → α) := f xs[(0 : USize)]! xs[(1 : USize)]!
|