• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1"""Generic (shallow and deep) copying operations.
2
3Interface 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
10For module specific errors, copy.Error is raised.
11
12The difference between shallow and deep copying is only relevant for
13compound objects (objects that contain other objects, like lists or
14class 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
23Two problems often exist with deep copy operations that don't exist
24with 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
33Python'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
41This version does not copy types like module, class, function, method,
42nor stack trace, stack frame, nor file, socket, window, nor array, nor
43any similar types.
44
45Classes can use the same interfaces to control copying that they use
46to 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
51import types
52import weakref
53from copyreg import dispatch_table
54
55class Error(Exception):
56    pass
57error = Error   # backward compatibility
58
59try:
60    from org.python.core import PyStringMap
61except ImportError:
62    PyStringMap = None
63
64__all__ = ["Error", "copy", "deepcopy"]
65
66def 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
111def _copy_immutable(x):
112    return x
113for 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
118t = getattr(types, "CodeType", None)
119if t is not None:
120    d[t] = _copy_immutable
121
122d[list] = list.copy
123d[dict] = dict.copy
124d[set] = set.copy
125d[bytearray] = bytearray.copy
126
127if PyStringMap is not None:
128    d[PyStringMap] = PyStringMap.copy
129
130del d, t
131
132def 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
190def _deepcopy_atomic(x, memo):
191    return x
192d[type(None)] = _deepcopy_atomic
193d[type(Ellipsis)] = _deepcopy_atomic
194d[type(NotImplemented)] = _deepcopy_atomic
195d[int] = _deepcopy_atomic
196d[float] = _deepcopy_atomic
197d[bool] = _deepcopy_atomic
198d[complex] = _deepcopy_atomic
199d[bytes] = _deepcopy_atomic
200d[str] = _deepcopy_atomic
201try:
202    d[types.CodeType] = _deepcopy_atomic
203except AttributeError:
204    pass
205d[type] = _deepcopy_atomic
206d[types.BuiltinFunctionType] = _deepcopy_atomic
207d[types.FunctionType] = _deepcopy_atomic
208d[weakref.ref] = _deepcopy_atomic
209
210def _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
217d[list] = _deepcopy_list
218
219def _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
234d[tuple] = _deepcopy_tuple
235
236def _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
242d[dict] = _deepcopy_dict
243if PyStringMap is not None:
244    d[PyStringMap] = _deepcopy_dict
245
246def _deepcopy_method(x, memo): # Copy instance methods
247    return type(x)(x.__func__, deepcopy(x.__self__, memo))
248d[types.MethodType] = _deepcopy_method
249
250del d
251
252def _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
268def _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
313del types, weakref, PyStringMap
314