• 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    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[types.BuiltinFunctionType] = _deepcopy_atomic
196d[types.FunctionType] = _deepcopy_atomic
197d[weakref.ref] = _deepcopy_atomic
198d[property] = _deepcopy_atomic
199
200def _deepcopy_list(x, memo, deepcopy=deepcopy):
201    y = []
202    memo[id(x)] = y
203    append = y.append
204    for a in x:
205        append(deepcopy(a, memo))
206    return y
207d[list] = _deepcopy_list
208
209def _deepcopy_tuple(x, memo, deepcopy=deepcopy):
210    y = [deepcopy(a, memo) for a in x]
211    # We're not going to put the tuple in the memo, but it's still important we
212    # check for it, in case the tuple contains recursive mutable structures.
213    try:
214        return memo[id(x)]
215    except KeyError:
216        pass
217    for k, j in zip(x, y):
218        if k is not j:
219            y = tuple(y)
220            break
221    else:
222        y = x
223    return y
224d[tuple] = _deepcopy_tuple
225
226def _deepcopy_dict(x, memo, deepcopy=deepcopy):
227    y = {}
228    memo[id(x)] = y
229    for key, value in x.items():
230        y[deepcopy(key, memo)] = deepcopy(value, memo)
231    return y
232d[dict] = _deepcopy_dict
233if PyStringMap is not None:
234    d[PyStringMap] = _deepcopy_dict
235
236def _deepcopy_method(x, memo): # Copy instance methods
237    return type(x)(x.__func__, deepcopy(x.__self__, memo))
238d[types.MethodType] = _deepcopy_method
239
240del d
241
242def _keep_alive(x, memo):
243    """Keeps a reference to the object x in the memo.
244
245    Because we remember objects by their id, we have
246    to assure that possibly temporary objects are kept
247    alive by referencing them.
248    We store a reference at the id of the memo, which should
249    normally not be used unless someone tries to deepcopy
250    the memo itself...
251    """
252    try:
253        memo[id(memo)].append(x)
254    except KeyError:
255        # aha, this is the first one :-)
256        memo[id(memo)]=[x]
257
258def _reconstruct(x, memo, func, args,
259                 state=None, listiter=None, dictiter=None,
260                 deepcopy=deepcopy):
261    deep = memo is not None
262    if deep and args:
263        args = (deepcopy(arg, memo) for arg in args)
264    y = func(*args)
265    if deep:
266        memo[id(x)] = y
267
268    if state is not None:
269        if deep:
270            state = deepcopy(state, memo)
271        if hasattr(y, '__setstate__'):
272            y.__setstate__(state)
273        else:
274            if isinstance(state, tuple) and len(state) == 2:
275                state, slotstate = state
276            else:
277                slotstate = None
278            if state is not None:
279                y.__dict__.update(state)
280            if slotstate is not None:
281                for key, value in slotstate.items():
282                    setattr(y, key, value)
283
284    if listiter is not None:
285        if deep:
286            for item in listiter:
287                item = deepcopy(item, memo)
288                y.append(item)
289        else:
290            for item in listiter:
291                y.append(item)
292    if dictiter is not None:
293        if deep:
294            for key, value in dictiter:
295                key = deepcopy(key, memo)
296                value = deepcopy(value, memo)
297                y[key] = value
298        else:
299            for key, value in dictiter:
300                y[key] = value
301    return y
302
303del types, weakref, PyStringMap
304