jj_lib/
object_id.rs

1// Copyright 2020-2024 The Jujutsu Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#![expect(missing_docs)]
16
17use std::fmt;
18use std::fmt::Debug;
19
20use crate::hex_util;
21
22pub trait ObjectId {
23    fn object_type(&self) -> String;
24    fn as_bytes(&self) -> &[u8];
25    fn to_bytes(&self) -> Vec<u8>;
26    fn hex(&self) -> String;
27}
28
29// Defines a new struct type with visibility `vis` and name `ident` containing
30// a single Vec<u8> used to store an identifier (typically the output of a hash
31// function) as bytes. Types defined using this macro automatically implement
32// the `ObjectId` and `ContentHash` traits.
33// Documentation comments written inside the macro definition will be captured
34// and associated with the type defined by the macro.
35//
36// Example:
37// ```no_run
38// id_type!(
39//     /// My favorite id type.
40//     pub MyId { hex() }
41// );
42// ```
43macro_rules! id_type {
44    (   $(#[$attr:meta])*
45        $vis:vis $name:ident { $hex_method:ident() }
46    ) => {
47        $(#[$attr])*
48        #[derive($crate::content_hash::ContentHash, PartialEq, Eq, PartialOrd, Ord, Clone, Hash)]
49        $vis struct $name(Vec<u8>);
50        $crate::object_id::impl_id_type!($name, $hex_method);
51    };
52}
53
54macro_rules! impl_id_type {
55    ($name:ident, $hex_method:ident) => {
56        #[allow(dead_code)]
57        impl $name {
58            /// Creates a new instance of this id type from the given bytes.
59            pub fn new(value: Vec<u8>) -> Self {
60                Self(value)
61            }
62
63            /// Creates a new instance of this id type from the given byte slice.
64            pub fn from_bytes(bytes: &[u8]) -> Self {
65                Self(bytes.to_vec())
66            }
67
68            /// Parses the given hex string into an ObjectId.
69            ///
70            /// The given string must be valid. A static str is required to
71            /// prevent API misuse.
72            pub fn from_hex(hex: &'static str) -> Self {
73                Self::try_from_hex(hex).unwrap()
74            }
75
76            /// Parses the given hex string into an ObjectId.
77            pub fn try_from_hex(hex: impl AsRef<[u8]>) -> Option<Self> {
78                $crate::hex_util::decode_hex(hex).map(Self)
79            }
80        }
81
82        impl std::fmt::Debug for $name {
83            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
84                // TODO: should we use $hex_method here?
85                f.debug_tuple(stringify!($name)).field(&self.hex()).finish()
86            }
87        }
88
89        impl std::fmt::Display for $name {
90            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
91                f.pad(&self.$hex_method())
92            }
93        }
94
95        impl serde::Serialize for $name {
96            fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
97            where
98                S: serde::Serializer,
99            {
100                if serializer.is_human_readable() {
101                    self.$hex_method().serialize(serializer)
102                } else {
103                    self.as_bytes().serialize(serializer)
104                }
105            }
106        }
107
108        impl crate::object_id::ObjectId for $name {
109            fn object_type(&self) -> String {
110                stringify!($name)
111                    .strip_suffix("Id")
112                    .unwrap()
113                    .to_ascii_lowercase()
114                    .to_string()
115            }
116
117            fn as_bytes(&self) -> &[u8] {
118                &self.0
119            }
120
121            fn to_bytes(&self) -> Vec<u8> {
122                self.0.clone()
123            }
124
125            fn hex(&self) -> String {
126                $crate::hex_util::encode_hex(&self.0)
127            }
128        }
129    };
130}
131
132pub(crate) use id_type;
133pub(crate) use impl_id_type;
134
135/// An identifier prefix (typically from a type implementing the [`ObjectId`]
136/// trait) with facilities for converting between bytes and a hex string.
137#[derive(Clone, PartialEq, Eq)]
138pub struct HexPrefix {
139    // For odd-length prefixes, the lower 4 bits of the last byte are
140    // zero-filled (e.g. the prefix "abc" is stored in two bytes as "abc0").
141    min_prefix_bytes: Vec<u8>,
142    has_odd_byte: bool,
143}
144
145impl HexPrefix {
146    /// Returns a new `HexPrefix` or `None` if `prefix` cannot be decoded from
147    /// hex to bytes.
148    pub fn try_from_hex(prefix: impl AsRef<[u8]>) -> Option<Self> {
149        let (min_prefix_bytes, has_odd_byte) = hex_util::decode_hex_prefix(prefix)?;
150        Some(Self {
151            min_prefix_bytes,
152            has_odd_byte,
153        })
154    }
155
156    /// Returns a new `HexPrefix` or `None` if `prefix` cannot be decoded from
157    /// "reverse" hex to bytes.
158    pub fn try_from_reverse_hex(prefix: impl AsRef<[u8]>) -> Option<Self> {
159        let (min_prefix_bytes, has_odd_byte) = hex_util::decode_reverse_hex_prefix(prefix)?;
160        Some(Self {
161            min_prefix_bytes,
162            has_odd_byte,
163        })
164    }
165
166    pub fn from_bytes(bytes: &[u8]) -> Self {
167        Self {
168            min_prefix_bytes: bytes.to_owned(),
169            has_odd_byte: false,
170        }
171    }
172
173    /// Returns a new `HexPrefix` representing the given `id`.
174    pub fn from_id<T: ObjectId + ?Sized>(id: &T) -> Self {
175        Self::from_bytes(id.as_bytes())
176    }
177
178    /// Returns string representation of this prefix using hex digits.
179    pub fn hex(&self) -> String {
180        let mut hex_string = hex_util::encode_hex(&self.min_prefix_bytes);
181        if self.has_odd_byte {
182            hex_string.pop().unwrap();
183        }
184        hex_string
185    }
186
187    /// Returns string representation of this prefix using `z-k` "digits".
188    pub fn reverse_hex(&self) -> String {
189        let mut hex_string = hex_util::encode_reverse_hex(&self.min_prefix_bytes);
190        if self.has_odd_byte {
191            hex_string.pop().unwrap();
192        }
193        hex_string
194    }
195
196    /// Minimum bytes that would match this prefix. (e.g. "abc0" for "abc")
197    ///
198    /// Use this to partition a sorted slice, and test `matches(id)` from there.
199    pub fn min_prefix_bytes(&self) -> &[u8] {
200        &self.min_prefix_bytes
201    }
202
203    /// Returns the bytes representation if this prefix can be a full id.
204    pub fn as_full_bytes(&self) -> Option<&[u8]> {
205        (!self.has_odd_byte).then_some(&self.min_prefix_bytes)
206    }
207
208    fn split_odd_byte(&self) -> (Option<u8>, &[u8]) {
209        if self.has_odd_byte {
210            let (&odd, prefix) = self.min_prefix_bytes.split_last().unwrap();
211            (Some(odd), prefix)
212        } else {
213            (None, &self.min_prefix_bytes)
214        }
215    }
216
217    /// Returns whether the stored prefix matches the prefix of `id`.
218    pub fn matches<Q: ObjectId>(&self, id: &Q) -> bool {
219        let id_bytes = id.as_bytes();
220        let (maybe_odd, prefix) = self.split_odd_byte();
221        if id_bytes.starts_with(prefix) {
222            if let Some(odd) = maybe_odd {
223                matches!(id_bytes.get(prefix.len()), Some(v) if v & 0xf0 == odd)
224            } else {
225                true
226            }
227        } else {
228            false
229        }
230    }
231}
232
233impl Debug for HexPrefix {
234    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
235        f.debug_tuple("HexPrefix").field(&self.hex()).finish()
236    }
237}
238
239/// The result of a prefix search.
240#[derive(Debug, Clone, PartialEq, Eq)]
241pub enum PrefixResolution<T> {
242    NoMatch,
243    SingleMatch(T),
244    AmbiguousMatch,
245}
246
247impl<T> PrefixResolution<T> {
248    pub fn map<U>(self, f: impl FnOnce(T) -> U) -> PrefixResolution<U> {
249        match self {
250            Self::NoMatch => PrefixResolution::NoMatch,
251            Self::SingleMatch(x) => PrefixResolution::SingleMatch(f(x)),
252            Self::AmbiguousMatch => PrefixResolution::AmbiguousMatch,
253        }
254    }
255
256    pub fn filter_map<U>(self, f: impl FnOnce(T) -> Option<U>) -> PrefixResolution<U> {
257        match self {
258            Self::NoMatch => PrefixResolution::NoMatch,
259            Self::SingleMatch(x) => match f(x) {
260                None => PrefixResolution::NoMatch,
261                Some(y) => PrefixResolution::SingleMatch(y),
262            },
263            Self::AmbiguousMatch => PrefixResolution::AmbiguousMatch,
264        }
265    }
266}
267
268impl<T: Clone> PrefixResolution<T> {
269    pub fn plus(&self, other: &Self) -> Self {
270        match (self, other) {
271            (Self::NoMatch, other) => other.clone(),
272            (local, Self::NoMatch) => local.clone(),
273            (Self::AmbiguousMatch, _) => Self::AmbiguousMatch,
274            (_, Self::AmbiguousMatch) => Self::AmbiguousMatch,
275            (Self::SingleMatch(_), Self::SingleMatch(_)) => Self::AmbiguousMatch,
276        }
277    }
278}
279
280#[cfg(test)]
281mod tests {
282    use super::*;
283    use crate::backend::ChangeId;
284    use crate::backend::CommitId;
285
286    #[test]
287    fn test_display_object_id() {
288        let commit_id = CommitId::from_hex("deadbeef0123");
289        assert_eq!(format!("{commit_id}"), "deadbeef0123");
290        assert_eq!(format!("{commit_id:.6}"), "deadbe");
291
292        let change_id = ChangeId::from_hex("deadbeef0123");
293        assert_eq!(format!("{change_id}"), "mlpmollkzyxw");
294        assert_eq!(format!("{change_id:.6}"), "mlpmol");
295    }
296
297    #[test]
298    fn test_hex_prefix_prefixes() {
299        let prefix = HexPrefix::try_from_hex("").unwrap();
300        assert_eq!(prefix.min_prefix_bytes(), b"");
301
302        let prefix = HexPrefix::try_from_hex("1").unwrap();
303        assert_eq!(prefix.min_prefix_bytes(), b"\x10");
304
305        let prefix = HexPrefix::try_from_hex("12").unwrap();
306        assert_eq!(prefix.min_prefix_bytes(), b"\x12");
307
308        let prefix = HexPrefix::try_from_hex("123").unwrap();
309        assert_eq!(prefix.min_prefix_bytes(), b"\x12\x30");
310
311        let bad_prefix = HexPrefix::try_from_hex("0x123");
312        assert_eq!(bad_prefix, None);
313
314        let bad_prefix = HexPrefix::try_from_hex("foobar");
315        assert_eq!(bad_prefix, None);
316    }
317
318    #[test]
319    fn test_hex_prefix_matches() {
320        let id = CommitId::from_hex("1234");
321
322        assert!(HexPrefix::try_from_hex("").unwrap().matches(&id));
323        assert!(HexPrefix::try_from_hex("1").unwrap().matches(&id));
324        assert!(HexPrefix::try_from_hex("12").unwrap().matches(&id));
325        assert!(HexPrefix::try_from_hex("123").unwrap().matches(&id));
326        assert!(HexPrefix::try_from_hex("1234").unwrap().matches(&id));
327        assert!(!HexPrefix::try_from_hex("12345").unwrap().matches(&id));
328
329        assert!(!HexPrefix::try_from_hex("a").unwrap().matches(&id));
330        assert!(!HexPrefix::try_from_hex("1a").unwrap().matches(&id));
331        assert!(!HexPrefix::try_from_hex("12a").unwrap().matches(&id));
332        assert!(!HexPrefix::try_from_hex("123a").unwrap().matches(&id));
333    }
334}
jj_lib/object_id.rs

jj_lib/
object_id.rs
