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