diff options
| -rw-r--r-- | graph_macro/Cargo.toml | 1 | ||||
| -rw-r--r-- | graph_macro/src/lib.rs | 663 | ||||
| -rw-r--r-- | graph_macro/tests/works.rs | 95 |
3 files changed, 745 insertions, 14 deletions
diff --git a/graph_macro/Cargo.toml b/graph_macro/Cargo.toml index 1e4c4db..6e96140 100644 --- a/graph_macro/Cargo.toml +++ b/graph_macro/Cargo.toml @@ -9,3 +9,4 @@ edition = "2021" proc-macro = true [dependencies] +graph = { path = "../graph" }
\ No newline at end of file diff --git a/graph_macro/src/lib.rs b/graph_macro/src/lib.rs index a55efbb..0f56f57 100644 --- a/graph_macro/src/lib.rs +++ b/graph_macro/src/lib.rs @@ -1,19 +1,664 @@ -#![allow(unused_imports)] //! This file provides a macro to delegate the implementation of a //! type that wraps a graph. More precisely, the macro helps the //! wrapper type implement the various Graph-related traits. +//! +//! See the macro [`graph_derive`]. -use proc_macro::TokenStream; +use proc_macro::{Delimiter, Group, Ident, Literal, Punct, Spacing, Span, TokenStream, TokenTree}; -use core::iter::Peekable; +use std::{collections::HashMap, iter::Peekable}; -#[proc_macro_derive(Testing)] -pub fn test_derive(input: TokenStream) -> TokenStream { - let input = input.into_iter().peekable(); +/// A visibility modifer is either "pub", "pub(restriction)", or +/// "Private". +#[derive(Debug, Default)] +enum VisibilityMod { + /// Simple pub visibility. + Pub, + /// The pub visibility with restrictions. + /// + /// Since the restrictions can be given in a variety of ways, and + /// since it does not matter to us, we just keep them as a + /// tokentree. + PubRes(TokenTree), + #[default] + Private, +} + +#[derive(Debug)] +struct Generic { + name: Ident, + type_stream: TokenStream, +} + +impl Generic { + fn new(name: Ident, type_stream: TokenStream) -> Self { + Self { name, type_stream } + } +} + +/// The content of the struct +#[derive(Debug)] +struct GraphInfo { + name: TokenStream, + generics: Vec<Generic>, + field_name: String, + field_type: TokenStream, +} + +impl GraphInfo { + fn new( + name: TokenStream, + generics: Vec<Generic>, + field_name: String, + field_type: TokenStream, + ) -> Self { + Self { + name, + generics, + field_name, + field_type, + } + } +} + +/// For custom compiler errors +#[derive(Debug)] +struct CompileError { + mes: String, + span: Span, +} + +impl CompileError { + fn new(mes: impl ToString, span: Span) -> Self { + Self { + mes: mes.to_string(), + span, + } + } + + /// Produce a token stream that will trigger compiler errors. + /// + /// The point is that the span of the token trees will be set to + /// the desired locations, and hence produce the effect we want. + fn emit(self) -> TokenStream { + // I cannot use the parse method of the type TokenStream, as + // that will not set the spans properly. + + let compile_error_ident = TokenTree::Ident(Ident::new("compile_error", self.span.clone())); + let mut exclamation_punct = TokenTree::Punct(Punct::new('!', Spacing::Alone)); + + exclamation_punct.set_span(self.span.clone()); + + let mut arg_mes_literal = TokenTree::Literal(Literal::string(&self.mes)); + + arg_mes_literal.set_span(self.span.clone()); + + let arg_mes_stream = [arg_mes_literal].into_iter().collect(); + + let mut arg_group = TokenTree::Group(Group::new(Delimiter::Parenthesis, arg_mes_stream)); + + arg_group.set_span(self.span.clone()); + + let mut semi_colon_punct = TokenTree::Punct(Punct::new(';', Spacing::Alone)); + + semi_colon_punct.set_span(self.span); + + [ + compile_error_ident, + exclamation_punct, + arg_group, + semi_colon_punct, + ] + .into_iter() + .collect() + } +} + +macro_rules! unwrap_or_emit { + ($value:ident) => { + if let Err(err) = $value { + return err.emit(); + } + + let $value = $value.unwrap(); + }; +} + +#[allow(unused)] +macro_rules! mytodo { + () => { + Err(CompileError::new("not umplemented yet", Span::mixed_site())) + }; +} + +macro_rules! myerror { + ($mes:tt, $input:ident) => { + Err(CompileError::new($mes, $input.peek().unwrap().span())) + }; +} + +#[proc_macro_derive(Graph, attributes(graph))] +pub fn graph_derive(input: TokenStream) -> TokenStream { + let mut input = input.into_iter().peekable(); + + while move_attributes(&mut input).is_ok() {} + + let _ = get_visibility_mod(&mut input); + + let info = get_info(&mut input); + + unwrap_or_emit!(info); + + let name = info.name; + let generics = info.generics; + let field_name = info.field_name; + let field_type = info.field_type; + + let generics_impl_string = { + let mut result = String::new(); + + if !generics.is_empty() { + result.push_str("<"); + } + + for generic in generics.iter() { + result.push_str(&format!("{}:{},", generic.name, generic.type_stream)); + } + + if !generics.is_empty() { + result.push_str(">"); + } + + result + }; + + let generic_struct_string = { + let mut result = String::new(); + + if !generics.is_empty() { + result.push_str("<"); + } + + for generic in generics.iter() { + result.push_str(&format!("{},", generic.name)); + } + + if !generics.is_empty() { + result.push_str(">"); + } + + result + }; + + let generic_where_string = { + let mut result = String::new(); + + if !generics.is_empty() { + result.push_str("\nwhere\n"); + } + + for generic in generics.iter() { + result.push_str(&format!("{}: 'a,\n", generic.name)); + } + + result + }; + + let result = format!( + " +#[automatically_derived] +impl{generics_impl_string} graph::Graph for {name}{generic_struct_string} {{ +type Iter<'a> = <{field_type} as graph::Graph>::Iter<'a>{generic_where_string}; + +#[inline] +fn is_empty(&self) -> bool {{self.{field_name}.is_empty()}} + +#[inline] +fn nodes_len(&self) -> usize {{ self.{field_name}.nodes_len() }} + +#[inline] +fn children_of(&self, node: usize) -> Result<<Self as graph::Graph>::Iter<'_>, graph::error::Error> {{ +self.{field_name}.children_of(node) +}} + +#[inline] +fn degree(&self, node: usize) -> Result<usize, graph::error::Error> {{ self.{field_name}.degree(node) }} + +#[inline] +fn is_empty_node(&self, node: usize) -> Result<bool, graph::error::Error> {{ self.{field_name}.is_empty_node(node) }} + +#[inline] +fn has_edge(&self, nodea: usize, nodeb: usize) -> Result<bool, graph::error::Error> {{ +self.{field_name}.has_edge(nodea, nodeb) +}} + +#[inline] +fn replace_by_builder(&mut self, _builder: impl graph::builder::Builder<Result = Self>) {{ +unimplemented!() +}} +}}" + ); + + result.parse().unwrap() +} + +fn get_visibility_mod( + input: &mut Peekable<impl Iterator<Item = TokenTree>>, +) -> Result<VisibilityMod, CompileError> { + if let Some(TokenTree::Ident(id)) = input.peek() { + if id.to_string() == "pub" { + input.next(); + + if let Some(TokenTree::Group(g)) = input.peek() { + let delimiter = g.delimiter(); + + if delimiter != Delimiter::Parenthesis { + return Err(CompileError::new("invalid bracket", g.span())); + } + + let tree = TokenTree::Group(g.clone()); + + input.next(); + + return Ok(VisibilityMod::PubRes(tree)); + } else { + return Ok(VisibilityMod::Pub); + } + } + } + + Ok(Default::default()) +} + +fn get_info( + input: &mut Peekable<impl Iterator<Item = TokenTree>>, +) -> Result<GraphInfo, CompileError> { + if let Some(TokenTree::Ident(id)) = input.peek() { + if id.to_string() != "struct" { + let span = input.next().unwrap().span(); + return Err(CompileError::new("Only struct is supported", span)); + } + + input.next(); + + let struct_name = get_until( + input, + |tree| match tree { + TokenTree::Group(g) + if g.delimiter() == Delimiter::Brace + || g.delimiter() == Delimiter::Parenthesis => + { + true + } + TokenTree::Punct(p) if p.as_char() == ';' || p.as_char() == '<' => true, + _ => false, + }, + false, + false, + )?; + + // We are not at the end as guaranteed by `get_until`. + let peek = input.peek().unwrap(); + + if matches!(peek, TokenTree::Punct(p) if p.as_char() == ';') { + // unit struct + + return myerror!("Cannot derive graph for unit structs", input); + } + + let mut generics = Vec::new(); + + if matches!(peek, TokenTree::Punct(p) if p.as_char() == '<') { + // Extract generics + + input.next(); + + generics = get_generics(input)?; + + // println!("generics: {generics:?}"); + } + + let (graph_field_name, graph_field_type) = get_graph_field_name_type(input)?; + + Ok(GraphInfo::new( + struct_name, + generics, + graph_field_name, + graph_field_type, + )) + } else { + myerror!("unexpected token", input) + } +} + +fn get_graph_field_name_type( + input: &mut Peekable<impl Iterator<Item = TokenTree>>, +) -> Result<(String, TokenStream), CompileError> { + let end_of_input = Err(CompileError::new( + "unexpected end of input", + Span::mixed_site(), + )); + + match input.peek() { + Some(TokenTree::Group(g)) => { + let delimiter = g.delimiter(); + + if delimiter != Delimiter::Parenthesis && delimiter != Delimiter::Brace { + return myerror!( + "expected a group enclosed in curly brackets or parentheses", + input + ); + } + + if delimiter == Delimiter::Parenthesis { + // a named tuple + + // in this case only a tuple with one field is + // supported + + let mut body = g.stream().into_iter().peekable(); + + while let Some(tree) = body.peek() { + if matches!(tree, TokenTree::Punct(p) if p.as_char() == ',') { + return myerror!( + "Among named tuples, only those with one field are supported", + input + ); + } + + body.next(); + } + + let mut body = g.stream().into_iter().peekable(); + + let _vis = get_visibility_mod(&mut body)?; + + return Ok(("0".to_string(), body.collect())); + } + + let mut body = g.stream().into_iter().peekable(); + + if body.peek().is_none() { + return end_of_input; + } + + get_visibility_mod(&mut body)?; + + let mut cloned_body = body.clone(); + + let mut result_name = get_first_ident(&mut cloned_body, g.span())?.to_string(); + + move_punct(&mut cloned_body, ':')?; + + if cloned_body.peek().is_none() { + return end_of_input; + } + + let mut result_type = get_until( + &mut cloned_body, + |tree| matches!(tree, TokenTree::Punct(p) if p.as_char() == ','), + true, + true, + )?; + + let mut result = (result_name, result_type); + + 'search: while let Some(tree) = body.next() { + match tree { + TokenTree::Punct(p) if p.as_char() == '#' => match body.peek() { + Some(TokenTree::Group(g)) if g.delimiter() == Delimiter::Bracket => { + let mut attr_stream = g.stream().into_iter().peekable(); + + let mut found_attribute = false; + + while let Some(TokenTree::Ident(id)) = attr_stream.next() { + if id.to_string() == "graph" { + found_attribute = true; + + break; + } + + let _ = move_punct(&mut attr_stream, ','); + } + + body.next(); + + if found_attribute { + get_visibility_mod(&mut body)?; + + result_name = get_ident(&mut body)?.to_string(); + + move_punct(&mut body, ':')?; + + result_type = get_until( + &mut body, + |tree| matches!(tree, TokenTree::Punct(p) if p.as_char() == ','), + true, + true, + )?; + + result = (result_name, result_type); + + break 'search; + } + } + Some(_) => { + return myerror!("expected a group enclosed in square brackets", body); + } + None => { + return end_of_input; + } + }, + _ => {} + } + } + + Ok(result) + } + Some(_) => myerror!("expected a group or a semicolon", input), + + _ => end_of_input, + } +} + +fn get_generics( + input: &mut Peekable<impl Iterator<Item = TokenTree>>, +) -> Result<Vec<Generic>, CompileError> { + // Assume the starting '<' punct has already been consumed. + + let mut generic_map: HashMap<String, TokenStream> = Default::default(); + + let mut result: Vec<Generic> = Vec::new(); + + while !matches!(input.peek(), Some(TokenTree::Punct(p)) if p.as_char() == '>') { + let ident = get_ident(input)?.to_string(); + + let mut stream = TokenStream::new(); + + if matches!(input.peek(), Some(TokenTree::Punct(p)) if p.as_char() == ':') { + input.next(); + stream = get_until( + input, + |tree| matches!(tree, TokenTree::Punct(p) if p.as_char() == ',' || p.as_char() == '>'), + false, + false, + )?; + } + + generic_map.insert(ident, stream); - for tree in input { - println!("tree = {tree:?}"); + let _ = move_punct(input, ','); } - TokenStream::new() + assert!(matches!(input.next(), Some(TokenTree::Punct(p)) if p.as_char() == '>')); + + if matches!(input.peek(), Some(TokenTree::Ident(id)) if id.to_string() == "where") { + // where clauses + + input.next(); + + while !matches!(input.peek(), Some(TokenTree::Group(g)) if g.delimiter() == Delimiter::Brace) + { + let ident = get_ident(input)?.to_string(); + + move_punct(input, ':')?; + + let stream = get_until( + input, + |tree| match tree { + TokenTree::Punct(p) if p.as_char() == ',' => true, + TokenTree::Group(g) if g.delimiter() == Delimiter::Brace => true, + _ => false, + }, + false, + false, + )?; + + generic_map.insert(ident, stream); + + let _ = move_punct(input, ','); + } + } + + if generic_map.is_empty() { + // this is not valid syntax anyways + return myerror!("empty generics section?", input); + } + + for (k, v) in generic_map { + result.push(Generic::new(Ident::new(k.as_str(), Span::mixed_site()), v)); + } + + Ok(result) +} + +fn get_ident(input: &mut Peekable<impl Iterator<Item = TokenTree>>) -> Result<Ident, CompileError> { + match input.peek() { + Some(TokenTree::Ident(id)) => { + let id = id.clone(); + + input.next(); + + Ok(id) + } + Some(next_tree) => { + let span = next_tree.span(); + + Err(CompileError::new("expected an identifier", span)) + } + _ => Err(CompileError::new( + "unexpected end of input", + Span::mixed_site(), + )), + } +} + +fn get_first_ident( + input: &mut Peekable<impl Iterator<Item = TokenTree>>, + span: Span, +) -> Result<Ident, CompileError> { + while let Some(tree) = input.next() { + match tree { + TokenTree::Ident(id) => { + return Ok(id); + } + _ => {} + } + } + + Err(CompileError::new("expect at least one identifier", span)) +} + +fn get_until( + input: &mut Peekable<impl Iterator<Item = TokenTree>>, + predicate: impl Fn(&TokenTree) -> bool, + accept_end: bool, + consume_boundary: bool, +) -> Result<TokenStream, CompileError> { + let mut trees: Vec<TokenTree> = Vec::new(); + + let mut found_predicate = false; + + if consume_boundary { + while let Some(tree) = input.next() { + if predicate(&tree) { + found_predicate = true; + break; + } + + trees.push(tree); + } + } else { + while let Some(tree) = input.peek() { + if predicate(tree) { + found_predicate = true; + break; + } + + let tree = input.next().unwrap(); + + trees.push(tree); + } + } + + if found_predicate || accept_end { + Ok(trees.into_iter().collect()) + } else { + Err(CompileError::new( + "unexpected end of input", + Span::mixed_site(), + )) + } +} + +fn move_punct( + input: &mut Peekable<impl Iterator<Item = TokenTree>>, + punct: char, +) -> Result<(), CompileError> { + let error_mes = format!("expect punctuation {punct}"); + + match input.peek() { + Some(TokenTree::Punct(p)) if p.as_char() == punct => { + input.next(); + + Ok(()) + } + Some(_) => myerror!(error_mes, input), + _ => Err(CompileError::new( + "unexpected end of input", + Span::mixed_site(), + )), + } +} + +fn move_attributes( + input: &mut Peekable<impl Iterator<Item = TokenTree>>, +) -> Result<(), CompileError> { + let error_mes = "expect attributes"; + let end_of_input = Err(CompileError::new( + "unexpected end of input", + Span::mixed_site(), + )); + + match input.peek() { + Some(TokenTree::Punct(p)) if p.as_char() == '#' => { + input.next(); + + match input.peek() { + Some(TokenTree::Group(g)) if g.delimiter() == Delimiter::Bracket => { + input.next(); + } + Some(_) => { + return myerror!("expected a group in square brackets", input); + } + _ => { + return end_of_input; + } + } + + Ok(()) + } + Some(_) => myerror!(error_mes, input), + _ => end_of_input, + } } diff --git a/graph_macro/tests/works.rs b/graph_macro/tests/works.rs index fe8a853..a57e866 100644 --- a/graph_macro/tests/works.rs +++ b/graph_macro/tests/works.rs @@ -1,13 +1,98 @@ #![allow(dead_code)] -use graph_macro::Testing; +use graph_macro::Graph; -#[derive(Debug, Testing)] -struct Haha { - size: usize, +#[derive(Debug, Graph, Default)] +pub(crate) struct Haha { + test: String, + #[graph] + little_graph: graph::ALGraph, +} + +#[derive(Debug)] +/// Testing docs +#[allow(unused)] +#[derive(Default, Graph)] +pub struct HahaU(pub(crate) graph::ALGraph); + +#[derive(Debug, Graph)] +pub struct HahaG<T: graph::GraphLabel> { + graph: graph::DLGraph<T>, +} + +impl<T: graph::GraphLabel> Default for HahaG<T> { + fn default() -> Self { + Self { + graph: Default::default(), + } + } +} + +#[derive(Debug, Graph)] +pub struct HahaW<T> +where + T: graph::GraphLabel, +{ + name: String, + #[graph] + graph: graph::DLGraph<T>, +} + +impl<T: graph::GraphLabel> Default for HahaW<T> { + fn default() -> Self { + Self { + name: Default::default(), + graph: Default::default(), + } + } +} + +impl Haha { + fn new(test: impl ToString) -> Self { + use graph::builder::Builder; + + let test = test.to_string(); + let mut little_graph_builder: graph::adlist::ALGBuilder = Default::default(); + + little_graph_builder.add_vertex(); + little_graph_builder.add_vertex(); + little_graph_builder.add_edge(0, 1, ()).unwrap(); + + let little_graph = little_graph_builder.build(); + + Self { little_graph, test } + } } #[test] fn it_works() { - println!("it works: {:?}", Haha { size: 0 }); + use graph::{builder::Builder, Graph}; + let haha = Haha::new("test"); + + assert!(!haha.is_empty()); + + assert_eq!(haha.has_edge(0, 1), Ok(true)); + + let hahaw = HahaW::<usize>::default(); + + assert!(hahaw.is_empty()); + + assert!(matches!( + hahaw.has_edge(0, 1), + Err(graph::error::Error::IndexOutOfBounds(0, 0)) + )); + + let mut builder: graph::adlist::ALGBuilder = Default::default(); + + let first = builder.add_vertex(); + let second = builder.add_vertex(); + builder.add_edge(first, second, ()).unwrap(); + + let hahau = HahaU(builder.build()); + + assert!(!hahau.is_empty()); + + assert_eq!(hahau.has_edge(0, 1), Ok(true)); + + dbg!(haha, hahaw, hahau); } |