rs-graph-derive 0.19.0

/*
 * Copyright (c) 2017-2020 Frank Fischer <frank-fischer@shadow-soft.de>
 *
 * This program is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
 */

#![recursion_limit = "256"]
#![forbid(unsafe_code)]

//! This crate provides automatic graph derivations.
//!
//! In order to automatically implement graph traits for a struct that contains
//! the actual graph data structure in a field, add #[derive(Graph)] to the
//! struct. The field containing the graph must either be named `graph` or be
//! attributed with `#[graph]`. All graph traits (`Graph`, `Digraph`, and
//! `IndexGraph`) that are implemented for the nested graph, are implemented for
//! the annotated struct, too.
//!
//! # Example
//!
//! ```
//! use rs_graph_derive::Graph;
//! use rs_graph::traits::*;
//! use rs_graph::linkedlistgraph::*;
//! use rs_graph::classes;
//!
//! #[derive(Graph)]
//! struct MyGraph {
//!     #[graph] graph: LinkedListGraph, // #[graph] not need for fields named `graph`.
//!     balances: Vec<f64>,
//!     bounds: Vec<f64>,
//! }
//!
//! impl From<LinkedListGraph> for MyGraph {
//!     fn from(g: LinkedListGraph) -> MyGraph {
//!         let n = g.num_nodes();
//!         let m = g.num_edges();
//!         MyGraph {
//!             graph: g,
//!             balances: vec![0.0; n],
//!             bounds: vec![0.0; m],
//!         }
//!     }
//! }
//!
//! impl MyGraph {
//!     fn balance_mut(&mut self, u: Node) -> &mut f64 {
//!         &mut self.balances[self.graph.node_id(u)]
//!     }
//!
//!     fn bound_mut(&mut self, e: Edge) -> &mut f64 {
//!         &mut self.bounds[self.graph.edge_id(e)]
//!     }
//! }
//!
//! # fn main() {
//! let mut g: MyGraph = classes::path::<LinkedListGraph>(5).into();
//! let (s, t) = (g.id2node(0), g.id2node(4));
//! *g.balance_mut(s) = 1.0;
//! *g.balance_mut(t) = -1.0;
//! for e in g.edges() { *g.bound_mut(e) = g.edge_id(e) as f64; }
//! # }
//! ```
//!
//! # Attributed graphs
//!
//! Some algorithms require the presence of specific node or edge attributes.
//! These requirements are represented by `NodeAttributes` and `EdgeAttributes`
//! traits from `rs_graph::attributes`. These traits can also be automatically
//! implemented using `#[derive(Graph)]` given that the wrapped graph is an
//! `IndexGraph`. The node/edge attributes must be collected in indexable arrays
//! (slice, `Vec`, ...) of an appropriate size and be annotated with `nodeattrs`
//! or `edgeattrs` attributes. Note that it is the responsibility of the user to
//! ensure that these vectors have to correct size.
//!
//! # Example
//!
//! ```
//! use rs_graph_derive::Graph;
//! use rs_graph::{traits::*};
//! use rs_graph::linkedlistgraph::*;
//! use rs_graph::classes;
//! use rs_graph::attributes::{NodeAttributes, EdgeAttributes, AttributedGraph};
//!
//! #[derive(Clone, Default)]
//! struct NodeData {
//!     balance: f64,
//! }
//!
//! #[derive(Clone, Default)]
//! struct EdgeData {
//!     bound: f64,
//! }
//!
//! #[derive(Graph)]
//! struct MyGraph {
//!     #[graph] graph: LinkedListGraph,
//!     #[nodeattrs(NodeData)] nodedata: Vec<NodeData>,
//!     #[edgeattrs(EdgeData)] edgedata: Vec<EdgeData>,
//! }
//!
//! #[derive(Graph)]
//! struct MyGraph2 {
//!     #[graph] graph: LinkedListGraph,
//!     #[nodeattrs(NodeData)] nodedata: Vec<NodeData>,
//!     #[edgeattrs(EdgeData)] edgedata: Vec<EdgeData>,
//! }
//!
//! impl From<LinkedListGraph> for MyGraph {
//!     fn from(g: LinkedListGraph) -> MyGraph {
//!         let n = g.num_nodes();
//!         let m = g.num_edges();
//!         MyGraph {
//!             graph: g,
//!             nodedata: vec![Default::default(); n],
//!             edgedata: vec![Default::default(); m],
//!         }
//!     }
//! }
//!
//! # fn main() {
//! let mut g: MyGraph = classes::peterson::<LinkedListGraph>().into();
//! let (s, t) = (g.id2node(0), g.id2node(4));
//! g.node_mut(s).balance = 1.0;
//! g.node_mut(t).balance = -1.0;
//! for e in g.edges() { g.edge_mut(e).bound = g.edge_id(e) as f64; }
//!
//! {
//!     let (g, mut attrs) = g.split();
//!     // this would also work: let (g, mut attrs) = attrs.split();
//!     for u in g.nodes() {
//!         for (e, v) in g.outedges(u) {
//!             attrs.node_mut(v).balance = 42.0 + g.node_id(v) as f64;
//!         }
//!     }
//! }
//! for u in g.nodes() {
//!     assert_eq!(g.node(u).balance, 42.0 + g.node_id(u) as f64);
//! }
//! # }
//! ```
//!

