Re: A simple unit test framework

This is a multi-part message in MIME format.
--------------050703020605020002080605
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Pete Becker wrote:
....


I have yet to meet a "test" developer that can beat the monte carlo test
for coverage.

OK - I agree, there are cases where a monte-carlo test will never be
able to test adequately, but as a rule, it is better to have a MC test
than not. I have uncovered more legitimate problems from the MC test
than from carefully crafted tests.


I challenge you. I don't think of myself as a tester. I believe you
can't do a better job than I in testing my code. Let's use this "range
map" as an example.

I have attached the header file and the test cases.

Your clain that I "don't understand testing well enough" and so I use an
MC test I think is short sighted.

For example, MC tests are the only tests that I have been able to truly
test multithreaded code. It is nigh impossible for me (or any human) to
truly understand all the interactions in a MT scenario. MC tests almost
always will push every edge of the problem space.

Again, it's not to say that there are no systematic errors that can't be
  discovered using random tests, but these types of errors are exactly
the kind that a good developer knows exist and tests for or even designs
around.

--------------050703020605020002080605
Content-Type: text/plain;
 name="at_rangemap.h"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="at_rangemap.h"

//
// The Austria library is copyright (c) Gianni Mariani 2004.
//
// Grant Of License. Grants to LICENSEE the non-exclusive right to use the Austria
// library subject to the terms of the LGPL.
//
// A copy of the license is available in this directory or one may be found at this URL:
// http://www.gnu.org/copyleft/lesser.txt
//
/**
 * at_rangemap.h
 *
 */

#ifndef x_at_rangemap_h_x
#define x_at_rangemap_h_x 1

#include "at_exports.h"
#include "at_os.h"
#include "at_assert.h"

#include <map>

// Austria namespace
namespace at
{

// ======== TypeRange =================================================
/**
 * TypeRange describes the range of a particular type
 *
 */

template <typename w_RangeType>
class TypeRange
{
    public:

    // range type
    typedef w_RangeType t_RangeType;

    // ======== Adjacent ==============================================
    /**
     * Adjacent returns true if the two parameters are "one apart"
     *
     * @param i_lesser is the lesser of the two values
     * @param i_greater is the greater of the two
     * @return true is no other elements exist between i_lesser and i_greater
     */

    static bool Adjacent(
        const t_RangeType & i_lesser,
        const t_RangeType & i_greater
    ) {

        t_RangeType l_greater_less( i_greater );

        -- l_greater_less; // go to the earlier element

        // deal with wrapping
        if ( i_greater < l_greater_less )
        {
            return false;
        }

        return !( i_lesser < l_greater_less );
    }
};

// ======== RangeMap ==================================================
/**
 * RangeMap is a template that defines ranges.
 *
 */

template <typename w_RangeType, typename w_RangeTraits=TypeRange<w_RangeType> >
class RangeMap
{
    public:

    // range type
    typedef w_RangeType t_RangeType;
    typedef w_RangeTraits t_RangeTraits;

    // index on the end of the range
    typedef std::map< t_RangeType, t_RangeType > t_Map;
    typedef typename t_Map::iterator t_Iterator;

    // ======== AddRange ==============================================
    /**
     * Add a segment to the range.
     *
     * @param i_begin The beginning of the range (inclusive)
     * @param i_end The end of the range (inclusive)
     * @return nothing
     */

