Iterator over RefCell<HashSet>

alexchamberlain · January 19, 2021, 8:36am

I have a Rc<RefCell<HashSet>> that is stored in exactly 2 HashMap indices, and I'm struggling to write an Iterator over one of those indices; this is my current attempt:

use std::cell::Ref;
use std::cell::RefCell;
use std::collections::hash_map;
use std::collections::hash_set;
use std::collections::HashMap;
use std::collections::HashSet;
use std::rc::Rc;


struct Store
{
    index1: HashMap<u32, Rc<RefCell<HashSet<u32>>>>,
    index2: HashMap<u32, Rc<RefCell<HashSet<u32>>>>,
}

struct StoreIter<'a>
{
    index_iterator: hash_map::Iter<'a, u32, Rc<RefCell<HashSet<u32>>>>,
    objects: Ref<'a, HashSet<u32>>,
    object_iterator: Ref<'a,hash_set::Iter<'a, u32>>,
    next: Option<(u32, u32)>
}

impl Store {
    fn new() -> Store {
        let twos: Rc<RefCell<HashSet<u32>>> =
            Rc::new(RefCell::new([ 2, 4, 6, 8, 10 ].iter().cloned().collect()));
        let threes: Rc<RefCell<HashSet<u32>>> =
            Rc::new(RefCell::new([ 3, 6, 9, 12, 15 ].iter().cloned().collect()));

        let mut index1 = HashMap::new();
        index1.insert(2, twos.clone());
        index1.insert(3, threes.clone());
        let mut index2 = HashMap::new();
        index2.insert(3, twos);
        index2.insert(2, threes);

        Store {
            index1,
            index2
        }
    }

    fn iter<'a>(&'a self) -> StoreIter<'a>
    {
        let mut i1it = self.index1.iter();
        let i1n = i1it.next().unwrap();
        let objects: Ref<'a, HashSet<u32>> = i1n.1.borrow();
        let mut oit: Ref<'a, hash_set::Iter<'a, u32>> = Ref::map(Ref::clone(&objects), |o| o.iter());
        let oin: u32 = *oit.next().unwrap();
        StoreIter {
            index_iterator: i1it,
            objects: objects,
            object_iterator: oit,
            next: Some((*i1n.0, oin))
        }
    }
}

impl<'a> Iterator for StoreIter<'a>
{
    type Item = (u32, u32);

    fn next(&mut self) -> Option<Self::Item>
    {
        None
    }
}

fn main() {
    let store = Store::new();
    for item in store.iter() {
        println!("{:?}", item);
    }
}

The current error is that the function in Ref::map should return a reference. I think I need some container that I can store in StoreIter alongside the objects Ref, which guarantees the lifetime of 'a, but I can't quite square that circle. Any ideas?

Thanks,

Alex

kornel · January 19, 2021, 9:58am

Unfortunately Ref::map is defined as mapping between &T -> &U, so it will prevent you from making any new objects, such as an iterator.

I don't think this is necessary for safety, but rather only a limitation on how this function is defined.

I suggest forcing it through with unsafe.

Get the hashset iter() outside Ref::map.
Store Ref and the hashset iterator both in StoreIter.
- Make sure the struct defines iter field before the ref field (they're destructed in declaration order).
- Carefully unsafely transmute hashset iterator's lifetime to 'a to make Rust allow you to keep it the struct.

Yandros · January 19, 2021, 11:39am

I'd strongly advise against using unsafe, especially when RefCell and lock guards are involved, since it gets pretty hard to correctly mix runtime lifetimes with compile-time lifetimes, and one can easily cause aliasing.

In instances such as the one in this thread, I suggest to, instead:

either use a bit of a different syntax, whose semantics change so that lifetimes are no longer a problem:

or to refactor a bit the code to chain multiple borrows and thus avoid the problem of "self-referentiality" that Rust struggles with:

use ::std::{
    cell::{Ref, RefCell},
    collections::{HashMap, HashSet},
    rc::Rc,
};

struct Store {
    index1: HashMap<u32, Rc<RefCell<HashSet<u32>>>>,
    index2: HashMap<u32, Rc<RefCell<HashSet<u32>>>>,
}

impl Store {
    fn new ()
      -> Store
    {
        let twos = Rc::new(RefCell::new(
            [2, 4, 6, 8, 10]
                .iter()
                .copied()
                .collect::<HashSet<u32>>()
        ));
        let threes = Rc::new(RefCell::new(
            [3, 6, 9, 12, 15]
                .iter()
                .copied()
                .collect::<HashSet<u32>>()
        ));

        let mut index1 = HashMap::new();
        index1.insert(2, twos.clone());
        index1.insert(3, threes.clone());
        let mut index2 = HashMap::new();
        index2.insert(3, twos);
        index2.insert(2, threes);

        Store { index1, index2 }
    }
}
   
impl Store {
    fn borrow<'borrow> (self: &'borrow Self)
      -> BorrowedStore<'borrow>
    {
        self.index1
            .iter()
            .next()
            .map(|(&elem_idx, i1n)| BorrowedStore {
                elem_idx,
                borrowed_set: i1n.borrow(),
            })
            .unwrap()
    }
}
// where
struct BorrowedStore<'store> {
    elem_idx: u32,
    borrowed_set: Ref<'store, HashSet<u32>>,
}
impl<'store> BorrowedStore<'store> {
    fn iter<'iter> (self: &'iter BorrowedStore<'store>)
      -> impl 'iter + Iterator<Item = (u32, u32)>
    {
        self.borrowed_set
            .iter()
            .map(move |&elem| (self.elem_idx, elem))
    }
}

