iddqd 0.3.5

Maps where keys borrow from values, including bijective and trijective maps.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337

<!-- cargo-sync-rdme title [[ -->
# iddqd
<!-- cargo-sync-rdme ]] -->
<!-- cargo-sync-rdme badge [[ -->
![License: MIT OR Apache-2.0](https://img.shields.io/crates/l/iddqd.svg?)
[![crates.io](https://img.shields.io/crates/v/iddqd.svg?logo=rust)](https://crates.io/crates/iddqd)
[![docs.rs](https://img.shields.io/docsrs/iddqd.svg?logo=docs.rs)](https://docs.rs/iddqd)
[![Rust: ^1.81.0](https://img.shields.io/badge/rust-^1.81.0-93450a.svg?logo=rust)](https://doc.rust-lang.org/cargo/reference/manifest.html#the-rust-version-field)
<!-- cargo-sync-rdme ]] -->
<!-- cargo-sync-rdme rustdoc [[ -->
Maps where keys are borrowed from values.

This crate consists of several map types, collectively called **ID maps**:

* [`IdOrdMap`](https://docs.rs/iddqd/0.3.5/iddqd/id_ord_map/imp/struct.IdOrdMap.html): A B-Tree based map where keys are borrowed from values.
* [`IdHashMap`](https://docs.rs/iddqd/0.3.5/iddqd/id_hash_map/imp/struct.IdHashMap.html): A hash map where keys are borrowed from values.
* [`BiHashMap`](https://docs.rs/iddqd/0.3.5/iddqd/bi_hash_map/imp/struct.BiHashMap.html): A bijective (1:1) hash map with two keys, borrowed from
  values.
* [`TriHashMap`](https://docs.rs/iddqd/0.3.5/iddqd/tri_hash_map/imp/struct.TriHashMap.html): A trijective (1:1:1) hash map with three keys, borrowed
  from values.

## Usage

* Pick your ID map type.
* Depending on the ID map type, implement [`IdOrdItem`](https://docs.rs/iddqd/0.3.5/iddqd/id_ord_map/trait_defs/trait.IdOrdItem.html), [`IdHashItem`](https://docs.rs/iddqd/0.3.5/iddqd/id_hash_map/trait_defs/trait.IdHashItem.html),
  [`BiHashItem`](https://docs.rs/iddqd/0.3.5/iddqd/bi_hash_map/trait_defs/trait.BiHashItem.html), or [`TriHashItem`](https://docs.rs/iddqd/0.3.5/iddqd/tri_hash_map/trait_defs/trait.TriHashItem.html) for your value type.
* Store values in the ID map type.

### Features

This crate was built out a practical need for map types, and addresses
issues encountered using Rust’s default map types in practice at Oxide.

* Keys are retrieved from values, not stored separately from them. Separate
  storage has been a recurring pain point in our codebases: if keys are
  duplicated within values, it’s proven to be hard to maintain consistency
  between keys and values. This crate addresses that need.
* Keys may be borrowed from values, which allows for more flexible
  implementations. (They don’t have to be borrowed, but they can be.)
* There’s no `insert` method; insertion must be through either
  `insert_overwrite` or `insert_unique`. You must pick an insertion
  behavior.
* For hash maps, the default hasher is [`foldhash`](https://docs.rs/foldhash/0.1.5/foldhash/index.html), which is much faster
  than SipHash. However, foldhash does *not provide the same level of HashDoS
  resistance* as SipHash. If that is important to you, you can use a different
  hasher. (Disable the `default-hasher` feature to require a hash
  builder type parameter to be passed in.)
* The serde implementations reject duplicate keys.

We’ve also sometimes needed to index a set of data by more than one key, or
perhaps map one key to another. For that purpose, this crate provides
[`BiHashMap`](https://docs.rs/iddqd/0.3.5/iddqd/bi_hash_map/imp/struct.BiHashMap.html) and [`TriHashMap`](https://docs.rs/iddqd/0.3.5/iddqd/tri_hash_map/imp/struct.TriHashMap.html).

* [`BiHashMap`](https://docs.rs/iddqd/0.3.5/iddqd/bi_hash_map/imp/struct.BiHashMap.html) has two keys, and provides a bijection (1:1 relationship)
  between the keys.
* [`TriHashMap`](https://docs.rs/iddqd/0.3.5/iddqd/tri_hash_map/imp/struct.TriHashMap.html) has three keys, and provides a trijection (1:1:1
  relationship) between the keys.

As a consequence of the general API structure, maps can have arbitrary
non-key data associated with them as well.

### Examples

An example for [`IdOrdMap`](https://docs.rs/iddqd/0.3.5/iddqd/id_ord_map/imp/struct.IdOrdMap.html):

````rust
use iddqd::{IdOrdItem, IdOrdMap, id_upcast};

#[derive(Debug)]
struct User {
    name: String,
    age: u8,
}

// Implement IdOrdItem so the map knows how to get the key from the value.
impl IdOrdItem for User {
    // The key type can borrow from the value.
    type Key<'a> = &'a str;

    fn key(&self) -> Self::Key<'_> {
        &self.name
    }

    id_upcast!();
}

let mut users = IdOrdMap::<User>::new();

// You must pick an insertion behavior. insert_unique returns an error if
// the key already exists.
users.insert_unique(User { name: "Alice".to_string(), age: 30 }).unwrap();
users.insert_unique(User { name: "Bob".to_string(), age: 35 }).unwrap();

// Lookup by name:
assert_eq!(users.get("Alice").unwrap().age, 30);
assert_eq!(users.get("Bob").unwrap().age, 35);

// Iterate over users:
for user in &users {
    println!("User {}: {}", user.name, user.age);
}
````

Keys don’t have to be borrowed from the value. For smaller `Copy` types,
it’s recommended that you use owned keys. Here’s an example of using
[`IdOrdMap`](https://docs.rs/iddqd/0.3.5/iddqd/id_ord_map/imp/struct.IdOrdMap.html) with a small integer key:

````rust
struct Record {
    id: u32,
    data: String,
}

impl IdOrdItem for Record {
    // The key type is small, so an owned key is preferred.
    type Key<'a> = u32;

    fn key(&self) -> Self::Key<'_> {
        self.id
    }

    id_upcast!();
}

// ...
````

An example for [`IdHashMap`](https://docs.rs/iddqd/0.3.5/iddqd/id_hash_map/imp/struct.IdHashMap.html), showing a complex borrowed key. Here,
“complex” means that the key is not a reference itself, but a struct that
returns references to more than one field from the value.

````rust
use iddqd::{IdHashItem, IdHashMap, id_upcast};

#[derive(Debug)]
struct Artifact {
    name: String,
    version: String,
    data: Vec<u8>,
}

// The key type is a borrowed form of the name and version. It needs to
// implement `Eq + Hash`.
#[derive(Eq, Hash, PartialEq)]
struct ArtifactKey<'a> {
    name: &'a str,
    version: &'a str,
}

impl IdHashItem for Artifact {
    // The key type can borrow from the value.
    type Key<'a> = ArtifactKey<'a>;

    fn key(&self) -> Self::Key<'_> {
        ArtifactKey { name: &self.name, version: &self.version }
    }

    id_upcast!();
}

let mut artifacts = IdHashMap::<Artifact>::new();

// Add artifacts to the map.
artifacts
    .insert_unique(Artifact {
        name: "artifact1".to_owned(),
        version: "1.0".to_owned(),
        data: b"data1".to_vec(),
    })
    .unwrap();
artifacts
    .insert_unique(Artifact {
        name: "artifact2".to_owned(),
        version: "1.0".to_owned(),
        data: b"data2".to_vec(),
    })
    .unwrap();

// Look up artifacts by name and version.
assert_eq!(
    artifacts
        .get(&ArtifactKey { name: "artifact1", version: "1.0" })
        .unwrap()
        .data,
    b"data1",
);
````

For more examples, see the
[examples](https://github.com/oxidecomputer/iddqd/tree/main/crates/iddqd/examples)
and [extended
examples](https://github.com/oxidecomputer/iddqd/tree/main/crates/iddqd-extended-examples/examples)
directories.

#### `Equivalent` and `Comparable`

An important feature of the standard library’s maps is that they allow any
borrowed form of the key type to be used for lookups; for example, a
`HashMap<String, T>` type can be looked up with a `&str` key. This is done
through the [`Borrow`] trait.

But the [`Borrow`] trait is a bit too restrictive for complex keys such as
`ArtifactKey` above, requiring workarounds such as [dynamic
dispatch](https://github.com/sunshowers-code/borrow-complex-key-example). To
address this, the crates.io ecosystem has standardized on the [`Equivalent`](https://docs.rs/equivalent/1.0.2/equivalent/trait.Equivalent.html)
and [`Comparable`](https://docs.rs/equivalent/1.0.2/equivalent/trait.Comparable.html) traits as generalizations of `Borrow`. The map types in
this crate require these traits.

For a key type `T::Key<'_>` and a lookup type `L`:

* The hash map types require `L: Hash + Equivalent<T::Key<'_>>`. Also, `L`
  must hash in the same way as `T::Key<'_>`. Typically, this is done by
  ensuring that enum variants and struct fields are in the same
  order[^proptest].
* [`IdOrdMap`](https://docs.rs/iddqd/0.3.5/iddqd/id_ord_map/imp/struct.IdOrdMap.html) requires `L: Comparable<T::Key<'_>>`, which in turn requires
  `Equivalent<T::Key<'_>>`. (There’s no need for `L` to implement `Ord` or
  `Eq` itself.)

[^proptest]: We recommend that you test this with e.g. a property-based
    test: see [this
    example](https://github.com/sunshowers-code/borrow-complex-key-example/blob/a6f17699/src/lib.rs#L233).

Continuing the `ArtifactKey` example from above, we can perform a lookup
using a key of this owned form:

````rust
use equivalent::Equivalent;

// This is an owned form of ArtifactKey. The fields are in the same
// order as ArtifactKey's fields, so it hashes the same way.
#[derive(Hash)]
struct OwnedArtifactKey {
    name: String,
    version: String,
}

impl Equivalent<ArtifactKey<'_>> for OwnedArtifactKey {
    fn equivalent(&self, other: &ArtifactKey<'_>) -> bool {
        self.name == other.name && self.version == other.version
    }
}

// Now you can use OwnedArtifactKey to look up the artifact.
let owned_key = OwnedArtifactKey {
    name: "artifact1".to_owned(),
    version: "1.0".to_owned(),
};
assert_eq!(artifacts.get(&owned_key).unwrap().data, b"data1",);
````

There’s a blanket implementation of [`Equivalent`](https://docs.rs/equivalent/1.0.2/equivalent/trait.Equivalent.html) and [`Comparable`](https://docs.rs/equivalent/1.0.2/equivalent/trait.Comparable.html) for
[`Borrow`], so if your type already implements [`Borrow`], there aren’t any
extra steps to take.

## Testing

This crate is validated through a combination of:

* Unit tests
* Property-based tests using a naive map as an oracle
* Chaos tests for several kinds of buggy `Eq` and `Ord` implementations
* Miri tests for unsafe code

If you see a gap in testing, new tests are welcome. Thank you!

## No-std compatibility

Most of this crate is no-std compatible, though [`alloc`](https://doc.rust-lang.org/nightly/alloc/index.html) is required.

The [`IdOrdMap`](https://docs.rs/iddqd/0.3.5/iddqd/id_ord_map/imp/struct.IdOrdMap.html) type is not currently no-std compatible due to its use of a
thread-local. This thread-local is just a way to work around a limitation in
std’s `BTreeMap` API, though. Either a custom B-Tree implementation, or a
platform-specific notion of thread locals, would suffice to make
[`IdOrdMap`](https://docs.rs/iddqd/0.3.5/iddqd/id_ord_map/imp/struct.IdOrdMap.html) no-std compatible.

## Optional features

* `serde`: Enables serde support for all ID map types. *Not enabled by
  default.*
* `schemars08`: Enables [`schemars`] support for all ID map types,
  including support for [automatic replacement] through [`typify`] or
  [`dropshot`]. *Not enabled by default.*
* `daft`: Enables [`daft`](https://docs.rs/daft/0.1.3/daft/index.html) support for all ID map types. *Not enabled by
  default.*
* `std`: Enables std support. *Enabled by default.*
* `default-hasher`: Enables the `DefaultHashBuilder` type. Disable this
  feature to require a hash builder type parameter to be passed into
  [`IdHashMap`](https://docs.rs/iddqd/0.3.5/iddqd/id_hash_map/imp/struct.IdHashMap.html), [`BiHashMap`](https://docs.rs/iddqd/0.3.5/iddqd/bi_hash_map/imp/struct.BiHashMap.html), and [`TriHashMap`](https://docs.rs/iddqd/0.3.5/iddqd/tri_hash_map/imp/struct.TriHashMap.html). *Enabled by default.*
* `allocator-api2`: Enables support for custom allocators via the
  [`allocator_api2`](https://docs.rs/allocator-api2/0.2.21/allocator_api2/index.html) crate. Both global and scoped/arena allocators
  (such as `bumpalo`) are supported. Custom allocators are not currently
  supported by `IdOrdMap`.

## Related work

* [`bimap`](https://docs.rs/bimap) provides a bijective map, but does not
  have a way to associate arbitrary values with each pair of keys. However,
  it does support an ordered map type without the need for std.

* [`multi_index_map`](https://crates.io/crates/multi_index_map) provides
  maps with arbitrary indexes on fields, and is more flexible than this
  crate. However, it doesn’t expose generic traits for map types, and it
  requires key types to be `Clone`. In `iddqd`, we pick a somewhat different
  point in the design space, but we think `multi_index_map` is also great.

* In general, this is similar to relational database records with
  indexes. For sufficiently complex use cases, consider an embedded
  database like [SQLite](https://www.sqlite.org/), or even a networked
  database like [PostgreSQL](https://www.postgresql.org/). `iddqd` is a
  good fit for simple in-memory caches of data stored in these databases.

## Minimum supported Rust version (MSRV)

This crate’s MSRV is **Rust 1.81**. In general we aim for 6 months of Rust
compatibility.

## What does iddqd mean?

The name `iddqd` is a reference to [a cheat
code](https://doomwiki.org/wiki/Doom_cheat_codes) in the classic video game
*Doom*. It has `id` in the name, and is short and memorable.

[`Borrow`]: https://doc.rust-lang.org/nightly/core/borrow/trait.Borrow.html
[`schemars`]: https://crates.io/crates/schemars
[automatic replacement]: https://github.com/oxidecomputer/iddqd/blob/main/crates/iddqd-extended-examples/examples/typify-types.rs
[`typify`]: https://crates.io/crates/typify
[`dropshot`]: https://crates.io/crates/dropshot
<!-- cargo-sync-rdme ]] -->

## License

This project is available under the terms of either the [Apache 2.0 license](LICENSE-APACHE) or the [MIT
license](LICENSE-MIT).

Portions adapted from [The Rust Programming Language](https://github.com/rust-lang/rust) and used under the MIT and Apache 2.0 licenses. The Rust Programming Language is (c) The Rust Project Contributors.

Portions adapted from [hashbrown](https://github.com/rust-lang/hashbrown) and used under the MIT and Apache 2.0 licenses. hashbrown is (c) 2016-2025 Amanieu d'Antras and others.