git_bug/replica/entity/id/

prefix.rs

// git-bug-rs - A rust library for interfacing with git-bug repositories
//
// Copyright (C) 2025 Benedikt Peetz <benedikt.peetz@b-peetz.de>
// SPDX-License-Identifier: GPL-3.0-or-later
//
// This file is part of git-bug-rs/git-gub.
//
// You should have received a copy of the License along with this program.
// If not, see <https://www.gnu.org/licenses/agpl.txt>.

//! A shortened from of an [`Id`][`super::Id`]

use std::fmt::{Display, Write};

use gix::Repository;

use super::{Id, entity_id::EntityId};
use crate::replica::{
    entity::{Entity, EntityRead},
    entity_iter::EntityIdIter,
};

/// A shortened from of an [`Id`][`super::Id`].
///
/// This is meant for Human interaction.
#[derive(Debug, Clone, Copy)]
pub struct IdPrefix {
    /// The first 4 hex-chars are always required in a Prefix.
    first: [u8; Self::REQUIRED_LENGTH],

    /// The other hex chars composing this [`IdPrefix`].
    /// These could be added to make this Prefix more unique.
    ///
    /// They are padded with [`None`] to fill the array.
    rest: [Option<u8>; 32 - Self::REQUIRED_LENGTH],

    /// If the rest is not even, this is hex decoded value of the last element
    /// in rest.
    ///
    /// Effectively this just stores a u4 (because a hex char can max be 15). As
    /// such, the leading four bits are guaranteed to be 0.
    uneven_offset: Option<u8>,
}

impl Display for IdPrefix {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        // TODO(@bpeetz): Ideally this function would actually check if 7 hex-chars are
        // enough. <2025-04-19>

        let mut buffer = [0; Self::REQUIRED_LENGTH * 2];
        f.write_str(
            &faster_hex::hex_encode(&self.first, &mut buffer).expect("We can count")
                [..Self::REQUIRED_LENGTH * 2],
        )?;

        // Try to write at least 7 chars (i.e., try to take 7 - <already printed> chars).
        for next in self
            .rest
            .iter()
            .filter_map(|a| a.as_ref())
            .chain(self.uneven_offset.iter())
            .flat_map(|value| {
                let second = value & 0xF;
                let first = (value >> 4) & 0xF;

                assert!(first < 16);
                assert!(second < 16);

                [first, second]
            })
            .take(7 - (Self::REQUIRED_LENGTH * 2))
        {
            f.write_char(encode_hex(next))?;
        }

        Ok(())
    }
}

impl From<Id> for IdPrefix {
    fn from(value: Id) -> Self {
        let mut first = [0; Self::REQUIRED_LENGTH];
        let mut rest = [None; 32 - Self::REQUIRED_LENGTH];

        first.copy_from_slice(&value.as_bytes()[..Self::REQUIRED_LENGTH]);
        for (slot, byte) in rest
            .iter_mut()
            .zip(&value.as_bytes()[Self::REQUIRED_LENGTH..])
        {
            *slot = Some(*byte);
        }

        Self {
            first,
            rest,
            uneven_offset: None,
        }
    }
}

impl IdPrefix {
    /// The number of required hex bytes in a prefix (i.e., a prefix must be at
    /// least this * 2 hex chars long.)
    // NOTE(@bpeetz): This number needs to be even. <2025-04-21>
    pub const REQUIRED_LENGTH: usize = 2;

