A high-performance immutable mapping type for Python.

Related tags

Data Structures python immutable python3 hamt immutable-datastructures immutable-collections frozen
Overview

immutables

https://github.com/MagicStack/immutables/workflows/Tests/badge.svg?branch=master

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):

bench.png

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

    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

    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

    Typing overhaul

    This PR aims to do three things:

    1. 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.

    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

    1. 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

    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

    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

    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

    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__

    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

    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.

    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

    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

    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

    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?

    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

    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()

    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)

  • v0.18(May 22, 2022)

  • v0.17(Mar 26, 2022)

  • 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)

  • 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)

  • v0.9(Apr 1, 2019)

  • 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)

  • v0.5(May 1, 2018)

  • 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)

Owner
magicstack
Any sufficiently advanced software is indistinguishable from magic.
magicstack
GitHub
Array is a functional mutable sequence inheriting from Python's built-in list.

funct.Array Array is a functional mutable sequence inheriting from Python's built-in list. Array provides 100+ higher-order methods and more functiona

null 182 Nov 21, 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

Shubhashish Dixit 63 Dec 23, 2022
Common sorting algorithims in Python

This a Github Repository with code for my attempts for commonly used sorting algorithims, tested on a list with 3000 randomly generated numbers.

Pratham Prasoon 14 Sep 2, 2021
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 work.

Tyler Barrus 86 Dec 25, 2022
Python collections that are backended by sqlite3 DB and are compatible with the built-in collections

sqlitecollections Python collections that are backended by sqlite3 DB and are compatible with the built-in collections Installation $ pip install git+

Takeshi OSOEKAWA 11 Feb 3, 2022
This repository is a compilation of important Data Structures and Algorithms based on Python.

Python DSA ?? This repository is a compilation of important Data Structures and Algorithms based on Python. Please make seperate folders for different

Bhavya Verma 27 Oct 29, 2022
Leetcode solutions - All algorithms implemented in Python 3 (for education)

Leetcode solutions - All algorithms implemented in Python 3 (for education)

Vineet Dhaimodker 3 Oct 21, 2022
nocasedict - A case-insensitive ordered dictionary for Python

nocasedict - A case-insensitive ordered dictionary for Python Overview Class NocaseDict is a case-insensitive ordered dictionary that preserves the or

PyWBEM Projects 2 Dec 12, 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

SAMIR PAUL 1.3k Jan 1, 2023
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

Chia Yong Kang 0 Feb 13, 2022
Python library for doing things with Grid-like structures

gridthings Python library for doing things with Grid-like structures Development This project uses poetry for dependency management, pre-commit for li

Matt Kafonek 2 Dec 21, 2021
A Python library for electronic structure pre/post-processing

PyProcar PyProcar is a robust, open-source Python library used for pre- and post-processing of the electronic structure data coming from DFT calculati

Romero Group 124 Dec 7, 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

Mathieu Lamon 1 Dec 16, 2021
A Python dictionary implementation designed to act as an in-memory cache for FaaS environments

faas-cache-dict A Python dictionary implementation designed to act as an in-memory cache for FaaS environments. Formally you would describe this a mem

Juan 3 Dec 13, 2022
Data Structure With Python

Data-Structure-With-Python- Python programs also include in this repo Stack A stack is a linear data structure that stores items in a Last-In/First-Ou

Sumit Nautiyal 2 Jan 9, 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

Aislyn Schalck 1 Jan 27, 2022
Basic sort and search algorithms written in python.

Basic sort and search algorithms written in python. These were all developed as part of my Computer Science course to demonstrate understanding so they aren't 100% efficent

Ben Jones 0 Dec 14, 2022
A Python implementation of red-black trees

Python red-black trees A Python implementation of red-black trees. This code was originally copied from programiz.com, but I have made a few tweaks to

Emily Dolson 7 Oct 20, 2022
SSL_SLAM2: Lightweight 3-D Localization and Mapping for Solid-State LiDAR (mapping and localization separated) ICRA 2021

SSL_SLAM2 Lightweight 3-D Localization and Mapping for Solid-State LiDAR (Intel Realsense L515 as an example) This repo is an extension work of SSL_SL

Wang Han 王晗 1.3k Jan 8, 2023
Docker image with Uvicorn managed by Gunicorn for high-performance FastAPI web applications in Python 3.6 and above with performance auto-tuning. Optionally with Alpine Linux.

Supported tags and respective Dockerfile links python3.8, latest (Dockerfile) python3.7, (Dockerfile) python3.6 (Dockerfile) python3.8-slim (Dockerfil

Sebastián Ramírez 2.1k Dec 31, 2022