Alternative to mutability restriction in single-threaded contexts?

(Not sure it is appropriate to post this here. Also I am no expert so pardon me if I am wrong)

I have been following Rust for a few years and lately I have decided to give it a serious try. So while learning Rust, I was trying to understand why borrow limits are imposed even for single-threaded programs and (I think) I have gained an understanding here. It seems that multiple mutable borrows doesn't have any consequence on memory safety of single-threaded programs, if and only if no structure type have any pointer to heap allocated data[1]. Things only get problematic if a structure type has a pointer to the heap and some function that invalidates the heap memory allocated is called after the object has already lent out a reference.

Update: The following strategy is less expressive and has bad granularity, among other problems. Skip to Update 3.

A strategy I have come up with alternative to borrow checking is to track memory invalidation and reference flow "effects" in terms of format parameters for individual functions. For example, a function that invalidates a heap allocation of some formal parameter p is said to have a memory invalidation effect (memoryinv for short) on p. So, Vec::push has a memoryinv effect on the self parameter. Similarly, a function is said to have an effect (a <- b) if there is reference flow from b to a given a and b are reference typed. These effects are built for individual functions and propagated to the root of the call graph. Local "reference flow" effects can be built using points-to analysis. Also, move semantics could be taken into account.

For example,

struct Foo {}

struct FooHolder {
    foo: &mut Foo,
}

// This function has the effect list [(y <- x)]
fn func1(x: &mut FooHolder, y: &mut FooHolder) {
    y.foo = x.foo;
}

// This function has the effect list [(a <- b)]
fn func2(a: &mut FooHolder, b: &mut FooHolder) {
    func1(b, a); // Add (a <- b) to the effect list since 'func1' has effect (y <- x)
}

// This function has the effect list [memoryinv(vec)] since it calls 'Vec::push' on 'vec'
fn func3(vec: &mut Vec<i32>) {
    vec.push(3);
}

struct BoxHolder {
    b: &mut Box<i32>,
}

// This function has the effect list [memoryinv(bh), memoryinv(b)]
fn func4(bh: &mut BoxHolder, b: &mut Box<i32>) {
    bh.b = b;
    std::mem::drop(b); // Add 'memoryinv' for both 'bh' and 'b' since both 'bh' has a reference to 'b'
}

fn main() {
    let mut outer = FooHolder { foo: Foo {} };
    {
        let mut inner = FooHolder { foo: Foo {} };
        // Error: 'func2' has an effect (a <- b) but 'outer' outlives 'inner'
        func2(&mut outer, &mut inner);
    }

    {
        let mut vec = vec![1, 2, 3];
        let mut itemref1 = &mut vec[0];
        let mut itemref2 = &mut vec[1];

        // Error: 'vec' has already lent out a reference but 'func3' has a memory invalidation
        // effect on 'vec'
        func3(&mut vec);
    }

    {
        let mut b = Box::<i32>::new(2);
        let mut bref1: &mut i32 = &mut b;

        // Error: 'b' has already lent out a reference but 'std::mem::drop' has a memory
        // invalidation effect on 'b'
        std::mem::drop(b);
    }
}

Is this reasoning correct or am I missing something?

Update 1: Of course, the compiler cannot infer memory invalidation effects. The memory invalidation effect must be manually annotated alongside the function signature. For example, the Vec::push method must be manually annotated since it might potentially reallocate the allocated memory. And yes, the missing annotations can be a source of bugs, but annotations are needed only for data structures implemented using raw pointers and those cases mostly involve unsafe blocks.

Update 2:
[1] - As @trentj pointed out, this post originally didn't take into account the type-punning enums. Marking the enum assignment operator as memory invalidating could solve this problem. This would seem hack-y or "plugging the holes" but actually it is not. The basic definition of the memory invalidation effect is that any the references lent out by an object getting invalidated. So, assigning an enum object a different type could be considered as memory invalidation. So the premise of this proposal still holds true: multiple mutable references to an object are benign unless the memory invalidation effect this proposal describes is exerted on the object later in the same scope.

