[Boost-users] Boost.Spirit bug report [Was: Bug report on Boost 1.32 lib]

From: Aleksey Gurtovoy (agurtovoy_at_[hidden])
Date: 2005-07-15 15:27:42

Ulzii Luvsanbat <batul_at_[hidden]> writes:
> Hi Aleksey,

Hi Ulzii,

>
> I got this email address from boost.org, if you're not the right person
> please forward this to the appropriate folks.  

The most appropriate place for bug reports would be either of our two
main mailing lists (http://www.boost.org/more/mailing_lists.htm), to
one of which I'm cc-ing. Please see http://www.boost.org/more/bugs.htm
for the more details on the Boost bug reporting policy.

> We believe we ran into a
> bug in Boost 1.32 library.  Here are the details:
>
> Basically boost_1_32_0\libs\spirit\test\bug_fixes.cpp test is failing
> for us with Visual C++ Compiler.
>
> In range_run.ipp file:
>
>         template <typename CharT>
>         inline bool
>         range_run<CharT>::test(CharT v) const
>         {
>             if (!run.empty())
>             {
>                 const_iterator iter =
>                     std::lower_bound(
>                         run.begin(), run.end(), v,
>                         range_char_compare<CharT>()
>                     );
>
>                 if (iter != run.end() && iter->includes(v))
>                     return true;
>
>                 if (iter != run.begin())
>                     return (--iter)->includes(v);
>             }
>
>             return false;
>
>         }
>
> but range_char_compare::operator() in
> boost\spirit\utility\impl\chset\range_run.hpp does not accept the same
> types as arguments:
>
>             template <typename CharT>
>             struct range_char_compare {
>
>                 bool operator()(range<CharT> const& x, const CharT y) const
>                 { return x.first < y; }
>
>                 bool operator()(const CharT x, range<CharT> const& y) const
>                 { return x < y.first; }
>             };
>
>         Now, in our lower_bound implementation (in Debug) we
> assume/enforce that Predicate is a valid ordering on the (First, Last)
> interval.
>
>         The C++ Standard says:
>
>         25.3.3 Binary search [lib.alg.binary.search]
>
>         1 All of the algorithms in this section are versions of
> binary search and assume that the sequence being searched is in
> order according to the implied or explicit comparison function.
>
>         The explicit comparison function provided to lower_bound in the
> repro case cannot be applied on the sequence being searched. Thus, we
> cannot check the assumption of 25.3.3.1.
>
> The test passes if we add one more overload in range_char_compare,
> something like:
>
>             template <typename CharT>
>             struct range_char_compare {
>                 bool operator()(range<CharT> const& x, const CharT y) const
>                 { return x.first < y; }
>
>                 bool operator()(const CharT x, range<CharT> const& y) const
>                 { return x < y.first; }
>
>                 bool operator()(range<CharT> const& x, range<CharT> const& y) const
>                 { return x.first < y.first; }
>
>             };
>
> Can you please confirm this?

I believe
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2001/n1313.html
covers this exact issue in detail.

HTH,
-- 
Aleksey Gurtovoy
MetaCommunications Engineering