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 # XXX need to support copy_reg here too...
  52
  53 import types
  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", "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     try:
  73         copierfunction = _copy_dispatch[type(x)]
  74     except KeyError:
  75         try:
  76             copier = x.__copy__
  77         except AttributeError:
  78             try:
  79                 reductor = x.__reduce__
  80             except AttributeError:
  81                 raise error, \
  82                       "un(shallow)copyable object of type %s" % type(x)
  83             else:
  84                 y = _reconstruct(x, reductor(), 0)
  85         else:
  86             y = copier()
  87     else:
  88         y = copierfunction(x)
  89     return y
  90
  91 _copy_dispatch = d = {}
  92
  93 def _copy_atomic(x):
  94     return x
  95 d[types.NoneType] = _copy_atomic
  96 d[types.IntType] = _copy_atomic
  97 d[types.LongType] = _copy_atomic
  98 d[types.FloatType] = _copy_atomic
  99 try:
 100     d[types.ComplexType] = _copy_atomic
 101 except AttributeError:
 102     pass
 103 d[types.StringType] = _copy_atomic
 104 try:
 105     d[types.UnicodeType] = _copy_atomic
 106 except AttributeError:
 107     pass
 108 try:
 109     d[types.CodeType] = _copy_atomic
 110 except AttributeError:
 111     pass
 112 d[types.TypeType] = _copy_atomic
 113 d[types.XRangeType] = _copy_atomic
 114 d[types.ClassType] = _copy_atomic
 115
 116 def _copy_list(x):
 117     return x[:]
 118 d[types.ListType] = _copy_list
 119
 120 def _copy_tuple(x):
 121     return x[:]
 122 d[types.TupleType] = _copy_tuple
 123
 124 def _copy_dict(x):
 125     return x.copy()
 126 d[types.DictionaryType] = _copy_dict
 127 if PyStringMap is not None:
 128     d[PyStringMap] = _copy_dict
 129
 130 def _copy_inst(x):
 131     if hasattr(x, '__copy__'):
 132         return x.__copy__()
 133     if hasattr(x, '__getinitargs__'):
 134         args = x.__getinitargs__()
 135         y = apply(x.__class__, args)
 136     else:
 137         y = _EmptyClass()
 138         y.__class__ = x.__class__
 139     if hasattr(x, '__getstate__'):
 140         state = x.__getstate__()
 141     else:
 142         state = x.__dict__
 143     if hasattr(y, '__setstate__'):
 144         y.__setstate__(state)
 145     else:
 146         y.__dict__.update(state)
 147     return y
 148 d[types.InstanceType] = _copy_inst
 149
 150 del d
 151
 152 def deepcopy(x, memo = None):
 153     """Deep copy operation on arbitrary Python objects.
 154
 155     See the module's __doc__ string for more info.
 156     """
 157
 158     if memo is None:
 159         memo = {}
 160     d = id(x)
 161     if d in memo:
 162         return memo[d]
 163     try:
 164         copierfunction = _deepcopy_dispatch[type(x)]
 165     except KeyError:
 166         try:
 167             issc = issubclass(type(x), type)
 168         except TypeError:
 169             issc = 0
 170         if issc:
 171             y = _deepcopy_dispatch[type](x, memo)
 172         else:
 173             try:
 174                 copier = x.__deepcopy__
 175             except AttributeError:
 176                 try:
 177                     reductor = x.__reduce__
 178                 except AttributeError:
 179                     raise error, \
 180                        "un-deep-copyable object of type %s" % type(x)
 181                 else:
 182                     y = _reconstruct(x, reductor(), 1, memo)
 183             else:
 184                 y = copier(memo)
 185     else:
 186         y = copierfunction(x, memo)
 187     memo[d] = y
 188     _keep_alive(x, memo) # Make sure x lives at least as long as d
 189     return y
 190
 191 _deepcopy_dispatch = d = {}
 192
 193 def _deepcopy_atomic(x, memo):
 194     return x
 195 d[types.NoneType] = _deepcopy_atomic
 196 d[types.IntType] = _deepcopy_atomic
 197 d[types.LongType] = _deepcopy_atomic
 198 d[types.FloatType] = _deepcopy_atomic
 199 try:
 200     d[types.ComplexType] = _deepcopy_atomic
 201 except AttributeError:
 202     pass
 203 d[types.StringType] = _deepcopy_atomic
 204 try:
 205     d[types.UnicodeType] = _deepcopy_atomic
 206 except AttributeError:
 207     pass
 208 try:
 209     d[types.CodeType] = _deepcopy_atomic
 210 except AttributeError:
 211     pass
 212 d[types.TypeType] = _deepcopy_atomic
 213 d[types.XRangeType] = _deepcopy_atomic
 214
 215 def _deepcopy_list(x, memo):
 216     y = []
 217     memo[id(x)] = y
 218     for a in x:
 219         y.append(deepcopy(a, memo))
 220     return y
 221 d[types.ListType] = _deepcopy_list
 222
 223 def _deepcopy_tuple(x, memo):
 224     y = []
 225     for a in x:
 226         y.append(deepcopy(a, memo))
 227     d = id(x)
 228     try:
 229         return memo[d]
 230     except KeyError:
 231         pass
 232     for i in range(len(x)):
 233         if x[i] is not y[i]:
 234             y = tuple(y)
 235             break
 236     else:
 237         y = x
 238     memo[d] = y
 239     return y
 240 d[types.TupleType] = _deepcopy_tuple
 241
 242 def _deepcopy_dict(x, memo):
 243     y = {}
 244     memo[id(x)] = y
 245     for key, value in x.iteritems():
 246         y[deepcopy(key, memo)] = deepcopy(value, memo)
 247     return y
 248 d[types.DictionaryType] = _deepcopy_dict
 249 if PyStringMap is not None:
 250     d[PyStringMap] = _deepcopy_dict
 251
 252 def _keep_alive(x, memo):
 253     """Keeps a reference to the object x in the memo.
 254
 255     Because we remember objects by their id, we have
 256     to assure that possibly temporary objects are kept
 257     alive by referencing them.
 258     We store a reference at the id of the memo, which should
 259     normally not be used unless someone tries to deepcopy
 260     the memo itself...
 261     """
 262     try:
 263         memo[id(memo)].append(x)
 264     except KeyError:
 265         # aha, this is the first one :-)
 266         memo[id(memo)]=[x]
 267
 268 def _deepcopy_inst(x, memo):
 269     if hasattr(x, '__deepcopy__'):
 270         return x.__deepcopy__(memo)
 271     if hasattr(x, '__getinitargs__'):
 272         args = x.__getinitargs__()
 273         args = deepcopy(args, memo)
 274         y = apply(x.__class__, args)
 275     else:
 276         y = _EmptyClass()
 277         y.__class__ = x.__class__
 278     memo[id(x)] = y
 279     if hasattr(x, '__getstate__'):
 280         state = x.__getstate__()
 281     else:
 282         state = x.__dict__
 283     state = deepcopy(state, memo)
 284     if hasattr(y, '__setstate__'):
 285         y.__setstate__(state)
 286     else:
 287         y.__dict__.update(state)
 288     return y
 289 d[types.InstanceType] = _deepcopy_inst
 290
 291 def _reconstruct(x, info, deep, memo=None):
 292     if isinstance(info, str):
 293         return x
 294     assert isinstance(info, tuple)
 295     if memo is None:
 296         memo = {}
 297     n = len(info)
 298     assert n in (2, 3)
 299     callable, args = info[:2]
 300     if n > 2:
 301         state = info[2]
 302     else:
 303         state = {}
 304     if deep:
 305         args = deepcopy(args, memo)
 306     y = callable(*args)
 307     if state:
 308         if deep:
 309             state = deepcopy(state, memo)
 310         if hasattr(y, '__setstate__'):
 311             y.__setstate__(state)
 312         else:
 313             y.__dict__.update(state)
 314     return y
 315
 316 del d
 317
 318 del types
 319
 320 # Helper for instance creation without calling __init__
 321 class _EmptyClass:
 322     pass
 323
 324 def _test():
 325     l = [None, 1, 2L, 3.14, 'xyzzy', (1, 2L), [3.14, 'abc'],
 326          {'abc': 'ABC'}, (), [], {}]
 327     l1 = copy(l)
 328     print l1==l
 329     l1 = map(copy, l)
 330     print l1==l
 331     l1 = deepcopy(l)
 332     print l1==l
 333     class C:
 334         def __init__(self, arg=None):
 335             self.a = 1
 336             self.arg = arg
 337             if __name__ == '__main__':
 338                 import sys
 339                 file = sys.argv[0]
 340             else:
 341                 file = __file__
 342             self.fp = open(file)
 343             self.fp.close()
 344         def __getstate__(self):
 345             return {'a': self.a, 'arg': self.arg}
 346         def __setstate__(self, state):
 347             for key, value in state.iteritems():
 348                 setattr(self, key, value)
 349         def __deepcopy__(self, memo = None):
 350             new = self.__class__(deepcopy(self.arg, memo))
 351             new.a = self.a
 352             return new
 353     c = C('argument sketch')
 354     l.append(c)
 355     l2 = copy(l)
 356     print l == l2
 357     print l
 358     print l2
 359     l2 = deepcopy(l)
 360     print l == l2
 361     print l
 362     print l2
 363     l.append({l[1]: l, 'xyz': l[2]})
 364     l3 = copy(l)
 365     import repr
 366     print map(repr.repr, l)
 367     print map(repr.repr, l1)
 368     print map(repr.repr, l2)
 369     print map(repr.repr, l3)
 370     l3 = deepcopy(l)
 371     import repr
 372     print map(repr.repr, l)
 373     print map(repr.repr, l1)
 374     print map(repr.repr, l2)
 375     print map(repr.repr, l3)
 376
 377 if __name__ == '__main__':
 378     _test()