Update 3:

After starting this thread, I read some amount of Rust code (and wrote a little of my own), I think I understand Rust now a lot better. I find explicit lifetimes to be a good thing (and not so painful as I thought) for the most part. It seems like the I have been reasoning about lifetimes in C++ as well, but only implicitly. And Rust makes up for the extra thinking/typing with better ergonomics (when compared to C++), plus safety guarantees. That said, I am still uncertain of the exclusive mutability restriction. Title of this thread has been changed to reflect this.

In this post, the memory invalidation thing (maybe "effect" gives the wrong impression) still sounds reasonable. Like, Vec<>::push being annotated as memory invalidating for self and other functions that accept a Vec<> parameter and calling Vec<>::push on it would be automatically considered memory invalidating for the said parameter. The only invariant is that local variables must not be passed as parameters to functions that invalidates their memory after they have lent out a reference. So, no mutability or borrow limits for thread-local objects. Note that only Vec<>::push needs to be annotated in the example and functions that are needed to be annotated most likely involve unsafe . This method eliminates all the errors the exclusive mutable aliasing prevents in single-threaded contexts (like iterator invalidation et al.).

For an example,

mod std {
    mod vec {
        impl<T> for Vec<T> {
            ...
            #[invalidates_memory(self)]
            pub fn push(&mut self, t: &T) {
                ...
            }
            ...
        }
    }
}

// This function is inferred to be memory invalidating for 'vec'
// since it calls 'Vec<>::push' on 'vec'
fn push_to(vec: &mut Vec<i32>) {
    vec.push(2);
}

fn main() {
    let vec = vec![1, 2, 3];
    let item_ref = &mut vec[0];
    let item_ref2 = &mut vec[1];
    // Error since 'push_to' invalidates 'vec' but 'vec' has already lent out
    // at least one reference
    push_to(&mut vec);
}

An enum constructor could also be considered memory invalidating. So in @trentj's example,

enum Foo {
    Bool(bool),
    Int(i8),
}

let mut foo = Foo::Int(10);
let mut i = match foo {
    Foo::Int(ref mut i) => i, // 'foo' lends out a reference here
    _ => unreachable!(),
};

// Error, since this invalidates the memory of 'foo' but 'foo' has already 
// lent out a reference
foo = Foo::Bool(true); 

So, wouldn't segregating objects into thread-safe and not thread-safe and enforcing the exclusive mutability restriction just for thread-safe objects and this memory invalidation restriction for the rest reduce a lot of friction?

It is true that Rust's ownership/borrowing/lifetime system is more restrictive than is strictly necessary to ensure soundness. In most cases this is intentional because:

  • It allows for a much simpler system. For example, & and &mut are the only kinds of references you have to learn. There is no &uniq or &move or &uninit or &singlethreaded or whatever else people have proposed over the years.
  • No ecosystem splits. For example, there's no split between "thread-safe" and "single-thread only" code, or (like in D) between "GC" and "no-GC" code.
  • Thread-safety, heap allocation, etc. are almost entirely handled by library code, keeping the core language simpler. This probably doesn't affect user-facing simplicity, but it makes it easier to reason about and prove the soundness of the core language (and possible changes to it), not to mention allowing users to write their own allocators, data structures and thread pools with confidence.
  • Every restriction is also a guarantee. Because Rust does not allow you to make two &muts alias, Rust can guarantee that every &mut argument passed to your functions won't have any aliases, which turns out to be an extremely useful guarantee both for API design and for compiler optimizations.
  • In particular, current Rust does not need to look at a function's implementation to do borrow checking / type checking on calls to that function (much less the entire call stack), and it effectively guarantees that any implementation change which doesn't impact the function signature won't break any callers, and so on. There are some small exceptions to this today (e.g. impl Trait "leaking" auto traits), but an "effects" proposal like this seems to almost completely drop those properties, which would no doubt hurt ecosystem stability and compile times and forever rule out better dynamic linking support.

