gix_hash/
prefix.rs

1use std::cmp::Ordering;
2
3use crate::{oid, ObjectId, Prefix};
4
5/// The error returned by [`Prefix::new()`].
6#[derive(Debug, thiserror::Error)]
7#[allow(missing_docs)]
8pub enum Error {
9    #[error(
10        "The minimum hex length of a short object id is {}, got {hex_len}",
11        Prefix::MIN_HEX_LEN
12    )]
13    TooShort { hex_len: usize },
14    #[error("An object of kind {object_kind} cannot be larger than {} in hex, but {hex_len} was requested", object_kind.len_in_hex())]
15    TooLong { object_kind: crate::Kind, hex_len: usize },
16}
17
18///
19pub mod from_hex {
20    /// The error returned by [`Prefix::from_hex`][super::Prefix::from_hex()].
21    #[derive(Debug, Eq, PartialEq, thiserror::Error)]
22    #[allow(missing_docs)]
23    pub enum Error {
24        #[error(
25            "The minimum hex length of a short object id is {}, got {hex_len}",
26            super::Prefix::MIN_HEX_LEN
27        )]
28        TooShort { hex_len: usize },
29        #[error("An id cannot be larger than {} chars in hex, but {hex_len} was requested", crate::Kind::longest().len_in_hex())]
30        TooLong { hex_len: usize },
31        #[error("Invalid hex character")]
32        Invalid,
33    }
34}
35
36impl Prefix {
37    /// The smallest allowed prefix length below which chances for collisions are too high even in small repositories.
38    pub const MIN_HEX_LEN: usize = 4;
39
40    /// Create a new instance by taking a full `id` as input and truncating it to `hex_len`.
41    ///
42    /// For instance, with `hex_len` of 7 the resulting prefix is 3.5 bytes, or 3 bytes and 4 bits
43    /// wide, with all other bytes and bits set to zero.
44    pub fn new(id: &oid, hex_len: usize) -> Result<Self, Error> {
45        if hex_len > id.kind().len_in_hex() {
46            Err(Error::TooLong {
47                object_kind: id.kind(),
48                hex_len,
49            })
50        } else if hex_len < Self::MIN_HEX_LEN {
51            Err(Error::TooShort { hex_len })
52        } else {
53            let mut prefix = ObjectId::null(id.kind());
54            let b = prefix.as_mut_slice();
55            let copy_len = (hex_len + 1) / 2;
56            b[..copy_len].copy_from_slice(&id.as_bytes()[..copy_len]);
57            if hex_len % 2 == 1 {
58                b[hex_len / 2] &= 0xf0;
59            }
60
61            Ok(Prefix { bytes: prefix, hex_len })
62        }
63    }
64
65    /// Returns the prefix as object id.
66    ///
67    /// Note that it may be deceptive to use given that it looks like a full
68    /// object id, even though its post-prefix bytes/bits are set to zero.
69    pub fn as_oid(&self) -> &oid {
70        &self.bytes
71    }
72
73    /// Return the amount of hexadecimal characters that are set in the prefix.
74    ///
75    /// This gives the prefix a granularity of 4 bits.
76    pub fn hex_len(&self) -> usize {
77        self.hex_len
78    }
79
80    /// Provided with candidate id which is a full hash, determine how this prefix compares to it,
81    /// only looking at the prefix bytes, ignoring everything behind that.
82    pub fn cmp_oid(&self, candidate: &oid) -> Ordering {
83        let common_len = self.hex_len / 2;
84
85        self.bytes.as_bytes()[..common_len]
86            .cmp(&candidate.as_bytes()[..common_len])
87            .then(if self.hex_len % 2 == 1 {
88                let half_byte_idx = self.hex_len / 2;
89                self.bytes.as_bytes()[half_byte_idx].cmp(&(candidate.as_bytes()[half_byte_idx] & 0xf0))
90            } else {
91                Ordering::Equal
92            })
93    }
94
95    /// Create an instance from the given hexadecimal prefix `value`, e.g. `35e77c16` would yield a `Prefix` with `hex_len()` = 8.
96    pub fn from_hex(value: &str) -> Result<Self, from_hex::Error> {
97        let hex_len = value.len();
98
99        if hex_len > crate::Kind::longest().len_in_hex() {
100            return Err(from_hex::Error::TooLong { hex_len });
101        } else if hex_len < Self::MIN_HEX_LEN {
102            return Err(from_hex::Error::TooShort { hex_len });
103        };
104
105        let src = if value.len() % 2 == 0 {
106            let mut out = Vec::from_iter(std::iter::repeat(0).take(value.len() / 2));
107            faster_hex::hex_decode(value.as_bytes(), &mut out).map(move |_| out)
108        } else {
109            // TODO(perf): do without heap allocation here.
110            let mut buf = [0u8; crate::Kind::longest().len_in_hex()];
111            buf[..value.len()].copy_from_slice(value.as_bytes());
112            buf[value.len()] = b'0';
113            let src = &buf[..=value.len()];
114            let mut out = Vec::from_iter(std::iter::repeat(0).take(src.len() / 2));
115            faster_hex::hex_decode(src, &mut out).map(move |_| out)
116        }
117        .map_err(|e| match e {
118            faster_hex::Error::InvalidChar | faster_hex::Error::Overflow => from_hex::Error::Invalid,
119            faster_hex::Error::InvalidLength(_) => panic!("This is already checked"),
120        })?;
121
122        let mut bytes = ObjectId::null(crate::Kind::from_hex_len(value.len()).expect("hex-len is already checked"));
123        let dst = bytes.as_mut_slice();
124        let copy_len = src.len();
125        dst[..copy_len].copy_from_slice(&src);
126
127        Ok(Prefix { bytes, hex_len })
128    }
129}
130
131/// Create an instance from the given hexadecimal prefix, e.g. `35e77c16` would yield a `Prefix`
132/// with `hex_len()` = 8.
133impl TryFrom<&str> for Prefix {
134    type Error = from_hex::Error;
135
136    fn try_from(value: &str) -> Result<Self, Self::Error> {
137        Prefix::from_hex(value)
138    }
139}
140
141impl std::fmt::Display for Prefix {
142    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
143        self.bytes.to_hex_with_len(self.hex_len).fmt(f)
144    }
145}
146
147impl From<ObjectId> for Prefix {
148    fn from(oid: ObjectId) -> Self {
149        Prefix {
150            bytes: oid,
151            hex_len: oid.kind().len_in_hex(),
152        }
153    }
154}
gix_hash/prefix.rs

gix_hash/
prefix.rs
