1 //! Traits for describing strong and weak pointers and their use as elements and keys.
2 //!
3 //! These traits provide mechanisms for converting between weak and strong pointers
4 //! ([`WeakElement`](trait.WeakElement.html)) and for dereferencing strong pointers
5 //! ([`WeakKey`](trait.WeakKey.html)). Implementations of these traits are provided for
6 //! `std::rc::Weak` and `std::sync::Weak`. If you would like to use your own pointer type
7 //! as a weak element, you need to implement `WeakElement` for your weak pointer type; to use it
8 //! as a weak key, implement `WeakKey` as well.
9 
10 use crate::compat::*;
11 
12 /// Interface for elements that can be stored in weak hash tables.
13 ///
14 /// This trait applies to the weak version of a reference-counted pointer; it can be used to
15 /// convert a weak pointer into a strong pointer and back. For example, the impl for
16 /// `std::rc::Weak<T>` defines the `Strong` associated type as `std::rc::Rc<T>`. Then method
17 /// `new` can be used to downgrade an `Rc<T>` to a `Weak<T>`, and method `view` can be used to
18 /// upgrade a `Weak<T>` into an `Rc<T>`, if it's still alive. If we think of the weak pointer as
19 /// what is stored, then the strong pointer is a temporary view of it.
20 pub trait WeakElement {
21     /// The type at which a weak element can be viewed.
22     ///
23     /// For example, for `std::rc::Weak<T>`, this will be `std::rc::Rc<T>`.
24     type Strong;
25 
26     /// Constructs a weak pointer from a strong pointer.
27     ///
28     /// This is usually implemented by a `downgrade` method.
new(view: &Self::Strong) -> Self29     fn new(view: &Self::Strong) -> Self;
30 
31     /// Acquires a strong pointer from a weak pointer.
32     ///
33     /// This is usually implemented by an `upgrade` method.
view(&self) -> Option<Self::Strong>34     fn view(&self) -> Option<Self::Strong>;
35 
36     /// Is the given weak element expired?
37     ///
38     /// The default implemention checks whether a strong pointer can be obtained via `view`.
is_expired(&self) -> bool39     fn is_expired(&self) -> bool {
40         self.view().is_none()
41     }
42 
43     /// Clones a strong pointer.
44     ///
45     /// The default implementation uses `new` and `view`; you should override it.
clone(view: &Self::Strong) -> Self::Strong where Self: Sized46     fn clone(view: &Self::Strong) -> Self::Strong
47         where Self: Sized
48     {
49         Self::new(view).view().expect("WeakElement::clone")
50     }
51 }
52 
53 /// Interface for elements that can act as keys in weak hash tables.
54 ///
55 /// To use an element as a weak hash map key or weak hash set element), the hash table
56 /// needs to be able to view the actual key values to hash and compare them. This trait
57 /// provides the necessary mechanism.
58 pub trait WeakKey : WeakElement {
59     /// The underlying key type.
60     ///
61     /// For example, for `std::rc::Weak<T>`, this will be `T`.
62     type Key: ?Sized + Eq + Hash;
63 
64     /// Allows borrowing a view of the key, via a callback.
65     ///
66     /// Rather than returning a borrowed reference to the actual key, this method passes a
67     /// reference to the key to a callback with an implicit higher-order lifetime bound. This is
68     /// necessary to get the lifetimes right in cases where the key is not actually store in the
69     /// strong pointer.
with_key<F, R>(view: &Self::Strong, f: F) -> R where F: FnOnce(&Self::Key) -> R70     fn with_key<F, R>(view: &Self::Strong, f: F) -> R
71         where F: FnOnce(&Self::Key) -> R;
72 
73     /// Hashes the key `view` into the given `Hasher`.
hash<H: Hasher>(view: &Self::Strong, h: &mut H)74     fn hash<H: Hasher>(view: &Self::Strong, h: &mut H) {
75         Self::with_key(view, |k| k.hash(h));
76     }
77 
78     /// Returns whether the key `view` equals the given `key`.
equals<Q>(view: &Self::Strong, key: &Q) -> bool where Q: ?Sized + Eq, Self::Key: Borrow<Q>79     fn equals<Q>(view: &Self::Strong, key: &Q) -> bool
80         where Q: ?Sized + Eq,
81               Self::Key: Borrow<Q>
82     {
83         Self::with_key(view, |k| k.borrow() == key)
84     }
85 }
86 
87 impl<T: ?Sized> WeakElement for rc::Weak<T> {
88     type Strong = rc::Rc<T>;
89 
new(view: &Self::Strong) -> Self90     fn new(view: &Self::Strong) -> Self {
91         rc::Rc::<T>::downgrade(view)
92     }
93 
view(&self) -> Option<Self::Strong>94     fn view(&self) -> Option<Self::Strong> {
95         self.upgrade()
96     }
97 
clone(view: &Self::Strong) -> Self::Strong98     fn clone(view: &Self::Strong) -> Self::Strong {
99         view.clone()
100     }
101 }
102 
103 impl<T: ?Sized + Eq + Hash> WeakKey for rc::Weak<T> {
104     type Key = T;
105 
with_key<F, R>(view: &Self::Strong, f: F) -> R where F: FnOnce(&Self::Key) -> R106     fn with_key<F, R>(view: &Self::Strong, f: F) -> R
107         where F: FnOnce(&Self::Key) -> R
108     {
109         f(view)
110     }
111 }
112 
113 impl<T: ?Sized> WeakElement for sync::Weak<T> {
114     type Strong = sync::Arc<T>;
115 
new(view: &Self::Strong) -> Self116     fn new(view: &Self::Strong) -> Self {
117         sync::Arc::<T>::downgrade(view)
118     }
119 
view(&self) -> Option<Self::Strong>120     fn view(&self) -> Option<Self::Strong> {
121         self.upgrade()
122     }
123 
clone(view: &Self::Strong) -> Self::Strong124     fn clone(view: &Self::Strong) -> Self::Strong {
125         view.clone()
126     }
127 }
128 
129 impl<T: ?Sized + Eq + Hash> WeakKey for sync::Weak<T>
130 {
131     type Key = T;
132 
with_key<F, R>(view: &Self::Strong, f: F) -> R where F: FnOnce(&Self::Key) -> R133     fn with_key<F, R>(view: &Self::Strong, f: F) -> R
134         where F: FnOnce(&Self::Key) -> R
135     {
136         f(view)
137     }
138 }
139 
140