sp_npos_elections/
node.rs

1// This file is part of Substrate.
2
3// Copyright (C) Parity Technologies (UK) Ltd.
4// SPDX-License-Identifier: Apache-2.0
5
6// Licensed under the Apache License, Version 2.0 (the "License");
7// you may not use this file except in compliance with the License.
8// You may obtain a copy of the License at
9//
10// 	http://www.apache.org/licenses/LICENSE-2.0
11//
12// Unless required by applicable law or agreed to in writing, software
13// distributed under the License is distributed on an "AS IS" BASIS,
14// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15// See the License for the specific language governing permissions and
16// limitations under the License.
17
18//! (very) Basic implementation of a graph node used in the reduce algorithm.
19
20use alloc::{rc::Rc, vec::Vec};
21use core::{cell::RefCell, fmt};
22
23/// The role that a node can accept.
24#[derive(PartialEq, Eq, Ord, PartialOrd, Clone, Debug)]
25pub(crate) enum NodeRole {
26	/// A voter. This is synonym to a nominator in a staking context.
27	Voter,
28	/// A target. This is synonym to a candidate/validator in a staking context.
29	Target,
30}
31
32pub(crate) type RefCellOf<T> = Rc<RefCell<T>>;
33pub(crate) type NodeRef<A> = RefCellOf<Node<A>>;
34
35/// Identifier of a node. This is particularly handy to have a proper `PartialEq` implementation.
36/// Otherwise, self votes wouldn't have been indistinguishable.
37#[derive(PartialOrd, Ord, Clone, PartialEq, Eq)]
38pub(crate) struct NodeId<A> {
39	/// An account-like identifier representing the node.
40	pub who: A,
41	/// The role of the node.
42	pub role: NodeRole,
43}
44
45impl<A> NodeId<A> {
46	/// Create a new [`NodeId`].
47	pub fn from(who: A, role: NodeRole) -> Self {
48		Self { who, role }
49	}
50}
51
52#[cfg(feature = "std")]
53impl<A: fmt::Debug> fmt::Debug for NodeId<A> {
54	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
55		write!(
56			f,
57			"Node({:?}, {:?})",
58			self.who,
59			if self.role == NodeRole::Voter { "V" } else { "T" }
60		)
61	}
62}
63
64/// A one-way graph note. This can only store a pointer to its parent.
65#[derive(Clone)]
66pub(crate) struct Node<A> {
67	/// The identifier of the note.
68	pub(crate) id: NodeId<A>,
69	/// The parent pointer.
70	pub(crate) parent: Option<NodeRef<A>>,
71}
72
73impl<A: PartialEq> PartialEq for Node<A> {
74	fn eq(&self, other: &Node<A>) -> bool {
75		self.id == other.id
76	}
77}
78
79impl<A: PartialEq> Eq for Node<A> {}
80
81#[cfg(feature = "std")]
82impl<A: fmt::Debug + Clone> fmt::Debug for Node<A> {
83	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
84		write!(f, "({:?} --> {:?})", self.id, self.parent.as_ref().map(|p| p.borrow().id.clone()))
85	}
86}
87
88impl<A: PartialEq + Eq + Clone + fmt::Debug> Node<A> {
89	/// Create a new [`Node`]
90	pub fn new(id: NodeId<A>) -> Node<A> {
91		Self { id, parent: None }
92	}
93
94	/// Returns true if `other` is the parent of `who`.
95	pub fn is_parent_of(who: &NodeRef<A>, other: &NodeRef<A>) -> bool {
96		if who.borrow().parent.is_none() {
97			return false
98		}
99		who.borrow().parent.as_ref() == Some(other)
100	}
101
102	/// Removes the parent of `who`.
103	pub fn remove_parent(who: &NodeRef<A>) {
104		who.borrow_mut().parent = None;
105	}
106
107	/// Sets `who`'s parent to be `parent`.
108	pub fn set_parent_of(who: &NodeRef<A>, parent: &NodeRef<A>) {
109		who.borrow_mut().parent = Some(parent.clone());
110	}
111
112	/// Finds the root of `start`. It return a tuple of `(root, root_vec)` where `root_vec` is the
113	/// vector of Nodes leading to the root. Hence the first element is the start itself and the
114	/// last one is the root. As convenient, the root itself is also returned as the first element
115	/// of the tuple.
116	///
117	/// This function detects cycles and breaks as soon a duplicate node is visited, returning the
118	/// cycle up to but not including the duplicate node.
119	///
120	/// If you are certain that no cycles exist, you can use [`root_unchecked`].
121	pub fn root(start: &NodeRef<A>) -> (NodeRef<A>, Vec<NodeRef<A>>) {
122		let mut parent_path: Vec<NodeRef<A>> = Vec::new();
123		let mut visited: Vec<NodeRef<A>> = Vec::new();
124
125		parent_path.push(start.clone());
126		visited.push(start.clone());
127		let mut current = start.clone();
128
129		while let Some(ref next_parent) = current.clone().borrow().parent {
130			if visited.contains(next_parent) {
131				break
132			}
133			parent_path.push(next_parent.clone());
134			current = next_parent.clone();
135			visited.push(current.clone());
136		}
137
138		(current, parent_path)
139	}
140
141	/// Consumes self and wraps it in a `Rc<RefCell<T>>`. This type can be used as the pointer type
142	/// to a parent node.
143	pub fn into_ref(self) -> NodeRef<A> {
144		Rc::from(RefCell::from(self))
145	}
146}
147
148#[cfg(test)]
149mod tests {
150	use super::*;
151
152	fn id(i: u32) -> NodeId<u32> {
153		NodeId::from(i, NodeRole::Target)
154	}
155
156	#[test]
157	fn basic_create_works() {
158		let node = Node::new(id(10));
159		assert_eq!(node, Node { id: NodeId { who: 10, role: NodeRole::Target }, parent: None });
160	}
161
162	#[test]
163	fn set_parent_works() {
164		let a = Node::new(id(10)).into_ref();
165		let b = Node::new(id(20)).into_ref();
166
167		assert_eq!(a.borrow().parent, None);
168		Node::set_parent_of(&a, &b);
169		assert_eq!(*a.borrow().parent.as_ref().unwrap(), b);
170	}
171
172	#[test]
173	fn get_root_singular() {
174		let a = Node::new(id(1)).into_ref();
175		assert_eq!(Node::root(&a), (a.clone(), vec![a.clone()]));
176	}
177
178	#[test]
179	fn get_root_works() {
180		// 	D <-- A <-- B <-- C
181		// 			\
182		// 			 <-- E
183		let a = Node::new(id(1)).into_ref();
184		let b = Node::new(id(2)).into_ref();
185		let c = Node::new(id(3)).into_ref();
186		let d = Node::new(id(4)).into_ref();
187		let e = Node::new(id(5)).into_ref();
188		let f = Node::new(id(6)).into_ref();
189
190		Node::set_parent_of(&c, &b);
191		Node::set_parent_of(&b, &a);
192		Node::set_parent_of(&e, &a);
193		Node::set_parent_of(&a, &d);
194
195		assert_eq!(Node::root(&e), (d.clone(), vec![e.clone(), a.clone(), d.clone()]));
196
197		assert_eq!(Node::root(&a), (d.clone(), vec![a.clone(), d.clone()]));
198
199		assert_eq!(Node::root(&c), (d.clone(), vec![c.clone(), b.clone(), a.clone(), d.clone()]));
200
201		// 	D 	    A <-- B <-- C
202		// 	F <-- /	\
203		// 			 <-- E
204		Node::set_parent_of(&a, &f);
205
206		assert_eq!(Node::root(&a), (f.clone(), vec![a.clone(), f.clone()]));
207
208		assert_eq!(Node::root(&c), (f.clone(), vec![c.clone(), b.clone(), a.clone(), f.clone()]));
209	}
210
211	#[test]
212	fn get_root_on_cycle() {
213		// A ---> B
214		// |      |
215		//  <---- C
216		let a = Node::new(id(1)).into_ref();
217		let b = Node::new(id(2)).into_ref();
218		let c = Node::new(id(3)).into_ref();
219
220		Node::set_parent_of(&a, &b);
221		Node::set_parent_of(&b, &c);
222		Node::set_parent_of(&c, &a);
223
224		let (root, path) = Node::root(&a);
225		assert_eq!(root, c);
226		assert_eq!(path.clone(), vec![a.clone(), b.clone(), c.clone()]);
227	}
228
229	#[test]
230	fn get_root_on_cycle_2() {
231		// A ---> B
232		// |   |  |
233		//     - C
234		let a = Node::new(id(1)).into_ref();
235		let b = Node::new(id(2)).into_ref();
236		let c = Node::new(id(3)).into_ref();
237
238		Node::set_parent_of(&a, &b);
239		Node::set_parent_of(&b, &c);
240		Node::set_parent_of(&c, &b);
241
242		let (root, path) = Node::root(&a);
243		assert_eq!(root, c);
244		assert_eq!(path.clone(), vec![a.clone(), b.clone(), c.clone()]);
245	}
246
247	#[test]
248	fn node_cmp_stack_overflows_on_non_unique_elements() {
249		// To make sure we don't stack overflow on duplicate who. This needs manual impl of
250		// PartialEq.
251		let a = Node::new(id(1)).into_ref();
252		let b = Node::new(id(2)).into_ref();
253		let c = Node::new(id(3)).into_ref();
254
255		Node::set_parent_of(&a, &b);
256		Node::set_parent_of(&b, &c);
257		Node::set_parent_of(&c, &a);
258
259		Node::root(&a);
260	}
261}
sp_npos_elections/node.rs

sp_npos_elections/
node.rs
