views:

173

answers:

4

I'm porting over some code from one project to another within my company and I encountered a generic "sets_intersect" function that won't compile:

template<typename _InputIter1, typename _InputIter2, typename _Compare>
bool sets_intersect(_InputIter1 __first1, _InputIter1 __last1,
                    _InputIter2 __first2, _InputIter2 __last2,
                    _Compare __comp)
{
    // Standard library concept requirements
    // These statements confuse automatic indentation tools.
    // concept requirements
    __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
    __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
    __glibcpp_function_requires(_SameTypeConcept<
          typename iterator_traits<_InputIter1>::value_type,
          typename iterator_traits<_InputIter2>::value_type>)
    __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
          typename iterator_traits<_InputIter1>::value_type>)
    __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
          typename iterator_traits<_InputIter1>::value_type,
          typename iterator_traits<_InputIter2>::value_type>)

    while (__first1 != __last1 && __first2 != __last2)
    if (__comp(*__first1, *__first2))
            ++__first1;
    else if (__comp(*__first2, *__first1))
            ++__first2;
    else {
            return true;
    }
    return false;
}

I'm new to this concept of "concepts" (sorry for the pun), so I did some poking around in the c++ standard library and some googling and I can see that these __glibcpp_function_requires macros were changed to __glibcxx_function_requires. So that fixed my compiler error; however, since this is new to me, I'm curious about what this code is doing for me and I'm having trouble finding any documentation or decyphering the code in the library.

I'm assuming that the point of these macros is that when the compiler expands the templated function these will run some type checking at compile-time to see if the container being used is compatible with this algorithm. In other words, I'm assuming the first call is checking that _InputIter1 conforms to the _InputIteratorConcept. Am I just confused or am I on the right track? Also, why were the names of these macros changed in the c++ standard library?

+3  A: 

"Concepts" were a proposed feature for the next version of C++, but they were (relatively) recently voted out of the standard so won't resurface for quote some time now.

They were designed to allow early checking of requirements for template parameters and, amongst other things, would have enabled much more succinct error messages when a type that didn't meet the required constrains was used to instantiate a template.

2nd Edit: (see comments from dribeas and Jerry Coffin) These g++ macros are an internal concept checking mechanism and are not directly related to the proposed new language feature of the same name. As they are internal to g++ you can (and perhaps should) safely remove them without any loss of functionality in your function template.

Charles Bailey
I'm starting to read boost's explanations of concepts and see what you mean about the more clear compiler errors. However, this syntax differs significantly from boost; furthermore, you say this was rejected for the next version of C++, but it appears in concept_check.h in g++ versions 3.2.2 (with the __glipcpp naming) and version 4.1.1 (with the __glipcxx naming). Did GNU just decide to make it available even though it's not in the standard?
Mutmansky
Ideas about concepts are fairly old, there was a proposal to the standards committee in 2006 and "concept-g++" was an early implementation. I can't admit to following the history of the proposals in enough detail, so I don't when/how the macros developed in parallel with the standards proposals.
Charles Bailey
I doubt these depend on (much) compiler support -- my guess is that they're similar to the Boot concept check templates, and only need a reasonably conforming compiler to work (though I haven't checked).
Jerry Coffin
That type of 'concept' check is present in many versions of the STL distributed with gcc compilers, and is unrelated to concepts as proposed and not accepted to the upcoming standard. They are internal details of the STL and should not be used outside of STL (they are as private as they can be within a templated piece of code). In g++ 4.0 if you follow it through the implementation detail files it ends up in a file documented as based on boost concept check library version 1.12
David Rodríguez - dribeas
Rechecking... by default it is in fact an empty variadic macro, the boost version can be enabled by modifying c++config.h for the platform, or by defining _GLIBCXX_CONCEPT_CHECKS
David Rodríguez - dribeas
+1  A: 

You are correct, the first call is checking that _InputIter1 implements "input iterator" concept.

These macros are internal GLIBC implementation details (starting with an underscore or a double underscore), therefore GLIBC implementers are allowed to change them at will. They are not supposed to be used by user's code.

Since "concepts" are no longer the part of C++0x draft, in order to have portable concept checking, you should use some third-party library, like Boost Concept Check Library.

