CodeCover

Add a new programming language



Preface

CodeCover is shipped with support for Java 1.4, Java 1.5 and VS COBOL 1985. These pages describe how to use CodeCover with another programming language.

Before we start to explain what you need and how you can integrate your programming language, it is import to understand our process of coverage measurement. Therefore, you can take a look at the design document – the chapter 2.1 Process chain gives an overview of the process: instrumentation, compilation and execution, analysing, creating the report (see the design document).

CodeCover is written in Java 1.5 and designed to support various programming languages. This is achieved by having strict interfaces. On the one side of these interfaces is the individual programming language. It has a special grammar and its semantic. On the other side of the interfaces are:

If you want to enable support for a new programming language, it is your task to write a collection of Java classes making your programming language compatible with these interfaces.

Although you can implement these interfaces in the order you want, it is recommended to use the approach we have used for Java – respectively COBOL. Why? Because we can describe this approach and we know, that it works.

This approach has the following steps:

Because examples are a very good way for learning, we use an imaginary programming language Xampil to explain the steps of our approach. Of course, this imaginary programming language has no compiler, so code in this language can not be executed. Moreover, this programming language – especially its grammar – is not complete. We just want to give you an overview, what you have to do in each step and how time-consuming each step might be for your programming language. To sum this up: we think that by explaining the required steps for Xampil, you learn, what you have to do for your programming language.

We provide a lot of source code examples that grow step by step. If you want to have a look at the final instrumenter, take a look at the download section at the end.

How Xampil looks like shows example.xpl:

// example.xpl
DECLARATION
    BOOLEAN b := FALSE

    INTEGER i := -1

    STRING characters := "unset"
PROGRAM
    i := 0

    IF TRUE THEN
        i := 1
    ELSE
        i := 0
    ENDIF

    WHILE ((i <> 0) AND (i <= 10)) DO
        i := i + 1
    ENDWHILE

    SWITCH i
        CASE 1 :
            characters := "i was 1"
        ENDCASE
        CASE 10 :
            characters := "i was 10"
        ENDCASE
        DEFAULT :
            characters := "i was not set to 1 or 10"
        ENDCASE
    ENDSWITCH

    FILE OVERWRITE "target.log" i
ENDPROGRAM

There in one requirement each programming language has to fullfill to be used with CodeCover:

Parser

The basis of the whole concept is a parser, that parses source files of your programming language. In addition to that, it builds up a syntaxtree of your source file. Later, this syntaxtree can be traversed by visitors. We use javacc and the Java Tree Builder for this purpose. They are both purely java and we used them successfully.

Grammar

To generate the parser, you need a grammar of your programming language. If you are not so advanced in building compilers and using grammars, this step might be a little bit difficult. The javacc grammars are based on BNF and regular expressions.

You can have a look at the javacc grammar repository. There is a list of grammars for the most important programming languages. Maybe, your programming language is in the list.

If not, you have to create an own grammar. We can not tell you how to do this in these chapters, but there is a documentation shipped with the javacc release.

At this point, we want to start with our example programming language Xampil. Therefore, we have provided a javacc grammar file for Xampil.

As you can see, the grammar reminds you of java code which is enriched by regular expressions and tags similar to XML. There are different sections in each grammar file.

A section for options

options {
  UNICODE_INPUT = true;
  ERROR_REPORTING = true;
  USER_CHAR_STREAM = true;
  STATIC = false;
  JDK_VERSION = "1.5";
  FORCE_LA_CHECK = true;
}

This tells the javacc parser generator, how to create the parser. Moreover some options affect the performance of the generated parser. Activated ERROR_REPORTING allows you to check, why a code file is rejected by the parser. A more verbose ParseException is thrown. But the performance decreases. The flag STATIC tells the generator, whether to have one static parser or instances of the parser. UNICODE_INPUT tells the parser to read Unicode instead of ASCII characters. The feature USER_CHAR_STREAM is needed later, so ensure that it is enabled. It tells the parser to use an interface as the CharStream instead of directly using a SimpleCharStream. All the options are explained in the javaccgrm.html of the javacc documentation.

A section for the Parser

Here you can give the parser class a name and you can put code that you want to add to the generated code.

PARSER_BEGIN(XampilParser)
package org.codecover.instrumentation.xampil.parser;

public class XampilParser
{/* you can paste you code here */}

PARSER_END(XampilParser)

A section for the tokens

[..]
SPECIAL_TOKEN :
{
    <SPACE_CHAR: " " | "\t" | "\f">
}
[..]
TOKEN :
{
    < PROGRAM: "PROGRAM" >
  | < ENDPROGRAM: "ENDPROGRAM" >

  | < IF: "IF" >
  | < THEN: "THEN" >
  | < ELSE: "ELSE" >
  | < WHILE: "WHILE" >
  | < DO: "DO" >
  | < END: "END" >
}

The tokens can be subdivided into TOKEN, SPECIAL_TOKEN, SKIP and MORE. The skip tokens are just ignored by the parser. The special tokens are not used for the BNF productions, but added to the generated tokens. The real Tokens are used for the BNF. Code created by the Java Tree Builder will transform these tokens to nodes of a syntaxtree.

Important hint: ensure, that your grammar has declared all kind of white spaces (" ", "\n", "\r", "\t", ...) as SPECIAL_TOKENs rather than SKIP tokens. This is important for the offset calculation and reproduction.

A section for the productions

void IfStatement():
{}
{
    <IF> BooleanExpression() <THEN> <EOL>
        ( Statement() )*
    (
      <ELSE> <EOL>
        ( Statement() )*
    )?
    <END> <EOL>
}
[..]

The productions of a javacc grammar describe BNF productions. You can use identifiers of other productions or predefined tokens within a production declaration.

The syntax of the javacc grammar file is explained in the javaccgrm.html of the javacc documentation.

Test the grammar

After you have created the grammar, you have to ensure, that it is correct. This can be done by simply invoking the javacc parser generator. It will tell you, if there are ParseExceptions. If you have not downloaded it yet, you have to do it now. Look at javacc.dev.java.net and download the javacc 4.0 parser generator. After you have extracted the zip file, you will find a doc folder with the javacc documentation and a bin folder with the javacc.jar. Now you can run the parser generator:

java -cp javacc-4.0/bin/lib/javacc.jar javacc
     -output_directory=src/org/codecover/instrumentation/xampil/parser/
      xampil.jj

If your grammar is correct, you will see an output like this:

Java Compiler Compiler Version 4.0 (Parser Generator)
  (type "javacc" with no arguments for help)
Reading from file xampil.jtb.jj . . .
Note: UNICODE_INPUT option is specified. Please make sure you create
  the parser/lexer using a Reader with the correct character encoding.
File "TokenMgrError.java" does not exist.  Will create one.
File "ParseException.java" does not exist.  Will create one.
File "Token.java" does not exist.  Will create one.
File "SimpleCharStream.java" does not exist.  Will create one.
Parser generated with 0 errors and 0 warnings.

If there are warnings or errors, you have to solve them before continuing with the next step!

We recommend to use a script – such as apache ant – to run the javacc command. Why? You will see that you have to run the parser generator very often when you adapt you grammar. By using a script, you needn't type in the commands and you are sure, that you use the same command every time.

To test the parser, you can use a short java main method like this:

File targetFile = new File("example.xpl");
FileInputStream fileInputStream = new FileInputStream(targetFile);
InputStreamReader inputStreamReader = new InputStreamReader(
        fileInputStream, Charset.forName("UTF-8"));
BufferedReader bufferedReader = new BufferedReader(
        inputStreamReader);
XampilParser parser = new XampilParser(bufferedReader);
parser.CompilationUnit();
bufferedReader.close();

What is this code doing? It is just parsing the file example.xpl with respect to the given grammar. We have not provided any code, that should be executed, when a token is found. This will do the Java Tree Builder.

Instrumentable item counter

This section is needed because of the special properties of our programming language Xampil. Although you might not understand every detail of this section, it is the best way to apply these changes now.

The reason for all this trouble lies in the declaration of possible counters. We have to declare additional integer variables to count the execution of statements and branches. Xampil does not allow to declare variables when you need them, you have to declare them in the DECLARATION section. In the consequence we get into trouble when instrumenting: we have to declare counting variables before we get to know how much variables we need. There are a number of solutions for this problem. Two of them are:

For being more performat, we choose the second approach. This requires changes in the grammar, before going on to the next step. If you need this approach for your programming language too, we recommend to do these changes now. If you have a programming language like Java, you can skip this step. Why? You can position declarations like this:

public class Person {
    String name, address;

    public Person(String name) {
        this.name = name;
        statementCounter[0]++;
        this.address = null;
        statementCounter[1]++;
    }

    public static int statementCounter = new int[2];
}

The counters can be declared after all statements where visited. For this reason, you can count the required counters and set the number afterwards.

But back to Xampil, where this method is not working. We will add a class that is counting the statements, branches, loops and boolean expressions in the source file. This is done during the parsing and will be logged in a special object: InstrumentableItemCounter. You have to put this file into the parser folder.

Now we want to adapt the grammar because we have to add some statements to notify the InstrumentableItemCounter. Some examples are shown in the following extract. The whole file is called xampil.counter.jj.

[..]

public class XampilParser
{ private InstrumentableItemCounter counter = new InstrumentableItemCounter(); }

[..}

void CompilationUnit(InstrumentableItemCounter counter):
{ this.counter = counter; }
{
    Declaration()
    Program()
    ( <EOL> )?
    <EOF>
    { this.counter = new InstrumentableItemCounter(); }
}

[..]

void Statement():
{ this.counter.incrementStatementCount(); }
{
    AssignmentStatement()
  | IfStatement()
  | WhileStatement()
  | SwitchStatement()
  | FileStatement()
}

[..]

void IfStatement():
{}
{
    <IF> Expression() <THEN> <EOL>
    { this.counter.incrementBranchCount(); }
        ( Statement() )*
    (
        <ELSE> <EOL>
            { this.counter.incrementBranchCount(); }
            ( Statement() )*
    )?
    <ENDIF> <EOL>
}

[..]

void WhileStatement():
{
    this.counter.incrementLoopCount();
}

[..]

void SwitchStatement():
{}
{
    <SWITCH> <IDENTIFIER> <EOL>
    (
        <CASE> Expression() <COLON> ( <EOL> )?
            { this.counter.incrementBranchCount(); }
            ( Statement() )*
        <ENDCASE> <EOL>
    )+
    (
        <CASE_DEFAULT> <COLON> ( <EOL> )?
            { this.counter.incrementBranchCount(); }
            ( Statement() )*
        <ENDCASE> <EOL>
    )?
    <ENDSWITCH> <EOL>
}

[..]

The counter for the conditions is a little bit more complex. We do not only need the number of conditions but the number of basic boolean terms for each condition. Here we use an IntegerContainer, that we hand over to the Expression() production. This collects the number of basic booleans recursively. Afterwards, we know which condition has how many basic booleans. This is only an extract of the changes:

public class XampilParser
{
    private InstrumentableItemCounter counter = new InstrumentableItemCounter();

    static interface IntegerContainer {
        public void set(int value);
        public int get();
    }

    static class RealIntegerContainer implements IntegerContainer {
        int value = 0;

        public void set(int value) {
            this.value = value;
        }

        public int get() {
            return this.value;
        }
    }

    static class DummyIntegerContainer implements IntegerContainer {
        public void set(int value) {}

        public int get() {
            return 0;
        }
    }

    static final DummyIntegerContainer DUMMY_CONTAINER = new DummyIntegerContainer();
}

[..]

void AssignmentStatement():
{}
{
    <IDENTIFIER> <ASSIGN> Expression(DUMMY_CONTAINER) <EOL>
}

