Is there a logical complexity beyond which TDD doesn't work?

Question

All the books which talk about test-driven development (TDD) illustrate it with only very basic examples, less than 100 LOC.

The algorithms I wrote using TDD were larger, but still relatively small in size and complexity.

I'm pretty sure I know a few developers who successfully used TDD on algorithms of a few thousands of LOCs. Anything larger, however, would be broken down to modules, and each module would be unit-tested separately, in isolation from other modules.

I don't have any example of a really large algorithm that used TDD successfully. Does TDD scale well when the complexity of the tested logic increases, or it becomes ineffective, forcing the developers to move to other testing approaches?

A few examples of a complex logic that cannot be reasonably split into multiple modules:

• A lexer for a rather complicated syntax.
• The compiler.
• The rendering engine of a web browser which is in charge of displaying a page based on the DOM and the CSS rules applied to it.
• A simulator of an electrical circuit.
• Regular expressions engine.

---

The question appears in the context of my answer to a question about the testing of a lexer. In my answer, I assumed that TDD would work great for someone who develops a lexer from scratch. In the comments, several persons highlighted that my assumption may be wrong.

---

The question is different from Does TDD really work for complex projects? : there, the question is about enterprise codebases, which include the user interfaces and other things which aren't particularly easy to unit test. My question is exclusively about algorithms, and specifically about the pure ones which have no side effects.

Answer 1

I'd say you're sort of asking the wrong question.

Yes, TDD can be a great method for developing pretty much any kind of software. But it's not sufficient by itself for anything but the simplest and least critical applications — ones where 99.9% of the inputs fall into a small number of common types, and where failure to handle the remaining 0.1% correctly is mostly harmless.

For anything else, you'll want to do something besides just TDD to ensure that your code operates correctly – where "something" can range from just writing additional tests on top of the minimal test set created during TDD iteration to fuzz testing and other kinds of automated test generation methods, or even formally proving the correctness of your algorithm (and its implementation!).

Basically, TDD has two main advantages as a development methodology:

• When faced with a problem where you're not initially sure exactly what the full requirements are or how to fully meet them, but where you do have examples of individual use cases and expected behavior in each case, TDD can help you iterate towards a working solution.

• Also, using TDD ensures that your code has tests, and that those tests cover at least a somewhat decent number of potential problem cases. Even if the tests aren't perfect and don't cover all ways in which the code could break, having any tests at all is still better than having none.

On the other hand, the main problems with relying only on pure TDD are that:

• The TDD iteration isn't guaranteed to converge to a correct solution. For some problem domains, it can be very hard to come up with a fully correct algorithm that works in all cases without careful top-down planning, like formally defining the pre- and postconditions that the inputs and outputs must satisfy and using these to construct an algorithm that provably yields valid output for any valid input. If one instead tries to just fix one individual case after another, the result may instead be an "overfitted" algorithm that basically only produces correct results for the test cases, and nothing else.

  Of course, it's possible to do that kind of top-down design within TDD, e.g. starting with an "overfitted" algorithm and replacing it with a properly designed solution in the refactoring phase. But at that point, what you're doing is stepping outside pure TDD, as your top-down redesign isn't only driven by the tests any more. Which, to be clear, is perfectly fine and even often necessary. But it does then bring up the second problem…

• If you only add tests that currently fail on each iteration, you may end up skipping cases that should be tested, but which your current code just happens to already handle correctly. (This is particularly likely if you've at some point actually done some non-trivial top down design to come up with a solution that handles more than just the current test cases.) Then a later change or refactoring, possibly several years later and/or by another developer, might break those cases without it being caught by the test suite.

  On the other hand, if you do add tests also for cases that already work, the question then becomes: when should you stop? For many programs — like the lexers mentioned in the earlier question — the set of possible input combinations is effectively infinite and it's not necessarily obvious which of those combinations are most vulnerable to later regressions.

That said, none of these issues should dissuade anyone from using TDD, or from writing comprehensive tests in general. One just needs to keep in mind that there's no "silver bullet" development methodology that can substitute for analytical insight and understanding the problem domain. And that applies to developing appropriate and effective test suites, too.

Answer 2

Is there a logical complexity beyond which TDD doesn't work?

I think the answer is no - logical complexity is the thing that TDD handles really well.

BUT - part of the way that TDD addresses logical complexity is introducing gentle pressure to partition that logical complexity into separately testable modules.

You don't have to decompose your design; if there are other reasons that you want one big lump of code, that's fine. Similarly, you can decompose your design without increasing your test surface -- in other words, using component tests rather than unit tests. That's also fine.

You're still going to want to be able to isolated the logical complexity from things that make the testing expensive or unstable (network effects, shared mutable state, etc). TDD loses a lot of its appeal when you have a slow or unreliable testing cycle between each refactoring.

---

What I think you will find is that many TDD practitioners introduce additional constraints to encourage their design preferences. A common one is that people want tests that are small, such that comprehending the intent of the test is lower effort. Or people who want micro-tests because they want a design composed of small modules. Or because they want to future proof their test designs against requirement changes.

The RED-GREEN-REFACTOR cycle is the essential element of TDD; that cycle implies that we have enough tests to be confident that the design tells the machine to do the right thing, and also that we are running those tests often (and therefore that the tests have the properties necessary that this doesn't drive us insane).

Most of the other ideas are just adaptations for common contexts.

Answer 3

Is there a logical complexity beyond which TDD doesn't work?

That depends completely on you.

All the books which talk about test-driven development (TDD) illustrate it with only very basic examples, less than 100 LOC.

Yeah, because they're books talking about examples. Only so much fits in a book. This is not exclusive to TDD.

The algorithms I wrote using TDD were larger, but still relatively small in size and complexity.

I'm pretty sure I know a few developers who successfully used TDD on algorithms of a few thousands of LOCs. Anything larger, however, would be broken down to modules, and each module would be unit-tested separately, in isolation from other modules.

That's because people who know about TDD also tend to know about modularizing programs and tend not to write 1000-LOC-in-one-file nightmares. TDD wont stop you from writing nightmares. You do that.

I don't have any example of a really large algorithm that used TDD successfully. Does TDD scale well when the complexity of the tested logic increases, or it becomes ineffective, forcing the developers to move to other testing approaches?

TDD doesn't care about complexity. It cares whether you can conceive of a testable interface. That's the limit. You want TDD to test something outrageously complex you have to think of some abstraction that can hide that complexity. You need a way to drive that interface that deterministically gives you a testable result. And you need to do that in a way that doesn't sneak behind the abstraction and lock you down to a particular implementation. This isn't about lines of code or complexity. The limiter here is your ability to design an abstraction that doesn't leak.

That's hard. Complexity doesn't make that easy. But that's not TDD's problem. It's yours. Not using TDD doesn't make it go away.

A few examples of a complex logic that cannot be reasonably split into multiple modules:

Well then let's be unreasonable.

A lexer for a rather complicated syntax.

These could be modules: scanner and evaluator

The compiler.

You can decompose a compiler by compiling to an intermediate language. Python can be compiled into C. C can be compiled into machine code.

The rendering engine of a web browser which is in charge of displaying a page based on the DOM and the CSS rules applied to it.

medium.com - how web browsers work

A simulator of an electrical circuit.

Resisters, capacitors, inductors, transistors, power...

Regular expressions engine.

No. Sorry. I know better than to even touch this one.