This is the mail archive of the
mailing list for the libstdc++ project.
room for improvement in implementation of "std::advance(InputIterator)": make it more resilient to bugs in user-level code: in particular, negative distances
- From: Abe <abe149 at gmail dot com>
- To: libstdc++ at gcc dot gnu dot org
- Date: Sun, 9 Dec 2012 18:11:50 -0600
- Subject: room for improvement in implementation of "std::advance(InputIterator)": make it more resilient to bugs in user-level code: in particular, negative distances
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>
__advance(_InputIterator& __i, _Distance __n, input_iterator_tag)
// concept requirements
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?