Good News for the Pipes Library: pipes::funnel Is Now Gone

Published September 10, 2019

Up until now, the pipelines created with the pipes library needed to start with pipes::funnel:

myVector >>= pipes::funnel
         >>= pipes::transform(f)
         >>= pipes::demux(back_inserter(results1),
                          back_inserter(results2),
                          back_inserter(results3));

pipes::funnel was in the library because I couldn’t see how to implement pipes without it.

Several reviewers, including Sy Brand and TH, suggested that the library could be implemented without pipes::funnel. That helped me find a way to remove it, and it’s now gone. Big thanks to them!

Implementing operator>>= without using pipes::funnel was interesting from a technical point of view. In this article I’ll explain why pipes::funnel was useful and how it got replaced thanks to the C++ detection idiom.

What `pipes::funnel` was doing before

As a reminder, here was the implementation of pipes::funnel (that used to be called to_output in the old version of the library that was called Smart Output Iterators):

struct Funnel {};
const Funnel funnel{};

template<typename Pipe>
class pipe_entrance
{
public:
    explicit pipe_entrance(Pipe pipe) : pipe_(pipe) {}
    Pipe get() const { return pipe_; }
private:
    Pipe pipe_;
};

template<typename Pipe>
pipe_entrance<Pipe> operator>>=(Funnel, Pipe pipe)
{
    return pipe_entrance<Pipe>(pipe);
}

template<typename Range, typename Pipe>
void operator>>=(Range&& range, pipe_entrance<Pipe> const& pipeEntrance)
{
    std::copy(begin(range), end(range), pipeEntrance.get());
}

The line that contains the main behaviour of pipes::funnel is the one before last: when you associate a range and pipes::funnel with operator>>=, the library iterates over the range and sends each element to the pipe after pipes::funnel.

The other operator>>=s between pipes have a different behaviour: they build up a pipeline by tacking on the pipe on the left to the pipeline on the right.

So the behaviour of operator>>= is not the same when the left hand side is a pipe and when it’s a range. And pipes::funnel allowed to write an operator>>= for the case where the left hand side is a range.

To get rid of pipes::funnel, we therefore need to write a specific code of operator>>= when its left hand side is a range.

To do that in C++20 we can use concepts, to detect that the left hand side of operator>>= is a range.

But the library is compatible with C++14, so we won’t use concepts here. Instead we’ll emulate concepts with the detection idiom.

The detection idiom

The detection idiom consists in writing an expression in a decltype, and using SFINAE to instantiate a template function if that expression is valid.

Let’s pull up the code to implement the detection idiom from the popular Expressive C++ Template Metaprogramming article:

template<typename...>
using try_to_instantiate = void;
 
using disregard_this = void;
 
template<template<typename...> class Expression, typename Attempt, typename... Ts>
struct is_detected_impl : std::false_type{};
 
template<template<typename...> class Expression, typename... Ts>
struct is_detected_impl<Expression, try_to_instantiate<Expression<Ts...>>, Ts...> : std::true_type{};
 
template<template<typename...> class Expression, typename... Ts>
constexpr bool is_detected = is_detected_impl<Expression, disregard_this, Ts...>::value;

Essentially is_detected_impl will inherit from std::false_type if Expression<Ts...> is not a valid expression, and from std::true_type if it is a valid expression.

is_detected is then a compile time constant equal to true or false accordingly.

An exemple of expression is an assignment x = y:

template<typename T, typename U>
using assign_expression = decltype(std::declval<T&>() = std::declval<U&>());

We can then use is_detected this way:

template<typename T, typename U> constexpr bool is_assignable = is_detected<assign_expression, T, U>;

If this doesn’t make perfect sense, check out the article that will walk you to every step of this idiom.

We can then create a template function that will only be instantiated if the template argument meet the requirement of being assignable to one another. To do this, we’ll use the SFINAE trick shown in How to make SFINAE pretty and robust, using a bool:

template<typename T, typename U>
using AreAssignable = std::enable_if_t<is_assignable<T, U>, bool>;

And then, using this requirement on a function (or class):

template<typename T, typename U, AreAssignable<T, U> = true>
void myFunction(T&& t, U&& u)
{
    // ...
}

This template function will only be instantiated if T is assignable to U.

The range expression

Our purpose now is to create an expression that will identify if the left hand side of operator>>= is a range. If it is, we’ll iterate through that range.

How do we identify if a type is a range? There are several things, but for our purpose of distinguishing between a range and a pipe we’ll define a range this way: a type is a range if it has a begin and an end.

Let’s create the expressions corresponding to calling begin and end on an object:

template<typename T
using begin_expression = decltype(std::begin(std::declval<T&>()));

template<typename T>
using end_expression = decltype(std::end(std::declval<T&>()));

We use std::begin because it calls the begin member function of the object, and also works on C arrays.

Now we can detect if an object is a range, by our definition:

template<typename Range>
constexpr bool range_expression_detected = is_detected<begin_expression, Range> && is_detected<end_expression, Range>;

template<typename Range>
using IsARange = std::enable_if_t<range_expression_detected<Range>, bool>;

The case of ADL functions

As Sy Brand and marzojr pointed out on Github, those expressions don’t cover the case of begin and end free functions that are found by ADL.

Indeed, if we have the following collection in a namespace:

namespace MyCollectionNamespace
{
    class MyCollection
    {
        // ...
        // no begin and end member functions
    };
    
    auto begin(MyCollection const& myCollection);
    auto end(MyCollection const& myCollection);
}

std::begin won’t work on that collection, because the available begin is not in the std namespace. We therefore need to add the possibility to just call begin on the collection. But we also need to be able to call std::begin for the collections it works on.

For that, we can add std::begin to the scope. But so as not to add it to every file that uses our code, we will scope it into its own namespace:

namespace adl
{
    using std::begin;
    using std::end;

    template<typename T>
    using begin_expression = decltype(begin(std::declval<T&>()));
    template<typename T>
    using end_expression = decltype(end(std::declval<T&>()));
}

template<typename Range>
constexpr bool range_expression_detected = detail::is_detected<adl::begin_expression, Range> && detail::is_detected<adl::end_expression, Range>;

template<typename Range>
using IsARange = std::enable_if_t<range_expression_detected<Range>, bool>;

This requirement for a range now also covers begin and end functions that are defined with ADL.

Implementing `operator>>=` without `pipes::funnel`

Now that we can identify a range, we can write our operator>>=:

template<typename Range, typename Pipeline, IsARange<Range> = true>
void operator>>=(Range&& range, Pipeline&& pipeline)
{
    std::copy(begin(range), end(range), pipeline);
}

We can now use the operator>>= with a range and without pipes::funnel:

myVector >>= pipes::transform(f)
         >>= pipes::demux(back_inserter(results1),
                          back_inserter(results2),
                          back_inserter(results3));

Note that the operator>>= is in the pipes namespace, so it won’t affect other classes when there is no pipe involved.

What’s next

There is much more that we want to do with operator>>=. For example, being able to compose pipes into reusable components:

auto pipeline = pipes::filter([](int i) { return i % 2 == 0; })
            >>= pipes::transform([](int i ){ return i * 2;});

input >>= pipeline >>= back_inserter(results);

For the moment the operator>>= doesn’t support this kind of composite pipes, even though that’s a natural thing to expect from the library.

To make this work, we need to rationalise the design of operator>>= and clarify our interfaces and what we mean by a Pipeline. This is what we tackle in a next post.