fn main ()
{
    let store = Store::new();
    for item in store.borrow().iter() {
        println!("{:?}", item);
    }
}

Playground

If you really want to try some unsafe self-referential pattern, then I suggest you try to use only helper crates that showcase non-unsafe APIs, such as:

(See OwningHandle in your case)

alexchamberlain · January 20, 2021, 7:21am

Thank You both for your input - I really appreciate it. I ended up with a minimal amount of unsafe code. This code isn't perfect, but demonstrates the concept:

use std::cell::Ref;
use std::cell::RefCell;
use std::collections::hash_map;
use std::collections::hash_set;
use std::collections::HashMap;
use std::collections::HashSet;
use std::rc::Rc;

use owning_ref::OwningHandle;

#[allow(dead_code)]
struct Store {
    index1: HashMap<u32, Rc<RefCell<HashSet<u32>>>>,
    index2: HashMap<u32, Rc<RefCell<HashSet<u32>>>>,
}

type RefHandle<'a, T, U = T> = OwningHandle<Ref<'a, T>, U>;

struct StoreIter<'a> {
    object_iterator: RefHandle<'a, HashSet<u32>, Box<hash_set::Iter<'a, u32>>>,
    index_iterator: hash_map::Iter<'a, u32, Rc<RefCell<HashSet<u32>>>>,
    next: Option<(u32, u32)>,
}

impl Store {
    fn new() -> Store {
        let twos: Rc<RefCell<HashSet<u32>>> =
            Rc::new(RefCell::new([2, 4, 6, 8, 10].iter().cloned().collect()));
        let threes: Rc<RefCell<HashSet<u32>>> =
            Rc::new(RefCell::new([3, 6, 9, 12, 15].iter().cloned().collect()));

        let mut index1 = HashMap::new();
        index1.insert(2, twos.clone());
        index1.insert(3, threes.clone());
        let mut index2 = HashMap::new();
        index2.insert(3, twos);
        index2.insert(2, threes);

        Store { index1, index2 }
    }

    fn iter<'a>(&'a self) -> StoreIter<'a> {
        let mut i1it = self.index1.iter();
        let i1n = i1it.next().unwrap();
        // let objects: Ref<'a, HashSet<u32>> = i1n.1.borrow();
        let mut oit: RefHandle<'a, HashSet<u32>, Box<hash_set::Iter<'a, u32>>> =
            RefHandle::new_with_fn(i1n.1.borrow(), unsafe {
                |o: *const HashSet<u32>| Box::new((*o).iter())
            });
        let oin: u32 = *oit.next().unwrap();
        StoreIter {
            index_iterator: i1it,
            object_iterator: oit,
            next: Some((*i1n.0, oin)),
        }
    }
}

impl<'a> Iterator for StoreIter<'a> {
    type Item = (u32, u32);

    fn next(&mut self) -> Option<Self::Item> {
        let next = self.next;

        if next.is_none() {
            return None;
        }

        let oin = self.object_iterator.next();
        match oin {
            Some(nnext) => {
                self.next = Some((self.next.unwrap().0, *nnext));
            }
            None => {
                let i1n = self.index_iterator.next();
                match i1n {
                    Some((nnext_i1, oit)) => {
                        let mut oit: RefHandle<'a, HashSet<u32>, Box<hash_set::Iter<'a, u32>>> =
                            RefHandle::new_with_fn(oit.borrow(), unsafe {
                                |o: *const HashSet<u32>| Box::new((*o).iter())
                            });
                        let oin: u32 = *oit.next().unwrap();

                        self.object_iterator = oit;
                        self.next = Some((*nnext_i1, oin));
                    }
                    None => {
                        self.next = None;
                    }
                }
            }
        }

        next
    }
}

fn main() {
    let store = Store::new();
    for item in store.iter() {
        println!("{:?}", item);
    }
}

alexchamberlain · January 20, 2021, 7:36am

By adapting OwningHandle for my own use case, I've been able to remove the Box too.

alexchamberlain · January 20, 2021, 8:41pm

