[boost] Provisional Boost.Generic and Boost.Auto_Function (concepts without concepts)

Subject: [boost] Provisional Boost.Generic and Boost.Auto_Function (concepts without concepts)
From: Matt Calabrese (rivorus_at_[hidden])
Date: 2010-11-13 17:15:27

For those of you who were following the Boost.Auto_Function call for
interest, this thread sort of spawned off of that.

Boost.Generic (not a part of boost) is a C++0x library intended to replace
BCCL as a way of specifying concepts and concept maps, and, when used in
conjunction with Boost.Auto_Function (also not a part of boost, though it's
in the sandbox and has online documentation at
http://www.rivorus.com/auto_function ) as a way to get concept-based
function template overloading. For anyone who followed the original thread,
I'm happy to say that I'm just a few days away from being able to fully and
automatically recognize standard library and user-defined iterator types,
though I've had a [not so] surprising amount of compiler crashes and
workarounds along the way. For an example of how concept mapping will look
(revised from earlier versions as I've made much more progress with
implementation), see http://codepaste.net/n47ocu And for an example of how
this will be used by Boost.Auto_Function, see http://codepaste.net/1faj21 .
At this point I'm not trying to do the equivalent of what would have been
C++0x "scoped" concept maps, though at some point I may try to support them,
but it would imply calling algorithms through macro invocations (yuck).

During development, I've come to some realizations that I'd like discussion
about here, mostly concerning concept map lookup and ODR. Essentially, the
way the library works is by assembling a compile-time list of concept maps
piecewise throughout a translation unit for a given type or combination of
types via a clever use of overload resolution that I talked about briefly in
the BOOST_AUTO_FUNCTION call for interest thread. Underneath the hood, there
is something that resembles tag-dispatching, however it is all done entirely
within decltype. In short, the way the concept-based overloading works is
that the macro used for specifying a function that dispatches based on
concept maps generates something along the lines of this. The "magic" shown
in comments is something I'm able to already do, as talked about in the
other thread:

/////
template< class It >
void foo( It&& it )
{
  typedef decltype
          ( function_returning_type_with_a_nested_static_function
            ( /* magical way to get a type that inherits from all concept
tags */() )
          )
          fun_holder;

  fun_holder::impl( std::forward< It >( it ) );
}
/////

Now, this is great, but I'm wondering what this means with respect to ODR.
If the user is working with the algorithm "correctly", the typedef will
resolve to the same type regardless of the translation unit, however, the
"path" taken when inside of the decltype via overload resolution may vary
depending on the translation unit when different, orthogonal concept maps
are specified for the same type in one translation unit but not in the other
(or if concept maps are specified in a different order I.E. via different
#include orders). My question is, does this violate ODR in any meaningful
sense? Since technically the typedefs should resolve to the same type in
each translation unit, not including user error, is there a problem?

The next question is much more devious and I have a feeling implies a
blatant violation of ODR.

Consider the following code, assuming "foo" does concept-based dispatching
in a way similar to the above:

/////
foo( 5 );

/* a concept map that specifies "int" models a concept that may affect
dispatching */

foo( 5 );
/////

With the definition of foo given above, what would effectively happen is
that the second call to "foo" will not be able to dispatch based on the new
concept map! The reason why is because both calls will use foo< int >, and
since it was already instantiated once for int, that first definition will
be used. Note that this problem technically even exists with traditional tag
dispatch, though I wonder if there may be some sort of solution that is
standard.

A hackish workaround I've come up for this is if we change the defintion of
"foo" to be generated as the following:

/////
// Uses C++0x function template default arguments
template< class It, class TagType = /* magical way to get a type that
inherits from all concept tags */ >
void foo( It&& it )
{
  typedef decltype
          ( function_returning_type_with_a_nested_static_function
            ( TagType() )
          )
          fun_holder;

  fun_holder::impl( std::forward< It >( it ) );
}
/////

Going back to the example calling code, "foo" will now correctly dispatch
differently if the intermediate concept map should affect concept-based
dispatch. This might seem like a perfect solution, but now we are pretty
much definitely violating ODR, since a function that calls "foo" in
different translation units will very possibly see different TagTypes even
though the overload resolution internal to "foo" would resolve the same.

Am I clear on this problem and why I believe my solution only works if you
don't consider ODR violations?

The final solution that I believe sidesteps all ODR violations would be if I
force calls to such algorithms to be done via a macro. The macro would
internally do the trick that is currently shown inside of the definition of
"foo", only it would now do it at the caller's scope. If I decide to
eventually try to support scoped concept maps I would be forced down such a
route anyway, so my question ends up being at what point does the library
cease being a convenience? Is it worth supporting concepts as accurately as
possible, including the above desired behavior, if the calling code has to
become:

/////
BOOST_GENERIC_CALL( (foo)( 5 ) );

/* a concept map that specifies "int" models a concept that may affect
dispatching */

BOOST_GENERIC_CALL( (foo)( 5 ) );
/////

or, if you want a more practical example:

/////
BOOST_GENERIC_CALL( (advance)( vector_.begin(), 5 ) );
/////

This is a problem that I would prefer to be resolved sooner rather than
later since I want to reduce code rewrites. Any feedback is greatly
appreciated, especially if you have insight into these problems.

I'll try to get Boost.Generic in its current, very limited form up on the
sandbox and the docs online as soon as possible.

-- 
-Matt Calabrese