A high-performance immutable mapping type for Python.

Last update: Jan 02, 2023

Overview

immutables

An immutable mapping type for Python.

The underlying datastructure is a Hash Array Mapped Trie (HAMT) used in Clojure, Scala, Haskell, and other functional languages. This implementation is used in CPython 3.7 in the contextvars module (see PEP 550 and PEP 567 for more details).

Immutable mappings based on HAMT have O(log N) performance for both set() and get() operations, which is essentially O(1) for relatively small mappings.

Below is a visualization of a simple get/set benchmark comparing HAMT to an immutable mapping implemented with a Python dict copy-on-write approach (the benchmark code is available here):

Installation

immutables requires Python 3.6+ and is available on PyPI:

$ pip install immutables

API

immutables.Map is an unordered immutable mapping. Map objects are hashable, comparable, and pickleable.

The Map object implements the collections.abc.Mapping ABC so working with it is very similar to working with Python dicts:

import immutables

map = immutables.Map(a=1, b=2)

print(map['a'])
# will print '1'

print(map.get('z', 100))
# will print '100'

print('z' in map)
# will print 'False'

Since Maps are immutable, there is a special API for mutations that allow apply changes to the Map object and create new (derived) Maps:

map2 = map.set('a', 10)
print(map, map2)
# will print:
#   
   
#   
   

map3 = map2.delete('b')
print(map, map2, map3)
# will print:
#   
   
#   
   
#

Maps also implement APIs for bulk updates: MapMutation objects:

map_mutation = map.mutate()
map_mutation['a'] = 100
del map_mutation['b']
map_mutation.set('y', 'y')

map2 = map_mutation.finish()

print(map, map2)
# will print:
#   
   
#

MapMutation objects are context managers. Here's the above example rewritten in a more idiomatic way:

with map.mutate() as mm:
    mm['a'] = 100
    del mm['b']
    mm.set('y', 'y')
    map2 = mm.finish()

print(map, map2)
# will print:
#   
   
#

Further development

An immutable version of Python set type with efficient add() and discard() operations.

License

Apache 2.0

Comments

0.16: pytest is failing

I'm trying to package your module as rpm packag. So I'm using typical in such case build, install and test cycle used on building package from non-root account:

"setup.py build"
"setup.py install --root </install/prefix>"
"pytest with PYTHONPATH pointing to sitearch and sitelib inside </install/prefix>

May I ask for help because few units are failing:

+ PYTHONPATH=/home/tkloczko/rpmbuild/BUILDROOT/python-immutables-0.16-2.fc35.x86_64/usr/lib64/python3.8/site-packages:/home/tkloczko/rpmbuild/BUILDROOT/python-immutables-0.16-2.fc35.x86_64/usr/lib/python3.8/site-packages
+ /usr/bin/pytest -ra
=========================================================================== test session starts ============================================================================
platform linux -- Python 3.8.11, pytest-6.2.4, py-1.10.0, pluggy-0.13.1
benchmark: 3.4.1 (defaults: timer=time.perf_counter disable_gc=False min_rounds=5 min_time=0.000005 max_time=1.0 calibration_precision=10 warmup=False warmup_iterations=100000)
rootdir: /home/tkloczko/rpmbuild/BUILD/immutables-0.16, configfile: pytest.ini, testpaths: tests
plugins: forked-1.3.0, shutil-1.7.0, virtualenv-1.7.0, expect-1.1.0, flake8-1.0.7, timeout-1.4.2, betamax-0.8.1, freezegun-0.4.2, case-1.5.3, isort-1.3.0, aspectlib-1.5.2, toolbox-0.5, mock-3.6.1, rerunfailures-9.1.1, requests-mock-1.9.3, cov-2.12.1, pyfakefs-4.5.0, flaky-3.7.0, benchmark-3.4.1, xdist-2.3.0, pylama-7.7.1, datadir-1.3.1, regressions-2.2.0, cases-3.6.3, hypothesis-6.14.4, xprocess-0.18.1, black-0.3.12, checkdocs-2.7.1, anyio-3.3.0, Faker-8.11.0, asyncio-0.15.1, trio-0.7.0, httpbin-1.0.0, subtests-0.5.0
collected 153 items

