iddqd

Added

• from_iter_unique constructors on IdHashMap, BiHashMap, and TriHashMap, matching the existing IdOrdMap::from_iter_unique. These build a map from an iterator and, rather than overwriting, return an error on the first item that conflicts with an already-inserted one.

  Because a value in a BiHashMap or TriHashMap can conflict on more than one key at once, the error reports every distinct existing item it collides with (up to two for BiHashMap and up to three for TriHashMap).

Changed

• MSRV updated to Rust 1.86.

Fixed

• Deserialization no longer preallocates based on an unbounded size hint. Length-prefixed formats such as bincode and postcard derive their size hint from the input, so a small hostile payload claiming a huge number of elements could previously cause an excessively large allocation before any element was read. Preallocation is now capped at 1 MiB worth of items, matching what serde does for the standard library's collections.

• The insert_overwrite path on IdHashMap no longer aborts when an allocation fails, matching the existing guarantee on BiHashMap and TriHashMap. Instead, it results in a catchable panic. (The map is left unchanged, similar to BiHashMap and TriHashMap.)

  Note that BTreeMap::insert_overwrite will abort on allocation failure, because it calls into std which doesn't have an equivalent to HashMap::try_reserve.

Other improvements

• The insert paths now do fewer redundant checks for duplicates. Thanks izuzak for your first contribution!

Added

• from_iter_unique constructors on IdHashMap, BiHashMap, and TriHashMap, matching the existing IdOrdMap::from_iter_unique. These build a map from an iterator and, rather than overwriting, return an error on the first item that conflicts with an already-inserted one.

  Because a value in a BiHashMap or TriHashMap can conflict on more than one key at once, the error reports every distinct existing item it collides with (up to two for BiHashMap and up to three for TriHashMap).

Changed

• MSRV updated to Rust 1.86.

Fixed

• Deserialization no longer preallocates based on an unbounded size hint. Length-prefixed formats such as bincode and postcard derive their size hint from the input, so a small hostile payload claiming a huge number of elements could previously cause an excessively large allocation before any element was read. Preallocation is now capped at 1 MiB worth of items, matching what serde does for the standard library's collections.

• The insert_overwrite path on IdHashMap no longer aborts when an allocation fails, matching the existing guarantee on BiHashMap and TriHashMap. Instead, it results in a catchable panic. (The map is left unchanged, similar to BiHashMap and TriHashMap.)

  Note that BTreeMap::insert_overwrite will abort on allocation failure, because it calls into std which doesn't have an equivalent to HashMap::try_reserve.

Other improvements

• The insert paths now do fewer redundant checks for duplicates. Thanks izuzak for your first contribution!

Added

• iddqd's core invariants are now formally verified under adversarial Hash and Ord impls using the Soteria symbolic executor. No new bugs were found during this process.

  The formal verification is broad (covers all possible adversarial return values) but bounded-depth; it acts as a complement to the existing layers of randomized testing, which are less broad but generate much deeper operation sequences.

  For more information on our validation philosophy, see this Oxide blog entry.

• Expanded examples for BiHashMap's Entry.

Added

• iddqd's core invariants are now formally verified under adversarial Hash and Ord impls using the Soteria symbolic executor. No new bugs were found during this process.

  The formal verification is broad (covers all possible adversarial return values) but bounded-depth; it acts as a complement to the existing layers of randomized testing, which are less broad but generate much deeper operation sequences.

  For more information on our validation philosophy, see this Oxide blog entry.

• Expanded examples for BiHashMap's Entry.

Changed

• The FromIterator implementations now reserve capacity at the start of the operation.

Changed

• The FromIterator implementations now reserve capacity at the start of the operation.

Fixed

• The insert_overwrite paths on BiHashMap and TriHashMap are now atomic in case user code panics. Thanks to SG-devel for your first contribution!

Fixed

• The insert_overwrite paths on BiHashMap and TriHashMap are now atomic in case user code panics. Thanks to SG-devel for your first contribution!

Fixed

• The retain callbacks no longer permit the RefMut to be stashed outside them. This is technically a breaking change, but is being treated as a soundness bugfix.
• A number of soundness and resilience fixes for pathological implementations. These were found through a combination of human-driven analysis, example-based tests with Miri, chaos testing using fault injection with proptest, and adversarial code review from Claude Opus 4.7 and GPT-5.5. In particular, iddqd now more consistently preserves internal map state across panics in user code by using patterns like prepare-then-commit, index-based cleanup, cached hashes, and careful ordering of user-code execution relative to internal mutations.

Changed

• MSRV updated to Rust 1.85.

Fixed

