git_bug/replica/entity/id/

combined_id.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>.

//! Implementation of combined Ids.
//!
//! See [`CombinedId`] for more.

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

use super::{Id, prefix::IdPrefix};

/// A combination of an [`Entities`][`crate::replica::entity::Entity`] [`Id`]
/// with one of it's [`Operation's`][`crate::replica::entity::operation::Operation`] [`Id`].
///
/// This is useful, to uniquely identify a property of an
/// [`Entity`][`crate::replica::entity::Entity`].
#[derive(Debug, Clone, Copy)]
pub struct CombinedId {
    pub(crate) primary_id: Id,
    pub(crate) secondary_id: Id,
}

impl CombinedId {
    /// Return the combined raw byte slices of the two underlying
    /// [`Ids`][`Id`] representing this [`CombinedId`].
    #[must_use]
    // Only asserts
    #[allow(clippy::missing_panics_doc)]
    pub fn to_slice(&self) -> [u8; 64] {
        let mut value = [0; 64];

        assert_eq!(self.primary_id.as_slice().len(), 32);
        assert_eq!(self.secondary_id.as_slice().len(), 32);

        // SAFETY: `value` is valid for 64 u8 elements by definition, and both sources only
        // contain 32 u8 elements.
        // The slices cannot overlap because mutable references are exclusive.
        unsafe {
            ptr::copy_nonoverlapping(self.primary_id.as_slice().as_ptr(), value.as_mut_ptr(), 32);
            ptr::copy_nonoverlapping(
                self.secondary_id.as_slice().as_ptr(),
                value.as_mut_ptr(),
                32,
            );
        }

        value
    }
}

/// A shortened from of an [`CombinedId`].
///
/// This is meant for Human interaction.
#[derive(Debug, Clone, Copy)]
pub struct CombinedIdPrefix {
    primary_id: IdPrefix,
    secondary_id: IdPrefix,
}

impl CombinedId {
    /// Shorten an [`CombinedId`] to the required length, so that it stays
    /// unique, but is still short enough for human consumption.
    #[must_use]
    pub fn shorten(self) -> CombinedIdPrefix {
        CombinedIdPrefix {
            primary_id: self.primary_id.shorten(),
            secondary_id: self.secondary_id.shorten(),
        }
    }
}

impl Display for CombinedIdPrefix {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        // See the [`FromStr`] impl for a documentation of the layout.
        let mut output = String::new();

        let mut primary = self.primary_id.to_string();
        let mut secondary = self.secondary_id.to_string();

        for index in 0..(IdPrefix::REQUIRED_LENGTH * 2) {
            match index {
                i if i == 1 || i == 3 || i == 5 || i == 9 || (i >= 10 && i % 5 == 4) => {
                    output.push(
                        secondary
                            .pop()
                            .expect("This should always be valid as we max out at REQUIRED_PREFIX"),
                    );
                }
                i if i == 0
                    || i == 2
                    || i == 4
                    || i == 6
                    || i == 7
                    || i == 8
                    || (i >= 10 && i % 5 != 4) =>
                {
                    output.push(
                        primary
                            .pop()
                            .expect("This should always be valid as we max out at REQUIRED_PREFIX"),
                    );
                }
                _ => unreachable!("All possible indices should be covered above."),
            }
        }

        f.write_str(output.as_str())?;

        Ok(())
    }
}

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

    use super::CombinedIdPrefix;
    use crate::replica::entity::id::prefix::{self, IdPrefix};

    #[derive(Debug, thiserror::Error)]
    pub enum Error {
        #[error(
            "Your combined id {combined_id} was too long: {len} of expected 64",
            len = combined_id.len()
        )]
        TooLong { combined_id: String },

        #[error("The separated id prefixes from the combined id prefix could not be parsed: {0}")]
        InvalidPrefix(#[from] prefix::decode::Error),
    }

    impl FromStr for CombinedIdPrefix {
        type Err = Error;

        fn from_str(s: &str) -> Result<Self, Self::Err> {
            // > A combined Id is computed (in `git-bug`) by merging two
            // > Ids, so that the resulting combined Id holds information
            // > from both the primary Id and the secondary Id.
            //
            // > This allows us to later find the secondary element efficiently because
            // > we can access the primary one directly instead of searching
            // > for a primary Entity that has a  secondary matching the Id.
            //
            // > An example usage of this is the Comment data in an Issue. The combined Id
            // > will hold part of the
            // > Issue Id and part of the Comment Id.
            //
            // > To allow the use of an arbitrary length prefix of this Id, Ids from primary
            // > and secondary are interleaved with this irregular pattern to give the
            // > best chance to find the secondary Id even with a 7 character prefix.
            //
            // > Format is as follows:
            // >     10       5     5     5     5     5     5     5     5     5     5    5
            // > PSPSPSPPPS PPPPS PPPPS PPPPS PPPPS PPPPS PPPPS PPPPS PPPPS PPPPS PPPPS PPPP
            //
            // > A complete combined Id holds 50 characters for the primary and 14 for the
            // > secondary, which gives a key space of 36^50 for the primary (~6 * 10^77)
            // > and 36^14 for the secondary (~6 * 10^21).
            // > This asymmetry assumes a reasonable number of secondary Ids within a
            // > primary Entity, while still allowing for a vast  key space  for the primary
            // > (that is, a globally merged database) with a low risk of collision.
            //
            // > Here is the breakdown of several common prefix length:
            //
            // > 5:    3P, 2S
            // > 7:    4P, 3S
            // > 10:   6P, 4S
            // > 16:  11P, 5S
            //
            // Thanks to our Id struct being Copy, we can simply store both the `primary`
            // and the `secondary` Id cheaply. We still need to en- and decode
            // it though, so that we can interface with git-bug (and because we
            // can't store our two Ids).

            if s.len() > 64 {
                return Err(Error::TooLong {
                    combined_id: s.to_owned(),
                });
            }

            let mut primary: [u8; 50] = [0; 50];
            let mut primary_index = 0;

            let mut secondary: [u8; 14] = [0; 14];
            let mut secondary_index = 0;

            for (index, ch) in s.chars().enumerate() {
                match index {
                    i if i == 1 || i == 3 || i == 5 || i == 9 || (i >= 10 && i % 5 == 4) => {
                        secondary[secondary_index] = ch as u8;
                        secondary_index += 1;
                    }
                    i if i == 0
                        || i == 2
                        || i == 4
                        || i == 6
                        || i == 7
                        || i == 8
                        || (i >= 10 && i % 5 != 4) =>
                    {
                        primary[primary_index] = ch as u8;
                        primary_index += 1;
                    }
                    _ => unreachable!("All possible indices should be covered above."),
                }
            }

            Ok(Self {
                primary_id: IdPrefix::from_hex_bytes(&primary)?,
                secondary_id: IdPrefix::from_hex_bytes(&secondary)?,
            })
        }
    }

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

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