You almost never want &Box<T>, you are better served by just having &T
You can use arenas to better make things more managable,
/// goup id definition
type Gid = usize;
type Value = Option<usize>;
pub struct Data {
cases: Vec<Case>,
groups: Vec<Group>,
}
// refers to some case in Data::cases
struct CaseIndex(usize);
// refers to some group in Data::groups
struct GroupIndex(usize);
pub struct Grid {
cases: Vec<Vec<CaseIndex>>,
groups: HashMap<usize, GroupIndex>,
}
pub struct Case {
group: GroupIndex,
value: Value,
coord: (usize, usize),
}
pub struct Group {
id: Gid,
cases: Vec<CaseIndex>,
}
If you're a beginner, don't use temporary borrows & in structs anywhere. Avoid them. struct …<'a> means you'll have a bad day. They don't do what you think they do (they're not for storing things by reference! They are read-only locks and views of data stored elsewhere).
To expand on what @kornel said, &'a mut self is also a bad idea, unless you already understand lifetimes*, don't use/annotate lifetimes excessively in your code. Lifetimes are very complex and can easily make your code unusable if done incorrectly.
Think of references as temporary views to a value. References are also compile time locks. These two together mean that you can't use references like pointers in C++ or in every other GC language. Putting references in a data--structure is always a performance optimization. Don't optimize prematurely.
* by this I mean you aren't fighting the borrow checker
I have a C/C++ background, my first mistake is to try to reproduce what I know (in C++, I would have used shared_ptr).
I could have tried to used Rc, but I think it is definitly more complex and more error-prone!
Thank you for your advices. Rust is my hobby language. My employer doesn't want to use it for our customers for the moment, considering it as a "passing trend" (deepl/google translation).
Tangential: I don't understand this new trend of people writing "references are not pointers BUT compile-time locks". They are both. They are pointers with compile-time lifetime and exclusive mutability ("rwlock" if you like) checking. Being indirect (ie. being pointers) is a fundamental aspect of their semantics.
It's because thinking of references as pointers usually doesn't lead to correct code for Rust beginners. Pointers are a familiar concept from other languages, which leads to some expectations around how references should work. (Given that references are pointers)
It is more likely to give them a better understanding of references if they think of them as temporary views/compile time locks, rather than pointers.
I think explaining that references are temporary views is close enough to the relavant pointer semantics to be useful, but without also bringing in all the baggage that pointers seem to imply.
But how do you explain "views" without indirection? (By that I'm trying to say that "views" is a lot less common concept or term than pointers in the context of programming, and I think this is why they deserve some additional elaboration, which, however, still needs to talk about indirection, i.e. the absence of moving/copying, which almost always works by simply taking a pointer under the hood.)
Furthermore, if you mean "references do not imply heap allocation or GC" (I'm not sure if you do), why not just write that? It's a simple enough fact that stands on its own and doesn't require more discussion.
I think that Rust references need to be described as pointers that serve as access tokens to objects:
a) they provide either exclusive read/write access (& mut) or shared read access (&)
to the pointed-to object, and
b) they are only valid for a lifetime that is strictly less than the lifetime of the pointed-to object.
The Rust compiler validates that all use of such tokens meet their stated constraints.
"References aren't pointers" in the same way "Pointers aren't integers". Technically they are, but that's an implementation detail, not semantic equivalence.
You can't divide an integer by a pointer — it doesn't make any sense, even though integers can be divided. And you can't return or store a newly created object by Rust reference — it doesn't make any sense, even though pointers can be returned or stored.
No, not in the same way at all. Pointers have semantics to them. Furthermore, I can't make sense of this assertion:
You are conflating non-pointers and pointers here. It's perfectly possible and meaningful to return or store references. Just like you could return raw pointers. You can make a Vec<&T> or a HashMap<String, &Foo> or a fn() -> &str. The fact that these pointers are non-owning doesn't pertain to their indirect nature at all – they are very regular types in this regard.
You've misread "storing by reference" as "storing reference". You can't return or store a newly created object by a Rust reference, i.e.
fn new() -> &Vec<u8> {
return &vec![];
}
or
hash_set.insert(&format!("hello"));
These won't compile, because they don't make any sense for Rust references. In the C world of pointers the equivalents such as: struct Vec* new() and insert(struct HashSet *s, char *v) are fine. So if you come with a pointer mindset to Rust references, you'll be disappointed.
The differentiator is that references are about ownership. Pointers are agnostic about it, and references aren't. You can't pass ownership through Rust reference, even though it's possible to pass ownership by pointer.
I think that's reading too much into C pointers' semantics. In C, a pointer can be either owning or non-owning by convention, but this has nothing to do with its "pointer" nature. Just like, for example, you can make a reference to a stack-allocated or a heap-allocated value in Rust. The primary point of pointers is not ownership in C either, it's indirection, just like with Rust references.
It is counter-productive to conflate a general programming/architectural notion with the implementation thereof in a specific language. Pointers are a widely used, language-agnostic concept, appearing throughout computer science. Their purpose is indirection - just look at an algorithms and data structures textbook that doesn't use C as the language of implementation. It will still talk about "pointers" in a linked list or a tree.
Nobody asserted that Rust references are C pointers. Only that they fit into the more general, well-known definition of a pointer.
Yes, this is true, but that's not how many people will think about it, given that ownership is something most languages don't emphasize. They will conflate the ownership semantics with the pointer semantics. (Like in C or GC languages, which will lead to bugs that Rust tries to prevent). This is the sort of baggage that I am concerned with.
Based off of this thread, I think explaining references as non-owning temporary pointers and compile time locks is the way to go.
When I see people fight the borrow checker, it often looks like they assume it is true.
Other languages put emphasis on passing "by reference" (pointer) vs "by value". Rust splits passing of arguments into "by reference" (borrow) vs "owned".
These are completely different, incompatible ways of slicing the problem. C's "by reference" can be either borrowed or owned. And Rust's "passing ownership" can be by either by value or by reference! This is a very confusing mismatch:
by reference
copying
borrowed
&T
U<'t>
owned
Box<T>
T
So in my experience in teaching Rust it's very important to emphasize that C-style referencing meaning "not copying" is not related to Rust-style referencing meaning "not owning". In the table one cell overlaps exactly, creating an invalid mental model that they're equivalent. And then you end up putting a reference in a struct because you don't want copying, but Rust works along the other axis, and you end up not owning it.
The other day I had a little program working fine. Until I wanted to put a loop around the main processing. The overall plan was that the processing was in a method of a struct that contained it's related variables. But it used a lookup table contained in another struct. I had just passed the lookup to my Process::new. Of course wrapping a loop around it resulted in a "value moved" error.
After a bit of a discussion with the compiler I ended up passing my lookup struct by reference and then having to add lifetime "line noise" annotations to my processing struct.
An outline of the thing is in the playground Rust Playground including comments indicating how the compiler talked me into that solution.
I was not happy with that. I'm a Rust newbie that has never needed life time ticks before and has not read the chapter of the book. So I don't know exactly what I have written means.
Here's what you wrote means, one comment at a time.
// Added "<'a>" because of "undeclared lifetime name 'a" // Added "'a" because "missing lifetime specifier"
In Rust, every reference has an associated lifetime, checked at compile time. This is to ensure that a reference can't be created to an object that the reference outlives, in which case it would be possible to use a dangling reference and cause memory corruption.
The lifetime associated with the reference is usually not written out inside a function, because the compiler is smart enough to infer them from the context, just like it's smart enough to infer the types for most variables and expressions.
However, just like the compiler isn't able to infer the types of each field in a struct or enum declaration (because, after all, that's a situation where you want to tell the compiler what types to use), it can't infer lifetimes of references in such declarations either. Therefore, you need to tell the compiler that "here's an explicit lifetime for this reference because I'm declaring it now to be in this new type I'm creating right now". This is why you need to write table: &'a Table.
However, a lifetime is not a concrete type. Just like type arguments to generics, lifetimes will also be substituted by the compiler, based on how and where you use a value of the struct type you are declaring. So, they also need to be generic arguments. Except that they don't stand in for a type that will be known later; instead, they stand in for a lifetime that will be known later.
And since there is now a generic argument in the type of the field table: &'a Table, you need to tell the compiler where this 'a comes from. Only 'a is not meaningful in itself, just like the T in table: &'a T wouldn't be. So, you need to tell the compiler that it comes from the outside, by declaring it along with the generic arguments of the struct itself, and that's why you need to write struct Process<'a>.
This is analogous to why you have to name your value arguments in a function. You can't use an argument named foo inside your function body if you didn't declare that the function has an argument named foo. In fact, generic "types" aren't really types, it's more appropriate to think of them as type-level functions. Process<'a> is a type-level function that takes a lifetime as an argument and produces a concrete struct type. Too bad that concrete lifetimes can't be named syntactically, so here's an example with types only: Vec<T> is a type-level function that takes a type argument like String and produces a concrete vector type like Vec<String>.
// Added <'_> because "help: indicate the anonymous lifetime: <'_>"
For the same reason, because your struct now has a generic lifetime parameter, it's not just called Process, it's called Process<'a>. So the most correct incantation of its impl would be:
impl<'a> Process<'a> { … }
However, this is such a common pattern that the compiler lets you get away with not repeating the lifetime annotation and instead it just assumes (based on the already-existing declaration of the struct type) that by the <'_>, you are referring to the <'a> lifetime argument.
// Added reference to fix "..value moved here,"
By default, if you refer to a value as-is, it is taken by value, and is "moved". Since the loop potentially runs multiple times, moving a value that was created outside of it would lead to the use of a moved (ie. invalidated) value on the subsequent iteration. This is why you can't do it.
Wow H2CO3, thanks for taking the time on that comprehensive explanation. That is another post I will have to print out and hang on the wall. I was having a hard time with the lifetime section of the book but this will make it all clear I'm sure.
Of course those steps you outlined did not happen in in that order chronologically:
I have had the correct notion of lifetimes, owning and borrowing from the get go. And hence the need for pass by reference '&' and '&mut'. It's a syntax similar to references in C++, it reads nicely. So far so good.
The knock on effect of pass by reference there is the need for the thing referenced in the struct to live at least as long as the struct. Conceptually I think I had the right idea. Unfortunately the syntax starts to look like line noise and give me a hard time reading it.
That <'_> threw me. WTF? Your explanation clears that detail up.
However the fact that it's equivalent to "impl <'a> Process <'a>" now causes me difficulty. I can see the need for it but it's racking up the line noise quotient. The logic of the syntax is not clear:
What are those two "<'a>" saying exactly? How do I read that?
Why are there two of them on that one line?
Why do they need to be there at all? This is an imp of 'Process' which already has it's fair share of "'a ". Not only that the "'a" is not actually used anywhere in that impl block. Seems odd.
Anyway, with all that in place why is kornel saying "don't use temporary borrows & in structs anywhere. Avoid them. struct …<'a> means you'll have a bad day."