Re: [boost] Is Boost.Range broken?

Subject: Re: [boost] Is Boost.Range broken?
From: David Abrahams (dave_at_[hidden])
Date: 2008-11-22 13:42:09

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.

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

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

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

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

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

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

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com