RFC: Generalize Freeze, etc. into custom-defined does-not-contain traits

[glaebhoerl]

Rust currently has a few built-in traits which all basically mean "does not contain Foo". Freeze: no &mut, Cell, or RefCell. Send: no managed or borrowed pointers. 'static: no non-'static borrowed pointers. Combined with the proposal to use marker types in #10834, perhaps this could be generalized to user-defined does-not-contain traits, with compiler support.

This would be useful for, for example, preventing cycles in Rc, in the spirit of #10837 but at a semantic rather than syntactic level. You could write something like:

pub struct ReferenceCounted;

#[does_not_contain(ReferenceCounted)]
pub trait NoRc { }; // an imaginary syntax, others possible

pub struct Rc<T> {
    priv val: *mut RcBox<T>,
    priv marker: ReferenceCounted
}

impl<T: NoRc> Rc<T> {
    pub fn new(val: T) -> Rc<T> { ... }
}

This would solve the problem of existentially quantified types the same way as the built-in traits: any existentially quantified type could only be passed to this new() if it explicitly had a NoRc bound (e.g. ~ToStr:NoRc). This might still be too high a burden, so there would probably be other constructors as well, as now, including a Freeze-based and an unconstrained one, but this is still finer-grained, at least, than the current situation.

This might also help with #10869, and with another crazy idea I've been thinking about that I'm not ready to post yet.

[thestinger]

That ReferenceCounted marker is still too specific - it should at least to be ReferenceCounted<T>. Even then, it still forbids many correct non-cyclical data structures, and it's more strict than the current Freeze bound in many cases. There's no way to make an Rc cycle if the inner type respects the mutability rules.

[glaebhoerl]

That ReferenceCounted marker is still too specific - it should at least be ReferenceCounted<T>.

Hmm. Would that still be sufficient to rule out cycles? I think it might be, but I'm having a hard time thinking straight enough to convince myself.

In that case it might be better to just straight-up make this a trait itself, instead of relying on magic attributes:

trait NoRc<T>: DoesNotContain<ReferenceCounted<T>> { }
impl<X: DoesNotContain<ReferenceCounted<T>> NoRc<T> for X { }

I was shying away from this earlier because it seems potentially harder to implement, but I have no actual idea.

At this point the NoRc trait is only for brevity. Maybe if you do it this way, you don't need the separate marker type either, and could just write DoesNotContain<Rc<T>>... but maybe it would still be useful for preventing a mutual cycle between different reference counted types? (Is that possible?)

Even then, it still forbids many correct non-cyclical data structures, and it's more strict than the current Freeze bound in many cases.

True, which is why I said the Freeze and unconstrained constructors would presumably also remain. I don't believe it's possible for a static analysis to precisely rule out all cyclical structures and only cyclical structures, you can't avoid having either false positives or false negatives. This would still be a strict improvement on the current Send constructor (I think).

The current built-in traits could potentially be reimplemented on top of this as well, so they would no longer have to be baked-in to the compiler, only DoesNotContain itself:

struct Local;
struct Managed { marker: Local } // inheritance-ish!
struct Gc<T> { val: ..., marker: Managed }
trait NoManaged: DoesNotContain<Managed> { } // (+ impl)
trait Send: 'static + DoesNotContain<Local> { } // (+ impl)
struct ReferenceCounted<T> { marker: Local }

struct Mutable;
struct &mut 'a T { ..., marker: Mutable } // imaginary syntax, this would have to be wired-in (sadly)
struct Cell<T> { ..., marker: Mutable }
struct RefCell<T> { ..., marker: Mutable }
trait Freeze: DoesNotContain<Mutable> { } // (+ impl)

I don't know how feasible it would be to implement a general DoesNotContain of this form though.

[pnkfelix]

cc me

[nikomatsakis]

Until we have our story straight about trait matching (#5527), I'd be reluctant to add features, and this seems like it's ultimately really a feature request for "negative" traits. I think those are feasible to support at some point, though.

[glaebhoerl]

I was thinking of this as more of a refactor-and-generalize, with added power falling out as a side benefit. If it doesn't make things "nicer" then it's probably not a good idea.

I did think of negated traits as a potential alternative way to achieve similar functionality, but:

• I think that would be a replacement for the marker type way of doing things (e.g. trait Mutable { }; trait Freeze = !Mutable; impl<T> Mutable for Cell<T> { }), whereas this idea builds on top of it, and
• I think marker type + DoesNotContain just plain works better. With negated traits you would still need some kind of special magic for why, if something is Mutable/!Freeze, that would propagate to any other type which has it as a member, whereas with DoesNotContain this transitivity happens naturally and the rule is easy to express.

I also don't think the two ideas have much in common: DoesNotContain is a negated trait only insofar as it negates DoesContain, which doesn't exist either (and which seems like it would be implemented similarly, only less useful).

[glaebhoerl]

I no longer think this is relevant and a good idea.