bin/tools/copy.py

   1 """
   2 FROM Python 2.5
   3 Generic (shallow and deep) copying operations.
   4
   5 Interface summary:
   6
   7         import copy
   8
   9         x = copy.copy(y)        # make a shallow copy of y
  10         x = copy.deepcopy(y)    # make a deep copy of y
  11
  12 For module specific errors, copy.Error is raised.
  13
  14 The difference between shallow and deep copying is only relevant for
  15 compound objects (objects that contain other objects, like lists or
  16 class instances).
  17
  18 - A shallow copy constructs a new compound object and then (to the
  19   extent possible) inserts *the same objects* into it that the
  20   original contains.
  21
  22 - A deep copy constructs a new compound object and then, recursively,
  23   inserts *copies* into it of the objects found in the original.
  24
  25 Two problems often exist with deep copy operations that don't exist
  26 with shallow copy operations:
  27
  28  a) recursive objects (compound objects that, directly or indirectly,
  29     contain a reference to themselves) may cause a recursive loop
  30
  31  b) because deep copy copies *everything* it may copy too much, e.g.
  32     administrative data structures that should be shared even between
  33     copies
  34
  35 Python's deep copy operation avoids these problems by:
  36
  37  a) keeping a table of objects already copied during the current
  38     copying pass
  39
  40  b) letting user-defined classes override the copying operation or the
  41     set of components copied
  42
  43 This version does not copy types like module, class, function, method,
  44 nor stack trace, stack frame, nor file, socket, window, nor array, nor
  45 any similar types.
  46
  47 Classes can use the same interfaces to control copying that they use
  48 to control pickling: they can define methods called __getinitargs__(),
  49 __getstate__() and __setstate__().  See the documentation for module
  50 "pickle" for information on these methods.
  51 """
  52
  53 import types
  54 from copy_reg import dispatch_table
  55
  56 class Error(Exception):
  57     pass
  58 error = Error   # backward compatibility
  59
  60 try:
  61     from org.python.core import PyStringMap
  62 except ImportError:
  63     PyStringMap = None
  64
  65 __all__ = ["Error", "copy", "deepcopy"]
  66
  67 def copy(x):
  68     """Shallow copy operation on arbitrary Python objects.
  69
  70     See the module's __doc__ string for more info.
  71     """
  72
  73     cls = type(x)
  74
  75     copier = _copy_dispatch.get(cls)
  76     if copier:
  77         return copier(x)
  78
  79     copier = getattr(cls, "__copy__", None)
  80     if copier:
  81         return copier(x)
  82
  83     reductor = dispatch_table.get(cls)
  84     if reductor:
  85         rv = reductor(x)
  86     else:
  87         reductor = getattr(x, "__reduce_ex__", None)
  88         if reductor:
  89             rv = reductor(2)
  90         else:
  91             reductor = getattr(x, "__reduce__", None)
  92             if reductor:
  93                 rv = reductor()
  94             else:
  95                 raise Error("un(shallow)copyable object of type %s" % cls)
  96
  97     return _reconstruct(x, rv, 0)
  98
  99
 100 _copy_dispatch = d = {}
 101
 102 def _copy_immutable(x):
 103     return x
 104 for t in (type(None), int, long, float, bool, str, tuple,
 105           frozenset, type, xrange, types.ClassType,
 106           types.BuiltinFunctionType,
 107           types.FunctionType):
 108     d[t] = _copy_immutable
 109 for name in ("ComplexType", "UnicodeType", "CodeType"):
 110     t = getattr(types, name, None)
 111     if t is not None:
 112         d[t] = _copy_immutable
 113
 114 def _copy_with_constructor(x):
 115     return type(x)(x)
 116 for t in (list, dict, set):
 117     d[t] = _copy_with_constructor
 118
 119 def _copy_with_copy_method(x):
 120     return x.copy()
 121 if PyStringMap is not None:
 122     d[PyStringMap] = _copy_with_copy_method
 123
 124 def _copy_inst(x):
 125     if hasattr(x, '__copy__'):
 126         return x.__copy__()
 127     if hasattr(x, '__getinitargs__'):
 128         args = x.__getinitargs__()
 129         y = x.__class__(*args)
 130     else:
 131         y = _EmptyClass()
 132         y.__class__ = x.__class__
 133     if hasattr(x, '__getstate__'):
 134         state = x.__getstate__()
 135     else:
 136         state = x.__dict__
 137     if hasattr(y, '__setstate__'):
 138         y.__setstate__(state)
 139     else:
 140         y.__dict__.update(state)
 141     return y
 142 d[types.InstanceType] = _copy_inst
 143
 144 del d
 145
 146 def deepcopy(x, memo=None, _nil=[]):
 147     """Deep copy operation on arbitrary Python objects.
 148
 149     See the module's __doc__ string for more info.
 150     """
 151
 152     if memo is None:
 153         memo = {}
 154
 155     d = id(x)
 156     y = memo.get(d, _nil)
 157     if y is not _nil:
 158         return y
 159
 160     cls = type(x)
 161
 162     copier = _deepcopy_dispatch.get(cls)
 163     if copier:
 164         y = copier(x, memo)
 165     else:
 166         try:
 167             issc = issubclass(cls, type)
 168         except TypeError: # cls is not a class (old Boost; see SF #502085)
 169             issc = 0
 170         if issc:
 171             y = _deepcopy_atomic(x, memo)
 172         else:
 173             copier = getattr(x, "__deepcopy__", None)
 174             if copier:
 175                 y = copier(memo)
 176             else:
 177                 reductor = dispatch_table.get(cls)
 178                 if reductor:
 179                     rv = reductor(x)
 180                 else:
 181                     reductor = getattr(x, "__reduce_ex__", None)
 182                     if reductor:
 183                         rv = reductor(2)
 184                     else:
 185                         reductor = getattr(x, "__reduce__", None)
 186                         if reductor:
 187                             rv = reductor()
 188                         else:
 189                             raise Error(
 190                                 "un(deep)copyable object of type %s" % cls)
 191                 y = _reconstruct(x, rv, 1, memo)
 192
 193     memo[d] = y
 194     _keep_alive(x, memo) # Make sure x lives at least as long as d
 195     return y
 196
 197 _deepcopy_dispatch = d = {}
 198
 199 def _deepcopy_atomic(x, memo):
 200     return x
 201 d[type(None)] = _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
 225 def _deepcopy_list(x, memo):
 226     y = []
 227     memo[id(x)] = y
 228     for a in x:
 229         y.append(deepcopy(a, memo))
 230     return y
 231 d[list] = _deepcopy_list
 232
 233 def _deepcopy_tuple(x, memo):
 234     y = []
 235     for a in x:
 236         y.append(deepcopy(a, memo))
 237     d = id(x)
 238     try:
 239         return memo[d]
 240     except KeyError:
 241         pass
 242     for i in range(len(x)):
 243         if x[i] is not y[i]:
 244             y = tuple(y)
 245             break
 246     else:
 247         y = x
 248     memo[d] = y
 249     return y
 250 d[tuple] = _deepcopy_tuple
 251
 252 def _deepcopy_dict(x, memo):
 253     y = {}
 254     memo[id(x)] = y
 255     for key, value in x.iteritems():
 256         y[deepcopy(key, memo)] = deepcopy(value, memo)
 257     return y
 258 d[dict] = _deepcopy_dict
 259 if PyStringMap is not None:
 260     d[PyStringMap] = _deepcopy_dict
 261
 262 def _keep_alive(x, memo):
 263     """Keeps a reference to the object x in the memo.
 264
 265     Because we remember objects by their id, we have
 266     to assure that possibly temporary objects are kept
 267     alive by referencing them.
 268     We store a reference at the id of the memo, which should
 269     normally not be used unless someone tries to deepcopy
 270     the memo itself...
 271     """
 272     try:
 273         memo[id(memo)].append(x)
 274     except KeyError:
 275         # aha, this is the first one :-)
 276         memo[id(memo)]=[x]
 277
 278 def _deepcopy_inst(x, memo):
 279     if hasattr(x, '__deepcopy__'):
 280         return x.__deepcopy__(memo)
 281     if hasattr(x, '__getinitargs__'):
 282         args = x.__getinitargs__()
 283         args = deepcopy(args, memo)
 284         y = x.__class__(*args)
 285     else:
 286         y = _EmptyClass()
 287         y.__class__ = x.__class__
 288     memo[id(x)] = y
 289     if hasattr(x, '__getstate__'):
 290         state = x.__getstate__()
 291     else:
 292         state = x.__dict__
 293     state = deepcopy(state, memo)
 294     if hasattr(y, '__setstate__'):
 295         y.__setstate__(state)
 296     else:
 297         y.__dict__.update(state)
 298     return y
 299 d[types.InstanceType] = _deepcopy_inst
 300
 301 def _reconstruct(x, info, deep, memo=None):
 302     if isinstance(info, str):
 303         return x
 304     assert isinstance(info, tuple)
 305     if memo is None:
 306         memo = {}
 307     n = len(info)
 308     assert n in (2, 3, 4, 5)
 309     callable, args = info[:2]
 310     if n > 2:
 311         state = info[2]
 312     else:
 313         state = {}
 314     if n > 3:
 315         listiter = info[3]
 316     else:
 317         listiter = None
 318     if n > 4:
 319         dictiter = info[4]
 320     else:
 321         dictiter = None
 322     if deep:
 323         args = deepcopy(args, memo)
 324     y = callable(*args)
 325     memo[id(x)] = y
 326     if listiter is not None:
 327         for item in listiter:
 328             if deep:
 329                 item = deepcopy(item, memo)
 330             y.append(item)
 331     if dictiter is not None:
 332         for key, value in dictiter:
 333             if deep:
 334                 key = deepcopy(key, memo)
 335                 value = deepcopy(value, memo)
 336             y[key] = value
 337     if state:
 338         if deep:
 339             state = deepcopy(state, memo)
 340         if hasattr(y, '__setstate__'):
 341             y.__setstate__(state)
 342         else:
 343             if isinstance(state, tuple) and len(state) == 2:
 344                 state, slotstate = state
 345             else:
 346                 slotstate = None
 347             if state is not None:
 348                 y.__dict__.update(state)
 349             if slotstate is not None:
 350                 for key, value in slotstate.iteritems():
 351                     setattr(y, key, value)
 352     return y
 353
 354 del d
 355
 356 del types
 357
 358 # Helper for instance creation without calling __init__
 359 class _EmptyClass:
 360     pass
 361
 362 def _test():
 363     l = [None, 1, 2L, 3.14, 'xyzzy', (1, 2L), [3.14, 'abc'],
 364          {'abc': 'ABC'}, (), [], {}]
 365     l1 = copy(l)
 366     print l1==l
 367     l1 = map(copy, l)
 368     print l1==l
 369     l1 = deepcopy(l)
 370     print l1==l
 371     class C:
 372         def __init__(self, arg=None):
 373             self.a = 1
 374             self.arg = arg
 375             if __name__ == '__main__':
 376                 import sys
 377                 file = sys.argv[0]
 378             else:
 379                 file = __file__
 380             self.fp = open(file)
 381             self.fp.close()
 382         def __getstate__(self):
 383             return {'a': self.a, 'arg': self.arg}
 384         def __setstate__(self, state):
 385             for key, value in state.iteritems():
 386                 setattr(self, key, value)
 387         def __deepcopy__(self, memo=None):
 388             new = self.__class__(deepcopy(self.arg, memo))
 389             new.a = self.a
 390             return new
 391     c = C('argument sketch')
 392     l.append(c)
 393     l2 = copy(l)
 394     print l == l2
 395     print l
 396     print l2
 397     l2 = deepcopy(l)
 398     print l == l2
 399     print l
 400     print l2
 401     l.append({l[1]: l, 'xyz': l[2]})
 402     l3 = copy(l)
 403     import repr
 404     print map(repr.repr, l)
 405     print map(repr.repr, l1)
 406     print map(repr.repr, l2)
 407     print map(repr.repr, l3)
 408     l3 = deepcopy(l)
 409     import repr
 410     print map(repr.repr, l)
 411     print map(repr.repr, l1)
 412     print map(repr.repr, l2)
 413     print map(repr.repr, l3)
 414
 415 if __name__ == '__main__':
 416     _test()