Eric Niebler wrote:

Actually, I seem to recall reading about this problem (there might even be a defect report already). If anybody can refresh my memory, I'd appreciate it.

It may be related to the problem reported here: http://lists.boost.org/MailArchives/boost/msg76861.php Jonathan

Arkadiy Vertleyb wrote:

...

Eelis van der Weegen wrote:

...

I'm having trouble using BOOST_FOREACH to iterate over Boost.MultiIndex containers. I've attached a testcase, which fails to compile because of what looks like an ADL collision between range_iterator's end() and boost::mpl::end.

It appears to be the same problem that I ran into a few month ago...

This is a combination of two problems with GCC:

1) GCC STL uses unqualified function calls to its own functions, such as end() in this particular case; 2) GCC ADL finds class names along with function names.

So, if an STL algorithm is used with a sequence whose value_type has anything related to boost::mpl namespace, and this algorithm uses unqualified call, and the appropriate MPL header is included, then the problem shows up.

I think GCC people are fixing number 1 (which will make the problem go away), but I don't know if they are done yet (apparently not).

Sounds like the problem is not in STL but in GCC's implementation of ADL, which is finding class names. In this case, the collision isn't in STL, it is a collision of end() from Boost.Range and end<> from MPL. Changing the STL implementation will *not* fix this problem. My understanding of ADL is that it should be used to locate *function* overloads. It is meaningless to find class names using ADL. Until gcc's rules for ADL are fixed, this problem will persist. -- Eric Niebler Boost Consulting www.boost-consulting.com

Arkadiy Vertleyb wrote:

The GCC's ADL is sure broken, but this only shows up in combination with another problem -- unqualified calls. Just fixing ADL would not solve the problem -- MPL is free to have a *function* called end(). In this particular case the Boost.Range needs to be fixed to avoid unqualified calls, IMO.

I believe Thorsten deliberately wanted to allow unqualified calls. Jonathan

Jonathan Turkanis wrote:

Arkadiy Vertleyb wrote:

...

In this particular case the Boost.Range needs to be fixed to avoid unqualified calls, IMO.

I believe Thorsten deliberately wanted to allow unqualified calls.

Yes, Boost.Range is designed that way. It is an extensible design -- you can range-ify your own type by defining your own begin() and end() and letting ADL find them. So it seems there is no simple work-around for GCC's bizarre ADL rules in this case. We'll need to think of something else. -- Eric Niebler Boost Consulting www.boost-consulting.com

"Arkadiy Vertleyb" wrote in message news:d05g68$qqu$1@sea.gmane.org... | "Eric Niebler" wrote | | > Jonathan Turkanis wrote: | > > Arkadiy Vertleyb wrote: | > > | > >>In this particular case the Boost.Range needs to be fixed to avoid | > >>unqualified calls, IMO. | > > | > > I believe Thorsten deliberately wanted to allow unqualified calls. | > | > Yes, Boost.Range is designed that way. It is an extensible design -- you | > can range-ify your own type by defining your own begin() and end() and | > letting ADL find them. So it seems there is no simple work-around for | > GCC's bizarre ADL rules in this case. We'll need to think of something | else. | | Well, then I hate to say this, but IMHO this is a problem in the Boost.Range | design :-( It is deliberate design. All generic code that uses boost.range should use unqualified calls to enable ADL. <aside> It is possible to imagine alternative designs where all calls to end(c) can be made qualified and still enable ADL; however, it requires the unqulified call of another function inside boost::end(c) , say adl_end(c), to enable ADL of that function. </aside> | I am not really that familiar with this library, but I assume it has to do | with containers, correct? Assume the following usage (pseudocode) | | Range(std::vector > > ) | | Now ADL will use std, boost, MyNamespace, boost::multi_index, and boost::mpl | to find Range. There is absolutely no guarantee that it won't find | conflicting functions :-( I don't get this. Surely one of the functions would be a better match than the others and hence called. -Thorsten

"Jonathan Turkanis" wrote in message news:d088s0$294$1@sea.gmane.org... | Thorsten Ottosen wrote: | > "Arkadiy Vertleyb" wrote in message | | >> I am not really that familiar with this library, but I assume it has | >> to do with containers, correct? Assume the following usage | >> (pseudocode) | >> | >> Range(std::vector> ector> > > ) | >> | >> Now ADL will use std, boost, MyNamespace, boost::multi_index, and | >> boost::mpl to find Range. There is absolutely no guarantee that it | >> won't find conflicting functions :-( | > | > I don't get this. Surely one of the functions would be a better match | > than the others and hence called. | | I think Arkadiy might mean that the wrong function could be selected; however, | the class author should be able to figure this out. I don't get that either :-) | Would it be possible to indroduce an extra level of indirection so that Range | can be used with a type even if there are preexisting begin/end/.. functions | that do the wrong thing? For instance, | | template<typename T> | struct begin_impl { | typename range_iterator<T>::type | begin( T& c ) { return adl_begin(c); } | | typename range_const_iterator<T>::type | begin( const T& c ) { return adl_begin(c); } | }; | | template< class T > | typename range_iterator<T>::type | begin( T& c ) | { | return begin_impl<T>::begin(c); | } | | template< class T > | typename range_const_iterator<T>::type | begin( const T& c ) | { | return begin_impl<T>::begin(c); | } | | Then as a last resort someone could specialize begin_impl. I was thinking of something like that too. May I ask why you want the functions inside a class (partial specialization doesn't seem to be needed very frequently, does it)? I would rather a protocol like this was made: template< class T > typename range_iterator<T>::type begin( T& r ) { return adl_begin(r); } | Or is something like | this already possible? no. -Thorsten

"Thorsten Ottosen" writes:

