1 """Generic (shallow and deep) copying operations.

     2 

     3 Interface summary:

     4 

     5         import copy

     6 

     7         x = copy.copy(y)        # make a shallow copy of y

     8         x = copy.deepcopy(y)    # make a deep copy of y

     9 

    10 For module specific errors, copy.Error is raised.

    11 

    12 The difference between shallow and deep copying is only relevant for

    13 compound objects (objects that contain other objects, like lists or

    14 class instances).

    15 

    16 - A shallow copy constructs a new compound object and then (to the

    17   extent possible) inserts *the same objects* into it that the

    18   original contains.

    19 

    20 - A deep copy constructs a new compound object and then, recursively,

    21   inserts *copies* into it of the objects found in the original.

    22 

    23 Two problems often exist with deep copy operations that don't exist

    24 with shallow copy operations:

    25 

    26  a) recursive objects (compound objects that, directly or indirectly,

    27     contain a reference to themselves) may cause a recursive loop

    28 

    29  b) because deep copy copies *everything* it may copy too much, e.g.

    30     administrative data structures that should be shared even between

    31     copies

    32 

    33 Python's deep copy operation avoids these problems by:

    34 

    35  a) keeping a table of objects already copied during the current

    36     copying pass

    37 

    38  b) letting user-defined classes override the copying operation or the

    39     set of components copied

    40 

    41 This version does not copy types like module, class, function, method,

    42 nor stack trace, stack frame, nor file, socket, window, nor array, nor

    43 any similar types.

    44 

    45 Classes can use the same interfaces to control copying that they use

    46 to control pickling: they can define methods called __getinitargs__(),

    47 __getstate__() and __setstate__().  See the documentation for module

    48 "pickle" for information on these methods.

    49 """

    50 

    51 import types

    52 from copy_reg import dispatch_table

    53 

    54 class Error(Exception):

    55     pass

    56 error = Error   # backward compatibility

    57 

    58 try:

    59     from org.python.core import PyStringMap

    60 except ImportError:

    61     PyStringMap = None

    62 

    63 __all__ = ["Error", "copy", "deepcopy"]

    64 

    65 def copy(x):

    66     """Shallow copy operation on arbitrary Python objects.

    67 

    68     See the module's __doc__ string for more info.

    69     """

    70 

    71     cls = type(x)

    72 

    73     copier = _copy_dispatch.get(cls)

    74     if copier:

    75         return copier(x)

    76 

    77     copier = getattr(cls, "__copy__", None)

    78     if copier:

    79         return copier(x)

    80 

    81     reductor = dispatch_table.get(cls)

    82     if reductor:

    83         rv = reductor(x)

    84     else:

    85         reductor = getattr(x, "__reduce_ex__", None)

    86         if reductor:

    87             rv = reductor(2)

    88         else:

    89             reductor = getattr(x, "__reduce__", None)

    90             if reductor:

    91                 rv = reductor()

    92             else:

    93                 raise Error("un(shallow)copyable object of type %s" % cls)

    94 

    95     return _reconstruct(x, rv, 0)

    96 

    97 

    98 _copy_dispatch = d = {}

    99 

   100 def _copy_immutable(x):

   101     return x

   102 for t in (type(None), int, long, float, bool, str, tuple,

   103           frozenset, type, xrange, types.ClassType,

   104           types.BuiltinFunctionType,

   105           types.FunctionType):

   106     d[t] = _copy_immutable

   107 for name in ("ComplexType", "UnicodeType", "CodeType"):

   108     t = getattr(types, name, None)

   109     if t is not None:

   110         d[t] = _copy_immutable

   111 

   112 def _copy_with_constructor(x):

   113     return type(x)(x)

   114 for t in (list, dict, set):

   115     d[t] = _copy_with_constructor

   116 

   117 def _copy_with_copy_method(x):

   118     return x.copy()

   119 if PyStringMap is not None:

   120     d[PyStringMap] = _copy_with_copy_method

   121 

   122 def _copy_inst(x):

   123     if hasattr(x, '__copy__'):

   124         return x.__copy__()

   125     if hasattr(x, '__getinitargs__'):

   126         args = x.__getinitargs__()

   127         y = x.__class__(*args)

   128     else:

   129         y = _EmptyClass()

   130         y.__class__ = x.__class__

   131     if hasattr(x, '__getstate__'):

   132         state = x.__getstate__()

   133     else:

   134         state = x.__dict__

   135     if hasattr(y, '__setstate__'):

   136         y.__setstate__(state)

   137     else:

   138         y.__dict__.update(state)

   139     return y

   140 d[types.InstanceType] = _copy_inst

   141 

   142 del d

   143 

   144 def deepcopy(x, memo=None, _nil=[]):

   145     """Deep copy operation on arbitrary Python objects.

   146 

   147     See the module's __doc__ string for more info.

   148     """

   149 

   150     if memo is None:

   151         memo = {}

   152 

   153     d = id(x)

   154     y = memo.get(d, _nil)

   155     if y is not _nil:

   156         return y

   157 

   158     cls = type(x)

   159 

   160     copier = _deepcopy_dispatch.get(cls)

   161     if copier:

   162         y = copier(x, memo)

   163     else:

   164         try:

   165             issc = issubclass(cls, type)

   166         except TypeError: # cls is not a class (old Boost; see SF #502085)

   167             issc = 0

   168         if issc:

   169             y = _deepcopy_atomic(x, memo)

   170         else:

   171             copier = getattr(x, "__deepcopy__", None)

   172             if copier:

   173                 y = copier(memo)

   174             else:

   175                 reductor = dispatch_table.get(cls)

   176                 if reductor:

   177                     rv = reductor(x)

   178                 else:

   179                     reductor = getattr(x, "__reduce_ex__", None)

   180                     if reductor:

   181                         rv = reductor(2)

   182                     else:

   183                         reductor = getattr(x, "__reduce__", None)

   184                         if reductor:

   185                             rv = reductor()

   186                         else:

   187                             raise Error(

   188                                 "un(deep)copyable object of type %s" % cls)

   189                 y = _reconstruct(x, rv, 1, memo)

   190 

   191     memo[d] = y

   192     _keep_alive(x, memo) # Make sure x lives at least as long as d

   193     return y

   194 

   195 _deepcopy_dispatch = d = {}

   196 

   197 def _deepcopy_atomic(x, memo):

   198     return x

   199 d[type(None)] = _deepcopy_atomic

   200 d[int] = _deepcopy_atomic

   201 d[long] = _deepcopy_atomic

   202 d[float] = _deepcopy_atomic

   203 d[bool] = _deepcopy_atomic

   204 try:

   205     d[complex] = _deepcopy_atomic

   206 except NameError:

   207     pass

   208 d[str] = _deepcopy_atomic

   209 try:

   210     d[unicode] = _deepcopy_atomic

   211 except NameError:

   212     pass

   213 try:

   214     d[types.CodeType] = _deepcopy_atomic

   215 except AttributeError:

   216     pass

   217 d[type] = _deepcopy_atomic

   218 d[xrange] = _deepcopy_atomic

   219 d[types.ClassType] = _deepcopy_atomic

   220 d[types.BuiltinFunctionType] = _deepcopy_atomic

   221 d[types.FunctionType] = _deepcopy_atomic

   222 

   223 def _deepcopy_list(x, memo):

   224     y = []

   225     memo[id(x)] = y

   226     for a in x:

   227         y.append(deepcopy(a, memo))

   228     return y

   229 d[list] = _deepcopy_list

   230 

   231 def _deepcopy_tuple(x, memo):

   232     y = []

   233     for a in x:

   234         y.append(deepcopy(a, memo))

   235     d = id(x)

   236     try:

   237         return memo[d]

   238     except KeyError:

   239         pass

   240     for i in range(len(x)):

   241         if x[i] is not y[i]:

   242             y = tuple(y)

   243             break

   244     else:

   245         y = x

   246     memo[d] = y

   247     return y

   248 d[tuple] = _deepcopy_tuple

   249 

   250 def _deepcopy_dict(x, memo):

   251     y = {}

   252     memo[id(x)] = y

   253     for key, value in x.iteritems():

   254         y[deepcopy(key, memo)] = deepcopy(value, memo)

   255     return y

   256 d[dict] = _deepcopy_dict

   257 if PyStringMap is not None:

   258     d[PyStringMap] = _deepcopy_dict

   259 

   260 def _keep_alive(x, memo):

   261     """Keeps a reference to the object x in the memo.

   262 

   263     Because we remember objects by their id, we have

   264     to assure that possibly temporary objects are kept

   265     alive by referencing them.

   266     We store a reference at the id of the memo, which should

   267     normally not be used unless someone tries to deepcopy

   268     the memo itself...

   269     """

   270     try:

   271         memo[id(memo)].append(x)

   272     except KeyError:

   273         # aha, this is the first one :-)

   274         memo[id(memo)]=[x]

   275 

   276 def _deepcopy_inst(x, memo):

   277     if hasattr(x, '__deepcopy__'):

   278         return x.__deepcopy__(memo)

   279     if hasattr(x, '__getinitargs__'):

   280         args = x.__getinitargs__()

   281         args = deepcopy(args, memo)

   282         y = x.__class__(*args)

   283     else:

   284         y = _EmptyClass()

   285         y.__class__ = x.__class__

   286     memo[id(x)] = y

   287     if hasattr(x, '__getstate__'):

   288         state = x.__getstate__()

   289     else:

   290         state = x.__dict__

   291     state = deepcopy(state, memo)

   292     if hasattr(y, '__setstate__'):

   293         y.__setstate__(state)

   294     else:

   295         y.__dict__.update(state)

   296     return y

   297 d[types.InstanceType] = _deepcopy_inst

   298 

   299 def _reconstruct(x, info, deep, memo=None):

   300     if isinstance(info, str):

   301         return x

   302     assert isinstance(info, tuple)

   303     if memo is None:

   304         memo = {}

   305     n = len(info)

   306     assert n in (2, 3, 4, 5)

   307     callable, args = info[:2]

   308     if n > 2:

   309         state = info[2]

   310     else:

   311         state = {}

   312     if n > 3:

   313         listiter = info[3]

   314     else:

   315         listiter = None

   316     if n > 4:

   317         dictiter = info[4]

   318     else:

   319         dictiter = None

   320     if deep:

   321         args = deepcopy(args, memo)

   322     y = callable(*args)

   323     memo[id(x)] = y

   324     if listiter is not None:

   325         for item in listiter:

   326             if deep:

   327                 item = deepcopy(item, memo)

   328             y.append(item)

   329     if dictiter is not None:

   330         for key, value in dictiter:

   331             if deep:

   332                 key = deepcopy(key, memo)

   333                 value = deepcopy(value, memo)

   334             y[key] = value

   335     if state:

   336         if deep:

   337             state = deepcopy(state, memo)

   338         if hasattr(y, '__setstate__'):

   339             y.__setstate__(state)

   340         else:

   341             if isinstance(state, tuple) and len(state) == 2:

   342                 state, slotstate = state

   343             else:

   344                 slotstate = None

   345             if state is not None:

   346                 y.__dict__.update(state)

   347             if slotstate is not None:

   348                 for key, value in slotstate.iteritems():

   349                     setattr(y, key, value)

   350     return y

   351 

   352 del d

   353 

   354 del types

   355 

   356 # Helper for instance creation without calling __init__

   357 class _EmptyClass:

   358     pass

   359 

   360 def _test():

   361     l = [None, 1, 2L, 3.14, 'xyzzy', (1, 2L), [3.14, 'abc'],

   362          {'abc': 'ABC'}, (), [], {}]

   363     l1 = copy(l)

   364     print l1==l

   365     l1 = map(copy, l)

   366     print l1==l

   367     l1 = deepcopy(l)

   368     print l1==l

   369     class C:

   370         def __init__(self, arg=None):

   371             self.a = 1

   372             self.arg = arg

   373             if __name__ == '__main__':

   374                 import sys

   375                 file = sys.argv[0]

   376             else:

   377                 file = __file__

   378             self.fp = open(file)

   379             self.fp.close()

   380         def __getstate__(self):

   381             return {'a': self.a, 'arg': self.arg}

   382         def __setstate__(self, state):

   383             for key, value in state.iteritems():

   384                 setattr(self, key, value)

   385         def __deepcopy__(self, memo=None):

   386             new = self.__class__(deepcopy(self.arg, memo))

   387             new.a = self.a

   388             return new

   389     c = C('argument sketch')

   390     l.append(c)

   391     l2 = copy(l)

   392     print l == l2

   393     print l

   394     print l2

   395     l2 = deepcopy(l)

   396     print l == l2

   397     print l

   398     print l2

   399     l.append({l[1]: l, 'xyz': l[2]})

   400     l3 = copy(l)

   401     import repr

   402     print map(repr.repr, l)

   403     print map(repr.repr, l1)

   404     print map(repr.repr, l2)

   405     print map(repr.repr, l3)

   406     l3 = deepcopy(l)

   407     import repr

   408     print map(repr.repr, l)

   409     print map(repr.repr, l1)

   410     print map(repr.repr, l2)

   411     print map(repr.repr, l3)

   412 

   413 if __name__ == '__main__':

   414     _test()