// Copyright 2020-2024 The Jujutsu Authors//// Licensed under the Apache License, Version 2.0 (the "License");// you may not use this file except in compliance with the License.// You may obtain a copy of the License at//// https://www.apache.org/licenses/LICENSE-2.0//// Unless required by applicable law or agreed to in writing, software// distributed under the License is distributed on an "AS IS" BASIS,// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.// See the License for the specific language governing permissions and// limitations under the License. //! Identifiers for objects (commits, changes, trees, etc.), and utilities for//! parsing and matching identifier prefixes. use std::fmt;use std::fmt::Debug; use crate::hex_util; /// An identifier for an object, such as a commit or a tree, usually the output/// of a hash function.pub trait ObjectId { /// A lowercase name identifying the type of object (e.g. "commit"). fn object_type(&self) -> String; /// The identifier as a byte slice. fn as_bytes(&self) -> &[u8]; /// The identifier as an owned byte vector. fn to_bytes(&self) -> Vec<u8>; /// String representation of the identifier using hex digits. fn hex(&self) -> String;} /// Defines a new struct type representing an object ID, with visibility `vis`/// and name `ident`.////// The struct contains a single `Vec<u8>` used to store the identifier/// (typically the output of a hash function) as bytes. Types defined using this/// macro automatically implement the `ObjectId` and `ContentHash` traits./// Documentation comments written inside the macro definition will be captured/// and associated with the type defined by the macro.////// Example:/// ```/// # use jj_core::object_id::*;/// id_type!(/// /// My favorite id type./// pub MyId { hex() }/// );/// ```#[doc(hidden)] // hide jj_core::_id_type!()#[macro_export]macro_rules! _id_type { ( $(#[$attr:meta])* $vis:vis $name:ident { $hex_method:ident() } ) => { $(#[$attr])* #[derive($crate::content_hash::ContentHash, PartialEq, Eq, PartialOrd, Ord, Clone, Hash)] $vis struct $name(Vec<u8>); $crate::object_id::_impl_id_type!($name, $hex_method); };} #[doc(hidden)]#[macro_export]macro_rules! _impl_id_type { ($name:ident, $hex_method:ident) => { #[allow(dead_code)] impl $name { /// Creates a new instance of this id type from the given bytes. pub fn new(value: Vec<u8>) -> Self { Self(value) } /// Creates a new instance of this id type from the given byte slice. pub fn from_bytes(bytes: &[u8]) -> Self { Self(bytes.to_vec()) } /// Parses the given hex string into an ObjectId. /// /// The given string must be valid. A static str is required to /// prevent API misuse. pub fn from_hex(hex: &'static str) -> Self { Self::try_from_hex(hex).unwrap() } /// Parses the given hex string into an ObjectId. pub fn try_from_hex(hex: impl AsRef<[u8]>) -> Option<Self> { $crate::hex_util::decode_hex(hex).map(Self) } } impl std::fmt::Debug for $name { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> { // TODO: should we use $hex_method here? f.debug_tuple(stringify!($name)).field(&self.hex()).finish() } } impl std::fmt::Display for $name { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> { f.pad(&self.$hex_method()) } } impl serde::Serialize for $name { fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> where S: serde::Serializer, { if serializer.is_human_readable() { self.$hex_method().serialize(serializer) } else { self.as_bytes().serialize(serializer) } } } impl $crate::object_id::ObjectId for $name { fn object_type(&self) -> String { stringify!($name) .strip_suffix("Id") .unwrap() .to_ascii_lowercase() .to_string() } fn as_bytes(&self) -> &[u8] { &self.0 } fn to_bytes(&self) -> Vec<u8> { self.0.clone() } fn hex(&self) -> String { $crate::hex_util::encode_hex(&self.0) } } };} #[doc(inline)]pub use _id_type as id_type;pub use _impl_id_type; /// An identifier prefix (typically from a type implementing the [`ObjectId`]/// trait) with facilities for converting between bytes and a hex string.#[derive(Clone, PartialEq, Eq)]pub struct HexPrefix { // For odd-length prefixes, the lower 4 bits of the last byte are // zero-filled (e.g. the prefix "abc" is stored in two bytes as "abc0"). min_prefix_bytes: Vec<u8>, has_odd_byte: bool,} impl HexPrefix { /// Returns a new `HexPrefix` or `None` if `prefix` cannot be decoded from /// hex to bytes. pub fn try_from_hex(prefix: impl AsRef<[u8]>) -> Option<Self> { let (min_prefix_bytes, has_odd_byte) = hex_util::decode_hex_prefix(prefix)?; Some(Self { min_prefix_bytes, has_odd_byte, }) } /// Returns a new `HexPrefix` or `None` if `prefix` cannot be decoded from /// "reverse" hex to bytes. pub fn try_from_reverse_hex(prefix: impl AsRef<[u8]>) -> Option<Self> { let (min_prefix_bytes, has_odd_byte) = hex_util::decode_reverse_hex_prefix(prefix)?; Some(Self { min_prefix_bytes, has_odd_byte, }) } /// Returns a new `HexPrefix` representing the given full bytes (i.e. an /// even number of hex digits.) pub fn from_bytes(bytes: &[u8]) -> Self { Self { min_prefix_bytes: bytes.to_owned(), has_odd_byte: false, } } /// Returns a new `HexPrefix` representing the given `id`. pub fn from_id<T: ObjectId + ?Sized>(id: &T) -> Self { Self::from_bytes(id.as_bytes()) } /// Returns string representation of this prefix using hex digits. pub fn hex(&self) -> String { let mut hex_string = hex_util::encode_hex(&self.min_prefix_bytes); if self.has_odd_byte { hex_string.pop().unwrap(); } hex_string } /// Returns string representation of this prefix using `z-k` "digits". pub fn reverse_hex(&self) -> String { let mut hex_string = hex_util::encode_reverse_hex(&self.min_prefix_bytes); if self.has_odd_byte { hex_string.pop().unwrap(); } hex_string } /// Minimum bytes that would match this prefix. (e.g. "abc0" for "abc") /// /// Use this to partition a sorted slice, and test `matches(id)` from there. pub fn min_prefix_bytes(&self) -> &[u8] { &self.min_prefix_bytes } /// Returns the bytes representation if this prefix can be a full id. pub fn as_full_bytes(&self) -> Option<&[u8]> { (!self.has_odd_byte).then_some(&self.min_prefix_bytes) } fn split_odd_byte(&self) -> (Option<u8>, &[u8]) { if self.has_odd_byte { let (&odd, prefix) = self.min_prefix_bytes.split_last().unwrap(); (Some(odd), prefix) } else { (None, &self.min_prefix_bytes) } } /// Returns whether the stored prefix matches the prefix of `id`. pub fn matches<Q: ObjectId>(&self, id: &Q) -> bool { let id_bytes = id.as_bytes(); let (maybe_odd, prefix) = self.split_odd_byte(); if id_bytes.starts_with(prefix) { if let Some(odd) = maybe_odd { matches!(id_bytes.get(prefix.len()), Some(v) if v & 0xf0 == odd) } else { true } } else { false } }} impl Debug for HexPrefix { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> { f.debug_tuple("HexPrefix").field(&self.hex()).finish() }} /// The result of a prefix search.#[derive(Debug, Clone, PartialEq, Eq)]pub enum PrefixResolution<T> { /// The prefix matched no objects. NoMatch, /// The prefix matched exactly one object. SingleMatch(T), /// The prefix matched more than one object. AmbiguousMatch,} impl<T> PrefixResolution<T> { /// Transforms the matched object, if any, by applying `f` to it. pub fn map<U>(self, f: impl FnOnce(T) -> U) -> PrefixResolution<U> { match self { Self::NoMatch => PrefixResolution::NoMatch, Self::SingleMatch(x) => PrefixResolution::SingleMatch(f(x)), Self::AmbiguousMatch => PrefixResolution::AmbiguousMatch, } } /// Transforms the matched object, if any, by applying `f` to it, turning /// a single match into [`NoMatch`](Self::NoMatch) if `f` returns `None`. pub fn filter_map<U>(self, f: impl FnOnce(T) -> Option<U>) -> PrefixResolution<U> { match self { Self::NoMatch => PrefixResolution::NoMatch, Self::SingleMatch(x) => match f(x) { None => PrefixResolution::NoMatch, Some(y) => PrefixResolution::SingleMatch(y), }, Self::AmbiguousMatch => PrefixResolution::AmbiguousMatch, } }} impl<T: Clone> PrefixResolution<T> { /// Combines two resolutions, e.g. from different sources, turning two /// single matches into an ambiguous match. pub fn plus(&self, other: &Self) -> Self { match (self, other) { (Self::NoMatch, other) => other.clone(), (local, Self::NoMatch) => local.clone(), (Self::AmbiguousMatch, _) => Self::AmbiguousMatch, (_, Self::AmbiguousMatch) => Self::AmbiguousMatch, (Self::SingleMatch(_), Self::SingleMatch(_)) => Self::AmbiguousMatch, } }} #[cfg(test)]#[cfg_attr(coverage_nightly, coverage(off))]mod tests { use super::*; id_type!(SomeId { hex() }); #[test] fn test_hex_prefix_prefixes() { let prefix = HexPrefix::try_from_hex("").unwrap(); assert_eq!(prefix.min_prefix_bytes(), b""); let prefix = HexPrefix::try_from_hex("1").unwrap(); assert_eq!(prefix.min_prefix_bytes(), b"\x10"); let prefix = HexPrefix::try_from_hex("12").unwrap(); assert_eq!(prefix.min_prefix_bytes(), b"\x12"); let prefix = HexPrefix::try_from_hex("123").unwrap(); assert_eq!(prefix.min_prefix_bytes(), b"\x12\x30"); let bad_prefix = HexPrefix::try_from_hex("0x123"); assert_eq!(bad_prefix, None); let bad_prefix = HexPrefix::try_from_hex("foobar"); assert_eq!(bad_prefix, None); } #[test] fn test_hex_prefix_matches() { let id = SomeId::from_hex("1234"); assert!(HexPrefix::try_from_hex("").unwrap().matches(&id)); assert!(HexPrefix::try_from_hex("1").unwrap().matches(&id)); assert!(HexPrefix::try_from_hex("12").unwrap().matches(&id)); assert!(HexPrefix::try_from_hex("123").unwrap().matches(&id)); assert!(HexPrefix::try_from_hex("1234").unwrap().matches(&id)); assert!(!HexPrefix::try_from_hex("12345").unwrap().matches(&id)); assert!(!HexPrefix::try_from_hex("a").unwrap().matches(&id)); assert!(!HexPrefix::try_from_hex("1a").unwrap().matches(&id)); assert!(!HexPrefix::try_from_hex("12a").unwrap().matches(&id)); assert!(!HexPrefix::try_from_hex("123a").unwrap().matches(&id)); }}
// Copyright 2020-2024 The Jujutsu Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//! Identifiers for objects (commits, changes, trees, etc.), and utilities for
//! parsing and matching identifier prefixes.
use std::fmt;
use std::fmt::Debug;
use crate::hex_util;
/// An identifier for an object, such as a commit or a tree, usually the output
/// of a hash function.
pub trait ObjectId {
/// A lowercase name identifying the type of object (e.g. "commit").
fn object_type(&self) -> String;
/// The identifier as a byte slice.
fn as_bytes(&self) -> &[u8];
/// The identifier as an owned byte vector.
fn to_bytes(&self) -> Vec<u8>;
/// String representation of the identifier using hex digits.
fn hex(&self) -> String;
}
/// Defines a new struct type representing an object ID, with visibility `vis`
/// and name `ident`.
///
/// The struct contains a single `Vec<u8>` used to store the identifier
/// (typically the output of a hash function) as bytes. Types defined using this
/// macro automatically implement the `ObjectId` and `ContentHash` traits.
/// Documentation comments written inside the macro definition will be captured
/// and associated with the type defined by the macro.
///
/// Example:
/// ```
/// # use jj_core::object_id::*;
/// id_type!(
/// /// My favorite id type.
/// pub MyId { hex() }
/// );
/// ```
#[doc(hidden)] // hide jj_core::_id_type!()
#[macro_export]
macro_rules! _id_type {
( $(#[$attr:meta])*
$vis:vis $name:ident { $hex_method:ident() }
) => {
$(#[$attr])*
#[derive($crate::content_hash::ContentHash, PartialEq, Eq, PartialOrd, Ord, Clone, Hash)]
$vis struct $name(Vec<u8>);
$crate::object_id::_impl_id_type!($name, $hex_method);
};
}
#[doc(hidden)]
#[macro_export]
macro_rules! _impl_id_type {
($name:ident, $hex_method:ident) => {
#[allow(dead_code)]
impl $name {
/// Creates a new instance of this id type from the given bytes.
pub fn new(value: Vec<u8>) -> Self {
Self(value)
}
/// Creates a new instance of this id type from the given byte slice.
pub fn from_bytes(bytes: &[u8]) -> Self {
Self(bytes.to_vec())
}
/// Parses the given hex string into an ObjectId.
///
/// The given string must be valid. A static str is required to
/// prevent API misuse.
pub fn from_hex(hex: &'static str) -> Self {
Self::try_from_hex(hex).unwrap()
}
/// Parses the given hex string into an ObjectId.
pub fn try_from_hex(hex: impl AsRef<[u8]>) -> Option<Self> {
$crate::hex_util::decode_hex(hex).map(Self)
}
}
impl std::fmt::Debug for $name {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
// TODO: should we use $hex_method here?
f.debug_tuple(stringify!($name)).field(&self.hex()).finish()
}
}
impl std::fmt::Display for $name {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
f.pad(&self.$hex_method())
}
}
impl serde::Serialize for $name {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: serde::Serializer,
{
if serializer.is_human_readable() {
self.$hex_method().serialize(serializer)
} else {
self.as_bytes().serialize(serializer)
}
}
}
impl $crate::object_id::ObjectId for $name {
fn object_type(&self) -> String {
stringify!($name)
.strip_suffix("Id")
.unwrap()
.to_ascii_lowercase()
.to_string()
}
fn as_bytes(&self) -> &[u8] {
&self.0
}
fn to_bytes(&self) -> Vec<u8> {
self.0.clone()
}
fn hex(&self) -> String {
$crate::hex_util::encode_hex(&self.0)
}
}
};
}
#[doc(inline)]
pub use _id_type as id_type;
pub use _impl_id_type;
/// An identifier prefix (typically from a type implementing the [`ObjectId`]
/// trait) with facilities for converting between bytes and a hex string.
#[derive(Clone, PartialEq, Eq)]
pub struct HexPrefix {
// For odd-length prefixes, the lower 4 bits of the last byte are
// zero-filled (e.g. the prefix "abc" is stored in two bytes as "abc0").
min_prefix_bytes: Vec<u8>,
has_odd_byte: bool,
}
impl HexPrefix {
/// Returns a new `HexPrefix` or `None` if `prefix` cannot be decoded from
/// hex to bytes.
pub fn try_from_hex(prefix: impl AsRef<[u8]>) -> Option<Self> {
let (min_prefix_bytes, has_odd_byte) = hex_util::decode_hex_prefix(prefix)?;
Some(Self {
min_prefix_bytes,
has_odd_byte,
})
}
/// Returns a new `HexPrefix` or `None` if `prefix` cannot be decoded from
/// "reverse" hex to bytes.
pub fn try_from_reverse_hex(prefix: impl AsRef<[u8]>) -> Option<Self> {
let (min_prefix_bytes, has_odd_byte) = hex_util::decode_reverse_hex_prefix(prefix)?;
Some(Self {
min_prefix_bytes,
has_odd_byte,
})
}
/// Returns a new `HexPrefix` representing the given full bytes (i.e. an
/// even number of hex digits.)
pub fn from_bytes(bytes: &[u8]) -> Self {
Self {
min_prefix_bytes: bytes.to_owned(),
has_odd_byte: false,
}
}
/// Returns a new `HexPrefix` representing the given `id`.
pub fn from_id<T: ObjectId + ?Sized>(id: &T) -> Self {
Self::from_bytes(id.as_bytes())
}
/// Returns string representation of this prefix using hex digits.
pub fn hex(&self) -> String {
let mut hex_string = hex_util::encode_hex(&self.min_prefix_bytes);
if self.has_odd_byte {
hex_string.pop().unwrap();
}
hex_string
}
/// Returns string representation of this prefix using `z-k` "digits".
pub fn reverse_hex(&self) -> String {
let mut hex_string = hex_util::encode_reverse_hex(&self.min_prefix_bytes);
if self.has_odd_byte {
hex_string.pop().unwrap();
}
hex_string
}
/// Minimum bytes that would match this prefix. (e.g. "abc0" for "abc")
///
/// Use this to partition a sorted slice, and test `matches(id)` from there.
pub fn min_prefix_bytes(&self) -> &[u8] {
&self.min_prefix_bytes
}
/// Returns the bytes representation if this prefix can be a full id.
pub fn as_full_bytes(&self) -> Option<&[u8]> {
(!self.has_odd_byte).then_some(&self.min_prefix_bytes)
}
fn split_odd_byte(&self) -> (Option<u8>, &[u8]) {
if self.has_odd_byte {
let (&odd, prefix) = self.min_prefix_bytes.split_last().unwrap();
(Some(odd), prefix)
} else {
(None, &self.min_prefix_bytes)
}
}
/// Returns whether the stored prefix matches the prefix of `id`.
pub fn matches<Q: ObjectId>(&self, id: &Q) -> bool {
let id_bytes = id.as_bytes();
let (maybe_odd, prefix) = self.split_odd_byte();
if id_bytes.starts_with(prefix) {
if let Some(odd) = maybe_odd {
matches!(id_bytes.get(prefix.len()), Some(v) if v & 0xf0 == odd)
} else {
true
}
} else {
false
}
}
}
impl Debug for HexPrefix {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
f.debug_tuple("HexPrefix").field(&self.hex()).finish()
}
}
/// The result of a prefix search.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum PrefixResolution<T> {
/// The prefix matched no objects.
NoMatch,
/// The prefix matched exactly one object.
SingleMatch(T),
/// The prefix matched more than one object.
AmbiguousMatch,
}
impl<T> PrefixResolution<T> {
/// Transforms the matched object, if any, by applying `f` to it.
pub fn map<U>(self, f: impl FnOnce(T) -> U) -> PrefixResolution<U> {
match self {
Self::NoMatch => PrefixResolution::NoMatch,
Self::SingleMatch(x) => PrefixResolution::SingleMatch(f(x)),
Self::AmbiguousMatch => PrefixResolution::AmbiguousMatch,
}
}
/// Transforms the matched object, if any, by applying `f` to it, turning
/// a single match into [`NoMatch`](Self::NoMatch) if `f` returns `None`.
pub fn filter_map<U>(self, f: impl FnOnce(T) -> Option<U>) -> PrefixResolution<U> {
match self {
Self::NoMatch => PrefixResolution::NoMatch,
Self::SingleMatch(x) => match f(x) {
None => PrefixResolution::NoMatch,
Some(y) => PrefixResolution::SingleMatch(y),
},
Self::AmbiguousMatch => PrefixResolution::AmbiguousMatch,
}
}
}
impl<T: Clone> PrefixResolution<T> {
/// Combines two resolutions, e.g. from different sources, turning two
/// single matches into an ambiguous match.
pub fn plus(&self, other: &Self) -> Self {
match (self, other) {
(Self::NoMatch, other) => other.clone(),
(local, Self::NoMatch) => local.clone(),
(Self::AmbiguousMatch, _) => Self::AmbiguousMatch,
(_, Self::AmbiguousMatch) => Self::AmbiguousMatch,
(Self::SingleMatch(_), Self::SingleMatch(_)) => Self::AmbiguousMatch,
}
}
}
#[cfg(test)]
#[cfg_attr(coverage_nightly, coverage(off))]
mod tests {
use super::*;
id_type!(SomeId { hex() });
#[test]
fn test_hex_prefix_prefixes() {
let prefix = HexPrefix::try_from_hex("").unwrap();
assert_eq!(prefix.min_prefix_bytes(), b"");
let prefix = HexPrefix::try_from_hex("1").unwrap();
assert_eq!(prefix.min_prefix_bytes(), b"\x10");
let prefix = HexPrefix::try_from_hex("12").unwrap();
assert_eq!(prefix.min_prefix_bytes(), b"\x12");
let prefix = HexPrefix::try_from_hex("123").unwrap();
assert_eq!(prefix.min_prefix_bytes(), b"\x12\x30");
let bad_prefix = HexPrefix::try_from_hex("0x123");
assert_eq!(bad_prefix, None);
let bad_prefix = HexPrefix::try_from_hex("foobar");
assert_eq!(bad_prefix, None);
}
#[test]
fn test_hex_prefix_matches() {
let id = SomeId::from_hex("1234");
assert!(HexPrefix::try_from_hex("").unwrap().matches(&id));
assert!(HexPrefix::try_from_hex("1").unwrap().matches(&id));
assert!(HexPrefix::try_from_hex("12").unwrap().matches(&id));
assert!(HexPrefix::try_from_hex("123").unwrap().matches(&id));
assert!(HexPrefix::try_from_hex("1234").unwrap().matches(&id));
assert!(!HexPrefix::try_from_hex("12345").unwrap().matches(&id));
assert!(!HexPrefix::try_from_hex("a").unwrap().matches(&id));
assert!(!HexPrefix::try_from_hex("1a").unwrap().matches(&id));
assert!(!HexPrefix::try_from_hex("12a").unwrap().matches(&id));
assert!(!HexPrefix::try_from_hex("123a").unwrap().matches(&id));
}
}