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