On 11-03-15 10:29 AM, Rafael Avila de Espindola wrote:
When handling
fn foo() {
fn zed(bar z) {
}
tag bar {
nil;
}
fn baz() {
zed(nil);
}
}
we currently do two passes in trans.rs. The first pass collects the tags
so that they can be used when collecting zed.
One way to avoid this is to have ty_tag point to the tag item. The
problem if we do that is that we get a cycle:
item_tag -> vec[variant]
variant -> ann
ann -> middle.ty.t (ty_tag)
middle.ty.t -> item_tag
so we would have to make one of the links mutable :-(
Do you guys think it is worth it? Which link do you prefer? Maybe you
have another idea to avoid the multiple passes without introducing the
cycle?
We discussed this on IRC, but I'll follow up here to summarize (it seems
our IRC network will not be logged any time soon; I'm working on
figuring out whether that can be made so).
My "short answer" was that I'm not interested in making the ast or ty.t
types mutable+cyclic, because it introduces a lot of potential
difficulty elsewhere (moves it to the gc layer, possibly undermines
parallelism, makes other code have to rebuild direct pointers properly,
makes folds complicated-to-impossible, depending on link).
We then had a longer discussion about whether there were any possible
alternatives, in particular trying to devise ways of addressing
potential performance costs of (a) constantly rebuilding the tree and
(b) having to keep it acyclic due to immutability.
For (a) I suggested a visitor for each node but does *not* rebuild, but
looks and possibly builds worklists for interesting subsets of the AST.
Somewhat like fold; in fact fold originally was built with the ability
to function this way; but it involved taking some 20-odd type parameters
to unify the roles and was quite cumbersome. Probably just a separate
module that walks an obj type through a tree will be sufficient.[1]
For (b) I had no ideas, but espindola suggested that a gc root could be
floated out to the maximum acyclic node in a constant structure;
pcwalton pointed out that the freeze/thaw scheme we've been discussing
for the future may well be able to integrate this with a sort of managed
weak pointer for the interior nodes, which immediately made me think of
the const refcount, and the similarity this idea has with the ideas
we've been pushing around for handling single-writer / multi-reader
multithreading as an optimized pattern for large frozen structures.
Ultimately we agreed (I think!) to defer the concept to when we're
implementing 'freeze', with the understanding that it would be very
desirable to be able to freeze not just mutables but *cyclic* mutables
into an immutable structure. So possibly we wind up with the output from
freeze being *const*, with only the root being refcounted-immutable. Or
something along these lines.
Anyway, that's a summary of how I saw the conversation unfold; correct
anything you see as wrong in this summary. It got a little heated and I
don't want to misrepresent anyone's opinion.
-Graydon
[1] Fold should really be an obj eventually; we just didn't have
obj-extension working in rustboot at the time
_______________________________________________
Rust-dev mailing list
[email protected]
https://mail.mozilla.org/listinfo/rust-dev