"Arkadiy Vertleyb" wrote in message news:d05g68$qqu$1@sea.gmane.org... | "Eric Niebler" wrote | | > Jonathan Turkanis wrote: | > Yes, Boost.Range is designed that way. It is an extensible design -- you | > can range-ify your own type by defining your own begin() and end() and | > letting ADL find them. So it seems there is no simple work-around for | > GCC's bizarre ADL rules in this case. We'll need to think of something | else. | | Well, then I hate to say this, but IMHO this is a problem in the Boost.Range | design :-(

It is deliberate design.

It might still be a design mistake.

All generic code that uses boost.range should use unqualified calls to enable ADL.

<aside> It is possible to imagine alternative designs where all calls to end(c) can be made qualified and still enable ADL; however, it requires the unqulified call of another function inside boost::end(c) , say adl_end(c), to enable ADL of that function. </aside>

ADL might not be the best customization solution. Problems with ADL are well-known, and there are other mechanisms; in this case static member functions of a class template specialization might have been better... especially since you can't stick overloads in std. For example: namespace boost { namespace ranges { template <class Range> struct traits; template <class Range> typename traits<Range>::iterator begin(Range& r) { return traits<Range>::begin(r); }; // ... etc... }}

| I am not really that familiar with this library, but I assume it has to do | with containers, correct? Assume the following usage (pseudocode) | | Range(std::vector > > ) | | Now ADL will use std, boost, MyNamespace, boost::multi_index, and boost::mpl | to find Range. There is absolutely no guarantee that it won't find | conflicting functions :-(

I don't get this. Surely one of the functions would be a better match than the others and hence called.

The problem is that controlling which is the best match is sometimes very difficult. Sometimes the best match doesn't get called. Sometimes there is ambiguity. ADL is a very blunt instrument. -- Dave Abrahams Boost Consulting www.boost-consulting.com

"Thorsten Ottosen" writes:

"David Abrahams" wrote in message news:uacpk414w.fsf@boost-consulting.com...

| The problem is that controlling which is the best match is sometimes | very difficult. Sometimes the best match doesn't get called.

then how can it be the best match then?

Sorry, I mean "best" from a human point-of-view. I mean, "the one you want."

| Sometimes there is ambiguity. ADL is a very blunt instrument.

If the implementation was to use a class template, what would be preffered naming?

I don't know; the one I posted might be fine.

Would you want one big fat class with all the functions?

Or would you like a class for each function, say for end(), std::end_impl<T>?

I *think* that for the purpose of adapting a type to meet a concept, a fat class is probably the best way. Granularity is really most important at the interface level, so users call boost::ranges::begin(s) rather than something like boost::ranges::traits<X>::begin(s) -- Dave Abrahams Boost Consulting www.boost-consulting.com

"Peter Dimov" writes:

David Abrahams wrote:

...

ADL might not be the best customization solution.

You keep saying that, but I keep disagreeing. ADL is the best customization solution. Not flawless, just better than any of the alternatives.

I guess I haven't seen enough be definitively convinced one way or the other. I have heard stories from people who switch to dispatching via specialization and report how much better things get. Furthermore, Daveed Vandevoorde has convinced me that it is far easier to reason about. The rules for matching partial specializations are trivial compared to the mess you have to consider when there is overloading. The inconvenience of specialization is ugly, but it seems like a one-time cost that may be justified for what it buys us. Are there any other costs to the specialization approach? -- Dave Abrahams Boost Consulting www.boost-consulting.com

"Peter Dimov" writes:

David Abrahams wrote:

...

"Peter Dimov" writes:

...

David Abrahams wrote:

...

ADL might not be the best customization solution.

You keep saying that, but I keep disagreeing. ADL is the best customization solution. Not flawless, just better than any of the alternatives.

I guess I haven't seen enough be definitively convinced one way or the other. I have heard stories from people who switch to dispatching via specialization and report how much better things get. Furthermore, Daveed Vandevoorde has convinced me that it is far easier to reason about. The rules for matching partial specializations are trivial compared to the mess you have to consider when there is overloading. The inconvenience of specialization is ugly, but it seems like a one-time cost that may be justified for what it buys us.

That's the thing. It doesn't actually buy us anything.

- Simpler matching rules - Customizability for built-in types - Code is explicit about what operation it's customizing and what operation it's calling. - A few more, but you're disputing them below...

It only claims to avoid potential problems.

* Uglier syntax for defining a specialization.

* Coupling; you need to include a primary template.

* Does not allow a base-specific version to be picked up automatically for derived classes.

* Does not allow non-exact matches.

* If four libraries need the same operation, you need to specialize four primary templates.

If four libraries happen to specify the exact same name and semantics for something, I'd say it's a well-known standard and _maybe_ you should have been using ADL in the first place. But in general, the chance of that happening is infinitesimal. Where there are function name collisions, the likelihood is that requirements will be similar, but not identical.

In practice people tend to respect de-facto standards; a + b is an addition, and swap(a, b) swaps a and b. The main fight is over who gets to keep the primary template.

No, the problem is what happens when you have no de-facto standard. Customizable interfaces get invented, and when they do, they are just some new thing. Everybody wants to think that they will invent the de-facto standard use for a name, but sometimes these things collide. Just look at _1, _2, et. al.

But this is not really a problem with ADL customization points, because in their purest form, there is no primary template. The primary template is usually a compatibility workaround for types that do not support the ADL interface yet.

I think you're being just a tiny bit too sanguine here. There are layers of concepts that need to be built upon commonly-used types, and there's a great danger that different libraries will pick the same simple names for different operations in their own domains. Just consider the widespread use of numeric types in all kinds of domain-specific applications. Is every library going to pick the same meaning for zero(x) ?? -- Dave Abrahams Boost Consulting www.boost-consulting.com

Peter Dimov wrote:

David Abrahams wrote:

...

"Peter Dimov" writes:

...

That's the thing. It doesn't actually buy us anything.

- Simpler matching rules - Customizability for built-in types - Code is explicit about what operation it's customizing and what operation it's calling. - A few more, but you're disputing them below...

Customizability for built-in types, agreed. I don't really see the inherent value in the others. They seem like circular reasoning to me. The overload resolution rules are complex for a reason; if we could use something simpler instead, we would.

I'm not sure. IIUC, for such library customization points the important thing is not the ADL, but 2-phase name lookup. If you could restrict name lookup to a particular namespace during template instantiation, that may well be a solution - just make the name visible in the namespace that the library requires. But the way name lookup works, to get lookup at the point of instantiation you must use an unqualified name, which gives you ADL as well. Is it really essential that these notations are coupled in this way?

...

...

In practice people tend to respect de-facto standards; a + b is an addition, and swap(a, b) swaps a and b. The main fight is over who gets to keep the primary template.

No, the problem is what happens when you have no de-facto standard. Customizable interfaces get invented, and when they do, they are just some new thing. Everybody wants to think that they will invent the de-facto standard use for a name, but sometimes these things collide. Just look at _1, _2, et. al.

Right. And if they did not collide, nothing would become a de-facto standard, because people could keep using their own versions. There would be no pressure to resolve these collisions.

So even on boost, such collisions occur - what about libraries that are developed completely independently? Which politburo is to decide how each name is supposed to be used? How is it to be enforced? And wern't namespaces supposed to solve these issues anyway?

...

...

But this is not really a problem with ADL customization points, because in their purest form, there is no primary template. The primary template is usually a compatibility workaround for types that do not support the ADL interface yet.

I think you're being just a tiny bit too sanguine here. There are layers of concepts that need to be built upon commonly-used types, and there's a great danger that different libraries will pick the same simple names for different operations in their own domains. Just consider the widespread use of numeric types in all kinds of domain-specific applications. Is every library going to pick the same meaning for

zero(x)

??

Yes, I hope so. I also hope that they would pick the same meaning for x+y.

Ok, quick (but serious) question: What are the semantics of zero(x) ? Cheers, Ian

"Peter Dimov" writes:

Ian McCulloch wrote:

...

Peter Dimov wrote:

...

Right. And if they did not collide, nothing would become a de-facto standard, because people could keep using their own versions. There would be no pressure to resolve these collisions.

So even on boost, such collisions occur - what about libraries that are developed completely independently? Which politburo is to decide how each name is supposed to be used? How is it to be enforced?

It is unenforceable, of course. But this doesn't mean that it can't happen. Library authors are, in general, reasonable people; they do cooperate and do respond to issues.

I don't know about that. The various placeholders in Boost still have usability problems when #included together. And the bind placeholders are still causing ODR violations. It's all very well that library writers may adjust eventually, but users can't always upgrade, or they can't always upgrade quickly. There ought to be a mechanism for staying out of one another's way.

This isn't really specific to ADL customization points. Consider, for example, container requirements, where a.begin() must return A::iterator or A::const_iterator. What happens if another library has its own requirements table that specifies different semantics for a.begin()? Can I make my container conform to these requirements as well? Of course not.

That's why generic library writers have developed a guideline to write concept requirements that don't depend on member functions.

...

And wern't namespaces supposed to solve these issues anyway?

The central question is: can we, the C++ community, decide on a common vocabulary for the primitive operations a type supports? If we can, there is no problem.

I disagree most strongly. One problem is that not all operations are going to be considered "primitive." More importantly, there should be a way to develop software with confidence that it has a future and scales well, without having to worry that all customizable names are "pending the community's verdict on common meaning."

Namespaces do not address this issue.

Because of ADL.

They are a way to partition identifiers that belong to a specific library. Inter-library communication, by its nature, touches two or more different namespaces. No library "owns" swap, or operator+.

It would be much better if every one of those was "owned" by a library -- if only we had the language mechanisms to make it work. When these things become part of the "common vocabulary" they can be added to the common list of using-declarations and used without qualification. Of course operator+ (the one that adds, and the one that concatenates strings) would have been in the common list from the get-go, and we'd have put swap there by now too.

...

...

...

Just consider the widespread use of numeric types in all kinds of domain-specific applications. Is every library going to pick the same meaning for

zero(x)

??

Yes, I hope so. I also hope that they would pick the same meaning for x+y.

Ok, quick (but serious) question: What are the semantics of zero(x) ?

I don't know; this is Dave's example. Whatever the community decides, as long as it's consistent. The user should learn what it means _once_.

It could take many years for a name like that to settle down, especially if two major libraries with strong user base and backward-compatibility considerations pick competing definitions. -- Dave Abrahams Boost Consulting www.boost-consulting.com

"Peter Dimov" writes:

David Abrahams wrote:

...

"Peter Dimov" writes:

...

Ian McCulloch wrote:

...

Peter Dimov wrote:

...

Right. And if they did not collide, nothing would become a de-facto standard, because people could keep using their own versions. There would be no pressure to resolve these collisions.

So even on boost, such collisions occur - what about libraries that are developed completely independently? Which politburo is to decide how each name is supposed to be used? How is it to be enforced?

It is unenforceable, of course. But this doesn't mean that it can't happen. Library authors are, in general, reasonable people; they do cooperate and do respond to issues.

I don't know about that. The various placeholders in Boost still have usability problems when #included together. And the bind placeholders are still causing ODR violations.

The placeholders do have the same meaning; they are an example of a de-facto standard. The conflicts that exist are (a) resolvable, (b) caused by factors that do not apply to our discussion.

Not exactly. I'm thinking of MPL and bind actually. They don't have the same meaning, only a similar one, and they can't be unified. It's the very "standard-ness" that prompted MPL to use the same names in a very similar -- but not identical -- way.

And for the record, Lambda's placeholders cause exactly the same ODR violations, although I'm not sure whether "cause" is the proper term.

You're right, "lead to" would be more accurate. I hope you understand the following: 1. I'm arguing about this because I want to end up convinced of something, and soon -- I'll need to choose customization techniques imminently -- so thank you for engaging me on this. 2. I only brought up the ODR thing as a piece of evidence that problems don't neccessarily get resolved quickly

...

It's all very well that library writers may adjust eventually, but users can't always upgrade, or they can't always upgrade quickly. There ought to be a mechanism for staying out of one another's way.

Such a mechanism does exist.

Yeah, but it's cumbersome, and has a few other problems some of which you've mentioned. With that sentence I was arguing that we ought to have a mechanism that works more smoothly, and suggesting that -- with the right language changes -- avoidance of the problems with the current mechanism does not _have_ to imply the use of ADL.

I maintain that not using this mechanism is better in the long term.

Why?

...

...

This isn't really specific to ADL customization points. Consider, for example, container requirements, where a.begin() must return A::iterator or A::const_iterator. What happens if another library has its own requirements table that specifies different semantics for a.begin()? Can I make my container conform to these requirements as well? Of course not.

That's why generic library writers have developed a guideline to write concept requirements that don't depend on member functions.

Maybe they did. My point is that I never see anti-v.begin() campaigns;

I do. Why do you think Boost.Range is using free functions? Not putting member functions in concept requirements is a well-known generic programming guideline. For years even Scott Meyers has been saying that "interfaces should be extended with free functions," which isn't viewed through the generic customization-point lens, but means the same thing.

it's ADL that gets all the flack.

I think that's because ADL has too many problems besides the one we're discussing right here (intrusive name reservation). Also because once we understand that member function requirements are a bad idea, we're forced to face those other problems and (I at least) anguish over whether to live with them or take the leap into using specialization. And because GCC's liberal interpretation of ADL screws everyone eventually ;-)