    void AddRange( const t_RangeType & i_begin, const t_RangeType & i_end )
    {
        const bool l_less_than( i_end < i_begin );

        const t_RangeType & l_begin = ! l_less_than ? i_begin : i_end;
        const t_RangeType & l_end = l_less_than ? i_begin : i_end;

        // deal with an empty map here
        if ( m_map.empty() )
        {
            // shorthand adding the first element into the map
            m_map[ l_end ] = l_begin;
            return;
        }

        // see if there is a segment to merge - find the element that preceeds
        // l_begin

        t_Iterator l_begin_bound = m_map.lower_bound( l_begin );

        if ( l_begin_bound == m_map.end() )
        {
            // l_begin is after the last element

            -- l_begin_bound;

            if ( t_RangeTraits::Adjacent( l_begin_bound->first, l_begin ) )
            {

                // yes, they are mergable
                t_RangeType l_temp = l_begin_bound->second;
                m_map.erase( l_begin_bound );
                m_map[ l_end ] = l_temp;

                return;
            }

            // not mergable - add the segment at the end

            m_map[ l_end ] = l_begin;
            return;
        }

        // if the end of the segment being inserted is not beyond this one
        if ( ( l_end < l_begin_bound->second ) && ! t_RangeTraits::Adjacent( l_end, l_begin_bound->second ) )
        {
            // NOT mergable with subsequent segments

            if ( l_begin_bound == m_map.begin() )
            {
                // There is no previous segment

                m_map[ l_end ] = l_begin;
                return;
            }

            // The segment being inserted can't be merged at the end

            // see if it can be merged with the previous one

            t_Iterator l_previous = l_begin_bound;
            -- l_previous;

            AT_Assert( l_previous->first < l_begin );

            if ( ! t_RangeTraits::Adjacent( l_previous->first, l_begin ) )
            {
                // not overlapping with previous and not mergable

                m_map[ l_end ] = l_begin;
                return;
            }
            else
            {
                // we are mergable with the previous element

                // yes, they are mergable
                t_RangeType l_temp = l_previous->second;
                m_map.erase( l_previous );
                m_map[ l_end ] = l_temp;
                return;
            }

        }

        if ( l_begin_bound == m_map.begin() )
        {
            if ( l_end < l_begin_bound->first )
            {
                if ( l_end < l_begin_bound->second )
                {
                    if ( t_RangeTraits::Adjacent( l_end, l_begin_bound->second ) )
                    {
                        l_begin_bound->second = l_begin;
                        return;
                    }
                    else
                    {
                        m_map[ l_end ] = l_begin;
                        return;
                    }
                }
                else
                {
                    if ( l_begin < l_begin_bound->second )
                    {
                        l_begin_bound->second = l_begin;
                    }
                    return;
                }
            }
            else
            {

                t_RangeType l_new_begin = l_begin;

                if ( l_begin_bound->second < l_begin )
                {
                    l_new_begin = l_begin_bound->second;
                }

                // Check to see what segment is close to the end
                t_Iterator l_end_bound = m_map.lower_bound( l_end );

                if ( l_end_bound == m_map.end() )
                {
                    // erase all the segments from l_previous to the end and
                    // replace with one

                    m_map.erase( l_begin_bound, l_end_bound );

                    m_map[ l_end ] = l_new_begin;
                    return;
                }

                if ( l_end < l_end_bound->second && ! t_RangeTraits::Adjacent( l_end, l_end_bound->second ) )
                {
                    m_map.erase( l_begin_bound, l_end_bound );
                    m_map[ l_end ] = l_new_begin;
                    return;
                }

                // merge with the current end

                m_map.erase( l_begin_bound, l_end_bound ); // erase segments in between
                l_end_bound->second = l_new_begin;
                return;
            }
        }

        if ( l_begin_bound == m_map.begin() )
        {
            // no previous ranges

            // see if we can merge with the current range

        }

        // find the previous iterator
        t_Iterator l_previous = l_begin_bound;
        -- l_previous;

        t_RangeType l_new_begin = l_begin;

        if ( t_RangeTraits::Adjacent( l_previous->first, l_begin ) )
        {
            l_new_begin = l_previous->second;
        }
        else
        {
            ++ l_previous;

            if ( l_previous->second < l_new_begin )
            {
                l_new_begin = l_previous->second;
            }
        }

        t_RangeType l_new_end = l_end;

        // Check to see what segment is close to the end
        t_Iterator l_end_bound = m_map.lower_bound( l_end );

        if ( l_end_bound == m_map.end() )
        {
            // erase all the segments from l_previous to the end and
            // replace with one

            m_map.erase( l_previous, l_end_bound );

            m_map[ l_end ] = l_new_begin;
            return;
        }

        if ( l_end < l_end_bound->second && ! t_RangeTraits::Adjacent( l_end, l_end_bound->second ) )
        {
            m_map.erase( l_previous, l_end_bound );
            m_map[ l_end ] = l_new_begin;
            return;
        }

        // merge with the current end

        m_map.erase( l_previous, l_end_bound ); // erase segments in between
        l_end_bound->second = l_new_begin;

        return;
    }

