rain_lang/graph/

node.rs

/*!
Nodes of the `rain` graph
*/
use std::ops::{Deref, DerefMut};
use std::borrow::Cow;
use std::convert::Infallible;
use std::sync::{Arc, Weak};
use std::fmt::{self, Debug, Display, Formatter};
use std::hash::{Hash, Hasher};
use either::Either;
use parking_lot::{RwLock, RwLockReadGuard, RwLockUpgradableReadGuard, RwLockWriteGuard};
use super::cons::CacheAcceptor;

/// A node in a `rain` graph
#[derive(Debug)]
pub struct Node<T: ?Sized> {
    /// A reference-counted pointer to the data held in this node
    data: Arc<RwLock<T>>
}

impl<T: ?Sized> Node<T> {
    /// Read the data associated with a `rain` node
    pub fn data(&self) -> View<RwLockReadGuard<T>> { View::new(self.data.read()) }
    /// Try to read the data associated with a `rain` node.
    /// Return `None` if the data is currently unavailable to read, i.e. there is a write occuring
    /// ```rust
    /// use std::ops::Deref;
    /// use rain_lang::graph::node::{Node, Data};
    /// let node = Node::new(Data(true));
    /// {
    ///     let read = node.data();
    ///     assert_eq!(read.deref(), &Data(true));
    ///     let try_read = node.try_data().expect("Multiple reads are allowed!");
    ///     assert_eq!(try_read.deref(), &Data(true));
    /// }
    /// let mut write = node.data_mut();
    /// *write = Data(false);
    /// assert_eq!(write.deref(), &Data(false));
    /// assert!(node.try_data().is_none(), "Concurrent reads and writes are not allowed!");
    /// ```
    pub fn try_data(&self) -> Option<View<RwLockReadGuard<T>>> {
        self.data.try_read().map(View::new)
    }
    /// Mutably get the data associated with a `rain` node. Note mutation is limited to
    /// operations which will not corrupt the `rain` graph (e.g. adding dependencies)
    pub fn data_mut(&self) -> View<RwLockWriteGuard<T>> { View::new(self.data.write()) }
    /// Try to mutably get the data associated with a `rain` node
    /// Return `None` if the data is currently unavailable to write
    /// ```rust
    /// use std::ops::Deref;
    /// use rain_lang::graph::node::{Node, Data};
    /// let node = Node::new(Data(true));
    /// {
    ///     let mut try_write = node.try_data_mut().expect("Valid write");
    ///     *try_write = Data(false);
    /// }
    /// let read = node.data();
    /// assert_eq!(read.deref(), &Data(false));
    /// let try_read = node.try_data().expect("Multiple reads are allowed!");
    /// assert_eq!(try_read.deref(), &Data(false));
    /// assert!(node.try_data_mut().is_none(), "Concurrent reads and writes are not allowed!");
    /// ```
    pub fn try_data_mut(&self) -> Option<View<RwLockWriteGuard<T>>> {
        self.data.try_write().map(View::new)
    }
    /// Downgrade this node to a weak handle
    pub fn downgrade(&self) -> WeakNode<T> { WeakNode { data: Arc::downgrade(&self.data) } }
}

impl<T: ?Sized> Clone for Node<T> {
    #[inline(always)] fn clone(&self) -> Node<T> { Node { data: self.data.clone() } }
}

impl<T: ?Sized> PartialEq for Node<T> {
    #[inline] fn eq(&self, other: &Node<T>) -> bool { Arc::ptr_eq(&self.data, &other.data) }
}

impl<T: ?Sized> Eq for Node<T> {}

impl<T: ?Sized> Hash for Node<T> {
    #[inline] fn hash<H: Hasher>(&self, hasher: &mut H) {
        (self.data.deref() as *const RwLock<_>).hash(hasher)
    }
}

/// A node which has not yet been backlinked
#[derive(Debug, Clone)]
pub struct NotBacklinked<T>(Node<T>);

impl<T: NodeData> NotBacklinked<T> {
    /// Backlink a given node
    pub fn backlink(self) -> Result<Node<T>, T::Error> {
        {
            let mut data = self.0.data.write();
            data.backlink(Backlink(&self.0))?;
        }
        Ok(self.0)
    }
}

/// A backlink to a node
#[derive(Debug, Clone)]
pub struct Backlink<'a, T>(&'a Node<T>);

