davidlehn/forge-issue-428-check-cli.js

## forge-issue-428-check-cli.js
/*
 * JavaScriptCore Loop Optimization Bug Test
 *
 * This test reveals an optimization bug in simple deterministic variable
 * assignment within an inner loop. After many iterations the result will no
 * longer be correct.
 *
 * This code runs on the command line with the 'jsc' tool.
 *
 * The initial failure was within hashing functions implementation:
 *   https://github.com/digitalbazaar/forge/issues/428
 *
 * The bug was assumed to be related to a math, shifting, or overflow bug. But
 * further reduction got it down to rotation of data between variables. A magic
 * ">>>" operation or similar on one var can often "fix" the optimization bug.
 * Further reduction got it down to basic two variable swap code failing. Both
 * swapping with a temporary var and with a destructuring expression can fail.
 *
 * Attempted test data as of latest builds and code on 2016-10-31:
 *
 * Passes:
 *   WebKit/JavaScriptCore jsc (linux - i386/32b)
 *   nodejs (any)
 *
 * Fails:
 *   WebKit/JavaScriptCore jsc (mac/linux - x86-64/64b)
 *
 * Authors:
 *   David I. Lehn <dlehn@digitalbazaar.com>
 *   Dave Longley <dlongley@digitalbazaar.com>
 */
var debug = debug || console.log;
// use values high enough for optimizer to run
// usually fails around the same number of inner loops
var test_max = 50000;
var outer_max = 2000;
// use at least 2 inner loops
var inner_max = 2;

// inner loop count
var count = 0;
var test, outer;
for(test = 0; test < test_max; ++test) {
  _test();
}
debug('PASS');

function _status(status, values) {
  debug(
    status +
    ' test:' + (test + 1) +
    ' outer:' + (outer + 1) + '/' + outer_max +
    ' count:' + count +
    (values ? ' values:' + values.join('') : ''));
}

function _test() {
  for(outer = 0; outer < outer_max; ++outer) {
    // var and let fail in or out of loop
    // moving outside of function works.
    var t, a, b;
    // fails with at least ints and bools
    // also fails when shifting [a,b,...,M,N] = [N,a,b,...,M]
    // simple 2 var swap done here as minimal test case
    a = 1;
    b = 0;

    // at least 2 swaps in an inner loop required.
    // manually unrolling avoids bug.
    for(var inner = 0; inner < inner_max; ++inner) {
      //t = b; b = a; a = t;
      t = b;
      b = a;
      // do one of the following to avoid optimization bug:
      // b = b & -1; // FIX
      // b = b >>> 0; // FIX
      // other operations will not avoid optimization bug:
      // b = b + 0; // FAILS
      // b = b * 1; // FAILS
      a = t;
      // also fails with destructuring expression vs above vars
      //[a,b] = [b,a];
      count++;
    }

    // check
    if((inner % 2 === 0 && !(a === 1 && b === 0)) ||
       (inner % 2 === 1 && !(a === 0 && b === 1))) {
      _status('FAIL', [a, b]);
      throw 'FAIL';
    }
    // progress
    //_status('....', [a, b]);
    if((test + 1) % 100 === 0 && (outer + 1) === outer_max) {
      _status('....', [a, b]);
    }
  }
}

