static void
test_erase ()
{
    rw_info (0, __FILE__, __LINE__, "21.3.5.5, p2");

    int thrown = 0;

    String s1 (s0);

    const String::const_pointer s1_data = s1.data ();
    const String::size_type     s1_size = s1.size ();
    const String::size_type     s1_cap  = s1.capacity ();

    try {
        // throws std::out_of_range if pos > size ()
        s1.erase (s1.size () + 1 /* , String::npos */);
    }
    catch (int id) {
        thrown = _RWSTD_ERROR_OUT_OF_RANGE == id;
    }
    catch (...) { /* empty */ }

    rw_assert (1 == thrown, __FILE__, __LINE__,
               "string::erase (size_type, size_type) "
               "failed to use __rw::__rw_throw()");

    // verify that string wasn't modified
    rw_assert (s1_data == s1.data () && s1_size == s1.size ()
               && s1_cap == s1.capacity (), __FILE__, __LINE__,
               "string::erase (size_type, size_type) modified *this");
}

void test_length (internT                                         /* dummy */,
                  int                                                line,
                  const std::mbstate_t                              *pstate,
                  const std::codecvt<internT, char, std::mbstate_t> &cvt,
                  const char                                        *from,
                  std::size_t                                        nchars,
                  int                                                maxi,
                  int                                                result)
{
    static const std::mbstate_t initial_state = std::mbstate_t ();

    const char* const tname = rw_any_t (internT ()).type_name ();

    std::mbstate_t state = pstate ? *pstate : initial_state;

    if (std::size_t (-1) == nchars)
        nchars = std::strlen (from);

    const int res = cvt.length (state, from, from + nchars, maxi);

    rw_assert (res == result, 0, line,
               "line %d: codecvt<%s, char, mbstate_t>::length("
               "state, from=%{*s}, from + %zu, %d) == %d, got %d",
               __LINE__, tname, sizeof *from, from, nchars, maxi, result, res);

    rw_assert (!pstate || 0 == std::memcmp (pstate, &state, sizeof state),
               0, line,
               "line %d: codecvt<%s, char, mbstate_t>::length("
               "state, from=%{*s}, from + %zu, %d) unexpected state",
               __LINE__, tname, from, nchars, maxi);
}

static void
test_copy ()
{
    rw_info (0, __FILE__, __LINE__, "21.3.5.7, p2");

    int thrown = 0;

    Char c = '\1';

    String s1 (s0);

    try {
        // throws std::out_of_range if pos > size ()
        s1.copy (&c, 1, s1.size () + 1);
    }
    catch (int id) {
        thrown = _RWSTD_ERROR_OUT_OF_RANGE == id;
    }
    catch (...) { /* empty */ }

    rw_assert (1 == thrown, __FILE__, __LINE__,
               "string::copy (pointer, size_type, size_type) "
               "failed to use __rw::__rw_throw()");

    // verify that destination buffer wasn't modified
    rw_assert ('\1' == c, __FILE__, __LINE__,
               "string::copy (pointer, size_type, size_type) "
               "modified buffer");
}

static void
test_replace2 ()
{
    rw_info (0, __FILE__, __LINE__, "21.3.5.6, p3 (pos2 > str.size ())");

    int thrown = 0;

    String s1 (s0);

    const String::const_pointer s1_data = s1.data ();
    const String::size_type     s1_size = s1.size ();
    const String::size_type     s1_cap  = s1.capacity ();

    try {
        // throws std::out_of_range if:
        // 1)    pos1 > size ()
        // 2) or pos2 > str.size ()   <-- testing
        s1.replace (s1.size (), 0, s1, s1.size () + 1, 0);
    }
    catch (int id) {
        thrown = _RWSTD_ERROR_OUT_OF_RANGE == id;
    }
    catch (...) { /* empty */ }

    rw_assert (1 == thrown, __FILE__, __LINE__,
               "string::replace (size_type, size_type, const string&, "
               "size_type, size_type) failed to use __rw::__rw_throw()");

    // verify that string wasn't modified
    rw_assert (s1_data == s1.data () && s1_size == s1.size ()
               && s1_cap == s1.capacity (), __FILE__, __LINE__,
               "string::replace (size_type, size_type, const string&, "
               "size_type, size_type) modified *this");
}