void IfStatement():
{
    RealIntegerContainer basicBooleanCounter = new RealIntegerContainer();
}
{
    <IF> Expression(basicBooleanCounter)
    { this.counter.incrementConditionCount(basicBooleanCounter.get()); }
    <THEN> <EOL>

[..]

void Expression(IntegerContainer basicBooleanCounter):
{}
{
   OrExpression(basicBooleanCounter)
}

[..]

void EqualityExpression(IntegerContainer basicBooleanCounter):
{
    int basicBooleanCountBefore = basicBooleanCounter.get();
}
{
    RelationalExpression(basicBooleanCounter)
    ( ( <EQ> | <NEQ> ) RelationalExpression(basicBooleanCounter)
      { basicBooleanCounter.set(basicBooleanCountBefore + 1); } ) ?
}

[..]

void BasicExpression(IntegerContainer basicBooleanCounter):
{}
{
    <IDENTIFIER> { basicBooleanCounter.set(basicBooleanCounter.get() + 1); }
  | <INTEGER_LITERAL>
  | <STRING_LITERAL>
  | <TRUE>
  | <FALSE>
  | <LPAREN> Expression(basicBooleanCounter) <RPAREN>
}

After we have added this feature and regenerated the parser using javacc, we can pimp up our main method:

File targetFile = new File("example.xpl");
FileInputStream fileInputStream = new FileInputStream(targetFile);
InputStreamReader inputStreamReader = new InputStreamReader(
        fileInputStream, Charset.forName("UTF-8"));
BufferedReader bufferedReader = new BufferedReader(
        inputStreamReader);
XampilParser parser = new XampilParser(bufferedReader);
InstrumentableItemCounter counter = new InstrumentableItemCounter();
parser.CompilationUnit(counter);
bufferedReader.close();

System.out.println("Statements:  " + counter.getStatementCount());
System.out.println("Branches:    " + counter.getBranchCount());
System.out.println("Loops:       " + counter.getLoopCount());
int conditionCount = counter.getConditionCount();
System.out.println("Conditions:  " + conditionCount);
for (int i = 0; i < conditionCount; i++) {
    System.out.println("Condition " + i + ": " + counter.getBasicBooleanCount(i));
}

Now we see the following output for exampel.xpl:

Statements:  12
Branches:    6
Loops:       1
Conditions:  2
Condition 0: 0
Condition 1: 2

Java Tree Builder (JTB)

You have created a javacc grammar of your programming language and have successfully generated a simple parser. Now you need the JTB. You will receive a jtb132.jar, which is everything you need. Now you can run the JTB:
java -jar jtb132.jar
     -p org.codecover.instrumentation.xampil // the package of the generated files
     -o xampil.jtb.jj                        // the output grammar
     -printer                                // generate a TreeDumper
     -jd                                     // JavaDoc-friendly comments
     -pp                                     // parent pointers
     -tk                                     // special tokens into the tree
     xampil.counter.jj                       // the source grammar

After you have run the command, you will see an output like this:

JTB version 1.3.2
JTB:  Reading from xampil.counter.jj...
JTB:  Input file parsed successfully.
JTB:  "xampil.jtb.jj" generated to current directory.
JTB:  Syntax tree Java source files generated to directory "syntaxtree".

JTB:  "GJVisitor.java" generated to directory "visitor".
JTB:  "Visitor.java" generated to directory "visitor".
JTB:  "GJNoArguVisitor.java" generated to directory "visitor".
JTB:  "GJVoidVisitor.java" generated to directory "visitor".
JTB:  "GJDepthFirst.java" generated to directory "visitor".
JTB:  "DepthFirstVisitor.java" generated to directory "visitor".
JTB:  "GJNoArguDepthFirst.java" generated to directory "visitor".
JTB:  "GJVoidDepthFirst.java" generated to directory "visitor".

JTB:  "TreeDumper.java" generated to directory "visitor".
JTB:  "TreeFormatter.java" generated to directory "visitor".

0 warnings, 0 errors.

What has the JTB done? It has parsed the xampil.jj grammar file. For every production of the BNF, a syntaxtree node is generated. The syntaxtree is a collection of class files in the directory syntaxtree, that all implement the interface Node.

Then there is a directory visitor. It contains visitors to traverse the syntaxtree nodes by using the visitor design pattern.

Last not least the original grammar file is annotated to xampil.jtb.jj, which has about four times the size of the original one. JTB has added code to the original grammar file to tell the parser how to build up the syntaxtree nodes for every production that is found.

You can have a look at these files, but they can do nothing without the parser.

Create the final parser

Now you have to generate the final parser. This is done by using the exact same command as used for the test – just with another grammar file:
java -cp javacc-4.0/bin/lib/javacc.jar javacc
     -output_directory=src/org/codecover/instrumentation/xampil/parser/
      xampil.jtb.jj

Now you can test this parser with a short java main method:

File targetFile = new File("example.xpl");
FileInputStream fileInputStream = new FileInputStream(targetFile);
InputStreamReader inputStreamReader = new InputStreamReader(
        fileInputStream, Charset.forName("UTF-8"));
BufferedReader bufferedReader = new BufferedReader(
        inputStreamReader);
XampilParser parser = new XampilParser(bufferedReader);
InstrumentableItemCounter counter = new InstrumentableItemCounter();
CompilationUnit compilationUnit = parser.CompilationUnit(counter);
Visitor visitor = new TreeDumper(System.out);
visitor.visit(compilationUnit);

bufferedReader.close();

If everything is working, you should see the code of the source file in the standard output. But what is this main method doing? First, the source file is parsed. But this time, a syntaxtree is generated. The entry point of the BNF is the token CompilationUnit(). So the root node of our generated syntaxtree is an object of the class with the same name: CompilationUnit.

As said before, visitors are used to traverse the syntaxtree. Each visitor is given a root node. Then the visitor visits all the children of the root node and their children recursively. The leaves of the syntaxtree are NodeToken. These are nodes having just an image like "IF", "ENDPROGRAM" or ">=". Each visitor can decide what should be done, when visiting a node. The TreeDumper used in this main method just prints out all the NodeToken to the standard output. This is why you see the source file in your shell.

Adapt the parser

To use the parser effectively, you have to change a number of source files manually. This step is needed to provide all the information needed for the further steps. Ensure that you can easily reapply these changes if you have to generate the parser again and overwrite the manual changes. A combination of a version control system and an ant script seems to be perfect for our approach. We recommend to make following changes in an atomic step, because the code files won't compile during the changes.

You have to use a CharStream, that differs a little bit to the standard character stream generated by javacc. Furthermore you have to use an instance of CharStream, that fits to the new requirements: SimpleCharStream. All files you have to copy – or overwrite – are listed below. They are ordered by target folder:

The rest of the changes, you have to do manually. First you have to go to XampilParser and change two lines in the inner class JTBToolkit. The following constructor call occurs twice. Change

new NodeToken(t.image.intern(), t.kind, t.beginLine, t.beginColumn,
              t.endLine, t.endColumn)

into

new NodeToken(t.image.intern(), t.kind, t.beginLine, t.endLine,
              t.beginColumn, t.endColumn, t.beginOffset, t.endOffset)

Pay attention to the change of the parameter order.

The last change considers the XampilParserTokenManager. Search for the method jjFillToken(). There you have to add two lines:

t.beginLine = input_stream.getBeginLine();
t.beginColumn = input_stream.getBeginColumn();
t.endLine = input_stream.getEndLine();
t.endColumn = input_stream.getEndColumn();
t.beginOffset = input_stream.getBeginOffset();
t.endOffset = input_stream.getEndOffset();
return t;

Why do you have to change all these classes? The approach we have made to describe the position within a source file is based on offsets. This means, that all the tokens have a start and an end offset. The ordinary SimpleCharStream does not provide such information. So we had to add this feature. The XampilParserTokenManager creates tokens. This token manager has to save the current offset information in an object of the type Token. The JTBToolkit, that transforms Token into NodeToken, has to save these information by handing them over to the constructor of NodeToken. All these changes are important for the creation of MAST elements (see MAST).

If you try to compile the org.codecover.instrumentation.xampil folder now, there should be no compiler errors. If you want to run our main method, you have to do some changes here too:

File targetFile = File("example.xpl");
FileInputStream fileInputStream = new FileInputStream(targetFile);
InputStreamReader inputStreamReader = new InputStreamReader(
        fileInputStream, Charset.forName("UTF-8"));
BufferedReader bufferedReader = new BufferedReader(
        inputStreamReader);
CharStream charStream = new SimpleCharStream(bufferedReader);
XampilParser parser = new XampilParser(charStream);
CompilationUnit compilationUnit = parser.CompilationUnit();
PrintWriter writer = new PrintWriter(System.out);
Visitor visitor = new TreeDumper(writer);
visitor.visit(compilationUnit);
writer.flush();

bufferedReader.close();

Instrumenter

After creating and adapting the parser you have to create the instrumenter. When you finished this chapter you will have an instrumenter, an instrumenter descriptor and an instrumentation visitor. All these components will be integrated into CodeCover, so it should be possible to call your instrumenter from the batch interface of CodeCover. But the instrumenter we build in this chapter won't instrument a file, it just puts out the source file. The real instrumentation is topic of the next chapter. This chapter contains essential preparatory work that has to be done before you can start with the real instrumentation.

CodeCover contains some interfaces and abstract classes you should know about. In this chapter we discuss the most important ones and give an example for our Xampil programming language.

Instrumenter

First of all, you have to create an instrumenter class which extends org.codecover.instrumentation.instrumenter class. The methods instrumentThis, getPackageHierarchyLevelType and allowsFileListInstrumentation needs to be implemented. Here is an example of Instrumenter.java for the Xampil programming language.

package org.codecover.instrumentation.xampil;

class Instrumenter extends org.codecover.instrumentation.Instrumenter {

    public Instrumenter() {
        super();
    }

    protected void instrumentThis(Reader source,
            Writer target,
            MASTBuilder database,
            SourceFile sourceFile,
            HierarchyLevelContainer hierarchyLevelContainer,
            String testSessionContainerUID,
            Map instrumenterDirectives) throws ParseException,
            IOException {
        ...
    }

    protected HierarchyLevelType getPackageHierarchyLevelType(MASTBuilder database) {
        return HierarchyLevelTypes.getSourceFileType(database);
    }

    public boolean allowsFileListInstrumentation() {
        return false;
    }
}

The allowsFileListInstrumentation method states whether or not this instrumenter allows the instrumentation of more than one source file at a run. The instrumenter for our Xampil programming language does not allow it, that is why the method returns false.

To explain the use of the getPackageHierarchyLevelType method you need some understanding of the hierarchy level concept of CodeCover which is described later in this guide. At this point we just set the hierarchy level to the SourceFileType. We will create the class HierarchyLevelTypes in the next subsection.

The instrumentThis method controls the instrumentation process. That means it starts the parsing of the source file and the traversal of the syntax tree. Before we go further into this we put our focus on the parameters.

Target and source are easy to understand. The target is the writer that writes the instrumented file and the source is the reader that reads the original source file.

More complex is the MASTBuilder. CodeCover transforms the parsed source code into an own syntax tree which we named MAST. This syntax tree contains a lot of special information like offsets or coverage data. It is your job to create the MAST objects during the instrumentation. There is a whole chapter about MAST at the end of this guide.

The SourceFile is a container for the source code and the name of the file. It is part of the CodeCover database. This object is needed during the instrumentation to create objects which contain the location of a certain token in the source file.

Every test session container has a unique ID. This ID is needed as part of the coverage log file and for this reason have to be given into the instrumentation process.

The map of instrumenter directives contains the name of all registered directives and a corresponding object which could be used for a specific behavior of the instrumentation.

As it is stated above, the instrumentThis method controls the instrumentation process, so you have to implement this method. In the last chapter you have seen how to parse and traverse the source file. Some of this code we will need now again. Here is an example of the instrumentThis method for the Xampil programming language.

SimpleCharStream simpleCharStream = new SimpleCharStream(source);
XampilParser xampilParser = new XampilParser(simpleCharStream);
CompilationUnit compilationUnit = xampilParser.CompilationUnit();
PrintWriter targetPrintWriter = new PrintWriter(target);
InstrumentationVisitor instrumentationVisitor = new InstrumentationVisitor(
    targetPrintWriter, database, sourceFile, hierarchyLevelContainer,
    testSessionContainerUID);
instrumentationVisitor.visit(compilationUnit);
targetPrintWriter.flush();

After parsing the source code an instrumentation visitor object is created. This class is explained later in this chapter. Afterwards we start the traversal.

HierarchyLevel

The hierarchy levels are needed for programming languages that structures the program into packages and files like Java. Our Xampil language don't need more than one hierarchy level, the source file level. In the instrumenter class we used a class named HierarchyLevelTypes. This class provides the HierarchyLevelType object for source files and have to be written by you. Here is an example of HierarchyLevelTypes.java for the Xampil programming language.

package org.codecover.instrumentation.xampil;
public class HierarchyLevelTypes {
    private static final String SOURCE_FILE_INTERN = "sourceFile";
    private static final String SOURCE_FILE = "Xampil source file";
    private static final String PROGRAM_INTERN = "program";
    private static final String PROGRAM = "program";
    private static HierarchyLevelType sourceFile = null;
    private static HierarchyLevelType program = null;

    public static HierarchyLevelType getSourceFileType(MASTBuilder builder) {
        if (sourceFile == null) {
            return sourceFile = builder.createHierarchyLevelType(SOURCE_FILE,
                    SOURCE_FILE_INTERN);
        }
        return sourceFile;
    }

    public static HierarchyLevelType getProgramType(MASTBuilder builder) {
        if (program == null) {
            return program = builder.createHierarchyLevelType(PROGRAM,
                    PROGRAM_INTERN);
        }
        return program;
    }
}

As you can see, the class contains only two methods. We have already used the method getSourceFileType in the instrumenter class. This method creates a HierarchyLevelType for source files and returns that object. The other method getProgramType will be used later in the InstrumentationVisitor (see PROGRAM unit).

For our Xampil programming language this is all about hierarchy levels you need to do. If you want to learn more about it you may have a look at the advanced section at the end of this guide.

InstrumenterDescriptor

The next step is to create the InstrumenterDescriptor class which should be extended from org.codecover.instrumentation.InstrumenterDescriptor. The instrumenter descriptor contains information about the corresponding instrumenter, for example the author, the name of the programming language, the charset, the instrumenter directives or the supported code coverage criteria. CodeCover asks the descriptor if the instrumenter matches the programming language the user wants to instrument. Here is an example of InstrumenterDescriptor.java for the Xampil programming language.

package org.codecover.instrumentation.xampil;
public class InstrumenterDescriptor extends
    org.codecover.instrumentation.InstrumenterDescriptor {

    private static final String INSTRUMENTER_UNIQUE_KEY = "CodeCover_Xampil_2007";
    private static final String LANGUAGE = "Xampil 2007";
    private static final Pattern NAME_PATTERN = Pattern.compile("Xampil(( )?(20)?07)?",
            Pattern.CASE_INSENSITIVE);
    private static final String DESCRIPTION = "Instrumenter for Xampil.";
    private static final String AUTHOR = "Author of this guide";
    private static final Charset DEFAULT_CHARSET = Charset.defaultCharset();

    public InstrumenterDescriptor() {
        super(INSTRUMENTER_UNIQUE_KEY);
        super.setLanguageName(LANGUAGE);
        super.setDescription(DESCRIPTION);
        super.setAuthor(AUTHOR);
        super.setDefaultCharset(DEFAULT_CHARSET);
    }

    @Override
    public boolean isLanguageSupported(String languageNameToCheck) {
        return NAME_PATTERN.matcher(languageNameToCheck).matches();
    }

    @Override
    protected Instrumenter getInstrumenter() {
        return new org.codecover.instrumentation.xampil.Instrumenter();
    }

    @Override
    public boolean accept(File file) {
        return FileTool.getExtension(file).equals("xpl");
    }
}

Most part of the code should be understandable. First, we set all the information like author or criteria. Afterwards we have to override some methods. The getInstrumenter returns an instance of a instrumenter child class, that fits to the information provided by this descriptor. With the accept method you can decide which files should be excepted by the instrumenter for instrumentation. In the case of Xampil we choose the file extension "xpl". FileTool is a utility class shipped by CodeCover. It is in the org.codecover.model.utils.file package.

As you may have noticed, the name is realized as pattern, because that way it is easier to check whether the instrumenter supports a certain programming language or not. In addition, the user can type in Xampil in upper case or lower, it may be Xampil with 2007 or without and a lot of other typing the user likes. The isLanguageSupported method enables CodeCover to ask the instrumenter descriptor for the language support the instrumenter supports.

Criteria

There are a lot of code coverage criteria defined in books and papers. We decided to use the most important and most known criteria. That are the statement, branch, condition and loop coverage. In the package org.codecover.model.utils.criteria you can find an abstract criterion class, you should use if you want to write your own criteria, and the implementation of the four criteria.

Back on our example language we decided to show you all four criteria. To inform CodeCover that your instrumenter is able to instrument a certain criterion you have to use the addSupportedCriteria method of the instrumenter descriptor class. Add the following lines into the constructor of our InstrumenterDescriptor class.

super.addSupportedCriteria(StatementCoverage.getInstance());
super.addSupportedCriteria(BranchCoverage.getInstance());
super.addSupportedCriteria(ConditionCoverage.getInstance());
super.addSupportedCriteria(LoopCoverage.getInstance());

InstrumentationVisitor

In the instrumentThis method of our instrumenter class we create an instrumentation visitor. This is the main class in the instrumentation process. At this point of the guide we just need a basic class with a constructor to reach the goal. Here is an example of InstrumentationVisitor.java for the Xampil programming language.

package org.codecover.instrumentation.xampil.visitor;
public InstrumentationVisitor(PrintWriter writer,
                              MASTBuilder builder,
                              SourceFile sourceFile,
                              HierarchyLevelContainer hierarchyLevelContainer,
                              String testSessionContainerUID) {
    super(writer);
    this.builder = builder;
    this.sourceFile = sourceFile;
    this.hierarchyLevelContainer = hierarchyLevelContainer;
    this.testSessionContainerUID = testSessionContainerUID;
}

Now you are ready to start your instrumenter by CodeCover. The only thing you have to do is packing all the files into a jar-file and adding this file to the java class path. It should be possible to start the Xampil instrumenter by giving "xampil" to the CodeCover -l option.

Instrumentation

Design the coverage measurement

Coverage data

Before you start to implement the instrumentation, you have to get to know, how you are going to instrument. In other words: you have to design how you want to collect coverage data. Coverage data can be measured for statements, branches, loops and boolean expressions. Coverage data is just a number, that represents, how often a statement is executed or a branch is entered. An element is called covered, if it is executed at least once.

You can decide, which criteria you want to instrument. This affects, which coverage metrics you can calculate. For example the coverage metric org.codecover.metrics.coverage.StatementCoverage needs the criteria org.codecover.model.utils.criteria.StatementCoverage instrumented in the source files. Then the metric can calculate, how many statements are covered – executed at least once – and which statements are not covered.

CodeCover has already implemented the following criteria for the programming languages Java and COBOL:

If you have questions understanding these terms, you can have a look in the Specification. The glossary at the end of the specification explains all these terms.

We now explain theoretically the instrumentation approach for all four coverage criteria. The final implementation is considered afterwards.

Statement coverage

The coverage measurement can be achieved by using counters. This is a very simple method, but it leads to a successful coverage measurement. Now you can start to think of your programming language. Create a small example program with as many language constructs, as you can think of. Now try to add counters after every statement, you want to measure coverage of.

An example for instrumentation of statement coverage of our exampel.xpl is shown in exampel.instr-st.xpl. The changes to the original source file are highlighted.

// example.instr-st.xpl
DECLARATION
    BOOLEAN b := FALSE

    INTEGER i := -1

    STRING characters := "unset"

    INTEGER countSt1 := 0
    INTEGER countSt2 := 0
    INTEGER countSt3 := 0
    INTEGER countSt4 := 0
    INTEGER countSt5 := 0
    INTEGER countSt6 := 0
    INTEGER countSt7 := 0
    INTEGER countSt8 := 0
    INTEGER countSt9 := 0
    INTEGER countSt10 := 0
    INTEGER countSt11 := 0
PROGRAM
    i := 0
    countSt1 := countSt1 + 1

    IF TRUE THEN
        i := 1
        countSt2 := countSt2 + 1
    ELSE
        i := 0
        countSt3 := countSt3 + 1
    ENDIF
    countSt4 := countSt4 + 1

    WHILE ((i <> 0) AND (i <= 10)) DO
        i := i + 1
        countSt5 := countSt5 + 1
    ENDWHILE
    countSt6 := countSt6 + 1

    SWITCH i
        CASE 1 :
            characters := "i was 1"
            countSt7 := countSt7 + 1
        ENDCASE
        CASE 10 :
            characters := "i was 10"
            countSt8 := countSt8 + 1
        ENDCASE
        DEFAULT :
            characters := "i was not set to 1 or 10"
            countSt9 := countSt9 + 1
        ENDCASE
    ENDSWITCH
    countSt10 := countSt10 + 1

    FILE OVERWRITE "target.log" i
    countSt11 := countSt11 + 1
ENDPROGRAM

As you can see, for every basic statement a counter is declared. It is set to zero in its declaration. After the related statement, each counter is incremented. This manual procedure might be a little bit time-consuming, but it gives answers to the following questions:

Branch coverage

Now we consider the branches. Branches occur in the program flow at branching statements like if or switch. A branch is covered, if it is entered at least once. To get to know when a branch is entered, we use counters too. The statement and branch instrumentation of exampel.xpl is shown in exampel.instr-br.xpl:

// example.instr-br.xpl
DECLARATION
    [..]

    INTEGER countBr1 := 0
    INTEGER countBr2 := 0
    INTEGER countBr3 := 0
    INTEGER countBr4 := 0
    INTEGER countBr5 := 0
PROGRAM
    [..]

    IF TRUE THEN
        countBr1 := countBr1 + 1
        i := 1
        countSt2 := countSt2 + 1
    ELSE
        countBr2 := countBr2 + 1
        i := 0
        countSt3 := countSt3 + 1
    ENDIF

    [..]

    SWITCH i
        CASE 1 :
            countBr3 := countBr3 + 1
            characters := "i was 1"
            countSt7 := countSt7 + 1
        ENDCASE
        CASE 10 :
            countBr4 := countBr4 + 1
            characters := "i was 10"
            countSt8 := countSt8 + 1
        ENDCASE
        DEFAULT :
            countBr5 := countBr5 + 1
            characters := "i was not set to 1 or 10"
            countSt9 := countSt9 + 1
        ENDCASE
    ENDSWITCH

    [..]
ENDPROGRAM

Loop coverage

How is loop coverage meant? Loop coverage considers looping statements like while, repeat until or for. The loop coverage criterion divides the program flow at looping statements into:

The related metric can use these information to tell you, for example that a loop body of a specific loop has never been skipped. The coverage data is again collected by counters. But this time, we need a temporary variable to count the number of loops, a loop body is entered. The statement, branch and loop instrumentation of exampel.xpl is shown in exampel.instr-lo.xpl:

// example.instr-lo.xpl
DECLARATION
    [..]

    INTEGER countLo1_temp := 0
    INTEGER countLo1_0 := 0
    INTEGER countLo1_1 := 0
    INTEGER countLo1_2 := 0
PROGRAM
    [..]

    countLo1_temp := 0
    WHILE ((i <> 0) AND (i <= 10)) DO
        countLo1_temp := countLo1_temp + 1
        i := i + 1
        countSt5 := countSt5 + 1
    ENDWHILE
    SWITCH countLo1_temp
        CASE 0 :
            countLo1_0 := countLo1_0 + 1
        ENDCASE
        CASE 1 :
            countLo1_1 := countLo1_1 + 1
        ENDCASE
        DEFAULT :
            countLo1_2 := countLo1_2 + 1
        ENDCASE
    ENDSWITCH

    [..]
ENDPROGRAM

Condition Coverage

Condition coverage is a very interesting topic, because there are a number of criteria that all consider the evaluation of boolean terms. They vary in the definition, when a basic boolean term is called covered. We have to introduce the term "basic boolean term", which is a boolean expression that can not be subdivided into other boolean terms. Where a = 4 AND NOT FALSE can be subdivided, a = 4 or vector.isEmpty() can not.

Different kinds of condition coverage vary in the following ways to decide whether or not a basic boolean term is covered:

To sum this up: we had to introduce a complex model of the boolean terms. When using this model after the execution, we can calculate nearly every condition coverage metric that is is used in common. Therefore, we have to describe the result of every basic boolean term for every evaluation of the whole condition. We distinguish the results of a basic boolean term the following:

For being very specific for every programming language, the condition coverage approach differs too. We now describe the approach for Xampil, that can be used, if the evaluation of boolean terms has no side effects and short circuit semantic is not used. For another approach you can have a look in the design document in Appendix A: "Formal Proof Of Conditional Coverage Instrumentation".

The statement, branch, loop and conditional instrumentation of exampel.xpl is shown in exampel.instr-co.xpl:

// example.instr-co.xpl
DECLARATION
    [..]

    BOOLEAN countCo1_temp1
    BOOLEAN countCo1_temp2
    INTEGER countCo1_1010 := 0
    INTEGER countCo1_1011 := 0
    INTEGER countCo1_1110 := 0
    INTEGER countCo1_1111 := 0
PROGRAM
    [..]
    countCo1_temp1 := i <> 0
    countCo1_temp2 := i <= 10
    IF countCo1_temp1 THEN
        IF countCo1_temp2 THEN
            countCo1_1111 := countCo1_1111 + 1
        ELSE
            countCo1_1110 := countCo1_1110 + 1
        ENDIF
    ELSE
        IF countCo1_temp2 THEN
            countCo1_1011 := countCo1_1011 + 1
        ELSE
            countCo1_1010 := countCo1_1010 + 1
        ENDIF
    ENDIF
    WHILE ((countCo1_temp1) AND (countCo1_temp2)) DO
        countLo1_temp := countLo1_temp + 1;
        i := i + 1
        countSt5 := countSt5 + 1
    ENDWHILE

    [..]
ENDPROGRAM

As you can see, we need a lot of code for instrumentation and it is very time-consuming to do this by hand. What have we done in these lines? We have substituted the evaluations in the WHILE statement by BOOLEAN variables, which are evaluated before. Then we combine the states of the two BOOLEAN variables by using an IF cascade. Hereby, we can distinguish four different states of the whole expression:

Why is the variable for example called countCo1_1110? By the binary decoding 1110, we describe that:

This convention is needed later again.

Note that the boolean expression of the if is not instrumented, because it is always TRUE and contains no basic boolean term. FALSE is for us just a boolean operator with arity zero.

By counting all the four states separately, we can afterwards count nearly every condition coverage metric and get to know the value of the whole condition by reproducing the AND evaluation. All in all this instrumentation is the most complex and therefore explained at the end.

Doing all these instrumentations manually in your programming language for the four coverage criteria is very important. You make fundamental decisions that should be made before starting to implement the instrumentation! Moreover, you get to know some problems of your programming language that make the instrumentation more difficult and it is a good way to handle special cases. Finally you can check your instrumented file against the automatically instrumented file, that you will hopefully receive at the end of this chapter.

The manipulator concept

Before we go on with the automatic instrumentation, we want to explain the manipulator concept. This concept is used to delegate all the changes, that should be made by the InstrumentationVisitor. The InstrumentationVisitor gets four Manipulators, one for each criterion but does not know what the Manipulators manipulate. This is a good practice to hide implementation details and we have found a variant how to skip the manipulation for a criterion. This feature is needed, because the user can select which criteria he wants to instrument and which not. All in all the InstrumentationVisitor will know at which positions which manipulator is called for manipulation, but only the specific manipulator will know whether to instrument and what to instrument.

So we create a sub package manipulators in the xampil package and an interface for all manipulators: Manipulator:

package org.codecover.instrumentation.xampil.manipulator;

import java.io.PrintWriter;

public interface Manipulator {
    public void setWriter(PrintWriter writer);
}

Than we create an abstract class AbstractDummyManipulator, which will be used by all manipulators, that just implement their interface but do not manipulate anything, because the related criterion is not selected for instrumentation:

package org.codecover.instrumentation.xampil.manipulator;

import java.io.PrintWriter;

public abstract class AbstractDummyManipulator implements Manipulator {
    public void setWriter(PrintWriter writer) {}
}

The next abstract class is the AbstractDefaultManipulator, that will be inherited by all classes that have manipulation tasks to do:

package org.codecover.instrumentation.xampil.manipulator;

import java.io.PrintWriter;

public abstract class AbstractDefaultManipulator implements Manipulator {
    private PrintWriter writer = null;

    public void setWriter(PrintWriter writer) {
        this.writer = writer;
    }

    protected PrintWriter getWriter() {
        return this.writer;
    }
}

Now you have to create four empty interfaces – one for each criterion. For example StatementManipulator:

package org.codecover.instrumentation.xampil.manipulator;

public interface StatementManipulator extends Manipulator {

}

And the others:

These interfaces will later receive manipulation statements. But not now – we just want to create the architecture.

The next steps is to create four dummy manipulators – one for each criterion. They implement their interface and extend AbstractDummyManipulator. For example DummyStatementManipulator:

package org.codecover.instrumentation.xampil.manipulator;

public class DummyStatementManipulator extends AbstractDummyManipulator
        implements StatementManipulator {

}

And the others:

To complete the manipulator collection, you need four default manipulators. Each implements a manipulator interface and extends AbstractDefaultManipulator. For example DefaultStatementManipulator:

package org.codecover.instrumentation.xampil.manipulator;

public class DefaultStatementManipulator extends AbstractDefaultManipulator
        implements StatementManipulator {

}

And the others:

After you have created these empty classes, you should 15 files in the folder manipulator:

What should happen with these manipulators now? We go to the method Instrumenter.instrumentThis(..). A method of the super Instrumenter is isCriterionSet(Criterion criterion). We use this method to decide which manipulators the InstrumentationVisitor will get. Add the following lines to the method Instrumenter.instrumentThis(..) before the visit call is done:

[..]

InstrumentationVisitor instrumentationVisitor = new InstrumentationVisitor(
        targetPrintWriter, database, sourceFile, hierarchyLevelContainer,
    testSessionContainerUID);

if (super.isCriterionSet(StatementCoverage.getInstance())) {
    instrumentationVisitor.setStatementManipulator(
        new DefaultStatementManipulator());
} else {
    instrumentationVisitor.setStatementManipulator(
        new DummyStatementManipulator());
}

if (super.isCriterionSet(BranchCoverage.getInstance())) {
    instrumentationVisitor.setBranchManipulator(
        new DefaultBranchManipulator());
} else {
    instrumentationVisitor.setBranchManipulator(
        new DummyBranchManipulator());
}

if (super.isCriterionSet(LoopCoverage.getInstance())) {
    instrumentationVisitor.setLoopManipulator(
        new DefaultLoopManipulator());
} else {
    instrumentationVisitor.setLoopManipulator(
        new DummyLoopManipulator());
}

if (super.isCriterionSet(ConditionCoverage.getInstance())) {
    instrumentationVisitor.setConditionManipulator(
        new DefaultConditionManipulator());
} else {
    instrumentationVisitor.setConditionManipulator(
        new DummyConditionManipulator());
}

instrumentationVisitor.visit(compilationUnit);

targetPrintWriter.flush();

[..]

Of course, you have to implement the set methods of the InstrumentationVisitor. There you have to pay attention to set the writer to the new manipulators. For example:

public void setStatementManipulator(StatementManipulator statementManipulator) {
    this.statementManipulator = statementManipulator;
    this.statementManipulator.setWriter(super.getTargetWriter());
}

Real instrumentation

CounterIDProvider

To manage the number of counters and their format, we have provided the class CounterIDProvider. This class is responsible to provide an ID for every statement, branch, loop and condition. Therefore counters are held and incremented for the current IDs. The CounterIDProvider has methods to increment the number of one of the current counters – e.g. for statements. We add the class by creating a new object in the constructor of InstrumentationVisitor. It will be used later.

[..]

private CounterIDProvider counterIDProvider;

public InstrumentationVisitor(PrintWriter writer,
        MASTBuilder builder,
        SourceFile sourceFile,
        HierarchyLevelContainer hierarchyLevelContainer,
        String testSessionContainerUID) {
    super(writer);
    this.builder = builder;
    this.sourceFile = sourceFile;
    this.hierarchyLevelContainer = hierarchyLevelContainer;
    this.testSessionContainerUID = testSessionContainerUID;
    this.counterIDProvider = new CounterIDProvider();
}

[..]

Statement Instrumentation

Now we start to instrument. We begin to consider statements. What do we have to do? We create the method InstrumentationVisitor.visit(Statement n):

@Override
public void visit(Statement n) {
   super.visit(n);
   String statementID = this.counterIDProvider.nextStatementID();
   this.statementManipulator.manipulate(n, statementID);
}

The super call tells the TreeDumper and its father to visit all nodes under Statement and print them to the target writer. The manipulate method tells the StatementManipulator: "I have found a statement. You can now add additional code for instrumentation purpose." This method has to be created in the interface StatementManipulator, in the DummyStatementManipulator and in the DefaultStatementManipulator. Where the dummy can leave the method empty, the default manipulator has to do the following:

public void manipulate(Statement n, String statementID) {
    super.getWriter().printf("%1$s%2$s := %1$s%2$s + 1%n",
                             CounterIDProvider.VARIABLE_PREFIX,
                             statementID);
}

That's all. After the visitor has printed all the original token images with the writer, the manipulator adds a statement that increments the counter. The counter name has a prefix for uniqueness and the statementID. For that reason, this counter should be unique and is related to the statement with the given ID.

We modify our main method to test this manipulation:

FileInputStream fileInputStream = new FileInputStream("example.xpl");
InputStreamReader inputStreamReader = new InputStreamReader(
        fileInputStream, Charset.forName("UTF-8"));
BufferedReader bufferedReader = new BufferedReader(
        inputStreamReader);
CharStream charStream = new SimpleCharStream(bufferedReader);
XampilParser parser = new XampilParser(charStream);
InstrumentableItemCounter counter = new InstrumentableItemCounter();
CompilationUnit compilationUnit = parser.CompilationUnit(counter);
PrintWriter writer = new PrintWriter(System.out);
InstrumentationVisitor visitor = new InstrumentationVisitor(writer,
                                             null,
                                             null,
                                             null,
                                             null);
visitor.setStatementManipulator(new DefaultStatementManipulator());
visitor.setBranchManipulator(new DefaultBranchManipulator());
visitor.setLoopManipulator(new DefaultLoopManipulator());
visitor.setConditionManipulator(new DefaultConditionManipulator());
visitor.visit(compilationUnit);
writer.flush();

bufferedReader.close();

And what do we see? An instrumented example.xpl:

// example.xpl
DECLARATION
    BOOLEAN b := FALSE

    INTEGER i := -1

    STRING characters := "unset"
PROGRAM
    i := 0

    CodeCoverCoverageCounter_S1 := CodeCoverCoverageCounter_S1 + 1
IF TRUE THEN
        i := 1
    CodeCoverCoverageCounter_S2 := CodeCoverCoverageCounter_S2 + 1
ELSE
        i := 0
    CodeCoverCoverageCounter_S3 := CodeCoverCoverageCounter_S3 + 1
ENDIF

    CodeCoverCoverageCounter_S4 := CodeCoverCoverageCounter_S4 + 1
WHILE ((i <> 0) AND (i <= 10)) DO
        i := i + 1
    CodeCoverCoverageCounter_S5 := CodeCoverCoverageCounter_S5 + 1
ENDWHILE

    CodeCoverCoverageCounter_S6 := CodeCoverCoverageCounter_S6 + 1
SWITCH i
        CASE 1 :
            characters := "i was 1"
        CodeCoverCoverageCounter_S7 := CodeCoverCoverageCounter_S7 + 1
ENDCASE
        CASE 10 :
            characters := "i was 10"
        CodeCoverCoverageCounter_S8 := CodeCoverCoverageCounter_S8 + 1
ENDCASE
        DEFAULT :
            characters := "i was not set to 1 or 10"
        CodeCoverCoverageCounter_S9 := CodeCoverCoverageCounter_S9 + 1
ENDCASE
    ENDSWITCH

    CodeCoverCoverageCounter_S10 := CodeCoverCoverageCounter_S10 + 1
FILE OVERWRITE "target.log" i
CodeCoverCoverageCounter_S11 := CodeCoverCoverageCounter_S11 + 1
ENDPROGRAM

This code is not formatted very well, but the statement instrumentation is working. The only thing, that is missing, is the declaration of the counters. Therefore we have to extend the interface StatementManipulator. We add a method that advises a manipulator to add all required declarations for the counters:

public interface StatementManipulator extends Manipulator {

    public void writeDeclarations(int statementCount);

    public void manipulate(Statement n, String statementID);
}

The DummyStatementManipulator does not need this method – it does not instrument and needs no counters. Consequently, the DummyStatementManipulator has only an empty writeDeclarations() method. But the DefaultStatementManipulator implements this method the following:

public void writeDeclarations(int statementCount) {
    PrintWriter writer = super.getWriter();
    for (int i = 1; i <= instrumentableItemCount; i++) {
        writer.printf("INTEGER %s%s := 0%n",
                CounterIDProvider.VARIABLE_PREFIX,
                CounterIDProvider.generateStatementID(i));
    }
}

We get the statement count and for every expected statement, we add a counter declaration. Again we use the CounterIDProvider to tell us, how a statement ID with a given number is formatted. After we have implemented this writeDeclarations() method, we should not forget that it is not used yet. We have to call it from the InstrumentationVisitor. For that reason, we have to add the following code (highlighted):

public InstrumentationVisitor(PrintWriter writer,
        InstrumentableItemCounter counter,
        MASTBuilder builder,
        SourceFile sourceFile,
        HierarchyLevelContainer hierarchyLevelContainer,
        String testSessionContainerUID) {
    super(writer);
    this.counter = counter;
    this.builder = builder;
    this.sourceFile = sourceFile;
    this.hierarchyLevelContainer = hierarchyLevelContainer;
    this.testSessionContainerUID = testSessionContainerUID;
    this.counterIDProvider = new CounterIDProvider();
}

[..]

/**
 * f0 -> Declaration()
 * f1 -> Program()
 * f2 -> ( <EOL> )?
 * f3 -> <EOF>
 */
@Override
public void visit(CompilationUnit n) {
   n.f0.accept(this);
   this.statementManipulator.writeDeclarations(this.counter.getStatementCount());
   n.f1.accept(this);
   n.f2.accept(this);
   n.f3.accept(this);
}

[..]

Of course, you have to update all calls of the constructor of the InstrumentationVisitor too. There you have to add the visitor as the second parameter.

If we run the corrected main method now, we see that the statements are instrumented and the declarations are added too. This instrumented example.xpl would compile now – if we had a compiler.

[..]

    STRING characters := "unset"
    INTEGER CodeCoverCoverageCounter_S1 := 0
    INTEGER CodeCoverCoverageCounter_S2 := 0
    INTEGER CodeCoverCoverageCounter_S3 := 0
    INTEGER CodeCoverCoverageCounter_S4 := 0
    INTEGER CodeCoverCoverageCounter_S5 := 0
    INTEGER CodeCoverCoverageCounter_S6 := 0
    INTEGER CodeCoverCoverageCounter_S7 := 0
    INTEGER CodeCoverCoverageCounter_S8 := 0
    INTEGER CodeCoverCoverageCounter_S9 := 0
    INTEGER CodeCoverCoverageCounter_S10 := 0
    INTEGER CodeCoverCoverageCounter_S11 := 0
PROGRAM

[..]

Branch Instrumentation

After we have discussed the instrumentation of statements in detail, you should have got a clue how the other instrumentations may work. For this reason, we do not discuss every detail anymore.

We start in the InstrumentationVisitor again. We have to add methods to instrument branches. Branches are created by IF, ELSE, CASE and DEFAULT. So we add manipulator calls there. Therefore we have to overwrite visit() methods again. We have to call the accept() methods that tell each Node to accept a visiting. Then we have to add the manipulate calls of the BranchManipulator. To allow a more detailed description, we show an extract of the IF instrumentation. The important lines are highlighted.

[..]

/**
 * f0 -> <IF>
 * f1 -> Expression(basicBooleanCounter)
 * f2 -> <THEN>
 * f3 -> <EOL>
 * f4 -> ( Statement() )*
 * f5 -> ( <ELSE> <EOL> ( Statement() )* )?
 * f6 -> <ENDIF>
 * f7 -> <EOL>
 */
@Override
public void visit(IfStatement n) {
   n.f0.accept(this);
   n.f1.accept(this);
   n.f2.accept(this);
   n.f3.accept(this);
   String ifBranchID = this.counterIDProvider.nextBranchID();
   this.branchManipulator.manipulateIf(n, ifBranchID);
   n.f4.accept(this);

   NodeOptional elseOption = n.f5;
   String elseBranchID = this.counterIDProvider.nextBranchID();
   if (elseOption.present()) {
       // the else is present
       NodeSequence elseSequence = (NodeSequence) elseOption.node;
       // <ELSE>
       elseSequence.nodes.get(0).accept(this);
       // <EOL>
       elseSequence.nodes.get(1).accept(this);

       this.branchManipulator.manipulateElse(n, elseBranchID, false);

       // ( Statement() )*
       elseSequence.nodes.get(2).accept(this);
   } else {
       // there was no else branch -> create it
       this.branchManipulator.manipulateElse(n, elseBranchID, true);
   }
   n.f6.accept(this);
   n.f7.accept(this);
}

[..]

We have added a manipulating statement in the if branch. This was expectable. But why do we need two manipualeElse calls? If there already exists an else branch, then we have to visit the ELSE keyword and write our instrumentation afterwards. But if there is no ELSE, we say, that this branch is implicit.

IF a > 5 THEN
    a := 5
ENDIF

The else branch is not explicit written, but it could be:

IF a > 5 THEN
    a := 5
ELSE
ENDIF

The coverage measurement requires that we get to know, if an implicit else branch is "entered" or not. For this reason, we have to add the ELSE keyword in such a case. The DefaultBranchManipulator looks like this:

public void manipulateIf(IfStatement n, String ifBranchID) {
    super.getWriter().printf("%1$s%2$s := %1$s%2$s + 1%n",
            CounterIDProvider.VARIABLE_PREFIX,
            ifBranchID);
}

public void manipulateElse(IfStatement n, String elseBranchID, boolean isImplicit) {
    PrintWriter writer = super.getWriter();
    if (isImplicit) {
        writer.printf("ELSE%n");
    }
    writer.printf("%1$s%2$s := %1$s%2$s + 1%n",
            CounterIDProvider.VARIABLE_PREFIX,
            elseBranchID);
}

As you can see, we use exactly the same instrumentation approach as used for instrumenting statements. The handling of an implicit else branch is highlighted.

We do not discuss the instrumentation of switch, because it is similar. What we have to do, is the declaration of the branch counters. This is done same way as for statement instrumentation:

@Override
public void visit(CompilationUnit n) {
   n.f0.accept(this);
   this.statementManipulator.writeDeclarations(this.counter.getStatementCount());
   this.branchManipulator.writeDeclarations(this.counter.getBranchCount());
   n.f1.accept(this);
   n.f2.accept(this);
   n.f3.accept(this);
}

The only thing left is to create the writeDeclarations() method in the BranchManipulator, DummyBranchManipulator and in the DefaultBranchManipulator. Everything is the same, except that you have to use branch IDs this time:

public class DefaultBranchManipulator extends AbstractDefaultManipulator
        implements BranchManipulator {

    public void writeDeclarations(int statementCount) {
        PrintWriter writer = super.getWriter();
        for (int i = 1; i <= statementCount; i++) {
            writer.printf("INTEGER %s%s := 0%n",
                    CounterIDProvider.VARIABLE_PREFIX,
                    CounterIDProvider.generateBranchID(i));
        }
    }

[..]

}

Our main method will now instrument the input for the measureemnt of statement and branch coverage. The instrumented file can be found here: example.autoinstr-br.xpl

Loop Instrumentation

The loop instrumentation is a little bit more advanced. Here, we need more than a single counter to be incremented. See design the loop instrumentation section, if you do not remember, how we want to instrument loops.

Again, we start in the InstrumentationVisitor. The only loop construct of Xampil is the WHILE loop. So we overwrite its visit method:

@Override
public void visit(WhileStatement n) {
    String loopID = this.counterIDProvider.nextLoopID();
    this.loopManipulator.manipulateBeforeWhile(n, loopID);

    // <WHILE>
    n.f0.accept(this);
    // Expression(basicBooleanCounter)
    n.f1.accept(this);
    // <DO>
    n.f2.accept(this);
    // <EOL>
    n.f3.accept(this);

    this.loopManipulator.manipulateInWhile(n, loopID);

    // ( Statement() )*
    n.f4.accept(this);
    // <ENDWHILE>
    n.f5.accept(this);
    // <EOL>
    n.f6.accept(this);

    this.loopManipulator.manipulateAfterWhile(n, loopID);
}

All in all, we need three manipulation methods. Consequently the LoopManipulator and its children will have three methods. The DefaultLoopManipulator has the following implementation:

private static final String TEMP_COUNTER_SUFFIX = "_temp";

public void manipulateBeforeWhile(WhileStatement n, String loopID) {
    super.getWriter().printf("%s%s%s := 0%n",
                             CounterIDProvider.VARIABLE_PREFIX,
                             loopID,
                             TEMP_COUNTER_SUFFIX);
}

public void manipulateInWhile(WhileStatement n, String loopID) {
    super.getWriter().printf("%1$s%2$s%3$s := %1$s%2$s%3$s + 1%n",
                             CounterIDProvider.VARIABLE_PREFIX,
                             loopID,
                             TEMP_COUNTER_SUFFIX);
}

public void manipulateAfterWhile(WhileStatement n, String loopID) {
    super.getWriter().printf("" +
                 "SWITCH %1$s%2$s%3$s%n" +
                 "    CASE 0 : %1$s%4$s := %1$s%4$s + 1%n" +
                 "    ENDCASE%n" +
                 "    CASE 1 : %1$s%5$s := %1$s%5$s + 1%n" +
                 "    ENDCASE%n" +
                 "    DEFAULT : %1$s%6$s := %1$s%6$s + 1%n" +
                 "    ENDCASE%n" +
                 "ENDSWITCH%n",
       /* 1$ */  CounterIDProvider.VARIABLE_PREFIX,
       /* 2$ */  loopID,
       /* 3$ */  TEMP_COUNTER_SUFFIX,
       /* 4$ */  CounterIDProvider.generateLoopSubIDZero(loopID).replace('-', '_'),
       /* 5$ */  CounterIDProvider.generateLoopSubIDOne(loopID).replace('-', '_'),
       /* 6$ */  CounterIDProvider.generateLoopSubIDAbove(loopID).replace('-', '_'));
}

To finish the loop instrumentation, we just have to call the writeDeclarations method in the InstrumentationVisitor and implement it in the DefaultLoopManipulator:

private static final String TEMP_COUNTER_SUFFIX = "_temp";

public void writeDeclarations(int loopCount) {
    PrintWriter writer = super.getWriter();
    for (int i = 1; i <= loopCount; i++) {
        String thisLoopID = CounterIDProvider.generateStatementID(i);
        writer.printf("    INTEGER %1$s%2$s%3$s%n" +
                      "    INTEGER %1$s%4$s := 0%n" +
                      "    INTEGER %1$s%5$s := 0%n" +
                      "    INTEGER %1$s%6$s := 0%n",
            CounterIDProvider.VARIABLE_PREFIX,
            thisLoopID,
            TEMP_COUNTER_SUFFIX,
            CounterIDProvider.generateLoopSubIDZero(thisLoopID).replace('-', '_'),
            CounterIDProvider.generateLoopSubIDOne(thisLoopID).replace('-', '_'),
            CounterIDProvider.generateLoopSubIDAbove(thisLoopID).replace('-', '_'));
}

Compared to the other implementations of writeDeclarations, this method is a little bit more complex. We need three counters for each loop. We get their ID from the CounterIDProvider. These IDs contain a minus (-), that is not allowed in the Xampil grammar within an identifier. For this reason, we have to replace each minus by an underscore. Last not least, we have to declare the temporary variable, that counts the number of loops of a while. This temporary variable does not need to be set to zero in the declaration, this is done in front of the related while loop.

Our main method will now instrument its input for statement, branch and loop coverage. The instrumented file can be found here: example.autoinstr-lo.xpl

Condition Instrumentation

For the condition instrumentation we need to parse a conditional expression and store the logical structure of the expression. We create a new visitor for this purpose, namely the XampilExpressionParser. This visitor provides a method to parse an expression. It returns an object of InstrBooleanTerm which contains the logical structure and the basic boolean terms. The InstrBooleanTerm is defined by CodeCover and can be found in the package org.codecover.instrumentation.booleanterms

public class XampilExpressionParser extends GJNoArguDepthFirst<InstrBooleanTerm>
    implements GJNoArguVisitor<InstrBooleanTerm> {

    public InstrBooleanTerm parse(Expression n) {
        return n.accept(this);
    }
}

The expression parser works like any other visitor, you just overwrite the visit method of the node you want the visitor to do special things. But we have to be sure that every child node of expression returns an InstrBooleanTerm object. For that, we have to implement the visit(Expression n) method.

public class XampilExpressionParser extends GJNoArguDepthFirst<InstrBooleanTerm>
    implements GJNoArguVisitor<InstrBooleanTerm> {

    public InstrBooleanTerm parse(Expression n) {
        return n.accept(this);
    }

    /**
     * f0 -> OrExpression(basicBooleanCounter)
     */
    public InstrBooleanTerm visit(Expression n) {
        return n.f0.accept(this);
    }
}

As you can see, we just accept the expression and assume that the visited OrExpression returns an InstrBooleanTerm object. Of course, we have to implement this as well. It is very helpfull to copy the grammar production from the node class to identify the visit method you implement. Here is the code of the OrExpression visit method.

    /**
     * f0 -> AndExpression(basicBooleanCounter)
     * f1 -> ( <OR> AndExpression(basicBooleanCounter) )*
     */
    @Override
    public InstrBooleanTerm visit(OrExpression n) {
        InstrBooleanTerm returnTerm = n.f0.accept(this);
        for (Node node : n.f1.nodes) {
            NodeSequence nodeSequence = (NodeSequence) node;
            NodeToken operatorToken = (NodeToken) nodeSequence.nodes.get(0);
            InstrBooleanTerm term = nodeSequence.nodes.get(1).accept(this);
            returnTerm = new InstrOperatorTerm(returnTerm,
                    XampilBooleanOperators.getOrOperator(), term,
                    operatorToken.startOffset, operatorToken.endOffset);
        }
        return returnTerm;
    }

This method is the first step we have to do. First we visit the AndExpression and store the return (returnTerm). After that the grammar allows zero or multiple sequences of OR and AndExpression. So we iterate over all sequences, store the InstrBooleanTerm of the AndExpression (term) and create a new InstrOperatorTerm with the operator OR and operands returnTerm and term.

The next visit method that has to be implemented is for the node AndExpression.

    /**
     * f0 -> NotExpression(basicBooleanCounter)
     * f1 -> ( <AND> NotExpression(basicBooleanCounter) )*
     */
    @Override
    public InstrBooleanTerm visit(AndExpression n) {
        InstrBooleanTerm returnTerm = n.f0.accept(this);
        for (Node node : n.f1.nodes) {
            NodeSequence nodeSequence = (NodeSequence) node;
            NodeToken operatorToken = (NodeToken) nodeSequence.nodes.get(0);
            InstrBooleanTerm term = nodeSequence.nodes.get(1).accept(this);
            returnTerm = new InstrOperatorTerm(returnTerm,
                    XampilBooleanOperators.getAndOperator(), term,
                    operatorToken.startOffset, operatorToken.endOffset);
        }
        return returnTerm;
    }

This is quite the same as above. If an AND operator occurs we create a new InstrOperatorTerm with the operator AND and operands returnTerm and term. The next visit methods should be easy to understand. Here is the listing.

    /**
     * f0 -> ( <NOT> )?
     * f1 -> EqualityExpression(basicBooleanCounter)
     */
    @Override
    public InstrBooleanTerm visit(NotExpression n) {
        InstrBooleanTerm returnTerm = n.f1.accept(this);
        if (n.f0.present()) {
            NodeToken operatorToken = (NodeToken) n.f0.node;
            returnTerm = new InstrOperatorTerm(XampilBooleanOperators.getNotOperator(),
                    returnTerm,
                    operatorToken.startOffset, operatorToken.endOffset);
        }
        return returnTerm;
    }

    /**
     * f0 -> RelationalExpression(basicBooleanCounter)
     * f1 -> ( ( <EQ> | <NEQ> ) RelationalExpression(basicBooleanCounter) )?
     */
    @Override
    public InstrBooleanTerm visit(EqualityExpression n) {
        InstrBooleanTerm returnTerm = n.f0.accept(this);
        if (n.f1.present()) {
            returnTerm = InstrBasicBooleanVisitor.convertToInstrBasicBoolean(n);
        }
        return returnTerm;
    }

    /**
     * f0 -> AdditiveExpression(basicBooleanCounter)
     * f1 -> ( ( <LT> | <GT> | <LE> | <GE> ) AdditiveExpression(basicBooleanCounter) )?
     */
    @Override
    public InstrBooleanTerm visit(RelationalExpression n) {
        InstrBooleanTerm returnTerm = n.f0.accept(this);
        if (n.f1.present()) {
            returnTerm = InstrBasicBooleanVisitor.convertToInstrBasicBoolean(n);
        }
        return returnTerm;
    }

    /**
     * f0 -> MultiplicativeExpression(basicBooleanCounter)
     * f1 -> ( ( <PLUS> | <MINUS> ) MultiplicativeExpression(basicBooleanCounter) )*
     */
    @Override
    public InstrBooleanTerm visit(AdditiveExpression n) {
        InstrBooleanTerm returnTerm = n.f0.accept(this);
        if (n.f1.present()) {
            returnTerm = InstrBasicBooleanVisitor.convertToInstrBasicBoolean(n);
        }
        return returnTerm;
    }

    /**
     * f0 -> BasicExpression(basicBooleanCounter)
     * f1 -> ( ( <STAR> | <SLASH> ) BasicExpression(basicBooleanCounter) )*
     */
    @Override
    public InstrBooleanTerm visit(MultiplicativeExpression n) {
        InstrBooleanTerm returnTerm = n.f0.accept(this);
        if (n.f1.present()) {
            returnTerm = InstrBasicBooleanVisitor.convertToInstrBasicBoolean(n);
        }
        return returnTerm;
    }

The InstrBasicBooleanVisitor is a visitor which converts a node to an InstrBasicBooleanTerm by capturing all NodeTokens, startOffset and endOffset. After writing the last visit method we will discuss the InstrBasicBooleanVisitor. This last method is needed for processing a BasicExpression.

    /**
     * f0 -> <IDENTIFIER>
     *       | <INTEGER_LITERAL>
     *       | <STRING_LITERAL>
     *       | <TRUE>
     *       | <FALSE>
     *       | <LPAREN> Expression(basicBooleanCounter) <RPAREN>
     */
    @Override
    public InstrBooleanTerm visit(BasicExpression n) {
        InstrBooleanTerm returnTerm = null;
        if (n.f0.which == 0) {
            returnTerm = InstrBasicBooleanVisitor.convertToInstrBasicBoolean(n);
        } else if (n.f0.which == 3) {
            NodeToken token = (NodeToken) n.f0.choice;
            returnTerm = new InstrOperatorTerm(XampilBooleanOperators.getTrueOperator(),
                    token.startOffset, token.endOffset);
        } else if (n.f0.which == 4) {
            NodeToken token = (NodeToken) n.f0.choice;
            returnTerm = new InstrOperatorTerm(XampilBooleanOperators.getFalseOperator(),
                    token.startOffset, token.endOffset);
        } else if (n.f0.choice instanceof NodeSequence) {
            NodeSequence nodeSequence = (NodeSequence) n.f0.choice;
            InstrBooleanTerm expressionTerm = nodeSequence.nodes.get(1).accept(this);
            returnTerm = new InstrBracketTerm(expressionTerm);
        } else {
            throw new RuntimeException("Integer or string literal used as" +
                                            "basic boolean term.");
        }
        return returnTerm;
    }

A BasicExpression can be a basic boolean term, true, false, an integer or string, or a nested expression. If it is a basic boolean term, an InstrBasicBoolean is created. For true and false, an InstrOperatorTerm with the arity zero is created and nested expression are visited by the visit(Expression n) method.

After discussing the XampilExpressionParser we change the focus to some helper classes we need for condition instrumentation. The first one we look at is the class InstrBasicBooleanVisitor.

public class InstrBasicBooleanVisitor extends DepthFirstVisitor {
    private StringWriter writer;

    private int foundStartOffset = -1;

    private int foundEndOffset = -1;

    private InstrBasicBooleanVisitor() {
        this.writer = new StringWriter();
    }

    public void visit(NodeToken n) {
        if (n.numSpecials() > 0) {
            for (NodeToken nt : n.specialTokens) {
                this.writer.write(nt.tokenImage);
            }
        }

        this.writer.write(n.tokenImage);
        if (this.foundStartOffset == -1) {
            this.foundStartOffset = n.startOffset;
        }
        this.foundEndOffset = n.endOffset;
    }

    public static InstrBasicBooleanTerm convertToInstrBasicBoolean(Node n) {
        InstrBasicBooleanVisitor treeStringDumper = new InstrBasicBooleanVisitor();
        n.accept(treeStringDumper);

        return new InstrBasicBooleanTerm(treeStringDumper.writer.toString().trim(),
                treeStringDumper.foundStartOffset,
                treeStringDumper.foundEndOffset);
    }
}

This visitor dumps all node tokens into a StringWriter for a node given to the convertToInstrBasicBoolean(Node n) method. In addition, the start and end offset of the given node is gathered. All the information is used to create a new InstrBasicBooleanTerm which is returned.

The second helper class is XampilBooleanOperators. We used its methods in the XampilExpressionParser to generate operator terms. The following listing shows the source.

public class XampilBooleanOperators {
    public static final String OR = "OR";
    public static final String NOT = "NOT";
    public static final String AND = "AND";
    public static final String TRUE_DESCRIPTION = "TRUE";
    public static final String FALSE_DESCRIPTION = "FALSE";
    private static InstrBooleanOperator orOperator = null;
    private static InstrBooleanOperator andOperator = null;
    private static InstrBooleanOperator notOperator = null;
    private static InstrBooleanOperator trueOperator = null;
    private static InstrBooleanOperator falseOperator = null;

    ...

}

This class basically contains methods that return InstrBooleanOperators which store information about possible boolean assignments of an operator. For example two operands connected by an OR operator returns true if one of the two is true. Such information has to be given for every operator your programming language is capable of. In Xampil we have to define the OR, AND, NOT, true, and false operator. True and false are operators with the arity zero in CodeCover!


    public static InstrBooleanOperator getOrOperator() {
        if (orOperator == null) {
            Map<BooleanAssignment, Boolean> possibleAssignments =
                    new HashMap<BooleanAssignment, Boolean>();
            BooleanAssignment assignment;

            assignment = new BooleanAssignment(FALSE, FALSE);
            possibleAssignments.put(assignment, Boolean.FALSE);

            assignment = new BooleanAssignment(FALSE, TRUE);
            possibleAssignments.put(assignment, Boolean.TRUE);

            assignment = new BooleanAssignment(TRUE, FALSE);
            possibleAssignments.put(assignment, Boolean.TRUE);

            assignment = new BooleanAssignment(TRUE, TRUE);
            possibleAssignments.put(assignment, Boolean.TRUE);

            orOperator = InstrBooleanOperator.getTwoArgumentOperator(
                    XampilBooleanOperators.OR, "OR", possibleAssignments);
        }

        return orOperator;
    }

    public static InstrBooleanOperator getAndOperator() {
        if (andOperator == null) {
            Map<BooleanAssignment, Boolean> possibleAssignments =
                    new HashMap<BooleanAssignment, Boolean>();
            BooleanAssignment assignment;

            assignment = new BooleanAssignment(FALSE, FALSE);
            possibleAssignments.put(assignment, Boolean.FALSE);

            assignment = new BooleanAssignment(FALSE, TRUE);
            possibleAssignments.put(assignment, Boolean.FALSE);

            assignment = new BooleanAssignment(TRUE, FALSE);
            possibleAssignments.put(assignment, Boolean.FALSE);

            assignment = new BooleanAssignment(TRUE, TRUE);
            possibleAssignments.put(assignment, Boolean.TRUE);

            andOperator = InstrBooleanOperator.getTwoArgumentOperator(
                    XampilBooleanOperators.AND, "AND", possibleAssignments);
        }

        return andOperator;
    }

    public static InstrBooleanOperator getNotOperator() {
        if (notOperator == null) {
            Map<BooleanAssignment, Boolean> possibleAssignments =
                    new HashMap<BooleanAssignment, Boolean>();
            BooleanAssignment assignment;

            assignment = new BooleanAssignment(FALSE);
            possibleAssignments.put(assignment, Boolean.TRUE);

            assignment = new BooleanAssignment(TRUE);
            possibleAssignments.put(assignment, Boolean.FALSE);

            notOperator = InstrBooleanOperator.getOneArgumentOperator(
                    XampilBooleanOperators.NOT, "NOT", false, possibleAssignments);
        }

        return notOperator;
    }

    public static InstrBooleanOperator getTrueOperator() {
        if (trueOperator == null) {
            BooleanAssignment assignment = new BooleanAssignment();

            trueOperator = InstrBooleanOperator.getConstantOperator(
                    XampilBooleanOperators.TRUE_DESCRIPTION, "TRUE",
                    Collections.singletonMap(assignment, Boolean.TRUE));
        }

        return trueOperator;
    }

    public static InstrBooleanOperator getFalseOperator() {
        if (falseOperator == null) {
            BooleanAssignment assignment = new BooleanAssignment();

            falseOperator = InstrBooleanOperator.getConstantOperator(
                    XampilBooleanOperators.FALSE_DESCRIPTION, "FALSE",
                    Collections.singletonMap(assignment, Boolean.FALSE));
        }

        return falseOperator;
    }

After doing all this stuff, we are now ready to add the instructions into the InstrumentationVisitor. To do so, we have to find out where conditional expressions can occure. In Xampil it is the if and while statement. So we insert the following piece of code:


    public void visit(IfStatement n) {
        XampilExpressionParser xampilExpressionParser = new XampilExpressionParser();
        InstrBooleanTerm instrBooleanTerm = xampilExpressionParser.parse(n.f1);
        List<InstrBasicBooleanTerm> termList = new LinkedList<InstrBasicBooleanTerm>();
        instrBooleanTerm.getAllBasicBooleanTerms(termList);
        this.conditionManipulator.manipulate(ifConditionID, termList);

        n.f0.accept(this);
        ....
    }

    public void visit(WhileStatement n) {
        XampilExpressionParser xampilExpressionParser = new XampilExpressionParser();
        InstrBooleanTerm instrBooleanTerm = xampilExpressionParser.parse(n.f1);
        List<InstrBasicBooleanTerm> termList = new LinkedList<InstrBasicBooleanTerm>();
        instrBooleanTerm.getAllBasicBooleanTerms(termList);
        this.conditionManipulator.manipulate(whileConditionID, termList);

        n.f0.accept(this);
        ....
    }

On the top of that, we have to insert a call of the condition manipulator's writeDeclaration() method. See next listing:

    public void visit(CompilationUnit n) {
       n.f0.accept(this);
       this.statementManipulator.writeDeclarations(this.counter.getStatementCount());
       this.branchManipulator.writeDeclarations(this.counter.getBranchCount());
       this.conditionManipulator.writeDeclarations(this.counter);
       this.loopManipulator.writeDeclarations(this.counter.getLoopCount());
       n.f1.accept(this);
       n.f2.accept(this);
       n.f3.accept(this);
    }

And now the last step for condition instrumentation can be taken, namely the condition manipulator. We need to implement the manipulate and writeDeclarations method.

public class DefaultConditionManipulator extends AbstractDefaultManipulator
        implements ConditionManipulator {

    private static final String END_IF = "ENDIF %n    ";

    private static final String ELSE = "ELSE %n    ";

    private static final String IF_NOT = "IF NOT(%s) THEN %n    ";

    private static final String ONE = "1";

    private static final String ZERO = "0";

    private static final String CONDITION_COUNTER =
            "%1$s%2$s_%3$s := %1$s%2$s_%3$s + 1%n    ";

    private int truthTableLine;

    private List<InstrBasicBooleanTerm> basicBooleanTerms;

    ....

}

First, we take a look at the writeDeclarations method.

    public void writeDeclarations(InstrumentableItemCounter counter) {
        PrintWriter writer = super.getWriter();
        OUTER_LOOP : for (int i = 0; i < counter.getConditionCount(); i++) {
            int booleanTerms = counter.getBasicBooleanCount(i);
            if (booleanTerms == 0) {
                continue OUTER_LOOP;
            }
            int basicBooleanCounters = 1 << booleanTerms;
            String conditionPrimaryID = CounterIDProvider.generateConditionPrimaryID(i);
            for (int j = 0; j < basicBooleanCounters; j++) {
                writer.printf("    INTEGER %s%s_%s := 0%n",
                        CounterIDProvider.VARIABLE_PREFIX,
                        conditionPrimaryID,
                        getTruthTableLine(booleanTerms, j));
            }
        }
        writer.printf("%n");
    }

This method writes all declarations for every condition to the output writer. To do that, we loop over all contitions and write to the output writer in an inner loop write for each line in the truth table. The second method we have to implement is the manipulate method.

    public void manipulate(String conditionID, List<InstrBasicBooleanTerm> termList) {
        if (termList.isEmpty()) {
            return;
        }
        this.truthTableLine = 0;
        this.basicBooleanTerms = termList;
        this.generateNestedIfBlock(0, conditionID);
    }

It seems to be very simple on the first look, but the whole complexity of generating the nested if block is put into an extra method. This method is generateNestedIfBlock which is implemented as follows.

    private void generateNestedIfBlock(int basicBooleanTerm, String conditionID) {
        String basicBooleanTermString =
                this.basicBooleanTerms.get(basicBooleanTerm).termToString();
        super.getWriter().printf(IF_NOT, basicBooleanTermString);
        if (basicBooleanTerm < this.basicBooleanTerms.size() - 1) {
            this.generateNestedIfBlock(basicBooleanTerm + 1, conditionID);
        } else {
            String truthTableLineString = this.getTruthTableLine(
                    this.basicBooleanTerms.size(), this.truthTableLine);
            super.getWriter().printf(CONDITION_COUNTER,
                    CounterIDProvider.VARIABLE_PREFIX,
                    conditionID,
                    truthTableLineString);
            this.truthTableLine++;
        }
        super.getWriter().printf(ELSE);
        if (basicBooleanTerm < this.basicBooleanTerms.size() - 1) {
            this.generateNestedIfBlock(basicBooleanTerm + 1, conditionID);
        } else {
            String truthTableLineString = this.getTruthTableLine(
                    this.basicBooleanTerms.size(), this.truthTableLine);
            super.getWriter().printf(CONDITION_COUNTER,
                    CounterIDProvider.VARIABLE_PREFIX,
                    conditionID,
                    truthTableLineString);
            this.truthTableLine++;
        }
        super.getWriter().printf(END_IF);
    }

As you might have seen, we implemented the generation recursively. That way it's easy to write and relatively easy to understand. The last method we have to implement is the getTruthTableLine method.

    private String getTruthTableLine(int variables, int line) {
        String tTableLine = Integer.toBinaryString(line);
        while (tTableLine.length() < variables) {
            tTableLine = ZERO + tTableLine;
        }
        String truthTableLineAdapted = new String("");
        for (int position = 0; position < variables; position++) {
            truthTableLineAdapted = truthTableLineAdapted + ONE
                    + tTableLine.charAt(position);
        }
        return truthTableLineAdapted;
    }

This method simply returns a string containing the binary code for a given line in the truth table with n variables. With these methods the condition manipulator is ready for instrumentation purposes.

If anything was done correctly you should be able to instrument the conditions now.

Coverage log file

The instrumentation we have done yet is nearly finshed. Although a Xampil file will collect coverage data during the run, the data is not written to a file. This feature has to be implemented now.

How does such a coverage log file look like? You can have a look in the design documentAppendix B: "Coverage log file specification".

How do we produce such a file? We have to add additional FILE statement for the output. Therefore, we add three methods in the InstrumentationVisitor:

private static final String CLF_NAME = "coverage-log.clf";

/**
 * f0 -> <PROGRAM>
 * f1 -> <EOL>
 * f2 -> ( Statement() )*
 * f3 -> <ENDPROGRAM>
 */
@Override
public void visit(Program n) {
   n.f0.accept(this);
   n.f1.accept(this);
   n.f2.accept(this);
   writeCoverageLogFileOutput();
   n.f3.accept(this);
}

public void writeCoverageLogFileOutput() {
    PrintWriter targetWriter = super.getTargetWriter();
    writeFileStatement(targetWriter, true, "\"TEST_SESSION_CONTAINER \\\"" +
        this.testSessionContainerUID + "\\\"\"");
    writeFileStatement(targetWriter, false,
        "\"START_TEST_CASE \\\"Single Test Case\\\"\"");
    this.statementManipulator.writeCoverageLogFileOutput(
        this.counter.getStatementCount());
    this.branchManipulator.writeCoverageLogFileOutput(
        this.counter.getBranchCount());
    this.loopManipulator.writeCoverageLogFileOutput(
        this.counter.getLoopCount());
    this.conditionManipulator.writeCoverageLogFileOutput(this.counter);
    writeFileStatement(targetWriter, false,
        "\"END_TEST_CASE \\\"Single Test Case\\\"\"");
}

public static void writeFileStatement(PrintWriter targetWriter,
                                      boolean overwrite,
                                      String message) {
    targetWriter.write("    FILE ");
    if (overwrite) {
        targetWriter.write("OVERWRITE");
    } else {
        targetWriter.write("APPEND");
    }
    targetWriter.write(" \"" + CLF_NAME + "\" ");
    targetWriter.write(message);
    targetWriter.write(" + \"\\n\"\n");
}

Before we accept the token ENDPROGRAM (n.f3.accept(this)), we call the method writeCoverageLogFileOutput. This method will create FILE statements, that do write the coverage log file at runtime. The only thing left to do is to implement the required methods for each Manipulator. An exampale is shown here. See the DefaultStatementManipulator:

public void writeCoverageLogFileOutput(int statementCount) {
    for (int i = 1; i <= statementCount; i++) {
        writeFileStatement(super.getWriter(), false,
                String.format("\"%2$s \" + %1$s%2$s",
                              CounterIDProvider.VARIABLE_PREFIX,
                              CounterIDProvider.generateStatementID(i)));
    }
}

After the instrumentation is finished, these FILE statements will look like this:

FILE OVERWRITE "coverage-log.clf" "TEST_SESSION_CONTAINER
        \"1ac546e6-901f-4673-bd20-194e6329f389\"" + "\n"
FILE APPEND "coverage-log.clf" "START_TEST_CASE \"Single Test Case\"" + "\n"
FILE APPEND "coverage-log.clf" "S1 " + CodeCoverCoverageCounter_S1 + "\n"
FILE APPEND "coverage-log.clf" "S2 " + CodeCoverCoverageCounter_S2 + "\n"
FILE APPEND "coverage-log.clf" "S3 " + CodeCoverCoverageCounter_S3 + "\n"
[..]
FILE APPEND "coverage-log.clf" "END_TEST_CASE \"Single Test Case\"" + "\n"

More abstract syntaxtree (MAST)

The syntaxtree model

As we have told you in the preface chapter, we need an abstract model of all the source files. This is required to get to know, which statements and branches are related to each other. Moreover, we can subdivide the model and calculate metrics only for parts of it. For this reason, we use a More abstract syntaxtree. This concept is explained in detail in the design document. The chapter "3.1 Data model" gives an overview of the classes used for the MAST. There is even an example of a small mast that illustrates, how the elements are hierarchically ordered. In this document, we only want to show you the basic ideas.

At the top of the MAST there are the so called HierarchyLevels. They represent a source file, a package, a class or a program unit. On the one hand, they can recursively contain child HierarchyLevels. On the other hand, they can contain StatementSequences with Statements.

These Statements are subdivided into:

Then there are BooleanTerms. They represent a boolean expression that occurs for example in an if. We subdivide BooleanTerms into:

Nearly every element of the MAST has a Location. A location references a SourceFile and an offset in it. This offset is the position of the start and end character of the element in the source file. For example might a BasicBooleanTerm "a > 0" occur in the SourceFile "program.xpl" at the offset 120..124 if the "a" is the 120th character and the "0" is the 124th.

StatementAttic

Now we start to prepare the MAST building. First, we create a statement attic. This is a collection, similar to a stack, where we want to push all Statements that occur at a given level. If we have the construct:

PROGRAM
    i := 1
    IF a > 9 THEN
        i := i + 1
        a := a * i
    ENDIF
    FILE OVERWRITE "target.log" i
ENDPROGRAM

We have i := 1, IF and FILE.. at the same statement level. Within the IF, statements are collected at a lower level and later combined to a Branch. Then the branch is used to create the ConditionalStatement IF at the highest level. The statement attic will look like this:

   → push new list for the PROGRAM unit
1) (PROGRAM) {}
2) (PROGRAM) {i := 1}
   → push new list for the IF
