{

enum token_type

{

kw_strict,

kw_graph,

kw_digraph,

kw_node,

kw_edge,

kw_subgraph,

left_brace,

right_brace,

semicolon,

equal,

left_bracket,

right_bracket,

comma,

colon,

dash_greater,

dash_dash,

plus,

left_paren,

right_paren,

at,

identifier,

quoted_string, // Only used internally in tokenizer

eof,

invalid

};

token_type type;

std::string normalized_value; // May have double-quotes removed and/or

// some escapes replaced

token(token_type type, const std::string& normalized_value)

: type(type), normalized_value(normalized_value)

{

}

token() : type(invalid), normalized_value("") {}

friend std::ostream& operator<<(std::ostream& o, const token& t)

{

switch (t.type)

{

case token::kw_strict:

o << "<strict>";

break;

case token::kw_graph:

o << "<graph>";

break;

case token::kw_digraph:

o << "<digraph>";

break;

case token::kw_node:

o << "<node>";

break;

case token::kw_edge:

o << "<edge>";

break;

case token::kw_subgraph:

o << "<subgraph>";

break;

case token::left_brace:

o << "<left_brace>";

break;

case token::right_brace:

o << "<right_brace>";

break;

case token::semicolon:

o << "<semicolon>";

break;

case token::equal:

o << "<equal>";

break;

case token::left_bracket:

o << "<left_bracket>";

break;

case token::right_bracket:

o << "<right_bracket>";

break;

case token::comma:

o << "<comma>";

break;

case token::colon:

o << "<colon>";

break;

case token::dash_greater:

o << "<dash-greater>";

break;

case token::dash_dash:

o << "<dash-dash>";

break;

case token::plus:

o << "<plus>";

break;

case token::left_paren:

o << "<left_paren>";

break;

case token::right_paren:

o << "<right_paren>";

break;

case token::at:

o << "<at>";

break;

case token::identifier:

o << "<identifier>";

break;

case token::quoted_string:

o << "<quoted_string>";

break;

case token::eof:

o << "<eof>";

break;

default:

o << "<invalid type>";

break;

}

o << " '" << t.normalized_value << "'";

return o;

}

{

if (bad_char == '\0')

{

return bad_graphviz_syntax(errmsg + " (at end of input)");

}

else

{

return bad_graphviz_syntax(

errmsg + " (char is '" + bad_char + "')");

}

const std::string& errmsg, const token& bad_token)

{

return bad_graphviz_syntax(errmsg + " (token is \""

+ boost::lexical_cast< std::string >(bad_token) + "\")");

{

std::string::const_iterator begin, end;

std::vector< token > lookahead;

// Precomputed regexes

boost::regex stuff_to_skip;

boost::regex basic_id_token;

boost::regex punctuation_token;

boost::regex number_token;

boost::regex quoted_string_token;

boost::regex xml_tag_token;

boost::regex cdata;

tokenizer(const std::string& str) : begin(str.begin()), end(str.end())

{

// std::string end_of_token = "(?=(?:\\W))"; // SEHE: unused?

std::string whitespace = "(?:\\s+)";

std::string slash_slash_comment = "(?://.*?$)";

std::string slash_star_comment = "(?:/\\*.*?\\*/)";

std::string hash_comment = "(?:^#.*?$)";

std::string backslash_newline = "(?:[\\\\][\\n])";

stuff_to_skip = "\\A(?:" + whitespace + "|" + slash_slash_comment

+ "|" + slash_star_comment + "|" + hash_comment + "|"

+ backslash_newline + ")*";

basic_id_token = "\\A([[:alpha:]_](?:\\w*))";

punctuation_token = "\\A([][{};=,:+()@]|[-][>-])";

number_token = "\\A([-]?(?:(?:\\.\\d+)|(?:\\d+(?:\\.\\d*)?)))";

quoted_string_token = "\\A(\"(?:[^\"\\\\]|(?:[\\\\].))*\")";

xml_tag_token

= "\\A<(/?)(?:[^!?'\"]|(?:'[^']*?')|(?:\"[^\"]*?\"))*?(/?)>";

cdata = "\\A\\Q<![CDATA[\\E.*?\\Q]]>\\E";

}

void skip()

{

boost::match_results< std::string::const_iterator > results;

#ifndef NDEBUG

bool found =

#endif

boost::regex_search(begin, end, results, stuff_to_skip);

#ifndef NDEBUG

BOOST_ASSERT(found);

#endif

boost::sub_match< std::string::const_iterator > sm1

= results.suffix();

BOOST_ASSERT(sm1.second == end);

begin = sm1.first;

}

token get_token_raw()

{

if (!lookahead.empty())

{

token t = lookahead.front();

lookahead.erase(lookahead.begin());

return t;

}

skip();

if (begin == end)

return token(token::eof, "");

// Look for keywords first

bool found;

boost::match_results< std::string::const_iterator > results;

found = boost::regex_search(begin, end, results, basic_id_token);

if (found)

{

std::string str = results[1].str();

std::string str_lower = str;

std::transform(

str_lower.begin(),

str_lower.end(),

str_lower.begin(),

[](unsigned char c) { return static_cast< char >(std::tolower(c)); }

);

begin = results.suffix().first;

if (str_lower == "strict")

{

return token(token::kw_strict, str);

}

else if (str_lower == "graph")

{

return token(token::kw_graph, str);

}

else if (str_lower == "digraph")

{

return token(token::kw_digraph, str);

}

else if (str_lower == "node")

{

return token(token::kw_node, str);

}

else if (str_lower == "edge")

{

return token(token::kw_edge, str);

}

else if (str_lower == "subgraph")

{

return token(token::kw_subgraph, str);

}

else

{

return token(token::identifier, str);

}

}

found = boost::regex_search(begin, end, results, punctuation_token);

if (found)

{

std::string str = results[1].str();

begin = results.suffix().first;

switch (str[0])

{

case '[':

return token(token::left_bracket, str);

case ']':

return token(token::right_bracket, str);

case '{':

return token(token::left_brace, str);

case '}':

return token(token::right_brace, str);

case ';':

return token(token::semicolon, str);

case '=':

return token(token::equal, str);

case ',':

return token(token::comma, str);

case ':':

return token(token::colon, str);

case '+':

return token(token::plus, str);

case '(':

return token(token::left_paren, str);

case ')':

return token(token::right_paren, str);

case '@':

return token(token::at, str);

case '-':

{

switch (str[1])

{

case '-':

return token(token::dash_dash, str);

case '>':

return token(token::dash_greater, str);

default:

BOOST_ASSERT(!"Definition of punctuation_token does "

"not match switch statement");

}

// Prevent static analyzers complaining about fallthrough:

break;

}

default:

BOOST_ASSERT(!"Definition of punctuation_token does not "

"match switch statement");

}

}

found = boost::regex_search(begin, end, results, number_token);

if (found)

{

std::string str = results[1].str();

begin = results.suffix().first;

return token(token::identifier, str);

}

found

= boost::regex_search(begin, end, results, quoted_string_token);

if (found)

{

std::string str = results[1].str();

begin = results.suffix().first;

// Remove the beginning and ending quotes

BOOST_ASSERT(str.size() >= 2);

str.erase(str.begin());

str.erase(str.end() - 1);

// Unescape quotes in the middle, but nothing else (see format

// spec)

for (size_t i = 0; i + 1 < str.size() /* May change */; ++i)

{

if (str[i] == '\\' && str[i + 1] == '"')

{

str.erase(str.begin() + i);

// Don't need to adjust i

}

else if (str[i] == '\\' && str[i + 1] == '\n')

{

str.erase(str.begin() + i);

str.erase(str.begin() + i);

--i; // Invert ++ that will be applied

}

}

return token(token::quoted_string, str);

}

if (*begin == '<')

{

std::string::const_iterator saved_begin = begin;

int counter = 0;

do

{

if (begin == end)

throw_lex_error("Unclosed HTML string");

if (*begin != '<')

{

++begin;

continue;

}

found = boost::regex_search(

begin, end, results, xml_tag_token);

if (found)

{

begin = results.suffix().first;

if (results[1].str() == "/")

{ // Close tag

--counter;

}

else if (results[2].str() == "/")

{ // Empty tag

}

else

{ // Open tag

++counter;

}

continue;

}

found = boost::regex_search(begin, end, results, cdata);

if (found)

{

begin = results.suffix().first;

continue;

}

throw_lex_error("Invalid contents in HTML string");

} while (counter > 0);

return token(

token::identifier, std::string(saved_begin, begin));

}

else

{

throw_lex_error("Invalid character");

return token();

}

}

token peek_token_raw()

{

if (lookahead.empty())

{

token t = get_token_raw();

lookahead.push_back(t);

}

return lookahead.front();

}

token get_token()

{ // Handle string concatenation

token t = get_token_raw();

if (t.type != token::quoted_string)

return t;

std::string str = t.normalized_value;

while (peek_token_raw().type == token::plus)

{

get_token_raw();

token t2 = get_token_raw();

if (t2.type != token::quoted_string)

{

throw_lex_error(

"Must have quoted string after string concatenation");

}

str += t2.normalized_value;

}

return token(

token::identifier, str); // Note that quoted_string does not get

// passed to the parser

}

void throw_lex_error(const std::string& errmsg)

{

boost::throw_exception(

lex_error(errmsg, (begin == end ? '\0' : *begin)));

}

};

struct edge_endpoint

{

bool is_subgraph;

node_and_port node_ep;

subgraph_name subgraph_ep;

static edge_endpoint node(const node_and_port& ep)

{

edge_endpoint r;

r.is_subgraph = false;

r.node_ep = ep;

return r;

}

static edge_endpoint subgraph(const subgraph_name& ep)

{

edge_endpoint r;

r.is_subgraph = true;

r.subgraph_ep = ep;

return r;

}

};

struct node_or_subgraph_ref

{

bool is_subgraph;

std::string

name; // Name for subgraphs or nodes, "___root___" for root graph

};

static node_or_subgraph_ref noderef(const node_name& n)

{

node_or_subgraph_ref r;

r.is_subgraph = false;

r.name = n;

return r;

}

static node_or_subgraph_ref subgraphref(const subgraph_name& n)

{

node_or_subgraph_ref r;

r.is_subgraph = true;

r.name = n;

return r;

}

typedef std::vector< node_or_subgraph_ref > subgraph_member_list;

struct subgraph_info

{

properties def_node_props;

properties def_edge_props;

subgraph_member_list members;

};

struct parser

{

tokenizer the_tokenizer;

std::vector< token > lookahead;

parser_result& r;

std::map< subgraph_name, subgraph_info > subgraphs;

std::string current_subgraph_name;

int sgcounter; // Counter for anonymous subgraphs

long sgnesting_level;

std::set< std::pair< node_name, node_name > >

existing_edges; // Used for checking in strict graphs

subgraph_info& current() { return subgraphs[current_subgraph_name]; }

properties& current_graph_props()

{

return r.graph_props[current_subgraph_name];

}

subgraph_member_list& current_members() { return current().members; }

parser(const std::string& gr, parser_result& result)

: the_tokenizer(gr), lookahead(), r(result), sgcounter(0), sgnesting_level(0)

{

current_subgraph_name = "___root___";

current() = subgraph_info(); // Initialize root graph

current_graph_props().clear();

current_members().clear();

}

token get()

{

if (lookahead.empty())

{

token t = the_tokenizer.get_token();

return t;

}

else

{

token t = lookahead.front();

lookahead.erase(lookahead.begin());

return t;

}

}

token peek()

{

if (lookahead.empty())

{

lookahead.push_back(the_tokenizer.get_token());

}

return lookahead.front();

}

void error(const std::string& str)

{

boost::throw_exception(parse_error(str, peek()));

}

void parse_graph(bool want_directed)

{

bool is_strict = false;

bool is_directed = false;

std::string name;

if (peek().type == token::kw_strict)

{

get();

is_strict = true;

}

switch (peek().type)

{

case token::kw_graph:

is_directed = false;

break;

case token::kw_digraph:

is_directed = true;

break;

default:

error("Wanted \"graph\" or \"digraph\"");

}

r.graph_is_directed = is_directed; // Used to check edges

r.graph_is_strict = is_strict;

if (want_directed != r.graph_is_directed)

{

if (want_directed)

{

boost::throw_exception(boost::undirected_graph_error());

}

else

{

boost::throw_exception(boost::directed_graph_error());

}

}

get();

switch (peek().type)

{

case token::identifier:

name = peek().normalized_value;

get();

break;

case token::left_brace:

break;

default:

error("Wanted a graph name or left brace");

}

if (peek().type == token::left_brace)

get();

else

error("Wanted a left brace to start the graph");

parse_stmt_list();

if (peek().type == token::right_brace)

get();

else

error("Wanted a right brace to end the graph");

if (peek().type == token::eof)

{

}

else

error("Wanted end of file");

}

void parse_stmt_list()

{

while (true)

{

if (peek().type == token::right_brace)

return;

parse_stmt();

if (peek().type == token::semicolon)

get();

}

}

void parse_stmt()

{

switch (peek().type)

{

case token::kw_node:

case token::kw_edge:

case token::kw_graph:

parse_attr_stmt();

break;

case token::kw_subgraph:

case token::left_brace:

case token::identifier:

{

token id = get();

if (id.type == token::identifier && peek().type == token::equal)

{ // Graph property

get();

if (peek().type != token::identifier)

error("Wanted identifier as right side of =");

token id2 = get();

current_graph_props()[id.normalized_value]

= id2.normalized_value;

}

else

{

edge_endpoint ep = parse_endpoint_rest(id);

if (peek().type == token::dash_dash

|| peek().type == token::dash_greater)

{ // Edge

parse_edge_stmt(ep);

}

else

{

if (!ep.is_subgraph)

{ // Only nodes can have attribute lists

// This node already exists because of its first

// mention (properties set to defaults by

// parse_node_and_port, called by

// parse_endpoint_rest)

properties this_node_props;

if (peek().type == token::left_bracket)

{

parse_attr_list(this_node_props);

}

for (properties::const_iterator i

= this_node_props.begin();

i != this_node_props.end(); ++i)

{

// Override old properties with same names

r.nodes[ep.node_ep.name][i->first] = i->second;

}

current_members().push_back(

noderef(ep.node_ep.name));

}

else

{

current_members().push_back(

subgraphref(ep.subgraph_ep));

}

}

}

break;

}

default:

error("Invalid start token for statement");

}

}

void parse_attr_stmt()

{

switch (get().type)

{

case token::kw_graph:

parse_attr_list(current_graph_props());

break;

case token::kw_node:

parse_attr_list(current().def_node_props);

break;

case token::kw_edge:

parse_attr_list(current().def_edge_props);

break;

default:

BOOST_ASSERT(!"Bad attr_stmt case");

}

}

edge_endpoint parse_endpoint()

{

switch (peek().type)

{

case token::kw_subgraph:

case token::left_brace:

case token::identifier:

{

token first = get();

return parse_endpoint_rest(first);

}

default:

{

error("Wanted \"subgraph\", \"{\", or identifier to start node "

"or subgraph");

return edge_endpoint();

}

}

}

edge_endpoint parse_endpoint_rest(const token& first_token)

{

switch (first_token.type)

{

case token::kw_subgraph:

case token::left_brace:

return edge_endpoint::subgraph(parse_subgraph(first_token));

default:

return edge_endpoint::node(parse_node_and_port(first_token));

}

}

subgraph_name parse_subgraph(const token& first_token)

{

std::string name;

bool is_anonymous = true;

if (first_token.type == token::kw_subgraph)

{

switch (peek().type)

{

case token::identifier:

name = get().normalized_value;

is_anonymous = false;

break;

case token::left_brace:

is_anonymous = true;

break;

default:

error("Subgraph reference needs a name");

break;

}

}

if (is_anonymous)

{

name = "___subgraph_"

+ boost::lexical_cast< std::string >(++sgcounter);

}

if (subgraphs.find(name) == subgraphs.end())

{

subgraphs[name]

= current(); // Initialize properties and defaults

subgraphs[name].members.clear(); // Except member list

}

if (!is_anonymous && peek().type != token::left_brace)

{

return name;

}

subgraph_name old_sg = current_subgraph_name;

if (++sgnesting_level > max_subgraph_nesting_level)

{

error("Exceeded maximum subgraph nesting level");

}

current_subgraph_name = name;

if (first_token.type != token::left_brace)

{

if (peek().type == token::left_brace)

get();

else

error("Wanted left brace to start subgraph");

}

parse_stmt_list();

if (peek().type == token::right_brace)

get();

else

error("Wanted right brace to end subgraph");

current_subgraph_name = old_sg;

sgnesting_level -= 1;

return name;

}

node_and_port parse_node_and_port(const token& name)

{

// A node ID is a node name, followed optionally by a port angle and

// a port location (in either order); a port location is either :id,

// :id:id, or :(id,id); the last two forms are treated as equivalent

// although I am not sure about that.

node_and_port id;

id.name = name.normalized_value;

parse_more:

switch (peek().type)

{

case token::at:

{

get();

if (peek().type != token::identifier)

error("Wanted identifier as port angle");

if (!id.angle.empty())

error("Duplicate port angle");

id.angle = get().normalized_value;

goto parse_more;

}

case token::colon:

{

get();

if (!id.location.empty())

error("Duplicate port location");

switch (peek().type)

{

case token::identifier:

{

id.location.push_back(get().normalized_value);

switch (peek().type)

{

case token::colon:

{

get();

if (peek().type != token::identifier)

error("Wanted identifier as port location");

id.location.push_back(get().normalized_value);

goto parse_more;

}

default:

goto parse_more;

}

}

case token::left_paren:

{

get();

if (peek().type != token::identifier)

error("Wanted identifier as first element of port "

"location");

id.location.push_back(get().normalized_value);

if (peek().type != token::comma)

error("Wanted comma between parts of port location");

get();

if (peek().type != token::identifier)

error("Wanted identifier as second element of port "

"location");

id.location.push_back(get().normalized_value);

if (peek().type != token::right_paren)

error(

"Wanted right parenthesis to close port location");

get();

goto parse_more;

}

default:

error("Wanted identifier or left parenthesis as start of "

"port location");

}

}

break;

default:

break;

}

if (r.nodes.find(id.name) == r.nodes.end())

{ // First mention

r.nodes[id.name] = current().def_node_props;

}

return id;

}

void parse_edge_stmt(const edge_endpoint& lhs)

{

std::vector< edge_endpoint > nodes_in_chain(1, lhs);

while (true)

{

bool leave_loop = true;

switch (peek().type)

{

case token::dash_dash:

{

if (r.graph_is_directed)

error("Using -- in directed graph");

get();

nodes_in_chain.push_back(parse_endpoint());

leave_loop = false;

break;

}

case token::dash_greater:

{

if (!r.graph_is_directed)

error("Using -> in undirected graph");

get();

nodes_in_chain.push_back(parse_endpoint());

leave_loop = false;

break;

}

default:

leave_loop = true;

break;

}

if (leave_loop)

break;

}

properties this_edge_props = current().def_edge_props;

if (peek().type == token::left_bracket)

parse_attr_list(this_edge_props);

BOOST_ASSERT(nodes_in_chain.size()

>= 2); // Should be in node parser otherwise

for (size_t i = 0; i + 1 < nodes_in_chain.size(); ++i)

{

do_orig_edge(

nodes_in_chain[i], nodes_in_chain[i + 1], this_edge_props);

}

}

// Do an edge from the file, the edge may need to be expanded if it

// connects to a subgraph

void do_orig_edge(const edge_endpoint& src, const edge_endpoint& tgt,

const properties& props)

{

std::set< node_and_port > sources = get_recursive_members(src);

std::set< node_and_port > targets = get_recursive_members(tgt);

for (std::set< node_and_port >::const_iterator i = sources.begin();

i != sources.end(); ++i)

{

for (std::set< node_and_port >::const_iterator j

= targets.begin();

j != targets.end(); ++j)

{

do_edge(*i, *j, props);

}

}

}

// Get nodes in an edge_endpoint, recursively

std::set< node_and_port > get_recursive_members(

const edge_endpoint& orig_ep)

{

std::set< node_and_port > result;

std::vector< edge_endpoint > worklist(1, orig_ep);

std::set< subgraph_name > done;

while (!worklist.empty())

{

edge_endpoint ep = worklist.back();

worklist.pop_back();

if (ep.is_subgraph)

{

if (done.find(ep.subgraph_ep) == done.end())

{

done.insert(ep.subgraph_ep);

std::map< subgraph_name, subgraph_info >::const_iterator

info_i

= subgraphs.find(ep.subgraph_ep);

if (info_i != subgraphs.end())