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