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