rs-graph-derive 0.17.0

/*
 * Copyright (c) 2017, 2018 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"]

//! 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`, `Network`, `IndexGraph` and
//! `IndexNetwork`) 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`, `EdgeAttributes` and
//! `BiEdgeAttributes` traits from `rs_graph::attributes`. These traits can also
//! be automatically implemented using `#[derive(Graph)]` given that the wrapped
//! graph is an `IndexGraph` or an `IndexNetwork`. The node/edge/biedge attributes
//! must be collected in indexable arrays (slice, `Vec`, ...) of an appropriate
//! size and be annotated with `nodeattrs`, `edgeattrs` or `biedgeattrs`
//! 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::Ident)> {
    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::Word(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, biedgeattrs))]
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;
    let mut biedgeattrs = 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 let Some(attrvar) = get_attr_var(field, i, "biedgeattrs") {
                if biedgeattrs.is_some() {
                    panic!("Only one field can be tagged `biedgeattrs`");
                }
                biedgeattrs = 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",
        "BiDirected",
        "IndexGraph",
        "IndexNetwork",
    ]
    .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 (bidirected_impl, _, bidirected_where) = gens[4].split_for_impl();
    let (indexgraph_impl, _, indexgraph_where) = gens[5].split_for_impl();
    let (indexnetwork_impl, _, indexnetwork_where) = gens[6].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 NeighIter = <#typ as ::rs_graph::traits::Undirected<'a>>::NeighIter;

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

            fn neighs(&'a self, u: Self::Node) -> Self::NeighIter {
                self.#var.neighs(u)
            }
        }

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

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

            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 outedges(&'a self, u: Self::Node) -> Self::OutEdgeIter {
                self.#var.outedges(u)
            }

            fn inedges(&'a self, u: Self::Node) -> Self::InEdgeIter {
                self.#var.inedges(u)
            }
        }

        impl #bidirected_impl ::rs_graph::traits::BiDirected<'a> for #name #ty_generics #bidirected_where
        {
            fn is_reverse(&self, e: Self::Edge, f: Self::Edge) -> bool {
                self.#var.is_reverse(e, f)
            }

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

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

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

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

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

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

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

        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)
            }
        }

        impl #indexnetwork_impl ::rs_graph::traits::IndexNetwork<'a> for #name #ty_generics #indexnetwork_where
        {
            fn biedge_id(&self, e: Self::Edge) -> usize {
                self.#var.biedge_id(e)
            }

            fn id2biedge(&'a self, id: usize) -> Self::Edge {
                self.#var.id2biedge(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 let Some((attrvar, attrtyp)) = biedgeattrs.as_ref() {
        expanded.extend(quote! {
            impl #indexnetwork_impl ::rs_graph::attributes::BiEdgeAttributes<'a, #typ, #attrtyp> for #name #ty_generics #indexnetwork_where
            {
                fn biedge(&self, u: <#typ as ::rs_graph::traits::GraphType<'a>>::Edge) -> &#attrtyp {
                    &self.#attrvar[self.#var.biedge_id(u)]
                }

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

    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)]
                    }
                }
            });
        }

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

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

    expanded.into()
}