From: itsme213 <itsme213@...>
Date: 2004-12-14T13:07:19+09:00
Subject: Re: How to make a deep copy of an object (Searching for Idiom) [Object State]

If your deep copy corresponds to a notion of object state deeper than its
immediate instance variables, and you need to do other state-related
traversals of your object graph, this might help.

"Robert Klemme" <bob.news@gmx.net> wrote in message
news:32010qF3gk6feU1@individual.net...

> There's a much more serious problem with the proposed implementation: it
> does not cope with graphs of objects that contain cycles.

Often a graph with cycles can be naturally decomposed into:
(a) a tree(or several trees), plus
(b) a bunch of non-tree edges

If your objects have a 'containment' structure, or clean boundaries of
object state, or a natural XML representation of element nesting vs. idrefs,
you likely have such a tree structure. You can iterate separately over the
two subgraphs: the tree portion (knowing it will have no cycles), and the
cross-tree edges (knowing all nodes to be copied have already been copied).

class MyNode
    #each_tree_edge #each_cross_tree_edge are application dependent
    # parent_node, source_node params not needed for deep_copy
    def each_tree_edge # {|parent_node, child_attr, child_node| .. }
        # class-specific iterator
    end
    def each_cross_tree_edge # {|source, cross_attr, related_node| .. }
        # class-specific iterator
    end
    def rec_each_tree_edge &block
        each_tree_edge { |p, a, n|
            yield p, a, n
            n.rec_each_tree_edge &block
        }
    end
    def rec_each_cross_tree_edge &block
        each_cross_tree_edge {|s, a, n| yield s, a, n}
        each_tree_edge {|s, a, n| n.rec_each_cross_tree_edge &block}
    end
    def deep_copy (h = {})
        cp = self.class.new
        h[self.id] = cp
        each_tree_edge { |p, iv, n|
            cp.instance_variable_set iv, n.deep_copy(h)
        }
        rec_each_cross_tree_edge { |s, iv, n|
            cp.instance_variable_set iv, h[n.id]
            # assumes no sharing between copy and original
            # alternately: cp.instance_variable_set iv, (h[n.id] || n)
        }
        cp
    end
end

# example
class House
    attr_accessor :roof, :garage, :subdivision
    def each_tree_edge
        yield self, "@roof", roof
        yield self, "@garage", garage
    end
    def each_cross_tree_edge
        yield self, "@subdivision", subdivision
    end
end

class Garage
    attr_accessor :door, :house
    def each_tree_edge
        yield self, "@door", door
    end
    def each_cross_tree_edge
        yield self, "@house", house
    end
end

If all state is in instance variables you could implement Object#deep_copy
once. Otherwise you need special case handling for Arrays, Hashes, and other
built-ins; and may need to further distinguish arrays used for multiple tree
edges vs. for multiple cross-tree edges. A few judicious macros can hide the
fact that the array itself is purely a Ruby implementation artifact for a
many-relationship, whether tree or cross_tree, and generate the iterators,
so all you would need to say is:
class House
    contains_one :roof, :garage # tree
    has_one :subdivision # cross tree
    contains_many :rooms # tree
    has_many :neighbors # cross tree
end
class Garage
    contains_one :door
    has_one :house # smarter macro would do inverses
end

You could get a consistent family of methods -- deep_copy, deep_equal,
deep_freeze, marshal_dump, marshal_load, etc. -- automatically from such
macros (except that #copy and #equal can be controlled at the level of
individual instance variables or accessors, while the built-in #freeze
cannot).

If you need finer-grained control than overriding the iterators at the class
level (similar to the earlier discussion of #freeze and object state), you
could parameterize on which accessors need to be traversed from a given node
i.e. pass around some kind of 'metagraph' parameter: a metanode could be as
simple as a hash of accessor symbols, each mapping to another corresponding
metanode. A metagraph, applied to some graph of objects, exposes (projects)
some portion of that graph via #each.... But then again, at some point you
might really be better off with a good macro library that can manipulate
relations (nested, not flat) and the kind of projection operation the
metagraph is trying to do :-)

> > Maybe it would make sense to extend the base classes Object, Array, Hash
> > with a
> > deep-copy functionality. That would be something for the extensions
> > project.
>
> IMHO not.  Reason beeing that the semantics of deep copy are class
> dependend.  You might not want to copy all instances in an object graph
for
> deep copy and that might totally depend on the class at hand and / or
(even
> worse) application.  IMHO there is no real general solution to thid.  Of
> course you could define a method in Object like

True, they are (at least) class dependent. The above is one approach to
providing that
customization by deferring the tree- and nontree-traversal control, and
providing a generic Object#deep_copy based on those methods.  This can then
be used for other traversals besides deep_copy.

But does it work ? and is it worth it ? :-)