vcsgraph/testing/
graph_in_mem.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 crate::ancestors::node_leaps;
12use crate::graph::{
13    Graph, GraphReadError, GraphWriteError, LabelledGraph, Leap, LeapCounts,
14    LeapType, MergeRankedGraph, MutableGraph, NodeID, Parents, Rank,
15    RankedGraph, Revision, SizedGraph, StableOrderGraph, NULL_ID,
16    NULL_REVISION,
17};
18use crate::testing::ordering::NodeComparator;
19use std::cmp::Ordering;
20use std::collections::HashMap;
21use std::marker::PhantomData;
22use std::option::Option::Some;
23use std::result::Result;
24use std::result::Result::{Err, Ok};
25use std::vec::Vec;
26
27/// Node
28///
29/// A single revision node.
30#[derive(Clone, Debug, PartialEq, Eq)]
31struct Node {
32    rev: Revision,
33    id: NodeID,
34    parents: Parents,
35    rank: Rank,
36    merge_rank: Rank,
37    leap_counts: LeapCounts,
38    leaps: Vec<Leap>,
39}
40
41/// Fully in-memory representation of a graph
42#[derive(Clone, Debug)]
43pub struct InMemoryGraph<C: NodeComparator> {
44    _node_comparator: PhantomData<C>,
45    _empty_leap_vec: Vec<Leap>,
46    /// Nodes indexed by Revision
47    nodes: Vec<Node>,
48    rev_map: HashMap<NodeID, Revision>,
49}
50
51impl<C: NodeComparator> InMemoryGraph<C> {
52    pub fn new() -> Self {
53        let mut graph = Self {
54            _node_comparator: PhantomData,
55            _empty_leap_vec: Vec::with_capacity(0),
56            nodes: Vec::new(),
57            rev_map: HashMap::new(),
58        };
59        graph.rev_map.insert(NULL_ID, NULL_REVISION);
60        graph
61    }
62
63    fn get_by_revision(&self, rev: Revision) -> Result<Node, GraphReadError> {
64        match self.nodes.get(rev as usize) {
65            Some(node) => Ok(node.clone()),
66            None => Err(GraphReadError::InvalidKey),
67        }
68    }
69}
70
71impl<C: NodeComparator> Graph for InMemoryGraph<C> {
72    fn parents(&self, rev: Revision) -> Result<Parents, GraphReadError> {
73        Ok(match rev {
74            NULL_REVISION => Parents([NULL_REVISION, NULL_REVISION]),
75            r => self.get_by_revision(r)?.parents,
76        })
77    }
78}
79
80impl<C: NodeComparator> RankedGraph for InMemoryGraph<C> {
81    fn rank(&self, rev: Revision) -> Result<Rank, GraphReadError> {
82        Ok(match rev {
83            NULL_REVISION => 0,
84            r => self.get_by_revision(r)?.rank,
85        })
86    }
87}
88
89impl<C: NodeComparator> MergeRankedGraph for InMemoryGraph<C> {
90    fn merge_rank(&self, rev: Revision) -> Result<Rank, GraphReadError> {
91        Ok(match rev {
92            NULL_REVISION => 0,
93            r => self.get_by_revision(r)?.merge_rank,
94        })
95    }
96}
97
98impl<C: NodeComparator> LabelledGraph for InMemoryGraph<C> {
99    fn rev_of_node_id(
100        &self,
101        node_id: NodeID,
102    ) -> Result<Revision, GraphReadError> {
103        self.rev_map
104            .get(&node_id)
105            .cloned()
106            .ok_or(GraphReadError::InvalidKey)
107    }
108
109    fn node_id(&self, rev: Revision) -> Result<NodeID, GraphReadError> {
110        Ok(self.get_by_revision(rev)?.id)
111    }
112}
113
114impl<C: NodeComparator> SizedGraph for InMemoryGraph<C> {
115    fn nb_nodes(&self) -> usize {
116        self.nodes.len()
117    }
118}
119
120impl<C: NodeComparator> StableOrderGraph for InMemoryGraph<C> {
121    fn sorted_parents(
122        &self,
123        parents: Parents,
124    ) -> Result<Parents, GraphReadError> {
125        Ok(Parents(match parents {
126            Parents([p, NULL_REVISION]) | Parents([NULL_REVISION, p]) => {
127                [p, NULL_REVISION]
128            }
129            Parents([p1, p2]) => {
130                if C::compare(self, p1, p2)? == Ordering::Less {
131                    [p1, p2]
132                } else {
133                    [p2, p1]
134                }
135            }
136        }))
137    }
138
139    fn ordered_parents(
140        &self,
141        rev: Revision,
142    ) -> Result<Parents, GraphReadError> {
143        self.sorted_parents(self.parents(rev)?)
144    }
145
146    fn leaps(&self, rev: Revision) -> Result<&Vec<Leap>, GraphReadError> {
147        match rev {
148            NULL_REVISION => Ok(&self._empty_leap_vec),
149            r => Ok(&self.nodes[r as usize].leaps),
150        }
151    }
152
153    fn leap_counts(
154        &self,
155        rev: Revision,
156    ) -> Result<LeapCounts, GraphReadError> {
157        Ok(match rev {
158            NULL_REVISION => LeapCounts {
159                soft_leaps: 0,
160                hard_leaps: 0,
161            },
162            r => self.nodes[r as usize].leap_counts,
163        })
164    }
165}
166
167fn count_leaps(leaps: &[Leap]) -> LeapCounts {
168    let mut leap_counts = LeapCounts {
169        soft_leaps: 0,
170        hard_leaps: 0,
171    };
172
173    for leap in leaps {
174        match leap.leap_type {
175            LeapType::Soft => leap_counts.soft_leaps += 1,
176            LeapType::Hard | LeapType::Last => leap_counts.hard_leaps += 1,
177        }
178    }
179
180    leap_counts
181}
182
183fn make_node<C: NodeComparator>(
184    graph: &InMemoryGraph<C>,
185    parents: Parents,
186    node_id: NodeID,
187    rev: Revision,
188) -> Result<Node, GraphReadError> {
189    let Parents([p_min, p_max]) = graph.sorted_parents(parents)?;
190    let leap_info = node_leaps(graph, rev, &parents)?;
191    let exclusive_merge_rank = if p_max == NULL_REVISION {
192        0
193    } else {
194        1 + leap_info.exclusive_merge_count
195    };
196
197    Ok(Node {
198        rev,
199        id: node_id,
200        parents,
201        rank: 1 + leap_info.exclusive_part_size + graph.rank(p_min)?,
202        merge_rank: exclusive_merge_rank + graph.merge_rank(p_min)?,
203        leap_counts: count_leaps(&leap_info.leaps)
204            + graph.leap_counts(p_min)?,
205        leaps: leap_info.leaps,
206    })
207}
208
209impl<C: NodeComparator> MutableGraph for InMemoryGraph<C> {
210    fn push(
211        &mut self,
212        node_id: NodeID,
213        p1: NodeID,
214        p2: NodeID,
215    ) -> Result<Revision, GraphWriteError> {
216        let parents = Parents([self.rev_map[&p1], self.rev_map[&p2]]);
217        let rev = self.nodes.len() as Revision;
218        let node = make_node(self, parents, node_id, rev)
219            .map_err(|_| GraphWriteError::InvalidParents(node_id))?;
220
221        self.rev_map.insert(node_id, rev);
222        self.nodes.push(node);
223        Ok(rev)
224    }
225}
226
227#[cfg(test)]
228mod tests {
229    use crate::graph::{
230        Graph, MutableGraph, NodeID, Parents, RankedGraph, SizedGraph,
231        NODE_ID_LEN, NULL_ID, NULL_REVISION,
232    };
233    use crate::testing::graph_in_mem::InMemoryGraph;
234    use crate::testing::ordering::NodeIDComparator;
235    use std::iter::Iterator;
236    use std::vec::Vec;
237
238    #[test]
239    fn test_simple_in_memory_graph() {
240        let node: Vec<NodeID> =
241            (0..=6).map(|i| NodeID([i + 1; NODE_ID_LEN])).collect();
242
243        let mut graph = InMemoryGraph::<NodeIDComparator>::new();
244        graph.push(node[0], NULL_ID, NULL_ID).unwrap();
245        graph.push(node[1], node[0], NULL_ID).unwrap();
246        graph.push(node[2], node[0], NULL_ID).unwrap();
247        graph.push(node[3], node[1], NULL_ID).unwrap();
248        graph.push(node[4], node[3], node[2]).unwrap();
249        graph.push(node[5], node[4], NULL_ID).unwrap();
250        graph.push(node[6], node[3], NULL_ID).unwrap();
251
252        assert_eq!(graph.nb_nodes(), 7);
253
254        assert_eq!(
255            graph.parents(NULL_REVISION).unwrap(),
256            Parents([NULL_REVISION, NULL_REVISION])
257        );
258        assert_eq!(graph.rank(NULL_REVISION).unwrap(), 0);
259
260        let r0 = graph.get_by_revision(0).unwrap();
261        assert_eq!(r0.rev, 0);
262        assert_eq!(r0.id, node[0]);
263        assert_eq!(r0.parents, Parents([NULL_REVISION, NULL_REVISION]));
264        assert_eq!(r0.rank, 1);
265        assert_eq!(r0.merge_rank, 0);
266        assert_eq!(r0.leap_counts.soft_leaps, 0);
267        assert_eq!(r0.leap_counts.hard_leaps, 0);
268
269        let r4 = graph.get_by_revision(4).unwrap();
270        assert_eq!(r4.rev, 4);
271        assert_eq!(r4.id, node[4]);
272        assert_eq!(r4.parents, Parents([3, 2]));
273        assert_eq!(r4.rank, 5);
274        assert_eq!(r4.merge_rank, 1);
275        assert_eq!(r4.leap_counts.soft_leaps, 0);
276        assert_eq!(r4.leap_counts.hard_leaps, 1);
277
278        let r6 = graph.get_by_revision(6).unwrap();
279        assert_eq!(r6.rev, 6);
280        assert_eq!(r6.id, node[6]);
281        assert_eq!(r6.parents, Parents([3, NULL_REVISION]));
282        assert_eq!(graph.parents(6).unwrap(), Parents([3, NULL_REVISION]));
283        assert_eq!(r6.rank, 4);
284        assert_eq!(r6.merge_rank, 0);
285        assert_eq!(r6.leap_counts.soft_leaps, 0);
286        assert_eq!(r6.leap_counts.hard_leaps, 0);
287    }
288}
vcsgraph/testing/graph_in_mem.rs

vcsgraph/testing/
graph_in_mem.rs
