<p>There are fairly straightforward ways to test a compiler's behaviour on valid programs: most obviously, build a suite of programs to run through the compiler, and know what should happen when they run.</p>
<p>For the compiler's treatment of <em>invalid</em> programs that it rejects statically, things are a bit harder. While producing probable parse errors isn't hard, since line noise almost certainly suffices, producing <em>constructive</em> test cases and measuring them isn't. Among other complexities:</p>
<ul>
<li>there are many more ways for the code to be wrong than right, but not all of them are interesting;</li>
<li>a test program that's rejected for e.g. a type error instead of the intended parse error is still a wrong result;</li>
<li>there can be multiple feasible parse errors arising from one input, but it should reliably produce the &quot;right&quot; one;</li>
<li>and in the right place(s);</li>
<li>a compiler change that causes a <em>different</em> parse error to be produced is likely a problem;</li>
<li>but error <em>messages</em> can be expected to change over time to be more useful to the programmer in ways that the semantics of a working program won't, but updating the entire test suite when that happens is fraught;</li>
<li>both rejected and accepted inputs are important.</li>
</ul>
<p>Producing useful test cases is complicated, evaluating them is difficult, and ensuring comprehensive coverage is challenging. A different approach is required, or a combination of approaches.</p>
<p>How should testing a compiler's parse error detection be managed? (How) can the compiler itself help this process?</p>

<compilers><parsing><compiler-checks><testing>
How can a compiler's parse errors be tested?
<p><a href="https://languagedesign.stackexchange.com/a/1559/285">kaya3's excellent answer</a> can be summarised as:</p>
<h1>Decouple identification of errors and reporting &amp;</h1>
<h2>Errors are Structured Data</h2>
<p>Many of the same practices for good testing apply as for regular software engineering but there are a few additional considerations.</p>
<p>A few points I would add:</p>
<ul>
<li>To make generating new test cases easier (for users) you can add a flag to your interpreter or compiler to output the structured error information directly instead of the actual error messages.</li>
</ul>
<h2><a href="https://en.wikipedia.org/wiki/Equivalence_partitioning" rel="nofollow noreferrer">Equivalence partitioning</a></h2>
<p>You want tests that cover the space of possible behaviours with little or no overlap.</p>
<h2><a href="https://en.wikipedia.org/wiki/Code_coverage" rel="nofollow noreferrer">Coverage Analysis</a></h2>
<ul>
<li>You can aim for near 100% line coverage of the code</li>
<li>A much lower branch coverage is reasonable.</li>
</ul>
<p>For a programming language you need to consider grammatical coverage.
E.g. <a href="https://www.cs.cornell.edu/courses/cs5154/2021sp/resources/SyntaxCoverage.pdf" rel="nofollow noreferrer">Syntax Based Parsing</a></p>
<h2>Fuzzing</h2>
<p>The next level of reliability up good coverage is via <a href="https://en.wikipedia.org/wiki/Fuzzing" rel="nofollow noreferrer">fuzzing</a>.
Randomly mutate your programs to produce new and interesting errors.
(Bonus point if you can use the same mechanism for <a href="https://en.wikipedia.org/wiki/Genetic_programming" rel="nofollow noreferrer">genetic programming</a>)</p>
<h2><a href="https://github.com/Microsvuln/Awesome-Grammar-Fuzzing" rel="nofollow noreferrer">Grammar Fuzzing</a></h2>
<p>Combining grammatical coverage and fuzzing</p>
<h2>Formal Verification</h2>
<p>The next level up is formal verfication or <a href="https://en.wikipedia.org/wiki/Compiler_correctness" rel="nofollow noreferrer">Compiler correctness</a>. A few programming languages or subsets thereof have achieved this.</p>