static void
test_max_size_ctor1 ()
{
    rw_info (0, __FILE__, __LINE__, "21.3.1, p7");

    // establish a chekpoint for memory leaks
    rwt_check_leaks (0, 0);

    int thrown = 0;

    try {
        // throws std::out_of_range if n > max_size () (*)
        // (*) see also lwg issue 83
        String s1 (s0.data (), s0.max_size () + 1);
    }
    catch (int id) {
        thrown = _RWSTD_ERROR_LENGTH_ERROR == id;
    }
    catch (...) { /* empty */ }

    std::size_t nbytes; /* uninitialized */
    std::size_t nblocks = rwt_check_leaks (&nbytes, 0);
    _RWSTD_UNUSED (nblocks);

    rw_assert (1 == thrown, __FILE__, __LINE__,
               "string::string (const char_type*, size_type) "
               "failed to use __rw::__rw_throw()");

    rw_assert (0 == nbytes, __FILE__, __LINE__,
               "string::string (const char_type*, size_type)"
               "leaked %u bytes", nbytes);

    rw_assert (s == s0, __FILE__, __LINE__,
               "original const string modified");
}

static int
run_test (int, char*[])
{
    const int new_0    = new_calls;
    const int delete_0 = delete_calls;

    do_test (char ());

    const int new_1    = new_calls - new_0;
    const int delete_1 = delete_calls - delete_0;

    // verify that test doesn't leak any dynamically allocated storage
    rw_assert (0 == new_1 - delete_1, 0, __LINE__,
               "test leaked %d blocks of memory", new_1 - delete_1);
    rw_assert (0 == init_new_calls, 0, __LINE__,
               "iostream initialization called operator new() %d times, "
               "0 expected", init_new_calls);

#ifdef _RWSTD_NO_REPLACEABLE_NEW_DELETE

    rw_warn (0, 0, __LINE__,
                "replacement operators new and delete not tested: "
                "_RWSTD_NO_REPLACEABLE_NEW_DELETE #defined");

#endif   // _RWSTD_NO_REPLACEABLE_NEW_DELETE

    return 0;
}

static void
test_reserve ()
{
    rw_info (0, __FILE__, __LINE__, "21.3.3, p12");

    int thrown = 0;

    String s1 (s0);

    const String::const_pointer s1_data = s1.data ();
    const String::size_type     s1_size = s1.size ();
    const String::size_type     s1_cap  = s1.capacity ();

    try {
        // throws std::length_error if n > max_size ()
        s1.reserve (s1.max_size () + 1U);
    }
    catch (int id) {
        thrown = _RWSTD_ERROR_LENGTH_ERROR == id;
    }
    catch (...) { /* empty */ }

    rw_assert (1 == thrown, __FILE__, __LINE__,
               "string::reserve (size_type)"
               "failed to use __rw::__rw_throw()");

    // verify that string wasn't modified
    rw_assert (s1_data == s1.data () && s1_size == s1.size ()
               && s1_cap == s1.capacity (), __FILE__, __LINE__,
               "string::reserve (size_type) modified *this");
}

static void
test_replace3 ()
{
    rw_info (0, __FILE__, __LINE__, "21.3.5.6, p5");

    int thrown = 0;

    String s1 (s0);

    const String::const_pointer s1_data = s1.data ();
    const String::size_type     s1_size = s1.size ();
    const String::size_type     s1_cap  = s1.capacity ();

    // establish a chekpoint for memory leaks
    rwt_check_leaks (0, 0);

    try {
        // make sure max_size() isn't too big
        assert (s1.max_size () == _RWSTD_NEW_CAPACITY (String, &s1, 0));

        thrown = -1;

        // must not throw
        String s2 (s1.max_size () - s1.size () + 2, Char ());

        thrown = 0;

        // throws std::length_error if:
        //               size () - xlen >= max_size () - rlen (*)
        // where xlen = min (n1, this->size () - pos1)
        // and   rlen = min (n2, str.size () - pos2)
        // (*) see also lwg issue 86
        s1.replace (0, 1, s2, 0, s2.size ());
    }
    catch (int id) {
        thrown = 0 == thrown && _RWSTD_ERROR_LENGTH_ERROR == id;
    }
    catch (...) { /* empty */ }

    std::size_t nbytes; /* uninitialized */
    std::size_t nblocks = rwt_check_leaks (&nbytes, 0);
    _RWSTD_UNUSED (nblocks);

    rw_assert (1 == thrown, __FILE__, __LINE__,
               "string::replace (size_type, size_type, const string&, "
               "size_type, size_type) failed to use __rw::__rw_throw()");

    // verify that string wasn't modified
    rw_assert (s1_data == s1.data () && s1_size == s1.size ()
               && s1_cap == s1.capacity (), __FILE__, __LINE__,
               "string::replace (size_type, size_type, const string&, "
               "size_type, size_type) modified *this");

    // tests not only replace() but also string ctor (s2 above)
    rw_assert (1 == thrown, __FILE__, __LINE__,
               "string::replace (size_type, size_type, const string&, "
               "size_type, size_type) leaked %u bytes", nbytes);
}

