[boost] String Algo bug.

From: John Maddock (john_at_[hidden])
Date: 2004-07-17 06:25:56

There seems to be a bug in the string algorithm library that results in a
valid container iterator being compared to a "singular" default constructed
iterator: this operation is not supported by the iterator requirements and
results in an assertion being thrown when testing with VC7.1+STLPort (or any
other compiler with STLPort for that matter).

The call stack is:

  stlport_vc71_stldebug46.dll!_STL::__stl_debug_engine<bool>::_Terminate()
Line 324 C++
  stlport_vc71_stldebug46.dll!_STL::__stl_debug_engine<bool>::_Assert(const
char * __expr=0x0057420c, const char * __f=0x00574180, int __l=0x0000012d)
Line 308 C++

regex_test.exe!_STL::operator==<_STL::_Nondebug_string<char,_STL::char_trait
s<char>,_STL::allocator<char> > >(const
_STL::_DBG_iter_base<_STL::_Nondebug_string<char,_STL::char_traits<char>,_ST
L::allocator<char> > > & __x={...}, const
_STL::_DBG_iter_base<_STL::_Nondebug_string<char,_STL::char_traits<char>,_ST
L::allocator<char> > > & __y={...})  Line 301 + 0x2e C++

regex_test.exe!boost::algorithm::iterator_range<_STL::_DBG_iter<_STL::_Nonde
bug_string<char,_STL::char_traits<char>,_STL::allocator<char>
>,_STL::_Const_traits<char> >
>::operator==<_STL::_DBG_iter<_STL::_Nondebug_string<char,_STL::char_traits<
char>,_STL::allocator<char> >,_STL::_Const_traits<char> > >()  Line 119 +
0x47 C++

regex_test.exe!boost::algorithm::find_iterator<_STL::_DBG_iter<_STL::_Nondeb
ug_string<char,_STL::char_traits<char>,_STL::allocator<char>
>,_STL::_Const_traits<char> > >::equal(const
boost::algorithm::find_iterator<_STL::_DBG_iter<_STL::_Nondebug_string<char,
_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Const_traits<char> >
> & Other={...})  Line 147 + 0x12 C++

regex_test.exe!boost::iterator_core_access::equal<boost::algorithm::find_ite
rator<_STL::_DBG_iter<_STL::_Nondebug_string<char,_STL::char_traits<char>,_S
TL::allocator<char> >,_STL::_Const_traits<char> >
>,boost::algorithm::find_iterator<_STL::_DBG_iter<_STL::_Nondebug_string<cha
r,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Const_traits<char>
> > >()  Line 518 C++

regex_test.exe!boost::operator==<boost::algorithm::find_iterator<_STL::_DBG_
iter<_STL::_Nondebug_string<char,_STL::char_traits<char>,_STL::allocator<cha
r> >,_STL::_Const_traits<char> >
>,boost::algorithm::iterator_range<_STL::_DBG_iter<_STL::_Nondebug_string<ch
ar,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Const_traits<char>
> > const
,boost::forward_traversal_tag,boost::algorithm::iterator_range<_STL::_DBG_it
er<_STL::_Nondebug_string<char,_STL::char_traits<char>,_STL::allocator<char>
>,_STL::_Const_traits<char> > > const
&,int,boost::algorithm::find_iterator<_STL::_DBG_iter<_STL::_Nondebug_string
<char,_STL::char_traits<char>,_STL::allocator<char>
>,_STL::_Const_traits<char> >
>,boost::algorithm::iterator_range<_STL::_DBG_iter<_STL::_Nondebug_string<ch
ar,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Const_traits<char>
> > const
,boost::forward_traversal_tag,boost::algorithm::iterator_range<_STL::_DBG_it
er<_STL::_Nondebug_string<char,_STL::char_traits<char>,_STL::allocator<char>
>,_STL::_Const_traits<char> > > const &,int>(const
boost::iterator_facade<boost::algorithm::find_iterator<_STL::_DBG_iter<_STL:
:_Nondebug_string<char,_STL::char_traits<char>,_STL::allocator<char>
>,_STL::_Const_traits<char> >
>,boost::algorithm::iterator_range<_STL::_DBG_iter<_STL::_Nondebug_string<ch
ar,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Const_traits<char>
> > const
,boost::forward_traversal_tag,boost::algorithm::iterator_range<_STL::_DBG_it
er<_STL::_Nondebug_string<char,_STL::char_traits<char>,_STL::allocator<char>
>,_STL::_Const_traits<char> > > const &,int> & lhs={...}, const
boost::iterator_facade<boost::algorithm::find_iterator<_STL::_DBG_iter<_STL:
:_Nondebug_string<char,_STL::char_traits<char>,_STL::allocator<char>
>,_STL::_Const_traits<char> >
>,boost::algorithm::iterator_range<_STL::_DBG_iter<_STL::_Nondebug_string<ch
ar,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Const_traits<char>
> > const
,boost::forward_traversal_tag,boost::algorithm::iterator_range<_STL::_DBG_it
er<_STL::_Nondebug_string<char,_STL::char_traits<char>,_STL::allocator<char>
>,_STL::_Const_traits<char> > > const &,int> & rhs={...})  Line 819 + 0x32
C++

