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