Tricky semantics of ranges & potentially numerous Phobos bugs

[H. S. Teoh]

On Tue, Oct 16, 2012 at 11:00:18PM +0200, Philippe Sigaud wrote:
> On Tue, Oct 16, 2012 at 9:41 PM, H. S. Teoh <hsteoh at quickfur.ath.cx> wrote:
[...]
> > I think with D's compile-time introspection capabilities, it
> > _should_ be possible to implement a generic deepCopy template that
> > works for any type.
> 
> I agree. Heck, IIRC I posted a putative deep copy code here some years
> ago. Today's Phobos and __traits and the recently improved is()
> expression would make that even easier.
> After all, any (aggregate) value in D can be decomposed into smaller
> parts, until the algorithm finds a leaf/terminal: either a value type
> or an array of value types.

I just thought of a potential problem. Right now I don't think there's a
way to tell whether a reference is a "hard" reference or an "external"
reference. For example, if you have a tree in which nodes reference some
global table of objects, you want to deep-copy only the tree nodes, not
the objects they refer to, otherwise you may end up duplicating the
entire global table every time you duplicate a tree.


> > Of course, then one has to address tricky issues such as complex
> > data structures that have interlinking parts; a blind recursive
> > deep-copy may not have the desired effect (e.g., if we're
> > deep-copying a graph and there are multiple paths (via references)
> > to the same node, then we shouldn't end up with multiple copies of
> > that node). Some care will also need to be taken to deal with cyclic
> > structures, etc.. And some optimizations can probably be done to
> > avoid copying immutable objects, since that would be a waste of time
> > & memory.
> 
> Good idea. Detecting immutable seems easy. Doing a graph traversal is
> a bit trickier.

I was thinking probably a bool[void*] should work as a way of keeping
track of what has already been copied, so a simple depth-first traversal
should work. And maybe another T[void*] for looking up cross-edges in
the DFS tree.


T

-- 
One disk to rule them all, One disk to find them. One disk to bring them
all and in the darkness grind them. In the Land of Redmond where the
shadows lie. -- The Silicon Valley Tarot