Improving self-referential structs

[Storyyeller]

Why can’t that example be represented as:

struct PreParsedString<'a> {
    str: &'a String,
    tokens: Vec<&'a str>
}

or some variation thereof? iow, the struct has references to both the original string and its tokens.

Because that still requires the String to be stored in a fixed location on the stack somewhere. The goal is to be able to pass it around arbitrarily, but right now you need crates like owning_ref or rental to do this.

Anyway, I think the “portable stack frames” idea has merit. It is often necessary to transform recursive code into iterative code in order to avoid running out of stack space. This involves simulating the stack on the heap (using a Vec<Box<Frame>> or similar). However, Rust’s borrow system requires borrowed data to have lifetimes tied to values that live on the actual stack, meaning there is no safe way to do this.

[beamspease]

Just wanted to chime in here that this limitation has been a massive pain for me using the Alex Crichton’s ssh2 library. I’d ideally like to have a Connector struct that my Object struct takes ownership of, that uses a connect() function. However…

1. I couldn’t get things to work using Options, because the references received by pattern-matching are transient.
2. I can’t take ownership of it otherwise, because of the inability to create self-referential structs.
3. I struggled somewhat with std::rc::Rc to try and follow his suggestion, but was ultimately unsuccessful.

Eventually I was able to work out a careful balance by only passing a reference to the Connector struct, doing the handshake in Connector::new(), and creating the Sftp etc objects in the connect() function. Then I needed to make the connection optional and found myself hassling with lifetimes again because the handshake in new() requires a mutable reference to the Session, moving it to the connect function requires me to upgrade the connect function to a mutable reference, and this in turn resulted in conflicts because of multiple mutable borrows or some other reason I don’t fully understand yet.

I’m not sure if this intended to force good design practices, but it’s been a real hassle that seems to make providing a simple API impossible without using reference-counting, unsafe, or some obscure workaround. I don’t want to force someone to have to create multiple structs and adhere to a specific initialization order every time they use my Object.

