Lib/copy.py

   1 """\
   2 Generic (shallow and deep) copying operations
   3 =============================================
   4
   5 Interface summary:
   6
   7         import copy
   8
   9         x = copy.copy(y)        # make a shallow copy of y
  10         x = copy.deepcopy(y)    # make a deep copy of y
  11
  12 For module specific errors, copy.error is raised.
  13
  14 The difference between shallow and deep copying is only relevant for
  15 compound objects (objects that contain other objects, like lists or
  16 class instances).
  17
  18 - A shallow copy constructs a new compound object and then (to the
  19   extent possible) inserts *the same objects* into in that the
  20   original contains.
  21
  22 - A deep copy constructs a new compound object and then, recursively,
  23   inserts *copies* into it of the objects found in the original.
  24
  25 Two problems often exist with deep copy operations that don't exist
  26 with shallow copy operations:
  27
  28  a) recursive objects (compound objects that, directly or indirectly,
  29     contain a reference to themselves) may cause a recursive loop
  30
  31  b) because deep copy copies *everything* it may copy too much, e.g.
  32     administrative data structures that should be shared even between
  33     copies
  34
  35 Python's deep copy operation avoids these problems by:
  36
  37  a) keeping a table of objects already copied during the current
  38     copying pass
  39
  40  b) letting user-defined classes override the copying operation or the
  41     set of components copied
  42
  43 This version does not copy types like module, class, function, method,
  44 nor stack trace, stack frame, nor file, socket, window, nor array, nor
  45 any similar types.
  46
  47 Classes can use the same interfaces to control copying that they use
  48 to control pickling: they can define methods called __getinitargs__(),
  49 __getstate__() and __setstate__().  See the documentation for module
  50 "pickle" for information on these methods.
  51 """
  52
  53 # XXX need to support copy_reg here too...
  54
  55 import types
  56
  57 error = 'copy.error'
  58 Error = error # backward compatibility
  59
  60 def copy(x):
  61         """Shallow copy operation on arbitrary Python objects.
  62
  63         See the module's __doc__ string for more info.
  64         """
  65
  66         try:
  67                 copierfunction = _copy_dispatch[type(x)]
  68         except KeyError:
  69                 try:
  70                         copier = x.__copy__
  71                 except AttributeError:
  72                         raise error, \
  73                               "un(shallow)copyable object of type %s" % type(x)
  74                 y = copier()
  75         else:
  76                 y = copierfunction(x)
  77         return y
  78
  79 _copy_dispatch = d = {}
  80
  81 def _copy_atomic(x):
  82         return x
  83 d[types.NoneType] = _copy_atomic
  84 d[types.IntType] = _copy_atomic
  85 d[types.LongType] = _copy_atomic
  86 d[types.FloatType] = _copy_atomic
  87 d[types.StringType] = _copy_atomic
  88 d[types.CodeType] = _copy_atomic
  89 d[types.TypeType] = _copy_atomic
  90 d[types.XRangeType] = _copy_atomic
  91 d[types.ClassType] = _copy_atomic
  92
  93 def _copy_list(x):
  94         return x[:]
  95 d[types.ListType] = _copy_list
  96
  97 def _copy_tuple(x):
  98         return x[:]
  99 d[types.TupleType] = _copy_tuple
 100
 101 def _copy_dict(x):
 102         return x.copy()
 103 d[types.DictionaryType] = _copy_dict
 104
 105 def _copy_inst(x):
 106         if hasattr(x, '__copy__'):
 107                 return x.__copy__()
 108         if hasattr(x, '__getinitargs__'):
 109                 args = x.__getinitargs__()
 110                 y = apply(x.__class__, args)
 111         else:
 112                 y = _EmptyClass()
 113                 y.__class__ = x.__class__
 114         if hasattr(x, '__getstate__'):
 115                 state = x.__getstate__()
 116         else:
 117                 state = x.__dict__
 118         if hasattr(y, '__setstate__'):
 119                 y.__setstate__(state)
 120         else:
 121                 y.__dict__.update(state)
 122         return y
 123 d[types.InstanceType] = _copy_inst
 124
 125 del d
 126
 127 def deepcopy(x, memo = None):
 128         """Deep copy operation on arbitrary Python objects.
 129
 130         See the module's __doc__ string for more info.
 131         """
 132
 133         if memo is None:
 134                 memo = {}
 135         d = id(x)
 136         if memo.has_key(d):
 137                 return memo[d]
 138         try:
 139                 copierfunction = _deepcopy_dispatch[type(x)]
 140         except KeyError:
 141                 try:
 142                         copier = x.__deepcopy__
 143                 except AttributeError:
 144                         raise error, \
 145                               "un-deep-copyable object of type %s" % type(x)
 146                 y = copier(memo)
 147         else:
 148                 y = copierfunction(x, memo)
 149         memo[d] = y
 150         return y
 151
 152 _deepcopy_dispatch = d = {}
 153
 154 def _deepcopy_atomic(x, memo):
 155         return x
 156 d[types.NoneType] = _deepcopy_atomic
 157 d[types.IntType] = _deepcopy_atomic
 158 d[types.LongType] = _deepcopy_atomic
 159 d[types.FloatType] = _deepcopy_atomic
 160 d[types.StringType] = _deepcopy_atomic
 161 d[types.CodeType] = _deepcopy_atomic
 162 d[types.TypeType] = _deepcopy_atomic
 163 d[types.XRangeType] = _deepcopy_atomic
 164
 165 def _deepcopy_list(x, memo):
 166         y = []
 167         memo[id(x)] = y
 168         for a in x:
 169                 y.append(deepcopy(a, memo))
 170         return y
 171 d[types.ListType] = _deepcopy_list
 172
 173 def _deepcopy_tuple(x, memo):
 174         y = []
 175         for a in x:
 176                 y.append(deepcopy(a, memo))
 177         d = id(x)
 178         try:
 179                 return memo[d]
 180         except KeyError:
 181                 pass
 182         for i in range(len(x)):
 183                 if x[i] is not y[i]:
 184                         y = tuple(y)
 185                         break
 186         else:
 187                 y = x
 188         memo[d] = y
 189         return y
 190 d[types.TupleType] = _deepcopy_tuple
 191
 192 def _deepcopy_dict(x, memo):
 193         y = {}
 194         memo[id(x)] = y
 195         for key in x.keys():
 196                 y[deepcopy(key, memo)] = deepcopy(x[key], memo)
 197         return y
 198 d[types.DictionaryType] = _deepcopy_dict
 199
 200 def _keep_alive(x, memo):
 201         """Keeps a reference to the object x in the memo.
 202
 203         Because we remember objects by their id, we have
 204         to assure that possibly temporary objects are kept
 205         alive by referencing them.
 206         We store a reference at the id of the memo, which should
 207         normally not be used unless someone tries to deepcopy
 208         the memo itself...
 209         """
 210         try:
 211                 memo[id(memo)].append(x)
 212         except KeyError:
 213                 # aha, this is the first one :-)
 214                 memo[id(memo)]=[x]
 215
 216 def _deepcopy_inst(x, memo):
 217         if hasattr(x, '__deepcopy__'):
 218                 return x.__deepcopy__(memo)
 219         if hasattr(x, '__getinitargs__'):
 220                 args = x.__getinitargs__()
 221                 _keep_alive(args, memo)
 222                 args = deepcopy(args, memo)
 223                 y = apply(x.__class__, args)
 224         else:
 225                 y = _EmptyClass()
 226                 y.__class__ = x.__class__
 227         memo[id(x)] = y
 228         if hasattr(x, '__getstate__'):
 229                 state = x.__getstate__()
 230                 _keep_alive(state, memo)
 231         else:
 232                 state = x.__dict__
 233         state = deepcopy(state, memo)
 234         if hasattr(y, '__setstate__'):
 235                 y.__setstate__(state)
 236         else:
 237                 y.__dict__.update(state)
 238         return y
 239 d[types.InstanceType] = _deepcopy_inst
 240
 241 del d
 242
 243 del types
 244
 245 # Helper for instance creation without calling __init__
 246 class _EmptyClass:
 247     pass
 248
 249 def _test():
 250         l = [None, 1, 2L, 3.14, 'xyzzy', (1, 2L), [3.14, 'abc'],
 251              {'abc': 'ABC'}, (), [], {}]
 252         l1 = copy(l)
 253         print l1==l
 254         l1 = map(copy, l)
 255         print l1==l
 256         l1 = deepcopy(l)
 257         print l1==l
 258         class C:
 259                 def __init__(self, arg=None):
 260                         self.a = 1
 261                         self.arg = arg
 262                         if __name__ == '__main__':
 263                                 import sys
 264                                 file = sys.argv[0]
 265                         else:
 266                                 file = __file__
 267                         self.fp = open(file)
 268                         self.fp.close()
 269                 def __getstate__(self):
 270                         return {'a': self.a, 'arg': self.arg}
 271                 def __setstate__(self, state):
 272                         for key in state.keys():
 273                                 setattr(self, key, state[key])
 274                 def __deepcopy__(self, memo = None):
 275                         new = self.__class__(deepcopy(self.arg, memo))
 276                         new.a = self.a
 277                         return new
 278         c = C('argument sketch')
 279         l.append(c)
 280         l2 = copy(l)
 281         print l == l2
 282         print l
 283         print l2
 284         l2 = deepcopy(l)
 285         print l == l2
 286         print l
 287         print l2
 288         l.append({l[1]: l, 'xyz': l[2]})
 289         l3 = copy(l)
 290         import repr
 291         print map(repr.repr, l)
 292         print map(repr.repr, l1)
 293         print map(repr.repr, l2)
 294         print map(repr.repr, l3)
 295         l3 = deepcopy(l)
 296         import repr
 297         print map(repr.repr, l)
 298         print map(repr.repr, l1)
 299         print map(repr.repr, l2)
 300         print map(repr.repr, l3)
 301
 302 if __name__ == '__main__':
 303         _test()