    /// Construct an new [`IdPrefix`] from hex bytes.
    ///
    /// # Errors
    /// - If the `input` does not contain ([`Self::REQUIRED_LENGTH`] * 2) hex bytes.
    /// - If the `input` is longer than 64 hex chars.
    ///
    /// This is probably not what you want.
    /// Use [`Id::shorten`][`super::Id::shorten`] to turn an [`Id`][`super::Id`]
    /// to it's short form instead.
    pub fn from_hex_bytes(input: &[u8]) -> Result<Self, decode::Error> {
        if input.len() > 64 || input.len() < Self::REQUIRED_LENGTH * 2 {
            return Err(decode::Error::InvalidLen(input.len()));
        }

        let first = {
            let mut first_raw = [0; Self::REQUIRED_LENGTH * 2];
            first_raw.copy_from_slice(&input[..Self::REQUIRED_LENGTH * 2]);

            let mut dst = [0; Self::REQUIRED_LENGTH];
            faster_hex::hex_decode(&first_raw, &mut dst).map_err(|err| match err {
                faster_hex::Error::InvalidChar => decode::Error::InvalidChar,
                faster_hex::Error::InvalidLength(_) | faster_hex::Error::Overflow => {
                    unreachable!("We checked our numbers")
                }
            })?;
            dst
        };

        let mut uneven_offset: Option<u8> = None;

        let rest = {
            let mut rest_raw = [0; 64 - (Self::REQUIRED_LENGTH * 2)];

            for (slot, source) in rest_raw.iter_mut().zip(&input[Self::REQUIRED_LENGTH * 2..]) {
                *slot = *source;
            }

            let populated_rest = input[Self::REQUIRED_LENGTH * 2..].len();
            if populated_rest == 0 {
                [None; 32 - Self::REQUIRED_LENGTH]
            } else {
                let mut trimmed_rest = &rest_raw[..populated_rest];

                if (trimmed_rest.len() & 1) == 1 {
                    // We have uneven input.
                    // Make the trimmed_rest even, and store the dangling byte separately.
                    uneven_offset = Some({
                        let base = trimmed_rest[trimmed_rest.len() - 1];

                        decode_hex(base)?
                    });

                    trimmed_rest = &trimmed_rest[..(trimmed_rest.len() - 1)];
                }

                let mut dst = [0; 32 - (Self::REQUIRED_LENGTH)];
                faster_hex::hex_decode(trimmed_rest, &mut dst[..trimmed_rest.len() / 2]).map_err(
                    |err| match err {
                        faster_hex::Error::InvalidChar => decode::Error::InvalidChar,
                        err @ (faster_hex::Error::InvalidLength(_)
                        | faster_hex::Error::Overflow) => {
                            unreachable!("We checked our numbers: {err}")
                        }
                    },
                )?;

                let set_rest = &dst[..trimmed_rest.len() / 2];

                let mut base = [None; 32 - Self::REQUIRED_LENGTH];
                for (slot, byte) in base.iter_mut().zip(set_rest.iter()) {
                    *slot = Some(*byte);
                }

                base
            }
        };

        Ok(Self {
            first,
            rest,
            uneven_offset,
        })
    }

    /// Try to resolve this prefix.
    ///
    /// Currently, this lists all ids of the specified [`Entity`] and tries to
    /// find exactly on with this prefix.
    ///
    /// # Errors
    /// - If it cannot read all the [`Entity's`][`Entity`] IDs.
    /// - If more that one matches.
    /// - If none match.
    pub fn resolve<E: Entity + EntityRead>(
        self,
        repo: &Repository,
    ) -> Result<EntityId<E>, resolve::Error> {
        let matching = EntityIdIter::<E>::new(repo)?
            .filter_map(|maybe_id| {
                if let Ok(id) = maybe_id {
                    if self.is_prefix_of(id.as_id()) {
                        Some(Ok(id))
                    } else {
                        None
                    }
                } else {
                    Some(maybe_id)
                }
            })
            .collect::<Result<Vec<_>, _>>()?;

        match matching.len().cmp(&1) {
            std::cmp::Ordering::Less => Err(resolve::Error::NotFound),
            std::cmp::Ordering::Equal => Ok(matching[0]),
            std::cmp::Ordering::Greater => Err(resolve::Error::TooManyFound(matching.len())),
        }
    }

    /// Check if this prefix is a prefix of the [`Id`] `id`.
    #[must_use]
    // Only asserts
    #[allow(clippy::missing_panics_doc)]
    pub fn is_prefix_of(&self, id: Id) -> bool {
        let mut output = true;

        if self.first == id.sha256_value[..Self::REQUIRED_LENGTH] {
            for ((prefix, is_uneven_offset), id) in self.rest[..]
                .iter()
                .filter_map(|a| a.map(|b| (b, false)))
                .chain(self.uneven_offset.iter().map(|a| (*a, true)))
                .zip(id.sha256_value[Self::REQUIRED_LENGTH..].iter())
            {
                // Handle the uneven offset in a special way, as the `pr_a` value will always
                // be invalid.
                if is_uneven_offset {
                    let pr_a = (prefix >> 4) & 0xF;
                    assert_eq!(pr_a, 0);

                    let pr_b = prefix & 0xF;

                    // We actually, compare our pr_b with id_a, as faster hex first uses the top
                    // part to store the u4 and only than the lower part.
                    let id_a = (id >> 4) & 0xF;

                    output = pr_b == id_a;
                } else {
                    let pr_a = (prefix >> 4) & 0xF;
                    let pr_b = prefix & 0xF;

                    let id_a = (id >> 4) & 0xF;
                    let id_b = id & 0xF;

                    output = output && pr_a == id_a && pr_b == id_b;
                }
            }

            output
        } else {
            false
        }
    }
}

#[allow(missing_docs)]
pub mod resolve {
    #[derive(Debug, thiserror::Error)]
    /// The Error returned from
    /// [`IdPrefix::resolve`][`super::IdPrefix::resolve`].
    pub enum Error {
        #[error("Failed to resolve this id, because an id de-referencing operation failed: {0}")]
        FailedGet(#[from] crate::replica::get::Error),

        #[error("Failed to resolve prefix, because we did not find a matching id.")]
        NotFound,

        #[error("Failed to resolve prefix, because we found too many matching ids ({0})")]
        TooManyFound(usize),
    }
}

#[allow(missing_docs)]
pub mod decode {
    use std::str::FromStr;