Regarding your specific proposal, I'm sure it could be made to work, but "alternative to borrow checking and lifetimes" doesn't seem like an accurate description. For example, reasoning about the lifetimes of shared references is still crucial for soundness when no heap allocations or mutability is involved (even if you ignore interior mutability!), so this proposal definitely can't "replace lifetimes" as we know them today. Right now I'm just not seeing a way that this could lead to making the overall ownership/borrowing/lifetime story in Rust simpler or more flexible or whatever.

6 Likes

This isn't true. Consider writing to an enum while holding an internal reference to a different variant:

enum Foo {
    Bool(bool),
    Int(i8),
}

let mut foo = Foo::Int(10);
let mut i = match foo {
    Foo::Int(ref mut i) => i,
    _ => unreachable!(),
};

foo = Foo::Bool(true);

// doing anything with *i here breaks aliasing, even if it's not written to
*i = 20;

println!("{:?}", foo);

Also, your example shows how such an effect-based system could prevent errors that Rust's current ownership and borrowing rules also prevent, but I would also like to see how it can allow things that the current rules forbid even though they are sound. That's where there is room for improvement, if any.

Also also, it just dawned on me that #[may_dangle] actually does kind of work like such an "effect". I'm not up to the task of explaining it, though, so all I can do is link to the Nomicon.

2 Likes

I want to re-emphasize this. There are many, many things that Rust could do, but chooses not to in order to keep this property.

It's extremely important for good error messages (a mistake inside one function can only give errors in that function) and for prototyping/testing (you don't want more things to compile just because you implemented a function as todo!() temporarily).

Is it possible that there are other systems than the current lifetime one that could work? Yes. But you also don't want to end up in a mode like Midori, where its language had 9 different composable effects, IIRC.

2 Likes

Given @trentj's post, it might be worth clarifying: Part of what I had in mind when I said "I'm sure it could be made to work" is that we'd obviously have to extend the analysis to consider not just functions, but also assignment statements to "have a memory invalidation effect" on the variable they assign to.

We'd also have to think about how to deal with each of these effects happening in conditionals or loops or other control flow constructs which even regular Rust often struggled with before NLL, and regular Rust is still trying to improve with Polonius and other refactors.

I chose not to spell out any of these "gotchas" in my first reply because I think the bigger picture of why Rust doesn't do anything like this is much more important and interesting. Simply "plugging all the holes" won't address those high-level concerns.

My proposal too wouldn't mandate the compiler to look at the implementation. A list of effects for a function is generated once when compiling a crate. If you meant it'd break the call site, I suspect it won't happen much in practice without changes in the API's interface part itself.

Could you elaborate on why my proposal would need explicit lifetimes?

Perhaps "look" was too vague. The important property @scottmcm and I are talking about is that the calling code and the implementing code can each be compiled completely independently of each other, using nothing but the function signature and whatever types/variables are in each scope.

The compile-time hit I was referring to is that calling code becomes impossible to compile until after the implementation (and all other function implementations down the call stack) have been compiled so that we know their memory effects. You can certainly cache this information, so the hit is tolerable on incremental builds with changes in leaf crates, but it's still a massive hit to cold builds and incremental builds for non-leaf changes since you can no longer do much in parallel.

While I agree that signature-preserving changes to a function's memory effects are rare by some metrics, in this proposal they are "viral", spreading that change to all of their transitive callers anywhere in your dependency tree. That quickly makes rare things become commonplace at scale, and leads to various kinds of "dependency hell".

I'm not entirely sure what to say here since it's no different from why current Rust sometimes needs explicit lifetimes. Your first post simply doesn't contain any of the cases where explicit lifetimes show up in current Rust, or any explanation for how this proposal would replace explicit lifetimes (until now it wasn't even clear to me if you thought it would).

