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