Guido van Rossum | 4b8c6ea | 2000-02-04 15:39:30 +0000 | [diff] [blame] | 1 | """Generic (shallow and deep) copying operations. |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 2 | |
Guido van Rossum | cc6764c | 1995-02-09 17:18:10 +0000 | [diff] [blame] | 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 | |
Guido van Rossum | 55d2f39 | 1995-03-14 17:41:36 +0000 | [diff] [blame] | 10 | For module specific errors, copy.error is raised. |
Guido van Rossum | cc6764c | 1995-02-09 17:18:10 +0000 | [diff] [blame] | 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 in 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 | |
Guido van Rossum | f7cea10 | 1997-05-28 19:31:14 +0000 | [diff] [blame] | 26 | a) recursive objects (compound objects that, directly or indirectly, |
Guido van Rossum | cc6764c | 1995-02-09 17:18:10 +0000 | [diff] [blame] | 27 | contain a reference to themselves) may cause a recursive loop |
| 28 | |
Guido van Rossum | f7cea10 | 1997-05-28 19:31:14 +0000 | [diff] [blame] | 29 | b) because deep copy copies *everything* it may copy too much, e.g. |
Guido van Rossum | cc6764c | 1995-02-09 17:18:10 +0000 | [diff] [blame] | 30 | administrative data structures that should be shared even between |
| 31 | copies |
| 32 | |
| 33 | Python's deep copy operation avoids these problems by: |
| 34 | |
Guido van Rossum | f7cea10 | 1997-05-28 19:31:14 +0000 | [diff] [blame] | 35 | a) keeping a table of objects already copied during the current |
| 36 | copying pass |
Guido van Rossum | cc6764c | 1995-02-09 17:18:10 +0000 | [diff] [blame] | 37 | |
Guido van Rossum | f7cea10 | 1997-05-28 19:31:14 +0000 | [diff] [blame] | 38 | b) letting user-defined classes override the copying operation or the |
Guido van Rossum | cc6764c | 1995-02-09 17:18:10 +0000 | [diff] [blame] | 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__(), |
Guido van Rossum | c5d2d51 | 1997-12-07 16:18:22 +0000 | [diff] [blame] | 47 | __getstate__() and __setstate__(). See the documentation for module |
Guido van Rossum | cc6764c | 1995-02-09 17:18:10 +0000 | [diff] [blame] | 48 | "pickle" for information on these methods. |
| 49 | """ |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 50 | |
Guido van Rossum | abfdd70 | 1997-10-07 14:47:50 +0000 | [diff] [blame] | 51 | # XXX need to support copy_reg here too... |
| 52 | |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 53 | import types |
| 54 | |
Fred Drake | 227b120 | 2000-08-17 05:06:49 +0000 | [diff] [blame] | 55 | class Error(Exception): |
| 56 | pass |
| 57 | error = Error # backward compatibility |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 58 | |
Guido van Rossum | f8baad0 | 2000-11-27 21:53:14 +0000 | [diff] [blame] | 59 | try: |
| 60 | from org.python.core import PyStringMap |
| 61 | except ImportError: |
| 62 | PyStringMap = None |
| 63 | |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 64 | def copy(x): |
Guido van Rossum | cc6764c | 1995-02-09 17:18:10 +0000 | [diff] [blame] | 65 | """Shallow copy operation on arbitrary Python objects. |
| 66 | |
| 67 | See the module's __doc__ string for more info. |
| 68 | """ |
| 69 | |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 70 | try: |
| 71 | copierfunction = _copy_dispatch[type(x)] |
| 72 | except KeyError: |
| 73 | try: |
| 74 | copier = x.__copy__ |
| 75 | except AttributeError: |
Guido van Rossum | 55d2f39 | 1995-03-14 17:41:36 +0000 | [diff] [blame] | 76 | raise error, \ |
Guido van Rossum | cc6764c | 1995-02-09 17:18:10 +0000 | [diff] [blame] | 77 | "un(shallow)copyable object of type %s" % type(x) |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 78 | y = copier() |
| 79 | else: |
| 80 | y = copierfunction(x) |
| 81 | return y |
| 82 | |
| 83 | _copy_dispatch = d = {} |
| 84 | |
| 85 | def _copy_atomic(x): |
| 86 | return x |
| 87 | d[types.NoneType] = _copy_atomic |
| 88 | d[types.IntType] = _copy_atomic |
| 89 | d[types.LongType] = _copy_atomic |
| 90 | d[types.FloatType] = _copy_atomic |
| 91 | d[types.StringType] = _copy_atomic |
Marc-André Lemburg | f156a44 | 2000-09-07 11:00:03 +0000 | [diff] [blame] | 92 | d[types.UnicodeType] = _copy_atomic |
Guido van Rossum | 2fff84d | 1999-01-25 21:37:02 +0000 | [diff] [blame] | 93 | try: |
| 94 | d[types.CodeType] = _copy_atomic |
| 95 | except AttributeError: |
| 96 | pass |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 97 | d[types.TypeType] = _copy_atomic |
| 98 | d[types.XRangeType] = _copy_atomic |
Guido van Rossum | 55d2f39 | 1995-03-14 17:41:36 +0000 | [diff] [blame] | 99 | d[types.ClassType] = _copy_atomic |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 100 | |
| 101 | def _copy_list(x): |
| 102 | return x[:] |
| 103 | d[types.ListType] = _copy_list |
| 104 | |
| 105 | def _copy_tuple(x): |
| 106 | return x[:] |
| 107 | d[types.TupleType] = _copy_tuple |
| 108 | |
| 109 | def _copy_dict(x): |
Guido van Rossum | f7cea10 | 1997-05-28 19:31:14 +0000 | [diff] [blame] | 110 | return x.copy() |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 111 | d[types.DictionaryType] = _copy_dict |
Guido van Rossum | f8baad0 | 2000-11-27 21:53:14 +0000 | [diff] [blame] | 112 | if PyStringMap is not None: |
| 113 | d[PyStringMap] = _copy_dict |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 114 | |
| 115 | def _copy_inst(x): |
| 116 | if hasattr(x, '__copy__'): |
| 117 | return x.__copy__() |
| 118 | if hasattr(x, '__getinitargs__'): |
| 119 | args = x.__getinitargs__() |
Guido van Rossum | c5d2d51 | 1997-12-07 16:18:22 +0000 | [diff] [blame] | 120 | y = apply(x.__class__, args) |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 121 | else: |
Guido van Rossum | c5d2d51 | 1997-12-07 16:18:22 +0000 | [diff] [blame] | 122 | y = _EmptyClass() |
| 123 | y.__class__ = x.__class__ |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 124 | if hasattr(x, '__getstate__'): |
Guido van Rossum | e6eef4b | 1997-10-26 17:00:25 +0000 | [diff] [blame] | 125 | state = x.__getstate__() |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 126 | else: |
Guido van Rossum | e6eef4b | 1997-10-26 17:00:25 +0000 | [diff] [blame] | 127 | state = x.__dict__ |
Guido van Rossum | fefbbe5 | 1995-03-22 10:10:31 +0000 | [diff] [blame] | 128 | if hasattr(y, '__setstate__'): |
Guido van Rossum | e6eef4b | 1997-10-26 17:00:25 +0000 | [diff] [blame] | 129 | y.__setstate__(state) |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 130 | else: |
Guido van Rossum | e6eef4b | 1997-10-26 17:00:25 +0000 | [diff] [blame] | 131 | y.__dict__.update(state) |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 132 | return y |
| 133 | d[types.InstanceType] = _copy_inst |
| 134 | |
| 135 | del d |
| 136 | |
| 137 | def deepcopy(x, memo = None): |
Guido van Rossum | cc6764c | 1995-02-09 17:18:10 +0000 | [diff] [blame] | 138 | """Deep copy operation on arbitrary Python objects. |
| 139 | |
| 140 | See the module's __doc__ string for more info. |
| 141 | """ |
| 142 | |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 143 | if memo is None: |
| 144 | memo = {} |
| 145 | d = id(x) |
| 146 | if memo.has_key(d): |
| 147 | return memo[d] |
| 148 | try: |
| 149 | copierfunction = _deepcopy_dispatch[type(x)] |
| 150 | except KeyError: |
| 151 | try: |
| 152 | copier = x.__deepcopy__ |
| 153 | except AttributeError: |
Guido van Rossum | 55d2f39 | 1995-03-14 17:41:36 +0000 | [diff] [blame] | 154 | raise error, \ |
Guido van Rossum | cc6764c | 1995-02-09 17:18:10 +0000 | [diff] [blame] | 155 | "un-deep-copyable object of type %s" % type(x) |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 156 | y = copier(memo) |
| 157 | else: |
| 158 | y = copierfunction(x, memo) |
| 159 | memo[d] = y |
| 160 | return y |
| 161 | |
| 162 | _deepcopy_dispatch = d = {} |
| 163 | |
| 164 | def _deepcopy_atomic(x, memo): |
| 165 | return x |
| 166 | d[types.NoneType] = _deepcopy_atomic |
| 167 | d[types.IntType] = _deepcopy_atomic |
| 168 | d[types.LongType] = _deepcopy_atomic |
| 169 | d[types.FloatType] = _deepcopy_atomic |
| 170 | d[types.StringType] = _deepcopy_atomic |
Marc-André Lemburg | f156a44 | 2000-09-07 11:00:03 +0000 | [diff] [blame] | 171 | d[types.UnicodeType] = _deepcopy_atomic |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 172 | d[types.CodeType] = _deepcopy_atomic |
| 173 | d[types.TypeType] = _deepcopy_atomic |
| 174 | d[types.XRangeType] = _deepcopy_atomic |
| 175 | |
| 176 | def _deepcopy_list(x, memo): |
| 177 | y = [] |
| 178 | memo[id(x)] = y |
| 179 | for a in x: |
| 180 | y.append(deepcopy(a, memo)) |
| 181 | return y |
| 182 | d[types.ListType] = _deepcopy_list |
| 183 | |
| 184 | def _deepcopy_tuple(x, memo): |
| 185 | y = [] |
| 186 | for a in x: |
| 187 | y.append(deepcopy(a, memo)) |
| 188 | d = id(x) |
| 189 | try: |
| 190 | return memo[d] |
| 191 | except KeyError: |
| 192 | pass |
| 193 | for i in range(len(x)): |
| 194 | if x[i] is not y[i]: |
Guido van Rossum | 6afff61 | 1996-06-17 17:10:11 +0000 | [diff] [blame] | 195 | y = tuple(y) |
| 196 | break |
| 197 | else: |
| 198 | y = x |
| 199 | memo[d] = y |
| 200 | return y |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 201 | d[types.TupleType] = _deepcopy_tuple |
| 202 | |
| 203 | def _deepcopy_dict(x, memo): |
| 204 | y = {} |
| 205 | memo[id(x)] = y |
| 206 | for key in x.keys(): |
| 207 | y[deepcopy(key, memo)] = deepcopy(x[key], memo) |
| 208 | return y |
| 209 | d[types.DictionaryType] = _deepcopy_dict |
Guido van Rossum | f8baad0 | 2000-11-27 21:53:14 +0000 | [diff] [blame] | 210 | if PyStringMap is not None: |
| 211 | d[PyStringMap] = _deepcopy_dict |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 212 | |
Guido van Rossum | 558be28 | 1997-08-20 22:26:19 +0000 | [diff] [blame] | 213 | def _keep_alive(x, memo): |
Guido van Rossum | 8ca8420 | 1998-03-26 20:56:10 +0000 | [diff] [blame] | 214 | """Keeps a reference to the object x in the memo. |
Guido van Rossum | 558be28 | 1997-08-20 22:26:19 +0000 | [diff] [blame] | 215 | |
Guido van Rossum | 8ca8420 | 1998-03-26 20:56:10 +0000 | [diff] [blame] | 216 | Because we remember objects by their id, we have |
| 217 | to assure that possibly temporary objects are kept |
| 218 | alive by referencing them. |
| 219 | We store a reference at the id of the memo, which should |
| 220 | normally not be used unless someone tries to deepcopy |
| 221 | the memo itself... |
| 222 | """ |
| 223 | try: |
| 224 | memo[id(memo)].append(x) |
| 225 | except KeyError: |
| 226 | # aha, this is the first one :-) |
| 227 | memo[id(memo)]=[x] |
Guido van Rossum | 558be28 | 1997-08-20 22:26:19 +0000 | [diff] [blame] | 228 | |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 229 | def _deepcopy_inst(x, memo): |
| 230 | if hasattr(x, '__deepcopy__'): |
Guido van Rossum | 677fc84 | 1998-03-13 20:12:17 +0000 | [diff] [blame] | 231 | return x.__deepcopy__(memo) |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 232 | if hasattr(x, '__getinitargs__'): |
| 233 | args = x.__getinitargs__() |
Guido van Rossum | 558be28 | 1997-08-20 22:26:19 +0000 | [diff] [blame] | 234 | _keep_alive(args, memo) |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 235 | args = deepcopy(args, memo) |
Guido van Rossum | c5d2d51 | 1997-12-07 16:18:22 +0000 | [diff] [blame] | 236 | y = apply(x.__class__, args) |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 237 | else: |
Guido van Rossum | c5d2d51 | 1997-12-07 16:18:22 +0000 | [diff] [blame] | 238 | y = _EmptyClass() |
| 239 | y.__class__ = x.__class__ |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 240 | memo[id(x)] = y |
| 241 | if hasattr(x, '__getstate__'): |
Guido van Rossum | e6eef4b | 1997-10-26 17:00:25 +0000 | [diff] [blame] | 242 | state = x.__getstate__() |
| 243 | _keep_alive(state, memo) |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 244 | else: |
Guido van Rossum | e6eef4b | 1997-10-26 17:00:25 +0000 | [diff] [blame] | 245 | state = x.__dict__ |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 246 | state = deepcopy(state, memo) |
Guido van Rossum | fefbbe5 | 1995-03-22 10:10:31 +0000 | [diff] [blame] | 247 | if hasattr(y, '__setstate__'): |
Guido van Rossum | e6eef4b | 1997-10-26 17:00:25 +0000 | [diff] [blame] | 248 | y.__setstate__(state) |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 249 | else: |
Guido van Rossum | e6eef4b | 1997-10-26 17:00:25 +0000 | [diff] [blame] | 250 | y.__dict__.update(state) |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 251 | return y |
| 252 | d[types.InstanceType] = _deepcopy_inst |
| 253 | |
| 254 | del d |
| 255 | |
| 256 | del types |
| 257 | |
Guido van Rossum | c5d2d51 | 1997-12-07 16:18:22 +0000 | [diff] [blame] | 258 | # Helper for instance creation without calling __init__ |
| 259 | class _EmptyClass: |
| 260 | pass |
| 261 | |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 262 | def _test(): |
Guido van Rossum | 55d2f39 | 1995-03-14 17:41:36 +0000 | [diff] [blame] | 263 | l = [None, 1, 2L, 3.14, 'xyzzy', (1, 2L), [3.14, 'abc'], |
| 264 | {'abc': 'ABC'}, (), [], {}] |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 265 | l1 = copy(l) |
| 266 | print l1==l |
| 267 | l1 = map(copy, l) |
| 268 | print l1==l |
| 269 | l1 = deepcopy(l) |
| 270 | print l1==l |
| 271 | class C: |
| 272 | def __init__(self, arg=None): |
| 273 | self.a = 1 |
| 274 | self.arg = arg |
Guido van Rossum | f7cea10 | 1997-05-28 19:31:14 +0000 | [diff] [blame] | 275 | if __name__ == '__main__': |
| 276 | import sys |
| 277 | file = sys.argv[0] |
| 278 | else: |
| 279 | file = __file__ |
| 280 | self.fp = open(file) |
Guido van Rossum | 409780f | 1995-01-10 00:34:21 +0000 | [diff] [blame] | 281 | self.fp.close() |
| 282 | def __getstate__(self): |
| 283 | return {'a': self.a, 'arg': self.arg} |
| 284 | def __setstate__(self, state): |
| 285 | for key in state.keys(): |
| 286 | setattr(self, key, state[key]) |
| 287 | def __deepcopy__(self, memo = None): |
| 288 | new = self.__class__(deepcopy(self.arg, memo)) |
| 289 | new.a = self.a |
| 290 | return new |
| 291 | c = C('argument sketch') |
| 292 | l.append(c) |
| 293 | l2 = copy(l) |
| 294 | print l == l2 |
| 295 | print l |
| 296 | print l2 |
| 297 | l2 = deepcopy(l) |
| 298 | print l == l2 |
| 299 | print l |
| 300 | print l2 |
| 301 | l.append({l[1]: l, 'xyz': l[2]}) |
| 302 | l3 = copy(l) |
| 303 | import repr |
| 304 | print map(repr.repr, l) |
| 305 | print map(repr.repr, l1) |
| 306 | print map(repr.repr, l2) |
| 307 | print map(repr.repr, l3) |
| 308 | l3 = deepcopy(l) |
| 309 | import repr |
| 310 | print map(repr.repr, l) |
| 311 | print map(repr.repr, l1) |
| 312 | print map(repr.repr, l2) |
| 313 | print map(repr.repr, l3) |
| 314 | |
| 315 | if __name__ == '__main__': |
| 316 | _test() |