| # -*- coding: utf-8 -*- |
| # Copyright 2010-2014, Google Inc. |
| # All rights reserved. |
| # |
| # Redistribution and use in source and binary forms, with or without |
| # modification, are permitted provided that the following conditions are |
| # met: |
| # |
| # * Redistributions of source code must retain the above copyright |
| # notice, this list of conditions and the following disclaimer. |
| # * Redistributions in binary form must reproduce the above |
| # copyright notice, this list of conditions and the following disclaimer |
| # in the documentation and/or other materials provided with the |
| # distribution. |
| # * Neither the name of Google Inc. nor the names of its |
| # contributors may be used to endorse or promote products derived from |
| # this software without specific prior written permission. |
| # |
| # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| # A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| # OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| # SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| # LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| |
| """Generates test cases for mozc/rewriter/calculator/calculator_test.cc""" |
| |
| # Usage example: |
| # $ python gen_test.py --size=5000 --test_output=testset.txt |
| # $ python gen_test.py --test_output=testset.txt --cc_output=test.cc |
| # To see other options available, type python gen_test.py --help |
| # |
| # This script randomly generates a number of test cases used in |
| # mozc/rewriter/calculator/calculator_test.cc. Each test case is written as a |
| # line in the form of expr=ans, where expr is an expression that may involve |
| # Japanese characters, and ans is the correct solution, in sufficiently |
| # accurate precision, to be calculated by mozc. In case where expr is |
| # incomputable due to, e.g., overflow and/or division-by-zero, ans is |
| # empty. It's expected that the mozc calculator rejects such expressions. |
| # |
| # Since a lot of expressions are generated at random, to guarantee that the |
| # values of ans are really correct, the script itself does "test-for-test" |
| # using python's eval() function. Namely, after building an expression tree, |
| # we generate a python expression corresponding to the tree and compare its |
| # value with that of the the direct evaluation. This test runs automatically |
| # inside the script, but you can also write it to a file by specifying |
| # --py_output option. Furthermore, passing --cc_output options enables you to |
| # generate C++ code, respectively, that warns about expressions if results in |
| # C++ differ from those of test cases. Thus, generated test cases are |
| # reliable. (Having said that, there still remains precision issue. For |
| # example, the same python expression leads to different result on 64-bit |
| # Linux and Mac. Thus, the accuracy of results is checked either by absolute |
| # error or relative error in check program; see implementation of |
| # TestCaseGenerator for details.) |
| # |
| # When generating string representation of an expression tree, we should put |
| # parentheses very carefully because, even if we know that changing evaluation |
| # order never affects the result mathematically, like the associativity of + |
| # operator, the result may slightly change in computer due to precision. That |
| # may cause an error in unit test because the mozc parser and the python |
| # eval() parser may build expression trees that are mathematically equivalent |
| # but have different order of computation. Thus, we put parentheses as safely |
| # as possible so that the same order of computations are guaranteed in mozc |
| # and python. |
| # |
| # *** NOTE ON PRECISION AND ORDER OF COMPUTATION *** |
| # |
| # Since the mozc just uses double to store values at each computational step |
| # and uses std::pow and std::fmod from cmath, plus since the script may |
| # generate long, complicated expressions with very large and very small |
| # values, the order of computation becomes a real issue. To see this, first |
| # take a look at the following two expressions from python: |
| # |
| # math.fmod(math.pow((5231*6477/+(1252.18620676)), |
| # (+(math.fmod(6621, -1318)))), |
| # (-(5389 + -8978)) + (1698 + ((3140.89975168) |
| # + (-(math.fmod(97.705869081900005, -322.0)))))) |
| # = 3728.1155588589027 |
| # |
| # math.fmod(math.pow((5231*6477/+(1252.18620676)), |
| # (+(math.fmod(6621, -1318)))), |
| # (-(5389 + -8978) + 1698 + 3140.89975168 |
| # + -(math.fmod(97.705869081900005, -322.0)))) |
| # = 3980.9098289592912 |
| # |
| # Looking like the same expression but the results look totally different. You |
| # will find out that only difference is the order of additions because of |
| # parentheses and those are mathematically equivalent. If we proceed |
| # calculation in python, we arrive at: |
| # |
| # big = 2.5175653147668723e+137 |
| # math.fmod(big, 8330.1938825980997) = 3728.1155588589027 |
| # math.fmod(big, 8330.1938825981015) = 3980.9098289592912 |
| # |
| # The difference of the second values is really small, but since the first |
| # argument, big, is enormously large, the math.fmod ends with really different |
| # results. Cases like this example rarely occurs, but really does. Indeed, |
| # the first expression was generated by this script and calculated by python, |
| # but mozc calculated as in the second one. To avoid such situations, the |
| # current script puts parentheses as carefully and safely as possible. If |
| # such a case happens, it's really tough to track bugs... |
| |
| import codecs |
| import logging |
| import math |
| import optparse |
| import random |
| import sys |
| |
| |
| class Error(Exception): |
| """Base class for all the exceptions in this script.""" |
| pass |
| |
| class EvalError(Error): |
| """Raised on failure of the evaluation of expression tree, e.g., overflow |
| and division-by-zero, etc.""" |
| pass |
| |
| class FatalError(Error): |
| """Raised, e.g., when the evaluation result of expression tree is different |
| from that of python's eval() function.""" |
| pass |
| |
| |
| def is_finite(x): |
| """Checks if x is finite real number.""" |
| return not (math.isnan(x) or math.isinf(x)) |
| |
| |
| class Expr(object): |
| """Base class for nodes of expression tree, like number, addition, etc.""" |
| def __init__(self): |
| pass |
| |
| def contains_operator(self): |
| """Checks whether the expression has at least one operator, such as |
| addition, multiplication, etc.""" |
| raise FatalError('Expr.contains_operator called') |
| |
| def eval(self): |
| """Evaluates the expression tree hanging from this node and returns the |
| result. Raises EvalError if the evaluation fails due to overflow, |
| division-by-zero, etc. |
| """ |
| raise FatalError('Expr.eval called') |
| |
| def build_test_expr(self): |
| """Returns a string representation of the tree for test cases.""" |
| raise FatalError('Expr.build_test_expr called') |
| |
| def build_python_expr(self): |
| """Returns a python expression of the tree that can be evaluated by |
| python's eval().""" |
| raise FatalError('Expr.build_python_expr called') |
| |
| def build_cc_expr(self): |
| """Returns a C++ expression of the tree that can be compiled by C++ |
| compilers.""" |
| raise FatalError('Expr.build_cc_expr called') |
| |
| |
| class Number(Expr): |
| """Base class for number nodes (i.e., levaes). |
| |
| Attribute: |
| _value: the value of the number. |
| """ |
| def __init__(self, value): |
| Expr.__init__(self) |
| self._value = value |
| |
| def contains_operator(self): |
| return False |
| |
| def eval(self): |
| return float(self._value) |
| |
| |
| class Integer(Number): |
| """Integer node, e.g., 10, 20, -30, etc.""" |
| |
| def __init__(self, value): |
| assert(isinstance(value, int)) |
| Number.__init__(self, value) |
| |
| def build_test_expr(self): |
| return str(self._value) |
| |
| def build_python_expr(self): |
| return '%d.0' % self._value |
| |
| def build_cc_expr(self): |
| return 'static_cast<double>(%d)' % self._value |
| |
| |
| class Float(Number): |
| """Floating-point number node, e.g., 3.14, 2.718, etc.""" |
| |
| def __init__(self, value): |
| assert(isinstance(value, float)) |
| |
| # Since values are created from string in mozc, we once convert the value |
| # to a string and then re-convert it to a float, for just in case. |
| self._value_str = str(value) |
| Number.__init__(self, float(self._value_str)) |
| |
| def build_test_expr(self): |
| return self._value_str |
| |
| def build_python_expr(self): |
| return repr(self._value) # E.g., 2.4 -> 2.3999999999999999 |
| |
| def build_cc_expr(self): |
| return repr(self._value) |
| |
| |
| class Group(Expr): |
| """Grouped expression: (Expr) |
| |
| Attribute: |
| _expr: an expression (Expr object) inside the parentheses. |
| """ |
| def __init__(self, expr): |
| Expr.__init__(self) |
| self._expr = expr |
| |
| def contains_operator(self): |
| # A pair of parentheses is not treated as an operator in mozc. |
| return self._expr.contains_operator() |
| |
| def eval(self): |
| return self._expr.eval() |
| |
| def build_test_expr(self): |
| return '(%s)' % self._expr.build_test_expr() |
| |
| def build_python_expr(self): |
| return '(%s)' % self._expr.build_python_expr() |
| |
| def build_cc_expr(self): |
| return '(%s)' % self._expr.build_cc_expr() |
| |
| |
| class UnaryExpr(Expr): |
| """Base class for unary operators. |
| |
| This is an abstract class: two functions, _unary_func and _op_symbol must be |
| implemented in each subclass. |
| |
| Attribute: |
| _expr: an Expr object to which the operator applied. |
| """ |
| def __init__(self, expr): |
| Expr.__init__(self) |
| self._expr = expr |
| |
| def contains_operator(self): |
| # Unary operators are treated as operator in mozc. |
| return True |
| |
| @classmethod |
| def _op_symbol(cls): |
| """Returns a character representation of this operator, like + and -.""" |
| raise FatalError('UnaryExpr._op_symbol called') |
| |
| @classmethod |
| def _unary_func(cls, x): |
| """Evaluates the unary operator (i.e., this function is an underlying |
| univariate function for the operator). |
| |
| Arg: |
| x: a float to which the operator applied. |
| """ |
| raise FatalError('UnaryExpr._unary_func called') |
| |
| def eval(self): |
| value = self._unary_func(self._expr.eval()) |
| if not is_finite(value): |
| raise EvalError('%s(%f) [overflow]' % (self._op_symbol(), value)) |
| return value |
| |
| def build_test_expr(self): |
| # If the child expression is one of the following, then we can omit |
| # parentheses becase of precedence. |
| if (isinstance(self._expr, Number) or |
| isinstance(self._expr, UnaryExpr) or |
| isinstance(self._expr, Group)): |
| format = '%s%s' |
| else: |
| format = '%s(%s)' |
| return format % (self._op_symbol(), self._expr.build_test_expr()) |
| |
| def build_python_expr(self): |
| return '%s(%s)' % (self._op_symbol(), self._expr.build_python_expr()) |
| |
| def build_cc_expr(self): |
| return '%s(%s)' % (self._op_symbol(), self._expr.build_cc_expr()) |
| |
| |
| class PositiveSign(UnaryExpr): |
| """Positive sign node: +Expr""" |
| |
| def __init__(self, expr): |
| UnaryExpr.__init__(self, expr) |
| |
| @classmethod |
| def _op_symbol(cls): |
| return '+' |
| |
| @classmethod |
| def _unary_func(cls, x): |
| return x |
| |
| |
| class Negation(UnaryExpr): |
| """Negation operator node: -Expr""" |
| |
| def __init__(self, expr): |
| UnaryExpr.__init__(self, expr) |
| |
| @classmethod |
| def _op_symbol(cls): |
| return '-' |
| |
| @classmethod |
| def _unary_func(cls, x): |
| return -x |
| |
| |
| class BinaryExpr(Expr): |
| """Base class for binary operators. |
| |
| This is an abstract class: two functions, _op_symbol and _binary_func must |
| be implemented in each subclass. |
| |
| Attributes: |
| _left_expr: an expression (Expr object) on left side. |
| _right_expr: an expression (Expr object) on right side. |
| """ |
| def __init__(self, left_expr, right_expr): |
| Expr.__init__(self) |
| self._left_expr = left_expr |
| self._right_expr = right_expr |
| |
| @classmethod |
| def _op_symbol(cls): |
| """Returns a character representation of this operator, like + and -.""" |
| raise FatalError('UnaryExpr._op_symbol called') |
| |
| @classmethod |
| def _binary_func(cls, x, y): |
| """Evaluates the unary operator (i.e., this function is an underlying |
| bivariate function for the operator).""" |
| raise FatalError('BinaryExpr._binary_func called') |
| |
| def contains_operator(self): |
| return True |
| |
| def eval(self): |
| left_value = self._left_expr.eval() |
| right_value = self._right_expr.eval() |
| if not (is_finite(left_value) and is_finite(right_value)): |
| raise EvalError('%f %s %f [invalid values]' |
| % (left_value, self._op_symbol(), right_value)) |
| value = self._binary_func(left_value, right_value) |
| if not is_finite(value): |
| raise EvalError('%f %s %f = %f [overflow or NaN]' |
| % (left_value, self._op_symbol(), right_value, value)) |
| return value |
| |
| def build_test_expr(self): |
| if (isinstance(self._left_expr, Number) or |
| isinstance(self._left_expr, UnaryExpr) or |
| isinstance(self._left_expr, Group)): |
| left_format = '%s' |
| else: |
| left_format = '(%s)' |
| |
| if (isinstance(self._right_expr, Number) or |
| isinstance(self._right_expr, UnaryExpr) or |
| isinstance(self._right_expr, Group)): |
| right_format = '%s' |
| else: |
| right_format = '(%s)' |
| |
| format = left_format + '%s' + right_format |
| return format % (self._left_expr.build_test_expr(), |
| self._op_symbol(), |
| self._right_expr.build_test_expr()) |
| |
| def build_python_expr(self): |
| return '(%s) %s (%s)' % (self._left_expr.build_python_expr(), |
| self._op_symbol(), |
| self._right_expr.build_python_expr()) |
| |
| def build_cc_expr(self): |
| return '(%s) %s (%s)' % (self._left_expr.build_cc_expr(), |
| self._op_symbol(), |
| self._right_expr.build_cc_expr()) |
| |
| class Addition(BinaryExpr): |
| """Addition: Expr1 + Expr2""" |
| |
| @classmethod |
| def _op_symbol(cls): |
| return '+' |
| |
| @classmethod |
| def _binary_func(cls, x, y): |
| return x + y |
| |
| def __init__(self, left_expr, right_expr): |
| BinaryExpr.__init__(self, left_expr, right_expr) |
| |
| |
| class Subtraction(BinaryExpr): |
| """Subtraction: Expr1 - Expr2""" |
| |
| def __init__(self, left_expr, right_expr): |
| BinaryExpr.__init__(self, left_expr, right_expr) |
| |
| @classmethod |
| def _op_symbol(cls): |
| return '-' |
| |
| @classmethod |
| def _binary_func(cls, x, y): |
| return x - y |
| |
| |
| class Multiplication(BinaryExpr): |
| """Multiplication: Expr1 * Expr2""" |
| |
| def __init__(self, left_expr, right_expr): |
| BinaryExpr.__init__(self, left_expr, right_expr) |
| |
| @classmethod |
| def _op_symbol(cls): |
| return '*' |
| |
| @classmethod |
| def _binary_func(cls, x, y): |
| return x * y |
| |
| |
| class Division(BinaryExpr): |
| """Division: Expr1 / Expr2""" |
| |
| def __init__(self, left_expr, right_expr): |
| BinaryExpr.__init__(self, left_expr, right_expr) |
| |
| @classmethod |
| def _op_symbol(cls): |
| return '/' |
| |
| @classmethod |
| def _binary_func(cls, x, y): |
| try: |
| return x / y |
| except ZeroDivisionError: |
| raise EvalError('%f / %f [division by zero]' % (x, y)) |
| |
| |
| class Power(BinaryExpr): |
| """Power: Expr1 ^ Expr2 or Expr1 ** Expr2""" |
| |
| def __init__(self, left_expr, right_expr): |
| BinaryExpr.__init__(self, left_expr, right_expr) |
| |
| @classmethod |
| def _op_symbol(cls): |
| return '^' |
| |
| @classmethod |
| def _binary_func(cls, x, y): |
| try: |
| return math.pow(x, y) |
| except OverflowError: |
| raise EvalError('%f ^ %f [overflow]' % (x, y)) |
| except ValueError: |
| raise EvalError('%f ^ %f [math.pow error]' % (x, y)) |
| |
| def build_test_expr(self): |
| # Note: we cannot use the default implementation of this function from |
| # BinaryExpr because mozc interprets, e.g., -3^2 as -(3^2), which means |
| # that if left expr is a number but negative, we need to put parentheses. |
| if not (isinstance(self._left_expr, Group)): |
| format = '(%s)^' |
| else: |
| format = '%s^' |
| |
| if not (isinstance(self._right_expr, Number) or |
| isinstance(self._right_expr, UnaryExpr) or |
| isinstance(self._right_expr, Group)): |
| format += '(%s)' |
| else: |
| format += '%s' |
| |
| return format % (self._left_expr.build_test_expr(), |
| self._right_expr.build_test_expr()) |
| |
| def build_python_expr(self): |
| return 'math.pow(%s, %s)' % (self._left_expr.build_python_expr(), |
| self._right_expr.build_python_expr()) |
| |
| def build_cc_expr(self): |
| return 'pow(%s, %s)' % (self._left_expr.build_cc_expr(), |
| self._right_expr.build_cc_expr()) |
| |
| |
| class Modulo(BinaryExpr): |
| """Modulo for floats: Expr1 % Expr2, or fmod(Expr1, Expr2)""" |
| |
| def __init__(self, left_expr, right_expr): |
| BinaryExpr.__init__(self, left_expr, right_expr) |
| |
| @classmethod |
| def _op_symbol(cls): |
| return '%' |
| |
| @classmethod |
| def _binary_func(cls, x, y): |
| try: |
| return math.fmod(x, y) |
| except ValueError: # Raised by calling math.fmod(x, 0.0) |
| raise EvalError('%f %% %f [math.fmod error]' % (x, y)) |
| |
| def build_python_expr(self): |
| return 'math.fmod(%s, %s)' % (self._left_expr.build_python_expr(), |
| self._right_expr.build_python_expr()) |
| |
| def build_cc_expr(self): |
| return 'fmod(%s, %s)' % (self._left_expr.build_cc_expr(), |
| self._right_expr.build_cc_expr()) |
| |
| |
| class RandomExprBuilder(object): |
| """Random expression tree builder. |
| |
| Randomly builds an expression tree using recursive calls. |
| |
| Attributes: |
| _max_abs_val: maximum absolute values of each number in expression. |
| _factories: a list of factories used to constract expression nodes. |
| """ |
| def __init__(self, max_abs_val): |
| self._max_abs_val = max_abs_val |
| |
| # Default factory is only self._build_expr, which means that only number |
| # nodes are generated; see the implementation of self._build_expr. |
| self._factories = [lambda n: self._build_expr(n)] |
| |
| def add_operators(self, string): |
| """Adds operators for node candidates. |
| |
| For example, to generate expressions with four arithmetic operations (+, |
| -, *, /), call this method like: builder.add_operators('add,sub,mul,div') |
| |
| Arg: |
| string: operator names, each separated by comma, without spaces. The |
| correspondence between operators and their names are as follows: |
| group: (expr) |
| pos: +expr |
| neg: -expr |
| add: expr1 + expr2 |
| sub: expr1 - expr2 |
| mul: expr1 * expr2 |
| div: expr1 / expr2 |
| pow: expr1 ^ expr2 |
| mod: expr1 % expr2 |
| """ |
| factories = {'group': lambda n: Group(self._build_expr(n)), |
| 'pos': lambda n: PositiveSign(self._build_expr(n)), |
| 'neg': lambda n: Negation(self._build_expr(n)), |
| 'add': lambda n: Addition(self._build_expr(n), |
| self._build_expr(n)), |
| 'sub': lambda n: Subtraction(self._build_expr(n), |
| self._build_expr(n)), |
| 'mul': lambda n: Multiplication(self._build_expr(n), |
| self._build_expr(n)), |
| 'div': lambda n: Division(self._build_expr(n), |
| self._build_expr(n)), |
| 'pow': lambda n: Power(self._build_expr(n), |
| self._build_expr(n)), |
| 'mod': lambda n: Modulo(self._build_expr(n), |
| self._build_expr(n))} |
| for op in string.split(','): |
| self._factories.append(factories[op]) |
| |
| def build(self, max_depth): |
| """Builds a random expression tree. |
| |
| This method generates only those expressions that include at least one |
| operator, because mozc doesn't calculates expressions without operator, |
| e.g. (123)=. |
| |
| Arg: |
| max_depth: the maximum possible height of tree. |
| """ |
| for i in range(100): |
| expr = self._build_expr(max_depth) |
| if expr.contains_operator(): |
| return expr |
| else: |
| raise FatalError('Failed to build expression containing ' |
| 'at least one operator many times') |
| |
| def _build_expr(self, max_depth): |
| """Implementation of recursive tree construction algorithm.""" |
| if max_depth == 0: # Leaf |
| if random.randint(0, 1) == 0: |
| return Integer(random.randint(-self._max_abs_val, self._max_abs_val)) |
| else: |
| return Float(random.uniform(-self._max_abs_val, self._max_abs_val)) |
| |
| # Select a node factory at random and generate childs. |
| factory = random.choice(self._factories) |
| return factory(max_depth - 1) |
| |
| |
| class TestCaseGenerator(object): |
| """Test case generator for expression trees. Generates test cases for |
| expressions by mixinig japanese fonts to expressions. |
| |
| Attributes: |
| _filename: filename of output file |
| _file: file object to which test cases are written. |
| _num_total_cases: total number of written expressions. |
| _num_computable_cases: number of computable expressions. |
| """ |
| |
| # Character map used to generate test expression including Japanese. |
| _EQUIVALENT_CHARS = {'+': ['+', u'+'], |
| '-': ['-', u'−', u'ー'], |
| '*': ['*', u'*'], |
| '/': ['/', u'/', u'・'], |
| '^': ['^'], |
| '%': ['%', u'%'], |
| '(': ['(', u'('], |
| ')': [')', u')'], |
| '0': ['0', u'0'], |
| '1': ['1', u'1'], |
| '2': ['2', u'2'], |
| '3': ['3', u'3'], |
| '4': ['4', u'4'], |
| '5': ['5', u'5'], |
| '6': ['6', u'6'], |
| '7': ['7', u'7'], |
| '8': ['8', u'8'], |
| '9': ['9', u'9']} |
| |
| def __init__(self, test_filename, py_filename = '', cc_filename = ''): |
| """ |
| Arg: |
| filename: output file. When it's empty, generates nothing. |
| """ |
| self._num_total_cases = 0 |
| self._num_computable_cases = 0 |
| |
| # Initialize output file |
| self._test_filename = test_filename |
| if test_filename: |
| self._test_file = codecs.getwriter('utf-8')(open(test_filename, 'wb')) |
| else: |
| # Replace the generating function by a dummy |
| self.add_test_case_for = lambda expr: None |
| self._test_file = None |
| |
| # Initialize python code |
| if py_filename: |
| self._py_file = codecs.getwriter('utf-8')(open(py_filename, 'wb')) |
| self._py_file.write('import math\n\n') |
| else: |
| self._add_py_code_for = lambda py_expr, expected: None |
| self._py_file = None |
| |
| # Initialize cc code |
| if cc_filename: |
| self._cc_file = codecs.getwriter('utf-8')(open(cc_filename, 'wb')) |
| self._cc_file.write('// Automatically generated by ' |
| 'mozc/src/data/test/calculator/gen_test.py\n\n' |
| '#include <cmath>\n' |
| '#include <iostream>\n' |
| '#include <string>\n\n' |
| 'using namespace std;\n\n') |
| else: |
| # Replace the generating function by a dummy |
| self._add_cc_code_for = lambda cc_expr, expectecd: None |
| self._cc_file = None |
| |
| def __del__(self): |
| if self._test_file: |
| self._test_file.close() |
| logging.info('%d test cases were written to %s, ' |
| 'of which %d can be calculated.', |
| self._num_total_cases, self._test_filename, |
| self._num_computable_cases) |
| |
| if self._py_file: |
| self._py_file.close() |
| |
| if self._cc_file: |
| self._cc_file.write('int main(int, char**) {\n') |
| for i in range(self._num_total_cases): |
| self._cc_file.write(' test%d();\n' % i) |
| self._cc_file.write(' return 0;\n' |
| '}\n') |
| self._cc_file.close() |
| |
| @staticmethod |
| def _mix_japanese_string(string): |
| """Randomly transforms half-width characters to full-width.""" |
| result = u'' |
| for char in string: |
| if char in TestCaseGenerator._EQUIVALENT_CHARS: |
| equiv_chars = TestCaseGenerator._EQUIVALENT_CHARS[char] |
| result += random.choice(equiv_chars) |
| else: |
| result += char |
| return result |
| |
| def add_test_case_for(self, expr): |
| """Appends the code that checks whether the evaluation result of given |
| expr coincides with the epxected result. |
| |
| Args: |
| expr: Expr object |
| """ |
| test_expr = self._mix_japanese_string(expr.build_test_expr()) |
| try: |
| # Raises an exceeption on failure, like divison-by-zero, etc. |
| value = expr.eval() |
| |
| # If the above evaluation was a success, the same value should be |
| # calculated by python's eval. This check should be done in absolute |
| # error because the script runs on the same machine. |
| py_expr = expr.build_python_expr() |
| py_value = eval(py_expr) |
| if not (abs(value - py_value) < 1e-8): |
| logging.critical('Calculation differs from python: %f != %f (python)\n' |
| 'test: %s\n' |
| ' py: %s', value, py_value, test_expr, py_expr) |
| raise FatalError('Expression tree evaluation error') |
| |
| self._num_computable_cases += 1 |
| self._test_file.write(u'%s=%.8g\n' % (test_expr, value)) |
| self._add_py_code_for(py_expr, value) |
| self._add_cc_code_for(expr.build_cc_expr(), value) |
| except EvalError: |
| self._test_file.write(u'%s=\n' % test_expr) |
| self._add_cc_code_for(expr.build_cc_expr(), None) |
| |
| self._num_total_cases += 1 |
| |
| def _add_py_code_for(self, py_expr, expected): |
| """Appends python code that checks whether the evaluation result of given |
| expr coincides with the epxected result. |
| |
| If expected is None, it indicates that the evaluation of expr results in |
| error (like overflow and division-by-zero). Currently, just generates |
| comments for such cases. |
| |
| In generated scrpt, the accuracy is verified either in absolute error or |
| relative error, because there's a possibility that different machines |
| generate different values due to precision. For example, if the expected |
| value is very large, we cannot expect that error is less than a certain |
| small threshold. In this case, however, the relative error would work. |
| |
| Args: |
| py_expr: string of python expression. |
| expected: expected value of the expression (float) |
| """ |
| if expected: |
| self._py_file.write('expr = u"%s"\n' % py_expr) |
| self._py_file.write('expected = %s\n' % repr(expected)) |
| self._py_file.write('val = eval(expr)\n') |
| self._py_file.write('err = abs(val - expected)\n') |
| self._py_file.write('if (err > 1e-8 and\n') |
| self._py_file.write(' err > 1e-2 * abs(expected)):\n') |
| self._py_file.write(' print repr(val), "!=", repr(expected)\n') |
| self._py_file.write(' print "expr =", expr\n\n') |
| else: |
| self._py_file.write('# Incomputable\n' |
| '# %s\n\n' % py_expr) |
| |
| def _add_cc_code_for(self, cc_expr, expected): |
| """Appends the code that checks whether the evaluation result of given |
| expr coincides with the epxected result. |
| |
| If expected is None, it indicates that the evaluation of expr results in |
| error (like overflow and division-by-zero). Currently, just generates |
| comments for such cases. |
| |
| In generated code, the accuracy is verified either in absolute error or |
| relative error; see _add_py_code_for for details. |
| |
| Args: |
| cc_expr: string of C++ expression. |
| expected: expected value of the expression (float) |
| """ |
| self._cc_file.write('void test%d() {\n' % self._num_total_cases) |
| if expected: |
| self._cc_file.write(' const string expr = string("%s");\n' % cc_expr) |
| self._cc_file.write(' const double expected = %s;\n' % repr(expected)) |
| self._cc_file.write(' const double val = %s;\n' % cc_expr) |
| self._cc_file.write(' const double err = abs(val - expected);\n') |
| self._cc_file.write(' if (err > 1e-8 || err > 1e-2 * abs(expected))\n') |
| self._cc_file.write(' cerr << val << " != " << expected\n') |
| self._cc_file.write(' << "expr = " << expr << endl;\n') |
| else: |
| self._cc_file.write(' // Incomputable\n' |
| ' // %s\n' % cc_expr) |
| self._cc_file.write('}\n\n') |
| |
| |
| def parse_options(): |
| parser = optparse.OptionParser() |
| parser.add_option('--size', type = 'int', dest = 'size', default = 100, |
| metavar = 'NUM', help = 'Number of tests to be generated') |
| parser.add_option('--max_depth', type = 'int', dest = 'max_depth', |
| default = 5, metavar = 'NUM', |
| help = 'Max depth of equation tree (default = 5)') |
| parser.add_option('--max_abs', type = 'float', dest = 'max_abs', |
| default = 1e+4, metavar = 'FLOAT', |
| help = 'Max absolute value of each number (default = 1e+4)') |
| parser.add_option('--operators', dest = 'operators', metavar = 'OPs', |
| default = 'group,pos,neg,add,sub,mul,div,pow,mod', |
| help = 'Operators used by expression generator') |
| parser.add_option('--test_output', dest = 'test_output', |
| default = '', metavar = 'FILE', |
| help = 'Output test data file') |
| parser.add_option('--py_output', dest = 'py_output', |
| default = '', metavar = 'FILE', |
| help = 'Output python script for verification (optional)') |
| parser.add_option('--cc_output', dest = 'cc_output', |
| default = '', metavar = 'FILE', |
| help = 'Output C++ src for verification (optional)') |
| options, args = parser.parse_args() |
| |
| if not options.test_output: |
| logging.error('--test_output is empty') |
| sys.exit(-1) |
| |
| return options |
| |
| |
| def main(): |
| sys.stdin = codecs.getreader('utf-8')(sys.stdin) |
| sys.stdout = codecs.getwriter('utf-8')(sys.stdout) |
| sys.stderr = codecs.getwriter('utf-8')(sys.stderr) |
| random.seed() |
| logging.basicConfig(level = logging.INFO, |
| format = '%(levelname)s: %(message)s') |
| options = parse_options() |
| |
| if not options.test_output: |
| logging.error('--test_output is empty') |
| sys.exit(-1) |
| |
| builder = RandomExprBuilder(options.max_abs) |
| builder.add_operators(options.operators) |
| test_case_generator = TestCaseGenerator(options.test_output, |
| options.py_output, |
| options.cc_output) |
| |
| for i in range(options.size): |
| expr = builder.build(options.max_depth) |
| test_case_generator.add_test_case_for(expr) |
| |
| |
| if __name__ == '__main__': |
| main() |