test for lib.alg.find

[Anton Pevtsov <an...@moscow.vdiweb.com>]

The attached file contains my attempt to update this test and port it to
new test driver.

I changed the test sequences used to exercise find and find_if.
Now they are created from the character strings like in the test for
lib.alg.adjacent.find (not automatically generated):
http://svn.apache.org/repos/asf/incubator/stdcxx/trunk/tests/algorithms/25.adjacent.find.cpp


With best wishes,
Anton Pevtsov

Re: test for lib.alg.find

[Martin Sebor <se...@roguewave.com>]

Anton Pevtsov wrote:
> The attached file contains my attempt to update this test and port it to
> new test driver.
> 
> I changed the test sequences used to exercise find and find_if.
> Now they are created from the character strings like in the test for
> lib.alg.adjacent.find (not automatically generated):
> http://svn.apache.org/repos/asf/incubator/stdcxx/trunk/tests/algorithms/25.adjacent.find.cpp 

Okay, that's a good start, thanks!

There are a few issues with the test. I corrected them and committed
the result here: http://svn.apache.org/viewcvs.cgi?rev=351871&view=rev
Please take a look to see what I did to simplify the logic. I point out
a few of the problems below:

[...]
> template <class T>
> struct ConstFindIfPredicate  : FindIfPredicateBase

I don't think there is any need for a cost and non-const predicates
in this test. According to 25, p7 "the [Predicate] function object
shall not apply any non-constant function through the dereferenced
iterator."

> {
>     ConstFindIfPredicate(T& tofind) : 
>         FindIfPredicateBase(true), tofind_(tofind) {}
> 
>     int operator() (T obj)

According to 25, p7 again, "if an algorithm takes Predicate pred
as its argument and first as its iterator argument, it should work
correctly in the construct if (pred(*first)){...}." This is pretty
loosely worded but what it means is that the Predicate need not
return bool but rather any type implicitly convertible to bool.
A strict test would try to detect assumptions made by the
algorithm about the return type being bool. I changed the function
call operator to return an object of a user-defined type that is
implicitly convertible to bool.

[...]
>     // construct T to be found
>     T* temp_t = 0;
>     if (nsrc)
>         temp_t = new T (tsrc[findoff]);
>     else // the sequence is empty, search any dummy value
>         temp_t = new T(); 

Here, there's no need to construct the object dynamically, or to
create a copy of the sought object. I avoided it by creating
a reference to the object (or a reference to an unnamed temporary
if no such object exists).

An enhancement to the test would be to exercise the algorithm with
type T that's different from iterator_traits<Iterator>::value_type,
e.g., std::find<InputIter<X>, Y>() where Y is distinct from X but
the two are EqualityComparable.

A similar enhancement could (and should) be made the predicate form
of the algorithm, e.g., std::find<InputIter<X>, Predicate<Y> >().

> 
[...]
>     if (res.cur_ != last.cur_)
>     {
>         success = res->val_ == temp_t->val_;
>         rw_assert (success, 0, line, 

This test is redundant. If the returned iterator points to the
expected element dereferencing the iterator must yield the value
of the element.

[...]
> 
>     // verify 25.1.5 p2
>     success = T::n_total_op_assign_ - last_n_op_assign <= nsrc - startoff;

This test can be tightened up -- while it appears to be allowed
by the standard it wouldn't make sense for the algorithm to apply
the predicate that many times unless the sought element didn't
exist.

>     rw_assert (success, 0, line, 
[...]
> // exercises std::find_if()
> template <class InputIterator, class Function, class T>
> void do_test_find_if (int         line,     // line number of test case

The body of this function can be trivially combined with the one
above.

[...]
> /**************************************************************************/
> 
> template <class InputIterator, class T>
> void run_find_tests (InputIterator dummy_iter, const T*)
> {   
>     static const char* const itname = type_name (dummy_iter, (T*)0);
>     static const char* const tname = "X";
> 
>     rw_info (0, 0, 0, "std::find (%s, %1$s, %s)", itname, tname);
> 
> #define TEST(src, off_start, off_find, off_res) \
>     do_test_find (__LINE__, src, std::size_t (off_start), \
>                   std::size_t (off_find), std::size_t (off_res), \
>                   dummy_iter, (X*)0)
>     
>     //    +------------------ subject sequence
>     //    |               +--- offset of the start iterator
>     //    |               |   +--- offset of the element to find
>     //    |               |   |   +-- offset of returned iterator,
>     //    |               |   |   |   -1 denotes the end of sequence
>     //    v               v   v   v
>     TEST ("a",            0,  0,  0);

We don't need to pass the offset of the start iterator (it's always
0, or there is no reason for it not to be). We also don't need to
pass the offset of the result; we can combine it with the offset
of the element to find.

[...]
> template <class InputIterator, class Function, class T> 
> void run_find_if_tests (InputIterator dummy_iter, Function* dummy_f, const T*)
> {   

This function is the same as the one above and can be eliminated.

[...]
> static 
> void test_find ()
> {
>     rw_info (0, 0, 0, 
>              "template <class %s> "
>              "%1$s std::find (%1$s, %1$s, const T& )",
>              "InputIterator");
> 
>     if (rw_opt_no_input_iter) {
>         rw_note (0, __FILE__, __LINE__, "InputIterator test disabled");
>     }
>     else {
>         run_find_tests (InputIter<X>((X*)0, (X*)0, (X*)0), (X*)0);
>     }
> 
>     if (rw_opt_no_fwd_iter) {
>         rw_note (0, __FILE__, __LINE__, "ForwardIterator test disabled");
>     }
>     else {
>         run_find_tests (FwdIter<X>(), (X*)0);

Here we should also exercise ConstFwdIter and other const iterators.

[...]
> static 
> void test_find_if ()
> {

Again, this can be integrated with the function above.

[...]
> 
> int main (int argc, char *argv[])
> {
>     return rw_test (argc, argv, __FILE__,
>                     "lib.alg.find",
>                     0 /* no comment */, run_test,
>                     "|-no-InputIterator#"
>                     "|-no-ForwardIterator#"
>                     "|-no-BidirectionalIterator#"
>                     "|-no-RandomAccessIterator#"
>                     "|-no-Predicate",
                        ^^^^^^^^^^^^^^

Careful here! Without the '#' sign the option expects a function
pointer as an argument. When the option appears on the command
line the test driver attempts to invoke the function and crashes
(we should detect this and give an error but that's an enhancement
to __rw::__rw_memattr() waiting to be implemented...)

>                     &rw_opt_no_input_iter,
>                     &rw_opt_no_fwd_iter,
>                     &rw_opt_no_bidir_iter,
>                     &rw_opt_no_rnd_iter,
>                     &rw_opt_no_predicate);
> }

Make sure you exercise each test manually by specifying each of
the command line options. Also run the test with the --trace option
to make sure all the diagnostic messages are properly formatted and
make sense.

Martin