Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/pyrsistent/

1from collections.abc import Mapping, Hashable

2from itertools import chain

3from pyrsistent._pvector import pvector

4from pyrsistent._transformations import transform

6class PMapView:

7 """View type for the persistent map/dict type `PMap`.

9 Provides an equivalent of Python's built-in `dict_values` and `dict_items`

10 types that result from expreessions such as `{}.values()` and

11 `{}.items()`. The equivalent for `{}.keys()` is absent because the keys are

12 instead represented by a `PSet` object, which can be created in `O(1)` time.

14 The `PMapView` class is overloaded by the `PMapValues` and `PMapItems`

15 classes which handle the specific case of values and items, respectively

17 Parameters

18 ----------

19 m : mapping

20 The mapping/dict-like object of which a view is to be created. This

21 should generally be a `PMap` object.

22 """

23 # The public methods that use the above.

24 def __init__(self, m):

25 # Make sure this is a persistnt map

26 if not isinstance(m, PMap):

27 # We can convert mapping objects into pmap objects, I guess (but why?)

28 if isinstance(m, Mapping):

29 m = pmap(m)

30 else:

31 raise TypeError("PViewMap requires a Mapping object")

32 object.__setattr__(self, '_map', m)

34 def __len__(self):

35 return len(self._map)

37 def __setattr__(self, k, v):

38 raise TypeError("%s is immutable" % (type(self),))

40 def __reversed__(self):

41 raise TypeError("Persistent maps are not reversible")

43class PMapValues(PMapView):

44 """View type for the values of the persistent map/dict type `PMap`.

46 Provides an equivalent of Python's built-in `dict_values` type that result

47 from expreessions such as `{}.values()`. See also `PMapView`.

49 Parameters

50 ----------

51 m : mapping

52 The mapping/dict-like object of which a view is to be created. This

53 should generally be a `PMap` object.

54 """

55 def __iter__(self):

56 return self._map.itervalues()

58 def __contains__(self, arg):

59 return arg in self._map.itervalues()

61 # The str and repr methods imitate the dict_view style currently.

62 def __str__(self):

63 return f"pmap_values({list(iter(self))})"

65 def __repr__(self):

66 return f"pmap_values({list(iter(self))})"

68 def __eq__(self, x):

69 # For whatever reason, dict_values always seem to return False for ==

70 # (probably it's not implemented), so we mimic that.

71 if x is self: return True

72 else: return False

74class PMapItems(PMapView):

75 """View type for the items of the persistent map/dict type `PMap`.

77 Provides an equivalent of Python's built-in `dict_items` type that result

78 from expreessions such as `{}.items()`. See also `PMapView`.

80 Parameters

81 ----------

82 m : mapping

83 The mapping/dict-like object of which a view is to be created. This

84 should generally be a `PMap` object.

85 """

86 def __iter__(self):

87 return self._map.iteritems()

89 def __contains__(self, arg):

90 try: (k,v) = arg

91 except Exception: return False

92 return k in self._map and self._map[k] == v

94 # The str and repr methods mitate the dict_view style currently.

95 def __str__(self):

96 return f"pmap_items({list(iter(self))})"

98 def __repr__(self):

99 return f"pmap_items({list(iter(self))})"

100

101 def __eq__(self, x):

102 if x is self: return True

103 elif not isinstance(x, type(self)): return False

104 else: return self._map == x._map

105

106class PMap(object):

107 """

108 Persistent map/dict. Tries to follow the same naming conventions as the built in dict where feasible.

109

110 Do not instantiate directly, instead use the factory functions :py:func:`m` or :py:func:`pmap` to

111 create an instance.

112

113 Was originally written as a very close copy of the Clojure equivalent but was later rewritten to closer

114 re-assemble the python dict. This means that a sparse vector (a PVector) of buckets is used. The keys are

115 hashed and the elements inserted at position hash % len(bucket_vector). Whenever the map size exceeds 2/3 of

116 the containing vectors size the map is reallocated to a vector of double the size. This is done to avoid

117 excessive hash collisions.

118

119 This structure corresponds most closely to the built in dict type and is intended as a replacement. Where the

120 semantics are the same (more or less) the same function names have been used but for some cases it is not possible,

121 for example assignments and deletion of values.

122

123 PMap implements the Mapping protocol and is Hashable. It also supports dot-notation for

124 element access.

125

126 Random access and insert is log32(n) where n is the size of the map.

127

128 The following are examples of some common operations on persistent maps

129

130 >>> m1 = m(a=1, b=3)

131 >>> m2 = m1.set('c', 3)

132 >>> m3 = m2.remove('a')

133 >>> m1 == {'a': 1, 'b': 3}

134 True

135 >>> m2 == {'a': 1, 'b': 3, 'c': 3}

136 True

137 >>> m3 == {'b': 3, 'c': 3}

138 True

139 >>> m3['c']

140 3

141 >>> m3.c

142 3

143 """

