swh_graph/
mph.rs

1// Copyright (C) 2024-2026  The Software Heritage developers
2// See the AUTHORS file at the top-level directory of this distribution
3// License: GNU General Public License version 3, or any later version
4// See top-level LICENSE file for more information
5
6//! Abstraction over possible Minimal-perfect hash functions
7
8use std::fs::File;
9use std::io::BufReader;
10use std::path::Path;
11
12use anyhow::{bail, Context, Result};
13use ph::fmph::GOFunction;
14use ph::seeds::TwoToPowerBitsStatic;
15
16use crate::graph::NodeId;
17use crate::java_compat::mph::gov::GOVMPH;
18use crate::map::{MappedPermutation, Permutation};
19use crate::utils::suffix_path;
20use crate::SWHID;
21
22/// Minimal-perfect hash function over [`SWHID`].
23///
24/// See [`DynMphf`] which wraps all implementer structs in an enum to dynamically choose
25/// which MPH algorithm to use with less overhead than `dyn SwhidMphf`.
26pub trait SwhidMphf {
27    fn num_keys(&self) -> usize;
28
29    /// Hashes a SWHID's binary representation
30    #[inline(always)]
31    fn hash_array(&self, swhid: &[u8; SWHID::BYTES_SIZE]) -> Option<NodeId> {
32        self.hash_swhid(&(*swhid).try_into().ok()?)
33    }
34
35    /// Hashes a SWHID's textual representation
36    fn hash_str(&self, swhid: impl AsRef<str>) -> Option<NodeId>;
37
38    /// Hashes a SWHID's textual representation
39    fn hash_str_array(&self, swhid: &[u8; 50]) -> Option<NodeId>;
40
41    /// Hashes a [`SWHID`]
42    #[inline(always)]
43    fn hash_swhid(&self, swhid: &SWHID) -> Option<NodeId> {
44        self.hash_str(swhid.to_string())
45    }
46}
47
48#[diagnostic::on_unimplemented(
49    label = "requires LoadableSwhidMphf (not just SwhidMphf)",
50    note = "swh-graph v7.0.0 split some methods of the SwhidMphf trait into a new LoadableSwhidMphf trait."
51)]
52/// Sub-trait of [`SwhidMphf`] for "concrete" MPHF implementations
53pub trait LoadableSwhidMphf: SwhidMphf {
54    type WithMappedPermutation: SwhidMphf;
55
56    fn load(basepath: impl AsRef<Path>) -> Result<Self>
57    where
58        Self: Sized;
59
60    /// Given the base path of the MPH, mmaps the associated .order file and returns it
61    fn with_mapped_permutation(
62        self,
63        basepath: impl AsRef<Path>,
64    ) -> Result<Self::WithMappedPermutation>;
65}
66
67/// Composition of a MPHF and a permutation
68pub struct PermutedMphf<MPHF: SwhidMphf, P: Permutation> {
69    mphf: MPHF,
70    permutation: P,
71}
72
73impl<MPHF: SwhidMphf, P: Permutation> SwhidMphf for PermutedMphf<MPHF, P> {
74    #[inline(always)]
75    fn num_keys(&self) -> usize {
76        self.mphf.num_keys()
77    }
78
79    #[inline(always)]
80    fn hash_array(&self, swhid: &[u8; SWHID::BYTES_SIZE]) -> Option<NodeId> {
81        self.mphf
82            .hash_array(swhid)
83            .and_then(|id| self.permutation.get(id))
84    }
85
86    #[inline(always)]
87    fn hash_str(&self, swhid: impl AsRef<str>) -> Option<NodeId> {
88        self.mphf
89            .hash_str(swhid)
90            .and_then(|id| self.permutation.get(id))
91    }
92
93    #[inline(always)]
94    fn hash_str_array(&self, swhid: &[u8; 50]) -> Option<NodeId> {
95        self.mphf
96            .hash_str_array(swhid)
97            .and_then(|id| self.permutation.get(id))
98    }
99
100    #[inline(always)]
101    fn hash_swhid(&self, swhid: &SWHID) -> Option<NodeId> {
102        self.mphf
103            .hash_swhid(swhid)
104            .and_then(|id| self.permutation.get(id))
105    }
106}
107
108/// Trivial implementation of [`SwhidMphf`] that stores the list of items in a vector
109pub struct VecMphf {
110    pub swhids: Vec<SWHID>,
111}
112
113impl SwhidMphf for VecMphf {
114    #[inline(always)]
115    fn num_keys(&self) -> usize {
116        self.swhids.len()
117    }
118
119    fn hash_str(&self, swhid: impl AsRef<str>) -> Option<NodeId> {
120        swhid
121            .as_ref()
122            .try_into()
123            .ok()
124            .and_then(|swhid: SWHID| self.hash_swhid(&swhid))
125    }
126
127    fn hash_str_array(&self, swhid: &[u8; 50]) -> Option<NodeId> {
128        String::from_utf8(swhid.to_vec())
129            .ok()
130            .and_then(|swhid| self.hash_str(swhid))
131    }
132
133    fn hash_swhid(&self, swhid: &SWHID) -> Option<NodeId> {
134        self.swhids.iter().position(|item| item == swhid)
135    }
136}
137
138impl LoadableSwhidMphf for GOVMPH {
139    type WithMappedPermutation = PermutedMphf<Self, MappedPermutation>;
140
141    fn load(basepath: impl AsRef<Path>) -> Result<Self>
142    where
143        Self: Sized,
144    {
145        let path = suffix_path(basepath, ".cmph");
146        GOVMPH::load(&path).with_context(|| format!("Could not load {}", path.display()))
147    }
148
149    fn with_mapped_permutation(
150        self,
151        basepath: impl AsRef<Path>,
152    ) -> Result<Self::WithMappedPermutation> {
153        let suffix = ".order"; // not .cmph.order because .order predates "modular" MPH functions
154        let permutation = MappedPermutation::load_unchecked(&suffix_path(&basepath, suffix))?;
155        Ok(PermutedMphf {
156            mphf: self,
157            permutation,
158        })
159    }
160}
161
162impl SwhidMphf for GOVMPH {
163    #[inline(always)]
164    fn num_keys(&self) -> usize {
165        self.size() as usize
166    }
167
168    #[inline(always)]
169    fn hash_str(&self, swhid: impl AsRef<str>) -> Option<NodeId> {
170        Some(self.get_byte_array(swhid.as_ref().as_bytes()) as usize)
171    }
172
173    #[inline(always)]
174    fn hash_str_array(&self, swhid: &[u8; 50]) -> Option<NodeId> {
175        Some(self.get_byte_array(swhid) as usize)
176    }
177}
178
179#[cfg(feature = "pthash")]
180mod swhid_pthash {
181    use super::*;
182
183    use pthash::{DictionaryDictionary, Minimal, MurmurHash2_128, PartitionedPhf, Phf};
184
185    pub struct SwhidPthash(pub PartitionedPhf<Minimal, MurmurHash2_128, DictionaryDictionary>);
186
187    impl SwhidPthash {
188        pub fn load(path: impl AsRef<Path>) -> Result<Self>
189        where
190            Self: Sized,
191        {
192            let path = path.as_ref();
193            PartitionedPhf::load(path)
194                .with_context(|| format!("Could not load {}", path.display()))
195                .map(SwhidPthash)
196        }
197    }
198
199    /// Newtype to make SWHID hashable by PTHash
200    pub(crate) struct HashableSWHID<T: AsRef<[u8]>>(pub T);
201
202    impl<T: AsRef<[u8]>> pthash::Hashable for HashableSWHID<T> {
203        type Bytes<'a>
204            = &'a T
205        where
206            T: 'a;
207        fn as_bytes(&self) -> Self::Bytes<'_> {
208            &self.0
209        }
210    }
211
212    impl LoadableSwhidMphf for SwhidPthash {
213        type WithMappedPermutation = PermutedMphf<Self, MappedPermutation>;
214
215        fn load(basepath: impl AsRef<Path>) -> Result<Self>
216        where
217            Self: Sized,
218        {
219            let path = suffix_path(basepath, ".pthash");
220            SwhidPthash::load(path)
221        }
222
223        fn with_mapped_permutation(
224            self,
225            basepath: impl AsRef<Path>,
226        ) -> Result<Self::WithMappedPermutation> {
227            let suffix = ".pthash.order";
228            let permutation = MappedPermutation::load_unchecked(&suffix_path(&basepath, suffix))?;
229            Ok(PermutedMphf {
230                mphf: self,
231                permutation,
232            })
233        }
234    }
235
236    impl SwhidMphf for SwhidPthash {
237        #[inline(always)]
238        fn num_keys(&self) -> usize {
239            self.0.num_keys() as usize
240        }
241
242        #[inline(always)]
243        fn hash_str(&self, swhid: impl AsRef<str>) -> Option<NodeId> {
244            Some(self.0.hash(HashableSWHID(swhid.as_ref().as_bytes())) as usize)
245        }
246
247        #[inline(always)]
248        fn hash_str_array(&self, swhid: &[u8; 50]) -> Option<NodeId> {
249            Some(self.0.hash(HashableSWHID(swhid)) as usize)
250        }
251    }
252}
253
254#[cfg(feature = "pthash")]
255pub use swhid_pthash::*;
256
257pub struct SwhidFmphgo(pub GOFunction<TwoToPowerBitsStatic<4>, TwoToPowerBitsStatic<1>>);
258
259impl SwhidFmphgo {
260    pub fn load(path: impl AsRef<Path>) -> Result<Self>
261    where
262        Self: Sized,
263    {
264        let path = path.as_ref();
265        let file =
266            File::open(path).with_context(|| format!("Could not open {}", path.display()))?;
267        ph::fmph::GOFunction::read(&mut BufReader::new(file))
268            .with_context(|| format!("Could not load {}", path.display()))
269            .map(SwhidFmphgo)
270    }
271}
272
273impl LoadableSwhidMphf for SwhidFmphgo {
274    type WithMappedPermutation = PermutedMphf<Self, MappedPermutation>;
275
276    fn load(basepath: impl AsRef<Path>) -> Result<Self>
277    where
278        Self: Sized,
279    {
280        let path = suffix_path(basepath, ".fmphgo");
281        SwhidFmphgo::load(path)
282    }
283
284    fn with_mapped_permutation(
285        self,
286        basepath: impl AsRef<Path>,
287    ) -> Result<Self::WithMappedPermutation> {
288        let suffix = ".fmphgo.order";
289        let permutation = MappedPermutation::load_unchecked(&suffix_path(&basepath, suffix))?;
290        Ok(PermutedMphf {
291            mphf: self,
292            permutation,
293        })
294    }
295}
296
297impl SwhidMphf for SwhidFmphgo {
298    #[inline(always)]
299    fn num_keys(&self) -> usize {
300        self.0.len()
301    }
302
303    #[inline(always)]
304    fn hash_str(&self, swhid: impl AsRef<str>) -> Option<NodeId> {
305        self.0
306            .get(swhid.as_ref().as_bytes())
307            .and_then(|hash| usize::try_from(hash).ok())
308    }
309
310    #[inline(always)]
311    fn hash_str_array(&self, swhid: &[u8; 50]) -> Option<NodeId> {
312        self.0
313            .get(swhid.as_ref())
314            .and_then(|hash| usize::try_from(hash).ok())
315    }
316}
317
318/// Enum of possible implementations of [`SwhidMphf`].
319///
320/// Loads either [`SwhidPthash`] or [`GOVMPH`]
321/// depending on which file is available at the given path.
322pub enum DynMphf {
323    Fmphgo(SwhidFmphgo),
324    #[cfg(feature = "pthash")]
325    Pthash(SwhidPthash),
326    GOV(GOVMPH),
327}
328
329impl std::fmt::Debug for DynMphf {
330    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
331        match self {
332            DynMphf::Fmphgo(_) => write!(f, "DynMphf::Fmphgo(_)"),
333            #[cfg(feature = "pthash")]
334            DynMphf::Pthash(_) => write!(f, "DynMphf::Pthash(_)"),
335            DynMphf::GOV(_) => write!(f, "DynMphf::GOV(_)"),
336        }
337    }
338}
339
340impl From<GOVMPH> for DynMphf {
341    #[inline(always)]
342    fn from(value: GOVMPH) -> DynMphf {
343        DynMphf::GOV(value)
344    }
345}
346
347#[cfg(feature = "pthash")]
348impl From<SwhidPthash> for DynMphf {
349    #[inline(always)]
350    fn from(value: SwhidPthash) -> DynMphf {
351        DynMphf::Pthash(value)
352    }
353}
354
355impl From<SwhidFmphgo> for DynMphf {
356    #[inline(always)]
357    fn from(value: SwhidFmphgo) -> DynMphf {
358        DynMphf::Fmphgo(value)
359    }
360}
361
362impl LoadableSwhidMphf for DynMphf {
363    type WithMappedPermutation = PermutedDynMphf;
364
365    fn load(basepath: impl AsRef<Path>) -> Result<Self> {
366        let basepath = basepath.as_ref();
367
368        let gov_path = suffix_path(basepath, ".cmph");
369        if gov_path.exists() {
370            return LoadableSwhidMphf::load(basepath)
371                .map(Self::GOV)
372                .with_context(|| format!("Could not load {}", gov_path.display()));
373        }
374
375        let fmphgo_path = suffix_path(basepath, ".fmphgo");
376        if fmphgo_path.exists() {
377            return LoadableSwhidMphf::load(basepath)
378                .map(Self::Fmphgo)
379                .with_context(|| format!("Could not load {}", fmphgo_path.display()));
380        }
381
382        let pthash_path = suffix_path(basepath, ".pthash");
383        if pthash_path.exists() {
384            #[cfg(not(feature = "pthash"))]
385            bail!(
386                "Cannot load MPHF {} because pthash support is disabled. Recompile swh-graph with --features pthash.",
387                pthash_path.display()
388            );
389            #[cfg(feature = "pthash")]
390            return LoadableSwhidMphf::load(basepath)
391                .map(Self::Pthash)
392                .with_context(|| format!("Could not load {}", pthash_path.display()));
393        }
394
395        bail!(
396            "Cannot load MPH function, neither {}, {}, nor {} exists.",
397            fmphgo_path.display(),
398            pthash_path.display(),
399            gov_path.display()
400        );
401    }
402
403    fn with_mapped_permutation(
404        self,
405        basepath: impl AsRef<Path>,
406    ) -> Result<Self::WithMappedPermutation> {
407        match self {
408            Self::Fmphgo(mphf) => mphf
409                .with_mapped_permutation(basepath)
410                .map(PermutedDynMphf::Fmphgo),
411            #[cfg(feature = "pthash")]
412            Self::Pthash(mphf) => mphf
413                .with_mapped_permutation(basepath)
414                .map(PermutedDynMphf::Pthash),
415            Self::GOV(mphf) => mphf
416                .with_mapped_permutation(basepath)
417                .map(PermutedDynMphf::GOV),
418        }
419    }
420}
421
422impl SwhidMphf for DynMphf {
423    #[inline(always)]
424    fn num_keys(&self) -> usize {
425        match self {
426            Self::Fmphgo(mphf) => mphf.num_keys(),
427            #[cfg(feature = "pthash")]
428            Self::Pthash(mphf) => mphf.num_keys(),
429            Self::GOV(mphf) => mphf.num_keys(),
430        }
431    }
432
433    #[inline(always)]
434    fn hash_array(&self, swhid: &[u8; SWHID::BYTES_SIZE]) -> Option<NodeId> {
435        match self {
436            Self::Fmphgo(mphf) => mphf.hash_array(swhid),
437            #[cfg(feature = "pthash")]
438            Self::Pthash(mphf) => mphf.hash_array(swhid),
439            Self::GOV(mphf) => mphf.hash_array(swhid),
440        }
441    }
442
443    #[inline(always)]
444    fn hash_str(&self, swhid: impl AsRef<str>) -> Option<NodeId> {
445        match self {
446            Self::Fmphgo(mphf) => mphf.hash_str(swhid),
447            #[cfg(feature = "pthash")]
448            Self::Pthash(mphf) => mphf.hash_str(swhid),
449            Self::GOV(mphf) => mphf.hash_str(swhid),
450        }
451    }
452
453    #[inline(always)]
454    fn hash_str_array(&self, swhid: &[u8; 50]) -> Option<NodeId> {
455        match self {
456            Self::Fmphgo(mphf) => mphf.hash_str_array(swhid),
457            #[cfg(feature = "pthash")]
458            Self::Pthash(mphf) => mphf.hash_str_array(swhid),
459            Self::GOV(mphf) => mphf.hash_str_array(swhid),
460        }
461    }
462
463    #[inline(always)]
464    fn hash_swhid(&self, swhid: &SWHID) -> Option<NodeId> {
465        match self {
466            Self::Fmphgo(mphf) => mphf.hash_swhid(swhid),
467            #[cfg(feature = "pthash")]
468            Self::Pthash(mphf) => mphf.hash_swhid(swhid),
469            Self::GOV(mphf) => mphf.hash_swhid(swhid),
470        }
471    }
472}
473
474/// [`DynMphf`] composed with a permutation
475pub enum PermutedDynMphf {
476    Fmphgo(<SwhidFmphgo as LoadableSwhidMphf>::WithMappedPermutation),
477    #[cfg(feature = "pthash")]
478    Pthash(<SwhidPthash as LoadableSwhidMphf>::WithMappedPermutation),
479    GOV(<GOVMPH as LoadableSwhidMphf>::WithMappedPermutation),
480}
481
482impl SwhidMphf for PermutedDynMphf {
483    #[inline(always)]
484    fn num_keys(&self) -> usize {
485        match self {
486            Self::Fmphgo(mphf) => mphf.num_keys(),
487            #[cfg(feature = "pthash")]
488            Self::Pthash(mphf) => mphf.num_keys(),
489            Self::GOV(mphf) => mphf.num_keys(),
490        }
491    }
492
493    #[inline(always)]
494    fn hash_array(&self, swhid: &[u8; SWHID::BYTES_SIZE]) -> Option<NodeId> {
495        match self {
496            Self::Fmphgo(mphf) => mphf.hash_array(swhid),
497            #[cfg(feature = "pthash")]
498            Self::Pthash(mphf) => mphf.hash_array(swhid),
499            Self::GOV(mphf) => mphf.hash_array(swhid),
500        }
501    }
502
503    #[inline(always)]
504    fn hash_str(&self, swhid: impl AsRef<str>) -> Option<NodeId> {
505        match self {
506            Self::Fmphgo(mphf) => mphf.hash_str(swhid),
507            #[cfg(feature = "pthash")]
508            Self::Pthash(mphf) => mphf.hash_str(swhid),
509            Self::GOV(mphf) => mphf.hash_str(swhid),
510        }
511    }
512
513    #[inline(always)]
514    fn hash_str_array(&self, swhid: &[u8; 50]) -> Option<NodeId> {
515        match self {
516            Self::Fmphgo(mphf) => mphf.hash_str_array(swhid),
517            #[cfg(feature = "pthash")]
518            Self::Pthash(mphf) => mphf.hash_str_array(swhid),
519            Self::GOV(mphf) => mphf.hash_str_array(swhid),
520        }
521    }
522
523    #[inline(always)]
524    fn hash_swhid(&self, swhid: &SWHID) -> Option<NodeId> {
525        match self {
526            Self::Fmphgo(mphf) => mphf.hash_swhid(swhid),
527            #[cfg(feature = "pthash")]
528            Self::Pthash(mphf) => mphf.hash_swhid(swhid),
529            Self::GOV(mphf) => mphf.hash_swhid(swhid),
530        }
531    }
532}
swh_graph/mph.rs

swh_graph/
mph.rs
