swh_graph/
labels.rs

1// Copyright (C) 2023-2024  The Software Heritage developers
2// See the AUTHORS file at the top-level directory of this distribution
3// License: GNU General Public License version 3, or any later version
4// See top-level LICENSE file for more information
5
6//! Labels on graph arcs
7
8use thiserror::Error;
9
10use crate::NodeType;
11
12/// Intermediary type that needs to be casted into one of the [`EdgeLabel`] variants
13#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
14pub struct UntypedEdgeLabel(pub(crate) u64);
15
16impl From<u64> for UntypedEdgeLabel {
17    fn from(n: u64) -> UntypedEdgeLabel {
18        UntypedEdgeLabel(n)
19    }
20}
21
22#[derive(Error, Debug, Clone, PartialEq, Eq, Hash)]
23pub enum EdgeTypingError {
24    #[error("{src} -> {dst} arcs cannot have labels")]
25    NodeTypes { src: NodeType, dst: NodeType },
26}
27
28impl UntypedEdgeLabel {
29    pub fn for_edge_type(
30        &self,
31        src: NodeType,
32        dst: NodeType,
33        transpose_graph: bool,
34    ) -> Result<EdgeLabel, EdgeTypingError> {
35        use crate::NodeType::*;
36
37        let (src, dst) = if transpose_graph {
38            (dst, src)
39        } else {
40            (src, dst)
41        };
42
43        match (src, dst) {
44            (Snapshot, _) => Ok(EdgeLabel::Branch(self.0.into())),
45            (Directory, _) => Ok(EdgeLabel::DirEntry(self.0.into())),
46            (Origin, Snapshot) => Ok(EdgeLabel::Visit(self.0.into())),
47            _ => Err(EdgeTypingError::NodeTypes { src, dst }),
48        }
49    }
50}
51
52impl From<EdgeLabel> for UntypedEdgeLabel {
53    fn from(label: EdgeLabel) -> Self {
54        UntypedEdgeLabel(match label {
55            EdgeLabel::Branch(branch) => branch.0,
56            EdgeLabel::DirEntry(dir_entry) => dir_entry.0,
57            EdgeLabel::Visit(visit) => visit.0,
58        })
59    }
60}
61
62#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
63pub enum EdgeLabel {
64    /// `snp -> *` branches (or `* -> snp` on the transposed graph)
65    Branch(Branch),
66    /// `dir -> *` branches (or `* -> dir` on the transposed graph)
67    DirEntry(DirEntry),
68    /// `ori -> snp` branches (or `snp -> ori` on the transposed graph)
69    Visit(Visit),
70}
71
72macro_rules! impl_edgelabel_convert {
73    ( $variant:ident ( $inner:ty ) ) => {
74        impl From<$inner> for EdgeLabel {
75            fn from(v: $inner) -> EdgeLabel {
76                EdgeLabel::$variant(v)
77            }
78        }
79
80        impl TryFrom<EdgeLabel> for $inner {
81            type Error = ();
82
83            fn try_from(label: EdgeLabel) -> Result<$inner, Self::Error> {
84                match label {
85                    EdgeLabel::$variant(v) => Ok(v),
86                    _ => Err(()),
87                }
88            }
89        }
90
91        impl From<UntypedEdgeLabel> for $inner {
92            fn from(label: UntypedEdgeLabel) -> $inner {
93                <$inner>::from(label.0)
94            }
95        }
96    };
97}
98
99impl_edgelabel_convert!(Branch(Branch));
100impl_edgelabel_convert!(DirEntry(DirEntry));
101impl_edgelabel_convert!(Visit(Visit));
102
103#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
104pub enum VisitStatus {
105    Full,
106    Partial,
107}
108
109#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
110pub struct Visit(pub(crate) u64);
111
112impl From<u64> for Visit {
113    fn from(n: u64) -> Visit {
114        Visit(n)
115    }
116}
117
118impl Visit {
119    /// Returns a new [`Visit`]
120    ///
121    /// or `None` if `timestamp` is 2^59 or greater
122    pub fn new(status: VisitStatus, timestamp: u64) -> Option<Visit> {
123        let is_full = match status {
124            VisitStatus::Full => 1u64,
125            VisitStatus::Partial => 0,
126        };
127        let reserved_bits = 0b1000u64;
128        timestamp
129            .checked_shl(5)
130            .map(|shifted_timestamp| Visit(shifted_timestamp | (is_full << 4) | reserved_bits))
131    }
132
133    pub fn timestamp(&self) -> u64 {
134        self.0 >> 5
135    }
136
137    pub fn status(&self) -> VisitStatus {
138        if self.0 & 0b10000 != 0 {
139            VisitStatus::Full
140        } else {
141            VisitStatus::Partial
142        }
143    }
144}
145
146#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
147pub struct Branch(pub(crate) u64);
148
149impl From<u64> for Branch {
150    fn from(n: u64) -> Branch {
151        Branch(n)
152    }
153}
154
155impl Branch {
156    /// Returns a new [`Branch`]
157    ///
158    /// or `None` if `label_name_id` is 2^61 or greater
159    pub fn new(label_name_id: LabelNameId) -> Option<Branch> {
160        label_name_id.0.checked_shl(3).map(Branch)
161    }
162
163    #[deprecated(since = "7.0.0", note = "filename_id was renamed label_name_id")]
164    /// Deprecated alias for [`label_name_id`](Self::label_name_id)
165    pub fn filename_id(self) -> LabelNameId {
166        self.label_name_id()
167    }
168
169    /// Returns an id of the label name of the entry.
170    ///
171    /// The id can be resolved to the label name through graph properties.
172    pub fn label_name_id(self) -> LabelNameId {
173        LabelNameId(self.0 >> 3)
174    }
175}
176
177#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
178pub struct DirEntry(pub(crate) u64);
179
180impl From<u64> for DirEntry {
181    fn from(n: u64) -> DirEntry {
182        DirEntry(n)
183    }
184}
185
186impl DirEntry {
187    /// Returns a new [`DirEntry`]
188    ///
189    /// or `None` if `label_name_id` is 2^61 or greater
190    pub fn new(permission: Permission, label_name_id: LabelNameId) -> Option<DirEntry> {
191        label_name_id
192            .0
193            .checked_shl(3)
194            .map(|shifted_label_name_id| DirEntry(shifted_label_name_id | (permission as u64)))
195    }
196
197    #[deprecated(since = "7.0.0", note = "filename_id was renamed label_name_id")]
198    /// Deprecated alias for [`label_name_id`](Self::label_name_id)
199    pub fn filename_id(self) -> LabelNameId {
200        self.label_name_id()
201    }
202
203    /// Returns an id of the filename of the entry.
204    ///
205    /// The id can be resolved to the label name through graph properties.
206    pub fn label_name_id(self) -> LabelNameId {
207        LabelNameId(self.0 >> 3)
208    }
209
210    /// Returns the file permission of the given directory entry
211    ///
212    /// Returns `None` when the labeled graph is corrupt or generated by a newer swh-graph
213    /// version with more [`Permission`] variants
214    pub fn permission(self) -> Option<Permission> {
215        use Permission::*;
216        match self.0 & 0b111 {
217            0 => Some(None),
218            1 => Some(Content),
219            2 => Some(ExecutableContent),
220            3 => Some(Symlink),
221            4 => Some(Directory),
222            5 => Some(Revision),
223            _ => Option::None,
224        }
225    }
226
227    /// Returns the file permission of the given directory entry
228    ///
229    /// # Safety
230    ///
231    /// May return an invalid [`Permission`] variant if the labeled graph is corrupt
232    /// or generated by a newer swh-graph version with more variants
233    pub unsafe fn permission_unchecked(self) -> Permission {
234        use Permission::*;
235        match self.0 & 0b111 {
236            0 => None,
237            1 => Content,
238            2 => ExecutableContent,
239            3 => Symlink,
240            4 => Directory,
241            5 => Revision,
242            n => unreachable!("{} mode", n),
243        }
244    }
245}
246
247#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
248pub struct LabelNameId(pub u64);
249
250#[deprecated(since = "7.0.0", note = "FilenameId was renamed to LabelNameId")]
251pub type FilenameId = LabelNameId;
252
253#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
254#[repr(u8)]
255pub enum Permission {
256    None = 0,
257    Content = 1,
258    ExecutableContent = 2,
259    Symlink = 3,
260    Directory = 4,
261    Revision = 5,
262}
263
264impl Permission {
265    /// Returns a UNIX-like mode matching the permission
266    ///
267    /// `0100644` for contents, `0100755` for executable contents, `0120000` for symbolic
268    /// links, `0040000` for directories, and `0160000` for revisions (git submodules);
269    /// or `0` if the [`DirEntry`] has no associated permission.
270    pub fn to_git(self) -> u16 {
271        use Permission::*;
272        match self {
273            None => 0,
274            Content => 0o100644,
275            ExecutableContent => 0o100755,
276            Symlink => 0o120000,
277            Directory => 0o040000,
278            Revision => 0o160000,
279        }
280    }
281
282    /// Returns a permission from a subset of UNIX-like modes.
283    ///
284    /// This is the inverse of [`Permission::to_git`].
285    pub fn from_git(mode: u16) -> Option<Permission> {
286        use Permission::*;
287        match mode {
288            0 => Some(None),
289            0o100644 => Some(Content),
290            0o100755 => Some(ExecutableContent),
291            0o120000 => Some(Symlink),
292            0o040000 => Some(Directory),
293            0o160000 => Some(Revision),
294            _ => Option::None,
295        }
296    }
297
298    /// Returns a permission from a subset of UNIX-like modes.
299    ///
300    /// This is the inverse of [`Permission::to_git`].
301    ///
302    /// # Safety
303    ///
304    /// Undefined behavior if the given mode is not one of the values returned by [`Permission::to_git`]
305    pub unsafe fn from_git_unchecked(mode: u16) -> Permission {
306        use Permission::*;
307        match mode {
308            0 => None,
309            0o100644 => Content,
310            0o100755 => ExecutableContent,
311            0o120000 => Symlink,
312            0o040000 => Directory,
313            0o160000 => Revision,
314            _ => unreachable!("{} mode", mode),
315        }
316    }
317}