Re: [boost] Is Boost.Range broken?

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

>
> on Fri Nov 21 2008, "Scott McMurray" <me22.ca+boost-AT-gmail.com> wrote:
>
>> On Fri, Nov 21, 2008 at 17:09, Tomas Puverle
>> <Tomas.Puverle_at_[hidden]> wrote:
>>> 1) Empty ranges are useless and they cannot even be reliably tested for
>>> emptiness.
>>
>> No, empty ranges are useful and can be reliably tested.
>>
>>> The empty() function now asserts and the is_singular() function
>>> behaves differently between debug and release builds, making it 
>>> impossible to
>>> detect if a range is, in fact, empty.
>>
>> Yes, singular ranges are almost useless, and cannot be tested for
>> singularity.  This seems reasonable, as it's just like ints and
>> iterators.  I wouldn't say that a singular range is empty, just as I
>> wouldn't say that an uninitialized int has a value.
>
> That's my inclination, too.  Of course, I wouldn't object to another
> iterator range class that gives the stronger guarantee that it is never
> singular.  There's no point in distinguishing the idea of "singular"
> from that of "empty" if they are really the same thing, though.
>
>> I would agree that is_singular should not be available at all in
>> release builds, if it's never useful there.  I'd consider it analagous
>> to iterator debugging features, and would think it might be exposition
>> only.
>
> "Exposition only" in the standard is used to give a sense of how
> something might be implemented, or to say, "here's a working
> implementation but we're not saying you actually have to do it that way,
> so long as you give the right observable behavior."
>
> So I don't think "exposition only" is quite the right terminology.
> Iterator debugging isn't described that way anywhere, AFAIK.
>
>>> In addition, this is not documented well and can lead to subtle bugs
>>> and undefined behaviour, which will only manifest itself in release
>>> builds.
>>
>> But what semantics for empty *are* documented?
>>
>> http://www.boost.org/doc/libs/1_37_0/libs/range/doc/boost_range.html#Semanticsempty(x)
>> returns boost::begin(x) == boost::end(x)
>>
>> That's undefined when begin and end return singular iterators,
>
> Correct.
>
>> 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.

>
>>> 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, 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 agree that singular iterators (as defined in the 
standard) are undefined when default constructed; 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.  Creating that sort 
of empty range by default constructing an iterator range was intuitive (at 
least to me), and actually worked in 1.34 and earlier.  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.

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. 
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.

Personally, reading this entire thread, I find the proposal by both Tomas 
Puverle and David Abrahams that 2 versions of iterator_range exist, one that 
tests for singularity and one that doesn't, by far the most palatable 
solution.  It allows you to have a lean and mean iterator_range if you want 
to store lots of them in a container (the use case that Dave talks about), 
it also allows you to have an empty range when you need an iterator_range to 
look like a container.  This could be trivially implemented with inheritance 
or a policy template.  It would be a nice solution to the problem from both 
directions, and I think it makes the most sense.

Dave