Arc to owning iterator

help
1 
fn foo(bar: Arc<[Arc<TreeNode>]>) -> impl Iterator<Item = Arc<TreeNode>> {
    bar.into_iter().cloned()
}

fn foo_ref(bar: &Arc<[Arc<TreeNode>]>) -> impl Iterator<Item = Arc<TreeNode>> + '_ {
    bar.into_iter().cloned()
}

Why does foo return an error "bar is dropped while still borrowed"? Is there a way to do that? Is this something missing from the compiler?

I'm trying to get rid of the first Arc::clone here but can't succeed. It won't let me reference self twice for the self.green.children and parent parts.

2

edit: sorry, I misjudged the situation.

You can't take ownership of Arc's contents, because it's a shared type and others can be still using it.

So Arc doesn't have its own into_iter(). You get a fallback to slice's iterator, which borrows from the slice.

When you loan Arc to a function, it guarantees that the Arc lives longer and so does its content.

If you move Arc into a function, and don't keep it anywhere, it will be destroyed at the end of its scope. If that was the last Arc, the content will be destroyed too.

3

Using .iter() doesn't fix it. Do you have any ideas for the code on GitHub?

4

You can't use a slice iterator because that wants a borrowed lifetime, but you can do it with indexing:

fn foo(bar: Arc<[Arc<TreeNode>]>) -> impl Iterator<Item = Arc<TreeNode>> {
    (0..bar.len()).map(move |i| Arc::clone(&bar[i]))
}
5

The problem is that the standard library doesn’t have an IntoIterator impl for Arc<[T]>, though it could provide one using indexing (like @cuviper's solution). You could write your own iterator type, though this is quite a bit more code:

pub fn foo<T>(bar: Arc<[Arc<T>]>) -> impl Iterator<Item = Arc<T>> {
    MyIter::new(bar)
}

struct MyIter<T> { items: Arc<[Arc<T>]>, pos: usize }

impl<T> MyIter<T> {
    pub fn new(items: Arc<[Arc<T>]>) -> Self {
        Self { items, pos: 0 }
    }
}

impl<T> Iterator for MyIter<T> {
    type Item = Arc<T>;
    fn next(&mut self) -> Option<Arc<T>> {
        let result = self.items.get(self.pos).cloned();
        self.pos += 1;
        result
    }
}
6

Thanks! Is there a proposal to add that to the standard library? Isn't the issue with my children function that I'm doing self.green.children.iter(), where the compiler fails to move self to the iterator?

Edit: Here's the types:

7

Note that indexing works only because the value is immediately cloned. It would not work for returning references.

1 Like
8

Oh right, I forgot as I was writing that the examples here were all specific to Arc<[Arc<T>]> rather than the more general Arc<[T]>.

9

It probably doesn't exist in std as it requires cloning each slice member. I could see an iter_cloned on Arc<[T]> where T: Clone method or such though.

The issue with getting rid of the lifetime (going from self: &Arc<_> to self: Arc<_>) is that you would be trying to return an iterator that borrows from a local variable. The compiler can't spontaneously decide to move things into the borrowing iterator (slice::Iter<'_, GreenItem>), any more that it can decide to spontaneously add new fields to your own structs due to far away code.[1]

On top of that, even it was possible, it would be self-referencial and unsound.

Consider a borrowing iterator that looked like

struct MagicIter<'a, T> {
    data: [T; 10],
    iter: slice::Iter<'a, T>,
}

where iter is borrowing data -- it holds pointers or references to data. When you move the MagicIter struct, the location of the [T; 10] and all the contained Ts move, and the pointers in data are now dangling.

Things don't always dangle when indirection (e.g. storing on the heap) is involved, but that's not part of the type system so it's nothing the compiler can solve on its own. The language would have to evolve significantly in order for such a self-referencial iterator to be possible without unsafe.

So you can't use .iter(), you need some non-borrowing iterator if you want to change the signature.

If you're okay with the borrowing signature, you can just replace

-                        parent: Some(Arc::clone(&arc)),
+                        parent: Some(Arc::clone(self)),

  1. More generally, borrow checker errors can't change the semantics of your code, such as when values are moved or dropped. ↩︎

10

If you're okay with the borrowing signature, you can just replace

Thank you for your comprehensive reply and solution! I didn't realize the fix was so easy or I just messed something else up previously.

On top of that, even it was possible, it would be self-referencial and unsound.

Could I make a custom iterator? Arc would make sure that it's immutable and doesn't move so I don't think there is any unsoundness going on.

Do you think this is sound?

struct OwnedGreenChildren {
    /// Even if this is never read, this keeps `iter` safe
    #[allow(dead_code)]
    green_node: Arc<GreenNode>,
    iter: std::slice::Iter<'static, GreenItem>
}
impl OwnedGreenChildren {
    fn new(green_node: Arc<GreenNode>) -> Self {
        Self {
            iter: unsafe { core::mem::transmute::<&[GreenItem], &'static [GreenItem]>(&green_node.children) }.iter(),
            green_node
        }
    }
}
impl Iterator for OwnedGreenChildren {
    type Item = GreenItem;
    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next().cloned()
    }
}

    pub fn owned_children(self: Arc<RedNode>) -> impl Iterator<Item = RedItem> {
        let mut current_text_offset = self.text_offset;

        OwnedGreenChildren::new(self.green.clone())
            .map(move |green_child| match green_child {
                GreenItem::Node(node) => {
                    let text_offset = current_text_offset;
                    current_text_offset += node.width;

                    RedItem::Node(Arc::new(RedNode {
                        parent: Some(Arc::clone(&self)),
                        green: node,
                        text_offset,
                    }))
                }
                GreenItem::Token(token) => {
                    let text_offset = current_text_offset;
                    current_text_offset += token.text.len();

                    RedItem::Token(Arc::new(RedToken {
                        parent: Arc::clone(&self),
                        green: token,
                        text_offset,
                    }))
                }
            })
    }
11

Just do the index based ones that have been proposed, if you need it.

Maybe, maybe not. Nothing jumps out at me,[1] but there's more to borrow checking than dangling pointers -- and honestly I didn't spend much time thinking about it.

I didn't spend much time because: It's not worth it. Just go with the non-unsafe version that's available to you.

  1. well, that transmute is unnecessary if you convert references/pointers instead ↩︎

2 Likes
12

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.