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#![allow(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            pub fn new(value: Vec<u8>) -> Self {
59                Self(value)
60            }
61
62            pub fn from_bytes(bytes: &[u8]) -> Self {
63                Self(bytes.to_vec())
64            }
65
66            /// Parses the given hex string into an ObjectId.
67            ///
68            /// The given string must be valid. A static str is required to
69            /// prevent API misuse.
70            pub fn from_hex(hex: &'static str) -> Self {
71                Self::try_from_hex(hex).unwrap()
72            }
73
74            /// Parses the given hex string into an ObjectId.
75            pub fn try_from_hex(hex: impl AsRef<[u8]>) -> Option<Self> {
76                $crate::hex_util::decode_hex(hex).map(Self)
77            }
78        }
79
80        impl std::fmt::Debug for $name {
81            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
82                // TODO: should we use $hex_method here?
83                f.debug_tuple(stringify!($name)).field(&self.hex()).finish()
84            }
85        }
86
87        impl std::fmt::Display for $name {
88            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
89                f.pad(&self.$hex_method())
90            }
91        }
92
93        impl serde::Serialize for $name {
94            fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
95            where
96                S: serde::Serializer,
97            {
98                if serializer.is_human_readable() {
99                    self.$hex_method().serialize(serializer)
100                } else {
101                    self.as_bytes().serialize(serializer)
102                }
103            }
104        }
105
106        impl crate::object_id::ObjectId for $name {
107            fn object_type(&self) -> String {
108                stringify!($name)
109                    .strip_suffix("Id")
110                    .unwrap()
111                    .to_ascii_lowercase()
112                    .to_string()
113            }
114
115            fn as_bytes(&self) -> &[u8] {
116                &self.0
117            }
118
119            fn to_bytes(&self) -> Vec<u8> {
120                self.0.clone()
121            }
122
123            fn hex(&self) -> String {
124                $crate::hex_util::encode_hex(&self.0)
125            }
126        }
127    };
128}
129
130pub(crate) use id_type;
131pub(crate) use impl_id_type;
132
133/// An identifier prefix (typically from a type implementing the [`ObjectId`]
134/// trait) with facilities for converting between bytes and a hex string.
135#[derive(Clone, PartialEq, Eq)]
136pub struct HexPrefix {
137    // For odd-length prefixes, the lower 4 bits of the last byte are
138    // zero-filled (e.g. the prefix "abc" is stored in two bytes as "abc0").
139    min_prefix_bytes: Vec<u8>,
140    has_odd_byte: bool,
141}
142
143impl HexPrefix {
144    /// Returns a new `HexPrefix` or `None` if `prefix` cannot be decoded from
145    /// hex to bytes.
146    pub fn try_from_hex(prefix: impl AsRef<[u8]>) -> Option<Self> {
147        let (min_prefix_bytes, has_odd_byte) = hex_util::decode_hex_prefix(prefix)?;
148        Some(Self {
149            min_prefix_bytes,
150            has_odd_byte,
151        })
152    }
153
154    /// Returns a new `HexPrefix` or `None` if `prefix` cannot be decoded from
155    /// "reverse" hex to bytes.
156    pub fn try_from_reverse_hex(prefix: impl AsRef<[u8]>) -> Option<Self> {
157        let (min_prefix_bytes, has_odd_byte) = hex_util::decode_reverse_hex_prefix(prefix)?;
158        Some(Self {
159            min_prefix_bytes,
160            has_odd_byte,
161        })
162    }
163
164    pub fn from_bytes(bytes: &[u8]) -> Self {
165        Self {
166            min_prefix_bytes: bytes.to_owned(),
167            has_odd_byte: false,
168        }
169    }
170
171    /// Returns a new `HexPrefix` representing the given `id`.
172    pub fn from_id<T: ObjectId + ?Sized>(id: &T) -> Self {
173        Self::from_bytes(id.as_bytes())
174    }
175
176    /// Returns string representation of this prefix using hex digits.
177    pub fn hex(&self) -> String {
178        let mut hex_string = hex_util::encode_hex(&self.min_prefix_bytes);
179        if self.has_odd_byte {
180            hex_string.pop().unwrap();
181        }
182        hex_string
183    }
184
185    /// Returns string representation of this prefix using `z-k` "digits".
186    pub fn reverse_hex(&self) -> String {
187        let mut hex_string = hex_util::encode_reverse_hex(&self.min_prefix_bytes);
188        if self.has_odd_byte {
189            hex_string.pop().unwrap();
190        }
191        hex_string
192    }
193
194    /// Minimum bytes that would match this prefix. (e.g. "abc0" for "abc")
195    ///
196    /// Use this to partition a sorted slice, and test `matches(id)` from there.
197    pub fn min_prefix_bytes(&self) -> &[u8] {
198        &self.min_prefix_bytes
199    }
200
201    /// Returns the bytes representation if this prefix can be a full id.
202    pub fn as_full_bytes(&self) -> Option<&[u8]> {
203        (!self.has_odd_byte).then_some(&self.min_prefix_bytes)
204    }
205
206    fn split_odd_byte(&self) -> (Option<u8>, &[u8]) {
207        if self.has_odd_byte {
208            let (&odd, prefix) = self.min_prefix_bytes.split_last().unwrap();
209            (Some(odd), prefix)
210        } else {
211            (None, &self.min_prefix_bytes)
212        }
213    }
214
215    /// Returns whether the stored prefix matches the prefix of `id`.
216    pub fn matches<Q: ObjectId>(&self, id: &Q) -> bool {
217        let id_bytes = id.as_bytes();
218        let (maybe_odd, prefix) = self.split_odd_byte();
219        if id_bytes.starts_with(prefix) {
220            if let Some(odd) = maybe_odd {
221                matches!(id_bytes.get(prefix.len()), Some(v) if v & 0xf0 == odd)
222            } else {
223                true
224            }
225        } else {
226            false
227        }
228    }
229}
230
231impl Debug for HexPrefix {
232    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
233        f.debug_tuple("HexPrefix").field(&self.hex()).finish()
234    }
235}
236
237/// The result of a prefix search.
238#[derive(Debug, Clone, PartialEq, Eq)]
239pub enum PrefixResolution<T> {
240    NoMatch,
241    SingleMatch(T),
242    AmbiguousMatch,
243}
244
245impl<T> PrefixResolution<T> {
246    pub fn map<U>(self, f: impl FnOnce(T) -> U) -> PrefixResolution<U> {
247        match self {
248            Self::NoMatch => PrefixResolution::NoMatch,
249            Self::SingleMatch(x) => PrefixResolution::SingleMatch(f(x)),
250            Self::AmbiguousMatch => PrefixResolution::AmbiguousMatch,
251        }
252    }
253}
254
255impl<T: Clone> PrefixResolution<T> {
256    pub fn plus(&self, other: &Self) -> Self {
257        match (self, other) {
258            (Self::NoMatch, other) => other.clone(),
259            (local, Self::NoMatch) => local.clone(),
260            (Self::AmbiguousMatch, _) => Self::AmbiguousMatch,
261            (_, Self::AmbiguousMatch) => Self::AmbiguousMatch,
262            (Self::SingleMatch(_), Self::SingleMatch(_)) => Self::AmbiguousMatch,
263        }
264    }
265}
266
267#[cfg(test)]
268mod tests {
269    use super::*;
270    use crate::backend::ChangeId;
271    use crate::backend::CommitId;
272
273    #[test]
274    fn test_display_object_id() {
275        let commit_id = CommitId::from_hex("deadbeef0123");
276        assert_eq!(format!("{commit_id}"), "deadbeef0123");
277        assert_eq!(format!("{commit_id:.6}"), "deadbe");
278
279        let change_id = ChangeId::from_hex("deadbeef0123");
280        assert_eq!(format!("{change_id}"), "mlpmollkzyxw");
281        assert_eq!(format!("{change_id:.6}"), "mlpmol");
282    }
283
284    #[test]
285    fn test_hex_prefix_prefixes() {
286        let prefix = HexPrefix::try_from_hex("").unwrap();
287        assert_eq!(prefix.min_prefix_bytes(), b"");
288
289        let prefix = HexPrefix::try_from_hex("1").unwrap();
290        assert_eq!(prefix.min_prefix_bytes(), b"\x10");
291
292        let prefix = HexPrefix::try_from_hex("12").unwrap();
293        assert_eq!(prefix.min_prefix_bytes(), b"\x12");
294
295        let prefix = HexPrefix::try_from_hex("123").unwrap();
296        assert_eq!(prefix.min_prefix_bytes(), b"\x12\x30");
297
298        let bad_prefix = HexPrefix::try_from_hex("0x123");
299        assert_eq!(bad_prefix, None);
300
301        let bad_prefix = HexPrefix::try_from_hex("foobar");
302        assert_eq!(bad_prefix, None);
303    }
304
305    #[test]
306    fn test_hex_prefix_matches() {
307        let id = CommitId::from_hex("1234");
308
309        assert!(HexPrefix::try_from_hex("").unwrap().matches(&id));
310        assert!(HexPrefix::try_from_hex("1").unwrap().matches(&id));
311        assert!(HexPrefix::try_from_hex("12").unwrap().matches(&id));
312        assert!(HexPrefix::try_from_hex("123").unwrap().matches(&id));
313        assert!(HexPrefix::try_from_hex("1234").unwrap().matches(&id));
314        assert!(!HexPrefix::try_from_hex("12345").unwrap().matches(&id));
315
316        assert!(!HexPrefix::try_from_hex("a").unwrap().matches(&id));
317        assert!(!HexPrefix::try_from_hex("1a").unwrap().matches(&id));
318        assert!(!HexPrefix::try_from_hex("12a").unwrap().matches(&id));
319        assert!(!HexPrefix::try_from_hex("123a").unwrap().matches(&id));
320    }
321}
jj_lib/object_id.rs

jj_lib/
object_id.rs
