Enabling Rc<Trait>

[mahkoh]

Given some additional intrinsics and extended subtyping support in function signatures, it's possible to write Rc<Trait>:

Extended subtyping support means that we can always write <X, Y: X> which means that Y is a subtype of X. Right now this syntax only works if X is a trait, but it should also work if X == Y. See the implementation below.

/// `Rc<T>` for sized and unsized `T`
///
/// How to use it:
///
/// Given two types `T`, `U` such that `T` is a subtype of `U`, and `x: T`, the following
/// just works:
///
/// ```
/// let u: Rc<U> = Rc::new(x);
/// let u_ref: &U = &*u;
/// ```
///
/// Implementation:
///
/// We use the following new intrinsics in the implementation:
///
/// ```
/// fn deref_drop<T>(ptr: *const T);
/// fn deref_size<T>(ptr: *const T) -> usize;
/// fn deref_align<T>(ptr: *const T) -> usize;
/// fn deref_addr<T>(ptr: *const T) -> *const ();
/// ```
///
/// For `T` sized this is merely what already exists in `std::intrinsics`. For `T` a
/// trait:
///
/// - `deref_drop` - Deref drop drops the object contained in the trait object, e.g.,
///   `deref_drop(&String::new() as &Any)` drops the string.
/// - `deref_size` - Returns the size of the object contained in the trait object, e.g.,
///   `deref_drop(&String::new() as &Any) == size_of::<String>`.
/// - `deref_size` - Returns the alignment of the object contained in the trait object.
/// - `deref_addr` - Returns the address of the object contained in the trait object.
///
/// Similar for `T` a slice.

use intrinsics::{deref_drop, deref_size, deref_align, deref_addr};

/// Data shared between all `Rc` and `Weak`.
#[repr(C)]
struct Shared<T> {
    strong: Cell<usize>,
    weak:   Cell<usize>
    value:  T,
}

impl<T> Shared<T> {
    fn bump_weak(&self) -> usize {
        let weak = self.weak.get() + 1;
        self.weak.set(weak);
        weak
    }

    fn dec_weak(&self) -> usize {
        let weak = self.weak.get() - 1;
        self.weak.set(weak);
        weak
    }

    fn bump_strong(&self) -> usize {
        let strong = self.strong.get() + 1;
        self.strong.set(strong);
        strong
    }

    fn dec_strong(&self) -> usize {
        let strong = self.strong.get() - 1;
        self.strong.set(strong);
        strong
    }
}

pub struct Rc<T: ?Sized> {
    _ref: *const T,
}

impl<T: ?Sized> !marker::Send for Rc<T> {}
impl<T: ?Sized> !marker::Sync for Rc<T> {}

impl<T: ?Sized> Rc<T> {
    pub fn new<X: T>(value: X) -> Rc<T> {
        unsafe {
            let shared = box Shared {
                strong: Cell::new(1),
                weak:   Cell::new(1)
                value:  value,
            };
            let _ref = mem::transmute::<&T, *const T>(&shared.value as &T);
            mem::forget(shared);
            Rc { _ref = _ref }
        }
    }

    pub fn downgrade(&self) -> Weak<T> {
        let shared = self.shared();
        shared.bump_weak();
        Weak { _ref = self._ref }
    }

    fn shared(&self) -> &Shared<()> {
        unsafe {
            let addr = (deref_addr(self._ref) as *const usize).offset(-2);
            mem::transmute(addr)
        }
    }
}

impl<T: ?Sized> Deref for Rc<T> {
    type Target = T;

    fn deref(&self) -> &T {
        unsafe { mem::transmute(self._ref) }
    }
}

impl<T: ?Sized> Drop for Rc<T> {
    fn drop(&mut self) {
        unsafe {
            let shared = self.shared();
            if shared.dec_strong() > 0 {
                return;
            }
            // This was the last strong reference
            deref_drop(self._ref);
            if shared.dec_weak() > 0 {
                return;
            }
            // There are no more strong or weak references
            let size = 2*size_of::<Cell<usize>> + deref_size(self._ref);
            let align = cmp::max(deref_align(self._ref), min_align_of(Cell<usize>>));
            deallocate(shared as *const _ as *mut u8, size, align);
        }
    }
}