## forge-issue-428-check-swap.html
<html>
  <head>
    <title>Safari 10.0.1 Loop Optimization Bug Test</title>
  </head>

  <body>
    <h1>Safari 10.0.1 Loop Optimization Bug Test</h1>

    <p>This test reveals an optimization bug. A deterministic function
    is run in a loop. The test stops when an incorrect result is found.
    Once a failure is found, reload the page to test again.</p>

    <hr/>

    <input type="button" value="Stop" onclick="stop()">
    <div>Test: <span id="test">...</span></div>
    <div>Outer Loop <span id="outer">...</span></div>
    <div>Count <span id="count">...</span></div>
    <div>First <span id="first">...</span></div>
    <div>Last <span id="last">...</span></div>
    <div>Status <span id="status">...</span></div>

    <hr/>

    <p>Attempted test data as of latest builds and code on 2016-10-31:</p>

    <p>Passes:</p>
    <ul>
      <li>Chrome, Firefox, Safari before 10.x (all platforms)</li>
      <li>Safari 10.0.1 mac/64b with debug console open</li>
      <li>WebKit/JavaScriptCore / jsc (linux - i386/32b)</li>
    </ul>
    <p>Fails:</p>
    <ul>
      <li>Safari 10.0.1 (mac/64b)</li>
      <li>Safari tech preview v16 (mac/64b)</li>
      <li>WebKit/JavaScriptCore / jsc (mac/linux - x86-64/64b)</li>
    </ul>

    <p>Authors:</p>
    <ul>
      <li>David I. Lehn &lt;<a href="mailto:dlehn@digitalbazaar.com">dlehn@digitalbazaar.com</a>&gt;</li>
      <li>Dave Longley &lt;<a href="mailto:dlongley@digitalbazaar.com">dlongley@digitalbazaar.com</a>&gt;</li>
    </ul>

    <script>
var run = true;
var first = null;
// use values high enough for optimizer to run
// usually fails around the same number of inner loops
var test_max = 50000;
var outer_max = 500;
// use at least 2 inner loops
var inner_max = 2;
// inner loop count
var count = 0;
var test = 0;
var outer, inner;
function stop() {
  run = false;
}
function _loop() {
  if(run && test < test_max) {
    if(_test()) {
      test++;
      setTimeout(_loop, 0);
    }
  }
}
setTimeout(_loop, 0);

function _status(status, values) {
  document.getElementById('status').innerHTML = status;
  document.getElementById('test').innerHTML = test + 1;
  document.getElementById('outer').innerHTML = (outer + 1) + '/' + outer_max;
  document.getElementById('count').innerHTML = count;
  document.getElementById('first').innerHTML = first.join('');
  document.getElementById('last').innerHTML = values.join('');
}

function _test() {
  for(outer = 0; outer < outer_max; ++outer) {
    var t, a, b;

    a = 1;
    b = 0;

    // loop required.  manually unrolling avoids bug.
    for(var inner = 0; inner < inner_max; ++inner) {
      t = b;
      b = a;
      // do one of the following to avoid optimization bug:
      // b = b & -1; // FIX
      // b = b >>> 0; // FIX
      // other operations will not avoid optimization bug:
      // b = b + 0; // FAILS
      // b = b * 1; // FAILS
      a = t;
      count++;
    }

    if(first === null) {
      first = [a, b];
    }
    // check
    if((inner % 2 === 0 && !(a === 1 && b === 0)) ||
       (inner % 2 === 1 && !(a === 0 && b === 1))) {
      _status('FAIL', [a, b]);
      return false;
    }
    // progress
    //_status('....', [a, b]);
    if((test + 1) % 100 === 0 && (outer + 1) === outer_max) {
      _status('...', [a, b]);
    }
  }
  return true;
}
    </script>
  </body>
</html>

## forge-issue-428-check.html
<html>

  <head>
    <title>Safari 10 Optimization Bug</title>
  </head>

  <body>
    <h1>Safari 10 Optimization Bug</h1>

    <p>This test reveals an optimization bug in Safari 10. A
      deterministic function is run in a loop. Its first return
      value is stored and printed to the screen. If any subsequent
      turn of the loop produces a different return value, the
      test exits immediately and prints the different value.
    </p>
    <p>This test passes successfully on Chrome, Firefox, and
      early versions of Safari (less than v10). It fails on
      Safari 10. You may need to refresh the page a few times
      to get a failure, but it typically fails every time.
    </p>

    <input type="button" value="Stop" onclick="stop()">
    <div>Attempt: <span id="iteration">...</span></div>
    <div>First result is <span id="expected">...</span></div>
    <div>Final result
      <span id="result">matches first result.<br>
        <span style="color: green">SUCCESS!</span></span>
    </div>

    <script>
var run = true;
var expected;
var attempt = 0;
var attempts = 5000;
var iterations = 500;
function stop() {
  run = false;
}
function _check() {
  if(run && attempt < attempts) {
    if(_runTest(attempt, iterations)) {
      attempt++;
      setTimeout(_check, 0);
    }
  }
}
setTimeout(_check, 0);

function _runTest(attempt, max) {
  function _status(itr) {
    document.getElementById('iteration').innerHTML =
      (attempt + 1) + ', Iteration ' + (itr + 1) + ' / ' + max;
  }
  for(var itr = 0; itr < max; ++itr) {
    var s = {
      a: 0,
      b: 0,
      c: 1
    };
    var t, a, b, c;

    a = s.a;
    b = s.b;
    c = s.c;

    // loop required.  manually unrolling avoids bug.
    for(var j = 0; j < 2; ++j) {
      t = c;
      c = b;
      // uncommenting line below with `>>> 0` will avoid the bug
      //c = c >>> 0;
      b = a;
      a = t;
    }

    s.a = a;
    s.b = b;
    s.c = c;

    // compute the result
    var result = [s.a, s.b, s.c].join('');
    // display and result comparison
    if((attempt + 1) % 100 === 0) {
      _status(itr);
    }
    if(attempt === 0 && itr === 0) {
      expected = result;
      document.getElementById('expected').innerHTML = expected;
    } else if(result !== expected) {
      var output = {iteration: itr, result: result};
      _status(itr);
      document.getElementById('result').innerHTML =
        ' is ' + output.result + '<br>' +
        '<span style="color: red">FAILURE!</span> ' +
        'Final result does not match first result.';
      return false;
    }
  }

  return true;
}
    </script>

  </body>

</html>
	/*
	* JavaScriptCore Loop Optimization Bug Test
	*
	* This test reveals an optimization bug in simple deterministic variable
	* assignment within an inner loop. After many iterations the result will no
	* longer be correct.
	*
	* This code runs on the command line with the 'jsc' tool.
	*
	* The initial failure was within hashing functions implementation:
	* https://github.com/digitalbazaar/forge/issues/428
	*
	* The bug was assumed to be related to a math, shifting, or overflow bug. But
	* further reduction got it down to rotation of data between variables. A magic
	* ">>>" operation or similar on one var can often "fix" the optimization bug.
	* Further reduction got it down to basic two variable swap code failing. Both
	* swapping with a temporary var and with a destructuring expression can fail.
	*
	* Attempted test data as of latest builds and code on 2016-10-31:
	*
	* Passes:
	* WebKit/JavaScriptCore jsc (linux - i386/32b)
	* nodejs (any)
	*
	* Fails:
	* WebKit/JavaScriptCore jsc (mac/linux - x86-64/64b)
	*
	* Authors:
	* David I. Lehn <dlehn@digitalbazaar.com>
	* Dave Longley <dlongley@digitalbazaar.com>
	*/
	var debug = debug \|\| console.log;
	// use values high enough for optimizer to run
	// usually fails around the same number of inner loops
	var test_max = 50000;
	var outer_max = 2000;
	// use at least 2 inner loops
	var inner_max = 2;

	// inner loop count
	var count = 0;
	var test, outer;
	for(test = 0; test < test_max; ++test) {
	_test();
	}
	debug('PASS');

	function _status(status, values) {
	debug(
	status +
	' test:' + (test + 1) +
	' outer:' + (outer + 1) + '/' + outer_max +
	' count:' + count +
	(values ? ' values:' + values.join('') : ''));
	}

	function _test() {
	for(outer = 0; outer < outer_max; ++outer) {
	// var and let fail in or out of loop
	// moving outside of function works.
	var t, a, b;
	// fails with at least ints and bools
	// also fails when shifting [a,b,...,M,N] = [N,a,b,...,M]
	// simple 2 var swap done here as minimal test case
	a = 1;
	b = 0;

	// at least 2 swaps in an inner loop required.
	// manually unrolling avoids bug.
	for(var inner = 0; inner < inner_max; ++inner) {
	//t = b; b = a; a = t;
	t = b;
	b = a;
	// do one of the following to avoid optimization bug:
	// b = b & -1; // FIX
	// b = b >>> 0; // FIX
	// other operations will not avoid optimization bug:
	// b = b + 0; // FAILS
	// b = b * 1; // FAILS
	a = t;
	// also fails with destructuring expression vs above vars
	//[a,b] = [b,a];
	count++;
	}

	// check
	if((inner % 2 === 0 && !(a === 1 && b === 0)) \|\|
	(inner % 2 === 1 && !(a === 0 && b === 1))) {
	_status('FAIL', [a, b]);
	throw 'FAIL';
	}
	// progress
	//_status('....', [a, b]);
	if((test + 1) % 100 === 0 && (outer + 1) === outer_max) {
	_status('....', [a, b]);
	}
	}
	}
	<html>
	<head>
	<title>Safari 10.0.1 Loop Optimization Bug Test</title>
	</head>

	<body>
	<h1>Safari 10.0.1 Loop Optimization Bug Test</h1>

	<p>This test reveals an optimization bug. A deterministic function
	is run in a loop. The test stops when an incorrect result is found.
	Once a failure is found, reload the page to test again.</p>

	<hr/>

	<input type="button" value="Stop" onclick="stop()">
	<div>Test: <span id="test">...</span></div>
	<div>Outer Loop <span id="outer">...</span></div>
	<div>Count <span id="count">...</span></div>
	<div>First <span id="first">...</span></div>
	<div>Last <span id="last">...</span></div>
	<div>Status <span id="status">...</span></div>

	<hr/>

	<p>Attempted test data as of latest builds and code on 2016-10-31:</p>

	<p>Passes:</p>
	<ul>
	<li>Chrome, Firefox, Safari before 10.x (all platforms)</li>
	<li>Safari 10.0.1 mac/64b with debug console open</li>
	<li>WebKit/JavaScriptCore / jsc (linux - i386/32b)</li>
	</ul>
	<p>Fails:</p>
	<ul>
	<li>Safari 10.0.1 (mac/64b)</li>
	<li>Safari tech preview v16 (mac/64b)</li>
	<li>WebKit/JavaScriptCore / jsc (mac/linux - x86-64/64b)</li>
	</ul>

	<p>Authors:</p>
	<ul>
	<li>David I. Lehn <<a href="mailto:dlehn@digitalbazaar.com">dlehn@digitalbazaar.com</a>></li>
	<li>Dave Longley <<a href="mailto:dlongley@digitalbazaar.com">dlongley@digitalbazaar.com</a>></li>
	</ul>

	<script>
	var run = true;
	var first = null;
	// use values high enough for optimizer to run
	// usually fails around the same number of inner loops
	var test_max = 50000;
	var outer_max = 500;
	// use at least 2 inner loops
	var inner_max = 2;
	// inner loop count
	var count = 0;
	var test = 0;
	var outer, inner;
	function stop() {
	run = false;
	}
	function _loop() {
	if(run && test < test_max) {
	if(_test()) {
	test++;
	setTimeout(_loop, 0);
	}
	}
	}
	setTimeout(_loop, 0);

	function _status(status, values) {
	document.getElementById('status').innerHTML = status;
	document.getElementById('test').innerHTML = test + 1;
	document.getElementById('outer').innerHTML = (outer + 1) + '/' + outer_max;
	document.getElementById('count').innerHTML = count;
	document.getElementById('first').innerHTML = first.join('');
	document.getElementById('last').innerHTML = values.join('');
	}

	function _test() {
	for(outer = 0; outer < outer_max; ++outer) {
	var t, a, b;

	a = 1;
	b = 0;

	// loop required. manually unrolling avoids bug.
	for(var inner = 0; inner < inner_max; ++inner) {
	t = b;
	b = a;
	// do one of the following to avoid optimization bug:
	// b = b & -1; // FIX
	// b = b >>> 0; // FIX
	// other operations will not avoid optimization bug:
	// b = b + 0; // FAILS
	// b = b * 1; // FAILS
	a = t;
	count++;
	}

	if(first === null) {
	first = [a, b];
	}
	// check
	if((inner % 2 === 0 && !(a === 1 && b === 0)) \|\|
	(inner % 2 === 1 && !(a === 0 && b === 1))) {
	_status('FAIL', [a, b]);
	return false;
	}
	// progress
	//_status('....', [a, b]);
	if((test + 1) % 100 === 0 && (outer + 1) === outer_max) {
	_status('...', [a, b]);
	}
	}
	return true;
	}
	</script>
	</body>
	</html>
	<html>

	<head>
	<title>Safari 10 Optimization Bug</title>
	</head>

	<body>
	<h1>Safari 10 Optimization Bug</h1>

	<p>This test reveals an optimization bug in Safari 10. A
	deterministic function is run in a loop. Its first return
	value is stored and printed to the screen. If any subsequent
	turn of the loop produces a different return value, the
	test exits immediately and prints the different value.
	</p>
	<p>This test passes successfully on Chrome, Firefox, and
	early versions of Safari (less than v10). It fails on
	Safari 10. You may need to refresh the page a few times
	to get a failure, but it typically fails every time.
	</p>

	<input type="button" value="Stop" onclick="stop()">
	<div>Attempt: <span id="iteration">...</span></div>
	<div>First result is <span id="expected">...</span></div>
	<div>Final result
	<span id="result">matches first result.<br>
	<span style="color: green">SUCCESS!</span></span>
	</div>

	<script>
	var run = true;
	var expected;
	var attempt = 0;
	var attempts = 5000;
	var iterations = 500;
	function stop() {
	run = false;
	}
	function _check() {
	if(run && attempt < attempts) {
	if(_runTest(attempt, iterations)) {
	attempt++;
	setTimeout(_check, 0);
	}
	}
	}
	setTimeout(_check, 0);

	function _runTest(attempt, max) {
	function _status(itr) {
	document.getElementById('iteration').innerHTML =
	(attempt + 1) + ', Iteration ' + (itr + 1) + ' / ' + max;
	}
	for(var itr = 0; itr < max; ++itr) {
	var s = {
	a: 0,
	b: 0,
	c: 1
	};
	var t, a, b, c;

	a = s.a;
	b = s.b;
	c = s.c;

	// loop required. manually unrolling avoids bug.
	for(var j = 0; j < 2; ++j) {
	t = c;
	c = b;
	// uncommenting line below with `>>> 0` will avoid the bug
	//c = c >>> 0;
	b = a;
	a = t;
	}

	s.a = a;
	s.b = b;
	s.c = c;

	// compute the result
	var result = [s.a, s.b, s.c].join('');
	// display and result comparison
	if((attempt + 1) % 100 === 0) {
	_status(itr);
	}
	if(attempt === 0 && itr === 0) {
	expected = result;
	document.getElementById('expected').innerHTML = expected;
	} else if(result !== expected) {
	var output = {iteration: itr, result: result};
	_status(itr);
	document.getElementById('result').innerHTML =
	' is ' + output.result + '<br>' +
	'<span style="color: red">FAILURE!</span> ' +
	'Final result does not match first result.';
	return false;
	}
	}

	return true;
	}
	</script>

	</body>

	</html>