Tying the knot with @

[huonw]

At the moment there doesn't seem to be a way to create an @ graph that has a cycle in it, without an @mut or &mut somewhere in its ownership tree, and so one can't write something that does, for example:

struct Foo { name: ~str, other: @Foo }

let a = @Foo { name: ~"a", other: b };
let b = @Foo { name: ~"a", other: a };

without using @mut, even though construction is the only time mutability is required.

(Examples of where it would be useful: part 1, part 2, one from IRC: log, code)

[Thiez]

I presented a toy example on irc of how one might still be able to construct an @ graph with a cycle and huonw thought it might be relevant. Note that the example has to use an Option<@Foo> because the compiler prohibits struct Foo{ other: @Foo }. This makes sense; one could not safely initialize such a type. However one can do so unsafely (with a technique similar to the one shown below) and the resulting struct should be safe to use after initialization. Perhaps it would be more appropriate for the compiler to merely warn for such structs rather than forbidding them entirely?

struct Foo {
  name: ~str,
  other: Option<@Foo>
}

fn circle(s:~str) -> @Foo {
  unsafe {
    let f = @Foo{ name:s, other:None};
    let x = Some(f);
    std::ptr::copy_nonoverlapping_memory::<Option<@Foo>>(std::unstable::intrinsics::transmute(&f.other), &x, 1);
    f
  }
}

fn main() {
  let f = ~circle(~"Hi");
  println(f.name);
  println(f.other.get().name);
  println(f.other.get().other.get().name);
}

The program prints 'Hi' three times. Exciting.

[nikomatsakis]

Eventually we may permit ~ pointers to be converted to @. That would address this problem nicely. Until then, my preference would be to leave it unsolved.

[huonw]

@nikomatsakis I'm not sure how that would allow a cycle to be created? (It would address the problem of doing complex initialisation of an @ pointer, though, which would be nice.)

[nikomatsakis]

@huonw Hmm, maybe you're right, it doesn't solve it as neatly as I thought, though I think it may still be an ingredient of a solution. My reasoning is that in order to convert from mutable to immutable soundly, you need ~ pointers. So the idea would be to build up your data structure and then switch it from ~ to @. But when I try to write up examples this doesn't quite work as well as I thought. Maybe there is a way to make some unsafe helper fn that can simultaneously convert from ~ to @ and do the assignments, I don't know. Have to think on it.

[bblum]

I could imagine an unsafe-under-the-hood library function to help with this. It would take a list of the structs you want to link together (with Option<@T> fields inside), and a closure that explains how to link them, and calls it for each adjacent pair of elements in the list (including the (last,first) pair). Not sure quite what the type signature would have to be, or if it would have to copy the structs/list in the process. But it seems preferable to a language change.

[glaebhoerl]

I agree that library solutions are usually preferable, though it seems hard to approach the same level of generality. A language feature that could solve the problem without being special-cased for it would be delayed initialization of struct fields, as with lets. But I have no idea what kind of restrictions the compiler could put into place to prove it safe while still being useful and scalable. E.g.:

struct Fractal { l: @Fractal, r: @Fractal }

let a = @Fractal { l: _, r: _ }
let b = @Fractal ( l: _, r: _ }
a.l = a;
a.r = b;
b.l = a;
b.r = b;

How do you safety-check that? Seems nontrivial.

[graydon]

Yeah, generally seems low priority. I imagine you'd have an easier time making the graph owned at the top, allocating nodes from an arena, and making edges out of option<&node>.

[thestinger]

If you're able to make a cyclic graph with @T where T is Freeze, we will need to remove the implementations of DeepClone, Eq, etc. completely because they do not handle cycles. These standard implementations only make sense if they are always correct because they prevent a user-defined version of the trait for @UserType.

[thestinger]

Nominating for the backwards compatible milestone, although I don't really think we should do this.

[huonw]

I agree that having the guarantee that <T:Freeze> @T is non-cyclic is a very useful one; I'm tempted to withdraw this proposal unless someone is strongly in favour.

[catamorphism]

wontfix