pijul_core/pristine/
vertex.rs

1use super::change_id::*;
2use super::{BASE32, L64};
3#[cfg(test)]
4use quickcheck::{Arbitrary, Gen};
5
6/// A node in the repository graph, made of a change internal
7/// identifier, and a line identifier in that change.
8#[derive(Clone, Copy, PartialEq, PartialOrd, Eq, Ord, Hash, Serialize, Deserialize)]
9#[repr(C)]
10pub struct Vertex<H> {
11    /// The change that introduced this node.
12    pub change: H,
13    /// The line identifier of the node in that change. Here,
14    /// "line" does not imply anything on the contents of the
15    /// chunk.
16    pub start: ChangePosition,
17    pub end: ChangePosition,
18}
19
20impl<T: std::fmt::Debug> std::fmt::Debug for Vertex<T> {
21    fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
22        write!(
23            fmt,
24            "V({:?}[{}:{}])",
25            self.change,
26            (self.start.0),
27            (self.end.0)
28        )
29    }
30}
31
32impl Vertex<ChangeId> {
33    /// The node at the root of the repository graph.
34    pub const ROOT: Vertex<ChangeId> = Vertex {
35        change: ChangeId::ROOT,
36        start: ChangePosition::ROOT,
37        end: ChangePosition::ROOT,
38    };
39
40    pub const MAX: Vertex<ChangeId> = Vertex {
41        // u64::MAX is the maximum both for LE and BE byte orders.
42        change: ChangeId(L64(u64::MAX)),
43        start: ChangePosition(L64(u64::MAX)),
44        end: ChangePosition(L64(u64::MAX)),
45    };
46
47    /// The node at the root of the repository graph.
48    pub(crate) const BOTTOM: Vertex<ChangeId> = Vertex {
49        change: ChangeId::ROOT,
50        start: ChangePosition::BOTTOM,
51        end: ChangePosition::BOTTOM,
52    };
53
54    /// Is this the root key? (the root key is all 0s).
55    pub fn is_root(&self) -> bool {
56        self == &Vertex::ROOT
57    }
58
59    pub fn to_option(&self) -> Vertex<Option<ChangeId>> {
60        Vertex {
61            change: Some(self.change),
62            start: self.start,
63            end: self.end,
64        }
65    }
66}
67
68impl<H: Clone> Vertex<H> {
69    /// Convenience function to get the start position of a
70    /// [`Vertex<ChangeId>`](struct.Vertex.html) as a
71    /// [`Position`](struct.Position.html).
72    pub fn start_pos(&self) -> Position<H> {
73        Position {
74            change: self.change.clone(),
75            pos: self.start,
76        }
77    }
78
79    /// Convenience function to get the end position of a
80    /// [`Vertex<ChangeId>`](struct.Vertex.html) as a
81    /// [`Position`](struct.Position.html).
82    pub fn end_pos(&self) -> Position<H> {
83        Position {
84            change: self.change.clone(),
85            pos: self.end,
86        }
87    }
88
89    /// Is this vertex of zero length?
90    pub fn is_empty(&self) -> bool {
91        self.end == self.start
92    }
93
94    /// Length of this key, in bytes.
95    pub fn len(&self) -> usize {
96        self.end - self.start
97    }
98}
99/// The position of a byte within a change.
100#[derive(Debug, Clone, Copy, PartialEq, PartialOrd, Eq, Ord, Hash, Serialize, Deserialize)]
101pub struct ChangePosition(pub super::L64);
102
103impl ChangePosition {
104    pub(crate) const ROOT: ChangePosition = ChangePosition(L64(0u64));
105    pub(crate) const BOTTOM: ChangePosition = ChangePosition(L64(1u64.to_le()));
106}
107
108impl std::ops::Add<usize> for ChangePosition {
109    type Output = ChangePosition;
110    fn add(self, x: usize) -> Self::Output {
111        ChangePosition(self.0 + x)
112    }
113}
114
115impl std::ops::Sub<ChangePosition> for ChangePosition {
116    type Output = usize;
117    fn sub(self, x: ChangePosition) -> Self::Output {
118        let a: u64 = self.0.into();
119        let b: u64 = x.0.into();
120        (a - b) as usize
121    }
122}
123
124#[cfg(test)]
125impl Arbitrary for ChangePosition {
126    fn arbitrary(g: &mut Gen) -> Self {
127        ChangePosition(L64(u64::arbitrary(g)))
128    }
129    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
130        Box::new(self.0.0.shrink().map(|x| ChangePosition(L64(x))))
131    }
132}
133
134impl ChangePosition {
135    pub(crate) fn us(&self) -> usize {
136        u64::from_le((self.0).0) as usize
137    }
138}
139
140impl From<ChangePosition> for u64 {
141    fn from(f: ChangePosition) -> u64 {
142        u64::from_le((f.0).0)
143    }
144}
145
146/// A byte identifier, i.e. a change together with a position.
147#[derive(Debug, Clone, Copy, PartialEq, PartialOrd, Eq, Ord, Hash, Serialize, Deserialize)]
148#[doc(hidden)]
149#[repr(C)]
150pub struct Position<P> {
151    pub change: P,
152    pub pos: ChangePosition,
153}
154
155use super::Base32;
156
157impl<H: super::Base32> Base32 for Position<H> {
158    fn to_base32(&self) -> String {
159        let mut v = self.change.to_base32();
160        let mut bytes = [0; 8];
161        self.pos.0.to_slice_le(&mut bytes);
162        let mut i = 7;
163        while i > 2 && bytes[i] == 0 {
164            i -= 1
165        }
166        i += 1;
167        let len = BASE32.encode_len(i);
168        let len0 = v.len() + 1;
169        v.push_str("..............");
170        v.truncate(len0 + len);
171        BASE32.encode_mut(&bytes[..i], unsafe {
172            v.split_at_mut(len0).1.as_bytes_mut()
173        });
174        v
175    }
176    fn from_base32(s: &[u8]) -> Option<Self> {
177        let n = s.iter().position(|c| *c == b'.')?;
178        let (s, pos) = s.split_at(n);
179        let pos = &pos[1..];
180        let change = H::from_base32(s)?;
181        let mut dec = [0; 8];
182        let len = BASE32.decode_len(pos.len()).ok()?;
183        let pos = BASE32
184            .decode_mut(pos, &mut dec[..len])
185            .map(|_| L64::from_slice_le(&dec))
186            .ok()?;
187        Some(Position {
188            change,
189            pos: ChangePosition(pos),
190        })
191    }
192}
193
194pub mod position_base32_serde {
195    use super::*;
196    use serde::*;
197
198    pub struct PositionDe {}
199
200    impl<'de> serde::de::Visitor<'de> for PositionDe {
201        type Value = Position<ChangeId>;
202
203        fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
204            write!(formatter, "a base32-encoded string")
205        }
206
207        fn visit_str<E>(self, s: &str) -> Result<Self::Value, E>
208        where
209            E: de::Error,
210        {
211            if let Some(b) = Position::from_base32(s.as_bytes()) {
212                Ok(b)
213            } else {
214                Err(de::Error::invalid_value(
215                    serde::de::Unexpected::Str(s),
216                    &self,
217                ))
218            }
219        }
220    }
221
222    pub fn deserialize<'de, D: Deserializer<'de>>(d: D) -> Result<Position<ChangeId>, D::Error> {
223        d.deserialize_str(PositionDe {})
224    }
225
226    pub fn serialize<S: Serializer>(pos: &Position<ChangeId>, s: S) -> Result<S::Ok, S::Error> {
227        let b = pos.to_base32();
228        s.serialize_str(&b)
229    }
230}
231
232impl<H> std::ops::Add<usize> for Position<H> {
233    type Output = Position<H>;
234    fn add(self, x: usize) -> Self::Output {
235        Position {
236            change: self.change,
237            pos: self.pos + x,
238        }
239    }
240}
241
242impl<H> Position<Option<H>> {
243    pub fn unwrap(self) -> Position<H> {
244        Position {
245            change: self.change.unwrap(),
246            pos: self.pos,
247        }
248    }
249}
250
251impl<H> Vertex<Option<H>> {
252    pub fn unwrap(self) -> Vertex<H> {
253        Vertex {
254            change: self.change.unwrap(),
255            start: self.start,
256            end: self.end,
257        }
258    }
259}
260
261impl Position<ChangeId> {
262    pub fn inode_vertex(&self) -> Vertex<ChangeId> {
263        Vertex {
264            change: self.change,
265            start: self.pos,
266            end: self.pos,
267        }
268    }
269
270    pub fn is_root(&self) -> bool {
271        self.change.is_root()
272    }
273
274    pub fn to_option(&self) -> Position<Option<ChangeId>> {
275        Position {
276            change: Some(self.change),
277            pos: self.pos,
278        }
279    }
280
281    pub const ROOT: Position<ChangeId> = Position {
282        change: ChangeId::ROOT,
283        pos: ChangePosition(L64(0u64)),
284    };
285
286    pub(crate) const OPTION_ROOT: Position<Option<ChangeId>> = Position {
287        change: Some(ChangeId::ROOT),
288        pos: ChangePosition(L64(0u64)),
289    };
290
291    pub(crate) const BOTTOM: Position<ChangeId> = Position {
292        change: ChangeId::ROOT,
293        pos: ChangePosition::BOTTOM,
294    };
295}
pijul_core/pristine/vertex.rs

pijul_core/pristine/
vertex.rs
