Borrow/move/closure symantics are driving me to my wit's end

[Laphicet]

I'm going to say right now I am having a royal pain of a time learning Rust that makes my learning of C++ pointers a decade ago pale by comparison. I've had this what I believe to be VERY erroneous quad tree implementation. While I could address one particular concern, it seems whenever I get an answer, be it asking here or finding a supposed solution, Rust seems to throw me another curve ball of monumental confusion to me and capsize what I thought I just learned.

At this point, here is the link to the entire code file. I feel that by doing this, someone might be able to see what I'm trying to do on the whole. http://pasteall.org/484922

I'm getting Cargo/rustc complaining about moved closures, can't borrow immutables as mutable despite what I believe to be mutable references, can't move 'self' out of borrowed context, etc etc. I'm frequently breaking everytime I try to tackle this and Rust just buries me under this whenever I try to fix it.

[vitalyd]

Did you ever read the Rust book or some other material? I'd guess you might be missing some fundamental understanding of how Rust works, but I could be wrong.

As for getting help, it's easier if you ask piecemeal questions with a distilled example - it's easier to answer and provide an explanation on why things are as they are.

[vitalyd]

For instance, why do push and subdiv take a &'a mut self instead of &mut self? By making the mutable borrow last for 'a, which is the lifetime parameter of the struct itself, you're going to make the borrow last until the whole struct dies, which is not what you want.

[leonardo]

The kind of programs that are easy to write in C (like a double linked list) is not necessarily easy to write in Rust.
A first suggestion is to remove all (or most) unwrap() from your code, and use match or if lets.

[vitalyd]

Another pattern I spotted that you hinted at giving you trouble is in select:

fn select<F: Fn(...) -> bool>(..., pred: F) {
 ...
 for x in ... {
   select(..., pred);
 }
}

Each time you enter the loop the pred closure is moved, and Rust will disallow this whole construct. Instead, you can try passing pred: &F to the function.

[vitalyd]

@leonardo

The kind of programs that are easy to write in C (like a double linked list)

Easy to pass compilation ...

[vitalyd]

In push there's a code fragment like this:

item.set_node(Some(&*self));
self.items.push(item);

Note that self is mutably borrowed when push is called. The first line above tries to obtain an immutable borrow while the mutable one is active - that violates Rust's borrow rules.

Also, you're trying to create a bidirectional relationship between the quadtree node and the items it holds. It's best to avoid this type of thing precisely because it easily leads to borrow problems.

[Laphicet]

Alright, I'm jotting all this down and I'll take a crack at it tomorrow. Maybe the 'a lifetime is the thorn in my side for 'self' parameters. Doing away with that should help me a lot.

For the record, I did make this same quad tree in C++ and it works. The problem is that... well, it's C++. I'm most likely eventually going to shoot myself in the foot and spend many hours in GDB/Valgrind/medicine cabinet looking for Ibuprofin lol

And yeah, I've looked over the Rust book, API ref, Stack Overflow quite a bit... I think maybe I have a slow learning disability.

[vitalyd]

@Laphicet

And yeah, I’ve looked over the Rust book, API ref, Stack Overflow quite a bit

Then it's just a matter of practice/experience/familiarity. It takes some time (and practice) for the stuff to sink in. Also, it's very important to understand why something didn't work, and why a solution does, rather than just hacking away until the compiler shuts up . Learning Rust requires patience and deliberateness in the process.

[Laphicet]

So I've attempted to take the lifetime out of &mut self in push() only to get this. I renamed the 'a lifetime to 'node to be a bit clearer. I kept the lifetime in subdiv() because otherwise I'd get E0495 for that too.

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
   --> src/quadtree.rs:150:43
    |
150 |                           if self.depth < self.max_depth { self.subdiv(); }
    |                                                                 ^^^^^^
    |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 144:2...
   --> src/quadtree.rs:144:2
    |
144 | /         pub fn push(&mut self, mut item: T) -> bool
145 | |         {
146 | |                 if self.bounds.contains_vec(item.position())
147 | |                 {
...   |
167 | |                 }
168 | |         }
    | |__^
note: ...so that reference does not outlive borrowed content
   --> src/quadtree.rs:150:38
    |
150 |                           if self.depth < self.max_depth { self.subdiv(); }
    |                                                            ^^^^
note: but, the lifetime must be valid for the lifetime 'node as defined on the impl at 20:1...
   --> src/quadtree.rs:20:1
    |
20  | / impl<'node, T> QuadTreeNode<'node, T> where T: QuadTreeItem<T> + PartialEq
21  | | {
22  | |         pub fn count(&self) -> i32
23  | |         {
...   |
280 | |         }
281 | | }
    | |_^
note: ...so that types are compatible (expected &mut QuadTreeNode<'_, T>, found &mut QuadTreeNode<'node, T>)
   --> src/quadtree.rs:150:43
    |
150 |                           if self.depth < self.max_depth { self.subdiv(); }

[vitalyd]

In short, I think you're bumping up against the borrow checker due to the bidirectional relationship you have in the design.

