I apologize that the example isn't tiny, but I had such an example and the responses that I got on irc suggest that too much context was lost.
Basically, I've written a parser for a packet-based stream. Some of the packets are containers (e.g., an encryption container and a compression container). These containers can contain any other valid packet. This can result in deep nesting, but in practice the amount of nesting is limited. The containers are implemented as filters. When parsing a packet, we effectively have a pipeline.
I've tried to design an API that allow progressively parsing the stream. The idea is that the user creates a MessageParser for some data source and calls pp = mp.next() to get the next PacketParser and mp.recurse(pp) to enter a container. Entering a container means creating a ContainerParser and pushing it on the stack, which is stored in the MessageParser (thus, MessageParser owns all of the containers). The data structure looks like:
Note: I can't change the decompressor to, say, own file, because when the decompressor's ContainerParser is popped from the stack, the top-level ContainerParser needs to read the next packet from file.
Is Rust's lifetime system not able to handle what I want to do? If it can, I'd appreciate any tips about how to accomplish that. And, more immediately, I'd appreciate any insight into the error that I'm currently getting.
This returns PacketParser tied to &mut self lifetime. There's no other way, because the function uses self.reader.as_mut().
So the exclusive access from self is passed down to PacketParser, so after mp.next() runs you can't use mp again for as long as pp is alive.
You can't use both at the same time, because it would allow modifying the same reader data from 2 places: mp.reader and pp.reader, and Rust doesn't allow mutable aliasing.
You could wrap the reader in RefCell (instead of &mut reader use &RefCell<reader> and borrow_mut() when needed), which changes exclusive mutability check from strict compile time to lax runtime check.
At least for me, commenting out the line you indicated actually doesn’t remove the lifetime error.
Which makes sense. The direct cause seems to be: Because MessageParser::next takes &’a mut self, calling it tells the compiler that the MessageParser itself must outlive the lifetime parameter in its type (’a), and indeed will be mutably borrowed for the remainder of that lifetime. Therefore, it must be dropped/destructed after that lifetime ends. But it (indirectly) contains a trait object which can hold references with lifetime ’a, and could have a destructor which accessed those references. So it would be unsafe to run that destructor after 'a ends! At least, I’m pretty sure that’s the cause.
More generally, I can see two problems with your design:
It seems like you’re trying to store intermediate packets side-by-side with ContainerParsers that hold references to them (in PacketOrContainerParser::Container). But that would be fundamentally unsafe, because nothing prevents you from changing the packet field to point to a new packet (with a different buffer) while the parser still exists. (Even if you changed the packet type to avoid the heap, there would be the potential of moving the enum value itself in memory.) The most direct way to make this work would be using the rental crate, but there’s probably a simpler approach. Why not make the parsers own any temporary buffers they need?
It seems like you want successive entries in the containers array to mutably borrow previous ones, but that can’t be proved safe; what stops you from accessing the previous ones directly? Consider a design that avoids the need for an array like that. [edit: In particular, if parsers own their temporary buffers, there should be no need to have a list of parsers at all.]
(Edit: @kornel's diagnosis is basically a different perspective on mine. MessageParser::next can't work the way you want it to, for the reason he explained, which I mentioned more briefly in point 2 above. You got it that method compile anyway by messing up the lifetime declaration - requiring &'a mut self instead of &mut self - which in turn created a lifetime error in count_packets for the reason I described.)
(Edit 2: Just out of my curiosity - you don't need to understand this: If you change &'a mut self to &'a self, and remove the method body, it compiles. But any number of changes break that, including implementing Drop for MessageParser - which would trigger drop check, requiring MessageParser to strictly outlive its lifetime parameter - or just adding something like RefCell<anything containing 'u8> in either MessageParser or ContainerParser, which would make the lifetime parameter invariant. As is, MessageParser is variant in its lifetime parameter, which means that a &MessageParser<'longer_lifetime> with a larger lifetime can be temporarily treated as a &MessageParser<'shorter_lifetime>. Not with &mut though, since with an &mut MessageParser<'shorter_lifetime> you could stash a ContainerParser<'shorter_lifetime>' in one of the containers.)
I would still be concerned even if writing the changes below, since there is a lot content with the same lifetime. RefCell likely better to comprehend, or maybe using closures.
First problem;
Comments are lies, since the code fails still without this.
// Commenting out the following line "solves" the lifetime issue.
To me the compiler is messing up and not pointing out the error is in next. You can't use iterator which will borrow and return a inside field which also borrows.
Removing the iter is easy;
D'oh
The subsequent error correctly reports in next.
To get around this I think rental crate or similar is needed.
Maybe instead you want to take? Which changes program data significantly.
Second problem
As @kornel point out next return value keeps the mutable borrow on mp.
The trick here is for recurse to instead take the unused part of the slice. Which again will modify next so it return a tuple. split_at_mut gives the code access.