Hi Matt, I apologize if this response took a while, I got buried into a few things that needed my immediate attention and almost missed replying to this email of yours. That said, please see some of my thoughts in-lined below. On Sun, Nov 14, 2010 at 6:15 AM, Matt Calabrese <rivorus@gmail.com> wrote:
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).
Interesting! So which compilers are you using to test your implementation? Is this with MSVC or GCC?
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?
I don't see an obvious problem here in terms of ODR here because you are using a template -- which by definition still gets instantiated anyway across multiple translation units, and is not required to have a single definition anyway. The only worrying thing is that if the nested function invocation referred to has a static but non-extern linkage, and thus will be defined in multiple translation units -- some compilers issue a diagnostic on this occurrence although I forget if the standard requires that a diagnostic be emitted in cases where you have nested static functions in templates. Maybe those who actually know enough about the relevant sections of the standard can chime in.
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.
Note that your concept map is computed at "compile-time" right, and should be in a globally accessible scope -- i.e. a template specialization or a template class in a namespace -- right? Unless you're able to create a concept map at runtime or call the foo function outside of a function body, then I don't see how adding a new concept_map might be an issue for ODR. Of course unless you're talking about invocations of foo<...> on multiple translation units where you have one translation unit already defining the concept map and the others having a different set of concept maps. In which case you will get around that by marking foo<...> as an inline function, thus allowing multiple definitions across translation units be acceptable. I'm not sure if that's what you're looking for or asking, and if I'm not making sense please enlighten me more as to what your concern actually is. ;)
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?
Like I already mentioned above, if `function_returning_type_with_a_nested_static_function` is a template, and the static function is defined in-line, I don't think you'll run into ODR violations here. If you're worried of the foo function being defined differently across multiple translation units, then that's fine because that is the nature of templates AFAIK. ;)
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.
I don't like the idea with making function calls macro functions. Unless I'm missing what you're saying above with ODR violations, I don't see them at all, granted that templates in general are instantiated per translation unit, and that you'll find ODR in cases where you have statics defined in multiple TU's that either differ or are exposed through a non-template class. Maybe looking at how Phoenix gets around the ODR issue might help -- I've never found any problems with the way Phoenix actors have static nested functions in templates, and I've never had compilers complain of ODR in those cases either. HTH -- Dean Michael Berris deanberris.com