[Boost-commit] svn:boost r54702 - sandbox/committee/LWG/proposals

Subject: [Boost-commit] svn:boost r54702 - sandbox/committee/LWG/proposals
From: dgregor_at_[hidden]
Date: 2009-07-06 00:19:57

Author: dgregor
Date: 2009-07-06 00:19:53 EDT (Mon, 06 Jul 2009)
New Revision: 54702
URL: http://svn.boost.org/trac/boost/changeset/54702

Log:
Fixes for both concepts papers
Text files modified: 
   sandbox/committee/LWG/proposals/explicit-refinement.rst           |    77 +++++++++++++++++++-------------------- 
   sandbox/committee/LWG/proposals/taxonomy-of-concepts-and-maps.rst |    14 +++---                                  
   2 files changed, 44 insertions(+), 47 deletions(-)

Modified: sandbox/committee/LWG/proposals/explicit-refinement.rst
==============================================================================
--- sandbox/committee/LWG/proposals/explicit-refinement.rst	(original)
+++ sandbox/committee/LWG/proposals/explicit-refinement.rst	2009-07-06 00:19:53 EDT (Mon, 06 Jul 2009)
@@ -4,7 +4,7 @@
 
 :Authors: Doug Gregor <doug.gregor_at_[hidden]> and Dave Abrahams <dave_at_[hidden]>
 :Number:  xxxx=xx-xxxx
-:Date: 2009-07-04
+:Date: 2009-07-05
 
 This paper describes a significant type-safety problem with explicit
 refinement, a feature proposed in N2906_ as a replacement for explicit
@@ -17,9 +17,11 @@
 
 In N2831_, we described a type-safety problem with the (then current)
 rvalue-reference binding rules, wherein an rvalue reference could bind
-to an lvalue, silently stealing resources from the lvalue. The
-rvalue-references problem highlighted an important principle of type
-safety:
+to an lvalue, silently stealing resources from the lvalue. The only
+way to avoid this problem was to provide an lvalue-reference overload
+that attracted lvalues more strongly than the rvalue-reference
+overload. This rvalue-references problem highlighted an important
+principle of type safety:
 
 .. Admonition:: Principle of Type-safe Overloading (PTO)
 
@@ -35,16 +37,6 @@
 overload set, due to language rules (such as SFINAE) or physical
 separation in different headers. 
 
-This principle is certainly not new. Back when overloading was
-introduced into C++, various uses of the "overload" keyword were tried
-(and subsequently removed). Bjarne Stroustrup summarizes the issue
-with the "overload" keyword succinctly (from c++std-lib-23985):
-
-    In particular, we *must* pick the right version of an algorithm
-    without a single point of definition of all versions.
-
-The principle of type-safe overloading is based on that same idea.
-
 Explicit Refinement
 ===================
 
@@ -52,20 +44,20 @@
 explicit (non-auto) concepts by introducing a new kind of concept
 refinement, *explicit refinement*, that limits when a concept map can
 be implicitly generated. In particular, when a concept ``B``