...

...

...

And wern't namespaces supposed to solve these issues anyway?

The central question is: can we, the C++ community, decide on a common vocabulary for the primitive operations a type supports? If we can, there is no problem.

I disagree most strongly.

One problem is that not all operations are going to be considered "primitive." More importantly, there should be a way to develop software with confidence that it has a future and scales well, without having to worry that all customizable names are "pending the community's verdict on common meaning."

See above; there is such a way

Sorry, I can't connect the dots. What way?

and the debate is whether not having to worry is a good thing. Customization points are very important and need to be treated with caution.

What kind of caution, if they are associated with a namespace, and why? We could use std::iterator_traits as an example.

Once they become de-facto standards, the library no longer owns them, even if they are in the library's own namespace.

Even if I understood what you meant by "the library no longer owns them, even if they are in the library's own namespace," what are the implications of that? Is std::iterator_traits an example of a de-facto standard customization point in a namespace? There are clearly some (just a very few, IMO) customization points like swap that are really intrinsic. They have to do with the semantics of what Stepanov and friends are calling "value types." It seems to me as though the rest are associated with a particular domain, and it's appropriate to name that domain.

...

...

...

...

...

Just consider the widespread use of numeric types in all kinds of domain-specific applications. Is every library going to pick the same meaning for

zero(x)

