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
17pub trait ObjectId {
18    fn object_type(&self) -> String;
19    fn as_bytes(&self) -> &[u8];
20    fn to_bytes(&self) -> Vec<u8>;
21    fn hex(&self) -> String;
22}
23
24// Defines a new struct type with visibility `vis` and name `ident` containing
25// a single Vec<u8> used to store an identifier (typically the output of a hash
26// function) as bytes. Types defined using this macro automatically implement
27// the `ObjectId` and `ContentHash` traits.
28// Documentation comments written inside the macro definition and will be
29// captured and associated with the type defined by the macro.
30//
31// Example:
32// ```no_run
33// id_type!(
34//     /// My favorite id type.
35//     pub MyId { hex() }
36// );
37// ```
38macro_rules! id_type {
39    (   $(#[$attr:meta])*
40        $vis:vis $name:ident { $hex_method:ident() }
41    ) => {
42        $(#[$attr])*
43        #[derive(ContentHash, PartialEq, Eq, PartialOrd, Ord, Clone, Hash)]
44        $vis struct $name(Vec<u8>);
45        $crate::object_id::impl_id_type!($name, $hex_method);
46    };
47}
48
49macro_rules! impl_id_type {
50    ($name:ident, $hex_method:ident) => {
51        impl $name {
52            pub fn new(value: Vec<u8>) -> Self {
53                Self(value)
54            }
55
56            pub fn from_bytes(bytes: &[u8]) -> Self {
57                Self(bytes.to_vec())
58            }
59
60            /// Parses the given hex string into an ObjectId.
61            ///
62            /// The given string must be valid. A static str is required to
63            /// prevent API misuse.
64            pub fn from_hex(hex: &'static str) -> Self {
65                Self::try_from_hex(hex).unwrap()
66            }
67
68            /// Parses the given hex string into an ObjectId.
69            pub fn try_from_hex(hex: &str) -> Result<Self, hex::FromHexError> {
70                hex::decode(hex).map(Self)
71            }
72        }
73
74        impl std::fmt::Debug for $name {
75            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
76                // TODO: should we use $hex_method here?
77                f.debug_tuple(stringify!($name)).field(&self.hex()).finish()
78            }
79        }
80
81        impl std::fmt::Display for $name {
82            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
83                f.pad(&self.$hex_method())
84            }
85        }
86
87        impl crate::object_id::ObjectId for $name {
88            fn object_type(&self) -> String {
89                stringify!($name)
90                    .strip_suffix("Id")
91                    .unwrap()
92                    .to_ascii_lowercase()
93                    .to_string()
94            }
95
96            fn as_bytes(&self) -> &[u8] {
97                &self.0
98            }
99
100            fn to_bytes(&self) -> Vec<u8> {
101                self.0.clone()
102            }
103
104            fn hex(&self) -> String {
105                hex::encode(&self.0)
106            }
107        }
108    };
109}
110
111pub(crate) use id_type;
112pub(crate) use impl_id_type;
113
114/// An identifier prefix (typically from a type implementing the [`ObjectId`]
115/// trait) with facilities for converting between bytes and a hex string.
116#[derive(Debug, Clone, PartialEq, Eq)]
117pub struct HexPrefix {
118    // For odd-length prefixes, the lower 4 bits of the last byte are
119    // zero-filled (e.g. the prefix "abc" is stored in two bytes as "abc0").
120    min_prefix_bytes: Vec<u8>,
121    has_odd_byte: bool,
122}
123
124impl HexPrefix {
125    /// Returns a new `HexPrefix` or `None` if `prefix` cannot be decoded from
126    /// hex to bytes.
127    pub fn new(prefix: &str) -> Option<HexPrefix> {
128        let has_odd_byte = prefix.len() & 1 != 0;
129        let min_prefix_bytes = if has_odd_byte {
130            hex::decode(prefix.to_owned() + "0").ok()?
131        } else {
132            hex::decode(prefix).ok()?
133        };
134        Some(HexPrefix {
135            min_prefix_bytes,
136            has_odd_byte,
137        })
138    }
139
140    pub fn from_bytes(bytes: &[u8]) -> Self {
141        HexPrefix {
142            min_prefix_bytes: bytes.to_owned(),
143            has_odd_byte: false,
144        }
145    }
146
147    pub fn hex(&self) -> String {
148        let mut hex_string = hex::encode(&self.min_prefix_bytes);
149        if self.has_odd_byte {
150            hex_string.pop().unwrap();
151        }
152        hex_string
153    }
154
155    /// Minimum bytes that would match this prefix. (e.g. "abc0" for "abc")
156    ///
157    /// Use this to partition a sorted slice, and test `matches(id)` from there.
158    pub fn min_prefix_bytes(&self) -> &[u8] {
159        &self.min_prefix_bytes
160    }
161
162    /// Returns the bytes representation if this prefix can be a full id.
163    pub fn as_full_bytes(&self) -> Option<&[u8]> {
164        (!self.has_odd_byte).then_some(&self.min_prefix_bytes)
165    }
166
167    fn split_odd_byte(&self) -> (Option<u8>, &[u8]) {
168        if self.has_odd_byte {
169            let (&odd, prefix) = self.min_prefix_bytes.split_last().unwrap();
170            (Some(odd), prefix)
171        } else {
172            (None, &self.min_prefix_bytes)
173        }
174    }
175
176    /// Returns whether the stored prefix matches the prefix of `id`.
177    pub fn matches<Q: ObjectId>(&self, id: &Q) -> bool {
178        let id_bytes = id.as_bytes();
179        let (maybe_odd, prefix) = self.split_odd_byte();
180        if id_bytes.starts_with(prefix) {
181            if let Some(odd) = maybe_odd {
182                matches!(id_bytes.get(prefix.len()), Some(v) if v & 0xf0 == odd)
183            } else {
184                true
185            }
186        } else {
187            false
188        }
189    }
190}
191
192/// The result of a prefix search.
193#[derive(Debug, Clone, PartialEq, Eq)]
194pub enum PrefixResolution<T> {
195    NoMatch,
196    SingleMatch(T),
197    AmbiguousMatch,
198}
199
200impl<T> PrefixResolution<T> {
201    pub fn map<U>(self, f: impl FnOnce(T) -> U) -> PrefixResolution<U> {
202        match self {
203            PrefixResolution::NoMatch => PrefixResolution::NoMatch,
204            PrefixResolution::SingleMatch(x) => PrefixResolution::SingleMatch(f(x)),
205            PrefixResolution::AmbiguousMatch => PrefixResolution::AmbiguousMatch,
206        }
207    }
208}
209
210impl<T: Clone> PrefixResolution<T> {
211    pub fn plus(&self, other: &PrefixResolution<T>) -> PrefixResolution<T> {
212        match (self, other) {
213            (PrefixResolution::NoMatch, other) => other.clone(),
214            (local, PrefixResolution::NoMatch) => local.clone(),
215            (PrefixResolution::AmbiguousMatch, _) => PrefixResolution::AmbiguousMatch,
216            (_, PrefixResolution::AmbiguousMatch) => PrefixResolution::AmbiguousMatch,
217            (PrefixResolution::SingleMatch(_), PrefixResolution::SingleMatch(_)) => {
218                PrefixResolution::AmbiguousMatch
219            }
220        }
221    }
222}
223
224#[cfg(test)]
225mod tests {
226    use super::*;
227    use crate::backend::ChangeId;
228    use crate::backend::CommitId;
229
230    #[test]
231    fn test_display_object_id() {
232        let commit_id = CommitId::from_hex("deadbeef0123");
233        assert_eq!(format!("{commit_id}"), "deadbeef0123");
234        assert_eq!(format!("{commit_id:.6}"), "deadbe");
235
236        let change_id = ChangeId::from_hex("deadbeef0123");
237        assert_eq!(format!("{change_id}"), "mlpmollkzyxw");
238        assert_eq!(format!("{change_id:.6}"), "mlpmol");
239    }
240
241    #[test]
242    fn test_hex_prefix_prefixes() {
243        let prefix = HexPrefix::new("").unwrap();
244        assert_eq!(prefix.min_prefix_bytes(), b"");
245
246        let prefix = HexPrefix::new("1").unwrap();
247        assert_eq!(prefix.min_prefix_bytes(), b"\x10");
248
249        let prefix = HexPrefix::new("12").unwrap();
250        assert_eq!(prefix.min_prefix_bytes(), b"\x12");
251
252        let prefix = HexPrefix::new("123").unwrap();
253        assert_eq!(prefix.min_prefix_bytes(), b"\x12\x30");
254
255        let bad_prefix = HexPrefix::new("0x123");
256        assert_eq!(bad_prefix, None);
257
258        let bad_prefix = HexPrefix::new("foobar");
259        assert_eq!(bad_prefix, None);
260    }
261
262    #[test]
263    fn test_hex_prefix_matches() {
264        let id = CommitId::from_hex("1234");
265
266        assert!(HexPrefix::new("").unwrap().matches(&id));
267        assert!(HexPrefix::new("1").unwrap().matches(&id));
268        assert!(HexPrefix::new("12").unwrap().matches(&id));
269        assert!(HexPrefix::new("123").unwrap().matches(&id));
270        assert!(HexPrefix::new("1234").unwrap().matches(&id));
271        assert!(!HexPrefix::new("12345").unwrap().matches(&id));
272
273        assert!(!HexPrefix::new("a").unwrap().matches(&id));
274        assert!(!HexPrefix::new("1a").unwrap().matches(&id));
275        assert!(!HexPrefix::new("12a").unwrap().matches(&id));
276        assert!(!HexPrefix::new("123a").unwrap().matches(&id));
277    }
278}
jj_lib/object_id.rs

jj_lib/
object_id.rs
