1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

//! Traits for describing strong and weak pointers and their use as elements and keys.
//!
//! These traits provide mechanisms for converting between weak and strong pointers
//! ([`WeakElement`](trait.WeakElement.html)) and for dereferencing strong pointers
//! ([`WeakKey`](trait.WeakKey.html)). Implementations of these traits are provided for
//! `std::rc::Weak` and `std::sync::Weak`. If you would like to use your own pointer type
//! as a weak element, you need to implement `WeakElement` for your weak pointer type; to use it
//! as a weak key, implement `WeakKey` as well.

use crate::compat::*;

/// Interface for elements that can be stored in weak hash tables.
///
/// This trait applies to the weak version of a reference-counted pointer; it can be used to
/// convert a weak pointer into a strong pointer and back. For example, the impl for
/// `std::rc::Weak<T>` defines the `Strong` associated type as `std::rc::Rc<T>`. Then method
/// `new` can be used to downgrade an `Rc<T>` to a `Weak<T>`, and method `view` can be used to
/// upgrade a `Weak<T>` into an `Rc<T>`, if it's still alive. If we think of the weak pointer as
/// what is stored, then the strong pointer is a temporary view of it.
pub trait WeakElement {
    /// The type at which a weak element can be viewed.
    ///
    /// For example, for `std::rc::Weak<T>`, this will be `std::rc::Rc<T>`.
    type Strong;

    /// Constructs a weak pointer from a strong pointer.
    ///
    /// This is usually implemented by a `downgrade` method.
    fn new(view: &Self::Strong) -> Self;

    /// Acquires a strong pointer from a weak pointer.
    ///
    /// This is usually implemented by an `upgrade` method.
    fn view(&self) -> Option<Self::Strong>;

    /// Is the given weak element expired?
    ///
    /// The default implemention checks whether a strong pointer can be obtained via `view`.
    fn is_expired(&self) -> bool {
        self.view().is_none()
    }

    /// Clones a strong pointer.
    ///
    /// The default implementation uses `new` and `view`; you should override it.
    fn clone(view: &Self::Strong) -> Self::Strong
        where Self: Sized
    {
        Self::new(view).view().expect("WeakElement::clone")
    }
}

/// Interface for elements that can act as keys in weak hash tables.
///
/// To use an element as a weak hash map key or weak hash set element), the hash table
/// needs to be able to view the actual key values to hash and compare them. This trait
/// provides the necessary mechanism.
pub trait WeakKey : WeakElement {
    /// The underlying key type.
    ///
    /// For example, for `std::rc::Weak<T>`, this will be `T`.
    type Key: ?Sized + Eq + Hash;

    /// Allows borrowing a view of the key, via a callback.
    ///
    /// Rather than returning a borrowed reference to the actual key, this method passes a
    /// reference to the key to a callback with an implicit higher-order lifetime bound. This is
    /// necessary to get the lifetimes right in cases where the key is not actually store in the
    /// strong pointer.
    fn with_key<F, R>(view: &Self::Strong, f: F) -> R
        where F: FnOnce(&Self::Key) -> R;

    /// Hashes the key `view` into the given `Hasher`.
    fn hash<H: Hasher>(view: &Self::Strong, h: &mut H) {
        Self::with_key(view, |k| k.hash(h));
    }

    /// Returns whether the key `view` equals the given `key`.
    fn equals<Q>(view: &Self::Strong, key: &Q) -> bool
        where Q: ?Sized + Eq,
              Self::Key: Borrow<Q>
    {
        Self::with_key(view, |k| k.borrow() == key)
    }
}

impl<T: ?Sized> WeakElement for rc::Weak<T> {
    type Strong = rc::Rc<T>;

    fn new(view: &Self::Strong) -> Self {
        rc::Rc::<T>::downgrade(view)
    }

    fn view(&self) -> Option<Self::Strong> {
        self.upgrade()
    }

    fn clone(view: &Self::Strong) -> Self::Strong {
        view.clone()
    }
}

impl<T: ?Sized + Eq + Hash> WeakKey for rc::Weak<T> {
    type Key = T;

    fn with_key<F, R>(view: &Self::Strong, f: F) -> R
        where F: FnOnce(&Self::Key) -> R
    {
        f(view)
    }
}

impl<T: ?Sized> WeakElement for sync::Weak<T> {
    type Strong = sync::Arc<T>;

    fn new(view: &Self::Strong) -> Self {
        sync::Arc::<T>::downgrade(view)
    }

    fn view(&self) -> Option<Self::Strong> {
        self.upgrade()
    }

    fn clone(view: &Self::Strong) -> Self::Strong {
        view.clone()
    }
}

impl<T: ?Sized + Eq + Hash> WeakKey for sync::Weak<T>
{
    type Key = T;

    fn with_key<F, R>(view: &Self::Strong, f: F) -> R
        where F: FnOnce(&Self::Key) -> R
    {
        f(view)
    }
}