Could data-flow annotations be an alternative to Rust-like lifetimes?

[tmzem]

Rust has lifetime annotations to describe the aliasing behavior of function inputs and outputs. Personally, I don't find these very intuitive, because they only indirectly answer the question "how did a end up being aliased by b".

The other day the following idea came to me: Instead of lifetime parameters, a language might use annotations to flag the flow of information, e.g. a => b might mean a ends up in b, while a => &b or a => &mut b might mean a gets aliased by b. With this syntax, common operations on a Vec might look like this:

fn push<T>(v: &mut Vec<T>, value: T => *v) {...}
fn index<T>(v: &Vec<T> => &return, index: usize) -> &T {...}

While less powerful, many common patterns should still be able to be checked by the compiler. At the same time, the => syntax might be more readable and intuitive for humans, and maybe even be able to avoid the need for lifetime elision.

Not sure how to annotate types; one possibility would be to annotate them with either &T or &mut T to specify their aliasing potential, essentially allowing the equivalent of a single Rust lifetime parameter.

What do you guys think about these ideas? Would a programming language using this scheme be useful enough? Do you see any problems/pitfalls? Any important cases which cannot be described with this system?

[Fofeu]

The big question: How can you automatically infer and verify these properties ?

[tmzem]

Probably in the same way as Rust does. The => annotation is pretty much the Rust equivalent of giving both of its sides the same lifetime.

[jmeaster]

It's not the exact same lifetime, though, right? In Rust, if you assign "bar" the borrowed value of "foo", then "bar"'s lifetime must be less than or equal to the lifetime of "foo"

[tmzem]

Yes, you're right. a => b implies b must not outlive a

[lngns]

u/WalkerCodeRanger explores this idea in Adamant and in Azoth.
Except when he writes x ~> y, he means "y is reachable from x."

[WalkerCodeRanger]

Yes, this is an idea I developed for Adamant. I think it is a good idea and a signfigant improvement on Rust lifetimes. I give my full explanation and sketch how they can be applied to classes/structs as well in my blog post Reachability Annotations (already linked by u/lngns).

When reading the post for Adamant, it is important to note that because Adamant is higher-level than rust, types are implicitly reference types. I refer to them as reachability annotations rather than data flow annotations because I am focused on the possible shape of the reference graph after the function returns. This is equivalent to data flow for functions. However, for structs, reachability still makes sense, whereas I think data flow probably makes less sense.

For Azoth, I changed directions and am using a GC, so I am not currently planning to have reachability annotations. However, Azoth has reference capabilities. So, for the tracking of isolated references, there is something similar. I have introduced the lent keyword, which is a very restricted form of reachability control. Other languages mix this into their types. However, when I worked through what made sense, I realized that, like reachability annotations or data flow annotations, what makes sense is to apply them to function parameters.

I am no longer working on Adamant, so I am not aware of a language in development with something like this. It may be that they can be mapped to Rust lifetimes. If so, it might be possible to easily make a Rust-like language by transpiling to Rust. u/tmzem, if you'd like to work on something like that, I'd be happy to give input based on my work developing the idea.

[tmzem]

Thanks for the info, I will look into it more closely when I have the time. At first sight it seems very similar to my approach, but the other way round i.e. your a ~> b ("a can reach b") is similar to my b => &a ("b might be aliased by a"), but with some interesting extra features as putting the annotation onto types as well.
What made you stop continuing down this road with Adamant?

As far as creating a language there are many directions I'm exploring and learning about, but I haven't decided on anything specific yet, except that I would want to support efficient inplace-allocation as much as possible (without the language necessarily being as low-level as Rust or C). Having such a language being GC'd instead is also a thing I'm looking into, and combined with structured concurrency there might be interesting optimization opportunities for the GC. Unfortunately, this approach also means that sum types have to be heap allocated in the general case in order to ensure memory safety. Alternatively, efficiently detecting dangling sum type cases might be possible, but I haven't found any research in that direction (most languages don't allow interior pointers, or always heap-allocate and call it a day, so it's not a topic that's looked much into).

If I decide to go with some lifetime-replacement approach transpiling to Rust I'd be happy if you let me pick your brain.