static void
test_1 ()
{
    UserClass *x = UserClass::from_char ("abcdef");
    UserClass *y = UserClass::from_char ("ABCDEF");

    const Iterator end = make_iter (x + 6, x + 0, x + 6, end);
    Iterator it  = make_iter (x + 0, x + 0, x + 6, it);

    bool equal;

    // non-end iterator must compare unequal to the end iterator
    PASS (equal = it == end);

    rw_assert (!equal, 0, __LINE__,
               "InputIter<UserClass> unexpectedly equal to end: "
               "%p == %p", it.cur_, end.cur_);

    PASS (y [0] = *it);
    PASS (++it);
    PASS (equal = it == end);

    rw_assert (!equal, 0, __LINE__,
               "InputIter<UserClass> unexpectedly equal to end: "
               "%p == %p", it.cur_, end.cur_);

    PASS (y [1] = *it);
    PASS (++it);

    PASS (equal = it == it);

    rw_assert (equal, 0, __LINE__,
               "InputIter<UserClass> unexpectedly equal to self: "
               "%p == %p", it.cur_, it.cur_);

    PASS (y [2] = *it);
    PASS (++it);
    PASS (y [3] = *it);
    PASS (++it);
    PASS (y [4] = *it);
    PASS (++it);
    PASS (y [5] = *it);
    PASS (++it);

    PASS (equal = it == end);

    rw_assert (equal, 0, __LINE__,
               "InputIter<UserClass> unexpectedly not qual to end: "
               "%p != %p (diff = %d)",
               it.cur_, end.cur_, end.cur_ - it.cur_);

    rw_assert (0 == UserClass::compare (x, y, 6), 0, __LINE__,
               "InputIter<UserClass> data mismatch: %s != %s",
               X2STR (x, 6), X2STR (y, 6));

    delete[] x;
    delete[] y;
}

static void
test_0 ()
{
    UserClass *x = UserClass::from_char ("abc");

    Iterator end0 = make_iter (x + 3, x + 0, x + 3, end0);
    Iterator end1 = make_iter (x + 3, x + 0, x + 3, end1);

    bool equal;

    // end iterator must compare equal to itself
    PASS (equal = end0 == end0);

    rw_assert (equal, 0, __LINE__,
               "InputIter<UserClass> end iterator unexpectedly "
               "not equal to self: %p == %p", end0.cur_, end0.cur_);

    PASS (equal = end0 != end0);

    rw_assert (!equal, 0, __LINE__,
               "InputIter<UserClass> end iterator unexpectedly "
               "not equal to self: %p == %p", end0.cur_, end0.cur_);

    // end iterator must compare equal to another
    PASS (equal = end0 == end1);

    rw_assert (equal, 0, __LINE__,
               "InputIter<UserClass> end iterator unexpectedly "
               "not equal to another: %p == %p", end0.cur_, end1.cur_);

    PASS (equal = end0 != end1);

    rw_assert (!equal, 0, __LINE__,
               "InputIter<UserClass> end iterator unexpectedly "
               "not equal to another: %p == %p", end0.cur_, end1.cur_);

    // cannot increment the end iterator
    FAIL (++end0);
    FAIL (end0++);
    FAIL (++end1);
    FAIL (end1++);

    // cannot dereference the end iterator
    FAIL (x [0] = *end0);
    FAIL (x [0] = *end1);

    FAIL (equal = int ('a') == end0->data_.val_);
    FAIL (equal = int ('a') == end1->data_.val_);

    delete[] x;
}