    // ======== SubtractRange =========================================
    /**
     * SubtractRange removes the range. (opposite of Add)
     *
     *
     * @param i_begin Beginning of range to subtract
     * @param i_end End of range to subtract
     * @return nothing
     */

    void SubtractRange( const t_RangeType & i_begin, const t_RangeType & i_end )
    {
        const bool l_less_than( i_end < i_begin );

        const t_RangeType & l_begin = ! l_less_than ? i_begin : i_end;
        const t_RangeType & l_end = l_less_than ? i_begin : i_end;

        // deal with an empty map here
        if ( m_map.empty() )
        {
            // Nothing to remove
            return;
        }

        // See if we find a segment
        // l_begin

        t_Iterator l_begin_bound = m_map.lower_bound( l_begin );

        if ( l_begin_bound == m_map.end() )
        {
            // this does not cover any segments
            return;
        }

        if ( l_begin_bound->second < l_begin )
        {
            // this segment is broken up

            t_RangeType l_newend = l_begin;

            -- l_newend;

            m_map[ l_newend ] = l_begin_bound->second;

            l_begin_bound->second = l_begin;
        }

        t_Iterator l_end_bound = m_map.lower_bound( l_end );

        if ( l_end_bound == m_map.end() )
        {
            // erase all the segments from the beginning to end
            m_map.erase( l_begin_bound, l_end_bound );
            return;
        }

        if ( !( l_end < l_end_bound->first ) )
        {
            // the segment end must be equal the segment given

            ++ l_end_bound;

            m_map.erase( l_begin_bound, l_end_bound );
            return;
        }

        // need to break up the final segment

        m_map.erase( l_begin_bound, l_end_bound );

        if ( !( l_end < l_end_bound->second ) )
        {
            t_RangeType l_newbegin = l_end;

            ++ l_newbegin;

            l_end_bound->second = l_newbegin;
        }

        return;

    }

    // ======== IsSet =================================================
    /**
     * Checks to see if the position is set
     *
     * @param i_pos
     * @return True if the position is set
     */

    bool IsSet( const t_RangeType & i_pos )
    {
        t_Iterator l_bound = m_map.lower_bound( i_pos );

        if ( l_bound == m_map.end() )
        {
            // this does not cover any segments
            return false;
        }

        return !( i_pos < l_bound->second );
    }

    t_Map m_map;

};

}; // namespace

#endif // x_at_rangemap_h_x

--------------050703020605020002080605
Content-Type: text/plain;
 name="tst_rangemap.cpp"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="tst_rangemap.cpp"

#include "at_rangemap.h"

#include "at_unit_test.h"

#include <iostream>
#include <vector>
#include <cstdlib>

using namespace at;

namespace RangemapTest {

//

// ======== TestBitMap ================================================
/**
 * TestBitMap is like a range map but the logic is far easier.
 *
 */

template <typename w_RangeType, typename w_RangeTraits=TypeRange<w_RangeType> >
class TestBitMap
{
    public:

    // range type
    typedef w_RangeType t_RangeType;
    typedef w_RangeTraits t_RangeTraits;

    // ======== AddRange ==============================================
    /**
     * Add a segment to the range.
     *
     * @param i_begin The beginning of the range (inclusive)
     * @param i_end The end of the range (inclusive)
     * @return nothing
     */

    void AddRange( const t_RangeType & i_begin, const t_RangeType & i_end )
    {
        const bool l_less_than( i_end < i_begin );

        const t_RangeType & l_begin = ! l_less_than ? i_begin : i_end;
        const t_RangeType & l_end = l_less_than ? i_begin : i_end;

        CheckSize( l_end );

        for ( unsigned i = l_begin; i <= l_end; ++i )
        {
            m_bitmap[ i ] = true;
        }
    }

    // ======== SubtractRange =========================================
    /**
     * SubtractRange removes the range. (opposite of Add)
     *
     *
     * @param i_begin Beginning of range to subtract
     * @param i_end End of range to subtract
     * @return nothing
     */