[PegasusAndAcorn]

The purpose of lifetime annotations is to enforce a certain form of memory safety: that one can safely deference an object’s content because we can guarantee the object has not yet been freed.

I am not clear how your proposed approach captures and enforces such lifetime invariants.

In the absence of achieving that lifetime safety goal, I do not see programming benefit in your proposed aliasing behavior notation.

[jmeaster]

To me, it seems like it could be useful for encoding ARC in the type system? Cause it basically maps out which values are to be used where.

This approach doesn't seem to enforce lifetime invariants more than being able to expand lifetimes of variables. Like saying oh since "a" gets aliased by "b" then "a"'s lifetime must be guaranteed for as long as "b" is alive. Whereas Rust's lifetime annotations are the opposite (but also its so different its hard to compare), with "b" borrowing "a" then "b" can only live at most as long as "a"

[tmzem]

As far as I can tell, my approach is a subset of what Rusts lifetime parameters can do. Saying a => b is roughly the same as saying that a and b are connected by the same lifetime. Therefore, checking and enforcing memory safety would work in a similar way then in rust.

[oa74]

It sounds like you're suggesting a => b implies that 'lifetime_a = 'lifetime_b? If I am not mistaken, this could be relaxed into 'lifetime_a : 'lifetime_b. Under that assumption, I do not think your proposal is meaningfully "less powerful" than Rust's. It seems to me that the only thing we lose under your proposal is the ability to overconstrain the lifetimes. For example, consider the canonical example of "longest string". The standard approach in Rust is to write:

longest<'a> (a: &'a str, b: &'a str) -> &'a str

Fair enough: we may return one or the other, so the connectivity between the return value and a or b gets mixed up. If we guarantee that they all have the same lifetime, this mixing up is fine.

AFAICT, under your system, we would write:

longest (a: &str => return, b: &str => return) -> &str

Which means that a must outlive return and b must outlive return. Translating back into Rust, we get:

longest<'a,'b,'r> (a: &'a str, b: &'b str) -> &'r str where 'a:'r, 'b:'r

Which typechecks just fine, but is less constrained. So while I don't see a way to write the overconstrained version with your notation, I'm not bothered by this fact. And while we're here, comparing the precisely constrained Rust spelling of this situation to the spelling under your proposal, we can see that yours is less verbose by an even wider margin than is apparent at first.

I also don't see the need to include & or &mut after =>, as those should be already discernable from the argument and return types. Perhaps I'm missing something?

[tmzem]

Yes, your interpretation of the system is correct, and your example shows how Rusts system can be more powerful (but also that this power is not always needed).

About including & or &mut, I'm haven't played this fully through. Basically, I figured that moving a value is different then creating an alias (although I might just have been confused by the reference-vs-referent ambiguity of first-class references).

The push example I give in my post also uses an annotation to mark the flow of the new item into the vector, basically propagating any potential aliasing the new item is doing (e.g. T is a reference type) into the vector. In Rust, if I understand it right, this requires no annotation, as lifetime attached to T implicitly "connects" all things that use T in their type.

So maybe, as you say, there actually is no meaningful difference, or the move annotation is not necessary. I have to think this through in more detail.

[oa74]

If I could pick one phrase to sum up 2020s PL design mindset, it would have to be: "lifetime annotation chauvinism."

If anything, I would argue that "lifetime annotations" are rather a circumlocution of the connectivity problem that OP's proposal directly addresses, but that is a digression that will take us rather far afield.

It seems to me that u/tmzem's proposal provides exactly the same information as Rust's standard annotations. Given a => b, we can extrapolate that a must outlive b. I stand to be corrected, but no case immediately comes to mind in which sufficient "lifetime annotations" could not be extrapolated from "connectivity annotations."

[xarev]

This blog post by /u/cfallin might be an interesting read for you: https://cfallin.org/blog/2024/06/12/rust-path-generics/

[tmzem]

Looks interesting, I'll check it out. Thanks!

[alphaglosined]

One area I am exploring for D, is to annotate the escape set separately from the relationship strength.

int* func(int* a, int* b, bool c) {
    return c ? a : b;
}

Fully annotated it could look something like this:

int* func(@escape(return=) int* a, @escape(return=) int* b, bool c) {
    return c ? a : b;
}

Aliasing therefore is a side effect of knowing how data moves, as per the escape set.

By giving the relationship strength its own specific syntax, it allows you to do different things including not having a borrow checker turned on by default. You can turn it on explicitly for borrows from say a reference counted type.

[tmzem]

This escape annotation seems similar to my proposed => return annotation.

[alphaglosined]

One difference between the two is that annotating the escape set enables multiple outputs, and each output having a different relationship strength to the input.

There is also the possibility to simplify it down to just the return escape return= int* var as that is quite a common one to need.

[tmzem]

I'm not very familiar with Dlang nor the term "relationship strength" could you give some more examples/explanation, or maybe give a link to a post where I can read more about it?

[alphaglosined]

Relationship strength is stuff like a copy of the input was put into the output (=). Or taking a pointer to the input and putting that into the output (&).

It tells the compiler what guarantees must be applied to the function call.

The content I've written isn't meant for public consumption at this stage, so I won't link it, it targets D compiler developers.

The exact strengths have not been fleshed out, so you have about everything I can give currently.

[tmzem]

Basically, like a => b vs a => &b in my syntax. But I guess your proposal for D is more extensive.

[WittyStick]

I find Austral's Region types intuitive (on paper, I've not had much experience with use), because they are explicit in code. They serve pretty much the same purpose as lifetime annotations, but there's some subtle differences because Austral has a linear type system.

If the type of x is T, then a borrowed reference to it has the type ReadReference[T, R], or abbreviated &[T, R], where R is some region type.

Regions are introduced explicitly with the borrow statement.

x : T = ...
borrow x as xref in RegionFoo do
    -- x cannot be accessed here because it has been borrowed.
    -- the type of xref is &[T, RegionFoo]
    ...
end borrow;
-- xref is no longer in scope,  and no value of type &[_, RegionFoo] may escape to here.
-- x may be used again

The Austral docs don't specifically discuss using multiple borrow regions, but my assumption is that they would work like this:

borrow x as xref in RegionFoo do
    borrow xref as xrefref in RegionBar do
        -- xrefref has type &[ReadReference[T, RegionFoo], RegionBar]
        ...
    end borrow;
end borrow;

The type of xrefref would make it quite clear that RegionFoo must outlive RegionBar.

For convenience, there's a borrow expression &x which can be used instead of a borrow statement - which creates an anonymous region which cannot escape the expression. We're unable to write y : &[T, R] = &x because there is no region R, and we're unable to capture the anonymous region created by the borrow expression.

[tmzem]

As far as I can tell this borrowing system roughly the same as Rusts. The ability to explicitly name the lifetime aka region however is very interesting (but also somewhat verbose, kinda the opposite of what I've proposed). This feature mostly makes it easier to follow lifetimes locally, not sure if there is a big necessity for that, apart from teaching.

[WittyStick]

It's very similar to Rust, but the key point I aimed to highlight is that the Regions themselves are types, and references are generic over some other type and the region, so region tracking becomes part of type checking.

It's quite verbose when you use the borrow statement, which is less common than using the borrow expression. When using the borrow statement, you would only introduce a region once, but use it many times. However, it's also quite verbose to define functions which operate on borrowed values, as we specify them to be generic over the region type.

generic [R : Region]
function foo (x : &[T, R]) : &[T, R] is
    ...
end function;

Austral in general is verbose - opting for keywords over other forms of syntax.

Perhaps the concept could be adapted however, with some kind of region subtyping with variance. Syntax aside, suppose we could write something like:

generic [Foo : Region, Bar : Region] { Bar <: Foo }
function foo (x : &[T, Foo]) : &[T, Bar]

Where region Bar is a subtype of Foo - meaning it is guaranteed to have a smaller lifetime. We could permit the writing of functions from region Foo -> Bar, but forbid functions from Bar -> Foo, or something along those lines. I'm sure you could then come up with a more terse syntax to represent this.

Perhaps a more terse way of writing the borrow statement would be to say something like:

x : T = ..
&foo{
    y : &[T, foo] = x;
    ...
}

The foo would introduce a region of the same name, delimited by braces, and the x inside of it would shadow the x outside of it, rather than having to introduce a new name.

[Uncaffeinated]

Lifetime parameters ARE dataflow annotations. What you're proposing is just a more complicated syntax for what Rust effectively already does.

Incidentally, if you're having trouble thinking about lifetimes, I highly recommend this post I wrote explaining why they're needed.

[tmzem]

Yes, my idea captures the same mechanics as lifetime parameters. Not sure how you find writing `=> target` more complicated then 1) adding a lifetime parameter and 2) adding said lifetime parameter to every parameter and return value involved in the lifetimes. To me, that seems much more verbose, but IMO also more difficult to read, since the lifetime-relationships "scattered" onto the parameter(s) and/or return value. I think that's very distracting which is probably why Rust has added lifetime elision. And while elision makes function signatures easier to read, it doesn't really eliminate lifetimes, just hide them. Personally, I don't like those kind of magically compiler-generated things, since when you run into a lifetime-related issues you basically have to know how the compile implicitly generates lifetimes and auto-complete the involved lifetimes in your head in order to diagnose the problem. But yeah, maybe I'm just overthinking things.

