PRs removing RefCells, longer term plans

[pythonesque]

Append-only or otherwise monotonically “increasing” structures could also be fruitful. There are many tables in the compiler which accumulate new entries but never lose old ones. As long as you avoid reallocations, append-only mutation need not invalidate extant borrows. LVars are an abstraction from the world of concurrency which attempt to capture the core notion of such monotonic growth. Perhaps there is a single-threaded analogue?

Rustc already leans heavily on arenas for this purpose (it doesn’t let you iterate over them but that’s more an accident of the API than anything else, I suspect).

[Diggsey]

I think the fundamental restriction of Cell is that you shouldn’t be able to borrow anything owned by the cell for a lifetime which is tied to the Cell itself. (There’s probably some mathematical name for this!)

With a Cell<Rc<T>>, all references to T are protected by Rc’s own borrow machinery, so there shouldn’t be any unsafety (provided Rc’s clone implementation doesn’t leak a reference to &self into user code).

An unsafe trait implemented for all Copy types by default would do the trick. (But what to call it? TransparentClone?) You’d also need a completely separate trait for the multithreaded one (AtomicClone?)

[pythonesque]

With a Cell<Rc<T>>, all references to T are protected by Rc’s own borrow machinery, so there shouldn’t be any unsafety (provided Rc’s clone implementation doesn’t leak a reference to &self into user code).

I suppose a "write only’ variant of Cell<Rc<T>> might be safe, but write only is the effective outcome if you can’t take any references into the Rc. If you could take references into it and write to it, it’s a recipe for memory unsafety, since setting the interior value could still drop things inside the Rc. If you can’t drop things inside the Rc, then it sounds identical to Rc<Cell<T>>, which is aleady safe (albeit relatively uncommon, probably because Cells tend to be embedded within larger structures).

An unsafe trait implemented for all Copy types by default would do the trick. (But what to call it? TransparentClone?) You’d also need a completely separate trait for the multithreaded one (AtomicClone?)

I think you could probably just go with TransparentClone + Sync; if a type is (1) thread safe and (2) has a clone implementation, then it must be safe to clone across threads, and if it additionally (3) guarantees that the clone doesn’t have shared ownership, I think that fulfills all our requirements, no? I admit I haven’t thought about this too carefully.

Edit: Actually yeah, it wouldn’t really work because atomics don’t really last long enough to do something like this. In my experience, any code that does pointer manipulation with atomics is very subtle; Cell has the luxury of having infinite time to perform its atomic operation.

[nikomatsakis]

Hmm. This is an interesting discussion, though a bit far afield of the original question. @pythonesque and @bkoropoff, I definitely enjoyed your take on why RefCell is bad. I’m sort on the fence here. I want us to use the Rust type system in the best way, and I do find that (in general) pursuing stricter divisions of mutable/immutable state makes the code clearer, will help us avoid ICEs, and so forth. OTOH, the current system is pretty simple and scalable, and I don’t see any huge problems with it.

On balance, I think I am currently in favor of removing the RefCell usage. If nothing else, it may help us to identify things we could change in Rust to make this more ergonomic. But also, if we were writing the compiler from scratch in today’s Rust, I think we would use a lot less RefCell. I suspect over time we will be able to refactor the code in the PRs further so that it is cleaner and requires less manual context passing. Basically, if we DO this change, it seems like overall a sideways step now or maybe a step back in terms of “cleanliness”, but it puts on a path that I think leads to a better tomorrow.

Note that there are some specific decisions I don’t like in the PRs. For example, I want to keep Typer as an object-safe trait, because it cuts down on generic costs (and avoids extra code gen costs). In general objects make the code so much nicer. But probably the best thing is for me to check out the PRs and play around with them; doing so often gives me an appreciation for the choices the author made originally. =)

Regarding parallel constructs and phasing:

I actually LIKE the current compiler structure where things are written in distinct phases and passes. Probably we need clearer documentation, but I think in the end pass-oriented structure is easier to reason about than when things occur in a lazy order (the usual alternative). It’s also more parallel friendly (maps to fork-join in a trivial way, whereas laziness requires a kind of micro-task-graph). I’ve certainly found when reading other compilers that those which use a more lazy scheme can be harder to understand, because the control-flow is very data-dependent, versus those that use a series of passes are relatively easy to diagram and describe.