??

Yes, I hope so. I also hope that they would pick the same meaning for x+y.

Ok, quick (but serious) question: What are the semantics of zero(x) ?

I don't know; this is Dave's example. Whatever the community decides, as long as it's consistent. The user should learn what it means _once_.

It could take many years for a name like that to settle down, especially if two major libraries with strong user base and backward-compatibility considerations pick competing definitions.

OK; so what alternatives do we have?

1. lib1::numeric_traits<X>::zero( x ); // somewhat unwieldy 2. lib1::zero( x ); // syntactic sugar for the above 3. lib1_zero( x );

What, exactly, are the advantages of #2 over #3?

#3 invokes ADL.

That you can bring lib1::zero into scope with a using declaration and call it unqualified?

Of course not! Getting the ability to make unqualified calls is not the goal here. Rather, the ability to make _qualified_ calls is valuable: it's more predictable, and it says what it means, and it avoids potential name choice collision problems, and...

Current language assumed. In this discussion I do not consider your extension proposal; it will take even more years to settle down.

Fair enough; I need answers urgently for the current language myself. You can ignore my one allusion to extensions in this thread; the rest of what I've written here deals with the current language. Thanks again, -- Dave Abrahams Boost Consulting www.boost-consulting.com

"Peter Dimov" writes:

David Abrahams wrote:

...

"Peter Dimov" writes:

Well, the problem here is that (a non-macro) _1 can't be a value and a type at the same time, not that the two _1s express different notions.

You can do it with a macro??

My own position is that one should pick overloading or specializations based on whether exact type matching better fits... no, make that "is essential for" the design.

IIUC, you're saying that if exact type matching is not _essential_, you'd never use specialization for customization? Wow. That would make it pretty rare. That leaves only cases where derived classes commonly need to use the default (primary template) customization when customizations have been made for their bases.

Potential identifier conflicts come a distant third to me. I understand the problem and the implications, I just don't give it that much weight.

It's not the only reason ADL makes me uneasy, as you know.

...

Not putting member functions in concept requirements is a well-known generic programming guideline. For years even Scott Meyers has been saying that "interfaces should be extended with free functions," which isn't viewed through the generic customization-point lens, but means the same thing.

Scott Meyers's point is that operations that can be expressed in terms of the public interface should be non-friends, which is not the same thing at all.

IMO it's a very closely related idea, IMO.

The primary problem with member functions (and types) as a concept requirement is that they can't be retrofitted to a type.

And that they don't work for builtins.

The fact that a type can't have two members with the same name

?? I can overload member functions.

is a secondary concern, which goes relatively unnoticed compared to the "ADL problem".

...

...

and the debate is whether not having to worry is a good thing. Customization points are very important and need to be treated with caution.

What kind of caution, if they are associated with a namespace, and why? We could use std::iterator_traits as an example.

Once these customization points become well-known, more and more types start to conform to them, and more and more other libraries start to depend on the customization point. This effectively means that this particular customization point can no longer be changed by the original author, because this will break too much code. In some cases it even changes the meaning of the customization point (usually to a subset of the original).

Okay, I understand that in theory, but have we seen it in practice?

...

...

Once they become de-facto standards, the library no longer owns them, even if they are in the library's own namespace.

Even if I understood what you meant by "the library no longer owns them, even if they are in the library's own namespace," what are the implications of that? Is std::iterator_traits an example of a de-facto standard customization point in a namespace?

The implication of that is that customization points need to be minimized

Of course. Delay generalization and parameterization.

and their semantics - carefully chosen. They are even more important than the (rest of the) public interface of the library, because they can affect and shape the code of people that don't even use this particular library.

So does the rest of the public interface. I'm not sure about the weight you're giving to these things. People supply these customization points at most once per component, and it's a "private matter between two consenting programmers." It doesn't need to affect other users of either programmers' code -- unless of course you have to worry about future name collisions ;-)

I see potential identifier collisions as just one of the things can go wrong, not as the only danger.

Oh, I fully agree.

To take iterator_traits<X>::reference as an example, a carefully chosen meaning for it would probably be "the return type of the expression *x", which isn't really domain specific. Once libraries start using it you can no longer turn back and redefine it as something that only makes sense for iterators.

Uh, wait. iterator_traits was not well designed, I'll grant you, but all the same, I'd call using iterator_traits<X>::reference to mean "the return type of *x" a definite no-no. Just think about the consequences of all those other type names in iterator_traits.