static void
test_gslice (std::size_t  start,
             const char  *sizes,
             const char  *strides)
{
    const std::valarray<std::size_t> asizes (make_array (sizes));
    const std::valarray<std::size_t> astrides (make_array (strides));

    const std::gslice gsl (start, asizes, astrides);

    const std::valarray<std::size_t> indices = get_index_array (gsl);

    std::size_t maxinx = 0;

    for (std::size_t i = 0; i != indices.size (); ++i)
        if (maxinx < indices [i])
            maxinx = indices [i];

    std::valarray<std::size_t> va (maxinx + 1);
    for (std::size_t i = 0; i != va.size (); ++i)
        va [i] = i;

    for (int i = 0; i != 3; ++i) {
        // repeat each test three to verify that operator[](gslice)
        // doesn't change the observable state of its argument and
        // that the same result is obtained for a copy of gslice

        const std::valarray<std::size_t> array_slice =
            i < 2 ? va [gsl] : va [std::gslice (gsl)];

        bool equal = array_slice.size () == indices.size ();

        rw_assert (equal, 0, __LINE__,
                   "size() == %zu, got %zu\n",
                   indices.size (), array_slice.size ());

        if (equal) {
            for (std::size_t j = 0; j != array_slice.size (); ++j) {

                equal = array_slice [j] == va [indices [j]];

                rw_assert (equal, 0, __LINE__,
                           "mismatch at %u, index %u: expected %u, got %u\n",
                           j, indices [j], va [indices [j]],
                           array_slice [j]);
            }
        }
    }
}

void test_std_swap ()
{
    static bool tested = false;

    if (tested)
        return;

    tested = true;

    rw_info (0, 0, 0, 
             "Testing std::swap (std::list&, std::list&) "
             "calls std::list::swap");

    // verify the signature of the function specialization
    void (*pswap)(ListType&, ListType&) =
        &std::swap<ListValueType, ListAllocator>;

    _RWSTD_UNUSED (pswap);

    // verify that std::swap() calls std::list::swap()
    ListType lst;

    std::swap (lst, lst);

    rw_assert (1 == list_swap_called, 0, __LINE__,
               "std::swap (std::list<T, A>&, std::list<T, A>&) called "
               "std::list<T, A>::swap (std::list<T, A>&) exactly once; "
               "got %d times", list_swap_called);
}

static void
test_default_ctor ()
{
    rw_info (0, __FILE__, __LINE__, "default constructor");

    std::tuple<> et; _RWSTD_UNUSED (et);
    // TODO: enable this test after implementing empty space optimization
    //rw_assert (sizeof (et) == 0, __FILE__, __LINE__,
                 //"sizeof (std::tuple<>); got %u, expected 0",
                 //sizeof (et));

    std::tuple<int> it; _RWSTD_UNUSED (it);
    std::tuple<const int> ct; _RWSTD_UNUSED (ct);
    // ill-formed for tuples with element types containing references
    std::tuple<long, const char*> pt; _RWSTD_UNUSED (pt);
    std::tuple<std::tuple<int> > nt; _RWSTD_UNUSED (nt);
    std::tuple<bool, char, int, double, void*, UserDefined> bt;
    _RWSTD_UNUSED (bt);

    UserDefined::reset ();
    std::tuple<UserDefined> ut; _RWSTD_UNUSED (ut);
    rw_assert (1 == UserDefined::actual.dflt_ctor, __FILE__, __LINE__,
               "std::tuple<UserDefined> ut; called %d default ctors, "
               "expected 1", UserDefined::actual.dflt_ctor);
}

void test_trait (int line, bool value, bool expect,
                 const char* trait, const char* typeT, const char* typeU)
{
    rw_assert (value == expect, 0, line,
               "%s<%s, %s>::type is%{?}n't%{;} %b as expected",
               trait, typeT, typeU, value != expect, expect);
}

static void
test_tie ()
{
    rw_info (0, __FILE__, __LINE__, "tie");

    int i = 0; double d = 0.0; const char* s = 0;
    std::tie (i, std::ignore, s)
        = std::make_tuple (256, 3.14159, "string");

    rw_assert (i == 256, __FILE__, __LINE__,
               "i == 256, got false, expected true");
    rw_assert (d == 0.0, __FILE__, __LINE__,
               "d == 0.0, got false, expected true");
    rw_assert (0 == std::strcmp (s, "string"), __FILE__, __LINE__,
               "s == \"string\", got false, expected true");
}

