9 ms·

Compilers are one of the easiest and most fun pieces of software to test, because you can test very specific behavior without touching the internals at all. E.

Compilers are one of the easiest and most fun pieces of software to test, because you can test very specific behavior without touching the internals at all. E.g. if I want to test that `*` has higher precedence than `+`, I would write something like this: assert_ast_equals(parse_expr("(a*b)+c"), parse_expr("a*b+c")) assert_ast_equals(parse_expr("a+(b*c)"), parse_expr("a+b*c")) You can rewrite the whole compiler if you want, but as long as you have some notion of a "parser", an "AST" and "two AST nodes being the same" this test will keep working. This is much more powerful than going into the parser internals and comparing get_operator_precedence('+') with get_operator_precedence('*') which is the default thing you would do if you're told to test every function after writing it.

actionfromafar 2y ago
Just be careful to not return null from all calls to parse_expr() :)
- 01HNNWZ0MV43FF 2y ago
  That's what mutation tests are for :)
MaxBarraclough 2y ago
Well, low skill floor, sure, but there's a very high skill ceiling. John Regehr and his students have done impressively deep work in finding compiler bugs. • https://blog.regehr.org/archives/category/compilers https://blog.regehr.org/archives/category/compilers • https://blog.regehr.org/ https://blog.regehr.org/ (some of his compiler-related posts aren't properly tagged) • [PDF] https://users.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf https://users.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf Finding and Understanding Bugs in C Compilers (edit I see someone else already posted this paper) • A (very) little discussion: https://news.ycombinator.com/item?id=7728035 https://news.ycombinator.com/item?id=7728035
YorickPeterse 2y ago
For parsing this might be the case, but writing tests becomes a lot more tricky the further down the compilation pipeline you go, as the amount of boilerplate code needed to set things up increases.
matrss 2y ago
This is good advice not just for compilers, but for any kind of software. Test the behavior of the public interface, not of the internals. Doing the latter too much will just unnecessarily lock you into one implementation of your software, without much gain. As examples: If you are creating a web API, only test against the exposed public routes of that API, instead of writing tests for internal helpers. If you are creating a GUI application, programmatically exercise the GUI instead of starting your tests halfway into the innards that respond to the GUI buttons. Tests lock behavior into place, so you should only write tests for behavior that needs to be locked.
- pfdietz 2y ago
  For the most reliable software, don't choose between different testing approaches, use them all. Testing is not like choosing an architecture or programming language for your system; the more approaches the merrier. As each testing approach experiences diminishing returns, it encourages using a different approach to start near the top of its curve. Unit testing enables hidden functionality to be tested. This can prevent future bugs when changes in the system suddenly uncloaks those functions, exposing them to higher level tests.
  - matrss 2y ago
    I don't fully agree. Yes, employ as many testing approaches as possible (e2e tests, property-based testing, golden tests, whatever), but only test for behavior that you expose and want to guarantee will stay as-is. Otherwise you will get into the situation where every refactor will require a test change. Unit testing is fine, if you do it for your public interface. If you are writing a math library then sure, unit test that `add(1, 2) == 3`. But if you just have an internal helper function for that, then think about if you really want to lock its existence and behavior into place, or if that would just hinder future architectural changes. You can always test the exposed functionality that uses the helper and achieve full coverage of it that way. If you can't, then you have dead code. Of course this is all a bit more nuanced. Past a certain size it might make sense to e.g. consider one modules interface to be public for the rest of your application and test it. But you can definitely overdo it and testing every single function you write (as I've seen people unironically suggest) is very likely detrimental.
kazinator 2y ago
Testing a compiler is very hard because the unit tests which validate that some code transformation is happening do not prove that the code transformation will be correct in all conceivable situations in which it occurs. If you pin down too much in test cases, on the other hand, it will be hard to make changes to the compiler without breaking tons of tests. I think, the best way to test a compiler is to have a large standard library or other body of code, including that compiler written in itself. Recompile the whole thing and then recompile it again with the compiled compiler and again. By the third iteration, you should have it a fixed point. That doesn't prove thing are correct, but it gives a lot of confidence, especially if the code base is large and uses a lot of the language. The second piece of confidence is that all that compiled code passes its tests.

actionfromafar 2y ago

Just be careful to not return null from all calls to parse_expr() :)

01HNNWZ0MV43FF 2y ago
That's what mutation tests are for :)

MaxBarraclough 2y ago

Well, low skill floor, sure, but there's a very high skill ceiling. John Regehr and his students have done impressively deep work in finding compiler bugs. • https://blog.regehr.org/archives/category/compilers https://blog.regehr.org/archives/category/compilers • https://blog.regehr.org/ https://blog.regehr.org/ (some of his compiler-related posts aren't properly tagged) • [PDF] https://users.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf https://users.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf Finding and Understanding Bugs in C Compilers (edit I see someone else already posted this paper) • A (very) little discussion: https://news.ycombinator.com/item?id=7728035 https://news.ycombinator.com/item?id=7728035

YorickPeterse 2y ago

For parsing this might be the case, but writing tests becomes a lot more tricky the further down the compilation pipeline you go, as the amount of boilerplate code needed to set things up increases.

matrss 2y ago

This is good advice not just for compilers, but for any kind of software. Test the behavior of the public interface, not of the internals. Doing the latter too much will just unnecessarily lock you into one implementation of your software, without much gain. As examples: If you are creating a web API, only test against the exposed public routes of that API, instead of writing tests for internal helpers. If you are creating a GUI application, programmatically exercise the GUI instead of starting your tests halfway into the innards that respond to the GUI buttons. Tests lock behavior into place, so you should only write tests for behavior that needs to be locked.

pfdietz 2y ago
For the most reliable software, don't choose between different testing approaches, use them all. Testing is not like choosing an architecture or programming language for your system; the more approaches the merrier. As each testing approach experiences diminishing returns, it encourages using a different approach to start near the top of its curve. Unit testing enables hidden functionality to be tested. This can prevent future bugs when changes in the system suddenly uncloaks those functions, exposing them to higher level tests.
- matrss 2y ago
  I don't fully agree. Yes, employ as many testing approaches as possible (e2e tests, property-based testing, golden tests, whatever), but only test for behavior that you expose and want to guarantee will stay as-is. Otherwise you will get into the situation where every refactor will require a test change. Unit testing is fine, if you do it for your public interface. If you are writing a math library then sure, unit test that `add(1, 2) == 3`. But if you just have an internal helper function for that, then think about if you really want to lock its existence and behavior into place, or if that would just hinder future architectural changes. You can always test the exposed functionality that uses the helper and achieve full coverage of it that way. If you can't, then you have dead code. Of course this is all a bit more nuanced. Past a certain size it might make sense to e.g. consider one modules interface to be public for the rest of your application and test it. But you can definitely overdo it and testing every single function you write (as I've seen people unironically suggest) is very likely detrimental.

kazinator 2y ago

Testing a compiler is very hard because the unit tests which validate that some code transformation is happening do not prove that the code transformation will be correct in all conceivable situations in which it occurs. If you pin down too much in test cases, on the other hand, it will be hard to make changes to the compiler without breaking tons of tests. I think, the best way to test a compiler is to have a large standard library or other body of code, including that compiler written in itself. Recompile the whole thing and then recompile it again with the compiled compiler and again. By the third iteration, you should have it a fixed point. That doesn't prove thing are correct, but it gives a lot of confidence, especially if the code base is large and uses a lot of the language. The second piece of confidence is that all that compiled code passes its tests.