regex_test.exe!boost::iterator_adaptor<boost::transform_iterator<boost::algo
rithm::detail::copy_iterator_rangeF<_STL::basic_string<char,_STL::char_trait
s<char>,_STL::allocator<char>
>,_STL::_DBG_iter<_STL::_Nondebug_string<char,_STL::char_traits<char>,_STL::
allocator<char> >,_STL::_Const_traits<char> >
>,boost::algorithm::find_iterator<_STL::_DBG_iter<_STL::_Nondebug_string<cha
r,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Const_traits<char>
>
>,boost::use_default,boost::use_default>,boost::algorithm::find_iterator<_ST
L::_DBG_iter<_STL::_Nondebug_string<char,_STL::char_traits<char>,_STL::alloc
ator<char> >,_STL::_Const_traits<char> >
>,_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char>
>,boost::use_default,_STL::basic_string<char,_STL::char_traits<char>,_STL::a
llocator<char>
>,boost::use_default>::equal<boost::transform_iterator<boost::algorithm::det
ail::copy_iterator_rangeF<_STL::basic_string<char,_STL::char_traits<char>,_S
TL::allocator<char>
>,_STL::_DBG_iter<_STL::_Nondebug_string<char,_STL::char_traits<char>,_STL::
allocator<char> >,_STL::_Const_traits<char> >
>,boost::algorithm::find_iterator<_STL::_DBG_iter<_STL::_Nondebug_string<cha
r,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Const_traits<char>
>
>,boost::use_default,boost::use_default>,boost::algorithm::find_iterator<_ST
L::_DBG_iter<_STL::_Nondebug_string<char,_STL::char_traits<char>,_STL::alloc
ator<char> >,_STL::_Const_traits<char> >
>,_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char>
>,boost::use_default,_STL::basic_string<char,_STL::char_traits<char>,_STL::a
llocator<char> >,boost::use_default>()  Line 297 + 0x12 C++

regex_test.exe!boost::iterator_core_access::equal<boost::transform_iterator<
boost::algorithm::detail::copy_iterator_rangeF<_STL::basic_string<char,_STL:
:char_traits<char>,_STL::allocator<char>
>,_STL::_DBG_iter<_STL::_Nondebug_string<char,_STL::char_traits<char>,_STL::
allocator<char> >,_STL::_Const_traits<char> >
>,boost::algorithm::find_iterator<_STL::_DBG_iter<_STL::_Nondebug_string<cha
r,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Const_traits<char>
>
>,boost::use_default,boost::use_default>,boost::transform_iterator<boost::al
gorithm::detail::copy_iterator_rangeF<_STL::basic_string<char,_STL::char_tra
its<char>,_STL::allocator<char>
>,_STL::_DBG_iter<_STL::_Nondebug_string<char,_STL::char_traits<char>,_STL::
allocator<char> >,_STL::_Const_traits<char> >
>,boost::algorithm::find_iterator<_STL::_DBG_iter<_STL::_Nondebug_string<cha
r,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Const_traits<char>
> >,boost::use_default,boost::use_default> >()  Line 518 C++

