semantics_visitor.py 23 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628
  1. import hutnparser as hp
  2. import symbol_table as st
  3. import sys
  4. import types_mv
  5. from declare_functions_visitor import DeclareFunctionsVisitor
  6. from visitor import Visitor
  7. class SemanticsVisitor(Visitor):
  8. def __init__(self):
  9. self.symbol_table = st.SymbolTable()
  10. # there is only one input file, list is for sharing it among visitors
  11. self.inputfiles = []
  12. # inherited attribute, set in funcdecl and used in return,
  13. # to ensure that (returned type == declared type)
  14. self.current_funcdecl = None
  15. self.declare_functions_visitor =\
  16. DeclareFunctionsVisitor(self.symbol_table, self.inputfiles)
  17. @staticmethod
  18. def incompatible_types(l_type, r_type):
  19. if type(l_type) != type(r_type):
  20. if types_mv.Void in (type(l_type), type(r_type)):
  21. return True
  22. if types_mv.Element in (type(l_type), type(r_type)):
  23. return False
  24. if l_type.isNotNumber() or r_type.isNotNumber():
  25. return True
  26. return False
  27. def do_check_binary_ops_arithmetic(self, l, r):
  28. l_type, r_type = self.get_type(l), self.get_type(r)
  29. if SemanticsVisitor.incompatible_types(l_type, r_type):
  30. raise RuntimeError(
  31. "{}:{}:{}: error: invalid operands to binary operator "
  32. "(have {} and {})".format(self.inputfiles[0],
  33. l.startpos['line'],
  34. l.startpos['column'],
  35. str(l_type),
  36. str(r_type)))
  37. def check_binary_ops_arithmetic(self, tree):
  38. l, r = tree.get_tail()[0], tree.get_tail()[2]
  39. self.do_check_binary_ops_arithmetic(l, r)
  40. def generalize_binary_ops_arithmetic(self, tree):
  41. l, r = tree.get_tail()[0], tree.get_tail()[2]
  42. l_type, r_type = self.get_type(l), self.get_type(r)
  43. return types_mv.generalize_arithmetic(l_type, r_type)
  44. def check_unary_ops_arithmetic(self, tree, operator_name):
  45. l = tree.get_tail()[1]
  46. l_type = self.get_type(l)
  47. if l_type.isNotNumber():
  48. raise RuntimeError(
  49. "{}:{}:{}: error: wrong type argument to unary {} "
  50. "({})".format(self.inputfiles[0],
  51. l.startpos['line'],
  52. l.startpos['column'],
  53. operator_name,
  54. str(l_type)))
  55. def promote_unary_ops_arithmetic(self, tree):
  56. l = tree.get_tail()[1]
  57. l_type = self.get_type(l)
  58. try:
  59. return types_mv.promote_arithmetic(l_type)
  60. except RuntimeError:
  61. raise RuntimeError(
  62. "Pathological situation in promote_unary_ops_arithmetic: "
  63. "check_unary_ops_arithmetic has not been executed")
  64. # if r_type is provided, r is not used
  65. def do_check_assignment(self, l, r, r_type = None):
  66. if r_type is not None:
  67. l_type = self.get_type(l)
  68. else:
  69. l_type, r_type = self.get_type(l), self.get_type(r)
  70. if SemanticsVisitor.incompatible_types(l_type, r_type):
  71. raise RuntimeError("{}:{}:{}: error: cannot assign a value of "
  72. "type '{}' to a variable of type '{}'"
  73. .format(self.inputfiles[0],
  74. l.startpos['line'],
  75. l.startpos['column'],
  76. str(r_type),
  77. str(l_type)))
  78. def check_assignment(self, tree):
  79. l, r = tree.get_tail()[0], tree.get_tail()[2]
  80. self.do_check_assignment(l, r)
  81. def check_return(self, tree):
  82. l = self.current_funcdecl
  83. if len(tree.get_tail()) > 1:
  84. r = tree.get_tail()[1]
  85. r_type = None
  86. else:
  87. r = None
  88. r_type = types_mv.Void()
  89. if l:
  90. self.do_check_assignment(l, r, r_type)
  91. else:
  92. raise RuntimeError(
  93. "{}:{}:{}: error: 'return' is used outside of a function"
  94. .format(self.inputfiles[0],
  95. tree.startpos['line'],
  96. tree.startpos['column']))
  97. def check_predicate(self, tree):
  98. if isinstance(self.get_type(tree), types_mv.Element):
  99. return
  100. if self.get_type(tree).isNotNumber():
  101. raise RuntimeError(
  102. "{}:{}:{}: error: predicates of type '{}' are not allowed"
  103. .format(self.inputfiles[0],
  104. tree.startpos['line'],
  105. tree.startpos['column'],
  106. self.get_type(tree)))
  107. def replace_child_binary_op_with_call(self, tree, i=0):
  108. child = tree.get_tail()[i]
  109. if len(child.get_tail()) > 1:
  110. l, op, r = child.get_tail()
  111. l_type, r_type = self.get_type(l), self.get_type(r)
  112. if type(l_type) != type(r_type):
  113. print("Error: " + str(l_type) + " <-> " + str(r_type))
  114. raise RuntimeError(
  115. "{}:{}:{}: error: children were not casted".format(
  116. self.inputfiles[0],
  117. tree.startpos['line'],
  118. tree.startpos['column']
  119. ))
  120. call_name = SemanticsVisitor.call_name_binary(l_type, op)
  121. call_tree = SemanticsVisitor.func_call(call_name, [l, r])
  122. try:
  123. self.visit(call_tree)
  124. except RuntimeError:
  125. call_signature = "{0} function {1}({2}, {2})".format(
  126. str(types_mv.Boolean()), call_name, l_type)
  127. raise RuntimeError(
  128. "{}:{}:{}: error: cannot perform {}: function '{}' is "
  129. "not found".format(
  130. self.inputfiles[0],
  131. tree.startpos['line'],
  132. tree.startpos['column'],
  133. child.head,
  134. call_signature))
  135. tree.replace_child(child, call_tree)
  136. self.set_type(tree, self.get_type(tree.get_tail()[i]))
  137. def replace_child_unary_op_with_call(self, tree):
  138. child = tree.get_tail()[0]
  139. if child.head == "keep_sign":
  140. tree.replace_child(child, child.get_tail()[1])
  141. else:
  142. op, l = child.get_tail()
  143. l_type = self.get_type(l)
  144. call_name = SemanticsVisitor.call_name_unary(l_type, op)
  145. call_tree = SemanticsVisitor.func_call(call_name, [l])
  146. try:
  147. self.visit(call_tree)
  148. except RuntimeError:
  149. call_signature = "{0} function {1}({2})".format(
  150. str(types_mv.Boolean()), call_name, l_type)
  151. raise RuntimeError(
  152. "{}:{}:{}: error: cannot perform {}: function '{}' is "
  153. "not found".format(
  154. self.inputfiles[0],
  155. tree.startpos['line'],
  156. tree.startpos['column'],
  157. child.head,
  158. call_signature))
  159. tree.replace_child(child, call_tree)
  160. self.set_type(tree, self.get_type(tree.get_tail()[0]))
  161. def cast_binary_ops_arithmetic(self, tree):
  162. l, op, r = tree.get_tail()
  163. l_type, r_type = self.get_type(l), self.get_type(r)
  164. if type(l_type) != type(r_type): # if two different numeric types
  165. g_type = types_mv.generalize_arithmetic(l_type, r_type)
  166. self.perform_implicit_cast(tree, l, l_type, g_type)
  167. self.perform_implicit_cast(tree, r, r_type, g_type)
  168. def cast_binary_ops_logical(self, tree):
  169. l, op, r = tree.get_tail()
  170. l_type, r_type = self.get_type(l), self.get_type(r)
  171. self.perform_implicit_cast(tree, l, l_type, types_mv.Boolean())
  172. self.perform_implicit_cast(tree, r, r_type, types_mv.Boolean())
  173. def cast_unary_ops_arithmetic(self, tree):
  174. l = tree.get_tail()[1]
  175. l_type = self.get_type(l)
  176. p_type = self.promote_unary_ops_arithmetic(tree)
  177. self.perform_implicit_cast(tree, l, l_type, p_type)
  178. @staticmethod
  179. def func_call(name, params):
  180. zero = {'line': 0, 'column': 0}
  181. tree = hp.Tree(
  182. "func_call",
  183. [
  184. hp.Tree("rvalue",
  185. [
  186. hp.Tree("ID", [name], zero, zero)
  187. ],
  188. zero, zero),
  189. # Tokens have no impact on visit_func_call. So leave them out.
  190. # hp.Tree("LPAREN", ["("], zero, zero),
  191. # hp.Tree("COMMA", [","], zero, zero),
  192. # hp.Tree("RPAREN", [")"], zero, zero),
  193. ],
  194. zero, zero)
  195. params = [hp.Tree("expression", [p], zero, zero) for p in params]
  196. tree.tail.extend(params)
  197. return hp.Tree("expression", [tree], zero, zero)
  198. @staticmethod
  199. def cast_name(from_type, to_type):
  200. from_t = str(from_type)[0].lower()
  201. to_t = str(to_type)[0].lower()
  202. cast_name = "cast_{}2{}".format(from_t, to_t)
  203. return cast_name
  204. def raise_implicit_cast_error(self, from_type, to_type, tree):
  205. cast_name = SemanticsVisitor.cast_name(from_type, to_type)
  206. cast_signature = "{} function {}({})".format(
  207. str(to_type), cast_name, str(from_type))
  208. raise RuntimeError(
  209. "{}:{}:{}: error: cannot perform implicit cast from '{}'"
  210. " to '{}': function '{}' is not found".format(
  211. self.inputfiles[0],
  212. tree.startpos['line'],
  213. tree.startpos['column'],
  214. str(to_type), str(from_type),
  215. cast_signature))
  216. def perform_implicit_cast(self, tree, child, from_type, to_type):
  217. if types_mv.Element in (type(from_type), type(to_type)):
  218. return
  219. if type(from_type) == type(to_type):
  220. return
  221. cast_name = SemanticsVisitor.cast_name(from_type, to_type)
  222. cast_tree = \
  223. SemanticsVisitor.func_call(cast_name, [child])
  224. try:
  225. self.visit(cast_tree)
  226. except RuntimeError:
  227. self.raise_implicit_cast_error(from_type, to_type, child)
  228. tree.replace_child(child, cast_tree)
  229. types = {
  230. "Integer": "integer",
  231. "Float": "float",
  232. "Boolean": "bool",
  233. "String": "string",
  234. "Action": "action",
  235. "Element": "element",
  236. "Type": "type"
  237. }
  238. binary_ops = {
  239. "OR": "or",
  240. "AND": "and",
  241. "EQ": "eq",
  242. "NEQ": "neq",
  243. "LT": "lt",
  244. "GT": "gt",
  245. "LE": "lte",
  246. "GE": "gte",
  247. "PLUS": "addition",
  248. "MINUS": "subtraction",
  249. "STAR": "multiplication",
  250. "SLASH": "division"
  251. }
  252. unary_ops = {
  253. "NOT": "not",
  254. "MINUS": "neg"
  255. }
  256. @staticmethod
  257. def call_name_binary(operand_type, operator):
  258. # String joins should also be possible
  259. if str(operand_type) == "String":
  260. if operator.head == "PLUS":
  261. return "string_join"
  262. call_name = "{}_{}".format(SemanticsVisitor.types[str(operand_type)],
  263. SemanticsVisitor.binary_ops[operator.head])
  264. return call_name
  265. @staticmethod
  266. def call_name_unary(operand_type, operator):
  267. call_name = "{}_{}".format(SemanticsVisitor.types[str(operand_type)],
  268. SemanticsVisitor.unary_ops[operator.head])
  269. return call_name
  270. def dump(self):
  271. return self.tree.get_text(with_implicit=True)
  272. # return "No code generation here"
  273. # a visit_* method for each non-terminal in the grammar
  274. def visit_start(self, tree):
  275. self.symbol_table.open_scope()
  276. self.inputfiles.append(tree.inputfile)
  277. for child in tree.get_tail():
  278. self.inputfiles[0] = child.inputfile
  279. self.declare_functions_visitor.visit(child)
  280. for child in tree.get_tail():
  281. self.inputfiles[0] = child.inputfile
  282. self.visit(child)
  283. self.inputfiles.pop()
  284. self.symbol_table.close_scope()
  285. self.tree = tree
  286. def visit_statement(self, tree):
  287. self.visit_children(tree)
  288. def visit_definition(self, tree):
  289. self.visit_vardecl(tree)
  290. def visit_vardecl(self, tree):
  291. type_spec = tree.get_child("type_specifier")
  292. var_id = tree.get_child("ID")
  293. var_type = types_mv.string_to_type(type_spec.get_text())
  294. var_name = var_id.get_text()
  295. symbol = st.Symbol(var_name, var_type,
  296. is_global=self.current_funcdecl is None)
  297. try:
  298. self.symbol_table.add(symbol)
  299. except Exception:
  300. raise RuntimeError(
  301. "{}:{}:{}: error: redeclaration of '{}'".format(
  302. self.inputfiles[0], tree.startpos['line'],
  303. tree.startpos['column'], var_name))
  304. self.set_symbol(tree, symbol)
  305. def visit_assignment(self, tree):
  306. self.visit_children(tree)
  307. self.check_assignment(tree)
  308. def visit_expression(self, tree):
  309. self.visit_children(tree)
  310. self.set_type(tree, self.get_type(tree.get_tail()[0]))
  311. def visit_binary_operation(self, tree):
  312. self.visit_children(tree)
  313. self.replace_child_binary_op_with_call(tree)
  314. def visit_disjunction(self, tree):
  315. self.visit_children(tree)
  316. if len(tree.get_tail()) == 1:
  317. self.replace_child_binary_op_with_call(tree)
  318. else:
  319. self.replace_child_binary_op_with_call(tree, 2)
  320. self.cast_binary_ops_logical(tree)
  321. self.set_type(tree, types_mv.Boolean())
  322. def visit_conjunction(self, tree):
  323. self.visit_children(tree)
  324. if len(tree.get_tail()) == 1:
  325. self.replace_child_binary_op_with_call(tree)
  326. else:
  327. self.replace_child_binary_op_with_call(tree, 2)
  328. self.cast_binary_ops_logical(tree)
  329. self.set_type(tree, types_mv.Boolean())
  330. def visit_comparison(self, tree):
  331. self.visit_children(tree)
  332. if len(tree.get_tail()) == 1:
  333. self.replace_child_binary_op_with_call(tree)
  334. else:
  335. self.replace_child_binary_op_with_call(tree, 2)
  336. self.check_binary_ops_arithmetic(tree)
  337. self.cast_binary_ops_arithmetic(tree)
  338. self.set_type(tree, types_mv.Boolean())
  339. def visit_relation(self, tree):
  340. self.visit_children(tree)
  341. if len(tree.get_tail()) == 1:
  342. self.replace_child_binary_op_with_call(tree)
  343. else:
  344. self.replace_child_binary_op_with_call(tree, 2)
  345. self.check_binary_ops_arithmetic(tree)
  346. self.cast_binary_ops_arithmetic(tree)
  347. self.set_type(tree, types_mv.Boolean())
  348. def visit_sum(self, tree):
  349. self.visit_children(tree)
  350. if len(tree.get_tail()) == 1:
  351. self.replace_child_binary_op_with_call(tree)
  352. else:
  353. self.replace_child_binary_op_with_call(tree, 2)
  354. self.check_binary_ops_arithmetic(tree)
  355. self.cast_binary_ops_arithmetic(tree)
  356. # after the cast both parameters have the same (generalized) type:
  357. self.set_type(tree, self.get_type(tree.get_tail()[0]))
  358. def visit_term(self, tree):
  359. self.visit_children(tree)
  360. if len(tree.get_tail()) == 1:
  361. self.set_type(tree, self.get_type(tree.get_tail()[0]))
  362. else:
  363. self.check_binary_ops_arithmetic(tree)
  364. self.cast_binary_ops_arithmetic(tree)
  365. # after the cast both parameters have the same (generalized) type:
  366. self.set_type(tree, self.get_type(tree.get_tail()[0]))
  367. def visit_factor(self, tree):
  368. self.visit_children(tree)
  369. if tree.get_child("primary") is not None:
  370. self.set_type(tree, self.get_type(tree.get_tail()[0]))
  371. else:
  372. self.replace_child_unary_op_with_call(tree)
  373. def visit_logical_not(self, tree):
  374. self.visit_children(tree)
  375. l = tree.get_tail()[1]
  376. l_type = self.get_type(l)
  377. self.perform_implicit_cast(tree, l, l_type, types_mv.Boolean())
  378. self.set_type(tree, self.get_type(tree.get_tail()[1]))
  379. def visit_invert_sign(self, tree):
  380. self.visit_children(tree)
  381. self.check_unary_ops_arithmetic(tree, "minus")
  382. self.cast_unary_ops_arithmetic(tree)
  383. self.set_type(tree, self.get_type(tree.get_tail()[1]))
  384. def visit_keep_sign(self, tree):
  385. self.visit_children(tree)
  386. self.check_unary_ops_arithmetic(tree, "plus")
  387. self.cast_unary_ops_arithmetic(tree)
  388. self.set_type(tree, self.get_type(tree.get_tail()[1]))
  389. def visit_primary(self, tree):
  390. self.visit_children(tree)
  391. self.set_type(tree, self.get_type(tree.get_tail()[0]))
  392. def visit_parenthesized(self, tree):
  393. self.visit_children(tree)
  394. self.set_type(tree, self.get_type(tree.get_tail()[1]))
  395. def visit_atomvalue(self, tree):
  396. self.visit_children(tree)
  397. self.set_type(tree, self.get_type(tree.get_tail()[0]))
  398. def visit_type_specifier(self, tree):
  399. self.set_type(tree, types_mv.Type())
  400. def visit_actionname(self, tree):
  401. self.set_type(tree, types_mv.Action())
  402. def visit_string(self, tree):
  403. self.set_type(tree, types_mv.String())
  404. def visit_integer(self, tree):
  405. self.set_type(tree, types_mv.Integer())
  406. def visit_float(self, tree):
  407. self.set_type(tree, types_mv.Float())
  408. # there is no such rule in the grammar, we just avoid code duplicates
  409. def visit_id(self, tree):
  410. name = tree.get_text()
  411. try:
  412. symbol = self.symbol_table.get(name)
  413. except KeyError:
  414. raise RuntimeError("{}:{}:{}: error: '{}' is not declared".format(
  415. self.inputfiles[0], tree.startpos['line'],
  416. tree.startpos['column'], name))
  417. self.set_type(tree, symbol.type)
  418. self.set_symbol(tree, symbol)
  419. def visit_rvalue(self, tree):
  420. if len(tree.get_tail()) > 1:
  421. # Complex
  422. raise Exception("TODO")
  423. else:
  424. # Simple
  425. self.visit_id(tree)
  426. def visit_lvalue(self, tree):
  427. self.visit_id(tree)
  428. def visit_func_call(self, tree):
  429. self.visit_children(tree)
  430. symbol = self.get_symbol(tree.get_tail()[0])
  431. self.set_type(tree, symbol.type)
  432. if not symbol.is_func():
  433. if isinstance(symbol.type, types_mv.Element):
  434. sys.stderr.write("{}:{}:{}: warning: calling a variable of type "
  435. "'Element'\n".format(self.inputfiles[0],
  436. tree.startpos['line'],
  437. tree.startpos['column'],
  438. symbol.name))
  439. return # allow the call without knowing the declaration
  440. raise RuntimeError(
  441. "{}:{}:{}: error: '{}' is a variable of type '{}', not a "
  442. "function".format(self.inputfiles[0],
  443. tree.startpos['line'],
  444. tree.startpos['column'],
  445. symbol.name,
  446. symbol.type))
  447. expressions = tree.get_children("expression")
  448. if len(expressions) != len(symbol.params):
  449. raise RuntimeError(
  450. "{}:{}:{}: error: wrong number of arguments to "
  451. "function '{}'".format(self.inputfiles[0],
  452. tree.startpos['line'],
  453. tree.startpos['column'],
  454. symbol.signature()))
  455. for i in range(len(expressions)):
  456. arg_type = self.get_type(expressions[i])
  457. param_type = symbol.params[i]
  458. if SemanticsVisitor.incompatible_types(arg_type, param_type):
  459. raise RuntimeError(
  460. "{}:{}:{}: error: argument {} has type '{}' instead of "
  461. "'{}', calling function '{}'".format(
  462. self.inputfiles[0],
  463. tree.startpos['line'],
  464. tree.startpos['column'],
  465. i + 1,
  466. str(arg_type),
  467. str(param_type),
  468. symbol.signature()))
  469. if type(arg_type) != type(param_type):
  470. self.perform_implicit_cast(tree, expressions[i], arg_type,
  471. param_type)
  472. if symbol.name in ["input", "output"]:
  473. tree.head = symbol.name
  474. def visit_input(self, tree):
  475. pass # no need to visit it again
  476. def visit_output(self, tree):
  477. pass # no need to visit it again
  478. def visit_dictionary(self, tree):
  479. self.set_type(tree, types_mv.Element)
  480. def visit_list(self, tree):
  481. self.set_type(tree, types_mv.Element)
  482. def visit_dict_item(self, tree):
  483. pass
  484. def visit_ifelse(self, tree):
  485. self.visit_children(tree)
  486. expressions = tree.get_children("expression")
  487. for expression in expressions:
  488. self.check_predicate(expression)
  489. def visit_while(self, tree):
  490. self.visit_children(tree)
  491. expression = tree.get_child("expression")
  492. self.check_predicate(expression)
  493. def visit_block(self, tree):
  494. self.symbol_table.open_scope()
  495. self.visit_children(tree)
  496. self.symbol_table.close_scope()
  497. def visit_func_body(self, tree):
  498. self.visit_children(tree)
  499. def visit_funcdecl(self, tree):
  500. # here we only visit the body cause the declaration is already done
  501. # by declare_functions_visitor
  502. if tree.get_child('func_body') is not None:
  503. self.current_funcdecl = tree
  504. self.symbol_table.open_scope()
  505. self.visit_children(tree)
  506. self.symbol_table.close_scope()
  507. self.current_funcdecl = None
  508. def visit_parameter(self, tree):
  509. param_id = tree.get_child("ID")
  510. type_spec = tree.get_child("type_specifier")
  511. param_type = types_mv.string_to_type(type_spec.get_text())
  512. param_name = param_id.get_text()
  513. symbol = st.Symbol(param_name, param_type, is_global=False)
  514. try:
  515. self.symbol_table.add(symbol)
  516. except Exception:
  517. raise RuntimeError(
  518. "{}:{}:{}: error: redeclaration of '{}'".format(
  519. self.inputfiles[0], tree.startpos['line'],
  520. tree.startpos['column'], param_name))
  521. self.set_symbol(tree, symbol)
  522. def visit_return(self, tree):
  523. self.visit_children(tree)
  524. self.check_return(tree)
  525. def visit_bool(self, tree):
  526. self.set_type(tree, types_mv.Boolean())