3) (PROGRAM) {i := 1}
   (if)      {}
4) (PROGRAM) {i := 1}
   (if)      {i := i + 1}
5) (PROGRAM) {i := 1}
   (if)      {i := i + 1, a := a * i}
   → pop lowest list and create a StatementSequence for the IF branch
6) (PROGRAM) {i := 1, {i := i + 1, a := a * i}}
7) (PROGRAM) {i := 1, {i := i + 1, a := a * i}, FILE OVERWRITE "target.log" i}
   → pop lowest list and create a StatementSequence for the PROGRAM unit

So this concept will push new lists to the statement attic for every element that creates an own statement body. Ordinary statements are always pushed to the lowest list. Then the end of an element body forces the lowest list to be poped and to be transformed into a StatementSequence. Finally this sequence is pushed to the lowest list, too.

Now we implement this feature and add some lines in the InstrumentationVisitor:

private Attic<List<org.codecover.model.mast.Statement>> statementAttic;

private void pushNewStatementLevelToAttic() {
    this.statementAttic.push(new LinkedList<org.codecover.model.mast.Statement>());
}

private StatementSequence createStatementSequenceFromAttic() {
    List<org.codecover.model.mast.Statement> statementList = this.statementAttic.pop();
    List<Location> locationsOfSequence = new Vector<Location>(statementList.size());
    for (org.codecover.model.mast.Statement thisStatement : statementList) {
        locationsOfSequence.addAll(thisStatement.getLocation().getLocations());
    }

    return this.builder.createStatementSequence(
            this.builder.createLocationList(locationsOfSequence),
            statementList);
}

