1

I'm practicing unit testing (specifically Test-driven design or Red-Green-Refactor) while writing a recursive descent parser for a simple domain-specific language. In trying to unit test a method that takes in Tokens and Outputs a Syntax Tree, I've found that mocking the input is overly complex. I had thought my initial design for the public interface was testable; is this problem in the design of the public interface, or inherent to high-level data transformation tests?

My test simplified to show the basic interface...

[TestFixture]
public class ParserTests
{
    [TestFixture]
    public class Parser_ParseTests
    {
        ...
        [Test]
        public void Parser_Parse_IfTokenSourceIsNullThrowException()
        {
            Parser parser = new Parser ();
            TokenSource tokens = null;

            Action action = () => parser.Parse(tokens);

            Assert.Throws<System.NullReferenceException>(() => action.Invoke ());
        }
        ...
    }

}

Obviously, the tests I have a problem with are those that will need TokenSource filling with a large number of Tokens.

My first thought is that perhaps my test covers too much. Perhaps I should only mock and test that Tokens are requested from the Token Source, and leave the testing of Token transformations to dependent classes. This would leave a gap in my tests description of the purpose of this interface though, and make it reliant on other tests to validate it.

It could also be that my code isn't testable, but I'm struggling to see another way to structure it. I know I want an interface that turns an input into a Syntax Tree, and that I will split up the process into Tokenisation (of a string source) and parse the Tokens. Perhaps there shouldn't be a level of abstraction that knows about the Parsing of Tokens but not the Tokenisation?

To try and get ideas I have looked at the unit tests for Fitnesse, which I knew had good coverage and must transform complex data sets (Wiki code into HTML). I'm not sure whether it follows good practices I should emulate though. For example, BaseWikiPage seems to use a number of objects from the actual project (WikiPageUtil, PathParser etc) in order to produce test data.

Is this good practice? My main problem with it is that it requires me writing code related to lower level abstractions like Tokens that I wasn't ready to design yet. Also, the Test code requires me to write functional code first, which means writing other Unit tests first, implicitly making this test dependant on those. Basically, it prevents me writing this test at all.

I'd love to know both the real-world solution to these kinds of tests and the ideal solution. Or does my entire understanding of the purpose of this tests makes the question irrelevant?

  • 1
    "Obviously the tests I have a problem with are those that will need TokenSource filling with a large number of Tokens." could you explain why this is true ? – Steve Chamaillard Jun 8 '18 at 11:48
  • What's wrong with a bunch of [TestCase("...", ExpectedResult=AST(...)] (or equivalent reading input & output pairs from somewhere)? – Caleth Jun 8 '18 at 12:00
  • @SteveChamaillard: Because my problem is an ability to write certain tests. The test I showed has been written, and serves as an example of the very basic interface. – James Jun 8 '18 at 12:26
  • @Caleth: Reading input pairs from somewhere is the problem, I think. I'm not sure. Most of the tests of that form I came up with repeated testing functionality that will need to be tested at a lower level. – James Jun 8 '18 at 12:26
  • 1
    The rigidity of TDD is not always an advantage, especially for a parser. Generally speaking, ordinary automated testing is used for language development, especially when the language is in flux. – Frank Hileman Jun 8 '18 at 22:32
1

I suspect that where you are getting bricked is the process you are using for drawing your boundaries. See this talk by Gary Bernhardt.

Heuristic: pay attention to the way that data moves across boundaries, rather than tracking capabilities.

Taking an outside in approach, you are starting with a problem like:

Input -> AST

And have decomposed that problem into

Input -> data-structure-of[Token]
data-structure-of[Token] -> AST

So the problem testing a data structure with a large number of tokens is "just" the problem of constructing a lot of tokens in the test.

If you can stand to create them one at a time, great.

If data-structure-of[Token] is seriablizable, then an option would be to create a serialized data sample that gets loaded into memory by the test. You lose something on test clarity (because the data is separate from the test), but it moves some of the complexity around.

If Input is serializable, you can craft an input and have the test logic load that. Same separation issues as before, plus you probably end up using your parsing function in the test -- the entire thing begins to look more like an "end to end" test than a "unit" test.

This approach is still "test first" and "test driven". See, for example, this demonstration of the Mars Rover kata.

Another possibility is to build out a DSL that the test uses to construct data-structure-of[Token]. This is a common technique for managing data, often used to improve the readability of the test. So if "large number of tokens" features things like runs of deterministic patterns, then using the DSL can give you what you need without I/O or separating the data from the tests.

If that doesn't work... you might need to consider an API that allows you to split data-structure-of[Token] into multiple frames/batches. That is, the difficulty in testing may be trying to tell you that you need to expose a "fold"; which is to say you might need an API for creating the parser in an intermediate state.

Given : the parser has consumed these 100 tokens
When  : the parser consumes these 5 additional tokens
Then  : the right thing happens

If you can put the parser directly into the correct state (that is, seed it with a partially built AST and so on), then you can short cut to the actual test you want to run.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.