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