[][src]Crate pour


crates.io Downloads Documentation Pipeline status codecov License: MIT

pour is an implementation of an immutable IdMap: it maps bitvector IDs to values using a radix trie.

Since these IdMaps are immutable, they can share a lot of data between them, and hash-consing can be used to increase the degree of sharing between IdMaps. More interestingly, this data structure is designed to support asymptotically fast set operations on hash-consed IdMaps, including:

  • Unions, intersections, (symmetric) differences, and complements
  • Subset/superset checks

The best part is, the more memory shared, the faster these operations become in the general case (though the specialized ptr variants of these operations may return incorrect values on non hash-consed, i.e. maximally shared, inputs!) To allow user customized hash-consing strategies, the internal Arcs behind this data structure can be exposed as opaque objects which the user may manipulate using the ConsCtx trait. Alternatively, () implements SetCtx with no consing, and there are helpers to perform set operations without consing.

There are also some nice implementation details (which may change), including:

  • IdMap<K, V> and hence IdSet<K> are the size of a pointer.
  • NonEmptyIdMap<K, V> and hence NonEmptyIdSet<K> are the size of a pointer and null-pointer optimized, i.e. Option<NonEmptySet<T>> is also the size of a pointer.

Right now, the feature-set is deliberately kept somewhat minimal, as pour has a particular use case (the rain intermediate representation). But if I have time and/or anyone wants to contribute, all kinds of things can be added! Examples of potential future features include

  • Map not just from integer keys but from integer ranges, with similar efficiency
  • Union maps of different types

pour is currently implemented without any unsafe, though that may change. We do, however use the non-standard elysees Arc implementation (a fork of Servo's triomphe by the author) to avoid weak reference counts.

NOTE: "levels" are currently not yet supported! Returning a level number greater than 0 will cause a panic!

Contributions, questions, and issues are welcome! Please file issues at https://gitlab.com/tekne/pour, and contact the author at jad.ghalayini@gtc.ox.ac.uk for any other queries.



A simple cons context implemented using a hashbrown HashMap for efficient access to the raw entry API, which is very helpful for hash consing.


Types and traits for functionally describing mutation of immutable maps



An immutable, optionally hash-consed pointer-sized map from small integer keys to arbitrary data


An iterator over an IdMap


A borrowed iterator over an IdMap


An IdMap's internal data.



A binary result, which can be either the left value, the right value, or a new value


A unary result, which can be either a new value or the old value



A trait implemented by objects which can perform hash-consing on a map's internal data


An n-bit pattern


A key which can be used in a radix trie

Type Definitions


An immutable, optionally hash-consed pointer-sized set of small integer keys