Lib/copy.py

   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 in 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_atomic(x):
 101     return x
 102 d[types.NoneType] = _copy_atomic
 103 d[types.IntType] = _copy_atomic
 104 d[types.LongType] = _copy_atomic
 105 d[types.FloatType] = _copy_atomic
 106 d[types.BooleanType] = _copy_atomic
 107 try:
 108     d[types.ComplexType] = _copy_atomic
 109 except AttributeError:
 110     pass
 111 d[types.StringType] = _copy_atomic
 112 try:
 113     d[types.UnicodeType] = _copy_atomic
 114 except AttributeError:
 115     pass
 116 try:
 117     d[types.CodeType] = _copy_atomic
 118 except AttributeError:
 119     pass
 120 d[types.TypeType] = _copy_atomic
 121 d[types.XRangeType] = _copy_atomic
 122 d[types.ClassType] = _copy_atomic
 123 d[types.BuiltinFunctionType] = _copy_atomic
 124
 125 def _copy_list(x):
 126     return x[:]
 127 d[types.ListType] = _copy_list
 128
 129 def _copy_tuple(x):
 130     return x[:]
 131 d[types.TupleType] = _copy_tuple
 132
 133 def _copy_dict(x):
 134     return x.copy()
 135 d[types.DictionaryType] = _copy_dict
 136 if PyStringMap is not None:
 137     d[PyStringMap] = _copy_dict
 138
 139 def _copy_inst(x):
 140     if hasattr(x, '__copy__'):
 141         return x.__copy__()
 142     if hasattr(x, '__getinitargs__'):
 143         args = x.__getinitargs__()
 144         y = x.__class__(*args)
 145     else:
 146         y = _EmptyClass()
 147         y.__class__ = x.__class__
 148     if hasattr(x, '__getstate__'):
 149         state = x.__getstate__()
 150     else:
 151         state = x.__dict__
 152     if hasattr(y, '__setstate__'):
 153         y.__setstate__(state)
 154     else:
 155         y.__dict__.update(state)
 156     return y
 157 d[types.InstanceType] = _copy_inst
 158
 159 del d
 160
 161 def deepcopy(x, memo=None, _nil=[]):
 162     """Deep copy operation on arbitrary Python objects.
 163
 164     See the module's __doc__ string for more info.
 165     """
 166
 167     if memo is None:
 168         memo = {}
 169
 170     d = id(x)
 171     y = memo.get(d, _nil)
 172     if y is not _nil:
 173         return y
 174
 175     cls = type(x)
 176
 177     copier = _deepcopy_dispatch.get(cls)
 178     if copier:
 179         y = copier(x, memo)
 180     else:
 181         try:
 182             issc = issubclass(cls, type)
 183         except TypeError: # cls is not a class (old Boost; see SF #502085)
 184             issc = 0
 185         if issc:
 186             y = _deepcopy_atomic(x, memo)
 187         else:
 188             copier = getattr(x, "__deepcopy__", None)
 189             if copier:
 190                 y = copier(memo)
 191             else:
 192                 reductor = dispatch_table.get(cls)
 193                 if reductor:
 194                     rv = reductor(x)
 195                 else:
 196                     reductor = getattr(x, "__reduce_ex__", None)
 197                     if reductor:
 198                         rv = reductor(2)
 199                     else:
 200                         reductor = getattr(x, "__reduce__", None)
 201                         if reductor:
 202                             rv = reductor()
 203                         else:
 204                             raise Error(
 205                                 "un(deep)copyable object of type %s" % cls)
 206                 y = _reconstruct(x, rv, 1, memo)
 207
 208     memo[d] = y
 209     _keep_alive(x, memo) # Make sure x lives at least as long as d
 210     return y
 211
 212 _deepcopy_dispatch = d = {}
 213
 214 def _deepcopy_atomic(x, memo):
 215     return x
 216 d[types.NoneType] = _deepcopy_atomic
 217 d[types.IntType] = _deepcopy_atomic
 218 d[types.LongType] = _deepcopy_atomic
 219 d[types.FloatType] = _deepcopy_atomic
 220 d[types.BooleanType] = _deepcopy_atomic
 221 try:
 222     d[types.ComplexType] = _deepcopy_atomic
 223 except AttributeError:
 224     pass
 225 d[types.StringType] = _deepcopy_atomic
 226 try:
 227     d[types.UnicodeType] = _deepcopy_atomic
 228 except AttributeError:
 229     pass
 230 try:
 231     d[types.CodeType] = _deepcopy_atomic
 232 except AttributeError:
 233     pass
 234 d[types.TypeType] = _deepcopy_atomic
 235 d[types.XRangeType] = _deepcopy_atomic
 236 d[types.ClassType] = _deepcopy_atomic
 237 d[types.BuiltinFunctionType] = _deepcopy_atomic
 238
 239 def _deepcopy_list(x, memo):
 240     y = []
 241     memo[id(x)] = y
 242     for a in x:
 243         y.append(deepcopy(a, memo))
 244     return y
 245 d[types.ListType] = _deepcopy_list
 246
 247 def _deepcopy_tuple(x, memo):
 248     y = []
 249     for a in x:
 250         y.append(deepcopy(a, memo))
 251     d = id(x)
 252     try:
 253         return memo[d]
 254     except KeyError:
 255         pass
 256     for i in range(len(x)):
 257         if x[i] is not y[i]:
 258             y = tuple(y)
 259             break
 260     else:
 261         y = x
 262     memo[d] = y
 263     return y
 264 d[types.TupleType] = _deepcopy_tuple
 265
 266 def _deepcopy_dict(x, memo):
 267     y = {}
 268     memo[id(x)] = y
 269     for key, value in x.iteritems():
 270         y[deepcopy(key, memo)] = deepcopy(value, memo)
 271     return y
 272 d[types.DictionaryType] = _deepcopy_dict
 273 if PyStringMap is not None:
 274     d[PyStringMap] = _deepcopy_dict
 275
 276 def _keep_alive(x, memo):
 277     """Keeps a reference to the object x in the memo.
 278
 279     Because we remember objects by their id, we have
 280     to assure that possibly temporary objects are kept
 281     alive by referencing them.
 282     We store a reference at the id of the memo, which should
 283     normally not be used unless someone tries to deepcopy
 284     the memo itself...
 285     """
 286     try:
 287         memo[id(memo)].append(x)
 288     except KeyError:
 289         # aha, this is the first one :-)
 290         memo[id(memo)]=[x]
 291
 292 def _deepcopy_inst(x, memo):
 293     if hasattr(x, '__deepcopy__'):
 294         return x.__deepcopy__(memo)
 295     if hasattr(x, '__getinitargs__'):
 296         args = x.__getinitargs__()
 297         args = deepcopy(args, memo)
 298         y = x.__class__(*args)
 299     else:
 300         y = _EmptyClass()
 301         y.__class__ = x.__class__
 302     memo[id(x)] = y
 303     if hasattr(x, '__getstate__'):
 304         state = x.__getstate__()
 305     else:
 306         state = x.__dict__
 307     state = deepcopy(state, memo)
 308     if hasattr(y, '__setstate__'):
 309         y.__setstate__(state)
 310     else:
 311         y.__dict__.update(state)
 312     return y
 313 d[types.InstanceType] = _deepcopy_inst
 314
 315 def _reconstruct(x, info, deep, memo=None):
 316     if isinstance(info, str):
 317         return x
 318     assert isinstance(info, tuple)
 319     if memo is None:
 320         memo = {}
 321     n = len(info)
 322     assert n in (2, 3, 4, 5)
 323     callable, args = info[:2]
 324     if n > 2:
 325         state = info[2]
 326     else:
 327         state = {}
 328     if n > 3:
 329         listiter = info[3]
 330     else:
 331         listiter = None
 332     if n > 4:
 333         dictiter = info[4]
 334     else:
 335         dictiter = None
 336     if deep:
 337         args = deepcopy(args, memo)
 338     y = callable(*args)
 339     memo[id(x)] = y
 340     if listiter is not None:
 341         for item in listiter:
 342             if deep:
 343                 item = deepcopy(item, memo)
 344             y.append(item)
 345     if dictiter is not None:
 346         for key, value in dictiter:
 347             if deep:
 348                 key = deepcopy(key, memo)
 349                 value = deepcopy(value, memo)
 350             y[key] = value
 351     if state:
 352         if deep:
 353             state = deepcopy(state, memo)
 354         if hasattr(y, '__setstate__'):
 355             y.__setstate__(state)
 356         else:
 357             if isinstance(state, tuple) and len(state) == 2:
 358                 state, slotstate = state
 359             else:
 360                 slotstate = None
 361             if state is not None:
 362                 y.__dict__.update(state)
 363             if slotstate is not None:
 364                 for key, value in slotstate.iteritems():
 365                     setattr(y, key, value)
 366     return y
 367
 368 del d
 369
 370 del types
 371
 372 # Helper for instance creation without calling __init__
 373 class _EmptyClass:
 374     pass
 375
 376 def _test():
 377     l = [None, 1, 2L, 3.14, 'xyzzy', (1, 2L), [3.14, 'abc'],
 378          {'abc': 'ABC'}, (), [], {}]
 379     l1 = copy(l)
 380     print l1==l
 381     l1 = map(copy, l)
 382     print l1==l
 383     l1 = deepcopy(l)
 384     print l1==l
 385     class C:
 386         def __init__(self, arg=None):
 387             self.a = 1
 388             self.arg = arg
 389             if __name__ == '__main__':
 390                 import sys
 391                 file = sys.argv[0]
 392             else:
 393                 file = __file__
 394             self.fp = open(file)
 395             self.fp.close()
 396         def __getstate__(self):
 397             return {'a': self.a, 'arg': self.arg}
 398         def __setstate__(self, state):
 399             for key, value in state.iteritems():
 400                 setattr(self, key, value)
 401         def __deepcopy__(self, memo=None):
 402             new = self.__class__(deepcopy(self.arg, memo))
 403             new.a = self.a
 404             return new
 405     c = C('argument sketch')
 406     l.append(c)
 407     l2 = copy(l)
 408     print l == l2
 409     print l
 410     print l2
 411     l2 = deepcopy(l)
 412     print l == l2
 413     print l
 414     print l2
 415     l.append({l[1]: l, 'xyz': l[2]})
 416     l3 = copy(l)
 417     import repr
 418     print map(repr.repr, l)
 419     print map(repr.repr, l1)
 420     print map(repr.repr, l2)
 421     print map(repr.repr, l3)
 422     l3 = deepcopy(l)
 423     import repr
 424     print map(repr.repr, l)
 425     print map(repr.repr, l1)
 426     print map(repr.repr, l2)
 427     print map(repr.repr, l3)
 428
 429 if __name__ == '__main__':
 430     _test()