RFC RustDOT: graph! { A -- A -- B; A -- C; }

[daniel-pfeiffer]

rust_dot.rs.gz

This is WIP, but already a quite a complete implementation of DOT as native Rust. E.g.:

let g /* UnGraph<&str, ()> */ = graph! {
    node [ label = "[#" id "]" ];
    // like "[#1]" -- "[#2]" -- "[#4]"; "[#1]" -- "[#3]" -- "[#4]";
    1 -- { 2 3 } -- 4;
};

TODO:

• Clean up and finish the docs.
• Edge defaults and digraph! {} need to be implemented. The latter is a fairly mechanical translation of half what I have, falling back to the 1st half of _graph!() as is.
• While it's nice to have a closure as weight-generator, that will hardly work for &'static str. That needs some syntax to get $id into concat!("prefix ", $id, " postfix"). Except the macro input can't specify $id, which is internal. Maybe something like node [label = $($prefix:literal)? id $($postfix:literal)?] and edge [label = $($prefix:literal)? id.0 $($midfix:literal)? id.1 $($postfix:literal)?]
• More test cases
• Systematic coverage of all graph types. At 1st sight they don't seem to have consistent constructors (e.g. sometimes <_, _, Ty> needs 3, sometimes new for undirected sometimes new_undirected). Either fix that upstream or (for the time being) do a match stringify!($type), which should boil down to one constructor call at compile time.
• Make ID map accessible, and passable to next graph! { self = … }

Please look at the comments and tests at the end and share here what you think! I have tried to be as 'static as possible, with only one temporary hashmap as an exception. Nonetheless I wonder if this could be more efficient.

Edit: Concat ID, as shown above, caused a major rewrite. As a result this now also works better, more consistently. Module docs got a lot better.

[daniel-pfeiffer]

Discovering the sheer power of declarative macros has been an amazing journey. Where this stands, it’s not difficult to add edge defaults and a variant digraph!. That would already make it quite complete.

However there are some rough spots, which seem impossible to address:

• This can only be recursive, tt-munching through the statements. Needing to extend the compilers emergency brake, to accomodate big graphs, feels wrong.
• ID stringification is ok for all normal cases, but not quite right.
• If N gets inferred, even giving all nodes a non &str weight, you still have to set a matching default.

All of this got me exploring the supposed dragon den of procedural macros. Seems they’re not as daunting as many claim. While it’s probably more work to implement it that way, all of the rough edges would go away. And it would be easy to get even closer to DOT, e.g. ; could be optional. Based on that many DOT files could be simply turned into Rust files, parsed at compile time. Just wrap them like:

use petgraph::csr::digraph;
// IDE can help with exact type returned by macro
pub fn some_name() -> petgraph::csr::Csr<…> {
    digraph! {
        …
    }
}

With a new start I would separate this into two layers. A basic macro would return an abstract graph. Since the macro generates this tuple as literal compiler input, arrays don’t need a size declaration. It might look like:

(bool, // directed
 [(&'static str, N), …], // the nodes with their stringified ID
 [(usize, usize, E), …], // the edges, with indices into the node array
)

Now N and E might optionally be either

• not present
• the value of the weight or label attribute, similar to the current implementation. These currently default to stringified ID and E = ().
• Maybe, though not currently relevant to Petgraph: HashMap<&'static str, &'static str> for each attribute’s name to value – not sure about this one yet, as the value’s type should be able to differ, e.g. weight: N. Maybe a huge struct for all valid attributes, with each an Option<individual_attribute_type>…

Then other macros, like graphmap::graph! {} or matrix_graph::digraph! {} would be thin wrappers around this with new(), a map over the node array and a loops over the edges.

For example

graph! {
    foo [ label = "foobar" ];
    foo -- foo [ label = "yes" ];
    foo -- baz [ label = "maybe" ];
    baz -- baz [ label = "no" ];
}

could be turned into far less code than I generate now (and much of which could be a helper function, maybe with a rayon variant or another helper macro):

let (_, nodes, edges) = (false,
    [("foo", "foobar"), ("baz", "baz")],
    [(0, 0, "yes"), (0, 1, "maybe"), (1, 1, "no")]
);
let mut graph = petgraph::graph::Graph::<_, _, petgraph::Undirected>::new_undirected();
let nodes: Vec<_> = nodes
    .iter()
    .map(|node| graph
        .add_node(node.1))
    .collect();
for edge in edges {
    graph
        .add_edge(nodes[edge.0], nodes[edge.1], edge.2);
};

[daniel-pfeiffer]

This has materialised as crate rust_dot. Still a plain macro, not yet a proc-macro, but built around that technology. Turns out this also allows parsing strings or files.