difference_type, the return type of the expression x - y, also makes sense in a non-iterator context.

Yeah, but this is clear abuse. If it wasn't clear, we'd have seen it done over and over. I haven't ever seen it.

...

There are clearly some (just a very few, IMO) customization points like swap that are really intrinsic. They have to do with the semantics of what Stepanov and friends are calling "value types." It seems to me as though the rest are associated with a particular domain, and it's appropriate to name that domain.

I can agree that most customization points are associated with a particular domain, but this doesn't mean that they are associated with a particular library from that domain.

Some library has to introduce them.

In my experience - which is not that extensive - well thought out customization points can be, and are, used outside of the context of the library that created them.

Maybe. You have examples?

They are a part of a domain to the extent that the type they are associated with is part of that domain, not because of the originating library.

Let's see: get_pointer is part of the domain of pointer-like types. Not part of the domain of iterators and the domain of smart pointers. swap is part of the domain of fundamental value-type operations. There's no way that you'll convince me that swap is part of the domain of generalized containers and also of numeric types, etc., just because types from all those domains can be swapped. The abstract swap operation belongs to the domain of the things they have in common. Anyway, that's what I mean by "domain," so if you meant something else, please re-read what I wrote in newly-understood context.

Example: I can use intrusive_ptr_add_ref to increment the reference count of a type without ever including . It is a way for a type to advertize itself as intrusively counted in general, not as suitable for use with boost::intrusive_ptr in particular.

Great, but it depends on the type implementing a particular protocol introduced by your library.

If every intrusively counted smart pointer has a different customization interface, users are protected from collisions, but need to mark their types as intrusively counted multiple times, to satisfy each library.

Yes. It's better if they all choose a common interface. That interface should be associated with a namespace.

They would certainly prefer the smart pointer authors getting together, so to speak, and settling on one interface.

But you'll note that the function is not named add_ref, after all. ;-)

Hum, I do note that...

...

...

OK; so what alternatives do we have?

1. lib1::numeric_traits<X>::zero( x ); // somewhat unwieldy 2. lib1::zero( x ); // syntactic sugar for the above 3. lib1_zero( x );

What, exactly, are the advantages of #2 over #3?

#3 invokes ADL.

Yes, yes, but what are the advantages of #2 over #3? ;-)

Ah, I see what you're getting at now. Maybe ADL customization points prefixed by the library name are the way to go, at least until the language gets better. That would make your thing boost_intrusive_ptr_add_ref unless you are intentionally trying to drive a stake in the ground for standardization. Is that better or worse than the use of "domain tags?" You poked a hole in that technique a few years ago, but I don't remember how big a hole. I mean: namespace lib { struct tag {}; template <class T> T zero(T a) { zero(tag,a); } // interface }; namespace my { struct X {}; X zero(lib::tag, X); // customization }; my::X z = lib::zero(my::X()); I realize it's not bulletproof, but it does narrow the possibile problems. -- Dave Abrahams Boost Consulting www.boost-consulting.com

"Peter Dimov" writes:

David Abrahams wrote:

...

"Peter Dimov" writes:

...

David Abrahams wrote:

...

"Peter Dimov" writes:

Well, the problem here is that (a non-macro) _1 can't be a value and a type at the same time, not that the two _1s express different notions.

You can do it with a macro??

Yes, the famous "#define _1 arg1()" trick by Daniel Wallin.

I thought it might be something like that.

...

...

My own position is that one should pick overloading or specializations based on whether exact type matching better fits... no, make that "is essential for" the design.

IIUC, you're saying that if exact type matching is not _essential_, you'd never use specialization for customization? Wow. That would make it pretty rare. That leaves only cases where derived classes commonly need to use the default (primary template) customization when customizations have been made for their bases.

More likely, when derived classes need to fail compilation when a base is customized but a derived is not.

Okay. Those are two of a kind.

...

...

Once these customization points become well-known, more and more types start to conform to them, and more and more other libraries start to depend on the customization point. This effectively means that this particular customization point can no longer be changed by the original author, because this will break too much code. In some cases it even changes the meaning of the customization point (usually to a subset of the original).

Okay, I understand that in theory, but have we seen it in practice?

We haven't seen identifier clashes in practice either. ;-) No, g++ doesn't count.

So maybe we should put everything in the global namespace?

Consider get_pointer. It was once "the protocol that mem_fn uses when faced with a smart pointer" and was not required to return a raw pointer. Now it's "the way to obtain a raw pointer from a pointer-like object" and is no longer used by mem_fn (in its TR1 incarnation). If this isn't an example of how the customization point is not owned by the library, I don't know what is. ;-)

I don't know if citing a library evolution for which you hold all the responsibility really counts. ;-)

...

...

The implication of that is that customization points need to be minimized and their semantics - carefully chosen. They are even more important than the (rest of the) public interface of the library, because they can affect and shape the code of people that don't even use this particular library.

So does the rest of the public interface.

The rest of the public interface does not affect non-users.

I don't get it. Even if author A has to glom a giant ugly fribsackle onto his type so that it can satisfy library B's concept requirements, author C can use A's type with B's functions without ever having to confront the fribsackle herself.

...

I'm not sure about the weight you're giving to these things. People supply these customization points at most once per component, and it's a "private matter between two consenting programmers." It doesn't need to affect other users of either programmers' code -- unless of course you have to worry about future name collisions ;-)

A customization point is a public protocol that needs to be followed by types in order to advertize a certain property or operation. I don't see how it can be a private matter. Library A introduces customization point f(x), library B defines f(y) for its type Y, library C uses f(x) in order to benefit from the fact that there are already types Y that support the protocol. These three libraries are totally separate.

You mean that the customization point is automatically up-for-grabs for any library to use, as soon as you advertise that it makes a type work with some particular library. Well, I guess that's the difference between specialization and overloading. With specialization, you sorta need to have one of that library's headers around to get the declaration.

...

Uh, wait. iterator_traits was not well designed, I'll grant you, but all the same, I'd call using iterator_traits<X>::reference to mean "the return type of *x" a definite no-no. Just think about the consequences of all those other type names in iterator_traits.

Well, what else could it mean? :-)

Leaving aside the fact that in real life it is underspecified and used inconsistently, it could mean "the return type of *x where x is an iterator."