• The retain callbacks no longer permit the RefMut to be stashed outside them. This is technically a breaking change, but is being treated as a soundness bugfix.
• A number of soundness and resilience fixes for pathological implementations. These were found through a combination of human-driven analysis, example-based tests with Miri, chaos testing using fault injection with proptest, and adversarial code review from Claude Opus 4.7 and GPT-5.5. In particular, iddqd now more consistently preserves internal map state across panics in user code by using patterns like prepare-then-commit, index-based cleanup, cached hashes, and careful ordering of user-code execution relative to internal mutations.

Changed

• MSRV updated to Rust 1.85.

Fixed

• Fixed a logic bug in TriHashMap::remove_unique, when key1 matches, and one of key2 and key3 matches, but not the other.

Fixed

• Fixed a logic bug in TriHashMap::remove_unique, when key1 matches, and one of key2 and key3 matches, but not the other.

Changed

• The internal implementation for item storage has been changed to use a linear slot-based buffer, resulting in 2-3x performance improvements for most workloads.
• The maps now have a limit of u32::MAX (4 294 967 295) elements at any given time. This limit is very unlikely to be reached in practice.

Fixed

• All mutation methods for IdHashMap and IdOrdMap are now panic-safe, in the sense that a panic in user code will not corrupt the map. This does not currently extend to BiHashMap and TriHashMap

Added

• Many more unit and property-based tests covering various kinds of pathological user implementations. We now have high confidence that arbitraily buggy user implementations (as long as they're in safe Rust) will not result in undefined behavior.

Changed

• The internal implementation for item storage has been changed to use a linear slot-based buffer, resulting in 2-3x performance improvements for most workloads.
• The maps now have a limit of u32::MAX (4 294 967 295) elements at any given time. This limit is very unlikely to be reached in practice.

Fixed

• All mutation methods for IdHashMap and IdOrdMap are now panic-safe, in the sense that a panic in user code will not corrupt the map. This does not currently extend to BiHashMap and TriHashMap

Added

• Many more unit and property-based tests covering various kinds of pathological user implementations. We now have high confidence that arbitraily buggy user implementations (as long as they're in safe Rust) will not result in undefined behavior.

Fixed

• Fixed a rehashing bug in hash map reserve and shrink-to-fit methods. (Due to an oversight, these methods were previously not part of our property-based tests. Now they are. Sorry about that!)

Fixed

• Fixed a rehashing bug in hash map reserve and shrink-to-fit methods. (Due to an oversight, these methods were previously not part of our property-based tests. Now they are. Sorry about that!)

Added

• Capacity management methods for all map types:
  • reserve(&mut self, additional: usize) reserves capacity for at least additional more elements.
  • shrink_to_fit(&mut self) shrinks capacity to fit the current length.
  • shrink_to(&mut self, min_capacity: usize) shrinks capacity to at least min_capacity.
  • try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError>: fallible capacity reservation for hash maps (IdHashMap, BiHashMap, TriHashMap).
• New TryReserveError type in the errors module for reporting allocation failures.

Notes

• For IdOrdMap, the reserve and shrink methods only affect item storage. The internal BTreeSet used for item ordering does not support capacity control.
• IdOrdMap does not provide try_reserve, since the underlying BTreeSet does not expose fallible reservation operations.

Fixed

• Fixed an instance of potential unsoundness in retain.

Changed

The Extend implementations now pre-reserve capacity based on the iterator's size_hint.

Added

• Capacity management methods for all map types:
  • reserve(&mut self, additional: usize) reserves capacity for at least additional more elements.
  • shrink_to_fit(&mut self) shrinks capacity to fit the current length.
  • shrink_to(&mut self, min_capacity: usize) shrinks capacity to at least min_capacity.
  • try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError>: fallible capacity reservation for hash maps (IdHashMap, BiHashMap, TriHashMap).
• New TryReserveError type in the errors module for reporting allocation failures.

Notes

• For IdOrdMap, the reserve and shrink methods only affect item storage. The internal BTreeSet used for item ordering does not support capacity control.
• IdOrdMap does not provide try_reserve, since the underlying BTreeSet does not expose fallible reservation operations.

Fixed

• Fixed an instance of potential unsoundness in retain.

Changed

The Extend implementations now pre-reserve capacity based on the iterator's size_hint.

Added

• clear methods for all map types to remove all items from the map.
• Optionally, serialize ID maps as maps (JSON objects) rather than sequences (JSON arrays):
  • New IdHashMapAsMap, BiHashMapAsMap, TriHashMapAsMap, and IdOrdMapAsMap marker types to use with #[serde(with = ...)].
  • The default deserializer for each map now accepts both maps and sequences.

Changed

• Documentation improvements for serde implementations.

Added

• retain methods that allow filtering items in place based on a predicate.
• IdOrdMap::first, first_entry, last, last_entry, pop_first, and pop_last methods for accessing entries at the beginning and end of the map.
• BiHashMap::with_hasher and TriHashMap::with_hasher are now const fn.

Changed

• Reduced memory footprint for BiHashMap and TriHashMap.

Fixed

Replaced obsolete doc_auto_cfg with doc_cfg, to fix Rust nightly builds with the doc_cfg flag enabled.

Changed

• iddqd now depends on serde_core rather than serde. This allows iddqd's compilation to be parallelized with serde_derive.
• Internal dependency updates: foldhash updated to 0.2, and hashbrown updated to 0.16.

Added

The following methods are now const fn:

• IdOrdMap::new
• IdHashMap::with_hasher

Fixed

The type definitions for IdHashMap, BiHashMap, TriHashMap, and IdOrdMap no longer require IdHashItem, BiHashItem, TriHashItem, and IdOrdItem, respectively. This matches the standard library's HashMap and BTreeMap type definitions which don't require Hash + Eq or Ord bounds.

Thanks to aatifsyed for your first contribution!

Fixed

id_ord_map::RefMut's reborrow method now works if the underlying IdOrdItem is non-'static.

Added

• For the optional daft feature, the map Diff types now implement fmt::Debug.

Miscellaneous

• Several documentation fixes.

Added

• New proptest feature adds strategy and Arbitrary implementations for map types.

Fixed

• iddqd is now compatible with schemars's preserve_order feature. Thanks Sh3Rm4n for your first contribution!

Changed

• Relaxed Debug requirement to only require that T::Key<'a>: fmt::Debug, not for<'k> T::Key<'k>: fmt::Debug. This allows items with borrowed data to compile in more cases.
• Relaxed Hash requirement for IdOrdMap get_mut and related APIs in a similar fashion.

Added

• New feature schemars08 adds support for generating JSON schemas.

Added

• New macros id_hash_map, bi_hash_map, tri_hash_map, and id_ord_map allow easy construction of literal macros. These macros use insert_unique, so they panic if duplicate keys are encountered.

Changed

• The id_upcast, bi_upcast and tri_upcast macros now have a Self: 'long bound, allowing them to be used for non-'static items.
• Minimized dependency list, removing the dependency on derive-where, debug-ignore, and serde's derive feature. iddqd no longer depends on any proc macros.

Added

• A lot of new documentation. Most functions now have doctests.

Fixed

• Serde implementations no longer do internal buffering.
• Serde implementations now reserve capacity if the size hint is available; thanks @aatifsyed for your first contribution!
• A few unnecessary bounds have been loosened.

Added

• The hash map types now support custom hashers.
• With the new allocator-api2 feature (enabled by default), the hash map types now support custom allocators, including on stable. See the bumpalo-alloc example.
• Added some documentation explaining iteration order.
• Added a note in the README and lib.rs that small copyable keys like integers are best returned as owned ones.

Changed

• Dropped the Ord requirement for Comparable keys. (The Hash requirement for Equivalent continues to be required.)

Added

• Re-export equivalent::Equivalent and equivalent::Comparable.

Changed

• Lookups now use equivalent::Equivalent or equivalent::Comparable, which are strictly more general than Borrow.
• get_mut and remove methods no longer require the key type; the borrow checker limitation has been worked around.

Fixed

• MapLeaf<'a, T>'s Clone and Copy no longer require T to be Clone or Copy. (MapLeaf is just a couple of references, so this is never necessary.)

Added

• Extend implementations.

Changed

• Daft implementations for BiHashMap and TriHashMap changed to also allow diffing by individual keys.

Added

• BiHashMap and TriHashMap now have a remove_unique method which removes an item uniquely indexed by all keys.

Changed

• upcast macros are now annotated with #[inline], since they're trivial.

Added

• Daft implementations with the new daft feature.
• BiHashItem implementations for reference types like &'a T and Box<T>.

Initial release.

<!-- next-url --> [0.4.6]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.4.6 [0.4.5]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.4.5 [0.4.4]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.4.4 [0.4.3]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.4.3 [0.4.2]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.4.2 [0.4.1]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.4.1 [0.4.0]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.4.0 [0.3.18]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.3.18 [0.3.17]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.3.17 [0.3.16]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.3.16 [0.3.15]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.3.15 [0.3.14]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.3.14 [0.3.13]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.3.13 [0.3.12]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.3.12 [0.3.11]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.3.11 [0.3.10]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.3.10 [0.3.9]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.3.9 [0.3.8]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.3.8 [0.3.7]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.3.7 [0.3.6]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.3.6 [0.3.5]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.3.5 [0.3.4]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.3.4 [0.3.3]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.3.3 [0.3.2]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.3.2 [0.3.1]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.3.1 [0.3.0]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.3.0 [0.2.1]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.2.1 [0.2.0]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.2.0 [0.1.2]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.1.2 [0.1.1]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.1.1 [0.1.0]: https://github.com/oxidecomputer/iddqd/releases/tag/iddqd-0.1.0