An invariant is a property of a program - or part of a program - that is always true. Ensuring that an invariant holds is one way to ensure that an algorithm works as intended.

One way invariants are employed is in loops. Because loops, by their very nature, involve lots of repetition with different values, it can be hard to write unit tests that anticipate the ways things might go wrong.

Sometimes developers include the invariant in the form of a comment, just to make their intentions clear to the next developer.

Class BrokenList
  attr_accessor :arr

  def initialize(arr)
    @arr = arr
  end

  def max
    current_max = arr[0]

    arr.each_with_index do |current, i|
      current_max = highest(current, current_max)
      # Invariant: current_max == arr[0..i].max
    end

    return current_max
  end
end

What we’re saying is that before the each block starts, at the end of every step within the each block, and after the each block has finished, it is true that current_max is equal to the maximum value in the array so far (i.e., up to the current index).

Let’s check this with an arbitrary example. Say arr is equal to [1, 3, 2].

Before the loop we set current_max equal to arr[0], or 1. 1 is indeed the largest number in [1], so the invariant holds.

The first iteration is the same as our setup. It’s a bit redundant, but it’s one of several possible ways to prevent current_max from being nil.

For the second iteration, we use some magical highest method to get the larger of current or current_max, and assign the result to current_max. Assuming highest works as expected, we’re setting current_max to 3, which is the largest number in [1, 3].

Finally, we use highest again to get the larger of current and current_max. 2 is not larger than 3, so 3 is still the current_max.

This is a bit of a contrived example. If arr[0..i].max is a good invariant, arr.max is a perfectly suitable implementation.

We could make the invariant more specific if we wanted. One possible way of implemeting max would be to sort arr in place and returning the last item. Programmers usually know to avoid these kind of side effects, but we could make it explicit.

There’s another way to take this a step further.

Imagine we have a subtle bug somewhere in our code, and that max returns an incorrect value a very small percentage of the time. We know that bad data is appearing very occasionally, and that it’s somehow related to the max method, but we have no idea when or why. By raising an exception whenever the invariant is violated, we get helpful information - and maybe even a backtrace - in our logging utility.

  def max
    current_max = arr[0]

    arr.each_with_index do |current, i|
      current_max = highest(current, current_max)

      invariant = current_max == arr[0..i].max
      raise "Violation: expected #{current_max} to equal #{arr[0..i].max} at index #{i}, current value: #{current}" unless invariant
    end

    return current_max
  end

If we’re reluctant to raise in production, we could combine the change with a property-based testing tool such as Rantly.

require 'rantly'
require 'rantly/rspec_extensions'
require_relative 'broken_list'

describe "BrokenList" do
  it "accepts an array of integers" do
    property_of {
      Rantly { array(range(0, 100)) { range(0,9000) }}
    }.check { |a|
      bl = BrokenList.new(a)
      expect(bl.max).to eq(a.max)
    }
  end
end

It doesn’t take very many runs to find the culprit:

Violation: expected 0 to equal 8899 at index 57, current value: 99

If our code truly works for every number except 99, and if it silently continues with bad data instead of breaking, this could be a very hard bug to find. Thanks to a loop invariant and property-based testing, we found it in minutes.