I'm starting with Rust, and I'm already facing problems with data ownership.
I want to implement a generic struct called Port<T> that has a vector of values Vec<T>. Also, this struct has a vector of reference-counting pointers to other structs of the same type, Vec<Rc<Port<T>>>:
use std::slice::Iter;
use std::rc::Rc;
pub struct Port<T> {
values: Vec<T>,
ports: Vec<Rc<Port<T>>>,
}
The idea is the following: there are multiple structures of type Port<T>. You can add a value of type T to a given port. Each port stores these values in its values attribute. However, it is possible to "chain" one port to others using reference-counting pointers:
impl <T> Port<T> {
pub fn new() -> Self {
Self { values: vec![], ports: vec![] }
}
pub fn add_value(&mut self, value: T) {
self.values.push(value);
}
pub fn chain_port(&mut self, port: Rc<Port<T>>) {
if !port.is_empty() {
self.ports.push(port)
}
}
pub fn is_empty(&self) -> bool {
self.values.is_empty() || self.ports.is_empty()
}
pub fn clear(&mut self) {
self.values.clear();
self.ports.clear();
}
}
So far, the code compiles. Now, I want to implement an iterator for a port that returns references to the values owned by this port but also references to values generated by an iterator of every chained port:
pub struct PortIterator<'a, T> {
values: Iter<'a, T>, // Iterates over values owned by Port<T>
port: Option<Box<PortIterator<'a, T>>>, // Pointer to current port iterator
ports: Vec<Rc<Port<T>>>, // Pointers to remaining chained ports
}
// Note that the iterator is created from an immutable reference to Port<T>
impl<'a, T: 'a> IntoIterator for &'a Port<T> {
type Item = &'a T; // the iterator returns references to values
type IntoIter = PortIterator<'a, T>;
fn into_iter(self) -> Self::IntoIter {
// We clone all the reference-counting pointers so the iterator owns them
let mut ports = vec![];
for port in self.ports.iter() {
ports.push(port.clone())
}
PortIterator {values: self.values.iter(), port: None, ports}
}
}
Now, let's define the Iterator trait for PortIterator:
impl <'a, T: 'a> Iterator for PortIterator<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
// We first iterate over values of the original port
if let Some(v) = self.values.next() {
return Some(v)
}
// If the first iterable is done, we try to iterate over a chained port
if let Some(port) = &mut self.port {
if let Some(v) = port.next() {
return Some(v)
}
}
// if the chained port is over, we try to consume the next chained port
if let Some(port) = self.ports.get(self.next_port) {
self.next_port += 1;
self.port = Some(Box::new(port.as_ref().into_iter()));
return self.next()
}
None
}
}
Now, the program does not compile. The issue seems to be in the third if let block, and it has to do with lifetimes. This is what the compiler says:
error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
--> src/modeling/port.rs:69:40
|
69 | if let Some(port) = self.ports.get(self.next_port) {
| ^^^
|
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 57:5...
--> src/modeling/port.rs:57:5
|
57 | fn next(&mut self) -> Option<Self::Item> {
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...so that reference does not outlive borrowed content
--> src/modeling/port.rs:69:29
|
69 | if let Some(port) = self.ports.get(self.next_port) {
| ^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 54:7...
--> src/modeling/port.rs:54:7
|
54 | impl <'a, T: 'a> Iterator for PortIterator<'a, T> {
| ^^
note: ...so that the expression is assignable
--> src/modeling/port.rs:71:25
|
71 | self.port = Some(Box::new(port.as_ref().into_iter()));
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
= note: expected `Option<Box<PortIterator<'a, _>>>`
found `Option<Box<PortIterator<'_, _>>>`
I'm not sure how to deal with this. I've been trying other options and implementations, but I keep going in circles.
I think there are simpler ways of achieving what you want to achieve. Let's start small: your Port<T> need an iter(&self) method that returns an iterator that hands out &T items:
pub fn iter(&self) -> impl Iterator<Item = &T> {
// ...
}
This function needs to chain the iterator over self.values, i.e. self.values.iter() with an iterator over chained ports. What you'd want to write is something like:
pub fn iter(&self) -> impl Iterator<Item = &T> {
self.values
.iter()
.chain(self.ports.iter().flat_map(|p| p.iter()))
}
However, this doesn't compile because the compiler complains of a "recursive opaque type". That's because the type of p.iter() is our very same impl Iterator<...>, which would then have to contain itself. This is conceptually the same problem you encountered when building PortIterator, which you resolved by boxing the chained PortIterator. We can resolve it the same way, by boxing the inner iterator and dispatching it dynamically:
pub fn iter(&self) -> impl Iterator<Item = &T> {
self.values.iter().chain(
self.ports
.iter()
.flat_map(|p| Box::new(p.iter()) as Box<dyn Iterator<Item = &T>>),
)
}