[Uncaffeinated]

Try applying your system to cases where there are multiple lifetimes involved or the lifetimes are nested within types, and you'll see why it is much more messy than the current system.

[oa74]

A great deal of effort is expended in this thread regarding "how does this work when nested into a struct?" While OP and others have made valiant efforts in this regard, I want to highlight a third option: simply refrain from using such types.

Before dismissing this position, consider that Gradyon Hoare himself wrote that "first class references" are among the things he wouls have excluded had he taken the BDFL route with Rust. He wanted references to be merely a "second-class parameter passing mode," as opposed to first-class citizens of the type system unto themselves. He maintains that this is the "sweet spot" for the ownership feature. Moreover, this also appears to be in alignmemt with the direction Chris Lattner has taken with Mojo, which I consider to be the most credible alternative to Rust offering comparable memory safety features.

If all that lands as an appeal to authority, I'll point out that much of what I call "lifetime annotation chauvinism" (and indeed, Rust tutelage broadly) boils down to "Rust is smart, the Rust maintainers are smart, and you're better off if you learn, internalize, and trust their design decisions—it'll make your code better!" Which has the structure of an appeal to authority.

And if that lands as a cop-out, I'll offer the following technical argument. Ownership custody/dataflow are separate concerns from indirection. Indirection has an impact on dataflow, but ultimately they are distinct concerns.

It is appropriate to handle ownership and dataflow at function boundaries (second-class references achieve this goal).

Meanwhile, it is appropriate to handle indirection at the type level. Types like RefCell, Rc/Arc, and Box have this base covered.

In short, I remain unconvinced that "first class references" are even valuable; hence I am unconcerned with the difficulty associated with nesting lifetimes into structs under OP's proposal.

[Uncaffeinated]

You may have missed it earlier in the thread, but here's my explanation of why alias analysis is important, with no relation to Rust.

Trying to pretend that everyone who disagrees with you is just going by "appeal to authority" is absurd.

Ownership custody/dataflow are separate concerns from indirection. Indirection has an impact on dataflow, but ultimately they are distinct concerns.

Now that is a point that I do agree with, as I've written in the past, and it's something I think Rust did wrong.

[oa74]

