pub use generativity::*;
use std::collections::HashMap;
use core::hash::{Hash, Hasher};
use core::mem::transmute;
use core::ops::{Index, IndexMut, Deref, DerefMut};
use core::ptr::NonNull;
use core::hint::unreachable_unchecked;
#[repr(transparent)]
#[derive(Eq)]
pub struct GraphPtr<'id, T> {
node : NonNull<T>,
_guard : Id<'id>
}
impl <'id, T> PartialEq for GraphPtr<'id, T> {
fn eq(&self, other : &Self) -> bool {
self.node == other.node
}
}
impl <'id, T> GraphPtr<'id, T> {
fn as_mut(self) -> *mut T {
self.node.as_ptr()
}
pub fn as_ptr(self) -> *const T {
self.node.as_ptr() as *const T
}
unsafe fn from_mut(ptr : *mut T, guard : Id<'id>) -> Self {
GraphPtr { node : NonNull::new_unchecked(ptr), _guard : guard }
}
unsafe fn from_ptr(ptr : *const T, guard : Id<'id>) -> Self {
GraphPtr { node : NonNull::new_unchecked(ptr as *mut T), _guard : guard }
}
}
impl <'id, T> Hash for GraphPtr<'id, T> {
fn hash<H: Hasher>(&self, state: &mut H) {
self.node.hash(state);
}
}
impl <'id, T> Clone for GraphPtr<'id, T> {
fn clone(&self) -> GraphPtr<'id, T> {
GraphPtr { node : self.node, _guard : self._guard }
}
}
impl <'id, T> Copy for GraphPtr<'id, T> {}
#[derive(PartialEq, Eq)]
#[repr(C)]
pub struct NamedNode<N, E> {
refs : HashMap<NonNull<NamedNode<N, E>>, E>,
payload : N,
}
pub mod node_views {
use super::*;
#[repr(C)]
pub struct NamedNode<'id, N, E> {
pub refs : HashMap<GraphPtr<'id, super::NamedNode<N, E>>, E>,
pub payload : N,
}
}
pub trait GraphNode : Sized {
type Node;
type Edge;
fn get(&self) -> &Self::Node;
fn get_mut(&mut self) -> &mut Self::Node;
fn from_payload(data : Self::Node) -> Self;
}
impl <N, E> GraphNode for NamedNode<N, E> {
type Node = N;
type Edge = E;
fn get(&self) -> &Self::Node {
&self.payload
}
fn get_mut(&mut self) -> &mut Self::Node {
&mut self.payload
}
fn from_payload(data : Self::Node) -> Self {
NamedNode { refs : HashMap::new(), payload : data }
}
}
pub struct GraphIterRes<E, T> {
pub values : E,
pub ptr : T,
}
pub struct EdgeBoth<N, E> {
pub this : N,
pub that : N,
pub edge : E
}
pub struct EdgeSingle<N, E> {
pub this : N,
pub edge : E
}
pub enum Edge<N, E> {
Both(EdgeBoth<N, E>),
Loop(EdgeSingle<N, E>),
}
pub use crate::Edge::Both;
pub use crate::Edge::Loop;
impl <N, E> Edge<N, E> {
pub fn this(self) -> EdgeSingle<N, E> {
match self {
Both(s) => EdgeSingle { this : s.this, edge : s.edge },
Loop(s) => s,
}
}
pub fn that(self) -> EdgeSingle<N, E> {
match self {
Both(s) => EdgeSingle { this : s.that, edge : s.edge },
Loop(s) => s,
}
}
pub fn unwrap(self) -> EdgeBoth<N, E> {
match self {
Both(s) => s,
_ => panic!("called `Edge::unwrap()` on a `Loop` value"),
}
}
pub unsafe fn unwrap_unchecked(self) -> EdgeBoth<N, E> {
match self {
Both(s) => s,
_ => unreachable_unchecked(),
}
}
}
#[derive(PartialEq, Eq)]
pub struct GraphRaw<T> {
data : Vec<Box<T>>,
}
impl <N, E, NodeType> GraphRaw<NodeType>
where NodeType : GraphNode<Node = N, Edge = E>
{
fn spawn_detached(&mut self, payload : N) -> *const NodeType {
let node = Box::new(NodeType::from_payload(payload));
let ptr : *const NodeType = &*node;
self.data.push(node);
ptr
}
fn get<'id>(&self, item : GraphPtr<'id, NodeType>) -> &N {
unsafe {
(*item.as_ptr()).get()
}
}
fn get_mut<'id>(&mut self, item : GraphPtr<'id, NodeType>) -> &mut N {
unsafe {
(*item.as_mut()).get_mut()
}
}
#[allow(dead_code)]
#[allow(unused_variables)]
unsafe fn kill(&mut self, item : *const NodeType) {
unimplemented!();
}
}
impl <N, E, NodeType> GraphRaw<NodeType>
where NodeType : GraphNode<Node = N, Edge = E>
{
fn bridge<'id>(&mut self, src : GraphPtr<'id, NodeType>, dst : GraphPtr<'id, NodeType>) -> Edge<&'_ mut N, ()> {
let this = self.get_mut(src);
if src == dst {
Loop(EdgeSingle { this, edge : () })
} else {
let that = unsafe { (*dst.as_mut()).get_mut() };
Both(EdgeBoth { this, that, edge : () })
}
}
}
impl <N, E> GraphRaw<NamedNode<N, E>> {
fn connect<'id>(&mut self, src : GraphPtr<'id, NamedNode<N, E>>, dst : GraphPtr<'id, NamedNode<N, E>>, edge : E) {
let refs = unsafe { &mut (*src.as_mut()).refs };
refs.insert(dst.node, edge);
}
fn disconnect<'id>(&mut self, src : GraphPtr<'id, NamedNode<N, E>>, dst : GraphPtr<'id, NamedNode<N, E>>) {
let refs = unsafe { &mut (*src.as_mut()).refs };
refs.remove(&dst.node);
}
fn get_edge<'id>(&self, src : GraphPtr<'id, NamedNode<N, E>>, dst : GraphPtr<'id, NamedNode<N, E>>) -> Option<Edge<&'_ N, &'_ E>> {
let this = unsafe { &(*src.as_ptr()) };
let this_refs = &this.refs;
let this = &this.payload;
if let Some(e) = this_refs.get(&dst.node) {
if src == dst {
Some(Loop(EdgeSingle { this, edge : &e }))
} else {
let that = self.get(dst);
Some(Both(EdgeBoth { this, that, edge : &e }))
}
} else {
None
}
}
fn get_edge_mut<'id>(&mut self, src : GraphPtr<'id, NamedNode<N, E>>, dst : GraphPtr<'id, NamedNode<N, E>>) -> Option<Edge<&'_ mut N, &'_ mut E>> {
let this = unsafe { &mut (*src.as_mut()) };
let this_refs = &mut this.refs;
let this = &mut this.payload;
if let Some(e) = this_refs.get_mut(&dst.node) {
if src == dst {
Some(Loop(EdgeSingle { this, edge : e }))
} else {
let that = self.get_mut(dst);
Some(Both(EdgeBoth { this, that, edge : e }))
}
} else {
None
}
}
}
impl <T> GraphRaw<T> {
fn new() -> GraphRaw<T> {
GraphRaw { data : Vec::new() }
}
}
pub struct GenericGraph<Root, NodeType> {
internal : GraphRaw<NodeType>,
root : Root
}
pub type VecGraph<T> = GenericGraph<Vec<NonNull<T>>, T>;
impl <Root : Default, NodeType> Default for GenericGraph<Root, NodeType> {
fn default() -> Self {
GenericGraph::new()
}
}
impl <Root : Default, NodeType> GenericGraph<Root, NodeType> {
pub fn new() -> Self {
GenericGraph { root : Root::default(), internal : GraphRaw::new() }
}
}
pub enum CleanupStrategy {
Never,
}
pub struct AnchorMut<'this, 'id : 'this, T : 'this> {
parent: &'this mut T,
strategy : CleanupStrategy,
_guard : Id<'id>,
}
impl <'this, 'id: 'this, T : 'this> Drop for AnchorMut<'this, 'id, T> {
fn drop(&mut self) {}
}
impl <'this, 'id : 'this, N : 'this, E : 'this, NodeType : 'this, Root : 'this>
Index<GraphPtr<'id, NodeType>> for AnchorMut<'this, 'id, GenericGraph<Root, NodeType>>
where NodeType : GraphNode<Node = N, Edge = E>
{
type Output = N;
fn index(&self, dst : GraphPtr<'id, NodeType>) -> &Self::Output {
&self.internal().get(dst)
}
}
impl <'this, 'id : 'this, N : 'this, E : 'this, NodeType : 'this, Root : 'this>
IndexMut<GraphPtr<'id, NodeType>> for AnchorMut<'this, 'id, GenericGraph<Root, NodeType>>
where NodeType : GraphNode<Node = N, Edge = E>
{
fn index_mut(&mut self, dst : GraphPtr<'id, NodeType>) -> &mut Self::Output {
self.internal_mut().get_mut(dst)
}
}
impl <Root, NodeType> GenericGraph<Root, NodeType> {
pub unsafe fn anchor_mut<'id>(&mut self, guard : Id<'id>, strategy : CleanupStrategy)
-> AnchorMut<'_, 'id, GenericGraph<Root,NodeType>> {
AnchorMut { parent : self, _guard : guard, strategy }
}
}
#[macro_export]
macro_rules! make_anchor_mut {
($name:ident, $parent:ident, $strategy:ident) => {
make_guard!(g);
let mut $name = unsafe { $parent.anchor_mut(Id::from(g), $crate::CleanupStrategy::$strategy) };
};
}
impl <'this, 'id : 'this, N : 'this, E : 'this, NodeType : 'this, Root : 'this>
AnchorMut<'this, 'id, GenericGraph<Root, NodeType>>
where NodeType : GraphNode<Node = N, Edge = E>
{
fn internal(&self) -> &GraphRaw<NodeType> {
&self.parent.internal
}
pub unsafe fn gptr_from_ptr(&self, raw : *const NodeType) -> GraphPtr<'id, NodeType> {
GraphPtr::from_ptr(raw, self._guard)
}
pub fn cursor(&self, dst : GraphPtr<'id, NodeType>) -> Cursor<'_, 'id, NodeType> {
Cursor { parent : self.internal(), current : dst }
}
}
impl <'this, 'id : 'this, N : 'this, E : 'this, NodeType : 'this, Root : 'this>
AnchorMut<'this, 'id, GenericGraph<Root, NodeType>>
where NodeType : GraphNode<Node = N, Edge = E>
{
fn internal_mut(&mut self) -> &mut GraphRaw<NodeType> {
&mut self.parent.internal
}
pub fn spawn_detached(&mut self, payload : N) -> GraphPtr<'id, NodeType> {
let ptr = self.internal_mut().spawn_detached(payload);
unsafe {
GraphPtr::from_ptr(ptr, self._guard )
}
}
pub fn cursor_mut(&mut self, dst : GraphPtr<'id, NodeType>) ->
CursorMut<'_, 'id, NodeType> {
CursorMut { parent : self.internal_mut(), current : dst }
}
}
impl <'this, 'id : 'this, N : 'this, E : 'this, Root : 'this>
AnchorMut<'this, 'id, GenericGraph<Root, NamedNode<N, E>>>
{
pub fn connect(&mut self, src : GraphPtr<'id, NamedNode<N, E>>,
dst : GraphPtr<'id, NamedNode<N, E>>, edge : E)
{
self.internal_mut().connect(src, dst, edge);
}
pub fn disconnect(&mut self, src : GraphPtr<'id, NamedNode<N, E>>,
dst : GraphPtr<'id, NamedNode<N, E>>)
{
self.internal_mut().disconnect(src, dst);
}
pub fn view(&self, dst : GraphPtr<'id, NamedNode<N, E>>) -> &node_views::NamedNode<'id, N, E> {
let this = unsafe { &(*dst.as_ptr()) };
unsafe { transmute(this) }
}
pub fn view_mut(&mut self, dst : GraphPtr<'id, NamedNode<N, E>>) -> &mut node_views::NamedNode<'id, N, E> {
let this = unsafe { &mut (*dst.as_mut()) };
unsafe { transmute(this) }
}
}
impl <'this, 'id : 'this, N : 'this, E : 'this, NodeType : 'this>
AnchorMut<'this, 'id, VecGraph<NodeType>>
where NodeType : GraphNode<Node = N, Edge = E>
{
pub fn spawn(&mut self, payload : N) -> GraphPtr<'id, NodeType> {
let res = self.spawn_detached(payload);
self.attach(res);
res
}
pub fn root(&self) -> &Vec<GraphPtr<'id, NodeType>> {
unsafe {
transmute(&self.parent.root)
}
}
pub fn root_mut(&mut self) -> &mut Vec<GraphPtr<'id, NodeType>> {
unsafe {
transmute(&mut self.parent.root)
}
}
pub fn attach(&mut self, dst : GraphPtr<'id, NodeType>) {
self.parent.root.push(dst.node);
}
pub fn detach(&mut self, index : usize) {
self.parent.root.swap_remove(index);
}
pub fn iter(&self) -> impl Iterator<Item = (&'_ N, GraphPtr<'id, NodeType>)> {
let g = self._guard;
self.parent.root.iter().map(move |x| {
let x = x.as_ptr() as *const NodeType;
let p = unsafe { GraphPtr::from_ptr(x, g) };
let payload = unsafe { (*x).get() };
(payload, p)
})
}
pub fn iter_mut(&mut self) -> impl Iterator<Item = (&'_ mut N, GraphPtr<'id, NodeType>)> {
let g = self._guard;
self.parent.root.iter_mut().map(move |x| {
let x = x.as_ptr();
let p = unsafe { GraphPtr::from_mut(x, g) };
let payload = unsafe { (*x).get_mut() };
(payload, p)
})
}
}
pub struct CursorMut<'this, 'id : 'this, T : 'this> {
parent : &'this mut GraphRaw<T>,
current : GraphPtr<'id, T>
}
#[derive(Clone, Copy, PartialEq, Eq)]
pub struct Cursor<'this, 'id : 'this, T : 'this> {
parent : &'this GraphRaw<T>,
current : GraphPtr<'id, T>
}
macro_rules! impl_cursor_immutable {
($cursor_type:ident) => {
impl <'this, 'id : 'this, N : 'this, E : 'this, NodeType : 'this>
$cursor_type<'this, 'id, NodeType>
where NodeType : GraphNode<Node = N, Edge = E>
{
pub fn at(&self) -> GraphPtr<'id, NodeType> {
self.current
}
pub fn is_at(&self, dst : GraphPtr<'id, NodeType>) -> bool {
dst == self.at()
}
pub fn get(&self) -> &N {
self.parent.get(self.at())
}
pub fn jump(&mut self, dst : GraphPtr<'id, NodeType>) {
self.current = dst;
}
}
impl <'this, 'id : 'this, N : 'this, E : 'this>
$cursor_type<'this, 'id, NamedNode<N, E>>
{
pub fn iter(&self) -> impl Iterator<Item = GraphIterRes<Edge<&'_ N, &'_ E>, GraphPtr<'id, NamedNode<N, E>>>> {
let current = self.at().as_ptr();
let g = self.at()._guard;
let node_refs = unsafe { &(*current).refs };
node_refs.iter().map(move |x| {
let ptr = (x.0).as_ptr() as *const NamedNode<N, E>;
let p = unsafe { GraphPtr::from_ptr(ptr, g) };
let that = unsafe { (*ptr).get() };
if (current == ptr) {
GraphIterRes { values : Loop(EdgeSingle { this : that, edge : x.1}), ptr : p }
} else {
let this = unsafe { (*current).get() };
GraphIterRes { values : Both(EdgeBoth { this : this, that : that, edge : x.1 }), ptr : p }
}
})
}
pub fn get_edge(&self, dst : GraphPtr<'id, NamedNode<N, E>>) -> Option<Edge<&'_ N, &'_ E>> {
self.parent.get_edge(self.at(), dst)
}
}
impl <'this, 'id : 'this, N : 'this, E : 'this> Deref for $cursor_type<'this, 'id, NamedNode<N, E>> {
type Target = node_views::NamedNode<'id, N, E>;
fn deref(&self) -> &Self::Target {
let this = unsafe { &(*self.at().as_ptr()) };
unsafe { transmute(this) }
}
}
}
}
impl_cursor_immutable!{CursorMut}
impl_cursor_immutable!{Cursor}
impl <'this, 'id : 'this, N : 'this, E : 'this, NodeType : 'this>
CursorMut<'this, 'id, NodeType>
where NodeType : GraphNode<Node = N, Edge = E>
{
pub fn bridge(&mut self, dst : GraphPtr<'id, NodeType>) -> Edge<&'_ mut N, ()> {
self.parent.bridge(self.at(), dst)
}
pub fn get_mut(&mut self) -> &mut N {
self.parent.get_mut(self.at())
}
}
impl <'this, 'id : 'this, N : 'this, E : 'this>
CursorMut<'this, 'id, NamedNode<N, E>>
{
pub fn iter_mut(&mut self) -> impl Iterator<Item = GraphIterRes<Edge<&'_ mut N, &'_ mut E>, GraphPtr<'id, NamedNode<N, E>>>> {
let current = self.at().as_mut();
let g = self.at()._guard;
let node_refs = unsafe { &mut (*current).refs };
node_refs.iter_mut().map(move |x| {
let ptr = (x.0).as_ptr();
let p = unsafe { GraphPtr::from_mut(ptr, g) };
let that = unsafe { (*ptr).get_mut() };
if current == ptr {
GraphIterRes { values : Loop(EdgeSingle { this : that, edge : x.1}), ptr : p }
} else {
let this = unsafe { (*current).get_mut() };
GraphIterRes { values : Both(EdgeBoth { this , that, edge : x.1 }), ptr : p }
}
})
}
pub fn attach(&mut self, dst : GraphPtr<'id, NamedNode<N, E>>, edge : E) {
self.parent.connect(self.at(), dst, edge);
}
pub fn detach(&mut self, dst : GraphPtr<'id, NamedNode<N, E>>) {
self.parent.disconnect(self.at(), dst);
}
fn get_edge_mut(&mut self, dst : GraphPtr<'id, NamedNode<N, E>>) -> Option<Edge<&'_ mut N, &'_ mut E>> {
self.parent.get_edge_mut(self.at(), dst)
}
}
impl <'this, 'id : 'this, N : 'this, E : 'this> DerefMut for CursorMut<'this, 'id, NamedNode<N, E>> {
fn deref_mut(&mut self) -> &mut Self::Target {
let this = unsafe { &mut (*self.at().as_mut()) };
unsafe { transmute(this) }
}
}