But I suspect we need clearer documentation about what will be written when. The PR by @Aatch https://github.com/rust-lang/rust/pull/22564 suggested one route here. Basically for those bits of data that will be “filled in” later, the struct includes an ivar (which is a write-once cell that begins empty, essentially). This ivar gives a natural place to document when the value will be provided and so forth, and makes it easy to diagnose when you are accessing data that is not yet supplied.

[llogiq]

At the very least, it would be worthwhile explicitly annotating every use of RefCell to explain why it’s guaranteed to never be borrowed multiple times (checking that would make quite a nice lint)

So how would those annotations look like and how would a lint pick them up?

[pythonesque]

As far as Typer specifically, I tried to keep it object safe for precisely that reason, but ran into other issues (I unfortunately don’t recall what they precisely were now, but I’m sure you will find it quickly if you start messing around with it ). I think arielb1 presented a good way forward long term with Typer (and actually, part of the reason I started working on trans next was because it’s one of the biggest non-typeck consumers of Typer, if not the biggest).

If you’re looking or specific things that would make refactoring like this easier in the future, the single biggest is of course nonlexical lifetimes, but this isn’t news to anyone ). Being able to skip writing out all the lifetime parameters when you really just need to specify one of them would also help ergonomics a lot, as well as the “group” thing I mentioned.

I actually LIKE the current compiler structure where things are written in distinct phases and passes. Probably we need clearer documentation, but I think in the end pass-oriented structure is easier to reason about than when things occur in a lazy order (the usual alternative). It’s also more parallel friendly (maps to fork-join in a trivial way, whereas laziness requires a kind of micro-task-graph). I’ve certainly found when reading other compilers that those which use a more lazy scheme can be harder to understand, because the control-flow is very data-dependent, versus those that use a series of passes are relatively easy to diagram and describe.

Hopefully, I conveyed in my post that I don’t think it’s bad to do things in phases, exactly. What I was getting at was that it feels extremely difficult to make alterations to the high level structure of the compiler (e.g. changing order of phases) because the contracts are relatively fragile, affect tons of code, and aren’t compiler-checked. Obviously, it’s a fairly large project and it’s never going to be easy to make sweeping changes, but more flexibility can’t be a bad thing, surely!

My only concern with the ivars was that we’re paying a runtime cost for the privilege, and this time one not required for memory safety. But the cost isn’t all that high and it’s not like the compiler is exactly microoptimized anyway, so adding something that will help us catch bugs can only be a good thing, I suppose. I do feel like it should be possible to do in a way that you don’t usually have to pay the cost, though: e.g., once you’re done with pass x, go double check to make sure all values you’re expecting to be set are set, and then turn them from Cell<Option<T>> into just T as a “type” transformation that only takes place at compile time (this is easier without the Option, and easier still if when the types are modifiable you have &mut references, since you can just shuttle your reference off to live behind something immutable whenever you want to freeze them, which lets you do a whole bunch of them at a time; BTW, am I wrong in thinking that if you have &mut Cell<T> you should be allowed to take direct references into its inner value?)). Anyway… like you said, extending Cell's functionality is really a separate discussion.

[nikomatsakis]

What I was getting at was that it feels extremely difficult to make alterations to the high level structure of the compiler (e.g. changing order of phases) because the contracts are relatively fragile, affect tons of code, and aren’t compiler-checked.

Yes, this is a downside of a more phase-oriented structure. It is also sometimes limited, in that there are language constructs which sometimes cannot be easily ordered. So I feel like we should take advantage of it where it makes sense, but not everywhere. I could be persuaded that moving entirely to a lazier architecture makes sense as well, but I’d definitely rather go there more gradually.

My only concern with the ivars was that we’re paying a runtime cost for the privilege, and this time one not required for memory safety.

