ilyagr.bsky.social
just playing with tangled
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}