please add a weak ref type

[dagit]

I started using this crate for my prolog interpreter (it's great, thank you for making it!).

I'd to make my interpreter do hash consing of the terms. Actually, I already made this change, but since there is no weak version of the Gc type, my interpreter now never collects anything. The reason is because the HashSet I use to store terms has a strong reference so once a term is inserted into my heap, it lives forever. Normally, when implementing hash-consing you store weak references in the hashset.

Basically, I want to write code like this:

type TermSet   = HashSet<WeakGc<Term>>;
pub struct Heap {
    terms:   TermSet,
}
// Check if `t` is already in the HashSet. If it is, then return
// a strong reference to it.
// if `t` is not in the HashSet, add it and return a strong reference to it.
fn insert_thing<A>(heap: &mut HashSet<Gc<A>>, t: A) -> Gc<A>
    where A: Trace,
          Gc<A>: Eq,
          Gc<A>: Hash
{
        let gc_thing = Gc::new(t);
        match heap.get(&gc_thing.downgrade()) {
            Some(gc) => return gc.upgrade().unwrap_or(gc_thing.clone()),
            None     => ()
        }
        heap.insert(gc_thing.downgrade());
        gc_thing
}
impl Heap {
    pub fn new() -> Self {
        Heap {
            terms:   HashSet::new(),
        }
    }

    pub fn insert_term(&mut self, t: Term) -> Gc<Term>
    {
        insert_thing(&mut self.terms, t)
    }
}

I tried something similar using Rc and Weak from std (even though cycles would cause issues), but I noticed Weak doesn't implement Hash and Eq so they can't be used as keys in a HashMap (and by extension, a HashSet). I don't know if that is due to the way dereferening Weak works or what. Perhaps I'll also need a custom collection type. Anyway, do you think that would be an issue here as well?

Would a weak version of Gc be hard to add? I haven't looked at the code yet, but if it's not too hard I might try adding one.

[Manishearth]

Ideally there would be a WeakSet type that automatically removes the thing from the set (this is a common pattern in GCd languages). Weak<T> itself would also probably be useful.

Don't have the time to work on this, but would accept a PR adding it.

[Manishearth]

Weak should be able to implement Hash and Eq

[dagit]

I was finally playing with this again today. I exposed a function that lets me check how many roots a Gc has. Then I can use retain on my HashSet to only keep references that have > 1 roots.

I doubt you want to expose this as part of the public API and I'm not even sure it's a good way to implement the feature I wanted.

Instead, I could add it as an internal part of the API and then make a wrapper around the std HashSet to behave like the one in my program. If I did that, one question that comes up is how often to look for values to remove from the HashSet? In my interpreter it's fairly easy to just hack something in, but I think the right time to do it is after a collection. So that might imply that collecting knows about values of the custom HashSet type and can tell them to compact. A simpler solution might be to provide a function compact that checks for collected elements and let the user call it when it makes sense to do so?

Perhaps some of these issues would be conceptually easier if there was a dedicated Weak type, but I'm less certain how to implement that so I went with the above hack.

Thoughts?