I guess the simplest thing I could add that might avoid descending into a distracting game of whack-a-mole is that if your function's implementation contains unsafe code, then it's extremely likely the compiler cannot infer all the memory effects for you, so no matter how this proposal gets fleshed out you'll always have to provide some sort of fallback mechanism for explicitly annotating those cases. Perhaps I shouldn't have lumped "memory effect annotations" together with current Rust's "lifetime annotations", but it seems like they'd be very similar and at least as complicated.

I am not sure about "dependency hell" thing. Unless an API function does wild things like assigning a passed reference into a global object, these errors wouldn't arise. On large projects, lifetime contracts are usually set/documented. In such cases wouldn't such an error signal a potential memory bug? C++ code bases would go unnoticed in a similar scenario.

Sorry I was missing an important point in the OP. Of course, the compiler cannot infer memory invalidation effects. The memory invalidation effect must be manually annotated alongside the function signature. For example, the Vec::push method must be manually annotated since it might potentially reallocate the allocated memory. And yes, the missing annotations can be a source of bugs, but annotations are needed only for data structures implemented using raw pointers and those cases mostly involve unsafe blocks.

(We can call &mut &uniq and that would be more accurate)

This sounds like it is quite a bit more complex to reason about, because now we will have two different systems to track lifetimes, thus it would make unsafe code harder to write. Rust shouldn't try to make safe code simpler at the expense of unsafe code.

Also, by making the lifetime contracts implicit, it becomes vastly more difficult to reason about your program. Lifetimes are so hard because by the time anyone starts to learn about them, they are already neck-deep in lifetime errors, thanks to lifetime elision for making all the simple lifetimes go away. Making things even more implicit doesn't seem like a good idea.

Moreover, lifetime annotations are more useful than just tracking references, see generativity which (ab)uses some subtle lifetime interactions to create a unique type per invocation of the make_guard macro. This can allow you to write abstractions that do completely runtime-unchecked indexing, because all of the indexes are compile-time checked via lifetime annotations. (my point being, lifetime annotations are a general tool to do compile-time-checks and are far more useful than you think)

1 Like

Sorry the original post didn't touch the type punning aspect of enum types. Honestly, I was aware of this problem even before starting this thread. Marking the enum assignment operator as memory invalidating could solve this problem. This would seem hack-y or "plugging the holes" but actually it is not. The basic definition of the memory invalidation effect is that any the references lent out by an object getting invalidated. So, assigning an enum object a different type could be considered as memory invalidation. So the premise of this proposal still holds true: multiple mutable references from an object are benign unless the memory invalidation effect this proposal describes is exerted on the object later in the same scope.

EDIT: typo

Update: The examples in this post are wrong.

In the following example, the borrow checker requires annotations,

struct Foo<'a, 'b, 'c> {
    x: &'a i32,
    y: &'b i32,
    z: &'c i32,
}

fn foo_with_three_xs<'a, 'b, 'c>(fooref: &Foo<'a, 'b, 'c>) -> Foo<'a, 'a, 'a> {
    Foo{x: &fooref.x, y: &fooref.x, z: &fooref.x}
}

fn main() {
    let x = 1;
    {
        let y = 2;
        let z = 3;
        let foo = Foo{x: &x, y: &y, z: &z};
        let new_foo = foo_with_three_xs(&foo);
    }
}

While my proposal wouldn't require lifetime annotations,

struct Foo {
    x: &i32,
    y: &i32,
    z: &i32,
}

// This function has the effect list [(return <- fooref)]
fn foo_with_three_xs(fooref: &Foo) -> Foo {
    Foo{&fooref.x, &fooref.x, &fooref.x}
}

fn main() {
    let x = 1;
    let outerfoo: Foo;
    {
	    let y = 2;
	    let z = 3;

	    // During analysis, the following line adds edges from the node 'foo' to nodes 'x', 'y'
	    // and 'z'.
	    // The invariant is that the descendent nodes must not have shorter lifetime
	    // than the parent node
	    let foo = Foo{x: &x, y: &y, z: &z};

	    // 'foo_with_three_xs' has an effect (return <- fooref).
	    // Substituting 'return' with 'new_foo' and 'fooref' with 'foo',
	    // we get (new_foo <- foo) which is safe since both 'new_foo' and 'foo' have the
	    // same lifetime.
	    let new_foo = foo_with_three_xs(&foo);
	    // ... while this is invalid because node 'foo' has children nodes 
        // (namely 'y' and 'z') that have a narrower lifetime than 'outerfoo'
	    outerfoo = foo_with_three_xs(&foo);
    }
}

