[borrow v2] Move borrow semantics v2 (type checker only)

[wrwg]

This PR is a first attempt towards implementing borrow semantics v2 for Move. In a nutshell, we implement the capability that storage references (als call static references) can (a) travel upwards the call stack and (b) leave module boundaries.

For background, it is currently not possible in Move to write a function fun my_borrow(..): &R { borrow_global<R>(...) }. Instead the result of borrow_global and borrow_global_mut can only be passed downwards the stack. This is a strong restriction regards the ability to factorize code. For example, one cannot write any helper functions to access global storage easily.

In this PR we avoid the complexity of full Rust style lifetimes and instead evolve the existing acquires concept of Move. The acquires R annotation on functions is already needed to declare that a function accesses global storage. We now allow functions which acquire R to potentially return &R or &mut R:

fun my_borrow(a: address): &R acquires R {
  borrow_global<R>(a)
}

On caller side of my_borrow, we can see that the function returns a reference to resource storage and has no incoming reference, henceforth a borrow edge is derived which notes that R is in fact derived from storage. This mechanism propagates upwards the call stack.

We also allow storage references to travel outside of module boundaries. This extends the acquires mechanism from local structs to imported structs. Currently, acquires for calls to other modules does not need to be considered because references to resources managed by thiose modules cannot exist. This is kept as the default behavior, but a user can mark a struct with the attribute #[open_struct] to indicate that references to it in storage can leave the module, in which cause acquires need to be used for external calls.

In addition to the #[open_struct] attribute, this PR introduces a new attribute #[no_borrow(param1, ..., paramn)] which allows to exclude an input borrow for implicitly creating a borrow edge. Without this, we wouldn't be able to describe for instance functions as the following:

#[no_borrow(r)]
fun reader_ref<T>(r: &ReaderRef<T>): &T acquires T { borrow_global<T>(r.addr) }

Here the parameter r is not a borrowing root for &T, instead we want to express that &T is from storage. Without the no_borrow attribute this would not be possible.

[chen-robert]

@wrwg Followup from some of our previous conversations. The borrow checker argument generally makes sense, but some potential complexities:

I think as a consequence of this change we'd need to add additional information to the file format for more complex linking relationships. For example, linking against a function with or without no_borrow changes the semantics of verification. acquires information (for only open structs?) would probably also need to be embedded somehow.

It also seems like this would require changes in the compatibility checker. For example, adding or removing acquires of open structs would no longer be a compatible change. Adding or removing #[open_struct] or #[no_borrow] also seems unacceptable.

There probably also needs to be additional validation for no_borrow.

All of this adds quite a bit of complexity. I wonder if it makes sense to treat everything as a Rust Rc and do reference management at runtime. I believe this already happens in some places such as move_from.

[wrwg]

@wrwg Followup from some of our previous conversations. The borrow checker argument generally makes sense, but some potential complexities:

I think as a consequence of this change we'd need to add additional information to the file format for more complex linking relationships. For example, linking against a function with or without no_borrow changes the semantics of verification. acquires information (for only open structs?) would probably also need to be embedded somehow.

It also seems like this would require changes in the compatibility checker. For example, adding or removing acquires of open structs would no longer be a compatible change. Adding or removing #[open_struct] or #[no_borrow] also seems unacceptable.

There probably also needs to be additional validation for no_borrow.

All of this adds quite a bit of complexity. I wonder if it makes sense to treat everything as a Rust Rc and do reference management at runtime. I believe this already happens in some places such as move_from.

The Rc based approach could look as follows:

module std::rc {

    struct Rc<phantom T> has drop, copy { // hot potato, no store or key
        handle: u64 
    }

    struct RcMut<phantom T> has drop { // hot potato, no store or key
        handle: u64
    }

    public native fun borrow<T>(addr: address): Rc<T>;
    public native fun borrow_mut<T>(addr: address): RcMut<T>;

    public native fun ref<T>(rc: Rc<T>): &T;                  // Need to had special treatment in borrow checker
    public native fun ref_mut<T>(rc: RcMut<T>): &mut T;
}

[wrwg]

@wrwg Followup from some of our previous conversations. The borrow checker argument generally makes sense, but some potential complexities: I think as a consequence of this change we'd need to add additional information to the file format for more complex linking relationships. For example, linking against a function with or without no_borrow changes the semantics of verification. acquires information (for only open structs?) would probably also need to be embedded somehow. It also seems like this would require changes in the compatibility checker. For example, adding or removing acquires of open structs would no longer be a compatible change. Adding or removing #[open_struct] or #[no_borrow] also seems unacceptable. There probably also needs to be additional validation for no_borrow. All of this adds quite a bit of complexity. I wonder if it makes sense to treat everything as a Rust Rc and do reference management at runtime. I believe this already happens in some places such as move_from.

The Rc based approach could look as follows:

module std::rc {

    struct Rc<phantom T> has drop, copy { // hot potato, no store or key
        handle: u64 
    }

    struct RcMut<phantom T> has drop { // hot potato, no store or key
        handle: u64
    }

    public native fun borrow<T>(addr: address): Rc<T>;
    public native fun borrow_mut<T>(addr: address): RcMut<T>;

    public native fun ref<T>(rc: Rc<T>): &T;                  // Need to had special treatment in borrow checker
    public native fun ref_mut<T>(rc: Rc<T>): &mut T;
}

... and perhaps it should be a new builtin type, rc<T>.

[davidiw]

Maybe this was already the intent but ... Why not make these native function calls that can only be called within the module that defines the resource but then let them expose wrappers around ref and ref_mut?

You'll also need something that converts a Rc<T> -> &T and RcMut<T> -> &mut T.

[jolestar]

Like RC approach, but the #[no_borrow(r)] can resolve the lifetime issue #210