Iterator over RefCell<HashSet>

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

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.

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);
        }
    }
    
  • 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)
4 Likes

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);
    }
}

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

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);
    }
}