144 __slots__ = ('_size', '_buckets', '__weakref__', '_cached_hash')

145

146 def __new__(cls, size, buckets):

147 self = super(PMap, cls).__new__(cls)

148 self._size = size

149 self._buckets = buckets

150 return self

151

152 @staticmethod

153 def _get_bucket(buckets, key):

154 index = hash(key) % len(buckets)

155 bucket = buckets[index]

156 return index, bucket

157

158 @staticmethod

159 def _getitem(buckets, key):

160 _, bucket = PMap._get_bucket(buckets, key)

161 if bucket:

162 for k, v in bucket:

163 if k == key:

164 return v

165

166 raise KeyError(key)

167

168 def __getitem__(self, key):

169 return PMap._getitem(self._buckets, key)

170

171 @staticmethod

172 def _contains(buckets, key):

173 _, bucket = PMap._get_bucket(buckets, key)

174 if bucket:

175 for k, _ in bucket:

176 if k == key:

177 return True

178

179 return False

180

181 return False

182

183 def __contains__(self, key):

184 return self._contains(self._buckets, key)

185

186 get = Mapping.get

187

188 def __iter__(self):

189 return self.iterkeys()

190

191 # If this method is not defined, then reversed(pmap) will attempt to reverse

192 # the map using len() and getitem, usually resulting in a mysterious

193 # KeyError.

194 def __reversed__(self):

195 raise TypeError("Persistent maps are not reversible")

196

197 def __getattr__(self, key):

198 try:

199 return self[key]

200 except KeyError as e:

201 raise AttributeError(

202 "{0} has no attribute '{1}'".format(type(self).__name__, key)

203 ) from e

204

205 def iterkeys(self):

206 for k, _ in self.iteritems():

207 yield k

208

209 # These are more efficient implementations compared to the original

210 # methods that are based on the keys iterator and then calls the

211 # accessor functions to access the value for the corresponding key

212 def itervalues(self):

213 for _, v in self.iteritems():

214 yield v

215

216 def iteritems(self):

217 for bucket in self._buckets:

218 if bucket:

219 for k, v in bucket:

220 yield k, v

221

222 def values(self):

223 return PMapValues(self)

224

225 def keys(self):

226 from ._pset import PSet

227 return PSet(self)

228

229 def items(self):

230 return PMapItems(self)

231

232 def __len__(self):

233 return self._size

234

235 def __repr__(self):

236 return 'pmap({0})'.format(str(dict(self)))

237

238 def __eq__(self, other):

239 if self is other:

240 return True

241 if not isinstance(other, Mapping):

242 return NotImplemented

243 if len(self) != len(other):

244 return False

245 if isinstance(other, PMap):

246 if (hasattr(self, '_cached_hash') and hasattr(other, '_cached_hash')

247 and self._cached_hash != other._cached_hash):

248 return False

249 if self._buckets == other._buckets:

250 return True

251 return dict(self.iteritems()) == dict(other.iteritems())

252 elif isinstance(other, dict):

253 return dict(self.iteritems()) == other

254 return dict(self.iteritems()) == dict(other.items())

255

256 __ne__ = Mapping.__ne__

257

258 def __lt__(self, other):

259 raise TypeError('PMaps are not orderable')

260

261 __le__ = __lt__

262 __gt__ = __lt__

263 __ge__ = __lt__

264

265 def __str__(self):

266 return self.__repr__()

267

268 def __hash__(self):

269 if not hasattr(self, '_cached_hash'):

270 self._cached_hash = hash(frozenset(self.iteritems()))

271 return self._cached_hash

272

273 def set(self, key, val):

274 """

275 Return a new PMap with key and val inserted.

276

277 >>> m1 = m(a=1, b=2)

278 >>> m2 = m1.set('a', 3)

279 >>> m3 = m1.set('c' ,4)

280 >>> m1 == {'a': 1, 'b': 2}

281 True

282 >>> m2 == {'a': 3, 'b': 2}

283 True

284 >>> m3 == {'a': 1, 'b': 2, 'c': 4}

285 True

286 """

287 return self.evolver().set(key, val).persistent()

288

289 def remove(self, key):

290 """

291 Return a new PMap without the element specified by key. Raises KeyError if the element

292 is not present.

293

294 >>> m1 = m(a=1, b=2)

295 >>> m1.remove('a')

296 pmap({'b': 2})

297 """

