Re: [boost] [Review:Algorithms] - Review by Neil Groves

Subject: Re: [boost] [Review:Algorithms] - Review by Neil Groves
From: Marshall Clow (mclow.lists_at_[hidden])
Date: 2011-10-01 12:29:08

On Oct 1, 2011, at 8:20 AM, Neil Groves wrote:

> *Evaluation of the design.*
> 
> The design is pleasingly consistent with other algorithms with the exception
> of clamp_range. The clamp_range function copies, which is inconsitent with
> the other Boost string algorithms that have the _copy suffix. The
> clamp_range feature would be better designed as a clamped range adaptor.

The clamp_range functions were added, as a trial balloon, after the review started.
They're (technically) not part of the review.

That being said - thanks for the notes.

> *Evaluation of the implementation*
> 
> Generally, the algorithms would benefit from concept checking. In particular
> the iterator traversals, and range concept requirements should be checked.
> 
> The implementation of the functions in all.hpp and clamp.hpp are correctly
> implemented. The clamp function does not provide the usual guarantees about
> NaN values that most of the floating-point operations do. That is any one
> argument being NaN does not guarantee a NaN result. This is probably
> intended, if so a note should be made in the documentation.

I'll add notes to the documentation.

> The argument
> types may benefit from using call_traits to optimally chose between constant
> reference and value types.

> It might be worth considering an assertion that p(lo,hi) is true in the
> clamp function.

Good idea - added.

> The mixing of differing integer types makes the search algorithms defective.
> The int type is signed, and typically <= the size of std::size_t yet these
> are mixed. The skip table uses ints, but std::size_t values are inserted.
> Certainly there should not be any c style casts. It would seem logical to
> use the boost::iterator_difference<Iterator>::type instead. Currently these
> algorithms are defective albeit under unusual conditions.
> 
> There are numerous invocations of non-member functions that should use
> qualified calls to avoid accidental argument-dependent lookup.
> 
> range_const_iterator<Rng> has been deprecated in favour of
> range_iterator<const Rng>
> 
> The Range versions of the functions should provide a non-const reference
> version since there are no requirements for the interoperability of
> range_iterator<const Range> and range_iterator<Range> although they normally
> exist..

Captured as:
        https://github.com/mclow/Boost.Algorithm/issues/15	

> The tests have some defects with respect to dereferencing end iterators.

I believe that I have fixed all of these since the review started - but if you disagree, I'ld love to hear about it.

> As others have mentioned there should be range versions of all of the
> functions.

https://github.com/mclow/Boost.Algorithm/issues/11

> *Evaluation of the documentation*
> 
> The documentation should make very clear that the result for empty ranges
> into all_of, any_of, none_of as this is currently ambiguous. The
> documentation should provide more clear performance guarantees about the
> number of predicate evaluations where this is possible eg. any_of can and
> does early exit. The documentation should also provide the exception
> guarantees.

New issue:
        https://github.com/mclow/Boost.Algorithm/issues/16

> 
> *Evaluation of usefulness*
> 
> If corrected and properly documented these functions will be very useful.
> The functions any_of etc. are extremely useful for runtime assertions of
> pre- and post-conditions.
> 
> *Did I try to use the library?*
> 
> I used the library with GCC 4.6.1. I had no problems, although I did defect
> the defects noted above.
> 
> *How much effort did I put into my evaluation?*
> 
> I reviewed the code for a couple of hours which was sufficient for the small
> amount of code under review.
> 
> *Am I knowledgeable about the problem domain?*
> 
> Yes, I maintain Boost.Range hence my comments with respect to ranges are
> reasonably well informed. I have long been a fan of Design by Contract and
> hence I have experience using my own versions of the functions all_of etc.
> 
> 
> I vote for inclusion into Boost if and only if:
> 
> 1. the defects in the search functions and test are resolved
> 
> 2. clamp_range is removed or replaced.
> 

Thanks for the review!

-- Marshall

Marshall Clow     Idio Software   <mailto:mclow.lists_at_[hidden]>

A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait).
        -- Yu Suzuki