eslint-plugin-no-spread-in-reduce

What this eslint rule does

This eslint rule detects when a reduce call returns a value that spreads the accumulator into the return value. Code written in this way is often accidentally quadratic. This rule helps to detect those slow paths so they can be rewritten in a more efficient manner.

const itemsById = items.reduce((acc, item) => {
	return {...acc, [item.id]: item}; // ❌ no-spread-in-reduce error
}, {});

Installation

# npm
npm install --save-dev eslint-plugin-no-spread-in-reduce

# yarn
yarn add --dev eslint-plugin-no-spread-in-reduce

# pnpm
pnpm add --save-dev eslint-plugin-no-spread-in-reduce

Usage

This plugin supports ESLint ^8.38, and ESLint >=9. Add the rule in your ESLint configuration to enable it.

import noSpreadInReduce from 'eslint-plugin-no-spread-in-reduce';

export default [
	{
		plugins: {
			'no-spread-in-reduce': noSpreadInReduce,
		},
		rules: {
			'no-spread-in-reduce/no-spread-in-reduce': 'error',
		},
	},
];

{
	"plugins": ["no-spread-in-reduce"],
	"rules": {
		"no-spread-in-reduce/no-spread-in-reduce": "error"
	}
}

Background

Generally speaking, the spread syntax (the ... part in the expression [...accumulator, value]) enumerates over the values yielded by an object's Iterator implementation. When spreading an Array into another Array, this means looping over all the values within that array.

This looping aspect is subtle, and it means that using a spread within another loop has the potential to create code that has quadratic or O(n^2) time complexity.

Here is a function that contains a nested loop to naively find "pairs" of numbers in an array and sum them together

function sumPairs(numbers: Array<number>): Array<number> {
	const pairs: Array<number> = [];

	let iterations = 0;

	// 💥 These nested `for` loops mean that `sumPairs` runs in O(n^2) time
	for (let i = 0; i < numbers.length; i++) {
		for (let j = 0; j < numbers.length; j++) {
			// Count each time we reach this inner loop
			iterations++;

			// If the numbers are next to each other
			if (i + 1 === j) {
				const a = numbers[i];
				const b = numbers[j];
				pairs.push(a + b);
			}
		}
	}

	console.log(`Looped ${iterations} times`);
	return pairs;
}

// An array of length 5 loops 25 times.
sumPairs([1, 2, 3, 4, 5]); // [3, 5, 7, 9], logs "Looped 25 times"

// An array of double the size (length 10) doesn't double the loop count to 50,
// it _squares_ the count to 100 instead.
sumPairs([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]); // [3, 5, 7, 9, 11, 13, 15, 17, 19], logs "Looped 100 times"

This function is written in a way that makes its quadratic nature obvious: the nested for loops mean that as the length of the numbers argument increases, the number of times we run the code in the innermost loop is proportional to the square of the length of the numbers array.

However, what if we didn't have an obvious signal like two explicit for loops? What if our code was written like this?

// 🤔 No nested `for` loops, so this code isn't `O(n^2)`, right?
function sumPairs(numbers: Array<number>): Array<number> {
	return numbers.reduce<Array<number>>((pairs, num, i) => {
		// There is no "next" number at the end, so exit early
		if (i === numbers.length - 1) {
			return pairs;
		}

		const a = num;
		const b = numbers[i + 1];

		return [...pairs, a + b];
	}, []);
}

It turns out the above snippet also runs in O(n^2) because we are spreading the existing accumulator again and again with each loop of the reduce, creating a new return value each time. The "nested loop" part of the example above is when we create a copy of the pairs array (the [...pairs] bit) before inserting the a + b value at the end of the array. Creating that array copy is an O(n) operation (it has to loop over each value of the array to copy it over), and two nested O(n) bits turns into O(n^2).

In this example, rather than treating the accumulator as immutable, we'd be better off creating the new list once and mutably pushing values onto the end.

function sumPairs(numbers: Array<number>): Array<number> {
	return numbers.reduce<Array<number>>((pairs, num, i) => {
		// There is no "next" number at the end, so exit early
		if (i === numbers.length - 1) {
			return pairs;
		}

		const a = num;
		const b = numbers[i + 1];

		// ✅ Modify `pairs` in place and return the reference,
		// rather than always returning a new accumulator
		pairs.push(a + b);
		return pairs;
	}, []);
}