room for improvement in implementation of "std::advance(InputIterator)": make it more resilient to bugs in user-level code: in particular, negative distances

[Abe <abe149 at gmail dot com>]

Dear all,

I`m a long-time GCC user, but this is my first post to this mailing list.

To make a long story short, nowadays I have reason to be reading the
guts of GCC`s STL implementation.

In the file called "<include path for GCC`s
STL>/bits/stl_iterator_base_funcs.h" [version 4.7.2], I found this:

  template<typename _InputIterator, typename _Distance>
    inline void
    __advance(_InputIterator& __i, _Distance __n, input_iterator_tag)
    {
      // concept requirements
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
      while (__n--)
        ++__i;
    }


It seems to me the above has something that might be considered a bug:
it does not catch negative numbers passed in.  One way of dealing with
this would be to prefix the "while" with "if (__n>0)".  Without any
handling at all of this situation, code that mistakenly passes in e.g.
-1000 with an iterator that is not bidi. or random-access will run
that loop until either the integer comes all the way back around
[passing through all the negative #s of the type, starting at -1000]
and arrives at zero, or the program crashes [e.g. maybe "++__i" will
throw an exception when it goes out of bounds, depending on the
container].  Either way, backwards motion was requested, but is not
possible in this context.  IMO either ignoring the request or throwing
an exception are better alternatives than forward-iterating some
probably-huge # of times.  What do you ["y`all" -- I live in Texas
;-)] think about that?

Since the extra check would incur a tiny amount of run-time overhead,
maybe the check itself should be surrounded by "#if !NDEBUG" or
similar, but perhaps a modified version of the above should be put
into the "debug/" top-level directory of libstdc++ instead.

Maybe the desired result can be achieved w/o any run-time overhead by
using concept checking to ensure the type indicated by "_Distance" is
unsigned?  In that case, I would change the name of that param. for
this template, since a "distance type" is supposed to be signed IIRC.
OTOH, that technique might cause unexpected problems: for example,
with the literal value for one with no suffix [i.e. just
"advance(iter, 1);", not "advance(iter, 1u);" or "advance(iter, 1uL);"
or similar], the type will be deduced as just "int" AFAIK [i.e. not
"unsigned int"], and that would break this way of dealing with the
problem.  I think it would be egregious to require users to write "1u"
instead of just 1 in order to be able to use "advance" safely with
literal #s.  Your opinion[s], please?

I wonder if there`s a way to do this with zero runtime overhead for at
least _some_ values, e.g. compile-time constants...  if I were to
write "static_assert(__n >= 0)" I`m pretty sure that would require the
value of __n to be known at compile-time, which is not what I want to
say.  What I want is something like "if /* maybe static_if instead */
(value_known_at_compile_time(__n))  static_assert(__n >= 0);".  IDK of
any way to express that yet in standard C++ [not even in C++2011].
Any suggestions, anybody?

Regards,

Abe