regex_test.exe!boost::operator!=<boost::transform_iterator<boost::algorithm:
:detail::copy_iterator_rangeF<_STL::basic_string<char,_STL::char_traits<char
>,_STL::allocator<char>
>,_STL::_DBG_iter<_STL::_Nondebug_string<char,_STL::char_traits<char>,_STL::
allocator<char> >,_STL::_Const_traits<char> >
>,boost::algorithm::find_iterator<_STL::_DBG_iter<_STL::_Nondebug_string<cha
r,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Const_traits<char>
>
>,boost::use_default,boost::use_default>,_STL::basic_string<char,_STL::char_
traits<char>,_STL::allocator<char>
>,boost::forward_traversal_tag,_STL::basic_string<char,_STL::char_traits<cha
r>,_STL::allocator<char>
>,int,boost::transform_iterator<boost::algorithm::detail::copy_iterator_rang
eF<_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char>
>,_STL::_DBG_iter<_STL::_Nondebug_string<char,_STL::char_traits<char>,_STL::
allocator<char> >,_STL::_Const_traits<char> >
>,boost::algorithm::find_iterator<_STL::_DBG_iter<_STL::_Nondebug_string<cha
r,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Const_traits<char>
>
>,boost::use_default,boost::use_default>,_STL::basic_string<char,_STL::char_
traits<char>,_STL::allocator<char>
>,boost::forward_traversal_tag,_STL::basic_string<char,_STL::char_traits<cha
r>,_STL::allocator<char> >,int>(const
boost::iterator_facade<boost::transform_iterator<boost::algorithm::detail::c
opy_iterator_rangeF<_STL::basic_string<char,_STL::char_traits<char>,_STL::al
locator<char>
>,_STL::_DBG_iter<_STL::_Nondebug_string<char,_STL::char_traits<char>,_STL::
allocator<char> >,_STL::_Const_traits<char> >
>,boost::algorithm::find_iterator<_STL::_DBG_iter<_STL::_Nondebug_string<cha
r,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Const_traits<char>
>
>,boost::use_default,boost::use_default>,_STL::basic_string<char,_STL::char_
traits<char>,_STL::allocator<char>
>,boost::forward_traversal_tag,_STL::basic_string<char,_STL::char_traits<cha
r>,_STL::allocator<char> >,int> & lhs={...}, const
boost::iterator_facade<boost::transform_iterator<boost::algorithm::detail::c
opy_iterator_rangeF<_STL::basic_string<char,_STL::char_traits<char>,_STL::al
locator<char>
>,_STL::_DBG_iter<_STL::_Nondebug_string<char,_STL::char_traits<char>,_STL::
allocator<char> >,_STL::_Const_traits<char> >
>,boost::algorithm::find_iterator<_STL::_DBG_iter<_STL::_Nondebug_string<cha
r,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Const_traits<char>
>
>,boost::use_default,boost::use_default>,_STL::basic_string<char,_STL::char_
traits<char>,_STL::allocator<char>
>,boost::forward_traversal_tag,_STL::basic_string<char,_STL::char_traits<cha
r>,_STL::allocator<char> >,int> & rhs={...})  Line 820 + 0x32 C++

regex_test.exe!_STL::__vector<_STL::basic_string<char,_STL::char_traits<char
>,_STL::allocator<char>
>,_STL::allocator<_STL::basic_string<char,_STL::char_traits<char>,_STL::allo
cator<char> > >
>::_M_range_initialize<boost::transform_iterator<boost::algorithm::detail::c
opy_iterator_rangeF<_STL::basic_string<char,_STL::char_traits<char>,_STL::al
locator<char>
>,_STL::_DBG_iter<_STL::_Nondebug_string<char,_STL::char_traits<char>,_STL::
allocator<char> >,_STL::_Const_traits<char> >
>,boost::algorithm::find_iterator<_STL::_DBG_iter<_STL::_Nondebug_string<cha
r,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Const_traits<char>
> >,boost::use_default,boost::use_default> >()  Line 535 + 0x17 C++

regex_test.exe!_STL::__vector<_STL::basic_string<char,_STL::char_traits<char
>,_STL::allocator<char>
>,_STL::allocator<_STL::basic_string<char,_STL::char_traits<char>,_STL::allo
cator<char> > >
>::_M_initialize_aux<boost::transform_iterator<boost::algorithm::detail::cop
y_iterator_rangeF<_STL::basic_string<char,_STL::char_traits<char>,_STL::allo
cator<char>
>,_STL::_DBG_iter<_STL::_Nondebug_string<char,_STL::char_traits<char>,_STL::
allocator<char> >,_STL::_Const_traits<char> >
>,boost::algorithm::find_iterator<_STL::_DBG_iter<_STL::_Nondebug_string<cha
r,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Const_traits<char>
> >,boost::use_default,boost::use_default> >()  Line 231 C++

regex_test.exe!_STL::__vector<_STL::basic_string<char,_STL::char_traits<char
>,_STL::allocator<char>
>,_STL::allocator<_STL::basic_string<char,_STL::char_traits<char>,_STL::allo
cator<char> > >
>::__vector<_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<
char>
>,_STL::allocator<_STL::basic_string<char,_STL::char_traits<char>,_STL::allo
cator<char> > >
><boost::transform_iterator<boost::algorithm::detail::copy_iterator_rangeF<_
STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char>
>,_STL::_DBG_iter<_STL::_Nondebug_string<char,_STL::char_traits<char>,_STL::
allocator<char> >,_STL::_Const_traits<char> >
>,boost::algorithm::find_iterator<_STL::_DBG_iter<_STL::_Nondebug_string<cha
r,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Const_traits<char>
> >,boost::use_default,boost::use_default> >()  Line 248 C++

