On 03/04/2010 07:56 PM, Jeremiah Willcock wrote:

How are you ending up with std::string (or an std::list in the second error message) as an index map? What are you trying to call Dijkstra's algorithm on?

The minimal test case is actually only the two includes and nothing else. No code, nothing. Just includes. ----------------- $ cat inc_test.cc #include <boost/graph/dijkstra_shortest_paths.hpp> #include <boost/spirit/include/qi.hpp> $ /usr/bin/g++ -c inc_test.cc In file included from /usr/include/boost/graph/properties.hpp:19,

from /usr/include/boost/graph/named_function_params.hpp:13, from /usr/include/boost/graph/dijkstra_shortest_paths.hpp:20, from inc_test.cc:1: /usr/include/boost/property_map/property_map.hpp: In instantiation of ‘boost::property_traits<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >’: /usr/include/boost/graph/two_bit_color_map.hpp:47: instantiated from ‘boost::two_bit_color_map<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >’ /usr/include/boost/spirit/home/qi/char/char.hpp:206: instantiated from here /usr/include/boost/property_map/property_map.hpp:31: error: no type named ‘key_type’ in ‘struct std::basic_string<char, std::char_traits<char>, std::allocator<char> >’ /usr/include/boost/property_map/property_map.hpp:34: error: no type named ‘category’ in ‘struct std::basic_string<char, std::char_traits<char>, std::allocator<char> >’ /usr/include/boost/property_map/property_map.hpp: In instantiation of ‘boost::property_traits<std::list<boost::spirit::info, std::allocator<boost::spirit::info> > >’: /usr/include/boost/graph/two_bit_color_map.hpp:47: instantiated from ‘boost::two_bit_color_map<std::list<boost::spirit::info, std::allocator<boost::spirit::info> > >’ /usr/include/boost/spirit/home/support/detail/what_function.hpp:35: instantiated from here /usr/include/boost/property_map/property_map.hpp:31: error: no type named ‘key_type’ in ‘class std::list<boost::spirit::info, std::allocator<boost::spirit::info> >’ /usr/include/boost/property_map/property_map.hpp:34: error: no type named ‘category’ in ‘class std::list<boost::spirit::info, std::allocator<boost::spirit::info> >’

$ ----------------- BTW, I noticed that if I change the order of the includes everything compiles fine. There's something really weird going on. -- Maxime

On 03/04/2010 08:06 PM, Jeremiah Willcock wrote:

This is the same issue as variant actually -- the boost::get thing. The info object that is causing trouble in char.hpp contains a variant that it's trying to get a field from. It's too bad that a later library (variant) reused a name from an earlier one (graph), but it's probably too late to do anything about either one.

This seems quite critical to me. As the times goes, more and more boost libraries might use variant and therefore become incompatible with Boost.Graph. Wouldn't it be better to break backward compatibility for a given release and solve this issue ? The backward compatibility is already broken : our codebase compiles fine in Boost 1.39 and doesn't in Boost 1.41 because of this issue. -- Maxime

On Thu, Mar 4, 2010 at 1:21 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

On Thu, 4 Mar 2010, Maxime van Noppen wrote:

On 03/04/2010 08:06 PM, Jeremiah Willcock wrote:

...

...

This is the same issue as variant actually -- the boost::get thing. The info object that is causing trouble in char.hpp contains a variant that it's trying to get a field from. It's too bad that a later library (variant) reused a name from an earlier one (graph), but it's probably too late to do anything about either one.

This seems quite critical to me. As the times goes, more and more boost libraries might use variant and therefore become incompatible with Boost.Graph. Wouldn't it be better to break backward compatibility for a given release and solve this issue ? The backward compatibility is already broken : our codebase compiles fine in Boost 1.39 and doesn't in Boost 1.41 because of this issue.

I guess I don't know how many programs use boost::get from BGL as opposed to just get. Users are supposed to use ADL to find get, at least in generic code, but it would still have to be in boost because that's where the graph types are. Remember that BGL's get is part of a concept so it needs to be accessible using an unqualified name when called on a built-in graph type. I don't see any obviously good ways to do this -- changing Variant would break more code but the fix would be simpler (since it's probably just a search-and-replace for boost::get< and get< since people won't use those syntaxes with BGL). For BGL, it might be possible to move the built-in property names (and references to them would need to be fixed up), but that's a hack just to get an additional associated namespace for the built-in definitions of get(). The other fix would be to move the graph types, but that would require user code changes as well; there would also need to be a rule that graph types could not go in boost:: anymore. I added [variant] into the subject line so we can get the Variant developers in here and try to get this worked out -- it is going to be an increasing problem as you said.