impl<T: ?Sized> Clone for Rc<T> {
    fn clone(&self) -> Rc<T> {
        let shared = self.shared();
        shared.inc_strong();
        Rc { _ref: self._ref }
    }
}

pub struct Weak<T: ?Sized> {
    _ref: *const T,
}

impl<T: ?Sized> !marker::Send for Weak<T> {}
impl<T: ?Sized> !marker::Sync for Weak<T> {}

impl<T: ?Sized> Weak<T> {
    pub fn upgrade(&self) -> Option<Rc<T>> {
        let shared = self.shared();
        if shared.inc_strong() > 1 {
            Some(Rc { _ref: self._ref })
        } else {
            shared.dec_strong();
            None
        }
    }

    fn shared(&self) -> &Shared<()> {
        unsafe {
            let addr = (deref_addr(self._ref) as *const usize).offset(-2);
            mem::transmute(addr)
        }
    }
}

impl<T: ?Sized> Drop for Weak<T> {
    fn drop(&mut self) {
        unsafe {
            let shared = self.shared();
            if shared.dec_weak() == 0 {
                let size = 2*size_of::<Cell<usize>> + deref_size(self._ref);
                let align = cmp::max(deref_align(self._ref), min_align_of(Cell<usize>>));
                deallocate(shared as *const _ as *mut u8, size, align);
            }
        }
    }
}

impl<T> Clone for Weak<T> {
    fn clone(&self) -> Weak<T> {
        let shared = self.shared();
        shared.inc_weak();
        Weak { _ref: self._ref }
    }
}

cc @nikomatsakis

[eddyb]

• you can't assume a maximum alignment - @nikomatsakis made this mistake in DST5
• we have names for most of those: deref_size -> size_of_val, deref_align -> align_of_val, deref_drop -> drop_in_place (the last one doesn't show up anywhere yet, but has been mentioned before).
• that kind of subtyping is not a thing in Rust, maybe you want a trait expressing the built-in *T -> *U unsizing coercion - though the plan is to have it automatic (@nrc and @nikomatsakis have been discussing that lately, since Type conversions #401 is not realistically actionable)

[eddyb]

While the example implementation feels alien, it made me realize that the language-level pivot pointers (*T points to a field of T that is not the first one) I tried to spec a while back are not necessary.

Actually, just remembered my reasoning: one of the concerns was Rc<RefCell<Trait>>, which would still have alignment issues (or dynamic vtable-base pointer adjustments) even if Rc<T> was pointing directly to T.

Still, it's a start and should be backwards-compatible to switch some structures in std to pivot pointers - modulo unsafe code (but we don't specify struct layout, so it should be fine).

[mahkoh]

Summarizing some discussion from IRC:

you can't assume a maximum alignment - @nikomatsakis made this mistake in DST5

I believe that right now there is no way to have a type whose alignment is larger than 2*sizeof(usize) (at least on 64 bit). In the future we'll hopefully be able to specify larger alignment. Then the Shared type could be written like this:

#[repr(C)]
struct Shared<T> {
    _padding: [u8; align_of::<T>().saturating_sub(2 * size_of::<usize>())],
    strong: Cell<usize>,
    weak:   Cell<usize>
    value:  T,
}

that kind of subtyping is not a thing in Rust

What I want is to express that there is a function that maps &Y to &X. So

trait As<X: ?Sized> {
    fn as(&self) -> &X;
}

impl<T: ?Sized> Rc<T> {
    pub fn new<X: As<T>>(value: X) -> Rc<T> {
// ...
            let _ref = mem::transmute::<&T, *const T>((&shared.value).as());

Still probably has to be built-in as long as one cannot automatically implement As<Trait> for all T such that T: Trait.

[bluss]

Rc<Trait> is now done.

[eddyb]

@bluss it doesn't use the efficient "pivot pointer" scheme, though.
Maybe a sepparate issue should be opened for that.

[Centril]

closing in favor of rust-lang/rust#54898.