Re: [boost] Call for interest - BOOST_AUTO_FUNCTION

Subject: Re: [boost] Call for interest - BOOST_AUTO_FUNCTION
From: Matt Calabrese (rivorus_at_[hidden])
Date: 2010-10-27 19:36:37

On Sun, Oct 17, 2010 at 10:27 PM, David Abrahams <dave_at_[hidden]> wrote:

> BTW, seems like you're close enough; it's probably time to integrate
> concept support for a future BCCL.
>

Okay, I've finished support for everything talked about up until this point
(minus continue try, which is also now called auto try).

I also have some exciting news (well, exciting to me at least, though I may
be jumping the gun). During development of the macro, I came up with a way
to emulate concept-based template overloads, and it should be possible to
integrate it into the macro, making for a possible, very powerful, BCCL 2.
By this I mean being able to write, for instance, a function template that
is overloaded for forward iterators and another that is overloaded for
random access iterators, while making it unambiguous to call with an
iterator that explicitly models the random access iterator concept -- I.E.
the random access iterator version will be picked as a better match, much
like what you'd use tag dispatching for now and what concept-based template
overloads would have done in C++ with concepts.

I don't have a working implementation with the macro yet, but my
"proof-of-concept" (har) seems to work like a charm, which I have included
in this post. Before going further, if you aren't following what I mean,
here's some hypothetical syntax that I'm fairly certain should be possible
(I may be able to come up with something simpler):

////////////////////////////////////////

// This is a "dispatcher" function template
// It specifies which arguments are used with concept overloads
// and forwards implementation to user-written overloads
// based on concepts that the arguments model
// "foo" is the name of the function and the part after that is a
// way to specify the parameters
BOOST_AUTO_FUNCTION
( ( template< class It > )
, ( foo )( (switch)(It)(iterator) ) // switch means that a given parameter
participates in the concept overloading
, ( explicit It )
)
// Note that switch can be used with any number of arguments
// I may get rid of switch on a per-argument basis and have it be
// implied for all arguments when a "switch" is present

// Here is an overload that is picked when iterator models forward_iterator
BOOST_AUTO_FUNCTION
( ( template< class It > )
, ( foo )( (case forward_iterator)(It)(iterator) )
, ( explicit It )
)
{
  // ...
  return iterator;
}

// Here is an overload that is picked when iterator models
random_access_iterator
BOOST_AUTO_FUNCTION
( ( template< class It > )
, ( foo )( (case random_access_iterator)(It)(iterator) )
)
{
  // ...
  return iterator;
}

int main()
{
  int* it = /*some valid initialization*/;
  foo( it ); // Unambiguously calls the random_access_iterator version
}

////////////////////////////////////////

The way it works internally is via an internal tag-dispatching-based system
that automatically knows all explicit concept maps associated with a given
type. It sort of magic, but I believe it is completely standard. The
surprisingly simple implementation trick that I use to pull this off is as
follows:

////////////////////////////////////////

// The max number of top-level concepts that can
// be associated with a single type
unsigned const top_index = 16;

template< unsigned MapIndex >
struct map_index : map_index< MapIndex - 1 >
{
  static_assert( MapIndex != top_index + 1, "Too many concept maps for type"
);
};

template<> struct map_index< 0 > {};

template< class ConceptMaps >
struct concept_map_child_t;

template< class... T >
struct vector;

template< class Vector, class Elem >
struct push_front;

template< class... T, class Elem >
struct push_front< vector< T... >, Elem >
{
  typedef vector< Elem, T... > type;
};

template< class... T >
struct concept_map_child_t< vector< T... > >
  : virtual T...
{
};

template< class ThisConceptMap = void, class OtherConceptMaps = void >
struct concept_maps_t
{
  static unsigned const value = OtherConceptMaps::value + 1;
  static map_index< value + 1 > next_index();
  typedef ThisConceptMap this_concept_map;
  typedef typename push_front< typename OtherConceptMaps::concept_maps
                             , this_concept_map
                             >::type
          concept_maps;
  typedef concept_map_child_t< concept_maps > tag_t;
  static tag_t tag() { return tag_t(); }
};

