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 copy_reg 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    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
101def _copy_immutable(x):
102    return x
103for 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
108for name in ("ComplexType", "UnicodeType", "CodeType"):
109    t = getattr(types, name, None)
110    if t is not None:
111        d[t] = _copy_immutable
112
113def _copy_with_constructor(x):
114    return type(x)(x)
115for t in (list, dict, set):
116    d[t] = _copy_with_constructor
117
118def _copy_with_copy_method(x):
119    return x.copy()
120if PyStringMap is not None:
121    d[PyStringMap] = _copy_with_copy_method
122
123def _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
141d[types.InstanceType] = _copy_inst
142
143del d
144
145def 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
198def _deepcopy_atomic(x, memo):
199    return x
200d[type(None)] = _deepcopy_atomic
201d[type(Ellipsis)] = _deepcopy_atomic
202d[int] = _deepcopy_atomic
203d[long] = _deepcopy_atomic
204d[float] = _deepcopy_atomic
205d[bool] = _deepcopy_atomic
206try:
207    d[complex] = _deepcopy_atomic
208except NameError:
209    pass
210d[str] = _deepcopy_atomic
211try:
212    d[unicode] = _deepcopy_atomic
213except NameError:
214    pass
215try:
216    d[types.CodeType] = _deepcopy_atomic
217except AttributeError:
218    pass
219d[type] = _deepcopy_atomic
220d[xrange] = _deepcopy_atomic
221d[types.ClassType] = _deepcopy_atomic
222d[types.BuiltinFunctionType] = _deepcopy_atomic
223d[types.FunctionType] = _deepcopy_atomic
224d[weakref.ref] = _deepcopy_atomic
225
226def _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
232d[list] = _deepcopy_list
233
234def _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
251d[tuple] = _deepcopy_tuple
252
253def _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
259d[dict] = _deepcopy_dict
260if PyStringMap is not None:
261    d[PyStringMap] = _deepcopy_dict
262
263def _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
267def _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
283def _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
304d[types.InstanceType] = _deepcopy_inst
305
306def _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
361del d
362
363del types
364
365# Helper for instance creation without calling __init__
366class _EmptyClass:
367    pass
368
369def _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
432if __name__ == '__main__':
433    _test()
434