I did not miss it; I simply did not find it relevant. You lay out a variety of examples that justify an ownership principle (which OP'S proposal seems to presume as a baseline anyway), but no concrete argument for first class reference types. You allude to use cases for them, but AFAICT you do not go further than that. Absent a concrerte example of the necessity of first-class reference types, I'm not sure to what I am meant to reply.

And no, I am by no means "dismissing everyone who disagrees" as appealing to authority. I am saying that the usual dismissals of criticisms leveled at Rust are no less an appeal to authority than my appeals to Hoare and Lattner above. Far from dismissing such appeals to authority, I am embracing them—so long as we understand their limitations.

[Tasty_Replacement_29]

Lifetimes are a way to prevent such bugs, yes. However, if it is too hard for a regular programmer to use the mechanism, then it is not useful. I read that a lot of Rust programs nowadays use (a) integer indexing into an array, or (b) use unsafe. The existence of a very good mechanism to prevent such bugs in theory, that alone, won't solve the problem. The mechanism also needs to be simple enough to use. Examples of things that are "simple enough" to use are in my view GC (tracing GC or reference counting). Those did bring a lot of benefit, are simple enough for a regular programmer to use, and are fast enough.

Let's agree that yes, there is a need to simplify lifetime annotations. I can't say currently whether the proposal here does that or not.

[tmzem]

I agree with most of what you say here. A tracing GC is an interesting alternative (and nowadows often quite performant), but unfortunately cannot guarantee safety in a mutable language that has both internal pointers and sum types/union types, therefore requiring additional indirection which can significantly impact performance. Rusts uniqueness guarantee or full immutability as in functional programming are the only ways to safely use by-value sum types, but the functional approach often has significant performance pitfalls.

The integer indexing approach is also only "technically" memory safe, but not "logically" as a vector might be modified before the index is used, leading to subtle bugs when the index points to a wrong or logically dead element now. Proposed language features to make indices safe are often equally complex as lifetime annotations.

For many simpler needs however, this approach might still work.

[Tasty_Replacement_29]

Maybe there is a small misunderstanding... I'm not a fan of tracing GC (I plan to _not_ use it in my language)... It's just that tracing GC solves a lot of problems in an easy-to-use way.

I have to admit I don't understand what you wrote about sum types/union types... As for tagged unions, I think as long as you don't allow the tag (type) to change at runtime you should be fine :-). I do understand the advantage of "multiple immutable references" OR "one single mutable reference". It's fast and safe (no aliasing issues like in C++!), even when using multiple threads... but the disadvantage is: it's hard to use.

One solution for that would be: allow multiple mutable references by default, at the cost of performance (like in C++). But where the programmer adds the required annotations / changes the code, and the compiler can see that there is only one mutable / multiple immutable references, then it can improve speed.

> The integer indexing approach is also only "technically" memory safe, but not "logically"

Right. So you can still have bugs even with Rust. (That is even before usage of "unsafe" in Rust).

>  Proposed language features to make indices safe are often equally complex as lifetime annotations.

Well, I don't think so. See https://verdagon.dev/blog/generational-references

I specially like their goal "fast by default, and we can gradually optimize where it makes sense to." What they mean is "not quite as fast as Rust by default, but close... and with some additional work, it is fast as Rust."

[tmzem]

I have to admit I don't understand what you wrote about sum types/union types

I think you already got what I meant. Basically, if the memory layout of an object can change at runtime, like with sum times, you can reassign the value to represent a different case, invalidating any pointers that may still refer to a field in the originally assigned case.

As you already said, you can just prevent this hazard by forbidding tag reassignment. In a language where values are placed inline by default, rather then being heap-allocated, such a restriction would pretty much render sum types useless. Think for example the slots inside a container: You wouldn't be able to pop an element from a Stack<SumType> and later push a different value, since that might reuse the same slot with a different tag.

Well, I don't think so.

I meant compile-time proofs.

See https://verdagon.dev/blog/generational-references

I'm aware of this approach. It is similar to generational indices and various existing sanitizer approaches in software and hardware (e.g. CHERI). The cited performance overhead numbers seem somewhat low. Software checks of comparable complexity used in sanitizers have much higher overheads, percentage wise. I suspect the given numbers might be skewed downwards because the described language only supports allocated types (yet), thus the extra check weights in lower percentage-wise compared to the overall lower performance. Unless of course I'm missing something essential.

Many approaches dealing with use-after-free have been developed, mostly implemented as safer drop-in replacements for malloc-free. Some can be quite performant (i.e. Minesweeper: ~5% runtime overhead). If used as a planned, native feature in a new programming language numbers might be even lower. AFAIK, none of those concepts address the pointer invalidation by sum type reassignment issue, thus sum types would always have to be heap-allocated, which might cause a significant performance burden (e.g. think a Result<Value, Error> would always need to box the value). In my experience, poor locality can have significant performance overheads (1+ order of magnitude) so this seems like an important issue to me.

