Lecture 8, Stubs, Output and Testing
Part of
the notes for 22C:196:002 (CS:4908:0002)
|
In developing any large project, there will always be places where you know more work could be done but you cannot do it now. Particularly in a group project, you cannot rely on your own memory to remind you to go back and flesh out those details. One way to deal with this is to agree, across the group, on a standard textual marker to show where additional work is needed. This way, any group member looking at the code can see if something is missing.
Here is an example, a fragment of a Kestrel lexical analyzer under development. Specifically, this is the part of the lexical analyzer that identifies character strings:
} else if ((ch == '"') || (ch == '\'')) { // string
int quote = ch; // remember opening quote mark
lex_next.type = STRING;
SCAN(); // skip opening quote
while ((ch != EOF) && (ch != quote)) { // scan over string
// ==BUG== must save the string
SCAN();
}
if (ch == EOF) {
er_gotbutwant( ch, ER_QUOTE, line );
// must not SCAN
} else {
SCAN(); // skip closing quote
}
This has a documented bug, flagged by a comment starting with the text ==BUG== because the code merely scans the string without saving anything -- the string pool is not yet available to store the text of the string, so nothing is stored.
By using a standard string such as ==BUG== to mark stubs in your code, a simple search with grep can show you all the stubs in your project, giving you a quick way to see what remains unfinished. In a large project, with many people sharing the work, communicating through bug notices in the code can be a far more effective way to direct the work than having group meetings.
It is important to note that, while the above code is incomplete, it is free of syntax errors, and in fact, it has been compiled and tested. If, at each step in developing the program, you can test what you have, you are far better off than if you can't. When you make changes, it is a good idea to verify that you can make the code after each step, so that when you commit, you commit working code.
Here, for example, is a test of the above code to trigger the call to er_gotbutwant() in the event of an unclosed string:
% echo ' "----' | testlex Found 'EOF' on line 1 when closing quote expected.
The testlex program used as scaffolding to conduct this test is trivial. Here is the entire main program:
main(){
// ==BUG== should open argv[1] if it is provided
lex_open( NULL ); // read from stdin
do {
lex_put( &lex_this, stdout );
putchar( '\n' );
lex_advance();
} while (!(lex_this.type == ENDFILE));
lex_put( &lex_this, stdout );
putchar( '\n' );
}
That error message, "found 'EOF' on line 1 when closing quote expected" implies a fairly sophisticated mechanism to output what the program found in the input text. The call to er_gotbutwant() merely passed the character that was found, yet it was output as 'EOF'. If the symbol that was encounterd had been printable, this would merely require outputting the symbol, in quotes, but for end-of-file and control characters, we need a translation mechanism. Here is the code that was included in the error reporting subsystem to support the above:
// names of ASCII control characters, in order
static const char * control_chars[] = {
"NUL","SOH","STX","ETX","EOT","ENQ","ACK","BEL",
"BS", "HT", "LF", "VT", "FF", "CR", "SO", "SI",
"DLE","DC1","DC2","DC3","DC4","NAK","SYN","ETB",
"CAN","EM", "SUB","ESC","FS", "GS", "RS", "US"
};
static void putascii( int ch ) {
if (ch < 0) { // EOF is the only one that should satisfy this
fputs( "EOF", stderr );
} else if (ch < ' ') {
fputs( control_chars[ ch ], stderr );
} else if (ch < 127) {
fputc( ch, stderr );
} else if (ch == 127) {
fputs( "DEL", stderr );
} else if (ch > 127) {
fputs( "??", stderr ); // ==BUG== not Unicode Clean!
}
}
We can do similar things in several other cases, for example, the code in lex_put() (the lexical analysis routine for outputting one lexeme to a file) can use such a table structure to translate from the internal codes for punctuation marks back to the textual representaiton of the mark, for example, translating from the enumeration constant P_GE to the string ">=".
When accumulating a number, the obvious code to use to add in successive digits is something like this:
value = (value * radix) + digit;
This works correctly, assuming that value is initially zero and that digit is, for each succesive application, the integer value associated with the successive digits.
But there are limits. If the variable value is declared as being of type uint32_t, the maximum 32-bit value is (in C notation) 0xFFFFFFFF, which is also defined as UINT32_MAX. If you evaluate this code in C or C++, and the correct result would be larger than this value, the program will fail silently, delivering just the least significant 32 bits of the result and discarding everything greater than that.
So, how do you write code that detects oversized values? You need to do the math. All of the following expressions are equivalent, from a mathematicians viewpoint:
(value * radix) + digit > UINT32_MAX (value * radix) > (UINT32_MAX - digit) value > (UINT32_MAX - digit)/ radix
Evaluating each of the first two of the above expressions can involve values greater than UINT32_MAX, and so will not produce correct results on a 32-bit computer. The final expression, though, is safe. It never overflows.
Of course, in your compiler, you should not declare the value of a lexeme to be of type uint32_t, nor should you use the naked constant 0xFFFFFFFF in your code. That makes it difficult to change things later, for example, if you wanted to shift to a 64-bit computer. Instead, use a named type, for example lex_value declared as uint32_t, and in an immediately adjacent declaration, define the constant LEX_MAXVAL (or something) to be the largest value of that type. This way, with changes to just two lines, you can change the type and limit that apply to numeric constants.
As you develop programs as complex as a compiler, there are huge numbers of test cases that you need to develop. Consider, in one small area, the problem of evaluating numeric lexemes. The following potential errors should be tested for in a Falcon numeric lexeme:
Each of these should be detected, and the code to detect each of them sould be tested. Here, for example, is a sequence of tests (using the test framework described above) to test the number too large problem in one Falcon lexical analyzer, verifying that the largest legal value is accepted while one larger than that is rejected:
% echo '16#FFFFFFFF' | testlex 4294967295 EOF % echo '4294967295' | testlex 4294967295 EOF % echo '4294967296' | testlex Error on line 1: Numeric constant too big. % echo '16#100000000' | testlex Error on line 1: Numeric constant too big.
Here are similar tests for the other issues raised above:
% echo '16#' | testlex Found 'LF' on line 1 when digit expected. % echo '32#ZZ' | testlex 1023 EOF % echo '33#ZZ' | testlex Error on line 1: Numeric radix too big. % echo '31#ZZ' | testlex Error on line 1: Digit larger than radix.
In each of the above cases, we have adopted a simple testing strategy: All of these involve numeric bounds of one kind or another, so we have conducted each test with the largest legal value, in which case, we expect no error, and then again, with the next larger value, in which case we expect failure.
Note that these tests are little! Instead of attempting to produce one large test file that elicits the behavior, we have constructed lots of little test files. Files so small that they are merely quoted arguments to the shell's echo command which then pipes them into our test program.
Any time we change the lexical analyzer, we really ought to re-run all of our tests to see that our changes have not broken anything. This suggests that we ought to automate the testing. The above tests were done by typing the echo commands, and this got old quickly. We could create a file of such commands, or we could start shell scripting to make the automation even tighter. Consider the following:
Note that the program should usually terminate with EXIT_SUCCESS, but if any errors are encountered, it whould exit with EXIT_FAILURE. This means that a shell script can test to see if any particular test was successful or not. So, an obvious thing to do is write two scripts:
These special test failure messages should stand out! ALL CAPS or long lines of dashes are important here. Of course, you should scan the actual test output to see if the messages are right, but having an automated test script makes it much easier to test and test and retest as you make changes to the compiler.
Each time you make a change that is testable, you should also add to the test scripts to test that change. As the compiler grows, it will be useful to produce generalizations of the test script that can test other parts of the code. This means that your test script framework is as much an interesting programming problem as the compiler itself.
One thing you can definitely do is include a makefile target for running the tests. Consider having make test actually administer all of the tests for your compiler and either terminate with success or with the make program itself declaring the failure.