1# -*- coding: utf-8 -*-23# Copyright (c) 2008/2009 Andrey Vlasovskikh4#5# Permission is hereby granted, free of charge, to any person obtaining6# a copy of this software and associated documentation files (the7# "Software"), to deal in the Software without restriction, including8# without limitation the rights to use, copy, modify, merge, publish,9# distribute, sublicense, and/or sell copies of the Software, and to10# permit persons to whom the Software is furnished to do so, subject to11# the following conditions:12#13# The above copyright notice and this permission notice shall be included14# in all copies or substantial portions of the Software.15#16# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,17# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF18# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.19# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY20# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,21# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE22# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.2324r'''A DOT language parser using funcparserlib.2526The parser is based on [the DOT grammar][1]. It is pretty complete with a few27not supported things:2829* Ports and compass points30* XML identifiers3132At the moment, the parser builds only a parse tree, not an abstract syntax tree33(AST) or an API for dealing with DOT.3435 [1]: http://www.graphviz.org/doc/info/lang.html36'''3738import io39from collections import namedtuple40from re import DOTALL, MULTILINE4142from blockdiag.parser import create_mapper, oneplus_to_list43from funcparserlib.lexer import LexerError, Token, make_tokenizer44from funcparserlib.parser import a, finished, many, maybe, skip, some4546Diagram = namedtuple('Diagram', 'id stmts')47Network = namedtuple('Network', 'id stmts')48Group = namedtuple('Group', 'id stmts')49Node = namedtuple('Node', 'id attrs')50Attr = namedtuple('Attr', 'name value')51Edge = namedtuple('Edge', 'from_node edge_type to_node attrs')52Peer = namedtuple('Peer', 'edges')53Route = namedtuple('Route', 'edges')54Extension = namedtuple('Extension', 'type name attrs')55Statements = namedtuple('Statements', 'stmts')565758class ParseException(Exception):59 pass606162def tokenize(string):63 """str -> Sequence(Token)"""64 # flake8: NOQA65 specs = [ # NOQA66 ('Comment', (r'/\*(.|[\r\n])*?\*/', MULTILINE)), # NOQA67 ('Comment', (r'(//|#).*',)), # NOQA68 ('NL', (r'[\r\n]+',)), # NOQA69 ('Space', (r'[ \t\r\n]+',)), # NOQA70 ('Name', ('[A-Za-z_\u0080-\uffff]' + # NOQA71 '[A-Za-z_\\-.0-9\u0080-\uffff]*',)), # NOQA72 ('Op', (r'([{};,=\[\]]|--|->)',)), # NOQA73 ('IPAddr', (r'([0-9]+(\.[0-9]+){3}|[:0-9a-fA-F]+)',)), # NOQA74 ('Number', (r'-?(\.[0-9]+)|([0-9]+(\.[0-9]*)?)',)), # NOQA75 ('String', (r'(?P<quote>(""")|(\'\'\')|"|\').*?(?<!\\)(?P=quote)', DOTALL)), # NOQA76 ]77 useless = ['Comment', 'NL', 'Space']78 t = make_tokenizer(specs)79 return [x for x in t(string) if x.type not in useless]808182def parse(seq):83 """Sequence(Token) -> object"""84 id_tokens = ['Name', 'IPAddr', 'Number', 'String']8586 tokval = lambda x: x.value87 op = lambda s: a(Token('Op', s)) >> tokval88 op_ = lambda s: skip(op(s))89 _id = some(lambda t: t.type in id_tokens) >> tokval90 keyword = lambda s: a(Token('Name', s)) >> tokval9192 def make_peer(first, edge_type, second, followers, attrs):93 edges = [Edge(first, edge_type, second, attrs)]9495 from_node = second96 for edge_type, to_node in followers:97 edges.append(Edge(from_node, edge_type, to_node, attrs))98 from_node = to_node99100 return Peer(edges)101102 def make_route(first, edge_type, second, followers, attrs):103 edges = [Edge(first, edge_type, second, attrs)]104105 from_node = second106 for edge_type, to_node in followers:107 edges.append(Edge(from_node, edge_type, to_node, attrs))108 from_node = to_node109110 return Route(edges)111112 #113 # parts of syntax114 #115 node_list = (116 _id +117 many(op_(',') + _id)118 >> create_mapper(oneplus_to_list)119 )120 option_stmt = (121 _id +122 maybe(op_('=') + _id)123 >> create_mapper(Attr)124 )125 option_list = (126 maybe(op_('[') + option_stmt + many(op_(',') + option_stmt) + op_(']'))127 >> create_mapper(oneplus_to_list, default_value=[])128 )129130 # node statement::131 # A;132 # B [attr = value, attr = value];133 #134 node_stmt = (135 _id + option_list136 >> create_mapper(Node)137 )138139 # peer network statement::140 # A -- B;141 #142 edge_stmt = (143 _id +144 op('--') +145 _id +146 many(op('--') + _id) +147 option_list148 >> create_mapper(make_peer)149 )150151 # attributes statement::152 # default_shape = box;153 # default_fontsize = 16;154 #155 attribute_stmt = (156 _id + op_('=') + _id157 >> create_mapper(Attr)158 )159160 # extension statement (class, plugin)::161 # class red [color = red];162 # plugin attributes [name = Name];163 #164 extension_stmt = (165 (keyword('class') | keyword('plugin')) +166 _id +167 option_list168 >> create_mapper(Extension)169 )170171 # group statement::172 # group {173 # A;174 # }175 #176 group_inline_stmt = (177 attribute_stmt |178 node_stmt179 )180 group_inline_stmt_list = (181 many(group_inline_stmt + skip(maybe(op(';'))))182 )183 group_stmt = (184 skip(keyword('group')) +185 maybe(_id) +186 op_('{') +187 group_inline_stmt_list +188 op_('}')189 >> create_mapper(Group)190 )191192 # network statement::193 # network {194 # A;195 # }196 #197 network_inline_stmt = (198 attribute_stmt |199 group_stmt |200 node_stmt201 )202 network_inline_stmt_list = (203 many(network_inline_stmt + skip(maybe(op(';'))))204 )205 network_stmt = (206 skip(keyword('network')) +207 maybe(_id) +208 op_('{') +209 network_inline_stmt_list +210 op_('}')211 >> create_mapper(Network)212 )213214 # route statement::215 # route {216 # A -> B -> C;217 # }218 #219 route_inline_stmt = (220 _id +221 op_('->') +222 _id +223 many(op_('->') + _id) +224 option_list225 >> create_mapper(make_route)226 )227 route_stmt = (228 skip(keyword('route')) +229 maybe(_id) +230 op_('{') +231 network_inline_stmt_list +232 op_('}')233 >> create_mapper(Network)234 )235236 #237 # diagram statement::238 # nwdiag {239 # A;240 # }241 #242 diagram_id = (243 (keyword('diagram') | keyword('nwdiag')) +244 maybe(_id)245 >> list246 )247 diagram_inline_stmt = (248 extension_stmt |249 network_stmt |250 group_stmt |251 attribute_stmt |252 route_stmt |253 edge_stmt |254 node_stmt255 )256 diagram_inline_stmt_list = (257 many(diagram_inline_stmt + skip(maybe(op(';'))))258 )259 diagram = (260 maybe(diagram_id) +261 op_('{') +262 diagram_inline_stmt_list +263 op_('}')264 >> create_mapper(Diagram)265 )266 dotfile = diagram + skip(finished)267268 return dotfile.parse(seq)269270271def sort_tree(tree):272 def weight(node):273 if isinstance(node, (Attr, Extension)):274 return 1275 else:276 return 2277278 if hasattr(tree, 'stmts'):279 tree.stmts.sort(key=lambda x: weight(x))280 for stmt in tree.stmts:281 sort_tree(stmt)282283 return tree284285286def parse_string(string):287 try:288 tree = parse(tokenize(string))289 return sort_tree(tree)290 except LexerError as e:291 message = "Got unexpected token at line %d column %d" % e.place292 raise ParseException(message)293 except Exception as e:294 raise ParseException(str(e))295296297def parse_file(path):298 code = io.open(path, 'r', encoding='utf-8-sig').read()299 return parse_string(code)