]> git.proxmox.com Git - ceph.git/blob - ceph/src/boost/boost/graph/detail/read_graphviz_spirit.hpp
bump version to 18.2.2-pve1
[ceph.git] / ceph / src / boost / boost / graph / detail / read_graphviz_spirit.hpp
1 // Copyright 2004-9 Trustees of Indiana University
2
3 // Distributed under the Boost Software License, Version 1.0.
4 // (See accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
6
7 //
8 // read_graphviz_spirit.hpp -
9 // Initialize a model of the BGL's MutableGraph concept and an associated
10 // collection of property maps using a graph expressed in the GraphViz
11 // DOT Language.
12 //
13 // Based on the grammar found at:
14 // https://web.archive.org/web/20041213234742/http://www.graphviz.org/cvs/doc/info/lang.html
15 //
16 // See documentation for this code at:
17 // http://www.boost.org/libs/graph/doc/read_graphviz.html
18 //
19
20 // Author: Ronald Garcia
21 //
22
23 #ifndef BOOST_READ_GRAPHVIZ_SPIRIT_HPP
24 #define BOOST_READ_GRAPHVIZ_SPIRIT_HPP
25
26 // Phoenix/Spirit set these limits to 3, but I need more.
27 #define PHOENIX_LIMIT 6
28 #define BOOST_SPIRIT_CLOSURE_LIMIT 6
29
30 #include <boost/spirit/include/classic_multi_pass.hpp>
31 #include <boost/spirit/include/classic_core.hpp>
32 #include <boost/spirit/include/classic_confix.hpp>
33 #include <boost/spirit/include/classic_distinct.hpp>
34 #include <boost/spirit/include/classic_lists.hpp>
35 #include <boost/spirit/include/classic_escape_char.hpp>
36 #include <boost/spirit/include/classic_attribute.hpp>
37 #include <boost/spirit/include/classic_dynamic.hpp>
38 #include <boost/spirit/include/classic_actor.hpp>
39 #include <boost/spirit/include/classic_closure.hpp>
40 #include <boost/spirit/include/phoenix1.hpp>
41 #include <boost/spirit/include/phoenix1_binders.hpp>
42 #include <boost/ref.hpp>
43 #include <boost/function/function2.hpp>
44 #include <boost/type_traits/is_same.hpp>
45 #include <boost/property_map/dynamic_property_map.hpp>
46 #include <boost/graph/graph_traits.hpp>
47 #include <boost/detail/workaround.hpp>
48 #include <algorithm>
49 #include <exception> // for std::exception
50 #include <string>
51 #include <vector>
52 #include <set>
53 #include <utility>
54 #include <map>
55 #include <boost/graph/graphviz.hpp>
56 #include <boost/throw_exception.hpp>
57
58 namespace phoenix
59 {
60 // Workaround: std::map::operator[] uses a different return type than all
61 // other standard containers. Phoenix doesn't account for that.
62 template < typename TK, typename T0, typename T1 >
63 struct binary_operator< index_op, std::map< TK, T0 >, T1 >
64 {
65 typedef typename std::map< TK, T0 >::mapped_type& result_type;
66 static result_type eval(std::map< TK, T0 >& container, T1 const& index)
67 {
68 return container[index];
69 }
70 };
71 } // namespace phoenix
72
73 namespace boost
74 {
75 namespace detail
76 {
77 namespace graph
78 {
79
80 /////////////////////////////////////////////////////////////////////////////
81 // Application-specific type definitions
82 /////////////////////////////////////////////////////////////////////////////
83
84 typedef std::set< edge_t > edges_t;
85 typedef std::set< node_t > nodes_t;
86 typedef std::set< id_t > ids_t;
87 typedef std::map< edge_t, ids_t > edge_map_t;
88 typedef std::map< node_t, ids_t > node_map_t;
89 typedef std::map< id_t, id_t > props_t;
90 typedef std::map< id_t, props_t > subgraph_props_t;
91 typedef boost::function2< void, id_t const&, id_t const& > actor_t;
92 typedef std::vector< edge_t > edge_stack_t;
93 typedef std::map< id_t, nodes_t > subgraph_nodes_t;
94 typedef std::map< id_t, edges_t > subgraph_edges_t;
95
96 /////////////////////////////////////////////////////////////////////////////
97 // Stack frames used by semantic actions
98 /////////////////////////////////////////////////////////////////////////////
99 struct id_closure
100 : boost::spirit::classic::closure< id_closure, node_t >
101 {
102 member1 name;
103 };
104
105 struct node_id_closure
106 : boost::spirit::classic::closure< node_id_closure, node_t >
107 {
108 member1 name;
109 };
110
111 struct attr_list_closure
112 : boost::spirit::classic::closure< attr_list_closure, actor_t >
113 {
114 member1 prop_actor;
115 };
116
117 struct property_closure
118 : boost::spirit::classic::closure< property_closure, id_t, id_t >
119 {
120 member1 key;
121 member2 value;
122 };
123
124 struct data_stmt_closure
125 : boost::spirit::classic::closure< data_stmt_closure, nodes_t, nodes_t,
126 edge_stack_t, bool, node_t >
127 {
128 member1 sources;
129 member2 dests;
130 member3 edge_stack;
131 member4 saw_node;
132 member5 active_node;
133 };
134
135 struct subgraph_closure
136 : boost::spirit::classic::closure< subgraph_closure, nodes_t, edges_t,
137 node_t >
138 {
139 member1 nodes;
140 member2 edges;
141 member3 name;
142 };
143
144 /////////////////////////////////////////////////////////////////////////////
145 // Grammar and Actions for the DOT Language
146 /////////////////////////////////////////////////////////////////////////////
147
148 // Grammar for a dot file.
149 struct dot_grammar
150 : public boost::spirit::classic::grammar< dot_grammar >
151 {
152 mutate_graph& graph_;
153 explicit dot_grammar(mutate_graph& graph) : graph_(graph) {}
154
155 template < class ScannerT > struct definition
156 {
157
158 definition(dot_grammar const& self)
159 : self(self), subgraph_depth(0), keyword_p("0-9a-zA-Z_")
160 {
161 using namespace boost::spirit::classic;
162 using namespace phoenix;
163
164 // RG - Future Work
165 // - Handle multi-line strings using \ line continuation
166 // - Make keywords case insensitive
167 ID = (lexeme_d[(
168 (alpha_p | ch_p('_')) >> *(alnum_p | ch_p('_')))]
169 | real_p | lexeme_d[confix_p('"', *c_escape_ch_p, '"')]
170 | comment_nest_p('<', '>'))[ID.name
171 = construct_< std::string >(arg1, arg2)];
172
173 a_list = list_p(
174 ID[(a_list.key = arg1), (a_list.value = "true")] >> !(
175 ch_p('=') >> ID[a_list.value = arg1])[phoenix::bind(
176 &definition::call_prop_actor)(
177 var(*this), a_list.key, a_list.value)],
178 !ch_p(','));
179
180 attr_list = +(ch_p('[') >> !a_list >> ch_p(']'));
181
182 // RG - disregard port id's for now.
183 port_location = (ch_p(':') >> ID)
184 | (ch_p(':') >> ch_p('(') >> ID >> ch_p(',') >> ID
185 >> ch_p(')'));
186
187 port_angle = ch_p('@') >> ID;
188
189 port = port_location >> (!port_angle)
190 | port_angle >> (!port_location);
191
192 node_id
193 = (ID[node_id.name = arg1] >> (!port))[phoenix::bind(
194 &definition::memoize_node)(var(*this))];
195
196 graph_stmt = (ID[graph_stmt.key = arg1] >> ch_p('=')
197 >> ID[graph_stmt.value = arg1])[phoenix::bind(
198 &definition::call_graph_prop)(var(*this),
199 graph_stmt.key, graph_stmt.value)]; // Graph property.
200
201 attr_stmt
202 = (as_lower_d[keyword_p("graph")] >> attr_list(actor_t(
203 phoenix::bind(&definition::default_graph_prop)(
204 var(*this), arg1, arg2))))
205 | (as_lower_d[keyword_p("node")] >> attr_list(actor_t(
206 phoenix::bind(&definition::default_node_prop)(
207 var(*this), arg1, arg2))))
208 | (as_lower_d[keyword_p("edge")] >> attr_list(actor_t(
209 phoenix::bind(&definition::default_edge_prop)(
210 var(*this), arg1, arg2))));
211
212 // edge_head is set depending on the graph type
213 // (directed/undirected)
214 edgeop = ch_p('-') >> ch_p(boost::ref(edge_head));
215
216 edgeRHS = +(edgeop[(data_stmt.sources = data_stmt.dests),
217 (data_stmt.dests = construct_< nodes_t >())]
218 >> (subgraph[data_stmt.dests = arg1]
219 | node_id[phoenix::bind(&definition::insert_node)(
220 var(*this), data_stmt.dests, arg1)])
221 [phoenix::bind(&definition::activate_edge)(
222 var(*this), data_stmt.sources, data_stmt.dests,
223 var(edges), var(default_edge_props))]);
224
225 // To avoid backtracking, edge, node, and subgraph
226 // statements are processed as one nonterminal.
227 data_stmt
228 = (subgraph[(data_stmt.dests
229 = arg1), // will get moved in rhs
230 (data_stmt.saw_node = false)]
231 | node_id[(phoenix::bind(
232 &definition::insert_node)(
233 var(*this), data_stmt.dests, arg1)),
234 (data_stmt.saw_node = true),
235 #ifdef BOOST_GRAPH_DEBUG
236 (std::cout << val("AcTive Node: ") << arg1
237 << "\n"),
238 #endif // BOOST_GRAPH_DEBUG
239 (data_stmt.active_node = arg1)])
240 >> if_p(edgeRHS)[!attr_list(actor_t(phoenix::bind(
241 &definition::edge_prop)(
242 var(*this), arg1, arg2)))]
243 .else_p[if_p(data_stmt.saw_node)[!attr_list(
244 actor_t(phoenix::bind(
245 &definition::node_prop)(var(*this), arg1,
246 arg2)))] // otherwise it's a subgraph,
247 // nothing more to do.
248 ];
249
250 stmt = graph_stmt | attr_stmt | data_stmt;
251
252 stmt_list = *(stmt >> !ch_p(';'));
253
254 subgraph = !(as_lower_d[keyword_p("subgraph")]
255 >> (!ID[(subgraph.name = arg1),
256 (subgraph.nodes
257 = (var(subgraph_nodes))[arg1]),
258 (subgraph.edges
259 = (var(subgraph_edges))[arg1])]))
260 >> ch_p('{')[++var(subgraph_depth)] >> stmt_list
261 >> ch_p('}')[--var(subgraph_depth)]
262 [(var(subgraph_nodes))[subgraph.name]
263 = subgraph.nodes]
264 [(var(subgraph_edges))[subgraph.name]
265 = subgraph.edges]
266
267 | as_lower_d[keyword_p("subgraph")]
268 >> ID[(subgraph.nodes
269 = (var(subgraph_nodes))[arg1]),
270 (subgraph.edges = (var(subgraph_edges))[arg1])];
271
272 the_grammar = (!as_lower_d[keyword_p("strict")])
273 >> (as_lower_d[keyword_p(
274 "graph")][(var(edge_head) = '-'),
275 (phoenix::bind(&definition::check_undirected)(
276 var(*this)))]
277 | as_lower_d[keyword_p(
278 "digraph")][(var(edge_head) = '>'),
279 (phoenix::bind(&definition::check_directed)(
280 var(*this)))])
281 >> (!ID) >> ch_p('{') >> stmt_list >> ch_p('}');
282
283 } // definition()
284
285 typedef boost::spirit::classic::rule< ScannerT > rule_t;
286
287 rule_t const& start() const { return the_grammar; }
288
289 //
290 // Semantic actions
291 //
292
293 void check_undirected()
294 {
295 if (self.graph_.is_directed())
296 boost::throw_exception(boost::undirected_graph_error());
297 }
298
299 void check_directed()
300 {
301 if (!self.graph_.is_directed())
302 boost::throw_exception(boost::directed_graph_error());
303 }
304
305 void memoize_node()
306 {
307 id_t const& node = node_id.name();
308 props_t& node_props = default_node_props;
309
310 if (nodes.find(node) == nodes.end())
311 {
312 nodes.insert(node);
313 self.graph_.do_add_vertex(node);
314
315 node_map.insert(std::make_pair(node, ids_t()));
316
317 #ifdef BOOST_GRAPH_DEBUG
318 std::cout << "Add new node " << node << std::endl;
319 #endif // BOOST_GRAPH_DEBUG
320 // Set the default properties for this edge
321 // RG: Here I would actually set the properties
322 for (props_t::iterator i = node_props.begin();
323 i != node_props.end(); ++i)
324 {
325 set_node_property(node, i->first, i->second);
326 }
327 if (subgraph_depth > 0)
328 {
329 subgraph.nodes().insert(node);
330 // Set the subgraph's default properties as well
331 props_t& props
332 = subgraph_node_props[subgraph.name()];
333 for (props_t::iterator i = props.begin();
334 i != props.end(); ++i)
335 {
336 set_node_property(node, i->first, i->second);
337 }
338 }
339 }
340 else
341 {
342 #ifdef BOOST_GRAPH_DEBUG
343 std::cout << "See node " << node << std::endl;
344 #endif // BOOST_GRAPH_DEBUG
345 }
346 }
347
348 void activate_edge(nodes_t& sources, nodes_t& dests,
349 edges_t& edges, props_t& edge_props)
350 {
351 edge_stack_t& edge_stack = data_stmt.edge_stack();
352 for (nodes_t::iterator i = sources.begin();
353 i != sources.end(); ++i)
354 {
355 for (nodes_t::iterator j = dests.begin();
356 j != dests.end(); ++j)
357 {
358 // Create the edge and push onto the edge stack.
359 #ifdef BOOST_GRAPH_DEBUG
360 std::cout << "Edge " << *i << " to " << *j
361 << std::endl;
362 #endif // BOOST_GRAPH_DEBUG
363
364 edge_t edge = edge_t::new_edge();
365 edge_stack.push_back(edge);
366 edges.insert(edge);
367 edge_map.insert(std::make_pair(edge, ids_t()));
368
369 // Add the real edge.
370 self.graph_.do_add_edge(edge, *i, *j);
371
372 // Set the default properties for this edge
373 for (props_t::iterator k = edge_props.begin();
374 k != edge_props.end(); ++k)
375 {
376 set_edge_property(edge, k->first, k->second);
377 }
378 if (subgraph_depth > 0)
379 {
380 subgraph.edges().insert(edge);
381 // Set the subgraph's default properties as well
382 props_t& props
383 = subgraph_edge_props[subgraph.name()];
384 for (props_t::iterator k = props.begin();
385 k != props.end(); ++k)
386 {
387 set_edge_property(
388 edge, k->first, k->second);
389 }
390 }
391 }
392 }
393 }
394
395 // node_prop - Assign the property for the current active node.
396 void node_prop(id_t const& key, id_t const& value)
397 {
398 node_t& active_object = data_stmt.active_node();
399 set_node_property(active_object, key, value);
400 }
401
402 // edge_prop - Assign the property for the current active edges.
403 void edge_prop(id_t const& key, id_t const& value)
404 {
405 edge_stack_t const& active_edges_ = data_stmt.edge_stack();
406 for (edge_stack_t::const_iterator i = active_edges_.begin();
407 i != active_edges_.end(); ++i)
408 {
409 set_edge_property(*i, key, value);
410 }
411 }
412
413 // default_graph_prop - Store as a graph property.
414 void default_graph_prop(id_t const& key, id_t const& value)
415 {
416 #ifdef BOOST_GRAPH_DEBUG
417 std::cout << key << " = " << value << std::endl;
418 #endif // BOOST_GRAPH_DEBUG
419 self.graph_.set_graph_property(key, value);
420 }
421
422 // default_node_prop - declare default properties for any future
423 // new nodes
424 void default_node_prop(id_t const& key, id_t const& value)
425 {
426 nodes_t& nodes_
427 = subgraph_depth == 0 ? nodes : subgraph.nodes();
428 props_t& node_props_ = subgraph_depth == 0
429 ? default_node_props
430 : subgraph_node_props[subgraph.name()];
431
432 // add this to the selected list of default node properties.
433 node_props_[key] = value;
434 // for each node, set its property to default-constructed
435 // value
436 // if it hasn't been set already.
437 // set the dynamic property map value
438 for (nodes_t::iterator i = nodes_.begin();
439 i != nodes_.end(); ++i)
440 if (node_map[*i].find(key) == node_map[*i].end())
441 {
442 set_node_property(*i, key, id_t());
443 }
444 }
445
446 // default_edge_prop - declare default properties for any future
447 // new edges
448 void default_edge_prop(id_t const& key, id_t const& value)
449 {
450 edges_t& edges_
451 = subgraph_depth == 0 ? edges : subgraph.edges();
452 props_t& edge_props_ = subgraph_depth == 0
453 ? default_edge_props
454 : subgraph_edge_props[subgraph.name()];
455
456 // add this to the list of default edge properties.
457 edge_props_[key] = value;
458 // for each edge, set its property to be empty string
459 // set the dynamic property map value
460 for (edges_t::iterator i = edges_.begin();
461 i != edges_.end(); ++i)
462 if (edge_map[*i].find(key) == edge_map[*i].end())
463 set_edge_property(*i, key, id_t());
464 }
465
466 // helper function
467 void insert_node(nodes_t& nodes, id_t const& name)
468 {
469 nodes.insert(name);
470 }
471
472 void call_prop_actor(
473 std::string const& lhs, std::string const& rhs)
474 {
475 actor_t& actor = attr_list.prop_actor();
476 // If first and last characters of the rhs are
477 // double-quotes, remove them.
478 if (!rhs.empty() && rhs[0] == '"'
479 && rhs[rhs.size() - 1] == '"')
480 actor(lhs, rhs.substr(1, rhs.size() - 2));
481 else
482 actor(lhs, rhs);
483 }
484
485 void call_graph_prop(
486 std::string const& lhs, std::string const& rhs)
487 {
488 // If first and last characters of the rhs are
489 // double-quotes, remove them.
490 if (!rhs.empty() && rhs[0] == '"'
491 && rhs[rhs.size() - 1] == '"')
492 this->default_graph_prop(
493 lhs, rhs.substr(1, rhs.size() - 2));
494 else
495 this->default_graph_prop(lhs, rhs);
496 }
497
498 void set_node_property(
499 node_t const& node, id_t const& key, id_t const& value)
500 {
501
502 // Add the property key to the "set" table to avoid default
503 // overwrite
504 node_map[node].insert(key);
505 // Set the user's property map
506 self.graph_.set_node_property(key, node, value);
507 #ifdef BOOST_GRAPH_DEBUG
508 // Tell the world
509 std::cout << node << ": " << key << " = " << value
510 << std::endl;
511 #endif // BOOST_GRAPH_DEBUG
512 }
513
514 void set_edge_property(
515 edge_t const& edge, id_t const& key, id_t const& value)
516 {
517
518 // Add the property key to the "set" table to avoid default
519 // overwrite
520 edge_map[edge].insert(key);
521 // Set the user's property map
522 self.graph_.set_edge_property(key, edge, value);
523 #ifdef BOOST_GRAPH_DEBUG
524 // Tell the world
525 #if 0 // RG - edge representation changed,
526 std::cout << "(" << edge.first << "," << edge.second << "): "
527 #else
528 std::cout << "an edge: "
529 #endif // 0
530 << key << " = " << value << std::endl;
531 #endif // BOOST_GRAPH_DEBUG
532 }
533
534 // Variables explicitly initialized
535 dot_grammar const& self;
536 // if subgraph_depth > 0, then we're processing a subgraph.
537 int subgraph_depth;
538
539 // Keywords;
540 const boost::spirit::classic::distinct_parser<> keyword_p;
541 //
542 // rules that make up the grammar
543 //
544 boost::spirit::classic::rule< ScannerT, id_closure::context_t >
545 ID;
546 boost::spirit::classic::rule< ScannerT,
547 property_closure::context_t >
548 a_list;
549 boost::spirit::classic::rule< ScannerT,
550 attr_list_closure::context_t >
551 attr_list;
552 rule_t port_location;
553 rule_t port_angle;
554 rule_t port;
555 boost::spirit::classic::rule< ScannerT,
556 node_id_closure::context_t >
557 node_id;
558 boost::spirit::classic::rule< ScannerT,
559 property_closure::context_t >
560 graph_stmt;
561 rule_t attr_stmt;
562 boost::spirit::classic::rule< ScannerT,
563 data_stmt_closure::context_t >
564 data_stmt;
565 boost::spirit::classic::rule< ScannerT,
566 subgraph_closure::context_t >
567 subgraph;
568 rule_t edgeop;
569 rule_t edgeRHS;
570 rule_t stmt;
571 rule_t stmt_list;
572 rule_t the_grammar;
573
574 // The grammar uses edge_head to dynamically set the syntax for
575 // edges directed graphs: edge_head = '>', and so edgeop = "->"
576 // undirected graphs: edge_head = '-', and so edgeop = "--"
577 char edge_head;
578
579 //
580 // Support data structures
581 //
582
583 nodes_t nodes; // list of node names seen
584 edges_t edges; // list of edges seen
585 node_map_t
586 node_map; // remember the properties set for each node
587 edge_map_t
588 edge_map; // remember the properties set for each edge
589
590 subgraph_nodes_t subgraph_nodes; // per-subgraph lists of nodes
591 subgraph_edges_t subgraph_edges; // per-subgraph lists of edges
592
593 props_t default_node_props; // global default node properties
594 props_t default_edge_props; // global default edge properties
595 subgraph_props_t
596 subgraph_node_props; // per-subgraph default node properties
597 subgraph_props_t
598 subgraph_edge_props; // per-subgraph default edge properties
599 }; // struct definition
600 }; // struct dot_grammar
601
602 //
603 // dot_skipper - GraphViz whitespace and comment skipper
604 //
605 struct dot_skipper
606 : public boost::spirit::classic::grammar< dot_skipper >
607 {
608 dot_skipper() {}
609
610 template < typename ScannerT > struct definition
611 {
612 definition(dot_skipper const& /*self*/)
613 {
614 using namespace boost::spirit::classic;
615 using namespace phoenix;
616 // comment forms
617 skip = eol_p >> comment_p("#") | space_p | comment_p("//")
618 #if BOOST_WORKAROUND(BOOST_MSVC, <= 1400)
619 | confix_p(str_p("/*"), *anychar_p, str_p("*/"))
620 #else
621 | confix_p("/*", *anychar_p, "*/")
622 #endif
623 ;
624
625 #ifdef BOOST_SPIRIT_DEBUG
626 BOOST_SPIRIT_DEBUG_RULE(skip);
627 #endif
628 }
629
630 boost::spirit::classic::rule< ScannerT > skip;
631 boost::spirit::classic::rule< ScannerT > const& start() const
632 {
633 return skip;
634 }
635 }; // definition
636 }; // dot_skipper
637
638 } // namespace graph
639 } // namespace detail
640
641 template < typename MultiPassIterator, typename MutableGraph >
642 bool read_graphviz_spirit(MultiPassIterator begin, MultiPassIterator end,
643 MutableGraph& graph, dynamic_properties& dp,
644 std::string const& node_id = "node_id")
645 {
646 using namespace boost;
647 using namespace boost::spirit::classic;
648
649 typedef MultiPassIterator iterator_t;
650 typedef skip_parser_iteration_policy< boost::detail::graph::dot_skipper >
651 iter_policy_t;
652 typedef scanner_policies< iter_policy_t > scanner_policies_t;
653 typedef scanner< iterator_t, scanner_policies_t > scanner_t;
654
655 ::boost::detail::graph::mutate_graph_impl< MutableGraph > m_graph(
656 graph, dp, node_id);
657
658 ::boost::detail::graph::dot_grammar p(m_graph);
659 ::boost::detail::graph::dot_skipper skip_p;
660
661 iter_policy_t iter_policy(skip_p);
662 scanner_policies_t policies(iter_policy);
663
664 scanner_t scan(begin, end, policies);
665
666 bool ok = p.parse(scan);
667 m_graph.finish_building_graph();
668 return ok;
669 }
670
671 } // namespace boost
672
673 #endif // BOOST_READ_GRAPHVIZ_SPIRIT_HPP