Re: [boost] Report from Berlin C++ Standards Committee meeting

From: Paul Mensonides (pmenso57_at_[hidden])
Date: 2006-04-12 17:36:58

> -----Original Message-----
> From: boost-bounces_at_[hidden] 
> [mailto:boost-bounces_at_[hidden]] On Behalf Of Doug Gregor

> > I really hope that is the case.  However, all examples that you've 
> > shown seem to allow transitive compatibility--meaning f can call g 
> > without listing the requirement for g if f and g both have the same 
> > requirements on their operands (etc.).  I don't see how this could 
> > possibly work without binding g at the point of f's 
> definition--i.e. 
> > _not_ during the second phase.
> 
> Ah, this is the issue at hand. Yes, we change when and how 
> names are bound. There are still two phases to I'll use the 
> lower_bound algorithm to illustrate how name resolution
> works:
> 
>    template<InputIterator Iter> void advance(Iter& x, 
> difference_type n); // #1
>    template<BidirectionalIterator Iter> void advance(Iter& x, 
> difference_type n); // #2
> 
>    template<ForwardIterator Iter> where LessThanComparable<value_type>
>    Iter lower_bound(Iter first, Iter last, const value_type& value)
>    {
>      difference_type n = distance(first, last);
>      Iter mid = first;
>      advance(mid, n/2); // we're concerned with this call...
>    }
> 
>    template<RandomAccessIterator Iter> void advance(Iter& x, 
> difference_type n); // #3
> 
> When we initially type-check lower_bound, we need to 
> determine if there is an advance() that we can call. Both #1 
> and #2 have been seen, so we check them. Can we call #1? 
> Sure, because every ForwardIterator is also an InputIterator. 
> Can we call #2? Nope, our ForwardIterator is not guaranteed 
> to be a BidirectionalIterator.

What happens if you have more than one seed?  I.e. there is more than one
function that is callable without a refinement relationship existing between the
two concepts?

> So, we call #1 our "seed" 
> function and use it for type-checking the template. 
> Type-checking succeeds.
> 
> Now, let's consider what happens with this call to lower_bound:
> 
>    vector<int> v; lower_bound(v.begin(), v.end(), 17);
> 
> When instantiating a template that uses concepts, we don't 
> perform the normal second phase lookup with ADL. Instead, we 
> do a more limited lookup designed to make sure that 
> instantiation cannot fail [*]. So, when we instantiate the 
> call to advance() in lower_bound(), we start with our "seed" 
> function #1. We then look for any other functions named 
> "lower_bound" in the same namespace as our seed that are 
> specializations of the seed, and add those functions to our 
> candidate set along with the seed.

Is the name resolution related to the seed is implicitly added to the concept
requirements that are checked immediately prior to instantiation?  Or is the
name resolution done during normal instantiation (with a restricted set of
possible bindings)?

> This means that our 
> candidate set will contain #1, #2, and #3. We perform normal 
> partial ordering of function templates on this candidate set, 
> then end up choosing #3.  
> That's the behavior we want and expect: pick the best 
> function when we instantiate.
> 
> 	Doug
> 
> [*] Yes, instantiation can still fail if partial ordering of 
> function templates returns an ambiguity. We can synthesize it 
> all we want, but it has yet to actually bite us in practice.

Well, it seems like an reasonable tradeoff--though I guarantee that the above
will bite eventually (which is no worse than what we have now).

Regards,
Paul Mensonides