I think the runtime cost is negligible. And of course the runtime cost IS required for memory safety in the absence of some fancy type features (or some transmutes). Both of these will however introduce divergence into the type signatures (now we have distinct types for “a class def’n before field X is set” and “a class def’n after field X is set”. This is nice, but it affects all consumers of the code, and you wind up writing a lot of very generic code (I’ve been down this path in past lives…). I’m not sure it’s worth it overall. But, in any case, writing the code with ivars is a natural first step.

[arielb1]

Rc's Clone impl is actually perfectly safe (it can’t invalidate anything). The Drop impl is somewhat problematic, however - when you are assigning, you must only drop the Rc after you placed a new value. This is more problematic in the concurrent case, because you can drop the Arc between a thread reading it and cloning it, so you need more synchronization, e.g. some kind of hazard pointers (e.g., Linux uses RCU in its AtomicOptionArc-s).

[Diggsey]

So how would those annotations look like and how would a lint pick them up?

I was thinking of just using a doc-comment on the declaration. They’d follow a particular pattern which a lint could recognise by starting with a known prefix or something:

/// Borrows: mutably borrowed once between each pass
foo: RefCell<Bar>

It’s then immediately obvious how ‘foo’ is used by the program, and when it’s safe to borrow ‘foo’ either mutably or immutably.

[comex]

(maps to fork-join in a trivial way, whereas laziness requires a kind of micro-task-graph)

But if you manage to serialize that graph to disk, you have something like a holy grail of incremental compilation

(I have never implemented something like this, so I do not know how feasible it would be in practice!)

[michaelwoerister]

But if you manage to serialize that graph to disk, you have something like a holy grail of incremental compilation

I think in practice this kind of graph would have too fine a granularity to do this effectively and without invading nearly every aspect of the code, making it rather hard to read.

[bkoropoff]

My speculation went a bit off track, but what I want to emphasize is that there are other abstractions which permit safe mutation through shared references but cannot fail at runtime, e.g. append-only vectors, insert-only hash tables, etc. This would give us extra flexibility in removing uses of RefCell without plumbing around mutable references or splitting structures.

In cases where RefCell is used gratuitously and we just need to pass some context structure by mutable reference instead, I think it’s a clear win to do so. Generally I think @pythonesque has the right idea, I just want to make sure we’re exploring other options in the design space. I don’t think Cell and RefCell are the last word in single-threaded interior mutability.

[michaelwoerister]

I haven’t had the time to look through the PRs in detail, but in general I’m in favor of moving away from RefCell and towards &mut where possible. Let’s use the static guarantees that the language provides us with.

I have this notion (which hasn’t yet made too much corrosive contact with reality) that it should be possible to structure things into passes that build up/aggregate some kind of information data-structure (which gets threaded through as an &mut or is a return value) while the information objects from previous passes are threaded through as shared references:

fn compile() {
    let ast = parse();
    let resolve_map = resolve(&ast);
    let polytypes = collect(&ast, &resolve_map);

    ...
}

Working data needed by the pass would then be passed through in an &mut context object. This is especially viable for passes with many small, independent work packages, like type-inference and function translation. I think that’s pretty much the direction the discussed PRs start off into.

For things that need to be shared and mutated by multiple threads (e.g. monomorphized functions impls) this won’t work but I think the idea of strictly growing data-structures, as has been discussed above, will be a good strategy in most cases. We effectively have this already for many things like interned ty::Tys and many of the caches being built up throughout.

I’ve just looked through the trans PR a bit and one thing I find a bit troublesome is that before Cells and RefCells clearly marked things that could change and one could rely on everything else to not change. Now there is no more distinction between “mutable” and “immutable” fields anymore (this is one of the cases where I’d like to have const fields that can’t be mutated after initialization even through a mutable reference). I guess it’s a trade-off between having to remember which fields not to mutate and having to fear runtime errors. I’m surprised to say that, from a documentation point of view, &FunctionContext + Cell/RefCell might be better than &mut FunctionContext. It could be worked around some by making fields private and only providing getters though. And I don’t suspect this to be a big problem as long as passes and their context objects are focused enough and don’t contain too much stuff that isn’t actually needed.

[nikomatsakis]

Now there is no more distinction between “mutable” and “immutable” fields anymore (this is one of the cases where I’d like to have const fields that can’t be mutated after initialization even through a mutable reference).

Yes, sometimes I wish that we required you to mark fields as mut in order to change them directly (even though, of course, one could change them by reassigning the struct entirely). I guess being able to mark fields as const would move back in that direction in a compatible way. Usually I don’t find this problematic because most state isn’t shared that widely; even here, grep’ing through trans isn’t hard, but of course it’s nicer to see it at your fingertips.

[nikomatsakis]

I have this notion (which hasn’t yet made too much corrosive contact with reality) that it should be possible to structure things into passes that build up/aggregate some kind of information data-structure (which gets threaded through as an &mut or is a return value) while the information objects from previous passes are threaded through as shared references

Some time ago I put this style into practice (at small scale) in the variance inference. I found it worked ok, but I’m not sure how it would scale up to bigger things. I think it might work better with either struct extension or perhaps just abusing Deref – it gets annoying to remember that, in order to access (e.g.) the AST, you need to do polytypes.resolve_map.ast.nodes[3] vs just cx.ast_nodes[3].

[nikomatsakis]

Generally I think @pythonesque has the right idea, I just want to make sure we’re exploring other options in the design space. I don’t think Cell and RefCell are the last word in single-threaded interior mutability.

Oh, I absolutely agree with this. I’ve been wondering about monontonic, non-moving data structures for a while. But I’ve yet to experiment with building one. In my experiments in that direction, I found that perhaps a persistent data structure would work better – in particular I was experimenting with different versions of persistent that were oriented at short-lived snapshots and a single master copy, trying to reduce the overhead of inserting data and so forth in that scenario.

The advantages of a persistent data structure is that it shares many of the same properties, but it is able to reorganize and reallocate its internal structure freely. Maybe I wasn’t thinking hard enough, but all the ideas I had for monotonic, non-moving hashtables and the like seemed to have poor lookup performance over time. And of course if you have a persistent data-structure, you can wrap it in an Rc (or Arc) and trivially extract and clone it, and then the user gets a nice snapshot.

Of course, if possible, I find IVars even more appealing: that is, leave a hole for the data, create a standard hashmap or set or whatever sequentially, and then plug it in. But I’ve found that in practice most of the maps DO wind up being mutated in later stages, though often it’s only during cross-crate inlining. If we moved away from using global maps, this would be much less of an issue.

Yesterday I started, but didn’t have time to get very far with (story of my life these days, it seems like), going through the data structures and trying to document and list up where they are modified from. I want to sketch out in more detail what I am talking about with regard to per-fn data structures, as well as identifying problematic cases in advance.

[pythonesque]

Oh, I absolutely agree with this. I’ve been wondering about monontonic, non-moving data structures for a while. But I’ve yet to experiment with building one. In my experiments in that direction, I found that perhaps a persistent data structure would work better – in particular I was experimenting with different versions of persistent that were oriented at short-lived snapshots and a single master copy, trying to reduce the overhead of inserting data and so forth in that scenario.

Hm… now I have some interesting ideas for how we might go about this based on MVCC databases, particularly how they handle things like lock elision, update chaining, and tombstoning. I’d never considered applying such ideas in a single-threaded context, but now that I am thinking about it I think it could both be done and made way simpler In particular, imagine using stuff like versioned transactions and value locking to get strong safety and correctness guarantees with very little extra overhead, using lifetimes for correctness only at a very coarse level. I realize this is pretty abstract, but I think together with HKTs you could effectively turn any strict collection into a persistent one without losing much performance (maybe even making the performance losses entirely opt-in). Let me play around with it…

[michaelwoerister]

Yes, sometimes I wish that we required you to mark fields as mut in order to change them directly (even though, of course, one could change them by reassigning the struct entirely)

Yes, overwriting the whole struct is always possible. However, my motivation for wanting to have const fields was always more a question of keeping a composite value internally consistent and not of preventing some memory slot from being mutated. But that’s just a side remark and not really important to this discussion.

[michaelwoerister]

or perhaps just abusing Deref – it gets annoying to remember that, in order to access (e.g.) the AST, you need to do polytypes.resolve_map.ast.nodes[3] vs just cx.ast_nodes[3].

Do you have an example to look at where Deref is used in such a way?

[arielb1]

rustc typically uses getter methods (e.g. every instance of fn tcx)