...

...

difference_type, the return type of the expression x - y, also makes sense in a non-iterator context.

Yeah, but this is clear abuse. If it wasn't clear, we'd have seen it done over and over. I haven't ever seen it.

Why is it a clear abuse?

Come, come, my man! Because of the way iterator_traits is named, first of all. Also because of the way the primary template is defined. The normal way to satisfy iterator_traits is to inject nested typedefs. If you want to use it to get difference_type for all subtractable types, you have to add a bunch of irrelevant typedefs, including iterator_category. And specializing iterator_traits and leaving out a type is almost as weird.

...

...

In my experience - which is not that extensive - well thought out customization points can be, and are, used outside of the context of the library that created them.

Maybe. You have examples?

get_pointer? intrusive_ptr_*?

Okay.

Right. There is nothing that links get_pointer or swap to a particular library. Whether get_pointer or swap makes sense for a type X is determined solely by X, not by the library that happened to introduce get_pointer or swap.

No, it's also determined by the specification of requirements for get_pointer and swap. These specifications came with a particular library. get_pointer, in particular, seems like it could easily collide someday.

...

...

Example: I can use intrusive_ptr_add_ref to increment the reference count of a type without ever including . It is a way for a type to advertize itself as intrusively counted in general, not as suitable for use with boost::intrusive_ptr in particular.

Great, but it depends on the type implementing a particular protocol introduced by your library.

Right. But "introduced by" and "owned by" are not the same thing. Once it's introduced and adopted, the genie is out of the bottle.

What is your meaning for "owned by?"

...

...

If every intrusively counted smart pointer has a different customization interface, users are protected from collisions, but need to mark their types as intrusively counted multiple times, to satisfy each library.

Yes. It's better if they all choose a common interface. That interface should be associated with a namespace.

If they all choose a common interface, why should it be protected by a namespace? The identifier is now a de-facto standard. It doesn't need protection.

Because people devlop in different domains. I can _easily_ imagine some person writing a boost::addressof with the name get_pointer. If they develop a big application in a single namespace with their own smart pointers and put this get_pointer in that namespace, they might have problems using Boost. Of course then there's the argument that people really ought to be making nice little granular namespaces to encapsulate types and their ADL customizations. At least then, a case like the above won't occur (a customization point colliding with a general utility function). That only leaves customization points to collide with one another, and only when a type is explicitly adapted to two libraries. In that case I guess the author can resort to some kind of wrapper.

...

Ah, I see what you're getting at now. Maybe ADL customization points prefixed by the library name are the way to go, at least until the language gets better.

On a more practical note, I think that making the identifier "sufficiently unique" is enough. boost_add_ref would be fine too, standardization notwithstanding.

Yeah, probably.

...

Is that better or worse than the use of "domain tags?" You poked a hole in that technique a few years ago, but I don't remember how big a hole. I mean:

namespace lib { struct tag {};

template <class T> T zero(T a) { zero(tag,a); } // interface };

namespace my { struct X {};

X zero(lib::tag, X); // customization };

my::X z = lib::zero(my::X());

I realize it's not bulletproof, but it does narrow the possibile problems.

I don't like domain tags much. Seems like a fairly high price to pay for dubious returns.

What's the cost, overall? You may "need" such an interface dispatching function anyway, to deal with builtin types.

I only use such tags when I need to inject a namespace for ADL purposes via the tag.

Example, please? -- Dave Abrahams Boost Consulting www.boost-consulting.com

"Peter Dimov" writes:

It is actually not _that_ unreasonable to put ADL customization point defaults in the global namespace and dispense with the "using" idiom. Moderately unreasonable, maybe. :-)

I'm interested in why you say that. After all, the likelihood of collision is infinitesimal, right? ;-)

...

...

Consider get_pointer. It was once "the protocol that mem_fn uses when faced with a smart pointer" and was not required to return a raw pointer. Now it's "the way to obtain a raw pointer from a pointer-like object" and is no longer used by mem_fn (in its TR1 incarnation). If this isn't an example of how the customization point is not owned by the library, I don't know what is. ;-)

I don't know if citing a library evolution for which you hold all the responsibility really counts. ;-)

I am not responsible for the evolution of get_pointer. tr1::mem_fn doesn't even use it.

So who's using it? [And why doesn't mem_fn use it?]

...

...

...

...

The implication of that is that customization points need to be minimized and their semantics - carefully chosen. They are even more important than the (rest of the) public interface of the library, because they can affect and shape the code of people that don't even use this particular library.

So does the rest of the public interface.

The rest of the public interface does not affect non-users.

I don't get it. Even if author A has to glom a giant ugly fribsackle onto his type so that it can satisfy library B's concept requirements, author C can use A's type with B's functions without ever having to confront the fribsackle herself.

Um, I beg your pardon? ;-)

Having a problem with the term "fribsackle?"

Library B defines requirements. Author A satisfies them by defining a function or specializing a class template. Author C uses A's public interface, which _includes_ the function or the specialization. Ergo, B's customization points

Aha! So you admit B owns these customization points! ;-)

affect C, who does not use B and may not even have heard of it.