private List<StatementSequence> createStatementSequenceListFromAttic() {
    StatementSequence statementSequence = createStatementSequenceFromAttic();

    if (statementSequence.getStatements().isEmpty()) {
        return Collections.<StatementSequence>emptyList();
    }

    return Collections.<StatementSequence>singletonList(statementSequence);
}

Where the method pushNewStatementLevelToAttic just pushes an empty list to the attic, the method createStatementSequenceFromAttic pops the lowest list and creates a StatementSequence out of it. For compatibility, CodeCover often expects a list of StatementSequences. We do not need this feature, so we use a singleton list to encapsulate our created StatementSequence in the method createStatementSequenceListFromAttic.

To create all the elements of the MAST, a MastBuilder has to be used. It has various create methods to create every element of the MAST. We have got this MastBuilder in the constructor of the InstrumentationVisitor.

PROGRAMM unit

We start with the mast creation at the root. We go to the method visit(CompilationUnit n) and add the following code:

[..]

private Attic<List<org.codecover.model.mast.Statement>> statementAttic;

public InstrumentationVisitor(PrintWriter writer,
                              InstrumentableItemCounter counter,
                              MASTBuilder builder,
                              SourceFile sourceFile,
                              HierarchyLevelContainer hierarchyLevelContainer,
                              String testSessionContainerUID) {
    [..]
    this.statementAttic = new Attic<List<org.codecover.model.mast.Statement>>();
}

