Re: [boost] [parameter] type requirement compiler error

Subject: Re: [boost] [parameter] type requirement compiler error
From: Lorenzo Caminiti (lorcaminiti_at_[hidden])
Date: 2011-11-08 17:21:21

On Tue, Nov 8, 2011 at 9:29 AM, Daniel Wallin <daniel_at_[hidden]> wrote:
> On Sun, Nov 6, 2011 at 8:12 PM, Lorenzo Caminiti <lorcaminiti_at_[hidden]> wrote:
> On Sat, Nov 5, 2011 at 7:17 AM, Lorenzo Caminiti <lorcaminiti_at_[hidden]> wrote:
>> > Please someone help :)
>>
>> I looked into Boost.Parameter tests and
>> boost/libs/parameter/test/deduced_dependent_predicate.cpp uses
>> tag::x::_ so I modified the example to the following that compiles:
>>
> [...]
>>
>> #include <boost/parameter.hpp>
>> #include <boost/mpl/placeholders.hpp>
>> #include <boost/type_traits/is_same.hpp>
>> #include <boost/type_traits/add_pointer.hpp>
>> #include <iostream>
>>
>> BOOST_PARAMETER_NAME(x)
>> BOOST_PARAMETER_NAME(y)
>>
>> BOOST_PARAMETER_FUNCTION(
>>     (int),
>>     f,
>>     tag,
>>     (required
>>         (x, *)
>>         (y, *(boost::is_same<boost::mpl::_,
>>                 boost::add_pointer<tag::x::_>::type>)) // (2)
>                                               ^^^^^^
> Here's the problem in this case: you are eagerly evaluating
> add_pointer<>. Remove the ::type and this works:
>
>  (y, *(boost::is_same<boost::mpl::_,
>         boost::add_pointer<tag::x::_> >))
>
> This is really the same problem that the documentation sample has:
>
>   (required (graph, *) )
>   (optional (root_vertex,
>       (typename boost::graph_traits<graph_type>::vertex_descriptor),
>           *boost::vertices(graph).first) )
>
> graph_traits<..> is eagerly evaluated here, resulting in the error. You
> need to be lazy here, but there's no appropriate metafunction in the
> graph library, so we need to write one:
>
>  template <class G>
>  struct vertex_descriptor {
>    typedef typename boost::graph_traits<G>::vertex_descriptor type;
>  };
>
> and then do:
>
>   (required (graph, *) )
>   (optional (root_vertex,
>       *(boost::is_convertible<mpl::_, vertex_descriptor<tag::graph::_> >),
>           *boost::vertices(graph).first) )

I see. Yes, this worked and I have listed below my original DFS
example with this change which now compiles. Thank you very much!

> Note that you need can't use:
>
>  (vertex_descriptor<tag::graph::_>)
>
> because the library doesn't properly treat the predicate as a
> metafunction in all the places that it should.

Can this be fixed?

>> A far as I can tell, there are two major issues here that should be
>> fixed in Boost.Parameter:
>> 1) The docs don't mention tag::xyz::_ at all, they refer to xyx_type
>> which only works within the function definition and not in the
>> function declaration.
>
> Yes, clearly a documentation bug.

Yes, the docs don't mention how to use tag::xyz::_ at all (I even
started to look at the source code and I understand some
metaprogramming but still I had no clue what was going on). Could the
doc examples also be tested by the regression tests to make sure they
compile? (I will send another email with attached the source code of
all the doc example that I reworked so they compile.)

>> 2) The change from x_type to tag::xyz::_ broke the ability to
>> manipulate the parameter type in the function declaration. For
>> example, it broke the ability for Boost.Parameter to program the DFS
>> interface. This seems a major feature that was lost and
>> Boost.Parameter should be fixed to regain such a feature. BTW, why was
>> x_type changed to tag::xyx::_? What's the benefit for that?
>
> It wasn't changed actually, it always worked like this.
>
> Predicates are invoked with two arguments: the argument type to
> validate, and the partial argument pack containing the preceding
> function parameters.
>
>  template <class Arg, class Pack>
>  struct predicate;

It'd be great to mention this in the docs as well (I'd probably be
able to figure our the issue if I knew this much).

> tag::x::_ is actually a shortcut for:
>
>  boost::parameter::value_type<tag::x, mpl::_2>
>
> intended to simplify referring to preceding parameters in the
> predicates.
>
> Now, if we wanted the ability to access preceding parameter types like
> in the docs, the macros would need to wrap the user predicates like
> this:
>
>  template <class Arg, class Pack>
>  struct z_predicate {
>    typedef typename parameter::value_type<tag::x, Pack> x_type;
>    ...
>    typedef typename parameter::value_type<tag::y, Pack> y_type;
>    typedef typename mpl::apply2<actual-predicate, Arg, Pack>::type type;
>  };
>
> It wasn't done this way for compile time performance reasons. Perhaps we
> could have done this in a simpler way, where we would build the entire
> argument pack and then use one single predicate to validate the entire
> thing once, but that's not how it currently works.
>
> Looking at the current docs, it's full of problems like this. :( In
> fact, *all* of the predicates in the DFS example are wrong.
>
> Does this help?

Yes, thanks a lot!!