You cannot remove the lifetime in push because subdiv then needs it, and you get the conflict error above. You cannot remove it from subdiv because it calls new_child, which also has the 'node lifetime - that's likely the other lifetime conflict error you got. new_child in turn tries to associate the new node's parent to be the current node, and you now end up with the borrow problem I alluded to earlier.

A few options, roughly in the order I'd consider them:

1. Rethink the design to avoid circularity.
2. Use Rc for shared ownership (instead of references)
3. Use handles instead of references. By handle, I mean something like an integer that somehow can be used to identify the related node (e.g. by being an index into a Vec or some such). I believe this approach is used by some datastructure libs that run into similar reference cycles (e.g. graphs)
4. Use raw pointers and unsafe code to arrange the circularity.

[Michael-F-Bryan]

This doesn't solve your problem exactly, but i would highly recommend checking out learn Rust with too many linked lists if you haven't already.

It's a tutorial someone put together where you go through step by step and make these kinds of more complicated data structures which the borrow checker doesn't like (because of multiple mutable references and all that). They shows how you can do a doubly linked list, which tackles the same problems you're having, without resorting to unsafe or needing to make a trip to the medicine cabinet.

[carols10cents]

@Michael-F-Bryan

It’s a tutorial someone put together

That someone is @Gankra

@vitalyd

2. Use Rc for shared ownership (instead of references)

Agree! We have a section in the book on Weak references that I hope is useful here. I would be interested to hear if that section of the book doesn't help

@vitalyd

3. Use handles instead of references. By handle, I mean something like an integer that somehow can be used to identify the related node (e.g. by being an index into a Vec or some such). I believe this approach is used by some datastructure libs that run into similar reference cycles (e.g. graphs)

This is the strategy taken by petgraph, you might want to see if petgraph works for your situation.

[donallen]

I have written code in everything from assembly code for many machines, through Fortran, PL/1, Lisp, Scheme, TCL, Python, C, C++, Haskell, Go and Rust (and I'm sure there are some I've forgotten). This is over the course of 57 years of programming (I wrote my first line of code in 1960! And I'm still at it). Rust was by far the most difficult to learn. Haskell has been called a language "designed by geniuses for geniuses" and I found it less difficult to learn than Rust, in the sense of being able to write code fluently. The languages are similar in the sense that you need to make a very demanding compiler happy and it did take a while with my first attempts at Haskell to understand why the compiler was grumping at me. But Rust takes this to another level.

It's hard to know exactly why this is. I've been critical of the documentation in the past, but that is getting fixed and while I have stopped actively developing code in Rust, I've looked at the documentation periodically and the new attempt is certainly an improvement. But I'm wondering whether the basic idea of Rust -- memory safety without runtime overhead -- is really worth it. I stopped developing in Rust awhile ago because of the kind of frustration you've encountered. If I don't need ultimate performance, which is most of the time, I tend to do my development in Haskell. As with Rust, once you convince the compiler that you know what you are doing, you are usually very close to a correct program. But I find the Haskell compiler (ghc) much easier to convince.

When I do need ultimate performance, I use C. Yes, the language has its warts, but we know what they are and having written an awful lot of it, I know how to use the language and write memory-safe code with it (verified by lack of seg-faults and some time spent with valgrind). The documentation is beyond reproach, the supporting libraries and compilers are first rate. In other words, it's mature software and it works very, very well.

What I'm saying is that, at least from my perspective, Rust's cost-benefit proposition doesn't work, at least not yet. Perhaps once the new documentation is finished and had some time to mature, I might find a reason to give it another try. But so far, I've found that it just wasn't worth the effort, given the available alternatives.

[vitalyd]

That's quite the language resume

Curious if you could enumerate the issues you found difficult in Rust? Not disputing that it's a fairly complex language, but wondering if you could pinpoint the problem areas.

[HadrienG]

It also took me two tries before I "got" Rust, so I totally understand your point of view and would recommend that you give it another try later on, for example after the documentation has matured some more.

Things which helped in my case:

• Pascal as a first programming language, and some experience in Ada. When you come from this perspective, "strict" languages feel helpful rather than demanding: the more the compiler and runtime catch for you, the less manual debugging you need to do. From this PoV, needing to resort often to run-time tools like gdb and valgrind, and thus to rely exclusively on manually written tests (which are incomplete by nature, test coverage tools providing a very poor approximation of reality in generic or highly dynamic code) feels like a regression.
• Learning OCaml. Rust has a very strong inspiration from the ML family (which Haskell also has close ties with), and when you're fluent with things like type inference, optional mutability that is off by default, and functional-style interfaces, Rust's design makes a lot more sense.
• Lots of negative experience from the build systems of other compiled programming languages. Spending way too much time a day fighting with raw Makefiles, undocumented shell scripts and kLOCs of CMake makes you realize how great of an achievement Cargo truly is.
• Lots of negative experience from the generic programming facilities of other programming languages. TypeError in python, template error vomit in C++, strange diagnostics deep in the implementation in OCaml... it makes you realize how fine the line between duck typing and anarchy truly is. I discovered the joy of well-specified generic interfaces in Ada and never came back.
• Working in the area of high-performance scientific programming. When a key part of your job is to get people who are not passionnate about programming to write multi-threaded code, you realize to which extent better tools are needed in this department.

In the end, for me, the memory safety is one important thing about Rust, because it allows me to write high-performance zero-copy or multithreaded code with a lot more confidence. But it's not the heart of the language. To me, the most important thing in Rust is how much it managed to bring together a lot of good ideas from other languages, and to build a language which is strict, performance-oriented, and readable at the same time.

And like @vitalyd, I'd love to know more about the things which make Rust hard to learn for you, in order to see whether it is essential complexity (things which are a direct byproduct of Rust's design goals) or accidental complication (things which are unneeded and can potentially be fixed by a future language revision).

