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