You apparently view these implementations of B's customization points as part of A's interface. But these customizations might be supplied by a third party, adapting A to B (yes, I know there's a problem when multiple third parties get involved). I tend to see them as something A does for B's benefit, and not neccessarily for the rest of the world.

...

...

...

I'm not sure about the weight you're giving to these things. People supply these customization points at most once per component, and it's a "private matter between two consenting programmers." It doesn't need to affect other users of either programmers' code -- unless of course you have to worry about future name collisions ;-)

A customization point is a public protocol that needs to be followed by types in order to advertize a certain property or operation. I don't see how it can be a private matter. Library A introduces customization point f(x), library B defines f(y) for its type Y, library C uses f(x) in order to benefit from the fact that there are already types Y that support the protocol. These three libraries are totally separate.

You mean that the customization point is automatically up-for-grabs for any library to use, as soon as you advertise that it makes a type work with some particular library.

Well, I guess that's the difference between specialization and overloading. With specialization, you sorta need to have one of that library's headers around to get the declaration.

It doesn't matter, really. If the customization point is useful, it will be used. The customization points define the interface of a domain-specific class, to use your terminology.

I don't view the class as domain-specific neccessarily. Most classes will cross domains. For example, swap, from the value-type domain, applies to almost everything. I also don't view those things as really being the interface of a class. That piece of interface was defined and specified by someone else. Maybe when you say "class" you mean something like "Concept," i.e. swappable?

This interface will then be picked up by others.

Of course you _could_ define the customization point in such a way so that its usefulness to others is minimized.

Heh, yes.

Eh, of course one wouldn't use iterator_traits<>::difference_type in such a way, but I wouldn't expect you to define this kind of a customization point. You would define difference_type<X>::type, probably, to which your objections do not apply.

Right.

Anyway, my point was just that good customization points transcend a specific library, if not the whole domain.

You seem to have a point.

iterator_traits isn't an example of a good customization point.

Tell me (all) about it.

...

...

Right. But "introduced by" and "owned by" are not the same thing. Once it's introduced and adopted, the genie is out of the bottle.

What is your meaning for "owned by?"

Controlled by. Something that you can change the specification of. Something that you can change the name of. Something you can change the namespace of, if you will.

Okay.

...

...

I don't like domain tags much. Seems like a fairly high price to pay for dubious returns.

What's the cost, overall? You may "need" such an interface dispatching function anyway, to deal with builtin types.

The cost is the extra parameter and the dependency on the tag header, and with the utility function infrastructure in place, a class template instead of a tag isn't very far.

But they have many disadvantages, including not matching derived classes.

...

...

I only use such tags when I need to inject a namespace for ADL purposes via the tag.

Example, please?

I'll need to think about it. A quick scan doesn't reveal anything similar, so I might have dropped this technique. I _think_ that it had to do with the fact that one can't put overloads into std. I had an ADL interface f(x, y), where the x'es came from different namespaces, and I needed to define f( _, std::vector ). I see in the code that I have "solved" this problem by putting all x'es in the same namespace. What a hack. ;-) The other option was to add a tag and put the std:: related overloads in that tag's namespace.

Thanks.

Maybe I'll just bite the bullet and start putting overloads in std instead one day.

Live dangerously or don't live at all ;-) -- Dave Abrahams Boost Consulting www.boost-consulting.com

"Peter Dimov" writes:

David Abrahams wrote:

...

"Peter Dimov" writes:

...

We haven't seen identifier clashes in practice either. ;-) No, g++ doesn't count.

So maybe we should put everything in the global namespace?

It is actually not _that_ unreasonable to put ADL customization point defaults in the global namespace and dispense with the "using" idiom. Moderately unreasonable, maybe. :-)

So let's talk about that: template <class T> T* get_pointer(T*); namespace foo { struct A {}; A* get_pointer(A const&); template <class T> T f(T const& x) { return get_pointer(x); } } namespace bar { template <class T> T f(T const& x) { return get_pointer(x); } } int x; int* q = bar::f(&x); int* p = foo::f(&x); // problem As long as you go with the "Herb Sutter Rule" of isolating types and their ADL functions in their own namespace, these problems disappear. template <class T> T* get_pointer(T*); namespace foo { namespace baz // { // struct A {}; // <= Here A* get_pointer(A const&); // } // using baz::A; // template <class T> T f(T const& x) { return get_pointer(x); } } namespace bar { template <class T> T f(T const& x) { return get_pointer(x); } } int x; int* q = bar::f(&x); int* p = foo::f(&x); Okay IIUC, we have two^H^H^Hthree reasons for using the idiom where ADL is dispatched to a long ugly name (e.g. adl_end, only not that name ;->) that does the actual work: [Do we call this pattern the static template method?] 1. GCC 2. Builtin types. 3. Default behaviors Not sure if 2 and 3 are really the same reason; they might be. I sure don't want people to have to remember different techniques for invoking these things based on whether there's a default or they apply to builtins. Say, wait: every ADL function with a default currently belongs to some library, or at least to some namespace. That's the namespace with which we qualify the name in the using declaration! -- Dave Abrahams Boost Consulting www.boost-consulting.com

Peter Dimov wrote:

David Abrahams wrote:

...

"Peter Dimov" writes:

...

David Abrahams wrote:

...

ADL might not be the best customization solution.

You keep saying that, but I keep disagreeing. ADL is the best customization solution. Not flawless, just better than any of the alternatives.

I guess I haven't seen enough be definitively convinced one way or the other. I have heard stories from people who switch to dispatching via specialization and report how much better things get. Furthermore, Daveed Vandevoorde has convinced me that it is far easier to reason about. The rules for matching partial specializations are trivial compared to the mess you have to consider when there is overloading. The inconvenience of specialization is ugly, but it seems like a one-time cost that may be justified for what it buys us.

That's the thing. It doesn't actually buy us anything. It only claims to avoid potential problems.

I would disagree with that - it buys quite a lot, although for simple uses the extra syntax might not be worth it.

* Uglier syntax for defining a specialization.

IME, this is the biggest cost. I would include also the (one-off) cost of providing a forwarding function to get a sane syntax for the outside world. That is OK if you have a closed set of functions because the forwarding function can be defined by the library, but if the library is merely providing a framework for user-supplied algorithms it becomes a bit messy.

* Coupling; you need to include a primary template.

Ok, but what does that primary template do? Surely nothing, or some very conservative default.

* Does not allow a base-specific version to be picked up automatically for derived classes.

But you can use a partial specialization heirachy instead. Something like template <typename T> struct forward_iterator {}; template <typename T> struct bidirectional_iterator {}; // ... typedef forward_iterator<void> forward_iterator_t; typedef forward_iterator bidirectional_iterator_t; // ... template struct my_algo_impl {}; template struct my_algo_impl { // implement my_algo for forward iterators }; template struct my_algo_impl > { // implement my_algo for bidirectional iterators }; Unfortunately, I don't know of a way of reducing the amount of typing needed for overloads on a deep heirachy, other than macros.

* Does not allow non-exact matches.

You could use enable_if >. Of course that is asking for trouble with ambiguous template specializations, but you would have a similar problem using ADL, with ambiguous overloads. And its certainly easier to control a set of template specializations verus an ADL overload set.

* If four libraries need the same operation, you need to specialize four primary templates.

Compare to four libraries using an ADL lookup on the same function name, but requiring different semantics?