AFAIK, this proposal violates the thread safety guarantee that Rust unless &threadsafe et al. are introduced.

I don't know but the Rust's single mutable aliasing everywhere paradigm imposes much more cognitive load and friction than any other language I have ever used. In my experience, I have found that with additional cognitive load I am more likely to introduce a logical bug. While it is true that non-GCed languages obligate more cognitive load, modern C++ surprisingly doesn't "get in the way" often. Maybe getting more familiar with Rust could change this opinion. Maybe Rust is not for me or I will get used to it.

C++ also won't help that much when things go sideways, so the time spent debugging C++ can far outweigh the time spent describing your problem to Rust. Rust gets in your way at compile time so that you can only focus on your logic at runtime and not worry about weird memory errors. Anytime you have to annotate lifetimes, your lifetime are sufficiently complex that the act of annotating lifetimes correctly will help you understand the domain better.

If you remove the annotations, it makes this program much harder to reason about. You now have to read the implementation of foo_with_three_xs to know it's lifetime contract, but what if it's much longer? It would be really easy to miss something and accidentally introduce a breaking change.

If you want mutable aliasing on a single thread, then you can use &Cell<T>, but that's only convenient to use for types that are Copy or Default. For other types you can use RefCell

1 Like

I'm not sure what the example is supposed to demonstrate. It seems like you're saying that (rhetorical syntax)

#[effect(return <- fooref)]
fn foo_with_three_xs(fooref: &Foo) -> Foo

would be equivalent to today's

fn foo_with_three_xs<'a>(fooref: &'a Foo) -> Foo<'a, 'a, 'a>

But that's actually less expressive than the current system, because (according to your example) it prevents you from assigning foo_with_three_xs(&foo) to outerfoo, which is perfectly valid!

If you extend the effect syntax to cover all the use cases of lifetime annotations, doesn't that just leave you with just the same degree of complexity under a different surface syntax?

#[effect(return <- fooref)]                          // like &'a Foo -> Foo<'a, 'a, 'a>
#[effect(return <- fooref.x)]                        // like &Foo<'a, '_, '_> -> Foo<'a, 'a, 'a>
#[effect(return.x <- fooref.x, return <- fooref.y)]  // like &Foo<'a, 'b, '_> -> Foo<'a, 'b, 'b>

I don't think this is relieving cognitive load; you still have the same lifetime relationships, they're just... not quite as explicit. Which can be good or bad; I'm not saying it's bad, necessarily, I'm just saying I don't know that it's better than what we have. Forgive me if I am misunderstanding the proposal.

