Re: [boost] [iterator] UB when implicitly using default constructed counting_iterator<unsigned>

Subject: Re: [boost] [iterator] UB when implicitly using default constructed counting_iterator<unsigned>
From: Claas H. Köhler (claas.koehler_at_[hidden])
Date: 2012-12-05 02:53:41

On 04/12/12 18:42, Jeffrey Lee Hellrung, Jr. wrote:
> On Mon, Dec 3, 2012 at 6:07 AM, "Claas H. Köhler" <claas.koehler_at_[hidden]>wrote:
> 
>>
>>
>> On 01/12/12 18:39, Steven Watanabe wrote:
>>> AMDG
>>>
>>> On 12/01/2012 07:20 AM, Peter Sommerlad wrote:
>>>> Hi Jeff
>>>>
>>>> On 01.12.2012, at 02:53, Jeffrey Lee Hellrung, Jr. wrote:
>>>>
>>>>>>  And a default
>>>>>> initialized scalar type, isn't.
>>>>>>
>>>>>
>>>>> "isn't"...what, exactly?
>>>>
>>>> it isn't initialized with a defined value.
>>>>
>>>> struct X{
>>>>      X(){}
>>>> unsigned x;
>>>> };
>>>> void foo(){
>>>> X y; // -> y.x has an uninitialized value AFAIK if it is local
>>>> }
>>>> that is the situation we run into with the default constructed
>> counting_iterator<unsigned>()
>>>>
>>>
>>> IMO, this is a good thing.  Any use of a default
>>> constructed counting_iterator is probably wrong,
>>> no matter what (arbitrary) value is chosen.  As
>>> such, it's better to leave it uninitialized, so
>>> these errors can be caught by tools like valgrind.
>>>
>>>>> I'm not opposed to giving defined behavior to a default constructed
>>>>> counting_iterator< [integral type] >, I'm just not sure what that
>> defined
>>>>> behavior should be. Maybe I'm over-analyzing it...
>>>>
>>>> I still believe the most simple change I suggested is enough (at least
>> it would cover my situation well enoughi).
>>>
>>> Your use case is very error prone.  It only works
>>> because you started the iteration at 1, not 0.
>>>
>>>> Those input iterators where a default constructed one is the end
>> iterator is IMHO more of an exception, because it is a special case for the
>> stream iterators.
>>>
>>> Any other iterator gives undefined behavior when
>>> it's default constructed.  I don't see why counting_iterator
>>> should be different.
>>>
>>>> Your idea with std::numberic_limits< Iterator >::max() requires a much
>> more complex solution with template meta programming, i.e.,
>> enable_if<is_arithmetic<Iterator>> or similar. And it won't provide the
>> default value of Iterator, which is zero in the case of the built-in
>> arithmetic types, i.e., unsigned().
>>>>
>>>> What do you think?
>>>>
>>>
>>> In Christ,
>>> Steven Watanabe
>>
>> Accidentally I just encountered a similar problem in my code, which was
>> caused by counting_iterator
>> not beeing initialised and it took me a while to debug it.
>>
> 
> To be precise, the cause of your problem is your use of a
> default-constructed counting_iterator, not the behavior of a
> default-constructed counting_iterator, right?
To be very precise, it was actually the assumption that counting_iterator behaves similar to
all other iterators in the standard library, which guarantee a defined behaviour when default
constructed. (By guaranteed I mean as far as I have seen so far. Not sure what the standard
says about them)

> 
> I support Peter's suggestion to initialise counting_iterator<T> with T()
>> because it forwards the
>> default behaviour of T, which will become inaccessible in template code
>> otherwise.
>>
> 
> I'm not sure I follow. Can't you just use
> counting_iterator<T>::counting_iterator(T) ?
> 
> [...]
> 
Most of the time no, because typically I have a template parameter for the iterator, i.e. something
like

template<class IT>
void doSomething(IT first, IT last){
  while(first != last){...}
}

Thus the information about the template parameter passed to counting_iterator is lost, unless you
specialise overloads for counting_iterator.

By the way, has anyone of you ever seen a case, where a loop similar to the one above leads to
undefined behaviour, if two default constructed  (standard library) iterators of any kind are passed?

>> Furthermore I interpret counting_iterator as a wrapper around objects of
>> type T, so forwarding the
>> default constructor of T is desirable from my point of view, mainly
>> because there is no way to
>> reproduce its behaviour, once the information about the iterator type is
>> lost (as is the case in the
>> example above)
>>
> 
> That may be true in general, but a default-constructed counting_iterator<
> [integral type] > should really never be used in iteration. I might even go
> so far as to suggest disabling the default constructor (or adding a static
> assertion), but that might be too restrictive (it's fine and sometimes
> convenient to default-construct and assign, for example). Furthermore,
> building on Steven's prior point, a default-constructed counting_iterator
> which 0-initializes could actually hide incorrect usage (see original
> example with primes, which works non-obviously with the proposed behavior
> change) that wouldn't be picked up by external tools.
I think this problem is more related to the underlying base class of the counting_iterator, since
integers do not provide an "invalid value" in contrast to pointers (underlying most
other iterators), which can be NULL to signal.

Considering your opinion, that uninitialised values for numeric types are preferable to
zero-initialised ones, since they are easier to trace back by external tools: Can you name
any place in the standard library, where this strategy is used? std::complex<T>, e.g. does not
follow this strategy, since the default constructor initialises real and imaginary part to T().

> I just haven't seen a valid use case where 0-initializing the value of a
> default-constructed counting_iterator< [integral type] > is desirable other
> than to help identify incorrect usage, but I'm not even convinced it would
> do that :/
> 
> - Jeff

One use case would be a loop, such as the one posted above. I would personally favour this loop to
quit immediately, when two default constructed iterators are passed. A similar use case is the
boost::iterator_range, which is not guaranteed to be empty, if default constructed for the
counting_iterator. In fact, that was actually the problem I encountered. Consider code like this

template<class R>
struct RangeWrapper{

  [...]

  bool empty(void) const { return range.begin() == range.end(); }

  R range;
};

I have not found a way (other than specialising for R= iterator_range<counting_iterator>) to define a
default constructor, such that empty is guaranteed to return true for default constructed
RangeWrapper instances.

>From my point of view, the biggest draw back is, that the current implementation behaves differently
from any other iterator in (my implementation of) the standard library I have worked with so-far.