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')47Lane = namedtuple('Lane', 'id stmts')48Node = namedtuple('Node', 'id attrs')49Attr = namedtuple('Attr', 'name value')50Edge = namedtuple('Edge', 'from_nodes edge_type to_nodes attrs')51Extension = namedtuple('Extension', 'type name attrs')52Statements = namedtuple('Statements', 'stmts')535455class ParseException(Exception):56 pass575859def tokenize(string):60 """str -> Sequence(Token)"""61 # flake8: NOQA62 specs = [ # NOQA63 ('Comment', (r'/\*(.|[\r\n])*?\*/', MULTILINE)), # NOQA64 ('Comment', (r'(//|#).*',)), # NOQA65 ('NL', (r'[\r\n]+',)), # NOQA66 ('Space', (r'[ \t\r\n]+',)), # NOQA67 ('Name', ('[A-Za-z_0-9\u0080-\uffff]' + # NOQA68 '[A-Za-z_\\-.0-9\u0080-\uffff]*',)), # NOQA69 ('Op', (r'[{};,=\[\]]|(<->)|(<-)|(--)|(->)',)), # NOQA70 ('Number', (r'-?(\.[0-9]+)|([0-9]+(\.[0-9]*)?)',)), # NOQA71 ('String', (r'(?P<quote>(""")|(\'\'\')|"|\').*?(?<!\\)(?P=quote)', DOTALL)), # NOQA72 ]73 useless = ['Comment', 'NL', 'Space']74 t = make_tokenizer(specs)75 return [x for x in t(string) if x.type not in useless]767778def parse(seq):79 """Sequence(Token) -> object"""80 tokval = lambda x: x.value81 op = lambda s: a(Token('Op', s)) >> tokval82 op_ = lambda s: skip(op(s))83 _id = some(lambda t: t.type in ['Name', 'Number', 'String']) >> tokval84 keyword = lambda s: a(Token('Name', s)) >> tokval8586 def make_node_list(node_list, attrs):87 return Statements([Node(node, attrs) for node in node_list])8889 def make_edge(first, edge_type, second, followers, attrs):90 edges = [Edge(first, edge_type, second, attrs)]9192 from_node = second93 for edge_type, to_node in followers:94 edges.append(Edge(from_node, edge_type, to_node, attrs))95 from_node = to_node9697 return Statements(edges)9899 #100 # parts of syntax101 #102 node_list = (103 _id +104 many(op_(',') + _id)105 >> create_mapper(oneplus_to_list)106 )107 option_stmt = (108 _id +109 maybe(op_('=') + _id)110 >> create_mapper(Attr)111 )112 option_list = (113 maybe(op_('[') + option_stmt + many(op_(',') + option_stmt) + op_(']'))114 >> create_mapper(oneplus_to_list, default_value=[])115 )116117 # node (node list) statement::118 # A;119 # B [attr = value, attr = value];120 # C, D [attr = value, attr = value];121 #122 node_stmt = (123 node_list + option_list124 >> create_mapper(make_node_list)125 )126127 # edge statement::128 # A -> B;129 # A <- B;130 #131 edge_relation = (132 op('->') | op('--') | op('<-') | op('<->')133 )134 edge_stmt = (135 node_list +136 edge_relation +137 node_list +138 many(edge_relation + node_list) +139 option_list140 >> create_mapper(make_edge)141 )142143 # attributes statement::144 # default_shape = box;145 # default_fontsize = 16;146 #147 attribute_stmt = (148 _id + op_('=') + _id149 >> create_mapper(Attr)150 )151152 # extension statement (class, plugin)::153 # class red [color = red];154 # plugin attributes [name = Name];155 #156 extension_stmt = (157 (keyword('class') | keyword('plugin')) +158 _id +159 option_list160 >> create_mapper(Extension)161 )162163 # lane statement::164 # lane A [color = red];165 # lane {166 # A;167 # }168 #169 lane_declare_stmt = (170 skip(keyword('lane')) +171 _id +172 option_list173 >> create_mapper(Lane)174 )175 lane_inline_stmt = (176 edge_stmt |177 attribute_stmt |178 node_stmt179 )180 lane_inline_stmt_list = (181 many(lane_inline_stmt + skip(maybe(op(';'))))182 )183 lane_stmt = (184 skip(keyword('lane')) +185 maybe(_id) +186 op_('{') +187 lane_inline_stmt_list +188 op_('}')189 >> create_mapper(Lane)190 )191192 #193 # diagram statement::194 # actdiag {195 # A;196 # }197 #198 diagram_id = (199 (keyword('diagram') | keyword('actdiag')) +200 maybe(_id)201 >> list202 )203 diagram_inline_stmt = (204 extension_stmt |205 edge_stmt |206 lane_stmt |207 lane_declare_stmt |208 attribute_stmt |209 node_stmt210 )211 diagram_inline_stmt_list = (212 many(diagram_inline_stmt + skip(maybe(op(';'))))213 )214 diagram = (215 maybe(diagram_id) +216 op_('{') +217 diagram_inline_stmt_list +218 op_('}')219 >> create_mapper(Diagram)220 )221 dotfile = diagram + skip(finished)222223 return dotfile.parse(seq)224225226def sort_tree(tree):227 def weight(node):228 if isinstance(node, (Attr, Extension)):229 return 1230 else:231 return 2232233 if hasattr(tree, 'stmts'):234 tree.stmts.sort(key=lambda x: weight(x))235 for stmt in tree.stmts:236 sort_tree(stmt)237238 return tree239240241def parse_string(string):242 try:243 tree = parse(tokenize(string))244 return sort_tree(tree)245 except LexerError as e:246 message = "Got unexpected token at line %d column %d" % e.place247 raise ParseException(message)248 except Exception as e:249 raise ParseException(str(e))250251252def parse_file(path):253 input = io.open(path, 'r', encoding='utf-8-sig').read()254 return parse_string(input)