# Copyright (C) 2014 The Android Open Source Project # # 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 collections import namedtuple from common.immutables import ImmutableDict from common.logger import Logger from file_format.checker.struct import TestStatement from match.line import match_lines, evaluate_line MatchScope = namedtuple("MatchScope", ["start", "end"]) MatchInfo = namedtuple("MatchInfo", ["scope", "variables"]) class MatchFailedException(Exception): def __init__(self, statement, line_no, variables): self.statement = statement self.line_no = line_no self.variables = variables class BadStructureException(Exception): def __init__(self, msg, line_no): self.msg = msg self.line_no = line_no class IfStack: """ The purpose of this class is to keep track of which branch the cursor is in. This will let us know if the line read by the cursor should be processed or not. Furthermore, this class contains the methods to handle the CHECK-[IF, ELIF, ELSE, FI] statements, and consequently update the stack with new information. The following elements can appear on the stack: - BRANCH_TAKEN: a branch is taken if its condition evaluates to true and its parent branch was also previously taken. - BRANCH_NOT_TAKEN_YET: the branch's parent was taken, but this branch wasn't as its condition did not evaluate to true. - BRANCH_NOT_TAKEN: a branch is not taken when its parent was either NotTaken or NotTakenYet. It doesn't matter if the condition would evaluate to true, that's not even checked. CHECK-IF is the only instruction that pushes a new element on the stack. CHECK-ELIF and CHECK-ELSE will update the top of the stack to keep track of what's been seen. That means that we can check if the line currently pointed to by the cursor should be processed just by looking at the top of the stack. CHECK-FI will pop the last element. `BRANCH_TAKEN`, `BRANCH_NOT_TAKEN`, `BRANCH_NOT_TAKEN_YET` are implemented as positive integers. Negated values of `BRANCH_TAKEN` and `BRANCH_NOT_TAKEN` may be appear; `-BRANCH_TAKEN` and `-BRANCH_NOT_TAKEN` have the same meaning as `BRANCH_TAKEN` and `BRANCH_NOT_TAKEN` (respectively), but they indicate that we went past the ELSE branch. Knowing that, we can output a precise error message if the user creates a malformed branching structure. """ BRANCH_TAKEN, BRANCH_NOT_TAKEN, BRANCH_NOT_TAKEN_YET = range(1, 4) def __init__(self): self.stack = [] def can_execute(self): """ Returns true if we're not in any branch, or the branch we're currently in was taken. """ if self._is_empty(): return True return abs(self._peek()) == IfStack.BRANCH_TAKEN def handle(self, statement, variables): """ This function is invoked if the cursor is pointing to a CHECK-[IF, ELIF, ELSE, FI] line. """ variant = statement.variant if variant is TestStatement.Variant.IF: self._if(statement, variables) elif variant is TestStatement.Variant.ELIF: self._elif(statement, variables) elif variant is TestStatement.Variant.ELSE: self._else(statement) else: assert variant is TestStatement.Variant.FI self._fi(statement) def eof(self): """ The last line the cursor points to is always EOF. """ if not self._is_empty(): raise BadStructureException("Missing CHECK-FI", -1) def _is_empty(self): return not self.stack def _if(self, statement, variables): if not self._is_empty() and abs(self._peek()) in [IfStack.BRANCH_NOT_TAKEN, IfStack.BRANCH_NOT_TAKEN_YET]: self._push(IfStack.BRANCH_NOT_TAKEN) elif evaluate_line(statement, variables): self._push(IfStack.BRANCH_TAKEN) else: self._push(IfStack.BRANCH_NOT_TAKEN_YET) def _elif(self, statement, variables): if self._is_empty(): raise BadStructureException("CHECK-ELIF must be after CHECK-IF or CHECK-ELIF", statement.line_no) if self._peek() < 0: raise BadStructureException("CHECK-ELIF cannot be after CHECK-ELSE", statement.line_no) if self._peek() == IfStack.BRANCH_TAKEN: self._set_last(IfStack.BRANCH_NOT_TAKEN) elif self._peek() == IfStack.BRANCH_NOT_TAKEN_YET: if evaluate_line(statement, variables): self._set_last(IfStack.BRANCH_TAKEN) # else, the CHECK-ELIF condition is False, so do nothing: the last element on the stack is # already set to BRANCH_NOT_TAKEN_YET. else: assert self._peek() == IfStack.BRANCH_NOT_TAKEN def _else(self, statement): if self._is_empty(): raise BadStructureException("CHECK-ELSE must be after CHECK-IF or CHECK-ELIF", statement.line_no) if self._peek() < 0: raise BadStructureException("Consecutive CHECK-ELSE statements", statement.line_no) if self._peek() in [IfStack.BRANCH_TAKEN, IfStack.BRANCH_NOT_TAKEN]: # Notice that we're setting -BRANCH_NOT_TAKEN rather that BRANCH_NOT_TAKEN as we went past the # ELSE branch. self._set_last(-IfStack.BRANCH_NOT_TAKEN) else: assert self._peek() == IfStack.BRANCH_NOT_TAKEN_YET # Setting -BRANCH_TAKEN rather BRANCH_TAKEN for the same reason. self._set_last(-IfStack.BRANCH_TAKEN) def _fi(self, statement): if self._is_empty(): raise BadStructureException("CHECK-FI does not have a matching CHECK-IF", statement.line_no) self.stack.pop() def _peek(self): assert not self._is_empty() return self.stack[-1] def _push(self, element): self.stack.append(element) def _set_last(self, element): self.stack[-1] = element def find_matching_line(statement, c1_pass, scope, variables, exclude_lines=[]): """ Finds the first line in `c1_pass` which matches `statement`. Scan only lines numbered between `scope.start` and `scope.end` and not on the `excludeLines` list. Returns the index of the `c1Pass` line matching the statement and variables values after the match. Raises MatchFailedException if no such `c1Pass` line can be found. """ for i in range(scope.start, scope.end): if i in exclude_lines: continue new_variables = match_lines(statement, c1_pass.body[i], variables) if new_variables is not None: return MatchInfo(MatchScope(i, i), new_variables) raise MatchFailedException(statement, scope.start, variables) class ExecutionState(object): def __init__(self, c1_pass, variables={}): self.cursor = 0 self.c1_pass = c1_pass self.c1_length = len(c1_pass.body) self.variables = ImmutableDict(variables) self.dag_queue = [] self.not_queue = [] self.if_stack = IfStack() self.last_variant = None def move_cursor(self, match): assert self.cursor <= match.scope.end # Handle any pending NOT statements before moving the cursor self.handle_not_queue(MatchScope(self.cursor, match.scope.start)) self.cursor = match.scope.end + 1 self.variables = match.variables def handle_dag_queue(self, scope): """ Attempts to find matching `c1Pass` lines for a group of DAG statements. Statements are matched in the list order and variable values propagated. Only lines in `scope` are scanned and each line can only match one statement. Returns the range of `c1Pass` lines covered by this group (min/max of matching line numbers) and the variable values after the match of the last statement. Raises MatchFailedException when a statement cannot be satisfied. """ if not self.dag_queue: return matched_lines = [] variables = self.variables for statement in self.dag_queue: assert statement.variant == TestStatement.Variant.DAG match = find_matching_line(statement, self.c1_pass, scope, variables, matched_lines) variables = match.variables assert match.scope.start == match.scope.end assert match.scope.start not in matched_lines matched_lines.append(match.scope.start) match = MatchInfo(MatchScope(min(matched_lines), max(matched_lines)), variables) self.dag_queue = [] self.move_cursor(match) def handle_not_queue(self, scope): """ Verifies that none of the given NOT statements matches a line inside the given `scope` of `c1Pass` lines. Raises MatchFailedException if a statement matches a line in the scope. """ for statement in self.not_queue: assert statement.variant == TestStatement.Variant.NOT for i in range(scope.start, scope.end): if match_lines(statement, self.c1_pass.body[i], self.variables) is not None: raise MatchFailedException(statement, i, self.variables) self.not_queue = [] def handle_eof(self): """ EOF marker always moves the cursor to the end of the file.""" match = MatchInfo(MatchScope(self.c1_length, self.c1_length), None) self.move_cursor(match) def handle_in_order(self, statement): """ Single in-order statement. Find the first line that matches and move the cursor to the subsequent line. Raises MatchFailedException if no such line can be found. """ scope = MatchScope(self.cursor, self.c1_length) match = find_matching_line(statement, self.c1_pass, scope, self.variables) self.move_cursor(match) def handle_next_line(self, statement): """ Single next-line statement. Test if the current line matches and move the cursor to the next line if it does. Raises MatchFailedException if the current line does not match. """ if self.last_variant not in [TestStatement.Variant.IN_ORDER, TestStatement.Variant.NEXT_LINE]: raise BadStructureException("A next-line statement can only be placed " "after an in-order statement or another next-line statement.", statement.line_no) scope = MatchScope(self.cursor, self.cursor + 1) match = find_matching_line(statement, self.c1_pass, scope, self.variables) self.move_cursor(match) def handle_eval(self, statement): """ Evaluates the statement in the current context. Raises MatchFailedException if the expression evaluates to False. """ if not evaluate_line(statement, self.variables): raise MatchFailedException(statement, self.cursor, self.variables) def handle(self, statement): variant = None if statement is None else statement.variant if variant in [TestStatement.Variant.IF, TestStatement.Variant.ELIF, TestStatement.Variant.ELSE, TestStatement.Variant.FI]: self.if_stack.handle(statement, self.variables) return if variant is None: self.if_stack.eof() if not self.if_stack.can_execute(): return # First non-DAG statement always triggers execution of any preceding # DAG statements. if variant is not TestStatement.Variant.DAG: self.handle_dag_queue(MatchScope(self.cursor, self.c1_length)) if variant is None: self.handle_eof() elif variant is TestStatement.Variant.IN_ORDER: self.handle_in_order(statement) elif variant is TestStatement.Variant.NEXT_LINE: self.handle_next_line(statement) elif variant is TestStatement.Variant.DAG: self.dag_queue.append(statement) elif variant is TestStatement.Variant.NOT: self.not_queue.append(statement) else: assert variant is TestStatement.Variant.EVAL self.handle_eval(statement) self.last_variant = variant def match_test_case( test_case, c1_pass, instruction_set_features, read_barrier_type): """ Runs a test case against a C1visualizer graph dump. Raises MatchFailedException when a statement cannot be satisfied. """ assert test_case.name == c1_pass.name initial_variables = { "ISA_FEATURES": instruction_set_features, "READ_BARRIER_TYPE": read_barrier_type } state = ExecutionState(c1_pass, initial_variables) test_statements = test_case.statements + [None] for statement in test_statements: state.handle(statement) def match_files(checker_file, c1_file, target_arch, debuggable_mode, print_cfg): for test_case in checker_file.test_cases: if test_case.test_arch not in [None, target_arch]: continue if test_case.for_debuggable != debuggable_mode: continue # TODO: Currently does not handle multiple occurrences of the same group # name, e.g. when a pass is run multiple times. It will always try to # match a check group against the first output group of the same name. c1_pass = c1_file.find_pass(test_case.name) if c1_pass is None: with open(c1_file.full_file_name) as cfg_file: Logger.log("".join(cfg_file), Logger.Level.ERROR) Logger.fail("Test case not found in the CFG file", c1_file.full_file_name, test_case.start_line_no, test_case.name) Logger.start_test(test_case.name) try: match_test_case( test_case, c1_pass, c1_file.instruction_set_features, c1_file.read_barrier_type) Logger.test_passed() except MatchFailedException as e: line_no = c1_pass.start_line_no + e.line_no if e.statement.variant == TestStatement.Variant.NOT: msg = "NOT statement matched line {}" else: msg = "Statement could not be matched starting from line {}" msg = msg.format(line_no) if print_cfg: with open(c1_file.full_file_name) as cfg_file: Logger.log("".join(cfg_file), Logger.Level.ERROR) Logger.test_failed(msg, e.statement, e.variables)