Idea: Discontinuous lifetime and its borrowing

language design
1

Currently, the lifecycle is continuous, and borrowing using the lifecycle must not survive beyond its lifespan (ignore dropck_eyepatch).

If we want to store a mutable pointer at the same time, we have to use RefCell or UnsafeCell to do this.

Now, propose a new lifetime form that will allow for discontinuous availability of its resources.

The method is to add a keyword with a tentative name of discontinuity, which will cause the following code to compile

let mut x = 1;
let a = #[discontinuity] &mut x;
let b = #[discontinuity] &mut x;
*a = 1;
*b = 2;

In the structure:

struct Foo<#[discontinuity] 'a> {
    r: &'a i32,
}

To dereference a discontinuous borrowing, it is necessary to prove that it is currently valid:

fn as_mut_ref<#[discontinuity] 's, 'a>(r: &'s mut i32) -> &'a mut i32
where 's: 'a {
    r
}

fn read_discontinuity_ref<#[discontinuity] 's, 'a>(r: &'s i32) -> i32
where 's: 'a {
    *r
}

fn read_discontinuity_ref<#[discontinuity] 's>(r: &'s i32) -> i32
where 's: 'function_call { // 'function_call: Is it valid when call function, or is it a different name?
    *r
}

Otherwise, it cannot be dereferenced:

fn err_read_discontinuity_ref<#[discontinuity] 's>(r: &'s i32) -> i32 {
    *r
//  ^^ Compile error: 's maybe dangling
}

Borrowing with discontinuous lifetime and 'static survival time.

fn box_any<#[discontinuity] 's>(r: &'s i32) -> Box<dyn Any + 'static> {
    Box::new(r)
}

Add a discontinuous lifetime constant of 'dangle, just like 'static, but the semantics are completely opposite.

fn dangle_ref<#[discontinuity] 's>(r: &'s i32) -> &'dangle i32 {
    r
}

fn dangle_ref2() -> &'dangle i32 {
    let x = 1;
     #[discontinuity] &mut x
}

Perhaps keywords and related language design still need to be discussed, but I believe discontinuous lifetime is complete.

It seems that quite a few people have asked me to provide a definition of discontinuous lifetime

Informally speaking:

  • A discontinuous lifetime is the sum of multiple ordinary lifetime.
  • Discontinuous lifetime borrowing can only be dereferenced when there is any one valid internal ordinary lifetime.
1 Like
2

What exactly are the rules you're proposing here?

What if x were a vector and it's reallocated via a before the b reference to an element is used?

You should probably include some examples that aren't trivially translatable to Cells.

1 Like
3 
struct B<#[discontinuity] 'a> {
    a: &'a mut Vec<i32>,
}
let mut a = Vec::new();
let b = B { a: #[discontinuity] &mut a };

a.push(1);
b.a.push(2);
a.push(3);

It is equivalent to using RefCell, but the latter introduces additional overhead (even if the compiler eliminates such simple situations)

struct B<'a> {
    a: &'a RefCell<Vec<i32>>,
}
let a = RefCell::new(Vec::new());
let b = B { a: &a };

a.borrow_mut().push(1);
b.a.borrow_mut().push(2);
a.borrow_mut().push(3);
4

Discontinuous borrowing refers to resources that may not be available now but may be available for certain time periods in the future. For variable mut borrowing, this does not violate the alias rule. Although there are multiple pointers to the same location at the same time, only one is still valid at the same time, but they can exhibit alternation.

5 
struct B<#[discontinuity] 'a> {
    a: &'a mut Vec<i32>,
}
let mut a = Vec::new();
let b: B<#[discontinuity] '1> = B { a: #[discontinuity] &mut a };

a.push(1);

// ’1 valid
b.a.push(2);
// '1 invalid

a.push(3);

// '1 valid again
b.a.push(2);
// '1 invalid again

 a.push(3);

The lifetime is the coloring on the Control flow graph. Now the coloring does not need to be continuous, and the creation of borrowing does not need to be currently valid.

6

I think scottmcm was referring to something like this:

let mut x = vec![1];
let a = #[discontinuity] &mut x;
let b: &mut [i32] = #[discontinuity] x.as_mut();
a.push(0); // reallocates storage
b[0] = 2; // what happens here? and what is the rule that makes it so?
6 Likes
7

A compile-time check literally can't be equivalent to the run-time check of a RefCell, as you can reduce the halting problem to "does this RefCell usage panic?".

So you need to explain exactly which cases would be covered (and preferably how that's implemented and why it's sound).

What's an example that isn't trivially rewritten to Rust that compiles today?

8

This is obviously wrong, and the reason for rejecting it can be

let b: &mut [i32] = #[discontinuity] x.as_mut();

or say

let b: &mut [i32] = #[discontinuity] &mut x.as_mut();

as_mut (and get) should return continuous borrowing, even if we can continue to make discontinuous borrowing on this continuous borrowing, and this continuous borrowing should not conflict with other borrowing methods

9

I see. So #[discontinuity] can’t be used with return values, because then the compiler wouldn’t know how to “restart” the borrow? I suppose that works, but then I’m less sure of the motivation. It seems like non-lexical borrows already let you do this, so you’re just saving from having to write let a = &mut x; a second time. Which is convenient, I guess.

10

