| 1 | <?xml version="1.0" encoding="utf-8" ?> |
|---|
| 2 | <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> |
|---|
| 3 | <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> |
|---|
| 4 | <head> |
|---|
| 5 | <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> |
|---|
| 6 | <meta name="generator" content="Docutils 0.3.6: http://docutils.sourceforge.net/" /> |
|---|
| 7 | <title>Problem with is_writable and is_swappable in N1550</title> |
|---|
| 8 | <link rel="stylesheet" href="default.css" type="text/css" /> |
|---|
| 9 | </head> |
|---|
| 10 | <body> |
|---|
| 11 | <h1 class="title">Problem with <tt class="literal"><span class="pre">is_writable</span></tt> and <tt class="literal"><span class="pre">is_swappable</span></tt> in <a class="reference" href="http://www.boost-consulting.com/writing/n1550.html">N1550</a></h1> |
|---|
| 12 | <div class="document" id="problem-with-is-writable-and-is-swappable-in-n1550"> |
|---|
| 13 | <table class="field-list" frame="void" rules="none"> |
|---|
| 14 | <col class="field-name" /> |
|---|
| 15 | <col class="field-body" /> |
|---|
| 16 | <tbody valign="top"> |
|---|
| 17 | <tr class="field"><th class="field-name">Author:</th><td class="field-body">David Abrahams and Jeremy Siek</td> |
|---|
| 18 | </tr> |
|---|
| 19 | <tr class="field"><th class="field-name">Contact:</th><td class="field-body"><a class="reference" href="mailto:dave@boost-consulting.com">dave@boost-consulting.com</a>, <a class="reference" href="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</a></td> |
|---|
| 20 | </tr> |
|---|
| 21 | <tr class="field"><th class="field-name">Organization:</th><td class="field-body"><a class="reference" href="http://www.boost-consulting.com">Boost Consulting</a>, Indiana University Bloomington</td> |
|---|
| 22 | </tr> |
|---|
| 23 | <tr class="field"><th class="field-name">date:</th><td class="field-body">$Date: 2004/11/02 14:31:17 $</td> |
|---|
| 24 | </tr> |
|---|
| 25 | <tr class="field"><th class="field-name">Copyright:</th><td class="field-body">Copyright David Abrahams, Jeremy Siek 2003. Use, modification and |
|---|
| 26 | distribution is subject to the Boost Software License, |
|---|
| 27 | Version 1.0. (See accompanying file LICENSE_1_0.txt or copy |
|---|
| 28 | at <a class="reference" href="http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)</td> |
|---|
| 29 | </tr> |
|---|
| 30 | </tbody> |
|---|
| 31 | </table> |
|---|
| 32 | <div class="contents topic" id="table-of-contents"> |
|---|
| 33 | <p class="topic-title first"><a name="table-of-contents">Table of Contents</a></p> |
|---|
| 34 | <ul class="simple"> |
|---|
| 35 | <li><a class="reference" href="#introduction" id="id1" name="id1">Introduction</a></li> |
|---|
| 36 | <li><a class="reference" href="#proposed-resolution" id="id2" name="id2">Proposed Resolution</a></li> |
|---|
| 37 | <li><a class="reference" href="#rationale" id="id3" name="id3">Rationale</a></li> |
|---|
| 38 | </ul> |
|---|
| 39 | </div> |
|---|
| 40 | <div class="section" id="introduction"> |
|---|
| 41 | <h1><a class="toc-backref" href="#id1" name="introduction">Introduction</a></h1> |
|---|
| 42 | <p>The <tt class="literal"><span class="pre">is_writable</span></tt> and <tt class="literal"><span class="pre">is_swappable</span></tt> traits classes in <a class="reference" href="http://www.boost-consulting.com/writing/n1550.html">N1550</a> |
|---|
| 43 | provide a mechanism for determining at compile time if an iterator |
|---|
| 44 | type is a model of the new Writable Iterator and Swappable Iterator |
|---|
| 45 | concepts, analogous to <tt class="literal"><span class="pre">iterator_traits<X>::iterator_category</span></tt> |
|---|
| 46 | for the old iterator concepts. For backward compatibility, |
|---|
| 47 | <tt class="literal"><span class="pre">is_writable</span></tt> and <tt class="literal"><span class="pre">is_swappable</span></tt> not only work with new |
|---|
| 48 | iterators, but they also are intended to work for old |
|---|
| 49 | iterators (iterators that meet the requirements for one of the |
|---|
| 50 | iterator concepts in the current standard). In the case of old |
|---|
| 51 | iterators, the writability and swapability is deduced based on the |
|---|
| 52 | <tt class="literal"><span class="pre">iterator_category</span></tt> and also the <tt class="literal"><span class="pre">reference</span></tt> type. The |
|---|
| 53 | specification for this deduction gives false positives for forward |
|---|
| 54 | iterators that have non-assignable value types.</p> |
|---|
| 55 | <p>To review, the part of the <tt class="literal"><span class="pre">is_writable</span></tt> trait definition which |
|---|
| 56 | applies to old iterators is:</p> |
|---|
| 57 | <pre class="literal-block"> |
|---|
| 58 | if (cat is convertible to output_iterator_tag) |
|---|
| 59 | return true; |
|---|
| 60 | else if (cat is convertible to forward_iterator_tag |
|---|
| 61 | and iterator_traits<Iterator>::reference is a |
|---|
| 62 | mutable reference) |
|---|
| 63 | return true; |
|---|
| 64 | else |
|---|
| 65 | return false; |
|---|
| 66 | </pre> |
|---|
| 67 | <p>Suppose the <tt class="literal"><span class="pre">value_type</span></tt> of the iterator <tt class="literal"><span class="pre">It</span></tt> has a private |
|---|
| 68 | assignment operator:</p> |
|---|
| 69 | <pre class="literal-block"> |
|---|
| 70 | class B { |
|---|
| 71 | public: |
|---|
| 72 | ... |
|---|
| 73 | private: |
|---|
| 74 | B& operator=(const B&); |
|---|
| 75 | }; |
|---|
| 76 | </pre> |
|---|
| 77 | <p>and suppose the <tt class="literal"><span class="pre">reference</span></tt> type of the iterator is <tt class="literal"><span class="pre">B&</span></tt>. In |
|---|
| 78 | that case, <tt class="literal"><span class="pre">is_writable<It>::value</span></tt> will be true when in fact |
|---|
| 79 | attempting to write into <tt class="literal"><span class="pre">B</span></tt> will cause an error.</p> |
|---|
| 80 | <p>The same problem applies to <tt class="literal"><span class="pre">is_swappable</span></tt>.</p> |
|---|
| 81 | </div> |
|---|
| 82 | <div class="section" id="proposed-resolution"> |
|---|
| 83 | <h1><a class="toc-backref" href="#id2" name="proposed-resolution">Proposed Resolution</a></h1> |
|---|
| 84 | <ol class="arabic"> |
|---|
| 85 | <li><p class="first">Remove the <tt class="literal"><span class="pre">is_writable</span></tt> and <tt class="literal"><span class="pre">is_swappable</span></tt> traits, and remove the |
|---|
| 86 | requirements in the Writable Iterator and Swappable Iterator concepts |
|---|
| 87 | that require their models to support these traits.</p> |
|---|
| 88 | </li> |
|---|
| 89 | <li><p class="first">Change the <tt class="literal"><span class="pre">is_readable</span></tt> specification to be: |
|---|
| 90 | <tt class="literal"><span class="pre">is_readable<X>::type</span></tt> is <tt class="literal"><span class="pre">true_type</span></tt> if the |
|---|
| 91 | result type of <tt class="literal"><span class="pre">X::operator*</span></tt> is convertible to |
|---|
| 92 | <tt class="literal"><span class="pre">iterator_traits<X>::value_type</span></tt> and is <tt class="literal"><span class="pre">false_type</span></tt> |
|---|
| 93 | otherwise. Also, <tt class="literal"><span class="pre">is_readable</span></tt> is required to satisfy |
|---|
| 94 | the requirements for the UnaryTypeTrait concept |
|---|
| 95 | (defined in the type traits proposal).</p> |
|---|
| 96 | <p>Remove the requirement for support of the <tt class="literal"><span class="pre">is_readable</span></tt> trait from |
|---|
| 97 | the Readable Iterator concept.</p> |
|---|
| 98 | </li> |
|---|
| 99 | <li><p class="first">Remove the <tt class="literal"><span class="pre">iterator_tag</span></tt> class.</p> |
|---|
| 100 | </li> |
|---|
| 101 | <li><p class="first">Change the specification of <tt class="literal"><span class="pre">traversal_category</span></tt> to:</p> |
|---|
| 102 | <pre class="literal-block"> |
|---|
| 103 | traversal-category(Iterator) = |
|---|
| 104 | let cat = iterator_traits<Iterator>::iterator_category |
|---|
| 105 | if (cat is convertible to incrementable_iterator_tag) |
|---|
| 106 | return cat; // Iterator is a new iterator |
|---|
| 107 | else if (cat is convertible to random_access_iterator_tag) |
|---|
| 108 | return random_access_traversal_tag; |
|---|
| 109 | else if (cat is convertible to bidirectional_iterator_tag) |
|---|
| 110 | return bidirectional_traversal_tag; |
|---|
| 111 | else if (cat is convertible to forward_iterator_tag) |
|---|
| 112 | return forward_traversal_tag; |
|---|
| 113 | else if (cat is convertible to input_iterator_tag) |
|---|
| 114 | return single_pass_iterator_tag; |
|---|
| 115 | else if (cat is convertible to output_iterator_tag) |
|---|
| 116 | return incrementable_iterator_tag; |
|---|
| 117 | else |
|---|
| 118 | return null_category_tag; |
|---|
| 119 | </pre> |
|---|
| 120 | </li> |
|---|
| 121 | </ol> |
|---|
| 122 | </div> |
|---|
| 123 | <div class="section" id="rationale"> |
|---|
| 124 | <h1><a class="toc-backref" href="#id3" name="rationale">Rationale</a></h1> |
|---|
| 125 | <ol class="arabic simple"> |
|---|
| 126 | <li>There are two reasons for removing <tt class="literal"><span class="pre">is_writable</span></tt> |
|---|
| 127 | and <tt class="literal"><span class="pre">is_swappable</span></tt>. The first is that we do not know of |
|---|
| 128 | a way to fix the specification so that it gives the correct |
|---|
| 129 | answer for all iterators. Second, there was only a weak |
|---|
| 130 | motivation for having <tt class="literal"><span class="pre">is_writable</span></tt> and <tt class="literal"><span class="pre">is_swappable</span></tt> |
|---|
| 131 | there in the first place. The main motivation was simply |
|---|
| 132 | uniformity: we have tags for the old iterator categories |
|---|
| 133 | so we should have tags for the new iterator categories. |
|---|
| 134 | While having tags and the capability to dispatch based |
|---|
| 135 | on the traversal categories is often used, we see |
|---|
| 136 | less of a need for dispatching based on writability |
|---|
| 137 | and swappability, since typically algorithms |
|---|
| 138 | that need these capabilities have no alternative if |
|---|
| 139 | they are not provided.</li> |
|---|
| 140 | <li>We discovered that the <tt class="literal"><span class="pre">is_readable</span></tt> trait can be implemented |
|---|
| 141 | using only the iterator type itself and its <tt class="literal"><span class="pre">value_type</span></tt>. |
|---|
| 142 | Therefore we remove the requirement for <tt class="literal"><span class="pre">is_readable</span></tt> from the |
|---|
| 143 | Readable Iterator concept, and change the definition of |
|---|
| 144 | <tt class="literal"><span class="pre">is_readable</span></tt> so that it works for any iterator type.</li> |
|---|
| 145 | <li>The purpose of the <tt class="literal"><span class="pre">iterator_tag</span></tt> class was to |
|---|
| 146 | bundle the traversal and access category tags |
|---|
| 147 | into the <tt class="literal"><span class="pre">iterator_category</span></tt> typedef. |
|---|
| 148 | With <tt class="literal"><span class="pre">is_writable</span></tt> and <tt class="literal"><span class="pre">is_swappable</span></tt> gone, and |
|---|
| 149 | <tt class="literal"><span class="pre">is_readable</span></tt> no longer in need of special hints, |
|---|
| 150 | there is no reason for iterators to provide |
|---|
| 151 | information about the access capabilities of an iterator. |
|---|
| 152 | Thus there is no need for the <tt class="literal"><span class="pre">iterator_tag</span></tt>. The |
|---|
| 153 | traversal tag can be directly used for the |
|---|
| 154 | <tt class="literal"><span class="pre">iterator_category</span></tt>. If a new iterator is intended to be backward |
|---|
| 155 | compatible with old iterator concepts, a tag type |
|---|
| 156 | that is convertible to both one of the new traversal tags |
|---|
| 157 | and also to an old iterator tag can be created and use |
|---|
| 158 | for the <tt class="literal"><span class="pre">iterator_category</span></tt>.</li> |
|---|
| 159 | <li>The changes to the specification of <tt class="literal"><span class="pre">traversal_category</span></tt> are a |
|---|
| 160 | direct result of the removal of <tt class="literal"><span class="pre">iterator_tag</span></tt>.</li> |
|---|
| 161 | </ol> |
|---|
| 162 | </div> |
|---|
| 163 | </div> |
|---|
| 164 | <hr class="footer" /> |
|---|
| 165 | <div class="footer"> |
|---|
| 166 | <a class="reference" href="issues.rst">View document source</a>. |
|---|
| 167 | Generated by <a class="reference" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source. |
|---|
| 168 | </div> |
|---|
| 169 | </body> |
|---|
| 170 | </html> |
|---|