This DFS example now compiles :))

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/range/irange.hpp>
#include <boost/pending/indirect_cmp.hpp>
#include <boost/parameter.hpp>
#include <boost/type_traits/is_convertible.hpp>
#include <boost/type_traits/is_integral.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/mpl/and.hpp>
#include <boost/mpl/placeholders.hpp>
#include <iostream>

namespace graphs {

template< typename G >
struct vertex_descriptor
{
    typedef typename boost::graph_traits<G>::vertex_descriptor type;
};

template< typename T >
struct is_incidence_and_vertex_list_graph :
    boost::mpl::and_<
          boost::is_convertible<
              typename boost::graph_traits<T>::traversal_category
            , boost::incidence_graph_tag
          >
        , boost::is_convertible<
              typename boost::graph_traits<T>::traversal_category
            , boost::vertex_list_graph_tag
          >
    >
{};

template< typename T, typename Key >
struct is_property_map_of_key :
    boost::is_same<Key, typename boost::property_traits<T>::key_type>
{};

template< typename T, typename Key >
struct is_integral_property_map_of_key :
    boost::mpl::and_<
          boost::is_integral<typename boost::property_traits<T>::value_type>
        , is_property_map_of_key<T, Key>
    >
{};

template< typename Size, typename IndexMap >
boost::iterator_property_map<boost::default_color_type*, IndexMap,
        boost::default_color_type, boost::default_color_type&>
default_color_map ( Size const& num_vertices, IndexMap const& index_map )
{
    std::vector<boost::default_color_type> colors(num_vertices);
    return &colors[0];
}

BOOST_PARAMETER_NAME(graph)
BOOST_PARAMETER_NAME(visitor)
BOOST_PARAMETER_NAME(root_vertex)
BOOST_PARAMETER_NAME(index_map)
BOOST_PARAMETER_NAME(color_map)

BOOST_PARAMETER_FUNCTION(
    (void),
    depth_first_search,
    tag,
    (required // Required named parameters (no default value).
        (graph, *(is_incidence_and_vertex_list_graph<boost::mpl::_>))
    )
    (optional // Optinal named parameters (with default values).
        (visitor, *, boost::dfs_visitor<>()) // Any type.
        (root_vertex, // Specified type.
                *(boost::is_same< boost::mpl::_,
                        vertex_descriptor<tag::graph::_> >),
                *boost::vertices(graph).first)
        (index_map,
                *(is_integral_property_map_of_key< boost::mpl::_,
                        vertex_descriptor<tag::graph::_> >),
                boost::get(boost::vertex_index, graph))
        (in_out(color_map),
                *(is_property_map_of_key< boost::mpl::_,
                        vertex_descriptor<tag::graph::_> >),
                default_color_map(boost::num_vertices(graph), index_map))
    )
) {
    boost::depth_first_search(graph, boost::visitor(visitor).
            color_map(color_map).root_vertex(root_vertex).
            vertex_index_map(index_map));
}

} // namespace graphs

template< typename TimeMap >
class dfs_time_visitor : public boost::default_dfs_visitor
{
    typedef typename boost::property_traits< TimeMap >::value_type T;
public:
    dfs_time_visitor(TimeMap dmap, TimeMap fmap, T& t)
        : dmap_(dmap), fmap_(fmap), time_(t)
    {}

    template< typename V, typename G >
    void discover_vertex ( V u, G const& g ) const { put(dmap_, u, time_++); }

    template< typename V, typename G >
    void finish_vertex ( V u, G const& g ) const { put(fmap_, u, time_++); }

    TimeMap dmap_;
    TimeMap fmap_;
    T& time_;
};

int main ( )
{
    typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS> G;
    typedef boost::graph_traits<G>::vertices_size_type size_type;

    enum {u, v, w, x, y, z, N};
    char names[] = {'u', 'v', 'w', 'x', 'y', 'z'};
    typedef std::pair<int, int> E;
    E edges[] = {E(u, v), E(u, x), E(x, v), E(y, x), E(v, y), E(w, y), E(w, z),
            E(z, z)};
    G g(edges, edges + sizeof(edges) / sizeof(E), N);

    std::vector<size_type> dtime(boost::num_vertices(g));
    std::vector<size_type> ftime(boost::num_vertices(g));
    size_type t = 0;
    dfs_time_visitor<size_type*> vis(&dtime[0], &ftime[0], t);

    graphs::depth_first_search(g, vis);

    std::vector<size_type> dorder(N);
    boost::integer_range<size_type> r(0, N);
    std::copy(r.begin(), r.end(), dorder.begin());
    std::sort(dorder.begin(), dorder.end(),
            boost::indirect_cmp<size_type*, std::less<size_type> >(&dtime[0]));
    std::cout << "order of discovery: ";
    for(int i = 0; i < N; ++i) std::cout << names[dorder[i]] << " ";
    std::cout << std::endl;

    std::vector<size_type> forder(N);
    std::copy(r.begin(), r.end(), forder.begin());
    std::sort(forder.begin(), forder.end(),
            boost::indirect_cmp<size_type*, std::less<size_type> >(&ftime[0]));
    std::cout << "order of finish: ";
    for(int i = 0; i < N; ++i) std::cout << names[forder[i]] << " ";
    std::cout << std::endl;

    return 0;
}

--Lorenzo