    void SubtractRange( const t_RangeType & i_begin, const t_RangeType & i_end )
    {
        const bool l_less_than( i_end < i_begin );

        const t_RangeType & l_begin = ! l_less_than ? i_begin : i_end;
        const t_RangeType & l_end = l_less_than ? i_begin : i_end;

        CheckSize( l_end );

        for ( unsigned i = l_begin; i <= l_end; ++i )
        {
            m_bitmap[ i ] = false;
        }

    }

    // ======== IsSet =================================================
    /**
     * Checks to see if the position is set
     *
     * @param i_pos
     * @return True if the position is set
     */

    bool IsSet( const t_RangeType & i_pos )
    {
        if ( m_bitmap.size() < std::size_t( i_pos ) )
        {
            return false;
        }
        return m_bitmap[ i_pos ];
    }

    void CheckSize( const t_RangeType & i_end )
    {
        if ( m_bitmap.size() < std::size_t(i_end + 1) )
        {
            m_bitmap.resize( i_end + 1 );
        }
    }

    std::vector<bool> m_bitmap;
};

// ======== TestBoth ==================================================
/**
 *
 *
 */

template <typename w_RangeType, typename w_RangeTraits=TypeRange<w_RangeType> >
class TestBoth
{
    public:
    // range type
    typedef w_RangeType t_RangeType;
    typedef w_RangeTraits t_RangeTraits;

    // ======== AddRange ==============================================
    /**
     * Add a segment to the range.
     *
     * @param i_begin The beginning of the range (inclusive)
     * @param i_end The end of the range (inclusive)
     * @return nothing
     */

    void AddRange( const t_RangeType & i_begin, const t_RangeType & i_end )
    {
        m_rangemap_pre = m_rangemap;
        m_rangemap.AddRange( i_begin, i_end );
        m_bitmap.AddRange( i_begin, i_end );

        Verify( "Add", i_begin, i_end );
    }

    // ======== SubtractRange =========================================
    /**
     * SubtractRange removes the range. (opposite of Add)
     *
     *
     * @param i_begin Beginning of range to subtract
     * @param i_end End of range to subtract
     * @return nothing
     */

    void SubtractRange( const t_RangeType & i_begin, const t_RangeType & i_end )
    {
        m_rangemap_pre = m_rangemap;
        m_rangemap.SubtractRange( i_begin, i_end );
        m_bitmap.SubtractRange( i_begin, i_end );

        Verify( "Sub", i_begin, i_end );
    }

    void Verify( const char * i_op, const t_RangeType & i_begin, const t_RangeType & i_end )
    {
        unsigned l_elems = m_bitmap.m_bitmap.size();

        typename at::RangeMap< w_RangeType, w_RangeTraits >::t_Iterator l_bound;
        typename at::RangeMap< w_RangeType, w_RangeTraits >::t_Iterator l_previous;
        bool l_previous_set = false;

        for ( unsigned i = 0; i < (l_elems); ++ i )
        {
            l_bound = m_rangemap.m_map.lower_bound( i );

            bool l_rangemap_val = l_bound == m_rangemap.m_map.end() ? false : !( i < l_bound->second );
            bool l_bitmap_val = m_bitmap.IsSet(i);
            bool l_segment_fail = false;

            if ( l_previous_set )
            {
                if ( l_rangemap_val )
                {
                    l_segment_fail = l_previous != l_bound;
                }
            }
            else
            {
            }

            l_previous_set = l_rangemap_val;

            if ( l_rangemap_val && ! l_segment_fail )
            {
                l_previous = l_bound;
            }

            if ( ( l_rangemap_val != l_bitmap_val ) || l_segment_fail )
            {
                if ( l_segment_fail )
                {
                    std::cout << "Segments ( " << l_bound->second << ", " << l_bound->first << " ) and \n";
                    std::cout << " ( " << l_previous->second << ", " << l_previous->first << " ) and \n";
                }
                std::cout << "Operation = " << i_op << " i_begin = " << i_begin << " i_end = " << i_end << "\n";
                std::cout << "Pre operation ";
                DumpRanges( m_rangemap_pre.m_map );
                std::cout << "Post operation ";
                DumpRanges( m_rangemap.m_map );
                std::cout << "rangemap " << w_RangeType(i) << " - l_rangemap_val = " << l_rangemap_val << ", l_bitmap_val = " << l_bitmap_val << "\n";
            }

            AT_TCAssert( m_rangemap.IsSet(i) == m_bitmap.IsSet(i), "Bitmap differs" );
        }
    }