Frankly I have always thought boost::get is a terrible name. Such a generic name for a free function is practically inviting trouble. Zach

On Thu, 4 Mar 2010, Steven Watanabe wrote:

AMDG

Jeremiah Willcock wrote:

...

I guess I don't know how many programs use boost::get from BGL as opposed to just get. Users are supposed to use ADL to find get, at least in generic code, but it would still have to be in boost because that's where the graph types are. Remember that BGL's get is part of a concept so it needs to be accessible using an unqualified name when called on a built-in graph type. I don't see any obviously good ways to do this -- changing Variant would break more code but the fix would be simpler (since it's probably just a search-and-replace for boost::get< and get< since people won't use those syntaxes with BGL). For BGL, it might be possible to move the built-in property names (and references to them would need to be fixed up), but that's a hack just to get an additional associated namespace for the built-in definitions of get(). The other fix would be to move the graph types, but that would require user code changes as well; there would also need to be a rule that graph types could not go in boost:: anymore. I added [variant] into the subject line so we can get the Variant developers in here and try to get this worked out -- it is going to be an increasing problem as you said.

Do you know which BGL overload of get is triggering this? IMHO, the graph library should not globally reserve a common name like get. Variant's overloads are well behaved, (they should never match anything except a variant and will not cause an error when they don't match.)

There are a lot of BGL overloads of get; it is intended to be found by ADL, and there's (at least) one definition for each graph type. The graph library's get has been around for a while. It is not globally reserved, at least not technically; it only applies to known graph and property map types, just like variant's. The problem is that variant's get takes explicit template arguments and that seems to make the overloading work incorrectly. I suspect that the error in this thread, for example, is coming from the boost::get version for two_bit_color_map; that function is restricted to work on only that property map type but instantiating its signature appears to be failing without SFINAE because of the explicit template argument. I think this is something that's fixed in C++0x but that doesn't help us now. Your workaround might fix the common cases though (since the compiler seems to differentiate functions based on the number of template arguments given); for some reason, the extra template argument in ::key_type is important in that definition of get. It will be annoying to have to work around this issue repeatedly, though. -- Jeremiah Willcock

On Thu, 4 Mar 2010, Steven Watanabe wrote:

AMDG

Jeremiah Willcock wrote:

...

There are a lot of BGL overloads of get; it is intended to be found by ADL, and there's (at least) one definition for each graph type. The graph library's get has been around for a while. It is not globally reserved, at least not technically; it only applies to known graph and property map types, just like variant's. The problem is that variant's get takes explicit template arguments and that seems to make the overloading work incorrectly. I suspect that the error in this thread, for example, is coming from the boost::get version for two_bit_color_map; that function is restricted to work on only that property map type but instantiating its signature appears to be failing without SFINAE because of the explicit template argument.

SFINAE doesn't apply for this overload of get.

OK -- I see that it's really the reference to the member type key_type that's causing the class to be instantiated, which is not a SFINAE error.

...

I think this is something that's fixed in C++0x but that doesn't help us now. Your workaround might fix the common cases though (since the compiler seems to differentiate functions based on the number of template arguments given); for some reason, the extra template argument in ::key_type is important in that definition of get. It will be annoying to have to work around this issue repeatedly, though.

Property maps that use put_get_helper seem to be okay.

Yes -- that uses two template parameters. There are only a few other places that need to be changed: one_bit_color_map.hpp (a copy of the two-bit one) csr_vertex_local_map in distributed/compressed_sparse_row_graph.hpp the Stanford GraphBase interface A few property maps in distributed/adjacency_list.hpp Should I just go ahead and do those? I do not know if your key_type thing will work in some of the other places -- the compiler seems sensitive to that. -- Jeremiah Willcock

On Thu, 4 Mar 2010, Steven Watanabe wrote:

Jeremiah Willcock wrote:

...

On Thu, 4 Mar 2010, Steven Watanabe wrote:

...

AMDG

Jeremiah Willcock wrote:

...

There are a lot of BGL overloads of get; it is intended to be found by ADL, and there's (at least) one definition for each graph type. The graph library's get has been around for a while. It is not globally reserved, at least not technically; it only applies to known graph and property map types, just like variant's. The problem is that variant's get takes explicit template arguments and that seems to make the overloading work incorrectly. I suspect that the error in this thread, for example, is coming from the boost::get version for two_bit_color_map; that function is restricted to work on only that property map type but instantiating its signature appears to be failing without SFINAE because of the explicit template argument.

SFINAE doesn't apply for this overload of get.

OK -- I see that it's really the reference to the member type key_type that's causing the class to be instantiated, which is not a SFINAE error.

...

...

