Short-circuiting nested loops

Published on 9 May 2020 • 4 min

The series of 19

Check out surrounding posts from the series:

4. Array#splice
5. Strings and Unicode
6. Short-circuiting nested loops (this post)
7. Inverting two values with destructuring
8. Easily stripping “blank values” from an array
9. …and beyond! (fear not, all 19 are scheduled already)…

It’s been a while

Ever since JS 1.2 (1997), it’s been possible to label statements. This has been mostly used for loops: classical for, for…in, while and do…while (and since ES2015, for…of). The idea is to allow in-depth short-circuiting, usually through nested loops.

(You’ll get further details from the always-amazing MDN docs, especially about labelled blocks when you have multiple successive blocks making return impractical but wrapping all the remaining scope in an if is undesirable.)

Short-circuiting with break

When we face nested loops, it is often desirable to be able to short-circuit multiple levels at once. Let’s say you’re looking for a value in a 2-dimension matrix; the moment you find it, you want to exit the inner loop (iterating the columns of the row) and the outer loop (iterating the rows of the matrix).

Without labels, this can be a bit kludgy:

const matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
]
const value = 5

let foundAt = null
for (let row = 0, rows = matrix.length; row < rows; ++row) {
  for (let col = 0, cols = matrix[row].length; col < cols; ++col) {
    if (matrix[row][col] === value) {
      foundAt = [row, col]
      break
    }
  }
  // Kludge to short-circuit the outer loop…
  if (foundAt) {
    break
  }
}

foundAt // => [1, 1]

The secret (which, like most secrets, can be discovered by reading the docs, dammit!) is that we can label loops, and use any “active” label as an operand of break. The text of the label is entirely up to you, it could even be an active identifier (but why would you hate readability that much?!). Common candidates are outer or top for the outermost loop. The previous code would become something like this:

// That’s our label
outer: for (let row = 0, rows = matrix.length; row < rows; ++row) {
  for (let col = 0, cols = matrix[row].length; col < cols; ++col) {
    if (matrix[row][col] === value) {
      foundAt = [row, col]
      break outer // And we’re using it here
    }
  }
  // You could have code here, it’d be skipped too.
}

That’s better already, isn’t it? One favorite example of mine, that you can find in the MDN, is about an array of predicates (truth tests) and a series of values, and we try to figure out whether all values pass all predicates. As you may have guessed, the moment one test fails, we want to drop the whole thing:

const values = [1, 2, 3, 4, 5, 6, 7, 8, 9]
const tests = [(n) => n >= 0, Number.isInteger, (n) => n < 5]

let allPassed = true
outer: for (const value of values) {
  for (const test of tests) {
    // When value === 5 and on the last test, this will fail
    if (!test(value)) {
      allPassed = false
      break outer
    }
  }
}

I like it 😊

Short-circuiting with continue

You probably realized we can also use this with continue, in order not to just skip to the next turn of the current loop, but to the next turn of a surrounding loop!

As a variation on the previous example, let’s say we want to get all the values that pass all the tests. The moment a test fails, there’s no point keeping on with the current run of the outer loop, we can skip right to the next one, and restart our inner loop (and any extra in-outer-loop code) from there.

const values = [1, 2, 3, 4, 5, 6, 7, 8, 9]
const tests = [
  (n) => n % 2 === 0, // Multiple of 2
  (n) => n % 3 !== 0, // Not a multiple of 3
]

const passingValues = []
outer: for (const value of values) {
  for (const test of tests) {
    if (!test(value)) {
      continue outer
    }
  }
  passingValues.push(value)
}

passingValues // => [2, 4, 8]

Neat. (And yes, we could have turned this code around and used tests.every(…), but that’s not the point.)

The trap of disguised labels

Ever since arrow functions showed up in ES2015, we’ve seen a rebirth of labels… by mistake!

Let’s say that, for the sake of compatibility with a third-party API, we need to turn a list of numbers into a list of objects with that number as a value property. We might be tempted to write this:

const values = [1, 2, 3, 4, 5, 6, 7, 8, 9]
values.map((n) => {
  value: n
})

Gotcha! We end up with an array of 9 undefined. Classy. This is because we’ve grown comfy with the shorthand notation of arrow functions just returning a value (which is good!) but forgot that curly braces have variable semantics.

// You think we wrote the equivalent to this:
values.map(function (n) {
  return { value: n }
})

// When we actually wrote the equivalent to this:
values.map(function (n) {
  value: n // Look Ma, a statement!
})

Your callback function evaluates n, doesn’t do squat with it and returns nothing (i.e. returns undefined).

This is a common trap when writing short arrow functions that need to return an object literal: you need to ensure that curly braces carry object literal semantics. Here, by default, they represent a function block.

For curly braces to mean an object literal, they need to appear in our code at a spot where JS grammar mandates an expression. The simplest way to trigger that grammatical context without altering code semantics is to surround the curlies with parentheses:

const values = [1, 2, 3, 4, 5, 6, 7, 8, 9]
values.map((n) => ({ value: n }))
// => [{ value: 1 }, { value: 2 }, …]

In recent code you often stumble upon this in selectors / mapStateToProps with Redux (or other application state management libraries, that have the same kind of needs).

Favor functions and return

To wrap up, remember that this type of code is often hard to read and may leave an unpleasant aftertaste in your mouth… For most cases, you’ll be better off defining small helper functions for nested traversals, and resort to trusty ol’ return for short-circuiting. The labeled break example from above would be better written like so:

function everythingPasses(values, tests) {
  for (const value of values) {
    for (const test of tests) {
      if (!test(value)) {
        return false
      }
    }
  }
  return true
}

Labelled nested loops may be preferred for raw performance reasons, and even then, only after having deeply profiled code to check that perf was indeed an issue and the refactored code brings significant gains. It’s pretty rare, nowadays. We’re not always coding a 3D engine that needs to guarantee 60FPS in Full HD, or working with nanosecond-obsessed devs like those of Lodash, you know…