Home | History | Annotate | Download | only in Lib 
      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     try:
     79         issc = issubclass(cls, type)
     80     except TypeError: # cls is not a class
     81         issc = False
     82     if issc:
     83         # treat it as a regular class:
     84         return _copy_immutable(x)
     85 
     86     copier = getattr(cls, "__copy__", None)
     87     if copier:
     88         return copier(x)
     89 
     90     reductor = dispatch_table.get(cls)
     91     if reductor:
     92         rv = reductor(x)
     93     else:
     94         reductor = getattr(x, "__reduce_ex__", None)
     95         if reductor:
     96             rv = reductor(4)
     97         else:
     98             reductor = getattr(x, "__reduce__", None)
     99             if reductor:
    100                 rv = reductor()
    101             else:
    102                 raise Error("un(shallow)copyable object of type %s" % cls)
    103 
    104     if isinstance(rv, str):
    105         return x
    106     return _reconstruct(x, None, *rv)
    107 
    108 
    109 _copy_dispatch = d = {}
    110 
    111 def _copy_immutable(x):
    112     return x
    113 for t in (type(None), int, float, bool, complex, str, tuple,
    114           bytes, frozenset, type, range, slice,
    115           types.BuiltinFunctionType, type(Ellipsis), type(NotImplemented),
    116           types.FunctionType, weakref.ref):
    117     d[t] = _copy_immutable
    118 t = getattr(types, "CodeType", None)
    119 if t is not None:
    120     d[t] = _copy_immutable
    121 
    122 d[list] = list.copy
    123 d[dict] = dict.copy
    124 d[set] = set.copy
    125 d[bytearray] = bytearray.copy
    126 
    127 if PyStringMap is not None:
    128     d[PyStringMap] = PyStringMap.copy
    129 
    130 del d, t
    131 
    132 def deepcopy(x, memo=None, _nil=[]):
    133     """Deep copy operation on arbitrary Python objects.
    134 
    135     See the module's __doc__ string for more info.
    136     """
    137 
    138     if memo is None:
    139         memo = {}
    140 
    141     d = id(x)
    142     y = memo.get(d, _nil)
    143     if y is not _nil:
    144         return y
    145 
    146     cls = type(x)
    147 
    148     copier = _deepcopy_dispatch.get(cls)
    149     if copier:
    150         y = copier(x, memo)
    151     else:
    152         try:
    153             issc = issubclass(cls, type)
    154         except TypeError: # cls is not a class (old Boost; see SF #502085)
    155             issc = 0
    156         if issc:
    157             y = _deepcopy_atomic(x, memo)
    158         else:
    159             copier = getattr(x, "__deepcopy__", None)
    160             if copier:
    161                 y = copier(memo)
    162             else:
    163                 reductor = dispatch_table.get(cls)
    164                 if reductor:
    165                     rv = reductor(x)
    166                 else:
    167                     reductor = getattr(x, "__reduce_ex__", None)
    168                     if reductor:
    169                         rv = reductor(4)
    170                     else:
    171                         reductor = getattr(x, "__reduce__", None)
    172                         if reductor:
    173                             rv = reductor()
    174                         else:
    175                             raise Error(
    176                                 "un(deep)copyable object of type %s" % cls)
    177                 if isinstance(rv, str):
    178                     y = x
    179                 else:
    180                     y = _reconstruct(x, memo, *rv)
    181 
    182     # If is its own copy, don't memoize.
    183     if y is not x:
    184         memo[d] = y
    185         _keep_alive(x, memo) # Make sure x lives at least as long as d
    186     return y
    187 
    188 _deepcopy_dispatch = d = {}
    189 
    190 def _deepcopy_atomic(x, memo):
    191     return x
    192 d[type(None)] = _deepcopy_atomic
    193 d[type(Ellipsis)] = _deepcopy_atomic
    194 d[type(NotImplemented)] = _deepcopy_atomic
    195 d[int] = _deepcopy_atomic
    196 d[float] = _deepcopy_atomic
    197 d[bool] = _deepcopy_atomic
    198 d[complex] = _deepcopy_atomic
    199 d[bytes] = _deepcopy_atomic
    200 d[str] = _deepcopy_atomic
    201 try:
    202     d[types.CodeType] = _deepcopy_atomic
    203 except AttributeError:
    204     pass
    205 d[type] = _deepcopy_atomic
    206 d[types.BuiltinFunctionType] = _deepcopy_atomic
    207 d[types.FunctionType] = _deepcopy_atomic
    208 d[weakref.ref] = _deepcopy_atomic
    209 
    210 def _deepcopy_list(x, memo, deepcopy=deepcopy):
    211     y = []
    212     memo[id(x)] = y
    213     append = y.append
    214     for a in x:
    215         append(deepcopy(a, memo))
    216     return y
    217 d[list] = _deepcopy_list
    218 
    219 def _deepcopy_tuple(x, memo, deepcopy=deepcopy):
    220     y = [deepcopy(a, memo) for a in x]
    221     # We're not going to put the tuple in the memo, but it's still important we
    222     # check for it, in case the tuple contains recursive mutable structures.
    223     try:
    224         return memo[id(x)]
    225     except KeyError:
    226         pass
    227     for k, j in zip(x, y):
    228         if k is not j:
    229             y = tuple(y)
    230             break
    231     else:
    232         y = x
    233     return y
    234 d[tuple] = _deepcopy_tuple
    235 
    236 def _deepcopy_dict(x, memo, deepcopy=deepcopy):
    237     y = {}
    238     memo[id(x)] = y
    239     for key, value in x.items():
    240         y[deepcopy(key, memo)] = deepcopy(value, memo)
    241     return y
    242 d[dict] = _deepcopy_dict
    243 if PyStringMap is not None:
    244     d[PyStringMap] = _deepcopy_dict
    245 
    246 def _deepcopy_method(x, memo): # Copy instance methods
    247     return type(x)(x.__func__, deepcopy(x.__self__, memo))
    248 d[types.MethodType] = _deepcopy_method
    249 
    250 del d
    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 _reconstruct(x, memo, func, args,
    269                  state=None, listiter=None, dictiter=None,
    270                  deepcopy=deepcopy):
    271     deep = memo is not None
    272     if deep and args:
    273         args = (deepcopy(arg, memo) for arg in args)
    274     y = func(*args)
    275     if deep:
    276         memo[id(x)] = y
    277 
    278     if state is not None:
    279         if deep:
    280             state = deepcopy(state, memo)
    281         if hasattr(y, '__setstate__'):
    282             y.__setstate__(state)
    283         else:
    284             if isinstance(state, tuple) and len(state) == 2:
    285                 state, slotstate = state
    286             else:
    287                 slotstate = None
    288             if state is not None:
    289                 y.__dict__.update(state)
    290             if slotstate is not None:
    291                 for key, value in slotstate.items():
    292                     setattr(y, key, value)
    293 
    294     if listiter is not None:
    295         if deep:
    296             for item in listiter:
    297                 item = deepcopy(item, memo)
    298                 y.append(item)
    299         else:
    300             for item in listiter:
    301                 y.append(item)
    302     if dictiter is not None:
    303         if deep:
    304             for key, value in dictiter:
    305                 key = deepcopy(key, memo)
    306                 value = deepcopy(value, memo)
    307                 y[key] = value
    308         else:
    309             for key, value in dictiter:
    310                 y[key] = value
    311     return y
    312 
    313 del types, weakref, PyStringMap
    314