regex_test.exe!_STL::vector<_STL::basic_string<char,_STL::char_traits<char>,
_STL::allocator<char>
>,_STL::allocator<_STL::basic_string<char,_STL::char_traits<char>,_STL::allo
cator<char> > >
>::vector<_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<ch
ar>
>,_STL::allocator<_STL::basic_string<char,_STL::char_traits<char>,_STL::allo
cator<char> > >
><boost::transform_iterator<boost::algorithm::detail::copy_iterator_rangeF<_
STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char>
>,_STL::_DBG_iter<_STL::_Nondebug_string<char,_STL::char_traits<char>,_STL::
allocator<char> >,_STL::_Const_traits<char> >
>,boost::algorithm::find_iterator<_STL::_DBG_iter<_STL::_Nondebug_string<cha
r,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Const_traits<char>
> >,boost::use_default,boost::use_default> >()  Line 164 + 0x93 C++

regex_test.exe!boost::algorithm::iter_find<_STL::vector<_STL::basic_string<c
har,_STL::char_traits<char>,_STL::allocator<char>
>,_STL::allocator<_STL::basic_string<char,_STL::char_traits<char>,_STL::allo
cator<char> > >
>,_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char> >
const
,boost::algorithm::detail::find_regexF<boost::reg_expression<char,boost::reg
ex_traits<char>,_STL::allocator<char> > >
>(_STL::vector<_STL::basic_string<char,_STL::char_traits<char>,_STL::allocat
or<char>
>,_STL::allocator<_STL::basic_string<char,_STL::char_traits<char>,_STL::allo
cator<char> > > > & Result={...}, const
_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char> > &
Input={...},
boost::algorithm::detail::find_regexF<boost::reg_expression<char,boost::rege
x_traits<char>,_STL::allocator<char> > > Finder={...})  Line 97 + 0x7e C++

regex_test.exe!boost::algorithm::find_all_regex<_STL::vector<_STL::basic_str
ing<char,_STL::char_traits<char>,_STL::allocator<char>
>,_STL::allocator<_STL::basic_string<char,_STL::char_traits<char>,_STL::allo
cator<char> > >
>,_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char>
>,char,boost::regex_traits<char>,_STL::allocator<char>
>(_STL::vector<_STL::basic_string<char,_STL::char_traits<char>,_STL::allocat
or<char>
>,_STL::allocator<_STL::basic_string<char,_STL::char_traits<char>,_STL::allo
cator<char> > > > & Result={...}, const
_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char> > &
Input={...}, const
boost::reg_expression<char,boost::regex_traits<char>,_STL::allocator<char> >
& Rx={...}, boost::regex_constants::_match_flags Flags=match_default)  Line
429 + 0x2b C++
  regex_test.exe!find_test()  Line 68 + 0x16 C++
  regex_test.exe!test_main(int __formal=0x00000001, int __formal=0x00000001)
Line 134 C++
  regex_test.exe!`anonymous namespace'::call_test_main()  Line 37 + 0x12 C++
  regex_test.exe!boost::unit_test::function_test_case::do_run()  Line 138 +
0x2b C++
  regex_test.exe!boost::unit_test::ut_detail::unit_test_monitor::function()
Line 77 + 0x14 C++
  regex_test.exe!boost::execution_monitor::run_function()  Line 188 + 0x54
C++
  regex_test.exe!boost::detail::catch_signals(boost::execution_monitor &
exmon={...}, bool __formal=true, bool __formal=true)  Line 472 C++
  regex_test.exe!boost::execution_monitor::execute(bool
catch_system_errors=true, int timeout=0x00000000)  Line 211 + 0x11 C++

regex_test.exe!boost::unit_test::ut_detail::unit_test_monitor::execute_and_t
ranslate(boost::unit_test::test_case * target_test_case=0x009c9990, void
(void)* f=0x0047d339, int timeout=0x00000000)  Line 43 + 0x13 C++
  regex_test.exe!boost::unit_test::test_case::run()  Line 145 + 0x6c C++
  regex_test.exe!main(int argc=0x00000001, char * * argv=0x009c6bb8)  Line
83 C++

And the actual problem I think is caused by (iter_find.hpp#98):

transform_iter_type itBegin=

make_transform_iterator(

find_iterator_type( begin(Input), InputEnd, Finder ),

copy_range_type());

transform_iter_type itEnd=

make_transform_iterator(

find_iterator_type(), // end iterator is default constructed here!!

copy_range_type());

SequenceSequenceT Tmp(itBegin, itEnd); // assertion here

There may be other occurances of course, this is just the first assertion to
be triggered...

John.