vcsgraph/
graph.rs

1// SPDX-License-Identifier: GPL-2.0-or-later
2//
3// This software may be used and distributed according to the terms of the
4// GNU General Public License version 2 or any later version.
5//
6// Copyright 2020  Laurent Bulteau <laurent.bulteau@u-pem.fr>
7//                 Pierre-Yves David <pierre-yves.david@octobus.net>
8//                 Georges Racinet <georges.racinet@octobus.net>
9//                 Pacien TRAN-GIRARD <pacien.trangirard@pacien.net>
10
11use hex::{FromHex, FromHexError, ToHex};
12use std::convert::{AsRef, From};
13use std::fmt::{Debug, Display, Formatter};
14use std::iter::{FromIterator, IntoIterator};
15use std::ops::Add;
16use std::result::Result;
17use std::result::Result::Ok;
18use std::str::FromStr;
19use std::string::String;
20
21/// Mercurial revision numbers
22///
23/// As noted in mercurial's revlog.c, revision numbers are actually encoded in
24/// 4 bytes, and are liberally converted to ints, whence the i32
25pub type Revision = i32;
26
27/// Mercurial Node ID length
28///
29/// Note that the 20 bytes length is too strict as we will need 32 size for
30/// sha2 (or other newer hash).
31pub const NODE_ID_LEN: usize = 20;
32
33/// Mercurial Node ID
34#[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash)]
35pub struct NodeID(pub [u8; NODE_ID_LEN]);
36
37impl FromHex for NodeID {
38    type Error = FromHexError;
39
40    fn from_hex<T: AsRef<[u8]>>(hex: T) -> Result<Self, Self::Error> {
41        Ok(NodeID(<[u8; NODE_ID_LEN]>::from_hex(hex)?))
42    }
43}
44
45impl FromStr for NodeID {
46    type Err = FromHexError;
47
48    fn from_str(s: &str) -> Result<Self, Self::Err> {
49        FromHex::from_hex(s)
50    }
51}
52
53impl ToHex for NodeID {
54    fn encode_hex<T: FromIterator<char>>(&self) -> T {
55        self.0.encode_hex()
56    }
57
58    fn encode_hex_upper<T: FromIterator<char>>(&self) -> T {
59        self.0.encode_hex_upper()
60    }
61}
62
63impl Display for NodeID {
64    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
65        write!(f, "{}", self.0.encode_hex::<String>())
66    }
67}
68
69impl Debug for NodeID {
70    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
71        Display::fmt(self, f)
72    }
73}
74
75/// Marker expressing the absence of a parent
76///
77/// Independently of the actual representation, `NULL_REVISION` is guaranteed
78/// to be smaller than all existing revisions.
79pub const NULL_REVISION: Revision = -1;
80pub const NULL_ID: NodeID = NodeID([0; NODE_ID_LEN]);
81
82/// Rank of a node, i.e. its number of ancestors including itself.
83pub type Rank = usize;
84
85/// Parents revisions of a Node
86///
87/// In Mercurial, a node may have at most two parents.
88///
89/// This may later be replaced to support an arbitrary number of parents.
90#[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash, Debug)]
91pub struct Parents(pub [Revision; 2]);
92
93impl Parents {
94    pub fn contains(&self, rev: Revision) -> bool {
95        self.0[0] == rev || self.0[1] == rev
96    }
97}
98
99impl From<Parents> for [Revision; 2] {
100    fn from(parents: Parents) -> Self {
101        parents.0
102    }
103}
104
105impl IntoIterator for Parents {
106    type Item = Revision;
107    type IntoIter = std::vec::IntoIter<Self::Item>;
108
109    fn into_iter(self) -> Self::IntoIter {
110        match self.0 {
111            [NULL_REVISION, NULL_REVISION] => vec![],
112            [p1, NULL_REVISION] | [NULL_REVISION, p1] => vec![p1],
113            [p1, p2] => vec![p1, p2],
114        }
115        .into_iter()
116    }
117}
118
119#[derive(Clone, Copy, Debug, PartialEq, Eq)]
120pub enum GraphReadError {
121    InvalidKey,
122    KeyedInvalidKey(Revision), // TODO: split errors
123    InconsistentGraphData,
124    WorkingDirectoryUnsupported, // TODO: split errors
125}
126
127/// Graph that can be queried
128pub trait Graph {
129    fn parents(&self, rev: Revision) -> Result<Parents, GraphReadError>;
130
131    /// Tells whether the given Revision is a merge node,
132    /// i.e. it has two parents that are not NULL_REVISION.
133    fn is_merge(&self, rev: Revision) -> Result<bool, GraphReadError> {
134        Ok(match self.parents(rev)? {
135            Parents([_, NULL_REVISION]) | Parents([NULL_REVISION, _]) => false,
136            _ => true,
137        })
138    }
139}
140
141/// Graph with efficient revision rank retrieval
142pub trait RankedGraph {
143    fn rank(&self, rev: Revision) -> Result<Rank, GraphReadError>;
144}
145
146/// Graph with efficient revision merge-rank retrieval
147pub trait MergeRankedGraph {
148    /// Returns the number of merge nodes in the ancestors of the given
149    /// Revision, which includes itself.
150    fn merge_rank(&self, rev: Revision) -> Result<Rank, GraphReadError>;
151}
152
153impl<G: Graph> Graph for &G {
154    fn parents(&self, rev: Revision) -> Result<Parents, GraphReadError> {
155        (**self).parents(rev)
156    }
157}
158
159impl<G: RankedGraph> RankedGraph for &G {
160    fn rank(&self, rev: Revision) -> Result<Rank, GraphReadError> {
161        (**self).rank(rev)
162    }
163}
164
165impl<G: MergeRankedGraph> MergeRankedGraph for &G {
166    fn merge_rank(&self, rev: Revision) -> Result<Rank, GraphReadError> {
167        (**self).merge_rank(rev)
168    }
169}
170
171/// Graph with labelled nodes
172pub trait LabelledGraph {
173    fn rev_of_node_id(
174        &self,
175        node_id: NodeID,
176    ) -> Result<Revision, GraphReadError>;
177    fn node_id(&self, rev: Revision) -> Result<NodeID, GraphReadError>;
178}
179
180/// Graph with a known order (number of nodes).
181pub trait SizedGraph {
182    fn nb_nodes(&self) -> usize;
183}
184
185/// Graph with a stable node order.
186pub trait StableOrderGraph: Graph {
187    /// Sorts the given parents according to the intrinsic node order of the
188    /// graph.
189    ///
190    /// This can be used to order the parents of a node not yet present in
191    /// the graph. Non-existing parents must however be part of the graph.
192    fn sorted_parents(
193        &self,
194        parents: Parents,
195    ) -> Result<Parents, GraphReadError>;
196
197    /// Returns the Parents of a given Revision sorted by the intrinsic order
198    /// of the stable graph. Single-parents are always on the left.
199    fn ordered_parents(
200        &self,
201        rev: Revision,
202    ) -> Result<Parents, GraphReadError>;
203
204    /// Returns the ordered list of leaps to follow when walking over the
205    /// exclusive part. The list is empty for linear commits.
206    fn leaps(&self, rev: Revision) -> Result<&Vec<Leap>, GraphReadError>;
207
208    /// Returns Leap count tuple, i.e. the number of Leap-s to follow when
209    /// iterating over the ancestor set of a given Revision in an ordered way.
210    fn leap_counts(&self, rev: Revision)
211        -> Result<LeapCounts, GraphReadError>;
212
213    /// Returns p_min, the lower parent of a Revision with respect to the
214    /// intrinsic node order of the graph.
215    fn lower_parent(&self, rev: Revision) -> Result<Revision, GraphReadError> {
216        Ok(match self.ordered_parents(rev)? {
217            Parents([p, NULL_REVISION]) | Parents([NULL_REVISION, p]) => p,
218            Parents([p_min, _]) => p_min,
219        })
220    }
221
222    /// Returns p_max, the higher parent of a Revision with respect to the
223    /// intrinsic node order of the graph.
224    fn higher_parent(
225        &self,
226        rev: Revision,
227    ) -> Result<Revision, GraphReadError> {
228        Ok(match self.ordered_parents(rev)? {
229            Parents([p, NULL_REVISION]) | Parents([NULL_REVISION, p]) => p,
230            Parents([_, p_max]) => p_max,
231        })
232    }
233}
234
235#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
236pub enum LeapType {
237    /// Leap that preserves the ordered walk within the exclusive part.
238    Soft,
239
240    /// Leap that breaks the ordered walk within the exclusive part.
241    Hard,
242
243    /// Last leap ending the exclusive part.
244    Last,
245}
246
247#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
248pub struct Leap {
249    pub source: Revision,
250    pub target: Revision,
251    pub leap_type: LeapType,
252    pub since_previous: usize,
253    pub merges_since_previous: usize,
254}
255
256#[derive(Clone, Copy, Debug, PartialEq, Eq)]
257pub struct LeapCounts {
258    pub soft_leaps: usize,
259
260    /// Includes Hard and Last Leap types.
261    pub hard_leaps: usize,
262}
263
264impl Add for LeapCounts {
265    type Output = Self;
266    fn add(self, other: Self) -> Self {
267        LeapCounts {
268            soft_leaps: self.soft_leaps + other.soft_leaps,
269            hard_leaps: self.hard_leaps + other.hard_leaps,
270        }
271    }
272}
273
274#[derive(Clone, Copy, Debug, PartialEq, Eq)]
275pub enum GraphWriteError {
276    InvalidNodeID(NodeID),
277    UnknownParent(NodeID),
278    InvalidParents(NodeID),
279}
280
281/// Mutable graph in which nodes can be added
282pub trait MutableGraph {
283    /// Add a revision to the graph
284    ///
285    /// Absent parents are represented by `NULL_REVISION`.
286    fn push(
287        &mut self,
288        node_id: NodeID,
289        p1: NodeID,
290        p2: NodeID,
291    ) -> Result<Revision, GraphWriteError>;
292}
vcsgraph/graph.rs

vcsgraph/
graph.rs