Alex B
I was also beginning to suspect that these should not really be used in user code, since all the examples I see in the boost documentation use macros like BOOST_CONCEPT_ASSERT or BOOST_CONCEPT_USAGE.
Mutmansky
In g++, those are macros that end up in either nothing (thanks to Charles I did check it) or in a call to an older version of the boost concept check library (1.12 as of g++ 4.0) if you configure or define _GLIBCXX_CONCEPT_CHECKS prior to STL header inclusion.
David Rodríguez - dribeas
A: 

As Charles already pointed out, direct support for concepts as part of C++ 0x was removed from the language relatively recently, and they almost certainly won't even be reconsidered until the next round of standardization. Hopefully by then there will be greater agreement on what they should really be/do.

A fair number of libraries attempt to provide similar capabilities though. Boost Concept Check Library is probably the most obvious, and I believe most of the others are based on it, at least in concept (if you'll pardon the pun). As to why the g++ guys decided to change from 'cxx' to 'cpp', I can't even begin to guess -- other than that they seem to think breaking backward compatibility as often as possible is a good thing (though these are really only intended for internal use, so changing the name shouldn't break much but their own code).

This is also fairly similar to the basic idea of what Andrei Alexandrescu presented in §2.1 of Modern C++ Design. If you want some idea of how to write concept checking of your own, you might want to read that (as well as §2.7, where he applies similar techniques to testing for convertibility and inheritance). While the concepts being checked varied, those do a good job of explaining most of the basic techniques, so:

  1. You stand a decent chance of reading and understanding concept-checking templates
  2. If you ever decide to write some of your own, you have a starting point

Edit: It's probably worth noting that the standard libraries for most current C++ compilers include at least some sort of concept-checking templates. Obviously gnu does. So does Comeau. In fact, the only one I can think of that doesn't seem to include any such thing anymore is MS VC++ (which uses the Dinkumware library). They've concentrated primarily on some (rather expensive) run-time debugging instead. This is also somewhat useful, but in an entirely different direction, and the two aren't mutually exclusive at all.

Jerry Coffin
Thanks. This really just piqued my curiosity as I don't generally follow developments in the standard library that closely. Hence why I was immediately aware of these being internal macros that should not be used anyway. Since I'm not the author of the code, I'm somewhat stuck just making it compile even though it should really be rewritten to not use these internal macros. It will take some political maneuvering to get it corrected.
Mutmansky
The easiest maneuver is just commenting the macros out. The second easiest maneuver is translating into the newer versions knowing that with any change of compiler version it can change and you will have to rework those same algorithms.
David Rodríguez - dribeas
Right. I've translated it to the newer versions, but I don't want to leave it like that permanently. This happens to be in one of the base include files that would be used in every project in our company and hence would be attempted to be compiled with multiple different compilers (dpending on what version/platform each project is on), so while I'm just the first to run into the compiler change headache, others will definitely run into it quickly.
Mutmansky
So I'll take some time analyzing how it's used (and I think your dead on in your answer above about what its intent is) and then see if it makes sense to just delete the macro calls or whether there's some alternative implementation that makes more sense and preserves the intended behavior.Thanks for all the feedback and answers.
Mutmansky
+1  A: 

There are two concept concepts (pun intended) around. The standard as it is being defined had a proposal for concepts as a standard language feature that would help in compilation and... there's quite a bit of literature around about C++0x concepts, discussions...

The other concept concept is the one you have just hit. The STL that is deployed with g++ implementations does have specific implementor checks that are also meant to aid in error detection. These are different to the previous concepts in that they are not a language feature and are not meant to be used by programmers, but rather they are used internally in the library. As the names are reserved (they begin with double underscore) the compiler/library implementor is free to add anything there as long as the behavior of the library does not differ from what the standard defines.

Going back to what you are doing: The code that you are trying to port to a newer compiler is a modified version of std::set_intersect as defined in the standard [lib.set.intersection] to return only whether they do intersect without having to parse the whole two ranges. I would either use the standard version and check that the output iterator was not modified, or if it is a performance issue, implement it without the concept checks, depending on non-standard hidden compiler defined symbols is asking for maintenance trouble when upgrading the compiler. But that you know already.

David Rodríguez - dribeas