unsound behavior with incorrect `Trace` impls, when `trace` is called on *too many* things

[steffahn]

First off, I’m not 100% sure I understand the docs correctly, i.e. whether Trace is even really “supposed” to be completely safe to implement. It only warns of “leaking cycles” as consequence for incorrect implementations – but also all the issues in this repo that I read seem to only consider examples where Trace implementations aren’t (deliberately) misbehaving in any way.

But I think it’s clear that incorrect Trace implementations can be quite problematic – i.e. they can simulate cycles that don’t actually exist, by calling trace on non-consituents. E.g. here’s an example where trace is simply called twice on a field:

use std::cell::RefCell;

use bacon_rajan_cc::{collect_cycles, Cc, Trace};

struct DoubleTrace<T: Trace + 'static>(T, RefCell<Option<Cc<DoubleTrace<T>>>>);

impl<T: Trace> Trace for DoubleTrace<T> {
    fn trace(&self, tracer: &mut bacon_rajan_cc::Tracer) {
        self.0.trace(tracer);
        self.0.trace(tracer); // incorrect second call
        self.1.trace(tracer);
    }
}

fn main() {
    let hello = Cc::new(String::from("Hello World"));
    let double = Cc::new(DoubleTrace(hello.clone(), RefCell::new(None)));

    *double.1.borrow_mut() = Some(double.clone());

    let hello_str: &str = &hello;
    println!("hello_str exists: {}", hello_str);

    drop(double);

    collect_cycles();
    println!("hello_str gone: {}", hello_str);
}

hello_str exists: Hello World
hello_str gone: ��vګcb��

There seems to be some partial defense against such accesses of a Cc after being freed, e.g. if the after-collect_cycles-access were to go through the Cc again like

// let hello_str: &str = &hello; // commented out
println!("hello_str exists: {}", &hello[..]);

drop(double);

collect_cycles();
println!("hello_str gone: {}", &hello[..]);

that produces Invalid access during cycle collection panic. But it doesn’t help for live references created before the collecting.

Another example of a simulated cycle would be

use bacon_rajan_cc::{collect_cycles, Cc, Trace};

struct GlobalFakeCycle(String);

thread_local! {
    static GLOBAL_FAKE_CYCLE: Cc<GlobalFakeCycle> = Cc::new(GlobalFakeCycle(String::from("Hello World")));
}

impl Trace for GlobalFakeCycle {
    fn trace(&self, tracer: &mut bacon_rajan_cc::Tracer) {
        GLOBAL_FAKE_CYCLE.with(|c| c.trace(tracer));
    }
}

fn main() {
    GLOBAL_FAKE_CYCLE.with(|gfc| {

        let hello_str: &str = &gfc.0;
        println!("hello_str exists: {}", &hello_str);

        drop(gfc.clone());
        collect_cycles();
        println!("hello_str gone: {}", &hello_str);
    });
}

hello_str exists: Hello World
hello_str gone: �QtT[J

I believe these example above do constitute a perfect simulation of an actual cycle,¹ so I simply don’t believe that a sound Trace is completely possible when it isn’t unsafe trait Trace.

Footnotes

1. The latter - global_fake_cycle - is clearly simulating an ordinary cycle. The former case with double trace calls, too, though – it simulates the scenario where double would simply have gained ownership of both clones of the hello reference; the difference could only be detected if multiple clones of a Cc has some differentiating properties / object identity. ↩