#!/usr/bin/env python3
|
# Copyright 2016 Google Inc. All Rights Reserved.
|
#
|
# Licensed under the Apache License, Version 2.0 (the "License");
|
# you may not use this file except in compliance with the License.
|
# You may obtain a copy of the License at
|
#
|
# http://www.apache.org/licenses/LICENSE-2.0
|
#
|
# Unless required by applicable law or agreed to in writing, software
|
# distributed under the License is distributed on an "AS-IS" BASIS,
|
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
# See the License for the specific language governing permissions and
|
# limitations under the License.
|
|
from concurrent import futures
|
|
import itertools
|
import sys
|
import re
|
import pygraphviz as gv
|
import ply.lex as lex
|
import ply.yacc as yacc
|
from functools import lru_cache as memoize
|
|
diagnostic_header_pattern = re.compile('[^ ]+\.[^ ]+:[0-9]+:[0-9]+: ([^ ]*): (.*)')
|
in_file_included_from_pattern = re.compile('In file included from .*:')
|
in_instantiation_of_template_pattern = re.compile('in instantiation of (.*) (?:requested|required) here')
|
static_warning_marked_deprecated_here_pattern = re.compile('\'static_warning\' has been explicitly marked deprecated here')
|
|
class Diagnostic:
|
def __init__(self, kind, message):
|
self.kind = kind
|
self.message = message
|
self.template_instantiation_trace = []
|
|
tokens = (
|
'LPAREN',
|
'RPAREN',
|
'LBRACKET',
|
'RBRACKET',
|
'LBRACE',
|
'RBRACE',
|
'LESS_THAN',
|
'GREATER_THAN',
|
'DOUBLE_COLON',
|
'COMMA',
|
'IDENTIFIER',
|
'ASTERISK',
|
'AMPERSAND',
|
)
|
|
t_LPAREN = r'\('
|
t_RPAREN = r'\)'
|
t_LBRACKET = r'\['
|
t_RBRACKET = r'\]'
|
t_LBRACE = r'}'
|
t_RBRACE = r'{'
|
t_LESS_THAN = r'<'
|
t_GREATER_THAN = r'>'
|
t_DOUBLE_COLON = r'::'
|
t_COMMA = r','
|
t_ASTERISK = r'\*'
|
t_AMPERSAND = r'&'
|
# We conflate numbers as identifiers too, we don't care about the difference.
|
t_IDENTIFIER = r'[a-zA-Z0-9_]+'
|
|
t_ignore = ' \t'
|
|
def t_error(t):
|
raise Exception("Illegal character '%s' followed by %s" % (t.value[0], t.value[1:]))
|
|
class LayoutNeedsMultipleLinesException(Exception):
|
pass
|
|
class AstNode:
|
def __str__(self):
|
return ''.join(self)
|
|
class TerminalAstNode(AstNode):
|
def __init__(self, s):
|
self.s = s
|
self.is_multiline = (s == '\n')
|
# last_line_length is the string length if s is not a multiline string.
|
# For multiline strings ending in a newline, this is 0.
|
if self.is_multiline:
|
self.first_line_length = 0
|
self.last_line_length = 0
|
self.max_line_length = 0
|
else:
|
# This never happens ATM, so we don't handle it.
|
assert not '\n' in s
|
|
self.first_line_length = len(s)
|
self.last_line_length = len(s)
|
self.max_line_length = len(s)
|
|
def __iter__(self):
|
return iter((self.s,))
|
|
class NonTerminalAstNode(AstNode):
|
def __init__(self, children_ast_nodes):
|
self.children_ast_nodes = children_ast_nodes
|
first_line_length = 0
|
last_line_length = 0
|
is_multiline = False
|
max_line_length = 0
|
for node in children_ast_nodes:
|
if node.is_multiline:
|
last_line_length = node.last_line_length
|
max_line_length = max(max_line_length, last_line_length + node.first_line_length, node.max_line_length)
|
is_multiline = True
|
else:
|
last_line_length += node.last_line_length
|
max_line_length = max(max_line_length, last_line_length)
|
|
self.first_line_length = first_line_length
|
self.last_line_length = last_line_length
|
self.is_multiline = is_multiline
|
self.max_line_length = max_line_length
|
|
def __iter__(self):
|
return itertools.chain(*self.children_ast_nodes)
|
|
max_line_length = 80
|
# Size of an indent in spaces.
|
single_indent_length = 4
|
|
class TerminalNodeFactory():
|
def __init__(self, s):
|
self.s = s
|
|
def __call__(self, current_indent, current_line_length, inside_meta_type, last_token_was_type_wrapper, accept_single_line_only):
|
return TerminalAstNode(self.s)
|
|
# 'balanced_string' nodes evaluate to a function (or a callable object) taking these parameters:
|
# current_indent (integer): the indentation in the current line (spaces only)
|
# current_line_length (integer): the number of preceding characters in the current line (>=current_indent)
|
# inside_meta_type (boolean): whether we're inside a Type<...>
|
# last_token_was_type_wrapper (boolean): whether the immediately-preceding token was the identifier 'Type'
|
# and returning an AstNode
|
# 'comma_separated_balanced_string' nodes evaluate to a tuple of such functions
|
|
def p_comma_separated_balanced_string_empty(p):
|
'comma_separated_balanced_string : '
|
p[0] = tuple()
|
|
def p_comma_separated_balanced_string_not_empty(p):
|
'comma_separated_balanced_string : COMMA balanced_string comma_separated_balanced_string'
|
p[0] = (
|
p[2],
|
*(p[3])
|
)
|
|
def p_optional_balanced_string_empty(p):
|
'optional_balanced_string : '
|
p[0] = TerminalNodeFactory('')
|
|
def p_optional_balanced_string_not_empty(p):
|
'optional_balanced_string : balanced_string'
|
p[0] = p[1]
|
|
class BalancedStringTerminalNodeFactory():
|
def __init__(self, first_token, node_factory):
|
self.first_token = first_token
|
self.node_factory = node_factory
|
|
def __call__(self, current_indent, current_line_length, inside_meta_type, last_token_was_type_wrapper, accept_single_line_only):
|
terminal_node = TerminalAstNode(self.first_token)
|
non_terminal_node = self.node_factory(
|
current_indent,
|
current_line_length + len(self.first_token),
|
inside_meta_type,
|
self.first_token == 'Type',
|
accept_single_line_only)
|
if non_terminal_node is None:
|
return None
|
return NonTerminalAstNode((terminal_node, non_terminal_node))
|
|
def p_balanced_string_terminal(p):
|
'''balanced_string : DOUBLE_COLON balanced_string
|
| IDENTIFIER optional_balanced_string
|
| ASTERISK optional_balanced_string
|
| AMPERSAND optional_balanced_string
|
'''
|
first_token = p[1]
|
node_factory = p[2]
|
|
p[0] = BalancedStringTerminalNodeFactory(first_token, node_factory)
|
|
def create_composite_node_from_factories(node_factory_inside_meta_type_pairs, current_line_length, accept_single_line_only):
|
nodes = []
|
for node_factory, current_indent, inside_meta_type in node_factory_inside_meta_type_pairs:
|
node = node_factory(current_indent, current_line_length, inside_meta_type, False, accept_single_line_only)
|
if node is None:
|
return None
|
nodes.append(node)
|
if node.is_multiline:
|
if accept_single_line_only:
|
raise Exception('Unexpected multiline, due to factory: ' + node_factory)
|
# Note that due to the way we break lines, the last line will have the same indent as the first.
|
# So we don't need to update current_indent here.
|
current_line_length = node.last_line_length
|
else:
|
current_line_length += node.last_line_length
|
return NonTerminalAstNode(nodes)
|
|
def compute_layout(left_token, intermediate_node_factories, right_token, rhs_node_factory, current_indent, current_line_length, inside_meta_type, last_token_was_type_wrapper, accept_single_line_only):
|
# We lay out the result in one of two ways:
|
#
|
# $previousIndent $previousContent LPAREN x1, x2, x3 RPAREN balanced_string
|
#
|
# Or:
|
#
|
# $previousIndent $previousContent LPAREN
|
# $previousIndent $indent x1 ,
|
# $previousIndent $indent x2 ,
|
# $previousIndent $indent x3 RPAREN balanced_string
|
|
entering_meta_type = last_token_was_type_wrapper
|
|
# First, we try to use the first format if possible
|
node_factory_inside_meta_type_pairs = [
|
(TerminalNodeFactory(left_token), current_indent, inside_meta_type),
|
*((intermediate_node_factory, current_indent, (inside_meta_type or entering_meta_type))
|
for intermediate_node_factory in intermediate_node_factories),
|
(TerminalNodeFactory(right_token), current_indent, inside_meta_type),
|
(rhs_node_factory, current_indent, inside_meta_type),
|
]
|
node_with_single_line_layout = create_composite_node_from_factories(node_factory_inside_meta_type_pairs, current_line_length, True)
|
if node_with_single_line_layout is not None and node_with_single_line_layout.max_line_length <= max_line_length:
|
assert not node_with_single_line_layout.is_multiline
|
return node_with_single_line_layout
|
|
if accept_single_line_only:
|
return None
|
|
# The result exceeds the line length, let's switch to the second one.
|
node_factory_inside_meta_type_pairs = [
|
(TerminalNodeFactory(left_token),
|
current_indent,
|
inside_meta_type)
|
]
|
new_indent_length = current_indent + single_indent_length
|
comma_node_factory_inside_meta_type_pair = (TerminalNodeFactory(','), current_indent, inside_meta_type or entering_meta_type)
|
newline_node_factory_inside_meta_type_pair = (TerminalNodeFactory('\n'), current_indent, inside_meta_type or entering_meta_type)
|
indent_node_factory_inside_meta_type_pair = (TerminalNodeFactory(' ' * new_indent_length), current_indent, inside_meta_type or entering_meta_type)
|
for inner_node_factory in intermediate_node_factories:
|
node_factory_inside_meta_type_pairs.append(newline_node_factory_inside_meta_type_pair)
|
node_factory_inside_meta_type_pairs.append(indent_node_factory_inside_meta_type_pair)
|
node_factory_inside_meta_type_pairs.append((inner_node_factory, new_indent_length, inside_meta_type or entering_meta_type))
|
node_factory_inside_meta_type_pairs.append(comma_node_factory_inside_meta_type_pair)
|
node_factory_inside_meta_type_pairs.pop()
|
node_factory_inside_meta_type_pairs.append((TerminalNodeFactory(right_token), current_indent, inside_meta_type))
|
node_factory_inside_meta_type_pairs.append((rhs_node_factory, current_indent, inside_meta_type))
|
return create_composite_node_from_factories(node_factory_inside_meta_type_pairs, current_line_length, accept_single_line_only)
|
|
|
def p_balanced_string_with_balanced_token_no_comma_separated_elems(p):
|
'''balanced_string : LPAREN RPAREN optional_balanced_string
|
| LBRACKET RBRACKET optional_balanced_string
|
| LBRACE RBRACE optional_balanced_string
|
| LESS_THAN GREATER_THAN optional_balanced_string
|
'''
|
p_1 = p[1]
|
p_2 = p[2]
|
p_3 = p[3]
|
def result(current_indent, current_line_length, inside_meta_type, last_token_was_type_wrapper, accept_single_line_only):
|
return compute_layout(p_1, [], p_2, p_3, current_indent, current_line_length, inside_meta_type, last_token_was_type_wrapper, accept_single_line_only)
|
|
p[0] = result
|
|
def p_balanced_string_with_balanced_token_some_comma_separated_elems(p):
|
'''balanced_string : LPAREN balanced_string comma_separated_balanced_string RPAREN optional_balanced_string
|
| LBRACKET balanced_string comma_separated_balanced_string RBRACKET optional_balanced_string
|
| LBRACE balanced_string comma_separated_balanced_string RBRACE optional_balanced_string
|
| LESS_THAN balanced_string comma_separated_balanced_string GREATER_THAN optional_balanced_string
|
'''
|
p_1 = p[1]
|
p_2 = p[2]
|
p_3 = p[3]
|
p_4 = p[4]
|
p_5 = p[5]
|
def result(current_indent, current_line_length, inside_meta_type, last_token_was_type_wrapper, accept_single_line_only):
|
if not inside_meta_type:
|
if p_1 == '(' and p_4 == ')':
|
if len(p_3) == 0:
|
if isinstance(p_2, BalancedStringTerminalNodeFactory) and p_2.first_token == '*':
|
if isinstance(p_2.node_factory, TerminalNodeFactory) and p_2.node_factory.s == '':
|
# Special case: we're not inside a Type<...> and we've encountered a '(*)'.
|
# Discard it and just print the rhs.
|
return p_5(current_indent, current_line_length, inside_meta_type, False, accept_single_line_only)
|
|
return compute_layout(p_1, (p_2, *(p_3)), p_4, p_5, current_indent, current_line_length, inside_meta_type, last_token_was_type_wrapper, accept_single_line_only)
|
|
p[0] = result
|
|
def p_error(p):
|
raise Exception("Syntax error when parsing meta type: ", p[:])
|
|
lexer = lex.lex()
|
parser = yacc.yacc(start='balanced_string')
|
|
strings_to_remove = re.compile(r'template class |template type alias |function template specialization |member class |member function |default argument for |fruit::impl::meta::|fruit::impl::|fruit::')
|
|
def do_simplify_template_trace_element(element):
|
element, _ = re.subn(strings_to_remove, '', element)
|
element = element.strip()
|
if element[0] != '\'' or element[-1] != '\'':
|
raise Exception('Expected single quotes in: ' + element)
|
element = element[1:-1]
|
if element.startswith('DoEval<') and element[-1] == '>':
|
element = element[7:-1]
|
result = ''.join(parser.parse(element, lexer)(0, 0, False, False, False))
|
return result
|
|
@memoize(maxsize=1000)
|
def simplify_template_trace_element(element, executor):
|
return executor.submit(do_simplify_template_trace_element, element)
|
|
def to_dot_left_justified_string(s):
|
return '\\l'.join(s.splitlines() + [''])
|
|
def main():
|
diagnostics = []
|
|
with futures.ProcessPoolExecutor() as executor:
|
lines = sys.stdin.readlines()
|
for line_number, line in enumerate(lines):
|
# Remove the newline
|
line = line[:-1]
|
|
matches = in_file_included_from_pattern.search(line)
|
if matches:
|
continue
|
|
matches = diagnostic_header_pattern.search(line)
|
if matches:
|
diagnostic_kind, diagnostic_message = matches.groups()
|
if diagnostic_kind == 'error':
|
diagnostics.append(Diagnostic(diagnostic_kind, diagnostic_message))
|
print('Processing diagnostic. (%s / %s) ' % (line_number, len(lines)), file=sys.stderr)
|
elif diagnostic_kind == 'note':
|
matches = in_instantiation_of_template_pattern.search(diagnostic_message)
|
if matches:
|
if not diagnostics:
|
raise Exception('Found template instantiation note before any error diagnostic: %s' % diagnostic_message)
|
if 'in instantiation of template type alias' in line:
|
pass
|
else:
|
group = matches.groups()[0]
|
trace_element_future = simplify_template_trace_element(group, executor)
|
diagnostics[-1].template_instantiation_trace.append(trace_element_future)
|
continue
|
|
matches = static_warning_marked_deprecated_here_pattern.search(diagnostic_message)
|
if matches:
|
continue
|
|
raise Exception('Found unknown note: %s' % diagnostic_message)
|
|
call_graph = {}
|
graph = gv.AGraph(directed=True)
|
|
for diagnostic_index, diagnostic in enumerate(diagnostics):
|
if diagnostic_index % 10 == 0:
|
print('Constructing dep graph: iteration %s/%s' % (diagnostic_index, len(diagnostics)), file=sys.stderr)
|
|
template_instantiation_trace = [trace_element_future.result() for trace_element_future in diagnostic.template_instantiation_trace]
|
for called, caller in zip(template_instantiation_trace[1:], template_instantiation_trace[2:]):
|
if called in call_graph and call_graph[called] != caller:
|
# Avoid this edge, so that the resulting graph is a tree
|
continue
|
graph.add_edge(to_dot_left_justified_string(caller), to_dot_left_justified_string(called))
|
call_graph[called] = caller
|
|
print(graph)
|
|
if __name__ == '__main__':
|
main()
|