CC BY-SA 4.0
2023-06-18T18:40:43.973Z
2023-06-18T20:39:24.413Z
2023-06-18T20:39:24.413Z
Bruce Adams
<p>I think there is actually a pretty straightforward way to achieve this, but it depends on the compiler being designed to make testing easy. Particularly, errors (and other diagnostics) must be structured data, not just strings, and the compiler needs an API which returns diagnostics in a data structure rather than directly printing them to stderr.</p>
<p>None of these things is particularly difficult to achieve. I'll use the compiler for my own language, Papyri, as an example:</p>
<ul>
<li>Diagnostics, including syntax errors, are represented as an enum type (<a href="https://github.com/kaya3/papyri-rs/blob/331eaaa6e16df7e228de95ab3aa6e206aae7e0c5/src/errors/syntax_error.rs" rel="noreferrer">source</a>).</li>
<li>Diagnostics are collected into a list during compilation (<a href="https://github.com/kaya3/papyri-rs/blob/331eaaa6e16df7e228de95ab3aa6e206aae7e0c5/src/errors/sink_base.rs#L113" rel="noreferrer">source</a>), instead of being output immediately when they occur.</li>
<li>Then, test cases for diagnostics can consist of an input as a string, and an enum variant for which diagnostic is expected (<a href="https://github.com/kaya3/papyri-rs/blob/331eaaa6e16df7e228de95ab3aa6e206aae7e0c5/tests/tag.rs#L112" rel="noreferrer">source</a>; these examples use a macro to make the tests easier to write).</li>
</ul>
<hr />
<p>I'll run through your bullet points to discuss how this strategy accounts for them:</p>
<blockquote>
<p>there are many more ways for the code to be wrong than right, but not all of them are interesting;</p>
</blockquote>
<p>A test suite for the compiler's diagnostics can be comprehensive if it covers every code path which emits a diagnostic. Having diagnostics represented by an enum makes it easier to ensure full coverage without writing excessively many tests for &quot;uninteresting&quot; cases which are already covered. In practice, many parse errors will only be emitted in one place; for diagnostics reported in multiple places, coverage can be ensured using the IDE's &quot;find all occurrences&quot; tool, or using a code coverage tool.</p>
<blockquote>
<p>a test program that's rejected for e.g. a type error instead of the intended parse error is still a wrong result; there can be multiple feasible parse errors arising from one input, but it should reliably produce the &quot;right&quot; one; and in the right place(s);</p>
</blockquote>
<p>Each test passes if and only if the expected enum variant is present in the list after compilation; occurrences of other diagnostics don't affect the test result.</p>
<p>In the Papyri compiler, I'm not also testing that the diagnostic is associated with the correct source span, but that's mainly because this would make test-writing more difficult, and the test cases are simple enough that there is only one place that the expected diagnostic could occur.</p>
<p>So if the diagnostic occurs at all then it's very likely in the right place, and I don't feel the need to also test that it does occur in the right place. If you do think it would be worth it, though, then a test could be a triple of (source, expected enum variant, expected span).</p>
<blockquote>
<p>a compiler change that causes a different parse error to be produced is likely a problem; but error messages can be expected to change over time to be more useful to the programmer in ways that the semantics of a working program won't, but updating the entire test suite when that happens is fraught;</p>
</blockquote>
<p>By using enum variants, the tests are stable with respect to changes in the wording of error messages, while still catching bugs where the wrong <em>kind</em> of diagnostic is emitted. Therefore there is no need to update the test suite when the wording of an error message changes, only when new kinds of diagnostic are introduced, or the conditions on which some kind of diagnostic should be reported are changed.</p>
<blockquote>
<p>both rejected and accepted inputs are important.</p>
</blockquote>
<p>Accepted inputs (i.e. those without parse errors) will be covered by all the other test cases which test for a particular result instead of a particular diagnostic being emitted. I don't find it that useful to write test cases where the input is valid and the test passes only if no diagnostics are emitted; it's more useful to also require the test to pass if the output matches some expectation.</p>
<p>So yes, it's important to test that parse errors <em>aren't</em> emitted for valid inputs, but this is something you get &quot;for free&quot; when you test that valid inputs have correct compilation results. Therefore I don't think it needs to be part of the strategy for testing diagnostic reporting.</p>

