parsec/gossip/graph/
mod.rs

1// Copyright 2018 MaidSafe.net limited.
2//
3// This SAFE Network Software is licensed to you under The General Public License (GPL), version 3.
4// Unless required by applicable law or agreed to in writing, the SAFE Network Software distributed
5// under the GPL Licence is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
6// KIND, either express or implied. Please review the Licences for the specific language governing
7// permissions and limitations relating to use of the SAFE Network Software.
8
9mod ancestors;
10mod event_index;
11mod event_ref;
12
13#[cfg(any(all(test, feature = "mock"), feature = "testing"))]
14pub(crate) use self::ancestors::Ancestors;
15pub(crate) use self::{event_index::EventIndex, event_ref::IndexedEventRef};
16
17use super::{event::Event, event_hash::EventHash};
18use crate::id::PublicId;
19#[cfg(feature = "malice-detection")]
20use fnv::FnvHashSet;
21use std::collections::btree_map::{BTreeMap, Entry};
22#[cfg(any(all(test, feature = "mock"), feature = "testing"))]
23use std::collections::BTreeSet;
24
25/// The gossip graph.
26#[derive(Eq, PartialEq, Debug)]
27pub(crate) struct Graph<P: PublicId> {
28    events: Vec<Event<P>>,
29    indices: BTreeMap<EventHash, EventIndex>,
30    /// Indices of `Requesting` events with no associated descendant `Request`, and `Request`s with
31    /// no associated descendant `Response`.
32    #[cfg(feature = "malice-detection")]
33    awaiting_associated_events: FnvHashSet<EventIndex>,
34}
35
36impl<P: PublicId> Default for Graph<P> {
37    fn default() -> Self {
38        Self {
39            events: Vec::new(),
40            indices: BTreeMap::new(),
41            #[cfg(feature = "malice-detection")]
42            awaiting_associated_events: FnvHashSet::default(),
43        }
44    }
45}
46
47impl<P: PublicId> Graph<P> {
48    pub fn new() -> Self {
49        Self::default()
50    }
51
52    /// Get index of an event with the given hash.
53    pub fn get_index(&self, hash: &EventHash) -> Option<EventIndex> {
54        self.indices.get(hash).cloned()
55    }
56
57    /// Checks whether this graph contains an event with the given hash.
58    pub fn contains(&self, hash: &EventHash) -> bool {
59        self.indices.contains_key(hash)
60    }
61
62    /// Insert new event into the graph.
63    ///
64    /// Returns `IndexedEventRef` to the newly inserted event.
65    /// If the event was already present in the graph, does not overwrite it, just returns an
66    /// `IndexedEventRef` to it.
67    ///
68    /// If the event is a `Requesting` or `Request`, it is also added to
69    /// `awaiting_associated_events`.
70    ///
71    /// If the event is a `Request` or `Response`, the other_parent is removed from
72    /// `awaiting_associated_events`.
73    pub fn insert(&mut self, event: Event<P>) -> IndexedEventRef<P> {
74        let index = match self.indices.entry(*event.hash()) {
75            Entry::Occupied(entry) => *entry.get(),
76            Entry::Vacant(entry) => {
77                let index = EventIndex(self.events.len());
78
79                #[cfg(any(test, feature = "testing"))]
80                assert_ne!(index, EventIndex::PHONY);
81
82                self.events.push(event);
83                let _ = entry.insert(index);
84
85                #[cfg(feature = "malice-detection")]
86                self.update_awaiting(index);
87
88                index
89            }
90        };
91
92        IndexedEventRef {
93            index,
94            event: &self.events[index.0],
95        }
96    }
97
98    /// Gets `Event` with the given `index`, if it exists.
99    pub fn get(&self, index: EventIndex) -> Option<IndexedEventRef<P>> {
100        self.events
101            .get(index.0)
102            .map(|event| IndexedEventRef { index, event })
103    }
104
105    /// Gets `Event` by the given `hash`, if it exists.
106    #[cfg(any(feature = "malice-detection", feature = "dump-graphs"))]
107    pub fn get_by_hash<'a>(&'a self, hash: &EventHash) -> Option<IndexedEventRef<'a, P>> {
108        self.get_index(hash).and_then(|index| self.get(index))
109    }
110
111    /// Number of events in this graph.
112    pub fn len(&self) -> usize {
113        self.events.len()
114    }
115
116    /// Iterator over all events in this graph. Yields `IndexedEventRef`s.
117    pub fn iter(&self) -> Iter<P> {
118        self.iter_from(0)
119    }
120
121    /// Iterator over events in this graph starting at the given topological index.
122    pub fn iter_from(&self, start_index: usize) -> Iter<P> {
123        Iter {
124            events: &self.events,
125            index: start_index,
126        }
127    }
128
129    /// Iterator over event indices starting at the given topological index.
130    pub fn indices_from(&self, start_index: usize) -> impl Iterator<Item = EventIndex> {
131        (start_index..self.events.len()).map(EventIndex)
132    }
133
134    /// Returns self-parent of the given event, if any.
135    #[cfg(feature = "malice-detection")]
136    pub fn self_parent<E: AsRef<Event<P>>>(&self, event: E) -> Option<IndexedEventRef<P>> {
137        event
138            .as_ref()
139            .self_parent()
140            .and_then(|index| self.get(index))
141    }
142
143    /// Returns other-parent of the given event, if any.
144    #[cfg(feature = "malice-detection")]
145    pub fn other_parent<E: AsRef<Event<P>>>(&self, event: E) -> Option<IndexedEventRef<P>> {
146        event
147            .as_ref()
148            .other_parent()
149            .and_then(|index| self.get(index))
150    }
151
152    /// Returns the first self-parent of the given event, that is a sync_event.
153    pub fn self_sync_parent<E: AsRef<Event<P>>>(&self, event: E) -> Option<IndexedEventRef<P>> {
154        let mut event = event.as_ref();
155        while let Some(parent) = event.self_parent().and_then(|index| self.get(index)) {
156            if parent.is_sync_event() {
157                return Some(parent);
158            }
159            event = parent.inner();
160        }
161        None
162    }
163
164    /// Returns `event` if it's a sync event, or else `self_sync_parent()` of it otherwise.
165    #[cfg(feature = "malice-detection")]
166    pub fn self_sync_ancestor<'a>(
167        &'a self,
168        event: IndexedEventRef<'a, P>,
169    ) -> Option<IndexedEventRef<'a, P>> {
170        if event.is_sync_event() {
171            Some(event)
172        } else {
173            self.self_sync_parent(event)
174        }
175    }
176
177    /// Iterator over all ancestors of the given event (including itself) in reverse topological
178    /// order.
179    #[cfg(any(all(test, feature = "mock"), feature = "testing"))]
180    pub fn ancestors<'a>(&'a self, event: IndexedEventRef<'a, P>) -> Ancestors<'a, P> {
181        let mut queue = BTreeSet::new();
182        let _ = queue.insert(event);
183
184        Ancestors {
185            graph: self,
186            queue,
187            visited: vec![false; event.topological_index() + 1],
188        }
189    }
190}
191
192#[cfg(feature = "malice-detection")]
193impl<P: PublicId> Graph<P> {
194    /// Returns true if the event specified by `index` should eventually but still doesn't have an
195    /// associated `Request` or `Response` added to the graph.
196    pub fn is_awaiting_associated_event(&self, event: IndexedEventRef<P>) -> bool {
197        self.awaiting_associated_events.contains(&event.index)
198    }
199
200    /// Returns `Some(true)` if the event is a `Request` or `Response` and is valid (follows the
201    /// `Requesting -> Request -> Response` pattern).  Returns `Some(false)` if the event is a
202    /// `Request` or `Response` and is invalid.  Otherwise returns `None`.
203    pub fn is_valid_sync_event(&self, event: &Event<P>) -> Option<bool> {
204        if event.is_request() {
205            Some(
206                self.other_parent(event)
207                    .map(|requesting_event| {
208                        Some(event.creator()) == requesting_event.requesting_recipient()
209                            && self.is_awaiting_associated_event(requesting_event)
210                    })
211                    .unwrap_or(false),
212            )
213        } else if event.is_response() {
214            Some(
215                self.other_parent(event)
216                    .and_then(|other_parent| self.self_sync_ancestor(other_parent))
217                    .and_then(|request_event| {
218                        self.other_parent(request_event)
219                            .map(|requesting_event| (request_event, requesting_event))
220                    })
221                    .map(|(request_event, requesting_event)| {
222                        request_event.is_request()
223                            && requesting_event.creator() == event.creator()
224                            && self.is_awaiting_associated_event(request_event)
225                    })
226                    .unwrap_or(false),
227            )
228        } else {
229            None
230        }
231    }
232
233    fn awaiting_and_awaited_indices(
234        &self,
235        index: EventIndex,
236    ) -> (Option<EventIndex>, Option<EventIndex>) {
237        let event = &self.events[index.0];
238        if event.is_requesting() {
239            (Some(index), None)
240        } else if event.is_request() {
241            (
242                Some(index),
243                self.other_parent(event)
244                    .map(|other_parent| other_parent.index),
245            )
246        } else if event.is_response() {
247            (
248                None,
249                self.other_parent(event)
250                    .and_then(|other_parent| self.self_sync_ancestor(other_parent))
251                    .map(|self_sync_ancestor| self_sync_ancestor.index),
252            )
253        } else {
254            (None, None)
255        }
256    }
257
258    fn update_awaiting(&mut self, index: EventIndex) {
259        let (awaiting, awaited) = self.awaiting_and_awaited_indices(index);
260        let _ = awaiting.map(|awaiting| self.awaiting_associated_events.insert(awaiting));
261        let _ = awaited.map(|awaited| self.awaiting_associated_events.remove(&awaited));
262    }
263}
264
265#[cfg(any(all(test, feature = "mock"), feature = "testing"))]
266impl<P: PublicId> Graph<P> {
267    /// Remove the topologically last event.
268    #[cfg(test)]
269    pub fn remove_last(&mut self) -> Option<(EventIndex, Event<P>)> {
270        let index = EventIndex(self.events.len() - 1);
271        #[cfg(feature = "malice-detection")]
272        {
273            let (awaiting, awaited) = self.awaiting_and_awaited_indices(index);
274            let _ = awaiting.map(|awaiting| self.awaiting_associated_events.remove(&awaiting));
275            let _ = awaited.map(|awaited| self.awaiting_associated_events.insert(awaited));
276        }
277        let event = self.events.pop()?;
278        let _ = self.indices.remove(event.hash());
279        Some((index, event))
280    }
281}
282
283#[cfg(all(test, feature = "mock"))]
284impl<P: PublicId> Graph<P> {
285    /// Finds the first event which has the `short_name` provided.
286    pub fn find_by_short_name<'a>(&'a self, short_name: &str) -> Option<IndexedEventRef<'a, P>> {
287        let short_name = short_name.to_uppercase();
288
289        if let Some(sep) = short_name.find(',') {
290            let just_short_name = &short_name[0..sep];
291            let fork_index: usize = unwrap!(short_name[(sep + 1)..].parse());
292
293            self.iter().find(|event| {
294                event.short_name().to_string() == just_short_name
295                    && event
296                        .fork_set()
297                        .map(|set| set.contains(fork_index))
298                        .unwrap_or(fork_index == 0)
299            })
300        } else {
301            self.iter()
302                .find(move |event| event.short_name().to_string() == short_name)
303        }
304    }
305}
306
307impl<P: PublicId> IntoIterator for Graph<P> {
308    type IntoIter = IntoIter<P>;
309    type Item = <Self::IntoIter as Iterator>::Item;
310
311    fn into_iter(self) -> Self::IntoIter {
312        let mut events = self.events;
313        events.reverse();
314
315        IntoIter { events, index: 0 }
316    }
317}
318
319pub(crate) struct IntoIter<P: PublicId> {
320    events: Vec<Event<P>>,
321    index: usize,
322}
323
324impl<P: PublicId> Iterator for IntoIter<P> {
325    type Item = (EventIndex, Event<P>);
326
327    fn next(&mut self) -> Option<Self::Item> {
328        if let Some(event) = self.events.pop() {
329            let item = (EventIndex(self.index), event);
330            self.index += 1;
331            Some(item)
332        } else {
333            None
334        }
335    }
336}
337
338impl<'a, P: PublicId> IntoIterator for &'a Graph<P> {
339    type IntoIter = Iter<'a, P>;
340    type Item = <Self::IntoIter as Iterator>::Item;
341
342    fn into_iter(self) -> Self::IntoIter {
343        Iter {
344            events: &self.events,
345            index: 0,
346        }
347    }
348}
349
350pub(crate) struct Iter<'a, P: PublicId + 'a> {
351    events: &'a [Event<P>],
352    index: usize,
353}
354
355impl<'a, P: PublicId> Iterator for Iter<'a, P> {
356    type Item = IndexedEventRef<'a, P>;
357
358    fn next(&mut self) -> Option<Self::Item> {
359        let event = self.events.get(self.index)?;
360        let item = IndexedEventRef {
361            index: EventIndex(self.index),
362            event,
363        };
364        self.index += 1;
365        Some(item)
366    }
367}
368
369#[cfg(any(all(test, feature = "mock"), feature = "dump-graphs"))]
370pub(crate) mod snapshot {
371    use super::*;
372    use std::collections::BTreeSet;
373
374    /// Snapshot of the graph. Two snapshots compare as equal if the graphs had the same events
375    /// modulo their insertion order.
376    #[derive(Eq, PartialEq, Debug, Serialize, Deserialize)]
377    pub(crate) struct GraphSnapshot(pub BTreeSet<EventHash>);
378
379    impl GraphSnapshot {
380        pub fn new<P: PublicId>(graph: &Graph<P>) -> Self {
381            Self::new_with_ignore(graph, 0)
382        }
383
384        /// Generate a snapshot without the last `ignore_last_events` events
385        pub fn new_with_ignore<P: PublicId>(graph: &Graph<P>, ignore_last_events: usize) -> Self {
386            GraphSnapshot(
387                graph
388                    .iter()
389                    .map(|event| *event.hash())
390                    .take(graph.len() - ignore_last_events)
391                    .collect(),
392            )
393        }
394    }
395}
396
397#[cfg(all(test, feature = "testing"))]
398mod tests {
399    use crate::dev_utils::parse_test_dot_file;
400    use std::cmp::Reverse;
401
402    #[test]
403    fn ancestors_iterator() {
404        // Generated with RNG seed: [174994228, 1445633118, 3041276290, 90293447].
405        let contents = parse_test_dot_file("carol.dot");
406        let graph = contents.graph;
407
408        let event = unwrap!(graph.find_by_short_name("C_8"));
409
410        let expected = vec![
411            "C_8", "C_7", "D_14", "B_26", "B_25", "B_24", "A_18", "B_23", "B_22", "D_13", "B_21",
412            "D_12", "D_11", "B_20", "B_19", "A_17", "B_18", "A_16", "A_15", "D_10", "B_17", "B_16",
413            "A_14", "B_15", "B_14", "D_9", "D_8", "A_13", "A_12", "A_11", "A_10", "D_7", "D_6",
414            "B_13", "A_9", "A_8", "D_5", "B_12", "B_11", "B_10", "C_6", "B_9", "B_8", "D_4", "D_3",
415            "A_7", "C_5", "C_4", "A_6", "A_5", "A_4", "D_2", "D_1", "D_0", "B_7", "B_6", "B_5",
416            "B_4", "A_3", "B_3", "C_3", "C_2", "B_2", "B_1", "B_0", "A_2", "A_1", "A_0", "C_1",
417            "C_0",
418        ];
419
420        let mut actual_names = Vec::new();
421        let mut actual_indices = Vec::new();
422
423        for event in graph.ancestors(event) {
424            actual_names.push(event.short_name().to_string());
425            actual_indices.push(event.event_index());
426        }
427
428        assert_eq!(actual_names, expected);
429
430        // Assert the events are yielded in reverse topological order.
431        let mut sorted_indices = actual_indices.clone();
432        sorted_indices.sort_by_key(|&b| Reverse(b));
433
434        assert_eq!(actual_indices, sorted_indices);
435    }
436}
parsec/gossip/graph/mod.rs

parsec/gossip/graph/
mod.rs
