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