private Location createLocation(int startOffset, int endOffset) {
    return this.builder.createLocation(this.sourceFile, startOffset, endOffset);
}

private LocationList createLocationList(int startOffset, int endOffset) {
    if (startOffset == -1 && endOffset == -1) {
        return this.builder.createEmptyLocationList();
    }

    if (startOffset != -1 && endOffset != -1) {
        Location location = createLocation(startOffset, endOffset);
        List<Location> listOfLocations = Collections.<Location>singletonList(location);
        return this.builder.createLocationList(listOfLocations);
    }

    String message = "startOffset == -1 ^ endOffset == -1";
    Exception exception = new IllegalStateException(message);
    this.builder.getLogger().fatal(message, exception);

    // never reached cause fatal throws an Exception
    return null;
}

private void popTopLevelHieraryLevelsFromAttic(int start,
                                               int end,
                                               int headerStartOffset,
                                               int headerEndOffset) {
    if (this.statementAttic.size() != 1) {
        String message = "this.statementAttic.size() != 1";
        Exception exception = new IllegalStateException(message);
        this.builder.getLogger().fatal(message, exception);
    }

    List<StatementSequence> programStatements = createStatementSequenceListFromAttic();
    HierarchyLevel programHL = this.builder.createHierarchyLevel(
            createLocationList(start, end),
            "PROGRAM",
            createLocationList(headerStartOffset, headerEndOffset),
            HierarchyLevelTypes.getProgramType(this.builder),
            Collections.<HierarchyLevel>emptyList(),
            programStatements);
    this.hierarchyLevelContainer.addHierarchyLevelToRoot(programHL);
}

