impl Trace for Rc<T> is not correct

[lalaithion]

The only unsafe code in my application is

use rpds::HashTrieMap;

pub struct Scope<V: Trace + 'static> {
    inner: HashTrieMap<String, Gc<V>>,
}

unsafe impl<V: Trace> Trace for Scope<V> {
    custom_trace!(this, {
        for (_, v) in this.inner.iter() {
            mark(v);
        }
    });
}

(This is essentially a workaround for rpds not implementing Trace).

I've checked, and nothing in the rpds library implements Drop, so I don't see how I'm violating the Trace contract. Is this a bug, or am I missing some invariant I need to maintain?

[andersk]

What version are you using? lib.rs line 126 is only a panic in v0.3.x, and your issue sounds like it could be the same as #117 which was fixed in v0.4.0.

[lalaithion]

#136

[lalaithion]

Hmm, sorry for the preemptive closure. I still get the error when updated to 0.4

[lalaithion]

Now it's failing on lib.rs:125:9

Trying to run the same code paths via manually calling my binary (vs. in a test) causes "Can't double-unroot a Gc" in lib.rs:226.

[andersk]

Are you using #[unsafe_ignore_trace] on a field that contains a Gc? That’s known to be a possible cause of that panic. (Well, known to me as of 15 minutes ago, at least. I assume it’s been known to the original authors for longer. 🙂 The README does warn “Incorrect usage of unsafe_empty_trace and unsafe_ignore_trace may lead to unsafety.”)

If not, you’ve probably found a new bug, and we’ll need to see some code that reproduces it to investigate further.

[lalaithion]

Took me a couple tries to figure out exactly where the issue was coming from, but here's my reproduction:

https://gist.github.com/lalaithion/125704f8f69408ec6d825b9075804787

[andersk]

Hmm. I was going to suggest that your Trace implementation might be wrong because rpds::HashTrieMap uses structural sharing of trie branches between instances. However, if that’s a bug, then our Trace implementation for Rc is wrong too, and, well…

use gc::Gc;
use std::rc::Rc;

fn main() {
    let r = Rc::new(Gc::new(()));
    Gc::new((Rc::clone(&r), r));
}

thread 'main' panicked at 'Can't double-unroot a Gc<T>', /home/anders/.cargo/registry/src/github.com-1ecc6299db9ec823/gc-0.4.1/src/lib.rs:226:9
stack backtrace:
   0: std::panicking::begin_panic
             at /rustc/5dc8789e300930751a78996da0fa906be5a344a2/library/std/src/panicking.rs:541:12
   1: <gc::Gc<T> as gc::trace::Trace>::unroot
             at /home/anders/.cargo/registry/src/github.com-1ecc6299db9ec823/gc-0.4.1/src/lib.rs:226:9
   2: <alloc::rc::Rc<T> as gc::trace::Trace>::unroot::mark
             at /home/anders/.cargo/registry/src/github.com-1ecc6299db9ec823/gc-0.4.1/src/trace.rs:85:17
   3: <alloc::rc::Rc<T> as gc::trace::Trace>::unroot
             at /home/anders/.cargo/registry/src/github.com-1ecc6299db9ec823/gc-0.4.1/src/trace.rs:241:9
   4: <(A,B) as gc::trace::Trace>::unroot::mark
             at /home/anders/.cargo/registry/src/github.com-1ecc6299db9ec823/gc-0.4.1/src/trace.rs:85:17
   5: <(A,B) as gc::trace::Trace>::unroot::avoid_lints
             at /home/anders/.cargo/registry/src/github.com-1ecc6299db9ec823/gc-0.4.1/src/trace.rs:205:32
   6: <(A,B) as gc::trace::Trace>::unroot
             at /home/anders/.cargo/registry/src/github.com-1ecc6299db9ec823/gc-0.4.1/src/trace.rs:222:1
   7: gc::Gc<T>::new
             at /home/anders/.cargo/registry/src/github.com-1ecc6299db9ec823/gc-0.4.1/src/lib.rs:76:13
   8: test::main
             at ./test.rs:6:5
   9: core::ops::function::FnOnce::call_once
             at /rustc/5dc8789e300930751a78996da0fa906be5a344a2/library/core/src/ops/function.rs:227:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

😕