void test_ops (const TempParams<T, CharT, Traits, Dist> &params,
               int                                       line,
               const char                               *input,
               T                                         expect,
               bool                                      is_eos,
               int                                       state)
{
    typedef std::istream_iterator<T, CharT, Traits, Dist> Iterator;
    typedef std::basic_stringstream<CharT, Traits>        StringStream;

    fmtnam (params.names);

    StringStream strm;

    typedef std::istreambuf_iterator<CharT, Traits> StreambufIterator;
    typedef std::num_get<CharT, StreambufIterator>  NumGet;

    if (false == std::has_facet<NumGet>(strm.getloc ())) {
        const std::locale loc (std::locale::classic (), new NumGet);
        strm.imbue (loc);
    }

    if (input && *input)
        strm << input;

    const Iterator eos;

    const Iterator it (strm);

    rw_assert (is_eos ^ (it != eos), 0, line,
               "line %d: %{$ITER}::operator() != %{$ITER}()", __LINE__);

    if (0 == (strm.rdstate () & (strm.badbit | strm.failbit))) {
        // operator*() is defined only for non-eos iterators
        // avoid calling it on a bad or failed stream too

        const T val = *it;

        rw_assert (val == expect, 0, line,
                   "line %d: %{$ITER}::operator*() == %{@}, got %{@}",
                   __LINE__, params.names.tfmt, expect, params.names.tfmt, val);
    }

    rw_assert (strm.rdstate () == state, 0, line,
               "line %d: %{$ITER}::operator*(), rdstate() == %{Is}, got %{Is}",
               __LINE__, state, strm.rdstate ());
}

static void
test_size_ctor ()
{
    rw_info (0, __FILE__, __LINE__, "21.3.1, p4 (size)");

    // establish a chekpoint for memory leaks
    rwt_check_leaks (0, 0);

    int thrown = 0;

    try {
        // throws std::out_of_range if pos > str.size ()
        String s1 (s0, s0.size () + 1);
    }
#ifndef _RWSTD_NO_EXCEPTIONS

    catch (std::out_of_range&) {
        thrown = 1;
    }

#else   // if defined (_RWSTD_NO_EXCEPTIONS)

    catch (int id) {
        thrown = id == _RWSTD_ERROR_OUT_OF_RANGE;
    }

#endif   // _RWSTD_NO_EXCEPTIONS

    catch (...) {
        thrown = -1;
    }

    std::size_t nbytes; /* uninitialized */
    std::size_t nblocks = rwt_check_leaks (&nbytes, 0);
    _RWSTD_UNUSED (nblocks);

    rw_assert (1 == thrown, __FILE__, __LINE__,
               ("string::string (const string&, size_type, size_type, "
                "const allocator_type&) failed to throw std::out_of_range"));

    rw_assert (s == s0, __FILE__, __LINE__,
               "original const string modified");

    rw_assert (0 == nbytes, __FILE__, __LINE__,
               "string::string (const string&, size_type, size_type, "
               "const allocator_type&) leaked %u bytes", nbytes);
}

static void vm_map_remove_entry(vm_map_t *vm_map, vm_map_entry_t *entry) {
  rw_assert(&vm_map->rwlock, RW_WLOCKED);
  vm_map->nentries--;
  if (entry->object)
    vm_object_free(entry->object);
  TAILQ_REMOVE(&vm_map->list, entry, map_list);
  kfree(M_VMMAP, entry);
}

void test_swap (const T*, const char* tname)
{
    rw_info (0, 0, 0, 
             "std::deque<%s>::swap(deque<%1$s>&)", tname);

    typedef std::deque<T, std::allocator<T> > MyDeque;
    typedef typename MyDeque::iterator        Iterator;

    // create two empty deque objects
    MyDeque empty [2];

    // save their begin and end iterators before calling swap
    const Iterator before [2][2] = {
        { empty [0].begin (), empty [0].end () },
        { empty [1].begin (), empty [1].end () }
    };

    // swap the two containers
    empty [0].swap (empty [1]);

    // get the new begin and end iterators
    const Iterator after [2][2] = {
        { empty [0].begin (), empty [0].end () },
        { empty [1].begin (), empty [1].end () }
    };

    // verify that the iterators have not been invalidated
    rw_assert (   before [0][0] == after [1][0] 
               && before [1][0] == after [0][0], 0, __LINE__, 
               "deque<%s>().begin() not swapped", tname);
    
    rw_assert (   before [0][1] == after [1][1] 
               && before [1][1] == after [0][1], 0, __LINE__, 
               "deque<%s>().end() not swapped", tname);

    // static to zero-initialize if T is a POD type
    static T seq [32];

    const std::size_t seq_len = sizeof seq / sizeof *seq;

    for (std::size_t i = 0; i != seq_len; ++i) {
        for (std::size_t j = 0; j != seq_len; ++j) {
            test_swap (seq, i, seq, j, (MyDeque*)0, tname);
        }
    }
}

void assert (int line, unsigned index, const char* tuple_name,
             const T& t, const U& u)
{
    const char* fmtT = FMT_SPEC (T);
    const char* fmtU = FMT_SPEC (U);
    rw_assert (equal (t, u), __FILE__, line,
               "get<%d, %s> (); got %{@}, expected %{@}",
               index, tuple_name, fmtT, t, fmtU, u);
}