impl<T> Deref for Backlink<'_, T> {
    type Target = Node<T>;
    #[inline(always)] fn deref(&self) -> &Node<T> { self.0 }
}

/// A trait implemented by items which can be placed into a node, but may require a node backlink
pub trait NodeData: Sized {
    /// A possible error in placing an item into a node *or* deduplicating
    type Error;
    /// An acceptor for cache entries
    type CacheAcceptor: CacheAcceptor<Self>;
    /// Backlink this data to the given node.
    /// **Warning:**
    /// *Any* attempt to read the data of `backlink` in this function will lead to *deadlock*!
    /// Backlinking should *not* create new nodes if dedup obtains a lock on the cache table!
    fn backlink(&mut self, _backlink: Backlink<Self>) -> Result<(), Self::Error> { Ok(()) }
    /// Attempt to deduplicate this `NodeData`, either succeeding or returning a cache entry
    /// to place the newly created node in *should backlinking succeed*.
    fn dedup(&mut self) -> Either<Node<Self>, Self::CacheAcceptor>;
}

/// A view into a node's data, allowing limited mutation
#[derive(Debug, PartialEq)]
pub struct View<R>(pub(crate) R);

impl<R> Deref for View<R> where R: Deref {
    type Target = R::Target;
    fn deref(&self) -> &R::Target { self.0.deref() }
}

impl<R> View<R> where R: Deref {
    /// Create a new value view
    pub fn new(r: R) -> View<R> { View(r) }
}

impl<'a, T> View<RwLockWriteGuard<'a, T>> {
    /// Downgrade this write view to a read view
    pub fn downgrade(self) -> View<RwLockReadGuard<'a, T>> {
        View::new(RwLockWriteGuard::downgrade(self.0))
    }
    /// Downgrade this write view to an upgradeable read view
    pub fn downgrade_to_upgradeable(self) -> View<RwLockUpgradableReadGuard<'a, T>> {
        View::new(RwLockWriteGuard::downgrade_to_upgradable(self.0))
    }
}

impl<'a, T> View<RwLockUpgradableReadGuard<'a, T>> {
    /// Upgrade this read guard
    pub fn upgrade(self) -> View<RwLockWriteGuard<'a, T>> {
        View::new(RwLockUpgradableReadGuard::upgrade(self.0))
    }
    /// Try to upgrade this read guard
    pub fn try_upgrade(self) -> Result<View<RwLockWriteGuard<'a, T>>, Self> {
        match RwLockUpgradableReadGuard::try_upgrade(self.0) {
            Ok(up) => Ok(View::new(up)),
            Err(s) => Err(View::new(s))
        }
    }
}

impl<T: NodeData> Node<T> {
    /// Create a new, non-backlinked node from given data, *without deduplication!*
    fn not_backlinked(data: T) -> NotBacklinked<T> {
        NotBacklinked(Node { data : Arc::new(RwLock::new(data)) })
    }
    /// Try to create a new node from given data, which *can* fail
    pub fn try_new(mut data: T) -> Result<Node<T>, T::Error> {
        match data.dedup() {
            Either::Left(node) => Ok(node),
            Either::Right(acceptor) => {
                let node = Node::not_backlinked(data).backlink()?;
                acceptor.accept(node.downgrade());
                Ok(node)
            }
        }
    }
}

impl<T: NodeData<Error=Infallible>> Node<T> {
    /// Try to create a new node from given data, which cannot fail
    pub fn new(data: T) -> Node<T> {
        Node::try_new(data).unwrap_or_else(|err| match err {})
    }
}

impl<T: Display> Display for Node<T> {
    fn fmt(&self, fmt: &mut Formatter) -> Result<(), fmt::Error> {
        write!(fmt, "{}", self.data().deref())
    }
}

/// A weak handle on a node in a `rain` graph
#[derive(Debug)]
pub struct WeakNode<T: ?Sized> {
    /// A weak reference-counted pointer to the data held in this node
    data: Weak<RwLock<T>>
}

impl<T: ?Sized> Clone for WeakNode<T> {
    #[inline(always)] fn clone(&self) -> WeakNode<T> { WeakNode { data: self.data.clone() } }
}

impl<T> Default for WeakNode<T> {
    #[inline(always)] fn default() -> WeakNode<T> { WeakNode { data: Weak::default() } }
}

