4 ms·

There isn't an acceptable way to fix Rc. It wouldn't be hard to require it not to have cycles, but cyclic data is actually a major usecase for Rc. A cycle col

There isn't an acceptable way to fix Rc. It wouldn't be hard to require it not to have cycles, but cyclic data is actually a major usecase for Rc. A cycle collector wouldn't fix any of the unsafety here unless it was run on literally every drop, which would be far too slow to be acceptable in a systems language. An opt-in trait to prevent leaking specific types would be practical, but the implementation details aren't settled and it can be done backwards-compatibly, so there's a strong feeling that it shouldn't block the release. Any other attempts to determine whether cyclic data structures always eventually drop their contents enter very-active-research territory and would be more like a ten year than a few week thing.

deleted 12y ago
[deleted]
pcwalton 12y ago
Precisely. Rc is not easy to "fix": the fact that it allows cycles is part of its design.
- mcguire 12y ago
  There's a reason why finalizers aren't a widely used technique in Java and why Python's cycle detector simply stacks things with destructors in an out-of-the-way location.
  - Jweb_Guru 12y ago
    Those languages have bigger problems than Rust here. Rust can still recover correct behavior for APIs like scoped because it can ensure (using lifetimes) that the relevant value never escapes the stack frame. In the languages you mention (and most other languages with a "with" or "IDisposable" equivalent), the "close" equivalent, or even the finalizer, can be called on objects that still have valid references to them hidden in another object or thread.
    - mcguire 12y ago
      I was actually speaking of the original finalize method it Java[1]. There's no guarantee that it will be called, there's no guarantee when it will be called if it is, and as a result it shouldn't be used to reclaim resources or much of anything, really. Where "should" is so strong in this case that I've never seen it in the wild, even given the N-monkeys code that I have seen. [1] http://www.informit.com/articles/article.aspx?p=1216151&seqNum=7 http://www.informit.com/articles/article.aspx?p=1216151&seqN...
- haberman 12y ago
  I don't know enough about how Rc is used to know if this is an acceptable possibility, I just wanted to mention it in case it is possibly helpful. I developed a reference-counting system in my library "upb" that handles cycles and never leaks objects. It is precise for no-longer-mutable objects (objects which may no longer change the set of other refcounted objects pointed to) and less precise for mutable objects. The basic idea is to reference-count groups of objects instead of single objects, and define the groups such that no reference cycle spans groups. If you introduce a link between two refcounted objects A -> B, then A and B's groups are merged. Now refs/unrefs of A or B ref/unref the (merged) group. Nothing in the group is freed until both A and B's refcounts both fall to zero. This conservative group-merging whenever you create a link ensures that no reference cycle spans groups. This is imprecise and relatively wasteful if the group grows really large. But you can make it totally precise for any subgraph of refcounted objects that you're willing to freeze. At freeze time, compute strongly-connected components, and each SCC becomes a refcounted group. For any frozen subgraphs, the refcounting is totally precise. And unfrozen objects can reference frozen ones (but not the other way around). If your application ends up freezing most of the graph, this works great. Or if you're ok with the collection being pretty coarse for your groups of objects, it also works great. If you have an application that can't freeze the graph and wants pretty precise collection, this doesn't work so well. More info about my scheme is in comments in these headers: https://github.com/haberman/upb/blob/master/upb/refcounted.h https://github.com/haberman/upb/blob/master/upb/refcounted.h https://github.com/haberman/upb/blob/master/upb/refcounted.c https://github.com/haberman/upb/blob/master/upb/refcounted.c I always was curious if the semantics of this scheme would play nicely with the ownership system in Rust.
  - haberman 12y ago
    btw, I never did this in my library because I didn't need to, but you could also support an operation that computes SCC's to minimize the groups without freezing the graph. The minimized groups would still merge with other groups if you created links between them. But this would be a way to make the refcounting more precise without strictly requiring that subgraphs become immutable.

deleted 12y ago

[deleted]

pcwalton 12y ago

Precisely. Rc is not easy to "fix": the fact that it allows cycles is part of its design.

mcguire 12y ago
There's a reason why finalizers aren't a widely used technique in Java and why Python's cycle detector simply stacks things with destructors in an out-of-the-way location.
- Jweb_Guru 12y ago
  Those languages have bigger problems than Rust here. Rust can still recover correct behavior for APIs like scoped because it can ensure (using lifetimes) that the relevant value never escapes the stack frame. In the languages you mention (and most other languages with a "with" or "IDisposable" equivalent), the "close" equivalent, or even the finalizer, can be called on objects that still have valid references to them hidden in another object or thread.
  - mcguire 12y ago
    I was actually speaking of the original finalize method it Java[1]. There's no guarantee that it will be called, there's no guarantee when it will be called if it is, and as a result it shouldn't be used to reclaim resources or much of anything, really. Where "should" is so strong in this case that I've never seen it in the wild, even given the N-monkeys code that I have seen. [1] http://www.informit.com/articles/article.aspx?p=1216151&seqNum=7 http://www.informit.com/articles/article.aspx?p=1216151&seqN...
haberman 12y ago
I don't know enough about how Rc is used to know if this is an acceptable possibility, I just wanted to mention it in case it is possibly helpful. I developed a reference-counting system in my library "upb" that handles cycles and never leaks objects. It is precise for no-longer-mutable objects (objects which may no longer change the set of other refcounted objects pointed to) and less precise for mutable objects. The basic idea is to reference-count groups of objects instead of single objects, and define the groups such that no reference cycle spans groups. If you introduce a link between two refcounted objects A -> B, then A and B's groups are merged. Now refs/unrefs of A or B ref/unref the (merged) group. Nothing in the group is freed until both A and B's refcounts both fall to zero. This conservative group-merging whenever you create a link ensures that no reference cycle spans groups. This is imprecise and relatively wasteful if the group grows really large. But you can make it totally precise for any subgraph of refcounted objects that you're willing to freeze. At freeze time, compute strongly-connected components, and each SCC becomes a refcounted group. For any frozen subgraphs, the refcounting is totally precise. And unfrozen objects can reference frozen ones (but not the other way around). If your application ends up freezing most of the graph, this works great. Or if you're ok with the collection being pretty coarse for your groups of objects, it also works great. If you have an application that can't freeze the graph and wants pretty precise collection, this doesn't work so well. More info about my scheme is in comments in these headers: https://github.com/haberman/upb/blob/master/upb/refcounted.h https://github.com/haberman/upb/blob/master/upb/refcounted.h https://github.com/haberman/upb/blob/master/upb/refcounted.c https://github.com/haberman/upb/blob/master/upb/refcounted.c I always was curious if the semantics of this scheme would play nicely with the ownership system in Rust.
- haberman 12y ago
  btw, I never did this in my library because I didn't need to, but you could also support an operation that computes SCC's to minimize the groups without freezing the graph. The minimized groups would still merge with other groups if you created links between them. But this would be a way to make the refcounting more precise without strictly requiring that subgraphs become immutable.