Re: [boost] Is Boost.Range broken?

Subject: Re: [boost] Is Boost.Range broken?
From: Dave Handley (dave_at_[hidden])
Date: 2008-11-22 14:38:21

>
> on Sat Nov 22 2008, "Dave Handley" <dave-AT-dah.me.uk> wrote:
>
>>> on Fri Nov 21 2008, "Scott McMurray" <me22.ca+boost-AT-gmail.com> wrote:
>>
>>>> so I'm not convinced that the "singular implies empty" behaviour was
>>>> ever documented.  (The "returns" entry for empty is the same for
>>>> 1_36_0, 1_35_0, 1_34_0, and 1_33_1.)
>>>
>>> Hmmm.
>>
>> Sorry - I'm not convinced this is correct.  In 1.35.0 onwards the
>> functionality looked like this:
>>
>>            bool empty() const
>>            {
>>                BOOST_ASSERT( !is_singular() );
>>                return m_Begin == m_End;
>>            }
>>
>> In earlier releases the functionality looked like this:
>>
>>            bool empty() const
>>            {
>>                if( singular )
>>                    return true;
>>
>>                return m_Begin == m_End;
>>            }
>>
>> This means that in earlier releases, empty() would return true for
>> singular ranges, in newer releases, debug would assert for singular
>> ranges and be undefined for non-singular ranges.  Perhaps the
>> documentation didn't reinforce this fact, but the functionality has
>> most definitely changed.  If the documentation didn't follow what the
>> library does, that just points to poor documentation IMHO.
>
> The library may indeed have been poorly documented, but I don't see how
> what you wrote here addresses Scott's statement in any way.  You simply
> cannot count on undocumented behaviors of a library; they are subject to
> change without notice.

Actually, looking at the quotes from Tom in a separate part of the thread, 
much of this behaviour was documented.

>
>>>>> 2) The behaviour is unintuitive.  Range is a generalisation of the
>>>>> interface of the std::containers.  With this change, containers and
>>>>> ranges can no longer be used in the same code path.
>>>>
>>>> Why would you ever want to pass a default-constructed range to 
>>>> anything?
>>>
>>> I will admit that there have been times that I really wished
>>> default-constructed iterators all had a value analogous to NULL, that
>>> was different from all other values of the same type and yet
>>> nonsingular.  But that's not how it is, and if you're going to build
>>> a range on top of the existing iterator abstraction, I don't see how
>>> you can do much better.
>>
>> Whilst I understand where everyone is coming from in this thread, I'm
>> going to slightly disagree.  Again quoting from the source,
>
> I doubt I'll find quotes from the source very persuasive, since what you
> can count on should be determined by the docs.... of course comments in
> the source are a kind of documentation.

And much of this was also in the docs; although this brings up a separate 
point.  One of the biggest complaints I got when supported boost for my firm 
was about the documentation.  Generally it just isn't up to the same 
standard as the code.  This is something that is gradually being fixed, but 
hearing the complaints from Java programmers moving to using C++ and Boost, 
it's very hard to argue against them.  Given the quality of the docs, are 
you surprised when people figure things out from the source?

>
>> at the top of iterator_range we see:
>>
>> /*! \file
>>    Defines the \c iterator_class and related functions.
>>    \c iterator_range is a simple wrapper of iterator pair idiom. It 
>> provides
>>    a rich subset of Container interface.
>> */
>>
>> This implies to me that range is trying to look and feel like a 
>> container -
>> not like an iterator.
>
> I understand that you drew that conclusion, but IMO it's a huge stretch
> to claim that a concept that doesn't even exist for containers
> (singularity) should behave in some container-like way for ranges.

It's not a huge stretch, it's just something that is useful for generic 
programming.  Like everything in programming, if we get hung up on 
principles, we forget that people have to use this code.

>
>> I agree that singular iterators (as defined in the standard) are
>> undefined when default constructed;
>
> To be precise, they're not undefined.  All singular iterators are alike,
> regardless of how they're produced (default-constructed or otherwise).
> They have two defined operations: assignment and destruction.
>
>> however, no equivalent exists for containers.  One of the most useful
>> use cases for iterator_range is where you allow some generic code to
>> accept both iterator_ranges and containers.  In this context having
>> some sort of empty range that isn't tied to a specific underlying
>> container is extremely useful.
>
> Yes, it can be.
>
>> Creating that sort of empty range by default constructing an iterator
>> range was intuitive (at least to me),
>
> Yes, it is intuitive.
>
>> and actually worked in 1.34 and earlier.
>
> Perhaps.  But did the documentation guarantee that it would work?

I believe it did - looking at a quote from Tom elsewhere in the thread.

>
>> Now of course that functionality doesn't work.  The new implementation
>> might seem more "pure" if you think of a range as being more like an
>> iterator than a container, but I would argue that it is more like a
>> container.  In that context, you really need some sort of empty
>> construct.
>
> You're free to define models of Range that have a default-constructed
> empty state.  Requiring all models of Range to behave that way is
> antithetical to the principles of generic programming.

And that isn't what I'm arguing for.  Tom has proposed (and I think in your 
first response you in general agreed) that 2 versions of iterator_range 
would be the best solution here.  I fundamentally agree with that position.

>
>> In general, range sits in a strange middle ground.  It is trying to be
>> a clever pair of iterators, and also trying to look and feel like a
>> container.
>
> I disagree.  IMO Range is a pair of iterators You can see that by
> looking at all of the models that don't behave in any container-like
> way, e.g. std::pair<int*,int*>, and if you read any book on the STL
> you'll even see pairs of iterators referred to as "ranges."  The key
> feature of a Container that distinguishes it from a Range is its
> ownership of the values: when you copy it, the values are copied, too.

One feature of some containers is that.  Some containers (not in the STL) 
don't own the data.  But that point isn't really that important.  An 
iterator range is also not an iterator, as well as not being a container.

> It's unfortunate that the original implementation of iterator_range set
> up different expectations for you, but AFAICT the only thing that a
> Range has in common with a container is that it supplies a begin() and
> end() that delimit a sequence of elements.

And an empty() and a size() and a random access function operator[], etc. 
And a comment in the source about being container-like.

>
>> As such it has properties of both.  Singularity is something really
>> reserved for iterators, and therefore, I don't think it is necessarily
>> obvious that a range either should or shouldn't have the same iterator
>> like singularity features.
>
> I would find that argument more compelling if there was a "singular"
> concept that applied to containers, but there isn't.
>

This is precisely the sort of discussion that comes about with a concept 
that sits between 2 other concepts.  Iterator_range sits in between iterator 
and container, which is the whole basis of my argument.  How much like an 
iterator or like a container it is is open to discussion, but it certainly 
isn't either one of them.  Singularity is a feature of iterators, not 
containers - I agree - but that also shouldn't necessarily drive the design 
of iterator_range, since an iterator_range isn't an iterator. It is; 
however, what the library intends it to be.  Clearly, in both documentation 
and code, the library changed it's mind about what an iterator_range was 
between 1.34 and 1.35 - that's problematic when people have spent a long 
time coding off the old functionality.

Finally, we can discuss detailed semantics of what an iterator_range should 
be all we like, the core issue here though is that iterator_range changed 
unannounced between 2 versions of boost.  Why can't we come to an agreement 
that 2 versions of iterator_range would make some sense, and move this 
discussion forward?

Dave