summaryrefslogtreecommitdiffstats
path: root/vendor/gix-hash/src/prefix.rs
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/gix-hash/src/prefix.rs')
-rw-r--r--vendor/gix-hash/src/prefix.rs152
1 files changed, 152 insertions, 0 deletions
diff --git a/vendor/gix-hash/src/prefix.rs b/vendor/gix-hash/src/prefix.rs
new file mode 100644
index 000000000..a8b55922e
--- /dev/null
+++ b/vendor/gix-hash/src/prefix.rs
@@ -0,0 +1,152 @@
+use std::{cmp::Ordering, convert::TryFrom};
+
+use crate::{oid, ObjectId, Prefix};
+
+/// The error returned by [Prefix::new()].
+#[derive(Debug, thiserror::Error)]
+#[allow(missing_docs)]
+pub enum Error {
+ #[error(
+ "The minimum hex length of a short object id is {}, got {hex_len}",
+ Prefix::MIN_HEX_LEN
+ )]
+ TooShort { hex_len: usize },
+ #[error("An object of kind {object_kind} cannot be larger than {} in hex, but {hex_len} was requested", object_kind.len_in_hex())]
+ TooLong { object_kind: crate::Kind, hex_len: usize },
+}
+
+///
+pub mod from_hex {
+ /// The error returned by [Prefix::from_hex][super::Prefix::from_hex()].
+ #[derive(Debug, Eq, PartialEq, thiserror::Error)]
+ #[allow(missing_docs)]
+ pub enum Error {
+ #[error(
+ "The minimum hex length of a short object id is {}, got {hex_len}",
+ super::Prefix::MIN_HEX_LEN
+ )]
+ TooShort { hex_len: usize },
+ #[error("An id cannot be larger than {} chars in hex, but {hex_len} was requested", crate::Kind::longest().len_in_hex())]
+ TooLong { hex_len: usize },
+ #[error("Invalid character {c} at position {index}")]
+ Invalid { c: char, index: usize },
+ }
+}
+
+impl Prefix {
+ /// The smallest allowed prefix length below which chances for collisions are too high even in small repositories.
+ pub const MIN_HEX_LEN: usize = 4;
+
+ /// Create a new instance by taking a full `id` as input and truncating it to `hex_len`.
+ ///
+ /// For instance, with `hex_len` of 7 the resulting prefix is 3.5 bytes, or 3 bytes and 4 bits
+ /// wide, with all other bytes and bits set to zero.
+ pub fn new(id: impl AsRef<oid>, hex_len: usize) -> Result<Self, Error> {
+ let id = id.as_ref();
+ if hex_len > id.kind().len_in_hex() {
+ Err(Error::TooLong {
+ object_kind: id.kind(),
+ hex_len,
+ })
+ } else if hex_len < Self::MIN_HEX_LEN {
+ Err(Error::TooShort { hex_len })
+ } else {
+ let mut prefix = ObjectId::null(id.kind());
+ let b = prefix.as_mut_slice();
+ let copy_len = (hex_len + 1) / 2;
+ b[..copy_len].copy_from_slice(&id.as_bytes()[..copy_len]);
+ if hex_len % 2 == 1 {
+ b[hex_len / 2] &= 0xf0;
+ }
+
+ Ok(Prefix { bytes: prefix, hex_len })
+ }
+ }
+
+ /// Returns the prefix as object id.
+ ///
+ /// Note that it may be deceptive to use given that it looks like a full
+ /// object id, even though its post-prefix bytes/bits are set to zero.
+ pub fn as_oid(&self) -> &oid {
+ &self.bytes
+ }
+
+ /// Return the amount of hexadecimal characters that are set in the prefix.
+ ///
+ /// This gives the prefix a granularity of 4 bits.
+ pub fn hex_len(&self) -> usize {
+ self.hex_len
+ }
+
+ /// Provided with candidate id which is a full hash, determine how this prefix compares to it,
+ /// only looking at the prefix bytes, ignoring everything behind that.
+ pub fn cmp_oid(&self, candidate: &oid) -> Ordering {
+ let common_len = self.hex_len / 2;
+
+ self.bytes.as_bytes()[..common_len]
+ .cmp(&candidate.as_bytes()[..common_len])
+ .then(if self.hex_len % 2 == 1 {
+ let half_byte_idx = self.hex_len / 2;
+ self.bytes.as_bytes()[half_byte_idx].cmp(&(candidate.as_bytes()[half_byte_idx] & 0xf0))
+ } else {
+ Ordering::Equal
+ })
+ }
+
+ /// Create an instance from the given hexadecimal prefix `value`, e.g. `35e77c16` would yield a `Prefix` with `hex_len()` = 8.
+ pub fn from_hex(value: &str) -> Result<Self, from_hex::Error> {
+ use hex::FromHex;
+ let hex_len = value.len();
+
+ if hex_len > crate::Kind::longest().len_in_hex() {
+ return Err(from_hex::Error::TooLong { hex_len });
+ } else if hex_len < Self::MIN_HEX_LEN {
+ return Err(from_hex::Error::TooShort { hex_len });
+ };
+
+ let src = if value.len() % 2 == 0 {
+ Vec::from_hex(value)
+ } else {
+ let mut buf = [0u8; crate::Kind::longest().len_in_hex()];
+ buf[..value.len()].copy_from_slice(value.as_bytes());
+ buf[value.len()] = b'0';
+ Vec::from_hex(&buf[..value.len() + 1])
+ }
+ .map_err(|e| match e {
+ hex::FromHexError::InvalidHexCharacter { c, index } => from_hex::Error::Invalid { c, index },
+ hex::FromHexError::OddLength | hex::FromHexError::InvalidStringLength => panic!("This is already checked"),
+ })?;
+
+ let mut bytes = ObjectId::null(crate::Kind::from_hex_len(value.len()).expect("hex-len is already checked"));
+ let dst = bytes.as_mut_slice();
+ let copy_len = src.len();
+ dst[..copy_len].copy_from_slice(&src);
+
+ Ok(Prefix { bytes, hex_len })
+ }
+}
+
+/// Create an instance from the given hexadecimal prefix, e.g. `35e77c16` would yield a `Prefix`
+/// with `hex_len()` = 8.
+impl TryFrom<&str> for Prefix {
+ type Error = from_hex::Error;
+
+ fn try_from(value: &str) -> Result<Self, Self::Error> {
+ Prefix::from_hex(value)
+ }
+}
+
+impl std::fmt::Display for Prefix {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ self.bytes.to_hex_with_len(self.hex_len).fmt(f)
+ }
+}
+
+impl From<ObjectId> for Prefix {
+ fn from(oid: ObjectId) -> Self {
+ Prefix {
+ bytes: oid,
+ hex_len: oid.kind().len_in_hex(),
+ }
+ }
+}