-
Notifications
You must be signed in to change notification settings - Fork 0
/
bigo_calc.py
104 lines (81 loc) · 3.47 KB
/
bigo_calc.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
import argparse
import json
import os
import sympy
from ast_transformer.c.ast_generator import CASTGenerator
from ast_transformer.c.transform_visitor import CTransformVisitor
from ast_transformer.java.ast_generator import JavaASTGenerator
from ast_transformer.java.transform_visitor import JavaTransformVisitor
from ast_transformer.python.ast_generator import PyASTGenerator
from ast_transformer.python.transform_visitor import PyTransformVisitor
from bigo_ast.bigo_ast import FuncDeclNode
from bigo_calculator.bigo_calculator import BigOCalculator
from bigo_calculator.bigo_simplify import BigOSimplify
def main():
arg_parse = argparse.ArgumentParser(description='A static Big-O analysis tool base on Big-O AST.')
arg_parse.format_help()
arg_parse.add_argument('filename', type=str, help='target code filename')
arg_parse.add_argument('-lang', nargs='?', type=str,
help='this argument is optional if file extension is .c or .java')
# arg_parse.add_argument('-loop', action='store_false', help='calculate loop time complexity.')
arg_parse.add_argument('-no-simplify', action='store_true', help=' do not simplify time complexity.')
args = arg_parse.parse_args()
# check file exist
source_file_name = args.filename
if not os.path.isfile(source_file_name):
raise FileNotFoundError
json_str = time_calc(source_file_name, file_language = args.lang)
# print function Big-O
print(json_str)
return json_str
def time_calc(filename : str, file_language : None):
# check file exist
source_file_name = filename
if not os.path.isfile(source_file_name):
raise FileNotFoundError
# default get programming language by extension
language = os.path.splitext(source_file_name)[1][1:].lower()
if file_language:
language = file_language
# transform ast
if language == 'c':
origin_ast = CASTGenerator().generate(source_file_name)
bigo_ast = CTransformVisitor().transform(origin_ast)
elif language == 'java':
origin_ast = JavaASTGenerator().generate(source_file_name)
bigo_ast = JavaTransformVisitor().transform(origin_ast)
elif language == 'py':
origin_ast = PyASTGenerator().generate(source_file_name)
bigo_ast = PyTransformVisitor().transform(origin_ast)
else:
raise Exception("Language does not support : " + language)
# evaluate big o
BigOCalculator(bigo_ast).calc()
new_bigo_ast = bigo_ast
new_bigo_ast = BigOSimplify(bigo_ast).simplify()
func_bigo_dict = {}
complexity = new_bigo_ast.time_complexity
if type(complexity) is sympy.Order:
complexity = str(complexity)
else:
complexity = 'O(' + str(complexity) + ')'
func_bigo_dict.update({'compilation node': complexity})
for func in new_bigo_ast.children:
if type(func) != FuncDeclNode:
continue
complexity = func.time_complexity
if func.recursive:
complexity = 'is a recursive function'
elif not complexity:
raise ArithmeticError('complexity can not recognize.')
elif type(complexity) is sympy.Order:
complexity = str(complexity)
else:
complexity = 'O(' + str(complexity) + ')'
func_bigo_dict.update({func.name: complexity})
json_str = json.dumps(func_bigo_dict, indent=4)
# print function Big-O
return json_str
if __name__ == '__main__':
main()
# time_calc('examples/colab-py/md1.py')