Re: [boost] [guidelines] why template errors suck

Subject: Re: [boost] [guidelines] why template errors suck
From: David Abrahams (dave_at_[hidden])
Date: 2010-09-28 21:04:11

At Tue, 28 Sep 2010 15:31:42 -0700, Steven Watanabe wrote:
> 
> How do you define a concept for a fusion sequence?
> 
> First of all, this a reasonable thing to do, since there
> are many algorithms that can be defined for an arbitrary
> fusion sequence.

Fantastic example!  

> As an example, let's use the fusion::less algorithm.

That would be great, except that I can't find such an algorithm in
http://www.boost.org/doc/libs/1_44_0/libs/fusion/doc/html/index.html,
and how the rest of this conversation goes would depend on its
semantics.  For example, does it do a full lexicographic compare, or
must the two sequences have the same length?  If you mean what's in
boost/fusion/sequence/comparison/less.hpp, it's the former.

> template<class S>
> bool less(const S& lhs, const S& rhs);
> 
> This algorithm requires that S is a FusionSequence,
> and all the elements are LessThanComparable
> 
> Here's a first attempt (playing fast and loose
> with syntax because I don't remember the details):
> 
> -------------------------------------------
> 
> concept FusionSequence<class S> {
>     // What goes here?
> };
> 
> template<FusionSequence S>
> requires LessThanComparable<???>
> bool less(const S& lhs, const S& rhs);
> 
> -------------------------------------------
> 
> Suppose that we use something like this:
> 
> concept FusionSequence<class S> {
>      FusionSequence next_type;
>      next_type pop_front(const S&);
>      S::front_type;
>      front_type front(const S&);
>      constexpr bool empty(const S&);
> };
> 
> This almost works, but what about the empty
> sequence?  pop_front for the empty sequence
> has to return itself, and front has to return a dummy
> value.

Close.  What you need is a refined concept for NonEmptyFusionSequence
that includes front_type and pop_front.  Just riffing here, but this
could work:

concept FusionSequence<class S>
{
     CompileTimeInt size_type = int_<0>;

     constexpr bool empty(const S&) { return size_type::value; }
     constexpr std::size_t size(const S&) { return size_type::value; }
}

auto concept NonEmptyFusionSequence<class S> 
  : FusionSequence<S>
{
     FusionSequence next_type;
     next_type pop_front(const S&);

     typename front_type;
     front_type front(const S&);

     CompileTimeInt size_type = int_<next_type::size_t::value+1>;
};

#if THE_VERBOSE_NON_TRICKY_WAY

auto concept EmptyFusionSequence<class S> : FusionSequence<S>
     requires SameType<S::size_type,int_<0> >
{};

template <EmptyFusionSequence S1, EmptyFusionSequence S2>
concept_map LessThanComparable<S1,S2>
{
    constexpr operator<(S1 const&, S2 const&) { return false; }
}

template <NonEmptyFusionSequence S1, EmptyFusionSequence S2>
concept_map LessThanComparable<S1,S2>
{
    constexpr operator<(S1 const&, S2 const&) { return false; }
}

template <EmptyFusionSequence S1, NonEmptyFusionSequence S2>
concept_map LessThanComparable<S1,S2>
{
    constexpr operator<(S1 const&, S2 const&) { return true; }
}

#else 

// A shorter way. Because of refinement, this one will only get
// used when either S1 or S2 is empty.

template <FusionSequence S1, FusionSequence S2>
  // a constraint you could add for clarity, but don't need
  // requires SameType<int_<0>, int_<S1::size_type()*S2::size_type()> >
concept_map LessThanComparable<S1,S2>
{
    constexpr operator<(S1 const&, S2 const&)
    { return S1::size_type() < S2::size_type(); }
}

#endif

template <NonEmptyFusionSequence S1, NonEmptyFusionSequence S2>
  requires LessThanComparable<S1::front_type,S2::front_type>
        && LessThanComparable<S1::next_type,S2::next_type>
concept_map LessThanComparable<S1,S2>
{
    operator<(S1 const& x, S2 const& y)
     { return front(x) < front(y) || pop_front(x) < pop_front(y) }
}

> Another way to solve this would be
> something like
> auto concept less_impl<EmptyFusionSequence> { ... };
> auto concept less_impl<FusionSequence> { ... };
> 
> This has the unfortunate side-effect of exposing
> implementation details of function templates
> using less.
> 
> template<class S>
> requires less_impl<S>
> void f(const S& arg) {
>      S other = /*...*/;
>      less(other, arg);
> }
> 
> User's of f don't care that it is less internally, but
> the fact of its use has to get propagated up to
> all calling templates.

I don't see where you get that, at all.

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