Heap Unit Testing Plan

Document formatted by vherva at Fri Apr 24 11:23:43 1998 on the host schemestation. This document is produced by the SchemeStation project during the Tik-76.115 course.

1 Purpose
	This document describes the unit testing of the SCHEMESTATION heap system. The purpose of testing is to show that the heap is capable to implement the heap specification, function properly, give expected values on all operations and report and behave well under erratic input. The limits of functionality are tested by different erratic input of different levels of error severity.
2 Module testing
	A test program(s) is set up to throughoutly test the module. The program will perform all basic operations of the heap implementation and all the (meaningful) combinations of operations and internal states to ensure correct operation. The program may be divided into two or more pieces to test nonfunctionality as well as possible. The heap can't (or isn't meaningful to) check all of its input, and thus there may be inputs that crash the test program (it must be ensured, that these conditions can't happen on the actual use environment).
2.1 Per function testing
	Each function will be separately tested considering: Operational validity Illegal arguments
2.2 Heap-context testing
	Heap [Heap Module Specification] interface is tested by creating and modifying heaps. The following aspects are tested: Type errors Domain errors Heap state consistency.
2.3 The test program
	The testing program will test the following aspects: Simple operations of all the heap types (creation, setting, getting) More complex tests on the heap testing garbage collection and bit string operation consistency (loopy structures, substring operations). Tests for linearisations (generating "generic" test structures with multiple references, loops, and all object types, modifying bit strings inside linearisations, delinearising heaps). Stress tests for certain elements (bit string table expansion test, generic stress tet by generating complex data structures). Heaps are generated and destroyed multiple times during these tests. The another part of the testing, error recovery testing may be performed using different test program that Tests type and domain errors, Tests heap behavior when performing a delinearisation of illegal heap (containing incorrect data that can't be generated by heap), Tests heap behavior with damaged heap linearisation header, Tests heap behavior with missing value initialisations. Last two of the tests can very probably crash the test program. Thus it's probably better to run these tests with special options or own test programs. All tests are performed with all different garbage collection modes (automatic collection/not, dynamic expansion/not) and with GC performed after every heap operation or just when needed.
3 Results
	Test cases (first part: (D)one, (U)ndone, (I)ncomplete, second part: (S)uccess, (U)nsuccess, (I)ncomplete (F)atal): Name Status Result Comments Heap initialisation and finalisation, GC control  D  S  includes root frame manipulation  Elementary typed data operations  D  S  type specific creation, read, write and copy semantics  Complex data structures  D  S  Various looped data structures  Constant table semantics  I  U/I  Constant tables should be read-only. Partially implemented.  Linearisation and delinearisation  D  S  Address remapping support  D  S  Type errors  D  S  Stress testing  D  S  Domain errors  D  S  (Indexing)  Source as target check  D  S  NULL pointers  D  S  Interoperability  D  S  (Intel, Alpha)  Broken heaps  D  I/F  Broken linearisations can crash the heap.
3.1 Remarks
	The "error recovery testing" part of the plan wasn't implemented as fully as propsed. Other parts were implemented as specified in the plan. The stress testing (along with the general testing of the running system) revealed spots where system efficiency is unoptimal (the root push/pop operations, linearization implementation using small heaps). These features are improved.