298 return self.evolver().remove(key).persistent()

299

300 def discard(self, key):

301 """

302 Return a new PMap without the element specified by key. Returns reference to itself

303 if element is not present.

304

305 >>> m1 = m(a=1, b=2)

306 >>> m1.discard('a')

307 pmap({'b': 2})

308 >>> m1 is m1.discard('c')

309 True

310 """

311 try:

312 return self.remove(key)

313 except KeyError:

314 return self

315

316 def update(self, *maps):

317 """

318 Return a new PMap with the items in Mappings inserted. If the same key is present in multiple

319 maps the rightmost (last) value is inserted.

320

321 >>> m1 = m(a=1, b=2)

322 >>> m1.update(m(a=2, c=3), {'a': 17, 'd': 35}) == {'a': 17, 'b': 2, 'c': 3, 'd': 35}

323 True

324 """

325 return self.update_with(lambda l, r: r, *maps)

326

327 def update_with(self, update_fn, *maps):

328 """

329 Return a new PMap with the items in Mappings maps inserted. If the same key is present in multiple

330 maps the values will be merged using merge_fn going from left to right.

331

332 >>> from operator import add

333 >>> m1 = m(a=1, b=2)

334 >>> m1.update_with(add, m(a=2)) == {'a': 3, 'b': 2}

335 True

336

337 The reverse behaviour of the regular merge. Keep the leftmost element instead of the rightmost.

338

339 >>> m1 = m(a=1)

340 >>> m1.update_with(lambda l, r: l, m(a=2), {'a':3})

341 pmap({'a': 1})

342 """

343 evolver = self.evolver()

344 for map in maps:

345 for key, value in map.items():

346 evolver.set(key, update_fn(evolver[key], value) if key in evolver else value)

347

348 return evolver.persistent()

349

350 def __add__(self, other):

351 return self.update(other)

352

353 __or__ = __add__

354

355 def __reduce__(self):

356 # Pickling support

357 return pmap, (dict(self),)

358

359 def transform(self, *transformations):

360 """

361 Transform arbitrarily complex combinations of PVectors and PMaps. A transformation

362 consists of two parts. One match expression that specifies which elements to transform

363 and one transformation function that performs the actual transformation.

364

365 >>> from pyrsistent import freeze, ny

366 >>> news_paper = freeze({'articles': [{'author': 'Sara', 'content': 'A short article'},

367 ... {'author': 'Steve', 'content': 'A slightly longer article'}],

368 ... 'weather': {'temperature': '11C', 'wind': '5m/s'}})

369 >>> short_news = news_paper.transform(['articles', ny, 'content'], lambda c: c[:25] + '...' if len(c) > 25 else c)

370 >>> very_short_news = news_paper.transform(['articles', ny, 'content'], lambda c: c[:15] + '...' if len(c) > 15 else c)

371 >>> very_short_news.articles[0].content

372 'A short article'

373 >>> very_short_news.articles[1].content

374 'A slightly long...'

375

376 When nothing has been transformed the original data structure is kept

377

378 >>> short_news is news_paper

379 True

380 >>> very_short_news is news_paper

381 False

382 >>> very_short_news.articles[0] is news_paper.articles[0]

383 True

384 """

385 return transform(self, transformations)

386

387 def copy(self):

388 return self

389

390 class _Evolver(object):

391 __slots__ = ('_buckets_evolver', '_size', '_original_pmap')

392

393 def __init__(self, original_pmap):

394 self._original_pmap = original_pmap

395 self._buckets_evolver = original_pmap._buckets.evolver()

396 self._size = original_pmap._size

397

398 def __getitem__(self, key):

399 return PMap._getitem(self._buckets_evolver, key)

400

401 def __setitem__(self, key, val):

402 self.set(key, val)

403

404 def set(self, key, val):

405 kv = (key, val)

406 index, bucket = PMap._get_bucket(self._buckets_evolver, key)

407 reallocation_required = len(self._buckets_evolver) < 0.67 * self._size

408 if bucket:

409 for k, v in bucket:

410 if k == key:

411 if v is not val:

412 new_bucket = [(k2, v2) if k2 != k else (k2, val) for k2, v2 in bucket]

413 self._buckets_evolver[index] = new_bucket

414

415 return self

416

417 # Only check and perform reallocation if not replacing an existing value.

418 # This is a performance tweak, see #247.

419 if reallocation_required:

420 self._reallocate()

421 return self.set(key, val)

422

423 new_bucket = [kv]

424 new_bucket.extend(bucket)

