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