template<>
struct concept_maps_t<>
{
  static unsigned const value = 0;
  static map_index< 1 > next_index();
  typedef vector<> concept_maps;
  typedef concept_map_child_t< concept_maps > tag_t;
  static tag_t tag() { return tag_t(); }
};

template< class T >
struct identity {};

template< class T >
concept_maps_t<> concept_maps( T, map_index< 0 > );

// Creates a new "concept_maps" declaration that will be picked over
previous ones
// when passing in a given type and map_index< top_index >
#define MACRO_CALLED_INTERNALLY_WHEN_MAPPING( type, concept )\
namespace{\
concept_maps_t\
< concept\
, decltype( concept_maps( identity< type >(), map_index< top_index >() ) )\
>\
concept_maps\
( identity< type >\
, decltype( concept_maps( identity< type >()\
                        , map_index< top_index >() ).next_index()\
          )\
);\
}

////////////////////////////////////////

The purpose of the above code is to be able to automatically retrieve all
concepts associated with a given type at a given point in code. To see how
this would be used in practice:

////////////////////////////////////////

// Dummy types used as examples to symbolize concepts
struct some_concept0 {};
struct some_concept1 {};
struct some_concept2 {};
struct some_concept3 {};

// A user's hypothetical container type
class some_container {};

// Internals to explicit mappings to 4 different concepts
MACRO_CALLED_INTERNALLY_WHEN_MAPPING( some_container, some_concept0 )
// ... arbitrary code here...
MACRO_CALLED_INTERNALLY_WHEN_MAPPING( some_container, some_concept1 )
MACRO_CALLED_INTERNALLY_WHEN_MAPPING( some_container, some_concept2 )
MACRO_CALLED_INTERNALLY_WHEN_MAPPING( some_container, some_concept3 )

// At this point we have mapped 4 separate concepts to some_container
// Each concept map could appear at namespace scope anywhere in
// library or user files

////////////////////////////////////////

Finally, here is how everything comes together. Inside of the
BOOST_AUTO_FUNCTION with the "switch" parameter from the first example, we
extract a type that inherits from all of the concepts from which there are
concept maps for the given type by relying on the trick shown above. We then
use this type internally for tag dispatching. An example of what happens in
the innards of that first function template is this (again, this is all
hidden from the user and done automatically via the BOOST_AUTO_FUNCTION
macro invocation):

////////////////////////////////////////

  typedef decltype( concept_maps( identity< some_container >(), map_index<
top_index >() ) )
          concepts_maps_type;

  typedef decltype( type_with_a_nested_static_function(
concepts_maps_type::tag() ) )
          fun_holder;

  return fun_holder::impl( std::forward< It >( iterator ) );

////////////////////////////////////////

I hope this shows my point. Using this approach we should be able to nearly
fully simulate concept-based overloading for types with explicit concept
maps, having all tag dispatching done in a way that is transparent to the
user. With some effort, this approach could even be applied to variadic
function templates. I'm fairly certain that this is all standard, but there
may be the possibility for ODR violations... Another thing to consider is
perhaps to not use "identity" and instead use something like "type**" for
purposes of ADL.

Regardless, I'm confident that this approach or a variant could be used in
some way to get entirely library-based-concept-based overloads, unless
someone sees a big problem.

Finally, back on the topic of BOOST_AUTO_FUNCTION. At this point, conditions
not met causes substitution to fail, which is extremely useful, however, it
seems that many times you may want a static_assert instead. The SFINAE
version is useful when you have multiple overloads with mutually exclusive
conditions, whereas the static_assert version is good for a function
template where you have a top-level condition that must be met regardless of
overloads. For this reason, I'm likely going to add

(break if some_condition)

which will static_assert when the condition is met, having the text of the
condition in the static_assert message. Similar behavior would exist for
(break not some_condition). As a use-case, the first "foo" template (the one
with the switch) could have ( break not is_forward_iterator< It > ), which
would trigger a static_assert if you try to call it with something that
isn't an iterator at all.

Also, in case it isn't already apparent, the old use of "break" no longer
exists because of the design changes talked about earlier in the thread.
This would be a new use entirely.

-- 
-Matt Calabrese