    void DumpRanges()
    {
        DumpRanges( m_rangemap.m_map );
    }

    void DumpRanges( typename at::RangeMap< w_RangeType, w_RangeTraits >::t_Map & l_map )
    {
        typename at::RangeMap< w_RangeType, w_RangeTraits >::t_Iterator l_iterator;

        for ( l_iterator = l_map.begin(); l_iterator != l_map.end(); ++ l_iterator )
        {
            std::cout << "( " << l_iterator->second << ", " << l_iterator->first << " )";
        }
        std::cout << "\n";
    }

    at::RangeMap< w_RangeType, w_RangeTraits > m_rangemap;
    at::RangeMap< w_RangeType, w_RangeTraits > m_rangemap_pre;
    TestBitMap< w_RangeType, w_RangeTraits > m_bitmap;
};

AT_TestArea( RangeMap, "Rangemap object tests" );

AT_DefineTest( RangeMap, RangeMap, "Basic RangeMap test" )
{

    void Run()
    {

        {
            TestBoth<unsigned char> l_rm;

            l_rm.AddRange( 'a','x' );

            l_rm.AddRange( 'A','X' );

            l_rm.AddRange( 'z','z' );

            l_rm.AddRange( 'Y','Z' );

            l_rm.DumpRanges();
        }
        {
            TestBoth<unsigned char> l_rm;

            l_rm.AddRange( '0','0' );

            l_rm.AddRange( 'a','a' );

            l_rm.AddRange( 'c','c' );

            l_rm.AddRange( 'h','h' );

            l_rm.AddRange( 'b','g' );

            l_rm.DumpRanges();
        }
        {
            TestBoth<unsigned char> l_rm;

            l_rm.AddRange( '0','0' );

            l_rm.AddRange( 'a','a' );

            l_rm.AddRange( 'c','c' );

            l_rm.AddRange( 'h','h' );

            l_rm.AddRange( 'b','i' );

            l_rm.DumpRanges();

            l_rm.AddRange( 'c','c' );

            l_rm.DumpRanges();

            l_rm.SubtractRange( 'b','b' );
            l_rm.SubtractRange( 'c','c' );
            l_rm.SubtractRange( 'd','d' );
            l_rm.SubtractRange( 'c','c' );

            l_rm.DumpRanges();
        }
        {
            TestBoth<unsigned char> l_rm;

            l_rm.AddRange( 'a','a' );

            l_rm.AddRange( 'c','c' );

            l_rm.AddRange( 'h','h' );

            l_rm.AddRange( 'b','i' );

            l_rm.AddRange( '0','0' );

            l_rm.SubtractRange( '0','0' );

            l_rm.AddRange( '0', 'i' );

            l_rm.SubtractRange( '0','i' );

            l_rm.AddRange( 'A','Z' );

            l_rm.SubtractRange( 'M','M' );

            l_rm.DumpRanges();
        }
    }

};

AT_RegisterTest( RangeMap, RangeMap );

AT_DefineTest( MonteRangeMap, RangeMap, "Basic RangeMap test" )
{

    void Run()
    {

        TestBoth<unsigned> l_rm;

        std::srand( 39000 );

        int range = 60;

        for ( int i = 0; i < 10000; ++i )
        {

            unsigned l_begin = std::rand() % range;
            unsigned l_end = std::rand() % range;

            bool operation = ( 2 & std::rand() ) == 0;

            if ( operation )
            {
                l_rm.SubtractRange( l_begin, l_end );
            }
            else
            {
                l_rm.AddRange( l_begin, l_end );
            }

        }
    }

};

AT_RegisterTest( MonteRangeMap, RangeMap );

} // RangeMap Test namespace

--------------050703020605020002080605--