boost/libs/iterator/doc/issues.rst

   1 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   2  Problem with ``is_writable`` and ``is_swappable`` in N1550_
   3 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   4
   5 .. _N1550: http://www.boost-consulting.com/writing/n1550.html
   6 .. _N1530: http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1530.html
   7
   8 :Author: David Abrahams and Jeremy Siek
   9 :Contact: dave@boost-consulting.com, jsiek@osl.iu.edu
  10 :Organization: `Boost Consulting`_, Indiana University Bloomington
  11 :date: $Date$
  12 :Copyright: Copyright David Abrahams, Jeremy Siek 2003. Use, modification and
  13       distribution is subject to the Boost Software License,
  14       Version 1.0. (See accompanying file LICENSE_1_0.txt or copy
  15       at http://www.boost.org/LICENSE_1_0.txt)
  16
  17 .. _`Boost Consulting`: http://www.boost-consulting.com
  18
  19 .. contents:: Table of Contents
  20
  21 ==============
  22  Introduction
  23 ==============
  24
  25 The ``is_writable`` and ``is_swappable`` traits classes in N1550_
  26 provide a mechanism for determining at compile time if an iterator
  27 type is a model of the new Writable Iterator and Swappable Iterator
  28 concepts, analogous to ``iterator_traits<X>::iterator_category``
  29 for the old iterator concepts. For backward compatibility,
  30 ``is_writable`` and ``is_swappable`` not only work with new
  31 iterators, but they also are intended to work for old
  32 iterators (iterators that meet the requirements for one of the
  33 iterator concepts in the current standard). In the case of old
  34 iterators, the writability and swapability is deduced based on the
  35 ``iterator_category`` and also the ``reference`` type. The
  36 specification for this deduction gives false positives for forward
  37 iterators that have non-assignable value types.
  38
  39 To review, the part of the ``is_writable`` trait definition which
  40 applies to old iterators is::
  41
  42   if (cat is convertible to output_iterator_tag)
  43       return true;
  44   else if (cat is convertible to forward_iterator_tag
  45            and iterator_traits<Iterator>::reference is a
  46                mutable reference)
  47       return true;
  48   else
  49       return false;
  50
  51 Suppose the ``value_type`` of the iterator ``It`` has a private
  52 assignment operator::
  53
  54   class B {
  55   public:
  56     ...
  57   private:
  58     B& operator=(const B&);
  59   };
  60
  61 and suppose the ``reference`` type of the iterator is ``B&``.  In
  62 that case, ``is_writable<It>::value`` will be true when in fact
  63 attempting to write into ``B`` will cause an error.
  64
  65 The same problem applies to ``is_swappable``.
  66
  67
  68 ====================
  69  Proposed Resolution
  70 ====================
  71
  72 1. Remove the ``is_writable`` and ``is_swappable`` traits, and remove the
  73    requirements in the Writable Iterator and Swappable Iterator concepts
  74    that require their models to support these traits.
  75
  76 2. Change the ``is_readable`` specification to be:
  77    ``is_readable<X>::type`` is ``true_type`` if the
  78    result type of ``X::operator*`` is convertible to
  79    ``iterator_traits<X>::value_type`` and is ``false_type``
  80    otherwise. Also, ``is_readable`` is required to satisfy
  81    the requirements for the UnaryTypeTrait concept
  82    (defined in the type traits proposal).
  83
  84    Remove the requirement for support of the ``is_readable`` trait from
  85    the Readable Iterator concept.
  86
  87
  88 3. Remove the ``iterator_tag`` class.
  89
  90 4. Change the specification of ``traversal_category`` to::
  91
  92     traversal-category(Iterator) =
  93         let cat = iterator_traits<Iterator>::iterator_category
  94         if (cat is convertible to incrementable_iterator_tag)
  95           return cat; // Iterator is a new iterator
  96         else if (cat is convertible to random_access_iterator_tag)
  97             return random_access_traversal_tag;
  98         else if (cat is convertible to bidirectional_iterator_tag)
  99             return bidirectional_traversal_tag;
 100         else if (cat is convertible to forward_iterator_tag)
 101             return forward_traversal_tag;
 102         else if (cat is convertible to input_iterator_tag)
 103             return single_pass_iterator_tag;
 104         else if (cat is convertible to output_iterator_tag)
 105             return incrementable_iterator_tag;
 106         else
 107             return null_category_tag;
 108
 109
 110 ==========
 111  Rationale
 112 ==========
 113
 114 1. There are two reasons for removing ``is_writable``
 115    and ``is_swappable``. The first is that we do not know of
 116    a way to fix the specification so that it gives the correct
 117    answer for all iterators. Second, there was only a weak
 118    motivation for having ``is_writable`` and ``is_swappable``
 119    there in the first place.  The main motivation was simply
 120    uniformity: we have tags for the old iterator categories
 121    so we should have tags for the new iterator categories.
 122    While having tags and the capability to dispatch based
 123    on the traversal categories is often used, we see
 124    less of a need for dispatching based on writability
 125    and swappability, since typically algorithms
 126    that need these capabilities have no alternative if
 127    they are not provided.
 128
 129 2. We discovered that the ``is_readable`` trait can be implemented
 130    using only the iterator type itself and its ``value_type``.
 131    Therefore we remove the requirement for ``is_readable`` from the
 132    Readable Iterator concept, and change the definition of
 133    ``is_readable`` so that it works for any iterator type.
 134
 135 3. The purpose of the ``iterator_tag`` class was to
 136    bundle the traversal and access category tags
 137    into the ``iterator_category`` typedef.
 138    With ``is_writable`` and ``is_swappable`` gone, and
 139    ``is_readable`` no longer in need of special hints,
 140    there is no reason for iterators to provide
 141    information about the access capabilities of an iterator.
 142    Thus there is no need for the ``iterator_tag``. The
 143    traversal tag can be directly used for the
 144    ``iterator_category``. If a new iterator is intended to be backward
 145    compatible with old iterator concepts, a tag type
 146    that is convertible to both one of the new traversal tags
 147    and also to an old iterator tag can be created and use
 148    for the ``iterator_category``.
 149
 150 4. The changes to the specification of ``traversal_category`` are a
 151    direct result of the removal of ``iterator_tag``.
 152