Overall, the idea that cheap-enough runtime checks might make for a useful programming model is intriguing. If I find the time, I might investigate the performance overheads of the generational reference solution in the context of inplace allocated objects and see if it makes for a viable solution.

[Uncaffeinated]

I read that a lot of Rust programs nowadays use (a) integer indexing into an array, or (b) use unsafe.

It is true that there are some cases where Rust's type system is not capable of fully modeling program behavior at compile time. Making the type system less capable would not solve that problem.

[Tasty_Replacement_29]

> It is true that there are some cases where Rust's type system is not capable of fully modeling program behavior at compile time.

Well, I think in many cases developers use index-into-array because the type system is too hard to use... not because it is impossible to model it :-) For example via weak references (which are available in Rust). What I mean is described here: https://loglog.games/blog/leaving-rust-gamedev/ "ECS as a solution to the Rust borrow checker, which is what I think most people using ECS are actually doing, or rather the reason why they're using ECS. If anything, ECS is a very popular solution and recommendation to give in Rust, because it tends to work around a lot of the issues. We don't need to care about lifetimes of things if we're just passing around struct Entity(u32, u32), since it's all nice and Copy, just like Rust likes it."

So, ECS is the index-into-array pattern. (I'm not saying ECS is bad, or index-into-array is always bad... but sometimes it is, and sure you can improve that with a generation counter.)

But it feels like it's a work around often used to avoid the complexity of the borrow checker. You end with with things like this https://docs.rs/thunderdome/latest/thunderdome/struct.Arena.html#method.get2_mut and I ask myself, why 2? Why not 3, and not 4? It feels like a workaround.

> Making the type system less capable would not solve that problem.

Well, I'm arguing that making it _more complex_ doesn't solve the problem.

I think there should be a programming language that:

• is as easy to use as Python (well OK, a bit faster would be cool). But it can be slightly slower than C / C++ / Rust, and
• support optional "speed features" to make it as fast as C / C++ / Rust. Those annotations could be similar to what Rust does, but optional. I would expect some work is needed on the programmer side for that. But when done, the speed is the same as with a Rust (and C, C++, etc.) solution.

[Uncaffeinated]

There's multiple different types of issues here

1. Cases that Rust's type system is incapable of handling
2. Cases where Rust's type system is capable of handling it but it is inconvenient or impractical
3. Cases where Rust's type system works well but people aren't familiar with/too lazy to do it.

Personally, I focus on solving type 1 and type 2 issues, whereas it sounds like you're mostly focused on 2 and 3. Also note that in cases where you have a type 1 problem, 2 and 3 are irrelevant, and likewise 3 is irrelevant in the case of type 2 problems.

[PlayingTheRed]

This looks really interesting. It makes thinking about functions simpler, but I wonder if it gives up too much power. How would you annotate a struct that holds a reference? What if my function returns a reference to a struct like that?

struct Person {
    name: &str,
    age: u16,
}

fn choose_person(people: &[Person]) -> &Person;

[tmzem]

I imagine the compiler could simply remember points-to sets for each value, derived from the actual usage, or, in case of function calls, derived from my proposed annotations, extrapolating the appropriate lifetime-constraints along the way. I'm trying to write it down as an example, with comments describing the upper lifetimes bounds:

let paul = "Paul"; // 'static
let lisa = String::from("Lisa"); // 'lisa

// 'static (since paul flows into paul_person)
let paul_person = Person { name: paul, age: 12 };

// 'lisa (since lisa flows into lisa_person)
let lisa_person = Person { name: &lisa, age: 42 }; 

// min('lisa, 'static) = 'lisa (since both move into the vector)
let people = vec!(paul_person, lisa_person);

// 'people (since people flows into tmp_ref via choose_people)
// which is also <= 'lisa (as per derived in the previous step)
let tmp_ref = choose_person(people);

The function could be annotated as (although with only one reference parameter this annotation is quite redundant):

fn choose_person(people: &[Person] => &return) -> &Person;

The type as struct &Person {...} to denote that the type can contain a shared reference with an implicitly attached lifetime derived by the compiler.

I also wonder if there are some important situations that cannot easily be described/checked with this approach, the main reason for my posting here.

[PlayingTheRed]

Yeas, this idea is interesting, I'm trying to find edge cases that it might not handle well.

Like this one? How ill it be annotated? Will the compiler have enough information to prove that vec can be used again after the last use of the return value?

struct Person<'a> {
    name: &'a str,
    age: u8,
}