    use crate::replica::entity::id::prefix::IdPrefix;

    #[derive(Debug, thiserror::Error, Clone, Copy)]
    /// The Error returned from [`IdPrefix::from_hex_bytes`].
    pub enum Error {
        #[error(
            "Your prefix input was {0} bytes long, but should be at least {len} bytes and \
                not more than 64.",
            len = IdPrefix::REQUIRED_LENGTH * 2
        )]
        InvalidLen(usize),

        #[error(
            "Your prefix input was not some for the required {first} bytes",
            first = IdPrefix::REQUIRED_LENGTH * 2
        )]
        FirstNotSome,

        #[error("Your hex bytes contained an invalid hex char.")]
        InvalidChar,
    }

    impl FromStr for IdPrefix {
        type Err = Error;

        fn from_str(s: &str) -> Result<Self, Self::Err> {
            Self::from_hex_bytes(s.as_bytes())
        }
    }

    impl TryFrom<&str> for IdPrefix {
        type Error = Error;

        fn try_from(value: &str) -> Result<Self, Self::Error> {
            <Self as FromStr>::from_str(value)
        }
    }
}

fn decode_hex(base: u8) -> Result<u8, decode::Error> {
    let val = match base {
        b'0'..=b'9' => base - b'0',
        b'a'..=b'f' => base - b'a' + 10,
        b'A'..=b'F' => base - b'A' + 10,
        _ => return Err(decode::Error::InvalidChar),
    };
    Ok(val)
}
fn encode_hex(base: u8) -> char {
    match base {
        0..=9 => (b'0' + base) as char,
        10..=15 => (b'a' + (base - 10)) as char,
        _ => unreachable!(),
    }
}

#[cfg(test)]
mod tests {
    use std::str::FromStr;

    use super::IdPrefix;
    use crate::replica::entity::id::{
        Id,
        prefix::{decode_hex, encode_hex},
    };

    const HEX_CHARS: [(u8, char); 16] = [
        (0, '0'),
        (1, '1'),
        (2, '2'),
        (3, '3'),
        (4, '4'),
        (5, '5'),
        (6, '6'),
        (7, '7'),
        (8, '8'),
        (9, '9'),
        (10, 'a'),
        (11, 'b'),
        (12, 'c'),
        (13, 'd'),
        (14, 'e'),
        (15, 'f'),
    ];

    #[test]
    fn test_print() {
        let id = Id::from_hex(b"e30589c8275f1cafd4485f1d414a9c2da0d9cb9b4122f37aa2f557d988e1f87f")
            .unwrap();
        let prefix = id.shorten();

        assert_eq!(prefix.to_string().as_str(), "e30589c");
    }

    #[test]
    fn test_print_2() {
        let id = Id::from_hex(b"b8f4a62333974e95eb69e6956d07e799662acefd28b00ab83fcd72d1ef6522eb")
            .unwrap();

        let prefix = id.shorten();
        assert_eq!(prefix.to_string().as_str(), "b8f4a62");
    }

    #[test]
    fn test_prefix_of_wrong() {
        let id = Id::from_hex(b"a7c3efc6b86b96023641e49b2ec96a4d54406fc5f164d7e79d2bdf66170de892")
            .unwrap();
        let prefix = IdPrefix::from_str("a7c3f").unwrap();

        assert!(!prefix.is_prefix_of(id));
    }

    #[test]
    fn test_prefix_of() {
        let id_str = "fe5ae5b4657a04784c6306473d0e0ec692b40a993195ab16a0e5019d19fbc01c";
        let id = Id::from_hex(id_str.as_bytes()).unwrap();

        for len in (IdPrefix::REQUIRED_LENGTH * 2)..(id_str.len()) {
            let prefix_str = &id_str[..len];

            eprintln!("Testing prefix with len: {len} ({prefix_str})");

            let prefix = IdPrefix::from_str(prefix_str).unwrap();
            assert!(prefix.is_prefix_of(id));
        }
    }

    #[test]
    fn decode_0() {
        assert_eq!(decode_hex(b'0').unwrap(), 0);
    }
    #[test]
    fn decode_a() {
        assert_eq!(decode_hex(b'a').unwrap(), 10);
    }
    #[test]
    #[allow(non_snake_case)]
    fn decode_F() {
        assert_eq!(decode_hex(b'F').unwrap(), 15);
    }

    #[test]
    fn test_all() {
        for (value, name) in HEX_CHARS {
            assert_eq!(value, decode_hex(name as u8).unwrap());
            assert_eq!(encode_hex(value), name);
        }
    }

    #[test]
    fn encode_0() {
        assert_eq!(encode_hex(0), '0');
    }
    #[test]
    fn encode_a() {
        assert_eq!(encode_hex(10), 'a');
    }
    #[test]
    fn encode_f() {
        assert_eq!(encode_hex(15), 'f');
    }
}