Ok, I'm pretty happy with this now; thanks again for your input and help.

use std::cell::Ref;
use std::cell::RefCell;
use std::collections::hash_map;
use std::collections::hash_set;
use std::collections::HashMap;
use std::collections::HashSet;
use std::rc::Rc;

pub struct RefIter<'a, O, H>
where
    H: Iterator,
{
    iter: H,
    _owner: Ref<'a, O>,
}

impl<O, H: Iterator> Iterator for RefIter<'_, O, H> {
    type Item = H::Item;

    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next()
    }
}

impl<'a, O, H> RefIter<'a, O, H>
where
    H: Iterator,
{
    pub fn new_with_fn<F>(o: Ref<'a, O>, f: F) -> Self
    where
        F: FnOnce(*const O) -> H,
    {
        RefIter {
            iter: f(&*o),
            _owner: o,
        }
    }
}

impl<'a, O> RefIter<'a, O, O::Iter>
where
    O: ToIterator,
{
    pub fn new(o: Ref<'a, O>) -> Self {
        RefIter::new_with_fn(o, |x| unsafe { O::to_iterator(x) })
    }
}

pub trait ToIterator {
    /// The type of iter to be encapsulated by the RefIter.
    type Iter: Iterator;

    /// Given an appropriately-long-lived pointer to ourselves, create a
    /// iter to be encapsulated by the `RefIter`.
    unsafe fn to_iterator(x: *const Self) -> Self::Iter;
}

impl<T: 'static> ToIterator for HashSet<T> {
    type Iter = hash_set::Iter<'static, T>;
    unsafe fn to_iterator(x: *const Self) -> Self::Iter {
        (*x).iter()
    }
}

#[allow(dead_code)]
struct Store {
    index1: HashMap<u32, Rc<RefCell<HashSet<u32>>>>,
    index2: HashMap<u32, Rc<RefCell<HashSet<u32>>>>,
}

struct StoreIter<'a> {
    object_iterator: RefIter<'a, HashSet<u32>, hash_set::Iter<'a, u32>>,
    index_iterator: hash_map::Iter<'a, u32, Rc<RefCell<HashSet<u32>>>>,
    next: Option<(u32, u32)>,
}

impl Store {
    fn new() -> Store {
        let twos: Rc<RefCell<HashSet<u32>>> =
            Rc::new(RefCell::new([2, 4, 6, 8, 10].iter().cloned().collect()));
        let threes: Rc<RefCell<HashSet<u32>>> =
            Rc::new(RefCell::new([3, 6, 9, 12, 15].iter().cloned().collect()));

        let mut index1 = HashMap::new();
        index1.insert(2, twos.clone());
        index1.insert(3, threes.clone());
        let mut index2 = HashMap::new();
        index2.insert(3, twos);
        index2.insert(2, threes);

        Store { index1, index2 }
    }

    fn iter<'a>(&'a self) -> StoreIter<'a> {
        let mut i1it = self.index1.iter();
        let i1n = i1it.next().unwrap();
        let mut oit: RefIter<'a, HashSet<u32>, hash_set::Iter<'a, u32>> =
            RefIter::new(i1n.1.borrow());
        let oin: u32 = *oit.next().unwrap();
        StoreIter {
            index_iterator: i1it,
            object_iterator: oit,
            next: Some((*i1n.0, oin)),
        }
    }
}

impl<'a> Iterator for StoreIter<'a> {
    type Item = (u32, u32);

    fn next(&mut self) -> Option<Self::Item> {
        let next = self.next;

        if next.is_none() {
            return None;
        }

        let oin = self.object_iterator.next();
        match oin {
            Some(nnext) => {
                self.next = Some((self.next.unwrap().0, *nnext));
            }
            None => {
                let i1n = self.index_iterator.next();
                match i1n {
                    Some((nnext_i1, oit)) => {
                        let mut oit: RefIter<'a, HashSet<u32>, hash_set::Iter<'a, u32>> =
                            RefIter::new(oit.borrow());
                        let oin: u32 = *oit.next().unwrap();

                        self.object_iterator = oit;
                        self.next = Some((*nnext_i1, oin));
                    }
                    None => {
                        self.next = None;
                    }
                }
            }
        }

        next
    }
}

fn main() {
    let store = Store::new();
    for item in store.iter() {
        println!("{:?}", item);
    }
}

system · April 20, 2021, 8:42pm

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.

Topic		Replies	Views
HashMap keyed by Rc<RefCell<..>> help	16	5793	January 3, 2020
How to return an impl Iterator from inside a RefCell? help	17	2151	January 12, 2023
Implementing iterator on a nested RefCell, is it possible? help	6	474	August 30, 2023
RefCell2, a totally broken RefCell announcements	9	1478	January 12, 2023
Uniqueness of array of references help	4	469	January 27, 2022

Iterator over RefCell<HashSet>

Related topics