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 funcparserlib.lexer import LexerError, Token, make_tokenizer43from funcparserlib.parser import (a, finished, forward_decl, many, maybe, skip,44 some)4546ENCODING = 'utf-8'4748Diagram = namedtuple('Diagram', 'id stmts')49Group = namedtuple('Group', 'id stmts')50Node = namedtuple('Node', 'id attrs')51Attr = namedtuple('Attr', 'name value')52Edge = namedtuple('Edge', 'from_nodes edge_type to_nodes attrs')53Extension = namedtuple('Extension', 'type name attrs')54Statements = namedtuple('Statements', 'stmts')555657class ParseException(Exception):58 pass596061def tokenize(string):62 """str -> Sequence(Token)"""63 # flake8: NOQA64 specs = [ # NOQA65 ('Comment', (r'/\*(.|[\r\n])*?\*/', MULTILINE)), # NOQA66 ('Comment', (r'(//|#).*',)), # NOQA67 ('NL', (r'[\r\n]+',)), # NOQA68 ('Space', (r'[ \t\r\n]+',)), # NOQA69 ('Name', ('[A-Za-z_0-9\u0080-\uffff]' + # NOQA70 '[A-Za-z_\\-.0-9\u0080-\uffff]*',)), # NOQA71 ('Op', (r'[{};,=\[\]]|(<->)|(<-)|(--)|(->)|(>-<)|(-<)|(>-)',)), # NOQA72 ('Number', (r'-?(\.[0-9]+)|([0-9]+(\.[0-9]*)?)',)), # NOQA73 ('String', (r'(?P<quote>(""")|(\'\'\')|"|\').*?(?<!\\)(?P=quote)', DOTALL)), # NOQA74 ]75 useless = ['Comment', 'NL', 'Space']76 t = make_tokenizer(specs)77 return [x for x in t(string) if x.type not in useless]787980def create_mapper(fn, default_value=None):81 if default_value is None:82 return lambda args: fn(*args)83 else:84 return lambda args: fn(*args) if args else default_value858687def flatten(seq):88 return sum(seq, [])899091def oneplus_to_list(first, more):92 return [first] + more939495def parse(seq):96 """Sequence(Token) -> object"""97 tokval = lambda x: x.value98 op = lambda s: a(Token('Op', s)) >> tokval99 op_ = lambda s: skip(op(s))100 _id = some(lambda t: t.type in ['Name', 'Number', 'String']) >> tokval101 keyword = lambda s: a(Token('Name', s)) >> tokval102103 def make_node_list(node_list, attrs):104 return Statements([Node(node, attrs) for node in node_list])105106 def make_edge(first, edge_type, second, followers, attrs):107 edges = [Edge(first, edge_type, second, attrs)]108109 from_node = second110 for edge_type, to_node in followers:111 edges.append(Edge(from_node, edge_type, to_node, attrs))112 from_node = to_node113114 return Statements(edges)115116 #117 # parts of syntax118 #119 node_list = (120 _id +121 many(op_(',') + _id)122 >> create_mapper(oneplus_to_list)123 )124 option_stmt = (125 _id +126 maybe(op_('=') + _id)127 >> create_mapper(Attr)128 )129 option_list = (130 maybe(op_('[') + option_stmt + many(op_(',') + option_stmt) + op_(']'))131 >> create_mapper(oneplus_to_list, default_value=[])132 )133134 # node (node list) statement::135 # A;136 # B [attr = value, attr = value];137 # C, D [attr = value, attr = value];138 #139 node_stmt = (140 node_list + option_list141 >> create_mapper(make_node_list)142 )143144 # edge statement::145 # A -> B;146 # A <- B;147 #148 edge_relation = (149 op('->') | op('--') | op('<-') | op('<->') |150 op('>-') | op('-<') | op('>-<')151 )152 edge_stmt = (153 node_list +154 edge_relation +155 node_list +156 many(edge_relation + node_list) +157 option_list158 >> create_mapper(make_edge)159 )160161 # attributes statement::162 # default_shape = box;163 # default_fontsize = 16;164 #165 attribute_stmt = (166 _id + op_('=') + _id167 >> create_mapper(Attr)168 )169170 # extension statement (class, plugin)::171 # class red [color = red];172 # plugin attributes [name = Name];173 #174 extension_stmt = (175 (keyword('class') | keyword('plugin')) +176 _id +177 option_list178 >> create_mapper(Extension)179 )180181 # group statement::182 # group {183 # A;184 # }185 #186 group_stmt = forward_decl()187 group_inline_stmt = (188 edge_stmt |189 group_stmt |190 attribute_stmt |191 node_stmt192 )193 group_inline_stmt_list = (194 many(group_inline_stmt + skip(maybe(op(';'))))195 )196 group_stmt.define(197 skip(keyword('group')) +198 maybe(_id) +199 op_('{') +200 group_inline_stmt_list +201 op_('}')202 >> create_mapper(Group)203 )204205 #206 # diagram statement::207 # blockdiag {208 # A;209 # }210 #211 diagram_id = (212 (keyword('diagram') | keyword('blockdiag')) +213 maybe(_id)214 >> list215 )216 diagram_inline_stmt = (217 extension_stmt |218 group_inline_stmt219 )220 diagram_inline_stmt_list = (221 many(diagram_inline_stmt + skip(maybe(op(';'))))222 )223 diagram = (224 maybe(diagram_id) +225 op_('{') +226 diagram_inline_stmt_list +227 op_('}')228 >> create_mapper(Diagram)229 )230 dotfile = diagram + skip(finished)231232 return dotfile.parse(seq)233234235def sort_tree(tree):236 def weight(node):237 if isinstance(node, (Attr, Extension)):238 return 1239 else:240 return 2241242 if hasattr(tree, 'stmts'):243 tree.stmts.sort(key=lambda x: weight(x))244 for stmt in tree.stmts:245 sort_tree(stmt)246247 return tree248249250def parse_string(string):251 try:252 tree = parse(tokenize(string))253 return sort_tree(tree)254 except LexerError as e:255 message = "Got unexpected token at line %d column %d" % e.place256 raise ParseException(message)257 except Exception as e:258 raise ParseException(str(e))259260261def parse_file(path):262 code = io.open(path, 'r', encoding='utf-8-sig').read()263 return parse_string(code)