[..]

@Override
public void visit(CompilationUnit n) {
   int startOffset = 0;
   int endOffset;
   int headerStartOffset;
   int headerEndOffset;
   pushNewStatementLevelToAttic();

   // Declaration()
   n.f0.accept(this);
   this.statementManipulator.writeDeclarations(this.counter.getStatementCount());
   this.branchManipulator.writeDeclarations(this.counter.getBranchCount());
   this.conditionManipulator.writeDeclarations(this.counter);
   this.loopManipulator.writeDeclarations(this.counter.getLoopCount());

   headerStartOffset = StartOffset.getStartOffset(n.f1);
   headerEndOffset = headerStartOffset + 7;
   // Program()
   n.f1.accept(this);
   // ( <EOL> )?
   n.f2.accept(this);
   // ( <EOF> )?
   n.f3.accept(this);

   endOffset = super.getLastEndOffset();
   popTopLevelHieraryLevelsFromAttic(startOffset, endOffset,
           headerStartOffset, headerEndOffset);
}

OK, this is a lot of code. What is it doing? The the variable statementAttic has been discussed in detail above. We have to initialize it in the constructor. The method createLocation can create a simple Location out of a start and an end offset. The method createLocationList can create a LocationList out of a start and an end offset. Again, the MAST often expects a LocationList rather than a single Location. For this reason, the method createLocationList only encapsulates a single Location in a LocationList.