-explicitly refines a concept ``A``, a type ``X`` that meets the syntactic
-requirements of both ``B`` and ``A`` will be considered a ``B`` unless
-we are performing some kind of partial ordering (of class template
-partial specialization, concept map templates, or function
+explicitly refines a concept ``A``, a type ``X`` that meets the
+syntactic requirements of both ``B`` and ``A`` will be considered a
+``B`` unless we are performing some kind of partial ordering (of class
+template partial specialization, concept map templates, or function
 templates). In these partial-ordering cases, ``X`` will only be
 considered a ``B`` when there is an explicit concept map ``B<X>`` or
-when the other candidates in the ordering do not involve ``A<X>``.
+when the other candidates in the ordering do not involve ``A<X>``. 
 
 Explicit refinement can best be understood through examples. N2906_
 uses the example of a ``copy()`` algorithm that is overloaded both for
 input iterators (as in the Standard Library) and for contiguous
 iterators. The two constrained templates are::
 
-  // #1
+  // #1: from the Standard Library; safe for all input/output iterators
   template<InputIterator InIter, OutputIterator<auto, InIter::reference> OutIter> 
     OutIter copy(InIter first, InIter last, OutIter result) {
       while (first != last) {
@@ -76,7 +68,7 @@
       return result;
     }
 
-  // #2
+  // #2: possibly in a 3rd-party library; safe and fast for contiguous regions of PODs
   template<ContiguousIterator InIter, ContiguousIterator OutIter>
     requires SameType<InIter::value_type, OutIter::value_type>
           && POD<InIter::value_type>
@@ -90,7 +82,20 @@
 works for any ``InputIterator``/``OutputIterator`` pair with suitable
 value types. The second ``copy()`` implementation uses ``memmove()``
 for far greater performance with both iterators point to contiguous
-blocks with the same POD data type.
+blocks with the same POD data type. The second ``copy()`` is
+considered to be *more specialized*, because it operates on a subset
+of the input types that the first ``copy()`` operates on.
+
+With explicit refinement, one would express the iterator concepts
+hierarchy using implicit concepts and some explicit refinement as, e.g.::
+
+  /*auto*/ concept InputIterator<typename T> { /* ... */ }
+  /*auto*/ concept ForwardIterator<typename T> : explicit InputIterator<T> { /* ... */ }
+  /*auto*/ concept BidirectionalIterator<typename T> : ForwardIterator<T> { /* ... */ }
+  /*auto*/ concept RandomAccessIterator<typename T> : BidirectionalIterator<T> { /* ... */ }
+  /*auto*/ concept ContiguousIterator<typename T> : explicit RandomAccessIterator<T> { 
+    requires LvalueReference<reference> && LvalueReference<subscript_reference>; 
+  }
 
 Next, we consider two calls to ``copy()``::
 
@@ -101,29 +106,20 @@
 
 Ideally, the first call should invoke the ``copy()`` marked #1, since a deque
 does not store its contents in contiguous memory. The second call
-should invoke the ``copy())`` marked #2, providing the ``memmove()``
+should invoke the ``copy()`` marked #2, providing the ``memmove()``
 optimization automatically. Any other solution either misses an
 optimization opportunity or leads to run-time errors. 
 
-With explicit refinement, one would express the iterator concepts
-hierarchy using implicit concepts and some explicit refinement as::
-
-  /*auto*/ concept InputIterator<typename T> { /* ... */ }
-  /*auto*/ concept ForwardIterator<typename T> : explicit InputIterator<T> { /* ... */ }
-  /*auto*/ concept BidirectionalIterator<typename T> : ForwardIterator<T> { /* ... */ }
-  /*auto*/ concept RandomAccessIterator<typename T> : BidirectionalIterator<T> { /* ... */ }
-  /*auto*/ concept ContiguousIterator<typename T> : explicit RandomAccessIterator<T> { 
-    requires LvalueReference<reference> && LvalueReference<subscript_reference>; 
-  }
-
-Now, consider the call to ``copy()`` that provides ``deque<int>``
-iterator arguments. Both versions of ``copy()`` could be called,
-because ``deque<int>::iterator`` syntactically meets the requirements
-of both ``InputIterator`` and ``ContiguousIterator``. However, the
+Now, consider the call to ``copy(di, di + n, result)``. Syntactically,
+the dequee iterators meet all of the requirements of the
+``ContiguousIterator`` concept (along with all of the other
+concepts), so the compiler could implicitly generate a concept map
+``ContiguousIterator<deque<int>::iterator>`` to satisfy the
+requirements of both ``copy()`` algorithms. However, the
 explicit refinement of ``ContiguousIterator`` from
 ``RandomAccessIterator`` (which, transitively, refines
 ``InputIterator``) prevents ``copy()`` #2 from being selected by
-partial ordering. That's good: if we called ``copy()`` #2, the result
+partial ordering (N2906_). That's good: if we called ``copy()`` #2, the result
 would be a run-time failure as the code attempts to ``memmove()`` the
 contents of a deque.
 
@@ -191,7 +187,8 @@
 ``memmove`` optimization in both cases, leading to erroneous run-time
 behavior for the deque.
 
-What happened? The optimized ``copy()`` violates the principle of
+What happened? Due to the use of explicit refinement in the iterator
+concepts hierarchy, the optimized ``copy()`` violates the principle of
 type-safe overloading, because it only properly rejects iterators that 
 syntactically meet the requirements of ``ContiguousIterator`` (but
 don't semantically meet those requirements) when the

Modified: sandbox/committee/LWG/proposals/taxonomy-of-concepts-and-maps.rst
==============================================================================
--- sandbox/committee/LWG/proposals/taxonomy-of-concepts-and-maps.rst	(original)
+++ sandbox/committee/LWG/proposals/taxonomy-of-concepts-and-maps.rst	2009-07-06 00:19:53 EDT (Mon, 06 Jul 2009)
@@ -332,7 +332,7 @@
     template <Swappable T, Swappable U>
     concept_map Swappable<pair<T,U> >
     {
-        swap(pair<T,U>& lhs, pair<T,U>& rhs) 
+        void swap(pair<T,U>& lhs, pair<T,U>& rhs) 
         { 
             swap(lhs.first,rhs.first); 
             swap(lhs.second,rhs.second);
@@ -361,20 +361,20 @@
   ``LessThanComparable`` looks like::
 
     template <LessThanComparable T, class A> 
-    bool operator< (const list<T,A>& x, const list<T,A>& y); 
+      bool operator< (const list<T,A>& x, const list<T,A>& y); 
     template <LessThanComparable T, class A> 
-    bool operator> (const list<T,A>& x, const list<T,A>& y); 
+      bool operator> (const list<T,A>& x, const list<T,A>& y); 
     template <LessThanComparable T, class A> 
-    bool operator>=(const list<T,A>& x, const list<T,A>& y); 
+      bool operator>=(const list<T,A>& x, const list<T,A>& y); 
     template <LessThanComparable T, class A> 
-    bool operator<=(const list<T,A>& x, const list<T,A>& y); 
+      bool operator<=(const list<T,A>& x, const list<T,A>& y); 
 
   which can be simplified, using an exported concept map, to::
 
     template <LessThanComparable T, class A>
     export concept_map LessThanComparable<list<T,A> >
     {
-        bool operator<(const list<T,A>& x, const list<T,A>& y);
+        bool operator<(const list<T,A>& x, const list<T,A>& y) { /*...*/ }
     };
 
   (without exported concept maps, the intended public interface would
@@ -408,7 +408,7 @@
 Adaptive Mapping
 ----------------
 
-Adaptative mapping is used to fulfill a concept's requirements that
+Adaptive mapping is used to fulfill a concept's requirements that
 are already expressed, but in a different form.  For example, one can
 use adaptive mapping to represent the edge connectivity of a graph
 using the nonzero elements of a sparse matrix (a technique used in