425 self._buckets_evolver[index] = new_bucket

426 self._size += 1

427 else:

428 if reallocation_required:

429 self._reallocate()

430 return self.set(key, val)

431

432 self._buckets_evolver[index] = [kv]

433 self._size += 1

434

435 return self

436

437 def _reallocate(self):

438 new_size = 2 * len(self._buckets_evolver)

439 new_list = new_size * [None]

440 buckets = self._buckets_evolver.persistent()

441 for k, v in chain.from_iterable(x for x in buckets if x):

442 index = hash(k) % new_size

443 if new_list[index]:

444 new_list[index].append((k, v))

445 else:

446 new_list[index] = [(k, v)]

447

448 # A reallocation should always result in a dirty buckets evolver to avoid

449 # possible loss of elements when doing the reallocation.

450 self._buckets_evolver = pvector().evolver()

451 self._buckets_evolver.extend(new_list)

452

453 def is_dirty(self):

454 return self._buckets_evolver.is_dirty()

455

456 def persistent(self):

457 if self.is_dirty():

458 self._original_pmap = PMap(self._size, self._buckets_evolver.persistent())

459

460 return self._original_pmap

461

462 def __len__(self):

463 return self._size

464

465 def __contains__(self, key):

466 return PMap._contains(self._buckets_evolver, key)

467

468 def __delitem__(self, key):

469 self.remove(key)

470

471 def remove(self, key):

472 index, bucket = PMap._get_bucket(self._buckets_evolver, key)

473

474 if bucket:

475 new_bucket = [(k, v) for (k, v) in bucket if k != key]

476 if len(bucket) > len(new_bucket):

477 self._buckets_evolver[index] = new_bucket if new_bucket else None

478 self._size -= 1

479 return self

480

481 raise KeyError('{0}'.format(key))

482

483 def evolver(self):

484 """

485 Create a new evolver for this pmap. For a discussion on evolvers in general see the

486 documentation for the pvector evolver.

487

488 Create the evolver and perform various mutating updates to it:

489

490 >>> m1 = m(a=1, b=2)

491 >>> e = m1.evolver()

492 >>> e['c'] = 3

493 >>> len(e)

494 3

495 >>> del e['a']

496

497 The underlying pmap remains the same:

498

499 >>> m1 == {'a': 1, 'b': 2}

500 True

501

502 The changes are kept in the evolver. An updated pmap can be created using the

503 persistent() function on the evolver.

504

505 >>> m2 = e.persistent()

506 >>> m2 == {'b': 2, 'c': 3}

507 True

508

509 The new pmap will share data with the original pmap in the same way that would have

510 been done if only using operations on the pmap.

511 """

512 return self._Evolver(self)

513

514Mapping.register(PMap)

515Hashable.register(PMap)

516

517

518def _turbo_mapping(initial, pre_size):

519 if pre_size:

520 size = pre_size

521 else:

522 try:

523 size = 2 * len(initial) or 8

524 except Exception:

525 # Guess we can't figure out the length. Give up on length hinting,

526 # we can always reallocate later.

527 size = 8

528

529 buckets = size * [None]

530

531 if not isinstance(initial, Mapping):

532 # Make a dictionary of the initial data if it isn't already,

533 # that will save us some job further down since we can assume no

534 # key collisions

535 initial = dict(initial)

536

537 for k, v in initial.items():

538 h = hash(k)

539 index = h % size

540 bucket = buckets[index]

541

542 if bucket:

543 bucket.append((k, v))

544 else:

545 buckets[index] = [(k, v)]

546

547 return PMap(len(initial), pvector().extend(buckets))

548

549

550_EMPTY_PMAP = _turbo_mapping({}, 0)

551

552

553def pmap(initial={}, pre_size=0):

554 """

555 Create new persistent map, inserts all elements in initial into the newly created map.

556 The optional argument pre_size may be used to specify an initial size of the underlying bucket vector. This

557 may have a positive performance impact in the cases where you know beforehand that a large number of elements

558 will be inserted into the map eventually since it will reduce the number of reallocations required.

559

560 >>> pmap({'a': 13, 'b': 14}) == {'a': 13, 'b': 14}

561 True

562 """

563 if not initial and pre_size == 0:

564 return _EMPTY_PMAP

565

566 return _turbo_mapping(initial, pre_size)

567

568

569def m(**kwargs):

570 """

571 Creates a new persistent map. Inserts all key value arguments into the newly created map.

572

573 >>> m(a=13, b=14) == {'a': 13, 'b': 14}

574 True

575 """

576 return pmap(kwargs)

Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/pyrsistent/_pmap.py: 64%

258 statements