dag_types/
id.rs

1/*
2 * Copyright (c) Meta Platforms, Inc. and affiliates.
3 *
4 * This source code is licensed under the MIT license found in the
5 * LICENSE file in the root directory of this source tree.
6 */
7
8//! # id
9//!
10//! Defines types around [`Id`].
11
12use std::fmt;
13use std::io;
14use std::ops;
15
16#[cfg(feature = "serialize-abomonation")]
17use abomonation_derive::Abomonation;
18pub use minibytes::Bytes;
19use serde::Deserialize;
20use serde::Serialize;
21
22/// An integer [`Id`] representing a node in the graph.
23/// [`Id`]s are topologically sorted.
24#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
25#[derive(Serialize, Deserialize)]
26#[cfg_attr(feature = "serialize-abomonation", derive(Abomonation))]
27pub struct Id(pub u64);
28
29/// Name of a vertex in the graph.
30#[derive(Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Serialize, Deserialize)]
31#[serde(transparent)]
32pub struct VertexName(pub Bytes);
33
34impl AsRef<[u8]> for VertexName {
35    fn as_ref(&self) -> &[u8] {
36        &self.0
37    }
38}
39
40impl VertexName {
41    pub fn to_hex(&self) -> String {
42        const HEX_CHARS: &[u8] = b"0123456789abcdef";
43        let mut v = Vec::with_capacity(self.0.len() * 2);
44        for &byte in self.as_ref() {
45            v.push(HEX_CHARS[(byte >> 4) as usize]);
46            v.push(HEX_CHARS[(byte & 0xf) as usize]);
47        }
48        unsafe { String::from_utf8_unchecked(v) }
49    }
50
51    /// Convert from hex.
52    ///
53    /// If `len(hex)` is an odd number, hex + '0' will be used.
54    pub fn from_hex(hex: &[u8]) -> io::Result<Self> {
55        let mut bytes = vec![0u8; (hex.len() + 1) / 2];
56        for (i, byte) in hex.iter().enumerate() {
57            let value = match byte {
58                b'0'..=b'9' => byte - b'0',
59                b'a'..=b'f' => byte - b'a' + 10,
60                b'A'..=b'F' => byte - b'A' + 10,
61                _ => {
62                    return Err(io::Error::new(
63                        io::ErrorKind::InvalidInput,
64                        format!("{:?} is not a hex character", *byte as char),
65                    ));
66                }
67            };
68            if i & 1 == 0 {
69                bytes[i / 2] |= value << 4;
70            } else {
71                bytes[i / 2] |= value;
72            }
73        }
74        Ok(VertexName(Bytes::from(bytes)))
75    }
76
77    pub fn copy_from(value: &[u8]) -> Self {
78        Self(value.to_vec().into())
79    }
80}
81
82impl<T> From<T> for VertexName
83where
84    Bytes: From<T>,
85{
86    fn from(value: T) -> Self {
87        Self(Bytes::from(value))
88    }
89}
90
91impl fmt::Debug for VertexName {
92    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
93        if self.0.len() >= 4 || !looks_like_ascii_identifier(self.as_ref()) {
94            // Use hex format for long names (ex. binary commit hashes).
95            let hex = self.to_hex();
96            // Truncate to specified width (ex. '{:#.12}').
97            if let Some(width) = f.precision() {
98                let truncated = hex.get(..width).unwrap_or(&hex);
99                f.write_str(truncated)
100            } else {
101                f.write_str(&hex)
102            }
103        } else {
104            // Do not use hex if it looks like an ASCII identifier.
105            match std::str::from_utf8(self.as_ref()) {
106                Ok(s) => write!(f, "{}", s),
107                Err(_) => write!(f, "{}", self.to_hex()),
108            }
109        }
110    }
111}
112
113fn looks_like_ascii_identifier(bytes: &[u8]) -> bool {
114    let mut iter = bytes.iter().copied();
115    if !(iter.next().unwrap_or(b'\0') as char).is_ascii_alphabetic() {
116        return false;
117    }
118    iter.all(|b| b.is_ascii_alphanumeric())
119}
120
121/// An integer that separates distinct groups of [`Id`]s.
122///
123/// This can be seen as a way to pre-allocate consecutive integers
124/// for one group to make segments less fragmented.
125///
126/// `(Group, Id)` are also topologically sorted.
127#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
128#[derive(Serialize, Deserialize)]
129pub struct Group(pub usize);
130
131impl Group {
132    /// The "master" group. `ancestors(master)`.
133    /// - Expected to have most of the commits in a repo.
134    /// - Expected to be free from fragmentation. In other words,
135    ///   `ancestors(master)` can be represented in a single Span.
136    pub const MASTER: Self = Self(0);
137
138    /// The "non-master" group.
139    /// - Anything not in `ancestors(master)`. For example, public release
140    ///   branches, local feature branches.
141    /// - Expected to have multiple heads. In other words, is fragmented.
142    /// - Expected to be sparse referred. For example, the "visible heads"
143    ///   will refer to a bounded subset in this group.
144    pub const NON_MASTER: Self = Self(1);
145
146    pub const ALL: [Self; 2] = [Self::MASTER, Self::NON_MASTER];
147
148    pub const COUNT: usize = Self::ALL.len();
149
150    // 1 byte for Group so it's easier to remove everything in a group.
151    pub const BITS: u32 = 8;
152    pub const BYTES: usize = 1;
153
154    /// The first [`Id`] in this group.
155    pub const fn min_id(self) -> Id {
156        Id((self.0 as u64) << (64 - Self::BITS))
157    }
158
159    /// The maximum [`Id`] in this group.
160    pub const fn max_id(self) -> Id {
161        Id(self.min_id().0 + ((1u64 << (64 - Self::BITS)) - 1))
162    }
163
164    /// Convert to array.
165    pub const fn bytes(self) -> [u8; 1] {
166        [self.0 as u8]
167    }
168
169    /// Convert to hex array.
170    pub fn hex_bytes(self) -> [u8; 2] {
171        if self.0 < 10 {
172            [b'0', b'0' + (self.0 as u8)]
173        } else {
174            unreachable!()
175        }
176    }
177}
178
179impl Id {
180    /// The [`Group`] of an Id.
181    pub fn group(self) -> Group {
182        let group = (self.0 >> (64 - Group::BITS)) as usize;
183        debug_assert!(group < Group::COUNT);
184        Group(group)
185    }
186
187    /// Similar to `self..=other`.
188    pub fn to(self, other: Id) -> IdIter {
189        IdIter {
190            current: self,
191            end: other,
192        }
193    }
194
195    /// Convert to a byte array. Useful for indexedlog range query.
196    pub fn to_bytearray(self) -> [u8; 8] {
197        // The field can be used for index range query. So it has to be BE.
198        unsafe { std::mem::transmute(self.0.to_be()) }
199    }
200
201    /// Similar to `to_bytearray`, but insert a `prefix` at the head.
202    /// Useful for segment queries where `level` is the `prefix`.
203    pub fn to_prefixed_bytearray(self, prefix: u8) -> [u8; 9] {
204        let a = self.to_bytearray();
205        [prefix, a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]]
206    }
207
208    pub const MAX: Self = Group::ALL[Group::COUNT - 1].max_id();
209    pub const MIN: Self = Group::ALL[0].min_id();
210}
211
212impl fmt::Display for Id {
213    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
214        let group = self.group();
215        if group == Group::NON_MASTER {
216            write!(f, "N")?;
217        }
218        write!(f, "{}", self.0 - group.min_id().0)
219    }
220}
221
222impl fmt::Debug for Id {
223    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
224        write!(f, "{}", self)
225    }
226}
227
228impl fmt::Display for Group {
229    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
230        match *self {
231            Group::MASTER => write!(f, "Group Master"),
232            Group::NON_MASTER => write!(f, "Group Non-Master"),
233            _ => write!(f, "Group {}", self.0),
234        }
235    }
236}
237
238impl ops::Add<u64> for Id {
239    type Output = Id;
240
241    fn add(self, other: u64) -> Self {
242        Self(self.0 + other)
243    }
244}
245
246impl ops::Sub<u64> for Id {
247    type Output = Id;
248
249    fn sub(self, other: u64) -> Self {
250        Self(self.0 - other)
251    }
252}
253
254// Consider replacing this with iter::Step once it's stable.
255pub struct IdIter {
256    current: Id,
257    end: Id,
258}
259
260impl Iterator for IdIter {
261    type Item = Id;
262
263    fn next(&mut self) -> Option<Id> {
264        if self.current > self.end {
265            None
266        } else {
267            let result = self.current;
268            self.current = self.current + 1;
269            Some(result)
270        }
271    }
272}
273
274#[cfg(any(test, feature = "for-tests"))]
275use quickcheck::Arbitrary;
276#[cfg(any(test, feature = "for-tests"))]
277use quickcheck::Gen;
278
279#[cfg(any(test, feature = "for-tests"))]
280impl Arbitrary for Id {
281    fn arbitrary(g: &mut Gen) -> Self {
282        let group = Group((u32::arbitrary(g) & 1) as usize);
283        group.min_id() + u64::arbitrary(g) % (group.max_id().0 - group.min_id().0)
284    }
285}
286
287// For convenience.
288impl std::cmp::PartialEq<u64> for Id {
289    fn eq(&self, other: &u64) -> bool {
290        self.0 == *other
291    }
292}
293
294#[cfg(test)]
295mod tests {
296    use quickcheck::quickcheck;
297
298    use super::*;
299
300    #[test]
301    fn test_vertex_from_hex_odd() {
302        let vertex = VertexName::from_hex(b"a").unwrap();
303        let vertex2 = VertexName::from_hex(b"a0").unwrap();
304        assert_eq!(vertex, vertex2);
305        assert_eq!(vertex.to_hex(), "a0");
306    }
307
308    quickcheck! {
309        fn test_vertex_hex_roundtrip(slice: Vec<u8>) -> bool {
310            let vertex = VertexName::from(slice);
311            let hex = vertex.to_hex();
312            let vertex2 = VertexName::from_hex(hex.as_bytes()).unwrap();
313            vertex2 == vertex
314        }
315    }
316}
dag_types/id.rs

dag_types/
id.rs