I think an example is:

fn as_mut<#[discontinuity] 'a: 'b, 'b, T>(x: &'a mut Vec<T>) -> &'b mut [T] {
    &mut *x
}

let mut x: Vec<i32> = vec![1];
let a/* &#[discontinuity] '1 mut Vec<i32> */ = #[discontinuity] &mut x;     // (in this line, '1 can be invalid)
let b/* &#[discontinuity] '2 mut Vec<i32> */ = #[discontinuity] &mut x;     // (in this line, '2 can be invalid)
let b_slice/* &'3 mut [i32] */ = as_mut(b);                                 // '2 '3
//  Error:                       ^^^^^^^ dissatisfaction  '2: '3

a.push(0);                                                                  // '1 '3
b_slice[0] = 2;                                                             // '2 '3
11

This indicates that my design is reasonable. :grinning:

But obviously not completely achieving my goal, because

This is unacceptable! Because this damages the packaging, if we need a wrapper, we cannot borrow it again every time.

12

A complaint I heard (though there was something wrong with it)

前段时间有个大作业不限制语言，于是就想用rust写一下顺便熟悉一下rust，然后习惯性地套上写C++时的代码习惯：

void foo() {
  A a();
  B b(&a);
  C c(&a, &b);
  // a, b, c干活balabala
}

然后问题来了，rust不准存在多个可变引用，即使这是个单线程程序，所以只好Box<RefCell<>>满天飞，用起来满处都是borrow，最后忍无可忍还是换回了C++11，感觉脑子被rustc强奸了一样（或许我并不适合写rust吧）。

作者：icysky 链接：C++20 vs Rust，谁胜谁败？ - 知乎 来源：知乎 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

13

I don't understand what that's trying to convey (something not permitted in your idea?), but it's still trivially rewritten to something that compiles today.

    let mut x: Vec<i32> = vec![1];
    x.push(0);
    x[0] = 2;

What's a motivating case that warrants the added complexity?

Why not?

    a.push(1);

    let b = B { a:  &mut a };
    b.a.push(2);

    a.push(3);

    let b = B { a:  &mut a };
    b.a.push(2);
1 Like
14

Because the creation of the wrapper may involve other tedious tasks, repeated creation is indeed unacceptable.

15

实话说我不建议看任何知乎上的关于Rust或者C++的讨论。

You need to provide a concrete example. Code repetition itself is not unacceptable.

2 Likes
16

我只是早上刷到了 :rofl:，不过我觉得别的语言里确实比较常见

Consider a classifier for classifying items and placing them in corresponding containers

fn classifier(input: i32, odd: &mut Vec<i32>, even: &mut Vec<i32>) {
    if (input & 1) == 0 {
        even.push(input);
    } else {
        odd.push(input);
    }
}

We can use it like this:

let mut odd = Vec::new();
let mut even = Vec::new();
while let Some(input) = read() {
    classifier(input, &mut odd, &mut even);
    // use odd and even
}

Its classification method is written and needs to be re passed in every time.

Now that we have more classification projects, we need to create a wrapper for all containers:

struct ClassifierConfig<'s> {
    odd: &'s mut Vec<i32>,
    even: &'s mut Vec<i32>,
    prime: &'s mut Vec<i32>,
    positive: &'s mut Vec<i32>, 
}

fn classifier(input: i32, config: &mut ClassifierConfig<'_>) {
    todo!()
}

The configuration may be large. And it may contain some proprietary things, such as Strings. Duplicate creation is indeed unacceptable.

let mut odd = Vec::new();
let mut even = Vec::new();
let mut prime = Vec::new();
let mut positive = Vec::new();
let mut config = ClassifierConfig {
    ...
};
while let Some(input) = read() {
    classifier(input, &mut config);
    // use all
}

You may say that the classifier should have ownership of these containers, but unfortunately, perhaps the users of the containers also think the same?

Users of containers will also create their usage configurations for these containers, it may not want to know the specific content of the classifier with ownership, and recreating configurations is also unacceptable.

1 Like
17

Aren't odd/even/prime/... outputs instead of configs? You should not mix them with actual configs. Put configs that is time consuming to create in one struct, and put outputs in another struct.

And with you last example. You can just reborrow the inner pieces of ClassifierConfig.

let mut odd = Vec::new();
let mut even = Vec::new();
let mut prime = Vec::new();
let mut positive = Vec::new();
let mut config = ClassifierConfig {
    ...
};
while let input = read() {
    classifier(input, &mut config);
    let ClassifierConfig { odd, even, prime, positive } = &mut config;
    // use all
}
1 Like
18

Please note that the configuration of the container's users can also be very large.

Recreating usage configurations is also unacceptable.

This may indeed be a feasible approach, but the accepted container may require some verification and other work, and repeated creation can affect performance.

19

In fact, I think the abuse of Cells has already reflected this.

I remember Actix had an argument about UnsafeCell before?

I believe that a discontinuous lifetime can avoid the use of a portion of Cells.

20

The way I see it, discontinuous lifetimes are just a fancy word for saying to the compiler that it could/should automatically reborrow a reference, which is however something you can already do manually without Cells although maybe less ergonomically. If this wasn't what you intended then please provide us with a formal description of the feature you're proposing so that we can properly understand the feature you need.

3 Likes