The next lines we have added are in the visit(CompilationUnit n) method. Here we get the offsets of the whole source file and of the token PROGRAM. Therefore we need the class StartOffset, that we have added earlier. This class can visit a Node and traverses until it has found the first NodeToken. Then its start offset is returned. The TreeDumper, that is the super class of the InstrumentationVisitor, has a method getLastEndOffset. This can be used to get the end offset of the very last token printed out.

Besides the offsets, we have added pushNewStatementLevelToAttic() at the beginning to add a new list at the statement attic. The method popTopLevelHieraryLevelsFromAttic at the end can then be used to pop the highest statement list from the attic and create a HierarchyLevel out of it. The MastBuilder.createHierarchyLevel method has a lot of arguments, that have to be collected first – e.g. various Locations, a name and a HierarchyLevelType. For this type we can use the class HierarchyLevelTypes, that has been copied before (see HierarchyLevel).

All in all, we have created the basis to create all the statements of the MAST. We will continue with this in the next section.

The BasicStatements

We start with the Assignment and File statement, which are both BasicStatements of the MAST. We go to the method InstrumentationVisitor.visit() and add some lines:

[..]

private CoverableItem createCoverableItem(String id) {
    return this.builder.createCoverableItem(this.sourceFile.getFileName(), id);
}


private void atticStatement(Node statement, String statementID) {
    if (statementID == null) {
        this.builder.getLogger().fatal("statementID == null");
    }
    int startOffset = StartOffset.getStartOffset(statement);
    int endOffset = super.getLastEndOffset();

    LocationList locationList = createLocationList(startOffset, endOffset);
    org.codecover.model.mast.Statement newStatement = this.builder
            .createBasicStatement(locationList,
                                  createCoverableItem(statementID),
                                  Collections.<RootTerm> emptySet());
    this.statementAttic.bottom().add(newStatement);
}

@Override
public void visit(Statement n) {
    n.f0.accept(this);
    String statementID = this.counterIDProvider.nextStatementID();
    if (n.f0.choice instanceof AssignmentStatement ||
        n.f0.choice instanceof FileStatement) {
        atticStatement(n.f0.choice, statementID);
    }

    this.statementManipulator.manipulate(n, statementID);
}

The visit method has a look, whether the visited Statement is an AssignmentStatement or a FileStatement. Only in this condition, the node is considered to be a BasicStatement of the MAST. The method atticStatement uses the MastBuilder to create this BasicStatement. The method createCoverableItem is a helper method to create a coverable item that is needed for coverage measurement. For this reason, it is the exact same statementID as we used for coverage measurement.

You want to test what you have done? This is not so simple, because we have no viewer for the MAST. But you have to change the main method either to avoid NullPointerExceptions. Try this:

MASTBuilder mastBuilder = new MASTBuilder(new SimpleLogger());
File targetFile = new File("example.xpl");
SourceFile sourceFile = mastBuilder.createSourceFile(targetFile.getName(),
        FileTool.getContentFromFile(targetFile));
CharStream charStream = new SimpleCharStream(new StringReader(sourceFile.getContent()));
XampilParser parser = new XampilParser(charStream);
InstrumentableItemCounter counter = new InstrumentableItemCounter();
CompilationUnit compilationUnit = parser.CompilationUnit(counter);
PrintWriter writer = new PrintWriter(System.out);
HierarchyLevelType rootType = HierarchyLevelTypes.getSourceFileType(mastBuilder);
HierarchyLevelContainer rootHierarchyLevelContainer = new HierarchyLevelContainer(
        rootType.getInternalName(), rootType, rootType);
