Subject: Re: tranformations and node visiting
From: Craig Chambers (chambers@cs.washington.edu)
Date: Fri Mar 02 2001 - 13:41:14 PST
Congrats on tracking this sucker down! I guess this is an example of the
"modify collection during iteration" classic bug. In general, it's really hard
to do this safely. We have the do_[associations_]allowing_updates operations
over collections to force them to protect themselves from updates that might
happen during iteration, but I don't think this works for all collections for
all possible mutations, only for modifications to/removals of the element
currently being iterated over, and in some cases also for new elements added to
the collection during iteration.
We could have a graph_visit_allowing_updates method (basically, compute the
successors of a node and cache them before calling the user's closure), but I'm
not sure if this handles all the cases we're talking about (I think it doesn't,
actually). Alternatively, we could have that _allowing_updates method cache all
the nodes in the graph into a vector, and then iterate out of that. This is
essentially what you're doing in the solution, except in the client code rather
than in the data structure itself. The drawback of my proposal is that a bunch
of _allowing_updates wrapper methods have to be added to all the various
traversal/do/visit methods over graphs.
-- Craig
Keunwoo Lee wrote:
>
> BTW, Sorin and I talked about this and concluded it was probably a bug.
> I've made a workaround where we accumulate the graph's initial node
> collection in a separate list and iterate over that list, thereby avoiding
> the mutation-while-iterating problem.
>
> My code, which was formerly breaking, now appears to be running smoothly.
>
> There's probably a better way to do this that doesn't involve allocating a
> list that's the length of the original graph, but right now we just need a
> quick fix.
>
> I think I will commit just transform-implementation.cecil (should have no
> dependencies on other changes I've made) tonight, if towers builds without
> dying.
>
> ~k.lee
>
> On Thu, 1 Mar 2001, Keunwoo Lee wrote:
>
> > I put forth the following question about node transformation code:
> >
> > Given:
> >
> > a. apply_transformations (in transform-implementation.cecil:15) uses
> > graph.nodes_do( ... ) to visit each node and determine if it needs a
> > transformation.
> >
> > b. nodes_do, as defined for most slices, ultimately uses
> > visit_graph_nodes to iterate over all nodes.
> >
> > c. visit_graph_nodes uses each node's succ_nodes to determine where to
> > traverse next.
> >
> > What is to prevent apply_transformations from
> >
> > 1. Visiting a node which it has just patched into the graph (because that
> > node is now a succ_node of some other node in the current graph).
> >
> > 2. Using this node's ID to index into the list of transformations.
> >
> > 3. Picking a bogus transformation to perform on that node.
> >
> > ?
> >
> > ~k.lee
>
> _______________________________________________
> Cecil mailing list
> Cecil@cs.washington.edu
> http://majordomo.cs.washington.edu/mailman/listinfo/cecil
_______________________________________________
Cecil mailing list
Cecil@cs.washington.edu
http://majordomo.cs.washington.edu/mailman/listinfo/cecil
This archive was generated by hypermail 2b25 : Fri Mar 02 2001 - 13:42:04 PST