I think this is something that's fixed in C++0x but that doesn't help us now. Your workaround might fix the common cases though (since the compiler seems to differentiate functions based on the number of template arguments given); for some reason, the extra template argument in ::key_type is important in that definition of get. It will be annoying to have to work around this issue repeatedly, though.

Property maps that use put_get_helper seem to be okay.

Yes -- that uses two template parameters.

Actually with template <class PropertyMap, class Reference, class K> inline Reference get(const put_get_helper<Reference, PropertyMap>& pa, const K& k) You should never get an error, since there are no templates that the compiler could errantly try to instantiate.

Yes -- I think the member type is the issue.

...

There are only a few other places that need to be changed:

one_bit_color_map.hpp (a copy of the two-bit one) csr_vertex_local_map in distributed/compressed_sparse_row_graph.hpp the Stanford GraphBase interface A few property maps in distributed/adjacency_list.hpp

Should I just go ahead and do those? I do not know if your key_type thing will work in some of the other places -- the compiler seems sensitive to that.

I'm somewhat nervous about my patch, since it was just a quick hack to see what was possible. I'd much rather adjust the definition of get so that it can't cause an error just by being the the overload set.

I looked at changing the key_type in get to something that would SFINAE out and there isn't one: the farthest I could go is property_traits<IndexMap>::value_type (key_type in the code is a bug), and that class will fail to instantiate (non-SFINAE) on bad index map types. That can be specialized, so I can't fall back to the default definition of value_type inside it. I don't see a general-purpose solution to problem right now. -- Jeremiah Willcock

On Thu, 4 Mar 2010, Steven Watanabe wrote:

AMDG

Jeremiah Willcock wrote:

...

I looked at changing the key_type in get to something that would SFINAE out and there isn't one: the farthest I could go is property_traits<IndexMap>::value_type (key_type in the code is a bug), and that class will fail to instantiate (non-SFINAE) on bad index map types. That can be specialized, so I can't fall back to the default definition of value_type inside it. I don't see a general-purpose solution to problem right now.

Would this break anything?

template<typename PA> struct property_traits : PA {};

That plus changing two_bit_property_map to use it passes the BGL, PBGL, and property_map test cases. Does it work to fix all of the known variant problems? -- Jeremiah Willcock

I thought at first that it would, but unfortunately not. Suppose that the argument is a built-in type...

So, here's try #2 at making property_traits usable for SFINAE (untested).

I did some little fixes to this (patch to trunk version of property_map.hpp attached) and it again passes the graph, graph_parallel, and property_map test cases. Could you please try it again with the variant bug cases?

The other alternative is to make the second argument of get fully generic. This will guarantee it against errors, but the downside is that it will match too much.

I don't like that because get is actually used for two things in BGL: for getting values from a property map, and for getting property maps out of a graph. Making it fully general would lead to poorer error detection and likely ambiguities between the two uses (there are already some versions whose first parameter is fully generic). -- Jeremiah Willcock

On Mon, 8 Mar 2010, Steven Watanabe wrote:

AMDG

Jeremiah Willcock wrote:

...

...

I thought at first that it would, but unfortunately not. Suppose that the argument is a built-in type...

So, here's try #2 at making property_traits usable for SFINAE (untested).

I did some little fixes to this (patch to trunk version of property_map.hpp attached) and it again passes the graph, graph_parallel, and property_map test cases. Could you please try it again with the variant bug cases?

The following tests both compile after I updated two_bit_color_map.hpp to use SFINAE on property_traits.

#include <boost/graph/two_bit_color_map.hpp> #include <boost/variant.hpp>

int test1() { using namespace boost; boost::variant<int, char> v; int i = get<int>(v); }

// make sure that it works even with incomplete types struct S;

typedef boost::variant<boost::recursive_wrapper<S> > v_type;

void test2(v_type& v) { boost::get<S>(&v); }

Could you please also test the include_test.cpp that got this thread started? If that passes I'll commit the change and see if the regression tests break (since there might be compiler compatibility issues). Thank you. -- Jeremiah Willcock

On Mon, 8 Mar 2010, Steven Watanabe wrote:

AMDG

Jeremiah Willcock wrote:

...

Could you please also test the include_test.cpp that got this thread started? If that passes I'll commit the change and see if the regression tests break (since there might be compiler compatibility issues). Thank you.

Yes, it passes with

...

g++ --version g++ (TDM-1 mingw32) 4.4.1 Copyright (C) 2009 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

(I checked that it fails without the patch, too)

It's in trunk now. I couldn't completely test it because Serialization is broken right now, but it passes all of the BGL and property map test cases that don't use serialization. -- Jeremiah Willcock