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

jj_lib/
object_id.rs