[donallen]

Responding to both you and Vitaly:

The biggest issue for me in terms of learning the language was lifetimes.
This was at the time when the second iteration of "The Book" had either not
been started or was in its earliest stage. So the only documentation on
lifetimes I had to rely on was that in the original Book, and lets just say
that it was totally inadequate. I've had a lot to say about this on this
forum in the past.

Another issue was the quality of the documentation. It simply wasn't good
enough (for me) at the time I threw up my hands. I've also talked about
this on this forum in the past and have submitted issues. As I said
earlier, I think the second iteration is clearly an improvement, but the
documentation is still not at the level of that written for competing
languages. And some of the library documentation, e.g., rusqlite, is just
pitiful.

But with some persistence and my friend, Google, I managed to write some
actual code. I wrote a fair amount of it, but problems kept coming up with
lifetimes, complaints about references not being mutable when they appeared
to be, and other things. I can't be specific without doing some digging, as
it was last year and I've forgotten the details (I am almost 75 years
old, which is sort of necessary if you have been doing this as long as I
have). I finally sat back and asked myself "why am I doing this?". It was
just too much effort, too much cost to write the code and what was the
benefit? From a cost-benefit perspective, it simply didn't make sense, for
me.

[vitalyd]

It'd be nice to see specifics for those problems you encountered, but I understand it requires you to dig. If you do find the time/willingness to do that, please report back.

In terms of documentation, I think your concern is very valid. Despite @carols10cents and @steveklabnik great efforts, it'll likely take several iterations (i.e. beyond the 2nd edition) before it's in a really good state. I think they've done a terrific job up to this point, but I do think the language's complexity exceeds the thoroughness of the current documentation. That said, there's no reason "3rd party" authors can't create great supplementary reading (or even primary). For instance, O'Reilly's Programming Rust (Programming Rust [Book]) is a great book as-is, even though it's still in development. I highly recommend it to get a nice grounding in the language.

As @HadrienG mentioned, it may take a few tries for Rust to "click". The ecosystem is maturing, the docs are getting better, compiler messages (for some things) get better, helpful linting is available (i.e. clippy), IDE support gets better, and so on.

[Dragonrun1]

Just a suggestion for helping with some of the bi-directional ref issues you seem to have ran into you might want to look into Weak references as they are meant to solve those types of problems. Just from a quick look at the code I think some of the lifetime issues might go away by using them.

To the rest of the posts about finding Rust so hard to learn I think In part for people that have a lot of experience with other programming languages it much harder in some ways because we all come with expectations because things have similar names or ideas in Rust we assume they will act like other languages we already know and that trips us up. As at least one other person has said that until you "get Rust" and some of it's core ideas and how they effect everything you thought you knew it does seem to fight you. I'm finally getting to the point where it reports an error I know what old habit I've fell back into based on what error I'm getting. The learning curve has been higher it seems with Rust but now when I go back to other languages I realize how many things I never even thought about before that I should have been that could be bugs and I'm becoming a better programmer as a result of learning it.

[dobkeratops]

@donallen

What I’m saying is that, at least from my perspective, Rust’s cost-benefit proposition doesn’t work, at least not yet. Perhaps once the new documentation is finished and had some time to mature, I might find a reason to give it another try. But so far, I’ve found that it just wasn’t worth the effort, given the available alternatives.

just 30 years of programming here,

I find rust very interesting, their goal is worthwhile, but IMO they should have an option to switch off the borrow checker (just make it warnings) they can call something else if they are really offended by that, but then we could have the best of both worlds. maybe a #[] that flags every function as unsafe etc.

the point I keep making is there's other classes of error that you still need to write tests to detect, so the compile-time safety (front-loading of work) isn't always a win (although I know why they want it, web-safety)

What interests me more is not the fact that it doesn't allow faulty code - we could retrofit a static analyser and use templates to label references in C++; it's all the extra forms that make safe code easier to write (the enum/match, expression based syntax making it easier to avoid uninitialised variables, etc). Tuples allowing multiple return values mean less need to pass pointers around. etc etc.

There's reasons other than safety to want a C or C++ replacement (these languages have awful syntactic cruft; rust is much cleaner)

I'm sure eventually tooling will get better that suggests how to fix the checker issues, and the checker can get smarter (it has to over-estimate. i see threads about non-lexical lifetimes..)