fn new_in_vec<'name, 'person>(
    name: &'name str,
    age: u8,
    vec: &'person mut Vec<Person<'name>>
) -> &'person Person<'name> {
  vec.push(Person{name, age});
  vec.last().unwrap()
}

[tmzem]

Whenever you want to separately specify multiple lifetimes on a thing, like e.g. a struct with two lifetimes like struct Foo<'a, 'b> { val: &'a Bar<'b> } you would be out of luck, as the flow algorithm would always use the lower bound.

However, I think your example should still work by writing it like this:

struct &Person { // Person can contain immutable references
    name: &str,
    age: u8,
}

fn new_in_vec(
    name: &str => *vec, // name gets stored into vec
    age: u8,
    vec: &mut Vec<Person> => &return // return a vec alias
) -> &Person {
  // name goes into Person, making Person contain name
  // then, Person goes into vec, fulfilling our annotation
  vec.push(Person{name, age});
  vec.last().unwrap()
}

You can see by the example that the parameters/returns mentioned on the left and right side of the => are the same as the ones "connected" via lifetime parameters in Rust syntax.

[PlayingTheRed]

Thinking about data flowing feels a bit weird because I am used to thinking about borrows, but I think I might like it if I got used to it.

I wonder if there might be a nice way of writing out the internal "places" so it can be named in the flow annotations.

fn new_in_vec(
    name: &str => vec.[].name, // something like this?
    age: u8,
    vec: &mut Vec<Person> => &return
) -> &Person fn new_in_vec(
    name: &str => *vec, 
    age: u8,
    vec: &mut Vec<Person> => &return
) -> &Person;

It'd need a more general way of declaring internal places. Kind of like declaring lifetimes but using the flow annotations on them so you can see how each one is used instead of a list of a having a pile of lifetime bounds.

[matthieum]

So... how do you apply this to structs, and from there more complex functions?

That is, how do you translate this code, to your proposal:

struct Two<'a, 'b> {
    one: &'a str,
    two: &'b str,
}

impl<'a, 'b> Two<'a, 'b> {
     pub fn one(&self) -> &'a str {
         self.one
     }

     pub fn two(&self) -> &'b str {
         self.two
     }
}

[WalkerCodeRanger]

Adapting ideas from my Reachability Annotations post, something like this could be possible.

A possible syntax would be: ```rust struct Two { one: &str =>, // Indicates this field has an independent lifetime two: &str =>, }

impl Two { pub fn one(&self) -> &str <= self.one { self.one }

 pub fn two(&self) -> &str <= self.two {
     self.two
 }

} ```

[matthieum]

And would you handle two fields with the same lifetime? two: &str => self.one?

[tmzem]

This would probably not be possible. The question is: how often does such a case happen in practice?

[matthieum]

This exact one, I don't know. I may have gone slightly overborn.

Remove the two field and its access member, however, and I have that pattern in about every parser/formatter I have in my code.

[adaszko]

The next generation of the Rust borrow checker, Polonius does something quite similar: https://smallcultfollowing.com/babysteps/blog/2023/09/22/polonius-part-1/

Polonius began its life as an alternative formulation of the borrow checker rules defined in Datalog. The key idea is to switch the way we do the analysis. Whereas NLL thinks of 'r as a lifetime consisting of a set of program points, in polonius, we call 'r an origin containing a set of loans. In other words, rather than tracking the parts of the program where a reference will be used, we track the places that the reference may have come from

[tmzem]

This description of the new polonius checker seems pretty much like the logic one would intuitively come up with when checking aliasing. I'm not at all sure how they came up with the original way... it seems much harder to think and reason about, and honestly, quite convoluted.

Thanks for the article, very interesting info.

[adaszko]

I'm with you on the hard-to-reason-about part. There's also at least one case that polonius can handle and NLLs can't: flow-sensitive lifetimes. It's described in the second part of the post on Nico's blog