1# -*- coding: utf-8 -*- 2# Copyright 2010-2018, Google Inc. 3# All rights reserved. 4# 5# Redistribution and use in source and binary forms, with or without 6# modification, are permitted provided that the following conditions are 7# met: 8# 9# * Redistributions of source code must retain the above copyright 10# notice, this list of conditions and the following disclaimer. 11# * Redistributions in binary form must reproduce the above 12# copyright notice, this list of conditions and the following disclaimer 13# in the documentation and/or other materials provided with the 14# distribution. 15# * Neither the name of Google Inc. nor the names of its 16# contributors may be used to endorse or promote products derived from 17# this software without specific prior written permission. 18# 19# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 31"""Generates test cases for mozc/rewriter/calculator/calculator_test.cc""" 32 33# Usage example: 34# $ python gen_test.py --size=5000 --test_output=testset.txt 35# $ python gen_test.py --test_output=testset.txt --cc_output=test.cc 36# To see other options available, type python gen_test.py --help 37# 38# This script randomly generates a number of test cases used in 39# mozc/rewriter/calculator/calculator_test.cc. Each test case is written as a 40# line in the form of expr=ans, where expr is an expression that may involve 41# Japanese characters, and ans is the correct solution, in sufficiently 42# accurate precision, to be calculated by mozc. In case where expr is 43# incomputable due to, e.g., overflow and/or division-by-zero, ans is 44# empty. It's expected that the mozc calculator rejects such expressions. 45# 46# Since a lot of expressions are generated at random, to guarantee that the 47# values of ans are really correct, the script itself does "test-for-test" 48# using python's eval() function. Namely, after building an expression tree, 49# we generate a python expression corresponding to the tree and compare its 50# value with that of the the direct evaluation. This test runs automatically 51# inside the script, but you can also write it to a file by specifying 52# --py_output option. Furthermore, passing --cc_output options enables you to 53# generate C++ code, respectively, that warns about expressions if results in 54# C++ differ from those of test cases. Thus, generated test cases are 55# reliable. (Having said that, there still remains precision issue. For 56# example, the same python expression leads to different result on 64-bit 57# Linux and Mac. Thus, the accuracy of results is checked either by absolute 58# error or relative error in check program; see implementation of 59# TestCaseGenerator for details.) 60# 61# When generating string representation of an expression tree, we should put 62# parentheses very carefully because, even if we know that changing evaluation 63# order never affects the result mathematically, like the associativity of + 64# operator, the result may slightly change in computer due to precision. That 65# may cause an error in unit test because the mozc parser and the python 66# eval() parser may build expression trees that are mathematically equivalent 67# but have different order of computation. Thus, we put parentheses as safely 68# as possible so that the same order of computations are guaranteed in mozc 69# and python. 70# 71# *** NOTE ON PRECISION AND ORDER OF COMPUTATION *** 72# 73# Since the mozc just uses double to store values at each computational step 74# and uses std::pow and std::fmod from cmath, plus since the script may 75# generate long, complicated expressions with very large and very small 76# values, the order of computation becomes a real issue. To see this, first 77# take a look at the following two expressions from python: 78# 79# math.fmod(math.pow((5231*6477/+(1252.18620676)), 80# (+(math.fmod(6621, -1318)))), 81# (-(5389 + -8978)) + (1698 + ((3140.89975168) 82# + (-(math.fmod(97.705869081900005, -322.0)))))) 83# = 3728.1155588589027 84# 85# math.fmod(math.pow((5231*6477/+(1252.18620676)), 86# (+(math.fmod(6621, -1318)))), 87# (-(5389 + -8978) + 1698 + 3140.89975168 88# + -(math.fmod(97.705869081900005, -322.0)))) 89# = 3980.9098289592912 90# 91# Looking like the same expression but the results look totally different. You 92# will find out that only difference is the order of additions because of 93# parentheses and those are mathematically equivalent. If we proceed 94# calculation in python, we arrive at: 95# 96# big = 2.5175653147668723e+137 97# math.fmod(big, 8330.1938825980997) = 3728.1155588589027 98# math.fmod(big, 8330.1938825981015) = 3980.9098289592912 99# 100# The difference of the second values is really small, but since the first 101# argument, big, is enormously large, the math.fmod ends with really different 102# results. Cases like this example rarely occurs, but really does. Indeed, 103# the first expression was generated by this script and calculated by python, 104# but mozc calculated as in the second one. To avoid such situations, the 105# current script puts parentheses as carefully and safely as possible. If 106# such a case happens, it's really tough to track bugs... 107 108import logging 109import math 110import optparse 111import random 112import sys 113 114 115class Error(Exception): 116 """Base class for all the exceptions in this script.""" 117 pass 118 119class EvalError(Error): 120 """Raised on failure of the evaluation of expression tree, e.g., overflow 121 and division-by-zero, etc.""" 122 pass 123 124class FatalError(Error): 125 """Raised, e.g., when the evaluation result of expression tree is different 126 from that of python's eval() function.""" 127 pass 128 129 130def is_finite(x): 131 """Checks if x is finite real number.""" 132 return not (math.isnan(x) or math.isinf(x)) 133 134 135class Expr(object): 136 """Base class for nodes of expression tree, like number, addition, etc.""" 137 def __init__(self): 138 pass 139 140 def contains_operator(self): 141 """Checks whether the expression has at least one operator, such as 142 addition, multiplication, etc.""" 143 raise FatalError('Expr.contains_operator called') 144 145 def eval(self): 146 """Evaluates the expression tree hanging from this node and returns the 147 result. Raises EvalError if the evaluation fails due to overflow, 148 division-by-zero, etc. 149 """ 150 raise FatalError('Expr.eval called') 151 152 def build_test_expr(self): 153 """Returns a string representation of the tree for test cases.""" 154 raise FatalError('Expr.build_test_expr called') 155 156 def build_python_expr(self): 157 """Returns a python expression of the tree that can be evaluated by 158 python's eval().""" 159 raise FatalError('Expr.build_python_expr called') 160 161 def build_cc_expr(self): 162 """Returns a C++ expression of the tree that can be compiled by C++ 163 compilers.""" 164 raise FatalError('Expr.build_cc_expr called') 165 166 167class Number(Expr): 168 """Base class for number nodes (i.e., levaes). 169 170 Attribute: 171 _value: the value of the number. 172 """ 173 def __init__(self, value): 174 Expr.__init__(self) 175 self._value = value 176 177 def contains_operator(self): 178 return False 179 180 def eval(self): 181 return float(self._value) 182 183 184class Integer(Number): 185 """Integer node, e.g., 10, 20, -30, etc.""" 186 187 def __init__(self, value): 188 assert(isinstance(value, int)) 189 Number.__init__(self, value) 190 191 def build_test_expr(self): 192 return str(self._value) 193 194 def build_python_expr(self): 195 return '%d.0' % self._value 196 197 def build_cc_expr(self): 198 return 'static_cast<double>(%d)' % self._value 199 200 201class Float(Number): 202 """Floating-point number node, e.g., 3.14, 2.718, etc.""" 203 204 def __init__(self, value): 205 assert(isinstance(value, float)) 206 207 # Since values are created from string in mozc, we once convert the value 208 # to a string and then re-convert it to a float, for just in case. 209 self._value_str = str(value) 210 Number.__init__(self, float(self._value_str)) 211 212 def build_test_expr(self): 213 return self._value_str 214 215 def build_python_expr(self): 216 return repr(self._value) # E.g., 2.4 -> 2.3999999999999999 217 218 def build_cc_expr(self): 219 return repr(self._value) 220 221 222class Group(Expr): 223 """Grouped expression: (Expr) 224 225 Attribute: 226 _expr: an expression (Expr object) inside the parentheses. 227 """ 228 def __init__(self, expr): 229 Expr.__init__(self) 230 self._expr = expr 231 232 def contains_operator(self): 233 # A pair of parentheses is not treated as an operator in mozc. 234 return self._expr.contains_operator() 235 236 def eval(self): 237 return self._expr.eval() 238 239 def build_test_expr(self): 240 return '(%s)' % self._expr.build_test_expr() 241 242 def build_python_expr(self): 243 return '(%s)' % self._expr.build_python_expr() 244 245 def build_cc_expr(self): 246 return '(%s)' % self._expr.build_cc_expr() 247 248 249class UnaryExpr(Expr): 250 """Base class for unary operators. 251 252 This is an abstract class: two functions, _unary_func and _op_symbol must be 253 implemented in each subclass. 254 255 Attribute: 256 _expr: an Expr object to which the operator applied. 257 """ 258 def __init__(self, expr): 259 Expr.__init__(self) 260 self._expr = expr 261 262 def contains_operator(self): 263 # Unary operators are treated as operator in mozc. 264 return True 265 266 @classmethod 267 def _op_symbol(cls): 268 """Returns a character representation of this operator, like + and -.""" 269 raise FatalError('UnaryExpr._op_symbol called') 270 271 @classmethod 272 def _unary_func(cls, x): 273 """Evaluates the unary operator (i.e., this function is an underlying 274 univariate function for the operator). 275 276 Arg: 277 x: a float to which the operator applied. 278 """ 279 raise FatalError('UnaryExpr._unary_func called') 280 281 def eval(self): 282 value = self._unary_func(self._expr.eval()) 283 if not is_finite(value): 284 raise EvalError('%s(%f) [overflow]' % (self._op_symbol(), value)) 285 return value 286 287 def build_test_expr(self): 288 # If the child expression is one of the following, then we can omit 289 # parentheses becase of precedence. 290 if (isinstance(self._expr, Number) or 291 isinstance(self._expr, UnaryExpr) or 292 isinstance(self._expr, Group)): 293 format = '%s%s' 294 else: 295 format = '%s(%s)' 296 return format % (self._op_symbol(), self._expr.build_test_expr()) 297 298 def build_python_expr(self): 299 return '%s(%s)' % (self._op_symbol(), self._expr.build_python_expr()) 300 301 def build_cc_expr(self): 302 return '%s(%s)' % (self._op_symbol(), self._expr.build_cc_expr()) 303 304 305class PositiveSign(UnaryExpr): 306 """Positive sign node: +Expr""" 307 308 def __init__(self, expr): 309 UnaryExpr.__init__(self, expr) 310 311 @classmethod 312 def _op_symbol(cls): 313 return '+' 314 315 @classmethod 316 def _unary_func(cls, x): 317 return x 318 319 320class Negation(UnaryExpr): 321 """Negation operator node: -Expr""" 322 323 def __init__(self, expr): 324 UnaryExpr.__init__(self, expr) 325 326 @classmethod 327 def _op_symbol(cls): 328 return '-' 329 330 @classmethod 331 def _unary_func(cls, x): 332 return -x 333 334 335class BinaryExpr(Expr): 336 """Base class for binary operators. 337 338 This is an abstract class: two functions, _op_symbol and _binary_func must 339 be implemented in each subclass. 340 341 Attributes: 342 _left_expr: an expression (Expr object) on left side. 343 _right_expr: an expression (Expr object) on right side. 344 """ 345 def __init__(self, left_expr, right_expr): 346 Expr.__init__(self) 347 self._left_expr = left_expr 348 self._right_expr = right_expr 349 350 @classmethod 351 def _op_symbol(cls): 352 """Returns a character representation of this operator, like + and -.""" 353 raise FatalError('UnaryExpr._op_symbol called') 354 355 @classmethod 356 def _binary_func(cls, x, y): 357 """Evaluates the unary operator (i.e., this function is an underlying 358 bivariate function for the operator).""" 359 raise FatalError('BinaryExpr._binary_func called') 360 361 def contains_operator(self): 362 return True 363 364 def eval(self): 365 left_value = self._left_expr.eval() 366 right_value = self._right_expr.eval() 367 if not (is_finite(left_value) and is_finite(right_value)): 368 raise EvalError('%f %s %f [invalid values]' 369 % (left_value, self._op_symbol(), right_value)) 370 value = self._binary_func(left_value, right_value) 371 if not is_finite(value): 372 raise EvalError('%f %s %f = %f [overflow or NaN]' 373 % (left_value, self._op_symbol(), right_value, value)) 374 return value 375 376 def build_test_expr(self): 377 if (isinstance(self._left_expr, Number) or 378 isinstance(self._left_expr, UnaryExpr) or 379 isinstance(self._left_expr, Group)): 380 left_format = '%s' 381 else: 382 left_format = '(%s)' 383 384 if (isinstance(self._right_expr, Number) or 385 isinstance(self._right_expr, UnaryExpr) or 386 isinstance(self._right_expr, Group)): 387 right_format = '%s' 388 else: 389 right_format = '(%s)' 390 391 format = left_format + '%s' + right_format 392 return format % (self._left_expr.build_test_expr(), 393 self._op_symbol(), 394 self._right_expr.build_test_expr()) 395 396 def build_python_expr(self): 397 return '(%s) %s (%s)' % (self._left_expr.build_python_expr(), 398 self._op_symbol(), 399 self._right_expr.build_python_expr()) 400 401 def build_cc_expr(self): 402 return '(%s) %s (%s)' % (self._left_expr.build_cc_expr(), 403 self._op_symbol(), 404 self._right_expr.build_cc_expr()) 405 406class Addition(BinaryExpr): 407 """Addition: Expr1 + Expr2""" 408 409 @classmethod 410 def _op_symbol(cls): 411 return '+' 412 413 @classmethod 414 def _binary_func(cls, x, y): 415 return x + y 416 417 def __init__(self, left_expr, right_expr): 418 BinaryExpr.__init__(self, left_expr, right_expr) 419 420 421class Subtraction(BinaryExpr): 422 """Subtraction: Expr1 - Expr2""" 423 424 def __init__(self, left_expr, right_expr): 425 BinaryExpr.__init__(self, left_expr, right_expr) 426 427 @classmethod 428 def _op_symbol(cls): 429 return '-' 430 431 @classmethod 432 def _binary_func(cls, x, y): 433 return x - y 434 435 436class Multiplication(BinaryExpr): 437 """Multiplication: Expr1 * Expr2""" 438 439 def __init__(self, left_expr, right_expr): 440 BinaryExpr.__init__(self, left_expr, right_expr) 441 442 @classmethod 443 def _op_symbol(cls): 444 return '*' 445 446 @classmethod 447 def _binary_func(cls, x, y): 448 return x * y 449 450 451class Division(BinaryExpr): 452 """Division: Expr1 / Expr2""" 453 454 def __init__(self, left_expr, right_expr): 455 BinaryExpr.__init__(self, left_expr, right_expr) 456 457 @classmethod 458 def _op_symbol(cls): 459 return '/' 460 461 @classmethod 462 def _binary_func(cls, x, y): 463 try: 464 return x / y 465 except ZeroDivisionError: 466 raise EvalError('%f / %f [division by zero]' % (x, y)) 467 468 469class Power(BinaryExpr): 470 """Power: Expr1 ^ Expr2 or Expr1 ** Expr2""" 471 472 def __init__(self, left_expr, right_expr): 473 BinaryExpr.__init__(self, left_expr, right_expr) 474 475 @classmethod 476 def _op_symbol(cls): 477 return '^' 478 479 @classmethod 480 def _binary_func(cls, x, y): 481 try: 482 return math.pow(x, y) 483 except OverflowError: 484 raise EvalError('%f ^ %f [overflow]' % (x, y)) 485 except ValueError: 486 raise EvalError('%f ^ %f [math.pow error]' % (x, y)) 487 488 def build_test_expr(self): 489 # Note: we cannot use the default implementation of this function from 490 # BinaryExpr because mozc interprets, e.g., -3^2 as -(3^2), which means 491 # that if left expr is a number but negative, we need to put parentheses. 492 if not (isinstance(self._left_expr, Group)): 493 format = '(%s)^' 494 else: 495 format = '%s^' 496 497 if not (isinstance(self._right_expr, Number) or 498 isinstance(self._right_expr, UnaryExpr) or 499 isinstance(self._right_expr, Group)): 500 format += '(%s)' 501 else: 502 format += '%s' 503 504 return format % (self._left_expr.build_test_expr(), 505 self._right_expr.build_test_expr()) 506 507 def build_python_expr(self): 508 return 'math.pow(%s, %s)' % (self._left_expr.build_python_expr(), 509 self._right_expr.build_python_expr()) 510 511 def build_cc_expr(self): 512 return 'pow(%s, %s)' % (self._left_expr.build_cc_expr(), 513 self._right_expr.build_cc_expr()) 514 515 516class Modulo(BinaryExpr): 517 """Modulo for floats: Expr1 % Expr2, or fmod(Expr1, Expr2)""" 518 519 def __init__(self, left_expr, right_expr): 520 BinaryExpr.__init__(self, left_expr, right_expr) 521 522 @classmethod 523 def _op_symbol(cls): 524 return '%' 525 526 @classmethod 527 def _binary_func(cls, x, y): 528 try: 529 return math.fmod(x, y) 530 except ValueError: # Raised by calling math.fmod(x, 0.0) 531 raise EvalError('%f %% %f [math.fmod error]' % (x, y)) 532 533 def build_python_expr(self): 534 return 'math.fmod(%s, %s)' % (self._left_expr.build_python_expr(), 535 self._right_expr.build_python_expr()) 536 537 def build_cc_expr(self): 538 return 'fmod(%s, %s)' % (self._left_expr.build_cc_expr(), 539 self._right_expr.build_cc_expr()) 540 541 542class RandomExprBuilder(object): 543 """Random expression tree builder. 544 545 Randomly builds an expression tree using recursive calls. 546 547 Attributes: 548 _max_abs_val: maximum absolute values of each number in expression. 549 _factories: a list of factories used to constract expression nodes. 550 """ 551 def __init__(self, max_abs_val): 552 self._max_abs_val = max_abs_val 553 554 # Default factory is only self._build_expr, which means that only number 555 # nodes are generated; see the implementation of self._build_expr. 556 self._factories = [lambda n: self._build_expr(n)] 557 558 def add_operators(self, string): 559 """Adds operators for node candidates. 560 561 For example, to generate expressions with four arithmetic operations (+, 562 -, *, /), call this method like: builder.add_operators('add,sub,mul,div') 563 564 Arg: 565 string: operator names, each separated by comma, without spaces. The 566 correspondence between operators and their names are as follows: 567 group: (expr) 568 pos: +expr 569 neg: -expr 570 add: expr1 + expr2 571 sub: expr1 - expr2 572 mul: expr1 * expr2 573 div: expr1 / expr2 574 pow: expr1 ^ expr2 575 mod: expr1 % expr2 576 """ 577 factories = {'group': lambda n: Group(self._build_expr(n)), 578 'pos': lambda n: PositiveSign(self._build_expr(n)), 579 'neg': lambda n: Negation(self._build_expr(n)), 580 'add': lambda n: Addition(self._build_expr(n), 581 self._build_expr(n)), 582 'sub': lambda n: Subtraction(self._build_expr(n), 583 self._build_expr(n)), 584 'mul': lambda n: Multiplication(self._build_expr(n), 585 self._build_expr(n)), 586 'div': lambda n: Division(self._build_expr(n), 587 self._build_expr(n)), 588 'pow': lambda n: Power(self._build_expr(n), 589 self._build_expr(n)), 590 'mod': lambda n: Modulo(self._build_expr(n), 591 self._build_expr(n))} 592 for op in string.split(','): 593 self._factories.append(factories[op]) 594 595 def build(self, max_depth): 596 """Builds a random expression tree. 597 598 This method generates only those expressions that include at least one 599 operator, because mozc doesn't calculates expressions without operator, 600 e.g. (123)=. 601 602 Arg: 603 max_depth: the maximum possible height of tree. 604 """ 605 for i in range(100): 606 expr = self._build_expr(max_depth) 607 if expr.contains_operator(): 608 return expr 609 else: 610 raise FatalError('Failed to build expression containing ' 611 'at least one operator many times') 612 613 def _build_expr(self, max_depth): 614 """Implementation of recursive tree construction algorithm.""" 615 if max_depth == 0: # Leaf 616 if random.randint(0, 1) == 0: 617 return Integer(random.randint(-self._max_abs_val, self._max_abs_val)) 618 else: 619 return Float(random.uniform(-self._max_abs_val, self._max_abs_val)) 620 621 # Select a node factory at random and generate childs. 622 factory = random.choice(self._factories) 623 return factory(max_depth - 1) 624 625 626class TestCaseGenerator(object): 627 """Test case generator for expression trees. Generates test cases for 628 expressions by mixinig japanese fonts to expressions. 629 630 Attributes: 631 _filename: filename of output file 632 _file: file object to which test cases are written. 633 _num_total_cases: total number of written expressions. 634 _num_computable_cases: number of computable expressions. 635 """ 636 637 # Character map used to generate test expression including Japanese. 638 _EQUIVALENT_CHARS = {'+': ['+', '+'], 639 '-': ['-', '−', 'ー'], 640 '*': ['*', '*'], 641 '/': ['/', '/', '・'], 642 '^': ['^'], 643 '%': ['%', '%'], 644 '(': ['(', '('], 645 ')': [')', ')'], 646 '0': ['0', '0'], 647 '1': ['1', '1'], 648 '2': ['2', '2'], 649 '3': ['3', '3'], 650 '4': ['4', '4'], 651 '5': ['5', '5'], 652 '6': ['6', '6'], 653 '7': ['7', '7'], 654 '8': ['8', '8'], 655 '9': ['9', '9']} 656 657 def __init__(self, test_filename, py_filename = '', cc_filename = ''): 658 """ 659 Arg: 660 filename: output file. When it's empty, generates nothing. 661 """ 662 self._num_total_cases = 0 663 self._num_computable_cases = 0 664 665 # Initialize output file 666 self._test_filename = test_filename 667 if test_filename: 668 self._test_file = open(test_filename, 'w', encoding='utf-8') 669 else: 670 # Replace the generating function by a dummy 671 self.add_test_case_for = lambda expr: None 672 self._test_file = None 673 674 # Initialize python code 675 if py_filename: 676 self._py_file = open(py_filename, 'w', encoding='utf-8') 677 self._py_file.write('import math\n\n') 678 else: 679 self._add_py_code_for = lambda py_expr, expected: None 680 self._py_file = None 681 682 # Initialize cc code 683 if cc_filename: 684 self._cc_file = open(cc_filename, 'w', encoding='utf-8') 685 self._cc_file.write('// Automatically generated by ' 686 'mozc/src/data/test/calculator/gen_test.py\n\n' 687 '#include <cmath>\n' 688 '#include <iostream>\n' 689 '#include <string>\n\n' 690 'using namespace std;\n\n') 691 else: 692 # Replace the generating function by a dummy 693 self._add_cc_code_for = lambda cc_expr, expectecd: None 694 self._cc_file = None 695 696 def __del__(self): 697 if self._test_file: 698 self._test_file.close() 699 logging.info('%d test cases were written to %s, ' 700 'of which %d can be calculated.', 701 self._num_total_cases, self._test_filename, 702 self._num_computable_cases) 703 704 if self._py_file: 705 self._py_file.close() 706 707 if self._cc_file: 708 self._cc_file.write('int main(int, char**) {\n') 709 for i in range(self._num_total_cases): 710 self._cc_file.write(' test%d();\n' % i) 711 self._cc_file.write(' return 0;\n' 712 '}\n') 713 self._cc_file.close() 714 715 @staticmethod 716 def _mix_japanese_string(string): 717 """Randomly transforms half-width characters to full-width.""" 718 result = '' 719 for char in string: 720 if char in TestCaseGenerator._EQUIVALENT_CHARS: 721 equiv_chars = TestCaseGenerator._EQUIVALENT_CHARS[char] 722 result += random.choice(equiv_chars) 723 else: 724 result += char 725 return result 726 727 def add_test_case_for(self, expr): 728 """Appends the code that checks whether the evaluation result of given 729 expr coincides with the expected result. 730 731 Args: 732 expr: Expr object 733 """ 734 test_expr = self._mix_japanese_string(expr.build_test_expr()) 735 try: 736 # Raises an exceeption on failure, like divison-by-zero, etc. 737 value = expr.eval() 738 739 # If the above evaluation was a success, the same value should be 740 # calculated by python's eval. This check should be done in absolute 741 # error because the script runs on the same machine. 742 py_expr = expr.build_python_expr() 743 py_value = eval(py_expr) 744 if not (abs(value - py_value) < 1e-8): 745 logging.critical('Calculation differs from python: %f != %f (python)\n' 746 'test: %s\n' 747 ' py: %s', value, py_value, test_expr, py_expr) 748 raise FatalError('Expression tree evaluation error') 749 750 self._num_computable_cases += 1 751 self._test_file.write('%s=%.8g\n' % (test_expr, value)) 752 self._add_py_code_for(py_expr, value) 753 self._add_cc_code_for(expr.build_cc_expr(), value) 754 except EvalError: 755 self._test_file.write('%s=\n' % test_expr) 756 self._add_cc_code_for(expr.build_cc_expr(), None) 757 758 self._num_total_cases += 1 759 760 def _add_py_code_for(self, py_expr, expected): 761 """Appends python code that checks whether the evaluation result of given 762 expr coincides with the expected result. 763 764 If expected is None, it indicates that the evaluation of expr results in 765 error (like overflow and division-by-zero). Currently, just generates 766 comments for such cases. 767 768 In generated script, the accuracy is verified either in absolute error or 769 relative error, because there's a possibility that different machines 770 generate different values due to precision. For example, if the expected 771 value is very large, we cannot expect that error is less than a certain 772 small threshold. In this case, however, the relative error would work. 773 774 Args: 775 py_expr: string of python expression. 776 expected: expected value of the expression (float) 777 """ 778 if expected: 779 self._py_file.write('expr = "%s"\n' % py_expr) 780 self._py_file.write('expected = %s\n' % repr(expected)) 781 self._py_file.write('val = eval(expr)\n') 782 self._py_file.write('err = abs(val - expected)\n') 783 self._py_file.write('if (err > 1e-8 and\n') 784 self._py_file.write(' err > 1e-2 * abs(expected)):\n') 785 self._py_file.write(' print("%r != %r" % (val, expected))\n') 786 self._py_file.write(' print("expr = %s" % expr)\n\n') 787 else: 788 self._py_file.write('# Incomputable\n' 789 '# %s\n\n' % py_expr) 790 791 def _add_cc_code_for(self, cc_expr, expected): 792 """Appends the code that checks whether the evaluation result of given 793 expr coincides with the expected result. 794 795 If expected is None, it indicates that the evaluation of expr results in 796 error (like overflow and division-by-zero). Currently, just generates 797 comments for such cases. 798 799 In generated code, the accuracy is verified either in absolute error or 800 relative error; see _add_py_code_for for details. 801 802 Args: 803 cc_expr: string of C++ expression. 804 expected: expected value of the expression (float) 805 """ 806 self._cc_file.write('void test%d() {\n' % self._num_total_cases) 807 if expected: 808 self._cc_file.write(' const string expr = string("%s");\n' % cc_expr) 809 self._cc_file.write(' const double expected = %s;\n' % repr(expected)) 810 self._cc_file.write(' const double val = %s;\n' % cc_expr) 811 self._cc_file.write(' const double err = abs(val - expected);\n') 812 self._cc_file.write(' if (err > 1e-8 || err > 1e-2 * abs(expected))\n') 813 self._cc_file.write(' cerr << val << " != " << expected\n') 814 self._cc_file.write(' << "expr = " << expr << endl;\n') 815 else: 816 self._cc_file.write(' // Incomputable\n' 817 ' // %s\n' % cc_expr) 818 self._cc_file.write('}\n\n') 819 820 821def parse_options(): 822 parser = optparse.OptionParser() 823 parser.add_option('--size', type = 'int', dest = 'size', default = 100, 824 metavar = 'NUM', help = 'Number of tests to be generated') 825 parser.add_option('--max_depth', type = 'int', dest = 'max_depth', 826 default = 5, metavar = 'NUM', 827 help = 'Max depth of equation tree (default = 5)') 828 parser.add_option('--max_abs', type = 'float', dest = 'max_abs', 829 default = 1e+4, metavar = 'FLOAT', 830 help = 'Max absolute value of each number (default = 1e+4)') 831 parser.add_option('--operators', dest = 'operators', metavar = 'OPs', 832 default = 'group,pos,neg,add,sub,mul,div,pow,mod', 833 help = 'Operators used by expression generator') 834 parser.add_option('--test_output', dest = 'test_output', 835 default = '', metavar = 'FILE', 836 help = 'Output test data file') 837 parser.add_option('--py_output', dest = 'py_output', 838 default = '', metavar = 'FILE', 839 help = 'Output python script for verification (optional)') 840 parser.add_option('--cc_output', dest = 'cc_output', 841 default = '', metavar = 'FILE', 842 help = 'Output C++ src for verification (optional)') 843 options, args = parser.parse_args() 844 845 if not options.test_output: 846 logging.error('--test_output is empty') 847 sys.exit(-1) 848 849 return options 850 851 852def main(): 853 random.seed() 854 logging.basicConfig(level = logging.INFO, 855 format = '%(levelname)s: %(message)s') 856 options = parse_options() 857 858 if not options.test_output: 859 logging.error('--test_output is empty') 860 sys.exit(-1) 861 862 builder = RandomExprBuilder(options.max_abs) 863 builder.add_operators(options.operators) 864 test_case_generator = TestCaseGenerator(options.test_output, 865 options.py_output, 866 options.cc_output) 867 868 for i in range(options.size): 869 expr = builder.build(options.max_depth) 870 test_case_generator.add_test_case_for(expr) 871 872 873if __name__ == '__main__': 874 main() 875