I like the idea of being able to specify references to fields on a struct as it’s being created (with default 'self lifetimes unless otherwise specified), and either have the compiler automatically determine the order, or require the developer to specify them in an order such that the prerequisite fields are created first.

[jpernst]

I like the idea of being able to specify references to fields on a struct as it’s being created (with default 'self lifetimes unless otherwise specified), and either have the compiler automatically determine the order, or require the developer to specify them in an order such that the prerequisite fields are created first.

I’m currently in the process of redesigning rental, and it will actually work basically as you describe. You’ll be able to define a struct with any number of fields, each of which implicitly creates a lifetime of the same name, and can borrow from previous fields arbitrarily deep. I’m feeling good about the design and hopefully it will be ready soon.

[beamspease]

rental

I strongly feel this should be a language feature. I can’t think of a technical reason this shouldn’t be doable from the POV of what’s going on with the stack, although someone mentioned what sounds like a compiler limitation earlier in the thread. This is something I’d definitely put in the ergonomic bin. If creating a self-reference were as easy as adding ‘&’ and the compiler adding an implicit 'self lifetime, I’d probably be able to figure it out in the first couple tries.

Having to hunt around for a library, and a tutorial on how to use that library, etc. just for this kind of thing detracts from the usefulness of the language because you get completely sidetracked from what you were doing. I appreciate the work, but this seems like one of those things that seems super-easy to someone super-experienced, but which is a major stumbling block for someone just getting started.

[jpernst]

Oh believe me, I totally agree. Rental exists as a stop gap until a hopeful eventual future time where it’s no longer necessary. In the meantime I’m trying very hard to make the new version feel as “natural” as possible, and will do a write up about it once it’s usable. Unfortunately 'self won’t work since it just doesn’t provide enough information to infer the lifetime relationships, but instead each field has its own lifetime that later fields can use.

[nikomatsakis]

Is your in-progress work for rental on a branch or some place I can take a look? As part of the canvas unsafe code effort I’d like to take a look at how the internals work.

[jpernst]

Sure. The latest work is happening here. Still under heavy development, but the core functionality is in and working.

[jpernst]

Bleh, spoke too soon I suppose. I appear to have slammed hard into the HRTB-associated-item-unification brick wall against which even transmute is powerless. Unless I can find some clever way to coax the compiler into unifying the types, there’s not much else I can do for now. I’ll probably just park this until the trait system refactor. To be fair though, I’m silently relying on drop order right now anyway, so I didn’t want to release until that’s specified either, so it’s not that big of a deal I suppose.

[jpernst]

Ok, after a few more days of banging on this, I’m going to fall back to extracting the type information I need syntactically instead of relying on an associated type. This is a terrible hack, but at least the current associated type machinery in place allows me to ensure that the syntactically extracted type is correct. This means incorrect uses won’t compile, but some correct uses won’t compile either. That’s an acceptable compromise for now, though, and I’ll lift it as soon as the compiler allows me to.

[jpernst]

I’ve reached what I’m confident in calling the 0.4 milestone. It should now be in a much more stable state for examination. More changes will occur as enabling language features land, but the bulk of the work is done, and further features will be relatively minor changes.

[beamspease]

I just wanted to chime in here that this is a major problem for me. I’ve run into multiple cases where I have a struct that should have ownership of an object and things derived from that object, but I can’t do it without workarounds or contorting my API to introduce extra layers, which increases the complexity to users of that API.

[Fylwind]

I dwelled a bit on the idea of existential lifetimes and I think it’s actually feasible and (surprisingly) safe. Unsafety should only be necessary if you try to store a short-lived reference inside a long-lived existential object − that requires a transmute.

I’m not totally sure whether this holds water, but it made sense in my head when I wrote it. I would appreciate any comments and reviews!

Rufflewind/_urandom/blob/968c603a285e41dfdb09266f0f767da069bd9bfb/rust/existential-lifetimes-and-self-referential-objects.md

[newpavlov]

Can’t we introduce the following syntax (or something alike)?

struct Foo {
    // this field references other owned field and should be dropped before it
    a: &'a [u8],
    // 'a is "defined" here and tied to owned object stored in this field
    b: 'a Vec<u8>,
}

This way we define ordered acyclic graph of lifeteimes which generalizes notion of portable stack-frame mentioned by @jpernst .

[dan_t]

Can we introduce the following syntax (or something alike)?

struct Foo { // this field references other owned field and should be dropped before it a: &'a [u8], // 'a is “defined” here and tied to owned object stored in this field b: 'a Vec, }

This way we define ordered acyclic graph of lifeteimes which generalizes notion of portable stack-frame mentioned by @jpernst .

Sorry, I haven’t followed this discussion, but seeing this syntax my first thought was: why not using the field name as a lifetime?

struct Foo {
    b: Vec<u8>,
}

[jpernst]

Rental takes the approach of just using the field name as the lifetime name, and I think it’s been working quite well so far. My hope is that an eventual built-in language feature will work similarly.

[jpernst]

This thread is another good case in point for this, and the conclusion is exactly the kind of thing I was afraid would start happening in the ecosystem. Nothing really new about this one, but I just think it’s important to maintain awareness that this is an ongoing issue with practical implications.

[spease]

This is once again a blocking problem for me. Literally spent hours today solely because of this.

This is making me feel very conflicted for using Rust for stuff. This seems to create problems a lot, especially where the desirable pattern is to consume / take ownership of an object. Since self-referential structs are not directly possible in Rust, this implicitly forces me to pull in Rental and use special syntax to work with such structs. I’m legit not sure how more people aren’t running into this (or maybe they are and they just never get to this ticket because they give up before then).

If there is an intended alternative or people simply don’t believe it’s an issue, please let me know. At the point that I have to reference count everything anyway, then I start to wonder if it’s really something I should be trying to write in Rust or if I’m trying to bend the language in a way that it wasn’t meant to go.

Thanks.

[rpjohnst]

Can you be more specific about your use case? People do run into this, which is why rental exists at all, but it is relatively uncommon.

My suspicion, from personal experience, is that most problems can be solved a slightly different way that doesn’t involve self-reference.

[jpernst]

Suffice it to say I disagree that a small adjustment is all it usually takes to fix the issue. The core problem is that rust lifetimes are immune to encapsulation. Once a struct exposes a lifetime param, any structs that contain it will also be infected with that param. There’s no way (other than something like rental) to just encapsulate such a relationship as an implementation detail and wrap it in an opaque object that the user doesn’t need to worry about.

The cleanest way out of this situation is to just not use lifetime params in lieu of something like Rc or Arc. This is fine if you control the full vertical stack of your app, but that’s not necessarily true. That thread I just linked above gives an example of someone willing to fork their dependency to resolve this issue. This talk at RustFest Zürich also makes a solid case for not using lifetimes when your objects are “long lived”. I completely agree with his conclusion, but the problem is there’s no way to clearly decide if a type is truly “long lived” or not.

The library author has to guess what scenarios their crate is likely to be used in and how long people are likely to hold onto the structs, but it’s just that, a guess. If i want to play it safe and allow my library to be fully general I have to use Rc/Arc, since using those don’t preclude any particular use case, whereas using a lifetime relationship does. Even in cases where a lifetime relationship seems clearly the correct choice, it still prevents encapsulation.

I don’t think it’s any kind of anti-pattern to want to encapsulate an ownership relationship, and making this possible will allow crate authors to use lifetimes in cases where they seem natural, without concern for what impact that will have on downstream’s ability to build abstractions. Rental is the best I could manage with the current language, but it’s still painfully awkward and unergonomic enough that forking dependencies still feels like a better choice in some cases.

[rpjohnst]

I’m not disputing any of that, other than the frequency with which I run into it- I just wanted to hear more about @spease’s particular use case. “Encapsulating lifetimes” is so general that it’s essentially just restating the problem.

But to give my equally-general solution, I prefer to expose the owner and the reference separately as far up the stack as possible. When this works out (apparently more often for me than for you) it is far more flexible than either Rc/Arc or self-reference, both of which preclude some use cases.