In practice people tend to respect de-facto standards; a + b is an addition, and swap(a, b) swaps a and b. The main fight is over who gets to keep the primary template. But this is not really a problem with ADL customization points, because in their purest form, there is no primary template. The primary template is usually a compatibility workaround for types that do not support the ADL interface yet.

Sure, for de-facto standard operations, ADL works fine. Cheers, Ian

Peter Dimov wrote:

Ian McCulloch wrote:

...

Peter Dimov wrote: <snip>

...

* If four libraries need the same operation, you need to specialize four primary templates.

Compare to four libraries using an ADL lookup on the same function name, but requiring different semantics?

Then these libraries are incompatible with each other, which will be reported as a bug.

How does one decide which library the bug is in? Doesn't this potential for incompatibility mean that ADL erases to a large extent the intended benefit of namespaces? Ben.

"Peter Dimov" wrote in message news:001a01c520c7$6b03f790$6501a8c0@pdimov2... | David Abrahams wrote: | > I guess I haven't seen enough be definitively convinced one way or the | > other. I have heard stories from people who switch to dispatching via | That's the thing. It doesn't actually buy us anything. It only claims to | avoid potential problems. | * Does not allow a base-specific version to be picked up automatically for | derived classes. This seems only to be possible with ADL if there is no primary template; otherwise the primary template will often be a better match than the derived type, eg. #include <iostream> namespace Foo { template< class T > void foo( const T& r ) { std::cout << "foo"; } } namespace Boo { //template< class T > struct X { }; //template< class T > struct Y : public X//<T> { }; // template< class T > void foo( const X& r ) { std::cout << "boo"; } } int main() { // // This statement will alter the behavior! // Therefore, all classes that overload // foo, must specialize foo if they are templates // using namespace Foo; Boo::X x; Boo::Y y; foo( x ); foo( y ); } will print "boofoo". -Thorsten

"David Abrahams" wrote in message news:uacpigs4u.fsf@boost-consulting.com... | "Thorsten Ottosen" writes: | | > // | > // This statement will alter the behavior! | > // Therefore, all classes that overload | > // foo, must specialize foo if they are templates | > // | | Wouldn't you need non-existent function template partial | specialization to do that? yeah, the comment is wrong. One must overload foo() for all supported class templates. -Thorsten

Ian McCulloch writes:

...

* Coupling; you need to include a primary template.

Ok, but what does that primary template do?  Surely nothing, or some very conservative default.

Actually you don't need to include a primary template. All you need is a declaration with no body. You can do that without even pulling in a header. -- Dave Abrahams Boost Consulting www.boost-consulting.com

Ian McCulloch writes:

David Abrahams wrote:

...

Ian McCulloch writes:

...

...

* Coupling; you need to include a primary template.

Ok, but what does that primary template do?  Surely nothing, or some very conservative default.

Actually you don't need to include a primary template. All you need is a declaration with no body. You can do that without even pulling in a header.

I think, an empty body is better than a bare declaration. At least, with

template <typename T> struct my_algo_impl {};

you can do SFINAE on whether my_algo_impl<T> is actually defined or not, for some T (ie. using T::result_type, or probably better boost::result_of).

That's a useful technique, but I don't see how it relates to coupling. In order for a user to provide a specialization of some library template for her type, she need only provide the bare declaration. Bare declarations and empty definitions aren't alternatives, they're apples and oranges. -- Dave Abrahams Boost Consulting www.boost-consulting.com

"Thorsten Ottosen" wrote

"Arkadiy Vertleyb" wrote in message ... | Well, then I hate to say this, but IMHO this is a problem in the Boost.Range | design :-(

It is deliberate design. All generic code that uses boost.range should use unqualified calls to enable ADL. ... | Range(std::vector > > ) | | Now ADL will use std, boost, MyNamespace, boost::multi_index, and boost::mpl | to find Range. There is absolutely no guarantee that it won't find | conflicting functions :-(

I don't get this. Surely one of the functions would be a better match than the others and hence called.

How is namespace MyNamespace { template<class T> end(const T&); } is better match than namespace YourNamespace { template<class T> end(const T&); } ? And now: MyNamespace::FooYourNamespace::Bar obj; end(obj); // ????? Regards, Arkadiy

"Arkadiy Vertleyb" wrote | "Thorsten Ottosen" wrote | > "Arkadiy Vertleyb" wrote in message

| > I don't get this. Surely one of the functions would be a better match

"Thorsten Ottosen" wrote than

| > the others and hence called. | | How is | | namespace MyNamespace | { | template<class T> end(const T&); | } | | is better match than | | namespace YourNamespace | { | template<class T> end(const T&); | } | ? | | And now: | | MyNamespace::FooYourNamespace::Bar obj; | end(obj); // ?????

Why would any function but the primary template be taking a const T& param, that is, why don't your YourNamespace::end() refer to some class in YourNamespace?

Because one may have many unrelated templates that support the same concept. Consider your range library. What if one wants to write end() that is good for any std container? I am not saying that taking "const T&" is a good thing to do. All that I am saying -- it is legal C++. And one should be OK doing this in their own namespace. The worst thing about this is that your library can clash with not a user code, but with some other library that user has no control about... Regards, Arkadiy

Arkadiy Vertleyb wrote:

The GCC's ADL is sure broken, but this only shows up in combination with another problem -- unqualified calls.

That's because ADL only applies to unqualified calls. ;-)

Just fixing ADL would not solve the problem -- MPL is free to have a *function* called end().

Overload resolution usually sorts them out. The problem with finding non-functions is that it never gets the chance to kick in.

Eric Niebler wrote:

Sounds like the problem is not in STL but in GCC's implementation of ADL, which is finding class names. In this case, the collision isn't in STL, it is a collision of end() from Boost.Range and end<> from MPL. Changing the STL implementation will *not* fix this problem. My understanding of ADL is that it should be used to locate *function* overloads. It is meaningless to find class names using ADL. Until gcc's rules for ADL are fixed, this problem will persist.

Apparently their position is that argument-dependent lookup should apply to names, just like ordinary lookup does. Sounds nice in theory, but brings no benefits and causes a lot of problems in practice. http://www.open-std.org/JTC1/SC22/WG21/docs/cwg_active.html#218