(And that's without even getting into more complex relationships -- like, how would you annotate a function like HashMap<K, V>::entry when K, V, and Entry all have different lifetimes? :cold_sweat:)

3 Likes

Rust's single mutable aliasing everywhere paradigm is pretty much only one simple rule you have to abide by. If you don't the compiler tell you off and suggests what to do about it. Yes, I agree it is an extra cognitive load compared to banging out some C/C++. But it is a cognitive load you bear at the time of writing the code, not in the long hours in the middle of the night trying to find some obscure memory leak or corruption in deployed systems. I also find it forces me to think a bit more upfront about the structure of my program and data, resulting in a someone better outcome. An outcome I can be much more confident to reason about. A logical bug is a lot less cognitive load than a hard to find memory error.

It's funny how we all have different feelings about these things. I have been using C++ for ages. Getting in my way of the program I actually want to write is something C++ does very well. C++ is so immensely complex I can never be sure it actually does what I think it should.

Certainly getting more used to Rust will change the way you feel about it. The more you begin to understand why things are the way they are the better you will feel about them. I do sympathize with the feeling that some of it is "off the wall". It happens because one does not know/understand the reasoning behind it.

Having said all that, I still have a long way to go in getting comfortable with a lot of Rust features. I'm confident it will be worth the effort.

2 Likes

Oh my God! :open_mouth: I have hastily written that post and x and y were meant to be in the outer scope instead of x. Never mind, I've found out other problems with the proposal as well other than the bad granularity. Okay, lets leave the whole "effect inference" thing.

After reading some Rust code (and writing a little), I think I understand Rust now a lot better. I find explicit lifetimes to be a good thing (and not so painful as I thought) for the most part. It seems like the I have been reasoning about lifetimes in C++ as well, but only implicitly. And Rust makes up for the extra thinking/typing with better ergonomics (when compared to C++), plus safety guarantees. That said, I am still uncertain of the exclusive mutability restriction.

In the OP, the memory invalidation thing (maybe "effect" gives the wrong impression) still sounds reasonable. Like, Vec<>::push being annotated as memory invalidating for self and other functions that accept a Vec<> parameter and calling Vec<>::push on it would be automatically considered memory invalidating for the said parameter. The only invariant is that local variables must not be passed as parameters to functions that invalidates their memory after they have lent out a reference. So, no mutability/immutability borrow limit for thread-local objects. Note that only Vec<>::push needs to be annotated in the example and functions that are needed to be annotated most likely involve unsafe. This method eliminates all the errors the exclusive mutable aliasing prevents in single-threaded contexts (like iterator invalidation et al.).

So, wouldn't segregating objects into thread-safe and not thread-safe and enforcing the exclusive mutability restriction just for thread-safe objects and this memory invalidation restriction for the rest reduce a lot of friction?

I will update the OP to reflect this.

2 Likes

What happens when I want to reuse an object in a threaded environment when it is not written for thread safety?

What happens when I decide to add threads to my project and inadvertently end up using thread unsafe code elsewhere in the code base?

As someone who has architected computers and designed cell libraries for most of the last 50 years, I have no qualms in predicting that the days of single-core non-hyperthreaded processors are numbered, except for the simplest highest-volume applications. Therefore languages for such future hardware will need to demand thread safety as the default, with exceptions requiring use of a flagging keyword such as unsafe.

Decades of system failures in many fields of endeavor show that humans do not reason well about concurrency in the large. In this respect Rust is very forward-looking. Rust is designed to be thread-safe by default; older languages like, C, C++, Ada, and even assembler were not. I personally would have little interest in Rust were it not thread-safe by default.

4 Likes

This is exactly why my original reply included:

So at best, it's trading one kind of friction for another.

There are probably ways to make the argument that "letting muts alias in single-threaded code is worth the ecosystem split", but I'm skeptical you could ever make that case the more persuasive one. AFAIK @TomP's extremely right that "the days of single-core non-hyperthreaded processors are numbered".

And personally, I've just never run into a case where I wanted aliasing muts in my code except when that code fundamentally needed to be unsafe anyway (e.g. efficient data structure implementations).

1 Like

One of the key points of the borrowing system is its profound simplicity.

I'm sure one can come up with exceptions where shared mutability is technically not wrong. But my *checks calendar* several-year experience with people wanting to give up the RWLock pattern consistently shows that basically everyone says "oh yeah, I never really needed shared mutability in the first place" after getting the hang of Rust and learning how to write idiomatic code.

Let's just keep the borrowing rules as-is. Piling subtle yet complicated exceptions on top of one another never worked out well in programming language design. There's no reason to believe we would magically get it right this time.

6 Likes

I might be overthinking/exaggerating this friction too much lately (instead of actually writing more code). Apparently, people who use regularly don't have a problem with it. So, the friction will more likely ease over time.

Thank you @Ixrec, @trentj, @scottmcm, @RustyYato, @ZiCog, @TomP and the Rust community for putting up with my rather uninformed posts. I will leave this thread.

2 Likes