tests/test_issue24.py .....sssssss
tests/test_map.py .............................................................sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss
tests/test_mypy.py Expected:
  ...
  test.py:30: error: Incompatible types in assignment (expression has type "M...
  test.py:31: error: Incompatible types in assignment (expression has type "M...
  test.py:33: error: Incompatible types in assignment (expression has type "M...
  test.py:34: error: Incompatible types in assignment (expression has type "M...
  test.py:44: error: Unexpected keyword argument "three" for "update" of "Map" (diff)
  test.py:45: error: Argument 1 to "update" of "Map" has incompatible type "Dict[int, int]"; expected "Union[IterableItems[int, str], Iterable[Tuple[int, str]]]" (diff)
  test.py:49: error: Argument 1 to "update" of "Map" has incompatible type "Dict[str, int]"; expected "Union[IterableItems[str, str], Iterable[Tuple[str, str]]]" (diff)
  test.py:53: error: Argument 1 to "update" of "Map" has incompatible type "Dict[str, int]"; expected "Union[IterableItems[Union[int, str], str], Iterable[Tuple[Union[int, str], str]]]" (diff)
  test.py:57: error: Argument 1 to "update" of "Map" has incompatible type "Dict[int, int]"; expected "Union[IterableItems[str, Union[int, str]], Iterable[Tuple[str, Union[int, str]]]]" (diff)
  test.py:63: error: Invalid index type "int" for "MapMutation[str, str]"; expected type "str" (diff)
  test.py:64: error: Incompatible types in assignment (expression has type "int", target has type "str") (diff)
  test.py:70: note: Revealed type is "immutables._map.Map[builtins.str*, builtins.str*]" (diff)
Actual:
  ...
  test.py:30: error: Incompatible types in assignment (expression has type "M...
  test.py:31: error: Incompatible types in assignment (expression has type "M...
  test.py:33: error: Incompatible types in assignment (expression has type "M...
  test.py:34: error: Incompatible types in assignment (expression has type "M...
  test.py:35: error: Incompatible types in assignment (expression has type "Map[str, str]", variable has type "Map[str, Union[int, str]]") (diff)
  test.py:45: error: Argument 1 to "update" of "Map" has incompatible type "Dict[int, int]"; expected "Union[Mapping[int, str], Iterable[Tuple[int, str]]]" (diff)
  test.py:49: error: Argument 1 to "update" of "Map" has incompatible type "Dict[str, int]"; expected "Union[Mapping[str, str], Iterable[Tuple[str, str]]]" (diff)
  test.py:52: error: Argument 1 to "update" of "Map" has incompatible type "Dict[int, str]"; expected "Union[Mapping[Union[int, str], str], Iterable[Tuple[Union[int, str], str]]]" (diff)
  test.py:53: error: Argument 1 to "update" of "Map" has incompatible type "Dict[str, int]"; expected "Union[Mapping[Union[int, str], str], Iterable[Tuple[Union[int, str], str]]]" (diff)
  test.py:57: error: Argument 1 to "update" of "Map" has incompatible type "Dict[int, int]"; expected "Union[Mapping[str, Union[int, str]], Iterable[Tuple[str, Union[int, str]]]]" (diff)
  test.py:63: error: Invalid index type "int" for "MapMutation[str, str]"; expected type "str" (diff)
  test.py:64: error: Incompatible types in assignment (expression has type "int", target has type "str") (diff)
  test.py:70: note: Revealed type is "immutables._map.Map[builtins.str*, builtins.str*]" (diff)

Alignment of first line difference:
  E: test.py:44: error: Unexpected keyword argument "three" for "update" of "...
  A: test.py:35: error: Incompatible types in assignment (expression has type...
             ^
F
tests/test_none_keys.py .........sssssssss

================================================================================= FAILURES =================================================================================
_______________________________________________________________________________ testMypyImmu _______________________________________________________________________________
data: /home/tkloczko/rpmbuild/BUILD/immutables-0.16/tests/test-data/check-immu.test:1:
/usr/lib/python3.8/site-packages/pluggy/hooks.py:286: in __call__
    return self._hookexec(self, self.get_hookimpls(), kwargs)
/usr/lib/python3.8/site-packages/pluggy/manager.py:93: in _hookexec
    return self._inner_hookexec(hook, methods, kwargs)
/usr/lib/python3.8/site-packages/pluggy/manager.py:84: in <lambda>
    self._inner_hookexec = lambda hook, methods, kwargs: hook.multicall(
/usr/lib/python3.8/site-packages/_pytest/runner.py:170: in pytest_runtest_call
    raise e
/usr/lib/python3.8/site-packages/_pytest/runner.py:162: in pytest_runtest_call
    item.runtest()
/usr/lib/python3.8/site-packages/mypy/test/data.py:248: in runtest
    suite.run_case(self)
/usr/lib/python3.8/site-packages/mypy/test/testcmdline.py:39: in run_case
    test_python_cmdline(testcase, step)
/usr/lib/python3.8/site-packages/mypy/test/testcmdline.py:101: in test_python_cmdline
    assert_string_arrays_equal(expected_out, out,
/usr/lib/python3.8/site-packages/mypy/test/helpers.py:117: in assert_string_arrays_equal
    raise AssertionError(msg)
E   AssertionError: Invalid output (/home/tkloczko/rpmbuild/BUILD/immutables-0.16/tests/test-data/check-immu.test, line 1)
============================================================================= warnings summary =============================================================================
../../../../../usr/lib/python3.8/site-packages/_pytest/config/__init__.py:1183
  /usr/lib/python3.8/site-packages/_pytest/config/__init__.py:1183: PytestDeprecationWarning: The --strict option is deprecated, use --strict-markers instead.
    self.issue_config_time_warning(

-- Docs: https://docs.pytest.org/en/stable/warnings.html
========================================================================= short test summary info ==========================================================================
SKIPPED [1] tests/test_issue24.py:137: C Map is not available
SKIPPED [1] tests/test_issue24.py:126: C Map is not available
SKIPPED [1] tests/test_issue24.py:59: C Map is not available
SKIPPED [1] tests/test_issue24.py:47: C Map is not available
SKIPPED [1] tests/test_issue24.py:88: C Map is not available
SKIPPED [1] tests/test_issue24.py:74: C Map is not available
SKIPPED [1] tests/test_issue24.py:14: C Map is not available
SKIPPED [1] tests/test_map.py:913: C Map is not available
SKIPPED [1] tests/test_map.py:886: C Map is not available
SKIPPED [1] tests/test_map.py:899: C Map is not available
SKIPPED [1] tests/test_map.py:22: C Map is not available
SKIPPED [1] tests/test_map.py:1359: C Map is not available
SKIPPED [1] tests/test_map.py:36: C Map is not available
SKIPPED [1] tests/test_map.py:40: C Map is not available
SKIPPED [1] tests/test_map.py:70: C Map is not available
SKIPPED [1] tests/test_map.py:77: C Map is not available
SKIPPED [1] tests/test_map.py:86: C Map is not available
SKIPPED [1] tests/test_map.py:123: C Map is not available
SKIPPED [1] tests/test_map.py:329: C Map is not available
SKIPPED [1] tests/test_map.py:376: C Map is not available
SKIPPED [1] tests/test_map.py:438: C Map is not available
SKIPPED [1] tests/test_map.py:495: C Map is not available
SKIPPED [1] tests/test_map.py:537: C Map is not available
SKIPPED [1] tests/test_map.py:589: C Map is not available
SKIPPED [1] tests/test_map.py:698: C Map is not available
SKIPPED [1] tests/test_map.py:745: C Map is not available
SKIPPED [1] tests/test_map.py:761: C Map is not available
SKIPPED [1] tests/test_map.py:764: C Map is not available
SKIPPED [1] tests/test_map.py:787: C Map is not available
SKIPPED [1] tests/test_map.py:826: C Map is not available
SKIPPED [1] tests/test_map.py:806: C Map is not available
SKIPPED [1] tests/test_map.py:1353: C Map is not available
SKIPPED [1] tests/test_map.py:596: C Map is not available
SKIPPED [1] tests/test_map.py:617: C Map is not available
SKIPPED [1] tests/test_map.py:638: C Map is not available
SKIPPED [1] tests/test_map.py:643: C Map is not available
SKIPPED [1] tests/test_map.py:649: C Map is not available
SKIPPED [1] tests/test_map.py:668: C Map is not available
SKIPPED [1] tests/test_map.py:916: C Map is not available
SKIPPED [1] tests/test_map.py:1091: C Map is not available
SKIPPED [1] tests/test_map.py:1111: C Map is not available
SKIPPED [1] tests/test_map.py:1127: C Map is not available
SKIPPED [1] tests/test_map.py:1148: C Map is not available
SKIPPED [1] tests/test_map.py:1169: C Map is not available
SKIPPED [1] tests/test_map.py:1178: C Map is not available
SKIPPED [1] tests/test_map.py:1190: C Map is not available
SKIPPED [1] tests/test_map.py:1204: C Map is not available
SKIPPED [1] tests/test_map.py:1211: C Map is not available
SKIPPED [1] tests/test_map.py:1226: C Map is not available
SKIPPED [1] tests/test_map.py:950: C Map is not available
SKIPPED [1] tests/test_map.py:1231: C Map is not available
SKIPPED [1] tests/test_map.py:1260: C Map is not available
SKIPPED [1] tests/test_map.py:963: C Map is not available
SKIPPED [1] tests/test_map.py:973: C Map is not available
SKIPPED [1] tests/test_map.py:992: C Map is not available
SKIPPED [1] tests/test_map.py:1016: C Map is not available
SKIPPED [1] tests/test_map.py:1031: C Map is not available
SKIPPED [1] tests/test_map.py:1054: C Map is not available
SKIPPED [1] tests/test_map.py:1078: C Map is not available
SKIPPED [1] tests/test_map.py:1291: C Map is not available
SKIPPED [1] tests/test_map.py:1341: C Map is not available
SKIPPED [1] tests/test_map.py:167: C Map is not available
SKIPPED [1] tests/test_map.py:257: C Map is not available
SKIPPED [1] tests/test_map.py:674: C Map is not available
SKIPPED [1] tests/test_map.py:692: C Map is not available
SKIPPED [1] tests/test_map.py:849: C Map is not available
SKIPPED [1] tests/test_map.py:856: C Map is not available
SKIPPED [1] tests/test_map.py:868: C Map is not available
SKIPPED [1] tests/test_none_keys.py:293: C Map is not available
SKIPPED [1] tests/test_none_keys.py:461: C Map is not available
SKIPPED [1] tests/test_none_keys.py:62: C Map is not available
SKIPPED [1] tests/test_none_keys.py:108: C Map is not available
SKIPPED [1] tests/test_none_keys.py:159: C Map is not available
SKIPPED [1] tests/test_none_keys.py:251: C Map is not available
SKIPPED [1] tests/test_none_keys.py:42: C Map is not available
SKIPPED [1] tests/test_none_keys.py:373: C Map is not available
SKIPPED [1] tests/test_none_keys.py:86: C Map is not available
FAILED tests/test_mypy.py::ImmuMypyTest::testMypyImmu
=========================================================== 1 failed, 75 passed, 77 skipped, 1 warning in 14.43s ===========================================================
pytest-xprocess reminder::Be sure to terminate the started process by running 'pytest --xkill' if you have not explicitly done so in your fixture with 'xprocess.getinfo(<process_name>).terminate()'.

opened by kloczek 22

PyMapNoneTest.test_none_collisions fails on 32-bit x86 systems

When running the package's tests on 32-bit x86, I get the following failure:

$ pytest
=============================================================== test session starts ===============================================================
platform linux -- Python 3.7.9, pytest-5.4.2, py-1.8.0, pluggy-0.13.1
rootdir: /home/mgorny/immutables, inifile: pytest.ini, testpaths: tests
plugins: hypothesis-5.18.1, services-2.0.1, backports.unittest-mock-1.5
collected 152 items                                                                                                                               

tests/test_issue24.py .....sssssss
tests/test_map.py .............................................................sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss
tests/test_none_keys.py ......F..sssssssss

==================================================================== FAILURES =====================================================================
_______________________________________________________ PyMapNoneTest.test_none_collisions ________________________________________________________
Traceback (most recent call last):
  File "/home/mgorny/immutables/tests/test_none_keys.py", line 47, in test_none_collisions
    self.assertEqual(map_mask(c_hash, j*5), idx)
  File "/usr/lib/python3.7/unittest/case.py", line 852, in assertEqual
    assertion_func(first, second, msg=msg)
  File "/usr/lib/python3.7/unittest/case.py", line 845, in _baseAssertEqual
    raise self.failureException(msg)
AssertionError: 10 != 9
============================================================= short test summary info =============================================================
FAILED tests/test_none_keys.py::PyMapNoneTest::test_none_collisions - AssertionError: 10 != 9
==================================================== 1 failed, 74 passed, 77 skipped in 17.31s ====================================================

I've been able to bisect this to:

commit 913572c2ef8a4c948bb8b67ff2064d6920e313e7
Author: TIGirardi <[email protected]>
Date:   Mon May 18 00:58:10 2020 -0300

    Accept None as a key in pure python module (#42)

 immutables/map.py       |  31 +--
 tests/test_none_keys.py | 511 ++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 530 insertions(+), 12 deletions(-)
 create mode 100644 tests/test_none_keys.py

Original bug report: https://bugs.gentoo.org/739578

opened by mgorny 8

Typing overhaul
This PR aims to do three things:

Make use of type annotations Before, only _map was annotated, so the type checker (Pylance in my case) wasn't picking up on it. This is done using TYPE_CHECKING, which is available since Python 3.5.2.

Additional constraints when using **kwargs: Specifically, this is wrong:

m: "Map[int, int]" = Map(answer=42)

m: "Map[int, int]" = Map({1: 41}).update(answer=42)

so if **kwargs are used, the key type should be a subtype of str

Allowing more valid updates With dict or any other mutable mapping, this is wrong:

d: dict[int, int] = {1: 2} d["answer"] = 42

However, with Map, this is fine, it just produces a map of different type:

m1: "Map[int, int]" = Map({1: 2}) m2: "Map[int | str, int]" = m1.update({"answer": 42}) m3: "Map[int | str, int]" = m1.update(answer=42) m4: "Map[int, int | str]" = m1.update({4: "four"}) m5: "Map[int | str, int | str]" = m1.update({"four": "four"}) m6: "Map[int | str, int | str]" = m1.update(four="four")
opened by decorator-factory 7

Build broken on Python 3.10

https://github.com/python/cpython/pull/20429

  immutables/_map.c: In function ‘map_node_bitmap_new’:
  immutables/_map.c:574:19: error: lvalue required as left operand of assignment
    574 |     Py_SIZE(node) = size;
        |                   ^
  immutables/_map.c: In function ‘map_node_collision_new’:
  immutables/_map.c:1359:19: error: lvalue required as left operand of assignment
   1359 |     Py_SIZE(node) = size;
        |                   ^
  error: command '/usr/bin/gcc' failed with exit code 1

@vstinner If the motivation is to make PyObject* opaque in the limited ABI, then why did you also make this change in the non-limited ABI?

opened by njsmith 7

pythoncapi_compat.h is MIT licensed

The MIT license requires including the license and the copyright notice in copies of the software. This file was pulled directly from the upstream repo.

https://github.com/pythoncapi/pythoncapi_compat/blob/main/COPYING

opened by carlwgeorge 5
Refactor typings
Improve typing of __init__()

Update typing of Map-producing functions to produce the correct type

Update typing of other methods to more closely align with Mapping

Add protocol classes for unexposed data structures

Export protocol classes for ease of use in typed code

Update stub file to pass in mypy strict mode

fixes #54

I've taken the work in the typing overhaul PR and improved it as detailed above. The following passes using mypy in strict mode:

from immutables import Map from typing import Union m: Map[int, int] = Map() m1 = Map[int, int]({1: 2}) m2: Map[Union[int, str], int] = m1.update({"answer": 2}) m3: Map[Union[int, str], int] = m1.update(answer=2) m4: Map[int, Union[int, str]] = m1.update({4: "four"}) m5: Map[Union[int, str], Union[int, str]] = m1.update({"four": "four"}) m6: Map[Union[int, str], Union[int, str]] = m1.update(four="four") m7: Map[Union[int, str], Union[int, str, float]] = m1.update(m5, five=5.0) reveal_type(m1.update(m5, four=(4.0,)).update(five=5)) # Revealed type is 'immutables._map.Map[Union[builtins.int, builtins.str], Union[builtins.int, Tuple[builtins.float], builtins.str]]' reveal_type(m1.set('four', 'four').set((4.0,), (5.0,))) # Revealed type is 'immutables._map.Map[Union[builtins.int, builtins.str, Tuple[builtins.float]], Union[builtins.int, builtins.str, Tuple[builtins.float]]]'

There was discussion in #54 about restricting update() and other Map-producing functions to the key and value types of the original Map. I'm not exactly sure which is the best approach since the implementation allows update() to take different types for the key and value, however typing.Dict disallows this for dict even though dict.update() allows similar functionality as Map.update(). For now, I've left Map.update() similar to what was done in #54, but that can certainly be changed before merging.
opened by bryanforbes 5

Make repr more similar to other mapping types

Resolves #17

Python 3.8.1 (tags/v3.8.1:1b293b6, Dec 18 2019, 23:11:46) [MSC v.1916 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> from collections import ChainMap, OrderedDict, defaultdict
>>>
>>> d = {'one': 1, 'two': 2}
>>> d
{'one': 1, 'two': 2}
>>> ChainMap({'one': 1}, {'two': 2})
ChainMap({'one': 1}, {'two': 2})
>>> OrderedDict((('one', 1), ('two', 2)))
OrderedDict([('one', 1), ('two', 2)])
>>> dd = defaultdict(int)
>>> dd.update(d)
>>> dd
defaultdict(<class 'int'>, {'one': 1, 'two': 2})

opened by ofek 5

Apparent segfault in immutables.Map.__init__
We're getting an intermittent segfault in the contextvars library, on our MacOS CI: https://ci.cryptography.io/blue/rest/organizations/jenkins/pipelines/python-trio/pipelines/trio/branches/PR-575/runs/2/nodes/6/steps/33/log/?start=0

The crash-handler traceback shows it as happening on line 27 of contextvars/__init__.py, which seems to be:

self._data = immutables.Map()

So our current hypothesis is that immutables.Map() sometimes segfaults? Does that ring any bells?

We don't know how to reproduce it locally, but I believe that's the python.org build of 3.6.1.

Previous discussion: https://github.com/python-trio/trio/issues/200#issuecomment-408670447
opened by njsmith 5
Data from benchmark and plot do not match

Why is reguar dict faster than HAMT?

Plot does not seem to match with times that can be found alongside the banchmark code: https://gist.github.com/1st1/292e3f0bbe43bd65ff3256f80aa2637d

opened by curusarn 5

Unable to install from sdist: pyproject.toml [project] requires a name.

This started to happen since yesterday in some CI environments using python:3.10-bullseye image. However, the CI jobs using python:3.8-bullseye and python:3.9-bullseye don't fail.

I've seen this in two different project: one uses tox to manage the virtualenv, the other one uses poetry. I don't really know why they are preferring the source dist over the binary wheels.

  Downloading immutables-0.16.tar.gz (84 kB)
     ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 84.5/84.5 KB 12.3 MB/s eta 0:00:00
  Installing build dependencies: started
  Installing build dependencies: finished with status 'done'
  Getting requirements to build wheel: started
  Getting requirements to build wheel: finished with status 'error'
  error: subprocess-exited-with-error
  
  × Getting requirements to build wheel did not run successfully.
  │ exit code: 1
  ╰─> [1009 lines of output]
      /tmp/pip-build-env-7qjk9iks/overlay/lib/python3.10/site-packages/setuptools/config/pyprojecttoml.py:100: _ExperimentalProjectMetadata: Support for project metadata in `pyproject.toml` is still experimental and may be removed (or change) in future releases.
        warnings.warn(msg, _ExperimentalProjectMetadata)
      configuration error: `project` must contain ['name'] properties
      DESCRIPTION:
          Data structure for the **project** table inside ``pyproject.toml`` (as
          initially defined in :pep:`621`)
      
      GIVEN VALUE:
          {
              "requires-python": ">=3.6"
          }
      
      OFFENDING RULE: 'required'

opened by mvaled 3

Tests test_none_collisions in CMapNoneTest and PyMapNoneTest fail on armv7l

When building the package for OpenSUSE on armv7l architecture, I get:

[  304s] ======================================================================
[  304s] FAIL: test_none_collisions (test_none_keys.CMapNoneTest)
[  304s] ----------------------------------------------------------------------
[  304s] Traceback (most recent call last):
[  304s]   File "/home/abuild/rpmbuild/BUILD/immutables-0.14/tests/test_none_keys.py", line 47, in test_none_collisions
[  304s]     self.assertEqual(map_mask(c_hash, j*5), idx)
[  304s] AssertionError: 13 != 12
[  304s] 
[  304s] ======================================================================
[  304s] FAIL: test_none_collisions (test_none_keys.PyMapNoneTest)
[  304s] ----------------------------------------------------------------------
[  304s] Traceback (most recent call last):
[  304s]   File "/home/abuild/rpmbuild/BUILD/immutables-0.14/tests/test_none_keys.py", line 47, in test_none_collisions
[  304s]     self.assertEqual(map_mask(c_hash, j*5), idx)
[  304s] AssertionError: 13 != 12
[  304s] 
[  304s] ----------------------------------------------------------------------
[  304s] Ran 152 tests in 98.443s
[  304s] 
[  304s] FAILED (failures=2)

Full build log with all details

opened by mcepl 3

Add PEP 585 (__class_getitem__ -> GenericAlias) support
This commit add supports for PEP 585 on Python 3.9+.

This is useful for runtime introspection ( resolves #83 ).

For example, on Python 3.9+:

>>> immutables.Map[str, int] immutables._map.Map[int, str]

On Python 3.8-:

>>> immutables.Map[str, int] <class 'immutables.map.Map'>

This does not affect type checkers, as they do not utilize runtime introspection.

This is immediately useful for applications that would like to use type information for (de)serialization. Examples:

https://github.com/python-attrs/cattrs

https://github.com/konradhalas/dacite

Thank you for your work on this library (and PEP, to boot!).
opened by ToBeReplaced 0
Map type arguments aren't introspectible in runtime

Currently I don't see a way of getting the key and value types from a map type. Ideally, the Map.__class_getitem__ should return an object with __origin__ set to Map and __args__ set to a tuple of the key and value types, so that typing.get_origin() and typing.get_args() work with it.

Without this information, libraries like cattrs have no way of correctly serializing and deserializing Map instances.

opened by Tinche 0

Do you want my frozenset implemenation using this lib?

if you do here it is:

from typing import Iterable

import immutables

# Design choices:
# - Using a class to allow for typing
# - The class has no methods to ensure all logic is in the functions below.
# - The wrapped map is kept private.
# - To prevent the user from making subtle mistake, we override `__eq__` to raise an error.
# Corollaries:
# - Will not work with operators ootb, e.g. `in`, `==` or `len`.


class ImmutableSet:
    def __init__(self, inner):
        self._inner = inner

    def __eq__(self, _):
        raise NotImplementedError(
            "Use the functions in this module instead of operators.",
        )


def create(iterable: Iterable) -> ImmutableSet:
    return ImmutableSet(immutables.Map(map(lambda x: (x, None), iterable)))


EMPTY: ImmutableSet = create([])


def equals(s1: ImmutableSet, s2: ImmutableSet) -> bool:
    return s1._inner == s2._inner  # noqa: SF01


def length(set: ImmutableSet) -> int:
    return len(set._inner)  # noqa: SF01


def add(set: ImmutableSet, element) -> ImmutableSet:
    return ImmutableSet(set._inner.set(element, None))  # noqa: SF01


def remove(set: ImmutableSet, element) -> ImmutableSet:
    return ImmutableSet(set._inner.delete(element))  # noqa: SF01


def contains(set: ImmutableSet, element) -> bool:
    return element in set._inner  # noqa: SF01


def union(set1: ImmutableSet, set2: ImmutableSet) -> ImmutableSet:
    smaller, larger = sorted([set1, set2], key=length)
    return ImmutableSet(larger._inner.update(smaller._inner))  # noqa: SF01


def intersection(set1: ImmutableSet, set2: ImmutableSet) -> ImmutableSet:
    smaller, larger = sorted([set1, set2], key=length)
    for element in smaller._inner:  # noqa: SF01
        if not contains(larger, element):
            smaller = remove(smaller, element)
    return smaller

and tests:

import time


def test_add():
    assert immutable_set.equals(
        immutable_set.add(
            immutable_set.create([1, 2, 3]),
            4,
        ),
        immutable_set.create(
            [1, 2, 3, 4],
        ),
    )


def test_remove():
    assert immutable_set.equals(
        immutable_set.remove(
            immutable_set.create([1, 2, 3]),
            2,
        ),
        immutable_set.create([1, 3]),
    )


def test_contains():
    assert immutable_set.contains(immutable_set.create([1, 2, 3]), 3)


def test_not_contains():
    assert not immutable_set.contains(immutable_set.create([1, 2, 3]), 4)


def test_union():
    assert immutable_set.equals(
        immutable_set.union(
            immutable_set.create([1, 2, 3, 4]),
            immutable_set.create([1, 2, 3]),
        ),
        immutable_set.create([1, 2, 3, 4]),
    )


def _is_o_of_1(f, arg1, arg2):
    start = time.perf_counter()
    f(arg1, arg2)
    return time.perf_counter() - start < 0.0001


_large_number = 9999


def test_intersection():
    assert immutable_set.equals(
        immutable_set.intersection(
            immutable_set.create([1, 2]),
            immutable_set.create([2]),
        ),
        immutable_set.create([2]),
    )


def test_performance_sanity():
    assert not _is_o_of_1(
        immutable_set.union,
        immutable_set.create(range(_large_number)),
        immutable_set.create(range(_large_number)),
    )


def test_union_performance():
    assert _is_o_of_1(
        immutable_set.union,
        immutable_set.create(range(_large_number)),
        immutable_set.create(range(_large_number // 64, _large_number // 32)),
    )


def test_intersection_performance():
    assert _is_o_of_1(
        immutable_set.intersection,
        immutable_set.create(range(_large_number)),
        immutable_set.create(range(1)),
    )

opened by uriva 0

How to efficiently track and store deltas between two HAMTs
Ideally, I would like to be able to do

x = Map({'a': 2, 'c': 1}) y = x.update({'b': 3: 'c': 2) z = y - x # magic z == Map({'b': 3, 'c': 2})

Is there any particularly efficient way to do this in terms of memory and computational time? Ideally, I'd like z to share its data with y in the same way y shares its data with x. One way that comes to mind is

def diff(y, x): z = y for k, v in y.items(): if k in x and x[k] == v: z = z.delete('k') return z

But this is O(N log N) (for log N get/set). Is there a more efficient way to go about this?
opened by aeftimia 0
immutables._map.MapMutation is not iterable / does not implement items()

I am wondering if this is by design or because it hasn't been useful up till now.

My use-case is implementing a middleware type of cache. The cache subscribes to some external data that gets updated and tracks it, and it allows clients to get an immutable view of the cache. The cache can be a nested immutables.Map dictionary. What works is to call mutate and finish for each new piece of data that comes in (N times each if the updated key is at depth N), but this can be too slow when the cache receives a large batch of updates. Using a profiler, I see my code spending ~35% of the time processing the incoming data to be added to the cache and ~65% of the time in the mutate/finish calls.

What I would like to implement is a lazy-finish protocol that calls mutate on updates as needed but not finish. Instead, we traverse the cache and make any needed finish calls when the client requests a view into the cache. What is preventing me from realizing this implementation (I think) is that the immutables._map.MapMutation objects that are returned by the un-finished mutate calls, are not iterable and they don't implement items(), but I need to finish the inner MapMutation objects before I finish the outer ones.

As a nasty hack, I can finish() an outer MapMutation to get its keys and use them to find and recurse into any inner MapMutation values to finish those, before I call finish() a second time on the outer MapMutation to really finish it this time.

opened by atzannes 3

Releases(v0.19)

v0.19(Sep 14, 2022)

Changes

Support for Python 3.11
Source code(tar.gz)
Source code(zip)
v0.18(May 22, 2022)

Source code(tar.gz)
Source code(zip)
v0.17(Mar 26, 2022)
Fixes

Add missing name in table [project] in 'pyproject.toml'. (#78) (by @mvaled in 80b537f7 for #78)

Source code(tar.gz)
Source code(zip)
v0.16(Aug 7, 2021)
Updates

Refactor typings (by @bryanforbes in 39f9f0de and @msullivan in 4a175499)

Update Python 3.10 support, drop Python 3.5 (by @elprans in fa355239 and 189b959d)

Fixes

Fix test_none_collisions on 32-bit systems (#69) (by @elprans in fa355239 for #69)

Misc

Clarify the license of the included pythoncapi_compat.h header (by @elprans in 67c5edfb for #64)

Use cibuildwheel to build wheels (#70) (by @elprans in f671cb4d for #70)

Source code(tar.gz)
Source code(zip)
v0.15(Feb 10, 2021)
New Features

Add support for Python 3.10 and more tests (by @vstinner in 45105ecd for #46, @hukkinj1 in d7f3eebb, f0b4fd40)

Make __repr__ more similar to other mapping types (by @ofek in 8af15021 for #17)

Misc

Minor docs and CI fixes (by @MisterKeefe in 76e491cf for #32, @fantix in 1282379d for #39)

Source code(tar.gz)
Source code(zip)
v0.14(May 18, 2020)
Allow None to be used as key in pure-Python implementation.

Source code(tar.gz)
Source code(zip)
v0.13(May 13, 2020)
Bugfixes

Various improvements w.r.t. type annotations & typing support (by @hukkinj1)

Fix pure-Python implementation to accept keyword argument "col" correctly (by @hukkinj1)

Source code(tar.gz)
Source code(zip)
v0.12(Apr 23, 2020)
Bug Fixes

Fix the mutation API to maintain elements count correctly (#25, #24)

Source code(tar.gz)
Source code(zip)
v0.9(Apr 1, 2019)
Don't allow MapMutation.update() calls after the mutation is finished

Simplify MapMutation.exit() implementation

Source code(tar.gz)
Source code(zip)
v0.8(Dec 13, 2018)
Add new MapMutation.update() method that behaves like MutableMapping.update()

Make it faster to create a Map() from another Map()—it's now an O(1) operation.

update() method had a bug that could cause the update Map object to have a wrong number of elements.

Source code(tar.gz)
Source code(zip)
v0.7(Nov 20, 2018)
New Features

All new APIs are covered in the README file.

Allow Map objects to be constructed from other mappings: Map(a=1), or Map([('a', 1)]), or Map(dict(a=1)).

Implement Map.update() method.

Implement Map.mutate() and MapMutation API.

Make Map objects pickleable.

Make Map.keys(), Map.values(), and Map.items() proper dict-view like objects.

Source code(tar.gz)
Source code(zip)
v0.6(Jun 8, 2018)
Fixed a crash in Map constructor (C implementation)

Source code(tar.gz)
Source code(zip)
v0.5(May 1, 2018)
Reject keyword and positional arguments in new

Source code(tar.gz)
Source code(zip)
v0.4(Apr 3, 2018)
Breaking change: Map.delete() now raises a KeyError if a user deletes a missing key.

Add a pure-Python implementation to support PyPy.

Test coverage is now 100%.

Source code(tar.gz)
Source code(zip)
v0.3(Apr 2, 2018)
Implement Map.__repr__() and Map.__hash__()

Source code(tar.gz)
Source code(zip)

Owner

magicstack

Any sufficiently advanced software is indistinguishable from magic.

GitHub Repository

A mutable set that remembers the order of its entries. One of Python's missing data types.

An OrderedSet is a mutable data structure that is a hybrid of a list and a set. It remembers the order of its entries, and every entry has an index nu

173 Nov 28, 2022

Multidict is dict-like collection of key-value pairs where key might be occurred more than once in the container.

multidict Multidict is dict-like collection of key-value pairs where key might be occurred more than once in the container. Introduction HTTP Headers

325 Dec 27, 2022

pyprobables is a pure-python library for probabilistic data structures

pyprobables is a pure-python library for probabilistic data structures. The goal is to provide the developer with a pure-python implementation of common probabilistic data-structures to use in their

86 Dec 25, 2022

Webtesting for course Data Structures & Algorithms

Selenium job to automate queries to check last posts of Module Data Structures & Algorithms Web-testing for course Data Structures & Algorithms Struct

1 Dec 15, 2021

Simple spill-to-disk dictionary

Chest A dictionary that spills to disk. Chest acts likes a dictionary but it can write its contents to disk. This is useful in the following two occas

59 Dec 19, 2022

Al-Quran dengan Terjemahan Indonesia

Al-Quran Rofi Al-Quran dengan Terjemahan / Tafsir Jalalayn Instalasi Al-Quran Rofi untuk Archlinux untuk pengguna distro Archlinux dengan paket manage

4 Dec 20, 2021

A HDF5-based python pickle replacement

Hickle Hickle is an HDF5 based clone of pickle, with a twist: instead of serializing to a pickle file, Hickle dumps to an HDF5 file (Hierarchical Data

450 Dec 21, 2022

My notes on Data structure and Algos in golang implementation and python

My notes on DS and Algo Table of Contents Arrays LinkedList Trees Types of trees: Tree/Graph Traversal Algorithms Heap Priorty Queue Trie Graphs Graph

0 Feb 13, 2022

RLStructures is a library to facilitate the implementation of new reinforcement learning algorithms.

RLStructures is a lightweight Python library that provides simple APIs as well as data structures that make as few assumptions as possibl

262 Nov 18, 2022

A DSA repository but everything is in python.

DSA Status Contents A: Mathematics B: Bit Magic C: Recursion D: Arrays E: Searching F: Sorting G: Matrix H: Hashing I: String J: Linked List K: Stack

63 Dec 23, 2022

A simple tutorial to use tree-sitter to parse code into ASTs

A simple tutorial to use py-tree-sitter to parse code into ASTs. To understand what is tree-sitter, see https://github.com/tree-sitter/tree-sitter. Tr

7 Sep 17, 2022

Solutions for leetcode problems.

Leetcode-solution This is an repository for storring new algorithms that I am learning form the LeetCode for future use. Implemetations Two Sum (pytho

1 Jan 09, 2022

Python tree data library

Links Documentation PyPI GitHub Changelog Issues Contributors If you enjoy anytree Getting started Usage is simple. Construction from anytree impo

776 Dec 28, 2022

Programming of a spanning tree algorithm with Python : In depth first with a root node.

ST Algorithm Programming of a spanning tree algorithm with Python : In depth first with a root node. Description This programm reads informations abou

1 Dec 16, 2021

This Repository consists of my solutions in Python 3 to various problems in Data Structures and Algorithms

Problems and it's solutions. Problem solving, a great Speed comes with a good Accuracy. The more Accurate you can write code, the more Speed you will

1.3k Jan 01, 2023

A mutable set that remembers the order of its entries. One of Python's missing data types.

An OrderedSet is a mutable data structure that is a hybrid of a list and a set. It remembers the order of its entries, and every entry has an index number that can be looked up.

173 Nov 28, 2022

Final Project for Practical Python Programming and Algorithms for Data Analysis

Final Project for Practical Python Programming and Algorithms for Data Analysis (PHW2781L, Summer 2020) Redlining, Race-Exclusive Deed Restriction Lan

1 Jan 27, 2022

This repository is for adding codes of data structures and algorithms, leetCode, hackerrank etc solutions in different languages

DSA-Code-Snippet This repository is for adding codes of data structures and algorithms, leetCode, hackerrank etc solutions in different languages Cont

3 Oct 22, 2021

This repo represents all we learned and are learning in Data Structure course.

DataStructure Journey This repo represents all we learned and are learning in Data Structure course which is based on CLRS book and is being taught by

3 Jan 22, 2022

This repository contains code for CTF platform.

CTF-platform Repository for backend of CTF hosting website For starting the project first time : Clone the repo in which you have to work in your syst

3 Feb 18, 2022

A high-performance immutable mapping type for Python.

Related tags

Overview

immutables

Installation

API

Further development

License

Comments

Releases(v0.19)

v0.19(Sep 14, 2022)

Changes

v0.18(May 22, 2022)

v0.17(Mar 26, 2022)

Fixes

v0.16(Aug 7, 2021)

Updates

Fixes

Misc

v0.15(Feb 10, 2021)

New Features

Misc

v0.14(May 18, 2020)

v0.13(May 13, 2020)

v0.12(Apr 23, 2020)

Bug Fixes

v0.9(Apr 1, 2019)

v0.8(Dec 13, 2018)

v0.7(Nov 20, 2018)

New Features

v0.6(Jun 8, 2018)

v0.5(May 1, 2018)

v0.4(Apr 3, 2018)

v0.3(Apr 2, 2018)

Owner

magicstack

A mutable set that remembers the order of its entries. One of Python's missing data types.

Multidict is dict-like collection of key-value pairs where key might be occurred more than once in the container.

pyprobables is a pure-python library for probabilistic data structures

Webtesting for course Data Structures & Algorithms

Simple spill-to-disk dictionary

Al-Quran dengan Terjemahan Indonesia

A HDF5-based python pickle replacement

My notes on Data structure and Algos in golang implementation and python

RLStructures is a library to facilitate the implementation of new reinforcement learning algorithms.

A DSA repository but everything is in python.

A simple tutorial to use tree-sitter to parse code into ASTs

Solutions for leetcode problems.

Python tree data library

Programming of a spanning tree algorithm with Python : In depth first with a root node.

This Repository consists of my solutions in Python 3 to various problems in Data Structures and Algorithms

A mutable set that remembers the order of its entries. One of Python's missing data types.

Final Project for Practical Python Programming and Algorithms for Data Analysis

This repository is for adding codes of data structures and algorithms, leetCode, hackerrank etc solutions in different languages

This repo represents all we learned and are learning in Data Structure course.

This repository contains code for CTF platform.