CC BY-SA 4.0
2023-06-18T01:04:02.493Z
2023-06-18T01:14:29.650Z
2023-06-18T01:14:29.650Z
kaya3
CC BY-SA 4.0
2023-06-18T01:07:47.923Z
I buy the rest of this, but "A test suite can be comprehensive if it covers every diagnostic that the parser or compiler is able to emit." is a bit questionable, isn't it? It proves there's **a** way to produce each kind of error, but not more than that.
Michael Homer
CC BY-SA 4.0
2023-06-18T01:11:11.080Z
@MichaelHomer That's a fair point. I would say in practice that there are very few kinds of parse error which can be emitted in more than one code path; at least, that's the case with my own language. If you want to be more rigorous then you can use the IDE's "find all occurrences" feature for each enum variant to ensure that each code path for each enum variant is covered; or you can use a code coverage tool to find code paths that aren't being tested by your existing test suite, and that will include the paths which emit diagnostics that you aren't testing for.
kaya3
# How can a compiler's parse errors be tested?
Posted by: username_0 on 2023-06-17
There are fairly straightforward ways to test a compiler's behaviour on valid programs: most obviously, build a suite of programs to run through the compiler, and know what should happen when they run.

For the compiler's treatment of *invalid* programs that it rejects statically, things are a bit harder. While producing probable parse errors isn't hard, since line noise almost certainly suffices, producing *constructive* test cases and measuring them isn't. Among other complexities:

* there are many more ways for the code to be wrong than right, but not all of them are interesting;
* a test program that's rejected for e.g. a type error instead of the intended parse error is still a wrong result;
* there can be multiple feasible parse errors arising from one input, but it should reliably produce the "right" one;
* and in the right place(s);
* a compiler change that causes a *different* parse error to be produced is likely a problem;
* but error *messages* can be expected to change over time to be more useful to the programmer in ways that the semantics of a working program won't, but updating the entire test suite when that happens is fraught;
* both rejected and accepted inputs are important.

Producing useful test cases is complicated, evaluating them is difficult, and ensuring comprehensive coverage is challenging. A different approach is required, or a combination of approaches.

How should testing a compiler's parse error detection be managed? (How) can the compiler itself help this process?
**Tags:** compilers parsing compiler-checks testing
---
## 2 answers
### Answer by username_2 on 2023-06-18. Score: 6
I think there is actually a pretty straightforward way to achieve this, but it depends on the compiler being designed to make testing easy. Particularly, errors (and other diagnostics) must be structured data, not just strings, and the compiler needs an API which returns diagnostics in a data structure rather than directly printing them to stderr.

None of these things is particularly difficult to achieve. I'll use the compiler for my own language, Papyri, as an example:

* Diagnostics, including syntax errors, are represented as an enum type ([source](https://github.com/kaya3/papyri-rs/blob/331eaaa6e16df7e228de95ab3aa6e206aae7e0c5/src/errors/syntax_error.rs)).
* Diagnostics are collected into a list during compilation ([source](https://github.com/kaya3/papyri-rs/blob/331eaaa6e16df7e228de95ab3aa6e206aae7e0c5/src/errors/sink_base.rs#L113)), instead of being output immediately when they occur.
* Then, test cases for diagnostics can consist of an input as a string, and an enum variant for which diagnostic is expected ([source](https://github.com/kaya3/papyri-rs/blob/331eaaa6e16df7e228de95ab3aa6e206aae7e0c5/tests/tag.rs#L112); these examples use a macro to make the tests easier to write).

---

I'll run through your bullet points to discuss how this strategy accounts for them:

> there are many more ways for the code to be wrong than right, but not all of them are interesting;

A test suite for the compiler's diagnostics can be comprehensive if it covers every code path which emits a diagnostic. Having diagnostics represented by an enum makes it easier to ensure full coverage without writing excessively many tests for "uninteresting" cases which are already covered. In practice, many parse errors will only be emitted in one place; for diagnostics reported in multiple places, coverage can be ensured using the IDE's "find all occurrences" tool, or using a code coverage tool.

> a test program that's rejected for e.g. a type error instead of the intended parse error is still a wrong result; there can be multiple feasible parse errors arising from one input, but it should reliably produce the "right" one; and in the right place(s);

Each test passes if and only if the expected enum variant is present in the list after compilation; occurrences of other diagnostics don't affect the test result.

In the Papyri compiler, I'm not also testing that the diagnostic is associated with the correct source span, but that's mainly because this would make test-writing more difficult, and the test cases are simple enough that there is only one place that the expected diagnostic could occur.

So if the diagnostic occurs at all then it's very likely in the right place, and I don't feel the need to also test that it does occur in the right place. If you do think it would be worth it, though, then a test could be a triple of (source, expected enum variant, expected span).

> a compiler change that causes a different parse error to be produced is likely a problem; but error messages can be expected to change over time to be more useful to the programmer in ways that the semantics of a working program won't, but updating the entire test suite when that happens is fraught;

By using enum variants, the tests are stable with respect to changes in the wording of error messages, while still catching bugs where the wrong *kind* of diagnostic is emitted. Therefore there is no need to update the test suite when the wording of an error message changes, only when new kinds of diagnostic are introduced, or the conditions on which some kind of diagnostic should be reported are changed.

> both rejected and accepted inputs are important.

Accepted inputs (i.e. those without parse errors) will be covered by all the other test cases which test for a particular result instead of a particular diagnostic being emitted. I don't find it that useful to write test cases where the input is valid and the test passes only if no diagnostics are emitted; it's more useful to also require the test to pass if the output matches some expectation.

So yes, it's important to test that parse errors *aren't* emitted for valid inputs, but this is something you get "for free" when you test that valid inputs have correct compilation results. Therefore I don't think it needs to be part of the strategy for testing diagnostic reporting.
> **Comments:**
> **username_0** (2023-06-18): I buy the rest of this, but "A test suite can be comprehensive if it covers every diagnostic that the parser or compiler is able to emit." is a bit questionable, isn't it? It proves there's **a** way to produce each kind of error, but not more than that.  
> **username_2** (2023-06-18): @MichaelHomer That's a fair point. I would say in practice that there are very few kinds of parse error which can be emitted in more than one code path; at least, that's the case with my own language. If you want to be more rigorous then you can use the IDE's "find all occurrences" feature for each enum variant to ensure that each code path for each enum variant is covered; or you can use a code coverage tool to find code paths that aren't being tested by your existing test suite, and that will include the paths which emit diagnostics that you aren't testing for.  
---
### Answer by username_1 on 2023-06-18. Score: 3
[kaya3's excellent answer](https://languagedesign.stackexchange.com/a/1559/285) can be summarised as:

# Decouple identification of errors and reporting &

## Errors are Structured Data

Many of the same practices for good testing apply as for regular software engineering but there are a few additional considerations.

A few points I would add:

* To make generating new test cases easier (for users) you can add a flag to your interpreter or compiler to output the structured error information directly instead of the actual error messages.

## [Equivalence partitioning](https://en.wikipedia.org/wiki/Equivalence_partitioning)

You want tests that cover the space of possible behaviours with little or no overlap.

## [Coverage Analysis](https://en.wikipedia.org/wiki/Code_coverage)

* You can aim for near 100% line coverage of the code
* A much lower branch coverage is reasonable.

For a programming language you need to consider grammatical coverage.
E.g. [Syntax Based Parsing](https://www.cs.cornell.edu/courses/cs5154/2021sp/resources/SyntaxCoverage.pdf)

## Fuzzing

The next level of reliability up good coverage is via [fuzzing](https://en.wikipedia.org/wiki/Fuzzing).
Randomly mutate your programs to produce new and interesting errors.
(Bonus point if you can use the same mechanism for [genetic programming](https://en.wikipedia.org/wiki/Genetic_programming))

## [Grammar Fuzzing](https://github.com/Microsvuln/Awesome-Grammar-Fuzzing)

Combining grammatical coverage and fuzzing

## Formal Verification

The next level up is formal verfication or [Compiler correctness](https://en.wikipedia.org/wiki/Compiler_correctness). A few programming languages or subsets thereof have achieved this.
---