impl<T: ?Sized> WeakNode<T> {
    /// Attempt to upgrade this node to a strong handle
    pub fn upgrade(&self) -> Option<Node<T>> { self.data.upgrade().map(|data| Node { data }) }
}

impl<T: ?Sized> PartialEq for WeakNode<T> {
    fn eq(&self, other: &WeakNode<T>) -> bool { self.data.ptr_eq(&other.data) }
}

impl<T: ?Sized> Eq for WeakNode<T> {}

impl<T> Hash for WeakNode<T> {
    #[inline] fn hash<H: Hasher>(&self, hasher: &mut H) {
        self.data.as_ptr().hash(hasher)
    }
}

impl<T> WeakNode<T> {
    /// Check whether this weak node is null
    pub fn is_null(&self) -> bool { self == &WeakNode::default() }
}

impl<T> WeakNode<T> {
    /// Create a new, empty weak node
    pub fn new() -> WeakNode<T> { WeakNode { data: Weak::default() } }
    /// Check whether this weak node points to the same allocation as another
    /// Returns false if either pointer points to no allocation.
    pub fn alloc_eq(&self, other: &WeakNode<T>) -> bool {
        !self.data.ptr_eq(&Weak::new()) && self == other
    }
}

/// A trait implemented by values which have a weak node address associated with them
pub trait HasThis<T=Self> {
    /// Get a `Cow` of the weak node address associated with this value.
    /// May be `null` if there is none.
    fn this(&self) -> Cow<WeakNode<T>>;
}

impl<T> HasThis<T> for WeakNode<T> {
    fn this(&self) -> Cow<WeakNode<T>> { Cow::Borrowed(&self) }
}

/// A trait implemented by values which have a strong node address associated with them
pub trait HasAddr<T=Self> {
    /// Get a `Cow` of the strong node address associated with this value
    fn addr(&self) -> Cow<Node<T>>;
}

impl<T> HasAddr<T> for Node<T> {
    #[inline(always)] fn addr(&self) -> Cow<Node<T>> { Cow::Borrowed(&self) }
}

impl<T> HasThis<T> for Node<T> {
    #[inline(always)] fn this(&self) -> Cow<WeakNode<T>> { Cow::Owned(self.downgrade()) }
}

/// Transforms an iterator over `&Node`s into an iterator over `WeakNode`s
#[derive(Debug, Copy, Clone, Eq, PartialEq)]
pub struct ToWeak<I>(pub I);

impl<'a, T: 'a, I> Iterator for ToWeak<I> where I: Iterator<Item=&'a Node<T>> {
    type Item = WeakNode<T>;
    fn next(&mut self) -> Option<WeakNode<T>> { self.0.next().map(Node::downgrade) }
    fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
    fn count(self) -> usize { self.0.count() }
    fn last(self) -> Option<WeakNode<T>> { self.0.last().map(Node::downgrade) }
    fn nth(&mut self, n: usize) -> Option<WeakNode<T>> { self.0.nth(n).map(Node::downgrade) }
}

impl<'a, T: 'a, I> ExactSizeIterator for ToWeak<I> where I: ExactSizeIterator<Item=&'a Node<T>> {
    fn len(&self) -> usize { self.0.len() }
}

impl<'a, T: 'a, I> DoubleEndedIterator for ToWeak<I> where I: DoubleEndedIterator<Item=&'a Node<T>>
{
    fn next_back(&mut self) -> Option<WeakNode<T>> { self.0.next_back().map(Node::downgrade) }
}

/// Simple data inside a node
#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash, Default)]
pub struct Data<T>(pub T);

impl<T> Deref for Data<T> {
    type Target = T;
    fn deref(&self) -> &T { &self.0 }
}

impl<T> DerefMut for Data<T> {
    fn deref_mut(&mut self) -> &mut T { &mut self.0 }
}

impl<T> NodeData for Data<T> {
    type Error = Infallible;
    type CacheAcceptor = ();
    fn dedup(&mut self) -> Either<Node<Data<T>>, ()> { Either::Right(()) }
}

impl<R, T> DerefMut for View<R> where R: DerefMut<Target=Data<T>> {
    fn deref_mut(&mut self) -> &mut Data<T> { self.0.deref_mut() }
}