This review is presented in 3 questions due to the amount of code:
- Part A contains the Lexical Analyzer and the main portion of the unit test code.
- Part B (this question) contains the lower level unit tests called in Part A
- Part C contains common unit test code that is included in all of the unit tests to be written.
Background
Back in June I provided this answer to a question here on code review. I advised the person that asked the question to use enums rather than numbers to represent the opcodes, but upon further consideration I thought that the virtual machine really needed an editor as the front end and I have been working on that. An editor will require a translator to convert text into the numbers the virtual machine uses for opcodes and operands. The translator is composed of a parser and a lexical analyzer. The lexical analyzer is complete, unit tested and debugged so I am presenting it here for code review with the unit tests.
This program is written in C because the original question was written in C. I tried to stick to the C90 standard as much as possible, but I did include _strdup() which is in the latest standard (perhaps it is strdup() in the latest standard, but Visual Studio suggested _strdup()).
Why did I write unit tests for the lexical analyzer?
- It is a best practice at many companies that do software development.
- The code was very complex, at the time it was not a state machine (unit testing convinced me to go that route). It was over 450 lines of un-commented code in the parser module and growing.
- I had gotten to the point where I wanted to test/debug the lexical analyzer and the parser wasn't working so I wanted a program that ran only the lexical analyzer.
- I wanted to test/debug the code in a bottom up manner to make sure the lowest level functions were working correctly before testing the higher level functions.
The benefits of unit testing were that it forced me to create a more modular design and to redesign the lexical analyzer to use a state machine rather another method. The results are less code and a better working lexical analyzer. It will also force a redesign of the parser, but that is for another question.
Questions
I learned C a long time ago from K&R “The C Programming Language” Version 1 (pre C89/C90).
- Other than compiling this –O3 what can I do to optimize this code?
- Are there any features in the more modern versions of C that could reduce the amount of code?
- Is there archaic C usage that is not customary to use anymore?
- Are the unit tests missing any test cases, especially edge cases?
- Are there any memory leaks?
- Is the code readable?
- I don’t like the fact that I need to include some of the unit test files in internal_sytax_state_tests.c do you see any way around this?
Code Available:
Rather than copy and pasting this code it is available in my GitHub Repository. The code as presented in these 3 questions is on the branch Before_First_Code_Review, updates including those based on the review will be added to the master branch.
The unit test ouput is always saved to a .txt file, a comparison text file is the unit test folder in the repository. The unit test output is 1827 lines so it is not included here in the question.
There is a CMakeLists.txt file in the unit test directory, but I'm not sure it works so it isn't posted here. If anyone would like to test it, let me know what to do or how to fix it. I could give you permission to update it in GitHub.
internal_character_transition_unit_tests.c
/*
* internal_character_transition_unit_tests.c
*
* This file contains the lowest level of unit testing for the lexical analyzer.
* It tests the lexical state transitions for particular characters. While it
* is a C source file rather than a header file it is included by static functions
* internal_sytax_state_tests.c because it is testing within lexical_analyzer.c.
* The file internal_sytax_state_tests.c is included by lexical_analyzer.c. as
* well. This file was separated out of internal_sytax_state_tests.c because at
* some point that file became too large and complex.
*/
#ifndef INTERNAL_CHARACTER_TRANSITION_UNIT_TEST_C
#define INTERNAL_CHARACTER_TRANSITION_UNIT_TEST_C
static void log_unit_test_get_transition_character_type_failure(
Test_Log_Data* log_data, unsigned char candidate, Syntax_State current_state,
State_Transition_Characters expected_type, State_Transition_Characters actual_type)
{
// Force failures to be reported
bool stand_alone = log_data->stand_alone;
log_test_status_each_step2(log_data);
char out_buffer[BUFSIZ];
sprintf(out_buffer, "\tcurrent_state = %s input character = %c\n",
state_name_for_printing(current_state), candidate);
log_generic_message(out_buffer);
sprintf(out_buffer, "\tExpected Transitiion %s Actual Transition %s\n\n",
transition_character[expected_type], transition_character[actual_type]);
log_generic_message(out_buffer);
log_data->stand_alone = stand_alone;
}
typedef enum test_character_case
{
LOWER_CASE = 0,
UPPER_CASE = 1
} TEST_CHARACTER_CASE;
static State_Transition_Characters get_expected_alpha_transition_character_type(
unsigned char input, Syntax_State current_state)
{
input = (unsigned char)toupper(input);
switch (input)
{
case 'A':
case 'B':
case 'C':
case 'D':
case 'E':
case 'F':
case 'X':
if (current_state == ENTER_OPERAND_STATE || current_state == OPERAND_STATE
|| current_state == END_OPERAND_STATE)
{
return DIGIT_STATE_TRANSITION;
}
else
{
return ALPHA_STATE_TRANSITION;
}
break;
default:
return ALPHA_STATE_TRANSITION;
break;
}
}
typedef State_Transition_Characters(*STFfunct)(unsigned char input, Syntax_State current_state);
static bool core_alpha_character_transition_unit_test(Test_Log_Data* log_data, Syntax_State current_state, STFfunct transition_function)
{
bool test_passed = true;
char buffer[BUFSIZ];
for (size_t alphabet = (size_t)LOWER_CASE; alphabet <= (size_t)UPPER_CASE; alphabet++)
{
if (log_data->stand_alone)
{
sprintf(buffer, "\tBegin Positive test path current_state = %s input character = %s\n\n",
state_name_for_printing(current_state), (alphabet == LOWER_CASE) ? "Lower Case" : "Upper case");
log_generic_message(buffer);
}
unsigned char fist_character_to_test = (alphabet == LOWER_CASE) ? 'a' : 'A';
unsigned char last_character_to_test = (alphabet == LOWER_CASE) ? 'z' : 'Z';
for (unsigned char candidate_character = fist_character_to_test; candidate_character <= last_character_to_test; candidate_character++)
{
log_data->status = true;
State_Transition_Characters expected_type = get_expected_alpha_transition_character_type(candidate_character, current_state);
State_Transition_Characters actual_type = transition_function(candidate_character, current_state);
if (expected_type != actual_type)
{
log_data->status = false;
test_passed = log_data->status;
log_unit_test_get_transition_character_type_failure(log_data, candidate_character, current_state, expected_type, actual_type);
}
else
{
log_test_status_each_step2(log_data);
}
}
if (log_data->stand_alone)
{
sprintf(buffer,
"\n\tEnd Positive test path current_state = %s input character = %s\n\n",
state_name_for_printing(current_state),
(alphabet == LOWER_CASE) ? "Lower Case" : "Upper case");
log_generic_message(buffer);
}
}
return test_passed;
}
static bool core_non_alpha_character_transition_unit_test(Test_Log_Data* log_data,
Syntax_State current_state, unsigned char* input, State_Transition_Characters expected_transition[],
size_t positive_path_count, char* local_func_name)
{
bool test_passed = true;
char* keep_old_path = log_data->path;
log_data->path = "Positive";
size_t test_count = 0;
for (unsigned char* test_input = input; *test_input; test_input++, test_count++)
{
if (positive_path_count == test_count)
{
log_end_positive_path(local_func_name);
log_start_negative_path(local_func_name);
log_data->path = "Negative";
}
log_data->status = true;
State_Transition_Characters actual_transistion = get_transition_character_type(
*test_input, current_state);
log_data->status = actual_transistion == expected_transition[test_count];
if (!log_data->status)
{
log_unit_test_get_transition_character_type_failure(log_data, *test_input,
current_state, expected_transition[test_count], actual_transistion);
test_passed = false;
}
else
{
log_test_status_each_step2(log_data);
}
}
log_data->status = test_passed;
log_data->path = keep_old_path;
return test_passed;
}
/*
* Tests limited number of states where alpha is important calls the lower level
* function get_alpha_input_transition_character_type().
*/
static bool unit_test_get_alpha_input_transition_character_type(unsigned test_step)
{
bool test_passed = true;
Test_Log_Data log_data;
init_test_log_data(&log_data, "unit_test_get_alpha_input_transition_character_type",
test_passed, "Positive", test_step == 0);
if (log_data.stand_alone)
{
log_start_positive_path(log_data.function_name);
}
for (size_t state = (size_t)ENTER_OPCODE_STATE; state <= (size_t)END_OPERAND_STATE; state++)
{
test_passed = core_alpha_character_transition_unit_test(&log_data, state,
get_alpha_input_transition_character_type);
}
if (log_data.stand_alone)
{
log_end_test_path(&log_data);
}
return test_passed;
}
static bool unit_test_whitespace_transition(Test_Log_Data* log_data, Syntax_State current_state)
{
bool test_passed = true;
unsigned char input[] = " \t\n\r\v\f";
State_Transition_Characters expected_transition[] =
{
// Positive test path
WHITESPACE_STATE_TRANSITION, WHITESPACE_STATE_TRANSITION, EOL_STATE_TRANSITION,
// Test the negatvie path as well.
EOL_STATE_TRANSITION, ILLEGAL_CHAR_TRANSITION, ILLEGAL_CHAR_TRANSITION
};
size_t positive_path_count = 4; // Change this if more positive path tests are added.
char buffer[BUFSIZ];
sprintf(buffer, "%s whitespace transition test", log_data->function_name);
char* local_func_name = _strdup(buffer);
log_start_positive_path(local_func_name);
if (core_non_alpha_character_transition_unit_test(log_data, current_state,
input, expected_transition, positive_path_count, local_func_name))
{
test_passed = log_data->status;
}
log_end_negative_path(local_func_name);
free(local_func_name);
log_data->status = test_passed;
return test_passed;
}
static void init_digit_test_data(unsigned char* input, State_Transition_Characters
expected_transition[], size_t* positive_test_path, Syntax_State current_state)
{
State_Transition_Characters* expected_ptr = expected_transition;
if (current_state == ENTER_OPERAND_STATE || current_state == OPERAND_STATE || current_state == END_OPERAND_STATE)
{
for (; *input; input++, expected_ptr++)
{
*expected_ptr = DIGIT_STATE_TRANSITION;
}
*positive_test_path = strlen((const char*)input);
}
else
{
for (; *input; input++, expected_ptr++)
{
if (isdigit(*input))
{
*expected_ptr = DIGIT_STATE_TRANSITION;
(*positive_test_path)++;
}
else
{
*expected_ptr = ALPHA_STATE_TRANSITION; // to force failures use this instead *expected_ptr = DIGIT_STATE_TRANSITION;
}
}
}
}
static bool unit_test_digit_transition(Test_Log_Data* log_data, Syntax_State current_state)
{
bool test_passed = true;
unsigned char* input = (unsigned char*)"0123456789ABCDEFXabcdefx"; // size is currently 24
#define MAX_INPUT_CHARACTERS 24
State_Transition_Characters expected_transition[MAX_INPUT_CHARACTERS];
size_t positive_path_count; // Change this if more positive path tests are added.
init_digit_test_data(input, expected_transition, &positive_path_count, current_state);
char* local_func_name = NULL;
if (log_data->stand_alone)
{
char buffer[BUFSIZ];
sprintf(buffer, "%s digit transition test", log_data->function_name);
local_func_name = _strdup(buffer);
log_start_positive_path(local_func_name);
}
if (core_non_alpha_character_transition_unit_test(log_data, current_state,
input, expected_transition, positive_path_count, local_func_name))
{
test_passed = log_data->status;
}
if (log_data->stand_alone)
{
if (positive_path_count > 10)
{
log_end_positive_path(local_func_name);
}
else
{
log_end_negative_path(local_func_name);
}
}
#undef MAX_INPUT_CHARACTERS
log_data->status = test_passed;
return test_passed;
}
/*
* test the state specified by the caller function. Calls the higher level function
* get_transition_character_type().
*/
static bool unit_test_alpha_transition(Test_Log_Data* log_data, Syntax_State current_state)
{
bool test_passed = true;
char* local_func_name = NULL;
if (log_data->stand_alone)
{
char buffer[BUFSIZ];
sprintf(buffer, "%s alpha transition test", log_data->function_name);
local_func_name = _strdup(buffer);
log_start_positive_path(local_func_name);
}
test_passed = core_alpha_character_transition_unit_test(log_data, current_state,
get_transition_character_type);
if (log_data->stand_alone)
{
log_end_positive_path(local_func_name);
}
return test_passed;
}
static bool unit_test_punctuation_transition(Test_Log_Data* log_data, Syntax_State current_state)
{
bool test_passed = true;
unsigned char input[] = "{},+-/*=&";
State_Transition_Characters expected_transition[] =
{
// Positive test path
OPENBRACE_STATE_TRANSITION, CLOSEBRACE_STATE_TRANSITION, COMMA_STATE_TRANSITION,
// Test the negatvie path as well.
ILLEGAL_CHAR_TRANSITION, ILLEGAL_CHAR_TRANSITION, ILLEGAL_CHAR_TRANSITION,
ILLEGAL_CHAR_TRANSITION, ILLEGAL_CHAR_TRANSITION, ILLEGAL_CHAR_TRANSITION
};
size_t positive_path_count = 3; // Change this if more positive path tests are added.
char buffer[BUFSIZ];
sprintf(buffer, "%s punctuation transition test", log_data->function_name);
char* local_func_name = _strdup(buffer);
log_start_positive_path(local_func_name);
if (core_non_alpha_character_transition_unit_test(log_data, current_state,
input, expected_transition, positive_path_count, local_func_name))
{
test_passed = log_data->status;
}
log_end_negative_path(local_func_name);
free(local_func_name);
log_data->status = test_passed;
return test_passed;
}
typedef bool (*character_transition_test_function)(Test_Log_Data* log_data, Syntax_State state);
static bool unit_test_get_transition_character_type(size_t test_step)
{
bool test_passed = true;
char buffer[BUFSIZ];
Test_Log_Data* log_data = create_and_init_test_log_data(
"unit_test_get_transition_character_type", test_passed, "Positive",
test_step == 0);
if (!log_data)
{
report_create_and_init_test_log_data_memory_failure(
"unit_test_get_transition_character_type");
return false;
}
if (log_data->stand_alone)
{
sprintf(buffer, "STARTING internal unit test for get_transition_character_type("
"unsigned char input, Syntax_State current_state)");
log_generic_message(buffer);
}
character_transition_test_function test_function[] =
{
unit_test_punctuation_transition,
unit_test_alpha_transition,
unit_test_digit_transition,
unit_test_whitespace_transition
};
for (size_t state = (size_t)START_STATE; state <= (size_t)ERROR_STATE; state++)
{
for (size_t unit_test_count = 0; unit_test_count < sizeof(test_function) /
sizeof(*test_function); unit_test_count++)
{
if (!test_function[unit_test_count](log_data, (Syntax_State)state))
{
test_passed = log_data->status;
}
}
}
if (log_data->stand_alone)
{
sprintf(buffer, "\nENDING internal unit test for get_transition_character_type("
"unsigned char input, Syntax_State current_state)\n");
log_generic_message(buffer);
}
free(log_data);
return test_passed;
}
#endif // INTERNAL_CHARACTER_TRANSITION_UNIT_TEST_C
lexical_analyzer_test_data.h
#ifndef LEXICAL_ANALYZER_TEST_DATA_H
#define LEXICAL_ANALYZER_TEST_DATA_H
#include "lexical_analyzer.h"
typedef struct expected_syntax_errors
{
unsigned error_count;
unsigned syntax_check_list[SYNTAX_CHECK_COUNT];
} Expected_Syntax_Errors;
typedef struct lexical_analyzer_test_data
{
unsigned char** test_program;
size_t test_program_size;
Expected_Syntax_Errors* expected_errors;
} Lexical_Analyzer_Test_Data;
extern void deallocate_lexical_test_data(Lexical_Analyzer_Test_Data* deletee);
extern void lexical_analyzer_test_data_allocation_failed(Test_Log_Data* log_data, char* allocating_function,
char* allocation_function);
extern Lexical_Analyzer_Test_Data* init_positive_path_data_for_lexical_analysis(Test_Log_Data* log_data);
extern Lexical_Analyzer_Test_Data* init_negative_path_data_for_lexical_analysis(Test_Log_Data* log_data);
#endif // LEXICAL_ANALYZER_TEST_DATA_H
lexical_analyzer_test_data.c
#include "common_unit_test_logic.h"
#include "lexical_analyzer_test_data.h"
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static void deallocate_test_program(size_t test_program_size, unsigned char **test_program)
{
if (!test_program)
{
return;
}
for (size_t i = 0; i < test_program_size; i++)
{
free(test_program[i]);
}
free(test_program);
}
static void deallocate_expected_data(Expected_Syntax_Errors* expected_errors)
{
if (!expected_errors)
{
return;
}
free(expected_errors);
}
void deallocate_lexical_test_data(Lexical_Analyzer_Test_Data* deletee)
{
if (!deletee)
{
return;
}
if (deletee->expected_errors)
{
deallocate_expected_data(deletee->expected_errors);
deletee->expected_errors = NULL;
}
if (deletee->test_program)
{
deallocate_test_program(deletee->test_program_size, deletee->test_program);
deletee->test_program = NULL;
}
free(deletee);
}
void lexical_analyzer_test_data_allocation_failed(Test_Log_Data* log_data, char* allocating_function,
char* allocation_function)
{
fprintf(error_out_file, "Memory Allocation Error in %s\n", allocating_function);
fprintf(error_out_file, "\t%s failed for allocation of test data\n", allocation_function);
fprintf(error_out_file, "\t Unable to continue %s\n", log_data->function_name);
}
static Lexical_Analyzer_Test_Data* create_and_init_lexical_test_data(unsigned char** test_program,
size_t test_program_size, Expected_Syntax_Errors* expected_data,
Test_Log_Data* log_data, char* allocating_function)
{
Expected_Syntax_Errors* expected_errors_dup = calloc(test_program_size, sizeof(*expected_errors_dup));
if (!expected_errors_dup)
{
lexical_analyzer_test_data_allocation_failed(log_data, "init_positive_path_data_for_lexical_analysis", "calloc");
return NULL;
}
for (size_t step_count = 0; step_count < test_program_size; step_count++)
{
expected_errors_dup[step_count].error_count = expected_data[step_count].error_count;
for (size_t checklist_item = 0; checklist_item < SYNTAX_CHECK_COUNT; checklist_item++)
{
expected_errors_dup[step_count].syntax_check_list[checklist_item] = expected_data[step_count].syntax_check_list[checklist_item];
}
}
unsigned char** test_program_dupe = calloc(test_program_size, sizeof(*test_program_dupe));
if (!test_program_dupe)
{
lexical_analyzer_test_data_allocation_failed(log_data, "init_positive_path_data_for_lexical_analysis", "calloc");
deallocate_expected_data(expected_errors_dup);
return NULL;
}
for (size_t step_count = 0; step_count < test_program_size; step_count++)
{
test_program_dupe[step_count] = (unsigned char*) _strdup((char *)test_program[step_count]);
if (!test_program_dupe[step_count])
{
lexical_analyzer_test_data_allocation_failed(log_data, "init_positive_path_data_for_lexical_analysis", "_strdup");
deallocate_test_program(step_count, test_program_dupe);
deallocate_expected_data(expected_errors_dup);
return NULL;
}
}
Lexical_Analyzer_Test_Data* new_lexical_test_data = calloc(1, sizeof(*new_lexical_test_data));
if (!new_lexical_test_data)
{
lexical_analyzer_test_data_allocation_failed(log_data, allocating_function, "calloc");
return NULL;
}
new_lexical_test_data->test_program_size = test_program_size;
new_lexical_test_data->test_program = test_program_dupe;
new_lexical_test_data->expected_errors = expected_errors_dup;
return new_lexical_test_data;
}
Lexical_Analyzer_Test_Data* init_positive_path_data_for_lexical_analysis(Test_Log_Data* log_data)
{
unsigned char* test_program[] = {
(unsigned char*)" {PUSH, 0x0A},\n", (unsigned char*)" {PUSH, 0x43},\n",
(unsigned char*)"{ PUSH, 0x42 },\n", (unsigned char*)"{ PUSH, 0x41 },\n",
(unsigned char*)"{ OUTPUTCHAR, 0x00 }, \n", (unsigned char*)"{ POP, 0x00 }, \n",
(unsigned char*)"{ OUTPUTCHAR, 0x00 },\n", (unsigned char*)"{ POP, 0x00 },\n",
(unsigned char*)"{OUTPUTCHAR, 0x00},\n", (unsigned char*)"{POP, 0x00},\n",
(unsigned char*)"{HALT, 0x00}"
};
size_t test_size = sizeof(test_program) / sizeof(*test_program);
Expected_Syntax_Errors* expected_errors = calloc(test_size, sizeof(*expected_errors));
if (!expected_errors)
{
lexical_analyzer_test_data_allocation_failed(log_data, "init_positive_path_data_for_lexical_analysis", "calloc");
return NULL;
}
Expected_Syntax_Errors sample_expect_data = { 0, {1, 1, 2, 1, 1, 0, 0, 0, 0, 0, 0} };
for (size_t test = 0; test < test_size; test++)
{
expected_errors[test].error_count = sample_expect_data.error_count;
for (size_t checklist_item = 0; checklist_item < SYNTAX_CHECK_COUNT; checklist_item++)
{
expected_errors[test].syntax_check_list[checklist_item] = sample_expect_data.syntax_check_list[checklist_item];
}
}
expected_errors[test_size - 1].syntax_check_list[COMMA] = 1;
Lexical_Analyzer_Test_Data* positive_test_data = create_and_init_lexical_test_data(
test_program, test_size, expected_errors, log_data, "init_positive_path_data_for_lexical_analysis");
return positive_test_data;
}
Lexical_Analyzer_Test_Data* init_negative_path_data_for_lexical_analysis(Test_Log_Data* log_data)
{
unsigned char* test_program[] =
{
(unsigned char*)" {PUSH, 0x0A},\n", // No problem
(unsigned char*)" PUSH, 0x43},\n", // Missing open brace
(unsigned char*)"{ PUSH, 0x42 ,\n", // Missing close brace
(unsigned char*)" { PUSH, 0x41 }, { OUTPUTCHAR 0x00 }, \n", // Multiple statements on one line missing comma in second statement
(unsigned char*)"{ , 0x00 }, \n", // Missibg opcode
(unsigned char*)"{ OUTPUTCHAR 0x00 },", // Missing comma between opcode and operand
(unsigned char*)"{ POP, },", // Missing OPERAND
(unsigned char*)"{OUTPUTCHAR, 0x00}\n", // Missing last comma
(unsigned char*)"{POP, 0x00 POP},\n", // Illegal characters after operand
(unsigned char*)"HALT" // Missing open brace, commas, operand, close brace
};
size_t test_size = sizeof(test_program) / sizeof(*test_program)
;
Expected_Syntax_Errors expected_errors[] =
{
{0, {1, 1, 2, 1, 1, 0, 0, 0, 0, 0, 0}}, // {PUSH, 0x0A}, No problem
{2, {0, 1, 2, 1, 1, 0, 0, 1, 0, 0, 0}}, // PUSH, 0x43}, Missing open brace and Illegal character in first column
{1, {1, 0, 2, 1, 1, 0, 0, 0, 0, 0, 0}}, // { PUSH, 0x42 , Missing close brace
{1, {2, 1, 2, 1, 1, 0, 0, 0, 1, 0, 0}}, // { PUSH, 0x41 }, { OUTPUTCHAR 0x00 }, Multiple statements on one line missing comma in second statement
{1, {1, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0}}, // { , 0x00 }, Missibg opcode
{1, {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1}}, // { OUTPUTCHAR 0x00 }, Missing comma between opcode and operand
{1, {1, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0}}, // { POP, }, Missing OPERAND
{0, {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0}}, // {OUTPUTCHAR, 0x00}, Missing last comma
{1, {1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0}}, // {POP, 0x00 POP}, Illegal characters after operand
{5, {0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0}} // HALT Missing open brace, commas, operand, close brace
};
Lexical_Analyzer_Test_Data* negative_test_data = create_and_init_lexical_test_data(
test_program, test_size, expected_errors, log_data, "init_negative_path_data_for_lexical_analysis");
return negative_test_data;
}
