forest/cid_collections/
mod.rs

1// Copyright 2019-2026 ChainSafe Systems
2// SPDX-License-Identifier: Apache-2.0, MIT
3pub mod hash_map;
4pub mod hash_set;
5mod small_cid_vec;
6pub use hash_map::CidHashMap;
7pub use hash_set::{CidHashSet, CidHashSetLike, FileBackedCidHashSet};
8use imp::{CidV1DagCborBlake2b256, Uncompactable};
9pub use small_cid_vec::{SmallCid, SmallCidNonEmptyVec};
10
11/// The core primitive for saving space in this module.
12///
13/// CIDs contain a significant amount of static data (such as version, codec, hash identifier, hash
14/// length).
15///
16/// Nearly all Filecoin CIDs are `V1`,`DagCbor` encoded, and hashed with `Blake2b256` (which has a hash
17/// length of 256 bits (32 bytes)).
18/// Naively representing such a CID requires 96 bytes but the non-static portion is only
19/// 32 bytes, represented as [`CidV1DagCborBlake2b256`].
20///
21/// In collections, choose to store only 32 bytes where possible.
22///
23/// Note that construction of CIDs should always go through this type, to ensure
24/// - canonicalization
25/// - the contract of [`Uncompactable`]
26///
27/// ```
28/// assert_eq!(std::mem::size_of::<cid::Cid>(), 96);
29/// ```
30///
31/// If other types of CID become popular, they should be added to this `enum`.
32#[derive(Debug, Clone, Copy, Hash, Eq, PartialEq, Ord, PartialOrd)]
33enum MaybeCompactedCid {
34    Compact(CidV1DagCborBlake2b256),
35    /// MUST NOT overlap with the above.
36    Uncompactable(Uncompactable),
37}
38
39// Hide the constructors for [`Uncompactable`] and [`CidV1DagCborBlake2b256`]
40mod imp {
41    use super::*;
42    use crate::utils::multihash::prelude::*;
43    use cid::{Cid, multihash::Multihash};
44    use get_size2::GetSize;
45    #[cfg(test)]
46    use {crate::utils::db::CborStoreExt as _, quickcheck::Arbitrary};
47
48    #[derive(Debug, Clone, Copy, Hash, Eq, PartialEq, Ord, PartialOrd, GetSize)]
49    #[repr(transparent)]
50    pub struct CidV1DagCborBlake2b256 {
51        digest: [u8; Self::WIDTH],
52    }
53
54    impl CidV1DagCborBlake2b256 {
55        const WIDTH: usize = 32;
56
57        pub fn digest(&self) -> &[u8; Self::WIDTH] {
58            &self.digest
59        }
60    }
61
62    #[cfg(test)]
63    impl Arbitrary for CidV1DagCborBlake2b256 {
64        fn arbitrary(g: &mut quickcheck::Gen) -> Self {
65            Self {
66                digest: std::array::from_fn(|_ix| u8::arbitrary(g)),
67            }
68        }
69    }
70
71    #[test]
72    fn width() {
73        assert_eq!(
74            MultihashCode::Blake2b256.digest(&[]).size() as usize,
75            CidV1DagCborBlake2b256::WIDTH,
76        );
77    }
78
79    impl TryFrom<Cid> for CidV1DagCborBlake2b256 {
80        type Error = &'static str;
81
82        fn try_from(value: Cid) -> Result<Self, Self::Error> {
83            if value.version() == cid::Version::V1
84                && value.codec() == fvm_ipld_encoding::DAG_CBOR
85                && let Ok(small_hash) = value.hash().resize()
86            {
87                let (code, digest, size) = small_hash.into_inner();
88                if code == u64::from(MultihashCode::Blake2b256) && size as usize == Self::WIDTH {
89                    return Ok(Self { digest });
90                }
91            }
92            Err("cannot be compacted")
93        }
94    }
95
96    impl From<CidV1DagCborBlake2b256> for Cid {
97        fn from(value: CidV1DagCborBlake2b256) -> Self {
98            let CidV1DagCborBlake2b256 { digest } = value;
99            Cid::new_v1(
100                fvm_ipld_encoding::DAG_CBOR,
101                Multihash::wrap(MultihashCode::Blake2b256.into(), digest.as_slice())
102                    .expect("could not round-trip compacted CID"),
103            )
104        }
105    }
106
107    #[derive(
108        Debug, Clone, Copy, Hash, Eq, PartialEq, Ord, PartialOrd, GetSize, derive_more::Deref,
109    )]
110    #[repr(transparent)]
111    pub struct Uncompactable {
112        #[get_size(ignore)]
113        inner: Cid,
114    }
115
116    /// [`Uncompactable`] can only be created through [`MaybeCompactedCid`], since
117    /// that type defines the canonical conversion
118    impl From<Uncompactable> for Cid {
119        fn from(value: Uncompactable) -> Self {
120            value.inner
121        }
122    }
123
124    impl From<Cid> for MaybeCompactedCid {
125        fn from(value: Cid) -> Self {
126            match value.try_into() {
127                Ok(compact) => Self::Compact(compact),
128                Err(_) => Self::Uncompactable(Uncompactable { inner: value }),
129            }
130        }
131    }
132
133    impl From<MaybeCompactedCid> for Cid {
134        fn from(value: MaybeCompactedCid) -> Self {
135            match value {
136                MaybeCompactedCid::Compact(compact) => compact.into(),
137                MaybeCompactedCid::Uncompactable(Uncompactable { inner }) => inner,
138            }
139        }
140    }
141
142    #[test]
143    fn compactable() {
144        let cid = Cid::new(
145            cid::Version::V1,
146            fvm_ipld_encoding::DAG_CBOR,
147            MultihashCode::Blake2b256.digest("blake".as_bytes()),
148        )
149        .unwrap();
150        assert!(matches!(cid.into(), MaybeCompactedCid::Compact(_)));
151    }
152
153    #[test]
154    fn default() {
155        let cid = crate::db::MemoryDB::default()
156            .put_cbor_default(&())
157            .unwrap();
158        assert!(
159            matches!(cid.into(), MaybeCompactedCid::Compact(_)),
160            "the default encoding is no longer v1+dagcbor+blake2b.
161            consider adding the new default CID type to [`MaybeCompactCid`]"
162        );
163    }
164
165    #[test]
166    fn uncompactable_get_size() {
167        let i = Uncompactable {
168            inner: Cid::default(),
169        };
170        assert_eq!(i.get_size(), std::mem::size_of_val(&i.inner));
171    }
172}
173
174#[cfg(test)]
175mod tests {
176    use super::*;
177    use cid::Cid;
178    use quickcheck::Arbitrary;
179
180    impl Arbitrary for MaybeCompactedCid {
181        fn arbitrary(g: &mut quickcheck::Gen) -> Self {
182            // bump the odds of a CID being compact
183            let compact = MaybeCompactedCid::Compact(CidV1DagCborBlake2b256::arbitrary(g));
184            let maybe_compact = Self::from(Cid::arbitrary(g));
185            *g.choose(&[compact, maybe_compact]).unwrap()
186        }
187    }
188
189    #[quickcheck_macros::quickcheck]
190    fn cid_via_maybe_compacted_cid(before: Cid) {
191        let via = MaybeCompactedCid::from(before);
192        let after = Cid::from(via);
193        assert_eq!(before, after);
194    }
195}
forest/cid_collections/mod.rs

forest/cid_collections/
mod.rs
