Add combinatorial tests for internal Exchange functions (#807)

* WIP add combinatorial tests for internal Exchange functions

* Change combinitorial testing strategy based on feedback

* Check value of filled[orderHash] in updateFilledState tests

* Add combinatorial tests for addFillResults

* Add combinatorial tests for getPartialAmount

* Implement generic `testWithReferenceFuncAsync`

* Implement generic `testCombinatoriallyWithReferenceFuncAsync`

* Add combinatorial tests for isRoundingError

* Add combinatorial tests for calculateFillResults

* Add support for Geth in internal contract tests

* Fix contract artifacts

* Change DECIMAL_PLACES to 78 and add a note.

* Document new functions in utils

* Optimize tests by only reseting state when needed

* Rename/move some files

* Print parameter names on failure in testWithReferenceFuncAsync

* Add to changelog for utils package

* Appease various linters

* Rename some more things related to FillOrderCombinatorialUtils

* Remove .only from test/exchange/internal.ts

* Remove old test for isRoundingError and getPartialAmount

* Appease linters again

* Remove old todos

* Fix typos, add comments, rename some things

* Re-add some LibMath tests

* Update contract internal tests to use new SafeMath revert reasons

* Apply PR feedback from Amir

* Apply PR feedback from Remco

* Re-add networks to ZRXToken artifact

* Remove duplicate Whitelist in compiler.json

5 files changed, 270 insertions, 9 deletions

diff --git a/packages/contracts/test/utils/artifacts.ts b/packages/contracts/test/utils/artifacts.ts
index 63bd555a4..e608ee174 100644
--- a/packages/contracts/test/utils/artifacts.ts
+++ b/packages/contracts/test/utils/artifacts.ts
@@ -16,6 +16,7 @@ import * as MultiSigWalletWithTimeLock from '../../artifacts/MultiSigWalletWithT
 import * as TestAssetProxyDispatcher from '../../artifacts/TestAssetProxyDispatcher.json';
 import * as TestAssetProxyOwner from '../../artifacts/TestAssetProxyOwner.json';
 import * as TestConstants from '../../artifacts/TestConstants.json';
+import * as TestExchangeInternals from '../../artifacts/TestExchangeInternals.json';
 import * as TestLibBytes from '../../artifacts/TestLibBytes.json';
 import * as TestLibs from '../../artifacts/TestLibs.json';
 import * as TestSignatureValidator from '../../artifacts/TestSignatureValidator.json';
@@ -46,6 +47,7 @@ export const artifacts = {
     TestConstants: (TestConstants as any) as ContractArtifact,
     TestLibBytes: (TestLibBytes as any) as ContractArtifact,
     TestLibs: (TestLibs as any) as ContractArtifact,
+    TestExchangeInternals: (TestExchangeInternals as any) as ContractArtifact,
     TestSignatureValidator: (TestSignatureValidator as any) as ContractArtifact,
     Validator: (Validator as any) as ContractArtifact,
     Wallet: (Wallet as any) as ContractArtifact,
diff --git a/packages/contracts/test/utils/assertions.ts b/packages/contracts/test/utils/assertions.ts
index 112a470f6..61df800c8 100644
--- a/packages/contracts/test/utils/assertions.ts
+++ b/packages/contracts/test/utils/assertions.ts
@@ -15,6 +15,14 @@ let nodeType: NodeType | undefined;
 // resolve with either a transaction receipt or a transaction hash.
 export type sendTransactionResult = Promise<TransactionReceipt | TransactionReceiptWithDecodedLogs | string>;
 
+/**
+ * Returns ganacheError if the backing Ethereum node is Ganache and gethError
+ * if it is Geth.
+ * @param ganacheError the error to be returned if the backing node is Ganache.
+ * @param gethError the error to be returned if the backing node is Geth.
+ * @returns either the given ganacheError or gethError depending on the backing
+ * node.
+ */
 async function _getGanacheOrGethError(ganacheError: string, gethError: string): Promise<string> {
     if (_.isUndefined(nodeType)) {
         nodeType = await web3Wrapper.getNodeTypeAsync();
@@ -42,6 +50,25 @@ async function _getContractCallFailedErrorMessageAsync(): Promise<string> {
 }
 
 /**
+ * Returns the expected error message for an 'invalid opcode' resulting from a
+ * contract call. The exact error message depends on the backing Ethereum node.
+ */
+export async function getInvalidOpcodeErrorMessageForCallAsync(): Promise<string> {
+    return _getGanacheOrGethError('invalid opcode', 'Contract call failed');
+}
+
+/**
+ * Returns the expected error message for the given revert reason resulting from
+ * a sendTransaction call. The exact error message depends on the backing
+ * Ethereum node and whether it supports revert reasons.
+ * @param reason a specific revert reason.
+ * @returns the expected error message.
+ */
+export async function getRevertReasonOrErrorMessageForSendTransactionAsync(reason: RevertReason): Promise<string> {
+    return _getGanacheOrGethError(reason, 'always failing transaction');
+}
+
+/**
  * Rejects if the given Promise does not reject with an error indicating
  * insufficient funds.
  * @param p a promise resulting from a contract call or sendTransaction call.
diff --git a/packages/contracts/test/utils/combinatorial_utils.ts b/packages/contracts/test/utils/combinatorial_utils.ts
new file mode 100644
index 000000000..d72b41f8a
--- /dev/null
+++ b/packages/contracts/test/utils/combinatorial_utils.ts
@@ -0,0 +1,113 @@
+import { BigNumber } from '@0xproject/utils';
+import * as combinatorics from 'js-combinatorics';
+
+import { testWithReferenceFuncAsync } from './test_with_reference';
+
+// A set of values corresponding to the uint256 type in Solidity. This set
+// contains some notable edge cases, including some values which will overflow
+// the uint256 type when used in different mathematical operations.
+export const uint256Values = [
+    new BigNumber(0),
+    new BigNumber(1),
+    new BigNumber(2),
+    // Non-trivial big number.
+    new BigNumber(2).pow(64),
+    // Max that does not overflow when squared.
+    new BigNumber(2).pow(128).minus(1),
+    // Min that does overflow when squared.
+    new BigNumber(2).pow(128),
+    // Max that does not overflow when doubled.
+    new BigNumber(2).pow(255).minus(1),
+    // Min that does overflow when doubled.
+    new BigNumber(2).pow(255),
+    // Max that does not overflow.
+    new BigNumber(2).pow(256).minus(1),
+];
+
+// A set of values corresponding to the bytes32 type in Solidity.
+export const bytes32Values = [
+    // Min
+    '0x0000000000000000000000000000000000000000000000000000000000000000',
+    '0x0000000000000000000000000000000000000000000000000000000000000001',
+    '0x0000000000000000000000000000000000000000000000000000000000000002',
+    // Non-trivial big number.
+    '0x000000000000f000000000000000000000000000000000000000000000000000',
+    // Max
+    '0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff',
+];
+
+export async function testCombinatoriallyWithReferenceFuncAsync<P0, P1, R>(
+    name: string,
+    referenceFunc: (p0: P0, p1: P1) => Promise<R>,
+    testFunc: (p0: P0, p1: P1) => Promise<R>,
+    allValues: [P0[], P1[]],
+): Promise<void>;
+export async function testCombinatoriallyWithReferenceFuncAsync<P0, P1, P2, R>(
+    name: string,
+    referenceFunc: (p0: P0, p1: P1, p2: P2) => Promise<R>,
+    testFunc: (p0: P0, p1: P1, p2: P2) => Promise<R>,
+    allValues: [P0[], P1[], P2[]],
+): Promise<void>;
+export async function testCombinatoriallyWithReferenceFuncAsync<P0, P1, P2, P3, R>(
+    name: string,
+    referenceFunc: (p0: P0, p1: P1, p2: P2, p3: P3) => Promise<R>,
+    testFunc: (p0: P0, p1: P1, p2: P2, p3: P3) => Promise<R>,
+    allValues: [P0[], P1[], P2[], P3[]],
+): Promise<void>;
+export async function testCombinatoriallyWithReferenceFuncAsync<P0, P1, P2, P3, P4, R>(
+    name: string,
+    referenceFunc: (p0: P0, p1: P1, p2: P2, p3: P3, p4: P4) => Promise<R>,
+    testFunc: (p0: P0, p1: P1, p2: P2, p3: P3, p4: P4) => Promise<R>,
+    allValues: [P0[], P1[], P2[], P3[], P4[]],
+): Promise<void>;
+
+/**
+ * Uses combinatorics to test the behavior of a test function by comparing it to
+ * the expected behavior (defined by a reference function) for a large number of
+ * possible input values.
+ *
+ * First generates test cases by taking the cartesian product of the given
+ * values. Each test case is a set of N values corresponding to the N arguments
+ * for the test func and the reference func. For each test case, first the
+ * reference function will be called to obtain an "expected result", or if the
+ * reference function throws/rejects, an "expected error". Next, the test
+ * function will be called to obtain an "actual result", or if the test function
+ * throws/rejects, an "actual error". Each test case passes if at least one of
+ * the following conditions is met:
+ *
+ * 1) Neither the reference function or the test function throw and the
+ * "expected result" equals the "actual result".
+ *
+ * 2) Both the reference function and the test function throw and the "actual
+ * error" message *contains* the "expected error" message.
+ *
+ * The first test case which does not meet one of these conditions will cause
+ * the entire test to fail and this function will throw/reject.
+ *
+ * @param referenceFuncAsync a reference function implemented in pure
+ * JavaScript/TypeScript which accepts N arguments and returns the "expected
+ * result" or "expected error" for a given test case.
+ * @param testFuncAsync a test function which, e.g., makes a call or sends a
+ * transaction to a contract. It accepts the same N arguments returns the
+ * "actual result" or "actual error" for a given test case.
+ * @param values an array of N arrays. Each inner array is a set of possible
+ * values which are passed into both the reference function and the test
+ * function.
+ * @return A Promise that resolves if the test passes and rejects if the test
+ * fails, according to the rules described above.
+ */
+export async function testCombinatoriallyWithReferenceFuncAsync(
+    name: string,
+    referenceFuncAsync: (...args: any[]) => Promise<any>,
+    testFuncAsync: (...args: any[]) => Promise<any>,
+    allValues: any[],
+): Promise<void> {
+    const testCases = combinatorics.cartesianProduct(...allValues);
+    let counter = 0;
+    testCases.forEach(async testCase => {
+        counter += 1;
+        it(`${name} ${counter}/${testCases.length}`, async () => {
+            await testWithReferenceFuncAsync(referenceFuncAsync, testFuncAsync, testCase as any);
+        });
+    });
+}
diff --git a/packages/contracts/test/utils/core_combinatorial_utils.ts b/packages/contracts/test/utils/fill_order_combinatorial_utils.ts
index 44a5199c0..bdd1e62a2 100644
--- a/packages/contracts/test/utils/core_combinatorial_utils.ts
+++ b/packages/contracts/test/utils/fill_order_combinatorial_utils.ts
@@ -46,16 +46,16 @@ chaiSetup.configure();
 const expect = chai.expect;
 
 /**
- * Instantiates a new instance of CoreCombinatorialUtils. Since this method has some
+ * Instantiates a new instance of FillOrderCombinatorialUtils. Since this method has some
  * required async setup, a factory method is required.
  * @param web3Wrapper Web3Wrapper instance
  * @param txDefaults Default Ethereum tx options
- * @return CoreCombinatorialUtils instance
+ * @return FillOrderCombinatorialUtils instance
  */
-export async function coreCombinatorialUtilsFactoryAsync(
+export async function fillOrderCombinatorialUtilsFactoryAsync(
     web3Wrapper: Web3Wrapper,
     txDefaults: Partial<TxData>,
-): Promise<CoreCombinatorialUtils> {
+): Promise<FillOrderCombinatorialUtils> {
     const accounts = await web3Wrapper.getAvailableAddressesAsync();
     const userAddresses = _.slice(accounts, 0, 5);
     const [ownerAddress, makerAddress, takerAddress] = userAddresses;
@@ -123,7 +123,7 @@ export async function coreCombinatorialUtilsFactoryAsync(
         exchangeContract.address,
     );
 
-    const coreCombinatorialUtils = new CoreCombinatorialUtils(
+    const fillOrderCombinatorialUtils = new FillOrderCombinatorialUtils(
         orderFactory,
         ownerAddress,
         makerAddress,
@@ -133,10 +133,10 @@ export async function coreCombinatorialUtilsFactoryAsync(
         exchangeWrapper,
         assetWrapper,
     );
-    return coreCombinatorialUtils;
+    return fillOrderCombinatorialUtils;
 }
 
-export class CoreCombinatorialUtils {
+export class FillOrderCombinatorialUtils {
     public orderFactory: OrderFactoryFromScenario;
     public ownerAddress: string;
     public makerAddress: string;
@@ -240,7 +240,7 @@ export class CoreCombinatorialUtils {
             // AllowanceAmountScenario.TooLow,
             // AllowanceAmountScenario.Unlimited,
         ];
-        const fillScenarioArrays = CoreCombinatorialUtils._getAllCombinations([
+        const fillScenarioArrays = FillOrderCombinatorialUtils._getAllCombinations([
             takerScenarios,
             feeRecipientScenarios,
             makerAssetAmountScenario,
@@ -309,7 +309,7 @@ export class CoreCombinatorialUtils {
         } else {
             const result = [];
             const restOfArrays = arrays.slice(1);
-            const allCombinationsOfRemaining = CoreCombinatorialUtils._getAllCombinations(restOfArrays); // recur with the rest of array
+            const allCombinationsOfRemaining = FillOrderCombinatorialUtils._getAllCombinations(restOfArrays); // recur with the rest of array
             // tslint:disable:prefer-for-of
             for (let i = 0; i < allCombinationsOfRemaining.length; i++) {
                 for (let j = 0; j < arrays[0].length; j++) {
diff --git a/packages/contracts/test/utils/test_with_reference.ts b/packages/contracts/test/utils/test_with_reference.ts
new file mode 100644
index 000000000..599b1eed4
--- /dev/null
+++ b/packages/contracts/test/utils/test_with_reference.ts
@@ -0,0 +1,119 @@
+import * as chai from 'chai';
+import * as _ from 'lodash';
+
+import { chaiSetup } from './chai_setup';
+
+chaiSetup.configure();
+const expect = chai.expect;
+
+export async function testWithReferenceFuncAsync<P0, R>(
+    referenceFunc: (p0: P0) => Promise<R>,
+    testFunc: (p0: P0) => Promise<R>,
+    values: [P0],
+): Promise<void>;
+export async function testWithReferenceFuncAsync<P0, P1, R>(
+    referenceFunc: (p0: P0, p1: P1) => Promise<R>,
+    testFunc: (p0: P0, p1: P1) => Promise<R>,
+    values: [P0, P1],
+): Promise<void>;
+export async function testWithReferenceFuncAsync<P0, P1, P2, R>(
+    referenceFunc: (p0: P0, p1: P1, p2: P2) => Promise<R>,
+    testFunc: (p0: P0, p1: P1, p2: P2) => Promise<R>,
+    values: [P0, P1, P2],
+): Promise<void>;
+export async function testWithReferenceFuncAsync<P0, P1, P2, P3, R>(
+    referenceFunc: (p0: P0, p1: P1, p2: P2, p3: P3) => Promise<R>,
+    testFunc: (p0: P0, p1: P1, p2: P2, p3: P3) => Promise<R>,
+    values: [P0, P1, P2, P3],
+): Promise<void>;
+export async function testWithReferenceFuncAsync<P0, P1, P2, P3, P4, R>(
+    referenceFunc: (p0: P0, p1: P1, p2: P2, p3: P3, p4: P4) => Promise<R>,
+    testFunc: (p0: P0, p1: P1, p2: P2, p3: P3, p4: P4) => Promise<R>,
+    values: [P0, P1, P2, P3, P4],
+): Promise<void>;
+
+/**
+ * Tests the behavior of a test function by comparing it to the expected
+ * behavior (defined by a reference function).
+ *
+ * First the reference function will be called to obtain an "expected result",
+ * or if the reference function throws/rejects, an "expected error". Next, the
+ * test function will be called to obtain an "actual result", or if the test
+ * function throws/rejects, an "actual error". The test passes if at least one
+ * of the following conditions is met:
+ *
+ * 1) Neither the reference function or the test function throw and the
+ * "expected result" equals the "actual result".
+ *
+ * 2) Both the reference function and the test function throw and the "actual
+ * error" message *contains* the "expected error" message.
+ *
+ * @param referenceFuncAsync a reference function implemented in pure
+ * JavaScript/TypeScript which accepts N arguments and returns the "expected
+ * result" or throws/rejects with the "expected error".
+ * @param testFuncAsync a test function which, e.g., makes a call or sends a
+ * transaction to a contract. It accepts the same N arguments returns the
+ * "actual result" or throws/rejects with the "actual error".
+ * @param values an array of N values, where each value corresponds in-order to
+ * an argument to both the test function and the reference function.
+ * @return A Promise that resolves if the test passes and rejects if the test
+ * fails, according to the rules described above.
+ */
+export async function testWithReferenceFuncAsync(
+    referenceFuncAsync: (...args: any[]) => Promise<any>,
+    testFuncAsync: (...args: any[]) => Promise<any>,
+    values: any[],
+): Promise<void> {
+    let expectedResult: any;
+    let expectedErr: string | undefined;
+    try {
+        expectedResult = await referenceFuncAsync(...values);
+    } catch (e) {
+        expectedErr = e.message;
+    }
+    let actualResult: any | undefined;
+    try {
+        actualResult = await testFuncAsync(...values);
+        if (!_.isUndefined(expectedErr)) {
+            throw new Error(
+                `Expected error containing ${expectedErr} but got no error\n\tTest case: ${_getTestCaseString(
+                    referenceFuncAsync,
+                    values,
+                )}`,
+            );
+        }
+    } catch (e) {
+        if (_.isUndefined(expectedErr)) {
+            throw new Error(`${e.message}\n\tTest case: ${_getTestCaseString(referenceFuncAsync, values)}`);
+        } else {
+            expect(e.message).to.contain(
+                expectedErr,
+                `${e.message}\n\tTest case: ${_getTestCaseString(referenceFuncAsync, values)}`,
+            );
+        }
+    }
+    if (!_.isUndefined(actualResult) && !_.isUndefined(expectedResult)) {
+        expect(actualResult).to.deep.equal(
+            expectedResult,
+            `Test case: ${_getTestCaseString(referenceFuncAsync, values)}`,
+        );
+    }
+}
+
+function _getTestCaseString(referenceFuncAsync: (...args: any[]) => Promise<any>, values: any[]): string {
+    const paramNames = _getParameterNames(referenceFuncAsync);
+    return JSON.stringify(_.zipObject(paramNames, values));
+}
+
+// Source: https://stackoverflow.com/questions/1007981/how-to-get-function-parameter-names-values-dynamically
+function _getParameterNames(func: (...args: any[]) => any): string[] {
+    return _.toString(func)
+        .replace(/[/][/].*$/gm, '') // strip single-line comments
+        .replace(/\s+/g, '') // strip white space
+        .replace(/[/][*][^/*]*[*][/]/g, '') // strip multi-line comments
+        .split('){', 1)[0]
+        .replace(/^[^(]*[(]/, '') // extract the parameters
+        .replace(/=[^,]+/g, '') // strip any ES6 defaults
+        .split(',')
+        .filter(Boolean); // split & filter [""]
+}