Thinking differently about software testing paradigms

Photo by Simon Berger: https://www.pexels.com/photo/brown-camel-931881/

> "The terms 'unit test' and 'integration test' have always been rather murky, even by the slippery standards of most software terminology." 
> -- [Martin Fowler](https://martinfowler.com/articles/2021-test-shapes.html)

> "...there is no such thing as a Unit Test" 
> -- [Michael Belivanakis](https://blog.michael.gr/2022/10/incremental-integration-testing.html)

## What is a Unit Test?

I typed the above question into a popular search engine, and the first three results I got back were as follows (emphasis mine)

> A unit test is a block of code that verifies the accuracy of a smaller, isolated block of application code, typically a function or method. -- [aws.amazon.com](https://aws.amazon.com/what-is/unit-testing/)

> A unit test is a way of testing a unit - the smallest piece of code **that can be logically isolated** in a system. In most programming languages, that is a function, a subroutine, a method or property. -- [smartbear.com](https://smartbear.com/learn/automated-testing/what-is-unit-testing/)

> Unit is defined as a single behaviour exhibited by the system under test (SUT), usually corresponding to a requirement. While it may imply that it is a function or a module (in procedural programming) or a method or a class (in object-oriented programming) **it does not mean functions/methods, modules or classes always correspond to units**. From the system-requirements perspective only the perimeter of the system is relevant, thus **only entry points to externally-visible system behaviours define units**. -- [Kent Beck via Wikipedia](https://en.wikipedia.org/wiki/Unit_testing)

A problem I often see with modern software testing is that [we lean toward the second definition too often](https://www.reddit.com/r/learnprogramming/comments/nwpzx9/how_can_unit_tests_be_useful_if_refactoring/): a unit is "the smallest piece of code that can be logically isolated in a system". The word "can" is carrying a _lot_ of weight in this sentence. We _can_ logically isolate just about anything.

"Is a unit a file?"

-- "Definitely not", I can hear you say.

"Assuming an object-oriented program, how about a class?"

-- "Probably not", you say with slightly less conviction.

"How about a method?"

-- "Probably", with a bit more confidence, agreeing with the first two results above.

"What if that method is 300 lines of code?"

-- "Ooh, yeah, you should probably break that out into smaller methods."

Suppose we do this. Let's break our 300-line method into, say, 10 methods of 30 lines each, as [some CS professors seem to teach their students that this is a good rule of thumb for function length](https://www.reddit.com/r/learnprogramming/comments/toynah/when_i_was_in_undergrad_they_told_us_no_function/#:~:text=In%20general%2C%20the%20most%20common,should%20only%20do%20one%20thing.).

```scala
// before
def original(x: String, y: Int): Boolean = {

 // ...
 // hundreds of lines of code
 // ...

}
```

```scala
// after
def improved(x: String, y: Int): Boolean = {

 val intermediateValueA = a(x)
 val intermediateValueB = b(intermediateValueA, y)
 val intermediateValueC = c(intermediateValueB)
 // ...
 val intermediateValueH = h(intermediateValueG)
 val intermediateValueI = i(intermediateValueH)
 
 j(intermediateValueI)

}

private def a(x: String): Long = {
 // ...
}

private def b(z: Long, y: Int): Double = {
 // ...
}

// eight more private functions...
```

All of these methods could be `private` (or whatever your language's equivalent of that is). In that case, they can only be accessed by the class which contains them. They used to be all in one method anyway, so we can be sure nobody else is using this logic anywhere else.

But now we face another decision: should we write unit tests for all of these individual methods? For many of us, our gut reaction will be "yes". This could make refactoring more difficult in the future, though, because ["the closer your tests are to the implementation the more sensitive they are to changes"](https://www.effective-software-testing.com/do-unit-tests-make-refactoring-harder).

> Anecdotally, I've worked on codebases with hundreds of tests like this, all tightly coupled to the production implementation. Adding one field to a class meant updating a hundred or more tests which didn't care about this field at all, but needed the new field in order to compile. The test changes regularly took longer to implement than the production changes.

Writing unit tests for these smaller methods might also require us to make them more `public` than they need to be; the world outside this class doesn't care about these individual methods, all it cares about is the one `improved` method which now ties them all together.

The real question is, are these functions "units" of code?

The answer is no.

As Kent Beck would say, these are not "entry points to externally-visible system behaviours".

The only externally-visible entry point in the refactored example above is the `improved` function, just as the `original` function was initially. But these pervasive ideas that...

1. large functions should be broken up into smaller ones, and
2. a "unit test" is a "test of a single function"

...combine to produce a result that is much worse than the sum of its parts: huge suites of tests tightly-coupled to unnecessarily-public production code that take too long to write and are difficult to maintain.

Outcomes like this lead many developers to believe things like...

> "Most Unit Testing is Waste" 
> -- [James O. Coplien](https://wikileaks.org/ciav7p1/cms/files/Why-Most-Unit-Testing-is-Waste.pdf)

## Kinds of Tests

Rather than thinking of tests along the traditional [unit / integration / end-to-end spectrum](https://qase.io/blog/test-pyramid/), I think it's helpful to think along a few other dimensions

1. is this test _fast_ or _slow_?
2. is this a _black-box_ test or a _white-box_ test?
3. is this test _informed by_ development or does _it inform_ development?

### Fast and Slow Tests

Let me start by asserting that "fast" is not synonymous with "good", and "slow" is not synonymous with "bad" in this context.

Fast tests are tests that run in a few seconds, milliseconds, microseconds, or less. Fast tests, therefore, must be entirely in-memory. They [do no disk IO and they make no network calls](https://gist.github.com/jboner/2841832). They can be run every single time a code change is made without being a roadblock to development speed, and should therefore be run as part of the developer's [inner loop](https://www.awwsmm.com/blog/drop-everything-and-review). Every time you compile, you can run these tests.

Slow tests take several seconds, minutes, or hours to run. The dividing line between fast and slow tests is somewhere around 2-5 seconds. Slow tests may require reading large input files from disk, doing lots of computation, or communicating across the network. That is: they are [IO, CPU, or network _bound_](https://stackoverflow.com/q/868568/2925434). [Contract tests](https://testsigma.com/blog/api-contract-testing/) (which often spin up Docker containers) and performance tests (which may run gigabytes of data or thousands of requests through the system) are examples of slow tests. These tests should be run less regularly, as they can impact development speed: before each commit to `main` / `master` is probably fine for tests shorter than a few minutes, daily or weekly might be a good cadence for tests much longer than that.

### Black-Box and White-Box Tests

Black-box tests make no assumptions about the internals of the thing they are testing. They provide inputs and assert on observable outputs, and that's it. The observable output is usually a return value from a method, but a black-box test might instead assert that a side effect has occurred, like that a log line has been written, or that a metric has been recorded, or that some state has been mutated.

White-box tests specifically test the internals of the thing they are testing. They are [_introspective_](https://stackoverflow.com/a/25199156/2925434). Tests which have assertions like "when 'x' happens, function a() should call function b()" are white-box tests. They are explicitly testing _how_ something should happen (_how_ some code is implemented), rather than testing only that it _has_ happened. Tests which rely heavily on mocking frameworks are often white-box tests, asserting that [such-and-such a method has (or hasn't) been called](https://sachithradangalla.medium.com/mockito-verify-how-to-test-method-invocations-8cf15be9bc19) in response to some inputs.

If you don't care about _how_ something is implemented -- just that that it does what it's supposed to do -- you should write a black-box test. This is usually the case, so opt for black-box tests as a default.

### Development-Informed Tests and Development-Informing Tests

Development-informed tests are written _reactively_, in that the production code is written first, and the tests are written afterward. Development-informed tests codify the behaviour of the system as-is. Traditional "unit tests" are almost exclusively development-informed tests.

Development-informing tests are written _proactively_, in that a test is written first, and the production code is written after. [Test-Driven Development (TDD)](https://en.wikipedia.org/wiki/Test-driven_development) is a software development methodology which encourages writing _only_ development-informing tests, ensuring that 100% of the system's behaviour is always codified in tests.

Development-informing tests can also provide confidence that some tricky piece of logic has been implemented correctly. For example, you might write a [regex](https://en.wikipedia.org/wiki/Regular_expression) to parse U.S. phone numbers, and -- at the same time -- add a handful of tests to ensure that you catch things like
- area codes surrounded by parentheses
- spaces vs. no spaces vs. hyphens
- the presence or absence of a `+1` country code

It can be hard to be sure -- just by staring at the regular expression -- that it catches all of these cases. Usually it's more convincing to just write a handful of simple tests to convince yourself that the most common edge cases are being handled correctly.

I always write bug fix tests in a development-informing way, as well. First, I write a test which _should_ pass, but which I expect to fail due to the presence of a bug. Then, I fix the bug in the production code, ensuring that the test now passes. This process shows that -- had the test existed originally -- it would have caught the bug. This gives confidence that the bug should not reappear in the future.

## "Most Unit Testing is Waste"

The three ways of looking at tests outlined above can provide insight into why developers like [James O. Coplien](https://wikileaks.org/ciav7p1/cms/files/Why-Most-Unit-Testing-is-Waste.pdf) believe that most unit testing is a waste of time.

### Most Unit Tests are Development-Informed

In my experience, TDD is not practiced by [_most_](https://www.reddit.com/r/ExperiencedDevs/comments/1g1xdqu/do_you_guys_use_tdd/) developers.

Most tests, therefore, are development-informed. A developer writes some production code and then writes a test, usually to ensure that some [code coverage minimum](https://www.atlassian.com/continuous-delivery/software-testing/code-coverage#:~:text=With%20that%20being%20said%20it,fairly%20low%20percentage%20of%20coverage.) is reached.

These tests are not written to catch bugs, and they are not written to help a developer think through some difficult implementation, and so their value is not immediately apparent.

### Most Unit Tests do not test "Externally-Visible System Behaviours"

As mentioned earlier, the twin practices of (1) breaking large functions up into smaller ones and (2) writing tests for each _function_ rather than for each _externally-visible system behaviour_ leads to a proliferation of tests tightly-coupled to the production implementation. These tests are, by their nature, fragile. They must be updated whenever the smallest implementation detail is changed, even if the externally-visible system behaviour is identical.

> This often happens when using mocking frameworks, since every method called on [a mocked object](https://www.digitalocean.com/community/tutorials/mockito-mock-examples) must be declared, with its return value specified.

In the worst-case scenario, developers will sometimes copy-and-paste the production implementation directly into the test, asserting that the "expected" result from the test implementation equals the "actual" result from the production code. This kind of white-box test unquestionably adds no value, even if it does increase "code coverage".

## A New Test Pyramid

The traditional [test pyramid](https://qase.io/blog/test-pyramid/) aims to emphasise to developers that they should be mostly writing "unit tests", with fewer "integration tests" and only a handful of "end-to-end tests". Although different formulations of the pyramid may use different terms for the latter two levels, almost all agree that the base of the pyramid should be composed of "unit tests". [Google recommends](https://testing.googleblog.com/2015/04/just-say-no-to-more-end-to-end-tests.html) a 70% / 20% / 10% split of unit / integration / end-to-end tests.

The idea is that you should cover most of the code's logic in small, fast tests which can be run over and over during the [inner loop of development](https://www.awwsmm.com/blog/drop-everything-and-review). Your integration tests should cover interactions between units; and your end-to-end tests should validate that an end user's actions result in some expected overall outcome.

That advice is fine, provided all developers agree what constitutes a "unit test" or an "integration test". Clearly this is not the case. (See the search engine results at the top of this blog post.) However, we can use the objective criteria above (fast vs. slow, black-box vs. white-box, development-informed vs. development-informing) to construct a New Test Pyramid.

![A New Test Pyramid](/blog/there-is-no-such-thing-as-a-unit-test/pyramid.png)

### The Base

Opt for black-box tests wherever possible. Where external dependencies are required, prefer [fake](https://stackoverflow.com/q/346372/2925434) implementations [rather than mocks](https://testing.googleblog.com/2024/02/increase-test-fidelity-by-avoiding-mocks.html) (and add corresponding contract tests to ensure that external dependency behaves as you think it does). This keeps the entire test in-memory, making it fast enough to run before each commit to `main` / `master`. You will find that most of your tests are these fast, black-box tests.

Note that this is _not_ synonymous with "unit test". As discussed above, traditional "unit tests" are usually fast, but are sometimes white-box tests, and are often development-informed.

### The Middle

Prefer development-informing tests over development-informed tests (prefer a TDD style of development). Development-informed tests are often written [by rote](https://www.merriam-webster.com/dictionary/rote) and offer little value.

Prefer slow black-box tests over fast white-box tests. The former are easier to maintain as they are less tightly-coupled to the production implementation.

Traditional "integration tests" and "end-to-end" tests both fall into the "slow, black-box tests" category.

### The Top

Write as few white-box tests as possible. That is, do as little code introspection as possible. Only test observable outputs.

Write development-informed tests only when necessary. If the production implementation works, it works. If it doesn't, you will find a bug, write a development-informing test, and fix the bug. This process is described above.

## Conclusion

The traditional unit / integration / end-to-end categorization of tests is fuzzy at best. Differing interpretations of what constitutes a "unit test", combined with well-intentioned but misapplied advice on keeping code readable by reducing the number of lines per function, class, etc. has led to a proliferation of hard-to-maintain, low-value test suites that negatively impact developer productivity.

Categorizing tests objectively, using the three criteria described above, can lead to more maintainable tests which provide more value.

There is No Such Thing as a Unit Test

Computer programming as an art form in and of itself

## Digital Art

In almost all circumstances, code is a means to an end.

The phrase "computer programming" itself describes the activity of _programming_ a _computer_ to accomplish a particular task. Often, that task is logical. Most computer programs do something "useful", whether that's calculating the best route from your home to work, balancing a budget, or running your [smart fridge's Twitter client](https://www.cbsnews.com/news/teen-goes-viral-for-tweeting-from-lg-smart-fridge-after-mom-confiscates-all-electronics/).

But many programs are written solely to produce something of aesthetic value.

Recently, Generative AI applications like [Midjourney](https://www.midjourney.com/showcase), which can produce visual art from text prompts, have seen a lot of press. But consider also [dwitter.net](https://www.dwitter.net/top/all), where JavaScript programs of 140 characters or fewer create moving 3D landscapes, gyrating fractals, and even [self-playing games of Pong](https://www.dwitter.net/d/135). And also programmers like [Grzegorz Witczak](https://codepen.io/Wujek_Greg/pen/LmrweG), [Ben Evans](https://codepen.io/ivorjetski/pen/xxGYWQG), and [Diana A. Smith](https://diana-adrianne.com/) who create photorealistic works of art using only [CSS](https://en.wikipedia.org/wiki/CSS), a language otherwise used mainly to style fonts, borders, and backgrounds on web pages.

[Digital art](https://en.wikipedia.org/wiki/Digital_art) is not a new phenomenon. Nearly as long as computers have existed, programmers have been using them to express themselves aesthetically.

> Traditional artists have been inspired by digital art, as well. Consider Dalí's [_Painting of Gala looking at the Mediterranean sea which from a distance of 20 meters is transformed into a portrait of Abraham Lincoln (Homage to Rothko)_](https://www.salvador-dali.org/en/artwork/catalogue-raisonne-paintings/obra/871/painting-of-gala-looking-at-the-mediterranean-sea-which-from-a-distance-of-20-meters-is-transformed-into-a-portrait-of-abraham-lincoln-homage-to-rothko), produced in 1976, which appears to show a pixelated image of Abraham Lincoln when viewed from a distance.

For most digital artists, code is a _medium_, like marble for a sculptor, or a canvas for a painter. Code is the material through which the art is _expressed_. Though it takes time and skill to produce, a canvas itself is not usually seen as art itself. But [could it be](https://www.npr.org/2021/09/29/1041492941/jens-haaning-kunsten-take-the-money-and-run-art-denmark-blank)?

## Readability

Developers often talk about writing ["clean"](https://en.wiktionary.org/wiki/clean_code) or ["elegant" code](https://www.quora.com/What-do-programmers-mean-by-elegant-code). Most programming languages are ["general-purpose"](https://en.wikipedia.org/wiki/General-purpose_programming_language), meaning they can be used to accomplish a variety of tasks. Accordingly, there are often many different ways to accomplish the _same_ task, using the same programming language.

Robert C. Martin's [_Clean Code: A Handbook of Agile Software Craftsmanship_](https://www.oreilly.com/library/view/clean-code-a/9780136083238/) gives many examples of "unclean" code, with tips and rules of thumb for rewriting the code in a "clean" way.

In the overwhelming majority of cases, the most important aspect of code is its functionality -- usually to perform some computational task. A _secondary_ aspect of the code is its _readability_, closely related to the "cleanliness", "elegance", or "aesthetics" of the code.

As a quick example, consider this 3x3 matrix

```scala
val identity = Array(1, 0, 0, 0, 1, 0, 0, 0, 1)
```

Which elements are on the diagonal of this matrix?

It's much more _readable_ if we [manually format it](https://scalameta.org/scalafmt/docs/configuration.html#-format-off) as follows

```scala
val identity = Array(1, 0, 0,
 0, 1, 0,
 0, 0, 1)
```

These two arrays are functionally identical. But _aesthetically_, the source code used to construct the latter array is more "readable" than the former. Functionality is paramount, but aesthetics are a close second.

But what if a program (or an entire programming language) were designed _primarily_ for its aesthetic qualities?

## Unreadability

Formatting code for readability -- or to follow established patterns and idioms -- is the norm. But some programmers do the opposite (intentionally or otherwise).

Every year, the International Obfuscated C Code Contest ([IOCCC](https://www.ioccc.org/)) accepts submissions of C code which accomplish some task, but do it in an unusual, hard-to-decipher way. These programs are functional, but are purposely formatted so as to be as _unreadable_ as possible (they are _obfuscated_).

Some programming languages have been designed specifically to accomplish as much as possible in as few characters as possible. [APL](https://en.wikipedia.org/wiki/APL_(programming_language)#Game_of_Life) is a "serious" (non-"esoteric") and very terse programming language which programmers may be familiar with, but many [code golf](https://en.wikipedia.org/wiki/Code_golf) languages have been created specifically to minimize source code size in a similar way.

And some programmers choose to format their code so that their entire ray-tracing C++ program can [fit on the back of a business card](https://mzucker.github.io/2016/08/03/miniray.html), or so [the source code](https://github.com/mame/quine-relay/blob/master/QR.rb) of their [ouroborous quine](https://en.wikipedia.org/wiki/Quine_(computing)#Ouroboros_programs) written in Ruby looks like a dragon (see the header image of this blog post), or so that they [look like and can be read as poems](https://code-poetry.com/). All of these examples use "serious" programming languages in an "unserious" way.

## Esoteric Languages

There are also many programming languages where the [aesthetics of the source code](https://www.awwsmm.com/blog/20-intriguing-unusual-and-goofy-programming-languages#aesthetics) is more important than what is actually written in that code. As most programming languages are written using ASCII or Unicode character sets, [some of these](https://web.archive.org/web/20240205064805/https://blue.sky.or.jp/grass/) look like [ASCII art](https://en.wikipedia.org/wiki/ASCII_art)...

```
　　　　_, ._
　　（　・ω・）　んも〜
　　○=｛=｝〇,
　 　|:::::::::＼, ', ´
､､､､し ､､､((（.＠）ｗｖｗｗＷＷｗｖｗｗＷｗｗｖｗｗｗｗＷＷＷｗｗＷｗ
ｗＷＷＷＷＷＷｗｗｗｗＷｗｗｖｗＷＷｗＷｗｗｖｗＷＷＷ
```


...though most just look like [jumbled messes of characters](https://esolangs.org/wiki/Labyrinth)

```
 72_1_108::_3+:}
 0 _ """
 11_{78_23_" " "
 4 4 ".{@
 _ " {
 1 }"
 08_100_33"""""
```

Some esoteric programming languages are [non-textual](https://esolangs.org/wiki/Category:Non-textual). The source code of these programs can be visual, as with [Piet](https://www.dangermouse.net/esoteric/piet/samples.html)

!["Hello World" in the Piet programming language](/blog/code-as-art/piet.gif)

or [Nice](https://esolangs.org/wiki/Nice) (which does not yet have a working interpreter)

!["Hello World" in the Nice programming language](/blog/code-as-art/nice.png)

Other languages are auditory, meaning programs are encoded as sound. Usually, these programs can also be written [as individual notes](https://esolangs.org/wiki/Sound), or as [sheet music](https://esolangs.org/wiki/Hello_world_program_in_esoteric_languages_(D-G)#Fugue)

!["Hello World" in the Fugue programming language](/blog/code-as-art/fugue.png)

<figure style="display:block;text-align:center">
 <figcaption>Listen to the above program</figcaption>
 <audio controls src="/blog/code-as-art/fugue-hello-world.mp3"></audio>
</figure>

In many cases, the simplest implementation of a program in these languages is not the most aesthetically pleasing. Programmers will opt for beautiful programs over efficient ones. 

For example, the following Piet program gets a number as input from the user, squares it, and prints the result

![A sample Piet program](https://thepracticaldev.s3.amazonaws.com/i/1clwo2qss6zurm2kisdw.png)

...but so does this one

![A simple Piet program](https://thepracticaldev.s3.amazonaws.com/i/i77oznhfqnyu147wxesz.png)

## Code as Art

> "There is no generally agreed definition of what constitutes art" [[Wikipedia](https://en.wikipedia.org/wiki/Art)]

Even in languages which aren't specifically designed to have "beautiful" source code, some programmers opt to format their code in ways which trade efficiency, practicality, or readability for aesthetic appeal.

There is no single, correct solution to a problem which can be solved by a program. Different programs can accomplish the same task in different ways. Weighing tradeoffs and choosing one solution over another is part of the art of computer programming.

The human desire to be creative and express one's individuality does not end where a keyboard begins. Hundreds of esoteric programming languages can attest to that.

Whether textual, visual, or auditory, code can be used as a medium to create art, but it can also _be_ art itself.

Code as Art

Given only inequality relationships between members of the set

## Sayonara Scala Steward

One of my ongoing projects at work is developing and maintaining an in-house dependency updating solution for our code.

We used to use [Scala Steward](https://github.com/scala-steward-org/scala-steward) to keep our Scala projects up-to-date, but found that it [created a lot of noise](https://medium.com/permutive/scala-steward-without-the-noise-da7424f3c315) -- failed pipelines, merge conflicts, and new versions of software being released where the only change was a patch version bump to a dependency. 

We wanted a cleaner solution
- one update PR per week per repo, containing all of the dependency updates
- PRs with failed pipelines would be assigned to a "repo owner" who could resolve them during the week
- and next week, if that PR was still open, it would be closed in favour of a new one

The last point ensures that at most one dependency update PR is open at any given time for any project. This seriously reduces the mental overhead on the developer (usually, the team lead) tasked with handling these weekly update PRs.

This project is implemented in two parts.

First, there's the [`sbt-dependency-updater`](https://gitlab.com/improving-andrew/sbt-dependency-updater), which adds an `updateDependencies` task to any [`sbt`](https://www.scala-sbt.org/)-managed Scala project (as all of ours are). This task makes it easy to update all of the dependencies for a specific repo. (Note that the way in which these dependencies are updated is pretty primitive and could use some refinement.)

Second, there's a (privately-hosted) `dependency-updater` repo which uses GitLab pipelines and the GitLab API to clone a project, run `updateDependencies` in that project, and -- if there is a nonzero number of updates -- create a branch and MR against `master` / `main`, assigning the team lead to the MR.

It's all been working very smoothly for the past few months. Noise (both cognitive and pipeline) has decreased significantly, and dependencies are as up-to-date as they have always been.

But this blog post is not about that dependency updating software; it's about how we grouped our dozens of repos into "Tiers", based on dependencies, to ensure that everything is always as up-to-date as possible.

## Tiers

A repository of code has some list of dependencies (upstream libraries which it uses to do its job).

Suppose you have some `infrastructure` library which is depended on by most projects, and a `utilities` library which depends on `infrastructure`, and that most projects also depend on `utilities`.

In order to ensure that some project `a` has the latest version of `utilities` and the latest version of `infrastructure`, ideally with no transitive version conflicts, we want to do something like the following

1. update `infrastructure`'s dependencies
2. update `utilities`'s dependencies, which include `infrastructure`
3. update `a`'s dependencies, which include `utilities` and `infrastructure`

A natural step-by-step process has emerged. Here we introduce some terminology and say that projects which can be updated at the same time belong to the same "tier". For instance, if we have another project `b` which also depends on `utilities` and `infrastructure`, then `a` and `b` can be updated simultaneously (in the same CI pipeline) without any problems. But if `b` depends on `a`, then updating `b`'s dependencies should happen _after_ updating `a`'s dependencies. `b` gets bumped into a lower tier.

This begs the question: _what is the minimum required number of tiers for some set of projects with dependencies on each other_? In other words, by analyzing their dependencies, how can we efficiently group a set of projects into tiers such that updates to higher tiers efficiently "flow" into lower tiers during the course of the week's dependency updates?

## Problem Statement

Given a set of `N` values representing projects: `a`, `b`, `c`, `d`, and `e`, let inequality relationships between the values indicate dependencies between projects. For example, `a < b` indicates that `a` depends on `b`.

What is the minimum number of unique values that can be assigned to `a`, `b`, `c`, `d`, and `e`, given some set of `M` unique inequality relationships?

"Unique equality relationships" means `a < b` and `b > a` count as only a single relationship, because they are just two different ways to express the same information.

## Discussion

I'm not planning on _proving_ this in the mathematical sense, but I think we can come up with an intuitive solution by thinking through this problem logically.

Let's start with `M = 0`. This is the case where there is _no_ inequality information. In this case, there is no reason we cannot assume `a = b = c = d = e`, and put all dependencies in the same tier. The minimum number of unique values in this case is `1`, when there is only a single tier. So in the `M = 0` case, we have no inequality information, and `1` tier is sufficient when `N = 5` and `M = 0`.

`1` is the minimum number of unique values when `N = 5` and `M = 0`.

> Note that `a`, `b`, `c`, `d`, and `e` _could_ also have five unique values. This is always possible if we assume that there _exists_ some additional information which we are just not currently aware of. But the problem we are trying to solve is the _minimum_ number of unique values _required_ to satisfy the known information. 

In the `M = 1` case we have a single unique inequality, for example `a < b`. Here, we must have at least two unique values, since `a` and `b` are explicitly not equal; `b` is in tier `1` and `a` is in tier `2`. However, `c`, `d`, and `e` can fall into either tier without contradicting any known inequality information, so `2` is the minimum number of unique values when `N = 5` and `M = 1`.

`M = 2` is where things start to get interesting, because there are two kinds of scenarios here.

First, suppose our two known inequalities are `a < b` and `b < c`. This requires `a`, `b`, and `c` to have three unique values, and so we require three tiers. But if our two known inequalities are `a < b` and `a < c`, then it's possible that `b = c`, and only two tiers are required. In fact, we could have up to four inequalities and still only require two tiers, if `a < b`, `a < c`, `a < d`, and `a < e`. In this case, `b = c = d = e`, `a` is in tier 2, and all other projects are in tier 1.

So `2` is the minimum number of unique values when `N = 5` and `0 < M <= 4`.

But when `M = 5` something changes. If our initial four inequalities are `a < b`, `a < c`, `a < d`, and `a < e`, and we add a fifth unique inequality, we must split tier `1` into two tiers. For example, if `b < c`, then `a`, `b`, and `c` must exist in different tiers, and the minimum required number of tiers is `3`.

But like the `1 < M <= 4` case, we can continue to add inequalities for a while with only three tiers. If `b < d` and `b < e`, then it's possible that `c = d = e`, `a < b`, and `b < c`, and all of our previous inequalities still hold (`a < b`, `a < c`, `a < d`, `a < e`, `b < c`, `b < d`, and `b < e`).

So `3` is the minimum number of unique values when `N = 5` and `4 < M <= 7`.

You may be starting to see where this is going. If we add another inequality, say `c < d`, we require a fourth tier. But four tiers is also enough for _another_ inequality, `c < e`.

`4` is the minimum number of unique values when `N = 5` and `7 < M <= 9`.

Finally, when `N = 5`, we can have at most `M = 10` unique inequalities. For example: `a < b`, `a < c`, `a < d`, `a < e`, `b < c`, `b < d`, `b < e`, `c < d`, `c < e`, and `d < e`. This uniquely orders all projects `a < b < c < d < e` and requires the maximum number of `5` tiers.

`5` is the minimum number of unique values when `N = 5` and `M = 10`.

Let's recap. If `k` is the minimum number of unique values required, then, when `N = 5`

- when `M = 0`, `k = 1`
- when `0 < M <= 4`, `k = 2`
- when `4 < M <= 7`, `k = 3`
- when `7 < M <= 9`, `k = 4`, and
- when `M = 10`, `k = 5`

Writing this another way

- when `M = 0`, `k = 1`, else
- when `M <= 4`, `k = 2`, else
- when `M <= 4 + 3`, `k = 3`, else
- when `M <= 4 + 3 + 2`, `k = 4`, and
- when `M = 4 + 3 + 2 + 1`, `k = 5`

The [triangular numbers](https://en.wikipedia.org/wiki/Triangular_number) have emerged. If `T(N)` is the `N`th triangular number, then

- `T(0) = 0`
- `T(1) = 1`
- `T(2) = 3`
- `T(3) = 6`
- `T(4) = 10`

So we can re-express the above as

- when `M = 0`, `k = 1`, else
- when `M <= T(4) - T(3)`, `k = 2`, else
- when `M <= T(4) - T(2)`, `k = 3`, else
- when `M <= T(4) - T(1)`, `k = 4`, and
- when `M = T(4)`, `k = 5`

Since `M` is bounded by the range `[0, T(4)]` when `N = N`, this covers all possible values of `M` and `k`.

We can postulate that, for any set of `N` values, described only by `M` unique inequalities between values, the set must be composed of at least `k` unique values, where

- `M` is bounded by the range `[0, T(N-1)]`
- when `M = 0`, `k = 1`
- when `M = T(N-1)`, `k = N`, and
- `T(N-1) - T(k) < M <= T(N-1) - T(k-1)`

## Future Work

### Optimal Number of Tiers

The above reasoning was enough to convince me that this is procedure gives the correct _minimum_ number of tiers required for staggered, grouped dependency updates. But the next step is more difficult -- actually determining what those tiers should be.

It's easy to see that when `a < b` and `b < c`, we can construct three tiers...

- tier 1: `c`, `d`, and `e` (these receive dependency updates first)
- tier 2: `b` (then this project receives dependency updates)
- tier 3: `a` (and finally, this one)

...but that `d` and `e` can be put into any tier.

However, it's much harder to reason about what the tiers should be, and where projects should be placed on them, when you have dozens of projects with dozens of dependencies. We know the _minimum_ number of tiers from the above analysis, but we've also seen that this minimum is exceeded when we have dependency chains like `a < b < c`. Does the longest dependency chain determine the "optimal" number of tiers? Can we prove this? Can we turn this process into an algorithm?

### Circular Dependencies

Another possible extension to this problem is the idea of _circular dependencies_. In the real world, it's possible (though an anti-pattern) for `a` to depend on `b` while `b` depends on `a`. Notationally, we could express this with the `<=` operator, rather than `<`. If `a <= b` and `b <= a`, then it must be the case that `a = b`, and these two dependencies should be updated at the same time, on the same tier.

This _is_ the case in my real-world system, and the way I handle this is to update any tiers with circular dependencies _twice_. Here's how that looks

- `a v1` depends on `b v0` and `b v1` depends on `a v0`
- update `a` to depend on `b v1`, producing `a v2`; update `b` to depend on `a v1`, producing `b v2`
- at this point, `a v2` still (circularly) depends on the "old" `a v0` via `b v1`, and vice versa for `b v2`
- so update `a` again to depend on `b v2`, producing `a v3`; and update `b` again to depend on `a v2`, producing `b v3`
- now, we have `a v3 < b v2 < a v1` and vice versa for `b`, and the old dependencies are no longer brought in transitively (at least two levels deep)

How does the possibility of circular dependencies affect the minimum required number of tiers? How do we express that, when `a <= b`, for example, but we have no corresponding `b <= a`, that `a` and `b` should be in different tiers?

There's a bit more to think about here, but I'll leave that for another time.

Solving for the Minimum Number of Unique Values in a Set

On prioritizing code review when developing software

## The Inner and Outer Development Loops

Feedback is critical when developing software; the earlier it can be given, the better. Static code analysis tools will _immediately_ write red squigglies underneath code, as it's being written, to let a programmer know that there's a syntax error. (In fact, as I'm writing this blog post, I'm getting blue underlines from my spellchecker.) Unit tests, similarly, give very quick feedback, validating the logic of any newly-written code, and ensuring that there are no regressions (that the new code doesn't cause previously-written tests to break).

This very fast code-build-test feedback loop is often called the [inner loop of software development](https://sourcegraph.com/blog/developer-productivity-thoughts). It requires no input from other people, and the time for a complete loop can be as short as the time it takes static analysis to run, which might be only a few hundred milliseconds. The only blockers in the inner loop are the speed of the compiler or interpreter and the speed at which the developer can program.

The _outer loop_, by contrast, usually refers to the process of deploying code to a live environment and iterating based on integration with the larger system, acceptance tests, performance tests, and so on (though [different](https://sourcegraph.com/blog/developer-productivity-thoughts) sources [disagree](https://docs.stakater.com/saap/for-developers/explanation/inner-outer-loop.html) about [which steps](https://notes.paulswail.com/public/The+inner+and+outer+loops+of+software+development+workflow) should be included in the [outer loop](https://www.mckinsey.com/industries/technology-media-and-telecommunications/our-insights/yes-you-can-measure-software-developer-productivity)). This loop is much more involved and, accordingly, takes much more time to provide feedback to the developer. Depending on how fast your CI / CD pipeline runs, and whether your QA tests are automated or manual, it could take anywhere from minutes to days.

But I propose that there is a _middle loop_, as well, which often gets incorrectly lumped into the outer loop: the code review loop.

## The Middle Loop

The Middle Development Loop involves getting feedback from developers and other stakeholders, adjusting your code according to that feedback, and then requesting additional feedback. It is distinct from the inner loop, which is traced by a single developer in a single codebase in a single environment, as well as from the outer loop, which is traced by many developers across many environments. The key differentiator here is that this is the first time that multiple stakeholders will be looking at the same new bit of code.

This often happens during code review, but feedback can come in many forms: pair programming, mob programming, [synchronous code review](https://glia.engineering/the-case-for-synchronous-code-reviews-51a19b76b7b7), as well as traditional asynchronous code review. The latter is, in many workplaces, the standard: you create a PR, add some reviewers, and go off and do something else while you wait for feedback.

![https://xkcd.com/303/](/blog/drop-everything-and-review/approvals.png)

This is usually fine, provided you have lots of tasks to work on and can context switch easily from one to another while waiting for reviews. And while this is often the case, in my experience, the opposite happens just as often: you're building some feature across multiple code bases, or in multiple steps, and you need reviews and approvals at each stage. In this case, each time a review is required, it becomes a blocker.

Developers can get frustrated waiting for reviews and glob multiple fixes into a single PR to reduce the number of reviews required, or they might ping other developers directly to ask for reviews. Those pinged might be taken out of their [flow state](https://github.blog/2024-01-22-how-to-get-in-the-flow-while-coding-and-why-its-important), or even feel harassed, if contacted over and over.

For all parties involved, it can be a very frustrating experience.

If you have the power to do so in your organization, push for [synchronous code reviews](https://glia.engineering/the-case-for-synchronous-code-reviews-51a19b76b7b7), which greatly reduce the size of the middle loop, or for synchronous _coding_, like pair or mob programming, which eliminates the middle loop entirely. For many reading this, though, I know this is not an option. You've got async code reviews and you're stuck with them. In that case, let's try to make the best of a less-than-ideal situation: what is it that makes async review frustrating?

The problem with async code review is that it often unnecessarily inflates the duration of the middle loop.

Code review can be a thankless job. When's the last time you heard of someone getting promoted for being the most thorough reviewer on a team? Plus, it's easy to hide in a crowd, and if 10 developers are added as reviewers to a PR which only needs 2 approvals, they may ignore the request, assuming that their teammates will pick up the slack. Even when a developer _does_ review some code, they may delay doing so. Waiting until you're finished your current task, or until after lunch, or even until after your next meeting, to review a PR may not seem like a delay for you. In fact, in may seem downright prompt. But to the developer waiting for a review to continue their work, they are blocked.

The next time _you_ put up a PR, you will _also_ need reviews. And just like your coworkers, you will want them as quickly as possible. So remember that when someone requests a code review, the courteous thing to do is to **Drop Everything and Review (DEAR)**.

## Minimize the Middle Loop, Dear

After handling any active production incidents, the first thing on a developer's `// TODO` list should _always_ be reviewing code.

If you've just sat down at your desk and are looking for something to work on, checking which pull requests you've been assigned to should become a reflex.

Don't start that little bug fix, don't read that next blog post (unless it's this one), don't check your inbox.

Remember **DEAR** and do the courteous thing: Drop Everything and Review.

Drop Everything and Review

Understanding const generics in the Rust programming language with a few examples

[I was working through an example](https://github.com/awwsmm/daily-bevy/tree/time/virtual_time) in [the repo for the Bevy game engine](https://github.com/bevyengine/bevy/blob/v0.13.0/examples/time/virtual_time.rs) recently and came across this code

```rust
/// Update the speed of `Time<Virtual>.` by `DELTA`
fn change_time_speed<const DELTA: i8>(mut time: ResMut<Time<Virtual>>) {
 let time_speed = (time.relative_speed() + DELTA as f32)
 .round()
 .clamp(0.25, 5.);

 // set the speed of the virtual time to speed it up or slow it down
 time.set_relative_speed(time_speed);
}
```

This is a function (`fn`) which takes a `mut`able argument called `time`. The type of `time`, `ResMut<Time<Virtual>>`, comes after the colon, `:`.

The thing that caught my eye here was the generic parameter: `<const DELTA: i8>`. What is that?

Here's another example from Bevy

```rust
pub unsafe fn read<T>(self) -> T {
 let ptr = self.as_ptr().cast::<T>().debug_ensure_aligned();
 // -- snip --
}
```

The `read` function takes a generic type parameter `T` and uses it in two places: in the body of the function, and as a return type. Programmers who are familiar with generics know that an unconstrained `T` is a placeholder that means "any type"; it could be `String` or `bool` or anything else.

> In languages with a global type hierarchy, like Java, a value `t: T` has _some_ operations which can be performed on it, like `.toString()`, because _every_ type `T` in Java extends the base `Object` type. Rust has no such global type hierarchy, and no root `Object` type, so there's not much at all you can do with an instance of an unconstrained type.

Going back to the first example, `const DELTA: i8` clearly already _has_ a type, appearing after the colon, `:`. (It is `i8`, an 8-bit signed integer.) So what is it doing sitting between those angle brackets (`<>`) where generic parameters usually sit?

In this position, `const DELTA: i8` is acting as a [const generic](https://doc.rust-lang.org/reference/items/generics.html#const-generics).

## What Are Const Generics?

Const generic parameters are a new ([ish](https://blog.rust-lang.org/2021/02/26/const-generics-mvp-beta.html)) kind of generic parameter in Rust, similar to type parameters (e.g. `T`) and lifetime parameters (e.g. `'a`). In the same way that a function (or method, `struct`, `enum`, `impl`, `trait`, or `type` alias) can use a generic _type_ parameter, it can also use _const generic_ parameters.

Const generic parameters are what power `[T; N]` type annotation of arrays in Rust. They are why `[T; 3]` (an array of three `T` values) and `[T; 4]` (an array of four `T` values) are _different types_, but different types which can be handled _generically_ as specific implementations of `[T; N]`.

Const generic parameters allow items to be generic over _constant values_, rather than over types.

The difference can be subtle. Here's a simple example

```rust
fn add<const b: i8>(a: i8) -> i8 {
 a + b
}
```

Here, `b` is not a "type parameter"; it is a _value_, and so it can be treated exactly as a value, used in expressions, and so on. But since it is `const`, the value of `b` must be known at compile time. For example, the following will not compile

```rust
fn example(a: i8, b: i8) -> i8 {
 add::(a) // error: attempt to use a non-constant value in a constant
}
```

The logic in this function, of course, could also be expressed like

```rust
fn add(a: i8, b: i8) -> i8 {
 a + b
}
```

...so what's the benefit of const generics? Let's look at some other examples

## Using Const Generics to Enforce Correctness

There are a few examples from linear algebra where const generics are very helpful. For example, the [dot product](https://en.wikipedia.org/wiki/Dot_product) of two vectors `a` and `b`, is defined for any two vectors of any dimensionality (length), provided they have the _same_ dimensionality

```rust
struct Vector<const N: usize>([i32; N]);

impl<const N: usize> Vector<N> {
 fn dot(&self, other: &Vector<N>) -> i32 {
 let mut result = 0;
 for index in 0..N {
 result += self.0[index] * other.0[index]
 }
 result
 }
}
```

We get a compile-time error if we try to find the dot product of two vectors with different numbers of elements

```rust
fn main() {
 let a = Vector([1, 2, 3]);
 let b = Vector([4, 5, 6]);
 
 assert_eq!(a.dot(&b), 32); // ok: a and b have the same length
 
 let c = Vector([7, 8, 9, 10]);
 
 a.dot(&c); // error: expected `&Vector<3>`, but found `&Vector<4>`
}
```

Const generics can be applied to [matrix multiplication](https://amacal.medium.com/learning-rust-const-generics-8c29fc26fad4), as well. Two matrices [can be multiplied](https://en.wikipedia.org/wiki/Matrix_multiplication) only if the first one has `M` rows and `N` columns and the second has `N` rows and `P` columns. The resulting matrix will have `M` rows and `P` columns.

```rust
struct Matrix<const nRows: usize, const nCols: usize>([[i32; nCols]; nRows]);

impl<const M: usize, const N: usize> Matrix<M, N> {
 fn multiply<const P: usize>(&self, other: &Matrix<N, P>) -> Matrix<M, P> {
 todo!()
 }
}
```

Here, we again get a compile-time error if we ignore this constraint

```rust
fn main() {
 let a = Matrix([[1, 2, 3], [4, 5, 6]]); // 2 x 3 matrix
 let b = Matrix([[1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6]]); // 3 x 4 matrix
 
 a.multiply(&b); // ok: 2 x 4 matrix
 
 let c = Matrix([[1, 2, 3], [2, 3, 4]]); // 2 x 3 matrix
 
 a.multiply(&c); // error: expected `&Matrix<3, <unknown>>`, but found `&Matrix<2, 3>`
}
```

These constraints can be enforced at runtime without const generics, but const generics can help [shift these issues left](https://en.wikipedia.org/wiki/Shift-left_testing), catching them earlier in the development process, tightening [the inner dev loop](https://www.getambassador.io/docs/telepresence/latest/concepts/devloop#what-is-the-inner-dev-loop).

## Using Const Generics to Conditionally Implement `trait`s

(Adapted from [Nora's example here](https://nora.codes/post/its-time-to-get-hyped-about-const-generics-in-rust/).)

Const generics also enable really powerful patterns, like compile-type checks on values in signatures. For example...

```rust
struct Assert<const COND: bool> {}
```

...this `struct` takes a constant generic `bool` parameter, `COND`. If we define a `trait` `IsTrue`...

```rust
trait IsTrue {}

impl IsTrue for Assert<true> {}
```

...we can conditionally implement `trait`s by requiring some `Assert` to `impl IsTrue`, like so

```rust
trait IsOdd<const N: i32> {}

impl<const N: i32> IsOdd<N> for i32 where Assert<{N % 2 == 1}>: IsTrue {}
```

> The above `Assert<{N % 2 == 1}>` requires `#![feature(generic_const_exprs)]` and the `nightly` toolchain. See https://github.com/rust-lang/rust/issues/76560 for more info.

Above, `trait IsOdd` is implemented for the `i32` type, but only on values `N` which satisfy `N % 2 == 1`. We can use this trait to get compile-time checks that constant (hard-coded) `i32` values are odd

```rust
fn do_something_odd<const N: i32>() where i32: IsOdd<N> {
 println!("oogabooga!")
}

fn do_something() {
 do_something_odd::<19>();
 do_something_odd::<42>(); // does not compile
 do_something_odd::<7>();
 do_something_odd::<64>(); // does not compile
 do_something_odd::<8>(); // does not compile
}
```

The above will generate a compiler error like

```rust
error[E0308]: mismatched types
 --> src/main.rs:70:5
 |
70 | do_something_odd::<42>();
 | ^^^^^^^^^^^^^^^^^^^^^^^^ expected `false`, found `true`
 |
 = note: expected constant `false`
 found constant `true`
```

## Using Const Generics to Avoid Complex Return Types

Finally, const generics can be used to make code more readable, and more performant. The example from the beginning of this post comes from Bevy, and the reason const generics are used there is because Bevy is expecting a function pointer as an argument to a method

```rust
fn main() {
 App::new()
 // -- snip --
 .add_systems(
 Update,
 (
 // -- snip --
 change_time_speed::<1>.run_if(input_just_pressed(KeyCode::ArrowUp)),
 // -- snip --
 ),
 )
 .run();
}
```

`change_time_speed::<1>`, above, is a function pointer. We can rearrange this method to take an argument, rather than using a const generic parameter...

```rust
change_time_speed_2(1).run_if(input_just_pressed(KeyCode::ArrowUp)),
```

...but then we would have to change the return type as well

```rust
/// Update the speed of `Time<Virtual>.` by `DELTA`
fn change_time_speed_2(delta: i8) -> impl FnMut(ResMut<Time<Virtual>>) {
 move |mut time| {
 let time_speed = (time.relative_speed() + delta as f32)
 .round()
 .clamp(0.25, 5.);

 // set the speed of the virtual time to speed it up or slow it down
 time.set_relative_speed(time_speed);
 }
}
```

To many, the original function may be more readable

```rust
/// Update the speed of `Time<Virtual>.` by `DELTA`
fn change_time_speed<const DELTA: i8>(mut time: ResMut<Time<Virtual>>) {
 let time_speed = (time.relative_speed() + DELTA as f32)
 .round()
 .clamp(0.25, 5.);

 // set the speed of the virtual time to speed it up or slow it down
 time.set_relative_speed(time_speed);
}
```

Remember, as well, that Rust uses [monomorphization of generics](https://doc.rust-lang.org/book/ch10-01-syntax.html#performance-of-code-using-generics) to improve runtime performance. So not only is the const generic version of this function more readable, but it's possible (though I haven't benchmarked) that it's more performant as well. Either way, it's good to know that there are multiple ways to attack a problem, and to be able to weigh the pros and cons of each approach.

Hopefully this discussion has helped you to understand what const generics are, and how they can be used in Rust.

Andrew Watson

Blog