Checking recursive calls in Jest
I am currently testing a Fibonacci algorithm that uses memoization + recursion.
function memoization(num, hash = {'0': 0, '1':1}) {
if (!hash.hasOwnProperty(num)) {
hash[num] = memoization(num-1,hash) + memoization(num-2,hash);
}
return hash[num];
}
I want to check the memoization aspect of a function in Jest to make sure the function is using the hash correctly and not doing any redundant work:
test('is never run on the same input twice', ()=>{
fib.memoization = jest.fn(fib.memoization);
fib.memoization(30);
expect(allUniqueValues(fib.memoization.mock.calls)).toBeTruthy();
});
However, mock.calls only reports that this function is called once with an initial parameter value and does not track additional recursive calls. Any ideas?
source to share
Spies in JavaScript depend on a function that is a property of an object. They work by replacing an object property with a new function that packages and tracks calls to the original .
If the recursive function calls itself directly, it is impossible to spy on those calls because they refer directly to the function.
To spy on recursive calls, they must refer to functions that can be watched. Fortunately, this is possible and can be done in one of two ways.
The first solution is to wrap the recursive function in an object and access the property of the object to recurse:
fib.js
const wrappingObject = {
memoization: (num, hash = { '0':0, '1':1 }) => {
if (hash[num-1] === undefined) {
hash[num-1] = wrappingObject.memoization(num-1, hash);
}
return hash[num-1] + hash[num-2];
}
};
export default wrappingObject;
fib.test.js
import fib from './fib';
describe('memoization', () => {
it('should memoize correctly', () => {
const mock = jest.spyOn(fib, 'memoization');
const result = fib.memoization(50);
expect(result).toBe(12586269025);
expect(mock).toHaveBeenCalledTimes(49);
mock.mockRestore();
});
});
The second solution is to import the recursive function back into its own module and use the imported function to recurse:
fib.js
import * as fib from './fib'; // <= import the module into itself
export function memoization(num, hash = { '0':0, '1':1 }) {
if (hash[num-1] === undefined) {
hash[num-1] = fib.memoization(num-1, hash); // <= call memoization using the module
}
return hash[num-1] + hash[num-2];
}
fib.test.js
import * as fib from './fib';
describe('memoization', () => {
it('should memoize correctly', () => {
const mock = jest.spyOn(fib, 'memoization');
const result = fib.memoization(50);
expect(result).toBe(12586269025);
expect(mock).toHaveBeenCalledTimes(49);
mock.mockRestore();
});
});
The tests above use Jest, but ideas extend to other test frameworks as well. For example, here's a test for the second solution using Jasmine:
// ---- fib.test.js ----
import * as fib from './fib';
describe('memoization', () => {
it('should memoize correctly', () => {
const spy = spyOn(fib, 'memoization').and.callThrough();
const result = fib.memoization(50);
expect(result).toBe(12586269025);
expect(spy.calls.count()).toBe(49);
});
});
(I optimized the memo to require the minimum number of calls)
source to share