InstrumentationVisitor visitor = new InstrumentationVisitor(writer,
        counter,
        mastBuilder,
        sourceFile,
        rootHierarchyLevelContainer,
        UUID.randomUUID().toString());
visitor.setStatementManipulator(new DefaultStatementManipulator());
visitor.setBranchManipulator(new DefaultBranchManipulator());
visitor.setLoopManipulator(new DefaultLoopManipulator());
visitor.setConditionManipulator(new DefaultConditionManipulator());
visitor.visit(compilationUnit);
writer.flush();

The ConditionalStatements

In the last section, we have ignored, that there are other statements – e.g. IF. Now, we will create a ConditionalStatement out of it. So we have to add the following lines:

[..]

private Branch createExplicitBranchFromAttic(String branchID,
                                             int startOffset,
                                             int endOffset,
                                             int decisionStartOffset,
                                             int decisionEndOffset) {
    LocationList locationList = createLocationList(startOffset, endOffset);
    LocationList locationListDecision = createLocationList(decisionStartOffset,
            decisionEndOffset);
    StatementSequence statementSequence = createStatementSequenceFromAttic();

    return this.builder.createBranch(locationList,
            createCoverableItem(branchID),
            false,
            locationListDecision,
            statementSequence);
}

private Branch createImplicitBranch(String branchID) {
    LocationList locationList = this.builder.createEmptyLocationList();
    LocationList locationListDecision = this.builder.createEmptyLocationList();
    StatementSequence statementSequence = this.builder.createStatementSequence(
            this.builder.createEmptyLocationList(),
            Collections.<org.codecover.model.mast.Statement> emptyList());

    return this.builder.createBranch(locationList,
            createCoverableItem(branchID),
            true,
            locationListDecision,
            statementSequence);
}

private void createConditionalStatementAndPushIt(String statementID,
        int startOffset,
        int endOffset,
        RootTerm rootTerm,
        List<Branch> branchList,
        int keywordStartOffset,
        int keywordEndOffset) {
    LocationList locationList = createLocationList(startOffset, endOffset);
    Location keywordLocation = createLocation(keywordStartOffset, keywordEndOffset);
    Set<RootTerm> setRootTerms;

    if (rootTerm == null) {
        setRootTerms = Collections.<RootTerm> emptySet();
    } else {
        setRootTerms = new HashSet<RootTerm>();
        setRootTerms.add(rootTerm);
    }

    ConditionalStatement conditionalStatement = this.builder.createConditionalStatement(
            locationList,
            createCoverableItem(statementID),
            setRootTerms,
            branchList,
            keywordLocation);
    this.statementAttic.bottom().add(conditionalStatement);
}

@Override
public void visit(Statement n) {
    String statementID = this.counterIDProvider.nextStatementID();
    if (n.f0.choice instanceof AssignmentStatement ||
        n.f0.choice instanceof FileStatement) {
        n.f0.accept(this);
        // create a MAST Statement here
        // the statement has to be visited BEFORE
        atticStatement(n.f0.choice, statementID);
    } else if (n.f0.choice instanceof IfStatement) {
        IfStatement ifStatement = (IfStatement) n.f0.choice;
        ifStatement.statementID = statementID;
        ifStatement.accept(this);
    } else if (n.f0.choice instanceof WhileStatement) {
        WhileStatement whileStatement = (WhileStatement) n.f0.choice;
        whileStatement.statementID = statementID;
        whileStatement.accept(this);
    } else if (n.f0.choice instanceof SwitchStatement) {
        SwitchStatement switchStatement = (SwitchStatement) n.f0.choice;
        switchStatement.statementID = statementID;
        switchStatement.accept(this);
    }

    this.statementManipulator.manipulate(n, statementID);
}

@Override
public void visit(IfStatement n) {
    final int startOffSet = n.f0.startOffset;
    final int endOffset;
    final int keywordStartOffset = startOffSet;
    final int keywordEndOffset = n.f0.endOffset;
    final int thenStartOffset;
    final int thenEndOffset;
    final int elseStartOffset;
    final int elseEndOffset;

    final String thenBranchID = this.counterIDProvider.nextBranchID();
    final String elseBranchID = this.counterIDProvider.nextBranchID();
    final String ifConditionID = this.counterIDProvider.nextConditionID();

    final Branch thenBranch;
    final Branch elseBranch;

    XampilExpressionParser xampilExpressionParser = new XampilExpressionParser();
    InstrBooleanTerm instrBooleanTerm = xampilExpressionParser.parse(n.f1);
    BooleanTerm booleanTerm = instrBooleanTerm.toBooleanTerm(this.builder,
            this.sourceFile);
    RootTerm rootTerm = this.builder.createRootTerm(booleanTerm,
            createCoverableItem(ifConditionID));

    // Instrumenting the boolean term
    List<InstrBasicBooleanTerm> termList = new LinkedList<InstrBasicBooleanTerm>();
    instrBooleanTerm.getAllBasicBooleanTerms(termList);

    this.conditionManipulator.manipulate(ifConditionID, termList);
    // <IF>
    n.f0.accept(this);
    // Expression
    n.f1.accept(this);
    // <THEN>
    n.f2.accept(this);
    // <EOL>
    n.f3.accept(this);

    this.branchManipulator.manipulateIf(n, thenBranchID);
    if (n.f4.present()) {
        thenStartOffset = StartOffset.getStartOffset(n.f4);
    } else {
        thenStartOffset = -1;
    }
    pushNewStatementLevelToAttic();

    // ( Statement() )*
    n.f4.accept(this);
    thenEndOffset = super.getLastEndOffset();

    thenBranch = createExplicitBranchFromAttic(thenBranchID,
                                               thenStartOffset,
                                               thenEndOffset,
                                               -1, -1);

    NodeOptional elseOption = n.f5;
    if (elseOption.present()) {
        // the else is present
        NodeSequence elseSequence = (NodeSequence) elseOption.node;
        // <ELSE>
        elseSequence.nodes.get(0).accept(this);
        // <EOL>
        elseSequence.nodes.get(1).accept(this);

        this.branchManipulator.manipulateElse(n, elseBranchID, false);

        NodeListOptional statementList = (NodeListOptional) elseSequence.nodes.get(2);
        if (statementList.present()) {
            elseStartOffset = StartOffset.getStartOffset(statementList);
        } else {
            elseStartOffset = -1;
        }
        pushNewStatementLevelToAttic();

        // ( Statement() )*
        statementList.accept(this);
        elseEndOffset = super.getLastEndOffset();

        // create the explicit else branch
        elseBranch = createExplicitBranchFromAttic(elseBranchID,
                                                   elseStartOffset,
                                                   elseEndOffset,
                                                   -1, -1);
    } else {
        this.branchManipulator.manipulateElse(n, elseBranchID, true);

        // create the implicit else branch
        elseBranch = createImplicitBranch(elseBranchID);
    }

    // <ENDIF>
    n.f6.accept(this);
    // <EOL>
    n.f7.accept(this);

    endOffset = super.getLastEndOffset();
    List<Branch> branchList = new Vector<Branch>(2);
    branchList.add(thenBranch);
    branchList.add(elseBranch);

    createConditionalStatementAndPushIt(n.statementID,
                                        startOffSet,
                                        endOffset,
                                        rootTerm,
                                        branchList,
                                        keywordStartOffset,
                                        keywordEndOffset);
}

[..]

Again, this is a lot of code we have to discuss. We start with the helper method createExplicitBranchFromAttic. It creates LocationLists for the whole branch and for the decision. The decision is meant to be the position of a value or expression, that stands for branch. For the then and else branch this decision location is not needed. For this reason the offsets can be set to -1 and by the way leads to an empty LocationList. This methods pops the lowest list of the statement attic, creates a StatementSequence and uses the MastBuilder to create a Branch.

The method createImplicitBranch has the same usage, but it is only for branches that are implicit. Implicit means, that the branch is not declared in the original source code, but could be (see implicit).

The method createConditionalStatementAndPushIt gets a list of explicit or implicit Branches and creates a ConditionalStatement out of it. The start and end offset refer to the start and end position of the whole ConditionalStatement. The RootTerm is the boolean expression, that is for example contained in an IF statement. The offset of the keyword means the position of the keyword like IF or SWITCH.

The visit(Statement n) method has to be extended to differentiate between the various Statements. This is needed because we have to hand over the statementID by setting a new field of a IfStatement, SwitchStatement and WhileStatement. This public field has to be created in all three classes now.

And now we consider the visit(IfStatement n). At the heading we declare some offset variables. Some can be initialized here – e.g.for the keyword IF. A few lines lower, we transform the InstrBooleanTerm into a BooleanTerm of the mast. We can use the simple method toBooleanTerm. The MAST requires a RootTerm rather than a BooleanTerm. So we have to encapsulate it in such a term.

Around the accept of the ( Statement() )* of the then branch we have on the one side the initialization of the start offset of the then branch. Very important: we have to call pushNewStatementLevelToAttic(). This is for all the statements that occur in the then branch.

The same is done for the else. Here we have to decide, whether the else is explicit or implicit. At the end of the method, we create a ConditionalStatement out of all the collected objects. The method createConditionalStatementAndPushIt is perfect for this purpose.

We do not discuss the MAST creation for switch. It is similar and can be seen in the final version of the source files.

The LoopingStatement

The last remaining statement of the MAST is the LoopingStatement. We have done a lot of preparatory work, but have to add a lot of lines of code too:

[..]

private void createLoopingStatementAntPushIt(String statementID,
        int startOffset,
        int endOffset,
        RootTerm rootTerm,
        int keywordStartOffset,
        int keywordEndOffset,
        String loopIDZero,
        String loopIDOnce,
        String loopIDAbove,
        boolean optionalBodyExecution) {
    LocationList locationList = createLocationList(startOffset, endOffset);
    Location keywordLocation = createLocation(keywordStartOffset, keywordEndOffset);
    StatementSequence statementSequence = createStatementSequenceFromAttic();
    Set<RootTerm> setRootTerms;

    if (rootTerm == null) {
        setRootTerms = Collections.<RootTerm> emptySet();
    } else {
        setRootTerms = new HashSet<RootTerm>();
        setRootTerms.add(rootTerm);
    }

    LoopingStatement loopingStatement = this.builder.createLoopingStatement(
            locationList,
            createCoverableItem(statementID),
            setRootTerms,
            statementSequence,
            keywordLocation,
            createCoverableItem(loopIDZero),
            createCoverableItem(loopIDOnce),
            createCoverableItem(loopIDAbove),
            optionalBodyExecution);
    this.statementAttic.bottom().add(loopingStatement);
}

@Override
public void visit(WhileStatement n) {
    final int startOffSet = n.f0.startOffset;
    final int endOffset;
    final int keywordStartOffset = startOffSet;
    final int keywordEndOffset = n.f0.endOffset;

    final String whileLoopID = this.counterIDProvider.nextLoopID();
    final String whileConditionID = this.counterIDProvider.nextConditionID();

    XampilExpressionParser xampilExpressionParser = new XampilExpressionParser();
    InstrBooleanTerm instrBooleanTerm = xampilExpressionParser.parse(n.f1);
    // create BooleanTerm BEFORE instrumenting
    BooleanTerm booleanTerm = instrBooleanTerm.toBooleanTerm(this.builder,
            this.sourceFile);
    RootTerm rootTerm = this.builder.createRootTerm(booleanTerm,
            createCoverableItem(whileConditionID));

    List<InstrBasicBooleanTerm> termList = new LinkedList<InstrBasicBooleanTerm>();
    instrBooleanTerm.getAllBasicBooleanTerms(termList);
    this.conditionManipulator.manipulate(whileConditionID, termList);

    pushNewStatementLevelToAttic();

    this.loopManipulator.manipulateBeforeWhile(n, whileLoopID);

    // <WHILE>
    n.f0.accept(this);
    // Expression(basicBooleanCounter)
    n.f1.accept(this);
    // <DO>
    n.f2.accept(this);
    // <EOL>
    n.f3.accept(this);

    this.loopManipulator.manipulateInWhile(n, whileLoopID);

    // ( Statement() )*
    n.f4.accept(this);
    // <ENDWHILE>
    n.f5.accept(this);
    // <EOL>
    n.f6.accept(this);

    this.loopManipulator.manipulateAfterWhile(n, whileLoopID);

    endOffset = super.getLastEndOffset();
    createLoopingStatementAntPushIt(n.statementID,
            startOffSet,
            endOffset,
            rootTerm,
            keywordStartOffset,
            keywordEndOffset,
            CounterIDProvider.generateLoopSubIDZero(whileLoopID),
            CounterIDProvider.generateLoopSubIDOne(whileLoopID),
            CounterIDProvider.generateLoopSubIDAbove(whileLoopID),
            false);
}

[..]

The helper method createLoopingStatementAntPushIt is responsible to create all the LocationLists and pop the lowest list of the statement attic to create the loop body. Finally the MastBuilder is used to create the LoopingStatement object and the looping statement is pushed to the attic. The flag optionalBodyExecution of MastBuilder.createLoopingStatement is used to indicate whether the body has to be executed at least once (false) or is skipped, if the expression is false for the first execution (true). Another important point is, that there are four CoverableItems required. One for the statement coverage and three for the loop coverage. We remember, that the loop coverage has a look at the number of executions of the loop body (see design of loop coverage).

And what was added in the visit(WhileStatement n)? Like in the visit(IfStatement n) we start to declare and initialize some offsets. Then we transform the instrumenter boolean term into a RootTerm. Before the visiting of the ( Statement() )*, we push a new list to the statement attic.

After all the visiting, we can use createLoopingStatementAntPushIt to create and push a new ConditionalStatement.

Download sources

As announced before, you can download all the finished sources of the parser and the instrumenter for Xampil: