How to statically “check” that callers perform an operation N times.

I had a C++ API for accumulating amounts in a vector and returning them in reverse order, similar to:

class Builder {
public:
  auto append(const int deltaAmount) && -> Builder {
    totalAmount += deltaAmount;
    amounts.push_back(totalAmount);
    return std::move(*this);
  }

  auto build() && -> std::vector<int> {
    std::ranges::reverse(amounts);
    return std::move(amounts);
  }

private:
  int totalAmount{0};
  std::vector<int> amounts{};
};

int main() {
  const std::vector<int> amounts = Builder{}.append(10).append(20).append(30).build();
  std::ranges::for_each(amounts, [](const int amt) { std::cout << amt << '\n'; });
}

Due to not so interesting reasons, I wanted to get rid of std::ranges::reverse.

Builder + compile-time countdown index

I decided to call resize with the number of amounts and keep track of a countdown index that I’d then use to assign amounts to their correct position (from end to beginning) instead of calling push_back (from beginning to end).

However, I now have to account for accidental mismatches between the number of amounts and how many times append ends up being actually called. That’s a not so easy to use correctly kind of API.

Although it might be impossible to enforce they do match with 100% certainty in C++, I’d be fine by making this API a little harder to misuse.

So I templatised the Builder<N> with a compile-time number N (our index) and made append require that N > 0 and then return a Builder<N - 1>. Finally, build requires that N == 0.

In code:

template <size_t NAmounts>
class Builder {
public:
  explicit Builder() {
    amounts.resize(NAmounts);
  }

  auto append(const int deltaAmount) && -> Builder<NAmounts - 1> requires (NAmounts > 0)  {
    Builder<NAmounts - 1> next{};
    next.totalAmount = totalAmount + deltaAmount;
    next.amounts = std::move(amounts);
    next.amounts[NAmounts - 1] = next.totalAmount;
    return next;
  }

  auto build() && -> std::vector<int> requires (NAmounts == 0) {
    return std::move(amounts);
  }

private:
  int totalAmount{0};
  std::vector<int> amounts{};

  template <size_t>
  friend class Builder;
};

int main() {
  const std::vector<int> amounts = Builder<3>{}.append(10).append(20).append(30).build();

  std::ranges::for_each(amounts, [](const int amt) { std::cout << amt << '\n'; });
}

Attempts to change 3 in Builder<3> to, say 2 or 4, are met with compile-time errors. Nice!

Bonus (Rust)

For extra fun I translated this example to Rust. As I wanted to stick to stable, I had to manually encode natural numbers – rather poorly I should add.

I reckon much of tha e boilerplate will vanish once we get generic const expressions and type equality constraints in where clauses.

Until then, here’s my sketch:

use std::marker::PhantomData;

trait Nat {
    const REIFY: usize;
}

struct Z;
trait IsZ: Nat {}
impl IsZ for Z {}

struct S<N>(PhantomData<N>);
trait IsS {}
impl<N: Nat> IsS for S<N> {}

impl Nat for Z {
    const REIFY: usize = 0;
}

impl<N: Nat> Nat for S<N> {
    const REIFY: usize = 1 + N::REIFY;
}

type Dec<M> = <M as DecT>::Out;

trait DecT: Nat {
    type Out: Nat;
}

impl<N: Nat> DecT for S<N> {
    type Out = N;
}

struct Builder<NAmounts: Nat> {
    total_amount: i32,
    amounts: Vec<i32>,
    _n: PhantomData<NAmounts>,
}

impl<N: Nat> Default for Builder<N> {
    fn default() -> Self {
        Self {
            total_amount: 0,
            amounts: vec![0; N::REIFY],
            _n: PhantomData,
        }
    }
}

impl<NAmounts: Nat> Builder<NAmounts> {
    fn append(self, delta_amount: i32) -> Builder<Dec<NAmounts>>
    where
        NAmounts: IsS + DecT,
    {
        let mut next = Builder {
            total_amount: self.total_amount + delta_amount,
            amounts: self.amounts,
            _n: PhantomData,
        };
        next.amounts[Dec::<NAmounts>::REIFY] = next.total_amount;

        next
    }

    fn build(self) -> Vec<i32>
    where
        NAmounts: IsZ,
    {
        self.amounts
    }
}

fn main() {
    dbg!(Builder::<S<S<S<Z>>>>::default()
        .append(10)
        .append(20)
        .append(30)
        .build());
}

Bonus Bonus (C++ Variadic Function + Fold Expression)

We could compress the whole builder into a variadic function, let the compiler infer the number of amounts instead of manually ascribing it, and get the job done with a fold expression over the comma operator:

template <typename...Amounts> requires (std::same_as<Amounts, int> && ...)
auto build(Amounts... deltaAmounts) -> std::vector<int> {
  size_t nAmounts = sizeof...(deltaAmounts);

  std::vector<int> amounts{};
  amounts.resize(nAmounts);

  auto append = [&amounts, totalAmount = 0](const size_t index, const int amount) mutable {
    totalAmount += amount;
    amounts[index] = totalAmount;
  };

  (append(--nAmounts, deltaAmounts), ...);

  return amounts;
}

int main() {
  const std::vector<int> amounts = build(10, 20, 30);
  std::ranges::for_each(amounts, [](const int amt) { std::cout << amt << '\n'; });
}

Conclusion

Just like the Typestate pattern, the principle behind those pieces of code was to encode states as distinct types and state transitions as type transitions. It might not be that mind blowing at first sight, but it’s actually quite a powerful design tool to statically prevent classes of bugs.

Tags: c++ rust