src/etc/test-float-parse/runtests.py

   1 #!/usr/bin/env python2.7
   2 #
   3 # Copyright 2015 The Rust Project Developers. See the COPYRIGHT
   4 # file at the top-level directory of this distribution and at
   5 # http://rust-lang.org/COPYRIGHT.
   6 #
   7 # Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   8 # http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   9 # <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
  10 # option. This file may not be copied, modified, or distributed
  11 # except according to those terms.
  12
  13 """
  14 Testing dec2flt
  15 ===============
  16 These are *really* extensive tests. Expect them to run for hours. Due to the
  17 nature of the problem (the input is a string of arbitrary length), exhaustive
  18 testing is not really possible. Instead, there are exhaustive tests for some
  19 classes of inputs for which that is feasible and a bunch of deterministic and
  20 random non-exhaustive tests for covering everything else.
  21
  22 The actual tests (generating decimal strings and feeding them to dec2flt) is
  23 performed by a set of stand-along rust programs. This script compiles, runs,
  24 and supervises them. The programs report the strings they generate and the
  25 floating point numbers they converted those strings to, and this script
  26 checks that the results are correct.
  27
  28 You can run specific tests rather than all of them by giving their names
  29 (without .rs extension) as command line parameters.
  30
  31 Verification
  32 ------------
  33 The tricky part is not generating those inputs but verifying the outputs.
  34 Comparing with the result of Python's float() does not cut it because
  35 (and this is apparently undocumented) although Python includes a version of
  36 Martin Gay's code including the decimal-to-float part, it doesn't actually use
  37 it for float() (only for round()) instead relying on the system scanf() which
  38 is not necessarily completely accurate.
  39
  40 Instead, we take the input and compute the true value with bignum arithmetic
  41 (as a fraction, using the ``fractions`` module).
  42
  43 Given an input string and the corresponding float computed via Rust, simply
  44 decode the float into f * 2^k (for integers f, k) and the ULP.
  45 We can now easily compute the error and check if it is within 0.5 ULP as it
  46 should be. Zero and infinites are handled similarly:
  47
  48 - If the approximation is 0.0, the exact value should be *less or equal*
  49   half the smallest denormal float: the smallest denormal floating point
  50   number has an odd mantissa (00...001) and thus half of that is rounded
  51   to 00...00, i.e., zero.
  52 - If the approximation is Inf, the exact value should be *greater or equal*
  53   to the largest finite float + 0.5 ULP: the largest finite float has an odd
  54   mantissa (11...11), so that plus half an ULP is rounded up to the nearest
  55   even number, which overflows.
  56
  57 Implementation details
  58 ----------------------
  59 This directory contains a set of single-file Rust programs that perform
  60 tests with a particular class of inputs. Each is compiled and run without
  61 parameters, outputs (f64, f32, decimal) pairs to verify externally, and
  62 in any case either exits gracefully or with a panic.
  63
  64 If a test binary writes *anything at all* to stderr or exits with an
  65 exit code that's not 0, the test fails.
  66 The output on stdout is treated as (f64, f32, decimal) record, encoded thusly:
  67
  68 - First, the bits of the f64 encoded as an ASCII hex string.
  69 - Second, the bits of the f32 encoded as an ASCII hex string.
  70 - Then the corresponding string input, in ASCII
  71 - The record is terminated with a newline.
  72
  73 Incomplete records are an error. Not-a-Number bit patterns are invalid too.
  74
  75 The tests run serially but the validation for a single test is parallelized
  76 with ``multiprocessing``. Each test is launched as a subprocess.
  77 One thread supervises it: Accepts and enqueues records to validate, observe
  78 stderr, and waits for the process to exit. A set of worker processes perform
  79 the validation work for the outputs enqueued there. Another thread listens
  80 for progress updates from the workers.
  81
  82 Known issues
  83 ------------
  84 Some errors (e.g., NaN outputs) aren't handled very gracefully.
  85 Also, if there is an exception or the process is interrupted (at least on
  86 Windows) the worker processes are leaked and stick around forever.
  87 They're only a few megabytes each, but still, this script should not be run
  88 if you aren't prepared to manually kill a lot of orphaned processes.
  89 """
  90 from __future__ import print_function
  91 import sys
  92 import os.path
  93 import time
  94 import struct
  95 from fractions import Fraction
  96 from collections import namedtuple
  97 from subprocess import Popen, check_call, PIPE
  98 from glob import glob
  99 import multiprocessing
 100 import threading
 101 import ctypes
 102 import binascii
 103
 104 try:  # Python 3
 105     import queue as Queue
 106 except ImportError:  # Python 2
 107     import Queue
 108
 109 NUM_WORKERS = 2
 110 UPDATE_EVERY_N = 50000
 111 INF = namedtuple('INF', '')()
 112 NEG_INF = namedtuple('NEG_INF', '')()
 113 ZERO = namedtuple('ZERO', '')()
 114 MAILBOX = None  # The queue for reporting errors to the main process.
 115 STDOUT_LOCK = threading.Lock()
 116 test_name = None
 117 child_processes = []
 118 exit_status = 0
 119
 120 def msg(*args):
 121     with STDOUT_LOCK:
 122         print("[" + test_name + "]", *args)
 123         sys.stdout.flush()
 124
 125
 126 def write_errors():
 127     global exit_status
 128     f = open("errors.txt", 'w')
 129     have_seen_error = False
 130     while True:
 131         args = MAILBOX.get()
 132         if args is None:
 133             f.close()
 134             break
 135         print(*args, file=f)
 136         f.flush()
 137         if not have_seen_error:
 138             have_seen_error = True
 139             msg("Something is broken:", *args)
 140             msg("Future errors logged to errors.txt")
 141             exit_status = 101
 142
 143
 144 def rustc(test):
 145     rs = test + '.rs'
 146     exe = test + '.exe'  # hopefully this makes it work on *nix
 147     print("compiling", test)
 148     sys.stdout.flush()
 149     check_call(['rustc', rs, '-o', exe])
 150
 151
 152 def run(test):
 153     global test_name
 154     test_name = test
 155
 156     t0 = time.clock()
 157     msg("setting up supervisor")
 158     exe = test + '.exe'
 159     proc = Popen(exe, bufsize=1<<20 , stdin=PIPE, stdout=PIPE, stderr=PIPE)
 160     done = multiprocessing.Value(ctypes.c_bool)
 161     queue = multiprocessing.Queue(maxsize=5)#(maxsize=1024)
 162     workers = []
 163     for n in range(NUM_WORKERS):
 164         worker = multiprocessing.Process(name='Worker-' + str(n + 1),
 165                                          target=init_worker,
 166                                          args=[test, MAILBOX, queue, done])
 167         workers.append(worker)
 168         child_processes.append(worker)
 169     for worker in workers:
 170         worker.start()
 171     msg("running test")
 172     interact(proc, queue)
 173     with done.get_lock():
 174         done.value = True
 175     for worker in workers:
 176         worker.join()
 177     msg("python is done")
 178     assert queue.empty(), "did not validate everything"
 179     dt = time.clock() - t0
 180     msg("took", round(dt, 3), "seconds")
 181
 182
 183 def interact(proc, queue):
 184     n = 0
 185     while proc.poll() is None:
 186         line = proc.stdout.readline()
 187         if not line:
 188             continue
 189         assert line.endswith('\n'), "incomplete line: " + repr(line)
 190         queue.put(line)
 191         n += 1
 192         if n % UPDATE_EVERY_N == 0:
 193             msg("got", str(n // 1000) + "k", "records")
 194     msg("rust is done. exit code:", proc.returncode)
 195     rest, stderr = proc.communicate()
 196     if stderr:
 197         msg("rust stderr output:", stderr)
 198     for line in rest.split('\n'):
 199         if not line:
 200             continue
 201         queue.put(line)
 202
 203
 204 def main():
 205     global MAILBOX
 206     tests = [os.path.splitext(f)[0] for f in glob('*.rs')
 207                                     if not f.startswith('_')]
 208     whitelist = sys.argv[1:]
 209     if whitelist:
 210         tests = [test for test in tests if test in whitelist]
 211     if not tests:
 212         print("Error: No tests to run")
 213         sys.exit(1)
 214     # Compile first for quicker feedback
 215     for test in tests:
 216         rustc(test)
 217     # Set up mailbox once for all tests
 218     MAILBOX = multiprocessing.Queue()
 219     mailman = threading.Thread(target=write_errors)
 220     mailman.daemon = True
 221     mailman.start()
 222     for test in tests:
 223         if whitelist and test not in whitelist:
 224             continue
 225         run(test)
 226     MAILBOX.put(None)
 227     mailman.join()
 228
 229
 230 # ---- Worker thread code ----
 231
 232
 233 POW2 = { e: Fraction(2) ** e for e in range(-1100, 1100) }
 234 HALF_ULP = { e: (Fraction(2) ** e)/2 for e in range(-1100, 1100) }
 235 DONE_FLAG = None
 236
 237
 238 def send_error_to_supervisor(*args):
 239     MAILBOX.put(args)
 240
 241
 242 def init_worker(test, mailbox, queue, done):
 243     global test_name, MAILBOX, DONE_FLAG
 244     test_name = test
 245     MAILBOX = mailbox
 246     DONE_FLAG = done
 247     do_work(queue)
 248
 249
 250 def is_done():
 251     with DONE_FLAG.get_lock():
 252         return DONE_FLAG.value
 253
 254
 255 def do_work(queue):
 256     while True:
 257         try:
 258             line = queue.get(timeout=0.01)
 259         except Queue.Empty:
 260             if queue.empty() and is_done():
 261                 return
 262             else:
 263                 continue
 264         bin64, bin32, text = line.rstrip().split()
 265         validate(bin64, bin32, text)
 266
 267
 268 def decode_binary64(x):
 269     """
 270     Turn a IEEE 754 binary64 into (mantissa, exponent), except 0.0 and
 271     infinity (positive and negative), which return ZERO, INF, and NEG_INF
 272     respectively.
 273     """
 274     x = binascii.unhexlify(x)
 275     assert len(x) == 8, repr(x)
 276     [bits] = struct.unpack(b'>Q', x)
 277     if bits == 0:
 278         return ZERO
 279     exponent = (bits >> 52) & 0x7FF
 280     negative = bits >> 63
 281     low_bits = bits & 0xFFFFFFFFFFFFF
 282     if exponent == 0:
 283         mantissa = low_bits
 284         exponent += 1
 285         if mantissa == 0:
 286             return ZERO
 287     elif exponent == 0x7FF:
 288         assert low_bits == 0, "NaN"
 289         if negative:
 290             return NEG_INF
 291         else:
 292             return INF
 293     else:
 294         mantissa = low_bits | (1 << 52)
 295     exponent -= 1023 + 52
 296     if negative:
 297         mantissa = -mantissa
 298     return (mantissa, exponent)
 299
 300
 301 def decode_binary32(x):
 302     """
 303     Turn a IEEE 754 binary32 into (mantissa, exponent), except 0.0 and
 304     infinity (positive and negative), which return ZERO, INF, and NEG_INF
 305     respectively.
 306     """
 307     x = binascii.unhexlify(x)
 308     assert len(x) == 4, repr(x)
 309     [bits] = struct.unpack(b'>I', x)
 310     if bits == 0:
 311         return ZERO
 312     exponent = (bits >> 23) & 0xFF
 313     negative = bits >> 31
 314     low_bits = bits & 0x7FFFFF
 315     if exponent == 0:
 316         mantissa = low_bits
 317         exponent += 1
 318         if mantissa == 0:
 319             return ZERO
 320     elif exponent == 0xFF:
 321         if negative:
 322             return NEG_INF
 323         else:
 324             return INF
 325     else:
 326         mantissa = low_bits | (1 << 23)
 327     exponent -= 127 + 23
 328     if negative:
 329         mantissa = -mantissa
 330     return (mantissa, exponent)
 331
 332
 333 MIN_SUBNORMAL_DOUBLE = Fraction(2) ** -1074
 334 MIN_SUBNORMAL_SINGLE = Fraction(2) ** -149  # XXX unsure
 335 MAX_DOUBLE = (2 - Fraction(2) ** -52) * (2 ** 1023)
 336 MAX_SINGLE = (2 - Fraction(2) ** -23) * (2 ** 127)
 337 MAX_ULP_DOUBLE = 1023 - 52
 338 MAX_ULP_SINGLE = 127 - 23
 339 DOUBLE_ZERO_CUTOFF = MIN_SUBNORMAL_DOUBLE / 2
 340 DOUBLE_INF_CUTOFF = MAX_DOUBLE + 2 ** (MAX_ULP_DOUBLE - 1)
 341 SINGLE_ZERO_CUTOFF = MIN_SUBNORMAL_SINGLE / 2
 342 SINGLE_INF_CUTOFF = MAX_SINGLE + 2 ** (MAX_ULP_SINGLE - 1)
 343
 344 def validate(bin64, bin32, text):
 345     double = decode_binary64(bin64)
 346     single = decode_binary32(bin32)
 347     real = Fraction(text)
 348
 349     if double is ZERO:
 350         if real > DOUBLE_ZERO_CUTOFF:
 351             record_special_error(text, "f64 zero")
 352     elif double is INF:
 353         if real < DOUBLE_INF_CUTOFF:
 354             record_special_error(text, "f64 inf")
 355     elif double is NEG_INF:
 356         if -real < DOUBLE_INF_CUTOFF:
 357             record_special_error(text, "f64 -inf")
 358     elif len(double) == 2:
 359         sig, k = double
 360         validate_normal(text, real, sig, k, "f64")
 361     else:
 362         assert 0, "didn't handle binary64"
 363     if single is ZERO:
 364         if real > SINGLE_ZERO_CUTOFF:
 365             record_special_error(text, "f32 zero")
 366     elif single is INF:
 367         if real < SINGLE_INF_CUTOFF:
 368             record_special_error(text, "f32 inf")
 369     elif single is NEG_INF:
 370         if -real < SINGLE_INF_CUTOFF:
 371             record_special_error(text, "f32 -inf")
 372     elif len(single) == 2:
 373         sig, k = single
 374         validate_normal(text, real, sig, k, "f32")
 375     else:
 376         assert 0, "didn't handle binary32"
 377
 378 def record_special_error(text, descr):
 379     send_error_to_supervisor(text.strip(), "wrongly rounded to", descr)
 380
 381
 382 def validate_normal(text, real, sig, k, kind):
 383     approx = sig * POW2[k]
 384     error = abs(approx - real)
 385     if error > HALF_ULP[k]:
 386         record_normal_error(text, error, k, kind)
 387
 388
 389 def record_normal_error(text, error, k, kind):
 390     one_ulp = HALF_ULP[k + 1]
 391     assert one_ulp == 2 * HALF_ULP[k]
 392     relative_error = error / one_ulp
 393     text = text.strip()
 394     try:
 395         err_repr = float(relative_error)
 396     except ValueError:
 397         err_repr = str(err_repr).replace('/', ' / ')
 398     send_error_to_supervisor(err_repr, "ULP error on", text, "(" + kind + ")")
 399
 400
 401 if __name__ == '__main__':
 402     main()