extern crate proc_macro;
use proc_macro2;
use quote::quote;
use syn::{self, parse_quote};

use proc_macro::TokenStream;
use proc_macro2::Span;
use proc_macro2::TokenStream as TokenStream2;

fn get_attr_var(field: &syn::Field, index: usize, attrname: &str) -> Option<(syn::Ident, syn::Path)> {
    for attr in field.attrs.iter() {
        if attr.path.is_ident(attrname) {
            return Some((
                field
                    .ident
                    .clone()
                    .unwrap_or_else(|| syn::Ident::new(&format!("{}", index), Span::call_site())),
                match attr
                    .parse_meta()
                    .unwrap_or_else(|_| panic!("Missing `{}` type", attrname))
                {
                    syn::Meta::List(list) => {
                        assert_eq!(
                            list.nested.len(),
                            1,
                            "expected exactly one type argument for `{}`",
                            attrname
                        );
                        if let Some(syn::NestedMeta::Meta(syn::Meta::Path(id))) = list.nested.iter().next() {
                            id.clone()
                        } else {
                            panic!("expected exactly one type argument for `{}`", attrname);
                        }
                    }
                    _ => panic!("expected exactly one type argument for `{}`", attrname),
                },
            ));
        }
    }

    None
}

#[proc_macro_derive(Graph, attributes(graph, nodeattrs, edgeattrs))]
pub fn graph(input: TokenStream) -> TokenStream {
    let input: TokenStream2 = input.into();
    let mut ast: syn::DeriveInput = syn::parse2(input).unwrap();
    let vis = &ast.vis;
    let name = &ast.ident;
    let generics = &mut ast.generics;

    let mut have_graph_attr = false;
    let mut var = None;
    let mut typ = None;

    let mut nodeattrs = None;
    let mut edgeattrs = None;

    // Collect all fields with attribute #[graph] or named `graph`.
    if let syn::Data::Struct(syn::DataStruct { ref fields, .. }) = ast.data {
        for (i, ref field) in fields.iter().enumerate() {
            if let Some(attrvar) = get_attr_var(field, i, "nodeattrs") {
                if nodeattrs.is_some() {
                    panic!("Only one field can be tagged `nodeattrs`");
                }
                nodeattrs = Some(attrvar);
            }

            if let Some(attrvar) = get_attr_var(field, i, "edgeattrs") {
                if edgeattrs.is_some() {
                    panic!("Only one field can be tagged `edgeattrs`");
                }
                edgeattrs = Some(attrvar);
            }

            if field.attrs.iter().any(|attr| attr.path.is_ident("graph")) {
                if have_graph_attr {
                    panic!("Only one field can be tagged `graph`");
                }
                have_graph_attr = true;
            } else if field.ident.as_ref().map(|s| s == "graph").unwrap_or(false) {
                if have_graph_attr {
                    continue;
                }
            } else {
                continue;
            }
            var = Some(
                field
                    .ident
                    .clone()
                    .unwrap_or_else(|| syn::Ident::new(&format!("{}", i), Span::call_site())),
            );
            typ = Some(&field.ty);
        }
    }

    if var.is_none() {
        panic!("No field `graph` or field with attribute #[graph] found");
    }

    // Implement all graph traits the nested graph implements.

    let ty_generics = generics.clone();
    generics.params.push(parse_quote!('a));

    let gens = ["GraphType", "GraphSize", "Undirected", "Directed", "IndexGraph"]
        .iter()
        .map(|name| {
            let name = syn::Ident::new(name, Span::call_site());
            let mut g = generics.clone();
            g.make_where_clause()
                .predicates
                .push(parse_quote!(#typ: ::rs_graph::traits::#name<'a>));
            g
        })
        .collect::<Vec<_>>();

    let (basegraph_impl, _, basegraph_where) = gens[0].split_for_impl();
    let (graphsize_impl, _, graphsize_where) = gens[1].split_for_impl();
    let (undirected_impl, _, undirected_where) = gens[2].split_for_impl();
    let (directed_impl, _, directed_where) = gens[3].split_for_impl();
    let (indexgraph_impl, _, indexgraph_where) = gens[4].split_for_impl();

    let mut expanded = quote! {
        impl #basegraph_impl ::rs_graph::traits::GraphType<'a> for #name #ty_generics #basegraph_where
        {
            type Node = <#typ as ::rs_graph::traits::GraphType<'a>>::Node;

            type Edge = <#typ as ::rs_graph::traits::GraphType<'a>>::Edge;
        }

        impl #graphsize_impl ::rs_graph::traits::GraphSize<'a> for #name #ty_generics #graphsize_where
        {
            type NodeIter = <#typ as ::rs_graph::traits::GraphSize<'a>>::NodeIter;

            type EdgeIter = <#typ as ::rs_graph::traits::GraphSize<'a>>::EdgeIter;

            fn num_nodes(&self) -> usize {
                self.#var.num_nodes()
            }

            fn num_edges(&self) -> usize {
                self.#var.num_edges()
            }

            fn nodes(&'a self) -> Self::NodeIter {
                self.#var.nodes()
            }

            fn edges(&'a self) -> Self::EdgeIter {
                self.#var.edges()
            }
        }

        impl #undirected_impl ::rs_graph::traits::Undirected<'a> for #name #ty_generics #undirected_where
        {
            type Neigh = <#typ as ::rs_graph::traits::Undirected<'a>>::Neigh;

            fn enodes(&'a self, e: Self::Edge) -> (Self::Node, Self::Node) {
                self.#var.enodes(e)
            }

            fn first_neigh(&'a self, u: Self::Node) -> Option<Self::Neigh> {
                self.#var.first_neigh(u)
            }

            fn next_neigh(&'a self, it: Self::Neigh) -> Option<Self::Neigh> {
                self.#var.next_neigh(it)
            }

            fn get_neigh(&'a self, it: &Self::Neigh) -> (Self::Edge, Self::Node) {
                self.#var.get_neigh(it)
            }
        }

        impl #directed_impl ::rs_graph::traits::Directed<'a> for #name #ty_generics #directed_where
        {
            type OutEdge = <#typ as ::rs_graph::traits::Directed<'a>>::OutEdge;

            type InEdge = <#typ as ::rs_graph::traits::Directed<'a>>::InEdge;

            type IncidentEdge = <#typ as ::rs_graph::traits::Directed<'a>>::IncidentEdge;

            type DirectedEdge = <#typ as ::rs_graph::traits::Directed<'a>>::DirectedEdge;

            fn src(&'a self, e: Self::Edge) -> Self::Node {
                self.#var.src(e)
            }

            fn snk(&'a self, e: Self::Edge) -> Self::Node {
                self.#var.snk(e)
            }

            fn first_out(&'a self, u: Self::Node) -> Option<Self::OutEdge> {
                self.#var.first_out(u)
            }

            fn next_out(&'a self, it: Self::OutEdge) -> Option<Self::OutEdge> {
                self.#var.next_out(it)
            }

            fn get_out(&'a self, it: &Self::OutEdge) -> (Self::Edge, Self::Node) {
                self.#var.get_out(it)
            }

            fn first_in(&'a self, u: Self::Node) -> Option<Self::InEdge> {
                self.#var.first_in(u)
            }

            fn next_in(&'a self, it: Self::InEdge) -> Option<Self::InEdge> {
                self.#var.next_in(it)
            }

            fn get_in(&'a self, it: &Self::InEdge) -> (Self::Edge, Self::Node) {
                self.#var.get_in(it)
            }

            fn first_incident(&'a self, u: Self::Node) -> Option<Self::IncidentEdge> {
                self.#var.first_incident(u)
            }

            fn next_incident(&'a self, it: Self::IncidentEdge) -> Option<Self::IncidentEdge> {
                self.#var.next_incident(it)
            }

            fn get_incident(&'a self, it: &Self::IncidentEdge) -> (Self::DirectedEdge, Self::Node) {
                self.#var.get_incident(it)
            }
        }

        impl #indexgraph_impl ::rs_graph::traits::IndexGraph<'a> for #name #ty_generics #indexgraph_where
        {
            fn node_id(&self, u: Self::Node) -> usize {
                self.#var.node_id(u)
            }

            fn id2node(&'a self, id: usize) -> Self::Node {
                self.#var.id2node(id)
            }

            fn edge_id(&self, e: Self::Edge) -> usize {
                self.#var.edge_id(e)
            }

            fn id2edge(&'a self, id: usize) -> Self::Edge {
                self.#var.id2edge(id)
            }
        }
    };

    let mut attrdefs = TokenStream2::new();
    let mut attrsets = TokenStream2::new();
    let mut attrsets2 = TokenStream2::new();
    if let Some((attrvar, attrtyp)) = nodeattrs.as_ref() {
        expanded.extend(quote! {
            impl #indexgraph_impl ::rs_graph::attributes::NodeAttributes<'a, #typ, #attrtyp> for #name #ty_generics #indexgraph_where
            {
                fn node(&self, u: <#typ as ::rs_graph::traits::GraphType<'a>>::Node) -> &#attrtyp {
                    &self.#attrvar[self.#var.node_id(u)]
                }

                fn node_mut(&mut self, u: <#typ as ::rs_graph::traits::GraphType<'a>>::Node) -> &mut #attrtyp {
                    &mut self.#attrvar[self.#var.node_id(u)]
                }
            }
        });
        attrdefs.extend(quote!(nodeattrs: &'a mut [#attrtyp],));
        attrsets.extend(quote!(nodeattrs: &mut self.#attrvar,));
        attrsets2.extend(quote!(nodeattrs: self.nodeattrs,));
    }

    if let Some((attrvar, attrtyp)) = edgeattrs.as_ref() {
        expanded.extend(quote! {
            impl #indexgraph_impl ::rs_graph::attributes::EdgeAttributes<'a, #typ, #attrtyp> for #name #ty_generics #indexgraph_where
            {
                fn edge(&self, u: <#typ as ::rs_graph::traits::GraphType<'a>>::Edge) -> &#attrtyp {
                    &self.#attrvar[self.#var.edge_id(u)]
                }

                fn edge_mut(&mut self, u: <#typ as ::rs_graph::traits::GraphType<'a>>::Edge) -> &mut #attrtyp {
                    &mut self.#attrvar[self.#var.edge_id(u)]
                }
            }
        });
        attrdefs.extend(quote!(edgeattrs: &'a mut [#attrtyp],));
        attrsets.extend(quote!(edgeattrs: &mut self.#attrvar,));
        attrsets2.extend(quote!(edgeattrs: self.edgeattrs,));
    }

    if !attrdefs.is_empty() {
        let (_, orig_ty_generics, orig_where) = ty_generics.split_for_impl();
        let attrstruct = syn::Ident::new(&format!("{}_Attributes", name), Span::call_site());
        expanded.extend(quote! {
            #vis struct #attrstruct<'a> {
                graph: &'a #typ,
                #attrdefs
            }

            impl #basegraph_impl ::rs_graph::attributes::AttributedGraph<'a> for #name #orig_ty_generics #orig_where {
                type Graph = #typ;
                type Attributes = #attrstruct<'a>;
                fn split<'b>(&'b mut self) -> (&'b #typ, #attrstruct<'b>) {
                        (
                            &self.#var,
                            #attrstruct {
                                graph: &self.#var,
                                #attrsets
                            },
                        )
                }
            }

            impl<'a> ::rs_graph::attributes::AttributedGraph<'a> for #attrstruct<'a> {
                type Graph = #typ;
                type Attributes = #attrstruct<'a>;
                fn split<'b>(&'b mut self) -> (&'b #typ, #attrstruct<'b>) {
                    (self.graph, #attrstruct {
                        graph: self.graph,
                        #attrsets2
                    })
                }
            }
        });

        if let Some((_, attrtyp)) = nodeattrs.as_ref() {
            expanded.extend(quote! {
                impl #indexgraph_impl ::rs_graph::attributes::NodeAttributes<'a, #typ, #attrtyp> for #attrstruct<'a> #ty_generics #indexgraph_where
                {
                    fn node(&self, u: <#typ as ::rs_graph::traits::GraphType<'a>>::Node) -> &#attrtyp {
                        &self.nodeattrs[self.#var.node_id(u)]
                    }

                    fn node_mut(&mut self, u: <#typ as ::rs_graph::traits::GraphType<'a>>::Node) -> &mut #attrtyp {
                        &mut self.nodeattrs[self.#var.node_id(u)]
                    }
                }
            });
        }

        if let Some((_, attrtyp)) = edgeattrs.as_ref() {
            expanded.extend(quote! {
                impl #indexgraph_impl ::rs_graph::attributes::EdgeAttributes<'a, #typ, #attrtyp> for #attrstruct<'a> #ty_generics #indexgraph_where
                {
                    fn edge(&self, u: <#typ as ::rs_graph::traits::GraphType<'a>>::Edge) -> &#attrtyp {
                        &self.edgeattrs[self.#var.edge_id(u)]
                    }

                    fn edge_mut(&mut self, u: <#typ as ::rs_graph::traits::GraphType<'a>>::Edge) -> &mut #attrtyp {
                        &mut self.edgeattrs[self.#var.edge_id(u)]
                    }
                }
            });
        }
    }

    expanded.into()
}